Continuous vs. Discrete Optimization of Deep Neural Networks
Authors: Omer Elkabetz
Nadav Cohen
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Deep Learning
Non-Convex Optimization
Gradient Flow
Gradient Descent

Abstract: Existing analyses of optimization in deep learning are either continuous, focusing on (variants of) gradient flow, or discrete, directly treating (variants of) gradient descent.  Gradient flow is amenable to theoretical analysis, but is stylized and disregards computational efficiency.  The extent to which it represents gradient descent is an open question in the theory of deep learning.  The current paper studies this question.  Viewing gradient descent as an approximate numerical solution to the initial value problem of gradient flow, we find that the degree of approximation depends on the curvature around the gradient flow trajectory.  We then show that over deep neural networks with homogeneous activations, gradient flow trajectories enjoy favorable curvature, suggesting they are well approximated by gradient descent.  This finding allows us to translate an analysis of gradient flow over deep linear neural networks into a guarantee that gradient descent efficiently converges to global minimum almost surely under random initialization.  Experiments suggest that over simple deep neural networks, gradient descent with conventional step size is indeed close to gradient flow.  We hypothesize that the theory of gradient flows will unravel mysteries behind deep learning.

Continuous vs. Discrete Optimization of Deep Neural Networks
Omer Elkabetz Tel Aviv University omer. elkabetzdcs tau.ac.... i1
Nadav Cohen Tel Aviv University cohennadavecs. tau. ac.
Abstract
Existing analyses of optimization in deep learning are either continuous, focusing on (variants of) gradient flow, or discrete, directly treating (variants of) gradient descent. Gradient flow is amenable to theoretical analysis, but stylized and disregards computational efficiency. The extent to which it represents gradient descent is an open question in the theory of deep learning. The current paper studies this question. Viewing gradient descent an approximate numerical solution to the initial value problem of gradient flow, we find that the degree of approximation depends on the curvature around the gradient flow trajectory. We then show that over deep neural networks with homogeneous activations, gradient flow trajectories enjoy favorable curvature, suggesting they are well approximated by gradient descent. This finding allows us to translate an analysis of gradient flow over deep linear neural networks into guarantee that gradient descent efficiently converges global minimum almost surely under random initialization. Experiments suggest that over simple deep neural networks, gradient descent with conventional step size is indeed close to gradient flow. We hypothesize that the theory of gradient flows will unravel mysteries behind deep learning
Introduction
The success of deep neural networks is fueled by the mysterious properties of gradient- based optimization, namely, the ability of (variants of) gradient descent to minimize non-convex training objectives while exhibiting tendency towards solutions that generalize well. Vast efforts are being directed at mathematically analyzing this phenomenon. with existing results typically falling into one of two categories: continuous or discrete. Continuous analyses usually focus on gradient flow (or variants thereof), which corresponds to gradient descent (or variants thereof) with infinitesimally small step size. Compared their discrete (positive step size) counterparts, continuous settings are oftentimes far more amenable to theoretical analysis (e.g. they admit use of the theory of differential equations), but on the other hand are stylized, and disregard the critical aspect of computational efficiency (number of steps required for convergence). Works analyzing gradient flow over deep neural networks either accept the latter shortcomings (see for example [49 46) or attempt to reproduce
part of the results via completely separate analysis of gradient descent (cf. 30 18 5)) The extent to which gradient flow represents gradient descent is an open question in the theory deep learning.
The current paper formally studies the foregoing question. Viewing gradient descent as a numerical method for approximately solving the initial value problem corresponding to gradient flow, we turn to the literature on numerical analysis, and invoke fundamental theorem concerning the approximation error. The theorem implies that in general, the match between gradient descent and gradient flow is deter- mined by the curvature around gradient flow's 's trajectory. In particular, the "more convex" the trajectory, i.c. the larger the (possibly negative) minimal eigenvalue of the Hessian is around the trajectory, the bet-
'Due to lack of space, essential portions of this paper were deferred to supplementary material. We refer the reader [1] for a self-contained version the text.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

