3.1 Gradient descent on quadratics

Motivation

Least squares turns fitting data into an optimization problem. Solving the normal equations gives an exact description of the answer, while gradient descent approaches that answer through repeated updates. The two viewpoints should agree: the equations identify the destination, and the iteration explains how the current error changes on the way there.

A quadratic objective is particularly useful for understanding this process. Its gradient depends affinely on the parameters, its curvature is constant, and its eigenvectors separate the update into independent scalar recurrences. Consequently, we can calculate precisely when a step size gives convergence, when the iterates oscillate, and when they move farther from the minimum. These conclusions also explain why changing the scale of a loss changes a suitable learning rate, even though the fitted model stays the same.

Throughout this section, parameter vectors are columns, and the gradient is a column of partial derivatives. The Euclidean geometry behind the word “steepest” is the same inner-product geometry used in projections and PCA. We will use the spectral decomposition of a real symmetric matrix rather than introduce another algorithm for finding eigenvectors.

Definitions

Definition

Quadratic objective and gradient

For a parameter vector $\theta\in\mathbb R^d$, consider

$$f(\theta)=\frac12\theta^\top Q\theta-b^\top\theta+c, \qquad Q=Q^\top.$$

Here $Q$ is a real $d\times d$ matrix, $b\in\mathbb R^d$, and $c$ is a scalar. Its gradient and Hessian are

$$\nabla f(\theta)=Q\theta-b,\qquad \nabla^2 f(\theta)=Q.$$

The matrix $Q$ is positive definite when $z^\top Qz>0$ for every nonzero $z$. In that case all its eigenvalues are positive. Write $\mu=\lambda_{\min}(Q)$ and $L=\lambda_{\max}(Q)$.

The symmetry assumption makes the derivative especially transparent. Expanding $(\theta+h)^\top Q(\theta+h)$ produces two equal cross terms, so the part linear in $h$ is $h^\top(Q\theta-b)$. The remaining part is $h^\top Qh/2$. The factor $1/2$ in the objective cancels the factor $2$ that differentiation of a square would otherwise introduce.

Definition

Gradient descent with a constant step size

Choose an initial parameter $\theta_0$ and a positive scalar step size $\eta>0$. Gradient descent generates

$$\theta_{k+1}=\theta_k-\eta\nabla f(\theta_k) =\theta_k-\eta(Q\theta_k-b), \qquad k=0,1,2,\ldots.$$

The gradient is evaluated at the current iterate. Every coordinate in $\theta_{k+1}$ uses that same current vector $\theta_k$.

To understand the direction, let $g=\nabla f(\theta)$. Among unit vectors $v$, the directional derivative $g^\top v$ has smallest value $-\|g\|_2$, attained at $v=-g/\|g\|_2$ when $g\ne0$. This follows from Cauchy–Schwarz. Gradient descent uses $-g$ itself, so its direction is steepest descent and its displacement length is $\eta\|g\|_2$. A direction and a displacement length are different choices: a useful direction does not make an arbitrarily long step useful.

Theorem/Proposition

Theorem

The minimum and its exact objective gap

Suppose $Q$ is symmetric positive definite. Then $f$ has the unique global minimizer

$$\theta_\star=Q^{-1}b.$$

For $e=\theta-\theta_\star$,

$$f(\theta)-f(\theta_\star)=\frac12e^\top Qe, \qquad \frac{\mu}{2}\|e\|_2^2 \le f(\theta)-f(\theta_\star) \le\frac{L}{2}\|e\|_2^2.$$

The constant $c$ changes objective values but has no effect on the minimizer or the updates. The vector $b$ determines the centre of the quadratic, while $Q$ determines the shape around that centre. In particular, finding a stationary point here solves the minimization problem because the objective gap is strictly positive away from that point.

Theorem

The exact constant-step convergence condition

Let $Q$ be symmetric positive definite and set $e_k=\theta_k-\theta_\star$. For a fixed real step size $\eta$,

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

The iterates converge to $\theta_\star$ for every initial vector if and only if

$$0<\eta<\frac2L.$$

For such a step size, define

$$\rho=\max_i|1-\eta\lambda_i(Q)|<1.$$

Then $\|e_k\|_2\le\rho^k\|e_0\|_2$ and $f(\theta_k)-f(\theta_\star)\le \rho^{2k}\bigl(f(\theta_0)-f(\theta_\star)\bigr)$.

The words “for every initial vector” matter. A particular initialization can have zero error in an unstable eigenvector direction, so a single successful run does not establish a step-size guarantee. The theorem controls every direction that an initial error might contain.

Proof sketch or proof idea

