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

Consider the classical gradient descent method:

It’s a thing of beauty isn’t it? While it’s not used directly in practice any more, the proof techniques used in its analysis are the building blocks behind the theory of more advanced optimization methods. I know of 8 different ways of proving its convergence rate. Each of the proof techniques are interesting in their own right, but most books on convex optimization give just a single proof of convergence, then move onto greater things. But to do research in modern convex optimization you should know them all.

The purpose of this series of posts is to detail each of these proof techniques and what applications they have to more advanced methods. This post will cover the proofs under strong convexity assumptions, and the next post will cover the non-strongly convex case. Unlike most proofs in the literature, we will go into detail of every step, so that these proofs can be used as a reference (don’t cite this post directly though, cite the original source preferably, or the technical notes version). If you are aware of any methods I’ve not covered, please leave a comment with a reference so I can update this post.

For most of the proofs we end with a statement like $A_{k+1}\le \left(1-\gamma \right)A_k$, where $A_k$ is some quantity of interest, like distance to solution or function value sub-optimality. A full proof requires chaining these inequalities for each $k$, giving something of the form $A_k\le {\left(1-\gamma \right)}^k{A}_0$. We leave this step as a given.

Basic lemmas

These hold for any $x$ and $y$. Here $\mu$ is the strong convexity constant and $L$ the Lipschitz smoothness constant. These are completely standard, see Nesterov’s book [7] for proofs. We use the notation $x^{\ast }$ for the unique minimizer of $f$ (for strongly convex problems).

$$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{\mu }{2}{∥x-y∥}^2.$$

(2)

$$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.$$

(3)

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

(4)

$$⟨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.$$

(5)

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

(6)

1 Function Value Descent

There is a very simple proof involving just the function values. We start by showing that the function value descent is controlled by the gradient norm:

Now since we are considering strongly convex problems, we actually have found a bound on the gradient norm in terms of function value. We apply (4): $f\left(y\right)\le f\left(x\right)+⟨f^{\prime }\left(x\right),y-x⟩+\frac{1}{2\mu }{∥f^{\prime }\left(x\right)-f^{\prime }\left(y\right)∥}^2$ using $x=x^{\ast }$, $y=x_k$:

So combining these two results:

We then negate, add & subtract $f\left(x^{\ast }\right)$, then rearrange:

Note that this function value style proof requires the step size $\alpha =\frac{1}{L}$ or smaller, instead of $\alpha =\frac{2}{\mu +L}$, which we shall see gives the fastest convergence when using some of the other proof techniques below.

Comments

This proof (when $\alpha =\frac{1}{L}$ is used) treats gradient descent as an upper bound minimization scheme. Such methods, sometimes known under the Majorization-Minimization nomenclature [3], are quite widespread in optimization. They can be applied to non-convex problems even, although the convergence rates in that case are necessarily weak. Likewise this proof gives the weakest convergence rate of the proof techniques presented in this post, but it is perhaps the simplest. Upper bound minimization techniques have recently seen interesting applications in 2nd order optimization, in the form of Nesterov’s cubicly regularized Newton’s method [9]. For stochastic optimization, the MISO method is also a upper bound minimization scheme [6]. For non-smooth problems, an interesting application of the MM approach is in minimizing convex problems with non-convex regularizers of the form $\lambda log\left(\left|x\right|+1\right)$, in the form of reweighted L1 regularization [5].

2 Iterate Descent

There is also a simple proof involving just the distance of the iterates $x_k$ to the solution. Using the definition of the step $x_{k+1}-x_k=-\alpha f^{\prime }\left(x_k\right)$:

$$\begin{array}{rcll}{∥x_{k+1}-x^{\ast }∥}^2& =& {∥x_k-\alpha f^{\prime }\left(x_k\right)-x^{\ast }∥}^2& \\ & =& {∥x_k-x^{\ast }∥}^2-2\alpha ⟨f^{\prime }\left(x_k\right),x_k-x^{\ast }⟩+{\alpha }^2{∥f^{\prime }\left(x_k\right)∥}^2.& \end{array}$$

We now apply both the inner product bounds (5) $⟨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$and (6) $⟨f^{\prime }\left(x\right)-f^{\prime }\left(y\right),x-y⟩\ge \mu {∥x-y∥}^2$ , in the following negated forms, using $f^{\prime }\left(x^{\ast }\right)=0$:

The inner product term has a weight $2\alpha$, and we apply each of these with weight $\alpha$, giving:

Now if we take $\alpha =\frac{1}{L},$ then the last term cancels and we have:

This proof is not as tight as possible. Instead of splitting the inner product term and applying both bounds (5) and (6), we can apply the following stronger combined bound from Nesterov’s Book [7]:

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