ter the match is guaranteed to be We show that when applied to deep neural networks (fully connected as well as convolutional) with homogeneous activations (e.g. linear, rectified linear or leaky rectified lin- ear), gradient flow emanating from near-zero initialization (as commonly employed in practice) follows trajectories are are "roughly convex," " in the sense that the minimal eigenvalue the Hessian along them is far greater than in arbitrary points in space, particularly towards convergence. This implies that over deep neural networks, gradient descent with moderately small step size may in fact be close to its contin- uous limit, i.e. to gradient flow. We exemplify an application of this finding by translating an analysis of gradient flow over deep linear neural networks into a convergence guarantee for gradient descent. The guarantee we obtain is, our knowledge, the first to ensure that conventional gradient- gradient-based algorithm optimizing a deep (three or more layer) neural network of fixed (data- ieattaaindeeeddenn size efficiently converge to global minimum almost surely under random dlata-independent near-zero initialization.
We corroborate our theoretical analysis through experiments with basic deep learning settings, which demonstrate that reducing the step size of gradient descent often leads to only slight changes in its trajectory. This confirms that, in basic settings, central aspects of deep neural network optimization may indeed be captured by gradient flow. Recent works (e.g. [8 33 53 suggest that by appropriately modifying gradient flow it is possible to account for advanced settings as well, including ones with momentum, stochasticity and large step size. Encouraged by these developments, we hypothesize that the vast bodies of knowledge on continuous dynamical systems, and gradient flow in particular (see, e.g.. (23 will pave way to unraveling mysteries behind deep learning.
1.1 Contributions
The main contributions of this work are: (i) we conduct the first formal study for the discrepancy between continuous and discrete optimization of deep neural networks; (ii) we demonstrate the use of generic mathematical machinery for translating a continuous non-convex convergence result into a discrete one: (iii) to our knowledge, the discrete result we obtain forms the first guarantee of random (data- independent) near-zero initialization almost surely leading a conventional gradient- -baee algorithm optimizing deep (three or more layer) neural network of fixed (data- (nttaainddeendntt) size efficiently con- verge to global minimum; (iv) the fundamental theorem (from numerical analysis) we emmpooy is seldom used in machine learning contexts and may be of independent interest; and (v) we provide empirical evi- dence suggesting that gradient descent over simple deep neural networks is often close to gradient flow.
2 Preliminaries: Numerical Solution of Initial Value Problems
Let deN. Given a function g: (0,00) x - 0. Rdd consider the initial value problem:
Rd (viewed as a time-dependent vector field) and point
((0)= 0
((t)=g(t,((t) fort
(1)
The following result - an extension of the well known Frcard-Lindelis Theorem - establishes that local Lipschitz continuity of g()) suffices for ensuring existence and uniqueness of solution ((-).
Theorem 1 EexistenceUuniqunness
Consider the initial value problem in Equation 1 and suppose
g(-) is locally Lipschitz, continuous. Then, there exists a solution O [0,4e) - TRo where either: te) or (ii) to < Co and lim, [[) || 0c. Moreover, the solution is unique in the sense that any other solution 0': [0,t2) + IRd must satisfy L'_ Ste and Vt E (0,t)): O'(()= = O(t.
Proof. The theorem is direct consequence of the results in Section 1.5 of 25
is typically the case that the solution to Equation M cannot be expressed in closed form, and a numerical approximation is sought after. Various numerical methods for approximately solving initial value problems have been developed over the years (see Chapter 12 in [55] for an introduction). The most basic one, Euler's 's method, is parameterized by a step size 17 > 0, and when applied to Equation follows the recursive scheme:
II addition to the minimal eigenvalue of the Hessian, local smoothness and Lipschitz constants also affect the guarantced match hetween gradient descent and gradient flow. However, the impact of these constants exponentially weaker than that the Hessian's 's minimal eigenvalue, For details see Theorem 3
"By data- lata-independence we mean that no assumptions training data are made beyond being subject to standard whitening and normalization procedures.
*We regard convergence as efficient if its computational complexity is polynomial in training set size and dimensions, as well as the desired level of accuracy.
'A minor subtlety is that in 25] the vector field g(:) defined over an open domain. To account for this requirement, simply extend g(-) to the domain (-00,00) x xtd by setting g(t.q) g(0.q) for all < 0, q qER..
2

---

(og1=,tt 0x)) for kork k0,1,,
(2)
where ty := kn and the initial point 0, is typically set to 0.. The motivation behind Euler's method is straightforward - a first order Taylor expansion of the exact solution ((-) around time &g
yields: 0((++1) )- - (tx + + R (tx) +1 = ((t)) + (/8(4. (fx)), therefore if O(tx) is well approximated by 2s. we may expect 0 to resemble ((t+11). The numerical solution produced
by Euler's s method may be viewed as a continuous polygonal curve:
0: (0(0,o0) RR
((0)=
0 =g),,00)) for EE k
The quality of the numerical solution then boils down to the distance between this curve and the exact solution, L.e. between (tt) and (tt fort 2 0. Many efforts have been made to derive tight bounds for this distance. We provide below a modern result known as "Fundamental Theorem."
Theorem 2 (Fundamental Theorem). Consider the initial value problem in Equation
and suppose g ) is continuously differentiable. Let 0: [0,t.) -2 be the solution to this problem (see Theorem and ler θ (0,20) +RR* R be a continuous polygonal curve (Equation (3) born from Euler's method (Equation ). For any /. E [0, [0,4e), q E RR4, denote by (1, E Rd.d the Jacobian of g(-) with respect its second argument at the point (t.q), and by Amac (t. q) the maximal eigenvalue )( Let :::Leet::00m.. (0.te) R be an integrable function satisfying: Xmaz (t.g((t.))) S m(t)
of (t
for aolall te [0.te) and q (()), where (((t),(()) stands for the line segment (in Rd between (t))
and (t). Let à: +R R2 be an integrable function that meets: Il ((((=)=g((,((t)))))
all LE (0,ta), where at ((+) represents the right derivative of (-) at time t. Then, all E (0,t.):
[10(1) (())l22 (e (10(0) ((0))l2+ - -M00- ((t)))t))
(4)
where p(tt)==(ú (mm()))dm ((t))tt'
Proof. The theorem is simply a restatement of Theorem 10.6 in (27).
3 Continuous vs. Discrete Optimization: Match Determined by Convexity
Let : RR, where E N, be a twice continuously differentiable function which we would like to minimize. Consider continuous optimization via gradient flow initialized at e TRd:
0(0)=0,
de 0())= - f(((((t) for 22..
4
(5)
This is special case of the initial value problem presented in Equation ( By Theorem I it admits a unique solution 0: [0,tz) -Rd where either: (i) te o0; or (ii) te <0 and lim: lim:)>.||((()] co. Numerically approximating this solution via Euler's method (Equation yields a discrete optimization algorithm which is no other than gradient descent:
θ 0 = V for 0
(6)
where 1) >> 0 is the chosen step size. We may thus invoke the Fundamental Theorem (Theorem 2 and obtain a bound on the distance between the trajectories of gradient flow and gradient descent.
Theorem 3. Consider the trajectory of gradient flow (solution to Equation (5)) 1))0) [0.t,)
and let (0, ta) and >> O. Define Di, =Uiero,ā Be (0()). where B. ((t) stands for the (closed) Euclidean ball of radius centered ((t). Let Br. >
be such that:
sup auPqeD,.IIV' [ (c)"lllllssetttte sppectvat S Bii and sup.ED, (1V/ S TE. Let m. [0,4] + be an integrable function satisfying: -Amin (V²(()) <m(() for all t E [O,ř] and q (0())), where Amin (())
stands for the minimal eigenvalue of f(q Then, the step size 17 > chosen for gradient descent (Equation satisfies:
e- )dt' 110 0
π< inf .E(0,f) Yi. mi de
the first [t/n] iterates of gradient descent will c-approximate the trajectory of gradient flow up to time i, i.e. we will huve (00=0((k))le S for all & [,/n]...L[//]]
Proof sketch (for complete proof see Subappendix J.2) The result follows from applying the Fundamental Thcorem (Theorem 2 with 8(-) fixed at Bt.
n
"This maximal eigenvalue known as the logarithmic norm of J(t.q) (cf. Section in 27 "The vector field in this case is time- ieme-independent (given by g(t,q) = (V for all t e (0,00). e.) Initial value problems of this type are known autonomous.
3

---

Theorem 3 gives sufficient condition -uper bound on step size (Equation for gradient descent to follow gradient flow up to given time The bound inversely proportional to smoothness and Lipschitz constants (3t,e and Yi, respectively). and more importantly depends exponentially on the integral of m(-) along the gradient flow trajectory, where m(.) corresponds to minus the minimal eigenvalue of the Hessian. The smaller the integral of m(.), i.e. the larger (less negative or more positive) the minimal eigenvalue of the Hessian around the trajectory is, the more relaxed the bound will be. That is, the "more convex" " the objective function is around the gradient flow trajectory, the better the match between gradient flow and gradient descent is guaranteed to be.
Corollary I below coarsely applies Theorem by fixing m(.) to minus the minimal eigenvalue of the Hessian across the entire space. If ml-) m (now a constant) is negative, i.e. the objective function f()) is strongly convex, the upper bound on the step size v) becomes constant, meaning independent of the time until which gradient descent is required to follow gradient flow. If m is equal to zero, i.e. f(() is non-strongly convex, the upper bound on 1) mildly decreases with i, namely it scales as 1/.. If on the other hand m is positive, meaning f() is non-convex, the bound on 1) shrinks to zero (becoming prohibitively restrictive) exponentially fast as grows. This suggests that as opposed to (strongly or non-strongly) convex objectives, over which gradient descent can easily be made to follow gradient flow, over non-convex objectives, in the worst case, gradient descent will immediately divert from gradient flow unless its step size is exponentially small. In Appendix B we present simple example of such a worst case scenario. In this worst case, the minimal eigenvalue of the Hessian is bounded below and away from zero around the gradient flow trajectory. A question is then whether there are non-convex objectives in which the minimal eigenvalue of the Hessian around gradient flow trajectories is large enough for them to he followed by gradient descent. We will that training losses of deep neural networks can meet this property.
Corollary 1. Assume that the objective function f()) is non-negative and 3-smooth with 33 >> 0F
Denote m == -in=-inf-ee qese a (V2 f())), where Xmin (V2 f())) stands for the minimal eigenvalue of
V2 fq)) Consider the trajectory of gradient flow (solution to Equation (5) 0: (:(0,t)) [0,te) and let
TE (0,te) and e >> O. Then, the step size nj 11> for gradient descent ( (Equation scatisfies:
c(E- 110 ((0))l))ll
if m <.0
(strong convexit))
c(e- ||0u o(e-110--00))])))1//
if m =
(non-strong convexity)
cle- 1--llll0000lllll T (e (1) -1)-m m
.if m > 0 (non-convexity)
where c:=
we will have 110
0 (kr) lla for ks (1,2,.... (1/2)....(//n]
Proof sketch (for complete proof see Subappendix [.3]. The result follows from applying Theorem
with - M.. - (23 Be and m(-)==))) =m.
Optimization of Deep Neural Networks is Roughly Convex
Section 3 has shown that the extent to which gradient descent matches gradient flow depends "how convex" the objective function is around the gradient flow trajectory. More precisely, the larger (less negative or more positive) the minimal eigenvalue of the Hessian is around this trajectory, the longer gradient descent (with given step size) is guaranteed to follow it In this section we establish that over training losses of deep neural networks (fully connected well as convolutional) with homogeneous activations (e.g. linear, rectified linear or leaky rectified linear), when emanating from near-zero initialization (as commonly employed in practice), trajectories of gradient flow are "roughly convex," in the sense that the minimal eigenvalue of the Hessian along them is far greater than in arbitrary points in space. particularly towards convergence. This finding suggests that when optimizing deep neural networks, gradient descent may closely resemble gradient flow. We demonstrate formal application of the finding in Scction translating an analysis of gradient flow over deep linear neural networks into a guarantee of efficient convergence (to global minimum) for gradient descent, which applies almost surely with respect a random near-zero initialization.
"Namely. 2 f(g) spectral S B for all q Rd. "Lemma in Appendix shows that in the current context (8-smoothness of the objective function f())) it necessarily holds that t. = 0o, i.e. the trajectory of gradient flow is defined over (0, For simplicity, the statement of the corollary does not rely on this fact.

---

4.1 Fully Connected Architectures
Consider the mappings realized by fully connected neural network with depth n E N22, input dimension do EN, hidden widths di di,d2....nnn11 E,, and output dimension d,, EN:
he: 2 + DRd
(8)
where: W E E R 1, ..j = 1.2..... m, are learned weight matrices; O with d: Di= -=jdddjj-
their arrangement as vector _ and σ : + IR is predetermined activation function that operates element-wise when applied a vector We assume that (-)) is (positively) homogeneous, meaning (cz)= ca (2) for all c2 0, E TR. This allows for linear (a(=)= =z). 2). as well as the commonly employed rectified linear (o))) = max max(x,0) activations.
(2.0}) ) and leaky rectified linear (a(z) = max max(2,022 (2,02] for some 0 <<)<
Let be a set of possible labels, and let S ((x with x; ER :/ E for -ori-113 1.2....... [S]. be sequence of labeled inputs. Given loss function R. xy -R convex and twice continuously differ- entiable in its first argument (common choices include square, logistic and exponential losses), we learn the weights of the neural network by minimizing its training loss average loss over elements of S:
1 |S
f: + RR f(0) = S
(xho(x))
and beloo show (for linear and non-linear activation functions, respectiely))) that although the minimal eigenvalue of f()(()) (Hessian of training loss) denoted Amin (V²(()) can in general be arbitrarily negative, along trajectories of gradient flow (which emanate from near-zero initialization) it is no less than moderately negative, approaching non-negativity towards convergence. In light of Section [] this suggests that over fully connected deep neural networks, gradient flow may lend itself to approximation by gradient descent- - a prospect we confirm (for a case with linear activation) in Section
Subsubsections 4.1.
4.1.1 Linear Activation
Assume that the activation function of the fully connected neural network (Fquation (8) is linear, iee. (z) and define the end-to-end matrix:
W Wn:1 = W,, W...W.-WWWW W1 E do.d.dd
(10)
The mappings realized by the network can then be written as ho(x) = W x,,,, and the training loss as (0) - ((W.), where
|S|
o: &: -R ((W)
((W.,.)))
(11)
S
convex and twice continuously differentiable. Lemmal below expresses V f(0) in this case.
Lemma 1. For any E Rdd. regard (() not only as (symmetric) matrix in R.d.d but also as a quadratic form V f()(() that intakes a tuple (AW1, AW2, AW,) E do x RRdz.d x ... x da-1, arranges it as a vector Af E Rdd (in correspondence with how weight matrices Wi,,W....,WW. are arranged to create Q), and returns A0 A Similarly, for any W E Rdd,dd regard (W) as quadratic form V² (-)[[ that intakes matrix in da and returns a scalar (non-negative since Φ(-) is convex). Then, 2 f() is given by:
V
AW.)= 1
(AW,)
(12)
+2TH (Vo(Wa)) T " "iskes W (W,,,,,-,
where W'' for any juI E m1, defined as W Wy-1--WW if SJ and as an identity matrix (with size to be inferred by context) otherwise.
Proof. See Subappendix J.4
The following proposition makes use of Lemma to show that (under mild conditions) Amin (V (()) can be arbitrarily negative, i.e. inf o Amin ( (V=(())) -00
Proposition 1. Assume that the network is deep (n2 > 3), and that the zero mapping is not global minimizer of the training loss (meaning V (0) +f 0) Then inf infegriAmin (V2 -o0.
The exact order by which the entries of Wi, ,,,, W,,..,, W., are placed in is insignificant for our purposes all that matters is that the same order be used throughout.
easily be extended to account for different activation functions at different hidden layers. We assume identical activation functions for simplicity of presentation.
11 "Our analysis
1Boo of these assumptions are necessary, in the sense that removing any of them (without imposing further assumptions) renders the proposition false Claim In Appendix(F
5

---

Proof. See Subappendix 0.5
Building on Lemmal
Lemma 2 below provides a lower bound on Amin (V2
Lemma 2. For any 0 Rd 13
Amin (V2 (V)) ( 1) (in VVo Frobenius
(n
max JC...2... 15 JEG
II
W sppctraal (13)
Proof. See Subappendix
Assuming the training loss is non-constant and the network is deep (n the infimum (over 0 E of the lower bound Equation (13) is minus infinity. In particular, if 0 not global minimizer (Vo(W,.)) m *0) 0) and at least n - 2 of its weight matrices W1, W2.... Wn, are non-zero, then by rescaling the latter it is possible to take the lower bound to minus infinity while keeping the end-to-end matrix W.. (and thus the input-output mapping (.).) and the training loss value f()) intact. However, gradient flow over fully connected neural networks (with homogeneous activations) initialized near zero is known to maintain balance between weight matrices- see [18] - and so along its trajectories the lower bound in Equation (13) takes a much tighter form. This is formalized in Proposition below..
)
Proposition 2. IfO E Rd resides on a trajectory of gradient flow (over f(-)) emanating from some point 0g Rdd with ||0,||2 S for some E (0.2ml then:
Amin (V2 f(0)) 2 - (n- - 1) v m (do, V (Waa) Flrobbenss [ II 1-2/1
spectral - cc 1-2n (14)
4n(x-1) /min d. V m: ) Frobening max 1, maax{ Ippootaal ]==1] 2(a-2)
where c:= [4m)=7m
Proof. See Subappendix(.77
Assume the network is deep (n 2 3), and consider a trajectory of gradient flow (over f-)) emanating from near-zero initialization. For every point on the trajectory, Proposition may be applied with
small leading the lower bound in Equation (14) to depend primarily on the sizes (norms) of the end-to-end matrix Wn.1 and the gradient of the loss with respect to it, i.e. Ve(Wn.) (see Equations (10) and (II). In the course of optimization, Wn:1 is initially small, and (since the loss ((0)= ((W):) is monotonically non-increasing) remains confined to sublevel sets of (6.) (which is convex) thereafter. V)( on the other hand tends to zero upon convergence to global minimum. We conclude that the lower bound on Amin (0)) in Equation (I4) starts off slightly negative, and approaches non-negativity (if and) the trajectory converges to global minimum. In light of Section[3] this implies that the gradient flow trajectory may lend itself to approximation by gradient descent. Indeed, the results of the current Subsubsection are used in Section 5 to establish proximity between gradient flow and gradient descent, thereby translating an analysis of gradient flow into a guarantee of efficient convergence (to global minimum) for gradient descent.
4.1.2 Non-Linear Activation
Due to lack of space. we defer our analysis for fully connected neural networks with non-linear activation to Appendix[[] This amalysis is similar in spirit to the one in Subsubsection(4.11 I.rttionn4...Irrratinin Ireating linear activation. particular, it makes use of the fact that gradient flow initialized near zero maintains balance between weight matrices -ariiiesss-ff. cf. [18]. A key difference brought forth by non-linear activation is that the training loss f() (Equation (9) is no longer differentiable. We circumvent this challenge by excluding from the analysis points of non- differentiaaiiityy which form a negligible (closed and zero measure) set.
4.2 Convolutional Architectures
We account for convolutional neural networks by allowing for weight sharing and sparsity patterns to be imposed on the layers of the fully connected model analyzed in Subsection 4. Namely, we consider the exact same mappings as in Equation (8) but now, rather than being learned directly, the matrices W; E Rdy,dy-,, j = 1,2,... .......ii .n, are determined by learned weight vectors w, E R with d' EN =1, such that each entry of W, is either fixed at zero or connected to predetermined coordinate of w, (with no repetition of coordinates within the same row). The weight setting 0 e Rd then simply a concatenation of the weight vectors Wi, W...,......W and its dimension is accordingly d= - ===1d d. Our analysis for this model (which includes convolutional neural networks as a special case) is essentially the same as that presented for fully connected neural networks with non-linear activation (Subsubsection 4.1.2). In partieular, we use the fact that even with weight sharing and sparsity patterns imposed on the layers of a fully connected neural network (with homogeneous activation), when initialized near zero, gradient flow over the network maintains balance between weights of different layers- - cf. [18]. For the complete analysis see Appendix D
Note that by convention, an empty product (i.e. product the elements of the empty set) is equal to one.

---

5 Continuous Proof of Discrete Convergence for Deep Linear Neural Networks
Section 3 invoked the Fundamental Theorem for numerical solution of initial value problems (The- 2remm to show that, in general, the extent to which gradient descent provably matches gradient flow is determined by how large (less negative more positive) the minimal eigenvalue of the Hessian is around the gradient flow trajectory. Section established that for training losses of deep neural networks, along trajectories of gradient flow emanating from near- zecor initialization (as commonly em- ployed in practice), the minimal eigenvalue of the Hessian is far greater than in arbitrary points in space, particularly towards convergence. In this section combine the two findings, translating an analysis of gradient flow over deep linear neural networks into a convergence guarantee for gradient descent. The guarantee we obtain is, our knowledge, the first to ensure that conventional gradient-basee algorithm optimizing a deep (three or more layer) neural network of fixed (data-independene? size efficiently converge to global minimum almost surely under random (data-independent) near-zero initialization.
Deep linear neural networks- - -fully connected neural networks with linear activation (see Subsec- 4.1 perhaps the most common subject of theoretical study in the context of optimization in deep learning. Though trivial from an expressiveness point of view (realize only linear input-output map- pings), they induce highly non-convex training losses, giving rise to highly non-trivial phenomena under sudient-basedd optimization. In recent years, various results concerning gradient flow over deep linear neural networks have been proven, most notably for the case of balanced initialization (see for exam- ple [49 34 6 46). Under the notations of Subsection [.] (in particular with Wi, Wi,,W..... W.....,; W,,,, standing for network weight matrices), balanced initialization means that when optimization commences:
Wf 3 1 for j=,,2.....
(15)
The condition holds approximately with any near-zero initialization, and exactly when the following procedure (adaptation of Procedure I in (5]) is employed.
Procedure 1 (random balanced initialization), With a distribution P over d., duy-by-g matrices rank at ). initialize W, E ER 1,,,...,,, via following steps: (i) sample A A~ P: (ii) take singular value decomposition A A-UEVT where U E min/do,dd and V E min have orthonormal columns, and Σ mi of A; and (iii) set W,, ~ ~U>'/" "/////WWn111 ~ Wn ~ W...,W ~ 1//m W1 ~ > 1/" where stands for equality up to zero-valued padding.
most min {
(dg. d.,]; J.min (do. is diagonal and holds the singular values
1//1
Compared to gradient flow, little is known about gradient descent when comes to optimization of deep (three more layer) linear neural networks. Indeed, there are relatively few results along this line (cf. ( 30 5l), and these are typically highly specific, built upon technical proofs that are difficult to generalize. Being able to obtain results via translation of gradient flow analyses is thus of prime interest.
We focus in this section on deep 1+ linear neural networks trained for scalar regression per least-squares criterion. In the context of Subsection 4.1 this means that the activation function a-)) is linear (a(z) = 2). the output dimension dn is one, and the loss function E(-) is the square loss (i.e. y = R and ((ū.v) [0 - ))) We assume that training inputs are whitened, i.c. have been transformed such that their empirical (uncentered) covariance matrix Age == | _ X;X, E Rd is equal to identity. A standard calculation (see Appendix Gb shows that in this case the function o(-) defined by Equation (II) becomes o(W)= = 1|l Ayyz Frobenius +c, where Aga := [ST
(8)
1 Σ 2= yiX; E 1.d
the empirical (uncentered) cross-covariance matrix between training labels and inputs, and ce IR is a constant (independent of W). We may thus write the training loss f-) (Equation (9) as:
1
((0)=,110 [I 11:W--AAzl1-e Al +c=
2 | 1iWa1-a0 - F + min-minnggeeee f(q),
(16)
where WT:1 IR 1,kk is the network's 's end-to-end matrix (Equation (10)).
We disregard the degenerate case where Age =0, i.e. where the zero mapping attains the global minimum, and assume that training labels are normalized (jointly scaled) such that Aye has unit length (|lAye Frobenius = 1).
Proposition Jeblw beloo analyzes gradient flow over the training loss in Equation (6)). Relying on known characterization for the dynamics of the end-to-end matrix (cf. 44), it establishes convergence to global minimum. Moreover, harnessing the results of Section 4 it derives a lower bound on (the integral of) the minimal eigenvalue of the Hessian around the gradient flow trajectory.
14 Our results apply to shallow (two layer) networks as well. We highlight the deep (three or more layer) setting
it is far less understood (ef. (5)) and arguably more central to deep learning.
7

---

Proposition 3. Consider minimization of the training loss f(-) in Equation (16 via gradient flow (Equation )5) starting from initial point 0₂ E Red that meets the balancedness condition (Equatiinn (15)). Denote by W 11 the initial value of the end-to-end matrix (Equation (OO). and suppose that [Wn:1.a Frobennuss E (0, (initialization is small but non-zero). Assume that W 11 is not antiparallel to Ayn, i.e. v Tr W n=11,)/ /IIAAa Frobenius [Wn1., n:1.s . Frobenius) + Then, the trajectory of gradient flow defined over infinite time, and with 0: (0,00) +R. representing this trajectory, for any E>> 0, the following time i satisfies ((O(t)) menggeeg (q) SE:
2m
max
1=
15mmax (1
i=
In
(17)
Probenias
(1.(1.
Moreover, under the notations of Theorem 3 for any t 0 and E (0. 2nd with corresponding Dr.
(e-neighborhood of gradient flow trajectory up to time t), we have the smoothness and Lipschitz constants B.. 16n and Tts =6 / respectively. and the following (upper) bound on the integral of (minus) the minimal eigenvalue of the Hessian:
S. m(tt mtt))dt's
[max (
15m
1.2 [+v1)
1-2 1- In
( n² (2(22max 1-v 11 1))0))--1 11
(18)
aa Frudenias
W Probenius
where the function m: [0,0] > R is non-negative
Proof. See Subappendix J.8
Plugging the gradient flow results of Proposition iinto the generic Theorem 3 Itranslates them to the following convergence guarantee for gradient descent.
Theorem 4. Assume the same conditions as in Proposition 3 but with minimization via gradient
descent (Equation (6)) instead of gradient flow 15 Then, with 0, .,.00........... representing the iterates of
gradient descent, W 11:10 standing for the end and matrix (Equation (10) of the initial point O, and
V:= -T(TTTATTT (n:1.))) (II (Aggglll Probenius I n:100 grollrroennnis
Probenius) for any ē 0, if step size n meets:
15mmax (1.
1-1)
-2
al Prahentnn (1,) S n17//277--1 (max Itv0)
In JW a Probeniu win [T,]
1t0
E
fll 17/2 (poly(
(19)
63/2
( itt))
it holds that f(0x)) min qeR f(g) Se where:
2n (maxf 1:2 1==1)"
15mmax 1.
n "[potul (1+2) (n(
k
In
14
+1
+1 E
(20)
Wnll,oll Probeniou?)
W o.ll Frobenius min [1,7]
Fl
Proof. See Subappendix J.9
Remark 1. Theorem our generic toolfor translating analyses between gradient flow and gradient descent allows for the two to be initialized differently. Accordingly, the convergence guarantee Theorem may be extended to account for initialization which not perfectly balanced, i.e. which satisfies Equation [5] only approximately. For details see Appendix
Remark 2. The convergence guarantee of Theorem f requires a number of iterates that scales exponentially with network depth (n). 157) hus proven that under mild conditions, for deep linear neural network whose input, hidden and output dimensions are all equal to one (i.e., in our notations, dg d1 dr, = 1), such exponential dependence on depth is unavoidable. We defer to future work the question of whether this also holds in the context of Theorem
Combining Theorem 4 with random balanced initialization (Procedure D yields what is, to our knowledge, the first guarantee of random data-indeppedeet) near-zero initialization almost surely leading a conventional gradient- based algorithm optimizing a deep (three or more layer) neural network of fixed (data- independent) size to efficiently converge to global minimum.
Corollary 2. Consider minimization of the training loss f(-) in Equation (16) via gradient descent (Equation (6 emanating from random balanced initialization (Procedure [ whose underlying distribution P is continuous and satisfies PIA~P [IIA| | Frobenius S 0.2] = 1. Assume do (network imput dimension) is greater than one, and let W 11110 and v be as defined in Theorem Then, almost surely with respect to (i.e. with probability one over) initialization, for any ē ē>0 0, if the step size n meets Equation (19), the value of f-) after k iterates will be within from global minimum, where ic is given by Equation (2))
Proof. See Subappendix J.10
The conditions Og in Proposition 3 are satistied by the initialization of gradient descent, Lee. by Oo.
8

---

Fully Connected, Linear Activation
Fully Connected, Rectified Linear Activation
3.5
3,0
3.0
3.0
n/2
2.5-
ny2
2.5
Training Loss
2.5-
+
0//5
Training Loss
2.0
ny/10
Distanc
Distani
2.0
+--
n/20
2.5
% from in?
3.5
-
1u20
- Rb from Ini
1.5-
1.0
1.0
5o from 76/5
1.0
1.0-
- d6 from 02/
0.3
6,5-
from 7u/20
0.5-
06 from gu20
0w10
0.0
0.0
0.0
2500
5000
10000
2500 5000
7500 10000
2500 Iterations
5000
7500
10000
2500 5000 7500 10000
no Iterations
Iterations
No Iterations
Figure 1: Over deep fully connected neural networks, trajectories of gradient descent with conventional step size barely change when step size is reduced, suggesting they close to the continuous limit, Le. trajectories of gradient flow. Presented results were obtained on fully connected neural networks as analyzed Subsection[4.] trained to classify MNIST handwritten digits (28-by-25 grayscale images, each labeled as an integer between O and 9 10-0 of. (35)). Networks had depth n=3, input dimension 70=784 784 (corresponding to 28 28-22-775 784 pixels), hidden widths d5= and output dimension dy=10 10 (corresponding to ten possible labels). Training was based on gradient descent applied to cross-entropy loss with no regularization, starting from near-zero point drawn from Xavier distribution (ef. (24). Separately on each network, we compared runs differing only in step size v/. Specifically, with =0.000 (standard choice of step size) and r ranging over (2,5,00,20) we compared, in terms of training loss value and location in weight space, every iteration of run using 1/ to every r'th iteration of run in which /r. Left pair of plots reports results obtained on network with linear activation (z() = 2). while right pair corresponds a network with rectified linear activation (a (2) = max 22,0)). each pair, left plot displays training loss values, and right one shows (Euclidcan) distances in weight space, namely, distance between initialization and run with 1o alongside distances between run with 77 and runs having n= for different values of r. Horizontal axes represent time in units of 1- iterations (meaning each time unit corresponds to iterations of run with 7=n)/r). Notice that the drift hetween runs with different step sizes minor compared the distance traveled. For further implementation details, and results of similar experiments on convolutional neural networks, see Appendix
Experiments
In this section we corroborate our theory by presenting experiments suggesting that over simple deep neural networks, gradient descent with conventional step size is indeed close the continuous limit, i.e. to gradient flow. Our experimental protocol is simple on several deep neural networks classifying MNIST handwritten digits ( (B5)), we compare runs of gradient descent differing only in the step size n. Specifically, separately on each evaluated network, with 7/0 = 0.001 (standard choice of step size) and ranging over [2,5,10, 10,20, we compare, in terms of training loss value and location in weight space, every iteration of a run using 1/ to every r 'tth iteration of run in which n= rreports the results obtained on fully connected neural networks (as analyzed in (ubssection/411p with both linear and non-linear activation. As can be seen, reducing the step size 1 leads to only slight changes, suggesting that the trajectory of gradient descent with 17= is already close to the continuous limit. Similar results obtained on convolutional neural networks (see Subsection for corresponding analysis) are reported by Figure 3 in Subappendix I.I
Our experimental findings suggest that in practice, proximity between gradient descent and gradient flow may take place even when the step size of gradient descent is larger than permitted by current theory. Indeed, the theoretical machinery developed in this paper brings forth upper bounds on step size that guarantee proximity, and while such upper bounds can be asymptotically tight under worst case conditions (see Appendix B). they are by no means tight in every given scenario, and therefore larger step sizes may also admit proximity. For illustration, a step size of. which in our experiments was seemingly sufficient for ensuring proximity, is many orders of magnitude greater than the upper bound on step size required by Theorem (Equation (9)).
7 Related Work
Theoretical study of gradient- based optimization in deep learning is an extremely active area of research. While far too wide to fully cover here, we note that analyses in this area can broadly be categorized as continuous (see for example 49
57 46 31
60
62
2 16 66 28 There are works comprising analyses of both types 12 ) but with these developed separately, wherein continuous proofs typically serve as inspiration for discrete ones (which are often far more technical and brittle).
or discrete (e.g. 9 26
17
(ef. 118 30 5

---

When relating continuous and discrete optimization, the algorithms at play are most commonly gradient flow and gradient descent. There are however works that draw analogies between other algorithms, replacing gradient flow on the continuous end and/or gradient descent on the discrete one (see, e.g., [54] 58
33 53 The literature includes works which, similarly to the current paper, provide formal results concerning the accumulated (non-local) discrepancy between continuous and discrete optimization (cf. [50
50 [2
43) However, such works typically focus on simple ob- jective functions (for example convex quadratic), whereas we center on (non-convex and non-smooth) training losses of deep neural networks. Several recent works (e.g. SS 33 44) ) also considered contimu- ous vs. discrete optimization of deep neural networks, but they did not provide formal results concerning the accumulated discrepancy. We are not aware of any study (prior to the current) formally quantifying the accumulated discrepancy between continuous and discrete optimization of deep neural networks.
With regards to the convergence guarantee we obtain in Section translation of gradient flow analy- sis to descen) - Tae Corollary 2 releeannt results are those that establish efficient convergenc to global minimum for a conventional (discrete) gradient- based algorithm optimizing deep (three or more layer) neural network. Existing results meeting this criterion either: (i) apply to neural networks (linear or non-linear) whose size depends on the data (i.e. is not data-independen predominantly in impractical fashion (cf. [65] 17 2 19
64 42 ); or (ii) apply to linear neural
networks of fixed (data-independemt size, similarly to our guarantee. Results of type (ii) often treat the residual setting, which boils down to (possibly scaled) identity initialization, perhaps with input and/or output layers initialized differently (see for example [9] 66)). Exceptions include [5]. [16] and (28]. [3] allows for random balanced initialization, as we do. Its results account for networks with multi- dimensional output, and require a number of iterates polynomial in network depth. Our guarantee on the other hand is limited networks with one-dimensional output, and calls for number of iterates scaling exponentially with network depth. However, while [5] demands that initialization be sufficiently close to global minimum, thereby excluding the possibility of saddle points being encountered, our guarantee holds almost surely (i.e. with probability one) under random (data-independent) near-zero initialization. The fact that we account for evasion of saddle points (in particular that at the origin, which is non-stric when network depth is three or more) may be the source of the gap in number of iterates see Remark 2 As for the results of [16] and (28), these also hold with high probability under random initialization. but they require network size to grow towards infinity in order for the probability to approach one.
8 Discussion
Our work puts forth a potential explanation to a puzzling phenomenon in deep learning, namely, the effect of weight decay (L2 regularization). While traditionally viewed as a regularizer, it is known (ef. 322) ) that in deep learning, weight decay can assist in minimizing the training loss. In light of
our findings, a possible reason for this is that weight decay translates to adding a positive constant to Hessian eigenvalues, thereby bringing gradient descent closer to gradient flow, which often enjoys favorable convergence properties. Theoretical and/or empirical investigation of this prospect is a potential avenue for future work.
Emerging evidence (ef. [38 36 29 suggests that for (variants of) gradient descent optimizing deep neural networks, large step size is often beneficial in terms of generalization (i.e. in terms of test accuracy). While the large step size regime is not necessarily captured by standard (variants of) gradient flow (see [4), (,),, recent works (e.g. B 33 (33) argue that it is captured by certain modified version of (variants of) gradient flow. Formally quantifying the discrepancy between gradient descent with large step size and such modified version of gradient flow is a promising direction for future research.
The demonstration we provided for translation of a gradient flow analysis to gradient descent (Section 5 culminated in a convergence guarantee, but in fact entails much more information. Namely, since the translated gradient flow analysis includes a careful trajectory characterization, not only do we know that gradient descent converges to global minimum (and how fast that happens), but we also have access information about the trajectory it takes to get there. This allows, for example, shedding light on how saddle points (non-strict ones in particula [t are evaded. A nascent belief (cf. 5 6
())) is that understanding the trajectories of gradient descent is key to unraveling mysteries behind optimization and generalization (implicit regularization) in deep learning. The machinery developed in the current paper may contribute to this understanding, by translating results from the vast bodies of literature on continuous dynamical systems.
16 A saddle point is said to be non-strict if its Hessian has no negative eigenvalues. Saddle points that are non-strict are generally regarded more difficult evade cf (5).
10

---

Acknowledgments and Disclosure of Funding
We thank Sanjeev Arora, Noah Golowich, Wei Hu, Michael Lee, Zhiyuan Li, Kaifeng Lyu, Govind Menon and Zsolt Veraszto for helpful discussions. This work was supported by Google Research Scholar Award, Google Research Gift, the Yandex Initiative in Machine Learning, the Israel Science Foundation (grant 1780/21), Len Blavatnik and the Blavatnik Family Foundation, and Amnon and Anat Shashua.
References
[1] Madhu Advani, Andrew M Saxe, and Haim Sompolinsky, High-dimensional dynamics of generalization error in neural networks. Neural Networks, 132:428 446, 2020.
[2] Zeyuan All, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pages 242-252. PMLR, MLR, 2019.
[3] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2008.
[4] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameteriizaion. In International Conference Machine Learning, pages 244-253, 2018
[5] Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent deep linear neural networks. International Conference on Learning Representations, 2019.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pages 7413-7424, 2019.
[7] Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake Woodworth, Nathan Srebro, Amir Globerson, and Daniel Soudry. On the implicit bias of initialization shape: Beyond infinitesimal mirror descent. arXiv preprint arXiv:2102.0977 09769, 2021.
[8] David GT Barrett and Benoit Dherin. Implicit gradicnt regularization. Internationa Conference on Learning Representations, 2021.
[9] Peter Bartlett, Dave Helmbold, and Phil Long. Gradient descent with identity initialization efficiently learns positive definite linear transformations. In International Conference Machine Learming, pages 520 529. 2018.
[10] Jonathan Borwein and Adrian Lewis. Convex analysis and nonlinear optimization: theory and examples. Springer Science & Business Media, 2010.
[11] Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pages 1305-1338. PMLR. 2020.
[12] Hung-Hap Hsu Chou, Carsten Gicshoff, Johannes Maly, and Holger Rauhut. Gradient descent for deep matrix factorization: Dynamics and implicit bias towards low rank. arXiv preprint arXiv: 13772, 2020.
[13] Frank H Clarke. Generalized gradients and applications. Transactions of the American Mathematical Society, 205:247-262, 1975.
[14] Jeremy Cohen, Simran Kaur, Yuanzhi Li, Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs the edge of stability. In International Conference Learning Representations, 2021.
[15] Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason Lee. Stochastic subgradient method converges on tame functions. Foundations of computational mathematics, 10(1):119-154, 2020.
[16] Simon Du and Wei Hu. Width provably matters optimization for deep linear neural networks. In International Conference on Machine Learning, pages 1655-16644 1664, PMLR, 2019.
[17] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai, Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685. PMLR, 2019.
[18] Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In Advances in Neural Information Processing Systems, pages 384-395, 2018.

---

[19] Weinan E, Chao Ma. Qingean Wang, and Lei Wu. Analysis of the gradient descent algorithm for deep neural network model with skip-connections. arXiv preprint (rXiv:1904.055633 2019.
[20] Armin Eftekhari. Training linear neural networks: Non-local convergence and complexity results. In International Conference on Machine Learning, pages 2836-2847. PMIR, 2020.
[21] Omer Elkabctz and Nadav Cohen. Continuous vs. discrete optimization of deep neural networks. arXiv preprint arXiv:2107.06660 2021.
[22] Guilherme Franca, Daniel Robinson, and Rene Vidal. Admm and accelerated admm continuous dynamical systems. International Conference on Machine Learning, pages 1559-1567. PMLR, 2018
[23] Paul Glendinning. Stability, instability and chaos: an introduction the theory of nonlinear differential equations. Cambridge university press, 1994.
[24] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedffrward neural networks. In Proceedings the the thirteenth international conference on artificial intelligence and statistics, pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
[25] Christopher P Grant. Theory of ordinary differential equations. Brigham Young University, 2014.
[26] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems, 31:9461-9477 2018. 2018.
[27] Emst Hairer, Syvert P Nørsett, and Gerhard Wanner. Solving ordinary differential equations i. nonstiff' problems, volume & of, 1993.
[28] Wei Hu, Lechao Xiao, and Jeffrey Pennington. Provable benefit of orthogonal initialization in optimizing deep linear networks. In International Conference on Learning Representations, 2020.
[29] Stanislaw Jastrzebski, Maciej Szymczak, Stanislav Fort, Devansh Arpit, Jacek Tahor, Kyunghyun Cho, and Krzysztof Geras. The break-even point optimization trajectories of deep neural networks. International Conference on Learning Represeniations, 2020.
[30] Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. International Conference on Learning Representations, 2019.
[31] Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems, 2020.
[32] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25:1097- 1105, 2012.
[33] Daniel Kunin, Javier Ergastuuy-Bena Surya Ganguli, Daniel LK Yamins. and Hidenori Tanaka. Neural mechanics: Symmetry and broken conservation laws in deep learning dynamics. International Conference on Learning Representations, 2021.
[34] Andrew K Lampinen and Surya Ganguli. An analytic theory generalization dynamics and transfer learning in deep linear networks. International Conference on Learning Representations, 2019.
[35] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun, com/exdb/nnist/, 1998.
[36] Aitor Lewkowyez, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003. 022000 2020.
[37] Qianxiao Li, Cheng Tai, and E Weinan. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference on Machine Learning, pages 2101-2110 10. PMLR, 2017.
[38] Yuanzhi Li. Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. In Advances in Neural Information Processing Systems, 2019.
[39] Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2019.
[40] Daniil Merkulov and Ivan Oseledets. Stochastic gradient algorithms from ode splitting perspective. In International Conference on Learning Representations, Workshop on Integration of Deep Neural Models and Differential Equations, 2020.
[41] Leon Mirsky. A trace inequality of john von neumann. Monatshefie für mathematik, 79(4):303 30(3))303-006. 1975.
12

---

[42] Asaf Noy, Yi Xu, Yonathan Aflalo, Lihi Zelnik-Manor, and Rong Jin. A convergence theory towards practical over-parameterized deep neural networks. arXiv preprint -Xiv:2101.042433 2021.
[43] Antonio Orvieto and Aurelien Lucchi. Shadowing properties optimization algorithms. Advances in
Neural Information Processing Systems, 32:12692-12703, 2019.
[44] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPS-W W, 2017.
[45] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-couvex learning via stochastic gradient langevin dynamics: a nonasympiotic analysis. Conference on Learning Theory, pages 1674-1703, PMLR. 2017.
[46]
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. In Advances in Neural Information Processing Systems, 2020.
[47] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in tensor factorization. In International Conference on Machine Learning. PMLR, 2021.
[48] Halsey Lawrence Royden and Patrick Fitzpatrick. Real analysis, volume 32. Macmillan New York, 1988.
[49] Andrew M Saxe. James L McClelland, and Surya Ganguli, Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. International Conference on Learning Representations. 2014.
[50] Damien Scieur, Vincent Roulet, Francis Bach, and Alexandre d' Aspremont. Integration methods and accelerated optimization algorithms. arXiv preprint arXiv: po::iiv:772.000 1702.06751, 2017.
[51] Ohad Shamir. Exponential convergence time of gradient descent for one-dimensional deep linear neural networks. In Conference on Learning Theory, pages 2691 12113.. PMLR, 2019.
[52] Bin Shi, Simon S Du, Michael I Jordan, and Weijie Su. Understanding the acceleration phenomenon via high-resolution differential equations. arXiv preprint 181.000000 2018
[53] Samuel I. Smith, Benoit Dherin, David GT Barrett, and Soham De. On the origin of implicit regularization in stochastic gradient descent. International Conference on Learning Representations, 2021.
[54] Weijie Su, Stephen Boyd, and Emmanuel J Candès. A differential equation for modeling nestero''s accelerated gradient method: theory and insights. In Advances in neural information processing systems. pages 25102251151100 2014.
[55] Endre Suli and David F Mayers. An introduction to numerical analysis. Cambridge university press, 2003.
[56] Flemming Topsoe. Some bounds for the logarithumic function. RGMIA Res. Rep. Collection, 7(2):1200, 2004.
[57] Gal Vardi and Ohad Shamir. Implicit regularization in relu networks with the square loss. arXiv preprint arXiv:2012.05 2020.
[58] Andre Wibisono, Ashia Wilson, and Michael Jordan. A variational perspective on accelerated methods in optimization. proceedings of the National Academy of Sciences, 113(47):E735) E7358, 2016.
[59] Ashia C Wilson, Benjamin Recht, and Michael I Jordan. A Iyapunov analysis of momentum methods in optimization. arXiv preprint arXiv: 16111026333 2016.
[60] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635-3673. PMLR, 2020.
[61] Lei Wu, Qingcan Wang, and Chao Ma. Global convergence of gradient descent for deep linear residual networks. In Advances in Neural Information Processing Systems, volume 32, pages 13389- 133988, 2019.
[62] Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view on implicit bias in training linear neural networks. International Conference on Learning Representations, 2021.
[63] Jingzhao Zhang, Aryan Mokhtari, Suvrit Sra, and Ali Jadbabaie. Direct runge-kutta discretization achieves acceleration. In Advances in neural information processing systems, pages 3904-3913, 2018
[64] Difan Zou and Quanquan Gu. An improved analysis of training over-parameterrzzed deep neural networks. Advances neural information processing systems, 2019.
[65] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over- pner-parameterized deep relu networks. arxiv e-prints, art. arXiv preprint 18.8888 2018.
[66] Difan Zou, Philip M Long, and Quanquan Gu. On the global convergence of training deep linear resnets.
In International Conference on Learning Representations, 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL.)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasigg new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No] All assets used (MNIST data and
PyTorch framework) are standard.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] assets other than our code (included in supplemental material).
There
(d) Did you discuss whether and how consent obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] All data used (MNIST) standard.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "mtLwuW4reYg", "reviewer": "Reviewer_x5V9", "summary": "This paper proposes to use bounds on the difference between gradient descent (GD) and gradient flow (GF) [Thm 3] as a general strategy to convert convergence proofs about GF (which is not an implementable dynamics) into convergence proofs about GD. The authors exemplify this strategy by providing a quantitative convergence guarantee for GD on deep linear neural networks [Thm 4], which is deduced from a convergence guarantee for GF [Prop 5]. The general comparison between GD and GF is classical in numerical analysis, so the main contribution is the analysis of GD on deep linear networks.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There could be two ways to position this paper, both of which are interesting but suffer from weaknesses in their current form:\n(i) putting forth [Thm. 3] as a general strategy to convert GF proofs into GD proofs, or\n(ii) proving a guarantee to train a deep linear network with GD\n\n- for (i): there are various ways to translate an optimization bound for GF into a bound for GD. The approach via Thm 3 (ie directly bounding the difference between the two trajectories) is maybe the most natural one, but it might degrade the guarantees.  Indeed, this difference grows in general exponentially in time, a commonly known and unavoidable fact (eg. the two trajectories can diverge at a saddle). The approach usually taken in the literature consists in taking the structure of the proof (eg, a Lojasiewicz inequality, a descent lemma, etc) and \"making it work\" in discrete time, which is not always much technically harder (in the present paper, bounding m(t) is not that easy either). Overall, if (i) is the goal of this paper, then the authors should convince the reader that using [Thm 3] is not less efficient than other proofs strategies; but the paper does not address this question since other strategies are not mentioned (in appendix A it is only written that discrete proofs are \"often far more technical and brittle\" but that is not convincing). On the positive side, it is a good contribution to make Thm 3 easily accessible in this community.\n\n\n- for (ii): unfortunately the arguments that make Prop. 5 (and thus Thm 4) true are not mentioned in the main paper. There is a proof sketch in the appendix but it is not very informative (in particular it does not detail the technical novelty compared to [4], which is needed to evaluate the contribution); also  I could not verify the plausibility of the argument due to its length and lack of detailed proof sketch. This is unfortunate because Prop. 5 Eq. (21) is an interesting result, and in particular I am not aware of a similar result where the alignment coefficient \"nu\" appears (but I am not aware of all the literature analyzing GD for deep linear networks).\n\nOverall, I find that this paper would benefit from a rewriting either focusing on point (i) or point (ii), and adapting the content accordingly.\n\nHere are minor additional remarks:\n- the title of section 4 \"optimization of deep neural networks is roughly convex\" is vague and misleading.\n- it is not clear how to interpret Proposition 2 because the natural \"time scale\" for a gradient flow is when the norm of the gradient of gradient is 1 (ie stepsize=1/gradient norm). So to compare GD and GF, what matters is how the curvature is small *relative* to the magnitude of the gradient. This important point does not seem to be discussed.\n- on Figure 1, it is impossible to see the distance between GF and GD as a function of eta. A potential fix is to plot this distance divided by the distance from initialization (and to not plot the distance from init, which has a different order of magnitude).\n- Orvieto and Lucchi, Shadowing Properties of Optimization Algorithms (Neurips 2019) is a relevant reference that should be mentioned.\n\n\nUPDATE AFTER REBUTTAL:\nI have read other reviews and the response from the authors. I thank the authors for the time they have spent replying to my comments. I think that they did not answer the core of my concerns which were about the positioning of the paper ((i) vs (ii)) and the lack clarity that results from this unsatisfying positioning. Reviewer jeQC has similar concerns. I acknowledge that the authors suggest various changes to improve the paper but there is little guarantee that the weaknesses will be fixed in a satisfying way in the next version. In short, if Prop 5 (and its consequence Thm 4) is indeed the main contribution of this work, then it is disappointing that after reading the main paper, the reader has almost no idea of how this result is proved. As a side note, I disagree that when the authors write \"our paper introduces an additional tool for proving discrete convergence\" because these tools are already known (as acknowledged in the article). For these reasons I maintain my score and encourage the authors to improve the presentation of their interesting result.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- there is no forseeable negative societal impact for this work.\n- limitations and suggestions are provided in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "OqRjGFETwj", "reviewer": "Reviewer_jeQC", "summary": "For fully connected neural networks with (i) linear activations (ii) homogeneous activations, the authors provide lower bounds on the minimal eigenvalue of training loss's hessian along the trajectory of gradient flow. In the case of linear activations, they leverage this result in order to give a convergence guarantee for gradient descent.", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Trying to translate continuous convergence results into (relevant) discrete ones by using generic discretisation results is in my opinion a challenging and interesting task which the authors want to address. However I have several major problems concerning the paper / results.\n\nOverall the paper is extremely dense and very hard to read. I suspect the use of many \\vspaces{-1} which does make the reading very pleasing.  Furthermore the related work is postponed to the appendix, it is therefore very hard for a non-expert reader to have any idea of the context in which the paper is built upon. For example the convergence guarantees from\n*A Convergence Analysis of Gradient Descent for Deep Linear Networks* (Arora et al.)  or   *Gradient descent optimizes over-parameterized deep ReLU networks* (Zou et al.) are not given nor discussed which is problematic. \nSeveral lemmas take space and are non-informative: for instance Lemma 3: what are we supposed to deduce from this expression ?  In general the authors make very little effort in order to make the stated results easily understandable: for instance eq (23) for the condition on the step size: what are the relevant quantities ? is the $\\ln$ quantity relevant ? why not simply use a $\\tilde{O}$ notation and leave the important quantities such as $\\tilde{\\varepsilon}$. Though these comments rely purely on the \"form\" and not on the actual mathematical claims, I believe much more effort must be put in order for the results to be understandable by future readers. All the unnecessary and technical constants / lemmas which complicate and slow down the reading without giving any intuition / relevant information should be postponed to the appendix. This would for instance make a lot of space for the related work which is crucial for the overall understanding of the challenges.\n\nPutting aside the \"form\" their still remain in my opinion some issues concerning the results:\n- l226-227: \"We conclude that the lower bound on $\\lambda_{min}$ starts off slightly negative, and becomes non-negative\": I don't understand what you mean. The lower bound you give seems to always be strictly negative. Do you mean that at convergence (which is in practice never stricltly attained) it is equal to $0$ ? If this is the case your sentence is a bit misleading as I first understood that from some point in the training is becomes positive.\n- Theorem 4: the result is not at all compared to the results from (Arora et al.) nor (Zou et al.). What is the improvement if there is one ?  To me it seems as your result is much weaker, their result holds for a step-size which is independent of $\\varepsilon$ whereas yours requires having a step size $O(\\sqrt{\\varepsilon})$ which basically means having to take step sizes infinitely small in order to converge. \n\nOverall much more effort must be put into the overall form of the paper (less dense and more digestible) and the main result seems weaker than previous results (which are not even discussed). This is why I give an overall grade of 3. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "NIM4es4qBA8", "reviewer": "Reviewer_4GXj", "summary": "This paper answers the question of how well does gradient flow explain the behaviour of gradient descent. They provide a sufficient condition — upper bound on step size — which when satisified ensures that the tracjectories of graidnet flow and gradient descent track each other. This upper bound is depends upon the minimum eigenvalue of the Hessian along the trajectory gradient flow, i.e., if the minimum eigenvalue is less large (less -ve or more +ve) better the match. \n\nFor FCNs and CNNs they show under certain assumptions, the minimum eigenvalue of the hessian along the trajectory of gradient flow doesn't goto -\\infty and is even non-negative around global minima, and therefore can be approximated by gradient descent with the appropriate step size. \n\nFor gradient descent, the authors show that a neural network of a fixed size and near zero initialization convergences, where the number of iterates has an exponential dependence $n$ on the depth of the network.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well written and motivated. The authors do not make many strong assumptions during their analysis. \n\nFurther, the proofs are backed with clear and well motivated proof sketches. Although I did go through most of the proof sketches, I did not go through all the proofs in detail. The proofs that I did go through looked correct to me. \n\nFew questions/comments for the authors\n\n- The convergence for gradient descent is only considered for networks with linear activation. While the number of iterates in this case is already exponential in $n$, can the authors comment on how the bound would change when we consider the nonlinear activation discussed.?\n- Empirically, it would be interesting to see how the minimum eigenvalue behaves throughout a gradient descent run, and if it indeed matches the claims made in section 4.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Negative societal impact is not applicable here. The future work discussed in this paper is to quantify/study the discrepancy between gradient descent with large step sizes.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "FnLIwIUAFhd", "reviewer": "Reviewer_nsKx", "summary": "- This paper applies the numerical analysis of the ODE initial value problem (the fundamental theorem, Thm 2) to explain the relation between continuous gradient flow and discrete gradient descent in deep learning.\n- The step size depends on the minimal eigenvalue of the Hessian, and Section 4 gives a lower bound of the minimal eigenvalue for linear networks, then try to extend it to a nonlinear setting.\n- For deep linear networks, Section 5 proves a convergence result for the continuous gradient flow, then applies the fundamental theorem to translate it to the discrete gradient descent directly.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: It is a novel idea to apply the classical numerical analysis results to deep learning. The authors show some preliminary results in this approach. E.g., the fundamental theorem requires the minimal eigenvalue of the Hessian, which can be estimated for linear networks; the authors also illustrate how to translate a gradient flow result to gradient descent in deep linear networks.\n\nQuality: This is a theoretical paper. The theorems and propositions are supported by mathematical proofs, and also illustrated by numerical experiments. Most of the theoretical results focus on the linear networks, and the extension to nonlinearities are discussed.\n\nClarity: The statements of the theorems and propositions are clear for me.\n\nSignificance: It is a good trial to revisit the classical numerical analysis in deep learning. The applications shown here are most in linear cases, and the convergence rate in Section 5 is not optimal since it is exponential w.r.t. the depth $n$. Nevertheless, I think it is still a good starting point.\n\n**UPDATE**\n\nThanks to the authors for the response, and I have also read others' reviews.\n\nI think the main contribution of this paper is to introduce the numerical analysis theorem to deep learning, and I think it is valuable to provide the fast tool to translate the continuous analysis to discrete GD, if one only requires *a* convergence result instead of *the best* convergence rate. Therefore the goal of Section 5 is to illustrate how to apply this tool to linear networks, and it is okay for me that the convergence rate here is not as good as previous literature.\n\nOn the other hand, I agree with reviewer x5V9 that the current presentation of the results may not convince the readers that this framework is not less efficient than other proof strategies.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While the linear results are rigorously proved, the extension to the nonlinear cases are more like discussions and illustrations instead of proofs. For the deep linear networks, the convergence rate given by the fundamental theorem is still not optimal, which may be regarded as future work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to use gradient flow techniques to analyze the convergence of gradient descent in deep neural networks (restricted to deep linear models). The paper receives diverse reviews at the beginning. One of the main criticisms of this paper is that the presentation is not position in a right pace to make the paper more easier understandable. The main paper contains some detailed "intermedia" results that can unnecessarily complicate the paper, e.g., Lemma 3 does not provide too much information to understand the main results and thus can be moved to the appendix. The presentation issue can be also improved by taking Reviewer x5V9 comment to better position the paper, (i) putting forth [Thm. 3] as a general strategy to convert GF proofs into GD proofs, or (ii) proving a guarantee to train a deep linear network with GD. Another weakness is about the limitation of the proposed technique, which only applies to deep linear neural networks, and the extension to the commonly useful non-linear one is not clear.

Overall, after some detailed conversations with the reviewers, we all agree that the presentation and position of the paper is the main weak point and should be significantly improved. I suggest the authors revise the paper according to the comments of the reviewers for next round submission. As a personal comment, it seems to me that the convergence results requires the stepsize to be bounded from above, which might not be the case in real cases, where some useful model usually take a large stepsize in the optimization. This point might need to be discussed.
Decision: Accept (Spotlight)