First expand $f(\theta_\star+e)$. The terms linear in $e$ cancel because $Q\theta_\star=b$, leaving $e^\top Qe/2$. If $Q=V\Lambda V^\top$ with $V$ orthogonal, set $z=V^\top e$. Then $e^\top Qe=\sum_i\lambda_i z_i^2$, and the objective-gap bounds follow by replacing each eigenvalue with $\mu$ or $L$. Positivity also proves uniqueness.

Subtract the stationary equation from one gradient step:

$$\begin{aligned} e_{k+1} &=\theta_k-\eta(Q\theta_k-b)-\theta_\star\\ &=e_k-\eta Qe_k. \end{aligned}$$

Changing to eigenvector coordinates $z_k=V^\top e_k$ gives

$$z_{k+1,i}=(1-\eta\lambda_i)z_{k,i}, \qquad z_{k,i}=(1-\eta\lambda_i)^kz_{0,i}.$$

Each coordinate is a geometric sequence. It tends to zero for every starting value exactly when $|1-\eta\lambda_i|<1$, equivalently $0<\eta\lambda_i<2$. Requiring this for all eigenvalues gives the stated interval. Taking squared sums yields the error bound; weighting those squares by $\lambda_i/2$ yields the objective-gap bound.

At $\eta=2/L$, a nonzero component in a largest-eigenvalue direction multiplies by $-1$, so it alternates without shrinking. Above this boundary, its multiplier has magnitude greater than one and that component diverges. At $\eta=0$, every iterate stays at its initial value. These cases explain both strict inequalities in the convergence condition.

Curvature, progress, and conditioning

There is also an exact one-step expression. With $g=\nabla f(\theta)$,

$$f(\theta-\eta g)-f(\theta) =-\eta\|g\|_2^2+\frac{\eta^2}{2}g^\top Qg \le-\eta\left(1-\frac{\eta L}{2}\right)\|g\|_2^2.$$

Thus every nonstationary step strictly decreases the objective when $0<\eta<2/L$. For $\eta=1/L$, all the eigenvector multipliers lie between $0$ and $1-\mu/L$: there is no sign alternation in these coordinates. When $\mu$ is much smaller than $L$, however, the low-curvature direction shrinks slowly. The steepest direction restricts the allowed step size, while the flattest direction limits progress.

The ratio $\kappa=L/\mu$ is the condition number of this positive-definite quadratic. Among constant steps, the smallest worst-direction contraction is obtained by balancing the two endpoint multipliers: $1-\eta\mu=-(1-\eta L)$. This gives $\eta=2/(\mu+L)$ and $\rho=(\kappa-1)/(\kappa+1)$. This is a statement about a known quadratic spectrum. It also makes the role of feature scaling concrete: changing coordinates can change the relative curvatures faced by the iteration.

The contraction factor describes repeated progress, rather than just a successful first update. If $\rho=3/4$, an error component that dominates the estimate initially may still require many updates to become small. After ten updates the bound contains $(3/4)^{10}$, whereas the corresponding objective-gap bound contains $(3/4)^{20}$. An apparently rapid decrease in the loss can therefore coexist with a more gradual improvement in the parameters. The two quantities measure different features of the same run, and the theorem states their relationship explicitly.

This distinction is especially visible in a narrow quadratic valley. Moving away from its steep walls can remove much of the initial loss quickly. Once that component is small, the remaining error lies mostly along the flatter direction. Progress then looks slower even though the same constant recurrence has governed every step. The apparent change of speed comes from changing proportions of the error components, rather than a change in the algorithm.

Worked examples

Worked example

1. A scalar step can shrink, alternate, or diverge

Let $f(t)=2(t-3)^2$. Its derivative is $4(t-3)$, so $t_\star=3$, $L=4$, and the step-size interval is $0<\eta<1/2$. Starting with $t_0=-1$, choose $\eta=1/8$. The error multiplier is $1-4\eta=1/2$, giving

$$t_0=-1,\quad t_1=1,\quad t_2=2,\quad t_3=\frac52.$$

The corresponding losses are $32$, $8$, $2$, and $1/2$. Error halves at each step, while loss is divided by four because it is quadratic in error.

With $\eta=1/2$, the multiplier is $-1$: the iterates alternate between $-1$ and $7$, and the loss stays at $32$. With $\eta=3/4$, the multiplier is $-2$: the first three iterates are $-1$, $11$, and $-13$, with losses $32$, $128$, and $512$. All three runs use the negative gradient; their different behaviour comes from the step length.

Worked example

2. Two eigenvector directions progress at different rates

Consider

$$f(u,v)=\frac12\bigl((u-1)^2+4(v+1)^2\bigr).$$

