acceptodds
Under review as a conference paper at ICLR 2027

The Cross-Entropy Gap: Scaling Laws for Sign and Gradient Descent

10 views

Abstract

Adam is currently one of the most used optimizers in deep learning, yet our understanding of it remains incomplete. We investigate a simple setting, but one that is rich enough to explain the key advantage of sign-like algorithms such as Adam. We analyze next-token prediction under a linear bigram model with Zipfian token frequencies for the -th token, and study gradient descent and sign descent, a common proxy for Adam, under the cross-entropy loss. Although widely used in practice, the cross-entropy loss remains hard to analyze in theory and exact asymptotic results are rare outside restrictive settings. To address this, we introduce a technique of independent interest: a two-stage reduction that matches discrete gradient descent to gradient flow despite a diverging step-size and replaces the coupled softmax flow by a decoupled exponential flow with closed-form trajectories. For sign descent, we use a fixed step-size that balances errors due to progress and oscillations and model the oscillations as independent uniform variables, which matches experimental results. With this method, we are able to show that gradient descent takes on the order of iterations to reach an error , while sign descent needs only , with only logarithmic dependence on the vocabulary size . This gives a strong advantage to sign descent on language tasks and confirms empirically observed behavior. Our predictions are verified on synthetic data and on OpenWebText.

Primary area:
optimization
Keywords:
bigram model, gradient descent, sign descent, adam, cross-entropy, scaling law, asymptotic equivalence

Reviews

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

This paper studies the optimization dynamics of gradient descent (GD) and sign descent (SD) for a linear bigram model under cross-entropy loss, assuming Zipf-distributed input and conditional output frequencies. For GD, the authors establish asymptotic equivalence between discrete optimization, softmax gradient flow, and decoupled exponential dynamics. This gives an explicit asymptotic characterization of the relative excess loss and also predicts sequential learning: more frequent contexts are learned earlier than less frequent ones. For SD, the authors describe initial movement toward moving targets and subsequent bounded oscillations. Under an i.i.d.\ uniform residual assumption, they derive a final relative error formula with 1/T1/T and log⁡(d)/(12T2)\log(d)/(12T^2) regimes. Experiments on synthetic distributions and OpenWebText frequency statistics support the predictions.

The main contributions include

  • A rigorous two-stage reduction from discrete GD to softmax gradient flow and then to decoupled exponential dynamics.

  • Explicit asymptotic predictions for the overall GD loss and per-context learning progress, revealing how input and output frequency imbalance jointly determine learning timescales.

  • A conditional analysis of SD's oscillatory endpoint error, predicting its weak dependence on vocabulary size and the larger GD--SD separation under cross-entropy than under squared loss.

Critical strengths
  • The paper is well organized, and the analysis is clear and easy to follow.

  • The discrete-to-continuous comparison and subsequent exponential reduction are substantive technical contributions.

  • Rather than presenting only upper bounds on convergence rates, the paper gives a limiting GD loss curve. Such predictions provide a more informative characterization of optimization dynamics.

Critical weaknesses
  • The paper closely follows the GD--SD comparison of Kunstner and Bach (2025). Although extending the analysis to cross-entropy requires substantial technical developments and yields different scaling laws, the overall research strategy remains similar. The conceptual contribution is therefore relatively incremental.

  • Figures 2 and 3 reproduce the predicted qualitative behavior, but noticeable gaps remain between the empirical and theoretical curves at the tested vocabulary sizes, especially for OpenWebText experiments in Figure~2 (right).

  • In the token-aligned model, ∇W:,jL=πj(p:,j−π:∣j)\nabla_{W_{:,j}}L=\pi_j(p_{:,j}-\pi_{:|j}), so sign normalization removes the input-frequency factor. The experiments do not assess whether the resulting GD--SD separation persists when input coordinates are mixed.

