How computers find the best answer, one step downhill at a time

Here is a sentence you might see in the first lecture:

$$\min_{\x\in\R^n}\ f(\x)\quad\text{subject to}\quad g_i(\x)\le 0,\ i=1,\dots,m.$$

Read aloud, it says: "Find the smallest value of the function $f$, over all lists $\x$ of $n$ real numbers, among those lists that make every $g_i(\x)$ at most zero." That's all. The rest of this chapter teaches you each piece, so you can do this translation yourself.

Sets: collections of things

A set is a collection of objects, called its elements. We write sets with curly braces: $\{1, 2, 3\}$ is the set containing 1, 2 and 3. Order and repetition don't matter: $\{3,1,2,1\}$ is the same set.

Often we describe a set by a rule instead of a list. The notation $\{x : x^2 < 4\}$ reads "the set of all $x$ such that $x^2<4$". The colon (sometimes a bar, $\{x \mid x^2<4\}$) means "such that".

Functions: machines that take an input and give one output

A function $f: A\to B$ takes each element of the set $A$ (the domain) and gives back exactly one element of $B$. In this course you'll mostly see $f:\R^n\to\R$: the input is a list of $n$ numbers and the output is a single number. That single number is the thing we want to make small: a cost, an error, an energy.

Example: $f(x_1,x_2) = x_1^2 + 3x_2^2$ takes the pair $(1,2)$ to $1+12=13$.

Sums, quantifiers and arrows

min, argmin, and the minimizer $\x^\star$

Two different questions hide in "minimize $f$":

• What is the smallest value? That's $\min_{\x} f(\x)$, a number, often called $f^\star$.
• Where is it reached? That's $\argmin_{\x} f(\x)$, the set of inputs where $f$ takes that smallest value. A point in this set is called a minimizer and written $\x^\star$ ("x star").

For $f(x)=(x-3)^2+1$: the minimum value is $1$, and $\argmin f=\{3\}$, so $x^\star=3$ and $f^\star=f(x^\star)=1$.

Sometimes there is no smallest value at all, only a value the function gets closer and closer to. For $f(x)=e^{x}$ on $\R$, the outputs approach 0 but never reach it. We then say the infimum is $0$ (written $\inf f = 0$) but the minimum doesn't exist. Part 2 makes this precise; for now just notice that "min" is a promise that the lowest value is actually reached.

A vector in $\R^n$ is a list of $n$ real numbers, written as a column: $$\x = \begin{pmatrix}x_1\\ x_2\\ \vdots\\ x_n\end{pmatrix}\in\R^n.$$ To save space we often write it as a row with a "transpose" mark, $\x=(x_1,\dots,x_n)^\top$. We print vectors in bold ($\x$, $\d$, $\g$) and plain numbers (also called scalars) in normal type ($\alpha$, $t$, $x_1$).

In $\R^2$ you can draw $\x=(3,2)^\top$ as an arrow from the origin to the point $(3,2)$. The same list can mean a position (a point) or a direction and distance (an arrow); context tells you which.

Adding and scaling

Add vectors entry by entry: $(1,2)^\top+(3,-1)^\top=(4,1)^\top$. As arrows: put the second arrow's tail at the first arrow's head. Multiply by a scalar to stretch: $2(1,2)^\top=(2,4)^\top$, and $-1$ flips the direction.

This is what every algorithm in this course does: $$\x_{k+1} = \x_k + \alpha_k \d_k,$$ "from the current point $\x_k$, move a distance controlled by $\alpha_k$ in the direction $\d_k$". The subscript $k$ counts the steps: $\x_0$ is where we start, $\x_1$ is after one step, and so on.

Example: $\x=(3,4)^\top$, $\y=(1,2)^\top$. Then $\x^\top\y=3+8=11$ and $\norm{\x}=\sqrt{9+16}=5$, which is Pythagoras' theorem.

What the dot product means

The dot product has a geometric meaning that makes it the most important operation in this course: $$\x^\top\y = \norm{\x}\,\norm{\y}\cos\theta,$$ where $\theta$ is the angle between the arrows. So:

• $\x^\top\y>0$: the arrows point "roughly the same way" (angle less than 90°).
• $\x^\top\y=0$: they are perpendicular (also called orthogonal).
• $\x^\top\y<0$: they point "roughly opposite ways" (angle more than 90°).

Later you'll learn that a direction $\d$ goes downhill from $\x$ whenever $\d^\top\grad f(\x)<0$, where $\grad f$ is the gradient. Everything starts here.

In words: the dot product can never exceed the product of the lengths. That's just $|\cos\theta|\le1$ in disguise. It has a consequence we'll use for gradient descent: among all directions $\d$ of length 1, the one that makes $\d^\top\g$ as negative as possible is $\d=-\g/\norm{\g}$, pointing exactly opposite to $\g$.

A second consequence, the triangle inequality $\norm{\x+\y}\le\norm{\x}+\norm{\y}$, says that going straight is never longer than taking a detour.

Other ways to measure length

The Euclidean norm is not the only sensible "size". Two others appear in optimization:

• $\norm{\x}_1=|x_1|+\dots+|x_n|$, the "taxicab" length (blocks walked on a grid).
• $\norm{\x}_\infty=\max_i |x_i|$, the largest single entry.

Any function that is positive for nonzero vectors, scales as $\norm{c\x}=|c|\norm{\x}$, and obeys the triangle inequality is called a norm. The set of vectors with norm at most 1 is the norm's unit ball: it looks different for each norm.

Graphs and level sets

For $f:\R^2\to\R$, the graph is the surface of points $(x_1,x_2,f(x_1,x_2))$ in 3-D. Drawing surfaces is hard, so we use the map view instead.

For $f(\x)=x_1^2+x_2^2$, the level set at height $c>0$ is a circle of radius $\sqrt c$. For $f(\x)=x_1^2+4x_2^2$, the level sets are ellipses that are twice as wide as they are tall. How stretched those ellipses are turns out to control how fast gradient descent runs: that's the condition number you'll meet in Part 0b and Part 5.

Three ways to read a contour map:

• Lines close together mean the height changes fast there: steep ground.
• Closed loops shrinking to a point mark a pit (a minimum) or a peak.
• A contour that crosses itself in an X marks a saddle, like a mountain pass. You'll study these in Part 3.

Recap: the derivative in one variable

For $f:\R\to\R$, the derivative $f'(x)$ is the slope of the graph at $x$: $$f'(x)=\lim_{h\to0}\frac{f(x+h)-f(x)}{h}.$$ "$\lim_{h\to0}$" means "the value this ratio settles down to as $h$ gets closer and closer to 0". The derivative gives the best straight-line approximation near $x$: $$f(x+h)\approx f(x)+f'(x)\,h\qquad\text{for small }h.$$ If $f'(x)>0$, nudging $x$ to the right increases $f$; if $f'(x)<0$, it decreases $f$. If $f'(x)=0$, the graph is flat there, which is where minima can hide.

Many variables: one slope per coordinate

Now take $f:\R^n\to\R$. Freeze every coordinate except $x_i$, and you have an ordinary one-variable function. Its slope is the partial derivative $\frac{\partial f}{\partial x_i}$ ("partial f, partial x i"). You compute it exactly like a school derivative, treating the other variables as constants.

Example: $f(x_1,x_2)=x_1^2+3x_1x_2$. Then $\frac{\partial f}{\partial x_1}=2x_1+3x_2$ (treat $x_2$ as a number) and $\frac{\partial f}{\partial x_2}=3x_1$ (treat $x_1$ as a number).

Slope in an arbitrary direction

Partial derivatives give slopes along the coordinate axes. What about along some other direction $\d$, say diagonally? Walk along the straight line $t\mapsto\x+t\d$ and measure how fast $f$ changes as $t$ starts increasing from 0. That rate is the directional derivative: $$D_{\d}f(\x)=\lim_{t\to0^+}\frac{f(\x+t\d)-f(\x)}{t}.$$ Here is the fact that makes the gradient so useful: you never need to compute this limit, because the gradient already knows the answer.

Why it's true, in one line: let $g(t)=f(\x+t\d)$. Each coordinate $x_i+td_i$ moves at speed $d_i$, so by the chain rule $g'(0)=\sum_i\frac{\partial f}{\partial x_i}(\x)\,d_i=\grad f(\x)^\top\d$.

Proof. By Cauchy–Schwarz (Part 0a), $-\norm{\grad f}\norm{\d}\le\grad f^\top\d\le\norm{\grad f}\norm{\d}$, and $\norm{\d}=1$. Equality on the right needs $\d$ to be a positive multiple of $\grad f$; on the left, a negative multiple. With length 1, that pins $\d$ down exactly. $\blacksquare$

This is the whole reason gradient descent steps along $-\grad f$: locally, it is the steepest way down. ("Locally" matters. Part 5 will show that steepest is not always fastest overall.)

One more picture worth keeping: the gradient is perpendicular to the level set through $\x$. Moving along a contour line keeps $f$ constant, so the slope along it is zero, so $\grad f^\top\d=0$ for the tangent direction $\d$.

A matrix is a machine that moves vectors

A $2\times2$ matrix $A=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ turns a vector $\v=(v_1,v_2)^\top$ into $$A\v=\begin{pmatrix}av_1+bv_2\\ cv_1+dv_2\end{pmatrix}.$$ Each entry of $A\v$ is a dot product of a row of $A$ with $\v$. The transpose $A^\top$ swaps rows and columns. $A$ is symmetric if $A^\top=A$, i.e. $b=c$. Every Hessian in this course is symmetric, so symmetric matrices are our focus.

The identity $I$ has 1s on the diagonal and 0s elsewhere: $I\v=\v$. The inverse $A^{-1}$, when it exists, undoes $A$: $A^{-1}A=I$. For $2\times2$: $A^{-1}=\frac{1}{ad-bc}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$, which exists when the determinant $\det A=ad-bc\ne0$.

Eigenvectors: directions that don't turn

Most vectors get rotated by $A$. A few special directions only get stretched (or flipped). If $$A\u=\lambda\u,\qquad \u\ne\0,$$ then $\u$ is an eigenvector and the number $\lambda$ ("lambda") is its eigenvalue: the stretch factor. To find eigenvalues, solve $\det(A-\lambda I)=0$. For a symmetric $2\times 2$ matrix $\begin{pmatrix}a&b\\b&d\end{pmatrix}$: $$\lambda^2-(a+d)\lambda+(ad-b^2)=0.$$ Useful shortcuts: the eigenvalues add up to the trace $a+d$ and multiply to the determinant $ad-b^2$.

What this buys us: write any vector in the eigenvector "coordinates", $\v=c_1\u_1+\dots+c_n\u_n$. Then $$\v^\top A\v=\lambda_1c_1^2+\lambda_2c_2^2+\dots+\lambda_nc_n^2.$$ The expression $\v^\top A\v$ is called the quadratic form of $A$. In eigen-coordinates it's just a weighted sum of squares, with the eigenvalues as weights. That one line explains everything below.

Both follow from the weighted-sum-of-squares formula: if every weight $\lambda_i$ is positive, a sum of $\lambda_i c_i^2$ is positive unless all $c_i=0$. And the sum lies between $\lambda_1\sum c_i^2$ and $\lambda_n\sum c_i^2$, where $\sum c_i^2=\norm{\v}^2$.

