2020

Asymptotics of Ridge (less) Regression under General Source Condition

Richards, Dominic, Mourtada, Jaouad, Rosasco, Lorenzo

Understand

We analyze the prediction error of ridge regression in an asymptotic regime where the sample size and dimension go to infinity at a proportional rate.

In particular, we consider the role played by the structure of the true regression parameter.
We observe that the case of a general deterministic parameter can be reduced to the case of a random parameter from a structured prior.
The latter assumption is a natural adaptation of classic smoothness assumptions in nonparametric regression, which are known as source conditions in the the context of regularization theory for inverse problems.

Built on

Solution of incorrectly formulated problems and the regularization method
Andrey N. Tikhonov · 1963
Earlier work this paper cites.
Distribution of eigenvalues for some sets of random matrices
Vladimir A Marčenko and Leonid Andreevich Pastur · 1967
Earlier work this paper cites.
Ridge regression: Biased estimation for nonorthogonal problems
Arthur E Hoerl and Robert W Kennard · 1970
Earlier work this paper cites.
A note on the use of principal components in regression
Ian T Jolliffe · 1982
Earlier work this paper cites.
Backpropagation applied to handwritten zip code recognition
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel · 1989
Earlier work this paper cites.
Signal detection via spectral theory of large dimensional random matrices
Jack W Silverstein and Patrick L Combettes · 1992
Earlier work this paper cites.
Analysis of the limiting spectral distribution of large dimensional random matrices
Jack W Silverstein and Sang-Il Choi · 1995
Earlier work this paper cites.
Regularization of inverse problems
Heinz Werner Engl, Martin Hanke, and Andreas Neubauer · 1996
Earlier work this paper cites.
Gradient-based learning applied to document recognition
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner · 1998
Earlier work this paper cites.
On the distribution of the largest eigenvalue in principal components analysis
Iain M Johnstone · 2001
Earlier work this paper cites.
Geometry of linear ill-posed problems in variable hilbert scales
Peter Mathé and Sergei V Pereverzev · 2003
Earlier work this paper cites.
Random matrix theory and wireless communications
Antonia M Tulino, Sergio Verdú, et al · 2004
Earlier work this paper cites.
On regularization algorithms in learning theory
Frank Bauer, Sergei Pereverzev, and Lorenzo Rosasco · 2007
Earlier work this paper cites.
Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
Debashis Paul · 2007
Earlier work this paper cites.
Optimal rates for regularized least squares regression
Ingo Steinwart, Don Hush, and Clint Scovel · 2009
Earlier work this paper cites.
Spectral analysis of large dimensional random matrices
Zhidong Bai and Jack W Silverstein · 2010
Earlier work this paper cites.
A regularized hotelling’s t 2 test for pathway analysis in proteomic studies
Lin S Chen, Debashis Paul, Ross L Prentice, and Pei Wang · 2011
Earlier work this paper cites.
Geometric sensitivity of random matrix results: consequences for shrinkage estimators of covariance and related statistical methods
Original
Noureddine El Karoui and Holger Kösters · 2011
Earlier work this paper cites.
Eigenvectors of some large sample covariance matrix ensembles
Olivier Ledoit and Sandrine Péché · 2011
Earlier work this paper cites.

Similar

Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators: rigorous results
Original
Noureddine El Karoui · 2013
Cited alongside, same era.
Sample covariance matrices and high-dimensional data analysis
Jianfeng Yao, Shurong Zheng, and ZD Bai · 2015
Cited alongside, same era.
Ridge regression and asymptotic minimax estimation over spheres of growing dimension
Lee H. Dicker · 2016
Cited alongside, same era.
Understanding deep learning requires rethinking generalization
Original
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals · 2016
Cited alongside, same era.
Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate
Mikhail Belkin, Daniel J Hsu, and Partha Mitra · 2018
Cited alongside, same era.
To understand deep learning we need to understand kernel learning
Mikhail Belkin, Siyuan Ma, and Soumik Mandal · 2018
Cited alongside, same era.
High-dimensional asymptotics of prediction: Ridge regression and classification
Edgar Dobriban, Stefan Wager, et al · 2018
Cited alongside, same era.
Random matrices and high-dimensional statistics: beyond covariance matrices
Noureddine El Karoui · 2018
Cited alongside, same era.
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Franck Gabriel, and Clément Hongler · 2018
Cited alongside, same era.
A random matrix approach to neural networks
Cosme Louart, Zhenyu Liao, Romain Couillet, et al · 2018
Cited alongside, same era.
A convergence theory for deep learning via over-parameterization
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song · 2019
Cited alongside, same era.
Reconciling modern machine-learning practice and the classical bias–variance trade-off
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal · 2019
Cited alongside, same era.

Then

On inner-product kernels of high dimensional data
Zhenyu Liao and Romain Couillet · 2019
Later among the works it cites.
Asymptotic risk of least squares minimum norm estimator under the spike covariance model
Original
Yasaman Mahdaviyeh and Zacharie Naulet · 2019
Later among the works it cites.
The generalization error of random features regression: Precise asymptotics and double descent curve
Original
Song Mei and Andrea Montanari · 2019
Later among the works it cites.
Understanding overfitting peaks in generalization error: Analytical risk curves for l _ 2 l\_2 and l _ 1 l\_1 penalized interpolation
Original
Partha P Mitra · 2019
Later among the works it cites.
A jamming transition from under-to over-parametrization affects generalization in deep learning
S Spigler, M Geiger, S d’Ascoli, L Sagun, G Biroli, and M Wyart · 2019
Later among the works it cites.
On the number of variables to use in principal component regression
Ji Xu and Daniel J Hsu · 2019
Later among the works it cites.
High-dimensional dynamics of generalization error in neural networks
Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky · 2020
Closest in time.
When does preconditioning help or hurt generalization?
Original
Shun-ichi Amari, Jimmy Ba, Roger Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu, and Ji Xu · 2020
Closest in time.
Benign overfitting in linear regression
Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler · 2020
Closest in time.
Two models of double descent for weak features
Mikhail Belkin, Daniel Hsu, and Ji Xu · 2020
Closest in time.
Multiple descent: Design your own generalization curve
Original
Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi · 2020
Closest in time.
Asymptotic errors for convex penalized linear regression beyond gaussian matrices
Original
Cédric Gerbelot, Alia Abbara, and Florent Krzakala · 2020
Closest in time.
Implicit regularization of random feature models
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel · 2020
Closest in time.
The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez · 2020
Closest in time.
Just interpolate: Kernel “ridgeless” regression can generalize
Tengyuan Liang, Alexander Rakhlin, et al · 2020
Closest in time.
Harmless interpolation of noisy data in regression
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai · 2020
Closest in time.
Optimal regularization can mitigate double descent
Original
Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma · 2020
Closest in time.
On the optimal weighted l_2 regularization in overparameterized linear regression
Original
Denny Wu and Ji Xu · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…