Here $Q=\operatorname{diag}(1,4)$, $\theta_\star=(1,-1)^\top$, and the coordinate axes are already eigenvector directions. For $\eta=1/4$, the two error multipliers are $3/4$ and $0$. Starting at $(u_0,v_0)=(3,1)$ therefore gives

$$(u_1,v_1)=\left(\frac52,-1\right),\qquad (u_2,v_2)=\left(\frac{17}{8},-1\right).$$

The second coordinate reaches its optimal value in one step. The first continues to approach $1$ geometrically. The losses are $f_0=10$, $f_1=9/8$, and $f_2=81/128$. The smallest worst-direction contraction instead uses $\eta=2/5$, giving multipliers $3/5$ and $-3/5$. Sign alternation can therefore coexist with convergence and even improve the worst-direction contraction.

The following Python code computes both gradient coordinates before updating either parameter. Reading its successive states beside the exact calculation makes the coordinate recurrence visible.

u, v = 3.0, 1.0
eta = 0.25
for k in range(4):
    loss = 0.5 * ((u - 1.0) ** 2 + 4.0 * (v + 1.0) ** 2)
    print(f"{k}: ({u:.6f}, {v:.6f}) f={loss:.6f}")
    grad_u, grad_v = u - 1.0, 4.0 * (v + 1.0)
    u, v = u - eta * grad_u, v - eta * grad_v

Its output is

0: (3.000000, 1.000000) f=10.000000
1: (2.500000, -1.000000) f=1.125000
2: (2.125000, -1.000000) f=0.632812
3: (1.843750, -1.000000) f=0.355957

Worked example

3. Gradient descent reaches the same regression fit

For three observations, take

$$A=\begin{bmatrix}1&-1\\1&0\\1&1\end{bmatrix}, \qquad y=\begin{bmatrix}0\\1\\3\end{bmatrix}, \qquad f(\theta)=\frac{1}{2n}\|A\theta-y\|_2^2,\quad n=3.$$

The first parameter is an intercept and the second is a slope. Expansion gives $Q=A^\top A/n=\operatorname{diag}(1,2/3)$ and $b=A^\top y/n=(4/3,1)^\top$, hence $\theta_\star=(4/3,3/2)^\top$. The columns of $A$ are independent, so $Q$ is positive definite and $L=1$.

With $\theta_0=(0,0)^\top$ and $\eta=1$, the gradient is $-b$, giving $\theta_1=(4/3,1)^\top$. The residual vector is $A\theta_1-y=(1/3,1/3,-2/3)^\top$, so $f(\theta_1)=1/9$. Another step gives $\theta_2=(4/3,4/3)^\top$ and $f(\theta_2)=1/27$. At the optimum, the residual is $(-1/6,1/3,-1/6)^\top$ and $f(\theta_\star)=1/36$. The intercept error disappears immediately; the slope error is multiplied by $1/3$ on every step. A positive minimum loss expresses the remaining fitting residual, rather than failure of the optimization.

For a general design matrix $A\in\mathbb R^{n\times d}$, the same normalization gives

$$\nabla f(\theta)=\frac1nA^\top(A\theta-y),\qquad Q=\frac1nA^\top A.$$

Full column rank is exactly the condition making $Q$ positive definite: $z^\top Qz=\|Az\|_2^2/n$ is positive for nonzero $z$ precisely when the null space is zero. The largest curvature is $L=\sigma_{\max}(A)^2/n$, linking the learning rate to singular values. No matrix inverse is needed to perform a step: form a prediction, subtract the target, multiply the residual by $A^\top$, and divide by $n$.

The indices in this calculation have distinct roles. The prediction and residual have one entry for each observation, whereas the gradient has one entry for each parameter. Multiplication by $A^\top$ converts observation errors into parameter directions by accumulating each feature's contribution. For an intercept column of ones, its gradient entry is the mean residual. For another feature column, it is the mean product of that feature with the residual. This explains how the normal-equation orthogonality condition appears inside an iterative algorithm: a zero gradient says that every feature column is orthogonal to the current residual.

Consequently, the residual vector itself need not tend to zero. At a least-squares solution it can retain a component orthogonal to the column space of $A$. Gradient descent cannot remove that component by changing the coefficients, because every available prediction remains in the same column space. What tends to zero is the gradient, or the part of the residual that still points toward an available improvement. This is the geometric reason to distinguish a small optimization error from a small data-fitting error.

The two products $A\theta$ and $A^\top r$ also provide a direct implementation without first constructing $A^\top A$. For a dense matrix, each product uses work proportional to the number of entries of $A$. The quadratic matrix remains useful for analysis even when the implementation applies those products separately. This separates the mathematical object that proves convergence from the operations that actually produce an update.

