acceptodds
Under review as a conference paper at ICLR 2027

Better Convergence Guarantees for Sign-Based Momentum Methods

Abstract

This paper presents an improved analysis for sign-based methods with momentum updates. Traditional sign-based methods obtain a convergence rate of under the separable smoothness assumption, but they typically require large batch sizes or assume unimodal symmetric stochastic noise. To address these limitations, we demonstrate that signSGD with momentum can achieve the same convergence rate using constant batch sizes without additional assumptions. We also establish a convergence rate under the -smoothness condition, improving upon the result of prior work by a factor of , where is the problem dimension. Furthermore, we explore sign-based methods in distributed settings and show that the proposed methods yield convergence rates of and , which outperform the previous results of and , respectively. Numerical experiments also validate the effectiveness of the proposed methods.

Primary area:
optimization
Keywords:
Stochastic optimization, non-convex optimization, sign-based methods, convergence guarantees, momentum updates

Reviews

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

This paper provides improved convergence analyses for sign-based optimization methods. For the existing Signum algorithm, the authors improve the dimension dependence of the convergence rate from O(dT−1/4)O(dT^{-1/4}) to O(dT−1/4)O(\sqrt{d}T^{-1/4}). In distributed settings, they establish sharper convergence bounds for majority-vote signSGD and analyze a variant using unbiased stochastic sign compression. The main contributions lie in tighter convergence rates rather than fundamentally new algorithms.

Critical strengths

The paper improves the dependence on the dimension dd and the iteration number TT for existing sign-based methods, leading to better theoretical complexity bounds. Besides, some results are established under weaker conditions than previous work. In particular, the paper achieves convergence rates comparable to variance-reduction-based methods under standard smoothness assumptions, without requiring the stronger average smoothness condition.

Critical weaknesses

The experiments seem insufficient.

  1. The authors do not compare MVSM-v2 with recent variance-reduction-based sign methods, such as SSVR-MV (Jiang W, et al. Efficient sign-based optimization: Accelerating convergence via variance reduction. In Advances in Neural Information Processing Systems 37, pp. 33891–33932, 2024.), which achieve comparable theoretical rates.
  2. Important practical metrics, such as wall-clock time, computational cost, or communication rounds, are missing. These comparisons would help demonstrate the practical benefits of the simpler momentum-based approach.
Questions for authors
  1. The stochastic sign operator SGS_G requires a gradient bound GG, which is generally unknown in practice. How to set this parameter in the experiments?
  2. Could the authors further discuss the constants hidden in the convergence rates and compare them with previous bounds? These constants may significantly affect the practical benefits of the improved rates for finite TT or dd.
5 comments
AuthorsOpenReview ↗

Response to Reviewer 9FKs (Part 1)

We thank the reviewer for the constructive comments and helpful suggestions! We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.


W1. Comparison with SSVR-MV.

Although SSVR-MV achieves the same O(d1/4T−1/4)O(d^{1/4}T^{-1/4}) convergence rate, it further relies on mean-squared smoothness, whereas MVSM-v2 requires smoothness only. Moreover, SSVR-MV evaluates gradients twice at the current and previous iterates. MVSM-v2 instead uses ordinary momentum, requiring only one gradient evaluation per round.

We have also conducted additional experiments comparing our methods with SSVR-MV on the controlled heterogeneous nonconvex problem. The results are shown in Figure 7 in Appendix E.4. As can be seen, MVSM-v2 achieves gradient norms comparable to those of SSVR-MV Option 2. MVSM-v1 also achieves lower values than SSVR-MV Option 1. Since both SSVR-MV variants require two stochastic-gradient evaluations per iteration, MVSM-v2 matches the performance of SSVR-MV Option 2 while using approximately half as many stochastic-gradient evaluations, illustrating the computational advantage of our estimator.


W2. Practical efficiency metrics.

Thank you for this suggestion. We agree that practical efficiency should be assessed through computational cost, communication requirements, and wall-clock time.

