Optimized first-order methods for smooth convex minimization

Introduction

First-order algorithms are used widely to solve large-scale optimization problems in various fields such as signal and image processing, machine learning, communications and many other areas. The computational cost per iteration of first-order algorithms is mildly dependent on the dimension of the problem, yielding computational efficiency. Particularly, Nesterov’s fast gradient methods nesterov:83:amo ; nesterov:05:smo have been celebrated in various applications for their fast convergence rates and efficient implementation. This paper proposes first-order algorithms (OGM1 and OGM2 in Section 7) that achieve a worst-case convergence bound that is twice as small as Nesterov’s fast gradient methods for smooth unconstrained convex minimization yet have remarkably similar efficient implementations.

The update step at the $i$th iterate $\bm{x}_{i}$ uses a linear combination of previous and current gradients $\{f^{\prime}(\bm{x}_{0}),\cdots,f^{\prime}(\bm{x}_{i})\}$. The coefficients $\{h_{i,k}\}_{0\leq k<i\leq N}$ determine the step size and are selected prior to iterating (non-adaptive). Designing these coefficients appropriately is the key to establishing fast convergence. The algorithm class FO includes gradient methods, heavy-ball methods polyak:64:smo , Nesterov’s fast gradient methods nesterov:83:amo ; nesterov:05:smo , and our proposed optimized first-order methods.

As reviewed in Section 4, DT drori:14:pof used relaxations to simplify the intractable problem (P) to a solvable form.

This paper proposes optimized first-order algorithms that have a worst-case convergence bound that is twice as small as that of Nesterov’s fast gradient methods, inspired by DT drori:14:pof . We develop remarkably efficient formulations of the optimized first-order algorithms that resemble those of Nesterov’s fast gradient methods, requiring $O(Nd)$ arithmetic operations and $O(d)$ memory.

Section 2 reviews the smooth convex minimization problem and introduces the approach to optimizing $\bm{h}$ used here and in drori:14:pof . Section 3 illustrates Nesterov’s fast gradient methods that are in class FO. Section 4 reviews DT’s (relaxed) PEP approach and Section 5 uses it to derive a new convergence bound for the secondary variables in Nesterov’s fast gradient methods. Section 6 reviews DT’s analysis on numerically optimizing $\bm{h}$ using (relaxed) PEP for first-order methods, and derives an analytical form of the optimized coefficients $\bm{h}$ and a corresponding new analytical bound. Section 7 investigates efficient formulations of the proposed first-order methods (OGM1 and OGM2). Section 8 shows that the corresponding analytical upper bound is tight and Section 9 concludes.

Problem and approach

We consider first-order algorithms for solving the following minimization problem

where the following two conditions are assumed:

We focus on measuring the “inaccuracy” $f(\bm{x}_{N})-f(\bm{x}_{*})$ after $N$ iterations to quantify the worst-case performance of any given first-order algorithm.

2 Optimizing the step coefficients 𝒉𝒉\bm{h} of first-order algorithms

In search of the best-performing first-order methods, DT drori:14:pof proposed to optimize $\bm{h}=\{h_{i,k}\}_{0\leq k<i\leq N}$ in Algorithm FO by minimizing a worst-case bound of $f(\bm{x}_{N})-f(\bm{x}_{*})$ for a given number of iterations $N\geq 1$ and initial distance $R>0$, by adding $\mathop{\operator@font arg\,min}_{\bm{h}}$ to problem (P) as follows:

To make DT’s work drori:14:pof practical, we directly derive the “analytical” solution for $\bm{h}$ in a relaxed version of the problem (HP), circumventing the numerical approach in drori:14:pof . Interestingly, the analytical solution of the relaxed version of (HP) satisfies a convenient recursion, so we provide practical optimized algorithms similar to Nesterov’s efficient fast gradient methods.

Nesterov’s fast gradient methods

This section reviews Nesterov’s well-known fast gradient methods nesterov:83:amo ; nesterov:05:smo . We further show the equivalence The equivalence of two of Nesterov’s fast gradient methods for smooth unconstrained convex minimization was previously mentioned without details in tseng:10:aag . of two of Nesterov’s fast gradient methods in smooth unconstrained convex minimization. The analysis techniques used here will be important in Section 7.

Nesterov’s first fast gradient method is called FGM1 nesterov:83:amo :

