Acceleration in Optimization (Part V)

Difficulty: Advanced Undergraduate Students

In the previous set of posts, we developed two schemes for finding $\varepsilon$-solutions of $({\cal P})$ based on Nesterov’s Estimating Sequence Scheme. In this post, we will show how our previous developments can be used to obtain convergence rates for finding an $\varepsilon$-stationary point of $({\cal P})$.

Key Property of a Composite Gradient Step

Since the main iterates $\{x_{k}\}_{k\geq1}$ in both the dual gradient method and accelerated gradient method are derived from a composite gradient step, one of the useful results we will need is the following lemma.

Lemma V.1. Suppose $f$, $h$, and $\phi$ are as in problem $({\cal P})$. Moreover, define the function

for every $K\geq0$ and $y\in\mathbb{R}^{n}$. Then, for every $x\in{\rm dom}\ h$, it holds that

Proof. Let $x\in{\rm dom}\ h$ and denote $T=T_{L}[x]$. Moreover, in view of the optimality of $x$, let $\xi\in\partial h(T)$ be such that $0=\nabla f(x)+\xi+L(T-x)$. Now, since

it suffices to show that $|r|^{2}\leq8L[\phi(x)-\inf_{u\in\mathbb{R}^{n}}\phi(u)].$ We first start with a technical inequality. Using upper curvature condition $(\alpha)$, the definition of $\xi$, and the definition of the subdifferential, we have that

and hence, we have

Combining the above bound with the triangle inequality, the $L$-Lipschitz continuity of $\nabla f$, and the definition of $r$, we conclude that

Squaring both sides yields the desired bound. QED

Obtaining $\varepsilon$-Stationary Points

The previous lemma showed a direct relationship between the stationarity of a composite gradient step and its optimality (in terms of function value). Let us now use this result to obtain appropriate complexity bounds for obtaining $\varepsilon$-stationary points. It is worth mentioning that this technique shows up in Subsection 2.2.2 of Nesterov’s convex optimization book for the special case of $h = 0$.

We first modify the original accelerated gradient method by defining $z_{0}=x_{0}$ and introducing the following additional computations at the end of each iteration:

We now obtain an interesting result about the modified method.

Proposition V.2. The iterates ${(z_{k},A_{k},\Gamma_{k})}$ of the modified accelerated gradient method satisfy $({\cal R}_{k}^{1})$ and $({\cal R}_{k}^{2})$ with $x_{k}=z_{k}$ and, hence, the modified accelerated gradient method implements the Estimating Sequence Scheme.

Proof. Condition $({\cal R}_{k}^{2})$ is immediate since we are using the same sequence ${\Gamma_{k}}$ from the original accelerated method. To show condition $({\cal R}_{k}^{1})$, it suffices to show that $\phi(z_{k})\leq\phi(x_{k})$ for $k\geq1$ (since the $k=0$ is obvious). Indeed, it follows from $(\gamma)$ in Lemma V.1. and the definition of $\bar{z}_{k}$ that

where $T_{K}[y]$ is as in Lemma V.1. QED

Let us now show that the new sequence ${z_{k}}_{k\ge0}$ converges to a stationary point at an accelerated rate. Using Lemma V.1. with $x=z_{k-1}$, we first have that

where $T_{K}[y]$ is as in Lemma V.1. and $x^{*}$ is any optimal solution. Defining $\eta_{k}=\phi(z_{k})-\phi(x^{*})$, we are left with the telescoping inequality

If we average the above inequality over indices $k+1$ and $2k$ and minorize it by the minimum squared distance, we have

Now, in view of Proposition V.2., we can use property $(*)$ of the Estimating Sequence Scheme to conclude that

Using the fact that $A_{k}$ exhibits either a quadratic or geometric growth rate, we can now derive the following result.

Theorem V.3. Modified accelerated gradient methods obtain a $\varepsilon$-stationary point of $({\cal P})$ in $O(T_{\varepsilon}’)$ iterations, where

and $W(\cdot)$ is the Lambert-W (or product log) function.

Sketch Proof. Show that the number of iterations needed to make $4L\|x_{0}-x^{*}\|^{2}\varepsilon^{2}\leq kA_{k}$ is $O(T_{\varepsilon}’)$ and combine this with relation $(\delta)$ above. A helpful fact is that for $y\geq0$ and any $x\in\mathbb{R}$ we have $W(y)=x$ if and only if $y=xe^{x}$. Moreover for the $\mu>0$ case, it is helpful to show the identity

which for $\alpha\in(0,1)$ implies that $y=W(c\log(1+\alpha))/\log(1+\alpha)\underset{\sim}{>}W(c)/\alpha$ (from the fact that $\log(1+x)\geq x/(1+x)$ for $x\geq-1$). QED

Remark V.4. For $x \geq e$, Hoorfar and Hassani showed that

In view of this bound, the modified accelerated gradient method asymptotically takes more iterations to find an $\varepsilon$-stationary point than an $\varepsilon$-solution when $\mu=0$ and slightly fewer iterations when $\mu>0$.

Remark V.5. The technique of introducing the auxiliary sequence $\{z_{k}\}_{k\geq1}$ does not have a specific name in the current optimization literature, but in nearly all of my recent works, you will see it being referred to as a refinement of the original iterate sequence. Personally, I would have liked to call it a transportation procedure following a well-know result of Brønsted & Rockafellar (see, for example, Theorem XI.4.2.1 in Lemarechal’s book), but this name didn’t jive too enough with my collaborators.

Exercise V.6. Show similar (but worse) bounds for the dual gradient method.

Remark V.7. The $O(\varepsilon^{-2/3})$ complexity bound for obtaining $\varepsilon$-stationary points of $({\cal P})$ is moderately better than the $O(\varepsilon^{-1})$ complexity bound for the composite gradient method. However, it is still does not reach the optimal lower bound complexity of $O(\varepsilon^{-1/2})$. Using a regularization trick, this bound can be improved to $O(\varepsilon^{-1/2} \log \varepsilon^{-1})$, but it still remains an open problem whether the logarithmic term in the previous complexity can be removed. It also remains open whether the previous bound can be obtained without and regularization tricks.