Faster Directional Convergence of Linear Neural Networks under Spherically Symmetric Data
Authors: Dachao Lin
Ruoyu Sun
Zhihua Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: optimization for deep linear networks
global directional convergence

Abstract: In this paper, we study gradient methods for training deep linear neural networks with binary cross-entropy loss. In particular, we show global directional convergence guarantees from a polynomial rate to a linear rate for (deep) linear networks with spherically symmetric data distribution, which can be viewed as a specific zero-margin dataset. Our results do not require the assumptions in other works such as small initial loss, presumed convergence of weight direction, or overparameterization. We also characterize our findings in experiments.

Faster Directional Convergence of Linear Neural Networks under Spherically Symmetric Data
Dachao Lin'
Ruoyu Sun? Zhihua Zhang²
Acaddmyy for Advanced Interdisciplinary Studies, Peking University
Department of Industrial and Enterprise Engineering, Coordinate Science Lab (affiliated)
University of Illinois Arrbana-Champaii
School of Mathematical Sciences, Peking University
lindachao@pku edu.cn ruoyusQillinois edu zhzhangGmath. pku.ppuueee edu.
Abstract
In this paper, we study gradient methods for training deep linear neural networks with binary cross-entropy loss. In particular, we show global directional conver- gence guarantees from a polynomial rate to linear rate for (deep) linear networks with spherically symmetric data distribution, which can be viewed as a specific zero-margin dataset. Our results not require the assumptions in other works such as small initial loss, presumed convergence of weight direction, overparam- eterization. We also characterize our findings in experiments.
Introduction
Local v.s. non-local analysis. Deep neural networks have been successfully trained with simple gradient-based methods, despite the inherent non-convexity of the objective function. Recently, number of works proved the convergence of gradient methods to global minima for ultra-wide neural networks 4 [12 13,
20 31. These works essentially performed "local analysis" because in their proofs the parameters stay close to initialization during training. In the large width setting, there exists global minimum near random initial point, thus staying in the local region can still result convergence to global minima. Despite the technical convenience of handling a local region, in practical training, the parameters often travel far from initialization (see, e.g., (15)). To understand the practical optimization trajectory, it important to develop a non-local convergence analysis.
Deep linear nets with quadratic loss: "local analysis"' To understand the behavior of gradient descent (GD) for general neural nets, we need understand GD for deep linear nets. A number of works analyzed linear networks with the square loss. Bartlett et al. ( provided that gradient descent converges the target matrix at linear rate from identity initialization, while assuming the target matrix is either close to identity or positive definite. Arora et al. (2] proved linear convergence of deep linear networks the initialization has a positive "deficiency margin" and nearly balanced. Later, few works followed similar idea to neural tangent kernel (NTK) 20 to establish convergence analysis. Du and Hu [TT showed GD with Gaussian random initialization converges minimum at linear rate if the width of every hidden layer is large enough. Hu et al. [19] improved the width requirement to be independent of depth, by utilizing orthogonal weight initialization, but they assume each layer to have the same width. All the above works are not non-local analysis.
global
Deep linear nets with quadratic loss: non-local analysis. Eftekhari 14 provided non-local convergence analysis for deep linear nets with quadratic loss. When one layer has only one neuron (including scalar output case) and assumming that the input data are whitened, they proved that gradient flow converges to global minimizers starting from balanced initialization.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this work, we are interested in the classification task with binary cross- ertss-yntropy loss. To our knowledge, there was no non-local convergence analysis of gradient flow for deep linear nets in such scheme.
Deep linear nets with logit loss: final-phase analysis. Several recent works 17 38 23
studied the exponential-tpp loss for deep linear networks. Specifically, Gunasekar et al. [17, Nacson al. [38] proved the convergence to max-margin solution, but under the assumption that the weight direction and the loss have converged to global optima, which is a "final-point analysis". Lyu and Li [37], Ji and Telgarsky [21 23 also proved the convergence to max- max-margin solution under the assumption that the initial point has already obtained zero classification error (weaker assumption than [17 (88) ). i.e. they analyzed the "final phase" of training. In this work, we would like to understand the entire training dynamics, not just the "late training" period.
1.1 Our Contributions
In this paper, we analyze gradient flow for deep linear networks with logit loss (i.e. binary cross- entropy loss). The main contributions of this paper are summarized as follows:
Convergence result. We prove the global convergence of gradient flow for minimizing population logit loss with deep linear nets, under the assumption that the input data is spherically symmetric (Theorem 3). This assumption covers the standard Gaussian distribution and uniform distribution the sphere. To our knowledge, this is the first global analysis of gradient flow on deep linear nets with logit loss, though under certain strong assumptions. We emphasize that our analysis is beyond the "lazy training" scheme.
Convergence rate. We also establish explicit convergence rate of gradient flow (Theorem 3) Denote P(t) the angle between w. (t) and v. where (t( is the collection of parameters at time t following gradient flow, and v is the directional global minimizer. In the first phase, we have polynomial convergence rate of cos(O(t)), that is, cos()(t)) 2 1- ((Nst) xi=). where N1 + is the depth of the deep linear network. In the second phase, we have lincar convergence rate of cos(O(t)), that is, cos cos()(t)) 2 1-c 1-e ((-)), And the second phase begins when the induced weight norm changes from descending ascending mentioned below.
Weight norm change pattern. We prove that the induced weight norm goes through descending and ascending periods. If the initial induced weight norm starts with descending behavior, then after finite time, will change to ascending and continues increasing to infinity. If the initial induced weight norm begins with ascending behavior, then it would increase to infinity directly.
We also verify our results in numerical experiments including the descending and ascending behavior of weight norm and the convergence rates in our setting.
1.2 Additional Related work
Directional convergence for exponentially-tailed loss. Previously, we mentioned few works on deep linear nets for classification. Next, we discuss convergence results on classification for more general settings (not just deep linear nets). For binary classification problems, oftentimes it is the direction of the predictor that matters, while the norm is less important. For a finite number of linearly separable data, there can be infinitely many directions that lead to zero loss, and classical optimization
results do not show which one GD converges to. In many recent works [2] 24 25
[38 39 46 16), it
shown that for binary classification problems with exponential-type loss (which can be viewed as
the 1- I-layer 1 l-linear-ncuron net case) and linearly separable data, GD converges to the &s maximum margin direction. These works assume there is a positive margin. Ji and Telgarsky (22]. Ji al. 25 also consider non- separable case, but still requires a positive margin in the "separable part". Moreover, some works [2] 23 17 38) study the convergence of GD for training deep linear nets. Lyu and Li (37] further studied deep homogeneous networks (covering deep linear nets and deep ReLU nets). Yun et al. [50] provided a unified framework that connects several existing results under a general tensor formulation of linear networks. A few other works study wide non-linear neural nets, e-g., Chizat and Bach (9, Bach and Chizat [5] improved previous results in the infinitely wide two-layer case, identifying the learned classifier as the solution of convex max- max-ma problem.

---

There are two differences between those works and ours. First, none of these works have performed non-local convergence analysis for deep linear nets as the current work does. Second, they consider finite data with a positive margin, and we consider infinitely many data with a zero margin. We underline that previous convergence rates are inversely proportional to such a margin, which vacuous in our zero-margin setting.
More discussions on non-local analysis of deep linear nets with quadratic loss. We mentioned Eftekhari [4] earlier; here we add more discussions. Besides the main difference in the loss functions, there are two other differences between Eftekhari [4]] and our work. First, they assume whitened data, while we assume spherically symmetric data. Second, their convergence rate result requires an extra assumption that the inverse spectral gap of the target matrix is small ([14) Theorem 4.4)), while our convergence rate result does not require extra assumption. Besides the work [14), another earlier work [6] performed "non-local analysis", but as pointed out by [14], their work only ensures convergence to the minimizer in constrained subset, not necessarily the global minimizer (see Appendix in 14 for detail).
Global landscape analysis. In our work, the term "non-local analysis" should actually be called "non-local convergence analysis". There another line of works on "non-local landscape analysis"
(see, e.g., [26 36 27
52 41 30 TO 34, 33 35 49 44] and the surveys [8]] 47)) which analyze
the properties of stationary points, local minima, strict local minima, etc. These works do not directly
analyze the convergence of GD, thus are different from our work.
2 Preliminaries
We consider binary classification problem where the data generated follows. Let Rdd be fixed vector satisfying ||v|| = 1. The input data point x E Rd is sampled from a distribution and the label for each is yx) = sgn(v x) E (-1,+1)
Suppose want to learn the parameter for predictor 6(; w): Rd - IR. (the specific form of will be discussed later). We use the population logit loss {(z) == In(1 + e=) (binary cross-entropy)
with 2(x, w) f(x) ((x, w). The parameter is learned by solving the optimization problem
min L(w) == Ex-D In (1 +1+ e e=0(0)o().))
(1)
We focus the following standard gradient methods.
1) Gradient flow: We initialize w(O). and for every & >> 0 let w(t) be the solution of the differential equation: (t) = (tw((t)))
2) Gradient descent: We initialize w(0) and set sequence of positive learning rates {m h= At each iteration n > O. we do a single step in the negative direction of the gradient, that is, w(k + 1) = w(k) 7/k (Ww().).
Notation. We denote vectors by lowercase bold letters (e.g., u, v). Moreover, || denotes the standard norm for vector, or the spectral norm for given matrix. Let Σ = Ex be the population covariance matrix, and (A) be the maximum eigenvalue of real symmetric matrix A. We by gd-1 denote the surface of an d-dimensional unit sphere, and by Is the k-dimensional identity matrix.
We let = w//w/| whenever ||w|| * 0. Given vectors (Wi,.... wa)T Rd and (VI,..., va) E Rd, we let 0(w, v) = arccos [w T / [[|w[| ||vl]]] [0, denote the angle between w and v. ((t) == 0 ((w(t), v) and ((n) := (ww(n), v). We let Dw, be the marginal distribution of x = (I1,... (I1,.......) .2) on the subspace spanned by two linearly independent vectors w, V (as a distribution over 2R²,, and D, similarly. Let D:, := De,,ez where Ci...., ed are the d-dimensional coordinate directions, and co := Ex-D,||x]]
Additionally, we the standard O(-), 2(-) and @(-) hide universal constant factors. We say the al algorithm achieves superpolynomial convergence if it takes O (In((1))) iterations (for a constant 0) achieve e-error.
Here, sgn(>) if x 2 0, otherwise -1.
3

---

2.1 Data distribution assumption
Assumption DD a spherically symmetric distribution, i.e. if ~ D, then for any orthogonal malrix A, we have Ax ~ D.
Unlike the common finite dataset, our main assumption the data is the above. Such construction gives aero-margin separable dataset in our scheme. Moreover, our assumption includes the standard
Gaussian distribution (adopted in 8 53 45
sphere S Under this assumption, D Dw,v shares the same distribution for different pairs of w, v E IR as long as and are not parallel (i.e., H v).
54 32 ) and uniform distribution
Warm-up: Logistic Regression Case
In this section, we analyze the logistic regression setting, i.e., o w) = Txx. All proofs of this section are given in Appendix A For the linear classifier, we have the gradient expression as follows
y(x)x
V -Ex-D 1 cu(x)w
3.1 Convergence of gradient flow for logistic regression
Our main result about logistic regression is the following. The proof is given in Appendix A.6
Theorem Consider gradient flow for solving the problem
Denote
infit:
@l]w(1)]1
at 2 0}.
Under Assumption 7 we have
2
TST,
A.1+B. +1
cos 0(t)
2
t> T.
e2v/t Seyyt-T+C2t B2 12++1
Here A1
25p
01 = 22n
8(0) tan
A2
4ep
0, B2 = -2 tan
8(T) 2
(O]]
2
V0.6%
(TT][w([)) and C2 0.6
||w [[w(2]]
0.6
This result shows that as I + oo, the error metric 1 1-cos (t) converges to O, which implies w w(I) - v. i.e., the weight converges to the globally optimal direction. Additionally, the training goes through two stages: in the first stage, 1 cos (t) I O(e-A((f5 in the second stage, cos (()) S O(e ((e-0(eA))))) A2vV).
Next, we present an interesting characterization of the optimization trajectory: the weight norm goes through descending stage and ascending stage. This dlescending--scenneee pattern" can be established for deep linear nets as well (see Theorem later).
Lemma Denote T := infft:
allw(())l
0}. Under Assumption 1 have T and a ([))1
12 0, V K00, VI<T.
Ot
This lemma shows that the training dynamics be divided into stages: in the first stage, the norm ||w(t)] is decreasing; in the second stage, the norm ||w(t)] is increasing, The first stage might be non-existent if A| (0) /2/tt /tt > 0, and the second stage is always existent (i.e., T oo as stated in the lemma). The existence of the second stage implies that there is lower bound of the weight norm throughout training.
The lower bound of weight norm is not needed for establishing Theorem 7 (the conver- gence result in the logistic regression case), but will be crucial for multi-layer linear nets. The reason we present Lemmal is that analysis is essentially similar to the multi-layer nets case while easier understand.
Remark

