REVIEW 3 major objections 3 minor 3 cited by
Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law
T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper claims that on a linear bigram model, Zipf-distributed token frequencies force gradient descent to take almost $d^{1-\varepsilon}$ iterations to reach relative error $\varepsilon$, while sign descent needs only about…
desk verdict The GD scaling for heavy-tailed spectra is rigorous and new, but the sign-descent result is a theorem about an averaging model, not about sign descent, and exact even-time analysis contradicts the claimed √d scaling. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the linear bigram model itself: $d$ tokens, $d^2$ parameters, square loss, and a diagonal Hessian whose eigenvalues are the token frequencies and whose initial residuals are the conditional next-token frequencies. Assumption 2.3 makes both sorted spectra equal power laws with the same exponent $\alpha$, which is what lets the dynamics collapse to one-dimensional sums. The technical machinery is rescaled-time asymptotics: rather than letting $d\to\infty$ with the iteration count fixed, which degenerates to no progress for $\alpha\le1$, the paper sets $t=\tau d^\alpha$ or $t=\tau\sqrt d$ and takes limits of the relative loss. For gradient descent it uses integral approximations via Laplace's method and dominated convergence; for sign descent, since a constant step-size never converges, it introduces an averaged-oscillation model in which components first decrease linearly and then sit at $\eta/2$, plus a step-size parameterization $\eta=1/(H_d T\phi^\alpha)$ that controls how many components remain in the decreasing phase.
What would settle it
On synthetic data that exactly satisfies Assumption 2.3 with $\alpha=1$, run gradient descent with step-size $1/\pi_1$ for $t=\tau d/2$ steps across $d=10^3,\dots,10^6$; the theorem predicts the relative loss tends to $1-\tau$ for every $\tau\in[0,1]$, so a measured limit that differs from $1-\tau$ would falsify the analysis. Equivalently, on real text one can measure the sorted conditional frequencies $\pi_{\rho_j(k)|j}$: if their decay exponent differs from the marginal exponent $\alpha$, the predicted dimension scalings should not hold.
Extended reading notes
Core claim
The paper's central discovery is a set of dimension-scaling laws for deterministic optimization of a linear bigram model with square loss, under Assumption 2.3 that both marginal frequencies and conditionally sorted next-token frequencies decay as $1/k^\alpha$. Because the Hessian is diagonal with eigenvalues $\lambda_{ij}=\pi_i$ and initial residuals $\delta_{ij}(0)=\pi_{j|i}$, the gradient-descent dynamics reduce to a single sum $\sum_k k^{-\alpha}(1-k^{-\alpha})^{2t}/H_{d,\alpha}$, where relative accuracy means $L_d(t)-L_d^*=\varepsilon(L_d(0)-L_d^*)$. Taking $d\to\infty$ with rescaled time gives: for gradient descent, $t\approx d^\alpha\log(1/\varepsilon)$ when $\alpha<1$, $t\approx d^{1-\varepsilon}$ when $\alpha=1$, and $t\approx (1/\varepsilon)^{\alpha/(\alpha-1)}$ when $\alpha>1$; for sign descent, $t\approx (1/\varepsilon)^{1/(2-4\alpha)}$ when $\alpha<1/2$, $t\approx d^{(1-\varepsilon)/2}$ when $\alpha=1/2$, and $t\approx \sqrt{d/\varepsilon}$ when $\alpha>1/2$. For Zipf-distributed data ($\alpha=1$), sign descent therefore cuts the iteration count by a factor of about $d^{1/2-\varepsilon}$, which the paper presents as the mechanism behind Adam's advantage on the first and last layers of transformers.
Load-bearing premise
The load-bearing premise is Assumption 2.3: the conditionally sorted next-token frequencies must decay as the same power law $1/k^\alpha$ as the marginal token frequencies, and for sign descent the oscillatory regime must be well approximated by freezing components at half the step-size; if those fail, the derived $d^{1-\varepsilon}$ and $\sqrt{d/\varepsilon}$ scalings are not guaranteed.
Editorial extensions
If this is right
- At $\alpha=1$, the cost of training to good relative accuracy with gradient descent grows almost linearly in vocabulary size, so vocabulary growth itself becomes an optimization bottleneck.
- With sign descent or Adam-like updates, the same task needs only about $\sqrt{d/\varepsilon}$ iterations, a factor-of-$d^{1/2-\varepsilon}$ saving that grows with vocabulary size.
- The standard neural-scaling-law form $(1/\varepsilon)^p$ is confined to $\alpha>1$; heavy-tailed data produces explicit dimension-dependent iteration counts instead.
- The better algorithm depends on the tail exponent: sign descent wins for $\alpha>1/2$, while gradient descent's dimension scaling is milder for $\alpha<1/2$.
Reading between the lines
- A testable extension of the paper's logic is that in stochastic training of real transformers, the time-to-loss at fixed model size should grow roughly with the square root of the tokenizer's vocabulary size for Adam, and roughly linearly for plain SGD.
- Because the $\alpha=1$ scaling is driven by the rare-token tail of the conditional distribution, the analysis suggests that frequency-aware preconditioners could give Adam-like gains with less dependence on the coordinate system.
- The averaged-oscillation assumption for sign descent is the least controlled step; replacing it with the exact sawtooth dynamics would show how much of the $\sqrt d$ law depends on that idealization.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies deterministic gradient descent (GD) and sign descent (SD) on a linear bigram model with square loss, assuming that marginal token frequencies and conditionally sorted next-token frequencies both follow π_k ∝ 1/k^α (Assumption 2.3). It derives asymptotic rates r(τ) = lim_d L_d(t_d(τ))/L_d(0) for GD (Theorem 3.1) and for an averaged surrogate of SD (Assumption 4.1, Theorem 4.5), and inverts these rates into iteration counts to reach relative error ε (Propositions E.1 and E.2). For Zipf-distributed data (α = 1), the paper claims GD needs t ≈ d^{1−ε} iterations while SD needs only t ≈ √(d/ε), which it presents as explaining the empirical advantage of Adam-like preconditioning. Experiments on synthetic power-law data and on OpenWebText are used to support the predicted scalings.
Significance. Taken on its own, the GD analysis is a solid and useful contribution: the reduction to the spectral sum Σ k^{-α}(1−k^{-α})^{2t}/H_{d,α} is exact, the sum-integral and Laplace arguments are careful, and the d^{1−ε} scaling at α = 1 is genuinely derived rather than fitted. The synthetic and real-data experiments for GD are convincing. The SD part, however, is not a theorem about sign descent as defined in Section 4.1: it concerns the averaged dynamics of Assumption 4.1, and an exact calculation under the paper's own data model contradicts the claimed √d scaling for α = 1. Because the headline claim about Adam's advantage rests on the SD scaling, the manuscript in its current form does not establish that claim. The paper is transparent about the averaging assumption and about the arbitrary fits in Appendix D.3, which is to its credit, but those are load-bearing issues rather than presentation issues.
major comments (3)
- [§4.1, Assumption 4.1; Theorem 4.5; Proposition E.2] The theorems for sign descent are statements about the averaged dynamics of Assumption 4.1, not about the sign descent update δ ← δ − η sign(δ). This distinction is load-bearing. For α = 1 under Assumption 2.3, set a = 1/H_{d,1}, so δ_k(0) = a/k, choose T even and η = a/T, the upper endpoint allowed by Proposition 4.3. In the exact dynamics, every coordinate with k ≤ T is confined to [−η, η] at time T, contributing at most Tη² = a²/T, while coordinates with k > T have δ_k(0) < η and an even number of steps returns them to their starting value, contributing Σ_{k>T} a²/k² ≤ a²/T. Since the initial loss is a²H_{d,2} ∼ ζ(2)a², the exact relative loss is at most 2/(ζ(2)T), so reaching relative error ε requires only T = O(1/ε), independent of d. This directly contradicts Proposition E.2's √(d/ε) scaling for α = 1. The √d dependence in the paper comes from charging d oscillating coordinates with magnitude η/2 each in Assumption 4.1; the exact dynamics confine oscillating coordinates to an interval of length η, removing the factor of d.
- [Appendix D.3, final paragraph] The paper states explicitly that the extension of the SD scalings to the regime τ² ≤ 1/(2α−1) was "decided arbitrarily to fit empirical data" and that the rate 1/(1 + ζ(2α)τ²) is an approximation chosen because it fits the observed data better than the derived 1/(ζ(2α)(1 + τ²)). This is not a fitted constant; it changes the functional form of the rate, and Proposition E.2 inverts this rate to obtain t ≈ √(d/ε). Moreover, for α = 1 and ε = 3/4, the inversion gives τ < 1, which lies outside the derived regime. Consequently, the ε-scaling statement for sign descent at α > 1/2 is not a theorem for the parameter range where it is used, and the plotted ε values in Fig. 2 include points that are not covered by the proven part of the result.
- [§2.1, Assumption 2.3 and Fig. 2] The claimed dimension exponents d^{1−ε} and d^{1/2} depend on the conditional frequencies, after sorting, having exactly the same power-law exponent α as the marginal frequencies. The paper acknowledges in Section 2.1 that this can fail, for example when a token can only be followed by specific tokens, and Fig. 3 shows only medians and quantiles of the raw conditional frequencies rather than a direct validation of the sorted-rank power law with a common α. In the real-data experiments of Fig. 2, the constant c is fitted and the exponent α is not estimated from the conditional frequency table. This does not undermine the mathematical results conditional on Assumption 2.3, but it means the real-data evidence for the specific dimension exponents is weaker than the synthetic validation, and this limitation should be stated more prominently in the main text.
minor comments (3)
- [Proposition E.1, α > 1 case] The constant is stated as C = Γ(1 − 1/α)/(αζ(2α)), whereas Theorem 3.1 defines C = Γ(1 − 1/α)/(αζ(α)). Since the relative loss for GD has denominator H_{d,α} ∼ ζ(α), the appearance of ζ(2α) here appears to be a typo and should be corrected.
- [Theorem 1.1 and Proposition E.1, α = 1 case] The notation t ≈ d^{1−ε} is easy to misread because ε denotes both the target relative error and the exponent of d. It would be clearer to write t = d^{1−ε_target} or to state explicitly that the exponent is 1 minus the desired relative error.
- [Figure 5, right panel] The caption says the envelope is obtained from the simplified dynamics, but the right panel is used to motivate the dependence of the optimal step-size on the budget T. It would help to state in the caption that the curves are computed using Proposition 4.2 rather than exact sign descent, since the exact dynamics behave differently.
Circularity Check
The GD scaling law is a genuine derivation, but the central SD scaling law is partly circular: the α>1/2 rate is explicitly fitted to empirical grid-search data (App. D.3) and the theorem is proved for the η/2 surrogate model (Assumption 4.1) rather than exact sign descent.
-
fitted input called prediction
[Definition 4.4 and Appendix D.3, propagated to Proposition E.2 (α > 1/2 case)]
"Proposition D.4 and Theorem 4.5 only gives guarantees for the regime τ 2 > 1/(2α−1). The extension of the scalings to the regime τ 2 ≤ 1/(2α−1) was decided arbitrarily to fit empirical data. ... the asymptotic scaling presented in Theorem 4.5 uses ... the following approximation for the loss, rd(...) ∼ 1/(1+ζ(2α)τ 2) instead of 1/(1+τ 2) 1/ζ(2α). ... the above proposals (given in Definition 4.4) fit the observed best step-size and loss scalings better."
The α>1/2 rate announced in Theorem 4.5 and used by Proposition E.2 is not the expression derived in Proposition D.4 (1/(ζ(2α)(1+τ^2))); it is an ad hoc replacement chosen because it fits the empirical curves. Proposition E.2 then solves this fitted rate for τ and reports t_d(ε)=1/2 sqrt(d(1/ε−1)/ζ(2α)) as a predicted scaling. The prediction is the inverse of a curve that was itself fitted to the data being 'predicted,' so the claimed √(d/ε) law is statistically forced rather than independently derived.
-
self definitional
[Section 4.1, Assumption 4.1, used by Theorem 4.5 and Proposition E.2]
"To simplify the analysis, we make the following assumption, essentially 'averaging' the oscillations to η/2. Assumption 4.1. We assume that sign descent with step-size η follows the dynamics |δij(t)| := |δij(0)| −tη if |δij(t − 1)| −η ≥ 0, η/2 otherwise."
The theorem's object is not exact sign descent δij(t+1)=δij(t)−η sign(δij(t)) (Prop. A.3) but this surrogate. Under the exact process, for α=1 and even T with η=δ1(0)/T, every coordinate with δ0<η returns to δ0 after two steps and the first T coordinates have |δ_T|≤η, giving normalized error O(1/T) independent of d; the d^{1/2}/√ε scaling in Prop. E.2 is produced by the η/2 convention, which assigns large squared error to all tail coordinates. Thus the central SD prediction is a property of the defining assumption, not of the algorithm it names.
full rationale
The gradient-descent half of the paper is not circular: Theorem 3.1 starts from the exact closed form r_d(t)=Σ k^{−α}(1−k^{−α})^{2t}/H_{d,α} and evaluates it via dominated convergence and Laplace asymptotics; the d^α and d^{1−ε} scalings are genuine consequences of that sum, and the α=1 result is independently derived. There is no load-bearing self-citation: Kunstner et al. (2024) only motivates the problem, and the α=1 GD rate is credited to Bulatov's earlier blog post. The sign-descent half is partially circular. Definition 4.4 is explicitly calibrated to the empirically best step-size found by grid search, and Appendix D.3 admits that the α>1/2 rate in Theorem 4.5 was 'decided arbitrarily to fit empirical data'; Proposition E.2 then inverts that fitted rate to obtain the √(d/ε) time-to-ε prediction. Additionally, Theorem 4.5 is proved for the η/2 surrogate dynamics of Assumption 4.1 rather than exact sign descent, and the exact even-time dynamics given in the paper do not produce the same d^{1/2}/√ε scaling. Because the GD analysis is independent and the small-ε functional form of the SD scaling also has a non-fitted derivation in Proposition D.4, the circularity is partial rather than total, giving a score of 5.
Assumptions & free parameters
free parameters (2)
- Sign descent step-size exponent scalings φ_d(τ) =
φ_d(τ) = d(c1 + 4c2 τ^2)^{-1} for α<1/2; d^{1-τ} for α=1/2; (1 + 1/τ^2)^{1/α} for α>1/2
- Constant c in real-data time-to-ε plots (Fig. 2) =
fitted, value not reported
assumptions (4)
- domain assumption Word frequencies and conditionally sorted next-word frequencies both decay as 1/k^α with the same exponent α > 0 (Assumption 2.3).
- ad hoc to paper Sign descent enters an oscillatory regime that can be modeled as a constant distance η/2 (Assumption 4.1).
- domain assumption The non-degenerate asymptotic limit is obtained by rescaling time t with d^α, d, or √d depending on α (Eq. (2)).
- standard math Standard asymptotic tools: sum-integral bounds (Lemma C.1), Laplace method, and dominated convergence for the integral forms (Appendix C).
Cite this review
Pith. "Pith review of Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law." pith.science (2026). https://pith.science/paper/ERTVQSU4
@misc{pith2026250519227,
author = {Pith},
title = {Pith review of: Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law},
year = {2026},
howpublished = {\url{https://pith.science/paper/ERTVQSU4}},
note = {Machine review of arXiv:2505.19227}
}
abstract
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 $k$th most frequent word $\pi_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 $\pi_k \propto 1/k^\alpha$ parameterized by the exponent $\alpha > 0$. We derive optimization scaling laws for deterministic gradient descent and sign descent as a proxy for Adam as a function of the exponent $\alpha$. Existing theoretical investigations in scaling laws assume that the eigenvalues of the data decay as a power law with exponent $\alpha > 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 $\alpha = 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.
Figures
Figures from the paper (5 more)
Forward citations
Cited by 3 Pith papers
-
Muon in Associative Memory Learning: Training Dynamics and Scaling Laws
In a linear softmax memory model, Muon equalizes learning across frequency tiers and gives exponential (noiseless) or T^{-2} (noisy power-law) convergence, versus polynomial or T^{-(1-1/β)} for gradient descent.
-
Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime
For diagonal and quadratic two-layer networks, training maps to LASSO and matrix compressed sensing, yielding a full phase diagram of excess-risk scaling exponents and a spectral characterization of the trained weights.
-
On the Effectiveness of the z-Transform Method in Quadratic Optimization
Using z-transforms and Tauberian theory, this paper derives sharp asymptotic rates, such as 1/k^omega for gradient descent and 1/k^{min(2omega, omega+1)} for Nesterov acceleration, for quadratic optimization in infini...
Reference graph
Works this paper leans on
-
[1]
High-dimensional dynamics of generalization error in neural networks
Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky (2020). “High-dimensional dynamics of generalization error in neural networks”. In: Neural Networks 132, pp. 428–446. Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma (2021). “Explaining Neural Scaling Laws”. arXiv/2102.06701. Lukas Balles, Fabian Pedregosa, and Nicolas Le Roux ...
arXiv 2020
-
[3]
A.2 Additional details about the figures Fig
= δij(t) − η sign(δij(t)), the distance after t steps is given by δij(t) = ( δij(0) − ηt if t ≤ Tswitch, cij if t − Tswitch is odd, cij − η if t − Tswitch is even, where Tswitch = ⌊δij(0)/η⌋, cij = δij(0) − Tswitchη. A.2 Additional details about the figures Fig. 1 shows the dynamics of gradient descent on Problem 2.1 on data satisfying Assumption 2.3. Fig...
work page 2019
-
[6]
We write the function rates in matrix form for the loss Ld defined in Problem 2.1, but this could equivalently be transformed to a vector form using and ∥x − x∗∥2 2 = ∥W − W∗∥2 if x = vec(W) and x∗ = vec(W∗) where vec stacks the columns of W as a single vector. For a twice-differentiable function, this is equivalent to assuming that the eigenvalues of the...
work page 2018
-
[8]
Ld(t) − L∗ d ≤ Tr(L)π1 T . Normalizing the loss and simplifying the constants using the same approach as in Proposition B.1 gives the following asymptotic upper bound Ld(t) − L∗ d Ld(0) − L∗ d ≤ rAdagrad d (t) := Tr(L)π1 T (Ld(0) − L∗ d) d ∼ d log(d) T 6 π2 . Although we might expect Adagrad to outperform sign descent as it uses decreasing step-sizes to a...
work page 2024
-
[9]
so the proposed approach does not improve over gradient descent. Normalizing the loss and using the same approach as in Proposition B.1 gives Ld(t) − L∗ d Ld(0) − L∗ d ≤ ϵ2 2 , after t ≥ ˜O(d). This scaling predicts the same performance for Adam and gradient descent (up to log factors depending on d and ϵ that we ignored) whereas our analysis shows a scal...
work page 2018
-
[87]
Super Con- sistency of Neural Network Landscapes and Learning Rate Transfer
Springer. Lorenzo Noci, Alexandru Meterez, Thomas Hofmann, and Antonio Orvieto (2024). “Super Con- sistency of Neural Network Landscapes and Learning Rate Transfer”. In: Neural Information Processing Systems (NeurIPS). Elliot Paquette, Courtney Paquette, Lechao Xiao, and Jeffrey Pennington (2024). “4+3 Phases of Compute-Optimal Neural Scaling Laws”. In: N...
arXiv 2024
-
[768]
We compute the frequencies and conditional frequency tables for each vocabulary size using the entire dataset. We use the closed form formulas for the loss after t steps using O(d2) computation detailed in the previous section to avoid having to run gradient and sign descent on those large models. Gradient descent uses the empirically-derived step-size of...
work page 2020
-
[2011]
for Das et al. (2024) and Liu et al. (2025), or consider more general problems including non-convex functions for Bernstein et al. (2018) and Safaryan and Richtárik (2021). We are not aware of existing analyses that specifically target sign descent on diagonal quadratic problems such as Problem 2.1. This makes a direct comparison difficult. It might be th...
work page 2024
Show all 10 references
-
[2018]
implementation of BPE Sennrich et al., 2016, we train tokenizers with vocabulary sizes of 1 000, 3 612, 10 000 and 31 622 tokens on a the first 2 000 000 entries of the dataset with a maximum sentence length of 16
2016
-
[2025]
effectively
give convergence results to stationarity instead of convergence in optimality gap, measured using the 1-norm of the gradient instead of the Euclidean norm. Because ∥v∥2 1 ≤ ∥v∥2 2d for a d-dimensional vector v, the time required to get the 1-norm small might be much worse than...
2021
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.