acceptodds
Under review as a conference paper at ICLR 2027

Provable Benefit of SignGD: A Minimal Model under Heavy-Tailed Class Imbalance

Abstract

Adaptive and non-Euclidean optimizers often outperform stochastic gradient descent (SGD) in language modeling by a large margin. Existing theory usually explains this gap by assuming favorable smoothness geometry or noise structure tailored to the specific optimizer. We instead ask whether such geometry can be induced from a concrete learning problem. Starting from an optimizer gap on realistic language-modeling experiments, we progressively remove sequence dependence, architectural complexity, and stochasticity. We find that the gap exists in a minimal setting: the softmax unigram model with heavy-tailed class imbalance. We prove that GD learns rare tokens slowly because the corresponding logits receive small updates, while SignGD removes this magnitude dependence and moves rare and common coordinates on a more comparable scale. We make this precise with upper and lower bounds for the convergence rate of GD and upper bounds for the convergence of SignGD. In the stochastic setting, we prove that mini-batch noise masks rather than creates this advantage, with sufficiently large batches yielding a separation between SignSGD and GD.

Primary area:
optimization
Keywords:
non euclidean steepest descent, heavy tailed class imbalance, softmax unigram, Adam, SignGD

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_cXywOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the advantages of signGD under imbalanced classes. The authors establish a minimal setting to study the difference in convergence rate between signGD, GD, and normalized steepest descent under specific initialization and other assumptions. Experimental evidence is also provided to validate their claims.

Critical strengths
  • This paper establishes convergence results across multiple algorithms and both deterministic and stochastic settings, and propose a minimal setting to study these algorithms.
Critical weaknesses
  • The presentation of theoretical results and emphasis of the story are not clear enough. See questions. Also, the abstract does not seem to cover all the strengths. Emphasizing the minimal setting is good; however, if there are no clear properties revealed behind these convergence results, I would suggest still focusing on the difference between these algorithms, which is the main strength of this paper.
Questions for authors
  • Does Theorem 4.1 only work for learning rate η=2\eta=2? If so, what is the intuition for this? What if both Theorem 4.1 and 4.2 are not initialized at 0? Which part will fail in the current analysis?
  • The statement of Theorem 4.3 seems a bit weak, since it assumes the trajectory is bounded and the objective is convex and Lipschitz smooth. However, the explanation below it indicates stronger results if I understand it correctly (the bounded trajectory is proved instead of assumed in each algorithm; also, bounded trajectory and Lipschitz smoothness is repeated if the function is for example C^1). It would be better if the statement could be revised to ensure better interpretation. The overall organization of Section 4.2 (including all statements of the theorem and corollaries) is readable but not in its strongest and cleanest version.
  • Existing literature sometimes uses normalized GD to understand spectral methods, where signGD roughly belongs to this family. Results in this paper show the difference. I wonder what is the reason behind this and what is special about signGD compared to different level/versions of spectral methods. It would be good if the author could provide a brief discussion on this.
2 comments

We thank the reviewer for the time and effort spent reading and engaging with our work! We are glad that the reviewer recognizes that our paper establishes convergence results across multiple algorithms and both deterministic and stochastic settings. We now answer their questions.

Clarity

  • The presentation of theoretical results and emphasis of the story are not clear enough

We thank the reviewer for their feedback on our presentation and have incorporated their suggestions into the main draft.

  • I wonder what is the reason behind this and what is special about signGD compared to different level/versions of spectral methods. It would be good if the author could provide a brief discussion on this.

Thank you for raising this point. Could you please clarify what you mean by “spectral methods” in this context, perhaps with a reference? Our understanding is that these methods typically apply to matrix-valued weights, and we would like to ensure we address the intended comparison.

Learning Rate Guarantees

  • Does Theorem 4.1 only work for learning rate η=2\eta =2.

We can modify Theorem 4.1 so that it holds for η<2=1/L2\eta < 2 = 1/L_2 . The learning rate η=2\eta = 2 is the largest learning rate that guarantees convergence under the standard smoothness-based condition and larger learning rates may fail to converge. In Theorem F.4., we show that GD is unstable near any minimizer of the softmax unigram model for η≳log⁡d\eta \gtrsim \log d Nevertheless, our main comparison is using the lower bound of GD which covers a large interval of learning rates, 0<η<d/20 < \eta < d/2. The upper bound is supplementary and provides additional theoretical evidence of the worse dimensional dependence of the ℓ2\ell_2 geometry for the softmax unigram model.

