Escaping Saddle Points with Compressed SGD

Dmitrii Avdiukhin, Grigory Yaroslavtsev

Abstract

Stochastic gradient descent (SGD) is a prevalent optimization technique for large-scale distributed machine learning. While SGD computation can be efficiently divided between multiple machines, communication typically becomes a bottleneck in the distributed setting. Gradient compression methods can be used to alleviate this problem, and a recent line of work shows that SGD augmented with gradient compression converges to an $\varepsilon$-first-order stationary point. In this paper we extend these results to convergence to an $\varepsilon$-second-order stationary point ($\varepsilon$-SOSP), which is to the best of our knowledge the first result of this type. In addition, we show that, when the stochastic gradient is not Lipschitz, compressed SGD with RandomK compressor converges to an $\varepsilon$-SOSP with the same number of iterations as uncompressed SGD [Jin et al., 2021], while improving the total communication by a factor of $\tilde \Theta(\sqrt{d} \varepsilon^{-3/4})$, where $d$ is the dimension of the optimization problem. We present additional results for the cases when the compressor is arbitrary and when the stochastic gradient is Lipschitz.

Introduction

In the landscape of large-scale distributed machine learning, Stochastic Gradient Descent (SGD) stands as the primary optimization workhorse. However, as models grow in complexity and datasets expand, the "communication bottleneck"—the time spent transmitting massive gradient vectors between machines—has become a significant hurdle. While gradient compression techniques have been developed to mitigate this, existing theoretical guarantees have largely been limited to finding First-Order Stationary Points (FOSPs), where the gradient is zero.

In non-convex landscapes typical of deep learning, a zero gradient does not guarantee a local minimum; it often indicates a saddle point. This paper provides the first theoretical proof that compressed SGD can successfully escape these saddle points to reach Second-Order Stationary Points (SOSPs), ensuring higher-quality solutions in distributed environments.

Methodology: Perturbation and Error-Feedback

The authors introduce Algorithm 1: Compressed SGD with Perturbation and Error-Feedback. This framework relies on three critical mechanisms to ensure convergence to an SOSP while maintaining communication efficiency:

  1. Artificial Noise (Perturbation): The algorithm injects a small amount of random Gaussian noise ($\xi_t$) into the gradient at each iteration. This perturbation acts as a catalyst, providing the necessary "kick" to move the optimization path away from precarious saddle points and toward directions of negative curvature that lower the loss.
  2. Error-Feedback: To prevent the information loss inherent in compression from leading to divergence, the algorithm utilizes an error-feedback mechanism. By storing the compression residual and adding it back into the subsequent gradient calculation, the method ensures that the accumulated compression error remains bounded and does not drift from the true gradient direction.
  3. Compressor Analysis: The study distinguishes between general compressors and linear compressors, such as RandomK (which selects $k$ random coordinates). The authors demonstrate that linear compressors allow for tighter mathematical bounds because their error characteristics are more predictable and easier to control during the optimization process.

Theoretical Contributions

This work establishes the first convergence guarantees to SOSPs for any form of compressed SGD. A key insight is the "Linearity Advantage": the RandomK compressor allows the algorithm to reach an SOSP in the same number of iterations as uncompressed SGD, but with significantly reduced data transmission.

Specifically, for non-Lipschitz gradients, the authors prove a communication improvement factor of approximately $\tilde{\Theta}(\sqrt{d}\varepsilon^{-3/4})$, where $d$ represents the problem dimension. Even when gradients are Lipschitz, the RandomK compressor reduces the total communication per worker by a factor of $\tilde{\Theta}(\varepsilon^{-1/4})$. These results suggest that the "jitter" introduced by noise is not just a byproduct of stochasticity but a functional feature that enables the discovery of escape routes from saddle points.

Empirical Evaluation

The theoretical framework was validated using two distinct experimental setups:

  • CIFAR-10 with ResNet34: This setup tested the algorithm's performance on a standard high-dimensional image classification task across 10 distributed machines.
  • MNIST with Deep Autoencoders: This architecture was specifically chosen as a "stress test" because deep autoencoders are known to encounter prominent saddle points.

In the MNIST experiments, standard SGD without noise frequently became trapped at saddle points characterized by near-zero gradient norms but high loss. In contrast, the noisy compressed SGD proposed by the authors escaped these points rapidly. Remarkably, the algorithm achieved performance nearly identical to full, uncompressed SGD while utilizing only 1% of the communication bandwidth.

Conclusion and Future Work

This research bridges a critical gap in distributed optimization theory, proving that communication efficiency does not have to come at the cost of solution quality. While the results are robust, the authors identify a $\sqrt{\varepsilon}$ gap in their final bounds that may be a subject for future mathematical refinement. Additionally, future work may explore the integration of these techniques with variance-reduction methods (like SPIDER or SARAH) to further optimize convergence rates in complex non-convex landscapes.

Summary updated

Abstract

Stochastic gradient descent (SGD) is a prevalent optimization technique for large-scale distributed machine learning. While SGD computation can be efficiently divided between multiple machines, communication typically becomes a bottleneck in the distributed setting. Gradient compression methods can be used to alleviate this problem, and a recent line of work shows that SGD augmented with gradient compression converges to an $\varepsilon$-first-order stationary point. In this paper we extend these results to convergence to an $\varepsilon$-second-order stationary point ($\varepsilon$-SOSP), which is to the best of our knowledge the first result of this type. In addition, we show that, when the stochastic gradient is not Lipschitz, compressed SGD with RandomK compressor converges to an $\varepsilon$-SOSP with the same number of iterations as uncompressed SGD [Jin et al.,2021] (JACM), while improving the total communication by a factor of $\tilde \Theta(\sqrt{d} \varepsilon^{-3/4})$, where $d$ is the dimension of the optimization problem. We present additional results for the cases when the compressor is arbitrary and when the stochastic gradient is Lipschitz.
BibTeX
@inproceedings{avdiukhin2021escaping,
  author = {Dmitrii Avdiukhin and Grigory Yaroslavtsev},
  title = {{Escaping Saddle Points with Compressed SGD}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=prF4ONaS51},
}
Figure