Convergence of gradient descent for smooth strongly 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 and for smooth and convex case in Convergence of gradient descent for smooth and convex case. This article is continuation of the convergence of gradient descent algorithm when the function is smooth and strongly 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.

 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 analysis

Before jumping to convergence analysis for smooth and strongly convex cases for gradient descent algorithm, we first define some basic inequalities that will be used:

Lipschitz smoothness: By definition, 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.$$

Strong Convexity: Consider a continuously differentiable function $f:{\mathbb{R}}^n\to \mathbb{R}$. We say $f$ is $\mu$-strongly convex over $X\subseteq {\mathbb{R}}^n$ if for some $\mu >0$ we have

$$f(\mathbf{y})+\mathrm{\nabla }f(\mathbf{y}{)}^T(\mathbf{x}-\mathbf{y})+\frac{\mu }{2}{\Vert \mathbf{x}-\mathbf{y}\Vert }^2\le f(\mathbf{x}),\text{for all }\mathbf{x},\mathbf{y}\in X.$$

By some algebraic manipulation of the above expression, we can say that for a strong convex function, the following also holds:

$${(\mathrm{\nabla }f(\mathbf{x})-\mathrm{\nabla }f(\mathbf{y}))}^T(\mathbf{x}-\mathbf{y})\ge \mu {\Vert \mathbf{x}-\mathbf{y}\Vert }^2,\text{for all }\mathbf{x},\mathbf{y}\in X.$$

Theorem for smooth and strongly convex function:

Let ${\mathbf{x}}^{\ast }\in {\mathbb{R}}^n$ denote the unique global optimal solution of $\underset{\mathbf{x}\in {\mathbb{R}}^n}{min}f(\mathbf{x})$, where $f$ is $L$-smooth and $\mu$-strongly convex. Then, when $\gamma <\frac{2\mu }{L^2}$, we have:

$${\Vert {\mathbf{x}}_T-{\mathbf{x}}^{\ast }\Vert }^2\le {(1–2\gamma \mu +{\gamma }^2{L}^2)}^T{\Vert x^{\ast }-x_0\Vert }^2\text{for all }T\ge 1.$$

Proof:

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

Where in $(i)$, we have applied the update rule of gradient descent algorithm, in $(ii)$ we have expanded the norm squared term by considering the terms ${\mathbf{x}}_t–{\mathbf{x}}^{\ast }$ and $\mathrm{\nabla }f({\mathbf{x}}_t)$. In $(iii)$, we have assumed the fact that $f$ is strongly convex, so $\mathrm{\nabla }f({\mathbf{x}}^{\ast })=0$ when ${\mathbf{x}}^{\ast }$ is optimal point. Finally, in $(iv)$, we apply the inequalities of a function being $L$ smooth and $\mu$ strongly convex as defined above.

By recursion, we obtain:

$$\boxed{{\displaystyle {\Vert {\mathbf{x}}_T-{\mathbf{x}}^{\ast }\Vert }^2\le {(1–2\gamma \mu +{\gamma }^2{L}^2)}^T{\Vert x^{\ast }-x_0\Vert }^2\text{for all }T\ge 1.}}$$

This concludes the proof of convergence of gradient descent when the function is smooth and strongly convex.