Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime

Abstract

In this manuscript we consider Kernel Ridge Regression (KRR) under the Gaussian design. Exponents for the decay of the excess generalization error of KRR have been reported in various works under the assumption of power-law decay of eigenvalues of the features co-variance. These decays were, however, provided for sizeably different setups, namely in the noiseless case with constant regularization and in the noisy optimally regularized case. Intermediary settings have been left substantially uncharted. In this work, we unify and extend this line of work, providing characterization of all regimes and excess error decay rates that can be observed in terms of the interplay of noise and regularization. In particular, we show the existence of a transition in the noisy setting between the noiseless exponents to its noisy values as the sample complexity is increased. Finally, we illustrate how this crossover can also be observed on real data sets.

arXiv comment22 pages, 10 figures, 2 tables

References in corpus (25)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Benign Overfitting in Linear Regression
• Deep Neural Networks as Gaussian Processes
• On Lazy Training in Differentiable Programming
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences
• Two models of double descent for weak features
• Statistical Mechanics of Support Vector Networks
• Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks
• Benign overfitting in ridge regression
• Generalisation error in learning with random features and the hidden manifold model
• Random design analysis of ridge regression
• Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results
• When Do Neural Networks Outperform Kernel Methods?
• Surprises in High-Dimensional Ridgeless Least Squares Interpolation
• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Ridge regression and asymptotic minimax estimation over spheres of growing dimension
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
• Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data
• Asymptotics of Ridge (less) Regression under General Source Condition
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model
• Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime

Cited by in corpus (3)

• Gaussian Universality of Perceptrons with Random Labels
• Simplified derivations for high-dimensional convex learning problems
• Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay