On the Explicit Role of Initialization on the Convergence and Generalization Properties of Overparametrized Linear Networks
Authors: Hancheng Min
Salma Tarmoun
Rene Vidal
Enrique Mallada
Venue:  (2021)

Abstract: Neural networks trained via gradient descent with random initialization and without any regularization enjoy good generalization performance in practice despite being highly overparametrized. A promising direction to explain this phenomenon is the \emph{Neural Tangent Kernel} (NTK), which characterizes the implicit regularization effect of gradient flow/descent on infinitely wide neural networks with random initialization. However, a non-asymptotic analysis that connects generalization performance, initialization, and optimization for finite width networks remains elusive. In this paper, we present a novel analysis of overparametrized single-hidden layer linear networks, which formally connects initialization, optimization, and overparametrization with generalization performance. We exploit the fact that gradient flow preserves a certain matrix that characterizes the \emph{imbalance} of the network weights, to show that the squared loss converges exponentially at a rate that depends on the level of imbalance of the initialization. Such guarantees on the convergence rate allow us to show that large hidden layer width, together with (properly scaled) random initialization, implicitly constrains the dynamics of the network parameters to be close to a low-dimensional manifold. In turn,  minimizing the loss over this manifold leads to solutions with good generalization, which correspond to the min-norm solution in the linear case. Finally, we derive a novel $\mathcal{O}( h^{-1/2})$ upper-bound on the operator norm distance between the trained network and the min-norm solution, where $h$ is the hidden layer width. 

Under review as a conference paper at ICLR 2021
ON THE EXPLICIT ROLE OF INITIALIZATION ON THE CONVERGENCE AND GENERALIZATION PROPERTIES OF OVERPARAMETRIZED LINEAR NETWORKS
Anonymous authors Paper under double-bling brindd review
ABSTRACT
Neural networks trained via gradient descent with random initialization and with- out any regularization enjoy good generalization performance in practice despite being highly overparametrized. A promising direction to explain this phenomenon is the Neural Tangent Kernel (NTK), which characterizes the implicit regular- ization effect of gradient flow/descent on infinitely wide neural networks with random initialization. However, a non-asymptotic analysis that connects gener- alization performance, initialization, and optimization for finite width networks remains elusive. In this paper, present novel analysis of overparametrized single-hidden layer linear networks, which formally connects initialization, opti- mization, and overparametrization with generalization performance. We exploit the fact that gradient flow preserves a certain matrix that characterizes the imbal- ance of the network weights, to show that the squared loss converges exponen- tially at rate that depends on the level of imbalance of the initialization. Such guarantees on the convergence rate allow us to show that large hidden layer width, together with (properly scaled) random initialization, implicitly constrains the dy- namics the network parameters to be close to a low- low-dimensional manifold. turn. minimizing the loss over this manifold leads to solutions with good general- ization, which correspond to the min-norm solution in the lincar case. Finally, we derive novel O(h -1/2) upper-bound on the operator norm distance between the trained network and the min-norm solution, where / is the hidden layer width.
INTRODUCTION
Neural networks have shown excellent empirical performance in many application domains such as vision (Krizhevsky et al.] 2012] Rawat & Wang 2017). speech (Hinton et al.) 2012 Graves et al.) 2013) and video games (Silver et al. 2016]] Vinyals 2017). Among the many unexplained mys- teries behind this success is the fact that gradient descent with random initialization and without ex- plicit regularization enjoys good generalization performance despite being highly overparametrized.
A promising attempt to explain this phenomena is the Neural Tangent Kernel (NTK) (Jacot et al.) 2018), which characterizes the implicit regularization effect of gradient flow/descent on infinitely wide neural networks with random initialization. Precisely, under this infinite width assumption, a proper initialization, together with gradient flow training, can be understood as a kernel gradient flow (NTK flow) of functional that is constrained on manifold that guarantees good generaliza- tion performance. The analysis further admits extensions to the finite width (Arora et al.) 2019b] Buchanan al., 2020). The core of the argument, illustrated in Figure | amounts showing that (properly scaled) random initialization of networks with sufficiently large width, leads to trajectories that are, in some sense initialized close to the aforementioned manifold. Thus, approximately good initialization, together with acceleration, ensures that the training stays close to the NTK Flow.
Such analysis, however, leads bounds the network width that significantly exceed practical val- ues [Buchanan et al.] 2020), and seems to suggest the need of acceleration to achieve generalization. This motivates the following questions:
Is the kernel regime, which requires impractical bounds on the network width, necessary to achieve good generalization?

---

