0x00 Preface

This post analyzes deterministic first-order optimization methods. Basic definitions are in Part 11. We default to the Euclidean norm and distinguish between gradient descent and the subgradient method for non-smooth problems.

The smooth section discusses unconstrained problems; the non-smooth section allows a closed convex feasible set $\mathcal C$, using projections to keep iterates within the feasible set. Assume an optimal solution $w^{\ast}$ exists, $f^{\ast}=f(w^{\ast})$.

0x01 Definition of Convergence

First, we must specify what error we are measuring:

  • Function value error: $f(w_T)-f^{\ast}$.
  • Distance to the optimal solution: $\Vert w_T-w^{\ast}\Vert^2$; if there are multiple optimal solutions, one can also discuss the distance to the set of optimal solutions.
  • Stationarity measure in non-convex problems: $\min_{0\le t<T}\Vert\nabla f(w_t)\Vert^2$, or the average of squared gradient norms.

These metrics cannot be arbitrarily interchanged. A small gradient norm does not imply finding a global optimum, nor does it alone guarantee that the iteration sequence converges to a specific point.

Linear convergence typically refers to an error upper bound of $Cq^T$, $0<q<1$; $O(1/T)$ and $O(1/\sqrt T)$ belong to sublinear convergence. For a positive error sequence $e_t$, Q-superlinear convergence means $e_{t+1}/e_t\to0$, while Q-quadratic convergence requires that eventually $e_{t+1}\le Ce_t^2$. We do not use $\log\log e_t$ to describe quadratic convergence because when $e_t<1$, this real-valued expression is undefined.

The complexities below refer to the number of iterations required to guarantee that the corresponding error does not exceed $\epsilon$; constants depend on the objective function and the starting point.

0x02 Smooth Strongly Convex with GD

defination

If $f$ is $L$-smooth and $\mu$-strongly convex, using a fixed step size $0<\eta\le1/L$, then
$$ f(w_T)-f^*\le(1-\eta\mu)^T(f(w_0)-f^*). $$

By the descent lemma and the update $w_{t+1}=w_t-\eta\nabla f(w_t)$:

$$ \begin{aligned} f(w_{t+1})-f(w_t) &\le-\eta\left(1-\frac{L\eta}{2}\right)\|\nabla f(w_t)\|^2\\ &\le-\frac\eta2\|\nabla f(w_t)\|^2 \le-\eta\mu(f(w_t)-f^*). \end{aligned} $$

The final step uses the PL inequality. Rearranging yields a single-step recurrence; iterating $T$ times suffices.

When $\eta=1/L$, $\mu<L$, setting $E_0=f(w_0)-f^{\ast}$ gives $f(w_T)-f^{\ast}\le e^{-\mu T/L}E_0$, so $T\ge(L/\mu)\log(E_0/\epsilon)$ is sufficient. The condition number is $L/\mu$; this result exhibits linear convergence. If $\mu=L$, the above recurrence yields zero error in a single step.

0x03 Smooth Convex with GD

defination

If $f$ is convex and $L$-smooth, using $\eta=1/L$, then for $T\ge1$,
$$ f(w_T)-f^*\le\frac{L\|w_0-w^*\|^2}{2T}. $$

Let $R_t=\Vert w_t-w^{\ast}\Vert$. By convexity and the distance identity of the update,

$$ f(w_t)-f^*\le\langle\nabla f(w_t),w_t-w^*\rangle =\frac{R_t^2-R_{t+1}^2}{2\eta}+\frac\eta2\|\nabla f(w_t)\|^2. $$

Adding the descent lemma, the squared gradient term cancels when $\eta=1/L$:

$$ f(w_{t+1})-f^*\le\frac L2(R_t^2-R_{t+1}^2). $$

Summing from $t=0$ to $T-1$ yields $\sum_{t=0}^{T-1}(f(w_{t+1})-f^{\ast})\le LR_0^2/2$. Since the function value is monotonically non-increasing under this step size, the left-hand side is at least $T(f(w_T)-f^{\ast})$, proving the claim. The iteration complexity is $O(LR_0^2/\epsilon)$, which is sublinear convergence.

0x04 Non-smooth Convex with Subgradient Method

Assume $f$ is convex, using

$$ w_{t+1}=\Pi_{\mathcal C}(w_t-\eta_tg_t),\qquad g_t\in\partial f(w_t),\quad\|g_t\|\le G. $$

$\Pi_{\mathcal C}$ denotes the Euclidean projection; in the unconstrained case, simply omit the projection. We only require that the chosen subgradient is bounded; do not mistakenly call this condition smoothness.

Fixed Step Size for a Given Horizon

Let $R=\Vert w_0-w^{\ast}\Vert>0$. Given a priori $T\ge1$, take a fixed step size $\eta=R/(G\sqrt T)$, then

$$ \min_{0\le t<T}(f(w_t)-f^*)\le\frac{GR}{\sqrt T}. $$

If only an upper bound on the initial distance is known, use that bound to set the step size; if the starting point is already optimal, stop immediately.

Projection does not increase the distance to $w^{\ast}\in\mathcal C$, hence

$$ R_{t+1}^2\le R_t^2-2\eta(f(w_t)-f^*)+\eta^2G^2. $$

