Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf’s Law
Authors: Frederik Kunstner
Francis Bach
Venue: NeurIPS 2025 poster ()
Keywords: scaling law
optimization
gradient descent
sign descent
bigram model
high dimension
power-law
zipf's law
Primary area: optimization
TL;DR: On a linear bigram model, we show that the heavy-tailed distribution found in text requires training for a number of iteration that scales linearly with the vocabulary size with gradient descent but only a square-root scaling with sign descent.

Abstract: Recent works have highlighted the optimization difficulties encountered by gradient descent in training the first and last layer of transformer-based language models, which are overcome by optimizers such as Adam. The problem appears 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$. We derive optimization scaling laws for deterministic gradient descent and sign descent as a proxy for Adam as a function of the power $\alpha \geq 0$. This setting differs from existing theoretical investigations in scaling laws which assume that the eigenvalues of the data decay as a power with power $\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 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 over gradient descent for large vocabularies.

Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law
Frederik Kunstner frederik. kunstner@inria.
Francis Bach francis. bach@inria.ff
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 kth most frequent word TTK is proportional to 1/k, following Zipf's law. To better understand the impact of the data distribution a linear bigram model for next-token prediction when the tokens follow a power law TTk 1/k² parameterized by the exponent >> We derive optimization scaling laws for deterministic gradient descent and sign descent as proxy for Adam function of the exponent a. Existing theoretical investigations in scaling laws assume that the eigenvalues of the data decay power law with exponent >> 1. This assumption effectively makes the problem "finite dimensional" 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 a as found in language is "worst-case" for gradient descent, in that the number of iterations required to reach 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 large improvement for large vocabularies.
training performance, we study
Introduction
Recent works have shown that one of the primary benefits of Adam (Kingma and Ba, 2015) in training transformed- language models (Vaswani et al., 2017) lies in how it handles the first and last layers (Zhang et al., 2025; Zhao et al., 2025). For language models, the input and output dimensions correspond to distinct words in the vocabulary, where the kth most frequent word has frequency * 1/k following Zipf's law (Piantadosi, 2014). Kunstner et al. (2024) provide evidence that this heavy-tailed distribution leads to optimization difficulties for gradient descent that Adam is able to overcome. They argue that Zipf's law is "worst-case" in that it combines large imbalance in frequencies, while decaying slowly enough that most samples come from the tail.
Our objective to formalize this empirical observation, and describe the impact of the heavy- tailedness of the data distribution the convergence of gradient descent (GD) and sign descent (SD) as a proxy for Adam (Ticleman and Hinton, 2012; Bernstein et al., 2018; Balles et al., 2020; Chen et al., 2023). We consider linear bigram model for next-token prediction trained with the square loss, where the token frequencies ne. follow a power law Te x 1/k: with exponent a > O. While this problem could be solved directly rather than with iterative methods, it is good starting point for the theoretical investigation of optimization dynamics. Despite its apparent simplicity, this model already reproduces the observation that GD performs poorly on Zipf-distributed data (see Fig. 1). The behavior of gradient and sign descent are also not well described by current results, see Section 1.2.
Our approach is inspired by the line of work on theoretical scaling laws, also known as asymptotic convergence as the dimensionality grows (e.g., Caponnetto and De Vito, 2007; Advani et al., 2020;
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1.0
TT X k172
Th x K
1
Relative error
d' 105
10
0.5-
10
109
10a
0.0
250
Steps
750
1000
250
Steps
Steps
1000
Figure Gradient descent (GD) scales badly with vocabulary size when the data is Zipfian. Relative error linear bigram problem with squared loss trained with GD with vocabulary size d when the word frequencies follow тą x 1/k". For a I 1 (left, middle) the performance degrades with vocabulary size and is worst for Zipf-distributed data (a 1). When the frequencies have lighter tails (a = 2, right) GD works well for all vocabulary sizes. Our objective is to explain this behavior.
Berthier et al., 2020; Bahri et al., 2021; Cui et al., 2021; Maloney et al., 2022; Paquette et al., 2024). Instead of analyzing the generalization error of online gradient descent as the dimension of the model and sample size grow, we study the convergence rate of GD the dimension grows, Spectral assump- tions on the eigenvalues of the Hessian following a power-law are common the literature, which in our case correspond to assumptions on word frequencies. But these works focus on power-laws that are not "too" heavy-tailed, 1/k with a > 1, which lead to sublinear rates independent of dimension. In contrast, we focus on the case S where it becomes impossible to make progress unless the number of iterations grows with the dimension of the problem. Our contributions are as follows.
1. We propose simplified model of the word frequencies that leads to tractable dynamics for GD and SD, that captures the difference in their training performance experimentally (Fig. 2).
2. We derive scaling laws for GD and SD in this model as function of a > O, covering power-laws that decrease as slow or slower than Zipf's law (a S 1). This setting is often ignored in existing analyses and leads to qualitatively different results, with scaling laws that are not power-laws and require the number of iterations to grow with
3. For GD on Zipf-distributed data (a = 1) the number of iterations required to reach small relative error seales almost linearly with dimension, ~ This setting is "worst-case" in that the case < results in better scaling of t ~ d while a: > 1 does not require t to scale with d.
4. In comparison, SD under Zipf-distributed data only requires t ~ vd. provably confirming its benefits over GD on a language task, but not in all settings as SD exhibits worse scaling a
1.1 Overview of the results
We consider a simplified language modeling tasks, given vocabulary of words, train linear bigram model with square loss to predict the next word E [d] given the current word x E [d] represented one-hot vectors x, (0, 1)d The dynamies of the problem depends the word frequencies and conditional frequencies T which we assume follow a power law 1/k", formalized in Section 2. The scaling we analyze how the loss changes as the dimension d and number of iterations increases, depending on a. For GD on a > 1, we recover the result that the loss after steps, (t),,, follows the power law La(t) ctt P + C2 as d constants c,, C2. Equivalently, we could write the relative optimality gap
for some power p and
La(l) La ~
ra(t) Lx(0) L2
where denotes asymptotic equivalence, rt()) PP means limg- ra(()/t-P 1. This rate is independent of d, but specific to GD with a > 1. Our results show that in other settings, the number of iteration t needs to scale with to achieve g-relative optimality gap. ra(t) ~ The following a simplification our main results, made formal in Theorems 3.1 and 4.5.
Informal theorem. To reach an e-relative optimality gap, the number of iterations should scale as
d
ia < 1, fa=1, = 1, fa>1. 1,
if < 1/2,
t 1x
dl
for GD, GD,
and tx
Vdi=
if 1/2,
SD, SD,
if 1/2,
where x (equivalently, t +(f)) hides constants and factors that depend on but not on d.

---

1.00
Real data
10*
Gradient descent
10
Sign descent
Relative error
0.75-
GD
10a
10a
SD
Time to
0.50
asym.
Time
10"=
10"-
asym.
0.25
10*-
10a-
0.00
10a
10
10
10a
10a
10a
10
10a
10
Optimization horizon T
Vocah, size d
Vocab. size df
Figure 2: Our scaling predicts the behavior of gradient descent and sign descent on real data. Left: the convergence of gradient descent (GD) and sign descent (SD) is close our asymptotic prediction (- -, the finite dimension and our simplified model of the frequencies in Assumption 2.3. Middle/Right as d grows, the number of iterations required to reach e relative error matches our predictions, showing that SD scales better with dimension for small e. We show results on real data (dots) against the scaling of cid= for GD and czd/ /2 for SD (dashes) where c1. C2 are fit to the data.
on a bigram model with 32k tokens on OpenWeTText WebText, although not exactly due
For language and Zipf-distributed data (a 1), scaling predicts that the number of iterations required to reach relative error scales almost linearly with d for GD if e is small while it scales as d'/² for SD. For common vocabulary sizes of 10a tokens, this leads a 100-times speedup. Zipf-distributed data is also "worst-case" for GD, as other values of a lead to better scaling in d.
We recover the power-law scaling for GD when settings (Theorems 3.1 and 4.5). For a = 1, the relative optimality gap behaves as
1, but obtain different functional forms for other
(t) 1 log(2t)
in the sense that ra( ~.c
log(d)
We confirm these predictions experimentally using real data on OpenWebText, shown in Fig. 2.
1.2 Related work
Convergence of Adam and sign descent. The benefit of Adam has been argued stem from its similarity to sign descent, in that the updates are uniform across coordinates (Bernstein et al., 2018; Balles et al., 2020; Chen al., 2023). This "scale-freeness" can reduce the dependence on the condition number (Zhuang et al., 2022), but this does not imply SD outperforms GD as known convergence rates for sign-like methods instead depend on the dimension (e.g.. Safaryan and Richtárik, 2021; Das et al., 2024; Liu et al., 2025). In the bigram problem with Zipf-distribute data, the dimension grows faster than the condition number, leading to worse guarantees for SD. We compare our asymptotic analysis to existing rates in Appendix B.
SDE approximations of sign methods. Scaling laws have been derived for online sign-like algorithms through stochastic differential equations (Ma et al., 2021; Malladi et al., 2022; Xiao et al., 2024; Compagnoni et al., 2025). The focus of these works on the scaling the step-size with batch size and the asymptotic stationary distribution of the algorithm which controls the generalization error. As noise is not necessary reproduce the performance gap between GD and Adam (Kunstner et al., 2023), we instead focus on the impact of heavy-tailed data on the deterministic dynamics.
Scaling laws and asymptotic results. Empirical scaling laws have been developed to extrapolate the performance of deep networks at seale and how to balance compute across model and data sizes (Rosenfeld et al., 2020; Kaplan et al., 2020; Hoffmann al., 2022). Many works have contributed to the theoretical understanding of this scaling behavior through high dimensional analyses and random matrix theory (Advani et al., 2020: Bahri et al., 2021: Maloney et al., 2022: Bordelon et al., 2024a; Lin et al., 2024; Paquette et al., 2024), classical source/capacity conditions from learning theory (Caponnetto and De Vito, 2007: Berthier al., 2020; Cui et al., 2021), also used in an optimization context (Velikanov and Yarotsky, 2024). However, those works study problems where the spectrum decays fast, and does not cover case a S 1. This regime, covering Zipf's ' law, might be more relevant when considering scaling the vocabulary size, as in the work of Gowda and May (2020) and Tao et al. (2024). While they hypothesize that larger vocabularies might lead to worse performance due to overfitting, as larger vocabularies implies fewer examples per word in addition to more compute per step, we show that larger vocabulary size might also need more steps to get the training eиror down. Closest to our work is perhaps the blog post of Bulatov (2023), which argues that
3

---

the loss under GD should approximately behave as log(t/d) on a problem matching our setting with a Our work provides formal justification for this scaling.
2 Problem setup
In this section, we present the problem setting, a linear bigram model with square loss, the modeling assumptions used to make the problem tractable and the approach we to derive our results.
Problem 2.1 (Linear bigram model), Let Xi E 1) for i = =1..... n be one-hot encodings from d classes (or tokens), with their concatenation X, E {0, (0,1, fūt with linear model,
W
XW - YI -
where W E Raxd and T -T(X'X)
2n
We define Th and TT the frequencies and conditional frequency statistics of the data,
m 12
(with the convention 1/- = 0) Vj, E [d].
Ei= 11
The analysis of GD quadratics typically uses eigenvalue decomposition. Consider a d- dimensional quadratic f(x) = (xxx'")AA(xxx² with minimizer x" where the eigenvalues/vectors pairs of A are (d4, v.) E R Rd for i ,....,d The dynamies of GD with step-size n, X X₁ (x, - x"), decompose in terms of the distance along cigenvectors, dt(t) = (v, X x²)
d
f(x:) = Z [x
x*) Ax)
Σ 2 1=1
1 - n,, ) (,)²
For the --dimensional bigram model (2.1), the dynamics depend on the frequencies Ty and T
Proposition 2.2. The dynamics of gradient descent on Problem 2. initialized at W = are described by the eigenvalues and distances to solution Aaj. (0)(0) for i, = 1,..., d, using La(t) = WW.,.),
Ca(t) Li - 2
Σ N1 22
t 1755))
21
51
(1)
j=1
where La = min Lod as the eigenvalues and distances to solution are Xij = T. and 5.5 = =33
Proof sketch. The Hessian of La is diagonal, with diagonal blocks X X/n Diag( [T 11..... aa)
repeated dl times. The eigenvectors are the standard basis with eigenvalues Xij m; The solution is
W (X"X)-1X) -Y where wty J i as [X Y //lls = Ty Tr giving (0) m3 8
2.1 Modeling assumptions
Getting an interpretable form of the rate in Eq. (1) requires assumptions on the values of X and 6;- Assuming μ X; L leads the typical smooth (strongly-) -convex rates (e.g., Nesterov, 2018),
La(t) - Ca < 8,(0)²
La(t) - C. C. (1 (1- (Ca(()))))) L.).
While valid, these worst-case bounds are too coarse capture the richness of the behavior of GD and becomes vacuous if - 0 or Σ (wo)2 + oo as d + co. To obtain fine- fine-graines grained results, we assume that the frequencies ne and conditional frequencies kx follow power laws.
Assumption 2.3 (Heavy-tailed data). We assume that the frequencies and conditional frequencies follow frequency-rant power law with exponent a 0. That is, assuming the frequencies are sorted (Tyy 2 T(+1)) and defining the sorting permutations Pj such that т Tpy(k) j 2 (p,(k+1)13
1 ka
Thk X
and Tp((k) x ka for all j.k,
where by TuK 1/k" mean that the frequencies are normalized, T 1/2k for 1/=1
This assumption may appear strong, as it would satisfied example if the words were sampled i.i.d. with frequencies ........ na n Tk. But it does not require that all conditional distributions

---

Word frequencies T
Conditional frequencies
10
(1:1b
5.95%
Frequency
10-90%
10
25-75%
10
data
median
1/k
1/k
10
Rank of word
10
10
10 Rank of next word 10
10"
Figure 3: Token frequencies and conditional frequencies approximately follow Zipf's law. The approximation of Assumption 2.3 (- is a reasonable approximation of the frequencies (left) and conditional frequencies (right) on text data, computed on Open WebText for a vocabulary of 104 words. Right: median and quantiles of the next-word frequencies after sorting, (k)(k) for j [d].
be the same. The distribution of the next word after j can depend on j. This assumption merely asks that, once sorted, the next-word frequencies follow power law with the same exponent. Some distributions might deviate from this trend if token can only logically be followed by specific tokens, or if the word being conditioned on is rare and our dataset is relatively small. While we do not expect the assumption to be exactly satisfied in practice, appears be reasonable high-level approximation of real-world data, as shown in Fig. 3 in comparison to the empirical distributions on OpenWetText, and leads accurate predictions shown in Fig. 2.
Relation to other spectral conditions. Even though Problem 2.1 is d2 --dimensiinal,, the dynamics of GD are equivalent to those run on a d-dimensional problem as Proposition 2.2 can be rewritten as (() Li 2 [1= (1 decay conditions on the eigenvalues and distances to the solution, Fy. x k- and A x -- similar to the source/capacity conditions (Caponnetto and De Vito, 2007). However, their focus is typically on a fast decay, a +6b 1, which leads dimension- pevensionnindeeeddenn power-laws (see c.g., Paquette et al., 2024, and references therein). While Assumption 2.3 is special case corresponding to (a, b) (a, 0), we study the case a I to understand the behavior of optimizers on heavy- data.
rymr;) A for A Σ 1 (0)2.. Many works have considered
2.2 Strategy for the analysis
Our goal is to derive scaling laws for the loss of Problem 2.1 in d dimensions after t steps, (t))). as d -> D0. Such scaling laws can be interpreted as approximating the convergence rate for large d, or serve as a guide on how to scale the hyperparameters of the optimizer as we increase the vocabulary size. Formally, we compute the asymptotic limit of the rate r(t) at which the relative loss decreases,
Ca(t) - L3 = r(t), Cx(0) Ca
Ca(t) L5 (t) Lā), where A is notation for lim
Works on scaling laws typically model the absolute value of the loss. This approach degenerates when the loss at initialization vanishes or diverges d - Do which happens when a < 1. Considering the relative decrease circumvents the issue, as also noted by Bulatov (2023) and Tao et al. (2024).
Another potential degeneracy is the scaling of time. If the problem becomes more difficult as d grows, might be impossible to make progress in finite time. To take a concrete example, suppose that Li = and La(t) (a()) with ra(t)= (1 1/d)". If we take the limit as d - oc for fixed t, obtain lim44+00 (1-1/d) = 1. The rate no longer depends on f, and we cannot make progress unless t grows with d. If we instead introduce a rescaled time variable and scale ta(r)= = rd, we recover linear rate in the rescaled time r as (1 - 1/d)rd A e-T_ A similar issue arises in random matrix theory, where the dimensions of the matrix solutions (Potters and Bouchaud, 2020). It can be verified that tz(T) = 7d is the "right" scaling, as the limit (T() degenerates otherwise. Using f(z) & 9(x) for lim f(r)/ (())//(()) O.
taken to grow jointly with fixed ratio to avoid degenerate
have ra(()(7)) A if La(T) & d and ra(La(T)) A 0 if La(T) > d: we either make no progress or solve the problem instantly. Our results are derived by taking the finite dimensional rate rt( with scaling tu such that the asymptotic rate r(7) is well-defined in terms of the rescaled time 7,
lim ra(ta(F)) lim Ca(ta(T)) L3 d=
r(T)
d=+00 Ca(0) L3
'vven with ii.d. data following T& x 1/k, accurately estimating the conditional frequency takes many samples. With vocabulary size of d = 10 we expect the pair (æ y d) once every 10" tokens.
5

---

a = 0.5
==l
2
100
10a
10
10-1
d
10
Relative
10
d 10
C
10
1-a
10
10
T/dd"
1010
10
7=1
10 10
Figure 4: Scaling of gradient descent on power-law data with exponent a (Theorem 3.1). The dynamics of gradient descent the linear bigram model with data satisfying Assumption 2.3 converge to our scaling law (- -, Theorem 3.1) as grows. Achieving a relative error E requires
scaling the iteration budget T with d for < 1, T with d' for = 1, and no scaling for a >> 1.
Scaling laws for gradient descent
We study the relative error of GD with the step-size 77 1/ /T. the inverse of the largest eigenvalue,
La(l) L3 ra(t) (0 La
2
Σ T T
Before diving into the main result, we provide some intuition on those dynamics. The performance of GD depends the speed of convergence for each word, (1 - Txx /T)), and the proportion of the error coming to that word, Ty. The parameter a controls both. If we increase a, the frequencies Ty x 1/k decay faster. Low-frequency words converge more slowly, (1 T& m1 (1 1/k"), but contribute less to the error, T 1/2k" where the normalization term is
1/k1
For > 1, the error is dominated by high-freque frequeeryye words, which converge quickly. The error attributed to the first K words. =k=1 Tk. is a constant approximation of the total. Increasing the vocabulary size d does not make the problem much harder as low- wwwffrequency words contribute little. For a < 1, the error associated with the first K words vanishes if K is fixed and d grows, indicating that most of the error comes from low-frequency words. However, their convergence speed improves as a decreases, with the extreme case uniform frequencies at a = O. making the problem easier. The case a 1 of Zipfian data exhibits the worst of both settings. The decay is slow enough that the contribution of low-frequency words is significant, but fast enough that their convergence is slow.
The following theorem formalizes these intuitions.
Theorem 3.1 (Scaling for gradient descent). On the bigram problem (Prob. 2.1) with distributions following a power law with exponent a >> 0 (Assumption 2.3), gradient descent with step-size 1/Th. /m. with time scaling ta(T) has the following asymptotic convergence rate (Eq. (2)).
r(r) 1 1-
E1( 2 1-a e a 7 ++1
Ifa 1,
(o(T) dd"
a
=a=
La(T) _dd"
where E [0, 1]. r(r) B 21 2t) x C 71-
r(T) = =1 1-7
ifa
Ca(T)=n+
aC(a)
where I' is the Gamma function, E is the generalized exponential integral, is the Beta function, and Ç is the zeta function (DLMF, $5.2, $5.12 $8.19 $25.2), and C I 2) /a((a).
Proof. We sketch the proof for a = and leave the remaining cases to Appendix C. Under Eq. (1) and Assumption 2.3 the dynamics of the normalized loss ra(t) (Eq. (3)) reduce to
ra(l)=
k
(1 kー k-
Há,a k=1
where Ha,a = Ed= ~ To simplify the analysis, we use the integral form of the sum as we can use Laplace's 's method to estimate its behavior for large d, see Appendix C for formal justification;
1
/ k- (1 k 2 ak
log(d)
Har [' 2) dz,
For = 1, ra(t)= ~ Ta(t)= = Ha,

---

Individual directions
Total emror (d = 4)
Budget T step-Size
1.0
1.0
81 63
Relative error
Exact Assumption
2
[6,())
82
8
2
Assumption
Relative
10
10
500 1000
1500
Figure 5: Illustration of our modeling assumption for sign descent (Assumption 4.1), Left: instead of modeling the oscillations of sign descent, we treat the oscillatory phase constant. Middle: The effect on the total error. Right: Because SD eventually oscillates, the step-size needs to depend on the iteration budget T' to achieve best performance after T steps (the envelope -).
after the change variable k = d or = log(k)/ log(d). As the normalizer Ha, log(d), we only need consider the limit of the integral. Taking we make no progress, regardless of t. To make progress, t needs to scale as 2t d' for T E [0, 1],
with fixed, the integral converges 1 and
(a(d") = log(d)
Hd, (1
d== d' d'
dz.
For fixed and as d -> oo, the integrand converges O if and if 7. As it is bounded by a constant, we can exchange limits and integrals by the dominated convergence theorem to obtain
(((1- d==²) d= = f Odz + [
lim d=+00
1dz
dr
The results highlight different regimes depending on a. The number iterations needs to scale with dimension if the data decays slow slower than Zipf's law (a S whereas it is necessary for tighter-tailed data (a >> 1). We show in Fig. 4 that the dynamics on data satisfying Assumption 2.3 converge to the asymptotic rates of Theorem 3.1 and are accurate even for common vocabulary sizes.
4 Scaling laws for sign descent
The dynamics of SD differ qualitatively from those of GD as they take a uniform update in all directions, regardless of the magnitude of the derivatives. As we will see, this makes it better suited for the linear bigram model with Zipf-distributed data, but comes with additional challenges. For SD, need to address two issues. First, the sign descent update is not linear, we need alternative to the closed form solution of GD in Eq. (1). Second, SD does not converge with a fixed step-size; we need scale step-size a function of the iteration budget and dimension.
If run with a constant step-size, the update of sign descent with a step-size of y
W #+1 W, sign( (rsig((L((W.)). VL(W.)).
As the Hessian of Problem 2.1 is diagonal, the update applies independently each parameter. Letting dey (t) be the distance along the (i. (h parameter at step t,
8ty(t + 1) (t) 77 sign(o,,
The difficulty the analysis comes from the fact that (+)( does not converge to Instead, (t) will oscillate between some E (0. 17) and y7, unless = |6:, (t)l/n is an integer and the distance to the solution reaches exactly Keeping track of these oscillations cumbersome, as each of the d² parameters will oscillate between different constants. To simplify the analysis, we assume that the distances decrease while (6,;(0) 2 ly then go to n/ to model the oscillatory regime, essentially "averaging" the oscillations, as illustrated in Fig. 5.
Assumption 4.1. We assume that sign descent with step-size 17 follows the dynamics
[or,(0) tn if (or((0) tn 2 0, otherwise.
(t))(t) =
n/2
7

---

a = 0.25
ar = 0.5
1.0
10a
10
10 22_
10*
d 10
0.5
10 10-5_
10'
d 10
4+
T-
0.0
10
==T
10 10
7:
7:47
10
7: rdd
10a
Figure 6: Convergence of the best step-size for sign descent the scaling Definition 4.4. The optimal step-size for T steps of sign descent converge to scaling (--) given in Defini- tion 4.4 (for in the case of a = 1). Computed by grid search on the linear bigram model with data satisfy Assumption 2.3.
Those dynamics do not capture the fact that a direction might reach exactly O, after which sign descent would not oscillate, but this can only happen for few directions if b;; (0) 1/j%, and their impact small with large d. With this assumption, we have the following dynamics.
Proposition 4.2. If the conditional distribution follows a power law with exponent a as in Assump- tion 2.3, the dynamics of sign descent with step-size y in Assumption 4. leud to the loss
Ca(t,n) -3== - (t) = E6
(66)())=I(60(000
tn)²
Σ
(2)
where 5x Th
k=k++1
and k, is the number of directions in the decreasing regime, k. maxe A TT >
Proof. By Proposition 2.2, Xo5 n; does not depend on j. By Assumption 2.3, there is a per- mutation Pj such that 04p (2) (0) Tj. As result, the dynamies of (1) do not depend on i. Writing (1) as shorteut for (1) for any and using that E 1,
Ag)r(())
Σ m
(1) Σ 8,(1)
We then split the depending whether [x) is decreasing oscillating.
The dynamics of SD in Proposition 4.2, differ qualitatively from those of GD in Eq. (1). The progress in each direction is not scaled by иi because the update uniform across directions. This is what will enable SD to make faster progress on low-frequency words. However, we now have another challenge in that need to choose the step-size 1j trade-off between the oscillations of magnitude (n/2)² on now-frequency words and still making progress on high-frequency words that are not yet in the oscillatory regime. This is easy when small spread for the initial distances 6g (0), but becomes more difficult as a increases. From this, we expect SD perform better than GD for small a, and worse for large o, but need understand how to set the step-size to understand where the transition happens.
small and the frequencies
close uniform, giving
4.1 Scaling of the step-size
As SD with a fixed step-size eventually enters an oscillatory regime, the loss we converge to as t grows depends on 7). To describe the performance achievable after tuning 7 for a given budget T. we need to estimate how 7) scales with 7 and d. This effect is illustrated in Fig. 5 (right). We use capital T to emphasize that a fixed step-size which depends on T. Getting the exact form of reach, but we establish bounds on the optimal step-size.
modeling the loss at the end of a training run of T steps with
arg min, La(T, n) is out of
Proposition 4.3. The step-size ne that La(T, n)) in Proposition 4.2 given T and d, satisfies
5a(0)
(1) T
T n-
Proof. If < 6,(0)/T all directions are still in the decreasing regime of Assumption 4.1 at time T. As long as Tnj < (0),,, increasing the step-size leads to more progress. Similarly, Th) 2 8, (1), all directions are in the oscillatory regime, and reducing the step-size reduces the oscillations.
D

---

a
0.25
= 0.5
10
(2r) (2r)
[+((2))2
1
10a
Relative
10
10
10
10-3
10
10
7=
10"10"
47 dr
10 10
4:
r
10
Figure Scaling of sign descent on power-law data with exponent a (Theorem 4.5). The dynamics of sign descent on the linear bigram model with data satisfying Assumption 2.3 converge to scaling law (- - as d grows, as described in Theorem 4.5, Achieving a relative error requires no scaling for 1/2, scaling with d(1-c//2 for 1/2, and with d for 1/2.
As our initial distances follow a power law, 6x (0) = T&s = = where 2 = Eb_i k Proposition 4.3 suggests alternative parameterization of the step-size
(
with Isosd,
TT
where & controls how many directions still decreasing. We now define the following scaling of Definition 4.4. We define the following scalings as a function of the dimension d and rescaled time
Φa(T) { d
isc + 4027² < 1 othenwise,
ff < 1/2, Ta(T)= =
d(ci= + 40272)-1
if 1/2, Ta(T) 1 da(T) d'=,, where T E [0,
a 1/2, Ta(T) VVd, da(T) { 1+ 1/2
if < -1 and 1,
(1 + 1/12)2/a
otherwise,
where 0 = 1 2a
1-a"
While those scalings need not be optimal, they match the empirical behavior of the best step- size computed by grid- grid-search, as shown in Fig. 6. For a 1/2, the step-size is only accurate for 72 2 1/(2" 1) or 2 for a = 1. We justify those estimates in Appendix D.
4.2 Asymptotic behavior
Using the scalings for I' and á in Definition 4.4, we define the asymptotic rate of sign descent as
La(Ta(T), (a(())((T))))))))))))))))))))) La La
r(7) lim d
Ca(
Theorem 4.5 (Scaling for sign descent). Given scalings for T and di in Definition 4.4, the asymptotic convergence rate of sign descent (Eq. (4)) is, with = Z T-a"
2002
if
1-11 doa
2n
ifa 1/2,
Ta(r)=
r(T)
2 47d
otherwise
A (2T
2-1a
ifa- = 1/2,
Ta(T) = 3dtt
r(r) 1-T,
where + E [0,
if 1/2, Ta(T) f7 Vdd.
r(r) 2 1 C(20)72
We leave the proofs Appendix D. The results also show different forms of scaling depending on a. with threshold at = 1/2 instead of 1. The scaling in dimension is flipped compared to GD. SD needs to scale with d when large, which is the regime where GD can make progress with finite I. For the case of Zipf-distributed data (ax 1), SD only needs scaling in d compared to the d!-s scaling of GD, showing that achieves better performance for & < 1/2. We show in Fig. 7 that the asymptotic rates of Theorem 3.1 are accurate even for finite d.

---

Gradient Descent
GD, Rescaled time
Sign Descent
Relative error
10
2
2 _ 2
2
10
exp( exp(-273
10
2
10-1
10
10
10
10
10
Time
10
Rescaled time
log(t) logid)
10
Time
Figure 8: The difference in scaling with dimension also occurs with the cross-entropy loss. Relative enror linear bigram problem with cross-entropy loss with vocabulary size d when the word frequencies follow Zipf's s law, Fy x 1/k. For GD (left), the performance depends heavily on the dimension. Its performance is similar to the scaling of 7 for t d' found for the square loss while r < 1, and worse for > (middle). The performance SD appears independent (right).
5 Conclusion
We have presented scaling laws for gradient descent (GD) and sign descent (SD) on the linear bigram model as function of the power law exponent of the word frequencies. Rather than hide the dimension dependence in problem specific constants, we consider the scaling of running time and dimension as the problem grows in size get precise estimates of the scaling. Our results highlight the benefit of SD and the need to address ill-conditioning to improve the performance of GD.
Our results show that the power-law scaling is specific to the regime > 1. This regime may accurately describe cases where the training dynamics converge to a well-defined limit, such as when increasing width depth (Yang al., 2021; Bordelon et al., 2024b; Noci et al., 2024), it misses large dimension dependence as we scale the vocabulary size. The scaling we obtain for a S have a different functional form and highlight the dependency on dimension. For GD on Zipf-distributed data, the scaling of d'-e shows a non-trivial interplay between the desired error & and the dimension. Our results suggest that increasing the vocabulary size might require larger training budget, not only because each iteration is more costly due to the larger embedding matrices, but also because more iterations are needed to reach the same error. Algorithms that target this dimension dependence, for example by estimating word frequencies (Li et al., 2022), would be an interesting next step.
Our approach however has limitations. We do not cover the online case, for which the analysis should be extendable using existing tools. The addition of momentum for sign descent would be more complex but particularly interesting to dampen oscillations. and getting dinee--amnsiional results by tracking a correction term for finite d would be enlightening, as the convergence to the asymptotic regime sometimes be slow, especially in the case 1. A more difficult extension would be to consider models leading to non-linear dynamics, such as bilinear models (Mikolov et al., 2013) or the cross-entropy loss. But it is not clear how obtain closed-form solutions sufficiently accurate approximations even for GD in the deterministic setting. We can however probe the behavior of GD and SD experimentally, and present preliminary results with the cross-entropy loss.
Empirical behavior with cross-entropy loss. We experiment with a variant of the linear bigram model trained with cross- cros--enroppy loss synthetic data satisfying Assumption 2.3 for 1. We show in Fig. 8 the result of training models with increasing vocabulary, with the step-size set by trid-search for both GD and SD to minimize the loss the given horizon. The results suggest that the gap in scaling between GD and SD is even larger than with the quadratic loss; GD appears to require & ~ d, in the quadratic case, while the performance of SD appears independent of d.
Acknowledgments and Disclosure of Funding
We thank Si Yi (Cathy) Meng. Aaron Mishkin, and Victor Sanches Portella for helpful discussions and providing comments on the manuscript. and for the feedback from anonymous reviewers. This work has received support from the French government, managed by the National Research Agency, under Frederik
the France 2030 program with the reference "PRIAIJRIE-PSAL" Kunstner is supported by a Marie Sklodowska- Curie Fellowship from the European Union's Horizon Europe Research and Innovation program under Grant Agreement No. 101210427.
10

---

References
Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky (2020). "Hiig-diimensional dynamics of generalization error in neural networks". In: Neural Networks 132, pp. pp. 428-446.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma (2021). "Explaining
Neural Scaling Laws". arXiv/2102.06700)
Lukas Balles, Fabian Pedregosa, and Nicolas Le Roux (2020). "The Geometry of Sign Gradient Descent". arXiv/2002..8805..
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar (2018). "SIGNSGD: Compressed Optimisation for Non-Convex Problems". In: International Conference on Machine Learning (ICMI.).
Raphaël Berthier, Francis R. Bach, and Pierre Gaillard (2020). "Tight Nonparametric Convergence
Rates for Stochastic Gradient Descent under the Noiseless Linear Model". In: Advances Neural Information Processing Systems (NeurIPS).
Blake Bordelon, Alexander B. Atanasov, and Cengiz Pehlevan (2024a). "A Dynamical Model of Neural Scaling Laws". In: International Conference on Machine Learning (ICML).
Blake Bordelon, Lorenzo Noci, Mufan Bill Li, Boris Hanin, and Cengiz Pehlevan (2024b). "Depthwise Hyperparameter Transfer in Residual Networks: Dynamics and Scaling Limit". In: International Conference Learning Representations (ICLR).
Stephen Boyd and Lieven Vandenherghe (2004). Convex Optimization. Cambridge University Press.
Yaroslav Bulatov (2023). Gradient descent under harmonic eigenvalue decay. Blog post. https:// mechine-learningg etc. ghost. io/ gradient gradient-descent-eeeeee sanaccentunder--e har.onnc--eeeenaalee decay-average case- ysis
Andrea Caponnetto and Ernesto De Vito (2007). "Optimal Rates for the Regularized Least-Squares Algorithm". In: Foundations of Computational Mathematics 7.3, pp. 331-368.
Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Hicu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsich, Yifeng Lu, and Quoc V. Le (2023). "Symmoolic Discovery of Opti- mization Algorithms". In: Advances in Neural Information Processing Systems (NeurIPS).
Enea Monzio Compagnoni, Tianlin Liu, Rustem Islamov, Frank Norbert Proske, Antonio Orvieto, and Aurélien Lucchi (2025). " "Adaptive Methods through the Lens of SDEs: Theoretical Insights on the Role of Noise". In: International Conference on Learning Representations (ICLR).
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová (2021). "Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime". In: Advances in Neural Information Processing Systems (NeurIPS).
Rudrajit Das, Naman Agarwal, Sujay Sanghavi, and Inderjit S. Dhillon (2024). "Towards Quantifying the Preconditioning Effect of Adam". 1tXii/24022.01144
DLMF (2025). NIST Digital Library of Mathematical Functions. https: /dmmff nist gov/, Release 1.2.4 of 2025-03-15. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
John C. Duchi, Elad Hazan, and Yoram Singer (2011). "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization". In: Journal of Machine Learning Research (JMLR) 12,
pp. 2121-2159.
Aaron Gokaslan, Vanya Cohen, Ellie Pavlick, and Stefanie Tellex (2019). OpenWebText Corpus. http://Skylion007 wwt.iiiooooooi....iii.i htt...///peeeeeeeeoorrrooo
Thamme Gowda and Jonathan May (2020). "Finding the Optimal Vocabulary Size for Neural Machine Translation". In: Conference on Empirical Methods in Natural Language Processing (EMNLP).
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Ruther- ford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbi, Aidan Clark, Tom Hennigan, Eric Noland, Katherine Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy. Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals, Jack W. Rac, and Laurent Sifre (2022). "An
11

---

empirical analysis of compute-optimal large language model training (Training Compute-Opting Large Language Models)". In: Advances in Neural Information Processing Systems (NeurIPS).
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei (2020). "Scaling Laws for Neural Language Models". Tech. report. arXiv/2001.0836.
Diederik P. Kingma and Jimmy Ba (2015). "Adam: A Method for Stochastic Optimization". In: International Conference on Learning Representations (ICLR).
Taku Kudo and John Richardson (2018). "SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing". In: Conference on Empirical Methods in Natural Language Processing (EMNLP).
Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt (2023). "Noise is not the main factor behind the gap between SGD and Adam on transformers, but sign descent might be". In: International Conference Learning Representations (ICLR).
Frederik Kunstner, Alan Milligan, Robin Yadav, Mark Schmidt, and Alberto Bietti (2024). "Heavy- Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Models", In: Advances in Neural Information Processing Systems (NeurIPS).
Yan Li, Dhruy Choudhary, Xiaohan Wei, Baichuan Yuan. Bhargav Bhushanam, Tuo Zhao, and Guanghui Lan (2022). "Frequency-awarc SGD for Efficient Embedding Learning with Provable Benefits". In: International Conference Learning Representations (ICIR).
Licong Lin, Jingfeng Wu, Sham M. Kakade, Peter L. Bartlett, and Jason D. Lee (2024). "Scaling Laws Linear Regression: Compute, Parameters, and Data". In: Advances in Neural Information Processing Systems (NeurIPS).
Liyuan Liu, Xiaodong Liu, Jianfeng Gao, Weizhu Chen, and Jiawei Han (2020). "Understanding the Difficulty of Training Transformers". In: Conference on Empirical Methods in Natural Language Processing (EMNLP).
Yuxing Liu, Rui Pan, and Tong Zhang (2025). "AdaGrad under Anisotropic Smoothness". In: International Conference on Learning Representations (ICLR).
Chao Ma, Lei Wu, and Weinan E (2021). "A Qualitative Study of the Dynamic Behavior for Adaptive Gradient Algorithms". In: Mathematical and Scientific Machine Learning (MSML).
Sadhika Malladi, Kaifeng Lyu, Abhishek Panigrahi, and Sanjeev Arora (2022). "On the SDEs and Scaling Rules for Adaptive Gradient Algorithms". In: Advances in Neural Information Processing Systems (NeurIPS).
Alexander Maloney, Daniel A. Roberts, and James Sully (2022). "A Solvable Model of Neural Scaling Laws". arXiv/2210.16859.
Tomás Mikolov, Kai Chen, Gregory S. Corrado, and Jeffrey Dean (2013). "Efficient Estimation of Word Representations in Vector Space". In: International Conference Learning Representations (ICLR).
Yurii E. Nesterov (2018). Lectures Convex Optimization. Vol. 87. Springer.
Lorenzo Noci, Alexandru Meterez, Thomas Hofmann, and Antonio Orvieto (2024). "Super Con- sistency of Neural Network Landscapes and Learning Rate Transfer". In: Advances 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: Advances in Neural Information Processing Systems (NeurIPS).
Steven T. Piantadosi (2014). "Zipf's word frequency law in natural language: A critical review and future directions". In: Psychonomic Bulletin Review 21, pp. 1112-113..
Marc Potters and lean-Philippe Bouchaud (2020). A First Course in Random Matrix Theory; for Physicists, Engineers and Data Scientists. Cambridge University Press.
12

---

Jonathan S. Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit (2020). "A Constructive Prediction of the Generalization Error Across Scales". In: International Conference on Learning Representations (ICIR).
Mher Safaryan and Peter Richtárik (2021). "Stochastic Sign Descent Methods: New Algorithms and Better Theory". In: International Conference on Machine Learning (ICML).
Rico Sennrich, Barry Haddow, and Alexandra Birch (2016). "Neural Machine Translation of Rare Words with Subword Units". In: Annual Meeting of the Association for Computational Linguistics
(ACL).
Chaofan Tao, Qian Liu, Longxu Dou, Niklas Muennighoff, Zhongwei Wan, Ping Luo, Min Lin, and Ngai Wong (2024). "Scaling Laws with Vocabulary: Larger Models Deserve Larger Vocabularies". In: Advances Neural Information Processing Systems (NeurIPS).
Tijmen Tieleman and Geoffrey F. Hinton (2012). RMSPROP: Divide the gradient by a running average of its recent magninude. Lecture notes http: /ttp://wwrr hwwp///wwwwee/////////////.../ cs. toronto edu/"ti ttjjmen/ cac321/slides/ http/llccureeeieeeeeeee wwwdddsleeesslleeeeeeeeee .df.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin (2017). "Attention All you Need". In: Advances Neural Information Processing Systems (NeurIPS).
Maksim Velikanov and Dmitry Yarotsky (2024). "Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditions". In: Journal of Machine Learning Research (JMLR) 25, 81:1-81:78.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Breut, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Ker,, Eric Larson, CJ Carey, Îlhan Polat, Yu Feng. Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors (2020). "SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python". In:
Nature Methods 17, pp. 261-272.
Ke Liang Xiao, Noah Marshall, Atish Agarwala, and Elliot Paquette (2024). "Exact Risk Curves of signSGD in :iigh-Dienssons:: Quantifying Preconditioning and Coise-Compn Effects". arXiv/2411.12133
Ge Yang, Edward J. Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu, David Farhi, Nick Ryder, Jakub Pachocki, Weizhu Chen, and Jianfeng Gao (2021). "(Tensor Program V) Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer". In: Advances in Neural Information Processing Systems (NeurIPS).
Yushun Zhang, Congliang Chen, Ziniu Li, Tian Ding, Chenwei Wu, Diederik P. Kingma, Yinyu Ye, Zhi Zhi-Quan Luo, and Ruoyu Sun (2025). "Adam-mini: Use Fewer Learning Rates To Gain More". In: International Conference on Learning Representations (ICLR).
Rosie Zhao, Depen Morwani, David Brandfonbrener, Nikhil Vyas, and Sham M. Kakade (2025). "Deconstructing What Makes a Good Optimizer for Autoregressive Language Models". In: Interna- tional Conference on Learning Representations (ICLR).
Zhenxun Zhuang, Mingrui Liu, Ashok Cutkosky, and Francesco Orabona (2022). "Understanding AdamW through Proximal Methods and "cale-Freeness" In: Transactions on Machine Learning Research (TMLR).
13

---

Supplementary Material
The supplementary material is organized as follows.
Appendix A gives experimental details and information how reproduce the figures.
Appendix B compares our results to standard convergence rates in the literature.
Appendix C gives the main results for gradient descent Theorem 3.1.
Appendix D gives the main results for sign descent Theorem 4.5.
A
Experimental details
This section goes over the technical details of the experiments needed to reproduce the figures.
A.1 Computational complexity
We denote the size of the vocabulary, but the number of parameters W is dl we have to learn the conditional probability table * [j- As the number of iterations t has to scale with dimension, the problem scales in d3, which becomes prohibitive fast. To circumvent this issue, we use the fact that the training dynamics of gradient descent and sign descent on data following Assumption 4.1 can be simulated in (d). The error after iterations can then be computed in closed- form if initialized at 0, making it possible to compute the loss after / steps without computing the intermediate steps.
Proposition A.1 (Reduction of the dynamics for gradient descent). Under Assumption 2.3, the dynamics of gradient descent with step-size 1/T2 can be computed in ((d)
ra(t) = La(t) L3 La(0) C Ek=ik
d
1
k
ka
k=
Proof. We use the dynamics using the eigendecomposition notation presented in Section 2,
ra(1)= = La(1) f3 {g) and 8,, - 2
Using Assumption 2.3 gives that Xuj is independent of j and dıj independent of
1
1
Xig n.
(1) pp)ss
where
270
zja
ka
k=1
Plugging in those together and using that the step-size is 1/2 gives
Lall) - C2
d
21
(0)(2)2
Cx(0) - C2
Σ
2j=1
21
(0)
21
(0)2
Ed Di=1
E 1
(1)
E
Proposition A.2 (Reduction of the dynamics for sign descent). Under Assumption 2.3, the sim- plified dynamics of sign descent (Assumption 4.1) with step-size n(T, = 1/2T following the reparameterization of Proposition 4.3 where = Ed=nke k- can be computed in (d)) as
(T(T, = La(T, (T, 6)) - -
d
(T- -10 otherwise,
(0) -
Σ1
12a
k=
2
Proof. Using the same derivation as above for Proposition A.1 but using the update dynamies assumed in Assumption 4.1. Note that those dynamics imply that diy (T") is independent of i. Writing A,
14

---

(T) for any and using that Σ n5 = 1, we have
La(T) - Ca La(0) Ca
Di= (T)
S (T)
E 4T
E En ) Σ CE (0)2
Expanding (T) using Assumption 4.1 gives the result.
For the real data experiments in Fig. 2, computing the dynamics cannot be reduced to O(d). We still use the fact that the dynamics can be computed in closed-form avoid running steps of gradient/sign descent. For sign descent, we do not use the simpler model of Assumption 2.3 but the full dynamics by computing the point reached after steps, including oscillations.
Proposition A.3. Under the dynamics of sign descent with step-size y)
6tg(t + 1) = 6t)(t) (t))
the distance after steps is given by
dig (0)
nt
ift S switch.
T Twiich
= [6:5(0)/m], Cij 6,y(0) T sw
81y(1)
Cij
ift T switch is odd, if switch is even,
where
n
A.2 Additional details about the figures
Fig. 1 shows the dynamics of gradient descent Problem 2.1 on data satisfying Assumption 2.3.
Fig. shows the dynamies on real data on the Open WebText dataset (Gokaslan et al., 2019). Using the SentencePiece (Kudo and Richardson, 2018) implementation of BPE Sennrich et al., 2016, we train tokenizers with vocabulary sizes of 1 0000, 3 612, 10 000 and 31 622 tokens on the first 2 000 000 entries of the dataset with maximum sentence length of 16 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 ((d) computation detailed in the previous section to avoid having to run gradient and sign descent on those large models.
Gradient descent uses the empirically-derive step-size of 1/m For sign descent, for a given time horizon T, we optimize over the step-size numerically. Because the loss after steps as a function of the step-size is unimodal, we use the default bounded bracketing method in scipy (Virtanen et al., 2020, bounds derived in Proposition 4.3. The optimal step-size can vary drastically if it is computed on even or odd iterations as the loss oscillates. To avoid this issue, we only show even iterations.
starting with the interval [Mmin/ ddmmax] where minn Mmax are the
Fig. 3 shows the frequencies computed as for Fig. 2 for the largest vocabulary size, d = 31 622.
The rightmost plot of Fig. 5 shows the simplified dynamics of sign descent.
Fig. 4, Fig. and Fig. show the convergence of the loss in dimension computed using the equations in Appendix A. For sign descent, the hest step-size is obtained by grid search. We know the optimal step-size satisfies & E [1,4] (Proposition 4.3), so let á d where x comes from a logarithmically spaced grid-search on from - 10 to 0, taking every 1 1/32th powers;
Ed E {10 10 10000-10 10+ ,2z 10 10+ + 109)}.
Fig. 8 shows the dynamies of GD and SD on the linear bigram problem trained with the cross-entropy loss. For both GD and SD, the step-size selected by grid-search with a similar 1 1/32th power logarithmic grid above, to minize the loss after steps. As for the plots of SD, Fig. 8 does not show a single run but the envelope of the performance achievable with constant step-size for T steps. We have not found way simplify the computational complexity of the experiments using the cross-entropy loss. Each run requires running GD or SD for steps on the full d x matrix. As t needs to scale with d, computing run of GD SD takes O(d3) time, which limits the vocabulary sizes we can consider.
15

---

B Comparison with worst-case rates
In this section, we compare our rates against results obtained using classical analyses to highlight the benefit of the asymptotic analysis in capturing the dependence on dimension. Our goal is not to imply those bounds are poor; each of the work cited below studied a specific problem and the assumptions were selected to highlight the impact of the condition number, non-convexity, variance, or other issue. However, due to their worst-case generality, existing results do not capture the dimension dependence on the problem of the linear bigram problem (Problem 2.1) with Zipf- distributed frequencies (Assumption 2.3) and predict worse behavior than actually observed.
In this section, we focus on Zipf-distributed data (a 1) it the most relevant to text data. To simplify notation, we assume that the conditional frequencies directly follow power-law | X 1 1/k, instead of assuming that there exists a reordering p; such that (k) Is X 1/k as Assumption 2.3. This reordering does not affect the dynamics of the loss and can be ignored without loss of generality.
B.1 Standard smooth, (strongly sstrongly-Jconver rates.
Classical results in smooth, convex optimization are derived under the assumption that the objective function La is L-smooth and j--ttrongyy convex with μ 2 0. We write the function rates in matrix form for the loss La defined in Problem 2. but this could equivalently be transformed to vector form using and ||x - x. 1 = W - W. 11 x = vec( () and x, = vec( (W.) .) where vec stacks the columns of W as single vector. For difeediifferentialle function, this is equivalent to assuming that the eigenvalues of the Hessian are bounded by S X13 S for all i,j E [d] at every possible input. We compare against simple forms available in this setting (Nesterov (2018, Cor. 2.1. Boyd and Vandenberghe (2004, Eq. 9.1)).. While it is possible to slightly improve the constants in these bounds, these constants do not meaningfully affect the asymptotic behavior grows.
W - 1.
Calt) C (1 (1- -1- 1) (Ca(0) Ci).
Ca(t) c2 S
To better compare these rates with our results, we normalize them by La( -f'y.
Ca(t) L' L| W Ca(0) - C3 ((C((0) - (3)
raa (t),
Ca(0) - L3 $ M rd (t).
Ca(t) Cj
rd
Proposition B.1 (Values of the constants). On Problem 2.1 with frequencies following a power-law with a = 1 (Assumption 2.3) initialized at Wa = 0, the smooth convex sublinear rate rad (t) and the smooth strongly-conver linear rate r (t) are asymptotically equivalent to
1
1 (1-2) d
sub (t) 2 2
r (t) A
log(d) t'
Proof. The proof follow from substituting the constants with the values
11
L
I. 1 d(Ca(Wo) L.).
dz
where: 2 = Σi=
k= 1/k A log(d). The eigenvalues are λi = म, = 1/2i after normalization, giving
L == 1/2 and / 1/2d. Using that (0) = 1/2j gives the loss and distance at initialization,
Co(Wo) C2
X (0)
Σ
T
zj
i=
i=1
j=1
d
d
IWo W.1 = Σ
(0) = d Σ
d( (Wo) - Ci)
Both rates struggle to predict the progress "early" iterations, when / much smaller than d. The sublinear rate requires scaling 1 x d//og(d) while the linear rate predicts i x d. Neither captures the progress that can be made by running / = /d1/2 iterations, which reaches an error of = 1/2. Instead, both rates predict no progress. We visualize the given rates in Fig. 9 after rescaling the number of
16

---

Standard rates
Standard rates (log scale)
Relative crror
Relative
Linear
Sublinear
d 10a
d 10
d 10
... d=
d 10a
... d= 10
d 1016
d= 1016
0-
10
l0z(!) log(4)
Los(t)
[og(4]
Figure Standard convergence rates do not capture the scaling dimension. Comparison the standard linear and sublinear rates obtained for GD on the linear bigram model with dipf-distributed data (a = 1) with our asymptotic rate. The sublinear rate predicts relative error greater than 1 until t z d, and the linear rate only reach the error 1/e at t d. Our rate captures the fact that GD makes progress even with t < d.
steps to our normalized time log(()/)og(d), The linear and sublinear rates are not converging to r(r) = 1 - т. Instead, they exhibit sharper and sharper transition between not predicting any progress for < (r(r) x 1 or r(r) > 1) and that the problem is solved if r >>> 1.
B.2 Rates for sign descent
Analyses on sign-like methods in the literature typically target more complex algorithms such as RMSProp (Tieleman and Hinton, 2012) or AdaGrad (Duchi et al., 2011) 1) for Das et al. (2024) and Liu al. (2025), or consider more general problems including non-convex functions for Bernstein et al. (2018) and Safaryan and Richtárik (2021). We not aware of existing analyses that specifically target sign descent on diagonal quadratic problems such as Problem 2.1. This makes direct comparison difficult. It might be that the rates described in those papers for the chosen problem setting or algorithm are tight. However, our message is that the resulting rates are too pessimistic even for problem as simple Problem 2.1 and suggest runtimes for sign descent that are off by factor depending on the dimension.
The main difficulty in studying sign descent and sign-like methods more generally is the strong dependence on the coordinate system used, For Problem 2. the dynamics perfectly separate along coordinates which makes it possible to derive a closed form for the dynamics. Other works typically rely on assumptions on the Hessian that quantify how close to diagonal it is. For example, bound the Hessian with diagonal matrix L, H < L in Loewner ordering, and obtain rates that depend on the trace of L (c.g., Bernstein et al., 2018 8; Liu et al., 2025). For Problem 2.1, the Hessian is diagonal and Diag([m [T1, .... Ra)). thus Tr(L) Cr = d.
made of d diagonal copies of X X
Anisotropic smoothness and AdaGrad. Using this assumption, Liu al. (2020, Theorem 4.1) show the following convergence rate for AdaGrad. To simplify their results and show the rate in its best light, we assume there is no noise in the gradient [| = 0 in their notation), that AdaGrad is run with the parameter 0, that the algorithm is run with projections onto the constrained set W (W: [[]] I m and that we initialize at W 0.
La(t) L3 Tr(L)=i
Normalizing the loss and simplifying the constants using the same approach as in Proposition B.1 gives the following asymptotic upper bound
Ca(t) C2 < r (1) T(Cx(0)- - T n (0) L;
Tr(L) A dlog( d)
Adagrad
Although we might expect Adagrad to outperform sign descent as it uses decreasing step-sizes to avoid the oscillations, this rate estimate that the number of iterations should scale with d log(d) instead of the scaling of df we find for sign descent.
17

---

Preconditioning effect of Adam. Das et al. (2024) study RMSProp. or Adam without momen- tum (3, but with momentum on the moving average of the squared gradient. They use high-probability arguments to handle the dynamics of the preconditioner and random initializa- tion. Their rate shows that Adam can perform better on diagonal quadraties if the condition num- ber scales worse than linearly with the dimensionality, by replacing the condition number K with RAdam = min(dw + 1, k} where dw is the dimensionality of W. Assuming that their bound holds with probability 1 with Wo 0 and ignoring logarithmic factors in d and e, their rate for diagonal quadratics (Das al., 2024, Thm. 2)
2²
(a(t) La 2
after
t (K
Unfortunately, Problem 2.1 the dimensionality is dw de while the condition number scales as A with Zipfian eigenvalues (a = 1) so the proposed approach does not improve over gradient descent. Normalizing the loss and using the same approach as in Proposition B. gives
Ca(1) C2 (a 2 2
after
2 ((d)
This scaling predicts the same performance for Adam and gradient descent (up log factors depending on d and that we ignored) whereas our analysis shows scaling of d2/2 for sign descent.
Non-convex results. Results in the non-convex setting (Bernstein et al., 2018; Balles al., 2020; Safaryan and Richtárik, 2021; Liu et al., 2025) 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 | < [ for a d-dimensional vector v, the time required to get the 1-norm small might be much worse than the time required to find stationary point in Euclidean norm or to minimize the function value. To illustrate this point, we show that it is possible to have arbitrarily small relative error on Problem 2.1 and arbitrarily large gradients in 1-norm in high dimension.
Proposition B.2. On Problem 2.1 with Zipf-distributed data (Assumption 2.3 with = 1), SD with simplified dynamics (Assumption 4. I) with La(T) = Td-12/2 and (a(T) (1 1 satisfies
La(We L
vec VCa A log (d)r
d=/2
A
+
Ca(Wo) - C
I+ ((2a)+2'
vec VCa(Wo))
Proof. Computations similar to Proposition 4.2 show that the 1-norm of the gradient is
(iveoVLCa W.)) = [ - bn) +
Σ
2
7
2
k=k.+1
where k. is the number of directions that are still in the decreasing regime after steps with step- size As |/vec(VL Σx= 1, this expression is also the normalized I-norm of the gradient. Using the parameterization 7) = 1/2ld, where 1 we get the update
||vec(VZL(W:))) ra(()= = [ive VL. (Wo))
[d]
1
zki
2Φ
21z
k=1
km [+b]
++1
Using the same scaling as in Definition 4.4, da(() = (1 + 1/72)-1 and 2ta(T) = 1/2 we get
H1,()u(7)) log(d)
[da(T))
d- [Qa(T)] -1 d'
ra(ta(T))
(og(d)(a(T) log(d)du(T)) (ta()))ta))))) log(d) - 73
L
While getting a small error only requires scaling t with d²/2 getting the magnitude of the gradient in 1 n-rorm smaller than a constant independent of d requires scaling i with d/ log(d).
18

---

C Proofs for gradient descent
This section gives the proof of Theorem 3.1 for the scaling of gradient descent.
C.1 Standard results
We start with standard results that are used the subsequent proofs. The following classical relation- ships between sums and integrals of monotone functions will be used to bound the approximation error induced by analyzing the asymptoties of the integral instead of the sum.
Lemma C.1 (Sum-Integral), For a function f that is monotone on (a, b).
b-1
E1(0 - S"" f(1) dk & Σ f(k),
if f is increasing on |a, b).
1=a
Σ f(k) $ [[ f(k) dA Σ f(k) i=++1
b-1
if f is decreasing (a, b).
To apply these sum-integral relationships to the dynamics of gradient descent in Theorem 3.1, we need to describe when they are increasing decreasing.
Lemma C.2 (Unimodal sequence). The sequence s(k) (1- is non-negative on k 2 1 and unimodal. It monotonically increases until k. (1 + t)1/a, then monotonically decreases.
Proof. As skk is non-negative, we can instead look at its logarithm,
log (A:) log(N) log(k) tlog(1 1 k))
i
log skk) at n k-a
at k(ka 1) k k(ka 1)
a(t - 1)(k1) -
Ōk
The denominator positive on 2 1, and the numerator is positive for small until the derivative changes sign at at - a(kaa - 1) = 0, or k. (1 + 1)1/2.
I
At the partial sum Háoo = - k appears proof gradient and sign descent, we give its
asymptotic behavior independently.
Lemma C.3 (Normalizer Asymptotics). As d grows, the partial sum Há,a =Et= ka behaves
Há,a &
if if
Ha, log(d)
Haa A ((a) af
where Ç is the zeta function, defined as the limit of Ha, ((a) E k-a < xc for a > 1.
Proof. For a >> 1, the sum converges to Ex= k- ((a). For a S 1, the sum diverges as d grows. As the sequence k- decreasing in we can use the sum-integral bounds (C.1) get a
d+1 k
<1+ 1 dk
ak <
k=1
If 1, the integrals evaluate to
((d + 1)1-
(d) (di-a-1) - +1 k-a
Σ
1-a
k=
and both terms asymptotically equivalent to d= /(1 a) as d oo. a 1. this gives
log(d dl + 1) <
k- < log(d) +
Both terms are asymptotically equivalent to log(d).
19

---

The main purpose of the sum -nteiiaerall bounds (C.1) and the Unimodal Lemma (C.2) is to bound on the error incurred by approximating the sum with the integral form of the loss.
Lemma C.4 (Approximating error). The approximation error between the following sum and integral,
d
Td(1) = [ / s(k)dd
Sa(t)=
Σ
(k))
where
s(k) = h: a0 k kaya
1=1
can be bounded by the following error term,
21
if + 2t S d²
[Sa(1) Ta(()] 5a(l) where 8a(1)=
I+t
1+26
(5)
1
if + 21 da
Proof. By the Unimodal Lemma (C.2), the sequence s(k) is increasing until k, (1 + 2emt) 1/a then decreasing, which lets us use the sum-integral bounds (C.1).
For large t. Suppose that is sufficiently large such that k. 2 d and 1 21 da meaning that the sequence slk) is increasing on [1, d]. Then,
[ (k) + +1) S Σ s(k) S J s(k) + s(d).
d
Using that s() 0 gives [L(t) - (t)l S sd) when t is large.
For small is small and k. < d the sequence flips from increasing to decreasing on [1,4] d]. We still use the same idea, but bound the increasing and the decreasing subsequences separately.
Upper bound. As the sequences skk) in increasing on [1, k.] and decreasing on [k.,d] d].
1-1-11
[k.]] s(k) dk;
Σ s(k) S f (d
Σ
s(k) S
k. sk))
k= k= +2
Summing both bounds and adding the remaining terms s( ki 1), s(1ki>|
1: + 1).
[ s(k) S s(k) dk + ftd s(k) dk + s((b.)) + s(Ib,) + 1) S / n
s(k) dk + skk))
[k. 1+1
where the last inequality uses the following simplifications.
min[s([k.J])) 1), s( [s.] + 1)} IR-1+1
|ko s(k)dk,
min(s((k.])) s( s(1ka] + 1))ck <
|K-]
[k-]]
max(s([ s( (( [.]] + 1)} S skk.).
Lower bound. Now using the lower bound.
[k-]
[
fr
s(k)
dk & Σ s(k),
J s(k) dk <
Σ s(k).
2m
k=
Summing both bounds, we can complete the integral by adding and subtracting [ adding the remaining terms s(1) and s(d) to obtain
[R-J++1 s(k) dk and
s(k) /.
s(k) dk //a
|k.1+1
s(k) dk + a(1) + s(d) 2 1" s(k) dk dodddk-sk)))))). s(d),
[k_]]
where the last inequality uses that s(1) 0, sk) < s(k:.). Combining the results for the small t regime gives
La(t) + s(k.) 2 St) 2 La(t) - s (kt..) ) + s s(d),
so [a((t) Sa(t)) S s(k.).
The final bound in Eq. (5) expands s(z) - o (1 a and replaces k. by (1 + 2t)
20

---

C.2 Scaling laws for gradient descent
are now ready to move to the proof of Theorem 3.1, for which we recall the theorem statement.
Proof sketch. We first give a sketch of the proof, which will be formalized the next lemmas. Based on the reduced dynamics for gradient descent in Proposition A.I, we know that
La(t) L > (o) L
k a k a))
(1(
Hd,a
where Ha.a = Ex=n a Let Sa and la be the sum and integral variants of the denominator,
d
Ia(t) = 1 k (1 - R: a dk.
Sa(t)
Σ
k 01
k
1=1
First, we establish in Lemma C.5 that the integral form converges to the rate r(T) in Theorem 3.1,
Ia(ta(r)) r(r). d
lim
Hd,
Next, we show Lemma C.6 that the error incurred by approximating the sum Sa by the integral La is negligible, in the sense that [L((t) - Sa(O) z da(t) and
lim )a(Lu(T)) d Ta(ta(T))
lim lim 8a(1)
if S 1,
and
i 1.
700 d=v00 Ia(t)
This gives the results that r(T) lim Ia(ta(T)) d0000
r(t) ~ lim Ia(t)
if 1,
and
if > 1.
Hd,
Ha
with the values of r(T) given in Theorem 3.1.
21

---

Lemma C.5 (Asymptotics of the integrals). Let [t(t) be the integral form given in Eq. (7) and ta(T)
be the scaling given in Theorem 3.1. The following limits hold.
Ta(ta(t))
a
(g(T) 1 a E
Ifa <
ta(T) rd"
lim
d-+00
Há
r+1
Ia(ta(T)) =1-r where T E [0. 1|.
fa=1,
tu(T) dd"
lim
d
Ha,
la(ta(T)) B(1 1,1422) 2t) a((a)
faz1, 1,
tu(T) T,
lim d
C -1
La(0),
Ha,
Proof. For a > We use the change of variable k- to get
Ta(1) 1 0 (1 22
As + oo, the integral converges to definition of the Beta function
[ z 21--2)² dz B
- +2
lim ala(t) d=+20
1+2
a
As lima-t Haa ((a) < oo (Lemma C.3),
La(t) B(1 1 1,,11112 11 Hdoo
lim
a<(a)
As is not easy to intuit the rate from the Beta function, we give an additional asymptotic equivalence for large f. Using Stirling's formula, the Beta function behaves as
B 1
a 1 +1
-2 2 r
1 a
(2t) (2t)--a
For a we use the change of variable : = 2tk to get
La(t) _ (2t) f
2
2 2
21
de.
2t
To have a well-defined integral, we need to introduce the scaling 2ta(T) = rd
1 dd
2 rd
Ta(rd"))
dz.
rd
The factor of l' will cancel out with the normalizer as Hd,a remaining integral should simplify for large d, as (1 2/ 2/Td²) )rd"
= (d (c) (Lemma C.3). The
~ c and converge to
2 md dz = T
lim To d0000
e d: ====E (T).
where Ep is the generalized exponential integral. To swap the limit and integral, we can verify that the dominated convergence theorem applies. The integral can be written as
t 2
ad = [ ((z, where a(z, d) [2ggra))
7d"
2 rd
1
T
The integrand a(2, d) converges pointwise to f(2 = z - - and dominated by f which is
integrable as f f(z) = -- E (T). Combined with the fact that Hd a d! al-a 1-/// /(1 - a)), we get
Ta(rd
1 1
lim d
(T)
Haa
a
To simplify for large and obtain (Tya(T) 2 E we use the fact that the generalized exponential integral E2(2) in decreasing in p. meaning that ELy.. > By,(T) Epyo and that for
22

---

integer values of we have 7 S ET(T) S E /+nn-1 (DLMF, $8. (8x1).. Both bounds are asymptotically equivalent +T+1..
For a = we use the change of variable k: == d or 2 = (oga(kk) to get
Ia(t) = log(d) / (1 - d= =2 dz.
The normalizer scales Há,a A log(d) (Lemma C.3) so only the integral remains. To make meaningful progress, we introduce the scaling 2tx(T) = d' for E [0,
d' dr
Ta(d")
dz.
log(d)
As + co, the integrand converges to & E (0,s) and to if 2 E (s, 1), and dominated by f(x) so by the DCT we swap the limit and integral to get
lim Iald") lim d=000 Ha.
(111- d"
d=
d"
f." Odz + [ 1dz = 1
de dz=
d=000
Lemma C.6 (Approximation error is negligible). Let da(l) be the upper bound on the approximation error derived in the Approximation Error Lemma (C.4). We have that
lim balta(T)) 0 if 1 Ia(La(T))
82(t) Ia(l)
and
lim
lim
0 if 1.
Proof. Recall that the bound approximation error 8 Approximation Error Lemma (C.4) is
if + 2t S d%, if 21 d
(Sa(t) - Ia(t) & 6x(t) where 5x(t)= =
1+28
14.28
For a > 1, does not scale with d so we are in the small t regime, 1 + 2t S d In this regime,
21
1
(t) = 2t +
2t+1
2t
The error 5a(t) does not vanish with d, but it goes down as O(1/t). As the integral Ia(t) is of order ((1/(==4] 2), the relative error is of order O(1/t²), ), and vanishes for large
For 1, we scale with d 21 rd. Whether is small large depends on r. If < are in the small regime as 1 a < d and
1
(1-
Td"
6a(rd")
Tdx + a
If 2 we are in the large i regime and
da(Td") = 1
( dn
do
In both cases lima- 8a(Td*) + 0 and the relative also vanishes.
For a we scale t with as 2t d' for T E [0, 1]. Taking + oo puts us the small regime, 1 + 2t + d' d. In this regime,
d' +1 (1 (1- dr +1
ba(d')
S d
which also vanishes with d.
23

---

D Proofs for sign descent
This section gives the derivation for the scaling of time and the step-size for sign descent given in Definition 4.4 and the resulting asymptotic convergence rates of Theorem 4.5, Each result start from the relative loss defined as follows.
Definition D.1 (Normalized loss for sign descent). Let Ca(t. be the loss after with step-size the repurameterization of the step-size derived from Proposition 4.3. The relative loss after T steps of the simplified sign descent dynamics freqeeeess as Assumption 2.3 is
as defined in Proposition 4.2, and (T,, 6) = a/
on Problem 2.1 with power-law frequencies
TT(T, = La(T, (T, 6)) -23 111.20 -2H 201 o + L 20 +
d 16l
47 Φ
20
Ca(0) 22
Hd,2a
where Hn.p - -> P.
Proof. Starting from Proposition 4.2 and using the fact that, if Φ [1, d). the number of components in the decreasing phase of the simplified sign descent dynamics is [Ø]], , we expand the square and replacing the sums by H n.
Ek= (k ( x--0² + =k== 101+1 27
+0
+E
ra(T, 6)
Σk=l k2a 20
Ek=l k- 2k- 20 + -2a
d- 2a
47 Ø
Σk=1 20
H [01.2n 2H 1o).00 aa + 1010
+
d-1Øl
0
17
H4,20
Our rates are given for a choice of scaling of the step-size @u(T) and time Ta(T),
r(r)
lim ra(Ta(r).du(T)) d=+00
D.1 Scaling of sign descent for 1/2
Proposition D.2. For the relative loss defined in Definition D.I, if 1/2, the scalings
Ta(T) = 1
Φa(T) d'--
are obtained by setting )a(T) = d2 where x xT( is the solution to [T) arg min lim ra(Ta(r),d") 0crg1dms
These choices result in the scaling r(r)
Proof. We start from the normalized loss given Φb
ra(T, Ø) Hjjj1 2H (o), - 1
d
37 1
Ha,1
Taking 2 d= and Φ = dl-T, most terms vanish as d + 00 as Hn, ~ 2 Hn.1 log(n), and
2H dd 11-r1,2d p
d (1-r)
dl-r d=1
Har are all θ
and converge to
Haı
Haı Ha.
log(d)
The first term is the only one remaining. and gives the scaling
H| lim
ifl-faa otherwise.
lim ra (Td)
lim d+o0
d+000
Нa
d
The optimum is x7) and gives r(T) lima rr(T(d,))),d =1
24

---

D.2 Scaling of sign descent for a < 1/2
Proposition D.3. For the relative loss defined in Definition D.I, if < 1/2, the scalings
d <a(T) pd(T)= - d(a + c2472)
if
1-61
Ta(T)= =T,
402
otherwise,
where 0j = 1 2a
and 02 a-I are obtained by setting du(T) dr=(T) where
x. (T) arg min lim ra(Ta(T), dz).
0<a$1d-r00
These choices result in the scaling
r(r) -
{
2002
if
if S V
1-61
lc2
~
2n
1
(27)2-4a* 4a
otherwise
Proof. Substituting & dd, taking the limit as d - co, and using that Ha.p
dl-y for < 1,
I-p
define (x) as the limit of ra(T, dx) as d grows,
H H|dz].20
2H (dx) + [dx)
+ d- d-Ide] (dr) 20
f+(x) = lim ra(T, dx) = lim d=o00
4rd
d-+00
Ha,aa
2 I-o
1---000 + x--2a
2a
172 1-30 1-20
1-20
1-20
We will show that our choice of step-size corresponds to taking r(T) = minoses1 fr (x). Gathering terms, fr fz) proportional the following polynomial
(+)
x² 1-20 20 (1+ 1--20
2
472 x² 2a
20
472
which has a unique stationary point at
2a 47 (1 20x
1
Tatas (T)
172
+ 1-2a
2
1-a
1
47
2xx
a
If (T) & (0, 1], we know the function f is decreasing on [0, 1] as lim fx = oc, f1) is finite, and there is no stationary point in (0, 1)). r(T) = (1). If the stationary point is in (0, 1]. it the minimum as fr must be decreasing from to Tstas (T). This gives
x= = min f+(x)= = Ustat (T)
0 < Istat S 1, otherwise.
and 0 < Istat (T) < is equivalent T V
1-a
If T 2 2/
and x. (T) = 1, we get
20
2a
2a
a²
fx = =1 1-c
+ (1 - 2a) = 2
1
I < 2 2a
I- and (T) = (1-
2a
1
+ a 47
-1
we get
(T) = (1- - 2a)
1-220 1
1
+
1
-20
1 - 2xx
1 1-a
472
47
(1
- 1-
2a
+
2a
472
2a
which can be simplified for large fr (T)) x (120)
(
25

---

D.3 Scaling of sign descent for & > 1/2
For a > 1/2, the expression for the loss does not simply as + oc. The conditional frequencies decay fast, meaning that most of the loss comes from the few high-frequency words. As result, cannot define the scaling of the step-size as the minimization problem for the optimal scaling in the limit d + oc. Instead, we use the fact that the (normalized) loss can not converge to 0 unless all components enter the oscillatory regime, at which point we can compute an optimal step-size.
Proposition D.A. For the relative loss defined in Definition D.I, if 1/2 and 47 - the optimal-step size is given by
d-1 1/a
Φ- (_ T) = arg min minnaa(TTo) 1
472
This gives the following scaling for 72 1112--1)
1/a
Ta(T) = =22
((T) = 1+ 72
r(r) = ((2a) 1 + 72
Proof. If Φ 2 2, the normalized loss is lower-bounded by the error on the first two components,
(T, x)) E (k- x x0²a²² + Ek=10l+1 27
Hayza
This is progress by running longer unless Φ < 2. only the first component oscillating, the optimal ø
by constant C > 0 independently of T, and implies that we cannot make
e. (d. 7) = arg min ra(T (T, Ø)) = arg min の 0² + d
472 Φ 20 = (1+ d d-1" 1/a
472
To be consistent with only having two components oscillating, this requires (o, T) S 2, giv- ing the constraint that this only holds when (1 + ) 2//a < 2 47 d-1 Taking the scal- ing 4Ta(7)² = r gives the limit
1 1/a lim o. (d(T)( = (1 (1+
1
((r)
if
72
d
2a
and the asymptotic loss
(1-6(7)-a)) o(T)) = (1 + 1 (2) 2a
lim d=
((2a)
1 (1 + 2/2
2
+ (1 #
((2xx)
1 1 72 ((2a)
where Ha,za A <(2a), the Riemann zeta function.
Proposition D.4 and Theorem 4.5 only gives guarantees for the regime >²> -1). The extension of the scalings to the regime ?2 < 1/(2"-1) was decided arbitrarily to fit empirical data. To fit the empirical the empirical data when both and are small (a < 1), the asymptotic scaling presented Theorem 4.5 uses the following step-size scaling
((7) {
#1++) (1 21+ 1/a
if < (2 1) and a < 1,
(1
1
instead of
1
otherwise,
72
and the following approximation for the loss,
1
1 1
(() Td 1+ ((20)72
instead of
+ 72 ((2xx)
Both expressions are asymptotically equivalent as + oc and t + co, but the above proposals (given in Definition 4.4) fit the observed best step-size and loss scalings better.
26

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claim of the abstract outlined in Section 1.1, which gives an overview of the results of Theorems 3.1 and 4.5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations discussed in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
27

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The problem setting and main assumption are given in Section 2. The sketch of the proof for the main theorem given in the main paper after Theorem 3.1 for one case, and the other cases are describe in Appendices C and D.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The experimental details are described in Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
28

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: The code available in the supplementary material. The data used is freely available and the experimental details are given in Appendix A.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips.cc////c//// wttp:ccccppccccceeeeeeeeeeeecece heabbiigguides///eeeeeeoeoeeseet httee//uudeee/eeouuuuuisseeessse (oodeeubmissiooooooooooooo
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
The experimental details are given Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
29

---

7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The experiments in the paper are deterministic.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
bars, but should state it. The authors should
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification:
The experiments in the paper are lightweight and did not require the use of high performance compute resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: h/w///eursp...// hptpblic//thhssuiideeee.
Answer: [Yes]
30

---

Justification:
The research conducted in the paper conforms witht he NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
The focus of the paper is on mathematical description of the convergence rate of optimization algorithms. While this theory improves our understanding of optimization algorithms and could lead to developments that make it easier develop machine learning models, we have not identified a societal impact relevant specifically to this work.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not release data or models.
Guidelines:
The answer NA means that the paper poses such risks.
31

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The assets used are described in Appendix A.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www.coo/////oo//o com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not introduce new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
32

---

Question: For crowdsoureing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve human subjects and no IRB approval is required.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core contribution of this paper does not rely on LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to LLM policy for what should or should not be described.
33


Reviews:
[{"review_id": "1sOOUcdyVx", "reviewer": "Reviewer_pUyz", "summary": "This paper provides a theoretical analysis of why vanilla gradient descent (GD) slows down while Adam-like \"sign descent\" (SD) maintains performance when training embedding layers of language models with Zipfian token frequencies, using a tractable linear bigram next-token predictor with squared loss where both unigram and conditional distributions follow power laws π ∝ 1/k^α. The authors derive closed-form optimization dynamics for both GD and SD, establishing scaling laws that show the number of iterations t needed to reach fixed relative training error ε scales as d^α for GD (nearly linear in vocabulary size d for the realistic Zipf case α=1) but only as √d for SD when α≥½, yielding a substantial √d versus d^{1-ε} speedup advantage for SD over GD in the Zipfian regime. Through validation on synthetic power-law data and real OpenWebText bigram statistics, the analysis formally demonstrates that Zipfian spectra represent a \"worst-case\" scenario for gradient descent and provides theoretical justification for the empirical observation that Adam outperforms SGD on large-vocabulary language models.", "questions": "- Training language models uses softmax cross‑entropy, not squared error. Do the scaling exponents change when the loss is replaced by cross‑entropy on the same linear bigram model? A short derivation or experiment would clarify applicability.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Rigorous asymptotic derivations, with proofs sketched in the main text and deferred to appendices.\n- Paper is well organised: assumptions ➔ theorems ➔ figures ➔ discussion\n- Extends classical spectral‑decay analyses, which assumed α>1, to the heavy‑tailed case and to sign‑methods.\n\nWeaknesses \n- Core proofs rely on strong simplifications: squared loss, linear model, deterministic GD/SD;, momentum and cross‑entropy are ignored.\n\n- The key SD analysis rests on Assumption 4.1 (replace oscillations by a constant η/2), whose correctness is argued only heuristically.\n\n - Because the model is linear, direct impact on full transformer training remains speculative.", "was_revised": true, "final_justification": "I thank the authors for the response. \nI have also read the other reviewer's comments. Overall i would keep my borderline accept rating.", "rebuttal": "# General response\n\nWe thank you for your efforts in this review and for the constructive feedback that will improve the paper. \n\nMultiple reviewers raised points regarding the simplicity of the model. We start by addressing those before answering your specific questions. We invite you to read the response to the other reviews for more information on the following points.\n- [Response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys): **Cross-entropy loss vs. squared loss**  \n  Capturing the dynamics of optimization on the cross-entropy loss is not possible, but experiments show that the performance gap between gradient descent (GD) and sign descent (SD) as $d$ increases is similar.\n- [Response to Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp): **Averaging oscillations with Assumption 4.1 and Adam vs. sign descent**  \n  SD is a simple proxy for Adam, but does capture the main benefit of a better scaling with $d$. Experimentally, Adam performs better than SD and also scales better than GD in $d$.\n- [Response to Reviewer 8S6d](https://openreview.net/forum?noteId=Ezuh3XcjFB): **Relation to prior scaling laws**  \n  The main novelty of our approach is on the scaling of $t$ with $d$ to derive a scaling law for GD when the difficulty of the problem scales with $d$.\n- [Response to Reviewer 9d42](https://openreview.net/forum?noteId=3xCuAZLexY): **Axis-aligned model and sign descent**  \n  The axis-aligned property of the model is a key assumption that allows not only for the analysis of SD but is also crucial to get an improvement over GD, and this property mimics the axis-alignment found in the first and last layers of LLMs.\n- [Response to Reviewer G8T2](https://openreview.net/forum?noteId=CfxXnAH6I3): **Connections to LLM training**  \n  Discussion of the bigram frequencies for real tokenizers and possible insights on LLM training.\n\nWe ran additional experiments to answer those questions, but as the NeurIPS guidelines do not allow sharing figures or updating the paper, we can only share a written description. We will use the additional page given for camera ready to include those experimental results and incorporate the clarifications and feedback provided by the reviewers.\n\n## Simplicity of the model\n\n> Training language models uses softmax cross‑entropy, not squared error. [...]\n> _Reviewer pUyz_  \n> Some of the assumptions are fairly unrealistic. Eg, the model is linear, uses square loss, assumes deterministic full-batch updates, and collapses Adam to SD [...]\n> _Reviewer xbaC_  \n> the analysis is restricted to the simple linear bigram model with squared loss [which] may not directly generalize to complex transformer layers or cross-entropy objectives [...]\n> _Reviewer G8T2_  \n\nMultiple reviewers have noted that the model we study is simple, and perhaps too simple to be of practical use for the training of LLMs.\nWe agree with this assessment. \nWe do not claim that our theory is directly applicable to LLMs. \nUnderstanding the impact of other hyperparameters is an interesting next step. \nThe choice of loss function, mini-batch size, momentum, model (attention or normalization layers), or the study of generalization instead of training error are all likely to yield new insights. \nHowever, we believe the simplicity of the model is a strength of the paper. \n\n\nDespite its simplicity, the model is not trivial and already captures a complex behavior observed in practice, that SD outperforms GD for language data. \nIts simplicity allows us to establish clean theoretical results for the convergence of GD and SD without relying on random matrix theory, Fourier transforms, or other complex mathematical tools. The scaling laws provide an explanation for the improvement of SD over GD and ties it to the properties of the data through the heavy tails in the distribution of the eigenvalues. These results prove that the performance gap grows with the vocabulary size even on a linear regression model. \n\nWe have ran additional experiments to show that the conclusion that SD scale better than GD extend to the cross-entropy loss and the use of Adam instead of SD. For space reasons, we cannot include these results in every response. We invite you to read [the response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys) for more details on the cross-entropy loss, and [the response to Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp) for more details on Adam.\n\n---\n\n# Points raised in your review\n\nWe now address the specific questions raised in your review.\n\n## Quadratic vs. cross-entropy loss\n\n> Do the scaling exponents change when the loss is replaced by cross‑entropy on the same linear bigram model? A short derivation or experiment would clarify applicability.\n\nTheoretically, we cannot describe the dynamics of optimizers on the cross-entropy loss. \nOur analysis is restricted to the quadratic loss, and \nthe closest existing analysis on similar models \nare restricted to continuous time (Cabannes et al., 2024, Kunstner et al., 2024)\nas the non-linearity of the gradient update make a discrete-step analysis intractable.\n\nHowever, we were able to confirm experimentally that \nthe separation between GD and SD as the vocabulary size $d$ increases \nstill holds for the cross-entropy loss for $\\alpha = 1$. \nWe pick the best step-size for a given time horizon by grid-search, \nand try to find the scalings by plotting.\n- The best step-size appears to scale as $\\eta \\sim 1/\\log(d)^2$ for GD (instead of $\\eta \\sim 1/\\log(d)$ for the quadratic loss)\n- The normalized optimality gap still appears to follow $r \\sim 1 - \\frac{\\log(t)}{\\log(d)}$ but converges more slowly to this limit as $d$ grows (or, possibly, to another limit).\n- The normalized optimality gap for SD appears independent of $d$ for the range of $d$ we were able to test run. \n\nThese results suggest that the performance gap between GD and SD still grows with $d$ for the cross-entropy loss, though the exact form of the scaling law may be different.\n\n## Averaging the oscillations in SD (Assumption 4.1)\n> The key SD analysis rests on Assumption 4.1 (replace oscillations by a constant η/2), whose correctness is argued only heuristically. \n\nSD is a simple proxy for Adam, but does capture the main benefit of a better scaling with $d$. Experimentally, Adam performs better than SD and also scales better than GD in $d$. We invite you to read the response to [Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp) for a discussion of Assumption 4.1.\n\n---\n\nWe remain available for further clarifications or other questions you may have. \n\n**References**\n- Cabannes et al., 2024: arxiv/2402.18724\n- Kunstner et al., 2024: arxiv/2402.19449"}, {"review_id": "8pCpdP4Xjp", "reviewer": "Reviewer_xbaC", "summary": "This paper investigates why gradient descent struggles to train language models with large vocabularies, focusing on how word frequency distributions affect optimization. The authors study a linear bigram model where word frequencies follow a power law (like Zipf's law in real text) and derive scaling laws showing how training time grows with vocabulary size.\n\nTheir main contributions are: (1) They prove that for Zipf-distributed text data (where word frequency is proportional to 1/rank), gradient descent requires nearly linear scaling with vocabulary size, explaining why GD performs poorly on language model embedding layers. In contrast, sign descent (a proxy for Adam) only needs iterations proportional to the square root of vocabulary size, providing up to 100x speedups for typical vocabularies. (2) They identify different scaling regimes based on how heavy-tailed the word distribution is: for very heavy-tailed data (including Zipf's law), the number of iterations must grow with dimension, while for lighter-tailed distributions, convergence is dimension-independent. (3) They develop a simplified model that captures the essential difficulty - frequent words dominate the loss but rare words in the long tail prevent fast convergence. Their theoretical predictions closely match experiments on real text data, providing a formal explanation for why Adam-like optimizers are crucial for training the first and last layers of transformers where vocabulary size matters most.", "questions": "- How well does sign descent capture the behavior of Adam in practice? An additional experiment which shows the convergence of Adam (or otherwise relaxing assumption 4.1) would strengthen the results.\n- Similarly, how much do the other modeling assumptions change empirics? E.g. using mini-batches, alternative loss function, etc.?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- Strong theoretical analysis: rigorous asymptotic scaling laws for both gradient descent and sign descent on a well-motivated problem. Generally non-trivial analysis.\n- Practical relevance: addresses a real phenomenon in deep learning - why Adam outperforms SGD on transformer embedding layers.\n- Some of the simplifying assumptions are reasonably well motivated (eg Figure 3)\n- Convincing empirical validation of the theoretical results\n- Well organized and reasonable clarity\n- Clear articulation of weaknesses\n\nWeaknesses\n- Some of the assumptions are fairly unrealistic. Eg, the model is linear, uses square loss, assumes deterministic full-batch updates, and collapses Adam to SD via an additional oscillation-averaging assumption (Assumption 4.1) whose fidelity is neither proved nor ablated.\n- Empirical validation is still in a toy domain, and does not test how well the theory generalizes outside of the fairly restrictive modeling assumptions.\n- The paper is fairly dense and would benefit from additional intuition.\n\n[This is outside my area of expertise so I am unable to judge novelty and relation to prior work.]", "was_revised": true, "final_justification": "I recommend acceptance. The paper is technically well executed, but there are questions around impact given the assumptions.", "rebuttal": "# General response\n\nWe thank you for your efforts in this review and for the constructive feedback that will improve the paper. \n\nMultiple reviewers raised similar points regarding the simplicity of the model. We start by addressing those points, and then answer the questions specific to your review. We invite you to read the response to the other reviews for more information on the following points.\n- [Response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys): **Cross-entropy loss vs. squared loss**  \n  Capturing the dynamics of optimization on the cross-entropy loss is not possible, but experiments show that the performance gap between gradient descent (GD) and sign descent (SD) as $d$ increases is similar.\n- [Response to Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp): **Averaging oscillations with Assumption 4.1 and Adam vs. sign descent**  \n  SD is a simple proxy for Adam, but does capture the main benefit of a better scaling with $d$. Experimentally, Adam performs better than SD and also scales better than GD in $d$.\n- [Response to Reviewer 8S6d](https://openreview.net/forum?noteId=Ezuh3XcjFB): **Relation to prior scaling laws**  \n  The main novelty of our approach is on the scaling of $t$ with $d$ to derive a scaling law for GD when the difficulty of the problem scales with $d$.\n- [Response to Reviewer 9d42](https://openreview.net/forum?noteId=3xCuAZLexY): **Axis-aligned model and sign descent**  \n  The axis-aligned property of the model is a key assumption that allows not only for the analysis of SD but is also crucial to get an improvement over GD, and this property mimics the axis-alignment found in the first and last layers of LLMs.\n- [Response to Reviewer G8T2](https://openreview.net/forum?noteId=CfxXnAH6I3): **Connections to LLM training**  \n  Discussion of the bigram frequencies for real tokenizers and possible insights on LLM training.\n\nWe ran additional experiments to answer those questions, but as the NeurIPS guidelines do not allow sharing figures or updating the paper, we can only share a written description. We will use the additional page given for camera ready to include those experimental results and incorporate the clarifications and feedback provided by the reviewers.\n\n## Simplicity of the model\n\n> Training language models uses softmax cross‑entropy, not squared error. [...]\n> _Reviewer pUyz_  \n> Some of the assumptions are fairly unrealistic. Eg, the model is linear, uses square loss, assumes deterministic full-batch updates, and collapses Adam to SD [...]\n> _Reviewer xbaC_  \n> the analysis is restricted to the simple linear bigram model with squared loss [which] may not directly generalize to complex transformer layers or cross-entropy objectives [...]\n> _Reviewer G8T2_  \n\nMultiple reviewers have noted that the model we study is simple, and perhaps too simple to be of practical use for the training of LLMs.\nWe agree with this assessment. \nWe do not claim that our theory is directly applicable to LLMs. \nUnderstanding the impact of other hyperparameters is an interesting next step. \nThe choice of loss function, mini-batch size, momentum, model (attention or normalization layers), or the study of generalization instead of training error are all likely to yield new insights. \nHowever, we believe the simplicity of the model is a strength of the paper. \n\nDespite its simplicity, the model is not trivial and already captures a complex behavior observed in practice, that SD outperforms GD for language data. \nIts simplicity allows us to establish clean theoretical results for the convergence of GD and SD without relying on random matrix theory, Fourier transforms, or other complex mathematical tools. The scaling laws provide an explanation for the improvement of SD over GD and ties it to the properties of the data through the heavy tails in the distribution of the eigenvalues. These results prove that the performance gap grows with the vocabulary size even on a linear regression model. \n\nWe have ran additional experiments to show that the conclusion that SD scale better than GD extend to the cross-entropy loss and the use of Adam instead of SD. For space reasons, we cannot include these results in every response. We invite you to read [the response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys) for more details on the cross-entropy loss, and [the response to Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp) for more details on Adam.\n\n---\n\n# Points raised in your review\n\nWe now address the specific questions raised in your review.\n\n## Averaging the oscillations in SD (Assumption 4.1) and comparison to Adam\nMultiple reviewers asked about the justification for the oscillation averaging in Assumption 4.1, and the connection between Adam and SD.\n\n> How well does SD capture the behavior of Adam in practice? An additional experiment which shows the convergence of Adam (or otherwise relaxing assumption 4.1) would strengthen the results.\n\nAssumption 4.1 is a simplification, but it is not overly strong. Once a component enters the oscillatory phase, we only miss-estimate its loss value by at most a factor of 2 every other step, so the real dynamics are within a constant factor of our model.\nThis is a small price to pay for a great simplification, and not having to keep track of which component is on which side of the oscillation. An alternative would be to use a random initialization and use the fact that the oscillation should cancel out, but we do not think the benefits of this approach outweigh the added complexity.\n\n**On Adam**, we agree that the scaling law derived for SD is unlikely to hold for Adam. Our goal is to provide a simplified model that provably establishes the benefit of SD over GD, which has been idenfitied by prior work as a good proxy for the success of Adam (Kunstner et al., 2023, 2024). We run additional experiments to verify that our Adam also scales better with $d$ when $\\alpha=1$. We fit the step-size by grid-search and fix other parameters to their default values ($\\beta_1=0.9,\\beta_2=0.999,\\epsilon=10^{-8}$). The performance of Adam appears even better than that of SD, and does not appear to degrade as $d$ increases (or if it does, very slowly).\n\n## Impact of changing the loss function\n> Similarly, how much do the other modeling assumptions change empirics? E.g. using mini-batches, alternative loss function, etc.?\n\nCapturing the dynamics of optimization on the cross-entropy loss is not possible, but experiments show that the performance gap between gradient descent (GD) and sign descent (SD) as $d$ increases is similar.\nWe invite you to read the response to [Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys) for a discussion of how the results change when using the cross-entropy loss instead of the squared loss.\n\n---\n\nWe remain available for further clarifications or other questions you may have. \n\n**References**\n- Kunstner et al., 2023: arxiv/2304.13960\n- Kunstner et al., 2024: arxiv/2402.19449"}, {"review_id": "k5DJWjnWzD", "reviewer": "Reviewer_8S6d", "summary": "This paper studies the optimization scaling law for GD and sign GD on a linear bigram model with square loss. They posit a power law distribution for the frequency of each word $\\pi_k \\sim k^{-\\alpha}$. They provide scalings for the MSE loss as a function of $t$ for both GD and sign GD. One key takeaway for Zipfian data $\\alpha = 1$ is that GD requires $d^{1-\\epsilon}$ steps while sign GD requires $\\sqrt d$ steps to converge where $d$ is the vocabulary size. The authors verify their approximations and scaling results with numerical simulations. Their work establishes the importance of optimizer in improving efficiency of training on large vocabularies with Zipfian structure.", "questions": "Questions\n\n1. In the related works section, the authors claim that previous scaling law studies required $\\alpha \\geq 1$ in order to have well defined infinite width and depth limits. I think both the Paquette paper and the Bordelon scaling law paper could consider either $\\alpha > 1$ or $\\alpha \\leq 1$ since their formulas depended on a general set of limiting eigenvalues. Could the authors explain what they meant in this section?\n2. The observed scaling laws often do have the form of $\\text{Loss} \\sim t^{- \\alpha}$. For GD this would require having $\\alpha > 1$ to get this functional form and it could allow for a variety of observed scaling law relationships. From Theorem 4.5 a power law scaling for time $t$ is achieved for any $\\alpha > \\frac{1}{2}$ where it goes as $t^{-2}$. Empirically the LLM scaling laws have an exponent for time of $\\approx 0.75$ (Kaplan). Do the authors think that this is compatible with their model?\n3. Have the authors experimented with LLM training using varying tokenizers? The theory suggests that time to train should depend on $\\sqrt{d}$. Validating this (or perhaps pointing to existing experiments on this) would be very impressive and strengthen the paper significantly. \n4. Do the authors have a sense of what finite model size scaling laws look like in this model? If they added an untrainable projection layer $\\hat{Y} = X A W$ where $A$ is $d \\times k$ (could be random and frozen as in Bordelon or Paquette papers) and $W$ is now $k \\times d$ can they describe the dependence of the final error on $k$ if $k < d$? Does it recover reasonable scaling laws (ie consistent with LLM papers?)\n\nNits\n\n1. \"would\" on line 34 should probably be \"could\"\n2. Should $\\lambda_{ij}$ under line 129 be $\\lambda_i$?", "limitations": "The authors address limitations of the present study.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. This paper studies an important problem of analyzing neural scaling laws for sign-GD. \n2. They provide a novel analysis of sign-GD on a bigram model and show that for Zipfian data, sign-GD outscores SGD significantly as a function of the token dimension ($\\sqrt d$ instead of $d$ steps).  \n3. They also include several experiments of their bigram model showing the validity of their analytical results.\n\nWeaknesses\n1. Connections to known scaling law results for LLMs could be improved or clarified (see questions below).", "was_revised": false, "final_justification": "", "rebuttal": "# General response\n\nWe thank you for your efforts in this review and for the constructive feedback that will improve the paper. \n\nMultiple reviewers raised similar points regarding the simplicity of the model. We start by addressing those points, and then answer the questions specific to your review. We invite you to read the response to the other reviews for more information on the following points.\n- [Response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys): **Cross-entropy loss vs. squared loss**  \n  Capturing the dynamics of optimization on the cross-entropy loss is not possible, but experiments show that the performance gap between gradient descent (GD) and sign descent (SD) as $d$ increases is similar.\n- [Response to Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp): **Averaging oscillations with Assumption 4.1 and Adam vs. sign descent**  \n  SD is a simple proxy for Adam, but does capture the main benefit of a better scaling with $d$. Experimentally, Adam performs better than SD and also scales better than GD in $d$.\n- [Response to Reviewer 8S6d](https://openreview.net/forum?noteId=Ezuh3XcjFB): **Relation to prior scaling laws**  \n  The main novelty of our approach is on the scaling of $t$ with $d$ to derive a scaling law for GD when the difficulty of the problem scales with $d$.\n- [Response to Reviewer 9d42](https://openreview.net/forum?noteId=3xCuAZLexY): **Axis-aligned model and sign descent**  \n  The axis-aligned property of the model is a key assumption that allows not only for the analysis of SD but is also crucial to get an improvement over GD, and this property mimics the axis-alignment found in the first and last layers of LLMs.\n- [Response to Reviewer G8T2](https://openreview.net/forum?noteId=CfxXnAH6I3): **Connections to LLM training**  \n  Discussion of the bigram frequencies for real tokenizers and possible insights on LLM training.\n\nWe ran additional experiments to answer those questions, but as the NeurIPS guidelines do not allow sharing figures or updating the paper, we can only share a written description. We will use the additional page given for camera ready to include those experimental results and incorporate the clarifications and feedback provided by the reviewers.\n\n## Simplicity of the model\n\n> Training language models uses softmax cross‑entropy, not squared error. [...]\n> _Reviewer pUyz_  \n> Some of the assumptions are fairly unrealistic. Eg, the model is linear, uses square loss, assumes deterministic full-batch updates, and collapses Adam to SD [...]\n> _Reviewer xbaC_  \n> the analysis is restricted to the simple linear bigram model with squared loss [which] may not directly generalize to complex transformer layers or cross-entropy objectives [...]\n> _Reviewer G8T2_  \n\nMultiple reviewers have noted that the model we study is simple, and perhaps too simple to be of practical use for the training of LLMs.\nWe agree with this assessment. \nWe do not claim that our theory is directly applicable to LLMs. \nUnderstanding the impact of other hyperparameters is an interesting next step. \nThe choice of loss function, mini-batch size, momentum, model (attention or normalization layers), or the study of generalization instead of training error are all likely to yield new insights. \nHowever, we believe the simplicity of the model is a strength of the paper. \n\nDespite its simplicity, the model is not trivial and already captures a complex behavior observed in practice, that SD outperforms GD for language data. \nIts simplicity allows us to establish clean theoretical results for the convergence of GD and SD without relying on random matrix theory, Fourier transforms, or other complex mathematical tools. The scaling laws provide an explanation for the improvement of SD over GD and ties it to the properties of the data through the heavy tails in the distribution of the eigenvalues. These results prove that the performance gap grows with the vocabulary size even on a linear regression model. \n\nWe have ran additional experiments to show that the conclusion that SD scale better than GD extend to the cross-entropy loss and the use of Adam instead of SD. For space reasons, we cannot include these results in every response. We invite you to read [the response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys) for more details on the cross-entropy loss, and [the response to Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp) for more details on Adam.\n\n---\n\n# Points raised in your review\n\nWe now address the specific questions raised in your review.\n\n## $\\alpha < 1$ and \"finite-dimensional\" models\n> the authors claim that previous scaling law studies required $\\alpha \\geq 1$ in order to have well defined infinite width and depth limits. I think both the Paquette paper and the Bordelon scaling law paper could consider either $\\alpha \\geq 1$ or $\\alpha \\leq 1$ [...] Could the authors explain what they meant in this section?\n\nWe agree that this statement requires clarification. We will revise it to convey the following. \n\nExisting scaling laws work in regimes where the difficulty of optimization does not scale with dimension. If $L \\sim t^{-c}$ for some constant $c$ without requiring $t$ to grow with $d$, even the high-dimensional limit is effectively as hard as a finite dimensional problem. In our setting, this is the $\\alpha \\geq 1$ regime. \nThe works of Paquette et al. (2024) on the random feature model and Bordelon et al. (2024) on the teacher-student study generalization and use different parameterizations, making a direct comparison difficult, but also fall in this \"effectively finite-dimensional\" regime.\n- In the work of Paquette et al. (2024), this can be seen from their phase diagrams in Figure 2.a and Figure 4.a. The area with very heavy tails in the Hessian eigenvalue and target does not admit a power-law decay, and likely does not decay without scaling $t$ with $d$. \n- Similarly, Bordelon et al. (2024) provide a scaling law of $L \\sim t^{-(a-1)/b}$ (Eq. 4, in their notation) when the dataset and model size $\\to\\infty$. The case $a = 1$ corresponds to Zipf-law decay of the eigenvalues, and the loss is independent of $t$. For $a < 1$, the loss explodes instead. Those degenerate problems appear because they take the dimensionality of the model to infinity first and keep $t$ finite. \n\nIn both cases, considering a joint limit where $t$ and $d$ scale together could capture interesting dynamics and show training can make progress, if only slowly.\n\n## Comparison with empirical scaling laws\n> The observed scaling laws often do have the form of $L \\sim t^{-\\alpha}$. For GD this would require having $\\alpha > 1$ to get this functional form and it could allow for a variety of observed scaling law relationships. [...] ]Empirically the LLM scaling laws have an exponent for time of $\\approx 0.75$ (Kaplan). Do the authors think that this is compatible with their model?\n\nThe comparison appears difficult, as the dimension taken to $\\infty$ is not the same. Experimental works on scaling laws that achieve $L\\sim t^{-3/4}$ increase parameter count by scaling the hidden dimension of the network. Given the same vocabulary size, it is likely that this makes the problem easier to fit rather than harder. This scaling is likely in the \"effectively finite-dimensional\" regime discussed above, and likely better modeled by existing analyses. The remaining differences could be explained by other effects, even without considering a more complex non-linear model; how to scale mini-batch size, momentum, and an analysis of the generalization error instead of training error are likely to have a significant impact on the exponent of the power in the power-law.\n\n\n## Experimental evidence for $\\sqrt{d}$ scaling\n> Have the authors experimented with LLM training using varying tokenizers? The theory suggests that time to train should depend on $\\sqrt{d}$. Validating this (or perhaps pointing to existing experiments on this) would be very impressive and strengthen the paper significantly.\n\nThe closest evidence for a scaling in vocabulary is the work of Tao et al. (2024), which shows experimentally that larger FLOPS budget benefit from larger vocabulary sizes. The analysis in FLOPS makes it unclear whether the need for more computation is due a higher cost per iteration or the need for more iterations however. \n\nWe agree that an experimental result trying to establish non-linear model also exhibit a different scaling in vocabulary size with GD vs. SD would strengthen the paper. We will try to train small language models with varying vocabulary sizes, but do not have the computational resources to do so with models considered practical.\n\n## Untrainable projection layer\n> Do the authors have a sense of what finite model size scaling laws look like in this model? If they added an untrainable projection layer $\\hat Y = XAW$ where $A$ is $d \\times k$ [random and frozen] and $W$ is now $k \\times d$ can they describe the dependence of the final error on $k$ if $k < d$?\n\nThe performance of sign descent will degrade considerably due to the removal of the axis-aligned structure of the problem and the scaling in $d$ will likely be much worse than for GD (see also the [response to Reviewer 9d42](https://openreview.net/forum?noteId=3xCuAZLexY) on the axis-aligned property of the model). If the dimension of the model $k$ scales with the vocabulary size $d$ and $k > d$ as in the work of Paquette et al. (2024), we suspect little change in the performance of GD on the expected error because of rotational invariance. The scaling with $k < d$ could be obtained by estimating the decay of the eigenvalues of the resulting Hessian random matrix, but we have not done the analysis.\n\n---\n\nWe remain available for further clarifications or other questions you may have. \n\n**References**\n- Bordelon et al., 2024: arxiv/2402.01092\n- Paquette et al., 2025: arxiv/2405.15074\n- Tao et al., 2024: arxiv/2407.13623"}, {"review_id": "SjplQbNJZc", "reviewer": "Reviewer_9d42", "summary": "In this paper, the authors consider a linear bigram model, where the distribution of the current token and the conditional \ndistribution of the next token both follow a power law. They study the loss curve of gradient descent and sign descent \nin this setting, and derive loss-iteration scaling laws that take the dimensional dependency into consideration and\nare more accurate than the usual worst-case rate from the generic convex optimization analysis in the early phase of \nthe training. The scaling laws also show that when the data follow a power law distribution, sign descent has a \nbetter dimensional dependency than vanilla gradient descent.", "questions": "* See the weakness section. For the sign descent analysis, what will happen if we apply a rotation to the input embedding?\n  What if the embeddings are only near orthogonal (for example, random Gaussian vectors)? Do the analysis/result/intuition \n  carry over to those cases? \n* Could you provide some intuitive explanations on why sign descent has a better rate than gradient descent in this task?\n* What will happen if the condtional/unconditional distributions have different exponents? I guess we will not be able \n  to get clean formulae in this case. However, I wonder given a scaling law formula, whether it is always possible to find exponents \n  $\\alpha_k$ such that gradient descent or sign descent realizes this scaling law, or this model can realize only a \n  certain class of scaling laws? I am asking this purely out of curiosity and do not expect a complete answer.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n* This is a neat paper in the sense that the task itself (bigram model) is simple, but the analysis is clean \n  and complete. The overall presentation is also clear and easy to follow. \n* The introduction of the rescaled time variable is new in the theoretical analysis of scaling laws (as far as I know).\n  The authors let the time $t$ be a function of the dimension $d$, so that the loss $L_d(t)$ does not degenerate when\n  $d \\to \\infty$. It is surprising that such a simple trick can lead to a wide variety of non-trivial results. \n* The theoretical analysis is quite complete, as the authors derive the scaling laws for both gradient descent and sign\n  descent in fo all different regimes of the power law exponent $\\alpha$. Experiments/simulation are also provided to \n  verify their theoretical claims. \n\n**Weakness**\n* The inputs are one-hot encoding vectors of the tokens, which are automatically axis-aligned. This greatly simplifies \n  the analysis of sign descent. It is not clear if the sign descent analysis can be extended to other orthogonal (rotated version of the one-hot embeddings) or \n  near orthogonal (random Gaussian vectors) embeddings. Though one may argue that algorithms such as Muon will remove the effect of a rotation, and it \n  behaves similar to axis-aligned sign descent, this is not obvious and does not apply to the near orthogonal case. \n\n**Typos and suggestions**\n* Line 144: \"$\\pi_{\\rho_j(k+1)|j} \\ge \\pi_{\\rho_j(k)|j}$.\" I believe the inequality should be reversed.\n* Line 225: \"$\\eta_* = \\min_\\eta...$\" Should be $\\mathrm{argmin}_\\eta$\n* Line 954: \"At she partial sum ...\"\n* I found Proposition 2.2 confusing until I reached the proof Theorem 3.1. It might be good if the authors could comment \n  near Proposition 2.2 that this proposition is intended to be used together with Eq (1) to get a clean formula for the \n  loss.", "was_revised": true, "final_justification": "Though the paper considers relatively simple models, the analysis is neat and contains some interesting ideas (choosing a proper scaling between $t$ and $d$ to obtain a non-trivial asymptotic result). \n\nMy main concern was the axis-aligned assumption. In the rebuttal, the authors admitted that this is a strong assumption and cannot be removed, but they justify this assumption with existing empirical results showing this property can indeed be observed in real-world models, at least to a certain degree. I believe this is an acceptable justification. \n\nTherefore, I recommend acceptance of the paper.", "rebuttal": "# General response\n\nWe thank you for your efforts in this review and for the constructive feedback that will improve the paper. \n\nMultiple reviewers raised similar points regarding the simplicity of the model. We start by addressing those points, and then answer the questions specific to your review. We invite you to read the response to the other reviews for more information on the following points.\n- [Response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys): **Cross-entropy loss vs. squared loss**  \n  Capturing the dynamics of optimization on the cross-entropy loss is not possible, but experiments show that the performance gap between gradient descent (GD) and sign descent (SD) as $d$ increases is similar.\n- [Response to Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp): **Averaging oscillations with Assumption 4.1 and Adam vs. sign descent**  \n  SD is a simple proxy for Adam, but does capture the main benefit of a better scaling with $d$. Experimentally, Adam performs better than SD and also scales better than GD in $d$.\n- [Response to Reviewer 8S6d](https://openreview.net/forum?noteId=Ezuh3XcjFB): **Relation to prior scaling laws**  \n  The main novelty of our approach is on the scaling of $t$ with $d$ to derive a scaling law for GD when the difficulty of the problem scales with $d$.\n- [Response to Reviewer 9d42](https://openreview.net/forum?noteId=3xCuAZLexY): **Axis-aligned model and sign descent**  \n  The axis-aligned property of the model is a key assumption that allows not only for the analysis of SD but is also crucial to get an improvement over GD, and this property mimics the axis-alignment found in the first and last layers of LLMs.\n- [Response to Reviewer G8T2](https://openreview.net/forum?noteId=CfxXnAH6I3): **Connections to LLM training**  \n  Discussion of the bigram frequencies for real tokenizers and possible insights on LLM training.\n\nWe ran additional experiments to answer those questions, but as the NeurIPS guidelines do not allow sharing figures or updating the paper, we can only share a written description. We will use the additional page given for camera ready to include those experimental results and incorporate the clarifications and feedback provided by the reviewers.\n\n## Simplicity of the model\n\n> Training language models uses softmax cross‑entropy, not squared error. [...]\n> _Reviewer pUyz_  \n> Some of the assumptions are fairly unrealistic. Eg, the model is linear, uses square loss, assumes deterministic full-batch updates, and collapses Adam to SD [...]\n> _Reviewer xbaC_  \n> the analysis is restricted to the simple linear bigram model with squared loss [which] may not directly generalize to complex transformer layers or cross-entropy objectives [...]\n> _Reviewer G8T2_  \n\nMultiple reviewers have noted that the model we study is simple, and perhaps too simple to be of practical use for the training of LLMs.\nWe agree with this assessment. \nWe do not claim that our theory is directly applicable to LLMs. \nUnderstanding the impact of other hyperparameters is an interesting next step. \nThe choice of loss function, mini-batch size, momentum, model (attention or normalization layers), or the study of generalization instead of training error are all likely to yield new insights. \nHowever, we believe the simplicity of the model is a strength of the paper. \n\nDespite its simplicity, the model is not trivial and already captures a complex behavior observed in practice, that SD outperforms GD for language data. \nIts simplicity allows us to establish clean theoretical results for the convergence of GD and SD without relying on random matrix theory, Fourier transforms, or other complex mathematical tools. The scaling laws provide an explanation for the improvement of SD over GD and ties it to the properties of the data through the heavy tails in the distribution of the eigenvalues. These results prove that the performance gap grows with the vocabulary size even on a linear regression model. \n\nWe have ran additional experiments to show that the conclusion that SD scale better than GD extend to the cross-entropy loss and the use of Adam instead of SD. For space reasons, we cannot include these results in every response. We invite you to read [the response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys) for more details on the cross-entropy loss, and [the response to Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp) for more details on Adam.\n\n---\n\n# Points raised in your review\n\nWe now address the specific questions raised in your review.\n\n## Axis-aligned model and why SD works\n> The inputs are one-hot encoding vectors of the tokens, which are automatically axis-aligned. This greatly simplifies the analysis of SD. [...] What will happen if we apply a rotation to the input embedding? What if the embeddings are only near orthogonal (for example, random Gaussian vectors)? Do the analysis/result/intuition carry over to those cases?\n\n> Could you provide some intuitive explanations on why SD has a better rate than GD in this task?\n\nWe agree that the axis-aligned structure of the problem is a key part of the analysis, and not only a simplifying assumption. Adding a random rotation to the problem breaks the axis-aligned property, makes SD much worse than GD empirically, and makes the analysis much harder. We will revise the paper to emphasize the following. \n\nThe benefits of SD come specifically from this axis-aligned structure. That SD has similar performance benefits as Adam in transformers has been shown experimentally by Kunstner et al. (2023, 2024), and the benefits of Adam have been shown experimentally to primarily come from how it handles in the first and last layer of the transformer by Zhang et al. (2024) and Zhao et al. (2024). Those layers are axis-aligned, and this structure is necessary to obtain good performance with SD, as the performance of Adam depends on this axis-alignment (Maes et al., 2024).\n\nWithout additional assumptions on the axis-aligned structure, existing analyses predict that the performance of SD scales worse with dimension than plain GD (we compare our results with existing rates for SD. Our work shows the benefits of this axis-aligned structure on a problem that is close to the first layer of a transformer, and the benefits of SD in this setting.\n\n## What if the exponents differ in $\\pi_i$ and $\\pi_{j\\vert i}$?\n> What will happen if the condtional/unconditional distributions have different exponents? \n\nGiven different exponents for the unconditional and conditional distributions, it should still be possible to obtain a scaling law for the loss. Although the number of cases with distinct functional forms might grow from the three currently covered ($\\alpha < 1, \\alpha=1, \\alpha> 1$) to potentially more. The analysis of each case is likely not much more complex than the cases we cover, but presenting the results in a unified way may be difficult. \n\n> I wonder given a scaling law formula, whether it is always possible to find exponents $\\alpha_k$ such that GD or SD realizes this scaling law, or this model can realize only a certain class of scaling laws? \n\nIt is likely not possible to fit _any_ scaling law. Our model is flexible enough to cover multiple functional forms, including the three cases below for GD (taking $r = \\frac{L_t - L_*}{L_0 - L_*}$)\n$$\n    \\begin{aligned}\n    r \\sim \\frac{1-\\alpha}{\\alpha} \\frac{\\exp(\\frac{2t}{d^{\\alpha}})}{\\frac{2t}{d^\\alpha}+1}\n    \\quad (\\alpha < 1)\n    \\quad &&\\quad \n    r \\sim 1 - \\frac{\\log(t)}{\\log(d)}\n    \\quad (\\alpha = 1)\n    \\quad &&\\quad \n    r \\sim \\frac{C(\\alpha) }{t^{1-\\frac{1}{\\alpha}}}\n    \\quad (\\alpha > 1)\n    \\end{aligned}\n$$\nAdding a separate exponent for the conditional distribution would allow us to cover more cases, \nlikely any power-law scaling of the form $L \\sim t^{-c}$ form some $c$. But those are only three functional form, and it is likely that many other could be obtained by studying other models.\n\n## Typos and suggestions\n\nThank you for the recommendations, we will incorporate them.\n\n\n---\n\nWe remain available for further clarifications or other questions you may have. \n\n**References**\n- Kunstner et al., 2023: arxiv/2304.13960\n- Kunstner et al., 2024: arxiv/2402.19449\n- Maes et al., 2024: arxiv/2410.19964\n- Zhang et al., 2024: arxiv/2406.16793\n- Zhao et al., 2024: arxiv/2407.07972"}, {"review_id": "kk2iyy6Ob3", "reviewer": "Reviewer_G8T2", "summary": "The paper investigates scaling laws for the convergence of Gradient Descent (GD) and Sign Descent (SD) optimizers for a simplified linear bigram model trained on data that follows power law distributions 1/k^α (in both token frequency, conditional token frequency, and consequently eigenvalues of the Hessian), where k is the frequency rank of each token.  This simplified model is chosen because it allows closed-form solutions for both GD and SD, while still reproducing differences between GD and SD seen in practice.  The final deliverable is a set of empirically-validated scaling theorems that show how many iterations are required to reach a relative loss target ϵ as a function of (1) the dimensionality and (2) the exponent of the power law α. GD is shown to perform particularly poorly on Zipfian α=1 data (for small ϵ), scaling almost linearly in the dimensionality, whereas SD scales closer to the square root of the dimensionality.  These findings formalize some prior empirical observations regarding the impact of heavy-tailedness of the data (as Zipfian reflects real language data).", "questions": "Could you make the connection to LLM studies a bit more clear?  I.e., do modern methods of creating LLM vocabularies avoid the degenerate case where a specific token is always followed by a specific other token (e.g., \"et\" and \"cetera\" being two separate tokens), thus perhaps helping justify your power law assumptions?  Recent work has also shown that increasing vocab size with scale can improve loss, which effectively means that changing the vocab size can change the slope of the scaling law.  I wonder how this relates to your work.\n\nMotivating α < 1: Can you provide stronger justification or evidence from practical datasets (beyond Figure 3) that data following α < 1 is worth studying, and thus your results may be practically meaningful?  Is this something that arises outside of language?  In other words, why do we care about very, very heavy tails?\n\nHyperparameter implications: You mention your scaling laws can guide hyperparameter selection as vocabulary size increases - can you elaborate precisely on how practitioners might use these scaling laws to adjust specific hyperparameters (e.g., step size or optimizer choice)?\n\nGeneralizability: How do you anticipate your results might generalize beyond linear bigram models (e.g., to transformers or non-squared-loss settings)? Which of your assumptions are most critical and least likely to hold in more complex models?  Do you have further thoughts on the first/last layer issues seen previously?  Do your findings imply things about parameters in non first/last Transformer layers?  Does the theory in this work make any testable predictions for LLMs?\n\nConditional distribution deviations: Can you quantify or bound how deviations from your conditional power-law assumption might impact your theoretical predictions?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\nQuality:\n- Technical soundness: The theoretical derivations are rigorous and are supported by experimental results on both synthetic (controlled α) and real data (OpenWebText).\n- Supported claims: The results on GD and SD scaling are clearly demonstrated experimentally (Figure 2). Their simplified theoretical model aligns well with empirical data.\n\nClarity:\n- Structure: Generally well-organized; contributions clearly stated.\n- Figures: Good illustrations effectively show theoretical predictions against empirical outcomes.\n\nSignificance:\n- Key insight: Shows explicitly why and when Sign Descent (proxy for Adam-like methods) outperforms Gradient Descent for power-law-distributed data.\n- Practical Impact: The analysis provides insights into optimizer performance with increasing vocabulary size, which is practically relevant for training language models.  However, because of the many assumptions and restrictions needed for the study, I do not foresee an immediate impact on practical LLM training arising directly from this work.\n\nOriginality:\n- Novelty of results: The paper uniquely addresses a gap by studying heavier-tailed data (α ≤ 1), which previous literature largely ignores.\n\nWeaknesses:\n\nScope limitation:\n- As noted above, the analysis is restricted to the simple linear bigram model with squared loss.  A number of other assumptions are made. While informative, the impact may not directly generalize to complex transformer layers or cross-entropy objectives common in practical NLP applications.\n- The assumption that conditional distributions also follow the same power-law as the marginal frequencies (Assumption 2.3) seems idealized. The authors investigate and acknowledge deviations (Figure 3), but the implications for practical scenarios are less clear. It's also unclear if α < 1 cases are practically motivated, as most natural language settings specifically reflect α ≈ 1.  This is not really investigated or discussed.\n\nClarity:\n\nThe paper would benefit greatly (and potentially have larger impact) by adding more general topic sentences and definitions at the beginning of sections. These can serve to anchor and provide scaffolding for readers who are not experts in this area (but may generally be interested in scaling laws, optimization, etc.).  That is, this paper may serve as a good entry point for such readers and therefore I would recommend greater clarity and also perhaps an extended related work section in an appendix to clarify the progress in understanding that has been made in this area over the last several years.\n\nAs an example of something requiring clarification, I note that the term “scaling law” is mentioned in the title, abstract, intro, Figure 1, related work, and if we jump ahead to the conclusion.  But none of this actually defines what an optimization scaling law actually is?  Readers familiar with scaling laws in other contexts will expect a clear and precise definition: here we consider a law that looks at how X changes in Y and Z (or whatever).\n- The related work mentions scaling laws for parameters like N and D (in C, for compute-efficient training) and η with B (for well-tuned training), but on a first pass, I wasn't able to extract similar scaling laws for optimization.\n- These sections of the paper definitely hint at what form the scaling law might take, but I think the paper’s clarity would have really benefited if the introduction had made the specific scaling law clear, which seems to happen at the start of Section 2.2: “Our goal is to derive scaling laws for the loss of Problem 2.1 in d dimensions after t steps, Ld(t), as d → ∞.”\n- So, in the intro, you could say something like, “specifically, we look at how the [squared-error] loss of a [linear] model, of dimensionality d, scales [after t steps] for tokens generated by a bigram LM with power law exponent α.” (where the bracketed parts depends on how specific you want to be; the key is to mention L scaling in d). You could also work this into the caption of Figure 1 in some form.\n\nAlso, it would have helped on a first read of the paper if we had more clearly defined what is meant by eigenvalues of the “data” (i.e., eigenvalues of the Hessian), and how the power law in these eigenvalues specifically relate to the power law in the unigram (and bigram) frequencies.  While you use α for both in the intro, the full connection wasn’t clear to me until after I read Section 2.  I definitely assumed that we were talking about the same α, but you could have helped by saying something like, “in our case, the eigenvalues follow the same power law as the bigram frequencies, thus we naturally consider cases where α < 1 by virtue of ...” or whatever.\n\nOther clarity issues:\n- 1.2 “Given matrices X and Y ∈ {0, 1}^{n×d} containing the one-hot encodings of n pairs of tokens”.  This was actually hard to parse at first (reading it as X and Y *each* contain pairs of tokens?).  Can we slow down a little bit here, say that x is a 1-hot-encoding of a token, and y is a 1-hot-encoding of the NEXT token, and we have a dataset of n such pairs (next-token prediction), which we put into matrix form as X and Y.  That would have helped a lot.\n- 2.1: Can we be a bit more explicit rather than defining things as we go?  Like, “let x* be the solution (loss minimizer?) of a convex quadratic loss in reduced form, f(x).  Let … be the eigenvectors/eigenvalues of A.  The loss …”\n- Figure 3, right: this plot was a bit confusing on first read.  The following words help: “once sorted, the next-word frequencies also follow a power law with the same exponent,” but the xlabel says “Rank of word k”, not “Rank of word k among followers of word j,” which I think is really meant.\n\nVery minor for the final paper:\n- Note it does say to “delete this instruction block” in the NeurIPS checklist\n- “Our approach is inspired by the line of work on theoretical scaling laws, or asymptotic convergence as the dimensionality grows” – could you revise to clarify the semantics of “or” here, i.e., does this mean “also known as” or are you talking about two distinct areas of work?", "was_revised": true, "final_justification": "I have read the other reviews and the rebuttal from the authors.  I find this is a technically solid paper, which, despite its assumptions, helps advance our understanding regarding optimization of natural language.  I believe the authors can and will take all the detailed reviews and feedback and use them to further improve the final version of the paper.  This is why I am recommeding \"Accept\"", "rebuttal": "# General response\n\nWe thank you for your efforts in this review and for the constructive feedback that will improve the paper. \n\nMultiple reviewers raised similar points regarding the simplicity of the model. We start by addressing those points, and then answer the questions specific to your review. We invite you to read the response to the other reviews for more information on the following points.\n- [Response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys): **Cross-entropy loss vs. squared loss**  \n  Capturing the dynamics of optimization on the cross-entropy loss is not possible, but experiments show that the performance gap between gradient descent (GD) and sign descent (SD) as $d$ increases is similar.\n- [Response to Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp): **Averaging oscillations with Assumption 4.1 and Adam vs. sign descent**  \n  SD is a simple proxy for Adam, but does capture the main benefit of a better scaling with $d$. Experimentally, Adam performs better than SD and also scales better than GD in $d$.\n- [Response to Reviewer 8S6d](https://openreview.net/forum?noteId=Ezuh3XcjFB): **Relation to prior scaling laws**  \n  The main novelty of our approach is on the scaling of $t$ with $d$ to derive a scaling law for GD when the difficulty of the problem scales with $d$.\n- [Response to Reviewer 9d42](https://openreview.net/forum?noteId=3xCuAZLexY): **Axis-aligned model and sign descent**  \n  The axis-aligned property of the model is a key assumption that allows not only for the analysis of SD but is also crucial to get an improvement over GD, and this property mimics the axis-alignment found in the first and last layers of LLMs.\n- [Response to Reviewer G8T2](https://openreview.net/forum?noteId=CfxXnAH6I3): **Connections to LLM training**  \n  Discussion of the bigram frequencies for real tokenizers and possible insights on LLM training.\n\nWe ran additional experiments to answer those questions, but as the NeurIPS guidelines do not allow sharing figures or updating the paper, we can only share a written description. We will use the additional page given for camera ready to include those experimental results and incorporate the clarifications and feedback provided by the reviewers.\n\n## Simplicity of the model\n\n> Training language models uses softmax cross‑entropy, not squared error. [...]\n> _Reviewer pUyz_  \n> Some of the assumptions are fairly unrealistic. Eg, the model is linear, uses square loss, assumes deterministic full-batch updates, and collapses Adam to SD [...]\n> _Reviewer xbaC_  \n> the analysis is restricted to the simple linear bigram model with squared loss [which] may not directly generalize to complex transformer layers or cross-entropy objectives [...]\n> _Reviewer G8T2_  \n\nMultiple reviewers have noted that the model we study is simple, and perhaps too simple to be of practical use for the training of LLMs.\nWe agree with this assessment. \nWe do not claim that our theory is directly applicable to LLMs. \nUnderstanding the impact of other hyperparameters is an interesting next step. \nThe choice of loss function, mini-batch size, momentum, model (attention or normalization layers), or the study of generalization instead of training error are all likely to yield new insights. \nHowever, we believe the simplicity of the model is a strength of the paper. \n\nDespite its simplicity, the model is not trivial and already captures a complex behavior observed in practice, that SD outperforms GD for language data. \nIts simplicity allows us to establish clean theoretical results for the convergence of GD and SD without relying on random matrix theory, Fourier transforms, or other complex mathematical tools. The scaling laws provide an explanation for the improvement of SD over GD and ties it to the properties of the data through the heavy tails in the distribution of the eigenvalues. These results prove that the performance gap grows with the vocabulary size even on a linear regression model. \n\nWe have ran additional experiments to show that the conclusion that SD scale better than GD extend to the cross-entropy loss and the use of Adam instead of SD. For space reasons, we cannot include these results in every response. We invite you to read [the response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys) for more details on the cross-entropy loss, and [the response to Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp) for more details on Adam.\n\n---\n\n# Points raised in your review\n\nWe now address the specific questions raised in your review.\n\n## Bigram distribution and LLMs\n> The assumption that conditional distributions also follow the same power-law as the marginal frequencies (Assumption 2.3) seems idealized.   \n> Do [tokenizers] avoid the degenerate case where a specific token is always followed by a specific other token [e.g., \"et\" and \"cetera\",] helping justify your power law assumptions? \n\nWe agree that our model is an approximation and not an accurate model of language. But the marginal and conditional probabilities do approximately follow the power-law, as shown using a standard tokenizer on OpenWebText in Figure 3. Most next-word distributions are far from being supported on just a few tokens.\n\nAnecdotally, from our trained vocabulary, the next-word distributions that deviate most from Zipf's law appear to be numbers (most likely followed by other numbers) and special characters used to start the BPE tokenizer (very rare compared to other tokens, some not appearing in the data). While the support of the next-word distribution is not the entire vocabulary, the tokens generated by the algorithm are more in line with the power-law assumption and can be followed by $10^3$ different tokens or more. \n\n> Can you quantify or bound how deviations from your conditional power-law assumption might impact your theoretical predictions?\n\nThis would require assumptions on the form of the deviations. Following Velikanov and Yarotsky (2022), assuming that the frequencies are bounded by $1/k^\\alpha$ up to a constant seems applicable given Figure 3 and might be sufficient to derive upper bounds on the loss instead of an asymptotic equivalence.\n\n## Connection to existing work on vocabulary size\n> Recent work has also shown that increasing vocab size with scale can improve loss, which effectively means that changing the vocab size can change the slope of the scaling law\n\nExisting works shows experimentally that larger vocabulary sizes are beneficial when the FLOPS budget is large (Tao et al. 2024). Whether this is because they need more FLOPS per iteration or more iterations is unclear. Our model hints at the latter, and suggests this scaling may be qualitatively different from scaling the width. On its own, it does not provide a complete explanation applicable in practice, but we hope it informs future work on the difference in the scaling behavior of vocabulary size and width.\n\n## Why $\\alpha < 1$?\n> Can you provide stronger justification or evidence from practical datasets (beyond Figure 3) that data following α < 1 is worth studying, and thus your results may be practically meaningful? \n\nWe agree that the case $\\alpha < 1$ is not the most relevant for practice.\nWe describe it to illustrate that the case $\\alpha = 1$ is a \"worst-case\" scenario. The decrease in performance of GD depends both on having heavy tails and a large imbalance in the frequencies. The case $\\alpha > 1$ lacks the heavy tails, and the case $\\alpha < 1$ lacks the imbalance. We will clarify this in the introduction.\n\n## Hyperparameter implications?\n> Hyperparameter implications: [...] can you elaborate precisely on how practitioners might use these scaling laws to adjust specific hyperparameters\n\nOur scaling laws provide guidelines to set hyperparameters for the linear bigram model.\nGD requires the step-size to scales with the vocabulary size $d$ as $\\eta \\sim \\log(d)$. SD requires the step-size to decrease with the step budget $T$ as well (Definition 4.4). While these scaling are likely not directly applicable to LLMs and would need to be combined with other approaches such as muP, those approaches do not yet consider the scaling of the step-size of the first layer as a function of the vocabulary size.\n\n## Generalizability beyond the model\n> Generalizability: How do you anticipate your results might generalize beyond linear bigram models? \n> Which of your assumptions are most critical and least likely to hold in more complex models?\n\nThe most crucial assumption is the linearity of the model. We do not expect our model to make quantitative testable predictions for LLM training, as many non-linear phenomenon cannot be captured by our model. We do however expect LLMs to exhibit a similar qualitative behavior in terms of training difficulty scaling with $d$.\n\nWe invite you to read [the response to Reviewer pUyz](https://openreview.net/forum?noteId=uPDWwfJLys), [Reviewer xbaC](https://openreview.net/forum?noteId=pIZjJafrGp),\nand [Reviewer 9d42](https://openreview.net/forum?noteId=3xCuAZLexY) for additional experiments and discussions on the generalization to the cross-entropy loss, the use of Adam instead of SD, and the axis-aligned structure of the model in the first and last layers, respectively.\n\n## Recommendations for readability\n\nWe thank you for your suggestions on how to improve the readability of the paper. \nWe will use the additional page for the camera ready to incorporate these suggestions\n(scaling law, data vs. eigenvalues, format of the data $X, Y$, and more explicit definitions). \n\"or\" was indeed meant as \"also known as\", and the instructions will be removed.\n\n---\n\nWe remain available for further clarifications or other questions you may have. \n\n**References**\n- Velikanov and Yarotsky, 2022: arxiv/2202.00992\n- Tao et al., 2024: arxiv/2407.13623"}]

Author rebuttal:

Meta-review: The paper explores scaling laws on a simple linear model with power-law covariance, $\lambda_j = 1/j^{\alpha}$. In particular, this work focuses on the setting where the exponent is $\alpha < 1$. The authors derive the scaling laws for both gradient descent and sign descent. The paper is well-written with rigorous theoretical analysis. All reviewers were fairly positive about the work and thought it was interesting.  While the work is on a simplistic setting, it provides insights and it is a stepping stone to understanding scaling laws of more complex objectives. Overall this is a solid submission.
Decision: Accept (poster)