Communication costs. For communication, bidirectional sign methods transmit one bit per coordinate, or dd bits for a dd-dimensional vector. The nominal payload per worker in a parameter-server implementation is:

MethodUploadDownload
SGDM / AdamWbdbd bitsbdbd bits
Sign-based methodsdd bitsdd bits

Here, b=32b=32 for FP32 and b=64b=64 for FP64. Sign-based methods include signSGD-MV, Signum-MV, Sto-signSGD, MV-signSGD-SIM, MVSM-v2, etc.

Computational cost. Beyond gradient computation, SGD directly updates the parameters, while SGDM additionally updates a momentum buffer. signSGD applies a coordinate-wise sign operation, and Signum combines this operation with momentum. EF-signSGD additionally corrects the update using accumulated compression errors and updates an error-feedback residual after compression. AdamW maintains both first- and second-moment estimates and performs bias correction, square-root computation, and coordinate-wise division. Overall, Signum retains a simple momentum-and-sign update without error-feedback for EF-signSGD or second-moment normalization for Adam.

Wall-clock time. We additionally measure wall-clock time per epoch. We report the mean and sample standard deviation. Apart from the SSVR-MV method, the execution times of the other methods are relatively similar.

(1) Centralized experiments: ResNet-18 on CIFAR-10.

MethodWall-clock time (s/epoch)
SGDM2.340 ± 0.031
signSGD2.346 ± 0.010
EF-signSGD2.484 ± 0.048
AdamW2.496 ± 0.007
Signum2.371 ± 0.019

(2) Distributed experiments: ResNet-50 on CIFAR-100.

MethodWall-clock time (s/epoch)
signSGD-MV6.779 ± 0.005
Signum-MV7.008 ± 0.006
Sto-signSGD7.144 ± 0.007
MV-signSGD-SIM7.365 ± 0.007
MVSM-v27.517 ± 0.008
SSVR-MV (Option 2)13.391 ± 0.013
AuthorsOpenReview ↗

Response to Reviewer 9FKs (Part 2)

Q1. Choice of the stochastic-sign bound GG.

In the experiments, we initialize G0=1G_0=1. At each iteration, we retain the current value unless an observed stochastic-gradient coordinate exceeds it in absolute value. Specifically, Gt=max⁡Gt−1,max⁡j∈[n]∥gtj∥∞G_t=\max\\{G_{t-1},\max_{j \in[n]}\Vert g_t^j\Vert_\infty\\}, where gtjg_t^j denotes the stochastic gradient computed by worker jj. Since the momentum estimator is a convex combination of current and past stochastic gradients, this nondecreasing bound also ensures ∥vtj∥∞≤Gt\Vert v_t^j\Vert_\infty\le G_t, making the stochastic-sign probabilities valid.


Q2. Dependence on problem constants.

Thank you for this suggestion. We agree that the dependence on problem constants should be explicit when interpreting the convergence rates. Let Δf=f(x1)−f∗\Delta_f=f(x_1)-f_*, LΣ=∑iLiL_\Sigma=\sum_iL_i, and σΣ=∑iσi\sigma_\Sigma=\sum_i\sigma_i. The following bounds concern the expected gradient norm averaged over the iterates.

ResultGradient normExplicit parameter dependence
Theorem 3.1ℓ1\ell_1O((LΣΔf+σΣ)T−1/4)O\left((\sqrt{L_\Sigma\Delta_f}+\sigma_\Sigma)T^{-1/4}\right)
Theorem 3.2ℓ1\ell_1O((LΔf+σ)dT−1/4)O\left((\sqrt{L\Delta_f}+\sigma)\sqrt{d}T^{-1/4}\right)
Theorem 4.2ℓ1\ell_1O(LΔfdT+Gdn)O\left(\sqrt{\frac{L\Delta_f d}{T}}+\frac{Gd}{\sqrt n}\right)
Theorem 4.3ℓ1\ell_1O(LΔfnT+(G+LΔf)dn)O\left(\frac{\sqrt{L\Delta_f n}}{T}+\frac{(G+\sqrt{L\Delta_f})d}{\sqrt n}\right)
Theorem 4.4ℓ2\ell_2O((G2LΔfdT)1/4+LΔfT)O\left(\left(\frac{G^2L\Delta_f d}{T}\right)^{1/4}+\sqrt{\frac{L\Delta_f}{T}}\right)

