The previous post detailed a bunch of different ways of proving the convergence rate of gradient descent:

for strongly convex problems. This post considers the non-strongly convex, but still convex case.

Rehash of Basic Lemmas

These hold for any $x$ and $y$. $L$ the Lipschitz smoothness constant. These are completely standard, see Nesterov’s book [2] for proofs. We use the notation $x^{\ast }$ for an arbitrary minimizer of $f$.

$$f\left(y\right)\le f\left(x\right)+⟨f^{\prime }\left(x\right),y-x⟩+\frac{L}{2}{∥x-y∥}^2.$$

(1)

$$f\left(y\right)\ge f\left(x\right)+⟨f^{\prime }\left(x\right),y-x⟩+\frac{1}{2L}{∥f^{\prime }\left(x\right)-f^{\prime }\left(y\right)∥}^2.$$

(2)

$$⟨f^{\prime }\left(x\right)-f^{\prime }\left(y\right),x-y⟩\ge \frac{1}{L}{∥f^{\prime }\left(x\right)-f^{\prime }\left(y\right)∥}^2.$$

(3)

1 Proximal Style Convergence Proof

The following argument gives a proof of convergence that is well suited to modification for proving the convergence of proximal gradient methods. We start by proving a useful lemma:

Using this lemma, the proof is quite simple. We apply it with $y=x^{\ast }$:

Now we sum this between $0$ and $k-1$. The left hand side telescopes:

Now we use the fact that gradient descent is a descent method, which implies that $f\left(x_k\right)\le f\left(x_{r+1}\right)$ for all $r\le k-1$. So:

Now we just drop the ${∥x_k-x^{\ast }∥}^2$ term since it is positive and small. Leaving:

Comments

As far as I know, this proof is fairly modern [1]. Notice that unlike the strongly convex case, the quantity we are bounding $\left(f\left(x_k\right)-f\left(x^{\ast }\right)\right)$ does not appear on both sides of the bound. Unfortunately, without strong convexity there is necessarily a looseness to the bounds, and this takes the form of bounding function value by distance to solution, with a large wiggle-factor. One thing that is perhaps a little confusing is the use of distance to solution $x-x^{\ast }$, when it is not unique, as there are potentially multiple minimizers for non-strongly convex problems. The bound in fact holds for any chosen minimizer $x^{\ast }$. I found this to be a little confusing at first.

2 Older Style Proof

This proof is from Nesterov [2]. I’m not sure of the original source for it.

We start with the function value descent equation, using $w:=\left[\alpha \left(1-\frac{1}{2}\alpha L\right)\right]:$

We introduce the simplified notation ${\Delta }_k=f\left(x_k\right)-f\left(x^{\ast }\right)$ so that we have

$${\Delta }_{k+1}\le {\Delta }_k-w{∥f^{\prime }\left(x_k\right)∥}^2.$$

(4)

Now using the convexity lower bound around $x_k$ evaluated at $x^{\ast }$, namely:

and applying Cauchy-Schwarz (note the spelling! there is no “t” in Schwarz) to it:

$$\begin{array}{rcll}{\Delta }_k& \le & ∥x_k-x^{\ast }∥∥f^{\prime }\left(x_k\right)∥& \\ & \le & ∥x_0-x^{\ast }∥∥f^{\prime }\left(x_k\right)∥.& \end{array}$$

The last line is because gradient descent method descends in iterate distance each step. We now introduce the additional notation $r_0=∥x_0-x^{\ast }∥$. Using this notation and rearranging gives:

We plug this into the function descent equation (Eq 4) above to get:

We now divide this through by ${\Delta }_{k+1}$:

Then divide through by ${\Delta }_k$ also:

Now we use the fact that gradient descent is a descent method again, which implies that $\frac{{\Delta }_k}{{\Delta }_{k+1}}\le 1,$ so:

We then chain this inequality for each $k$:

To get the final convergence rate we invert both sides:

This is quite a complex expression. To simplify even further, we can get rid of the $f\left(x_0\right)-f\left(x^{\ast }\right)$ terms on the right hand side using the Lipschitz upper bound about $x^{\ast }$:

Plugging in the step size $\alpha =\frac{1}{L}$ gives $w=\frac{1}{2L}$, yielding the following simpler convergence rate:

Compared to the rate from the previous proof, $f\left(x_k\right)-f\left(x^{\ast }\right)\le \frac{L}{2k}{∥x^0-x^{\ast }∥}^2$, this is slightly better at $k=1$, and worse thereafter.

Comments

I don’t like this proof. It’s feels like a random sequence of steps when you first look at it. The way the proof uses inverse quantities like $\frac{1}{{\Delta }_k}$ is also confusing. The key equation is really the direct bound on $\Delta$:

Often this is the kind of equation you encounter when proving the properties of dual methods for example. Equations of this kind can be encountered when applying proximal methods to non-differentiable functions also. It is also quite a clear statement about what is going on in terms of per-step convergence, a property that is less clear in the previous proof.

3 Gradient Concentration

When we don’t even have convexity, just Lipschitz smoothness, we can still prove something about convergence of the gradient norm. The Lipschitz upper bound holds without the requirement of convexity:

Recall that from minimizing this bound with respect to $y$ we can prove the equation:

Examine this equation carefully. We have a bound on each gradient encountered during the optimization in terms of the difference in function values between steps. The sequence of function values is bounded below, so in fact we have a hard bound on the sum of the encountered gradient norms. Effectively, we chain (telescope) the above inequality over steps:

Now since $f\left(x_{k+1}\right)\ge f\left(x^{\ast }\right)$:

Now to make this bound a little more concrete, we can put it in terms of the gradient $g_k$ with the smallest norm seen during the minimization ($∥g_k∥\le ∥g_i∥$ for all $i$), so that ${\sum }_i^k{∥f^{\prime }\left(x_i\right)∥}^2\ge k{∥g_k∥}^2$, so:

Comments

Notice that the core technique used in this proof is the same as the last 2 proofs. We have a single step inequality bounding one of the quantities we care about. By summing that inequality over each step of minimization, one side of the inequality telescopes. We get an equality saying the the sum of the $k$ versions of that quantity (one from each step) is less then some fixed constant independent of $k$, for any $k$. The convergence rate is thus of the form $1∕k$, because the summation of the $k$ quantities fits in a fixed bound.

Almost any proof for an optimization method that applies in the non-convex case uses a similar proof technique. There is just not that many assumptions to work with, so the options are limited.

References