Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning
Authors: Tomoya Murata
Taiji Suzuki
Venue: NeurIPS 2022 Accept (2022)
Keywords: nonconvex optimization
distributed learning
local SGD
escaping saddle points
communication efficiency

Abstract: In recent centralized nonconvex distributed learning and federated learning, local methods are one of the promising approaches to reduce communication time. However, existing work has mainly focused on studying first-order optimality guarantees. 
On the other side, second-order optimality guaranteed algorithms, i.e., algorithms escaping saddle points, have been extensively studied in the non-distributed optimization literature. 
In this paper, we study a new local algorithm called Bias-Variance Reduced Local Perturbed SGD (BVR-L-PSGD), that combines the existing bias-variance reduced gradient estimator with parameter perturbation to find second-order optimal points in centralized nonconvex distributed optimization. 
BVR-L-PSGD enjoys second-order optimality with nearly the same communication complexity as the best known one of BVR-L-SGD to find first-order optimality. Particularly, the communication complexity is better than non-local methods when the local datasets heterogeneity is smaller than the smoothness of the local loss. In an extreme case, the communication complexity approaches to $\widetilde \Theta(1)$ when the local datasets heterogeneity goes to zero. Numerical results validate our theoretical findings. 

Escaping Saddle Points with Bias- Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning
Tomoya Murata
NTT DATA Mathematical Systems Inc., Tokyo, Japan Graduate School of Information Science and Technology, The University of Tokyo
Taiji Suzuki
Graduate School of Information Science and Technology, The University Tokyo Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan
Abstract
In recent centralized nonconvex distributed learning and federated learning, lo- cal methods are one the promising approaches to reduce communication time. However, existing work has mainly focused on studying first-order optimality guarantces. On the other side, second-order optimality guaranteed algorithms, ie.. algorithms escaping saddle points, have been extensively studied in the non- distributed optimization literature. In this paper, we study a new local algorithm called Bias-Variance Reduced Local Perturbed SGD (B (BVR-L-PSGD), that com- bines the existing bias-variance reduced gradient estimator with parameter pertur- bation find second-order optimal points in centralized nonconvex distributed optimization. BVR-L-PSGD enjoys second-orde optimality with nearly the same communication complexity the best known one of B BVR-L-SGD find first-order optimality. Particularly, the communication complexity is better than non-local methods when the local datasets heterogeneity smaller than the smoothness of the local loss. In an extreme case, the communication complexity approaches to @(1) when the local datasets heterogeneity goes to zero. Numerical results validate our theoretical findings.
1 Introduction
Distributed learning is an attractive approach to reduce the total execution time by utilizing the parallel computations. However, the communication time in distributed learning can be a main bottleneck in the entire process due to huge parameter size typical in deep learning or low bandwidth communication environments.
To reduce communication time, one of the promising approaches is the usage of local methods such local SGD (also called as Parallel Restart SGD FedAvg). In local SGD, each worker independently executes multiple updates of the local model based on his own local dataset, and the server periodically communicates and aggregates the local models. Many paper have studied local 28 27). Particularly, for convex objectives, it has been shown in [27), for the first time, the communication complexity (that is the necessary number of communication rounds to achieve given desired optimization error) of local SGD can be smaller than the one of minibatch
SGD [25] 30 7 6 15
"murata @ msi.co.jp 36th Conference on Neural Information Processing Systems (NcurIPS 2022).
f 'taji @ iist.i.utook tokkyo...ko

---

