Gradient Descent: What Converges, and How Fast?

Stationarity, convex rates, and stochastic gradients

Will Gao · March 2025

Contents

1 Gradient descent for smooth functions
2 The convex case
3 The strongly convex case
4 Stochastic gradient descent
4.1 Step-size consequences

These notes are adapted from Prof. Alexis Drouot's MATH 480 course at the University of Washington, Seattle (Winter 2025). They are my own notes, not official course materials. I have done my best to ensure correctness, but errors may remain.

The goal is to collect a few basic convergence guarantees for gradient descent under progressively stronger assumptions, and then to see what changes when exact gradients are replaced by stochastic ones. We begin with smooth, possibly nonconvex objectives, then add convexity and strong convexity, and finish with a standard stationarity bound for stochastic gradient descent.

1Gradient descent for smooth functions

We seek to solve

min_{x \in R^{d}} f (x), f \in C^{2} (R^{d}; R),

starting from $x_{0} \in R^{d}$ and applying the fixed-step iteration

x_{k + 1} = x_{k} - α \nabla f (x_{k}),

(1)

where $α > 0$ is small. Under suitable assumptions, the gradient norms converge to zero.

Definition 1.1 (Smoothness). A differentiable function

f : R^{d} \to R

is $L$ -smooth if

‖ \nabla f (x) - \nabla f (y) ‖ \leq L ‖ x - y ‖ for all x, y \in R^{d} .

Equivalently, its gradient is

L

-Lipschitz. If

f \in C^{2} (R^{d})

, the bound

{‖ \nabla^{2} f (x) ‖}_{op} \leq L

for all

x

implies that

f

L

-smooth.

Assume throughout this section that $f$ is $L$ -smooth. In the $C^{2}$ setting above, a sufficient condition is

- L I ⪯ \nabla^{2} f (x) ⪯ L I for every x \in R^{d},

(2)

where, for symmetric matrices, $A ⪯ B$ means $h^{⊤} A h \leq h^{⊤} B h$ for every $h \in R^{d}$ .

Lemma 1.2 (Descent lemma). If

f

is differentiable and

L

-smooth, then, for every

x, y \in R^{d}

| f (y) - f (x) - \nabla f (x)^{⊤} (y - x) | \leq \frac{L}{2} {‖ y - x ‖}^{2} .

(3)

In particular,

f (y) \leq f (x) + \nabla f (x)^{⊤} (y - x) + \frac{L}{2} {‖ y - x ‖}^{2} .

Proof. Let

d = y - x

. By the fundamental theorem of calculus,

f (y) - f (x) - \nabla f (x)^{⊤} d = \int_{0}^{1} (\nabla f (x + t d) - \nabla f (x))^{⊤} d d t .

Using Cauchy–Schwarz and

L

-smoothness,

| f (y) - f (x) - \nabla f (x)^{⊤} d | \leq \int_{0}^{1} L t {‖ d ‖}^{2} d t = \frac{L}{2} {‖ d ‖}^{2},

which is (3).

Theorem 1.3 (Stationarity rate). Let

f_{*} = inf_{x} f (x) > - \infty

, and suppose

f

L

-smooth. For a fixed step size

0 < α \leq 1 / L

, the iterates in (1) satisfy, for every integer

K \geq 1

min_{0 \leq k \leq K - 1} {‖ \nabla f (x_{k}) ‖}^{2} \leq \frac{2 (f (x_{0}) - f_{*})}{α K} .

(4)

Moreover,

‖ \nabla f (x_{k}) ‖ \to 0

k \to \infty

Proof. Apply Lemma 1.2 with

y = x_{k + 1} = x_{k} - α \nabla f (x_{k})

\begin{aligned} f (x_{k + 1}) & \leq f (x_{k}) - α {‖ \nabla f (x_{k}) ‖}^{2} + \frac{L α^{2}}{2} {‖ \nabla f (x_{k}) ‖}^{2} \\ = f (x_{k}) - α (1 - \frac{L α}{2}) {‖ \nabla f (x_{k}) ‖}^{2} \\ \leq f (x_{k}) - \frac{α}{2} {‖ \nabla f (x_{k}) ‖}^{2} . \end{aligned}

