- 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 and 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, , 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 to . 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 , 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 , replacing inputs by and parameters by , 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 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?
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
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 loglog(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 d, e.g. Figure 2 (left) and Figure 3 at d=104. 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 iterations to reach the threshold 1/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
Please see the global response for details regarding momentum and stochasticity.
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)
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.