Optimal rates for the regularized least-squares algorithm

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

237 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)331-368
Journal / PublicationFoundations of Computational Mathematics
Issue number3
Publication statusPublished - Jul 2007
Externally publishedYes


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. © 2006 Springer.

Research Area(s)

  • Learning theory, Least squares, Model selection, Optimal rates