Questions for authors
  • How would momentum and stochastic sampling change the mechanisms identified here? The conclusion conjectures that momentum could improve GD's vocabulary dependence from d2d^2 to dd. What motivates this conjecture, or what are the main technical obstacles to establishing it?

  • Can closer agreement with the asymptotic predictions be demonstrated? Could the authors quantify the discrepancies in Figures 2 and~3 and explain their dependence on dd, either through a sharper finite-dimensional error analysis or experiments with larger vocabularies?

  • How robust is the separation to coordinate perturbations? For an orthogonal matrix QQ, replacing inputs by QejQe_j and parameters by V=WQ⊤V=WQ^\top, GD is invariant under this transformation, whereas coordinatewise SD generally is not. Could the authors test rotations close to the identity to assess how rapidly SD's advantage changes as alignment is perturbed?

  • Section 4.1 motivates Assumption 4.4 through tractability and the empirical residual histogram. However, unlike the fixed absolute-residual approximation η/2\eta/2 in Kunstner and Bach (2025), it introduces i.i.d.\ uniform random residuals. Could the authors clarify the benefit of this change and the approximation gap relative to deterministic SD?

1 comment

Thank you for your feedback.

We reply to your individual questions in this post, and address common concerns in the separate global response post.

Quality of the approximation

Figures 2 and 3 reproduce the predicted qualitative behavior, but noticeable gaps remain between the empirical and theoretical curves at the tested vocabulary sizes, especially for OpenWebText experiments in Figure~2 (right).

Can closer agreement with the asymptotic predictions be demonstrated? Could the authors quantify the discrepancies in Figures 2 and 3 and explain their dependence on dd, either through a sharper finite-dimensional error analysis or experiments with larger vocabularies?

The discrepancies between the simulation and asymptotic results in Figure 2 (left) and Figure 3 come from the small-d dependency, as the error between the asymptotic prediction scales in log⁡log⁡(d)/log⁡(d)\log\log(d)/\log(d) from our propositions for gradient descent. The simulation however do agree quite well with the asymptotic results even for moderate values of dd, e.g. Figure 2 (left) and Figure 3 at d=104d=10^4. The larger discrepancy noted in Figure 2 (right) come from the fact that it uses real data rather than finite-dimensional approximation issues.

While the big picture behavior still holds (e.g. it still takes on the order of ≈d\approx d iterations to reach the threshold 1/31/3), we do observe faster convergence than on the equivalent finite dimensional problems satisfying the Zipfian assumption, likely because the conditional frequencies of the empirical data do not follow Zipf's law exactly and instead decay faster (see Figure 3 in the work of Kunstner and Bach (2025)). We have updated the caption to make this point more explicit.

Extensions to momentum, stochastic sampling and rotation

How would momentum and stochastic sampling change the mechanisms identified here?

Please see the global response for details regarding momentum and stochasticity.

How robust is the separation to coordinate perturbations? [...] GD is invariant under [rotation], whereas coordinatewise SD generally is not.

Indeed, our problem and analysis is specialized to the structure of the problem and the fact that it is "axis-aligned". our goal is to provide intuition as to why sign descent works well in this setting, where it has been found to be beneficial. The performance of sign descent and Adam has been documented to be sensitive to small changes in rotation (Zhang et al., 2024) and we do not expect to see sign descent improve over gradient descent under coordinate perturbations.

The random residual model for sign descent (Assumption 4.4)

Section 4.1 motivates Assumption 4.4 through tractability and the empirical residual histogram. However, unlike the fixed absolute-residual approximation η/2\eta/2 in Kunstner and Bach (2025), it introduces i.i.d. uniform random residuals. Could the authors clarify the benefit of this change and the approximation gap relative to deterministic SD?

Based on the feedback from all reviewers, we understand that Assumption 4.4 would have benefited from a more detailed motivation. We have added a discussion of the assumption in the main text, and additional plots to justify the assumption.

Please see the global response for details.

Reviewer_ESyKOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper extends the analysis of Kunstner & Bach (2025) for the linear bigram model with Zipfian token frequencies from the squared loss to the cross-entropy loss, comparing gradient descent (GD) and sign descent (SD) as a proxy for Adam. The authors derive asymptotic scaling laws for both methods as the vocabulary size grows. For GD, they develop a reduction to a simpler decoupled dynamics that admits a closed-form analysis. For SD, they rely on a specific choice of stepsize and a probabilistic model of the oscillations around the solution. They conclude that the gap between the two methods is substantially larger under cross-entropy than under the squared loss: the number of iterations of GD grows polynomially with the vocabulary size, whereas that of SD depends on it only logarithmically. Experiments on synthetic and real data are reported as consistent with these predictions.

