Why curvature changes the rate
The previous descent bound for a smooth convex objective decreases like . Sometimes a stronger conclusion is possible: each update removes a fixed fraction of the remaining error. To see why this is useful in learning, imagine a quadratic loss whose level sets are long thin ellipses. A step safe in the steep direction may make very little progress along the flat direction. The ratio between these curvatures predicts the difficulty of using one common step size.
Our objective is deterministic and unconstrained; noisy gradients and boundary optima require separate arguments.
Assumptions and notation
Definition 21.1.1
(Smooth strongly convex objective)
Let be twice continuously differentiable, and suppose there are constants such that, for every ,
The inequalities are in the quadratic-form sense. The condition number is . Gradient descent with constant step takes .
The lower bound implies . In particular is coercive: this lower bound at tends to infinity as . Thus has a minimizer ; strong convexity makes it unique, and differentiability on all of gives . The upper bound gives the corresponding quadratic upper estimate with . These are global assumptions, not conclusions from a Hessian observed at one iterate.
A contraction theorem
Theorem 21.1.2
(A curvature-balanced step)
Under the assumptions above, set and . For every integer ,
When , the update reaches the minimizer in one step. Interpret the bound at separately, or use .
Proof
(Linearize the error along a segment)
Put . The fundamental theorem of calculus along the segment from to gives
The symmetric matrix also satisfies : integrate the original quadratic-form inequalities against any fixed vector. Hence every eigenvalue of belongs to , and
With the stated step, the factors at the two endpoints are and . Since the absolute value of an affine function reaches its maximum on an interval at an endpoint, the norm factor is at most . Iteration gives the distance estimate. The upper quadratic estimate at , where the gradient vanishes, gives the objective estimate.
Proof X-ray
Why the changing Hessian causes no gap in the proof
Both curvature bounds are used twice. The lower bound gives existence and uniqueness of and the gradient condition , which lets the error recursion start from ; the two bounds together then confine the eigenvalues of every averaged Hessian to . The key move is the integral form of the mean value theorem: it turns a nonlinear update into an exact linear recursion with a symmetric matrix that depends on . The matrix may change at every iteration and need not commute with earlier matrices. We bound the norm of each individual update uniformly before multiplying the inequalities; simultaneous diagonalization is unnecessary. This is why the hypotheses must be global: a Hessian at the starting point alone would not bound the averaged Hessians along later segments.
For a symmetric positive definite quadratic with eigenvalues at both endpoints, the worst multiplier for a constant step is . Balancing the two endpoint magnitudes gives and the smallest such worst multiplier . This is a worst-case statement over these curvatures, not a claim that the step is best for every initial vector. A large makes close to one. Rescaling features or using a justified preconditioner can improve conditioning, but changes of variables must be reflected in the objective and update.
A second route: objective decrease
The step gives a convenient direct objective bound, which avoids the distance altogether.
Theorem 21.1.3
(Objective decrease with step )
Under the same assumptions, gradient descent with satisfies, for every integer ,
Proof
(Combine a descent step with a gradient lower bound)
The upper Hessian bound gives . Taking yields
Strong convexity also implies . Indeed, minimize the strong-convexity lower bound in over all of : the minimum is attained at , equals , and is no greater than . Subtract from the first inequality at and insert the second:
Iterating this one-step factor gives the claim.
This bound concerns objective gaps directly. It uses a different step and a different initial quantity from the preceding distance bound; comparing the displayed exponents alone does not prove one numerical bound is always smaller.
Worked example 21.1.4
(An elongated quadratic)
Let , with . Here , , , and the balanced step is . The update multiplies the two coordinates by and , respectively. Thus and , down from . The second coordinate alternates sign, yet its magnitude contracts. In fact the objective is exactly multiplied by each step for this example.
Worked example 21.1.5
(A non-quadratic objective whose curvature varies)
Let on . With the logistic function we have and . Since , the assumptions hold with and . Hence and .
The minimizer solves and has no closed form; numerically . From the gradient is , so . Then
The averaged curvature on the segment is , which lies in as the proof requires. The iterate overshoots because , yet the error still contracts by the guaranteed factor.
Worked example 21.1.6
(How the condition number sets the iteration count)
To guarantee with the balanced step, we need , that is , where .
For , and , so suffices. For , and , so suffices. A tenfold increase in costs about ten times as many guaranteed iterations, because for large , giving . In the edge case we have , and a single step suffices for every tolerance.
Counterexample mode
Smoothness alone does not produce a minimum
The function has -Lipschitz gradient, but is unbounded below and has no minimizer. With , gradient descent gives , which diverges from any nonzero start. The upper curvature bound is not a lower curvature bound. Even a convergent sequence for a nonconvex objective need not converge to a global minimum.
A bound is a guarantee under its hypotheses, not a measurement of training performance. An empirical neural-network objective may have negative or zero curvature, and stochastic gradient noise generally prevents applying this deterministic theorem to individual iterates unchanged. Strong convexity from adding a quadratic penalty also requires the remaining term to be convex, or a separate lower Hessian bound.
Common mistake
(Reading and off one Hessian)
The constants must bound the Hessian at every point the iterates and the segments to can visit. In the non-quadratic example, but as ; on other objectives the curvature at the start can be far smaller than elsewhere. A step chosen from alone carries no guarantee.
Common mistake
(Assuming any quadratic penalty creates strong convexity)
Adding raises every Hessian eigenvalue by . If the remaining term has curvature below , the sum is still not convex: has second derivative . The penalty yields only when the remaining term is convex.
Practice with solutions
Quick check
(For and , identify , and calculate the balanced-step iterate .)
The second derivative is constant.
Solution · Answer
The Hessian is , so choose . Then and . This illustrates the edge case.
Quick check
(In the elongated quadratic, compute the first update using and its objective value.)
Each coordinate is multiplied by with its own curvature .
Solution · Answer
The multipliers are and , so and . The general objective bound gives at most ; it is valid but loose for this starting point.
Quick check
(For the same quadratic, what happens with from ?)
Compute the multiplier of the second coordinate.
Solution · Answer
The second multiplier is , so . The objective stays and the iterates do not converge. The endpoint cannot be included in a strict contraction claim.
Quick check
(If and , how many balanced-step iterations suffice to reduce the distance guarantee to at most one percent of the starting distance?)
First compute .
Solution · Answer
Here . We need , so . The sufficient integer is . This is a worst-case certificate and does not say that every initial point needs twelve steps.