Convergence Rate of Gradient Descent for Smooth and Strongly Convex Functions

Hello! In our previous lesson, we established a solid theoretical footing by defining L-smoothness and m-strong convexity. We saw how these two properties "sandwich" a function between a quadratic upper bound and a quadratic lower bound. Today, we will put this powerful result to work.

Introduction

Our goal for this lesson is to fulfill the learning outcome: Derive the convergence rate of gradient descent for smooth and strongly convex functions. We will move beyond the empirical observation that gradient descent works and formally prove how quickly it converges to the optimal solution.

You've already seen that for a function to be well-behaved for gradient descent, its curvature shouldn't be too sharp (L-smoothness) or too flat (m-strong convexity). We will now quantify this relationship precisely. We will derive an expression showing that the error, or "suboptimality gap," decreases by a constant multiplicative factor at each iteration. This is known as linear convergence (or geometric convergence), and it is a hallmark of efficient optimization.

This lesson will connect the abstract condition number $\kappa =L/m$ directly to the speed of your algorithm, providing a rigorous explanation for the behaviors you've observed in practice.

---

Part 1: Progress in a Single Step of Gradient Descent

Let's start by analyzing what happens in a single iteration of gradient descent. The update rule is:
${\mathbf{x}}_{k+1}={\mathbf{x}}_k-\eta \nabla f({\mathbf{x}}_k)$
where $\eta$ is the step size (or learning rate).

Our primary tool here is the quadratic upper bound for L-smooth functions, which we derived in the last lesson:
$f(\mathbf{y})\le f(\mathbf{x})+\nabla f(\mathbf{x}{)}^T(\mathbf{y}-\mathbf{x})+\frac{L}{2}\Vert \mathbf{y}-\mathbf{x}{\Vert }_2^2$

Let's apply this to a single step of gradient descent by setting $\mathbf{x}={\mathbf{x}}_k$ and $\mathbf{y}={\mathbf{x}}_{k+1}$.
Substituting $\mathbf{y}-\mathbf{x}={\mathbf{x}}_{k+1}-{\mathbf{x}}_k=-\eta \nabla f({\mathbf{x}}_k)$, we get:

$$\begin{array}{rl}f({\mathbf{x}}_{k+1})& \le f({\mathbf{x}}_k)+\nabla f({\mathbf{x}}_k{)}^T(-\eta \nabla f({\mathbf{x}}_k))+\frac{L}{2}\Vert -\eta \nabla f({\mathbf{x}}_k){\Vert }_2^2\\ f({\mathbf{x}}_{k+1})& \le f({\mathbf{x}}_k)-\eta \Vert \nabla f({\mathbf{x}}_k){\Vert }_2^2+\frac{L{\eta }^2}{2}\Vert \nabla f({\mathbf{x}}_k){\Vert }_2^2\\ f({\mathbf{x}}_{k+1})& \le f({\mathbf{x}}_k)-\left(\eta -\frac{L{\eta }^2}{2}\right)\Vert \nabla f({\mathbf{x}}_k){\Vert }_2^2\end{array}$$

This inequality is crucial. It shows that as long as the term $\left(\eta -\frac{L{\eta }^2}{2}\right)$ is positive, the function value is guaranteed to decrease at every step (unless we are already at a point where the gradient is zero).

To maximize the progress in one step, we can choose $\eta$ to maximize this term. This is a simple quadratic in $\eta$, and its maximum occurs at $\eta =1/L$. Plugging this optimal step size back in, we get:

$$f({\mathbf{x}}_{k+1})\le f({\mathbf{x}}_k)-\left(\frac{1}{L}-\frac{L(1/L{)}^2}{2}\right)\Vert \nabla f({\mathbf{x}}_k){\Vert }_2^2=f({\mathbf{x}}_k)-\frac{1}{2L}\Vert \nabla f({\mathbf{x}}_k){\Vert }_2^2$$

This result, derived using only the smoothness assumption, is already significant. It guarantees that with a step size of $\eta =1/L$, gradient descent will always converge to a point with a zero gradient. However, it doesn't tell us how fast this convergence is in terms of reaching the global minimum $f({\mathbf{x}}^{\ast })$. To do that, we need to bring in our second assumption: strong convexity.

---

Part 2: Deriving Linear Convergence

Now we will combine the result above with the properties of m-strong convexity to derive the final convergence rate.

Recall that a key consequence of m-strong convexity is a lower bound on the squared norm of the gradient in terms of the suboptimality gap, $f(\mathbf{x})-f({\mathbf{x}}^{\ast })$. Specifically, for an m-strongly convex function:
$\Vert \nabla f(\mathbf{x}){\Vert }_2^2\ge 2m(f(\mathbf{x})-f({\mathbf{x}}^{\ast }))$
This inequality formalizes the idea that if we are far from the minimum (i.e., $f(\mathbf{x})-f({\mathbf{x}}^{\ast })$ is large), the gradient must also be large, ensuring we take substantial steps.

We have everything we need. Let's combine our two main inequalities.

