A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast

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 firstorder 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 O(1/K) rate in the prox-grad setup, faster than the O(1/K) rates of Nesterov’s FGM or Kim and Fessler’s FPGM-m.

heading: 1 Introduction
text: 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 a unified framework.
In this work, we identify geometric structures, which we call the parallel and collinear structures, satisfied by a wide range of gradient- and prox-based accelerated methods including: Nesterov’s FGM [57], OGM [47], OGM-G [47], Nesterov’s FGM in the strongly convex setup (SC-FGM) [60, (2.2.22)], SC-OGM [63], TMM [78], non-stationary SC-FGM [19, §4.5], ITEM [73], geometric descent [13], Güler’s first and second accelerated proximal methods [37], and FISTA [11] 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 O(1/K4) rate when combined with FISTA in the prox-grad (composite minimization) setup. The rate is optimal as it matches the Ω(1/K4) complexity lower bound [55, 56] and is faster than the O(1/K3) rates achieved by of Nesterov’s AGM [46, 69] in the smooth convex setup or Kim and Fessler’s FPGM-m [45] in the prox-grad setup.

heading: 1.1 Preliminaries and notations
text: For L > 0, f : Rn → R is L-smooth if f is differentiable and ‖∇f(x)−∇f(y)‖ ≤ L‖x− y‖ ∀x, y ∈ Rn.
For µ > 0, g : Rn → R ∪ {∞} is µ-strongly convex if g(x) − (µ/2)‖x‖2 is convex. Let L and µ respectively denote the smoothness and strong convexity parameters of f . Write the gradient steps with stepsizes 1/L and 1/µ as
x+ = x− 1 L ∇f(x), x++ = x− 1 µ ∇f(x).
For λ > 0, the proximal operator [53, 62] Proxλg : Rn → Rn is defined as
x◦ = Proxλg(x) = arg min y∈Rn
{ g(y) + 1
2λ ‖y − x‖2
} .
35th Conference on Neural Information Processing Systems (NeurIPS 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
x⊕ = arg min y∈Rn
{ f(x) + 〈∇f(x), y − x〉+ g(y) + L
2 ‖y − x‖2
} .
If g = 0, then x⊕ = x+. If f = 0 and 1/λ = L, then x⊕ = x◦. Furthermore, write
∇̃LF (x) := −L(x⊕ − x), ∇̃1/λg(x) := − 1
λ (x◦ − x).
u ∈ Rn is a subgradient of convex function g at x if g(x) + 〈u, y − x〉 ≤ g(y) ∀ y ∈ Rn.
Subdifferential of g at x, denoted ∂g(x), is the set of subgradients of g at x. Throughout this paper, we consider the problem
minimize x∈Rn F (x) := f(x) + g(x), (P)
where f : Rn → R is convex and L-smooth and g : Rn → R ∪ {∞} is closed, convex, and proper. We say we are in the smooth convex setup if f 6= 0 and g = 0, the proximal-point setup if f = 0 and g 6= 0, and the prox-grad setup if f 6= 0 and g 6= 0. Write f?, g?, and F? to respectively denote the infima of f , g, and F . We also informally assume Proxλg is efficient to evaluate [17].

heading: 1.2 Prior works
text: 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) [44] improves this rate by a 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üler’s first and second accelerated proximal methods [37]. There are also other variants of accelerated proximal methods [51, 49, 39, 77].
The study of algorithms for reducing the gradient magnitude, which can help us understand nonconvex optimization better and design faster non-convex machine learning algorithms, was initiated by Nesterov [58]. For smooth nonconvex minimization, gradient descent (GD) achieves O((f(x0)− f?) /K) rate [54, Proposition 3.3.1]. In the smooth convex setup, combiningK iterations of FGM with K iterations of GD achieves O(‖x0 − x?‖2/K3) rate [58]. Adding a strongly convex regularization and then using SC-FGM achieves Õ(‖x0 − x?‖2/K4) rate, where Õ ignores logarithmic factors [58]. Finally, OGM-G [47] achieved O((f(x0)− f?) /K2) rate and O(‖x0 − x?‖2/K4) rate is achieved by combining FGM with OGM-G [61, Remark 2.1]. This rate is optimal as it matches the Ω(‖x0 − x?‖2/K4) lower bound [55, 56]. Making gradients small have also been studied in the setup with stochastic gradients [2, 3, 33, 79, 34], for composite problems with strong convexity and non-Euclidean norms [23], and for convex-concave saddle-point problems [22, 24, 80].
In the prox-grad setup, iterative shrinkage-thresholding algorithm (ISTA) [12, 64, 20, 18] achieves O(‖x0 − x?‖2/K) rate on function-value suboptimality and fast iterative shrinkage-thresholding algorithm (FISTA) [11] accelerates this rate toO(‖x0−x?‖2/K2). On the squared gradient magnitude, FPGM-m achieves O(‖x0 − x?‖2/K3) rate [45]. The performance estimation problem (PEP) is a computer-assisted proof methodology based on semidefinite programming [29, 75, 74]. Extensions and variations of the PEP have been utilized to obtain analyses and algorithms that would be difficult to obtain without the assistance of computers [67, 72, 10, 76, 21, 36, 50, 26, 43]. In particular, OGM [29, 44], OGM-G [47], and ITEM [73] were obtained with the PEP. Integral quadratic constraints is a related computer-assisted approach based on control-theoretic ideas [48, 38, 78, 31].
A Lyapunov analysis constructs a nonincreasing quantity, and many modern analyses of accelerated first-order methods are based on this technique [11, 70, 9, 72, 1, 6, 7, 8, 63]. In fact, Nesterov’s original presentation of FGM was a Lyapunov analysis [57].
Finally, we mention some closely related prior work. The scaled relative graph (SRG) analyzes optimization algorithms via Euclidean geometry [66, 40, 41, 68], but the SRG has not been used to analyze accelerated methods. Linear coupling [4, 5] interprets acceleration as a coupling between gradient descent and mirror descent to efficiently reduce function values. Geometric descent [13, 16, 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, 1]. 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, as 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.