Hence

\frac{α}{2} \sum_{k = 0}^{K - 1} {‖ \nabla f (x_{k}) ‖}^{2} \leq f (x_{0}) - f (x_{K}) \leq f (x_{0}) - f_{*} .

Since the minimum is at most the average, (4) follows. Letting

K \to \infty

shows that the nonnegative series

\sum_{k} {‖ \nabla f (x_{k}) ‖}^{2}

is finite, so its terms tend to zero.

The conclusion above guarantees convergence to first-order stationarity, but a critical point need not be a global minimizer. Convexity supplies that missing implication.

2The convex case

Definition 2.1. A function

f : R^{d} \to R

is convex if, for all

x, y \in R^{d}

and

θ \in [0, 1]

f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y) .

Lemma 2.2 (First-order characterization). If

f

is differentiable and convex, then, for every

x, y \in R^{d}

f (y) \geq f (x) + \nabla f (x)^{⊤} (y - x) .

(5)

Thus a differentiable convex function lies above each of its tangent hyperplanes.

Proof. For

θ \in (0, 1)

, convexity gives

f (x + θ (y - x)) \leq (1 - θ) f (x) + θ f (y) .

Rearranging,

\frac{f (x + θ (y - x)) - f (x)}{θ} \leq f (y) - f (x) .

Letting

θ ↓ 0

yields

\nabla f (x)^{⊤} (y - x) \leq f (y) - f (x)

In particular, if $\nabla f (x_{*}) = 0$ , then (5) implies $f (y) \geq f (x_{*})$ for every $y$ , so $x_{*}$ is a global minimizer.

Theorem 2.3 (Function-value rate for convex objectives). Suppose

f

is convex, differentiable, and

L

-smooth, and assume a minimizer

x_{*} \in \arg \min f

exists. With

0 < α \leq 1 / L

, gradient descent satisfies

f (x_{K}) - f_{*} \leq \frac{{‖ x_{0} - x_{*} ‖}^{2}}{2 α K}, K \geq 1,

(6)

where

f_{*} = f (x_{*})

Proof. The previous descent estimate gives

f (x_{k + 1}) \leq f (x_{k}) - \frac{α}{2} {‖ \nabla f (x_{k}) ‖}^{2} .

(7)

Let

d_{k} = x_{*} - x_{k}

. Since

d_{k + 1} = d_{k} + α \nabla f (x_{k})

\nabla f (x_{k})^{⊤} d_{k} = \frac{{‖ d_{k + 1} ‖}^{2} - {‖ d_{k} ‖}^{2}}{2 α} - \frac{α}{2} {‖ \nabla f (x_{k}) ‖}^{2} .

By Lemma 2.2,

f (x_{k}) \leq f_{*} - \nabla f (x_{k})^{⊤} d_{k}

. Combining this with (7) gives

f (x_{k + 1}) - f_{*} \leq \frac{{‖ d_{k} ‖}^{2} - {‖ d_{k + 1} ‖}^{2}}{2 α} .

Summing from

k = 0

K - 1

yields

\sum_{k = 0}^{K - 1} (f (x_{k + 1}) - f_{*}) \leq \frac{{‖ d_{0} ‖}^{2} - {‖ d_{K} ‖}^{2}}{2 α} \leq \frac{{‖ d_{0} ‖}^{2}}{2 α} .

The values

f (x_{k})

are nonincreasing by (7); hence the left side is at least

K (f (x_{K}) - f_{*})

, proving (6).

Thus $K = O (ε^{- 1})$ iterations suffice to ensure $f (x_{K}) - f_{*} \leq ε$ .

3The strongly convex case

Definition 3.1. A differentiable function

f : R^{d} \to R

is $μ$ -strongly convex, for

μ > 0

, if

f (y) \geq f (x) + \nabla f (x)^{⊤} (y - x) + \frac{μ}{2} {‖ y - x ‖}^{2} for all x, y \in R^{d} .