Critical strengths
  1. The question is well motivated. Why the gap between SD/Adam and GD is larger under cross-entropy than under the squared loss was explicitly left open by Kunstner & Bach (2025).

  2. The GD part is rigorous and, as far as I could verify, correct.

  3. The paper is clearly written and openly discusses its limitations.

Critical weaknesses
  1. The SD result rests on a stepsize choice and an assumption that are justified neither theoretically nor empirically.

The headline SD rate depends entirely on the stepsize η=log⁡(d)/(2T)\eta=\log(d)/(2T), which is not derived from any convergence argument. Proposition 4.3 only shows that this stepsize is necessary for the continuous sign flow to reach the solution; it is not shown to be sufficient for discrete SD, and its optimality is only conjectured.

Moreover, this choice is inconsistent with the stepsizes prescribed by existing convergence analyses of sign descent (Bernstein et al., 2018; Xie et al., ICLR 2025), which scale as 1/T1/\sqrt{T} rather than 1/T1/T. With these stepsizes, the claimed rate is not recovered: under coordinate-wise smoothness, SD needs T≳dlog⁡2dT\gtrsim d\log^2 d iterations just to reach the targets, and under ℓ∞\ell_\infty-smoothness, the authors' own Theorem 4.5 gives O(1/ε)O(1/\varepsilon) instead of log⁡(d)/ε\sqrt{\log(d)/\varepsilon} iterations. Conversely, existing theory gives no convergence guarantee for the proposed stepsize. In addition, under the paper's normalization the ℓ∞\ell_\infty-smoothness constant is bounded by 22, which contradicts the claim in Section 1.2 that it scales with dd.

Empirically, neither choice is validated: the residual histogram (Figure 4) uses an arbitrary stepsize rather than the proposed one, and in Figure 6 the stepsize is grid-searched. Hence the claim in the abstract that the authors "are able to show" the log⁡(d)/ε\sqrt{\log(d)/\varepsilon} rate is overstated.

  1. The asymptotic GD result is not established in the claimed regime and is uninformative at realistic vocabulary sizes.

Theorem 3.5 is a pointwise limit for a fixed rescaled time, with an additive error of order log⁡log⁡d/log⁡d\log\log d/\log d. For any fixed accuracy ε\varepsilon, it implies a number of iterations polynomially smaller than d2d^2, and near the end of training the additive error dominates the predicted value. The claim of d2d^2 iterations as d→∞d\to\infty and ε→0\varepsilon\to0 (Table 1) would therefore require a joint limit, which is not proven.

In practice, the error terms are far from negligible. For a GPT-2-size vocabulary (d≈5⋅104d\approx5\cdot10^4), the actual initial loss gap is about 40%40\% smaller than its asymptotic value used in the analysis, and the bound in Lemma 3.4 already covers most of the range of the relative error. The most frequent contexts, discarded as negligible in Theorem D.3, still carry almost half of the probability mass, and the explicit bound on their contribution exceeds the whole range of the relative error. The proven bounds therefore say nothing about realistic vocabulary sizes, and the agreement in Figure 2 is not explained by the theory.

  1. The contribution is unclear.

For GD, the d2d^2 scaling is intuitive: the Hessian at the optimum has eigenvalues of order πjπk∣j\pi_j\pi_{k|j} and condition number d2d^2, as the authors themselves note. The paper proves a weaker, asymptotic version of this heuristic, which, as discussed in W2, does not cover the claimed d2d^2 regime and is uninformative at realistic vocabulary sizes. The SD part, which is needed for the claimed separation, is questionable for the reasons in W1. Overall, the contribution beyond Kunstner & Bach (2025) is incremental, and the main claim of a provably larger gap under cross-entropy is not fully supported.

  1. Deterministic setting only.

Restricting the analysis to the deterministic setting is reasonable as a first step. However, methods are used in practice with stochastic gradients and momentum. It remains unclear whether results of this kind, and the claimed separation in particular, carry over to SGD, signSGD, or methods with momentum. The authors mention that momentum could improve the dimension dependence of GD from d2d^2 to dd. Can they provide any argument or evidence for this?

  1. The experimental comparison appears asymmetric.

