Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results

Abstract

We study the behavior of high-dimensional robust regression estimators in the asymptotic regime where $p/n$ tends to a finite non-zero limit. More specifically, we study ridge-regularized estimators, i.e $\hat{\beta }={\text{argmin}}_{\beta \in {\mathbb{R}}^p}\frac{1}{n}{\sum }_{i=1}^n\rho ({\epsilon }_i-X_i^{\prime }\beta )+\frac{\tau }{2}\Vert \beta {\Vert }^2$. In a recently published paper, we had developed with collaborators probabilistic heuristics to understand the asymptotic behavior of $\hat{\beta }$. We give here a rigorous proof, properly justifying all the arguments we had given in that paper. Our proof is based on the probabilistic heuristics we had developed, and hence ideas from random matrix theory, measure concentration and convex analysis. While most the work is done for $\tau >0$, we show that under some extra assumptions on $\rho$, it is possible to recover the case $\tau =0$ as a limiting case. We require that the $X_i$'s be i.i.d with independent entries, but our proof handles the case where these entries are not Gaussian. A 2-week old paper of Donoho and Montanari [arXiv:1310.7320] studied a similar problem by a different method and with a different point of view. At this point, their interesting approach requires Gaussianity of the design matrix.

References in corpus (1)

• High Dimensional Robust M-Estimation: Asymptotic Variance via Approximate Message Passing

Cited by in corpus (31)

• A modern maximum-likelihood theory for high-dimensional logistic regression
• The distribution of the Lasso: Uniform control over sparse balls and adaptive parameter tuning
• Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
• A scalable estimate of the extra-sample prediction error via approximate leave-one-out
• On the Optimal Weighted ${\ell }_2$ Regularization in Overparameterized Linear Regression
• Don't Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions
• Leave-one-out prediction intervals in linear regression models with many variables
• Precise Error Analysis of Regularized M-estimators in High-dimensions
• Variance Breakdown of Huber (M)-estimators: $n/p\to m\in (1,\infty )$
• An Assumption-Free Exact Test For Fixed-Design Linear Models With Exchangeable Errors
• Robustness in sparse linear models: relative efficiency based on robust approximate message passing
• Can we trust the bootstrap in high-dimension?
• When Does Preconditioning Help or Hurt Generalization?
• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques
• Sharp Asymptotics and Optimal Performance for Inference in Binary Models
• Cross-trait prediction accuracy of high-dimensional ridge-type estimators in genome-wide association studies
• Out-of-sample error estimate for robust M-estimators with convex penalty
• CAD: Debiasing the Lasso with inaccurate covariate model
• Asymptotic Behavior of Adversarial Training in Binary Classification
• Second order statistics of robust estimators of scatter. Application to GLRT detection for elliptical signals
• Optimum GSSK Transmission in Massive MIMO Systems Using the Box-LASSO Decoder
• Exact high-dimensional asymptotics for Support Vector Machine
• Quadratic Discriminant Analysis under Moderate Dimension
• Minimum ${\ell }_1$-norm interpolators: Precise asymptotics and multiple descent
• Moderate-Dimensional Inferences on Quadratic Functionals in Ordinary Least Squares
• Understanding the Under-Coverage Bias in Uncertainty Estimation
• Asymptotic normality of robust $M$-estimators with convex penalty
• Low noise sensitivity analysis of Lq-minimization in oversampled systems
• Asymptotics For High Dimensional Regression M-Estimates: Fixed Design Results