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

Acceleration in Optimization (Part IV)

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

In the last post, we saw an example of an unaccelerated method that implemented Nesterov’s Estimating Sequence Scheme. Let us now give an example of an accelerated method.


Accelerated Gradient Method for P{\cal P}


  • 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

    • Find aka_{k} satisfying the quadratic equation ak2/(Ak−1+ak)=2(1+μAk−1)/La_{k}^{2}/(A_{k-1}+a_{k})=2(1+\mu A_{k-1})/L.

    • Set Ak=Ak−1+akA_{k}=A_{k-1}+a_{k} and compute

yk←Ak−1Akxk−1+akAkvk−1,xk←argmin u∈Rn{ℓf(u;yk)+h(u)+L2∥u−yk∥2}.\begin{aligned} y_{k} & \gets\frac{A_{k-1}}{A_{k}}x_{k-1}+\frac{a_{k}}{A_{k}}v_{k-1},\\ x_{k} & \gets{\rm argmin}\ _{u\in\mathbb{R}^{n}}\left\{ \ell_{f}(u;y_{k})+h(u)+\frac{L}{2}\|u-y_{k}\|^{2}\right\} .\end{aligned}
  • Define the function
Γk(⋅)←Ak−1AkΓk−1(⋅)+akAk[ℓf(⋅;xk)+h(⋅)].\Gamma_{k}(\cdot)\gets\frac{A_{k-1}}{A_{k}}\Gamma_{k-1}(\cdot)+\frac{a_{k}}{A_{k}}\left[\ell_{f}(\cdot;x_{k})+h(\cdot)\right].
  • Compute
vk←argmin u∈Rn{AkΓk(u)+12∥u−x0∥2}.v_{k}\gets{\rm argmin}\ _{u\in\mathbb{R}^{n}}\left\{ A_{k}\Gamma_{k}(u)+\frac{1}{2}\|u-x_{0}\|^{2}\right\} .

Like the previous post, let us also prove that the iterates of the above method satisfy both (Rk1)({\cal R}_{k}^{1}) and (Rk2)({\cal R}_{k}^{2}).

An Important Technical Bound

Before doing so, we derive an important technical inequality. In view of the optimality condition for xk+1x_{k+1}, let us denote and observe that

(∗∗)ϕ′(xk+1):=∇f(xk+1)−∇f(yk+1)+L(yk+1−xk+1)∈∇f(xk+1)+∂h(xk+1)=∂ϕ(xk+1).\begin{aligned} (**)\qquad\phi'(x_{k+1}) & :=\nabla f(x_{k+1})-\nabla f(y_{k+1})+L(y_{k+1}-x_{k+1})\\ & \in\nabla f(x_{k+1})+\partial h(x_{k+1})=\partial\phi(x_{k+1}).\end{aligned}

Using the inclusion (∗∗)(**) and the fact that ∇f(⋅)\nabla f(\cdot) is LL-Lipschitz continuous (see three posts ago), we first have that