For comparison, representative previous analyses give the following dependencies.

Previous resultGradient normExplicit parameter dependence
signSGD, Bernstein et al. (2018)ℓ1\ell_1O((LΣ(Δf+1)+σΣ)N−1/4)O\left((\sqrt{L_\Sigma}(\Delta_f+1)+\sigma_\Sigma)N^{-1/4}\right)
SignSGD-SIM, Sun et al. (2023)ℓ1\ell_1O((LΔf+d+σd)T−1/4)O\left((L\Delta_f+d+\sigma\sqrt d)T^{-1/4}\right)
MV-sto-signSGD-SIM, Sun et al. (2023)ℓ1\ell_1O((LΔf+d+σd/n)T−1/4+Gdn)O\left((L\Delta_f+d+\sigma\sqrt{d/n})T^{-1/4}+\frac{Gd}{\sqrt n}\right)
SSVR-MV, Option 1ℓ1\ell_1O(LΔfdT+Gdn)O\left(\sqrt{\frac{L\Delta_f d}{T}}+\frac{Gd}{\sqrt n}\right)
SSVR-MV, Option 2ℓ2\ell_2O([(G2LΔfd)1/4+σ+LΔf]T−1/4)O\left(\left[(G^2L\Delta_f d)^{1/4}+\sigma+\sqrt{L\Delta_f}\right]T^{-1/4}\right)

Dear Reviewer,

Thank you for your constructive comments, which have helped us improve our manuscript. We have addressed each point in our responses and uploaded a revised manuscript with all changes highlighted in blue.

As the discussion period draws to a close, we would appreciate your feedback on our responses and revisions. Please let us know if any concerns remain. We would be happy to provide further clarification.

Reviewer_2scbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary
  • The paper is well-written and easy to follow. The "Source of Theoretical Improvement" remarks help readers to follow much better.
  • Each algorithm either matches or improves upon previous result theoretically. Sometimes previous assumptions are lifted, for example MVSM-v2 achieves similar result to previous sota without the avg smoothness assumption.
Critical strengths
  • The paper is well-written and easy to follow. The "Source of Theoretical Improvement" remarks help readers to follow much better.
  • Each algorithm either matches or improves upon previous result theoretically. Sometimes previous assumptions are lifted, for example MVSM-v2 achieves similar result to previous sota without the avg smoothness assumption.
Critical weaknesses
  • Contribution is quite incremental. Signum and MVSM-v1 are the same as previous methods and MVSM-v2 only changes the server side aggregation. The proof strategy also seem standard, so it is not that other works can really benefit from the analysis here.
  • Thm 4.4 holds for every β∈(0,1]\beta\in(0,1], including β=1\beta=1, i.e., no momentum. Such guarantee does not distinguish with and without momentum cases and cannot provide insight as to whehther or not momentum should be used.
  • In terms of the experiments, it is already known that signum performs similarly to AdamW, as the paper already notes. Also, the LLM results are training loss only and the improvements are quite marginal.
  • Marginal: accuracy and loss plots are quite small and hard to read.
Questions for authors
  • How does Thm 3.2 compare with the O(dK−1/4)O(\sqrt{d}K^{-1/4}) ℓ1\ell_1-norm rate of Lion (Dong et al. (2024))?
  • Thms 4.2–4.3 seem to contain nonvanishing terms? How can we interpret them?
4 comments
AuthorsOpenReview ↗

Response to Reviewer 2scb

We thank the reviewer for the constructive comments! We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.


W1. Contribution of the analysis.

