Convergence of gradient descent for smooth and convex case

$$

We provided the proof of convergence of gradient descent algorithm for smooth and nonconvex case in our article on Convergence of Gradient Descent for Smooth and Nonconvex Case.

In this article, we will provide a different flavor and provide the convergence bound when the function is smooth and convex.

A quick recap:

Gradient descent is a widely used optimization algorithm that aims to find the minimum of a given function by iteratively updating its parameters in the direction of the negative gradient. In recent years, gradient descent has become particularly popular in the context of training deep neural networks for machine learning tasks. However, many of these problems are characterized by smooth, convex and nonconvex functions, which present unique challenges for convergence.

Recall that the gradient descent algorithm is given as:

 Algorithm 1 - Gradient Descent (GD) 

Input: An arbitrary vector ${\mathbf{x}}_0\in {\mathbb{R}}^n$ and a decaying step size ${\gamma }_t>0$;
1. for $t=1,2,\dots ,$ do
2. $$ Evaluate the gradient mapping at ${\mathbf{x}}_t$, i.e., evaluate $\mathrm{\nabla }f({\mathbf{x}}_t)$;
3. $$ Do the following update:
   $$    $${\mathbf{x}}_{t+1}:={\mathbf{x}}_t-{\gamma }_t\mathrm{\nabla }f({\mathbf{x}}_t)$$
4. end for

Pre-requisite for convergence:

L-smooth: A differentiable function $f:X\to \mathbb{R}$ over the set $X\subseteq R^n$ is called L-smooth if the following property is satisfied, where $L>0$ is a scalar:

$$\Vert \mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y})\Vert \le L\Vert \mathbf{x}-\mathbf{y}\Vert \text{for all }\mathbf{x},\mathbf{y}\in X.$$

Descent Lemma: Let $f:{\mathbb{R}}^n\to R$ be $L$-smooth over the set $X\subseteq R^n$. Then, for any $\mathbf{x},\mathbf{y}\in X$ we have

$$f(\mathbf{x})\le f(\mathbf{y})+\mathrm{\nabla }f(\mathbf{y}{)}^T(\mathbf{x}-\mathbf{y})+\frac{L}{2}{\Vert \mathbf{x}-\mathbf{y}\Vert }^2.$$

Subgradient Inequality: A differentiable and convex function $f$ satisfies the following inequality:

$$f({\mathbf{x}}_t)+\mathrm{\nabla }f({\mathbf{x}}_t)({\mathbf{x}}^{\ast }–{\mathbf{x}}_t)\le f({\mathbf{x}}^{\ast })$$

Theorem for smooth and convex case

Let $\underset{\mathbf{x}\in {\mathbb{R}}^n}{min}f(\mathbf{x})$ have at least one global optimal solution denoted by ${\mathbf{x}}^{\ast }\in {\mathbb{R}}^n$, where $f$ is $L$-smooth and convex. Then, when $\gamma \le \frac{1}{L}$:

$$f({\mathbf{x}}_T)–f({\mathbf{x}}^{\ast })\le \frac{0.5{\gamma }^{-1}{\Vert {\mathbf{x}}_0–{\mathbf{x}}^{\ast }\Vert }^2}{T}\text{for all }T\ge 1.$$

Proof:

We now use the Lipschitz continuity and Descent lemma to prove the above result.

$$\begin{array}{rl}f({\mathbf{x}}_{t+1})& \stackrel{(i)}{\le }f({\mathbf{x}}_t)+\mathrm{\nabla }f({\mathbf{x}}_t{)}^T({\mathbf{x}}_{t+1}-x_t)+\frac{L}{2}{\Vert {\mathbf{x}}_{t+1}-{\mathbf{x}}_t\Vert }^2\\ & \stackrel{(ii)}{=}f({\mathbf{x}}_t)+\mathrm{\nabla }f({\mathbf{x}}_t{)}^T(-\gamma \mathrm{\nabla }f({\mathbf{x}}_t))+\frac{L}{2}{\Vert -\gamma \mathrm{\nabla }f(x_t)\Vert }^2\\ & \stackrel{(iii)}{=}f({\mathbf{x}}_t)-\gamma {\Vert \mathrm{\nabla }f({\mathbf{x}}_t)\Vert }^2+\frac{{\gamma }^{2}L}{2}{\Vert \mathrm{\nabla }f({\mathbf{x}}_t)\Vert }^2\\ & =f({\mathbf{x}}_t)-\gamma (1-\frac{\gamma L}{2}){\Vert \mathrm{\nabla }f({\mathbf{x}}_t)\Vert }^2\\ & \stackrel{(iv)}{\le }f({\mathbf{x}}_t)-\frac{\gamma }{2}{\Vert \mathrm{\nabla }f({\mathbf{x}}_t)\Vert }^2.\end{array}$$

Where, in $(i)$ we have used Descent lemma by substituting $\mathbf{x}:={\mathbf{x}}_{t+1},\mathbf{y}:={\mathbf{x}}_t$; in $(ii)$ we applied gradient descent update rule ${\mathbf{x}}_{t+1}:={\mathbf{x}}_t-\gamma \mathrm{\nabla }f({\mathbf{x}}_t)$; in $(iii)$ the definition of Euclidian norm square, i.e., ${\mathbf{a}}^T\mathbf{a}={\Vert a\Vert }^2\text{ for all }\mathbf{a}\in {\mathbb{R}}^n$; and finally in $(iv)$ we assume that $\gamma L\le 1$ which states that $1-\frac{\gamma L}{2}\ge \frac{1}{2}$. So, we have:

$$\begin{array}{}\text{(1)}& f({\mathbf{x}}_{t+1})\le f({\mathbf{x}}_t)-\frac{\gamma }{2}{\Vert \mathrm{\nabla }f({\mathbf{x}}_t)\Vert }^2.\end{array}$$

