Research map / Optimization / Implicit bias and generalization
Improved Scaling Laws in Linear Regression via Data Reuse
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 via sketched linear regression theory that multi-pass SGD with geometric stepsize decay achieves test error Θ(M^{1-b}+T^{(1-b)/a}) for T≲N^{a/b} steps, improving on one-pass scaling when data is reused.
Problem
Existing provable neural scaling laws for linear regression cover only one-pass SGD, which is unsustainable when fresh data runs out; it is unclear how data reuse via multi-pass SGD affects test-error scaling in model size M and sample size N.
Approach
Derives sharp finite-sample test error bounds for the last iterate of multi-pass SGD on M-dimensional Gaussian-sketched linear models with power-law data and prior spectra, decomposing risk into approximation, bias, variance and a new fluctuation error term from random sampling, showing that reused data scales better than one-pass SGD when the step count exceeds N.
Key results
- Multi-pass SGD achieves test error Θ(M^{1-b}+T^{(1-b)/a}) for T≲N^{a/b} steps, versus Θ(M^{1-b}+N^{(1-b)/a}) for one-pass SGD.
- With optimal step count T≈N^{a/b}, multi-pass SGD gives excess error Θ̃(N^{(1-b)/b}) in the data-constrained regime N≪M^b, improving on one-pass Θ̃(N^{(1-b)/a}) when a>b.
- Simulations with d=10000, (a,b)=(2,1.5), M=1000 give fitted exponents close to theory (-0.33 for multi-pass vs -0.25 for one-pass).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reuse the training data for multiple passes, with optimal effective steps stepeff ≃ N^{a/b} | Multi-pass SGD on an M-dimensional sketched linear model · Data-constrained linear regression (N ≪ M^b; a > b > 1) | excess test error rate: Θ(N^{(1-b)/a}) -> Θ(N^{(1-b)/b}) | Helped |
| Use multiple passes rather than one pass when a < b < a+1 | SGD on an M-dimensional sketched linear model · Data-constrained linear regression (a < b < a+1) | excess test error rate | No clear effect |
| Use constant-stepsize SGD with iterate averaging instead of geometrically decaying stepsizes | Multi-pass SGD · Linear regression simulations | excess test error scaling | No clear effect |
| Use multi-pass SGD with sequential sample reuse without replacement in each epoch | Multi-pass SGD · Non-Gaussian-design simulation | fitted exponent: 0.26 -> 0.34 | Helped |
Surprising findings
- Multi-pass SGD with sampling with replacement matches one-pass SGD on fresh data for the number of passes below roughly N^{a/b-1}, i.e. reused data behaves like fresh data for a range of epochs.
Limitations
- Requires aligned eigenspaces of data and prior covariance; relaxing this changes the rates.
- Lower bounds on fluctuation error and the stated lower bounds rely on Gaussian design.
- Analysis uses batch size one and a specific geometric stepsize schedule, with extra log factors and technical stepsize conditions.
Experimental setup
Datasets: synthetic Gaussian linear regression data synthetic non-Gaussian (Rademacher-type) design for robustness check
Metrics: excess test error fitted log-log scaling exponents
Baselines: one-pass SGD gradient descent
Builds on: one-pass SGD scaling laws in linear regression (Lin et al.) Gaussian random sketching neural scaling laws (Kaplan et al.) Muennighoff et al. data-constrained scaling
Closest papers by meaning
- Scaling Laws in Linear Regression: Compute, Parameters, and Data (NeurIPS 2024 · similarity 0.92)
- Learning with Synthetic Data via SGD in High-Dimensional Linear Regression (NeurIPS 2026 · similarity 0.88)
- On the Invariance and Generality of Neural Scaling Laws (NeurIPS 2026 · similarity 0.87)
- A Dynamical Model of Neural Scaling Laws (ICML 2024 · similarity 0.86)
- Scaling Laws for Optimal Data Mixtures (NeurIPS 2025 · similarity 0.86)
- Analyzing Neural Scaling Laws in Two-Layer Networks with Power-Law Data Spectra (ICLR 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.