Year: 2021

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.

heading: 1 INTRODUCTION
text: Consider the unconstrained minimization problem for a given cost function f : Rn → R. When f is sufficiently regular, the standard algorithm in continuous time (dynamical system) is given by
ẋ = FGF(x) , −∇f(x) (1) with ẋ , ddtx(t), known as the gradient flow (GF). Generalizing GF, the q-rescaled GF (qRGF) Wibisono et al. (2016) given by
ẋ = Fq−RGF(x) = −c ∇f(x)
‖∇f(x)‖ q−2 q−1 2
(2)
with c > 0 and q ∈ (1,∞] has an asymptotic convergence rate f(x(t))− f(x?) = O (
1 tq−1
) under
mild regularity, for ‖x(0)− x?‖ > 0 small enough, where x? ∈ Rn denotes a local minimizer of f . However, it has been recently proven Romero & Benosman (2020) that q-RGF, as well as q-signed GF (q-SGF)
ẋ = Fq−SGF(x) = −c ‖∇f(x)‖ 1 q−1 1 sign(∇f(x)), (3)
where sign(·) denotes the sign function (element-wise), are both finite-time convergent (in continuoustime), provided that f is gradient dominated of order p ∈ (1, q). In particular, if f is strongly convex, then q-RGF and q-SGF is finite-time convergent for any q ∈ (2,∞], since f must be gradient dominated of order p = 2. Considering that many algorithms are inspired from continuous flows with convergence guarantee, e.g., Muehlebach & Jordan (2019); Fazlyab et al. (2017a); Shi et al. (2018); Zhang et al. (2018); França et al. (2019b); Wibisono et al. (2016), a natural question arises: what is the convergence rate of the corresponding discrete-time algorithms, which are induced by discretization of finite-time convergent continuous-time flows?

heading: 1.1 CONTRIBUTION
text: In this paper, we investigate the convergence behavior of an Euler discretization for the q-RGF (equation 2) 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.