Note that $t_{i}$ in (3.1) satisfies the following relationships used frequently in later derivations:

Algorithm FGM1 is in Algorithm Class FO (drori:14:pof, , Proposition 2) with:

for $i=0,\cdots,N-1$. Note that Algorithm FO with (3.3) is impractical as written for large-scale optimization problems, whereas the mathematically equivalent version FGM1 is far more useful practically due to its efficient form.

While the sequence $\{\bm{x}_{0},\cdots,\bm{x}_{N-1},\bm{y}_{N}\}$ of FGM1 can be also written in class FO (drori:14:pof, , Proposition 2), only the primary sequence $\{\bm{y}_{0},\cdots,\bm{y}_{N}\}$ is known to achieve the rate $O\left(\frac{1}{N^{2}}\right)$ for decreasing $f$ beck:09:afi ; nesterov:83:amo . DT conjectured that the secondary sequence $\{\bm{x}_{0},\cdots,\bm{x}_{N}\}$ of FGM1 also achieves the same $O\left(\frac{1}{N^{2}}\right)$ rate based on the numerical results using the PEP approach (drori:14:pof, , Conjecture 2); our Section 5 verifies the conjecture by providing an analytical bound using the PEP approach.

2 Nesterov’s fast gradient method 2 (FGM2)

In nesterov:05:smo , Nesterov proposed another fast gradient method that has a different The fast gradient method in nesterov:05:smo was originally developed to generalize FGM1 to the constrained case. Here, this second form is introduced for use in later proofs. form than FGM1 and that used a choice of $t_{i}$ factors different from (3.1). Here, we use (3.1) because it leads to faster convergence than the factors used in nesterov:05:smo . The algorithm in nesterov:05:smo then becomes FGM2 shown below.

Similar to FGM1, the following proposition shows that FGM2 is in class FO with

for $i=0,\cdots,N-1$ with $t_{i}$ in (3.1).

The sequence $\{\bm{x}_{0},\cdots,\bm{x}_{N}\}$ generated by Algorithm FO with (3.4) is identical to the corresponding sequence generated by Algorithm FGM2.

We use induction, and for clarity, we use the notation $\bm{x}_{0}^{\prime},\cdots,\bm{x}_{N}^{\prime}$ for Algorithm FO. Clearly $\bm{x}_{0}^{\prime}=\bm{x}_{0}$. To prove equivalence for $i=1$:

Assuming $\bm{x}_{i}^{\prime}=\bm{x}_{i}$ for $i=0,\cdots,n$, we then have

The fifth equality uses the telescoping sum $\bm{x}_{n}=\bm{x}_{0}+\sum_{j=1}^{n}(\bm{x}_{j}-\bm{x}_{j-1})$ and (1.1) in Algorithm FO. ∎

We show next the equivalence of Nesterov’s two algorithms FGM1 and FGM2 for smooth unconstrained convex minimization using (3.3) and (3.4).

The sequence $\{\bm{x}_{0},\cdots,\bm{x}_{N}\}$ generated by Algorithm FGM2 is identical to the corresponding sequence generated by Algorithm FGM1.

We prove the statement by showing the equivalence of (3.3) and (3.4). We use the notation $\bar{h}_{i,k}^{\prime}$ for the coefficients (3.4) of Algorithm FGM2 to distinguish from those of Algorithm FGM1.

It is obvious that $\bar{h}_{i+1,i}^{\prime}=\bar{h}_{i+1,i},\;i=0,\cdots,N-1$, and we can easily prove for $i=0,\cdots,N-1$ that

We next use induction by assuming $\bar{h}_{i+1,k}^{\prime}=\bar{h}_{i+1,k}$ for $i=0,\cdots,n-1,\;k=0,\cdots,i$. We then have

for $k=0,\cdots,n-2$. Note that this proof is independent of the choice of $t_{i}$. ∎

3 A convergence bound for Nesterov’s fast gradient methods

Algorithms FGM1 and FGM2 generate the same sequences $\{\bm{x}_{i}\}$ and $\{\bm{y}_{i}\}$, and the primary sequence $\{\bm{y}_{i}\}$ is known to satisfy the bound The second inequality of (3.5) is widely known since it provides simpler interpretation of a convergence bound, compared to the first inequality of (3.5). beck:09:afi ; nesterov:83:amo ; nesterov:05:smo :

