First-Order Optimization Algorithms via Discretization of Finite-Time Convergent Flows
Authors: Mouhacine Benosman
Orlando Romero
Anoop Cherian
Venue:  (2021)
Keywords: Finite-time optimization
dynamical systems
deep neural networks optimization

Abstract: In this paper, we investigate the performance of several discretization algorithms for two first-order finite-time optimization flows. These flows are, namely, the rescaled-gradient flow (RGF) and the signed-gradient flow (SGF), and consist of non-Lipscthiz or discontinuous dynamical systems that converge locally in finite time to the minima of gradient-dominated functions. We introduce three discretization methods for these first-order finite-time flows, and provide convergence guarantees. We then apply the proposed algorithms in training neural networks and empirically test their performances on three standard datasets, namely, CIFAR10, SVHN, and MNIST. Our results show that our schemes demonstrate faster convergences against standard optimization alternatives, while achieving equivalent or better accuracy.

Under review as a conference paper at ICLR 2021
FIRST-ORDER OPTIMIZATION ALGORITHMS VIA DIS- CRETIZATION OF FINITE-TIME CONVERGENT FLOWS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper the performance of several discretization algorithms for two first-order finite-time optimization flows. These flows are, namely, the rescaled- rescaled-gradient flow (RGF) and the discontinuous dynamical systems that converge locally in finite time to the minima gradient-dominate functions. We introduce three discretization methods for these first-order finite-time flows, and provide convergence guarantees, We then apply the proposed algorithms in training neural networks and empirically test their performances on three standard datasets, namely, CIFARIO, 10, SVHN, and MNIST. Our results show that our schemes demonstrate faster convergences against standard optimization alternatives, while achieving equivalent or better accuracy.
flow (SGF), and consist of non-Lipscthiz
INTRODUCTION
Consider the unconstrained minimization problem for given cost function f: Rd -> TR. When f is sufficiently regular, the standard algorithm in continuous time (dynamical system) is given by
á = FGF & f()(
(1)
with I(),,, known the gradient flow (GF). Generalizing GF, the q-rescaled GF (q- RGF) Wibisono et al. (2016) given by
Vf(x)
(2)
with 0 and E (1, oo) has an asymptotic convergence rate f(=))))
under mild regularity, for ||x[(0) - x=1 > 0 small enough, where x² E IR" denotes a local minimizer of f. However. we recently proved Romero Benosman (2020) that the q-RGF, q-signed GF (G-SGF)
as well as our proposed
= >=>\\>>[<>))>> sign( (V)(z)),
(3)
where sign(-) denotes the sign function, applied element-wise for (real-valued) vectors, both finite-time convergent, provided that f is gradient dominated of order E (1,4). In particular, if is strongly convex, then RGG and 9-SGF is finite-time convergent for any q E (2, oo). since f must be gradient dominated of order p = 2.
CONTRIBUTION
In this paper, we explore three discretization schemes for the q-RGF (2) and q- Q-FGF (3) and provide some convergence guarantees using results from hybrid dynamical control theory. In particular, we explore Corward-Eules discretization RGF/SGF, followed by an explicit Runge-Kutta discretiza- tion, and finally novel Nesterov-like discretization. We then test their performance both synthetic and real-world data in the context of deep learning, namely, over the well-known datasets CİFARIO, SVHN, and MNIST.
RELATED WORK
Propelled by the work Wang & Elia (20IT) and Su et al. (2014), there has been a recent and significant research effort dedicated analyzing optimization algorithms from the perspective of

---