Initialization

  • What if both Theorem 4.1 and 4.2 are not initialized at 0? Which part will fail in the current analysis?

Although our current theorems are stated with zero initialization for clarity, the conclusions extend to the commonly used initialization θ0∼N(0,σ2I)\theta_0 \sim \mathcal{N}(0, \sigma^2 I) for small σ\sigma. For arbitrary θ0\theta_0, the NSD-WD theorem bound depends on D=max⁡∥θ0∥,1/λD = \max\\{\lVert\theta_0\rVert, 1/\lambda\\}. For θ0∼N(0,σ2I)\theta_0 \sim \mathcal{N}(0, \sigma^2 I) we can average the theorem over initialization and use the fact that E∥θ0∥∞2=O(σ2log⁡d)\mathbb{E}\lVert\theta_0\rVert_\infty^2 = O(\sigma^2\log d) and E∥θ0∥22=σ2d\mathbb{E}\lVert\theta_0\rVert_2^2 = \sigma^2 d to obtain O(((log⁡d)2+σ2log⁡d)/T)O(((\log d)^2 + \sigma^2\log d)/T) bound for SignGD-WD and O(d(1+σ2)/T)O(d(1 + \sigma^2)/T) for normalized GD-WD. Hence, we recover the poly-log dd dependent bound for SignGD-WD and the dd dependent bound for normalized GD-WD. Without weight decay, adjusting the horizon-tuned stepsizes to the initial distance gives the same bounds with an additional log⁡T\log T factor, since the initial logit distance is at most log⁡d+2∥θ0∥∞\log d+2\lVert\theta_0\rVert_\infty and the expected squared Euclidean distance to a minimizer is O(d(1+σ2))O(d(1+\sigma^2)). The GD lower bound also extends in expectation: each initial dyadic log-ratio is θ0,i−θ0,2i∼N(0,2σ2)\theta_{0,i}-\theta_{0,2i}\sim\mathcal N(0,2\sigma^2), and a constant fraction remain sufficiently close to zero for the original slow-progress argument to apply, changing only a σ\sigma-dependent constant. Thus, both the upper-bound comparison and the polynomial GD lower bound are robust to standard Gaussian initialization and can be extended to schemes that initialize close to zero.

Concluding remarks

We thank the reviewer again for their valuable feedback. We hope that our rebuttal addresses their questions and concerns, and we kindly ask the reviewer to consider a fresher evaluation of our paper if the reviewer is satisfied with our responses. We are also more than happy to answer any further questions that arise.

Dear Reviewer,

We wanted to follow up on our rebuttal and would appreciate any additional feedback on whether our responses have addressed your concerns. We would be happy to provide further clarification if needed. Thank you again for your time and consideration.

Reviewer_iHZPOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies why SignGD can work better than GD in language modeling using a simple model with Zipfian token frequencies. The authors prove that SignGD converges much faster than GD in this setting and explain this by showing that SignGD learns rare tokens more efficiently. Moreover, stochastic variants and momentum technique are also provided. To verify their findings, the authors conduct numerical experiments.

Critical strengths

I can emphasize following strengths:

  1. Theoretical results. The authors provide a substantial number of convergence results for different variants of the methods (with and without stochasticity, and with momentum). I went through the appendix and did not find any technical flaws. I would particularly like to highlight Theorem 4.2, which is fundamental to the authors' conclusion about difference between SignGD and GD. Its proof is nontrivial and interesting in its own right.

  2. The idea of simplifying the model to better understand the behavior of optimizers, despite the existing literature on the topic, is something I have not encountered before, and it seems interesting. In particular, this approach is what allows the authors to formulate the problem (1).

Critical weaknesses

Despite the advantages, I must mention some shortcomings:

  1. To the best of my knowledge, there are already works that investigate the differences in geometry induced by different norms (in particular, the ℓ∞\ell_\infty and ℓ2\ell_2 norms). For example, [1] studies the similarity between L∞L_\infty and L2L_2. Moreover, it seems to me that the main improvement comes from the different scaling of distances under these norms due to L∞∼L2L_\infty \sim L_2. This is particularly evident in Theorem 4.3 and Corollary 4.4.

  2. The theoretical model is highly simplified. The main results are proved for a softmax unigram model with Zipfian token frequencies. This setting is very different from actual language model training, where parameters are shared across tokens and optimization involves many interacting layers. It is unclear whether the theoretical separation extends to more realistic models.

  3. The stochastic results do not establish the same strong separation. Although the paper extends its analysis to stochastic optimization and momentum, the results mainly provide upper bounds for different methods. These bounds alone do not prove that stochastic SignGD necessarily outperforms its competitors. Therefore, the strongest theoretical result remains restricted to the deterministic setting.