(8)

The factor $1 / 2$ is the standard normalization. Under this convention, $f$ is $μ$ -strongly convex exactly when $x \mapsto f (x) - (μ / 2) {‖ x ‖}^{2}$ is convex. If $f \in C^{2}$ , this is equivalent to $\nabla^{2} f (x) ⪰ μ I$ for all $x$ . If $f$ is also $L$ -smooth, then necessarily $0 < μ \leq L$ .

Lemma 3.2 (Existence and uniqueness of the minimizer). A continuously differentiable, strongly convex function on

R^{d}

has a unique minimizer

x_{*}

Proof. Set

x = 0

in (8):

f (y) \geq f (0) + \nabla f (0)^{⊤} y + \frac{μ}{2} {‖ y ‖}^{2} .

The quadratic term dominates the linear term as

‖ y ‖ \to \infty

, so

f (y) \to \infty

; that is,

f

is coercive. A continuous coercive function on

R^{d}

attains its minimum. Strong convexity implies strict convexity, so two distinct minimizers cannot exist.

Lemma 3.3 (Gradient domination). If

f

μ

-strongly convex and

x_{*}

is its minimizer, then

\frac{1}{2} {‖ \nabla f (x) ‖}^{2} \geq μ (f (x) - f_{*}) for every x \in R^{d} .

(9)

Proof. Taking the infimum in

y

on the right side of (8),

f_{*} \geq inf_{y} {f (x) + \nabla f (x)^{⊤} (y - x) + \frac{μ}{2} {‖ y - x ‖}^{2}} = f (x) - \frac{1}{2 μ} {‖ \nabla f (x) ‖}^{2},

where the quadratic is minimized at

y = x - μ^{- 1} \nabla f (x)

. Rearrangement gives (9).

Theorem 3.4 (Linear convergence). Suppose

f

μ

-strongly convex and

L

-smooth. If

0 < α \leq 1 / L

, then gradient descent satisfies

f (x_{K}) - f_{*} \leq (1 - α μ)^{K} (f (x_{0}) - f_{*}) .

(10)

0 < α μ < 1

and

0 < ε < f (x_{0}) - f_{*}

, it therefore suffices to take

K \geq \frac{\log ((f (x_{0}) - f_{*}) / ε)}{- \log (1 - α μ)}

(11)

to guarantee

f (x_{K}) - f_{*} \leq ε

. Thus the iteration complexity is

O (\log (1 / ε))

for fixed

α

and

μ

. In the endpoint case

α μ = 1

, (10) already gives

f (x_{1}) = f_{*}

Proof. By (7) and Lemma 3.3,

f (x_{k + 1}) - f_{*} \leq f (x_{k}) - f_{*} - \frac{α}{2} {‖ \nabla f (x_{k}) ‖}^{2} \leq (1 - α μ) (f (x_{k}) - f_{*}) .

Iterating proves (10); solving the resulting geometric bound for

K

proves (11).

4Stochastic gradient descent

Large-data objectives often have the finite-sum form

f (a) = \frac{1}{N} \sum_{j = 1}^{N} f_{j} (a),

(12)

where $f_{j}$ is the loss associated with the $j$ th data point. Computing the full gradient may be expensive. Stochastic gradient descent (SGD) instead uses

a_{k + 1} = a_{k} - α_{k} \nabla f_{J_{k}} (a_{k}),

(13)

where, conditional on the past, $J_{k}$ is sampled uniformly from ${1, \dots, N}$ . If $F_{k}$ denotes the information available before drawing $J_{k}$ , then

E [\nabla f_{J_{k}} (a_{k}) ∣ F_{k}] = \nabla f (a_{k}) .

(14)

Lemma 4.1 (First and second moments). For uniform sampling and any fixed

a

E_{J} [\nabla f (a)^{⊤} \nabla f_{J} (a)] = {‖ \nabla f (a) ‖}^{2},

(15)