for $n\geq 1$, which was the previously best known analytical bound of first-order methods for smooth unconstrained convex minimization; DT’s PEP approach provides a tighter numerical bound for the sequences $\{\bm{x}_{i}\}$ and $\{\bm{y}_{i}\}$ compared to the analytical bound (3.5) (drori:14:pof, , Table 1). Using the PEP approach, Section 5 provides a new analytical bound for the secondary sequence $\{\bm{x}_{i}\}$ of FGM1 and FGM2.

for $n=1,\cdots,\left\lfloor\frac{d-1}{2}\right\rfloor$, indicating that Nesterov’s two FGM1 and FMG2 achieve the optimal rate $O\left(\frac{1}{N^{2}}\right)$. (Note that the bound (3.6) is valid if the large-scale condition “$d\geq 2N+1$” is satisfied.) However, (3.6) also illustrates the potential room for improving first-order algorithms by a constant factor.

To narrow this gap, DT drori:14:pof used a relaxation of problem (HP) to find the “optimal” choice of $\{h_{i,k}\}$ for Algorithm FO that minimizes a relaxed bound on $f(\bm{x}_{N})-f(\bm{x}_{*})$ at the $N$th iteration, which was found numerically to provide a twice smaller bound than (3.5), yet remained computationally impractical.

We next review the PEP approach for solving a relaxed version of (P).

DT’s convergence bound for first-order algorithms using PEP

This section summarizes the relaxation scheme for the PEP approach that transforms problem (P) into a tractable form drori:14:pof . The relaxed PEP bounds are used in later sections.

Problem (P) is challenging to solve due to the (infinite-dimensional) functional constraint on $f$, so DT drori:14:pof cleverly relax the constraint by using a well-known property for the class of convex $C_{L}^{1,1}$ functions in (nesterov:04, , Theorem 2.1.5) and further relax as follows:

DT drori:14:pof finally use a duality approach on (P1). Replacing $\max_{\bm{G},\bm{\delta}}LR^{2}\delta_{N}$ by $\min_{\bm{G},\bm{\delta}}-\delta_{N}$ for convenience, the Lagrangian of the corresponding constrained minimization problem (P1) becomes the following separable function in $(\bm{\delta},\bm{G})$:

Here $\min_{\bm{\delta}}\mathcal{L}_{1}(\bm{\delta},\bm{\lambda},\bm{{\tau}})=0$ for any $(\bm{\lambda},\bm{{\tau}})\in\Lambda$, where

for any given $(\bm{\lambda},\bm{{\tau}})\in\Lambda$, where DT drori:14:pof define the following $(N+1)\times(N+1)$ matrix using the definition of $\bm{A}_{i-1,i}(\bm{h})$ and $\bm{D}_{i}(\bm{h})$ in (4.1):

In short, using the dual approach on the problem (P1) yields the following bound:

Overall, DT drori:14:pof introduced a series of relaxations to the problem (P), eventually reaching the solvable problem (D) that provides a valid upper bound as

where $\bm{x}_{N}$ is generated by Algorithm FO with given $\bm{h}$ and $N$, and $||\bm{x}_{0}-\bm{x}_{*}||\leq R$. This bound is for a given $\bm{h}$ and later we optimize the bound over $\bm{h}$.

Solving problem (D) with a SDP method for any given coefficients $\bm{h}$ and $N$ provides a numerical convergence bound for $f(\bm{x}_{N})-f(\bm{x}_{*})$ drori:14:pof . However, numerical bounds only partially explain the behavior of algorithms in class FO. An analytical bound of gradient methods with a constant step $0<h\leq 1$, for example, was found using a specific PEP approach drori:14:pof , but no other analytical bound was discussed in drori:14:pof . The next section exploits the PEP approach to reveal a new analytical bound for the secondary sequence $\{f(\bm{x}_{i})\}$ generated by FGM1 or FGM2 as an example, confirming the conjecture by DT that the secondary sequence $\{\bm{x}_{i}\}$ achieves the same rate $O\left(\frac{1}{N^{2}}\right)$ as the primary sequence $\{\bm{y}_{i}\}$ (drori:14:pof, , Conjecture 2).

A new analytical bound for Nesterov’s fast gradient methods

This section provides an analytical bound for the secondary sequence $\{\bm{x}_{i}\}$ in FGM1 and FGM2.

For the $\bm{\bar{h}}$ factors in (3.3) or (3.4) of Nesterov’s fast gradient methods, the following choice of dual variables (inspired by Section 6.2) is a feasible point of problem (D):

