Gradient Descent: Direction, Step Size and Convergence

Preparation

We assume gradients, Hessians, the multivariable chain rule, eigenvalues of symmetric matrices and one-variable Taylor’s theorem. Review multivariable Taylor polynomials before the finite-step analysis.

5.3 Why the negative gradient is locally downhill

Assume $f$ is differentiable at $x$. For a unit direction $u$, $D_uf(x)=\nabla f(x)^Tu$. By Cauchy–Schwarz this is at least $-\|\nabla f(x)\|$, with equality for $u=-\nabla f/\|\nabla f\|$ when the gradient is nonzero. Thus the negative gradient is the direction of steepest first-order decrease in the chosen Euclidean coordinates.

The coordinate metric matters: changing the scales of inputs changes which direction has unit length. A gradient direction in dollars and rate proportions has no invariant physical meaning until scaling is chosen.

Gradient descent uses

$$x_{k+1}=x_k-\eta_k\nabla f(x_k),\qquad\eta_k>0.$$

Its directional derivative at a nonstationary point is negative, but an arbitrary finite step can overshoot and increase the objective. A step-size condition requires curvature information.

5.4 Deriving a finite-step descent bound

Assume $f$ is $C^1$ on an open set containing the entire relevant segment, and the gradient is Lipschitz there with constant $L>0$: $\|\nabla f(x+ts)-\nabla f(x)\|\le Lt\|s\|$ for $0\le t\le1$. A zero Lipschitz constant may be replaced by any positive upper bound. By the line-integral form of the one-variable fundamental theorem,

$$f(x+s)-f(x)=\int_0^1\nabla f(x+ts)^Ts\,dt.$$

Subtract $\nabla f(x)^Ts$, use Cauchy–Schwarz and integrate $Lt\|s\|^2$ to obtain the descent lemma

$$f(x+s)\le f(x)+\nabla f(x)^Ts+\frac L2\|s\|^2.$$

For $s=-\eta\nabla f(x)$,

$$f(x-\eta\nabla f(x))\le f(x)-\eta\left(1-\frac{L\eta}{2}\right)\|\nabla f(x)\|^2.$$

Hence $0<\eta<2/L$ guarantees strict decrease at a nonstationary point when the assumptions hold throughout the step. A local curvature bound must not be used to justify a step that leaves the region where that bound is valid.

Worked example 2: safe and unsafe steps. For $f(x,y)=(x^2+9y^2)/2$, gradient is $(x,9y)^T$ and $L=9$ globally. With constant $\eta=0.1$,

$$x_{k+1}=0.9x_k,\qquad y_{k+1}=0.1y_k.$$

Starting at $(1,1)$, the first iterate is $(0.9,0.1)$ with objective $0.45$, compared with initial value five. The next is $(0.81,0.01)$ with objective $0.3285$. With $\eta=0.3$, the second-coordinate multiplier is $-1.7$; that component grows in magnitude even though the initial direction is downhill.

5.5 Exact convergence for positive-definite quadratics

Let $f(x)=\frac12x^THx-b^Tx+c$ with symmetric positive-definite $H$, and use a fixed constant step size $\eta$. Its unique minimizer is $x_*=H^{-1}b$. Writing error $e_k=x_k-x_*$ gives

$$e_{k+1}=(I-\eta H)e_k.$$

Use an orthonormal eigenbasis of $H$. Each error coordinate is multiplied by $1-\eta\lambda_i$. Thus every initial point converges to $x_*$ exactly when $|1-\eta\lambda_i|<1$ for all eigenvalues, namely

$$0<\eta<2/\lambda_{\max}.$$

At the upper endpoint, a largest-eigenvalue component can oscillate without decaying. Below the range, a zero or negative step need not decrease; above it, some component grows. The conditioning ratio $\lambda_{max}/\lambda_{min}$ also explains slow convergence when one coordinate direction is much flatter than another.

For this quadratic, $\|\nabla f(x)\|=\|H(x-x_*)\|\ge\lambda_{min}\|x-x_*\|$. A gradient-norm stopping rule therefore yields a distance bound only when a positive lower eigenvalue bound is known. Small steps caused by choosing a tiny $\eta$ do not themselves establish closeness to the minimizer.

5.6 Constraints and stopping statements

An unconstrained step can leave a feasible set. For example, a nonnegative-weight constraint is not automatically preserved by subtracting a gradient. Equality constraints may require projected directions, substitution or a separate constrained algorithm. Chapter 2's multiplier condition and the unconstrained gradient descent formula answer different questions.

A useful numerical report states the objective, starting point, coordinate scaling, step rule, stopping criterion, and any error or decrease bound actually justified. “The code stopped” is not a mathematical convergence certificate, and a nonconvex stationary point may be a saddle rather than a desired minimum.

5.7 Exercises

P02. Find the gradient descent update for $f(x,y)=x^2+2y^2$.

P03. For $f(x,y)=x^2+y^2$, show one step with $\eta=2$ from $(1,0)$ increases the objective.

P05. For $f=(x^2+4y^2)/2$, determine every constant step size yielding convergence from all starting points.

P06. For the same objective, take $\eta=1/4$ from $(2,1)$ and calculate the first two iterates and objective values.

P08. For $f(x)=\frac12x^THx-b^Tx+c$ with $H=\operatorname{diag}(2,5)$, if $\|\nabla f(x)\|\le0.001$, bound distance to the quadratic's minimizer.

P09. Derive the finite-step descent lemma directly for a symmetric positive-definite quadratic and compare its curvature bound with the largest eigenvalue.

P10. Explain why a step parallel to the negative gradient does not necessarily preserve the constraint $x+y=1$. At $(x,y)$ with gradient $(g_1,g_2)$, derive the condition under which that particular step preserves the sum.

5.8 Full solutions

P02. Gradient is $(2x,4y)^T$, so $(x_{k+1},y_{k+1})=((1-2\eta)x_k,(1-4\eta)y_k)$ for constant step.

P03. Gradient at $(1,0)$ is $(2,0)$. The step gives $(-3,0)$, changing the objective from one to nine. A downhill infinitesimal direction did not protect an oversized finite step.

P05. Eigenvalues are one and four, so convergence from all initial points requires $0<\eta<1/2$.

P06. Update multipliers are $3/4$ and zero. Iterates are $(3/2,0)$ then $(9/8,0)$. Objective values are $9/8$ and $81/128$, respectively, below initial value four.

P08. The minimum eigenvalue is two, so distance is at most $0.001/2=0.0005$.

P09. The exact difference is $f(x+s)-f(x)=\nabla f(x)^Ts+s^THs/2$. Since $s^THs\le\lambda_{max}\|s\|^2$, the descent lemma holds with $L=\lambda_{max}$. Substituting $s=-\eta\nabla f$ gives the same sufficient decrease bound; the eigen-coordinate recurrence gives the exact all-starting-point convergence range.

P10. The new sum is $x+y-\eta(g_1+g_2)=1-\eta(g_1+g_2)$. For a positive step it stays one exactly when $g_1+g_2=0$. A general gradient need not satisfy that tangent-direction condition.

Summary

The negative gradient is steepest only for a chosen metric and at first order. Lipschitz curvature gives a finite-step decrease bound; symmetric eigenvalues give an exact convergence test for positive-definite quadratics. Constraints and stopping certificates require separate checks.