E_{J} [{‖ \nabla f_{J} (a) ‖}^{2}] = {‖ \nabla f (a) ‖}^{2} + E_{J} [{‖ \nabla f_{J} (a) - \nabla f (a) ‖}^{2}] .

(16)

Proof. By (12),

E_{J} [\nabla f_{J} (a)] = N^{- 1} \sum_{j = 1}^{N} \nabla f_{j} (a) = \nabla f (a)

, which gives (15). Equation (16) is the vector-valued bias–variance identity

E {‖ G ‖}^{2} = {‖ E G ‖}^{2} + E {‖ G - E G ‖}^{2}

The variance term generally depends on the current iterate. For a uniform theorem, assume that there exists $σ \geq 0$ such that, almost surely,

E [{‖ \nabla f_{J_{k}} (a_{k}) - \nabla f (a_{k}) ‖}^{2} | F_{k}] \leq σ^{2} for every k .

(17)

Theorem 4.2 (Expected stationarity bound for SGD). Assume

f

L

-smooth and bounded below by

f_{*}

, the stochastic gradients are conditionally unbiased as in (14), and (17) holds. If

0 < α_{k} \leq 1 / L

, then, for every

K \geq 1

\begin{aligned} min_{0 \leq k \leq K - 1} E {‖ \nabla f (a_{k}) ‖}^{2} & \leq \frac{2 (f (a_{0}) - E f (a_{K})) + L σ^{2} \sum_{k = 0}^{K - 1} α_{k}^{2}}{\sum_{k = 0}^{K - 1} α_{k}} \\ \leq \frac{2 (f (a_{0}) - f_{*}) + L σ^{2} \sum_{k = 0}^{K - 1} α_{k}^{2}}{\sum_{k = 0}^{K - 1} α_{k}} . \end{aligned}

(18)

Proof. The descent lemma and (13) give

f (a_{k + 1}) \leq f (a_{k}) - α_{k} \nabla f (a_{k})^{⊤} \nabla f_{J_{k}} (a_{k}) + \frac{L α_{k}^{2}}{2} {‖ \nabla f_{J_{k}} (a_{k}) ‖}^{2} .

Take conditional expectation and apply Lemma 4.1 together with (17):

\begin{aligned} E [f (a_{k + 1}) ∣ F_{k}] & \leq f (a_{k}) - α_{k} {‖ \nabla f (a_{k}) ‖}^{2} + \frac{L α_{k}^{2}}{2} ({‖ \nabla f (a_{k}) ‖}^{2} + σ^{2}) \\ \leq f (a_{k}) - \frac{α_{k}}{2} {‖ \nabla f (a_{k}) ‖}^{2} + \frac{L α_{k}^{2} σ^{2}}{2} . \end{aligned}

After taking full expectation and summing from

k = 0

K - 1

\sum_{k = 0}^{K - 1} α_{k} E {‖ \nabla f (a_{k}) ‖}^{2} \leq 2 (f (a_{0}) - E f (a_{K})) + L σ^{2} \sum_{k = 0}^{K - 1} α_{k}^{2} .

Dividing by

\sum_{k = 0}^{K - 1} α_{k}

and using that a minimum is no larger than the corresponding weighted average proves (18).

4.1Step-size consequences

For a constant step $α_{k} = α \leq 1 / L$ , Theorem 4.2 becomes

min_{0 \leq k \leq K - 1} E {‖ \nabla f (a_{k}) ‖}^{2} \leq \frac{2 (f (a_{0}) - f_{*})}{α K} + L α σ^{2} .

The second term is the noise floor. Choosing $α$ on the order of $K^{- 1 / 2}$ balances the two terms and yields an $O (K^{- 1 / 2})$ stationarity bound. More generally, if

\sum_{k = 0}^{\infty} α_{k} = \infty, \sum_{k = 0}^{\infty} α_{k}^{2} < \infty,

then the bound in (18) forces the weighted average of the expected squared gradient norms to vanish asymptotically. In particular,

\underset{k \to \infty}{lim inf} E {‖ \nabla f (a_{k}) ‖}^{2} = 0 .