A quick hand test (Sylvester's criterion). A symmetric matrix is positive definite if and only if all its leading principal minors are positive: the top-left $1\times1$ determinant, the top-left $2\times2$ determinant, and so on. For $2\times2$: $a>0$ and $ad-b^2>0$.

The condition number. For $A\succ0$, $\kappa(A)=\lambda_{\max}/\lambda_{\min}\ge1$. The level sets $\{\v:\v^\top A\v=1\}$ are ellipses with half-axes $1/\sqrt{\lambda_i}$ along $\u_i$. So $\kappa$ says how stretched they are: the ratio of longest to shortest axis is $\sqrt\kappa$. A large $\kappa$ means a long narrow valley, and that is what slows gradient descent down.

Second derivatives in many variables

In one variable, $f''(x)$ measures how the slope changes: $f''>0$ means the graph curves upward like a cup. In $n$ variables there are $n^2$ second derivatives $\frac{\partial^2 f}{\partial x_i\partial x_j}$ (differentiate with respect to $x_j$, then $x_i$). We arrange them in a matrix.

Example: $f=x_1^2+3x_1x_2+5x_2^2$. Then $\grad f=(2x_1+3x_2,\ 3x_1+10x_2)^\top$ and $$\hess f=\begin{pmatrix}2&3\\3&10\end{pmatrix}.$$ Notice the matrix is symmetric: $\partial^2f/\partial x_1\partial x_2=\partial^2f/\partial x_2\partial x_1=3$. That's no accident.

Taylor's theorem: the local quadratic picture

The trick that turns many-variable calculus into one-variable calculus: walk along a straight line. Fix $\x$ and a step $\p$, and let $g(t)=f(\x+t\p)$. The chain rule gives $$g'(t)=\grad f(\x+t\p)^\top\p,\qquad g''(t)=\p^\top\hess f(\x+t\p)\,\p.$$ Now apply the school Taylor formula to $g$ between $t=0$ and $t=1$.

The symbol $o(\norm{\p}^2)$ ("little-o") means "an error that shrinks faster than $\norm{\p}^2$": divide it by $\norm{\p}^2$ and the result goes to 0 as $\p\to\0$. So for small steps, the quadratic part dominates the error.

Which form when? The book's advice, worth memorizing: the Lagrange form proves necessary conditions for a minimum (Part 3); the asymptotic form proves sufficient conditions (Part 3); the integral form proves global inequalities like the descent lemma (Part 6).

Quadratics are their own Taylor expansion

The most important functions in this course are quadratics $$f(\x)=\tfrac12\x^\top A\x-\b^\top\x+c,\qquad A\text{ symmetric}.$$ For them, $\grad f(\x)=A\x-\b$ and $\hess f(\x)=A$ everywhere, and the second-order Taylor formula is exact with no error term. Our fit-the-line loss is such a quadratic: expanding the squares gives $L(w,c)=\frac12\z^\top A\z-\b^\top\z+38$ with $\z=(w,c)^\top$, $$A=\begin{pmatrix}28&12\\12&6\end{pmatrix},\qquad \b=\begin{pmatrix}46\\20\end{pmatrix}.$$ Its eigenvalues are about $0.72$ and $33.3$, so $\kappa\approx46$: that's why the valley in Part 0a looked so long and thin.

Every problem in this course has the same three ingredients:

• Decision variables $\x=(x_1,\dots,x_n)^\top$: the numbers you're free to choose.
• Objective function $f(\x)$: a single number measuring how bad a choice is (a cost, an error, an energy). We minimize it. To maximize a profit $P$, minimize $-P$: same problem.
• Constraints: rules $g_i(\x)\le0$ and $h_j(\x)=0$ that a choice must satisfy. The choices that obey every rule form the feasible set $\mathcal F$.

Two ways a problem can go wrong before you even start: it can be infeasible ($\mathcal F=\emptyset$: no choice obeys all the rules), or unbounded (you can make $f$ as negative as you like, so $\inf f=-\infty$ and there's no minimizer). And even with a finite infimum, it may never be reached, as with $\min_x e^x$; again there is no minimizer.

Global and local minimizers

A ball of radius $\varepsilon$ around $\x^\star$ is $B(\x^\star,\varepsilon)=\{\x:\norm{\x-\x^\star}<\varepsilon\}$: every point closer than $\varepsilon$.

Every global minimizer is a local one, but not the other way round. A local minimizer only has to beat its neighbours. Think of a mountain lake: it's the lowest point around, but the sea is lower.

The algorithms in this course look only at local information (the value, slope and curvature where they stand). So by themselves they can only promise local answers. Part 4 (convexity) identifies the problems where local automatically means global.

A two-food version you can solve by eye

Using Stigler-style prices in dollars: oats cost $0.30 per serving and give 200 kcal and 10 g protein; milk costs $0.25 and gives 100 kcal and 10 g protein. You need at least 600 kcal and 40 g protein a day. Let $x_1$ be servings of oats and $x_2$ servings of milk.

$$\min_{\x}\ 0.30x_1+0.25x_2\quad\text{s.t.}\quad 2x_1+x_2\ge6,\quad x_1+x_2\ge4,\quad x_1\ge0,\ x_2\ge0.$$

(Calories in hundreds: $200x_1+100x_2\ge600$ becomes $2x_1+x_2\ge6$; protein: $10x_1+10x_2\ge40$ becomes $x_1+x_2\ge4$.) Both the objective and the constraints are linear: this is a linear program (LP).

Each constraint keeps one side of a straight line, so the feasible set is a region with straight edges, a polygon. The cost's level sets $0.30x_1+0.25x_2=C$ are parallel lines. Sliding that line towards lower cost until it's about to leave the feasible region, it last touches a corner (vertex). That's a general fact about linear programs: if an optimum exists, one is at a vertex.

A short history (what the lecture covered)

Problems are classified along four independent axes. Each one decides something concrete about which methods can work:

To see why this matters, take the simplest algorithm, gradient descent with a fixed step $\alpha>0$: $$x_{k+1}=x_k-\alpha f'(x_k),$$ and run it blindly on three one-variable functions, each breaking a different assumption.

Three failures, three missing assumptions

1. $f_1(x)=2x$ (linear, unconstrained). $f_1'\equiv2$, so $x_k=x_0-2k\alpha\to-\infty$ and $f_1(x_k)\to-\infty$. Nothing is wrong with the algorithm: the problem has no minimizer. It's unbounded below. Missing assumption: a minimizer exists.
2. $f_2(x)=|x|$ (convex but not smooth). The slope is $\pm1$ right up to the kink at 0, so the step $\alpha f'(x)$ never shrinks and the iterates cycle (with $\alpha=0.8$ from $0.5$: $0.5\to-0.3\to0.5\to\cdots$). Missing assumption: differentiability (smoothness). Non-smooth problems need subgradient methods with step sizes that shrink to zero, which are beyond this course.
3. $f_3(x)=x^4-2x^2$ (smooth but not convex). $f_3'(x)=4x(x^2-1)$ is zero at $-1,0,1$. Start exactly at $x_0=0$ and the gradient is 0, so the iterate never moves, even though 0 is a local maximum. Start at $x_0=0.01$ with a small step (say $\alpha=0.1$) and it rolls to $+1$; at $-0.01$, to $-1$. Missing assumption: convexity. Gradient descent can't tell a maximum, a saddle or a minimum apart by the gradient alone.

Try to minimize $f(x)=x$ over the open interval $(0,1)$. Every candidate $x$ loses to $x/2$, which is smaller and still in $(0,1)$. So there is no smallest value. Yet the number 0 still plays a special role as a bound: no value is below 0, and the values get as close to 0 as you like. We need a word for that number. It's the infimum.

Bounds

Let $E$ be a set of real numbers. A number $\beta$ is an upper bound of $E$ if $x\le\beta$ for every $x\in E$. If $E$ has an upper bound, $E$ is bounded above. Lower bounds and "bounded below" are defined the same way with $\ge$. A set can have many upper bounds: for $E=(0,1)$, the numbers $1$, $2$ and $100$ are all upper bounds. The interesting one is the smallest.

Read condition (ii) as a challenge game. Someone proposes a number $\gamma$ slightly below $\alpha$. You must answer with an element of $E$ that beats $\gamma$. If you can always answer, however close $\gamma$ is to $\alpha$, then $\alpha$ is the least upper bound. Condition (ii) is the one students forget when asked to prove that a number is a supremum.

Max versus sup. A maximum of $E$ is an upper bound that belongs to $E$. If $E$ has a maximum, then $\max E=\sup E$. The supremum may or may not belong to $E$: the maximum exists exactly when $\sup E\in E$. The same holds for minimum and infimum. In optimization language: a minimizer exists exactly when the infimum is attained.

Completeness: why we work in $\R$ and not in $\Q$

Does every bounded set have a supremum? In the rationals $\Q$, no. Take $E=\{p\in\Q:p>0,\ p^2\lt2\}$. It's bounded above by 2, but its least upper bound "should" be $\sqrt2$, which isn't rational (Part 0a's $\Q$ is fractions only). Whatever rational upper bound you propose, a slightly smaller rational upper bound exists. So inside $\Q$, $E$ has no supremum at all.

This is the foundation of the whole existence theory. For a nonempty feasible set $\mathcal F$, the optimal value $p^\star=\inf_{\x\in\mathcal F}f(\x)$ always makes sense: it's a real number if $f$ is bounded below on $\mathcal F$, and we write $p^\star=-\infty$ if it isn't. By convention $\inf_{\emptyset}f=+\infty$ for an infeasible problem. (Allowing $\pm\infty$ as values is called the extended real line.) So the value always exists. The minimizer is what may fail to exist, and the rest of this part is about when it's guaranteed.

One consequence of completeness gets used in nearly every proof with an $\varepsilon$ in it:

Distance and metric spaces

Everything in this chapter is built from one idea: the distance between two points. In $\R^n$ it's the Euclidean distance $d(\x,\y)=\norm{\x-\y}=\sqrt{\sum_i(x_i-y_i)^2}$. Rudin's approach is to list the three properties of distance that every argument actually uses. Any set with a distance function obeying them is a metric space, and everything below works there.

The 1-norm and $\infty$-norm of Part 0a also satisfy the triangle inequality, so $d_1(\x,\y)=\norm{\x-\y}_1$ and $d_\infty(\x,\y)=\norm{\x-\y}_\infty$ are metrics on $\R^n$ too. Their "balls" are diamonds and squares instead of discs. In $\R^n$ all three give the same open sets, closed sets and convergent sequences, so for this course the choice doesn't matter.

The vocabulary of Rudin's Definition 2.18

From now on, $X$ is a metric space (think $\R^2$) and $E\subseteq X$. The basic object is the neighbourhood of $p$ with radius $r>0$: $$N_r(p)=\{q\in X: d(p,q)\lt r\},$$ the open ball of Part 1, $B(p,r)$. In $\R$ it's the interval $(p-r,p+r)$; in $\R^2$ it's a disc without its rim.

Two theorems from Lecture 2 make the vocabulary consistent:

Theorem 2.19 says the name "open ball" is honest. Theorem 2.20 says a limit point is not an accident of one nearby point: shrink the ball and new points of $E$ keep appearing inside. That's why the limit point of $\{\frac1n\}$ is 0 (infinitely many terms crowd near it) and why a single point like $\frac13$ is isolated.

Closure: adding the missing limit points

Examples: the closure of $(0,1)$ is $[0,1]$; of the open unit disc, the closed unit disc; of $\{\frac1n\}$, the set $\{\frac1n\}\cup\{0\}$; of $\Q$ in $\R$, all of $\R$ (that's what "dense" means).

Now the link to Chapter 1. The supremum of a set can always be approached from inside the set, so it's either in the set or a limit point of it:

So a closed, bounded set of real numbers always has a maximum and a minimum. That's the seed of the Weierstrass theorem in Chapter 4: if we can show that the set of values $\{f(\x):\x\in K\}$ is closed and bounded, its infimum is attained, and that is a minimizer.

Read it as a contract. The sceptic names a tolerance $\varepsilon$; you must answer with an index $N$ after which every term is within $\varepsilon$ of $p$. The order of the quantifiers matters (Part 0a): $N$ is chosen after $\varepsilon$, so it may depend on it, and smaller tolerances usually need larger $N$. Limits are unique (two different limits $p\ne q$ would need terms within $\frac12d(p,q)$ of both, contradicting the triangle inequality).

Sequences describe closed sets and limit points

The $\varepsilon$-ball definitions of Chapter 2 have sequence versions, and in practice these are what you use:

• $p$ is a limit point of $E$ if and only if some sequence of points of $E\setminus\{p\}$ converges to $p$.
• $E$ is closed if and only if whenever a sequence of points of $E$ converges, its limit is in $E$. ("You can't escape a closed set by taking limits.")

Example: the sequence $\frac1n\in(0,1]$ converges to $0\notin(0,1]$, so $(0,1]$ isn't closed. An algorithm whose iterates stay feasible and converge, on a closed feasible set, converges to a feasible point.

Continuity

Building blocks: constants, $x\mapsto x_i$, sums, products, quotients (where the denominator isn't 0), and compositions of continuous functions are continuous (Rudin Thms. 4.7, 4.9). So polynomials, norms, $e^x$, $\log$ on $(0,\infty)$, and every objective in this course are continuous.

The widget's two discontinuities, written as sequence arguments:

• Step function ($1$ for $x\ge0$, $0$ for $x\lt0$): $x_n=-\frac1n\to0$ but $f(x_n)=0\not\to1=f(0)$.
• $\sin(1/x)$ with $f(0)=0$: $x_n=\frac1{\pi/2+2\pi n}\to0$ but $f(x_n)=1\not\to0$. No jump, just wild oscillation.
• $x\sin(1/x)$ with $f(0)=0$ is continuous at 0: $|f(x)-0|\le|x|$, so $\delta=\varepsilon$ works.

The intermediate value theorem

A continuous function can't get from one height to another without passing through every height in between. Its most common use: if $f(a)\lt0\lt f(b)$, then $f$ has a root in $(a,b)$. Halving the interval and keeping the half whose endpoints still have opposite signs is the bisection method, and the same "bracket then shrink" reasoning guarantees that the line searches of Part 6 can find an acceptable step. Both hypotheses matter: the step function above jumps from 0 to 1 and never takes the value $\frac12$.

Compact sets

Chapter 1 showed that a closed and bounded set of numbers contains its inf and sup. The idea that makes this work in $\R^n$ is compactness. Its official definition uses open covers: a collection of open sets whose union contains $K$.

You'll almost never check the open-cover definition directly. In this course, "compact" means "closed and bounded" (the book's exam tip allows Heine–Borel as a black box). Examples: $[a,b]$, closed balls, closed boxes, the unit circle, a finite set, $\{\frac1n\}\cup\{0\}$. Not compact: $(0,1]$ (not closed), $[0,\infty)$ and $\Z$ (not bounded), $\{\frac1n\}$ (not closed).

How the pieces fit: by Theorem 4.15 the set of values $f(K)$ is closed and bounded; by Theorem 2.28 a closed, bounded set of reals contains its inf and sup. So the infimum value is some $f(\mathbf q)$: a minimizer. Memorize the hypotheses precisely: $f$ continuous, $K$ nonempty, closed and bounded. Drop any one and the conclusion can fail:

A classic exam mistake (the book's pitfall): "$f$ is continuous and $\mathcal F$ is closed, therefore a minimizer exists." Boundedness is not optional: $f(x)=x$ is continuous on the closed set $\R$ and has no minimizer. The book's three-step checklist:

1. Is $f$ continuous on $\mathcal F$? (Nearly always, for the functions in this course.)
2. Is $\mathcal F$ closed? Constraints of the form $g(\x)\le c$ or $h(\x)=c$ with continuous $g,h$ give closed sets; strict inequalities usually don't.
3. Is $\mathcal F$ bounded? If not, is $f$ coercive? That's next.

Coercivity: Weierstrass on all of $\R^n$

Unconstrained problems live on $\R^n$, which is closed but not bounded, so Weierstrass doesn't apply directly. The fix: if $f$ grows without bound far away, the minimizer can't be far away, so we can restrict attention to a bounded region.

The running example, and where this goes next

For a quadratic $f(\x)=\frac12\x^\top A\x-\b^\top\x$ with $A\succ0$ and smallest eigenvalue $m>0$ (Part 0b), $\x^\top A\x\ge m\norm\x^2$ and, by Cauchy–Schwarz, $\b^\top\x\le\norm\b\norm\x$. So $$f(\x)\ \ge\ \tfrac m2\norm\x^2-\norm\b\,\norm\x\ \to\ +\infty:$$ positive definite quadratics are coercive, and always have a minimizer. Our fit-the-line loss $L(w,c)=\frac12\z^\top A\z-\b^\top\z+38$ has $m\approx0.721$, so it's coercive, and its minimizer $(1.5,\frac13)$ was guaranteed to exist before we computed it.

The same argument with the strong-convexity inequality in place of $\frac m2\norm\x^2$ is Tutorial 1, Problem 17(b): a strongly convex function on $\R^n$ has exactly one global minimizer (existence by coercivity and Weierstrass; uniqueness by strict convexity). Part 4 does it in full. Coercivity can also come from constraints: in the diet problem of Part 1, on the feasible set $\x\ge\0$, the cost satisfies $0.30x_1+0.25x_2\ge0.25\norm\x_1\to\infty$, so a cheapest diet exists.

The setting

From now on the problem is unconstrained: $$\min_{\x\in\R^n} f(\x).$$ More generally, $f$ may be defined only on an open set $U\subseteq\R^n$: a set where every point has a small ball around it that stays inside $U$. Openness is what lets you step a little in every direction from any point, and every proof in this part uses that.

How smooth is smooth enough?

The theorems carry hypotheses about how many derivatives $f$ has. Recall from Part 0b:

The hypotheses are not decoration. $f(x)=|x|$ is not even differentiable at 0. $f(x)=x|x|$ has $f'(x)=2|x|$, which is continuous, so $f\in C^1$; but $f'$ has a kink at 0, so $f''(0)$ doesn't exist and $f\notin C^2$. The first-order theory below needs $C^1$; the second-order theory (Chapter 3.2) needs $C^2$, both to have a Hessian at all and to know it's symmetric.

The idea of the proof: look at $f$ only along a straight line through $\x^\star$. That's a function of one variable, it has a local minimum at the centre, so its derivative there is zero. Since that's true for every line, the gradient must be zero. Learn the steps below; you should be able to write them out from memory.

What Taylor says at a critical point

At a critical point, $\grad f(\x^\star)=\0$, so the asymptotic Taylor formula (Part 0b) loses its linear term: $$f(\x^\star+\p)-f(\x^\star)=\tfrac12\,\p^\top\hess f(\x^\star)\,\p+o(\norm{\p}^2).$$ For small steps, the quadratic form decides. Write $H=\hess f(\x^\star)$, with eigenvalues $\lambda_i$ and orthonormal eigenvectors $\u_i$, and expand $\p=\sum_ic_i\u_i$. Then, as in Part 0b, $$\tfrac12\p^\top H\p=\tfrac12\left(\lambda_1c_1^2+\dots+\lambda_nc_n^2\right).$$ If every $\lambda_i\gt0$, every small step goes up: a bowl. If every $\lambda_i\lt0$, every step goes down: a cap. If some are positive and some negative, you go up along some eigenvectors and down along others: a saddle. If some $\lambda_i=0$, the quadratic part is flat in that direction, and the $o(\norm{\p}^2)$ terms we threw away decide.

Cases 1 and 2 are SOSC. Proof of case 3. Take unit eigenvectors $\u_+$ with $\lambda_+\gt0$ and $\u_-$ with $\lambda_-\lt0$. With $\p=\alpha\u_+$, Taylor gives $f(\x^\star+\alpha\u_+)-f(\x^\star)=\tfrac12\alpha^2\lambda_++o(\alpha^2)=\alpha^2\big(\tfrac12\lambda_++o(\alpha^2)/\alpha^2\big)\gt0$ for small $\alpha\ne0$. In the same way $f(\x^\star+\alpha\u_-)\lt f(\x^\star)$. Both points lie in any given neighbourhood once $|\alpha|$ is small, so $\x^\star$ is a saddle. $\blacksquare$

The 2×2 shortcut. For $H=\begin{pmatrix}a&b\\b&d\end{pmatrix}$, $\det H=\lambda_1\lambda_2$ and $\operatorname{tr}H=\lambda_1+\lambda_2$. So: $\det H\lt0$ ⇒ saddle; $\det H\gt0$ and $a\gt0$ ⇒ minimum; $\det H\gt0$ and $a\lt0$ ⇒ maximum; $\det H=0$ ⇒ inconclusive.

Counting the downhill directions: the Morse index

A critical point is non-degenerate if $\hess f(\x^\star)$ is invertible (no zero eigenvalue), and degenerate otherwise.

So up to a smooth change of coordinates, every non-degenerate critical point is a quadratic with $k$ downhill and $n-k$ uphill directions: index $0$ is a minimum, index $n$ a maximum, anything in between a saddle. For example $f=x^2-y^2$ (Tutorial 1, Problem 6) has $\grad f=(2x,-2y)$, a single critical point at the origin with Hessian $\operatorname{diag}(2,-2)$: a saddle of index 1. The Morse lemma says nothing about degenerate points; those come later in this chapter.

Escaping a saddle along negative curvature

Take $f(x_1,x_2)=\tfrac12x_1^2-\tfrac12x_2^2+\tfrac14x_2^4$ (Tutorial 1, Problem 7). Then $\grad f=\big(x_1,\ x_2(x_2^2-1)\big)$ and $\hess f=\operatorname{diag}(1,\ 3x_2^2-1)$. The critical points are:

• $(0,0)$: eigenvalues $1$ (eigenvector $(1,0)$) and $-1$ (eigenvector $(0,1)$): a saddle, Morse index 1.
• $(0,\pm1)$: eigenvalues $1$ and $2$: strict local minima, index 0, with $f=-\tfrac14$. They are global: $f=\tfrac12x_1^2+\tfrac14(x_2^2-1)^2-\tfrac14\ge-\tfrac14$.

Gradient descent with step $\alpha$ updates the two coordinates separately: $$x_1\leftarrow(1-\alpha)x_1,\qquad x_2\leftarrow x_2\big(1+\alpha(1-x_2^2)\big).$$ Started exactly on the $x_1$-axis ($x_2=0$), $x_2$ stays 0 forever and, for $0\lt\alpha\lt2$, $x_1\to0$: gradient descent converges to the saddle. Nudge $x_2$ to any $\epsilon\ne0$: near the saddle $|x_2|$ is multiplied by about $1+\alpha$ each step, so it grows geometrically along the negative-curvature eigenvector until it reaches the minimum at $(0,\pm1)$ (for $\alpha\lt1$; larger steps overshoot it). One step from $(0,\epsilon)$ already lowers $f$: $f(0,\epsilon)=-\tfrac12\epsilon^2+\tfrac14\epsilon^4\lt0$ for $0\lt|\epsilon|\lt\sqrt2$. A random perturbation almost surely has a component along $\u_-$, which is the idea behind perturbed gradient descent.

Why plain Newton walks into saddles

Newton's method (covered properly in Part 10) jumps to the critical point of the local quadratic model: $\x_{k+1}=\x_k-[\hess f(\x_k)]^{-1}\grad f(\x_k)$. It is a root-finder for $\grad f=\0$, and it doesn't care whether that root is a minimum. Near the saddle above, $3x_2^2-1\lt0$ and the Newton update in $x_2$ is $x_2\leftarrow2x_2^3/(3x_2^2-1)$, which pulls $x_2$ towards 0 very fast.

The standard remedies (Tutorial 1, Problem 10(c)) all put curvature-sign information back in: damping (solve $(\hess f+\tau I)\d=-\grad f$ with $\tau\gt-\lambda_{\min}$, which tends to steepest descent as $\tau\to\infty$); eigenvalue rectification (replace $H=U\Lambda U^\top$ by $U|\Lambda|U^\top$, which on this example is $I$ and turns the $y$-step around); and trust regions (minimize the model within $\norm{\d}\le\Delta$; with negative curvature the solution lies on the boundary, along the most negative eigenvector).

Degenerate critical points: when the Hessian says nothing

If $\hess f(\x^\star)$ has a zero eigenvalue, anything can happen. One-variable warm-up: $x^4$ (minimum), $-x^4$ (maximum), $x^3$ (neither), all with $f'(0)=f''(0)=0$. Two-variable versions, all with $\hess f(0,0)=\operatorname{diag}(2,0)$: $x^2+y^4$ is a strict minimum; $x^2-y^4$ and $x^2+y^3$ are saddles (look along the $y$-axis); $x^2$ alone has a whole line of minimizers.

Peano's surface: a minimum along every line, and still not a minimum

The book flags this as a favourite exam question. Let $$f(x,y)=(y-x^2)(y-2x^2)=y^2-3x^2y+2x^4.$$ The two parabolas $y=x^2$ and $y=2x^2$ are where $f=0$. Between them (in the thin sliver $x^2\lt y\lt2x^2$) one factor is positive and the other negative, so $f\lt0$; everywhere else $f\ge0$.

Convex sets: no dents, no holes

Take two points $\x$ and $\y$. The points on the straight segment between them are exactly the convex combinations $\theta\x+(1-\theta)\y$ with $\theta\in[0,1]$: at $\theta=1$ you're at $\x$, at $\theta=0$ you're at $\y$, and $\theta=\tfrac12$ is the midpoint. (In one variable, $\theta\cdot3+(1-\theta)\cdot7$ sweeps from 7 down to 3 as $\theta$ goes from 0 to 1.)

Examples. All of $\R^n$; a ball $\{\x:\norm{\x-\mathbf c}\le r\}$; a half-space $\{\x:\a^\top\x\le\beta\}$; a line; a single point; the empty set. Non-examples. A ring (annulus): the segment between two opposite points passes through the hole. Two separate discs: the segment between them crosses the gap. A crescent or a peanut shape: the segment cuts across the dent.

Intersections stay convex. If $C_1$ and $C_2$ are convex and $\x,\y$ lie in both, the segment lies in $C_1$ (since $C_1$ is convex) and in $C_2$, so it lies in $C_1\cap C_2$. This is why the feasible region of Part 1's diet problem, an intersection of half-planes, is a convex polygon.

Convex functions: the chord lies above the graph

Now take a function $f$ and two inputs $\x,\y$. Draw the straight line (the chord) from the point $(\x,f(\x))$ on the graph to the point $(\y,f(\y))$. At the input $\theta\x+(1-\theta)\y$, the chord has height $\theta f(\x)+(1-\theta)f(\y)$, the same mix of the two end heights. Convexity says the graph never rises above the chord.

The domain must be convex, otherwise the point $\theta\x+(1-\theta)\y$ might not even be in it. This is why the definition starts with "let $C$ be a convex set".

Why the epigraph? If the graph had a dent, the region above it would have a dent too, and a segment between two points of the region could pass under the graph. The epigraph turns "convex function" into "convex set", so pictures of sets apply to functions.

A catalogue of convex functions

• Affine functions $f(\x)=\a^\top\x+\beta$: the definition holds with equality, so they are convex and concave. They're the boundary case.
• Every norm, e.g. $\norm{\x}_2$, $\norm{\x}_1$, $|x|$: by the triangle inequality and $\norm{c\v}=|c|\norm{\v}$, $\ \norm{\theta\x+(1-\theta)\y}\le\theta\norm{\x}+(1-\theta)\norm{\y}$.
• Convex quadratics $\tfrac12\x^\top A\x-\b^\top\x+c$ with $A\succeq0$ (proved in Chapter 4.2), including the fit-the-line loss $L(w,c)$ and least squares $\tfrac12\norm{A\x-\b}^2$.
• One-variable classics: $e^x$; $x^p$ on $[0,\infty)$ for $p\ge1$; $-\log x$ and $x\log x$ on $(0,\infty)$.
• Log-sum-exp $\log\sum_ie^{x_i}$, the smooth version of $\max_i x_i$ used in machine learning (proved in Chapter 4.2).

Not convex: $x^4-2x^2$ (two valleys), $\sin x$, $x^3$ (concave for $x\lt0$), $\sqrt{|x|}$, and $x_1x_2$ (a saddle).

Why (2): $M(\theta\x+(1-\theta)\y)+\mathbf c=\theta(M\x+\mathbf c)+(1-\theta)(M\y+\mathbf c)$, so a segment in $\x$ maps to a segment in $M\x+\mathbf c$, and $f$'s chord inequality applies there. Why (3): $f(\theta\x+(1-\theta)\y)\le\theta f(\x)+(1-\theta)f(\y)\le\theta\max\{f,g\}(\x)+(1-\theta)\max\{f,g\}(\y)$, and the same for $g$; so the larger of the two is also below the right-hand side. Why (4): if $f(\x)\le c$ and $f(\y)\le c$ then $f(\theta\x+(1-\theta)\y)\le\theta c+(1-\theta)c=c$.

First order: tangents are global under-estimators

Recall from Part 0b that $f(\x)+\grad f(\x)^\top(\y-\x)$ is the first-order Taylor approximation of $f(\y)$ around $\x$: the tangent line (or tangent plane). For a general function it is only good near $\x$. For a convex function something much stronger holds: it is a lower bound everywhere.

In one variable these read: $f(y)\ge f(x)+f'(x)(y-x)$; $f'$ is nondecreasing ($(f'(y)-f'(x))(y-x)\ge0$ says $f'$ moves in the same direction as $x$); and $f''\ge0$. A function is convex exactly when its slope never decreases.

The payoff of the tangent inequality. If $\grad f(\x^\star)=\0$, it reads $f(\y)\ge f(\x^\star)$ for every $\y$. A flat tangent at a point of a convex function is a floor under the whole graph. Chapter 4.3 builds on this.

The proofs (examinable)

Tutorial 1 Problems 14 and 16 ask for these. Each proof is short once you know the one trick it uses; learn the trick, not the algebra.

Applying the Hessian test

Quadratics. $f(\x)=\tfrac12\x^\top A\x-\b^\top\x+c$ has $\hess f=A$ at every point, so $f$ is convex $\iff A\succeq0$. Least squares $\tfrac12\norm{A\x-\b}^2$ has Hessian $A^\top A$, and $\v^\top A^\top A\v=\norm{A\v}^2\ge0$: always convex. The fit-the-line loss has Hessian $\begin{pmatrix}28&12\\12&6\end{pmatrix}$ with eigenvalues $\approx0.721$ and $33.28$, both positive: convex.

Part 3 is one line: the minimizers are the sublevel set $\{\x:f(\x)\le\min f\}$, which is convex by Chapter 4.1. So a convex function can have no minimizer ($e^x$), exactly one ($x^2$), or a whole convex set of them ($(x_1+x_2-1)^2$ has a whole line), but never, say, exactly two.

Why this matters for algorithms. Gradient descent stops when $\norm{\grad f(\x_k)}\approx0$. For general $f$ that only certifies a stationary point, which might be a saddle or a poor local minimum. For convex $f$ it certifies (approximately) the global minimum. Every convergence theorem from Lecture 8 onwards assumes convexity for exactly this reason.

The hierarchy: strictly and strongly convex

Convexity alone allows flat stretches (the chord can lie on the graph) and allows no minimizer at all. Two stronger notions fix these.

Picture it. Strong convexity says that at every point there is not just a tangent plane below $f$, but a whole upward parabola of curvature $\mu$ below it. The function curves up at least as fast as $\tfrac\mu2\norm{\x}^2$, everywhere. A useful equivalent: $f$ is $\mu$-strongly convex iff $f(\x)-\tfrac\mu2\norm{\x}^2$ is still convex (for $C^2$ functions: $\hess f-\mu I\succeq0$).

Examples. $\tfrac12\x^\top A\x-\b^\top\x$ with $A\succ0$ is $\lambda_{\min}(A)$-strongly convex; ridge regression is $\lambda$-strongly convex. The worked example of Chapter 4.1 showed $x^2$ is $2$-strongly convex.

Compare with strong convexity, the same expression with $\mu$ and $\ge$. Putting them together:

The middle quantity is "how far $f$ rises above its tangent". In one variable, Taylor says it is about $\frac12f''\cdot(y-x)^2$, so the sandwich is the statement $\mu\le f''\le L$ everywhere. For a quadratic $\tfrac12\x^\top A\x-\b^\top\x$, the middle quantity is exactly $\frac12(\y-\x)^\top A(\y-\x)$, and the Rayleigh bounds of Part 0b give the sandwich with $\mu=\lambda_{\min}(A)$, $L=\lambda_{\max}(A)$.

The bridge to Part 5

Part 5 runs gradient descent on convex quadratics and shows the error shrinks by a factor about $\frac{\kappa-1}{\kappa+1}$ per step (with the best constant step). For $\kappa=2$ that's $\tfrac13$ per step: fast. For the fit-the-line loss, $\kappa\approx46.1$ gives about $0.958$ per step: slow zig-zagging along the valley. Lectures 9–10 prove the same kind of rates for all of $\mathcal F_L^{1,1}$ (an $O(1/k)$ rate) and $\mathcal S_{\mu,L}^{1,1}$ (a linear rate governed by $\kappa$), using the sandwich as their main tool. In every one of those proofs, $L$ sets the safe step size ($h\le1/L$ or $2/(\mu+L)$) and $\mu$ sets how much progress each step guarantees.

Recall from Part 0b that at a point $\x$ with $\grad f(\x)\ne\0$, the direction of fastest decrease is $-\grad f(\x)$: among unit directions $\d$, the slope $\grad f(\x)^\top\d$ is smallest (equal to $-\norm{\grad f(\x)}$) exactly when $\d=-\grad f(\x)/\norm{\grad f(\x)}$ (Cauchy–Schwarz). Gradient descent simply keeps moving in that direction.

Each iteration needs one gradient and a few vector operations: $O(n)$ memory and arithmetic beyond the gradient itself. Compare (Tutorial 1 §9.2):

With $n=10^7$ parameters (an ordinary neural network), an $n\times n$ matrix has $10^{14}$ entries: it cannot even be stored. That is why gradient descent and its relatives dominate large-scale computing, and why it matters so much to understand how fast it converges.

Each step minimizes a simple model of $f$

Why should a step of size $\alpha$ along $-\g_k$ be sensible, and not just "for very small $\alpha$"? Here is a clean answer from the lecture. Near $\x_k$, replace $f$ by the surrogate model $$m_k(\y)=f(\x_k)+\g_k^\top(\y-\x_k)+\frac1{2\alpha}\norm{\y-\x_k}^2 .$$ It is the tangent plane (first two terms) plus a round bowl of curvature $1/\alpha$ in every direction. Such a bowl is called isotropic: it curves the same amount in every direction.

So a small $\alpha$ means a steep, narrow model bowl and a short step; a large $\alpha$ means a shallow, wide bowl and a long step. The value the model predicts at its minimizer is $$m_k(\x_k-\alpha\g_k)=f(\x_k)-\alpha\norm{\g_k}^2+\tfrac{\alpha}{2}\norm{\g_k}^2=f(\x_k)-\tfrac\alpha2\norm{\g_k}^2 .$$

When can we trust the prediction? If the model lies above $f$ everywhere (we say $m_k$ majorizes $f$), then $$f(\x_{k+1})\le m_k(\x_{k+1})=f(\x_k)-\tfrac\alpha2\norm{\g_k}^2,$$ a guaranteed decrease. This "build an upper model, minimize it, repeat" scheme is called majorize–minimize. For a quadratic $f(\x)=\tfrac12\x^\top A\x-\b^\top\x$ the second-order Taylor expansion is exact (Part 0b), so $$m_k(\y)-f(\y)=\tfrac12(\y-\x_k)^\top\Big(\tfrac1\alpha I-A\Big)(\y-\x_k),$$ which is $\ge0$ for every $\y$ exactly when $\tfrac1\alpha\ge\lambda_{\max}(A)=L$, that is, $\alpha\le 1/L$. In Part 6 the same idea, with $L$ a bound on the curvature of a general $f$, becomes the Descent Lemma.

Choosing the step size

Three strategies run through the course:

• Fixed step $\alpha_k=\alpha$: cheapest. Needs some knowledge of the curvature $L$. Chapter 5.2 analyses it exactly on quadratics.
• Exact line search: choose $\alpha_k$ to minimize $f$ along the ray $\x_k-\alpha\g_k$. On a quadratic this has a closed form (Chapter 5.3); for general $f$ it is itself an optimization problem.
• Inexact line search (Armijo, Wolfe): accept any step that decreases $f$ "enough". This is Part 6.

A fixed step can fail badly when the curvature is unbounded. On $f(x)=x^4$, gradient descent with $\alpha=0.1$ is $x_{k+1}=x_k(1-0.4x_k^2)$; from $x_0=3$ it gives $x_1=3(1-3.6)=-7.8$ and then explodes. The curvature $f''(x)=12x^2$ grows without bound, so no single $\alpha$ is safe everywhere (Tutorial 1, Problem 28). On quadratics, the curvature is the constant matrix $A$, and everything can be computed exactly. That is why this part works on quadratics.

(The gap formula: expand $\tfrac12(\x-\x^\star)^\top A(\x-\x^\star)=\tfrac12\x^\top A\x-\x^{\star\top}A\x+\tfrac12\x^{\star\top}A\x^\star$, use $A\x^\star=\b$ so the middle term is $-\b^\top\x$, and note $f(\x^\star)=-\tfrac12\x^{\star\top}A\x^\star$.)

First, one variable: the whole story on one parabola

For $f(x)=\tfrac L2x^2$, $f'(x)=Lx$ and the update is $x_{k+1}=x_k-\alpha Lx_k=(1-\alpha L)x_k$, so $x_k=(1-\alpha L)^kx_0$. Everything depends on the single factor $1-\alpha L$:

So $2/L$ is not a cautious technical bound: it is the exact threshold. In $n$ dimensions the same thing happens independently along each eigenvector, each with its own curvature $\lambda_i$. Before proving it, test your intuition.

Step 1: the error recursion

Because $\b=A\x^\star$, the gradient is $\g_k=A\x_k-A\x^\star=A\e_k$. Subtract $\x^\star$ from both sides of $\x_{k+1}=\x_k-\alpha\g_k$: $$\e_{k+1}=\e_k-\alpha A\e_k=(I-\alpha A)\,\e_k,\qquad\text{so}\qquad \e_k=(I-\alpha A)^k\e_0 .$$

Step 2: decouple in the eigenbasis

Write the error in eigenvector coordinates: $\e_k=\sum_i z_{i,k}\u_i$, i.e. $\z_k=U^\top\e_k$ where $U$ has the eigenvectors as columns. Since $A\u_i=\lambda_i\u_i$, we get $(I-\alpha A)\u_i=(1-\alpha\lambda_i)\u_i$, so $$z_{i,k+1}=(1-\alpha\lambda_i)\,z_{i,k}\qquad\Longrightarrow\qquad z_{i,k}=(1-\alpha\lambda_i)^k z_{i,0}.$$ The $n$-dimensional problem has split into $n$ independent one-variable parabolas, one per eigen-direction, each with its own curvature $\lambda_i$. And because $U$ is orthogonal, $\norm{\e_k}=\norm{\z_k}$: lengths are the same in either coordinate system.

How many iterations? The $O(\kappa\log(1/\eps))$ law

To guarantee $\norm{\e_k}\le\eps\norm{\e_0}$ it suffices that $\rho^k\le\eps$, i.e. $k\ge\dfrac{\ln(1/\eps)}{\ln(1/\rho)}$. With $\rho=\frac{\kappa-1}{\kappa+1}$, $$\ln\frac1\rho=\ln\Big(1+\frac{2}{\kappa-1}\Big)\ge\frac{2/(\kappa-1)}{1+2/(\kappa-1)}=\frac{2}{\kappa+1},$$ using $\ln(1+x)\ge\frac{x}{1+x}$ for $x>0$. So $k\ge\frac{\kappa+1}{2}\ln\frac1\eps$ steps are enough: the number of iterations grows linearly in $\kappa$ and only logarithmically in the accuracy. Doubling $\kappa$ roughly doubles the work. This $O(\kappa\log(1/\eps))$ count is one of the most quoted facts in the course.

The simpler choice $\alpha=1/L$ gives $\rho=\max(1-\frac1\kappa,0)=1-\frac1\kappa$, about twice as many steps: still $O(\kappa\log(1/\eps))$.

Why it is slow. The step must respect the steepest direction ($\alpha\lt2/L$), but progress along the flattest direction is then only a fraction $\alpha m\lt 2/\kappa$ of the remaining distance per step. One curvature limits the step; the other limits the progress.

The function value also decreases every step. Expanding the quadratic exactly, $$f(\x_k-\alpha\g_k)=f(\x_k)-\alpha\norm{\g_k}^2+\tfrac{\alpha^2}{2}\g_k^\top A\g_k\le f(\x_k)-\alpha\Big(1-\tfrac{\alpha L}{2}\Big)\norm{\g_k}^2,$$ using $\g_k^\top A\g_k\le L\norm{\g_k}^2$ (Rayleigh, Part 0b). For $0\lt\alpha\lt2/L$ the bracket is positive, so $f$ strictly decreases until $\g_k=\0$. And the gap, $E=\tfrac12\sum_i\lambda_iz_i^2$, shrinks by at least $\rho(\alpha)^2$ per step, since every $z_i$ shrinks by at least $\rho(\alpha)$.

By the chain rule, $\phi'(\alpha)=\grad f(\x_k+\alpha\d_k)^\top\d_k$: the slope of $f$ along the line. In particular $\phi'(0)=\g_k^\top\d_k\lt0$, so the line starts downhill.

Geometrically: you stop exactly where the ray becomes tangent to a level set, and the new gradient is perpendicular to that level set (Part 0b), hence perpendicular to the ray you came along. So each new direction turns by exactly $90^\circ$.

Two useful consequences. By the Rayleigh bounds $m\norm{\g}^2\le\g^\top A\g\le L\norm{\g}^2$, every exact step satisfies $\frac1L\le\alpha_k\le\frac1m$: sometimes it takes steps far longer than the fixed-step limit $2/L$, safely, because they are tailored to the current direction. And the cost per step is still one matrix–vector product: compute $A\g_k$ once, use it for $\alpha_k$, and update $\g_{k+1}=\g_k-\alpha_kA\g_k$.

The convergence rate

You need the statement, not the proof (the book marks the proof as not examinable; it is in the box below). Recognize $\frac{4\kappa}{(1+\kappa)^2}$ on sight: $1-\frac{4\kappa}{(1+\kappa)^2}=\frac{(\kappa-1)^2}{(\kappa+1)^2}$.

Reading the result

• The bound is tight. Equality in Kantorovich happens when $\g_k$ has equal weight on the eigenvectors for $m$ and $L$, as in the worked example ($\g_0=(20,20)$). Then two steps reproduce the same situation scaled down, and the worst-case ratio is hit at every step. The book's lab measured per-step ratios $0.440$, $0.921$, $0.991$ for $\kappa=5,50,500$ against the bounds $0.444$, $0.923$, $0.992$: from a generic start the method settles into this worst-case zig-zag.
• It can also be much faster. If $\g_0$ is an eigenvector, $\alpha_0=1/\lambda$ and the method lands on $\x^\star$ in one step. And if $\kappa=1$ (a round bowl) every start converges in one step.
• Compare with the best fixed step. $\alpha^\star=\frac2{m+L}$ shrinks every eigen-component by at least $\frac{\kappa-1}{\kappa+1}$, so it also shrinks $E=\frac12\sum\lambda_iz_i^2$ by at least $\left(\frac{\kappa-1}{\kappa+1}\right)^2$: the same guarantee. Exact line search does not improve the worst case; its advantage is that it needs no knowledge of $m$ and $L$. Both need $O(\kappa\log(1/\eps))$ iterations.
• Rates for $E$ versus rates for $\norm{\e}$. Since $\frac m2\norm{\e}^2\le E\le\frac L2\norm{\e}^2$, a rate $\rho^2$ for $E$ corresponds to a rate $\rho$ for $\norm{\e}$ (up to a constant factor $\sqrt\kappa$). Always say which quantity a rate refers to.

The line-search template

Every method in Parts 5–10 has the same shape. At the current point $\x_k$:

1. choose a direction $\d_k$ that goes downhill (steepest descent uses $\d_k=-\g_k$, Newton uses something else);
2. choose a step size $\alpha_k\gt0$;
3. move: $\x_{k+1}=\x_k+\alpha_k\d_k$.

This part is entirely about step 2. Once $\x_k$ and $\d_k$ are fixed, the only unknown is the number $\alpha$, so we look at $f$ along the ray only.

The formula for $\phi'$ is the chain rule from Part 0b: moving $\alpha$ by a little moves the point along $\d_k$, and the slope of $f$ along $\d_k$ is $\grad f^\top\d_k$. So $\phi'(0)$ is the directional derivative at the start. It is negative exactly because $\d_k$ is a descent direction: the graph of $\phi$ starts by going down.

For steepest descent, $\d_k=-\g_k$ and $\phi'(0)=-\g_k^\top\g_k=-\norm{\g_k}^2$.

Why not just minimize φ exactly?

In Part 5 we did: for a quadratic $f(\x)=\frac12\x^\top A\x-\b^\top\x$, $\phi$ is a parabola in $\alpha$, and its minimizer has the closed form $\alpha_k=\g_k^\top\g_k/\g_k^\top A\g_k$. For anything else, $\phi'(\alpha)=0$ is a nonlinear equation.

Take $f(x_1,x_2)=x_1^4+2x_2^4$ at $\x_0=(1,1)^\top$ with $\d_0=-\g_0=-(4,8)^\top$. Then $\phi(\alpha)=(1-4\alpha)^4+2(1-8\alpha)^4$ and $$\phi'(\alpha)=-16(1-4\alpha)^3-64(1-8\alpha)^3=0$$ is a cubic with no clean root. A numerical solver finds $\alpha^\star\approx0.1549$. For a non-polynomial $f$ the equation is transcendental. Either way you must run an inner iterative solver (Newton on $\phi'$, or golden-section search) at every outer iteration, paying many function evaluations for one step. And the payoff is small: the next direction will change anyway, so a perfect step along this one is wasted precision.

So we ask for less: a step that is good enough to make the convergence proofs of Part 7 work, and that is cheap to find.

Is "f goes down" good enough?

The most naive rule is: accept any $\alpha$ with $\phi(\alpha)\lt\phi(0)$. It fails, in two opposite ways. Both are visible on the simplest function there is.

The two failure modes

For $f(x)=x^2$ and $\d_k=-2x_k$, the exact step is $\alpha=\tfrac12$ (it lands on $0$). The schedules in the widget are mirror images around it:

• Steps too short ($\alpha_k=\tfrac14,\tfrac18,\dots$). Each step decreases $f$, but the steps are summable ($\sum_k\alpha_k=\tfrac12\lt\infty$), so the total distance the method can ever travel is finite. The iterates run out of steam at $x_\infty\approx0.2888$.
• Steps too long ($\alpha_k=\tfrac34,\tfrac78,\dots$). Then $1-2\alpha_k=-(1-2^{-(k+1)})$: the iterate jumps over the minimum and lands almost as far away on the other side. $|x_k|$ is exactly the same as before, so again it stalls at distance $0.2888$, while $f$ decreases each time by a vanishing amount.

[NW] Fig. 3.2 shows the same disease with function values $5/k\to0$ while the true minimum is $-1$. The cure is two tests: one that demands a decrease proportional to the step (this kills overly long steps), and one that refuses steps that stop while $\phi$ is still steeply decreasing (this kills overly short ones). Chapters 6.3 and 6.4 build them. Chapter 6.2 builds the tool that proves they work.

Lipschitz continuity

A function $h$ is Lipschitz continuous with constant $L$ if $\norm{h(\x)-h(\y)}\le L\norm{\x-\y}$ for all $\x,\y$. In words: the output can't change faster than $L$ times the input change. In one variable: every chord of the graph has slope between $-L$ and $L$.

• $h(x)=|x|$ is Lipschitz with $L=1$ (kink and all).
• $h(x)=x^2$ is not Lipschitz on $\R$: its chords get arbitrarily steep. On $[-3,3]$ it is, with $L=6$.
• $h(x)=\sqrt{|x|}$ is continuous but not Lipschitz near $0$: chords from $0$ have slope $1/\sqrt{|x|}\to\infty$.

For optimization, the useful thing to bound is not $f$ itself but its gradient.

The smallest valid $L$ is the largest curvature (in absolute value) anywhere. Examples:

• Quadratics $f=\frac12\x^\top A\x-\b^\top\x$ with $A\succ0$: $\hess f=A$, so $L=\lambda_{\max}(A)$. This is why the book calls the largest eigenvalue $L$. Our fit-the-line loss has $L\approx33.28$.
• $f(x)=\ln(1+e^x)$ (the logistic loss): $f''(x)=\sigma(x)(1-\sigma(x))$ with $\sigma(x)=1/(1+e^{-x})$, and this is at most $\tfrac14$. So $L=\tfrac14$.
• $f(x)=x^4$: $f''(x)=12x^2$ is unbounded, so $x^4$ is not $L$-smooth on $\R$ for any $L$. (It is on a bounded interval.) Tutorial 1 Q23 shows the consequence: for every fixed step size there are starting points from which gradient descent on $x^4$ diverges.

Reading it. The first two terms on the right are the tangent plane at $\x$. The lemma says: $f$ can rise above its tangent by at most $\frac L2\norm{\y-\x}^2$. So $f$ is trapped below a parabola (a bowl in $n$ dimensions) with curvature $L$ that touches $f$ at $\x$. It is an upper bound only: $f$ may fall far below it, especially when $f$ is not convex.

Proof. Put $\y=\x-\alpha\grad f(\x)$ in the descent lemma: $\grad f(\x)^\top(\y-\x)=-\alpha\norm{\grad f(\x)}^2$ and $\frac L2\norm{\y-\x}^2=\frac{L\alpha^2}2\norm{\grad f(\x)}^2$. Add them. The function $\alpha(1-L\alpha/2)$ is a downward parabola in $\alpha$ with roots $0$ and $2/L$ and peak at $\alpha=1/L$, value $\frac1{2L}$. $\blacksquare$

Two connections. (1) Part 5 found that constant-step gradient descent on a quadratic is stable exactly when $0\lt\alpha\lt2/L$. The corollary extends the same threshold to every $L$-smooth function, convex or not. (2) Part 5 also showed that the gradient step of size $\alpha$ minimizes the surrogate $f(\x_k)+\g_k^\top(\y-\x_k)+\frac1{2\alpha}\norm{\y-\x_k}^2$. With $\alpha=1/L$ that surrogate is exactly the descent-lemma bound. So the $1/L$ step minimizes a function that lies above $f$ everywhere: whatever it promises, $f$ delivers at least that much. This is the "majorize, then minimize" idea.

Why this matters for line search. In practice you rarely know $L$, so you can't simply use $1/L$. But the corollary tells us that small enough steps always give a decrease proportional to $\alpha\norm{\g_k}^2$. Chapter 6.4 uses exactly this to prove that backtracking terminates with a step no smaller than a constant times $1/L$.

Sufficient decrease (Armijo)

The tangent line at $0$, $\phi(0)+\alpha\phi'(0)$, is what $f$ would do if it stayed linear. Real functions curve up, so we can't ask for that much decrease. Armijo asks for a fixed fraction $c_1$ of it.

The right side is a line of slope $c_1\phi'(0)$: negative, but much shallower than the tangent. Acceptable steps are those where the graph of $\phi$ lies on or below this line. The decrease achieved is at least $c_1\alpha|\phi'(0)|$: proportional to the step. That proportionality is what kills the "too long" failure of Chapter 6.1: overshooting steps barely decrease $f$, so they fail.

Small steps always pass. By Taylor, $\phi(\alpha)=\phi(0)+\alpha\phi'(0)+o(\alpha)$. Since $c_1\lt1$ and $\phi'(0)\lt0$, the gap $(1-c_1)\alpha|\phi'(0)|$ between the Armijo line and the tangent beats the $o(\alpha)$ error for all small enough $\alpha$. So Armijo accepts an entire interval $(0,\bar\alpha]$. This is good news (an acceptable step always exists) and bad news: Armijo is a ceiling, never a floor. It happily accepts uselessly tiny steps.

Why $c_1\le\frac12$ is usual. If $\phi$ is a parabola $\phi(0)+\phi'(0)\alpha+\frac a2\alpha^2$ ($a\gt0$), its minimizer $\alpha^\star=-\phi'(0)/a$ gives $\phi(\alpha^\star)=\phi(0)+\frac12\alpha^\star\phi'(0)$. So the exact minimizer passes Armijo exactly when $c_1\le\frac12$. Near a minimizer most smooth $\phi$ look like parabolas, so $c_1\gt\frac12$ would reject the very steps that Newton-type methods produce.

A floor: Goldstein's second line

The right inequality is Armijo with $c_1=c$. The left one adds a steeper line of slope $(1-c)\phi'(0)$ and demands $\phi(\alpha)$ stay above it. Near $\alpha=0$, $\phi$ hugs its tangent, which is below the steep line, so tiny steps now fail: we have a floor. The requirement $c\lt\frac12$ makes the shallow line lie above the steep one ($c\lt1-c$), so there is room between them, and (by the parabola computation above) it lets the minimizer of a quadratic pass. Its drawback ([NW] p.41): on a non-quadratic $\phi$ the lower line can cut off every minimizer of $\phi$.

A floor using the slope: the Wolfe conditions

Instead of a second line, look at the slope of $\phi$ where you stop. If $\phi'(\alpha)$ is still strongly negative, $f$ is still dropping fast, so you stopped too early. If the slope has flattened (or turned positive), there is little more to gain along this ray.

Since $\phi'(0)\lt0$, the curvature condition says the slope at $\alpha$ is "less negative" than $c_2$ times the starting slope. Strong Wolfe also forbids $\phi'(\alpha)$ from being too positive, which keeps $\alpha$ near a stationary point of $\phi$ rather than far up the far side of a valley.

Fletcher [FR] §2.5 writes $\rho$ for $c_1$ (and for Goldstein's $c$) and $\sigma$ for $c_2$, and calls Wolfe's pair the Wolfe–Powell conditions. Nocedal–Wright [NW] uses $c_1,c_2$ as here.

Proof. (1) The Armijo line $\ell(\alpha)=\phi(0)+c_1\alpha\phi'(0)$ decreases without bound, while $\phi$ is bounded below. Near $0$, $\phi\lt\ell$ (small steps pass Armijo). So the graph of $\phi$ must cross $\ell$; let $\alpha'\gt0$ be the first crossing, $\phi(\alpha')=\phi(0)+c_1\alpha'\phi'(0)$. Every $\alpha\in(0,\alpha')$ satisfies Armijo strictly.
(2) By the mean value theorem there is $\alpha''\in(0,\alpha')$ with $\phi(\alpha')-\phi(0)=\alpha'\phi'(\alpha'')$. Comparing with (1): $\phi'(\alpha'')=c_1\phi'(0)$.
(3) Since $c_1\lt c_2$ and $\phi'(0)\lt0$: $\phi'(\alpha'')=c_1\phi'(0)\gt c_2\phi'(0)$, so curvature holds strictly at $\alpha''$. Also $\phi'(\alpha'')\lt0$, so $|\phi'(\alpha'')|=c_1|\phi'(0)|\lt c_2|\phi'(0)|$: strong Wolfe holds too. All the inequalities are strict and $\phi,\phi'$ are continuous, so they still hold on a small interval around $\alpha''$. $\blacksquare$

Notice where $c_1\lt c_2$ was used: in step (3). With $c_2\le c_1$, the slope $c_1\phi'(0)$ found by the mean value theorem would not be good enough, and on some functions no step satisfies both conditions.

Back to the trap

For $f(x)=x^2$ with $\d_k=-2x_k$: $\phi(\alpha)=x_k^2(1-2\alpha)^2$ and $\phi'(\alpha)=-4x_k^2(1-2\alpha)$. Armijo reduces to $\alpha\le1-c_1$, so every short step $\alpha_k=2^{-(k+2)}$ passes, and the long steps $1-2^{-(k+2)}$ pass until $2^{-(k+2)}\lt c_1$. Curvature reduces to $1-2\alpha\le c_2$, i.e. $\alpha\ge(1-c_2)/2$. With $c_2=0.9$ that is $\alpha\ge0.05$: $\alpha_0,\alpha_1,\alpha_2$ pass but $\alpha_3=\frac1{32}=0.03125$ fails, and so does every later short step. The Wolfe line search would refuse them and look for a larger step. Strong Wolfe gives $0.05\le\alpha\le0.95$ and also rejects the long steps from $\alpha_3=\frac{31}{32}$ on.

Why it terminates

Only two facts are needed: small steps pass Armijo (Chapter 6.3, using $c_1\lt1$ and $\phi'(0)\lt0$), and the trials $\beta^j\bar\alpha$ go to $0$. So some trial is small enough, and the loop stops after finitely many trials. This works for any $f\in C^1$.

But termination alone does not stop the "too short" failure: what if the accepted step is absurdly small? For $L$-smooth $f$ the descent lemma rules that out, with an explicit bound. The idea: the step just before the accepted one was rejected, and a rejection tells you that $f$ curves up a lot, which the descent lemma says can only happen for steps of size at least about $1/L$.

From the lower bound to convergence

Write $\omega=c_1\min\{\bar\alpha,2\beta(1-c_1)/L\}\gt0$. If $f$ is bounded below by $f^\star$, add the decrease bound over $k=0,\dots,N-1$; the left side telescopes: $$\omega\sum_{k=0}^{N-1}\norm{\g_k}^2\le f(\x_0)-f(\x_N)\le f(\x_0)-f^\star.$$ The right side doesn't depend on $N$, so the series $\sum\norm{\g_k}^2$ converges and $\norm{\g_k}\to0$. Backtracking gradient descent is globally convergent to stationary points, without any curvature condition. This resolves the summable-step trap: an externally imposed schedule $2^{-(k+2)}$ can shrink forever, but backtracking restarts from $\bar\alpha$ every iteration and only shrinks while Armijo actually fails. Part 7 extends this kind of argument to Wolfe steps and general directions (Zoutendijk).

A practical by-product: any $\alpha\le2(1-c_1)G/(L\norm{\d_k}^2)$ passes Armijo (that is what step 4 shows in reverse), so the number of trials is at most the number of halvings needed to get below that value, plus one.

An iterative method produces $\x_0,\x_1,\x_2,\dots$. To talk about speed we pick an error measure $e_k\ge0$ that is zero exactly at the answer. Three are used in this part:

• the optimality gap $f(\x_k)-f^\star$, where $f^\star=\inf f$;
• the distance $\norm{\x_k-\x^\star}$ to a minimizer $\x^\star$;
• the gradient norm $\norm{\grad f(\x_k)}$ (zero exactly at stationary points).

"The method converges" means $e_k\to0$. The rate describes how $e_k$ shrinks.

Why "linear"? Take logarithms of $e_k=\rho^ke_0$: $\log e_k=\log e_0+k\log\rho$, a straight line in $k$. On a plot with a logarithmic error axis (a semi-log plot), linear convergence is a straight line going down; sublinear convergence is a curve that keeps flattening; quadratic convergence is a curve that bends down ever more steeply (the number of correct digits roughly doubles each step).

How many iterations for accuracy $\varepsilon$?

This is the question exams (and practitioners) actually ask. Solve $e_k\le\varepsilon$ for $k$:

For gradient descent the linear rate is usually $\rho=\frac{\kappa-1}{\kappa+1}$ (Part 5, and Chapter 7.4 below). Since $\ln\frac1\rho=\ln\frac{\kappa+1}{\kappa-1}\approx\frac2\kappa$ for large $\kappa$, the iteration count is roughly $$k\approx\frac\kappa2\ln\frac{e_0}{\varepsilon}.$$ So the condition number multiplies the work: $\kappa=1000$ means about 500 steps per factor $e$ of improvement.

What "global" does and does not mean

A method is globally convergent if $\norm{\grad f(\x_k)}\to0$ from every starting point $\x_0$. "Global" refers to the starting point, not to the answer: the limit is a stationary point, which may be a saddle or (rarely) a maximum. Without convexity nothing better can be promised.

The angle between $\d_k$ and $-\grad f$

A line-search method moves $\x_{k+1}=\x_k+\alpha_k\d_k$ along a descent direction $\d_k$, meaning $\g_k^\top\d_k\lt0$ where $\g_k=\grad f(\x_k)$. How "downhill" it is, is measured by the angle $\theta_k$ between $\d_k$ and the steepest-descent direction $-\g_k$:

Which directions satisfy the angle condition?

• Steepest descent $\d_k=-\g_k$: $\cos\theta_k=1$.
• Newton-like directions $\d_k=-B_k^{-1}\g_k$ with $B_k\succ0$ ([NW] §3.2, p.45). With eigenvalues $\lambda_{\min}\le\lambda_{\max}$ of $B_k$: $-\g_k^\top\d_k=\g_k^\top B_k^{-1}\g_k\ge\norm{\g_k}^2/\lambda_{\max}$ and $\norm{\d_k}\le\norm{\g_k}/\lambda_{\min}$, so $$\cos\theta_k\ge\frac{\lambda_{\min}}{\lambda_{\max}}=\frac1{\kappa(B_k)}.$$ If the condition numbers $\kappa(B_k)$ stay bounded by $M$, then $\cos\theta_k\ge1/M$ and the method is globally convergent. Quasi-Newton methods (Part 10) are analysed this way.

What goes wrong when $\cos\theta_k\to0$? The guaranteed decrease $c\cos^2\theta_k\norm{\g_k}^2$ shrinks to nothing even while the gradient is large. If $\sum_k\cos^2\theta_k\lt\infty$, the total progress can be finite and the method can stall at a point that isn't stationary.

Constant step sizes ([Y] §1.2.3)

Nesterov studies the plainest scheme: gradient descent $\x_{k+1}=\x_k-h_k\grad f(\x_k)$ with step $h_k$. In the Nesterov-based chapters the step is called $h$ (Part 5 called it $\alpha$). He compares three rules: a constant step $h_k=h$; full relaxation (exact line search) $h_k=\argmin_{h\ge0}f(\x_k-h\grad f(\x_k))$; and the Goldstein–Armijo rule, which with $\x_k-\x_{k+1}=h_k\g_k$ asks for $$a\,h_k\norm{\g_k}^2\le f(\x_k)-f(\x_{k+1})\le b\,h_k\norm{\g_k}^2,\qquad0\lt a\lt b\lt1$$ ([Y] writes $\alpha,\beta$ for $a,b$).

Assume $f\in C_L^{1,1}$ (gradient $L$-Lipschitz; no convexity) and bounded below by $f^\star$. The Descent Lemma (Part 6) with $\y=\x_k-h\g_k$ gives [Y] (1.2.12): $$f(\x_{k+1})\le f(\x_k)-h\norm{\g_k}^2+\tfrac{h^2L}2\norm{\g_k}^2=f(\x_k)-h\Big(1-\tfrac h2L\Big)\norm{\g_k}^2.$$

Setting: $f\in\mathcal F_L^{1,1}(\R^n)$ (convex, differentiable, $\grad f$ $L$-Lipschitz; Part 4), with a minimizer $\x^\star$ (assumed to exist), $f^\star=f(\x^\star)$. Method: $\x_{k+1}=\x_k-h\grad f(\x_k)$ with constant $0\lt h\lt2/L$. Notation: $r_k=\norm{\x_k-\x^\star}$ and $\Delta_k=f(\x_k)-f^\star$.

The idea in one line

Convexity gives $f^\star\ge f(\x_k)+\g_k^\top(\x^\star-\x_k)$, i.e. $\Delta_k\le\g_k^\top(\x_k-\x^\star)\le\norm{\g_k}\,r_k$. So a large gap forces a large gradient, and (Descent Lemma) a large gradient forces a large decrease. This gives a self-improving recursion $$\Delta_{k+1}\le\Delta_k-c\,\Delta_k^2,$$ and any such recursion decays like $1/(ck)$. Try it with $c=1$, $\Delta_0=0.5$: $0.5,\ 0.25,\ 0.1875,\ 0.1523,\ 0.1291,\ 0.1125,\dots$ (compare $1/(k+2)$: $0.5,0.333,0.25,0.2,0.167,0.143$).

One more ingredient is needed: $r_k$ must not grow. That comes from a sharper inequality than convexity.

Proof. Fix $\x$ and let $\varphi(\z)=f(\z)-\grad f(\x)^\top\z$. It is convex and $L$-smooth (we only subtracted a linear function), and $\grad\varphi(\x)=\0$, so $\x$ is a global minimizer of $\varphi$ (convex + zero gradient, Part 4). Apply the Descent Lemma to $\varphi$ at the point $\y$ with the step $\z=\y-\frac1L\grad\varphi(\y)$: $$\varphi(\x)\le\varphi(\z)\le\varphi(\y)-\tfrac1L\norm{\grad\varphi(\y)}^2+\tfrac L2\cdot\tfrac1{L^2}\norm{\grad\varphi(\y)}^2=\varphi(\y)-\tfrac1{2L}\norm{\grad\varphi(\y)}^2.$$ Since $\grad\varphi(\y)=\grad f(\y)-\grad f(\x)$ and $\varphi(\y)-\varphi(\x)=f(\y)-f(\x)-\grad f(\x)^\top(\y-\x)$, this is ($\star$). Write ($\star$) again with $\x$ and $\y$ swapped and add the two: the function values cancel and co-coercivity remains. $\square$

Compared with plain convexity, ($\star$) has the extra term $\frac1{2L}\norm{\grad f(\y)-\grad f(\x)}^2$: convexity and smoothness working together.

Recall (Part 4): $f\in\mathcal S_{\mu,L}^{1,1}$ if $f\in\mathcal F_L^{1,1}$ and $f$ is $\mu$-strongly convex, $f(\y)\ge f(\x)+\grad f(\x)^\top(\y-\x)+\frac\mu2\norm{\y-\x}^2$; for $C^2$ functions, $\mu I\preceq\hess f(\x)\preceq LI$. Such $f$ has exactly one minimizer $\x^\star$. Nesterov writes $Q_f=L/\mu\ge1$ for the condition number; it plays the role of $\kappa$ from Part 5 (for a quadratic, $Q_f=\kappa$).

Closing the loop with Part 5

On a quadratic $f(\x)=\tfrac12\x^\top A\x-\b^\top\x$ with eigenvalues in $[m,L]$, Part 5 found that constant step $\alpha$ gives $\x_{k+1}-\x^\star=(I-\alpha A)(\x_k-\x^\star)$, worst-case factor $\max_i|1-\alpha\lambda_i|$, minimized at $\alpha=\frac2{m+L}$ with value $\frac{\kappa-1}{\kappa+1}$. Theorem 2.1.15 gives the same step and the same factor for every $f\in\mathcal S_{\mu,L}^{1,1}$, quadratic or not. And the exact-line-search rate $\big(\frac{\kappa-1}{\kappa+1}\big)^2$ per step in function value (Kantorovich, Part 5) matches the $\big(\frac{Q_f-1}{Q_f+1}\big)^{2k}$ in the $f$-bound here.

The problem for this whole part

Throughout, $A$ is a symmetric positive definite $n\times n$ matrix ($A=A^\top\succ0$, Part 0b) and $$f(\x)=\tfrac12\x^\top A\x-\b^\top\x,\qquad \g(\x)=\grad f(\x)=A\x-\b.$$ Because $A\succ0$, $f$ is strictly convex with the unique minimizer $\x^\star=A^{-1}\b$ (the point where $\g=\0$). So minimizing $f$ and solving the linear system $A\x=\b$ are the same problem. We write $\x_k$ for the iterates and $\g_k=\g(\x_k)=A\x_k-\b$.

Why something better than gradient descent?

Recall from Part 5: gradient descent with exact line search on this $f$ makes consecutive gradients orthogonal ($\g_{k+1}^\top\g_k=0$), so on a stretched bowl it zig-zags, and the error shrinks only by a factor tied to $\kappa=L/m$ each step. Even on a $2\times2$ problem it generally never lands exactly on $\x^\star$.

Here is a hint of what could work. If $A$ were diagonal, $f$ would be a sum of separate one-variable parabolas, $f=\sum_i(\tfrac12a_{ii}x_i^2-b_ix_i)$. Minimizing exactly along $x_1$, then $x_2$, …, then $x_n$ would finish in $n$ steps, because fixing $x_2$ can't spoil the choice of $x_1$. The contours are ellipses whose axes line up with the coordinate axes. For a general $A$ the ellipses are tilted, and line searches along the coordinate axes interfere. The fix: find $n$ directions that behave, for this $A$, the way the coordinate axes behave for a diagonal matrix.

With $A=I$, conjugate just means orthogonal. For any other $A$ the two ideas differ. For $A=\begin{pmatrix}4&1\\1&3\end{pmatrix}$, the vectors $\d_0=(1,0)^\top$ and $\d_1=(-\tfrac14,1)^\top$ are conjugate: $A\d_1=(-1+1,\,-\tfrac14+3)^\top=(0,\tfrac{11}4)^\top$, so $\d_0^\top A\d_1=0$. But $\d_0^\top\d_1=-\tfrac14\ne0$: they are not perpendicular.

The picture: stretch the ellipses into circles

Write $A=V\Lambda V^\top$ (spectral theorem) and let $A^{1/2}=V\Lambda^{1/2}V^\top$, the symmetric positive definite matrix with $A^{1/2}A^{1/2}=A$. Change variables to $\y=A^{1/2}\x$. Then $$\u^\top A\v=(A^{1/2}\u)^\top(A^{1/2}\v),\qquad \x^\top A\x=\norm{\y}^2.$$ So the level sets $\x^\top A\x=c$ (ellipses) become circles $\norm{\y}^2=c$, and $\u,\v$ are $A$-conjugate exactly when their stretched images $A^{1/2}\u$, $A^{1/2}\v$ are perpendicular. Conjugacy is ordinary orthogonality, seen through the lens that makes the bowl round.

A second picture you can draw by hand: take the ellipse $\x^\top A\x=c$ through the tip of $\d_0$. The gradient of $\x^\top A\x$ at that tip is $2A\d_0$, which is perpendicular to the tangent. So the tangent direction $\v$ satisfies $\v^\top A\d_0=0$: the direction conjugate to $\d_0$ is parallel to the tangent of the ellipse where $\d_0$ meets it. In $\R^2$ that pins it down up to scaling; in $\R^n$ the vectors conjugate to $\d_0$ form an $(n-1)$-dimensional subspace, $\{\v:\v^\top(A\d_0)=0\}$.

Proof (examinable). Suppose $\sum_{i=0}^{m-1}c_i\d_i=\0$. Multiply on the left by $\d_j^\top A$. Every term with $i\ne j$ vanishes by conjugacy, leaving $c_j\,\d_j^\top A\d_j=0$. Since $\d_j\ne\0$ and $A\succ0$, $\d_j^\top A\d_j\gt0$, so $c_j=0$. This holds for every $j$, so the only combination giving $\0$ is the trivial one. $\blacksquare$

The proof is the "multiply by $\d_j^\top A$ to kill every term but one" trick. You'll use it again three times in this part.

Expanding $\x^\star$ in a conjugate basis

Let $\d_0,\dots,\d_{n-1}$ be $A$-conjugate. By the lemma they form a basis of $\R^n$, so $\x^\star=\sum_ia_i\d_i$ for some numbers $a_i$. Multiply by $\d_j^\top A$: $$\d_j^\top A\x^\star=a_j\,\d_j^\top A\d_j\quad\Longrightarrow\quad a_j=\frac{\d_j^\top A\x^\star}{\d_j^\top A\d_j}=\frac{\d_j^\top\b}{\d_j^\top A\d_j},$$ using $A\x^\star=\b$. The last expression needs only $\b$, not the unknown $\x^\star$. That is the whole point of $A$-orthogonality. With an ordinary orthogonal basis the coefficient would be $\d_j^\top\x^\star/\norm{\d_j}^2$, which needs $\x^\star$, the thing we're trying to find. ([LD] §9.1 p.264.)

Where do conjugate directions come from?

• Eigenvectors. The orthonormal eigenvectors $\v_1,\dots,\v_n$ of $A$ satisfy $\v_i^\top A\v_j=\lambda_j\v_i^\top\v_j=0$ for $i\ne j$: both orthogonal and conjugate. But computing them is harder than solving $A\x=\b$.
• Gram–Schmidt in the $A$-inner product. From any basis $\u_0,\dots,\u_{n-1}$: $\d_0=\u_0$ and $$\d_k=\u_k-\sum_{i\lt k}\frac{\u_k^\top A\d_i}{\d_i^\top A\d_i}\,\d_i .$$ Each correction removes the $A$-component along one old direction. This works, but it stores all old directions and costs $O(n^3)$ for dense $A$. The conjugate gradient method of Chapter 8.3 is a way to do it almost for free.

Proof (examinable). Expanding, $\phi(\alpha)=f(\x_k)+\alpha\,\g_k^\top\d_k+\tfrac{\alpha^2}2\d_k^\top A\d_k$, a parabola in $\alpha$ with positive leading coefficient. $\phi'(\alpha)=\g_k^\top\d_k+\alpha\,\d_k^\top A\d_k=0$ gives $\alpha_k$. Next, $\g_{k+1}=A(\x_k+\alpha_k\d_k)-\b=\g_k+\alpha_kA\d_k$. Finally, by the chain rule $\phi'(\alpha_k)=\g_{k+1}^\top\d_k$, and this is 0 at the minimizer. $\blacksquare$

In words: after an exact line search, the new gradient is perpendicular to the direction you just searched. (You met this in Part 5 for $\d_k=-\g_k$.) Note that $\alpha_k$ may be negative: the method walks along the line, in whichever sense goes down.

Why it works: coordinate descent in disguise

Put the directions in the columns of $S=[\d_0|\cdots|\d_{n-1}]$ and write $\x=S\hat\x$. Then $f(S\hat\x)=\tfrac12\hat\x^\top(S^\top AS)\hat\x-(S^\top\b)^\top\hat\x$, and $S^\top AS=\mathrm{diag}(\d_0^\top A\d_0,\dots,\d_{n-1}^\top A\d_{n-1})$ by conjugacy. In the $\hat\x$ coordinates the function is a sum of $n$ separate parabolas, and step $k$ minimizes exactly along the $k$-th coordinate axis. That's the diagonal case from Chapter 8.1: no later move can disturb an earlier one. When $A$ is already diagonal, the coordinate axes themselves are conjugate.

What is true at every intermediate step

Let $\mathcal B_k=\operatorname{span}\{\d_0,\dots,\d_{k-1}\}$ (with $\mathcal B_0=\{\0\}$). These subspaces grow by one dimension per step, $\mathcal B_1\subset\mathcal B_2\subset\cdots\subset\mathcal B_n=\R^n$, and $\x_k$ lies in the affine set $\x_0+\mathcal B_k$ ("$\x_0$ plus anything in $\mathcal B_k$"; [LD] calls it a linear variety).

Proof of (ii). Write points of $\x_0+\mathcal B_k$ as $\x_0+D_k\y$ with $D_k=[\d_0|\cdots|\d_{k-1}]$ and $\y\in\R^k$, and let $h(\y)=f(\x_0+D_k\y)$. This is a quadratic in $\y$ with Hessian $D_k^\top AD_k=\mathrm{diag}(\d_i^\top A\d_i)\succ0$, so it is strictly convex. By the chain rule $\grad h(\y)=D_k^\top\grad f(\x_0+D_k\y)$. The iterate $\x_k=\x_0+\sum_{i\lt k}\alpha_i\d_i$ corresponds to $\y=(\alpha_0,\dots,\alpha_{k-1})$, where $\grad h=D_k^\top\g_k=\0$ by part (i). A stationary point of a convex function is a global minimizer (Part 4), and strict convexity makes it unique. The line through $\x_{k-1}$ along $\d_{k-1}$ lies inside $\x_0+\mathcal B_k$ and contains $\x_k$, so $\x_k$ minimizes over that line too. $\blacksquare$

Taking $k=n$: $\x_n$ minimizes $f$ over $\x_0+\R^n=\R^n$, so $\x_n=\x^\star$. That's a second proof of the Conjugate Direction Theorem.

Another reading: the closest point in the $A$-norm

Using $A\x^\star=\b$, a short expansion gives $f(\x)-f(\x^\star)=\tfrac12\norm{\x-\x^\star}_A^2$. So minimizing $f$ is the same as minimizing the $A$-norm distance to the solution, and the theorem says: $\x_k$ is the point of $\x_0+\mathcal B_k$ closest to $\x^\star$ in the $A$-norm. Since $\g_k=A(\x_k-\x^\star)$, part (i) reads $\ip{\x_k-\x^\star}{\d_i}_A=0$: the error is $A$-orthogonal to the explored subspace, just like "the best approximation from a subspace is the orthogonal projection". Part 9 builds its convergence analysis on this view.

Deriving the algorithm

Chapter 8.2 assumed someone handed us conjugate directions. CG chooses $\d_0=-\g_0$ (a steepest descent step) and then $$\d_k=-\g_k+\beta_k\d_{k-1},\qquad\beta_k\text{ chosen so that }\d_k^\top A\d_{k-1}=0.$$ Substituting: $0=-\g_k^\top A\d_{k-1}+\beta_k\,\d_{k-1}^\top A\d_{k-1}$, so $$\beta_k=\frac{\g_k^\top A\d_{k-1}}{\d_{k-1}^\top A\d_{k-1}}.$$ The step size is the exact line search from Chapter 8.2. The term $\beta_k\d_{k-1}$ is a memory of the previous heading, the very thing gradient descent lacks.

We only forced $\d_{k+1}$ to be conjugate to $\d_k$. Why would it be conjugate to $\d_{k-1},\d_{k-2},\dots$? That is the content of the CG Theorem, and its proof uses one more idea.

Krylov subspaces: what CG can "see"

After one step you've moved along $\g_0$, and the new gradient $\g_1=\g_0+\alpha_0A\d_0$ involves $A\g_0$. After two steps, the new gradient involves $A^2\g_0$. Each step applies $A$ once more.

Read it before proving it. (c) is the surprise: one condition imposed, all conditions obtained. (d) gives a second view of termination: there's room for at most $n$ nonzero orthogonal vectors in $\R^n$, so some $\g_k$ with $k\le n$ must be $\0$. Compare gradient descent, which only guarantees $\g_{k+1}\perp\g_k$. (e) makes $\alpha_k\gt0$ and gives cheaper formulas.

Proof (examinable). For $\alpha_k$: $-\g_k^\top\d_k=\norm{\g_k}^2$ by (e). For $\beta_{k+1}$: from $\g_{k+1}=\g_k+\alpha_kA\d_k$, $A\d_k=(\g_{k+1}-\g_k)/\alpha_k$. The numerator of the preliminary $\beta_{k+1}$ is $\g_{k+1}^\top A\d_k=(\norm{\g_{k+1}}^2-\g_{k+1}^\top\g_k)/\alpha_k=\norm{\g_{k+1}}^2/\alpha_k$ by (d). The denominator is $\d_k^\top A\d_k=\norm{\g_k}^2/\alpha_k$ by the new $\alpha_k$ formula. Divide; $\alpha_k$ cancels. $\blacksquare$

If an exam asks you to derive CG, start from the preliminary $\beta$ and the line-search $\alpha$, then simplify using (d) and (e). The cheap formulas are consequences of the theorem, not definitions.

CG needs $A$ only as a function $\v\mapsto A\v$. If $A$ is sparse with a handful of nonzeros per row, each iteration costs $O(n)$, which is why CG can handle systems with millions of unknowns that a direct method couldn't even store.

Why only one $\beta$? Symmetry

Gram–Schmidt must correct a new vector against every old direction. In CG all corrections except the last vanish (Step 5), because $\g_{k+1}^\top A\d_i=(A\g_{k+1})^\top\d_i$ needs $A=A^\top$ to move $A$ across, and because the Krylov structure keeps $A\d_i$ inside the explored space. For non-symmetric $A$ there is no such short recurrence, and Krylov methods for those systems (such as GMRES) must store all old directions.

A teaser for Part 9. Finite termination is an exact-arithmetic statement, and for $n$ in the millions you never run $n$ steps anyway. CG is used as an iterative method that is often accurate after far fewer than $n$ steps. How few depends on the eigenvalues of $A$, and Part 9 makes this precise.

Recall the setting from Part 8. We minimize $f(\x)=\tfrac12\x^\top A\x-\b^\top\x$ with $A$ symmetric positive definite ($A\succ0$), so the minimizer is $\x^\star=A^{-1}\b$ and the gradient is $\g_k=\grad f(\x_k)=A\x_k-\b$. Part 8 gave us three facts about CG:

• CG Theorem: the directions span a Krylov subspace, $\operatorname{span}\{\d_0,\dots,\d_k\}=\mathcal K_k(\g_0):=\operatorname{span}\{\g_0,A\g_0,\dots,A^k\g_0\}$.
• Expanding Subspace Theorem: $\x_{k+1}$ minimizes $f$ over the whole set $\x_0+\operatorname{span}\{\d_0,\dots,\d_k\}$, not just along the last direction.
• Error identity: $f(\x)-f(\x^\star)=\tfrac12(\x-\x^\star)^\top A(\x-\x^\star)$. So minimizing $f$ is the same as minimizing the distance to $\x^\star$ measured in the $A$-norm below.

Finite termination in $n$ steps follows. The question this part answers is the practical one: how small is the error after $k\ll n$ steps?

Plugging a matrix into a polynomial

For a polynomial $P(t)=\gamma_0+\gamma_1t+\dots+\gamma_kt^k$, define $P(A)=\gamma_0I+\gamma_1A+\dots+\gamma_kA^k$. If $A\v=\lambda\v$, then $A^2\v=A(\lambda\v)=\lambda^2\v$, and in general $A^j\v=\lambda^j\v$. Adding up:

Example: $A=\begin{pmatrix}1&0\\0&4\end{pmatrix}$ and $P(t)=1-\tfrac t2$ give $P(A)=I-\tfrac12A=\begin{pmatrix}1/2&0\\0&-1\end{pmatrix}$: the diagonal entries are $P(1)$ and $P(4)$.

Step 1: CG's iterates are "$\x_0$ + a polynomial in $A$ times $\g_0$"

Since $\x_{k+1}=\x_0+\alpha_0\d_0+\dots+\alpha_k\d_k$ and the $\d_i$ span $\mathcal K_k(\g_0)$, there are numbers $\gamma_0,\dots,\gamma_k$ with $$\x_{k+1}=\x_0+\gamma_0\g_0+\gamma_1A\g_0+\dots+\gamma_kA^k\g_0=\x_0+P_k(A)\,\g_0,\qquad P_k\in\mathcal P_k .$$ This is [NW] (5.25) and [LD] §9.4 (24).

Step 2: the error is $Q(A)\e_0$ with $Q(0)=1$

Because $\b=A\x^\star$, the first gradient is $\g_0=A\x_0-A\x^\star=A\e_0$. Subtract $\x^\star$ from Step 1: $$\e_{k+1}=\e_0+P_k(A)A\e_0=\big[I+AP_k(A)\big]\e_0=Q_{k+1}(A)\,\e_0,\qquad Q_{k+1}(t):=1+t\,P_k(t).$$ $Q_{k+1}$ has degree at most $k+1$ and $Q_{k+1}(0)=1$. Conversely, any $Q$ of degree $\le k+1$ with $Q(0)=1$ arises this way: $Q(t)-1$ vanishes at $t=0$, so $P(t)=(Q(t)-1)/t$ is a polynomial of degree $\le k$.

Proof. The set $\{\x_0+P(A)\g_0:P\in\mathcal P_k\}$ is exactly $\x_0+\mathcal K_k(\g_0)=\x_0+\operatorname{span}\{\d_0,\dots,\d_k\}$. By the Expanding Subspace Theorem, $\x_{k+1}$ minimizes $f$ over this set, hence minimizes $f-f^\star=\tfrac12\norm{\cdot-\x^\star}_A^2$. That is the first equality. The second follows from $\x_0+P(A)\g_0-\x^\star=[I+AP(A)]\e_0=Q(A)\e_0$ and the correspondence $P\leftrightarrow Q$. $\blacksquare$

Step 3: eigenvalues turn the matrix problem into a scalar one

Expand the starting error in the eigenbasis, $\e_0=\sum_i\xi_i\v_i$. By the lemma, $Q(A)\e_0=\sum_iQ(\lambda_i)\xi_i\v_i$. For any coefficients $c_i$, $$\Big\lVert\sum_ic_i\v_i\Big\rVert_A^2=\sum_{i,j}c_ic_j\,\v_i^\top A\v_j=\sum_i\lambda_ic_i^2,$$ because $\v_i^\top A\v_j=\lambda_j\v_i^\top\v_j$ is $0$ for $i\ne j$ and $\lambda_i$ for $i=j$. Therefore $$\norm{Q(A)\e_0}_A^2=\sum_{i=1}^n\lambda_i\,Q(\lambda_i)^2\,\xi_i^2,\qquad \norm{\e_0}_A^2=\sum_{i=1}^n\lambda_i\,\xi_i^2 .$$ Read it like this: the error component along $\v_i$ gets multiplied by the number $Q(\lambda_i)$.

[NW] writes the same polynomial as $Q_r(\lambda)=\frac{(-1)^r}{\tau_1\cdots\tau_r}(\lambda-\tau_1)\cdots(\lambda-\tau_r)$; expanding the product shows they agree.

Clusters: Luenberger's bound

Exactly repeated eigenvalues are rare. Tight clusters are common, and a root placed inside a tight cluster makes $Q$ tiny on the whole cluster. The following estimate makes this precise.

How to read it:

• $k=0$: the bound is $\frac{\lambda_n-\lambda_1}{\lambda_n+\lambda_1}=\frac{\kappa-1}{\kappa+1}$, the one-step steepest descent rate from Part 5. That makes sense: CG's first step is steepest descent with exact line search.
• Each further step removes the largest remaining eigenvalue from the effective condition number. The polynomial behind it spends $k$ roots on the $k$ largest eigenvalues and one root at the midpoint of what is left.
• $m$ outliers plus a cluster. If $m$ eigenvalues are large and the other $n-m$ lie in $[1-\epsilon,1+\epsilon]$, take $k=m$: $\lambda_{n-m}\le1+\epsilon$ and $\lambda_1\ge1-\epsilon$, so after $m+1$ steps $\norm{\e_{m+1}}_A\le\frac{2\epsilon}{2}\norm{\e_0}_A=\epsilon\norm{\e_0}_A$. CG spends $m$ steps on the outliers and one on the whole cluster.

[NW] Fig. 5.4 shows exactly this with five large eigenvalues and the rest in $[0.95,1.05]$: a sharp drop around iteration 6, and another at iteration 7, because the matrix "almost" has six distinct eigenvalues. In general, $r$ tight clusters mean CG approximately solves the problem in about $r$ steps ([NW] p.116): a polynomial with one root per cluster is not zero at the eigenvalues, but tiny.

CG beats every gradient method

Proof. From the story in Chapter 9.1, $\y_{k+1}-\x^\star=Q(A)\e_0$ with $Q(t)=\prod_{j=0}^k(1-h_jt)\in\mathcal Q_{k+1}$. CG's error is the minimum of $\norm{Q(A)\e_0}_A$ over all of $\mathcal Q_{k+1}$, so $\norm{\e_{k+1}}_A\le\norm{\y_{k+1}-\x^\star}_A$, and $f-f^\star=\tfrac12\norm{\cdot}_A^2$. $\blacksquare$

(Step sizes chosen by a line search depend on the iterates, but once the run is over they are just numbers $h_j$, and the identity above holds.) [LD] makes a related point: each CG step is at least as good as one steepest descent step taken from the same point $\x_k$.

Recovering the Part 5 rate. On the whole interval $[m,L]$, the degree-1 polynomial $Q(t)=1-\frac{2t}{m+L}$ has maximum $\frac{L-m}{L+m}=\frac{\kappa-1}{\kappa+1}$, attained at both ends. Using $Q(t)^k$ in the min–max bound shows CG is never slower than $\big(\frac{\kappa-1}{\kappa+1}\big)^k$. That is the polynomial of gradient descent with constant step $h=\frac2{m+L}$: all $k$ roots stacked at the midpoint. Chapter 9.3 spreads them out.

Suppose we only know $m=\lambda_1$ and $L=\lambda_n$. Every eigenvalue lies in $[m,L]$, so making $Q$ small on the whole interval is enough: $$\max_i|Q(\lambda_i)|\le\max_{t\in[m,L]}|Q(t)|.$$ Gradient descent's best constant-step polynomial $(1-\frac{2t}{m+L})^k$ gives $\big(\frac{\kappa-1}{\kappa+1}\big)^k$ (Chapter 9.2). Can another degree-$k$ polynomial with $Q(0)=1$ be smaller on $[m,L]$? Yes, and the answer is classical.

Where it comes from. The map $z(t)=\frac{L+m-2t}{L-m}$ sends $[m,L]$ onto $[-1,1]$ (reversed) and sends $t=0$ to $z_0=\frac{\kappa+1}{\kappa-1}>1$. Take $$Q(t)=\frac{T_k(z(t))}{T_k(z_0)} .$$ It has degree $k$, and $Q(0)=1$ because we divided by $T_k(z_0)$. On $[m,L]$, $|T_k(z(t))|\le1$, so $|Q|\le1/T_k(z_0)$. Since $z_0>1$ and $T_k$ grows fast outside $[-1,1]$, $T_k(z_0)$ is large and $Q$ is small on the whole interval. A short calculation (below) gives $1/T_k(z_0)\le2q^k$ with $q=\frac{\sqrt\kappa-1}{\sqrt\kappa+1}$. The min–max bound finishes the proof. (If $\kappa=1$, then $A=mI$ and CG finishes in one step.)

What $\sqrt\kappa$ means for iteration counts

To guarantee $\norm{\e_k}_A\le\varepsilon\norm{\e_0}_A$:

• Steepest descent (rate $\frac{\kappa-1}{\kappa+1}$, Part 5): need $k\ge\dfrac{\ln(1/\varepsilon)}{\ln\frac{\kappa+1}{\kappa-1}}\approx\dfrac\kappa2\ln\dfrac1\varepsilon$.
• CG: need $2q^k\le\varepsilon$, i.e. $k\ge\dfrac{\ln(2/\varepsilon)}{\ln\frac{\sqrt\kappa+1}{\sqrt\kappa-1}}\approx\dfrac{\sqrt\kappa}2\ln\dfrac2\varepsilon$.

The approximations use $\ln\frac{x+1}{x-1}=\ln(1+\frac1x)-\ln(1-\frac1x)\approx\frac2x$ for large $x$. So the iteration count is $O(\kappa\log\frac1\varepsilon)$ for steepest descent and $O(\sqrt\kappa\log\frac1\varepsilon)$ for CG.

Where it comes from: solving an equation with tangent lines

Forget minimization for a moment. You want a number $t^\star$ with $\phi(t^\star)=0$, for some smooth function $\phi:\R\to\R$. You are at a guess $t_k$. Close to $t_k$, the graph of $\phi$ looks like its tangent line: $$\phi(t_k+\Delta t)\approx\phi(t_k)+\phi'(t_k)\,\Delta t.$$ Pretend this approximation is exact and solve $\phi(t_k)+\phi'(t_k)\Delta t=0$ for the move $\Delta t$. That gives Newton's iteration for a root: $$t_{k+1}=t_k-\frac{\phi(t_k)}{\phi'(t_k)}\qquad(\phi'(t_k)\ne0).$$ Geometrically: draw the tangent at $(t_k,\phi(t_k))$ and walk down it to where it crosses the axis.

Example: $\phi(t)=t^2-2$ (root $\sqrt2$) from $t_0=1$ gives $t_1=1.5$, $t_2=1.416667$, $t_3=1.4142157$, $t_4=1.414213562375$. The errors are $0.41,\ 0.086,\ 0.0025,\ 2.1\times10^{-6},\ 1.6\times10^{-12}$: once close, each step roughly doubles the number of correct digits. Chapter 2 makes this precise.

From roots to minima

A minimizer of a smooth $f$ must satisfy the first-order condition $\grad f(\x)=\0$ (Part 3). So minimizing is "finding a root of the gradient". In one variable, apply the tangent-line rule to $\phi=f'$, whose derivative is $f''$: $$x_{k+1}=x_k-\frac{f'(x_k)}{f''(x_k)}.$$ In $n$ variables the gradient is a map $\R^n\to\R^n$, and its "derivative" (its Jacobian matrix) is the Hessian $\hess f$. Linearizing $\grad f(\x_k+\d)\approx\grad f(\x_k)+\hess f(\x_k)\d$ and setting this to $\0$ gives the multivariable rule.

The second derivation: minimize the quadratic model

Taylor's theorem (Part 0b) says that near $\x_k$, $f(\x_k+\d)\approx q_k(\d)$, where $\g_k=\grad f(\x_k)$ and $$q_k(\d):=f(\x_k)+\g_k^\top\d+\tfrac12\d^\top\hess f(\x_k)\,\d .$$ This quadratic model $q_k$ is a bowl when $\hess f(\x_k)\succ0$. Its gradient is $\grad q_k(\d)=\grad f(\x_k)+\hess f(\x_k)\d$, which vanishes exactly at the Newton direction. So Newton jumps to the bottom of the local quadratic model ([FR] (3.1.1)). Gradient descent, by contrast, uses the model $f(\x_k)+\grad f(\x_k)^\top\d+\frac1{2\alpha}\norm{\d}^2$, which pretends the curvature is the same, $1/\alpha$, in every direction.

Why Newton doesn't care about $\kappa$: affine invariance

Change variables $\x=S\y$ with an invertible matrix $S$, and let $g(\y)=f(S\y)$. The chain rule gives $\grad g(\y)=S^\top\grad f(\x)$ and $\hess g(\y)=S^\top\hess f(\x)S$. So the Newton step in $\y$ is $$-\big(S^\top\hess f\,S\big)^{-1}S^\top\grad f=-S^{-1}[\hess f]^{-1}\grad f,$$ which is exactly the Newton step in $\x$, mapped back by $S^{-1}$. Stretching or rotating the coordinates changes nothing: the iterates correspond one-to-one. Gradient descent is not like this, because $\grad g=S^\top\grad f$ points somewhere else; that is why its speed depends on $\kappa$ (Part 5) and Newton's doesn't. Newton is steepest descent measured in the Hessian's own metric, the metric that turns the elliptical level sets into circles.

Is the Newton direction downhill?

A direction $\d$ is a descent direction when $\grad f(\x_k)^\top\d\lt0$. For the Newton direction, $$\grad f(\x_k)^\top\d_k=-\grad f(\x_k)^\top[\hess f(\x_k)]^{-1}\grad f(\x_k).$$ If $\hess f(\x_k)\succ0$ then its inverse is also positive definite (eigenvalues $1/\lambda_i>0$), so this is negative whenever $\grad f(\x_k)\ne\0$: descent. If the Hessian is indefinite, the Newton direction may point uphill or towards a saddle point; Part 3 showed Newton walking into a saddle. Newton is a root-finder for $\grad f=\0$, and maxima and saddles are roots too.

Measuring speed: rates of convergence

Let $\x_k\to\x^\star$ and write $r_k=\norm{\x_k-\x^\star}$ for the error.

Nesterov's example: Newton can diverge on a convex function

The lesson: Newton's method is a local method. Its guarantees need the start to be close enough to $\x^\star$. Far out, $\sqrt{1+t^2}$ is nearly linear ($f''$ is tiny), so the quadratic model is a very flat parabola whose bottom lies far beyond the true minimizer.

The local convergence theorem

Nesterov works under three assumptions ([Y] p.34):

1. (N1) $f\in C^{2,2}_M(\R^n)$: $f$ is twice differentiable and its Hessian is Lipschitz with constant $M$: $\norm{\hess f(\x)-\hess f(\y)}\le M\norm{\x-\y}$ for all $\x,\y$, where $\norm{\cdot}$ on matrices is the operator norm (largest stretch factor; for symmetric matrices, the largest $|\lambda|$). $M$ measures how far $f$ is from quadratic; $M=0$ for a quadratic.
2. (N2) There is a local minimizer $\x^\star$ with $\hess f(\x^\star)\succeq\ell I$ for some $\ell\gt0$ ([Y] (1.2.22)): the bowl is genuinely curved in every direction at the bottom. ($\ell$ plays the role that $\mu$ played for strong convexity in Part 7, but only at $\x^\star$.)
3. (N3) The start $\x_0$ is close enough to $\x^\star$.

[Y] (p.36) notes that this ball has almost the same size as the region where gradient descent is guaranteed to converge linearly ($\bar r=2\ell/M$). Hence the standard plan: use a globally safe method to get close, then let Newton finish.

Making Newton practical

• Damped Newton ([Y] p.34): $\x_{k+1}=\x_k-h_k[\hess f(\x_k)]^{-1}\grad f(\x_k)$, with the step $h_k$ chosen by a line search (Armijo backtracking, Lecture 7) early on and $h_k=1$ near the solution. Whenever $\hess f\succ0$ the direction is downhill, so the line search always finds an acceptable step.
• Hessian modification ([FR] pp.47–49): if $\hess f(\x_k)$ is not positive definite, replace it by a positive definite matrix, e.g. $\hess f(\x_k)+\nu I$ with $\nu\gt0$ large enough (Levenberg–Marquardt style), or a modified $LDL^\top$ factorization. As $\nu\to\infty$ the step turns into a short gradient-descent step.
• Cost: each step needs the $\tfrac12n(n+1)$ second derivatives and an $n\times n$ solve (about $\frac16n^3$ multiplications). For $n=10^6$ that is out of the question. This is what quasi-Newton methods (Chapter 3) remove.
• Degenerate minimizers: if $\hess f(\x^\star)$ is singular, (N2) fails and the rate can drop to linear. For $f(x)=x^4$: $x_{k+1}=x_k-\frac{4x_k^3}{12x_k^2}=\tfrac23x_k$.

The idea

Every step gives free curvature information. In [FR] notation, with $\g_k=\grad f(\x_k)$, define the step and the gradient change ([FR] (3.2.2)–(3.2.3)): $$\boldsymbol\delta_k=\x_{k+1}-\x_k,\qquad\boldsymbol\gamma_k=\g_{k+1}-\g_k .$$ By Taylor's theorem for the gradient, $\boldsymbol\gamma_k=G\boldsymbol\delta_k+o(\norm{\boldsymbol\delta_k})$, where $G$ is the Hessian ([FR] (3.2.4)). For a quadratic with Hessian $G$ this is exact: $\boldsymbol\gamma_k=G\boldsymbol\delta_k$ ([FR] (3.2.8)). So the true inverse Hessian maps $\boldsymbol\gamma_k$ to $\boldsymbol\delta_k$. In one dimension, $\gamma/\delta$ is just a finite-difference estimate of $f''$: this is the old secant method.

The quasi-Newton (secant) condition

We cannot ask $H_k$ to satisfy $H_k\boldsymbol\gamma_k=\boldsymbol\delta_k$: the step was taken with $H_k$ before $\boldsymbol\gamma_k$ was known. So we demand it of the next matrix.

Rank one: SR1

Try the simplest symmetric correction, a rank-one matrix: $H_{k+1}=H+a\u\u^\top$ (dropping the index $k$ on the right, as [FR] does, (3.2.6)). The secant condition requires $$H\boldsymbol\gamma+a\,\u(\u^\top\boldsymbol\gamma)=\boldsymbol\delta,\ \text{ i.e. }$$ $$a(\u^\top\boldsymbol\gamma)\,\u=\boldsymbol\delta-H\boldsymbol\gamma .$$ So $\u$ must be parallel to $\boldsymbol\delta-H\boldsymbol\gamma$. Take $\u=\boldsymbol\delta-H\boldsymbol\gamma$; then $a\,\u^\top\boldsymbol\gamma=1$, which gives the symmetric rank-one formula ([FR] (3.2.7)): $$H_{k+1}^{\rm SR1}=H+\frac{(\boldsymbol\delta-H\boldsymbol\gamma)(\boldsymbol\delta-H\boldsymbol\gamma)^\top}{(\boldsymbol\delta-H\boldsymbol\gamma)^\top\boldsymbol\gamma}.$$

The proof never used exact line searches. But SR1 has two flaws ([FR] p.53): $H_{k+1}$ need not stay positive definite (so $\d_k$ may stop being downhill), and the denominator $(\boldsymbol\delta-H\boldsymbol\gamma)^\top\boldsymbol\gamma$ can be zero or tiny. Practical codes skip the update in that case.

Rank two: DFP

Allow two terms, $H_{k+1}=H+a\u\u^\top+b\v\v^\top$. The secant condition becomes $H\boldsymbol\gamma+a\u(\u^\top\boldsymbol\gamma)+b\v(\v^\top\boldsymbol\gamma)=\boldsymbol\delta$. The natural choice ([FR] (3.2.10)) is one term that produces $\boldsymbol\delta$ and one that cancels $H\boldsymbol\gamma$: $\u=\boldsymbol\delta$, $\v=H\boldsymbol\gamma$, with $a=1/\boldsymbol\delta^\top\boldsymbol\gamma$ and $b=-1/\boldsymbol\gamma^\top H\boldsymbol\gamma$: $$H_{k+1}^{\rm DFP}=H+\frac{\boldsymbol\delta\boldsymbol\delta^\top}{\boldsymbol\delta^\top\boldsymbol\gamma}-\frac{H\boldsymbol\gamma\boldsymbol\gamma^\top H}{\boldsymbol\gamma^\top H\boldsymbol\gamma}$$ ([FR] (3.2.11); Davidon 1959, Fletcher and Powell 1963). Secant check: $H_{k+1}\boldsymbol\gamma=H\boldsymbol\gamma+\boldsymbol\delta\frac{\boldsymbol\delta^\top\boldsymbol\gamma}{\boldsymbol\delta^\top\boldsymbol\gamma}-H\boldsymbol\gamma\frac{\boldsymbol\gamma^\top H\boldsymbol\gamma}{\boldsymbol\gamma^\top H\boldsymbol\gamma}=\boldsymbol\delta$. Read it as: add the new information along $\boldsymbol\delta$, remove what $H$ used to say along $\boldsymbol\gamma$.

BFGS, and duality

Secant check (write $\rho=\boldsymbol\delta^\top\boldsymbol\gamma$, a scalar): $H_{k+1}\boldsymbol\gamma=H\boldsymbol\gamma+\big(1+\frac{\boldsymbol\gamma^\top H\boldsymbol\gamma}{\rho}\big)\boldsymbol\delta-\frac{\boldsymbol\delta(\boldsymbol\gamma^\top H\boldsymbol\gamma)+H\boldsymbol\gamma\,\rho}{\rho}=\boldsymbol\delta$. In $B$-form it's even quicker: $B_{k+1}\boldsymbol\delta=B\boldsymbol\delta+\boldsymbol\gamma-B\boldsymbol\delta=\boldsymbol\gamma$.

Duality. The $B$-form of BFGS is the DFP formula with $H\leftrightarrow B$ and $\boldsymbol\delta\leftrightarrow\boldsymbol\gamma$ swapped ([FR] p.55: the two are dual or complementary; (3.2.14) is the dual $B$-form of DFP). Because Theorem 3.2.2's proof only needs a positive definite matrix and $\boldsymbol\gamma^\top\boldsymbol\delta\gt0$, it applies to $B_{k+1}^{\rm BFGS}$ too, so $H^{\rm BFGS}_{k+1}=(B^{\rm BFGS}_{k+1})^{-1}\succ0$ whenever $\boldsymbol\delta^\top\boldsymbol\gamma\gt0$.

Properties of DFP and BFGS ([FR] p.54, proved in [FR] §3.3–3.4). On a quadratic with exact line searches: (i) termination in at most $n$ iterations with $H_{n+1}=G^{-1}$; (ii) the hereditary property; (iii) the directions are $G$-conjugate, and with $H_1=I$ the iterates are exactly those of conjugate gradients (Parts 8–9). On general functions: (iv) $H_k\succ0$; (v) about $3n^2$ multiplications per iteration; (vi) superlinear local convergence; (vii) global convergence on strictly convex functions with exact line searches. BFGS is the more robust of the two with inexact line searches and is the standard choice.

How the methods are related

• CG = steepest descent + memory: $\d_k=-\g_k+\beta_k\d_{k-1}$.
• Newton = steepest descent in the Hessian's metric: it rescales space so the level sets become circles, which is why $\kappa$ disappears.
• Quasi-Newton = Newton with a learned metric: $H_k$ is assembled from the pairs $(\boldsymbol\delta_k,\boldsymbol\gamma_k)$.
• Quasi-Newton = CG on quadratics: with $H_1=I$ and exact line searches, DFP and BFGS produce exactly the CG iterates (Lab 14 confirms agreement to about $10^{-16}$ for $n=8$) and also end with $H_{n+1}=G^{-1}$.
• Quadratic results become local results: near $\x^\star$ every smooth $f$ is close to its quadratic model with $A=\hess f(\x^\star)$, so the quadratic analysis predicts the final phase of every method.

Existence and optimality (Lectures 2–5)

Convexity (Interlude)

Gradient methods and line search (Lectures 6–10)

Conjugate gradients, Newton, quasi-Newton (Lectures 11–14)