Finding Local Minima Efficiently in Decentralized Optimization
Authors: Wenhan Xian
Heng Huang
Venue: NeurIPS 2023 poster (2023)
Keywords: second-order optimality
decentralized optimization

Abstract: In this paper we study the second-order optimality of decentralized stochastic algorithm that escapes saddle point efficiently for nonconvex optimization problems. We propose a new pure gradient-based decentralized stochastic algorithm PEDESTAL with a novel convergence analysis framework to address the technical challenges unique to the decentralized stochastic setting. Our method is the first decentralized stochastic algorithm to achieve second-order optimality with non-asymptotic analysis. We provide theoretical guarantees with the gradient complexity of $\tilde{O} (\epsilon^{-3})$ to find $O(\epsilon, \sqrt{\epsilon})$-second-order stationary point, which matches state-of-the-art results of centralized counterparts or decentralized methods to find first-order stationary point. We also conduct two decentralized tasks in our experiments, a matrix sensing task with synthetic data and a matrix factorization task with a real-world dataset to validate the performance of our method.

Finding Local Minima Efficiently in Decentralized Optimization
Wenhan Xian
Heng Huang
Computer Science
Computer Science
University of Maryland College Park wxian an1 @umd. edu
University of Maryland College Park heng@umd.. edu
Abstract
In this paper we study the second-order optimality of decentralized stochastic algorithm that escapes saddle point efficiently for nonconvex optimization prob- lems. We propose new pure gradient-based decentralized stochastic algorithm PEDESTAL with a novel convergence analysis framework to address the techni- cal challenges unique to the decentralized stochastic setting. Our method is the first decentralized stochastic algorithm to achieve second-order optimality with non-asymptotic analysis. We provide theoretical guarantees with the gradient com- plexity of Ö(E-3) to find Ole, vē) ((e))-)cooddodde stationary point, which matches state-of-the-art results of centralized counterparts or decentralized methods to find first-order stationary point. We also conduct two decentralized tasks in exper- iments, a matrix sensing task with synthetic data and a matrix factorization task with worldworld dataset to validate the performance of our method.
1 Introduction
Decentralized optimization is class of distributed optimization that trains models in parallel across multiple worker nodes over decentralized communication network. Decentralized optimization has recently attracted increased attention machine learning and emerged as a promising framework to solve large-scale tasks because of its capability to reduce communication costs. In the conventional centralized paradigm, all worker nodes need to communicate with the central node, which results in high communication cost the central node when the number of nodes is large the transmission between the center and some remote nodes suffers network latency. Conversely, decentralized optimization avoids these issues since each worker node only communicates with its neighbors.
Although decentralized optimization has shown advantageous performance in many previous works (Lian et al.] [2017). Tang et al. (2018)), the study of second-order optimality for decentralized stochastic optimization algorithms is still limited. Escaping saddle point and finding local minima problem in nonconvex optimization since saddle point is category of first-order stationary point that can be reached by many gradient-basse based optimizers such as gradient descent but it is not the expected point to minimize the objective function.
Perturbed gradient descent (Jin al. (017]) and negative curvature descent (Xu al. (018)) (8).
Allen-Zhu and Li (018)) are two primary pure gradient-based methods (not involving second-orde -oddr derivatives) to achieve second-order optimality. Typically, perturbed gradient descent method is composed of descent phase and an escaping phase. If the norm of gradient is large, the algorithm will run the descent phase as normal. Otherwise will run escaping phase to discriminate whether the candidate first-order stationary point is saddle point or local minimum. Negative curvature
"This work was partially supported by NSF IIS 1838627, 1837956, 1956002, 221 1492, CNS 2213701, CCF 2217003, DBI 2225775.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