heading: 1.3 Contribution
text: This paper presents two major contributions, one conceptual and one 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 to 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 O(1/K4) on the squared gradient norm in the prox-grad setup. In addition, we use the geometric structures to find G-FISTA-G, G-FGM-G, G-Güler-G, ProximalTMM, and Proximal-ITEM, novel variants of accelerated first-order methods, and present them as minor contributions. (G-FGM-G is the abbreviation for Generalized-FGM-(for reducing Gradients).)
2 Making gradients small at rate O(1/K4) in the prox-grad setup
In this section, we present a novel method FISTA-G, which reduces the squared gradient norm with O(1/K4) rate when combined with FISTA in 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 a self-contained analysis that uses, but does not explain this Lyapunov function.
Smooth convex setup. Kim and Fessler’s (OGM-G) [47] is
xk+1 = x + k + (θk − 1)(2θk+1 − 1) θk(2θk − 1) (x+k − x + k−1) + 2θk+1 − 1 2θk − 1 (x+k − xk) for k = 0, 1, . . . ,K − 1, where x+−1 := x0, θK = 1, θk = 1+ √ 1+4θ2k+1 2 for k = 1, 2, . . . ,K − 1, and θ0 = 1+ √ 1+8θ21 2 . Note, K is the total number of iterations and θ0 = O(K), so θ0 is a function of K. OGM-G is the first method to achieve the accelerated rate O((f(x0)− f?)/K2) on the squared gradient norm, and the method was originally obtained through a computer-assisted methodology. However, the computer-generated analysis is verifiable but arguably difficult to understand.
We characterize the convergence of OGM-G with the following novel Lyapunov function
Uk = 1
θ2k
( 1
2L ‖∇f(xK)‖2 +
1
2L ‖∇f(xk)‖2 + f(xk)− f(xK)−
〈 ∇f(xk), xk − x+k−1 〉) + L
θ4k
〈 zk − x+k−1, zk − x + K 〉 , for k = 1, 2, . . . ,K,
where zk = xk + (θk−1)2 2θk−1 (xk − x + k−1) for k = 1, 2, . . . ,K, (note zK = xK) through the steps
1 L ‖∇f(xK)‖2 = UK ≤ UK−1 ≤ · · · ≤ U1 ≤ 2
θ20
( 1
2L ‖∇f(xK)‖2 + f(x0)− f(xK)
) .
Section 3 explains the geometric insights behind the discovery of this Lyapunov function and the proof that {Uk}Kk=1 is nonincreasing. As related work, Diakonikolas and Wang [24] presented a human-understandable analysis of OGM-G, but their analysis is not a 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.
2.1 Accelerated O((F (x0)− F?)/K2) rate with FISTA-G
We now present the novel method (FISTA-G):
xk+1 = x ⊕ k + ϕk+1 − ϕk+2 ϕk − ϕk+1 (x⊕k − x ⊕ k−1) for k = 0, 1, . . . ,K − 1,
where x⊕−1 := x0, ϕK+1 = 0, ϕK = 1, and
ϕk = ϕ2k+2 − ϕk+1ϕk+2 + 2ϕ2k+1 + (ϕk+1 − ϕk+2)
√ ϕ2k+2 + 3ϕ 2 k+1
ϕk+1 + ϕk+2 for k = −1, 0, . . . ,K−1.
Note that K is the total number of iterations. Theorem 1. Consider (P). FISTA-G’s final iterate xK exhibits the rate
min ∥∥∂F (x⊕K)∥∥2 ≤ 4 ∥∥∥∇̃LF (xK)∥∥∥2 ≤ 264L(K + 2)2 (F (x0)− F?) .
We clarify that min ‖∂F (x)‖2 = min{‖u‖2 |u ∈ ∂F (x)} for x ∈ Rn.
Proof outline. Define z0 = x0, zk = ϕkϕk−ϕk+1xk − ϕk+1 ϕk−ϕk+1x ⊕ k−1 for k = 0, 1, . . . ,K, and
Uk = 2ϕk−1
(ϕk−1 − ϕk)2
( 1
2L ∥∥∥∇̃LF (xk)∥∥∥2 + F (x⊕k )− F (x⊕K)− 〈∇̃LF (xk), xk − x⊕k−1〉) + L
ϕk
〈 zk − x⊕k−1, zk − x ⊕ K 〉 for k = 0, 1, . . . ,K.
(Note that zK = xK .) We can show that {Uk}Kk=0 is nonincreasing. Then 1
2L ∥∥∥∇̃LF (xK)∥∥∥2 = UK ≤ · · · ≤ U0 = 2ϕ−1 (ϕ−1 − ϕ0)2 ( 1 2L ∥∥∥∇̃LF (x0)∥∥∥2 + F (x⊕0 )− F (x⊕K)) ≤ 2ϕ−1
(ϕ−1 − ϕ0)2 ( F (x0)− F (x⊕K) ) ≤ 33L (K + 2)2 (F (x0)− F?) ,
where we used 12L ∥∥∥∇̃LF (x0)∥∥∥2 ≤ F (x0)− F (x⊕0 ), stated as Lemma 9 in the appendix.
The complete proof is presented in Section E of the appendix. In fact, FISTA-G is the best instance within the family of methods G-FISTA-G presented in Section E of the appendix, in the sense that FISTA-G is the instance for which we could obtain the smallest constant in the bound.