(7)

Doing so yields:

Now clearly to cancel out the gradient norm term we can take $\alpha =\frac{2}{\mu +L}$, which yields the convergence rate:

$$\begin{array}{rcll}{∥x_{k+1}-x^{\ast }∥}^2& \le & \left(1-\frac{4\mu L}{{\left(\mu +L\right)}^2}\right){∥x_k-x^{\ast }∥}^2& \\ & \approx & \left(1-\frac{4\mu }{L}\right){∥x_k-x^{\ast }∥}^2.& \end{array}$$

Comments

This proof technique is the building block of the standard stochastic gradient descent (SGD) proof. The above proof is mostly based on Nesterov’s book, I’m not sure what the original citation is. It has a nice geometric interpretation, as the bound on the inner product term $⟨f^{\prime }\left(x_k\right),x_k-x^{\ast }⟩$ can easily be illustrated in 2 dimensions, say on a white-board. It’s effectively a statement on the angles that gradients in convex problems can take. To get the strongest bound using this technique, the complex bound in Equation 7 has to be used. That stronger bound is not really straight-forward, and perhaps too technical (in my opinion) to use in a textbook proof of the convergence rate.

3 Using the Second Fundamental Theorem of Calculus

Recall the second fundamental theorem of calculus:

This can be applied along intervals in higher dimensions. The case we care about is applying it to the first derivatives of $f$, giving an integral involving the Hessian:

We abuse the angle bracket notation here to apply to matrix-vector products as well as the usual dot-product. Using this result gives an interesting proof of convergence of gradient descent that doesn’t rely on the usual convexity lemmas. This proof bounds the distance to solution, just like the previous proof.

Using this lemma gives a simple proof along the lines of the iterate descent proof.

First, note that $∥x_{k+1}-x^{\ast }∥$ is in the right form for direct application of this lemma after substituting in the step equation:

$$\begin{array}{rcll}∥x_{k+1}-x^{\ast }∥& =& ∥x_k-x^{\ast }+\alpha \left(f^{\prime }\left(x_k\right)-f^{\prime }\left(x^{\ast }\right)\right)∥& \\ & \le & max\left\{\left|1-\alpha L\right|,\left|1-\alpha \mu \right|\right\}∥x_k-x^{\ast }∥.& \end{array}$$

Note we introduced $f^{\prime }\left(x^{\ast }\right)$ for “free”, as it’s of course equal to zero. The next step is optimize this bound in terms of $\alpha$. Note that $L$ is always larger than $\mu$, so we take the $\left|1-\alpha L\right|$ absolute value as negative, and the other positive, and match their magnitudes:

Which gives the convergence rate:

Note that this rate is in terms of the distance to solution directly, rather than its square like in the previous proof. Converting to squared norm gives the same rate as before.

Comments

This proof technique has a linear-algebra feel to it, and is perhaps most comfortable to people with that background. The absolute values make it ugly in my opinion though. This proof technique is the building block used in the standard proof of the convergence of the heavy ball method for strongly convex problems [10]. It doesn’t appear to have many other applications, and so is probably the least seen of the techniques in this document. The main use of this kind of argument is in lower complexity bounds, where we often do some sort of eigenvalue analysis.

4 Lyapunov Style

The above results prove convergence of either the iterates or the function value separately. There is an interesting proof involving the sum of the two quantities. First we start with with the iterate convergence:

$$\begin{array}{rcll}{∥x_{k+1}-x^{\ast }∥}^2& =& {∥x_k-x^{\ast }-\alpha f^{\prime }\left(x_k\right)∥}^2& \\ & =& {∥x_k-x^{\ast }∥}^2-2\alpha ⟨f^{\prime }\left(x_k\right),x_k-x^{\ast }⟩+{\alpha }^2{∥f^{\prime }\left(x_k\right)∥}^2.& \end{array}$$

Now we use the function descent amount equation (Lemma 1) to bound the gradient norm term: $\frac{1}{c}{∥f^{\prime }\left(x_k\right)∥}^2\le f\left(x_k\right)-f\left(x_{k+1}\right)$ , where we have defined $c=1∕\left[\alpha \left(1-\frac{1}{2}\alpha L\right)\right]$:

Now we use the strong convexity lower bound (2) in a rearranged form:

$$\begin{array}{rcll}⟨f^{\prime }\left(x_k\right),x^{\ast }-x_k⟩& \le & f\left(x^{\ast }\right)-f\left(x_k\right)-\frac{\mu }{2}{∥x_k-x^{\ast }∥}^2,& \end{array}$$

to simplify:

Now rearranging further:

Now this equation gives a descent rate for the weighted sum of ${∥x_k-x^{\ast }∥}^2$ and $f\left(x_k\right)-f\left(x^{\ast }\right).$ The best rate is given by matching the two convergence rates, that of the iterate distance terms:

and that of the function value terms, which changes from $c{\alpha }^2$ to $c{\alpha }^2-2\alpha$:

$$\begin{array}{rcll}\frac{c{\alpha }^2-2{\alpha }_k}{c{\alpha }^2}& =& 1-\frac{2}{c\alpha }& \\ & =& 1-2\left(1-\frac{1}{2}\alpha L\right)& \\ & =& \alpha L-1.& \end{array}$$

Matching these two rates:

Using this derived value for $\alpha$ gives a convergence rate of $1-\frac{2\mu }{\mu +L}$. I.e.

and therefore after $k$ steps:

The constants can be simplified to:

$$\begin{array}{rcll}c{\alpha }^2& =& \frac{{\alpha }^2}{\alpha \left(1-\frac{1}{2}\alpha L\right)}& \\ & =& \frac{\alpha }{1-\frac{1}{2}\alpha L}& \\ & =& \frac{\alpha }{1-\frac{L}{\mu +L}}& \\ & =& \frac{\alpha }{\frac{\mu }{\mu +L}}& \\ & =& \frac{2}{\mu }.& \end{array}$$

Now we use: $f\left(x^0\right)-f\left(x^{\ast }\right)\le \frac{L}{2}{∥x^0-x^{\ast }∥}^2$ on the right, and we just drop the function value term altogether on the left:

$$\begin{array}{rcll}{∥x_k-x^{\ast }∥}^2& \le & {\left(1-\frac{2\mu }{\mu +L}\right)}^k\frac{\mu +L}{\mu }{∥x_0-x^{\ast }∥}^2.& \end{array}$$

If we instead use the more robust step size $\frac{1}{L}$, which doesn’t require knowledge of $\mu$, then a simple calculation shows that we instead get $c=2L$, and so:

$$\begin{array}{rcll}{∥x_k-x^{\ast }∥}^2& \le & {\left(1-\frac{\mu }{L}\right)}^k\left[{∥x_0-x^{\ast }∥}^2+\frac{2}{L}\left[f\left(x_0\right)-f\left(x^{\ast }\right)\right]\right],& \\ & \le & {\left(1-\frac{\mu }{L}\right)}^{k}2{∥x_0-x^{\ast }∥}^2.& \end{array}$$

The right hand side is obviously a much tighter bound then when $2∕\left(\mu +L\right)$ is used, but the geometric rate is roughly twice as slow.

Comments

This proof technique has seen a lot of application lately. It is used for the SAGA [2]and SVRG [4] methods, and can be applied to accelerated method even, such as the accelerated coordinate descent theory [8]. The Lyapunov function analysis technique is of great general utility, and so it is worth studying carefully. It is covered perhaps best in Polyak’s book [10].

5 Gradient Norm Descent

In the strongly convex case, it is actually possible to show that the gradient norm decreases at least linearly as well as the function value and iterates. This requires a fixed step size of $\alpha =\frac{1}{L}$, as it is not true when line searches are used.

Chaining this result (Lemma 3) over $k$ gives:

$$\begin{array}{rcll}{∥x_{k+1}-x_k∥}^2& \le & {\left(1-\frac{\mu }{L}\right)}^k{∥x_1-x_0∥}^2& \\ & =& {\left(1-\frac{\mu }{L}\right)}^k\frac{1}{L^2}{∥f^{\prime }\left(x_0\right)∥}^2.& \end{array}$$

We now use $f\left(x_k\right)-f\left(x^{\ast }\right)\le \frac{1}{2\mu }{∥f^{\prime }\left(x_k\right)∥}^2=\frac{L^2}{2\mu }{∥x_{k+1}-x_k∥}^2:$

Comments

This technique is probably the weirdest of those listed here. It has seen application in proving the convergence rate of MISO under some different stochastic orderings [1]. While clearly a primal result, this proof has some components normally seen in the proof for a dual method. The gradient $f^{\prime }\left(x_k\right)$ is effectively the dual iterate. Another interesting property is that the portion of the proof concerning the gradient’s convergence uses the strong convexity between $x_{k+1}$ and $x_k$, whereas the other proofs considered all use the degree of strong convexity between $x_k$ and $x^{\ast }$.

This proof technique can’t work when line searches are used, as bounding the inner product:

would fail if $\alpha$ changed between steps, as it would become $⟨{\alpha }_k{f}^{\prime }\left(x_k\right)-{\alpha }_{k+1}{f}^{\prime }\left(x_{k+1}\right),x_{k+1}-x_k⟩$, which is a weird expression to work with.

References