A Unified Discretization Framework for Differential Equation Approach with Lyapunov Arguments for Convex Optimization
Authors: Kansei Ushiyama
Shun Sato
Takayasu Matsuo
Venue: NeurIPS 2023 poster (2023)
Keywords: Convex optimization
Numerical analysis
Ordinary differential equations
Convergence estimate
TL;DR: We give a unified discretization method that has been desired in the differential equation approach with rate-revealing Lyapunov functionals for convex optimization.

Abstract: The differential equation (DE) approach for convex optimization, which relates optimization methods to specific continuous DEs with rate-revealing Lyapunov functionals, has gained increasing interest since the seminal paper by Su--Boyd--Candès (2014).
However, the approach still lacks a crucial component to make it truly useful: there is no general, consistent way to transition back to discrete optimization methods. Consequently, even if we derive insights from continuous DEs, we still need to perform individualized and tedious calculations for the analysis of each method.
This paper aims to bridge this gap by introducing a new concept called  ``weak discrete gradient'' (wDG), which consolidates the conditions required for discrete versions of gradients in the DE approach arguments.
We then define abstract optimization methods using wDG and provide abstract convergence theories that parallel those in continuous DEs.
We demonstrate that many typical optimization methods and their convergence rates can be derived as special cases of this abstract theory.
The proposed unified discretization framework for the differential equation approach to convex optimization provides an easy environment for developing new optimization methods and achieving competitive convergence rates with state-of-the-art methods, such as Nesterov's accelerated gradient.

A Unified Discretization Framework for Differential Equation Approach with Lyapunov Arguments for Convex Optimization
Kansei Ushiyama
Shun Sato
The University of Tokyo, Tokyo, Japan ushiyama- -asaama0aaaaii0700 ecc. u-tokyo. jp.
The University of Tokyo, Tokyo, Japan shun@mist. i. uutooyo jc.jp
Takayasu Matsuo
The University of Tokyo, Tokyo, Japan matsuošmist. u-tokyo jp
Abstract
The differential equation (DE) approach for convex optimization, which relates optimization methods to specific continuous DEs with rate-revealing Lyapunov functionals, has gained increasing interest since the seminal paper by Su-Boyd- Candès (2014). However, the approach still lacks crucial component make it truly useful: there is no general, consistent way to transition back to discrete optimization methods. Consequently, even if we derive insights from continuous DEs, we still need to perform individualized and tedious calculations for the analysis of each method. This paper aims to bridge this gap by introducing a new concept called "weak discrete gradient" (wDG), which consolidates the conditions required for discrete versions gradients in the DE approach arguments. then define abstract optimization methods using wDG and provide abstract convergence theories that parallel those in continuous DEs. We demonstrate that many typical optimization methods and their convergence rates be derived as special cases this abstract theory. The proposed unified discretization framework for the differential equation approach convex optimization provides easy environment for developing new optimization methods and achieving competitive convergence rates with state-of-the-an methods, such as Nesterov's accelerated gradient.
Introduction
In this paper, consider unconstrained convex optimization problems:
min (x)
(1)
#ERd
Various optimization methods, such as standard gradient descent and Nesterov's accelerated gradient methods (Nesterov, 1983), are known for these problems. The convergence rates of these methods have been intensively investigated based on the classes of objective functions (L-smooth and/or μ strongly convex). We focus on the convergence rate function values ff (=) while the rates for (z)) || or (*) => have also been discussed. Topics particularly relevant to this study include the lower bound of convergence rates for first-order methods (see Remark 4.3 for the relationship
between our framework and first-order methods) for convex and strongly convex functions: O (1/k²²
for L-smooth and convex functions (cf. Nesterov (2018)) and O (1 Vp/D)2k) for L-smooth and j-strongly convex functions (Drori and Taylor, 2022). These lower bounds are tight, as they are
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

achieved by some optimization methods, such as Nesterov (1983) for convex functions and Van Scoy et al. (2018); Taylor and Drori (2022a) for strongly convex functions. In these studies, the discussion is typically conducted for each method, utilizing various techniques accumulated in the optimization research field.
Whereas, it has long been known that some optimization methods can be related to continuous differential equations (DEs). Early works on this aspect include the following: the continuous gradient flow उ = - (x) as a continuous optimization method was discussed in Bruck (1975). Similar arguments were later applied to second-order differential equations (Alvarez, 2000; Alvarez et al., 2002; Cabot et al., 2009). An important milestone in this direction was Su et al. (2014), where it was shown that Nesterov's famous accelerated gradient method (Nesterov, 1983) could be related to a second-order system with a convergence rate-revealing "Lyapunov functional." The insights gained from this relationship have been useful in understanding the behavior of the Nesterov method and in considering its new variants. This success has followed by many studies, including Wilson (2018); Wilson et al. (2021). The advantage of the DEs with Lyapunov functional approach (which we simply call the "DE approach" hereafter) is that the continuous DEs are generally more intuitive, and convergence rate estimates are quite straightforward thanks to the Lyapunov functionals. However, the DE approach still lacks one important component; although we can draw useful insights from continuous DEs, there is no known general way to translate them into a discrete setting. Consequently, we still need to perform complex discrete arguments for each method. This limitation already acknowledged in Su et al. (2014):* "... The translation, however, involves parameter tuning and tedious calculations. This is the reason why a general theory mapping properties of ODEs into corresponding properties for discrete updates would be a welcome advance."
In this paper we attempt to provide this missing piece by incorporating the concept of "discrete gradients" " (DGs) from numerical analysis, which is used to replicate some properties of continuous DEs in discrete settings. We demonstrate that relaxed concept of DG, which we call "weak discrete gradient" (wDG), can serve a similar purpose in the optimization context. More precisely, we show that for known DEs in the DE approach, if we define abstract optimization methods using wDGs analogously to the DEs, their abstract convergence theories can be obtained by following the continuous arguments and replacing gradients with wDGs. The tedious parts of the case-specific discrete arguments are consolidated in the definition of wDG, which simplifies the overall arguments: can now consider "simple continuous DE arguments" " and "case-specific discrete discussions summarized in wDG" separately. We demonstrate that many typical existing optimization methods and their rate estimates, previously done separately for each method, can be recovered as special cases of the abstract methods/theorree, providing simpler view of them. Any untested combination of a known DE and wDG presents an obvious new method and its rate, further expanding the potential for innovation in the optimization field. Creating a new wDG leads to a series of optimization methods by applying it to known DEs. One simply needs to verify if the wDG satisfies the conditions for wDG (Theorem 4.2) and reveal the constants of the wDG If. in the future, new DE with a rate-revealing Lyapunov functional is discovered, should be possible to achieve similar results. We suggest first defining an abstract wDG method analogous to the DE and then examining whether the continuous theory can be translated to a discrete setting, as demonstrated in this paper.
The aforementioned paper (Su et al., 2014) concludes in the following way (continued from the previous quote) "Indeed, this would allow researchers only study the simpler and more user-friendly ODEs." Although there is still room for minor adjustments (see the discussion on limitations below), we believe the wDG framework substantially reduces the complexity of discussions in discrete methods, allowing researchers to focus on more accessible and intuitive aspects of optimization.
We consider the problems (1) the d-dimensional Euclidean space Ed (d is positive integer) with the standard inner product (..-) and the induced norm ||-I1. where f: Rd + IR represents a differentiable convex objective function. We assume the existence of the optimal value f and the optimal solution x". In the following discussion, we use the inequality
1 ll - 211 <
(V(x))
which holds for any x, E Rd when f is ju-strongly convex and differentiable.
Remark 1.1. Although the scope of this paper is limitted due to the restriction of space, the framework can be naturally extended to more general cases. Extension to the objective functions satisfying the (PL) condition is provided in Appendix H. The framework can be extended to
2

---

constrained optimizations by the DE approach for mirror descent methods (cf. Krichene et al. (2015); Wilson et al. (2021)), which the authors have already confirmed. Stochastic methods such as the stochastic gradient descent can be handled by considering random compositions of wDGs, which is left as our future work.
2 Short summary of the differential equation approach
Let us first consider the gradient flow:
i = -Vfc(, z(0) = 2o E R
(3)
It is easy to see that
d dt
- S..
This means the flow can be regarded as a continuous optimization method. Notice that the proof is quite simple, once admit the chain rule of differentiation, and the form of the flow itself (3); this will be quite important in the subsequent discussion.
Despite its simplicity, the convergence rate varies depending on the class of objective functions. Below we show some known results. The following rates are proven using the so-called Lyapunov argument, which introduces "Lyapunov functional" that explicitly contains the convergence rate. The proof is left to Appendix B (we only note here that, addition to the two key tools the chain rule and the form of the flow we need the convexity inequality (2) to complete the proof.)
Theorem 2.1 (Convex case). Suppose that is convex. Let [0, oo) - Rd be the solution of the gradient flow (3). Then the solution satisfies
1²
f(x(t)) fr
2t
Theorem 2.2 (Strongly convex case). Suppose that f p-strongly comvex Let x: [0, 00) + Rdd be the solution of the gradient flow (3). Then the solution satisfies
((x(() 5 S e e= - x x²11
An incomplete partial list of works using the Lyapunov approach includes, in addition to Su et al. (2014), Karimi and Vavasis (2016); Attouch al. (2016); Attouch and Cabot (2017); Attouch et al. (2018); França et al. (2018); Defazio (2019); Shi et al. (2019); Wilson et al. (2021) (see also comprehensive list in Suh et al. (2022)). A difficulty in this approach is that the Lyapunov functionals were found only heuristically. A remedy is provided in Suh al. (2022); Du (2022), but its target is still limited.
Next, we consider DEs corresponding to accelerated gradient methods, including Nesterov's 's method. As well known, the forms of accelerated gradient methods differ depending on the class of objective functions, and consequently, the DEs to be considered also change. In this paper, we call them accelerated gradient flows.
When the objective functions are convex, we consider the following DE proposed in Wilson et al. (2021): let A: R20 + R20 be a differentiable strictly monotonically increasing function with A(0) = 0, and
À (v x), A
à = 4 V((r),
(5)
with (z))),,(0)) (Zo, vo) E R
Rd
Theorem 2.3 (Convex case (Wilson al. (2021))). Suppose that f is convex. Let (z) [0, xc) gd x dd be the solution of the DE (5). Then satisfies
f(x(t)) - f 2| 11
A(I)
3

---

Remark 2.4. If we set A(t) = t?, this system coincides with continuous limit DE of the accelerated gradient method for convex functions
3 V+(z)) = 0,
which is derived Su et al. (2016).
Remark 2.5. From Theorem 2.3, it might seem that we can achieve an arbitrarily high order rate. Although it is surely true in the continuous context, it does not imply we can construct discrete optimization methods from the ODE. In fact, greedily demanding a higher rate is penalized at the timing of discretization from the numerical stability. See, for example, the discussion in Ushiyama et al. (2022b).
Next, for strongly convex objective functions, let us consider the DE (again in Wilson et al. (2021)):
2 == Vu(u-=a -)), -= Vulz - V
(6)
with (a+(0), e()) (zo, 0o) E Rd Rd. (Note that this system coincides with the continuous limit ODE of the accelerated gradient method for strongly convex functions by Polyak (1964):
2//2 + Vf(x)= 0.)
Theorem 2.6 (Strongly convex case (Wilson et al. (2021); Luo and Chen (2022))). Suppose that is u-strongly convex. Let u): oo) - Rdd x Id be the solution of (6). Then it satisfies
f(x(() fr S Sevvi via ((()))
M 1000==112) =²I²²)
Discrete gradient method for gradient flows (from numerical analysis)
The remaining issue is how we discretize the above DEs. In the optimization context, it done separately in each study. One tempting strategy for a more systematic discretization is to import the concept of "DG," which was invented in numerical analysis for designing structure-preserv numerical methods for gradient flows such as (3) (Gonzalez (1996); McLachlan et al. (1999)). Recall that the automatic decrease of objective function came from the two keys: (a) the chain rule, and (b) the gradient flow structure. The DG method respects and tries to imitate them in discrete settings.
Definition 3.1 (Discrete gradient (Gonzalez (1996): Quispel and Capel (1996))). A continuous map Vaf: Rd x 12d + IRd is said to be discrete gradient of if the following two conditions hold for all x, y gd:
=
x),
=
(7)
In the definition provided above, the second condition simply requires that Vaf approximates V.. On the contrary, the first condition, referred to as the discrete chain rule, is a critical requirement for the key (a). The discrete chain rule a scalar equality constraint on the vector-values function, and for any given f. there are generally infinitely many DGs. The following is list of some popular choices of DGs. When necessary to differentiate them from wDGs, we call them strict DGs.
Proposition 3.2 (Strict discrete gradients). The following functions are strict DGs. Gonzalez discrete gradiens Vaf(y, x) (Gonzalez (1996)):
vs
y +
(()) f(x) (V]
x) (y x).
11y x
Itoh-Abe discrete gradient VIA fy, x)) (Iohh and Abe (1988)):
{(n 3r F.)) - flas .2...)......
flu 22) fly 23.
U2 22
flun M2. Ma) fln wa....a........... ua.
Ba
Average vector field (AVF) V f x)) (Quispel and McLaren (2008)):
Vs(Ty + dd)