heading: 2.2 Accelerated O(‖x0 − x?‖2/K4) rate with FISTA+FISTA-G
text: Define the method (FISTA+FISTA-G) as: from a starting point x0 run K iterations of FISTA [11] 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 x2K . Corollary 1. Consider (P). Assume F has a minimizer x?. FISTA+FISTA-G’s final iterate x2K exhibits the rate1
min ∥∥∂F (x⊕2K)∥∥2 ≤ 4 ∥∥∥∇̃LF (x2K)∥∥∥2 ≤ 528L2(K + 2)4 ‖x0 − x?‖2 .
Proof. Combining the F (x⊕K)− F? ≤ 2L‖x0 − x?‖2/(K + 2)2 rate of FISTA [11, Theorem 4.4] with Theorem 1, we get the rate of FISTA+FISTA-G:
min ∥∥∂F (x⊕2K)∥∥2 ≤ 4 ∥∥∥∇̃LF (x2K)∥∥∥2 ≤ 264L(K + 2)2 (F (x⊕K)− F?) ≤ 528L2(K + 2)4 ‖x0 − x?‖2 .
1Obtaining an iterate xK with ‖∇̃LF (xK)‖2 ≤ requiresK ≥ ( 66L(F (x0)−F?) ) 1 2 iterations for FISTA-G,
and K ≥ 2 ( 132L2‖x0−x?‖2 ) 1 4 iterations for FISTA+FISTA-G, where K is a positive even integer.
FISTA+FISTA-G was inspired by the FGM+OGM-G method, which has O(‖x0 − x?‖2/K4) rate on the squared gradient norm in the smooth convex setup [61, Remark 2.1]. Nesterov FGM by itself only achieves O(‖x0 − x?‖2/K3) rate [75, 71, 46, 69, 24]. In the prox-grad setup, FPGM-m [45] held the prior state-of-the-art rate of O(‖x0 − x?‖2/K3). Our O(‖x0 − x?‖2/K4) rate matches the known complexity lower bound [55, 56] and therefore is optimal in the case g = 0.

