Asymptotic errors for convex penalized linear regression beyond Gaussian matrices

Abstract

We consider the problem of learning a coefficient vector $x_0$ in $R^N$ from noisy linear observations $y=F{x}_0+w$ in $R^M$ in the high dimensional limit $M,N$ to infinity with $\alpha =M/N$ fixed. We provide a rigorous derivation of an explicit formula -- first conjectured using heuristic methods from statistical physics -- for the asymptotic mean squared error obtained by penalized convex regression estimators such as the LASSO or the elastic net, for a class of very generic random matrices corresponding to rotationally invariant data matrices with arbitrary spectrum. The proof is based on a convergence analysis of an oracle version of vector approximate message-passing (oracle-VAMP) and on the properties of its state evolution equations. Our method leverages on and highlights the link between vector approximate message-passing, Douglas-Rachford splitting and proximal descent algorithms, extending previous results obtained with i.i.d. matrices for a large class of problems. We illustrate our results on some concrete examples and show that even though they are asymptotic, our predictions agree remarkably well with numerics even for very moderate sizes.

31 pages, 2 figures

References in corpus (13)

• Scikit-learn: Machine Learning in Python
• Reconciling modern machine learning practice and the bias-variance trade-off
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Statistical physics of inference: Thresholds and algorithms
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Statistical Mechanics of Support Vector Networks
• Mean-Field Equations for Spin Models with Orthogonal Interaction Matrices
• The Mutual Information in Random Linear Estimation
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• Plug-in Estimation in High-Dimensional Linear Inverse Problems: A Rigorous Analysis
• Understanding overfitting peaks in generalization error: Analytical risk curves for $l_2$ and $l_1$ penalized interpolation
• Approximate message-passing for convex optimization with non-separable penalties

Cited by in corpus (9)

• Asymptotics of Ridge (less) Regression under General Source Condition
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• Provable More Data Hurt in High Dimensional Least Squares Estimator
• Exact results on high-dimensional linear regression via statistical physics
• Out-of-sample error estimate for robust M-estimators with convex penalty
• Generalization Error of Generalized Linear Models in High Dimensions
• Implicit Bias of Linear RNNs
• Ising Model Selection Using ${\ell }_1$-Regularized Linear Regression: A Statistical Mechanics Analysis
• Replica analysis of overfitting in generalized linear models