William Kong William Kong
← All Blog Posts · · 3 min read · Advanced Undergraduate Students

Acceleration in Optimization (Part III)

#mathematics #algorithms #acceleration #optimization #convex analysis
Series: Acceleration in Optimization (Part 3 of 6)

In the previous post, we introduced one of Nesterov’s classic optimization schemes, and claimed that accelerated methods were just special instances of that scheme. For this post, let us give a simple example of an unaccelerated method that implements the Estimating Sequence Scheme and describe some of its properties.


Dual Gradient Method


  • Choose x0∈dom hx_{0}\in{\rm dom}\ h and define Γ0(⋅)≡0\Gamma_{0}(\cdot)\equiv0. Set A0=0A_{0}=0, v0=x0v_{0}=x_{0}, and y0=x0y_{0}=x_{0}.

  • For k=1,…k=1,\ldots

    • Set Ak←Ak−1+L−1A_{k}\gets A_{k-1}+L^{-1} and define the function
Γk(⋅)←Ak−1Γk−1(⋅)Ak+L−1[ℓf(⋅;vk−1)+h(⋅)]Ak.\Gamma_{k}(\cdot)\gets\frac{A_{k-1}\Gamma_{k-1}(\cdot)}{A_{k}}+\frac{L^{-1}\left[\ell_{f}(\cdot;v_{k-1})+h(\cdot)\right]}{A_{k}}.
*  Compute 
vk←argminu∈Rn{AkΓk(u)+12∥u−v0∥2},yk←argminu∈Rn{ℓf(u;vk)+h(u)+L2∥u−vk∥2},xk←argmin0≤i≤k−1ϕ(yi).\begin{aligned} v_{k} & \gets{\rm argmin}_{u\in\mathbb{R}^{n}}\left\{ A_{k}\Gamma_{k}(u)+\frac{1}{2}\|u-v_{0}\|^{2}\right\} ,\\ y_{k} & \gets{\rm argmin}_{u\in\mathbb{R}^{n}}\left\{ \ell_{f}(u;v_{k})+h(u)+\frac{L}{2}\|u-v_{k}\|^{2}\right\},\\ x_{k} & \gets{\rm argmin}_{0\leq i\leq k-1}\phi(y_{i}). \end{aligned}

For completeness, let us show that the iterates of the above method satisfy both (Rk1)({\cal R}_{k}^{1}) and (Rk2)({\cal R}_{k}^{2}), so that the method is indeed an implementation of the Estimating Sequence Scheme.

Verifying the Key Conditions

Condition (Rk2)({\cal R}_{k}^{2}) follows immediately from the fact that the convex combination of two minorants is still a minorant. For condition (Rk1)({\cal R}_{k}^{1}), we proceed by induction. Since (R01)({\cal R}_{0}^{1}) is trivial, suppose (Rk1)({\cal R}_{k}^{1}) holds. Using the relations in (β)(\beta), the updates for Γk\Gamma_{k} and yky_{k}, and the upper curvature condition (α)(\alpha), we have

inf⁡u∈Rn{Ak+1Γk+1(u)+12∥u−x0∥2}=inf⁡u∈Rn{AkΓk(u)+1L[ℓf(u;vk)+h(u)]+12∥u−x0∥2}≥(β)Akϕ(xk)+1Linf⁡u∈Rn{ℓf(u;vk)+h(u)+L2∥u−vk∥2}=ykAkϕ(xk)+1L[ℓf(yk;vk)+h(yk)+L2∥yk−vk∥2]≥(α)Akϕ(xk)+1Lϕ(yk)≥Akϕ(xk+1)+1Lϕ(xk+1)=Ak+1ϕ(xk+1),\begin{align*} & \inf_{u\in\mathbb{R}^{n}}\left\{ A_{k+1}\Gamma_{k+1}(u)+\frac{1}{2}\|u-x_{0}\|^{2}\right\} \\ & =\inf_{u\in\mathbb{R}^{n}}\left\{ A_{k}\Gamma_{k}(u)+\frac{1}{L}\left[\ell_{f}(u;v_{k})+h(u)\right]+\frac{1}{2}\|u-x_{0}\|^{2}\right\} \\ & \overset{(\beta)}{\ge}A_{k}\phi(x_{k})+\frac{1}{L}\inf_{u\in\mathbb{R}^{n}}\left\{ \ell_{f}(u;v_{k})+h(u)+\frac{L}{2}\|u-v_{k}\|^{2}\right\} \\ & \overset{y_{k}}{=}A_{k}\phi(x_{k})+\frac{1}{L}\left[\ell_{f}(y_{k};v_{k})+h(y_{k})+\frac{L}{2}\|y_{k}-v_{k}\|^{2}\right]\\ & \overset{(\alpha)}{\geq}A_{k}\phi(x_{k})+\frac{1}{L}\phi(y_{k})\geq A_{k}\phi(x_{k+1})+\frac{1}{L}\phi(x_{k+1})\\ & =A_{k+1}\phi(x_{k+1}), \end{align*}

