- 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 to . 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 and the iteration number 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.
- 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.
- 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
- The stochastic sign operator requires a gradient bound , which is generally unknown in practice. How to set this parameter in the experiments?
- 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 or .
5 comments
Response to Reviewer 9FKs (Part 2)
Q1. Choice of the stochastic-sign bound .
In the experiments, we initialize . At each iteration, we retain the current value unless an observed stochastic-gradient coordinate exceeds it in absolute value. Specifically, , where denotes the stochastic gradient computed by worker . Since the momentum estimator is a convex combination of current and past stochastic gradients, this nondecreasing bound also ensures , 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 , , and . The following bounds concern the expected gradient norm averaged over the iterates.
| Result | Gradient norm | Explicit parameter dependence |
|---|---|---|
| Theorem 3.1 | ||
| Theorem 3.2 | ||
| Theorem 4.2 | ||
| Theorem 4.3 | ||
| Theorem 4.4 |
For comparison, representative previous analyses give the following dependencies.
| Previous result | Gradient norm | Explicit parameter dependence |
|---|---|---|
| signSGD, Bernstein et al. (2018) | ||
| SignSGD-SIM, Sun et al. (2023) | ||
| MV-sto-signSGD-SIM, Sun et al. (2023) | ||
| SSVR-MV, Option 1 | ||
| SSVR-MV, Option 2 |
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.
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) 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 d bits for a d-dimensional vector. The nominal payload per worker in a parameter-server implementation is:
Here, b=32 for FP32 and b=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.
(2) Distributed experiments: ResNet-50 on CIFAR-100.