The two methods do not seem to be compared under the same protocol:

  • For GD, the stepsize is fixed by the local stability condition at the optimum, and its near-optimality is checked only at T=dT=d (Figure 7).
  • For SD, the stepsize is tuned separately for every horizon TT, and the reported curves are lower envelopes over horizons (Appendix A).
  • Figure 1 compares relative errors across the squared and cross-entropy losses, whose normalizations differ (the initial cross-entropy gap grows as log⁡d\log d).
  • Adam is run without momentum.

The authors should explain why this protocol yields a fair comparison, or report results with both methods tuned in the same way.

Questions for authors

See Weaknesses

2 comments

Thank you for your feedback.

We reply to your individual questions in this post, and address common concerns in the separate global response post.

2. & 3. Clarity of the results

The asymptotic GD result is not established in the claimed regime [...] the claim in the abstract that the authors "are able to show" the log⁡(d)/ε\sqrt{\log(d)/\varepsilon} rate is overstated.

These comments appear to be based on a miscommunication. We hoped the introduction would give intuition without diving into the technical details, but the simplification may have been misleading. We have updated the abstract and introduction to clarify that the d2d^2 scaling for gradient descent is obtained as a limit of ε→0\varepsilon \to 0 after taking d→∞d \to \infty, and that the sign descent results are conditional on the random residual model. Those are the results we meant to present, and that the reviewer agrees are proven.

1. Justification of the random residuals (Assumption 4.4)

The SD result rests on a stepsize choice and an assumption that are justified neither theoretically nor empirically.

Based on the feedback from all reviewers, we understand that Assumption 4.4 would have benefited from a more detailed motivation. We have added a discussion of the assumption in the main text, and additional plots to justify the assumption.

Please see the global response for details.

Moreover, [the choice of stepsize] is inconsistent with the stepsizes prescribed by existing convergence analyses [...] which scale as 1/T1/\sqrt{T} rather than 1/T1/T.

While this is true, existing analyses work on broader problem classes. The specific setting in this paper allows for larger step-sizes that would not work in the general case. There is no contradiction with the broader literature, as we get tighter results for a more specific problem, and experimental results in Figure 5 and 6 show that 1/T1/T scaling is indeed the correct scaling in TT.

Empirically, neither choice [of stepsize] is validated: the residual histogram (Figure 4) uses an arbitrary stepsize rather than the proposed one, and in Figure 6 [edit: now Figure 7] the stepsize is grid-searched.

We disagree. That the step-size heuristic η=log⁡(d)/2T\eta = \log(d)/2T approximates the optimal step-size at a given budget TT is validated in Figure 5 and 6 (now Figure 5 and 7).

  • Figure 5 shows that the theoretically derived step-size matches the best step-size obtained by grid search at T=1000T=1000 (Left), and that the best step-size follows the η=log⁡(d)/2T\eta = \log(d)/2T (right).
  • Figure 6 (now Figure 7) shows that the theoretical results with η=log⁡(d)/2T\eta = \log(d)/2T (left) match the best performance obtained by grid-search (middle), which is what the theoretical step-size is meant to capture.

In addition, under the paper's normalization the ℓ∞\ell_\infty-smoothness constant is bounded by 22, which contradicts the claim in Section 1.2 that it scales with dd.

This was indeed a mistake; that comment has been removed.

2. Slow convergence to the asymptotic

[The result] is uninformative at realistic vocabulary sizes.

The reviewer is referring to the fact that our bound on the error between the finite-dimensional dynamics and the asymptotic regime is of order O(log⁡log⁡(d)/log⁡(d))O(\log\log(d)/\log(d)) for GD. We agree that the convergence is slow, and added a paragraph highlighting this in the main text. However, our empirical results indicate reasonable agreement between simulation and the asymptotic results even for moderate dd, much better than what would be expected from log⁡log⁡(d)/log⁡(d)\log\log(d)/\log(d) (see e.g. d=104d=10^4 in Figure 2). The real approximation error is likely smaller than our worst-case bound, but the resulting the asymptotic limit is a good approximation even at realistic dd.

