# Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law

arXiv: https://arxiv.org/abs/2505.19227 · HTML: https://mlsanity.com/paper/2505.19227/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 50 references that are in the map.
- First posted on arXiv 25 May 2025.

## Builds on (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Symbolic Discovery of Optimization Algorithms](https://mlsanity.com/paper/2302.06675/) (2023)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer](https://mlsanity.com/paper/2203.03466/) (2022)
- [High-dimensional dynamics of generalization error in neural networks](https://mlsanity.com/paper/1710.03667/) (2017)
- [A Constructive Prediction of the Generalization Error Across Scales](https://mlsanity.com/paper/1909.12673/) (2019)
- [Understanding the Difficulty of Training Transformers](https://mlsanity.com/paper/2004.08249/) (2020)
- [Adam-mini: Use Fewer Learning Rates To Gain More](https://mlsanity.com/paper/2406.16793/) (2024)
- [Scaling Laws with Vocabulary: Larger Models Deserve Larger Vocabularies](https://mlsanity.com/paper/2407.13623/) (2024)
- [A Solvable Model of Neural Scaling Laws](https://mlsanity.com/paper/2210.16859/) (2022)
- [Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Be](https://mlsanity.com/paper/2304.13960/) (2023)
- [A Dynamical Model of Neural Scaling Laws](https://mlsanity.com/paper/2402.01092/) (2024)
- [On the SDEs and Scaling Rules for Adaptive Gradient Algorithms](https://mlsanity.com/paper/2205.10287/) (2022)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Models](https://mlsanity.com/paper/2402.19449/) (2024)
- [4+3 Phases of Compute-Optimal Neural Scaling Laws](https://mlsanity.com/paper/2405.15074/) (2024)
- [Depthwise Hyperparameter Transfer in Residual Networks: Dynamics and Scaling Limit](https://mlsanity.com/paper/2309.16620/) (2023)
- [Scaling Laws in Linear Regression: Compute, Parameters, and Data](https://mlsanity.com/paper/2406.08466/) (2024)
- [Stochastic Sign Descent Methods: New Algorithms and Better Theory](https://mlsanity.com/paper/1905.12938/) (2019)
- [Understanding AdamW through Proximal Methods and Scale-Freeness](https://mlsanity.com/paper/2202.00089/) (2022)
- [The Geometry of Sign Gradient Descent](https://mlsanity.com/paper/2002.08056/) (2020)
- [Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model](https://mlsanity.com/paper/2006.08212/) (2020)
- [A Qualitative Study of the Dynamic Behavior for Adaptive Gradient Algorithms](https://mlsanity.com/paper/2009.06125/) (2020)

## Built on by (most cited first, 24 of 24)

- [Deriving Neural Scaling Laws from the statistics of natural language](https://mlsanity.com/paper/2602.07488/) (2026)
- [Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime](https://mlsanity.com/paper/2509.24882/) (2025)
- [Theory of Scaling Laws for In-Context Regression: Depth, Width, Context and Time](https://mlsanity.com/paper/2510.01098/) (2025)
- [Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memory](https://mlsanity.com/paper/2603.26554/) (2026)
- [Kernel ridge regression under power-law data: spectrum and generalization](https://mlsanity.com/paper/2510.04780/) (2025)
- [Optimal scaling laws in learning hierarchical multi-index models](https://mlsanity.com/paper/2602.05846/) (2026)
- [Optimal Learning Rate Schedules under Functional Scaling Laws: Power Decay and Warmup-Stable-Decay](https://mlsanity.com/paper/2602.06797/) (2026)
- [Clarifying Shampoo: Adapting Spectral Descent to Stochasticity and the Parameter Trajectory](https://mlsanity.com/paper/2602.09314/) (2026)
- [Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Laws](https://mlsanity.com/paper/2509.24914/) (2025)
- [Towards Robust Scaling Laws for Optimizers](https://mlsanity.com/paper/2602.07712/) (2026)
- [Fast Catch-Up, Late Switching: Optimal Batch Size Scheduling via Functional Scaling Laws](https://mlsanity.com/paper/2602.14208/) (2026)
- [Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance](https://mlsanity.com/paper/2512.00763/) (2025)
- [On the Effectiveness of the z-Transform Method in Quadratic Optimization](https://mlsanity.com/paper/2507.03404/) (2025)
- [Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data](https://mlsanity.com/paper/2511.18661/) (2025)
- [Tight Complexity of Muon under Heavy-Tailed Noise](https://mlsanity.com/paper/2605.18528/) (2026)
- [Same Architecture, Different Capacity: Optimizer-Induced Spectral Scaling Laws](https://mlsanity.com/paper/2605.21803/) (2026)
- [Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success](https://mlsanity.com/paper/2606.14560/) (2026)
- [Beyond a Single Explanation of the Adam--SGD Gap](https://mlsanity.com/paper/2606.14259/) (2026)
- [Open Problem: Is AdamW Effective Under Heavy-Tailed Noise?](https://mlsanity.com/paper/2606.23676/) (2026)
- [Dynamics of Stochastic Momentum with Sparse Updates in High Dimensions](https://mlsanity.com/paper/2605.28961/) (2026)
- [SGD in Multiclass Logistic Regression: Sequential Learning and Scaling Laws](https://mlsanity.com/paper/2609.07868/) (2026)
- [Linear RNN Scaling Laws: When Longer Sequences Beat More Sequences](https://mlsanity.com/paper/2609.27964/) (2026)
- [Asymptotic Risk of Learning-Rate Schedules for Least-Squares Regression with Discretely Distributed Features](https://mlsanity.com/paper/2610.16518/) (2026)
- [Exact Scaling Laws for a Random-Features Bigram Model](https://mlsanity.com/paper/2610.19281/) (2026)

## Abstract (arXiv)

Recent works have highlighted optimization difficulties faced by gradient descent in training the first and last layers of transformer-based language models, which are overcome by optimizers such as Adam. These works suggest that the difficulty is linked to the heavy-tailed distribution of words in text data, where the frequency of the kth most frequent word πk is proportional to 1/k, following Zipf's law. To better understand the impact of the data distribution on training performance, we study a linear bigram model for next-token prediction when the tokens follow a power law πk propto 1/kα parameterized by the exponent α > 0. We derive optimization scaling laws for deterministic gradient descent and sign descent as a proxy for Adam as a function of the exponent α. Existing theoretical investigations in scaling laws assume that the eigenvalues of the data decay as a power law with exponent α > 1. This assumption effectively makes the problem ``finite dimensional'' as most of the loss comes from a few of the largest eigencomponents. In comparison, we show that the problem is more difficult when the data have heavier tails. The case α = 1 as found in text data is ``worst-case'' for gradient descent, in that the number of iterations required to reach a small relative error scales almost linearly with dimension. While the performance of sign descent also depends on the dimension, for Zipf-distributed data the number of iterations scales only with the square-root of the dimension, leading to a large improvement for large vocabularies.