Research map / Optimization / Implicit bias and generalization
Scaling Laws in Linear Regression: Compute, Parameters, and Data
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 in an infinite-dimensional sketched linear regression trained by one-pass SGD with geometric stepsize decay that the reducible test risk scales as M^{-(a-1)} + N^{-(a-1)/a}, with the variance error hidden by implicit SGD regularization, matching neural scaling laws.
Problem
Neural scaling laws show test error improving polynomially in model size M and data size N, yet classical bias-variance theory predicts variance error grows with model size, conflicting with the empirical law.
Approach
Model M-parameter predictors as linear functions of Gaussian-sketched covariates trained by one-pass SGD with geometrically decaying stepsizes; under a power-law covariance spectrum and Gaussian/source priors, derive matching upper and lower bounds showing the variance error is of strictly higher order and vanishes from the risk bound due to implicit regularization of SGD.
Key results
- For a=1.5, d=20000, fitted exponents (0.54, 0.34) closely match predicted (0.5, 0.33) for M and N terms.
- For a=2, d=2000, fitted exponents (1.07, 0.49) match predicted (1.0, 0.5).
- Theory shows reducible risk Theta(M^{-(a-1)} + N^{-(a-1)/a}) and variance error min{M,(N gamma)^{1/a}}/N is of strictly higher order, so it does not appear in the bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase model size M under the power-law spectrum of degree a>1 | One-pass SGD on sketched linear regression with isotropic parameter prior · Power-law spectrum, degree a>1 | population risk above irreducible risk: M^{-(a-1)} | Helped |
| Increase data size N under the power-law spectrum of degree a>1 | One-pass SGD on sketched linear regression with isotropic parameter prior · Power-law spectrum, degree a>1 | population risk above irreducible risk: N^{-(a-1)/a} | Helped |
| Use one-pass SGD, whose implicit regularization suppresses variance | Sketched linear regression · Power-law spectrum, degree a>1 | variance error: \tilde\Theta(\min\{M, (N\gamma)^{1/a}\}/N) | Helped |
| Use one-pass SGD with geometric decay and increase model size | Sketched linear regression, a=1.5 (d=20000) · Synthetic linear regression | model-size risk-decay exponent: 0.54; predicted 0.5 | Helped |
| Use one-pass SGD with geometric decay and increase data size | Sketched linear regression, a=1.5 (d=20000) · Synthetic linear regression | data-size risk-decay exponent: 0.34; predicted 0.33 | Helped |
| Use one-pass SGD with geometric decay and increase model size | Sketched linear regression, a=2 (d=2000) · Synthetic linear regression | model-size risk-decay exponent: 1.07; predicted 1.0 | Helped |
| Use one-pass SGD with geometric decay and increase data size | Sketched linear regression, a=2 (d=2000) · Synthetic linear regression | data-size risk-decay exponent: 0.49; predicted 0.5 | Helped |
| Replace the isotropic prior with a source condition, 1<b<a+1 (ablation) | One-pass SGD on sketched linear regression · Power-law spectrum, source condition | population risk above irreducible risk: M^{1-b} + (N_eff γ)^{(1-b)/a} + min{M,(N_eff γ)^{1/a}}/N_eff | Mixed |
| Replace the power-law spectrum with a logarithmic power-law spectrum (ablation) | One-pass SGD on sketched linear regression · Logarithmic power-law spectrum | population risk above irreducible risk: 1/log^{a-1}(M) + 1/log^{a-1}(N_eff γ) | Helped |
| Use constant stepsize SGD with iterate averaging instead of last-iterate SGD with geometric decay (ablation) | Sketched linear regression · Power-law spectrum | population risk | No clear effect |
Surprising findings
- The variance error, which grows with model size M, is dominated by approximation and bias errors, so the risk decreases monotonically in M despite classical bias-variance intuition.
- Optimal stepsize is order 1 for most regimes, and the compute-optimal allocation is M ~ C^{1/(a+1)}, N ~ C^{a/(a+1)}.
Limitations
- Analysis restricted to linear models; extension to random features or two-layer networks left open.
- Relies on Gaussian design and Gaussian (or source-condition) priors on the optimal parameter.
- Only one-pass SGD with geometric stepsize decay analyzed; other optimizers such as Adam are not covered.
Experimental setup
Datasets: synthetic Gaussian linear regression data with power-law covariance
Benchmarks: synthetic sketched linear regression
Metrics: expected risk fitted power-law exponents
Baselines: Chinchilla scaling law Bahri et al. 2021 teacher-student scaling Maloney et al. 2022 random feature scaling Lin et al. ridge/SGD risk bounds
Builds on: Zou et al. 2021 SGD tail-averaging/last iterate analysis Bach & Moulines 2013 SGD analysis Paquette et al. teacher-student scaling Chinchilla scaling law
Closest papers by meaning
- Improved Scaling Laws in Linear Regression via Data Reuse (NeurIPS 2025 · similarity 0.92)
- A Dynamical Model of Neural Scaling Laws (ICML 2024 · similarity 0.92)
- Analyzing Neural Scaling Laws in Two-Layer Networks with Power-Law Data Spectra (ICLR 2025 · similarity 0.91)
- Asymmetric Scaling Laws from Sparse Features (NeurIPS 2026 · similarity 0.89)
- On the Invariance and Generality of Neural Scaling Laws (NeurIPS 2026 · similarity 0.89)
- Emergence and scaling laws in SGD learning of shallow neural networks (NeurIPS 2025 · similarity 0.88)
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.