Deep linear networks for regression are implicitly regularized towards flat minima
Authors: Pierre Marion
Lénaïc Chizat
Venue: NeurIPS 2024 poster (2024)
Keywords: deep learning theory
sharpness
non-convex optimization
implicit regularization
gradient flow
Primary area: optimization_for_deep_networks
TL;DR: Gradient flow implicitly regularizes deep linear networks towards flat minima, both for a small-scale and a residual initialization.

Abstract: The largest eigenvalue of the Hessian, or sharpness, of neural networks is a key quantity to understand their optimization dynamics. In this paper, we study the sharpness of deep linear networks for univariate regression. Minimizers can have arbitrarily large sharpness, but not an arbitrarily small one. Indeed, we show a lower bound on the sharpness of minimizers, which grows linearly with depth. We then study the properties of the minimizer found by gradient flow, which is the limit of gradient descent with vanishing learning rate. We show an implicit regularization towards flat minima: the sharpness of the minimizer is no more than a constant times the lower bound. The constant depends on the condition number of the data covariance matrix, but not on width or depth. This result is proven both for a small-scale initialization and a residual initialization. Results of independent interest are shown in both cases. For small-scale initialization, we show that the learned weight matrices are approximately rank-one and that their singular vectors align. For residual initialization, convergence of the gradient flow for a Gaussian initialization of the residual network is proven. Numerical experiments illustrate our results and connect them to gradient descent with non-vanishing learning rate.

Deep linear networks for regression are implicitly regularized towards flat minima
Pierre Marion
Lénaïc Chizat Institute of Mathematics EPFL
Institute of Mathematics
EPFL
Station Z, CH-1015 Lausanne, Switzerland pierre. wwr marion@epf1.ch
Station Z, CH-1015 Lausanne, Switzerland lenaic. chizat@epfl.ccmm ch
Abstract
The largest eigenvalue of the Hessian, or sharpness, of neural networks is key quantity to understand their optimization dynamics. In this paper, we study the sharpness of deep linear networks for univariate regression. Minimizers can have arbitrarily large sharpness, but not arbitrarily small one. Indeed, show lower bound on the sharpness of minimizers, which grows linearly with depth. We then study the properties of the minimizer found by gradient flow, which is the limit gradient descent with vanishing learning rate. We show an implicit regularization towards flat minima: the sharpness of the minimizer is a constant times the lower bound. The constant depends on the condition number of the data covariance matrix, but not on width depth. This result is proven both for a small-scale initialization and a residual initialization. Results of independent interest are shown in both cases. For small-scale initialization, learned weight matrices are approximately rank-on one and that their singular vectors align. For residual initialization, convergence of the gradient flow for Gaussian initialization of the residual network is proven. Numerical experiments illustrate our results and connect them gradient descent with non-vanishing learning rate.
than
show that the
Introduction
Neural networks have intricate optimization dynamics due to the non-convexity of their objective. A key quantity to understand these dynamics is the largest eigenvalue of the Hessian or sharpness S(W) (see Section 3 for formal definition), in particular because of its connection with the choice of learning rate 7). Classical theory from convex optimization indicates that the sharpness should remain lower than 2/1 to avoid divergence (Nesterov, 2018). The relevance of this point of view for deep learning has recently been questioned since neural networks have been shown to often operate at the edge of stability (Cohen al., 2021), where the sharpness oscillates around 2/n, while the loss still steadily decreases, albeit non mono-oonooiilly. Damian et al. (2023) explained the stability of gradient descent slightly above the 2/n threshold to be general phenomenon for non- non-quadratic objectives, where the third-order derivatives of the loss induce a self self-stabilization effect. They also show that, under appropriate assumptions, gradient descent on risk RL implicitly solves the constrained minimization problem
min RZ (W) such that S(W) 2
W
1
Trainability neural networks initialized with a sharpness larger than 2/1 is also studied by Lewkowycz et al. (2020), which describes transient catapult regime, which lasts until the sharpness goes below 2/17. These results beg the question of quantifying the largest learning rate that enables successful training of neural networks. For classification with linearly separable data and logistic loss,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Wu et al. (2024) show that gradient descent converges for any learning rate. In this work, we address the case of deep linear networks for regression. As illustrated by Figure la, the picture then differs from the classification case: when the learning rate exceeds some critical value, the network fails learn. We further remark that this critical value does not seem to be related the initial scale: when the learning rate is under the critical value, learning is successful for wide range of initial scales. In Figure 1b, we see that the large initialization scales correspond to initial sharpnesses well over the 2/1 threshold, confirming that training is possible while initializing beyond the 2/n threshold.
Squared dibence to sptina negresoor
10"
Rid zaton
10"
mil 0.025
(012 0.1
10"
rolo: 0.2
10
Inttallzaioonn
:ite: 0.005
10"19
rile: 0.02
(a) Squared distance the trained network to em- pirical risk minimizer, for various learning rates and initialization scales. Training succeeds when the learn- ing rate lower than critical value independent of the initialization scale.
(b) Sharpness at initialization and after training, for various learning rates and initialization scales. For a given learning rate the dashed lines represent the 2/n threshold. The dotted black lines represent the lower and upper bounds given in Theorem and Corollary 2.
007
607
Thaniig
(c) Evolution during training of the squared distance to
(d) Evolution during training of the squared distance to
the empirical risk minimizer and of sharpness, for 17 the empirical risk minimizer and of sharpness, for 0.02 and an initialization scale of 0.35. The network 0.1 and an initialization scale of 0.35. The network does not enter edge of stability.
enters edge of stability.
Training deep linear network on univariate regression task with quadratic loss. The weight matrices are initialized as Gaussian random variables, whose standard deviation is the x-axis of plots la and 1b. Experimental details given in Appendix C.
Figure I:
To understand where the critical value for the learning rate comes from, characterize the sharpness of minimizers of the empirical risk. We show that there exist minimizers with arbitrarily large sharpness, but not with arbitrarily small sharpness. Indeed, the sharpness of any minimizer grows linearly with depth, as made precise next.
Theorem 1. Let X E xd dd be design matrix and y R² target. Then the minimal sharpness Smin of any linear network x + WT... Wix of depth L that implements the optimal linear regressor w" E Idd satisfies
211w=12 2 La & Smin < 21 V22L- 1)A2 + (T. 1)2
where is the largest eigenvalue of the empirical covariance matrix E = 1x and (w* ///l//ww10 SS [[[[w\[[[]]]] [I]
We note that this bound is similar to a result of Mulayoff and Michaeli (2020), although we alleviate their assumption of data whiteness É I). In particular, do not assume that data covariance

---

matrix is full rank. Furthermore, our proof technique differs, since we do not require tensor algebra, and instead exhibit direction in which the second derivative of the loss is large.
This result shows that it is not possible to find a minimizer of the empirical risk in regions low sharpness. Combined with (1), this suggests an interpretation of the critical value for the learning rate: gradient descent should not be able to converge to a global minimizer as soon as
2
(1 - La)
Sinn
Smin
This is confirmed experimentally by Figure which shows that the critical value of the learning rate matches our theoretical prediction. We note that this gives a quantitative answer to the observations of Lewkowyez et al. (2020), which shows the existence of a maximal rate beyond which training fails. The dependence of learning rate on depth (namely, constant over depth) also matches other papers that study scaling of neural networks (Chizat and Netrapalli, 2024; Yang et al., 2024).
learning
0,200
depth:
depth:
Squared dillance to oplinel regresso
0.176
dapth: 20
dapth:40 40
0.100
0,076
0.080
0.025
0.000
10"
Learnnng rale
Figure Squared distance of the trained network to the empirical risk minimizer, for various learning rates and depth. For each depth, learning succeeds if the learning rate is below a threshold, which corresponds to the theoretical value
Swwn ~ [12
2 La) 1 of Theorem (dashed vertical line).
To deepen our understanding of the training dynamics, we aim quantifying the sharpness of the minimizer found by gradient descent (when it succeeds): we know that it has to be larger than Smins but is it close Smin or is it much larger? Inspecting Figure 1b, we see that the answer empirically depends on the interplay between initialization scale and learning rate. For small initialization scale, the sharpness after training is equal
value relatively close Smin and independent of the learning rate. As the initialization scale increases, the sharpness of the trained network also increases, and plateaus at the value 2/1.. The plateauing for large initialization scales can be explained by the edge of stability analysis (I). which upper bounds the sharpness of the minimizer by 2/n (see Figure Id). However, this gives no insight on the value of the sharpness when the learning rate is sufficiently small so that the network does not enter the edge of stability regime (see Figure Ic).
In this paper, study the limiting case for vanishing 7), i.e., training with gradient flow. As our main finding, we bound the sharpness of the minimizer found by gradient flow in the case of overdeternined regression, meaning that the sample size larger that the data dimension d and the data empirical covariance matrix is nonsingular. In this case, we prove that the ratio between the sharpness after training and Smin is less than constant depending mainly on the condition number of the empirical covariance matrix Σ. In particular, the ratio does not depend on the width or depth of the network. This shows an implicit regularization towards flat minima. Note that the phenomenon we exhibit is different from the well- studied implicit regularization towards flat minima caused by stochasticity in SGD (Keskar et al., 2017; Smith and Le, 2018; 8; Blanc et al.. 2020; Damian et al., 2021; Li et al., 2022; Liu al., 2023). In the present study, the dynamics are purely deterministic, and the low sharpness is due to the fact that the weight matrices found by gradient flow have (approximately) the same norm across layers, and that this norm (approximately) the smallest possible one so that the network can minimize the risk.
3

---

Link with generalization. Flatter minima have been found to generalize better (Hochreiter and Schmidhuber, 1997; Jastrzebski al., 2017; Keskar et al., 2017; Jiang et al., 2020). although the picture is subtle (Dinh et al., 2017; Neyshabur et al., 2017; Andriushchenko et al., 2023). However, in this paper, we focus on the link of sharpness with (non-convex) optimization dynamics, rather than with generalization abilities. Indeed, our implicit regularization result holds in the overdetermined setting, where all minimizers of the empirical risk implement the same function thus have the same generalization enror, although they differ in parameter space and in particular have different sharpnesses. We leave to future work extensions to more complex settings where our approach may link sharpness and generalization, beginning with deep linear networks for underdetermined regression. We refer to Appendix C for more comments on the link with generalization.
We investigate two initialization schemes, quite different in nature: small-scale initialization and residual initialization. Let us explain both settings, by presenting our approach, contributions of independent interest, and related works.
Small-scale initialization. In this setting, we consider an initialization of the weight matrices W with i.i.d. Gaussian entries of small variance. Initialization scale is known play a key role in training of neural networks: small-scale initialization corresponds to the "feature learning" regime where the weights change significantly during training, by opposition to the "lazy" regime (see, e.g., Chizat et al., 2019). We show convergence of the empirical risk to zero, then characterize the structure of the minimizer found by gradient flow, a novel result of interest independently of its connection with sharpness. At convergence, the weight matrices are close to being rank-one, in the sense that all their singular values but the largest one are small. Furthermore, the first left singular vector of any weight matrix aligns with the first right singular vector of the next weight matrix. From this specific structure, we deduce our bound on the sharpness of the trained network. The bound is illustrated on Figure 1b, where our lower and upper theoretical bounds on the sharpness are plotted as dotted black lines. We observe that the sharpness after training, when starting from a small-scale initialization, is indeed situated between the black lines.
The result and proof extend the study by Ji and Telgarsky (2020) for classification, although the parameters do not diverge to infinity contrarily to the classification case, thus requiring finer control of the distance the rank-one aligned solution. In regression, implicit regularization towards low- rank structure in parameter space was also studied by Saxe et al. (2014); Lampinen and Ganguli (2019); Gidel al. (2019); Saxe et al. (2019); Varre et al. (2023) for two-layer neural networks and in Timor et al. (2023) for deep ReLU networks. This latter paper assumes convergence of the optimization algorithm and show that solution with minimal f2-norm has to be low-rank. In our linear setting, we instead show convergence. As detailed below, we impose mild requirements on the structure on the initialization beyond its scale; they are satisfied for instance by initializing one weight matrix to zero and the others with i.i.d. Gaussian entries. In particular, we do not require the so-called crero-balanced initialization" as is common in the literature on deep linear networks (see, e.g., Arora et al., 2018; Advani et al., 2020; Li et al., 2021) or deficient-marght initialization as in Arora et al. (2019a). Finally, the limit when initialization scale tends to zero has been described for deep linear networks in Jacot et al. (2021) for multivariate regression. It consists in saddle-to-saddie dynamics, where the rank of the weight matrices increases after each saddle. The present study considers instead asymtttmpo setting where the initialization scale is small but nonzero, and shows convergence to a rank-one limit because univariate and not multivariate regression is considered.
We note that sharpness at initialization can be made arbitrarily small, since it is controlled by the initialization scale, while sharpness after training scales as (T.). This therefore showcases an example of sharpening during training (although we make no statement on monotonicity).
Residual initialization. Architectures of deep neural networks used in practice often present resid- ual connections, which stabilize training (He et al., 2015). A simple non-linear residual architecture writes hu++1 = hy + (NN.))) Removing the non-linearity, we get h = (T + N&)he,, which prompts us to consider deep linear networks with square weight matrices Wa E IRdxd that are initialized as
(O I
VLd No.
(2)
where the No E Rdxd are filled with i.i.d. standard Gaussian entries and > 0 is hyperparameter tuning the initialization scale. The scaling of the residual branch in 1/vd is common and corresponds

---

for instance to the so-called Glorot and He initializations respectively from Glorot and Bengio (2010) and He al. (2015). It ensures that the variance of the residual branch is independent of the width d. Similarly, as studied Arpit et al. (2019); Marion et al. (2022), the scaling in 1/ I/VL. is the right one so that the initialization noise neither blows up nor decays when L - co. Note that, in practice, this scaling factor is often replaced by batch normalization (loffe and Szegedy, 2015), 5), which has been shown empirically to have a similar effect to 1/VT. scaling (De and Smith, 2020).
In this setting which we refer to as residual initialization, we show global convergence of the empirical risk. To our knowledge, is the first time that convergence is proven for standard Gaussian initialization of the residual network outside the large width d' e n. regime. Previous works considered either an identity initialization (Bartlett et al., 2018; Arora et al., 2019a; Zou al., 2020) or smooth initialization such that
W (O)lle (1/L) (Sander et al., 2022: Marion et al., 2024). The extension to standard Gaussian initialization leverages sharp bounds for the singular values of the product of W& (0). Our main assumption, in alignment with the literature, is that the risk at initialization should not be larger than a constant (depending on E and s).
We then show that the weights after training can be written
1 T 0k.
(xo) 1 VLd
Nu
where the Frobenius norm of the 0g is bounded by a constant (depending only on s). This structure finally enables us to bound the sharpness of the trained network. Remark that, to connect this analysis with our discussion of sharpness in univariate regression, we add to the residual network a final fixed projection vector p E Rdd so that our neural network writes x + p WL... W1x, but the proof of convergence also holds without this projection.
Experimentally, we give in Appendix C plots in the residual case that are qualitatively similar to Figure 1. The main difference is that the initial sharpness is less sensitive to the initialization scale s.
Organization of the paper. Section 2 details our setting and notations. Section 3 studies the sharp- ness of minimizers of the empirical risk and proves Theorem 1. Dynamics of gradient flow starting from small-scale initialization and residual initialization are respectively presented in Sections and 5. The Appendix contains proofs, additional plots, experimental details, and related works.
2 Setting
Model. We consider linear networks of depth L from Rd to R, which are linear maps
x' + p Wr.... Wix
(3)
parameterized by weight matrices WI,..., Wr, where We E Rdaaxe-11, do d and p Re. is fixed vector. This definition includes both fully-connected networks by setting dj = 1 and p = 1, and residual networks by setting d1 -...- d, = d, the WA close to the identity, and p to some fixed (potentially random) vector in Rd. We let W (Wi.... W,.) and Wpoo WT.... ... WT p. Given E Igaxd a design matrix and y E IR." a target, we consider the empirical risk for regression
Rd R'(W)= == lly - XW. W., pl1 = ll - Xuproul12 =: R (Wprod).
The notations R²(W) and R (Wores) may seem redundant, but are actually practical to define gradients of the risk both with respect to single matrix Wi and to the product Wpmmd Let := _ X the empirical covariance matrix, and À and A respectively its smallest nonzero and largest eigenvalue, For now, we do not assume that E full rank, so there is more than one solution to the regression problem min R (Wprod). We denote by w" Rd the smallest norm solution, and we let Rmin R (w+) be the minimum of R' (and R²). In all the following, we assume that "" * O. Note that, due to the overparameterization induced by the neural network, there exists an infinity of parameterizations of the mapping & + TT..
Gradient flow. We consider that the neural network is trained by gradient flow on the empirical risk R., that is, the parameters evolve according to the ordinary differential equation
dWr dt
2RL
(4)
oWk"
5