Under review as a conference paper at ICLR 2021
Acceleration
Infinite/ /inite Width
FFinit
Approximate NTK Flow
Generalization
Random Initialization
Constraint Manifold
NTK Analysis
Analysie for Single-hidden-layee Linear Networks
Contribution 1, Section 3
Contribution 3, Section 4.2
Approximate Imbalanced Initialization
Convergence/ Acceleration
Large Finite Width
Generalization
Random Initialization
Approximate Orthogonal Initialization
Constraint Manifold
Contribution 2, Section 4.1
Figure 1: Comparing our analysis to coamptooichnon-asymppin NTK analysis.
Does generalization depends explicitly on acceleration? Or acceleration required only due to the choosing an initialization outside the good generalization manifold?
For the simplified, yet certainly non-trivial, single-hidden layer linear network setting, this paper finds an answer these questions.
Contributions. We present a novel analysis of the gradient flow dynamics of overparametrized single-hiddes hidden layer linear networks, which provides disentangled conditions on initialization that lead to acceleration and generalization. Specifically, we show that imbalanced initialization ensures acceleration, while orthogonal initialization ensures that trajectories remain close the general- ization manifold. Interestingly, properly scaled random initialization of moderately wide networks sufficient to ensure that initialization is approximately imbalanced and orthogonal, yet it is not necessary for either. More specifically, illustrated in Figure I this paper makes the following contributions:
1.
We show first that gradient flow on the squared-12 loss preserves certain matrix vaitrix-valudd quantity, akin to constants of motion mechanics conservation laws of physics, that measures the im- balance of the network weights. Notably, some level of imbalance, measured by certain singular value of the imbalance matrix and defined at initialization, is sufficient to guarantee the exponen- tial rate of convergence of the loss. Our analysis is -on-probabiliitic and valid under very mild assumptions, satisfied by moderately wide maglee-hidden-lyee linear networks.
2.
We characterize the existence condition on the parameters, which is invariant under the gradient flow. All trajectories within this manifold lead to a unique (w.r.t the end-to-end function) minimizer with good generalization performance, which corresponds to the min-norm solution. As result, initializing the network within this manifold guarantees good generalization.
cow-dimensional manifold defined by a specific orthogonality
3. We further show that by randomly initializing the network weights using (0, 1/h) (where is the hidden layer width), initialization setting related the kernel regime (see Appendix H one can approximately satisfy both our sufficient imbalance and orthogonality conditions with high probability. Notably, the inaccurate initialization relative to the good generalization mani- fold requires acceleration to control the generalization error. In the context of NTK, our result further provide for linear networks novel O (h (1/)) upper- bound on the operator norm distance between the trained network and the min-norm solution. To the best of our knowledge, this is the
2

---

Under review as a conference paper at ICLR 2021
first non-asymptotic bound regarding the generalization property of wide linear networks under random initialization in the global sense.
Notation. For matrix A, we let A denote its transpose, Lr(A) denote its trace, (A( and o (A
denote its i-th eigenvalue and i-th singular value, respectively, in decreasing order (when adequate). We let [A]ay. [A] and [A]., denote the (i.j)-th element, the i-th row and the j-th column of A,
respectively, We also let ||A||2 and ||||| denote the spectral norm and the Frobenius norm of A,
respectively. For scalar-valued or matrix-valued function of time, F(t), we let F' F()) - # F()) denote its time derivative. Additionally, we let i, denote the identity matrix of order n. and N (1, o²) denote the normal distribution with mean μ and variance o².
2 RELATED WORK
There is a rich line of research that studies the convergence (Du et al. 2019b a Du & Hu 2019: Alhen-Zhu et al.; 2019b) and generalization (Allen-Zhu et al., 2019a, Arora et al. 2019a b. Li & Liang 2018: Cao & Gu 2019 Buchanan et al. 2020) of wide neural networks with random initialization. The behavior of such networks in their infinite width limit can be characterized by the Neural Tangens Kernel (NTK) (Jacot et al. 2018). With the concept of NTK, heuristically, training wide neural networks can be approximately viewed as kernel regression under gradient flow/descent (Arora et al. 2019h), hence the convergence and generalization can be under- stood by studying the non-asymptotic results regarding the equivalence of finite width networks to their infinite limit (Du et al. 2019b a Du & Huj 2019 Allen-Zhu et al. [2019b AAroa et al. 2019a bj Buchanan al., [2020). More generally, such non-asymplotie results are related the "lazy train- ing" (Chizat et al.) 2019 Du et al. 2019a Allen-Zhu et al. 2019b), where the network weights do not deviate too much from its initialization during training. Our results for wide linear networks presented in Section 4.2 do not follow the NTK analysis, but provide an alternative, presumably more general view on the effect of random initialization when the hidden layer sufficiently wide.
Wide neural networks.
Convergence of linear networks. Convergence in overparametrized linear networks has been stud- ied for both gradient flow (Saxe et al., 2014) and gradient descent (Bartlett et al. 2018 AArora al.) 201 8a b). In the kernel regime, Du & Hu 2019) applied the analysis of convergence of wide neural networks (Du et al., 2019b) to deep linear networks. Aside from the large hidden layer width and random initialization assumptions, Saxe et al. (2044) analyzed the trajectory of network parame- ters under spectral initialization, while Bartlett et al. 2018) studied the case of identity initializa- tion. Although the fact that the imbalance is conservative under gradient flow has been exploited in Arora et al. (201 a). they consider the case of balanced initialization only to simplify the learn- ing dynamics, and additional conditions are required for convergence. Most works mentioned above considered specific, often data-dependent, types of initialization that makes the learning dynamics tractable. Our result, based on an imbalance measure, is data-agnostic and satisfied under wide range of random initialization schemes, see lemmas ① and
Min-norm solution in high-dimension linear regression. For nigh-dimensiooal under-determined linear regression, the asymptotic generalization error of min-norm norm solution has been studied in Hastie et al. (2019). In Bartlett et al. (202)): Mei & Montanari (2019), the min-norm solution was proved to have near-optimal generalization performance under mild assumptions on the data model. For our purpose, we study the generalization of a trained linear network as its distance to the min-norm solution. In this way, we refer to solutions with good generalization performance, as those with small distance to the min-norm solution.
3 CONVERGENCE RATE OF GRADIENT FLOW FOR SINGLE-HIDDEN-LAYER LINEAR NETWORKS
In this section we study the convergence of gradient flow on squared lo-loss for single-hiddenn-lyer linear networks. Given training data of n samples {2!0), y yr jim with x(() E RD, ()(() E RmM we aim to solve the linear regression problem
min D
1 L
~0000
0" - 102
(1)
i=1
3

---

Under review as a conference paper at ICLR 2021
by training a single-hidden-laye linear network y f<:V,U =V'' Rm U R with gradient flow, or equivalently, gradient descent with "infinitesimal step size", here h is the hidden layer width. We consider overparamettrized model such that h 2 min(m, D).
We rewrite the loss function with respect to our parameters V, U as
n
- C(V
1 1 VU
00 ||Y - XUVV
where Y = [y (m))) X [x(11, ,.... x "' are concatenations of the training data in
rows. Assuming that the input data X has full rank, we consider the under-determined case D > n for our regression problem, i.e., there are infinitely many solutions O* to achieve zero loss of (T) With minor a reformulation, our convergence result works for the case where the input data X is rank deficient. We refer the reader to Appendix B
We will show that under certain conditions, the trajectory of the loss function L(1) = ((V)
under gradient flow of ( i.e.,
(t) av C(V(t). (()) = au --
0
(3)
converges to 0 exponentially, and that proper initialization of (0), V(0) controls the convergence rate via iimerinvariant matrix natrix-valued term, the imbalance of the network.
3.1 REPARAMETRIZATION OF GRADIENT FLOW
Given > r rank(X), the singular value decomposition X is given by
1/2 o| X = W -x
W E R 1 E Rx D2 E DDDxD--))
(4)
with WWT WTW 07 In TT ID-n 4 Φ 0, and $ T7 + D2 ID.
Notice that
U = LuU = 2 + 2 = 4 42
hence we can reparametrize U as (U1, using the bijection : Ra (R(Dn)xxh - RDxh U g(U1,U2) U2) U +
22U2, with inverse (U1, U2) 9 (U) U.U
We write the gradient flow in explicitly as
(t)) = (Y - (U(O)T(()) xU(t) = ET (1)E
(5a)
(() x x XUU-XU(VVT (1) V(I)
(5b)
based on the SVD of data X in where
Ett) = ((V()))) -
(6)
defined to be the error. Then from Sa (bb) we obtain the dynamics in parameter space (V,U1, U2)
(t) (0)2) Úi(t) 2 (2(1) =.
Notice that since W is orthogonal, we have
C(t) 2 1 XUUUUU (0)F 1 I = - 1E(0)
1
(8)
Therefore suffices to analyze the convergence rate the error E(t) under the dynamics of ((I), (t) in 77) As we mentioned in Section [ the exponential convergence of E(t), or equiv- alently the loss function C(t) is crucial for our analysis for generalization, in the sense that expo- nential convergence ensures that the parameters do not deviate much away from the manifold of our interest, which we will discuss in Section so that good properties from the initialization are approximately preserved during training.
4

---

Under review as a conference paper at ICLR 2021
3.2 IMBALANCE AND CONVERGENCE RATE OF THE ERROR
We define the imbalance of the single-hidden-layer linear network under input data X as Imbalance UTU, - VTV.
The imbalance term is time-invariant under gradient flow, stated in the following claim Claim. Under continuous dynamics (7). we have dt (t)(U (+)V)(() = O.
Proof. Under ( we compute the time derivative of Uf (t)Ui(t) and V (t)V(t) as
d
[T((((1)11) (T + +T(()(((T)) - vT (0000 di
_ (t)V(()) = V)(O)()) + (+V(() = (0000000000000000000000000000000 0.
dt
The right- side of two equations is identical, hence
The imbalance is a h x h matrix with rank at most m + the rank of imbalance characterizes how much the row spaces of Un and are misaligned. We show that a rank-(m + n - 1) imbalance sufficient for exponential convergence of the error E(),, or equivalently, the loss function.
Now we present our result regarding convergence the error. (see Appendix D for the proof).
Theorem (Convergence of linear networks with sufficient rank of imbalance). Suppose h 2 m + L. Let (t),, (t) 0 be the trajectory of continuous dynamics starting from some ((0)UU(()) If
Ontm-1 1 (O)U: - VT (O)) = =c>
(10)
then for F(()) defined in (6, we have
[(t) exp (-2on(Ex)ct)) [(E()) Vt O. Additionally, V(t), ( converges to some equilibrium point (V(oo), U2(0)) such that U1())) =.
(11)
The fact that the imbalance is preserved under gradient flow has been exploited in Arora et al. (2018a]b) where imbalance is assumed to be zero (or small), such that the learning dynamics can be expressed in closed form with respect the end-to-end matrix. This analysis, requires, however, additional assumptions on the initialization of the end-to-end matrix for acceleration. Similarly, though in a more general setting, Du al.) (20T8) showed that the imbalance is preserved, and proves convergence under small imbalance assumption. Acceleration (exponential rate), however, is not guaranteed. Exploiting imbalance for guaranteeing acceleration was first presented in [aaxe ee al. 2014), under a spectral initialization assumption. In contrast, Theorem T shows acceleration without the spectral initialization condition. Rather, we show that under very mild conditions on the alignment between the initialization and the data, acceleration is achieved.
Such good choice of initialization, at first glance, seems to largely depend on the data given the definition of the imbalance. However, show in the section that for sufficiently wide networks with random initialization, the imbalance has rank at least + m with high probability, for any data matrix X, hence exponential convergence is almost guaranteed when training such networks. Later we will illustrate how such convergence also affects the generalization of the trained network.
The dependence on on (Ex) has been also appeared in Du Hu (2019), where linear convergence rate of gradient descent was shown for multi-layer linear networks. Their proof followed the same high-level procedure in showing convergence for networks with nonlinear activation (Du et al.) 2019b which relied on showing that the Gram matrix is close to its initialization during training. For our result, although it provided for higge--hidde--layeee linear networks, we essentially lower bound the smallest eigenvalue of the Gram matrix at any time t by a fixed constant that only depends on the initialization.
We end the section by noting that our result is not restricted to the case that X is full rank. In Appendix B we show that similar result hold for the case that X is rank deficient, with mi- nor reformulations. In that case, only require h > d + 0 3 (0) VT (0) replaces what in shown in (I0), where d is the rank of X. In addition, we present and discuss the numerical simulation regarding Theorem in Appendix
1, and the singular value
5

---

Under review as a conference paper at ICLR 2021
4 GENERALIZATION OF SINGLE-HIDDE--LATE LINEAR NETWORK
In this section, we study the generalization properties of trained hingle-hidden-Ber linear networks under gradient flow. Assuming that D > = rank(X), the regression problem ① has infinitely many solutions O* that achieve zero loss. Among all these solutions, one that is of particular interest in high-dimensional linear regression is the minimum norm solution (min-norm solution)
b arg min (||1l2 : xe = 03 = = x" (xx(x)- @ERDXM
(12)
which has near-optimal generalization error for suitable data models, as shown in (Bartlett et al, 2020 Mei & Montanari, 2019). Here, we study conditions under which our trained network is equal or close to the min-norm solution by showing how the initialization explicitly controls the trajectory of the training parameters to be exactly (or approximately) confined within some low-dimensional manifold. In turn, minimizing the loss over this manifold leads to the min-norm solution.
Moreover, analysis constrained learning applies wide single- sangle-hidde--aage -laer linear networks with random initialization, whose infinite width limit is equivalent to the kernel predictor with linear kernel K (xx, x²) x² z', suggested by Jacot et al. 2018). One can easily check that such a kernel predictor is the min-norm solution Ô. In addition, we show that the operator norm distance between trained finite width single-hidden-lyee linear network and the min-norm solution is upper bounded by a O (1-1/2) term with high probability over random initialization.
4.1 DECOMPOSITION OF TRAINED NETWORK
To begin with, notice that the linear operator UVT E RDxm associated with the single-hidden-layy linear network can be decomposed according to the data matrix X as
UVT = ( + Tb JVV = UUUV" + D2U.VT
(13)
where 11,02, U1, U2 are previously defined in Section 3 Here [UVT] i.e., the j-th column of UVT, the linear predictor for the j-th output Ч/j, and is decomposed into two components within complementary subspaces span( (f1) and span (P2)). Moreover [U1T) , is the coordinate of [UVT)ss Jay w.r.t. the orthonormal basis as the columns of d1, and similarly [U2 UTV is the coor- dinate w.r.t. basis 22. Clearly, under gradient flow
(3) the trajectory (U)) (t),, t 0) is fully determined by the trajectory (U) (t), (t)t (t), > 0), which is governed by the dynamics
Convergence of Training Parameters. We have derived useful results regarding U1 VT) for t 0 in Section 3
By Theorem if the rank of the imbalance matrix large enough, U1 (t) converges to some ( (oo) and the stationary point satisfies WTY - (
0, which implies U1 (2o) Σ,p 5."1/WTyy Then it is easy to check that
Φ U/Ui())) = 4 -,,,,//2 = x" (Xx") è
(14)
In other words, the projected trajectory (in columns) of U(IVVT(() onto span( converges exactly to the min-norm solution.
For U2 (L)VT(())) notice that (2(()= = 0 in dynamics 77. hence U2(() U2(0), VL 0. Then under sufficient rank of imbalance, U(L)VF(L)) converges to some U (Xo) and
U(oo) = 4 (o()) + (0) (z)) (oo).
Therefore (O) quantifies how much the trained network ('(o)) is deviated from the min-norm solution é, and since $ 42 ID-n. we have
[|U(so)\"((>)) - 2112 = (001/))))
(15)
Constrained Training via Initialization. Based on our analysis above, initializing U2(0) such that U2(0)VT((x))) (oo) 0 in the limit, guarantees convergence to the min-norm solution via (5).
However, this is not easily achievable, as one needs to know a priori V(xc). Instead, we can show that by choosing a proper initialization, one can constrain the trajectory of the matrix U(IVTT (1)

---

Under review as a conference paper at ICLR 2021
to lie identically in the set (t)V(t 0 for all t 2 0, which is equivalent to saying that the columns of (t) lie in span (1). Indeed, using the fact that for all 2 0, U2(t) = (2) and
4 UTU(t)V (t) we obtain
0 DU = {>)( =
- -0)
(16)
Therefore, using (1)). follows that U(oo) = ô, as desired.
Here, the constraint that all columns of U()VVT()) (t) lie in span((;) is equivalent the constraint that (V.U) is within some low-dimensional manifold in the parameter space. More importantly such constraint on UVT is relevant to generalization: When column of UV is in span (#2), predictions are made based on features in (pan($2). However, those features are not present in the data X that spans 11 thus, intuitively, hurting the generalization performance.
To enforce the constraint (t) = V(I)U? (0). From 7 we have
0, consider the dynamics of (2(0)V or equivalently
V(UUT()) dt (1(t) (0)
ET ET
V(nUZ (0) Ui(t) ( (0)
(17)
The most straightforward way to enforce V(t)U? (0) = 0, V. > is to properly initialize
V(0), (0)) such that V(O)U? (0) 0 and U₁ (0) (0) O. To have such proper initializa- tion, one can
Initialize columns of (0) in span 11). which leads (0) 0;
Initialize (0) and (0) to enforce the orthogonality condition on the rows, i.. (O)) (0) 0 and (O)) (0) ID.
Such initialization guarantees that gradient flow is constrained within some low-dimensional mani- fold in the parameter space, such that any global minimizer of the loss in that manifold corresponds to the min-norm solution. Therefore, whenever the network parameters in this manifold converge, and E(xx 0, then the solution must be the minimum-norm one. While in practice we can make the initialization exactly as above, such choice is data-dependent and requires the SVD of the data matrix X. Moreover. we note that while the zero initialization works for the standard linear regres- sion case, such initialization (0)) (0) 0 is bad in the overparametrizee case because is saddle point of the gradient flow, even though it satisfies the orthogonal condition VO)U (0) 0 and (O)U? (0) = O.
In the next section, we show that under random initialization and sufficiently large hidden layer width ht these conditions on initialization are approximately satisfied, i.e., with high probability the rank of imbalance is m + and [[V()) (0)lle, | (o)):((0)]e:: (12). So that the trajectory Utt)V"(t), tt), > 0 will be approximately constrained in the subspace as we mentioned above.
4.2 WIDE
LINEAR NETWORK
We will now discuss the generalization of wide single-hidden-layer linear network with random initialization. In particular, we will show how the previously mentioned conditions for convergence and good generalization, i.c., high imbalance and orthogonality, are approximately satisfied with high probability under the following initialization
(U(0)) ~ ~ 0,
isis siiiD,IsiiM
h
1 h
(V)) ~ M
0,
1si m, ssish.
where all the entries are independent. Our analysis indeed highlights the need, within this regime, of exponential convergence to ensure good generalization.
Remark 1. Our analysis can be extended to the more general case where all entries of (O), V (0) sampled from from (10, h- -2a with 1 < 1/2 For the simplicity of the presentation, consider
the particular case 2 in this section. Please see Appendix F for the more general result.
7

---

Under review as a conference paper at ICLR 2021
Previous works Jacot et al. (2018) have suggested in the limit h + oo, the trained network is equivalent to the kernel predictor with NTK. For linear networks, the NTK is the linear kernel (xx,x'= x² '' whose corresponding kernel predictor is the min-norm solution. Therefore, as h - co, we should expect the trained network to converge to the min-norm solution, given proper scaling of the network (Arora al.] 2019h). Combining what we have discussed regarding the convergence and generalization of linear networks with basic random matrix theory, we are able to derive the non-asymptotic O (h-1)) bound on the operator norm distance between a trained h-width network under random initialization and the min-norm solution.
We note that, both our parametrization and initialization, are at first sight different that the one used in previous works (Jucot et al.) 2018; (u Hu [2019] Arora et al.) 2019b) on NTK analysis. However, one can relate our model assumptions the NTK ones by a rescaling of the parameters and time. In the context of this comparison, we see that our setting achieves the same as it achieves the same limiting end-to-end function, but with a rate of convergence h times faster (due to the timescale rescaling). Further, our result does not rely on studying the tangent kernel of the network, hence there is significant difference between our approach to the NTK one.
Remark 2.
Recall in the last section, one can obtain exactly min-norm solution via proper initialization of the kingle-hidden-ie network. In particular, it requires 1) convergence of the error E(t) to zero; and 2) the orthogonality conditions VOOU? (0) 0 and U1 (O)UZ (0) = 0. Under random initialization and sufficiently large hidden layer width h. these two conditions are approximately satisfied. Us- ing basic random matrix theory, one can show that with high probability, the rank of imbalance is m + n, which leads to (exponential) convergence of ((). and [V (0)ll,, [|U (0)UZ (0)]lF Oh-1//2, as stated in the following lemma (See Appendix F for the proof)
Lemma 1. Given data matrix X. Vō E (0, 1). vh > ho = poly (m, D, t). with probability at least
1 - 5 over random initializations with (U),, (O)]a ~ NN(0, h )) we have all the following hold.
1. (Sufficient rank of imbalance)
On-t-m (UT (0) -V*(() > 1-2 vm + D +
log
2
(18)
Vh
2. (Approximate orthogonality condition)
V(O) U. (0)U? (0)
S 2 m +n Vm D + 1 log 2
(19)
Vh
F
||1(0)] (0)l, 2 V m + D + 1 log 2
(20)
Vh
Clearly, (I)U))))) O0h-1111)))) alone is insufficient to have the final bound on the trained
network. However, from (17) we show that as long as the error E(f) converges to 0 exponentially, which is guaranteed by sufficient rank of imbalance with high probability, the final deviation from min-norm solution (o)))" (O)]l F can not exceed C(IIV (O)U3 (O)ll + [U,( (0)] F) for some constant C that depends on the data and the convergence rate of E(t), leading to the desired bound. The formal statement is summarized in the following theorem.
Theorem 2 (Generalization of wide single-hidden-layer linear network). Let (V))), U()) > 0) be trajectory of continuous dynamics 77. Then, 3C > O, such that 48 E (0, Wh > ho (I(E2)) poly m, D, 8 (E.) with probabiiity 1 1-6 5 over random initializations with (U()]) (V(0)) (00,h=1) we have
Vm + D + log 2 ([( (oo) < 20
(21)
Vh
where C deepends on the data X, Y.
The proof is shown in Appendix This is, to our best knowledge, the first asymptoti bound in the global (operator) sense of gradient flow trained wide neural networks under random initialization.
8

---

Under review as a conference paper at ICLR 2021
Although understand that this can not be directly compared previous works (Arora et al. 2019b Buchanan et al., 2020) that show non -anammtptoiic results connecting a trained network to the general network structure and activation functions than
kernel predictor by the NTK, using that of the linear network, we believe this theorem a clear illustration how overparametrization, in particular the hidden layer width, together with random initialization affects the convergence and generalization, beyond the kernel regime.
To be specific, regarding the non-asymptotic analysis for wide neural networks, the concept of con- strained learning presented in this section and used to prove Theorem is more general than previous works (Arora et al. 2019b), where one requires sufficiently large hidden layer width such that the trajectory of the network in the function space approximately matches the trajectory in the infinite width limit. Loosely speaking, such a large width enforces the trajectory to be approximately con- fined within a one-dimension manifold, parametrized only by I, and independent of the initialization. We have shown here, however, that even for relative smaller width h, there is larger dimensional manifold that provides good generalization performance. This shows that, while the kernel regime maybe sufficient, is certainly, at least for the linear single-hidden layer network, not necessary to guarantee good generalization.
To verify Theorem 2, we present the numerical simulation regarding the implicit regularization of gradient descent wide linear network in Appendix A The simulation result shows that (()) @ll approximately has the order O(h-1) as h grows, suggesting that non- asymptotic bound is tight in the order w.r.t. h. We refer interested readers to the appendix for the details of the simulation settings.
5 CONCLUSION
In this paper, study the explicit role of initialization on controlling the convergence and gener- alization of single-hidden-layer linear networks trained under gradient flow. First of all, initializ- ing the imbalance have sufficient rank leads the exponential convergence of the loss. Then proper initialization enforces the trajectory of network parameters to be exactly (or approximately) constrained a low-dimensional manifold, over which minimizing the loss yields the min-norm solution. Combining those results, we obtain O(h non-asymptotic bound regarding the equiv- alence of trained wide linear networks under random initialization to the min-norm solution. Our analysis, although on simpler overparametrized model, formally connects overparametrizatio, initialization, and optimization with generalization performance. We think it is promising to trans- late some of the concepts such as the imbalance, and the constrained learning concept to multi-layer linear networks, and eventually to neural networks with nonlinear activations.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. In Advances in neural information processing systems, pp. 6158-6169, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pp. 242-252. PMLR, 2019b.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient de- scent for deep linear neural networks. In International Conference on Learning Representations, 2018a.
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterizaaton. In 35th International Conference on Machine Learning, 2018b.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pp. 322-332, 2019a

---

Under review as a conference paper at ICLR 2021
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang- On exact computation with an infinitely wide neural net. In Advances Neural Information Processing Systems, pp. 8141-81511 2019b.
Peter Bartlett, Dave Helmbold, and Philip Long. Gradient descent with identity initialization effi- ciently learns positive definite linear transformations by deep residual networks. In International conference on machine learning, pp- 521-530. PMLR, 2018.
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
Sam Buchanan, Dar Gilboa, and John Wright. Deep networks and the multiple manifold problem. arXiv preprint arXiv:2008. 12245, 2020.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pp. 10836-10846, 2019.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Advances Neural Information Processing Systems, pp. 2937-2947, 2019.
Kenneth R Davidson and Stanislaw J Szarek. Local operator theory, random matrices and banach spaces. Handbook of the geometry of Banach spaces, 13117-366)131, 2001.
Simon Du and Wei Hu. Width provably matters in optimization for deep linear neural networks. In International Conference on Machine Learning, pp. 1655-1664, 2019.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. International Conference on Machine Learning, pp. 1675- 1685, 2019a.
Simon Du, Wei Hu, and Jason Lee. Algorithmic regularization in learning deep homogeneous models: Layers automatically balanced. In Advances in Neural Information Processing Sys- tems (NeurIPS), 2018.
Simon S Du, Xiyu Zhai, Barnabas Poezos, and Aarti Singh. Gradient descent provably opti- mizes over-parameterized neural networks. In International Conference on Learning Represen- tations(ICLR), 2019, 2019b.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recur- rent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pp. 6645 6649. IEEE, 2013.
H. Grönwall. Note on the derivatives with respect to parameter of the solutions system of differential equations. Annals of Mathematics, 20(4):292-22 2269 1919. ISSN 0003486X.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv: 1xXiv:1903.08560 2019.
Geoffrey Hinton, Deng, Dong Yu, George E Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N Sainath, et al. Deep neural networks for acoustic modeling speech recognition: The shared views of four research groups. IEEE Signal processing magazine, 29()):82-97 2012.
Morris W Hirsch, Robert L Devancy, and Stephen Smale. Differential equationn, dynamical systems, and linear algebra, volume 60. Academic press, 1974.
Roger Horn and Charles Johnson. Topics in Matrix Analysis. Cambridge University Press, 1994.
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, New York, NY, USA, 2nd edition, 2012. ISBN 0521548233, 9780521548236.
10

---

Under review as a conference paper at ICLR 2021
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 8157- 8166, 2018.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv: 2019.
Waseem Rawat and Zenghui Wang. Deep convolutional neural networks for image classification: A comprehensive review. Neural computation, 29(9:2352-2444, 2017.
Andrew M Saxe, James L Mcclelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural network. In International Conference on Learning Representa- tions, 2014.
Sheng-De De Wang, Te-Son Kuo, and Chen-Fa Hsu. Trace bounds on the solution of the algebraic matrix riccati and Iyapunov equation. IEEE Transactions Automatic Control, 31(7):654-656, 1986.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwiesser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and search. nature, 529(7587):484, 2016.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Starcraft ii: A new challenge for reinforcement learning, arXiv preprint arXiv:1708.0478)) 2017.
A NUMERICAL VERIFICATION
The scale of the linear regression we consider in the numerical section is D 400, 100, and m 1.
A.1
CONVERGENCE OF SINGLE-HIDDEN-LAEER LINEAR NETWORK
Generating training data The synthetic training data is generated following:
I) For data matrix X, first we generate Xo RRxxD with the entries sampled from ("00, 1), and take its SVD X, = WE1/20,, Then we let X W hence we have all the singular values X being 1.
2) For Y. we first sample e AO, DJ and e (0 0.01 TT)), then we let
XO
Initialization and Training We set the hidden layer width h 500. We initialize U(0). (0) with (U(0)) ~ (0, of), [V()) ~ NN ).), and we consider two cases of such initialization: 1) ou = 0.1, σv = 0.1: 2) ou 0.5, σy = 0.02. For these two cases, we run gradient descent on the averaged loss L + XUVTT with step size 77 5c - 4.
The case 2 has much greater e than the case 1, and as the consequence, the loss converges much faster for the case 2, shown in Fig 2 We see from the right log plot that for the case 1, the bound in Theorem is not a tight characterization of the asymptotic convergence rate, while for the case 2, when is large, the bound in Theorem I is almost tight regarding the asymptotic rate. Clearly for case 1, there are additional factors that contribute to the linear convergence, which would be an interesting research topic in the future work.

