Gradient descent and variants — convergence analysis: Question bank

Before you start, one reminder of the cast of characters so no symbol trips you up:

Recall The symbols in one place

$η$ = step size (learning rate). $L$ = smoothness constant (curvature ceiling, Lipschitz bound on the gradient). $μ$ = strong-convexity constant (curvature floor). $κ = L / μ \geq 1$ = condition number. $ρ$ = per-step contraction factor. $x^{⋆}$ = the minimizer, $f^{⋆} = f (x^{⋆})$ .

True or false — justify

Constant step size always works for full-batch GD but never for SGD.

True. Full-batch gradients are exact so a fixed

η \leq 2/ L

contracts every step; SGD gradient noise never vanishes near

x^{⋆}

, so a constant

η

leaves a residual bounce of radius

\sim η σ

f

is convex and

L

-smooth, GD converges linearly (geometrically).

False. Plain convexity (

μ = 0

) only buys

O (1/ k)

. You need strong convexity

μ > 0

to get a contraction factor

ρ < 1

and hence a linear

ρ^{k}

rate.

Choosing

η = 1/ L

guarantees

f

decreases every single iteration.

True. From the descent lemma the drop is

η (1 - L η /2) ∥\nabla f ∥^{2}

; at

η = 1/ L

this is

\frac{1}{2 L} ∥\nabla f ∥^{2} \geq 0

, so

f

is monotone non-increasing.

A larger learning rate always reaches the minimum in fewer iterations.

False. Speed only lives in

(0, 2/ L)

; beyond

η = 2/ L

the factor

∣1 - η L ∣ > 1

and GD diverges by oscillating outward. The guaranteed-drop term even turns negative.

For a perfectly conditioned problem (

κ = 1

) GD with the optimal step converges in one step.

True. With

μ = L = a

and

η^{⋆} = 2/ (μ + L) = 1/ a

, the contraction factor

1 - η a = 0

, so

x_{1} = x^{⋆}

exactly.

Momentum changes the problem's condition number

κ

False.

κ

is a property of

f

