On the Intrinsic Dimensions of Data in Kernel Learning

AI summary

Overview

Research area: Statistical learning theory and kernel methods — specifically the theory of intrinsic dimension, geometric measure theory, and approximation theory (Kolmogorov n-widths) as applied to Kernel Ridge Regression.

Technical level: Advanced. The paper works with reproducing kernel Hilbert spaces, Minkowski and Hausdorff dimension, Kolmogorov n-widths, spectral theory of integral operators, and empirical process bounds. It assumes fluency in functional analysis and learning theory.

Scope (one sentence): The paper defines two different notions of the intrinsic dimension of a data distribution's support — a kernel-induced Minkowski dimension and a Kolmogorov n-width-based "effective dimension" — proves how they relate, shows that the effective dimension controls the excess risk of constrained Kernel Ridge Regression, and provides an algorithm for estimating n-widths from finite samples.

What This Paper Is About

The manifold hypothesis says that machine learning should get easier when data lives near a low-dimensional structure, and the goal is to make generalization bounds depend on that intrinsic dimension rather than the ambient dimension. Most existing work assumes the data lies on a smooth low-dimensional manifold, which excludes irregular sets such as fractals. This paper instead uses tools from geometric measure theory to characterize only the support of the data distribution, and it introduces two kernel-based notions of dimension that require no smoothness assumptions on that support.

Key Contributions

1. Two intrinsic-dimension definitions for a kernel and domain. The first, d_ϱ, is the kernel-based upper metric (Minkowski) dimension defined via the canonical pseudometric ϱ(x,y) = ||K(x,·) − K(y,·)||_{H_K}. The second, d_K, is a "kernel-based effective dimension" derived from the decay rate of the Kolmogorov n-widths w_K(n) of the domain embedded in the RKHS. Both depend only on the support Ω of the input distribution, not on the distribution itself.

2. A worst-case link between n-widths and kernel eigenvalues. The paper shows that the Kolmogorov n-widths of a fixed domain characterize the worst-case eigenvalue decay of the integral operator O_{K,μ} over all probability measures μ supported on that domain — a counterpart to Ismagilov's classical theorem in approximation theory.

3. An excess risk bound for constrained KRR in terms of d_K. For the ERM algorithm over the unit ball B_{H_K} of the RKHS, the paper derives a high-probability excess error bound of order O(n^{-(2+d_K)/(2+2d_K)+ε}) for any ε > 0, matching the abstract's stated rate.

4. A sampling algorithm plus a sample-complexity guarantee. Algorithm 1 estimates upper bounds on the n-widths from a finite point set, and under a "C-uniformness" assumption on μ the paper proves that ε-accurate upper bounds on all n-widths can be obtained with high probability from O(ε^{-d_ϱ} log(1/ε)) samples.

Main Findings

• d_K never exceeds d_ϱ. Theorem 1 proves d_K ≤ d_ϱ, using the fact that w_K(n) ≤ ε(n), where ε(n) is derived from the inverse of the covering number N(ε, Ω, ϱ).

• The two dimensions coincide on regular domains. Theorem 2 establishes d_K = d_ϱ for three families: the exponential kernel K(x,y) = e^{-γ||x-y||^a} with a ∈ (0,1] on a Riemann-measurable Ω ⊆ ℝ^d of non-zero volume; the Matérn kernel with ν ∈ (0,1), l > 0 on the same type of domain; and the same exponential kernel on the sphere Ω = S^{d-1}.

• n-widths bound eigenvalue decay in the worst case. For any Borel probability measure μ on Ω, Theorem 3 gives λ_{2n}(O_{K,μ}) ≤ w_K(n)² / n, and shows the bound is essentially tight: lim sup_{n→∞} sup_μ n λ_n(O_{K,μ}) / w_K(n)² ≥ 1/e, where the supremum is over Borel probability measures supported on Ω.

• Explicit excess-risk bound. Theorem 5 states that with probability at least 1 − e^{−x}, the excess risk is at most 1995 B^{1/(1+d_K+ε)} L^{1−1/(1+d_K+ε)} n^{−(2+d_K+ε)/(2(1+d_K+ε))} + (11L+27B)x/n, provided n ≥ B²(3+d_K+ε) N_ε^{2(1+d_K+ε)/(d_K+ε)} / (2L²).

