Global Convergence Analysis of Local SGD for Two-layer Neural Network without Overparameterization
Authors: Yajie Bao
Amarda Shehu
Mingrui Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: convolutional neural network
gaussian input
local SGD
global convergence
non-convex optimization
TL;DR: We provide the first global convergence analysis of the vanilla local SGD for one-hidden-layer convolutional neural networks without overparameterization and without injecting noise, when the input data is Gaussian.

Abstract: Local SGD, a cornerstone algorithm in federated learning, is widely used in training deep neural networks and shown to have strong empirical performance. A theoretical understanding of such performance on nonconvex loss landscapes is currently lacking. Analysis of the global convergence of SGD is challenging, as the noise depends on the model parameters. Indeed, many works narrow their focus to GD and rely on injecting noise to enable convergence to the local or global optimum. When expanding the focus to local SGD, existing analyses in the nonconvex case can only guarantee finding stationary points or assume the neural network is overparameterized so as to guarantee convergence to the global minimum through neural tangent kernel analysis. In this work, we provide the first global convergence analysis of the vanilla local SGD for two-layer neural networks \emph{without overparameterization} and \textit{without injecting noise}, when the input data is Gaussian. The main technical ingredients of our proof are \textit{a self-correction mechanism} and \textit{a new exact recursive characterization of the direction of global model parameters}. The self-correction mechanism guarantees the algorithm reaches a good region even if the initialization is in a bad region. A good (bad) region means updating the model by gradient descent will move closer to (away from) the optimal solution. The main difficulty in establishing a self-correction mechanism is to cope with the gradient dependency between two layers. To address this challenge, we divide the landscape of the objective into several regions to carefully control the interference of two layers during the correction process. As a result, we show that local SGD can correct the two layers and enter the good region in polynomial time. After that, we establish a new exact recursive characterization of the direction of global parameters, which is the key to showing convergence to the global minimum with linear speedup in the number of machines and reduced communication rounds. Experiments on synthetic data confirm theoretical results.

Global Convergence Analysis of Local SGD for Two-layer Neural Network without
Overparameterization
Yajie Bao' Amarda Shehu² Mingrui Li
1 School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai, 200240
2 *Department of Computer Science, George Mason University, Fairfax, VA 22030 baoyaj aas2000tttt@sss
ete.eju..uuu..ooo. edu. cn, (ashehu, migghel edu
Abstract
Local SGD, a cornerstone algorithm in federated learning, is widely used in train- ing deep neural networks and shown have strong empirical performance. A theoretical understanding of such performance on nonconvex loss landscapes is currently lacking. Analysis of the global convergence of SGD is challenging, the noise depends on the model parameters. Indeed, many works narrow their focus GD and rely on injecting noise enable convergence to the local global optimum. When expanding the focus to local SGD, existing analyses in the nonconvex case can only guarantee finding stationary points or assume the neural network is overparameterized so as to guarantee convergence to the global minimum through neural tangent kernel analysis. this work, we provide the first global convergence analysis of the vanilla local SGD for two-layer neural networks without overparameterization and without injecting noise, when the input data is Gaussian. The main technical ingredients of our proof are a self-correction mecha- nism and a new exact recursive characterization of the direction of global model parameters. The self-correction mechanism guarantees the algorithm reaches a good region even the initialization is in bad region. good (bad) region means updating the model by gradient descent will move closer (away from) the optimal solution. The main difficulty in establishing a self-correction mechanism is to cope with the gradient dependency between divide the landscape of the objective into several regions to carefully control the interference of two layers during the correction process. As result, local SGD can correct the two layers and enter the good region in polynomial time. After that, we establish new exact recursive characterization of the direction of global parameters, which the key to showing convergence to the global minimum with linear speedup the number of machines and reduced communication rounds. Experiments on synthetic data confirm theoretical results.
layers. To address this challenge,
show that
Introduction
Federated learning is a prevalent framework in distributed learning to significantly reduce the communication cost and effectively preserve the privacy of local clients 43 27
As the most popular algorithm in federated learning, local SGD has shown great empirical success in training deep neural networks (DNNs) 43 33). However, existing literature has not been able to fully explain or characterize the convergence local SGD in training DNNs. Recently, extensive works are devoted
to analyzing the convergence of local SGD and its variants in nonconvex optimization (39 56 20 28
"Corresoonding Author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

32 40 However, traditional nonconvex analysis only guarantees convergence to stationary point, and convergence to the global minimum is in general NP-hard (2T].
Despite the NP-hardness results for nonconvex optimization, an increasing body of research tries to address structured nonconvex optimization by first-order methods with noise injection. For instance, Ge et al. [17] considered strict-saddle functions and showed that SGD with isotropic noise can find local minima in polynomial time. This motivated several ensuing works [25] 33 26 55 I on designing different first-order algorithms to improve convergence to local minima by injecting noise. cojje-inje schemes and their variants (such as, for instance, broadening from isotropic to anisotropic noise [64]) were shown to help convergence to global minima for
many problems that satisfy one of two conditions: (i) local minima are global minima, as in matrix
completion [18], dictionary learning [48], and certain deep linear networks [29]; or (ii) neural networks with distributional assumption, such as two-layer neural networks with the Gaussian input 63 It is worth noting that there is also a rich history on noisy GD based on Langevin dynamies (L.D) 30 52 8 99. For instance, recent work 6 proposes Exponential Family Langevin Dynamics (EFLD) to relax the Gaussian noise assumption and include noisy sign-SGD and variants of drop-out as special cases. When assuming the neural network is overparameterized. neural tangent kernel (NTK) analysis (23 guarantees convergence to the global minimum for local SGD 23 22 58 I0. However, the NTK theory is far from sufficient, since neural networks outperform their NTK counterpart in practice 4 and in theory (38]
Despite existing global convergence analyses of first-order methods for solving nonconvex opti- mization problems such as neural networks, they either require explicitly injecting noise or assume overparameterization such that NTK analysis can apply. Practical federated learning algorithms such as local SGD do not inject any noise and do not belong to the NTK regime, but they can still converge to global minima. For example, McMahan et al. [43] shows that the local SGD algorithm can achieve around 99% accuracy when training neural networks for image classification task. This motivates us to study the following question in this paper:
Is it possible to formally prove that the local SGD algorithm can find global minima for two-layer neural networks without injecting noise and without overparameterication
In this paper, we give a positive answer to this question under Gaussian input. We are inspired by a line of work on neural network learning theory with Gaussian input 7 [4 15 37 61 [3] and, in
particular address the distributed version of the setting in 13. Suppose N local machines share the following network:
f(Z. w. a) = Σ aj (z (Z. w),
where - (Z,,..., Zx) Raxk is the input matrix, u E Rd is the weight, R* is the output weight, and a (z)) = max 0} denotes the ReLU activation function. A good property of this network is positive homogeneity, i.e.. f(Z, cw, a/c) = fZ, w, a) holds for any e O. We assume each entry of the input Z is independently sampled from a standard Gaussian distribution. Then the response generated by noiseless teacher network: y - fZz, w", aa). Without loss of generality, we further assume ||w*| || = 1. We hope to learn student network by collaboratively minimizing the following mean square loss among N local machines:
L(w, a) = _ (v f(Z, w. a))²] 1E [fF(z) w., aa) w. a a))
(1)
Obviously, (w= a²) ) is the global minimum of the objective (1) with zero loss. In particular, the loss function also has a spurious local minimum; hence, minimizing loss is a nonconvex optimization problem. Please refer to work in [3] for further details on the landscape of L(w, a).
Despite the special input distribution, the best of our knowledge, there is currently no work demon- strating the global convergence of vanilla SGD or vanilla local SGD without overparameterization Work in [T3] proved that randomly initialized GD can converge to the global minimum or the local minimum with a constant probability. The initial region where GD can converge to the global minimum also called the attraction basin, where the gradients of two layers both point in the correct directions to the ground truth. To obtain the global convergence with arbitrary initialization in the same initial region, Zhou et al. (33) proposed a new perturbed GD algorithm by carefully injecting noise to the weights in two layers. Although the convergence of vanilla SGD has not been explored
2

---

theoretically, the simulation results in [13 631 show that vanilla SGD with random initialization can converge to the global minimum with probability when the ratio [1 aaa//laaa is large. This result motivates us to investigate the global convergence of local SGD without injecting additional noise to escape the local minimum.
In this paper, we analyze the global convergence of the vanilla local SGD for training a two-layer neural network with Gaussian input, whose initialization starts from the same initial region as in 13 63) Formally, our main contributions are summarized as follows:
1. We introduce a new self-correction mechanism of local SGD under condition on a" (see Assumption []: the signals from two layers can be corrected in polynomial time even though the initial point comes from bad region where the gradients point to the wrong direction (w", a') a²). The condition also explains the simulation results in [3] The self-correction process is very difficult to analyze due to the mutual influence effect of two layers. To address this challenge, we utilize novel technique by carefully dividing the landscape of the objective (T) into several regions. In each region, the negative effect from one layer to another layer can be controlled to a negligible scale. We notice that Li and Yuan (37] also showed the self-correction phase of SGD for the two-layer network under Gaussian input. However, the network's 's structure in 37 is different from the network studied in this paper. In addition, Li and Yuan (37 also required bounding the noise of stochastic gradient and so cannot handle the vanilla SGD with Gaussian noise as in our case.
2.
We show the global convergence of local SGD with linear speedup, which indicates that the iteration complexity is divided by the number of machines N. In addition, we also show that the communication complexity of local SGD is reduced compared with the naive parallel version of SGD which needs to communicate at every iteration. The analysis in the convergence stage is very different from the GD in Du et al. [T3. We establish a new recursive dynamic to characterize the direction of the global weight in the first layer. Moreover, the objective is not smooth, since the gradients incorporate the angle between the first layer's 's weight and the ground truth. Therefore, conventional analysis of local SGD for a general smooth objective [47 54 cannot be applied in the convergence stage. Due to the inner structure of gradients under Gaussian input, we find that the discrepancy caused by the local updates can shrink as the angle decreases, which enables us to refine the bound of discrepancy to be dominated by the statistical bound of noise.
3. We conduct several simulations on the two-layer neural network to verify the theoretical results. The experiments demonstrate that local SGD indeed corrects the wrong signals from the initial point and exhibits speedup in the convergence stage, corroborating our theoretical results. The simulation results also verify that the condition imposed on [1 T a aa|/||a is almost necessary to show the convergence with almost arbitrary initialization.
2 Related Work
Federated Optimization There is a wave of studies on federated optimization in different settings. In the convex optimization setting with homogeneous data, one-shot averaging was studied [5] 42
60
where each machine solves a local optimization problem and the average happens only at the last iterate. Local SGD skips communication rounds, and the convergence analysis is shown for
convex 47
1
34
28
54
53 32
31 and nonconvex optimization problems [62] 24 51 39 20
There is a line of work which tried to compare minibatch SGD and local However, these optimization algorithms only work for black-box functions and do not utilize the property of neural networks. As neural network loss landscapes are typically nonconvex, these federated optimization algorithm can only guarantee to find stationary point instcad of a global minimum.
56
34
28
45
59
32
SGD in federated learning [54] 53
Optimization Theory for Neural Networks
There is a line of work studying two layer neural 61 19 5). Li and Liang [36] studied two layer neural
networks with Gaussian input 49 37 networks with cross-entropy loss and showed that SGD can find the global minimum when the neural network is overparameterized. Du et al. (16] proved that GD can find the global minimum for two layer overparameterized neural networks under &2 loss. These results are later extended to deep neural but are not directly applicable to analyzing local SGD the distributed
networks by 14 66 2
setting.
3

---

Algorithm Local SGD for training two-layer neural network with Gaussian input
Initialize vo E gd-1 and do B& [1aaa]
vR
for r = ........ R 1 do
for = 1.................. do
Synchronization: a; <- az and vi, <- Ut, for .........
do Sample Z from the standard Gaussian distribution and generate the response yf- Update 4/+1 = aj VVal(oj, a; Zi, vi).
Update v/ = vi - v)V.lv a Z.,().
end for end for Update at,+1
1 N a and 0t N/2 EE Dir N
end for
Federated Learning on Neural Networks There is a line of work which studied federated learning algorithms on overparameterized neural networks under the NTK regime [35 22 10 58 [7]. contrast, our analysis does not fall in the NTK regime: we directly study the dynamics of local SGD over neural networks without overparametrization.
In
3 Notations and Problem Setup
Denote || || the Euclidean norm and ( by the inner product. gd-1 denotes the d-dimensional unit sphere and IB (p) denotes the k-dimensional ball with center zero and radius p. For two vectors v, IRd denote (vv w)) E [0, n] the angle between v and w. The uniform distribution denoted by (-). Moreover, we use O hide logarithmic factors.
We adopt the weight-normalization technique [46] to the first layer by re-parametrizing w = 1/||o|| which leads to the following prediction model:
f(Z, v. a)
Σ
(Z v)
o
(2)
|
1=1
Given any sample (Z, v). we denote the empirical loss by
1 (5 w: ,a) 5(2, a)))²
E(v, a: Z. v) = 5 f n, a)) 2
In the distributed environment, suppose there are local machines sharing the same teacher model fZ, w", "",a", aa). It means that given any local input Z', the response is y² = f(Z', w", aa). Let (4o....,1n 1n) be the set of synchronization time, where io 0, in = and f 1, = I for any The detailed procedure of local SGD is presented in Algorithm 1 where the initial point is from the same region in Du et al. [3] and Zhou et al. 63] : Un E Sd and an E [ [[[1Taal//V]
In each
round, the i-th machine runs / steps SGD using the stochastic gradients V.,((v), at; Zi. vf) and Val(r) af; Zi yf) computed by the local input (Z), v(). At the end of round, the server aggregates
local weights to obtain the global weight and then synchronizes the global weight to each machine.
4 Theoretical Analysis
We first introduce two auxiliary sequences v2 = EN / and a, = E at/N, which often appears the analysis of local SGD 47 53 28 Notice that (v, a,) = (vj, a²) for E [N] if is the synchronization time, i.e., t E Z. Denote wi = w the local normalized weight and P. (I- (w)) | the respective projection matrix. Now let L(w, a: Z) be the empirical version of the loss function I(w, a) defined in ( that is T.uw, a: Z.) = (z(, w",
(Z, w, a))²
Since fZZ w", ,aa),
will hide and write E(V, a; Z) f(v. a; Z, y) hereafter. Notice that L(w, a; Z) = f(v. a; Z) for w = w/llul.. By recalling the normalized model ( we have
V V. af: z = P.V [(wi, a:: Z,), Val(oi a; Z2 V.L(wi at Z,).

---

According to Algorithm | the updates of auxiliary sequences can be written as
N _ P..VoLiui ai: Z,), ac+1 - " V VaL(wi. a; Z,). U++1 = U1 N
N
1
For ease of technical presentation, we denote the averaged noise terms by &. = N E Pic: and
Er N Li=1 ei. where ş Vw at; Zi) (ww, at) and Ej - Val(wij ai Zi) VaL(w)) a;) are the local noises in stochastic gradients. addition, for the iterates of and vt. we write 0f = L(v,. w*) and o, = L(v,, w*), respectively.
4.1 Exact Dynamic of Each Layer
In this subsection, we will give the exact dynamic of each layer in the training process of local SGD, which is the starting point of our analysis. Denote P, - ||. (I (.w.? by the global projection
matrix, where wi = / / The proofs of this subsection are deferred to Appendix A.1
Lemma 1.
Let ú1+1 = 24 - 17
P N E WwL(wj ai) + E1) and o = L(d,, w²)
The first
layer in local SGD satisfies that
||142||2 sin² Φct1 (1 d cos Φ1) |122| "ooll"sin² sin² o. 22 + M2, + H
(4)
where d = 1 EN
x-d; (a)) aa" He = ||00111 sin Φet1 - || liiii Φ041 and
sin?
2x
will
M1. = U1 1 P
Σ i=1
v Law a;) (I-w" (ww))( Et, M2. = E. (I- (1-w((wl (ww") E
Lemma] [ is crucial to control the angle and show the linear speedup in further analysis. For each local machine, Lemma 5.5 in [13] provides the dynamic of sin? of. which cannot characterize the dynamic of global quantity sin o; due to the nonlincarity. Here we introduce new intermediate variable Ut41 and find an equality (4) to show the recursive relation between || ? Φt+1 and ||,, sin" 2 de through the global quantities, such as Mr. and M2,.. It is worthwhile noticing that MI.2 is the averaged noise in local SGD, whose variance is divided by the number of clients N, namely linear speedup term. fact, we can control the dynamic of sin Φi by upper bounding the discrepancy term He. Let us assume the last three terms in 4 are negligible and (at) aa >> 0 for any E [N]:
(1) When 6, > x/2, ||v.1 ssnn oe will continuously increase since X COS d, O. It indicates that di can decrease to n// if Dell is upper bounded by a constant, which also means the first layer can be corrected and avoided converging the spurious local minima.
(2) When d, < 1//2, ///l sin? di will continuously decrease to zero. It indicates that Φi can converge to zero if ||v,1] is lower bounded by a constant. The initial region with Φo < x/2 and ag a 0 is also called the attraction basin in [3]
Through the remarks above, we can see that the positive signal of the second layer is crucial both the self-correction of the first layer and global convergence. Next lemma presents an exact dynamic of the averaged weight in the second layer.
Lemma 2. Let Ao = |1 12 12- - (1 a a²)(1" ao) and ((w) = (TT ()) cos Φ + sin Φ. For local SGD algorithm started with the initial point (vo, ao), the second layer satisfies that
2 2 p(++
π - 17
2
n(
a a"
1
ag
a=
1 1-
Ao
2
k
2π
?||a"1 6-1
t-1-a
1
N
1
Σ
B S(Ev0-1),
(5)
2x
2
where S(Eo:t11) (defined in Appendix A) is the noise term involving Eo. ... _ and
17 |1
x-1
s-1-1
= 1+
1-
(N g(o)))
2π || la 112
2π
1=0
5

---

1/64
1/32
1/16
1/8
1/4
1/2
Local SGD
0.61
0.62
0.69
0.93
1.00
1.00
Minibatch SGD
0.60
0.62
0.69
0.91
1.00
1.00
Table 1; Success probabilities of converging the global minima under different values of [1 a" (</(aalla"" The simulation setting is given in Section
Notice that the first term ( in B3 is negative whenever o < </2, but the second term in B is always positive for of E (0, m]. In particular, ग ( tends to be larger when of gets closer to (i.e., wi drifts away from w²). This insight provides a possibility that local SGD can correct the signal of the second layer by itself, instead of injecting additional noise like [63
Through carefully inspecting the ingredients of dynamics, we have the following roadmap to show the global convergence of local SGD: (1) For arbitrary initialization (Vo, ao) except for measure zero set, where the angle of the first layer between initialization and the global minimum is π, show that a, a' can turn to the positive signal in polynomial time; (2) Show that a, a" can be lower bounded by a positive constant value and 6s will decrease below π /2. (3) After entering the attraction basin, show that (wr, a,) will converge to the ground truth with linear speedup guarantee.
4.2 Self-correction of Signals in Two Layers
In this subsection, we will show the iterates of local SGD can enter the attraction basin such that a, a- > and d, 7/2 after Ö steps. Before that, introduce an assumption on a*.
Assumption 1. Define |1 a" /2/ (A|laa"1??) We assume k 320( π 1)² and the ground truth k(*+k-1) satisfies [1 a²12== 720 log (4+
and
π + k π - k
32(m 1) -1
(6)
The conditions on k and [1 a² are imposed for technical reasons. We believe that constant lower bound (the right-hand side (6)) for a is necessary to show the global convergence with almost arbitrary initialization, which is also verified by our simulation results in Table We compute convergence probabilities of local SGD and minibatch SGD under different values of a. The initial (I1laa//VV
points are randomly selected by wo ~ Unif(S and ag ~ Unif (|1 a I/VK) in each trial. the convergence probability reaches 1, it means that local SGD minibatch SGD can converge to the global minima with arbitrary initialization except for a measure zero set. When a I 1/8, both minibatch SGD and local SGD cannot converge the global minima with probability 1.
Theorem (Self-correction of the second layer). For any initial point (Vo, ao) with do E [0, x), we
Ta'? Under Assumption 16( k(++E-1)
denote Ta = in 2 0 : a a* 2 )a) the first time, where Ja
if
ck2 /oog(NNk/// max { n( n(VT +D.nn(IIVVV++
qk N
|a-11 TT
<1
for a sufficiently large constant c, then Ta S <0 log k) with probability least 8.
This theorem completes the first step of the roadmap. the self-correction of the signal the second layer, whose proof is given in Appendix D.I If [1 aa 1212/ [|//|aa]| II2 s 1/ (p)y Du al. 13 proved GD can converge to the spurious local minima with the initial condition a a" < 0 and de n//2. Therefore, our results do not contradict theirs because we assume |1 a. 12 |2/||""||" is large. The simulations of [13, 63) show that the success probability of converging to the global optimum of SGD increases the ratio | a" l/||a*|| increasing. Theorem I can potentially explain this phenomenon since the condition (6) will be satisfied eventually when I aa l/|la" keeps increasing.
Proof sketch of Theorem 1. The proof is very technical since the angle of will affect the sign of B in the dynamic of a, while controlling of also requires bounding the scale and controlling

---

the sign of a, a". To tackle this challenge: (1) We divide the initial region of ou into four regions: (0, dd), 100, x x22). [T/2, d²) and lő" r)); (2) For each of the first three initial regions, prove that either a a" 2 7 in O(1/n) steps enter the next region in ((1/n) steps; (3) In the last region [0", T). we use the condition (6) to show a a* will turn positive in ((1/n) steps. The dividing technique enables us to control the individual angle of in four "nice" regions where a, a can be corrected with negligible disturbance. Here Ø0 = arccos /5) is chosen for convenience to avoid dependence on the initial value sin @o if ØU < T/2, and 6t is carefully chosen for technical reasons.
Lemma 3. Denote Tt arcoos
114 -+*-11 (-
11 a log(4 + x2)) and
so = min sin Φ"1
6osōō sin Øo 0o>0u1 sin [ {(20) a a13) (111111111 11]]]
Under the same conditions of Theorem [ If the learning rate satisfies
clla*| Vla""l2Vlog(AMM Lll//olgNNN///// max I(lTa+
V
N
TJ
16k
(8)
for a large absolute constant e >> 0, we have sin Pr. 2 15VE
with probability at least 1 - 8.
Recalling the dynamic 4.. we know sin di tends to decrease to O when o; n/2 and a, a' < 0. means that the first layer moves in the direction of spurious local minima during the self-correction process of the second layer. Lemma I
lower bound for sin or,, guarantee the first layer
will not converge to the local minima. The proof of Lemma 3 is deferred to Appendix D.2
Theorem 2 (Self-correction of the first layer). For the initial point (vo, ao) with ag a" Ta
(defined in Theorem [ and sin do > we denote To inffl 0: &v S Φ ). where cos Φ 1 aT log(4 (4 + 12)). If the learning rate satisfies
144m
c|Ia"113 (oVoooNNk/// max { T (nIVIa+
S sin Φo.
(9)
N R2a
for a large absolute constant c > 0, it holds that Tv S 0 probability at least 1 8. 8.
and a., a" 2 7a/32 with
17 sin Φo
This theorem finishes the second step of the roadmap to convergence. The detailed proof is deferred to Appendix D.3 Now we give the iteration complexity spent for self-correction for the worst
initialization: ag a < 0 and do max - (|120=11//0A1]] Since sin 23t = 0(1,, plugging
the lower bound of sin o., in Lemma 3 we can get
( h7/2
To + To S
(10)
17 sin do
Proof sketch of Theorem 2. We divide the initial region into three regions: (01, x), (²) and [o, o²), where of is adapted to the choices for Ø and のt For the first two regions, we show that d will enter the next region in polynomial time, while the last region is our target. The difficult part to show the correction of oe falls in how to guarantee a, a" will be lower bounded by O(7a) for
any 2 O, which is divided and conquered by considering the intermediate quantities such as d', zs and 6² To better understand the choices for these quantities and %o. we rearrange B3 and have the following decomposition
1
1 1
--1 1
a²
7T + k 1)
B
1
π
1
aa
T T
-
||a11
2x
8a
+ g(())
17 1
8-1
+ l
-
8 8-1-1
(1 (1- g(oi))
17
2T la
12
2
Due to the condition (6) in Assumption 1 C. is positive and used to correct the sign of a. a" and
keep it positive. Since Oa is still not negligible when is small, we use Ya to compensate la after enrolled summation. The uncertain part 0, will be positive whenever o' < of < Ø² for 1 < s.
7

---

4.3 Convergence with Linear Speedup
With the correction guarantees in the previous subsection, we are ready to proceed with the conver- gence analysis of local SGD.
Theorem 3. Suppose the initial point (vo. an) satisfies ag a' 2 "la/32 and do S क'. For Ne
any > O, we choose
a dlog(dN/eo) for some absolute constant > 0. If
sta' s'd I S EN min {1, NIT No
and c < min dk d)- then E(VT, aT) S e holds with proba-
bility at least 1 - where T =
dk Nr
We have the following implications about the result in Theorem
(1) To the best of our knowledge, this is the first convergence result with linear speedup on the number of machines N for two-layer neural networks. Besides, our convergence analysis does not rely on the overparameterization of the width of the second layer (i.c., k).
(2) The dependency on e matches the best-known results of local SGD for strongly convex objective in Woodworth et al. [53]. In fact. the size of the first layer d resembles the variance of stochastic gradients o² in the traditional optimization literature. We can show (V [[,,,, 0r a²) m-1
2m I|a, a a=1 (( ((oe)>la* 112. Therefore, when the first layer converges has converged (Øl R 0), at can converge to a" like the strongly convex regime.
(3) According to the condition on I, we can obtain the communication complexity in the convergence stage
No6 d
Rewen = = max
(11)
When N S min(dk4 ( JJ the communication complexity in this stage can be Reome Ō(k*), which is significantly reduced compared with the iteration complexity.
We show local SGD's convergence layer by layer. Next lemma ensures that the weight of the first layer can converge to the ground truth in polynomial time.
Lemma 4 (Convergence of the first layer). Under the settings in Theorem 3 Suppose the initial point satisfies Φo I Φ' and ag a 2 Ya /2/32. With probability at least 6, we can guarantee that sin? 2 de S holds for any Ö (1:27-1) S t < Ö(n=
worthwhile noticing that (Ur,, a,,) ) in Theorem satisfies the conditions for initial point in Lemma 4 Therefore, local SGD enters the attraction basin after finishing the self-correction process. In fact, showing the complexity Ō(e-1) ) is not trivial based on the traditional analysis of local SGD
47 [4]. The issue comes from the inner-product noise term M1,; and the discrepancy term Hę in Lemmal whose enrolled summations can only be bounded by O O(ve/d) and Of [)e} respectively at the beginning of convergence stage. Thanks to the special structure of gradient, we find that the scales of M1, and H, shrink sin di decreases. In light of this,
continuously refine the bound by the following contraction: for (K + 1)T, SLS Ö(1 it holds that
1+
sin 2 de S max (VE++VVd ne
By taking K = (logg(1/e))) (L))), we can obtain the target convergence sin? o. S e with high probability. More details can be found in Appendix E.I
Lemma 5 (Convergence of the second layer). Under the choice for n and conditions for in Theorem
Suppose sin? Φe < e holds for any 0 S Ö(n 2). With probability least 8, we can guarantee that ||a - a" S holds for any Ö (1 < 0()
The lemma stated above guarantees the convergence of the second layer after that of the first layer,
whose proof is deferred to Appendix F.2 Equipped with Lemmas 4 and we can prove Theorem by leveraging the closed form of the objective L(w, a) (see Lemma
8

---

1.0
1.0
1.00
0.75
co5p2
0.6
0.50
Local SGD
0.4
Minibatch SGD
0.2
1.0
1.0
0.5
0.6
-0.5
0.2
-1.0
-1.0
0.0
1059
0.2
0-
0.0
100
20
Rounds
Rounds
Rounds
(a) = aa", du > //2
(b) 0g aa' O0 < 4/2
(c) 0u 0, do T/2
Figure 1: Converged trajectories of local SGD and minibatch SGD with different bad initial points. The dimensions of the two layers are 10 and d 25. The number of skipped communication [= 8. The batch size is 4. The two algorithms' learning rates are 0.1.
The perturbed GD method in Zhou et al. 63 requires manually adjusting the scale of injected noises and the learning rate between the transition of two phases. In local SGD, learning rate in the self-correction stage and convergence stage. Considering an initial point that
universal
closer to spurious local minima (øo > の²) defined in Lemma 3 conditions (7.. (8) and (9) on
the learning rate be satisfied if choose O [d/(eN))- Together with (TO) and (11, if
N $ min(dk*, 111, we can get the total communication complexity
1.11/2
Ruxal Ō
sin Φ0
Therefore, theory shows that local SGD can correct the signals and converge the global minima with almost arbitrary initialization except for the case of initializing at the local minima (Øo = π))
Experiments
We report simulation results synthetic data. We also compare the performance of two algorithms: local SGD and minibatch SGD. At each round, minibatch SGD updates the model weights by using the stochastic gradients with batch size NI in total to update the model, where each local machine computes I gradients and communicates with other machines. Minibatch SGD and local SGD have the same computation and communication structure
In our first simulation, bad initial regions (i.c., Φo > 7/2 or ag a" < 0) are reported in Figure As of two layers can be both corrected to good region (i.e., both cos ( and a, a' to 1 and the loss goes when increases) even in the worst case when au phenomenon is that local SGD can correct the signals faster than minibatch SGD. The reason is that the statistical error stochastic gradients not dominating the self-correction process, so effect of large batch size in minibatch SGD (i.e., with batch size N/ for 1 iteration) is not as useful as smaller batch size in local SGD with more iterations (i.e., batch size 1 for iterations on each machine with N machines in total). These results corroborate theoretical analysis.
||w*| = =||a"||
and [ Vk. The results starting from three see, the signals
and do π 7/2. An interesting

---

-0.2
-0.
1.00
Local SGD
-0.4
Minibatch SGD
-0.4
0.75
COSØ
0.50
-0.6
-0.6
0.25
0.00
-0.25
-0.1
-0.1
0.75
-0.2
0.50
-0.4
0.5
1.5
0.30
0.4
0.25
0.5
0.2
0.0
250
1000
200
1000
200
400
600
Rounds
Rounds
Rounds
1/32
(b) 1/16
(c) 1/4
Figure 2: Trajectories of local SGD and minibatch SGD under different values of a. The dimensions of the two layers are k = 64 and d = 25. The number of skipped communication 8. The batch size is 16. The two algorithms' learning rates n 0.1.
In the second simulation, we plot the trajectories of local SGD and minibatch SGD under different 1a/Vd and point is fixed 1n (-1,0,.... 0) and as (-var, 0, .,...; 0), where do n/2 and ag a < 0. When a = 1/32, 1/16, we can see that minibatch SGD and local SGD converge to the local minima. When 144, they converge the global minima with the same initial point. In this case, as we can see from Figure Ccc, the signals of two layers can be both corrected to good region.
values of a in Figure 2 Here we
(1ck. O...., .)...0v//v 0)/Vak. The bad initial
In the third simulation, we calculate the probabilities that local SGD and minibatch SGD converge to the global minimum under different values a. The averaged results are taken over 100 independent repeated simulations. In each trial, generate initial points by do Unif(Sd-1) and ag Uni a² (/)/)))) The results given in Table
Conclusion
We theoretically investigate the convergence of local SGD, a cornerstone algorithm in federated learning with strong empirical performance. We demonstrate convergence the global minimum for two-layer neural networks without overparameterization, without injecting noise, and when the input data Gaussian. A new self-correction mechanism guarantees the algorithm reaches good region even if the initialization is in bad region. The landscape of the objective is divided into several regions to carefully control the interference of the two layers during the correction process. new exact recursive characterization of the direction of global parameter provides the key to show convergence to the global minimum with linear speedup in the number of machines and reduced communication rounds. Experiments best of our knowledge, this work is the first to theoretically demonstrate the global convergence of the vanilla local SGD for neural networks without overparameteriiatton.
simulated data corroborate the theoretical results. To the
10

---

Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers for their helpful comments. Mingrui Liu is supported by grant from George Mason University. The work of Yajie Bao was done when he was virtually visiting Mingrui Liu's 's research group in the Department of Computer Science George Mason University.
References
[1] Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. Advances Neural Information Processing Systems, 31, 2018.
[2] Zeyuan Allen-Zhu and Yuanzhi Li. Can sgd learn recurrent neural networks with provable generalization? Advances in Neural Information Processing Systems, 32, 2019.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization.. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
[4] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 32, 2019.
[5] Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two layer rectified neural networks in polynomial time. In Conference on Learning Theory, pages 195-268. PMLR, 2019.
[6] Arindam Banerjee, Tiancong Chen, Xinyan Li, and Yingxue Zhou. Stability based generalization bounds for exponential family langevin dynamics. International Conference on Machine Learning (ICML), 2022.
[7] Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In International conference on machine learning, pages 605-614. PMLR, 2017.
[8] Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-SGD: Biasing gradient descent into wide valleys. In International Conference on Learning Representations, 2017.
URL
[9] Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamics of langevin diffusion and noisy gradient descent. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL hhtpps
//openreview. http://rwwweeeeeeefouuuio..aaaae
[10] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi. Local sgd optimizes overparameterized neural networks in polynomial time. In International Conference on Artificial Intelligence and Statistics, pages 6840-6861. PMLR, 2022.
[11] Aymeric Diculeveut and Kumar Kshitij Patel. Communication trade-offs for local-sgd with large step size. Advances in Neural Information Processing Systems, 32: 12:13601-13612 2019,
[12] Simon Du and Jason Lee. On the power pur-parametrizatioon in neural networks with quadratic activation. In International conference on machine learning, pages 1329-1338. PMLR, 2018.
[13] Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer cnn: Don't be afraid of spurious local minima. In International Conference on Machine Learning, pages 1339-1348. PMLR, 2018.
[14] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675-1685. PMLR, 2019.

---

[15] Simon S Du, Jason D Lee, and Yuandong Tian, When is a convolutional filter easy to learn? arXiv preprint arXiv: wrXi::7709.06129 2017.
[16] Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint arXiv: 1.03804, 2018.
[17] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points Donine-online stochastic gradient for tensor decomposition. Conference on learning theory, pages 797-842. PMLR, 2015.
online
[18] Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. Advances in neural information processing systems, 29, 2016.
[19] Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden-laye neural networks with landscape design. arXiv preprint arXiv: 170101001,0000000000
[20] Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local sgd with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pages 11080-11092. 2019.
[21] Christopher J Hillar and Lek- Hen- Lim. Most tensor problems are np-hard. Journal of the ACM (JACM), 60(6):1-3))) 2013.
[22] Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. Fl-ntk: A neural tangent kernel- based framework for federated learning analysis. In International Conference on Machine Learning,
pages 4423 1423-4434. PMLR, 2021.
[23] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[24] Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances in Neural Information Processing Systems, pages 2525-2536, 2018.
[25] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International conference machine learning, pages 1724-1732. PMLR, 2017.
[26] Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pages 1042-1085. PMLR, 2018
[27] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning, Foundations and Trends in Machine Learning, 14(1-2):1-210 2021.
[28] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143 PMLR, 2020.
[29] Kenji Kawaguchi. Deep learning without poor local minima. Advances in neural information processing systems, 29, 2016.
[30] A. D. Kennedy. The Theory of Hybrid Stochastic Algorithms,, pages 209-222 Springer US, Boston, MA, 1990. ISBN -78-1-99151555 100------15--778777 doi: 10.10007978---4415--00 1007
URL
hntpss://doi. http://d...0.//...000000/1111110
[31] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. In International Conference on Artificial Intelligence and Statistics, pages 4519-4529, PMLR, 2020.
12

---

[32] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393. PMLR, 2020.
[33] Kfir Y Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint 1611.:661..4553 1.0431, 2016.
[34] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3)500-60, 2020.
[35] Xiaoxiao Li, Meirui Jiang, Xiaofei Zhang, Michael Kamp, and Qi Dou. Fedbn: Federated learning non-iid features via local batch normalization. arXiv preprint a1X.02210..07623, 2021.
[36] Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent structured data. Advances in neural information processing systems, 31, 2018.
[37] Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, pages 597-607, 2017.
[38] Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning weerpparaettrized two-layer neural networks beyond ntk. In Conference on learning theory, pages 2613-2682. PMLR, 2020.
[39] Tao Lin, Sebastian Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local sgd. arXiv preprint
088100777,, 2018
[40] Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication-efiiai distributed gradient clipping algorithm for training deep neural networks. arXiv preprint wwXi::2005.05040 2022.
[41] Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael Jordan. Sampling can be faster than optimization. CoRR, abs/181 2018. URL http:://aaaxiiv.or hatg//bs//8111 08413
[42] Ryan McDonald. Keith Hall, and Gideon Mann. Distributed training strategies for the structured perceptron. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 456446566666 166.464.7 Association for Computational Linguistics, 2010.
[43] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. coamuuicaation-fffcciene learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[44] R. M. Neill. MCMC Using Hamiltonian Dynamics, pages 113-162. ISBN 9780429138508 wow.innoooiiiinnnn wawp:/aaaannnnaaaaaaaaaaoooo.ooo 10tp//000..000/100900000000
Chap- URL
man and Hall/CRC, Boston, MA, 2011. https: https://www, taylorfrancis..oomm htt.:/aannnis.ccocaaaaaaaaaaaaaa hhtpa//ccccccappaeeeeeaat////// acmc-using.
[45] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konecny, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. ICLR, 2021.
[46] Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterizatioon to accelerate training of deep neural networks. Advances in neural information processing systems, 29, 2016.
[47] Sebastian U Stich. Local sgd converges fast and communicates little. 18X.v:1805.09767, 2018
arXiv preprint
[48] Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere i: Overview and the geometric picture. IEEE Transactions on Information Theory, 888-8485 2016.
[49] Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications convergence and critical point analysis. In International conference on machine learning, pages 3404-3413, PMLR, 2017.
13

---

[50] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[51] Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication-efficientt sgd algorithms. arXiv preprint 1eXivv1808.07555 2018.
[52] Max Welling and Yee Whye Teh. Bayesian learning via stochastic gradient langevin dynamics. In 28th International Conference on International Conference on Machine Learning, ICML'11, page 681-688, Madison, WI, USA, 2011. Omnipress. ISBN 978 14503061995
[53] Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch local sgd for heterogeneous distributed learning. arXiv preprint arXiv:2006.0473 04735, 2020.
[54] Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai. Brian Bullins. Brendan Memahan, Ohad Shamir, and Nathan Srebro. local sgd better than minibatch sgd? In International Conference on Machine Learning, pages 10334-10343. PMLR, 2020.
[55] 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.
[56] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. arXiv preprint arXiv:1905.0m 03817,
2019.
[57] Yaodong Yu, Alexander Wei, Sai Praneeth Karimireddy, Yi Ma, and Michael Jordan. Tet: Convexifying federated learning using bootstrapped neural tangent kernels. Advances in Neural Information Processing Systems, 35:30882- 00380888-3397,,,00 2022.
[58] Kai Yue, Richeng Jin, Ryan Pilgrim, Chau-War Wong, Dror Baron, and Huaiyu Dai. Neural tangent kernel empowered federated learning. In International Conference on Machine Learning, pages 25783-25803, PMLR, 2022.
[59] Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A feder- ated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint a0Xiv:2005. 1418, 2020.
[60] Yuchen Zhang, John C Duchi, and Martin J Wainwright. Communication-efficee algorithms for statistical optimization. The Journal of Machine Learning Research, 14(1):3321-3363, 2013.
[61] Kai Zhong, Zhao Song, Prateek Jain, Peter Bartlett, and Inderjit Dhillon. Recovery guarantees for me-hiddeenllaye neural networks. In International conference machine learning, pages 4 4149. PMLR, 2017.
[62] Fan Zhou and Guojing Cong. On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization. arXiv preprint arXiv: 2017.
[63] Mo Zhou, Tianyi Liu, Yan Li, Dachao Lin, Enlu Zhou, and Tuo Zhao. Toward understanding the importance of noise in training neural networks. In International Conference on Machine Learning, pages 7594-7602. PMLR, 2019.
[64] Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects, 2019.
[65] Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. In Advances in neural information processing systems, pages 2595-2603, 2010.
[66] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterizze deep relu networks. arXiv preprint 181 2018.
14

---

Appendix
Contents
1
Introduction
2 Related Work
3 Notations and Problem Setup
4
Theoretical Analysis
4.1
Exact Dynamic of Each Layer
4.2 Self-correction of Signals in Two Layers
4.3
Convergence with Linear Speedup
5
Experiments
Conclusion
10
A Preliminaries for Analysis
A.1 Dynamic of the First Layer
16
A.2 Dynamic of the Second Layer
A.3 Concentration Inequalities for the Noises
19
A.3.1
Sub-exponential Martingale Difference
19
A.3.2 Scales of Sub-exponential Norm for Noises in Stochastic Gradients
20
A.3.3 Corollaries of Lemma
Bound the Weight's Norm during Training Process
B.1 The Scale of the Second Layer's Weight
B.2 The Scale of the First Layer's weight
C Bound the Discrepancy during Training Process
28
C.1 The Discrepancy in the First Layer
28
C.2 The Discrepancy in the Second Layer
30
Self-correction of Signals
D.1 Self-correction of the Second I Layer
D.2 Proof of Lemmal
D.3 Self-correction of the First Layer
E Convergence with Linear Speedup Convergence of the First Layer
E.1
E.2 Convergence of the Second Layer
48
E.3 Conclusion
50
15

---

A Preliminaries for Analysis
We write 0 = (O.....0)) 0)T, 1 = (I) and denote by the identity matrix. The following lemma gives the closed forms of the objective and gradients.
Lemma 6 (Du al. (I3). If every entry of Z is i.id. sampled from Gaussian distribution with mean 0 and variance I, and |
1, then the population loss is
L(w, a)
π 11
||a|2
π -
( - 1
a²a
2T
2
π
1
(1 a a²)²²
1
(1 a)²
(1)
(A.1)
2T
2T
-0s where g( = (π - (6) cos Φ + sin @ And the the expected gradient of w and a are
T- a a w
VoL(w, a)
(A.2)
2T
1 [111 + (x - 1)I)a - -(11 (g(Ø) - 1)))aa]
Val(w,
(A.3)
2
Denote the noises of stochastic gradients in each local machine i E by]
Ε: = V L(wi, Z)) VuL(w, a;), e = VaL(wi, a:: Z,) Val(wi,a))
Then we write the averaged noises as
N &
1 6 =
Pigi
N
Let P.
|oo 1 (I w, w.w,). We introduce an auxiliary sequence öG which updates by
1 N
0++1 U2 -1
P
Σ v
W at) + Es
(A.4)
Then it holds that
1 Út+1 U2+1 "
=: 0:0 n/14
(A.5)
We define the o-fittration in the training process: Fo is the trivial filtration and
F. a e : ; (M)) for 2 1.
We also write E.[] E[- Fi..
A.1 Dynamic of the First Layer
Lemma restated. The first layer in local SGD satisfies that
|/ 2| sin d.t1 (1 m7de cos 2 | sin Φe 2n + 17² M2, He.
(A.6)
where d = 1 DN x-dt Ta T H. = || sin Φe+1 112 sin? 2e and
M1. = (v: - -7p
V oe L(wi at)) (I w (w))) Er, M2, = E._ (I w'ww") E..
16

---

Proof. Let i, 11 1 Ex= v Lww a;), then we have 8,-1= 8, 17E,- If follows that
N
|1 1|2 sin कe+1 = || [0++ 112 (oi+ 2w0)))
= 0 n/E: 11 - [ )²²² (n((5: u0 [0; (0,"0' w0) )- + (5r w²)²²
| (0, w0) )² 2n10 (I w" (w") (W")))E
"Ec + E (I w (w") )
= 1/0111 - (+) w² - 2 1p² M2,
(A.7)
N ΣN -- (a;)Ta" and (.2)). we can write
From the definition
2n 1|
0. w" v,'=' "" nnww)) TP.
P.
V
V (ww ai)
N
N
68 (a a
2a w" + n(w") (I-w,
w
2m
10
N
Φ (a)) T a"
||0 cos db + -/1//a/1 cos² 11))
π
N
2m
|1
| (cos 6: + =m s Φ1).
(A.8)
and
1
|6
||
r/Pr
V u
T( ai)
N
1=1
N
11
+
(at) (ai)Ta'' a-
(w")T (I w,w,))² w
N
2n
1=1
(88
|0011
+
NV
17
π
of
(at) a"
(1 - cos2 xz)
N
2n
(68
| 2 (1 + 172 X2 sin? Φ1).
(A.9)
where (i) holds since P,U; (ii) is true due comes from |w0 = 1. Combining A.S and (A.9). we can get
w. is idempotent matrix, and (fit)
|| 1 (ö, )²
+ 1/² X sin" oi (cos or 1/dx sin? db) 2]
||,,|1²
[sin? Φe 2mde cos di sin 2 Φi + 17² X (sin² Φe sin Φb)] ||
(sin² Φ: 2nAAe cos oe sin Φe + 17² X₂ sin Φe cos? Φe) ||
(1 217 di + n²² X cos Φt) 1 sin? のb
(1 n cos )²)² || sin dr.
(A.10)
Plugging (A.10) into
A.7
gives
16++1 1|
sin
Jz+1 = (1 - A cos 2.) 1 1| sin di 2nM1, + 22,30
where T. [M,] = O since Pt, G. E F, and [, = O, and M2, 2 0 because P, and I w0 (w+)) both semi positive definite. The result follows from the definition of H,
L
A.2 Dynamic of the Second Layer
Lemma 2 restated. Let A (1 aaTaa)²- (1Taa))) aa)(a" ap). For local SGD algorithm started with the initial point (vo, aq), the second layer satisfies that
2n 2 y
a a"
(1-
π
2 a a +
2x 7/ 1)
1 1-
1
Ao
k
2T
17

---

+
al1a212
7
Σ
1-1
1- 17
π
t-1-s 1
N
B + S(E0:-1),
(A.11)
2π
2T
==
1=1
where
S(co:t-)
112
1 17 2T
--1
1-1-850 8-
1 1- 11
π + k - 1 6-1-1
(ITT)(
2π ==0
2T
1-1
t-1-8
1]
Σ
11 π
c a²
2
==0
and
B = (g(o)) - 1) +
11
(1
1 1-11
1)
π
+ k - 1
8-1-1
(π g(ot)).
2x a 1
2T
1=0
Proof.
From
A.3
we have
N
N
1 N
1
La (w,, a²) = (11 + +(T - (T--1)1)
1
Σ
a
1
11
+
Σ (( - I a'
N
N
2T
N
1m1
iml
N
1
(11 T + +(T - 1)1) a:
11 T +
Σ
((ot) - 1 1) | a'
2x
2m
N
i=1
Let A, = (1 a1Ta2= - (1 a (1 T a,). By the definition of ac+1, we know
1 N
N
a_-1a' a'
(a (ait1) T a = =a a
1
V L(wl a me? a'
a
N
N
i=1
1
1|
π
a, a"
Σ
(( -1) 11a" + 2t
7 A, neo a', (A.12)
2x
2T
N
Fort t 2 0, we also have
A411 a1=a²²²
11-11 π k -
(1 (1Ta))(Taa)) az)
2T
-17 N i= ((0)) -1
1: + 1 N
(1 aTaa)² + 1 Taa)(
2T
1 17
π + k 1
A 1)
π N
Σ g(dt)
(1 aa²²²² + tn(11 (1) a)
2T
2T
k 1
[+1
711 )²)²
t
π + 8-8
1
1 17
Ag +
1 1-
1]
π
g(oz)
2π
2π
2n
N
π 7 -+k-11
t-s
+1 s=0
1
1)
(TTa)()
(A.13)
2x
Plugging A3 into A2.12) then enrolling
12 from timestamp 0 to L gives that
aT1aa"= = 1 11-1
π
1+1
ag
T a=
+
a/la" *
2
1
π -
N
g(Ot)
-1 -1)))
2
2T
2T
N
s=0
1=1
+
7 2T
a+1
2
Σ
1 n7 2x
1
1-83-1
1- 17
+ k -
8-1-1
N Σ 9(6))
1 N
2
0
1=0
172 t
1
1)
π
6- s-1
1 17
T + k
1) - 1)
2/1
8-1-1
(1 (aT)a
2T 0=0
2n
2
1=0
18

---

2x 2 bn-n(h+=11
f-g
1+1
1] 2
Eg a"
1 (1-1) 17
Ao
k
11 2m
0g a
+
1
2x
25-n [(
2--1(x-1)
1 (1-1)
11
Ao
2π
n a|aa*
112
1-1
1]
π
t- 1-8
Σ
N
B + S(Eo:t1)).
2π
2m
i=1
In fact, we also used the following summation result in the first equality
π T-
t-x
+ k -
2
2%
1
1
17 k-
1 17 2T
2x
1)
I-1
2
!]
π
2T 11 1)
2TT- n + 1)
1+1
1 - 1|
1
2m
2T
1/k
2m - n)(TT - 1)
2n 2n-n(k+ 1) 1+1
1
[+1
n
17 2T
k
A.3
Concentration Inequalities for the Noises
A.3.1
Sub-exponential Martingale Difference
Definition A.1 (Sub-exponential and sub- gaussian random variable). The random variable x E R is called expooeenii with norm || if
|x|| = inf { {2 1:0::.
[ $2].
In addition, the random variable x E R is called sub-gaussian with norm ||x|| if
||x 122 = inf { E
x 2)
Lemma 7 (Proposition 2.6.1 in (50).. Let Xi. Xn be independent mean-zero sub- uub-gaussian random variables. Then Σ X; is also sub- sabb-aassiin random vuriable with
N
Σ
x
1=1
V22
Lemma 8 (Lemma 2.6.8 in [0)). gaussian too and
If x is a sub- sub-gaassian random variable, then x E[x] is sub-
|x - E[x] S ||x||12-
Lemma 9 (Lemma 2.7.7 in 50 sub-exponential and
Let x and y be sub-gaussian random variables. Then xy is
xylle, & ||x|ealllyl
Lemma 10. Suppose (x1re21 C R are sub-exponential martingale difference sequence with norm
[|xxell la yo Ji21 adapted to the filtration (Fi)221, that is [[x O and ||xe||e> inf(s 2 0
Blelxil/ Fil < 2}. Then have
1
Σ
x,
log(1/8)
Σ
Xxs 1i3, clog(116) max |xal 15$51
S 28,
where is absolute constant.
19

---

Proof. Invoking Proposition 2.7.1 in [50], we know
[(xx((Ax:)
Fi] exp (c 2)21xx1111), if | s
(A.14)
Define
Mf exp
c= Σ x 1
follows from
A.14) that for any 2 1,
E Me Fi]
M IE
(exp \xx- c |FF S M1-1-
further implies that
E [M] 18 [M [i]]] - E M ..........B1 [MM S
Using Markov's inequality, for 0 < X v maxis 1i we have
P
Σ x, 2
Σ
Mr 2 8 5 X 12 + x [088(188) P
(A.15)
a=1
Now taking
c² log(1/8)
A = min
(1
Ei |xx.ll,, maxisusi |xs<lvi
and plugging it into AA.15) gives
P
|x 11. + cclo(1100) log(1/8) Σ
max 1845t
||x|| d/ 5..
#=1
Similarly, we also prove
2
P
Σ
x,
1
V
log(1/8)
Σ
||x 112. clog(1/6)
max ISast
||xa1l0r 56.
Then the proof is finished.
A.3.2 Scales of Sub-exponential Norm for Noises in Stochastic Gradients
For any (u, a) with w w/|l0/, we denote
(
K
ε(1)
Σ a (Z, wi)
a; 2
[ w 2 20}
Σ Z {Z, w 2 01 ]
Σ
cia(zz
-
Σ 0 (2, w 2 0)
E12)
Σ
aZ w0))
)
E
Σ
aij (TZTT"))))
Σ a; 211 (Z w 2 01
((1) = a (Zw) (a) (Zur) F. (Zw) To (Zw))
((2) = a (Zw) (a") o (Zw") - E | (Zw) (a') o (Zw")
Lemma 11. Let P =
1 |
(I wow T). The following noise terms satisfy: for f = 1.2
20

---

((e) (1) For any fixed vector u E R u (() is sub-exponential with max I| l Eeg)llo S cl(ui] max[||a]l ||a" ||
(2) For any fixed vector E R,, u PÉ(e) is sub-exponential with max || T PE S c||a|||a*|// |||||
Proof. Recall the definition of E(1). then we have
(c()) u u (Za) o (Zur)
E [[u' (Z))((a) To(
Applying Lemma yields
|uT (Zw) E |u TuTo (Zw))
Σ u (o(2) w) [z] w)l)
1/2
213
Σ |uy (o(Z) w) E [o w)
luyo [z] w)
(18)
|| | |
(6)
(A.16)
where (1) and (ii) comes from Lemma
and respectively, (Mi) holds since or (Z, w) is a half- 12/2, and (iv) holds due to ||//|| = 1. Combining (A.16)
normal random variable with variance |
and Lemma 8 we can verify that
|u o (Zw) 22 $ |ull,
||a o (Zw))ll S ||a]], [Taaa) (Zw) Iloz S ||a
Applying Lemma
9 gives
[u (Zw) (a)T o (Zw) (Zw) [u' a (a*) o
vi 24 21
oZw ||,0 laTo(Zuu) ||, x |
vi
uu o
(Zw |1,s ||(a') ToToo(( (Zw) < |u||||*|||
Invoking Lemma 8 prove conclusion (1) immediately.
Recall the definitions P
|aa (I ww) ). Notice that, for any fixed vector u E Rdd
Σ 0 (Z w)
Σ a.u PZ, [ 2 20}
Σ au PZ, 12, 2 03 ]
EE
a a (Z, w)
follows that
1/
P
1 x
Σ a (Z) w))
Σ a:u T P2Z (Z, w 0]
2
Σ
a a ? w
Σ
a.u PZ, 1 (z] w 2 0}
x ||a
12 w 2 ||
PP
< ||a""
12 ||||
12 ||
where we used ||ma||| arguments.
and
|||||
S /
The counterpart for P5(2) follows from similar
D
21

---

A.3.3 Corollaries of Lemmal
Let (oth20 be sequence of real numbers. Recall that & = N/ Σi Piș and c, = ΣE C/N, where (Ei and [EN] independent random variables given Fu. Applying Lemma 10 and Lemma IT( D) we can directly get the following results
ana T
- N
log(2/8)
aj
a [| V ||a)]l)
1=0
e
(2/g)
max
faillail (Ila") V [[aiil))
(A.17)
N
[M]
and
m1 El S
k 12g(22
of [I|aa1 ||iil)
cv k (2/(2
max
{ar (I|a*) V [|ail))
(A.18)
N
Is 15
Specially, choosing u = ej for j E [kt]. we also have
ck (kg(/))
|c, ~ k max
e c,
max iE[N]
(Ila'l (Ila")| (
(A.19)
jElk]
N
hold with probability at least 1 - 8.
Similarly, using Lemma 11 2), also have
a
s-1 N
clog(2/6)
Ei w
log(2/6)
| +
||a*]
max ||a
(A.20)
N ||
||
(E[N]
1=0
1=0
and
1| cd log((//))
||a 11 max ||a!]|?
(A.21)
N/
N
hold with probability at least 1 6.
B Bound the Weight's Norm during Training Process
B.1 The Scale of the Second Layer's Weight
Lemma 12 (The scale of the second layer's weight). Suppose the learning rate satisfies that
ny logooo//()))
cmax Tikk v log(k//))))
< 1,
(B.1)
N
for a large absolute constant Then for any 565 (1||a*|13)-2 we are guaranteed that
n1 log((1/0))
A 2 -cKay | < Kg 5|10*11
KE(N]
N
with probability at least 8.
Proof. Recall the definition at
1 ΣN a E, = N Σ ef and
N
1
VaL(wi, = 2T 111 + ( 1)1) aj
(11 + (g(0)) 1)
2n
22

---

Then notice that
N
N
1 N
V
L
(w Ei)
2
1
v
L
(wi ai)
+2
Σ
c
N
N
N
t=1
1=1
i=1
N
2
1
(11 T + (I --)))a
1
Σ
[11 T + (o(0)) - 1) I)a²
+ +
2πT
N
2m1
(k + --2 (Ia=112 + ||a*|11) + | 11?
x²
where the last inequality holds since ||11 + (T 1) + k 1 and g S x. Denote A, = (1 a,)²
(1 (1"aa"a))) Together with the definition of ac+1, we have
N
1
|a++1|| 1|
V Vallw, (i) {i)
at
N
-I|ael?2
2n 2
Σ
(V VaL(w, at) - 2na, E + n²
Vallwi, Ei)
N
N
kE|N]
7 N
=1|a|12
1 a,
11
+ (T - 1)I) a +
Σ
a
T
(11 + 1)
π
a N
i=1
1 N
2na T El 122
V L ( at +
N
i=1
1 N
1
rT(T= -1)
||ael1
7 Al +
7 - 1)
|ar||[a"| - -2na, T
+ n
v
VaL(wi
at:
2x
2T
N
7TTT= 1))
1+1
71( 1)
1
nT(T== - 1)
|a0|| 1|
Σ
1
||a||||a||
2x
2TT
2x
s=0
7
1)
6-8
Ag + 2m
t Σ
1
n7(T= 1)
b-g
a Ex
aTE,
π
2T
2nT
+ 21
2
77 1)
t-8
(K: -1)
(I|a, + 1=1aa112) + ||eal?).
2n
x²
(B.2)
Denote the event
& Vs <t: max iE(N]
|| S 651aa11
Let 0y (1 - 17 2
"
1
then it holds that Eizd of - Diz an -) 1) Using concentration
A.17), we have
2 log(1/0)
a,a 6s
I 1 n
a a=||a,1|(([1a" V max ||
N
log(1/6)
+ 1EE
max ax a5t
I|allla.1(lla V max ||a;]])
N
n (10((1
I 1s, 10c|la"| 122
(B.3)
N
holds with probability at least - 6. Applying the concentration inequality (A.19) gives
ck log(tk/8)
1 17
ar valler 2 < 1,,n" Σ
a
(I|a') V max [a
N
==0
23

---

50ckn log log(tk/0)
|a 11?
(B.4)
N
holds with probability at least 6. In addition, from A.11))
we know
E A, = 11
(1-7
Ag +
711 "aaa
1j
+
k
8-1-1
N
g
2x
2m
2T
1=1
8-1-1
+ 1)
π
(1 (Taa)((TT))
2%
1=0
2 1l
11
1
π +
k -
(1 (1Ta)((Tei))
2
1=
nk loggg(1/0)
k
8-1-1
2 11.,
(Ila*1 V max ||a)]))
N
2n
n log(1/5)
2 11.. 5c
(B.5)
N
holds with probability at least 1 - 6. Plugging B.3 we can get
[.4
and
into B together with & < 1 n (B.
ry log(1/10)
log(1/n0)
||44 1 S 1|00122 2 + 55|a"|1 1 + 5c|la 1|
+ 10c| a 11
N
N
π k
50cnk log(t/0
+ 4n
(25
||a))
||a0112
π
N
< 9
(B.6)
where the last inequality holds due to our assumption (.. and |aol| S ||a"|: ||. By setting = +t and K, = 5|[a"] in conclusion (1) of Lemma 15
we have
N
1 |ait1 ac+ill S 11.,
|
a'+2ll
N
j=1
< 11, 10 (2nl + on kl log(k/8)
< 1g 4||a"||,
(B.7)
where we used the assumption B.I). In conjunction with B.6
we can verify that
P. (E, illar-1ll
5||a" (1}) < IP (One of B.3
B.4
B.5
and B.7 does not hold)
< 48.
Therefore, we have
(E141) P (E, n {|| s 55(a"113)
2 P (E.) P (&, n (I|a:+1ll > 5||a*(1})
IP (E, 48.
Hence by induction, we can verify that IP (E.) 2 1 - 4tö for any t < (nK?)-> -2, By adjusting the level of 5 and P(Eu) 1 due to ||ao|| ||a"||, we can finish the proof.
B.2 The Scale of the First Layer's weight
Lemma 13 (The scale of the first layer's weight). Under the conditions of Lemma 12 Let Ka 5|[a"]|, we assume the learning rate satisfies
(1t v Vollog < 1,
for a large absolute constant c. Then for any S 1 (800cl) ( T) ( [og((Nd/8)K3) we guaranteed that 1/2 < ||r]|| < 3 with probability at least 1 5.
24

---

Proof. In this proof, we suppose the event Lemma holds and hide the indicator function every- where. To facilitate the technical presentation, denote ej i n af). Define the following event
Uc = SA8 (8S SISS (800er) - -) Nog(())))) : : 1/2 - |.,1 53).
Step 1: show || 2 1/2 under the event U1 From v, = N
Ei
di and Pi-10--1 0, we have
N
N
2n
| 1
11 11 N
P V
Vo
i 8 11-1 + 1111
N
N
2m
1
Pt-11 N
V V
(ū-11 61-1 + 1111==1111
N
N
N
+ 2n
U(-1 - PP
1-1
N
V w
N
1
(P--1 P
V L el-1)
1=1
1=1
N
+1/"
P - P V ai
1=1
27 N
1
2 1|11-1112
0 1 E1-1) 4n|1 11
P - V a
N
N i=1
227 P Wwl 1
1
Σ
P
P
N
N
(B.8)
where the inequality follows from dropping positive terms and the inductive assumption |0,-1| 2 1/2. With probability at least 1 holds that
[Pi_ - P.- = 1m
(1
1
(I
(wi_ 1
|0-ill (I wT - -w
||
1u4-1
1
1
|w0
(wo
w 1e-1 10
|0j
|ll
|
||
1,
114-1
1
+
2 w
1
w
Wi-1
1
|/
(0)
1
0
11-1
x 1
+ 4
112
|0 ill
|
|ل }
< 11--1
||
|1
+ |
||0|
-
12-1
4|
|ليياع||
(18)
2 "||1
0--1l
8110/
0/-1 ||
1
|
|
(iv)
10cn( VId + I) log( (oggNN/))K
x 1u
1/2 6enl( / TTd + 1) Tog( (Nd/))
(0)
2 1u-- 40en( Id log( k
(B.9)
where (i) holds due to ||=|_|||| = - 1; (ii) and (iii) hold due to the inductive assumption
| l1 2 1/2: ((v) follows from the conclusion (1) in Lemma 14 and (u) is true because 6cn( ( VId+
1) (Nd/)) < 1/4. Substituting (.9 9 into B.S) with probability at least 1 - -28, we have
N
2m
1u 10,01122 1
|v--1
G 1
25

---

N
1|02-1112
Vw
N
i=1
sotr: ||P--ll
Σ
V
L( ال
N
1: { (1- (1-800c7] + 1) 1) 1|00-111
21
N
N
1)
(it)
(1 80000) ( |l00l
1:--1
[-1
(1 800m)) (ogo0/++)))o((N((0()(( t-8
N
2m
Σ
So
1) llgloo(N//)))))
6
Σ (1 800c (VId+ + 1) Vlgg(o///))))))
-
==0
(18)
5
1
1um-1
0.36
nn 4
2n
Σ
[
200 I) 1og(NN)))))/)))
0 E.
NV
==0
(B.10)
where (i) holds because V T.wjj r < (aa) a*1 | S 5K2 by using Lemma 12 and P <
rll 2 holds under the event U:-1; (ii) holds due to ||ool = 1; and (in) follows from
t S (800cn) (d T)K3 (Ng((N//)))- such that
(1 8000) ( (VId+
1) (og((Nd
2 800cn I) log( (Nd/))K
2 (1 100 2 0.36.
In fact, the bound above holds because 800cT)² (vId + 1) lo < 0.01 and (1 - 2)² is decreasing in (0, 1). According to the definition of oj and Lemma 12 we know
N
1
12
14m- 23
T a
<3+5nk2
(B.11)
N
N
1=1
1=1
Recall that E,
N
P.g. Invoking Lemmas
11
and 10
we have
N
(-1
t-1-
N
124-19 9
Σ
10-800 200n)((TT (VTd+ + 1ogoo(Nd//8) (N)()
E.
N
==0
1=1
cTp (3 + 5nk3)
2(1 2(1-1-8) 1-8)
< 11--1
1 log(2/5) Σ
800n I) (oog++///1
VN
Kn log(2/6)
N
c33 + K2)
log(2/5)
knp log (2/6)
< 11-11
20 (og((N//))
N
N
c (3+ kTk3)
knk? log(2/8)
< 1:
+
(B.12)
NT
N
26

---

holds with probability at least - 6. Plugging B.12 into (B.10).
we get
5
c33 5n
(2())
kn log (2/6)
|
2 nlz,
0.36
4
Tnk - 2
+
20 7og Tlog(N (dd/8)
N
N
2 nl,
0.36
16
16)
1
lu-- 4'
(B.13)
where the first inequality holds since VIdlog 2
Step 2: show || I 3 under the event 1--1 From the update rule of vj and vs = N E 1/. with
probability least 1 6, we have
1 |/00|12 144-1
U
P
1-1
N
1
N
V w
L(w
ai
2n
N
N
1 + E1-11
1=1
1=1
+ +2
11-1 ppp
1-1 N
I
[
ai
P
P
+ 11
(P 1-1
P i
V I (1
N
1u--1
1|01-111 +17
P V Vi.iVL((ur L(w (w
N
21
+
112
Σ
P - P - ||||| V [. 1/
3
N
N
1 N
+ +27
Σ
Pt- Vw oi-))
Σ
P
- P(-1) 1.
N
N
N
271 N N
+ 17
Σ (P-1
i 1 Ex-1) -
N
(18)
(1+5m) max P - -P--1l) |10 12 + 2517 K + 25n/² K max |P
PA-1ll
25n2 Kt
N 2n
+ max | - ?|-
+ (1)) 11
N
(38)
1:t-- {
(1+20000) [1+200c7((VIdL IId+ I) [/g
112
25
+ 1100 + x [Ioo++(////(
27 N
Σ
E +n2 n2
1n-1 { (1+ Dog0oo// alllllll |la1ll
Σ
11+ 2 () (Noo(NN//))
+
1-1-8
+ 2m
[ 200c7) 2 V/ggo///////////////
Σ
==0
i=1
27

---

Σ [1 200cn) +) /)ooo)))////// Nog(Nd/))) 1-1-8 ==0
11E.11
(B.14)
where (2) comes from 1 0 and |
<
3 under U (ti) comes from |P 1| S
1/1 S 2 under 14=1; and (iii) holds due to B.9
With probability at least - 6, we have the
following concentration
1 + 200c (VTd 1) (oloooN/No)K3
11
am0
dndd (1/10) K2
Σ 1 200cr)((Tdd I) (ogg(NN//)K) 1-1-8
I 1:-1
N
400c7 d) \og(N//)))
andd (
$ 1u-11
400cr) d) /lg(
- ce (llog(1/10)
(B.15)
N
where we used the assumption t (400cn) ( -1 Similar to B.12 we can also guarantee
N
Σ (1 200cr) (1/ood+)))oo(N//1// 6-1-8
11 11
Eo
onk' (3 + 5m/33)
log(2/0)
Σ (1
(voo) 1) (oggo(/8888)))1 2(1-1-8)
VN
en K? (2g8)
N
ce (3 + kmk?)
+ k log (2/8)
$ 1u--1
(B.16)
V(I d)N
N
Plugging
B B.15) and
B.16
into B. 14
gives that
10en + 2ce log (og(L/m))
ce (3 + 5nk3)
cnk log(2/0)
1 1,12 < 144-
+2
V(Lvd)N
N
< 1 9,
holds with probability at least - 38. Together with B.13). we have showed that
P ( (1/2 ||w.1| < 3}) 2 P (M1-1 IP (24- 1
fll s 1/23)
IP (4h-1 0 fll 3))
2 (14-)
(One of B. B. B.13). and Lemma 12 does not hold)
P (One of BB.14). 1515).
B.16). and Lemma 12 does not hold)
2 P (4 86.
Using induction and IP (24) = 1 due to ||vo| 1, we can prove the desired conclusion by adjusting
the level
Remark. In the following proofs, we use to denote the absolute constant, which does not depend on any variables of the model or training process. For conciseness, we do not distinguish the specific value of in some contexts.
C Bound the Discrepancy during Training Process
C.1 The Discrepancy in the First Layer
Lemma 14 (The discrepancy in the first layer). Denote O max,, SIST |al - w/'l for
< T < t 1. Suppose the learning rate satisfies the conditions in Lemmas 12 and 13
28

---

If fmaxi || S Ka holds, with probability at least 1 - 6, we have
max 0 S cnn 1l (JE[N]
In addition, we also have
Kaj a²) a'l S cnj(Vll Vil 1
max
SIST
Proof. Denote the discrepancy term by
h P. V L(w at) wWVLLwW ai)
π of (at) Ta
π of (a;) a
(I w/ (w/)
(I - wixi
w.
(C.1)
2m
||
2x
|
Since ||w=|| || = 1 and ||aj||
5K, in Lemma 12
we can bound h as
|0b/ oi (at)
a
--
&e (a)
ag)
a
of
|
(a/)
Ta"
2
|0//
2π
2x
|
||'|||
+ n - 1f (at)
1
1
||
||
||,|||
| - w/'l
||
u
s 3K3 + I(a ) T aal + 6k2 29 5k
|
2/
|| 2o
S 3K2 + I(a a T a=1 10K oj v/ll.
(C.2)
where we also used the fact max
I wj(wi) T|| S and
"w" "To"
wo! (w!) Tuo w
< ||2a/ (w) w! )
"w=""
[1(w)
w! (wo?) w='l
w w!
|0
||>>|
From the definition of B and B Lemma
we know for any i,j E [N],
17 (1 aa)a² s-1
+ k:
8-1-1
B¹ B3 S [g((2)) g(
Σ
1 1
g(0))
g(oi)
||a1|2
2T
1mt,
< + a)) nI
2
a 1
where the last inequality holds due to ((Ø) E [0, T] for & E [0, n]. Using concentration A. and I S kn with probability at least we can guarantee
SS (S()).1111)
7 Ti a
Σ
s-1
2n(
1-1
1)
π
+
1-1-m m
(1 6m)
2x
2
|=
m=
2T1(T - 1)
8-1-j
+ 1
Σ
C a"
jutt
log(2t/0) 0)
a
217(T 1)
< <cnlV
K²
1
+1
N
|
1=t.
k klog(21 (2t
< $2cn!1
K2
(C.3)
29

---

Using the dynamic of a, a" in Lemma 2 with probability at least 1 - 8, we also have
(a/i1- 10--0 -ai_)) a
n/
t-2
π 1
1-2-5
(B. - Bb) + s(e(..t-2) - s(e)
1]
2T
s=t,
17/ 1/||a* I12
n (1 a a²)²)
+ s(efx:t-)) - S(Eina-2)
+
2T
2 |a012 1|2
n
n/
1 2π
T| a 11
+
(1 )²
+ 2on kl log(t/6)
2
2 2n)( Vkl + 1)2 log///////////// (1/1))))))
(C.4)
where the second last inequality holds due to the concentration
C.3
Plugging
CC.4)
into
gives
||l| - s n
Σ
h
+
Σ s=t,
P.E. P!E!
s=1,
t-1
S 1 Σ
(3K² + K(a -o2) a01 aa11+ 10 o2ll) +1
Ta)Taa'
Σ
P
+
Σ
P
1 nI 33K3 + 2n(1+ + VKI)K2 + 10K30%11 + 4oT///
(C.5)
where we used the following concentration
P.e.
S Va
(PP: S logg/
max
max iE[M),te(d]
Taking maximum on the left hand side of (C.5) over b, S S T, we can get
RT $ (1 10mIK3) n/ (3K2 2m(I + VkI)KK) + 4cn (og(/8/)
I
2
V (log(Nd/5) + +4e) n [od/log(N//))
4e
2 5c + w//5) ny (o
where we also used the assumption n(I + VkI) 1.
C.2 The Discrepancy in the Second Layer
Lemma 15 (The discrepancy in the second layer). Let 2 = m ||a
at || for
t, < T < tr+1 1. Suppose the learning rate satisfies the conditions in Lemmas 12 and 13
[ax, 1 - 6, we have
aill S Ko holds for Ka ||a" and enk1 with probability at least
maxEMy 1J
s 2Ka (2n1 + enyy kl log(k/6))
Proof. Recall the closed form of V VaL(w, a), then for i,j [N]. we have
Va VaL(wi, at) VaL(wf, a!) (11 + (TT 1)1) (a: at)
"7
(o(ot)-9(e )(0)) a"
2
2π
Let f, be the previous synchronization time before t. Using the fact ai = a/_ = a.,, we have
||a] af nn
Σ VaL(w', at) Val(wi, +
Σ E e!
e=t,
30

---

17(
+
1)
t-1
||a] a!ll + na(a01
Σ
x-1
-
+
Σ c
[-]
2π
2x
s=b,
ạ +
1)
t-1
a|1a"1
||ay a!ll +
II + cv kT log
(C.6)
2n
2x
s=1,
where the last inequality holds due to Lemma 1). Taking maximum on the both sides over ty S S T, we get
E - 1 17(T k 1)1
InI
||a"l || + env 1k)
2x
2
s 2Ka (inI + log(k/))))
D
Self-correction of Signals
Recalling the dynamic in Lemma 2
2
T a, a-
17 π - 1
ag a"
1
2x-
1 (1-7
-
1
Ao
2
k
2
111a"11 1|2
6-1
1-1-5 5
1
17
B S(Ev:-11),
(D.1)
2
2
N
where
B -(=0) - +
(1aa2)2
Σ
8-1
1 1-
π +
( 1T-9(67 g(6)).
(D.2)
2π
||a 12
2x
1=0
Using concentration (A.18)
with probability at least - 8, we can guarantee
1121 1
211( -
k
1-1-m
max (S(Ee:t-1)
max
Σ
17 2T
(1 (m)
2x
1=0
m=0
2m(T
1-1-j
E e,=a"
+ 7
1og(2/8)
1 a
[-1
27(
1-1-1
$ c
K2 max
n
|a+1|
+1
π
n/ (2/0)
s 2cv
K²
(D.3)
N
For any 0 8 Ö61 2) and any E [N]. with probability least 1 8, it holds that
cos o. - cos =
(v])
V._ 20"
|
|/a/l|
1(0g
U.)) "rn
VA
+ |b_ w='
||>|||
|
122
|0 V. ||
| Dzll
|
D
v.
(6))
K TT + 1) (ooo)o))))
1/2 - Kn ( Id + 1) (od(8))8)
31

---

S 12cn I)
(D.4)
where (i) follows from | = and the triangle inequality; and (it) holds due to Lemma 14
Define good event
Egood = N
(D.5)
where
11 log(2/0) K2
En
max [5(Ent-1)] & 201 t20
N
E1
ie (e(N)=550(m (a')
max
(a'm) a'l S san
+ vhli log N/no)K
7 log(1/n0)
E2
max
Σ (Emw" + =n=w") S V
8 s50 000 5005+
N
E3
max
cos cos S 12mn (vTd+ T) Eovllg(NN (Nd/6)
iE(N),0SO( 2)
1 1og((1 /no))
max 05r50(n
||a=|| < Ka:
min osršn,1
A,
N
According to Lemmas
[4 12 and relations
D.3)
D.4.
A.20
we know F (EE) S 8 for 0 - 5854. 4.
D.1 Self-correction of the Second Layer
Theorem restated. For any initial point (Va, ag) with Φo E [O, we denote Ta inf 2 0
a, a }o the first time, where Ta k(m
16(m- 1111
Under Assumption
if
yk
a 1|
ck2 Ilg (dkk/) max n +
1.
(D.6)
N
a
for a sufficiently large constant c, then Ta & x0(17-) with probability at least 8.
Proof. We first define sequence of events
16(x - a²)² k(π + k 1)
A = (vs tt: a_aa S TaF,
where Ta
Notice that once show for some O,
P
a" < 7a1) 5
then we can conclude that TP (AA) < 6. According to the definition of Ta, we can guarantee S T with probability at least 8. For simplicity, we introduce the following stopping time w.r.t. the angle & during the training process,
T (6)
inf (1: Φe 2 o) for E m)
120
Define ø and T" such that
144T
(1 2²)²
cos J
k log(4 4 + k2),
cos D" cos J..
+ t
Choose 30 aarcoos(155 such that cos /² 1/5 cos 30 due Assumption 1 such that
(1 12²2² < K(т + k 1)
(D.7)
720 log(4 k2)
32

---

The correction condition
G is equivalent to
(1 32( 1)
π --1 (1 a))
> 1.
(D.8)
k
k -1 a 1
We denote
2 T- T n,, n
2g > x +
Z3 (==00)>~((11) + 113
where 71,1, 71,2 and T1,3 deterministic and will be defined later.
Initial region: (0, o)). For any S min (0"), Ön })}. under the event Egood it holds that
cos o 2 008 O.
cos &3: COs dsl
2 cos 6"
12cn K2 (V Id + l)/log((Nd/))
C0S d
10
Since g(-) E [0, is decreasing in [0, m). plugging it into D.2). we can get the following lower bound
N
1
B
(o(
2 (0.46T) 1,
N
Under the event Egood, using the lower bound of Ao in B.5 for min (T-(6))0(11-)) we can guarantee
1|| (00(0.66TT))
-1
7 1)
π T k 1
a, a" "1|la"
1
11
2x
2x
2
==
- -11a"11
1
17(TT - 1)
2
17
(2/6)
K2
2T
N
9(0.46T))
-1
7, 1)
|1a111
1
π
1
2T
2x 2x--n(kton
1
2x 2 -1)
- 1| π 1
[g(0.46m)
1] ||a1|
k
2x
|| (1- 17( - 1)
n/ (2g(2/0)
201
K2
2xT
N
Here we take
π log
4+ 4(T 1)
1T
111
<
log (4 + 20(m 1)),
(D.9)
2x
(0.466)) -
2
where we used the fact g(0.467) 1 > 0.2. Since TI.1 1 < Ö(n 2), under the event
n11 - < (50) n Egood, it holds that
(g(0.46m)) 12
ni log(21/0)) K2
a" >
-201
2(T - 1)
N
( 0.2(1 a²)2
npp (oog(1110)))
201/
K2
2k(T 1)
N
33

---

(1) 32( 1)(1 T a²)²
ok 1og(21/0) 201
N K²
k(āT k 1)
(10) 16( -1)(1) =1)
Yaa
kiπT + k: 1)
where (i) holds due to |a 2 1 a- all/Va: (it) follows from k 2 320( 1)²; and (iti) holds due
the assumption (D6). We can conclude that
P - T- (09) n fra n11) s (1.1-1<<-((0 n ffat a'
a's d'sna))
SP {( -1.1-1<=-(00) (E6
< P (Eg UE3) 28,
(D.10)
where the second last inequality holds since
F1J - 1 <5)) s -( n Egood {a a" 2a3.
such that
{n1-1<<-(09) n fat, a' s saa S f n good
If .1,1 2 2--(0%). we regard (0- a ( as the new initial point and step into the analysis of the next region.
Initial region: 19/x/22, Denote to = (o)) From now on, we assume the event 21 happens and hide the indicator. Recalling the definition of h,, we have
N P.
| S
P V at)l
N
1=1
(i)
1 N
x 24en( Id I) 1og(
IV L( a;)l
(10)
$ 24cn
(D.11)
where (i) holds due to addition, we also have
B.9 and (ii) is true because | Lww, ai)l S ((a)) a'l S K In
4
T w0 v.
n0
11 N
1
Σ
PiV nn Lwii Z,)
1=1
5 00 11h, w
v. w" 1) P
w Lww, ax) E w" nh, w²
N
v w" +
n1
(a))Ta Ta" a" sin or nhh "" - -nE. w..
(D.12)
2π N
|0 ||
i=1
Here take
1 2π log
20( + a 11
1 2t log(4 + 1:2.
11.
(D.13)
17 π
)² (π - /(T/5))
17 क -
For any to < < - 15 to
71,, under the event A 7 Egood, invoking (.12) guarantees that,
cos d.
0/1
T w0
17
ii (a Ta sin" om n Σ (TT"w"" + & w.T="))
|
2T
[mm] ||
m=to
34

---

(
8-1
5-1
S 20os Pio + +2s177a + 2n
Σ max a (a/)² ( TTal +
a=a1+ 2m
Σ m=to
(S ur + h w0))
m=to
(6)
2 20os $io + 27/ + 20T1,27 (T + vhT) /lg(11 (1)))))))) + 2n max
Σ un + -h w²) +))
05T5T1.1
m=r
(()))
64
(1
4
S 2 cos 80
log(4 + +2) +
log(4+ + k2) on(1 + VkT) 1og(1///()
π x+ k
π T-1
4T
+ π 1
log(4 (4 + k2) .24mn Tdl + T) Voggogd////
4T log(4 k2)
1) glog( (Nd/
+ 2cKa|
π
((v)
12 1) (1 a²)
cos 3"
+
log(4 4 + 122) S 3 Ō"
(D.14)
π + k
k
where (i) holds due ||2 2 1/2. || 2 1/2 and the definition of A:-1; (ii) comes from
to S T1,1 and &1: (éii) follows from @to 2 Φ¹, and Ezi and (iv) holds due the assumption (D.6) Further, under the event A,- Egnod, we have for any i E [N] and lo S 8 S L - 1 S lo + 71,2
cos 0²= S cos go + 12
(VId+ (VVdd I) (og(())))
4
I 4os ~0
< cos(TT/5)
5
Under the event A n Egood n ( - to 2 n22. it implies that for any to S 1-15
to + T122-
1,
1 N
N
8-1
-
π +
(a - ((oه)
- 7
N
N
2m
|a 1|
2T
Y=1
1=0
π - ( /5) (1 a²)²
π + k 1 17
1
1 -
π + - 1
a 1|
2T
Together with (DT and D.3 we can guarantee that
28-n( t-to
to
1
1 8
a. aa=
(1 1 (1-1
π 17
a
T a"
+
2
1 1-11 11 2
Ato
2π
? aa 1|2
1-1
1
1-1-8 1
1 17 2T
B + ((1p:tt-1)
2T
N
==to
π - g5 (1 T )²
t-to
1 - 1) π
2
1
π - 1
π + k -
2TT
2x (x 1)
6-
t-to
(1Ta²)
2n - (( 1)
1 - 17 π
[T --- 9TT((//5)
k
2TT
π + k 1
1 1/( - 1)
1-1o
T7K (0g(
51|a"| 1|2
201
K2.
2t
N
Choosing t f= to + 21,2, it holds that
3 - 9((5/) (1 (1Ta²) a²
nhe log 1/nō)
3eV
K²
4 π 1
π + k
N
π g(T/5)
(1 a²)²
4(7 - 1)
π 7 k 1 0.5 (1
4(T 1) π +
35

---

16(x 1)(11a")) a²)²
k(T + --11 = -a
where we used the assumptions
D.6 and k: = 320(x= - 1)2.
Recalling that 2g - (-/2) (09) + -1.2 hence we have verified that
P PZ nTo > 11, + x2
z n 22 n {T.O > r + tm2)))
PP 2 n 22 A (6 (1 { a a a" S sra))
<
IP Ar (6)) T1 ggood S 58.
(D.15)
If T1.2 2 (T/2), we regard (v/2( a2_ a-_ (2 as the new initial point and step into the analysis of the next region.
Initial region: 1x/2, )"). From now on, we assign tu (TT1/2 and consider the case
{ (09) S T1,1
} n { to < <~) + ) Take
1 2π
24( 1)
2π log(4 + k2))
31,3
17 π -1 log 4+
(D.16)
Sa
π
where the inequality holds due to our assumptions k 2 320( 1)² and D.8
Similar to D.14), for
any to St - 11-1 1 Ö(n ?). under the event Ar-1 n Egood we have
cos o.
T w== U
+
7
N
s-1
π
H (am)) T sin" pm n
Σ (n w + ET w))
|ua1|
2x
N
m=to
m=
(1)
I 2T 20 2 (T
VkT) Mog (og(1//0))K3 2n
Σ (ET w0 h w²)
max +
(6)
64
(1Ja")
4x 1og(4+
log + 1-2) on(1 kT) v
π + 1 k
+ - log(4 +
6π
log(4+ k3).
2 1) llg((Nd/o) + cKa
n nlog(Nd) Ndd//// d/nm)
N
128
(1 )²
log(4 4 + k²),
(D.17)
+ k
k
where (6) holds due to or 2 //2 and the definition of At-1; and (ii) holds due to 1-7 2Ō(n = Under the event Ar-1 n Egoud, we can guarantee that
max cos 03 S cos 0. + max |cos cb. cos Ø'
128m
aa))
log(4 + k2) + 12cn (VTd+ (ogoo((d//)))
π + k-
k
144m
(1 aa²)2
k log(4 + R22)
π + h --1 1
cos Ø².
where we used the assumption (.6).. It implies that min; 0² 2 T under the event Ar-1 n Egood- In addition, we notice that cos ø¹ cos S² which implies @f + Φ" and sin ø sin क Under
the event A!- n Egood n {l - 1 < min(T_(0")) (()- for any a S tt - 1, we have
1
N
g( +
1 (1 T a x) Σ
1 1-
++
2
1)
8-1-1
(1 -(00))
N
2x ||a 1|
I=fo
36

---

7 (1 )² 8-1
8-1-1
2 20(0")
Σ 1=fo
1 π
+
(1 (1-0(0))
2x aa 12
2T
Tpe
π + k 1
8-1-1
2 2g(6") +
1 1
(1 (1- o(
2
2T
t=
=((0)) + 1<1 )(
π + l 1
1 - 1
k
2T
2 g(0h) +1 g(
(TT 0²) cos @" +sin @" (π - - cos Φ¹ - sin Ø¹ +1
(2TT 2² 3 cos 6t +1
144 )1)
log(4 (4 + 13) + 120,
(D.18)
where the last inequality holds due to the condition
(.7)) Together with the definition of B,, we have
1 A
N
1
N
- +1)+ 17 (1 aaaaa)²
π -=k-1] 1)
8-1-1
Bi
(o(o))
1 -
(aT s(oi))
N
N
2π aa 1|2
2%
i=1
2=1
1=0
(1 )=
+ ki 8-1-1
2T ||a, 2
17
2T
(T 11-
1=0
π 1
(1 (1Ta*) aTaa)²
π 1
(1 aa²
+
1-
k - 1 |a+1 1|2
π + k - 1
||
2T
We know Sa > 0 due to the condition we can guarantee
D.8.
Under A Egoodd nft- min(f_(d"), ((n) ?)}}.
Sa |a
7 1)
5K2 1- 77( 1
ag a"
π
2T
2T
2 -1)
nlog(1/mp)
1
1
8 [TT a))
2cka V
1 1- 1)
N
2T
π +
Salla")) 112
(1- 7( (((T-1)) 1
[6] + Sa Salla*|12)
m/e log (0gg(1/1) (1/16)
2cKK
π --
2T
N
where we used aa1 S ||a*|| || Kaa = a1 Now let t = to + T1.3, under A n Egood n tto -
a-1
11.3 -5 ( we have
3 Gall aa 1|
2ck 2
a1 a
4 π -
N
24( 1)(1T T a )²
n/e log(1/0))
2cK2
1iT + 1)
N
16( 1)(11 aa)²
Ta
(D.19)
kiT --
where we used the assumption
D.8) and (.6)). Since Z3 = to + T1.3 - - (ō")) we have
P (2 0 25 Za {Ta > TI.1 + T1.2 ) < 58.
(D.20)
(T + T.. (that is 2g), we regard (v, (ā a (5.)) as the new initial point and step into the analysis of the next region.
37

---

Initial region: 16", T). Now we assign to = (m"" and choose 71.4 = 71,3. Recall that cos Ø" 144m
I log(4 + 12). Similar to what we showed in D.17). for any to S S 1 - S
lo + 71,4 - 1, under the event Ar-1 O Egood, we have,
cos 0g =
||u51|
too
T w
+
2x N
1
Σ
N
π
|/mll
O' (aim) a sin" pm 1
Σ
(h w + E 200))
1=1
m=to
m=lo
1
COS Pto
Σ (ETw + h m/)
7, + CTI,1 (I (I+ V(T) /lo((k/m6)) +
||val|
m=to
VA
008 4
36
(TTa))
log +
+22) k2))
|u51 ||
3
+ k --1
(6)
4m
(1 )²
log(4 [4 + k22)
(D.21)
π
k
k
where (i) holds due |/ |l < 3. Φn > n/2 and the definition of A 1: and (ii) holds due to
|/all S 3. Applying the bound cos 0. cos 0y in (D.4) and the assumption D.6 we have
max cos of S cos db + max cos O. cos d'
8
4m
log(4 + b2) K Dogoo(Nd/)) So.
x + -
which means min, 03 2 Z. It follows that for any S. 1,
1 N
B
1
(o(ot) -1)+ 17
Σ
8-1
17
+ k k-
8-1-1
(T g(oi))
N
2 ||at 112
2T
into
1
)
π + k 1
5-1-1
-1 +
1
(x -1)
N
2T ||a 1
2T
1=1
Into
π 1
(1 )²
π +
= Sa
1 1
(D.22)
+
k
|| 12
2T
Plugging D.22 and D.3 into D.I. under the event Ar-1 O Egood, we can get
Sa 12
1 (1
11 - 1)
(1 77( 1)
a a
|aj aa1
π
2x
2x
2xx - n(k+ oT 11
1
(π 1)(1 (1TTaa) at)² π
2x n( 11
1-1
1
π 17
k
2
+ k
Mn log (1/10)
2cK2
(D.23)
N
Plugging = to + T1,4, according to (D233
and D.19,, we can guarantee that or,, 2 x/2 and
})
PP
2g
n
29
Ta
1i.
S 55.
(D.24)
q=1
Conclusion.
Combining D.10),
D.15
D.20
and D.24
we have
4
Ta
Ti.a
P((Ta > Tua n
Ta
Tha
n z
9=1
q=1
48 +P
Ta
T14 0 2f
n Zz
+P
Ti.g
0 21
nzg
q=1
38

---

3
(P((T0
S 9. P
Ta Σ
1
n 2
n
+P/
+P
n 7g Σ 9=1
n2in 22
q=1
140 IP
n n21n
n23
$ 196.
Therefore, we have proved S <E²= for other initial regions can be obtained in similar arguments. From the definitions D.. (D133) and D.16), we have
71,4 with high probability for Φ0 E (0. The conclusion
1,.9 2 17 log k.
D.2 Proof of Lemma
Lemma restated. Denote T" = arcoos (-
(aTa')² 144x x E
log(4 + 12)) and
5 min { sin 6" So sin @u do>g", sin (N ((20) a 113) A 1))
Under the same conditions of Theorem
If the learning rate satisfies
clla"| 1| Vlog max n( n(Vid+
1
(D.25)
N
16k
for large absolute constant >> 0, we have sin Φr, 2 15VE
with probability at least 1 - 8.
Proof. If Φr. s S", the lower bound trivially holds. Next prove the lower bound for sin or. starting from the last initial region, that is do 10" x). From D.16 and T a²1 ||a*|], we know that
16(T - 1)
1
16(x - 1)
T1.4
log
4+
log 44 12 1
< log(4 (4 + 122).
17
Sa
17
k(T+k- 1
Let C
log( 2222))
then 20 S (1 + 222)
S 2k. Denote wa = sin J21
do <du + sin do 202gu.
4
From the definition he and B.9
know
N
1
||
<
p - P. V. L(wi, ai)ll S 50cn(V/dd D) (os//og(NN))))))
(D.26)
N
1=1
where we also used V - (ww a;)ll S 5K? Recall that ē. U. 17/1-11 then it follows that
|||o sin 3, |0,11 sin? de
/11 || - ((0, w²)= (o, ===)²)))
= [( || + [[xxl))
||w,|))|| + ((0, w01 - 10, w=)) (1ø,7 "n' |I + [os w w=
< 7| - wyl + v;) T
< 14
(D.27)
where we used variable
|| < 3 in Lemma 13 and
| < ||wel| + h/ll < 4. For any I, we define
o¹ S π ( 2003 11 {1)
T((Ka) = sup
min [E[M]
(D.28)
05.5t-1
39

---

If To (Ka) does not exist, that is min 0² > ((20K2)- A 1) holds for any 0 s 1,
we let To (Kaa O. Then for any (K()) S S 1, we always have minke[N] O² >
((20K3) A 1) such that
0
(a')
a
1 77 cos @ = 17 05
N
2π
|ty1
1
(aa a
2 1 - "
N
2T
(20K") V 1)
|u,1|
(i)
5
7
1 11 2π
(D.29)
(20K V1)
Without loss of generality, we assume arg min & (K.))
1. It follows that
sin (K.( 2 sin (k,) (sin' (K,) - sin" o (K.))
02 2 sin" (x.(K.) - 2 cos (r((K)) cos x (KK))
21121 (((a) Vr.(Ko))l 21|0= (k.))l
2 sin² (Ka)))
|
1 10 (kk))
sin ( ((00 ^ 1)) (onn(VTd+ T) (Nd())))
sin 2 (π (200k))- 11)
(D.30)
Notice that if S 4C/1, we have
(1- 77 8) 2 1
2t
1) c
2 2 2C
2-2
20 2 2k
1
(D.31)
8
It holds because n/8 S and f(x) (1 1/2 is decreasing in [0, 1]. Invoking Lemma I know
||o 1 sin o.- (1- (1-nde-1 cos 1) ) ///011 2 sin? Φ. 22 + M2, + He
17) 2(t-re(Ka)
||,,,(K.)]] 11 sin" (iinnn((())))) -2n
Σ
(1
!? 8)
2(1-1-0)
(M + 7| h,ll)
smT((Ko)
1
7
2r 1
min { ssin (r,(),,) m - 2n1 Σ
(1
77) 2(t 1
(M1 + +7 h,1
8
8
"mmr(Kaa)
(8)
1
sin? 2 [ ((20K2) -1 ^ 1)
1
min
8
4
! 2(t 2(t-1-8)
140cn( VId + 1) Ioooog(NN/6))))
2n max
Σ
M1.
0STSt-1
8
(158)
1
1
sin2 T - ((20X3)
-140ey( Vld 1) (ogg(Ndd/)
2k
4
min
2
wi
12cK21)
(3 + (3+5nk?) knk²)
log(1/np)
t-1 N Σ
11
2(1-1-8)
N
8
(t)) min (sin [TT ((20K)) 1)] R
25k
where (1) holds due to (D.77) and (D.29; (Mi follows from (D30 and (D266): (Mi) comes from
D.31 and Lemma II and (iv) holds due to the assumption D.25 Plugging the choice of C
40

---

log(1 + 242) together with ||12|| S 3, we can prove the conclusion
min {sin² [Tt ((20K2) A ^ x
2 225k
sin TT.
225k
D.3 Self-correction of the First Layer
Theorem 2 restated. For the initial point (No, ao) with ag a" 2 Ya and sin @o > 0, we denote
To =i 2 0::00: on S J. where cos T+k-1
144 (1 (1"a')² log(4 (4 + k2). If the learning rate satisfies
clla") 11 (PVVoog (og((Nk/// max { {nlvid+))
S sin Φo.
(D.32)
N
for large absolute constant it holds that TV 0 probability at least 1 - 5.
A2
and a a 2 7a/32 with
sin
Proof. Find D E x) such that cos of x+k-1 aIaa'
log(4 + 12). We introduce the following stopping time w.r.t. the angle & during the training process,
(Ø) = inf {t: oe S of 120
for E m)
Initial angle: do (Ør, r). For any S (ōd).
under the event Egood, we have
cos 0² S cos Φ. + coos of - cos @5
cos Φc + 12cn (VId + / llg(NN/8)
a )²)² log(4 + k22)
(1 12 log ( + k2) 0.
π + カー
means that 03 2 2 holds for any 0 < $ - min T+ (0)), (0(n-2)) As a consequence, we have
1 N N
Σ
B
π - (1 a²)²
1 - +
+ k: |
2x
1=1
Notice that if 1
1 2x
we have
1-
π
1 - 17
2 1
2 4'
2TT
2x
which holds because 11 2
1
< and (1 22/2/z2 is decreasing in [0, 1]. Ift 2 2r m-
also have
1- (1 11 2x
2 1 (1 (1-1) π -
2 4'
because (1 - /// <e- for E [0, 1]. Together with the dynamic
D.I and ag a 2 Yas under
the event Egood, we have
Sa Salla*1) 112 2(T - 1)
17
11 -k1-1117
17 201 N
mlog(21/0)
a
K²
2x
(π - (1) (a)a)))))
(1 (1-
77( 1)
+
%a
he + k
2T
(6) 32(T 1)
(TT 1)(1 1)(11a))²
a2)2)
log( (1 1/18)
+
%a
k - 3e0
K²
4 k(T + -
4
N
41

---

(66)
7/
(Ta-
Na
30V
1k log(11 (1/n))
K2
16
N
(11)
Va
(D.33)
4
where (1) holds due to (D8): (ii) holds since "a 16( 1) and (iii) follows from the condition
k(7+k-1)
D.6..
Under the event Egood, we know for any S min (T+((1 ()]
(at) a 2 a a- |a a" (a a"
Ta cKanlvIk I) /lo((//))
4
1(T 1) cKKnnvVTk (lg(k/88) k( + k 1)
Ya
(D.34)
8
holds with probability at least - 6. Recall that ö; - = 17 then it follows that
|1 sin 5i || sin 0i| | 2 - 10/12 ((0) w²)² - (2, w=w")" )²)
12 h1-1 + 1 2 2n w") w²))(( (h w-) 17 1 120
S 27 |o! (I - w² (w ) h4-1 + +1 h (I - w" (w") h
wwww"))))
S 2n ||(T =w"(w)) will h + 1 h (I w0 (w*) hi-1
@ 2n (v, (I- - w² (w" )T) (?(r)) v.))
1/2 h1,-11 || + n/ h (I - w² (w=) hi-1
21y (I 1 (v, w )²)
)²)1/² 1/2 |12,-11 + r/ h (I- - (ww")) hi-1
( sin dx // ||| v h
(D.35)
where (i) holds due to - w (w=) is idempotent; and (ii) holds due to ||o0|| = 1. Invoking Lemma and (D266). for any s S t < min (0') (0)(((n))))))) under the event Egood, we can get
1u 2 sin" d. (1 1//--1 cos 2 1 ||,-- 1|2 sin" dh-1 M1,-1
11² M2 ||0,11 sin² Φh. - | 12 sin? 2 Th
0. 11 sin" Φ,-1 - 22,
6nl 1o- 17² 11,--111
1,8
s-1
N |/ 12 sin" do 2m
Σ
M1.1 11
Σ
(61lhil] + ml]ball?
1=0
1=0
sin Φn
-24cK, (3+ + 5n (Ng(N/
V
n llgg(1/8)
3
N
sin? do
IV
where (1) holds due to (D.34) and cos d. < < for 1 (o()) (di) follows from assumption (D.22)
implies that sin? dh 2 sin do/54 for any $ t 1-1 1 min (5 (τ1), O(n Then we can lower bound sin? 0f by
sin 0f sin? Φx - |sin? &5 sin? ds
sin do
2 cos 0; - cos cos s1
54
sin do
54
sin do
64
42

---

Together with the dynamic
(.12)
and lower bound D.34,
we can guarantee
t-1
N
o'm
(a
T
L-1
cOs Oi
w
+ 1
sin pm n
Σ m==o
(S wn + n w²)
|vel
N
2m
1mml
m=to
i=1
Ya sin?
Φ
arcsin(sin Φ6/6)
3 + ntt
|rr
288
2m
n llog(N N d//o)
cn 1) (oggd+/////(N//)))) lod(N) cKay
(D.36)
N
Now we take
5429
40000
22
Na sin? Φu asis Φ6/
Ma sin do
where the inequality holds since arcsin(sin 6o/6) arcsin(0) sin 6 due aresin' Plugging it into (D366) we have
cos 6ra 2 |///11
1- 4- 1) > cos Øf.
which implies
P(121 T2,1 S =T(()))))) = P ((2211 - S x n (cos S (30
< P T2,1 - 1 S T+ (0/) ) n Egcod) 550.
Initial angle: do E 10 Now assign to = ( ). Denote
A. {vto S m S s: a 2 Ya
for s 2 to.
16
Clearly, P(A,)) 2 1 78 due to D.33 Similar to D.34). we can verify that min (T aa² 2
7a/32 for any < under Ag n Egood In addition, under the event Egood, for any l > 0 we have cos 0v
|vell
10 w +
Σ
N
2T
d' (a
|mmll
a
sin 2 om
11
Σ (SmT + 1 20)=
to
1=1
mmmo
1) log( Nd/no)
coo Φ5 K2nK2 Id 1) Vog log(Nd/))
2cKaa
N
6π a1))))²
2T
(1 T a²)²
log(4 + k²)
log(4 + k2)
π + k - 1 k
π T -
k
144
a1))))
log ( + 122 = cos 8".
(D.37)
π +
It means that Φ¹ < di S きf for any l 1 s minn(4 Ö })} under the event A. 0 Egood
Hence we know (D18) holds. Consequently, the lower bound (D.22) also holds for /V Therefore, similar to (D33), we can further verify that
N 1i=1 B
Sa Salla") 112
(1 nT(T 7((T-1)
- 1 30
nh log(L/n))
a a_11a=
1
K=2
2(T
1)
2x
(IT 1) Ta))2
(1 (1- 7T(TT 1)
Ya
+
4
h(TT + k 1)
2T
2 %a
16" 1
where we used a a > 7a/4 This yields that for any t0 5851-1
A n Egood n (=-15T((0) s { (ain1a²
7a
16
43

---

which implies that
As n Egood
s 1 = Aoti-
It follows that
P =
=P
+ (1- n { a < <761)
S
+ +55
S n 1-1 + 55(1 10)
$ P (4g) - 50(t - to)
S 78 + 50(t to)
(D.38)
Similar to D.34). we can guarantee that minse[N] (a)) T a 2 /64 holds for any s tt-14
min(r+(05) (,0), 2) under the event A n Egood. It follows that
N
(a a
cos Φi
10 w
m
sin" pm n Σ (ST w" + h (==w))
|
N
2π
|mmll
m=to
m=lo
1
Ya sin
2
||0o|| ll cos du
64
2T
Ilog(N (gg(Ne) (Nd/d)/)))
2enk2 Id (VII
+ 1) log(Nd/8) 2cKa V
(D.39)
N
Taking
C Φ
384 1
T2
%a sin ju π 6"
Plugging t = to T222 into D.39 under { to T22 15 1 (5)) } n Acotrai Egood, we get
co8 72,2 2 Geos of 3 cos Ø¹ 2cm K2 (2 TT 1) (og((//0)) - 2cKa| n (log(Nd/no)
N
2 2 Ø 22nk2 I) (log 2cK (lo((Nd)n))
2 cos 0..
where we used the condition
D.6p. Invoking D.38 we can have
(T)()') 2 to + +2.2) = (( (T) 2 to + T2.2 } n cos drotrai I cos cos d'1)
(fr+(0) 2 to 72.2 - } n A n of cos foss Mosp r2,2 S cos 7. 2²))
P (0)) 13 n n n cossrrotza S cos 31})
S 55 + P (f (+() 2 to + - 11 n Alotran))
< 126 + 55 T2.2
Recalling to (T() and D.37p. we have
P (T+) 2 T2,1 + T2,2 SP (f(=+(0)) 2 2(()) + T22 n (=((0))))) s r2)))) sm))) ((T+(0) 2 (0') + T2.2 n f (0') 2 221
+ P
44

---

SP 2 = + T2.2) +P (T((10)) 2 Te,1)
2
176 56 T22
By adjusting the level of d, we can verify that To S 72,1 T22 such that Φr, S / and a a" 2 7a/32 with high probability. Now recalling that
16( =)) k( kk
144T
(1ar*)
2
%/4
sin 0"
1
log(4 + +22)
2
π + k h
we have
1
40000
1
3465x cos Ø1
222
72,2
17
sin Ø0
sin nM
π 6a
1
k²
log(k)
sin 3
77
1
k-2
1) sin Ø0
where the last inequality holds due to (D.8).
E
Convergence with Linear Speedup
E.1 Convergence of the First Layer
Lemma 4 restated. Under the settings in Theorem 3 Suppose the initial point satisfies Φo S a and a a 2 7/a /22 With probability at least 1 8, we can guarantee that sin 2 de S holds for any Ô (k2 < O(n Ö(n ?).
Proof. Denote the event C. = {a_ a" 2 7a/128 (1la1|2 A1): Vs S f). For any S t - 1, with probability least 1 35, we have
s-1
s-1
1 Ic_,, cos o. =
Up w
+
π
01
a
sin Φi 2
(E) w + +hi w0)
|u,1|
2m
1
1=0
1=0
[c
cos Ø!
glog(Nd/mg)
2on 2 (VII + 1) llg( - 2cKa|
||
3
N
2(1 T a²)²
> 1c.
(E.1)
k( + k -
where we used the assumption I eN min {1,
////0 A'd and e < dk Together with D.4). N172 Noc
we can guarantee cos of 2 that for any $ S - 1,
(1Ta') holds for any E [N] with probability at least 8. follows k(++k-1)
1c.
1
B N 1c
1
Σ
g(Ot)
-
N
N
1=1
-=1
k(T + k - 1) 1) - g
(1 (1Ta7)2
1c..
g
arccos
1
('(6/6)
arccos
(1Ja²) a²)²
- arcc
K( + k 1)
(1)
5
1Taa)²
1c..
(E.2)
12
ki k 1)
45

---

where (i) holds since g'x)) -- z)) sin x is decreasing in (0, 7/2 and (1Ta')²
k(++b-1) < due to under
Assumption ] and (ii) holds since arccos' (Ir) the event -111. I. we can get
Using the dynamic in Lemma
7/ 12
ag a
2
1 - 2
dg
T
a"
+
1
Σ
B
|S(60:t i)l
2TT
2
N
==0
1=1
1 1)
1
Na
+
1 - 1
=
1
5 51
(1 )
201
Illog(1 (1/m6)
K2
2
32
2
12
k(T k -)
N
||2 A
Y/a
5(1 T²
1/L log( 1/mp)
min
12k(n + k - 1) 201
K2
32'
N
IV
To
(Ila") 1? A 1).
128
By adjusting the level of ö, we can guarantee
P (Coin 3)) = P a aa_aa'' 2 %o
(Iaa1
Vs st)
21-5.
128
Next we assume Co(a 2) happens and hide the indicator.
Invoking
E. we have for any 8 S Ö(n
COS Φ. = cOs Φ
N
0f (at)
a
2(1 aa)²
T/7 7/a
(Ila*|3 A 1)
N
2x
1
k((T
+ k - 1)
2T
128
%a
(IIa") 1| =:
70
(E.3)
512
12'
where we used of < 2/22. Invoking Lemmal we have
197
|| sin? 2 Φe v
1
1|0, sin? Φz - 21, + M2,2221111 + He
12
2(2-1-5)
1
||0o|| sin" Φo + 207
Σ
1
77
Mi,s
12
12
==0
2(1-1-s)
1
7/a
(1,
||00|| ssn? Φe siin 2.) (E.4)
12
Recall the choices
Ne
T, log (
(1 2k2
(E.5)
2k
a 1 d dlog(dN/co)
7a
a 1 A
According to D.35 and (.26). with probability at least 1 - 8, we have
1-1
2(r-1-9)
7ia
|||0 11 sin" d. - -100,11 sin T.1
12
1-1
1(t-1-s)
17/a
1
(6n p0 + 1721)
12
==0
on (VId + I)
+ (Id+ 12) log
1 1- 1-(1-70
Tia
12
24 { (on(VId + +1) (2 (Ndd/o)) + on
(od (od
%/a
[T 1)
NT2 + +Id)
< Ne
V d + +
(E.6)
46

---

where we used /2 < 1/2. Using Lemma 11
and recalling the definition of MI,t, we have the
following concentration
2((-1-s)
ni
M1,5
12
8=0
2(t-1-s)
1
77a
rpP
La a'))
(I -
Eo
12
N
w
==0
i=1
12cK2n
t-1
1iaa
2(1-1-a)
N
log(1
1/5) ==0
r7P, Vw az))
VN
12
N
i=1
cKan
7iaa
2(t-1-8)
1og(1/0)
+ 1)
VN
12
20
10gg(11/8
n (lg((18) No
S VVa
$ VN
S 12ck2 a
(E.7)
12
holds with probability at least - 6. Moreover, it holds that
M2. = E7 (I - w (w") )) & S 11 log(d/(d/)))
N
which yields with probability at least 8 such that
7ia
2(t-1 1-s) 5)
24n
cK2 S.c
17
M2.
(E.8)
12
Ra
N
==0
Plugging
F.6
E.7
and
(E.8)
into
we can guarantee that with probability at least 1 - -30, for
any To <t
Onn
C
IN N (Vatt)
2T2 Id)
sin² Φ -
32² + Vd
+ 1 c
||2112
d²
(VId I)Ne d
< 4max
-4 =a(V2 + (VId + INNe
(E.9)
d
where we used I < eN min { 1,
1adl12 ktd \ and < dd1 Then we further have
N112 N²c
I I- (I-w' (wo') 11 -np
mp.
V w www at)
S 20n (I w'ww)) Vi + n7
P V w L(w ai)l
N
< | ? sin? Φe + 4n²
V w L(w,, at
N
+ (VTd + I)Ne
S3 36
E V
+ 2 K-
d
Vd + (VTa+ + INNe
< 49
d
47

---

With this upper bound, we can improve the concentration
E.
through
2((-1-a)
M
12
c
log (1/5) Σ
t-1
1
Mia
2(1-1-e)
49
i (Va
+ (vId+ NNN
V N
12
c
c
(VId + N)
S 4
V
d
d
+
(E.10)
Denote H = Kr (vT vTd + 1) /og( N Nd/6). Using E.9 we can further refine the bound (E.6) by
| |1 sin? Φi 1,0111 sin 2 क - sin 01 h || + n 1
(VId + N)Ne
<4
6 61 + n²' h 11
c
-Glll +1 1/²12. (VId + 1)Ne
V
It follows that
2(t 2(t-1-s)
77a
||10.|13sin sin? tx - 1|0.,112 sin? T5
12
3 (V++ WII++))NE
(VId + I)Ne <
+e.
(E.11)
d
d
Combining E.
E.
and E.8
we can show that for any 2T, S t (nK?)-2
sin 2 de I 4 max (Vā=+ (vId + T)Ne
1+
(E.12)
d
Repeating Ö(n
E. 10 1.00-E.12
E.12
for K log(1/c) times, we can guarantee that for any (K + 1)T, st
sin? de S 4 max { {(V++ (VId I)Ne
1+
,
= 4e.
E.2 Convergence of the Second Layer
Lemma 5 restated. Under the choice for n and conditions for in Theorem Suppose sin? Φ1 S
holds for any S t < Ö(1 2). With probability least 1 5, we can guarantee that ||a, a" 1|2 3 e
holds for any 0 (1- < t < Ö(n
Proof. Let hi = vú Ur. Similar to (D35 we can verify that for any i E [N]
|||/||| 2 sin? of -/ 1/ sin dbl
s sn di |/ ||]||| + v² h 1 11?
< 27e enK (v Id + I) (og((Nd/6)) + c 1)² (og(())))
< 4me,
48

---

where we used Lemma 14 and sin? oe S c. It further implies that
| sin Φe + |||of I|2 sin? of
- 1/ ?snn Φz
sin of Σ
||o||2
9E + 477
(luill - 110, vill)
1 100c.
(E.13)
Further, for any 0 5(n ?) and i E [AV] we have
ー -(0))) g(0)= (( ( S (T of sin oi of s 55me! 1/2 .6 S 5
(8)
(E.14)
where (i) holds since g' (xx) = (i - v)) sin x;; and (ii) holds due to aresin' (x) = -ল Applying this bound, we can get
VaL(wi, a:). a: - a'
1 (a: - aa) (11 + (a - (1)) (ar - aa)
7
2x
1 N
7
Σ { (a- (a--a') a
+
π
2m
N
i=1
77
[T
|a a || -37e|la - a ||||aa"||
2m
n
π
a. a || 6ne
(E.15)
2m
where the last inequality holds due to Lemma 12 such that ||a: - a || S 6||a"||. In addition, it holds
that
N
N
1
L(wi
at)
11 + (m- (a: a²)+ +
Σ 1=1
g(o)) n
a"
4
(m 1)2
aa - a a²112 + +15c" 11c2211aa)) ||"*11
(E.16)
2x²
where we used the relation
E.14) Denote à, = a; a" - - Σm
V VaL(wi, a;), then we have
N
2
1
la: - a²11==
a: a' - '
V VaL(wi-110)
- T/E
N
1
0: a' N
Σ
V L w
at a/-
2n ((.-1. + 17 1
rパa -1) 1) +
( T + k 1)2
<
- -a-11-
2π
2T
112 + Gne² 2 + 1/2et ||a*!12
2n
(
+
77( 1)
+ 17²c2
||a_- a²112- - 2n (ā 1, E/-1) + 1/2 1| + kmee
x ||a"|
4m
n7(T= - 11)
1-
n - -1 (ā,, Es)
|100 11 + 27
Σ
1
4x
4T
7 - 1))
7/(
+
1|
4T
[-1
17( 11
t-1-s
(6neR3 + 15n)2e "5n"2= 112).
(E.
4x
49

---

Using Lemma 12 again, we can verify that
1
| - aa a'll +
v VaL(wi,
$ 6,, + 11 (1l (1
( 1)1) (ar aaa-aa)l + ( ((o)))]la
2T
71( + k: -1
6||a || + ! |la"
$ 6K, +
2x
< 8Ke.
(E.18)
Similar to A.17 with (1 1) 1)
we can guarantee
[-1
77
π
r-s
log(2/0)
17(T
1-8
K log
1
a_ Es
S cn
+
4T
N
4
N
17 (2/6)
I 4cK2
(E.19)
N
with probability at least - 6. Now take T. with the concentration inequality (A.19), have for any Ta S On
-
log (1). Plugging
E.19 into E.17
together
"
|a a00=a1112 (1 7
-
17 (20(22
|100 - a0022
1 + 4cK² V
4m
N
2nenk log(t/0)
K² + 12TcK3 + 2n
N
$ <clan - a" 12 Vck? + e + 12Tck3 2n K
< <2VEK?
(E.20)
With this upper bound, we can refine (E.18 by
| 2 s 2||a,
11 + 2
V Val at)l S 8VEK2.
Consequently, the bound 19.19 can be improved
t-
7( -
nec log((/2))
a_ E,
S 4cK2
4T
N
==
Then we can guarantee that for any 21a S st Ō(7-
1 77
11) (_-)--1))
n log(2/5)
|| |a: 1a==2"11
2²112=5 <
1100- - -a"11 + +4cK2
4T
N
2Tcnk log(t/))
+
K2 + 12TEE?? + 2nTE" Ks?
N
$ El|ao a²1
3/4 3/1K3 2 12TeK3 + 27 K3
S k/3
(E.21)
Repeating the refinement from proof.
E.20 to for at most log(1/e) times, show finish the
E.3 Conclusion
Theorem 3 restated. Suppose the initial point (vo. an) satisfies ag a' 2 7a/32 and do < Z!. No For any > 0, we choose 1/ के 1. (lg(dN)/8) for some absolute constant e > 0. If S
/// A'd | and < min(NN- d= dl -2), then [(vr, ar) O(cK?) holds with EN min { 1, N N²E
probability least 1 where T = δ
dx
Ne
50

---

Proof. According to the dynamic of at, we know
1 (aa -a")= =(1- nT(T + k 1)
1 -40=1-aa)+ 2
Σ
g(
1aa² + m1 mlae E-1
2T
N
i=1
nsT + k 1--11 1)
t-1
+ k + 1)
6-1-8
1 (aa=- (a0- a²) +
Σ
1
IT
2
1-1
+ k 1-1-s
1 N
1
- x
lTa".
(E.22)
2m
2n
N
i=1
follows from that
E.14
7
1
(7 k 11
)
6-1-8
Σ g( - -7) 1
5Te
(E.23)
2x
2π
T+
Using Lemma
1), it holds that
h-1
17(T
+ k 15-1) 1)
1-1-8
(1oo(110))
1T E, S cKap
1
(E.24)
2m
N
Plugging E.23 and (..44)
into E.22 and taking Ti 1--20 2x
log (+), we can have
1) 7/
5xc
|1 (ai-aa)) a')l s c|1 (as (as a')l + VeKa +
1 Taa
a"
a k
I <eVkKa + VcKa +
T 11 a1aa1
5Te
$ <2ccKa.
(E.25)
where we used [1 aol I [1 a"I and 1/k. Invoking Lemma 6 and the normalized network in we know
1
1
|al| 9(0) Taa
[00 a) -(w, a)
a
1
2T
1
1 ( a1)
(1 T a²²² +
(1 (1aa) a)²
2T
2T
1
9
1 1 1T aaaa-aa))' at){
l|a a² 2|
Ta
(F.26)
2
π
2π
Similar to E.14 for any 2 Tu, we also have
π g(or) = g(0) ( S (π - Φz) sin dr 0: S TE - di S TE.
(E.27)
Invoking Lemma 4 and 5 to E.26 together with E.27 conclude that for T = Ō
dk
Ne
E(VT, aT) I 2
1
15
eK, + e||ar|llaa|| + +4ck3
S Sella'113
2
with probability at least 8.
51


Reviews:
[{"review_id": "tCGkPFkQIc", "reviewer": "Reviewer_p3Vw", "summary": "This paper considers a federated learning setting for a  one-hidden-layer convolutional neural network without overparameterization. It is proven that vanilla local SGD (where in each iteration each node updates the model by the local gradient and then all nodes synchronize the model parameters) can converge to a global minimum.", "questions": "Please see \"weakness\".", "limitations": "I don't think the authors adequately addressed the limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The convergence analysis does not require over-parameterization (i.e., in the NTK region) and injected noise.    \n     \n2. Based on a careful landscape study, the paper proposes a self-correction mechanism that ensures the algorithm enters a good landscape region in polynomial time. This explains why local SGD can converge in practice even though the landscape is not well-conditioned. ", "weaknesses": "1. The online learning assumption, i.e., each node samples data i.i.d. from the same distribution in each iteration, is crucial to the analysis of this paper, but it deviates from the practical settings, where each node computes its gradient according to a given set of local data.\n\n2. Why is the proposed model a CNN? It seems a fully-connected network.\n\n3. The weight-normalization technique twists the vanilla SGD.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for taking your precious time to review our paper! Next, we provide detailed responses to your comments and questions.\n\n**1. The online learning assumption, i.e., each node samples data i.i.d. from the same distribution in each iteration, is crucial to the analysis of this paper, but it deviates from the practical settings, where each node computes its gradient according to a given set of local data.**\n\nThank you for this important point. We agree that non-i.i.d. is a relevant problem in federated learning. However, one of the points we want to make in the paper is that the global convergence of SGD under one hidden layer neural network without overparameterization in the single-machine setting is still unknown until our paper. Specifically, due to the non-convexity, prior works only show the local convergence of GD [13] and the global convergence of perturbed GD by injecting noise [63]. Currently, there is no literature analyzing vanilla SGD for this neural network, let alone local SGD. Our paper proves the global convergence of local SGD under this setting, which is even more challenging than SGD since we have to handle the effects of local steps. We devote significant efforts to establishing the new recursive dynamics and developing new analysis techniques (namely, self-correction) to demonstrate the convergence to global minima with almost arbitrary initialization, despite the loss landscape being nonconvex. Note that the technique in local SGD for general nonconvex problems can only guarantee finding a stationary point instead of a global minimum [56,62].\n\n**2. Why is the proposed model a CNN? It seems a fully-connected network.**\n\nWe apologize for the confusion. Please note that we follow the assumption and terminology in Du et al. [13] and Zhou et al. [63] to refer to the network as a CNN. We acknowledge that it is indeed a fully-connected network since there is no overlap between patches in CNN. In our paper, we elect to refer to the network as CNN to keep the terminology consistent with the most related works [13, 63]. We will add a sentence to explain this in the revised version of the paper.\n\n**3. The weight-normalization technique twists the vanilla SGD.**\n\nThe vanilla SGD in our paper refers to optimizing the loss function of the model defined in Eq.(2) after applying weight-normalization, which is a function of $v$ and $a$. Note that the description of Algorithm 1 on page 4 is indeed vanilla SGD because it applies stochastic gradient updates over $(v,a)$ but not $(w,a)$. \n\nApplying the weight normalization is consistent with Du et al. [13] and Zhou et al. [63]. The GD algorithm in Du et al. [13] and the perturbed GD in Zhou et al. [63] are also conducted under the same model. The original network $f(Z, w, a)$ has a positive-homogeneity issue: for any $c>0$, it holds $f(Z, cw, a/c) = f(Z, w, a)$. This property allows the network to be rescaled without changing the function value. It also implies that only the direction of the first layer $w$ will essentially affect the loss function. The weight-normalization technique makes the learning algorithm scaling-invariant and can stabilize the training process [46].\n \n**References**\n\n[13] Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer cnn: Don’t be afraid of spurious local minima. In International Conference on Machine Learning, pages 1339–1348. PMLR, 2018.\n\n[46] Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. Advances in neural information processing systems, 29, 2016.\n\n[56] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. arXiv preprint arXiv:1905.03817, 2019.\n\n[62] Fan Zhou and Guojing Cong. On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization. arXiv preprint arXiv:1708.01012, 2017.\n\n[63] Mo Zhou, Tianyi Liu, Yan Li, Dachao Lin, Enlu Zhou, and Tuo Zhao. Toward understanding the importance of noise in training neural networks. In International Conference on Machine Learning, pages 7594–7602. PMLR, 2019.\n"}, {"review_id": "bg3Dky1Gcs", "reviewer": "Reviewer_coFq", "summary": "The paper asserts that local SGD achieves convergence to the global minimum in the presence of Gaussian input. The experimental setup involves a two-layer student model, where the ground truth is generated by a two-layer teacher model. The authors highlight their main contribution as a proof that does not necessitate noise injection.", "questions": "Please review the suggested revisions for the mentioned weaknesses:\n\n\nMinor comments:\n\nIn line 167, could you please clarify the distinction between L(w, a; Z) and l(w, a; Z)?\nIn line 169, \"wights\" should be corrected to \"weights\".\nIn line 215, \"learning\" should be changed to \"learning rate\".", "limitations": "\nI believe it is important for the authors to provide justification for the assumptions made. Without such justification, the scope and applicability of the proposed results may be limited.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper proved global convergence of local SGD without noise injection.", "weaknesses": "1. The presentation of the results is unclear and the proof is difficult to follow. It would be beneficial for the authors to provide a more intuitive interpretation of the terms, lemmas, and equations. For instance:\n- Could the authors clarify the purpose and significance of the intermediate step $\\check{v}_{t+1}$?\n- How does Theorem 1 demonstrate the self-correction of the second layer?\n\n2. The realism of the assumptions made by the authors is questionable. For instance:\n- What is the probability that a randomly selected $a^*$ satisfies equation (5)? It appears to be very low in my estimation.\n\n3.  I'm uncertain why the authors chose to consider CNN instead of linear layers. It seems to add unnecessary confusion to the problem.\n\n4. What sets \"local\" SGD apart from regular SGD? It would be helpful for the authors to clarify the distinctive aspects (in terms of proof) of \"local\" SGD in comparison to regular SGD.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper.\n\n**1. Could the authors clarify the purpose and significance of the intermediate step $\\check{v}\\_{t+1}$.**\n\nThe purpose of the intermediate step $\\check{v}_\\{t+1}$ is to establish an exact recursion to characterize how the global angle $\\phi\\_{t+1}$ changes in the training process.  In traditional analysis of local SGD, the descent inequality is obtained by taking the average on local weights and local gradients. However, this analysis is not applicable in our setting since we have to consider the angle $\\phi_t$ instead of the inner product between $v_t$ and the ground truth. Due to the nonlinear relationship between the global angle $\\phi_t$ and local angle $\\phi_t^i$, we cannot get a global dynamic of $\\phi_t$ by averaging local dynamics of $\\phi_t^i$ as provided in [13]. To address this challenge, we introduce the virtual sequence $\\check {v}\\_{t+1}$ and use the corresponding angle $\\check{\\phi}\\_{t+1}$ as a proxy between $\\phi\\_{t+1}$ and $\\phi_t$.\n\n**2. How does Theorem 1 demonstrate the self-correction of the second layer?**\n\nThe intermediate step $\\check{v}\\_{t+1}$ appears in the term $H_t$ in (3), so its significance in the proof hinges on the recursion (3). First, the sign of $\\lambda_t \\cos \\phi_t$ in (3) determines the direction of the first layer’s update, and this observation enlightens us to analyze the self-correction of the first layer in different regions. Second, $H_t$ is the discrepancy term, $M\\_{1,t}$ is a martingale difference sequence, and $M\\_{2,t}$ is the variance term of noise. Hence the recursion (3) actually resembles the descent inequality of local SGD analysis for general functions. It helps us show the linear speedup and reduce communication rounds in the convergence stage.\n\nDu et al. [13] proved that GD can converge to the global minimum if the initialization is in the attraction basin, that is $\\{(v_0, a_0): \\phi_0 < \\pi/2, a_0^{\\prime}a^* > 0\\}$. In our paper, we consider local SGD with almost arbitrary initialization including the bad area with wrong signals such that $\\phi_0 > \\pi/ 2$ or $a_0^{\\prime}a^* \\leq 0$. The self-correction process means SGD or local SGD can correct the wrong signals from the initialization and enter the attraction basin in polynomial time. In Theorem 1, $\\tau_a$ is the time stamp when the signal of the second layer turns positive (and the initial signal could be negative). Therefore, $\\tau_a \\leq O(\\eta^{-1} \\log k)$ means that the signal of the second layer can be corrected in $O(\\eta^{-1} \\log k)$ steps for any initialization.\n\n**3. The realism of the assumptions made by the authors is questionable. For instance: What is the probability that a randomly selected $a^{*}$ satisfies equation (5)? It appears to be very low in my estimation.**\n\nSince $a^*$ is a fixed vector in our paper, we respectfully disagree that one can use random selection to evaluate the condition Eq.(5). But it can be satisfied when $a^*$ is dense. For example, we let $\\alpha = \\frac{(1^{\\prime}a^*)^2}{k |a^*|^2}$ where $\\alpha \\in (0,1]$ roughly stands for the degree of sparsity of the vector $a^{*}$. Then Eq.(5) will hold if \n$$\\alpha > (1-32(\\pi-1)/k)^{-1}\\frac{\\pi +k-1}{(\\pi-1)k}.$$ \nThis right-hand side can be a constant in $(0,1)$ for proper $k$. For example, when $k \\geq 320(\\pi-1)^2$ (a technical choice as in Theorem 1), this condition will be satisfied as long as $\\alpha > 0.48$.\n\nWe have added an additional simulation with different $\\alpha$ to show that this condition is almost necessary to show the global convergence with arbitrary initialization. In each trial, we randomly select an initial point from the initial region defined in our paper. Then we calculate the probability of convergence over 100 independent trials with $k=64$. From **Table 1 in the rebuttal PDF file**, we can see the probability of convergence becomes larger when $\\alpha$ tends to 1. Specifically, the probability becomes 1 when $\\alpha > 1/8$. Even though the coefficient in our condition on $\\alpha$ may require it to be greater than $1/4$ due to the technical relaxation, the results indicate that a constant $\\alpha$ is necessary.\n\n**4. I'm uncertain why the authors chose to consider CNN instead of linear layers. It seems to add unnecessary confusion to the problem.**\n\nWe apologize for the confusion. Please note that we follow the assumption and terminology in Du et al. [13] and Zhou et al. [63] to refer to the network as a CNN. We acknowledge that it is indeed a fully-connected network since there is no overlap between patches in CNN. In our paper, we elect to refer to the network as CNN to keep the terminology consistent with the most related works [13, 63]. We will add a sentence to explain this in the revised version of the paper.\n\n**5. What sets \"local\" SGD apart from regular SGD? It would be helpful for the authors to clarify the distinctive aspects (in terms of proof) of \"local\" SGD in comparison to regular SGD.**\n\nWe thank the reviewer for this suggestion. For regular SGD (that is, single machine with $N=1$), the intermediate step $\\check{v}\\_{t+1}$ equals to $v\\_{t+1}$, so the discrepancy $H_t$ is zero. Then the distinctive aspects of local SGD in the proof are how to quantify and control the scale of the discrepancy term $H_t$. The traditional analysis in distributed nonconvex optimization relies on the bounded smoothness condition to bound the discrepancy term and attain linear speedup. Our paper carries out a more careful analysis because the loss function of the neural network model has an unbounded smooth parameter.\n\n**6. In line 167, could you please clarify the distinction between $L(w, a; Z)$ and $\\ell(w, a; Z)$?**\n\nWe apologize for this. We first want to clarify that only $\\ell(v,a;Z)$ is used in our paper, and there is no definition for $\\ell(w,a;Z)$. The loss $\\ell$ is defined in terms of $v$, and the loss $L$ is defined in terms of $w = v/\\|v\\|$. We will take care to address this in the paper."}, {"review_id": "66DUR74iEc", "reviewer": "Reviewer_bCYH", "summary": "This paper provides a rigorous theoretical justification on how the local SGD (without the injection of noise) can find the global minima for CNN without relying on the NTK-type analysis (i.e., overparametrization) under federated learning framework. ", "questions": "A.\tWhy is the f (Z, w, a) CNN? It looks to me like a shallow fully connected neural network. What is the exact structure of $w \\in \\mathbb{R}^{d}$? \nB.\tIn line 90, the paper says the algorithm starts from the random initialization from the same initial region as in [13, 63]. In line 203, it says arbitrary initialization. I was bit confused while reading the paper on this point. And it becomes clear while reading line 312~313. \nC.\tJust to clear my understanding, so your result is saying that weights in the first layer converges (in polynomial time), and then the weights in the second layer converges afterward? \n\n", "limitations": "This work has no negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "A.\tThe contributions of the paper are clearly written.  \nB.\tNice simulation results which are consistent with the theoretical predictions.\nC.\tLike the part where the authors divide the landscape of the objective function into several regions. This type of analysis is not something that I can find in the current literature. \n", "weaknesses": "A.\tWriting is little bit technical. It would be great if the authors can draw some cartoons of dynamics of each layer for the global convergence. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for appreciating our work and please see our responses to your questions.\n\n**1. Why is the f (Z, w, a) CNN? It looks to me like a shallow fully connected neural network. What is the exact structure of $w$?**\n\nWe apologize for the confusion. Please note that we follow the assumption and terminology in Du et al. [13] and Zhou et al. [63] to refer to the network as a CNN. We acknowledge that it is indeed a fully-connected network, since there is no overlap between patches in CNN. In our paper, we elect to refer to the network as a CNN so that we can keep the terminology consistent with the most related works [13, 63]. We will add a sentence to explain this in the revised version of the paper. There is no special structural for $w$.\n\n**2. In line 90, the paper says the algorithm starts from the random initialization from the same initial region as in [13, 63]. In line 203, it says arbitrary initialization. I was bit confused while reading the paper on this point. And it becomes clear while reading line 312~313.**\n\nWe thank the reviewer for pointing this out. We will modify the statements in lines 90 and 203 to make it more precise. We will mention explicitly that the local SGD converges from arbitrary initialization except for a measure zero set, where the angle of the first layer between initialization and the global minimum is $\\pi$.\n\n\n**3. Just to clear my understanding, so your result is saying that weights in the first layer converges (in polynomial time), and then the weights in the second layer converges afterward?**\n\nWe thank the reviewer for this insightful question. Lemmas 4 and 5 in Section 4.3 are only used to prove the convergence results, which are not saying the second layer converges afterward the first layer. They actually converge simultaneously without particular order. We will add this remark in our revision. Our simulation results in **Figure 1 of rebuttal PDF file** indeed show that two layers almost converge simultaneously after the self-correction process.\n\n**References**\n\n[13] Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer cnn: Don’t be afraid of spurious local minima. In International Conference on Machine Learning, pages 1339–1348. PMLR, 2018.\n\n[63] Mo Zhou, Tianyi Liu, Yan Li, Dachao Lin, Enlu Zhou, and Tuo Zhao. Toward understanding the importance of noise in training neural networks. In International Conference on Machine Learning, pages 7594–7602. PMLR, 2019.\n"}, {"review_id": "KqwbZuuEzb", "reviewer": "Reviewer_GGhs", "summary": "This paper studies the global convergence of local SGD for One-hidden-layer Convolutional Neural Networks. The authors present solid theoretical understanding. They show that without overparameterization and injecting noise,  local SGD have global convergence by new proof techniques and new understanding.", "questions": "My main question pertains to Assumption 1 about the teacher traget. \nIt appears that this assumption suggestes that stronger conditions on $\\boldsymbol{a}^*$ are required for larger values of $k$. \nI am curious to know whether this requirement is essential or merely technical. \nIn other words, if one use a sufficiently large $k$ that contradicts this assumption, do the training dynamics in the last region (in the proof of Theorem 1) fundamentally change? \nThe authors could attempt to demonstrate this aspect experimentally or theoretically.", "limitations": "The limitations of this article lie in the requirements for data and target Assumption. \nHowever, these limitations should not be grounds for rejection. \nGiven our limited understanding of the training dynamics of nonconvex optimization, studying such simple setups can still provide valuable insights and contribute to the field.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is clear and well-written. \nUnderstanding the optimization dynamics of gradient-based method is a significant theoretical issue. \nThis paper provides a solid theoretical analysis without highly over-parameterization and injecting noise, which results in the highly non-convexity.\nTheoretically, the authors provide a novel understanding of the training dynamics by dividing them into two phases: self-correction and convergence.", "weaknesses": "The article's significance is limited due to the restriction of input data to Gaussian distributions. However, this limitation is not a major concern since the problem itself is non-convex, even in this simplified scenario. Additionally, I have significant concerns regarding Assumption 1 about the target function, which I will discuss in detail in the Questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for taking your precious time to review our paper and please see our responses to your questions.\n\n**1. My main question pertains to Assumption 1 about the teacher target. It appears that this assumption suggests that stronger conditions on $a^{*}$ are required for larger values of k. I am curious to know whether this requirement is essential or merely technical. In other words, if one uses a sufficiently large k that contradicts this assumption, do the training dynamics in the last region (in the proof of Theorem 1) fundamentally change? The authors could attempt to demonstrate this aspect experimentally or theoretically.**\n\nWe thank the reviewer for this question. In Assumption 1, the condition on the upper bound of $(1^{\\prime}a^*)^2$ is merely technical, and the condition in Eq.(5) is almost essential to show the global convergence with arbitrary initialization. Let $\\alpha = \\frac{(1^{\\prime}a^*)^2}{k |a^*|^2}$ where $\\alpha \\in (0,1]$ roughly stands for the degree of sparsity of the vector $a^{*}$. Then Eq.(5) will hold if \n$$\\alpha > (1-32(\\pi-1)/k)^{-1}\\frac{\\pi +k-1}{(\\pi-1)k}.$$ \nThis right-hand side can be a constant in $(0,1)$ for proper $k$. For example, when $k \\geq 320(\\pi-1)^2$ (a technical choice as in Theorem 1), this condition will be satisfied as long as $\\alpha > 0.48$.\n\nTo show that (5) is essential, we have added an additional simulation with different $\\alpha$ to show that this condition is nearly necessary for arbitrary initialization. In each trial, we randomly select an initial point from the initial region defined in our paper. Then we calculate the probability of convergence over 100 independent trials with $k=64$. From the following table (**Table 1 in the rebuttal PDF file**), we can see the probability of convergence becomes larger when $\\alpha$ tends to 1. Specially, the probability becomes 1 when $\\alpha > 1/4$. \n\n| alpha     | 1/64 | 1/32 | 1/16 | 1/8  | 1/4 | 1/2 |\n|-----------|------|------|------|------|-----|-----|\n| Local SGD | 0.54 | 0.65 | 0.74 | 0.87 | 1   | 1 |\n| SGD       | 0.54 | 0.62 | 0.73 | 0.85 | 1   | 1   |\n\nIt is challenging to theoretically demonstrate the last region in the proof of Theorem 1 if Eq.(5) does not hold because it would require a lower-bound analysis for this specific model. Experimentally, we plot the trajectories of SGD and local SGD that start from the region with $\\phi_0$ and converge to the spurious local minima. It means that the self-correction process could fail if Eq.(5) does not hold for the ground truth.\n\n\n**2. The limitations of this article lie in the requirements for data and target Assumption. However, these limitations should not be grounds for rejection. Given our limited understanding of the training dynamics of nonconvex optimization, studying such simple setups can still provide valuable insights and contribute to the field.**\n\nWe thank the reviewer for these insightful and encouraging comments. To the best of our knowledge, this is the first global convergence result for local SGD for such a nonconvex function which does not require overparameterization and NTK analysis.\n"}]

Author rebuttal:
Dear Reviewers:

We appreciate your constructive reviews and would like to thank you for your time in helping us to improve our paper. We have responded to the reviews and questions individually and have added several new simulations in the PDF file. Here we provide a general response to address the two frequently asked questions by reviewers about the terminology and assumption in the paper:

**Regarding the terminology of CNNs.** We apologize for the confusion. We have followed the assumption and terminology in Du et al. [13] and Zhou et al. [63] to refer to the network as a CNN. We acknowledge that it is indeed a fully-connected network since there is no overlap between patches in the CNN. In our paper, we elect to refer to the network as a CNN so that we can keep the terminology consistent with the most related works [13, 63]. We will add a sentence to explain this in the revised version of the paper.

**Regarding the Assumption in Theorem 1.** To illustrate the necessity of condition (6) to guarantee the global convergence with almost arbitrary initialization, we calculate the probabilities of convergence to the global minimum under different values of $(1^{\prime}a^*)^2/\|a^*\|^2$ in the new simulations. **Table 1 in the rebuttal PDF file** shows that the condition where the probability of converging to the global minimum reaches 1 is very close to condition (6). Therefore, we believe (6) is nearly essential to the self-correction mechanism as illustrated in Theorem 1.

[13] Simon Du, Jason Lee, Yuandong Tian, Aarti Singh, and Barnabas Poczos. Gradient descent learns one-hidden-layer cnn: Don’t be afraid of spurious local minima. In International Conference on Machine Learning, pages 1339–1348. PMLR, 2018.

[63] Mo Zhou, Tianyi Liu, Yan Li, Dachao Lin, Enlu Zhou, and Tuo Zhao. Toward understanding the importance of noise in training neural networks. In International Conference on Machine Learning, pages 7594–7602. PMLR, 2019.

Meta-review: The paper analyzes the convergence behavior of local SGD for training two-layer neural networks in a federated learning setup. It studies this problem in a teacher-student model in which the goal is to reproduce the output of the teacher network, and the input vectors are drawn from a Gaussian distribution. Local SGD interleaves gradient updates based on local data with consensus (averaging) steps. The paper analyzes the dynamics of both network layers, and identifies a ``self-correction’’ mechanism, by which, if the second layer weights have coherent signs (in the sense that <1,a> is large compared to ||a||), in polynomial time the iterates enter a basin in which they then exhibit linear convergence to the ground truth. For the federated version of the problem, the paper shows a linear speedup in the number of machines. 

 Reviewers produced a split evaluation of the paper. The main concern involved the condition on the ground truth second layer weights a_*. Secondary issues include terminology (this is not a convolutional neural network) and the paper’s relatively dense presentation. On the positive side, the paper produces novel results on local stochastic gradient descent for federated learning, and, as a by-product, strengthens existing results on single machine SGD, by articulating conditions under which gradient descent is converges globally, without theoretical conveniences such as noise injection. The author response addresses issue with the a_* conditions in two ways: first, by arguing that this assumption (or some similar form of sign consistency) is almost necessary for the global convergence of GD, and second, by arguing that under certain random models, this condition holds with high probability. In the final version, the authors are strongly encouraged to (i) avoid the terminology of convolutional neural networks, (ii) provide additional discussion of the paper’s conditions on a_* (e.g., by including material from the response to reviewers).
Decision: Accept (poster)