First-Order Optimization Inspired from Finite-Time Convergent Flows
Authors: Siqi Zhang
Mouhacine Benosman
Orlando Romero
Anoop Cherian
Venue: ICLR 2022 Submitted (2022)
Keywords: Dynamical systems
continuous-time optimization flows
first-order optimization
DNN applications

Abstract: In this paper, we investigate the performance of two first-order optimization algorithms, obtained from forward Euler discretization of finite-time optimization flows. These flows are 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 propose an Euler discretization for these first-order finite-time flows, and provide convergence guarantees, in the deterministic and the stochastic setting. We then apply the proposed algorithms to academic examples, as well as deep neural networks training, where we empirically test their performances on the SVHN dataset. Our results show that our schemes demonstrate faster convergences against standard optimization alternatives.

Under review as a conference paper at ICLR 2022
FIRST-ORDER OPTIMIZATION INSPIRED FROM FINITE- TIME CONVERGENT FLOWS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we investigate the performance of two first-order optimization al- gorithms, obtained from forward Euler discretization of finite-time timee-time optimization flows. These flows are the rescaled rescaled-gradient flow (RGF) and the signed-gradien flow (SGF), and consist of non-Lipscthiz discontinuous dynamical systems that converge locally in finite time to the minima of gradient-dominated functions. We propose Euler discretization for these first-order finite-time flows, and provide convergence guarantees, in the deterministic and the stochastic setting. We then ap- ply the proposed algorithms to academic examples, well as deep neural networks training, where we empirically test their performances on the SVHN dataset. Our results show that our schemes demonstrate faster convergences against standard optimization alternatives.
INTRODUCTION
Consider the unconstrained minimization problem for given cost function : -> R. When f is
sufficiently regular, the standard algorithm in continuous time (dynamical system) is given by
FFF (2) - fx)
with à ar xx()), known the gradient flow (GF). Generalizing GF, the q-rescaled GF (q-
RGF) Wibisono et al. (2016) given by
Vf(z)
F. (GF(
(2)
[V
with >> 0 and E oo) has an asymptotic convergence rate f(x)
under
mild regularity, for ||x[(0) - x+1 > 0 small enough, where x² E R2" denotes a local minimizer of f-
However, it has been recently proven Romero & Benosman (020) that R-RGF, well as q-signed GF (g-SGF)
i= F Fcr = - (<)] (ign(V((z))
where sign(-) denotes the sign function (element-wise) are both finite-tine timee--tmmme convergent (in continuous- time), provided that f is gradient dominated of order p E (1, q). In particular, is strongly convex, then q-RGF and q-SGF is finite-time convergent for any 9 (2,00), since ʃ must be gradient 2. Considering that many algorithms are inspired from continuous flows
dominated of order with convergence guarantee, e.g., Muchlebach & Jordan (2019) Fazlyab et al. (2017a): Shh al. (2018); Zhang et al. (2018); y França et al. (2019b); Wibisono al. (2016), natural question arises: what the convergence rate of the corresponding discrete time algorithms, which are induced by discretization of finite-time time convergent continuous- sameinuuuu-time flows?
1.1 CONTRIBUTION
In this paper, we investigate the convergence behavior of an Euler discretization for the R-RGF (equa- tion and q-SGF (equation 3). We provide convergence guarantees in terms of closeness of solutions, using results from hybrid dynamical control theory. Furthermore, we provide iteration sample complexity upper bounds for both the general (deterministic) and stochastic settings. We then test the performance of the proposed algorithms on both synthetic and real- world data in the context of deep learning, namely, on the well-known SVHN dataset.

---

Under review as a conference paper at ICLR 2022
1.2
RELATED WORK
Propelled by the work of Wang & Elia (011)) and Su et al. (2014), there has been a recent and
significant research effort dedicated amalyzing optimization algorithms from the perspective of dynamical systems and control theory, especially in continuous time (Wibisono et al. 2016 Wilson
2018 Lessard et al. 2016 Fazlyab et al. 2017b Scieur et al. 2017]] Franca et al. (0.8) Fazlyab et al.
2018 Fazlyab et al., 2018 Taylor et al. 2018; França et al. 2019a Orvicto & Lucchi, 2019; Romero
ct al. 2019; Muchlebach & Jordan 2019). A major focus within this initiative is in accceleration,
both terms of 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 [2099] Fazlyab et al.) 7a017a Shi et al. 2018 Zhang et al.] 2018: França et al. [2019] 9b] Wilson et al. 2019). Many of these papers also focus on deriving convergence rates based on the discretization of flows designed in the continuous- time domain.
Connecting ordinary differential equations (ODEs) and their numerical analysis, with optimization algorithms is very important topic, which can be dated back to 1970s, see [Botsrii (1978a b);
Zghier (198T); ); |Snyman [1982] 1983); Brockett (1988;; Brown (1989). In [eelmee & Moore (1994). the authors studied relationships between linear programming. ODEs, and general matrix theory. Further, Schroopl (1995) and Schropp & Singer| 2000) explored several aspects linking nonlinear dynamical systems to gradient-based optimization, including nonlinear constraints.
Tools from Lyapunov stability theory are often employed for the analysis, mainly because there already exists rich body of works 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) at an isolated extremum of the given cost function, thus certifying local convergence. Naturally, the global asymptotic stability leads to global convergence, though such analysis will typically require the cost function to be strongly convex everywhere.
For physical systems, Lyapunov function 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, (xx) (xx - f(==) can be a good initial candidate. Further, if ʃ is continuously differentiable and xt is an isolated stationary point, then another alternative is Vix) [+f())]
However, most fundamental and applied research conducted in systems and control regarding Lya- punov stability theory deals exclusively with continuous-timg systems. Unfortunately, (dynamical) stability properties are generally not preserved for simple forward-Eiu and sample-and-holl dis- cretizations and control laws (Sturrt& & Humphries 1998). Furthermore, practical implementations of optimization algorithms in modern digital computers demand discrete-time. Nonetheless, has been extensively noted that a vast amount of general Lyapunov- basedd results (perhaps most) appear to have a discrete-time equivalent.
2 PRELIMINARIES
2.1 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
*(1) E F(x(())
(5)
a.e. t 0 (e.g. g. for the q case), such that artt + x² as t + t*. In the case of the R-RGF ( and SGF (3) for f gradient dominated of order p E (1, g). we have mitee-time convergence, and thus /* (1)) < co.
2

---

Under review as a conference paper at ICLR 2022
Most of the popular numerical optimization schemes can be written in state-space form (i.e., recursively), as
X&+1 = Xx) 3 G(Xx)
(6a)
(6b)
for & Σ4 - (0,1,2,,..) and given Xo E Rn (typically m 2 n)), where Fa 24 R and G _ + =..
R
Naturally, 6 be seen as discrete-time dynamical system constructed by discretizing 4 in time. In particular, we have Fg = r(fx), where {0 to < t < t2 < <...} denotes time partition and
ax-) solution to (4) or (5) as appropriate. Therefore, we call X₂ and 2x. respectively, the state and output at time step k.
Example The standard gradient descent (GD) algorithm
Øk+1 = 2 7/ f(xx)
with step size (learning rate) > 0 can be readily written in the form (6) by taking m (x r 7V f(z), and G(x) A x.
If the step sizes are adaptive, i.e. if we replace 7 by sequence {me) with m7s 0, then we only need to replace (a x) ê x m/e fx), provided that {mF } computed using feedback from { (e.g. through line search method).
If we do wish to use vary-ngrying step-size, then we can set m - n + 1, G( n)) A x, and Fa([2;; n]) _ [E( ([æ; n]); F/ ([x; n])] where Fá ([z; x 1)V f()), and F( is user-defined function that dictates the updates in the step size. particular, an open-loop adaptive step size } may be achieved under this scenario, provided that it is possible to write M F( (m))
If we wish to use individual step sizes for each the n components of {zx}, then it suffices to take 7/ n-dimensional vector (thus m 2n), and make appropriate changes in Fa and G.
In each of these cases, GD can be seen as a forward-Fuler discretization of the GF ie.
Z++1 + FtrFFr(
(8)
with FGF = f and adaptive time step At - tx+1 tu chosen as Atk Tjk-
Example 2.
The proximal point algorithm (PPA)
Tk+1 = arg min =ER*
f(x) +
|| xx11
(9)
2TT
with step size > 0 (open loop, for simplicity) can also be written in the form (6. by taking = Fa x) 2 arg min (z') + 1 |2' - =11)), and G(z) x. Naturally, we need to assume sufficient regularity for Fa 2) to exist and must design consistent way choose Fa when multiple minimizers exist in the definition of Fa z). Alternatively, these conditions must be satisfied, the very least, every (k,,x) E {(0, 20), (1, 11,)),, (2,x2),... for particular chosen initial Zi E IR..
2ne
By assuming sufficient regularity, have (z(((x) + 27/u || FA 111) -=1+11 0. and thus
1
V (((=+1) + - (2R+1 I1)
Øe41 + Ale Fer
(10)
7jk
with Ale Tj. which is precisely the backward-Fuler discretization of the GF
2.2 CONTINUOUS-TIME CONVERGENCE OF R-RGF AND SGF
In this section, we review the necessary conditions to ensure inite-time convergence of these flows. Here the hyperparameter > 0 in equation 2 and equation B will not be explicitly denoted in
FG-RGP; F, FGS Next, borrowing terminologies from Wilson et al. (019). we define the notion of gradient dominance with order p following.
3

---

Under review as a conference paper at ICLR 2022
Assumption 1 (Gradient Dominance of Order p). For a continuously differentiable function f. assume the function f is u-gradiient dominated of order p E (1, ooj (1 > 0), i.c.
p P
[Vf(())
(fa)
YEER".
(11)
where x= E arg min f(x) is the local minimizer, also we denote the optimal value s" f(x)).
Remark 1. It can be proved that continuously differentiable strongly convex functions are gradient dominated of order p 2. In fact. gradient dominance is usually defined exclusively for order y = 2, often referred to the Polyak-L.ojsieewiz (PL) inequality, which was introduced by PPolykk (1963) to relax the (strong) convexity assumption commonly used to show convergence of the GD algorithm ( The PL inequality can also be used to relax convexity assumptions of similar gradient and proximal- -gandintt methods (Karimi et al. 2016 Attouch & Bolte 2009). Furthermore, if is gradient dominated (of any order) w.r.t. x², then x= an isolated stationary point of f.
Our adopted generalized notion of gradient dominance is strongly tied to the Lojasiewicz gradient inequality from real analytic geometry, established by /Loasiewicz (1963 1965 independently and simultaneously from Polyak (1963), and generalizing the PL inequality. More precisely, this inequality is typically written as: for some C and 0 E (2 1].
[V)(2)22 > C (f((())-1)))
(12)
holds for every E R" in small enough open neighborhood of the stationary point x², This inequality is guaranteed for analytic functions Lojasiewicz (965). More precisely, when x is a local minimizer of f. the aforementioned relationship is explicitly given by
C
P p
p P-1
(13)
Therefore, analytic functions are always gradient dominated. However, while analytic functions are always smooth, smoothness is not required to attain gradient dominance. Also recently it is shown that in reinforcement learning, the value functions with softmax parameterization satisfies the above condition (Mei et al. 2020 2021). which further rationalizes settings.
The following results in Romero & Benosman 2020) summarized the finite-time convergence of q-RGF (equation topic in this paper.
[ and g-SGF (equation 3h in continuous-ting sense, which also motivates the main
Theorem 1 (Romero & Benosman (2020). Suppose that RR + R is continuously disferentiable and u-gradient dominated of order E (1, 00) near a strict local minimizer x² E IR.". Let e >> 0 and q E (p, 20). Then, any maximal solution z(-). in the sense of Filippov, to the R-RGF (2) SGF will converge in finite time to xx, provided that [|x(0) - x 1=1 > is sufficiently small. More precisely,
lim x(t)= x², where the convergence time t* < may depend on which flow is used, but in both
cases is upper bounded by
V f((o))) cC d
c"
(14)
where xo = x0), C-
8-1 (
1 1
and 0' = 9-1 In particular, given any compuct 9
and positively invariant subset S C D, both flows converge in finite time with the aforementioned convergence time upper bound (which Furthermore, D = RR. then we have global finite-time convergence, i.e. finite-tmme convergence to any maximal solution (in the sense of Filippov) x(.)) with arbitrary Tog E R
be tightened by replacing D with S) for any To S.
In essence, the analysis introduced in Romero & Benosman (002) consists of leveraging the gradient dominance to show that the energy function E(t) & f(x(t)) f satisfies the Lyapunov-like differential inequality E()) ((((())) for some 1. The detailed proof is recalled in Appendix for completeness.
For modern treatments English, Lojasiewicz & Zurro 1999 Bolte al. 2007
4

---

Under review as a conference paper at ICLR 2022
3 MAIN RESULTS: CONVERGENCE ANALYSIS FOR EULER DISCRETIZATION
With the previous discussion on continuous-time gradient flow, now we turn to the algorithm perspec- tive. We propose the following general framework based on forward Euler discretization of the flows with finite-time convergence guarantee.
Fk+1 = TA + (Tx)) <> 0
(15)
where F { Fq-SCFJ. We will show later, in Theorem 2 that the simple method leads, for small enough > O, to solutions that are (cllos to the continuous-time flows. Also with a little abuse of notations, we will still use RGF/SGF to call the discrete- time algorithms induced by their corresponding continuous-timg time flows if the context is clear.
3.1 CLOSENESS OF THE DISCRETIZATION
We present here some convergence results of the proposed discretization. We first start with a proximity analysis, which aims at showing the closeness between the solutions of the continuous flows and the trajectories of their forward Fuler discretization.
Theorem 2 (Closeness of Discretization). Suppose that f RR" - R. is continuously differentiable, locally Lipischhitz, and u-gradient dominated of order p E (1, oo) in a compact neighborhood S
of strict local minimizer x² E TR... Let > O and E {p. oo). Then, for given initial condition To E S, any maximal solution z<t), xx0)= = To. (in the sense of Filippov) to the q-RGF given by (2) or the q-SGF flow (3, there exists arbitrarily small > 0 such that the solution I& of any of the
discrete algorithm (15), with sufficiently small 7) > O, are e-close to x(t), i.e. || - xtt]l2 S foo
It knl < c, and the following bound holds
(1(())) f(xx)())= 112 L [F((x) f(xt)) ē(1 annt
(1-a)
L 0, k ks
(1(())) - f(x))(())))))) lll S Tife, k> k*,
(16)
where a = 1, = p=1 p
0'
_ q ē=c (((((2))
and k*
(f((m))-fi) [(=")) ()
6(1-a))
The analysis summarized in Theorem 2 is based tools form hybrid control theory, and is detailed in Appendix Theorem shows that c-covergeecce of ø4 - x* can be achieved in a finite number of steps upper bounded by k- (f(zo)=((x')))
This a preliminary convergence result aiming to show the existence of discrete solutions obtained via the proposed discretization algorithms, which e-close the continuous solutions of the finite-time flows. We also underline here that after zak reaches an c-neighborhood of x", then Tx-1 R Tk, Vk > k", since x² is an equilibrium point of the continuous flows, i.e., Af = 0, e.g. see Definition 2 in Appendix B
2(1 8(1-a))
3.2 CONVERGENCE RATES OF EULER DISCRETIZATION: GENERAL CASE
However, the bound 16) does not allow to have constructive practical value of the stepsize 7, since the pair (e, 7) are implicitly related, for 'sufficiently small' y) (refer to the definition of e-closeness and the proof of Theorem 2 in Appendix D). To derive convergence rates of the proposed discretization with practical stepsize 77. we need to introduce an extra assumption of L-Lipschitz smooth, as presented below.
Assumption 2 (Lipschitz Smoothness of Order q). We assume the function / is L-Lipschitz smooth of order q E (1, 2]. i.e., for any x, y E R."
(v)))~ ( S Dlyy - -
(17)
Remark 2. The smoothness assumption is a very common setting in optimization algorithm literature (Nesterov 2003 Beck 2017). This assumption above is also called as (I, -Hödder continuity
"Note 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).
5

---

Under review as a conference paper at ICLR 2022
(Devolder et al. 2014 Nesterov 2015), it easy to find that the condition will lead to the following property:
((v) S f(x) (V/(²), + 11-
(18)
which is also called weak smoothness. When y = 2, the function will be Lipschitz smooth, so the above setting is generalization of the common Lipschitz smoothness.
With these setting, now we will start our discussion from the general case, i.e., we have the access to the true gradient V fx)) The main result presented in the following theorem, while we defer the proof to Appendix
Theorem (Convergence Rate of the general Casc). Suppose that f: R" + R. is continuously dif- ferentiable, u-gradient dominated of order q and L-Lipschitz smooth of order q following Assumption 1 Iand then running q-RGF (equation 2 and equation 15) for K iterations with a stepsize 1) -
satisfies that
f(zk) f (1=(11111 kin (f(zo) - f)),
(19)
and running q-SGF (equation 3 and equation 15) for K iterations with = (nL) satisfies that
f(xk) - fr (11-((())) (t)
K
(nx(x)
((1oo)-f7
(20)
where n. is the dimension number and i. A 4. 0( (K In and ((n*)) In !). respectively.
The corresponding iteration complexity are
Remark 3. The above results show that with a constant stepsize, both the q-RGF and g-SGF can attain linear convergence rate to reach the optimal point. Note that for the classical Lipschitz smooth
case (i.e. = 2), the RHS of the RGF result (equation 19) will reduce to (1 - x 1) (f(z) - f*).
which is the same as that in (Karimi et al. 2016 Theorem I); while for SGF (equation 20 it will be
(1 11) (f(z)) - f*), which recovers the result in (Beznosikov et al. 2020 Theorem 13
So conclude that our results extend the classical results in Lipschitz smoothness case.
3.3 CONVERGENCE RATES OF EULER DISCRETIZATION STOCHASTIC CASE
Attaining the full gradient may be expensive in practical applications due to the large data size, while stochastic optimization algorithms are more applicable such cases (Robbins & Monro 1951] Bottou et al. 2018). So now we turn to discuss the complexity results when we have only the access to the unbiased estimator of the gradient. To formalize the discussion, we impose the following assumption on the gradient estimator, which is very common in stochastic optimization literature (Ghadimi Lan 2013 Bottou et al. 20188...
Assumption (Unbiased Gradient Estimator). For any given æ E R", assume to have only the access of the unbiased gradient estimator, denoted as g(x; where & is a random variable, while we assume that it satisfies that T. [g;;; {)] = (z)),, Rellg(a; v fx)) < o².
Stochastic RGG We present the convergence result stochastic RGG in the following theorem, and defer the proof to Appendix For convenience, we denote 1) 2 بي [o0).
Theorem (Convergence Rate of the Stochastic RGF). With the setting in Theorem 3 if we fur- IR,, we only have access the unbiased estimator the gradient in
ther assume for each Assumption then if we replace the gradient in q-RGF (equation 2 by its unbiased estimator
b(()) g(x) 1= g(x;; Es) with batch size b(x) E N Then for R-RGF (equation 2 and equation 15
3
with (()), if we set - Mxx) =
then we have
2
E[f(xk) 5r]
-1)
(21)
(2
Note that || " f(x)) is an d-approximate compressor of gradient Vf(x)) Karimireddy Theorem 13) recover the result.
2019) so we can apply [Beznosikov 2020

---

Under review as a conference paper at ICLR 2022
Stochastic q-SGF The analysis of the Euler discretization of q-SGF in the stochastic case is bit more complicated. Indeed, note that previously our discussion are based on fn-norm. Here, however, following the argument in Balles al. (2020), we change the gradient dominance and Lipschitz smoothness assumption to hold in -nomm (and its dual norm &1)
Assumption (Gradient Dominance and Lipschitz Smoothness under (41, Loo -nnoms), We assume the function f is j-gradient dominated of order q and I--L.pschitz smooth of order y under lo -nom (and its dual norm (1), i.e., for any 2; y E I
g - 1 - 2
IV - V - Lly =11.=t
(22)
Similarly the new smoothness condition above implies that f(y) S f(x) + (VI()),y x) L lly =Il (V z, y E ). And for the gradient estimator, we need the following assumption.
Assumption (SPB Unbiased Gradient Estimator (Safaryan & Richtárik, (021]). For any given E R", we assume have only the access of the unbiased gradient estimator under -n-ormm i.e.,
Eg(g(<; {)] = f(x), Eg (2g {) f l S o²; and for its mini-batch version g(z) with batch size b()), we further assume that it satisfies success probability bounds (SPB) property, i.c., for each component of g(x) and V (x) (denoted as (a()) and (r)( we have 3y E ((2, 1] such that
Psiggn (V,f(z)) sign (g,(z))) 2 p' 2' ViE (1,2,-...10 .n..
(23)
Remark 4. Note that similar assumptions under loo norm (and its dual norm ε1) are widely adapted in the literature of sign-based algorithms, e.g., Karimi ct al. Bernstein et al. (2018s) Sa b); Balles
eet al. 2020). Here the extra SPB assumption, proposed in Saaaaryan & Richtárik (2021). 1), very
important in the convergence analysis of stochastic sign-based algorithms. An intuitive understanding to justify SPB is that, with a large batch size, the output estimator g(z) will be very similar to V fx), so the corresponding probability above should be higher. For more details on the rationality of the assumption, we refer the reader to Safaryan Richtárik (2021) for further discussions.
With the above preparation, we summarize the result of stochastic SGF in the following theorem, while deferring the proof to Appendix G
Theorem 5 (Convergence Rate of the Stochastic SGF). Suppose the function f satisfies the setting in Assumption 4 above, then for q-SGF (equation 3 and equation (5) with an unbiased gradient estimator g(x) of butch size b(x) N we assume the gradient estimator g(x) satisfies Assumption
and sel 1)
12"-1
and b(xx)
T-g
02,, it satisfies that (2p²
qe
E[f(xx)= - fr1 (1- (2p" 1)ah(a1 (120 1) (f(zo) - f E
(24)
Remark 5. The results in Theorem 4 and Theorem 5 shows that both stochastic RGF and SGF will drive the function value to linearly converge to the -eighbooooooroooo of the optimal value. As comparison on stochastic RGF, Lei et al. (2019) studied the convergence guarantee of stochastic gradient descent (SGD), which can be viewed as stochastic 2-RGF, under similar setting. Also for stochastic SGF, we notice that recently Li et al. (202T) provided similar convergence result of stochastic SGF in the classical setting (i.e., g 2), their result also requires an lower bound on the probability of estimation correctness, which corresponds to the SPB assumption above. Our result can be viewed as extension of their work.
4 NUMERICAL EXPERIMENTS
In this section, we will use several experiments to verify the effectiveness of our proposed algorithms, more details will be presented in Appendix H
4.1 NUMERICAL EXPERIMENTS ON ACADEMIC EXAMPLES
Let show first simple numerical example that the acceleration in convergence, proven in continuous time for certain range of the hyperparmeters, can translate to some convergence acceleration in discrete time.
7

---

Under review as a conference paper at ICLR 2022
Example 1
Consider the following function: f: :R + R and f(x) & 1 1/1l", which can be shown to
g
be (g- 1)s-1--ree gradient dominated of order q, and 2-Lipschitz smooth of order q when 1 < q S Lei
& Ying 2020 Romero & Benosman 2020). Here we set q 1.95 for the objective function. The test results of the proposed RGF and SGF algorithms compared with other algorithms is presented in Figure I below. The figure shows both sensitivities to stepsizes and performances of algorithms, measured by the optimality gap [(x) - f" where I is the optimal value which is O. We can find that q-RGF and q-SGF, comparing to the classical one (2-RGF) and over-large one (10-RGF), can accommodate larger stepsize and attain better performances with the best-tuned stepsize ! Also we further plot the theoretical bounds provided in Theorem [ (in red), we can find that the proposed algorithms attain linear convergence patterns and their optimal stepsize choice is close to those in Theorem so the experiment results matches the theory well the example.
RGF, Performance Stopdizes, e-1.5
Parforancee Alger tims, g=1.95
10-11
10
10 10-101
10 -M4
10 20-
110-3u
10
10
10 10-
10-21
10.00
107
10"
200
400
600
800
1.00
Steoslbe
Boraiton
merfo Steasiees,
SGF, Performance Each Algoriamm q=1.95
10-91
20 119
210-1k
1.-13
10-77L
10-10
$10-
10-10
10-10.
3007
39007
Thapnen
Stepsizee
Tteration
Figure 1: Results of discretization of RGF and SGF with different q on Example
We consider the Rosenbrock functionf: RR2 + IR, given by f(x1, x22) = (a (a-x)) x1)²² b(x² x²)², with parameters a, E R., which is locally Lipschitz smooth. This function admits exactly one stationary point (xj,=)) .r²) (a, a²) for b 2 0, and is locally strongly convex, hence locally satisfies gradient dominance of order p = 2, which allows us to select y > 2 in g-RGF and q-SGF to achieve finite-time convergence in conitnuous-time We report in Figure the mean performance of forward-Eulle discretization for q- RRG and SGFG with fixed step siz for several values of q, for 10 random initial conditions in [0, We observe that, expected from the continuous flow analysis, for g close to 2, q-RGF behaves similar to GD in terms of convergence rate, whereas for q >>> 2 the finite-time convergence in continuous time translates to some acceleration in the associated discretization algorithm as well. Similarly for 9-SGF, g closer to 2 translates to less accelerated algorithms, with a behavior similar GD, whereas larger q values lead to accelerated convergence.
Example 2
4.2 NUMERICAL EXPERIMENTS ON REAL-WORLD DATA
We report here the results of our experiments using deep neural network (DNN) training on the SVHN dataset. Note that, we use PyTorch platform to conduct all the tests reported in this paper. Both CPU and GPU tests have been performed. The results reported in this section are CPU tests, whereas GPU tests reported in Appendix H We underline here that the DNNs 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 7 Appendix H) for more explanations on the choice of g).
* 'The experiment results show that q- RGG and 9FF will drive the function value exactly 0 with certain stepsizes, which generates plots that may exceed the lower limit in figures.
We did multiple iterations to find the best step size for each algorithm (best values where hetween 10-4 and 10 2 depending the algorithm). Details of the step size for each test given in Appendix H
8

---

Under review as a conference paper at ICLR 2022
peptiisee Eul Eoa vilution
Figure 2: Results of Discretization of RGF and SGF with Different on Example 2
4.2.1 EXPERIMENTS ON SVHN DATASET
We test the proposed algorithms to train the same VGG16 CNN model with cross entropy loss the SVHN dataset. We divided the dataset into training of 74 batches with 1000 images each, and test set of 27 batches of 1000 images each, and ran 20 epochs of training over all the training batches. We tested the discretization q-RGF (c 1, q 2.1, 77 0.04), and of q-SGF 2.1, 7) 0.04) against classical gradient descent (GD), and Adam 0 Note from clear that q-RGF and q-SGF give good performance in terms of convergence speed, and final test performance 93%. We can also observe in Figure 4 that q-SGF, and g-RGF converge faster (40 min lead average) than SGD and Adam these tests, and reach an overall similar performance the test-set. Additional numerical results, including GPU runs, can be found in Appendix
10
Figures 3
Inhyy
00%
0.15
0.0
013
Figure Losses for several optimization algorithms- SVHN: Train loss (left), test loss (right)
Figure 4: Training loss vs. com- putation time for several opti- mization algorithms- VGG-16- SVHN
5 CONCLUSION
We presetned some connections between optimization algorithms and continuous-time representa- tions (dynamical systems) via discretization. We then reviewed two families of non-Lipschitz or discontinuous first-order optimization flows for continuous-time optimization, namely the q- RGRGF and g-SGF, whose distinguishing characteristic their finite-time convergence. We then proposed forward Fuler discretization of these flows. Based on tools from hybrid systems control theory, we proved a closeness convergence bound for these algorithms, and then proposed several convergence rates in the deterministic and the stochastic setting. Finally, a known deep neural network benchmark, which showed that the proposed discrete algorithms can outperform some state of the art algorithms, when tested large DNN models.
conducted numerical experiments on
'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 2022
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.
Lukas Balles, Fabian Pedregosa, and Nicolas Le Roux. The geometry of sign gradient descent. arXiv preprint arXiv:2002.08055 2020.
Amir Beck. First-order methods in optimization. SIAM, 2017.
Michel Benaïm, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 44(1):328-348, 2005.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pp. 560-569. PMLR, 2018a.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote communication efficient and fault tolerant. arXiv preprint arXlv:1810.05291, 2018b.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002.124/ 12410, 2020.
Jérôme Bolte, Aris Danillidis, and Adrian Lewis. The Lojasiewicz inequality for nonsmooth suban- alytic functions with applications to subgradient dynamical systems. Society for Industrial and Applied Mathematics, 17:1205-1223 January 2007.
C.A Botsaris. A class of methods for unconstrained minimization based stable numerical integra- tion techniques. Journal of Mathematical Analysis and Applications, 63(3):729-749, 1978a.
C.A. Botsaris. Differential gradient methods. Journal of Mathematical Analysis and Applications, 63 (1):177-198, 1978b.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223 311, 2018.
R.W. Brockett. Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems. In JEEE 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(11):1995 1991)):993-0000, 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 on Control and Optimization, 44(5):15331154, October 2005.
Olivier Devolder, François Glineur, and Yurii Nesterov. First-order methods of smooth convex optimization with inexact oracle. Mathematical Programming, 146(1):37-75,, 2014.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: near-optimal non-convex optimization via stochastic path integrated differential estimator. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pp. 687-697, 2018.
10

---

Under review as a conference paper at ICLR 2022
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. 2269-5275, May 2017a.
M. Fazlyab, A. Koppel, 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-2683 2018.
Aleksei Fedorovich Filippov and F. M. Arscott. Differential equations with discontinuous righthand sides. Kluwer Academic Publishers Group, Dordrecht, Netherlands, 1988.
Guilherme Franca, Daniel Robinson, and Rene Vidal. Admm and accelerated admm as continuous dynamical systems. In International Conference Machine Learning, pp. 1559-1567. PMLR, 2018.
G. França, D.P. Robinson, and R. Vidal. A dynamical systems perspective on nonsmooth constrained optimization. arXiv preprint 1808. 04048, 2019a.
G. França, Sulam, D. Robinson, and R. Vidal. Conformal symplectic and relativistic optimization. arXiv preprint 1903.04100, 2019b.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal Optimization, 23(4):2341 1-2223111-66,,, 2013.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2): 2016.
Uwe Helmke and John Barratt Moore. Optimization and Dynamical Systems. Springer-Verlage 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-24777 November 2009.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the bojyak-tojasiewwic condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Dutabases, pp. 795-811. Springer, 2016.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pp. 3252-3261. PMLR, 2019.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. International Conference on Machine Learning, pp. 5809-5819. PMLR, 2020.
Yunwen Lei, Ting Hu, Guiying Li, and Ke Tang. Stochastic gradient descent for nonconvex learning without bounded gradient assumptions. IEEE transactions on neural networks and learning systems, (304)443444440, 2019.
L. Lessard, B. Recht, and A. Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Optim, 26(1):57-95, 2016.
Xiuxian Li, Kuo-Yo Yi Lin, Li Li, Yiguang Hong, and Jie Chen. On faster convergence of scaled sign gradient descent. arXiv preprint 209.:200 2021.
S. Lojasiewicz. A topological property of real analytic subsets (in French). Les équations aux dérivées partielles, pp. 87-89, 1963.
11

---

Under review as a conference paper at ICLR 2022
S. Lojasiewicz. Ensembles semi-analytiquus. Centre de Physique Theorique de l'Ecole Polytechnique. 1965. URL Stip:s//parsooouuiieeeeeeeee... http://aaccccl..oooooooaoaaaaaae pdf
StanisLaw Lojasiewicz and Maria-Angeles Zurro. On the gradient inequality. Bulletin of the Polish Academy of Sciences, Mathematics, 47, January 1999.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pp. 6820-6829, PMLR, 2020.
Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non non-uniformity in first-order non-convex optimization. arXiv preprint arXiv:2105.06072. 2021.
Michael Muchlebach 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.
Yu Nesterov. Universal gradient methods for convex optimization problems. Mathematical Program- ming, 152(1):381 2015.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
A. Orvicto and A. Lucchi. Shadowing properties of optimization algorithms. In Neural Information Processing Systems, December 2019.
Bradley Paden and Shankar Sastry. A calculus for computing filippov's 's differential inclusion with application to the variable structure control of robot manipulators. IEEE Transactions Circuits and Systems, 34:73-82, February 1987.
Boris Polyak. Gradient methods for the minimisation of functionals (in Russian). USSR Computa- fional Mathematics and Mathematical Physics, 3:864-878, December 1963.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
O. Romero and M. Benosman. Finite-time convergence in continuous-time optimization. In Interna- tional Conference on Machine Learning, Vienna, Austria, July 2020.
O. Romero, S. Chaterjee, and S. Pequito. Convergence of the expectation maxiimiiiiiniiiiiiiiiiii algorithm through discrete-time іуарuпov stability theory. Proceedings of the American Control Conference (ACC). pp. 163-168. July 2019.
Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In International Conference on Machine Learning, pp. 9224-9234. PMLR, 2021.
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-33,, 1995.
Johannes Schropp and I Singer. A 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' Aspremmnn. 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.
J.A. Snyman. A new and dynamic method for unconstrained minimization. Applied Mathematical Modelling, 6(6):448 462, December 1982.
12

---

Under review as a conference paper at ICLR 2022
J.A. Snyman. An improved version of the original leap-frog frog dynamic method for unconstrained minimization: LFOPI(b). Applied Mathematical Modelling, 7(3):216-218 June 1983.
Andrew M. Stuart and A. R. Humphries. Dynamical systems and numerical analysis. Cambridge University Press, first edition, November 1998.
W. Su, S. Boyd, and J. Candes. A differential equation for modeling Nesterov's 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. Lyapumov functions for first-order methods: Tight automated convergence guarantees. In International Conference 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 accelerated methods in optimization. Proceedings of the National Academy of Sciences, 133(47)573311-7755 2016.
A. Wilson. Lyapunov Arguments in Optimization. PhD thesis, UC Berkeley, 2018.
Ashia Wilson, Lester Mackey, and Andre Wibisono. Accelerating rescaled gradient descent: Fast optimization of smooth functions. arXiv preprint arXiv:1902.088255 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 Neural Information Processing Systems, December 2018.
13

---

Under review as a conference paper at ICLR 2022
A DISCONTINUOUS SYSTEMS AND DIFFERENTIAL INCLUSIONS
Recall that for an initial value problem (IVP)
f(t) = F(((t))
(25a)
zr(0) .
(25b)
with F + R", the typical way check for existence of solutions is by establishing continuity of Likewise, to establish uniqueness of the solution, we rypically seek Lipschitz continuity. When F is discontinuous, we may understand (25g as the Filippov differential inclusion
a(L) (())),
(26)
where K[F]: RR" = I denotes the Filippov set-valued map given by
(x) -
n co F(Bs(a) \ S),
(27)
8>-0 (SS)0
where μ denotes the usual Lebesgue measure and to the convex closure, i.e. closure of the convex
hull For more details, Paden & Sastry (1987). We can generalize (26) the differential inclusion Bacciotti & Ceragioli (199))
((1) E F(x(()),
(28)
where F: R" is some set-valued map.
solutions). We say that [0, R with < co is compact subset of T), Furthermore,
Definition 1 (Carathéodory/Fllipppee
a Carathéodory solution to (28) if xx)) is absolutely continuous and (28) is satisfied a.e. in every
say that sr-) is maximal Carathéodory solution if no
other Carathéodory solution x' x'(.) exists with x = x' [0.r)- If = K[FF). then Carathéodory solutions
are referred as Filippov solutions.
For a comprehensive overview of discontinuous systems, including sufficient conditions for existence (Proposition and uniqueness (Propositions 4 and 5) of Filippov solutions, the work of Cortés (2008). In particular, it can be established that Filippov solutions to (25) exist, provided that the following assumption (Assumption 6 holds.
Assumption (Existence of Filippov solutions). F FR + R" is defined almost everywhere (a.e.) and is Lebesgue-measurran in non-empty open neighborhood U c IR" of zg E R" Further, F is locally essentially bounded in U, i.e., for every point x E U, F is bounded a.e. in some bounded neighborhood of
More generally, Carathéodory solutions to 28 exist (now with arbitrary E R"), provided that the following assumption (Assumption holds.
Assumption 7 (Existence of Carathéodory solutions). F R" = R has nonempty, compact, and convex values, and upper semi-continuous.
Filippov & Arscott 1988) proved that, for the Filippov set- valued map F = K[FF), Assumptions
and 7 are equivalent (with arbitrary Zg E R²" in Assumption ()
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 the following proposition.
Proposition 1 (Theorem of Paden & Sastry (1987) ) Under Assumption
we have
K[F]()) = { lim F(Tx): 2s E R" (NF US) s.t. 2z + k0000
(29)
for some (Lebesgue) zero-measure set NF C pn and any other zero-measure set C R In particular, if F is continuous at fixeedd then K(FF(x) = (F(x)).
For instance, for the GF (1. we have ([)v)[(>) = (-V)(x))
for every x E R provided that is continuously differentiable. Furthermore, if is only locally Lipschitz continuous and regular (see Definition of Appendix B then K[[vf][ = -i((z), where
af(x) lim Vf(x)) : a E R \ s.t. Tb - x )
(30)
14

---

Under review as a conference paper at ICLR 2022
denotes Clarke's generalized gradient Clarke (1981 of f. with denoting the zero- measure set over which f is not differentiable (Rademacher ' theorem). It can be established that f coincides with the subgradient of f, provided that f is convex. Therefore, the GF (I) interpreted as Filippov differential inclusion may also be seen as a continuous-time 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.
We say that x" E IR. is an equilibrium of (28) if x(t) = x² on some small enough non- degenerate interval is a Carathéodory solution to 28 In other words, if and only i E F(x*). We say that 28 is (Lyapunov) stable at x* E R" if. for every > 0, there exists some d > 0 such that, for
Definition 2.
every maximal Carathéodory solution xx-) of (28), we have ||00 - x='12 ||2 < 8 = [xx(t)
x 1|2 <
for every 2 0 in the interval where x x-)) is defined. Note that, under Assumption 7 if 28 is stable
at xx," then x" is an equilibrium of (28) Bacciotti & Ceragioli (egggooii((999) 1999).. Furthermore, we say that (28) is
(locally and strongly) asymptotically stable xx E IR" if stable at x" and there exists some ò such that, for every maximal Carathéodory solution x [0, r) - IR" of (28) if | - -x x*112 < then xtt) + x² as + т. Finally, (28) is (locally and strongly) finite-fime stable at x if it is asymptotically stable and there exists some >> O and T", : (B(²²) + o0) such that, for every maximal Carathéodory solution xx.)) of 28 with zo Bg(x"), we have lim,-) 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 S -cE(t)
(31)
a.e. in t 2 0, with c, E(0) 0 and < 1. Then, there exists some > such that E(t) 0 0.for t E [0, (*) and E(t*) = 0. Furthermore, t" > 0 can be bounded by
((0)__a
< c(1 a)
(32)
with this bound tight whenever (31 holds with equality. In that case, but now with a 2 1, then (t) for every? t O, with Tom E(t) 0. This will be represented by t 00, with (Oo) A lim E().
Proof. Suppose that E(t) > 0 for every E [0, 7] with T > 0. Let t be the supremum of all such T's, thus satisfying {t) > 0 for every E t"). We will now investigate (tt). First, by continuity of &, it follows that E {(²) 2 0. Now, by rewriting
d T(1)1-a
ε(t) < <cE())
S -c,
(33)
di 1
a.c. in t (0, can thus integrate to obtain
E(t) 8(0) 1-a
1-a a 1-a < ct,
(34)
everywhere in t E [0, 1)), which in turn turn leads to
E(1) & [8(0)] 1- - a(1 - 111-)
(35)
and
t E(0) -(())-- 1(0)1-a c(1 - a)
W c(1 aa)
(36)
where the last inequality follows from E(t) > 0 for every E 10, t)). Taking the supremum in 36
then leads to the upper bound (3)). Finally, we conclude that E(t)) = 0, since E(t*) is impossible
given that would mean, due to continuity of ε, that there exists some > t" such that (t) > 0 for every i E [0, T), thus contradicting the construction of '*.
15

---

Under review as a conference paper at ICLR 2022
Finally, notice that if & is such that (31) holds with equality, then (35 and the first inequality
in (36) hold with equality as well. The tightness of the bound (32) thus follows immediately.
Furthermore, notice that if 2 1, and & is tight solution to the differential inequality {31), i.e.
E(t) [E(0)=-a
c(1 a))))/(aa), then clearly E(t) > 0 for every t 0 and E(t - as
t 000
Cortés & Bullo (2005) proposed (Proposition 2.8) I. Lyapunov-based criterion establish finite- time stability of discontinuous systems, which fundamentally coincides with our Lemma for the particular choice of exponent a Their proposition was, however, directly based on Theorem Paden & Sastry (1987). Later, Cortés 2006) proposed a second-order Lyapunov criterion, which, on the other hand, fundamentally translates to {t) V (x) being strongly convex. Finally, Hui al. (2009) generalized Proposition 2.8 of Cortés & Bullo (2005) in their Corollary 3.1, to establish semistability. Indeed, these two results coincide for isolated equílibria.
We now present a novel result that generalizes the aforementioned first-order Lyapunov- results, by exploiting our Lemma] [ More precisely, given Laypunov candidate function V--). the objective is to set (L) A Viz(()), 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 D - R w.r.t the differential inclusion given by
28
((x) a faeR: 3u E F(z) s.t. a a= ap-22 v, Vp E (V))),,
(37)
for each x E D. Notice that, under Assumption for Filippov differential inclusions F K.[
the set-valued time derivative of V thus coincides with with the set-valued Lie derivative V (-).
Indeed, more generally V could be seen as a set-valued Lie derivative C w.r.t. the set-valued map F.
Definition 3. V(-) is said to be regular if every directional derivative, given by
V(x + hv) V(x)
V( A lim h-0
(38)
h
exists and is equal to
V(x' + hhv - V(x))
(x: limsup
(39)
h
known as Clarke'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 is Lipschitz and regular.
Assumption 8. V D + IR is locally Lipscthiz continuous and regular, with D C IR" open.
Under Assumption 8 Clarke's generalized gradient
(v A {p R" (Z; R
(40)
non-empty for every x E D, and is also given by
(V(x) lim VV(*k) : 2g E RR \Ny s.t. Fy +
(41)
&-000
where Ny denotes the set of points in D C R" where V is not differentiable (Rademacher's theorem) Clarke (198T).
(looree
Through the following lemma (Lemma 2 we can formally establish the correspondence between the set-valued time-derivative of V and the derivative of the energy function E(t) e (a((t) associated
with an arbitrary Carathéodory solution zx-) the differential inclusion (28).
Lemma (Lemma of Bacciotti & Ceragioli (1999). Under Assumption g given any Carathéodory
solution x T) + R. to (28). then E(t) - V(x(t)) is absolutely continuous and ε()
de (=x(t) E (xx()) a.e. in (0,
We are now ready to state and prove our Lyapunov-based sufficient condition for finite-time stability of differential inclusions.
16

---

Under review as a conference paper at ICLR 2022
Theorem 6. Suppose that Assumptions 7 and & hold for some set set-valued map F R = and some function V: D - R, where D C 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 V(x) -cV(2))
(42)
a.e. in x E D. Then,
28 is finite finite-time stable at x², with settling time upper bounded by
t* V(xo)==a al
(43)
where z²0)- = zg- In particular, any Carathéodory solution x(-) with x(0) Fp E D will converge in finite time to x² under the upper bound (43). Furthermore, D R2, then (28) is globally finite-time stable. Finally, if V (x) is singleton a.e. in x. E DD and 42 holds with equality, then the bound (43) light.
Proof. Note that, by Proposition I of Bacciotti & Ceragioli (999). we know that (28 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 (28) with
<0)) zo * x², we know by Lemma 2 that E() = ((x(t)) is absolutely continuous with E(t) E (z(()) a.c. in a [0, t*]. Therefore, we have
ε(1) S sup V(x(()) S - -cV(x(()) = -CE =-E())))))()))
(44)
a.e. in E [0, Since E(O) = (xa) > 0, given that so + x*, the result then follows by invoking Lemma [ noting that E(()) = 0 > V(L", x((*))((')))) 0 < xx(*) =
Finite-time stability still follows without Assumption provided that x" is an equilibrium of 28 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 zx--) that indeed exists and starts x00) zip E DD must converge in finite time to z², with settling time upper bounded by T(zo) (the bound still tight in the case that (42) holds with equality).
C PROOF OF THEOREM
Let focus on the q-RGF (the case of q-SGF (3) follows exactly the same steps) with the candidate Lyapunov function - fff((=", Clearly, V is Lipschitz continuous and regular (given that it is continuously differentiable). Furthermore. V is positive definite w.r.t. x*.
Notice that, due the dominated gradient assumption, x² must be an isolated stationary point of f. To see this, notice that, if x* were not an isolated stationary point, then there would have to exist some 8* sufficiently near x= such that ä* is both stationary point of f. and satisfies f( > f fx*). since x* is strict local minimizer of f. But then, we would have
0 p ( 2 kr ( - -((x))) >0,
(45)
and subsequently > 0, which is absurd.
Therefore, F(x) - cV (())
is continuous for every r E D {0}. for some small
enough open neighborhood D of x* Let us assume that D positively invariant w.r.t. (2). which can be achieved, for instance, by replacing D with its intersection with some small enough strict sublevel
set of f. Notice that [[)())) cll f=)Vl(=))l I'I with q (p, oo] (1, i.e., - oc). If
4= 0o, which results in the normalized gradient flow à TV((2l proposed by Cortés (006)).
v/(x)
then [[F(=)]l2 = c > 0. We can thus show that F(x) is discontinuous at x = 0 for q = 0o. On the other hand, if q (p,
oo), then we have [IF(x)) + 0 as + x²" and thus F(x) is continuous (but not Lipschitz) at x = x". Regardless, we may freely focus exclusively on {a*} since (x:) } is obviously zero-measure set.
17

---

Under review as a conference paper at ICLR 2022
Let F A K[F]. We thus have, for each x E D \ {x*},
sup (xx) = sup {a E R Fe E F F(x) s.t.
(46a)
sup (x) 2iVE F(x)}
(46b)
(Z(z) F(x)
(46c)
(46d)
= -cIVV(>>11
(46e)
S -
(46f)
-cC V(x)
(46g)
Since 0. < 1, given that & > 1 b s-1 is strictly increasing, then the conditions of Theorem are 6' satisfied. In particular, we have finite-time stability at x² with settling time t" upper bounded by
t" (f(2o) f(-"))²~ ( (2/C) 12/0))(1-
( cCb (1 #
(47)
cC (1 (1-6) 8r
cC (1- 8'
for each ro E D, 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 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 as a simple case of hybrid systems with one differential inclusion, with a possible jump or discontinuity the optimum. Based on this, we will use the tools and results of Sannflice & Teel (2010), which study how a certain class of hybrid systems behave after discretization with a 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 Th = IR"", and its discretization in time by Fa : IR. = R" We first recall definition, which we will adapt from the general case of jumps between multiple differential inclusions (Definition 3.2, Sanfelice Teel (2010)) to our case of one differential inclusion or flow.
Definition 4. ([T, cllossessss. Given T > 0, 0, 17 O, two solutions x [0, 7 + R". and Ik : {0, 1, 2, ...] + I" are (T,e) c)-close if: (a) for all t < T there cxists k E {1, 2, ...] such that It kn) e, and [tx xx(k)] 2
(b) for all E (1, .,... there exists 1 < 7 such that |t - k7) < 6, and [[x+(t xx (k)]l < 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
Theorem 7. (Closeness of continuous and discrete solutions on compact domains) Consider the differential inclusion
x(t E F(X(t)),
(48)
for given set-valued mapping F = TD assumed to be outer semicontinuous locally bounded,
nonempty, and with convex values for every x E C, for some closed set C S I Consider the discrete-time system represented by the flow Fa RRa = IR., such that, for each compact set K C R..
there exists E Koee and 17' > Such that for each x E K and each 1) E (0, 17*),
Fa(x) C. x + conF + p(n)B) + np(n)B.
(49)
A set-valued mapping J 1R" 3 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 locally bounded if, for each x R". there exists compact sets K, K' R2 such that K and F(K) & Uzek
K". In what follows, we use the following notations: Given set A, conA denotes the convex hull, and B denotes the closed unit ball in Euclidean space.
18

---

Under review as a conference paper at ICLR 2022
Then, for every compact set K C R", every > O, and every time horizon T R20 there exists
nf >> 0 such that: for any 7 E (0, 1t and any discrete solution Ię with Iy (0) E K + éB, 5 > 0,
there exists continuous solution 2t with 2,) K such that Dy and o, are ()) c)loos.
To prove Theorem 2 we will use the results of Theorem 7 where we will have to check that condition (49 satisfied for forward Euler discretization.
We are now 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 examine their discretization by forward-
The mapping Fa in this case is singleton, given by
Fa(x) _ x + n)
(50)
where 1) > 0, which clearly satisfies condition (49)
Then, using Theorem 7 we conclude about the eclossesssss between the continuous-time solutions of the flows F: q-RGG
q-SGF (3) and the discrete-time solutions.
Finally, using the Lyapunov function V = f- f(x*) as defined in the proof of Theorem together with inequalities (46g). (35). and a local Lipschitz bound on f. one can derive the weak convergence bound given by 16. follows:
[((x) f(x*) -fa -(a Lye, b > 0, 6>
=²=
[f(x)) 1 -(=))))21(((x)) -[(())))((x()]])
f(zi)ll) SE,
(51)
[f(xx) f(x*)]le S E+ [1f(z))) - f(x)>)
[1xx)) - -[(x))l2 E (1(xo) [(x ()(-a) =(( - an) for S kit 7
where
6 σ 0 p- 0'
2-1 ē= 7
k* ((=)))((="))(a-- ?(1-a)n
Next, the case for > k* is rather straightforward: Indeed, for > t* by finite-time convergence result, we have x², which directly leads to the bound (*xx) f(x))]] Lye, k <> k- since the term (x( - f(x* ll in 51) vanishes.
E PROOF OF THEOREM 3
Proof. We divide the discussion by different flows
Proof of q-RGF:
Following the definitions of smoothness, we have
f(x+11) & f(xx) + (Vf(F)), 04+1 - Ixx) +
|| - 12
V [ 12
Ly f
=((xx)
q
||
(2x))l2
uly
9-1
Lyd
fmx)
7 q
ff(x))
V
(52)
S (xx))
9
L -
| [
$ f(x)
q L L
- (f(xx) f*)
q
q
q q-1
= f(x) - kILL (f(x))
'Note that here for convenience, we fix the order in gradient dominance g, while previous discussion assumes that q > p.
19

---

Under review as a conference paper at ICLR 2022
subtract both sides by fr, we have
f(*x+1) - (f(x fr,
(53)
which verifies the conclusion by recursion.
Proof of q-SGF: Similarly, for the q-SGF case, we have
L [(x+1)) S [(xx) + (V (xx() F6+11 xR))
|,841
Ix 112
= f((x) - > 1| ((T (af())) (VI(xx))) + Lyan²
[V
q
= f((x)) - (7
nă I79
| [
(54)
9
s {(xx)
q
(n L) rox [+(+)))
q
I f(xx)
9 1-1
(n b) - q أ (f(xx) - -
so we have
f(*++1) f - (1 (n) (f(Iz) (*).
(55)
By the inequality e 1 - 2, we can get that the complexity of the above algorithm with q-RGF and q-SGF are
KTT In 2) and ((n2n) - In )
(56)
which verifies the conclusion.
F PROOF OF STOCHASTIC RGR (THEOREM 4D
Proof. Following the definitions of smoothness, we have
f(x++1) S {((x)) + (V (V]((x), Th+1 - xk) + ||0001 - x2
g(xx))
L
119(#=))13
=s(xx) 7t [I(x)) - g(xx) + g((x))
2=2
(1g( )12
(19(()))12
Li4 [1a(TT)]12
g((x)
[(xx)
TTh
q
7M
vs(xx) -g(xx)
(1g(()))) 2-z
[1] g(xr))
Lrg
< <((x)
(Tk
7/ [|((
Vf((x)
(xx))
q
f(x))
1kk
[1((=))1
+
2h +
[VV((z))
(<xx)
q
(57)
where the second inequality comes from the Young's inequality. Then note that by Jensen's inequality,
[V((x)))) = 2t | (V)(=)) o(xx) + g(xx)) 2 (19(==))1) [Vf(x)) g(xx)))l))
- - --21-01 + [Vf(xx)
(xx)) -V(x))))((1))11
(58)
20

---

Under review as a conference paper at ICLR 2022
note that the setting of 7/k will ensure the coefficient of [1((2)) to be negative, so we have
f(xx+1) s ff(x))
(7h-
Ink
(2
(2'
[Vf - s(xx))13) + 7h 2b
- -
vp
q
= =s(rk) 2
Tk
L q
[+ +
2 Lik
[VV]( -V((())) (1xx))
4/ q
(59)
then take expectation on both sides, by the bounded variance and gradient dominance, we have
[f(x++1) S E
f(xx) f(xx)-2" - 2 v
22
7k
I
[+(x))))
+
12nk
Inkk
q
1/
q
b(xr))
S -xxx)=
-2
7k
Ink
pp (f(xz) - -1²) +
2
Lik
0²
9
b(xxa)
(60)
so subtract both sides by 1", we have
B[f(0x42)- 14] S EB (1-21-9 22-
7k
Ink
puttt) ) (F(OK) -5²)+ +
(2th
Lik
o²
1
q
q
b((x))
(61)
set 7/ (pb)T b(xxx) =²²=
22(20) 1
and
(2 & log
24
K
2x
6
we have
2
20
E.
1-q
(s(rk) (r)
1.1-9
(24))
2
K
2
K-1
< E
+
(2 Ns NiT
(2xb)
K
20
E
(2
A T
A
+
LT
1
[
(2
2
1-m
2
K
20
(216)
(62)
E
1
A +
(2
by bt
2
2
K
(2or) 10 N
E
1
(2 Ao-
b
2x T-
(2o) 8 p 1-9
< E
exp
(2
K
A
b
6
+ = E,
2
2
while the total sample complexity is (note that
1
+
1
= =1, E (1,2), which implies vb E [2, +00))
q
$
K. 62 2 (2xh)
log
24
(2 (2o) u
= o
0 - -ivee
- log A) e
(63)
1-
which verifies the conclusion.
21

---

Under review as a conference paper at ICLR 2022
G PROOF OF STOCHASTIC q-SGF (THEOREM 5)
Proof. Note that, as mentioned in Assumption and here the gradient dominance and Lipschitz smoothness is defined under (61, (o.l))))oooo -norms. Following the definitions of smoothness, we have (note that v0 -
L
f(x++1) - f(xx) + (Vf(z)), Fx41 -x2) | - Fx 11.
=f(xk) - >ull(<>))) (V (g (g(xx))) + L [g(x)))1 |sign (I(xx))1l
L [|((()))]
f((x)) - x 2l sign (g(xx)))
(64)
conditioning on Th, we have
[(f(=++1) [x]]
In (1x(x=))11
(65)
$ f((k) E >kll(<>>>1l (V (Vf( (g(xx))) 2s
1
note that for each component of ((xx), ), we have
E
[1((=))] sign (0x())))) m7
E
(1o(( IIF PPiiggn (V:((xx)) sign (g:(1)))) sign (V.((xx))
(66)
-19(0)))1 P(sign (V.f(ax)) * sign (g. sign (+f((x)) ( z
=E -B(lo(e))1lf (2P(sign (V.f(x+)) sign (xx sign (V.f(rx)) 2b
(2P(ssn
then with the SPB condition in Assumption 5 we have
1
P(sign (V.f(zx)) sign (g((xx))) 2p"
2'
so we have
[[f 1) [x]]
T
< f(xx) E8
7h (mllg(xx)) (2p" ()isig (Vf(xx)). vf(xx)) 2x
+ E
(
)l -
Ly
< f((x))
E
nh (2ppp" - 1)1lg(=))11 || (xx))l
+ E
[19(#)))1 |
q
T B [1((xx)]]
-
< <((x))
(2ppp" 1>>
arkk
q
(67)
where the last inequality comes from the convexity of - decomposition, we have
Then for the last term in the RHS, by
|)( = 2" -20 1 (o((z) - f(xx) + ((sa)))
5-t (1-ta()) + [[V)(x)) - s(xx))1))
(68)
22

---

Under review as a conference paper at ICLR 2022
so we have (recall that vb 701)
[[f(x++1] mml
s [axx) - -2x(2p" - / - +
LT
E [1 + [IV - ((x)))l") JM
9
LTg20-1
|V [[[(= + L 0²
s (1xx)
(29" 1)7k
b((0k)
9
9
L 21/20-11
qu 1 (f(zz) - -f++ + 1
0²
7
S fxx)) -
(2p* - 1)7k
((xx)
(69)
so take
$
1,20
1-g
b(xx)) =b²= =
(2p" 1) -4
0²E -
7k
2x"
and
K = (2p" -1) 11)- (12001) In
2A
we have
[[f(xx) -f f*]
1 (2p" - 1) 112V-1) r =ur-
(12V-1)
0²
*/4
E
(f(*k-1) ft) -f)
9 9-1
(2pp'
1)a²
1/2
(1 1-22p 1) (122 1'o -) (*) (12V-1) 1-1
0²
E
'(2p" 1)
b2
$ (1 - (2p' - -1) (12t K (f(xo) - -f*) + (L2 -
02
iz
8(2p"
1)
ba
(2p" - 1)t 1x20011))
(-(2p* 1)ah (122-1) - K A + (n) (1) 02 4z4
S exp
((2p" 1) 1
b2
6 + =,,
2 2
(70)
which concludes the proof"
Remark 6. Similar results can be derived in the case of single sample (trivial batch size), however, some of them will require additional assumptions like bounded gradient norm and vanishing stepsize (Karimi et al.] (2016), Theorem 4), but here we do not need this strong assumption of gradient boundedness, and we always use a constant stepsize; these are the benefits brought by 'non-trivial' batch-size, i.e., neither one sample nor the full set of data.
Furthermore, in that case, the final complexity will be generally O(1/e) (Krimi et al. (016)).
Theorem 4), whereas here our result is a linear convergence iteration complexity (i.e., Oloo (1/c))
to achieve the e-neighborhood (while the final sample complexities of two paradigms should be the same), which is much faster. So there will be a tradeoff in different parameter settings.
Lastly, we want to mention that batch size with dependence on is pretty common (or even required) in stochastic optimization problems, e.g.. Ghadimi et al. (2016) and Fang et al. (2018). Therefore, we believe that using a batch size with dependence on e is a reasonable option.
'Different from stochastic RGF, here we do not discuss the sample complexity. because the extra SPB assumption is defined on the "oracle", i.c., the mini-batch estimator g(z),, so the concern here should be the oracle complexity instead, which will be the iteration number K here.
23

---

Under review as a conference paper at ICLR 2022
H ADDITIONAL EXPERIMENT DETAILS AND NUMERICAL RESULTS
In this section, we will expand upon the numerical results experiments discussed in the paper. In particular, report more details the hyper-parameter values used for the numerical tests, and report some results for GPU implementation of SVHN experiments.
H.1 HYPER PARAMETERS VALUES USED IN THE TESTS OF SECTION 4. EXAMPLE 2
GD fixed step size: 10-3
RGF Euler disc. w/fixed step size: q = 2.2, 10-3
RGF Euler disc. w/fixed step size: q = 3, = 10 2
RGF Euler disc. w/fixed step size: q = 6, r 10
RGF Euler disc. w/fixed step size: q 10, 10-2
H.2
HYPER PARAMETERS VALUES USED IN 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:://yyoocchorrdddd////bbb//p
GD: 17 = 4.10 / = 0.9, Nesterov=False
RGF: = 4.10-2
SGF: 4.10-3
ADAM: 8.10 (remaining coefficients=nominaa values)
RMS: = 10 10-3 (remaining coefficients-nominal values)
ADAGRAD: 7/ 10-3 (remaining coefficients-nmminal values)
ADADELTA: 7) 4.10-2, 2 p 0.9, 10-6, weight decay
Remark 7. Choice of g: The settling time upper bound (15) decreases as + co, which appears to lead to faster convergence when discretized. On the other hand, the larger q is, the stiffer the ODE, so more prone to numerical instability, so 9 cannot be too large. Therefore, assuming p to be not too large, appears that g E (p, p 6] works best, with issues. For instance, if we know the cost function to be strongly convex (locally), then we search for q slightly larger than p the other hand, we don't 't know the order investigate this further in future work. Furthermore, there evidence that gradient dominance does hold locally in many deep learning contexts (Zhou and Liang, 2017, https://arxiv.org/abss hta/aaass/1// 1710.06910011 Indeed, since convexity readily leads to gradient dominance of order oc, suffices that slightly stronger form of it holds (but weaker than strong convexity), in order to have and thus for us to be able to choose > p.
small needed to avoid numerical
first, but continue increase until performance deteriorates. If, on 1, then it's currently unclear how to choose q. We will
H.3 EXPERIMENT 6: GPU IMPLEMENTATION
To check if the numerical results obtained CPU, more specifically the acceleration trends, hold true on a GPU, we run some extra tests on Titan X nvidia gpu with 12GB memory, the results are reported below.
We first tested the performance of Euler discretization of the proposed flows against Adam, and GD algorithms SVHN dataset. We tested the proposed algorithms train the VGG16 CNN model with cross entropy loss. We divided the dataset into training set of 74 batches with 1000 images each, and training batches. We tested Euler discretization of q-RGF (c 1, 2.1, 1, 7) 0.04 ), and Fuler discretization of q-SGF (c 10-3 optimal tuning as in Section 4.2).
of batches of 1000 images each, and ran 20 epochs of training over all the
2.1. rj 0.04 against GD (n 0.1) and Adam (same
In Figures 5
we can see that both algorithms, Euler RGF and Euler g-GGF converge faster than GD and Adam for these tests, and reach the same performance on the test-set.
10 all the tests, for R-RGF and q-SGF unless otherwise stated.
24

---

Under review as a conference paper at ICLR 2022
Adam-944 94%
ADAM-94%
RGF-94%
RGF-94%
SGD-94%
SGD-949
2.0
SGF=94%
Training Loss
1.5
Test
0.5
Training lterations
Test lterations
Figure 5: Losses for several optimization algorithms run GPU- VGG16-SVHN: Train loss (left), test loss (right)
94%
RGF-94%
SGD-94%
SGF-94%
Training Loss
100
200
300
600
700
Computation Time [sec]
Figure 6: Training loss vs. computation time for several optimization algorithms run on GPU- VGG16-SVHN
25


Reviews:
[{"review_id": "vbcFWhZ_u_D", "reviewer": "Reviewer_rpnN", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strength**\n- Fundamental methods: This paper studies two (discrete) fundamental methods, which are gradient methods (with or without sign function) with gradient norm dependent step sizes. Many practical gradient methods in deep learning use such step sizes, so studying their fundamental versions are of interest.\n- Experiments: Although only one very practical problem is considered, the experiments illustrate that the proposed methods outperform ADAM and Nesterov's accelerated GD.\n\n**Weakness**\n- Motivation: Although this work has merit, it is not well motivated. For example, it would have been nice if the authors provided references to the sentence \"Concerning that many ~\" in page 1. In specific, I have hoped to see some reasoning why we need to study such two specific gradient flows (and their discretization) over the standard gradient flow in Introduction and Related work sections. In addition, why is the gradient dominant condition of interest, over existing standard conditions, especially considering the authors' interest in applying their method to deep learning?\n- Finite-time convergence in continuous time translates to acceleration in discretization: The authors mention that many existing related analyses focus on matching convergence rates from the continuous-time domain into the discrete-time domain. Instead, this paper states that (e.g., in page 8) finite-time convergence in continuous time translates to some acceleration in the associated discretized algorithm. I think matching the convergence rates as other papers did would have better convinced the readers on the theoretical justification of acceleration (in early iterations).\n- Gradient dominant condition: There is no comparison to convergence rates of other methods under the same condition. Since the authors claim that their methods are faster than other methods in experiment, it would be nice to have some theoretical comparison. \n- Experiment: Intuition behind the practical acceleration of the proposed methods is barely given. Therefore, I am not optimistic that this trend will appear in other experiments. What does the tuned parameter $q$ mean in the experiment on SVHN dataset? \n\n**Minor**\n- Page 3 below (6b): $F_d: Z_+ \\times R^m \\to R^m$\n- Page 3 Examples 1 and 2: A feedback-based step size, component-wise step size and a backward Euler discretization are not used in the paper hereafter, so I think it is better to make this page concise, and state something more related to the main part.\n- Page 6: Do the rates of the discretized methods match those of their continuous ones?\n- Page 6: Could you explain further about the choice of $\\ell_\\infty$-norm, rather than $\\ell_2$?\n- Page 7 Example 1: For the case $q>1$ in example 1, it does not seem Lipschitz smooth given in Assumption 2. For an \"academic\" example, I think one would hope to see an example satisfying all of the considered conditions.\n- Page 8 Figure 1 left: How did you define the optimality gap in the figure? (e.g., after certain number of iterations?)\n- Page 9: How about the vanilla GD or the heavy-ball momentum? Using acronym GD (and SGD) for Nesterov's method seems odd.\n- Page 9: How did you get 40 min here?\n- Page 9 Figure 3: Why do we have drastic drops in the right figure?", "summary_of_the_paper": "This paper studies the convergence rates of the two first-order methods, named $q$-RGF and $q$-SGF. These are constructed by forward Euler discretizing the $q$-rescaled gradient flow ($q$-RGF) [Wibisono et al., 2016] and $q$-signed GF ($q$-SGF) [Romero-Benosman, 2020], respectively. These gradient flows are shown to converge in finite time in [Romero-Benosman, 2020], under the gradient dominant condition of order $q$. The authors show that their forward Euler discretized versions have linear rates, under an additional Lipschitz smoothness of order $q$. The paper also considers their stochastic variants. Numerical experiments on toy examples and practical example illustrate that the proposed method might have practical advantage over existing methods such as GD and ADAM.", "summary_of_the_review": "While the theoretical results seem new, they are not well motivated (at least practically), and the paper does not seem to provide sufficient justification of the success of the proposed methods in practical applications.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "U7PkT9f-XVD", "reviewer": "Reviewer_xRJ7", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strength: \n1. Convergence behavior of the discretization of gradient flows is an important question in optimization. \n2. The paper is well written and very good to follow.\n3. The methodology is validated via empirical experiments and theoretical analysis.\n\nWeakness:\n1. The convergence rate of Euler discretizations of rescaled gradient flow and signed gradient flow under the deterministic setting exists in the literature. (The author do point out this.) The only difference is the generalization of the Lipschitz smoothness. The author should illustrate why such generalization is important and what is the main technical difficulty in extending the existing theoretical result. \n2. Under the stochastic setting, the result is not convincing in the sense that although the epsilon can be arbitrary small, the batch size will go to infinity, which is not good especially under the stochastic setting. ", "summary_of_the_paper": "In this paper, the author study two first-order optimization methods, which are the Euler discretizations of rescaled gradient flow and signed gradient flow. They prove the convergence rates for both methods under both deterministic and stochastic settings. ", "summary_of_the_review": "I found the manuscript to be clearly written and technically sound. I am, rather unfortunately, inclined to recommend that the manuscript be rejected on the grounds that the work may not have sufficient merit / novelty to warrant publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "OX6qtKPRG07", "reviewer": "Reviewer_5qiS", "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": "My comments are as follows.\n\n1) The paper starts well but in Eq. (6a)-(6b), when authors describe the state-space form of the optimization algorithms, I think there might be a typo in (6b): Is it supposed to be $G(X_{k+1})$? Thiis notation is confusing as it is not made clear what $x_k$ and $X_k$ actually denote.\n\n2) The following examples are meant to be helpful but they all consider the case $G(x) = x$. It is really unclear what (6a)-(6b) describes. Authors should put an example with a clear case where $G$ is not identity (e.g. a proximal-gradient scheme?)\n\nI also don’t understand the introduction of this notation, as it looks like it’s not used elsewhere in the paper and not central.\n\n3) The authors then introduce the fundamental assumption of the cost functions considered, that is, gradient dominance of order $p$. I strongly suggest authors to motivate this assumption beyond strong convexity. What kind of non-convex functions does satisfy this inequality? Is it similar to, e.g., weak-convexity or dissipativity conditions usually used in non-convex optimization literature?\n\n4) The toy examples in the paper are helpful but their connection to theory is not exploited: In particular, in this section, I’d strongly suggest authors to verify their assumptions for these toy examples precisely by working out relevant constants. Then, plotting the errors vs. actual error bound computations would really be insightful about the meaning of the results derived in this paper.", "summary_of_the_paper": "This paper considers the analysis of two discrete time schemes derived from gradient flows named q-RGF and q-SGF. The topic fits more generally into continuous time perspectives for optimization and the relations between ODE theory and optimization. This is an interesting direction with many interesting promises.", "summary_of_the_review": "These results can be potentially useful for advances in this field. I found the paper clear and insightful in general.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MjT0lAZi8v7", "reviewer": "Reviewer_AvzH", "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": "The submitted paper studies the convergence properties of discretized gradient flows, and provides some convergence results which is the main strength of the paper. To me, there are few points which are not clear\n1. In Theorem 2, we have $k^\\star = \\frac{(f(x_0)-f(x^\\star))^{(1-\\alpha)}}{\\tilde{c}(1-\\alpha) \\eta}$. Now denote $C = \\frac{(f(x_0)-f(x^\\star))^{(1-\\alpha)}}{\\tilde{c}(1-\\alpha)}$ which is a constant. Suppose $\\epsilon$ is some chosen accuracy and $\\eta$ is some sufficiently small time step-size. The condition $|t-k\\eta|<\\epsilon$ means that $$ \\frac{t-\\epsilon}{\\eta} < k < \\frac{t+\\epsilon}{\\eta}  . $$ For $t$ large enough, it can happen that $$ t - \\epsilon > C $$ where $C$ is defined above. Corresponding we have $k > k^\\star$. Then Equation 16 would fail since $k \\leq k^\\star$? I'm wondering if I missed something here?\n2. The results for stochastic gradient descent are $\\epsilon$-dependent, such as the batch size which is $O(\\frac{1}{\\epsilon})$ for stochastic $q$-RGF and $q$ closed to $2$. So in the numerical experiments, what are the choices of $\\epsilon$? And the result is not very practical in the sense that if sufficiently high accuracy solution is desired, then the batch size would be too large such that it will be close or equal to the full gradient descent. As a result, is it possible to establish result for accuracy independent batch size or for the vanishing step-size?\n\nAlso I have two side questions\n1. Since the discrete algorithms fails the finite-time convergence, is it possible to have other type of discretization which can provide finite convergence? Or at least numerically.\n2. Suppose we consider second-order dynamic systems, can the finite-time convergence still hold in this case? \n\n", "summary_of_the_paper": "Motivated from the finite-time convergence of two first-order gradient flows, the submitted paper studied the convergence properties of discrete iteration schemes in both deterministic and stochastic settings. Convergence results are proved for these algorithms, and numerical experiments are provided to demonstrate the performance of the schemes. ", "summary_of_the_review": "Motivated from continuous dynamical system, the authors studied the convergence behaviors of discrete first-order methods. However, there is a gap between the continuous and discrete setting, and the obtained results need to be clarified. \n\n\nedit: the responses look good to me, and i raised my score by 1.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper starts from the observation that a certain class of rescaled gradient flows - referred to in the paper as RGF and SGF - converge to a solution in finite time (Wibisono et al., 2016; Romero and Benosman, 2020). As a result, it is plausible to ask whether the Euler discretizations of these flows - viewed now as optimization algorithms - enjoy superior convergence properties or not. The authors' main results establish a linear convergence rate under a certain gradient dominance condition, as well as linear convergence to an $\epsilon$-neighborhood of a solution if the algorithms are run with minibatch gradients of size $O(1/\epsilon^\rho)$ for some positive exponent $\rho>0$.

The reviewers raised several concerns regarding the motivation of the authors' work and the comparison of the rates they obtain to other related papers in the literature. The reviewers that raised these concerns were not convinced by the authors' rebuttal and maintained their original assessment during the discussion phase.

From my own reading of the paper, I was perplexed by the fact that the authors did not compare the rates they obtained to existing results in the context of KL optimization, such as the cited paper by Attouch and Bolte and many follow-up works in the area. Also, in the stochastic part, while the authors argue that "utilizing batches with size dependent on $1/\epsilon$ is absolutely reasonable and usual, in both theory and practice", it should be noted that a high accuracy requirement (small $\epsilon$) could lead to completely unreasonable batch sizes (effectively exceeding the size of the dataset, especially when $\psi$ is small). Thus, while it is possible to achieve convergence to arbitrarily high accuracy with a sufficiently small step-size for a _fixed_ batch size, the rate of this convergence cannot be linear overall - in contrast to the way that the authors frame their result.

In view of the above, I concur that the paper does not clear the bar for ICLR, so I am recommending rejection at this stage (but I would encourage the authors to resubmit a suitably revised version of their paper at the next opportunity).
Decision: Reject