References

[1] Balles et al. (2020). The Geometry of Sign Gradient Descent

Questions for authors
  1. Could GD reach a fixed accuracy much faster with a larger learning rate, even if such a learning rate makes the optimum unstable?
2 comments

We would like to thank the reviewer for the time they spent on reviewing our work! We are glad that the reviewer found our simplified model interesting and the proof of Theorem 4.2 to be non-trivial and interesting in its own right. We now address their concerns.

Novelty

  • To the best of my knowledge, there are already works that investigate the differences in geometry induced by different norms (in particular, the ℓ2\ell_2 and ℓ∞\ell_\infty norms). Moreover, it seems to me that the main improvement comes from the different scaling of distances under these norms.

We appreciate the reviewer’s observation and the opportunity to clarify the framing of our contributions in terms of prior work. Indeed, our theory indicates that SignGD is beneficial for the softmax unigram model because the ℓ∞\ell_\infty smoothness constant is not much worse than the ℓ2\ell_2 constant but the distance scaling is favourable for SignGD due to is coordinate-wise normalization. Rather than assuming these abstract conditions, one of our main contributions is to rigourously show how this favourable geometry is induced from a concrete next token prediction problem. We begin by isolating the key mechanisms for the optimizer gap in real transformer language modelling experiments. Then, from the softmax activation, cross-entropy loss, and heavy-tailed token distribution, we establish the smoothness and trajectory-distance properties, and combine the SignGD guarantee with a novel GD lower bound to prove the separation between optimizers. This gives a complete chain of reasoning from the specific learning problem to a theoretical explanation of the optimizer gap. Overall, we use the norm-dependent convergence framework as a tool to show why conditions favourable to the ℓ∞\ell_\infty geometry arise in the softmax unigram learning problem and establish the resulting separation as a main contribution.

Furthermore, prior work in optimization theory typically postulates benefits of non-Euclidean methods by assuming optimizer-friendly geometry, e.g., anisotropic smoothness, coordinate-wise smoothness and then derive generic convergence guarantees [3, 4]. These type of results clarify which algorithms may potentially benefit from which assumptions but they don’t answer how a particular favourable geometry emerges in a concrete learning problem connected to real world training setups. For example, Balles et al. 2020 assume separable smoothness, L2L_2 smoothness and L∞L_\infty smoothness to derive convergence rates. They propose abstract and general conditions where there might be benefits of the ℓ∞\ell_\infty geometry. But they do not analyze norm distance scaling, derive lower bounds to prove a separation, or study problems beyond 2D quadratics.

On the other hand, we rigorously prove a separation between the geometries directly from properties of the architecture and data distribution. We propose a novel concrete learning problem derived from real world training setups and directly prove the advantages of SignGD. Instead of considering a quadratic model as a proxy, the softmax unigram model is motivated by simplifying the transformer architecture step by step and isolates the heavy-tailed class imbalance property. We also extend the analysis to the stochastic setting. This suggests that, despite its simplicity, the softmax unigram model captures at least one aspect of the dynamics, namely, the tail-learning bottleneck observed in transformer training. Furthermore, this phenomenon is an important contributor to the observed benefits of adaptive/non-Euclidean optimizers such as Adam in practice [2].

Scope

  • The theoretical model is highly simplified. The main results are proved for a softmax unigram model with Zipfian token frequencies.

We politely direct the reviewer to the response to Reviewer Fnyi where we extend our analysis to general power laws.

  • This setting is very different from actual language model training, where parameters are shared across tokens and optimization involves many interacting layers.

We thank the reviewer for raising this concern. Our motivation is to isolate a phenomenon that also appears in transformer training: SGD makes slow progress on low-frequency tokens, whereas SignSGD progresses more uniformly across frequency groups (Figure 2). Our ablations in Figure 3 connect the Transformer and unigram settings, showing that the optimizer gap persists as we progressively simplify the architecture. The resulting model still couples parameters through the softmax activation while allowing us to derive rigorous discrete-time upper and lower bounds. We view this as a step toward understanding more complex language model training. For a more detailed discussion of the model’s scope and its connection to transformers, we kindly refer the reviewer to our response to Reviewer Fnyi.

AuthorsOpenReview ↗

Rebuttal Cont.

Stochastic Lower Bounds

  • Although the paper extends its analysis to stochastic optimization and momentum, the results mainly provide upper bounds for different methods.

