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