Research map / Learning theory and algorithms / Kernels and regression theory
On the Saturation Effects of Spectral Algorithms in Large Dimensions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies saturation effects of spectral algorithms (KRR, gradient flow, iterated ridge) for inner-product kernels on the sphere in large-dimensional settings n ≍ d^γ, proving gradient flow is minimax optimal and KRR saturates when s>τ.
Problem
Whether the saturation effect of KRR (failure to reach the minimax lower bound for over-smooth regression functions) occurs for spectral algorithms in large-dimensional kernel regression where n ≍ d^γ, and how the excess-risk rates behave across γ.
Approach
Derives exact excess-risk rates for large-dimensional spectral algorithms with inner product kernels on the sphere, shows early-stopped gradient flow attains an improved minimax lower bound (up to polylog factors), and characterizes periodic plateau, polynomial approximation barrier and saturation as functions of γ, s and qualification τ.
Key results
- Early-stopped kernel gradient flow achieves excess risk Θ_P(d^{-min{γ-p, s(p+1)}}) poly(ln d), matching the improved minimax lower bound up to polylog factors, so it is minimax optimal for any s>0, γ>0.
- Improved minimax lower bound Ω(d^{-min{γ-p, s(p+1)}}) / poly(ln d) replaces the previous d^{-ε} loss.
- For s>τ, spectral algorithms with qualification τ saturate in large dimensions: rate d^{-min{γ-p, (τ(γ-p+1)+p s̃)/(τ+1), s̃(p+1)}} with s̃=min{s,2τ}, showing saturation when s>τ versus s>2τ in fixed dimension.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use optimally tuned kernel gradient flow instead of KRR | Large-dimensional kernel regression · Large-dimensional kernel regression; 1 < s ≤ 2 and γ ∈ (p(s+1)+1, p(s+1)+2s−1), or s > 2 and γ ∈ (p(s+1)+1, (p+1)(s+1)) | excess risk convergence rate: Kernel gradient flow: d^{-\min\{\gamma-p, s(p+1)\}}; KRR: d^{-\min\{\gamma-p, \frac{\gamma-p+p\tilde{s}+1}{2}, \tilde{s} | Helped |
| Use kernel gradient flow with early stopping and optimal tuning | Large-dimensional kernel regression · Large-dimensional kernel regression, any s > 0 and γ > 0 | excess risk convergence rate: \Theta_{\mathbb{P}}(d^{-\min\{\gamma-p, s(p+1)\}})\cdot\text{poly}(\ln(d)) | Helped |
| Use a finite-qualification spectral algorithm when s > τ | Large-dimensional spectral algorithms · Large-dimensional kernel regression, s > τ | excess risk convergence rate: d^{-\min\{\gamma-p, \frac{\tau(\gamma-p+1)+p\tilde{s}}{\tau+1}, \tilde{s}(p+1)\}}; minimax lower bound: d^{-\min\{\gamma | Hurt |
| Replace the previous minimax lower-bound factor d^{-ε} with a logarithmic factor | Minimax lower bound for large-dimensional kernel regression · Large-dimensional kernel regression, any s > 0 and γ > 0 | minimax excess risk lower bound: d^{-\min\{\gamma-p, s(p+1)\}} / \text{poly}(\ln(d)); previous: d^{-\min\{\gamma-p, s(p+1)\}} \cdot d^{-\varepsilon} | Helped |
| Increase γ within the stated plateau interval | Spectral algorithms with s ≤ 2τ · Large-dimensional kernel regression, 0 < s ≤ 2τ and γ ∈ [p(s+1)+s+max{s,τ}/τ−1, (p+1)(s+1)) | excess risk convergence rate: d^{-s(p+1)} | No clear effect |
| Increase γ past p(s+1) within the stated interval | Spectral algorithms with s close to zero · Large-dimensional kernel regression, γ ∈ [p(s+1)+s, (p+1)(s+1)) | excess risk convergence rate: d^{-\min\{\gamma-p, s(p+1)\}} | No clear effect |
| Use KRR with s > 1 in the specified ranges of γ instead of a minimax-optimal method | Kernel ridge regression · Large-dimensional kernel regression, s > 1 and certain ranges of γ | excess risk convergence rate: KRR: d^{-\min\{\gamma-p, \frac{\gamma-p+p\tilde{s}+1}{2}, \tilde{s}(p+1)\}}; minimax lower bound: d^{-\min\{\gamma-p, s( | Hurt |
Surprising findings
- Saturation in large dimensions occurs already when s>τ, whereas in fixed dimension it requires s>2τ.
Limitations
- Analysis restricted to inner product kernels on the uniform sphere with uniform input distribution.
- Results concern optimally tuned regularization; learning curves for arbitrary lambda and kernel interpolation are not covered.
- Rates hold up to poly(ln d) factors and constants depending on s, gamma, etc.
Experimental setup
Metrics: excess risk L2 rate exponent r (Excess risk ≍ d^r)
Baselines: kernel ridge regression kernel interpolation minimax lower bound of Liu and Li
Builds on: kernel ridge regression saturation analysis (fixed dimension) analytic filter function framework large-dimensional KRR consistency results
Closest papers by meaning
- Optimal Rates for Vector-Valued Spectral Regularization Learning Algorithms (NeurIPS 2024 · similarity 0.91)
- Generalization error of spectral algorithms (ICLR 2024 · similarity 0.88)
- Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum (ICML 2024 · similarity 0.87)
- Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.86)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.86)
- Learning Curves of Stochastic Gradient Descent in Kernel Regression (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.