We acknowledge the reviewer’s concern regarding the stochastic bounds. Although we provide upper bounds, our stochastic analysis is indeed informative and clarifies how mini-batch noise affects SignSGD’s deterministic advantage. The bounds and experiments indicate that noise suppresses this advantage at small batch sizes, while larger batches allow it to become visible. We verify this phenomenon empirically and show that SGD can outperform SignSGD at small batch sizes in both transformer experiments in Figure 7 and the softmax unigram model in Figure 5.

Furthermore, we do provide a separation between the upper bound of SignSGD and the lower bound for GD at large batch sizes. Therefore, we rigorously establish that large batch SignSGD can outperform even full-batch GD for large enough batch sizes.

To address whether the small-batch upper bounds reflect actual performance, we additionally analyze B=1B=1. With Section 5’s parameter choices, we prove that SignSGD improves on its initialization loss by at most O(1/log⁡d)O(1/\log d) in expectation, regardless of the number of iterations. This matches the order of its Θ(log⁡d)\Theta(\log d) noise floor and establishes a separation in favor of SGD for sufficiently large token budgets

Proof sketch for B=1B=1. Write f(θ)=KL(p∣softmax⁡(θ))f(\theta)=\mathrm{KL}(p\\|\operatorname{softmax}(\theta)), where pi=1/(iHd)p_i=1/(iH_d), and let ℓ=log⁡d\ell=\log d. Use Section 5’s initialization and parameters:

θ0=0,λ=2ℓ,η=ℓlog⁡T2T.\theta_0=0,\qquad\lambda=\frac2\ell,\qquad\eta=\frac{\ell\log T}{2T}.

For qt=softmax⁡(θt)q_t=\operatorname{softmax}(\theta_t), the stochastic sign satisfies:

sign⁡(qt−eξt)=1−2eξt.\operatorname{sign}(q_t-e_{\xi_t})=\mathbf1-2e_{\xi_t}.

Consequently, the exact discrete-time update gives

EθT=aT(p−121),aT=ℓ[1−(1−log⁡TT)T]∈[0,ℓ].\mathbb E\theta_T=a_T\left(p-\tfrac12\mathbf1\right),\qquad a_T=\ell\left[1-\left(1-\frac{\log T}{T}\right)^T\right]\in[0,\ell].

Adding a common constant to the logits leaves softmax unchanged. Convexity therefore yields

\mathbb E f(\theta_T) &\ge f(\mathbb E\theta_T)=f(a_Tp) \\\\ &=f(0)+\log\left(\frac1d\sum_i e^{a_Tp_i}\right) -a_T\\|p\\|_2^2 \\\\ &\ge f(0)-\ell\\|p\\|_2^2. \end{aligned}$$ Since $H_d\ge\ell$ and $\sum_i i^{-2}\le\pi^2/6$, we obtain, for every $T\ge2$, $$\mathbb E f(\theta_T)\ge f(0)-\frac{\pi^2}{6\log d}=\frac12\log d-\log\log d+O(1).$$ Thus, the $\Theta(\log d)$ noise floor in the SignSGD upper bound is unavoidable at $B=1$. For comparison, $B=1$ gives token budget $N=T$. For $N\ge d$, SGD with step size $\sqrt{d/N}$ and averaged logits satisfies $$\mathbb E f(\bar\theta_N^{\mathrm{SGD}})\le2\sqrt{\frac dN}\le2.$$ For sufficiently large $d$, this is strictly below the SignSGD lower bound whenever $N\ge d$. The same lower bound holds for deterministic averages of the SignSGD parameters, so averaging does not remove the separation. ## Unstable Learning Rates - *Could GD reach a fixed accuracy much faster with a larger learning rate, even if such a learning rate makes the optimum unstable?* GD can reach a fixed accuracy faster with a larger unstable learning rate but SignGD is still significantly faster. We verify this empirically by running the experiments in the main Figure 1 again but select the learning rate that achieves the best loss at any iterate along the run instead of the last iterate. We used the original grids: $\mathcal G_{\rm GD}=\\{10^{k/4}:k=0,\ldots,12\\}$ and $\mathcal G_{\rm SignGD}=\\{10^{k/4}:k=-12,\ldots,-4\\}$. We run SignGD and GD for $T = 600$ iterations as in Figure 1 and summarize the findings in the table below. | Optimizer | Selected learning rate | Minimum KL loss | | --- | --- | --- | | GD | 56.234 | $1.3629\times10^{-2}$ | | SignGD | 0.01 | $1.5045\times10^{-5}$ | This improves GD’s loss by $3.18\times$ over last-iterate selection, while SignGD still achieves approximately ****906× lower loss. Theorem 4.2 provides a lower bound for GD to reach a fixed target accuracy and aligns with this empirical finding as it covers large learning rates that are in the unstable regime (Theorem F.4) $0 < \eta < d/2$. ## Concluding Remarks We hope that our responses were sufficient in clarifying all the great questions asked by the reviewer. We thank the reviewer again for their time, and we politely encourage the reviewer to consider updating their score if they deem that our responses, along with our new experiments, in this rebuttal merit it. ## References [1] Kunstner and Bach, Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models, 2025 [2] Kunstner et al., Why Adam Outperforms GD on Language Models, 2024. [3] Liu et al., Adagrad under Anisotropic Smoothness, 2024 [4] Xie et al., Adam Exploits $\ell_\infty$-geometry of Loss Landscape, 2025
Reviewer_FnyiOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper compares convergence rates of sign(S)GD and (S)GD optimization algorithms with the aim of understanding whether the benefits of using the former can come from the geometry induced by a specific language learning problem. To do so, the authors first find a theoretically tractable minimal model that when trained with these algorithms still exhibits experimental performance gap similar to that of a more realistic language model. The model they consider is the softmax unigram model with data coming from a heavy tailed Zipf distribution. The authors provide lower and upper bounds on the convergence under cross-entropy loss (or equivalently KL) for GD and upper bounds for SignGD, thus proving that SignGD converges in less iterations. The interoperation for this observation is due to the fact that GD provably gives smaller updates to rare data examples compared to SignGD, which becomes more important under heavy tailed distribution. On the other hand, when analyzing their stochastic counterparts with weight decay, the authors are able to prove benefits of SignSGD over normalized SGD only once the batch size is large enough. The authors supplement these theoretical findings with numerical and real experiments throughout the paper.