First, although Signum and MVSM-v1 are existing methods, our results improve their previously stated convergence guarantees (Sun et al., 2023). For Signum, we improve the bound from O(dT−1/4)O(dT^{-1/4}) to O(d1/2T−1/4)O(d^{1/2}T^{-1/4}). For MVSM-v1, we improve the bound from O(dT−1/4+dn−1/2)O(dT^{-1/4}+dn^{-1/2}) to O(d1/2T−1/2+dn−1/2)O(d^{1/2}T^{-1/2}+dn^{-1/2}).

Second, the proof is not standard. For example, in the analysis of MVSM-v2, our proof combines the conditional unbiasedness of the worker–server quantization process with a virtual-iterate transformation. Let vˉt\bar v_t and gˉt\bar g_t denote the averaged local momentum and stochastic gradient. The update can be written as vt=vˉt/G+etv_t=\bar v_t/G+e_t, where the communication error ete_t has zero conditional mean and a bounded second moment. We introduce

$y_t=x_t-\frac{\eta(1-\beta)}{G\beta}\bar v_{t-1},
\qquad t\ge 2$.

This construction absorbs the momentum recursion and yields the exact update

yt+1=yt−ηGgˉt−ηet.y_{t+1}=y_t-\frac{\eta}{G} \bar g_t-\eta e_t.

The virtual sequence therefore follows a stochastic-gradient step evaluated at the actual iterate, together with centered communication noise. Crucially, its displacement from the actual sequence satisfies ∥yt−xt∥2≤ηd(1−β)/β\|y_t-x_t\|_2\le\eta\sqrt d(1-\beta)/\beta. Smoothness then controls the gradient mismatch between these sequences, avoiding the need to force the momentum tracking error to vanish at every iteration. These steps identify which properties of compression and momentum are sufficient for the descent argument and offer an analytical template that subsequent work can build upon.


W2. The non-momentum case.

Theorem 4.4 indeed includes the no-momentum case and this actually broadens the applicability of our analysis since it provides a unified convergence guarantee covering both momentum and no-momentum variants.

We also have to emphasize that the objective of our paper is to establish convergence guarantees for sign-based momentum methods. We do not claim that momentum necessarily improves the convergence order over the no-momentum methods. This also arises in classical stochastic optimization: SGD and stochastic momentum methods both admit O(T−1/4)O(T^{-1/4}) convergence guarantees, while momentum can still improve practical performance.

Regarding whether momentum should be used in practice, our experiments provide evidence supporting its use. Figure 1 and Table 1 show that Signum outperforms its no-momentum counterpart, signSGD. Similarly, Figure 2 shows that Signum-MV performs better than signSGD-MV. These comparisons support the use of momentum in the evaluated tasks.


W3. Experimental results.

Thank you for this comment. We would like to emphasize that Signum offers two other practical advantages over AdamW:

  • Communication efficiency. In distributed implementations, Signum requires transmitting only sign information, enabling one-bit communication and reducing communication volume compared with AdamW.

  • Memory efficiency. Signum avoids the additional second-moment accumulator required by AdamW, thereby reducing memory usage.

These resource advantages make achieving performance comparable to AdamW practically valuable.

Regarding the limitation of reporting training loss alone, we have additionally evaluated validation perplexity and included the results in Table 2 of the revised paper. These results show that Signum achieves the best validation perplexity on both GPT-2 and Qwen3, providing evidence of competitive predictive performance beyond the loss on training data.


Q1. Convergence rate of Lion.

In the original version of Dong et al. (2024), their analysis additionally requires coercivity of the objective. In their recently updated version, this assumption has been removed. With weight decay disabled and the two momentum coefficients set equal, Lion reduces to Signum, and their analysis can recover the O(dT−1/4)O(\sqrt{d}T^{-1/4}) rate. We have added a remark to discuss this rate. We also emphasize that our paper’s broader contributions include the distributed convergence guarantees, which address the additional effects of worker aggregation and stochastic sign quantization. Beyond the centralized rate, our bounds on aggregated momentum-estimation error and our virtual-iterate analysis provide analytical tools that may help extend their work to distributed variants of Lion.


