Optimal Rates for the Regularized Least-Squares Algorithm

By Andrea Caponnetto, Ernesto De Vito. 2007

961 citations recorded by the source corpus.

We develop a theoretical analysis of the performance of the regularized least-square algorithm on a reproducing kernel Hilbert space in the supervised learning setting. The presented results hold in the general framework of vector-valued functions; therefore they can be applied to multitask problems. In particular, we observe that the concept of effective dimension plays a central role in the definition of a criterion for the choice of the regularization parameter as a function of the number of samples. Moreover, a complete minimax analysis of the problem is described, showing that the convergence rates obtained by regularized least-squares estimators are indeed optimal over a suitable class of priors defined by the considered kernel. Finally, we give an improved lower rate result describing worst asymptotic behavior on individual probability measures rather than over classes of priors.

Subfields: Computational Mechanics, Control and Systems Engineering, Mathematical Physics, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Control and Systems Engineering

In Mathematical Physics

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, background): “…( λ ) = tr Σ(Σ + λI ) − 1 is the degrees of freedom , a traditional quantity in the analysis of least-squares regression (Hastie and Tibshirani, 1990; Caponnetto and De Vito, 2007), which is always smaller than d max (1 , λ ) and can be upper-bounded explicitly for many examples, as we now explain.”
Density Estimation in Infinite Dimensional Exponential Families (2013, methodology): “…we obtain k ≤ k − k k kk − k k k We now provide an estimate on C ( ˆ C + λI ) − 1 using the idea used in the proof of Theorem 4 (see step 3.1) in [8]. k kk − k ≤ k k ≤ Therefore, by Bernstein’s inequality [35, Theorem 6.14], with probability at least 1 − e − τ over the choice of ( X i ), and…”
Conditional mean embeddings as regressors (2012, methodology): “A can be written as (Caponnetto & De Vito, 2007, Rem.”
Kernel Bayes' Rule (2010, methodology): “The proof idea for the consistency rates of the KBR estimators is similar to [6, 30], in which the basic techniques are taken from the general theory of regularization [8].”
Just Interpolate: Kernel "Ridgeless" Regression Can Generalize (2018, methodology): “Notions like metric entropy [11] or “effective dimension” [9] were employed to analyze the guarantees on the excess loss of Kernel Ridge Regression, even when the model is misspecified.”
Quasi-oracle estimation of heterogeneous treatment effects (2017, methodology): “In the case α = 0 where τ ∗ is within the RKHS used for penalization, we recover the more familiar n − 1 / (1+ p ) rate established by Caponnetto and De Vito (2007).”
Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences (2018, background): “Kernel ridge regression (KRR), which is also known as regularized least-squares [Caponnetto and Vito, 2007] or spline smoothing [Wahba, 1990], arises as a regularized empirical risk minimization problem where the hypothesis space is chosen to be an RKHS Hk.”
Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks (2020, methodology): “[20] Andrea Caponnetto and Ernesto De Vito.”
Spectral Algorithms for Supervised Learning (2008, background): “The optimal choice of the regularization parameter will be a trade-o between these two errors ‐ see (De Vito et al., 2005a; Caponnetto & De Vito, 2006; Smale & Zhou, 2005; Wu et al., 2006) and references therein about the rates for regularized least-squares, and (De Vito et al., 2005c; Bauer et al”
Rademacher Chaos Complexities for Learning the Kernel Problem (2010, neutral): “Our last example is the least square loss for classification, which is extensively studied in the single kernel case (Caponnetto & De Vito, 2007 ; De Vito et al, 2006 ; Smale & Zhou, 2004 ; Zhang, 2004 ).”
Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning (2014, methodology): “Note that, while in the range β ≥ 12 , that implies fρ ∈ HK , it is possible to prove high probability bounds [4, 7, 27, 29], the range 0 < β < 12 considered in this paper is very tricky, see the discussion in [27].”