which is exactly condition (Rk+11)({\cal R}_{k+1}^{1}). Notice that we did not invoke any properties related to the convexity of ff to establish (Rk+11)({\cal R}_{k+1}^{1}) (though convexity of ff is used for (Rk2)({\cal R}_{k}^{2})).

Remark III.1 The update for yky_{k} is similar to the primal (proximal) gradient method in (†)(\dagger) from the last post. However, it has the undesirable property that Ak=k/LA_{k}=k/L, meaning that it is an unaccelerated method. In the next post, we will look at a better way to construct the estimate sequence Γk\Gamma_{k} (using the convexity of ff) to obtain an accelerated method.

Remark III.2. The affine estimate function Γk\Gamma_{k} is a balanced convex combination of the first-order approximants ℓf(⋅;vk−1)+h(⋅)\ell_{f}(\cdot;v_{k-1})+h(\cdot) at the points {vi}i≥0\{v_{i}\}_{i\geq0}. To achieve acceleration, we will consider an unbalanced convex combination of similar approximants which have larger associated values of AkA_k.

Remark III.3. By completing the square, we can write the update for yky_k as

yk←argminu∈Rn{ℓf(u;vk)+h(u)+L2∥u−vk∥2}=argminu∈Rn{∥∇f(vk)∥22L2+⟨1L∇f(vk),u−vk⟩+h(u)L+12∥u−vk∥2}=argminu∈Rn{h(u)L+12∥u−vk+1L∇f(vk)∥2}=proxh/L(vk−1L∇f(vk)),\begin{align*} y_{k} & \gets{\rm argmin}_{u\in\mathbb{R}^{n}}\left\{ \ell_{f}(u;v_{k})+h(u)+\frac{L}{2}\|u-v_{k}\|^{2}\right\} \\ & ={\rm argmin}_{u\in\mathbb{R}^{n}}\left\{ \frac{\|\nabla f(v_{k})\|^{2}}{2L^{2}}+\left\langle \frac{1}{L}\nabla f(v_{k}),u-v_{k}\right\rangle +\frac{h(u)}{L}+\frac{1}{2}\|u-v_{k}\|^{2}\right\} \\ & ={\rm argmin}_{u\in\mathbb{R}^{n}}\left\{ \frac{h(u)}{L}+\frac{1}{2}\|u-v_{k}+\frac{1}{L}\nabla f(v_{k})\|^{2}\right\} \\ & ={\rm prox}_{h/L}\left(v_{k}-\frac{1}{L}\nabla f(v_{k})\right), \end{align*}

which can similarly be done for the primal (proximal) gradient method. A similar technique can be applied to the update for vkv_k.

Remark III.4. (For advanced students) The naming of dual gradient method as a “dual” method remains a mystery to probably all but Nesterov himself. One interpretation that I have about its name comes from the duality theory corresponding to perturbation functions that I wrote about in my previous set of posts. Specifically, if a primal optimization problem can be reformulated as the minimization of a perturbation function Φ(x,u)\Phi(x,u) over xx with u=0u=0, then its dual problem is given as the maximization of the conjugate −Φ∗(x~,u~)-\Phi^{*}(\tilde{x},\tilde{u}) over u~\tilde{u} with x~=0\tilde{x}=0 and

dual→sup⁡u~−Φ∗(0,u~)≤inf⁡xΦ(x,0)←primal.\text{dual}\to\sup_{\tilde{u}}-\Phi^{*}(0,\tilde{u})\leq\inf_{x}\Phi(x,0)\gets\text{primal}.

Since the dual/conjugate problem is about finding the “best” support vector for Φ(⋅,⋅)\Phi(\cdot,\cdot), one can see a correspondence to the dual gradient method in the sense that we are looking for the “best” support function Γk\Gamma_k for ff.

Remark III.5. Nesterov also gives another analogy comparing the primal and dual gradient methods. The primal method improves the current optimization state using a local model of the objective function, and is analogous to how practitioners work in industry. On the other hand, the dual method uses its generated sequence of iterates to construct an increasingly more accurate model of the objective, and is analogous to scientists and researchers.

Discussion