heading: 3 Parallel structure for the convex setup
text: 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 to obtain novel variants of accelerated first-order methods and, in particular, obtain the Lyapunov analysis presented in Section 2.

heading: 3.1 Parallel structure of acceleration
text: Nesterov’s (FGM) [57] has the form:
xk+1 = x + k + θk − 1 θk+1 (x+k − x + k−1)
zk = xk + (θk − 1)(xk − x+k−1) for k = 0, 1, . . . ,
where x+−1 := x0, x0 = z0, θ0 = 1, and θk+1 = 1+ √ 1+4θ2k 2 for k = 0, 1, . . . . The zk-iterates are known as the auxiliary sequence, and they play a key role in the Lyapunov analysis of FGM [57]. Figure 1 (left) depicts x+k−1, xk, x + k , xk+1, zk, and zk+1. These points in Rn lie on a 2D-plane, which we call the plane of iteration. Observe that the line segments representing x+k − xk and zk+1 − zk are parallel. (We prove observations 1 and 2 in Section B of the appendix.) Observation 1. In FGM, x+k − xk and zk+1 − zk are parallel2.
Drori, Teboulle, Kim, and Fessler’s (OGM) [29, 44] has the form:
xk+1 = x + k + θk − 1 θk+1 (x+k − x + k−1) + θk θk+1 (x+k − xk)
zk = xk + (θk − 1)(xk − x+k−1) for k = 0, 1, . . .K − 1,
where x+−1 := x0, z0 = x0, θ0 = 1, θk+1 = 1+ √ 1+4θ2k 2 for k = 0, 1, . . . ,K − 1, and θK =
1+ √
1+8θ2K−1 2 . OGM improves upon the rate of FGM [44]. Interestingly, OGM also exhibits a similar geometric structure as depicted in Figure 1 (middle), and the auxiliary sequence, the zk-iterates, plays a similar role in the Lyapunov analysis [63]. Observation 2. In OGM, x+k − xk and zk+1 − zk 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 zk-iterates to exhibit the parallel structure:
xk+1 = x + k + ak+1(x + k − x + k−1) + bk+1(x + k − xk) =⇒
xk = ckx + k−1 + (1− ck)zk
zk+1 = zk − dk∇f(xk) 2We define “parallel” to include the degenerate case x+k − xk = zk+1 − zk = 0.
where ak+1, bk+1, ck, and dk satisfy an appropriate relationship as shown in Section B of the appendix. The zk-iterates of FGM and OGM have this form. The parallel structure also holds for Güler’s accelerated methods [37] for the proximal-point setup and FISTA [11] for the prox-grad setup with analogous definitions of the zk-iterates. The table of Section A.1 of the appendix presents the precise forms.

