Every unconstrained-optimization method, and which one to pick
Gradient descent, Newton, quasi-Newton, conjugate gradient, derivative-free search, and stochastic/population methods — one decision chain spanning three chapters.
Start with the cheapest question: is a gradient available and cheap to compute exactly, for one fixed deterministic objective? If so, reach for gradient descent (plain or with momentum) on a well-conditioned bowl, or a second-order method (Newton, a quasi-Newton method, or conjugate gradient) once curvature is affordable. If the gradient genuinely isn't available, drop to a derivative-free method — coordinate descent when the objective is separable, pattern search when evaluations are noisy, Nelder-Mead when the dimension is small. If the objective is secretly an average over a huge dataset, move to stochastic gradient descent or an adaptive method like Adam instead of a full gradient every step. If the landscape is multimodal, discrete, or a black box, a population method (simulated annealing, a genetic algorithm, or particle swarm) searches where a single-point gradient method would gamble on one starting basin. No method wins every case — that's the No Free Lunch Theorem, not a gap in this course's coverage.
Gradient-based descent (Chapter 3)
The plain update rule — step opposite the gradient, scaled by a learning rate.
Term
line search
How far to actually step once a descent direction is chosen.
Carries a fraction of the previous step forward, damping the zig-zag in narrow valleys.
Second-order and quasi-Newton (Chapter 4)
Uses the Hessian to jump straight to a quadratic model's own minimum.
Approximates the Hessian from gradient changes instead of computing it directly (DFP, BFGS, L-BFGS).
Let g:\mathbb{R}\to\mathbb{R} be twice continuously differentiable near a root x^* (that is, g(x^*)=0) with g'(x^*)\ne 0, and suppose g'' is Lipschitz continuous with constant M on an interval around x^*. Let e_n = x_n - x^* denote the error of the n-th Newton iterate x_{n+1}=x_n-\dfrac{g(x_n)}{g'(x_n)}. Then, for x_0 close enough to x^*, there is a constant C>0 with |e_{n+1}| \le C\, |e_n|^2 for every n — the error roughly squares at each step, which is what "quadratic convergence" means. (Applied to unconstrained optimization, g=\nabla f is the gradient of the objective and x^* a stationary point with nonsingular Hessian H(x^*)=g'(x^*).)
Sanity check: take g(x)=x^2-2 (so x^*=\sqrt2\approx1.41421356), with Newton update x_{n+1}=x_n-\frac{x_n^2-2}{2x_n}. Starting from x_0=1.5: e_0 = 0.08579. One step gives x_1 = 1.5 - \frac{0.25}{3} = 1.41\overline{6}, so e_1\approx 0.002453. The ratio |e_1|/|e_0|^2 \approx 0.002453/0.007360 \approx 0.333, a modest constant — and squaring again, one more step gives x_2\approx1.4142157 with e_2\approx 2.1\times10^{-6}, and indeed |e_2|/|e_1|^2\approx 2.1\times10^{-6}/6.0\times10^{-6}\approx0.35, the same order of constant. The number of correct digits is visibly doubling each step (2, then 5, then 10+), exactly the signature of quadratic convergence.
Why Newton's method's error roughly squares each step, once it's close enough.
Show proof
Write e_n = x_n - x^*. By the definition of Newton's update and using g(x^*) = 0, e_{n+1} = x_{n+1}-x^* = x_n - x^* - \frac{g(x_n)}{g'(x_n)} = e_n - \frac{g(x_n) - g(x^*)}{g'(x_n)} = \frac{g'(x_n)e_n - \big(g(x_n)-g(x^*)\big)}{g'(x_n)}.
Now expand g(x^*) as a second-order Taylor series of g around x_n (valid since g is twice differentiable, with the Lagrange remainder form using the Lipschitz bound on g''): g(x^*) = g(x_n) + g'(x_n)(x^*-x_n) + \tfrac12 g''(\xi_n)(x^*-x_n)^2 for some \xi_n between x_n and x^*. Since g(x^*)=0 and x^*-x_n=-e_n, rearranging gives g(x_n) - g'(x_n)e_n = -\tfrac12 g''(\xi_n) e_n^2, i.e. g'(x_n)e_n - g(x_n) = \tfrac12 g''(\xi_n)e_n^2. Substituting into the expression for e_{n+1} above: e_{n+1} = \frac{\tfrac12 g''(\xi_n)\, e_n^2}{g'(x_n)}.
Because g' is continuous and g'(x^*)\ne 0, there is a neighborhood of x^* on which |g'(x)| \ge \tfrac12|g'(x^*)|>0; and because g'' is Lipschitz (hence continuous), it is bounded by some constant \bar M near x^*. Choosing x_0 (hence every subsequent x_n, by induction, provided they stay in this neighborhood) close enough to x^* that both bounds apply, we get |e_{n+1}| = \frac{|g''(\xi_n)|}{2|g'(x_n)|}\,|e_n|^2 \le \underbrace{\frac{\bar M}{|g'(x^*)|}}_{=:C} |e_n|^2. This is the claimed bound. (A standard companion argument, omitted here, confirms that if x_0 is close enough that C|e_0|<1, the sequence |e_n| in fact shrinks to 0, so the iterates stay in the neighborhood where the bound applies at every step — quadratic convergence is a local, not global, guarantee.)
Section
Conjugate gradient descent
Derivative-free search (Chapter 4)
Reshapes a simplex of trial points by reflecting, expanding, and contracting toward better values.
Stochastic and population methods (Chapter 11)
Estimates the gradient from one example or a mini-batch instead of the full dataset.
Adagrad, RMSProp, and Adam — per-parameter step sizes that adapt as training runs.
One evolving candidate, accepting occasional worse moves early on to escape a bad basin.
A population of candidates, combined and mutated across generations.
A population that keeps momentum, pulled toward its own best-known point and the swarm's best.
The decision chains
Averaged over all possible objective functions on a finite search space, every optimization algorithm that never re-evaluates a point achieves the same average performance — measured, say, as the sequence of best-value-found-so-far after k evaluations. No algorithm is better than any other "in general"; an algorithm can only be better for a class of problems with structure (smoothness, convexity, separability, and so on) that the algorithm is built to exploit.
This card states the result at the vocabulary level this course needs and sketches why it's true, rather than proving it. The full proof (Wolpert and Macready, 1997) is a counting argument over permutations of function values that is genuinely graduate-level measure-theoretic bookkeeping, and it is out of scope here — see a dedicated optimization theory text if you want the complete argument.
Sanity check: with |X|=2 points \{a,b\} and |Y|=2 values \{0,1\}, there are 2^2=4 possible objectives: (f(a),f(b)) \in \{(0,0),(0,1),(1,0),(1,1)\}. An algorithm that always checks a first finds the best-of-the-two-points value \max(f(a),f(b)) after one step exactly when f(a)=1: that happens for 2 of the 4 objectives, i.e. average success rate 1/2 after one evaluation. An algorithm that always checks b first finds it after one step exactly when f(b)=1 — also 2 of the 4 objectives, average 1/2. The two "opposite" strategies tie exactly, which is the pattern the full theorem generalizes: averaged over every possible objective, no fixed traversal order beats any other.
Averaged over every possible problem, no algorithm beats every other one — this is why the chain above asks questions instead of naming a winner.
Show proof
This is an informal justification sketch, not a full proof — see the statement above for why a complete proof is out of scope for this course.
Fix a finite search space X and a finite set of possible objective values Y. An objective function is any assignment f:X\to Y; there are |Y|^{|X|} of them, and "averaged over all objective functions" means averaged uniformly over this entire set, including every wildly discontinuous, non-smooth, adversarially scrambled assignment along with every well-behaved one.
An optimization algorithm that doesn't re-visit points, after k steps, has produced a sequence of (point, value) pairs. The key observation is this: because the average is taken over literally every possible assignment f:X\to Y, for any fixed sequence of points the algorithm might choose to visit, the sequence of values f assigns to them is equally likely to be any of the |Y|^k possible value-sequences — the average washes out any information the algorithm's choice of which points to visit could have used, because nothing about f correlates the value at one unvisited point with the value at another once f ranges uniformly over every possibility. A clever traversal order, a gradient- following heuristic, a random walk — none of these can systematically land on better values sooner than any other fixed traversal, precisely because "systematically better" would require the objective functions being averaged over to share some structure the strategy exploits, and by construction the average includes every structure-breaking permutation of f's values with equal weight.
Consequently, the average (over all f) of any performance statistic that depends only on the values an algorithm has seen (like "best value found after k steps") is the same for every non-repeating algorithm. This is the sense in which "no algorithm is better than any other, averaged over all problems" — real problems are never drawn uniformly from this set (a real objective has continuity, smoothness, or other exploitable structure), which is exactly why algorithm choice still matters in practice: an algorithm wins by assuming the structure a specific problem actually has.