Time-Reversed Dissipation Induces Duality Between Minimizing Gradient Norm and Function Value
Authors: Jaeyeon Kim
Asuman E. Ozdaglar
Chanwoo Park
Ernest K. Ryu
Venue: NeurIPS 2023 poster (2023)
Keywords: Convex Optimization
Acceleration
First-Order methods
TL;DR: Function value minimization algorithm and gradient norm minimization algorithms have a one-to-one correspondence.

Abstract: In convex optimization, first-order optimization methods efficiently minimizing function values have been a central subject study since Nesterov's seminal work of 1983. Recently, however, Kim and Fessler's OGM-G and Lee et al.'s FISTA-G have been presented as alternatives that efficiently minimize the gradient magnitude instead. In this paper, we present H-duality, which represents a surprising one-to-one correspondence between methods efficiently minimizing function values and methods efficiently minimizing gradient magnitude. In continuous-time formulations, H-duality corresponds to reversing the time dependence of the dissipation/friction term. To the best of our knowledge, H-duality is different from Lagrange/Fenchel duality and is distinct from any previously known duality or symmetry relations. Using H-duality, we obtain a clearer understanding of the symmetry between Nesterov's method and OGM-G, derive a new class of methods efficiently reducing gradient magnitudes of smooth convex functions, and find a new composite minimization method that is simpler and faster than FISTA-G.

Time- Time-Reversed Dissipation Induces Duality Between Minimizing Gradient Norm and Function Value
Jaeyeon Kim Seoul National University 11y011102@ kr.
Asuman Ozdaglar MIT EECS asuman mit.edu
Chanwoo Park MIT EECS cpark97 @mit.edu
Ernest K. Ryu Seoul National University ernestryu @ snu.ac.kr
Abstract
In convex optimization, first-order optimization methods efficiently minimizing function values have been central subject study since Nesterov's seminal work 1983. Recently, however, Kim and Fessler's OGM-G and Lee et al.'s FISTA-G have been presented as alternatives that efficiently minimize the gradient magni- tude instead. this paper, we present H-duality, which represents a surprising one-to-one correspondence between methods efficiently minimizing function val- ues and methods efficiently minimizing gradient magnitude. In continuous time formulations, H-duality corresponds reversing the time dependence of the dis- sipation/friction term. To the best our knowledge, H-duality is different from Lagrange/Fenchel duality and is distinet from any previously known duality symmetry relations. Using H-duality, we obtain a clearer understanding of the symmetry between Nesterov's method and OGM-G, derive new class of methods efficiently reducing gradient magnitudes of smooth convex functions, and find a new composite minimization method that is simpler and faster than FISTA-G.
1 Introduction
Since Nesterov's ' seminal work of 1983 [37], accelerated first-order optimization methods that effi- ciently reduce function values have been central to the theory and practice of large-scale optimization and machine learning. In 2012, however, Nesterov initiated the study of first-order methods that efficiently reduce gradient magnitudes of convex functions [41]. convex optimization, making the function value exactly optimal is equivalent to making the gradient exactly zero, but reducing the function-value suboptimality below threshold is not equivalent to reducing the gradient magnitude below threshold. This line of research showed that accelerated methods for reducing function values, such as Nesterov's s FGM [37], the more modern OGM [26], and the accelerated composite optimization method FISTA [11] are not optimal for reducing gradient magnitude, and new optimal alternatives, such as OGM-G [29] and FISTA-G [31], were presented.
These new accelerated methods for reducing gradient magnitudes are understood far less than those for minimizing function values. However, an interesting observation of symmetry, described in Section was made between these two types of methods, and it was conjectured that this symmetry might be key to understanding the acceleration mechanism for efficiently reducing gradient magnitude.
Contribution. We present surprising one-to-one correspondence between methods efficiently minimizing function values and methods efficiently minimizing gradient magnitude. We call this correspondence H-duality and formally establish duality theory in both discrete- and continuous- time dynamics. Using H-duality, we obtain a clearer understanding of the symmetry between FGM/OGM and OGM-G, derive new class of methods efficiently reducing gradient magnitudes, and find a new composite minimization method that simpler and faster than FISTA-G, the prior state-of-the- -frt---r----tt in efficiently reducing gradient magnitude in the composite minimization setup.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1.1 Preliminaries and Notation
Given F" argminzer* f(x) for minimizer, if one exists. Throughout this paper, we assume f. * -00, but we do not always assume a minimizer x, exists. Given a differentiable f: R² + R and pre-specified value of L > O, we define the notation
+ F:
R. write f. inf f(z) E 00) for the minimum value and x, E
[c. v] = f(v) - (xx + (V/(v), y)
[x, yl == f(y) - f(x) + (Vf(y), v) + 2L
[Vf(2) vf(')]|
1
[a, +| == f.- f(x) + 2L [x)(
for x, y E R A differentiable function f: _ + R is convex if the convexity incquality [a, y] S 0 holds for all z, y E R.. For L > 0, a function f: _ + R is L-smooth convex if it is differentiable and the cocoercivity inequality [ y/] < 0 holds for all x, y E Rd [42]. If f has a minimizer z., then [xr, #1 = x.]] but the notation [ *1 is well defined even when a minimizer x, does not exist. If f is L-smooth convex, then [I, *] I O holds for all x E R [42].
Throughout this paper, we consider the duality between the following two problems.
(P1) Efficiently reduce fxxx f. assuming I, exists and || x. |l - R.
(P2) Efficiently reduce 2L | (yN) assuming f+ > -o0 and f30) - f. S R.
Here, R E (0, oo) is a parameter, Th and yo denote initial points of methods for (P1) and (P2), and IN and yN denote outputs of methods for (P1) and (P2).
Finally, the standard gradient descent (GD) with stepsize is
Fi+1 = Vi (1;;). i= i=
(GD)
1.2 Prior works
Classically, the goal of optimization methods is to reduce the function value efficiently. In the smooth convex setup, Nesterov's 's fast gradient method (FGM) [37] achieves an accelerated O(1/N3)-rate and the optimized gradient method (OGM) [26) improves this rate by a factor of which is, in fact, exactly optimal [18].
On the other hand, Nesterov initiated the study of methods for reducing the gradient magnitude of convex functions [41] as such methods help us understand non-convex optimization better and design faster non non-convex machine learning methods. For smooth convex functions, (GD) achieves (( f-) / /N)-N r-atte on the squared gradient magnitude [34, Proposition 3.3. while (OGM-G) achieves accelerated ((f(xx)) - f.) ////) [29], which matches lower bound and is there- fore optimal [35, 36). Interestingly, (OGM) and (OGM-G) exhibit an interesting hint of symmetry, as we detail in Section 2, and the goal of this work is to derive more general duality principle from this observation.
In the composite optimization setup, iterative Ahrinkage-thresholddee algorithm (ISTA) [13, 45, 16, 14] achieves a O(1 /l2//N / -rate on function- suboptimality, while the fast iterative shrinkage- thresholdng algorithm (FISTA) [11] achieves an accelerated O x= /Nat- On the squared gradient mapping norm, FISTA-G achieves (((F(ro)
F-)/N²)-rate [31], which optimal [35, 36). Analysis of an accelerated method often uses the estimate sequence technique [38, 8, 39,9 9, 40, 32] or a Lyapunov analysis [37, 11, 50, 10, 53, 1, 5, 6, 7, 433. In this work, we focus is simpler and more amenable to continuous-time view.
on the Lyapunov analysis technique,
The notion of duality is fundamental in many branches of mathematics, including optimization. Lagrange duality [46, 47, 12]. Wolfe duality [57, 15, 49, 33], and Manchel-Rockachellee duality [20, 46] are related (arguably equivalent) notions that consider a pairing of primal and dual optimization problems. The recent gauge duality [21, 22, 3, 58) and radial duality [24, 23) are alternative notions of duality for optimization problems. Attouch-Théra duality [4, 48) generalizes Cenchel-Rockachedr to the setup of monotone inclusion problems. In this work, we present H-duality, which is notion of duality for optimization algorithms, and is, to the best of our knowledge, distinct from any previously known duality symmetry relations.

---

2 H-duality
In this section, we will introduce H-duality, state the main H-duality theorem, and provide applications. Let N 2 be pre-specified iteration count. Let & JogickeN be an array of (scalar) stepsizes and identify it with a lower triangular matrix H E RNNN via Hx-1,i+1 = 1.+1,, if < i S k S N - 1
and H 0 otherwise. An N-step Fixed Step First Order Method (FSFOM) with H is
rk+1 2R
L Vf(x.),
O
==0
for any initial point E Rd and differentiable f. For H E RNNN define its anti-transpose HA E NNN with H.* HN-j+t.N-441 for i,j 1, I....,N.. N. We call [FSFOM with HA] the H-dual of [FSFOM with H].
2.1 Symmetry between OGM and OGM-G
Let f be an T-smooth convex function. Define the notation 2 [V((() for E RR.. The accelerated methods OGM [19, 26] and OGM-G [29] are
Tk+1 = Fig + 0₂=
Ox
(x xx +
( - -bk)
(OGM)
Bx+1
8x+1
Wk+1 = y + (0N-x 1)(20 N k-1 -- 1)
2k-
(ut w 20 - (4) yn) (OGM-G)
ON (20 1)
for h = 0, .....,, . 1, 1, where ( are defined as 0n = 1, 02 c++ 0,+1 0Z for O - 2, and B% ON 20 y (OGM) and (OGM-G) are two representative accelerated methods for the setups (P1) and (P2), respectively. As surface-level symmetry, the methods both access the [0:] sequence, but (OGM-G) does in a reversed ordering [29]. There turns out be a deeper- level symmetry: (OGM) and (OGM-G) are H-duals of each other, i.e., HôGM HOGM-G- The proof structures of (OGM) and (OGM-G) also exhibit symmetry. We can analyze (OGM) with the Lyapunov function
L Us = 2 11000
k +
x.112
11
Σ 1=
ui Fi, Fi+ ]
u Ui 1i-1) si]] Σ 1=0
(2)
2
for - S N with {u,) = (203..... 20 (3) and u-1 = O. Since [.- S 0 and {
is a positive monotonically increasing sequence, {lls J is dissipative, i.e., Uv S UN S ...
Uo S Uu..
L 200 - x 11 + =1| 2 UN SU1==
Oy (f(xN) - f.) s Oy (f(zN) - ff) +
2
where 2 14-ييي - Vzzz)) The justification of (+) is the main technical challenge of this
1=0
analysis, and it is provided in Appendix B.2. Dividing both sides by 02 we conclude the rate
1 L 200 11
[(NN) By
Likewise, we can analyze (OGM-G) with the Lyapunov function
V/2 vo (f(y)) f- [TuN, x]]
Σ
U [vs
Mitil
(we+1 u.) vi]
==0
for 0 < k N with [ril.No
Similarly, (Va) k=o is dissipative, so
0%
20
206
2L [V (0) VN S Vo
ox (f(1)) - fa) + By [UN * S Øy (f(w)) - f*).
'Throughout this paper. we use the convention of denoting iterates of given "primal" FSFOM as while denoting the iterates of the H-dual FSFOM yk.
3

---

Again, the justification of (o) is the main technical challenge of this analysis, and it is provided in Appendix B.2. The crucial observations are (i) u, 1/ for I I N and (ii) the convergence rates share the identical factor 1/0% = 1/uN vo- Interestingly, a similar symmetry relation holds between method pairs (OBI.-)) (OBL--G)][44) and (GDD) (GD)), which we discuss later in Section 2.4.
2.2 H-duality theorem
The symmetry observed in Section 2.1 is, in fact, not a coincidenc. Suppose we have -sstep FSFOMs with H and HA. We denote their iterates as {r:}i-o and {y: For clarity, note that {u.} are free variables and can be appropriately chosen for the convergence rate analysis. For the FSFOM with
==0
H, define [ with the general form (2) with u-1 = 0. If O = u-1 S uo S S ... S uN. then {Uds ( is monotonically nonincreasing (dissipative). Assume we can show
uN([(EN) - f.) s UN (V Vf(o)),........ (((E))) R²))
(CI)
To clarify, since {asti lies within span Vf(zo).... Vf(x))), the UN depends (zo, (Vf(=))) {u.) H). If (CI) holds, the FSFOM with H exhibits the convergence rate
L 2 1100 x.1.
uN(((IN) f.) S UN S...... su
For the FSFOM with HA define { with the general form (3). Also, note that {w are free variables and can be appropriately chosen for the convergence rate analysis. If S vo S 01 S ...5 UN. then (Vx k= is monotonically nonincreasing (dissipative). Assume we can show
2L [V S VN
(V yo, Vf(vo), ... Vf(UN) E Rd, ER.
(C2)
To clarify, since { = lies within span[yo. Vi(wo),..., V((y))), the VN depends on (yo. (Vf(u)) far fer A)) . If (C2) holds, the FSFOM with H exhibits the convergence
rate
[f S VNN ... V. (f(v0) f.) + volUN, +1 S do (f(re) f.). (5) 2L
We now state our main H-duality theorem, which establishes a correspondence between the two types of bounds for the FSFOMs induced by H and H
Theorem 1. Consider sequences of positive real numbers {w and {v.) related through i/ for = 0,...,N, N. Let H E TR. NxN be lower triangular. Then,
(CC1) is satisfied with {u and H]]
N (C2) satisfied with { and HA
Theorem provides a sufficient condition that ensures an FSFOM with H with a convergence guarantee on (f(xN) f.) can be H-dualized obtain FSFOM with / with convergence guarantee on /Vf To the best of our knowledge, this the first result establishing a symmetrical relationship between (P1) and (P2). Section 2.3 provides proof outline of Theorem 1.
2.3 Proof outline of Theorem 1
Define
N
L
1
U: Un - (xw-ux(((E))) -
fa) x4
Fo
+
L
Σ
(u:
1=0
1 V: V2 2 |f(lN))1?
Expanding U and V reveals that all function value terms are eliminated and only quadratic terms of [V](x)) and (V/ No remain. Now, (C1) and (C2) equivalent the conditions
U U20. 0, A (VS(20), Vs(xx) [R))
V V20 A (VS())).... VS(N)) E IR.))

---

respectively.
Next, define = Vfall E (x+(N+)) and By = (V(w)) VS(uN)] Rdx(N+1), We show that there is SH,, u) and T(H u) gN+1
such that
U= Tr (I,)((H,))))))
== Tr ( ,0)g))
Next, find explicit invertible matrix M(u) R(++1)x(N+1) such that S(H, u) M(u)TT(H4, u)M((u). Therefore,
Tr (9,
Tr (HHT((HA .0)9))
with By = ( and conclude the proof. This technique of considering the quadratic forms of Lyapunov functions as trace of matrices is inspired by the ideas from the Performance Estimation Problem (PEP) literature [19, 55]. The full proof is given in Appendix A.
2.4 Verifying conditions for H-duality theorem
In this section, we illustrate how to verify conditions (C1) and (C2) through examples. Detailed calculations are deferred to Appendices B.1 and B.2.
Example 1. For (OGM) and (OGM-G), the choice
1
{u = (20).... ..., ,2,0,,00 20.-1:03)
(u))
0g
20
203
leads to
U=0, 0,
= 0.
Therefore, (CI) and (C2) hold.
Example 2. Again, define 2
4. f(z)
for E RRd Consider the FSFSOMs [44]
k
t++1 = = +
( - x +
( - xx)
== 0
NN N-2
h: ++ 3
k + 3
(OBL-F,)
N 1
N (x (IN-1-IN- IN-1)
IN = و
+
(x 2) +
2( + 1)
2(7 1)
and
N
N
81 = y0 +
(16 vti) +
(NO - yo)
2(7 + 1)
2(> + 1)
(OBL-G,)
N - k
N k: - 1
where v+, yo. xt, k w0t yズ 1) N ++2 (yt yk) == l=
2k+1 1 y
xo and 7 (NN + 1)/2. It turns out that (OBL-F,) and (OBL.G, are
H-duals of each other. The choice
1.2
N(N+1) 11
2
72 +7), (u:) (
N(V+IJ
1-2
2
leads to
N
N-1
U
ui-1
[f(x)) = 2L
to
U U++1-U
|V - ff(xn)
2L
2L
0=0
where u_1 0. Since U and V are expressed sum of squares, (CI) and (C2) hold.
Example Interestingly, (GD) is self-dual FSFOM in the H-dual sense. For the case h the choice
{u (...,
(2N+1)(+41) 2N-1
2N. ....,2N++1 +1),
fur = 12
N+i (2N+1(N-44)...
leads to
U= Σ
$6 (Vf(a))
V= Σ ty (V)())) Vf(g,)
OSLJEN
OSIJEN
for some {8iz) and {4iz} stated precisely in Appendix B.2. V V 0 can established by showing that the ((yj) forms diagonally dominant and hence positive semidefinite matrix [29]. U > 0 can be established with a more elaborate argument [19], but that is not necessary; 2 0 implies (C2), and, by Theorem 1, this implies (C1).
5

---

2.5 Applications of the H-duality theorem
family of gradient reduction methods. Parameterized families accelerated FSFOMs for reducing function values have been presented throughout the extensive prior literature. Such fami- lies generalize Nesterov's method and elucidate the essential algorithmic component that enables acceleration. For reducing gradient magnitude, however, there are only four accelerated FSFOMs (OGM-G), (OBI.-G,), and M-OGM-G [60], and [17, Lemma 2.6]. Here, we construct a simple parameterized family of accelerated FSFOMs for reducing gradient magnitude by H-dualizing an accelerated FSFOM family for reducing function values.
Let (4i) and {Ti) be sequences positive real numbers satisfying &f S 27; = =i by for S i S N and fy - TN = E)= Consider a family of FSFOMs
#k+1 at (Tr 16)lx+1 (at =
(13 -TE)la+! (# -xx)
(6)
Tx
TxTx-1
for k = O... 1, where xー = 20. This family coincides with the GOGM of [28]. and exhibits the rate [28, Theorem 5]
1 L TN 2 aav I.11
f(xN) - f. S
which can be established from (2) with i4 T; for < <i <iSN.
Corollary 1. The H-dual of (6) is
Mk++ V/ + (N- TN TN-x(tN-k -
(yt vīt1) + (L - Tw -Tw-)((N-R-1-1) (yt Mks
TN-N(tN-k11)
for k = O,.... N - 1, where yー = yo. and it exhibits the rate
1
[[ & TN
(f(w0) - f.).
2L
Proof outline. By Theorem 1, (C2) holds with v, = 1/TN for sis N. We then use (5).
When T; f for 0 Sis N. the FSFOM (6) reduces to Nestrov's s FGM [37] and its H-dual is.
to the best of our knowledge, new method without a name. If 1 27; for 0 < i s N - and
i = Tv. (6) reduces to (OGM) and its H-dual is (OGM-G). If + for S S N and
ty = (N + 1), (6) reduces to (OBL-F,) and its H-dual is (OBL-G,).
Gradient magnitude rate of (GD). For gradient descent (GD) with stepsize h, the H matrix is the identity matrix scaled by ht and the H-dual is (GD) itself, i.c., (GD) is self-dual. For 0 < h < 1, the rate [( S 2N I0 x. 122 originally due [19], can be established from (2) with {u, I = (..., (2N++1)(++1)
2N ,....,2Nh + 1). Applying Theorem leads to the following.
Corollary 2. Consider (GD) with 0 < h - applied to an L-smooth convex f. For N 2 1,
(f(x)) f- 2Nh +1 ' ' Jh + 1) )
L I xx
2L [f([N)) < min
To the best of our knowledge, Corollary 2 is the tightest rate on gradient magnitude for (GD) for the general step size 0 < h < 1, and it matches [53, Theorem 3] for h = 1.
Resolving conjectures of A' opptimallyyy of (OGM-G) and (OBL-F,). The prior work of [44] defines the notion of A A*-optimality, certain restricted sense of optimality of FSFOMs, and shows that (OGM) and (OBL-F,) are A oottmall under certain set relaxed inequalities. On the other hand, A -ottimaalyyy of (OGM-G) and (OBL-G,) are presented as conjectures. Combining Theorem I and the A -ptoiiaalyy of (OGM) and (OBL-F,) resolves these conjectures; (OGM-G) and (OBL-GG,) are A optimal.

---

2.6 Intuition behind energy functions: Lagrangian Formulation
Ome might ask where the energy functions (2) and (3) came from. In this section, we provide an intuitive explanation of these energy functions using the QCQP and its Lagrangian. Consider an FSFOM (1) given with a lower triangular matrix H RN with function f. resulting in the sequence {ata J To analyze the convergence rate of the function value, we formulate the following optimization problem:
sup f(EN) f+
subject to f: + R is L-smooth convex,
- - R².
However, this optimization problem is not solvable, as f is functional variable. To address this, [19, 55] demonstrated its equivalence to QCQP:
sup [(NN) - fx
subject [,, S [-I... NJ?, | 2. Hi
where r-1: x. To clarify, the optimization variables (V/(x;), [x;)) S.. zo, and x. since { lies within spanfxo, Vf(zo),.... Vf(z))). We consider relaxed optimization problem as [26]:
sup f
[(NN
subject to
[x,, x.+11 1] s 0, i= O,......,, -- -1, [x,, SO, i= I..,,..,,NN
Ial0 1= R²
Now, consider the Lagrangian function and the convex dual.
N-1
CJ, (as No- (b:) ar) ((N +
Σ a:[ r++l
[r. mx] + al x.11? aR?
where fa, No11 [b:) and a are dual variables which are nonnegative. Considering a- and oN = 1, the infimum of Li equals -oo unless b; = a; - a for 0 < S N. Therefore, by introducing uN 2a
L and u, = a,uN for 0 S i N, the convex dual problem can be simplified as
follows:
LR Bu
inf (u. Ria
N Σ p (w: w-))( 2 2o.tt. uN([(=N)) (4)) 11000 1.11
L
N-1
inf
N nonnegative nondecreasing.
the above two constraints holds for {w:) we have [(xx) - S. S R2. This understanding motivates the introduction (2) and (C1). We can perform similar analysis on the gradient norm minimization problem with the relaxed optimization problem follows:
2uN
1 fy
sup f
2L
subject to
[Iv. Vi+ 1 $ 0, i= 1,..,, -11, [VN. v.l S 0, i= 1
[uN. +1 0, f(yo)
R.
Finally, we note that although (2) and (3) both originate from the relaxed optimization problems, they have been commonly employed to achieve the convergence analysis. The function value convergence rate of OGM[26], FGM[37], G-OGM[28), GD[19], OBL-F, [44] can be proved by using (2) with appropriate {u, J- The gradient norm convergence rate of OGM-G[29), OBL-G,[44], M-OGM- G[60], and [17, Lemma 2.6] can be proved by using (3) with appropriate {w: h. We also note that recent works [2, 25] do not employ (2) achieve the convergence rate, particularly for gradient descent with varying step sizes.

---

3 H-duality in continuous time
We now establish continuous-time analog of the H-duality theorem. As the continuous-time result and, especially, its proof is much simpler than its discrete-time counterpart, the results of this section serve vehicle convey the key ideas more clearly. Let ''' be pre-specified terminal time. Let (t, s) be an appropriately integrable" real-valued kernel with domain {(t. s) |0 < s <<<<<< We define Continuous-time Fixed Step First Order Method (C-FSFOM) with H
x(0) 2o, ((1)= = (()=-J. I. ( ((())))((((S))))))))))))))))(()) ds,
AA (0,
(7)
for any initial point Zo E Idd and differentiable f. Note. the Euler discretization of C-FSFOMs (7) corresponds to FSFOMs (1). The notion of C-FSFOMs has been considered previously in [30].
Given kernel (t, s). analogously define its anti-transpose as (t, 8) = H(T - 8, T t). We call
[C-FSFOM with A] the H-dual of [C-FSFOM with H]. In the special case [t, 8) = -(())
for some function 7-), the C-FSFOMs with H and its H-dual have the form
(t) (())X(((()) + (O( = 0 (t) + -T + ()(( =0
(C-RSFOM with (t, s) e (())))(())
(C-FSFOM with (t,t, s))
Interestingly, friction terms with Y have time-reversed dependence between the H-duals, and this is why refer this phenomenon time-reversed dissipation.
3.1 Continuous-time H-duality theorem
For the C-FSFOM with H, define the energy function
1 u(I) - [ x. + L( (s(s)( X(s)]ds
88)
for t E [0, T] with differentiable u: (0,7) - R. If u u'()) 2 0. then (U(t)e)joo is dissipative. Assume can show
u(T) (F(X(T)) - f.) s (T) (VX(0), x., (V(X)) ERR)
(C3)
Then, the C-FSFOM with H exhibits the convergence rate
(f(X(())) - s (TT) - (((0) = 2 X - 12112.
For the C-FSFOM with HA, define the energy function
V(t) = v()) - -f(((((((())))((())))))))) + [' ) (T)))
(9)
for t E [0, l'I with differentiable (O,T) - R. If o(()) 2 0. then (V())e is dissipative.
Assume we can show
Ie
( S V(T) (VY()), (V)(( Rd).
(C4)
Then, the C-FSFOM with A exhibits the convergence rate
(V)()))) < V(T) < ((0) = (0) S c00) ((((())))))))))))))))))))))))))) f.).
Theorem 2 (informal). Consider differentiable functions u, v: (0. T) + R related through v())
((T-r) for E [0, T). Assume certain regularity conditions (specified in Appendix C.2). Then,
(C3) is satisfied with u(-) and H]
[(C4) is satisfied with v(-) and H
The formal statement of 2 and its proof are given in Appendix C.2. Loosely speaking, we can consider Theorem as the limit of Theorem 1 with N + oc.
IIn this paper, we avoid analytical and measure- measure-theoretic details and focus convergence (rather than existence) results of the continuous-time dynamics.
8

---

3.2 Verifying conditions for H-duality theorem
As an illustrative example, consider the case H(,,)) Fr for r 2 3 which corresponds to an ODE studied in the prior work [50. 51]. For the C-FSFOM with H, the choice u(t) 2rr-1 for the dissipative energy function (2((t)) of (8) leads to
u(T) - u(T (f(X(T) - f.) = [ ("
(r=3)a
(((s) ds. 2(r-1)
+
4(r-1)
For the C-FSFOM with HA, the choice v(t) u(T-t)
2(r-1)
for the dissipative energy function ()
(V())== of (9) leads to
V(T) (V 2(r- () (Y Y(MII
/
3) 20--000-30077770000000000000 (00000000)0000000000))-0 ds.
(T-8))
Since the right-hand sides expressed sums/integrals of squares, they are nonnegative, (C3) and (C4) hold. (By Theorem 2, verifying (C3) implies (C4) and vice versa.) The detailed calculations provided in Appendix C.I.
3.3 Applications of continuous-time H-duality theorem
The C-FSFOM (7) with Hl, CDP 1F+1
recovers
x(1) + p+1 Cpp
an ODE considered in [56]. The rate f(X(T)) - f+ 2CTF (X(0) - =z.1² can be established from (8) with u(t) = Ct.. The C-FSFOM with H can be expressed as the ODE
((1) T-1
2p
(() +0) 1)
0.
(10)
By Theorem using (9) with (t) लリーニ leads the rate
[V(((()) S 1 2
CTP (O)
Note that the continuous -ie models of (OGM) and (OGM-G), considered [51], are special cases of this setup with p 2 and C' = 1/2. The detailed derivation and well-definedness of the ODE are presented in Appendix C.3.
4 New method efficiently reducing gradient mapping norm: (SFG)
In this section, we introduce novel algorithm obtained using the insights of Theorem Consider minimizing F(x) := f(z) + g(z). where f: Rd + R is L-smooth convex with 0 < L < oc and g: Rdd U { po) is a closed convex proper function. Write F, = inf F(r) for the minimum
value. For 0, define the a-proximal gradient step
B. argmin f()) + (Vf(v), v) + 9(2) =ER*
aL
|| v1() Prox a 2
at al - v
(v 1
Consider FSFOMs defined by lower triangular matrix H (ha.coosikss follows:
k
Ik+1 = Fk Σ
ahut1, (xz - 2 B.a), =k= O....,N -
When g = 0, this reduces to (1). FISTA [1I], FISTA-G [31] and GFPGM [27] are instances of this FSFOM with = 1. In this section, we present new method for efficiently reducing the gradient mapping norm. This method faster than the prior state-of-the-ar FISTA-G [31] by constant factor of 5.28 while having substantially simpler coefficients.

---

Theorem 3. Consider the method
B.4
(N-R+1)(2N-2+
8,
(4N-IR-D)2N-2k-)
4.4 (
Uk+1 = U/ + (N-R+3)(2N-2H44
UUs
- 1k-11
+
6(N 6NN
(Uk
yk
UN = -1 10
...4
UN -
00.4
22
69.4
+
3
UN-1
0.4
- yN-1)
(SFG)
40
for k- = 0 N- - 2, where V-1
0.4 yoo This method exhibits the rate
||e|| S 251. |ow vEBF
min
UN S (N () +3
50L
(F(yo) - F.).
We call this method Super FISTA-G (SFG), and in Appendix D.3, we present a further general parameterized family (SFG-family). To derive (SFG-family), we start with the parameterized family GFPGM [27]. which exhibits an accelerated rate on function values, and expresses it as FSFOMs with H. We then obtain the FSFOMs with H C, where C a lower triangular matrix satisfying certain constraints. We find that the appropriate H-dual for the composite setup is given by this H + C, rather than A We provide the proof of Theorem 3 in Appendix D.2.
(SFG) is an instance of (SFG-family) with simple rational coefficients. Among the family, the optimal choice has complicated coefficients, but its rate has leading coefficient of 46, which is slightly smaller than the 50 of (SFG). We provide the details Appendix D.4.
5 Conclusion
In this work, we defined the notion of H-duality and formally established that the H-dual of an optimization method designed to efficiently reduce function values is another method that efficiently reduces gradient magnitude. For optimization algorithms, the notion of equivalence, whether informal or formal [59]. is intuitive and standard. For optimization problems, the notion of equivalence is also standard, but the beauty of convex optimization is arguably derived from the elegant duality of optimization problems. In fact, there are many notions of duality for spaces, problems, operators, functions, sets, etc. However, the notion of duality for algorithms is something we, the authors, are unfamiliar with within the context of optimization, applied mathematics, and computer science. In our view, the significance of this work establishing the first instance of a duality of algorithmss The idea that an optimization algorithm is an abstract mathematical object that we can take the dual of opens the door to many interesting questions. In particular, exploring for what type of algorithms the H-dual or similar notion of duality makes sense is an interesting direction for future work.
Acknowledgments and Disclosure of Funding
We thank Soonwon Choi, G. Bruno De Luca, and Eva Silverstein for sharing their insights as physicists. We thank Jaewook J. Suh for reviewing the manuscript and providing valuable feedback. We are grateful to Jungbin Kim and Jeongwhan Lee for their valuable discussions at the outset of this work. J.K. and E.K.R. were supported by the National the Samsung Science and Technology Foundation (Project Number SSTF-BA2101-02), C.P. acknowledges support from the Xianhong Wu Fellowship, the Korea Foundation for Advanced Studies, and the Siebel Scholarship. A.O. acknowledges support from the MIT-IBM Watson AI Lab grant 027397-001 Trustworthy Al grant 029436-00103 and the MIT-DSTA grant 031017-00016. Finally, we also thank anonymous reviewers for giving thoughtful comments.
References
[1] K. Ahn and S. Sra. From Nesterov's estimate sequence to Riemannian acceleration. COLT, 2020.
[2] J. M. Altschuler and P. A. Parrilo. Acceleration by stepsize hedging II: Silver stepsize schedule for smooth convex optimization. [TtI:2309.165334 2023.
[3] A. Y. Aravkin, J. Burke, Drusvyatskiy, M. Friedlander, and K. MacPhee. Foundations of gauge and perspective duality. SIAM Journal Optimization, 28(3):2406-2433 2018.
10

---

[4] H. Attouch and M. Théra. A general duality principle for the sum of two operators. Journal of Convex Analysis, 3:1-24, 01 1996.
[5] J.-F. Aujol and C. Dossal. Optimal rate of convergence of an ODE associated the fast gradient descent schemes for b > 0. HAL Archives Ouvertes, 2017.
[6] J.-F. Aujol, C. Dossal, G. Fort, and É. Moulines. Rates of convergence of perturbed FISTA-based algorithms. HAL Archives Ouvertes, 2019.
[7] J.-F. Aujol, Dossal, and A. Rondepierre, Optimal convergence rates for Nesterov acceleration. SIAM Journal on Optimization, 29(4):311-33153 2019.
[8] A. Auslender and M. Teboulle. Interior gradient and proximal methods for convex and conic optimization. SIAM Journal on Optimization, 16(3):697-725, 2006.
[9] M. Bacs. Estimate sequence methods: extensions and approximations. 2009.
[10] N. Bansal and A. Gupta. Potential-function proofs for gradient methods. Theory of Computing, 153)) 2019.
[11] A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183-2000 102-222, 2009.
[12] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
[13] R. E. Bruck. On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space. Journal of Mathematical Analysis and Applications, 61(1):159-16
1977.
[14] L. Combettes and V. R. Wajs. Signal recovery by proximal forward-backward splitting. Multiscale Modeling and Simulation, 4(4): 168-1200, 2005.
[15] G. B. Dantzig, E. Eisenberg, and R. W. Cottle. Symmetric dual nonlinear programs. Pacific Journal of Mathematics, 15(3):809 812, 1965.
[16] I. Daubechies, M. Defrise, and C. De Mol. An iterative thresholding algorithm for linear inverse problems with sparsity constraint. Communications Pure and Applied Mathematics, 57(11):1413-1457 2004.
[17] J. Diakonikolas and P. Wang. Potential function-based framework for making the gradients small in convex and min-max optimization. SIAM Journal on Optimization, 32(3):1668-169) 2021.
[18] Y. Drori. The exact information-bast complexity of smooth convex minimization. Journal of Complexity, 39:1-16, 2017.
[19] Y. Drori and M. Teboulle. Performance of first-order methods for smooth convex minimization: a novel approach. Mathematical Programming, 145(1):451-44) -482, 2014.
[20] W. Fenchel. On conjugate convex functions. Canadian Journal of Mathematics, 1(1):73-77,
1949.
[21] R. M. Freund. Dual gauge programs, with applications to quadratic programming and the minimum-norm problem. Mathematical Programming, 38(1):47-67, 1987.
[22] M. P. Friedlander, I. Macê do, and T. K. Pong. Gauge optimization and duality. SIAM Journal on Optimization, 24(4):1999-2022, 2014.
[23] B. Grimmer. Radial duality part II: Applications and algorithms. arXiv:2104 2021.
[24] B. Grimmer. Radial duality part Foundations. arXiv:2 1179, 2022.
[25] B. Grimmer. Provably faster gradient descent via long steps. arXiv:2307.06324 2023.
[26] D. Kim and A. Fessler. Optimized first-order methods for smooth convex minimization. Mathematical Programming, 1190)) 2016.

---

[27] D. Kim and J. A. Fessler. Another look at the fast iterative shrinkage//breshooddnng algorithm (FISTA). SIAM Journal on Optimization, 28( 1):223325, 2018.
[28] D. Kim and J. A. Fessler. Generalizing the optimized gradient method for smooth convex minimization. SIAM Journal on Optimization, 28(2): 1920-19900- 2018.
[29] D. Kim and A. Fessler. Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions. Journal of Optimization Theory and Applications, 188(1):192-219, 2021.
[30] J. Kim and I. Yang. Unitying nesterov's accelerated gradient methods for convex and strongly convex objective functions: From continuous-time dynamics to discrete-time algorithms. ICML, 2023.
[31] J. Lee, C. Park, and E. K. Ryu. A geometric structure of acceleration and its role in making gradients small fast. NeurlPS, 2021.
[32] B. Li, M. Coutiño, and G. B. Giannakis. Revisit of estimate sequence for accelerated gradient methods. ICASSP, 2020.
[33] O. L.. Mangasarian and J. Ponstein. Minmax and duality in nonlinear programming. Journal of Mathematical Analysis and Applications, 1 11:00-5518, 1965.
[34] A. Nemirovski. Optimization II: Numerical methods for nonlinear continuous optimization. 1999.
[35] A. Nemirovsky. On optimality of Krylov's information when solving linear operator equations. Journal of Complexity, 122):121 1991.
[36] A. S. Nemirovsky. Information-base complexity of linear operator equations. Journal of Complexity, 8()):133-77,, 1992.
[37] Y. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence (1/kk)) Proceedings of the USSR Academy of Sciences, 269:543-547, 1983.
[38] Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(():127-152, 2005.
[39] Y. Nesterov. Accelerating the cubic regularization of Newton's method on convex problems. Mathematical Programming, 11((1)155-181)) 2008.
[40] Y. Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341-362, 2012.
[41] Y. Nesterov. How to make the gradients small. Optima. Mathematical Optimization Society Newsletter, 10-11, 2012.
[42] Y. Nesterov. Lectures on Convex Optimization. Springer, 2nd edition, 2018
[43] C. Park, Park, and E. K. Ryu. Factor-V2 acceleration of accelerated gradient methods. Applied Mathematics and Optimization, 2023.
[44] C. Park and E. K. Ryu. Optimal first-order algorithms as function of inequalities. arXiv:2110. 1035,, 2021.
[45] G. B. Passty. Ergodic convergence Journal of Mathematical Analysis and Applications, 72(2):383-39 1979.
of the sum of monotone operators in Hilbert space.
[46] R. T. Rockafellar. Convex Analysis. Princeton university press, 1970.
[47] R. T. Rockafellar. Conjugate Duality and Optimization. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, 1974.
[48] E. K. Ryu and W. Yin. Large-Scale Convex Optimization. Cambrige University Press, 2022.
12

---

[49] J. Stoer. Duality in nonlinear programming and the minimax theorem, Numerische Mathematik, 5(1):371-379, 1963.
[50] W. Su, S. Boyd, and E. Candes. differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. NeurIPS, 2014.
[51] J. Suh, G. Roh, and E. K. Ryu. Continuous- time analysis of accelerated gradient methods via conservation laws dilated coordinate systems. ICML, 2022.
[52] A. B. Taylor. Convex interpolation and performance estimation of first-order methods for convex optimization. 2017.
[53] A. B. Taylor and F. Bach. Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions. COLT, 2019.
[54] A. B. Taylor, J. M. Hendrickx, and F. Glineur. Exact worst-case performance of first-order methods for composite convex optimization. SIAM Journal on Optimization, 1833)1123-1333, 2017.
[55] A. B. Taylor, J. M. Hendrickx, and F. Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming, 161(1-)):307-355 2017.
[56] A. Wibisono, C. Wilson, and M. I. Jordan. A variational perspective on accelerated methods in optimization. Proceedings of the National Academy of Sciences of the United States of America, 1 113(47):E7351 E7358, 2016.
[57] Wolfe. duality theorem for non-linear programming. Quarterly of applied mathematics, 19(3):239-244 1961.
[58] S. Yamanaka and N. Yamashita. Duality of optimization problems with gauge functions. Optimization, pages 1-31, 2022.
[59] S. Zhao, L. Lessard, and M. Udell. An automatic system to detect equivalence between iterative algorithms. arXiv:2 200.046400.44444,, 2021.
[60] K. Zhou, L. Tian, A. M.-C. So, and Cheng. Practical schemes for finding near-stationary points of convex finite-sums, AISTATS, 2022.
13

---

A Proof of Theorem 1
Reformulate (CI) and (C2) into and V. In this paragraph, we will show
(CI)
U20, 0, (VVI(z))..... VS(EN) E Rd))
and
(C2)
V V20, 0, (VV vf(UN) =R.)
Recall the definition of U and V.
U: UN - uN(((NN)) - f+) L.
1
3o
Σ
(u: u4 u1))
(11)
L 1=0
V: = VN 1 |Vf(uN)1?
(12)
First we calculate UN uN (f(ØN) - f.).
Un uN (f(IN)- - S+)
L
11:00 - 2+112+ +
Σ
(ui= - ui-1) ((xx)) - S- (V[(xx))
- nz) + 2T.
1 [x:))(
1
2
1=0
N-
+
Σ
[(i+11) [(xi) + (V]( +
V5(x)) - V((
uN (f(xN) - fz)
2T.
1=0
N
(0)
L
100
+
Σ
(u: wi-1) (VS(Ez)), -x;)
- [=(()
2
2T
1=0
N-1
1
+
Σ
ui
(
x1+1
+
[ f(+++111
2L
L
u1-1 V f(x))
1
Σ [u - -ル (u-
20
r.
2L
1=
N
+
Σ
[44 u4-1)
(1FF(E)), - x²) + 2L
1=0
N-1
+
Σ
(V(((H))))))) +
ff(z)) V((H+)I))))
2L
1=0
Note that all function value terms are deleted at Therefore,
N
N
U=
1
Σ
(u. - (u--u-iVf(E))
+
Σ (w: u-11 (IVF(E)),20 x.) + 1
(V((E))))
2L
2L
1=0
k=0
N-1
+
Σ
m4
(V x+1) + Vf(x;) vf(a++1)11
2L
1=0
(13)
and
Un uN (f(xx) - ff))
-U+ +
L
2g E. +
N
u4
u;
v f(xa)
2
L
0
14

---

Since (ro 10--) Iz), (2: - I++1) E span (Vf(ro).... vf(xN)), the value of U is independent with
F0, F.. Thus the only term that depends on 20 and v. Y/4 2o 2x + Σ -i V
Next, since 20, can have any value, we can take 2o I. " " V (x;)). Thus it gives the fact
that (C1) is equivalent to U O, (vVf(zo),... Vi(aN) E R
Now caleulate VN=
Vf(vn)]].
VN= 2
Vf(yN)]1
1 f+ f(UN) + IVS [V + to00 (f(vo) - f*)
=00
2L
Us+1 (((5+1))
- + (Vi((+1)).6 M(+1) 2L
[(ss)) V
+ Σ (1++1 - vi) (f(u)) -(NN))))))))))) + ( ve) +
-v))
1
VS(n)) - V((UN))
V [yNN)1
2L
2I
N-1
(e) vo
(yNN))
+
Σ
1++1 ((VS(U4H).)) - +
VV(x) - V
2T.
2T.
1=0
N
Σ
(01+1-0)
(1VS())) vi) -
1 -V/W) v((ww))))
1
| [
2L
2L
Note that all function values are deleted at (o). By the calculation result,
N-1
00
V
[1NN]1
+
Σ
1i+1 (VI((Ct)))) - y6+1) + 2L VV(v)) - VS(H+D))))
2L
=
(1i+1 - vi)
(VS())) vi) + 2T. [V([))) - </(ww))²)
1
II (2NN)
2T
(14)
(C2) is equivalent to V20, 0, (VVS(1)),.... (((()))),,,,,))) E RR]] ]. To establish Theorem 1, demon-
strating
[v20, 0, U 0, (VVf(zo)..... (e((E)))..,,V((xx) (((x))RR) +
Vf(NN) E Rd)
(15)
would suffice.
Transforming U and V into trace.
Define
92 = [f(o fxxx)] e [dx(N+1)
9y: [V(O)) [f(NN]] E (N+1))
In this paragraph, we convert the of (11) and the Vf (12) into the trace of symmetric matrices. The key idea is: For each (a, b) term where a,b E span(V[(zn) I.a, b = b for some b R(N+1)x1 Then
V((N))), we can write
(a, b) = (g b) = =b glg.a- Tr (bT (l Tr (ab glg.) Tr (g.ablg.) (16) Also note that (Io Iz), (x: x E spant [ fxa)..... vf(n)) and (y: yN), (y l1+1) span ( (yo))..........................) .... Vf(yN)]. By using this technique, we observe that there exists
S S(H,u) u), T(H* v) that satisfy
(11) Tr
(12) = Tr ((11 ,u)9,)
15

---

vector which (i + 1)-th component 1, e-1 ex+1 and define H. as a unit
From now, we specifically calculate S(H, u) and T(H*,e) Denote fe. E (N++))
0
0
H = H
E R(N+1)x(N+1)
0]
Then, by the definition of Oz and H. we have
1
e V((())))
OSiSN,
I Dr
TTe =0,
(17)
L 1211"0n cit1 = L
Σ
Cj = L
Σ
his Vf(xz) =2 I++1 0 1.
(18)
j=U
j=0
Therefore, we can express (11) with H. {ur J In and { using (17) and (18) as
(11)
N
N
Σ
(u - u4 11)
+
(u: ui-1)
(v - xz,) + - [V(())))
2L
2L
1=0
k=0
N
1 [Vf(x;)
(Vf(=++1), -1+11
2L
1=0
N
N
(ares i 1 + .......)))
+o)) + 21
Σ
(us - 1)gaa
+
Σ 1=0
[n u4-1)
2L
1=0
N-1
Σ
7 e )+
1
+ -
1
U4
1=
Using (16) induces (11) Tr (g u)g3) where
u(H,u)
N
(u, u1-1)es
Σ (u: u, u
2L
N
N
+
HTT
Σ 1=0
ui + .... t.. - e(t1)"
+
Σ
ui(e:
e ... e;) H.
2L
2L
Σ Us ((e: c.41)e + te(e
-
2L
(19)
Similarly, we calculate (12). Define HA as a anti-transpose matrix of H:
0
0
E ((N+1)
HA
0
Then, by the definition of gy and HA, have
1
gye, Vf(v.) 0SiSN, ; 9 (HA)T c++1 = 1 Σ
9y (H1)) eu =0,
(20)
1
higgy0. Σ
his vf(1,) = V: U4+1 0sisN-1. (21)
1=0
1=0
16

---

Therefore, we can express (12) with H ff 9 and fer using (20) and (21) as (12)
N-1
00
+
Σ vi+1 ((VS(MAA)) - 31+1) + 2L
[Vf(())) V
2L
N-1
(0/41 v1) ( (V UN -v) + [Vf()) - vf(UN)11
+
2L
==
1 11g + Σ uit1 ((ogeett
1 1ll -+till
I I (HA)) eit1 2
2L
1=0
N-1
Σ
(Ut+1 uz)
uz)
s0c 1 1 ))() (HA) (cit1 + +.....oN)) owl)
1 Ilqu(c ex)le)
2L
We can write (12) Tr (gg THH,, ,0)55) where
T(H A
v)
N
1
Us (( - -NN + (ei-1- -x)(e-
tve
2T. eveey
2T
21.
P=U
N
1
Σ U/ ((HA)) (c:+........ (c. [w]( - + (c; -... .... (o...
2L
N
1
Σ
-N) 2uN I
1
eNe
2L
UN-i
2L
N
1
Σ
+ (e: -e--)( + .................... exx) ((()) + +... (..+ - -e--))
2T
uN-i
L
(22)
Finding auxiliary matrix M(u) that gives the relation between S(H, u) and T(HA, can show that there exists an invertible (u) E RRN+1)x(N+1) such that
We
S(H, u) = (u)
(23)
If we assume the above equation,
Tr SH, m)g!) = Tr (9h ,0)5]) with gy = 9z.(( Since M(u) is invertible,
(24)
(glg E Rxx(N++)) = (
(25)
Also, note that
U 12 (Vf(zo)...... (f(EE)
[Ir( 20
Agz E =x)(++1)
and
1 0 VVf(8)..... ... v((Nn] By combining (24) and (25), we obtain
Tr (g, T (HH,)))))))) 20 0 Agg Rdx(o+2)).
Tr S(H, w)g!)=
yg, [
Tr (g, u)g
2 0
Ag. d
9, = M(u)(
Tr S(H u)gt) 2 0
Agg d
To sum up, we obtain (15)
U VVI(x))..... V[(x)))))))
4> [V20 VV ..., V](uN)] (V/(,))...,////N))
which concludes the proof.
17

---

Explicit form of (u) and justification of (23).
Explicit form of M(u) is
0
0
UN
0
UN
UN UN
M
UN-2
UN-1
UN-2
UN uN-1 :
E R (N+++))(N+D),
(26)
UN 2 UN 3
UN-1 UN-2 uN uN-1
Now, express M(u) Σ my(u)eee] u)
E OSIJSN
sire,e), and T(H ,0)
OSIJSN
Σ
A. Calculating (T ,U)M(u) gives
USEJSN
(
Σ mysw)as
Σ
Σ my(u))c
hi
Σbi lis Σ
max(ueex
Emalw)ee
f
Σ
Thus is enough to show that Σ S.jC,J] and Σ (u) are the same under the basis transfor- mation (u) = Σ mux(u)e. From here, we briefly write f, instead [u), and f-1 = 0. Note that wi Bi+1) = (fN-i fN- sis by definition of M(u). Therefore, we have
1 L H Σ ui(es +... +.... ee)(e: - -.+1)
1
HT
co + ..................... (aa((f---fN-e-))
L
i=0
1
71
eeff N-
L
i=0
Therefore, we can rewrite (19) as follows:
S(H,u)=
1
fNf
HT
Σ
+
Σ
TT
2L
2L
2L
1=0
N
+
(fN- - IN-
+
3r|
UN
eNe
2T.
2I.
(=0
fN
Σ
f N-i
+
hi
(27)
2L
N
2L
2L
inj
(
A
+
(fN -
fN- Cov-i-fy---ll
-aai-ff---i fN-
cNecy
2L
2L
==0
D
C1
Similarly, by using
-N eN-
(f: f(-1) (f, - ff.
UN-i
18

---

we can rewrite (22) as follows:
MT v)M(u)
1
CNN1141 - eN-i)(fi-1 - fv) + (ft-1 fe)(eN-st1-
- eN-1)
2L
1=0
N
N
fuf0
fNfN +
(
T
Σ
f.e.
+
Σ
CN
of.
H
2u
2L
2L
2L
1=0
1=
fuco +
hN-
hN-
2uN L
2L
2
f,j
D2
B2
1 (eof) + fxel)
(eN-141 -N- + f- (en eN-
fNfN.
2L
2L
2L
A
C2
(28)
For the final step, we compare (28) and (27) term-by-term, by showing X X2 for X
A, B, C, D.
A A2 comes directly.
B B₂ comes from changing the summation index + N - and j + N - j.
C C2 comes from the expansion of summation.
D. D2 comes from uNêN.
Therefore,
S(H, v) = (T) M
which concludes the proof.
Remark 1. We can interpret M as a basis transformation, where
uNeN = for uu(e; - e.41) fN-: - fN---11 0,0, N 1.
(29)
2. To clarify, the quantifier [VVS(z)),.... vf(an) in (CI) means (f(a)).....
Remark
fx can be any arbitrary vectors in Rd. This is different from (V)(z)) V ( be gradient of some f: RRd - RJ. The same is true for (C2).
B Omitted calculation of Section 2
B.1 Calculation of H matrices
OGM and OGM-G.
[26, Proposition 3] provides recursive formula for (OGM) follows:
4
0, k 2 2
Ut+1
be41.1
8 (h 1)
(30)
1 +
29
k.
Ox
If > i,
0: 20 -
hx+1,k
0k
0/ hu,s
0
k
1
20,
hx413
h141,-11= =
II
0k+1
O.+1
0
0:+1
1=++2
19

---

Thus HOGM can be calculated as
i> k
1 +
20a-1
= k
Ho + +,,
8k41
01-1
20,-1
11+1
28
[mi+1
Recursive formula [29] of (OGM-G) as following:
- 1
hs+11i+1
= 0,
By
hx+1,1
-
(ha+1,i-1)
-11
k
(31)
NN Ell
2
20
If >>
ON 1220 k-1
11+1
-Nt1
k++
ON
N N-1-1 01
NN-i-1
ON-
II
0 1
28 k-1
hK+1,i
hx+1,411
14t16-11
ON
01+1
81+1
ON
N -+1
1m N
Thus HOOM-U can be calculated as
0
i> k
1 +
20 N -
k
HOGM-O(k + 1)
UN
N 1-
A--1
28N-R-1-1
< k
1=N-k 0111
ON K
which gives HOCM = HdGM-
Gradient Descent. For (GD), 11,+1,4+1) = = delta. Therefore, HGD = HÓ.
h00411441 where و.g is the Kronecker
Recall 7 N(N+1) We obtain the recursive formula of the H matrix
OBL-F, and OBL-G, of (OBL-F,).
K+3 h4.s
k O,...,,--1 - = 0, N 2,
k
1 +
2k
k: O,...,
i= k
k+3
k
(k2,k-1-1) 1
h: ,,... N N-2,i=1 -
h1414
k+3
(32)
+ 7+1
N-1
k N 1,1=
(hN-1N-2-1)
- 1,,- - -2
2(y+1)
1N-
k N - 1,i -3
2
By using the above formula, we obtain
2k
h = 0. N 2, i i= k
k+3
k: = 0, N - 2, i 0, O....,k
HOBL.1, (R: + 1,1+
(R+ (++1)++2)443)
+ N-1
k = N 1, i= -1
7+
(6+1)(+2)
k N i- O,.... N
G+NN(N+1
20

---

Similarly, we achieve the following recursive formula of the H matrix of (OBL-G,).
N k+2 hAyi
N k-1
k = 1, N - 1, = O..... --2
2(N k-1
h ..... . 1, i-i
hat1i
N N-k+2
(33)
N k+2 (1
N 1-
h I,....,N
1
+ N-1
k = 0, i=
7+1
By using the above recursive formula, we obtain
N-1
k = 0, i i=0 1,
(N- N COINNN--I---- -
N 1,
HOBL-G, (k + 1,
2
k = 1,
N 1, k
N-k+2
2 2 IIN---IJ(NN&
k
N- 1, 1,..., k
(N (N=1)(--+1)
Thus HOBL.F, HOBL-G,
B.2 Calculation of energy functions
Calculation of U and with H matrix In this paragraph, we calculate U and V. Recall (13)
and (14).
First, we put Tk+1 - Fk = - Σ 1 (1(s)) (11). We have
U
1
Σ [u: - uz
ΣE (u: u-11) (V - 21)
1 1 [V
2L
--1
Σ
(V I(+1) + vf(2,) ff(+++1)113
+
2L
i=0
N
i-1 + U u,-1 (TTF(e))
h141, Vf(o)) + +1108(=)11))
Σ - -1n----)f(a
+
ΣΣ
2L
1=0 ==
--1 Ui
(V/(CCH))) Σ
hitts VI(z))
+ - V[(++1))
1=0
By arranging, we obtain
U= Σ
$ij
vf(a,)
L
0SiSiSN
where
(uN 1N ) jN
i i N
{w; u;-1)2 + ui
j = i, ,,.., N
86.
Whbis11 - u:-1 - (u: ui (1;-) - 2;-2)
j=i-1
i-1
(nn - 11-1)
Σ
h411 + wiiiiis - (w; - u--)((u; - uz-1)
j == 0, 0,..,ii-3 2-2
(34)
21

---

Recall that we defined u-1 = O. Next, put yk+1 - Uk = -
Σ
h6t1. to (12). We have
=
V = VN
[
2L
N-1
00
f(NN)) 122 + Σ
vi+1 (V -v+1) +
1
Vf(u)) V
2L
2L
i=0
N-1
1 VVl()) v((eN)I))
+
Σ
(0/+1 - uv)
(VF())) - -i) +
[V(N)))1
2L
2L
=
N-1
((rreun)) Σ
UD 1
1
V f(UN))1
+
Σ
vit1
h441 V
+
2L
2L
==0
N-1
((vr0a))
N-1
+ Σ (0411 - us)
Σ
M )
VS())) V((ww)1)))
-
+ 2T
I
1=1
j=0
By arranging, we obtain
V
Σ 0SISISN
4.
L
where
N-1
+
11 2
(11 vo)
Σ
h4110
i = 0, =
1=0
2
+
2
(1i+1
U1
h141,
i == 1...., N N-1,5 1,
10-1
+
Σ 1111-
i N. =i
2
N-1
N-1 Σ
0.h4,1-1 - U/- - (11+1 - -%
Σ h1415--1 - (01--00 16--00 12-1)
h141
1...., . - 1, j
UNhNNN-1 - UN - (UN -1
N.j = =i-1
N-1
N-1
0,/ii - (1i+1 vi)
Σ
1441. - (15+1
Σ
h441
i = 2.... N - -,, = O,... i-
1=
1
uNhNJ (1j+1 Ug))
i = N. = O....,N
N - 2
(35)
Now we calculate { and (tay} for (OGM-G) (OBL-G) and (GD), (GD)
B.2.1 Calculation of energy function of (OGM) and (OGM-G)
We will show S.y = and t.j = 0 for all i.j. By the definition of {ut and {0, J.N.
u4 - u,-1 = 28 228?_ 20;
0
uN UN-1 = 0% -20% = ON.
Therefore, have
1 (uN - 12 + 2
uN = 0N + fly =0
j=i,i= i- N i i= ON.,
$1,5
(wu 14:4 )2 + u; -0; + 0; = 0
22

---

Now we claim that sty = 0 when # i. In the case that = j + 1, we have
14-1
(2; u4- (1 (ui-1 22-2) Mi-1 - (U; - ui (ui-) - 22
20,
1
ui
+ 1
20
10 +
1)
20 40,0;-1 0 0siSN- N -1
8,
20N-1-1
+
26 2 20N i= N
8N
0.
We show Siz = 0 for j # with induction on i, i.e., proving
8i = (w: ui-1)
bitts + us uiis (ui ui () 45-1) =0, j= 0, -.....,f --2
(36)
First we prove (36) for i + 2.
(uz+2 - -(++1) (hz+1,) + h5) + U3+143+25 - (1442 - -3-1)
U1+2h3422 (1)+)=(;+=))++1 +
(uy-2 U141)(ug 1z-1)
128+2215+1 +0 -
- -48++20 0
ON h NN 20 j=N-1 N-2 -2
=0.
Next, assume (36) for =
When i = i0 do++l 1,
10
(ui++1 U1oo
h111 + uig M1ot (uig+1 - vio)(uj u--1)
1 Σ
=(Uo++1 -Woo)
h1t1f + heot1s + uichso+11 - (Uio+1 - Uio 2)-1)
j-j
(Ui, U 1 - Ug u1-11
Usg M + hio+ls ) + uio Mithi
=(ui++1 WWoo
Uio Uig-1
- -Wuio+1 - Uso (2, - -ú--1
Uio -1 (Uto+1 Usa)
Mig+thio+1..
Migs
nio
Uio-1
16
202
10+1
hiot1.
20.a
hiod
0 10 S N -
20
0 hiotii
hiod
i0 N -
24
where the second equality comes from the induction hypothesis, and the third equality comes from (30). In sum, we proved 8ij = 0 for every and j. which implies U = O.
Next, we will claim that tip = 0 for all i, Firstly, explicit formula of HoOM + 1, 1) first. When & > i,
Ho + 1,1+1) = 0 N ON- 1
ON-1-1 - 120- -1
- k+1
ON-s
NN
0/ - ON k
02
0N-
0 N-
ON N0--
i-1
N b0 -k+1
0N-K+ ON -+2
0N-i-10N- 10
ON-K
2 Nー k-
02y
0 N-i-2 1-2 20 1
On 10 N k+1 ON - ON- k+2
O ON
0 ON
82 8y (20 28N-kk1 1)
N - ON-i
23

---

To calculate (tr,s) is enough to deal with the sum Σ ht+1,j which can be expressed as
0x+1
= 0, j = i
ON-i
= ,,... N - 1, j =i
(37)
I,...,, N - 1, j O,..., -1
ON ON- B3
By inserting (37) in (35), [Ba = 0, Vi, is obtained, which implies V = 0. (37) and (35) are also stated in [29, Lemma 6.1].
B.2.2 Calculation of energy function of (OBL-FF) and (OBL-G,
First we calculate {si)} for (OBL-F)). Recall u2 (++1((++) for S S N - and uN = +
2
where 7 (N 1)/2. When
(UN UN -N- + JuN i=N
84,
(1: 1 2 uu; 0 0SiSN-1
UN WN
i= N
1)²²
(++1)(+2)
0 OSiSN-
2
Now claim that Ssy when In the case j = = - 1, we have
8 u. - 24-1 (ui Ui 1 (1:-1 44-2) (i+ ((+1)(+2) hi,i-1 1(++1) (i + 1)i 0 0siSN= N-1
(T2 + 7) WN.N-1 - N(N+1)
2 ?N i=N
0.
We show 8iz = 0 for j A with induction on i, i.e. proving
Si.j (w: Ui
h4415 1i-iiis (u: u4-1) ug-1) =0 j 0, ... -2
(38)
(38) holds when j + since
(uj+2 -(+1))(+))))))) (hi+1s hy- + U141 - (uz42 (0412-u)11(u4, - -1-1)
= - -1t1)/ihts + 2222
(-----u-1------- uy-1)
(i +33)/441s + (+ 23-2 - -(+3)( 0SiSN-3 -
7 (n2 + +7) hN.N-2 == N-2
0.
24

---

Assume (38) for i ig. For i i0 + 1.
30
(Uig+1 - Wio
h+1 + Uig Aio - (Uio+1 - uio)(uz - 2 u--1)
l=1
10-1
=(ui++1 Uio
h141, hio
uip Niot1.3 (Uio+ Win)(1j Uj ug-1)
Wig phoood + heot1.s) ) + uio Mit (Nip Mig 11) Uj-1)
-MMi++1 -Wto
Uio Uip-1
-(Niot1
Uno (2) - 11--1)
Vio (11i+1 Uso) hios
-1ig+1 +1g
U/o Uig-1
(to (Ho+2)(4o+3)
hig+15
iollo ()660+1((6++2)
hiod 0 10 S N
2 (72 + +7)
2(+o+1)
(N-1)N hN 1 1N- 40 N -1
hN.
2N
0.
Next, calculate [ty) for (OBL-G,). We need to deal with the sum expressed as
1441 which can be
1 (N+
i 0, j =0 1, I....., i= j + I....,N -
1(++1)
N-1
(N- -AN------------ -N---N-
NN 1, =0
h411
16++))((++)
(N (N (N
1,
1.
N -
l=1
2 -) (V
i I,...,N N
By combining uo 7-ng 2/ (N-1+)[(N-++) for sis N and (35), we obtain
i N, j = N i = 0, j =1
Ni 2N(N+1)
2
00
N(N+1J
i N, = 0
fij
i L....,N 1, j =
N, j I....,N
[N 30-2)[8 - 222)
otherwise
N, j N ..., N 1, j
9:-1
U/+1 + U2
N, j = O....,N
otherwise
Therefore,
N-1 1
= Σ
to
(VF())
20
V [f(y))
Ut+1 1
(f() vf(un)1
L
2L
2L
OSiSISN
1=0
25

---

B.2.3 Calculation of energy function of GD
We calculate [ty first. Recall that {u) ) to (35), and making (ty) symmetric gives us
N+
and hi+1, òs,k
2N+1
(2N+1](N -i+1j....
i= j, i=
V;
j, Sisss-
by
UN
i=j
(Umin(t.5) (min((,))+1)
{
2
We can verify that the matrix fossosS is diagonally dominant: tu = ب tyyl Therefore, E fe (V)(w)) vf(s))) 2 0 for any {V)()))< This proof is essentially the same as the
OSiJEN-1
proof in [29], but we repeat here with our notation for the sake of completeness.
Next, we prove that (GD) with and {ui = -..... by showing more general statement:
(2N+D(++1) 2N-1
...
2N + +1) satisfies (CI),
(GD) and Ju = (.... (2Nh + 1)(2 +
2Nh 2Nh+1 +1 satisfies (CI)
(39)
2N -i
Note that (39) gives
2N + ()([(N)) M) SNN 1 4-1
- 100 x=1
(40)
Later the proof Corollary 2, we will utilize the equation (39). The result (39) is proved [19, Theorem 3.1], and give the proof outline here.
In order demonstrate (39), we will directly expand the expression Uy UN (f(IN) f*). instead of employing U as intermediary step. Define {u()
(2N+1)(++1)
2N-1 ....,, 2N + 1). Then
UN uN (f(#N) - f*) I
Tr (gTgS)
where g = [Vo()))).... [f(EN))[(Eo x²)] Rdx((N2) and SN+ is given by
S
A
5
A
1
2
(na M1 uol-.. JUN uN-1)
2N
(hS0 (1 - h))1))
2N+1
N-1
So =
Σ
1
(cit1e] + tesef11 + (e: - - =
2
1=0
N
-
4/11
(ei(eo +... +...0++.......)) (co .... ei ee- teee))
1=0
S = Σ
N-1
u
(e: -
+
Σ 1=0
u r/
e.e.
2
2
==0
Now we will show S > 0 to obtain [NN - uN (f(x)) 1*) 2 0, Vg) which is (CI). By using Sylvester's Criterion, So > 0 follows. S₁ follows from the fact that S₁ expressed by the sum of positive
matrices =zT. Since the convex sum of two positive semi semi-definite matrices is also positive semi-definite, S' h.S (1 h)S1 0.
Next, we argue that det S = 0. Indeed, take r = (1,.... .....-(22 (2Nh + 1))J to show ST = 0, which gives det S 0. Note that the determinant of 5 can also be expressed by
dct(S)= = { XT (T > det(5").
(41)
We have shown that S' > 0, (41) implies AT - 0, which the Schur complement of the matrix S. By well-known lemma the Schur complement, we conclude S ž 0.
26

---

B.3
Omitted proof in Section 2.5
B.3.1
Omitted calculation of Corollary
Here, we will give the general formulation of H-dual FSFOM of x + 7 (x - =kk)
Ik+1 Th + 3x (
k == NN,,
(42)
Proposition 1. The H-dual of (42) is
Mk+1 yk - 8 (v
y + N/ (ut - yk)
k= 0, OV..,
(43)
where
8 NN AN-x(3N-1-2 1N-1-k)
BN-k + -N-
7/6 7N - (3N- + -1
Ax- + -NN-
for 1: = 0, .....,N N
and (BN, (N) is any value that BN + + 0.
Proof.
The H matrix (hessSss satisfies
1 + Bk 7
i i= k, k 0, N -
hp41,1
Bx (hR.s
1)
i= k 1, k N.... -11
i= k - 2, k = 2 N.....N --1
Therefore,
k II -=++1
he+1,
3y
(3s + 7: + 5x,,)
where d is a Kronecker Delta function. Similarly, H matrix of (43) Josscksicss satisfies
A:
II j=++1
By
(8, + 7/6 + 8k.i)
9k+1.
A: II j=++
Ny NN- (BN + +7N-1-1)
(SN-1- + 7N-1-5 8x.i)
9N-j + 7N-j
II -=++1
BN-s
+ + -N---IN---)-
Thus Ik+1.1 = IN-1-N-1-k
Now we derive the H-dual of (6) by applying Proposition 1. Note that
Bk (Tr 14)6441
(12 T2)(x+1 == O....,
+xT+11
txTx+1
Next, define 3N and NN same form of (Bi, N-1 with any 14+1 0. Note that
(1 (x)
(0t1(te -1)
Bx +
txTx+1
Tht1
By applying the formula at Proposition 1, we obtain
3 (TN-k IN d- (fN-
Tx-k
(TN-A - tN (NN)(tNN--11
Ty (tN--
ty tN
TN Tv-i(tN- -1)
T TtN-
and
%/2 (f2 Ty- IN-elth 1-1-1)
(Py- - -TN=)((N---1-11
Tx
Ky IN-K
Tv-
'eere, note that FSFOM (43) is independent with the any choice of AN, NN since yı = yo + (86 + 76) (vo v0) yo (3x-1 -1) (vo vo).
27

---

B.3.2 Proof of Corollary
First, recall (39) when 0 < S 1:
(2N4 + 1) +
2N - ..... 2N + satisfies (CD)
(GD) and {u, )
Additionally, observe that the H matrix of (GD) is diag (h...., h), which gives the fact that the H-dual (GD) is itself.
Next, use Theorem to obtain
:...) 2Nh +1 (2N4 1)(N -i+1) 1)",..
N +
(GD) with 0 < h s 1 and {u:)
satisfies (C2)
(44)
By using the same argument with (5), (44) gives
1
1
1
[f( s VN s Vo 2Nh (f(3)) f.) + 2Nh [NN. v.1
(f(y)) f.).
2L
2Nh
(45)
In addition, we can achieve the convergence rate the gradient norm under the initial condition of 220
x. 2
L 100 2Nh -1 (f(EN) f.) 5 (2Nh + 1)2
V Vf(222)1
=.112
2L
and
L x=11²
2L [/
2(N + 1)h+1 (f(mN) f+) (2(N + 1)h + (2Nh 1)
11:00
The first inequality comes from (45) and the second inequality comes from (40).
B.3.3
Proof A.-optimality of (OGM-G) and (OBL-G,)
Definition of AA oopttiaal FSFOM. For the given incquality sets C. A' A''A''oppiin oppttti FSFOM with respect to PI] is defined as FSFOM which H matrix is the solution of following minimax problem:
minimize maximize f(xN) - HERE
subject.to.
[vo ..... UN are generated by FSFOM with the matrix H] VI E C, satisfies []
(46)
|00 - 22 < R²
Similarly, A optoiiaa FSFOM with respect to [C, (P2)) is specified with its H matrix, which is the solution of the following minimax problem:
1
minimize maximize
[V(Nn))
HER
2L
subject.to.
I.o...., yn are generated by FSFOM with the matrix H] VV E L, f satisfies
(47)
f(v)) - f. < LRR
Here F. N is the set of lower triangular matrices. Next we denote the inner maximize problem of (46) and (47) Pi (C, H, R) and P2 H, R). respectively. For a more rigorous definition of A -pttmaa FSFOM, refer [44].
Remark. We discuss the minimax problems (46) and (47) and their interpretation. Specifically,
we consider the meaning the maximization problem these minimax problems, which can be thought of as calculating the worst-case performance for fixed FSFOM with H. In other words, the minimization problem (46) and (47) can be interpreted as determining the optimal value of that minimizes the worst-case performance.
28

---

Prior works. The prior works for ootpiiialiyt are summarized as follows. Consider the following sets of inequalities.
C. = (1 U1 a1 (
[(((m)) (( + (V[(244), x1+1) +
2T. [V(x))) V/(44)) N-1 1=0
U U u U[UN, +1}
1
[[;[);]]| i=o'
21
{((m) 2 f(1++1) + (V - vo+1) + Р
1
[Vf[(t V N-1
N-1 i==
(( 2 f(v)) + (VI(m)) - ma) + 2L [Vf(y,) V](UN))1
1=
U(S(UN)2 2 ʃ. 2T.
1
Lo Ul U [uN, vo1
2T. [v:)) V)(NN)] N-1
1
i U (
+]
1
V
[[(N))]
2T.
=(S(w)) f(0++1) (Vf(1+1)) vo+1)
1
[V(())) -
N-1
Jimo
21
U(S(UN) ((v)) (VI())) mi) } U{ 2 2.).
L U1 U [I,, #:]
1
[V[(x))]12
2L
i=0
=(f(e)) 2 f(a+t) + (Vf(2.))) 1),;; lzti) +
Vf(x;;) ((( [
2L
UR 2 f(x)) (Vf(z,,, x. 2z) } |==o'
and
Lexac
(OGM) is A'-optimal with respect to [Cr: (P1)) [26). Furthermore, (OGM) also A'-optimal under [Fexect: (P1)) which implies that (OGM) is the exact optimal FSFOM with respect to (P1). In addition, the A"-optimality of (OGM-G) with respect to [Lg, (P2)) was presented as a conjecture in [29], (OBL-F,) is ootomia with respect to [Cp, (P1)] [44, Theorem 4], and the At-optimality of (OBL-G,) with respect to [Lor, (P2) was presented as conjecture [44, Conjecture 8).
In the remaining parts, give the proof of the following two theorems.
Theorem 4. (OGM-G) A opptimal with respect to [Co, (P2)).
Theorem 5. (OBL-G,) is A opttiall with respect to [Cor, (P2)).
'Originally, the inequality set suggested that (OBL-G,) would A"-optimal is which (f(xx) 2 f.) is replaced with (f(w)) 2 f- a [[[(())) in Le.
29

---

Proof of A -optimaaly of (OGM-G) We provide an alternative formulation of P2(Co, R) by using the methodology called PEP [19, 52]
maximize
[/(N))
2T
subject to
f(v++1) - f(v)) + (Vf(yi+1). - yit1) + [V())) - vf((++1)l1 00 i= .N...,N--
-
2L
1
f(y)) f(UN) + (Vf())) UN - vi)
V Vf v 00, i= 0,... ... N
2L
f+ 21 |V((v)]11 f(uN)
f(80) - f. - LR²
2
V4+1 V/- I
Σ
h441a Vf(uj) i= -1
1=0
(48)
Next, define F, G, (c:) and {x:
(Vf())), vf(00))
(Vf()o)
(Vi(20). v
G
SN++1
(V](N)), Vf(NN)
(Vf(w)): vs((n))
VI(UN)
((10) - S.
f(y1) - fx
F
R(N+I)XI
f(yN) f.)
E NBN+1 is unit vector which (i + 1)-th component is 1, and
yo =- O, Yi+1 = yi T.
Σ
hittge
i= O=O....NND
1=0
By using the definition of F, G. {e, N and (yrlino. P2(Co, H, R) can be converted into
1
minimize F,G20
2L (GeNe)))
subject to
F(c:41 e,)T Tr (GA,) 50, i= 0=0,.... O -
F(e, eN) + Tr (GB)) <0,
i= 0, 0....,N-1
(49)
FFey 1 Tr (Geve 50
2
FeJ LR <0
2
where
1 (y: - T++1) +
1
A;
2 (y: -141)e4 + (e: e:41) e
2L
1
B; cy - y
2 (yN -yje + 2L (c. eN) (x) eN)
Moreover, under the condition d + 2, we can take the Cholesky factorization of G recover the triplet {Jt, (B:), ff Thus (48) and (49) are equivalent. The next step is calculating the Lagrangian of (49) and deriving the Lagrangian dual problem of In [54], they argued about the strong duality of (49).
'Cholesky factorization is unique if G > 0 but it may be not unique if G > 0. In this case, we choose one representation of Cholesky factorization.
30

---

Fact 1. Assume h4-1.5 # 0 for SiSN -1. 1. Then the strong duality holds between (48) and (49).
Denote the dual variables of each constraints as (6:) (A:) 8x and т. Then Lagrangian becomes
TL R²
C(,,A,,,FFC = F X + (G T
2
where
N-1
N-1
X
8,(1+11 - - +
Σ
A - eN) ÖNeN + Tep.
i=0
N-1
N-1
ON
1
T =
8 +
Σ A + 2
CNcy
2 exely.
2=0
<=0
[ = 0 and - 0] is false, we can choose F and G that makes the value of Lagrangian to be
0C. Thus the convex dual problem of (49) is
maximize 6, subject to
1 122
maximize minimize [6, T,, = 6,
X = 0, 0
(50)
F,G
8
\ 72 0
For the constraint X = 0, A = 6, - - for <is N 1. ōn and -60 + Ao + 6N = 0. By
substituting U1+1 for I i is N and 0o 8N. (50) becomes
maximize 6,A.T
21 R2
maximize minimize L(O,A,T,F,CE F.G
subject to
T ヒ 0
(51)
0
S Uo S ... UN
Therefore if strong duality holds, P2(Co, H, R) becomes
L
minimize uo.....
R²
2
(52)
subject.to. T 05 0 UN.
We can apply similar argument for Pf H, R). To begin with, define (f.),- as a unit vector
of length N 2 which (i + commpnent is 1. Additionally, define {x (C,) N- and (D.) as follows:
Nu = f1, Xi+1 = X;
Σ j=0
M4irff i= o=O...,NN-
L
+ 1 (f: f(+1) (f. - f.41)
(53)
C = - fh-
(xi
x
(xi
Xi+ x
2T.
1 - [x]
1
D Dj:=
ス x + - f.P.
2L
Then, if the strong duality holds, the problem
maximize /
f(xx)- - f-
subject.to.
[z....., UN are generated by FSFO with the matrix H]
(54)
|Vl E Lr, I satisfies
| 2.1² 11 < R²
equivalent
L Ii²
maximize Mo.....aN
2un
(55)
subject.to. S z 0, 0 < ug - - UN,
31

---

where
N-1
N
L
f-
+
u
C,C,
Σ
[4
u1-1 D
2
==
1=0
By using Schur's Complement,
+ 0
where
N-1 S' = Σ
N
u.C, C, + Σ
[n - u, 1,
Σ
[1 - uz 1)-
Σ 11 - u
u
2L
1=0
i=0
1=0
Hence (55) is equivalent to
L R²
maximize
uo...
2uN
(56)
subject.to. S' ž 0, 0 5 un S .... UN.
Now will prove the following proposition.
Proposition 2. Consider a matrix H (hro)osj<isn and HA, If 14 + f 0 <is N -1 and treating the solution infeasible maximize problem as 0, the optimal values of PC H, R) and (C H R) are same.
Proof. To simplify the analysis, we can consider {f.) J as length + unit vector, as all terms with f-1 can be eliminated by using S' instead of S. With this simplification, both S' and T belong SN+1
Next, let 0 < uo S 01 S ... S un and 0 = wx- for 0 < < N, noting that 0 < t0 S
< UN. It is important to observe that S' and T can be expressed in terms of S (H. u) and T ((HA, v), respectively. Furthermore, in the proof of Theorem (A), we proved that S( H, u) M( ,v)M(u) for some invertible M(u). Thus,
S(H,)) + T(H ,0) 0
Therefore, we obtain
(ag....., aN) E ((24....., 00 un S u..
(57)
and only if
1 ON
1
E
ux)
T
0, 0 < S ... S vN)
(58)
For the next step, we claim that the optimal value of (56) and
L
maximize Mo....
R²
2uN
(59)
subject.to. S' >
< un < uN
same, i.c., consider the case when all u; are positive enough. To prove that, assume there exists 0 = uo = ... 0 < Uk-1 < ... S uy and H that satisfy S' > 0. Next, observe that the frfß component of S' is but f441f] component of S is 144144414 # 0. which makes S impossible.
When the optimal value of (52) is 0, it implies {(o..... uN T = 0, 0 up S uw is an empty set. Therefore, {(uo..... ux)] S' 2 0, O < ug S S un is also empty set. Since (59)
and (56) have the same optimal value, the optimal value of (56) is 0.
If the optimal value (52) is positive, the optimal values of (56) and (52) are the same since (57) and (58) are equivalent.
32

---

Proof of Theorem 4. HOGM is the solution of (46) since (OGM) is A with respect to Lp and (P1). Additionally, if
(46) maximize Pi (Cp, H1, R) H.
(60)
holds, HOGM is the solution to the following problem due the strong duality,
L
maximize maximize H.ha 1,:70 Ug...,NN
R²
2u
(61)
subject.to. S = 0, 0 S S ... S
Applying Proposition and using the fact HOOMa HÓOM provides that HOCM is the solution of
maximize minimize vo R H, UN
(62)
subject.to. T > 0 5 00
UN.
Finally, if
(47) maximize P P1 H,
(63)
11,7
holds, the optimal solution of (47) is the HoUMG. which proves the A" optoimallyyy of (OGM-G) with respect to Lo and (P2). The proof (60) and (63) uses the continuity argument with and please refer [44, Claim 4].
Remark of Proof of A"-opiimality of (OGM-G). We proved that (OGM-G) is opttiial if we use the subset of cocoercivity inequalities. Therefore, it is still open whether (OGM-G) is optimal or among the L-smooth convex function's gradient minimization method.
Proof of -pttiiaalyyy of (OBL-G,). We provide the proof that the H matrix of (OBL-G,) is the solution of
minimize P2(Ca H, R)
(64)
HER
To begin with, bring to mind the A'-optimality of (OBL-F,): (OBL-FF)) is A' A'-otiiaal with respect to the [LF, PI], i.e. the matrix (OBL-F,) is the solution
minimize Pi R). HER HERNOY
(65)
To prove the A optiimallyyy of (OBL-G,), the A--optimality of (OBL-F,).
Under the assumption of strong duality, we could change Pi H, R) into the following SDP:
L
maximize uO....uN
R²
2u
(66)
subject.to. S 2 0, 0 < un S ... S UN
where
N-1 Σ
L S
L
u, C,C, + Eu, u-1)
D.
f.ft
2
2L
Here we used the same notation with (53). Each 27. f.f. term is subtracted from the original S since we consider the inequality [_,,..] - 2t [[)x)) instead of [r,, 2I,] for Lp.. Moreover, (66) is equivalent to
L R²
maximize
uO.....N
2u
(67)
subject.to. S Z 0, 0 < up < ... $ uN
33

---

where
S
u. C
Σ u4
wi-1)
(D.
D.
1 2L
1
fift]
1
Σ
Σ
(w:
Ui )s3 )
2L
Similarly, under the assumption of strong duality, P2(Co H, R) is equivalent to
VoL Ri
minimize ON
2
(68)
subject.to. T
ス 0, 0 S ... UN
where
N-1 T
N
0:4 A
+
Σ t=0
0/)
B:
(e: - -Nv)(e: - -wwT 2T.
1
1
jever
1=0
Now will prove the following proposition.
Proposition 3. Consider a matrix H = Josscces and HA, If h4+1, + 0 for SiiS N-1 and treating the solution of infeasible maximize problem O, the optimal values of P (CF, H, Rt) and P2(Cu: HA, Rt) are same.
Proof. The proof structure is the same the proof of Proposition 2. First consider (fr N as length N which gives Si. Tí SN+1, Furthermore, in the proof of Appendix A, we proved that
8 = Ti,u)
Therefore,
8 - 0
+ T 0.
The other steps are the same as the proof of Proposition 2.
Proof of Theorem 5. HOGM is the solution of (46) since (OGM) is A*-optimal with respect Cp and (P1). Additionally, if
(46) maximize Pi (Cr, H, R) H.h++...00
(69)
holds, HOGM is the solution to the following problem due to the strong duality.
L
maximize maximize 1 Ba...,
RR
2un
(70)
subject.to. S = 0, 0 S uo S ... S uN.
Applying Proposition and using the fact HOGMG Hoam provides that HOGM. is the solution of
VoL R²
maximize minimize H, "g.... uN
(71)
subject.to. T 0 00 S UN.
Finally, if
(47) maximize P PL H, R)
(72)
H.,,
holds, the optimal solution of (47) is the HOGM.G which proves the A'-optimality of (OGM-G) with respect to LG and (P2). The proof of (69) and (72) uses the continuity argument with H and please refer [44, Claim 4].
34

---

Omitted parts in Section
C.1 Omitted calculations in Section 3.1
Strictly speaking, (7) is not a differential equation but rather a diffeo-integral equation. However, if H separable, i.e,, when (t, s) = e0())-<(t) for some 3, [0, T) - R, then (7) can be reformulated as ODE.
Assume the process (7) is well-defined. We can alternatively write (7)
x(t) - 7(1) J B()) (
(0) 20.
(73)
By multiplying ed(t) each side and differentiating, obtain
(t) + +
( 0.
The H-dual of (73)
=(t== - / (-(00-
Y())= 20.
Under the well-definedness, by multiplying -(T- each side and differentiating, we obtain (1) + ²(T - (4) + -
0.
When ((s)= = r log two ODEs become
x(1) + _ X(1) + VS(((()) =
(74)
and
(t) + T
0,
(75)
which are introduced in Section 3.2.
For the calculations of energy functions of (74) and (75), refer [51, Section 3.1, Section 4.2]. They proved that
(r 1) (0) 2.11² = (f(((TT) x.,) + 1/2 TX(T) +((((T) =2.
1 (r 3)8 x(s) ds (-' 2s(X x.Jos
- x. x2,1 1 -
holds for (74) and
+3 T |Y Y())
72 (U((())) -(X
/"
I 3-3
[ (T- + (s))))))))))YX -Y(T)) ds 1" 2
4(r 1) [T((())))
(s).. ((T)
(T -) s)3
(T s)3
holds for (75). After arranging terms, we obtain the results in Section 3.2. 6
C.2 Proof of Theorem
To begin with, we give formal version of Theorem 2. Consider two following conditions.
u(T) (F(X(T)) (M) {U(), (V (VV00) E A1).
(C3')
2 (V V(T), (VY (T)(())))) E Az).
(C4')
where Ai and A₂ family of vectors which makes Fubini's Theorem be applied and will be
defined later in this section.
In [51], they considered the ODE which gradient term is 2V (() instead of (()
35

---

Theorem 6 (Formal version of Theorem 2). Assume the C-FSFOMs (7) with H and H are well- defined in the sense that solutions to the diffeo-integral equations exist. Consider differentiable functions u: (0, 7) + R that v(() w(T-o] for / [0. 7] and
(i) lim, ut) =
(ii) o(m (1N.--7776((0000---N0/--VXXX0000
O.
(iii) f is L-smooth and convex.
Then the following holds.
[C33)) is satisfied with u(-) and H] <> [(C4') is satisfied with vo-) and H4]
Calculations of energy functions via transformation Frist of all, we calculate ((T)
-
-
1
|x(0) - =f ! +
fr) ds
2
(X(0) P u'(s) (V) ds - [f" ( ((= ds
2
1
(x(0) x²1 / (V)(())) - x())) ds
2
/ ('(s) (VF(X(s)) (()X X(s)) ds I' u(() (Vf(((s)),, ds
+
( - xx = -f" (())((())))
1
% ('())\(((())dd
2
2
+ [' n'(s) X() - ds S/¹ u(s) (s((X(s)) {()) ds.
We used parts of integration and = lim, u(s) 0. Since x(0) x² can have any value, (C3) is equivalent to
u (()))(
(s)) (V)(((()) ds 1' u(s) ((1) ds 20 (76)
holds for any (V)(((s)))
Now define transformation (fs Rd ) + fg. E R [R)>e >
as
Js: = u(s) + [' u((2)f.dz, s sE [0,
(77)
and (g.
Rd Rd) "E(oTT
{fa Rd e >
90 + u(s) (g. - goo) - f." v'(b) u(b)2 (g. gb) db, s [0,
f:: u(T)
(78)
One can show that the above two transformations are in the inverse relationship. Next, we calculate UT)). Define fa: (s)(s.)) Under the transformation (77), we can find simple expression of
36

---

(76).
1
J T
u'(s) ((, -(s)) do f-" u(s) X(s)) ds
(76)
|1
2
x(a)da ds + f u(s) u(s) Jmn l- x(a)da) ds [sn
|1
u(())
Ss:
2
u
1
u'(s) far / X(a)da ds f-" [o¹ (u(s)) fo) dads (79)
11
2
(0) 1
T x(())
['" ds(s da [" T S (((ss (u(s) fa) dads
11
2
1
+ I.'² T
S H(s,a) a) (Far 9a) dads.
11ool
2
We used Fubini's Theorem at (o). Next we calculate (TT).
T(T) ( [- d (1V6)))-1 -Y)))) (())))
V(T)
ds u( -8)
T(T) (S(((O)) -(X(T))) + {" p uT 88)
u(T sss
I d 1 ds u( (f(Y ((Y(T)) -(1) (T), + /'' u'(T -iT-- 5)) u(T - 8)2
ds
L. uT - (Vs)) -V/V())))))) ds.
(o) comes from parts of integration and the assumption
lim u(s) + .+8
- 0.
To clarify, u' 5) = ul (=(=)\==T=-. Now briefly write g:: = VT - 8)). Then
1
V(T)-
[V)((()))
2
1
u(T) [- (0o.((s) ds + 1" u'(T - 8)
1
2 11
u(T s)2 (Y(T) - V(s). gr- -9n) ds
1-" u(T - 3) (v()). gr- 90) ds
1
2 11.00122 ('' IT(T s) s)
1
J: 9r-)
-r----r------ ds
u(T 2)
T(T) 1'" (g0: v(s) ds - 1"' u(T -s) (v(5), ((6),9T-s (00 ds
(0) 1 11 + (-1
T ( u(T))00 9u uTT s) (gr- go) + f/r nd -T b)
u(T b)2 (9r-b gu) db. M(s) ds.
2
(80)
37

---

We use Fubini's Theorem at (o). Finally, using (78), we obtain
V(T) 2
[)(((T)))
|19011
(IT=))((s)) ds
2 1190ll2 + {-" (Fr-on { (s, ds
(81)
/'' (Ir-.))
T
( H(T u. - s) ds
2 |1,011
jo
T
I' Hss, a) (fas ga) dads.
|l
2
2
Proof of Theorem 2 Define Ai and A follows.
A ([Ja)rrooor/Anallll Analysis in the previous paragraph holds),
A H00 Analysis in the previous paragraph holds).
Now prove Theorem 2. We have shown that (C3') is equivalent to (76) 2 0 for all [V)(X(s)) E A1. By definition of A1, equivalent to
2 |loll + //" {. H(ss a) (fa 9a) dads 2
for any fga E A2. Moreover, by (81), it also equivalent to
- |1ool1 + [[ ([H(s,)) (Sa: 9e) dads V(T) - ()(())))) o
for any (g.). E Ag, which (C4').
C.3 Omitted parts in Section 3.3
Regularity of (10) at - To begin with, note that ODE (10) can be expressed as ((t)= ( - CT - - (V (tt)= = ((t)
for t (0, T) Since right hand sides are Lipschitz continuous with respect to W and Y in any closed interval [0. s] E [0, T), solution (Y, W) uniquely exists that satisfies above ODE with initial condition (Y) ((0) (yo. 0). Next, give the proof of regularity of ODE (10) terminal time 7' in the following order. The proof structure is based on the regularity proof in [51]:
(+)
(i) sup
bounded
(E(O,T)
(ii) Y (t) can be continuously extended T
(iii) lim
Y (+) =0
T
8(t) ()- = CPV)(Y(T)).
(iv) lim
Step (i): sup (0/)
(t) is bounded.
ODE (10) equivalent
1
2p 1p-1-
(T s-p-2 ((s) + (T 5)p
-C3 = 0.
(82)
38

---

By multiplying (s) and integrating from 0 to t, we obtain
(T (T-s)p-2 s)p (V()))(())) ds + J (T - (T-s)0-1 (((() do + Cpp 1'' (V()))))()))
2p 2p-1
VS((())) ds =0
and integration by parts gives us
1 2(T 11p-2 |10 27v-2
1
[(0) 2 + /
2p-1
((5) ds + Cp -
=
(T - (T-s)p-1
Define (():: (0, + R as
|r/0 2 + +Cp² (1((())) - ((((0)))
T (t) = 2(T -
Since
(())
2p 1p-1 1 (T - s)p-1
{s) ds,
(t) is a nonincreasing function. Thus
2(T t)p- + - -
f.))
(83)
{1)
and the right hand side of (83) is constant, which implies M :=
sup
<0.
3E(O,T)
Step (ii): (t) can be continuously extended to T. due to the following analysis.
We can prove Y() is uniformly continuous
|Y + - - = 11,
146 (s)dds
1+6
$
Y(s) ds S 5M.
Since a uniformly continuous function g: D Rd can be extended continuously D. Y: (O,T) + Rd can be extended to [0, T).
Step (iii): lim I-T
| o. We first prove the limit lim
[e) 0 exists. From C.3,
2- f()(t)) also exists. Moreover, Vt()) is (-T
we know lim (t) exists and by continuity of f. lim /- non-increasing and
(1( 2(T - 1 |/0) +
U ((Y(O)),
rool I- (T-1)-- exists, which implies lim t-
thus lim (1) exists. Therefore,
lim
{1) = when
--
p > For the case p p= =2 2, lim (-T
|1)
exists, and lim
|r0)
= 0 follows since we have
4-2
1
|0)
L. (T- spp-1
{(s)
(t) = 27F
ds
is bounded below. Thus the value of integration is finite.
Step (iv): lim
8 t (T-1)P
= (P))( The (7) form of process Y
-(t==// 1. Cp² - 2)2p-1
V ds))ds.
(T
s)p+1 s)p+1
39

---

By dividing (T-) each side, we obtain
(t) (T 1)p-1 -T 13 /.' (T-s) V.(((s))dls
Cp²
By the result of C.3, we can apply L. L'Hopital's rule, which gives
lim Y())
Lo (1-8)p+)
Cp' ()(Y =CVVf(Y(T))
lim +-
T-T - -)p
(T - t)-
(I ((T)) Therefore, Also, since V is L-psiiih -
- V/(Y V =0
lim t-
(84)
(1-
for any 8 < p.
Applying Theorem 2 to (10). For the p 2, refer [51]. Now we consider the case p > with u(t) = Ct and vtt) C(T-1)>- First, we verify conditions (i) and (ii) in Theorem (i) holds
since u0) = O, and (ii) holds since
lim 8-7-
- (V
f(Y +VV1))))) (s))
lim 8--
(T
- -V((
(o)
lim
C
s-T-
-P(T- - -SP-
(s)
lim pC s-T-
(T (T-8)P (T- VS(( - V)(((T))
-0.
(o) uses L'Hospital's rule and (o) uses the limit results at the previous paragraph.
To prove
(V((((M)) & J
CTP
2
we carefully check that for any T-smooth convex function f. (V) E Az.
Verification of (80). Fubini's Theorem is used for
n' a'(T - 8) Jssaugr 185a
u(T s)2 5)² (V(V)))) - -V((((T)))
JossaST
1.ca
-
C(T - s)ptt
The above function is continuous in 0 S s,a S 7 due to lim with 3 2 < p.
(T-1)-- CPV and (84)
(())
1---
Verification of (79). First,
Y()) Y(T)-
Y())
lim
1jp-1 lim -p(T 11t--)p-1 -CV
(T- f)p
-Y(())- <00. Now will show
holds from (iv). Thus sup6e(0.7)
lim a lte fa 0, VC> O.
a a+++
40

---

Observe
1
(ga 90) - -f²
P
Ja
CTp
+
CTp
Cbe+I
(gb - ga)
and
a ltc
a l+e
T pal+e
|a + fa
CTP 90
(ga -go)
C' (96 9o) db
CTP
tr
pa
pa palte
CTp 90
CTp (9a 90)
+
Chp+T 1196 goll dll
Ch
11ga - 9oll
a tte
2+e
[ Lpa
Chp+I - -Y)- db + [- Lpa
CTp 90
CTp
(ga- 90)
+
Cha+i
(Y -a) -Y(T))
a
at
+ /² Lpa
Y b) -))-
CTp 90
(ga
[0)
db
CTr
La La!te
1
| - a) - Y(T)I
a
TP
By using the boundness of Y(T-b)-YRD Next,
we obtain the desired result.
a a2c-pt2X(0) ((a)
a (a,
Cp2b2r-1
ff db
12p-1-2e
Cp2b20-2-
020-1-26 l1bl+e foll db
Cp 2p
|b |
sup bE[U,a]
which gives
lim (2)ptt2((a) = 0, v0< 2p 1. a-++
For the final step, recall that Fubini's Theorem is used for
J losas"-1 (Sor ((a))(a)) dads.
To prove that the above function is continuous, take any 0 p-2 Then
lim SP (1. (fo.
lim
2ctp-2 (((a)..)
22+22p-
lim +0+
2-2222p-3
fall
lim a=+0
X(a)
0.
05aS*.
0Sa5s, 5, +0
a
22tpp2
which gives the desired result.
D Omitted calculation in Section 4
D.1 Preliminaries
General proximal step and composite ESFOM For a > 0, we newly define a prox-grad step with step size 1 a follows:
al || u12
argmin ZER
(f() + (Vf()), +22
(85)
2
First, will provide a generalized version of prox-grad inequality: Prox -rad inequality is originally used to prove the convergence of FISTA as below [11]:
L 11y y1
#) L E,
y. x 2 s F(x) 2
41

---

Proposition 4 (Generalized version of prox -rad inequality). For every z, y E R the following holds:
L
ve,y. = F(y F(x - La Ly
10000--00 y, y, 0 - y0
3 111 0: - y11² S 0.
2
Proof.
The optimality condition of (85) provides
La(y - y) + V =0 u e 0g(y
(86)
In addition, L-smoothness of and convexity inequality of f and g give
I.
B. v) I v12 gly g(y a (u,n y0 (y f(y) - (V((y), v) s f(x8.a).
aly
+ ( (-La(y88 - - Vf(y), = y S g(x
Summing the above inequalities provides the generalized version prox-grad inequality.
Two problem settings for the composite optimization problem. For the composite optimization problem, we consider the following two problems.
(PI') Efficiently reduce
F(* F. assuming x. exists and | xx1l S R.
(P2') Efficiently reduce min (v) (x || assuming F. > - 0o and F(yo) - F. S R.
Note that when g = O. (P1') and (P2') collapse (PI) and (P2), respectively.
Parameterized FSFOM that reduces the composite function value GFPGM [27] First define
I.: argmin F(z). We recall the composite function minimization FSFOMs with x; S.a by lower triangular matrix (hr,)ossccsN as follows:
Th+1
ahu41.i (x+ -2; ( Vk = O....N
N 1.
(87)
0=
In the case g = 0, (87) collapses to (1) as a (z- =20aa = (2 - (+²) = Vz(z). The iterations of GFGPM are defined
(Th t +x)+++1
(th -x))x+1 (20.1 - mx). (011-xx).
Ik+1
..1 Ik
1b,1 x2-11
+
k 0.
Tx
t4Ix41
(88)
where _111 xo and [t, 0, Ti
Ej=o S 1 for 0 sis NJ. (88) reduces the composite
function value as follows:
1 1
F F. <
100 =.11?
(89)
Tv
We can reconstruct the convergence proof [27, Theorem 3.3] via our energy function scheme, which is defined
Uh = 7 11:00 - 12.12 +
Σ us 1,, I L +
Σ 2=0
(us
(90)
2
for t: 1, ,........ N. The convergence rate result (89) proved by using that { is dissipative, and
UN TN (F( 2.1 -F.)
L
+
Σ
(u
12) -
x )
+
L(T; 2
8.1
0.
1=0
i=0
911)
42

---

Here, we can make crucial observation.
The formulation of (90) is same with (2), which all [ are changed into 4: D and u; T, (o)
Moreover, express the recursive formula of the H matrix of (88)
+ (f 11
i == k i == i i= o.... ......,
T2+1
(Tr tt (HE,A-1-1)
(92)
(Th 11--ta 11.06 11- hkg
1x76+1
As we used a parameterized family in the convex function (see Section 2.5), we will use these convergence results to construct the method for minimizing min ||:||
Relationship between minimizing z ll - uNl1 and minimizing min memFeFFF ||ll
Note that La(yN 8.0 - uN) + ( + == 0, u 0g(uN which gives
|0ll2 V - [ La JN UN "I1 s L²(a + 1)2 min vEDF
1|
UN a12
(0)
(93)
is triangle inequality and (o) comes from the L-smoothness of f.
D.2 Proof of Theorem 3
In this section, we give the proof outline of Theorem 3 and discuss the construction of matrix C.
Proof outline of Theorem 3. We begin by proposing a parameterized family reduces 2E || 10.0 yN] I| under fixed value a > To construct this family, take {4)] T. T 4 that satisfies (96). We define the H matrix of the family as (2 Ho + C) where Ho has the same formulation the H matrix of GFGPM (88) and C follows the recursive formula (97). We refer to this family as (SFG-family).
We prove that (SFG-family) exhibits the convergence rate
aL B.a yy < TN (F(ro) F.).
luu
(94)
2
which is motivated by the observation (o). In parallel with (o), we consider the energy function
VE- F(vo) - Fly R..0)
+ by 1, 9.0
1
W., 1 +
(UN. Bil"
TN
T
TN-i-1
TN
1=0
for t: O,..., N. which [yN, *] changed into 1,01, all other
[:-]] terms changed into ( -
and 24 Tx-1¹
(94) follows from the fact that (Vi is dissipative and
aL 8. - M
uN 2 < VN.
Detailed justification is given in Appendix D.3.
For the next step, we show that (SFG) is an instance of (SFG-family), under the choice of
(i + 2) 3)
a 4,
0 < Kis N.
The detailed derivation is given in Appendix D.4.
43

---

Finally, combining the convergence result
2 0. 2 I VN Vo S
(N 2) 3) (F(yo) - F.)
and (93) gives
min sEaF(yN))
||a|2 S 25L2
19,4 UNN
yN 1|2
S
50
(F(1)) F.).
(N 2) +3)
Construction of matrix C. Define
9: La 9o0
9o B.ay 1... 1yN - 3.
For an FSFOM (87) with matrix H1, we have V/x at 11 YN 112 2La² Ir gT with
N
To: = a²
Σ
(MT + ................................ ... - --1) + (c: - c.-1)(e
+........ ... eN) (H1)
TN-1
1=0
N
+
Σ
(()-) - -;)(e-))-----)))) eN) + (e-1 -N)( e;)T) -,))))
1
cool e
TN-i
In
1=0
B3
N-1
+
Σ
Tw-1-i e.e. e
1
TN
To
where e-1
0, e is unit vector which (i + th component is 1 and RN+1 and H2
0
yN 2| follows. Next observe A + BB3 =T(H1, for 1s TN-i which defined as (22). By expanding (91) and defining
If we take Hi that makes @ 2 0. VN L y
Hi 0
g': I[500 -Fo 1...
0..0 IN
N
Un TN (F F.)
- (11) = =Tr (o' (T') (x=
40 T.
+
U1
Ui
t=0
follows where
8 S(Ho, u) Σ (T, -T, e.e.
Here, u, = T, and S( Ho, u) given by the formulation (19). Using (91), we obtain
N-1
S(Ho u) Σ (2T. eee (TN Jever
Now recall matrix M(u) (26) and the result of Theorem 1: S(Ho, u) M(w)) o)) o)M(u).
(95)
By substituting H1 1 H + X and using (95), the result is
M(uTTTMMin
(2T. e (TN - (eNe
+ Ma²M(u)T
Σ TN-
....))ee.....e...... (XT + .............. teN)(e - -e-1)" + +(e e,-1) .... +NN) M(u)
N-1
+M(u)T
Σ
c.e.
eNec M(u)
Ty
Tn TN-1-i
To
1=0l
C
44

---

0 0 X 0j
where X::
Next, consider As as function of the lower triangular matrix X' The key observation is that if we choose A' appropriately, all non-diagonal terms of C3 can be eliminated. With this choice of X, we have
N 7 = a
N Σ
T?
2-2 Σ j=0
2T: - - e. - Tycool
c.
T
Tj
k=0
Note that T contains only diagonal terms. Therefore, T = 0 is equivalent all coefficients of c,e! being nonnegative, which can be formulated using t; and T,
Remark. In the proof of Theorem (B2 and B1 (27) and (28)), we have shown that
A1 = a² Σ (xd) (xd) TT(ee e.4 + ..... + + Ti(eo + e,)(e, - xx
Observe that (e; 01+1) +... e,)T is lower triangular matrix and X strictly lower triangular matrix, i.e., all diagonal component is 0. Thus it is worth noting that A4 cannot induce any diagonal term e.e?, choosing matrix as the optimal one.
D.3 Parameterized family reduces the gradient mapping norm
FSFOM that reduces 27.
L
G. UN in the composite minimization. || 1
We propose the param-
eterized family that reduces 27.
9.a
UN
For fixed a >> 0, take {4) T; Σj=o by that
satisfies the following conditions:
a2TT ()) 2 To:
T
+
(96)
a(2 12:) z
+ 4
+
h ==
Tk-1
To
1=0
where we define Σ T. = 0 for & = case. (Cka)oSi<AgN
We define an lower triangular matrix C =
h Ti
i = 0, k = 0
2-
Ck+1,
Thi1
t++1
to
To
t
T
+
Tk
Te
i == ki k = 1,...,
(97)
0
1x+1 (T)
(gTk-1
Ch.
h -1, i= 2. N -
Matrix C has a crucial role in the correspondence between composite fuucction value minimization and composite function gradient norm minimization with 2 -)
Proposition (SFG family). Assume that we choose Ho matrix of (88), and define C' as (97). Consider an FSFOM (87) which matrix is Ho C) Such FSFOM can be expressed as
Vk++ = yk + B/ (y) Bia ( + 2/ (1 2.a - - k= O.....,,N
8 11 1 -N--1k
%/e IN -N-x(3N- ( -
84.
AN k + -N-k
3N-K k + YN-k
(SFG-family)
tx+1 (Th - tx)
t.+1 (th - Tx)
1
3x
Ch+1k
4TT111
TxT41
and y Un- Then exhibits the convergence rate
aT
1
Un
1 < Ty
(F(2)) - F.).
2
45

---

Proof of Proposition 5. To start, we give the claim about matrix C.
1 0 satisfies the following equality.
Claim 1. C:
C
2
Σ
Ti(e: ec0 te:)²
(98)
LN f N-i + 1 To
T
i-2
ENfy Toene
Σ
Σ T
T
T:-1
where fe is any basis of R.V +1 N++ which is defined as
eN-1 f-1 are zero vectors and [f:), 1=0 are another basis of
T, (c: c.41) = fN-i fN-i-1, i= 1.1......A N.
The proof of Claim will be provided after the proof of Proposition 5. To begin with, for the FSFOM with matrix (2 Ho + 1 C) define the energy function
V4- F(yo) F + 11 Yol
1
1
We 11+1
(yN. vi)
TN
TN-i-1
TN-i-1
T TN-
for 1 = O,...,N N. 1 is dissipative since (,, 1/- S 0. This energy function is inspired by (3). Note that if we can prove
aL 2.a 2 UN
yN < VN.
(99)
then
al
B.a MN
uNll
SNN s S
1 (F(y)) a) s (F(()) F.).
1 TN
T'v
Thus, it is enough to show (99). Defining g: La(y vi aa)) for 0 < sist N gives
18, 21 Fay F(y
+ (g), 4ソ) +
La (gj. 9.) 2La 11,,11?
2a
18-1. wol"" = F(yo - F(vo) +
19o1
L 2a
46

---

Plugging the above equalities provides
2La²
VN
al
uNll²
N-
N-1
-2ax²
(gi+1.31 Vit1)
Σ
(gs, (g.: yN
yi)
+
2a 1
-1900l? - a lllxN 1|
-i-
TN-i-1
Tv-
Tn
1=0
1=0
N-1
N-1
1
+
(2a (9i+1. - - -119++111 112)+
+
(2xx (gi. 9N) - -119:113
T N--i-1
TN-i-1
TN-s
==0
2=0
2
1 - -2+11
+
Σ
(ot. yN v4)
TN-i-1
TN-i-1
Tw-
==0
N-
N-1
a
|10+11 - -:ill + Σ
a
1191 - 11N1-9N112 -algx|1 + TN |1
T--i-1
TN-i-1
TN-i)
N
N-1
+
(-allgill? + (a - 1)119++11*
+
Σ
(-allex 11 + (a- - 1)119:113)
TN-i-1
TN-i-1 TN
1=0
1=0
2a
110011==
11
Tx
Tn
N-1
1
(9141:311
V(+1)
Σ
1
(0t. yN v1)
TN-i-1
TN-i-1
TN-
1=0
1=
N-1
N-1
11 - 96ll2 + Σ
a
11 - -9Nl1* -allaw1
11
a TN
|
-N-1-1
TN-1-1
Tw-1
i=0
N-1
+
|1aul1
Σ
|1
1
1lax|1?.
Ty
Tn -1
To
1=0
Next, define g: = [90l91 ...
[gN] and
o
0 0
H1: Ho + 2 0)
Ho:
Ho
0]
By the same procedure as the proof of Theorem 1, we obtain 2La² (V Tr (T
a/
0.0 - yn 2xrl2)
2
where
7 =
(f: + ff) - ff-1) + (f: ff--) + +.... {x)
TN-i
N
+ a
(ff - (f)(f(1 - TT + (f:-1 f - -)))
fuff - fNfN
TN-i
Tn
N-1
1
+ fufg
Σ TN-1-1
fff.
fNff
TN
To
And consider the vector e; <W++1)x1 which same with (29).
In the proof of Theorem ((27), (28)). we have shown that
N
(f + ... ffv - f--1) + (f. f. +... (72)
2L
TN-i
i=0
1
HT
CT
N
Ti(eo +... +.) e++1)
+ 2L
Σ
Tí(e: e +.. +...
(Hl + C
Ho
2L
?
a o2
1=0
1=0
47

---

and
1
1 foßj
TN-i ((f-1 (
fN) + (GG-1
-
(I) f))
[N [N[N
2T.
2Tx T.
21.
N
N E(T: 1=0
1
Σ (T; - 1)e
(T: - 1Ti
27.
1
+
Ti ((e: e.t1ee - e:(e: -(+1) - - TNexeN
2L
===
under the above transformation. Therefore, To can be expressed as
To = T a²
Hg
CT a²
Σ Ti +.... c:)(e: +:)e eit1)
Σ Ti(e, e,+1) +... .......))) e;)T
(#h
a
Ho c
a
a²
N
N Σ (T: -ii-ei--)e;
N
ta
Σ
(T; - 1e
Ti ((e, - e.1)e +ele, - e+t1))) TweNeJy
1=0
N-1
+
fof
Σ
f.f7
FNTT
TN
TN-1-i
To
1=0
a folg
= a. + B +
Tn
where
N
A = Hg
Σ Ti + ee) r
+
Σ
Ti(e, - e4+1) + ................................ ..,.,,,,) +e,)
Ho
1=0
N
Σ (T: 1i-1)e
-Ti--Ti-1
+
T ((e: ex41ee +e,(e, e(4))) Tweve
i=0
1=0
and
B =CT
Te + te:)ee: - e(t2) +
Σ
Tí(e: e + ..... e;) c
--1
1
f.f.
fNfJ.
TM-1-1
To
1=0
To calculate A, expand the energy function (91). Then we obtain
A Σ (2
G)eeTT (TN try Jevey
Moreover, by Claim 1,
N
T
8-2
B = To
c,o..
T
T
1=
Combining above results and Tyex for we achieve
T T:1
1
T Σ 2T. e.e The
Σ
e.e.
j= T
and the condition (96) makes each coefficient of e.e. nonnegative, which gives T > 0. To achieve the iteration formula (SFG-family), consider the FSFOM (87) with H + + C. which can be
48

---

expressed as
Tk++ 3kk +
BE
(o (m
-R--1 + 7k (x -kk).
k == O...., N 1,
4Tt [x)
(12 Tk)
Bx.
4xTT++1
Thk
La TTT11
- Ch+1,e
For last step. We make an observation that Proposition can be applied when all at terms changed into 2 a,, Proposition 1 gives the H-dual.
Proof of Claim
The left hand side of (98) is
Ti(e: (e4 + + +e,)² ) c
2
(I c
Ti(e: e:4) +.))t,e)
N
Σ
(fN-i fw-it2)(00 + ... +c;)" .....
Σ
ASi
Σ
fx-s0!
Σ
N
oo
1=0
A=++1
Now we calculate the right-hand side of (98). By plugging
fN = T,C; + 1441 + ..... +.... INCN:
N
N
T
1 i-2
N-1
Σ T:-1
fN ff + To
ENfy - Theoet
0 =2
Σ
a
T
Tj
j=
1=0
where
an = 1le1 +... INNN,
4
1-2
Ti
a;
(1++10:+1 +.. (.. i= 1, 1,..,, N
To
T--1
==
Now claim that a, Σ
Ck f.- for i == =0 O....,NN N - 1. Note that
k=it1
CN-
Σ
CKii (TeCk 14110441 +.. tNeN)
Rmi+1
k=i+1
N
(Cr,iTss + Ck-1,it4 + ... + ci+1,tt) e
k=++1
Coefficients of e:41 are coincides since
c1,0Ti = bi,
1-2
C41,TT++1 = -441
+
i= i= -1
To
T
T;-1
1=0
Now assume
1
C3 + C--liiy ... C441d
(100)
t/t1
9441,15+1 + C3sts++ + c=11,t
49

---

By multiplying the above equation recursively, we obtain
h+1
5+1
14+1 9jtti t.. + c241,15+1
for SSSN - which implies a; Eksiti CL,NN-
To prove (100), expand and obtain
1410,,77 1/ (1i+1, + ((14+1))
Above equation holds due to the recursive formula of C' (97).
D.4
Instances of SFG family
Derivation of (SFG) Here, we will show that (SFG) is the instance of SFG family, under the choice
of
T, (i + 2) 3)
a 4,
0 H i N.
First, 1;
1+2 for i 2 1 and to
3 2.
Also (96) holds since
2
4
3
2 2
4
(k+3) 16
(k +
(k + +3)
(k (
2)
(k +
(2
2 k x)
4
+
+ 4
== 1= N.
2
4
(++1)(++2)
Plugging above values into (92) and (97), obtain
= k, k = 0
1
k
i k, k = N....,N-- N
h
E44
(ht,
i = k 1
O,..., 2-2
and
i 0, k 0
1,+
2(4k++55
3(k+4)
k, 1, .y..... N
k+14 Cki
k++
0, O,...,k h: 1, = 2
N
Other terms come directly, and
2-2
tx+1
tk
T
Ck+1,
+
to
Th+1
To
T
Te-1
1=
k-1
1x+1
La
+
t
Σ
1 +1
Tk+1
To
Tj
j=0
k43
k
2
1: 2
4
4
2
X
+
+
+1)
(k++3)(k+4))
2
3
2
3x3 3
(k: + 1) + 2)
2
k 1+2 2
1 4
2k
+ 1
k+4
3
2
2
2(4k + 5)
3(k: + 4)
50

---

To sum up, the matrix (ok.Josic = Ho + 1 C' satisfies the following recursive formula.
16
(1+ 5
i 0,
1 + 106+5 6(K+4)
i k; h = 1, 1,... N W-1
9
(gh.r +
1
k-444
K+1194 gRi
O,...,h. k -2
Note that
1
h
1
2(4 + +5)
9k+1,
1
+
4
h: +
16
3(k: + 4)
1
4k 5
1
4
k
6(k 4)
1
10k + 5
1
6(k 4)
Therefore, the FSFOM with {gr.i Josickss can be expressed as
8.4 31 = 00 +
[ - -x 2..1)
1
3.4 xo
2k41 Fx
+
k ++1 1
9.4
$1
+
4k 1
k= N-1
+4 4
6(k
+ 4)
where x = Eg. To obtain the H-dual, we apply Proposition 1.
3k+1 = 1k
0.1
+
(N + 1)(2N 2k
1)
Uk
v
+
(4N 4k 1)(2N 2k - 1)
(1
(N
k + (2N - 2k
1)
6(N - k + 3)(N - 22 +
0.4
3
Φ4
8.1
3
0,4
yN-1)
UN -1
UN-1
UN VN-2)
UN-1
10
40
where & = 0, ...,. N and y-1 = yo-
Fastest method among the SFG family via a numerical choice of a In this section, we give simple form of SFG, when all inequality conditions in (96) holds as equalities. {geaJosicksN becomes
91.0 - (1 (1+
(to -1111
1
t
Ti
a
Ti
and for > O,
1
(14 1)1x+1
1++1
1
1
+ Tk
11,
1
+ a Tk+1
tk
+
+.. ... +
Tht1
To
To
Tx-2
Tk-1
1
(1+ 1 -1)(x+1
1 1++1
a(2Tx
12)
Tk
T2
Tk.
1
+
+
Th+11
a² Tktt
Tk-1
1
(44 - -1)tx41
1 1++1
a(2T
-
12)
Tk
1 +
0
Tk+1
a² Tk+1
1x
1
1 1++1
2T 12
Tk
1
1
1x+1 Tk
+
tx 1 1+
a Tk41
14
tx
a
The
1 1 (T 1x)4411
(1
1
14+1 Tk
a +
a txTR+1
a
a²
Te4its"
L++ 1 (Th (x)
1
9k-1,k-1
gh.k-1
-
TxT
α
t 1 (Th tx)
9k+1.i
gk.ts
i= k - 122....,
51

---

Hence FSFOM with 2. Ho + 2
a Tn Te-1tk+1 (Ix
(1-2)
iR+il's
F6+1
x-
(5 xKk)
Tk+ilK
where T-1 = 20-1 a²
By using Proposition 1, we obtain H-dual.
B.a 1ズ-1) + (1- TN-k BN -
Ur B.a
+ (1/kkk
Bia -ya)
Vk++
TN-k+1
TN-A-IIN+ (TN-k-2 + (1 (1- 2 TN-K-1)
B/ IN IN-K-ITN- (TN- (1 2 TN-x)
k 0......,NN
Since all equality holds at (96), the above FSFOM achieves the fastest rate among the SFG family under fixed Now optimize to achieve the fastest convergence rate. Combine (93) and the result of Proposition 5 to obtain
||ll2 < (3 + 1)2 uN - uN al < 2 + 1)² (F(y)) - F.).
min TEAF
aTT'
To achieve the tightest convergence guarantee, solve the following optimization problem under the fixed N.
2(a + 1)
minimize
aTN
subject to. a27o
10) = To.
T
a (2Tx 12)
Σ k= 1.,,..., N.
T
Denote the solution of the above optimization problem as R(a, N). Since R(a, NN depends on and cannot achieve glosed-form solution, we numerically choose and observe an asymptotic behavior of RRa, N). By choosing a 3.8, asymptotic rate of R(3.8, N) about N2.
E Broader Impacts
Our work focuses on the theoretical aspects of convex optimization algorithms. There are negative social impacts that we anticipate from our theoretical results.
Limitations
Our analysis concerns L-smooth convex functions. Although this assumption is standard in op- timization theory, many functions that arise in machine learning practice are neither smooth nor convex.
In fact, when 1. the FSFOM becomes FISTA-G [31].
52


Reviews:
[{"review_id": "ZoZyt0n3I3", "reviewer": "Reviewer_2PtR", "summary": "This paper presents the concept of H-duality, which refers to the duality between optimization algorithms. The notion involves two sets of algorithms: 1) those that efficiently reduce the function value, and 2) those that efficiently reduce the gradient magnitude. The authors create the H matrix, which contains the coefficients of previous gradient evaluations at time step t, for all fixed step size first-order methods. They define the anti-transpose of H, denoted as H^A, as the H-dual of H.\n\nIn the main theorem, the authors demonstrate that if there exists an algorithm that reduces the function value using matrix H, then there is another algorithm that minimizes the gradient magnitude using H^A. This duality property is applicable to both discrete time and continuous time first-order optimization algorithms.\n\nLeveraging this duality property for composite objectives, the authors utilize a proximal-based first-order method that minimizes the function value. Subsequently, they propose a novel algorithm that minimizes the gradient value.", "questions": "look at the weaknesses ", "limitations": "Have been addressed ", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The introduction of duality between algorithms is a concept presented to the optimization community. This idea not only aids in establishing equivalence between algorithms but also proves valuable in conducting convergence analysis for these algorithms.", "weaknesses": "The proposed duality, while introducing a novel perspective, has certain limitations as it does not encompass a broader class of algorithms and loss functions commonly used in machine learning. For instance, it requires the convergence of the last iterate and overlooks convergence based on average iterates. Additionally, it assumes the objective to be convex and L-smooth, which may not always hold in practical Machine Learning scenarios. As a result, the paper primarily pertains to optimization theory rather than providing specific optimization techniques tailored to machine learning applications, especially for stochastic algorithms frequently used in this field.\n\nThe paper lacks a clear explanation of how discovering this equivalence between algorithms can facilitate the development of better optimization techniques. For instance, in cases where the objective is convex and the gradient vanishes (\\nabla f* = 0), it is evident that achieving convergence based on function values can easily translate to convergence based on gradient magnitudes.\n\nAnother aspect that remains unclear in the paper is whether algorithms that are H-dual to each other exhibit similar convergence rates. For instance, in the gradient descent (GD) example, it is observed that the gradient norm can attain a rate of O(1/N^2) under certain conditions. Consequently, it is ambiguous whether two dual algorithms have identical convergence rates or if one may achieve a better rate. In the former case, it becomes necessary to conduct separate convergence analyses for each algorithm to account for potential differences in their rates.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thoughtful comments and suggestions regarding our paper. \n\n First and foremost, we would like to emphasize that the primary focus of our paper lies in its theoretical contributions rather than constructing a faster method. However, we firmly believe that H-duality opens up the possibility of developing a more efficient gradient-norm-reducing approach: an aspect we will further elaborate on in response to W2. \n\nAs for the concern about the exclusive focus on convex optimization, we believe that establishing a unified scheme within the realm of convex optimization is crucial to advancing toward nonconvex optimization. Prior to our paper, first-order methods of reducing the gradient norm were not fully understood. Particularly in nonconvex literature, minimizing the gradient is a frequently used objective. We posit that H-duality could offer valuable insights regarding gradient minimization first-order methods. Therefore, we view the exploration of convex settings as the first step toward unraveling the intricacies of nonconvex methods. Specifically, for a nonconvex $L$-smooth function $f$, the following holds for all $x,y$.\n$$ f(y) \\geq f(x) + \\langle \\nabla f(x) , y-x \\rangle + \\frac{1}{2L}\\| \\nabla f(x) -\\nabla f(y)\\|^2 -\\frac{L}{2}\\| x-y-\\frac{1}{L}\\left(\\nabla f(x) -\\nabla f(y) \\right)\\|^2\n$$\nUtilizing the above inequality and constructing the parallel energy functions may lead to a similar conclusion.\n\nMoreover, in the realm of minimax optimization, we anticipate that a notion akin to H-duality could potentially extend to minimizing the duality gap or the operator norm. For example, a natural extension for $f(x)-f_\\star$ is the duality gap and a natural extension for the $\\|\\nabla f(x)\\|^2$ is the operator norm.\n\nH-duality has provided a clear and insightful understanding of the relationship between one-to-one correspondence gradient norm-reducing methods and function value-reducing methods. Our work stands out as unique because it offers a unified analysis of both function value minimization and gradient value minimization. \n\n**W1)  The assumption of H-duality concerning the last iterate convergence and knowledge of $L$.**\n\n\n We acknowledge your concerns. In regard to our assumption of the objective being convex and $L$-smooth, we concur that it might not always align with practical scenarios. However, such assumptions are common in numerous papers addressing convex optimization (even those published in machine learning conference venues), including [28,49,11,29,(1),(2),(3)].\n\n Practically, the smoothness factor $L$ can be estimated using backtracking. In fact, (OBL-F$_b$) and (OBL-G$_b$) (Section 2.3 , Example 2 in our paper ) are originated from backtracking methods.  Regarding average iterates, we think that our methodology could be adapted to use a similar scheme. This is a topic we plan to delve into in future research. \n\n**W3) The clarity of whether algorithms that are H-dual to each other exhibit similar convergence rates.**\n\nBefore delving further into the topic, it is important to clarify two common initial conditions: (IDC) and (IFC), which are also written in (P1) and (P2) (lines 48 and 49) in our paper. \n\n(IDC) represents a condition where the initial point's distance from the optimal point is bounded, i.e., $\\|x_0 - x_\\star\\| \\leq R$ for some constant $R$.\n\n(IFC), on the other hand, implies that the initial point's function sub-optimality is bounded, i.e., $f(y_0)-f_\\star \\leq R$ for some constant $R$. \n\nTo clarify further, we have established a duality between **[(IDC), function value minimization], and its H-dual method [(IFC), gradient value minimization].** \n\nFor the Gradient Descent (GD), the known tightest bound of the gradient norm is $\\mathcal{O}(1/N^2)$ under (IDC), but it becomes $\\mathcal{O}(1/N)$ under (IFC), aligning with our results. \nAlso (GD) reduces the function value with $\\mathcal{O}\\left(1/N\\right)$ rate under (IDC), which matches the complexity bound with the gradient norm convergence rate under (IFC). Additionally, they share the same factor of convergence rate due to our main theorem.\n\n**W2) How does H-duality contribute to the development of optimization methods?**\n\nhe analysis of the *concatenation* of the two methods, which provides faster methods for gradient minimization, is as follows: Suppose we perform $2N$ iterations of an algorithm, using method $\\mathcal{A}$ for the first $N$ iterations, and then its H-dual method $\\mathcal{B}$ for the last $N$ iterations. Assuming $\\mathcal{A}$ exhibits an $\\mathcal{O}(1/N^\\alpha)$ rate under IDC, then $\\mathcal{B}$ exhibits the same $\\mathcal{O}(1/N^\\alpha)$ rate under IFC.\n\nTo elaborate, we have: $$\n \\|\\nabla f(x_{2N})\\|^2 \\leq \\mathcal{O}((f(x_{N}) -  f_\\star) / N^\\alpha)  \\leq  \\mathcal{O}( \\|x_0 - x_\\star\\|^2 / N^{2\\alpha}) . \n$$\n\nThe first inequality arises from the convergence rate of $\\mathcal{B}$, and the second one comes from the convergence rate of $\\mathcal{A}$. As a result, the convergence rate becomes faster than the original method that provides only the $\\mathcal{O} ( 1 / N^\\alpha) $ rate of the gradient norm. For instance, running (FISTA) for the first $N$ steps and (SFG) for the last $N$ steps yields a $\\mathcal{O}(1/N^4)$ rate under (IDC).\n\n\n**References**\n\n(1) : W. Krichene, A. Bayen, and P. L. Bartlett. Accelerated mirror descent in continuous and discrete\ntime. NeurIPS, 2015.\n\n(2) : C. Y. Lin, C. Song, and J. Diakonikolas. Accelerated cyclic coordinate dual averaging with\nextrapolation for composite convex optimization. ICML, 2023.\n\n(3) : M. B. Cohen, J. Diakonikolas, and L. Orecchia. On acceleration with noise-corrupted gradients.\nICML, 2018.\n\n*The other citations are from our paper, so please check our paper for reference. Apologies for the inconvenience due to the word limit in rebuttal*"}, {"review_id": "20pQ7NQXdI", "reviewer": "Reviewer_8tCz", "summary": "This paper shows an intriguing symmetry in convex optimization between first-order methods that efficiently minimizes the function value and those that efficiently minimizes the squared gradient norm. In particular, they show that if a specific Lyapunov function upper bounds the function value suboptimality for Algorithm A, then a corresponding Lyapunov function would upper bound the squared gradient norm for Algorithm B, which is the \"dual\" of Algorithm A. This duality relation is further extended to continuous-time dynamics. By using this new tool, the authors propose a new parameterized family of methods for reducing the squared gradient norm, as well as a new composite minimization method that improves the state-of-the-art by a constant factor. ", "questions": "- Just a clarifying question, it seems to me that the H-duality is only useful when the algorithm can be analyzed using the particular Lyapunov function in (2). On the other hand, many algorithms, such as the original Nesterov's accelerated method, may not conform to such a Lyapunov function, since they do not rely on the cocoercivity inequaltiy. Is it possible to generalize (2) to a broader family of Lyapunov functions?\n- By definition, it is necessary to know the time horizon $N$ to form the H-dual of a given algorithm. Is it possible to establish a duality relation between two anytime algorithms? More concretely, can we use H-duality theorem to obtain an anytime method for reducing the gradient norm?\n\nA minor typo: in (1) it should be $\\nabla f(x_i)$ instead of $\\nabla f(x_k)$.", "limitations": "The authors have addressed the limitations. ", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- I find the results in this paper interesting and novel. At the surface, accelerated methods for reducing the function value seem quite distinct from those for reducing the gradient norm, and the mechanism for the latter is somehow mysterious. Surprisingly, the authors uncover a one-to-one correspondence between these two families of algorithms. This new concept of H-duality could help us better understand OGM-G type algorithms and design better and practical ones for minimizing the gradient norm. \n- Moreover, the paper is very well-written. While the underlying proofs require heavy notations and tedious calculations, the authors manage to make the main theorems quite accessible and clearly explain the high-level ideas. ", "weaknesses": "Overall, I don't find any major issues with this paper. While this might be too much to ask, I feel that I still don't have a good intuition for H-duality theorem or why it makes sense to reverse the combining coefficients, except that the algebra indicates so. Still, I believe this could be the first step towards some more fundamental understanding.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and your insightful comments. They certainly will aid us in refining our paper further. I would like to clarify a few points based on your queries.\n\n\n**W1) Why does the H-duality theorem intuitively hold?**\n\n Let us explain the motivation of the main theorem and energy function, (2) and (3). They come from the Lagrangian of a certain SDP.  Let an FSFOM (1) with matrix H is given. Then we consider the following optimization problem :\n\\begin{align*}\n\\sup_{f} \t\\\\,\\\\, \t& f(x_N) - f_\\star\\\\\\\\\n\\text{sub. to.}\\\\,\\\\, & x_0, x_1, ... x_N \\text{ are generated by } H \\\\\\\\\n\t\t&[[ x_i, x_{i+1} ]] \\leq 0 ,\\quad  i = 0,1,... N-1\\\\\\\\\n\t\t&[[ x_i , x_\\star]] \\leq 0 ,\\quad  i = 0,1,... N\\\\\\\\\n\t\t&\\| x_0 - x_\\star \\|^2 \\leq R.\n\\end{align*}\nThe Lagrangian is : $L( f , a_{i,i+1}, b_i , \\alpha) = - f(x_N) + f_\\star + \\sum_{i=0}^{N} a_{i, i+1} [[x_i  , x_{i+1} ]] + \\sum_{i=0}^{N}b_i [[ x_i , x_\\star ]] +  \\alpha \\|x_0 - x_\\star\\|^2$  for nonnegative dual variables $a_{i,i+1} , b_i, \\alpha$ and the convex dual problem becomes\n\\begin{align*}\n    \\sup_{a , b} \\inf_{ f(x_i), \\nabla f(x_i) } L( f , a_{i,i+1} ,b_i , \\alpha).  \n\\end{align*}\nHere, we can reduce the dual variables into $u_i - u_{i-1}$ and $u_i $. For the other cases,  $\\inf_{ f(x_i), \\nabla f(x_i) } L$ becomes $-\\infty$. Therefore, if $L( f , a_{i,i+1} , b_i, \\alpha) = 1/u_N ( U_N  - u_N ( f(x_N) - f_\\star ) \\geq 0$, we have the function value convergence rate $f(x_N) - f_\\star \\leq \\frac{1}{u_N}\\frac{L}{2} \\| x_0 - x_\\star \\|^2$ . This is the motivation of the energy function (2) and the condition (C1). For the gradient norm case, we consider the following optimization problem.\n\\begin{align*}\n    \\sup_{f} \\\\,\\\\,\t \t&\\| \\nabla f(y_N) \\|^2 \\\\\\\\\n\\text{sub. to.} \\\\,\\\\, \t&y_0, y_1, ... y_N \\text{ are generated by } H' \\\\\\\\\n\t\t&[[ y_i, y_{i+1} ]] \\leq 0 ,\\quad  i = 0,1,... N-1\\\\\\\\\n\t\t&[[ y_i , y_N ]] \\leq 0 ,\\quad i = 0,1,... N-1\\\\\\\\\n\t\t&f(y_0) - f_\\star \\leq D.    \n\\end{align*}\nAnalogously, we obtain a similar Lagrangian function, $L(f , v_i ) = V_N -\\frac{1}{2L}\\| \\nabla f(y_N)\\|^2$.  \nTherefore,  $V_N - \\frac{1}{2L} \\| \\nabla f(y_N)\\|^2 \\geq 0 $ , we have the gradient norm convergence rate $\\frac{1}{2L} \\| \\nabla f(y_N) \\|^2 \\leq v_0 ( f(y_0) - f_\\star)$ . This is the motivation of the energy function (3) and the condition (C2).\n\nSurprisingly, when $H' = H^{\\text{AT}}$ and $v_i = 1/u_{N-i}$, $V_N-\\frac{1}{2L} \\| \\nabla f(y_N)\\|^2$ has the same value with $U_N  - u_N ( f(x_N) - f_\\star )$  under the transformation $u_i ( \\nabla f(x_i) - \\nabla f(x_{i+1}) ) \\leftrightarrow \\nabla f(y_{N-i}) - \\nabla f(y_{N-i-1})$. It leads to our main Theorem 1. For the continuous-time interpretation of H-duality (Theorem 2), we use the continuous-time version of transformation: Please refer to lines 707 and 708 in the supplementary material. \n\nIt may be too long for an answer to be 'intuitive', but to the best of our knowledge, we have all shared an understanding. We believe that a simple transformation : $u_i ( \\nabla f(x_i) - \\nabla f(x_{i+1}) )\\leftrightarrow\\nabla f(y_{N-i}) - \\nabla f(y_{N-i-1})$ will be the principle of H-duality. However, we firmly believe that even more profound insights underlie the duality between gradient minimization and function value minimization. Hence, we used the phrase \"open the door\" to convey that our discovery of this new form of duality is exact and that we anticipate numerous potential directions for future research and exploration.\n\n**Q1) Is the H-duality useful only when an algorithm can be analyzed using the Lyapunov function in (2)?**\n\nIndeed, the most well-known algorithms, including  Nesterov's FGM [35], OGM [24], G-OGM [26], GD [18], OBL-F$_\\flat$ [42], and others, can be analyzed using the framework presented in (2). While some of these algorithms may have alternative analysis approaches, their convergence proofs can still be interpreted within the context of (2).\n\nFurthermore, it is worth noting that altering the form of the Lyapunov function is a possibility. For example, in composite minimization problems (where the problem reduces to a single function setting when \\(g=0\\)), we have explored a different form of the Lyapunov function, specifically related to SFG (as discussed in our paper), FISTA [10], G-FPGM [25], and FISTA-G [29]. As we mention in our paper, we have left this as a future research direction to explore more generalized forms of the Lyapunov function.\n\nBy adopting framework (2) and allowing for different forms of the Lyapunov function, we hope to enable a deeper understanding and analysis of various optimization algorithms, opening up opportunities for further exploration and advancements in the field.\n\n**Q2) What about the necessity of $N$ in the H-duality? Is it feasible without a terminal time?**\n\nWe admit that our paper does not offer a dual version without the knowledge of terminal iteration number $N$. However, we suspect it might be possible, albeit not straightforward, as conjectured in  [16, Conjecture 1], which states that there would be no any-time algorithm for minimizing gradient norm having acceleration. If we presume the conjecture, we must discover the dual of Nesterov's FGM in an unknown terminal iteration case, given that Nesterov's FGM accelerates but the conjecture suggests all-time algorithms cannot accelerate gradient norm minimization, which indicates that there would be no convergence rate counterpart. \n\n\n**References**\n\n*Every citation is from our paper, so please check our paper for reference. Apologies for the inconvenience due to the word limit in rebuttal* \n"}, {"review_id": "Uk2i5XWQt0", "reviewer": "Reviewer_JyDy", "summary": "This paper studies the duality for optimization algorithms. As claimed by the authors, the notion they present is distinct form any previously known duality or symmetry relations. In this work, the authors present a one-to-one correspondence between methods efficiently minimizing function values and methods efficiently minimizing gradient magnitude, which is called H-duality. Using H-duality, a clearer understanding of the symmetry between FGM/OGM and OGM-G and a new class of methods efficiently reducing gradient magnitudes can be obtained. The authors claim that their new composite minimization method achieve better results than state-of-the-art methods in efficiently reducing gradient magnitude in the composite minimization setup.", "questions": "Please see my question in the \"Weakness\" section.", "limitations": "Not applicable.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper presents a novel notion of duality.\n2. The theory of H-duality seems to be sound.\n", "weaknesses": "1. The relevance to NeurIPS is a concern. Actually, this paper studies the duality for optimization algorithms, which is an important problem in Optimization and Control. I am not sure whether NeurIPS is the right place.\n2. In the Section 4 “New method efficiently reducing gradient mapping norm: (SFG)”, the authors claim that their method (SFG) is faster than FISTA-G by a constant factor of 5.28 while having substantially simpler coefficients. In the paper which presented FISTA-G, two graph were given to describe different methods’ effectiveness on reducing the gradient magnitude. But the result of experiments can’t be found in the paper, which make the comparison between SFG and FISTA-G is lack of persuasiveness. Could you add the result of experiments to describe the comparison between SFG and FISTA-G?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We value the considerate remarks and recommendations you've provided concerning our paper.\n\n**W1) Regarding the relativity of NeurIPS and this topic**\n\nIndeed, the primary value of our work lies in its theoretical novelty. In our view, H-duality is an unexpected discovery that may enrich our understanding of accelerated optimization methods and has the potential to have a strong practical downstream impact. We kindly ask the reviewers to consider the potential downstream value of our theoretical results. \n\nAs for the concern about the exclusive focus on convex optimization, we believe that establishing a unified scheme within the realm of convex optimization is crucial to advancing toward nonconvex optimization. Prior to our paper, first-order methods of reducing the gradient norm were not fully understood. Particularly in nonconvex literature, minimizing the gradient is a frequently used objective. We posit that H-duality could offer valuable insights regarding gradient minimization first-order methods. Therefore, we view the exploration of convex settings as the first step toward unraveling the intricacies of nonconvex methods. \n\n We also want to note that there are various convex optimization papers in the ML conference venues, including [(1), (2), (3), (4), (5), (6), (7)].\n\n**W2) SFG and FISTA-G**\n\nThe term '$5.26$ faster' does not come from the specific experiment, but comes from the exact worst-case analysis. In rigorous terms, the 'worst-case' rate of a given method $\\mathcal{A}$ is defined as $\\sup_{f,g} (\\text{Objective})$ where $f=L$-smooth convex and $g$ is convex. This worst-case analysis provides careful and risk-minimizing upper bounds.\n\nFor the FISTA-G [(1)], the worst-case upper bound is $ \\min_{v \\in \\partial (y)} \\| v \\|^2 \\leq \\frac{264 L^2}{(N+2)^2} \\left(F(y_0)-F_\\star\\right)$. On the other hand, for (SFG), we show that the worst-case upper bound is $ \\min_{v \\in \\partial (y)} \\|v \\|^2 \\leq \\frac{50L^2}{(N+2)(N+3)} \\left(F(y_0)-F_\\star\\right)$  (Theorem 3). This is why we mentioned that (SFG) is 5.26 times faster than (FISTA-G).\n\n**References**\n\n(1) :  J. Lee, C. Park, and E. K. Ryu. A geometric structure of acceleration and its role in making\ngradients small fast. NeurIPS, 2021.\n\n(2) : M. B. Cohen, J. Diakonikolas, and L. Orecchia. On acceleration with noise-corrupted gradients.\nICML, 2018.\n\n(3) : J. Kim and I. Yang. Unifying nesterov’s accelerated gradient methods for convex and strongly\nconvex objective functions: From continuous-time dynamics to discrete-time algorithms.\narXiv:2301.03576, 2023.\n\n(4) : W. Krichene, A. Bayen, and P. L. Bartlett. Accelerated mirror descent in continuous and discrete\ntime. NeurIPS, 2015.\n\n(5) : C. Y. Lin, C. Song, and J. Diakonikolas. Accelerated cyclic coordinate dual averaging with\nextrapolation for composite convex optimization. ICML, 2023.\n\n(6) :  W. Su, S. Boyd, and E. Candes. A differential equation for modeling Nesterov’s accelerated\ngradient method: Theory and insights. NeurIPS, 2014.\n\n(7) :  J. J. Suh, G. Roh, and E. K. Ryu. Continuous-time analysis of accelerated gradient methods via\nconservation laws in dilated coordinate systems. ICML, 2022.\n"}, {"review_id": "p08qFow6rT", "reviewer": "Reviewer_Fq7n", "summary": "This work defines H-duality, which is a one-to-one correspondence between methods that minimize function values and methods that minimize gradient magnitudes, under the assumption that the objective function is convex and $L$-smooth. It is proved in both discrete and continuous time dynamics that, when one method satisfies a convergence condition, the convergence of its H-duality correspondence can also be guaranteed. Furthermore, a new class of methods is derived by applying H-duality to a known class of FSFOMs, and the H-duality convergence theorem can be used to establish the convergence of the new methods.", "questions": "1. In practice a method is usually terminated when a certain stopping criterion is reached, and the total number of iterations $N$ is often not known or fixed in advance. However, in this work, $N$ is required to be known and fixed. Could the authors please discuss about this difference? How would it affect the applicability of the conclusions in this work?\n\n2. In section 2.3, it is not obvious to me why $U \\geq 0$ is equivalent to (C1), because there is an additional term $- \\frac{L}{2} \\|\\|x_\\star -x_0 + \\frac{1}{L} \\sum_{i=0}^N (u_i - u_{i-1}) \\nabla f(x_i) \\|\\|^2$, which is not in (C1). Could the authors please explain in a high level how to bridge this gap?", "limitations": "As far as I can see, there is no potential negative societal impact of this work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. To the best of my knowledge, the concept of H-duality proposed in this work is novel, and the theorems which establish the equivalence between convergence conditions of two algorithms and their H-duality are also novel.\n\n2. This work demonstrates that the proposed H-duality can be useful, by using it to establish a symmetry property between pairs of methods, to prove the convergence of them, and to derive new methods.\n\n3. The paper is in general well written, and the sketch of proof helps readers more easily understand the techniques in the proof. ", "weaknesses": "1. It should be noted that this work only applies to $L$-smooth and convex objective functions, and the value of $L$ is required be known as a prior, since it is used in the methods.\n\n2. If I understand correctly, the number of iterations $N$ is fixed in advance, which could also limit the applicability of this work. (details in question 1)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the thoughtful comments and suggestions you've offered regarding our paper.\n\n**W1) Assumption of $L$-smooth convex function**\n\nPlease refer to the response for W1) of reviewer 2PtR.\n\n**W2, Q1)  What about the necessity of $N$ in the H-duality?**\n\nPlease refer to the response for Q2) of reviewer  8tCz. \n\nIn addition, requiring the total iteration count $N$  of the method to be determined a priori (using \n in the deterministic stepsizes) is a common property among stochastic gradient methods with convergence rates. Since (OGM-G)'s discovery in 2018, the acceleration mechanism of (OGM-G) has been an active object of study in the field [(1),(2),(3),(4),(5),(6),(7)]. In fact, if a threshold $\\epsilon$ is given, we $N$ can be selected to obtain the desired error: For example, (OGM-G) with  \n \\begin{align*}\n   N  \\geq \\left(\\frac{4L(f(y_0)-f_\\star)}{ \\epsilon}\\right)^{1/2}\n \\end{align*}\nmakes  $\\|\\nabla f(y_N) \\|^2 \\leq \\mathcal{O}(1/N^2)$.  \n\n**Q2) Why $ U\\geq 0$ is equivalent to (C1)?**\n\nThe only term depends on $(x_0, x_\\star)$ in $\\mathbf{U}$ is $\\frac{L}{2}\\left \\| x_0-x_{\\star} + \\sum_{i=0}^{N}\\frac{u_i-u_{i-1}}{L}\\nabla f(x_i)\\right \\|^2$. Note that (C1) is saying about $(\\forall x_0, x_\\star, \\nabla f(x_0),\\dots, \\nabla f(x_N))$. Next, since $x_0,x_{\\star}$ can have any value, we can take $x_0-x_{\\star}=-\\sum_{i=0}^{N}\\frac{u_i-u_{i-1}}{L}\\nabla f(x_i)$. In this case, $ U_N - u_N ( f(x_N) - f_\\star ) = \\mathbf{U} $ Thus it gives the fact that (C1) s equivalent to $\\Big[ \\mathbf{U} \\geq 0, \\quad \\left(\\forall\\, \\nabla f(x_0),\\dots,\\nabla f(x_N)  \\in \\mathbb{R}^d \\right) \\Big]$. You can see the same argument in line 406 of the supplementary material. \n\nThis proof technique is mainly adapted from PEP(Performance Estimation Programming) literature, which provides the necessary and sufficient conditions that $(x_i, \\nabla f(x_i), f(x_i))$ can be interpolated with a $L$-smooth function. $(\\forall x_0, x_\\star, \\nabla f(x_0),\\dots, \\nabla f(x_N))$ part can be understood with the same perspective of the PEP analysis.\n\n\n\n**References**\n\n(1) : Z. Allen-Zhu. How to make the gradients small stochastically: Even faster convex and noncon-\nvex SGD. NeurIPS, 2018.\n\n(2) : D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex functions.\nSIAM Journal on Optimization, 29(1):207–239, 2019.\n\n(3) : J. Diakonikolas and P. Wang. Potential function-based framework for making the gradients\nsmall in convex and min-max optimization. SIAM Journal on Optimization, 32(3):1668–1697,\n2021.\n\n(4) : J. Lee, C. Park, and E. K. Ryu. A geometric structure of acceleration and its role in making\ngradients small fast. NeurIPS, 2021.\n\n(5) : Y. Nesterov, A. Gasnikov, S. Guminov, and P. Dvurechensky. Primal–dual accelerated gradient\nmethods with small-dimensional relaxation oracle. Optimization Methods and Software, pages\n1–38, 2020.\n\n(6) : C. Park and E. K. Ryu. Optimal first-order algorithms as a function of inequalities.\narXiv:2110.11035, 2021.\n\n(7) : K. Zhou, L. Tian, A. M.-C. So, and J. Cheng. Practical schemes for finding near-stationary\npoints of convex finite-sums. AISTATS, 2022."}, {"review_id": "eOWH1Y1k3K", "reviewer": "Reviewer_x8JQ", "summary": "This paper introduces novel notion of H-duality, which shows unexpected connection between time-reversed coefficients of methods and optimality w.r.t. gradient norm or function value.", "questions": "Notion is based on phrases like \"efficiently reduce function values/gradient magnitude\", which is not very clear in part \"efficiently\". Any method which optimises function value optimises gradient norm as well for convex functions, so word \"efficiently\" requires formalisation. I guess, it is connected with optimality w.r.t. different measures of convergence. If it's possible to develop it better, it would be good.", "limitations": "Everything is okay", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Very inspiring work, introduced notion is quite curious. I think that such an idea will be interesting to most of readers. The contribution of this paper is primarily theoretical which could make it \"intermediate\" for those readers who work in practical field of ML, but I believe that introduced notions can help theorists to develop the theory of optimisation taking into account more important details, which will impact on practice in the end. Especially such abstract works can affect theory the most, if the introduced notion is really helpful and fundamental, which can be confirmed only by the time, but I see it necessary to present such ideas to community to \"test\" them. Idea seems to be novel: my experience doesn't tell me attempts to introduced such a parallels in methods constructions in terms of duality notion.", "weaknesses": "I do not see significant weaknesses. Proof presented in the paper are correct, but assumption are expressful enough to make proofs simple in cases where they are satisfied. In the best case, more detailed development of these concepts should lead to simplification and weakening of assumptions by showing from when do they arise in many cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We're grateful for your thorough evaluation and the perceptive observations you've shared. These will certainly assist us in enhancing our paper even more. I'd like to address a few matters in response to your questions.\n\n\n**Q1) Clarification on the phrase \"efficiently reduce function values/gradient magnitude\"**\n\n\nIn this context, the term 'efficiently' primarily pertains to the notion of acceleration or achieving a significant convergence rate. However, it's important to note that Theorem 1 does not depend on the rate of convergence; it holds for every $H$ and $u_i$s. The use of the term 'efficiently minimizing' was intended to accommodate the general interest in acceleration methods.\n\n**Q2) Optimality with respect to Different measures**\n\nYou are absolutely correct in associating H-duality with optimality. Indeed, (OGM) can be considered the exact optimal method with respect to function value measurement under an initial distance constraint, while (OGM-G) is widely presumed to be the exact optimal method with respect to gradient norm measurement under an initial function value gap constraint. It's worth noting that these two methods share the same convergence rate factor, $1/\\theta_N^2$, as mentioned in lines 103 and 105. Consequently, they both \"share\" the same convergence rate, which contributes to their efficiency.\n\nSimilarly, for the notion of $\\mathcal{A}^\\star$-optimality, which concerns the optimal method under a certain constrained sense, we have demonstrated that several pairs of methods exhibit interesting properties: a method is $\\mathcal{A}^\\star$-optimal with respect to function value measures if and only if its H-dual is $\\mathcal{A}^\\star$-optimal with respect to gradient norm measures. Moreover, the convergence rates of these methods also share the same factor, due to our main theorem (Theorem 1). For more in-depth insights into this topic, please refer to the last paragraph of Section 2.5, where we resolve conjectures regarding $\\mathcal{A}^\\star$-optimality [(1), (2)].\n\n**References**\n\n(1) D. Kim and J. A. Fessler. Optimizing the efficiency of first-order methods for decreasing\nthe gradient of smooth convex functions. Journal of Optimization Theory and Applications,\n188(1):192–219, 2021\n\n(2) C. Park and E. K. Ryu. Optimal first-order algorithms as a function of inequalities.\narXiv:2110.11035, 2021."}]

Author rebuttal:

# Common Response

We would like to express our sincere appreciation to the reviewers for their time and constructive criticism.

Several reviewers (Reviewers 8tCz, Fq7n, and x8JQ) strongly appreciated the theoretical novelty and value of our paper, acknowledging the innovative aspects of H-duality. (With reviewer x8JQ providing a rating of 9!)


On the other hand, Reviewers 2PtR and JyDy had concerns about the immediate practical applicability of our work, with Reviewer 2PtR pointing out that the convexity and $L$-smoothness assumptions limit the applicability of the analysis in practical machine learning. Indeed, the primary value of our work lies in its theoretical novelty. In our view, however, H-duality is an unexpected discovery that may enrich our understanding of accelerated optimization methods and has the potential to have a strong practical downstream impact. We kindly ask the reviewers to consider the potential downstream value of our theoretical results. 


Meta-review: Overall the reviewers viewed the paper positively. There was some discussion over whether the work fits in the scope of NeurIPS, but ultimately it does apply to problems that have historically arised in ML.
Decision: Accept (poster)