heading: 3.2 Parallel structure for OGM-G and FISTA-G
text: We equivalently write (OGM-G) as
xk = θ4k+1 θ4k x+k−1 +
( 1−
θ4k+1 θ4k
) zk
zk+1 = zk − θk L ∇f(xk) for k = 1, 2, . . . ,K,
where z0 = x0, z1 = z0 − θ0+12L ∇f(x0), θK+1 = 0, and θk = 1+ √ 1+4θ2k+1 2 for k = 1, 2, . . . ,K,
and θ0 = 1+ √ 1+8θ21 2 . The key point is that the auxiliary zk-sequence is defined to exhibit the parallel structure. As a 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.
Here, we show how the Lyapunov function Uk is obtained from the parallel structure of OGM-G. For k ≥ 1, combine the cocoercivity inequalities between (xk+1, xk) and (xk, xK) to get
0 ≥ 1 θ2k+1
( f(xk+1)− f(xk)− 〈∇f(xk+1), xk+1 − xk〉+ 1
2L ‖∇f(xk+1)−∇f(xk)‖2 ) + ( 1
θ2k+1 − 1 θ2k
)( f(xk)− f(xK)− 〈∇f(xk), xk − xK〉+ 1
2L ‖∇f(xk)−∇f(xK)‖2 ) = 1
θ2k+1
( 1
2L ‖∇f(xK)‖2 +
1
2L ‖∇f(xk+1)‖2 + f(xk+1)− f(xK)−
〈 ∇f(xk+1), xk+1 − x+k 〉) − 1 θ2k ( 1 2L ‖∇f(xK)‖2 + 1 2L ‖∇f(xk)‖2 + f(xk)− f(xK)− 〈 ∇f(xk), xk − x+k−1
〉) − 〈 ∇f(xk), θ−2k+1x + k − θ −2 k x + k−1 − ( θ−2k+1 − θ −2 k ) x+K 〉︸ ︷︷ ︸
:=T
.
With the following geometric arguments, we analyze the term T and conclude 0 ≥ Uk+1 − Uk. Let t ∈ Rn be the (orthogonal) projection of x+K onto the plane of iteration. For u, v ∈ Rn, define−→uv = v − u. Then
x+k−1 xk zk
zk+1
x+k
t
1 L T
(i) = 〈−−−→ xkx + k , (θ −2 k+1 − θ −2 k ) −−→ tx+k + θ −2 k −−−−−→ x+k−1x + k 〉 (ii) = 〈−−−→ xkx + k , (θ −2 k+1 − θ −2 k )( −−−→ tzk+1 −−−−−→zkzk+1 −−−→xkzk + −−−→ xkx + k )
+ θ−2k ( −−−−→ x+k−1xk + −−−→ xkx + k ) 〉
(iii) = 〈−−−→ xkx + k , (θ −2 k+1 − θ −2 k ) −−−→ tzk+1 − (θ−2k+1 − θ −2 k )(θk − 1) −−−→ xkx + k
− ( θ−2k+1 − θ −2 k )−−→xkzk + (2θk − 1)θ−4k+1−−→xkzk + θ−2k −−−→xkx+k 〉 (iv) = 〈−−−→ xkx + k , ( θ−2k+1 − θ −2 k )−−−→ tzk+1 + θ −2 k+1(θk − 1) −1−−→xkzk 〉
(v) = θ−4k+1 〈−−−−→ x+k zk+1 − −−→xkzk, −−−→ tzk+1 〉 + θ−4k+1 〈−−−→ tzk+1 − −→ tzk, −−→xkzk 〉 (vi) = θ−4k+1 〈 zk+1 − x+k , zk+1 − x + K 〉 − θ−4k 〈 zk − x+k−1, zk − x + K 〉 ,
where (i) follows from the definition of t and the fact that we can replace x+K with t, the projection of xK onto the plane of iteration, without affecting the inner products, (ii) from vector addition,
(iii) from the fact that −−−−→zkzk+1 and −−−→ xkx + k are parallel and their lengths satisfy −−−−→zkzk+1 = θk −−−→ xkx + k and −−−−→ x+k−1xk and −−→xkzk are parallel and their lengths satisfy −−−−→ x+k−1xk = θ2k(2θk−1) θ4k+1
−−→xkzk, (iv) from the identity (θ−2k+1 − θ −2 k )(θk − 1) = θ −2 k and (2θk − 1)θ −4 k+1 − (θ −2 k+1 − θ −2 k ) = θ −2 k+1(θk − 1)−1, (v) from distributing the product and substituting −−−→ xkx + k = (θk − 1)−1( −−−−→ x+k zk+1 −
−−→xkzk) (which follows from −−−→ xkx + k = −−→xkzk +−−−−→zkzk+1 − −−−−→ x+k zk+1 = −−→xkzk + θk −−−→ xkx + k − −−−−→ x+k zk+1) into the first term and −−−→ xkx + k = θ −1 k −−−−→zkzk+1 = θ−1k (−−−→ tzk+1 − −→ tzk ) into the second term, and the identity (θ−2k+1 − θ−2k )(θk − 1)−1 = θ −2 k+1(θk − 1)−1θ −1 k = θ −4 k+1, and (vi) from cancelling out the cross terms, using θ−4k −−−−→ x+k−1zk = θ −4 k+1 −−→xkzk, and by replacing t with x+K 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 C of the appendix.
This geometric reasoning naturally extends to the prox-grad setup. Using analogous Lyapunov functions and proof structure, we obtain convergence rates of FISTA-G and the other generalizations presented in Section 3.3. Figure 1 (right) illustrates the parallel structure of FISTA-G with the zk-iterates defined as in Section A.2 of the appendix.