---

An application of the chain rule gives
(W) = OK
= Wk+1... W;, pVR (Wppdd W. W 1-11
(5)
aWk
with
2 X (y X (pood)
R (R-roe)))) =
x "((w" - Wprod)
(6)
where the second equality is consequence V VR+
Notations. For k E (1,... I.), we denote respectively by ok, ukg and iy the first singular value (which equals the & operator norm), the first left singular vector and the first right singular vector of Wg. The &2 operator norm of a matrix M is denoted by ||M and its Frobenius norm by || Fl Its smallest singular value is denoted by miin (M). For vector v, let ||u|22 its Euclidean norm. Finally, for quantities that depend on the gradient flow time f, we omit for concision their explicit dependence on t when it is dispensable.
3 Estimates of the minimal sharpness of minimizers
To define the sharpness of the model, we let D = Σt= dedx-1 and identify the space parameters with RD,, which amounts to stacking all the entries of the weight matrices in a large D-dimensional vector. Then the norm of the parameters Frobenius norm of the matrices by
D-dimensional vector can be related to the
I = Σ W
k=1
This allows us define the Hessian of the risk H R R DxD, and we denote by S(W) its largest eigenvalue for some parameters W, or sharpness. We note that there exists alternative definitions of the sharpness, but this one is the most relevant to study optimization dynamics. Our results are specific to this definition. The following result gives estimates on the minimal sharpness of minimizers of the empirical risk (and is strictly stronger statement than Theorem 1).
Theorem Let Smin infweargmin RL(W) S(W) and a == (w* /|| [[w"/[[w=
We have
Swin > 2allw* 112 - [|p||
||
and
2||w* 112 112-
||p||
La Smin & 21 lplll 1 + ( 1)
The proof of the result relies on the following variational characterization of the sharpness as the direction of the highest change of the gradient
El [VR+ V
s(w)= = lim
sup
(7)
<- JW: W.
Σk. [
W
Lower bounds are proven by considering well-chosen directions Wt. for instance We (1 W for the first lower bound. The upper bound is proven by constructing a specific minimizer and bounding its sharpness. The first lower bound shows that the sharpness of minimizers can be arbitrarily high if one of the matrices has low-enough norm. More precisely, take any minimizer W (W WW.... Wr) and consider WC (CW, Wz/C, W,...., W.). for some 0. Then WC is still minimizer, and
S(WC) 2aIl 2- |
2a 2a|lw
2-
|p
C-+00 oc.
12/CC|
The fact that a reparameterization of the network can lead to arbitrarily high sharpness consistent with similar result by Dinh et al. (2017) for two-layer ReLU networks.

---

Note that the first lower bound is arbitrarily small for minimizers such that the norms |W ll are large. On the contrary, the second lower bound is uniform and asymptotically matches the upper bound when I. > xc: we have Smin 1 LT.
As already noted by Mulayoff and Michaeli (2020), the intuition behind the linear scaling of the bound with depth can be seen from a one-dimensional example: take f zL) I Zz. Then an easy computation shows that the sharpness of at (1,..., 1) is equal to L - 1. This showcases simple example where the output of ʃ is constant with while its sharpness grows linearly with L.
Analysis of gradient flow from small initialization
In this section, we characterize the structure of the minimizer found by gradient flow starting from small-scale initialization. The proof inspired by the one of Ji and Telgarsky (2020) for linearly- separable classification, with a finer analysis due to the finiteness of minimizers in our setting.
We consider the model (3) with dz weight matrices are equal to zero, we can state our assumption on the initialization.
and p Denoting by Rg the empirical risk when the
(A1) The initialization satisfies that R (W)() < Ro and V (W(O)) + 0.
is satisfied for instance if one of the weight matrices W₂ is equal to zero at initialization while the others have i.i.d Gaussian entries, so that R (W(()) Ro and (W(() # 0 (almost surely).
Linear networks trained by gradient flow possess the following remarkable property (Arora et al., 2018) that shall be useful in the remainder. Lemma 1. For any time > 0 and any & E
1}. W (4) (1) - (0)Wa = Wa(o)WT (1) - (o))
Define now
E = 3 max [| + Σ II (WW - (0)=
Note that & only depends on the initialization, and can be made arbitrarily small by scaling down the initialization. The following key lemma connects throughout training three key quantities s.
Lemma 2. The parameters following gradient flow satisfy for any L 2 0 that
for L).
[t)l3 &| <E.
for k E (I,...,L. L},
(a -(())-}((1) E,,
for k fl,................. L 1}. (1)+1(t), (t), (t)) >
E
o (t)
The first identity of the Lemma bounds the sum of the squared singular values of Wit(t), except the largest one. other words, it quantifies how close (t) is to the rank-one approximation given by the first term in its singular value decomposition. The second statement bounds the distance between the spectral norms of any two weight matrices. The last bound quantifies the alignment between the first left singular vector of (1) and the first right singular vector of Wx+1 In particular, if is small and of (t) is of order 1. then uk+1(t) (t) and (t) are nearly aligned.
We next use this Lemma to show that the neural network satisfies which is one of the main tools to study non-convex optimization dynamics (Rebjock and Boumal, 2023). A well-known result, recalled in Appendix A for completeness, shows that this implies exponential convergence of the gradient flow to a minimizer Wsl of the empirical risk.
Lojysi--jjsiiwiizz (PL) condition,
Theorem 3. Under Assumption (A1). the network satisfies the PL condition for t 3 1, in the sense that there exists some Ps > O such that, for t > 1,
V+ (WR((W(t)) Rmiin).
7

---

The proof leverages the structure of the gradient of the risk with respect to the first weight matrix, which relies on the linearity of the neural network and the fact that we consider univariate output. More precisely, recall that, by (5),
R (W)()) (Wr.()....We))
R (1)rra(())
d1x1
1x
Therefore the Frobenius norm of the gradient decomposes as the product of two vector norms
V | ([ W2( Vi (W)roa
> 4X) Wa(O)B(("((( Rmin))
where the lower bound unfolds from a straightforward computation. The delicate step to lower W2(t))l2. which we approach by distinguishing depending the magnitude of 0i (t) = [[W, (1)ll. If (t) is large, we use Lemma 2 to deduce both that all (v(() are large and then that the first singular vectors of successive weight matrices are aligned. This implies that the product of weight matrices has large norm. To analyze the case where (1) is small, we use Assumption (A₁) to bound away Rd (W)()) from Rg for t > 1, and therefore (p)od() (t) from O. The fact that ppod( (t) cannot be too close to 0 while σ1 (t) is small implies that (t) ... (t) is large. All in all, this allows to lower bound [t) ... Wa (2(t)ll2 and the PL condition follows.
bound [[W((t)
To characterize the weights the end of the training, we make the following assumption.
(A2) The data covariance matrix Σ is full rank, and we have E < 1, || 3 1, and 32I & 1.
The first statement ensures unicity of the minimizer w of Rt,, and thus, given that the risk goes we have Uprod + w². The last condition means that the initialization has to be scaled down as the depth increases, so that = (.) Intermediates conditions are technical. We can then show the following corollary.
Corollary 1. Under Assumptions (A2). there exists T such that, for all & T and E (I,...,T.).
|
1/1. < (t) < (2 (2)22*1122 2/2
2
Together with Lemma 2, this result gives a precise description of the structure the weights at the end of the gradient flow trajectory. Up to the small factor e, the weights are rank-one matrices, with equal norms and aligned singular vectors. Since the product of weights aligns with w*, this means that the first right singular vector of W2 has align with w*, and then the weight matrices align with their neighbors in order to propagate the signal in the network.
Combining this specific structure of the weights with the variational characterization (7) of the sharpness and the explicit formulas (6) for the gradients, we derive the following upper bound on the sharpness of the found minimizer.
Corollary 2. Under Assumptions (A1 (A1)-(A)) the following bounds the sharpness of the mini- mizer WSI hold:
S(WS))
A
<<-
S Smin
This result shows that the sharpness of the minimizer is close to Smin in the sense that their ratio is bounded by constant times the condition number of E. For example, in the case of white data S I), we obtain that S(WSI) < 45min
5
Analysis of gradient flow from residual initialization
We now study the case of residual initialization. We consider linear network of the form (3) with
(t) = II+ 8
No. + I (t),
LLd
8

---

where each matrix is a d x d matrix and the N& are filled with i.idd. Gaussian entries (0, 1). We refer Section 1 for discussion of the scaling factor in front of Ng. Following the standard initialization of residual networks, we assume that the 0g are initialized to zero. Note that the scaling factor I/T. in front of the 0g has no impact on the dynamics; it convenient for exposition and computations, since we show that, with this scaling factor, the 0g are of order (11) after training.
Before stating the main result of this section on the convergence of the gradient flow, recall that E Rd is a fixed vector appended at the end of the residual network to project its output back in R.
Theorem There exist C1,..., Cs > depending only on s such that, if L E C1 and d > Cz. then,
with probability at least
1-16cxp(-Cxpp
if
(WV()) - RBmin & Cad21la12
A
the gradient flow dynamics (4) converge to global minimizer W of the risk. Furthermore, the minimizer WRR satisfies
W
VLd I, ORI with I Co, LEKEL.
1 No
To our knowledge, Theorem 4 is the first result showing convergence of gradient flow for standard Gaussian initialization of residual networks without assuming overparameterization. The main requirement is that the loss at initialization be not too large, as is standard in the literature analyzing gradient flow for deep linear residual networks (Bartlett et al., 2018; Arora et al., 2019a; Zou et al., 2020; Sander et al., 2022). Note that our bound on the loss initialization does not depend on the width d, depth I, or sample size n. We emphasize that the same proof holds for multivariate regression, in the absence of the projection vector p. We focus here on univariate regression to connect the result with the analysis of sharpness for univariate regression in Section 3. Details on adaptation to multivariate regression are given in Appendix B.7. Finally, the precise dependence of Ci to C5 on can be found in the proof.
The proof is a refinement of the analysis for identity initialization of residual networks (Zou et al., 2020: Sander et al., 2022). From the expression of the gradients (5), we can show that
E +
11 1 (RW)) Rmin)
> R| (W))l > 4Alpp|Boo (11..4+1)) )o (11s (a) Rmin),
with Uz = Wt... We and 11 = Ws... W1. Letting
=" inf {I R4,3k E (I, (1x((() > Cs):
the crucial step is to lower bound 2 (TI,,8+1) and o (I1+1:1) uniformly for i E [0, (*), in order to get PL condition valid for & [0, t*). Then, the condition the loss at initialization is used to prove that t" = oo, thereby the PL condition holds for all f 3 O. We deduce both convergence and the bound on the norm of OR! The lower bound on oi (III. and oi (I1g-1:1) is straightforward in the case of an identity initialization. In the case of Gaussian initialization, the proof is more intricate, and leverages the following high probability bounds on the singular values of residual networks.
Lemma 3. There exist C1,.... C4 > depending only on s such that, if
L> CI d C2.
E e C11
then, with probability at least
du
1- 8xxp
32s²
holds for all such that maxigkel 102122 & ta exp( -252 - 4u) and all k E L} that
[|( LLd
No + 1 (K)
(I I
s
N1 + (1) |1, < 4 4exp (5- +u)
ss2
VLd
and
(1+
8 Nk + L
8
I (1)) >
exp (- 22² - 4
Omiu
0kk
I+
N1 +
ILd
LLd.
4
d

---

The proof of this result goes in three steps, We first study the evolution of the norm of the activations across the layers of the residual network when f and prove proh-probability bound by leveraging concentration inequalities for Gaussian and x² distributions. Then an E-net argument allows to bound the singular values. Finally, the extension to perturbation analysis. The proof technique is related to previous works (Marion et al., 2022; Zhang et al., 2022), but provides a crisper and sounder bound. More precisely, Marion et al. (2022) show a bound on the norm of the activations with probability of failure that decays polynomially with the width d. which is not sufficient to apply the E-net argument that requires an exponentially decreasing probability of failure. As for Zhang et al. (2022), they provide similar bound with the purpose of showing convergence of wide residual networks, however with a less sharp probability failure that increases polynomially with depth.' Finally, as previously, the dependence of C1 to C₁ on can be found in the proof.
done via a ball around
The characterization (8) of the minimizer in Theorem 4 allows to bound its sharpness, as made precise by the following corollary. It holds under the same assumptions and high-pros probbbbbbbbi bound as the conclusion of Theorem 4.
Corollary 3. Under the assumptions of Theorem 4, and if the data covariance matrix Σ is full rank, there exists C 0 depending only on such that the following bounds on the sharpness of the minimizer WR hold;
S(WR))
1 1<
C X
Smin
As for Corollary 2, the proof relies on the fact that the norms of the weight matrices are close each other and to the smallest possible norm to minimize the risk. This result shows again an implicit regularization towards low-sharpness minimizer. Experimental illustration connecting the result with gradient descent with non-vanishing learning rate is provided in Appendix C.
6 Conclusion
This paper studies dynamics of gradient flow for deep linear networks a regression task. For small-scale initialization, we prove that the learned weight matrices are approximately rank-one and that their singular vectors align. For residual initialization, convergence of the gradient flow for Gaussian initialization is proven. In both cases, we obtain that the sharpness of the solution found by gradient flow is close to the smallest sharpness among all minimizers. Interesting next steps include studying the dynamics at any initialization scale, for non-vanishing learning rates, as well as extension non-linear networks. We refer Appendix C for additional comments and preliminary experimental results regarding possible extensions.
Acknowledgments
P.M. acknowledges support of Google through a Google PhD Fellowship. Authors thank Matus Telgarsky for insightful discussions, and Eloise Berthier, Guillaume Dalle, Benjamin Dupuis, well as anonymous NeurIPS reviewers, for thoughtful proofreading and remarks. An improvement to proof was also made possible by a tweet of Gabriel Peyré.
References
M. S. Advani, A. M. Saxe, and H. Sompolinsky. High-dimensional dynamics of generalization error in neural networks. Neural Networks, 132:428 446, 2020.
A. Agarwala, F. Pedregosa, and J. Pennington. Second-order regression models exhibit progressive sharpening to the edge of stability. In Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 169-195. PMLR, 23-29 Jul 2023.
We further note an incorrect use of concentration inequalities for x² distributions that are assumed to be sub Gab-Gaussian while they in fact only exbeexponentall. Details given in Appendix B.S.
10

---

M. Andriushchenko, F. Croce, M. Müller, M. Hein, and N. Flammarion. A modern look at the rela- tionship between sharpness and generalization. In Krause. E. Brunskill, K. Cho. B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 840-902. PMLR, 23-29 Jul 2023.
S. Arora, N. Cohen, and E. Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In J. Dy and Krause, editors, Proceedings the Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 244-253. PMLR, 10-15 Jul 2018.
the 35th International
Arora, N. Cohen, N. Golowich, and W. Hu. A convergence analysis of gradient descent for deep linear neural networks. In International Conference on Learning Representations, 2019a.
S. Arora, N. Cohen, W. Hu, and Y. Luo. Implicit regularization in deep matrix factorization. In H. Wallach, H. Larochelle, A. Beygelzimer. F. d'Alché-Buc, E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019b.
D. Arpit, V. Campos, and Y. Bengio. How to initialize your network? Robust initialization for WeightNorm & ResNets. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32, pages (0902-10911. Curran Associates, Inc., 2019.
P. Bartlett, D. Helmbold, and P. Long. Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 521-530. PMLR, 10-15 Jul 2018.
G. Blanc, N. Gupta, G. Valiant, and P. Valiant. Implicit regularization for deep neural networks driven by an omstein-uhlenbeck like process. In Abernethy and S. Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 483-513, PMLR, 09-12 Jul 2020.
J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Miine, and Q. Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:///pp http::///ttttubtt. com/ google/jax.
I. Chizat and P. Netrapalli. The feature speed formula: flexible approach scale hyper-parameters of deep neural networks. A. Globerson, L. Mackey, A. Fan, C. Zhang, D. Belgrave, Tomezak, and U. Paquet, editors, Advances in Neural Information Processing Systems, volume 37. Curran Associates, Inc., 2024.
L. Chizat, E. Oyallon, and F. Bach. On lazy training in differentiable programming. In H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Hn. H. Wallach,
J. Cohen, S. Kaur, Y. L. Z. Kolter, and A. Talwalkar, Gradient descent on neural networks typically occurs at the edge of stability. In International Conference Learning Representations, 2021.
A. Damian, T. Ma, and J. D. Lee. Label noise SGD provably prefers flat global minimizers. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 27449-27461. Curran Associates, Inc., 2021.
A. Damian, E. Nichani, and J. D. Lee. Self-stabilization: The implicit bias of gradient descent the edge of stability. The Eleventh International Conference on Learning Representations, 2023.
De and S. Smith. Batch normalization biases residual blocks towards the identity function in deep networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 19964-19975. Curran Associates, Inc., 2020.

---

L. Dinh, R. Pascanu. S. Bengio, and Y. Bengio. Sharp minima can generalize for deep nets. In D. Precup and Y. W. Tch, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1019-1028. PMLR, 06-11 Aug 2017.
M. Ghosh. Exponential tail bounds for chisquared random variables. Journal of Statistical Theory and Practice, 15(2):35, 2021.
G. Gidel, F. Bach, and S. Lacoste-Julien. Implicit regularization of discrete gradient dynamics in linear neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue Bucc E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In Y. Teh and M. Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 249-256. PMLR, 2010.
S. Gunasekar, B. E. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro. Implicit regular- ization in matrix factorization. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and Garnett, editors, Advances in Neural Information Processing Systems, volume 30, Curran Associates, Inc., 2017.
K. He, X. Zhang, S. Ren, and J. Sun. Delving deep into rectifiers: Surpassing human-level perfor- mance on ImageNet classification. In 2015 IEEE International Conference on Computer Vision (ICCV), pages 1026-1034. IEEE Computer Society, 2015.
D. Hendrycks and K. Gimpel. Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08415. 2016.
Hochreiter and J. Schmidhuber. Flat minima. Neural Computation, 9(1):1-42, 1997.
S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In F. Bach and D. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 448-456. PMLR, 2015.
A. Jacot, F. Ged, B. Şimşek, C. Hongler, and F. Gabriel. Saddle-to-saddle dynamics in deep linear networks: Small initialization training, symmetry, and sparsity. arXiv preprint 200i 15933, 2021.
S. Jastrzebski, Z. Kenton, D. Arpit, N. Ballas, A. Fischer, Y. Bengio, and A. Storkey. Three factors 2017.
influencing minima in SGD. arXiv preprint
7. Ji and M. Telgarsky. Directional convergence and alignment in deep learning. In Advances in Neural Information Processing Systems, volume 33, pages 17176-17186. Curran Associates, Inc., 2020.
Y. Jaang B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures and where to find them. In International Conference on Learning Representations, 2020.
N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
A. K. Lampinen and S. Ganguli. An analytic theory of generalization dynamics and transfer learning in deep linear networks, In International Conference on Learning Representationss 2019.
A. Lewkowyez, Y. Bahri, E. Dyer, Sohl-Dickstein, and G. Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.022/6 2020.
Z. Li, Y. Luo, and K. Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. In International Conference on Learning Representations, 2021.
12

---

Z. Li, T. Wang, and S. Arora. What happens after SGD reaches zero loss? mathematical framework. In International Conference on Learning Representations, 2022.
H. Liu, S. M. Xie, Z. Li, and T. Ma. Same pre- pre-traing training loss, better downstream: Implicit bias matters for language models. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 2188-42 PMLR, 23-29 Jul 2023.
L. E. MacDonald, J. Valmadre, and S. Lucey. On progressive sharpening, flat minima and generalisa- tion. arXiv preprint S.0.::2330..16888. 2023.
Marion, A. Fermanian, Biau, and J.-P. Vert. Scaling ResNets in the large-depth regime, arXiv preprint arXiv:2206.06922 06929, 2022.
P. Marion, Y.-H. Wu, M. E. Sander, and G. Biau. Implicit regularization of deep residual networks towards neural ODEs. In The Twelfth International Conference on Learning Representations, 2024.
M. Michel Petrovitch. Sur une manière d' d'étendre théorème de la moyenne aux équations différen- tielles du premier ordre. Mathematische Annalen, 54(3):417-436, 1901.
R. Mulayoff and T. Michaeli. Unique properties of flat minima in deep networks. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume
119 of Proceedings of Machine Learning Research, pages 7108-7118. PMLR, 13-18 Jul 2020.
Y. Nesterov. Lectures on Convex Optimization. Springer Optimization and Its Applications. Springer Cham, 2nd edition, 2018.
B. Neyshabur, S. Bhojanapalli, Mcallester, and N. Srebro. Exploring generalization in deep learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Q Rebjock and N. Boumal. Fast convergence to non-isolated minima: four equivalent conditions for C2 functions. arXiv preprint arXiv:2303.00000 2023.
M. E. Sander, P. Ablin, and G. Peyré. Do residual neural networks discretize neural ordinary differen- tial equations? In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors. Advances in Neural Information Processing Systems, volume 35, pages 36520-36532. Curran Associates, Inc., 2022.
A. Saxe, J. McClelland, and S. Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. International Conference on Learning Representations, 2014.
A. M. Saxe, J. L.. McClelland, and S. Ganguli. A mathematical theory of semantic development in deep neural networks. Proceedings of the National Academy of Sciences, 1 116(23):1133--1154) 2019.
S. I.. Smith and Q. L.e A bayesian perspective generalization and stochastic gradient descent. In International Conference on Learning Representations, 2018.
N. Timor, G. Vardi, and O. Shamir. Implicit regularization towards rank minimization in ReLU networks. In S. Agrawal and F. Orabona, editors. Proceedings of The 34th International Conference on Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Research, pages 1429-1459, PMLR, 20 Feb-23 Feb 2023.
A. V. Varre, M.-L. Vladarean, L. Pillaud-Vivii and N. Flammarion. On the spectral bias of two-layer linear networks. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 64380-6441 Curran Associates, Inc., 2023.
R. Vershynin. Hiigh-Dimensionl Probability: An Introduction with Applications Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
13

---

Z. Wang. Z. Li, and J. Li. Analyzing sharpness along GD trajectory: Progressive sharpening and edge of stability, In S. Koyejo, Mohamed, A. Agarwal, Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 9983-9994, Curran Associates, Inc., 2022.
Wu, P. L. Bartlett, M. Telgarsky, and Yu. Large stepsize gradient descent for logistic loss: Non-monotonicity of the loss improves optimization efficiency. arXiv preprint arXhv:2402.15926 2024.
G. Yang, D. Yu, C. Zhu, and S. Hayou. Tensor programs VI: Feature learning in infinite depth neural networks. In The Twelfth International Conference Learning Representations, 2024.
C. Yun, S. Krishnan, and H. Mobahi. unifying view implicit bias in training linear neural networks. In International Conference on Learning Representations, 2021.
H. Zhang, D. Yu, M. Yi, W. Chen, and T.-Y. Liu. Stabilize deep ResNet with sharp scaling factor Machine Learning, 11 (11(()335993399)) 2022.
D. Zou, P. M. Long, and Q. Gu. On the global convergence of training deep linear ResNets. In International Conference Learning Representations, 2020.
14

---

Appendix
Organization the Appendix. Appendix A presents some useful preliminary lemmas. The proofs of the results of the main paper are presented in Appendix B, while additional plots, discussion, and experimental details are given in Appendix C. Finally, Appendix D discusses some additional related work.
A Technical lemmas
Lemma 4. For a >> 0 and x E [0, 1/2).
(1 > 1 -2ax.
For >> 0 and > 0 such that ox & L,
(1+ x) < 1 200.
Proof. Regarding the first inequality of the Lemma, we have
(1 x) = exp(a log(a (1- =x) > exp(a(-2x)) > 1 - 200r,
where the first inequality holds for [0, 1/2]. The second inequality of the Lemma is proven by
(1 + x²" exp(a log(1 + x)) exp(ax) & 1 20x,
where the second inequality holds when or < 1.
Lemma 5. There exists an absolute constant > O such that, for 2 C and x 2 1,
Lexp(-vLx) < 4exp(-x).
Proof. For any R,
L Lexp(-vIL < 4exp(-x) + exp((v[ (o)() > 4
Then, for and > 1, we have
- 1+ (VL - 1)x + (VL - 1)
1+ =1 1)x (L + 1 2 2VD)2²
1 + 2 2
1 4
> ( -)x +
+1 2VD)a²
For L large enough, 1/2 1--1-20 1-1-244 2vL > 0. Thus, since >> 1,
exp((VL - 1)2) > (VL - 1)x +
+ - - +1 -2VL)a
4
2 2
I 1
+ 4
2)xr
2
where the last inequality holds for L large enough. This concludes the proof.
Lemma 6. Let h Rd,, N E Raxd with i.idd. standard Gaussian entries, and
NN
hT N
YI
Y2
1
Then
Yi (d) and Y2 (00 1).
15

---

Proof. We have, for i E {l,...,d}.
(Nh); Σ Nigh.
By independence of the (Sig) deduce that (Nh), follows NO [|]l²) distribution. Furthermore, by independence of the rows of N, the (Nh); are independent. Thus
Y1
(N))
|
follows (d) distribution. Moving on to Y2, we have
Y2 |
Nightlh..
Thus Y2 follows a centered Gaussian distribution, and by independence of the (Ni))esied its variance is equal to
Σ JJ
h 11
|
which concludes the proof.
The next lemma shows that the PL condition implies exponential convergence of the gradient flow. is a well-known fact (see, e.g., Rebjock and Boumal, 2023, for an overview of similar conditions). proved here for completeness.
Lemma 7. Let RDD IR be differentiable function lower bounded by smin R. and consider the gradient flow dynamics
dx
dt =-V((x(t)))
If f satisfies the Polyak-tojasiewicz inequality for 1.3 0
[V > ((f(x(t)) fmin):
then æ(t) converges to a global minimizer Toc. and, for t 2 0,
f(x(t)) - fmim & (f(x(0)) f f
Proof. By the chain rule,
dt f(((t)) (f((()))) dr -V)
dt
Plugging in the Polyak-Loojasewiiz inequality,
di f(x(1)) < -u(f(((()) - fmnn)
Thus
d (f(x(1)) - (min) < -u([(x(()) - fmin).
di
To solve this differential inequality, one can for instance use the comparison theorem (Michel Petro- vitch, 1901), which states that f(x(()) fmin is smaller that the solution of the initial value problem
d
g(0) f(x(0)) fmin
dt gg(() -)1g(().
This shows that
f(x(t)) fmnn & (f(x(0)) fmin)e nt
16

---

To show convergence of the iterates, let F(t) vp lo [VV + 2/f((((t) - fmin- We have by the Polyak-Lojasiewicz inequality
[V
(1(1) = [V (VT f(x(t)) fmin 0
Then
dx ds
ds ! [V
F(U)
F())
0
Vp
v/
showing that sr) converges.
Lemma 8. With the notation introduced in Section 2, the following identities holds
R²WW = Rmmi + 1 |X(w" - 1pp
and
4X(R" - Rmmin < VRR (podd)) < 4A(IR RRoin)
Proof. We have
1 11 X Xupmall 11 n
R² RWW)-
ly -Xw" + +X(w" - 2prce)l
|y Xw" + ||x("* Upreae) 7 Xww, "'w"" -ppoo))
n
Rmin n || (umaa) )
2 (x (y- Xx=x w² Upma))
where the scalar product is equal zero because R! (w*) -2 (y X X O. This gives the first identity of the Lemma. Next, denoting π ((pp)) the projection of Uprod on the orthogonal subspace to the kernel of X, we have
Tx
R'WW) Ruin
|| [x(w" - ((upoaa))1
n
(w* ((poos)) T X X X(w" x (Wpood)
I ग (W l1al1x T X(w" I (Wppocd))l
By the formula (6) for the gradient of R!,
V (woo))le = | X (w" Uprod)]l2
|| X(w* T( > 2A Alo" n (Wprod)l2
where the last lower bound holds because both w² and (W)roa) are in the orthogonal to the kernel of X. Plugging in formula above, we obtain that
Rd (W) Rmin & 2X VRR
(upmat Il2 f RR' (wpmoa) = 4X IVR (1
Finally, to obtain the upper bound on the gradient, note that
V (Wproe)
| "xw""" Wprod) )
n
ne (w* - Uprod) T x X X X(w" - Wproa)
4A
(w* Wpros) T X X(w= Wpros)
n
4A(R" - Rmiu).
17

---

Lemma 9. Take WI.... WL E Raxd such that, for all E fl......4 L}.
[W ... Willa lll & M,
and
Wi > m, mmin (W&
where M 3/ 1 and m E (0, 1). Then, for all such that maxiskEL 10x112 &
m aMZ. letting W₁:
8g, W& + L' we have
||W ... W1 2M,
and
min (We Wi) >
m 2
Proof.
First note that the assumptions imply that, for any < < k: & L,
[W W W11tll2 WVi....W+1l. Will2
I1 ... Will min (W, W1)
M
(9)
Tmin (W....W, W1)
m
shall come handy to extend this formula the case where h. where we define the empty matrix product to be equal to the identity matrix, which has an operator norm of 1 & M
Now, take any 0 as in the Lemma and any ho E Rdd Let, for k > 0,
h& = Wk Wiho,
and
h1 = W.... Who.
Then
ha =Waha-1
and
hss = (Wa. + Og hR--1-
Thus
8k hha-1 + Wa(hx- - 11-1)-
hy hy
Since ho ho we get by recurrence that, for l 3
hg hy Σ Wk ... Wj+1 0j hj-1-
(10)
From there, let us prove by recurrence that
[lıella & 2Mlloll..
(11)
This equation holds for = 0 since M > 1. Next, assume that it holds up to a certain rank and let prove it rank k. From (10), we get that
1,
1hg hxlla < L
Σ j=1
[W ... W 1111111111
(12)
Since M > and m particular that |10yll2 m
< 1, the bound on |10, ll2 from the assumptions of the Lemma implies in
Utilizing this, well as (9) and the recurrence hypothesis (11) up to
rank & - 1, we get
M
lhe hull2
&
2M 2M & M M
L
m 2M
1=1
Then
nhe la < |//u/12
11 1xll2 & [ Willel/holl M/ooll & 22Mlioll2.
18

---

This concludes the proof of the recurrence hypothesis at rank k. We therefore get that ||W ... Wi la 2M.
To prove the lower bound on the smallest singular value W.... W1, observe that
|l4ull2 > ||aal12 l|kz hull2
mii (W ... Willlholl2 1
Σ W ... W 10l
by (12). Finally, by (9), the bound on |00l12 from the assumptions, and the upper bound we just
proved on | 112,, we have
|/all2 2 m||/tol22
I
Σ j=1
k
M
m
4M2
m²
2M
holl2 3
m
2
holl2
This concludes the proof.
B
Proofs
B.1 Proof of Theorem 2
For a twice continuously differentiable function ʃ RP - I. the largest eigenvalue S of its Hessian
H(f) IRD" RDDD at some IR. admits the variational characterization
S
lim 8
sup ICE
| - 2||2
In our case, the parameters are set of matrices and the formula above translates into
Σt [V Vv (WV)
S(w)²
lim sup SE
(13)
5-0 I|: p W.
Σ [W W
We now take W to be arbitrary minimizer of R__ To obtain the lower bounds, consider for & < 1
Wx(E) W4 + EMR,,
where the My E Rdexde-1 are parameters that will be chosen later (depending on the W₂ but not on E). Then
El [VR² (V(EE2
S(W) lim 8++
(14)
<² E² &|
To alleviate notations, drop the dependence of W4 on Recall that, for any parameters W V&R"(WO) = W W pVR (
T ...
W
with
2 xx X(w" w wpra))
w:0 "rod WOOT WH p and VR (w
For minimizers of the empirical risk, V&R4(W) 0, so
A = (W) - V (VV) W W.NVR (mpod) T WT. WTI- (15)
Minimizers of the empirical risk also satisfy that X X XWipm = xw= Thus, by adding and subtracting differences.
2 X Tx X(uprod Wprod)
V R (Wood
11
2 x
xT
WT. WL,WW. - W.WWE ... WIP)
n
k=1
2 _
X
Σ
WT.
WI, WTt1 ... ......)..I)) + +(E)). (16)
km
19

---

Here, and in the remainder of this proof, the notation O is taken with respect to the limit when ç + O, everything else being fixed. In particular, inspecting the expression above, we see that v R([ (padd = (g)), and therefore, going back to (15), that
A W W;, pVR (uprod) WT W + 0(52) A. + +0(5)
(17)
By the inequality of arithmetic and geometric means, and by subadditivity of the operator norm,
| 0(*))
| 12 + +O(5
2/L L [ (21]
+0(5")
k=1
> L [II A1ll2) 2/1 + +((5)
(18)
By definition of Åk.
Å
Å (-1)² R2! (wppod)" T wprod V VR (Wprod) W Wprd V R (w (rodd)
L-1 times
= = (1oro "prrod) L- L- 12-11-1R (iiprod)
= =(-1)"p(VR) ((aa))) ) VR R (1prod))
where the last identity comes from the formulas VR (wppa)) X Wuprod = X Xw= Thus
2 X X (1ūprod
Uprodd and
Arll2 (VR' (Kppee)) "=) 1-1 1lp|| VR' (eūpoa) ll2
Rd (Wooa) T w
> (VR' ((i
"." 1--1111 ) 1p11 I 1
(w (pod)) T "w*)=1lpp)
1 1/2
and, by (18),
(VR (1pp) "w"" >1x1111 2/1
2 > L
+ 0
(19)
| 112 2/T.
1=1
Coming back to (16), we have
2 x XW. WILMMWIT ... WIp+0
w VR' (Wpma)
w
At this point, the computations diverge for the two lower bounds want to prove. For the first inequality, we take M₁ = BB We. where the Sh are free parameters to be optimized. We have
w" VRR (wpp)
3R 3 T x x XWI
WT ... .....
n
L
Σg
Bk w
T X Xiprod + O(g2)
k=1
2
Σ
BR T
x T Xw" + 0
k=1
L
25a (gfa|w"11] |12 Σg
BR + O
j=k
20

---

Therefore, by (19),
1 2
Σ A 4L52 aL52a2||w"15 1112112 11-55 & 112112
Σ
Bk +E((5).
Furthermore,
Σ M 1 = Σ B 113
By (14), we get
Eken 1 3n )²
S(W) > 4La² 1 112 11- 11p12
Ek 88 1
The first lower bound unfolds by taking 3g = W Moving on to the second lower-bound, we now take
2 W1 x
Ms = 3k Uu le 2xl1
2A = W
'x=, 2k = W ...W..P. W.PP. P.
n
where again the 3& are free parameters to be optimized. We therefore have
2 w T
w VR VR-( (Uppdd)
- XWT WT., Mr WT ... WIP+
n
k=
Be 12/1ua/l2llu//22 (E33)
3e WeIlWT K+1 WIrllallus T 2 _ WI + O(53)
8
n
k=1
BallW k+1 ... WI ww T 2 XxTx W
1m
where the last line unfolds from subadditivity of the operator norm. W WT, pw T2 2xTXW WT,, and choose 3a | Then
We let A
prod VR (Wppod) >
| + O
k=1
Coming back to (19), we get
L Σ
L 2/1
A [|4x11)) 2
+0(5))
|
12/2
Furthermore,
L
T
12
L
L
W4 WA1 = 5²
8%
g2
52
||A
|ux
12
2k
11
=
km
Therefore, we obtain, by (14),
1 2/1.
S(W)2
2
Σ
A
2 2/L
We can lower bound the sum similarly to (18):
A > L( ... /11l))
21

---

and
- X X ... prod T 2 -x X
AL ... A1 = pw- -x
X wrodw +T
L-1
times
xx ( _x Xw"
4-1
2
w
-
=xXx.
X.
Thus, using the Cauchy-Schwarze inequality, we get
2
4-1
1pw 2 -x X|12
2
A ... A1ll2
X
Xw=)
71
2
1-1
X Xm#*)
1|lll||w**
x x|12
n
n
Dpll
w =x
_xxx="
2"
[|lla
[ala|lww11 112 222-1
Therefore
| > 4La² 1|=1 |La²||w=11
km
We finally obtain
S(W)² > 4L'2a'110011
Ilella
which gives the second lower bound.
To obtain the upper bound on Smin. we construct explicitly a minimizer, and upper bound its sharpness. More precisely, let the W; be rank-one matrices, such that ||Wll22 || || 1| ///////lp ||pl', successive matrices have aligned first singular vectors, the first right singular vector of W1 aligned with w*. and the first left singular vector of W, is aligned with We then have
WL W1 ="
meaning that the network minimizes the loss. We now upper bound its sharpness using (13), where we recall that the matrix appearing the numerator is denoted by A₂ and satisfies A, Å ( where A& is given by (17). Contrarily to the proof of the lower bounds where exhibited specific direction W, we here seek upper bound valid for all W. Recall that, by (16), we have
2
V R (10))))
T X
W
WT WT,, ( Wa) T
WT k+1 ... W. (20)
By subadditivity of the operator norm,
|VR (1pmoa)lla 122 & 2A
Σ Wi ... I WllllWl Wellal|We+1lle
||Wllallelle + O(
2=2
= 2A || (L-1)/L
1p112/
1/L
Σ [ W
(21)
k=1
Moving on to bounding the squared Frobenius norm of Ae. we observe that As decomposes rank-one matrix. We split cases for & = and k > 1. First, for k = 1, we have, by subadditivity of the operator norm and by (21),
|
|W WTJ p|l2| V Rt (mma)l + O(E2)
[2ll2 ... [| WWL/l2llple R (Üprod) 1l2 + O(52)
< 2A|lw a| 11/1//112(--11)// 2(4-1)/1
||
Σ I W4ll -(())
22

---

Then
|
< <AA 11 4(1 13/1
1111 1/
1 Wallz) + 0(())
< 4TA | 1 11/1.-11//1
11
4/1.
I1 w 0(5))
1=1
< 4TA 11
11:12/ 2/2
11 Will + 0(g9)
For 1, we have
|A [ w pl pll VR' (upped) W. W 112 + O
< [W 1l2 ... W la lllllll VR (wod
W, ||2 W2lle
|| 112 2/) lp / VR (Wpod) W,] 1|2 + O
(22)
Let us now bound |/ (1 (wod W11 12. By (20), separating the first term, we have ( W.T. 1|2
1p
Wt. WT,
W2(W, WW) - x XTWTI112 l2
W2 ... WW+ W W3 2 x x
2A 2A|pP|a|| 1112 Well2l1 - Willa/lWill
XW, 1Plla||Well II Wellll/ ww _xxxTT +0(5)
2x
2=
I|allW - Willa
Σ
| 11 (L-2)
2
2/L Wi
2
Xx,T | Wall +
Finally, recall that W1 is rank-one and its first right singular vector is aligned with w*. A short computation therefore shows that
W x XW,
2
= -2al| = 2a|lw* 11 1|rl2 2/L
Thus
L
V (1ūpod) T W 12 < 211w=l12 (AIIW; - Wille + a Σ
l - Walla) + +0(5)
k=
Then, coming back to (22), for k > 1,
|
< 2||w= 2| (12 1)/
1121//// (Allir Willa + Σ w Willz)+ + 0(E3).
Thus
| 11 < 4/|w=1
(AlIi wille + Σ
I| Walls) + +OEE)
k=
< <111w01|b(6-1)) 110 4// (A² (A2 + +(L - 1)a2)
Σ
I -((
k=1
< <4/1w""1b((111//// 4/4 (A2 + (L - 1)a
Σ
I -
k=
23

---

where the second inequality holds by the Cauchy-Schware inequality. Thus, by (13), putting together the bounds on | & for k 1 and k
Ei=1 1
S(W)²
lim
sup
8-0 || wall ss Σ I Woll
lim 4|| 112 5-0
(11(1-1)) 1)/- || 4/ (T.A² + (T. 1) + ((,-1)a²)) + O(g).
Therefore
S(W) & 2||
12- 112
1112 -
which concludes the proof.
B.2
Proof of Lemma
This identity can be shown by noting that the identity is trivially true for = 0, then differentiating on both sides with respect to time, and using (5). We refer, e.g., Arora et al. (2018) for detailed proof.
B.3 Proof of Lemma 2
Before proving the three statements the lemma in order, we let
E max IEkEL
[WL(O)] +
[ (0) - (W)O) (0)l22
Note that & & 8.
First statement.
The claim is true for l = T, since Wr is a (row) vector. For & E (I...., --11. 1}. taking the 2-norm Lemma we have
W We+1lle = [| T + W W (0) - (o) (())l
< W à lla + (0) (w (0)ll2
Thus, using || A = |AA 2| ||
W 113 W ++ (1) W < |
(23)
We now take the trace in Lemma to obtain
We+1 J Combining with the inequality above, have that
= || - (0)1
w - 1 < || || + (|W+)) [|
+ (O) Ww (0)]l2
Summing from l: to L - and telescoping, we have
[ ||
[W2l l [[) ([
1-
(1) (o
The first two terms compensate since Wr vector, and the remainder of the terms is less than E & E by definition. This gives the first statement of the Lemma.
24

---

Second statement. obtain that
Assume without loss of generality that j > k. By recurrence over (23), we
E
& of +E.
The reverse inequality can be shown similarly: by considering again Lemma and taking the 2-norm, get
WW &
[ k+1 W || (0 W (0)llz
Thus
W [| WW++ill l + [W (w (0)l22-
(0)l2.
As previously, get by recurrence that
of o
Combined with the reverse bound above, this gives the second statement of the lemma.
Third statement. Let us lower and upper bound _ W +++ WK+14K- uk. We have on the one hand, by Lemma
Ug W k+1 W u4
u2 W un W (0)uz + 4f (0)W u1 W WT uy -u, W.()) (0)mx
o [0
On the other hand,
Ug WT
Wk WK+1 uh = uyg (W Wk+1 uk+ uk+1 111 ug uy th+ 10 1 uk
< <I k+1 Wx+1 2 + (Uk41, 20)2
The 2-norm above is equal to the second largest eigenvalue of W k++1 W which is the square of the second largest singular value of Wk+1. In particular, it is lower than [| ll || which is the sum of the squared singular values of W except the largest one. We obtain
T WT W uk & W I| - W + (0k+1, ux) 20)2 & E + (BE+1, u4) 20 dg k+1
by the first statement of the Lemma. Combining the lower and upper bound of ug WT get
k+1 W Me, we
(w++1: ux)
2 o+11 2 of [[W((0)12
Thus
(o) -
of - -
| -
(Uk+1. m
oltt1
by the second statement the Lemma. We finally obtain
28 + W (0)1
(MK+1, 2
k+1
by definition of and e.
B.4 Proof of Theorem 3
We lower bound the first term the sum of the left-hand side. Recall that, by (5), we have
(WRL(W())) = (Wz(t)... ... (2(()) VRl (w)
d1x1
Ixdo
thus
(W -| (2) VR (w)oa(())))
(24)
We show that [[W(()).. ... W2(O)l2 is large by distinguishing between two cases depending on the magnitude of (t) [f)l(, To this aim, let C' > V2eL.
25

---

Large spectral norm.
We first consider the case where
Φ1 > >>>>> V2
(25)
By Lemma 2, for E fI,...,,---- l}.
k 2 o
2
where the second inequality unfolds from (25). Then, again by Lemma 2, for & E fl,..., L 1}.
(UK+11 u&)
0.
A++
It is always possible (without loss of generality) to choose the orientation of the uy and such that (UK+1, ux) for any & {I.... 1}. Making this choice, the equation above implies that
|0b41 uxl1 = 2 2(UR+1, ux)
E
< 2 1
k
For x E [0, v1 > and thus
2E
| 4 <
(26)
k++1
Let us show that this implies a lower bound on [ ... W2ll2. To do so, let us denote recursively
21 U2
Øk+1 = Wk+1 for e fl....... L 17.
We then have Jt Wt W231, thus
|ær.112 = ||
WW ... W2 >
|
Our goal is thus to lower bound || 12, which entails lower bound on [W,... W2ll2. To this aim, first note that, for any & E (1,.... : 1-11. 1}.
(1E+1) uk+1) = (WR+1 UK+1)
0h41 (Zp, Uk+1)
ok+1 (rik, Uk + uk+11 ux)
ok (Ik, un) 0k++ || b2
uxl12
ok+1 (Zky ux) /2 (
(27)
where the last equation stems from (26). Denote Og 5u shows that
Ug).
Then the previous equation
|xall (ox+1a4
|
12
/28
V2s)
0:411
|00+1 2
|
112
O'k
ak-1
Further note that ||
& oxt1
1 1,,
thus
V2E
ak+1 3
Tk+1
By recurrence,
V2 2)
ak 02
2
02
2
02
2= xk+1
Vo -
Vo7 -
2=
Coming back to (27), we have
|24+1l22 >
(2841,
> |2 12 2222,
26

---

thus by recurrence,
| > | 2
L-1
II
(0x+ - V28) 3 |
L-1
of - =(02>
22 -2) - -V28)
Voद -
k=2
0i 2
-2ck)
E00
k=
Finally, by definition, 02 = -1 [T2l U2)
Since x2 = W = W2 d2 we obtain that (22 1,
and thus
W Wall2 R
|
L-1
V 09 - - -EVk
k=2
V 9ी 8 (Vo) - - v2E(L 1911-11) 1)) 1--
(Vo7 - Ve- -V2ELL - -1) 4-1
(0l v22L) 4-1
We finally get
W.... Walla > (C v2EL)
(28)
which is positive quantity by definition of C.
Small spectral norm. We now inspect the case where (25) is not satisfied, that is, oI < C. First note that, by the formula (6) for the gradient of Rt,
||V Rd (1proa) < 2A|lW* - pred la x 2A 2A(1|w*11 + [[ppoodl2).
Thus, for || prod la ||w" l|,, Wprod + R' (Wpoo) is 4A || -ipssscch Let us use this property to lower bound (red (t)]l2 by constant independent of t, for >> 1. Either we have [[))pod(t) >
||w* l|2. or poapllll2 w= 2. but then, by the Lipschitzness property,
R² (Woro(()) (t) Rol < W l| Uprod (t) O|1 4A|| lla (t)
where we recall that Ro is the risk associated to the null parameters. Furthermore, for t > 1,
R (Wprod (t)) (t) = R (M(())
(WW(1)
(The risk is decreasing along the gradient flow)
(M((())
(VR)(M(()) # 0 by Assumption (A1)
Ro
(by Assumption (A1))
Thus, for >
R ((ipro((t) (t)) Rol > Ry - R=(W(()) > 0. To summarize, we proved that, for t 1,
Ro - (WW())))
[|u)poa())]22 2 min
4A/|w*112 ||0001 0,
where we recall that ||w= 2l2 > 0 by assumption (see Section 2). Furthermore,
(t) & [t) ... (1) [t)
(2(
Then, for t > 1.
1
Ro Rº (W(L)) |1,01112
(W.))) >
min
0. (t)
4A|lw*le ll2
Ro R=(W(1)) || l12
C min
(29)
4A |A|| 12
27

---

Conclusion. Combining (28) and (29), we obtain that, for t > 1,
[.. W2(t)]l2 min (CC- V2EL) 4-1 min
Ro RW(W))
[[W ... where by the proof above. Then, for > 1, by (24),
vpi,
C
4A/lw=12 112
[ > pr VR (pprod (t))
By Lemma 8,
VR ppod Thus, taking μ 4p14 O, fort 1.
(pmaa())) (t)) (M(()( Ruin)
Σ Il (V > ((((( - Rmiin.
B.5 Proof of Corollary 1
We first show that Assumption (A2) implies number of estimates that useful in the following. Since || 2 2 1, we have
1/L
1/L
(30)
2
thus
SLE & 8LVE
&
|w=1|
1/2
1/L
<
(2110" 1/2
(31)
2
Moreover,
||=0
1|2
2/L
1
7
4
so we also have
||
2/1
8L <
(32)
2
Let us prove the Corollary. We first note that Theorem 3 implies exponential convergence of the empirical risk to its minimum by Lemma 7. This also implies the (exponential) convergence of Wpod to w", since the covariance matrix X X is full rank, so w² is the unique minimizer of R_, and, by Lemma 8,
Rd RL(W)- - Rmin = [|[[ww" wproa)l2 A||w= Wprod 112
Furthermore,
Upood ll2 = [[WTT WIll ll & [W W <
máx oN )² k=1
Let us show that, for large enough,
||w01|
1/b
max 0 > 1=1
tc.
(33)
2
If it were not the case, then
12 E
max Tk k=1
1.
L
1222 1|2
1/L
+ E
2
||00
l|2
1/1
+
2
||
1|2
||00
||2
(1
2
1/4
+
2LE
2
1
28

---

where the last inequality holds by Lemma 4 since
1/L
2
1/4
Le
<
1
Le
2
which holds by (31). Then, we obtain
3/120*
1|2 <
since
2
1/L
3
| 12
1/6
+ 21.
4he &
| 112
which also holds by (31). The inequality [/x)pred] |12 to w thus proving (33). Then, we have
<
311 llz
contradicts the fact that Wprod converges
L max 1=
(110"11 112
2/L
1/7
||10|12 2/L. tG,
>
+
25
2
2
where the last inequality holds by (30). Furthermore, by Lemma 2, for all k E {I..... 4}.
o
max maxoj- -E.
1
J=1
This brings the first inequality of the Corollary. We now show the second inequality of the Corollary. First note that, by Lemma 2,
I o u
1P:
||
since both quantities are equal to the sum of the squared singular values of Wi except the largest one. Then, adding and substracting,
W.T W 01 ILvIn rluill2
WW. WW okueV Jokt1 .oaet.....peeee 0104414441 vrulle
[ [Will.... WW-l oxwani 12004111
01 - W 1
k= jz
Okk
j=1
min
j=1
LVVE
1/L
oj
||ut
j=l
by the first inequality of the Corollary. Moreover, using again the first inequality of the Corollary and Lemma 2, we have that
(UK+1, (
L/L
0k+1
la
29

---

Since Tn = 1, we deduce that
L
|or... l ... u..
ll
II
ll2
u uk+1
k=1
k=1
L
2
Ok
2/E
w 1|2
k=1
L
(L-
-1)
2/
10 ll2
k=1
where in the last step we used Lemma 4 which is valid since
w 2
2/L
+
|
2/T.
2
which holds by (32). By the triangular inequality, we now have
1 (L
1)
II k=1
< <101...oz01u ... .ruull
||00 1|2
2/L
[WT W2 + I[T
WT - 01 or....
awri ... -0....oouu
uuu 12
L
L
< WTT W
ok
[ ll2
k=1
Thus
L
(L
1)c
LVVE
< WWT
WIll2.
ok
2/L
1/1
| ||2
|| ||2
Using (31) and (32),
(L - 1)8
LVGE
1 1 3 4
>
1
||== 2/L
[1 2
1/E
8
2
Moreover, the product the singular values can be lower-bounded by the smallest one to the power L,
3(min oR)
... [|T....IIla.
4
Let us show that, for large enough,
min の < (2|| (211
were not the case, we would have
3(2)l1=*|22 112 - -e)²
WT WI
3
11
E
b
2
(2||w0) (2)
3
2LE
l|a
2
(2| 12))1/1
9
||2
(34)
8
30

---

where the second inequality holds by Lemma 4 since
22
12)
2
by (31), and the third since
2L
1 4
(2 22 122 1/
Le
<
(2) | 122
also by (31). Since 9/8 I, the inequality (34) a contradiction with the fact that [[ ... WZ ll2 ||Wpodl22 + ||w*|2, showing that, for t large enough,
min ox & (2|1==1122) 112)
Thus
min o & (211=*112)2/ 122 + -22(211u==11)) 112)
By Lemma 2, for all l E ().
o min oj +
< (2|1w0 112) + 222)(22w" +e
(2[1w0112)21
since
2E | 12) + E < 0
+ 2<2(22)20* 112)
which holds true by Assumption (A2) since
< 2(2 (22)2=1112))/ 1/2
since w!=" 1|2 > 1.
B.6 Proof of Corollary 2
The lower bound unfolds by definition of Smin since WSI is minimizer of the empirical risk. To obtain the upper bound, we proceed similarly to the proof of Theorem 2. For simplicity, we denote W WSl in the remainder of the proof. We have, as in the proof of Theorem
ΣL IV (W)) V R (WV) 12:
S(W)² lim sup
(35)
<-> W W. EE
Σ
WE
Wxll
with
A (W) Vz
-W ... WI v R8 (1prod) T WTT ... ...WTT +
and
L WT WW - W. + O(E2).
= 2 T
VR (
We recall that, as in the proof of Theorem 2, the notation O is taken with respect to the limit when E -+0 O. everything else being fixed. By subadditivity of the operator norm and by Corollary we have
L
V Rd (1pma)l22 & 2A
Σ k=1
Wi 2 ... [ W2 WallelWWa-1lle |Wr]|2+ + 0
< 2A(22 [2) (L- 1)/2 Σ
1W - Wx12+0(65))
(36)
km
31

---

Moving on to bounding the Frobenius norm of As, we observe that the dominating term of this matrix decomposes as rank-one matrix. Thus, again by subadditivity of the operator norm, equation (36)
and Corollary 1,
| F = | W. 12 V ( (podd) T WT W T 122 + O
< [Wa+1ll2 [ W2l/ (i prod 1| [W 1l.12............. W O
<
I + (1))6-11 13/2 Σ
k=1
Then
| < (211001)))
4(2 4(2-))((11) 13/L
W4 Wall)) + +0(5
< 4TA (2| 112)
[W Wal3 + 0
k=1
< 4T. (2 (1112)((([(-1)))
Thus, by (35).
S(W) & lim (1)
1)/2 17
{->
Therefore
S(W) & 8LA||W011 112
which concludes the proof by the second lower bound on Smin of Theorem 2, where here ||p|| = 1
and À > 0.
B.7 Proof of Theorem 4
To alleviate notations, we omit in this proof to write the explicit dependence of parameters on time. Starting from (5), since the gradient decomposes a rank-one matrix, we have
| VWR = [[ W. pl V V (wirod) W.T WT
mi (WT k+1 WI 1p min (WT ... W.. R (upred)l2
By Lemma 8,
IRR (Wpoo)) 112 > 4X(R" (W) Rmin).
Recall the notation introduced in Section 5
Hi. WL We and I == We ... W1.
Then
(' > 12 (T 1o (T)-11) (R (W) Rmann)
(37)
We now let > 0 (whose value will be specified next), and
Jr = inf {{ E R., 3k E (1..... LJ. 10x10
exp( -2p2 4m) }
64
Let us lower bound the minimum singular values of I1. and II uniformly for t E [0] by Lemma 3. By definition of tm, for t* and for any is E {I,..., 4). ||0x 2l2 & exp(- -2s² 4u). Therefore. renaming C₁ to C2 the constants of Lemma 3, and taking u = C2. we get that, if
L> max (c1,
d E2
(38)
then, with probability at least
dC3
1- 8exp
32s2
32

---

it holds for & < t" and for all le E fI..... L} that
(2 + Cz)
(8²
[Tall < 4exp
(39)
and
1
(-
-
2s²
min (1La:1)
exp
By symmetry, the same statement holds for I1 instead of Ilg:1 with the same probability. By the union bound, the event
E = N
{
{Illetlle 1l2. ||lzall2 < 4exp
( +
s²
IELEL
(- 23²
and amin (Tla mmin (Mzsk)
> 4
exp
d - C3
holds with probability at least
1 16 (-
dO3
32s²
Let now
Es b2 { R² Rmin
C1 1p
and Eg the event that the gradient flow dynamics converge to global minimizer W of the risk satisfying the statement (8). We show next that, if E₁ and Eg hold, then Eg must hold, which shall conclude the proof of the Theorem with
(2)
C33
C
Ci max (
C2 = C2, Cs
C.
32s²
(40)
C 2 exp (-4x²- 4s2
16s
2003),
C3
1
exp( -2x 4C3).
C2
64
Under E,, we have
0 min 111 (iin (II=1a))
>
1
exp
(-d - 403).
852
28
thus by (37)
(W)
26 exp (- -403)/11p133 (1W)((((e Rmminn
8s²
10s)
d
Therefore we get the PL condition, for & t",
VW) > ((R²(W) Rmmiu)
with
26 exp (- (-
1
85² - -4Cs) Al|p||2L.
By Lemma 7, this implies that, for t < t*,
R² (W) Rmin < (R*((V(0)) - Rmin)e
(41)
Let us now show that t" = 30. We have, since 8(0) 0 and by definition of the gradient flow,
|x 1|0 (0)] < //" |V (W(G)))
(42)
We now upper bound the gradient as follows: starting again from (5),
| Rd (W)llr = ||W W. /l222/RR (Wpea)) WT WTT ll2
| k+1
W. 122111112 WW WT,, ||2|| V (upood)l2
33

---

By Lemma 8, we get
(W)ll & 2 Walllllla Wi-llla (LW(W) - Rmin
(43)
By (39) and (41), for & t*
|R (W)] & 16exp(s² + AAa)) - Rmine 21 Plugging this into (42), we get, for < t",
(44)
| || < 16 2 + 22ss) V Alpll R=(W(0)) Rmia S - dt
32 exp +200) VAIAAAAP//1// R=(W(()))) REin
1
2 exp(s2 + 852 J Allp|l2 +
- Rmin
where the last equality comes from the definition of μ. By Eg and by definition (40) of C4, for t & t*,
8s² d + +60))V 128
10 2 exp(s²
exp( 2ap(-22²- -
If had t* oo, would have, by definition of 1*, [10((t))] > 04 exp(-2s² 4C3). This contradicts the equation above, showing that 1" = co. By (41), this implies convergence of the risk to its minimum. We also see by (44) that V (WV) is integrable, W has limit as f goes to infinity. This limit RRI is a minimizer of the risk and satisfies the condition (8) by definition of t" =c.
Extension to multivariate regression. We emphasize that a very similar proof holds in the case of multivariate regression, where the neural network is defined the linear map from TR to Rdd
WL ... Wi
and we now aim at minimizing the mean squared error loss
1 l Wt ...... W W 112 n
Rd R=(W)-
where X, Raxd, In this case, as shown in Zou et (2020); Sander et al. (2022), the following bounds on the gradient hold:
& (W)l > 2 min (T (Iza+1)o (Tk=1a)(R(WW) Rmin)
and
V (W)) & 4A 12 (3 - Rmin)
Comparing with (37) and (43), the only difference is the absence of [|pl|a here. From there, the same computations as above hold (taking ||p||2 = 1), and give the following result.
Theorem S. There exist CI,..., Cs > depending only on s such that, if L > Ci and d > O2, then, with probability at least
16exp((-3dd)
if
R²(W(())) Rmin Ca
the gradient flow dynamics (4) converge global minimizer RR of the risk. Furthermore, the minimizer WiRL satisfies
Rl
I+
N +
with | & Cs 1
LLd
I
34

---

B.8 Proof of Lemma 3
We begin by proving the result when # O, then explain how extend any & ball around Recall that I1 denotes the product of weight matrices up to the k-th. Let
2 2
1 exp
2s² d
Ma 2 exp
+
Ma,u
and denote by A the event that for all k; ||TT ll2 & M. and B the event that for all k. m (TT,.1) > Ms.a. We begin by bounding the probability of A, then bound the probability of B n A.
Useful identities. To this aim, first introduce some notations and derive some useful identities. We let F& the filtration generated by the random variables NI,..., .Ng. For some hg E Rdd, we let
......,,,,
hg 1l (I+
No) (I+ 8 N1 ) ho
VLd
VLd
In partieular, h441 and h2 are related through
hK+1 = (T+
8 Na+1 hrg.
)
Ld
Taking the squared norm, we get
s²
2s VLd
|| i 112 |1
|
he
mi Netihe.
Tad
Dividing by | and taking the logarithm leads to
s² 3211|N++1hk
2sh Nx+11hx Tadlhall
In (c]1 = In(11/ + In 1+
(45)
Let
V2,1 52 1
Vx.2 25hh1 Ne+1hs ha Ld hx12
v VLd
and Yg Yx,1 + Yk.2 Then, by Lemma
s² FR La xdd) and Yx./FF ~ N4(1,
4s²
(46)
Ld
This shows in particular that V2,1 and Yx,2 are independent of Nı,..., Then, letting
Ng. and depend only on N
A-1 ΣX,, Y, and Sk.2 = Σ
k-1 1
S
Yj2
j=0
==0
both are sums of i.i.d. random variables. In particular,
$2 St,1 Ld (Ld) and Sr.2 St.2~N N7(1
4s2 -//
Bound on PAA). We first bound the deviation of the norm of has 1l.-1ho for any fixed ho E Rd. then conclude on the operator norm of IIx:1 by an e-net argument. For any (fixed) ho Rd and O, we have
P
max L
> exp(s² + 2u)
|
12
= PP
max In( 11x (12) - In(1 > 52 + 2w) 1
82 8211 113
2sh NJ+ 12
P
max
(1+
> 52 + 2u
&
h
v Ld 12
j=0
1 I13
2sh N5+thh
P
max
> s2 2u
Ld h
Ld|lh,
35

---

by using In(1 + x) &
Thus
| 1
IP max 1EKEL
2 exp(s= + 2u)
PP
max LE
Sk,1 + Sk.2 8² 2u
< P
max 1E
Sk
52 + w) + P max Sk.2 2 u)
IEKEL
by the union bound. We now study the two deviation probabilities separately. Beginning by the first one, recall that L1,,1 follows a (Ld) distribution. Chi-squared random variables are sub- exponential, and more precisely satisfy the following property (Ghosh, 2021): if X ~ (c(c and 0, then
u²
4(c (-4(c+ w))
P(X > c u) cxp
(47)
Since the Sk.1 1 increasing, we have, for 0.
Sk > 8² + + P(SL, 30 2² + u)
max Lg
Ld Ld + 5²
Ldu
P
S1
82
122
Ldu2
< exp
exp
(sd + Ldu)
4s 4 + usa
Moving on to Sk,2, we have, for u, X > 0,
P max Sk.2 > u) =IP max exp(ASx,2) > exp(Au)) L
IEREL
Furthermore, (A is sub-martingale, since Sk,2 is martingale and by Jensen's inequality:
E(exp(AS(+12))F5) > exp(AE(S exp(ASAa.).
Thus, by Doob's martingale inequality,
P max Sk.2 2 u) B(exp(ASL.2)) exp(-Au) L
Furthermore, since S1,2 N(0, 40²).
E(exp(ASz.2)) = =xxp 1s22>2
Therefore,
4
P max Sk.2 3 u lgkE
exp
-u++
d
This quantity is minimal for À =
du
We get, for all u u> 0,
862
Sx > u) < <exp (-
duz
P max 1
(48)
16s2
Therefore, for any 0,
P max 1E
2 exp(s2
2 + 2u)) < exp (-
du²
+ exp
(-
Ldu
(49)
holl
16s
4s4 + us?
To conclude on the operator norm of Th consider Σ 1/2-net of the unit sphere of IRd By Vershynin (2018, Corollary 4.2.13), it is possible to take such a net of cardinality 5d, Let us show that, for any E.
2 <
222 (5+ + (50)
IP max 1
|[ 1l2 > 2exp
- + +u))
U
[1. 1
max
hollo 2 exp
(
hn
36

---

Indeed, assume that there exists & such that [Ta l|2 > 2exp( & + u). By definition of the operator norm, there exists z the unit sphere of Idd such that
| = ||T2-1/22.
But then, by definition of Σ,, there exists ho E E such that || - hollz & 1/2. Then
(x ho)ll2 & |
Therefore, by the triangular inequality,
1
/ooll > | 11 - ho)ll2
2 2 11112 ll2
Then
1 [Teall2 i exp
0
(e- 2 +
| >
2
which proves (50). By the union bound, conclude that
P(A) = (
max 1
2exp
( 2 + +))
(2 +2)
8²
max EEEL
11.1holl2 212 > exp
(82
max L
|TT holla > exp
2 +
where now bu denotes any unit-norm fixed vector in Rd Thus, by (49),
P(A)
< 5dp
max
[14::1
ho
exp(s* + +uu
IE
du²
Ldu²
5d
exp
16s
exp
48 us
This upper bound will be simplified in the conclusion of the proof.
Bound on PPBB A). We now move on to proving the lower-bound on amin (II=.). We again use an s-net argument, as follows. Let E be an s-net for
Then
M.
P
min Jmin (IIm.)) & mm.u) 3) < P EE
U
min
|ooah 2ms.u)
IERET
NEE
Indeed, assume that A holds, that is [I1:1112 & Ma.us and that there exists l such that Omin (II::1 < M..a.
By definition the singular value, there exists x on the unit sphere of Idd such that | mmin (II;.). But then, by definition of Σ, there exists ho Σ such that || hullz E. Then || (a - ho)ll & e
Under A, the right-hand side is smaller than sM Therefore, by the triangular inequality, / < || + || x)112 < man + EM = 22m By the union bound, we conclude that
IP Ann min IEKEL
Tmin (Ila)) masaa }) < P
U
min IEkEL
[[Taa & 2maa))
IP
||1 foll2 & 2me.) IEk$
min
h
EP
min IE
|1l:: & 2mz.u
2Ma
+1) d
min LEkEL
[Ta- & 2ma.a).
Mg,u
37

---

where the cardinality of the net is given by Vershynin (2018, Corollary 4.2.13). We now take fixed ho E Fd and compute
1/ l22
| 2
P
min IEkEL
hool22
=
min 1
ho 2
<
4m
s,u
Denote by E the event
11 Yn. 2
-
1
We have, by (45),
min ||
< 4m
P
min 1EkEL
In In(11/all2) In((1holl)) In(4m3
IEREL
||hol22
<
min 1EkEL
In(1 + +2,2) < 1n(4m3.))
f=0
In(1 + 1n(1+Y (,2) (n ) + +P(E).
min IE
j=0
Using the inequality In(1 + x) > x - x² for - 1/2, we obtain
P 11
--1
4m 8.a
<P
min Li
Σ 12220 & In(4m ( + P(E).
h
5=0
Thus, by the union bound,
TP( min
|
&
4m²
& TP
min [(' (Yj2-1333 -2,2) & In(4433.) +
k-1
4-1
Σ P YY, < -22
L |
L
j=0
k=
Pi Ps.
We handle both terms separately. Beginning by the second term, we have, for A E (1,... L).
P P(V22 < <x2) 2 2) < exp (-
Ld
32s²
where we used (46) and the tail bound PNN > u) E u212 if N ~ NO0, 1). Moving on to the first term, we have
P
IP
min Sk.2 Sk.3 & In(4m?...) 1
where we let Sp.3 = E5 232 By definition of ms we have
4s2 2u.
In(4m d
Thus we can split the probability into two parts by the union bound:
40
Pi < P min Sa.2 < -u) + P( max Sk.3 > d + +u)
1
LEKEL
Let us bound each probability separately. We have, for 0.
du²
TP min Sk.2 < -u) =P( LEREL
max- 1
Sk. 3 u) = IP( max
Sk,2 7 1 1
E exp
16s
by symmetry of Sk.2 and by (48). Moving to Sk,3, we have that
4s2
4s²
102
Ld (1),
Ld
38

---

thus
Ld
Sk,3 ~ (L).
4s²
By monotonicity of Sk.3 and by (47),
4x2
482
P max Sk,3
+ u
P
S1,3
d +u)
IEREL
=P Ld
Lauu
S1,3 3 +
2
4s2
L²d
Lddu²
< <exp
exp (- 16(4s² + du)
6487 + Ldu
18
Putting everything together, we proved that
P(BnA) < 2MM.
+ +1)
P2
exp
dIn
2M
+ (P)+
Mas
Mls.u
with
du²
Ldduu
Pi E exp
(
+ +exp
16.2
16(4 + du)
and
Ld
P2 < L exp
32s²
Bounding the probability of failure.
Putting together the two main bounds showed, we have
P(ÁU B) = =((A) + PP A)
< 5a (expp(
duz
+ exp (-
Ldu?
exp
16s
4s + us²
+ exp (dIn
(2Ms.u + +1))
du
IdZu²
Ld 32s²
exp
cxp
16(4s² + du)) + Lexp
Ma3u
16s
This expression valid for all u, 0 and L, d 1. We now simplify the expression of our upper bound by algebraic computations using the assumptions of the Theorem. To somewhat alleviate the technicality of the computations, stop this point tracking some of the explicit constants and let C denote positive absolute constant that might vary from equality to equality. We show next that the conditions
L> C, d2 C, u 2 Cmmax(2" -2/3), & CL
(51)
imply that
P(AUB) < 8exp (-
du²
3252
This shall conclude the proof of the Lemma with
G C= C, C2 = C, C3 = C max(s 2233), C4 C=
First note that the conditions (51) imply that
Cs and u C.
(52)
We study the terms of the bound on P(ÁU B) one by one. First, we have by (52) that
5d exexp (-
du?
exp (dln())
du²
exp
du?
16s2
16s2
32s
Next,
5d exp (-
Iddu?
< 5d exp (
Ldu?
48 + us²
8us
Ldu
exp
exp
8
Ldu
=exp
(d]n(()
852
Ldu
< exp
16s
39

---

where the first inequality uses > s² by (51), and the last one uses that Lu 32
> C. This is true since
L L> C' and 3 Cs² by (51). Then we can bound this term by
du²
exp
32x
since & CL which is implied by the assumption
& CL
in (51). Next,
2M
2
2s²
In
+1) = in 88 exxp
+ 2u + 1
Ma
2
d
2s²
< In exp
+ 2u
2
d
where we used that the exponential of a positive term is greater than 1. Then
MMM..
s² +
25 + 2u < 3 3u,
In
+
In(9)
(53)
Ms,u
2
4 by (51). Thus we can bound the three remaining terms appearing the bound of PAA U B), as follows:
since u 2 82,
exp (dim 2MM,M + +1)) exp (
du²
du²
& exp (
du?
< exp
3d + 3du
16s2
16s
32s
since
u²
> 21 +
This is the case by (52), which implics that
1
C
C
C² +
2
u² +
uu
2²
+
stu
s² (1 + u).
2
2
2
Next, by (53),
exp
Id
2M
+ 1)) exp (
LdP
< exp
3d + 3du
TuP2
Maa
16(4 + du)
16(4s² + du)
Ldf
< exp
3d + 3du
32du
since du Cs² 2 by (51). Thus
exp (pp(dnn dd'n 2Ma.u +1 +1)
Lafu²
Ldu
Ldu
exp 16(4s² + du)
exp
3d + 3du
< exp
M2,u
32
64
where the second inequality uses that L e C by (51), and Lu 2 C' since > C C'and u > C by (51) and (52). We can also bound this term by
du²
exp
32.
since L Cu/s?, using first that L Cu then that > Cs 2/3 by (51). Regarding the last term of the bound of (PA B), we have by (53) that
MM + +1)) exp
Ld 325²
Ld
Lexp (dIn
< Lexp
3d 3du
(54)
M5,u
32s
Let us show that this implies that
L eexp (dIn
2Ma,u
+ +1)) exp
Ld
< L exp
VTdu²
(55)
Ma,a
32s²
32s²
This statement is true because the three terms appearing inside the exponential the right-hand side of (54) can be bounded by CVLdu² More precisely, we have
Ld
CVLdu
VL Cu²
32s2
40

---

which holds by (51);
CVLdu²²
3du &
+ Cs & vLu,
82
which is implied by L e and a > Cs by (51); and
CVTdu
3d <
+ Cs & VLn
82
which is implied by L > C' C'and u > Css by (51) and (52). Finally, we use Lemma 5 to bound the right-hand side of (55) by
du²
4 exp
32s²
du This is possible for L > C. and Collecting everything, we bounded P(AU by
3 which is implied by 3 C and Cs,, by (51) and (52).
32s2
du
Sexp
32,
which concludes the proof when 0.
Summary when A = 0. In summary, we proved so far the following result: there exist Ci...., C4 > 0 depending only on such that, if
L C1
= C2. ME (C,, C2 C,
then, with probability at least
du?
8exp
32g
holds for all E (1,..., L} that
(
VLd Na) (I+
N1 Ni)111 11 $ ma,u
Ld
and
Mmin (1+
No) ( ... ...(1+ Ld
8 Ld
Ni
Ms
Conclusion for arbitrary 0. The conclusion is a direct application of Lemma 9, with We No. The size of the admissible ball for is
I+ 8
VLd
m
exp
(-s²
4s d
4u >
exp(-222
-4u)
4
64
64
for d > 4, which concludes the proof.
Comparison with the bounds Zhang al. (2022). Theorem Zhang et al. (2022) gives an upper bound on the singular values of residual networks at initialization, and their Theorem 2 gives a lower bound on the norm of the activations. Comparing with our results, we note two important differences. First, their probability of failure grows quadratically with the depth, whereas independent of depth. This achieved by a more precise martingale argument making use of Doob's 's martingale inequality. Second, their lower bound incorrectly assumes that x² random variables sub-Gaussian (see equation (21) of their paper), while in fact they are only eibbexponential (Ghosh, 2021). Finally, their upper bound holds for the product
is
(T
N Ld
I
(1
[++YN, N,
0,)
Ld
any < & L, which could seem stronger than our result stated for j 1. fact, both statements are equivalent, because it is possible to deduce the statement for any j by combining the upper bound and the lower bound for The precise argument is given in the beginning of the proof of our Lemma 9.
41

---

B.9 Proof of Corollary 3
The beginning of the proof is very similar to the one of Corollary 2. Denoting W WR we have
Σ (VR VvR)(W)) ||3
s(w)² lim 8-0 w WE
sup
(56)
Σ [
W
with
- Ag := VaR - -VRt (W)
W W. (oo)) T W. ... +
W.PVR'
and
V VR (wod
2 X X
Σ
L
WT W WT ( W .............. + O
n1
At this point, the proofs diverge. We have, by subadditivity of the operator norm,
VR (woooa)l & 2A
Σ IW Willa|WW, Wa ... W + O(g)). k=1
Let us now briefly recall the outline of the proof of Theorem 4, which will be useful in bounding the quantity above. The proof shows the existence of C3 depending only on s such that, with high probability (which is exactly the probability in the statement of the Theorem), have for all t and & E {I,..., L} that
82 +t) (
82 and [W,(()) ... Wk+1(1))l2 & 4exp ( +
(W) ... (O)la & 4exp
as well as
2s² d
min (Wx(1) W.
>
44" exp (
C3)
(57)
Under this high-probabilli event, the proof of Theorem 4 shows convergence of the gradient flow to W WRI In particular, this means that W also verifies the bounds on the operator norm of the matrix products. We therefore obtain
8² |RR (Mipoa) lla & 2A Σ exp + (-+
+03))11 Will24 (
82 +Os)IPl1z O
1.
= cxp s2 + 22a2)|1pp11 Σ I - Wall2+
Moving on to bounding the Frobenius norm of Ak. we have
| = W WTrllel R (m)) W.T WT 0
WW W 1 lplla V R (Wprod)) 122l Will+
2 exp(2s + 4C
Σ IW W O
by bounding the three norms by the expressions given above. Then
| 13 < 28 exp(4s² 8C3))211p11
We Wall)) + +0(5)
28 exp(442 + (C
W - Wx + +
A=1
< e21eex2 + (88 LA? 1|ll
Σ
W - W212+ + +0(3).
Am
42

---

Thus, by (56),
S(W)² lim 2d exp(4s² + +88)) Ipli + (()) 8
Therefore
S(W) & 2 exp(2s² + 4C3)
(58)
To conclude, we need to upper bound ||l|2 by a constant times ||00 To this aim, we leverage the bound from the assumptions of Theorem 4 on the risk at initialization, show that |plla cannot be too far away from ||w" More precisely, by Lemma 8, since the covariance matrix X X is full rank,
1 ((Wpoo (0) w=' 112
(W((())) Rmin
n
1
(wprod (0) )= X (wprod(O) w²)
Al Wpod (0) w= 112.
Thus
(WV())) - Rmin
A Uppod (0) - w=112
Then, by the triangular inequality, || 2 Upodd (0)ll2 1/0 (0) =wwl
R!((())) - Rmiu
|[ (0) WI (0)pl12
X
min (Wz(0) ... (o)))llll / (L((W(O)) - Rmiin
A
exp (-
2s² - C3 lell2 VCaV Illlle.
d
by (57) and by the assumption of Theorem 4 on the risk at initialization. We now note that the value of C3 given by (40) as
16s²
C3 = 2 36 exp ( (- (492
2003)
C2
where O2 & d by (38). Thus
852
2s²
vCsv A
< VCs= = 2-18 exp(p22"
- 100's) < exp (- - -Os)
O2
d
Denoting
C" 1
2s² 0z VCa E (0,1),
4 exp
d
we therefore obtain that || 112 > C'llpll2. Therefore, by (58),
S(W) 2 (2s² 4Cs) LA || w* 122 t |p
Thus, by the second lower bound on Smi from Theorem 2, and since > 0,
S(W)
< < 2 + 44) X
Smin
which concludes the proof by setting
C== 2 exp(2s² + 4Ca)(C") 2 exp(22² + CC') 2+
C Experimental details, additional plots, and additional comments
Our code is available at https::/ htpps::///tthiin wtw.ght...ooo//eeeeeee Catuub..om/iieret htom///erreeMarin2//mmmapp Our framework for experiments JAX (Bradbury al., 2018). The experiments take around hours to run laptop CPU,
searsshap.eess.
43

---

Setup. We take = 50, d = 5, 10. The design matrix X is sampled from an isotropic Gaussian distribution. The target y is computed in two steps. First, we compute yo X Wree + Ç. where Winee and Ç are standard Gaussian vectors. Then, we compute wi as the optimal regressor of Yo on X. Finally, we let y = yo/ || and
w /1 This simplifies the expressions of our bounds by having w* of unit norm. All Gaussian random variables are independent.
Details of Figure We consider a Gaussian initialization of the weight matrices, where the scale of the initialization (x-axis of some the graphs) is the standard deviation of the entries. All weight matrices are d x d, except the last one which 1 x d. The square distance to the optimal regressor corresponds to ||Wppdd w" l The largest eigenvalue of the Hessian is computed by power iteration method, stopped after 20 iterations. In Figures la and Ib, the 95% confidence intervals are plotted. The number of gradient steps and number of independent repetitions depend on the learning rate, and are given below.
Learning rate
Number of steps
Number of repetitions
0.005
40, 000
20
0.02
10, 000
20
0.07
4, 000
20
0.1
4, 000
20
0.2
2, 000
80
For large values of the initialization scale, it may happen that the gradient descent diverges. Figure 3 shows the probability of divergence depending on the initialization scale and the learning rate.
0:32
0.37
06
0.30
0.35
0.40
0.00
Scale iilaiaatoo
Figure 3: Probability of divergence of gradient descent for a Gaussian initialization of the weight matrices, depending on the initialization scale and the learning rate.
When the probability of divergence equal to one, no point reported in Figure 1. When it is strictly between O and 1, the confidence intervals are computed over non non-diverging runs.
Figures Ic and Id show randomly-chosen run each. The plots subsampled 5 times for readability, due to the oscillations in Figure ld.
Residual initialization. We now consider the case of residual initialization in Section 5. Results are given in Figure 4. The scale of the initialization now corresponds to the hyperparameter in (2). The projection vector p IRd is random isotropic vector of unit norm, which does not change during training. For each learning rate, we use 4, 000 steps of gradient descent, and perform 20 independent repetitions. The plots similar the case of Gaussian initialization, apart from the fact that the sharpness at initialization is better conditioned.
As previously, for large values of the initialization scale, it may happen that the gradient descent diverges. Figure 5 shows the probability of divergence depending on the initialization scale and the learning rate.
Details of Figure 2. use 1, 000 steps of gradient descent, and perform 50 independent repetitions. We take 0.25.
The setup is the same as the residual initialization. For each learning rate,
44

---

10
Squard dateroo co reghtnal regresoo
10
10
Irabe
rat:: 0.000
0,2
10
10
10
16
0.005
10"19
rote: 0.02
rate: 0.07
0.00
0.25
0.50
0.75
1,20
1225
1.50
1.75
0.0
02
0.4
0.8
0.5
1.0
1/5
Scale insiiinnationn
Scale of Intiaization
(a) Squared distance of the trained network to the pirical risk minimizer, various learning rates and initialization scales. Training succeeds when the learn- ing rate is lower than critical value independent of the initialization scale.
(b) Sharpmess initialization and after training, for various learning rates and initialization scales. For
given learning rate y, the dashed lines represent the 2/n threshold. The dotted black line represents the lower bound given in Theorem 1.
607
10
Traring
Tranin
(c) Evolution during training of the squared distance to (d) Evolution during training of the squared distance the empirical risk minimizer and of sharpness, for r =
to the empirical risk minimizer and of sharpness, for
0.02 and an initialization scale of 0.5. The network = 0.1 and an initialization scale of 0.5. The network does not enter edge of stability.
enters edge of stability.
Figure 4: Training deep linear network on a univariate regression task with quadratic loss. The initialization residual initialization in Section 5.
E.2
rblc 8.07
2.
2.0
0.00
6.25
2.50
0.75
1.30
1.25
1.50
1.75
Figure 5: Probability of divergence of gradient descent for a residual initialization of the weight matrices, depending on the initialization scale and the learning rate.
Underdetermined regression and link to generalization. Although this is not our original moti- vation, we note that simple change our setting allows to make appear the connection between sharpness and generalization. To this aim, we consider the underdetermined case, where the number of data is lower than the dimension (while keeping the rest of the setup identical). Figure shows in this case a correlation between generalization and sharpness. This suggests that the tools developed the paper could be used in this case to understand the generalization performance of deep (linear) networks, and we leave this analysis for future work. We also qualitatively observe in Figure 6 similar connection between learning rate, initialization scale and sharpness in the case of full-rank data (Figure lb). We take here 15, d = 20, L = 5. The number of gradient steps and number of
45

---

independent repetitions depend on the learning rate, and are given below. Other technical details are as Figure
Learning rate
Number of steps
Number of repetitions
0.001
40, 000
100
0.004
10, 000
20
0.01
4, 000
20
31.52
Sharpress
3.16
Irisal
rate 0.001
rew 0.004
0.32
0.01
0.15
0.20
0.25
0.35
316
002
of intiaiztiion
(a) Sharpness at initialization and after training. various learning rates and initialization scales. We qual- itatively observe similar connection between learning rate, initialization scale and sharpness as in the case of full rank data matrix (Figure 1b of the paper).
(b) Link between generalization and sharpness. Each dot corresponds to one realization of the experiment (where the randomness comes from the random initial- ization of the neural network). The plot is shown in log-log scale. The line corresponds the linear regres- sion the log the generalization gap on the log of the sharpness after training (slope=0.42) + 0.01, in- tercept = 0.96 1 0.03).
Figure 6: Experiment with a deep linear network and degenerate data covariance matrix, where the number of data is less than the dimension d.
Non-linear MIPs. As first attempt to extend our results to non-linear networks, we consider the case of non-linear MIPs. The non-linearity is GELU (Hendrycks and Gimpel, 2016), smooth version of ReL.U, which we chose because smoothness is necessary in order to compute the sharpness. We qualitatively observe in Figure a similar connection between learning rate, initialization scale and sharpness as for deep linear neural networks (Figure lb). For large initialization, the sharpness after training plateaus at 2/1). in the linear case. For small initialization, the sharpness after training less that 2/1), and close to the bounds in the linear case (dotted black lines). For this experiment, consider noiseless data, meaning that you Wruee (see paragraph "Setup" above for notations). We perform 20 independent repetitions of each experiment. The number of gradient steps depends on the learning rate, and is given below. Other details are for Figure 1. Finally, we also performed the same experiment in the case of noisy data yo X Wimee Ç (no plot reported). We observed that the sharpness of the network reaches 2/1,, for every learning rate and initialization scale reported in Figure 7. We suspect that this is because the network (over)fits the noise in the data, resulting in a high sharpness.
Learning rate
Number of steps
0.005
160, 000
0.02
40, 000
0.07
16, 000
Comments on the connection between gradient flow and gradient descent. In this paper, we show that gradient flow from small-scale initialization is driven towards low-sharpness regions. This should imply that gradient flow and gradient descent up to a reasonably large learning rate should follow the same trajectory when starting from small-scale initialization, because they do not
46

---

101
Sharpness
10"
Intil zaton
10"
0.005
mete:
0.45
0.50
0.55
0.60
0.85
0.70
Scale infisizzttion
Figure 7: For a non-linear MLP, sharpness at initialization and after training, for various learning rates and initialization scales. For given learning rate 17, the dashed lines represent the 2/1 threshold. The dotted black lines represent the lower and upper bounds given in Theorem and Corollary 2 of the paper.
go in regions of high sharpness where the difference between gradient flow and gradient descent would become significant. This intuition supported by Figure 1b where we see that, for small initializations, the sharpness after training is independent of the learning rate. We leave further investigation of these questions for future work.
D Additional related work
Progressive sharpening. Cohen et al. (2021) show that the edge of stability phase is typically preceded by phase of progressive sharpening, where the sharpness steadily increases until reaching the value of 2/1.. Our setting of small-scale initialization presents example of such progressive sharpening (although we make no statement on the monotonicity of the increase in sharpness). Other works have proposed analyses of progressive sharpening. Wang et al. (2022) suggest that progressive sharpening is driven by the increase in norm of the output layer. MacDonald et al. (2023) assume from empirical evidence link between sharpness and the magnitude of the input-output Jacobian, and show that the latter has to be large for the loss to decrease. Finally, Agarwala et al. (2023) propose and analyze a simplified model with quadratic dependence in its parameters, which exhibits a progressive sharpening phenomenon.
Connection with deep matrix factorization. Regression with deep linear networks be as an instance of a matrix factorization problem. There is a well-established literature studying the implicit regularization of gradient descent for this class of problem (see, e.g., Gunasekar et al., 2017; Arora et al., 2019b; Li et al., 2021; Yun et al., 2021). However, this line of work study under-determined settings where there are an infinite number of factorizations reaching zero empirical risk, and study the implicit regularization in function space. On the contrary, we consider an over- determined setting where there is single optimal regressor, and study the regularization in parameter space.
47

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims regard the theoretical analysis sharpness of deep linear networks. The corresponding results are given in Sections 3, 4, and 5, and proven in Appendix B.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper presents work of theoretical nature, and explains clearly the setting and assumptions (e-g., linear activation function) in which the results are applicable.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
48

---

Answer:
[Yes]
Justification: The assumptions are stated in the main paper, and all proofs are given in Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The experimental details are given in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
49

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is given in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //niss... wttpcccppppppeeeeeeeccecccccceet gww///uiisee//ee weeeeee/ooeeeemeeeeeeeeeee wwwsssssiiiiyyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
The experimental details are given in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All plots have error bars (except the plots showing the trajectory of gradient descent along one run, for illustration).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
50

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiments are small-scale and run on a laptop CPU. The runtime is
given in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics attpp:://eerr/ http://wuuriss.ccppblbl/p// cc/public etth:ttthhiiiieeie ines?
Answer: [Yes]
Justification: The authors have reviewed the NeurlPS Code of Ethics, and attest that this paper conforms to the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This foundational research paper, not tied to particular applications, let alone deployments.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
51

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the papers for code we are using in Appendix C.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi twwode..ooo..... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
52

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
53


Reviews:
[{"review_id": "pSX4YhPDUP", "reviewer": "Reviewer_hdrG", "summary": "The authors show three new results for deep linear networks (DLN).  First, they show that any DLN that implements the optimal linear regressor must have a certain \"sharpness\".  This amounts to a lower bound on the largest eigenvalue of the Hessian matrix at that set of weights.  They then argue that the weights found by using gradient flow with two different types of initialization find minima that have a sharpness that is within a constant of this lower bound.  They interpret these results as an implicit regularization of gradient flow towards flat minima.", "questions": "Do these results add to our understanding of the generalization power of deep linear networks trained with gradient flow?", "limitations": "none", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "Results are novel.  They are also of at least abstract interest to the community of researches working on the theory of deep learning.  I also agree with their assertion that some of the intermediate results presented on the structure of weight matrices in DLNs post-training (e.g. approx rank 1 and aligned in small scale initialization case) might be of interest.", "weaknesses": "The paper kind of has a mixed message, and doesn't really make the connection to generalization power in a way that is intepretable.  Theorem 1 shows that the sharpness has to grow at a rate that is essentially linear in the number of layers.  But then they mention that prior work indicates that flat minima generalize better, which suggests that making the DLN deeper is going to hurt you in this regard.  The subjective interpretation of gradient flow going to flat minima is hard to digest when the authors just proved that there are no flat minima.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper kind of has a mixed message, and doesn't really make the connection to generalization power in a way that is intepretable. Theorem 1 shows that the sharpness has to grow at a rate that is essentially linear in the number of layers. But then they mention that prior work indicates that flat minima generalize better, which suggests that making the DLN deeper is going to hurt you in this regard. \n\nThe link between sharpness and generalization is very delicate, for example because reparameterizing the neural network changes the sharpness but not the generalization power. Your question on the link with generalization is shared with other reviewers and is addressed in the common rebuttal. Our results are mostly concerned with optimization dynamics and not so much with the link with generalization. In particular, we do not claim that our results indicate that increasing the depth of the neural networks leads to a worse generalization. Nevertheless, we agree that the current formulation of the introduction might be somewhat misleading in this regard, and we will reformulate to remove any confusion.\n\n> The subjective interpretation of gradient flow going to flat minima is hard to digest when the authors just proved that there are no flat minima.\n\nFor a given (fixed) architecture, our results show that gradient flow drives the network towards flat minima, since, among all minima, the one selected by gradient flow is “close” to the one with lowest sharpness. Here, “close” has an objective and rigourous meaning, which is that the ratio between the sharpness of the gradient flow solution and the lowest sharpness is architecture-independent and is given by precise formulas in Corollaries 3 and 4. This being said, as the reviewer rightfully indicates, the lowest sharpness itself depends on the architecture (through the depth). However, this should not be interpreted as the fact that there are no flat minima, but rather that the characteristics of the loss landscape (in this case, the sharpness of the flattest minima) are architecture-dependent, which is reasonable. We finally note that the fact that the sharpness of the flattest minima depends linearly on the depth was already shown in previous works, for instance in Mulayoff and Michaeli (2020).\n\n> Do these results add to our understanding of the generalization power of deep linear networks trained with gradient flow?\n\nThis question is shared with other reviewers and is addressed in the common 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": "", "extra_scores": {}}, {"review_id": "Kx46dUIOT5", "reviewer": "Reviewer_WC3N", "summary": "The paper considers a toy non-convex optimization problem, namely overdetermined univariate regression with a deep linear network. Their main contributions are:\n\n1) A lower bound on the sharpness of the minimizers of the empirical risk. In particular, if the step size is chosen too big, then gradient descent will fail to converge.\n\n2) They show that the sharpness of the minimizer found by gradient flow is at most a constant multiple of the above lower bound, for both small-scale and residual initialization. This constant does not depend on the width or depth, but only on the conditioning number of the data. This shows an implicit regularization towards flat minima (the empirical minimizers of the risk can have arbitrarily large sharpness).\n\nOn the technical side, they prove convergence of the GF and characterize the solution at convergence in both initialization regimes. Numerical simulations are provided to illustrate and substantiate their claims.", "questions": "Here, it is assumed that the data matrix is full rank. Is it not sufficient to assume that there exists a unique minimizer?", "limitations": "Yes", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The theoretical analysis is substantial. The results are novel and not straightforward. At the same time, they are easy to understand  and offer clear insights.\n\n- The qualitative picture obtained in this paper, with the interplay between step size, scale at initialization, and sharpness of the gradient descent solution, is convincing and surprisingly clear, given the complex non-convex problem.  In particular, I think it is interesting to have in a single model the behavior of sharpness, edge of stability and GD minimizer (even if only qualitatively).\n\n- The discussions are reasonably clear. The plots help a lot to understand the general message of the paper.", "weaknesses": "The paper considers a simple setting: deep linear network and underdetermined regime. This allows the authors to characterize interesting and non-trivial behavior. However, it is unclear how much these results can extend beyond this simple setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper considers a simple setting: deep linear network and underdetermined regime. This allows the authors to characterize interesting and non-trivial behavior. However, it is unclear how much these results can extend beyond this simple setting.\n\nThe question on the extension to more complex settings is shared with other reviewers and is addressed in the common rebuttal.\n\n> Here, it is assumed that the data matrix is full rank. Is it not sufficient to assume that there exists a unique minimizer?\n\nWe note that our assumption that the data covariance matrix $X^\\top X$ is full rank is in fact _equivalent_ to the uniqueness of the minimizer of the linear regression of $y$ on $X$.\n\nNevertheless, it is a very interesting question to study the case where this assumption is relaxed, that is, where $X^\\top X$ is not full rank. A part of our results which adapts reasonably easily to this relaxation is Theorem 1 (and 2). In this case, there exists an infinity of minimizers of the linear regression of $y$ on $X$, and $w^\\star$ should now be the minimizer with the smallest norm. Furthermore, the lowest eigenvalue $\\lambda$ of $X^\\top X$ is now equal to $0$ and should be replaced by  $a := (w^\\star / \\||w^\\star\\||) X^\\top X (w^\\star /  \\||w^\\star\\||)$. If $w^\\star$ is nonzero, then $a$ is also nonzero even though $X^\\top X$ is not full rank.\n\nWe also refer the reviewer to Figure 3a in the additional PDF, which considers the case $n < d$, implying in particular that the data covariance matrix $X^\\top X$ is not full rank. We qualitatively observe a similar connection between learning rate, initialization scale and sharpness as in the case of full-rank data (Figure 1b).\n\nWe will add these comments (and corresponding proof) in the next version of the paper. We leave the study of the extension of the other results in the paper to future work.", "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": "", "extra_scores": {}}, {"review_id": "xTgDuvwYjh", "reviewer": "Reviewer_hhnc", "summary": "This paper studies the implicit bias of gradient flow on deep linear networks for overdetermined univariate regression problems. A lower bound on the sharpness of any minimizer is first derived for the general data covariance matrix, then it is shown that gradient flow with small initialization finds a minimizer with a sharpness no larger than a constant times the lower bound, where the constant depends on the condition number of the data covariance matrix. A similar result is also derived for GF on linear residual networks.", "questions": "See Weaknesses", "limitations": "See Weaknesses", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Well-motivated problem. Good introduction. Clear writings. Theoretical results are carefully explained in the main paper.\n2. New convergence results for deep linear networks and linear residual networks, together with the upper bound on the sharpness.", "weaknesses": "1. **Tightness of Theorem 2**: In Mulayoff and Michaeli (2020), the lower bound on the sharpness is tight for whitened data: there exists a minimizer that achieves the lower bound. However, Theorem 2 in this paper only provides a lower bound. Is this lower bound improvable? For example, if the true lower bound has $\\Lambda$ instead of $\\lambda$, then the following results show that the sharpness minimizes found by GF is no larger than a constant times the lower bound, where the constant now does not depend on condition number.\n2. **Relevance of the problem setting**:  The sharpness is often considered to be affecting the generalization error of the trained network. However, this paper studies overdetermined linear regression, where every minimizer corresponds to the same input-output map $w^*$, thus having the same generalization error. Why does one care about studying the sharpness of the minimizer in this case, if sharpness does not affect generalization at all?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Tightness of Theorem 2: In Mulayoff and Michaeli (2020), the lower bound on the sharpness is tight for whitened data: there exists a minimizer that achieves the lower bound. However, Theorem 2 in this paper only provides a lower bound. Is this lower bound improvable? (...)\n\nWe agree with the reviewer that there is a gap between our lower bound $2L \\lambda \\||w^\\star\\||^{2-2/L}$ in Theorem 2 and the upper bound on the sharpness of the GF solution $8L \\Lambda \\||w^\\star\\||^{2-2/L}$ in Corollary 3, and that understanding this gap is a very interesting question. We give below a few comments, which we will add to the paper.\n\nFirst, an inspection of the proof for the lower bound shows that it can be improved by replacing $\\lambda$ by $a := (w^\\star / \\||w^\\star\\||) X^\\top X (w^\\star /  \\||w^\\star\\||)$. Note that $\\lambda \\leq a \\leq \\Lambda$, and the value of $a$ depends on the alignment between the optimal regressor $w^\\star$ and the eigenvectors of the data covariance matrix $X^\\top X$. For example, if $w^\\star$ is aligned with the eigenvector associated with the largest eigenvalue $\\Lambda$, then $a=\\Lambda$, and we get the improvement suggested by the reviewer. However, if $w^\\star$ is aligned with the eigenvector associated with the smallest eigenvalue $\\lambda$, then $a=\\lambda$, showing no improvement with respect to our current bound.\n\nSecond, moving on to the upper bound, it is possible to construct a minimizer with sharpness\n$2 \\||w^\\star\\||^{2-2/L} \\sqrt{L (\\Lambda^2 + (L-1) a^2)}$. While this quantity is not exactly matching the lower bound, it is close to the lower bound when $L$ is large. In particular, the ratio between both quantities goes to 1 when $L$ goes to infinity. This minimizer is constructed by taking all the weight matrices to be rank-one, with norm $\\||w^\\star\\||^{1/L}$, aligned first singular vectors, and the first right singular vector of $W_1$ is aligned with $w^\\star$. The proof of this fact is too long to be included in the present rebuttal, but will of course be added to the next version of the paper. It is quite similar to the proof of Corollary 3 of the paper.\n\nA question which remains is to rewrite the sharpness of the minimizer found by GF as a function of the quantity $a$. We believe that it is possible to do so, and to obtain a bound on this sharpness close to the upper bound given above. The main difficulty is to quantify the distance between the first right singular vector of $W_1$ and $w^\\star$. As explained below Corollary 1 in the paper, our proof shows that these two vectors have to be close, but quantifying their distance involves significant additional computations. We leave these for future work.\n\nFinally, we note that Figure 1b shows that the sharpness after training is less than the upper bound of Corollary 3, showing indeed some room for improvement.\n\n> Relevance of the problem setting: The sharpness is often considered to be affecting the generalization error of the trained network. However, this paper studies overdetermined linear regression (...). Why does one care about studying the sharpness of the minimizer in this case, if sharpness does not affect generalization at all?\n\nYour question on the link with generalization is shared with other reviewers and is addressed in the common rebuttal. In particular, our results are mostly concerned with optimization dynamics, and studying the sharpness in this setting allows for example to understand the maximal learning rate leading to stable training.\n\nLet us mention two other applications of sharpness to the understanding of the training dynamics. \n\nFirst, we show that GF from a small-scale initialization is driven towards low-sharpness regions. This should imply that GF and GD up to a reasonably large learning rate should follow the same trajectory when starting from small-scale initialization (because they do not go in regions of high sharpness where the difference between GF and GD would become significant). This is suggested by Figure 1b where we see that, for small initializations, the sharpness after training is independent of the learning rate. The fact that GF and GD follow the same trajectory is itself interesting because GF is often easier to analyze than GD, so it is nice to describe settings where the GF analysis provably matches the GD case.  We leave this study for future work, as well as the investigation of more complex cases where the minimizers implement different input-output functions.\n\nSecond, phenomena that have been of interest lately in understanding training dynamics of deep networks are the “progressive sharpening” and “edge of stability” [1-5]. As explained in the introduction, these phenomena are quite crucial to the training dynamics since they suggest an implicit regularization by large learning rates (see equation (1) in the paper). One of our initial motivations for this paper was to understand progressive sharpening for deep linear networks. Our results partially answer this question, in showing that a small-scale initialization leads to an increase of the sharpness during training (see lines 114-116). However, there are still many open questions on this topic (in particular the link with the phenomena observed for non-linear neural networks), which are left for future work.\n\nWe will add a more detailed discussion of these topics in the next version of the paper.\n\n[1] Agarwala, Pedregosa, Pennington. Second-order regression models exhibit progressive sharpening to the edge of stability. ICML 2023.\n\n[2] Cohen, Kaur, Li, Kolter, Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability, ICLR 2021.\n\n[3] Damian, Nichani, Lee. Self-stabilization: The implicit bias of gradient descent at the edge of stability. ICLR 2023. \n\n[4] MacDonald, Valmadre, Lucey. On progressive sharpening, flat minima and generalisation. 2023.\n\n[5] Wang, Li, Li. Analyzing sharpness along GD trajectory: Progressive sharpening and edge of stability. NeurIPS 2022.", "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": "", "extra_scores": {}}, {"review_id": "cK618UZhzn", "reviewer": "Reviewer_PPoT", "summary": "The paper explores the behavior of deep linear neural networks in the context of overdetermined univariate regression, which is the setting of a univariate response $y$, more samples than input dimensions, and nonsingular data covariance matrix. \n\nThe first result concerns the empirical risk minimizer (this is not equal to the gradient descent or gradient flow estimator)  and shows a lower bound on the sharpness of the ERM.\n\nThe next set of results show that gradient flow, a limit of gradient descent with a vanishing learning rate, implicitly regularizes the network towards flat minima, with sharpness close to a constant times the lower bound. This is proven for both small-scale and residual initializations.", "questions": "* Apologies for this very naive question, but what does $S(\\mathcal W)$, the largest eigenvalue of $\\mathcal W=(W_1,\\ldots,W_L)$ mean exactly? This $\\mathcal W$ is not itself a matrix. \n* Each of your results in Sections 3, 4, and 5 are based on existing proof techniques. Specifically, Section 3 proof is based on Mulayoff and Michaeli 2020, Section 4 on Ji and Telgarsky (2020), and Section 5 on Zou et al 2020, Sander et al 2022. I am not familiar with these papers. Do they attempt to prove similar things to this paper? Do you reach the same conclusions but with different proof techniques?", "limitations": "* There are some obvious limitations that are par for the course in papers attempting to prove theoretical results in deep learning. Namely, the architecture here is extremely oversimplified. The data covariance being full rank is also unrealistic. Finally, the main results are about gradient flow and discrete-time stochastic gradient descent is surely very different in nature.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The exposition is excellent. There are three main results, each given in its own section corresponding to Section 3, 4, and 5. \n* The setting described in Section 2 is mathematically clear\n* The first main result, Theorem 1, reaches a similar conclusion to previous work in Mulayoff and Michaeli (2020) but relaxes identity data covariance assumption and uses a supposedly simpler proof.\n* The next set of results characterize the gradient flow minimizers. This is indeed of independent interest, although the connection to sharpness is also interesting. \n* The sharpness papers I have come across seem to focus on sharpness induced by SGD. It's interesting that here the authors were able to demonstrate a preference for sharpness for deterministic gradient flow, albeit with specific initialization schemes.", "weaknesses": "* I missed a rigorous theoretical connection between the three main results and the behavior of the gradient descent minimizer. If the connection is only empirical in nature, it might be good to highlight this\n* The work employs, to my eyes at least, a rather limited definition of sharpness. Are the results really very particular to sharpness being the largest eigenvalue of the Hessian?\n* I'm missing some motivation for the two initialization schemes studied. Are they studied simply because they've been studied before and so the results here can borrow from existing work? \n* I find the title misleading. An architecture cannot have a preference for flat minima(?). It must be the architecture in conjunction with how it is learned. In this case, the main results concern very specific configurations of gradient flow. \n* The implication for learning rate design from this theoretical analysis seems rather weak to me. I mean that I cannot envision a practitioner implementing a learning rate design based on the results presented here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "* Rigorous connection between theoretical results and GD:\n\nWe agree that the connection between our results on gradient flow and the case of GD is not rigorously proven, and we will further emphasize this in the next version.\n\n* Other definitions of sharpness:\n\nWe agree that there are several definitions of sharpness, but believe that the largest eigenvalue of the Hessian is the most relevant quantity to study optimization dynamics. For example, in quadratic optimization, the maximal learning rate is given by 2 over this quantity. This quantity also appears to show convergence of GD in convex optimization. Our results are specific to this quantity, and we will mention this caveat.\n\n* Motivation for the initialization schemes:\n\nThe first scheme (small-scale initialization) is a classical Gaussian initialization, but with small variance. The scale of the initialization is known to play a key role in training of neural networks: the small-scale initialization corresponds to the “feature learning” regime where the weights change significantly during training, by opposition to the “lazy” regime (see e.g. [1]). This motivates the study of this regime.\n\n[1] On Lazy Training in Differentiable Programming, Chizat, Oyallon, Bach, NeurIPS 2019.\n\nThe second scheme (residual initialization) corresponds to a simplification of non-linear residual networks. More precisely, a simple non-linear residual architecture is given by\n\n$$h_{k+1} = h_k + \\sigma(N_k h_k),$$\n\nwhere the matrices $N_k$ are Gaussian at initialization. Removing the non-linearity, we get\n\n$$h_{k+1} = h_k + N_k h_k = (I + N_k) h_k = W_k h_k.$$\n\nWe recover (up to scaling factors) our residual initialization (see eq. (2) of the paper). We further note that this specific initialization scheme for linear networks has not been previously studied to our knowledge. The simpler but less realistic scheme which has been studied is the identity initialization $W_k = I$.\n\nWe will add these remarks in the next version.\n\n* Title:\n\nWe agree that the choice of optimization algorithm plays a key role. We had preferred brevity in the current title, but will consider a more precise title.\n\n* Implication for learning rate design:\n\nOur paper provides a step towards understanding training dynamics of neural networks. In particular, we explain the largest learning rate for training deep linear networks for regression tasks (see in particular Fig. 1 in the additional PDF). However, the goal of this work is not to make claims beyond this setting, and we leave extensions to more realistic settings for future work.\n\nWe nevertheless note that our dependence of learning rate on depth (namely, constant over depth) matches other papers that study scaling of neural networks [2, 3]. These analysis concern more complex cases (non-linear residual networks), but are limited to the beginning of training. Our analysis regards a simpler architecture but goes beyond, in describing the evolution of the weights throughout training, and showing convergence to a global minimizer.\n\n[2] Tensor Programs VI. Yang, Yu, Zhu, Hayou, ICLR 2024.\n\n[3] The Feature Speed Formula. Chizat, Netrapalli, 2023.\n\n* Definition of $S(\\mathcal{W})$:\n\nThanks for this question. Denoting the empirical risk as $R(\\mathcal{W})$ which depends on parameters $\\mathcal{W} \\in \\mathbb{R}^p$ (where we flatten all parameters in a single vector), we can consider the Hessian of $R$, which associates $\\mathcal{W}$ to a matrix $H(\\mathcal{W}) \\in \\mathbb{R}^{p \\times p}$. Then $S(\\mathcal{W})$ is the largest eigenvalue of $H(\\mathcal{W})$. This is explained in the paper in Section 3. Nevertheless, we agree that the notation might be misleading when first introduced, and we will make this clearer.\n\n* Link with the literature:\n\nWhile the paper emphasizes connections with the literature, there are very substantial differences between our paper and those mentioned by the reviewer, both in the proof techniques and in the goal of the papers.\n\nClosest to our approach is Mulayoff and Michaeli, which also study the sharpness of deep linear networks. As noted by the reviewer, we relax their assumption on the identity covariance matrix. Our proof technique is also different, and does not involve tools from tensor algebra. Furthermore, their study is concerned with describing the sharpness of the set of minimizers (the equivalent of our Theorem 1), while we go significantly beyond, in describing the training dynamics and the sharpness of the network after training, as well as providing experiments which connect the initialization scale, the learning rate and the sharpness.\n\nThe other papers mentioned by the reviewer study convergence of deep linear networks. The goal of the present paper is therefore very different, since it is centrally concerned with sharpness properties of the network.\n\nMore precisely, Ji and Telgarsky show convergence of deep linear networks for classification tasks. In the present paper, we consider a regression task, which introduces additional technicalities, because we cannot leverage the fact that the minimizer is at infinity, as is done by Ji and Telgarsky to simplify the analysis. Furthermore, many ideas in our paper are not present in theirs, such as the connection with sharpness, the experiments with large learning rates, and the study of residual networks.\n\nZou et al and Sander et al study convergence of deep linear residual networks starting from an identity initialization ($W_k = I$). We consider the more realistic residual initialization (see the answer on initialization schemes above), bringing significant additional technicalities in controlling the initialization randomness. Again, many ideas in our paper are not present in theirs, such as the connection with sharpness, the experiments with large learning rates, and the study of non-residual networks.\n\n* Limitations:\n\nThe question of extension to more complex settings is shared with other reviewers and is addressed in the common 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": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers,

We warmly thank you for your time and relevant comments, which will help us improve our work. If accepted, we will take into account your suggestions, making use of the additional page. 

Since several reviewers raised the relevant questions of the link with generalization and of the extension to more complex settings, we address these two questions below, and leave the answers to other questions in individual responses. 

Sincerely,

The authors

----

**Link with generalization:**

Sharpness analysis is quite intricate because **sharpness is linked both to generalization and optimization**. Generalization depends on the input-output function implemented by the trained neural network, while optimization depends on the loss landscape, and thus on the parameterization of the neural network.

**In this paper, we focus on the link with optimization dynamics** by choosing a setting (linear network, overdetermined linear regression) where we are able to disentangle both effects since all minimizers of the empirical risk implement the same function and thus have the same generalization error.

In this context, sharpness allows to **understand the optimization dynamics**. For example, leveraging our Theorem 1, we can **predict the largest learning rate for successful training**. This is mentioned in the paper (in the comments after Theorem 1). To better illustrate this fact, we refer to Figure 1 in the additional PDF, which shows the distance to the optimal regressor as a function of the learning rate, for various depths. We see a transition occurring when the learning rate crosses a threshold which depends on depth. For a given depth, the value for the threshold (dashed line) is equal to $2/S_{\min}$ where $S_{\min}$ is given in Theorem 1. We note that this gives a quantitative answer to the observations of [1], which shows the existence of a maximal architecture-dependent learning rate beyond which training fails.

Although this is not our original motivation, we also note that a simple change to our setting allows to make appear the connection between sharpness and generalization. To this aim, we consider the underdetermined case, where the number of data $n$ is lower than the dimension $d$ (while keeping the rest of the setup identical to the paper). We refer to Figure 3b in the additional PDF, which shows in this case a **correlation between generalization and sharpness**. This suggests that the tools developed in the paper could be used in this case to understand the generalization performance of deep (linear) networks, and we leave this analysis for future work.

All in all, the connection with generalization is an important question, which we will clarify by adding this discussion to the paper.

[1] The large learning rate phase of deep learning: the catapult mechanism, Lewkowycz, Bahri, Dyer, Sohl-Dickstein, Gur-Ari, 2020.

-----------

**Extension to more complex settings:**

Extending our results to more complex settings is an important question raised by the reviewers, and we performed **additional experiments** that we will add to the paper. We consider two additional settings: **non-linear MLP, and overdetermined regime for deep linear network** (when the number of data $n$ is lower than the dimension $d$). In both cases (see Figures 2 and 3a of the additional PDF), **we qualitatively observe a similar connection between learning rate, initialization scale and sharpness** as in Figure 1b of the paper. More precisely, we observe in all cases that the sharpness after training grows when increasing the scale of the initialization or when decreasing the learning rate. In the case of non-linear MLPs (Figure 2 of the additional PDF), we also see that for large initialization, the sharpness after training plateaus at 2/lr, as in the linear case. For small initialization, the sharpness after training is less that 2/lr, and is close to the bounds described in the paper in the linear case (dotted black lines).

Meta-review: The paper proposes an implicit bias of gradient flow for deep linear networks and overdetermined univariate regression that the sharpness of the minimizer is bounded.

The reviewers discussed the paper in detail, most of the concerns (regarding link with generalization, extension to general settings, and tightness of the bounds, etc.) were resolved during the discussion period and thus the reviewers agreed upon positive ratings. Overall I recommend accept.
Decision: Accept (poster)