4. Restrictive setting

The authors mention that momentum could improve the dimension dependence of GD from d2d^2 to dd. Can they provide any argument or evidence for this?

Please see the global response for details regarding momentum and stochasticity.

5. Asymmetric experiments

The two methods do not seem to be compared under the same protocol: [...] The authors should explain why this protocol yields a fair comparison

We use a fixed step-size for GD and a step-size that depends on the horizon TT for SD because those are the standard ways to run the two algorithms in the theoretical literature. GD can use a constant step-size that depends on curvature, while SD needs to know the horizon to reach arbitrarily small error. This is the same setup used by Kunstner and Bach (2025).

  • Figure 1 compares relative errors [...] whose normalizations differ

Figure 1 compare relative errors precisely to allow comparison of optimization speed when both errors scale differently in dd.

  • Adam is run without momentum [in Figure 1].

Adam is run without momentum because all other methods do not have momentum.

I thank the authors for the detailed response and the revision. The corrected statements of the GD result (Table 1), the added discussion of the slow convergence, and the removal of the ℓ∞\ell_\infty-smoothness claim address part of my concerns.

However, my main concern remains. The revision makes explicit that the SD result holds only under the random residual model, which the authors state is not literally true. The step-size η=log⁡(d)/(2T)\eta=\log(d)/(2T) is still justified only by a necessary condition for the continuous flow, and its sufficiency for discrete SD is not proven. Moreover, the new experiments show that with this step-size the weights enter the oscillatory regime only after TT, so Assumption 4.4 holds only for a larger step-size (1.05η1.05\eta), not for the one used in Theorem 4.5. The weaker moment-based condition mentioned in the response is not stated formally, the discrepancy between the 2η2\eta bound of Proposition 4.2 and the [−η,η][-\eta,\eta] support is not discussed, and the period-2 oscillations of order 1/T1/T (Appendix A), which are inconsistent with the i.i.d. model, remain unaddressed. As a result, the rigorous contribution of the paper reduces to the asymptotic GD result, which converges slowly and confirms an intuitive scaling.

I therefore keep my score.

Reviewer_yH5aOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper compares gradient descent and sign descent on cross-entropy loss in a linear bigram model with Zipfian token frequencies. It derives a large-dimension scaling law for gradient descent by connecting the discrete dynamics to gradient flow and then to a decoupled exponential system. For sign descent, it models the final oscillation residuals as independent uniform variables and obtains a much weaker dependence on vocabulary size. Experiments compare the predictions with synthetic Zipf data and empirical OpenWebText bigram frequencies.

Critical strengths
  1. The paper addresses a clear question left by the square-loss analysis of the same Zipfian bigram model: how the optimizer comparison changes under cross-entropy.
  2. The two-stage reduction from discrete GD to gradient flow and then to an exponential system is a substantial technical contribution. It provides more information than a condition-number argument alone.
  3. The synthetic and empirical-frequency experiments help assess the predictions, and the paper explicitly acknowledges the simplified setting and the heuristic nature of the SD residual model.
Critical weaknesses
  1. The SD result is conditional on a strong assumption about the final trajectory. Assumption 4.4 requires all coordinates to have reached the oscillatory regime at T, with independent uniform residuals, at eta = log(d)/(2T). Proposition 4.3 only gives a necessary step-size bound for continuous sign flow; it does not establish that the discrete algorithm reaches this regime at the boundary step size. A residual histogram that looks approximately uniform also does not establish independence or control the contribution of coordinates that have not reached their targets. Theorem 4.5 is useful under the model, but should not be presented on the same footing as a convergence result derived from the actual GD dynamics. Can the authors quantify the residual approximation or give an explicit step-size margin under which the prediction is justified?
  2. The step-size range covered by the GD proof is unclear. The main text uses eta = 1/lambda_max at the optimum, asymptotically equivalent to H_d squared. In Lemma D.2, the discrete argument uses 1 - eta_eff*pi_k = 1 - 1/(kj) >= 0, which specializes to eta = H_d squared. The proof should state whether it covers only this choice or also the broader constant-factor range discussed in the paper.
  3. The scope of the optimizer comparison is limited. The setting is deterministic, momentum-free, and based on a linear bigram model with a specific Zipf distribution. The paper itself conjectures that momentum could improve the GD dimension dependence from d squared to d, which could change the comparison substantially.