Q2. Nonvanishing terms in Theorems 4.2–4.3.

These two bounds contain nonvanishing terms since applying the biased sign operation introduces large estimation bias after compression. We acknowledge this limitation in the original paper, and it is the exact motivation for the MVSM-v2 method. Theorem 4.4 addresses this limitation by establishing an O(d1/4T−1/4)O(d^{1/4}T^{-1/4}) convergence bound for MVSM-v2, which tends to zero as T→∞T\to\infty.

Dear Reviewer,

Thank you for your constructive comments, which have helped us improve our manuscript. We have addressed each point in our responses and uploaded a revised manuscript with all changes highlighted in blue.

As the discussion period draws to a close, we would appreciate your feedback on our responses and revisions. Please let us know if any concerns remain. We would be happy to provide further clarification.

Apologies for the late reply, and thank you for the clarifications and additional experiments. The validation perplexity results address my concern about only presenting the training loss. Unfortunately, my main reservation remains: what additional understanding of sign-based optimization follows from the sharper guarantees is unclear. The updated Lion analysis also recovers the centralized rate. While the distributed results are new, the additional experiments mainly demonstrate algorithmic competitiveness rather than conceptual or practical implications of the improved bounds, and my main concern about incrementality remains. Therefore I keep my socre, but this is provisional, and I will engage in further discussion with the AC and other reviewers before finalizing my assessment.

Thank you for the detailed follow-up and for acknowledging that the validation perplexity results address your concern. We appreciate the opportunity to clarify the additional understanding provided by our analysis.

We would like to emphasize that our distributed results address a further question: which algorithmic ingredients and smoothness conditions are sufficient to obtain the O(T−1/4)O(T^{-1/4}) guarantee under bidirectional one-bit communication?

  1. Our Theorem 4.4 achieves an O(d1/4T−1/4)O(d^{1/4}T^{-1/4}) convergence guarantee with a fixed momentum coefficient and one stochastic-gradient evaluation per worker per round. The corresponding SSVR-MV guarantee uses a variance-reduction estimator, paired gradient evaluations, and the additional mean-squared smoothness assumption. Our analysis shows that these additional ingredients are not necessary to obtain the same dependence on dd and TT in the setting we study. This provides a concrete algorithm-design implication: ordinary momentum already suffices, allowing a simpler implementation with fewer gradient evaluations per round.

  2. The analysis explains why persistent estimation noise need not prevent convergence. The implication of the virtual-iterate argument is that the momentum estimator does not need to approach the exact current gradient at every iteration. The proof handles centered stochastic and communication noise through the descent analysis, while controlling a momentum-induced displacement that shrinks with the step size. Consequently, a fixed momentum coefficient remains compatible with a vanishing stationarity bound. Combined with the conditionally unbiased server aggregation, this also establishes that a nonvanishing residual is not an unavoidable cost of bidirectional one-bit communication. This conclusion concerns what can be guaranteed.

  3. The supplementary experiments illustrate the practical consequence of this simpler design. Our efficiency measurements, reported in the response to Reviewer 9FKs, also give 7.517 s/epoch for MVSM-v2 versus 13.391 s/epoch for SSVR-MV Option 2 under the reported setup. These measurements provide evidence of lower per-epoch cost. Separately, the controlled dimension and worker-count sweeps examine sensitivity to these quantities while holding the other problem constants fixed.

We would appreciate your consideration of these implications in the further discussion with the AC and other reviewers.

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

The paper sharpens convergence guarantees for Signum and distributed sign-based momentum methods. Its main value is theoretical: it relaxes requirements on batch size and noise distributions, improves dimension dependence, and analyzes two-way one-bit communication.

Critical strengths
  1. The constant-batch analysis under separable smoothness removes restrictive noise assumptions while retaining the O(T^{-1/4}) rate.
  2. The improved dimension dependence and the convergence guarantee for MVSM-v2 provide useful refinements to existing sign-based optimization theory.