---

3.2 Basic properties for the proof of Theorem
In this subsection, we describe a few technical propositions that will be used in the proof of Theorem Readers who care about the proof sketch can skip this part, and turn back to check these propositions we mention subsequently.
Proposition 1 Denote := Ex~D |x]]. Suppose o(x, w) w x and P(xx v'x 0}) 0. Then the function L(w) defined in Eq. (T) is c-Lipschitz continuous, Amaax (2) smooth, and convex but not strongly convex.
Generally speaking, gradient methods do not exhibit linear convergence rate for non-strongly convex functions [40]. However, the training dynamic enjoy faster convergence rates in terms of directional convergence, due to certain invariant properties (such as Proposition 2 below).
Proposition 2 Suppose Φ(x, w) = x and v x= 0}) <
Then the gradient flow for the problem Eq. ① satisfies the following properties: (i) v VL(()) for any E Rd. (ii) v w(() is increasing increases; (iii) (tt]l) is unbounded;
Similarly, the gradient descent for the problem in Eq. (I satisfies the following properties: (iv) if the learning rates are lower bounded, ie., Th 2 17- > 0, then v v/ w(n) is increasing as increases, and [|] (n) n is unbounded.
When Assumption
I holds, we can provide a more precise description of w()) and L(()) below:
Proposition 3 Under Assumption ! have: (i) [[VL(W)] co ExED, ||||| (ii) VL(av)
Ee-Dy V, V; (iii) lim v ((()) = +oc. (iv) If the learning rates are lower bounded, i.e.
Th 2 n- > 0, then limn-+oo v (n) +00.
Remark 2 This proposition shows that in the logistic regression case, we do not need to consider the case w(t) || (including 0), since we have [[)((t)) |l when w(t) || by (ii) in Proposition 3 Therefore, we only need to consider the case w(t) + 0 and w(t) R v Vt O.
3.3 Proof sketch of Theorem 1
We mainly consider the dynamics of cos 8 ((w, v), which is also employed in cos O())
22
28
50
43
(w()) (w())Tv) w(t) (L()(t))
(4)
Üt
(w(t]
In
Step 1: We have the analytic expression of I2 shown in Lemma below. This expression relies because the symmetry eliminates the collision among data points.
Assumption [
Lemma Under Assumption and if w + 0, then
(vv- (w VL(w)= --v -I (I--ww)) VL(w)= sin" 0(w, v)
(5)
Moreover, if additionally w I v, the above result implies
(Ia w w VL(w)=
Co [I - w w
(6)
π
From Lemma 2 and Eq. 4 we obtain that cos 0(E)
0 when w(t) * 0 and w(t) H v. by its derivative. Denote
St
Step 2: Next, analyze the remaining term [[w(t]] in Eq.
4l
1 0 [0@((())'
g( (()( = 2 at
w()) (L((())).
The following lemma describes the behavior of g(w(.)) Some properties in Lemma can be explained visually from Figure 2 in the Appendix.
5

---

Lemma 3 Under Assumption 1 the following hold:
(i) (w) S 0.3; (ii) 1f ( (w, v) n/ 7/2, then g( ((w) < O:
(ii)) 1f (/0(W, S 7/2, then 0g w) (00 v) <.
(iv) If0 < [w| - colcus 0 w.w with L = ExwDz ||x|| then g( cos fow v) >
2
Step 3: Finally, we bound [[w(t]] < | (w)ll if T, and I I 0.6(t T) if
t t> 7 from (i) in Lemma which shows two-phase directional convergence in Theorem
3.4 Convergence of gradient descent for linear regression
Now we turn to the gradient descent setting based on the previous results. The difficulty encounter that the arbitrary choice of learning rates each step may break the directional monotonicity in Lemma 2 as Eq. (8) reveals (See Appendix [ for the proof).
cos (n + + O(n) [|w(n + T)ll Th (v (w(n) (((n)/)ww//) v)w(n)) [((((n))
(8)
(Ilw(n + 1)ll w(n) w(n + 1)) cos cos
Fortunately, when v (nz) < 0, we have g(w) 2 0 by (ii) in Lemma implying that the first-phase directional convergence in the gradient flow case still holds.
Lemma 4 Under Assumption
suppose ((0) + and v w(0) < 0. Then have that
cos Cos 2 1 (1 cos (()) -BS
until cos (()) 2 0, where S == n
W1
A
Iw og
and 1+ccs A(0)
VA+E. "f
Hence, when (nn) stays in the "wrong" region that ((n) > 22, larger learning rate gives faster directional convergence to the region {w (((w.v) I x/2). Unfortunately, when ((n) S π 2/2, the directional dynamic becomes unstable and heavily relies the current learning rate. However, after simple calculation invoked from Lemma 2 we find that (Lemmal 12 in Appendix)
w [++ 1)]2 (w(n) (wn)nn((re w(n+1))² +
Co
sin" 0(n).
(10)
Combining Eq. (10) and Eq. (8). figure out
cos cos+((++)) cos ((n) = [w[++1)]l Co'la sin" 0(n)
3 sin 0(n) cos (nn)/
w 1)1l w w(n+1)
Hence, characterize sufficient condition in the remaining training period to guarantee the directional monotonicity. Moreover, we will show that such a condition can be satisfied when the weight norm |[w[n]] is large enough compared to the current learning rate.
Lemma 5 (A sufficient convergence condition) Under Assumption I if (() + 0, 0(0) + and there exists d 0, s.f.
[[([++1]]| (n)) w(++1)> (1 8)000 cos ((n)
VNEN,
(11)
then there exist constants A, B, > O such that
cos (n) 2 - (1 cos ((0)) e Bst
(12)
Here St == Ei= VA+E (né C..))
T1
= [/w( B 6(1+cns #0)) and C = 0.6/c8
(1+8)T
Furthermore, we can show the directional convergence with bounded learning rates as follows. Note that when [[](n)] 2 Cn + (1 ()conm/((2)) by (i) Proposition 3 Eq. [1] can be satisfied from
[ + (n) w(+1)) 2 22(((())) - n., VV(((n)))I) (1 8)cmna/

---

Once Tn I 7+,, then |w 2 R1 : 7- + con+/TT is sufficient to derive the convergence, We note that [[]]]]] 2 v [(n), and from (ii) in Proposition Saaaitioonnnnd and (iii) in Proposition the right term vT ('w(n) monotonically increases to infinity. Thus, after finite iterations, the sufficient convergence condition would be satisfied.
Theorem Under Assumption 7 for a bounded learning rate sequence {Th hi with 174 2 On 2
n- >-> cos (m) first converges following Eq. (9) until cos ((n)) 2 0 for some no 2 0. Then
there exists an n4 on such that w(n)) c7 + 70 /0/T, n. and cos (n) converges from n following Eq.
72
Remark 3 Generally, a 3--moooh objective loss has the learning rate constraint (0 < <イ< }) to guarantee convergence [40]. There is no such constraint because the purpose learning the direction instead of decreasing the loss. Furthermore, need to underline that the loss still converges. Since for large enough (w(n) (w))), the smoothness coefficient of the objective becomes certainly small and the bounded learning rate is naturally suitable guarantee convergence.
Comparison. Our convergence bounds provide a faster and non non-asymptotic directional convergence
rate exp (O( (o(-ve -)) (under constant learning rates, i.e., 7/2 (1)) compared O (1/ log t) in Soudry et al. [46, Theorem 5]. Additionally, previous results hold for a certain large t and the finite dataset with positive margin, but we show the behavior in the entire training dynamic. We think that the possible explanation is the benefit of the structured data in Assumption | Moreover, log p(t) with the max-margin solution w and almost bounded residual term p(t). We can implicitly obtain an analogous decomposition, but such a way would lose sight variation during the early training, such as the decreasing and increasing period of [|](l)]]- Furthermore, for gradient descent, directional convergence in previous results is built on the loss convergence [22] 24, 38] 39 (46.. Hence they need "small" learning rates with data-related upper bound. When data distributed well, derive the directional convergence directly under implicitly bounded learning rates and then obtain the loss
the prior technique proofs mostly employs the decomposition: w(1)
convergence from the directional convergence.
4 Deep Linear Networks
In this section, we extend the results of gradient flow to deep linear networks. For an N-layer linear network 6(x, w) WN ... Wix where (WN,.... W1), the objective is
min L (N) (W....... Wi) == Ex~D In [+te v(x)Wxx..WW
Every such network represents a linear mapping given by We (WN... ... Wi) E RR:
( (W (WI.... ..... WN) I [(" ExaDln in (1+c-olx)w.2
4.1 Main results for deep linear networks
key tool for analyzing the induced flow for we is established in Claim of Arora et al. [3]. Specifically, if the initial balancedness conditions
W (0) (0) (0) W,(0), = [,.,,. N hold, then we have the induced gradient flow with (.):):
(13)
Ow.(!)
201 (dL.)) 2- &
(ww(()) -N ()) (1( (L.))(w(()) dw
(14)
Øt
dw
Such an initialization technique is common for linear networks 2
18
19 Claim 4 in Arora
et al. [2] discusses the importance of (nearly) balanced initialization for deep linear networks. For equal-width linear nets, orthogonal intialization is special case balanced initialization, and was shown to perform better than Gaussian initialization [19].
Before presenting results of deep linear networks for general N, we first present the result for the simple case N = 2:
7

---

Proposition 4 Under Assumption 7 and the initial balancedness condition Eq. (.) + 0 and (0) * k, we obtain the directional convergence as follows:
13
if = 2,
2
with C1 1 1 cos 8
cos (() C/e2cot/=
cos 0(D)
Next, we present a lemma which is extension of Lemma Ioo the deep linear case: both lemmas present the "descending-thens thenann-nnn-n--niinggg pattern of the weight norm.
Lemma 6 Denote T := inf{t: Ollw. (ww(())l//0t 2 0}. We have T < co, and a @e (+)
2 O, V12T
(15)
Ōt
O, Vt<T.
The main result for the deep linear net case provides the convergence rate of the gradient flow.
Theorem Under Assumption 7 and the initial balancedness condition Eq. (3). if > we (0) +
O and 0(0) + n, we obtain two-phase convergence below. With the T defined in Lemma 0 we have
2
TS
C1 + 1) +1
cos
2
t t>t.
(a(1I-T)+B, +1
Here A (N - 2). Bi [|]] --1 Ci
I-cos 010) and A2 = 2co (T)]==
1+cos A(0)
((T) B2 = -2nn tan 2 and a = 2/((N - m)
In addition, we have the upper bound that
2
cos 0(t) 2 (F(0.6G++))*72---M22
where D = (0]] E -n tan 8(0) and F
4cg
0.
Theorem implies cos (()) undergoes two stages: polynomial convergence stage and exponential convergence stage. Finally, for the initialization ((0) we have that 0(1) ग, 14 2 0, and (.) 0 but never hits the origin by the lower bound in Eq. 17
Remark 4 We briefly discuss how different items affect the convergence rate of both stages. The convergence speed of the second stage is positively correlated with A2, which is positively correlated with co and [[w((T))] (2)] (when the number of layers N 2 3). Scaling up the data can increase the expected data norm Co. thus increasing Ag and the convergence speed. It is not clear, though, how to increase [[)][))] since it depends on an unknown transition time T. The convergence speed of the first stage is positively correlated with A and 1/ L/B We skip the discussions of this stage.
Remark 5 Since we need to cover the worse case during optimization, our bound may seem loose in two possible cases. First, when S T. we use the lower bound in Eq. (17) capture the decreasing period of w..() (.).))l. Actually, [t)]l]] may descend to a certain value that is higer than the lower bound in Eq. (17) before ascending. Second, when 2 T, note that cos f(t) 1 except we(0) kv for k < by Theorem 3 We can guarantee [!we(!)] + because v "we(t) is increasing after some time (but not always). Hence, the convergence could be faster when [[we([)] increases much, but we only treat such scheme lower bounded by [ww(T)ll)
Comparison. Our global convergence rate results for deep linear networks neither require small training loss [1 23] nor presume convergence of loss and weight direction [17] 38). Moreover, our results do not require overparameterization 9 IT 19]. However, we need the exact initial balancedness condition
mainly provided asymptotic directional convergence to the maximum margin solution given zero classification error at the beginning. We could obtain an explicit global directional convergence including the early training dynamic. Our directional rates could be linear when the induced weight norm begins increasing, which is faster than the polynomial convergence rate of the surrogate loss function obtained in [37 Theorem 4.3]. However, our results heavily depend on the benign training data assumption and the linear net structure compared to Lyu and Li [37]. Yun et al. [51].
3 Previous works [37 21 51

---

4.2 Technical lemmas for analyzing deep linear networks
We present a series of technical results that will be used for proving Lemma 6 and Theorem Some are extensions of those for logstic regression, and some are new for deep nets.
Lemma Under Assumption and the initial balancedness condition Eq. 13 if (o()) + 0, then
ô cos (ww(())))))))))))))))))()))))) co sin ((w,((), v) ||wa(t)]
(16)
Öt
The main difference from the logistic regression case is that the dependence of weight norm [[wa(t) is reversed. Larger (t)ll gives faster convergence for the deep linear networks when N 2 3, while no influence for N 2, and for = 1 is opposite (i.e. larger ||we(t)] gives slower convergence).
We then provide a few properties of the weight norm during training.
Lemma Under Assumption D and the initial balancedness condition Eq.
with we(O) + O, we
have the following two properties:
(i) Suppose N 2. For any
2 have
(1 (Iw=(0)]l & + 0.6t
2 ||we(t)]
xx > 0. (17) [[[w<(0]] (N -NN-20 (N-2)cot)
(ii) Suppose Ö|| (t)) 0 with (tat # 0 for some to N 0. Then Ōg(w. (to)) 0.
We briefly explain how to use Lemma 8 to prove Lemma 6 which consists of two properties: Eq. 15)
and T cc. First, Eq. (15) an immediate consequence of Part (ii) of Lemma g as well as calculus fact Lemma 10 (see Appendix). This proof approach is similar to that for the logistic regression case. Second, T
requires different proof approach from the logistic regression case: the latter is due to unbounded weight norm and the fact that zero-norm weight is non non- statiiotton,,, but for deep linear case the latter does not hold (the origin is a saddle point). Instead, we rely on Part (i) of Lemma 8 to prove T < oc by contradiction. More specifically, assume T = oc, i.e., |[,(t) (t) is decreasing for all then (t)ll converges to a finite value. We will use Part (i) of Lemma 8 and Part (iv) of Lemma 3 to derive contradiction. See details in Appendix B.2
4.3 Proof of Theorem
Proof: Using Lemma and the lower bound of wwe (t)l in Lemma 8 obtain
1 1+ cos (tt)
+ cos (0))
1
A + B
In
2 (N 2)
In
2 1 cos (t))
2 cos (0))
B1
This implies
2
cos (()) 2 CA 1)a +1 VA 2 0.
(18)
Notice that 18 holds for the whole training period, thus surely holds for T.
Next, we will show a stronger convergence rate for the peoriod t > T, i.e., the second part of the theorem. According Lemma 0 we have
W [t)l 2 V T.
Hence (f)l 2 ||we (1) Vt 2 T. Therefore,
1 1 + cos (t) In 1 cos (T)
In
+ cos (T))
2 w. (T) [T) 1-
CD
T).
2 cos (t)
2
cos 0tt) 1 c +)+ Ra +1 Vt> T.
For the third part, using the upper bound of [[we(()] in Lemma
we obtain
+ cos 0(1)
In 1 + cos (0))
200
(0..6t + D) - -
<
1 - cos 0())
2
cos (0)
0.6NN

---

16
Trde
31
PHL aE Peree---Pr .e
34
-25
13
10
10
(a) Linear predictor
(b) Four-layee layer deep lincar network
Figure 1: Simulation of (deep) linear network with x (( v= (0. 1T_T)_ (a): Linear predictor. We show our lower bounds Theorem network. We also show our lower and upper bounds in Theorem 3 at r = 0 and n = 18000. In each experiment, we plot angle variation, loss and weight norm in sequence.
and 5000. (b): Four-layer deep linear
This implies
2 (0.6444)))) -
cos cos@(t) $
5
Experiments
In this section we conduct experiments to verify our theoretical analyses. We consider training linear classifier and 4-layer linear network under the logit loss simple dataset with x ~ ((*)) and yxx) sgn(v x) with v = (0, 1)T. We use common stochastic gradient descent (SGD) with the batch size 1000 and the constant small learning rate 10 Moreover, we choose an initial value w w(0) = (0) = (0.6, 0.8) In the deep linear network, we set (0) = x (O) 1 with || = 1, = 2, ......N and in = (0 to satisfy the balancedness conditions Eq. (13.. The results are shown in Figure
theorems show. We construct
Figure shows the optimization period for linear classifiers. We also plot convergence bounds obtained in Theorems [] Although we do not give convergence for SGD, our bounds in gradient flow still roughly match the directional convergence in practice, and the weight norm |w(n)] indeed goes through decreasing and increasing period. Figure Ib depicts the dynamic for the deep linear networks. We also plot three convergence bounds Theorems 3 which roughly match the actual behavior. The weight norm [n)]l still goes through the decreasing and increasing period, and could observe a distinct stuck period when 3 < 17 S 10 as the lower bound shown Lemma [ Moreover, the loss decreases slowly when [[][]]] is small, but cos f(t) still has considerable growth. Thus previous loss-based analysis may neglect potential variation of the accuracy we most concern. Furthermore,
a more rigorous understanding of [|w(n)] may give more precise rates in the late training period (t. 2 20).
Conclusion
In this work, have studied the training dynamic of (deep) linear networks binary classification tasks. Specifically, we focus the gradient flow and gradient descent methods under population loss. We have proved exact directional convergence for (deep) linear networks in the entire training process on spherically symmetric data. Moreover, we have characterized the descent and ascent behavior of the induced weight norm theoretically. Such phenomenon also observed numerical experiments. We hope that our limited view of directional convergence would bring a better understanding of (linear) neural networks.
10

---

Acknowledgments and Disclosure of Funding
Lin and Zhang have been supported by the National Key Research and Development Project of China (No. 2018AAA0101004) and Beijing Natural Science Foundation (Z190001).
References
[1] Zeyuan Aluen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via weer-parameterization. In International Conference on Machine Learning, pages 242-252. PMLR, 2019.
[2] Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. International Conference on Learning Representations, 2018.
[3] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterivation. International Conference on Machine Learning, pages 244-253, PMLR, 2018.
[4] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grainee analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pages 322-332. PMLR, 2019.
[5] Francis Bach and Lenaic Chizat, Gradient descent on infinitely wide neural networks: Global convergence and generalization. arXiv preprini arXiv:21 10.08084, 2021.
[6] Bubacarr Bah, Holger Rauhut, UIrich Terstiege, and Michael Westdickenberg. Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers. Information and Inference: A Journal of the IMA, 02 2021. ISSN 2049-8772, doi: 10.1093/ imaiai/inna039. BtRLhttps:// //doi. org 10. 1093/ wwt.11099mmmaaa.. wwl.amaaaaaaaaa.a iaaa039.
[7] Peter Bartlett, Dave Helmbold, and Philip Long. Gradient descent with identity initializa- tion efficiently learns positive definite linear transformations by deep residual networks. In International conference on machine learning, pages 521-530. PMLR, 2018.
[8] Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a convnet with gaussian inputs. In International conference machine learning, pages 605-614. PMLR, 2017.
[9] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss, In Conference on Learning Theory, pages 1305-1338. PMLR, 2020.
[10] Tian Ding, Dawei Li. and Ruoyu Sun. Sub-optimal local minima exist for almost all over- parameterized neural networks. arXiv preprint arXiv: vrXiiv:911.01444 1.01413, 2019.
[11] Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In International Conference on Machine Learning, pages 1655-1664. PMLR, 2019.
[12] 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.
[13] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2018.
[14] Armin Eftekhari. Training línear neural networks: Non-local convergence and complexity results. In International Conference on Machine Learning, pages 2836-2847, PMLR, 2020.
[15] Jonathan Frankle, David J. Schwab, and Ari S. Morcos. The early phase of neural network training. International Conference on Learning Representations, 2020. URI. https
//openreview

---

[16] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias terms of optimization geometry. In International Conference on Machine Learning, pages I 1832-1841. PMIR, 2018.
[17] Suriya Gunasekar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pages 9461-9471, 2018.
[18] Moritz Hardt and Tengyu Ma. Identity matters in deep learning. International Conference on Learning Representations, 2017.
[19] Wei Hu, Lechao Xiao, and Jeffrey Pennington. Provable benefit of orthogonal initialization in optimizing deep linear networks. In International Conference on Learning Representations, 2019.
[20] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 3571-8580, 2018.
[21] Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. In 7th International Conference on Learning Representations, ICLR 2019, 2019.
[22] Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference Learning Theory, pages 1772-1798. PMLR, 2019.
[23] Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. Ad- vances in Neural Information Processing Systems, 33, 2020.
[24] Ziwei Ji and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Algorithmic Learning Theory, pages 772-804. PMLR, 2021.
[25] Ziwei Ji, Miroslav Dudik, Robert Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Conference on Learning Theory, pages 2109-220 2136. PMLR, 2020.
[26] Kenji Kawaguchi. Deep learning without poor local minima. In Advances in neural information processing systems, pages 586-594, 2016.
[27] Thomas Laurent and James Brecht. Deep linear networks with arbitrary loss: All local minima are global. In International Conference on Machine Learning, pages 2908-29111 2018.
[28] Chris Junchi Li, Mendgi Wang. Han Liu, and Tong Zhang. Diffusson approximations for online principal component estimation and global convergence. Advances in Neural Information Processing Systems, page 646, 2017.
[29] Chris Junchi Li, Mengdi Wang, Han Liu, and Tong Zhang. Near-optimal stochastic approxima- tion for online principal component estimation. Mathematical Programming, 167(1):75-97, 2018.
[30] Dawei Li, Tian Ding, and Ruoyu Sun. On the benefit of width for neural networks: Disappear- ance of bad basins, 2021.
[31] Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pages 81 5157-8666, 2018
[32] Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Learning over-parametrized two-layer neural networks beyond ntk. In Conference on Learning Theory, pages 2613-2682, PMLR, 2020.
[33] Shiyu Liang, Ruoyu Sun, Jason Lee, and R Srikant. Adding one neuron can eliminate bad local minima. In Advances in Neural Information Processing Systems, pages 4355-4365, 2018.
12

---

[34] Shiyu Liang, Ruoyu Sun, Yixuan Li. and Rayadurgam Srikant. Understanding the loss sur- face of neural networks for binary classification. In Jennifer Dy and Andreas Krause, editors. Proceedings of the 35th International Conference on Machine Learning, volume 80 of Pro- ceedings of Machine Learning Research, pages 2835-288 2843. PMLR, 10-15 Jul 2018. URL httpp::/proceeednggs mlr wwwps/ewsssoe. httpss//v0/iianggle html
[35] Shiyu Liang, Ruoyu Sun, and R. Srikant. Revisiting landscape analysis in deep neural networks: Eliminating decreasing paths to infinity, 2019.
[36] Haihao Lu and Kenji Kawaguchi. Depth creates no bad local minima. arXiv preprint arXiv:1702.0858/ 2017.
[37] Kaifeng Lyu and Jian Li, Gradient descent maximizes the margin of homogeneous neural networks. International Conference on Learning Representations, 2019.
[38] Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3420-3428. PMLR, 2019.
[39] Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with a fixed learning rate. The 22nd International Conference Artificial Intelligence and Statistics, pages 3051-3059. PMLR, 2019.
[40] Yuri Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science Business Media, 2013.
[41] Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein. On the loss landscape of a class of deep neural networks with no bad local valleys. arXiv preprint arXiv:1809.1074 2018.
[42] Maher Nouiehed and Meisam Razaviyayn. Learning deep models: Critical points and local openness. arXiv preprint arXiv: 02966, 2018.
[43] Mary Phuong and Christoph Lampert. Towards understanding knowledge distillation. In International Conference on Machine Learning, pages 5142-5151. PMLR, 2019.
[44] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. arXiv preprint arXiv:1712.08800 2017.
[45] Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference on Machine Learning, pages 4433-4441. PMLR, 2018.
[46] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Reseurch, 19(1):2822-2878 2878, 2018
[47] Ruo- Yu Sun. Optimization for deep learning: An overview. Journal of the Operations Research Society of China, pages 1-46, 2020.
[48] Ruoyu Sun, Dawei Li, Shiyu Liang, Tian Ding, and Rayadurgam Srikant. The global landscape of neural networks: An overview. IEEE Signal Processing Magazine, 37 2020.
[49] Luca Venturi, Afonso Bandeira, and Joan Bruna. Spurious valleys in two-layer neural network optimization landscapes. arXiv preprini 1802.06384 2018.
[50] Gilad Yehudai and Ohad Shamir. Learning single neuron with gradient methods. In Conference on Learning Theory, pages 3756-3786. PMLR, 2020.
[51] Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view on implicit bias in training linear neural networks. In International Conference Learning Representations, 2021. URL httphtttt//ppereviiiii http:://pppereeeieeeeeeee/rrrmr wwtp:/neffooomim/////// -iMMQH
[52] Li Zhang. Depth creates no more spurious local minima. arXiv preprint arXiv: 1901.09827 2019.
13

---

[53] Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for me-hidden-layer neural networks. In Proceedings of the 34th International Conference Machine Learning-Voon Volume 70, pages 4140-4149. JMLR. org, 2017.
[54] Mo Zhou, Rong Ge, and Chi Jin. A local convergence theory for mildly over-parameterized two-layer neural network. In Conference on Learning Theory, pages 4577-4634 PMLR, 2021.
14


Reviews:
[{"review_id": "eq9Lp2acIxV", "reviewer": "Reviewer_X2Dr", "summary": "The authors study the directional convergence of linear and deep linear networks under a specific setting:  data is separable with zero margin and assumed to be spherically symmetric, and the model is trained by gradient flow/descent with the logit loss. In this setting, the authors improve upon previous results by showing fast directional convergence (superpolynomial). Moreover, unlike previous works the authors are able to analyze the directional dynamics along the entire training process without relying on over parametrization or zero error assumption.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the authors present an interesting analysis of directional convergence in a restricted setting, which improves upon previous work. My main concern is with the highly narrow scope for which the results apply, as the authors themselves have pointed out (i'd like to commend the authors for providing an honest description of the limitations of their work). \nThe technical aspect of the derivation rely heavily on the spherically symmetric distribution assumption (assumption 1 in the paper), absent from previous work , rendering the results somewhat incremental (a more complete theoretical handle of convergence in exchange for a more restrictive setting). \n\nI'd like to add that i am no expert in this particular area, hence i will leave the more in depth technical review for other more qualified reviewers. \n\nquestion:\n\nThe authors relate assumption 1 to the benefit of data augmentation and preprocessing. Can they elaborate on this given that recent papers (Neha S et al*) have pointed to the adverse effects of data whitening as preprocessing? How is data augmentation related? \n\n*Neha S. Wadia, Daniel Duckworth, Samuel S. Schoenholz, Ethan Dyer, Jascha Sohl-Dickstein, \"Whitening and second order optimization both make information in the dataset\nunusable during training, and can reduce or prevent generalization\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They are adressed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "_rj7xSr4mMD", "reviewer": "Reviewer_8tLY", "summary": "In this paper the authors present a convergence proof of linear neural networks trained with a logit loss. The analysis is based on previous works of Telgarsky, and is only concerned with binary classification of linearly separable points with 0 margin. In addition the authors make the assumption that the data distribution of the points are isotropic namely, spherically symmetric. With this the authors prove a directional convergence result, that states while the parameters magnitude approaches infinity as seen in previous works with separable data and logit losses,  the direction of the parameters converges to the orthogonal vector to the decision hyperplane. The authors present the result for shallow (1 layer) networks as well as deep linear networks. In addition to convergence the authors observe a trend of decreasing and then increasing parameter magnitudes that they also analyze empirically.\n\n", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I find this paper interesting and provides a nice analysis of a new data distribution setting (0-margin separable data). At the same time, some of the assumptions of this work make it too restrictive and similar to previous art. I find the biggest limitation of this work to be the assumption that the data distribution is isotropic and the development of the theory only with respect to a distribution loss. Namely, a spherically symmetric data assumption is very stringent and is very very far from any interesting data manifold of real data. Even for normalized datasets where the covariance is whitened the assumption that the data is spherically symmetric implies that the dataset contains no directionally specific clusters or variation in density which I find to be very far from any real dataset example. Additionally I recommend the authors spend more time to motivate the key discoveries of this work and their importance, as well as tighten up some of the writing as there are many grammatical issues that occasionally obstruct meaning. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not fully address the limitation and the implication of their data distribution assumption of spherically symmetric data.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "X7f44r6sV1", "reviewer": "Reviewer_JkRT", "summary": "The authors study both shallow and deep linear networks under the assumption of spherically symmetrical input data. They show that gradient descent provides a super-polynomial convergence rate in this setting, which does not rely on any assumptions on the margin of the data or over-parameterization of the network. They provide some experiments demonstrating their results when their assumptions exactly hold, as well as with deep non-linear activation networks where their assumptions no longer hold. ", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, while the theoretical analysis is sound in this work, the impact of the work is unclear to me. In particular, since there are some restrictive data assumptions upon which the analysis relies, it doesn't appear that the analysis is practically useful for anything. That being said, I appreciate the fact that there is no assumption on the margin or overparameterization. \n\nThe purpose of experiments on non-linear networks is not very clear to me. If anything, it demonstrates that the general intuitions on super-polynomial convergence that were derived under different assumptions do not carry over when these assumptions are removed. Therefore there is a question of what practical utility the theory provides to neural networks as they are used in practice.  Furthermore, it is strange to me that only test error is displayed, rather than training error, since the theory makes claims about the convergence of training loss rather than test loss. It would be good for the authors to clarify these experiments a bit more. \n\nProposition 1: The loss function L(w) is only convex in the shallow linear network case as discussed in Section 3. In the deep linear network case where w := (W_1, ..., W_n), the loss is not convex with this parameterization (though it is convex in w_e := (W_n...W_1)^T). This should be clarified. \n\nThis is a small thing, but it seems as though most of the claims in Section 4 apply to N > 2 case, while Section 3 applies to N=1 case. However, the N=2 case is not explicitly discussed. For completeness I think the authors should be clear about this specific case. \n\nThere are also grammatical errors scattered throughout the text, which should be corrected. I list some examples below:\n\nLine 31: \"However, these work consider\" --> \"However, these works consider\"\nLine 233: \"The intuitive of a)\" --> \"The intuition of a)\"\nLine 235:  \"...weight is the multiply of the other...\" --> \"...weight is the product of the other...\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "NHXZmp04WR", "reviewer": "Reviewer_Ce73", "summary": "The paper analyzes the setting of shallow and deep linear neural networks under gradient flow and gradient descent and deduces a superpolynomial directional convergence guarantee.\nThe result is proven under one assumption: spherically symmetric data distribution. Additionally, in the deep linear networks case, it requires a balancedness condition on the initialization.\nAmong the existing convergence analysis of binary classification on separable data, the current result diverges by examining the dynamics of minimizing the population logit loss (rather than empirical loss) and tests the case of zero margin separable data. It mitigates some assumptions like prior convergence to zero classification error or overparameterization.\nThe findings are shown empirically by experiments on both benign and real-world datasets and also partially on non-linear fully-connected ReLU networks. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\n\nIn my view, the paper addresses a fundamental topic for better understanding the theory behind deep neural networks --- convergence analysis. Even though the setting is rather restrictive, the work takes a step forward in understanding convergence in these kinds of models. Further, it mitigates assumptions of previous works with a similar setup and therefore presents an important contribution in this field. \nHowever, there are several issues with the current version that in my opinion should be treated prior to publication.\n\nFirst, regarding the problem setup. The spherically symmetric distribution is quite a restrictive assumption. Together with assuming separability, it is worth supporting both with stronger motivation. For instance, giving examples for real-world problems that satisfy or nearly achieve those assumptions or preprocessing methods that can approximate this form of the data.\nFurthermore, analyzing the population loss instead of empirical loss is a bit nonstandard. In my opinion, it requires justification since in real-world problems we usually don't have access to the distribution but to a finite set of samples, which is the case that is usually addressed. \n\nRegarding the experiments on MNIST and CIFAR, it is mentioned that: \"the datasets do not satisfy our data assumption generally\". Despite the fact that the reported results do show a positive effect of the acceleration methods. In my view, the theory presented in the paper cannot provide a valid justification for the phenomenon if the data does not of the correct form of the proofs. Therefore, showing it is a bit out of the topic as I see it. Demonstrating these acceleration methods on datasets that do satisfy the data assumption would be better since the presented theory could support its reasoning. \n\nOverall, the contribution of the paper justifies publication in my opinion. Although I think clarifying the reasoning for the setting and focusing on the direct implications of its results are things that the authors should address prior to publication.\n\n### Post-rebuttal update\nAfter reading the author's response and all other comments, my opinion remained as before. I believe the paper is borderline but tend to accept. In my view, the main drawback is still the limited significance of the results within the setting presented in the paper. Other criteria, however, seem to assess the paper positively, as the technical aspects of the paper and the results are solid. Therefore, I keep my score slightly above the acceptance threshold.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work mainly focus on the theoretical aspect of deep neural networks. If there are implication that should be addressed I think they only belong to the impact of deep learning in general and not directly to this work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is borderline.  Reviewers generally agreed that the theoretical analysis (main contribution) is technically solid and delivers strong results, but on the other hand is limited to a very restricted setting of spherically symmetric data distributions.  In addition, several reviewers felt that the empirical section on non-linear neural networks is somewhat disconnected from the theory (which applies to linear neural networks), and the value it adds to the paper is limited.  While I share the aforementioned concerns, I believe the state of deep learning theory is such that strong analyses of restricted settings are still of interest, and therefore recommend publication.  I encourage the authors to reconsider the necessity of some of their experiments and defer to the appendix those that do not significantly contribute to the main message of the paper.



Decision: Accept (Poster)