Questions for authors
  1. At eta = log(d)/(2T), what fraction of coordinates has entered the oscillatory regime by T, and what is the loss contribution of those that have not? Can the uniform-residual approximation be checked across dimensions and horizons, including residual dependence and small increases in eta?
  2. Which step sizes does the discrete-GD proof actually cover? Please reconcile Lemma D.2 with eta = 1/lambda_max and the constant-factor range discussed in the main text.
  3. Can the plots include predictions normalized by the exact finite-dimension initial excess loss, alongside the asymptotic normalization log(d)/2? This would help separate finite-dimension effects from errors in the dynamical approximation.
  4. How do momentum and context-dependent empirical bigram distributions change the observed scaling? Even a controlled experiment in the same linear model would clarify which conclusions are robust to these extensions.
  5. The deterministic setting is clearly stated and reasonable. It would be helpful to discuss whether the proposed explanation extends to mini-batch training, where sign estimation can be biased and rare contexts may be absent from a batch.
1 comment

Thank you for your feedback.

We reply to your individual questions in this post, and address common concerns in the separate global response post.

1. Random residual model for sign descent (Assumption 4.4)

At η=log⁡(d)/(2T)\eta = \log(d)/(2T), what fraction of coordinates has entered the oscillatory regime by T, and what is the loss contribution of those that have not? Can the uniform-residual approximation be checked across dimensions and horizons, including residual dependence and small increases in eta?

Thank you for the plotting suggestion.

Based on the feedback from all reviewers, we understand that Assumption 4.4 would have benefited from a more detailed motivation. We have added a discussion of the assumption in the main text, and additional plots to justify the assumption.

Please see the global response for details.

2. The step-size range covered by the GD proof is unclear

Which step sizes does the discrete-GD proof actually cover? Please reconcile Lemma D.2 with η=1/λmax⁡\eta = 1/\lambda_{\max} and the constant-factor range discussed in the main text.

We have updated the submission to be more explicit about the step-size covered, both in the main text and in the statements of the results. The results hold for η=Hd2\eta = H_d^2.

3. Finite-dimension errors

Can the plots include predictions normalized by the exact finite-dimension initial excess loss, alongside the asymptotic normalization log(d)/2? This would help separate finite-dimension effects from errors in the dynamical approximation.

The plots show the normalized error. The theoretical prediction uses the theoretically derived asymptotics, while the empirical results use the finite-dimension optimality gap at initialization.

Our understanding is that you are suggesting to replace the 12log⁡(d){\frac{1}{2}\log(d)} normalization term in the theoretical curves by the initial optimality gap Ld(0)−Ld∗{\mathcal{L}_d(0)-\mathcal{L}_d^*}, as a finite-dimension corrections to the denominator, while leaving the numerator at its asymptotic value.

Unfortunately, while this change corrects for small-d effect in the denominator, it does not fully account for such errors in the dynamical approximation because the numerator also has similar small-d effects. Applying finite-dimension corrections only to the denominator can make the prediction worse if those effects cancel out, which is the case here; with this correction, the relative error (which is supposed to start at 1), would instead start at ≈2.5,2,1.8\approx 2.5, 2, 1.8 for d=102,103,104d = 10^2, 10^3, 10^4.

4. and 5. Extensions to momentum and stochastic setting

How would momentum [...] change the observed scaling?

It would be helpful to discuss whether the proposed explanation extends to mini-batch training

Please see the global response for details regarding momentum and stochasticity.

How would [...] context-dependent empirical bigram distributions change the observed scaling?

We note that our theory covers the case where the bigram distribution is conditional on the input. Although Assumption 2.2 assumes each conditional distribution is the same, changing them by a permutation so that which next word is most likely leads to the same dynamics, as long as they're still Zipf-distributed.