• Interpretation of the rate. As the paper puts it, d_K = 0 (the case for the Gaussian kernel) gives an excess risk rate arbitrarily close to O(1/n), while larger d_K moves the rate toward the typical kernel-method rate O(1/√n). For a kernel like the Laplace kernel with d_K = d_ϱ on regular domains, the rate behaves like O(n^{−(2+d_ϱ)/(2+2d_ϱ)+ε}), aligning with the manifold hypothesis.

• Finite-sample estimation guarantee. Lemma 2 shows √S_t is 1-Lipschitz with respect to ϱ, and Theorem 6 proves that when the finite input set Ω₁ is an ε-net in (Ω, ϱ), Algorithm 1's outputs satisfy w_t ≥ w_K(t) − ε for t = 0, …, T−1.

• C-uniform measures and sample complexity. Definition 1 calls μ C-uniform over Ω if μ(B(x,ε)) ≥ C ε^{d_ϱ} for all x ∈ Ω and small ε; this generalizes uniformity and yields the O(ε^{−d_ϱ} log(1/ε)) sample bound, with fewer samples needed for small n. The remark connects this to the lower d_ϱ-density Θ_*(x, μ) from geometric measure theory.

• Fractal gap between d_K and d_ϱ. Numerical experiments compute d_K for various fractal sets. A key empirical finding is that even for kernels where d_K = d_ϱ provably holds on regular domains — such as the Laplace kernel — the strict inequality d_K < d_ϱ often holds when Ω is fractal. The paper interprets kernels with d_K = d_ϱ as the "least smooth," since they produce the slowest possible decay w_K(n) ≍ n^{−1/d_ϱ} for a given domain geometry.

• Table 1 examples on Ω = S^{d−1}. For the Gaussian kernel e^{−||x−y||²/σ²} with σ > √(2/d), the n-widths decay exponentially fast, d_ϱ = d − 1, and d_K = 0. For the ReLU NTK over max(0,x), w_K(n) ≍ n^{−1/(2d−2)} with both dimensions equal to 2d−2. For NNGP_cos and NNGP_sin, w_K(n) ≪ n^{−1/2}, d_ϱ = d−1, and d_K ≤ 2.

Methodology in Plain English

The approach splits the problem into theory and numerics.

First, the authors define a metric built directly from the kernel: the distance between two points is how far apart their kernel sections K(x,·) and K(y,·) are in the RKHS. Covering the domain with balls under this metric yields a covering number, and the growth rate of that covering number gives the first intrinsic dimension d_ϱ. Separately, they ask how well the RKHS can approximate the whole family {K(x,·) : x ∈ Ω} using an n-dimensional subspace — the Kolmogorov n-width — and the rate at which those widths shrink gives the second dimension d_K.

Next, they connect n-widths to the eigenvalues of the kernel integral operator. The upper bound follows from Ismagilov's theorem. The lower bound (the tightness part) is proved constructively: they build a sequence of points x₁, x₂, … by greedily maximizing the determinant det(K[(X_n, x), (X_n, x)]), and show the empirical measures μ_m = (1/m) Σ δ_{x_i} achieve the worst-case eigenvalue decay. This same greedy construction is exactly what Algorithm 1 implements in practice.

Then they apply the resulting spectral control to the standard Bartlett-style ERM framework, using loss conditions (Lipschitz constant L, and a constant B relating excess risk to L₂ distance; B = 1 for square loss) to obtain the excess risk bound in terms of d_K.

Finally, for the sampling side, they show that the greedy residual quantities S_t(x) are 1-Lipschitz under the kernel metric, so a finite ε-net of the domain suffices to approximate the n-widths from above up to error ε. Counting how many samples are needed for a net to be an ε-net with high probability gives the O(ε^{−d_ϱ} log(1/ε)) sample complexity under C-uniformness. Numerical experiments then compute n-widths and d_K for several kernels and domains, including fractal sets.

Why This Matters

Impact on research. The paper decouples intrinsic dimension from smoothness of the data manifold. Prior bounds of this type typically require a low-dimensional Riemannian manifold; here the support only needs to be a compact set, so fractals and other irregular supports are covered. It also introduces a notion of dimension that responds to the global structure of the kernel rather than just its local Taylor behavior, and it gives a new numerical tool — estimating n-widths from samples — analogous to the widely used practice of estimating eigenvalues from empirical kernel matrices.