heading: 1.2 RELATED WORK
text: Propelled by the work of Wang & Elia (2011) and Su et al. (2014), there has been a recent and significant research effort dedicated to analyzing 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., 2018; Fazlyab et al., 2018; Fazlyab et al., 2018; Taylor et al., 2018; França et al., 2019a; Orvieto & Lucchi, 2019; Romero et al., 2019; Muehlebach & Jordan, 2019). A major focus within this initiative is in accceleration, both in 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 (Muehlebach & Jordan, 2019; Fazlyab et al., 2017a; Shi et al., 2018; Zhang et al., 2018; França et al., 2019b; 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 a very important topic, which can be dated back to 1970s, see Botsaris (1978a;b); Zghier (1981); Snyman (1982; 1983); Brockett (1988); Brown (1989). In Helmke & Moore (1994), 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-based optimization, including nonlinear constraints.
Tools from Lyapunov stability theory are often employed for the analysis, mainly because there already exists a 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 an 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, 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 is 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(x) − f(x?) can be a good initial candidate. Further, if f is continuously differentiable and x? is an isolated stationary point, then another alternative is V (x) , ‖∇f(x)‖2. However, most fundamental and applied research conducted in systems and control regarding Lyapunov stability theory deals exclusively with continuous-time systems. Unfortunately, (dynamical) stability properties are generally not preserved for simple forward-Euler and sample-and-hold discretizations and control laws (Stuart & Humphries, 1998). Furthermore, practical implementations of optimization algorithms in modern digital computers demand discrete-time. Nonetheless, it has been extensively noted that a vast amount of general Lyapunov-based results (perhaps most) appear to have a discrete-time equivalent.

heading: 2 PRELIMINARIES

heading: 2.1 OPTIMIZATION ALGORITHMS AS DISCRETE-TIME SYSTEMS
text: Generalizing (1), (2), and (3), consider a continuous-time algorithm (dynamical system) modeled via an ordinary differential equation (ODE)
ẋ = F (x) (4)
for t ≥ 0, or, more generally, a differential inclusion
ẋ(t) ∈ F(x(t)) (5)
a.e. t ≥ 0 (e.g. for the q = ∞ case), such that x(t) → x? as t → t?. In the case of the q-RGF (2) and q-SGF (3) for f gradient dominated of order p ∈ (1, q), we have finite-time convergence, and thus t? = t?(x(0)) <∞.
Most of the popular numerical optimization schemes can be written in a state-space form (i.e., recursively), as
Xk+1 = Fd(k,Xk) (6a) xk = G(Xk) (6b)
for k ∈ Z+ , {0, 1, 2, . . .} and a given X0 ∈ Rm (typically m ≥ n), where Fd : Z+ × Rm → Rm and G : Rm → Rn. Naturally, (6) can be seen as a discrete-time dynamical system constructed by discretizing (4) in time. In particular, we have xk ≈ x(tk), where {0 = t0 < t1 < t2 < . . .} denotes a time partition and x(·) a solution to (4) or (5) as appropriate. Therefore, we call Xk and xk, respectively, the state and output at time step k. Example 1. The standard gradient descent (GD) algorithm
xk+1 = xk − η∇f(xk) (7) with step size (learning rate) η > 0 can be readily written in the form (6) by taking m = n, Fd(x) , x− η∇f(x), and G(x) , x.
• If the step sizes are adaptive, i.e. if we replace η by a sequence {ηk} with ηk > 0, then we only need to replace Fd(k, x) , x− ηk∇f(x), provided that {ηk} is not computed using feedback from {xk} (e.g. through a line search method).
• If we do wish to use time-varying step-size, then we can set m = n + 1, G([x; η]) , x, and Fd([x; η]) , [F (1) d ([x; η]);F (2) d ([x; η])], where F (1) d ([x; η]) , x − η∇f(x), and F (2) d is
a user-defined function that dictates the updates in the step size. In particular, an open-loop adaptive step size {ηk} may be achieved under this scenario, provided that it is possible to write ηk+1 = F (2) d (ηk).
• If we wish to use individual step sizes for each the n components of {xk}, then it suffices to take ηk as an n-dimensional vector (thus m = 2n), and make appropriate changes in Fd and G.
In each of these cases, GD can be seen as a forward-Euler discretization of the GF (1), i.e.,
xk+1 = xk + ∆tkFGF(xk) (8)
with FGF = −∇f and adaptive time step ∆tk , tk+1 − tk chosen as ∆tk = ηk.
Example 2. The proximal point algorithm (PPA)
xk+1 = arg min x∈Rn
{ f(x) + 1
2ηk ‖x− xk‖22
} (9)
with step size ηk > 0 (open loop, for simplicity) can also be written in the form (6), by taking m = n, Fd(k, x) , arg minx′∈Rn{f(x′) + 12ηk ‖x
′ − x‖22}, and G(x) , x. Naturally, we need to assume sufficient regularity for Fd(k, x) to exist and we must design a consistent way to choose Fd(k, x) when multiple minimizers exist in the definition of Fd(k, x). Alternatively, these conditions must be satisfied, at the very least, at every (k, x) ∈ {(0, x0), (1, x1), (2, x2), . . .} for a particular chosen initial x0 ∈ Rn. By assuming sufficient regularity, we have∇x{f(x) + 12ηk ‖x− xk‖ 2 2}|x=xk+1 = 0, and thus
∇f(xk+1) + 1
ηk (xk+1 − xk) = 0 ⇐⇒ xk+1 = xk + ∆tkFGF(xk+1) (10)
with ∆tk = ηk, which is precisely the backward-Euler discretization of the GF (1).
2.2 CONTINUOUS-TIME CONVERGENCE OF q-RGF AND q-SGF
In this section, we review the necessary conditions to ensure finite-time convergence of these flows. Here the hyperparameter c > 0 in equation 2 and equation 3 will not be explicitly denoted in Fq−RGF, Fq−SGF. Next, borrowing terminologies from Wilson et al. (2019), we define the notion of gradient dominance with order p as following.
Assumption 1 (Gradient Dominance of Order p). For a continuously differentiable function f , we assume the function f is µ-gradient dominated of order p ∈ (1,∞] (µ > 0), i.e.,
p− 1 p ‖∇f(x)‖ p p−1 2 ≥ µ 1 p−1 (f(x)− f(x?)), ∀ x ∈ Rn, (11)
where x? ∈ arg minx∈Rn f(x) is the local minimizer, also we denote the optimal value f? , 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 p = 2, often referred to as the Polyak-Łojasiewicz (PL) inequality, which was introduced by Polyak (1963) to relax the (strong) convexity assumption commonly used to show convergence of the GD algorithm (7). The PL inequality can also be used to relax convexity assumptions of similar gradient and proximal-gradient methods (Karimi et al., 2016; Attouch & Bolte, 2009). Furthermore, if f is gradient dominated (of any order) w.r.t. x?, then x? is an isolated stationary point of f .
Our adopted generalized notion of gradient dominance is strongly tied to the Łojasiewicz gradient inequality from real analytic geometry, established by Łojasiewicz (1963; 1965)1 independently and simultaneously from Polyak (1963), and generalizing the PL inequality. More precisely, this inequality is typically written as: for some C > 0 and θ ∈ ( 1 2 , 1 ] ,
‖∇f(x)‖2 ≥ C · |f(x)− f?|θ (12)
holds for every x ∈ Rn in a small enough open neighborhood of the stationary point x = x?. This inequality is guaranteed for analytic functions Łojasiewicz (1965). More precisely, when x? is a local minimizer of f , the aforementioned relationship is explicitly given by
C =
( p
p− 1
) p−1 p
µ 1 p , θ = p− 1 p . (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 our settings.
The following results in Romero & Benosman (2020) summarized the finite-time convergence of q-RGF (equation 2) and q-SGF (equation 3) in continuous-time sense, which also motivates the main topic in this paper.
Theorem 1 (Romero & Benosman (2020)). Suppose that f : Rn → R is continuously differentiable and µ-gradient dominated of order p ∈ (1,∞) near a strict local minimizer x? ∈ Rn. Let c > 0 and q ∈ (p,∞]. Then, any maximal solution x(·), in the sense of Filippov, to the q-RGF (2) or q-SGF (3) will converge in finite time to x?, provided that ‖x(0)−x?‖2 > 0 is sufficiently small. More precisely, lim t→t?
x(t) = x?, where the convergence time t? <∞ may depend on which flow is used, but in both cases is upper bounded by
t? ≤ ‖∇f(x0)‖ 1 θ− 1 θ′ 2
cC 1 θ ( 1− θθ′ ) , (14) where x0 = x(0), C = ( p p−1 ) p−1 p µ 1 p , θ = p−1p , and θ
′ = q−1q . In particular, given any compact and positively invariant subset S ⊂ D, both flows converge in finite time with the aforementioned convergence time upper bound (which can be tightened by replacing D with S) for any x0 ∈ S. Furthermore, if D = Rn, then we have global finite-time convergence, i.e. finite-time convergence to any maximal solution (in the sense of Filippov) x(·) with arbitrary x0 ∈ Rn.
In essence, the analysis introduced in Romero & Benosman (2020) 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̇(t) = O(E(t)α) for some α < 1. The detailed proof is recalled in Appendix C for completeness.
1For more modern treatments in English, see Łojasiewicz & Zurro (1999); Bolte et al. (2007)

heading: 3 MAIN RESULTS: CONVERGENCE ANALYSIS FOR EULER DISCRETIZATION
text: With the previous discussion on continuous-time gradient flow, now we turn to the algorithm perspective. We propose the following general framework based on forward Euler discretization of the flows with finite-time convergence guarantee.
xk+1 = xk + ηF (xk), η > 0 (15)
where F ∈ {Fq−RGF, Fq−SGF}. We will show later, in Theorem 2, that the simple method leads, for small enough η > 0, to solutions that are O( )-close 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-time flows if the context is clear.

heading: 3.1 CLOSENESS OF THE DISCRETIZATION
text: 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 Euler discretization.
Theorem 2 (Closeness of Discretization). Suppose that f : Rn → R is continuously differentiable, locally Lf -Lipschitz, and µ-gradient dominated of order p ∈ (1,∞) in a compact neighborhood S of a strict local minimizer x? ∈ Rn. Let c > 0 and q ∈ (p,∞]. Then, for a given initial condition x0 ∈ S, any maximal solution x(t), x(0) = x0, (in the sense of Filippov) to the q-RGF given by (2) or the q-SGF flow (3), there exists an arbitrarily small > 0 such that the solution xk of any of the discrete algorithm (15), with sufficiently small η > 0, are -close to x(t), i.e., ‖xk − x(t)‖2 ≤ for |t− kη| < , and s.t. the following bound holds
‖f(xk)− f(x?)‖2 ≤ Lf + [ (f(x0)− f(x?))(1−α) − c̃(1− α)ηk ](1−α) , Lf > 0, k ≤ k?,
‖f(xk)− f(x?)‖2 ≤ Lf , k > k?, (16)
where α = θ θ′ , θ = p−1p , θ ′ = q−1q , c̃ = c (( p p−1 ) p−1 p µ 1 p ) 1 θ ′ and k? = (f(x0)−f(x ?))(1−α) c̃(1−α)η .
The analysis summarized in Theorem 2 is based on tools form hybrid control theory, and is detailed in Appendix D2. Theorem 2 shows that -convergence of xk → x? can be achieved in a finite number of steps upper bounded by k? = (f(x0)−f(x ?))(1−α)
c̃(1−α)η . This is a preliminary convergence result aiming to show the existence of discrete solutions obtained via the proposed discretization algorithms, which are -close to the continuous solutions of the finite-time flows. We also underline here that after xk reaches an -neighborhood of x?, then xk+1 ≈ xk, ∀k > k?, since x? is an equilibrium point of the continuous flows, i.e., ∆f(x?) = 0, e.g. see Definition 2 in Appendix B.

heading: 3.2 CONVERGENCE RATES OF EULER DISCRETIZATION: GENERAL CASE
text: However, the bound (16) does not allow us to have a constructive practical value of the stepsize η, since the pair ( , η) are implicitly related, for ‘sufficiently small’ η (refer to the definition of -closeness and the proof of Theorem 2 in Appendix D). To derive convergence rates of the proposed discretization with practical stepsize η, 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 f is L-Lipschitz smooth of order q ∈ (1, 2], i.e., for any x, y ∈ Rn,
‖∇f(y)−∇f(x)‖2 ≤ L‖y − x‖ q−1 2 . (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 (L, q)-Hölder continuity
2Note 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 Benaı̈m et al. (2005).
(Devolder et al., 2014; Nesterov, 2015), it is easy to find that the condition will lead to the following property:
f(y) ≤ f(x) + 〈∇f(x), y − x〉+ L q ‖y − x‖q2, (18)
which is also called weak smoothness. When q = 2, the function will be Lipschitz smooth, so the above setting is a 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 ∇f(x). The main result is presented in the following theorem, while we defer the proof to Appendix E. . Theorem 3 (Convergence Rate of the general Case). Suppose that f : Rn → R is continuously differentiable, µ-gradient dominated of order q and L-Lipschitz smooth of order q following Assumption 1 and 2, then running q-RGF (equation 2 and equation 15) for K iterations with a stepsize η = L 1 1−q satisfies that f(xK)− f? ≤ ( 1− κ 1 1−q )K (f(x0)− f?), (19)
and running q-SGF (equation 3 and equation 15) for K iterations with η = (nL) 1 1−q satisfies that
f(xK)− f? ≤ ( 1− ( n q 2 κ ) 1 1−q )K (f(x0)− f?), (20)
where n is the dimension number and κ , Lµ . The corresponding iteration complexity are O ( κ 1 q−1 ln 1 ) and O (( n q 2 κ ) 1 q−1 ln 1 ) , respectively.
Remark 3. The above results show that with a constant stepsize, both the q-RGF and q-SGF can attain a linear convergence rate to reach the optimal point. Note that for the classical Lipschitz smooth case (i.e. q = 2), the RHS of the RGF result (equation 19) will reduce to ( 1− κ−1 )K (f(x0)− f?), which is the same as that in (Karimi et al., 2016, Theorem 1); while for SGF (equation 20), it will be( 1− (nκ)−1 )K (f(x0)− f?), which recovers the result in (Beznosikov et al., 2020, Theorem 13)3. So we can conclude that our results extend the classical results in Lipschitz smoothness case.

heading: 3.3 CONVERGENCE RATES OF EULER DISCRETIZATION: STOCHASTIC CASE
text: Attaining the full gradient may be expensive in practical applications due to the large data size, while stochastic optimization algorithms are more applicable in 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., 2018). . Assumption 3 (Unbiased Gradient Estimator). For any given x ∈ Rn, we 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 Eξ[g(x; ξ)] = ∇f(x), Eξ‖g(x; ξ)−∇f(x)‖22 ≤ σ2.
Stochastic q-RGF We present the convergence result of stochastic q-RGF in the following theorem, and defer the proof to Appendix F. For convenience, we denote ψ , qq−1 ∈ [2,+∞]. Theorem 4 (Convergence Rate of the Stochastic RGF). With the setting in Theorem 3, if we further assume for each x ∈ Rn, we only have access to the unbiased estimator of the gradient in Assumption 3, then if we replace the gradient in q-RGF (equation 2) by its unbiased estimator g(x) , 1b(x) ∑b(x) i=1 g(x; ξi) with batch size b(x) ∈ N+. Then for q-RGF (equation 2 and equation 15)
with g(x), if we set η = (ψL) 1 1−q , b(x) ≡ ( 2·(2σ)ψµ 1 1−q ) 2 ψ , then we have
E[f(xK)− f?] ≤ (
1− 2 (2ψ)ψ κ 1 1−q
)K (f(x0)− f?) +
2 . (21)
3Note that 1 n ‖∇f(x)‖−11 sign(∇f(x)) is an 1n -approximate compressor of gradient∇f(x) (Karimireddy
et al., 2019), so we can apply (Beznosikov et al., 2020, Theorem 13) to recover the result.
Stochastic q-SGF The analysis of the Euler discretization of q-SGF in the stochastic case is a bit more complicated. Indeed, note that previously our discussion are based on `2-norm. Here, however, following the argument in Balles et al. (2020), we change the gradient dominance and Lipschitz smoothness assumption to hold in `∞-norm (and its dual norm `1). Assumption 4 (Gradient Dominance and Lipschitz Smoothness under (`1, `∞)-norms). We assume the function f is µ-gradient dominated of order q and L-Lipschitz smooth of order q under `∞-norm (and its dual norm `1), i.e., for any x, y ∈ Rn
q − 1 q ‖∇f(x)‖ q q−1 1 ≥ µ 1 q−1 (f(x)− f?), ‖∇f(y)−∇f(x)‖1 ≤ L‖y − x‖ q−1 ∞ . (22)
Similarly the new smoothness condition above implies that f(y) ≤ f(x) + 〈∇f(x), y − x〉 + L q ‖y − x‖ q ∞ (∀x, y ∈ Rn). And for the gradient estimator, we need the following assumption.
Assumption 5 (SPB Unbiased Gradient Estimator (Safaryan & Richtárik, 2021)). For any given x ∈ Rn, we assume to have only the access of the unbiased gradient estimator under `1-norm, i.e., Eξ[g(x; ξ)] = ∇f(x), Eξ‖g(x; ξ)−∇f(x)‖21 ≤ σ2; and for its mini-batch version g(x) with batch size b(x), we further assume that it satisfies success probability bounds (SPB) property, i.e., for each component of g(x) and ∇f(x) (denoted as gi(x) and∇if(x)), we have ∃ p∗ ∈ ( 12 , 1] such that
P(sign (∇if(x)) = sign (gi(x))) ≥ p∗ > 1
2 , ∀ i ∈ {1, 2, · · · , n}. (23)
Remark 4. Note that similar assumptions under `∞-norm (and its dual norm `1) are widely adapted in the literature of sign-based algorithms, e.g., Karimi et al. (2016); Bernstein et al. (2018a;b); Balles et al. (2020). Here the extra SPB assumption, proposed in Safaryan & Richtárik (2021), is 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(x) will be very similar to∇f(x), so the corresponding probability above should be higher. For more details on the rationality of the assumption, we refer the reader to Safaryan & Richtá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 15) with an unbiased gradient estimator g(x) of batch size b(x) ∈ N+, if we assume the gradient estimator g(x) satisfies Assumption
5, and set η = ( L2ψ−1
2p∗−1
) 1 1−q and b(xk) ≡ ( 2µ 1 1−q
q
) 2 ψ
(2p∗ − 1)−4σ2, it satisfies that
E[f(xK)− f?] ≤ ( 1− (2p∗ − 1)ψ ( κ2ψ−1 ) 1 1−q )K (f(x0)− f?) +
2 . (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 O( )-neighborhood of the optimal value. As a 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 a similar setting. Also for stochastic SGF, we notice that recently Li et al. (2021) provided a similar convergence result of stochastic SGF in the classical setting (i.e., q = 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 an extension of their work.

heading: 4 NUMERICAL EXPERIMENTS
text: In this section, we will use several experiments to verify the effectiveness of our proposed algorithms, more details will be presented in Appendix H.

heading: 4.1 NUMERICAL EXPERIMENTS ON ACADEMIC EXAMPLES
text: Let us 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 acceleration in discrete time.
Example 1 Consider the following function: f : R→ R and f(x) , 1q |x| q , which can be shown to be (q−1)q−1-gradient dominated of order q, and 2-Lipschitz smooth of order q when 1 < q ≤ 2 (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 1 below. The figure shows both sensitivities to stepsizes and performances of algorithms, measured by the optimality gap f(x) − f∗ where f∗ is the optimal value which is 0. We can find that q-RGF and q-SGF, comparing to the classical one (2-RGF) and an over-large one (10-RGF), can accommodate larger stepsize and attain better performances with the best-tuned stepsize4. Also we further plot the theoretical bounds provided in Theorem 3 (in red), we can find that the proposed algorithms attain linear convergence patterns and their optimal stepsize choice is close to those in Theorem 3, so the experiment results matches the theory well in the example.
Example 2 We consider the Rosenbrock functionf : R2 → R, given by f(x1, x2) = (a− x1)2 + b(x2 − x21)2, with parameters a, b ∈ R, which is locally Lipschitz smooth. This function admits exactly one stationary point (x?1, x ? 2) = (a, a
2) for b ≥ 0, and is locally strongly convex, hence locally satisfies gradient dominance of order p = 2, which allows us to select q > 2 in q-RGF and q-SGF to achieve finite-time convergence in conitnuous-time. We report in Figure 2 the mean performance of forward-Euler discretization for q-RGF and q-SGF, with fixed step size5, for several values of q, for 10 random initial conditions in [0, 2]. We observe 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 > 2 the finite-time convergence in continuous time translates to some acceleration in the associated discretization algorithm as well. Similarly for q-SGF, q closer to 2 translates to less accelerated algorithms, with a behavior similar to GD, whereas larger q values lead to accelerated convergence.

heading: 4.2 NUMERICAL EXPERIMENTS ON REAL-WORLD DATA
text: 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 are reported in Appendix H. We underline here that the DNNs are non-convex globally, however, one could assume at least local convexity, hence local gradient dominance of order p = 2, thus, we will select q > 2 in our experiments (see (Remark 7, Appendix H) for more explanations on the choice of q).
4The experiment results show that q-RGF and q-SGF will drive the function value to exactly 0 with certain stepsizes, which generates plots that may exceed the lower limit in figures.
5We did multiple iterations to find the best step size for each algorithm (best values where between 10−4 and 10−2 depending on the algorithm). Details of the step size for each test are given in Appendix H.

heading: 4.2.1 EXPERIMENTS ON SVHN DATASET
text: We test the proposed algorithms to train the same VGG16 CNN model with cross entropy loss on the SVHN dataset. We divided the dataset into a training set of 74 batches with 1000 images each, and a test set of 27 batches of 1000 images each, and ran 20 epochs of training over all the training batches. We tested the discretization of q-RGF (c = 1, q = 2.1, η = 0.04), and of q-SGF (c = 10−3, q = 2.1, η = 0.04) against classical gradient descent (GD), and Adam6. Note from Figures 3, 4 it is clear that q-RGF and q-SGF give a good performance in terms of convergence speed, and final test performance 93%. We can also observe in Figure 4 that q-SGF, and q-RGF converge faster (40 min lead in average) than SGD and Adam for these tests, and reach an overall similar performance on the test-set. Additional numerical results, including GPU runs, can be found in Appendix H.

heading: 5 CONCLUSION
text: We presetned some connections between optimization algorithms and continuous-time representations (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-RGF and q-SGF, whose distinguishing characteristic is their finite-time convergence. We then proposed a forward Euler 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, we conducted numerical experiments on a known deep neural network benchmark, which showed that the proposed discrete algorithms can outperform some state of the art algorithms, when tested on large DNN models.
6We 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 we decided not to report the plots to avoid overloading the figures.

heading: A DISCONTINUOUS SYSTEMS AND DIFFERENTIAL INCLUSIONS
text: Recall that for an initial value problem (IVP)
ẋ(t) = F (x(t)) (25a) x(0) = x0 (25b)
with F : Rn → Rn, the typical way to check for existence of solutions is by establishing continuity of F . Likewise, to establish uniqueness of the solution, we typically seek Lipschitz continuity. When F is discontinuous, we may understand (25a) as the Filippov differential inclusion
ẋ(t) ∈ K[F ](x(t)), (26) where K[F ] : Rn ⇒ Rn denotes the Filippov set-valued map given by
K[F ](x) , ⋂ δ>0 ⋂ µ(S)=0 coF (Bδ(x) \ S), (27)
where µ denotes the usual Lebesgue measure and co the convex closure, i.e. closure of the convex hull co. For more details, see Paden & Sastry (1987). We can generalize (26) to the differential inclusion Bacciotti & Ceragioli (1999)
ẋ(t) ∈ F(x(t)), (28) where F : Rn ⇒ Rn is some set-valued map. Definition 1 (Carathéodory/Filippov solutions). We say that x : [0, τ) → Rn with 0 < τ ≤ ∞ is a Carathéodory solution to (28) if x(·) is absolutely continuous and (28) is satisfied a.e. in every compact subset of [0, τ). Furthermore, we say that x(·) is a maximal Carathéodory solution if no other Carathéodory solution x′(·) exists with x = x′|[0,τ). If F = K[F ], then Carathéodory solutions are referred to as Filippov solutions.
For a 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 Cortés (2008). In particular, it can be established that Filippov solutions to (25) exist, provided that the following assumption (Assumption 6) holds. Assumption 6 (Existence of Filippov solutions). F : Rn → Rn is defined almost everywhere (a.e.) and is Lebesgue-measurable in a non-empty open neighborhood U ⊂ Rn of x0 ∈ Rn. Further, F is locally essentially bounded in U , i.e., for every point x ∈ U , F is bounded a.e. in some bounded neighborhood of x.
More generally, Carathéodory solutions to (28) exist (now with arbitrary x0 ∈ Rn), provided that the following assumption (Assumption 7) holds. Assumption 7 (Existence of Carathéodory solutions). F : Rn ⇒ Rn has nonempty, compact, and convex values, and is upper semi-continuous.
Filippov & Arscott (1988) proved that, for the Filippov set-valued map F = K[F ], Assumptions 6 and 7 are equivalent (with arbitrary x0 ∈ Rn in Assumption 6). Uniqueness of the solution requires further assumptions. Nevertheless, we can characterize the Filippov set-valued map in a similar manner to Clarke’s generalized gradient, as seen in the following proposition. Proposition 1 (Theorem 1 of Paden & Sastry (1987)). Under Assumption 6, we have
K[F ](x) = {
lim k→∞
F (xk) : xk ∈ Rn \ (NF ∪ S) s.t. xk → x }
(29)
for some (Lebesgue) zero-measure set NF ⊂ Rn and any other zero-measure set S ⊂ Rn. In particular, if F is continuous at a fixed x, then K[F ](x) = {F (x)}.
For instance, for the GF (1), we have K[−∇f ](x) = {−∇f(x)} for every x ∈ Rn, provided that f is continuously differentiable. Furthermore, if f is only locally Lipschitz continuous and regular (see Definition 3 of Appendix B), then K[−∇f ](x) = −∂f(x), where
∂f(x) , { lim k→∞ ∇f(xk) : xk ∈ Rn \ Nf s.t. xk → x }
(30)
denotes Clarke’s generalized gradient Clarke (1981) of f , with Nf denoting the zero-measure set over which f is not differentiable (Rademacher’s theorem). It can be established that ∂f 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-time variant of subgradient descent methods.

heading: B FINITE-TIME STABILITY OF DIFFERENTIAL INCLUSIONS
text: We are now ready to focus on extending some notions from traditional Lipschitz continuous systems to differential inclusions. Definition 2. We say that x? ∈ Rn is an equilibrium of (28) if x(t) ≡ x? on some small enough nondegenerate interval is a Carathéodory solution to (28). In other words, if and only if 0 ∈ F(x?). We say that (28) is (Lyapunov) stable at x? ∈ Rn if, for every ε > 0, there exists some δ > 0 such that, for every maximal Carathéodory solution x(·) of (28), we have ‖x0− x?‖2 < δ =⇒ ‖x(t)− x?‖2 < ε for every t ≥ 0 in the interval where x(·) is defined. Note that, under Assumption 7, if (28) is stable at x?, then x? is an equilibrium of (28) Bacciotti & Ceragioli (1999). Furthermore, we say that (28) is (locally and strongly) asymptotically stable at x? ∈ Rn if is stable at x? and there exists some δ > 0 such that, for every maximal Carathéodory solution x : [0, τ) → Rn of (28), if ‖x0 − x?‖2 < δ then x(t) → x? as t → τ . Finally, (28) is (locally and strongly) finite-time stable at x? if it is asymptotically stable and there exists some δ > 0 and T : Bδ(x?) → [0,∞) such that, for every maximal Carathéodory solution x(·) of (28) with x0 ∈ Bδ(x?), we have limt→T (x0) x(t) = x?.
We will now construct a 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 E(t)α (31)
a.e. in t ≥ 0, with c, E(0) > 0 and α < 1. Then, there exists some t? > 0 such that E(t) > 0 for t ∈ [0, t?) and E(t?) = 0. Furthermore, t? > 0 can be bounded by
t? ≤ E(0) 1−α
c(1− α) , (32)
with this bound tight whenever (31) holds with equality. In that case, but now with α ≥ 1, then E(t) > 0 for every t ≥ 0, with limt→∞ E(t) = 0. This will be represented by t? = ∞, with E(∞) , limt→∞ E(t).
Proof. Suppose that E(t) > 0 for every t ∈ [0, T ] with T > 0. Let t? be the supremum of all such T ’s, thus satisfying E(t) > 0 for every t ∈ [0, t?). We will now investigate E(t?). First, by continuity of E , it follows that E(t?) ≥ 0. Now, by rewriting
Ė(t) ≤ −c E(t)α ⇐⇒ d dt
[ E(t)1−α
1− α
] ≤ −c, (33)
a.e. in t ∈ [0, t?), we can thus integrate to obtain
E(t)1−α 1− α − E(0) 1−α 1− α ≤ −c t, (34)
everywhere in t ∈ [0, t?), which in turn turn leads to
E(t) ≤ [E(0)1−α − c(1− α)t]1/(1−α) (35)
and
t ≤ E(0) 1−α − E(t)1−α c(1− α) ≤ E(0) 1−α c(1− α) , (36)
where the last inequality follows from E(t) > 0 for every t ∈ [0, t?). Taking the supremum in (36) then leads to the upper bound (32). Finally, we conclude that E(t?) = 0, since E(t?) > 0 is impossible given that it would mean, due to continuity of E , that there exists some T > t? such that E(t) > 0 for every t ∈ [0, T ], thus contradicting the construction of t?.
Finally, notice that if E 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 α ≥ 1, and E is a tight solution to the differential inequality (31), i.e. E(t) = [E(0)1−α − c(1 − α)t]1/(1−α), then clearly E(t) > 0 for every t ≥ 0 and E(t) → 0 as t→∞.
Cortés & Bullo (2005) proposed (Proposition 2.8) a Lyapunov-based criterion to establish finitetime stability of discontinuous systems, which fundamentally coincides with our Lemma 1 for the particular choice of exponent α = 0. Their proposition was, however, directly based on Theorem 2 of Paden & Sastry (1987). Later, Cortés (2006) proposed a second-order Lyapunov criterion, which, on the other hand, fundamentally translates to E(t) , V (x(t)) being strongly convex. Finally, Hui et al. (2009) generalized Proposition 2.8 of Corté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-based results, by exploiting our Lemma 1. More precisely, given a Laypunov candidate function V (·), the objective is to set E(t) , V (x(t)), and we aim to check that the conditions of Lemma 1 hold. To do this, and assuming V 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 (28), given by
V̇ (x) , {a ∈ R : ∃v ∈ F(x) s.t. a = p · v, ∀p ∈ ∂V (x)}, (37) for each x ∈ D. Notice that, under Assumption 7 for Filippov differential inclusions F = K[F ], the set-valued time derivative of V thus coincides with with the set-valued Lie derivative LFV (·). Indeed, more generally V̇ could be seen as a set-valued Lie derivative LFV w.r.t. the set-valued map F . Definition 3. V (·) is said to be regular if every directional derivative, given by
V ′(x; v) , lim h→0 V (x+ h v)− V (x) h , (38)
exists and is equal to
V ◦(x; v) , lim sup x′→xh→0+ V (x′ + h v)− V (x′) h , (39)
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 or continuously differentiable to ensure that it is Lipschitz and regular. Assumption 8. V : D → R is locally Lipscthiz continuous and regular, with D ⊆ Rn open.
Under Assumption 8, Clarke’s generalized gradient
∂V (x) , {p ∈ Rn : V ◦(x; v) ≥ p · v,∀v ∈ Rn} (40) is non-empty for every x ∈ D, and is also given by
∂V (x) = { lim k→∞ ∇V (xk) : xk ∈ Rn \ NV s.t. xk → x } , (41)
where NV denotes the set of points in D ⊆ Rn where V is not differentiable (Rademacher’s theorem) Clarke (1981).
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) , V (x(t)) associated with an arbitrary Carathéodory solution x(·) to the differential inclusion (28). Lemma 2 (Lemma 1 of Bacciotti & Ceragioli (1999)). Under Assumption 8, given any Carathéodory solution x : [0, τ)→ Rn to (28), then E(t) , V (x(t)) is absolutely continuous and Ė(t) = d dtV (x(t)) ∈ V̇ (x(t)) a.e. in t ∈ [0, τ).
We are now ready to state and prove our Lyapunov-based sufficient condition for finite-time stability of differential inclusions.
Theorem 6. Suppose that Assumptions 7 and 8 hold for some set-valued map F : Rn ⇒ Rn and some function V : D → R, where D ⊆ Rn is an open and positively invariant neighborhood of a point x? ∈ Rn. Suppose that V is positive definite w.r.t. x? and that there exist constants c > 0 and α < 1 such that sup V̇ (x) ≤ −c V (x)α (42) a.e. in x ∈ D. Then, (28) is finite-time stable at x?, with settling time upper bounded by
t? ≤ V (x0) 1−α
c(1− α) , (43)
where x(0) = x0. In particular, any Carathéodory solution x(·) with x(0) = x0 ∈ D will converge in finite time to x? under the upper bound (43). Furthermore, if D = Rn, then (28) is globally finite-time stable. Finally, if V̇ (x) is a singleton a.e. in x ∈ D and (42) holds with equality, then the bound (43) is tight.
Proof. Note that, by Proposition 1 of Bacciotti & Ceragioli (1999), 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 x : [0, t?) → Rn to (28) with x(0) = x0 6= x?, we know by Lemma 2, that E(t) = V (x(t)) is absolutely continuous with Ė(t) ∈ V̇ (x(t)) a.e. in t ∈ [0, t?]. Therefore, we have
Ė(t) ≤ sup V̇ (x(t)) ≤ −c V (x(t))α = −c E(t)α (44)
a.e. in t ∈ [0, t?]. Since E(0) = V (x0) > 0, given that x0 6= x?, the result then follows by invoking Lemma 1 and noting that E(t?) = 0 ⇐⇒ V (t?, x(t?)) = 0 ⇐⇒ x(t?) = x?.
Finite-time stability still follows without Assumption 7, provided that x? is an equilibrium of (28). In practical terms, this means that trajectories starting arbitrarily close to x? may not actually exist, but nevertheless there exists a neighborhood D of x? over which, any trajectory x(·) that indeed exists and starts at x(0) = x0 ∈ D must converge in finite time to x?, with settling time upper bounded by T (x0) (the bound still tight in the case that (42) holds with equality).

heading: C PROOF OF THEOREM 1
text: Let us focus on the q-RGF (2) (the case of q-SGF (3) follows exactly the same steps) with the candidate Lyapunov function V , f − f(x?). 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 to 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 x̃? sufficiently near x? such that x̃? is both a stationary point of f , and satisfies f(x̃?) > f(x?), since x? is a strict local minimizer of f . But then, we would have
0 = p− 1 ψ ‖∇f(x̃?)‖ ψ p−1 2 ≥ µ 1 p−1 (f(x̃?)− f(x?)) > 0, (45)
and subsequently 0 > 0, which is absurd.
Therefore, F (x) , −c∇f(x)/‖∇f(x)‖ q−2 q−1 2 is continuous for every x ∈ D \ {0}, for some small enough open neighborhood D of x?. Let us assume that D is 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 ‖F (x)‖2 = c‖∇f(x)‖ 1 q−1 2 with q ∈ (p,∞] ⊂ (1,∞], i.e., 1q−1 ∈ [0,∞). If q =∞, which results in the normalized gradient flow ẋ = − ∇f(x)‖∇f(x)‖2 proposed by Cortés (2006), then ‖F (x)‖2 = c > 0. We can thus show that F (x) is discontinuous at x = 0 for q = ∞. On the other hand, if q ∈ (p,∞) ⊂ (1,∞), then we have ‖F (x)‖2 → 0 as x → x?, and thus F (x) is continuous (but not Lipschitz) at x = x?. Regardless, we may freely focus exclusively on D \ {x?} since {x?} is obviously a zero-measure set.
Let F , K[F ]. We thus have, for each x ∈ D \ {x?},
sup V̇ (x) = sup {a ∈ R : ∃v ∈ F(x) s.t. a = p · v,∀p ∈ ∂V (x)} (46a) = sup {∇V (x) · v : v ∈ F(x)} (46b) = ∇V (x) · F (x) (46c)
= −c‖∇f(x)‖2− q−2 q−1
2 (46d)
= −c‖∇f(x)‖ 1 θ′ 2 (46e) ≤ −c[C(f(x)− f(x?))θ] 1θ′ (46f)
= −cC 1θ′ V (x) θθ′ . (46g)
Since θθ′ < 1, given that s > 1 7→ s−1 s is strictly increasing, then the conditions of Theorem 6 are satisfied. In particular, we have finite-time stability at x? with a settling time t? upper bounded by
t? ≤ (f(x0)− f(x ?))1− θ θ′ cC 1 θ′ ( 1− θθ′ ) ≤ (‖∇f(x0)‖2/C) 1θ (1− θθ′ ) cC 1 θ′ ( 1− θθ′ ) = ‖∇f(x0)‖ 1θ− 1θ′2 cC 1 θ ( 1− θθ′ ) (47) for each x0 ∈ D, which completes the proof.

heading: D PROOF OF THEOREM 2
text: 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 as a simple case of a hybrid systems with one differential inclusion, with a 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 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 : Rn ⇒ Rn, and its discretization in time by Fd : Rn ⇒ Rn. We first recall a 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, )-closeness). Given T > 0, > 0, η > 0, two solutions xt : [0, T ]→ Rn, and xk : {0, 1, 2, ...} → Rn are (T, )-close if: (a) for all t ≤ T there exists k ∈ {1, 2, ...} such that |t− kη| < , and ‖xt(t)− xk(k)‖2 < , (b) for all k ∈ {1, 2, ...} there exists t ≤ T such that |t− kη| < , and ‖xt(t)− xk(k)‖2 < .
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 inclusion7. Theorem 7. (Closeness of continuous and discrete solutions on compact domains) Consider the differential inclusion Ẋ(t) ∈ F(X(t)), (48) for a given set-valued mapping F : Rm ⇒ Rm assumed to be outer semicontinuous, locally bounded, nonempty, and with convex values for every x ∈ C, for some closed set C ⊆ Rm. Consider the discrete-time system represented by the flow Fd : Rn ⇒ Rn, such that, for each compact setK ⊂ Rn, there exists ρ ∈ K∞, and η? > 0 such that for each x ∈ K and each η ∈ (0, η?],
Fd(x) ⊂ x+ η conF(x+ ρ(η)B) + ηρ(η)B. (49) 7A set-valued mapping F : Rn ⇒ Rn is outer semicontinuous if for each sequence {xi}∞i=1 converging to a point x ∈ Rn and each sequence yi ∈ F(xi) converging to a point y, it holds that y ∈ F(x). It is locally bounded if, for each x ∈ Rn, there exists compact sets K,K′ ⊂ Rn such that x ∈ K and F(K) , ∪x∈KF(x) ⊂ K ′ . In what follows, we use the following notations: Given a set A, conA denotes the convex hull, and B denotes the closed unit ball in a Euclidean space.
Then, for every compact set K ⊂ Rn, every > 0, and every time horizon T ∈ R≥0 there exists η? > 0 such that: for any η ∈ (0, η?] and any discrete solution xk with xk(0) ∈ K + δB, δ > 0, there exists a continuous solution xt with xt(0) ∈ K such that xk and xt are (T, )-close.
To prove Theorem 2 we will use the results of Theorem 7, where we will have to check that condition (49) is 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 us examine their discretization by forward-Euler.
The mapping Fd in this case is a singleton, given by
Fd(x) , x+ ηF (x), (50)
where η > 0, which clearly satisfies condition (49).
Then, using Theorem 7 we conclude about the (T, )-closeness between the continuous-time solutions of the flows F : q-RGF (2), q-SGF (3), and the discrete-time solutions. Finally, using the Lyapunov function V = f − f(x?) as defined in the proof of Theorem 1, together with inequalities (46g), (35), and a local Lipschitz bound on f , one can derive the weak convergence bound given by (16), as follows:
‖f(xk)− f(x?)− (f(xt)− f(x?))‖2 = ‖f(xk)− f(xt)‖2 ≤ ̃ = Lf , Lf > 0, > 0, ‖f(xk)− f(x?)‖2 − ‖(f(xt)− f(x?))‖2 ≤ ‖f(xk)− f(xt)‖2 ≤ ̃, ‖f(xk)− f(x?)‖2 ≤ ̃+ ‖f(xt)− f(x?)‖2, ‖f(xk)− f(x?)‖2 ≤ ̃+ [(f(x0)− f(x?))(1−α) − c̃(1− α)ηk]1/(1−α), for k ≤ k?, (51)
where α = θ θ′ , θ = p−1ψ , θ ′ = q−1q , c̃ = c (( ψ p−1 ) p−1 ψ µ 1 ψ ) 1 θ ′ , k? = (f(x0)−f(x ?))(1−α) c̃(1−α)η .
Next, the case for k > k? is rather straightforward: Indeed, for t > t? by finite-time convergence result, we have xt = x?, which directly leads to the bound ‖f(xk)− f(x?)‖2 ≤ Lf , k > k?, since the term ‖(f(xt)− f(x?))‖2 in (51) vanishes.

heading: E PROOF OF THEOREM 3
text: Proof. We divide the discussion by different flows8.
Proof of q-RGF: Following the definitions of smoothness, we have
f(xk+1) ≤ f(xk) + 〈∇f(xk), xk+1 − xk〉+ L
q ‖xk+1 − xk‖q2
= f(xk)− γ ‖∇f(xk)‖22 ‖∇f(xk)‖ q−2 q−1 2 + Lγq q ‖∇f(xk)‖q2 ‖∇f(xk)‖ q(q−2) q−1 2
= f(xk)− ( γ − Lγ q
q
) ‖∇f(xk)‖ q q−1 2
≤ f(xk)− q − 1 q L 1 1−q ‖∇f(xk)‖ q q−1 2
≤ f(xk)− q − 1 q L 1 1−q q q − 1 µ 1 q−1 (f(xk)− f?)
= f(xk)− κ 1 1−q (f(xk)− f?)
(52)
8Note that here for convenience, we fix the order in gradient dominance as q, while previous discussion assumes that q > p.
so subtract both sides by f?, we have f(xk+1)− f? ≤ ( 1− κ 1 1−q ) (f(xk)− f?), (53)
which verifies the conclusion by recursion.
Proof of q-SGF: Similarly, for the q-SGF case, we have
f(xk+1) ≤ f(xk) + 〈∇f(xk), xk+1 − xk〉+ L
q ‖xk+1 − xk‖q2
= f(xk)− γ‖∇f(xk)‖ 1 q−1 1 〈∇f(xk), sign (∇f(xk))〉+
Lγqn q 2
q ‖∇f(xk)‖
q q−1 1
= f(xk)− ( γ − n q 2Lγq
q
) ‖∇f(xk)‖ q q−1 1
≤ f(xk)− q − 1 q (n q 2L) 1 1−q ‖∇f(xk)‖ q q−1 1
≤ f(xk)− q − 1 q (n q 2L) 1 1−q q q − 1 µ 1 q−1 (f(xk)− f?),
(54)
so we have f(xk+1)− f? ≤ ( 1− (n q 2 κ) 1 1−q ) (f(xk)− f?). (55)
By the inequality e−x ≥ 1− x, we can get that the complexity of the above algorithm with q-RGF and q-SGF are
O ( κ 1 q−1 ln ∆ ) and O (( n q 2 κ ) 1 q−1 ln ∆ ) , (56)
which verifies the conclusion.
F PROOF OF STOCHASTIC q-RGF (THEOREM 4)
Proof. Following the definitions of smoothness, we have
f(xk+1) ≤ f(xk) + 〈∇f(xk), xk+1 − xk〉+ L
q ‖xk+1 − xk‖q2
= f(xk)− γk 〈 ∇f(xk)− g(xk) + g(xk),
g(xk)
‖g(xk)‖ q−2 q−1 2
〉 + Lγqk q
‖g(xk)‖q2 ‖g(xk)‖ q−2 q−1 2
= f(xk)− ( γk −
Lγqk q ) ‖g(xk)‖ψ2 − γk 〈 ∇f(xk)− g(xk),
g(xk)
‖g(xk)‖ q−2 q−1 2
〉
≤ f(xk)− ( γk −
Lγqk q ) ‖g(xk)‖ψ2 + γk 1 q ∥∥∥∥∥∥ g(xk)‖g(xk)‖ q−2q−12 ∥∥∥∥∥∥ q
2
+ 1
ψ ‖∇f(xk)− g(xk)‖ψ2  = f(xk)− ( γk ψ − Lγqk q ) ‖g(xk)‖ψ2 + γk ψ ‖∇f(xk)− g(xk)‖ψ2 ,
(57)
where the second inequality comes from the Young’s inequality. Then note that by Jensen’s inequality,
‖∇f(xk)‖ψ2 = 2 ψ ∥∥∥∥12(∇f(xk)− g(xk) + g(xk)) ∥∥∥∥ψ 2 ≤ 2ψ−1 ( ‖g(xk)‖ψ2 + ‖∇f(xk)− g(xk)‖ ψ 2 ) =⇒ − ‖g(xk)‖ψ2 ≤ −2 1−ψ‖∇f(xk)‖ψ2 + ‖∇f(xk)− g(xk)‖ ψ 2
(58)
note that the setting of γk will ensure the coefficient of ‖g(xk)‖ψ2 to be negative, so we have f(xk+1) ≤ f(xk)− ( γk ψ − Lγqk q )( 21−ψ‖∇f(xk)‖ψ2 − ‖∇f(xk)− g(xk)‖ ψ 2 ) + γk ψ ‖∇f(xk)− g(xk)‖ψ2
= f(xk)− 21−ψ ( γk ψ − Lγqk q ) ‖∇f(xk)‖ψ2 + ( 2γk ψ − Lγqk q ) ‖∇f(xk)− g(xk)‖ψ2 ,
(59)
then take expectation on both sides, by the bounded variance and gradient dominance, we have
Ef(xk+1) ≤ E [ f(xk)− 21−ψ ( γk ψ − Lγqk q ) ‖∇f(xk)‖ψ2 + ( 2γk ψ − Lγqk q )( σ2
b(xk)
)ψ 2 ]
≤ E [ f(xk)− 21−ψ ( γk ψ − Lγqk q ) pµ 1 q−1 (f(xk)− f?) + ( 2γk ψ − Lγqk q )( σ2
b(xk)
)ψ 2 ] (60)
so subtract both sides by f?, we have
E[f(xk+1)− f?] ≤ E [( 1− 21−ψ ( γk ψ − Lγqk q ) pµ 1 q−1 ) (f(xk)− f?) + ( 2γk ψ − Lγqk q )( σ2
b(xk)
)ψ 2 ] ,
(61)
set γk ≡ (pL) 1 1−q , b(xk) ≡ b2 = ( 2·(2σ)ψµ 1 1−q ) 2 ψ and
K =
⌈ (2ψ) ψ
2κ 1
1−q log
( 2∆ )⌉ ,
we have E[f(xK)− f?] ≤ E [(
1− 2 (2ψ)ψ κ 1 1−q
) (f(xk)− f?) + 2σψ
ψψbψ L
1 1−q ] ≤ E [( 1− 2
(2ψ)ψ κ
1 1−q )K ∆ + 2σψ
ψψbψ L
1 1−q K−1∑ i=0 ( 1− 2 (2ψ)ψ κ 1 1−q )i]
≤ E (1− 2 (2ψ)ψ κ 1 1−q )K ∆ + 2σψ ψψbψ L 1 1−q
1 1− (
1− 2 (2ψ)ψ
κ 1 1−q
) 
= E [( 1− 2
(2ψ)ψ κ
1 1−q )K ∆ + 2σψ
ψψbψ L
1 1−q · (2ψ)
ψ
2 κ
1 q−1
]
= E [( 1− 2
(2ψ)ψ κ
1 1−q )K ∆ + (2σ)ψµ 1 1−q
bψ
]
≤ E [ exp ( −2κ 1 1−q
(2ψ)ψ K
) ∆ + (2σ)ψµ 1 1−q
bψ ] ≤
2 + 2 = ,
(62)
while the total sample complexity is (note that 1ψ + 1 q = 1, q ∈ (1, 2], which implies ψ ∈ [2,+∞))
K · b2 ≥ (2ψ) ψ
2κ 1
1−q log
( 2∆ ) · ( 2 · (2σ)ψµ 1 1−q ) 2 ψ = O ( σ2κ 1 q−1µ− 2 qψψ − 2 ψ log ∆ ) , (63)
which verifies the conclusion.
G PROOF OF STOCHASTIC q-SGF (THEOREM 5)
Proof. Note that, as mentioned in Assumption 4 and 5, here the gradient dominance and Lipschitz smoothness is defined under (`1, `∞)-norms. Following the definitions of smoothness, we have (note that ψ = qq−1 )
f(xk+1) ≤ f(xk) + 〈∇f(xk), xk+1 − xk〉+ L
q ‖xk+1 − xk‖q∞
= f(xk)− γk‖g(xk)‖ 1 q−1 1 〈∇f(xk), sign (g(xk))〉+ Lγqk q ‖g(xk)‖ q q−1 1 · ‖sign (g(xk))‖ q ∞
= f(xk)− γk‖g(xk)‖ 1 q−1 1 〈∇f(xk), sign (g(xk))〉+ Lγqk q ‖g(xk)‖ q q−1 1 ,
(64)
conditioning on xk, we have
E[f(xk+1) |xk] ≤ f(xk)− E [ γk‖g(xk)‖ 1 q−1 1 〈∇f(xk), sign (g(xk))〉 |xk ] + E [ Lγqk q ‖g(xk)‖ q q−1 1 |xk ] , (65)
note that for each component of g(xk), we have E [ ‖g(xk)‖ 1 q−1 1 sign (gi(xk)) |xk ] = E [ ‖g(xk)‖ 1 q−1 1 P(sign (∇if(xk)) = sign (gi(xk))) sign (∇if(xk))
− ‖g(xk)‖ 1 q−1 1 P(sign (∇if(xk)) 6= sign (gi(xk))) sign (∇if(xk)) |xk
]
= E [ ‖g(xk)‖ 1 q−1 1 (2P(sign (∇if(xk)) = sign (gi(xk)))− 1) sign (∇if(xk)) |xk ] ,
(66)
then with the SPB condition in Assumption 5, we have
P(sign (∇if(xk)) = sign (gi(xk))) ≥ p∗ > 1
2 ,
so we have
E[f(xk+1) |xk] ≤ f(xk)− E [ γk‖g(xk)‖ 1 q−1 1 (2p ∗ − 1)〈sign (∇f(xk)),∇f(xk)〉 |xk ] + E [ Lγqk q ‖g(xk)‖ q q−1 1 |xk ] ≤ f(xk)− E [ γk(2p ∗ − 1)‖g(xk)‖ 1 q−1 1 ‖∇f(xk)‖1 |xk ] + E [ Lγqk q ‖g(xk)‖ q q−1 1 |xk
] ≤ f(xk)− γk(2p∗ − 1)‖∇f(xk)‖ q q−1 1 + Lγqk q E [ ‖g(xk)‖ q q−1 1 |xk
] (67)
where the last inequality comes from the convexity of ‖·‖ 1 q−1 1 . Then for the last term in the RHS, by decomposition, we have
‖g(xk)‖ψ1 = 2 ψ ∥∥∥∥12(∇g(xk)− f(xk) + f(xk)) ∥∥∥∥ψ 1 ≤ 2ψ−1 ( ‖f(xk)‖ψ1 + ‖∇f(xk)− g(xk)‖ ψ 1 ) ,
(68)
so we have (recall that ψ = qq−1 )
E[f(xk+1) |xk]
≤ f(xk)− γk(2p∗ − 1)‖∇f(xk)‖ q q−1 1 +
Lγqk2 ψ−1 q E [ ‖f(xk)‖ψ1 + ‖∇f(xk)− g(xk)‖ ψ 1 |xk ] ≤ f(xk)− ( (2p∗ − 1)γk − Lγqk2 ψ−1
q
) ‖∇f(xk)‖ q q−1 1 + Lγqk2 ψ−1
q
( σ2
b(xk)
)ψ 2
≤ f(xk)− ( (2p∗ − 1)γk − Lγqk2 ψ−1
q
) qµ 1 q−1
q − 1 (f(xk)− f?) +
Lγqk2 ψ−1
q
( σ2
b(xk)
)ψ 2
,
(69)
so take
γk ≡ ( L2ψ−1
2p∗ − 1
) 1 1−q
, b(xk) ≡ b2 =
( 2µ 1 1−q
q
) 2 ψ
(2p∗ − 1)−4σ2 − 2 ψ ,
and
K = ⌈ (2p∗ − 1)−ψ ( κ2ψ−1 ) 1 q−1 ln 2∆ ⌉ ,
we have
E[f(xK)− f?]
≤ E (1− 1 ψ (2p∗ − 1)ψ ( L2ψ−1 ) 1 1−q qµ 1 q−1 q − 1 ) (f(xK−1)− f?) + ( L2ψ−1 ) 1 1−q
q(2p∗ − 1)ψ
( σ2
b2
)ψ 2  = E (1− (2p∗ − 1)ψ(κ2ψ−1) 11−q )(f(xK−1)− f?) + (L2ψ−1) 11−q q(2p∗ − 1)ψ ( σ2 b2 )ψ 2
 ≤ ( 1− (2p∗ − 1)ψ ( κ2ψ−1 ) 1 1−q )K (f(x0)− f?) + ( L2ψ−1 ) 1 1−q
q(2p∗ − 1)ψ
( σ2
b2
)ψ 2
· 1 (2p∗ − 1)ψ(κ2ψ−1) 1 1−q
≤ exp ( −(2p∗ − 1)ψ ( κ2ψ−1 ) 1 1−qK ) ∆ +
(µ) 1 1−q
q(2p∗ − 1)2ψ
( σ2
b2
)ψ 2
= 2 + 2 = ,
(70)
which concludes the proof9.
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/ ) (Karimi et al. (2016), Theorem 4), whereas here our result is a linear convergence iteration complexity (i.e., O(log (1/ ))) to achieve the -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 is a reasonable option.
9Different from stochastic RGF, here we do not discuss the sample complexity, because the extra SPB assumption is defined on the “oracle”, i.e., the mini-batch estimator g(x), so the concern here should be the oracle complexity instead, which will be the iteration number K here.

heading: H ADDITIONAL EXPERIMENT DETAILS AND NUMERICAL RESULTS
text: 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 used10 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.1- 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, η = 10−2
• 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: https://pytorch.org/docs/stable/optim.html.
• GD: η = 4.10−2, µ = 0.9, Nesterov=False • RGF: η = 4.10−2
• SGF: η = 4.10−3
• ADAM: η = 8.10−4 (remaining coefficients=nominal values) • RMS: η = 10−3 (remaining coefficients=nominal values) • ADAGRAD: η = 10−3 (remaining coefficients=nominal values) • ADADELTA: η = 4.10−2, ρ = 0.9, = 10−6, weight decay = 0
Remark 7. Choice of q: The settling time upper bound (15) decreases as q →∞, 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 q cannot be too large. Therefore, assuming p to be not too large, it appears that q ∈ (p, p + δ] works best, with δ > 0 as small as needed to avoid numerical issues. For instance, if we know the cost function to be strongly convex (locally), then we search for q slightly larger than p = 2 at first, but continue to increase until performance deteriorates. If, on the other hand, we don’t know the order p > 1, then it’s currently unclear how to choose q. We 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://arxiv.org/abs/1710.06910). Indeed, since convexity readily leads to gradient dominance of order p =∞, it suffices that a slightly stronger form of it holds (but weaker than strong convexity), in order to have p <∞, and thus for us to be able to choose q > p.
H.3 EXPERIMENT 6: GPU IMPLEMENTATION
To check if the numerical results obtained on CPU, more specifically the acceleration trends, hold true on a GPU, we run some extra tests on a 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 on SVHN dataset. We tested the proposed algorithms to train the VGG16 CNN model with cross entropy loss. We divided the dataset into a training set of 74 batches with 1000 images each, and a test set of 27 batches of 1000 images each, and ran 20 epochs of training over all the training batches. We tested Euler discretization of q-RGF (c = 1, q = 2.1, η = 0.04 ), and Euler discretization of q-SGF (c = 10−3, q = 2.1, η = 0.04 ) against GD (η = 0.1) and Adam (same optimal tuning as in Section 4.2).
In Figures 5 , 6 we can see that both algorithms, Euler q-RGF and Euler q-SGF, converge faster than GD and Adam for these tests, and reach the same performance on the test-set.
10In all the tests, for q-RGF and q-SGF c = 1 unless otherwise stated.

Review summaries:
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.

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.