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.

22 pages, 10 figures, 2 tables

References in corpus (11)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• 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
• When Do Neural Networks Outperform Kernel Methods?
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
• 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