A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
Authors: Jongmin Lee
Chanwoo Park
Ernest K. Ryu
Venue: NeurIPS 2021 Poster (2021)
Keywords: acceleration
convex optimization
Euclidean geometry
gradient norm
small gradients
making gradients small
composite optimization
OGM
FISTA
OGM-G
potential function-based
Lyapunov analysis
complexity bounds

Abstract: Since Nesterov's seminal 1983 work, many accelerated first-order optimization methods have been proposed, but their analyses lacks a common unifying structure. In this work, we identify a geometric structure satisfied by a wide range of first-order accelerated methods. Using this geometric insight, we present several novel generalizations of accelerated methods. Most interesting among them is a method that reduces the squared gradient norm with $\mathcal{O}(1/K^4)$ rate in the prox-grad setup, faster than the $\mathcal{O}(1/K^3)$ rates of Nesterov's FGM or Kim and Fessler's FPGM-m.

A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
Jongmin Lee Seoul National University dlwhd2000@ snu.ac.kr
Chanwoo Park Seoul National University chanwoo.pare smu.ac.kr
Ernest K. Ryu Seoul National University ernestryu @ snu.ac.kr
Abstract
Since Nesterov's seminal 1983 work, many accelerated first-order optimization methods have been proposed, but their analyses lacks common unifying structure. In this work, we identify a geometric structure satisfied by a wide range of first- order accelerated methods. Using this geometric insight, present several novel generalizations of accelerated methods. Most interesting among them is method that reduces the squared gradient norm with OLI/K*) rate in the prox-grad setup, faster than the (11/K)) rates of Nesterov's 's FGM or Kim and Fessler's FPGM-m.
Introduction
Since Nesterov's ' seminal 1983 work [57], accelerated methods in optimization have been widely used in large-scale optimization and machine learning. However, the many accelerated methods have been developed and analyzed with disparate techniques, without unified framework.
In this work, identify geometric structures, which call the parallel and collinear structures, satisfied by a wide range of gradient- and prox-based accelerated methods including: Nesterov's
FGM (57], OGM (7). OGM-G [47] Nesterov's FGM in the strongly convex setup (SC-FGM) 660
(2.2.22) SC-OGM (63] TMM 788,, non-stationary SC-FGM [99 $4.5), ITEM (73), geometric
descent 133. Güler's first and second accelerated proximal methods (37, and FISTA (II] Using the
insight provided by these geometric structures, we present several novel generalizations of accelerated methods.
Among these novel generalizations, the most interesting is FISTA-G, which reduces the squared gradient norm with O11/K*) rate when combined with FISTA in the prox-grat moxx-rrad (composite mini- mization) setup. The rate optimal as it matches the ((1/K*) complexity lower bound [55] [6 and is faster than the O / K3 rates achieved by of Nesterov's AGM 46 69 in the smooth convex setup or Kim and Fessler's 's FPGM-m (45 in the prox-grad setup.
1.1 Preliminaries and notations
For L > f: f: R" + R is L-smooth if f is differentiable and
[)(x)~ - s L|| yll Vx, y R
For μ > 0. g: R R (xx) μ-stroogly convex g(x) (n/2) | respectively denote the smoothness and strong convexity parameters of f. Write the gradient steps with stepsizes 1/L and 1/μ as
convex. Let L and Jr
(x)),
++ = Vz()).
For À > 0, the proximal operator [53 62
Proxag
12 Rd is defined as
r = Prox
(x) = arg min g(v) + y x0
vER"
2X
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

When g is closed, convex, and proper [65], the proximal operator is well-defined i.e., the arg min exists and is unique [52]. Define the prox-grad step as
arg min yER
(V)(), - +) + 2 11 x1
If g 0, then x: = xt. If f = 0 and 1/2 = I, then x = Furthermore, write
:=F(z))==L<+">> = x), V1/20(>)= = - 1 1 -2). x).
12 is a subgradient of convex function g at if g(z) + (u. z) S g
YyE
Subdifferential of g at x, denoted (z(z). is the set of subgradients of g at x. Throughout this paper, we consider the problem
minimize =E8"
F(x) = f(x) + 9(x),
(P)
where f: 12" + R is convex and L-smooth and g: IR + R U {oc} is closed, convex, and proper. We say we are in the smooth convex setup if f * and g= = the proximal-point setup if f 0 and & O, and the prox-grad setup if f & O and * O. Write f.. 9x. and F. to respectively denote the infima of f. g. and F. We also informally assume Prox2g efficient to evaluate 17
1.2
Prior works
In convex optimization and machine learning, the classical goal of algorithms is to reduce the function value efficiently. In the smooth convex setup, Nesterov's celebrated fast gradient method (FGM) [57] achieves an accelerated rate, and the optimized gradient method (OGM) [4 improves this rate by factor of 2, which is in fact exactly optimal [27]. In the smooth strongly convex setup, the strongly convex fast gradient method (SC-FGM) 60 (2.2.22) strongly convex optimized gradient method (SC-OGM) (63) and non-stationary SC-FGM 19 $4.5] achieves an accelerated rate, and the triple momentum method (TMM) (78 and information theoretic exact method (ITEM) (73) achieve exact optimal rates 28 In the proximal-point setup, there are Güller's first and second accelerated proximal
methods 37 There are also other variants of accelerated proximal methods [51 49 39 (7]..
The study of algorithms for reducing the gradient magnitude, which can help us understand non- convex optimization better and design faster non-convex machine learning algorithms, was ini- tiated by Nesterov (58) For smooth nonconvex minimization, gradient descent (GD) achieves (ff(z)) - f-) (K) rate [44 Proposition 3. In the smooth convex setup, combining iterations of FGM with K iterations of GD achieves (1 x. |////KKKK)) rate (58). Adding strongly convex regularization and then using SC-FGM achieves O(1 - x;, x.,1 122/K2) rate, where Ô ignores logarith- mie factors (58). Finally, OGM-G [47 achieved ((f(zo) f.) /K²) rate and O(I 2. 22,12//3 ()
matches rate is achieved by combining FGM with OGM-G [61] Remark 2.1]. This rate is optimal
the [0 x, /1²/K*) lower bound [55 56) Making gradients small have also been studied in the for composite problems with strong convexity and
setup with stochastic gradients
33
non non-Euclidean norms 23 and for
saddle-pond point problems 22
24
80
In the prox-grad setup, iterative shrinkage-threshoolingg algorithm (ISTA) 12
64
achieves 20
[8]
O11 - x., l=/////K) rate on function-value suboptimality and fast iterative
al-
gorithm (FISTA) [T] accelerates this rate to
O 250 12 22). On the squared gradient magnitude,
FPGM-m achieves OiI - 12, 32/33) rate
The performance estimation problem (PEP) is computer-assister proof methodology based on semidefinite programming [29] 775 74 Extensions and variations of the PEP have been utilized to obtain analyses and algorithms that would be difficult obtain without the assistance of computers
67
72
10
76
21
36, 50
26
43
In particular, OGM 29 44 OGM-G [7), and ITEM [73] were
obtained with the PEP. Integral quadratic constraints is a related computer-assisted approach based
on control-theoretie ideas 48 38
31).
A Lyapunov analysis constructs nonincreasing quantity, and many modern analyses of accelerated
first-order methods are based on this technique [I]] 70 72
63 In fact, Nesterov's
original presentation of FGM was Lyapunov analysis [57]