SGD when the heterogeneity of the local datasets is extremely small. In traditional distributed learning, the local datasets are typically random subsets of the global dataset and in this case the heterogeneity of the local datasets may become quite small. However, in the recent federated learning regimes [6 24 18,, it is often the case that the heterogeneity of the local datasets is not too small. Also, the analysis in [27 has only focused on convex cases. Hence, the superiority of local SGD to minibatch SGD is still quite limited.
Recently, more communication efficient local methods than local SGD have been proposed for possibly nonconvex objectives to guarantee first-order optimality [2 22
SCAFFOLD [[2] is new local algorithm based on the idea of reducing their called flient-drfft by using similar formulation to the variance reduction technique [10]. They have shown that the communication complexity of SCAFFOLD can be smaller than the one of minibatch SGD for not too heterogenous local datasets under the quadraticity of the (possibly nonconvex) local objectives, which is quite limited. For general nonconvex objectives, the communication complexity of SCAFFOLD is same as minibatch SGD. More recently, Murate and Suzuki [19] have proposed Bias- Variance Reduced Local SGD (BVR-L-SGD) BVR-L-SGD utilizes their proposed bias- bias-variance reduced estimator that simultaneously reduces the bias caused by local gradient steps and the variance caused by stochastization of the gradients in local optimization based on the formulation of SARAH like variance reduction [20). They have shown that the communication complexity of BVR-L-SGD is smaller than minibatch SGD for not too heterogeneous local datasets for general nonconvex objectives. Specifically, BVR-L-SGD is superior to minibatch SGD when the Hessian heterogeneity of the local datasets is small relative to the smoothness of the local loss in order sense.
On the other side, there are vast work that has studied second-order optimality guarantees, which is much more challenging to ensure but desirable than first-order one, in non non-distributed nonconvex optimization. Several approaches are known and one of the simplest approaches is parameter perturbation 4 g g. However, almost all existing analysis of local methods have only focused on achieving first-order optimality. As an exception, Vlaski et al. 226 have analysed second-order guarantees of local SGD with parameter perturbation, but the obtained communication complexity is much worse than the one of minibatch SGD and no benefit of localization has been shown.
Open question. For local methods, it is not well-studied how to find second-orde optimal points with low communication cost and thus we have the following research questions:
Is there a first-order distributed optimization algorithu with second-order optimality guarantees which satisfies that (i) the communication complexity is smaller than non-local methods for not too heterogeneous local datasets; and (ii) the communication complexity approaches to ((1) when the heterogeneity of local datasets goes to zero?
Note that the both properties are desirable in distributed optimization. We expect that local methods are superior to non-local methods for not highly heterogeneous local datasets. Furthermore, when the local datasets are nearly identical, it is expected that a few communications are sufficient to optimize the global objective. Only in the case of first-order optimality, Murata and Suzuki [19] have shown that their proposed BVR-L-SGD satisfies (i) and (ii), and the question has been positively answered. However, the question is still open in the case of second-order optimality?
Main Contributions
We propose new local algorithm called Vtas-Variance Reduced Local Perturbed SGD (BVR-L- PSGD) for nonconvex distributed learning to efficiently find second-order optimal points, which positively answered the above research questions.
The algorithm is based on a simple combination of the existing bias and variance reduced gradient estimator and parameter perturbation. In our algorithm, parameter perturbation is carried out at every
'Since there are communication efficient distributed optimization algorithms that find first-order stationary points like BVR-L-SGD, we can apply generic algorithms which guarantee second-ordes optimality to them
29 [. However, this naive approach does not possess the aforementioned property (ii) because the generic
framework requires at least 2(1/e communication rounds guarantee second-order optimality due to the multiple negative curvature exploitation steps in their framework for any communication efficient algorithms with order optimality guarantees. Also, this approach requires explicit negative curvature exploitation, that is complicated and makes the whole algorithm less practical.

---

Algorithm
Communication Rounds
Assumptions
Guarantee
Minibatch SGD
2-3, BSGV
Ist-order
BPs
Noisy Minibatch SGD
9
+
BP
2-4
2nd-order
Minibatch SARAH 21
+
8P
vn
+
BP
2-3
1st-order
SSRGD 17
2
2-5, B 2 Y
2nd-order
Local SGD 30
2-3, 5
Ist-order
B
BP
SCAFFOLD
2-3, BSGV
Ist-order
BP
1-3, BSGV, quadraticity
SCAFFOLD 12
Ist-order
Bga
BP&T
BVR-L-SGD 19
vB2a
+
BPg²
V
ga
1-4
1st-order
BVR-L-PSGD (this paper)
vBaa
+
BPg²
vn
ga
1-5
2nd-order
Table 1: Comparison of the order of the necessary number of communication rounds achieve desired optimization error E in terms of given optimization criteria (described in the column of "Guarantee") in nonconvex optimization. "Assumptions" indicates the necessary assumptions derive the results (the numbers correspond to Assumptions 2
3 5 in Section 2 respectively). BSGV means the bounded stochastic gradient variance assumption that is Eg-D, D. V4(z, 2) (z))) < a². B is the local computation budget, which is defined in Section 2
P is the number of workers. n is the total number of samples. The gradient Lipschitzness L, Hessian Lipschitzness p. the gradient boundedness G are regarded as (1)) for ease of presentation. In this notation, Hessian heterogeneiry
Ç always satisfies S (()) = O()).
local update and it is not necessary to determine whether or not to add noise by checking the norm of the global gradients, which is often required in several previous non-distributed algorithms [7.
We analyse BVR-L-PSGD for general nonconvex smooth objectives. The most challenging part of our analysis is to ensure that our algorithm efficiently escapes global saddle points even in local optimization. To realize this, it necessary to analyse the behavior of the bias-variane reduced estimator around the saddle points by carefully evaluating the degree of some kind of asymptotic consistency of the estimator around the saddle points. This point has never been pursued in previous work and has a unique difficulty of our analysis.
The comparison of the communication complexities of our method with the most relevant existing results is given in Table [ Our proposed method enjoys second-order optimality with nearly the same communication complexity as the one of BVR-L-SGD, which achieves the best known communication complexity to achieve first-order optimality. This means that our method finds second-order optimal points without hurting the communication efficiency of the -tate-of-the-art first-order optimality guaranteed method. Particularly, the communication complexity is better than minibatch SGD when Hessian heterogeneity Ç is small relative smoothness approaches to (() when heterogeneity ( goes to zero and the local computation budget B (see Section 2 goes to infinity. Hence, our method enjoys the aforementioned two desired properties.
Also, the communication complexity
Related Work
Here, we briefly review the related studies to our paper.
Local methods. Several recent papers have studied local algorithms combined with variance reduction technique [23 2 14 Sharma et al. (23) have proposed a local variant of SPIDER (3) and shown that the proposed algorithm achieves the optimal total computational complexity. However, the communication complexity essentially matches the ones of non-local SARAH and no advantage of localization has been shown. Khanduri et [14] have proposed STEM and its variants based on their called two-sided momentum, but again the communication complexity does not improve non-local methods. Also, Das al. have considered a SPIDER like local algorithm called FedGLOMO but the derived communication complexity is even worse than minibatch SARAH. Karimireddy et al.
[T]] have proposed Mime, which is a general framework to mitigate client-drift. Particularly, under 8-Bounded Hessian Dissimilarity (BHD O their MimeMVR achieves communication complexity of
1/(Pe))+0((VF) 8/5² when B + oo, that is better than the one of minibatch SGD 1/e² when
3

---

8 S VPs. However, the asymptotic rate is still worse than the one of BVR-L-SGD Ç/=² because S 8 aaways holds.
Second-order guarantee. Neon 29 and Neon2 [ are generic first-order methods with second-order
guarantees, that repeatedly run first-order guaranteed algorithm and negative curvature descent. Another approach is a parameter perturbation for SGD. For the first time, Ge et al. [4] have shown that SGD with a simple parameter perturbation escapes saddle points efficiently. Later, the analysis has been refined by g [ Recently, applying variance reduction technique to second-order guaranteed methods has been also studied [5] 17 and particularly Li al. [77 have proposed SSRGD that
combines SARAH [20] with parameter perturbation and shown that SSRGD nearly achieves the
optimal computational complexity with second-order optimality guarantees.
2 Problem Definition and Assumptions
In this section, we first introduce several notations and definitions used in this paper. Then, the problem settings are described and theoretical assumptions used in our analysis are given.
Notation. || || denotes the Euclidean L2 norm || ||2: ||=||= = VE,
V oo for vector x. For matrix X, || denotes the induced norm by the Euclidean L2 norm. For a natural number m. [m] means the set 2 m). For a set A, # A means the number of elements, which is possibly co. For any number a, b, a V b and a A b denote maxfa,, by and min(a, b} respectively. We denote the uniform distribution over by (nif (A). Given K, K,T.S S N. let I(k, t, be integer
Kt + KT's for k [ U [0), t E [T 1] U {0} and $ [S U {0}. Note that I(K, t. s) = [ + 1, s) and
T(k: T, = T(k: 0, 8 + 1) for & E [K] [0), (T- - 11 and E [S - 1]U (0). B denotes
the set {x E -2 ||=|| S r). which the Euclidean ball in Idd with radius r.
Definition 2.1 (Gradient Lipschitzness). A differentiable function f : IRd + R is L-gradient Lipschitz if f[= ff(y) < L||= yll, Vn, E R
Definition 2.2 (Hessian Lipschitzness). A twice differentiable function : .Rd IR is p-Hessian Lipschitz if V (xx) - [()]] < p| vll, Vx, y E Rd.
Definition 2.3 (Second-orde optimality). For p-Hessian Lipschitz function f, R is an e-second-order optimal point of f if [[V]())] < E and (²f(x) 2 - VpeT.
2.1 Problem Settings
Objective function. We want to minimize nonconvex smooth objective f(x) == 3o Ep fo(x).
where fp(x) := E2-D,, =)] for x E IR4, where D, is the data distribution associated with worker In this paper, we focus on offline settings (i.c., #supp(D,)) < oo for every p [P]) for simple presentation. It easy to extend our results to online settings. Also, just that each local dataset has an equal number of samples, i.e., #supp where n is the total number of samples.
just for simplicity, it assumed
n/ P for every p E (P),
Optimization criteria. Since objective function f is nonconvex, it is generally difficult to find global minima of f. Previous work in distributed learning has mainly focused on finding first-order stationary points of f. In this study, we aim to find e-second-order stationary points of f in distributed learning settings.
Data access constraints and communication settings. It is assumed that each worker p can only access the own data distribution D, without communication. Aggregation (c.g., summation) of all the worker's 's d-dimensional parameters or broadcast of d-dimensional parameter from one worker to the other workers can be realized by single communication. 3
Evaluation criteria: communication complexity. In this paper, compare communication complexities of optimization algorithms to satisfy the aforementioned optimization criteria. In typical situations, single communication more time-consuming than single stochastic gradient computation. Let C be the single communication cost and G be the single stochastic gradient computation cost. Using these notations, C > G is assumed. We expect that increasing the number of available stochastic
+8-BHD condition in I requires V x) v fxx]] I ō for every 12d, 2 Dg and p E [P]. Note that ó 6-BHD condition requires both intra Hessian dissimilarity boundedness f1² D f()]]] which is bounded by ( under Assumption I and additionally inner Hessian dissimilarity [[, fi())) Hence, 8- BHD much stronger than Assumption I and it is possible that à > C.

---

gradients in single communication round leads to faster convergence. Hence, it is natural to increase the number of stochastic gradient computations in a single communication round unless the total stochastic gradient computation time exceeds C to reduce the total running time. This motivates the concept of local computation budget B (S C/G): given a communication and computational environment, it is assumed that each worker can only computes at most B single stochastic gradients per communication round on average. Then, we compare the communication complexity, that is the total number of communication rounds of distributed optimization algorithm to achieve the desired optimization accuracy. From the definition, we can see that the communication complexity on fixed local computation budget B == C/G captures the best achievable total running time of an algorithm.
2.2 Theoretical Assumptions
In this paper, we assume the following five assumptions. The first one has already been adopted in several previous work 122 19]. The other ones are standard in the nonconvex optimization literature to guarantees second-order optimality.
Assumption (Hessian heterogeneity any p.p' E [P]. f((x) V
[22
(f2) is second-order ( (-heterogeneous, i.e., for 19
fo
x
S S. Va E =..
Assumption 1 characterizes the heterogeneity of local objectives {fp) in terms of Hessians and has a important Tole in our analysis. Intuitively, we expect that relatively small heterogeneity parameter to the smoothness parameter L (defined in Assumption [ reduces the necessary number of communi- cation rounds to optimize the global objective. Especially when the local objectives are identical, i.e., Dp = Dr for every p.p' E [P]. < becomes zero. When each Dp is the empirical distribution of n
((vP/nL) 2 for fixed x. Hence, in traditional distributed learning regimes, Assumption naturally holds. An important remark that Assumption implies Ç S 2L, i.e., the heterogeneity is bounded by the smoothness. Even in federated learning regimes, we expect Ç < 2L for some problems practically.
IID samples from common data distribution D, we have f(²) V2 f
S frr())))
(x)]
with high probability by matrix Hoeffding's 's inequality under Assumption
Assumption 2 (Gradient Lipschitzness). Vp [P], = E supp(D,). ((,,)) is L-gradient Lipschitz.
Assumption (Existence of global optimum). f has a global minimizer x, E IR
Assumption (Hessian Lipschitzness). Vp [P], 2 E supp(D,)) {(,, 2) is p-Hessian Lipschitz. Assumption 5 (Bounded stochastic gradient). Vp E [P], = E supp(D,), Vi(;, is G-bounded, i.e. [[V((z, =)]l S G, Vx E Rdd
In our analysis. G has no significant impact because G only depends on our theoretical communication complexity in logarithmic order.
3 Main Ideas and Proposed Algorithm
Our proposed algorithm is based on natural combination of (i) Bias- Variana Reduced (BVR) estimator; and (ii) parameter perturbation at each local update. The first idea has been proposed by [19] to find first-order stationary points with small communication complexity. The second one is a well-known approach to find second-order stationary points in non-distributed nonconvex optimization 4 g 9. In this section, we illustrate these two ideas and provide its concrete procedures.
3.1 Review of BVR Estimator 119
The bias-variance reduced estimator aims to efficiently find first-order stationary points by simul- tancously reducing the bias caused by local gradient descent steps and the variance caused by stochastization of the used gradients.
First we consider why the standard local SGD is not sufficient to achieve fast convergence and sometimes slower than minibatch SGD. Recall that in local SGD each worker takes the update rules
'In this work, it assumed that all the workers can participate in a single communication. It is not so hard to extend our algorithm and analysis to worker sampling settings, which is more realistic in cross-devies federated learning.
5

---

Algorithm 1 PSVD--- n, b. K,T.S.T
1: Add noise d0 To + - where {-1 ~ Bn))
2:
for 0 S - do
3: forp- 1 to P in parallel do
4: (p)
(x
+)),,0,s) 5: end for
6: Communicate { ((0.0.s) p=1 Set v1(0.0.s) $ &E==1 T(0.0a))
(p)
7: for = to T do
8: for p = 1 to P in parallel do
9:
(p)
Kb Zi
1
Kb
10:
((0,
()).ref
Kō
1 Kb VE( 21,10)))))) (21,)(0 itd Dp).
EE
(p)
1 1:21 (2100) 91(,11s) ((0,t-1,s)) + 1 (p)
(p)
(p).re (p)
11:
(1000,s)) end for
(0,0,a)
12:
13:
Communicate {u [1),,,,s) p- Set vI(...s) = 1 Ep ((0.,,s)
IP
14:
Randomly select Pt.s Un. # Only worker pt,, runs local optimization. for k = to - do
15:
16:
by 11 == (mod[vK) K b + I kyp (mod[vR1)
(I(k,,,)) by EIn ([[0I[).1,))=
rel = b% Ee VE((I((K1,.)))) 211((,1,,)) (#I,I(),1..) is.d Dr..).
18:
(I(k...e
VT(R.A,s) = 1121(9((4...))) 97(k.t.)) + (((0)))),s)) + I.=UV1(0,,)))-
20:
Update T((++1A55) = Ii(k,t,s) TUI(K,))))
21:
Add noise T1(++1,4.)) = T1(k+11,)) + (EI(ka)))) where EI(ke),)) ~ Un)) end for
22:
23:
Communicate 1,(0
end for
25: end for
of x
1++1
(p) =1(²²
- for le [B/b] in each communication round, where (() is stochastic
19
(p)
gradient with minibatch size b o (p) local dataset D, and B is given local computation budget.
In typical convergence analysis, we need to bound the expected deviation of 9k
(p) from ideal global
gradient (xx), that is E Ellg(()) (v I| = [V - [(x (P) 1 (p) V (p(()())))
(P)
The former term is called bias and the latter one is called variance. Á typical assumption to bound the first term is bounded gradient heterogeneity assumption, that requires f Vf(x)] s S1
for every x E Rdd and p E [P]. Under this assumption, the first term is only bounded by S1, that is constant. The second term is typically bounded by o² b for g with minibatch size b, when the variance of single stochastic gradient is bounded by o². These facts show that the bias is still constant and does not vanish even if minibatch size b is enhanced and the variance vanishes. This is why local SGD can be worse than minibatch SGD when Çi is not too small. Also, we can that the variance is still a constant for fixed minibatch size and this is a common reason why minibatch SGD and local SGD only show slow convergences. These observations give critical motivations of the simultancous reduction of the bias and variance.
The biai-variance reduced estimator o is defined v( = (1/b) El= (EEEnV((r))) (Vi(T))) xx) Vi(No, 21)) + (x()) (SVRG version). It known that the bias caused by localization can be bounded by $110(6)) zoll and the variance caused by stochastization can be bounded by (L2/6)]l=(? =ol?,, where Ç is the Hessian heterogeneity of {fr) and is the smoothness of f. This implies that both the bias and variance of ez converges zero .,(P) and zo go x.. In other words, bias-variance reduced estimator Uk is asymptotically consistent to the global gradient v (a(( by using periodically computed global full gradients V (xo)). We actually adopt SARAH version of BVR estimator in [9] rather than SVRG one due to its theoretical advantages.

---

3.2 Parameter Perturbation at Local Updates
Although the bias-variance reduced estimator useful to guarantee first-order optimality with small communication complexity in noncovex optimization, the algorithm often gets stuck at saddle points. To tackle this problem, we borrow the ideas of escaping saddle points in non-distributed nonconvex optimization. Particularly, to efficiently find second-order optimal points, we utilize parameter perturbation. Parameter perturbation a familiar approach in non-distributed nonconvex optimization. Specifically, Jin et al.
g [ have considered the update rule of #*++ 24 1/ fx*x) 775k, where
&A ~ (B;) for some small radius т. This algorithm is called Perturbed GD (PGD) or Noisy GD. Similar to this formulation, we add noise each local update, i.c., #2+1 2 (p)) R++1 + n
where 'k+1 = k The intuition behind the noise addition is that random noise has some components along the negative curvature directions of the global objective around the saddle point, and we expect that noise addition helps the parameter proceed the decreasing directions of f and escape the saddle points.
Necessity of local perturbation. Perturbing the global model at the server side is an intuitive way, but not sufficient for communication efficiency when we want to utilize small heterogeneity of the local datasets (i.e., Ç < L). The Slas-variance reduced estimator with local perturbation enables to escape multiple global saddle points in local optimization and achieves second-order optimality with communication complexity ((</=²) for sufficiently large B. In contrast, perturbing the global parameter at the server side only ensures escape single global saddle point each round and only achieves communication complexity of (T./e²)) This is the reason why local perturbation rather than global one is adopted.
3.3 Concrete Procedures
The full description of our proposed Bias- Variance Reduced Local Perturbed SGD (BVR-L-PSGD) is given in Algorithm I When we set the noise size r = O, Algorithm I essentially matches BVR-L- SGD. Additionally setting K = 1, Algorithm | matches SARAH. The algorithm requires ((ST) communication rounds. At each communication round, each worker computes large batch stochastic gradients and the server constructs U)(0,c,s) by aggregating them. (I(0...s)) is used as an estimator of (z to reduce computational cost. In line 14-21, we randomly select worker Pt.s and only worker Pt,, runs local optimization as described above. In the local optimization, we use SARAH like bias variance reduced estimator (line 16- 16-18) rather than SVRG one and add noise (line 20) at each local update.
4 Convergence Analysis
In this section, we provide convergence theory of BVR-L-PSGD (Algorithm D. All the omitted proofs are found in the supplementary material. For simple presentations, we use θ symbol to hide extra moly-logarithmic factors that depend on L, p, G, K, b, T, where q represents the confidence parameter in high probability bounds.
4.1 Finding First-Order Stationary Points
First, we derive Descent Lemma for BVR-L-PSGE and first-order optimality guarantees by using it.
Proposition 4.1 (Descent Lemma). Let S E N and Ilk, t) 2 I(ku, to, so) [KTS] U {0}. 5 hold. Given q E (0, r 0, if we appropriately choose
Suppose that Assumptions 2
3 and
= O A 1/(K)) A Vb/K/L (VK()),)) it holds that
I(k-1,t,s) Σ
f(F((LL))) S ( i= tok0
[VF((z)) 1/1r2 + Rı
with probability least 1 39.
Here,
A
I(k, T(ko,to, to 80).
R1 = An -/=1( (ko, || - xi
1(k.t,))-1
+
E (AAAK
(i=
> [(ko 1|2111 - x2,12 +
AAKK _ [(00.a..0)- ||0 22ll2) for some universal constant Cn 0.
_i=11000.00)
7

---

From Proposition 4.1 with [kk, to, so) < 0 and I(k,t, t KTS gives the following corollary.
Corollary 4.2. Suppose that Assumptions
hold. Under the same setting as in Proposition }), with probability least 1 3q, there exists i
4.3 and S (z)()) f(x,)) ( Te
[KTS- - 1 [0} such that (Z.) S.
Remark (Communication complexity). The total number of communication rounds @(TS) becomes
δ ( (L/K + (L/K+ + + /TLL//T/// (f - ((=)))/ Given local computation budget B, we set 7 == @(1 n/(B)) and Kb ( with b < @(vB). Then, we have the averaged number of local computations per communication round Kb + (/(P)) = (B)) and the communication complexity TS with budget B becomes
(1
AL BP
2)
BP
vB
which matches the best known communication complexity [19]
4.2 Escaping Saddle Points
Next, we show that BVR-L-PSGD implicitly exploits the negative curvature of f around saddle points and efficiently escapes the saddle points by utilizing the asymptotic consistency of BVR estimator and the parameter perturbation at each local update.
We rely on the technique of coupling sequence 19). Given saddle point T (K(ko and î 2 [ko, to, so), we define a new sequence {ar]] (mko as follows:
(1) (571 Emin) = - (57 emnn); (2) (5'. e₁) = (E7, e,) for j E { ......dH, d}; and (3) All the other randomness is completely same as the one of [==]/=0 KTS- Let ro == KEf. emin) I. Note that [5y Ej, emin) = 2ro and thus lk - Egl 2rg. Also, observe that .741 F = n1Er Ej. emin emin.
We define 7 used in the definition of coupling sequence as follows:
I(ko, to: so); [Kk) to s0) 1,
(1/(nA) S VK)
(VK < 1/(nA) S K)
i==
I(0, s,) 11
(K< 1/(1) S KKT
I(0,0, 80 + 11
(KT < 1/(1A)
Here, Kn is the minimum index k that satisfies k >> ko and l 0 (mod v k)). We can easily check
that T T(ko, to. s0) S 1/(r)))
Then, we show that either of the two sequences {x.} or {œ{} efficiently escapes the saddle points by bounding the norm of the cumulative difference of x; and x from below. The novel and most difficult part of the analysis is to evaluate the norm of the cumulative difference of the deviations
1Σ J (v: fz(z)) - of + V fx())) generated by the two sequences, where vf denotes the BVR estimator at iteration generated by sequence {x(}.
Proposition 4.3 (Implicit Negative Curvature Exploitation). Let I(ko, to so) E [KTS] U (0). Suppose that Assumptions 7 and 5 hold, (T )ll S and the minimum eigenvalue Amnn of H == (() satisfies X == - -mnin > Vpc. Under b = Q(K V K((VKpp)) V (PPK)) we appropriately choose Ti(karto,so) = ((1/(nA)), 17 O(L/LAL/(KC))////K VPb/(V L)), with Fi(kotto.50) CFnJT(ko.ttoso)" 2 and r C, (cF = ((1) and c, 6(1))
we have
(II(kk))toa)) S - F Fliko,Ao,8o) Rs
with probability at least 1/2 9q/2. Here, R2 = 20y Trikgtoorg AK ((ko.to.80)-- ||0++1 - 12
Exe (0,00))0)
20g Jrik tnlko ATT Σ 1(0.to-00)-1 2i=1(0.0.50)
| 1;1l2 for some universal constant On > O.
KT
Proposition 4.3 says the function value decreases by roughly Fr(kn.ta.so) and the global model escapes saddle points with probability at least 1/2 after Ji(ko.to.eo) local steps.
8

---

4.3 Finding Second-Orde Stationary Points
In this subsection, we derive final theorem that guarantees the second-order optimality of the global model by combining Propositions 4. and 4.3
Theorem 4.4 (Final Theorem), Suppose that Assumptions 7
2
3
4 and S hold. Under b =
Q(KVI/ 1 pε) v TT(PK)), if we appropriately choose = ((1 A (/((K) A Vb/K
/Pb/(VKTL), r (()) and S @ + 1/2, there exists E [KTS]] U {0) such that 34 is e-second-order optimal point of /
with probability at least
Remark (High probability bound). Theorem 4.4 guarantees that Algorithm finds an approximate
second-order optimal point in KTS iterations with probability at least 1/2. Repeating Algorithm (lgg(1/)) times guarantees that the same statement holds with probability at least - q.
Remark (Communication complexity). The total number of communication rounds TS is given by
δ O (L/K + + L/VKb- VTL/VKPb, (f(2)) - [(x.))/ .Given local computation budget B, we set T == @ + nBP)) and Kb == ( with b < @(VB). Then, we have the averaged number of local computations per communication round Kb + (/TP)) = (B)) and the communication complexity (TT)) with budget B becomes
δ (
VB 1
This implies that for < = o( L)) the communication complexity strictly smaller than the one of minibatch SGD Õ(1 + L/e+ + G2 / (BPE))). Note that the rate matches to the one of BVR-L-SGD [1]. Hence, our method finds second-order optimal points without hurting communication efficiency of the state-of-thh-art first-order optimality guaranteed method. Furthermore, when B - oc, we have
Ô(1 + c/E²), that goes to (1) as Ç 0.
In summary, BVR-L-PSGD enjoys the desirable properties (i) and (ii) described in Section !
5 Numerical Resutls
In this section, we give some experimental results to verify our theoretical findings.
Data Preparation. We artificially generated heterogencous local datasets from CIFARIC dataset. The data preparation procedure is completely in accordance with [19] and the details are found in 19 We set homogeneity parameter q to 0.35, which captures how similar the local datasets
(q = 0.1 corresponds to I.L.D. case and higher g does to higher heterogeneity).
Model. We conducted our experiments using two-hidden layers fully connected neural network with 100 hidden units and softplus activation. For loss function, we used the standard cross-entropy loss. We initialized parameters by uniformly sampling the parameters from |-1/100, 1/100].
Implemented Algorithms. Minibatch SGD, Noisy Minibatch SGD, BVR-L-SGD [19 and our proposed BVR-L-PSGD were implemented. We set K = 64 and b = 16, and thus B = 1024. For BVR-L-PSGID, the noise radius was tuned from r E {0.5, 2.5, 12.5). For each algorithm, we tuned learning rate 7 from (0.005, 0.01, 0.05, 0.1, 0.5, 1.0]. The details of the tuning procedure are found in the supplementary material.
Evaluation. We compared the implemented algorithms using six criteria of train gradient norm [V][()]]; train loss; train accuracy; test gradient norm; loss and test accuracy against the number of communication rounds. The total number of communication rounds was fixed to 1, 000 for each algorithm. We independently repeated the experiments 5 times and report the mean and standard deviation of the above criteria. Due to the space limitation, we will only report train gradient norm, train loss and test accuracy in the main paper. The full results are found in the supplementary material.
Results. Figure T shows the performances of BVR-L-SGD and our proposed algorithm. We can
"One limitation of Theorem 4.4 is that it only guarantees the existence of e-second-order optimal point H, in the history of (ž. < KT5-1 However. this also the case in the existing studies 17. We empirically found that the outputs of each communication rounds showed stable performances (see Section https://wwwe cs. toronto. maauu//kri//cee for html

---

0= 1004
q= 0.35, 8= 1024
10224
q= 0.35,35.8 1024
2.5
50
107
2.4
Nolay 5GD
Noisy SGD
Nelay SGD
10-2 Propisse
LGD
2.0
Proposed
BVR SGD
test acc
Proposse
5GD
1.8
30
10"
20
10
1.2
10
100 # Communication Rounds/10
20
30
40
60 70
10
20 30
40
50 00 70
50
100
20 40
00 70 00 90 100
# Communication Rounds/10
# Communication Rounds/10
(a) Train Gradient Norm
(b) Train Loss
(c) Test Accuracy
Figure I:
Comparison of (a) train gradient norm; (b) train loss; and (iii) test accuracy against the number of communication rounds for three layered DNN on heterogeneous CIFARIO.
that the both algorithms got stuck at small gradient norm region in initial rounds. After that BVR-L-SGD showed unstable convergence and took a lot of time to escape the stucked region. In contrast, proposed method efficiently escaped the stucked region and consistently achieves better train loss and test accuracy than BVR-L-SGD. Also, our method consistently outperformed Minibatch SGD and Noisy Minihatch SGD.
Conclusion
In this paper, we have studied a new local algorithm called Bias- Variance Reduced Local Perturbed SGD (BVR-L-PSGD) based combination of the birs-variance reduced gradient estimator with parameter perturbation to efficiently find second-order optimal points in centralized nonconvex distributed optimization. We have shown that BVR-L-PSGD enjoys second-order optimality without hurting the best known communication complexity for first-order optimality guarantees. Particularly, the communication complexity is better than non-local methods when Hessian heterogeneity ( of local datasets smaller than the smoothness of the local loss in order sense. Also, for sufficiently large B, the communication complexity of our method approaches to @(1) when the local datasets heterogeneity goes to zero. The numerical results have validated our theoretical findings.
Acknowledgement
TS was partially supported by JSPS KAKENHI (20H00576) and JST CREST. The authors would like thank Kazusato Oko for his helpful advice.
References
[1] Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. Advances Neural Information Processing Systems, 31, 2018.
[2] Rudrajit Das, Anish Acharya, Abolfazl Hashemi, Sujay Sanghavi, Inderjit Dhillon, and Ufuk Topcu. Faster non-convex federated learning via global and local momentum. In Uncertainty in Artificial Intelligence, pages 496-506. PMLR, 2022.
[3] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic path-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018.
[4] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-onling stochastic gradient for tensor decomposition. In Conference learning theory, pages 797-842. PMLR, 2015.
[5] Rong Ge, Zhize Li, Weiyao Wang, and Xiang Wang. Stabilized svrg: Simple variance reduction for nonconvex optimization. In Conference learning theory, pages 1394-1448, PMLR, 2019.
10

---

[6] Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. Advances in Neural Information Processing Systems, 32, 2019.
[7] Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint arXiv:I910 10910.1442.. I4425, 2019.
[8] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732 PMLR, 2017.
[9] 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.
[10] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26:3 16:315-323, 323,,, 2013.
[11] Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint (XXi::0088.03606 2020.
[12] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR, 2020.
[13] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneouss data. In International Conference on Artificial Intelligence and Statistics, pages 4519-4529. PMLR, 2020.
[14] Prashant Khanduri, Pranay Sharma, Haibo Yang. Mingyi Hong, Jia Liu, Ketan Rajawat, and Pramod K Varshney. Achieving optimal sample and communication complexities for non-iid federated learning. ICML Workshop on Federated Learning for User Privacy and Data Confidentiality, 2021.
[15] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393, PMLR, 2020.
[16] Jakub Konečný, Brendan McMahan, and Daniel Ramage. Federated optimization: Distributed optimization beyond the datacenter. arXiv preprint arXiv: 1.0355,, 2015.
[17] Zhize Li. Ssrgd: Simple stochastic recursive gradient descent for escaping saddle points. Advances in Neurul Information Processing Systems, 32, 2019.
[18] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas Communication-eficeee efficient learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273-1282. PMLR, 2017.
[19] Tomoya Murata and Taiji Suzuki. Bias-variance reduced local sgd for less heterogeneous federated learning. In International Conference on Machine Learning, pages 7872-7881.
PMLR, 2021.
[20] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages 2613-2621. PMLR, 2017.
[21] Lam M Nguyen, Marten van Dijk, Dzung T Phan, Phuong Ha Nguyen, Tsui- Wei Weng, and Jayant R Kalagnanam. Finite-sum smooth optimization with sarah. Computational Optimization and Applications, pages 1 1-33, 2022.
[22] Sashank J Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póczós, and Alex Smola. Aide: Fast and communication efficient distributed optimization. arXiv preprint arXiv: 1608.06879, 2016.

---

[23] Pranay Sharma, Swatantra Kafle, Prashant Khanduri, Saikiran Bulusu, Ketan Rajawat, and Pramod Varshney. Parallel restarted spider- coddurccmmmiicationn efficient distributed nonconvex optimization with optimal computation complexity. arXiv preprint arXiv: 22006636 2019.
[24] Reza Shokri and Vitaly Shmatikov. Privacy-preseriing deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1310-1321, 2015.
[25] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv: 2018.
[26] Stefan Vlaski, Elsa Rizk, and Ali H Sayed. Second-order guarantees in federated learning. In 2020 54th Asilomar Conference on Signals, Systems, and Computers, pages 915-922. IEEE, 2020.
[27] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Mcmahan, Ohad Shamir, and Nathan Srebro. Is local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334-10343, PMLR, 2020.
[28] Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heteroge- neous distributed learning. Advances in Neural Information Processing Systems, 33:6281-6292, 2020.
[29] Yi Xu, Rong Jin, and Tianbao Yang. First-order stochastic algorithms for escaping from saddle points in almost linear time. Advances in neural information processing systems, 31, 2018.
[30] Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5693-5700, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Section |
(b) Did you describe the limitations of your work? [Yes] See Section 4
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See section
(b) Did you include complete proofs all theoretical results? [Yes] See Section and the supplementary material.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as a URL)? [Yes] See Section 3 and the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section and the supplementary material.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Section [5]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See the supplementary material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 5
(b) Did you mention the license of the assets? [N/A]
12

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' roure using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "Q6P1-E8N6S", "reviewer": "Reviewer_RYcp", "summary": "This work proposes a new local algorithm called Bias-Variance Reduced Local Perturbed SGD (BVR-L-PSGD), via a simple combination of the existing bias and variance reduced gradient estimator and parameter perturbation. BVR-L-PSGD converges to second-order stationary point of non-convex federated optimization problem with nearly the same communication complexity as the best known one of BVR-L-SGD to find first-order stationary point, which is smaller than non-local minibatch SGD when the local datasets heterogeneity is smaller than the smoothness of the local loss. The communication efficiency over BVR-L-SGD is demonstrated via experiments. ", "questions": "(1) Could you explain what is a local method in introduction? (i.e., the difference between local and non-local methods) Which methods in Table 1 are non-local? Why are local methods in related work not listed in Table 1? \n\t\n(2) The first sentence in \"**Open question**\" in the introduction has grammar mistake that hinders understanding. Do you mean \"it is not well-studied how to find second-order optimal points with **low communication cost** and **thus** we have the following research question**s**\"?\n\t\n(3) At the beginning of \"**Main Contributions**\", you might mention something like \"which positively answered the above research questions\". \n\t\n(4) Gradient norm bound $G$ is very strong. There are some works that did not use this assumption, like [13,14] cited in your paper. Is it possible use a weaker assumption instead? (e.g. $\\frac{1}{P}\\sum_{p=1}^{P}\\|f_p(x)\\|^2\\le G^2+B^2\\|\\nabla f(x)\\|^2$ in [13]) Also, do all the works in Table 1 use Assumptions 2-5? This relates to fairness of comparison. \n\t\n(5) From Table 1, it seems that to let your commmunication complexity is smaller than non-local minibatch SGD, we not only require small $\\zeta$, but also small $n$ relative to $\\epsilon$, right? \n\t\n(6) (Minor) In line 136, I think it sufficient to write #supp$(D_p)=n/P$ for every $p\\in[P]$. \n\n(7) In Algorithm 1, $x_0=\\widetilde{x} _ 0+\\eta\\xi_{-1}$ seems equivalent to directly initializing $x_0$. How about removing this line and replacing input $\\widetilde{x}_0$ with $x_0$? \n\t\n(8) In Algorithm 1, lines 8-13 can be put in the block \"if $t\\ge 1$\" as we do not need to do these when $t=0$. Acccordingly, line 11 can be simplified. Similarly, lines 16-18 can be put in \"if $k\\ge 1$\" and line 18 can be simplified. \n\t\n(9) STORM variance reduction does not need large batchsize (you may see Appendix B of [1] for the complexity result that does not need assumption on gradient norm bound), but both achieves the same near-optimal sample complexity as SARAH/SPIDER. They may further reduce complexity and might be a future direction. \n\n[1] Cutkosky, Ashok, and Francesco Orabona. \"Momentum-based variance reduction in non-convex sgd.\" Advances in neural information processing systems 32 (2019). \n\n(10) (Grammar) In line 251, you may use \"poly-logarithmic factors **that** depend on\". \n\t\n(11) In line 264, should the total number of communication rounds be $2TS+1$? \n\t\n(12) The hyperparameter choices in the propostions, theorems and corollaries are expressed using $\\widetilde{\\Theta}$. It is highly recommended to express their full form either in the main text, or in the appendix and tell the locations right after $\\widetilde{\\Theta}$. \n\t\n(13) In Figs. 1-3, the gradient norms of both algorithms increase and converge to 1 (looks very large) instead of 0. How to explain? Also, you may add plot of $-\\lambda_{\\min} \\big(\\nabla^2 f(x_t)\\big)$ to demonstrate convergence of your proposed algorithm to second-order stationary point. In addition, you have made the claim that your communication complexity is lower than non-local minibatch SGD for $\\zeta\\ll L$, yes? If so, you would better demonstrate that by comparing with non-local minibatch SGD.", "limitations": "I only found the limitation mentioned in the footnote in page 8. Is that correct? Just make sure. \nThat limitation is also in existing studies and thus I think it fine that this work has not addressed this limitation. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: This work simply combines BVR-L-PSGD and parameter perturbation in algorithm design, but it has better complexity in achieving second-order stationary point for nonconvex federated optimization. Technical novelty is also explicitly expressed. Lit review looks good to me. Therefore, I think the originality is sufficient for Neurips. \n\t\nQuality: The claims are well supported by theoretical results on communication complexity and partially supported by experiments which have some flaws as I mentioned in my final question. \n\t\nClarity: This paper is clearly written and well organized. \n\t\nSignificance: The results are important to me since BVR-L-PSGD converges to second-order stationary point of non-convex federated optimization problem with nearly the same communication complexity as the best known one of BVR-L-SGD to find first-order stationary point, which is smaller than non-local minibatch SGD when the local datasets heterogeneity is smaller than the smoothness of the local loss. The strong gradient norm assumption and flaws in experiment kind of undermines significance, as elaborated in my questions. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "MJU9AN1vjU", "reviewer": "Reviewer_sztZ", "summary": "The previously proposed method BVR-L-SGD (using bias-variance reduced gradient estimator) is claimed to be one of the best first-order optimality methods for nonconvex distributed learning. This paper integrates the parameter perturbation into the existed BVR-L-SGD, named BVR-L-PSGD, to give it second-order optimality.", "questions": "I think the author should clarify and emphasize the significance of such a second-order up-gradation. ", "limitations": "No potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths：\nIt’s a second-order optimality upgraded version of the existed BVR-L-SGD. This is a nice extension. It will be better if the author can add more contents to show this work is the state-of-the-art second-order method.\n\nCombining the parameter perturbation, which is an easy-installed approach that has been validated by previous works. So, it is intuitive and totally makes sense.\n\nWeaknesses：\nThere is only one second-order method mentioned in the theoretical baseline. \n\nFor the experiment side, it only compares the BVR-L-SGD and BVR-L-PSGD proposed.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Bk5A-gH3lA", "reviewer": "Reviewer_hqiv", "summary": "This paper proposes a new algorithm called Bias-variacne reduced local perturbed SGD for nonconvex distributed learning to efficiently find second-order optimal points, and furthermore, it is proved in this paper that this new algorithm escapes saddle points, which implies the convergence to approximate second-order stationarity. \n\nThis result is built on the former 1st-order convergence guarantee of BVR-L-SGD, the main techniques of the approximate second order convergence/escaping saddle points come from the well-known work of Ge. Et al and other related works since 2015. The novelty is clear.\n", "questions": "One question I am interested in is presented above. \nAdditionally, can the authors discuss a bit on the main challenge comparing to the work of [10]? \nIs it possible to get rate of escaping saddle points without perturbation for BVR-L-SGD?", "limitations": "The limitation of the result in this paper might be the dependence on the parameters, how to set these parameters in real applications? From theoretical perspective, assuming the Hessian to be Lipschitz is reasonable but this constrains the application of perturbed GD in contrast to the gradient descent which only requires Lipschitz gradient to get saddle avoidance result. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The main strength is the theoretical contribution, it is good to see the idea of [10] on perturbed SGD can be extended to other settings.\n\nWeaknesses: Considering the complexity of the algorithm itself, it is better if the authors can provide more guidance on the setting of parameters. \n\nIt is not clear whether current algorithm really outperforms BVR-L-SGD (without perturbation) in the following sense: Combined with the result of “On the almost sure convergence of stochastic gradient descent in non-convex problems, 2020”, it is not hard to believe that BVR-L-SGD likely avoids saddle points.\n\n Is it possible to compare the quality of the second order information of the outputs by using these two algorithms, BVR-L-SGD and BVR-L-PSGD?  \n\nThe authors could have done a better survey on “escaping saddle points” literature, e.g. \n\nEscaping saddle points with adaptive gradient methods, Staib et al. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept