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

Hossein Taheri, Ramtin Pedarsani, Christos Thrampoulidis

Abstract

Empirical Risk Minimization (ERM) algorithms are foundational to estimation and prediction tasks in signal processing and machine learning. However, a comprehensive theory explaining their statistical properties in modern high-dimensional regimes—where the number of measurements ($m$) and parameters ($n$) are of the same order—has only recently begun to emerge. This paper characterizes the fundamental limits on the statistical accuracy of convex ridge-regularized ERM (RERM) for inference in high-dimensional generalized linear models (GLMs). By analyzing a stylized setting with Gaussian features where dimensions grow proportionally, the authors derive tight lower bounds on estimation and prediction error. These bounds hold across a wide class of loss functions and regularization parameters, providing a recipe for optimal tuning and a means to quantify the sub-optimality of popular heuristic choices.

Introduction

In classical statistics, the prevailing assumption is that the number of observations significantly exceeds the number of parameters ($m \gg n$). Modern machine learning, however, frequently operates in regimes where $m$ and $n$ are comparable, or even where the model is over-parameterized ($n > m$). While Empirical Risk Minimization (ERM) is the standard approach for these tasks, the theoretical "floor" of its performance—specifically when using ridge regularization—has remained elusive.

This research addresses this gap by determining the absolute best performance achievable by any convex ridge-regularized estimator. By moving beyond the analysis of specific algorithms, the authors establish the fundamental limits of the entire class of convex RERM, offering a framework to design mathematically optimal loss functions and regularization parameters for any given data distribution.

Methodology: The CGMT Framework

The study focuses on Generalized Linear Models (GLMs), encompassing both linear regression with additive noise and binary classification models (e.g., logistic or probit). To derive the fundamental limits, the authors utilize the Convex Gaussian min-max Theorem (CGMT). This mathematical framework allows for the reduction of complex, high-dimensional optimization problems into a simpler system of a few nonlinear scalar equations.

By identifying a specific algebraic structure within these equations, the researchers established lower bounds that remain valid for any choice of convex loss function. This insight led to the derivation of an "optimal" loss function ($L_*$), tailored to the Fisher Information of the data distribution. This connection creates a significant bridge between modern high-dimensional theory and classical statistical principles.

Key Insights and Theoretical Results

The Fisher Information Connection

The fundamental limits derived in this paper are expressed in terms of the Fisher Information of random variables derived from the data distribution. This suggests that even in high-dimensional, non-classical regimes, the intrinsic "information" available in the data remains the primary determinant of achievable accuracy.

Optimal Tuning and the Sub-optimality of Least Squares

The paper provides a precise "recipe" for tuning the loss function and the regularization parameter $\lambda$. A notable finding is the performance of optimally-tuned Ridge Least Squares (RLS):

  • Weak Signal Regime: For standard logistic data with a low signal-to-noise ratio, RLS is surprisingly close to the theoretical optimum.
  • High Signal Regime: As signal strength increases, the sub-optimality gap of RLS grows significantly. For instance, with high signal strength in logistic data, the gap can reach a factor of 2.44, suggesting that using the derived optimal loss function $L_*$ provides substantial performance gains.

Over-parameterization

In highly over-parameterized settings ($n > m$), the choice of noise distribution becomes less critical. In these instances, RLS tends toward optimality regardless of the specific noise type, simplifying the practitioner's choice in extremely high-dimensional spaces.

Empirical Validation

To validate the theoretical derivations, the authors conducted Monte-Carlo simulations using stylized synthetic models:

  • Linear Models: Gaussian features with additive Laplacian noise.
  • Binary Models: Logistic, Probit, and "Signed" data models.

Despite the proofs being asymptotic (assuming $n \to \infty$), the experimental results with $n=100$ features perfectly matched the theoretical predictions. This suggests that the derived bounds are highly relevant even for finite, relatively small-scale problems.

Limitations and Future Work

While the paper provides a landmark characterization of RERM limits, it acknowledges certain constraints:

  1. Gaussian Features: The theory currently assumes independent and identically distributed (i.i.d.) Gaussian feature vectors. Real-world data often contains complex correlations not yet captured by this model.
  2. Convexity: The bounds apply specifically to convex ERM. While this covers Logistic Regression, SVMs, and Lasso, it does not necessarily extend to non-convex models like deep neural networks.

Future research directions include extending the analysis to arbitrary link functions and investigating the impact of correlated features on the fundamental limits of ERM.

Summary updated

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.
BibTeX
@inproceedings{taheri2021fundamental,
  author = {Hossein Taheri and Ramtin Pedarsani and Christos Thrampoulidis},
  title = {{Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=kWtQDd9gFio},
}
Figure