CoChat
Sign Up
PreprintCited by 541Stochastic Gradient Optimization TechniquesMachine Learning and Data ClassificationDistributed Control Multi-Agent Systems

signSGD: Compressed Optimisation for Non-Convex Problems

Open access
Bernstein, Jeremy, Wang, Yu-Xiang, Azizzadenesheli, Kamyar, Anandkumar, Anima·2018·arXiv
DOI 10.48550/arxiv.1802.04434arXiv 1802.04434
Open this paper in CoChat — free accountOpen PDF

Abstract

Training large neural networks requires distributing learning across multiple workers, where the cost of communicating gradients can be a significant bottleneck. signSGD alleviates this problem by transmitting just the sign of each minibatch stochastic gradient. We prove that it can get the best of both worlds: compressed gradients and SGD-level convergence rate. The relative $\ell_1/\ell_2$ geometry of gradients, noise and curvature informs whether signSGD or SGD is theoretically better suited to a particular problem. On the practical side we find that the momentum counterpart of signSGD is able to match the accuracy and convergence speed of Adam on deep Imagenet models. We extend our theory to the distributed setting, where the parameter server uses majority vote to aggregate gradient signs from each worker enabling 1-bit compression of worker-server communication in both directions. Using a theorem by Gauss we prove that majority vote can achieve the same reduction in variance as full precision distributed SGD. Thus, there is great promise for sign-based optimisation schemes to achieve fast communication and fast convergence. Code to reproduce experiments is to be found at https://github.com/jxbz/signSGD .

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1802.04434

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • RMSProp, SignSGD and its momentum-based variants, NAdam, AMSGrad, RAdam, and Lion are instances of an associative memory that aims to compress the gradients.

    “we discuss other similar algorithms such as RMSProp (Hinton et al. 2012), SignSGD and its momentum-based variants (Bernstein et al. 2018), NAdam (Dozat 2016), AMSGrad (Reddi et al. 2016), RAdam (Liu et al. 2020), and Lion (Chen et al. 2023) are also instances of an associative memory that aims to compress the gradients.”

    From Nested Learning: The Illusion of Deep Learning Architectures (2025) · cites this paper as Bernstein et al. 2018

    The Abstract (p. 1) says SIGNSGD compresses gradients by transmitting their signs, and §5 (p. 7) identifies SIGNUM as its momentum-based counterpart. The paper does not describe either algorithm as an associative memory; the other optimizers in the sentence have separate citations and are not attributed to this source. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • Based on connections of Adam with other algorithms and AdaGrad's connection with Shampoo and Soap, all these optimizers can be re-formulated as associative memory that aims to compress the gradients.

    “we can conclude that all these optimizers can be re-formulated as associative memory that aims to compress the gradients.”

    From Nested Learning: The Illusion of Deep Learning Architectures (2025) · cites this paper as Bernstein et al. 2018

    The SIGNUM passage (p. 1) describes signSGD as gradient compression, and Related Work (p. 2) connects signSGD with Adam. Neither passage reformulates optimizers as associative memory, and the cited evidence does not establish that all the named optimizers aim to compress gradients. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

  • signSGD's focus is to mitigate communication costs between agents in distributed training, and it observes inferior performance when training ConvNets on image classification tasks.

    “Their focus is to mitigate communication costs between agents in distributed training, and they observe inferior performance when training ConvNets on image classification tasks.”

    From Symbolic Discovery of Optimization Algorithms (2023) · cites this paper as Bernstein et al., 2018

    The Abstract (p. 1) says signSGD aims to reduce communication costs in distributed training. Figure 3 (Section 5, p. 7) reports that its momentum variant, SIGNUM, performs about 2% worse than SGD with well-tuned weight decay on ImageNet. The claim overgeneralizes that result: Figure A.3 (p. 11) reports little difference in final test performance on CIFAR-10. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • The sign operation has been explored in previous optimizers.

    “The sign operation has been explored in previous optimizers (Bernstein et al., 2018; Riedmiller and Braun, 1993).”

    From Symbolic Discovery of Optimization Algorithms (2023) · cites this paper as Bernstein et al., 2018

  • The closest previous optimizer to Lion is signSGD (and its momentum variant), which also uses the sign operation but has a different momentum update rule.

    “The closest to ours is the handcrafted optimizer signSGD (Bernstein et al., 2018) (and its momentum variant) that also utilizes the sign operation to calculate the update but has a different momentum update rule from Lion.”

    From Symbolic Discovery of Optimization Algorithms (2023) · cites this paper as Bernstein et al., 2018

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 35

  1. Akiba, T., Suzuki, S., and Fukuda, K. Extremely Large Minibatch SGD: Training ResNet-50 on ImageNet in 15 Minutes. arXiv:1711.04325 , 2017. · arXiv
  2. Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding. In Advances in neural information processing systems (NIPS-17) , 2017.
  3. Allen-Zhu, Z. Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter. In International Conference on Machine Learning (ICML17) , 2017a.
  4. Allen-Zhu, Z. Natasha 2: Faster Non-Convex Optimization Than SGD. arXiv:1708.08694 , 2017b. · arXiv
  5. Balles, L. and Hennig, P. Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients. arXiv:1705.07774 , 2017. · arXiv
  6. Boyd, S. and Vandenberghe, L. Convex Optimization . Cambridge University Press, 2004.
  7. Carlson, D., Hsieh, Y., Collins, E., Carin, L., and Cevher, V . Stochastic spectral descent for discrete graphical models. IEEE Journal of Selected Topics in Signal Processing , 10 (2):296-311, 2016.
  8. Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., and Bengio, Y. Identifying and Attacking the Saddle Point Problem in High-Dimensional Non-Convex Optimization. In Advances in neural information processing systems (NIPS-14) , 2014.
  9. Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research , 12:2121-2159, 2011.
  10. Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization , 23(4):2341-2368, 2013.
  11. Glorot, X. and Bengio, Y. Understanding the Difficulty of Training Deep Feedforward Neural Networks. In Artificial intelligence and statistics (AISTATS-10) , 2010.
  12. Goodfellow, I. J., Vinyals, O., and Saxe, A. M. Qualitatively Characterizing Neural Network Optimization Problems. In International Conference on Learning Representations (ICLR-15) , 2015.
  13. Goyal, P., Doll´ ar, P., Girshick, R. B., Noordhuis, P., Wesolowski, L., Kyrola, A., Tulloch, A., Jia, Y., and He, K. Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour. arXiv:1706.02677 , 2017. · arXiv
  14. He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR-16) , pp. 770-778, 2016a.
  15. He, K., Zhang, X., Ren, S., and Sun, J. Identity mappings in deep residual networks. In European Conference on Computer Vision (ECCV-16) , pp. 630-645. Springer, 2016b.
  16. Jin, C., Netrapalli, P., and Jordan, M. I. Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent. arXiv:1711.10456 , 2017. · arXiv
  17. Karimi, H., Nutini, J., and Schmidt, M. Linear convergence of gradient and proximal-gradient methods under the Polyak-łojasiewicz condition. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD-16) , pp. 795-811. Springer, 2016.
  18. Kingma, D. P. and Ba, J. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations (ICLR-15) , 2015.
  19. Knuth, D. E. The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms . Addison-Wesley Longman Publishing Co., Inc., 1997.
  20. LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. Nature , 521(7553):436, 2015.
  21. Li, M., Andersen, D. G., Park, J. W., Smola, A. J., Ahmed, A., Josifovski, V., Long, J., Shekita, E. J., and Su, B.-Y . Scaling Distributed Machine Learning with the Parameter Server. In Symposium on Operating Systems Design and Implementation (OSDI-14) , pp. 583-598, 2014.
  22. Loshchilov, I. and Hutter, F. Fixing Weight Decay Regularization in Adam. arXiv:1711.05101 , 2017. · arXiv
  23. MacKay, D. J. C. Information Theory, Inference & Learning Algorithms . Cambridge University Press, 2002.
  24. Nesterov, Y. Introductory Lectures on Convex Optimization: A Basic Course . Springer, 2013.
  25. Reddi, S. J., Kale, S., and Kumar, S. On the Convergence of Adam and Beyond. In International Conference on Learning Representations (ICLR-18) , 2018.
  26. Richt´ arik, P . and Tak´ aˇ c, M. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Mathematical Programming , 144 (1-2):1-38, 2014.
  27. Riedmiller, M. and Braun, H. A Direct Adaptive Method for Faster Backpropagation Learning: the RPROP Algorithm. In International Conference on Neural Networks (ICNN93) , pp. 586-591. IEEE, 1993.
  28. Robbins, H. and Monro, S. A Stochastic Approximation Method. The Annals of Mathematical Statistics , 1951.
  29. Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision , 115(3): 211-252, 2015.
  30. Seide, F., Fu, H., Droppo, J., Li, G., and Yu, D. 1-Bit Stochastic Gradient Descent and Application to DataParallel Distributed Training of Speech DNNs. In Conference of the International Speech Communication Association (INTERSPEECH-14) , 2014.
  31. Smith, S. L. and Le, Q. V. A Bayesian Perspective on Generalization and Stochastic Gradient Descent. In International Conference on Learning Representations (ICLR18) , 2018.
  32. Strom, N. Scalable distributed DNN training using commodity GPU cloud computing. In Conference of the International Speech Communication Association (INTERSPEECH-15) , 2015.
  33. Suresh, A. T., Yu, F. X., Kumar, S., and McMahan, H. B. Distributed Mean Estimation with Limited Communication. In International Conference on Machine Learning (ICML-17) , 2017.
  34. Wen, W., Xu, C., Yan, F., Wu, C., Wang, Y., Chen, Y., and Li, H. TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning. In Advances in neural information processing systems (NIPS-17) , 2017.
  35. Wilson, A. C., Roelofs, R., Stern, M., Srebro, N., and Recht, B. The Marginal Value of Adaptive Gradient Methods in Machine Learning. In Advances in neural information processing systems (NIPS-17) , 2017.

Cited by

Sorted by citations

Authors
Bernstein, J., Wang, Y.-X., Azizzadenesheli, K., & Anandkumar, A.
Affiliations
  • California Institute of Technology (US)
  • Carnegie Mellon University (US)
  • Stanford University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2018
Pages
559-568
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1802.04434
arXiv
1802.04434
OpenAlex
W2786602455
Cited by
541
References
0
Citations by year
2026: 1 · 2025: 38 · 2024: 105 · 2023: 131 · 2022: 90 · 2021: 101 · 2020: 60 · 2019: 15
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • CaltechAUTHORS (California Institute of Technology) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (1254106)
  • Air Force Office of Scientific Research (FA9550-, -15-1-, FA9550-15-1-0221)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
  • Physical Sciences › Computer Science › Computer Networks and Communications › Distributed Control Multi-Agent Systems
Keywords
signSGD, gradient compression, non-convex optimization, stochastic gradient descent, momentum, majority voting, distributed training, parameter server, communication efficiency, convergence rate, variance reduction, neural network training

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review