Critical weaknesses
  1. Distributed implementation details are incomplete. The choice of the bound GG, which determines stochastic-sign probabilities, and the data partition across workers are insufficiently specified. Observing bounded gradients along a finite trajectory does not establish the global assumption.
  2. Experiments only indirectly support the theoretical improvements. Controlled sweeps over dimension and worker count would better test the claimed dependencies. The LLM experiments report training loss alone, providing limited evidence about practical model quality.
Questions for authors

See weaknesses.

4 comments
AuthorsOpenReview ↗

Response to Reviewer Mkjr

We thank the reviewer for the constructive comments! We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.


W1. Distributed implementation details. We have added implementation details and clarified the interpretation of the gradient-norm observations in the revised paper.

  • Choice of GG. In the experiments, we initialize G0=1G_0=1. At each iteration, we retain the current value unless an observed stochastic-gradient coordinate exceeds it in absolute value. Specifically, Gt=max⁡Gt−1,max⁡j∈[n]∥gtj∥∞G_t=\max\\{G_{t-1},\max_{j \in[n]}\Vert g_t^j\Vert_\infty\\}, where gtjg_t^j denotes the stochastic gradient computed by worker jj. Since the momentum estimator is a convex combination of current and past stochastic gradients, this nondecreasing bound also ensures ∥vtj∥∞≤Gt\Vert v_t^j\Vert_\infty\le G_t, making the stochastic-sign probabilities valid.

  • Data partition across workers. In the distributed experiments, we use a balanced IID partition: the training data are randomly divided into eight equally sized, non-overlapping subsets, with one subset assigned to each worker.

  • Scope of the gradient-norm observations. Our intention in reporting these plots was to examine the gradient scales encountered during the experimental runs and check whether extremely large gradient values occur. We agree with the reviewer that observations along finite training trajectories cannot establish the global boundedness assumption. We have revised the discussion in Appendix E.3 to clarify the purpose of these empirical observations and avoid suggesting that they verify Assumption 8.


W2. Experiments only indirectly support the theoretical improvements. Thank you for these suggestions. We have conducted two supplementary evaluations and included the full experimental details and results in the revised manuscript.

  • Controlled dimension and worker-count sweeps. In the original neural-network experiments, changing the dimension requires modifying the architecture and can alter the objective geometry. To isolate the dependencies of interest, we introduce a heterogeneous nonconvex synthetic problem with controlled smoothness, noise-variance bound, initial objective gap, and a fixed G=1.25G=1.25. We vary dd over 16,64,256,1024\\{16, 64, 256, 1024\\} with n=8n=8, and separately vary nn over 2,4,8,16,32\\{2, 4, 8, 16, 32\\} with d=64d=64. We report the gradient norm, averaged over 20 independent runs. As can be seen in the results, increasing dd from 16 to 1024 increases the MVSM-v2 metric from 0.3772 to 1.0622. At fixed d=64d=64, increasing the worker count from 2 to 32 reduces the MVSM-v1 metric from 0.5379 to 0.2478, while MVSM-v2 remains near 0.54. More details can be found in Appendix E.4.

  • Validation perplexity. We agree that training loss alone provides limited evidence of model quality. We therefore additionally evaluate validation perplexity, with lower values indicating better predictive performance. Our method achieves validation perplexity comparable to AdamW on both models, providing evidence of competitive predictive performance beyond the training data.

    MethodGPT-2Qwen3
    SGDM15.106.35
    signSGD11.346.11
    EF-signSGD11.976.05
    AdamW10.816.01
    Ours10.756.00

Dear Reviewer,

Thank you for your constructive comments, which have helped us improve our manuscript. We have addressed each point in our responses and uploaded a revised manuscript with all changes highlighted in blue.

As the discussion period draws to a close, we would appreciate your feedback on our responses and revisions. Please let us know if any concerns remain. We would be happy to provide further clarification.

Thank you for your reply. I will update my score.

Thank you for your positive assessment and for increasing the score! We appreciate your constructive feedback, which has helped us improve our paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.