Research map / Optimization / Implicit bias and generalization
Emergence and scaling laws in SGD learning of shallow neural networks
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.
Analyzes online SGD with MSE on a 2-homogeneous two-layer student learning an extensive-width additive sum of high-information-exponent single-index neurons, proving polynomial sample complexity and deriving power-law scaling laws from superposed emergent learning curves.
Problem
Understanding the complexity of online SGD for learning wide two-layer networks with many orthogonal teacher neurons and large second-layer condition number, and how emergent sharp learning transitions superpose into neural scaling laws.
Approach
Trains both layers simultaneously under MSE with a 2-homogeneous student parameterization so that the automatic deflation removes learned tasks from the loss, giving polynomial complexity in condition number and width (vs. exponential in prior layer-wise analyses) and a power-law MSE scaling law from emergent learning times.
Key results
- Sharp transition time for teacher neuron p is T_p ~ 1/(eta a_p bar v^(2I-2)(0)); with m ~ P_* log P_* student neurons, online SGD recovers P_* teacher directions with n ~ T ~ a_{P_*}^2 d^(k-1) poly(P) samples.
- Under power-law a_p ~ p^(-beta), beta>1/2, the MSE scales as m^(1-2beta) approximation term plus (eta t d^(1-I))^((1-2beta)/beta) optimization term.
- Simulations with beta=0.8, d=2048, P=1024 show empirical GD loss slope roughly consistent with predicted compute-optimal L ~ T^((1-2beta)/(1+beta)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a 2-homogeneous student network and train both layers simultaneously with online SGD on MSE | Two-layer network learning an orthogonal additive teacher · Top P_* teacher directions | sample complexity: n \asymp a_{P_*}^2 \cdot d^{k_*-1} \mathrm{poly}(P) | Helped |
| Power-law second-layer coefficients a_p = p^{-\beta}/Z, with \beta>1/2 | Online SGD learning the additive teacher · Population MSE over training steps | MSE loss: \left(\frac{K_0\eta t}{d^{I-1}}\right)^\frac{1-2\beta}{\beta} | Helped |
| Increase student width m | Online SGD learning a power-law teacher · Population MSE | MSE loss: \left(\frac{m}{\log m}\right)^{1 - 2\beta} | Helped |
| Increase training steps t | Online SGD learning a power-law teacher · Population MSE | MSE loss: \left(\frac{K_0\eta t}{d^{I-1}}\right)^\frac{1-2\beta}{\beta} | Helped |
| Choose learning rate depending on the fixed training budget n and width m | Online SGD learning a power-law teacher · Unstable scaling law | MSE loss: \tilde \Theta\left( m^{1 - 2\beta} + \left(\frac{n}{d^{2I-1}\poly(P)}\right)^{\frac{1 - 2\beta}{2\beta}}\right) | Helped |
| Superpose the learning curves of many teacher directions with different signal strengths | Online SGD learning an extensive-width additive teacher · Cumulative population MSE | MSE loss: \mathcal{L}(t) \sim \left(t\eta d^{1-k_*/2}\right)^{\frac{1-2\beta}{\beta}} \vee m^{1-2\beta} | Helped |
| Use a compute-optimal width and training time under budget \mathcal{T}\asymp mt | Online SGD/GD power-law setting · Compute-optimal frontier | MSE loss: \mathcal{L}\sim \mathcal{T}^{\frac{1-2\beta}{1+\beta}} | Helped |
| Use a power-law teacher with \beta=0.8 | GD training on population loss · Figure simulation (d=2048, P=1024) | compute-optimal MSE loss scaling: \mathcal{L}\sim (mt)^{1/3} | Mixed |
Surprising findings
- Constant-size gradient-descent learning rates chosen 'unstably' (larger than needed for all teacher neurons) can still yield a scaling law in the sample count with matching exponent to minimax rates.
Limitations
- Requires high information exponent (IE > 2); does not cover IE=2 case.
- Assumes isotropic Gaussian input data with identity covariance and orthonormal teacher directions.
- Scaling law is an idealized result; finite-d simulations deviate slightly from the predicted exponent.
Experimental setup
Datasets: synthetic isotropic Gaussian inputs with teacher two-layer network targets
Metrics: population MSE loss recovery time of teacher neurons scaling law exponent
Baselines: layer-wise correlation-loss SGD analysis lazy/kernel regime (n ~ d^deg)
Builds on: single-index model SGD analysis (information exponent) layer-wise multi-index training analysis greedy maximum selection (tensor decomposition) Hermite expansion of MSE loss
Closest papers by meaning
- Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws (NeurIPS 2025 · similarity 0.91)
- Analyzing Neural Scaling Laws in Two-Layer Networks with Power-Law Data Spectra (ICLR 2025 · similarity 0.90)
- The Optimization Landscape of SGD Across the Feature Learning Strength (ICLR 2025 · similarity 0.90)
- From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD (NeurIPS 2025 · similarity 0.89)
- Online Learning and Information Exponents: The Importance of Batch size & Time/Complexity Tradeoffs (ICML 2024 · similarity 0.89)
- Scaling Laws in Linear Regression: Compute, Parameters, and Data (NeurIPS 2024 · 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.