2020

Regularization in High-Dimensional Regression and Classification via Random Matrix Theory

Lolas, Panagiotis

Understand

We study general singular value shrinkage estimators in high-dimensional regression and classification, when the number of features and the sample size both grow proportionally to infinity.

We allow models with general covariance matrices that include a large class of data generating distributions.
As far as the implications of our results are concerned, we find exact asymptotic formulas for both the training and test errors in regression models fitted by gradient descent, which provides theoretical insights for early stopping as a regularization method.
In addition, we propose a numerical method based on the empirical spectra of covariance matrices for the optimal eigenvalue shrinkage classifier in linear discriminant analysis.

Built on

Discriminant analysis: applications in finance
Alka J Bramhandkar · 1989
Earlier work this paper cites.
Regularized discriminant analysis
Jerome H Friedman · 1989
Earlier work this paper cites.
Analysis on manifolds
James R. Munkres · 1991
Earlier work this paper cites.
On the empirical distribution of eigenvalues of a class of large dimensional random matrices
Jack W Silverstein and ZD Bai · 1995
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.
Identification of protein coding regions in the human genome by quadratic discriminant analysis
Michael Q Zhang · 1997
Earlier work this paper cites.
No eigenvalues outside the support of the limiting spectral distribution of large-dimensional sample covariance matrices
Zhi-Dong Bai and Jack W Silverstein · 1998
Earlier work this paper cites.
Molecular classification of cancer: class discovery and class prediction by gene expression monitoring
Todd R Golub, Donna K Slonim, Pablo Tamayo, Christine Huard, Michelle Gaasenbeek, Jill P Mesirov, Hilary Coller, Mignon L Loh, James R Downing, Mark A Caligiuri, et al · 1999
Earlier work this paper cites.
Some theory for fisher’s linear discriminant function,naive bayes’, and some alternatives when there are many more variables than observations
Peter J Bickel, Elizaveta Levina, et al · 2004
Earlier work this paper cites.
A well-conditioned estimator for large-dimensional covariance matrices
Olivier Ledoit and Michael Wolf · 2004
Earlier work this paper cites.
Stable signal recovery from incomplete and inaccurate measurements
Emmanuel J Candes, Justin K Romberg, and Terence Tao · 2006
Earlier work this paper cites.
High dimensional statistical inference and random matrices
Iain M Johnstone · 2006
Earlier work this paper cites.
On early stopping in gradient descent learning
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto · 2007
Earlier work this paper cites.
Clt for linear spectral statistics of large-dimensional sample covariance matrices
Zhidong D Bai and Jack W Silverstein · 2008
Earlier work this paper cites.
Covariance regularization by thresholding
Peter J Bickel, Elizaveta Levina, et al · 2008
Earlier work this paper cites.
High dimensional classification using features annealed independence rules
Jianqing Fan and Yingying Fan · 2008
Earlier work this paper cites.

Similar

Nonparametric estimate of spectral density functions of sample covariance matrices: A first step
Bing-Yi Jing, Guangming Pan, Qi-Man Shao, Wang Zhou, et al · 2010
Cited alongside, same era.
The lasso risk for gaussian matrices
Mohsen Bayati and Andrea Montanari · 2011
Cited alongside, same era.
Eigenvectors of some large sample covariance matrix ensembles
Olivier Ledoit and Sandrine Péché · 2011
Cited alongside, same era.
Practical recommendations for gradient-based training of deep architectures
Yoshua Bengio · 2012
Cited alongside, same era.
Nonlinear shrinkage estimation of large-dimensional covariance matrices
Olivier Ledoit and Michael Wolf · 2012
Cited alongside, same era.
Hanson-wright inequality and sub-gaussian concentration
Mark Rudelson, Roman Vershynin, et al · 2013
Cited alongside, same era.
Minimax risk of matrix denoising by singular value thresholding
David Donoho, Matan Gavish, et al · 2014
Cited alongside, same era.
The optimal hard threshold for singular values is 4 3 \frac{4}{\sqrt{3}}
Matan Gavish and David L Donoho · 2014
Cited alongside, same era.
Random matrix theory in statistics: A review
Debashis Paul and Alexander Aue · 2014
Cited alongside, same era.
Early stopping and non-parametric regression: an optimal data-dependent stopping rule
Garvesh Raskutti, Martin J Wainwright, and Bin Yu · 2014
Cited alongside, same era.
A differential equation for modeling nesterov’s accelerated gradient method: Theory and insights
Weijie Su, Stephen Boyd, and Emmanuel Candes · 2014
Cited alongside, same era.
Efficient computation of limit spectra of sample covariance matrices
Edgar Dobriban · 2015
Cited alongside, same era.

Then

High dimensional robust m-estimation: Asymptotic variance via approximate message passing
David Donoho and Andrea Montanari · 2016
Later among the works it cites.
Nonparametric eigenvalue-regularized precision or covariance matrix estimator
Clifford Lam et al · 2016
Later among the works it cites.
High-dimensional dynamics of generalization error in neural networks
Original
Madhu S Advani and Andrew M Saxe · 2017
Later among the works it cites.
A dynamical approach to random matrix theory , volume 28
László Erdős and Horng-Tzer Yau · 2017
Later among the works it cites.
Eigenprism: inference for high dimensional signal-to-noise ratios
Lucas Janson, Rina Foygel Barber, and Emmanuel Candes · 2017
Later among the works it cites.
Direct nonlinear shrinkage estimation of large-dimensional covariance matrices
Olivier Ledoit and Michael Wolf · 2017
Later among the works it cites.
A continuous-time view of early stopping for least squares
Original
Alnur Ali, J Zico Kolter, and Ryan J Tibshirani · 2018
Later among the works it cites.
The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression
Original
Emmanuel J Candès and Pragya Sur · 2018
Later among the works it cites.
High-dimensional asymptotics of prediction: Ridge regression and classification
Edgar Dobriban and Stefan Wager · 2018
Later among the works it cites.
Optimal shrinkage of eigenvalues in the spiked covariance model
David L Donoho, Matan Gavish, and Iain M Johnstone · 2018
Later among the works it cites.
Surprises in high-dimensional ridgeless least squares interpolation
Original
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani · 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.
A modern maximum-likelihood theory for high-dimensional logistic regression
Pragya Sur and Emmanuel J Candès · 2019
Later among the works it cites.
The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled chi-square
Pragya Sur, Yuxin Chen, and Emmanuel J Candès · 2019
Later among the works it cites.
Sharp asymptotics and optimal performance for inference in binary models
Original
Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis · 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…