Faster Directional Convergence of Linear Neural Networks under Spherically Symmetric Data
Year: 2021

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.

text: 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.

heading: 1 Introduction
text: 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, a number of works proved the convergence of gradient methods to global minima for ultra-wide neural networks [1, 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 a global minimum near a random initial point, thus staying in the local region can still result in 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 is 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 to understand GD for deep linear nets. A number of works analyzed linear networks with the square loss. Bartlett et al. [7] provided that gradient descent converges to the target matrix at a 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 if the initialization has a positive “deficiency margin" and is nearly balanced. Later, a few works followed a similar idea to neural tangent kernel (NTK) [20] to establish convergence analysis. Du and Hu [11] showed GD with Gaussian random initialization converges to a global minimum at a 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.
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 (NeurIPS 2021).
In this work, we are interested in the classification task with binary cross-entropy loss. To our knowledge, there was no non-local convergence analysis of gradient flow for deep linear nets in such a scheme.
Deep linear nets with logit loss: final-phase analysis. Several recent works [17, 38, 23, 21, 37] studied the exponential-type loss for deep linear networks. Specifically, Gunasekar et al. [17], Nacson et 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-margin solution under the assumption that the initial point has already obtained zero classification error (weaker assumption than [17, 38]), 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.

heading: 1.1 Our Contributions
text: In this paper, we analyze gradient flow for deep linear networks with logit loss (i.e. binary crossentropy loss). The main contributions of this paper are summarized as follows:
• Convergence result. We prove the global convergence of gradient flow for minimizing a 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 on 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 θ(t) as the angle between we(t) and v, where we(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(θ(t)), that is, cos(θ(t)) ≥ 1−O ( (N1t) − 2N1π ) ,
where N1 + 2 is the depth of the deep linear network. In the second phase, we have linear convergence rate of cos(θ(t)), that is, cos(θ(t)) ≥ 1− eO(−t). And the second phase begins when the induced weight norm changes from descending to 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, it 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.

heading: 1.2 Additional Related work
text: Directional convergence for exponentially-tailed loss. Previously, we mentioned a 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 [22, 24, 25, 38, 39, 46, 16], it is shown that for binary classification problems with exponential-type loss (which can be viewed as the 1-layer 1-linear-neuron net case) and linearly separable data, GD converges to the `2 maximum margin direction. These works assume there is a positive margin. Ji and Telgarsky [22], Ji et al. [25] also consider a non-separable case, but still requires a positive margin in the “separable part”. Moreover, some works [21, 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. [51] 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 a convex max-margin 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 is vacuous in our zero-margin setting.
More discussions on non-local analysis of deep linear nets with quadratic loss. We mentioned Eftekhari [14] earlier; here we add more discussions. Besides the main difference in the loss functions, there are two other differences between Eftekhari [14] 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 a constrained subset, not necessarily the global minimizer (see Appendix F in [14] for detail).
Global landscape analysis. In our work, the term “non-local analysis” should actually be called “non-local convergence analysis”. There is another line of works on “non-local landscape analysis” (see, e.g., [26, 36, 27, 42, 52, 41, 30, 10, 34, 33, 35, 49, 44] and the surveys [48, 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.

heading: 2 Preliminaries
text: We consider a binary classification problem where the data are generated as follows. Let v ∈ Rd be a fixed vector satisfying ‖v‖ = 1. The input data point x ∈ Rd is sampled from a distribution D and the label for each x is y(x) = sgn(v>x) ∈ {−1,+1} 1.
Suppose we want to learn the parameter w for a predictor φ(·,w) : Rd → R (the specific form of φ will be discussed later). We use the population logit loss `(z) := ln(1 + e−z) (binary cross-entropy) with z(x,w) = y(x) · φ(x,w). The parameter is learned by solving the optimization problem
min w
L(w) := Ex∼D ln ( 1 + e−y(x)φ(x,w) ) . (1)
We focus on the following standard gradient methods.
1) Gradient flow: We initialize w(0), and for every t > 0 let w(t) be the solution of the differential equation: ẇ(t) = −∇L(w(t)). 2) Gradient descent: We initialize w(0) and set a sequence of positive learning rates {ηk}∞k=1. At each iteration n > 0, we do a single step in the negative direction of the gradient, that is, w(k + 1) = w(k)− ηk∇L(w(k)).
Notation. We denote vectors by lowercase bold letters (e.g., u,x,v). Moreover, ‖ · ‖ denotes the standard `2-norm for a vector, or the spectral norm for a given matrix. Let Σ = Ex∼Dxx> be the population covariance matrix, and λmax(A) be the maximum eigenvalue of a real symmetric matrix A. We by Sd−1 denote the surface of an d-dimensional unit sphere, and by Ik the k-dimensional identity matrix.
We let w := w/‖w‖ whenever ‖w‖ 6= 0. Given vectors w = (w1, . . . , wd)> ∈ Rd and v = (v1, . . . , vd) > ∈ Rd, we let θ(w,v) := arccos [ w>v/ (‖w‖ · ‖v‖) ] ∈ [0, π] denote the angle between w and v, θ(t) := θ(w(t),v) and θ(n) := θ(w(n),v). We let Dw,v be the marginal distribution of x = (x1, . . . , xd)> on the subspace spanned by two linearly independent vectors w,v (as a distribution over R2), and Dv similarly. Let D2 := De1,e2 where e1, . . . , ed are the d-dimensional coordinate directions, and c0 := Ex∼D2‖x‖. Additionally, we use the standard O(·),Ω(·) and Θ(·) to hide universal constant factors. We say the algorithm achieves superpolynomial convergence if it takes O (lnα(1/ )) iterations (for a constant α > 0) to achieve -error.
1Here, sgn(z) = 1 if z ≥ 0, otherwise −1.

heading: 2.1 Data distribution assumption
text: Assumption 1 D is a spherically symmetric distribution, i.e., if x ∼ D, then for any orthogonal matrix A, we have Ax ∼ D.
Unlike the common finite dataset, our main assumption on the data is the above. Such construction gives a zero-margin separable dataset in our scheme. Moreover, our assumption includes the standard Gaussian distribution (adopted in [8, 53, 45, 54, 32]), and uniform distribution on a sphere Sd−1. Under this assumption, Dw,v shares the same distribution for different pairs of w,v ∈ Rd as long as w and v are not parallel (i.e., w ∦ v).

heading: 3 Warm-up: Logistic Regression Case
text: In this section, we analyze the logistic regression setting, i.e., φ(x,w) = w>x. All proofs of this section are given in Appendix A. For the linear classifier, we have the gradient expression as follows
∇L(w) = −Ex∼D y(x)x
1 + ey(x)w>x . (2)

heading: 3.1 Convergence of gradient flow for logistic regression
text: Our main result about logistic regression is the following. The proof is given in Appendix A.6.
Theorem 1 Consider gradient flow for solving the problem (1). Denote T = inf{t : ∂‖w(t)‖ 2
∂t ≥ 0}. Under Assumption 1, we have
cos θ(t) ≥  1− 2 eA1t+B1 + 1 , t ≤ T,
1− 2 eA2 √ t−T+C2+B2 + 1 , t > T.
Here A1 = 2c0π‖w(0)‖ > 0, B1 = −2 ln ∣∣∣tan θ(0)2 ∣∣∣, A2 = 4c0√0.6π > 0, B2 = −2 ln ∣∣∣tan θ(T )2 ∣∣∣ − 4c0‖w(T )‖ 0.6π , and C2 = ‖w(T )‖2 0.6 .
This result shows that as t→∞, the error metric 1−cos θ(t) converges to 0, which implies w(t)→ 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) ≤ O(e−A1t); in the second stage, 1− cos θ(t) ≤ O(e−A2 √ t).
Next, we present an interesting characterization of the optimization trajectory: the weight norm goes through a descending stage and an ascending stage. This “descending-ascending pattern” can be established for deep linear nets as well (see Theorem 3 later).
Lemma 1 Denote T := inf{t : ∂‖w(t)‖ 2
∂t ≥ 0}. Under Assumption 1, we have T <∞, and
∂‖w(t)‖2
∂t
{ ≥ 0, ∀ t ≥ T. < 0, ∀ t < T. (3)
This lemma shows that the training dynamics can be divided into two 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 ∂‖w(0)‖2/∂t ≥ 0, and the second stage is always existent (i.e., T <∞ as stated in the lemma). The existence of the second stage implies that there is a lower bound of the weight norm throughout training.
Remark 1 The lower bound of weight norm is not needed for establishing Theorem 1 (the convergence result in the logistic regression case), but will be crucial for multi-layer linear nets. The reason we present Lemma 1 is that its analysis is essentially similar to the multi-layer nets case while easier to understand.

heading: 3.2 Basic properties for the proof of Theorem 1
text: In this subsection, we describe a few technical propositions that will be used in the proof of Theorem 1. Readers who care about the proof sketch can skip this part, and turn back to check these propositions if we mention subsequently.
Proposition 1 Denote c := Ex∼D ‖x‖. Suppose φ(x,w) = w>x and P ({x : v>x = 0}) = 0. Then the function L(w) defined in Eq. (1) is c-Lipschitz continuous, 14λmax(Σ)-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) = w>x and P ({x : v>x = 0}) < 1.
Then the gradient flow for the problem in Eq. (1) satisfies the following properties: (i) v>∇L(w) < 0 for any w ∈ Rd. (ii) v>w(t) is increasing as t increases; (iii) {‖w(t)‖}t≥0 is unbounded; Similarly, the gradient descent for the problem in Eq. (1) satisfies the following properties: (iv) if the learning rates are lower bounded, i.e., ηn ≥ η− > 0, then v>w(n) is increasing as n increases, and {‖w(n)‖}∞n=0 is unbounded.
When Assumption 1 holds, we can provide a more precise description of v>w(t) and∇L(w) below:
Proposition 3 Under Assumption 1, we have: (i) ‖∇L(w)‖ ≤ c0 = Ex∈D2‖x‖; (ii) ∇L(av) = Et∼Dv |t| 1+ea|t|
v; (iii) limt→∞ v>w(t) = +∞. (iv) If the learning rates are lower bounded, i.e., ηn ≥ η− > 0, then limn→∞ v>w(n) = +∞.
Remark 2 This proposition shows that in the logistic regression case, we do not need to consider the case w(t) ‖ v (including 0), since we have ∇L(w(t)) ‖ v when w(t) ‖ v by (ii) in Proposition 3. Therefore, we only need to consider the case w(t) 6= 0 and w(t) ∦ v,∀t ≥ 0.

heading: 3.3 Proof sketch of Theorem 1
text: We mainly consider the dynamics of cos θ(w,v), which is also employed in [29, 28, 50, 43].
∂ cos θ(t) ∂t = − 1
‖w(t)‖︸ ︷︷ ︸ I1
· ( v − ( w(t)>v ) w(t) )>∇L(w(t))︸ ︷︷ ︸ I2 . (4)
Step 1: We have the analytic expression of I2 shown in Lemma 2 below. This expression relies on Assumption 1, because the symmetry eliminates the collision among data points.
Lemma 2 Under Assumption 1 and if w 6= 0, then
− ( v − ( w>v ) w )>∇L(w) = −v> (Id −w w>)∇L(w) = c0 sin2 θ(w,v)
π . (5)
Moreover, if additionally w ∦ v, the above result implies − ( Id −w w> ) ∇L(w) = c0
π
( Id −w w> ) v. (6)
From Lemma 2 and Eq. (4), we obtain that ∂ cos θ(t)∂t > 0 when w(t) 6= 0 and w(t) ∦ v. Step 2: Next, we analyze the remaining term ‖w(t)‖ in Eq. (4) by its derivative. Denote
g(w(t)) := 1 2 · ∂‖w(t)‖ 2 ∂t = −w(t)>∇L(w(t)). (7)
The following lemma describes the behavior of g(w(t)). Some properties in Lemma 3 can be explained visually from Figure 2 in the Appendix.
Lemma 3 Under Assumption 1, the following hold:
(i) g(w) ≤ 0.3; (ii) If θ(w,v) > π/2, then g(w) < 0; (iii) If θ(w,v) ≤ π/2, then ∂g(w)/∂θ(w,v) < 0.
(iv) If 0 < ‖w‖ ≤ c0|cos θ(w,v)|2πL with L := 1 8Ex∼D2 ‖x‖ 2, then g(w) cos θ(w,v) > 0.
Step 3: Finally, we bound ‖w(t)‖ ≤ ‖w(0)‖ if t ≤ T , and ‖w(t)‖2 − ‖w(T )‖2 ≤ 0.6(t − T ) if t > T from (i) in Lemma 3, which shows two-phase directional convergence in Theorem 1.

heading: 3.4 Convergence of gradient descent for linear regression
text: Now we turn to the gradient descent setting based on the previous results. The difficulty we encounter is that the arbitrary choice of learning rates in each step may break the directional monotonicity in Lemma 2 as Eq. (8) reveals (See Appendix A for the proof).
cos θ(n+ 1)− cos θ(n) = 1 ‖w(n+ 1)‖
[ − ηn ( v − (w(n)>v)w(n) )>∇L(w(n)) − ( ‖w(n+ 1)‖ −w(n)>w(n+ 1) ) cos θ(n) ] .
(8)
Fortunately, when v>w(n) ≤ 0, we have g(w) ≤ 0 by (ii) in Lemma 3, implying that the first-phase directional convergence in the gradient flow case still holds.
Lemma 4 Under Assumption 1, suppose θ(0) 6= π and v>w(0) < 0. Then we have that
cos θ(n) ≥ 1− (1− cos θ(0)) e−BS − n (9)
until cos θ(n) ≥ 0, where S−n := ∑n−1 k=0
ηk√ A+ ∑k i=0 η 2 i , A = ‖w(0)‖ 2 c20 and B = 1+cos θ(0)π .
Hence, when w(n) stays in the “wrong” region that θ(n) > π/2, larger learning rate gives faster directional convergence to the region {w : θ(w,v) ≤ π/2}. Unfortunately, when θ(n) ≤ π/2, the directional dynamic becomes unstable and heavily relies on the current learning rate. However, after simple calculation invoked from Lemma 2, we find that (Lemma 12 in Appendix)
‖w(n+1)‖2 = ( w(n)>w(n+1) )2 + (c0ηn
π
)2 sin2 θ(n). (10)
Combining Eq. (10) and Eq. (8), we figure out
cos θ(n+1)− cos θ(n) = 1 ‖w(n+1)‖
( c0ηn sin 2 θ(n)
π − c
2 0η 2 n sin 2 θ(n) cos θ(n)/π2 ‖w(n+1)‖+ w>nw(n+1)
) .
Hence, we characterize a 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 1, if w(0) 6= 0, θ(0) 6= π, and there exists a δ > 0, s.t.
‖w(n+1)‖+ w(n)>w(n+1) ≥ (1 + δ)c0ηn cos θ(n) π ,∀ n ∈ N, (11)
then there exist constants A,B,C > 0 such that
cos θ(n) ≥ 1− (1− cos θ(0)) e−BS + n . (12)
Here S+n := ∑n−1 k=0
ηk√ A+ ∑k i=0(η 2 i+Cηi) , A = ‖w(0)‖2/c20, B = δ(1+cos θ(0)) (1+δ)π , and C = 0.6/c 2 0.
Furthermore, we can show the directional convergence with bounded learning rates as follows. Note that when ‖w(n)‖ ≥ ηnc0 + (1 + δ)c0ηn/(2π), by (i) in Proposition 3, Eq. (11) can be satisfied from
‖w(n+1)‖+ w(n)>w(n+1) ≥ 2 (‖w(n)‖ − ηn‖∇L(w(n))‖) ≥ (1 + δ)c0ηn/π.
Once ηn ≤ η+, then ‖w(n)‖ ≥ R1 := η+c0 + c0η+/π is sufficient to derive the convergence. We note that ‖w(n)‖ ≥ v>w(n), and from (ii) in Proposition 2 and (iii) in Proposition 3, the right term v>w(n) monotonically increases to infinity. Thus, after finite iterations, the sufficient convergence condition would be satisfied.
Theorem 2 Under Assumption 1, for a bounded learning rate sequence {ηn}∞n=1 with η+ ≥ ηn ≥ η− > 0, cos θ(n) first converges following Eq. (9) until cos θ(n0) ≥ 0 for some n0 ≥ 0. Then there exists an n1 ≥ n0 such that v>w(n1) ≥ η+c0 + η+c0/π, and cos θ(n) converges to 1 from n1 following Eq. (12).
Remark 3 Generally, a β-smooth objective loss has the learning rate constraint (0 < η < 2β ) to guarantee convergence [40]. There is no such constraint because the purpose is learning the direction instead of decreasing the loss. Furthermore, we need to underline that the loss still converges. Since for large enough ‖w(n)‖, the smoothness coefficient of the objective becomes certainly small and the bounded learning rate is naturally suitable to guarantee convergence.
Comparison. Our convergence bounds provide a faster and non-asymptotic directional convergence rate exp ( O(− √ t) ) (under constant learning rates, i.e., ηn = Θ(1)) compared to O ( 1/ log2 t ) in Soudry et al. [46, Theorem 5]. Additionally, previous results hold for a certain large t and the finite dataset with a 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 1. Moreover, the prior technique of proofs mostly employs the decomposition: w(t) = ŵ log t + ρ(t) with the max-margin solution ŵ and almost bounded residual term ρ(t). We can implicitly obtain an analogous decomposition, but such a way would lose sight of variation during the early training, such as the decreasing and increasing period of ‖w(t)‖. 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 a data-related upper bound. When data are distributed well, we derive the directional convergence directly under implicitly bounded learning rates and then obtain the loss convergence from the directional convergence.

heading: 4 Deep Linear Networks
text: In this section, we extend the results of gradient flow to deep linear networks. For an N -layer linear network φ(x,w) = WN . . .W1x where w := (WN , . . . ,W1), the objective is
min w
L(N)(WN , . . . ,W1) := Ex∼D ln [ 1+e−y(x)WN ···W1x ] .
Every such a network represents a linear mapping given by we = (WN · · ·W1)> ∈ Rd:
L(N)(W1, . . . ,WN ) = L (1)(we) = Ex∼D ln ( 1+e−y(x)w > e x ) .

heading: 4.1 Main results for deep linear networks
text: A key tool for analyzing the induced flow for we is established in Claim 2 of Arora et al. [3]. Specifically, if the initial balancedness conditions
Wj+1(0) >Wj+1(0) = Wj(0) >Wj(0), j = 1, . . . , N − 1 (13) hold, then we have the induced gradient flow with we(t):
∂we(t)
∂t = −‖we(t)‖2− 2 N
( dL(1)(we(t))
dw + (N − 1)we(t)we(t)>
dL(1)(we(t))
dw
) . (14)
Such an initialization technique is common for linear networks [2, 3, 7, 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 a special case of 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:
Proposition 4 Under Assumption 1 and the initial balancedness condition Eq. (13), if N = 2, we(0) 6= 0 and θ(0) 6= π, we obtain the directional convergence as follows:
cos θ(t) = 1− 2 C1e2c0t/π + 1 , with C1 = 1 + cos θ(0) 1− cos θ(0) .
Next, we present a lemma which is an extension of Lemma 1 to the deep linear case: both lemmas present the “descending-then-ascending” pattern of the weight norm.
Lemma 6 Denote T := inf{t : ∂‖we(t)‖2/∂t ≥ 0}. We have T <∞, and ∂‖we(t)‖2
∂t
{ ≥ 0, ∀ t ≥ T < 0, ∀ t < T. (15)
The main result for the deep linear net case provides the convergence rate of the gradient flow.
Theorem 3 Under Assumption 1 and the initial balancedness condition Eq. (13), ifN > 2, we(0) 6= 0 and θ(0) 6= π, we obtain two-phase convergence below. With the T defined in Lemma 6, we have
cos θ(t) ≥  1− 2 C1(A1t/B1 + 1)α + 1 , t ≤ T,
1− 2 eA2(t−T )+B2 + 1 , t > T.
Here A1 = (N − 2)c0, B1 = ‖we(0)‖ 2 N−1, C1 = 1+cos θ(0) 1−cos θ(0) , and A2 = 2c0‖we(T )‖ 1− 2N /π, B2 = −2 ln ∣∣∣tan θ(T )2 ∣∣∣, and α = 2/[(N − 2)π].
In addition, we have the upper bound that
cos θ(t) ≤ 1− 2 eF [(0.6t+D) N/2−DN/2]+E + 1 ,
where D = ‖we(0)‖ 2 N , E = −2 ln ∣∣∣ tan θ(0)2 ∣∣∣, and F = 4c00.6Nπ . Theorem 3 implies cos θ(t) undergoes two stages: polynomial convergence stage and exponential convergence stage. Finally, as for the initialization θ(0) = π, we have that θ(t) = π, ∀t ≥ 0, and we(t)→ 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 c0 and ‖we(T )‖1−2/N (when the number of layers N ≥ 3). Scaling up the data can increase the expected data norm c0, thus increasing A2 and the convergence speed. It is not clear, though, how to increase ‖we(T )‖ since it depends on an unknown transition time T . The convergence speed of the first stage is positively correlated with A1 and 1/B1. 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 t ≤ T , we use the lower bound in Eq. (17) to capture the decreasing period of ‖we(t)‖. Actually, ‖we(t)‖ may descend to a certain value that is higer than the lower bound in Eq. (17) before ascending. Second, when t ≥ T , note that cos θ(t)→ 1 except we(0) = kv for k ≤ 0 by Theorem 3. We can guarantee ‖we(t)‖ → ∞ because v>we(t) is increasing after some time (but not always). Hence, the convergence could be faster when ‖we(t)‖ increases much, but we only treat such a scheme lower bounded by ‖we(T )‖.
Comparison. Our global convergence rate results for deep linear networks neither require small training loss [37, 21, 23] nor presume convergence of loss and weight direction [17, 38]. Moreover, our results do not require overparameterization [9, 11, 19]. However, we need the exact initial balancedness condition [3]. Previous works [37, 21, 51] 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].

heading: 4.2 Technical lemmas for analyzing deep linear networks
text: We present a series of technical results that will be used for proving Lemma 6 and Theorem 3. Some are extensions of those for logstic regression, and some are new for deep nets.
Lemma 7 Under Assumption 1 and the initial balancedness condition Eq. (13), if we(t) 6= 0, then
∂ cos θ(we(t),v) ∂t = c0 sin
2 θ(we(t),v)
π · ‖we(t)‖1− 2 N . (16)
The main difference from the logistic regression case is that the dependence of weight norm ‖we(t)‖ is reversed. Larger ‖we(t)‖ gives faster convergence for the deep linear networks whenN ≥ 3, while no influence for N = 2, and for N = 1 it is opposite (i.e. larger ‖we(t)‖ gives slower convergence). We then provide a few properties of the weight norm during training.
Lemma 8 Under Assumption 1 and the initial balancedness condition Eq. (13) with we(0) 6= 0, we have the following two properties:
(i) Suppose N > 2. For any t ≥ 0, we have( ‖we(0)‖ 2 N + 0.6t )N 2 ≥ ‖we(t)‖ ≥ ( ‖we(0)‖ 2 N−1 + (N − 2)c0t )− NN−2 > 0. (17)
(ii) Suppose ∂‖we(t0)‖2/∂t = 0 with we(t0) 6= 0 for some t0 ≥ 0. Then ∂g(we(t0))/∂t > 0.
We briefly explain how to use Lemma 8 to prove Lemma 6, which consists of two properties: Eq. (15) and T <∞. First, Eq. (15) is an immediate consequence of Part (ii) of Lemma 8, as well as a calculus fact Lemma 10 (see Appendix). This proof approach is similar to that for the logistic regression case. Second, T <∞ requires a 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-stationary, 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 <∞ by contradiction. More specifically, assume T =∞, i.e., ‖we(t)‖ is decreasing for all t, then ‖we(t)‖ converges to a finite value. We will use Part (i) of Lemma 8 and Part (iv) of Lemma 3 to derive a contradiction. See details in Appendix B.2.

heading: 4.3 Proof of Theorem 3
text: Proof: Using Lemma 7 and the lower bound of ‖we(t)‖ in Lemma 8, we obtain 1
2 ln
1 + cos θ(t) 1− cos θ(t) − 1 2 ln 1 + cos θ(0) 1− cos θ(0) ≥ 1 (N − 2)π ln A1t+B1 B1 .
This implies
cos θ(t) ≥ 1− 2 C1(A1t/B1 + 1)α + 1 ,∀t ≥ 0. (18)
Notice that (18) holds for the whole training period, thus surely holds for t ≤ T . Next, we will show a stronger convergence rate for the peoriod t > T , i.e., the second part of the theorem. According to Lemma 6 we have
∂‖we(t)‖ 2 N
∂t ≥ 0, ∀t ≥ T.
Hence ‖we(t)‖ ≥ ‖we(T )‖,∀t ≥ T . Therefore, 1
2 ln
1 + cos θ(t) 1− cos θ(t) − 1 2 ln 1 + cos θ(T ) 1− cos θ(T ) ≥ c0 π ‖we(T )‖1− 2 N (t− T ).
=⇒ cos θ(t) ≥ 1− 2 eA2(t−T )+B2 + 1 ,∀ t ≥ T.
For the third part, using the upper bound of ‖we(t)‖ in Lemma 8, we obtain 1
2 ln
1 + cos θ(t) 1− cos θ(t) − 1 2 ln 1 + cos θ(0) 1− cos θ(0) ≤ 2c0 0.6Nπ
( (0.6t+D) N 2 −DN2 ) .
This implies
cos θ(t) ≤ 1− 2 eF [(0.6t+D) N/2−DN/2]+E + 1 .

heading: 5 Experiments
text: In this section we conduct experiments to verify our theoretical analyses. We consider training a linear classifier and a 4-layer linear network under the logit loss as our theorems show. We construct simple dataset with x ∼ U(S1) and y(x) = sgn(v>x) with v = (0, 1)>. We use common stochastic gradient descent (SGD) with the batch size 1000 and the constant small learning rate 10−3. Moreover, we choose an initial value w(0) = we(0) = (0.6,−0.8)>. In the deep linear network, we set WN (0) = u > N , Wi(0) = ui+1u > i with ‖ui‖ = 1, i = 2, . . . , N and u1 = we(0) to satisfy the balancedness conditions Eq. (13). The results are shown in Figure 1.
Figure 1a shows the optimization period for linear classifiers. We also plot the convergence bounds obtained in Theorems 1. 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 a decreasing and increasing period. Figure 1b depicts the dynamic for the deep linear networks. We also plot three convergence bounds in Theorems 3, which roughly match the actual behavior. The weight norm ‖we(n)‖ still goes through the decreasing and increasing period, and we could observe a distinct stuck period when 5 ≤ η · n ≤ 10 as the lower bound shown in Lemma 8. Moreover, the loss decreases slowly when ‖w(n)‖ is small, but cos θ(t) still has considerable growth. Thus previous loss-based analysis may neglect potential variation of the accuracy we most concern. Furthermore, we can see a more rigorous understanding of ‖w(n)‖ may give more precise rates in the late training period (t ≥ 20).

heading: 6 Conclusion
text: In this work, we have studied the training dynamic of (deep) linear networks in binary classification tasks. Specifically, we focus on 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 a phenomenon also is observed in numerical experiments. We hope that our limited view of directional convergence would bring a better understanding of (linear) neural networks.
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).

Review summaries:
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. The 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. Among 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. The findings are shown empirically by experiments on both benign and real-world datasets and also partially on non-linear fully-connected ReLU networks. 

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. 

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.  

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.