Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions

Abstract

Empirical Risk Minimization (ERM) algorithms are widely used in a variety of estimation and prediction tasks in signal-processing and machine learning applications. Despite their popularity, a theory that explains their statistical properties in modern regimes where both the number of measurements and the number of unknown parameters is large is only recently emerging. In this paper, we characterize for the first time the fundamental limits on the statistical accuracy of convex ERM for inference in high-dimensional generalized linear models. For a stylized setting with Gaussian features and problem dimensions that grow large at a proportional rate, we start with sharp performance characterizations and then derive tight lower bounds on the estimation and prediction error that hold over a wide class of loss functions and for any value of the regularization parameter. Our precise analysis has several attributes. First, it leads to a recipe for optimally tuning the loss function and the regularization parameter. Second, it allows to precisely quantify the sub-optimality of popular heuristic choices: for instance, we show that optimally-tuned least-squares is (perhaps surprisingly) approximately optimal for standard logistic data, but the sub-optimality gap grows drastically as the signal strength increases. Third, we use the bounds to precisely assess the merits of ridge-regularization as a function of the over-parameterization ratio. Notably, our bounds are expressed in terms of the Fisher Information of random variables that are simple functions of the data distribution, thus making ties to corresponding bounds in classical statistics.

References in corpus (8)

• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• A framework to characterize performance of LASSO algorithms
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• The generalized Lasso with non-linear observations
• Variance Breakdown of Huber (M)-estimators: $n/p\to m\in (1,\infty )$

Cited by in corpus (5)

• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Don't Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification
• Label-Imbalanced and Group-Sensitive Classification under Overparameterization
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• Asymptotic Behavior of Adversarial Training in Binary Classification