Dimension-free deterministic equivalents for random feature regression

Leonardo Defilippis, Bruno Loureiro, Theodor Misiakiewicz

Abstract

This paper provides a rigorous, non-asymptotic framework for predicting the test error of random feature ridge regression (RFRR) that is independent of the input data dimension. By deriving "deterministic equivalents"—closed-form approximations of the error—the authors establish sharp scaling laws that determine exactly how many random features are needed to achieve optimal learning rates for a given number of training samples.

Introduction

In modern machine learning, models often employ far more parameters than training samples, a state known as overparameterization, yet they generalize remarkably well. Random Feature (RF) models serve as a popular "sandbox" for studying this phenomenon. However, most existing mathematical theories for RF models rely on asymptotic limits, assuming the number of samples ($n$), features ($p$), and input dimension ($d$) all grow to infinity at fixed ratios.

In practice, these ratios are rarely fixed, and the input dimension may be effectively infinite. This research addresses the need for a dimension-free and non-asymptotic theory applicable to real-world datasets where $d$ varies. The proposed framework provides a clear picture of how error scales with $n$ and $p$ without relying on specific dimensional ratios.

Methods

The authors utilize tools from random matrix theory and concentration of measure to derive their results:

  • Deterministic Equivalents: They prove that the test error of RFRR is well-approximated by a deterministic expression involving "self-consistent equations." These equations depend only on the eigenvalues of the feature map's kernel, rather than the raw input dimension.
  • Non-Asymptotic Analysis: Unlike previous work, the approximation guarantee includes explicit error bounds that vanish as $n$ and $p$ grow, providing a multiplicative guarantee that holds for finite sample sizes.
  • Source and Capacity Conditions: To derive scaling laws, the kernel's eigenvalues and the target function's coefficients are assumed to decay according to power laws (characterized by exponents $\alpha$ and $r$).
  • Fixed-Point Equations: Parameters $\nu_1$ and $\nu_2$ are defined through coupled equations acting as "effective regularizers," capturing the interplay between finite features and finite samples.

Results

The theoretical formulas were validated using both synthetic "teacher-student" models and real-world benchmarks like MNIST and FashionMNIST. The analysis reveals a critical threshold for $p$:

  1. Resolution Limited Regime: With too few features, performance is limited by the model's approximation power.
  2. Variance Limited Regime: Once $p \ge p_*$, the bottleneck becomes the amount of training data.
Excess risk $\mathcal{R}$ as a function of the number of features $p$ for various regularization strengths $\lambda$. Solid lines represent the theoretical deterministic equivalents, while points represent empirical results.

The paper proves an approximation guarantee where $|R_{test} - R_{deterministic}| \le \tilde{O}(p^{-1/2} + n^{-1/2}) \cdot R_{deterministic}$. As shown in the figure above, numerical simulations show an almost perfect match between the theoretical "solid lines" and empirical data points. The framework also derives explicit exponents for bias and variance decay; for instance, the optimal excess risk rate scales as $n^{-\frac{2\alpha r}{2\alpha r + 1}}$.

Discussion and Limitations

The most significant insight is that generalization error depends on the "spectral content" (eigenvalues) of the features rather than the input dimension $d$ directly. This allows the theory to apply to infinite-dimensional feature spaces.

However, some limitations remain. The proof relies on concentration assumptions for eigenfunctions which might be restrictive for certain highly non-linear or heavy-tailed feature maps. Additionally, extending the theory to the "ridgeless" limit ($\lambda \to 0$) for all regimes remains a technical challenge. While RFRR is a proxy for the "lazy" regime of neural networks, extending these dimension-free equivalents to fully trained, deep non-linear networks is the next major frontier.

Summary updated

BibTeX
@inproceedings{defilippis2024dimension,
  author = {Leonardo Defilippis and Bruno Loureiro and Theodor Misiakiewicz},
  title = {{Dimension-free deterministic equivalents for random feature regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=FBLJIfW64D},
}
Figure