Critical strengths

I believe the minimal theoretical model is well motivated and the main insight extracted from it is simple, yet convincing. Firstly, the transition from experimental observation to theory analysis, as done in Figures 2 and 3, gives convincing motivation for exploring the model. Moreover, I find the analysis of the theoretical model in Sections 4 and 5 to be sound, and informative, as it gives a convincing explanation where the benefit of SignGD could lie.

Additionally, not a critical strength, but something I appreciate is that supporting real and numerical experiments are integrated throughout the sections of the main body in a way that supports and motivates the main findings.

Critical weaknesses
  1. Finite sample results from Section 5 so far aim at explaining the phenomenon only for batch sizes being much larger. I think, in order to understand better the benefits of SignSGD in practice, it would be important to analyze finite sample regime guarantees more tightly, with lower bounds, checking under which circumstances the benefit do and do not hold.

  2. While I believe that the minimal theoretical model is well motivated as a first step of analyzing the gap between SignGD and GD, I believe it is a bit limited in its scope and that there could be more to understand about this gap by considering a more general model. Firstly, the only data distribution considered is Zipf's, and I think it would good to see whether this phenomenon is true for a larger family of (heavy tailed) distributions, e.g. with some different power law structure, or if this was the consequence of the specific data distribution choice. Moreover, understanding more complex models that take into account context, learned embeddings or non convex optimization would give insights whether there exist other drivers for the gap between SignSGD over SGD in language modeling.

Questions for authors
  1. Would you expect the upper bounds in Section 5 to be tight, implying that SignSGD would indeed be worse than SGD for not too large of a batch size?

  2. What are the properties of the data distribution that you think would be crucial for the gap between SignGD and GD to be noticeable?

  3. Do you expect that SignGD moving rare and common coordinates on a more comparable scale is the main driver for its benefit over GD also in the more complicated language learning tasks? Do you expect this to also be true for Adam or could there be some interaction with context information, token embeddings and non-convex optimization that could lead to a more nuanced phenomenology contributing to the gap?

4 comments

We would like to thank the reviewer for the time and effort they spent engaging with our work! We are glad that the reviewer found that our minimal theoretical model is well motivated and the main insight extracted from it is simple, yet convincing.

General Distributions/Different Power Laws

The only data distribution considered is Zipf's, and I think it would good to see whether this phenomenon is true for a larger family of (heavy tailed) distributions, e.g. with some different power law structure, or if this was the consequence of the specific data distribution choice.

We thank the reviewer for this suggestion. We can indeed extend our analysis to other distributions. For instance, consider the upper bound for SignGD with WD.

Suppose pp is an arbitrary probability distribution with no zero entries, and let