We will now use the subgradient inequality in $\text{1}$ to get:

$$\begin{array}{rl}f({\mathbf{x}}_{t+1})+\mathrm{\nabla }f({\mathbf{x}}_t{)}^T({\mathbf{x}}^{\ast }-{\mathbf{x}}_t)& \le f({\mathbf{x}}^{\ast })-\frac{\gamma }{2}{\Vert \mathrm{\nabla }f({\mathbf{x}}_t)\Vert }^2\\ f({\mathbf{x}}_{t+1})–f({\mathbf{x}}^{\ast })& \le -\mathrm{\nabla }f({\mathbf{x}}_t{)}^T({\mathbf{x}}^{\ast }-{\mathbf{x}}_t)-\frac{\gamma }{2}{\Vert \mathrm{\nabla }f({\mathbf{x}}_t)\Vert }^2\\ & \stackrel{(i)}{\le }\frac{1}{\gamma }({\mathbf{x}}_{t+1}-{\mathbf{x}}_t{)}^T({\mathbf{x}}^{\ast }-{\mathbf{x}}_t)-\frac{1}{2\gamma }{\Vert {\mathbf{x}}_{t+1}-{\mathbf{x}}_t\Vert }^2\\ & \stackrel{(ii)}{\le }\frac{1}{\gamma }({\mathbf{x}}_{t+1}-{\mathbf{x}}_t{)}^T({\mathbf{x}}^{\ast }-{\mathbf{x}}_t)-\frac{1}{2\gamma }{\Vert ({\mathbf{x}}_{t+1}-{\mathbf{x}}^{\ast })-({\mathbf{x}}_t-{\mathbf{x}}^{\ast })\Vert }^2\\ & \stackrel{(iii)}{\le }\frac{1}{\gamma }({\mathbf{x}}_{t+1}-{\mathbf{x}}_t{)}^T({\mathbf{x}}^{\ast }-{\mathbf{x}}_t)-\frac{1}{2\gamma }({\Vert {\mathbf{x}}_{t+1}-{\mathbf{x}}^{\ast }\Vert }^2+{\Vert {\mathbf{x}}_t-{\mathbf{x}}^{\ast }\Vert }^2–2({\mathbf{x}}_{t+1}-{\mathbf{x}}^{\ast }{)}^T({\mathbf{x}}_t-{\mathbf{x}}^{\ast }))\\ & =[\frac{1}{\gamma }({\mathbf{x}}_{t+1}-{\mathbf{x}}_t{)}^T({\mathbf{x}}^{\ast }-{\mathbf{x}}_t)+\frac{1}{\gamma }({\mathbf{x}}_{t+1}-{\mathbf{x}}^{\ast }{)}^T({\mathbf{x}}_t-{\mathbf{x}}^{\ast })]–\frac{1}{2\gamma }({\Vert {\mathbf{x}}_{t+1}-{\mathbf{x}}^{\ast }\Vert }^2+{\Vert {\mathbf{x}}_t-{\mathbf{x}}^{\ast }\Vert }^2)\\ & =\frac{1}{\gamma }{\Vert {\mathbf{x}}_t-{\mathbf{x}}^{\ast }\Vert }^2-\frac{1}{2\gamma }{\Vert {\mathbf{x}}_{t+1}-{\mathbf{x}}^{\ast }\Vert }^2-\frac{1}{2\gamma }{\Vert {\mathbf{x}}_t-{\mathbf{x}}^{\ast }\Vert }^2\\ & =\frac{1}{2\gamma }({\Vert {\mathbf{x}}_t-{\mathbf{x}}^{\ast }\Vert }^2-{\Vert {\mathbf{x}}_{t+1}-{\mathbf{x}}^{\ast }\Vert }^2)\end{array}$$

Where in $(i)$ we replaced $\mathrm{\nabla }f({\mathbf{x}}_t)$ from the update rule, in $(ii)$, we added and subtracted ${\mathbf{x}}^{\ast }$ in the last term, and in $(iii)$, we expanded the whole square term.

Now summing over $t=0,1,\dots ,T-1$. Noting that on the right side, we will have telescoping series.

$$(\sum _{t=0}^{T-1}f({\mathbf{x}}_{t+1}))–Tf({\mathbf{x}}^{\ast })\le \frac{1}{2\gamma }({\Vert {\mathbf{x}}_0-{\mathbf{x}}^{\ast }\Vert }^2-{\Vert {\mathbf{x}}_T-{\mathbf{x}}^{\ast }\Vert }^2)$$

Note that, $f({\mathbf{x}}_{t+1})<f({\mathbf{x}}_t)$ as $f$ is a convex function, so $(\sum _{t=0}^{T-1}f({\mathbf{x}}_{t+1}))\ge Tf({\mathbf{x}}_T)$ and that ${\Vert \cdot \Vert }^2\ge 0$. So, we have:

$$Tf({\mathbf{x}}_T)–Tf({\mathbf{x}}^{\ast })\le (\sum _{t=0}^{T-1}f({\mathbf{x}}_{t+1}))–Tf({\mathbf{x}}^{\ast })\le \frac{1}{2\gamma }\left({\Vert {\mathbf{x}}_0-{\mathbf{x}}^{\ast }\Vert }^2\right)$$

Hence, we have:

$$\boxed{{\displaystyle f({\mathbf{x}}_T)–f({\mathbf{x}}^{\ast })\le \frac{0.5{\gamma }^{-1}{\Vert {\mathbf{x}}_0-{\mathbf{x}}^{\ast }\Vert }^2}{T}}}$$

This concludes the proof of convergence of the gradient descent algorithm when a function is L-smooth and convex.