Escaping Saddle Points with Compressed SGD
Year: 2022

Abstract:
Stochastic gradient descent (SGD) is a prevalent optimization technique for largescale 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 ε-first-order stationary point. In this paper we extend these results to convergence to an ε-second-order stationary point (ε-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 ε-SOSP with the same number of iterations as uncompressed SGD [25], while improving the total communication by a factor of Θ̃( √ dε−/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.

text: additional results for the cases when the compressor is arbitrary and when the stochastic gradient is Lipschitz.

heading: 1 Introduction
text: Stochastic Gradient Descent (SGD) and its variants are the main workhorses of modern machine learning. Distributed implementations of SGD on a cluster of machines with a central server and a large number of workers are frequently used in practice due to the massive size of the data. In distributed SGD each machine holds a copy of the model and the computation proceeds in rounds. In every round, each worker finds a stochastic gradient based on its batch of examples, the server averages these stochastic gradients to obtain the gradient of the entire batch, makes an SGD step, and broadcasts the updated model parameters to the workers. With a large number of workers, computation parallelizes efficiently while communication becomes the main bottleneck [12, 38], since each worker needs to send its gradients to the server and receive the updated model parameters. Common solutions for this problem include: local SGD and its variants, when each machine performs multiple local steps before communication [36]; decentralized architectures which allow pairwise communication between the workers [30] and gradient compression, when a compressed version of the gradient is communicated instead of the full gradient [6, 37, 27]. In this work, we consider the latter approach, which we refer to as compressed SGD.
Most machine learning models can be described by a d-dimensional vector of parameters x and the model quality can be estimated as a function f(x). Hence optimization of the model parameters can be cast a minimization problem minx f(x), where f : Rd → R is a continuous function, which can be optimized using continuous optimization techniques, such as SGD. Fast convergence of compressed SGD to a first-order stationary point (FOSP, ‖∇f(x)‖ < ε) was shown recently for various gradient compression schemes [6, 37, 27, 23, 2]. However, even an exact FOSP can be either a local minimum, a saddle point or a local maximum. While local minima often correspond to good solutions in machine learning applications [21, 39, 7], saddle points and local maxima are always suboptimal and
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
it is important for an optimization algorithm to avoid converging to them. In particular, [13] show that for neural networks many local minima are almost optimal, but the corresponding loss functions have a combinatorial explosion in the number of saddle points. Furthermore, [15] show that saddle points can significantly slow down SGD convergence and hence it is important to be able to escape from them efficiently.
Since finding a local minimum is NP-hard in general [5], a common relaxation of this requirement is to find an approximate second-order stationary point (SOSP), i.e. a point with a small gradient norm (‖∇f(x)‖ < ε) and the smallest (negative) eigenvalue being small in absolute value (λmin(∇2f(x)) > −εH ). When f has ρ-Lipschitz Hessian (i.e. ‖∇2f(x)−∇2f(y)‖ ≤ ρ‖x− y‖ for all x, y), a standard choice of εH is √ ρε [32], and such approximate SOSP is commonly referred as an ε-SOSP. While second-order optimization methods allow one to escape saddle points, such methods are typically substantially more expensive computationally. A line of work originating with the breakthrough of [20] shows that first-order methods can escape saddle points when perturbations are added at certain iterations. In particular, a follow-up [25] show that SGD converges to an ε-SOSP in an almost optimal number of iterations.
In this paper, we show that even compressed SGD can efficiently converge to an ε-SOSP. To the best of our knowledge, this is the first result showing convergence of compressed methods to a second-order stationary point.

heading: 1.1 Related Work
text: Escaping from saddle points While it is known that gradient descent with random initialization converges to a local minimum almost surely [28], existence of saddle points may result in exponential number of steps with non-negligible probability [17]. Classical approaches for escaping from saddle points assume access to second-order information [32, 14]. Although these algorithms find a secondorder stationary point in O(ε−3/2) iterations, each iteration requires computation of the full Hessian matrix, which can be prohibitive for high-dimensional problems in practice. Some approaches relax this requirement, and instead of full Hessian matrix they only require access to a Hessian-vector product oracle [9, 1]. While in certain settings, including training of neural networks, it’s possible to compute Hessian-vector products (HVP) efficiently [33, 35], such an oracle might not be available in general. Furthermore, in practice HVP-based approaches are significantly more complex compared to SGD (especially if the workers aren’t communicating in every iteration in the distributed setting) and require additional hyperparameter tuning. Moreover, HVP is typically used for approximate an eigenvector computation, which may increase the number of iterations by a logarithmic factor.
Limitations of second-order methods motivate a long line of recent research on escaping from saddle points using first-order algorithms, starting from [20]. [24] show that perturbed gradient descent finds ε-SOSP in Õ(ε−2) iterations. Later, this is improved by a series of accelerated algorithms [10, 1, 11, 26] which achieves Õ ( ε−7/4 ) iteration complexity. There are also a number
of algorithms designed for finite sum setting where f(x) = ∑n i=1 fi(x) [34, 4, 18], or in case when only stochastic gradients are available [40, 25], including variance reduction techniques [3, 18]. The sharpest rates in these settings have been obtained by [18], [42] and [19].
Compressed SGD While gradient compression may require a complex communication protocol, from theoretical perspective this process is often treated as a black-box function: a (possibly randomized) function C is called a µ-compressor if E [ ‖x− C(x)‖2 ] < (1− µ)‖x‖2. In a simplified form, the update step in compressed SGD can be expressed as xt+1 ← xt − ηC(∇f(x))1. Notable examples of compressors include the following: SIGN [6] sends the sign of each coordinate, QUANTIZATION [2] splits all possible values into buckets and communicates bucket indices, TOPK preserves only k largest (by the absolute value) coordinates while setting other coordinates to 0, and RANDOMK preserves k random coordinates. Among them, it’s not clear how to implement SIGN and TOPK in distributed settings; [23] suggest an efficient sketch-based approximate implementation of TOPK. Both RANDOMK and sketch-based TOPK are k/d-compressors requiring Õ(k) communication.
1The actual update equation is more complicated, see Algorithm 1.
While it is known that compressed SGD converges (e.g. [27] and the works above), the convergence was shown only to a FOSP. The crucial idea to facilitate convergence is to use error-feedback [37]: the difference between the true gradient and its compression is propagated to the next iteration.

heading: 1.2 Our Contributions
text: Our main contribution is the analysis showing that perturbed compressed SGD with error-feedback can escape from saddle points efficiently. Moreover, we show faster convergence rate for a certain type of compressors and show that such compressors exist. Inspired by the ideas from [25] and [37], we present an algorithm (Algorithm 1) which uses perturbed compressed gradients with error-feedback and converges to an ε-second-order stationary point (see Theorem 3.1). Our main results shows that compressed SGD with RANDOMK compressor achieves substantial communication improvement:2
Theorem 1.1 (Informal, Theorem 3.2 and Corollary 3.3) Assume that f has Lipschitz gradient and Lipschitz Hessian. Let α = 1 when the stochastic gradient is Lipschitz and α = d otherwise. Then SGD with RANDOMK compressor (which selects k random coordinates) with k = dε
3/4 √ α converges to an ε-SOSP after Õ ( α ε4 ) iterations, with Õ ( d √ α
ε3+1/4
) total communication per worker.
Compared with the uncompressed case, the total communication improves by ε−1/4 when the stochastic gradient is Lipschitz and by √ dε−3/4 otherwise (the sharpest results for SGD are by [19] and [25] respectively). In Theorem 1.1, we heavily rely on the following property of RANDOMK: when its randomness (i.e. sampled k coordinates) is fixed, the compressor becomes a linear function. For other compressors, this property doesn’t necessarily hold; in this case, we show convergence with a slower convergence rate:
Theorem 1.2 (Informal, Theorem 3.1 and Corollary 3.4) Assume that f has Lipschitz gradient and Lipschitz Hessian. Let α = 1 when the stochastic gradient is Lipschitz and α = d otherwise. Let C be a k/d-compressor requiring Õ(k) communication. Then SGD with compressor C with k = d √ dε
3/4 √ α converges to an ε-SOSP after Õ ( α ε4 ) iterations, with Õ ( d √ d √ α ε3+1/4 ) total communication
per worker.
Compared with the uncompressed case, the total communication improves by ε −1/4 √ d
when the stochastic gradient is Lipschitz (note that this is the only setting where the convergence improvement is conditional, requiring ε = o(d−2)) and by ε−3/4 otherwise. Table 1 in Section 3.1 shows communication improvements for various choices of compression parameters. We outline our main techniques and technical contributions in Section 3.2 and give the complete proof in Appendix A and B.

heading: 2 Preliminaries
text: Function Properties For a twice differentiable nonconvex function f : Rd → R, we consider the unconstrained minimization problem minx∈Rd f(x). We use the following standard [25, 19, 41, 3, 43] assumptions about the objective function f :
Assumption A f is fmax-bounded, L-smooth and has ρ-Lipschitz Hessian, i.e. for all x, y: |f(x)− f(y)| ≤ fmax, ‖∇f(x)−∇f(y)‖ ≤ L‖x− y‖, ‖∇2f(x)−∇2f(y)‖ ≤ ρ‖x− y‖
Assumption B Access to an unbiased stochastic gradient oracle ∇F (x, θ), whose randomness is controlled by a parameter θ ∼ D3, with bounded variance, i.e. for all x:
Eθ∼D [∇F (x, θ)] = ∇f(x), Eθ∼D [ ‖∇F (x, θ)−∇f(x)‖2 ] ≤ σ2
As shown by the above works, smoothness allows one to achieve fast convergence for nonconvex optimization problems (namely, to use the folklore descent lemma). Similarly, Lipschitz Hessian
2Õ hides polylogarithmic dependence dependence on d and ε and polynomial dependence on other parameters.
3E.g. θ is a minibatch selected at the current iteration
allows one to show fast second-order convergence, since, within a certain radius, the function stays close to its quadratic approximation (see e.g. [8, Section 9.5.3]). As common in the literature, in our convergence rates we treat L, ρ and σ2 as constants. We also consider an additional optional assumption (see [25] for a justification):
Assumption C (Lipschitz stochastic gradient, optional) For any x,y, θ:
‖∇F (x, θ)−∇F (y, θ)‖ ≤ ˜̀‖x− y‖.
Gradient Compression Our goal is to optimize f in a distributed setting [16, 29]: given W workers, for each worker i we have a corresponding data distribution Di. Then the each worker has a corresponding function fi(x) = Eθi∼Di [F (x, θi)] and f = ∑W i=1 fi. In a typical distributed SGD setting, each worker computes a stochastic gradient ∇Fi(x, θi) and sends it to the coordinator machine. The coordinator machine computes the average of these gradients v = 1W ∑W i=1∇Fi(x, θi) and broadcasts it to the workers, which update the local parameters x← x− ηv (η is the step size). With this approach, with increase of the number of machines, the computation can be perfectly parallelized. However, with each machine required to send its gradient, communication becomes the main bottleneck [12, 38]. There exist various solutions to this problem (see Section 1), including gradient compression, when each machine sends an approximation of its gradient. Then coordinator averages these approximations and broadcasts the average to all machines (possibly compressing it again, see discussion on TOPK and SIGN in Section 1.1).
Depending on the compression method, this protocol results in different gradient approximation and different communication per machine. There is a natural trade-off between approximation and communication, and it’s not clear whether having smaller per-iteration communication results in smaller total communication required for convergence. The approximation quality can be formalized using the following definition:
Definition 2.1 ([37]) Function C(x, θ̃), whose randomness is controlled by a parameter θ̃ ∼ D̃4, is a µ-compressor if Eθ̃∼D̃ [ ‖x− C(x, θ̃)‖2 ] < (1− µ)‖x‖2.
Section 1.1 provides examples of important compressors. In our analysis, we consider general and linear compressors separately, and in the latter case, we show an improved convergence rate.
Definition 2.2 C is a linear compressor if C(·, θ̃) is a linear function for any θ̃.
One example of a linear compressor is RANDOMK, which sets all but k coordinates of a vector to 0; it’s a k/d-compressor [37] and can be computed easily in the distributed setting.
Stationary Points The optimization problem of finding a global minimum or even a local minimum is NP-hard for nonconvex objectives [31, 5]. Instead, as is standard in the literature, we show convergence to an approximate FOSP or an approximate SOSP, see Section 1.
Definition 2.3 If f is differentiable then x is an ε-First-Order Stationary Point if ‖∇f(x)‖ ≤ ε.
An ε-FOSP can be a local maximum, a local minimum or a saddle point. While local minima typically correspond to good solutions, saddle points and local maxima are inherently suboptimal. Assuming non-degeneracy, saddle points and local maxima have escaping directions, corresponding to Hessian’s negative eigenvectors. Following [32] we refer to points with no escape directions (up to a second-order approximation) as approximate second-order stationary points:
Definition 2.4 ([32]) If f is a twice differentiable ρ-Hessian Lipschitz function then x is an ε-SecondOrder Stationary Point if ‖∇f(x)‖ ≤ ε and λmin(∇2f(x)) ≥ − √ ρε, where λmin is the smallest eigenvalue5.
4E.g. for RANDOMK, θ̃ is the set of indices of preserved coordinates. 5While one can consider two threshold parameters – εg for ∇f and εH for ∇2f – we follow convention
of [32] which selects εH = − √ ρε, which, intuitively, balances first-order and second-order variability.
Algorithm 1: Compressed SGD parameters: η – step size, T – number of iterations, r2 – variance of the artificial noise, I – the
number of iterations required for escaping,R – escaping radius input :objective f , compressor function C, starting point x0 output :ε-SOSP of f
1 e0 ← 0d 2 t′ ← 0 3 for t = 0 . . . T − 1 do 4 // Reset the error after I iterations or in case we moved far from the initial point 5 if (t− t′ > I or ‖xt′ − (xt − ηet)‖ > R then 6 if f(xt) < f(xt′) then xt ← xt − ηet else xt ← xt′ ; 7 t′ ← t, et ← 0d 8 end 9 Sample ξt ∼ Nd(0d, r2), θt ∼ D, θ̃t ∼ D̃
10 gt ← C(et +∇F (xt, θt) + ξt, θ̃t) // Compressed gradient 11 xt+1 ← xt − ηgt // Compressed gradient descent step 12 et+1 ← et +∇F (xt, θt) + ξt − gt // Update the error 13 end 14 return xT
An important property of points which are not ε-SOSP is that they are unstable: adding a small perturbation allows gradient descent to escape them [20] (similar results were shown for e.g. stochastic [25] and accelerated [26] gradient descent). In this work we show that this property holds even for SGD with gradient compression.

heading: 3 Algorithm and Analysis
text: Algorithm We present our algorithm in Algorithm 1, a compressed stochastic gradient descent approach based on [37, Algorithm 1]. In order to achieve convergence to a SOSP, similarly to [25], we add artificial random noise ξt to gradient at every iteration, which allows compressed gradient descent to escape saddle points. At every iteration t, we compute the stochastic gradient ∇F (xt, θt). Then we add artificial noise ξt, compress the resulting value (Line 10) and update the current iterate xt using the compressed value (Line 11). However, the information is not lost during compression: the difference between the computed value and the compressed value (Line 12), et+1, is added to the gradient in the next iteration. [27] show that carrying over the error term improves convergence of compressed SGD to a FOSP. Algorithm 1 sets et to 0 (Line 7) when conditions in Line 5 hold: either we moved far from the point where the condition was triggered last time (intuitively, the condition indicates that we successfully escaped from a saddle point), or we spent a certain number of iterations since that event (to ensure that the accumulated compression error is sufficiently bounded).
Distributed Setting Algorithm 1 provides a general framework for compressed SGD in distributed settings, with implementation details depending on the choice of the compressor function C. θt, θ̃t and ξt can be efficiently shared between machines using shared randomness. Each machine i maintains its own local e(i)t which can be computed as e (i) t+1 ← e (i) t +∇Fi(xt, θt) + ξt − g (i) t . Then
et = 1 W ∑W i=1 e (i) t . Finally, the norm in Line 7 of Algorithm 1 can be efficiently computed within multiplicative approximation using linear sketches.

heading: 3.1 Convergence to an ε-SOSP
text: In the following statements, Õ hides polynomial dependence on L, ρ, fmax, σ, ˜̀and polylogarithmic dependence on all parameters. The next two theorems present our main result, namely that compressed SGD converges to an ε-SOSP6. The first theorem addresses the general compressor case.
6see proof sketch in Section 3.2 and the full proof in Appendix B
Theorem 3.1 (Convergence to ε-SOSP for general compressor) Let f satisfy Assumptions A and B, let C be a µ-compressor. Let α = 1 when Assumption C holds and α = d otherwise. Then for Algorithm 1 with η = Õ ( min ( ε2
α , µε√ 1−µ ,
µ2 √ ε
(1−µ)d
)) , after T = Õ ( 1 ε2η ) =
Õ ( α ε4 + √ 1−µ µε3 + d(1−µ) µ2ε2 √ ε ) iterations, at least half points x0, . . . ,xT are ε-SOSP w.h.p.
In general, convergence to an ε-SOSP is noticeably slower than convergence to an ε-FOSP: in Appendix A we show that an ε-FOSP can be found in Õ ( 1 ε4 + √ 1−µ µε3 ) iterations (the result is similar to [37], but slightly more general and under weaker assumptions). The reason for such behavior is that, in the analysis of convergence to a SOSP, compression introduces error similar to that of the stochastic noise. When the stochastic gradient is not Lipschitz (i.e. Assumption C doesn’t hold), the number of iterations increases by a factor of d due to stochastic noise. Unfortunately, in general the compression is not Lipschitz even for deterministic gradients: consider a TOPK compression of a vector where each coordinate is 1 with small perturbations. However, if the compressor is linear (Definition 2.2), we show improved convergence rate: the last term in the number of iterations decreases by the factor of d.
Theorem 3.2 (Convergence to ε-SOSP for linear compressor) Let f satisfy Assumptions A and B, let C be a linear compressor. Let α = 1 when Assumption C holds and α = d otherwise. Then for Algorithm 1 with η = Õ ( min ( ε2
α , µε√ 1−µ ,
µ2 √ ε
1−µ
)) , after T = Õ ( 1 ε2η ) = Õ ( α ε4 + √ 1−µ µε3 + 1−µ µ2ε2 √ ε ) iterations, at least half of points x0, . . . ,xT are ε-SOSP w.h.p.
Since RANDOMK is a linear compressor, by balancing the terms we have:
Corollary 3.3 For RANDOMK compressor with k = dε 3/4 √ α , the total number of iterations of Algorithm 1 is Õ( αε4 ) and the total communication per worker is Õ ( d √ α
ε3+1/4
) . When Assumption C holds,
the total communication for RANDOMK decreases by the factor of Θ̃(ε−1/4) compared with the unconstrained case [19]. Otherwise, the total communication decreases by the factor of Θ̃( √ dε−3/4) compared with [25].
Compressed SGD in Distributed Settings Below we consider different scenarios to illustrate how convergence depends on the properties of the compressor. Recall that sketch-based TOPK is a k/d-compressor which requires Õ(k) communication. Selecting µ = k/d, with k d, by Theorem 3.1 we have η = Õ ( min ( ε2
α , kε d ,
k2 √ ε
d3
)) . Therefore, the total number of iterations is
Õ (
1 ε4 + d kε3 +
d3
k2ε2 √ ε
) and the total communication is Õ ( k ε4 + d ε3 + d3 kε2 √ ε ) .
Note that the above reasoning considers a worst-case scenario. However, in practice it’s often possible to achieve good compression at a low communication cost due to the fact that gradient coordinates have heavy-hitters, which are easy to recover using TOPK. We formulate this beyond worst-case scenario as the following optional assumption:
Assumption D (Optional) There exists a constant c < 1 such that for all t, C(∇F (xt, θt)+ ξt+et) provides a c-compression and requires Õ(1) bits of communication per worker.
In other words, Assumption D means that for all computed values, C provides a constant compression and requires a polylogarithmic amount of communication. This assumption can be satisfied under various conditions. For example, some methods may take advantage of the situation when gradients between adjacent iterations are close [22]. In cases when certain coordinates are much more prominent in the gradient compared to others, TOPK compressor will show good performance.
Corollary 3.4 Algorithm 1 converges to ε-SOSP in a number of settings, as shown in Table 1.

heading: 3.2 Proof Sketch
text: In this section, we outline the main techniques used to prove Theorems 3.1 and 3.2. A recent breakthrough line of work focused on convergence of first-order methods to ε-SOSP [20, 9, 24, 40, 25]
has developed a comprehensive set of analytic techniques. We start by outlining [25], which is the sharpest known SGD analysis in the case when the stochastic gradient is not Lipschitz. Let x0 be an iterate such that λmin(∇2f(x0)) < − √ ρε, and v1 be the eigenvector corresponding to λmin. Consider sequences {xt} and {x′t} starting with x0 which are referred to as coupling sequences: their distributions match the distribution of compressed SGD iterates (i.e. both sequences can be produced by Algorithm 1), and they share the same randomness, with an exception that their artificial noise has the opposite sign in the direction v1. The main idea is that such artificial noise combined with SGD updates ensures that projection of xt − x′t on v1 increases exponentially, and therefore at least one of the sequences moves far from x. After that, one can use an “Improve or localize” Lemma which states that, if we move far from the original point, then the objective decreases substantially.
If we have an access to a deterministic gradient oracle and the objective function is quadratic, then gradient descent behaves similarly to the power method, since in this case: xt+1 = (I−η∇2f(x0))xt. Adding artificial noise guarantees that there is a non-trivial projection of xt − x′t on direction v1, and the power method further amplifies this projection. In general, the SGD behavior deviates from power method due to: 1) the difference between f and its quadratic approximation and 2) stochastic noise. [25] show that the errors introduced by these deviations are dominated by the increase in direction v1, and therefore SGD successfully escapes saddle points.
Outline of our compressed SGD analysis The analysis above is not applicable to our algorithm due to gradient compression and error-feedback. Moreover, in the case of an arbitrary compressor we change the algorithm even further by periodically setting et to 0.
One of the major changes is that errors introduced by the compression lead to even greater deviation of SGD from the power method, and this deviation can potentially dominate other terms: if the compression error is accumulated from the beginning of the algorithm execution, then the compression error can be arbitrarily large. Let e′t be the compression error sequence corresponding to x ′ t such that
e′0 = e0. The deviation of SGD from the power method caused by compression can be expressed as:
η2∇2f(x0) t−1∑ i=1 (I − η∇2f(x0))t−1−i(ei − e′i). (Proposition B.12 and Lemma B.16)
It remains to bound ‖ei−e′i‖ for all i. ForGt = et+∇F (xt, θt)+ξt (withG′t defined analogously), since et+1 = Gt − C(Gt), by linearity of C we have:
E [ ‖et+1 − e′t+1‖2 ] = E [ ‖(Gt −G′t)− C(Gt −G′t, θ̃t)‖2 ] ≤ (1− µ)E [ ‖Gt −G′t‖2
] = (1− µ)E [ ‖(et − e′t) + (∇F (xt, θt)−∇F (x′t, θt)) + (ξt − ξ′t)‖2 ] .
Since e0 = e′0, after telescoping, ‖et+1 − e′t+1‖ can be bounded using ‖∇F (xi, θi)−∇F (x′i, θi)‖ and ‖ξi − ξ′i‖ for i ∈ [0 : t] (Lemma B.17). In other words, when escaping from a saddle point, the deviation can bounded based on gradients and noises encountered during escaping. Therefore it is comparable to other terms and can be bounded with an appropriate choice of η.
Unfortunately, for the arbitrary compressor case we don’t have a good estimation on Et, since in general we don’t have better bound on ‖ei − e′i‖ than ‖ei‖ + ‖e′i‖ (see proof of Lemma B.16). Lemma A.5 bounds the compression error et in terms of ‖∇f(x0)‖, . . . , ‖∇f(xt)‖:
E [ ‖et‖2 ] ≤ 2(1− µ)
µ
t−1∑ i=0 ( 1− µ 2 )t−i E [ ‖∇f(xi)‖2 + χ2 ] ,
but the bound depends on all gradients starting from the first iteration. To solve this problem, we periodically set the compression error to 0 (Line 5 of Algorithm 1). Let t′ be an iteration such that et′ is set to 0: then, when escaping from xt′ , we can apply Lemma A.5 with i starting from t′. This leads to major difference from the [25] analysis: we need to consider large- and small-gradient cases separately. When the gradient at xt′ is large (Lemma B.7), we show that nearby gradients are also large, and the objective improves by the Compressed Descent Lemma A.7. Otherwise, we can bound the error norm for the next few iterations (Lemma B.16).
Finally, the analysis uses not only the sequence of iterates {xt}, but also the corrected sequence {yt} where yt = xt − ηet (similarly, y′t = x′t − ηe′t). Intuitively, et accumulates the difference between the communicated and the original gradient, and therefore the goal of yt is to offset the compression error. Typically, xt is used as an argument of∇f(·), while yt is used in distances and as an argument of f(·), which noticeably complicates the analysis. In particular, if some property holds for xt, it doesn’t necessarily hold for yt and vice versa: for example, since xt and yt are not necessarily close, bound ‖yt − y′t‖ doesn’t in general imply bound on ‖xt − x′t‖. However, in our analysis, we show that we can bound ‖xt − x′t‖, which is required to bound ‖∇f(xt)−∇f(x′t)‖ in Lemma B.18.