Real-world applications (areas the theory speaks to):

• Choosing kernels for data that is not manifold-like — for example signals or images whose supports have fractional Hausdorff dimension — where the analysis suggests smooth kernels can behave as if the data were effectively lower-dimensional than its metric complexity.
• Predicting when kernel regression will be fast: a small d_K (as with the Gaussian kernel) implies rates close to O(1/n), which is useful for deciding whether a kernel is worth the cost on a given problem.
• Model selection between classical kernels, neural tangent kernels, and NNGP kernels, since Table 1 compares their n-width decay rates and effective dimensions on the sphere.
• Diagnosing sample requirements: the O(ε^{−d_ϱ} log(1/ε)) bound tells practitioners roughly how much data an n-width estimate needs.

Industry relevance. Because the results apply to constrained Kernel Ridge Regression — including over the unit ball of the RKHS — they are directly relevant to any pipeline where KRR or kernel-based regularization is used and where generalization guarantees are needed. The paper also notes that the same n-width machinery can be transferred to other kernel methods whenever their statistics are governed by eigenvalue decay, citing the effective dimension of Caponnetto and De Vito and the Signal Capture Threshold of Jacot et al.

Future Directions

• Characterize the fractal gap. The empirical observation that d_K < d_ϱ for kernels like the Laplace kernel on fractal domains — while d_K = d_ϱ provably holds on regular domains — is presented as the source of new conjectures rather than a settled theorem.

• Unfavorable case in Table 1. The entry for NNGP_{max(0,x)^α} with α ≥ 0 lists d_ϱ = (2d−2)/(1+α) marked with a question mark and d_K ≥ (2d−2)/(1+2α), indicating unresolved questions about the exact dimensions for these kernels.

• Extend beyond constrained KRR. The paper remarks that Theorem 3 could be combined with the effective dimension of Caponnetto and De Vito or the Signal Capture Threshold to derive implications for unconstrained KRR — a step left for future work.

• Develop the estimation algorithm into a general tool. The paper positions Algorithm 1 as an analog of empirical eigenvalue estimation, suggesting broader use for studying kernels on general domains beyond the experiments reported here.

Target Audience

This paper is aimed at learning theorists and mathematically inclined machine learning researchers working on kernel methods, generalization bounds, and intrinsic dimension. It will also interest researchers in approximation theory who work with Kolmogorov n-widths, and geometric measure theorists interested in applications to learning. Practitioners will find Section 6 and the numerical tooling relevant, but the theoretical sections assume background in RKHS theory and spectral analysis.

Authors’ abstract

The manifold hypothesis suggests that the generalization performance of machine learning methods improves significantly when the intrinsic dimension of the input distribution's support is low. In the context of KRR, we investigate two alternative notions of intrinsic dimension. The first, denoted $d_ρ$, is the upper Minkowski dimension defined with respect to the canonical metric induced by a kernel function $K$ on a domain $Ω$. The second, denoted $d_K$, is the effective dimension, derived from the decay rate of Kolmogorov $n$-widths associated with $K$ on $Ω$. Given a probability measure $μ$ on $Ω$, we analyze the relationship between these $n$-widths and eigenvalues of the integral operator $φ\to \int_ΩK(\cdot,x)φ(x)dμ(x)$. We show that, for a fixed domain $Ω$, the Kolmogorov $n$-widths characterize the worst-case eigenvalue decay across all probability measures $μ$ supported on $Ω$. These eigenvalues are central to understanding the generalization behavior of constrained KRR, enabling us to derive an excess error bound of order $O(n^{-\frac{2+d_K}{2+2d_K} + ε})$ for any $ε> 0$, when the training set size $n$ is large. We also propose an algorithm that estimates upper bounds on the $n$-widths using only a finite sample from $μ$. For distributions close to uniform, we prove that $ε$-accurate upper bounds on all $n$-widths can be computed with high probability using at most $O\left(ε^{-d_ρ}\log\frac{1}ε\right)$ samples, with fewer required for small $n$. Finally, we compute the effective dimension $d_K$ for various fractal sets and present additional numerical experiments. Our results show that, for kernels such as the Laplace kernel, the effective dimension $d_K$ can be significantly smaller than the Minkowski dimension $d_ρ$, even though $d_K = d_ρ$ provably holds on regular domains.