f_p(\theta)= \mathrm{KL}\\!\left( p\\,\middle\\|\\,\operatorname{softmax}(\theta)\right).

The minimizer set is

\mathcal{X}^{\star} = \left\\{\log p+c\mathbf{1}:c\in\mathbb{R} \right\\}.

The minimum ℓ∞\ell_\infty radius is therefore

R∞:=min⁡θ⋆∈X⋆∥θ⋆∥∞=min⁡c∈Rmax⁡i∣log⁡pi+c∣.R_\infty:=\min_{\theta^{\star}\in\mathcal{X}^{\star}}\lVert\theta^{\star}\rVert_\infty=\min_{c\in\mathbb{R}}\max_i |\log p_i+c|.

To determine R∞R_\infty, we can follow the calculation in the proof of Lemma A.2, which computes the minimizer with minimal ℓ∞\ell_\infty norm for Zipf's law. The derivation strategy is not specific to the structure of pp. Thus, we find that

R∞=12log⁡(pmax⁡pmin⁡),R_\infty=\frac{1}{2}\log\left(\frac{p_{\max}}{p_{\min}}\right),

where pmax⁡=max⁡ipip_{\max}=\max_i p_i and pmin⁡=min⁡ipip_{\min}=\min_i p_i. By Lemma A.1, the Hessian of fpf_p does not depend on pp, and the objective is 11-smooth in ℓ∞\ell_\infty. Thus, the NSD-WD theorem gives the following bound for SignGD with WD:

fp(θT)−fp⋆≤8R∞2T=2log⁡2(pmax⁡/pmin⁡)T.f_p(\theta_T)-f_p^{\star}\leq\frac{8R_\infty^2}{T}=\frac{2\log^2(p_{\max}/p_{\min})}{T}.

For pi∝i−αp_i\propto i^{-\alpha}, this becomes 2α2(log⁡d)2/T2\alpha^2(\log d)^2/T. Therefore, the SignGD upper bound only depends on α\alpha through a constant and retains the polylogarithmic dependence on dd. SignGD remains effective across values of α\alpha because its coordinate-wise sign update does not depend on the gradient magnitude, allowing head and tail logits to move on a comparable scale despite changes in token-frequency imbalance.

We can also extend the GD lower-bound argument to general α\alpha. As in our α=1\alpha=1 proof, consider the disjoint coordinate pairs i,2i\\{i,2i\\} for odd ii. Their target log-odds gap is

log⁡pip2i=αlog⁡2,\log\frac{p_i}{p_{2i}}=\alpha\log 2,

whereas the GD dynamics imply

0≤log⁡qT,iqT,2i≤ηT(pi−p2i)=ηT(1−2−α)iαHd,α.0\leq\log\frac{q_{T,i}}{q_{T,2i}}\leq\eta T(p_i-p_{2i})=\frac{\eta T(1-2^{-\alpha})}{i^{\alpha}H_{d,\alpha}}.

Consequently, for

\right)^{1/\alpha},$$ GD has learned at most a constant fraction of the required log-odds gap. The conditional KL divergence within each such pair is bounded below by an $\alpha$-dependent constant. Summing over the disjoint unresolved pairs using the KL chain rule gives $$f_p(\theta_T)-f_p^{\star} \gtrsim_\alpha \frac{1}{H_{d,\alpha}} \sum_{\substack{ i\gtrsim_\alpha(\eta T/H_{d,\alpha})^{1/\alpha} \\\\ i\leq d/2,\\ i\\ \mathrm{odd} }} i^{-\alpha}.$$ Evaluating this power-law tail sum yields the following bounds: $$\begin{array}{c|c} \text{Exponent} & \text{GD lower bound} \\\\ \hline 0 < \alpha < 1 & \displaystyle f_p(\theta_T)-f_p^{\star} \gtrsim_\alpha \left[ 1-C_\alpha \left(\frac{\eta T}{d}\right)^{(1-\alpha)/\alpha} \right]_+ \\\\[3mm] \alpha=1 & \displaystyle f_p(\theta_T)-f_p^{\star} \gtrsim \frac{1}{\log d} \left[ \log\left(\frac{d\log d}{\eta T}\right) \right]_+ \\\\[3mm] \alpha > 1 & \displaystyle f_p(\theta_T)-f_p^{\star} \gtrsim_\alpha \left[ (1+\eta T)^{-(\alpha-1)/\alpha} -d^{1-\alpha} \right]_+ \end{array}$$ Consequently, at fixed sufficiently small accuracy, $$\begin{array}{c|c} \text{Exponent} & \text{GD iteration lower bound} \\\\ \hline 0 < \alpha < 1 & \displaystyle T_{\mathrm{GD}}(\epsilon) \gtrsim_\alpha \frac{d}{\eta} \\\\[3mm] \alpha=1 & \displaystyle T_{\mathrm{GD}}(\epsilon) \gtrsim \frac{d^{\\,1-C\epsilon}\log d}{\eta} \\\\[3mm] \alpha > 1 & \displaystyle T_{\mathrm{GD}}(\epsilon) \gtrsim_\alpha \frac{\log d}{\eta} \end{array}$$
AuthorsOpenReview ↗