An experiment using empirical bigram distributions is given in Figure 2 (right), where the frequencies are estimated from OpenWebText with varying vocabulary size under Byte Pair Encoding. While the big picture behavior still holds (e.g. it still takes on the order of ≈d\approx d iterations to reach the threshold 1/31/3), we do observe faster convergence than on the equivalent finite dimensional problems satisfying the Zipfian assumption, likely because the conditional frequencies of the empirical data do not follow Zipf's law exactly and instead decay faster (see Figure 3 in the work of Kunstner and Bach (2025)). We have updated the caption to make this point more explicit.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank all reviewers for their feedback.

We have updated the paper to address the concerns raised; changes made to address specific concerns are highlighted in blue. Since the original submission, we also have substantially improved the organization of the appendix; the content is the same, but the structure should be easier to navigate.

This response addresses common concerns raised by all reviewers.

Random residual model for sign descent (Assumption 4.4)

Based on the feedback from all reviewers, we understand that Assumption 4.4 would have benefited from a more detailed motivation. We have added a discussion of the assumption in the main text, and additional plots to justify the assumptions.

The additions clarify the following questions, which were raised by multiple reviewers:

  • How much of the independence assumption is actually needed?
  • Can we provide evidence that the oscillatory regime is reached?
  • Is the uniformity assumption really valid?

Assumption 4.4 is meant as a simplification; we observe empirically that the residuals reach a roughly uniform distribution after TT steps with step-size η=log⁡(d)/2T\eta = \log(d)/2T, and assume that they are indeed i.i.d. U[−1,1]{U}[-1,1] to simplify the analysis. We do not claim this property is literaly true; only that it is a useful simplified model. This assumption is much stronger than what is technically needed to prove the main result. We do not need the independence of the residuals, only some control over the weighted mean and variance of the residuals, specifically ηδk\eta \delta_k and exp⁡(ηδk)\exp(\eta\delta_k), which appear in the loss.

While it is possible to prove the needed bounds directly, covering all possible regimes would require a long and technical analysis. The purpose of the assumption is to avoid these 20 pages of technical lemmas which are unlikely to be of great interest to readers, as the dynamics of sign descent with a constant step-size on the Zipfian bigram model is a highly specialized setting. We made this decision to focus the technical part of the paper on the analysis of gradient descent on the cross-entropy loss, which is much more likely to be of interest.

We give more evidence that random residuals is a reasonable models in Section 4.1 and Figure 6, showing that

  • The weights enter the fully oscillatory regime around TT steps when using a step-size close to η=log⁡(d)/2T\eta = \log(d)/2T, showing that the heuristic used to derive the step-size is reasonable. Specifically, all the residuals indeed enter the oscillatory regime slightly after TT iterations with a step-size η=log⁡(d)/2T\eta = \log(d)/2T, and all the residuals have entered the oscillatory regime at time TT for a slightly larger step-size η′=1.05η\eta' = 1.05 \eta
  • We show that the property we need from the uniformity assumption, that moments of the residuals match the expected values from the uniform-residual assumption, with that same step-size η′\eta' after TT steps.

Extensions beyond deterministic gradient descent

All reviewers have asked in some form about the possible extension of the results presented here to methods with momentum, or to the stochastic setting.

Stochasticity. We do not expect to see the same behavior in the stochastic setting. Prior work on the benefit of sign descent and Adam-like methods has shown that the benefit of sign descent is most prominent in the deterministic setting (Kunstner et al. 2023), and there is little gain to using sign descent over gradient descent with small minibatches (Marek et al. 2024, Srećković et al. 2025). While those results are on large transformer, we do not expect to be able to show much improvement in the stochastic setting on the bigram model, at least not without big changes to sign descent to make it stable. We have updated the paper to include this discussion.

Momentum. Our comment in the paper that momentum was likely to improve the dimension dependence of gradient descent from d2d^2 to dd was based on the intuition that momentum helps to accelerate convergence from a condition number κ\kappa to κ\sqrt{\kappa}, and the fact that the (pseudo-)condition number of the Hessian at the optimum is d2d^2. While we hope the reduction to the continuous time limit we introduce can help address this setting, we do not have a clear idea of how to extend the proof to momentum, as the analysis of momentum methods on non-linear algorithms is difficult. We have updated the paper to include this discussion, and to show some experimental results that suggest that momentum does improve the dimension dependence over gradient descent in Figure 8, Appendix A.1.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.