---

Suppose we have a DG for a given f. Then we can define a discrete scheme for the gradient flow (3):
(k (k) Vas (al((tttt)) x(()) x
30,
h
where the positive real number h is referred to as the step size, and (x( = xkhh) is the numerical solution. The left-hand side approximates I and is denoted by 8+ xx(k) hereafter. Note that the definition conforms to the key point (b) mentioned earlier.
The scheme decreases (()(k)) expected:
(5
hh- ////h//vatttt (ktt) 2011) .8 = - (2((+1), , )²² O.
In the first equality we used the discrete chain rule, and in the second, the form of the scheme itself. Observe that the proof proceeds in the same manner as the continuous case (4). Due the decreasing property, the scheme should work as an optimization method. Additionally, the above argument does not reply on the step size h, and it can be changed in every step (which will not destroy the decreasing property).
In the numerical analysis community, the above approach has already been attempted for optimizations (Grimm et al. (2017); Celledoni et al. (2018); Ehrhardt et al. (2018); Miyatake et al. (2018); Ringholm al. (2018); Benning et al. (2020); Riis et al. (2022)). Although they were successful their own, this does not immediately provide the missing piece we seek for the following reasons. First, the DG framework does not include typical important optimization methods; it even does not include the steepest descent. Second, as noted above, the proofs of rate estimates in the continuous DEs (in Section 2) require the inequality of convexity (2). Unfortunately, however, existing DGs generally do not satisfy it; see Appendix C for counterexamplc. Next, we show how to overcome these difficulties.
Remark 3.3. Some members of the optimization community may find the use DGs peculiar, since it involves referring two solutions ((k+1), (x)))_ However, in some sense, it is quite natural because the decrease of occurs in single step (A) + r((+1), There may also be concerns about the computational complexity of DGs because the method becomes "implicit" by referring to (+++1), numerical methods, however, widely known that in some
In the field of structure-preservin highly unstable DEs, implicit methods are often advantageous, allowing larger time-stepping widths, while explicit methods require extremely small ones. In fact. it has been confirmed in Ehrhardt et al. (2018) that this also applies to the optimization context. The Itoh-Abe DG results in system of nonlinear equations, which is slightly less expensive. Moreover, note that the integral the AVF can be evaluated analytically before implementation, when f is polynomial.
4 Weak discrete gradients and abstract optimization methods
We introduce the concept of a weak discrete gradient (wDG), which is a relaxed version of the DG introduced earlier.
Definition 4.1 (Weak discrete gradient). A gradient approximation' 1 v IRd x Rd - Red is said to be weak discrete gradient of f if there exists a 2 0 and 3, with 8 + 7 such that the following two conditions hold for all x, y, E Rd:
f(v) - f(z) <
=) + ally - 2112 - B112 - x - -0--- +ll - x =((,,))=V((a
Note that (8) can be regarded as a modification of the three points descent lemma, where the third variable z is utilized give some estimates. The freedom in variable in (8) is fully utilized also in this paper; see Theorems 5.4 and 5.5 and their proofs.
The condition (8) can be interpreted in two ways. First, it can be understood discrete chain rule weaker sense. By substituting x with z, we obtain the inequality:
f(v) fa) s x). x) + (a 7)lly x=|
Notice that we use the notation V here, distinguishing it from Va denoted as the standard notation for strict discrete gradients in numerical analysis.
5

---

Compared to the strict discrete chain rule (7), it is weaker because it is an inequality and allows an error term. Second, can be interpreted as a weaker discrete convex inequality. By exchanging æ and y and rearranging terms, we obtain another expression
(10) Compared to the strongly convex inequality (2), the term (n/2)lly - =01 is now replaced with Blly =1|² + r 2|| which can be interpreted as the squared distance between y and the point (x, where the gradient is evaluated. The term -a|| =1|² is an error term.
f(v) [(z) (V(
=) 2 >ly z=12 + Bly =1² arl =|1?
We now list some examples of wDGs (proof is provided in Appendix D). Notice that these exam- ples include various typical gradient approximations from the optimization and numerical analysis literature. Note that for case of presentation, we simply write "p-strongly convex function," which includes convex functions by setting μ4 0.
Theorem 4.2. Suppose that f: Rd + a ju-strongyy convex function, Let (L) and (SC) denote the additional assumptions: (L) f is L-smooth, and (SC) μ 0. Then, the following functions are wDGs:
①) I/ x) (xx and f satisfies (L), then (a, 3,7) = (L/2,1/2,0).
( lV x) V fw) then (a, 00,0,
(ii) If /Vfly. x) V f( デ and f satisfies (L), then (a, B,7) = + (LL+))/8, 1)/..
(iv) V fly.z) = V AAv f(y, x) and f satisfies (L), then (a, 3,7) = (L/6 + 4/4,
(v) If x)
vof(y.z) and f satisfies (L)(SC), then (a, ((L + w)/8
(L /1)² /16p, m/4,0)
(vi) If V f x) = VI)f(,, and f satisfies (L)(SC), then (a,3,7) (dL2/p
// 4, 1/2,-1/41 -w/4).
Although we assumed the smoothness of f to simplify the presentation, the case (ii) does not demand it (see the end of Appendix D). Thus, it can handle non-smooth convex optimization. While the wDGs (i), (iii), (iv) only require (L), the wDGs (v) and (vi) demand (SC) (μ > 0). This implies that the latter wDGs might be fragile for small p's.
We now define an abstract method using wDGs: (b++1) (k)
- V (2((++1)) (x())
x = To.
(11)
h
which is analogous to the gradient flow (3). By "abstract," " we mean that is a formal formula, and given a concrete wDG it reduces concrete method; see Table which summarizes some typical choices. Observe that the abstract method covers many popular methods from both optimization and numerical analysis communities. The step size h may be selected using line search techniques, but for simplicity, we limit our presentation to the fixed step size in this paper (see Remark 5.1).
Remark 4.3. Note that some wDGs are not directly connected to the original gradient V.'s; the Itoh-Abe wDG (vi) does not even refer to the gradient. Thus, the concrete methods resulting from framework do not necessarily fall into the so-called "first-order methods," which run in a linear space spanned by the past gradients (Nesterov (1983)). This is why we use the terminology "gradient-based methods" in this paper, instead of first-order methods.
Similar to the aforementioned, we can define abstract methods for (5) and (6). Details and theoretical results can be found in Theorems 5.4 and 5.5.
We also introduce the next lemma, which is useful in expanding the scope of our framework.
sum of two functions fi, f2. Vf Vifi and V2f2 are wDGs of fi and f2 with parameters (an, B1, 71) and (a22, 32, 72),, respectively, then ViSi + V2f2 is weak discrete gradient of J with (a,8,7) = (an a22 31 B2, 7i + 72).
Lemma 4.4. Suppose I can be expressed
This lemma allows us consider the following discretization of the gradient flow: (k+1)
(k)
-Vfi (2(kt) -V (2((tt))
(12)

---

within our framework. For instance. if fi is L1-smooth and μ1 -t-stnyyglyy convex. and fz is 42 uu--strongyy convex, then the right-hand side of (12) a wDG with (a, 3,))
22. H2/2).. In this case, splitting algorithm
the method is known as the proximal gradient method or the forward-backwe in optimization (cf. Bauschke and Combettes (2017)). Discretizing the accelerated gradient flows allows for obtaining accelerated versions. (Acceleration of the proximal gradient method has been studied for some time (Beck and Teboulle, 2009b,a).)
Table I: Examples of wDGs and their corresponding convergence rates for pu-strongly convex and L-smooth function f on R The numbers in the ff column correspond to the numbers in Theorem 4.2. The line in the figure corresponding to the proximal gradient method is described the setting of (12). The notation (DG) represents strict discrete gradient. The convergence rates shown in the table are the best possible for the step sizes chosen in Theorems 5.3 and 5.5.
Opt. meth.
Convergence rates
(for (3))
Numer. meth.
Theorem 5.3
Theorem 5.5
- 2 1
0(1
o
0 vF))
(i) steep. des.
exp. Euler
(ii) prox. point
imp. Euler
(i)+(ii) prox. grad.
(splitting)
# LI+ +3p2
LItp2
(iii)
imp. midpoint
8
H
4p D+3μ
L+7p
(iv)
AVF (DG)
0
(1
6 T,i
3 L1
(v)
Gonzalez (DG)
4
4/12 L L3
(vi)
Itoh-Abe (DG)
0
5 Convergence rates of abstract optimization methods
We establish the discrete counterparts of Theorems 2.1 to 2.3 and 2.6. Although the proof's are left to Appendix E, emphasize that they can be performed analogously those of the continuous cases. The discrete theorems are established in four cases: the gradient flow (3) (for f convex and p-strongly convex), and the accelerated flows (for f convex (5) and p-strongly convex (6)). For ease of understanding, we summarize the results for μ--ttrongly convex cases in Table 1. A similar table for convex cases included Appendix A.
Remark 5.1. The following theorems are presented under the assumption that the step size is fixed for simplicity. However, if all varying step sizes satisfy the step size condition (with finite number of violations allowed), the theorems still hold true. The step sizes must be bounded by positive number from below to ensure the designated rates.)
5.1 For the abstract method based on the gradient flow
The abstract method given in (11).
Theorem 5.2 (Convex case). Let f be convex function. Let f be wDG of f. and suppose that
also satisfies the necessary conditions required by the wDG. Suppose that in the wDG B 2 0, 2 0. Let (a(k) } be the sequence given by (11). Then, under the step size condition h S 1/(2)), the sequence satisfies
) 110
5(
-
2kh
Let us demonstrate how to use the theorem using the proximal gradient method (12) as an example. Suppose that fi is -mooth and convex, and f2 is convex. Then, (y(,, = (f) + Vf2(y) wDG with the parameter 3.) (L1/2, 0, 0) due to Theorem 4.2 and Lemma 4.4. Therefore,
7

---

the proximal gradient method (12) satisfies the assumption of Theorem 5.2 and thus the convergence rate is O(1/k) under the step size condition
(L/L,).
Theorem 5.3 (Strongly convex case). Let f be strongly convex function. Let V be a wDG of S. and suppose that I also satisfies the necessary conditions required by the wDG Suppose that in the wDG [3 + + O. Let {x(l)} } be the sequence given by (11). Then, under the step size condition h 1/(a + 3), the sequence satisfies
2(3++)1 K 1+
)
|1:00 - x-112
In particular, the sequence satisfies
f )
- -
2(B + 7)
)
k
| - =x"11
+ 3 + 2
when the optimal step size h = 1/(a + 8) is employed.
5.2 For the abstract methods based on the accelerated gradient flows
We consider abstract methods with wDGs based on the accelerated gradient flows (5) and (6), which will be embedded in the theorems below. We note one thing: when using (8) as an approximation of the chain rule, we can determine independently of x and which gives us some degrees of freedom (thus allowing for adjustment.) Below we show some choices of 2(4) that are easy to calculate from known values while keeping the decrease of the Lyapunov functional.
Theorem 5.4 (Convex case). Let f be convex function, Let f be wDG of f. and suppose that also satisfies the necessary conditions required by the wDG. Suppose that in the wDG B 2 0, 2 Let { (2 v(()) } be the sequence given by
8+ As
(k)
(1(kt1)- -x((+1))
(,(++1)
Ak
8 (k)
8+ Ak V
( (2(kt2)) 210)
(k) (1)
8 A+AA (n((k) - xolhi)
h
Ast1
with (I!0), ,v(0)) (zu, vo). where A& A(kh). Then if Ak (kh)² and h S 1/v2a, the
sequence satisfies
f (x(0)) - 2/(200 x2
A
Theorem 5.5 (Strongly convex case). Let f be strongly convex function. Let f be wDG of f. and suppose that f also satisfies the necessary conditions required by the wDG. Suppose that in the wDG 8 + y > O. Let (x(th) o(h)) be the sequence given by
8 x (k) = /2 + 7) (1-1-1) - -
( 200)) 2(3 + 7)
8 (N) = /2(3+ + 7)
(1)) +
7 (k+1) -0+11)
3+4
3+y
(k)) - x(k)
22B + 7)
(1())) + (A) - -22(k)
h
with (z)(0) (1(1))) (xo, vo). Then if Th= (V2(Va + - the sequence satisfies
5( f s (1 22 (111+) (f(00) - fr Bl1eo - x= =1²)
In particular, the sequence satisfies
8 8+7 1r (1- a+47
(1-
(f(2o) f - 8 - =²(²))
when the optimal step size h = h is employed.
8

---

Remark 5.6. Time scaling can eliminate the factor /2 +)) from the scheme and simplify it, as shown in Luo and Chen (2022). However, we do not use time scaling here match the time scale with the accelerated gradient method and to maintain correspondence with the continuous system.
6 Discussions including Limitations
Relation to some other systematic/unified frameworks A systematic approach obtaining optimization methods with convergence estimates was developed using the "performance estimation problems" (PEPs) technique, as seen in works such Taylor al. (2018); Taylor and Drori (2022b). While our framework unifies discussions in both continuous and discrete settings, the design of methods is not automatic and requires finding new wDG. In contrast, the PEP framework automates method design but separates discussions between the continuous and discrete settings. Combining these two approaches could be promising research direction, such as applying our framework the Lyapunov functionals obtained in Taylor and Drori (2022b).
Another unified convergence analysis is presented in Chen and Luo (2021), where the authors cite the same passage in the Introduction from Su et al. (2016). However, this seems to focus on unifying discussions in the continuous setting, and it is still necessary individualize the discretization for each method in the discrete setting.
In Diakonikolas and Orecchia (2019), a unified method for deriving continuous DEs describing first-order optimization methods was proposed using the "approximate duality gap technique." While this work is capable of finding new DEs, it does not provide insight into how to discretize the DEs for obtaining discrete optimization methods.
Another closely related work is De Sa et al. (2022), which proposed framework to construct Lyapunov functionals for continuous ODEs. This is strong in view of the fact that generally Lyapunov functionals can be found only in ad hoc ways. Instead, they considered only the simplest gradient descent (and its stochastic version), while the main focus of the present paper lies the discretizations.
As said in Section 3, in the field of numerical analysis, the use of discrete gradients has been tried. Among them, Ehrhardt al. (2018) is pioneering work that comes with several theoretical results. Both this and the present work aim at convex, strongly convex, and the PE functions (in the Appendix, the present paper). The scope of Ehrhardt et al. (2018) was limited in the sense that they considered only discretizations of gradient flows with strict discrete gradients. Our target ODEs and discretizations are not limited to that, but as its price, our rate worse in some strict discrete gradient discretizations of gradient flow. This comes from the difference in proof techniques: they proved convergence rates directly and algebraically, while our analysis is via Lyapunov functionals. They also gave several theoretical results besides the convergence analysis, such as the (unique) existence of solutions, and step-size analysis which are important in actual implementations. Whether these two frameworks could be unified would be an interesting future research topic.
Limitations of the proposed framework. Although we believe that the current framework provides an easy environment for working on the DE approach to optimization, it still has some limitations.
First, methods that do not fall into the current framework exist, such as the following splitting method (cf. the Douglas-Rachfore Rachford splitting method (Eckstein and Bertsekas, 1992)):
(k (k+) (k) = vifi ( (2(+112),,x01))
(k++) 1x+1) = V2f2 x (k+1) (++1/2))
h
h
The right-hand side cannot be written by a single wDG. Additionally, methods based on Runge- Kutta (RK) numerical methods (Zhang al. (2018); Ushiyama al. (2022a)) appear difficult to be captured by wDG because RK methods cannot be expressed by DG in the first place. Investigating whether these methods can be captured by the concept of DG is interesting future research topic.
Second, there is still some room for adjustment in wDG methods. A typical example is (M) in Section 5.2, which is chosen in the theorems to optimize efficiency and rates. Another example is the adjustment of time-stepping in the last phase of constructing a method to achieve better rate or practical efficiency. Although these optimizations the construction of optimization methods are standard in optimization studies, we feel that they are difficult to capture in the current framework, as they fall between the intuitive continuous argument and the discrete wDG arguments that aim to capture common structures.
9

---

Third, some rates in the theorems are not optimal. For example, on strongly convex func- tions, the scheme proposed in Theorem 5.5 with the choice achieves the convergence rate of ((1-V///L))
This is because the choice of the DE and Lyapunov functional used in this work is not optimal. A DE and Lyаpunov functional for obtaining the optimal rate are known (Sun et al., 2020), but the DE is a so-called high-resolution DE (known as a "modified equation" in numerical analysis), which involves the Hessian. Whether these DEs be captured with the wDG perspective is an interesting future research topic.
which is not the optimal rate of ((1
7 Concluding remaks
In this paper, we proposed a new unified discretization framework for the DE approach to convex optimization. Our framework provides an easy environment for those working on the DE approach, and some new methods are immediate from the framework, both as methods and for their convergence estimates. For example, any combination of strict DGs with the accelerated gradient flows are new methods, and their rates are given by the theorems. Although we did not include numerical experiments in the main body owing to the space restrictions, some preliminary numerical tests confirming the theory can be found in Appendix These tests show that some new methods can be competitive with state-of-the-art methods, such as Nesterov's accelerated gradient.
Acknowledgements
The authors grateful for the anonymous reviewers who gave helpful comments to improve this paper. This work is partially supported by JSPS KAKENHI Grant Number JP22K13955 H02140355, JP20K21786, and JP20H01822 822, and by JST SPRING Grant Number JPMJSP2108.
References
Alvarez, F. (2000). On the minimizing property a second order dissipative system in Hilbert spaces.
SIAM J. Control Optim.,
Alvarez, F., Attouch, H., Bolte, J., and Redont, P. (2002). A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanies. J. Math. Pures Appl. (9), (8)7777777
Attouch, H. and Cabot, A. (2017). Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity. J. Differential Equations, 263(9):5412-5458.
Attouch, H., Chbani, Z., and Riahi, H. (2018). Combining fast inertial dynamics for convex optimization with Tikhonov regularization. J. Math. Anal. Appl., 457(2)):065-1099 1094
Attouch, H., Peypouquet, J., and Redont, (2016). Fast convex optimization via inertial dynamics with Hessian driven damping. J. Differential Equations, 261(10):5734-5788
Bauschke, H. and Combettes, L. (2017). Convex analysis and monotone operator theory in Hilbert spaces. CMS Books in Mathemmatics/Ouvragee de Mathématiques de la SMC. Springer, Cham, second edition.
Beck, A. and Teboulle, M. (2009a). Fast gradient-based algorithms for constrained total variation image demoising and deblurring problems. IEEE Trans. Image Process., 18(11):241) (0(11)2119-2434
Beck, A. and Teboulle, M. (2009b). fast iterative shrinkagg-threshholdnng algorithm for linear inverse problems. SIAM J. Imaging Sci., 2(1):183-202.
Benning, M., Riis, E. S., and Schönlieb, C.-B. (2020). Bregman Itoh-Abe methods for sparse optimisation. J. Math. Imaging Vision, 62(667):842-857.
Bruck, Jr., E. (1975). Asymptotic convergence nonlinear contraction semigroups in Hilbert
space. J. Functional Analysis, 18:15-26.
10

---

Cabot, A., Engler, H., and Gadat, S. (2009). On the long time behavior of second order differential equations with asymptotically small dissipation. Trans. Amer. Math. Soc., 361 6017.
Celledoni, E., Eidnes, S., Owren, B., and Ringholm, T. (2018). Dissipative numerical schemes on Riemannian manifolds with applications to gradient flows. SIAM J. Sci. Comput., A3789 A3806.
Chen, L. and Luo, H. (2021). unified convergence analysis of first order convex optimization methods via strong Yyapunov functions. arXiv preprint, arXiv:2108.00132.
De Sa, C. M., Kale, S., Lee, J. D., Sekhari, A., and Sridharan, K. (2022). From gradient flow population loss to learning with stochastic gradient descent. In Advances in Neural Information Processing Systems, volume 35, pages 30963-30976.
Defazio, A. (2019). On the curved geometry of accelerated optimization. In Advances in Neural Information Processing Systems, volume 32.
Diakonikolas. J. and Orecchia, L. (2019). The approximate duality gap technique: a unified theory of first-order methods. SIAM J. Optim., (9(1)) (966)6660-689,
Drori, Y. and Taylor, A. (2022). On the oracle complexity of smooth strongly convex minimization. J. Complexity, 68: 101590.
Du, D. (2022). Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization. arXiv preprint, arXiv:2205.122 12442..
Eckstein, J. and Bertsekas, P. (1992). On the Douglas-Rachford Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Programming, 55(3, Ser. A):293-318.
Ehrhardt, M. J., Riis, E. S., Ringholm, T., and Schönlieb, C.-B. (2018). A geometric integration approach to smooth optimisation: Foundations of the discrete gradient method. arXiv preprint. arXiv:1805.06444
França, G., Robinson, D., and Vidal, R. (2018). ADMM and accelerated ADMM as continuous dynamical systems. In Proceedings of the 35th International Conference on Machine Learning, pages 1559-1567.
Gonzalez, O. (1996). Time integration and discrete Hamiltonian systems. J. Nonlinear Sci., 6(5):449 467.
Grimm, V., McLachlan, R. I., McLaren, D. D. Quispel, G. R. W., and Schönlieb, C.-B. (2017). Discrete gradient methods for solving variational image regularisation models. J. Phys. A, 205291, 21.
Itoh, T. and Abe, K. (1988). Hamiltonian-consevviee discrete canonical equations based on variational difference quotients. J. Comput. Phys., 76(1):85-102.
Karimi, S. and Vavasis, S. A. (2016). A unified convergence bound for conjugate gradient and accelerated gradient. arXiv preprint, arXiv:1605.00m 160::002000000
Krichene, W., Bayen, A., and Bartlett, P. I.. (2015). Accelerated mirror descent in continuous and discrete time. Advances in Neural Information Processing Systems, volume 28.
Luo, H. and Chen, L. (2022). From differential equation solvers to accelerated first-order methods for convex optimization. Math. Program., 195:735-781.
McLachlan, R. I., Quispel, G. R. W., and Robidoux, N. (1999). Geometric integration using discrete gradients. R. Soc. Lond. Philos. Trans. Ser. Math. Phys. Eng. Sei., 357(1754):0011-145
Miyatake, Y., Sogabe, T., and Zhang, S.-L. (2018). On the equivalence between SOR-type methods for linear systems and the discrete gradient methods for gradient systems. J. Comput. Appl. Math., 342:58 69.
Nesterov, Y. (2018). Lectures on convex optimization, volume 137 of Springer Optimization and Its Applications. Springer, Cham.
11

---

Nesterov. Y. E. (1983). A method for solving the convex programming problem with convergence rate O(1/k²). Dokl. Akad. Nauk SSSR, 269(3):543-547.
Polyak, B. T. (1963). Gradient methods for the minimisation of functionals. USSR Comput. Math. Math. Phys., 3(4):864-878.
Polyak, B. T. (1964). Some methods of speeding up the convergence of iterative methods. USSR Comput. Math. Math. Phys., 4(5):1-17.
Quispel, G. R. W. and Capel. H. W. (1996). Solving ODE's numerically while preserving a first integral. Phys. Lett., 2182:223-228.
Quispel, G. R. W. and McLaren, D. (2008). A new class of energy energy-preserving numerical integration methods. J. Phys. A, 41(4):045206, 7.
Riis, E. S., Ehrhardt, M. J., Quispel, G. R. W., and Schönlieb, C.-B. (2022). A geometric integration approach nonsmooth, nonconvex optimisation. Found. Comput. Math., 1355):135--1394
Ringholm, T., Lazić, J., and Schönlieb, C.-B. (2018). Variational image regularization with Euler's elastica using discrete gradient scheme. SIAM J. Imaging Sci., 11(4):2665-2611
Shi, B., Du S. S., Su, W., and Jordan, M. I. (2019). Acceleration via symplectic discretization of high-resolution differential equations. In Advances in Neural Information Processing Systems, volume 32.
Su, W., Boyd, S., and Candès, E. J. (2014). A differential equation for modeling nesterov's accelerated gradient method: theory and insights. Advances in neural information processing systems, 27.
Su, W., Boyd, S., and Candès, E. J. (2016), A differential equation for modeling Nesterov's accelerated gradient method: theory and insights. J. Mach. Learn. Res., 17(153):1
Suh, J. J., Roh, G., and Ryu, K. (2022). Continuous-time analysis of accelerated gradient methods via conservation laws in dilated coordinate systems. In Proceedings of the 39th International Conference on Machine Learning, pages 20640-20667.
Sun, B., George, J., and Kia, S. (2020). High-resolution modeling of the fastest first-order optimization method for strongly convex functions. In 2020 59th IEEE Conference Decision and Control (CDC), pages 4237-4242
Taylor, A. and Drori, Y. (2022a). An optimal gradient method for smooth strongly convex minimiza- tion. Math. Program., pages 1-38.
Taylor, A. and Drori, Y. (2022b). An optimal gradient method for smooth strongly convex minimiza- tion. Mathematical Programming, pages 1-38.
Taylor, A., Van Scoy, B., and Lessard, L. (2018). Lyapunov functions for first-order methods: Tight automated convergence guarantees. In International Conference on Machine Learning, pages 4897-4906.
Ushiyama, K., Sato, S., and Matsuo, Т. (2022a). Deriving efficient optimization methods based on stable explicit numerical methods. JSIAM Lett., 14:29-32.
Ushiyama, K., Sato, S., and Matsuo, (2022b). Essential convergence rate of ordinary differential equations appearing in optimization. JSIAM Lett., 14:119-121
Van Scoy, B., Freeman, R. A., and Lynch, K. M. (2018). The fastest known globally convergent first-order method for minimizing strongly convex functions. IEEE Control Syst. Lett. 2(1):49-54.
Wilson, A. (2018). Lyapunov arguments in optimization. University of California, Berkeley.
Wilson, A. C., Recht, B., and Jordan, M. I. (2021). A Lyapunov analysis of accelerated methods in optimization. J. Mach. Learn. Res., 22 (11113):1-34
Zhang. J., Mokhtari, A., Sra, S., and Jadhahaie, A. (2018). Direct runge-kutta discretization achieves acceleration. In Advances in Neural Information Processing Systems, volume 31.
12

---

A Table summarizing the convex cases
In contrast to the strongly convex cases, in the convex the convergence rates the same in the order, and the difference appears its coefficients, which actually depends on the maximum step sizes allowed. See Theorems 5.2 and 5.4 for the rates. In the table below summarize the step size information.
Table 2: Examples of weak discrete gradients and resulting convergence rates when is L-smooth function on 1R The numbers in the V column correspond the numbers in Theorem 4.2. The line of the proximal gradient method is described in the setting of (12). (DG) represents that this weak discrete gradient strict discrete gradient.
Opt. meth.
Max. step sizes
(for (3))
Numer. meth.
Theorem 5.3
Theorem 5.5
(i) steep. des.
exp. Euler
1/L
I/VI
(ii) prox. point
imp. Fuler
80
oc
(i)+
prox. grad.
(splitting)
1/L1
1/VLi
(iii)
imp. midpoint
4/L
2/VL
(iv)
AVF (DG)
3/L
v3/L
B Proofs of theorems in Section 2
B.1 Proof of Theorem 2.1
It is sufficient to show that Lyapunov function
1
E(t) t(f(x(t)) - f²) ++21la12 (lll(t) - =x111
monotonically nonincreasing since
- S E(1) <
E(O) |
101
-
t
2t
Indeed,
È = + [(x) +*+ (x x², .)
V/) + f(x) - (V)((x) x- x²)
00
holds. Here, each line, applied the Leibniz rule and the chain rule, substituted the ODE, and used the convexity f this order.
B.2 Proof of Theorem 2.2
is sufficient to show a Lyapunov function
E(t) = exth (f(z(t)) ft =l z²11²)
monotonically nonincreasing and thus sufficient to show that E(I) -- satisfies
c < -uÉ. Indeed,
E (V)((), p/x- x²,
-I[Vf(z)] - ((Vf(x) x²)
< -IV - --u
-f" -f -1==="=))
x x1
holds. Here, at each line, we applied the chain rule, substituted the ODE, and used strong convexity of f in this order.
13

---

B.3 Proof of Theorem 2.3
It is sufficient to show that
E(t) = A(0()(((((()) - + + - x²12
nonincreasing. Actually,
É A(f(x) - f*) d
(f(x) -1) + d
dt (2) x²11?)
dt
A(f(x)) 5*) A(V](=)) - x²)
=(((()) /*+ A Vf(x), 4 (0- -リ-z) x) ) 4 1
/ A
V v(z)),
-(((a) (V(()
00
holds. Here, each line, we applied the Leibniz rule, used the chain rule, substituted the ODE, and used the convexity of f in this order.
B.4 Proof of Theorem 2.6
It is sufficient to show that
E(t)= = e (f()(((()))))))(())))))
- fr - x² x²11²)
is nonincreasing and thus it is sufficient to show that B(t) e Vat E(t) satisfies E s -VVE. Actually,
i (V](), + + u x²)
(VS()), vāllo x)) + plypl p/o - V/V////) x-
V (z),
p(u I, --))
-V (1)), xx 1)
H (11 =s1 + --11==*11 - || x² -11))
S --v7(( - + 1 1 x x²1)))
|11 ||e - x1|
S-VTE
holds. Here, each line. we applied the chain rule, substituted the ODE, rearranged terms, decom- posed the inner product by the law of cosines (see Appendix F). and used the strong convexity of f.
C Strict discrete gradients and convexity
In this section, we describe that strict discrete gradients are not generally compatible with the convex inequality; this complements the discussion in Section 3. For example, let us consider imitating the discussion in Appendix B. by using discrete gradient scheme 8' x+t)(() a aa (x(++1) (k)). Then, since we use the inequality
f(x) - l (VI(x)x <
that holds due to the convexity of f. we should ensure that the discrete counterpart of the left-hand side
f(x) - f* (Vaf(y, x²)
is nonpositive for any x, y E Rd, However, there is simple counterexample as shown below.
Let us consider a quadratic and convex objective function f(x) 1 (z, Qx), where Q E Rdxd is positive definite matrix. In this case, x= and f = 0 hold. Then, when we choose a discrete gradient Vaf x) VGJ(y, x) = AVF (v, x) = Q (2*²² we see
(Vaf (), x^) sr, Q+) Q
y +
1 -v. Qu), (v)
-(x)- -
x
2
which is positive when and x + 0.
14

---

D Proof of Theorem 4.2
Since assume f is I-smooth and j-strongly convex,
L f(v) - f(=) - (Vf(=). -) =)++ 1y =
2
f(z) - f(z) - (v)(=); 2-)) b =11= ø1
2
holds for any z, y, E IR By adding each side of these inequalities, we obtain
-1
-
f(v) f()) - (Vf(=),
(13)
(This inequality is known the three points descent lemma in optimization.)
(ii) It follows immediately from the j-stroog convexity of f.
(ii) By replacing z in (13) with Oy + (1 0)z, and invoking Lemma F.2, we have
f())= f(x) (Vy + (1 8)2). y x))
$ [1y (0y + (1 - (1-0)=)11 11 *10y + (1 - -0)= 15--x] xx1
L
L (1 - 0) =10- - 1-0 - 0)1v =1|² + (1 - [1]0]]|= x012 + +01ly xx1²).
2 Especially when 0 = 1/2. (a,
2
+ 1/8
(iv) By the same calculation as (iii,, we obtain
((y) ((x) (// Vs(Ty (1 r)))dr, x
1/' [f(v) f(x) - (Vf(ry + (1 (1- -))=))); v/- - x²) dr
// (1 -) =1? 1/ (-7(1- - -T)lly =11² + (1 -1-17 (1- - x=1? + + 2113] dr
L +
|I 2112 211
11
1|2 x/| /4 lll x=|?
6 12
4
(v) By (13), we obtain
(w) f(=) (4
+ 2 "
<
L
+ z
y
+
2
L
= =11²
2
2
2
2
Since this inequality holds with y and 2 swapped, we have
f(8) f(z) (
+ 2
)
<
11
- 2
2
8
Thus,
f(v) - f(x) - (Vaf(v. 2), xx)
y +
f(y) - f(=) - (V.( ,, x)
-f()) ((0) VS
(y -2), y
2
11 21|
(
y + 2
s(v) - f(z) - (VS ()(tt2 ).11 2)
S f(v) f(z)
1/
+
Ky 2, y x>)
2
|1 =|?
< 2
" #+2 2
1
y/ + 2
+ 8
1
L 1
|1y =1(²
+ L
2μ |1 - x0l12
2
2
8p1
1yy
1| 2
1
1
11y
2112
2| - x 2
1
Ilv
=112
(I. 11)
ll z1 + 11 "1y - x01
8
2
2
2
4
16p
L
(L
11)2
|/
2
1
8
8
161
15

---

holds, where the second inequality follows from the arithmetic-geometric geometric means (AM-GM) inequality.
(vi) In the following, for y Fd and k 2....,d, d, 21 denotes vector
(Hh...., :.t..::kk-11 2k1 Ed) E IR, while F1:021:d and Vi:d&d+1:d denote z and y. respectively. By the telescoping sum and jestrong convexity of f, we obtain
f(v)-((z)
-
-x)
f 1:d) - f -1 (2kedd)
f(v)) - f(x)
(ye I&)
yk 2k
[Wvi Fh 1:d) [ 1 2hord)
f(v) - f(x)
(y)1 2k + 2k 37k)
yk - 2k
f 2k +11+)))))))))))) - f 12kcd)
= [(=) - f(x)
(2x - xxx)
Vv: 2x
1=1
< (Vf(2), - x)
|| - =x1
2
(V) (VI Sk:a) ()(( y1.) - ( y1
2 Ik
(zu Tk)
if
+
D1 2k
1/k: 2k
(V[(I1 12d) ( - =2x) - [ zn
Zk J.k
1=1
(Zk xkk
if
0
2k M/k
1/k 2k
(V[(2), = - x) - -/1 -1=
=11=-x0 -
=x|1?
2k Tk
T =x (Et Ikk + 2/2 (ylk= 2x) - x3ke)
if
yk 2k
(VI
xx)) + (Ex mxx Ikk
if
2/
IK
1/k ZR
2k Tkk
((Vf(=))) (V 1
xx) if
yk
2k
2k
((Vi(=))) (V f xxm
if
yk 2k
I|1= - x||2
1
Ex vullz*
xxa--
2
To evaluate the first term of the most right-hand side, the following inequalities:
[V)())) (V (() < L||z - S L||z | - y
(V/(=)) (V / (11+=++))))))) T||== U1 T|| y
which hold due to the L-smoothness of f. and also
ZR In 12
vdll x/|,
which holds due Jensen's inequality. Using them, we obtain
f(y) f(x) (Viasly, (),, x)
S vdll|= =|lll= - =||| 5ー || - =0| 11
zk
yk ||=x - 27
2 A=1
dI? z 2 + -1 x|1
2 20
yellzx
-Ikb
2
km
16

---

where the last inequality holds due to the AM-GM inequality. Finally, the last term is bounded by
11
2k
yxll=*
Σ
yk
+ 1=x xxl 2
112k ykl
|2
2
4 k=1
k=1
-
4
(|z* y/ 1 + 1z2 xx11
1i5k Iz 12)
4 k=1
1
||
y|1
+ || x01² - 11 x012)
4
This proves the theorem.
For (ii), as noted in the above proof, the assumption of differentiability of f unnecessary. let alone L-smoothness. Since ff is proper convex function on IR in our setting, the subdifferential (f is nonempty for all x E Rd. Thus we can use V ff z) E 0f(y) instead of ff z) f By definition of subgradients, we can recover the same parameters (0,8,7) 7) as the differentiable case.
If = O, the proofs for (v) and (vi) cease to work where we apply the AM-GM inequality to the inner product. This is also pointed out in the main body of the paper.
E Proofs of theorems in Section 5
E. Proof of Theorem 5.2
is sufficient to show that the discrete Lyapunov function
E(K) = kh (x)((x)))))
( + 1 2
-
())
(0(8) xz
is nonincreasing. Actually,
8+ ((())
= kh (5t/ (2((1)) + (2lkt1)) 5r + (1 ((0) - =001?))
I kh (vf (z (x(++1) 20111 8+ (t))
ah 8+ 2(6b111) + of (z(kt2)) - fr + (alktt) x², 8 x1)(1)))
12
5+ (k)
2
= kh(11 - anl) / // 1o (x(+t)),,00))
|1² + (21
8 (vS ( .olt) ), _ xz))
5+ (k) 2
2
< khh(1 - (a)1-ah)] | (2((+t)) ((()))
||
2 - ahi || 2(0)
holds, and thus if / < 1/(2)). the right-hand side is not positive. Here, at each line, we applied the discrete Leibniz rule, the weak discrete gradient condition (8), Lemma F.1 the chain rule, substituted the scheme, and applied again (8) as the convex inequality.
E.2
Proof of Theorem 5.3
Let
E(0) = (x(1)) - 5 + (3 + 7) (2(00) x=
17

---

If 8 E(R) I (c+((++1) for e >> 0, it can be concluded that E(A) = (1 + ch)*E(k))))) is nonincreasing.
E(x)
and hence f(x(k))= - f I (1 + ch) (()) Actually,
8+ E(R)
= f {(x(tt) + 1+ (8 + 7) z(1k) -
(21k)) =01(²)
1 f x (((+1) x((4) 8t stz(k1)
+ (a 17/ 2 +2(33 m) (x((h111) - x², (88+((1) - -(3 + y) 1ool|10 1
, /| - -2 + 7){ 2(4+1) =x", (f((0(01))
(1 (a - 7/h (8+
s 22 7) (5 (f(x(h) - f + 1/12(0) x'1
+ イ + - x² ///
- (1 - (a - 7 + (3 + 7)h - 2a(3 + >))² V (x
x (1)
(14)
holds. Here, after the second line we used the weak discrete gradient condition (8) as the chain rule, substituted the scheme and used (8) the strongly convex inequality.
1=1 -x11 By the same calculation for Now we aim to bound ||x]*) 11 with || -
8+ =1xx(()) I+ as above, we get the evaluation
8+ 3t|l0tt) (k) xz =1| -((((((tt)) +33 (ock)) x²1| +7 cryluelttt - - 20li)) (
|
(2044 (0())))))))))))) )|²
(15)
Thus, h S 1/((a). we get ||.(0-1)))))) - 201 S ||0((t) 2²11² In this case, since the second term of (14) is nonpositive, it follows that
8+ - () ((-1)
To obtain a better rate which is included in the statement of the theorem, by directly using (15) for (14), we see
2(3 +7)
()(altt))) -5+ +B+ (B+ 7) ((0tt) -x-1))))==+(()) =-11²) ->/o0))t)-==-11)))
8+ E(R)_ S
1 - 233h
1 2ah
2(3 + 7)3h2 +1 1 (a-7)) (m->)h~ (3 + 7 2a(3 7))²²² (
(2(t1)))) (, )|²
1 2,h
Since the second term of the right-hand side is nonpositive under h s 1/(a + 3). it can be concluded that
2(B 77 F(k+1))
8+ ((,)
1 1 1-28h
In this case the convergence rate is
2(3 + +7)h k
1
2[04 1h 1-2
1 1+27h
E.3 Proof of Theorem 5.4
It is sufficient to show that
E(a) = A (5(2()))
-
-s*) + 22110 x11
18

---

is nonincreasing. Actually,
8+ E(R)
- -1*) Au 8 651 (x(1i)) + 28 -1000)-0011 10)))
= (8+ Ax) (a(ht1))-
- x-
s (6+ Ax) (1 (s(2(tt)) - - Av 4. 1 (1(+t)) (4)
55 )02(())
+ 44 ((8t1(1)) e((+1) - x²)
Ax
x (k+1) 210)
2h 8 ( 1
s 5 An) { (2 (2(k+1))
- - - A 7f (f(2((+11) )101).
A² (ulltt) 2(ttt)))
An
1 8 vn
A (1(++1)) =((1) (2lkt2) +
As [2(0t2)) - =/ 22/11tt stol
4
h
(8+ An)
(((kt))) -
ft
(Vf (V5(2(1t1) 200) ,x((t1)] -2a) )) + An
h -
- 200l|
2h 2/1100 001l p
S (0+ Au)a -
+ Ax a
2 2050 -2h||0 oct)||
h (attaa/olttt) 2001?
-2 u(k+2) -2l1
(err).
Here, at each line, we used the discrete Leibniz rule, applied (8) and Lemma F.1 as the chain rule, substituted the scheme, and applied again (8) the convex inequality.
Now we define 2(k) so that (err) < 0 holds. When zkk) == ((++1), (err) becomes nonpositive without step size constraints.
Or, since using the scheme we can write
| 11+1)) 2(0)
A Ak (k++)) Ax+1
As (1) (kk)
Ak+1
by setting
Act1 A ((()) +
As (())
20)
Ap+1
Ak+1
we obtain
(Ae+11- - -A
2 | - - m100l1
h x (err)
- -2
Ak+1
This choice of (k) is shown in the theorem. When, for example, A₁ = (Ash)², (err) < 0, provided that h < 1/v2a. Here we see that only up to a quadratic function is allowed as Ag a >
E,4 Proof of Theorem 5.5
It is sufficient to show that
B(N) = (2(()) - - (3 7) 0000000) x+
19

---

satisfies 8+ E(R)_ - --vma
--VmE(k+1) To simplify notation, 2(3 +1)+)) is written as m, and the error termss
are gathered into (err). Then, we see
8t )tE = 55 f(t(((()))
m 5+
(u())
+
x²
2
$ f 2
(N+1) x(k) 0 x())
+
2
x
(k+1) - 200) =000
2(00 - -
- h
- -nhi| -vbll 2000l
3
m xt (k)
0 (1++1) 1)
x²
m
10
8/|0= [+ 2
2
x (++1)
m
1
((++))
xlh+1)) ) + (err)
23 (k)
27 x (k+1) - ((+11)
1 / (o(kttt),,, ,2()))
) ) ,o(tt)) x0*
m
+
m
m
(1. 2(K) xx= -x(( x((+1))) 2 mm v(a+1) - =()), (0+.)) - xx))
(0 (o(kt)) z (1+1), (((+1)) xx)) + (err)
2/2mmm
mm
vml
vm(/// 4
2 (1++1) 2(1)) x² -(((t1)) vmg
[olkt)) - 2000 + - =000|² / - x012²- - 2 x²* 11²)
( /(ttu) 2 + (o(tt1) x. 1/
11( xt 2211)) + (err)
-mm
mml f (alittt gr + m 1 (k+t1) (1-t))===11"" =012r)
(2ll)((t1)) - 2(0) | ((0t)) ccaole? 7 | - s(atu)(²) + (err)
vm
= - + (err).
Here, the first incquality follows from (8) the chain rule, the second equality from the substitution of the form of the method, and the second inequality follows from again (8) as the strongly convex inequality. In the second inequality, we also used
( (V (k+1) 2(1) ) 20tht11) - x² +>>++|/200 x.1 * - --= -
- -f f*) + tallostt1- - -200)
(f(((tti))
Now we define (b) so that (err) S 0. An obvious choice is 2()) = (k++)), where (err) is nonpositive under any step size.
To derive another definition of 2(²), we proceed with the calculation of the error terms by substituting the form of the method:
h (err)= a ((+11) - 2(h) - 88| -0||((0) - -2001/ -
- -200) -
(B 7)) (ok+2)) - -
+ Vmhh
- 2(3) 1²= 3 p(1t))t)) - =
-
aa + 1) (11 - 1/ 8 (1:00) ( =
+ (arralll
- oloolp
Vmraa / - 2(01)²))
+ | 5(8) l| + vidolloati ((t1)))
= a(h + 1) (1 - |(1i
8 (1) = 2 + |111111) - o/11l + Vmnh ( x((+11 (R)
Vmh x(()) 2)
-7 (1210011) - 2(00|2 + (((+t)) - w1slpp + vmollaatt (k++1) (())
-
Vmhh
20

---

Hereafter, vmh is denoted by By using Lemma F.2, we have
(k++)) (1)
2
h x
(k+1)
+
201)
h
h
h +
2
h
(x(kt1) -101) +
1 (s(kt1) -2(t)) (2(tt))=((1))
h +
h+1
h + 1
h.
(k+ -2(3)
1|
x (k+1) -x(0) 2241|²
h
2(0) 20.00 220018
h
h+1
+ h h+1
(h +
2
-(h+
h -(++1]le 1 +
10:411=x(00 =000
+ 1 (k+ - x0()) - -1|1000 x
h
Thus, we see
x (err) = (a- (a 1) -(00] (B + 7)
h+1
bd(tt)) - =0////²++
/lottt - -c08)/
Here when we define 2( == x8)) (err) is nonpositive under the condition
(a - B) hh + 1) (B + +>) h + <
h
This condition reads as h (3 (3))\/ B), and the convergence rate is
(1 B + k
(1+V2(8+7)) = (l+ 2
a
+
To obtain a better rate, we continue the computation of (err) without defining (k)) Let
1
h
h-1
2h +1
and again by inserting the form of the method, and by using Lemma F22,
h
1 (k+1) - =chol² + (1-0--1) -1100-1)-0000 1
h
h+ + 1 [x(tt1)) - -0(0) 1| + 121tt11) x((+1) - x(())
((()
h
h
+ h++1 2
h 1
1. (k++)
2/10/1 -1000
(1++1
h
(A)
x (k)
h
h
7 +
h.
2
h+ + 1 1
-00l
+ (1 11)
(k+1)
h
(8)
(k)
h
h
h +
h + 1
17 ( - x(()) + (1 17) (b++1)
7,
(M)
h
+ 1
h +
+n(1 1)
[((tt]) (k)
(k+1)
(8)
1
a: (A)
h +
h + 1
2
h + 1 2h +1
z (k+1)
h + (8))
(k)
1
-2(00)0
h h
2h +
2h
+
1
2h
+
h. +
21

---

Hence we obtain
h x (crr) (a (0--() ah+ ( +-+11 (2(kt1) - =2(a11²
(B 7)
h
x(5)
2h + 1
(3 +7) h + 2h +
h +
h
(1++1)
x(
(k)
h
h
2h +
2h +
If we set
h + 1
h (16)
2(k)
x.1k)
2h +
2h + 1
(err) is nonpositive under the condition
(a- (h (B+1))))) 7)
h +
2h +
5.
h
h
The definition of (N) is shown in the theorem. By solving the above inequality, obtain the step size limitation
VB+7
h < Va+ VB+7
which is shown in the theorem.
Law of cosines and parallelogram identity
This section summarizes useful lemmas used in the preceding sections.
In Hilbert spaces, especially in Euclidean spaces, the law of cosines holds:
|lv 01| = ||yl + ||=|| 2(y, .²).
In this paper, we use this formula as an error-containnng discrete chain rule of the squared norm. Lemma F.1. For all (+(+1), (kk) Rdd
| || ((x(++1) ((+ - (b)) - - 20(4)
-
Another famous identity for the Hilbert norm (especially the Fuclidean norm) is the parallelogram identity:
r +
σ - (1==]] + lIvvl
2
In this paper, parallelogram identity by setting a = 1/2. Lemma F.2. For all x, y Rdd and E R ||o (1 x)yll a||=|| + (1 - 1|dl| a(1 a) vll?.
generalization of this identity. In the following lemma, recover the
Proof. The claim is obtained by adding each side of the following equalities:
||az + (1 a yllll = a² | +
llvll + 2a(1 a)(x, v):
a(1 a]I - w/12 = at1 - |2||| a a(1 l111 2a - (I.
G Proofs of theorems in Section
G.1 Proof of Theorem H.1
is sufficient to show that
E(I) = ((x(1)) -
satisfies E Eu. Indeed,
E = (V)()), -IV)(>))) -x) -2pE
holds. Here, we used the chain rule, the continuous system itself, the Pf. condition, and the definition of E in this order.
22

---

G.2 Proof of Theorem H.3
By the Pt. condition, we observe that
[1) - - / x)
$ --) ff(
Thus, the evaluation of [f,, ff(x))] yields 3.
From L-smoothness L/2 follows. By the definition 8 = 0.
(ii) Z-smoothness yields a = L/2 and 3 = L. (Note that the convexity of f would imply a = 0, but it is not assumed now. If we adopt the other definition (18) then 3 0.)
(iii) By the same application of L-smoothness, we obtain a = L/8 and [ = L/2.
(iv) Since the discrete chain rule exactly holds, Vavrf satisfies 0. Then, by the T-smoothness of] f,
AVrFf(y.2) -v)()) 1//
<
[VV[TT+ (V v[<>]]d
I.Iry + +(1 -))x 2||dr
LT|ly - =/|dd
Jo
L
11y z||
holds, which implies 3 = 1./2.
(v) Similar to the case (iv),
holds. By the L-smoothness of f.
V
V
y x+ r
f(y) - f(x) -
(VF( - )
(y - v
2
||v 2|
Vf
y + x
Vf(x))
+ f(v) f(x) (VF 4 (V)()+2) y x>
2
|y - x
L
x1|
5L
ly
||.
which implics 3 5L/8.
23

---

(vi) Similar to the previous cases, a = 0 holds. Using the same notation as in Appendix D (vi), we obtain
Fi ua aa... f( aad
(Vaf(y,2) Vf(x)]|
Vf(z)
f(n M2.99 Me) f(u 32.88. US....
Yu -2d 0 +1 8 )z 22 33 .... :..
021 021/2 - (1 02) 43 ..,,, Idl
Oas (1) U2. Vs.
Oayd (1 02)
d
[1(0001A0441a - (V)(a)))
d
L? 1ly x²1
Vdllly æ||
where 0g E [0, 1] is a constant by the mean value theorem. Therefore, B = vdL holds.
G.3
Proof of Theorem H.5
Let
(R))
(x) f
- (1 (1-ch)-+E is nonincreasing If E(N) < (MF(( for 0, it can be concluded that E(K) =
and hence (x l < (1 ch)* E(O), Before starting the computation of 5 (()) transform the weak discrete Pt. condition (17) into a more convenient form. By substituting the scheme into
(17), we obtain
(1+ 3h) (1(x1t))))) Thus, it follows from the weak discrete chain rule (16), the scheme, and the above inequality, that
F /0)
7
5+ 8 (1(h)
V ( (k++) xx(k)) , t0(1)) + cabllotz00))
Vf (1++1) .z(( ,1²
= - (1 ah)
I (1 ah)
-
(1+ + Bh)2
ah
E(R)
- (1 +1+ Bh)
Hence if h < 1/a we have the convergence.
H Extension to Polyak-Lojasiewice type functions.
The weak discrete gradients can be useful also for non-convex functions. Here we illustrate by taking functions satisfying the Polylak- (Pt.) condition. A function f is said to satisfy the Pf. condition if
-|] < -2((f(x) f*)
24

---

holds for any I' Rd. This was introduced as a sufficient condition for the steepest descent to converge Polyak (1963). The set of functions satisfying the PL condition contains all differentiable
strongly convex functions and some nonconvex functions such as f(x) = x²² 3 sin (1)).
Theorem H.1 (Continuous systems), Suppose that I satisfies the Pt condition. Lea [0, oo) - IR be the solution of the gradient flow (3). Then the solution satisfies
[(x(t) ff S e e= - x=11²
Let us define another weak discrete gradient for functions satisfying the Pt. condition. Recall that the first condition of weak discrete gradients (Definition 4.1) has two meanings: the discrete chain rule (9) and the discrete convex inequality (10). One could consider the PL condition instead of convexity.
Definition H.2. A gradient approximation ff: Rd Rd + Rd is said to be Pt-type weak discrete gradient of f if there exists positive numbers B such that for all E R the following three conditions hold:
f((,x)) = Vf(x),
f(y) - f() xffl,,).yy aaly = x||;,
(16)
- -V, =||ه &
(v) --1|- =||.
(17)
Theorem H.3. If f is L-smooth and satisfies the PL condition with the parameter μ. the following functions are PL-type weak discrete gradients:
① V/ [y, x) f(x); then (a, 3) = (L/2,0).
(i)) ff x) fyy) then (a, B) = LL.
(ii) 1fV x) V f( _ ) then (a, 3) (L/8, L/2).
(iv) V x) V Avr porr((y; 2), then (a, B) 1.2).
(v) If VVV. x) = I x), then (ar 3) = (0,5L/8).
(vi) V (y, (,, then (a, B) (0, VaL).
Remark H.4. The parameters and 3 imply the magnitude of the discretization error. As the second condition Definition H.2, we can adopt instead
fw. |) S - 222(f(u) - f*) + Blly - æ|1-
(18)
Then, obtain better parameters for the implicit Euler method (ii).
The proof of Theorem H.3 is postponed in Appendix G.2.
Theorem H.5 (Discrete systems). Let V f be PL-type weak discrete gradient of f. Let of be function which satisfies the necessary conditions that the PL-type weak DG requires. Let (x(()) be the sequence given by (11). Then, under the step size condition h S 1//o, the sequence satisfies
(1 (1-2pi) -
2ph (1 -ah)
(1-ah)
-
(1+ 3h)z (f(#o) -f)
In particular, the sequence satisfies
{(x(tt) - 5 (1 2(a 3)
b
(f(zo) f*),
when the optimal step size h = 1/(2a + (3) is employed.
I Some numerical examples
In this section, we give some numerical examples to complement the discussion the main body of this paper. Note that this is just to illustrate that we can actually casily construct new concrete
25

---

methods just by assuring the conditions of weak discrete gradients (weak DGs), and that the resulting methods in fact achieve the prescribed rates; we here do not intend to explore method that beats known state-of-the-arr methods. It is of course an ultimate goal of the unified framework project, but left as an important future work.
Below we consider some explicit optimization methods derived as special cases of the abstract weak DG methods. Here we pick up simple two-dimensional problems that we can observe not only the decrease of the objective functions but also the trajectories of the points æ's for our intuitive understandings.
First, we consider the case where the objective function is L-smooth convex function. An explicit weak discrete gradient method is then found
(1(+1)) x(()
2k
+
(( - x xo(tt))).
k2
(/++1) -((k)
2k +
h2 (=(()(1)) (2(00)
(19)
4
2 (b)
2k +
(1(8) x (K)
(I: + 1)2
We call this method (wDG-c). This is the simplest example of the abstract method in Theorem 5.4, where we choose As (kh)² and (v,,x) v (xx). The authors believe this method itself has not been explicitly pointed out the literature, and is new. The expected rate is the one predicted in the theorem, O (1/k²), under the step size condition h I 1/vLL (recall that a for the weak DG is L/2 as shown in Theorem 4.2). For comparison, we pick up Nesterov's ' accelerated gradient method for convex functions
y (k+1)) (k() 12V / (x.
(20)
x (k+1) ((++)) +
1: + (y(tt1)) (b)
K
We denote this method by (NAG-c). It is well-known that it achieves the same rate, under the same step size condition; we summarize these information in Table As an objective function, we employ
(xx = 0.1., 0.001.r2²,
(21)
which is not strongly convex. (Strictly speaking, this is not L-smooth as well, but we consider in the following way: for each initial æ we obtain the level set (x [xx) (()()))). Then we consider the function (21) inside the region, and extend the function outside it appropriately; for example such that the function grows linearly as ||a:|| + oo.)
Numerical results are shown in Figure The top-left panel of the figure shows the convergence of the objective function (x) when the optimal step size 1/VL L is chosen. We see both methods achieve the predicted rate (1/k²² (mind the dotted guide line). We also that under this setting, (wDG-e) converges faster than (NAG-c). This suggests that the new framework can give rise to optimization method that is competitive state-of-the-art methods (as said before, we do not say anything conclusive on this point; in order to discuss practical performance, we further need to discuss other implementation issues such as stepping schemes.) The trajectories of (kksss are almost the same, for all the tested step sizes.
Next, we consider methods for strongly convex functions. We use the following explicit weak DG method:
2 (k+1) (k) Vuh (k(+)) -2 2((+1))
(((++)) - (k(N)= = Vuh ((k) v((+1) vf(2(*))
(22)
1
((k) (k) Vph (k)) + t((k) 2x)
We call this (wDG-sc). This can be obtained by setting V5 x) = Vf((x) in Theorem 5.5. Since for this choice we have L/2 and B 1/2 (Theorem 4.2), the step size condition is
26

---

Table 3: Step size limitations and convergence rates of the methods used in the experiments
scheme
step size limitation
convergence rate
NAG-c (20)
1/VL
wDG-c (19)
1/VL
NAG-sc (23)
1/VL
wDG-se (22)
1/(VI. VP)
0 vt)
wDG2-sc (24)
VP/(L - 1))
(1 (1- ))
10
3
10 10-4
2
f(
10-7
wDG
10 10~10
NAG
wDG-c NAG-a
10
13
10
10a
10a
10a
10a
0.5
1.5
2
(a) Evolution of function values (h 1/VT.).
(b) Trajectory (h = 1/VL).
3
2
32
wDG-c
wDG
0
NAG
0.5
1.5
2
0
0.5
1
1.5
2
31
X1
(c) Trajectory (h 0.7/ /LL.
(d) Trajectory (h 0.4/
Figure I: Trajectories and function values by (wDG-c) and (NAG-c). The objective function is (21) and the initial solution (2, 4).
27

---

S 1/(VL- vT), and the predicted rate 0 ((1 vp/L)* (which is attained by the largest == 1/vVV VT).
As before, we compare this method with Nesterov's accelerated gradient method for strongly convex functions (NAG-sc):
(((+))) ((()) h (2(tt)
x(l+1) y(kt2) + 1 vihh
1 + vph (y)ot1)-
(23)
Here, in addition to these, we also consider simpler method, where 2() = (*) is chosen to find
(k++1) - x(()= = vuh (((+t)) - -z( =2(tt))
((++1) 2(()) = Vihh (k) (((+1) vi(a(t))
(24)
We call this (wDG2-sc). This method is more natural as a numerical method for the accelerated gradient flow (6), compared to the methods above, and we expect it illustrates how "being natural as a numerical method" affects the performance. The rate and the step size limitation were revealed in the proof of Theorem 5.5 (Appendix E).
We summarized the step size limitations and rates in Table 3. Notice that the predicted rate of (wDG-sc) is better than that of (wDG2-sc).
The objective function is taken to be the quadratic function
f(x) = 0.001 x²2²² + 0.1(21 xx) + 0.01z; + 0.02x2,
(25)
and results are shown is Figure 2. Again the top-left panel shows the convergence of the objective function. We see that (wDG-sc) and (NAG-sc) with each optimal step size show almost the same convergence, which is in this case much better than the predicted worst case rate (the dotted guide line). (wDG2-sc) slightly falls behind the other two, but it eventually achieves almost the same performance + oc. The trajectories of the points (**)ss are, however, quite different among the three methods, which is interesting to observe. The trajectory of (wDG2-sc) seems to suffer from wild oscillations, while (wDG-se) generates milder trajectory. (NAG-sc) comes between these two. We need careful discussion to conclude which dynamics is the best as an optimization method, but if we consider such oscillations are not desirable (possibly causing some instability), might suggest that (wDG-sc) is the first choice for this problem. In any case, in this way we can explore various concrete optimization method within the framework the weak DG by varying the weak DG, which is exactly the main claim of this paper.
28

---

10
wDG-se
wDG2-se
2
10
f(x ((x00)
10
202
wDG2-sc
10 10-10
NAG-sc
-2
10
20
40
60
80
100
120
140
-2
(a) Evolution function values (h = 1/(VI- v for wDG-se and wDG2-sc, (b) Trajectory (h 1/(VL- WT) for wDG-sc
I1
and h 1/VT. for NAG-sc).
and wDG2-se, and h = 1/ v T. for NAG-sc).
wDG-sc
wDG2-sc
wDG2-sse sc
2
NAG-sc
2
NAG-sc
0
-2
-2
22
-1
2
0
I1
T1
(c) Trajectory (h = 0.7/vT.)
(d) Trajectory (h = 0.4/
Figure 2: Trajectories and function values by (wDG-sc), (wDG2-sc) and (NAG-se). The objective function is (25) and the initial value is (2, 3).
29


Reviews:
[{"review_id": "O037uOgsaw", "reviewer": "Reviewer_eJSN", "summary": "This paper introduces a family of oracles called wDG (weak discrete gradient) verifying (8).\nThis family constraint (8) has been created in order to make proof works in the discrete setting and has been inspired by the observation of what happens in the continuous setting.\nAs expected, authors propose results obtained running classical algorithms replacing the gradient by any of those oracles. This new framework allows including many popular algorithms using different oracles such as proximal operator.", "questions": "NA", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is concise and clear. The problem is motivated, and well explained.\nThe new framework is fairly large and authors detailed examples of classical algorithms that are included in their framework.", "weaknesses": "- It might be because I did not know this line of work, but based on the title, I thought of a completely different result, on how, using gradients on the current iterate, efficiently discretize an ODE. Finally, the proposed framework seems to be more about the nature of the oracle itself, not the algorithm, and some of them (prox, average gradients, ...) are not always accessible.\n\n- Thm 2.3: From this thm, it seems that the convergence rate can be arbitrarily good. Authors should discuss this here and mention that discretization error unables to converge faster than the proven lower bound $1/t^2$.\n\n$\\underline{\\text{Typos:}}$\n\n- l.23: « strong convex » -> strongly\n- l.164: « in of »\n- eq 10: I think \\beta and \\gamma have been permuted\n- Thm 5.2: « Let $\\bar{\\nabla} f$ be a wDG of $f$ […] let f be […] » -> « Let f be … let $\\bar{\\nabla} f$ be …. »", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading and suggestions. We really appreciate it.\nBelow are our responses to your criticisms in Weaknesses.\n\n>Weakness 1. It might be because I did not know this line of work, but based on the title, I thought of a completely different result, on how, using gradients on the current iterate, efficiently discretize an ODE. Finally, the proposed framework seems to be more about the nature of the oracle itself, not the algorithm, and some of them (prox, average gradients, ...) are not always accessible.\n\nA. We agree with the comment that if we regard weak discrete gradient as an oracle, the main focus in our paper is exactly \"the nature of the oracle itself,\" i.e., we investigate conditions wDGs should satisfy.\nWe could not catch what the reviewer meant by the second sentence. Below are some possibilities we considered.\n\nFirst, if the reviewer means that some wDGs (prox, average gradients, ...) are not acceptable as oracles for first-order methods because they lead to implicit methods, we would like to claim that this does not immediately mean that these wDGs are impractical. For example, for minimization problems with a regularization term, one can generate variants of the accelerated proximal gradient method (with the convergence rate guaranteed) by considering wDGs for the regularization term. We have experimentally confirmed that some of these methods perform better than the accelerated gradient method for some objective functions. \n\nSecond, if the problem is in that some wDGs seem to die for some objective functions (in our paper, (v) and (vi) in Thm 4.2 seem to work only for strongly-convex functions), we hope to claim that this does not immediately mean the limitation of our framework, but rather clarifies that some choices of wDG are only of limited use, which is informative for users of our framework.\n\nIf both understandings are not what the reviewer intended, it would be greatly appreciated if the reviewer could kindly rephrase the criticism. Then we are more than happy to add further response.\n\n>Weakness 2. Thm 2.3: From this thm, it seems that the convergence rate can be arbitrarily good. Authors should discuss this here and mention that discretization error unables to converge faster than the proven lower bound 1/t^2.\n\nA. Thank you for pointing out this very important point. Yes, as the reviewer says, even though in the continuous ODE arbitrarily high convergence rate seems possible, it does not at all mean that we can draw discrete schemes (actual optimization methods) out of the ODE while keeping the same high order. What happens actually is that, greedily demanding a higher rate is penalized at the timing of discretization from the numerical stability. See, for example, \n\nUshiyama, K., Sato, S., and Matsuo, T., Essential convergence rate of ordinary differential equations appearing in optimization, JSIAM Letters, 14 (2022). https://doi.org/10.14495/jsiaml.14.119\n\nWe would like to add a new remark after Thm 2.3 as follows.\n\n```\nRem 2.X. From Thm 2.3 it might seem that we can achieve arbitrarily high order rate. Although it is surely true in the continuous context, it does not imply we can construct discrete optimization methods from the ODE. In fact, greedily demanding a higher rate is penalized at the timing of discretization from the numerical stability. See, for example, the discussion in Ushiyama--Sato--Matsuo (2022).\n```\n\nThank you also for pointing out the typos. We would like to thank you again for your very careful reading."}, {"review_id": "4up0T2VOo7", "reviewer": "Reviewer_tGA7", "summary": "The paper considers unconstrained convex optimization problems, studied from the angle of their close relation with differential equations. Specifically, the authors propose a framework for translating results from continuous time methods to their discrete time counterparts. They propose Discrete Gradients (a technical tool from Numerical Analysis) as a means for achieving this, and suitably adapt the concept to the convex optimization scenario (via weak Discrete Gradients). As such, the complexity of showing convergence for DE discretizations is mostly transferred to finding the appropriate wDG. The authors then show how this framework can recover known convex optimization results for some important methods in the class.", "questions": "- Can the authors provide some discussion on why, e.g., the max stepsize for Gradient Descent (line 1 in table 2) is more restrictive compared to the known strict upper bound of 2/L? It is not clear whether this kind of situation comes from some insurmountable limitations of the framework. \n- Reference [2] is a missing reference for Lyapunov-based approaches. The paper has the same goal as the present work but achieves it via a different route, involving formulas for constructing Lyapunov functions. It would be good to briefly discuss it in the section \"Relation to some other systematic/unified frameworks\"\n- Reference [3] might be relevant for motivating the unified approach\n\n[2] De Sa, C. M., Kale, S., Lee, J. D., Sekhari, A., & Sridharan, K. (2022). From Gradient Flow on Population Loss to Learning with Stochastic Gradient Descent. Advances in Neural Information Processing Systems, 35, 30963-30976.\n[3] Bansal, N., & Gupta, A. (2017). Potential-function proofs for first-order methods. arXiv preprint arXiv:1712.04581.", "limitations": "The authors address the limitations in a separate and very clearly written section and go into adequate detail describing them. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper follows in a line of work studying discrete gradient methods as optimization schemes. While the central concept of Discrete Gradients is not novel, its weak variant used in this paper and the unifying framework built around it are, to the best of my knowledge. The studied topic is of considerable interest to the optimization community, and the tools introduced in this work are welcome additions. The paper is written in a crisp and clear style (making for a very pleasant read), and the authors critically discuss their results in (mostly) adequate detail. ", "weaknesses": "- Reference [1] seems to have quite some overlap in terms of results and considered classes of functions. In this light, a more detailed comparison is warranted in terms of e.g., assumptions -- especially on stepsize values, type of results, classes of functions, and techniques.\n- The usage of the \"free\" iterate z (introduced in Def. 4.1) when devising the discrete accelerated schemes is opaque and would benefit from further discussion. \n\n* Minor (typos and the like):\n\t- Line 315: of in \n\t- Line 315: the Hessian\n\t- you use (i), (ii) in Thm 4.2, but on page 4 line 131 you use the same notation for other concepts, which allows for confusion\n\n\n[1] Ehrhardt, M. J., Riis, E. S., Ringholm, T., and Schönlieb, C.-B. (2018). A geometric integration approach to smooth optimisation: Foundations of the discrete gradient method. arXiv preprint, arXiv:1805.06444.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading and suggestions. We really appreciate it.\nBelow are our responses to your criticisms in Weaknesses and Questions.\n\n>Weakness 1. Reference [1] seems to have quite some overlap in terms of results and considered classes of functions. In this light, a more detailed comparison is warranted in terms of e.g., assumptions -- especially on stepsize values, type of results, classes of functions, and techniques.\n\nThank you so much for pointing out this important point. We would like to add the following paragraph in \"Relation to some other systematic/unified frameworks\":\n\n```\nAs said in Section 3, in the field of numerical analysis, the use of discrete gradients has been tried. Among them, Ehrhardt et al. (2018) is a pioneering work that comes with several theoretical results. Both this and the present work aim at convex, strongly-convex, and the PL functions (in the Appendix, in the present paper). The scope of Ehrhardt et al. (2018) was limited in the sense that they considered only discretizations of gradient flows with strict discrete gradients. Our target ODEs and discretizations are not limited to that, but as its price, our rate is worse in some strict discrete gradient discretizations of gradient flow. This comes from the difference in proof techniques: they proved convergence rates directly and algebraically, while our analysis is via Lyapunov functionals. They also gave several theoretical results besides the convergence analysis, such as the (unique) existence of solutions, and step-size analysis which are important in actual implementations. Whether these two framework could be unified would be an interesting future research topic.\n```\n\n>Weakness 2. The usage of the \"free\" iterate z (introduced in Def. 4.1) when devising the discrete accelerated schemes is opaque and would benefit from further discussion.\n\nThis is a very good point, and thank you for suggesting this.\nIn fact, we can think of several possibilities for z, which are discussed in the proof of Thm. 5.4 (Appendix E.3) and Thm. 5.5 (E.4).\nPlease note also that this can be regarded as a modification of the three points descent lemma (see, for example, https://fa.bianp.net/blog/2017/optimization-inequalities-cheatsheet/).\n\nWe agree that our explanation about how we utilize z is not quite clear. We would like to add the following paragraph after Def. 4.1.\n\n```\nNote that (8) can be regarded as a modification of the three points descent lemma, where the third variable z is utilized to give some estimates. The freedom in variable z in (8) is fully utilized also in this paper; see Thm. 5.4 and 5.5 and their proofs.\n```\n\n>Weakness 3. Minor (typos and the like)\n\nThank you so much for your very careful reading. We will fix them in the final version.\n\n>Question 1. Can the authors provide some discussion on why, e.g., the max stepsize for Gradient Descent (line 1 in table 2) is more restrictive compared to the known strict upper bound of 2/L? It is not clear whether this kind of situation comes from some insurmountable limitations of the framework.\n\nThis is a very good point. We noticed this, and our understanding is as follows.\nAs far as we know, the bound $2/L$ is shown in Nesterov (2004; the textbook, Thm 2.1.14), with the rate $c_1/(c_2 + k c_3)$ ($c_1, c_2, c_3$ are some constants), which is slightly different from the rate in our paper $c/k$ (although asymptotically they are the same).\nThe rate $c/k$ is obtained in the ODE approach and the designated Lyapunov functional, but this time, we cannot have the strict bound $2/L$. In this sense, we understand this is a limitation of the ODE approach, or more specifically, the limitation in the known combination of ODE and Lyapunov functional. Whether there exists a better combination such that we can have the rate $c/k$ with the strict bound $2/L$ or not is an interesting open question.\n\n>Question 2.  Reference [2] is a missing reference for Lyapunov-based approaches. The paper has the same goal as the present work but achieves it via a different route, involving formulas for constructing Lyapunov functionals. It would be good to briefly discuss it in the section \"Relation to some other systematic/unified frameworks\"\n\nThank you so much for letting us know of this. We would like to add the following paragraph in \"Relation to some other systematic/unified frameworks\"\n\n```\nAnother closely related work is Skhari et al. (2022), which proposed a framework to construct Lyapunov functionals for continuous ODEs. This is strong in view of the fact that generally Lyapunov functionals can be found only in ad hoc ways. Instead, they considered only the simplest gradient descent (and its stochastic version), while the main focus of the present paper lies in the discretizations.\n```\n\n>Question 3.  Reference [3] might be relevant for motivating the unified approach\n\nThank you for this information. We will include this reference in Introduction where we survey the history of the ODE and Lyapunov approach.\n"}, {"review_id": "1KFXmQS7D1", "reviewer": "Reviewer_xD6M", "summary": "This paper focuses on the design of convex optimization schemes based on a general discretization framework applied to differential equations (DE). The authors heavily rely on Lyapunov based inequalities to provide convergence rates. \nThe authors build a systematic framework on top of the one proposed by Su, Boyd and Candès, allowing to provide an automatized analysis, thanks to the concept of weak discrete gradient (wDG). This weaker notion of DG allows one to overcome the assumptions needed for discrete versions of gradients in the DE approach. The resulting convergence rates turn out to be competitive, even though they might not be optimal.\n", "questions": "l81: The abbreviation PŁ is not defined in the main text. Please indicate what it stands for. (Polyak-Lojasiewicz)\n", "limitations": "There is a clear section dedicated to limitations with an explicit list:\n\n- some methods do not fall into the authors' framework, e.g., Douglas–Rachford splitting method \n- adjustment (for instance of time-stepping) could be improved for wDG\n- the obtained rates are not always optimal", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The analysis of a large class of convex optimization algorithms can now be performed in an automatized fashion. Many existing optimization methods together with their rate estimates, can be retrieved as special cases of the authors' method. This offers a simpler perspective.\n\nThe presentation of the paper is great, the authors make an effort to avoid loosing the reader into too many technicalities. Not being an expert in such convex optimization schemes, it was still enjoyable to follow most of the details. The paper is well-written.\n", "weaknesses": "The estimated rates are not always optimal as demonstrated by the authors (some sub-cases of Theorem 5.5 for strongly convex functions), which indicates that there are still specific efforts to be pursued for certain algorithms.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading and suggestions. We really appreciate it.\nBelow are our responses to your criticisms in Weaknesses and Questions.\n\n>Weakness 1.  The estimated rates are not always optimal as demonstrated by the authors (some sub-cases of Theorem 5.5 for strongly convex functions), which indicates that there are still specific efforts to be pursued for certain algorithms.\n\nThank you for pointing out this important point. We agree with your view that some rates in the present paper do not achieve known optimal rates, as we explicitly declared in Limitations. However, this comes from the limitation in the currently known \"ODE + Lyapunov functional,\" not from our framework. Let us explain this by taking the example we showed in \"Limitations.\" The rate in our paper $O((1-\\sqrt{\\mu/L})^k)$ (accelerate gradient method (AGM) rate) comes from the continuous estimate in Thm. 2.5, the term $e^{-\\sqrt{\\mu}t}$. On the other hand, the optimal rate is known to be $O((1-\\sqrt{\\mu/L})^{2k})$ (a method was given in Scoy et al. (2017), which was then shown to be optimal in Drori--Taylor (2022); the arguments are more direct, i.e., not in the ODE approach).  In the ODE approach, if we find a combination of DE+Lyapunov functional that exhibits the rate $e^{-2\\sqrt{\\mu}t}$, then wDG shall be able to derive methods achieving the optimal rate. To our best knowledge, such a combination is not yet known---but recently steady progress has been made. We the authors are aware of an ODE that seems promising, although we have not yet succeeded in finding a Lyapunov functional for it. Sun et al. (2020) derived a combination of ODE+Lyapunov functional that achieves a rate better than AGM, but it is still not optimal. In viewing this recent information, we expect to find the desired ODE+Lyapunov functional in the near future.\n\n>Question 1.  l81: The abbreviation PŁ is not defined in the main text. Please indicate what it stands for. (Polyak-Lojasiewicz)\n\nThank you so much for your careful reading. We originally spelled out this, but we somehow dropped it in finalizing the submitted paper. We will appropriately include the full spell."}, {"review_id": "nCbrA1UdxX", "reviewer": "Reviewer_7m3u", "summary": "The paper proposes a unified discretization framework for the differential equation (DE) approach to convex optimization. The DE approach relates optimization methods to continuous DEs with Lyapunov functionals, providing intuitive insights and convergence rate estimates. However, there has been a lack of a general and consistent way to transition back to discrete optimization methods. The paper introduces the concept of \"weak discrete gradient\" (wDG), which consolidates the conditions required for discrete versions of gradients in the DE approach arguments. The authors define abstract optimization methods using wDG and demonstrate that many existing optimization methods and their convergence rates can be derived as special cases of their setting.", "questions": "- Can the framework be easily extended to handle constrained optimizations (for instance, using indicator functions)?\n\n- Theorem 4.2 list several wDG for smooth and/or strongly convex function. Is it possible to find easily other wDG for sunction that does not satisfies those assumptions? (for instance, non convex smooth functions, or functions with smooth second-order derivatives?)\n\n- Can the limitations of the framework, such as the non-optimality of certain convergence rates, be overcome by considering alternative DEs and Lyapunov functionals?", "limitations": "- Non-Universal Applicability: The paper acknowledges that certain optimization methods, such as the Douglas-Rachford splitting method and methods based on Runge-Kutta numerical methods, may not fit into the current framework. The applicability of wDG to these methods remains an open question.\n\n- Practicability: While the paper indeed overcome some limitation from previous work in this vein, given the previous points in the Weakness section, it seems the approach overcomplicate the design of new accelerated methods in other settings.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "Comprehensive Approach: The paper addresses an important gap in the DE approach to convex optimization by providing a unified discretization framework. It consolidates the conditions required for discrete versions of gradients, simplifying the overall analysis.\n\nClarity: The pedagogical approach of the paper is appreciated. Most of the theory is constructive and all new aspect are clearly presented.\n\nAbstract Optimization Methods: The introduction of abstract optimization methods using wDG allows for a simpler view and analysis of existing optimization methods. It provides a systematic framework for deriving convergence rate estimates.\n\nPotential for new methods: The framework allows for the development of new optimization methods by combining known DEs with wDG. It opens up opportunities for researchers to explore novel approaches in the optimization field.", "weaknesses": "Knowing the accelerated gradient flow: The biggest problem of the approach presented in this paper is the requirement that one needs to know the accelerated gradient flow to derive its discretization - accelerated gradient flow that has been derived from an accelerated algorithm. Hence, the practicability of the approach is limited as one requires to know already an accelerated method before deriving another one.\n\nCase-Specific Discrete Arguments: The authors acknowledge the need for adjustment and optimization in the construction of optimization methods: while the framework consolidates the case-specific discrete arguments in the definition of wDG, there may still be some complexity involved in finding new pratical wDGs for different methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading and suggestions. We really appreciate it.\nBelow are our responses to your criticisms in Weaknesses and Questions.\n\n>Weakness 1. Knowing the accelerated gradient flow: \n\nWe feel the reviewer misunderstood our problem setting. Let us explain our standpoint again as follows.\nIt is surely true that our framework is on how we discretize ODEs in the ODE approach, and it cannot be invoked if we do not have any ODEs (and Lyapunov functionals). But this does not mean that we have to have a new (discrete) optimization method first to start a new generalization;  instead one can start with freely exploiting new ODEs with rate-revealing Lyapunov functionals (In fact, Celine--Taylor--Bach (2022, arXiv:2205.12772) derived ODE and Lyapunov functional without basing on existing optimization methods, and Kim--Yang (2023, ICML2023) integrated known accelerated gradient flows to derive a new ODE that has good natures of both). Then if the ODE only uses gradients (i.e. does not involve Hessian or higher derivatives), it should be an easy task to define an abstract wDG method for it and write down a discrete convergence estimate just by following the proof in the continuous case (as we demonstrated in the present paper for known ODEs/Lyapunov functionals).\nIn this sense, we claim that now people can almost forget about the final discretizations, and purely concentrate on the exploration of new ODEs/Lyapunov functionals. That is exactly the best outcome of our framework,  originally hoped in the seminal work by Su--Boyd--Candes (2014). These explanations were given in L62--69 (although it was a bit hasty due to the limitation of the space.)\n\n>Weakness 2.  Case-Specific Discrete Arguments: \n\nWe feel there is some confusion again in the reviewer. What we meant by \"Although there is still room for minor adjustments\"(L72) is described in L303--309; roughly speaking, the choice of some additional variables, and/or optimization of time-stepping. These rooms are not necessarily negative, and in some case we can utilize them for further optimizing resulting optimization methods. Even if we leave these freedoms to some obvious choices, the framework gives a convergent method and its rate.\n\nWe agree with the reviewer's view that finding a new, good wDG would be a nontrivial task. But this could be done as in usual research on creating new optimization methods; suppose we are considering some modification of an existing first-order method. Then, in our framework, it suffices to find out what serves as a wDG there, and check if it satisfies the condition of being a wDG. If so, then we know the convergence and the rate. It is also a good idea to start with an existing wDG, and consider its modification, keeping the conditions for wDG satisfied. In these ways, we believe our framework can serve as a good working environment also for considering new discretizations. \nThese were briefly explained in L62--69.\n\n>Question 1.  Can the framework be easily extended to handle constrained optimizations (for instance, using indicator functions)?\n\nYes. At this moment we have at least two directions for achieving this.\nThe first direction is to follow the DE approach for mirror descent methods, which is very briefly mentioned in Rem 1.1.\nThe second direction is to consider including indicating functions, as suggested by the reviewer. Because a linear combination of wDGs is again a wDG, we can consider a new objective function $\\tilde{f} = f + \\delta_C$ (where $\\delta_C$ is the indicating function for the domain $C$) and their wDGs.\nThese topics are outside the scope of this paper (due to the space restriction), but we have already confirmed that they work, and will report somewhere in the near future.\n\n>Question 2. Theorem 4.2 list several wDG for smooth and/or strongly convex function. Is it possible to find easily other wDG for function that does not satisfies those assumptions? (for instance, non convex smooth functions, or functions with smooth second-order derivatives?)\n\nWe cordially ask the reviewer to distinguish problems in our framework and those in the entire DE approach. \nFor non-convex and/or non-smooth functions, difficulties first lie in the DE approach itself; extensions to these objective functions are hoped, but are still left to be investigated, as far as the present authors understand.\nFor functions with higher smoothness, investigations should be done both in the DE approach and our framework. As far as we know, no DE approach theory has been established for such objective functions. Even if it does, the authors are not sure if it can be easily copied to discrete setting with our wDG framework, since there we might be demanded to use Hessians. Whether some difference of wDGs can work for approximating such Hessians or not is an interesting research topic, but we cannot say anything conclusive at this moment.\n\n>Question 3.  Can the limitations of the framework, such as the non-optimality of certain convergence rates, be overcome by considering alternative DEs and Lyapunov functionals?\n\nThank you for pointing out this important point. Yes, we believe so. For example, in the example we showed in \"Limitations\",  the rate in our paper $O((1-\\sqrt{\\mu/L})^k)$ (NAG rate) comes from the continuous estimate in Thm. 2.5, the term $e^{-\\sqrt{\\mu}t}$. On the other hand, the optimal rate is known to be $O((1-\\sqrt{\\mu/L})^{2k})$ (a method was given in Scoy et al. (2017), which was then shown to be optimal in Drori--Taylor (2022); the arguments are more direct, i.e., not in the ODE approach).  In the ODE approach, if we find a combination of DE+Lyapunov functional that exhibits the rate $e^{-2\\sqrt{\\mu}t}$, then wDG shall be able to derive methods achieving the optimal rate. Several teams are now working to solve this open question."}]

Author rebuttal:

Meta-review: All reviewers are positive about the paper. Please revise the paper and add a discussion about the practicability of your method.
Decision: Accept (poster)