Difficulty: Advanced Undergraduate Students

In our last post, we introduced a few important optimization concepts. With the understanding that the reader has (at least) a cursory knowledge of these concepts, let’s present the main idea behind acceleration.

We start by introducing one of Nesterov’s classic optimization schemes and then see how acceleration for obtaining $\varepsilon$-solutions can be understood within this scheme. For brevity, let us introduce the notation

to denote the linear approximation of a function $\psi:\mathbb{R}^{n}\mapsto\mathbb{R}$ at a given point $\bar{x}\in{\rm dom}\ \psi$.

Estimating Sequence Scheme for $({\cal P})$

• Choose $x_{0}\in{\rm dom}\ h$ and some function $\Gamma_{0}:\mathbb{R}^{n}\mapsto\mathbb{R}$. Set $A_{0}\gets0$.

• For $k=1,\ldots$

  • Find $(x_{k},A_{k})\in{\rm dom}\ h\times\mathbb{R}_{++}$ and function $\Gamma_{k}:\mathbb{R}^{n}\mapsto\mathbb{R}$ such that
  \[\begin{aligned} ({\cal R}_{k}^{1})\qquad & A_{k}\phi(x_{k})\leq\inf_{u\in\mathbb{R}^{n}}\left\{ A_{k}\Gamma_{k}(u)+\frac{1}{2}\|u-x_{0}\|^{2}\right\} ,\\ ({\cal R}_{k}^{2})\qquad & A_k \Gamma_k (u)\leq A_k \phi(u)\quad\forall u\in{\rm dom}\ h.\end{aligned}\]

Clearly, for any optimum $x^{*}$ of $({\cal P})$, the generated iterates of the above scheme satisfy

for every $k\geq1$. Re-arranging, we have

We now make a bold claim in view of the above result.

Claim II.1. All “classical” (or “Nesterov-like”) accelerated methods are instances (or minor variants) of the Estimating Sequence Scheme with

As a consequence, accelerated methods obtain an $\varepsilon$-solution of $({\cal P})$ in $O(T_{\varepsilon})$ iterations, where

Remark II.2. Bounds such as $(*)$ share some similarities with non-accelerated methods. For example, in the primal (proximal) gradient method, which has updates of the form

a similar bound as in $(*)$ can be made in which $A_{k}\approx\sum_{i=1}^{k}\lambda_{i}$ under the assumption that $\lambda_{i}\in(0,2/L)$ for every $i\geq1$. As an aside, note that if $h(\cdot) \equiv 0$ then the above update reduces to classic gradient descent with stepsize $\lambda_k$.

Remark II.3. The function $\Gamma_{k}$ acts like a special support function for $\phi$ whose approximation of $\phi$ at $x_{k}$ becomes increasingly more accurate as $A_{k}\to\infty$. Indeed, $\Gamma_{k}$ supports $\phi$ in the sense that $({\cal R}_{k}^{2})$ implies $\Gamma_{k}$ minorizes $\phi$ (i.e., bounds it from below at every point in its domain) while $({\cal R}_{k}^{1})$ implies that

in which the term $\|x_{k}-x^{*}\|^{2} / A_{k}+\|x^{*}-x^{0}\|^{2} / A_{k}$ can be made small as $A_{k}\to\infty$. However it does require the very strong global condition $({\cal R}_{k}^{1})$ to hold.

Remark II.4. Defining $v_k := {\rm argmin}_{u\in\mathbb{R}^{n}}\{A_{k}\Gamma_{k}(u)+\|u-x_{0}\|^{2}/2\}$, an interesting set of bounds implied by the above scheme is

for every $u\in\mathbb{R}^{n}$, where the second inequality follows from the fact that $A_k \Gamma_k + \|\cdot\|/2$ is $(1+\mu A_k)$-strongly convex. In particular, the above bounds at $u=x^{*}$ yield the relations

Remark II.5. The previous remark gives some insight into how acceleration can be qualified. Specifically, the rate of acceleration is directly related to the quality of the generated estimate sequence $\{\Gamma_{k}\}_{k\geq1}$ in terms of its approximation of $f$ on the sequence of points $\{x_{k}\}_{k\ge 1}$. The better the approximation, the faster the algorithm converges. For convex (or strongly convex) functions, we will see that their structure plays an important role in creating good estimate sequences.

Remark II.6. In Nesterov’s paper, the function $\psi_{k}$ is defined to be $A_{k}\Gamma_{k}+\|\cdot-x_{0}\|^{2}/2$ in order to simplify some technical expressions. For this series of posts, we opt to use $\Gamma_{k}$ because it is easier to interpret some of the results relative to $\Gamma_k$.