Research map / Learning theory and algorithms / Kernels and regression theory
No Free Lunch from Random Feature Ensembles: Scaling Laws and Near-Optimality Conditions
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.
Shows theoretically that, at fixed total random-feature budget, ridge-optimized RFRR ensembles never beat a single model, and characterizes when ensembles can nearly match it via deterministic-equivalent risk and growth-exponent scaling laws.
Problem
Whether, under a fixed total parameter budget, an ensemble of smaller random-feature ridge regression models can match a single large model in test risk.
Approach
Uses deterministic-equivalent risk estimates for RFRR ensembles to prove a no-free-lunch theorem (ridge-optimized risk increases with ensemble size at fixed total features), shows overparameterized ensembles depend only on total feature count M=KN, and derives scaling laws under a growth exponent ell for joint scaling of K and N.
Key results
- Theorem: ridge-optimized test risk of RFRR ensembles is nondecreasing in K at fixed total features M=KN, so a single large model is optimal.
- Overparameterized ensembles: to leading order in lambda and 1/N, risk depends only on total feature count KN.
- Scaling exponent s = min(2 alpha ell min(r,1), 1-ell + 2 alpha ell min(r,1/2)); for CIFAR-10 alpha~1.33, r~0.038 and MNIST alpha~1.46, r~0.14 (difficult regime r<1/2, bias-dominated).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase ensemble size K while keeping total feature count M fixed | RFRR ensembles · Binarized CIFAR-10 | optimal test risk | Hurt |
| Allocate a fixed total feature count to one model instead of multiple models | RFRR ensembles · RFRR tasks | ridge-optimized test risk | Helped |
| Increase model size N with optimally tuned ridge | RFRR ensembles · RFRR tasks | test risk | Helped |
| Increase training sample size P with optimally tuned ridge | RFRR ensembles · RFRR tasks | test risk | Helped |
| Divide a fixed total feature count among overparameterized ensemble members | RFRR ensembles · Overparameterized regime | test risk: risk depends on K and N only through KN | No clear effect |
| Jointly increase ensemble size and model size with growth exponent ℓ | RFRR ensembles on difficult tasks · Underparameterized regime, r<1/2 | test-risk scaling exponent: s = min (2 α ℓ min(r, 1), 1−ℓ + 2 α ℓ min(r, 1/2)) | Mixed |
| Jointly scale ensemble size and model size with ℓ above the threshold | RFRR ensembles on easier tasks · Underparameterized regime, r>1/2 | test-risk scaling exponent: ℓ* = 1/(1+α(2r−1)) for 1/2<r<1; ℓ* = 1/(1+α) for r>1 | No clear effect |
Surprising findings
- For easy tasks (r>1/2), near-optimal scaling can be obtained by joint scaling of ensemble size and model size beyond a threshold ell*.
Limitations
- Assumes statistically homogeneous ensembles trained on the same data and task; no functional specialization or MoE analysis.
- Relies on Gaussian universality and deterministic-equivalent approximations valid asymptotically; dimension-free equivalence not proven for ensembles.
- Analysis restricted to random-feature ridge regression, not feature-learning deep networks.
Experimental setup
Datasets: CIFAR-10 (binarized) MNIST (binarized) synthetic power-law Gaussian data
Benchmarks: binarized CIFAR-10 MNIST
Metrics: test risk (MSE) 0-1 classification error scaling exponents
Baselines: single RFRR model with M features
Builds on: random-feature ridge regression deterministic equivalent risk estimates Gaussian universality
Closest papers by meaning
- Theoretical Limitations of Ensembles in the Age of Overparameterization (ICML 2025 · similarity 0.90)
- Dimension-free deterministic equivalents and scaling laws for random feature regression (NeurIPS 2024 · similarity 0.87)
- Sharpness-diversity tradeoff: improving flat ensembles with SharpBalance (NeurIPS 2024 · similarity 0.87)
- Asymptotically Free Sketched Ridge Ensembles: Risks, Cross-Validation, and Tuning (ICLR 2024 · similarity 0.87)
- Optimal Ridge Regularization for Out-of-Distribution Prediction (ICML 2024 · similarity 0.86)
- Structure-informed Risk Minimization for Robust Ensemble Learning (ICML 2025 · similarity 0.86)
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.