On the Saturation Effects of Spectral Algorithms in Large Dimensions
Not on the map. Why?
Abstract (arXiv)
The saturation effects, which originally refer to the fact that kernel ridge regression (KRR) fails to achieve the information-theoretical lower bound when the regression function is over-smooth, have been observed for almost 20 years and were rigorously proved recently for kernel ridge regression and some other spectral algorithms over a fixed dimensional domain. The main focus of this paper is to explore the saturation effects for a large class of spectral algorithms (including the KRR, gradient descent, etc.) in large dimensional settings where n asymp dγ. More precisely, we first propose an improved minimax lower bound for the kernel regression problem in large dimensional settings and show that the gradient flow with early stopping strategy will result in an estimator achieving this lower bound (up to a logarithmic factor). Similar to the results in KRR, we can further determine the exact convergence rates (both upper and lower bounds) of a large class of (optimal tuned) spectral algorithms with different qualification τ's. In particular, we find that these exact rate curves (varying along γ) exhibit the periodic plateau behavior and the polynomial approximation barrier. Consequently, we can fully depict the saturation effects of the spectral algorithms and reveal a new phenomenon in large dimensional settings (i.e., the saturation effect occurs in large dimensional setting as long as the source condition s>τ while it occurs in fixed dimensional setting as long as s>2τ).
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 41 of its 63 references that are in the map. First posted on arXiv 1 Mar 2025.
Builds on
41 of 63 references.
References · 41
- 2015Deep Residual Learning for Image Recognitioncited by 52,096
- 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
- 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
- 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
- 2019On Exact Computation with an Infinitely Wide Neural Netcited by 573
- 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 566
- 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
- 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 261
- 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
- 2019Linearized two-layers neural networks in high dimensioncited by 155
- 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
29 more
- 2017Sobolev Norm Learning Rates for Regularized Least-Squares Algorithmcited by 114
- 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
- 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 96
- 2013Early stopping and non-parametric regression: An optimal data-dependent stopping rulecited by 89
- 2021Learning with invariances in random features and kernel modelscited by 89
- 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
- 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
- 2018Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spacescited by 59
- 2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 45
- 2020Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Networkcited by 38
- 2021How rotational invariance of common kernels prevents generalization in high dimensionscited by 32
- 2023On the Eigenvalue Decay Rates of a Class of Neural-Network Related Kernel Functions Defined on General Domainscited by 31
- 2023Generalization Ability of Wide Neural Networks on ℝcited by 30
- 2023Generalization in Kernel Regression Under Realistic Assumptionscited by 27
- 2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimensioncited by 26
- 2021The Three Stages of Learning Dynamics in High-Dimensional Kernel Methodscited by 22
- 2022Precise Learning Curves and Higher-Order Scaling Limits for Dot Product Kernel Regressioncited by 22
- 2021Learning with convolution and pooling operations in kernel methodscited by 21
- 2023On the Optimality of Misspecified Kernel Ridge Regressioncited by 20
- 2022Sharp Asymptotics of Kernel Ridge Regression Beyond the Linear Regimecited by 19
- 2023On the Asymptotic Learning Curves of Kernel Ridge Regression under Power-law Decaycited by 19
- 2020Analyzing the discrepancy principle for kernelized spectral filter learning algorithmscited by 15
- 2024On the Saturation Effect of Kernel Ridge Regressioncited by 13
- 2016Optimal rates for the regularized learning algorithms under general source conditioncited by 11
- 2023Optimal Rate of Kernel Regression in Large Dimensionscited by 11
- 2024Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensionscited by 11
- 2024Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decaycited by 11
- 2023Strong inductive biases provably prevent harmless interpolationcited by 10
- 2024The phase diagram of kernel interpolation in large dimensionscited by 9
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.