heading: 4 Experiments
text: In our experiments, we show that noisy Compressed SGD achieves convergence comparable with full SGD and successfully escapes saddle points. We perform our first set of experiments on ResNet34 model trained using CIFAR-10 dataset with step size 0.1. We distribute the data across 10 machines, such that each machine contains data from a single class. We analyze convergence of compressed SGD with RANDOMK compressor when 100%, 10%, 1% and 0.1% random gradient coordinates are communicated. Figure 1 shows that SGD with RANDOMK with 10% or 1% of coordinates compression converges as fast as the full SGD, while requiring substantially smaller communication.
In our second set of experiments, we show that SGD indeed encounters saddle points and noise facilitates escaping from them. We compare uncompressed SGD, SGD with TOPK compressor (0.1% of coordinates), and SGD with RANDOMK compressor (0.1% of coordinates) on deep MNIST autoencoder7. In all settings, we compare their convergence rates with and without noise. Figure 2
7The encoder is defined using 3 convolutional layers with ReLU activation, with the following parameters: (channels=16, kernel=3, stride=2, padding=1), (channels=32, kernel=3, stride=2, padding=1) and (channels=64, kernel=7, stride=1, padding=0). The decoder is symmetrical.
† For the sake of presentation, to ensure that gradient converges to 0, we decrease the magnitude of the artificial noise at later iterations. With a fixed noise magnitude, as our theory predicts, gradient norm converges if a smaller step size is used, but this requires significantly more iterations. Note that this modification only affects the gradient convergence as the objective converges even with fixed noise and a large step size.
shows that SGD does encounter saddle points: e.g. in Figure 2a, for SGD without noise, during epochs 1-3, the gradient norm is close to 0 and the objective value doesn’t improve. However, compressed SGD escapes from the saddle points, and noise significantly improves the escaping rate.

