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.
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."
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