heading: 3.3 Other generalizations
text: 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, E, and F 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:
xk+1 = x + k + ϕk+1 − ϕk+2 ϕk − ϕk+1 (x+k − x + k−1) for k = 0, 1, . . . ,K − 1,
where x+−1 = x0 and {ϕk} K+1 k=0 is the same as the {ϕk} K+1 k=0 of FISTA-G. We can view FGM-G as a special case of FISTA-G with g = 0 or as a special case of G-FGM-G. In any case, FGM-G’s final iterate xK exhibits the rate
‖∇f(xK)‖2 ≤ 66L
(K + 2)2 (f(x0)− f?) .
OGM-G uses the “correction term” 2θk+1−12θk−1 (x + k − xk) and the “first-step modification”, i.e., θ0 is defined separately from {θk}K−1k=1 . FGM-G demonstrates that these features are not necessary for achieving the accelerated O((f(x0)− f?)/K2) rate. However, the simplification does come at the cost of a worse constant.
We present (Güler-G) for the proximal-point setup:
xk = θ4k+1 θ4k x◦k−1 +
( 1−
θ4k+1 θ4k
) zk
zk+1 = zk − θk∇̃1/λg(xk) for k = 0, 1, . . . ,K,
where z0 = x0, θK+1 = 0, and θk = 1+ √ 1+4θ2k+1 2 for k = 0, 1, . . . ,K. Theorem 2. Consider (P) with f = 0. Güler-G’s final iterate xK exhibits the rate∥∥∥∇̃1/λg(xK)∥∥∥2 ≤ 4 λ(K + 2)2 (g(x0)− g?).
Furthermore assume g has a minimizer x? and define the method Güler+Güler-G as: from a starting point x0 run K iterations of Güler second method [37] and then from the output start Güler-G and run K iterations. Then the final iterate x2K exhibits the rate∥∥∥∇̃1/λg(x2K)∥∥∥2 ≤ 4
λ2(K + 2)4 ‖x0 − x?‖2 .