⟨ϕ′(xk+1),yk+1−xk+1⟩=L∥yk+1−xk+1∥2−⟨∇f(yk+1)−∇f(xk+1),yk+1−xk+1⟩=(∗∗)1L[∥ϕ′(xk+1)−[∇f(xk+1)−∇f(yk+1)]∥2]−⟨∇f(yk+1)−∇f(xk+1),yk+1−xk+1⟩=1L[∥ϕ′(xk+1)∥2−2⟨ϕ′(xk+1),∇f(xk+1)−∇f(yk+1)⟩+∥∇f(xk+1)−∇f(yk+1)∥2]−⟨∇f(yk+1)−∇f(xk+1),yk+1−xk+1⟩=1L∥ϕ′(xk+1)∥2−1L∥∇f(xk+1)−∇f(yk+1)∥2+⟨∇f(yk+1)−∇f(xk+1),yk+1−xk+1⟩≥1L∥ϕ′(xk+1)∥2−L∥yk+1−xk+1∥2+⟨∇f(yk+1)−∇f(xk+1),yk+1−xk+1⟩\begin{aligned} & \left\langle \phi'(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle \\ & =L\|y_{k+1}-x_{k+1}\|^{2}-\left\langle \nabla f(y_{k+1})-\nabla f(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle \\ & \overset{(**)}{=}\frac{1}{L}\left[\|\phi'(x_{k+1})-\left[\nabla f(x_{k+1})-\nabla f(y_{k+1})\right]\|^{2}\right]-\left\langle \nabla f(y_{k+1})-\nabla f(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle \\ & =\frac{1}{L}\left[\|\phi'(x_{k+1})\|^{2}-2\left\langle \phi'(x_{k+1}),\nabla f(x_{k+1})-\nabla f(y_{k+1})\right\rangle +\|\nabla f(x_{k+1})-\nabla f(y_{k+1})\|^{2}\right]\\ & \qquad-\left\langle \nabla f(y_{k+1})-\nabla f(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle \\ & =\frac{1}{L}\|\phi'(x_{k+1})\|^{2}-\frac{1}{L}\|\nabla f(x_{k+1})-\nabla f(y_{k+1})\|^{2}+\left\langle \nabla f(y_{k+1})-\nabla f(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle \\ & \geq\frac{1}{L}\|\phi'(x_{k+1})\|^{2}-L\|y_{k+1}-x_{k+1}\|^{2}+\left\langle \nabla f(y_{k+1})-\nabla f(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle \end{aligned}

On the other hand, summing (α)(\alpha) at (x,y)=(xk+1,yk+1)(x,y)=(x_{k+1},y_{k+1}) and (x,y)=(yk+1,xk+1)(x,y)=(y_{k+1},x_{k+1}) yields

−⟨∇f(yk+1)−∇f(xk+1),yk+1−xk+1⟩≤L∥yk+1−xk+1∥2.-\left\langle \nabla f(y_{k+1})-\nabla f(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle \leq L\|y_{k+1}-x_{k+1}\|^{2}.

Combining the two sets of relations gives us the important bound

(α′)⟨ϕ′(xk+1),yk+1−xk+1⟩≥1L∥ϕ′(xk+1)∥2.(\alpha')\qquad\left\langle \phi'(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle \geq\frac{1}{L}\|\phi'(x_{k+1})\|^{2}.

Verifying the Key Conditions

We now proceed by induction on conditions (Rk1)({\cal R}_{k}^{1}) and (Rk2)({\cal R}_{k}^{2}). Since they both trivially hold at iteration 00, suppose they hold for some k≥1k\geq1. Using (Rk2)({\cal R}_{k}^{2}) and the fact that convex functions are minorized by their first-order approximations we have

Ak+1Γk+1(u)+12∥u−x0∥2=AkΓk(u)+ak+1[ℓf(u;xk+1)+h(u)]+12∥u−x0∥2≤(Rk2)Akϕ(u)+ak+1[ℓf(u;xk+1)+h(u)]+12∥u−x0∥2≤(Ak+ak+1)ϕ(u)+12∥u−x0∥2=Ak+1ϕ(u)+12∥u−x0∥2,\begin{aligned} A_{k+1}\Gamma_{k+1}(u)+\frac{1}{2}\|u-x_{0}\|^{2} & =A_{k}\Gamma_{k}(u)+a_{k+1}\left[\ell_{f}(u;x_{k+1})+h(u)\right]+\frac{1}{2}\|u-x_{0}\|^{2}\\ & \overset{({\cal R}_{k}^{2})}{\leq}A_{k}\phi(u)+a_{k+1}\left[\ell_{f}(u;x_{k+1})+h(u)\right]+\frac{1}{2}\|u-x_{0}\|^{2}\\ & \leq(A_{k}+a_{k+1})\phi(u)+\frac{1}{2}\|u-x_{0}\|^{2}=A_{k+1}\phi(u)+\frac{1}{2}\|u-x_{0}\|^{2},\end{aligned}

for every u∈Rnu\in\mathbb{R}^{n}, which is exactly (Rk+12)({\cal R}_{k+1}^{2}). For (Rk+11)({\cal R}_{k+1}^{1}), let ϕ′(xk+1)∈∂ϕ(xk+1)\phi'(x_{k+1})\in\partial\phi(x_{k+1}) be as in (∗∗)(**) and recall that convexity of ϕ\phi implies that

(‡)ϕ(u)≥ϕ(xk+1)+⟨ϕ′(xk+1),u−xk+1⟩∀u∈Rn.(\ddagger)\qquad\phi(u)\geq\phi(x_{k+1})+\left\langle \phi'(x_{k+1}),u-x_{k+1}\right\rangle \quad\forall u\in\mathbb{R}^{n}.

We now use the relations in (β)(\beta) from two posts ago, condition (‡)(\ddagger) above, and the updates for yk+1,y_{k+1}, Ak+1,A_{k+1}, and Γk+1\Gamma_{k+1} to obtain

inf⁡u∈Rn{Ak+1Γk+1(u)+12∥u−x0∥2}=Γk+1inf⁡u∈Rn{AkΓk(u)+ak+1[ℓf(u;xk+1)+h(u)]+12∥u−x0∥2}≥(β)inf⁡u∈Rn{Akϕ(xk)+1+μAk2∥u−vk∥2+ak+1[ℓf(u;xk+1)+h(u)]}≥hinf⁡u∈Rn{Akϕ(xk)+1+μAk2∥u−vk∥2+ak+1[ϕ(xk+1)+⟨ϕ′(xk+1),u−xk+1⟩]}≥(‡)inf⁡u∈Rn{Ak+1ϕ(xk+1)+1+μAk2∥u−vk∥2+ak+1⟨ϕ′(xk+1),u−xk+1⟩+Ak⟨ϕ′(xk+1),xk−xk+1⟩}=yk+1inf⁡u∈Rn{Ak+1ϕ(xk+1)+1+μAk2∥u−vk∥2+ak+1⟨ϕ′(xk+1),u−xk+1⟩+⟨ϕ′(xk+1),Ak+1yk+1−ak+1vk−Akxk+1⟩}=inf⁡u∈Rn{Ak+1ϕ(xk+1)+1+μAk2∥u−vk∥2+ak+1⟨ϕ′(xk+1),u−vk⟩+Ak+1⟨ϕ′(xk+1),yk+1−xk+1⟩}.\begin{aligned} & \inf_{u\in\mathbb{R}^{n}}\left\{ A_{k+1}\Gamma_{k+1}(u)+\frac{1}{2}\|u-x_{0}\|^{2}\right\} \\ & \overset{\Gamma_{k+1}}{=}\inf_{u\in\mathbb{R}^{n}}\left\{ A_{k}\Gamma_{k}(u)+a_{k+1}\left[\ell_{f}(u;x_{k+1})+h(u)\right]+\frac{1}{2}\|u-x_{0}\|^{2}\right\} \\ & \overset{(\beta)}{\geq}\inf_{u\in\mathbb{R}^{n}}\left\{ A_{k}\phi(x_{k})+\frac{1+\mu A_{k}}{2}\|u-v_{k}\|^{2}+a_{k+1}\left[\ell_{f}(u;x_{k+1})+h(u)\right]\right\} \\ & \overset{h}{\geq}\inf_{u\in\mathbb{R}^{n}}\left\{ A_{k}\phi(x_{k})+\frac{1+\mu A_{k}}{2}\|u-v_{k}\|^{2}+a_{k+1}\left[\phi(x_{k+1})+\left\langle \phi'(x_{k+1}),u-x_{k+1}\right\rangle \right]\right\} \\ & \overset{(\ddagger)}{\geq}\inf_{u\in\mathbb{R}^{n}}\left\{ A_{k+1}\phi(x_{k+1})+\frac{1+\mu A_{k}}{2}\|u-v_{k}\|^{2}+\right.\\ & \qquad\qquad\left.a_{k+1}\left\langle \phi'(x_{k+1}),u-x_{k+1}\right\rangle +A_{k}\left\langle \phi'(x_{k+1}),x_{k}-x_{k+1}\right\rangle \right\} \\ & \overset{y_{k+1}}{=}\inf_{u\in\mathbb{R}^{n}}\left\{ A_{k+1}\phi(x_{k+1})+\frac{1+\mu A_{k}}{2}\|u-v_{k}\|^{2}+\right.\\ & \qquad\qquad\left.a_{k+1}\left\langle \phi'(x_{k+1}),u-x_{k+1}\right\rangle +\left\langle \phi'(x_{k+1}),A_{k+1}y_{k+1}-a_{k+1}v_{k}-A_{k}x_{k+1}\right\rangle \right\} \\ & =\inf_{u\in\mathbb{R}^{n}}\left\{ A_{k+1}\phi(x_{k+1})+\frac{1+\mu A_{k}}{2}\|u-v_{k}\|^{2}+\right.\\ & \qquad\qquad\left.a_{k+1}\left\langle \phi'(x_{k+1}),u-v_{k}\right\rangle +A_{k+1}\left\langle \phi'(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle \right\} .\end{aligned}

It is then straightforward to show that the minimum of the last problem is attained at

uk=vk−ak+11+μAkϕ′(xk+1).u_{k}=v_{k}-\frac{a_{k+1}}{1+\mu A_{k}}\phi'(x_{k+1}).

Substituting u=uku=u_{k} into the previous set of inequalities, and using the quadratic identity associated with ak+1a_{k+1} and the technical bound (α′)(\alpha'), we have that

inf⁡u∈Rn{Ak+1Γk+1(u)+12∥u−x0∥2}≥Ak+1ϕ(xk+1)−ak+122(1+μAk)∥ϕ′(xk+1)∥2+Ak+1⟨ϕ′(xk+1),yk+1−xk+1⟩=ak+1Ak+1[ϕ(xk+1)+⟨ϕ′(xk+1),yk+1−xk+1⟩−1L∥ϕ′(xk+1)∥2]≥(α′)Ak+1ϕ(xk+1),\begin{aligned} & \inf_{u\in\mathbb{R}^{n}}\left\{ A_{k+1}\Gamma_{k+1}(u)+\frac{1}{2}\|u-x_{0}\|^{2}\right\} \\ & \geq A_{k+1}\phi(x_{k+1})-\frac{a_{k+1}^{2}}{2(1+\mu A_{k})}\|\phi'(x_{k+1})\|^{2}+A_{k+1}\left\langle \phi'(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle \\ & \overset{a_{k+1}}{=}A_{k+1}\left[\phi(x_{k+1})+\left\langle \phi'(x_{k+1}),y_{k+1}-x_{k+1}\right\rangle -\frac{1}{L}\|\phi'(x_{k+1})\|^{2}\right]\\ & \overset{(\alpha')}{\geq}A_{k+1}\phi(x_{k+1}),\end{aligned}

which is exactly (Rk+11)({\cal R}_{k+1}^{1}). Consequently, the accelerated gradient method is an implementation of the Estimating Sequence Scheme.

Growth Rate of AkA_{k}

Before finishing with some remarks, let us establish the growth rate of AkA_{k}. We claim that

Ak≥max⁡{k22L,2L[1+μ2L]2(k−1)},A_{k}\geq\max\left\{ \frac{k^{2}}{2L},\frac{2}{L}\left[1+\sqrt{\frac{\mu}{2L}}\right]^{2(k-1)}\right\},

which proves that this method is indeed an accelerated one (see the previous posts). To show this, we first suppose that μ=0\mu=0. Then, the quadratic associated with ak+1a_{k+1} implies that

Ak+1≤Ak+1(1+μAk)=ak+1L2(Ak+1−Ak)2=L2(Ak+11/2−Ak1/2)2(Ak+11/2+Ak1/2)2≤2Ak+1L(Ak+11/2−Ak1/2)2\begin{aligned} A_{k+1} & \leq A_{k+1}(1+\mu A_{k})\overset{a_{k+1}}{=}\frac{L}{2}(A_{k+1}-A_{k})^{2}=\frac{L}{2}(A_{k+1}^{1/2}-A_{k}^{1/2})^{2}(A_{k+1}^{1/2}+A_{k}^{1/2})^{2}\\ & \leq2A_{k+1}L(A_{k+1}^{1/2}-A_{k}^{1/2})^{2}\end{aligned}

and, hence, dividing by Ak+1A_{k+1} and applying the recursion yields Ak1/2≥k/2LA_{k}^{1/2}\geq k/\sqrt{2L}. Now suppose μ>0\mu>0. By the same argument, we have

μAkAk+1<Ak+1(1+μAk)≤2Ak+1L[Ak+11/2−Ak1/2]2\mu A_{k}A_{k+1}<A_{k+1}(1+\mu A_{k})\leq2A_{k+1}L\left[A_{k+1}^{1/2}-A_{k}^{1/2}\right]^{2}

and, hence, Ak+11/2≥Ak1/2[1+μ/2L]A_{k+1}^{1/2}\geq A_{k}^{1/2}\left[1+\sqrt{\mu/2L}\right]. Since A1=2/LA_{1}=2/L, the bound on AkA_{k} follows.

Interactive Experiment (Powered by Proxax)

Adjust the condition number κ=L/μ\kappa = L/\mu and iteration count below to compare unaccelerated gradient descent, the dual gradient method (Part III), and accelerated gradient descent—the core foundation behind the parameter-free px.solvers.APD solver in Proxax.

Interactive Demo Powered by Proxax

Gradient Descent vs. Dual Gradient vs. Accelerated Gradient (Proxax APD)

Gradient Descent (1/L) Dual Gradient (Part III) Accelerated Gradient / Proxax APD
2D Contours of f(x₁, x₂) = ½(x₁² + κx₂²)
Suboptimality log₁₀(f(xₖ) − f*) vs. Iteration k
Run this problem in Python / JAX with Proxax (parameter-free px.solvers.APD)
import jax.numpy as jnp
from proxax import px

kappa = 25.0  # L / mu
def quadratic(x):
  return 0.5 * (x[0] ** 2 + kappa * x[1] ** 2)

problem = px.CompositeProblem(smooth=quadratic)
sol = px.solve(
    problem=problem,
    x0=jnp.array([-2.2, 0.85]),
    solver=px.solvers.APD(opt_tol=1e-6),
)
print(sol.status_enum.name, sol.iters, sol.obj)

Proxax implements certified, parameter-free accelerated solvers (px.solvers.APD, IALM, DAICG, DPADMM) in pure JAX & Optax without needing to know L or μ beforehand.

Remark IV.1. The accelerated gradient method shares a few similarities with the dual gradient method. For example, its minorant Γk\Gamma_{k} is a convex combination of the first-order approximations ℓf(⋅;xˉ)+h(⋅)\ell_{f}(\cdot;\bar{x})+h(\cdot) at various centering points xˉ\bar{x}, the main iterate sequence {xk}k≥0\{x_{k}\}_{k\geq0} is generated by a primal (proximal) gradient step, and the definition of vkv_{k} is the same as in the dual gradient method.

Remark IV.2. On the other hand, the main difference between the two methods is that Γk\Gamma_{k} in the accelerated method is an unbalanced convex combination of the first-order approximations, with larger weights placed on later iterations. Also, the prox center used in the computation of xkx_{k} is based on a convex combination of xk−1x_{k-1} and vk−1v_{k-1} rather than just vk−1v_{k-1}. Finally, the growth of Ak+1A_{k+1} is the same order as an accelerated method (as defined a few posts ago), making convergence of this method much faster than the dual method.

Remark IV.3. Compared to the analysis of the dual gradient method, the analysis of the accelerated method strongly uses convexity (see the underlined text above) in the proof for both (Rk1)({\cal R}_{k}^{1}) and (Rk2)({\cal R}_{k}^{2}).

Discussion