1. From L-smoothness (with $\eta =1/L$): $f({\mathbf{x}}_{k+1})\le f({\mathbf{x}}_k)-\frac{1}{2L}\Vert \nabla f({\mathbf{x}}_k){\Vert }_2^2$
2. From m-strong convexity: $-\Vert \nabla f({\mathbf{x}}_k){\Vert }_2^2\le -2m(f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast }))$

Let's subtract the optimal value $f({\mathbf{x}}^{\ast })$ from both sides of the smoothness inequality:
$f({\mathbf{x}}_{k+1})-f({\mathbf{x}}^{\ast })\le f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast })-\frac{1}{2L}\Vert \nabla f({\mathbf{x}}_k){\Vert }_2^2$

Now, substitute the strong convexity inequality into the expression above:

$$\begin{array}{rl}f({\mathbf{x}}_{k+1})-f({\mathbf{x}}^{\ast })& \le (f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast }))-\frac{1}{2L}\left(2m(f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast }))\right)\\ & \le (f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast }))-\frac{m}{L}(f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast }))\\ & \le \left(1-\frac{m}{L}\right)(f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast }))\end{array}$$

This is our main result. Let ${\delta }_k=f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast })$ be the suboptimality gap at iteration $k$. We have shown that:
${\delta }_{k+1}\le \left(1-\frac{m}{L}\right){\delta }_k$

By unrolling this recursion, we get the explicit convergence rate:
$f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast })\le {\left(1-\frac{m}{L}\right)}^k(f({\mathbf{x}}_0)-f({\mathbf{x}}^{\ast }))$

To solidify your understanding of this derivation, please study the following resource, which presents this proof formally.

---

Part 3: Interpreting the Result

The formula we derived is rich with meaning. Let's break it down.

Linear Convergence

The term "linear convergence" can be slightly confusing. It means that the logarithm of the error decreases linearly with the number of iterations. The error itself shrinks by a constant factor $(1-m/L)$ at each step, which is a form of exponential decay. This is a very fast and desirable mode of convergence. This contrasts with sublinear convergence (e.g., $O(1/k)$), which we would get with smoothness alone, where the steps become progressively smaller and convergence slows down dramatically.

The Condition Number

The rate of convergence is governed by the factor $\rho =(1-m/L)=(1-1/\kappa )$, where $\kappa =L/m$ is the condition number.

• Well-conditioned function ($\kappa \approx 1$): Here, $m\approx L$. The convergence factor $\rho$ is close to 0. This means the error is reduced dramatically at each step, leading to very fast convergence. A function with $\kappa =1$ has spherical level sets, and gradient descent (with $\eta =1/L$) finds the minimum in a single step.
• Ill-conditioned function ($\kappa \gg 1$): Here, $m\ll L$. The convergence factor $\rho$ is close to 1. The error decreases very slowly, and the algorithm requires many iterations to converge. This corresponds to the elongated, valley-like functions where gradient descent struggles.

The following video provides an excellent concrete example using a 2D quadratic function, perfectly illustrating the effect of the condition number on the path taken by gradient descent.

Test your understanding!

Let's revisit the function $f(x_1,x_2)=x_1^2+5x_2^2$ from our last lesson. We calculated its smoothness constant $L=10$ and strong convexity constant $m=2$.

1. What is the condition number $\kappa$?
2. According to our derived formula, what is the convergence factor $\rho =(1-m/L)$?
3. Suppose the initial error is ${\delta }_0=100$. After 10 iterations, what is the theoretical upper bound on the error, ${\delta }_{10}$?

Show answer

1. The condition number is $\kappa =L/m=10/2=5$.
2. The convergence factor is $\rho =(1-2/10)=1-0.2=0.8$. This means the error is guaranteed to decrease by at least 20% at each iteration.
3. The upper bound on the error after 10 iterations is ${\delta }_{10}\le {\rho }^{10}{\delta }_0=(0.8{)}^{10}\times 100\approx 0.107\times 100=10.7$. The error has been reduced by nearly a factor of 10.

---

Conclusion

In this lesson, we have moved from intuition to a rigorous mathematical proof, achieving a deep understanding of gradient descent's performance.

Key Takeaways:

• For a function that is both L-smooth and m-strongly convex, gradient descent with a step size of $\eta =1/L$ converges at a linear rate.
• The suboptimality gap ${\delta }_k=f({\mathbf{x}}_k)-f({\mathbf{x}}^{\ast })$ decreases at each step according to the inequality: ${\delta }_{k+1}\le \left(1-\frac{m}{L}\right){\delta }_k$.
• The convergence speed is entirely determined by the condition number $\kappa =L/m$. A high condition number signifies an ill-conditioned problem and leads to slow convergence.
• This theoretical result precisely explains the practical behavior of gradient descent, where performance is excellent on "spherical" functions ($\kappa \approx 1$) and poor on "elongated valley" functions ($\kappa \gg 1$).

Preview of the Next Lesson:
We have now concluded our deep dive into the theory of unconstrained optimization using gradient descent. Our next module, "Constrained Optimization and Duality," will introduce a new class of problems where the variables must satisfy certain constraints. We will begin by formulating optimization problems with equality constraints and derive the powerful method of Lagrange multipliers to solve them.