heading: 4 Collinear structure for the strongly convex setup
text: In this section, we present the collinear structure, a geometric structure observed in a wide range of accelerated first-order methods for the strongly convex setup. We then utilize this structure to obtain novel variants of accelerated first-order methods. We specifically consider two strongly convex setups: f is L-smooth and µ-strongly convex and g = 0 in Section 4.1, while f = 0 and g is µ-strongly convex in Section 4.3.

heading: 4.1 Collinear structure
text: Nesterov’s (SC-FGM) [60] has the form:
xk+1 = x + k + √ κ− 1√ κ+ 1 (x+k − x + k−1) zk+1 = xk+1 + √ κ(xk+1 − x+k ) for k = 0, 1, . . . ,
where κ = Lµ and x + −1 := x0. Again, the auxiliary zk-iterates reveal the geometric structure and play a key role in the Lyapunov analysis [9, §5.5]. Figure 2 (left) depicts x+k−1, xk, x + k , x ++ k , xk+1, zk, and zk+1. These points in Rn lie on a 2D-plane, which we again call the plane of iteration. Note that zk, zk+1, and x++k are collinear, i.e., there is a line in Rn intersecting the three points. (We prove observations 3 and 4 in Section B of the appendix.)
Observation 3. In SC-FGM, zk, zk+1, and x++k are collinear 3.
Van Scoy, Freeman, and Lynch’s (TMM) [78], which improves upon SC-FGM, has the form:
xk+1 = x + k +
( √ κ− 1)2√
κ( √ κ+ 1) (x+k − x + k−1) + √ κ− 1√ κ (x+k − xk)
zk+1 = xk+1 + √ κ− 1 2 (xk+1 − x+k ) for k = 0, 1, . . . ,
where x+−1 := x0 and κ = L µ . TMM also exhibits a similar geometric structure as depicted in Figure 2 (middle), and the zk-iterates play a similar role in the Lyapunov analysis [19, Theorem 4.19].
Observation 4. In TMM, zk, zk+1, and x++k are collinear.
We refer to this geometric structure as the collinear structure. Given an algorithm expressed with momentum and correction terms, one can define the zk-iterates to exhibit the collinear structure:
xk+1 = x + k + ak(x + k − x + k−1) + bk(x + k − xk) =⇒
xk = ckx + k−1 + (1− ck)zk
zk+1 = dkx ++ k + (1− dk)zk
where ak, bk, ck, and dk satisfy an appropriate relationship as shown in Section B of the appendix. The collinear structure also holds for non-stationary SC-FGM [19, §4.5], SC-OGM [63], ITEM [73], and geometric descent [13, 30]. The table of Section A.1 presents the precise forms.
3We define “collinear” to include the degenerate case zk = zk+1 = x++k .

heading: 4.2 Collinear to parallel structure as µ→ 0
text: We briefly discuss how the parallel structure arises as the limit of the collinear structure as µ→ 0. When µ = 0, the collinear structure is undefined, as x++k = xk − (1/µ)∇f(xk) is undefined. In the limit µ→ 0, however, x++k diverges to a point of infinity in the plane of iteration, and the collinear structure becomes the parallel structure since zk, zk+1, and x++k are collinear and xk, x + k , and x ++ k are collinear.
There are two possible scenarios. In the first degenerate case, zk and zk+1 diverges to infinity. This is the case with SC-FGM, SC-OGM, and TMM. In the second scenario, zk and zk+1 stay bounded and x+k − xk and zk+1 − zk become parallel. This is the case with non-stationary4 SC-FGM and ITEM, which respectively converge to FGM and OGM.

