Research map / Optimization / Implicit bias and generalization
From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD
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.
Characterizes how the learning rate of multi-step gradient updates on single-index models controls sample complexity, showing a phase transition from information-exponent to generative-exponent regimes, and proposes alternating SGD with two-timescale layer-wise learning rates.
Problem
Sample complexity of gradient-based learning of Gaussian single-index models is governed by the information exponent for online SGD, and by the generative exponent only for non-correlational updates, but the role of the learning rate in choosing between these regimes is not understood.
Approach
A generic spherical online update framework with a learning-rate-dependent oracle psi_eta shows the sample complexity is min over i of (gamma*mu_i(eta))^{-1} d^{(i-2)/2}, so large non-correlational learning rate eta switches the complexity from information exponent to generative exponent; a new alternating SGD updates the second layer first with rate eta and then the first layer on the same sample
Key results
- Sample complexity of batch reuse SGD interpolates from d^{(p-1)∨1} (small eta) to d^{(p*-1)∨1} (large eta), with phase transition at eta ≈ d^{-(p+1)/2}.
- For alternating SGD with sigma_* = He_3, the phase transition occurs at eta ≍ d^{-1/2}; eta ≳ 1/polylog d gives near-linear sample complexity.
- Simulation for alternating SGD shows constant sample requirement in eta until a threshold, then test error decreasing at rate about 1/eta^2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the second-layer learning rate η beyond the phase-transition threshold | Alternating SGD · Gaussian single-index models where p₂ < p | sample complexity (weak recovery): \tilde{\Theta}\big(d^{(p-1) \lor 1}\big) -> \tilde{\Theta}\big(\eta^{-2} d^{(p_2-1) \lor 1}\big) | Helped |
| Choose η too small for the non-correlational term to dominate | Alternating SGD · Gaussian single-index models | sample complexity (weak recovery): T(\eta) = \tilde{\Theta}\big(d^{(p-1) \lor 1}\big) \land \tilde{\Theta}\big(\eta^{-2} d^{(p_2-1) \lor 1}\big) | No clear effect |
| Increase η in batch reuse SGD | Batch reuse SGD · Gaussian single-index models | sample complexity (weak recovery): T(\eta) = \min_{1 \leq i \leq r} \tilde{\Theta}\big((\eta d)^{-2(i-1)} d^{(p_i-1) \lor 1}\big) | Helped |
| Use η ≲ d^{-(p+1)/2} rather than a sufficiently large η | Batch reuse SGD · Gaussian single-index models | sample complexity (weak recovery): T = \Theta(d^{(p-1) \lor 1}) | Hurt |
| Use η ≳ d^{-1} with r ≥ I | Batch reuse SGD · Polynomial target | sample complexity (weak recovery): T = \tilde{\Theta}(d) | Helped |
| Use η ≳ 1 / polylog d and D ≥ I | Layer-wise SGD with D layers · Polynomial target | sample complexity (weak recovery): \tilde{\Theta}(d) | Helped |
| Replace the one-step correlational update with a non-correlational update through sequential second-layer and first-layer steps | Alternating SGD · Gaussian single-index models with p₂ < p | sample complexity (weak recovery): \tilde{\Theta}\big(d^{(p-1) \lor 1}\big) and \tilde{\Theta}\big(\eta^{-2} d^{(p_2-1) \lor 1}\big) | Helped |
Surprising findings
- Full-batch gradient flow on squared loss still has sample complexity depending on the information exponent under the best known upper bounds, so the learning rate rather than reuse alone determines the query class.
Limitations
- Analysis restricted to polynomial activations and Gaussian inputs on the sphere.
- Constant learning rates only; non-constant schedules left to future work.
- Deeper-network extension requires assumptions on Hermite coefficients of compositions that are hard to verify in general.
Experimental setup
Metrics: sample complexity scaling exponent in d alignment with target direction test error
Baselines: online SGD batch reuse SGD smoothed online SGD
Builds on: information exponent (Ben Arous et al.) generative exponent (Damian et al.) batch reuse SGD (Dandi et al.) smoothed online SGD
Closest papers by meaning
- Online Learning and Information Exponents: The Importance of Batch size & Time/Complexity Tradeoffs (ICML 2024 · similarity 0.90)
- Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis (NeurIPS 2025 · similarity 0.90)
- Emergence and scaling laws in SGD learning of shallow neural networks (NeurIPS 2025 · similarity 0.89)
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.88)
- The Optimization Landscape of SGD Across the Feature Learning Strength (ICLR 2025 · similarity 0.88)
- Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws (NeurIPS 2025 · similarity 0.87)
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.