Under review as a conference paper at ICLR 2021
dynamical systems and control theory, especially in continuous time Wibisono et al. (0016) Wilson
(2018): ; Lessard et al. (2016); Fazlyab et al. (2017b); Scieur et al. (2017): França et al. (2018); ; Fazlyab
7b);
ct al. 2018); Fazlyab et al. (2018); Taylor al. (2018): França al. (211 Orvieto & Lucchi (2019): Muchlebach & Jordan (2019). A major focus within this initiative is in accceleration, both in
terms trying to gain new insight into more traditional optimization algorithms from this perspective, or even to exploit the interplay between continuous- -time systems and their potential discretizations for novel algorithm design Muchlebach & Jordan (2019); Fazlyab et al. (2017a); (Shi et al. (2018); Zhang et al. (2018); França et al. (201 (2019b); Wilson et al. (2019). Many of these papers also focus on explicit mappings and matchings of convergence rates from the continuous- time domain into discrete time.
For older work connecting ordinary differential equations (ODEs) and their numerical analysis, with optimization algorithms, see [Botsaiis (1978a b): Zggier (981); Snymmn (9822 1983); Brookett (1988); Brown (989). In Helmke & Moore (194)). the authors studied relationships between linear programming, ODEs, and general matrix theory. Further, Schropp 1995) and Schropp & Singer (2000) explored several aspects linking nonlinear dynamical systems to gradient- optimization, including nonlinear constraints.
Tools from Lyapunov stability theory are often employed for this purpose, mainly because there already exists a rich body of work within the nonlinear systems and control theory community for this purpose. In particular, typically in previous works, one seeks asymptotically Lyapunov stable gradient-based systems with equilibrium (stationary point) cost function, thus certifying local convergence. Naturally, global asymptotic stability leads to global convergence, though such an analysis will typically require the cost function to be strongly convex everywhere.
isolated extremum of the given
For physical systems, a Lyapunov function can often be constructed from first principles via some physically meaningful measure of energy (e.g., total energy potential energy + kinetic energy). In optimization. the situation somewhat similar in the sense that a suitable Lyapunov function may often be constructed by taking simple surrogates of the objective function as candidates. For instance, V(x) f(z) - f(x") can be a good initial candidate. Further, if f is continuously differentiable and xt is an isolated stationary point, then another alternative is V(x) & [[>]() However, most fundamental and applied research conducted in systems and control regarding Lyapunov stability theory deals exclusively with continuous-timg systems. Unfortunately, (dynamical) stability properties are generally not preserved for simple forward-Eules and sample-and laws laws|Stuar Stuart& & Humphries 1998). Furthermore, practical implementations of optimization algorithms in modern digital computers demand sescrreee-ime. Nonetheless, it has been extensively noted that a vast amount of general Lyapunov-based results appear have a discrete-time equivalent.
discretizations and control
In that sense, we aim here to start from the q-RGF, and q-SGF continuous flows, characterized by their syapunov-hased finite-time convergence, and seek discretization schemes, which allow to "shadow" the solutions of these flows in discrete time, hoping to achieve an acceleration of the discrete methods inspired from the finite-time convergence characteristics of the continuous flows.
2 OPTIMIZATION ALGORITHMS AS DISCRETE-TIME SYSTEMS
Generalizing 1] and 3 consider a continuous-time algorithm (dynamical system) modeled via an ordinary differential equation (ODE)
== F(x)
(4)
for 2 0, or, more generally, a differential inclusion
i(() E F(x((()
(5)
a.e. t (e.g. for the q oo case), such that xx(() + x² t In the case of the R-RGF ( and SFFG (3) for f gradient dominated of order p E (1, we have finite-time convergence, and thus t* (z()) oc.
Most of the popular numerical optimization schemes can be written in a state-space form (i.e., recursively),
Xx+1 = Fa(k,
(6a)
F6 G(X+)
(6b)
2

---

Under review as a conference paper at ICLR 2021
for k E Z+ _ (0,1,2.... and given Xo R" (typically 2 n), where Fa 24 R R" and G: R -
discrete-time dynamical system constructed by discretizing (4) in time. particular, we have 2₁z = x((t), where {0 = to < t < t2 < .... denotes a time partition call X5 and 2k. respectively, the state
Naturally, (6) can be
and xx.) solution (4) (5) appropriate. Therefore, and outpur at time step k. Whenever (a X) does not depend on k, we will drop and thus write
( instead. Whenever m = n, we will denote take G(X) X and replace X and X by a and Tk, respectively.
Example The standard gradient descent (GD) algorithm
Øk++ = 2 7/ f(rx)
with step size (learning rate) 7 > 0 can be readily written in the form 6 by taking m n. Fa( [(x), and ((x) A
If the step sizes are adaptive, i.e. if replace 7) by sequence {m& with mp >> O, then we only need to replace (a é 778 fxx), provided that {m not computed using feedback from { (e.g. through a line search method).
If we do wish use feedback (and no memory past the recent output and step size), then we can set m = n + 1, vi) - xr and Fa((z; - [F] ([x; v]); F(?) ([x; n))] where F3 (1) nn) & r f()). and F:(2) is user-defined function that dictates the updates in the step size. In particular, an open-loop (no feedback) adaptive step size { may
also be achieved under this scenario, provided that it possible write π F. (nk). If this is not possible (and still open-loop step size), then may take F (k: X) 1/++1 and of course add k-argument in Fa-
If we wish to use individual step sizes for each the n components of {.x}. then it suffices to take Y/ as an n-dimensional vector (thus m 2n), and make appropriate changes Fa and G.
In each of these cases, GD can be seen forward-Eull discretization of the GF ( i...
1 2k + +4 (GF(k)
with For f and adaptive time step At, - tx+1 tx chosen as At, Tk-
Example The proximal point algorithm (PPA)
Tk+1 arg min #ER=
f(x) + 21TR
|| -0-1x= xxll?
(9)
with step size 7k > (open loop, for simplicity) can also written the form (6). by taking m = n, 1 |2' - [ and G(z) & x. Naturally, we need to assume (akk, x) & arg min (x') + 27j.
sufficient regularity for (a æ)) to exist and we must design a consistent way to choose Fa(k, x) when multiple minimizers exist in the definition of Fa 2). Alternatively, these conditions must be satisfied, at the very least, at every (ks, x) E {00, ,n), (1, (1, (2) .} for particular chosen initial To E R
Assuming sufficient regularity, we have vz(((x) + 2mz ||
xx H 0, and thus
1 (x4+1 x + Fe+1 + At, FGr((E4)))
V (x(++1) +
(10)
with Ate 77. which is precisely the backward-Fin -ullr discretization of the GF
Also known as closed-loop design in control theoreetc and reinforcement learning terminology, meaning that ni (k(, Rx) for some ip Z., R + R that does not depend on (Xo. X1, X2....). On the other hand, open-loop design he seen closed loop with sp(k, constant for each E Z._.
3

---

Under review as a conference paper at ICLR 2021
Example 3. The Nesterov accelerated gradient descent (N-AGD)
yk = + :3e(T xt-1)
(11a)
1 = yk T/s V (31))
(1lb)
with step size m 0 and momentum coefficient
(both open loop, for simplicity), can be
written in the form (6) by taking m = 2n,
Fa [u: z²)) - (1 3k+1) (v 1/e f -k+103) Tk V f()
(12)
and G([yxz)) x)) - x for y, x E R In other words, X = [uus rn). Traditionally, 3x $=2 but clearly, we set 77 = 7 > 0 and 3g = (0, 1) (in practice, n x 0 and 8 = 1), then we can drop
from (k, [y)
There exist a few approaches in the literature on the interpretation of N-AGD T1b as the dis- cretization of second-order continuous-timg dynamical system, namely via vanishing step size
argument Su et al. (2014), or via symplectic Euler schemes of crafted Hamiltonian systems MMuhlee bach & Jordan 2019); França et al. (2019b).
PROPOSED ALGORITTMS VIA DISCRETIZATION
In this section. we propose three classes optimization algorithms via discretization of the q-RGF (2) and q-SGF (3. But first, we review the necessary conditions to ensure finite-time convergence of these flows.
Given E co), let Fg-RGF(2 (x) and Fg (z)) be defined, respectively, by the RHS of (2)
and 3 The hyperparameter > 0 is not explicitly denoted in RGF, FGF Next, borrowing terminology from Wilson et al. (2019), we say that f (assumed continuously differentiable) is j-gradient dominated of order (1, 0ol (with μ > 0) near the local minimizer if
[f(x)] 2 (f(x)
(13)
p
for every E T near x², where f f(x)). When fr > O is unknown unimportant, but known to exist, we will omit it in the previous definition. It can be proved that continuously differentiable strongly convex functions gradient dominated of order p 2. Furthermore, if is gradient dominated (of any order) w.r.t. x", then x* is an isolated stationary point of f.
Remark 1. For strongly convex functions, gradient dominance of order = can be established. In the Polyak-
fact, gradient dominance is usually defined exclusively for order p 2, often referred Eojasiewicz (PL) inequality, which was introduced by Polyak (9633) to relax the (strong) convexity assumption commonly used show convergence of the GD algorithm (7). The PL inequality can also be used to relax convexity assumptions of similar gradient and proximal-gradee gradient methods Karimi et al. (2016): Attouch & Bolte (2009). Our adopted generalized notion of gradient dominance is strongly hid to the Lojasiewicz gradient inequality from real analytic geometry, established by Eojasiewicz (1963 1965 independently and simultaneously from Polyak (1963). and generalizing the PI. inequality. lit. More precisely, this inequality is typically written as
[((I) C -1) S
(14)
for every E Rn in small enough open neighborhood of the stationary point x = for some C> 0 and 0 E [2. 1]. This inequality is guaranteed for analytic functions Lojasiewicz/ (1965). More precisely, when x" is a local minimizer of the aforementioned relationship explicitly given by
C= c=(p-)
p
(15)
Therefore, analytic functions are always gradient dominated. However, while analytic functions are always smooth, smoothness is not required to attain gradient dominance.
For modern treatments English, tojasiewicz & Zurro 1999 Bolte
2007
4

---

Under review as a conference paper at ICLR 2021
We ready state the Kiite-ttime convergence of the q-RGF and q-SGF (3
Theorem 1. Romero & Benosman 2020) Suppose that f R - IR is continuously differentiable and u-gradient dominated of order p E (1, 00) near a strici local minimizer x² E IR. Let > 0 and q E (p, x... Then, any maximal solution x-)), in the sense of Filippov, to the q-RGF ( or g-SGF will converge in finite time to x", provided that [1x(0) - x=1 > 0 sufficiently small. More precisely,
lim æ(t) z², where the convergence time t* < may depend on which flow is used, but in both
cases is upper bounded by
V [f(x)))| |
Cr
(16)
cC (1 )
where zo = =(0), C-
pu" 1=:00
P-1 and 0' = -- In particular, given any compact
and positively invariant subset C D, both flows converge finite time with the aforementioned convergence time upper bound (which can be tightened by replacing D with S) for any E S. Furthermore, Df R", then we have global funite-time time convergence, ie. finite-time convergence to any maximal solution (in the sense of Filippov) re-)) with arbitrary Do E R
In essence, the analysis (introduced Romero & Benosman (2000) consists of leveraging the gradient dominance to show that the energy function {t) _/ f(((t) f satisfies the Lyapunov-like
differential inequality {() = ((E(1))) for some < 1. The detailed proof is recalled in Appendix for completeness.
3.1
MAIN RESULT 1: DISCRETIZATION ALGORTHTM AND THEIR CONVERGENCE ANALYSIS
3.1.1
FORWARD-BULER DISCRETIZATION
First, we propose simple forward Euler discretization of the finite-time convergent flows
Th++1 = 1 (Tx). 1) >>> 0
(17)
where F E {FG- FG-SCF). We show later, in Theorem 2 that this simple method leads, for small enough 17 > 0, to solutions that are c-close to the finite-time time flows.
3.1.2 EXPLICIT RUNGE- KUTTA DISCRETIZATION
We propose the following discretization
Tk+1 Ik + 17
a F(y)), 2k Ikg
02 1,
(18a)
i-1
vi = Ib + nn
F,F(d),
(18b)
for 17 0, K E (1,2,3,...) and F E (Fq-RGF, Fy-SGF) ). This method is well-known to be numerically stable under the consistency condition >i a; = 1. Stuart & Humphries (996).. However, in optimization framework, want to be able to guarantee that the stable numerical solution of (18) remains close to the solution the continuous flows. other words, we seek arbitrarily small global error, also known shadowing. This will be discussed in Theorem 2
3.1.3 NESTEROV-LIKE DISCRETIZATION
First, rewrite Nesterov's accelerated GD as
Tk+1 = Ty + 8yk - 7/ V ((x + + Bykk)
(19a)
Vk+1 T
Tk.
(19b)
where yk as actually applying the discretization given by 199 to the GF ([), i.e. by seeing the term fxx Byk) as mapping applied to the GF flow (1) 2k + Byk. Far (It Byk))
momentum term. We argue that Nesterov's acceleration can be interpreted
5

---

Under review as a conference paper at ICLR 2021
Therefore, given any optimization flow represented by the continuous-time system à F(r), locally convergent to a local minimizer x* E R" cost function f : R" + I, we can replicate Nesterov's
acceleration of (I. More precisely, obtain the algorithm
Tk+1 = 24 + F + Byk) + Byk
(20a)
yk+1 #k+1 - J.k-
(20b)
Based on this idea, propose two "Nesterovlikke' discrete optimization algorithms. The first one based on the g- q-RGF continuous flow, is defined as:
VS(a Byk)
Fk-1 = Ik + n
[Vf(xx + Byx))1 7-7 Byk
(21a)
1k-1 1k+1 T.k
(21b)
The second algorithm is based on the q-SGF continuous flow, and is given by:
1k+1 3k 7 clIV/((x Byn)ll sign(V (a Byn))) Byx
(22a)
Mc++1 2k+1 Ik-
(22b)
3.1.4 CONVERGENCE ANALYSIS
We present here some convergence results of the three proposed discretizations. The analysis summarized in Theorem 2is is based on tools from hybrid control theory, and is detailed in Appendix
Theorem 2. Suppose that f: IR + R is continuously differentiable, locally Ly-Lipschitz, and μ-
gradient dominated of order p E (2, oc) in a compuct neighborhood of strict local minimizer x E S any maximal solution q q-RGF given by (2) or the q-SGF flow (3), there O) such that the solution && of any of the discrete algorithms (77). 118. (27). or (22). with sufficiently small v > O, are c-close to xxt). ie., || xll S c, and s.t. the following convergence bound holds
R" Let 0 and q (p, oo]. Then, for a given initial condition
xtt), z(0) = To. (in the sense of Filippov) to the
exists an arbitrarily small
(**))) [[x))| S T.fe + [(f(z0) ((c00))((xx))) f(x")) 7(1 aa)k)//aa L > 0. k S k*, (23)
0 = p-1 0' 9-1 ē 0 8 where a
1r and k* = (f(mm) ((a))) f(a"))
9
2(1-a)n
Theorem thus shows that that e-convergence of 2g - x can be achieved in finite number of steps upper bounded by k (f(zo) f(a"))(1 This is a preliminary convergence result, which is meant to show the existence of discrete solutions obtained via the proposed discretization algorithms, which are e-close the continuous solutions of the finite-time flows. We also underline here that after 2g reaches an e-neighborhood of x², then Tx+1 R3 Th. vk > k*, since x² is an equilibrium
2(1-a)n
point of the continuous flows; see Definition 2 in Appendix B
MAIN RESULT 2: NUMERICAL EXPERIMENTS
4.1 NUMERICAL TESTS ON AN ACADEMIC EXAMPLE
Let show first on a simple numerical example that the acceleration in convergence, proven in continuous time for certain range of the hyperparmeters, can translate to some convergence accelcration in discrete time, shown in Theorem
2 We consider the Rosenbrock function f 2 )2, with parameters a, b E R. This function
R² + IR, given by x()1,22) = (a ) + b(x2
admits exactly one stationary point (=f x5) (a, a for b 2 0, and is locally strongly convex,
hence locally satisfies gradient dominance order p = 2, which allows us to select g > 2 in RGR
NNot that there might be several ways of approaching this proof. For instance, one could follow the general results on stochastic approximation of set-valued dynamical systems, using the notion of perturbed solutions to differential inclusions presented in Benaim et al. (2005).

---

Under review as a conference paper at ICLR 2021
and q-SGF to achieve finite-time convergence in continuous-ting We report in Figure I the mean performance of all three discretizations for q-RGF and 9 q-SGH with fixed step size for several values of 9, for 10 random initial conditions in [0. 2]. We observe for all three discretizations that, as expected from the continuous flow analysis, for q close to 2, q-RGF behaves similar to GD in terms of convergence rate, whereas for q the finite-time convergence in continuous time seems to translate to some acceleration in this simple discretization method. Similarly for q-SGF, closer to 2 translates less accelerated algorithms, with behavior similar to GD, whereas larger g values lead to accelerated convergence.
tfand sim)
RGF IS comittttiionn arfood stag: Q1Q.3 3)
SCF GOTtNeeters 1o wheed ENp: qnd)
Siicr arfoud ump: Q-4) RCT (Buke Eicrstication
Seestaroe-lg dEc stap coidt
SCP ecteed
107
E Fule reccrettatton whooeeeeeeeee slep soe)
RGG [Kings dicoedzzdoo DMp- 014
RCC
101
607
100
120
200
Figure 1: Example of the proposed discretization algorithms of finite-time R-RGF and g-SGF
4.2 NUMERICAL EXPERIMENTS ON REAL- DATA
We report here the results of our experiments using deep neural network (DNN) training on three well-known datasets, namely, II.ARIO. MNIST, and SVHN. We report results on CIFARIO, and SVHN in the sequel, while results on MNIST can be found in Appendix Note that, we use Pytorch platform conduct all the tests reported in this paper, and do not use GPUs. We underline here that the DNNs are non-convex globally, however, one could assume at least local convexity, hence local gradient dominance of order 2, thus, we will select q 2 in our experiments (see (Remark Appendix E) for more explanations on the choice of 9).
4.2.1 EXPERIMENT ON CIFAR10
In this experiment, we use the proposed algorithms to train VGG16 CNN model with cross entropy loss, e.g., (Simonyan & Zisserman (2015) on the CIFARIO dataset. We divided the dataset into training set spread in 50 batches of 1000 images each, and test set of 10 batches with 1000 images each. We ran 20 epochs of training over all the training batches. Since Nesterov accelerated GD is one of the most efficient methods is DNN applications, to conduct fair comparisons we implemented our Nesterov-like discretization of RGGGF (c = 1, = 3, 0.04, μ 0.9), and the Nesterov- = 3, 0.04, = 0.9). We compare against the like discretization g-FGF (c = 10
"To avoid overloading the figures we had choose flow time, either RGR q-SGF, More results can found in Appendix
'e did multiple iterations to find the best step size for each algorithm (best values where hetween 10-4 and 10 depending the algorithm). Details of the step size for each test given in Appendix F
7

---

Under review as a conference paper at ICLR 2021
mainstream algorithms _ such as, Nesterov's accelerated gradient descent (GD), Adam, Adaptive gradient (AdaGrad), per-dimension learning rate method for gradient descent (AdaDelta), and Root Mean Square Propagation (RMSprop Note that, all algorithms have been implemented in their stochastic version i.e. using mini-batches implementation, with constant step size. For instance, in we the training loss for the different optimization algorithms. We notice that the proposed Algorithms, RGF, and SGF, quickly separate from the GD, and RMS algorithms in terms of convergence speed, but also ends up with an overall better performance on the test set 84% vs. 83% for GD, and RMS. We also note that other algorithms, such as, AdaGrad and AdaDelta behave similarly to RGF in terms of convergence speed, but lack behind in terms of final performance 75% and 68%, respectively. Finally, in Figure 3 we notice that Adam is slower in terms of computation time w.r.t SGF, and RGF, with an average lag min, and 80 min, respectively. However, to be fair one, has to underline that Adam is adaptive method based on the extra computations and memory overhead of lower order moments estimate and bias correction, Kingma & Ba (2015). Furthermore, to better compare the performance of these algorithms, over the learning iterations. We confirm that RGF and SGF performs better than GD, RMSprop, and Adam, while avoiding the overfitting observed with AdaGrad and AdaDelta.
Figures 2 2
report in Figure the loss on the test dataset
SGD-83%
225
SRGF 84%
Acom-84%
2.00
Adam 04%
5RMS-83%
SRMSS-85 83%%
SAdagrad- 75%
175
SAdagrad
SSGF- 84%
SAdadetta--de
Los
150
5SGF -84%
125
1.00
0.75
0.50
200
400
600
1000
100
125
175
200
Training Rerations
Test Iterations
Figure 2: Losses for several optimization algorithms- VGG-16- CIFARIO I0: Train loss (left), test loss (right)- We add S before the name of an algorithm to denote its stochastic implementation.
30
Adam 84%
2.5
20
Traming
1.5
1.0
0.
00
5000
10000
15000
20000
25000
30000
35000
Computation Time [sec]
Figure 3:
Training loss vs. computation time for several optimization algorithms- VGG- 16- CIFARIO
'We run several tests by trying optimally tune the parameters of each algorithms validation set (tenth of training set), and we reporting the best final accuracy performance we could obtain for each one. We have implemented all algorithms with the same total number of iterations, so that we can compare convergence speed of all algorithms against a common iteration range. Details of the Appendix.
values are given in
Original reference for each method can be found in: https///ptorrh.oog/ooosssstaaaat atg/ddcs//tabbleoptii...uu
'We want to underline here that our first tests were done in the deterministic setting, however, to compare the propsed optimization methods against the best optimization algorithms available for DNNs training, we decided also conduct comparison tests in the stochastic setting. Since the results remain qualitatively unchanged, we only report here results due to the stochastic setting.
"To avoid overloading the figures we reported only the computation time plots of the three most competitive methods; RGF, SGF and Adam.
8

---

Under review as a conference paper at ICLR 2021
4.2.2 EXPERIMENTS ON SVHN DATASET
We test the proposed algorithms train the same VGGI6 CNN model with cross entropy loss on the SVHN dataset. We divided the dataset into a training set of 70 batches with 1000 images each, and set of 10 of 1000 images each, and ran 20 epochs of training over all the training batches. We tested the Nesterov-lik, discretization of q- g-RGF (c = 1, q 3, = 0.04, / = 0.09), and the Nesterov-like discretization q-SGF (c 10
= 11, 1j = 0.04, L 0.09) against Nesterov's it is clear that RGF and SGF give good performance terms of convergence speed, and final test performance 93%. We also observe in Figure that SGF, RGF are faster than GD, and all three methods are faster (in average 41 min for GD, 58 min for SGF, 75 min for RGF) than Adam as expected since is an adaptive scheme with more computation steps (see discussion of Adam in Section 4.2.1 More
accelerated gradient descent (GD), and Adan To Note from Figures
Adam
Adam-93%%
150
VMW
SSGF-93%
30
SCD-92%
SCD-92%
25
1.00
wy MM
WPM
20
0.75
15
10
0.50
05
0.25
00
0.00
100
200
300
400
500
600
700
100
200
Training Beertions
Test Rteaaions
Figure 4: Losses for several optimization algorithms CNN- SVHN: Train loss (left), test loss (right)
Adam-53%
30
2.0
1.5
0.5
0.0
5000
10000
15000
20000
25000
30000
35000
40000
Computet
[sne]
Figure 5: Training loss vs. computation time for several optimization algorithms- VGG-16- SVHN
numerical results MNIST, and SVHN using Euler and Runge-Kutta Kutta descretization, showing similar qualitative results, can be found in Appendix
5 CONCLUSION
We studied connections between optimization algorithms and continuous-time representations (dy- namical systems) via discretization. We then reviewed two families of non-Lipschitz or discontinuous first-order optimization flows for continuous-time optimization, namely the q-RGF and q-SGF, whose distinguishing characteristic is their finite-time convergence. We then proposed three discretization methods for these flows, namely a forward-Euley discretization, followed by an explicit Munge-Kuutee discretization, and finally a novel Nesterov-like discretization. Based on tools from hybrid systems control theory, we proved a convergence bound for these algorithms. Finally, we conducted numer- ical experiments on known deep neural net benchmarks, which showed that proposed discrete algorithms can outperform some state of the art algorithms, when tested on large DNN models.
We also tested Adaptive gradient (AdaGrad), per-dimension learning rate method for gradient descent (AdaDelta), and Root Mean Square Propagation (RMSprop). However, since their performance was not competitive decided report the plots avoid overloading the figures.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Hedy Attouch and Jerome Bolte. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming B, 116(1):5-16, 2009.
Andrea Bacciotti and Francesca Ceragioli. Stability and stabilization of discontinuous systems and nonsmooth Iyapunov functions. ESAIM: Control, Optimisation and Calculus of Variations, 4: 361-376, 1999.
Michel Benaim, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 44(1):328-343 2005.
Jérôme Bolte, Aris Danilliiis, and Adrian Lewis. The Łojasiewicz inequality for nonsmooth suban- alytic functions with applications to subgradient dynamical systems. Society for Industrial and Applied Mathematics, 17:1205-1222 January 2007.
C.A Botsaris. A class of methods for unconstrained minimization based on stable numerical integra- tion techniques. Journal of Mathematical Analysis and Applications, 63(3):729-7499 1978a.
C.A. Botsaris. Differential gradient methods. Journal of Mathematical Analysis and Applications, 63 (1):177-198, 1978b.
R.W. Brockett. Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems. In IEEE Conference on Decision and Control, pp. 799-803, 1988.
A.A. Brown. Some effective methods for unconstrained optimization based on the solution of systems of ordinary differential equations. Journal of Optimization Theory and Applications, 62 (2):211-224, August 1989.
Frank H. Clarke. Generalized gradients of lipschitz functionals. Advances in Mathematics, 40(1): 52-67, 1981.
Jorge Cortés. Finite-time convergent gradient flows with applications to network consensus. Auto- matica, 42(1 (9911))1993-000) November 2006.
Jorge Cortés. Discontinuous dynamical systems. IEEE Control Systems Magazine, 28(3):36-73, June 2008
Jorge Cortés and Francesco Bullo. Coordination and geometric optimization via distributed dynamical systems. SIAM Journal Control and Optimization, 44(5):1543 1574, October 2005.
M. Fazlyab, A. Koppel, V. M. Preciado, and A. Ribeiro. A variational approach to dual methods for constrained convex optimization. In 2017 American Control Conference (ACC), pp. 5269-5275, May 2017a.
M. Fazlyab, A. Koppel, V. M. Preciado, and A. Ribeiro. A variational approach dual methods for constrained convex optimization. In 2017 American Control Conference (ACC), pp. 52690-5275, May 2017b.
M. Fazlyab, M. Morari, and V. M. Preciado. Design of first-order optimization algorithms via sum- of-squares programming. In IEEE Conference on Decision and Control (CDC), pp. 4445 4452, December 2018.
Mahyar Fazlyab, Alejandro Ribeiro, Manfred Morari, and Victor M. Preciado. Analysis of optimiza- tion algorithms via integral quadratic constraints: Nonstrongly convex problems. SIAM J. Optim, 28(3):2654 2018.
Aleksei Fedorovich Filippov and M. Arscott. Differential equations with discontinuous righthand sides. Kluwer Academic Publishers Group, Dordrecht, Netherlands, 1988.
G. França, D. Robinson, and R. Vidal. ADMM and accelerated ADMM continuous dynamical systems. July 2018.
G. França, D.P. Robinson, and R. Vidal. A dynamical systems perspective on nonsmooth constrained optimization. arXiv preprint 008.04048, 2019a.
10

---

Under review as a conference paper at ICLR 2021
G. França, J. Sulam, D. Robinson, and R. Vidal. Conformal symplectic and relativistic optimization. arXiv preprint 1903.04100, 2019b.
Uwe Helmke and John Barratt Moore. Optimization and Dynamical Systems. Springer-Verlag 1994.
Qing Hui, Wassim Haddad, and Sanjay Bhat. Semistability, finite-time stability, differential inclusions, and discontinuous dynamical systems having a continuum equilibria. IEEE Transactions on Automatic Control, 54:2465-2470, November 2009.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Polyak-tojasiewicz condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795-811. Springer, 2016.
Diederik P. Kingma and Jimmy Lei Ba. Adam: a method for stochastic optimization. International Conference on Learning Representations, pp. 1-15, May 2015.
L. Lessard, B. Recht, and A. Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM J. Optim, 26(1):57-95, 2016.
S. Lojasiewicz. A topological property of real analytic subsets (in French). Les équations aux dérivées partielles, pp. 87-89, 1963.
S. Lojasiewicz. Ensembles semi-nnnyieeeeeee Centre de Physique Theorique de l'Ecole Polytechnique, 1965. URL https::/pperoo.uiivv rennesl..eeell.... wttpll.ff//mechheeeee wtwpaiceel..cotteeoossiiiieeeeee pdf
StanisLaw Lojasiewicz and Maria-Angeles Zurro. On the gradient inequality. Bulletin of the Polish Academy of Sciences, Mathematics, 47, January 1999.
Michael Muehlebach and Michael Jordan. dynamical systems perspective on Nesterov acceleration. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 4656 4662, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
A. Orvieto and A. Lucchi. Shadowing properties of optimization algorithms. In Neural Information Processing Systems, December 2019.
Bradley Paden and Shankar Sastry. calculus for computing filippov's differential inclusion with application to the variable structure control of robot manipulators. IEEE Transactions on Circuits and Systems, 14, February 1987.
Boris Polyak. Gradient methods for the minimisation of functionals (in Russian). USSR Computa- tional Mathematics and Mathematical Physics, 3:864-878, December 1963.
O. Romero and M. Benosman. Finite-time convergence in continuous-time optimization. In Interna- tional Conference on Machine Learning, Vienna, Austria, July 2020.
R. G. Sanfelice and A. R. Teel. Dynamical properties of hybrid systems simulators. Automatica, 46: 239-248, 2010.
Johannes Schropp. Using dynamical systems methods to solve minimization problems. Applied Numerical Mathematics, 18(1):321-335, 1995.
Johannes Schropp and Singer. dynamical systems approach to constrained minimization. Numer- ical Functional Analysis and Optimization, 21:537-551, May 2000.
D. Scieur, V. Roulet, F. Bach, and A. d' d'ppemmnot. Integration methods and optimization algorithms. In Neural Information Processing Systems, December 2017.
Bin Shi, Simon Du, Michael Jordan, and Weijie Su. Understanding the acceleration phenomenon via high-resolution differential equations. arXiv preprint 1810.08907, October 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference Learning Representations, pp. 1-14, May 2015.

---

Under review as a conference paper at ICLR 2021
J.A. Snyman. A new and dynamic method for unconstrained minimization. Applied Mathematical Modelling, 6(6):448 462, December 1982.
J.A. Snyman. An improved version of the original leap-frog dynamic method for unconstrained minimization: LFOPI(b). Applied Mathematical Modelling, 73):216-218, June 1983.
A. M. Stuart and R. Humphries. Dynamical systems and numerical analysis. Cambridge University Press, 1996.
Andrew M. Stuart and A. R. Humphries. Dynamical systems and numerical analysis. Cambridge University Press, first edition, November 1998.
W. Su, S. Boyd, and E. J. Candes. A differential equation for modeling Nesterov's ' accelerated gradient method: Theory and insights. In Advances in Neural Information Processing Systems, pp. 2510-2518. Curran Associates, Inc., 2014.
Adrien Taylor, Bryan Van Scoy, and Laurent Lessard. Lyapunov functions for first-order methods: Tight automated convergence guarantees. In International Conference on Machine Learning, Stockholm, Sweden, July 2018.
J. Wang and N. Elia. A control perspective for centralized and distributed convex optimization. In IEEE Conference on Decision and Control and European Control Conference, pp. 3800-3805, December 2011.
Andre Wibisono, Ashia C. Wilson, and Michael I. Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences, (13(4)))7751--7738 2016.
A. Wilson. Lyapunov Arguments in Optimization. PhD thesis, UC Berkeley, 2018.
Ashia Wilson, Lester Mackey, and Andre Wibisono. Accelerating rescaled gradient descent: Fast op- timization of smooth functions. In Advances in Neural Information Processing Systems. December 2019.
Abbas K. Zghier. The use of differential equations in optimization. PhD thesis, Loughborough University, 1981
Zhang, A. Mokhtari, Sra, and A. Jadbabaie. Direct runge-kutta discretization achieves acceleration. In Neurul Information Processiny Systems, December 2018.
12

---

Under review as a conference paper at ICLR 2021
A DISCONTINUOUS SYSTEMS AND DIFFERENTIAL INCLUSIONS
Recall that for an initial value problem (IVP)
*(t) F(x(t)) z=0) = 3o
(24a)
(24b)
with F: : R", the typical way to check for existence of solutions is by establishing continuity of F. Likewise, establish uniqueness of the solution, we typically seek Lipschitz continuity. When F is discontinuous, we may understand (24a) as the Filippov differential inclusion
+(t) ([F)()(()),
(25)
where K[F]: IR" = I denotes the Filippov set-valued map given by
x[F((x)
n co F(B(() \ S),
(26)
8>0 ((8)=
where y denotes the usual Lebesgue measure and the convex closure, i.e. closure of the convex
hull Co. For more details, see Paden & Sastry (1987). We can generalize (25) to the differential
inclusion Bacciotti iaccisionBaaciottti & Ceragioli (1999)
a(1) E F(x()))
(27)
where F: R" is some set-valued map.
Definition (Carathéodory/Filipoo solutions). We say that x [0, R with oo is Carathéodory solution to (27) if x=()) is absolutely continuous and (27) is satisfied a.e. in every compact subset of [0, r). Furthermore, we say that xx-) is a maximal Carathéodory solution no other Carathéodory solution æ' (-) exists with = x' [0.r)- If K[F)). then Carathéodory solutions
are referred to as Filippov solutions.
For comprehensive overview of discontinuous systems, including sufficient conditions for existence (Proposition 3) and uniqueness (Propositions 4 and 5) of Filippov solutions, see the work of Cortés (2008). In particular, can be established that Filippov solutions (24) exist, provided that the following assumption (Assumption holds.
Assumption (Existence of Filippov solutions). F: TR" + RD is defined almost everywhere (a.e.) and is meaasuuleeeas in non-empty open neighborhood U IR" of zo E RR. Further, F is locally essentially bounded in U, i.e., for every point r E U, F is bounded a.e. in some bounded neighborhood of
More generally, Carathéodory solutions to (27 exist (now with arbitrary IR), provided that the following assumption (Assumption 2 holds.
Assumption (Existence of Carathéodory solutions). F: R" = Rn has nonempty, compact, and
convex values, and is upper semi-continuous.
Filippoy & Arscott 19888 proved that, for the Filippov set valued map F XCFF., Assumptions !
and are equivalent (with arbitrary 2e E R" in Assumption I.
Uniqueness of the solution requires further assumptions. Nevertheless, we can characterize the Filippov set-valued map in similar manner to Clarke's generalized gradient, as seen in the following proposition.
Proposition 1 (Theorem of Paden & Sastry (1987) ) Under Assumption we have
K[F]()) = { lim F(Fx): Th E Ra (NF US) S.t. 32 + x f
(28)
for some (Lebesgue) zero-measure set NE C Rn and any other zero-measure set S C R In particular, if is continuous at a fixed x, then =[F(())=(F(())) (F))))
=
Thhe notions introduced here are solely needed for rigorously dealing with the singular discontinuity at the equilibrium point of the RGF and SGF flows. However, the reader can skip these definitions and still be able intuitively follow the proofs of Theorems 1, and 2.
13

---

Under review as a conference paper at ICLR 2021
For instance, for the GF 1I. have (())) = [-Vf(x)) for every I E R,, provided that is continuously differentiable. Furthermore, if f is only locally Lipschitz continuous and regular (see (x), where
Definition 3 of Appendix B then
(f lim (Z()) I& E R \W s.t. 26 }
(29)
1--000
denotes Clarke's generalized gradient Clarke 1981 of f. with Ny denoting the zero-mente cero-measure set over which f' not differentiable (Rademacher theorem). can be established that oʃ coincides with the subgradient of f. provided that f is convex. Therefore, the GF (1 interpreted as Filippov differential inclusion may also be seen as a continuous-tima variant of subgradient descent methods.
B FINITE-TIME STABILITY OF DIFFERENTIAL INCLUSIONS
We are now ready to focus on extending some notions from traditional Lipschitz continuous systems to differential inclusions.
Definition 2. We say that x² E T is an equilibrium of 27 if x(() = x* on some small enough
non-degenerate interval is a Carathéodory solution to (27 In other words, if and only if 0 E F(x*) ). We say that (27) (Lyapunov) stable x² E R.n if, for every > 0, there exists some >> such that, for every maximal Carathéodory solution x( of (27). we have || |=0===1| <
|xx(t) ==]))>>[] <
for every 2 0 in the interval where x(-) is defined. Note that, under Assumption 2 if (27) is stable
at x², then x* is equilibrium of (27 Bacciotti & Ceragioli (199)). Furthermore,
say that (27)
is flocally and strongly) asymptotically stable at x E R" if is stable at xx and there exists some ō > 0 such that, for every maximal Carathéodory solution x: [0, r) Rn of (27), if ||: - x*1l then sr)) + x² as - т. Finally, (27) is (locally and strongly) finite-time stable at x² if it is asymptotically stable and there exists some 0 and T' (B(x²)) + [0, oo) such that, for every maximal Carathéodory solution x--) of (27) with To B,(x"), we have lim, (imo) xxt) = x².
We will now construct Lyapunov-based criterion adapted from the literature of finite-time stability of Lipschitz continuous systems.
Lemma 1. Let E() be an absolutely continuous function satisfying the differential inequality
E(t) -c((t
(30)
a.e. in 2 0. with e, E(0) > and a < 1. Then, there exists some > such that E(t) > 0 0. t E ()) and E(t*) = O. Furthermore, t* 0 can be bounded by
8(0)
(31)
c(1 (1
with this bound tight whenever 30 holds with equality. In that case, but now with a 2 1, then (() 0 for every t O, with lim, {() 0. This will be represented by 00, with E(oo & lim Et).
Proof. Suppose that {()) > 0 for every E [0, T' with T > 0. Let (* be the supremum of all such T's, thus satisfying {t) > 0 for every E [0, t"). We will now investigate E(t*). First, by continuity of &, it follows that E(t*) 2 0. Now, by rewriting
d E() aa
é(t) S -tt())
-
(32)
dt
1 -
a.e. in t [0, t)), thus integrate to obtain
E(t) 8(0)1- 1-a
1-a 1-a < -ct,
(33)
everywhere in t E [0, which in turn leads to
8(1) s (8(0)_-a
c(1 - 2/1-))
(34)
and
8(0) 1-a
2 c(1 a)
<
(35)
c(1 a1
14

---

Under review as a conference paper at ICLR 2021
where the last inequality follows from E(t) > 0 for every t E [0) Taking the supremum in (35
then leads to the upper bound (3I). Finally, we conclude that {(t)) = O. since E(t)) > 0 is
impossible given that it would mean, due continuity of &, that there exists some T > t* such that
{() > 0 for every & E [0, T thus contradicting the construction of t*
Finally, notice that if & is such that (30) holds with equality, then 33 and the first inequality
in (35) hold with equality as well. The tightness of the bound (31) thus follows immediately.
Furthermore, notice that if 2 1, and & is tight solution to the differential inequality (30), i.e.
E(t [E(0)] c(1 200 then clearly E(t) 0 for every t 2 0 and E(t - 0 as t 00.
Cortés & Bullo (2055) proposed (Proposition 2.8) Lyapunov-based criterion to establish finite- time stability of discontinuous systems, which fundamentally coincides with our Lemma] T for the particular choice of exponent 0. Their proposition was, however, directly based on Theorem Paden & Sastry (1987). Later, Cootés (2006) proposed a second-order Lyapunov criterion, which, on the other hand, fundamentally translates to Ett & (x)))) being strongly convex. Finally, Hui
al. (200)) generalized Proposition 2.8 of Cortés & Bullo (2005) in their Corollary 3.1, to establish semistability. Indeed, these two results coincide for isolated equilibria.
We now present a novel result that generalizes the aforementioned first-order Lyapunov- bhased results, by exploiting our Lemma| [ More precisely, given Laypunov candidate function V-)), the objective is to set Et) A V(z(t)), and we aim to check that the conditions of Lemma | hold. To do this, and assuming to be locally Lipschitz continuous, we first borrow and adapt from Bacciotti Ceragioli (1999) the definition of set-valued time derivative of V DD - R w.r.t. the differential inclusion 27 given by
(x) {a : 3o E F(x) s.t. a a=
Vp E (v))),
(36)
for each x E D. Notice that, under Assumption 2 for Filippov differential inclusions F = K([F
the set-valued time derivative of V thus coincides with with the set-valued Lie derivative (-)(()) Indeed, more generally V could be seen as a set-valued Lie derivative ==V w.r.t the set-valued map F.
Definition 3. V-)) is said to be regular if every directional derivative, given by
V(x + ho) V(x)
V' b) A lim
(37)
h
exists and is equal to
V(x' + hv) V(x)
V (x;,)) A
lim sup
(38)
h
xf +
known as Clarke's 's upper generalized derivative Clarke 1981
In practice, regularity is a fairly mild and easy to guarantee condition. For instance, it would suffice that V is convex continuously differentiable ensure that it is Lipschitz and regular.
Assumption 3. V D > IR is locally Lipsethiz continuous and regular, with D C R open.
Under Assumption 3 Clarke's generalized gradient
(v A E V' 2 p. Vo e R"}
(39)
non-empty for every x D. and is also given by
(v = lim VV(x)) 26 E R Wy s.t. 3% - 7
(40)
10000
where Ny denotes the set of points C Rnn where V is not differentiable (Rademacher's theorem) Clarke Cloore) (188)).
Through the following lemma (Lemma I. we can formally establish the correspondence between the set-valued time-derivative of V and the derivative of the energy function {(t) ((x(t) associated
with arbitrary Carathéodory solution s(-) to the differential inclusion 27
15

---

Under review as a conference paper at ICLR 2021
Lemma 2 (Lemma of Bacciott & Ceragioli (1999)). Under Assumption 3 given any Carathéodory
solution (0, R" to (27). then E(t) _ V(z(t)) is absolutely continuous and E(t
de v=x(t)) (=()t) a.c. int (0,
We are now ready to state and prove our Lyapunov-based sufficient condition for finite-time stability of differential inclusions.
Theorem 3. Suppose that Assumptions 2 and 3 hold for some set-valued map F : R = RR" and
some function V D - R, where D S In is an open and positively invariant neighborhood of point x² E R". Suppose that V is positive definite w.r.t x² and that there exist constants > 0 and
o < such that
sup (x) S -cV(2))
(41)
a.e. in x E D. Then,
27 is finite-time stable at x², with settling time upper bounded by
V(zo)² 1-a
(42)
c11 a)
where x²0) = mq- In particular, any Carathéodory solution x(-) with xx0) = zo E DD will converge in finite time x² under the upper bound (42). Furthermore, if = R", then (27) is globally finite-time stable, Finally, if V (x) is singleton in x E D and holds with equality, then the bound 42 is tight.
Proof. Note that, by Proposition 1 of Bacciotti & Ceragioli [999), know that (2 is Lyapunov stable at x². All that remains to be shown is local convergence towards x* (which must be an equilibrium) in finite time. Indeed, given any maximal solution [0, + R (27) with
a(0) * x², we know by Lemma 2 that Et) = V(x(t)) is absolutely continuous with E(I) E V (x((t) a.e. in 1. E [0, (*) Therefore, we have
Ê(I) S sup ((x(()) < - -cV(x())) E((
(43)
a.c. in e [0,t*]. Since E(0) = V (zo) > 0, given that xo + x², the result then follows by invoking V( xx()))
Lemma and noting that E(()) = 0
sxtt) x².
Finite-time thite-timmeaa stability still follows without Assumption 2. provided that xx is an equilibrium of (27 In practical terms, this means that trajectories starting arbitrarily close x may not actually exist, but nevertheless there exists neighborhood 'D of x² over which, any trajectory sr-)) that indeed exists and starts x0) = Zig E 'D must converge in finite time to x², with settlng time upper bounded by T(zo) (the bound still tight in the case that holds with equality).
C PROOF OF THEOREM
Let focus on the q-RGF 2 (the case of q-SGF (3) follows exactly the same steps) with the candidate Lyapunov function V f- Clearly, V is Lipschitz continuous and regular (given that is continuously differentiable). Furthermore, V is positive definite w.r.t. x².
Notice that, due to the dominated gradient assumption. x'' must be an isolated stationary point of f. To see this, notice that, x were not an isolated stationary point, then there would have to exist some i* sufficiently near x* such that 3* is both stationary point of f, and satisfies f(ū*) > f*, since xt is a strict local minimizer of f. But then, we would have
0
V
- (
(44)
p
and subsequently 0 0, which is absurd
Therefore, F(x) é -VV [=) [
continuous for every x E D \ {a*}, }. for some small
enough open neighborhood D of x². Let us assume that D is positively invariant w.r.t. ( which can be achieved, for instance, by replacing D with its intersection with some small enough strict sublevel
set of f. Notice that [[(())] <l [+)]| with q E (p, C (1, i.e., --و oo). If
q oc, which results in the normalized gradient flow å [((z) [+((]]
proposed by Cortés (006))
16

---

Under review as a conference paper at ICLR 2021
then |[F())] = c 0. We can thus show that F(x) is discontinuous the other hand, if q E (p. oo) C (1, then we have [IF(()]] + as i + x², and thus F(x) is continuous (but not Lipschitz) at 2 = x². Regardless, we may freely focus exclusively on D {x*) since (x*) | is obviously a zero-measure set.
0 for q cc. On
Let F _ K[ We thus have, for each x E ED) {x*),
sup (zx) sup fa R Eu F(z) s.t. a = u, oV(=))
(45a)
sup (VV :u:0 E F(x))
(45b)
VV(z) F(x)
(45c)
-cllV f()) 3
(45d)
= --IVf(=>|
(45e)
- -c(CU(()- - 2
(45f)
(45g)
Since 0 < 1, given that s 1 s-1 is strictly increasing, then the conditions of Theorem are &r satisfied. In particular, we have finite-time stability at x² with settling time t" upper bounded by
*
t" (f(2o) -r) cCP (1 8
[VVf(z))I/CCa((c ( (1-8)
[ cC (1 +
(46)
0 cC (1
6¹)
for each xo E DD which completes the proof.
D PROOF OF THEOREM 2
To prove Theorem 2 we borrow some tools and results from hybrid control systems theory. Hybrid control systems are characterized by continuous flows with discrete jumps between the continuous flows. They are often modeled by differential inclusions added to discrete mappings to model the jumps between the differential inclusions. We see the case of the optimization flows proposed here simple case of hybrid systems with one differential inclusion, with possible jump or discontinuity at the optimum. Based on this, we will use the tools and results of Sanfelice & Teel (2010), which study how a certain class of hybrid systems behave after discretization with certain class of discretization algorithms. In other words, Sanfelice & Teel (2010) quantifies, under some conditions, how close are the solutions of the discretized hybrid dynamical system to the solutions of the original hybrid system.
In this section we will denote the differential inclusion of the continuous optimization flow by F R² = R","" and its discretization in time by Fa : I² = R.. We first recall definition, which we will adapt from the general case of jumps between multiple differential inclusions (Definition 3.2, Sanfelice & Teel (2010h) to our case of one differential inclusion or flow.
Definition 4. ((T,ee)closeness)) Given T > 0, e <>>0 0, 0, two solutions x2
[0, T7 + R". and
I& : {0, 1, 2, ...} + E= are (I', (Tleeec if:
(a) for all f < T there exists & E {1, 2, ) such that It - kn) < c, and
Ix (t) Iz (k) < C,
(b) for all E (1. there exists f < T such that |t kn) < c, and (t) x& (k) <c
Next, we will recall Theorem 5.2 in Sanfelice & Teel (2010), while adapting it to our special case of a hybrid system with one differential inclusion 1Z
Theorem 4. (Closeness of continuous and discrete solutions on compact domains) Consider the differential inclusion
x(11 F(X())),
(47)
12 A set-valued mapping J IR" = R" is outer semicontinuous if for each sequence {a:) converging to point x E I"" and each sequence yı E F(x:) converging to a point y. it holds that E F(x). It is locally bounded if, for each x R". there exists compact sets K, K' R2 such that K and F(K) & Uzek convex hull, and B denotes the closed unit ball in Euclidean space.
K'. In what follows, we use the following notations: Given set A, conAA denotes the
17

---

Under review as a conference paper at ICLR 2021
for given set-valued mapping F R = R assumed to be outer semicontinuous, locally bounded, nonempty, and with convex values for every x E C, for some closed set C S IR.. Consider the discrete-time system represented by the flow Fa I=" = IR", such that, for each compact set K C R",
there exists E Koae, and 17¹ > such that for each x. E K and each v E (0, n7),
Fa(x) C + conF + p(n) + n)(())
(48)
Then, for every compact set C R", every c > and every time horizon T E R20 there exists 'i" > 0 such that: for any 1 E (0, 1τ"] and any discrete solution with (0) E K + 8B, ó > O, there exists continuous solution &t with (0) K such that ug and It are (T, --close
To prove Theorem 2 we will use the results of Theorem 4 where will have to check that condition (48 satisfied for the three proposed discretizations.
We ready to prove Theorem 2 First, note that outer semicontinuity follows from the upper semicontinuity and the closedness of the Filippov differential inclusion map. Furthermore, local boundedness follows from continuity everywhere outside stationary points, which are isolated.
Now, let us examine their discretization by the three proposed algorithms:
FORWARD-EULED DISCRETIZATION
The mapping Fa in this case is singleton, given by
Fa(x) +
(49)
where 7) > 0, which clearly satisfies condition 48
RUNGE- KUTTA DISCRETIZATION
Once again, the mapping Fa is singleton, this time given by
K
Fa(x) 2 x +
Fly')
(50a)
y¹
B,F(y')
(50b)
j=1
where 7), ai,...,aK,K. .x...... > 0 are such that Σ a; 1.
By equation (50b) one can establish a function p Ko such that for each Fy E K C R" for each 7 > 0, zi Fg + (P(T))B. Next, by equation (50a) together with the condition Σi=k a, = 1, one can write that for any vy E K and v > 0, Fa(xx) C I + nyoon((v))) C a + /conF(rr + m)(n)BB) B.
NESTEROV-LIKE DISCRETIZATION
In this case the discrete-time flow Fa is defined as
Fa(x)) 2% FT + pgy) + pyjk
(51a)
U/ 2g Ik-1-
(5lb)
In this case, to take into account the integral effect of the Nesterov-like discretization, let extend continuous-time flow as
it
)-(
F(x+)
i
(s)ds
(52)
db
7
we then compare the solution the extended continuous-time system time system
52 with the extended discrete-
0 =
Tk+1
)
Ihk +n + 4) + 1) + u(æx xx-11) (1 uu) xx-1) p(ax - xR-1)
=
(53)
F4+1
2kk
18

---

Under review as a conference paper at ICLR 2021
which could be rearranged
Fa(0k) = Øk+1 2k + Max + (.x))
(54)
where 0
F(i+) F(
11+1 and F((Tx)
which shows that for any In K R
and > 0, we have (using similar recursive reasoning above) that Fa(Ea) C C Fi np(r) + BB Then, using Theorem 4 we conclude about the (7, c--losenssssss between the continuous-time solutions of the flows F g-RGF (2) q-SGF (3, and the discrete-time solutions of their respective discretization by any of the three discretization methods. Furthermore, for the Nesterov-like discretization,
also conclude about the (T, closeness of the integral of the continuous time solutions (2) and its discretization (2).
Finally, using the Lyapunov function V == f f as defined in the proof of Theorem together with inequalities (45g). 34). and a local Lipschitz bound on f, one can derive the convergence bound
given by (23). follows:
Sē= Lie, L5 > 0, E> =>0, 0,
[f(x)) (ack)-f(ar f(=")) [(r]]] -(z))l
[f(zk) - f(x²) < E (ff(a))))))...)))))))))))))))))) -((())
[f(xz) - -f(x))
-(x))] S - f(=)) - a)nk) 1/(1aa for k S k.
where a
0 g
0 p- p
9-1 ==
( .k- (f(za) (izz))((2=))(1--
p-
o(-007
E ADDITIONAL DETAILS AND NUMERICAL RESULTS
In this section, we will expand upon the numerical results experiments discussed in the paper. In particular, we report more details on the hyper-parameters values used for the numerical tests, and report some results for the MNIST experiments.
E.1 HYPER PARAMETERS VALUES USED IN THE TESTS OF SECTION 4.1
GD fixed step size: 17 10-3
RGF Euler disc. w/fixed step size: = 2.2, 77 10
RGF Buler disc. w/fixed step size: q 3, 10-2
RGF Buler disc. w/fixed step size: q 6, 10-2
RGF Euler disc. w/fixed step size: q 10, 10-2
GD Nesterov acceleration fixed step size: π 10-4, 4 0.9
SGF Nesterov-like disc. w/fixed step size: g 2.2, 10-4 0.9
SGF Nesterov-like disc. w/fixed step size: q 3, 1) = 10-3, / = 0.9
SGF Nesterov-like disc. w/fixed step size: q = 6, 1) = 10-3 3
/ = 0.9
SGF Nesterov-like disc. w/fixed step size: q = 10, = 10-2 = 0.09
RGF Runge Kutta disc. w/fixed step size: q = 2.2, K = 2, = 10 2, 81 = 0.09, a1 =
022 0.5
RGF Runge Kutta disc. w/fixed step size: q 3, K 2, 1 1 31 0.09, ai
022 = 0.5
RGF Runge Kutta disc. w/fxxed step size: q = 6, K 2, 1 1 3 = 0.09, a1 =
022 0.5
RGF Runge Kutta disc. w/fixed step size: 10, K 2, - 3 0.09, a1
0/2 = 0.5
In all the tests, for q-RGF and q-SGF unless otherwise stated.
19

---

Under review as a conference paper at ICLR 2021
E.2
HYPER PARAMETERS VALUES USED THE TESTS OF SECTION 4.2
Note that the description of the coefficients for each of the prior art methods can be found in: http://yyoochoor/////sssaleliio
GD: r7 = 4.10-², p= 0.9, Nesterov=True
RGF: 1 = 4.10-2
0.9
SGF: 4.10-3 / 0.9
ADAM: 8.10-a (remaining coefficients=nominaal values)
RMS: 10-3 (remaining coefficient=nominnal values)
ADAGRAD: 7/ 10- (remaining coefficients=noninall values) ADADELTA: 7) 4.10- 2 p 0.9, 10-6, weight decay
E.3 MORE TESTS ON THE ROSENBROCK FUNCTION
Due to space limitations, we have decided to report in the main paper only one test for q-RGF with Euler discretization, one test for q-SGF with Nesterov-like discretization, and one for g-RGF with Runge Kutta discretization. For the sake of completeness we report here the remaining tests for each algorithm. One can observe similar qualitative behavior Figure 6 as the one noticed in the results of Section 4.5.
The step-size and other
for each test are given below:
GD fixed step size: 10-3
SGF Fuler disc. w/fixed step size: 2.1, 1/ 10-3
SGF Euler disc. w/fixed step size: 2.5, rj = 10-3
SGF Euler disc. w/fixed step size: 2.8, r 10-3
SGF Euler disc. w/fixed step size: 100, 10-2
GD Nesterov acceleration fixed step size: 1 = 10 4; = 0.9
RGF Nesterov-like disc. w/fixed step size: 2.2, 1] = 10
/ = 0.9
RGF Nesterov-like disc. w/fixed step size: 3, Р 10-3 / 0.9
RGF Nesterov-like disc. w/fixed step size: 6, 10-3
0.9
RGF Nesterov-like disc. w/fixed step size: 10, 1 = 10-3 / 0.9
SGF Runge Kutta disc. w/fixed step size: q 2.2, K 2, 1) 10-3 81 0.09, 01
022 = 0.5
SGF Runge Kutta disc. w/fixed step size: g 3,
2, " = 10 8 0.9, 01
022 0.5
SGF Runge Kutta disc. w/fixed step size: = 6, K 2, 10-2 31 = 0.09, 01
022 0.5
SGF Runge Kutta disc. w/fixed step size: q 10, K 2, 1 81 0.09, a1
02 = 0.5
Remark 2. Choice of q: The settling time upper bound (15) decreases q - co, which appears
lead to faster convergence when discretized. On the other hand, the larger is, the stiffer the ODE, so more prone numerical instability, so g cannot be too large. Therefore. assuming p to be not too large. it appears that E (p. p + 6] works best, with > 0 as small as needed to avoid numerical issues. For instance, if we know the cost function be strongly convex (locally), then we search for q slightly larger than the other hand, we don't know the order > 1, then it's currently unclear how to choose q. will investigate this further in future work. Furthermore, there is evidence that gradient dominance does hold locally in many deep learning contexts (Zhou and Liang, 2017, https://aaaxiv.og/aa/////I 100.). Indeed, since convexity readily leads to gradient dominance of order cc, it suffices that slightly stronger form of it holds (but weaker than strong convexity), in order to have < oc, and thus for us to be able to choose q p.
at first, but continue to increase until performance deteriorates. If, on
20

---

Under review as a conference paper at ICLR 2021
8
180
107
Figure 6: Example of the proposed discretization algorithms of finite-time R-RGF and g-SGF
E.4 EXPERIMENT 3: MNIST CNN MODEL
In this experiment we optimize the CNN network described using a Pytorch code sequence in MODEL 1 with a negative log likelihood loss, on the MNIST dataset.
We use 10 epochs of training, with 60 batches of 1000 images for training, and 10 batches of 1000 images for testing. We tested Algorithm RGF (c 1, 0.9) against Nesterov's 's accelerated gradient descent
3, 7) 0.06, μ 0.9), and Algorithm
2.1, 7 0.06, (GD) (1) = 0.06, μ = 0.9, Nesterov=Trrue), and Adam (17 0.004, remaining coefficients-nominal We also tested other algorithms such as RMSprop, AdaGrad, and AdaDelta, since their convergence performance, as well as, test performance were not very competitive w.r.t. decided not to report them here, to avoid overloading the graphs. In Figures 7 we can see the training loss over the training iterations, where we see that GD, RGF and SGF perform better than Adam in terms of convergence speed (20 sec lead in average), and in terms test performance 98% for Adam, 98% for GD, and 99% for both RGF and SGF. The RGF and SGF perform slightly better than GD in terms of convergence speed. The gain relatively small (5 sec to 10 sec in average) which is expected in such small DNN network (please refer VGG16-CIFARI 10, and VGGI6-SVHI test results for larger computation-time gains). We also notice, in Figure 7 that all algorithms behave well in terms of avoiding overfitting the model.
2 SGF (c 0.001,
values of
GD. this experiment,
99%
ADAM-96%
2.0
ADAM-98N,
S5GF-99%: 99%
SSCF-995 99%
Traning
Lose
0.5
20
30
40
50
Iterations
Berat
Figure Losses for several optimization algorithms- CNN- MNIST: Train loss (left), test loss (right)
21

---

Under review as a conference paper at ICLR 2021
Adam-98% 98%
SRGF-99%
SSGF-999 99%
Training
1.0
100
125
175
Computation Time [sec]
Figure 8: Training loss vs. computation time for several optimization algorithms- MNIST
MODEL 1: MNIST-CNN
class Nc((MNIST-CNN)
def. def..iit.(self)::
super(Net, self).init()
self.convl Conv2d(1, 10, kemnelssize=5)
self.conv2 mw. 2d(02 20, kernel.size=5)
celf.comv2.drop- nn. Dropout2)))))
self.fel = nn. Lin.Linarr(32) 50)
self.fe2 nn. Linearr05550, 10)
forward(self, x):
x = haap://fmma.poo22fffeff..omm 2))
2))
x.view(11, 320)
Frelu(self.feeI()))
x = Edropout(xx, training=self.taanning
= self. fc2())
return F.log. softmaxxf))
E.5 EXPERIMENT 4: EULER DISCRETIZATION SVHN DATASET
the main paper. to space limitation, we decided to report the results the Nesterov-like discretization only, which also seems like fair comparison since our Nesterov-like discretization of R-RGF and q-SGF flows can be compared against Nesterov implementation of GD algorithm. However, we also wanted to test the performance of the simple Euler discretization of the proposed flows against the simple GD algorithm, to do extra tests on the SVHN dataset. These results are presented below.
some
We tested proposed Euler algorithms train same VGG16 CNN model with cross entropy loss. divided the dataset into a training set of 70 batches with 1000 images each, and test set of 10 of 1000 images each, and ran 20 epochs of training over all the training batches. We tested the Euler discretization of q RGF (c q 2.1, 71 0.04, / 0.9), and the Euler discretization of q-SGF (c 10- - q 2.1, ") 0.04, μ 0.9) against gradient descent (GD) and Adam (same optimal tuning as in Section 4.2). All algorithms have been implemented their stochastic version.
In Figures IT we can see that both algorithms, Euler q- RGF and Euler SGSG converge faster (40 min lead in average) than SGD and Adam for these tests, and reach overall better performance the test-set.
E.6 EXPERIMENT 5: RUNGE-KUTTH DISCRETIZATION ON SVHN DATASET
Finally, for compleetness, we also wanted to test the performance of the Runge- Kutta discretization of the proposed flows against SGD, do so we run some extra tests on the SVHN dataset. These results are presented helow.
We tested the proposed Runge- Kutte-KKKtattaa algorithms to train same VGG16 CNN model with cross entropy loss. We divided the dataset into a training set of 70 batches with 1000 images each, and test set of 10 of 1000 images each, and ran 20 epochs of training over all the training batches. We tested the Runge- Kutta discretization
of q-RGF (c 1, q 2.1, K- = 2, 10 81 10 2
01 02 0.5), and the Runge- Kutta
discretization of SGF 10
2.1, K 2,
10
12
8 10 an 02 0.5) against
22

---

Under review as a conference paper at ICLR 2021
Adam 93%
M
Adam-93%%
5RGF-93%
SRGF-93%
SSGF-93%
SGD 92%
SGD-92%
125
Loss
1.00
0.75
0.50
0.2
0.00
200
Training
Figure 9: Losses for several optimization algorithms- SVHN: Train loss (left), test loss (right)
Adam-93%
SRGF-9
SSGF-93%
SGD-92%
Training
5000 10000 15000
20000
25000
30000
35000
40000
Computation Time
Figure 10: Training loss vs. computation time for several optimization algorithms- VGG-16- SVHN
gradient descent (GD) and Adam (same optimal tuning as in Section 4.2). All algorithms have been implemented in their stochastic version.
In Figures 11 12
that both algorithms, Runge-Kurte q- RGF and Runge- Kutta SGF converge faster (40 men lead average) than SGD and Adam for these tests.
Adam-33%
Whh
Adam 93%
SRGF-539
175
SRGF 93%
S5GF-93%
SSGF -3%%
MM
1.00
M
0.75
0.50
0.25
100
200
Figure 11: Losses for several optimization algorithms- SVHN: Train loss (left), test loss (right)
23

---

Under review as a conference paper at ICLR 2021
SRGF-93%
SSGF 93%%993
Training Loss
10000
20000
30000
Computation
[sec]
Figure 12: Training loss vs. computation time for several optimization algorithms- VGG-16- SVHN
24


Reviews:
[{"review_id": "YShzmFQFfk4", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper studies inertial algorithms motivated from discretization of continuous-time systems. The focus of this paper is on rescaled gradient flows and studies three different numerical discretization schemes. The performance of the thus obtained schemes is tested on standard test instances in deep learning. \n\nEvaluation: \nThe paper treats a very important and interesting topic. I very much like the idea of using rescaled gradient flows for optimization problems. However, the scheme described is conceptual in nature as many unexplained hyper parameters play a key role in the optimization and no indication of how to choose these hyper parameters is given. Furthermore, I am missing a discussion with a comparison between the described method and the other first-order methods under the stated gradient-dominance condition. Furthermore, the writing is partly a bit imprecise and I am not quite sure to fully understand the main arguments used in the proof of Theorem 2. If the authors are able to explain this a bit better, then I would be in principle willing to increase my evaluation of this paper. \n\n\nPros: \n+ The analysis of numerical discretization techniques of rescaled gradient flows is a topic that received a lot of attention and definitely is an important subject. \n+ A complexity estimate of the numerical schemes is given. \n+ Numerical results \n+ Detailed technical details are provided in the appendix. \n\nCons: \n- The meaning of Eqs. (6a),(6b) is unclear to me. The map $G$ seems to be not really playing any role in the Examples 1-3. \n- The gradient dominance condition reduces in the case $p=2$ to the well-known Polyak-Lojasiewicz condition. Polyak proved already in 1963 that simple GD features linear convergence under this condition. Attouch-Bolte (2009) generalized this to significantly. These connections are not mentioned at all but are central to the approach here. \n- I don't understand why the algorithms stops once and $\\epsilon$-neighborhood of the solution is reached. Is this a stopping condition in the numerical approach? If so, it must be stated explicitly. Also, do you really mean $\\Delta f(x^{*})=0$ for the equilibrium condition on p. 6? \n- I don't understand why the connection between the numerical scheme and hybrid systems has to be made to prove that approximation property. There is a solid theory of stochastic approximation of set-valued dynamical systems due to Benaim, Hofbauer and Sorin (SIAM J. CONTROL OPTIM. 2005, Vol. 44, No. 1, pp. 328–348) where the needed tubular estimates are provided in quite some generality using the theory of perturbed solutions to differential inclusions. I belief that it is more natural to relate the approximation results to these techniques. However, I might miss this point as the authors write on p. 16 that they consider the dynamics as a hybrid system with a possible jump at the optimum. In my opinion this is an imprecise formulation and should be reconsidered. \n- The methods are not really algorithms but rather conceptual computational schemes. \n- I don’t understand the statement in Theorem 2 why the bound is a „weak convergence statement“. Can you explain this terminology?\n- There is no discussion on the efficiency of the method although gradient dominated functions have been studied in the literature to quite some extend. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JUWNnZhjUVy", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\n### Summary\nThis paper studied two continuous time methods called  rescaled-gradient flow and the signed gradient flow and proposed three efficient discretization, namely the forward-Euler, Runge-Kutta and Nesterov discretization. The paper demonstrated the finite-time convergence of the proposed methods under gradient dominance assumption, and use experiments to show that the proposed methods outperform standard stochastic gradient algorithms in many deep learning tasks.\n\n### Comments\n\nThe paper is clearly structured; the related work in the dynamical systems and control are well presented; experiments are detailed and rigorous, it is good to see detailed report on hyperparameters in appendix.\n\n\nWhile the paper claims that the study is in the context of deep learning, it is unclear to me whether the theoretical analysis is well suited for deep learning models. In particular, the algorithm and main convergence result (Theorem 2) require full gradient. It would be more interesting to show  convergence result for stochastic setting where only mini batch of samples are provided each time. \n\nIn abstract, the paper claims the flows include  non-Lipscthiz or discontinuous system, can the paper give a few examples of such cases? If I understand correctly,  the gradient in example 1 is continuous due to Lipschitz continuity, and the proximal mapping in example 2 is continuous due to nonexpansiveness. \n\n\nThe main result Theorem 2 seems to be problematic. It claims that after finite number of iteration, the iterates $x_k$ will eventually fall in a small $\\epsilon$ neighborhood for some $\\epsilon$ error. However, it does not specify how small $\\epsilon$ is. By using sufficiently large $\\epsilon$, the weak bound is always valid. Can we prove the weak convergence bound (eq. 21) for arbitrarily small  $\\epsilon$?\n\nThe main convergence property is established on the gradient dominance condition (13), which seems to be relatively strong because it requires isolated saddle points. Can the authors elaborate the intuition of (13) for deep learning models?\n\nIn the experiment (Figure 8, appendix) both training loss and testing loss are plotted. However,  it appears that testing loss is much smaller than the training loss. Is it normal or does it have any underfitting issue?\n\nSince the main focus (theory part) is on deterministic setting, to confirm the theoretical finding and  to show the advantage of continuous time methods,  it would be more interesting to compare with Nesterov method or other gradient method for deterministic optimization.  I feel that this work would be more interesting to the field of dynamic control or optimization rather than deep learning.\n\nTypo:\nIn 4.2.2. \n\"Nesterov's Nesterov accelerated gradient descent\" should be \"Nesterov's  accelerated gradient descent\" ", "extra_scores": {}, "extra_text": {}}, {"review_id": "JTFIHnM0twg", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The submission analyzes convergence behavior of three numerical discretizations (forward Euler, explicit Runge-Kutta, and Nesterov-based) of the q-rescaled gradient flow proposed by Wibisono et al. and a variant (q-signed gradient flow), and performs experiments to demonstrate improved convergence speed.\n\n\nThe paper is written clearly, and its relation with prior work is adequately addressed to the best of my knowledge.\nHowever, I also believe that the paper has a few serious drawbacks, which makes it a stretch to include it in the conference in the current form. In general, I feel the submission has the potential in becoming a good paper after some non-trivial updates. \n\n\nThe first issue is with regards to the motivation. After reading the paper, I don’t fully see the benefit that finite-time continuous time convergence provides. What’s more is that the submission does not well motivate the reason to use the particular flows and the techniques of analyses which rely on differential inclusion. \n\n\nThe second issue I’d like to raise is perhaps more important and really is the deal breaker in my opinion. It seems the only new theoretical contribution (i.e. theorem 2) does not provide a converging bound with which a convergence rate can be derived. This is demonstrated by the fact that the authors acknowledge in the theorem that epsilon is chosen, i.e. it cannot be arbitrary. It is also unclear how small a step size eta is required for this bound to hold. Skimming the proof in the appendix, it is clear that the analysis is based on bounding the error between the cont. time solution and the optimum and the error between the cont. time solution and its discrete counterpart. However, it is unclear how the discretization error varies as the step size and number of iterations vary. \n\n\nThe theorem also does not provide any basis to compare the three discretizations, since the same bound is provided, and the same set of assumptions is used for all discretization considered. An ideal analysis would likely distinguish different discretizations based on different assumptions (most likely smoothness of the loss function a la “Direct Runge-Kutta Discretization Achieves Acceleration”), and provide some meaningful non-asymptotic analysis of the magnitude of errors based on characteristics of the discretization. \n\n\nThe experiments section seems well-planned in general. Though the wall-time experiments could be inflating the gains vs Adam, since the first-order and second-order ema moments can be accumulated in parallel on a GPU (and this doesn’t require much effort to implement with standard frameworks, since most dispatches are async.). \n\n\nMinor typos:\nbottom of pg 5: “The analysis summarized in Theorem 2 is based on tools form hybrid control…” form -> from \nmiddle of pg 6: “to achieve finite-time convergence in conitnuous-time” conitnuous-time -> continuous time\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5dlsPVlbII9", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides several discretization strategies for three optimization flows. The main contribution comes from the convergence guarantee for the discrete system.\n1. The convergence guarantee for continuous flow comes from previous work. Moreover, I understand that the author may wish to present the results as general as possible. However, since all the F is continuous and singleton in the main part (if I do not miss some parts), there is no need to introduce the differential inclusion based discontinuous dynamic system, which causes the appendix to be hard to read. All the auxiliary lemmas and theorems have a simple and intuitive version.\n2. Eq. (32) is wrong. The order should be 1/(1-\\alpha). Therefore, so do Theorem 2 also has a similar typo. At the end of page 15, \"Therefore, Bala Bala...\", it should be X \\in D\\\\{x_0} not D\\\\{0}.\n3. In the context of deep neural networks, transferring the convergence guarantee from the continuous optimization flow to the discrete system is quite important. However, this paper does not utilize any detailed information on DNNs; hence it is more like a general optimization paper. Considering there is rich work investigating the discretizations, I can't judge the contribution's significance of this paper.\n4. In the experiment, the format and the resolution of the figures are not consistent.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes three discretization schemes for two first-order optimization flows, and proves the "convergence" to the minimizers of the problem that the optimization flows approach. The methods are tested on the DNN training problem and show comparable performance.

Pros:
1. The problem being studied, the discretization of optimization flows, is of interest to the community.
2. "Convergence" guarantee is provided.

Cons:
1. The theoretical analysis is somewhat preliminary, as the authors have admitted. There is a prescribed \epsilon in the approximation error (23) that prevents the right hand side of (23) from approaching zero. The parameter \eta, depending on the chosen accuracy \epsilon, should be provided so that a user can implement the discretization schemes if s/he is interested. Moreover, by specifying \eta, it may be possible to compare the numbers of iterations to approach an \epsilon-solution between the proposed discretization schemes and other optimization methods for solving the original optimization problem. By doing this, the motivation issue from Reviewer #1 (and the AC) can be resolved. Purely discretizing an optimization flow is of less interest to the machine learning community.
2. Although the comparison on academic problem is obviously advantageous, the comparison on DNN training is only comparable or marginally better. 

The author responses resolved part of the challenges from the reviewers, but the key issues remained (as communicated in confidential comments). Since the final average score is below threshold, the AC decided to reject the paper.
Decision: Reject