Research map / Optimization / Implicit bias and generalization
Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf’s Law
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.
Derives asymptotic scaling laws for gradient descent and sign descent on a linear bigram model with power-law (Zipfian) token frequencies, showing alpha<=1 (Zipf) makes GD need near-linear-in-dimension iterations while SD scales with sqrt(d).
Problem
Why gradient descent performs poorly on heavy-tailed (Zipf-distributed) word frequencies in training first and last layers of language models, and how iteration count scales with vocabulary size versus Adam-like sign methods.
Approach
Models the linear bigram problem with power-law token and conditional frequencies, reduces GD and sign descent dynamics to closed-form sums, and derives asymptotic relative-error scaling laws in dimension d and rescaled time, covering the alpha<=1 regime that classical scaling-law analyses exclude.
Key results
- For GD with alpha=1 (Zipf), iterations to reach relative error epsilon scale as d^{1-epsilon}, nearly linear in vocabulary size.
- For sign descent with alpha>1/2, iterations scale as (d/epsilon)^{1/2}, giving roughly 100x speedup at common vocabulary sizes.
- GD with alpha>1 converges with iterations scaling as (1/epsilon)^{alpha/(alpha-1)}, independent of dimension.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use sign descent with a well-selected step-size instead of gradient descent | Linear bigram model · Zipf-distributed data (α = 1) | iterations to ε relative accuracy: d^{1-ε} -> (d/ε)^{1/2} | Helped |
| Use gradient descent on power-law data with α < 1 | Linear bigram model · α < 1 | iterations to ε relative accuracy: d^α log(1/ε) | Mixed |
| Use gradient descent on power-law data with α > 1 | Linear bigram model · α > 1 | iterations to ε relative accuracy: (1/ε)^{α/(α-1)} | Helped |
| Use sign descent with a well-selected step-size | Linear bigram model · α < 1/2 | iterations to ε relative accuracy: (1/ε)^{1/(2(1-2α))} | Helped |
| Use sign descent with a well-selected step-size | Linear bigram model · α = 1/2 | iterations to ε relative accuracy: d^{(1-ε)/2} | Mixed |
| Use sign descent with a well-selected step-size | Linear bigram model · α > 1/2 | iterations to ε relative accuracy: (d/ε)^{1/2} | Mixed |
| Use sign descent rather than gradient descent | Linear bigram model · α > 1 | dimension scaling of iterations: t ≈ (1/ε)^{α/(α-1)}; t ≈ (d/ε)^{1/2} | Hurt |
Surprising findings
- Classical smooth convex and Adam-style worst-case bounds predict no progress in early iterations and give dimension-dependent rates that are too pessimistic for this problem.
- The SD scaling in dimension is flipped relative to GD: SD needs more iterations for large alpha where GD converges quickly.
Limitations
- Analysis restricted to deterministic full-batch updates; online/stochastic case not covered.
- Sign descent analysis relies on an averaging assumption for oscillatory regime, and no momentum.
- Model is a linear bigram with square loss; cross-entropy and bilinear models not analyzed.
Experimental setup
Datasets: OpenWebText
Benchmarks: OpenWebText (BPE tokenizers, vocab sizes 1000 to 31622)
Metrics: relative loss error after t steps iterations to reach relative accuracy
Baselines: gradient descent classical smooth convex rates AdaGrad rate RMSProp/Adam analysis
Builds on: Adam source/capacity conditions Zipf's law
Closest papers by meaning
- Sign-Based Optimizers Are Effective Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.89)
- Tokens-per-Parameter Coverage Is Critical for Robust LLM Scaling Law Extrapolation (NeurIPS 2026 · similarity 0.88)
- Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Models (NeurIPS 2024 · similarity 0.88)
- AlphaZero Neural Scaling and Zipf's Law: a Tale of Board Games and Power Laws (NeurIPS 2025 · similarity 0.87)
- Scaling Law with Learning Rate Annealing (NeurIPS 2025 · similarity 0.87)
- Functional Scaling Laws in Kernel Regression: Loss Dynamics and Learning Rate Schedules (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.