with $t_{i}$ in (3.1), as shown in the following lemma.

The choice $(\bm{\bar{\lambda}},\bm{{\bar{\tau}}},\bar{\gamma})$ in (5.1), (5.2) and (5.3) is a feasible point of the problem (D) for the $\bm{\bar{h}}$ designs given in (3.3) or (3.4) that are used in Nesterov’s FGM1 and FGM2.

It is obvious that $(\bm{\bar{\lambda}},\bm{{\bar{\tau}}})\in\Lambda$ using $t_{i}^{2}=\sum_{k=0}^{i}t_{k}$ in (3.2). We next rewrite $\bm{S}(\bm{\bar{h}},\bm{\bar{\lambda}},\bm{{\bar{\tau}}})$ using (3.4), (5.1) and (5.2) to show that the choice $(\bm{\bar{\lambda}},\bm{{\bar{\tau}}},\bar{\gamma})$ satisfies the positive semidefinite condition in (D) for given $\bm{\bar{h}}$.

For any $\bm{h}$ and $(\bm{\lambda},\bm{{\tau}})\in\Lambda$, the $(i,k)$-th entry of the symmetric matrix $\bm{S}(\bm{h},\bm{\lambda},\bm{{\tau}})$ in (4.9) can be written as

Inserting $\bm{\bar{h}}$ (3.4), $\bm{\bar{\lambda}}$ (5.1) and $\bm{{\bar{\tau}}}$ (5.2) into (5.4) and using $\bar{\lambda}_{i}+\bar{\tau}_{i}=\frac{t_{i}^{2}}{t_{N}^{2}}$ for $i=1,\cdots,N$, we get

where $\bm{t}=(t_{0},\cdots,t_{N})^{\top}$ and $\bm{\check{t}}=(t_{0}^{2},\cdots,t_{N-1}^{2})^{\top}$. The second equality uses $t_{i}^{2}-t_{i}-t_{i-1}^{2}=0$ in (3.2), and $\mathop{{}\mathsf{diag}\!\left\{\bm{t}\right\}}\nolimits$ denotes a matrix where diagonal elements are filled with elements of a vector $\bm{t}$ and zero for other elements.

Finally, using $\bar{\gamma}$ in (5.3), we have

Using Lemma 1, we provide an analytical convergence bound for the secondary sequence $\{\bm{x}_{i}\}$ of FGM1 and FMG2.

Using $\bar{\gamma}$ (5.3) and $t_{N}^{2}\geq\frac{(N+2)^{2}}{4}$ from (3.2), we have

for given $\bm{\bar{h}}$ in (3.3) or (3.4), based on Lemma 1. Since the coefficients $\bm{\bar{h}}$ in (3.3) or (3.4) are recursive and do not depend on a given $N$, we can extend (5.6) for all iterations ($n\geq 1$). Finally, we let $R=||\bm{x}_{0}-\bm{x}_{*}||$. ∎

Theorem 5.1 illustrates using the PEP approach to find an analytical bound for an algorithm in class FO. We used a SDP solver cvx ; gb08 to verify numerically that the choice $(\bm{\bar{\lambda}},\bm{{\bar{\tau}}},\bar{\gamma})$ in (5.1), (5.2) and (5.3) is not an optimal solution of (D) for given $\bm{\bar{h}}$ in (3.3) or (3.4). Nevertheless, this feasible point $(\bm{\bar{\lambda}},\bm{{\bar{\tau}}},\bar{\gamma})$ provides a valid upper bound for the sequence $\{\bm{x}_{i}\}$ of FGM1 and FGM2 as shown in Theorem 5.1 that is similar to (3.5) and verifies DT’s conjecture (drori:14:pof, , Conjecture 2).

Towards optimized first-order algorithms

This section summarizes the numerically optimized first-order algorithms described in drori:14:pof .

Having relaxed (P) in Section 4 to (D), DT proposed to optimize $\bm{h}$ by relaxing (HP) as follows:

to convert (HD) into the following linear SDP problem:

An optimal solution $(\bm{\hat{r}},\bm{\hat{\lambda}},\bm{{\hat{\tau}}},\hat{\gamma})$ of (RD) for a given $N$ can be computed by any numerical SDP method cvx ; gb08 . DT showed that the resulting values $(\bm{\hat{\lambda}},\bm{{\hat{\tau}}},\hat{\gamma})$ with the following $\bm{\hat{h}}$:

The numerical results for problem (HD) in drori:14:pof provided a convergence bound that is about two-times smaller than that of Nesterov’s fast gradient methods for a couple of choices of $N$ in (drori:14:pof, , Tables 1 and 2). However, numerical calculations cannot verify the acceleration for all $N$, and SDP computation for solving (RD) becomes expensive for large $N$. In the next section, we analytically solve problem (HD), which is our first main contribution.

2 Proposed analytically optimized first-order algorithms

This section provides an analytical optimal solution of (HD) by reformulating (RD).

We first find an equivalent form of the dual function $H(\bm{\lambda},\bm{{\tau}};\bm{h})$ in (4.2) that differs from (4.8) by using the following equality:

i.e., the $(N,N)$-th entry of $\bm{S}(\bm{h},\bm{\lambda},\bm{{\tau}})$ in (4.9) and (5.4) is $\frac{1}{2}$ for any $(\bm{\lambda},\bm{{\tau}})\in\Lambda$. Hereafter we use the notation

where $\bm{Q}(\bm{h},\bm{\lambda},\bm{{\tau}})$ is a $N\times N$ symmetric matrix, $\bm{q}(\bm{h},\bm{\lambda},\bm{{\tau}})$, $\bm{{\check{w}}}$ and $\bm{{\check{\tau}}}$ are $N\times 1$ vectors, and $w_{N}$ and $\tau_{N}$ are scalars. We omit the arguments $(\bm{h},\bm{\lambda},\bm{{\tau}})$ in $\bm{Q}(\bm{h},\bm{\lambda},\bm{{\tau}})$ and $\bm{q}(\bm{h},\bm{\lambda},\bm{{\tau}})$ for notational simplicity in the next derivation. For any given $(\bm{\lambda},\bm{{\tau}})\in\Lambda$, we rewrite $H(\bm{\lambda},\bm{{\tau}};\bm{h})$ in (4.2) and (4.8) as follows:

where the second equality comes from minimizing the function with respect to $w_{N}$.

Using (6.20) instead of (4.8) for the function $H(\bm{\lambda},\bm{{\tau}};\bm{h})$ and again using the variable $\bm{r}$ in (6.1) leads to the following optimization problem that is equivalent to (RD):

A feasible point of both (RD) and (RD1) is $(\bm{\hat{r}},\bm{\hat{\lambda}},\bm{{\hat{\tau}}},\hat{\gamma})$, where

The following set of conditions are sufficient for the feasible conditions of (RD1):

The “Appendix” shows that the point $(\bm{\hat{r}},\bm{\hat{\lambda}},\bm{{\hat{\tau}}},\hat{\gamma})$ in (6.26), (6.27), (6.28) and (6.29) is the unique solution of (6.31) and also satisfies the feasible conditions of (RD). ∎

Note that the parameter $\theta_{i}$ (6.30) used in Lemma 2 differs from $t_{i}$ (3.1) only at the last iteration $N$. In other words, $\{\theta_{0},\cdots,\theta_{N-1}\}$ is equivalent to $\{t_{0},\cdots,t_{N-1}\}$ in (3.1) satisfying (3.2), whereas the last parameter $\theta_{N}$ satisfies

The next lemma shows that the feasible point derived in Lemma 2 is an optimal solution of both (RD) and (RD1).

The choice of $(\bm{\hat{r}},\bm{\hat{\lambda}},\bm{{\hat{\tau}}},\hat{\gamma})$ in (6.26), (6.27), (6.28) and (6.29) is an optimal solution of both (RD) and (RD1).

The proof in kim:14:ofo-arxiv uses the Karush-Kuhn-Tucker (KKT) conditions of linear SDP (RD). ∎

The optimized step coefficients $\bm{\hat{h}}$ of interest are then derived using (6.6) with the analytical optimal solution $(\bm{\hat{r}},\bm{\hat{\lambda}},\bm{{\hat{\tau}}},\hat{\gamma})$ of (RD). It is interesting to note that the corresponding coefficients $\bm{\hat{h}}$ in (6.33) below have a recursive form that is similar to (3.4) of FGM2, as discussed further in Section 7.

The choice of $(\bm{\hat{h}},\bm{\hat{\lambda}},\bm{{\hat{\tau}}},\hat{\gamma})$ in (6.27), (6.28), (6.29) and