Loss normalization and stopping

Replacing $f$ by $F=\alpha f$ for $\alpha>0$ preserves its minimizer, but multiplies its gradient and Hessian by $\alpha$. To reproduce the same iterates, divide the step size by $\alpha$. In the regression example, the unnormalized residual sum of squares is $F=2nf=6f$. Its largest curvature is $6$, so its interval is $0<\eta<1/3$; a step of $1/6$ reproduces the mean-loss step of $1$.

A useful stopping quantity is $\|\nabla f(\theta_k)\|_2$. Since $\nabla f=Qe_k$, a known lower curvature bound gives $\|e_k\|_2\le\|\nabla f(\theta_k)\|_2/\mu$. A small update by itself has a different meaning: it may simply reflect an extremely small chosen $\eta$. Report the loss normalization and the stopping quantity together when comparing numerical runs.

Common mistakes

Common mistake

Confusing a gradient direction with a guaranteed decrease

The negative gradient gives a local descent direction at a nonstationary point. A finite step also depends on curvature. For a quadratic, the factor $1-\eta\lambda_i$ determines whether each error component shrinks. Checking its magnitude explains both convergence with alternating signs and divergence after an excessively long step.

Common mistake

Changing the loss while retaining the same learning rate

The losses $\|A\theta-y\|_2^2$ and $\|A\theta-y\|_2^2/(2n)$ have the same minimizers, but their gradients differ by $2n$. Write the objective first, differentiate that objective, and adjust $\eta$ when a multiplicative normalization changes.

Summary

The stationary equation locates the unique minimum of a positive-definite quadratic. Subtracting that equation from the update gives an exact linear recurrence for the error. In eigenvector coordinates, each error component is multiplied by $1-\eta\lambda_i$; all components shrink precisely when $0<\eta<2/L$. Least-squares regression fits this framework when the design matrix has independent columns, with curvature determined by its squared singular values and by the chosen loss normalization.

Exercises

Checkpoint

1. Find the minimum, the full constant-step convergence interval, and the first step when $Q=\operatorname{diag}(2,5)$, $b=(4,-5)^\top$, $\theta_0=(0,1)^\top$, and $\eta=1/5$.

Compute the gradient at the initial vector before updating either coordinate.

Checkpoint

2. For $f(t)=3(t+2)^2$ and $t_0=0$, compute the next two iterates for $\eta=1/3$ and for $\eta=1/4$. Which run converges?

Express the update using the error $t_k+2$.

Checkpoint

3. In the regression example, replace $f$ by the residual sum of squares $F=6f$. Which step reproduces $\eta=1$ for $f$, and what is the convergence interval for $F$?

Track both the gradient scaling and the largest Hessian eigenvalue.

Checkpoint

4. Let $f(\theta)=(\theta_1-1)^2/2$ with $\theta_0=(0,7)^\top$ and $\eta=1$. Find the iterates and all minimizers. Why does the uniqueness theorem not apply?

Identify what the gradient does in the second coordinate.

Solutions

Solution · 1. Solve the stationary equation and apply the two multipliers

The minimum is $\theta_\star=(2,-1)^\top$. Since $L=5$, the interval is $0<\eta<2/5$. At $\theta_0$, the gradient is $(-4,10)^\top$, so $\theta_1=(0,1)^\top-\frac15(-4,10)^\top=(4/5,-1)^\top$. The multipliers are $3/5$ and $0$.

Solution · 2. Separate boundary oscillation from shrinking oscillation

The derivative is $6(t+2)$, and the error multiplier is $1-6\eta$. For $\eta=1/3$ it is $-1$, giving $t_1=-4$, $t_2=0$ and continued alternation. For $\eta=1/4$ it is $-1/2$, giving $t_1=-3$, $t_2=-3/2$ and convergence to $-2$. The convergence interval is $0<\eta<1/3$, so only the second run lies inside it.

Solution · 3. Scale the learning rate inversely with the objective

Because $\nabla F=6\nabla f$, choose $\eta_F=1/6$ to reproduce the same update. The largest Hessian eigenvalue becomes $L_F=6$, giving $0<\eta_F<2/6=1/3$ for convergence from every initial vector.

Solution · 4. A flat direction preserves its initial coordinate

The gradient is $(\theta_1-1,0)^\top$. The first step gives $(1,7)^\top$, and every later iterate stays there. All vectors $(1,s)^\top$ with $s\in\mathbb R$ minimize the objective. Its Hessian $\operatorname{diag}(1,0)$ is positive semidefinite but not positive definite; the flat second direction prevents uniqueness.

Continue with least squares and residuals, SVD and principal components, or the course reading list.