heading: 4.3 Other generalizations
text: Using the collinear structure, we find two novel methods: Proximal-TMM and Proximal-ITEM. These methods can be viewed as proximal versions of TMM [78] and ITEM [73], and they improve upon the accelerated proximal point method [19, 10]. We provide the proofs in Section G.
We present (Proximal-TMM) for the strongly convex proximal-point setup:
xk = 1−√q 1 + √ q x◦k−1 +
( 1−
1−√q 1 + √ q ) zk
zk+1 = √ qx◦◦k + (1− √ q)zk for k = 0, 1, . . . ,
where q = λµλµ+1 , x ◦◦ k = xk − ( λ+ 1µ ) ∇̃1/λg(xk), and x◦−1 = x0 = z0.
Theorem 3. Consider (P). Assume g is µ-strongly convex, g has a minimizer x?, and f = 0. Proximal-TMM’s zk-iterates exhibits the rate
‖zk − x?‖2 ≤ 2 µ (1−√q)2k (g(x0)− g(x?)).
We present (Proximal-ITEM) for the strongly convex proximal-point setup:
xk = γkx ◦ k−1 + (1− γk)zk
zk+1 = qδkx ◦◦ k + (1− qδk)zk for k = 0, 1, . . . ,
where q = λµλµ+1 , x ◦◦ k = xk − ( λ+ 1µ ) ∇̃1/λg(xk), x◦−1 = x0 = z0, A0 = 0, Ak+1 =
(1+q)Ak+2 ( 1+ √ (1+Ak)(1+qAk) )
(1−q)2 , γk = Ak (1−q)Ak+1 , and δk = (1−q)2Ak+1−(1+q)Ak 2(1+q+qAk) for k = 0, 1, . . . .
Theorem 4. Consider (P). Assume g is µ-strongly convex, g has a minimizer x?, and f = 0. Proximal-ITEM’s zk-iterates exhibits the rate
‖zk − x?‖2 ≤ (1−√q)2k
(1−√q)2k + q ‖z0 − x?‖2.
4We say algorithm is stationary if the parameters depend on the iteration [35].

heading: 5 Experiments
text: We consider the compressed sensing [25, 15, 14] problems
minimize x∈Rn ‖Ax− b‖2 + λ ‖x‖1 , minimize x∈Rn ‖Ax− b‖2 + λ ‖x‖nuc ,
where λ > 0, ‖ · ‖1 is the `1-norm, ‖ · ‖nuc is the nuclear norm, and the data A ∈ Rm×n and b ∈ Rm are generated synthetically. We describe the data generation in Section I of the appendix. Figure 4 presents the comparison of ISTA, FISTA, FPGM-m, FISTA, FISTA-G, and FISTA+FISTA-G. The results indicate that FISTA+FISTA-G is indeed the most effective at reducing the gradient magnitude.

heading: 6 Conclusion
text: In this work, we identified geometric structures of accelerated first-order methods and utilized them to find novel variants. Specifically, we found that appropriate auxiliary zk-iterates reveal parallel and collinear structures and that these iterates are crucial for the Lyapunov analyses. Among the new methods, we highlight FISTA-G, which, combined with FISTA, achieves a O(‖x0 − x?‖2/K4) 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 ‖∇̃LF (xK)‖2 rather than mink=0,...,K ‖∇̃LF (xk)‖2, but are not anytime algorithms, i.e., the total iteration count K must be known in advance and intermediate iterates have no guarantees. In contrast, the FGM achieves acceleration on function-value suboptimality with a last-iterate rate as an anytime algorithm. Interestingly, all known algorithms for the smooth convex setup or the prox-grad setup with rate O(‖x0−x?‖2/K3) or better do not have this property. For example, OGM+OGM-G is not an anytime algorithm but has a last-iterate bound, while FGM is an anytime algorithm with a best-iterate, not a lastiterate, bound. In the prox-grad setup, FPGM-m [45] is not an anytime algorithm but has a last-iterate rate. Whether an anytime algorithm can achieve a last-iterate rate of O(‖x0 − x?‖2/K3) or better is an open problem. On a related note, Diakonikolas and Wang conjecture that a O((f(x0)− f?)/K2) 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 Government (MSIP) [No. 2020R1F1A1A01072877], the National Research Foundation of Korea (NRF) Grant funded by the Korean Government (MSIP) [No. 2017R1A5A1015626], and by the Samsung Science and Technology Foundation (Project Number SSTF-BA2101-02). CP was 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.

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

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.