Introduction
In modern machine learning, understanding model behavior in the overparameterized regime—where the number of parameters exceeds the number of data points—is a central challenge. Researchers often analyze this through asymptotic learning curves, which predict training and test errors as the dataset size ($n$) and parameter count ($m$) grow to infinity at a fixed ratio $\gamma = m/n$. While these curves are well-understood for simple linear models with independent data, Random Feature (RF) models are significantly more complex due to the correlations introduced by nonlinear transformations. This paper provides a precise, computable framework for these curves under general convex regularization, including $\ell_1$ (LASSO) and Elastic Net.
Methodology: Multi-level CGMT
The primary technical innovation is a "multi-level" application of the Convex Gaussian Min-Max Theorem (CGMT). While standard CGMT is a powerful tool for average-case analysis, it typically fails when data is correlated. The authors overcome this by applying CGMT twice: first to handle the randomness of the input data, and second to handle the randomness of the weight matrix ($W$) used in the feature mapping.
This approach reduces a complex, high-dimensional optimization problem into a simple 4-dimensional scalar optimization. Unlike previous methods that required solving intractable proximal operators, this 4D problem is easily computable. Furthermore, the authors extend Gaussian universality results, proving that RF models with non-differentiable regularizers like $\ell_1$ behave asymptotically like simpler "surrogate" Gaussian models.
Key Insights
- Smoothing Double Descent: The framework provides a fine-grained look at the "double descent" phenomenon. It quantifies exactly how increasing regularization strength ($\alpha$) suppresses the sharp spike in generalization error typically observed at the interpolation threshold ($\gamma \approx 1$).
- Effective Sparsity: For models using $\ell_1$ regularization, the authors derived a formula to predict "effective sparsity"—the exact proportion of weights that will be zeroed out. This has significant implications for model compression and sub-network selection.
- Hyperparameter Tuning: By providing precise curves, the framework allows practitioners to identify the optimal regularization strength for any given ratio of parameters to data.
Results and Validation
The theoretical predictions were validated using synthetic datasets with Gaussian inputs and labels generated via a noisy "teacher" model. The results demonstrate that the theoretical "limit" is a highly accurate predictor even for finite-sized models (e.g., $n+m = 1000$).
As shown in the figures above, the theoretical curves (solid lines) match the experimental markers almost perfectly. The generalization error plot (bottom) clearly illustrates how increasing $\alpha$ smooths the performance peak at the interpolation boundary.
Conclusion and Future Work
This work establishes a robust mathematical foundation for predicting the performance of Random Feature models with a wide array of regularization techniques. While the current analysis is restricted to square-loss functions and separable regularization, it provides a methodology that can be extended to more complex loss functions (like cross-entropy) and deeper architectures in future research.
Summary updated