Summing and dividing by $2\eta T$:

$$ \min_{0\le t<T}(f(w_t)-f^*) \le\frac{R^2}{2\eta T}+\frac{\eta G^2}{2} =\frac{GR}{\sqrt T}. $$

Therefore, $T\ge G^2R^2/\epsilon^2$ is sufficient. This conclusion constrains the best iterate; by Jensen’s inequality, the unweighted average point also satisfies the same function value bound, but the last point is not guaranteed to have the same bound.

Polyak Step Size

If $f^{\ast}$ is known and optimality has not yet been reached, one can take

$$ \eta_t=\frac{f(w_t)-f^*}{\|g_t\|^2}. $$

Convexity provides the inequality $\langle g_t,w_t-w^{\ast}\rangle\ge f(w_t)-f^{\ast}$. Substituting into the distance recurrence yields

$$ R_{t+1}^2\le R_t^2-\frac{(f(w_t)-f^*)^2}{\|g_t\|^2}. $$

Summing and using $\Vert g_t\Vert\le G$ gives $\sum_{t=0}^{T-1}(f(w_t)-f^{\ast})^2\le G^2R^2$, so the best function value error is also bounded by $GR/\sqrt T$. If $g_t=0$, convexity implies this point is already optimal; in this case, do not compute a step size with a zero denominator. In practice, $f^{\ast}$ is often unknown, so this is a step-size rule requiring additional information.

0x05 Smooth Non-convex with GD

Assume $f$ is $L$-smooth and has a finite lower bound $f_{\inf}$. Take $\eta=1/L$; the descent lemma gives

$$ f(w_{t+1})\le f(w_t)-\frac1{2L}\|\nabla f(w_t)\|^2. $$

Summing from $t=0$ to $T-1$:

$$ \frac1T\sum_{t=0}^{T-1}\|\nabla f(w_t)\|^2 \le\frac{2L(f(w_0)-f_{\inf})}{T}. $$

The best squared gradient also does not exceed this bound. Achieving $\Vert\nabla f\Vert^2\le\epsilon$ requires $O(1/\epsilon)$ iterations; if the target is $\Vert\nabla f\Vert\le\epsilon$, then $O(1/\epsilon^2)$. This is not a guarantee on the error of the global optimum value.

0x06 Strongly Convex and Non-smooth with Subgradient Method

Let $f$ be $\mu$-strongly convex on the closed convex feasible set $\mathcal C$, with the optimal solution attained in $\mathcal C$. Along the projected subgradient iteration, we have $\Vert g_t\Vert\le G$. Here, we do not require strong convexity and function value Lipschitz continuity simultaneously over the entire space.

Take $\eta_t=2/(\mu(t+2))$; for $T\ge1$, we have

$$ \min_{0\le t<T}(f(w_t)-f^*)\le\frac{2G^2}{\mu(T+1)}. $$

Proof: The subgradient inequality for strong convexity combined with projection yields

$$ R_{t+1}^2\le(1-\mu\eta_t)R_t^2-2\eta_t(f(w_t)-f^*)+\eta_t^2G^2. $$

Substitute the step size and rearrange:

$$ f(w_t)-f^*\le\frac\mu4\left[tR_t^2-(t+2)R_{t+1}^2\right]+\frac{G^2}{\mu(t+2)}. $$

Multiply by $t+1$ and sum; the distance terms telescope away, yielding

$$ \begin{aligned} \sum_{t=0}^{T-1}(t+1)(f(w_t)-f^*) &\le-\frac\mu4T(T+1)R_T^2 +\frac{G^2}{\mu}\sum_{t=0}^{T-1}\frac{t+1}{t+2}\\ &\le\frac{TG^2}{\mu}. \end{aligned} $$

Dividing by $\sum_{t=0}^{T-1}(t+1)=T(T+1)/2$ gives the conclusion. The average point with equal weights also satisfies this function value bound. Its rate is $O(1/T)$, still sublinear.

0x07 Conclusion

Condition and MethodMetric Guaranteed in This PaperOrder of Error Upper Bound
Smooth strongly convex, GDFunction value error at the last iterate$O((1-\mu/L)^T)$
Smooth convex, GDFunction value error at the last iterate$O(1/T)$
Nonsmooth convex, subgradient methodFunction value error at the best point or average point$O(1/\sqrt T)$
Smooth nonconvex, GDAverage squared gradient$O(1/T)$
Nonsmooth strongly convex, projected subgradient methodFunction value error at the best point or weighted average point$O(1/T)$

These conclusions rely separately on the step sizes, lower bounds, existence of optimal solutions, or subgradient bounds discussed above; they cannot be applied merely by following the ‘convex/nonconvex’ labels. General nonsmooth nonconvex problems require alternative algorithms and concepts of stationary points.

Reference

Sources: 2 3 4 5.

  1. Part 1 ↩︎

  2. Boyd, S., Subgradient Methods. ↩︎

  3. Boyd, S. and Vandenberghe, L., Convex Optimization, Chapter 9. ↩︎

  4. Beck, A., First-Order Methods in Optimization. ↩︎

  5. Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course. ↩︎