Escaping Saddle Points with Compressed SGD

Dmitrii Avdiukhin, Grigory Yaroslavtsev

Introduction

Stochastic gradient descent (SGD) is the workhorse of large-scale distributed machine learning. While computation can be efficiently parallelized across multiple machines, the communication of gradients between workers and the central server frequently becomes a bottleneck. Gradient compression—sending only a fraction of the gradient information—is a popular technique to alleviate this issue.

While previous research has proven that compressed SGD can successfully find First-Order Stationary Points (FOSPs), this guarantee is insufficient for modern non-convex deep learning. A FOSP could be a local minimum, but it could also be a saddle point or a local maximum. Saddle points are notorious for stalling training and trapping models in suboptimal states. This paper provides the first theoretical guarantee that Compressed SGD, when augmented with error-feedback and artificial noise, can successfully escape saddle points to find local minima (Second-Order Stationary Points, or SOSPs) while preserving massive communication savings.

The Challenge of Saddle Points in Compressed Training

In standard, uncompressed training, injecting noise into SGD is a known method for escaping saddle points. However, it was previously unknown if the "noise" and "errors" inherently introduced by gradient compression would overwhelm the optimizer, preventing it from navigating away from these unstable equilibria. The core problem this paper addresses is whether we can mathematically guarantee convergence to an SOSP without sacrificing the communication efficiency of compressed SGD.

Methodology: Compressed SGD with Error-Feedback and Noise

The authors introduce a modified algorithm, Compressed SGD with Error-Feedback and Noise, built on three key mechanisms:

  1. Error-Feedback: Instead of discarding the information lost during compression (the difference between the true and compressed gradient), this "error" is stored locally by each worker and added to the next iteration's gradient. This ensures no gradient information is permanently lost.
  2. Artificial Noise: At each step, a small amount of random Gaussian noise is injected into the gradient. This provides the necessary "kick" to push the optimizer away from the flat, unstable regions of a saddle point.
  3. Periodic Resets: To prevent the accumulated compression error from growing too large and destabilizing the escape trajectory, the algorithm periodically resets the error buffer based on the distance the model has moved or after a set number of iterations.

Key Insights and Theoretical Guarantees

A major theoretical insight from the paper is that linearity is a superpower in compression. The authors analyze both general $\mu$-compressors and linear compressors (specifically RANDOMK, which randomly selects $k$ coordinates to transmit). Because the RANDOMK operation is linear, the errors introduced across different iterations can be bounded much more tightly, leading to significantly faster convergence rates.

Theoretical communication and iteration complexities for various compressors.

As shown in the theoretical complexity table above, for problems where the stochastic gradient is not Lipschitz (a common scenario in deep learning), compressed SGD with the RANDOMK compressor converges to an $\epsilon$-SOSP in the same number of iterations as uncompressed SGD. Crucially, it improves the total communication by a factor of $\tilde{\Theta}(\sqrt{d}\epsilon^{-3/4})$, where $d$ is the dimension of the optimization problem.

To prove these escape guarantees, the authors employ a sophisticated "coupling" proof technique. They model two parallel versions of the algorithm starting at the same saddle point but receiving opposite noise, proving that at least one version must move far enough away to significantly decrease the objective function.

Empirical Validation

The authors validated their theoretical findings using two primary experimental setups:

  • CIFAR-10 (ResNet34): Distributed across 10 machines, using RANDOMK to send only 1% or 10% of the gradient coordinates resulted in training performance nearly identical to uncompressed SGD, while consuming a fraction of the bandwidth.
  • MNIST (Deep Autoencoder): This task was specifically chosen to observe behavior near known saddle point regions. Without artificial noise, the compressed optimizer became stuck at a saddle point for several epochs (exhibiting a near-zero gradient norm and flat loss). With the added noise, the optimizer escaped almost immediately, confirming the theoretical necessity of the noise injection.

Limitations and Future Work

While the paper establishes strong guarantees for linear compressors, the theoretical convergence rate for general, non-linear compressors (like Top-K) remains slower. The authors leave it as an open question whether this gap is a fundamental limitation of non-linear compression or merely a limitation of the current mathematical analysis.

Furthermore, the authors suggest that integrating variance reduction techniques (such as SPIDER) could further improve the algorithm's dependence on the accuracy parameter $\epsilon$. Finally, while the theory provides robust bounds, practical implementation requires careful hyperparameter tuning, particularly regarding the magnitude of the artificial noise and the frequency of the error buffer resets.

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