Earlier notes analyzed gradient descent on a positive-definite quadratic. In that setting the iteration is linear, and the eigenvalues of the Hessian describe the error exactly. Training even a very small neural network produces objectives that are neither quadratic nor convex. The spectral argument therefore no longer applies, and the question itself has to change.
We can no longer hope to prove convergence to a global minimizer in general. What we can prove, under a smoothness hypothesis and a lower bound on the objective, is that gradient descent makes the gradient small. This note derives that guarantee from first principles and states it precisely. It then tests every part of the statement against examples that show where it stops.
Standing assumptions
Throughout, satisfies the following.
- Smoothness. is continuously differentiable, and its gradient is globally -Lipschitz for some :
- Lower bound. There is a real number with for all .
The number only has to be a lower bound; it need not be the infimum, and it need not be attained. For a nonnegative loss, is always admissible. Norms are Euclidean.
The algorithm is fixed-step gradient descent. Choose and a step size with , and set
The descent lemma
The Lipschitz condition controls how quickly the gradient changes. The first task is to turn that into a statement about the function itself: how far can deviate from its tangent plane.
Theorem 3.2.1
(Descent lemma)
Under the smoothness assumption, for all ,
Proof
(Integrating the gradient along a segment)
Fix and write . Define by .
Since is differentiable, the chain rule gives . This derivative is continuous in because is continuous. The fundamental theorem of calculus therefore applies:
The constant equals . Subtracting it,
Now bound the integrand. Cauchy–Schwarz gives , and the Lipschitz condition gives for . Hence
The proof uses both hypotheses. Continuity of makes the fundamental theorem legitimate, and the Lipschitz bound controls the integrand. Convexity is never used.
The lemma gives a two-sided quadratic envelope around the tangent plane. Only the upper half is needed below:
One step decreases the objective
Theorem 3.2.2
(Sufficient decrease)
Under the standing assumptions with , every gradient step satisfies
Proof
(Substituting the gradient step)
Write , so that . Insert this into the upper descent inequality with , :
Write . The step-size restriction is exactly the condition .
As a function of , the quantity is a downward parabola with maximum at , where . So is the step size that maximizes the guaranteed decrease. The actual decrease may be larger.
Concept lensAlgorithmic
Gradient descent as minimizing a quadratic upper model
The upper descent inequality says that lies above and touches it at . Completing the square shows that is minimized exactly at , with value . So the step is the majorize-then-minimize step, and its guaranteed decrease is the model's own drop. A step minimizes the model with curvature , which is an upper model only when .
Summable squared gradients and a finite-time bound
Theorem 3.2.3
(Stationarity guarantee for fixed-step gradient descent)
Under the standing assumptions with :
For every integer ,
In particular, as .
Proof
(Telescoping the decrease inequality)
Rearrange sufficient decrease as and sum over . The right-hand side telescopes:
The last inequality is where the lower bound enters.
The partial sums of the nonnegative series are therefore bounded by , uniformly in . A nonnegative series with bounded partial sums converges, and its sum obeys the same bound. The terms of a convergent series tend to zero, so and hence .
For the finite-time bound, each of the terms is at least the smallest one, so
Divide by and take square roots. Since is increasing, and coincide.
Proof X-ray
Where each hypothesis enters the stationarity proof
The argument has one idea: every step pays for its squared gradient with function value, and the total amount of function value available is the finite budget . Summing converts a local, one-step inequality into a global count, without ever asking where the iterates are.
Smoothness enters exactly once, through the descent lemma, and only to produce the per-step inequality. The step-size restriction enters through : at the telescoped inequality reads and carries no information. The lower bound enters only in the final estimate . Without it the budget is infinite. For , whose gradient is constant and hence -Lipschitz for every , the iteration is , and for every .
The proof controls a sum, and a sum controls its smallest term and its average, not each term. That is why the finite-time statement is about and not about the last iterate. Convexity is never used.
The bound decays like . To guarantee , it suffices to take
Worked example 3.2.4
(How pessimistic the iteration count can be)
Take on , so , and . Choose and , so and
What the theorem guarantees. For the tolerance the sufficient count is
so iterations are guaranteed to suffice.
What actually happens. The iteration is , so and . The condition means , first satisfied at , where . So the first iterates already contain a point meeting the tolerance.
Check. Sufficient decrease at the first step predicts , and indeed : the per-step inequality is attained here. The gap between and comes from the summation, which assumes every step makes only the guaranteed decrease from the guaranteed budget. This function is strongly convex, a structure the theorem does not use, so its worst-case count is far from the truth here.
What follows for the iterates, and what does not
Definition 3.2.5
(Stationary point and cluster point)
A point is a stationary point of if .
A point is a cluster point of a sequence if some subsequence converges to .
Corollary 3.2.6
(Cluster points of gradient descent are stationary)
Under the standing assumptions with , every cluster point of the gradient-descent sequence is a stationary point of . If is bounded, at least one cluster point exists.
Proof
(Passing to the limit along a subsequence)
Suppose . Because is continuous, . The full sequence of gradient norms tends to zero by the stationarity guarantee, so the same is true along the subsequence. Limits are unique, so .
If is bounded, the Bolzano–Weierstrass theorem provides a convergent subsequence, hence at least one cluster point, and by the first part it is stationary.
Boundedness is an additional hypothesis. The standing assumptions do not imply it, and the logistic counterexample below has no cluster point at all.
The theorem does not assert any of the following, and each can fail under the standing assumptions alone:
- that the iterates converge;
- that a stationary limit is a minimizer (it may be a saddle or even a maximum);
- that the true parameters of some data-generating model are recovered;
- any rate at which tends to zero.
Each of these requires further structure, such as convexity, a gradient-domination inequality, or bounded sublevel sets combined with knowledge of the stationary set.
Worked example 3.2.7
(Convergence to a saddle point)
Let on . Then , so , and
The Hessian has operator norm , so is -Lipschitz and . Take . The two coordinates decouple:
Edge case: . From we get at every step, so and . The iterates converge to , a stationary point with Hessian : a saddle point, with while the minimum value is . Every conclusion of the theorem holds, and the limit is not a minimizer.
A perturbed start. From with , the map has and , so it sends into itself, and there because . The sequence is increasing and bounded by ; its limit satisfies , so . The iterates converge to , a global minimizer with . Which stationary point is reached depends on the starting point, which the theorem does not see.
For twice continuously differentiable objectives and small fixed steps, convergence to a strict saddle happens only from a measure-zero set of starting points.
A natural next question
How often does gradient descent end at a saddle?
For twice continuously differentiable objectives and small fixed steps, convergence to a strict saddle happens only from a measure-zero set of starting points.
In the example the bad starts are exactly the horizontal lines , where ; from every other start the iterates reach a minimizer. This is typical. If is twice continuously differentiable and , the gradient map is a diffeomorphism, and the starting points whose iterates converge to a stationary point where the Hessian has a negative eigenvalue form a set of Lebesgue measure zero. The proof uses the stable-manifold theorem and is beyond this note; it gives no bound on how long iterates may linger near a saddle.
A one-parameter tanh predictor
Worked example 3.2.8
(Fitting to the target )
Consider the predictor , a single tanh unit with one weight and a single input fixed to . Fit it to the target with squared loss:
Clearly , so .
Derivatives. Use and . Then
and, by the product rule,
A valid Lipschitz constant. For every real we have , , and therefore . The triangle inequality gives
By the mean value theorem, . So is valid.
It is not sharp. Writing , one finds , and for example . The theorem needs only some valid , not the best one.
One step with from . Since , the theorem applies. We have and , so
Here . Sufficient decrease predicts
Numerically, . This follows from the series at . Hence
The actual value is strictly below both and the guaranteed bound .
The optimum, and why this example is special. The equation forces , because . So the unique stationary point is
and since , it is the global minimizer.
Here we can also prove that the iterates converge. For , monotone decrease gives . This means , so lies in the closed interval , which is contained in . Consequently stays in a bounded interval.
Every cluster point is stationary and therefore equals . A bounded sequence whose only cluster point is converges to .
This conclusion used facts specific to the example: a bounded sublevel set and a unique stationary point. It is not part of the general theorem.
Counterexamples that mark the boundary
Counterexample mode
Descent without a finite stationary point: the logistic loss
Let . Then , so . Its derivatives are
Since , we get , so is valid. The function has no stationary point at all.
For any finite and any fixed , gradient descent reads
The increment is strictly positive, so is strictly increasing.
Suppose . Letting and using continuity gives , that is, , which is impossible. An increasing real sequence with no finite limit is unbounded above, so .
Then and . The theorem's conclusion holds: gradients vanish. Yet there is no cluster point and no minimizer. Small gradients do not mean the iterates are near any stationary point.
The algebra above is exact mathematics. In floating point, overflows for large negative . Real computations should use the stable rearrangement
with evaluated by a dedicated log1p routine.
The second counterexample concerns the step-size hypothesis rather than the shape of .
Counterexample mode
The endpoint step size two over L
Let on . Its gradient is exactly -Lipschitz. With ,
From the iterates alternate , and never decreases. The gradient norms stay equal to and do not tend to zero.
This does not contradict sufficient decrease, because ; it shows the strict inequality cannot be dropped.
Common mistake
(Applying the theorem to a loss with a ReLU kink)
Let . For we have , and for we have . The two formulas agree at , so is continuous, and it is tempting to quote the stationarity guarantee for it.
The left derivative at is , while the right derivative is . So is not differentiable at . The descent lemma's proof, which relies on the fundamental theorem along a line through , does not apply, and neither does the stationarity guarantee in its stated form; the last exercise below shows that no choice of a “derivative at ” rescues the descent inequality. Using such a loss requires a separate nonsmooth analysis.
Reading the guarantee in training practice
Which iterate to report. The finite-time bound concerns the best of the first iterates, not the last. The algorithm computes at every step anyway, so one can record
and report , which inherits the bound. This is a statement about stationarity of only.
Common mistake
(Reading the bound as a statement about the last iterate)
The finite-time bound does not bound . Gradient norms need not decrease from one step to the next: in the exercise on the sine iterates below, the gradient norm rises after the first step. What the proof controls is the sum of the first squared gradient norms, so only the best iterate, or the average of the squared norms, inherits the bound. For instance, an index drawn uniformly from satisfies .
Deterministic versus stochastic gradients. The analysis assumes the exact gradient of at every step. Stochastic training replaces it with a random minibatch estimate. The decrease inequality then fails pathwise and must be replaced by a different argument, typically in expectation and with conditions on the noise and the step sizes. None of the conclusions above transfer automatically.
Empirical versus population loss. When is an average loss over a fixed dataset, the theorem certifies a nearly stationary point of that empirical loss. It says nothing about the loss on new data drawn from the underlying distribution. Making the training gradient small is an optimization statement; good test performance is a separate statistical question.
Exercises
Exercise 3.2.9
(Let . Find the smallest constant for which is -Lipschitz and a valid lower bound . Prove the descent lemma directly, and state the resulting bound on for .)
Core
Solution(4)
- 1
Show that is valid
for some between and , so works.
Because: Mean value theorem applied to .
- 2
Show that no smaller constant works
If for all , then dividing by and letting gives for every , and forces . The lower bound is valid and attained.
- 3
Verify the descent lemma directly
Set . Then
The integrand has absolute value at most , so the whole expression is bounded in absolute value by .
- 4
Apply the stationarity guarantee
With , which satisfies , we have , and
Exercise 3.2.10
(Let , and . How many iterations does the theorem require to guarantee ? Compare with .)
Foundation
Solution(3)
- 1
Check the step size and compute
Since , the theorem applies, with .
- 2
Solve the sufficient condition for
So iterations suffice.
- 3
Compare with
With we get and . This is the smallest requirement the bound can give, because is maximized at . These are sufficient counts from a worst-case bound, not predictions of actual behavior.
Exercise 3.2.11
(Take and . (a) From , show that . (b) Show that the iterates stay in and identify their limit. (c) What happens from ?)
Core
Solution(4)
- 1
(a) The gradient norm can increase
We have , so . Then
Because , the angle satisfies . Sine is strictly increasing on , so . Gradient norms need not decrease monotonically; the theorem never claimed they would. Meanwhile by sufficient decrease.
- 2
(b) The interval is invariant
Let . Then , so is nondecreasing. For , we have , which gives , and also .
- 3
(b) Identify the limit
Key step
On this interval , so the sequence is nonincreasing and bounded below. It converges to some , which is stationary, so and . Since , we conclude , a global minimizer.
Because: Monotonicity, not the general theorem, singles out the limit.
- 4
(c) Starting at a maximum
Here , so for every . The iterates sit at a global maximum: stationary, with zero gradient, and as far from optimal as possible.
Exercise 3.2.12
((a) For , describe gradient descent for and for . (b) For , show that no number assigned as the derivative at makes the two-sided descent-lemma inequality hold near for any .)
SynthesisProof
Solution(4)
- 1
(a) The linear recursion
In both cases . For the factor is , and the iterates oscillate between and with constant loss. For we have , so and whenever .
- 2
(b) The remainder on each side of the kink
Let . For , ; for , .
- 3
(b) Both one-sided limits must vanish
Key step
So must tend to from both sides. From the right, , which forces . From the left, , which forces .
Because: Dividing by gives .
- 4
(b) Contradiction
∎The two requirements and are incompatible. The kink is not an artifact of notation; it genuinely violates the smoothness the theorem requires.
Summary
For a continuously differentiable function with -Lipschitz gradient that is bounded below, gradient descent with fixed step has the following properties:
- each step decreases by at least ;
- the squared gradient norms are summable;
- the best of the first gradient norms is at most ;
- every cluster point is stationary, and if the iterates are bounded, at least one cluster point exists.
Convergence of the iterates, global optimality, parameter recovery and rates for the function gap all require additional structure.