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....mmm..... 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- inattaaindeeeddenn 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. Rd. 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,4e), q E RR,, 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::00mmm [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),(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 (( (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' [ (<)"llllsssetttte 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 100-0(0)1l2 0(0)1l2
π< 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=-infgee 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- 10-llll0000lllll T (e (1) -1)-m m
.if m > 0 (non-convexity)
where c:=
we will have 110
0 (kr) lla for k (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..... n, 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) (2.0}) ) and leaky rectified linear (a(z) = max max(2,022 (2,02] for some 0 <<)< activations.
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
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 " 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=((0)) -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 SubappendixI.6
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,.)) *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 - -c 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.rationn4...Irrratinin Ireating linear activation. particular, it makes use of the fact that gradient flow initialized near zero maintains balance between weight matrices -artiiess--fff 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 converge to global minimum almost surely under random (data-independent) near-zero initialization.
size efficiently
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 -=,,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 Ayzz Frobenius +c, where Aga := [ST
(S)
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 Jebow 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=11a)/ /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 m(t))dt's
[max (
15m
1.2 [+v1)
1-2 1- In
( n² (2(22max 1-v 11 1))0))n-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 (w: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
L.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//0
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), 1,,,, 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 (9(6))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- paer-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": "cZ0m256nlOf", "reviewer": "Reviewer_4TKP", "summary": "Using continuous time flows to analyze discrete time descent methods is very appealing, but the soundness and utility of the connection between the two is still being determined by the community.  Existing analyses using gradient flow disregard computational efficiency, and do not obviously imply that discrete time descents will converge, given convergence of flow trajectories.  The authors address these concerns by employing modern tools from numerical integration literature which depend upon curvature bounds local to flow trajectories.  The authors show that these conditions can be expected in deep linear neural networks, and hint towards their applicability in networks with homogeneous nonlinear activations.", "questions": "", "limitations": "", "rating": 8, "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": "EDIT: Score updated from 6 to 8 in light of author rebuttal.\n\n## Major Feedback\n\nSummary: \n- Contributions to the linear setting are good, but empirical support and clarity could be improved.\n- Contributions to the nonlinear setting are less convincing and complete.\n- Scope is too large for a conference paper, and the standalone completeness of the first 9 pages has been hurt by relegating the related work and conclusion to appendices.\n\nMy recommendation for publication comes from the positive aspects of the linear setting.  Similarly, the opportunity for improving my review score lies mostly in improving clarity and empirical support for the linear setting.\n\n### Deep linear setting\n\nThe contributions to the deep linear network setting are sufficiently convincing, complete, and novel to warrant publication.  Especially if empirical support is improved.\n\nTo my knowledge, the soundness of flow-based analysis in existing literature is grounded in three elementary integrator properties: consistency, convergence, and some flavor of stability (CCS).  Specifically, when a numerical integrator with CCS properties is shown to connect discrete and continuous time, the continuous time flow is used to make claims about the discrete time descent method.  But important questions about descent methods, i.e. convergence conditions and rate over long horizons, cannot be determined based only on CCS.  Especially for the naive Euler-like integrators which correspond to gradient descent methods, because they have only first order consistency (which entails very poor bounds on long-tail behaviour via global truncation error) and poor numerical stability in many cases.  The “Fundamental Theorem” cited in this work provides much more relaxed bounds on step size for similar guarantees of the approximation error between discrete and continuous trajectories.  The Fundamental Theorem is most powerful when the curvature along flow trajectories is well-behaved.  The authors spend considerable effort showing that such conditions can be expected for fully connected and convolutional neural networks with linear activations, culminating in Section 5.  This is a significant and novel contribution.  In my opinion, these results alone are sufficient for publication, and more than enough scope for a conference paper.\n\nThe experiments summarized by the left pair of plots in Figures 1 and 2 offer some support for theoretical claims, but only in that “standard choices” are close to the continuous limit.  This is important to establish, but there is room for validation of the theory itself.  Specifically:\n- A bound on step size is theoretically provided, but the experiments do not use it.  Rather, they start from a step size $\\eta_0$ according to a “standard choice” of 0.001.  If the theory is correct, we should see identical experimental results if $\\eta_0$ were chosen at or near the established bound.\n- A similar experiment should be run with step size increasing above and beyond the theoretically guaranteed step size bound, so that the severity of approximation error is made clear.  This would help determine the tightness of the bound.\n- For a fixed $\\bar{t}$, Theorem 3 shows a step size for which the descent and flow will be epsilon close to each other over the interval $(0, \\bar{t}]$.  So we have a theoretical prediction for the horizon where approximation might break down.  Similar to the point above, the tightness of the bound could be experimentally indicated if the specific time $\\bar{t}$ were indicated on the plots (e.g. as a vertical line) and the optimization process were allowed to continue well beyond $\\bar{t}$.\n\n### Deep nonlinear setting\n\nThe nonlinear setting analysis is not as complete, and I am hesitant to suggest its publication.\n\nOn L240-242, nonlinear, homogeneous activations are excluded from the results of the fundamental theorem.  Due to the lack of theoretical guarantee, claims in this nonlinear setting warrant specific and considerable empirical evaluation.  But there are only two experiments with nonlinear activations, and their discussion is quite minimal.  Further, the authors claim that the linear setting analysis is still useful as a “piecewise characterization” without much discussion on where the failures of such piecewise characterization might lay.  The contributions to nonlinear setting would be much improved by further discussion of the meaning and potential limitations of “piecewise characterization,” as well as experiments which specifically demonstrate them.\n\nHowever, this work is already 95 pages with appendices, so I do _not_ recommend adding even more content for discussion empirical support.  I am open to discussion on how this might be addressed, but my initial preference is for the nonlinear setting to be completely deferred to future publication.  That way, the finishing touches to the linear setting can be included in the main body, along with related work and concluding remarks.  \n\n## Minor Feedback\n\n- The bounds on step size, e.g. equation (23), appear quite cryptic, and they strongly motivate the reader to wonder how large such step sizes might be.  It would be useful to see examples of the magnitudes of step sizes these bounds entail.  (Similar feedback applies to the expressions for tbar, the endpoint of the time interval for which flow and descent are epsilon close.)\n- Since \\mu(t) appears twice in equation (4), once as a positive exponent, and again as a negative exponent in an integrand, it is not immediately obvious what \\mu(t) we should hope for in order to have good correspondence between continuous and discrete time.  In what cases should we expect \\mu(t) to be pathological?    i.e. which \\mu(t) would induce a poor correspondence?  Perhaps the worst case described in Appendix E would be more edifying if accompanied by some figures to demonstrate this.\n- In sections 2 and 3, the difference between discrete and continuous initializations $||\\theta_0 - \\theta(0)||$ appears several times.  To my knowledge, we are primarily concerned about the case when initialization is identical.  And the expressions would be more clear and interpretable if the difference were to vanish.  Remark 1 suggests that it is to “account for initialization which is not perfectly balanced.”  Is this a significant enough reason to hurt clarity and interpretability of your results?  Since you already defer analysis of this case to Appendix J, perhaps it would be worth simplifying the expressions in the main body to improve clarity and interpretability.  Then their more general forms could be used and proven in Appendices J and L, respectively.\n- In Figure 1, the plots showing distance (right of each pair) are reasonably convincing as presented, but it would be helpful to see the same data on a log scale y axis.\n- Several times, the phrase “the latter” is used ambiguously.  Please replace these occurrences with the actual noun or noun phrase being referred to.  It is frustrating to parse the same sentence repeatedly, and it hurts overall clarity when the correct reference is ambiguous.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations: Technical limitations are explicitly suggested, and the boundaries between well-established results and more speculative claims are made clear.\n\nSocietal Impact:  The work is highly theoretical and fundamental, so the ethical considerations are the same as those which apply to science and technology in general.  The authors need not address them specifically in this work.\n\nHence, Both are addressed adequately in the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "UiJ_n88SxNf", "reviewer": "Reviewer_r4iB", "summary": "This paper studies the approximation of discrete gradient descent algorithm to the continuous gradient flow for neural network models. Firstly, a general result is cited from previous work on numerical analysis to control the distance between Euler discretization and the ODE solution. Then, the result is translated into a theorem on the distance between gradient descent solution and gradient flow solution. A critical quantity in the bounds is the minimal eigenvalue of the loss function's Hessian. The bigger this smallest eigenvalue, the better the gradient descent approximates the gradient flow. For deep neural networks with linear, ReLU and leaky ReLU activation functions trained from small initializations, lower bounds for this smallest eigenvalues are derived along the GF trajectory. Especially, for linear networks, this lower bound is extended to the neighborhood of the GF trajectory, and together with the distance control between GD and GF solutions, a convergence result for GD is proven. \n\nNumerical experiments show that for fully connected linear and ReLU networks the GD trajectories with sufficiently small learning rate do not differ drastically when the learning rate changes. Hence the GD trajectory should be close to the GF trajectory. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper combines existing works from several different sources---the numerical discretization of ODEs, the weight balance along the GD trajectory for neural networks, and the convergence of GF for deep linear networks---and derive new results on the global convergence of GD on linear networks. The convergence result is indeed new. However, the results are not surprising, and the analysis techniques used are also not new. \n\nDetailed comments as follows:\n1. In theorem 4, the learning rate should be super small, depending exponentially on the depth. This makes the results less meaningful. By classical numerical analysis, as long as the loss landscape is smooth, the GD trajectory, as a Euler scheme, will always tends to the GF trajectory when the learning rate decreases to zero. Hence, as long as the learning rate is small enough, results like that in theorem 4 is natural and trivial. I did not see any big improvement of Theorem 4 over those given by traditional understanding. Just show that the GF trajectory is bounded, and thus the Hessian of the loss function is also bounded, we can easily get results like Theorem 4 using truncation error analysis of Euler scheme. The statement of the results will be much simpler than Theorem 4 in the paper, while no essential difference. I believe the upper bound for the learning rate will still depend exponentially on the depth. \n\n2. In proposition 1 and 3, the authors show that the smallest eigenvalue of the Hessian has no lower bound if the parameter \\theta can be arbitrary. However, this is achieved by pushing the parameters to infinity. This means, as long as some norm of the parameter vector is bounded, the smallest eigenvalue is bounded. Hence, for any dynamics that will not push the parameters to infinity, the closeness between the dynamics and its discretization can always be bounded. \n\n3. In real applications, many phenomena confirm the big difference between GD and GF. For example, the loss curve jumps down when learning rate is decayed; and GD with different learning rate finds solutions with different generalization performance. These phenomena should not happen if GD is just a close approximation of GF. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations of the work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3h"}, "extra_text": {}}, {"review_id": "PYWeOJjEAt4", "reviewer": "Reviewer_kYKg", "summary": "This paper studies under which conditions gradient descent (discrete) may approximate gradient flow (continuous) in neural networks. The motivation is that gradient flow is often considered in theoretical studies while gradient descent (with a finite step size) is used in practice. An upper bound for the distance between the two is derived in terms of the eigenvalues of the Hessian and the Lipschitz constant of the loss.  The bound is then applied to fully connected architectures with linear and leaky ReLU activations. A convergence proof of gradient descent for deep linear networks is provided and also some experiments on MNIST to test the theory.\n", "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": "Pros:\n- First convergence proof of deep (three or more layer) neural network of fixed size.\n- Results may inspire future theoretical work.\n- Writing is OK\n\nCons:\n- Convergence proof only applies to linear activation functions.\n- The upper bound for the distance between continuous vs discrete problem is not novel. The main theoretical contribution is bounding the minimum eigenvalue of the Hessian for deep linear networks and leaky ReLU.\n- My main concern is about the practical significance of the work. Currently, the widespread opinion is that learning rate is a crucial parameter for training neural networks, and that (generalization) performance is optimal for a finite value of the learning rate which is far from gradient flow (see for example the recent work of https://arxiv.org/abs/2101.12176). Therefore, gradient flow, while interesting theoretically, is not very useful in practice.\n\nOther comments:\n- The statement: “the “more convex” the objective function is along the trajectory of gradient flow, the better the match between that and gradient descent”, is misleading. If the loss is very \"sharp\" along some directions, then gradient descent will fail to follow gradient flow. This is accounted for by the \"smoothness\" beta: if the max eigenvalue of the Hessian is very large, then beta is large and the bound is small. I understand that the author’s statement refers to the minimum eigenvalue, not the maximum, but the statement remains misleading.\n- Unresolved questionmarks on line 314\n- A detailed discussion of the limitations of the work is missing.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Little societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "IKQGSu6YjH", "reviewer": "Reviewer_DACB", "summary": "The authors propose to use a result from numerical analysis that connects approximate numerical solution to the exact solution of an ODE to analyze the relationship between gradient descent and gradient flow.  In particular, more convex i.e. more positive the smallest eigenvalue of the Hessian, the better the approximation. The authors claim that for a certain class of networks (mainly with homogeneous activations),  starting from a near zero initial point, the curvature is favorable and gradient descent approximates gradient flow well. This leads them to be able to to \"lift\" an argument about how well such networks can be optimized from gradient flow to gradient descent.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is mathematically dense with most of the real meat in 100 pages of supplementary material. I have not checked the math, and so these are more or less high level comments.\n\nFirst off, I really like the experimental bit (which is only a small part of the paper) that shows that as step size decreases, the trajectory of gradient descent more or less remains the same. This is a nice check.\n\nSecond, the main point about using results from numerical analysis to understand the relationship between gradient flow and gradient descent is also a good one, and perhaps even though obvious, is worth saying, and reminding the community.\n\nThat said, some high level questions:\n\n(1) I do not have a good sense of how \"convex\" gradient descent trajectories are (even if started near zero), and would like a reconciliation of what the authors are saying here with the work from Belkin and colleagues recently: https://arxiv.org/abs/2003.00307 Are these papers in agreement or disagreement about the convexity (either overall or near optimum)?\n\n(2) I am unclear on if the authors are claiming the gradient flow convergence to minimum as a new result, or if that was well known, and their contribution is lifting that to the discrete case? \n\n(3) Does gradient flow always converge to the minimum (within the class of networks considered, >= 3 levels, homogeneous) even if they are not over parameterized? (And why >= 3, i.e., why isn't >=2 \"deep\"?)\n\n---\n\nOriginality: Not sure, please see clarifying questions above.\n\nQuality: Unable to evaluate correctness of the main claims. \n\nClarity: Not very clear. The paper seems to be a hasty condensation of a much longer work.\n\nSignificance: Somewhat. Theoretically connecting gradient flow and gradient descent using tools from numerical analysis seems useful and something that folks could build on. The rest I am not sure.\n\nOverall my sense is that this work probably is more appropriate for a journal given its length.\n\n---\n\nThank you for the response. I raise my score. Sadly my confidence remains low since I cannot intuitively understand or vouch for the new results obtained by the authors. I would encourage the authors to provide more intuition in the final writeup for the main parts, e.g., why is the trajectory of gradient flow mildly non-convex, Proposition 5, etc.\n\nRegarding my question (3) above, I mean \"almost always\" since that's what I think you are claiming. I am still surprised that something magical happens for 3 layer networks that doesn't for 2. I would imagine that the watershed is the presence of a single hidden layer (i.e. 2 layer networks) rather than the requirement for 2 hidden layers (which is how I interpret 3 layer networks). I may be off by 1 in interpreting your depth numbers (if so, please let me know and clarify in the paper), but if not, can you provide some intuition for this requirement? \n\n\n\n     \n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Atp-aQDD69F", "reviewer": "Reviewer_hENG", "summary": "DISCLAIMER: I am not a theorist, and have not looked at the proofs. My confidence level for this review is hence low, and is based on the theorem statements only. I am also not familiar with what would count as a solid contribution in a theory paper, so this is a best guess on my part.\n\nThis paper uses classical results from numerical analysis to analyze the discrepancy between gradient descent and gradient flow, as the latter is often used in proofs, while the former is applied in practice. They show a bound (based on classical results) for the discrepancy based on the minimum Hessian eigenvalue along the gradient flow path, and then proceed to bound the min eigenvalue for linear, nonlinear (homogeneous activation) fc and conv nets along this path with near-zero initialization (but also show that it can be arbitrarily negative in general).\n\nUsing this, they are able to transfer a proof of convergence to global minimum (under appropriate initialization) for a linear deep network from gradient flow to gradient descent.\n\nThey also include small experiments to verify that the gradient descent path is indeed close to the gradient flow path by decreasing the step size.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "Noting the disclaimer above, I think this is a solid contribution. The authors seem to have successfully applied a classical numerical analysis theorem to proving convergence to a global minimum of gradient descent. I vote to accept the paper.\n\nThe proofs are quite extensive, with a 95 page appendix. This might distract from the clarity of the paper. I also do think the conclusion and some related work would be a better fit in the main paper, rather than in the appendix. Perhaps some theorem statements could be delegated to the appendix, such as the lower bound of the min eigenvalue for non-linear activations (since this is not used in the final transfer proof from flow -> descent). \n\nOne suggestion for experiments:\n- Another way I can think of that could help compare ordinary GD to GF could be to do optimization using more advanced ODE time-steppers, such as RK4 or adaptive time-stepping. Of course this could be computationally expensive to do in practice for training real NNs, but for the purposes of seeing how well an approximation Euler is it could be a valuable comparison compared to just decreasing the step size.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors seem to provide precise theorem statements of their results and adequately addressed the shortcomings.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is an important theoretical contribution to the field of deep neural networks providing one of the first rigorous mathematical analysis of the commonly used discrete gradient-descent methods via the rich literature on continuous gradient flows. All the reviewers agree that the manuscript is a strong contribution to the field. Furthermore, reviewers' comments were addressed by the authors in detail in the rebuttal phase.
Decision: Accept (Spotlight)