Research map / Learning theory and algorithms / Kernels and regression theory
Dimension-free deterministic equivalents and scaling laws for random feature regression
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives a non-asymptotic, dimension-free, multiplicative deterministic equivalent for the test error of random feature ridge regression and uses it to get sharp scaling laws and the minimal feature count achieving minimax rates.
Problem
Characterizing the generalization error of random feature ridge regression (RFRR) without asymptotic dimension scaling, including infinite-dimensional features, and determining the minimum number of features needed for optimal minimax excess risk under source and capacity conditions.
Approach
Under a concentration assumption on eigenfunctions, the test error of RFRR is shown to be multiplicatively close to a closed-form deterministic equivalent depending only on the feature-map eigenvalues, with error rates independent of feature dimension; this is applied to derive sharp power-law scaling regimes.
Key results
- Deterministic equivalent approximates RFRR test error with multiplicative error Õ(n^{-1/2}+p^{-1/2}), independent of feature dimension, with high probability.
- Optimal excess risk rate under source and capacity conditions is γ* = 2α(r∧1)/(2α(r∧1)+1), matching minimax ridge regression rates.
- Minimal feature count to achieve optimal rate is p* = n^{q*} with q* = 1 - α(2r∧1)/(2α(r∧1)+1), strictly smaller than previous upper bound p0 = n^{q0} for r in [1/2,1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of random features beyond the point needed for the fixed data budget | Random feature ridge regression · Fixed sample size n | excess risk | No clear effect |
| Use at least p_star random features with the stated optimal regularization | Random feature ridge regression · Power-law source and capacity conditions, r ≥ 1/2 | excess risk decay rate: γ_star = 2α (r∧1)/(2α (r∧1) + 1) | Helped |
| Use p_star = (λ_star^{-1} n)^{1/α} features with λ = λ_star, or use λ ≤ λ_star with p = p_star | Random feature ridge regression · Power-law source and capacity conditions, r < 1/2 | excess risk decay rate: γ_star = 2α (r∧1)/(2α (r∧1) + 1) | Helped |
Surprising findings
- The minimal number of features needed for optimal rates is strictly smaller than the previously known sufficient number of features for r in [1/2,1).
Limitations
- Concentration assumption on eigenfunctions is restrictive and excludes many nonlinear settings (e.g., uniform on sphere or hypercube).
- Technical conditions on lambda and spectrum; approximation rates may be suboptimal in some regimes.
- Scaling-law rates are established only within vanishing-approximation-error regions of (l,q).
Experimental setup
Datasets: real dataset (unspecified in excerpt) synthetic data (single-index target with spiked random features)
Metrics: test error (risk) excess risk scaling exponent
Baselines: Rudi and Rosasco random features analysis Bach random features bounds asymptotic RFRR formulas (Atanasov et al., Bach)
Builds on: deterministic equivalents for ridge regression kernel ridge regression dimension-free results source and capacity conditions
Closest papers by meaning
- Towards Theoretical Understanding of Learning Large-scale Dependent Data via Random Features (ICML 2024 · similarity 0.88)
- No Free Lunch from Random Feature Ensembles: Scaling Laws and Near-Optimality Conditions (ICML 2025 · similarity 0.87)
- High-Dimensional Analysis for Generalized Nonlinear Regression: From Asymptotics to Algorithm (AAAI 2024 · similarity 0.86)
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.86)
- On the Efficiency of ERM in Feature Learning (NeurIPS 2024 · similarity 0.85)
- Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterization (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.