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

Hossein Taheri, Ramtin Pedarsani, Christos Thrampoulidis

Abstract

This paper establishes the first fundamental limits for ridge-regularized Empirical Risk Minimization (ERM) in high-dimensional settings where the number of features and observations are of the same order. By employing the Convex Gaussian Min-Max Theorem (CGMT), the authors provide a precise recipe for choosing the mathematically optimal loss function and regularization parameter. They prove that the best possible performance is tied directly to the Fisher Information of the data's noise distribution, bridging the gap between classical statistical theory and modern high-dimensional inference.

Introduction

In classical statistics, the regime where the number of observations ($m$) far exceeds the number of variables ($n$) is well-understood, with the Cramér-Rao bound providing a clear benchmark for estimator performance. However, modern datasets often reside in the high-dimensional regime where $m$ and $n$ are comparable ($m/n \approx \delta$). In this setting, standard intuitions fail. While researchers have recently developed tools to analyze specific algorithms like Logistic Regression or Least Squares in high dimensions, they haven't been able to define the "best possible" convex algorithm. This paper fills that gap by finding the lower bounds of error for a wide class of Generalized Linear Models (GLMs) and showing how to tune algorithms to reach those bounds.

Theoretical Framework and Optimal Estimators

The authors utilize the Convex Gaussian Min-Max Theorem (CGMT) to reduce complex high-dimensional optimization problems into simpler scalar optimizations. This framework allows for the optimization of the entire shape of the loss function $L$, rather than just a single scalar parameter like the regularization strength $\lambda$.

A key finding is that the optimal loss function for high-dimensional ERM is a "smoothed" version of the log-likelihood, specifically the Moreau envelope of the noise distribution's density. This result reinforces the central role of Fisher Information: even in high dimensions, it remains the core metric defining the limits of inference. The authors derived closed-form bounds showing that as the noise distribution becomes "less Gaussian," the potential gains from using the optimal loss function increase.

Theoretical error curves (estimation and classification error) vs. sampling ratio $\delta$ for various loss functions, validated by Gaussian and Rademacher simulations.

Empirical Validation and Universality

The theoretical predictions were validated using synthetic datasets with various noise distributions (e.g., Laplacian) and link functions (e.g., Signed, Logistic). As shown in Figure 1, the theoretical curves for estimation and classification error align closely with numerical simulations. Notably, the theory holds not only for Gaussian features but also for Rademacher features, demonstrating a property known as "universality."

Comparison of theoretical predictions and experimental results for different noise distributions and link functions across various sampling ratios.

The research also quantifies the sub-optimality of standard Ridge Least Squares (RLS). While RLS performs well for low-signal logistic data, it becomes significantly less efficient than the optimally tuned ERM as signal strength increases. For Laplacian noise, the authors proved that optimally-tuned RLS is at most twice as bad as the absolute optimal estimator, regardless of the sampling ratio.

Conclusion and Future Work

This work provides a constructive method for calculating the best loss function and regularization for high-dimensional data. While the current formal proofs require Gaussian feature vectors, empirical evidence suggests these limits apply more broadly. Future work may extend these results to non-convex estimators and more complex, correlated feature structures, which would require a more complex system of equations to describe.

Summary updated

Abstract

Despite the popularity of Empirical Risk Minimization (ERM) algorithms, a theory that explains their statistical properties in modern high-dimensional regimes is only recently emerging. We characterize for the first time the fundamental limits on the statistical accuracy of convex ridge-regularized 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. Our bounds provably hold over a wide class of loss functions, and, for any value of the regularization parameter and of the sampling ratio. 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, such as optimally-tuned least-squares. Third, we use the bounds to precisely assess the merits of ridge-regularization as a function of the sampling ratio. 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