(its Hessian's eigenvalue spread), not the algorithm. Momentum leaves

κ

untouched but improves the rate's dependence from

κ

κ

The descent lemma requires

f

to be convex.

False. It only needs

L

-smoothness. The proof uses the fundamental theorem of calculus plus the Lipschitz bound — convexity is never invoked. Convexity is needed later, to turn the per-step drop into a global rate.

For SGD the conditions

\sum η_{k} = \infty

and

\sum η_{k}^{2} < \infty

are both necessary.

True.

\sum η_{k} = \infty

lets the iterates travel arbitrarily far (reach any minimizer);

\sum η_{k}^{2} < \infty

makes the accumulated noise finite so the jitter dies out. Drop either and convergence fails.

Strong convexity guarantees a unique global minimizer.

True.

\nabla^{2} f ⪰ μ I

with

μ > 0

means

f

curves strictly upward in every direction, so the bowl has exactly one bottom.

Spot the error

"To speed up GD I'll set

η = 3/ L

— bigger steps, faster convergence."

Wrong:

3/ L > 2/ L

, so

∣1 - η L ∣ = ∣1 - 3∣ = 2 > 1

and the worst eigendirection grows each step. GD diverges, it doesn't speed up.

f (x) = x^{4}

is convex with a unique min, so GD converges linearly."

Wrong: at the minimum

x = 0

the curvature

f^{''} (0) = 0

, so

μ = 0

(not strongly convex). GD converges only sublinearly, not at a

ρ^{k}

rate.

"The optimal step for strongly convex GD is

η = 1/ L

because that's the smooth-case magic step."

Wrong:

1/ L

is optimal for smooth convex

f

. For strongly convex, minimizing

ρ (η) = max (∣1 - η μ ∣, ∣1 - η L ∣)

gives

η^{⋆} = 2/ (μ + L)

, which balances the two worst eigendirections.

"Since

- \nabla f

is steepest descent, GD takes the shortest path to the minimum."

Wrong: steepest descent is locally the best unit direction, but the globally shortest route is generally a straight line to

x^{⋆}

. In an anisotropic valley GD zig-zags — locally optimal, globally wasteful.

"I set

η

from

L

, and my convergence proof needs

L

to be an exact Hessian bound."

Wrong:

L

only needs to be a valid upper bound on curvature (

\nabla^{2} f ⪯ L I

). Any overestimate is safe (just gives smaller steps); the danger is underestimating

L

, which permits

η > 2/ L

and divergence.

"For

f (x, y) = \frac{1}{2} (x^{2} + 100 y^{2})

I'll pick

η = 1

since one eigenvalue is

1

Wrong: stability is set by the largest eigenvalue

L = 100

, needing

η < 2/100

. At

η = 1

the

y

-direction factor is

∣1 - 100∣ = 99

and blows up.

"SGD with

η_{k} = 1/ k

satisfies the Robbins–Monro conditions."

Wrong:

\sum 1/ k = \infty

✓ but

\sum 1/ k = \infty

as well (since

η_{k}^{2} = 1/ k

), so

\sum η_{k}^{2}

diverges. The noise isn't killed; use

η_{k} = 1/ k

instead where

\sum 1/ k^{2} < \infty

Why questions

Why does the parent minimize a parabola each step rather than

f

itself?

Because the descent lemma sandwiches

f

below the parabola

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

. Minimizing that easy upper bound guarantees

f

drops at least as much — we can't minimize

f

directly without knowing it globally.

Why does the condition number

κ

control the convergence speed?

κ = L / μ

measures how stretched the bowl is (ratio of steepest to flattest curvature). A large

κ

means a long thin valley where the safe step for the steep direction is tiny for the flat direction, forcing zig-zag and

ρ^{⋆} = \frac{κ - 1}{κ + 1} \to 1

Why does the optimal

η^{⋆} = 2/ (μ + L)

balance

∣1 - η μ ∣

and

∣1 - η L ∣

The rate is the max of the two eigendirection factors. Lowering one raises the other, so the minimax is reached exactly where they're equal — solving

1 - η μ = η L - 1

gives

η^{⋆} = 2/ (μ + L)

Why does momentum turn

κ

into

κ

Momentum averages out the oscillation across the narrow valley and accumulates speed along its floor, so the effective slowdown scales with the square root of the eigenvalue spread. Formally the accelerated contraction is

\frac{κ - 1}{κ + 1}

Why is

- \nabla f

(and not some other descent direction) the steepest one?

For a unit direction

u

, the rate of change is

\nabla f^{⊤} u

, which by Cauchy–Schwarz is most negative when

u

points exactly opposite the gradient,

u = - \nabla f /∥\nabla f ∥

Why must SGD's step decay while GD's can stay constant?

GD's gradient is exact, so a constant contraction shrinks error to zero. SGD's stochastic gradient keeps a variance floor

σ^{2}

near

x^{⋆}

; only a shrinking

η_{k}

scales that noise down to zero.

Why does the descent lemma proof integrate along the segment

x \to y

To express

f (y) - f (x)

exactly via the fundamental theorem of calculus, so the only inequality used is the Lipschitz bound on how far the gradient can drift — that's what produces the clean

\frac{L}{2} ∥ y - x ∥^{2}

term.

Edge cases

What happens to GD at exactly

η = 2/ L

on the worst eigendirection?

The factor is

∣1 - 2∣ = 1

: no contraction and no divergence — the iterate oscillates forever between

\pm

the same magnitude. It's the exact knife-edge of stability.

What is the rate when

μ = 0

(convex but not strongly convex)?

The contraction factor

ρ^{⋆} = \frac{κ - 1}{κ + 1} \to 1

κ \to \infty

, so no linear rate exists; you fall back to the

O (1/ k)

sublinear guarantee.

What does

κ = 1

mean geometrically and for the rate?

All curvatures equal (

μ = L

): the level sets are perfect circles/spheres.

ρ^{⋆} = \frac{1 - 1}{1 + 1} = 0

, so one optimal step lands on

x^{⋆}

\nabla f (x_{k}) = 0

but

x_{k}

is a saddle, what does GD do?

It stops moving —

x_{k + 1} = x_{k}

— since the update multiplies the (zero) gradient. GD's convergence guarantees assume convexity precisely to rule out saddles; on nonconvex

f

it can stall at one.

What is the drop term

η (1 - L η /2)

η \to 0^{+}

It tends to

0

: infinitesimal steps make infinitesimal progress. Convergence still holds but takes infinitely many steps — the reason

η

near

1/ L

(not near

0

) is the sweet spot.

For

η

slightly above

2/ L

, does

f

increase or the iterate diverge first?

Both are the same phenomenon:

∣1 - η L ∣ > 1

makes the worst-direction error grow geometrically, so

∥ x_{k} - x^{⋆} ∥

and hence

f (x_{k}) - f^{⋆}

both blow up. The guaranteed-drop term has already gone negative.

What happens if you feed an underestimate of

L

into the step

η = 1/ \hat{L}

with

\hat{L} < L

Then

η = 1/ \hat{L} > 1/ L

, possibly exceeding

2/ L

, so the "safe" step is no longer safe and GD may diverge. Overestimating

L

is conservative; underestimating is dangerous.