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
Choose x0∈domh and define Γ0(⋅)≡0. Set A0=0, v0=x0, and y0=x0.
For k=1,…
Find ak satisfying the quadratic equation ak2/(Ak−1+ak)=2(1+μAk−1)/L.
Combining the two sets of relations gives us the important bound
(α′)⟨ϕ′(xk+1),yk+1−xk+1⟩≥L1∥ϕ′(xk+1)∥2.
Verifying the Key Conditions
We now proceed by induction on conditions (Rk1) and (Rk2). Since they both trivially hold at iteration 0, suppose they hold for some k≥1. Using (Rk2) and the fact that convex functions are minorized by their first-order approximations we have
It is then straightforward to show that the minimum of the last problem is attained at
uk=vk−1+μAkak+1ϕ′(xk+1).
Substituting u=uk into the previous set of inequalities, and using the quadratic identity associated with ak+1 and the technical bound (α′), we have that
which is exactly (Rk+11). Consequently, the accelerated gradient method is an implementation of the Estimating Sequence Scheme.
Growth Rate of Ak
Before finishing with some remarks, let us establish the growth rate of Ak. We claim that
Ak≥max{2Lk2,L2[1+2Lμ]2(k−1)},
which proves that this method is indeed an accelerated one (see the previous posts). To show this, we first suppose that μ=0. Then, the quadratic associated with ak+1 implies that
and, hence, dividing by Ak+1 and applying the recursion yields Ak1/2≥k/2L. Now suppose μ>0. By the same argument, we have
μAkAk+1<Ak+1(1+μAk)≤2Ak+1L[Ak+11/2−Ak1/2]2
and, hence, Ak+11/2≥Ak1/2[1+μ/2L]. Since A1=2/L, the bound on Ak follows.
Interactive Experiment (Powered by Proxax)
Adjust the condition number κ=L/μ 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.
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 is a convex combination of the first-order approximations ℓf(⋅;xˉ)+h(⋅) at various centering points xˉ, the main iterate sequence {xk}k≥0 is generated by a primal (proximal) gradient step, and the definition of vk 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 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 xk is based on a convex combination of xk−1 and vk−1 rather than just vk−1. Finally, the growth of Ak+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) and (Rk2).