heading: 5 Conclusion
text: We give the first result for convergence of compressed SGD to an ε-SOSP, and it’s possible that the convergence rate and the total communication can be further improved. When Assumption C holds,
it is likely that the communication can be improved by an ε−1/4 factor using techniques from [19], which achieve Õ(ε−3.5) convergence rate under Assumption C. Using variance reduction techniques, which achieve Õ(ε−3) convergence rate, we expect ε−1/2 improvement. Finally, it remains open whether linearity of the compressor is required for Theorem 3.2: similarly to the stochastic gradient case, it may suffice for the compressor to be Lipschitz.

Review summaries:
This paper is concerned with finding local minima, or second order stationary points of a function $\mathbb{R}^d \to \mathbb{R}$. The key contribution of the paper is to combine the ideas of stochastic gradient descent (SGD) and compressed gradient descent (CGD). This leads to an algorithm which takes care of both the convergence rate and communication complexity, and is favorable for distributed computing. Theoretical results of the convergence and communication complexity are rigorously established, and some empirical studies are conducted. 

It has been proven in previous works that SGD can escape saddle points existing in non-convex objective functions and find local minima. This paper considers non-convex optimization problems in the distributed setting where the gradients communicating between workers and the parameter server are compressed to reduce the communication cost. It shows that when the compression technique is either \mu-compression or Random-K compression then SGD can still escape from saddle points. Their analysis shows that under some reasonable assumptions the compressed SGD can reach \epsilon-SOSP after O(\epsilon^{-4}) iterations.