---

Under review as a conference paper at ICLR 2021
0.08
Cose By 0.l.fy 0.1,
10a1
10-2
0.05
Log squareed 12 Lona
Squared 12 Leos
10"1
0.03
10-4
0.02
0.01
10-7
Case 1: bound by Thm 1, A2001 200)
0.00
1.25
0.25
1.25
Iteration
heration k
Figure 2: Convergence of gradient descent with different initial level of imbalance, Un+m-1(U7 (0) VT (0)).))..
A.2 IMPLICIT REGULARIZATION ON WIDE SINGLE-HIDDEN-LAYER LINEAR NETWORK
Generating training data The synthetic training data is generated following:
1) For data matrix X, first we generate X E RaXD with all the entries sampled from (N,0, D-1);
2) For Y, first sample O A and (0, 0.01 I,), then let XO + Initialization and Training We initialize U(O), V(O) with [U(0]} ~ ((0, [V(0)}; ~ W/0,h~ and run gradient descent on the averaged loss L = Y - XUVT with step size 7 = 5e - 4. The training stops when the loss below le We run the algorithm various from 500 to 10000, and we repeat 10 runs for each h.
of iterations until stop
1.0
8.0
(1500
(100))111))))
[M/
B0
7.5
0.8
0.8
01 lleretione
7.0
0.8
0.6
6.5
0.4-
0.4
5.5
0.2
0.2
5.0
0.2
0.4
0.6
0.8
0.04
0.03
0.02
0.01
0.2
0.4
0.6
0.8
1.0
Hidden layer width
1/h
Hidden layor widlh
twi
Figure 3: Implicit regularization of wide hingle-hiddee-llyer linear network. (())) is the initial distance between the end-to-end function to the desired manifold discussed Section 4.] [U (t) (ty) Ô is the distance between the end-to-end function and the min-norm solution when the algorithm stops. The line is plotting the average over 10 runs for each h, and the error bar shows the standard deviation.
Clearly, shows that increases, the distance between the trained network and the min-norm solution decreases. The middle plot verifies that the distance is indeed (/22) Lastly, we note that the right plot implies the convergence rate approaches a constant as h increases, which verifies the result in Lemma regarding the imbalance singular value.
12

---

Under review as a conference paper at ICLR 2021
B CONVERGENCE RATE ANALYSIS FOR LINEAR REGRESSION: GENERAL CASE
Suppose the input data matrix X has rank d V min n). write the compact SVD of X as
X Ww W E IR"xd Φ E RDxx
D. Notice that we always have W W I. Given the compact SVD, we still define U1 = Φ U, and write the loss function as
and in Section we assume that
LV, 2 |Y XUV = Y W " V
|1(1x WW + -
[I(Ta WW Y + W(WYY ///"
[1 WW 11 + 1 W - - ||
+ ((Ta - ww )Y w(W"y- >
Il( ww + 1 W(WTY - -
2 (Ia WW )r -
2// VT
where the last equality is because that W W = 1, and the second last equality is because that the cross terms equal zero due to W (Ia WW = 0.
It is easy to that minvuu L(V.U) Ill WWT L-, which is usually referred as the residue. Similarly to Section we still define the error as E = TTY - / U,''U''' V and one can check that the gradient flow on C(V.U) U) yields
V(I) Ex (1)E)/"0100) (1), 21/1
(22)
parameter space (V, Similar to Theorem 1 we have
1. Let V(t),Ui(t)) 0 be the trajectory of continuous dynamics 22 starting from some (0), (0). If
Theorem B.1. Suppose h d d
Od+m-1 (U] (0)U:(0) (")) = =>> 0,
then for F.(I) = WTY 1//2 (T)VV (1), we have
E(t) & exp (- (- (Ex))))) [(O)) Vt H>0 0. Additionally, (l), 0 converges to some equilibrium point (V(oo),U((xo) such that (()
It follows exactly the same proof as for Theorem which is shown in Appendix D except that the size of U₁ and E is now d x and d x m respectively.
To Summarize, for any linear regression problem, Theorem shows that sufficient rank of imbalance guarantees exponential convergence of L(t) - L*, where = - - W WW?) YE
C USEFUL LEMMAS
Before proving Theorem T andd we state several Lemmas that will be used the proof.
The first Lemma is the Grönwall's 's inequality (Grönwall 1919 in the differential form. Lemma C.1 (Grönwall's inequality). Let u(t), 3(t): [0, +oo) + R be continuous, and u(t) differ- entiable on (0, +00). If
d (t) < ((t) -> 0,
dt
13

---

Under review as a conference paper at ICLR 2021
then
utt) - 2(0) exp (L. (())))) Vt 0.
The next Lemma is known as Weyl's Inequality for singular values. Lemma C.2 (Weyl's inequality for singular values). Let A, B Raxm. let minfn, m), then O++j-1(A+ B) (,(A) (B
0 0+j-1 (AB") - of (A)o,, (B²), for any i.j satisfying 1 i.j I and ++ 1 159 9.
The proof can be found in Horn & Johnson 1994 Theorem 3.3.16). Using Weyl's inequality, we state and prove lemma that is used for proving Theorem 2
Lemma C.3. Let A E Rexn, B E Raxm Suppose n S m, then
(BA)) s.(()
for 1 sis n).
Proof. We start with the case where n. When on (B²) O, the result trivial. When an (B²) * O, we have BB = I, where B is the follows that
inverse of B. By Lemma C.2 it
(A) S (AB)o (Bt), vi Since ai (Bt) = on (B), we get the desired inequality.
When l: >> we have
(A) = 0; ([A (xx( S o, (A on ([Bi
=; v1 sisn.
which still leads to the desired result.
A
When & < n, consider replacing A with
we have
(n-x))x
(B)))n(B) = (0
1) on((B) So;
0 (f,
( = o 1
AB
41 visish k.
We also state trace inequality widely using for solving control problems
Lemma C.4. Suppose for A, B Raxn, symmetric and is positive semidefinite, then
tr) S Str(AB)rrB))BBB s tr)
If both A, B are positive semidefinite, then (n(A) tr S tr(AB) < 01 tr())
The proof can be found in Sheng-De Wang et al. 1986
Lemma 1).
D PROOF OF THEOREM
We begin with restating the Theorem.
Theorem (Convergence of linear networks with sufficient rank of rebbalanc, Suppose h + 1. Let (t), U)(),t > be the trajectory of continuous dynamics (7) starting from some (O), (0). If
Ontm-1 -UT
VT(O)((0)) 0,
then for E(t) defined in (6, we have
(() < exp (-20, [0 VI>
Additionally, U(t),U,(t) converges to some equilibrium point (V(oo), U1 (20)) such that F(V (x))) 0.
14

---

Under review as a conference paper at ICLR 2021
Proof. For readability simply write V(t), Ui(t,, Et)) as V. V,U E for most of the proof.
Under the time derivative of error is given by
E - -
Consider the time derivative of ||
d
d tr(E" E)
|
dt
dt
2r
E oo'SUPUUUTE!EP E = EVEV)
(23)
Use the trace inequality in Lemma as
C.4 to get the lower bound the trace of two matrices respectively
tr (ETE!/U,UTE!//
tr (S."EE"E/PPUUC))
z on(UTU)) 1E
or(UiUF) tr (I,EEE
2 (E.) ( (0 (24)
and
2 (VV lr E)
a tr (E,EE")
om(VV?)o on mx)
- (02"))) |E)
(25)
Combine 23 with (24 25 we have
d
|1] S -20n (En)) (U:U7) a
o. (VVT)) (m |
(26)
dt
Moreover, we have
((UiU))+ommVV
UI)
+ f0 mm
(Lemma C.2
2 1ntm-1 1onfm-i-UFF, - V²V)
(Imbalance is lime-invariant)
- (T(O)((0)) =, Ontm-1 (0)Ui(0) -
where the first equality uses the fact that U,U (VVT resp.) has the same non-zero singular values as UT UVTV resp.). Finally we have
d di
1 S 20 b11
The result follows by applying Grönwall's inequality, Lemma C.I which leads to
[t()) & exp (-,,,,,E,)ee |E 12 Vt > 0,
(27)
then the exponential convergence Et)) is proved.
Regarding the second statement, for the gradient system 7 the parameters (U1 (t), V()) converge either to an equilibrium point which minimizes the potential |[E()) or to infinity HHissc et al, 1974].
Consider the following dynamics
d V(
ET (T)EE/1/2
V Ui(t)
(28)
dt (1)
I! E(t)
A+)
Z(1)
15

---

Under review as a conference paper at ICLR 2021
which is a time-variany linear system. Notice that by Horr & Johnson (001
Theorem 7.3.3),
have A22())l22 = = |E E())
From
28 we have
12001 = 2 (Z)
dt
2tr (1)2(()
I =2]A2(t)]la (Z())))))===(((2)))))) (Z())2((1))
2
- 20 1/21)(2))) (20 < 201 1/2 (211""001100000010000000
By Grönwall's inequality, Lemma C.I we have
1Z(112 S exp (
201 1/2 (2x)
|z(0)
Finally, from we have |[(()]l== S exp
(-on (E,)) [[E(O)] VL > which leads to
(t)) s exp (f, (E21I(EI))))) |Z(0)]
20 (E.)) (
S exp
exp expp(-on (-n))))() dr |Z
S cxp
1/2 [,,]||(())I 201
exp (xp((on (op(--((E)) |
220 1/2 (Ex) |E(()]|e)
cxp
|Z(0)
(29)
co (E.)
Therefore the trajectory V(t), (t), > is bounded, i.e. it can not converge to infinity, then it has to converges to some equilibrium point (V(o)), Ui (0o)) such that U()) 0.
E COMPARISON WITH THE NTK INITIALIZATION FOR WIDE SINGLE-HIDDEN-LAN
LINEAR NETWORKS
In Section 4.2 we analyzed generalization property of wide singlehhidden-layer linear networks
under properly scaled random initialization. Our initialization for network weights U, V different from the typical setting in previous works (Jacot et al.) 2018 Du & Hul 2019 Arora et al. 2019b). In this section, we show that under our setting, the gradient flow is related to the NTK flow by 1) reparametrization and rescaling in time 2) proper scaling of the network output. The necessity of output scaling also shown in Arora et al. (2019b).
In this paper we work with single-hidden-layer linear network defined as RD V,U) = VUTx, x, which is parametrized by V. Then we analyze the gradient flow on the loss function L(V,U)= 1 ||Y - XUVTI given the data and output matrix X, Y. Lastly, in Section 4.2, we initialize (O)) (0)) such that all the entries are randomly drawn from A (0, (0.
f(;; R"",
R""
where h is the hidden layer width.
Now we define Ü == Vhu, V = VhV, then the loss function can be written as
L(V.U) _(V, 1 Y
1
m
h
=
2
Y
Vh
Vmh
1
(())
Vm
1
VūT (0(
2
Vh. vmhh
1=1
Σ
(
Vm
f(x; V.ū)
Vh.
16

---

Under review as a conference paper at ICLR 2021
Notice that fa;; V. ū)-
VŪT= x is the typical network discussed in previous works (Jacot mah
2018 Du & Hu 2019 Arora et al. 2019b). When all the entries of (O), (() are initialized ct al.
randomly as / [0, h ). the entries of UO), ((0) are random samples from N (0, 1), which is the
typical choice of initialization for NTK analysis.
However, the difference is that (a;; V, scaled by ymm In previous work showing non- vh asymptotic bound between wide neural networks and its infinite width limit (Arora et al. 2019b] Theorem 3.2), the wide neural network is scaled by a small constant k such that the prediction by the trained network is within e-distance to the one by the kernel predictor of its NTK. More- over, Arora et al. (2019b) suggests i should scale as poly( ( i.e., make sure the trained network is arbitrarily close to the kernel predictor, should be vanishingly small. In our setting, the random initialization implicitly enforces such a vanishing scaling y as the width of network increases.
VA"
Lastly, we show that the gradient flow on L(V, U) only differs from the flow on Ł(V, Ü) by the time scale. Suppose U, V follows the gradient flow on L(V, U) w.r.t time t. Define & == ht, we have
d d Ü= Vh d vi=viha vh dl d di dt
du U
v dt au (V.
d U 1 0
dt
dt
and similarly we have
di A =
1-
Vi OV ((V.U)
0
Now notice that
d Ū== 1 0 ((V.U)=
1 x- (YYY-UUVJJ
di vh
00
Vh
h xxxx y -x-
0 (000rr)==-20.00 (V. au aū
and
1 a C(V.U) = 1 dt Vnov
d V
vh (Y XUVT)=XU
y h x XÙ - -(V 1)
8
av
Therefore, the gradient flow of U, V on LVV,U) w.r.t. time is equivalent to the gradient flow of Ü, V on LV, U) w.r.t. a rescaled time i hl.
Another way to see the time scale difference is the following, consider the gradient flow on L(V U)
w.r.t. time f, we have
d U(t) ou ((V())
a
dt
1 d ū(t) o0 ((V(t).
Vh. dt
1 (((t) = - Vh au
((((),
Vh di
+ d (ū()= h i (((()),()))
(30)
dt
au
where we use the fact that
a
au C(V(),U())
xT (1))
Vh - vV- -x00000))) v(1) = vh. 0
1 XT (r
0 (V))),
a0
Similarly we have
a d (()) ae C(V(),U(()
d v(t) 4
aV ((V()),(()).
(31)
di
We write (tt) V(t) U, V for simplicity. Same for ((), V(t).
17

---

Under review as a conference paper at ICLR 2021
From (30) and (31) we know that the gradient flow LV, w.r.t time essentially runs the gradient flow L(V, Ú) with accelerated rate by h.
Such equivalence through time rescaling suggests that running gradient flow on our setting is h times faster than the NTK one. In Arora et al. (2019b),
mentioned above, the network is scaled by a small constant such that the trained network is within e-distance to the kernel predictor by its NTK in terms of the prediction. As a consequence, the convergence rate is scaled by x² which makes the convergence slower. Therefore, our initialization scheme yields similar result as in Arora al. (2019b) but the gradient flow faster. Also, we note that this gap in rate of convergence in not present in (Du & Hu. 2019), which only focuses on providing convergence guarantees of the algorithm. that case, the network is not scaled by small и, however, the properties of generalization is not studied there.
F PROOF OF LEMMA AND THEOREM 2
To prove Lemma I and Theorem we use a basic result in random matrix theory
Lemma F.1. Given m, n. IN with m S n. Lel A be n random matrix with i.i.d. standard normal entries Aij- ~ - (0, 1). For 5 > 0, with probability at least 1 - 2 exp(--8²), we have
Vn (vm + 6) m (A) (A) < vn (vm + 6)
The proof can be found in Davidson & Szarek 2001 In this section, we show more general results under the following random initialization
Theorem 2.13)
1
[U(O)ss ~ ~
0,
ISiSD.ISiM
2
1
[V)) ~ M 0,
h2a
J. It is easy to see that a = corresponds to the random initialization scheme shown in Section 4.2 i.c. all the entries of (0),, (0) are random mean zero Gaussian with h -1 variance.
where < a -.
Regarding the imbalance and orthogonality condition, we have the following
Lemma F2. Lel 1 a a 3/2 Given data matrix X. vg E (0, 1), vh bg = poly (m, D, D) over random initializations with (U))) (V))) ~ NN(0, h -2a),
with probability at least have all the following hold.
1. (Sufficient rank of imbalance)
Tutim (UT (O) V (0)V(0)) > 11-22 vm + D + log 2
2.20
2. (Approximate orthogonality condition)
((O) U (0)UT(
m + D
+ 1 log
< 2 +
h 2,20- 1
m + + log
||V' (0)le 22m
h 1,20-5
From the Lemma, we can see why our analysis only applies to the case where 1 < 3: I) 1. the lower bound we can obtain for on+m (UT (0)U)()) (T()))(0)) will decreases to zero as h increases; 2) If I +. the orthogonality condition will not be asymptotically satisfied as h increases.
From Lemma
R2 let
2. have
18

---

Under review as a conference paper at ICLR 2021
Lemma 1 (restated). Given data matrix X. 48 E (0,1), Ah > he = poly (m, D, 3). with prob- ability at least 1 over random initializations with (U())) [V(0],, N((0, h-)), have all the following hold.
1. (Sisfficient rank of imbalance)
n++m - > 11-2 112- Vm + D + log 8
vh
2. (Approximate orthogonality condition)
V(O)UT
S 2 + V m + D +
1 log 8
2
U1 (1(00
Vh
v + D + 1 log 2
||,, I 2/m
Now we present the proof for Lemma F22
Proof of Lemma F.2 For readability we simply write U(0), U, (0), (2))) V(0) as U,U, U2. V.
Consider the matrix [VT UT] which is h (m D). Apply Lemma F.1 to matrix A
ho [VT U.] with probability at least 6, we have
Vh (Vm+d+0) s am+alh [VT U-) s (1 [vT UT)) S vh+ (Vm+ + (vm+d+6) dd))
which leads to
h vm D + 1 log < oo ([V
vm D + 1 log 2
UT]) s -
ha
ha
(32)
Regarding the first inequality, write the imbalance as
UTU - V [vT uf] U1 [VT
U [-0
m
V
U
For h > (vm W log 2)² assume event 32) happens, then om+D ((VT
0²T)) 2 -d-
vm+ 17 $ log 2tt
> 0, then we have
4
Ontm (UTU, - VVV)
[VT
UT]
T
0
1
Cxtm
T
I
O
[1]
(Lemma C.3
2 m
[VT
UJ]
0
$ 11
Om-D
UU]
Im
V
(1V)
Tutm
0
$
U
Tm+D
(Lemma C.3
2 nm
m
0
o
(T)
0
Im
om (LV UT))
Tntm
0
T
oz
([V
UTT)
Im
0
where the last equality is due to the fact that
has exactly n + m non-zero singular
T
value and all of them are
Therefore when h (vm+ + D log 2)²
conditioned on event 32 with probability 1 we have
mn (UTT - VTV) 2nDD ([VT
UT)
19

---

Under review as a conference paper at ICLR 2021
2
V m + D + / log _
h ht-a
ha
v m + D + 1/2 log 2
\/m + D D+ log
h 1-2a 2a
2
1 1,20-2 2
ha
m + D + 2 log 2
h 20
(33)
2aa
Regarding the second and third incquality, using the fact that ||A|e s Raxm, we have
mmin(n, m ||Al||
e
1 m
VU U1
VUT
U1U
T2
Tm
V
UT
0
0
Φ7
U
D22
Im
[
[VT
UT]
- -//m+D
0
[U]
$22
[VT
UT]
mm
for any E R,
Il
0
where the second equality is by the fact that
0, and
0
Φ2
112
[0
of
[VT
U2]
Im
U
0
.nm++)) D )
[m
Φ7
VT
UT
V
UT]
n/
for any 17 E R,
2
[m
where the second equality is by the fact that [0
of
0.
0
Notice that
VT
UT- - In
= max [o UF) - -/|
U
2
Again we let h (Vm + D 1/2 log 2)²²
When event
32 happens, all ( UT)
within
the interval ( (nt-a_ vm+D+ log 3
(n Vm+
Vm+D+1
log 1 27
Since the choice of n is
ha
ha
arbitrary, we pick
Vm + D +
log 2
122 +
(34)
ha
which is the mid-point of this interval, then we have
of( [ UT))
ml
max
Vm + D + 2/2 log
2
Vm +
+ 1 log 2
2
max
h
ha
(n is the mid-point)
20

---

Under review as a conference paper at ICLR 2021
1 h
vm + D +
log 2
2 112-2a
<m + D log 2
2
ha
ha
m + + log
h 1,2-2
Therefore, when > ho (Vm +D+ log 2)²² conditioned on event (32) with probability 1, we have
VUT U
V [VT U-] mmm++ - 2 m + 7
m D + 1 log 3
S v + n
1,2-
n S 22m m + D + 2
log 2
and | m
VT
UT]
(35)
h 3
and 35 happen with proba- bility 1, hence the probability that both 33 and 35) happen is at least the probability event (32 which is at least 5.
where we choose in 34 Conditioned on event
32
events
33
More generally, for readers' interest, we show that all the non-zero imbalance singular values con- centrate to 11-2a as I increases. For the of a 2. the singular values concentrate to as suggested by the following
Claim F.1. Let 1/2 < a S 1.2 Given data matrix v8 E (0, 1), vh > ho = poly (m, D, 2). with probability at least - over random initializations with (U())) [V(0)l NN00, -2aa), we have all the following hold.
htt-a_ vm + D log 3
Fntm (U (0)U1 (*(O)(()))
(36)
h (0)U, v (O)) < (1t-a v
m +
log 205
(37)
ha
Proof. For readability we simply write (()). (0), (()) U, U1, V. When the width condition
h > ho = poly (m, D 4) is satisfied. Condition on event 332. The lower bound (36) for the + m-th singular value has been shown by (33p.
For the upper bound (37 notice that
(IV
21 [b]) of ([VT U=))
oTUUf -VV--VV)= 0
UT
(1-m
S m
0
o xt
s < (VT
UT]).
[- 0
where again we use the the fact that
has exactly n + m non-zero singular value and
all of them are 1.
Condition on event 32) we have
Vm D + 1 log
- of ([VT
UT) < hhta +
ha
which is Therefore 36 37
holds with at least probability.
With Lemma F2 have the following result regarding the generalization property of wide single- hidden-layer linear networks. Notice that here the result is presented under random initialization such that all entries of U()), V(0) are sample from (0 h. h222),
21

---

Under review as a conference paper at ICLR 2021
Theorem F.1. Let <ass 2. Let (V(t), 0) be trajectory of continuous dynamics
Then, 3C O, such that Vo (0, 1), vh > hn 11(4--11 with ho poly (, D2 0. -1(2m)
0x(2))) wwth
probability 8 over random initializations with (U(0)) (V()); (N, -2a), we have
(U((o))V"(o)) - -Q12 - 11- vm +
V v + D
2
log 3
(38)
h 1,203
where C depends on the data X, Y.
From Theorem F.1 let a 2. we have
Theorem (Generalization of wide single-hidden-layer linear network, restated). Let (V(1), U()), > 0) be trajectory of continuous dynamics 7 Then, 3C > 0, such that Vō E (0, 1), vh > ho = poly m, D, à: (((2))
oi(Ex)) with probability - over random initializa-
tions with [V)),, ~ N(0, (i,hh")), we have
( 2112 - 20 + Vm + D + 1 log
Vh
where C depends on the data X, Y.
Now we only remain prove Theorem
Proof of Theorem F.1 From the continuous dynamics and Theorem the stationary point U(oo), (co) satisty
Ui(oo)V = ofÔ. U2(00) U2(0).
Hence we have
- (x0) = |0)U)((0)V + 02) - 1112
[0+,0//+++++00 -612
|1b,U)(20))<(<<)}}
= (=0=
Consider the following dynamics
(
Ex E (t))
v (0) (i(t)uZ(0))
(39)
(t(t)
Σ D1/E(() E()
:=(())
which is a time-variant linear system, and in particular, by Horn & Johnson 2012 Theorem 7.3.3),
have [A)22)] [/t)ll Notice that here the Z(t) is different from the one in the proof for Theorem 1
From
39
we have
|201 = 2tr (7A(()2()))(
di
2tr (1(()) (t))2(t)
S 221A2(()]l (()))))))(((())((00)))) (Z)1)Z
= (|X)/
< ( E(1) ((0 < 20 2/2 (2.1)
By Grönwall's inequality, Lemma we have
(0) & exp (f"
20 1/2 (E.)))(((()) ||((0]
22

---

Under review as a conference paper at ICLR 2021
[I((t]le & exp (f/ (Ix)) [1
(40)
Using Lemma F.2 for h > h/g == 16 (vm D + | In }) with probability at least 1 - 5 we have all the following.
nn-m -V) > 11-20 vm D
1
In
2
h
12x
(41)
h
h.20
2
2
((0)23 (i(0)
Vm + D +
In
|Z(0)le=
S 2vm
2
(42)
12a
[[U( - 2/m m D + 2 In
(43)
h2a-3
Here h/g is larger than from Lemma because in 41 we want the least non-zero singular value of the imbalance to be further bounded by 2.
From Theorem we have
| |EOI 3 exp 1-20 (Ex))())) [100
where c = Ontm-1 (UT (0)U2(0) VT(O) then by we have
||((1)]1 exp (-11-200 am Em |[(())]
||E(()]F exp (- EEn 222 ||]())]r--
Finally, from 40 we have
1z(t) S exp (1, 01 1/2 (E)))) ||((0]]l
(1// (E.(())))1(())))) (f exx (-h2-200 dr
< exp
||(()]|r
(1o0 exp (-h o (Ex) (Ex)T/2) dr
s exp
1/2 (Ex)(
|
01 1/2 (Fez) 2 h 20 on (Exz)
exp
E(O]]e))
|Z(00]|r.
(44)
The initial error depends on the initialization but can be upper bounded as
||[(0)]|r=
- y (00) S + 122=)//102=-- < ||Y|| .. (1""00))00)00000000000)
then we can write (44)
2 01 (1a)
|Z(()|E= S exp
2
h 20 nn En,
||||
exp
11-200
3/2 (Fiz)
[U((D) (0)ll)
||(())l
1/h1-20 20
2 1 1/2 [Ex)
exp
o (Enr)
||||F
exp
2
3/2 (2xr)
(U(O))T(())))
[|Z(0)]
(45)
For the second exponential, we let hu == max
k/. 16 06 (2
(Vm + D 1 In 3)² 21
then wh
a (2.)
1))
by
43
we have
(2
V + D + 1 In
exp
On (>))
1/2
UU
(O)V (O)IF)
< eexp
4
σn
3/2
(2a)
m
122-
2
Se. (46)
23

---

Under review as a conference paper at ICLR 2021
1/)(a-1) also ensures h
1/(4a-1) ho 116- hence the width condition for
Notice that h Ng
ho
42 M43 to hold is satisfied.
Finally by 42
46
write
45
1/h1-20
1/2
|Z(()|r x
exp
1
|
nn (x)
1/h1-20
1/2 1
D + + In 12a- 1
x
exp
nn (Ex)
||||E
2 m
n1
=C1//4 2u
2C 12
m D
In
Vm+
h
Therefore for some C 0 that depends the data (), given any < 5 < 1, when h
ho 1) as defined above, with at least probability 6, we have
(o(oc))2((oo) -
([))))) (1)
sup 1>0
|(()]| S 201/1-22 vm + n
m + D
In 2
sup t>0
h 20
24


Reviews:
[{"review_id": "d-J1FoJHzVf", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the convergence of gradient descent optimizing overparametrized linear nn, and proves a exponential convergence rate. Moreover, the paper proposes the distance of the optimizer to the smallest norm solution, which is justified in other papers such as Montanari, etc. as the generalizable solution. Thus the solution that SGD outputs has good generalization as well.\nI believe overall the result is good, and the points are stated clearly. I have the following suggestions:\n\n1. If the space is allowed in appendix, the algebra proving that (9) is time invariant can be provided, rather than \"one can easily check\". This intermediate step is critical for the full proof so I'd like to check it. (with this I can raise score to 6)\n2. A sketch of Montanari paper about the property of $\\hat \\Theta$ can be discussed in the appendix. \n3. Regarding the thm, it would be definitely sufficient for the conference if anything can be suggested with RELU activation. In NTK work that's just another kernel so it's easy to extend, but it might be hard here, I'm not sure.\n4. More literature review. I think Rong Ge has some papers about the landscape of matrix factorization problem so it's great to compare with them in detail, even if in appendix.\n5. In appendix, it's also great to prove that under a certain initialization, what is the expectation/value of high probability of the imbalance singular value.\n6. How does amount of data affect generalization bound? I think it's 1/\\sqrt{n} in NTK work, any a similar behavior here?", "extra_scores": {}, "extra_text": {}}, {"review_id": "GtYYaSorf9", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 9, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### General Comments\nA proper initialization plays an important role in the success of over-parameterized models such as deep neural networks and high dimensional models.  However, the explicit role of initialization in theoretical results of an algorithm has not been stated well to my knowledge.  The main task of this paper is to  present a novel analysis of overparametrized single-hidden layer linear networks, which formally connects initialization, optimization, and overparametrization with generalization performance. Specially,  it is shown that the squared loss converges exponentially at a rate that depends on the level of imbalance of the initialization.\nWith respect to linear networks, the paper makes the following three main contributions:\n（1） The role of initialization of the gradient flow on the convergence is characterized explicitly.  \n  (2) The stationary point of the gradient flow is sufficiently close to the min-norm solution in the linear case.\n（3） Random initialization for large wide  linear networks ensures that the dynamics of the network parameters \n      are constrained to a low-dimensional manifold. \nOverall, this is a written- well paper with significant novelty.  The results seem interesting in the deep learning theory literature. \n#### Specific Comments\n(1) For Theorem 2,  the network width is required to be a polynomial of the input dimension D, which may be loose in some practical network structures.  I wonder whether such constrain can be relaxed further? it will be better that some quantitative comparison with those related work is made. \n(2) When noisy gradient descent is considered,   is the current analysis  still applicable to the case and similar results can be derived?  \n(3) If an activation function is added such that the hypothesis class is nonlinear,  is the adopted analysis still valid? if not, what is the additional challenges? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "G4Sfk3Vvbgo", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proves the convergence rate of gradient flow for training two-layer linear networks. In particular, this paper discusses the connection between initialization, optimization, generalization, and overparameterization. The results show that gradient flow can converge to the global minimum at a rate depending on the level of imbalance of the initialization. Moreover, the authors show that random initialization and overparameterization can implicitly constrain the gradient flow trajectory to converge to a point lying in a low-dimensional manifold, thus guarantees good generalization ability.\n\nThis paper is well organized. It is interesting that sufficient imbalance can guarantee global convergence of two-layer linear networks while other papers may require nearly zero initialization or wide enough networks. Besides, my detailed comments are as follows.\n\nOne drawback is that this paper still requires that the width be greater than n+m-1 (Theorem 1), while the network width condition proved in some existing works (listed as follows) does not depend on the number of training examples n (although they require random or orthogonal initialization), the authors may need to comment their network width conditions after Theorem 1 (currently the authors only say that “our results is not limited to extremely wide networks with random initialization’’).\n\n[1] Du, S. S., & Hu, W., Width provably matters in optimization for deep linear neural networks. arXiv preprint arXiv:1901.08572.\n\n[2] Hu, W., Xiao, L., & Pennington, J., Provable Benefit of Orthogonal Initialization in Optimizing Deep Linear Networks. In International Conference on Learning Representations.\n\n[3] Zou, D., Long, P. M., & Gu, Q., On the Global Convergence of Training Deep Linear ResNets. In International Conference on Learning Representations.\n\nThe authors prove that the limit of gradient flow can be sufficiently close to the minimum-norm solution if the neural network is sufficiently wide. This conclusion is good and of certain importance to understand the optimization path of training linear networks. However, if the data matrix X is of full rank and D<n, the training objective is strongly convex. In this case, there is only one minimum, thus the convergence result Theorem 1 can directly imply the parameter convergence results in Theorem 2. \n\nSome experiments may be needed to verify the theory. In particular, theorem 1 only provides an upper bound result, thus cannot fully characterize the effect of the imbalance on the convergence. The authors may try initializations with different imbalances and plot the convergence curves to demonstrate the results in Theorem 1. Additionally, results in Theorem 2 may also need to be verified in experiments.\n\nSo far I can only see that the imbalance plays an important role in training two-layer linear networks, can you extend this to multi-layer cases? Will the imbalance at the initialization together with sufficient overparameterization still guarantee the convergence of gradient flow?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1WATnh7UIOg", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the optimization and generalization properties of a two-layer linear network. The considered setting is over-parameterized linear regression where the input dimension is D, number of samples is n<D, and the target dimension is m. The hidden width is h. The paper has two main results. The first result is exponential convergence of gradient flow to global minimum, where the convergence rate depends on the (m+n-1)-th singular value of an \"imbalance\" matrix. The second result shows that the solution found is close to the minimum L2 norm solution if certain orthogonality assumption is approximately satisfied at initially; then it was shown that if the width h is sufficiently large, then under a random initialization scheme, the solution found is close to the minimum L2 norm solution with a distance $1/\\sqrt{h}$.\n\npros:\nThe results are not previously known to my knowledge. The proofs appear to be correct as far as I can tell.\n\ncons:\nMy overall concern is the significance of the results. The results, while correct, do not contribute much to our understandings of optimization and generalization in deep learning. The ways in which the authors interpret the results are unsatisfactory or even misleading.\n\n1) Thm 1 shows a convergence rate of $e^{-ct}$, where $c$ is the (m+n-1)-th singular value of an imbalance matrix. On the appearance this result seems to suggest that a larger $c$ is beneficial for convergence. However I believe this suggestion is incorrect and can be very misleading. Indeed, previous work (e.g. Arora et al. 2018a) has shown linear convergence under zero imbalance ($c=0$), as cited in the paper, but Thm 1 fails to capture that. I think in general this $e^{-ct}$ is a very loose bound that does not capture the real convergence rate (unless the authors can provide convincing evidence that suggests otherwise).\n\nThat said, I do think Thm 1 is an interesting theoretical result and the proof is clever. I'm concerned about the practical relevance and the possibly misleading message it sends.\n\nAnother weakness is that Thm 1 only considers gradient flow but not gradient descent. \n\n2) Thm 2 and its interpretations are unsatisfactory in a number of ways.\n\nFirst, we know that just doing a normal linear regression using gradient descent (starting from 0) leads to the minimum L2 norm solution. So now we go through all the trouble in the 2-layer net and finally show we can find a solution that's almost as good as linear regression -- what's the point of doing that?\nOf course, one may argue that we are studying a toy model in order to better understand deep learning. However, the main message from this result can be also conveyed in linear regression -- as shown in Sec 4.1, the main step is to find an invariant manifold for gradient flow such that the minimizer in that manifold must be the min-norm solution; for linear regression, such manifold also exists, which is just the span of the data points. \n\nSecond, the initialization used ($1/h$ variance in both layers) is unconventional. It's different from the standard 1/fan_in initialization or the NTK parameterization. What happens if we use those more standard initializations? And what happens if we make the initialization smaller, e.g. $1/h^2$, or $1/h^{100}$? Would those change the result? The scale of the initialization is very important in this line of work (such as NTK), so this should be addressed clearly.\n(The authors actually claim that as $h\\to\\infty$ we would get the NTK solution, following Jacot et al (on page 7). I actually don't think Jacot et al.'s work directly implies this, because this paper uses a different initialization scale.)\n\nThird, the authors try to differ this result from all the NTK results, but the theorem is exactly showing that the final solution is close to the NTK solution. Isn't this a bit ironic?\n\nFourth, the authors claim \"this is the first non-asymptotic bound regarding the generalization of linear networks in the global sense.\" Maybe check out these papers:\nImplicit Bias of Gradient Descent on Linear Convolutional Networks,\nImplicit Regularization in Matrix Factorization.\nAlso, many NTK papers also have non-asymptotic bounds. For 2-layer linear networks, one should be able to easily get a bound on the distance of the learned model and the min-norm solution -- might be better than Thm 2.\n\n\n-------- after rebuttal --------\n\nThanks to the authors for the response and the updated manuscript. My assessment stays the same, and below are my additional comments.\n\n1. About Appendix E\n\nThanks for the clarification about the initialization scaling. However, this raises more concern about the significance of the result. In Appendex E, it is shown that the scaling considered in the paper and the NTK scaling lead to the **same** gradient flow dynamics. This suggests that we are actually still in the kernel regime, in contrary to the main motivation and the claims in the paper. (As for the time rescaling issue, it doesn't matter in gradient flow since the difference can be absorbed by rescaling the learning rates.)\n\nAppendix E also mentions that several previous papers used a small multiplier $\\kappa$ to make the initial network small. The authors claim that this makes the convergence rate slower. I don't think this affects the convergence rate, but it only affects the width requirement (see e.g. [1]). In fact, in stead of using this multiplier, there is another way to make the output zero without changing the NTK and without requiring a larger width, that is to use an anti-symmetric initialization -- see e.g. [2][3][4][5].\n\n[1] Arora et al. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks\n\n[2] Chizat et al. On lazy training in differentiable programming\n\n[3] Hu et al.  Simple and effective regularization methods for training on noisily labeled data with generalization guarantee\n\n[4] Bai and Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks\n\n[5] Zhang et al. A type of generalization error induced by initialization in deep neural networks\n\n2. About the motivating questions\n\nThis paper proposes to answer two questions in the introduction. The first question is \"Is the kernel regime, which requires impractical bounds on the network width, necessary to achieve good generalization?\" First, I don't think this paper answers this question since the considered regime is still basically the same as the kernel regime. Second, even if it does, this question itself is not valid, since there are numerous previous theoretical works that study generalization outside the kernel regime, in more interesting settings, e.g. [6][7][8][9] and many more (none of which are mentioned in the paper).\n\n[6] Allen-Zhu and Li. Backward Feature Correction: How Deep Learning Performs Deep Learning\n\n[7] Allen-Zhu and Li. What Can ResNet Learn Efficiently, Going Beyond Kernels?\n\n[8] Wei et al. Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel\n\n[9] Woodworth et al. Kernel and Rich Regimes in Overparametrized Models.\n\nThe second main question in the introduction is \"Does generalization depends explicitly on acceleration? Or is acceleration required only due to the choosing an initialization outside the good generalization manifold?\" I genuinely cannot understand this question.\n\n3. In the updated manuscript the authors state \"To the best of our knowledge, this is the first non-asymptotic bound regarding the generalization property of wide linear networks under random initialization in the global sense.\" This is still false (and insignificant) since the stated result is a direct consequence of previous NTK work.\n\n4. I certainly understand that understanding deep learning is very challenging so it's a natural step to start with simple models. However I think this paper in its current form has limited significance and has major issues in how it discusses previous work, main motivations and contributions, etc., for reasons described in the review.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide a new analysis of learning of two-layer linear networks with gradient flow, leading to some novel optimization and generalization guarantees incorporating a notion of the imbalance in the weights.  While there was some diversity of opinion, the prevailing view was that the results were not sufficiently significant for publication in ICLR.
Decision: Reject