Rebuttal Cont.

For α>1\alpha > 1, the GD bound depends logarithmically on dd at fixed accuracy because the distribution becomes concentrated on the head token, so GD just needs to learn an order-log⁡d\log d logit gap. The largest separation between GD and SignGD-WD occurs for 0<α≤10 < \alpha\leq 1, i.e., when the distribution is heavy-tailed. GD requires polynomially many iterations in dd to reach a fixed sufficiently small error, while SignGD-WD still has an Oα((log⁡d)2/T)O_{\alpha}((\log d)^2/T) bound with polylogarithmic dependence on dd.

We experimentally verified different values of α\alpha using GD with η=2\eta=2 and SignGD without weight decay, with the learning rate suggested by the deterministic analysis in Section 4. Both algorithms are initialized at θ0=0\theta_0=0. We define the hitting time for both algorithms as

T_\epsilon=\min\left\\{t:f_\alpha(\theta_t)\leq\epsilon\right\\},

with ϵ=0.05\epsilon=0.05. We report the empirical speedup

Remp(α,d)=TϵGDTϵSignGD.R_{\mathrm{emp}}(\alpha,d)=\frac{T_\epsilon^{\mathrm{GD}}}{T_\epsilon^{\mathrm{SignGD}}}.

For α=0.5\alpha=0.5, the theoretical scalings suggest

TϵGD=Ω(d),TϵSignGD=O~((log⁡d)2).T_\epsilon^{\mathrm{GD}}=\Omega(d),\qquad T_\epsilon^{\mathrm{SignGD}}=\widetilde{\mathcal{O}}((\log d)^2).

Hence,

Rpred(d)=C^,d(log⁡d)2,R_{\mathrm{pred}}(d)=\widehat{C}\\,\frac{d}{(\log d)^2},

where C^\widehat{C} is a multiplicative constant fitted across dimensions. We fit the empirical ratio to this curve and obtain:

\text{Dimension }d & \text{Empirical speedup} & \text{Predicted speedup} & \text{Empirical / predicted} \\\\ \hline 4{,}096 & 23.0 & 24.4 & 0.944 \\\\ 8{,}192 & 40.2 & 41.6 & 0.966 \\\\ 16{,}384 & 72.9 & 71.7 & 1.017 \\\\ 65{,}536 & 236.8 & 219.6 & 1.078 \end{array}$$ The predicted $d/(\log d)^2$ shape describes the observed speedup as dimension increases. We also run scaling experiments for different values of $\alpha$. $$\begin{array}{c|r|r} \alpha & \text{Dimension }d & \text{Empirical speedup} \\\\ \hline 0.5 & 4{,}096 & 23.0 \\\\ 0.5 & 8{,}192 & 40.2 \\\\ 0.5 & 16{,}384 & 72.9 \\\\ 0.5 & 65{,}536 & 236.8 \\\\ \hline 1 & 4{,}096 & 7.0 \\\\ 1 & 8{,}192 & 12.0 \\\\ 1 & 16{,}384 & 20.8 \\\\ 1 & 65{,}536 & 64.4 \\\\ \hline 2 & 4{,}096 & 2.3 \\\\ 2 & 8{,}192 & 3.0 \\\\ 2 & 16{,}384 & 3.9 \\\\ 2 & 65{,}536 & 5.9 \end{array}$$ For the heavy-tailed regimes $\alpha\leq 1$, the GD/SignGD gap grows strongly with dimension, as predicted by the theory. In contrast, for the head-dominated regime $\alpha=2$, the speedup grows more modestly, consistent with the weaker dimension dependence predicted for $\alpha > 1$. These results are consistent with both the polylogarithmic SignGD guarantee and the predicted change in GD behavior across the $\alpha=1$ boundary.

Significance and Scope

I believe it is a bit limited in its scope and that there could be more to understand about this gap by considering a more general model.