for $i=0,\cdots,N-1$ with $\theta_{i}$ in (6.30) is an optimal solution of (HD).

Inserting $\bm{\hat{r}}$ (6.26), $\bm{\hat{\lambda}}$ (6.27) and $\bm{{\hat{\tau}}}$ (6.28) into (6.6), and noting that $\hat{\lambda}_{i}+\hat{\tau}_{i}>0$ for $i=1,\cdots,N$, we get

which is equivalent to (6.33). From (drori:14:pof, , Theorem 3), the corresponding $(\bm{\hat{h}},\bm{\hat{\lambda}},\bm{{\hat{\tau}}},\hat{\gamma})$ becomes an optimal solution of (HD). ∎

The following theorem shows that Algorithm FO with the optimized $\bm{\hat{h}}$ (6.33) achieves a new convergence bound.

Using $\hat{\gamma}$ (6.29) and $\theta_{N-1}^{2}=t_{N-1}^{2}\geq\frac{(N+1)^{2}}{4}$ from (3.2) and (6.30), we get

based on Lemma 4. Finally, we let $R=||\bm{x}_{0}-\bm{x}_{*}||$. ∎

Theorem 6.1 shows that algorithm FO with the optimized $\bm{\hat{h}}$ (6.33) decreases the function $f$ with a bound that is twice as small as that of Nesterov’s fast gradient methods in (3.5) and (5.5), confirming DT’s numerical results in (drori:14:pof, , Tables 1 and 2). The proposed algorithm requires at most $N=\left\lceil\sqrt{\frac{L}{\epsilon}}||\bm{x}_{0}-\bm{x}_{*}||\right\rceil$ iterations to achieve the desired accuracy $f(\bm{x}_{N})-f(\bm{x}_{*})\leq\epsilon$, while Nesterov’s fast gradient methods require at most $N=\left\lceil\sqrt{\frac{2L}{\epsilon}}||\bm{x}_{0}-\bm{x}_{*}||\right\rceil$, a factor of about $\sqrt{2}$-times more iterations.

The next section describes efficient implementations of the corresponding Algorithm FO with $\bm{\hat{h}}$ (6.33).

Efficient formulations of proposed optimized first-order algorithms

Even though the analytical expression for $\bm{\hat{h}}$ in (6.33) that solves (HD) does not require an expensive SDP method, using $\bm{\hat{h}}$ in Algorithm FO would still be computationally undesirable. Noticing the similarity between (3.4) of FGM2 and (6.33), we can expect that Algorithm FO with (6.33) may have an equivalent efficient form as FGM2, as described next. In addition, we find an equivalent form of (6.33) that is similar to (3.3) of FGM1, so that we can find a formulation that is similar to FGM1 by analogy with how Proposition 2 shows the equivalence between (3.3) and (3.4).

The optimized $\bm{\hat{h}}$ in (6.33) satisfies the following recursive relationship

for $i=0,\cdots,N-1$ with $\theta_{i}$ in (6.30).

We follow the induction proof of Proposition 2 showing the equivalence between (3.3) and (3.4). We use the notation $\hat{h}_{i,k}^{\prime}$ for the coefficient (6.33) to distinguish from (7.1).

It is obvious that $\hat{h}_{i+1,i}^{\prime}=\hat{h}_{i+1,i},\;i=0,\cdots,N-1$, and we clearly have

We next use induction by assuming $\hat{h}_{i+1,k}^{\prime}=\hat{h}_{i+1,k}$ for $i=0,\cdots,n-1,\;k=0,\cdots,i$. We then have

for $k=1,\cdots,n-2$. Note that this proof is independent of the choice of $\theta_{i}$. ∎

Next, we revisit the derivation in Section 3 to transform Algorithm FO with (6.33) or (7.1) into efficient formulations akin to Nesterov’s fast gradient methods, leading to practical algorithms.

We first propose the following optimized gradient method, called OGM1, using (7.1) in Algorithm FO. OGM1 is computationally similar to FGM1 yet the sequence $\{\bm{x}_{i}\}$ generated by OGM1 achieves the fast convergence bound in Theorem 6.1.