descent method escapes saddle point by computing the direction of negative curvature at the candidate point, If it is categorized as saddle point then the algorithm will update along the direction of negative curvature. Generally it involves a nested loop to perform the negative curvature subroutine.
Currently, the solution to the second-order optimality of decentralized problem in deterministic setting has been proposed. Perturbed Decentralized Gradient Tracking (PDGT) (Tiioiis et al.) (2020)) a decentralized deterministic algorithm adopting the perturbed gradient descent strategy to achieve second-order stationary point. However, it is expensive to compute full gradients for large machine learning models. It is crucial to propose a stochastic algorithm to obtain second-order optimality for decentralized problems. Besides, there are some drawbacks of PDGT to make it less efficient and hard to be generalized to the stochastic setting. These drawbacks are also the key challenges to achieve second-order optimality for decentralized algorithms, which are listed as follows:
(1) PDGT runs fixed numbers of iterations in descent phase and escaping phase such that the phases of all nodes can be changed simultaneously. This strategy works because the descent is easy to be estimated in deterministic setting. Nonetheless, the exact descent of stochastic algorithm over fixed number of iterations is hard to be bounded because of randomness and noises. If the fixed number is not large enough it is possible that the averaged model parameter is not a first-order stationary point. If the fixed number is as large as the expected number of iterations to achieve first-order stationary point, the algorithm will become less efficient as it is probably stuck at a saddle point for a long time before drawing the perturbation, especially in the second and later descent phase. Specifically. applying fixed number of iterations in each phase results in the complexity of at least ((e-4.5) (see Appendix D), which is higher than Ö(c-3) of our method. Therefore, we are motivated to propose an algorithm that can change phases adaptively (based on runtime gradient norm) and independently (not required to consider status on other nodes or notify other nodes).
(2) In PDGT the perturbations on all nodes are drawn from the same random seed. Besides, a coordinating protocol involving broadcast and aggregation is used to compute the averaged model parameter and the descent of overall loss function discriminate the candidate point. These strategies together with the fixed number of iterations act as a hidden coordinator to make PDGT discriminate saddle point in the same way as centralized algorithms. However, when the number of worker nodes is large it is time-consuming to perform broadcast or aggregation over the whole decentralized network. Moreover, when generalized to stochastic setting the changing of phase is not guaranteed to be synchronized. Additionally, we will note in the Supplementary Material that the consensus error 1
n. --= (x]") ă, 2|2 is another factor to impact the effectiveness of perturbed gradient descent, which is not present in centralized problems. All above issues are theoretical difficulties to study and ensure second-orde optimality for decentralized stochastic algorithms.
(Vlaski and Sayed (2020) proves the theoretical guarantee of second-order optimality for decen- tralized stochastic algorithm with perturbed gradient descent. However, it does not provide non-asymptotic analysis to estimate the convergence rate or gradient complexity. The effectiveness of the result relies on sufficiently small learning rate, and it does not present specific algorithm. The analysis is based on the assumption that the iteration formula can be approximated by a centralized update scheme when the learning rate is small enough. Nevertheless, in practice is difficult to maintain an ideally small learning rate, and the iterative update process can be more complex as previously mentioned. To our best knowledge, the second-order optimality issue of decentralized stochastic algorithm with non-as asympttpii analysis is still not solved. Therefore, we are motivated to study this important and challenging issue and raise the following questions:
Can we design a decentralized stochastic optimization algorithm with non-asymptotic analysis to find local minima efficiently? Is the algorithm still effective discriminate saddle point even if each node can change its phase adaptively and independently without any coordinating protocols?
The answer is affirmative. In this paper, we propose novel gradient-based -ased algorithm named PErturbed DEcentralized STORM ALgorithm (PEDESTAL) which is the first decentralized stochastic algorithm to find second-order stationary point. We adopt perturbed gradient descent to ensure the second-order optimality and use STORM (Cutkosky and Orabona (2019) estimator to accelerate the convergence. We provide completed convergence analysis guarantee the theoretically. More details about the reason of choosing perturbed gradient descent and technical difficulties are discussed in Section 3.2. Next will introduce the problem setup in this paper.
optimality
2

---

We focus on the following decentralized optimization problem:
1 Σ f((x), =
min f(z)
(I)
where n is the number of worker nodes in the decentralized network and fi is the local loss function on i-th worker node. Here fi is supposed to take the form of stochastic expectation over local data distribution D, which covers a variety of optimization problems including finite-sum problem and online problem. Data distributions different nodes are allowed to be heterogeneous. The objective function f is nonconvex such that saddle points probably exist.
The goal of our method is to find O(e, e -second-order stationary point of problem D which defined by the point z satisfying [V](l S e and min eig( (xx) 2 -EH, where eig(-) represents the eigenvalues. The classic setting is Eи VE.
We summarize the contributions of this paper as follows:
We propose a novel algorithm PEDESTAL, which is the first decentralized stochastic gradient-based algorithm achieve second-order optimality with non-asymptotic analysis.
We provide new analysis framework to support changing phases adaptively and indepen- dently on each node without any coordinating protocols involving broadcast or aggregation. We also address certain technical difficulties unique to decentralized optimization to justify the effectiveness of perturbed gradient descent in discriminating saddle point.
We prove that our PEDESTAL achieves the gradient complexity of ÓE + 11) to find O(e, EØ >second-order stationary point. Particularly, PEDESTAL achieves the gradient complexity of Ö(c-3) in the classic setting Cи Vē, which matches sfate-of-thh-an art results of centralized counterparts or decentralized methods to find first-order stationary point.
2
Related Work
In this section we will introduce the background of related works. The comparison of important features is shown in Table I Here Ō() refers to the big O notation that hides the logarithmic terms.
2.1 Decentralized Algorithms for First-Order Optimality
Decentralized optimization is efficient framework to solve problem [ colaborativvy by multiple worker nodes. In each iteration a worker node only needs to communicate with its neighbors. One of the best-known decentralized stochastic algorithm is D-PSGD (Lian et al. (2077). which integrates average consensus with local stochastic gradient descent steps and shows competitive result to centralized SGD. The ability to address IID data limitation of D-PSGD and some variants of
D-PSGD are studied to tackle the data heterogeneity issue, such as D (Tang et al. (2018) by storing previous status and GT-DSGI (Xin al.) 2021b) by using gradient tracking (Xu et (2015).
Lorenzo and Scutari (2016). ). D-GET (Sun et al. (020 and D-SPIDER-STD
(Pan et al. [2020]
improve the gradient complexity of D-PSGD from Ole to Oc by utilizing variance reduced
gradient estimator SPIDER (Fang et al. 22018 8 ). GT-HSGD also achieves gradient complexity of
0 3) by combining gradient tracking and STORM gradient estimator (Cutkosky and Orabona 2019). ). SPIDER requires a large batchsize of Ole-1) on average and mega batchsize of O periodically. contrast, STORM only requires large batch in the first iteration. After that the batchsize can be as small as O(1, which makes STORM more efficient to be implemented in practice.
2.2 Centralized Algorithms for Second-Order Optimality
Perturbed gradient descent is a simple and effective method to escape saddle points and find local minima. PGD (Jin et al.] 2017]) the representative of this family of algorithms, which achieves second-order optimality in deterministic setting. It draws a perturbation when the gradient norm small. If this point is saddle point, the loss function value will decrease by a certain threshold within specified number of iterations (i.e., breaking the escaping phase) with high probability. Otherwise, the candidate point is regarded Perturbed SGD perturbs every iteration and suffers a high gradient complexity of O(E-5) to achieve O(e, vē (e))-))ooddoorrr stationary point and the gradient complexity hides a polynomial factor of dimension d. CNC-SGD requires Correlated Negative Curvature assumption and the gradient complexity of (5) to achieve the classic second-order optimality. SSRGD (Li 2019] adopts the
second-order stationary point. In stochastic setting,
3

---

Name
Averaged Batchsize
Gradient Complexity
Classic Setting
D-PSGD
12
0(1)
GT-DSGD
22
0(1)
0(c
D-GET 16
0(c-3)
D-SPIDER-SFO
15
0
(
GT-HSGD
0(1)
(
SGD+Neon2
0(1)
Ö(c + 4 22 CH 3
Ö(e
SCSG+Neon2
0
O 10/3 + cH +cH
Natasha2+Neon2
O((²)
-(26 + + +
0
SPIDER-SFO"
O(c-))
0(e +c 2 +CH) )
Perturbed SGD
0(1)
O(e 0(E++E#1 16)
0
CNC-SGD
0(1)
Ō +
0
SSRGD [|]
Ō(e +e 2c + + -
EH
Pullback 2
Ole +
0
PDGT [8]
Full
PEDESTAL-S (ours)
O(1)
Ō )) Eh 2 02 Ō(E 3 + EEH 8 + - 11
PEDESTAL (ours)
0(e-3/4)
Ō(E-))
Table I: The comparison of important properties between related algorithms and our PEDESTAL. Column "Averaged Batchsize" computed when εл = Ve. Column "Classic Setting" refers to the gradient complexity under the classic condition are decentralized methods achieving first-order optimality. The second group of algorithms are centralized methods achieving second-order optimality. The last group of algorithms are decentralized methods achieving second-order optimality. PEDESTAL-S is special case of PEDESTAL with ((1) batchsize. The complexity of PDGT is not shown because it is not stochastic.
Vē. The first group of algorithms
same two-phase scheme PGD but uses the moving distance as the criterion discriminate saddle point in escaping phase. It also takes advantage variance reduction to improve the gradient complexity to ((6)).).. Pullback (Chen et al. (2022) ) proposes a pullback step to further enhance the gradient complexity to Ö(e-3) which matches the best result of reaching first-order stationary point.
2.3 Stochastic Gradient Descent
branch of study of stochastic gradient descent argues that SGD can avoid saddle point under certain conditions. However, that is completely different from the problem we focus on. In this paper we propose method that can find local minima effectively for a general problem [ while escaping saddle point by stochastic gradient itself depends on some additional assumptions. For example, (Mertikopoulos al. 22200) requires the noise of gradient should be uniformly excited. According to our experimental result in Section 5 we can see in some cases stochastic gradient descent cannot escape saddle point effectively or efficiently. Besides, the gradient noise variance reduced methods is reduced in order to accelerate the convergence. Our experimental results indicate that the gradient noise variance reduced algorithms is as good as SGD to serve the perturbation to avoid saddle point. Therefore, is necessary to study the second-order stationary point for variance reduced algorithms so as enable both second-order optimality and fast convergence.
3 Method
3.1
Algorithm
In this section, we will introduce PEDESTAL algorithm, which is demonstrated in Algorithm Suppose there are n worker nodes in the decentralized communication network connected by weight matrix W. The initial value of model parameters all nodes are identical and equal to Zp. x( 02
(6) are the model parameter, gradient estimator and gradient tracker on the i-th worker node and y
(s) is the temporary model parameter that is awaiting communication. Ze, 6 and y in iteration i. #t
corresponding mean values over all nodes. Counter (fc counts the number of iterations in the

---

Algorithm Perturbed Decentralized STORM Algorithm (PEDESTAL)
Input: initial value "00 My, v0 0. b esc(1) 11
Parameter: bo. b1. 17, 3, r, Cv. Ca. Cr.
1: On i-th node:
2: for = 0, 1....,
T 1 do
3: if ( - 0 then
4:
Compute
(8) (F 5 with c6 -b-
5: else
6: Compute of = (= < (1 () VF (())) with 15 = b1.
7: end if
8: Communicate and update the gradient tracker: Vi (1)
Σド= Wisl (Ut-) + ot - - --1-
if escl)) -1 and lly; a - Cp then
9:
(+) (1) Draw a perturbation & ~~ Br(r) and update 2t It. +
10:
11: Save 2i as .5(0) and set esc! = 0.
12: else
13:
Update (+) = = - my (0)
(6)
14:
end if
Communicate and update the model parameter: zt+1 = Σ3= Wifzt (f) if esc 0 then
15:
17: Reset esc( = if ( z0 > Ca else update esc( = esc +
18: end if
19:
end for
Return: Tt-Cr there are at least n nodes satisfying escl 2 Cr.
16
current escaping phase on the i-th worker node, which is also the indicator of current phase. When runs the descent phase on the i-th worker node esc( set to -1; otherwise esc! 2 0.
In the first iteration, the gradient estimator is computed based on large batch size with bg. Be- ginning from the second iteration, the gradient estimator v, is calculated by small mini-batch of samples according to the update rule of STORM, which can be formulated by line 6 in Al-
gorithm 1 where B is hyperparameter of STORM algorithm. Notation V (x
()) <f() repre-
sents the stochastic gradient obtained from batch samples e((), which can be written as (x.
()) ((()) = (1/15(") Ezee!" (.(2()) .)).
After calculating ( each worker node communicates with neighbors and update the gradient tracker v1 Inspired by the framework of Perturbed Gradient Descent, our PEDESTAL method also consists of two phases, the descent phase and the escaping phase. If worker node is in the descent (8) phase and the norm l1vi || is smaller than the given threshold Ce, then it will draw perturbation & uniformly from (r(r) and update 2(() =t + E. The phase is switched to escaping phase and (sc is set to 0. Anchor (+)) (6) is saved and will be used to discriminate whether the escaping phase is broken. After this iteration counter (ic( will be added by 1 in each following iteration until the moving distance from the anchor i-th worker node (i.e., ||=?)") (;(00 []) is larger than threshold C2 for some I, which breaks the escaping phase and turn back to descent phase. If the condition of
drawing perturbation is not satisfied, 2(() is updated by (t) xz (t) (s) running currently.
my:" matter which phase is
If the i-th worker node's counter (s is larger than the threshold Cr, it indicates that or-Or is candidate second-order stationary point. When least a nodes satisfy the condition esc(1) Cr, the algorithm terminated. Notice that the fraction is set to for convenience the convergence analysis. Our algorithm also works for other constant fractions. From Algorithm we can see the decision of changing phases on each node only depends on its own status, which adaptive and independent. Coordinating protocol including broadcast or aggregation is not required.
TO
5

---

3.2 Discussion
Here we will discuss the insight of the algorithm design and compare the differences between our method and related works. Some novel improvements are the key to the questions in Section
3.2.1 Perturbed Gradient Descent or Negative Curvature Descent
Perturbed gradient descent and negative curvature descent are two of the most widely used pure first-order methods to find second-order stationary points. In PEDESTAL algorithm, we adopt the strategy of perturbed gradient descent rather than negative curvature descent because of the following reasons. First, negative curvature descent methods such as Neon (Xu et al. (2018) and Neon2 (Allen-Zhne and Li 2018)) involves a nested loop to execute the negative curvature subroutine to recognize if a first-order stationary point is local minimum. However, in decentralized setting, it is possible that the gradient norms on some nodes are smaller than the threshold while others are not. Therefore, some nodes will execute the negative curvature subroutine but its neighbors may not. In this case neighbor nodes need to wait for the nodes running negative curvature subroutines and there will be idle time neighbor nodes. Besides, the analysis of negative curvature descent methods rely on the precision of the negative curvature direction. It is unknown if the theoretical results are still effective when only fraction of nodes participate in the computation of negative curvature direction while the others use the gradient. In contrast, perturbed gradient descent only requires a simple operation of drawing perturbation, which is more suitable for decentralized algorithms.
3.2.2 Stepsize and Batchsize
In Pullback, a dynamic stepsize 7/: = /// uz|l in the descent phase where v = (c)) and 82 is the gradient estimator. This stepsize is originated from SPIDER (Fang et al. (2018) which ensures its convergence by bounding the update distance || 2x ll. In the escaping phase, Pullback adopts a larger stepsize of ((1) in the escaping phase and a special pullback stepsize in the last iteration, which is the key to improve the gradient complexity. Different from Pullback, in Algorithm we adopt a consistent stepsize such that it keeps invariant even if phase changes and all nodes always use the same stepsize. If there is no perturbation in iteration t, we have ē④41 = T. 170,, which is important to the convergence analysis. We discard the strategy in Pullback for two reasons. First, the gradient normalization will probably cause divergence issues in decentralized optimization because in centralized algorithm the gradient direction is ve/l/vell, which is equivalent to Ve = (i)
I
Ei=1" /Il Σ - " ||- However, in decentralized algorithm the average of
Ut is not available on
local nodes. If the gradient normalization is done locally, we will get Ud = En= == 0f /|lo II. which is different to U. and the error is hard to be estimated. Actually. both D-GET and D D-SPIDER-SFO adopt the constant stepsize in SpiderBoost (Wang et al.] (2019) to avoid performing the gradient normalization step. SPIDER needs the gradient normalization because || 25g || is required to be small in the proof, while SpiderBoost improves the proof to bound || - =ell by n / which is canceled eventually. In our analysis we also adopt the strategy in SpiderBoost. Second, in our algorithm the changing of phase is occurred independently on each node. The phase-wise stepsize and pullback strategy will lead to different stepsizes among all nodes one iteration, which will also cause potential convergence issues.
In (Cen et al. (022 D, two versions of Pullback are proposed, i.e., Dallback-SPIDERR and Pullback- STORM using SPIDER and STORM as the gradient estimator respectively. As introduced previously, one of the advantages of STORM is avoiding large batchsize. Nonetheless, Dallback-STORR, adopt large batchsize of Oc--)) in each iteration, which violates the original intention of STORM. Besides, from Table 1 we can see all algorithms achieving second-order optimality with Ö(E- gradient complexity require a large batchsize of O(E-1) Therefore, we propose a small batch version named PEDESTAL-S as a special case of PEDESTAL that only requires an averaged batchsize of O(1).
3.2.3 Conditions of Termination
As result of applying gradient tracking, we can bound E 1
5. 11 2 O(E2). Even though || is large Olv on some
we have such estimation, it is still possible that the norm (8) nodes when the entire decentralized network has already achieved optimality. Therefore, waiting for all nodes to reach second-order stationary point is not efficient strategy. This is the reason why terminate our algorithm when only a fraction of worker nodes satisfy (9) > Cr.

---

In SSRGD and Pullback, there is an upper bound of iteration numbers in the escaping phase. If the escaping phase is not broken in this number of iterations then the candidate point is regarded as a second-order stationary point. If the escaping phase is broken, then the averaged moving distance larger than a threshold and the loss function will be reduced by (c²2) on average. This strategy guarantees that the algorithm will terminate with a certain gradient complexity. However, in our algorithm worker nodes do not enter escaping phase simultaneously and thus we do not set such an upper bound. In this case the averaged moving distance cannot be lower bounded as CT has no upper bound. Fortunately, we can complete our analysis by a different novel framework (see the proof outline in the Appendix). An alternative solution is to stop the update the node that has run certain number of iterations in the escaping phase while the algorithm will continue. But that solution is also challenging since the relation between the acst-achieved local optimal solution and the final global optimal solution is unknown and the analysis is non-trivial.
One remaining issue of the current termination strategy is that it involves the global knowledge of how many worker nodes satisfying the termination condition. One solution is to run an additional process to track this global value. The cost of transmitting Boolean values is much less expensive than broadcasting the model. Another solution is to set a maximum iteration in practice. Generally we need to evaluate the model after certain epochs to see if the training process is running smoothly and we can save a checkpoint when we find a better evaluation result. The theoretical analysis ensures that optimal solution can be visited if the number of iterations is as large O(e ").
3.2.4 Small Stuck Region
The theoretical guarantee of second-order optimality in SSRGD and Pullback is mainly credit to the lemma of small stuck region, which states that if there are two decoupled sequences x, and at with identical stochastic samples, I. = x' and rs+1 - r'211 = tuo where e₁ is the eigenvector corresponding to the smallest eigenvalue, then it satisfies max [|2: - zall. || ='Il]} 2 Ca for SSRGD and Pullback, the averaged moving distance 7-8 E# || - x+1 is used as the criterion to discriminate saddle point because the small stuck region lemma can be applied in this way. However, in decentralized algorithm some nodes enter the escaping phase before the candidate point ã, is achieved. Suppose node i enters escaping phase in iteration s', then the averaged moving distance starting from iteration s on node cannot be well estimated because the condition of not breaking escaping phase on node only guarantees the bound of averaged moving distance starting from s'. Therefore, in our method we use the total
some s S S s + Cr with high probability.
moving distance ||xr)" xx² || as the criterion because we can obtain estimation ||=?)"" - x || S 2Ca given ||o 2//1 S C2 and || - S Ca. And we can further complete our analysis by the small stuck region lemma. Actually we do not require more memory because I is the point to return in SSRGD and Pullback (hence should be saved). In practice, we can also return ((()) for any node i drawing perturbation in iteration t - CT since ||=;)) (1) æz ll can be well bounded. Besides, we discover that the consensus error 1 E || 1 results in an extra term when proving the small stuck region lemma, which becomes another challenge. If the consensus error is not under control, it can drive æ away from F, or push x toward x., no matter what fzx is. In this manner, the stuck region cannot be estimated. In this work, we provide the corresponding proof to estimate this new term exclusively occurred in decentralized setting in our convergence analysis.
4
Convergence Analysis
4.1
Assumptions
In this section we will provide the main theorem of our convergence analysis. First we will introduce the assumptions used in this paper. All assumptions used in this paper are mild and commonly used in the analysis of related works.
Assumption 1. (Lower Bound) The objective f is lower bounded, i.e., inf f(x)= = -00.
Assumption 2. (Bounded Variance) The stochastic gradient of each local loss function is an unbiased estimator and has bounded variance, i.e.. any i E {1, 2, .,,.,,,,, ,n) we have
Es VF( -Vf(x), E& (z, (f((z))l>s
(2)
7

---

Et has Lipschitz gradient, Assumption 3. (Lipschitz Gradient) For all Ç and E {1,2, [1,2,...n1) .n], i.e,, for any 21 and 22 we have [[V Assumption 4. (Lipschitz Hessian) For all ε and i E [1, 2, ... .n.. Fx {) has Lipschitz hessian, i.e., for any I1 and 22 we have f - ( 9ll S |||aa] x2 with a constant p.
(22( E)]l - - I2l with constant L.
Assumption Assumption 2 and Assumption 3 are common assumptions used in the analysis of stochastic optimization algorithms. Assumption 4 is the standard assumption to find second-orde optimality, which is used all algorithms that achieves second- -odder stationary point in Table [
Assumption 5. (Spectral Gap) The decentralized network is connected by doubly-stochastic weight matrix W E TRax satisfying W W 1,, and À = I[ Jíl [0, 1).
Here J a network where Waj > O if node and node are connected. otherwise wa = 0. spectral norm of matrix (i.e., largest singular value). Notice that À is a connectivity measurement of the network graph and it is also the second largest singular value of W. We do not assume W to be symmetric and hence the communication network can be both directed graph and undirected graph. The spectral gap assumption is also used commonly in the analysis of decentralized algorithms.
matrix with all elements equal 1. W is the weight matrix of the decentralized
n
denotes the
4.2 Main Theorems
Let eι c². When S 0.5, we have the following Theorem !
Theorem 1. Assume a S 0.5 and Assumption 1 to 5 are satisfied. Let 0 min 3-5a
1}. We ser
2 ((c bn O) d1 (0max((2-6-50 11}, O(c2+0), C, O(c),
7 (. C = Oe aa)) and Ca = ((c Then our PEDESTAL algorthn will achieve O secoo-- order stationary point with Ō(e-3) gradient complexity.
The specific constants hidden in (()) will be shown in Appendix B where the proof outline and the completed proof of Theorem can also be found. From Theorem we can our PEDESTAL-S
with 6 (1) can achieve O(e, e -ecc---dd---dde stationary point with Ö(E-)) gradient complexity
for ен 2 e 0.2 In the classic setting, our PEDESTAL achieves second-order stationary point with Ō(-3)) gradient complexity. When a > 0.5, i.e., en < Vē, we have the following Theorem 2 Since the parameter settings are different and the O(1) batchsize is only available in Theorem we separate these two theorems. The proof of Theorem 2 can be found in Appendix D
Theorem 2. When EH < VE (i.e., a > 0.5), we set = Ô(c"), B = ((2 by = 1) by = Ō 11-x
F == O(c(+0), Co O(c). Cr = P(- and C= = Ô(())
where 0 = min 3a 3a 2}. Under Assumption 7 Too our PEDESTAL algorithm will achieve
O(e, < -scennd-order stationary point with ÖcE + E
11) gradient complexity.
Experiments
In this section we will demonstrate our experimental results validate the performance of our method. We conduct two tasks in our experiment, a matrix sensing task on synthetic dataset and matrix factorization task on real-world dataset. Both of these two tasks are non-spurious local minimum problems (Ge et al. 2017 2016)). which means all local minima are global minima. Thus, conclude algorithm is stuck at saddle point if the loss function value does not achieve the com/WH- WH- XIAN/PEDESAAL
global minimum. The source code is available in https:: //t::/gittt //ggtttttb..////////////t com
5.1 Matrix Sensing
We follow the experimental setup of (Chen et al. [202]] 1) to solve a decentralized matrix sensing problem. The goal of this task to recover low-rank where U E dR for some small We set the number of worker nodes synthetic dataset with N sensing matrices {A, and N corresponding observations by = (Ai, M*). Here the inner product (X, Y) of two matrices X and Y is defined by the trace tr(XTy) The decentralized optimization problem can be formulated by
d symmetric matrix M (U-)
20. We generate
1 N;
min U VERAXT
LU,,,, where L.(U)
Σ
(AAG, - bb,)
(3)
2
8

---

D-SPEMED-O SED
DESOO
(a) d 50, ring
(b) d 50, toroidal
(c) d = 50, exponential
D75GD
DuPOEEE CT Fieco
TESHRSTAL
(d) d = 100, ring
(c) d 100, toroidal
(f) d = 100, exponential
Figure 1: Experimental results of the decentralized matrix sensing task on different network topology
for d = 50 and d 100. Data is assigned to worker nodes by random distribution. The y-axis is the loss function value and the x-axis the number of gradient oracles divided by the number of data N.
D GET
(a) ring, random
toroidal, random
(c) exponential, random
D25CO
2054D
BACE ZEBESTAL
Teate: Orudo
Sentorr of Dbocae
Seater of Ubccs
(d) ring, Dirichlet
(e) toroidal, Dirichlet
(f) exponential, Dirichlet
Figure 2: Experimental results of the decentralized matrix factorization task different network topology on MovieLens- 100k. The y-axis is the loss function value and the x-axis is the number of gradient oracles divided by the size of matrix N x I.
where N, the amount of data assigned worker node i.
The number rows of matrix is set to d = 50 and d = 100 respectively and the number of columns is set to r 3. The ground truth low-rank matrix M equals (**!" where each entry of U" is generated by Gaussian distribution. A (0, 1/d) independently. We randomly generate N 20 x n x samples of sensing matrices {At).r A; E d from standard Gaussian distribution and calculate the corresponding labels b; (A,, M*). We consider two different types of data distribution, random distribution and Dirichlet distribution Dir (0.3) to assign data to each worker node. We conduct experiments three different types of network topology, i.e., ring topology, toroidal

---

topology (2-dimensional ring) and undirected exponential graph. The initial value of U is set to [uo. 0, 0] where uo yield from Gaussian distribution and multiplied by a scalar such that it satisfies |uo|| < max eäg( ). We compare our PEDESTAL algorithm to decentralized baselines including D-PSGD, GTDSGD, D-GET, D-SPIDER-SFO and GTHSGD. this experiment, the learning rate is chosen from (0.01, 0.001, 0.0001). The batchsize is set to 10. For PEDESTAL and GTHSGD, parameter is set to 0.01. For D-GET and D-SPIDER-SEE threshold C, is set to 0.0001. Perturbation radius is set to 0.001. The threshold of moving distance Ca is set to 0.01. The experimental results are shown in Figure T Due to the space limit, we only show the result of random data distribution in the main manuscript and leave the result of Dirichlet distribution to Appendix A
the period q is 100. For PEDESTAL,
From the experimental result we can see all baselines are stuck at the saddle point and cannot escape effectively. contrast, our PEDESTAL reaches and escapes saddle points and finally find the local minimum. We also calculate the smallest eigenvalue of hessian matrix for each algorithm at the converged optimal point, which left to the Supplementary Material because of space limit. According to the eigenvalue result, we can see the smallest eigenvalue is much closer to 0 than all baselines. Therefore, our experiment verifies that our PEDESTAL achieves the best performance to escape saddle point and find local minimum.
5.2 Matrix Factorization
The second task in our experiment is matrix factorization, which aims to approximate a given matrix M E R xl by a low-rank matrix that can be decomposed to the product of two matrices U e R Nxr and V R!xx" for some small r. The optimization problem can be formulated by
N >E (M, (UV)
min UERN X Vealer
M - UV 1
(4)
where ||- denotes the Frobenius norm and subscript ij refers the element i-th row and j-th column. In our experiment we solve this problem on the Moviel 100k dataset (Harper and Konstan ). MovieLens-100g contains 100,000 ratings of 1682 movies provided by 943 users. Each rating is in the interval [0, 5] and scaled to [0, 1] in the experiment. This task can be regarded as an association task to predict users' potential ratings for unseen movies. In our experiment we set the number of worker node to n = 50. Each node is assigned the data from different group of users. Similar the matrix sensing task, here we also use random distribution and Dirichlet distribution respectively to distribute users to worker nodes. And we also use ring topology, toroidal topology and undirected exponential graph as the communication network. The baselines are also D-PSGD, GTDSGD, D-GET, D-SPIDER-SFO and GTHSGD, In this experiment, the number of worker nodes 50 and the rank of the matrix M is set to 25. The learning rate is chosen from (0.01, 0.001, 0.0001}. ). The batchsize is set to 100. For PEDESTAL and GTHSGD, parameter / is set to 0.1. For D-GET and D-SPIDER-SS SFO, the period & is 100. For PEDESTAL, threshold C, is set to 0.002. Perturbation radius is set to 0.01. The threshold of moving distance Ca is set to 0.5. The experimental results are shown in Figure 2
From the experimental results we can see our PEDESTAL achieves the best performance to escape saddle point and find second-order stationary point. All baselines cannot escape saddle point effectively or efficiently. Particularly, variance reduced methods D-GET and D-SPIDER-SFE shows worse performance than SGD based algorithms D-PSGD and GTDSGD, which indicates that although reducing gradient noise can accelerate convergence, it also weakens the ability to escape saddle point. Therefore, our contribution is important since we make the fast convergence of variance reduction compatible with the capability to avoid saddle point.
6 Conclusion
In this paper we propose a novel algorithm PEDESTAL to find local minima in nonconvex decentral- ized optimization. PEDESTAL is the first decentralized stochastic algorithm achieve second-order optimality with non-asymptotic analysis. We improve the drawbacks in previous deterministic counterpart make phase changed independently on each node and avoid consensus protocols of broadcast or aggregation. We prove that PEDESTAL can achieve O(c, -econd-oodrrrd stationary point with the gradient complexity of Ô(e-3), which matches state-of-the-art results of centralized counterpart or decentralized method to find first-order stationary point. We also conduct the matrix sensing and matrix factorization tasks in experiments to validate the performance of PEDESTAL.
10

---

References
Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. Advances in Neural Information Processing Systems, 31, 2018.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Faster perturbed stochastic gradient methods for finding local minima. In Sanjoy Dasgupta and Nika Haghtalab, editors, Proceedings of The 33rd International Conference Algorithmic Learning Theory, volume 167 of Proceedings of Machine Learning Research, pages 704..04.77 PMLR, 29 Mar-01 Apr 2022.
Ashok Cutkosky and Francesco Orabona. Momentum- baseed variance reduction in non-convex sgd. Neural Information Processing Systems (NeurIPS), 2019.
Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th Interna- tional Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1155-1164, 10-15 Jul 2018.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic
differential estimator. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bisachia and R. Garnett, editors, Advances in Neural Infor- mation Processing Systems, volume 31. Curran Associates, Inc., 2018
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedingy of Machine Learning Research, pages 797-842, Paris, France, 03-06 Jul 2015. PMLR.
Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. D. Lee, M. Sugiyama, U. Luxburg. I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR, 2017.
F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis, 5(4):1-19, 2015.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1733 PMLR, 2017.
Zhize Li. Ssrgd: Simple stochastic recursive gradient descent for escaping saddle points. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bun Buc, E. Fox, and R. Gareett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Paolo Di Lorenzo and Gesualdo Scutari. Next:
In-network nonconvex optimization. JEEE Transactions on Signal and Information Processing over Networks, 2(2): 136, 2016. doi: 10. 10.1109/SSIPN..01.222222
Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, and Volkan Cevher. On the almost sure con- vergence of stochastic gradient descent in non-convex problems. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 1117-1128. Curran Associates, Inc., 2020.

---

Taoxing Pan. Jun Liu, and Jie Wang. D-spider-sfo: A decentralized optimization algorithm with faster convergence rate for nonconvex problems. Proceedings of the AAAI Conference on Artificial Intelligence, 34(00))1619-1663)
Apr. 2020. doi: 10. 10.16609aai.v.4ii v34.02.5523.
Haoran Sun, Songtao Lu, and Mingyi Hong. Improving the sample and communication complexity for decentralized non-convex optimization: Joint gradient estimation and tracking. Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9217-9228, PMLR, 13-18 Jul 2020.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Liu. de: Decentralized training over decen- tralized data. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4848-4856. PMLR, 10-15 Jul 2018.
Isidoros Tziotis, Constantine Caramanis, and Aryan Mokhtari. Second order optimality in decen- tralized non-convex optimization via perturbed gradient tracking. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21162-21111 173. Curran Associates, Inc., 2020.
Stefan Vlaski and Ali H Sayed. Second-order guarantees in centralized, federated and decentralized nonconvex optimization. arXiv preprint arXiv:2003.14366 2020.
Zhe Wang. Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Ran Xin, Usman Khan, and Soummya Kar. A hybrid variance-reduced method for decentralized stochastic non-convex optimization. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11459-11469 PMLR, 18-24 Jul 2021a.
Ran Xin, Usman A. Khan, and Soummya Kar. An improved convergence analysis for decentralized online stochastic non-convex optimization. IEEE Transactions Signal Processing, 19:16699 1842- 1858, 2021b. doi: 10.11099TSPP22213322555.2
Jinming Xu, Shanying Zhu, Yeng Chai Soh, and Lihua Xie. Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes. In 2015 54th IEEE Conference on Decision and Control (CDC), pages 2055-2060, 2015. doi: N0.10000DCC2011..700225
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.
12

---

A Additional Experimental Results
The experimental results of Dirichlet distribution of the matrix sensing task is shown in Figure 3 smallest eigenvalue at the converged point for each algorithm is shown Table 2 and Table
The
DUDEE
SHECG
(a) 50, ring
50, toroidal
(c) exponential
IDURT SHSCCE PEDESTAL
SC2 DUAC AEO
DCDDGG TELESTAL
(d) d 100, ring
(c) d 100, toroidal
(f) d 100, exponential
Figure 3: Experimental results of the decentralized matrix sensing task on different network topology
for d 50 and d 100. Data is assigned to worker nodes by Dirichlet distribution. The y-axis is the loss function value and the x-axis the number of gradient oracles divided by the number data N.
D-PSGD
GTDSGD D-GET
D-SPIDER-SED
GTHSGD
PEDESTAL
d 50, ring
-0.0332
-0.0327
-0.0333
-0.0328
-0.0329
-1.88
d 50, toroidal
-0.0331
-0.0334
-0.0334
-0.0327
-0.0329
-4.18c
d = 50, exponential
-0.0323
-0.0330
-0.0331
-0,0332
-0.0333
-1.09e
100, ring
-0.0184
-0.0184
-0.0184
-0.0184
-0.0185
-2.07e
d 100, toroidal
-0.0185
-0.0186
-0.0185
-0.0184
-0.0184
-2.25e
d 100, exponential
-0.0184
-0.0184
-0.0186
-0.0184
-0.0184
-3.07e
Table 2: Smallest eigenvalue of hessian matrix at the converged point (random data distribution).
D-PSGD
GTDSGD D-GET
D-SPIDER-SFO
GTHSGD
PEDESTAL
d = 50, ring
-0.0332
-0.0337
-0.0332
-0.0325
-0.0330
-3.60e
= 50, toroidal
-0.0334
-0.0324
-0.0329
-0.0325
-0.0327
-2.29e 55
d 50, exponential
-0.0334
-0.0326
-0.0333
-0.0330
-0.0328
-3.97e
100, ring
-0.0184
-0.0184
-0.0184
-0.0185
-0.0183
-4.88e
d = 100, toroidal
-0.0184
-0.0184
-0.0184
-0.0184
-0.0185
-1.24e
100, exponential
-0.0186
-0.0185
-0.0186
-0.0183
-0.0185
-3.33
Table Smallest eigenvalue hessian matrix at the converged point (Dirichlet data distribution).
B Proof of Theorem 1
B.1 Notation
define matrix X, [o| ... x (")] E dkd where xi is the model parameter on i-th worker
node with dimension d and n is the number of worker nodes. Similarly we have Y; [v." (1)
(x))
*.* .3.
13

---

2, [-()
(x)
and V [of
) Let wi = 1 -z and Q = Ze X Define
2t
Pt = nt/n n where ne is the number of worker nodes drawing perturbation iteration t.
B.2 Outline
In this section we will provide the proof outline of Theorem I] First, we prove some basic lemmas to estimate gradient noise and consensus error, which will be used frequently later proof. The gradient noise is estimated by Lemma [ the proof of which can be found in Section C.1 estimated by Lemma 2
The consensus error
the proof of which can be found in Section C.2
Lemma 1. (Gradient Noise) Under Assumption 2 and Assumption 3 we have
16 16log(4/0)80
384 (84lo/(4/8)L
(a)
1x Xell?
nT
b1
nb
192 log 4/0)L2
T-1
2log(4/0)o*
we + Σ
b,3T
BboT
1
T
n
16 1olo(446))3o
384 log (84l0g(4/8)
T
(b)
7 ΣΣ t=1
160
Vi(( )
|| - Xel1
nb
b1,3
192 log (4/0))
2log(4/0)0²
+
nbi8TT
n1BboT
t=
Lemma 2. (Consensus Error) Let 7 S
(1 B
21-x
CTT and bi 2 11e-
1+0
where
C 2 is a constant. Under Assumption 33 Bland
3and
we have
T
160000m 160000nlog(488)333 (o04 T-1
log( 1 2
(a)
|x xe11 <
wi
A14 min bainnbr (b,3. 1|TT
(1-1)ab1
2000n (0g(4/)))2220
12
T-1 64n 64 + +2
(1 -1 AbnT
(1- 3j37
--))27
1
1 T-1
4644 1644log(4 (o444/8)))/) 441))L22X X2
384 log(4/0)n\X300
(b)
- Σ
|Y - Voll 5 (1 A) min (b, 1)T
We
(1-
1=
50 log m42
8X2
150000
+r²)
(1-A) T)
(1 AYT
(1 (1- (-i))mminbba (b, 1|T
Next we will prove that PEDESTAL will terminate in certain number of iterations. Under Assumption
and 5 can prove the following Lemma 3 The proof is demonstrated in Section
Lemma 3. (Descent) Let S
21
cl+8, bi 2 11e-1+8 and by C2c
where
600 log L
G 2 is constant. Under Assumption 2 and 5 we have
f(rr) < f(x))
a²
1
T-1 vf((z))11
Σ De
L nL
where
(1 2)2
200 (1-A)cc
7pr(r + 12)
(1)
7
(7)
D. 167 We +
xe+1
22
256n7
2n
4n
Here we call D, the descent of iteration t. We categorize all iterations into three types:
type-A: pı 2 5'
type-B: pt < and
1
Σ
1
12
4C²
type-C: otherwise
5
im1
14

---

When at least ". nodes drawing perturbation in iteration t, then it is type-A. There are two cases where Pt small: most nodes the descent phase or most nodes in the escaping phase. An iteration 4Ct
is type-B if pt < $ and Ei= llv/ |2 N 5 which represents the case where most nodes are in the descent phase. And type-C iteration represents the case where most nodes are in the escaping phase. Next will estimate type-A and type-C iteration with the following Lemma 4
Lemma 4. Let v GOO 1og(7/00))
(1-1)²-"
CT bi Cie bo Cie Ca C2nCre,
C.
[1-A]Css and S. C where Ci = [1-X]=C2
20000 and C2 a constant. Under Assumption
200
5 we can find disjoint intervals In U... U.k such that the indexes of all type-A and rype- C iterations except the last CT iterations are contained in I and the descent over I can be estimated by
D (1- C1
10000
FEI
where| . denotes the total number of the set.
Besides, for all type-B iteration t, we have the following estimation
Lemma 5. Let parameter and assumption settings be the same as Lemma
then for all rype-B
iteration t we have
D, > (1- 1)
8000000
With Lemma Lemma 5 and Assumption we can conclude that PEDESTAL will terminate in Ö(e-2-0) Cr iterations. As the last two negative terms in D, are canceled by - ||=||]
(0) and 1/ Em= 11 1| respectively in Lemma 4 and Lemma we have 1
(1)
TT-1 w/ S 0(1. 7 2t=
Hence by Lemma 2 we know the consensus error Xr X.l f can be bounded by O(el+)) on
average. Besides, from the parameter setting we can see C, is ( which ensures the first-order optimality of the decentralized algorithm.
Finally, we will prove PEDESTAL is able to achieve second-order stationary point. First, will give the small stuck region lemma in decentralized setting. Recall that e = is the tolerance of second-order stationary point. The proof is in Section C.6
Lemma 6.
(Small Stuck Region) Suppose ns worker nodes draw perturbation in iteration and (1-X)22
= min mineig( (Vg(VV (V))(E)) S -CH- Let 1 S 1000 logl(T log(116)x+L 8 = - 12+0 1+0
bj Z
1000C1 2-0 50x C. = C2nCrre and Cr = Oog(12nCa/ro)/O0)
where C1 = 20000
C2 S
(1-X)=O²'
2000 log 1g8)1 log((.) and μ = max [1, 20.. Let X, and X; be two coupled decentralized sequences (6)
1-A
by running PEDESTAL from X, with X, = X², .li = xs41 if node i does not draw perturbation (1)' in iteration s and 4+11 x+11 + roes otherwise. Here es is the eigenvector with respect to the
smallest eigenvalue Define d; = max.grs+tor A1aa! x 22 ||: 20 [1}. Then there are at 9n nodes such that d: 2 2Ca-
least 10
In decentralized small stuck region lemma, the consensus error will lead to a new term (see Eq. and make the proof more complicated. In our proof, For smaller си the batchsize by is required to set larger. With Lemma 6 we can prove that when PEDESTAL is terminated, finds local minimum with high probability.
34
the condition of cH c, iee,
Lemma 7. Let Tn = 88 / where d the dimension of model parameter. Other parameters are the same as Lemma [ Suppose PEDESTAL is terminated in ileration Cr. Then 3. a second-order stationary point with probability at least 1 - ó.
Lemma 7 provides the guarantee of second-order optimality of PEDESTAL. When 6n 2 Ve, Lee. S 0.5 (including the classic setting н = Vt), the parameter settings of all lemmas are consistent and the main theorem is proven. The total gradient complexity is
Ō(E 2200 -1+0 Ō
15

---

When a = 0.5. we have 0 0.25 and b1 = (c 0.75 When a I 0.2, we can set 0 = 1 and (1). which is result of PEDESTAL-S. In Section D we will provide the analysis of the case 0.5 with a different parameter setting of 0 and b₁. We can achieve the gradient complexity of
Ō(E -3 + Een + t 11
(5)
over all cases of éx-
C Proof of Lemmas
C.1 Proof of Lemma
Proof. According to the definition of v/ we have
(6) v.(((
1 [((( 3(VF. (1) (10)
(1 - B) ((VF(EL+1:144) v((((((11)
- 8)
(1-
(V (41 - (VF((a)) e v
(6)
B)
where 15(41 b₁- The expectation of the right side of Eq.
(()) 6 over 5441 is O. Using Schwar-Schwarzz
inequality, Assumption and Assumption 3 we have
B(VF (1 V (1(222))
(VR((221 - Vfi(2 (V 10 .5) Vf((o,)) ))
(1 3)++1
(1 3)
2/3002
(1) 81 1|
- -x,111/
[+]
(1- 8)2122
(1 3)
for each j E 6-
Thus, applying Hauma-Hoeffding inequality to Eq.
6
we can obtain
||0 - ()(( (1 (1-))((m6)) ([r()))
4 4log(4/0) (230² + SL > - 3)) ()) |1 x0.0113
1-1
(8)
b1
==0
with probability 1- Here we use the fact that Σt (1 - 3)* = #/- Using Cauchy-Schwartz
inequality to Eq. ( we have
100 (a( 11 S 16 16lo((40))
1-1
(8)
(3o² + 41. Σ (1 -) 1|
||0 (1)
b
+1(1 - 21)))1)2111 1116 V.((=)))|1
(9)
Sum Eq.
9
we obtain
10 ( {=
1og(4/8)mT
t=0
16,00
64L
T-
[|++1 - Xx13 20²
61
nb,
3T
BBOT
1630²
384L2
T-1
||X,- - X, 1
1921
T-1
Σ W.
+
20²
(10)
b
BT
b,3T
3b6T
1=0
which finishes the proof of (a) in Lemmal [ In the first inequality of Eq. (10) we apply Azuma-
Hoeffding inequality to u V((())). In the second inequality we apply
inequality
and use the fact 2 2t (1) (#++1 F(t1) (x Fz)) (Ø++1 Ft.). Mimic above steps and
(t)
(i)
we can achieve the inequality (b) in Lemma [ The term n in the denominator derived by the fact
that ( 's different nodes are independent.
16

---

C.2 Proof of Lemma 2
Proof. As Y1, + -Ve-))) we have
| - -V11?
-I(W -J)(Y-1 11-1) + -W JJ( (IVV-VV-11) -VV--vV--- V--1)11
s - 2((W - -J)Y, (W- - - (V-V)) + Vi-1lp
++1²
[|Y 11 22 x*
1- x2 11V; -. -V--112
2
1 1 X2
3A² + x²)
n
||||_1 Y 113
(11g) (6) v(((=("))1 + +1 V/i(z
2
X
262 (1 + X²)
(IIX,-X, - x.113 - || 11 + niw--1
(11)
1 1 X2
where the first inequality is derived by Assumption S the second inequality is derived by Young's s incquality and the last incquality is derived by Schwwrt- inequality and Assumption 3 t = 0, by Azuma-Hoeffiee inequality we can get
When
[7((())) 8log(4/6)A2202
\ - -ool S 2X²
(12)
bu
with probability 5. As X = W(X, S22), by Assumption 5
and Young's 's inequality we have
|
Xt+1 17
1+ X2
2X²
||x, - -Xell +
152 - 12
2
1- X2
1 1+
41 X2
4)2
1X: X.I1e
1 V.l13
1- X2 110 - Q2 -n( 8i)1
2
1- x2
1 1+ X X2
47
8nX pr +2)
[X - 1
1- x2 |Y, v.1
(13)
2
1-
where the second inequality is obtained by Cauchy-Schwand inequality and the last inequality is because when node i draws perturbation it must satisfy ||v| (0) || < C.. Note that Xo = Xo. Sum Eq. we have
T
|x
X2I
8172
T-1
(17 + TT
<
| - 11
(1 X2)2
(1 X2)2
1=0
288 28 X1 + 1
96 X2)
T-1
| x111
(3) vf((o! !|
(1-
(1-
t=U
1=0 i=1
144m12n + X2)
T-1
1622,2
16n pu (12 + r2)
(1-
Σ
w
+
(1 12)3
1o 1o122
(1
(14)
where the last inequality comes from Eq.
11 When -
(1-2)²
403=f. we have
28812,,2>(1+433
< 1 and
(1-x2)+
2
X X
1921)2 X2)
Σ n
288nL3))22(11+ + X2)
(
Σ Wt
x2 t= i=1
X1-17
17

---

64 2
256 1oglog( (4/0)) 0²0
T-1
32m 2i +
+ (1 (1- 12)3T
V Vf((zo)1?+ +
1-123360T
(1 (1- -1227
t=
73728 log (4 + 2²)
T-1
24576n logg(//))()))) (4/6)) + X2)
T-1
|1,; - Xell?
Σ
(1 (1-12)4b1,7
(1- 3T
t=0
1=
n logg(4/5)) (00(4)))) + +2)00 3072,
384
288nL21 + X2)
(1 (1-17)4
+
3b0T
(1 (1- 1374T
Wi
1=0
77
256 log 1p
T-1 32m 32m (1 C. +
+ (1 - 22)3T
Σ [f((())]?
(15)
(1 ---2)0b0JT
(1-
where the last inequality is achieved by Lemmal | According to the parameter setting, we have 73728 log((/)))))))) 4/ x+11))111111 + 2²)
1 2
Therefore, we have
Σ Xr Xel13
160000n log( 4/6) X4
T-1
12288n log (4/45)/3n1222 x02
2000n 1o04
Σ We +
+
(1 (1- (1-A)² m-n 13T
- --)bbb
(1 - 3b
128
61 +2
+ (1 X 2=1
(()oo))
(16)
(1- 1)2T
where we have used the condition X _ to simplify the inequality. Moreover, sum Eq. 11 and we can achieve
T
Σ
|
T
1=0
12X²
T-1
36L2X² T-1 (1 A)T
||x, 1x11 + 18n T-1
< (1- XyT
11 - -
Σ
(1 - X)T
1=0 i=1
1=
t=0
2
+
1/
(1 X)T
361.2 X2
128 1og(4/6))
T-1
+ 18n1,22
128 (4/(4
(1 +
Σ
|| - -x11
(1
We
(1 -1-A)T
(1 A)T
6
1=0
192 log( (40
25 25
412
n
[10021)
(1- X-)1
(1- 2)
(1 X)T
(6444og(4/8)T4)
T-1
2322 log log(4/8)m T-1
Σ
|| - X.113 + (1- A)min(b 3, 1\T
Σ
We
(1 (1- A) m)ninbb 1|T
1=0
t=
192 log (op2lo))))m Bo²
25 (40044/)m2220
4X2
n
[x)o)11
(1 X)b1
(1 - 2))3ho
(1 XyT
(7152log(4/8)12) X
T-1
||: -Y.1? + 2322 log (4/8)mI222 T-1
Σ Wt
(1 - 1-30)1nmmm min(b,,, 1|T
(1- A) min! ( //,,,117
1=
192 192 (40)) 2302
1 (1 - A)3 min BIT
+ 2
25 2
+
(1 (1-1)b
(1 - --)
412 n
+ (1 - X)T
\((())))
(17)
1=1
18

---

where the second inequality uses Lemma D 37152 1o/(4//)/444 A (1-A) min bb p.1}
and Eq. (12).
The last inequality uses the sum of Eq.
13
As
S 2. we have
T Σ
|r, -.113
1644log(4/00) (4/5)LL2>2
T-1
384 log(4/0)))2 30log(4/0)XX0
Wt +
1) min 3. 1,TT
(1-
(1 (1- 1)33bb
8A2
150000 log 4
Vf(az))]
(18)
(1 XyT
(1 - 2)5 3,,
which finishes the proof.
C.3 Proof of Lemma
Proof. By Assumption
we have
L
1(f++1) S f(1,) + (V.( T441 - zx)) +
| - Fell2
2
= f(()) + (V.((..). -76;) + (V Tz+1 - It + mpoe) + L
Ti+1 - 2111
2
= f((a)) " ||//1| " 1 [x+)(( 11² + 2
00 - v((+))1 + " (V (3:))1
2
2
1
1
+ 2n
|7 - 3e + +,ppel' 1|
|,+11 - 5e + 1pūp [ + 2 || - Tell?
21
S f(x) 1116 + " |0:
vf(xt)11 +
1
|ل1 3z + nool1 2 + Lare
2n
2
1
Wi
" 0/
(a.),)] +
1
wi
+ ,/|l²= - (
2m
4n
S fāx) W1
|| +
2 + +2²
+
Lait
+ 2n
fz(((()) 11
4n 2
7
2
+ L'
XX, X,112
(19)
where the first inequality is obtained by Young's inequality and the last inequality is obtained by SchwartS inequality, Assumption 3 and the fact that perturbation only drawn when and apply Lemma
llv [0] < C, and ne nodes draw perturbation in iteration t. Sum Eq. (19) have
we
[(Tr) S ((10)
4n
T-1
Σ
Wi
n
2
Σ
T-1
6o 2
768 log log 4/0) + (1 +
nb,8 3
L' T-1
1x,
Xe112
1=0
pr(n7 C2 CZ++²) +2)
32 log (4/8)
384 log (o
1
(1+
Lur
"
nbi
nb13 3
t=
1=
4 log 4/0)no2
(20)
n,3bg
According to the update of gradient tracker, we have Dt = Ut. By Lemma 10 we have
zt. (1)
we + n
1 [[x+1 Xe+1) -xx, X.)
(21)
1
lly
|| 2 + I Y/11?
(22)
19

---

Divide the term
|Tell in Eq.
(0 into three portions and we get
f(TT)
$ f10)
1 T-1
Σ We
(1 - 2)²
Σ w
1 T-1
Σ
13ell + +1+
768 log (4/6)
L211
Σ
T-1
| X
8n
2567
2
nby
72
T-1
prl +2))
32 log( (16))/////// 2
384 (84loH(4//) L4)
Alog (4/))
+
+
+ (1 +
Lui- +
nb
nb1,3
n13bo
$ f(0)
817
1 T-1
Σ
We
(1=
2561
T-1
2n
11
T-1 n Σ
1
2n
1/
Σ
T-1
| -Vlli.
1-0
t=0
t=0
T-1
C2 +r²)
768 log (4/6)
L211
T-1
32 log 3,/0)
+
+ (1
||
Xel3
7
nb18
n
nbi
3841og(4/0)Ln
T-1
4 4log( logg(4/))70²
+(1+ +
Taue +
nb1,3
n13bo
S {((0))
1
(1- 2)
| 41
It
12
71
n
llv! 1/
81
256me0
2n
+ +(14 +
768 (og(/)))
(1-
La11
T-1
|x x.1
+
17
T-1
| - Vdl
rub18
12
2n ==0
1=0
384 log 384/0
T-1
T-1
Pcl C + )
32 log Ong 2²
4 4log(4/6))p
+ +11
Leos
nb183
"
nbi
n13b0
1=0
t=
S <((o))
T-1
Lun-
(1
2)2
T-1
10411 x1 10
17
T-
11
8L11 1=0
256mn
2n
1=0 1=1
Tono²
As 70?
(e C. +r²)
+ +1
Las + A2 bi
A
" +
As
V {
(23)
3bo
n
In the second inequality we use Eq. (2)) inequality. In the last inequality we use Lemma and the coefficients are
In the third inequality we use Eq.
21 and Cauchy-Schwartz
384 Log(4/6)L
+1++ 768 (4/()
+ (1 A)² 160000 (og(4 ,2 774log(4/8)Lnb
A1 1+
nb189
mbi ,
1287.2172 (1 A)4 min (b 8, 1} (1 - A)2 12288 log (4/8))2,,2x*
(1-
32 log(4/0)
+ (1 + 768 1og(4/6)
64log(4/8)4²
A2 =
n
nb18
128
(1-
(1 (1-))
4 log(4/0)
(1 + 768 log(4/))
(1- x)²
2000 log(//(44))) XM
10log(4/6)2
43
+
n
nbi /
12
(1 A)4
(1 X)
A4 (1 + 768 1o/(4/8)
(1 x)2
6=, 25000 log (4/6)
nb1/
128T.2n
(1 (1-122
2)3
768 (o/6
(1 2)2
128X*
21²
As = (1 +
+ 1
128T,2y2
(1 - --3
According to the parameter setting, we have A E Tohn A2 <
200 logi//4/)) [I-X²²
Ag 5
401gg(4/8)
(1-
A4 S I and As I T.x. Therefore, we have
S(TT) S f(x0) +
40 40log(4/))n0²
+ (1 A)m
5n
Σ
[V
- Σ Dr
T-1
(1 2)2,8bg
1=1
1=
< <((2)) + 0² 1
T-1
Σ D.
(24)
nI.
where
D. 160
1 (1
wi
256mm
2 n
(9)
(5)
+
2n
77
11 (4) 2
(1 - P)
200me20a
Tpe(n C +r2)
41
(25)
which reaches the conclusion.
20

---

C.4 Proof of Lemma 4
Proof. For convenience, the iteration that draws perturbation considered to be included in the escaping phase. If an iteration belongs to type-A, i.e., pt 2 5. then at least n/55 worker nodes are in the escaping phase. If an iteration belongs to type-C, we have E 10 < 5.
AC2
Therefore, there are at least h worker nodes satisfying |1y (1) S C.. which also indicates that at least worker nodes are in the escaping phase. Then if iteration is either type-A type-C, there must be n/5 worker nodes in the escaping phase. We denote the set of these n1/5 worker nodes as & Furthermore, not one of the last CT iterations before termination, then there must exist n/ worker nodes out of & such that they have not met the condition esc( N CT and will break the escaping phase before meeting the condition because of the termination criterion in Algorithm | We use B, to denote these worker nodes.
if this iteration
For each E B,, we have an interval (a.") 6,,"] such that E la b. and node i enters escaping phase in iteration di and breaks escaping phase in iteration (()) Besides, we also have
(9) Cr and (|x( 800
x 11120 Ca a.
Then by Cauchy-Schwards inequality we have
C S ||x (1) 6.
- x 1 12 S C,
(8)
Enago
|aft)
2i 100
(26)
Let a; = min ( and 6 max, {bg J. It easy to check that by - at S 2OT. Next, we will perform the refining step. If' t < t' are two iterations that are either type-A or type-C and t' E [at, br]. then we make or a, and by = b.. Let I U,la,, be] for all type-A and type-C iterations t. Then
(1)
I can be written as disjoint union of
I= I=ZUZu...UU
(27)
because if a, S or S. by then (at, by] and lae, br] can be merged into one interval. Now we can see for each iteration t that is either type-A or type-C and t is not one of the last Cr iterations, we have t E Z. Next we will estimate the descent over I. Without loss of generality, we consider an interval Iy. I, can be expressed by union Jn U.. J, where Jm [at... b,m. for some tm m 1..... .L. Because of the refining step, we have each i. is only included in interval Im and the intersection of any three intervals in J1, ... , D. According Eq. (26) we have
1
(0) 10 o 10112 Z
C2
(28)
10CT
IE
since |B.l 2 To. Next, we will consider the intersection of Im and Jm+1- Notice that when estimating Eq. (88 we only add the terms [ xx 10 on nodes i E B.., and in the intervals 1a (. Therefore, for any node i & Br,,, n B...... the terms used to estimate Eq. (28) will not (i) be added repeatedly. If Bin. BLm+1 we have | ((4 and [0 b are disjoint because tm+1 E [a. the escaping phase. Hence we can sum Eq. 188h over m and achieve
1 b(() but tm+1 & [a."). [(01 and a node cannot draw perturbation before breaking
1C3 xt 10 Z 10Cr
ΣΣ i= TET,
(29)
Since the length of each Im is not larger than 2Cr, we have
2
122
[C and n 1=1 FET
ΣΣ
- 24
10 22
[
(30)
20C2
20C2
1= TE
Combining Eq. 30 and Lemma 3 we can estimate the descent over by
(1
x)CC2
20
7(n²C3 + +r²)
(1 - X)2O
(1-x)
Σ D. 2
[
(31)
5120n
(1-
C)
4n
10000
TET
according to the parameter setting.
21

---

C.5 Proof of Lemma 5
Proof. According Lemma B
and the definition of type-B iteration, we have
200rp²
7r
200m
(1 - 2)
Dj
(32)
20
201
40
(1 AJ
8000000
for all type-B BB iteration & where we have used the parameter setting.
C.6 Proof of Lemma
Proof. Suppose the conclusion is not true and we will find the conflict. Thus, have the assumption that there are at least a worker nodes satisfying d, S 2Ca. First, we define 10
(2)) Wi = Et E,, H f(..), H ('f((E), - -'F (
w
n n
1
(1 (60) -
. -
(1 (V ( (1))))11111)) (F (F(CEL):))))
14 == Vf((.) - (V-()()) - St
and
A.
(V2 (V2S(T) + 0(T. - k()) H)dd
A (V + 0(z, - z() - )00
Then have
Wt= = W1-1 1 - 1( 1)
= Wi-11 - ((Vff(t - Vf + U2- (f( - 1/11 + vs(
Wh-1 - 1 E/-1) / V2 V2f(E'11 + -1 + 11-1 + G6-1
= (T - -/H)w:11 17( 1
1 + 1/-1 + (1-1)
(33)
Here term Ç is yield from consensus error and does not exist in centralized algorithms. Applying recursion to Eq. 33 we can obtain
1-1
W = - -I-)) Wo+1 n
Σ
+ +u + (+)
(34)
7=8-1
Let q: = 17 - (I 1710/- (A w
A + Vr + (r). We will prove
11:11 S ! (1 + 177)² 17))
1
------1-- Paro
(35)
2
which leads to
3 (1 1-01 p.ro - well S 2 (1+ + (-) P
(36)
because (1) w.. = (1+ paro according the definition of W.+ We define
d = max [1|2, -1, 1. 11 =111 )l Since at least a nodes satisfy d, S 2Ca. Ca Ō 1-))aa)
and the averaged consensus error is bounded by ((2((++)) we have
1 Σ
d, < 3Ca and d
d; S 3Cd
(37)
i=1
22

---

To achieve Eq.
35 it is sufficient to prove
7
(1 + m)) I1, wer 11
||r||| + +|k+l| - (1 177)===11p1) Paro
(38)
4lo((4/8) (1 +
177
| s
(1 + 171) Psro
(39)
b1
s-s s
12
LiPorr + Ln(1 + my) Lpsro
||slll < 8
(1 + 177) -- ( Paro (40)
2
Vb
12yOT
which can be derived by induction. When + 1, the left side of Eq. (38 is 0 and thus the
inequality is satisfied. Suppose Eq. (38) holds for S tg. When f to + 1. we have
(1+m)* | A+
3
2 nod
Σ (1 ( paro S 5mpC.Cr(11 - Paro
Tma+1
1 + 17) P.ro
(41)
6
where we use Assumption and the case of t S to in the first two incqualities. We use the parameter setting of Ca in the last inequality. Next, we will estimate the terms related to vt- By Azuma-Hoeffding inequality we know Eq. 39 is satisfied when t = + 1. We define
Et, (V (6)
(1-
vf((t)
<,₁ (VF( (1 vf((((+1) - (1 (V V
Then according the definition of v4 we have
V/+1 = (1 (1-11)11) B)vz
6.. - 4,)
1 Σ
B) Σ
(E, tn,))
(42)
1=1
T=S
1=1
Define
A F1 -Z) -1,00 )d0
411
AM / (V'P.TT 0 ".-1),=.") H1 )00
y00
AM / (( 00' +0(x))
1 ) (0)) )- 7 da
01)
10 = / (V ( + 0 - 1 2 100)000
08
(43)
Then we have
Er - é
-H w1+1 + A 141,1 We+1 - (10 we+1 A u1+1 + (1 (1- (0) wr + ((ww))
(1)
-(1 - (11-))(H(1) 111771100 w. + (1) (
-HH - H) (w - (1- B)w)) + (A 111.1 - A (0) 1 + +1- (1- (00 1 (44)
According to Assumption 3 and Assumption we have
||et,e ا6,1 < 2L| wzll + (28L + 3pCa) + 3pCaalaautt w
(45)
23

---

Applying Azuma Nouma-Hoeffding inequality to Eq. 42
with Eq. 45 we can obtain
4 1l0g(4/8)
|u/112 v
- u.rl (2 + 3pCa)] w-ll + 3pCa|luo++1ll]
nbi
48 log (4/0)
Σ (L21 - +l-1++5a1 w 1??
(46)
nbi
T=s+1
since B is ( and Ca is ( According to Eq. 34p. we have
L|| W1
T-2
-11--1H((1 -1HH) ---1)-5-33 -ws+1
11+1 1)
Σ
n/H(T 2 + Uyr + (ri)
r'=411
+ 1 + 1 + +---1)ll
Poro + LaT
S L + - 22r0
(1 + 177) (7-7))=-33 P&TO + Ln) 11 + 14-1 + Gr-1ll
2
22 + - p.ro + Lnl 1, + + G--1l
(47)
In the first inequality, the first term is derived by the definition of W.+1. The second term is derived by the supposition that Eq. (38) holds for & S to and the fact that Eq. 338 implies
Σ
(1+
| + Gol S 2 (1+m))=++
Paro
(48)
T=8+1
Combining Eq.
446 and Eq.
we have
48 18gg(4//))
||, 11 <
[I' w. wy-1l1 5p C3
nb1
270
192 log (4g((4/))
(1+ (1+m))((---))p11)) +
(1+ m)) 2))
mbim
nbi
t-2 (6log(4/8) +
| W + + + 2
nb
r=s+1
300 300 (og( (1 177)) 2(( 1::0 192 log (4/8)))) m7!
+ 11+ 22t---11
nbimy
ndi
4 10 mb
5000 log 2 (4/8) L11
f-2
(1 + 1777 (1 ((T
(1 + m7) 2((-
P310
bi
5)2
7=
800 2 T.2 m
(1 + 77)
2(
p3
(1 + 17) 21 (
28
nb
s in
5000 log 2 (4/8)L417'2?)
177 2(7-0-11
( 8)2
T=s+1
10000 1))
(1 + 2(1--11 11
+ 177) 2(1-8-1)) p3r0
6//2
s)-
14
(1 + my) 2(1-0-1) 1)
1222208
+
(1 + 177) 2(-=)(=--)
(49)
s)-
C4
The exponential term in Eq. 440 can be addressed by the following strategy. When t 2 Ō 2, the term can be dominated by other terms such as . When t < Ō(1-x)))))))) it can be bounded by
L L2n log((/0)) 4/0))
< L2 5)² log 1og(4/6)p3r3
(50)
n11 A)bi
(1 2)bi (1 =s)²
24

---

The term f in the numerator will be bounded by 1) in this case and hence it can be merged to the first term Eq. (39). In the third inequality of Eq. (49). we split the last term into two parts: La
Ln and T - S Lyy Since f,+ de = t. we can merge the case 7 -- s > buy into the a²
T --8 8 > bIT
byT"
second term and estimate the rest one where T - is small. According to the choice of 0, we have
b1 2 0(2
and ,²C90
b1 < {1)) and hence get the estimation in Eq. (49). We should notice
that we use the relation
2 S ((1) in our proof, which is automatically satisfied. By Eq. (49) we
b17
can reach the conclusion in Eq. 339. Furthermore, we have
Σ (1 + (1+77)--111 |+1|| 1=9+1
"
1
< Lm((1 + -17))=--1ppp parol
Σ
(1 + m77) ( Psro
12
Tms+1
1 12 (1 (1+m) psro S 6 (1 m7)) s-1
< Lmylog(Cr) + (7)))11+))))))) Paro +
'prro
paro
(51)
The last step to prove Eq. (38 is to estimate the term corresponding to St which is new term only occurred in decentralized algorithms. Recall the definitions in Eq. (43) we have
Ge
+ Σ (HL Au( (H4 + A u (1- (B)
+ 10)00 -A150 + A )(1))
1
H [11)
(5)
(1) -w)) -(1 (w (4) W 13] Σ
(2) 1.1
(wf -w+)
1=1
1=1
1
(6) 1,1
10: 1 B (10 (8) w 1 3
Σ ( ( w (52)
n
Then by Assumption 3 Assumption
Eq. (37b. Lemma 10 and Gauuch-SSchwand inequality, we
have
4L2 1|Gel1 1
n (I|X, - 8,-(xx; x21 + |X, - -X,-1-X;-1133
+ +144 (1 12 112)
(53)
It is sufficient to prove
vn Il X. - (X- X,I1r S 2(
L
1 + X2
)-22 I./Paro +
1 481/Cr (1 + (-07 psro
2
Lmy(1 + 1/))t Lparo
(54)
4vbi(1 - 8)
because of Eq. (53) and the parameter setting. Eq. (54)
can also be proven by induction. When
t t= + 1 the condition is satisfied. Next we will estimate - (X/ -1)1 By Assumption
5 and Young's 's incquality we have
||
X,- - -XX- - X
IIW - -]]((X,11- - -2-11-
- (X,=1 - X/-1)) - 7 - Y--1- - (Y/_) - 1)11
1+
21,²X²
||x-1 -8,1- - -XXi1 X(11)11++ + 1 X2
| - P1- - -Y-1-11-1 - -
2
2²
Σ
(-1
)r ----- (+X22)
1 1+ X2
||,, - 8, - -Y- 9
1 - X²
2
T=$+1
+ 1 ++X* X2
y j--s-1
|| x+1 8s11 (X'4 X
2
2n12 2
[-1
1 + 2
1 + X2
Σ
| Y, -Y- AD +
1 - n, n.rp (55)
1
2
7=
25

---

where we apply recursion in the second inequality and use the definition of the decoupled sequences in the last equality. Similarly, by recursion we also have
1| Yx- - -OY- -1311
14
12
A + A 1 x2
|| -,-1- -8,1 - +
1 -V-V - -VV -V-
2
21
t
1
< 1-
Σ
2 I V+-1 (V? - V 11
(56)
+=
Combining above two inequalities, we achieve
||x - X1 (X-
21
Σ
1-1
+ X2
)t- +)l1, V.-1 -VV -V,-VV V1-1)1
(1 2)2 1=x+1
2
X2
+ ( 2
2m - -n.)p.r
(57)
According to the update rule of ( we have
- 6
1 - (v) 60) - - - (1 B)( - 2 - (v 10'
= -VP(
- -V (1 (10) - VF( 00' 151 (4 + (1-3)) (1))
- -IVR (10) - (1 BV- (2,) - (1 (
(1- 0'' ((
(58)
Then mimic the estimation of 1/2 we can obtain
VV= V - (V₁ 12
32 (4/)
(-1 n
Σ
22 1 (9) 7+1 - w || + (2 + 3pCa)llu(111 + 3pCall |II
bi
T=8 1=1
n
n Ww 101
+ 4L2
(8) 112 + 36p C2
(59)
Combining above inequalities and the parameter setting of B, we can obtain
1 |X, - R, -x-xx)11 1 1+
-- X2-10
2
2000 log log (4/0)
72n² p222
Σ
[-1
1+X
(t
n 7)
1 11
(1 (1-1)=b
(1
2)2
2
7=6+1
1=1
+
500 log(4 (og(4/8)L3)p(1- - s)X*
++X
x2
(1 - T)
1
(7)
w 1
(1-2)ab
(1- (1-))2
2
n
1000log(4//0 - 5)
1-1
X
(L
(32 +
|| XX, X, - -XX, - -X,11
(1 x)
2
7
r=s+1
2000 (4/(6))m²² p20 8)X²
+ 72n p² C22x
t-1
1+X2 1-- - -)] (--00--
(1 (1-))²b
(1 X)2
7=
500 log( (1/8)))),, s)X*
+ 81
Σ
1+ x2
1
) (t T) w|w, - -wr-1ll
(60)
(1-))ab.
(1 x)2
2
x=x41
Using Eq.
(36), Eq.
47 and Eq.
54
we have
1
X X.
(X/ -
n
26

---

I (- y-- 1 L'pwri + BB((1 + (=)
1 12
Σ
(1 + (2 + m7)
) )-- (1 7)
2
2
r=++1
+ B3 + 177) 2)) L2
Σ
(1 (1+13)1++
1 t- 7
2
(7 7-88 8)2
7=
1 + X2
+
)( p.0
(61)
2
where
1/
2000 log( 4/8)(1
00) )
172 500 log (4/6));2)p(
812,12
B1 = (1 - x)2
(32 +
bj
(1-))ab
(1- 2)2
125 log (4/0)(t ) ))) + 4500 log (4/6)1/ -
162
B2 72(1 - C)2
(2+
b
2)2b1
(1-
1
500 log 4/6) -t
8L2r)²
+ (8 54T.212
+
6C7
(1 21
(1 - X)2
48 logg(4/)))
500 (ogg(40))))))) (t 5) + (1 A)2
8L217
B3
bn
(1 2)2b1
/11 ((t))()-11)))
2000 log (og(4/))(t -s)
(1- 1)2b1 (32 +
(62)
bj
If 2 Ó 0,,2))1 (1
) y--e-1 is small and the first term of Eq. (61) can be merged to the second
term. Otherwise if < 0 ( it can be merged to the last term according to the parameter setting
3+X² Hence the second term of Eq. 61 can be bounded by Lemma 8 The third term of Eq. (61) can be estimated by Lemma (the case of t < Ō Ō(1=)) can be addressed by the parameter setting of 17 and b2). Therefore, we can prove
of 17 and bz. When is small, we have (1+)2)(1+m)²
n 1,2 || - X. - (X) X S 4( 1 X2
X2 1 ) L'p + 2304 (1 + m)) p3r0
L 13 + +,,))(1------1))p)0
(63)
16b (1 x)2
because of the parameter setting. We should notice that here we also use the relation which is always satisfied according to the setting of bj. Based on Eq. (53) and Eq. 663 check that Çe satisfies Eq. (40). Moreover, we have
< O())
0
it is easy to
1-1
Σ (1 + + r=s+1
"
1-1
4 4+ 22
t-1
< Lm((1 +
(8
Σ
p-8-1+
Σ
)
12 (1 --
psro
5
T
+=
+=
80
1
< LTy( 1-X + log (C)) + +7) Psro
+
(1 + (1+m)) -- psro
12
< $ (1+ p5ro psro
(64)
where the first inequality is derived by
1 2
3 X+ and (3 + X²) + m7)
4+
(65)
2
4
5
Now combining Eq. the proof of the induction. Recall the assumption the beginning, we have
41
Eq. 51) and Eq. 64). we can reach the conclusion in Eq. 38 and finish
1 (1 + psro $ wer S 2d s 6C
(66)
2
27

---

since | z,1l
- [ -Bell + | - T-l1- Eq. 66) implies that
(og(12Ca/(Pero))
2 2log(12nCa//m)
Cr
v log(1 + +m7)
(67)
7/7
which conflicts with the definition Cr. Therefore, the proof of Lemma 6 is finished.
C.7 Proof of Lemma
Proof. If node i enters the escaping phase in iteration s' before iteration and does not break it in iteration s- Cr, then for t S s+Cr, we have | -z!" S
||x] -x
|| -x,²1 2Ca-
Therefore, there are at least n worker nodes satisfying max.ges*+ | I (a) S 2Ca-
10
Suppose min eig f(g(V) < -Eи and e₁ is the corresponding eigenvector. Let S; denote the region of the perturbation on node i that PEDESTAL will terminate in iteration + Cr, i.e. To workers will not break the escaping phase. Then by Lemma 6 we can conclude that there must exist one worker node such that the projection of S; onto direction e₁ is smaller than ro- Since the perturbation & is drawn from uniform distribution, the probability of & E S; can be bounded by
Pr(Ei E S.) S ToV 1,r)) 8
(68)
V(Ball
where V-) denotes the volume and Ball(d, r) denotes the d-dimensional ball with radius r. The last inequality is achieved by the definition of ro- Therefore, we can prove that T. is second-order stationary point with probability at least ò.
D Additional Theoretical Result
In this section we will provide some additional theoretical result of our PEDESTAL algorithm. First we will demonstrate the convergence analysis of the case Eµ Ve, i.e., a 0.5. Next, will discuss the strategy of using fixed number of iterations in each descent and escaping phase, which motivates the design of PEDESTAL.
D.1 Smaller Tolerance for Second-Ordes Optimality
When efr < VE, the conclusions of previous Lemmas are still satisfied except Lemma 4 In this case, Ca Con/Cree where 2x > 1. Parameter Ca should be smaller than the original setting in Lemmalg 4 which results in more iterations to converge. Fortunately, the analysis of Lemma can be adjusted and can achieve Theorem 2 The proof is provided as follows.
Proof. The fourth term of Dr in Lemma 3 is derived by nßo?
"1 and at this time we will set bj 2
e (2)-1-6) that the term is replaced by eft. The last term of Dj be written
Cp +r²)
7(n + r²)
Σ
(69)
4m
n
4nj
(1.)EP
where P is the set of all pairs of (t, such that node draws perturbation in iteration t. We can divide P into two parts. P1 contains all pairs of (t, such that node breaks the escaping phase within M iterations, where M is integer to be decided later. The rest part is denoted by P2.
For any (t, i) E P1. suppose node breaks escaping phase iteration m, where m S M. Then node i will never draw perturbation between iteration & and iteration t + M. Mimic the steps of Eq. (6).. by Cauchy-Schwart inequality we can obtain
Σ 4+m
C2 M
(0
(70)
Let M = 22-26+20 Then we have
- A)2
7(7²0² + +22) -00
11
(1)
-
200
(71)
512n)
4nj
r=t
28

---

and
(1 2) 512mm
12 1 E
7 +2²)
(72)
4nj
(t.1)E71
by the parameter setting of C... On the other hand, if (t, E P2, then node will not break the escaping phase in M steps and hence the perturbation step will not execute, either. Therefore, we have estimation
1
Σ
7 +r²
7(m C +2²)
(73)
n
4n
4M
(L.))Ep2
t=0
With Eq.
72). Eq. (73) and the new setting of bi. the descent in Lemma 3 can be improved to
D. = 16n Wi + (1 2)²
200
7(1 C2 +9)
Σ
| 2+1
12
10
llue (
512mm
2n 1=1
(1 X)CC
4M
1=1
When 2 3a - 2, we have
37
2
S 2M and Lemma
still holds but the conclusion is changed to
(1
C)
D
10000
EEI
In this case, PEDESTAL algooritm will terminate in Ö(E iterations. In Lemma 6 and Lemma we need the relations
PCC 0(1),
7
S 0()
(74)
b
bICH
which implies b, 2 ((c-aa)) Therefore, set d Ō (0-x((x1---1.84oo) with the condition 0 2 30 2. When a I 1, we set f
3a which satisfies 2 30 2 and
2
5a
4a - -=
(75)
2
The gradient complexity in this case is
Ō درلد ha-t Ö
(8a11)
(76)
When a > 1, we have 3a - 2 and bj = (1a-2)). The gradient complexity is
e ( (1a-2)) =
(77)
which finishes the proof of Theorem
Therefore, the gradient complexity over all cases can by written by
Ō(c-3 + ec 8 + AcHll)
(78)
D.2 Phases with Fixed Number Iterations
If a decentralized stochastic perturbed gradient descent method adopt the strategy of fixed number of iterations in each phase, the gradient complexity the descent phase should be at least O( to ensure the first-order stationary point. But the total descent of a descent phase could be small because it is possible that is stuck at a saddle point after only a few steps. Hence we need to consider the descent in the escaping phase. According to Lemma and Lemma 4 we can the
descent of an escaping phase O C. As the conditions 11C,Cr S ((1) and Cr Ō ((1م) are required in Lemma 6 we can obtain that the total descent of an escaping phase is no larger than Ō In the classic setting of éн = Ve, the total descent of an escaping is upper bounded by (c...)) Consequently, the total gradient complexity to achieve (c, -ocooddoo-rr stationary point is at least Ō(E-1.5), which is worse than the result of our PEDESTAL.
29

---

E
Auxiliary Lemmas
Lemma 8. Let 1. Then we have
1 1 a²
ta¹
Σ Ta --
(1 a)²
Lemma 9. Let < When 0 (Ta)) we have
Ta Ta 7-1
8
t++1- 7)2
8 a)²
Proof. When 2. by Lemma
we have
Ta=-1
Σ
S
(79)
(t+ 1 T)2 t² a)²
S1/22
When 7 > 1. we have
Σ TDf/2
Ta
Σ Ta- S 5/2/2(
t 1
(80)
(1+1-7)
2(1 a)
(1 - a)
T5//2
Therefore, we can reach the conclusion when t 2 Ō (
Lemma 10. (Definition of Variance) For any random variable X, we have
E[X EX]² EX² (EX)²
Lemma 11. (Lemma D.I in (Chen et al. 1202 Let e1.h E Rd be a vector-valued martingale difference sequence with respect to Fi. i.e., for each k E [K], [[] 0 and [|ex|] & Bg, then with probability
ō we have
K Σ A=
clll < 4log(4/6)
B
(81)
k=1
30


Reviews:
[{"review_id": "k7bVpTByoH", "reviewer": "Reviewer_tsG4", "summary": "This work proposes PEDESTAL, the first decentralized algorithm for the stochastic non-convex optimization framework that escapes saddle points efficiently. Theoretical guarantees are provided indicating that PEDESTAL finds second order stationary points in $\\tilde{\\mathcal{O}} (\\epsilon^{-3} + \\epsilon_H^{-5})$. In the classical setting where $\\epsilon_H = \\sqrt{\\epsilon}$ this translates to $\\tilde{\\mathcal{O}$ which matches the state of the art results for finding a first order stationary point. To achieve this aforementioned result the authors utilize perturbed gradient decent (from the centralized regime) and STORM to accelerate convergence. Importantly, the ideas of perturbed gradient descent (i.e. the injection of noise followed by a phase that verifies whether a second order stationary point is reached) are utilized in a distributed manner thus improving from prior work and requiring no coordination between the nodes. Additionally, numerical results on matrix sensing and matrix factorization tasks are provided supporting the theoretical findings.", "questions": "See the weaknesses section.", "limitations": "The authors adequately addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is $\\textbf{very well written}$ and easy to follow for the most part (more details on this in the weaknesses section.)\n\n- This paper studies an $\\textbf{interesting problem}$ in the field of non-convex stochastic optimization i.e. finding efficiently second order stationary points in a decentralized manner. \n\n- $\\textbf{Novel techniques}$. The paper combines ideas from prior works (perturbed gradient descent, perturbed gradient tracking, STORM estimator) in a non-trivial manner. The theoretical contribution is significant since the authors utilize ideas of perturbed gradient descent in a decentralized manner without the need for any coordination among the participating nodes. I believe that this is a novel and interesting technique that can be used by more decentralized methods in the future to escape efficiently from saddles.\n\n- $\\textbf{Impactful results}$. The resulting algorithm and analysis are impactful deriving the first decentralized algorithm for the stochastic non-convex optimization framework that escapes saddle points efficiently with convergence guarantee $\\tilde{\\mathcal{O}$; this is indeed a competitive rate matching the best known rates for finding first order stationary points.\n\n- $\\textbf{Numerical results}$ that support the theoretical findings are provided showcasing that PEDESTAL efficiently escapes saddle points. ", "weaknesses": "- Although the paper has very nice structure and is well-written, I believe that the presentation of $\\textbf{section $3.2.4$ could be improved}$. Arguably one of the most interesting ideas of this work is the implementation of the descent and escape phases in a fully distributed fashion without the need for any coordination. I believe that conveying the intuition of how this is achieved in PEDESTAL is of crucial importance that needs to be emphasized. Although, the authors have attempted to do that in section $3.2.4$ I think that this part of the text should be revised explaining the underlining ideas more clearly and in more detail. Similarly, very little intuition or discussion has been for the proof of the important Lemma $6$ in the appendix.\n\n- I would like the authors to clarify how the algorithm terminates i.e. how the clients know that $n/10$ of them satisfy the $\\textbf{termination condition}$.\n\n- The bound provided in Theorem $1$ holds for a $\\textbf{specific range of}$   $\\boldsymbol{\\alpha \\leq 0.5}$. Although it is true that $\\alpha =0.5$ covers the most important (classic) setting, this limitation should be clearly stated in the main body of the paper (a footnote could suffice).\n\n- Typos: \nLine 170 \"REDESTAL\" change to \"PEDESTAL\".\nLine 171 change \"two phase\" to \"two phases\".\nLine 204 \"In Pullback...as SPIDER\" needs rephrasing.\nLine 214 \"If the...is used\" needs rephrasing.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the recognition of the contribution of our work and will address you concerns as follows.\n1. Thank you for your suggestion. We will add more details to convey the intuition of Section 3.2.4 and Lemma 6 more clearly. We will add a figure to show the relations of moving distances, the challenge and our solution.\n2. We have two strategies to implement the termination condition in practice. The first one is to run a separated process to obtain the number of nodes satisfying the stopping condition at the same time of gradient calculation, communication and evaluation since transmitting bool value is relatively less expensive. The second solution is to set up the number of iterations in advance. The model is evaluated after certain number of iterations such that we can check if the training process is running properly and plot figures based on these results. If the evaluated model achieves the current best result, we will save this checkpoint. Our theorem guarantees that the optimal solution must be visited if the number of iterations is $O(\\epsilon^{-3})$.\n3. Thank you for the suggestion. We will add a note of the range of $\\alpha$ in Theorem 1. In the appendix, we provide another Theorem 2 that proves the case of $\\alpha > 0.5$ using different parameter settings. In our final version, we will put both Theorem 1 and 2 in the main manuscript.\n4. Thank you for pointing out the grammar errors and typos in our paper. We will revise and polish the language in our final version."}, {"review_id": "8kRj32yZzq", "reviewer": "Reviewer_eGsh", "summary": "This paper proposed a gradient-based decentralized stochastic algorithm in decentralized optimization. The second-order optimality is proved with non-asymptotic analysis. ", "questions": "I have some concerns on the numerical studies part. In the tasks studied, the performance proposed method seems to be too strong as compared to other baselines. All methods except the proposed one stuck at the saddle point. Maybe the author can consider some common machine learning jobs like image classification and do some comparsions. ", "limitations": "See questions.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and easy to follow. The mathematical proof seems rigorous.", "weaknesses": "The numerical studies can be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and suggestion and we will address your concerns. In this paper the two experiments we conducted are both non-spurious local minimum problems according to [1] and [2], which means all local minima are global minima. Therefore, we can conclude when an algorithm is stuck at saddle point by comparing the loss function value and thus evaluate the capability to escape saddle points. Otherwise, in some general problems such as image classification we cannot distinguish a saddle point or a bad local minimum.\n\n[1] No spurious local minima in nonconvex low rank problems: A unified geometric analysis, ICML 2017\n\n[2] Matrix completion has no spurious local minimum, NeurIPS 2016"}, {"review_id": "LuCHYIAH97", "reviewer": "Reviewer_D1UK", "summary": "This paper proposes PEDESTAL, decentralized optimization algorithm that can find second-order stationary points efficiently, and provides extensive numerical experiments to support theoretical analysis. PEDESTAL outperforms other existing decentralized second-order algorithms as it requires a smaller batch size and less iterations to converge.", "questions": "I have a question about numerical experiments. Are all ", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed algorithm is simple but has a stronger performance guarantee than existing algorithms. The proof requires only standard assumptions.\n2. In addition to having superior convergence guarantees, the proposed algorithm outperforms other algorithms in numerical experiments.", "weaknesses": "1. The stopping criteria requires global synchronization. Even though this algorithm only requires to send an integer over the network, it is still required to sync every iteration to decided whether to stop.\n2. Rates don't include the eigen gap. I suggest the authors to explicitly show this terms, which gives us a better idea of the algorithm's efficiency.\n3. Notations are not clearly defined in the paper. I was not able to find the definition of $\\tilde O(\\cdot)$.\n4. Some minor typesetting flaws. Page 7 line 276 - 279, should be $x_1$ instead of $x1$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the recognition of our contribution and we will address you concerns as follows.\n1. To avoid synchronization, an alternative solution of the termination condition is to set an upper bound of the number of iterations. We can evaluate the training model at certain frequency and save the status if it achieves the best result so far. The theoretical analysis guarantees that the optimal solution will be visited, though the algorithm probably does not stop at this point.\n2. According to current proof, the iteration complexity on eigen gap is $O(\\frac{1}{(1 - \\lambda)^2})$ and the total complexity on eigen gap is $O(\\frac{1}{(1 - \\lambda)^4})$. However, in our work we focus on the second-order optimality of decentralized optimization and hence some unnecessary relaxations on eigen gap are probably applied because of simplicity. Therefore, this result can probably be improved and we will work on it to add it in our final version.\n3. Thank you for pointing out missing definitions and typos. In our final version we will introduce all notations used in this paper at the end of Section 1. We will also revise our paper to correct typos and grammar mistakes."}, {"review_id": "UUroLcSG89", "reviewer": "Reviewer_aGCa", "summary": "This paper presents a novel decentralized algorithm for escaping saddle points for non-convex problems. The authors focus primarily on the second-order optimality. Specifically, they propose a gradient-based stochastic optimization algorithm PEDESTAL with a novel convergence analysis framework. They provide the theoretical guarantees with the best available gradient complexity to achieve the second-order stationary point. To validate the proposed algorithm, the authors present two empirical results with the synthetic and real-world datasets.", "questions": "1. How to quantitatively decide the termination criterion for the PEDESTAL algorithm?\n2. How does the proposed algorithm perform in a non-IID data distribution setting?\n3. How to distinguish the bad local minima from the saddle points in terms of the results presented in the paper?", "limitations": "Please include the discussion of the limitations for the proposed algorithms in the paper.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "I think the investigated topic is very interesting. The second-order optimality of decentralized stochastic optimization algorithm has not sufficiently been investigated. Most of existing works focused only on finding the first-order stationary point. It is exciting to see a fresh work that investigates the second-order optimality. The paper is easy to follow, though there are some typos that need to be corrected.", "weaknesses": "In order to make the paper more technically solid and sound, the authors may have to pay attention to the following aspects.\n\n1. In the algorithm framework, the authors use $n/10$ to terminate the algorithm. Why? Why not $n/5$ or $n/2$? Any specific criterion to determine such a certain number of nodes? Otherwise, it would be odd to just have this condition.\n\n2. The authors mentioned that broadcasting or aggregation is not required. But what about step 8 or 15? Did I misunderstand something here?\n\n3. The experimental results are not promising. More complex datasets and models are required to validate the proposed algorithm. In the discussion, the authors also said that all baselines were stuck at the saddle point and couldn’t escape it efficiently. How to guarantee the point these baselines were stuck at is a saddle point? Not just a bad local minimum? I think the authors should be careful about their claim. It would be better to see a toy example problem that includes obvious saddle points and local minima. Then the authors show exactly how the proposed algorithm and baselines perform.\n\n4. Some confusion about the table. The authors showed that the PEDESTAL has the larger gradient complexity than GT-HSGD. However, in terms of empirical plots, the PEDESTAL had faster and better convergence rate. Why? Moreover, the classic setting for the PEDESTAL-S is missing.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and we will address your concerns as follows.\n1. We can use any constant $\\alpha \\in (0, 1)$ in the terminate condition. In our paper we set $\\alpha = 1/10$ to simplify the computation in the convergence analysis. $\\alpha$ can also be set to $1/5$ or $1/2$, but some coefficients in the proof should be changed correspondingly. We will clarify it in our final version.\n2. Step 8 and step 15 only require communications among neighborhoods, without broadcast over the whole network. If node i and node j are not connected in the network, $w_{ij}$ is 0.\n3. Both two experiments in this paper are non-spurious local minimum problems, which means all local minima are global minima (see [1] and [2]). If the loss function value does not meet the global minimum, then the reached point is not a local minimum. Therefore, it is guaranteed that baselines are stuck at saddle points, not just bad local minima. We will add the explanation in the description of each task instead of putting it in the front of Section 5.\n4. First we need to point out that PEDESTAL matches the gradient complexity of GT-HSGD in the classic setting of $\\epsilon_H = \\sqrt{\\epsilon}$, ignoring logarithm terms. Moreover, the gradient complexity of GT-HSGD only guarantees the first-order optimality, which include both local minimum and saddle point. In contrast, the gradient complexity of PEDESTAL guarantees second-order optimality. In the experiments, PEDESTAL shows advantageous performance because PEDESTAL is better at escaping saddle points. PEDESTAL-S is a special case of PEDESTAL that the batchsize is fixed as $O(1)$ and the analysis of PEDESTAL-S only works for $\\epsilon_H \\ge \\epsilon^{0.2}$, which does not cover the classic setting.\n\n[1] No spurious local minima in nonconvex low rank problems: A unified geometric analysis, ICML 2017\n\n[2] Matrix completion has no spurious local minimum, NeurIPS 2016"}, {"review_id": "k5KD6UK7RG", "reviewer": "Reviewer_C5yK", "summary": "In \"Finding Local Minima Efficiently in Decentralized Optimization\" the authors propose a perturbed variance reduction stochastic optimization scheme that finds second order stationary points over a mesh network. The authors establish convergence results of the order \\tilde(O)(\\epsilon^{-3})  and verify empirically that their theoretical findings hold. Overall I think this work is nice, I follow with some criticism in the following sections.", "questions": "Questions/Suggestions/Comments:\n1. There are paragraphs in which the language needs to be polished. See for example lines 45 to 48. I \n2. In 2.2. the authors state that Perturbed SGD requires a complexity of O(epsilon^{-8}) to obtain a second order stationary point, and that this further hides a polynomial scaling with the dimension. My understanding is that the complexity is of order O(epsilon^{-4}) with logarithmic dependence with the dimension, see, e.g. Theorem 16 in https://arxiv.org/abs/1902.04811 (or 17 for the mini-batch).\n3.  If my comment in 2 is correct, the way to justify the current work, as opposed to a decentralized extension of perturbed stochastic gradient descent (which would yield a much simpler scheme) is through the benefits of variance reduction. \n4. The termination criteria is problematic. This is covered in detail under Weaknesses.\n5. In my view the main technical contribution of this work should be to extend the \"small stuck region\" lemma to the decentralized case. In this sense, I would expect a similar intuition as that highlighted in https://arxiv.org/abs/1902.04811 with further complications due to the consensus error(s). Instead, the intuition provided in 3.2.4. is entirely based on the quantities that can or can not be controlled in the proof. I think having a geometric interpretation instead would make the paper more understandable. ", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Originality: To the reviewer's knowledge this seems to be the first paper in the (stochastic) decentralized set-up to establish second order guarantees with a given rate. Consequently, in this regard the paper's novelty seems to be sufficient.\n2. Quality: The provided result seems to be technically sound. \n3. Clarity: The presentation of the paper and the use of language can be improved. In many situations, I feel the authors' comments do not provide an intuition on the scheme's dependence on relevant quantities but provide an explanation based on what can be controlled or not in the proof. I provide concrete feedback on this in \"Questions.\"\n4. Significance: I think this work is significant given that it is the first to provide this type of guarantees in the decentralized set-up.", "weaknesses": "1. It should be clear from the main text which polylog factors the notation \\tilde{O} is hiding. For this type of result, I would expect some scaling with the dimension (even if logarithmic) which should be highlighted at  some point. \n2. Experimental set-up: The results in this work hold under the assumptions that the gradients and hessian are Lipschitz. The problem upon which the simulations are run fulfills neither of these assumptions. I understand that the numerical simulations confirm that the scheme converges even if the assumptions are violated, but there is currently no way of understanding wether the order of number of gradient evaluations that it takes to achieve a certain precision is close to tight (given that the simulations work with a more general class of functions than that covered by the theory).\n3. Termination criteria: the scheme returns \\bar{x}_{t-C_T} if there are at least n/10 nodes satisfying esc^i \\geq  C_T. This seems to require global knowledge of the system. In other words, this does not seem implementable. As it is written, it seems to be the scheme does not terminate if this condition does not hold. The authors should clarify this. I see that in Section 3.2.3 the authors motivate the termination criteria via avoidance of the consensus error on the tracking variable (which is also not implementable), but this does not address how to implement the criteria.\n\n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the review of our paper and we will answer your questions as follows.\n1. Thank you for the suggestion. In our final version we will go through the paper carefully and revise those grammar and language mistakes.\n2. In our paper, we adopt the general bounded variance assumption on the stochastic gradient estimator. The baselines in this paper are also studied under this condition.  However, in [1] a stronger assumption on the tail of data distribution is used (see Assumption B in [1]). We will list and discuss this result in our final version.\n3. The limitation of [1] has been mentioned in the answer to Question 2, which requires a stronger assumption on the data distribution. Under such assumption, we think it is feasible to extend the simpler scheme in [1] to the decentralized setting since the perturbation is drawn from Gaussian distribution (the mixture of Gaussian distributions is also Gaussian distribution).\n4. Thank you for the question. The termination condition is used to guarantee a second-order stationary point theoretically, which can be satisfied with high probability. In practice, we can set a maximum iteration (as we have done in our experiment). Generally we need to evaluate the model after certain epochs to see if the training process is running properly and we can save a checkpoint when we find a better evaluation result. The theoretical analysis ensures that an optimal solution can be visited if the number of iterations is as large as $O(\\epsilon^{-3})$. Moreover, if we need the termination condition to avoid unnecessary iterations, we can run a separated process to collect the information when calculating gradients and transmitting models among neighborhoods, since obtaining the global knowledge of bool values (whether $esc^{(i)} \\ge C_T$) is relatively less expensive.\n5. In addition to the shape of stuck region, another important question is why there exists a stuck region. Suppose $x_0$ is a saddle point and $x$ is in the neighborhood of $x_0$.  If $x – x_0$ is in the eigenvector direction corresponding to a negative eigenvalue of $\\nabla^2 f(x_0)$, then the negative gradient is a descent direction and $x$ moves away from $x_0$. Consequently, the stuck region is proven to be contained in a ``thin pancake” as shown in figure 1 in [1]. However, if the consensus error is not under control, it can drive $x$ away from $x_0$ or push $x$ toward $x_0$, no matter what $\\nabla f(x)$ is. In this manner, the stuck region cannot be estimated. Besides, we would like to point out that the theoretical result of the termination section which categorizes all iterations into three types is also an important technical contribution of this paper. It forms the complete theorem together with the generalized small stuck region lemma. The small stuck region lemma provides guarantees for the case that the escaping phase is not broken while the termination section deals with the case that the escaping phase is broken.\n\n[1] On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points, https://arxiv.org/abs/1902.04811"}]

Author rebuttal:

Meta-review: The paper is the first of its kind to establish second-order guarantees with a given rate in a decentralized, stochastic setup. The technical soundness of the results is affirmed.  One weakness is that the experimental setup violates the paper's own assumptions about Lipschitz continuity for gradients and Hessians. Also, the experimental results are not promising. Overall, given its strong theoretical result, the value of this work outweighs its weakness.
Decision: Accept (poster)