We believe this simplicity is a strength. Our findings indicate that specific architectural components, e.g., LayerNorm and attention mechanisms, are not necessary for the optimizer gap and motivate studying the softmax unigram model. In Figure 2(a), SignSGD achieves lower overall training loss than SGD on the Transformer trained on the PTB dataset. The frequency-grouped curves in Figures 2(b,c) reveal that SGD does not make progress minimizing the loss on low-frequency tokens, whereas SignSGD makes more uniform progress across frequency groups and alleviates this tail-learning bottleneck. Each group contains approximately the same fraction of training tokens, so slow progress on the tail has a meaningful effect on the overall loss. The same pattern also appears in the softmax unigram experiments in Figures 1(c,d). Our ablations in Figure 3 connect these two experiments. The optimizer gap persists even when we freeze the embeddings and attention and train only the classification head, remove attention to obtain a bigram model, and finally share a single embedding across tokens to obtain a unigram model.

Furthermore, while prior work has shown empirical evidence for the tail-learning bottleneck, a rigorous theoretical explanation is lacking. Our contribution is therefore to isolate this mechanism in a minimal model and derive a direct, nontrivial theoretical explanation for the advantage of non-Euclidean methods such as SignGD over GD.

Additionally, prior works analyze the performance of SignGD over GD only on diagonal quadratic models or in continuous time settings [1, 2]. Instead of using a quadratic proxy, we introduce a new model obtained directly from simplifying the Transformer architecture. Unlike these simpler diagonal quadratic models, which are separable, the parameters of the softmax unigram model are coupled through the softmax operation. Despite this additional complexity, we provide a clear separation between algorithms by deriving discrete time upper and lower bounds. We believe that our specifically scoped contributions can lay the groundwork for developing theory for more complicated Transformer training setups and modern adaptive optimizers.

Stochastic Results

I think, in order to understand better the benefits of SignSGD in practice, it would be important to analyze finite sample regime guarantees more tightly, with lower bounds, checking under which circumstances the benefit do and do not hold. Would you expect the upper bounds in Section 5 to be tight, implying that SignSGD would indeed be worse than SGD for not too large of a batch size?

We politely direct the reviewer to our discussion with Reviewer iHZP.

Questions

What are the properties of the data distribution that you think would be crucial for the gap between SignGD and GD to be noticeable?

We thank the reviewer for this question. Could you please clarify whether you mean in general or specifically in the unigram setting? In the unigram setting, our analysis identifies two key properties: a large number of classes dd, and power-law class probabilities with exponent 0<α≤10 < \alpha\leq 1.

Do you expect that SignGD moving rare and common coordinates on a more comparable scale is the main driver for its benefit over GD also in the more complicated language learning tasks?

We believe that coordinate-wise normalization, as used by SignGD and adaptive optimizers such as Adam, is a key contributor to their advantage over GD in language modeling. Figure 2 shows that, when training a Transformer with SignGD, the loss on low-frequency tokens decreases at a rate comparable to that on high-frequency tokens. In contrast, GD makes little progress on low-frequency tokens. In Appendix Section N.1, we also verify that Adam decreases the loss on low- and high-frequency tokens at comparable rates. Beyond token-frequency imbalance, other architectural properties of Transformers, including context-dependent representations and embedding structure, may also contribute to differences in gradient magnitudes across coordinates.

Concluding remarks

We thank the reviewer again for their valuable feedback. We hope that our rebuttal addresses their concerns, and we kindly ask the reviewer to consider a fresh evaluation of our paper if they are satisfied with our responses. We are also more than happy to answer any further questions that arise.

References

[1] Kunstner and Bach, Scaling Laws for Gradient Descent and Sign Descent for Linear Bigram Models under Zipf's Law, 2025. [2] Kunstner et al., Heavy-Tailed Class Imbalance and Why Adam Outperforms GD on Language Models, 2024. [3] Liu et al., Adagrad under Anisotropic Smoothness, 2024. [4] Xie et al., Adam Exploits ℓ∞\ell_\infty-geometry of Loss Landscape via Coordinate-wise Adaptivity, 2025.

I thank the authors for their response, especially regarding the additional results for more general distributions and the new lower bounds. While I do agree that the simplicity of this setup has benefits, especially in terms of isolating potential minimal explanation, I think there could still be room for a more nuanced theoretical explanation of the phenomenon with exploration of how/whether additional realistic components contribute to the full explanation of the gap between SignGD and GD. That being said, I can see this as being outside of the scope, and view your paper as motivating further exploration.

I will keep my score, as it was already positive, and add that my impression of the paper improved after the rebuttal.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.