Apparently, the proposed OGM1 accelerates FGM1 by using just one additional momentum term $\frac{\theta_{i}}{\theta_{i+1}}(\bm{y}_{i+1}-\bm{x}_{i})$, and thus OGM1 is computationally efficient. Also, unlike DT’s approach that requires choosing $N$ for using a SDP solver before iterating, the proposed OGM1 does not need to know $N$ in advance because the coefficients $\bm{\hat{h}}$ (or $\theta_{i}$) for intermediate iterations ($i=0,\cdots,N-1$) do not depend on $N$.

The sequence $\{\bm{x}_{0},\cdots,\bm{x}_{N}\}$ generated by Algorithm FO with (7.1) is identical to the corresponding sequence generated by Algorithm OGM1.

We use induction, and for clarity, we use the notation $\bm{x}_{0}^{\prime},\cdots,\bm{x}_{N}^{\prime}$ for Algorithm FO. It is obvious that $\bm{x}_{0}^{\prime}=\bm{x}_{0}$, and since $\theta_{0}=1$ we get

Assuming $\bm{x}_{i}^{\prime}=\bm{x}_{i}$ for $i=0,\cdots,n$, we then have

2 Proposed optimized gradient method 2 (OGM2)

We propose another efficient formulation of Algorithm FO with (6.33) that is similar to the formulation of FGM2.

The sequence $\{\bm{x}_{i}\}$ generated by OGM2 achieves the fast convergence bound in Theorem 6.1. Algorithm OGM2 doubles the weight on all previous gradients for $\{\bm{z}_{i}\}$ compared to FGM2, providing some intuition for its two-fold acceleration. OGM2 requires comparable computation per iteration as FGM2.

The sequence $\{\bm{x}_{0},\cdots,\bm{x}_{N}\}$ generated by Algorithm FO with (6.33) is identical to the corresponding sequence generated by Algorithm OGM2.

We use induction, and for clarity, we use the notation $\bm{x}_{0}^{\prime},\cdots,\bm{x}_{N}^{\prime}$ for Algorithm FO. It is obvious that $\bm{x}_{0}^{\prime}=\bm{x}_{0}$, and since $\theta_{0}=1$ we get

Assuming $\bm{x}_{i}^{\prime}=\bm{x}_{i}$ for $i=0,\cdots,n$, we then have

The third equality uses the telescoping sum $\bm{x}_{n}=\bm{x}_{0}+\sum_{j=1}^{n}(\bm{x}_{j}-\bm{x}_{j-1})$ and (1.1) in Algorithm FO. ∎

Discussion

After submitting this work kim:14:ofo-arxiv , Taylor et al. taylor:15:ssc further studied the PEP approach to compute the exact worst-case bound of first-order methods, unlike DT drori:14:pof and this paper that use the relaxed PEP. Taylor et al. taylor:15:ssc studied the tightness of relaxations on PEP introduced in drori:14:pof and avoided some strict relaxations.

both OGM1 and OGM2 exactly achieve the smallest upper bound in (6.34), i.e.,

We show in the “Appendix” that the following property of the coefficients $\bm{\hat{h}}$ (7.1) of OGM1 and OGM2 holds:

Then, starting from $\bm{x}_{0}=R\bm{\nu}$, where $\bm{\nu}$ is a unit vector, and using (8.2), the iterates of OGM1 and OGM2 are as follows

where the corresponding sequence $\{\bm{x}_{0},\cdots,\bm{x}_{N}\}$ stays in the affine region of the function $\phi(\bm{x})$ with the same gradient value:

Therefore, after $N$ iterations of OGM1 and OGM2, we have

exactly matching the smallest upper bound in (6.34). ∎

Conclusion

We proposed new optimized first-order algorithms that achieve a worst-case convergence bound that is twice as small as that of Nesterov’s methods for smooth unconstrained convex minimization, inspired by Drori and Teboulle drori:14:pof . The proposed first-order methods are comparably efficient for implementation as Nesterov’s methods. Thus it is natural to use the proposed OGM1 and OGM2 to replace Nesterov’s methods in smooth unconstrained convex minimization. Numerical results in large-scale imaging applications show practical convergence acceleration consistent with those predicted by the bounds given here kim:14:oms ; kim:15:aof . Those applications use regularizers that have shapes somewhat similar to the worst-case function (8.1).

