Random Features Model with General Convex Regularization: A Fine Grained Analysis with Precise Asymptotic Learning Curves

David Bosch, Ashkan Panahi, Ayça Özçelikkale, Devdatt P. Dubhashi

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$).

Asymptotic learning curves for training and generalization error. The solid lines represent the theoretical predictions, while markers show experimental results across different regularization strengths $\alpha$.

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

Abstract

We compute precise asymptotic expressions for the learning curves of least squares random feature (RF) models with either a separable strongly convex regularization or the $\ell_1$ regularization. We propose a novel multi-level application of the convex Gaussian min max theorem (CGMT) to overcome the traditional difficulty of finding computable expressions for random features models with correlated data. Our result takes the form of a computable 4-dimensional scalar optimization. In contrast to previous results, our approach does not require solving an often intractable proximal operator, which scales with the number of model parameters. Furthermore, we extend the universality results for the training and generalization errors for RF models to $\ell_1$ regularization. In particular, we demonstrate that under mild conditions, random feature models with elastic net or $\ell_1$ regularization are asymptotically equivalent to a surrogate Gaussian model with the same first and second moments. We numerically demonstrate the predictive capacity of our results, and show experimentally that the predicted test error is accurate even in the non-asymptotic regime.
BibTeX
@inproceedings{bosch2023random,
  author = {David Bosch and Ashkan Panahi and Ayça Özçelikkale and Devdatt P. Dubhashi},
  title = {{Random Features Model with General Convex Regularization: A Fine Grained Analysis with Precise Asymptotic Learning Curves}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=PR1KVNwWlM},
}
Figure