Escaping Saddle Points with Compressed SGD
Authors: Dmitrii Avdiukhin
Grigory Yaroslavtsev
Venue: NeurIPS 2021 Poster (2021)
Keywords: optimization
distributed optimization
nonconvex optimization
machine learning
gradient descent
saddle points

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.

Escaping Saddle Points with Compressed SGD
Dmitrïi Avdiukhin Department of Computer Science Indiana University Bloomington, IN 47405 davdyukh@iu. edu
Grigory Yaroslavtsev
Department Computer Science George Mason University
Fairfax, VA 22030 grigory@grigory..o us
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 bottleneck in the distributed setting. Gradient compression methods can used to alleviate this problem, and a recent line of work shows that SGD augmented with gradient compression converges to an e-first-order stationary point. this paper we extend these results convergence 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 RAN- DOMK compressor converges to an E-SOSP with the same number of iterations as uncompressed SGD (25), while improving the total communication by factor of @(vde-%/4 where 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.
e-second-orde stationary point (e-SOSP), which
Introduction
Stochastic Gradient Descent (SGD) and its variants are the main workhorses of modern machine learning. Distributed implementations of SGD on 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 copy of the model and the computation proceeds in rounds. In every round, each worker finds stochastic gradient based on 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 gradients
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 In this work, we consider the
the gradient is communicated instead of the full gradient 6 37 27
latter approach, which we refer 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 function fxx). Hence optimization of the model parameters can be cast minimization problem minx fxx), where f: Rd + IR is a continuous function, which can be optimized using continuous optimization techniques, such as SGD. Fast convergence of compressed SGD to first-order stationary point (FOSP, | [x)]] < E) was shown recently for various gradient compression schemes 6 37
23
However, even an exact FOSP can be either local minimum. While local minima often correspond to good solutions in saddle points and local maxima are always suboptimal and
saddle point or a local maximum. machine learning applications 21
35th Conference on Neural Information Processing Systems (NcurIPS 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 NP-hard in general [5] a common relaxation of this requirement is to find an approximate second-order stationary point (SOSP), i.c. a point with a small gradi- ent norm (x)ll < E) and the smallest (negative) eigenvalue being small in absolute value (Amin ( fx())) > -EH). When f has p p-Lipschitz Hessian (i.e. || f(x) V fy)ll S p||æz - yll for all z. y), a standard choice of и is u [32]. and such approximate SOSP is commonly referred as an E-SOSP. While second-orde 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 E-SOSP in an almost optimal number of iterations.
In this paper, we show that even compressed SGD can efficiently converge to an S-SOSP. To the best of our knowledge, this is the first result showing convergence of compressed methods to a second-order stationary point.
1.1 Related Work
Escaping from saddle points While it is known that gradient descent with random initialization converges to local minimum almost surely (28). existence of saddle points may result in exponential number of steps with non-negligible probability [7]. Classical approaches for escaping from saddle
Although these algorithms find second- order stationary point in O 9/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-vecton product oracle I. While in certain settings, including training of neural networks, it's possible to compute Hessian- 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 '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 logarithmic factor.
points assume access to second-order information [32 14,
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 E- E-SOSP in Ō(=-?) iterations. Later, this is improved by a series of accelerated 26 which achieves Ô (c-7/4 iteration complexity. There are also a number
algorithms [10 1
of algorithms designed for finite sum setting where f(xx) = - [x(x) [34 4 [8] 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 [8] 42 and [19.
While gradient compression may require complex communication protocol, from theoretical perspective this process is often treated as a black-box function: a (possibly ran- domized) function C is called a /ı-compressor if T.. [|X C(x)]I
Compressed SGD
(1 1²) |x|22 In simplified form, the update step in compressed SGD can be expressed as x + X; - (V I Notable examples of compressors include the following: SIGN (6] sends the sign of each coordinate, QUANTI- ZATION (2 splits all possible values into buckets and communicates bucket indices, ToPK preserves only & largest (by the absolute value) coordinates while setting other coordinates to O, and RANDOMK preserves l random coordinates. Among them, it's not clear how to implement SIGN and TOPK in distributed settings; (23) suggest an efficient
approximate implementation of TOPK. Both RANDOMK and sketch-based ToPK are t/a-compressors requiring Ö(k) communication.
'The actual update equation is more complicated, Algorithm

---

While it is known that compressed SGD converges (e.g. 227 and the works above), the convergence was shown only a FOSP. The crucial idea to facilitate convergence is use error-feedback [37] the difference between the true gradient and its compression is propagated to the next iteration.
1.2 Our Contributions
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 certain type of compressors and show that such compressors exist. Inspired by the ideas from [25 and [37] present an algorithm (Algorithm[] T which uses perturbed compressed gradients with error-feedback and converges e-second-order stationary point (see Theorem (.T]. Our main results shows that
compressed SGD with RANDOMK compressor achieves substantial communication improvement
Theorem 1.1 (Informal, Theorem 3.2 and Corollary 3.3) Assume that f has Lipschitz gradient and Lipschitz Hessian. Let a = 1 when the stochastic gradient is Lipschitz and a d otherwise. Then SGD with RANDOMK compressor (which selects random coordinates) with de// converges to an E-SOSP after Ö (2) iterations, with Ô
va
dva c3-1/4
total communication per worker.
Compared with the uncompressed case, the total communication improves by g when the stochas- tic gradient is Lipschitz and by vde- otherwise (the sharpest results for SGD are by [9] and [25) respectively). In Theorem T.1 we heavily rely 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 It necessarily hold; in this case, we show convergence with slower convergence rate:
Assume that f has Lipschitz gradient and Lipschitz Hessian. Let a = when the stochastic gradient is Lipschitz and a d otherwise. Let C. be k/a-compressor requiring Ōkk) communication. Then SGD with compressor C with converges to an s-SOSP after (f) iterations, with aafay/
Theorem 1.2 (Informal, Theorem 3.1 and Corollary 3.4)
k dv 2/4
total communication
per worker
Compared with the uncompressed case, the total communication improves by vd when the stochas- tic gradient Lipschitz (note that this is the only setting where the convergence improvement conditional, requiring o)) and by - otherwise. Table 1 in Section shows communica-
tion improvements for various choices of compression parameters. We outline our main techniques
and technical contributions Section 3.2 and give the complete proof in Appendix and B
2 Preliminaries
Function Properties For a twice differentiable nonconvex function f: Rd + R. we consider the unconstrained minimization problem minxeR* fxx). We use the following standard 25 assumptions about the objective function f:
Assumption A boundde. L-smooth and has p-Lipschitz Hessian, i.e. for all x, y:
[f(x) - f(y)l < fmax, -Vf(x)-Vf(y) - s L|x -ll- [[V2 f'y(y) s pl|x yll
Assumption B Access unbiased stochastic gradient oracle F 0), whose randomness is controlled by a parameter ~ D with bounded variance, i.e. for all x:
EgnD / 0]] fxx),
EA-D
[]] V 0) f(x)] <
As shown by the above works, smoothness allows one to achieve fast convergence for nonconvex optimization problems (namely, use the folklore descent lemma). Similarly, Lipschitz Hessian
2Ô hides polylogarithmic dependence dependence on and and polynomial dependence on other parame- ters.
EEgg 0 is minibatch selected the current iteration

---

allows one to show fast second-orde convergence, since, within a certain radius, the function stays close its quadratic approximation (see e.g. B Section 9.5.3J. As common in the literature, in our convergence rates we treat L, and o² as constants. We also consider an additional optional assumption (see 25 for a justification):
Assumption C (Lipschitz stochastic gradient, optional) For any x, y,
VV 0) (F 0) S x-yyl
Gradient Compression Our goal is to optimize f in a distributed setting 16 29
given W
workers, for each worker have corresponding data distribution D,- Then the each worker has corresponding function (x) Eg,-D, [x 0:)] and f =>==, ft. In a typical distributed SGD setting, each worker computes stochastic gradient (x,(x, 0z) and sends it to the coordinator machine. The coordinator machine computes the average of these gradients and broadcasts it to the workers, which update the local parameters + Φ Σ V 0,)
(1) is the step size).
With this approach, with increase of the number of machines, the computation 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 [ including gradient compression, when each machine sends an approximation of its gradient. Then coordinator averages these approximations and broadcasts the average all machines (possibly compressing it again, see discussion on ToPK and SIGN in Section 1.1
be perfectly
Depending 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, 8), whose randommess controlled by a parameter θ p-compressor if EgDD ||X C(x, 0)][?] (1 |
-
provides examples of important compressors. In our analysis, consider general and linear compressors separately, and the latter case, we show an improved convergence rate.
Section [.]
Definition 2.2 C is a linear compressor if (C
(.,00 0) is a function for any 0.
One example linear compressor RANDOMK, which sets all but & coordinates of a vector to 0; it's a 5/d-compressor (37] and can be computed casily in the distributed setting.
Stationary Points
The optimization problem of finding global minimum even a local minimum NP-hard for nonconvex objectives [31 5 Instead, as standard in the literature, we show
convergence to an approximate FOSP or an approximate SOSP, see Section [
Definition 2.3 If is differentiable then is e-First-Order Stationary Point if [ S.
An E-FOSP can be 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 's negative eigenvectors. Following 332 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 p-Hessian Lipschitz function then x is an E-Second- Order Stationary Point if V fxx)] S and Xuiin 2 f(x)) 2 VpE, where Xmia is the smallest eigenvalud
'E.g. for RANDOMK, Ø the set of indices of preserved coordinates. 'While one can consider two threshold parameters Ey for V and ин for V we follow convention which selects eи -yp,, which, intuitively, balances first-order and second-order variability.
of 32

---

Algorithm 1: Compressed SGD
parameters: 1) step size, T number of iterations, r² variance of the artificial noise, the number of iterations required for escaping, R escaping radius input :objective f. compressor function C, starting point Xo output:e-SOSP of
--0 0d en
3 for /
= 0 T do // Reset the eπrоr after iterations or in case we moved far from the initial point
if (t t' > I or |x (x: r7e))] > R then
if fxx) < f(xe) then X, Xt 1/e else X2 t- X
d' 1 e, + 0
end
Sample & ~ Na(0 ; ,r²), 01 ~ DD
Be 2~
10
gi C(e + VF(x,, 01) + tc,00)
I/ Compressed gradient // Compressed gradient descent step // Update the error
11
X++1 f X₁ - 1/E:
e++1 f e, + V F 0,) + &t gr
13 end
14 return XT
An important property of points which are not s-SOSP is that they are unstable: adding small pertur- bation 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.
Algorithm and Analysis
Algorithm We present our algorithm in Algorithm [ a compressed stochastic gradient descent approach based on 337 Algorithm IJ. In order to achieve convergence SOSP, similarly to (25), we add artificial random noise & to gradient at every iteration, which allows compressed gradient descent to escape saddle points. At every iteration L, we compute the stochastic gradient V VF(x,, 0)). Then we add artificial noise ε,, compress the resulting value (Line 10] and update the current iterate x; using the compressed value [Line[[]) However, the information not lost during compression: the difference between the computed value and the compressed value (Line 12) ec+1, is added to the gradient in the next iteration.
the error term improves convergence of compressed SGD to a FOSP. Algorithm sets e, to 0 (Line 7 when conditions in Line hoold: either triggered last time (intuitively, the condition
(27) show that carrying
moved far from the point where 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 sufficiently bounded).
Distributed Setting A provides general framework for compressed SGD in distributed settings, with implementation details depending on the choice of the compressor function C. Oz. 0, and & can be efficiently shared between machines using shared randomness. Each machine i maintains its own local c,") which can be computed as C,41
(i) (t) F 0,) + + g. Then
D (i) Finally, the norm in Line 7 of Algorithm can be efficiently computed within multiplicative approximation using linear sketches.
3.1 Convergence to an E-SOSP
In the following statements, Ô hides polynomial dependence on L, P, fmax, o, ? and polylogarithmic dependence on all parameters. The next two theorems present our main result, namely that compressed SGD converges an E-SOS The first theorem addresses the general compressor case.
see proof sketch in Section 3.2 and the full proof in Appendix B
5

---

Theorem 3.1 (Convergence to E-SOSP for general compressor)
Let f satisfy Assumptions A
and B let C be p-compressor. Let a when Assumption
C
holds and a other- after T (
wise. Then for Algorithm I with n Ō min
1 yLVE
VI-F" (1-M)d
- D
d(1 p VE)
iterations, least half points ; XT E-SOSP w.h.p.
In general. convergence to an E-SOSP is noticeably slower than convergence to an E-FOSP: in Appendix A show that an e-FOSP be found in Ô --= 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 doesn't hold), the number of iterations increases by factor of due to stochastic noise. Unfortunately, in general the compression is not Lipschitz even for deterministic gradients: consider a ToPK compression with small perturbations. However, if the compressor linear (Definition 2.2) show improved convergence rate: the last term in the number of iterations decreases by the factor of d.
C
of a vector where each coordinate
Theorem 3.2 (Convergence to E-SOSP for linear compressor) Let f satisfy Assumptions A A B let C be a linear compressor. Let a = when Assumption Craimpptionhhhlla and a = otherwise. Then for Algo-
rithm with 1j Ô min @ VI- 1- ) after T Ô 2 Ô --- + iterations, at least half of points No. ;
H² V/
1-
Med
Xr are E-SOSP w.h.p.
Since RANDOMK linear compressor, by balancing the terms we have:
Corollary 3.3 For RANDOMK compressor with k ds vaa the total number of iterations of Algo-
rithm I is (g$) and the total communication per worker is Ô dyaa c31
When Assumption C holds,
the total communication for RANDOMK decreases by the factor of ((E-V/)) compared with the unconstrained case 179]. Otherwise, the total communication decreases by the factor of ( d// compared with (25).
Compressed SGD in Distributed Settings Below consider different scenarios illustrate how convergence depends on the properties of the compressor. Recall that sketch- ToPK 4/d-compressor which requires Ō(k) communication. Selecting μ = t/d, with < d, by Theorem 3.1 we have 1j Ô min (= ( kc K² kx=)) Therefore, the total number of iterations is d
ò ( +
43 and the total communication is Ō ( A-g-VE)
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 constant e < such that for all CCFFFCFF 0.) + ex) provides c-compression and requires Õ(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 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 much more prominent in the gradient compared to others, ToPK compressor will show good performance.
Corollary 3.4 Algorithm converges e-SOSP number of settings, as shown in Table 7
3.2
Proof Sketch
In this section, we outline the main techniques used to prove Theorems and 3.2 A recent
breakthrough line of work focused on convergence of first-order methods to e- SOSP 20 24 40 25

---

Table 1: Convergence to E-SPPP with uncompressed SGD, with sketch- ToPK compressor, with RANDOMK compressor, and with a constant-compressor requiring constant communication (Assumption DJ beyond worst-case assumption). We considered two settings depending the stochastic gradient is Lipschitz (i.e. Assumption [C] holds). For each setting we select the optimal l based on our bounds. The results show that communication of SGD with RANDOM K compression outperforms that of the uncompressed SGD by (s- when Assumption C holds and by O(vid= %/ otherwise. Based on our results, since a constant-memory constant-communice compressor is not necessarily linear, depending on d and E, it may converge slower than RANDOMK.
whether
Total comm.
Total comm. improvement
Setting
/
Iterations
per worker
Uncompressed
1
Ô Ó
Ô 2
[9
Lipschitz V
Sketch-based
Vde
Ô (+))
dva $/
5 (-
TOPK
(e = oo=o(d=2) o))
Vd
RANDOMK
8/
Ô (())
1/o
331
Constant-memory
<> 0
Ô ( + 2/3
Ö d
d
i min(d, Jt)
c-compressor
doVE)
non- Mon-Lipschitz VF
Uncompressed
1
Ô (#)
d2
[25]
Sketch-based
8/4
Ô (44)
d2
θ (1-
TOPK
RANDOMK
7/
Ô (#)
dvdd
θ dd -//a
vd
234-74
Constant-memory
>> 0
Ô (44)
Ô
(
Ô (d)
c-compressor
has developed comprehensive set of analytic techniques. We start by outlining 25). which the sharpest known SGD analysis in the case when the stochastic gradient is not Lipschitz.
Let Xo be iterate such that Amiu (V² (xx)) <-VPE, and v1 be the eigenvector corresponding to Amin- Consider sequences {x,} and {x,} starting with Xn 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 []. 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 x, x on 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: X,+1 Adding artificial noise guarantees that there is a non-trivial projection of x; x 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.
(=xo))()))))) )x,,
Outline of our compressed SGD analysis The analysis above is not applicable to our algorithm due to gradient compression and error-feedbart Moreover, in the case of an arbitrary compressor we change the algorithm even further by periodically setting e to O.
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 be the compression error sequence corresponding to x such that
7

---

c = c.. The deviation of SGD from the power method caused by compression can be expressed as:
Σ ( f(xo)
-e)). (-x
(Proposition B.12 and Lemma B.16
i=1
It remains to bound ||e; e/ll for all i. For G. e, + (x 06) + (with G2, defined analogously).
since 0t+1 = G. - C(G)). by linearity we have:
E [[ler+1 8/411 = E. [I[CG - G.) C(G, Gy 0.)1
- (1 - | ||G Gi
= (1 - |B [1] - ei) + (VF(x;, 01) VF(X,, 0,)) + (Sc E)
Since co = c/. after telescoping, ||| c || can be bounded using [V, 0.) - FF 0
and I[C, - <ill for i [0 (Lemma B.17 In other words, when escaping from 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 r).
Unfortunately, for the arbitrary compressor case we don't have good estimation on & since in general we don't have better bound ||e, e'll than ||e,]| + ||e|[l| (see proof of Lemma (.1ma.B.16) Lemma A.5 bounds the compression error e; in terms of | (xo) ..... [x(x))]l:
E [[|ov113]
< 2(1
7 E [[V ++xx) + 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 5f Algorithm D Let t' be an iteration such that By is set to O: then, when escaping from Xy, we can apply Lemma A.5 with i starting from t'. This leads to major difference from the [25] analysis: we need consider large- and smadl-gradient cases separately. When the gradient at X 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 }x,). but also the corrected sequence {y:) where y, = X, 1je, (similarly, y = x; r7e(). Intuitively, e, accumulates the difference between the communicated and the original gradient, and therefore the goal of y: error. Typically, X; is used as an argument of V f-), while is used in distances and as an argument of f(). which noticeably complicates the analysis. In particular, if some property holds for X doesn't tt necessarily hold for y, and vice versa: for example, since and yr are not necessarily close, bound lly; - y'll doesn" 't in general imply bound on |x; x 1. However, in our analysis, we show that we can bound ||x x/Il. which is required to bound || f V fx())l in Lemma B.18
offset the compression
4 Experiments
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 single class. We analyze convergence of compressed SGD with RANDOMK compressor when 100%. 10%, 1% and 0.1% random gradient coordinates communicated. Figure I shows that SGD with RANDOMK with 10% 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) deep MNIST autoencoder In all settings, we compare their convergence rates with and without noise. Figure
"The encoder is defined using 3 convolutional layers with ReLU activation, with the following parameters: (channels=16, kernel=3, stride=2, padding=1). (channels=32, kemel=3, stride=2, padding=1) 1) and (channels=64, kernel=7, stride=1, padding=0). The decoder is symmetrical.
8

---

10%
Test Error, % (log sc.)
Train Loss (log (log-sc.)
Communication (log
3.0
Epoch
Epoch
Epoch (log-sc.)
(a) Test Error
(b) Train Loss
(c) # of communicated parameters
Figure 1: Convergence distributed SGD (1) 0.1, batch size is 8 per machine) with RANDOM compressor when 100% (full gradient), 10%, 1% and 0.1% of coordinates are used. ResNet34 model trained on CIFAR- 10 distributed across 10 machines: each machine corresponds to a single class. SGD with 10% and 1% compression achieves performance similar to that of uncompressed SGD, while requiring significantly less communication
Without
Test Loss (log-sc.)
(log-sc.)
Loss (log-se S6.
1
0.7
Epoch
Epoch
Epoch
(a) Uncompressed loss
(b) TopK loss
(c) Random compressor loss
Avg Grad norm
3.8
Avg Grad norm
3.2
3.20
3:15
3.10
2:10
3.6
2.06
3.00
10
10
20
60
60
107
Epach
Epach
Epoch
(d) Uncompressed gradient
(e) TopK gradient
(f) RANDOMM gradient
Figure 2: Convergence of SGD (17 = 0.1, batch size is 64) without compression (left), with ToPK (0.1% of coordinates) compression (middle), and with RANDOMK (0.1% of coordinates) compression (right) on MNIST autoencoder dataset without noise (red) and with Gaussian noise (green, = 0.01 for each coordinate). Data points correspond to average over executions and error bars correspond to 10%- and 90%-quantiles. The bottom row shows the norms of the stochastic gradients averaged over the last 100 iterations. The figure shows that SGD encounters and escapes saddle points for all compressors, and adding noise facilitates escaping from the saddle points!.
For the sake of presentation, to ensure that gradient converges to 0, we decrease the magnitude of the artificial noise later fterations. With a fixed noise magnitude, our theory predicts, gradient norm converges 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 fixed noise and 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 and the objective value doesn't improve. However, compressed SGD escapes from the saddle points, and noise significantly improves the escaping rate.
Conclusion
We give the first result for convergence of compressed SGD to an e-SOSP, it's possible that the convergence rate and the total communication can be further improved. When Assumption Cholds

---

it is likely that the communication can be improved by an which achieve Ō( convergence rate under Assumption
factor using techniques from [9].
Using variance reduction techniques, which achieve ()==)) convergence rate, we expect 5 e/\/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.
References
[1] Naman Agarwal, Zeyuan Allen- Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. Proceedings of the 49th Annual ACM SIGACT Symposiun on Theory of Computing, pages 1195-1199 1199. ACM, 2017.
[2] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. In Advances in Neural Information Processing 2017.
Systems, pages
[3] Zeyuan Allen Zhu. Natasha 2: Faster non-convex optimization than sgd. In Advances in neural information processing systems, pages 2675-2686 2018
[4] Zeyuan Allen-Zhu Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. In Advances in Neural Information Processing Systems, pages 3716-3726 2018
[5] Animashree Anandkumar and Rong Ge. Efficient approaches for escaping higher order saddle points in non-convex optimization. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 81-102, Columbia University, New York, New York, USA, 26 Jun 2016. PMLR.
[6] Jeremy Bersstein. Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd: Com- pressed optimisation for non-convex problems. arXiv preprint arXiv: 802004434, 2018.
[7] Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery. In D. D. Lee, Sugiyama, U. Luxburg, Guyon, and R. Gamett, editors, Advances in Neural Information Processing Systems 29, pages 1873-3881 Curran Associates, Inc., 2016.
[8] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[9] Yair Carmon and John C. Duchi. Gradient descent efficiently finds cubic-regularized non-convex newton step. ArXiv, htss/112.005547 2016.
[10] Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for non-convex optimization. arXiv preprint wrXiv:1611.007555 2016.
[11] Yair Carmon, Oliver Hinder, John Duchi, Aaron Sidford. Convex until proven guilty: Dimension-free acceleration of gradient descent on non-convex functions. arXiv preprini urXiv:1705.02766 2017.
[12] Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam: Building an efficient and scalable deep learning training system. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pages 571-582, 2014.
[13] Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial intelligence and statistics, pages 192-204. PMLR, 2015.
[14] Frank F. Curtis, Daniel P Robinson, and Mohammadreza Samadi. A trust region algorithm with a worst-case iteration complexity (occ-3/2) for nonconvex optimization. Mathematical Programming, pages 1-32, 2014.
[15] Yann Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identitying and attacking the saddle point problem nigh-dimensional non-convex optimization. Advances in Neural Information Processing Systems, 27:2933 2941, 2014.
[16] Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mani-batches. Journal of Machine Learning Research, 13(1), 2012.
[17] Simon S Du. Chi Jin, Jason D Lee, Michael I Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. In Advances in neural information processing systems. pages 1067-1077, 2017.
10

---

[18] Cong Fang. Chris Junchi Li. Zhouchen Lin, and Tong Zhang, Spider: Near-optimal non-convex optimiza- tion via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pages 687-697, 2018.
[19] Cong Fang. Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. arXiv preprint arXiv:1902. 00247, 2019.
[20] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Conference on Learning Theory, pages 797-842, 2015.
[21] Rong Ge, Jason D. Lee, and Tengyu Ma. Matrix completion has spurious local minimum. In Proceedings the 30th International Conference on Neural Information Processing Systems, NIPS' 16, page 2981-2989. Red Hook, NY, USA, 2016. Curran Associates Inc.
[22] Filip Hanzely, Konstantin Mishchenko, and Peter Richtárik. Sega: Variance reduction via gradient sketching. In Advances in Neural Information Processing Systems, pages 3082-2093, 2018.
[23] Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Ion Stoica, Raman Arora, et al. Communication--efiiee distributed sgd with sketching. In Advances in Neural Information Processing Syxtems, pages 13144-13154, 2019.
[24] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, pages 1724-1732. JMLR.org, 2017.
[25] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68(2):1-29, 2021.
[26] Chi Jin, Praneeth Netrapalli, and Michael Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. Conference On Learning Theory, pages 1042-1085. PMLR, 2018
[27] Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. arXiv preprint
9994099477 2019.
[28] Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference on learning theory, pages 1246-1257, 2016.
[29] Mu Li, David G Andersen, Alexander Smola, and Kai Yu. Communication efficient distributed machinc learning with the parameter server. NIPS, volume 2. pages 1-4, 2014.
[30] Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efiee learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[31] Yurii Nesterov. Squared functional systems and optimization problems. High performance optimization, pages 405-440. Springer, 2000.
[32] Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Progranming, 108( 177-2227772205 2006.
[33] Barak A. Pearlmutter. Fast exact multiplication by the hessian. Neural Comput., 6(1):147-160, January 1994.
[34] Sashank J Reddi, Manzil Zaheer, Suvrit Sra, Barnabas Poczos, Francis Bach, Ruslan Salakhutdinov, and Alexander Smola. A generic approach for escaping saddle points. arXiv preprint arXiv:/709.01434 2017.
[35] Nicol N Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural computation, 14(7))1723-1738, 2002.
[36] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint 2018.
[37] Schastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Advances in Neural Information Processing Systems, pages
2018.
[38] Nikko Strom. Scalable distributed dnn training using commodity gpu cloud computing. In Sixteenth Annual Conference the International Speech Communication Association, 2015.
11

---

[39] J. Sun, Q. Qu, and J. Wright. A geometric analysis of phase retrieval. In 2016 IEEE International Symposium Information Theory (ISIT), pages 2379-2383, 2016.
[40] Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cubic regularization for fast nonconvex optimization. In Advances in Neural Information Processing Systems, pages 2904-2913, 2018
[41] Yi Xu, Rong Jin, and Tianbao Yang. First-order stochastic algorithms for escaping from saddle points in almost linear time. Advances Neural Information Processing Systems, pages 5530 5540, 2018.
[42] Dongruo Zhou and Quanquan Gu. Stochastic recursive variance-reduced cubic regularization methods. arXiv preprint 111. 2019.
[43] Dongruo Zhou, Pan Xu, and Quanquan Gu. Finding local minima via stochastic nested variance reduction. arXiv preprint 1r0iv:1806..mm 08782, 2018
12


Reviews:
[{"review_id": "xhnvuntF1pO", "reviewer": "Reviewer_VP57", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea of combining SGD and CGD might not be too novel, since there are works using these two ingredients to find the first order stationary points. However, this paper is the first instance to study rigorously finding the second order stationary points, a.k.a. escaping the saddle points, using the compressed SGD. This is important for learning problems, since the main obstacle is saddle points not the local extrema. The paper is well-written, and the results seem to be scientifically correct. However, there are still a few unclear points to me (see below), and I am not sure what is exactly the technical contribution of this paper (i.e. compare to previous works of compressed SGD applied to the first order optimization). I would consider to raise my score if the following points are addressed. \n\nUnclear points and suggestions:\n1. l.72 and elsewhere: there is the notation $\\tilde{\\mathcal{O}}$ which is not explained. I understand that in other previous papers this notation is also used to hide log term, but it might be better to explain for ease of reading. \n\n2. l.79-83: It is unclear to me what it means \"RANDOMK preserves k random coordinates\", does it mean $\\mathcal{C}(x)$ is $k$-dimensional? This way, how to make sense of $x - \\mathcal{C}(x)$? ($x$ is $d$-dimension, while $\\mathcal{C}(x)$ is $k$-dimension). The authors should explain this in a clear way.\n\n3. Theorem 1.1: the rate of convergence is $\\tilde{\\mathcal{O}}(\\varepsilon^{-4})$ which is slower than $\\tilde{\\mathcal{O}}(\\varepsilon^{-2})$ established in [24, 25]. The authors may comment on this fact. Any explanation?\n\n4. l.130-133: do you mean $\\theta_i \\sim \\mathcal{D}_i$ in the definition of $f_i(x)$? Otherwise, the authors should make clear the definitions of $f_i, F_i, \\theta_i$ and connections.\n\n5. l.188: I guess the authors mean Line 6 of Algorithm 1 instead of Line 1 of Algorithm 6.\n\n6. Theorem 3.1: I am a bit confused with the notations. It seems to me that $\\mathcal{R}$ is a positive number as the distance in Euclidian space. But in the theorem, $t \\in \\mathcal{R}$ is used as an index set for the time $t$. \n\n7. Theorem 3.1 and 3.2: in both theorems, there is a claim that at least half of visited points are $\\varepsilon$-SOSP. I wonder if this set is finite or infinite. My understanding is that this set would be infinite, so the authors may be a bit careful about what \"at least half\" mean (there is possibly a limiting frequency involved).\n\n8. l.239: (JACM) should be removed.\n\n9. What is the technical contribution of this paper in comparison with the previous ones on the first order optimization?\n\n10. There is also some work on the perturbed gradient descent, with non-uniform perturbation, see e.g. Perturbed gradient descent with occupation time (https://arxiv.org/abs/2005.04507v1). Theoretically the proposed algorithm achieves at least the same convergence rate as in [24, 25]. They also showed in practice, the carefully chosen perturbation is efficient in escaping saddle points even with some bad initializations.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "rVEVyjuMUFH", "reviewer": "Reviewer_XCGn", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work is an incremental work that is based on the analysis of compressed SGD and saddle point avoidance properties of SGD that have been shown in previous works. However, since in practice training big models using distributed settings is essential, this work provides some guarantee about finding second-order stationary points while SGD is used. \n\nIt is easy to follow the main text and also the proofs. They considered various scenarios and analyzed them carefully to improve the quality of their work. \n\n\n\nMy questions \n\n- I was wondering how hard it is to generalize this analysis for applying a general random function to a stochastic gradient. For example, should this function be an unbiased estimator?   \n\n- In Fig 2 it is not clear why you claim that SGD encountered and then escaped from a saddle point. Since the x-axis is based on the epoch, SGD has the ability to escape from a saddle point even after a few iterations. Also for the graph in the 2nd row, it would be more informative to depict the gradient norm at the current iteration, not the averaged one. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "oWouc6obP5", "reviewer": "Reviewer_goPg", "summary": "This paper presents the compressed stochastic gradient descent with random perturbations and the convergence analysis.  The results show that the proposed algorithm enjoys the same rate as the GD with random perturbations but can reduce communications.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:  \n1. The authors extended the gradient descent with random perturbations to the compressed version and applied it to the distributed setting. As far as I know, this is novel.\n\n2.The algorithm scheme uses error feedback and random noise perturbation, which is more complicated than the previous scheme. The paper combines previous techniques and develops several novel ones. \n\n3. The writing of this paper is very clear. The \"sketch of the proof\" helps a lot to get the difficulty in the analysis.\n\n4. A very interesting is that the authors also present numerical results to demonstrate the efficiency after adding noise.  This is few in previous papers about random perturbations to escape saddle points.\n\nWeakness: 1. Although the proof of the proposed algorithm is not obvious,   previous works (including [Chi Jin,Sai Praneeth Karimireddy]) have provided many methods. This paper should be more specific on the point, i.e., the novelty of the technique in the proof.  From my view, it seems not very difficult to get proof.  Thus, I hope the authors could answer this comment.\n\n2.  In RANDOMK compressor, the total communication is dependent on the sparsity level. If $k=\\epsilon^{\\tau}$, the total communication is then$O(1/\\epsilon^{4-\\tau})$. Is this true？If it is true, why just set $\\tau=3/4$?\n\nI will raise the score if my concerns are addressed.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 "}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper generated a fair bit of discussion, and the reviewers agree that the paper has interesting approach and combination of arguments of escaping saddle point with compressed gradient is very elegant. 
Decision: Accept (Poster)