---

Finally, we mention some closely related prior work. The scaled relative graph (SRG) analyzes optimization algorithms via Euclidean geometry 666
40 68]. but the SRG has not been used to coupling between gradient descent and mirror descent to efficiently reduce function values. Geometric descent [33 [2]42] is an accelerated algorithm designed expressly based on geometric principles, and quadratic averaging [30] is an equivalent algorithm with an alternate interpretation. The method of similar triangles (MST) generalizes FGM with geometric notions [32] (60) T. The parallel and collinear structures of this work, in our view, expand these prior notions and concretely articulate ideas that had been utilized implicitly. In particular, the prior interpretations, is, are insufficient for analyzing OGM-G and deriving our newly proposed method FISTA-G In Section H of the appendix, we further discuss the relationship of our contributions with these prior works.
analyze accelerated methods. Linear coupling 4 S interprets acceleration
1.3 Contribution
This paper presents two major contributions, conceptual and concrete. The first is the identification of the parallel and collinear geometric structures, which are observed in a wide variety of accelerated first-order methods. This geometric structure provides us with valuable insight into the mechanism of acceleration and enables us to obtain results that would be otherwise difficult discover, including FISTA-G. The second major contribution is the novel method FISTA-G and FISTA+FISTA-G. To the best of our knowledge, FISTA+FISTA G is the first method to achieve the rate OL1/K+) on the squared gradient norm the prox-gret grad setup.
In addition, we use the geometric structures to find G-FISTA-G, G-FGM-G, G-Güler-G, Proximal- TMM, and Proximal-ITEM, novel variants of accelerated first-order methods, and present them as minor contributions. (G-FGM-G is the abbreviation for Generalized-FGMM-n reducing Gradients).)
Making gradients small at rate Ol1/K*) in the prox-grad setup
In this section, we present novel method FISTA-G, which reduces the squared gradient norm with OLL/K*) rate when combined with FISTA the prox-grad setup. Our analysis uses a novel and unusual Lyapunov function, whose discovery crucially relied on the geometric insights presented later in Section 3 Here, we provide self-contained analysis that uses, but does not explain this Lyapunov function.
Smooth convex setup.
Kim and Fessler's (OGM-G)
[7 is
Ik+1 = I& + (0s 12 -
20
0g(20) - 1) (xt -xx-1) +
(xt - -xk) for 1: = 0, 0,....., K
20, - 1
1+V1-18 for k 1,2..... ..... K 1, and 0g 2 Note, K is the total number of iterations and 0g = O(K), so 0 is function of K. OGM-G is the first method to achieve the accelerated rate (((f(zo) - f.)/ on the squared gradient norm, and the method was originally obtained through computer-assisted methodology. However, the computer-generatie analysis is verifiable but arguably difficult to understand.
1+ 1+86
where x_ = Tu, 0K 1, 0₂ =
We characterize the convergence of OGM-G with the following novel Lyapunov function
1 U 0h
|| + f(x)) - f(Ix) (Vf(*)), atti))
[Vf(())
2L
2L
L
(2k
1: xx)
for k: = 1,2...., K,
0
k
where 2k = 2%
(0, - 1)²
(rk
x 1) for ..,,..., K, (note 2Ø =KK through the steps
20
1 7, [ UK s UK-1 < S SU
2 0g 2T. [V](<x)]] + - -s(xx)
Section 3 exxlains the geometric insights behind the discovery of this Lyapunov function and the proof that {(x nonincreasing. As related work, Diakonikolas and Wang (24) presented a human-underssanddabl analysis of OGM-G, but their analysis is not Lyapunov analysis since (as they acknowledge) they do not establish a nonincreasing quantity. In any case, our main contribution of this section is the following generalization of the method and analysis to the prox-grad setup.
3

---

2.1 Accelerated (((((z)) - F.)/K²) rate with FISTA-G
We now present the novel method (FISTA-G):
Tk+1 = Ik Pk+1 - Pkk+2
(x
x-1))
for =o 0.1,..., 1,
Pk Pk++
where v= 1 = To. Pk+1 0, KK 1, and
0h+2 - Pk+1Pk42 + 24 + (ph+1 - (k+22) V Pbt2 +3
Ph
for k: = -,,0, K-1.
Pk++ + Pk+2
Note that K is the total number of iterations.
Theorem 1. Consider (P. FISTA-G's final iterate zK exhibits the rate
min [a 2 [(F(Ex) (K 2)2 (F(xo) - F.).
264L
We clarify that min =
min [aln [|//|
n E (F())) for RR..
Proof outline. Define
20.
P6- 2 for k = =0,1,... and
9x+1
F4 PP+1
Uk (pk-1 - )xx)²
2
+F((t) ((n)
||
F(* (r. 26 =
2L
+
zk
2k
k-1
xk)
for k: = 0, 1, , K.
6pk
(Note that 2x = kK.) We can show that {U K k=0 is nonincreasing. Then
1
(((())
UK S
2
1
(z)())) ||" +((aa)) F(x
2L
(0-1 - 20)
21
26-1
33L
(F(zo) - F)x -
(F(xo) - -F),
(0-1 00))
(K
2
|
where we used
1 21
V F
< F(ro) - F(x # stated as Lemma 9 in the appendix.
The complete proof is presented in Section B of the appendix. In fact, FISTA-G is the best instance within the family of methods G-FISTA-G presented in Section[EJof the appendix, in the sense that FISTA-G is the instance for which could obtain the smallest constant in the bound.
2.2 Accelerated O(I x.11. /1² rate with FISTA+FISTA-G
Define the method (FISTA FISTA-+ -G) as: from a starting point xp run iterations FISTA [I] and then from the output of FISTA start FISTA-G and run K iterations. (2K iterations total.) We denote the final iterate of this method as ø2K.
Corollary 1. Consider P Assume F has minimizer x., FISTA--sS final iterate d2K exhibits the rate
min OF
2 11 < < | F(2K)) (1= 2K
||?
< (K + 2)
5281
||x0 - x=.12.
Proof. Combining the F( F. < 21 x. with Theorem [
/I 2)² rate of FISTA II Theorem 4.4]
we get the rate F
min ( 44 4
528L2 (K 2)2 (F(x*) - F.) (K + 2)
264L
||ao -x.12
OOtaining an iterate कx with || F(Tx)l1 requires K (6L(
iterations for FISTA-G.
and K > 2 1321 20
iterations for FISTA+FISTA-G, where K is positive even integer.

---

FISTA+FISTA- G was inspired by the FGM+OGM-G method, which has O[ x=112/K*) rate on the squared gradient norm in the smooth convex setup
61 Remark 2.1]. Nesterov FGM by itself
only achieves (1 I=1 /K33 ) rate 75
71
46
69
24 In the prox-grad setup. FPGM-m [S
held the prior state-of-the-ane rate of O Fo Z+
Our O[ 2+112/ /1ll///))) rate matches the known complexity lower bound 55 56 and therefore is optimal in the case O.
/
3 Parallel structure for the convex setup
In this section, we present the parallel structure, a geometric structure observed in a wide range of accelerated first-order methods. We then utilize the parallel structure obtain novel variants of accelerated first-order methods and, in particular, obtain the Lyapunov analysis presented Section 2
3.1
Parallel structure of acceleration
Nesterov's (FGM)
57 has the form:
Ik+1 I + 0₂ 1
(5 x7
0x+1
2 I2 + (0x 1)(xx
x
for k 0, 1,.....
where xi, := Io. To 20. Oo 1, and 0x+1 1+ 1+ for k 0, l,... The zı-iterates are
known as the auxiliary sequence, and they play key role in the Lyapunov analysis of FGM (57].
Figure (left) depicts 1 2k. xx. I 2k. and 2x+1- These points in IR" lie on a 2D-plane, which we call the plane of iteration. Observe that the line segments representing at Ix. and 2k+1 2k
parallel. (We prove observations [and in Section of the appendix.)
Observation 1. In FGM, r
and 2k+1 24 are paralle
26
2k
2
2
0k++1
Zk-1
2k
Zi++-
Figure 1: Plane of iteration of FGM (left), OGM (middle), and FISTA-G (right)
Drori, Teboulle, Kim, and Fessler's (OGM)
29 has the form:
0k+1 x 02
(xt
+
P (at I*k)
8k+1
24 3t + (0s
1)
for t: 0, 0, K 1,
To, 9 = 1, 0k+1 1+ 11440 for k 0, 1,.,,,,, K 1, and 0x To, 20
where xt
11+80 OGM improves upon the rate of FGM [4]. Interestingly, OGM also exhibits a similar geometric structure as depicted Figure (middle), and the auxiliary sequence, the 25 ze-iterates, plays similar role in the Lyapunov analysis 633
Observation 2. In OGM, at Ix and že+1 2s are parallel.
We refer to this geometric structure as the parallel structure. Given an algorithm expressed with momentum and correction terms, one can define the zy-iterates to exhibit the parallel structure:
Iy = c.. + (1 - (1ckk)as cx)=K
Fo+1 = + ax+ (xt - + bR+t (st xx)
žk-1 = 2μ ds V f(x))
We define "parallel" to include the degenerate case 2t 24 2e+1 2t 0.
5

---

where ax++1 b&+1, Ck2 and dę satisfy an appropriate relationship as shown in Section B of the appendix. The zg-iterates of FGM and OGM have this form. The parallel structure also holds for Güler's s accelerated methods (37 for the proximal-point setup and FISTA [1] for the prox-grad setup with analogous definitions of the zy-iterates. The table of Section A.1 of the appendix presents the precise forms.
3.2 Parallel structure for OGM-G and FISTA-G
We equivalently write (OGM-G) as
0
I k- + (1-
0
Zk 02
0%
Ak
2k+1 = 2k
f(z))
for 1,2,...,
L
1t 1144466 for h: 1, 1,2.... K,
where 20 To.
20
t1 v (xr)), 0x+1 O. and O2 2L
and On- = 1+ 1+800
The key point is that the auxiliary 2k- zx-sequence defined to exhibit the parallel structure. As comparison. [47 Equation (43) provides a different auxiliary sequence for OGM-G that does not exhibit the parallel structure, but this sequence does not lead to a Lyapunov analysis.
2
Here, we show how the Lyapunov function U3 is obtained from the parallel structure of OGM-G. For k 2 1, combine the cocoercivity inequalities between (I x2,) and (Zk, xx) to get
0 2
1
((0041)- f(())
- mx) + [ V (x=)))
1
1
2L
1
(2)
1
f( - (V.(( (f(oN)
xk)
1
[Vf(xx) {x(xx))
02+1
2L
1
[V((x))) )1 + 2L
V [ + f(xx+)) f(xx) -(xx)=))-(lx)((((((((-- (V)((x+)), xx.
2L
1
1 +
2T. [(x())) + +(xx)) - -((x)) - (VS(x)), - =
1
2T.
(Tx))
2x²0t
(0x41 -0x²) }kk))
With the following geometric arguments, we analyze the term T and conclude 0 2 UR41 Uk- Let E R" be the (orthogonal) projection of æ onto the plane iteration. For u, v E R", define
wt v u. Then
T (
I (0 2 - 0g² 2)t0
-0p2)tzz + 00%
2x- 2xxx 1
2k
( (0 0F²))((0 (lent] =
Jaak + xuat)
+ 0%² 2 t o xxai))
(
oxot (0T4 0 2)zzk+1 - (0,.1 0% ((x - 1) 1)
(0 0- Jंズt + (20g 1) 1)0 1+ T ने + - -
(iv)
F 7 (0 0%² tzu+i + 0
2 (0s 1) - )
xx. 2x+1 - 2k. t +
+ 0-4
1tz4+1 - t2k 24
k+11
0 4
2k+1 t 2k+1
z/ + 0xx
(
x 1 24 IT
k++
where (i) follows from the definition of and the fact that we can replace a with 1, the projection of ZK onto the plane of iteration, without affecting the inner products, (ii) from vector addition,

---

(iii) from the fact that 7x and Zy-zg are parallel and their lengths satisty 2x²x+1
120,
the identity (0 (0s, 1) 0x²² and (20, 1)0 (0k+1 0r²)) o T4 (iv) from
and - 1 and 2h are parallel and their lengths satisfy 2 Lh
Ox (0 1)_
(v) from distributing the product and substituting u = (0, (x #x41 )x=E) (which
follows from 2 IzZl 2x22+1 2x 2k+1 DEEK + 0g 22Z Iu 2x+1) into the first term and k 0% 22=22=++ 0% tøk+1 tzk into the second term, and the identity (0
0x (0p - -1)-1 - (0x 1) 0r = 1 and (vi) from cancelling out the cross terms, using
0e 4 -k- 2h 0r ++ Th and by replacing with æ in the inner products. At this point, the proof is essentially done. The remaining few details of the analysis of OGM-G are presented in Section of the appendix.
This geometric reasoning naturally extends to the prox-grace setup. Using analogous Lyapunov functions and proof structure, we obtain convergence rates of FISTA-G and the other generalizations presented Section 3.3 Figure (right) illustrates the parallel structure of FISTA-G with the ze-iterates defined as in Section A.2 of the appendix.
3.3 Other generalizations
Using the parallel structure, we find several novel variants of accelerated first-order methods: G-FISTA-G, G-FGM-G, and G-Güler-G. We discuss them in detail in Sections A.2 and of the appendix. Here, we briefly highlight the two special cases that we found most interesting.
We present (FGM-G) for the smooth convex setup:
#k++ 2
F++
(at =
for k = 0,1,..... K 1,
Pk
Pk+1
K+1 is the same the ( K+1 of FISTAGG. We view FGM-G as where xt, Zo and { k==0 special case of FISTA-G with g = or as a special case of G-FGM-G. In any case, FGM-G's final iterate zk exhibits the rate
66L
[ <
(f(x0) - s+).
(K + 2)
OGM-G uses the "correction term"
28 - xx) and the "first-step modification", i.c., 0g is 20, -1
defined separately from (0x) (0] FGM-G demonstrates that these features are not necessary for achieving the accelerated ((f(())) f.)/ k?) rate. However, the simplification does come the cost of worse constant.
We present (Güler-G) for the proximal-point setup:
x++1
(1--
0
k++1
Th
04
" a6 +
04
2k
- 02 V 11/2((TK))
for 1 = 1, K,
0, and 0g 1+ 1 for 0, 1,..... K.
where 20 Fo. 0k+1
2
Theorem 2. Consider (P) with = 0. Güiler-G's final iterate æ exhibits the rate
V |
4
*(K (x( 9.)..
Furthermore assume has a minimizer I. and define the method point Te run K iterations Güiler second method (37] and then from the output start Güler-G and run K iterations. Then the final iterate D2K exhibits the rate
as: from a starting
X²(K 2) ||z0
x 12,1
7

---

Collinear structure for the strongly convex setup
In this section, we present the collinear structure, geometric structure observed in wide range of accelerated first-order methods for the strongly convex setup. We then utilize this structure obtain novel variants of accelerated first-order methods. We specifically consider two strongly convex setups: T-smooth and v-rrrongly convex and = in Section while f and g j--strongly convex in Section
4.1 Collinear structure
Nesterov's (SC-FGM) has the form:
Vk-
2k+1 z VK 1
(at =x
2k+1 2k+1 VK(F++1 2
for ls 0, 1,..,
where x and x := zg. Again, the auxiliary 2 iterates reveal the geometric structure and play key role in the Lyapunov analysis (9] $5.5]. Figure (left) depicts - The z Jy ++ Uh+1 Zk- and #k+1. These points in I on 2D-plane, which we again call the plane iteration. Note that Fk, #,+1, and ii are collinear, i.e., there is line in I2" intersecting the three points. (We prove
observations 3 and 4 in Section of the appendix.)
Observation 3. In SC-FGM, 2k. 2k+1, and ++ are collinea
35
2k
2k++1
3%
F
2%
3h+1
2h+1
2k+11
Zk++1
2
000
Figure 2: Plane of iteration of SC-FGM (left), TMM (middle), and Proxmal-TMM (right)
Van Scoy, Freeman, and Lynch's (TMM) 78 which improves upon SC-FGM, has the form:
0b+1 = 2 + (Vn 1)²
(x xx + VK (at - Ik)
Vn(v 1)
VK
VK
2k+1 = 2b+1 +
(#k+1 xx for h = 0, 0,
2
where =-, To and L TMM also exhibits similar geometric structure depicted in Figure
(middle), and the zæ-iterates play similar role in the Lyapunov analysis [9 Theorem 4.19].
Observation TMM, Zıs 1 and x are collinear:
We refer to this geometric structure the collinear structure. Given an algorithm expressed with momentum and correction terms, one can define the zı-iterates to exhibit the collinear structure:
C2 + cx)=
Th+1 I au (x = + bu xR)
d ++ + (1 dx) Zk
24++1
where 0g, be, Ck. and de satisfy an appropriate relationship as shown in Section B of the appendix. The collinear structure also holds for non non-stationary SC-FGM [19 84.5], SC-OGM 63 ITEM 73 and geometric descent [3] 30]. The table of Section A. presents the precise forms.
We define "collinear" include the degenerate
2k+1
x

---

4.2
Collinear to parallel structure as
We briefly discuss how the parallel structure arises as the limit of the collinear structure as μ -> When = 0, the collinear structure is undefined, as 2x 2 f is undefined. In the limit + 0, however, =xx diverges to point of infinity in the plane of iteration, and the collinear
structure becomes the parallel structure since 2g. 1 and 2g ++ are collinear and Vg. and oy are collinear.
There are two possible scenarios. In the first degenerate case, 24 and 24+1 diverges to infinity. This is the case with SC-FGM, SC-OGM, and TMM. In the second scenario, 2 and 26+11 stay bounded and ak 2g and # become parallel. This is the case with non-stationary SC-FGM and ITEM, which respectively converge to FGM and OGM.
2
T
J
1k++
3k
R-30
21++11
2x+1
Zk++1
Figure 3: Collinear to parallel structure as + (ITEM (left) + OGM (right))
4.3
Other generalizations
Using the collinear structure, we find two novel methods: Proximal- -MM and Proximal-ITEM. These methods can be viewed as proximal versions of TMM 77 and ITEM 73], and they improve upon the accelerated proximal point method [19 10). We provide the proofs in Section
We present (Proximal-TMMe TMMM for the strongly convex proximal point setup:
1 Vg
(1
1 1- /4
Jk + V
Zk
1
V4
2k+1 ya + + 7
0, 1, for
where q =
Ap Au+1 3k
Ik (A (A+ (I)) and x-_ = T0 = 20-
Theorem 3. Consider P Assume is p-strongly convex, g has a minimizer x., and f 0. Proximal-TMMN zg-iterates exhibits the rate
2 x. < (1 vq)= (g(#n) - g(xx)).
We present (Proximal-ITEM) for the strongly convex proximal-pooi setup:
n + 7x))) = qóx22
00 + (1 - qox)zx
for k = 0, 0,.....
where
Ape Ap+1 2x
Jk (2 1) (I/A0(#R)) x²1
10 20. An 0, A
(14-))Ax+2
(1+ (1+1221111111111 (1+ 7kk = (1-g)At-1 and 6z = (1-9)² (4) for = 0, 0,1..... 2(1-4-9AL)
A
(1-9)²
Theorem 4. Consider Assume g is u-strongly convex, g has minimizer Ea, and Proximal-ITIe -ITM'ss 's z iterates exhibits the rate
x.1 (1 v 2h
||
/ + 1: 1.11
WWe say algorithm is stationary if the parameters depend the iteration 35

---

Experiments
We consider the compressed sensing 25 15
problems
minimize ZEX
|| - b1l2 + X | 1
minimize ZER"
||xx - b1l 1|| ||
where À 0, -II is the mnoom, || |
nuclear norm, and the data E IR=x and b E R are generated synthetically. We describe the data generation in Section the appendix. Figure presents the comparison of ISTA, FISTA, FPGM-m, FISTA, FISTA-G, and FISTA+FISTA-G. The results indicate that FISTA+FIST -I- is indeed the most effective at reducing the gradient magnitude.
10
10-
110 Fos
10-4
10-2
10-4
ISTA
10-9
ISTA
10-12
FPGM-TI
FISTA
10-8
FPGM-m
FISTA
10-16
FISTA-G
10-11
FISTA-G
FISTA+FISTA-G
FISTA+FISTA-G
10a
10
10
10
lteration count (K)
Iteration count (K)
Figure 4: Minimizing the gradient magnitude for compressed sensing problems with & regularizer (left) and nuclear norm regularizer (right).
Conclusion
In this work, identified geometric structures of accelerated first-order methods and utilized them to find novel variants. Specifically, we found that appropriate auxiliary zg-iterates reveal parallel and collinear structures and that these iterates crucial for the Lyapunov analyses. Among the new methods, we highlight FISTA-G, which, combined with FISTA, achieves a O - x, 12 K*) rate on the squared gradient norm in the prox-grad setup.
FISTA-G and FISTA+FISTA-G have last-iterate rates, i.e., the bound is on I )12 rather than minkk=o..... K I/ F(xx)) but are not anytime algorithms,, i.e., the total iteration count K must known advance and intermediate iterates have no guarantees. In contrast, the FGM achieves acceleration function-value suboptimality with last-iterate rate as anytime algorithm. Interestingly, all known algorithms for the smooth convex setup or the prox-grad setup with rate 011 //////////// 3²3) or better do not have this property. For example, OGM+OGM-O G is not anytime algorithm but has last-iterate bound, while FGM is an anytime algorithm with a best- iteratee not a last- iterate, bound. In the prox-grad setup, FPGM-m 45 is not anytime algorithm but has last-iterate rate. Whether an anytime algorithm can achieve a last-iterate rate O 2 K3) or better is open problem. On related note, Diakonikolas and Wang conjecture that ((f((r)) f-)/ k?) rate is impossible to achieve with an anytime algorithm in the smooth convex setup (24] Conjecture 1].
Acknowledgments and Disclosure of Funding
JL and EKR were supported by the National Research Foundation of Korea (NRF) Grant funded by the Korean Govermment (MSIP) [No. 1E20RIFFAAA0110277777 the National Research Foundation of Korea (NRF) Grant funded by the Korean Government (MSIP) [No. 2017R1A5A1015666, and by the Samsung Science and Technology Foundation (Project Number supported by an undergraduate research internship in the first half of the 2021 Seoul National University College of Natural Sciences. We thank Jaewook Suh, Jisun Park, and TaeHo Yoon for providing valuable feedback. We also thank anonymous reviewers for giving thoughtful comments.
CP was
10

---

References
[1] K. Ahn and S. Sra. From Nesterov's estimate sequence to Riemannian acceleration. COLT, 2020.
[2] Z.. Allen-Zhu. How to make the gradients small stochastically: Even faster convex and nonconvex SGD. NeurlPS, 2018.
[3] Z. Allen-Zhu and Y. Li. NEON2: Finding local minima via first-order oracles. NeurIPS, 2018.
[4] Z. Allen-Zhu and L. Orecchia. Linear coupling: An ultimate unification gradient and mirror descent. ITCS, 2017.
[5] Z. Allen- Z. Qu, Richtárik, and Yuan. Even faster accelerated coordinate descent using non-uniform sampling. ICML, 2016.
[6] J.-F. Aujol and C. Dossal. Optimal rate of convergence of an ODE associated to the fast gradient descent schemes for b > 0. HAL Archives Ouvertes, 2017.
[7] J.-F. Aujol, C. Dossal, G. Fort, and É. Moulines. Rates of convergence of perturbed FISTA-based algorithms. HAL Archives Ouvertes, 2019.
[8] J.-F. Aujol, C. Dossal, and A. Rondepierre. Optimal convergence rates for Nesterov acceleration. SIAM Journal on Optimization, 3934)333 2019.
[9] N. Bansal and A. Gupta. dotential-functiinn proofs for gradient methods. Theory of Computing, 15-4), 2019.
[10] M. Barré, Taylor, and Bach. Principled analyses and design of first-order methods with inexact proximal operators. arXiv preprint arXiv:2006.0604) 2020.
[11] A. Beck and M. Teboulle. A fast iterative shrinkage-thressoldin algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183-202, 2009.
[12] R. E. Bruck. On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators Hilbert space. Journal of Mathematical Analysis and Applications, 61(1:11991164 1977.
[13] S. Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-357, 2015.
[14] E. Candès, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 22(2):489-500 2006.
[15] E. J. Candès and T. Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions Information Theory, 52(12):5406-55 -4266,5555554- 2006.
[16] S. Chen, S. Ma, and W. Liu. Geometric descent method for convex composite minimization. NeurlPS, 2017.
[17] L. Combettes and J.-C. Pesquet. Proximal splitting methods in signal processing. In H. H. Bauschke, R. S. Burachik, P. L. Combettes, Elser, D. R. Luke, and H. Wolkowicz, editors, Fixed-Poin Algorithms for Inverse Problems in Science and Engineering, pages 185-212. 2011.
[18] L. Combettes and V. R. Wajs. Signal recovery by proximal forward-backward splitting. Multiscale Modeling and Simulation, ((4)):168-122)) 2005.
[19] A. d' d'Appemoon,, D. Scieur, and A. Taylor. Acceleration methods. arXiv:2101.099: 2021.
arXiv preprint
[20] 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.

---

[21] E. De Klerk, F. Glineur, and A. B. Taylor. Worst-case convergence analysis of inexact gradient and newton methods through semidefinite programming performance estimation. SIAM Journal on Optimization, 30(3):2053-2082 2020.
[22] J. Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. COLT, 2020.
[23] J. Diakonikolas and C. Guzmán. Complementary composite minimization, small gradients in general norms, and applications regression problems. arXiv preprint arXiv:2101.11041, 2021.
[24] J. Diakonikolas and P. Wang. Potential function-based framework for making the gradients small in convex and min-max optimization. arXiv preprint arXiv:2101.12101, 2021.
[25] D. L. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289- 1306, 2006.
[26] R.-A. Dragomir, A. B. Taylor, A. d' d'Aspremont, and J. Bolte. Optimal complexity and certifica- tion Bregman first-order methods. Mathematical Programming. 2021.
[27] Y. Drori. The exact information-based complexity of smooth convex minimization. Journal of Complexity, 39:1-16, 2017.
[28] Y. Drori and A. Taylor. On the oracle complexity of smooth strongly convex minimization. arXiv preprint arXiv:2 2021.
[29] Y. Drori and M. Tehoulle. Performance of first-order methods for smooth convex minimization: a novel approach. Mathematical Programming, 145(1):451-482 2014.
[30] D. Drusvyatskiy, M. Fazel, and S. Roy, An optimal first order method based on optimal quadratic averaging. SIAM Journal on Optimization, 28(1):251-271) 2018.
[31] M. Fazlyab, A. Ribeiro, M. Morari, and V. M. Preciado. Analysis of optimization algorithms via integral quadratic constraints: Nonstrongly convex problems. SIAM Journal on Optimization, 28(3):2654-2689) 2018.
[32] A. V. Gasnikov and Y. E. Nesterov. Universal method for stochastic composite optimization problems. Computational Mathematics and Mathematical Physics, 58 11:4464,,44 2018.
[33] R. Ge, Huang, C. Jin, and Y. Yuan. Escaping from saddle points - online stochastic gradient for tensor decomposition. COLT, 2015.
[34] S. Ghadimi and G. Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1-2):59-99, 2016.
[35] N. Golowich, S. Pattathil, C. Daskalakis, and A. Ozdaglar. Last iterate is slower than averaged iterate smooth convex-concave saddle point problems. COLT, 2020.
[36] G. Gu and J. Yang. Tight sublinear convergence rate of the proximal point algorithm for maximal monotone inclusion problems. SIAM Journal Optimization, 101 2020.
[37] O. Güler. New proximal point algorithms for convex minimization. SIAM Journal on Optimiza- tion, 2(4):649 1992.
[38] B. Hu and L. Lessard. Dissipativity theory for Nesterov's accelerated method. ICML,, 2017.
[39] W. Huang and K. Wei. Riemannian proximal gradient methods. Mathematical Programming, 2021.
[40] X. Huang, E. K. Ryu, and W. Yin. Scaled relative graph of normal matrices. arXiv preprint XrXiv:2001.0m 222660 2019.
[41] X. Huang, F. K. Ryu, and Yin. Tight coefficients of averaged operators via sealed relative graph. Journal of Mathematical Analysis and Applications, 124(1): 2020.
12

---

[42] S. Karimi and S. Vavasis. A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descent. arXiv preprint arXiv:1712.09498. 2017.
[43] D. Kim. Accelerated proximal point method for maximally monotone operators. Mathematical Programming, 2021.
[44] D. Kim and J. A. Fessler. Optimized first-order methods for smooth convex minimization. Mathematical Programming, 159(1) 2016.
[45] D. Kim and A. Fessler. Another look at the fast iterative shrinkage/tbresholddngg algorithm (FISTA). SIAM Journal on Optimization, 28( (8(11:223-255 2018.
[46] D. Kim and J. A. Fessler. Generalizing the optimized gradient method for smooth convex minimization. SIAM Journal on Optimization, 2802):1900-1900, 2018.
[47] 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, 18999)91 2021.
[48] L. Lessard, B. Recht, and A. Packard. Analysis and design of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016.
[49] H. Li and Z. Lin. Accelerated proximal gradient methods for nonconvex programming. NeurIPS, 2015.
[50] Lieder. On the convergence rate of the Halpern-ierratoon Optimization Letters, 15(2):005-418, 2021.
[51] Q. Lin, 7. Lu, and L. Xiao. An accelerated proximal coordinate gradient method. NeurlPS, 2014.
[52] J. Moreau. Fonctions convexes duales points proximaux dans un espace hilbertien. Comples rendus hebdomadaires des séances de I' l'Académie des sciences, 255:2897-2899, 1962.
[53] J.-J. Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société mathématique de France, 03:273-299, 1965.
[54] A. S. Nemirovski. Optimization II: Numerical methods for nonlinear continuous optimization. lecture note, 1999.
[55] A. S. Nemirovsky. On optimality of Krylov's information when solving linear operator equations. Journal of Complexity, 12)):12 1991.
[56] A. S. Nemirovsky. Information- based complexity of linear operator equations. Journal of Complexity, 8(2)1533-75, 1992.
[57] Y. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence (1)/k²). Proceedings of the USSR Academy of Sciences, 269:543-544 547, 1983.
[58] Y. Nesterov. How to make the gradients small. Optima. Mathematical Optimization Society Newsletter, (88): 10:110011,,10 11, 2012.
[59] Y. Nesterov. Gradient methods for minimizing composite functions. Mathematical Program- ming, 140(1):125-161, 2013.
[60] Y. Nesterov. Lectures Convex Optimization. 2nd edition, 2018.
[61] Y. Nesterov, A. Gasnikov, S. Guminov, and P. Dvurechensky. Primal-dual accelerated gradient methods with small-dimensional relaxation oracle. Optimization Methods and Software, pages
1-38, 2020.
[62] N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1(3):127- 239, 2014.
[63] C. Park, Park, and K. Ryu, Factor- acceleration of accelerated gradient methods. arXiv preprint arXiv:2102.07366, 2021.
13

---

[64] G. B. Passty. Ergodic convergence to zero of the sum of monotone operators in Hilbert space. Journal of Mathematical Analysis and Applications, 72(2):383-390, 1979.
[65] R. Rockafellar. Convex Analysis. 1970.
[66] E. K. Ryu, R. Hannah, and W. Yin. Scaled relative graph: Nonexpansive operators via 2d euclidean geometry. Mathematical Programming. 2021.
[67] E. K. Ryu, A. B. Taylor, C. Bergeling, and P. Giselsson. Operator splitting performance estima- tion: Tight contraction factors and optimal parameter selection. SIAM Journal on Optimization, 30(3):251122771 2020.
[68] E. Ryu and W. Yin. Large-Scale Convex Optimization via Monotone Operators. Draft, 2021.
[69] B. Shi, S. Du, M. I. Jordan, and J. Su. Understanding the acceleration phenomenon via high-resolution differential equations. Mathematical Programming, 2021.
[70] W. Su, S. Boyd, and E. Candes. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. NeurlPS, 2014.
[71] A. B. Taylor. Convex interpolation and performance estimation of first-order methods for convex optimization. PhD thesis, Catholic University of Louvain, Louvain-la-Neuve, Belgium, 2017.
[72] A. B. Taylor and F. Bach. Stochastic frst-order methods: -on-asympiooicc and computer-aided analyses via potential functions. COLT, 2019.
[73] A. B. Taylor and Y. Drori. An optimal gradient method for smooth (possibly strongly) convex minimization. arXiv preprint arXiv:2101.0974 2021.
[74] 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, 27(3):1283-1313, 2017.
[75] A. B. Taylor, M. Hendrickx, and Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming, 161(1=2):077-35, 2017.
[76] A. B. Taylor, J. M. Hendrickx, and F. Glineur. Exact worst-case convergence rates of the proximal gradient method for composite convex minimization. Journal of Optimization Theory and Applications, 178(2)4455-47) 476, 2018.
[77] Tseng. On accelerated proximal gradient methods for convex optimmizatiniiiioonnnn submitted SIAM Journal Optimization. 2008
[78] B. Van Scoy, A. Freeman, and K. M. Lynch. The fastest known globally convergent first-order method for minimizing strongly convex functions. IEEE Control Systems Letters, 2(1):49-54, 2017.
[79] Y. Xu, R. Jin, and T. Yang. First-order stochastic algorithms for escaping from saddle points in almost linear time. NeurlPS, 2018.
[80] T. Yoon and E. K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems with (11kk² rate on squared gradient norm. ICML, 2021.
14


Reviews:
[{"review_id": "gFpDu9l7Tlh", "reviewer": "Reviewer_wtVu", "summary": "This paper tries to propose a new algorithm to obtain faster rate O(1/k^4) for convex objective function. The bound is OK on the surface, actually does not make sense.", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main algorithm (FISTA-G) between the line 114 and the line 115 does not work practically. The key coefficient psi_k needs the afterword coefficient psi_{k+1} and psi_{k+2}. Moreover, for every specific iteration number K, it needs a special coefficients, psi_{0}, ..., psi_{K+2}. In other words, for different K, these settings are not an algorithm but a series of algorithms, and every algorithm only efficient for a specific K. Essentially, it is not an algorithm and then obtains a bound O(1/K^4) for it. I believe this paper only hopes to use some tricks to obtain a desired bound and does not design an efficient algorithm.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I hope the authors could consider a real algorithms in practice, not only give a bound and a superficial proof. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "40"}, "extra_text": {}}, {"review_id": "gFLD58abtPF", "reviewer": "Reviewer_jb5a", "summary": "Two main contributions of this paper include (i) proposing a geometric structure that is satisfied by many first-order accelerated methods and (ii) proposing algorithms with the rate $O(1/K^4)$ for the squared gradient norm.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. The parallel structure and the collinear structure are quite interesting. \n2. The way of determining the extrapolation parameters $\\theta_k$ is strange:$ \\theta_K =1$, $\\theta_k$ is defined depending on $\\theta_{k+1}$. Does it mean we must save all the values of the sequence $\\theta_k$ in advance before running the algorithm?  \n3. $U_k$ is a sequence, it is not a Lyapunov function. The authors may want to call it an auxiliary sequence. \n4. Although the obtained rate is optimal, it is not clear how to choose K to obtain an $\\varepsilon$-optimal solution. This is important because K is chosen in advance for the proposed algorithms. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N.A. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "RQQchGHF9j", "reviewer": "Reviewer_YeUF", "summary": "This paper studies the geometric structure in composite minimization by making gradients small. More specifically, the author identifies parallel and collinear geometric structures. The novelty of this paper is the analysis of parallel structure and its extension to new variants of accelerated methods. It is indeed important to study the geometric structures for convergence rates of gradients for convex problems and the Lyapunov analysis is a standard way to analyze the convergence rates.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper provides a comprehensive and elegant analysis in terms of providing geometric insights for accelerated methods. Basically, I think this paper is a wonderful work. The only two comments I have is : 1. It would be nice to have some theoretical insights for geometric structures under non-convex settings as citation[2] did. 2. It is encouraged to use more real dataset instead of generated ones to support the theoretical results in this paper. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "26YLDFZ2t1", "reviewer": "Reviewer_TTHa", "summary": "The paper discovers parallel and co-linear structures in known accelerated first order methods and claims that these are important ingredients to achieve acceleration. The introduction of parallel structure in an optimization algorithm yields a standard way of designing a discrete Lyapunov function to analyze its convergence. A new Lyapunov analysis for OGM-G is obtained, but also a new method FISTA-G, which, combined with FISTA, yields to an improvement in the state of the art regarding convergence of gradient in the proximal gradient setting. An experiment in compressed sensing is presented as well.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The mechanism behind acceleration is a vastly studied problem in optimization community and I think that any contribution to that is of interest for neurips. The paper finds common characteristics of popular accelerated algorithms. More specifically, these algorithms can be written as a primary and secondary sequence of iterates that satisfy parallel properties in the convex case and co-linear properties in the strongly convex case. What I like here is that the co-linear structure \"converges\" in some sense to the parallel one when the strong convexity constant goes to $0$.\n\nThe authors believe that these can serve as unified characteristics of all accelerated methods and a first remarkable result is that changing slightly the auxiliary sequence of iterates in OGM-G, can yield to a novel Lyapunov analysis of convergence. However, the OGM-G presented in the paper is the same as the original one? The auxiliary iterates participate also in the definition of the primary ones...\n\nAfter a modification in FISTA to make the auxiliary iterates parallel, the new method FISTA-G combined with FISTA yields $O(1/K^4)$ iteration complexity for gradient convergence. This is better than the sate of the art which is $O(1/K^3)$. Excuse my ignorance here but why FISTA+FISTA-G yields better result than FISTA-G running for all $2K$ iterates? Can you give some intuition? Also, what is the difficulty to establish iteration complexity of the new method for the suboptimality of function values?\n\nSimilar things happening for methods for accelerated strongly convex optimization where the auxiliary iterates are endowed with the co-linear structure. In 228 it is claimed that the new methods improve over the original ones, can you explain exactly how? It is not obvious to me.\n\nThe paper is in general well-written and explains in detail subtle differences among a very large literature in accelerated methods. However, the figures are not very enlightening to me and I find a bit weird the use of arrows above vectors.\n\nLimitations of the work are discussed at the end, noting that the presented algorithms are not anytime algorithms, but this is also a limitation of the original methods that upon them the paper improves. \n\nOverall, I find the content of the paper a bit out of the ordinary, but since the presented observations can yield to better convergence result even in the special case of prox-grad, I think that this is a good contribution and vote for acceptance. However, I was not able to check the math in detail in the given time which means that my evaluation is not confident. The only concern that i have is that maybe this paper is not such a good fit for neurips due to its highly technical nature (40 pages, mostly math). Probably an optimization journal would be a better fit for proper reviewing.\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss limitations of the work and there is no negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides new geometric insights into acceleration under the Euclidean squared norm based on parallelism and collinearity of query and auxiliary points. The reviewers and area chair found the conceptual value of this contribution somewhat hard to evaluate, possibly because it only covers the Euclidean case and does not fully motivate the choice of Lyapunov function. However, the value of the contribution is reinforced by the fact that the authors use it to provide the best known bounds for making gradient small in the prox-grad setting and to derive a number of alternative algorithms for making gradient small. This improvement testifies to the novelty and usefulness of the techniques in the paper.
Decision: Accept (Poster)