The efficient formulations of both Nesterov’s methods and the new optimized first-order methods still seem somewhat magical. Recently, allen-zhu:15:lca , odonoghue:15:arf and su:15:ade studied Nesterov’s FGM formulations, and extending such studies to the new OGM methods should further illuminate the fundamental causes for their efficient formulations and acceleration. Also, new optimized first-order methods lack analytical convergence bounds for the intermediate iterations, whereas numerical bounds are studied in taylor:15:ssc ; deriving those analytical bounds is interesting future work.

Drori recently extended the PEP approach to projected gradient methods for constrained smooth convex minimization drori:14:phd . Extending this approach to general first-order algorithms including our proposed OGM1 and OGM2 is important future work. In addition, just as Nesterov’s fast gradient methods have been extended for nonsmooth composite convex minimization beck:09:afi ; nesterov:13:gmf , extending the proposed optimized first-order algorithms for minimizing nonsmooth composite convex functions would be a natural direction to pursue.

While DT’s PEP approach involves a series of relaxations to make the problem solvable, OGM1 and OGM2 with the step coefficients $\bm{\hat{h}}$ that are optimized over the relaxed PEP upper bound (HD) achieve an exact bound in Theorem 8.1. However, it remains an open problem to either prove that the smallest upper bound in (6.34) of OGM1 and OGM2 is optimal. We leave either proving the above statement for (HP) or to further optimize the first-order methods as future work.

Appendix

We prove that the choice $(\bm{\hat{r}},\bm{\hat{\lambda}},\bm{{\hat{\tau}}},\gamma)$ in (6.26), (6.27), (6.28) and (6.29) satisfies the feasible conditions (6.31) of (RD1).

Using the definition of $\bm{\breve{Q}}(\bm{r},\bm{\lambda},\bm{{\tau}})$ in (6.24), and considering the first two conditions of (6.31), we get

where the last equality comes from $(\bm{\lambda},\bm{{\tau}})\in\Lambda$, and this reduces to the following recursion:

We use induction to prove that the solution of (10.1) is

which is equivalent to $\bm{\hat{\lambda}}$ (6.27). It is obvious that $\lambda_{1}=\theta_{0}\lambda_{1}$, and for $i=2$ in (10.1), we get

Then, assuming $\lambda_{i}=\theta_{i-1}^{2}\lambda_{1}$ for $i=1,\cdots,n$ and $n\leq N-1$, and using the second equality in (10.1) for $i=n+1$, we get

where the last equality uses (3.2). Then we use the first equality in (10.1) to find the value of $\lambda_{1}$ as

Until now, we derived $\bm{\hat{\lambda}}$ (6.27) using some conditions of (6.31). Consequently, using the last two conditions in (6.31) with (3.2) and (6.32), we can easily derive the following:

which are equivalent to $\bm{{\hat{\tau}}}$ (6.28) and $\hat{\gamma}$ (6.29).

Next, we derive $\bm{\hat{r}}$ for given $\bm{\hat{\lambda}}$ (6.27) and $\bm{{\hat{\tau}}}$ (6.28). Inserting $\bm{{\hat{\tau}}}$ (6.28) to the first two conditions of (6.31), we get

for $i,k=0,\cdots,N-1$, and considering (6.14) and (10.2), we get

Finally, using the two equivalent forms (6.5) and (10.3) of $\bm{\breve{S}}(\bm{\hat{r}},\bm{\hat{\lambda}},\bm{{\hat{\tau}}})$, we get

and this can be easily converted to the choice $\hat{r}_{i,k}$ in (6.26).

For these given $(\bm{\hat{r}},\bm{\hat{\lambda}},\bm{{\hat{\tau}}})$, we can easily notice that

for $\bm{\check{\theta}}=\left(\theta_{0},\cdots,\theta_{N-1},\frac{\theta_{N}}{2}\right)^{\top}$, showing that the choice is feasible in both (RD) and (RD1). ∎

2 Proof of (8.2)

We prove that (8.2) holds for the coefficients $\bm{\hat{h}}$ (7.1) of OGM1 and OGM2.

We first show the following property using induction:

Clearly, $\hat{h}_{1,0}=1+\frac{2\theta_{0}-1}{\theta_{1}}=\theta_{1}$ using (3.2). Assuming $\sum_{k=0}^{j-1}\hat{h}_{j,k}=\theta_{j}$ for $j=1,\cdots,n$ and $n\leq N-1$, we get

where the last equality uses (3.2) and (6.32).

Then, (8.2) can be easily derived using (3.2) and (6.32) as

References