Optimization for Machine Learning

Optimization means choosing values for some unknowns, the decision variables $\mathbf{x}$, so that a number called the objective function $f(\mathbf{x})$ is as small (or as large) as possible, while obeying any constraints. For a "make it small" problem we write

$$\min_{\mathbf{x}} \; f(\mathbf{x}).$$

Read it as: "find the $\mathbf{x}$ that makes $f(\mathbf{x})$ smallest". The rest of this chapter names each part of that sentence.

An objective function is a function

$$f : \mathbb{R}^n \to \mathbb{R}, \qquad \mathbf{x} \mapsto f(\mathbf{x}),$$

which takes the decision variables $\mathbf{x} = (x_1, \dots, x_n)$ and returns a single real number. We either minimise it or maximise it.

• It must output one number. If you care about two things at once (speed and cost), you must combine them into one score, for example $0.25 \cdot \text{minutes} + \text{toll}$ as in the routes above.
• Which function you choose defines the problem. Change $f$ and the best answer changes.

The decision variables are the unknowns we choose, collected into a vector

$$\mathbf{x} = \begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} \in \mathbb{R}^n .$$

The number $n$ is the dimension of the problem. Choosing $\mathbf{x}$ means choosing a point in $\mathbb{R}^n$; the objective $f(\mathbf{x})$ is the height of the landscape over that point. (Vectors are explained in the Linear Algebra guide.)

Vocabulary warning. In optimization textbooks "parameters" are the problem constants. In machine learning, "the model's parameters" almost always means the weights, which are the decision variables. In this guide we say "decision variables" (or "weights") for the numbers being optimised, "data" or "problem parameters" for the fixed inputs, and "hyperparameters" for the knobs of the method.

Notation, stated once for the whole guide. We always move everything to one side so that a constraint compares a function with zero:

• An inequality constraint is written $g_i(\mathbf{x}) \le 0$, for $i = 1, \dots, m$. The letter $g$ means "inequality".
• An equality constraint is written $h_j(\mathbf{x}) = 0$, for $j = 1, \dots, p$. The letter $h$ means "equality".

Converting is just moving terms: $x + y \le 4$ becomes $g_1(x,y) = x + y - 4 \le 0$. A "$\ge$" rule is flipped by multiplying by $-1$: $x \ge 0$ becomes $g_2(x,y) = -x \le 0$. And $xy = 100$ becomes $h_1(x,y) = xy - 100 = 0$.

A constraint is active at a point if it holds with equality there ($g_i = 0$, the point sits on the edge of the rule) and inactive if it holds with room to spare ($g_i \lt 0$). Equality constraints are always active. (We study active constraints properly in Chapter 3.7.)

The feasible region (or feasible set) is the set of all points that obey every constraint:

$$\mathcal{F} = \{\, \mathbf{x} \in \mathbb{R}^n \;:\; g_i(\mathbf{x}) \le 0 \text{ for all } i, \;\; h_j(\mathbf{x}) = 0 \text{ for all } j \,\}.$$

• A point $\mathbf{x} \in \mathcal{F}$ is a feasible solution (or feasible point). A point outside is infeasible.
• No constraints at all means $\mathcal{F} = \mathbb{R}^n$: an unconstrained problem (Chapter 3.2).
• If the rules contradict each other (for example $x \ge 2$ and $x \le 1$), $\mathcal{F}$ is empty and the problem is infeasible: it has no solution at all.
• $\mathcal{F}$ can be bounded (the triangle) or unbounded (just $x \ge 0$: a whole half-line).

A point $\mathbf{x}^\star \in \mathcal{F}$ is an optimal solution of the problem $\min_{\mathbf{x} \in \mathcal{F}} f(\mathbf{x})$ if

$$f(\mathbf{x}^\star) \le f(\mathbf{x}) \quad \text{for every feasible } \mathbf{x}.$$

Then $f^\star = f(\mathbf{x}^\star)$ is the optimal value, written $\min_{\mathbf{x}} f(\mathbf{x})$. The set of all winners is written $\arg\min_{\mathbf{x}} f(\mathbf{x})$ ("the argument that gives the minimum"). The two answers are different objects: $\min$ returns a number $f^\star$; $\arg\min$ returns an input $\mathbf{x}^\star$.

• An optimum may be non-unique (a flat-bottomed valley has a whole interval of winners; then $\arg\min$ is a set).
• An optimum may not exist: the objective may keep improving forever, or approach a value it never reaches. In that case we speak of the infimum (the greatest lower bound).
• It is guaranteed to exist if $f$ is continuous and $\mathcal{F}$ is non-empty, closed and bounded (the extreme value theorem). Closed means the edge belongs to $\mathcal{F}$; bounded means $\mathcal{F}$ does not stretch out to infinity.

For any objective $f$ and feasible set $\mathcal{F}$:

$$\max_{\mathbf{x}\in\mathcal{F}} f(\mathbf{x}) = -\min_{\mathbf{x}\in\mathcal{F}} \bigl(-f(\mathbf{x})\bigr), \qquad \arg\max_{\mathbf{x}} f(\mathbf{x}) = \arg\min_{\mathbf{x}} \bigl(-f(\mathbf{x})\bigr).$$

• The maximiser is the same point; only the value changes sign.
• More generally, the best point does not change if you add a constant to $f$, multiply it by a positive number, or apply any strictly increasing function (such as $\log$): $\arg\min f = \arg\min (a f + c)$ for $a \gt 0$, and $\arg\max L = \arg\max \log L$ when $L \gt 0$.
• Maximum (global): $f(\mathbf{x}^\star) \ge f(\mathbf{x})$ for all feasible $\mathbf{x}$. Minimum (global): $f(\mathbf{x}^\star) \le f(\mathbf{x})$ for all feasible $\mathbf{x}$. Local versions come in the next section.

Let $\mathcal{F}$ be the feasible set. A point $\mathbf{x}^\star \in \mathcal{F}$ is

• a local minimum if there is some radius $\varepsilon \gt 0$ such that $f(\mathbf{x}^\star) \le f(\mathbf{x})$ for every feasible $\mathbf{x}$ with $\|\mathbf{x} - \mathbf{x}^\star\| \lt \varepsilon$;
• a strict local minimum if the inequality is strict ($\lt$) for every such $\mathbf{x} \ne \mathbf{x}^\star$;
• a global minimum if $f(\mathbf{x}^\star) \le f(\mathbf{x})$ for all $\mathbf{x} \in \mathcal{F}$.

Local and global maxima are defined the same way with $\ge$. Global $\Rightarrow$ local, never the other way round. A problem may have several global minima (all with the same value), as in the Himmelblau landscape below.

The big good news (Chapter 3.6). For a special family called convex problems, every local minimum is global. Linear and logistic regression are convex; deep neural networks are not.

A saddle point is a point where the slope is zero ($\nabla f = \mathbf{0}$) but which is neither a local minimum nor a local maximum: in some directions $f$ goes up, in others it goes down.

In one variable there is no real saddle, but $f(x) = x^3$ at $x = 0$ is a cousin: the slope is zero there, and yet the function keeps falling on the left and rising on the right. Chapter 3.2 gives the exact test using the Hessian (if the Hessian has both positive and negative eigenvalues at a zero-slope point, that point is a saddle); Chapter 3.15 explains why saddles matter in deep learning.

The general form (also called the standard form) of a constrained optimization problem is

$$\begin{aligned} \min_{\mathbf{x} \in \mathbb{R}^n} \quad & f(\mathbf{x}) \\ \text{subject to} \quad & g_i(\mathbf{x}) \le 0, \quad i = 1, \dots, m, \\ & h_j(\mathbf{x}) = 0, \quad j = 1, \dots, p. \end{aligned}$$

"Subject to" is often abbreviated s.t. Remember the convention from the Constraints section: $g_i$ are the inequality constraints, $h_j$ are the equality constraints. We keep this notation in every later chapter.

• If $m = p = 0$ there are no rules: an unconstrained problem, $\min_{\mathbf{x}} f(\mathbf{x})$ (Chapter 3.2).
• Rewriting rules: $\max f \to \min(-f)$; "$g \ge 0$" $\to$ "$-g \le 0$"; "$a \le b$" $\to$ "$a - b \le 0$".
• Problems get names from the shape of $f$, $g_i$, $h_j$: all linear $\Rightarrow$ linear program; quadratic $f$ with linear rules $\Rightarrow$ quadratic program; convex pieces $\Rightarrow$ convex problem (Chapter 3.6).

The recipe used here (substitute out an equality, then use calculus on what remains):

1. Write the objective and the constraints.
2. Solve the equality for one variable and substitute it into the objective.
3. Set the derivative of the result to 0, and check the second derivative.
4. Check the boundaries and compare with other candidates; then rebuild the other variables.

Substitution works when the equality is easy to solve. For harder constraints we need Lagrange multipliers (Chapter 3.8). The derivative test is explained fully in Chapter 3.2; derivatives themselves in the Calculus guide.

Three facts to remember.

• Adding constraints can never improve the optimal value of a minimisation problem: $f^\star_{\text{constrained}} \ge f^\star_{\text{unconstrained}}$ (a smaller allowed set has a worse-or-equal best).
• If the unconstrained optimum is feasible, the constraint is inactive and the answer is unchanged.
• If it is not feasible, the constrained optimum usually lies on the boundary: an active constraint, $g_i(\mathbf{x}^\star) = 0$. Chapters 3.7 to 3.9 make this precise.

Almost every supervised-learning problem is empirical risk minimisation: given $N$ training examples $(\mathbf{x}_i, y_i)$ and a model $\hat y = m(\mathbf{x}; \boldsymbol{\theta})$ with weights $\boldsymbol{\theta}$,

$$\min_{\boldsymbol{\theta}} \;\; \frac{1}{N}\sum_{i=1}^{N} \ell\bigl(m(\mathbf{x}_i; \boldsymbol{\theta}),\, y_i\bigr) \;\;(+\; \text{optional penalty or constraint on } \boldsymbol{\theta}),$$

where $\ell$ is a per-example loss (squared error, cross-entropy…). The dictionary from optimization words to ML words:

Recipe for a smooth function of one variable.

1. First-order step. Solve $f'(x) = 0$. The solutions are the critical points (candidates).
2. Second-order step. At each candidate $\hat x$ look at $f''(\hat x)$:   $f''(\hat x) \gt 0 \Rightarrow$ local minimum;   $f''(\hat x) \lt 0 \Rightarrow$ local maximum;   $f''(\hat x) = 0 \Rightarrow$ the test is inconclusive (see the later section on semidefinite cases).
3. Global step. To find the global optimum on an interval $[a, b]$, compare $f$ at every critical point and at the endpoints $a$ and $b$. On all of $\mathbb{R}$, also check what $f$ does as $x \to \pm\infty$.

The alternative to step 2 is the first-derivative test: if $f'$ changes from negative to positive at $\hat x$, it is a minimum; from positive to negative, a maximum; no change of sign, neither. (Derivatives are explained in the Calculus guide.)

A multivariable unconstrained optimization problem is

$$\min_{\mathbf{x} \in \mathbb{R}^n} f(\mathbf{x}), \qquad f: \mathbb{R}^n \to \mathbb{R}.$$

A point $\mathbf{x}^\star$ is a local minimum if $f(\mathbf{x}^\star) \le f(\mathbf{x})$ for all $\mathbf{x}$ in some small ball around it, that is, in every direction at once (Chapter 3.1). The two one-variable tools generalise as follows:

For $f: \mathbb{R}^n \to \mathbb{R}$, the gradient is the column vector of partial derivatives:

$$\nabla f(\mathbf{x}) = \begin{bmatrix} \partial f / \partial x_1 \\ \vdots \\ \partial f / \partial x_n \end{bmatrix}.$$

• $\nabla f$ points in the direction of steepest ascent; $-\nabla f$ in the direction of steepest descent. Its length $\|\nabla f\|$ is the steepness.
• The slope in any unit direction $\mathbf{u}$ is the dot product $\nabla f(\mathbf{x})^\top \mathbf{u}$ (the directional derivative).
• $\nabla f$ is perpendicular to the contour line through $\mathbf{x}$.

All of this is derived in the Calculus guide (the gradient) and steepest ascent and descent.

$\hat{\mathbf{x}}$ is a critical point of a differentiable $f$ if

$$\nabla f(\hat{\mathbf{x}}) = \mathbf{0}, \qquad\text{that is,}\qquad \frac{\partial f}{\partial x_1}(\hat{\mathbf{x}}) = 0, \;\dots,\; \frac{\partial f}{\partial x_n}(\hat{\mathbf{x}}) = 0.$$

This is a system of $n$ equations in $n$ unknowns. Critical points can be minima, maxima, saddle points, or flat plateaus. Every unconstrained local minimum or maximum of a differentiable function is a critical point (the next section proves it).

First-order necessary condition. If $\mathbf{x}^\star$ is a local minimum (or local maximum) of a differentiable function $f$ and $\mathbf{x}^\star$ lies in the interior of the allowed set (here: there are no constraints), then

$$\nabla f(\mathbf{x}^\star) = \mathbf{0}.$$

• Necessary: every unconstrained local optimum satisfies it.
• Not sufficient: a point with $\nabla f = \mathbf{0}$ may be a minimum, a maximum, a saddle or a plateau. We need second-order information to decide.
• Only for unconstrained problems. If the optimum sits on the edge of the allowed set, its gradient need not be zero (see the last preset in the widget). Handling that case is the job of Chapters 3.7 to 3.9.

The Hessian of $f: \mathbb{R}^n \to \mathbb{R}$ at $\mathbf{x}$ is the symmetric $n \times n$ matrix of second partial derivatives:

$$\nabla^2 f(\mathbf{x}) = \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \cdots & \dfrac{\partial^2 f}{\partial x_1 \partial x_n} \\ \vdots & \ddots & \vdots \\ \dfrac{\partial^2 f}{\partial x_n \partial x_1} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix}, \qquad H_{ij} = \frac{\partial^2 f}{\partial x_i\, \partial x_j}.$$

• Symmetric ($H_{ij} = H_{ji}$) when the second derivatives are continuous.
• Curvature along a direction. Along a unit vector $\mathbf{u}$, the slice $\phi(t) = f(\mathbf{x} + t\mathbf{u})$ has $\phi'(0) = \nabla f^\top\mathbf{u}$ and $\phi''(0) = \mathbf{u}^\top H \mathbf{u}$.
• Eigenvalues. $\mathbf{u}^\top H \mathbf{u}$ always lies between the smallest and the largest eigenvalue of $H$; the extremes are reached along the eigenvectors (the principal directions of curvature).
• The second-order Taylor picture. Near $\mathbf{x}$, for a small step $\mathbf{d}$: $$f(\mathbf{x} + \mathbf{d}) \approx f(\mathbf{x}) + \nabla f(\mathbf{x})^\top \mathbf{d} + \tfrac12\, \mathbf{d}^\top H(\mathbf{x})\, \mathbf{d}.$$

See the Hessian in the Calculus guide, and for eigenvalues the Linear Algebra guide.

Let $\nabla f(\hat{\mathbf{x}}) = \mathbf{0}$ and let $H = \nabla^2 f(\hat{\mathbf{x}})$.

Why it works. At a critical point the gradient term vanishes, so for small $\mathbf{d}$, by Taylor's theorem, $f(\hat{\mathbf{x}} + \mathbf{d}) = f(\hat{\mathbf{x}}) + \tfrac12 \mathbf{d}^\top H\mathbf{d} + (\text{smaller terms})$. If $H$ is positive definite, then $\mathbf{d}^\top H \mathbf{d} \ge \lambda_{\min}\|\mathbf{d}\|^2$ with $\lambda_{\min} \gt 0$, which beats the smaller terms: $f$ goes up in every direction. If $H$ has an eigenvector $\mathbf{v}$ with eigenvalue $\lambda \lt 0$, then $f(\hat{\mathbf{x}} + t\mathbf{v}) \approx f(\hat{\mathbf{x}}) + \tfrac12 \lambda t^2$ goes down.

Necessary versus sufficient. (Notation: $H \succ 0$ means "$H$ is positive definite", all eigenvalues $\gt 0$; $H \succeq 0$ means "positive semidefinite", all eigenvalues $\ge 0$; $\prec$ and $\preceq$ are the same for negative.) Sufficient: $\nabla f = \mathbf{0}$ and $H \succ 0$ $\Rightarrow$ strict local minimum. Necessary: a local minimum must have $\nabla f = \mathbf{0}$ and $H$ positive semidefinite (no negative eigenvalue). The gap between "$\succ 0$" and "$\succeq 0$" is exactly the inconclusive case.

Definiteness is explained in the Linear Algebra guide; practical tests (eigenvalues, Cholesky, leading minors) are in tests for definiteness; the Calculus guide has the second-derivative test.

For a smooth $f$ and a critical point $\hat{\mathbf{x}}$:

• Local minimum: $f(\hat{\mathbf{x}}) \le f(\mathbf{x})$ for all nearby $\mathbf{x}$. Detected by $H \succ 0$ (strict), sometimes by $H \succeq 0$ plus extra checks.
• Local maximum: $f(\hat{\mathbf{x}}) \ge f(\mathbf{x})$ for all nearby $\mathbf{x}$. Detected by $H \prec 0$.
• Saddle point: $\nabla f = \mathbf{0}$, but $f$ goes up in some directions and down in others. Detected by $H$ indefinite.

From local to global. To get a global minimum you need more: (i) if $f \to \infty$ in every direction far away (e.g. $x^4 + y^4$), then a global minimum exists and it is the lowest of the local minima; (ii) if $f$ is convex (Chapter 3.6), every local minimum is global.

At a critical point $\hat{\mathbf{x}}$, the second-order test is inconclusive when the Hessian is positive semidefinite but not positive definite (or negative semidefinite but not negative definite): all eigenvalues have the same sign or are zero, and at least one is zero.

• If $H$ has both a positive and a negative eigenvalue, the point is a saddle regardless of any zero eigenvalues.
• In one variable, $f'(\hat{x}) = 0$ and $f''(\hat{x}) = 0$ is inconclusive; use the sign pattern of $f'$, or the first non-zero higher derivative: if it is of even order, positive means minimum and negative means maximum; if odd, it is neither.
• Never call a point a minimum just because "$H \succeq 0$": that is only necessary.

Let $A$ be a symmetric $n \times n$ matrix and $f(\mathbf{x}) = \tfrac12 \mathbf{x}^\top A \mathbf{x} - \mathbf{b}^\top \mathbf{x}$. Then

$$\nabla f(\mathbf{x}) = A\mathbf{x} - \mathbf{b}, \qquad \nabla^2 f(\mathbf{x}) = A \quad(\text{the same everywhere}).$$

(The gradient rule for $\tfrac12\mathbf{x}^\top A\mathbf{x}$ is derived in the Calculus guide.) Critical points solve the linear system $A\mathbf{x} = \mathbf{b}$.

• $A$ positive definite (all eigenvalues $\gt 0$; see here): there is exactly one critical point $\mathbf{x}^\star = A^{-1}\mathbf{b}$, and it is the unique global minimum, with $f^\star = -\tfrac12 \mathbf{b}^\top A^{-1}\mathbf{b}$.
• $A$ singular (some eigenvalue $0$) and positive semidefinite: either $A\mathbf{x} = \mathbf{b}$ has no solution (then $f$ falls to $-\infty$: no minimum), or it has infinitely many (a flat valley of equally good minimisers).
• $A$ with a negative eigenvalue: no minimum ($f$ falls to $-\infty$ along that eigenvector). A non-singular indefinite $A$ gives a saddle at $A^{-1}\mathbf{b}$.

Why the PD minimiser is global (completing the square). Let $A\mathbf{x}^\star = \mathbf{b}$. Expand $\tfrac12(\mathbf{x}-\mathbf{x}^\star)^\top A(\mathbf{x}-\mathbf{x}^\star) = \tfrac12\mathbf{x}^\top A\mathbf{x} - \mathbf{x}^\top A\mathbf{x}^\star + \tfrac12 \mathbf{x}^{\star\top} A \mathbf{x}^\star = \tfrac12\mathbf{x}^\top A\mathbf{x} - \mathbf{b}^\top\mathbf{x} + \tfrac12\mathbf{b}^\top\mathbf{x}^\star$. Therefore

$$f(\mathbf{x}) = f(\mathbf{x}^\star) + \tfrac12 (\mathbf{x} - \mathbf{x}^\star)^\top A\, (\mathbf{x} - \mathbf{x}^\star), \qquad f(\mathbf{x}^\star) = -\tfrac12 \mathbf{b}^\top \mathbf{x}^\star.$$

If $A \succ 0$ the last term is $\gt 0$ for every $\mathbf{x} \ne \mathbf{x}^\star$, so $\mathbf{x}^\star$ beats every other point. ∎

The unconstrained recipe.

1. Compute the gradient $\nabla f$.
2. Solve $\nabla f = \mathbf{0}$: these are the critical points (first-order condition).
3. Compute the Hessian and evaluate it at each critical point.
4. Read the eigenvalues: all $\gt 0$ min; all $\lt 0$ max; mixed saddle; some $0$ inconclusive (probe further).
5. For a global answer, compare the values of the minima and ask whether $f$ can go lower far away (or use convexity, Chapter 3.6).

Gradient descent finds a low point of a function $f$ (the objective) with this loop. Here $\mathbf{x}_k$ is the point after $k$ steps (the iterate), and one pass through the loop is one iteration:

1. Choose a starting point $\mathbf{x}_0$ and a learning rate $\eta \gt 0$.
2. Feel the slope: compute the gradient $\mathbf{g}_k = \nabla f(\mathbf{x}_k)$.
3. Step downhill: $\ \mathbf{x}_{k+1} = \mathbf{x}_k - \eta\,\mathbf{g}_k$.
4. If the stopping rule says "good enough" (for example, the gradient is almost zero, or we ran out of time), stop. Otherwise go back to step 2.

Everything in this chapter is a closer look at one of these four lines.

An objective function is a function $f:\mathbb{R}^n\to\mathbb{R}$. We want a point $\mathbf{x}^\star$ where $f$ is as small as possible.

Its gradient is the column vector of partial derivatives (see the gradient in the Calculus guide):

$$\nabla f(\mathbf{x}) = \begin{bmatrix} \partial f/\partial x_1 \\ \vdots \\ \partial f/\partial x_n \end{bmatrix}.$$

The slope of $f$ at $\mathbf{x}$ when you walk in the unit direction $\mathbf{u}$ is the directional derivative $\nabla f(\mathbf{x})\cdot\mathbf{u} = \|\nabla f\|\cos\theta$, where $\theta$ is the angle between $\mathbf{u}$ and $\nabla f$. Since $-1\le\cos\theta\le 1$:

• $\theta = 0$ (walk along $\nabla f$): the slope is $+\|\nabla f\|$, the largest possible. So the gradient is the direction of steepest ascent.
• $\theta = 180^\circ$ (walk along $-\nabla f$): slope $-\|\nabla f\|$, the most negative. Steepest descent.
• $\theta = 90^\circ$: slope $0$. The gradient is perpendicular to the contour line.

A point where $\nabla f = \mathbf{0}$ is a stationary point (flat ground: a minimum, a maximum or a saddle; Chapter 3.2).

Derivation, in three steps.

1. The tilted board. For a small step $\mathbf{d}$: $\ f(\mathbf{x}+\mathbf{d}) \approx f(\mathbf{x}) + \nabla f(\mathbf{x})^\top\mathbf{d}$.
2. The best direction. Fix the step length $\|\mathbf{d}\| = r$. We want $\nabla f^\top\mathbf{d}$ as negative as possible. By the Cauchy–Schwarz inequality, $\nabla f^\top\mathbf{d} \ge -\|\nabla f\|\,\|\mathbf{d}\|$, with equality exactly when $\mathbf{d}$ points opposite to $\nabla f$. So $\mathbf{d} = -r\,\nabla f/\|\nabla f\|$.
3. The length. Make the length proportional to the slope: $r = \eta\|\nabla f\|$. Then $\mathbf{d} = -\eta\,\nabla f(\mathbf{x})$.

$$\boxed{\ \mathbf{x}_{k+1} = \mathbf{x}_k - \eta\,\nabla f(\mathbf{x}_k)\ }$$

A second way to see it (the "price for distance" view). Build a model that trusts the board but charges a price for walking far: $\ m(\mathbf{d}) = f + \mathbf{g}^\top\mathbf{d} + \frac{1}{2\eta}\|\mathbf{d}\|^2$. Its lowest point is where the slope of $m$ is zero: $\mathbf{g} + \mathbf{d}/\eta = \mathbf{0}$, so $\mathbf{d} = -\eta\mathbf{g}$, the same rule. Now $1/\eta$ reads as "how curved we assume the ground is": a big $\eta$ means we assume gentle curvature and walk far.

When is a step guaranteed to help? Suppose the ground never curves more than $L$ (all eigenvalues of the Hessian are at most $L$). Then $f(\mathbf{x}+\mathbf{d}) \le f + \mathbf{g}^\top\mathbf{d} + \frac L2\|\mathbf{d}\|^2$ (we prove this in Chapter 3.5). Put $\mathbf{d} = -\eta\mathbf{g}$:

$$f(\mathbf{x}_{k+1}) \le f(\mathbf{x}_k) - \eta\Big(1 - \frac{L\eta}{2}\Big)\|\mathbf{g}_k\|^2 .$$

The bracket is positive exactly when $\eta \lt 2/L$, so every step goes down. With $\eta = 1/L$ the guaranteed drop is $\|\mathbf{g}\|^2/(2L)$. In our example $L = 6$ (the largest second derivative of $x_1^2+3x_2^2$), and for $\eta = 0.1$ the guaranteed drop is $0.1(1-0.3)\cdot208 = 14.56$; the actual drop was $28 - 12.16 = 15.84 \ge 14.56$. ✓

Stack the inputs into the design matrix $X$ (row $i$ is $[1,\ x_i]$) and the targets into $\mathbf{y}$. Then, with $\mathbf{w} = [b, m]$:

$$f(\mathbf{w}) = \tfrac12\|X\mathbf{w}-\mathbf{y}\|^2,\qquad \nabla f(\mathbf{w}) = X^\top(X\mathbf{w}-\mathbf{y}),\qquad \nabla^2 f = X^\top X.$$

Gradient descent on least squares is therefore $\ \mathbf{w}\leftarrow\mathbf{w} - \eta\,X^\top(X\mathbf{w}-\mathbf{y})$. The Hessian $X^\top X$ is constant, so $f$ is exactly a quadratic bowl (positive definite when the columns of $X$ are independent; see quadratic forms and least squares). If your loss is the mean squared error $\frac1n\|X\mathbf{w}-\mathbf{y}\|^2$ (as in the Calculus guide), the gradient is $\frac2nX^\top(X\mathbf{w}-\mathbf{y})$: the same direction, just a different scale, which only rescales $\eta$.

For a run $\mathbf{x}_0,\mathbf{x}_1,\dots$ of gradient descent we track

$$f(\mathbf{x}_k),\qquad \|\nabla f(\mathbf{x}_k)\|,\qquad \|\mathbf{x}_{k+1}-\mathbf{x}_k\| = \eta\,\|\nabla f(\mathbf{x}_k)\|.$$

The last identity follows directly from the update rule: the step is $-\eta\nabla f$, so its length is $\eta$ times the gradient length. The plots below use a log scale on the vertical axis, because a loss that shrinks by the same factor each step is a straight line on a log plot (we explain why in the quadratic section). "Loss gap" means $f(\mathbf{x}_k) - f^\star$, the height above the lowest point.

A sequence $\mathbf{x}_k$ converges to $\mathbf{x}^\star$ if $\|\mathbf{x}_k-\mathbf{x}^\star\|\to0$ as $k\to\infty$. Several related statements are used:

• Iterates converge: $\|\mathbf{x}_k-\mathbf{x}^\star\|\to0$.
• Values converge: $f(\mathbf{x}_k)\to f^\star$.
• Stationarity: $\|\nabla f(\mathbf{x}_k)\|\to0$ (the only one we can always measure).

Stopping rules (stop at the first $k$ where a rule fires; use a small tolerance $\varepsilon$ you choose):

1. Gradient small: $\|\nabla f(\mathbf{x}_k)\|\le\varepsilon$ (the usual one).
2. Steps small: $\|\mathbf{x}_{k+1}-\mathbf{x}_k\|\le\varepsilon$.
3. Loss stalls: $|f(\mathbf{x}_{k})-f(\mathbf{x}_{k+1})|\le\varepsilon$.
4. Budget: $k$ reaches a maximum number of iterations (always keep this one as a safety net).

What does it converge to? For a smooth convex function with a suitable $\eta$: to a global minimum. For a non-convex function: to a stationary point ($\nabla f=\mathbf{0}$), which can be a local minimum, and in unlucky cases a saddle. How fast it converges is the topic of Chapter 3.5; in the next section we compute it exactly for quadratics.

Setting. Let $f(\mathbf{x}) = \tfrac12\mathbf{x}^\top A\mathbf{x} - \mathbf{b}^\top\mathbf{x}$ with $A$ symmetric positive definite (positive definite: all eigenvalues $\lambda_i \gt 0$). Its gradient is $A\mathbf{x}-\mathbf{b}$ and its minimiser is $\mathbf{x}^\star = A^{-1}\mathbf{b}$, so $\nabla f(\mathbf{x}) = A(\mathbf{x}-\mathbf{x}^\star)$.

Derivation.

1. The error. Let $\mathbf{e}_k = \mathbf{x}_k-\mathbf{x}^\star$. The update gives $\mathbf{e}_{k+1} = \mathbf{e}_k - \eta A\mathbf{e}_k = (I-\eta A)\,\mathbf{e}_k$. So $\mathbf{e}_k = (I-\eta A)^k\mathbf{e}_0$.
2. Separate the axes. $A$ is symmetric, so $A = Q\Lambda Q^\top$ with $Q$ orthogonal and $\Lambda = \mathrm{diag}(\lambda_1,\dots,\lambda_n)$ (symmetric eigen-decomposition; the columns of $Q$ are the bowl's axes). Write the error in the axis coordinates: $\mathbf{c}_k = Q^\top\mathbf{e}_k$.
3. Each axis on its own. Multiply step 1 by $Q^\top$: $\mathbf{c}_{k+1} = (I-\eta\Lambda)\mathbf{c}_k$. Since $I-\eta\Lambda$ is diagonal, coordinate $i$ evolves alone: $$c_i(k) = (1-\eta\lambda_i)^k\,c_i(0).$$
4. When does everything shrink? We need $|1-\eta\lambda_i|\lt 1$ for every $i$, that is $0\lt \eta\lambda_i\lt 2$. The binding one is the largest eigenvalue: $$\boxed{\ 0\lt \eta\lt \frac{2}{\lambda_{\max}}\ }$$
5. The rate. The slowest axis decides: $\|\mathbf{e}_k\|\le\rho^k\|\mathbf{e}_0\|$ with $\rho(\eta) = \max_i|1-\eta\lambda_i| = \max\big(|1-\eta\lambda_{\min}|,\ |1-\eta\lambda_{\max}|\big)$. (Because $Q$ is orthogonal it does not change lengths.)
6. The best fixed step. $1-\eta\lambda_{\min}$ decreases as $\eta$ grows and $|1-\eta\lambda_{\max}|$ is first shrinking, then growing. The best $\eta$ makes the two equal in size, $1-\eta\lambda_{\min} = -(1-\eta\lambda_{\max})$: $$\boxed{\ \eta^\star = \frac{2}{\lambda_{\min}+\lambda_{\max}},\qquad \rho^\star = \frac{\lambda_{\max}-\lambda_{\min}}{\lambda_{\max}+\lambda_{\min}} = \frac{\kappa-1}{\kappa+1}\ }$$ where $\kappa = \lambda_{\max}/\lambda_{\min}$ is the condition number. (Check: $1-\eta^\star\lambda_{\min} = \frac{\lambda_{\max}+\lambda_{\min}-2\lambda_{\min}}{\lambda_{\max}+\lambda_{\min}} = \rho^\star$ ✓.)

Numbers. $\kappa = 10$: $\eta^\star = 2/11$, $\rho^\star = 9/11 = 0.818$ (we measured $0.8182$ by running the code). To shrink the error by $10^{-6}$ you need $k\ge \ln(10^{6})/\ln(1/\rho)$ steps: $68.8$ steps for $\kappa=10$, $690.8$ for $\kappa=100$. In general this is about $\frac\kappa2\ln\frac1\varepsilon$: the number of steps grows in proportion to $\kappa$.

The loss shrinks twice as fast on a log scale. $f-f^\star = \tfrac12\sum\lambda_ic_i^2$, so each term shrinks like $(1-\eta\lambda_i)^{2k}$: the loss gap decays like $\rho^{2k}$. On a log plot each $\log|c_i|$ is a straight line with slope $\log|1-\eta\lambda_i|$, which is why we plot loss curves on a log axis.

Beyond quadratics. Near a minimum $\mathbf{x}^\star$ of any smooth $f$, $f\approx f^\star+\tfrac12(\mathbf{x}-\mathbf{x}^\star)^\top H(\mathbf{x}-\mathbf{x}^\star)$ with $H=\nabla^2f(\mathbf{x}^\star)$. So close enough to the minimum, GD behaves like the quadratic with $A=H$ (we prove this properly in Chapter 3.5, where $\lambda_{\max}$ becomes the smoothness constant $L$ and $\lambda_{\min}$ the strong-convexity constant $\mu$).

The learning rate (or step size, when it is constant) $\eta\gt 0$ is the scalar in $\mathbf{x}_{k+1}=\mathbf{x}_k-\eta\nabla f(\mathbf{x}_k)$. It is a hyperparameter: a setting you choose, not something the method learns. For an $L$-smooth function:

• Stability: $0\lt \eta\lt 2/L$ (exact for quadratics; for general functions it is the threshold for guaranteed decrease, see the derivation above).
• Safe default: $\eta=1/L$ (guaranteed drop $\|\nabla f\|^2/(2L)$ per step).
• Best constant step on a quadratic: $2/(\lambda_{\min}+\lambda_{\max})$, which gives rate $(\kappa-1)/(\kappa+1)$.

Scale rules (they save debugging time). If you multiply the loss by $c$, then $L$ becomes $cL$, so $\eta$ must become $\eta/c$. In particular, switching from the mean loss over $n$ examples to the sum multiplies $L$ by $n$, so the same $\eta$ would explode.

If you do not know $L$: try $\eta$ on a log grid ($1, 0.3, 0.1, 0.03, 0.01,\dots$) and keep the largest value whose loss curve falls smoothly. Many people also run a short "learning-rate range test" (increase $\eta$ every step and watch where the loss starts to rise).

On a parabola with curvature $\lambda$, gradient descent is the straight-line map $x_{k+1}=m\,x_k$ with the multiplier $m=1-\eta\lambda$. (Measure $x$ from the minimum.) Then:

• $0\lt m\lt 1$ ($0\lt \eta\lt 1/\lambda$): the iterates approach from one side. No overshoot.
• $m=0$ ($\eta=1/\lambda$): lands on the minimum in one step.
• $-1\lt m\lt 0$ ($1/\lambda\lt \eta\lt 2/\lambda$): overshoot. $x$ changes sign every step but $|x|$ shrinks: oscillating convergence.
• $m=-1$ ($\eta=2/\lambda$): a two-cycle $+c,-c,+c,\dots$, no progress.
• $m\lt -1$ ($\eta\gt 2/\lambda$): oscillating divergence; $|x|$ grows like $|m|^k$.

In several dimensions each axis has its own $m_i=1-\eta\lambda_i$. The steepest axis (largest $\lambda_i$) overshoots first and diverges first, so $\eta\lt 2/\lambda_{\max}$ protects all axes. A zig-zag across a valley is exactly "the steep axis has $-1\lt m\lt 0$ while the flat axis crawls with $m$ close to $+1$".

The condition number of the Hessian is $\kappa=\lambda_{\max}/\lambda_{\min}\ge1$: how much steeper the steepest direction is than the flattest. A problem with large $\kappa$ is ill-conditioned. On a quadratic, gradient descent with the best fixed step needs about $\frac\kappa2\ln\frac1\varepsilon$ iterations to reach accuracy $\varepsilon$: proportional to $\kappa$.

A plateau is a region where $\|\nabla f\|$ is small although we are far from a minimum (or where the curvature vanishes at the minimum, as in $x^4$). Near such places the convergence is sublinear (the error shrinks like $1/\sqrt{k}$ or $1/k$, not like $\rho^k$).

Remedies (each is a topic later in the guide):

• Rescale the problem (you can do this today): standardise and centre the features, which makes the valley rounder. Our least-squares example went from $\kappa=8.55$ to $1.5$ just by centring $x$. This idea, in general, is called preconditioning.
• Momentum (Chapter 3.4): averaging past gradients damps the zig-zag and speeds up the floor; on quadratics it turns $\kappa$ into about $\sqrt\kappa$ in the iteration count.
• Adaptive methods such as AdaGrad, RMSProp and Adam (Chapter 3.4): a separate step size for each coordinate.
• Second-order methods (Chapter 3.12): Newton's method and L-BFGS use curvature to point at the bottom, and on a quadratic Newton needs one step.

Fixed: $\eta_k=\eta$. Decreasing (common schedules): $\eta_k=\dfrac{\eta_0}{1+d\,k}$ (inverse time), $\eta_k=\eta_0\gamma^k$ (exponential), $\eta_k=\dfrac{\eta_0}{\sqrt{k+1}}$. (More schedules, such as cosine and warmup, are in Chapter 3.4.) For noisy gradients the classical requirement is $\sum_k\eta_k=\infty$ (we can still travel any distance) and $\sum_k\eta_k^2\lt \infty$ (the noise eventually dies out) (Chapter 3.14).

Backtracking line search (awareness): choose a starting length $\alpha_0$ (often $1$), a shrink factor $\beta\in(0,1)$ (often $\tfrac12$) and a tiny $c$ (often $10^{-4}$). At each iteration, with direction $\mathbf{d}=-\nabla f(\mathbf{x}_k)$:

1. Set $\alpha=\alpha_0$.
2. While $f(\mathbf{x}_k+\alpha\mathbf{d})\gt f(\mathbf{x}_k)+c\,\alpha\,\nabla f(\mathbf{x}_k)^\top\mathbf{d}$: set $\alpha\leftarrow\beta\alpha$.
3. Take the step $\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha\mathbf{d}$.

The inequality is the Armijo (sufficient decrease) condition: "the function must fall by at least a fraction $c$ of what the tilted-board model promised". Since $\nabla f^\top\mathbf{d}=-\|\nabla f\|^2$ here, this is the test in the example. It always stops after finitely many halvings. An exact line search minimises $f$ along the ray; it is rarely worth its cost. Stronger conditions (Wolfe) are used with quasi-Newton methods (Chapter 3.12).

Initialization is the choice of $\mathbf{x}_0$. The basin of attraction of a minimum $\mathbf{x}^\star$ is the set of starting points from which gradient descent (with a given $\eta$) converges to $\mathbf{x}^\star$.

• Convex problems (Chapter 3.6): there are no bad valleys; with $\eta\lt 2/L$ every start converges to a global minimum. A zero start $\mathbf{x}_0=\mathbf{0}$ is a perfectly good default (linear regression, logistic regression).
• Non-convex problems: the start decides which stationary point you reach. Practical answers: random restarts (run from several random starts and keep the lowest loss), warm starts (start from a solution of a similar problem, such as a pre-trained model), or a problem-specific initialization.
• Neural networks (a forward note, Chapter 3.15): weights are started at small random numbers, scaled by the width of the layer (the names to look up are Xavier/Glorot and He initialization). Two reasons: if all weights start equal (for example zero) all the hidden units in a layer get identical gradients and stay identical forever (the symmetry is never broken), and the scale controls whether signals and gradients shrink or blow up as they pass through many layers.

Symmetry traps. Starting exactly on a line of symmetry can lock you out of the good valleys: for $f=x^2-y^2+y^4/4$ a start with $y=0$ never leaves the saddle at the origin ($\partial f/\partial y = -2y+y^3=0$ stays $0$), while any $y\neq0$ slides away. This is the same reason zero-initialized networks do not learn.

Let $f(\mathbf{w})=\frac1n\sum_i\ell_i(\mathbf{w})$. An epoch is one pass through all $n$ examples. In every variant the update is $\mathbf{w}\leftarrow\mathbf{w}-\eta\,\hat{\mathbf{g}}$ with

Here $\sigma^2=\frac1n\sum_i\|\nabla\ell_i-\nabla f\|^2$ measures how much the examples disagree. Two facts make the whole idea work:

• Unbiased: $\mathbb{E}[\hat{\mathbf{g}}]=\nabla f(\mathbf{w})$. On average the estimate is the true gradient.
• Variance falls like $1/B$ (for samples drawn independently), so the noise (standard deviation) falls like $1/\sqrt B$: four times the batch, half the noise.

Cost per epoch is the same for all three (about $n$ gradient computations); what differs is how many updates you get out of it: $1$, $n$ or $n/B$. Typical loop: shuffle the data, cut it into batches of size $B$, and for each batch compute $\hat{\mathbf{g}}$ and update. In deep-learning libraries "SGD" almost always means mini-batch SGD. Common batch sizes are $32$ to a few hundred (a habit, not a law).

Behaviour near the bottom. With a fixed $\eta$ the noise never fully fades, so SGD does not settle at $\mathbf{w}^\star$: it hovers in a "noise ball" around it, whose size grows with $\eta$ and shrinks with $B$. Shrinking $\eta$ over time (or growing $B$) tightens the ball (details in Chapter 3.14).

The loss surface (or loss landscape) of an objective $f$ with two parameters is the graph $z=f(x_1,x_2)$. Its contour lines are the level sets $\{f=c\}$. Valleys are minima, hilltops are maxima, and a saddle is a point that is a minimum in one direction and a maximum in another (like a mountain pass; Chapter 3.2). Gradient descent produces a path that, seen from above, crosses each contour line at a right angle (the gradient is perpendicular to the contour).

Real models have millions of parameters, so their surface cannot be drawn. People draw two-dimensional slices through it and rely on the intuition from low dimensions, which is useful but not the whole truth (Chapter 3.15).

Recall the numbers from Chapter 3.3. For a bowl whose curvature ranges from $\mu$ (flattest direction) to $L$ (steepest direction), the condition number is $\kappa = L/\mu$. With the best fixed step $\eta = 2/(L+\mu)$, the distance to the minimum shrinks, at best, by the factor

$$\frac{\kappa - 1}{\kappa + 1} \quad\text{per step.}$$

For $\kappa = 100$ that is $99/101 \approx 0.980$, so you need about $115$ steps just to make the error ten times smaller. The family tree of fixes for this chapter:

Given a stream $g_1, g_2, \dots$ and a number $0 \le \beta \lt 1$, the exponentially weighted average is

$$m_t = \beta\, m_{t-1} + (1 - \beta)\, g_t, \qquad m_0 = 0.$$

Unroll it to see the weights. Substitute $m_{t-1} = \beta m_{t-2} + (1-\beta)g_{t-1}$, then $m_{t-2}$, and so on:

$$m_t = (1-\beta)\big(g_t + \beta\, g_{t-1} + \beta^2 g_{t-2} + \dots + \beta^{t-1} g_1\big).$$

So the gradient that is $k$ steps old gets the weight $(1-\beta)\beta^k$: each step back multiplies the weight by $\beta$. Three facts follow.

• The weights add up to $1 - \beta^t$. The sum $(1-\beta)(1 + \beta + \dots + \beta^{t-1}) = (1-\beta)\dfrac{1-\beta^t}{1-\beta} = 1 - \beta^t$. After many steps this is almost $1$, so $m_t$ really is an average. In the first few steps it is less than $1$, which is why $m_t$ starts low.
• Average age. The weight on a $k$-step-old value is $(1-\beta)\beta^k$, so the average age is $\sum_{k\ge 0} k(1-\beta)\beta^k = \beta/(1-\beta)$.
• Effective window $\approx 1/(1-\beta)$. After $1/(1-\beta)$ steps a weight has shrunk by $\beta^{1/(1-\beta)}$, which tends to $e^{-1} \approx 0.37$ as $\beta \to 1$. So "the last $1/(1-\beta)$ values" is a good picture of what is being averaged. This is a rule of thumb, not an exact window.

The momentum (heavy-ball) update, with learning rate $\eta$ and momentum coefficient $\beta \in [0, 1)$ (often $0.9$), is

$$\mathbf{v}_{t+1} = \beta\,\mathbf{v}_t - \eta\,\nabla f(\mathbf{x}_t), \qquad \mathbf{x}_{t+1} = \mathbf{x}_t + \mathbf{v}_{t+1}, \qquad \mathbf{v}_0 = \mathbf{0}.$$

Since the step taken is $\mathbf{x}_{t+1} - \mathbf{x}_t = \mathbf{v}_{t+1}$, this is the same as: new step = plain gradient step + $\beta\,\times$ the previous step,

$$\mathbf{x}_{t+1} = \mathbf{x}_t - \eta\,\mathbf{g}_t + \beta\,(\mathbf{x}_t - \mathbf{x}_{t-1}).$$

It is an average of past gradients. Unroll $\mathbf{v}_t$ exactly as in the previous section: $\mathbf{v}_t = -\eta\,(\mathbf{g}_{t-1} + \beta\,\mathbf{g}_{t-2} + \beta^2\mathbf{g}_{t-3} + \dots)$. The weights $\beta^k$ add up to $1/(1-\beta)$, so

$$\mathbf{v}_t = -\frac{\eta}{1-\beta}\ \times\ (\text{an exponentially weighted average of past gradients}).$$

Why it damps zig-zag and speeds up valleys. Look at one coordinate.

• Steady gradient $g$ (along the valley): the velocity settles where $v = \beta v - \eta g$, so $v = -\eta g/(1-\beta)$. With $\beta = 0.9$ that is a step 10 times larger than plain GD's $-\eta g$. This is the "effective window $1/(1-\beta)$" from the previous section.
• Alternating gradient $+g, -g, +g, \dots$ (across the valley): the velocity settles into a see-saw of size only $\eta g/(1+\beta)$. With $\beta = 0.9$ that is $0.53\,\eta g$, smaller than plain GD's $\eta g$.
• So the ratio "useful steady step : useless see-saw" improves from $1$ to $\dfrac{1/(1-\beta)}{1/(1+\beta)} = \dfrac{1+\beta}{1-\beta}$, which is $19$ for $\beta = 0.9$.

How fast, exactly (quadratics). In one direction with curvature $h$ the gradient is $hx$ and the update becomes $x_{t+1} = (1 + \beta - \eta h)\,x_t - \beta\,x_{t-1}$. Its characteristic equation is $\lambda^2 - (1+\beta-\eta h)\lambda + \beta = 0$, and the error shrinks like $\rho^t$ where $\rho$ is the larger $|\lambda|$. Two facts follow.

• Stability: it converges if and only if $0 \lt \eta h \lt 2(1+\beta)$. Plain GD is the case $\beta=0$, limit $2$. So momentum even allows a larger $\eta h$.
• Exactly $\sqrt{\beta}$ in a whole band: the two roots are complex whenever $(1-\sqrt\beta)^2 \le \eta h \le (1+\sqrt\beta)^2$, and then $|\lambda| = \sqrt{\beta}$ (the product of the roots is $\beta$), no matter what $h$ is. Pick $\eta$ and $\beta$ so that every curvature between $\mu$ and $L$ falls inside that band: $\beta = \Big(\dfrac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\Big)^2$ and $\eta = \dfrac{4}{(\sqrt L + \sqrt\mu)^2}$. Then the rate is $\sqrt\beta = \dfrac{\sqrt\kappa - 1}{\sqrt\kappa + 1}$ (Polyak's result for quadratics).

For $\kappa = 100$: plain GD at its best step shrinks the error by $0.980$ per step, tuned momentum by $0.818$. The number of steps needed grows like $\sqrt\kappa$ instead of $\kappa$. (Quick numerical check, error in $f$ down to $10^{-12}$ on a bowl with $\kappa = 100$: GD takes 824 steps, tuned momentum 109.) These formulas are exact for quadratics; for general losses they are a guide, not a guarantee.

The Nesterov momentum update (the "classical" teaching form) is

$$\tilde{\mathbf{x}}_t = \mathbf{x}_t + \beta\,\mathbf{v}_t, \qquad \mathbf{v}_{t+1} = \beta\,\mathbf{v}_t - \eta\,\nabla f(\tilde{\mathbf{x}}_t), \qquad \mathbf{x}_{t+1} = \mathbf{x}_t + \mathbf{v}_{t+1}.$$

The only difference from momentum is where the gradient is measured: at the look-ahead point $\tilde{\mathbf{x}}_t$ instead of $\mathbf{x}_t$.

Equivalent two-line form. Put $\mathbf{y}_t = \mathbf{x}_t + \beta\mathbf{v}_t$. Because $\mathbf{x}_{t+1} - \mathbf{x}_t = \mathbf{v}_{t+1}$, one checks that

$$\mathbf{x}_{t+1} = \mathbf{y}_t - \eta\,\nabla f(\mathbf{y}_t), \qquad \mathbf{y}_{t+1} = \mathbf{x}_{t+1} + \beta\,(\mathbf{x}_{t+1} - \mathbf{x}_t).$$

In words: take a plain gradient step from the look-ahead point, then extrapolate along the direction you just moved.

Why it brakes earlier. Use the first-order Taylor expansion (linearization, with Hessian $H$): $\nabla f(\mathbf{x} + \beta\mathbf{v}) \approx \nabla f(\mathbf{x}) + \beta H\mathbf{v}$. Put that into the update:

$$\mathbf{v}_{t+1} \approx \beta\,\mathbf{v}_t - \eta\,\mathbf{g}_t \;-\; \eta\beta\,H\mathbf{v}_t.$$

The first two terms are exactly momentum. The extra term $-\eta\beta H\mathbf{v}_t$ opposes the velocity, and more strongly where the curvature $H$ is large. It is friction that is switched on exactly in the steep directions, where overshoot happens. (For $f = \tfrac12 h x^2$ this is exact: $v_{t+1} = \beta(1 - \eta h)\,v_t - \eta h\,x_t$.)

What is proved. For a smooth convex function (gradient Lipschitz with constant $L$), the two-line form with step $\eta = 1/L$ and the special momentum weights $\beta_t = (t-1)/(t+2)$ gives an error that shrinks like $O(1/t^2)$, versus $O(1/t)$ for plain gradient descent. Up to constant factors, no method that only uses gradients can guarantee a better rate on that class of functions (a lower bound by Nemirovski and Yudin). With a fixed $\beta$ such as $0.9$ in deep learning, and non-convex losses, no such guarantee exists: treat it as a good heuristic. (You will meet rates in Chapter 3.5.)

An adaptive method replaces the single number $\eta$ by one number per coordinate. Let $\mathbf{s}_t$ be a running measure of the squared gradient of each coordinate (a different recipe for $\mathbf{s}_t$ gives a different method). The update is

$$\mathbf{x}_{t+1} = \mathbf{x}_t - \eta\ \frac{\mathbf{g}_t}{\sqrt{\mathbf{s}_t} + \varepsilon},$$

where $\varepsilon$ is a tiny number (such as $10^{-8}$) that avoids dividing by zero. The preconditioning view. This is gradient descent with a diagonal rescaling:

$$\mathbf{x}_{t+1} = \mathbf{x}_t - \eta\,P_t^{-1}\,\mathbf{g}_t, \qquad P_t = \mathrm{diag}\big(\sqrt{\mathbf{s}_t} + \varepsilon\big).$$

The matrix $P_t$ is called a preconditioner. It reshapes the problem so that the valley looks rounder. Newton's method (Chapter 3.12) is the same idea with the best possible preconditioner, the full Hessian $H$ instead of a diagonal. Here is how the three famous methods choose $\mathbf{s}_t$:

Two insights.

• The step has a fixed size in parameter units. $g/\sqrt{s}$ has no units: if you rescale the loss by $1000$, the gradients and $\sqrt{s}$ both grow $1000$-fold and the step does not change. That is why $\eta$ becomes "roughly how far a parameter moves per step", whatever the loss scale is. With no averaging at all ($s = g^2$) the step is $\eta\,g/|g| = \eta\,\mathrm{sign}(g)$: sign descent.
• It is a diagonal fix only. Dividing by gradient size is a crude stand-in for dividing by curvature, and a diagonal $P$ can only fix a valley whose axes line up with the coordinate axes. In a rotated valley it helps much less (see the widget below).

AdaGrad (Duchi, Hazan and Singer, 2011), per coordinate:

$$\mathbf{G}_t = \mathbf{G}_{t-1} + \mathbf{g}_t^2, \qquad \mathbf{x}_{t+1} = \mathbf{x}_t - \frac{\eta}{\sqrt{\mathbf{G}_t} + \varepsilon}\ \mathbf{g}_t, \qquad \mathbf{G}_0 = \mathbf{0}.$$

The squares and the root are taken entry by entry; $\varepsilon \approx 10^{-8}$ protects against $0/0$. This is the adaptive update with $\mathbf{s}_t = \mathbf{G}_t$ (the sum).

• The first step is $\eta$ in every coordinate. At $t = 1$, $G = g^2$, so the step is $\eta\,g/|g| = \eta\,\mathrm{sign}(g)$, whatever the gradient size.
• The learning rate decays. If a coordinate's gradient has about the same size $c$ each step, then $G_t \approx t\,c^2$, so its effective rate is $\eta/(c\sqrt{t})$ and its step is about $\eta/\sqrt{t}$. After $10{,}000$ steps the step is $100$ times smaller than at the start. The steps still add up to infinity (the sum of $1/\sqrt{t}$ diverges), so the iterate can in principle travel as far as needed, but slowly.
• Known theory. For convex problems AdaGrad has a proven guarantee (a regret bound) that is competitive with the best per-coordinate step sizes you could have picked in hindsight, and it is especially good when the gradients are sparse. (This is a statement about convex problems; deep non-convex losses are different.)

RMSProp (proposed by Geoffrey Hinton in a 2012 lecture; there is no original paper), per coordinate:

$$\mathbf{s}_t = \beta\,\mathbf{s}_{t-1} + (1-\beta)\,\mathbf{g}_t^2, \qquad \mathbf{x}_{t+1} = \mathbf{x}_t - \frac{\eta}{\sqrt{\mathbf{s}_t} + \varepsilon}\ \mathbf{g}_t, \qquad \mathbf{s}_0 = \mathbf{0}.$$

Typical values: $\beta = 0.9$ (or $0.99$), $\varepsilon = 10^{-8}$, and a small $\eta$ such as $0.001$. $\mathbf{s}_t$ is exactly the exponentially weighted average of $\mathbf{g}^2$ from the earlier section, so $\sqrt{\mathbf{s}_t}$ is the recent root mean square of the gradient, over a window of about $1/(1-\beta)$ steps.

• It fixes AdaGrad's decay. With a constant-size gradient, $\mathbf{s}_t$ settles at $g^2$, so the step stays near $\eta$ forever instead of shrinking like $1/\sqrt{t}$.
• It starts with a big step. Because $\mathbf{s}_0 = \mathbf{0}$, after $t$ steps with a constant gradient $\mathbf{s}_t = (1-\beta^t)\,g^2$, and the step multiplier is $1/\sqrt{1-\beta^t}$. At $t=1$ that is $1/\sqrt{1-\beta}$: $3.16$ for $\beta = 0.9$ and $10$ for $\beta = 0.99$. This start-up bias is exactly what Adam's correction removes.
• It adapts to a change. If the gradients suddenly become 10 times smaller, $\mathbf{s}_t$ follows within about $1/(1-\beta)$ steps and the step size returns to about $\eta$.

Adam (Kingma and Ba, 2015). At step $t = 1, 2, \dots$ with gradient $\mathbf{g}_t$ (all operations entry by entry):

$$\begin{aligned} \mathbf{m}_t &= \beta_1\,\mathbf{m}_{t-1} + (1-\beta_1)\,\mathbf{g}_t &&\text{(first moment: average gradient)}\\ \mathbf{v}_t &= \beta_2\,\mathbf{v}_{t-1} + (1-\beta_2)\,\mathbf{g}_t^2 &&\text{(second moment: average squared gradient)}\\ \hat{\mathbf{m}}_t &= \mathbf{m}_t/(1-\beta_1^t), \qquad \hat{\mathbf{v}}_t = \mathbf{v}_t/(1-\beta_2^t) &&\text{(bias correction)}\\ \mathbf{x}_{t+1} &= \mathbf{x}_t - \eta\,\hat{\mathbf{m}}_t\big/\big(\sqrt{\hat{\mathbf{v}}_t} + \varepsilon\big) \end{aligned}$$

with $\mathbf{m}_0 = \mathbf{v}_0 = \mathbf{0}$. Defaults: $\beta_1 = 0.9$ (memory of about $10$ steps), $\beta_2 = 0.999$ (about $1000$ steps), $\varepsilon = 10^{-8}$; the paper suggests $\eta = 0.001$. (Careful: here $\mathbf{v}$ is the second moment, not the velocity of momentum.)

Where does $1-\beta^t$ come from? Unroll the first moment as in the exponentially-weighted-average section: $m_t = (1-\beta_1)\sum_{i=1}^{t}\beta_1^{\,t-i}\,g_i$. Suppose, for the sake of the argument, that every gradient has the same expected value $\mu = \mathbb{E}[g_i]$. Then

$$\mathbb{E}[m_t] = \mu\,(1-\beta_1)\sum_{i=1}^{t}\beta_1^{\,t-i} = \mu\,(1-\beta_1)\,\frac{1-\beta_1^t}{1-\beta_1} = \mu\,\big(1 - \beta_1^t\big).$$

So $m_t$ is too small by exactly the factor $1-\beta_1^t$, and dividing by it gives an average with the right expected value: $\mathbb{E}[\hat m_t] = \mu$. The same calculation for $g^2$ gives $\mathbb{E}[v_t] = (1-\beta_2^t)\,\mathbb{E}[g^2]$, hence the second correction. (If the true mean drifts, the correction is no longer exact, but the error is small because old terms carry little weight.) Notice that $1 - \beta^t$ is exactly the sum of the weights we found earlier.

Consequences.

• The first step has size $\approx\eta$ in every coordinate. At $t=1$: $\hat m_1 = g_1$ and $\hat v_1 = g_1^2$, so the step is $\eta\,g_1/(|g_1| + \varepsilon) \approx \eta\,\mathrm{sign}(g_1)$.
• $\eta$ is roughly a per-step distance. Since $|\hat m| \lesssim \sqrt{\hat v}$ in most situations, each parameter moves at most about $\eta$ per step (in the rare extreme of one huge gradient after a long calm period, up to about $\eta(1-\beta_1)/\sqrt{1-\beta_2} \approx 3.2\,\eta$). That is a kind of built-in trust region.
• Why $\beta_2$ is so close to $1$. $\hat v$ needs many samples to be reliable (the warmup section shows how poor it is early on), so it gets a long memory. $\hat m$ should react faster, so $\beta_1$ is smaller.

AdamW (Loshchilov and Hutter, 2019) computes $\hat{\mathbf{m}}_t$ and $\hat{\mathbf{v}}_t$ from the loss gradient only, exactly as Adam does, and then

$$\mathbf{x}_{t+1} = \mathbf{x}_t - \eta\left(\frac{\hat{\mathbf{m}}_t}{\sqrt{\hat{\mathbf{v}}_t} + \varepsilon} + \lambda\,\mathbf{x}_t\right).$$

$\lambda$ is the weight-decay coefficient. The term $-\eta\lambda\mathbf{x}_t$ is the decoupled decay: when the loss gradient is $\mathbf{0}$, every weight is multiplied by exactly $1 - \eta\lambda$ per step.

Compare with Adam + L2 (the older way): replace $\mathbf{g}_t$ by $\mathbf{g}_t + \lambda\mathbf{x}_t$ before computing $\mathbf{m}$ and $\mathbf{v}$. Then the decay enters through $\hat m/\sqrt{\hat v}$, so the effective shrinking of a weight is roughly $\eta\lambda w / \sqrt{\hat v}$: inversely proportional to that weight's gradient size. With a learning-rate schedule, the decay term is scaled by the current $\eta_t$ too (this is what the usual implementations do).

An honest note. AdamW is not "minimising the loss plus an L2 penalty": at a resting point it satisfies $\hat m/\sqrt{\hat v} = -\lambda\mathbf{x}$, which depends on gradient scales. Why it often generalizes better than Adam + L2 is partly empirical. What is solid: the decay strength becomes independent of the gradient scale, which also makes $\lambda$ and $\eta$ easier to tune.

All the methods in this chapter share one skeleton: at step $t$, compute a gradient, update one or two running averages, move. They differ in what they remember and what they divide by:

A learning-rate scan (sweep) is the standard way to tune $\eta$:

1. Pick a fixed budget (number of steps or epochs) and a metric (final loss, or loss on held-out data).
2. Choose $\eta$ on a logarithmic grid (for example $10^{-4}, 3\cdot 10^{-4}, 10^{-3}, 3\cdot 10^{-3}, \dots$). A linear grid wastes almost all its points on the large values.
3. Run each, plot the metric against $\eta$, and take a value near the bottom of the valley, not at the very edge of the blow-up (the edge is fragile).

Rules of thumb (heuristics, not theorems): tune $\eta$ first, then $\beta$ or the schedule. Start Adam at $10^{-3}$ and move by factors of $3$ or $10$. A quick screening trick used in practice, the learning-rate range test, raises $\eta$ exponentially over a short run and watches where the loss starts to explode. And whenever you change the batch size, momentum or schedule, $\eta$ may need re-tuning.

A schedule is a rule $t \mapsto \eta_t$. The standard ones, with base rate $\eta_0$:

Where does the cosine come from? $\cos(\pi t/T)$ goes from $1$ (at $t = 0$) to $-1$ (at $t = T$), so $\tfrac12(1+\cos)$ goes smoothly from $1$ to $0$. It is just a convenient smooth "S" curve with zero slope at both ends. There is no deep theory behind the choice. (The linear warmup and the combined warmup + cosine schedule are in the next section.)

Linear warmup over $W$ steps:

$$\eta_t = \eta_0\,\frac{t+1}{W} \quad (t = 0, 1, \dots, W-1), \qquad \eta_t = \eta_0 \quad (t \ge W).$$

Linear warmup + cosine decay (the modern default for large models), for a total of $T$ steps:

$$\eta_t = \begin{cases} \eta_0\,\dfrac{t+1}{W} & t \lt W,\\[2mm] \eta_{\min} + \tfrac12(\eta_0 - \eta_{\min})\Big(1 + \cos\dfrac{\pi\,(t - W)}{T - W}\Big) & W \le t \le T.\end{cases}$$

Rules of thumb (not laws): the warmup is a small fraction of the whole run (a few percent is common, from a few hundred steps in small runs to thousands in very large ones). Use a longer warmup if training is unstable early, and when you use a bigger batch or a higher $\eta_0$.

How warmup interacts with Adam. Adam's bias correction (previous sections) fixes the size of the early averages; it cannot fix their noise: $\hat v_1 = g_1^2$ is a single squared number. Warmup keeps the early steps small while $\hat v$ collects more samples.

A practical decision checklist (heuristics):

1. Start with the community default for your model type (table above). It encodes years of trial and error.
2. Scan $\eta$ on a log grid (previous section). Tune $\eta$ before anything else.
3. Add a schedule (warmup, then cosine or step decay) and a sensible weight decay (AdamW's $\lambda$).
4. If training is unstable: lower $\eta$, lengthen the warmup, clip the gradient norm (Chapter 3.15), or raise $\varepsilon$. If it is slow but stable: raise $\eta$ or $\beta_1$-style momentum, or switch to an adaptive method.
5. Judge by validation performance, not only the training loss, and compare optimizers with equally good tuning of each.

What they all share. Every method here is first-order: it uses only gradients. None of them uses curvature beyond a diagonal rescaling. When the problem is small and smooth enough to afford second-order information, Newton-type methods (Chapter 3.12) converge in far fewer steps; they are rarely affordable for deep networks.

An algorithm produces a sequence of points $\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots$ We can measure its progress in three ways:

• Convergence of the iterates: $\|\mathbf{x}_k - \mathbf{x}^\star\| \to 0$. The points settle on the optimum.
• Convergence of the function values: $f(\mathbf{x}_k) - f^\star \to 0$. The score reaches its lowest value. (The difference $f(\mathbf{x}_k) - f^\star \ge 0$ is called the optimality gap.)
• Convergence of the gradients: $\|\nabla f(\mathbf{x}_k)\| \to 0$. The ground becomes flat. The points where $\nabla f = \mathbf{0}$ are the stationary points (Chapter 3.2).

Warning: the three are not the same. For a nicely curved bowl they go together. For a function with a very flat bottom (like $x^4$) the gap can be tiny while the point is still far from $\mathbf{x}^\star$. And for a non-convex function a small gradient only tells you that you are near some stationary point: a local minimum, a local maximum or a saddle. Only for convex problems (Chapter 3.6) does "a stationary point" mean "the global optimum".

Let $e_k \to 0$ be the error. The usual families are:

• Sublinear: $e_k \approx C/k^{p}$ for some $p \gt 0$ (for example $O(1/k)$ or $O(1/\sqrt{k})$). The ratio $e_{k+1}/e_k$ creeps up to $1$. Reaching accuracy $\varepsilon$ takes about $(C/\varepsilon)^{1/p}$ steps.
• Linear (geometric): $e_{k+1} \le \rho\, e_k$ with a fixed $0 \lt \rho \lt 1$, so $e_k \le \rho^k e_0$. The number $\rho$ is the rate. Reaching $\varepsilon$ takes about $\dfrac{\ln(e_0/\varepsilon)}{\ln(1/\rho)}$ steps. Each step gains $-\log_{10}\rho$ digits.
• Superlinear: $e_{k+1}/e_k \to 0$. The ratio itself shrinks (quasi-Newton methods such as BFGS, Chapter 3.12, behave like this).
• Quadratic: $e_{k+1} \le C\,e_k^{2}$. The digits double each step. Reaching $\varepsilon$ takes only about $\log_2\log(1/\varepsilon)$ steps once you are close. (In general "order $q$" means $e_{k+1} \le C e_k^{\,q}$.)

The word linear is confusing. It does not mean slow. It comes from the picture: if you plot $\log e_k$ against $k$, geometric decay $e_k = \rho^k e_0$ gives $\log e_k = k\log\rho + \log e_0$, which is a straight line.

We classify functions by how many times you can differentiate them with continuous results:

• $C^0$: continuous (no jumps). $\lvert x\rvert$ and ReLU are $C^0$ and no better.
• $C^1$: continuously differentiable (the gradient exists and is continuous). Huber is $C^1$ but not $C^2$.
• $C^2$: the Hessian exists and is continuous. $C^\infty$: differentiable as many times as you like (polynomials, $e^x$, softplus, $\sin$).

"Smooth" in everyday ML talk means at least $C^1$. In optimization theory it usually means something a little stronger: the gradient is Lipschitz (two sections ahead). Functions with corners are called non-smooth; they need subgradients or proximal methods (Chapter 3.13).

A function $f$ is $G$-Lipschitz (on a set $S$) if for all $\mathbf{x}, \mathbf{y}\in S$

$$\lvert f(\mathbf{x}) - f(\mathbf{y})\rvert \le G\,\|\mathbf{x}-\mathbf{y}\|.$$

The smallest such $G$ is the Lipschitz constant. For a vector-valued function use $\|F(\mathbf{x})-F(\mathbf{y})\|$ on the left.

For differentiable $f$ on a convex set: $f$ is $G$-Lipschitz exactly when $\|\nabla f(\mathbf{x})\| \le G$ everywhere. (Why one direction holds: by the mean value theorem (somewhere between $\mathbf{x}$ and $\mathbf{y}$ the slope along the segment equals the average slope) $f(\mathbf{x})-f(\mathbf{y}) = \nabla f(\mathbf{z})^\top(\mathbf{x}-\mathbf{y})$ for some point $\mathbf{z}$ between them. By the Cauchy–Schwarz inequality $\lvert\mathbf{a}^\top\mathbf{b}\rvert\le\|\mathbf{a}\|\|\mathbf{b}\|$ this is at most $\|\nabla f(\mathbf{z})\|\,\|\mathbf{x}-\mathbf{y}\|$.)

A differentiable function $f$ is $L$-smooth (its gradient is $L$-Lipschitz) if for all $\mathbf{x}, \mathbf{y}$

$$\|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\| \le L\,\|\mathbf{x}-\mathbf{y}\|.$$

(The norm is the usual length.) The consequences you will use:

1. The roof (quadratic upper bound). For all $\mathbf{x},\mathbf{y}$: $$f(\mathbf{y}) \le f(\mathbf{x}) + \nabla f(\mathbf{x})^\top(\mathbf{y}-\mathbf{x}) + \frac{L}{2}\|\mathbf{y}-\mathbf{x}\|^2.$$ Proof. Let $\mathbf{d} = \mathbf{y}-\mathbf{x}$. By the fundamental theorem of calculus along the straight line, $f(\mathbf{y}) - f(\mathbf{x}) = \int_0^1 \nabla f(\mathbf{x}+t\mathbf{d})^\top\mathbf{d}\,dt$. Subtract $\nabla f(\mathbf{x})^\top\mathbf{d} = \int_0^1\nabla f(\mathbf{x})^\top\mathbf{d}\,dt$: $$f(\mathbf{y}) - f(\mathbf{x}) - \nabla f(\mathbf{x})^\top\mathbf{d} = \int_0^1 \big(\nabla f(\mathbf{x}+t\mathbf{d}) - \nabla f(\mathbf{x})\big)^\top\mathbf{d}\,dt \le \int_0^1 \underbrace{L\,t\|\mathbf{d}\|}_{\text{Lipschitz}}\,\|\mathbf{d}\|\,dt = \frac{L}{2}\|\mathbf{d}\|^2.$$ (We used Cauchy–Schwarz for the dot product, then the definition of $L$.) $\blacksquare$ The same argument gives a matching floor $f(\mathbf{y}) \ge f(\mathbf{x}) + \nabla f(\mathbf{x})^\top\mathbf{d} - \frac L2\|\mathbf{d}\|^2$.
2. In terms of the Hessian. If $f$ is twice differentiable, $f$ is $L$-smooth exactly when every Hessian $\nabla^2 f(\mathbf{x})$ has all its eigenvalues between $-L$ and $L$. For a convex function (all eigenvalues $\ge 0$, see Chapter 3.6) this just says $\lambda_{\max}\big(\nabla^2 f(\mathbf{x})\big) \le L$ everywhere: $L$ is the largest curvature the function ever has.
3. Calculation rules. A quadratic $\tfrac12\mathbf{x}^\top A\mathbf{x}$ with $A$ symmetric positive semi-definite has $L = \lambda_{\max}(A)$. Scaling: $cf$ has $|c|L$. Sums: $L_{f+g} \le L_f + L_g$. And a linear map: $\mathbf{w}\mapsto f(X\mathbf{w})$ has $L \le \lambda_{\max}(X^\top X)\,L_f$.

A small $L$ is good news: it means large steps are safe.

Descent lemma. Let $f$ be $L$-smooth and take one gradient step $\mathbf{x}^+ = \mathbf{x} - \eta\nabla f(\mathbf{x})$. Then

$$f(\mathbf{x}^+) \le f(\mathbf{x}) - \eta\Big(1 - \frac{L\eta}{2}\Big)\|\nabla f(\mathbf{x})\|^2.$$

In particular, for every step size $0 \lt \eta \le 1/L$:

$$\boxed{\,f(\mathbf{x}^+) \le f(\mathbf{x}) - \frac{\eta}{2}\,\|\nabla f(\mathbf{x})\|^2\,}$$

Proof. Put $\mathbf{y} = \mathbf{x}^+ = \mathbf{x} - \eta\nabla f(\mathbf{x})$ into the roof inequality, so $\mathbf{y}-\mathbf{x} = -\eta\nabla f(\mathbf{x})$:

$$f(\mathbf{x}^+) \le f(\mathbf{x}) + \nabla f(\mathbf{x})^\top\big(-\eta\nabla f(\mathbf{x})\big) + \frac{L}{2}\eta^2\|\nabla f(\mathbf{x})\|^2 = f(\mathbf{x}) - \eta\|\nabla f(\mathbf{x})\|^2 + \frac{L\eta^2}{2}\|\nabla f(\mathbf{x})\|^2.$$

Factor out $\eta\|\nabla f\|^2$ to get the first formula. If $\eta \le 1/L$ then $1 - L\eta/2 \ge \tfrac12$, which gives the boxed one. $\blacksquare$

• Progress is guaranteed whenever $0 \lt \eta \lt 2/L$, because then $1-L\eta/2 \gt 0$. This is the "$\eta \lt 2/L$" rule you saw for a quadratic in the Calculus guide (curvature and the learning rate), now for any smooth function.
• The guaranteed drop $\eta(1 - L\eta/2)\|\nabla f\|^2$ is largest at $\eta = 1/L$, where it equals $\dfrac{1}{2L}\|\nabla f\|^2$.

Corollary (this holds even for non-convex $f$). Run $K$ steps with $\eta = 1/L$ and add up the drops: $\frac{1}{2L}\sum_{k=0}^{K-1}\|\nabla f(\mathbf{x}_k)\|^2 \le f(\mathbf{x}_0) - f(\mathbf{x}_K) \le f(\mathbf{x}_0) - f^\star$ (the right side telescopes). So the smallest of the $K$ squared gradient norms is at most their average:

$$\min_{0\le k \lt K}\|\nabla f(\mathbf{x}_k)\| \le \sqrt{\frac{2L\,\big(f(\mathbf{x}_0)-f^\star\big)}{K}}.$$

So gradient descent always finds a point with a small gradient, at rate $O(1/\sqrt K)$, as long as $f$ is $L$-smooth and bounded below. Needing $\|\nabla f\|\le\varepsilon$ is guaranteed after at most $2L(f(\mathbf{x}_0)-f^\star)/\varepsilon^2$ steps (for our example, $f(\mathbf{x}_0) = 23.125$ at $(-2.5, 2)$, so $\varepsilon = 0.1$ is guaranteed within $2\cdot10\cdot23.125/0.01 = 46{,}250$ steps; the real run needs far fewer, because this is a worst-case promise).

Theorem (gradient descent on a convex, $L$-smooth function). Let $f$ be convex and $L$-smooth with a minimiser $\mathbf{x}^\star$, and run $\mathbf{x}_{k+1} = \mathbf{x}_k - \eta\nabla f(\mathbf{x}_k)$ with $\eta \le 1/L$. Then for every $K\ge1$

$$\boxed{\,f(\mathbf{x}_K) - f^\star \le \frac{\|\mathbf{x}_0 - \mathbf{x}^\star\|^2}{2\eta K}\,}\qquad\Big(\text{with }\eta = \tfrac1L:\ \ \frac{L\,\|\mathbf{x}_0-\mathbf{x}^\star\|^2}{2K}\Big).$$

So the gap is $O(1/k)$: reaching accuracy $\varepsilon$ needs about $\dfrac{L\|\mathbf{x}_0-\mathbf{x}^\star\|^2}{2\varepsilon}$ steps. This is a sublinear rate.

Proof. Write $\mathbf{g}_k = \nabla f(\mathbf{x}_k)$ and $\mathbf{r}_k = \mathbf{x}_k - \mathbf{x}^\star$. Three facts:

1. Descent lemma: $f(\mathbf{x}_{k+1}) \le f(\mathbf{x}_k) - \frac\eta2\|\mathbf{g}_k\|^2$.
2. Convexity (the tangent lies below the graph, Chapter 3.6): $f^\star \ge f(\mathbf{x}_k) + \mathbf{g}_k^\top(\mathbf{x}^\star - \mathbf{x}_k)$, that is, $f(\mathbf{x}_k) \le f^\star + \mathbf{g}_k^\top\mathbf{r}_k$.
3. Expand the distance: $\|\mathbf{r}_{k+1}\|^2 = \|\mathbf{r}_k - \eta\mathbf{g}_k\|^2 = \|\mathbf{r}_k\|^2 - 2\eta\,\mathbf{g}_k^\top\mathbf{r}_k + \eta^2\|\mathbf{g}_k\|^2$, so $\mathbf{g}_k^\top\mathbf{r}_k = \dfrac{\|\mathbf{r}_k\|^2 - \|\mathbf{r}_{k+1}\|^2}{2\eta} + \dfrac\eta2\|\mathbf{g}_k\|^2$.

Chain them: $f(\mathbf{x}_{k+1}) \le f(\mathbf{x}_k) - \frac\eta2\|\mathbf{g}_k\|^2 \le f^\star + \mathbf{g}_k^\top\mathbf{r}_k - \frac\eta2\|\mathbf{g}_k\|^2 = f^\star + \dfrac{\|\mathbf{r}_k\|^2 - \|\mathbf{r}_{k+1}\|^2}{2\eta}$. The gradient terms cancel! Now add this up for $k = 0, 1, \dots, K-1$; the right side telescopes (each $\|\mathbf{r}_{k+1}\|^2$ cancels against the next term, so only the first and last survive):

$$\sum_{k=0}^{K-1}\big(f(\mathbf{x}_{k+1}) - f^\star\big) \le \frac{\|\mathbf{r}_0\|^2 - \|\mathbf{r}_K\|^2}{2\eta} \le \frac{\|\mathbf{r}_0\|^2}{2\eta}.$$

The descent lemma says $f(\mathbf{x}_k)$ never goes up, so the last term is the smallest of the $K$ terms: $K\,(f(\mathbf{x}_K) - f^\star) \le \sum_{k=0}^{K-1}(f(\mathbf{x}_{k+1}) - f^\star)$. Divide by $K$. $\blacksquare$

Why $1/k$ (a second look). If $a_{k+1} \le a_k - c\,a_k^2$ then $\dfrac{1}{a_{k+1}} \ge \dfrac{1}{a_k(1 - c a_k)} \ge \dfrac{1 + c a_k}{a_k} = \dfrac1{a_k} + c$, so $\dfrac1{a_k} \ge \dfrac1{a_0} + ck$, that is $a_k \le \dfrac{1}{1/a_0 + ck} \le \dfrac{1}{ck}$. For gradient descent the gap $a_k = f(\mathbf{x}_k)-f^\star$ obeys this with $c = \eta/(2R^2)$, where $R = \|\mathbf{x}_0-\mathbf{x}^\star\|$ (the descent lemma gives the drop $\frac\eta2\|\mathbf{g}_k\|^2$, and convexity gives $a_k \le \|\mathbf{g}_k\|\,\|\mathbf{r}_k\|$, where $\|\mathbf{r}_k\| \le R$ because the chain above shows the distance never grows). This quick route gives the weaker constant $2R^2/(\eta k)$; the telescoping proof above is sharper (by a factor 4) but needs a little more work.

A differentiable $f$ is $\mu$-strongly convex ($\mu\gt0$) if for all $\mathbf{x},\mathbf{y}$

$$f(\mathbf{y}) \ge f(\mathbf{x}) + \nabla f(\mathbf{x})^\top(\mathbf{y}-\mathbf{x}) + \frac{\mu}{2}\|\mathbf{y}-\mathbf{x}\|^2.$$

(A floor: the mirror image of the roof.) For twice-differentiable $f$ this says every Hessian eigenvalue is at least $\mu$: $\nabla^2 f \succeq \mu I$. Together with $L$-smoothness: $\mu I \preceq \nabla^2 f \preceq L I$, and $\kappa = L/\mu \ge 1$ is the condition number (conditioning in the Linear Algebra guide). This is only a first look; Chapter 3.6 develops strong convexity fully, with pictures.

A consequence (the Polyak–Łojasiewicz inequality). Minimise the floor over $\mathbf{y}$. Its lowest point is at $\mathbf{y} = \mathbf{x} - \nabla f(\mathbf{x})/\mu$ with height $f(\mathbf{x}) - \frac{1}{2\mu}\|\nabla f(\mathbf{x})\|^2$. Since $f^\star$ is below the floor's lowest point:

$$f^\star \ge f(\mathbf{x}) - \frac{1}{2\mu}\|\nabla f(\mathbf{x})\|^2 \qquad\Longleftrightarrow\qquad \|\nabla f(\mathbf{x})\|^2 \ge 2\mu\,\big(f(\mathbf{x}) - f^\star\big).$$

Theorem (linear rate). Let $f$ be $\mu$-strongly convex and $L$-smooth and take $\eta = 1/L$. Then

$$\boxed{\,f(\mathbf{x}_{k+1}) - f^\star \le \Big(1 - \frac{\mu}{L}\Big)\big(f(\mathbf{x}_k) - f^\star\big)\,}\qquad\text{so}\qquad f(\mathbf{x}_k) - f^\star \le \Big(1-\frac1\kappa\Big)^k\big(f(\mathbf{x}_0) - f^\star\big).$$

Proof. The descent lemma gives $f(\mathbf{x}_{k+1}) \le f(\mathbf{x}_k) - \frac{1}{2L}\|\nabla f(\mathbf{x}_k)\|^2$. Subtract $f^\star$ and use the consequence above: $f(\mathbf{x}_{k+1}) - f^\star \le (f(\mathbf{x}_k) - f^\star) - \frac{1}{2L}\cdot2\mu\,(f(\mathbf{x}_k)-f^\star) = (1 - \mu/L)(f(\mathbf{x}_k) - f^\star)$. $\blacksquare$

• Steps needed. Since $1 - 1/\kappa \le e^{-1/\kappa}$, we get $f(\mathbf{x}_k) - f^\star \le \varepsilon$ once $k \ge \kappa\ln\dfrac{f(\mathbf{x}_0)-f^\star}{\varepsilon}$. The cost grows linearly in $\kappa$ and only logarithmically in $1/\varepsilon$. (For $\kappa = 10$ and a reduction of $10^{-6}$: at most $10\ln10^6 \approx 138$ steps.)
• The distance converges too. At $\mathbf{x}^\star$ the gradient is $\mathbf{0}$, so the floor gives $f(\mathbf{x}) - f^\star \ge \frac\mu2\|\mathbf{x}-\mathbf{x}^\star\|^2$, hence $\|\mathbf{x}_k - \mathbf{x}^\star\|^2 \le \frac2\mu(1-\frac1\kappa)^k(f(\mathbf{x}_0) - f^\star)$.
• Best fixed step for a quadratic: $\eta = \dfrac{2}{L+\mu}$ gives the factor $\dfrac{\kappa-1}{\kappa+1}$ per step on the distance.

The step counts are for a quadratic, shrinking the distance by $10^{-6}$ (computed from $\ln 10^6/\ln(1/\text{factor})$).

Newton's method for minimising $f$ takes the step

$$\mathbf{x}_{k+1} = \mathbf{x}_k - \big[\nabla^2 f(\mathbf{x}_k)\big]^{-1}\nabla f(\mathbf{x}_k),$$

in practice by solving the linear system $\nabla^2 f(\mathbf{x}_k)\,\mathbf{d} = -\nabla f(\mathbf{x}_k)$ for the step $\mathbf{d}$. (It comes from minimising the second-order Taylor model $f(\mathbf{x}+\mathbf{d}) \approx f + \nabla f^\top\mathbf{d} + \tfrac12\mathbf{d}^\top\nabla^2 f\,\mathbf{d}$: set its gradient $\nabla f + \nabla^2 f\,\mathbf{d}$ to zero.)

Local quadratic convergence (one variable). Let $f$ be three times continuously differentiable, with $f'(x^\star) = 0$ and $f''(x^\star)\ne0$. Take $x$ close enough to $x^\star$ that $f''(x)\ne0$. Taylor-expand $f'$ around $x$ and evaluate at $x^\star$, with some point $\xi$ between them:

$$0 = f'(x^\star) = f'(x) + f''(x)\,(x^\star - x) + \tfrac12 f'''(\xi)\,(x^\star - x)^2.$$

Divide by $f''(x)$ and move terms: $\;x - \dfrac{f'(x)}{f''(x)} = x^\star + \dfrac{f'''(\xi)}{2f''(x)}(x - x^\star)^2$. The left side is the Newton step $x^+$, so

$$\boxed{\,x^+ - x^\star = \frac{f'''(\xi)}{2f''(x)}\,(x - x^\star)^2\,}\qquad\Longrightarrow\qquad e_{k+1} \le C\,e_k^2.$$

(In the example, $f''' = f'' = e^x$, so $C \approx \tfrac12$, matching the table.)

Many variables (stated without the full proof; it is the same Taylor idea, with the Lipschitz constant of the Hessian playing the role of $f'''$). Suppose that in a ball around $\mathbf{x}^\star$ the Hessian is $M$-Lipschitz (it changes by at most $M\|\mathbf{x}-\mathbf{y}\|$) and $\nabla^2 f \succeq \mu I$. Then for every $\mathbf{x}$ in that ball, $\|\mathbf{x}^+ - \mathbf{x}^\star\| \le \dfrac{M}{2\mu}\|\mathbf{x}-\mathbf{x}^\star\|^2$. This needs the start to be close enough (within about $2\mu/M$) for the squared error to be smaller than the error. On a quadratic function $M = 0$: the Hessian is constant, and Newton lands exactly in one step.

The price. Each step needs the $n\times n$ Hessian ($n^2$ numbers) and a linear solve (about $n^3$ operations). For a network with millions of weights that is impossible, which is why quasi-Newton methods (BFGS, L-BFGS, Chapter 3.12) approximate it. Far from the solution, or where the Hessian is not positive definite, pure Newton can also go badly wrong.

At a minimiser of a differentiable function, $\nabla f(\mathbf{x}^\star) = \mathbf{0}$. Away from it, the gradient norm is linked to the two other yardsticks:

• Lower bound on the gap (needs only $L$-smoothness): $f(\mathbf{x}) - f^\star \ge \dfrac{1}{2L}\|\nabla f(\mathbf{x})\|^2$. Proof: $f^\star \le f(\mathbf{x} - \tfrac1L\nabla f) \le f(\mathbf{x}) - \tfrac1{2L}\|\nabla f\|^2$ by the descent lemma.
• Upper bound on the gap (needs $\mu$-strong convexity): $f(\mathbf{x}) - f^\star \le \dfrac{1}{2\mu}\|\nabla f(\mathbf{x})\|^2$ (shown in the previous section).
• Bound on the distance ($\mu$-strong convexity): $\|\mathbf{x}-\mathbf{x}^\star\| \le \dfrac{1}{\mu}\|\nabla f(\mathbf{x})\|$. Proof: write the floor inequality at $\mathbf{x}$ looking at $\mathbf{x}^\star$, and at $\mathbf{x}^\star$ looking at $\mathbf{x}$, and add them: $0 \ge \nabla f(\mathbf{x})^\top(\mathbf{x}^\star-\mathbf{x}) + \mu\|\mathbf{x}-\mathbf{x}^\star\|^2$ (the gradient at $\mathbf{x}^\star$ is zero). So $\mu\|\mathbf{x}-\mathbf{x}^\star\|^2 \le \nabla f(\mathbf{x})^\top(\mathbf{x}-\mathbf{x}^\star) \le \|\nabla f(\mathbf{x})\|\,\|\mathbf{x}-\mathbf{x}^\star\|$. Divide.

$$\frac{\|\nabla f(\mathbf{x})\|^2}{2L} \;\le\; f(\mathbf{x}) - f^\star \;\le\; \frac{\|\nabla f(\mathbf{x})\|^2}{2\mu}.$$

So a small gradient means a small gap only when $\mu$ is not tiny. And for a non-convex function a small gradient only says "this is near some stationary point": a local minimum, a maximum or a saddle.

Scale. Multiply $f$ by $1000$ and every gradient is $1000$ times larger. So the absolute tolerance "$\|\nabla f\| \le 10^{-6}$" means different things for different problems. Many solvers use the relative test $\|\nabla f(\mathbf{x}_k)\| \le \varepsilon\,\|\nabla f(\mathbf{x}_0)\|$.

With a tolerance $\varepsilon$ (see the next section), the common rules are:

Trade-offs. A tight tolerance gives accuracy but costs steps (and may be impossible because of rounding). A loose one is cheap but may stop too early. Combining a gradient test with a budget is the usual safe choice. In machine learning there is one more rule, early stopping: stop when the validation loss stops improving. That is about generalisation, not about optimisation, and it can fire long before any of the rules above.

A point $\mathbf{x}$ is an $\varepsilon$-optimal solution if $f(\mathbf{x}) - f^\star \le \varepsilon$. It is an $\varepsilon$-stationary point if $\|\nabla f(\mathbf{x})\| \le \varepsilon$ (the usual goal for non-convex problems, where a global optimum is out of reach).

• Absolute vs relative tolerance. An absolute test "$\text{quantity} \le \varepsilon$" depends on units. A relative test "$\text{quantity} \le \varepsilon\,(\text{scale})$" does not. Libraries often combine them: $\le \varepsilon_{\text{abs}} + \varepsilon_{\text{rel}}\cdot|\text{value}|$.
• The floating-point floor. Computers keep about 16 significant digits (machine epsilon $\approx 2.2\cdot10^{-16}$, see Numerical Linear Algebra). Near a minimum $f(\mathbf{x}^\star + \boldsymbol\delta) - f^\star \approx \tfrac12\boldsymbol\delta^\top H\boldsymbol\delta$, which is smaller than $10^{-16}|f|$ once $\|\boldsymbol\delta\| \lesssim \sqrt{10^{-16}}= 10^{-8}$. So by comparing function values you cannot locate a minimiser better than about 8 digits. Gradients can be used a little further, but a tolerance below about $10^{-12}$ is rarely meaningful.
• The statistical floor. In machine learning the loss itself is measured on a finite, noisy data set. Solving the training problem more accurately than the noise in the data justifies buys nothing (and an over-trained model can generalise worse). This is one reason why tolerances around $10^{-4}$ are common defaults.

A set $C\subseteq\mathbb{R}^n$ is convex if for all $\mathbf{x},\mathbf{y}\in C$ and every $\theta\in[0,1]$,

$$\theta\,\mathbf{x} + (1-\theta)\,\mathbf{y} \in C.$$

The points $\theta\mathbf{x}+(1-\theta)\mathbf{y}$, for $\theta$ from $1$ to $0$, are exactly the straight segment from $\mathbf{y}$ to $\mathbf{x}$ ($\theta=1$ gives $\mathbf{x}$, $\theta = 0$ gives $\mathbf{y}$, $\theta=\tfrac12$ gives the midpoint). So convex means "the segment between any two points of the set stays in the set".

Why the main examples are convex.

• Half-space $\{\mathbf{x}: \mathbf{a}^\top\mathbf{x}\le b\}$: if $\mathbf{a}^\top\mathbf{x}\le b$ and $\mathbf{a}^\top\mathbf{y}\le b$ then $\mathbf{a}^\top(\theta\mathbf{x}+(1-\theta)\mathbf{y}) = \theta\,\mathbf{a}^\top\mathbf{x}+(1-\theta)\,\mathbf{a}^\top\mathbf{y} \le \theta b+(1-\theta)b = b$.
• Ball $\|\mathbf{x}-\mathbf{c}\|\le r$: by the triangle inequality, $\|\theta\mathbf{x}+(1-\theta)\mathbf{y}-\mathbf{c}\| = \|\theta(\mathbf{x}-\mathbf{c})+(1-\theta)(\mathbf{y}-\mathbf{c})\| \le \theta\|\mathbf{x}-\mathbf{c}\| + (1-\theta)\|\mathbf{y}-\mathbf{c}\|\le r$. (This works for every norm: the L1 diamond and the L-infinity square are convex too.)
• Intersection $C_1\cap C_2$: if $\mathbf{x},\mathbf{y}$ lie in both sets, the segment between them lies in $C_1$ (it is convex) and in $C_2$, so in the intersection. The same holds for any number of sets.

Let $C$ be a convex set. A function $f: C \to \mathbb{R}$ is convex if for all $\mathbf{x},\mathbf{y}\in C$ and every $\theta\in[0,1]$,

$$f\big(\theta\mathbf{x} + (1-\theta)\mathbf{y}\big) \;\le\; \theta f(\mathbf{x}) + (1-\theta) f(\mathbf{y}).$$

Left side: the height of the graph above the point between $\mathbf{x}$ and $\mathbf{y}$. Right side: the height of the string (the chord) above the same point.

Epigraph (awareness). The epigraph of $f$ is the set $\text{epi}\,f = \{(\mathbf{x}, t) : t \ge f(\mathbf{x})\}$, everything on or above the graph. $f$ is convex exactly when $\text{epi}\,f$ is a convex set. Reason: the string between two graph points $(\mathbf{x},f(\mathbf{x}))$ and $(\mathbf{y},f(\mathbf{y}))$ is the set of points $\big(\theta\mathbf{x}+(1-\theta)\mathbf{y},\ \theta f(\mathbf{x})+(1-\theta)f(\mathbf{y})\big)$, and "this point is in the epigraph" says exactly "$\theta f(\mathbf{x})+(1-\theta)f(\mathbf{y}) \ge f(\theta\mathbf{x}+(1-\theta)\mathbf{y})$". This is why convex functions and convex sets are one idea. A useful consequence: every sublevel set $\{\mathbf{x}: f(\mathbf{x})\le c\}$ of a convex function is a convex set (a bowl cut at any height is a convex region).

Convex functions need not be smooth: $\lvert x\rvert$ and $\max(0,x)$ are convex with corners.

A convex function $f$ is strictly convex if for all $\mathbf{x}\ne\mathbf{y}$ and every $\theta\in(0,1)$ (strictly between $0$ and $1$)

$$f\big(\theta\mathbf{x} + (1-\theta)\mathbf{y}\big) \;\lt\; \theta f(\mathbf{x}) + (1-\theta) f(\mathbf{y}).$$

Consequence: at most one minimiser. Suppose $\mathbf{x}\ne\mathbf{y}$ both minimise $f$, with the same value $m$. Then at the midpoint $f\big(\tfrac{\mathbf{x}+\mathbf{y}}{2}\big) \lt \tfrac12 m + \tfrac12 m = m$, which is lower than the minimum: a contradiction. So the minimiser, if it exists, is unique.

Strict convexity does not guarantee that a minimiser exists: $e^x$ is strictly convex, decreases toward $0$ as $x\to-\infty$, and never reaches it. (Also, "strictly convex" is stronger than "convex" but weaker than "strongly convex", next.)

A differentiable $f$ is $\mu$-strongly convex ($\mu \gt 0$) if for all $\mathbf{x},\mathbf{y}$

$$f(\mathbf{y}) \;\ge\; f(\mathbf{x}) + \nabla f(\mathbf{x})^\top(\mathbf{y}-\mathbf{x}) + \frac{\mu}{2}\|\mathbf{y}-\mathbf{x}\|^2.$$

Equivalent forms: (i) the chord version $f(\theta\mathbf{x}+(1-\theta)\mathbf{y}) \le \theta f(\mathbf{x})+(1-\theta)f(\mathbf{y}) - \frac\mu2\theta(1-\theta)\|\mathbf{x}-\mathbf{y}\|^2$; (ii) $f(\mathbf{x}) - \frac\mu2\|\mathbf{x}\|^2$ is still convex; (iii) if $f$ is twice differentiable, $\nabla^2 f(\mathbf{x}) \succeq \mu I$ for all $\mathbf{x}$, that is, every Hessian eigenvalue is at least $\mu$ (positive definiteness with a margin).

What it gives you.

• A unique minimiser exists. The floor parabola grows to $+\infty$ in every direction, so $f$ does too. A continuous function that tends to infinity at infinity has a minimum. And strong convexity implies strict convexity, so the minimiser is unique.
• Close in value means close in position. At $\mathbf{x}^\star$ the gradient is zero, so $f(\mathbf{x}) - f^\star \ge \tfrac\mu2\|\mathbf{x}-\mathbf{x}^\star\|^2$.
• The linear rate of Chapter 3.5. With $L$-smoothness too, gradient descent with $\eta=1/L$ satisfies $f(\mathbf{x}_k)-f^\star \le (1-\mu/L)^k\,(f(\mathbf{x}_0)-f^\star)$ (proved there). The ratio $\kappa = L/\mu \ge 1$ is the condition number: $\kappa=1$ is a perfectly round bowl, a large $\kappa$ is a long thin valley.

A function $f$ is concave if $-f$ is convex, that is, for all $\mathbf{x},\mathbf{y}$ and $\theta\in[0,1]$

$$f\big(\theta\mathbf{x} + (1-\theta)\mathbf{y}\big) \;\ge\; \theta f(\mathbf{x}) + (1-\theta) f(\mathbf{y}).$$

Everything flips: the chord is below the graph, the tangent line lies above the graph, a stationary point is a global maximum, and the Hessian is negative semi-definite ($\preceq 0$).

The standard translation. $\max_{\mathbf{x}} f(\mathbf{x})$ with $f$ concave $\;\Longleftrightarrow\;$ $\min_{\mathbf{x}}\,(-f(\mathbf{x}))$ with $-f$ convex. Same optimiser, and the optimal values differ only by a sign. A convex optimization problem is therefore "minimise a convex function" or equally "maximise a concave function", over a convex set.

Jensen's inequality. Let $f$ be convex and $X$ a random variable (or a list of values $x_i$ with probabilities $p_i \ge 0$, $\sum p_i = 1$). Then

$$f\big(\mathbb{E}[X]\big) \le \mathbb{E}\big[f(X)\big], \qquad\text{that is}\qquad f\Big(\sum_i p_i x_i\Big) \le \sum_i p_i f(x_i).$$

For a concave $f$ the inequality reverses: $f(\mathbb{E}[X]) \ge \mathbb{E}[f(X)]$. For a strictly convex $f$, equality holds only when $X$ is constant.

Proof (using the tangent line; it is proved in the section on the first-order test). Let $m = \mathbb{E}[X]$ and let $g$ be the slope of $f$ at $m$ (at a corner, take the slope of any supporting line). A convex function lies above its tangent line, so $f(x) \ge f(m) + g\,(x - m)$ for every $x$. Take the expectation of both sides: $\mathbb{E}[f(X)] \ge f(m) + g\,(\mathbb{E}[X] - m) = f(m) + 0 = f(m)$. $\blacksquare$ (With two points and $p_1 = \theta$, Jensen is exactly the definition of convexity; for more points it follows by induction.)

Four standard uses.

1. Variance is non-negative. With $f(x) = x^2$: $\mathbb{E}[X^2] \ge (\mathbb{E}[X])^2$. The gap is $\text{Var}(X)$.
2. AM–GM. $\ln$ is concave, so $\ln\!\big(\tfrac{x_1+\dots+x_n}{n}\big) \ge \tfrac1n\sum\ln x_i = \ln\big((x_1\cdots x_n)^{1/n}\big)$: the arithmetic mean is at least the geometric mean.
3. KL divergence is non-negative. For distributions $p, q$: $\text{KL}(p\|q) = \sum_i p_i\ln\frac{p_i}{q_i} = -\sum_i p_i\ln\frac{q_i}{p_i} \ge -\ln\sum_i p_i\frac{q_i}{p_i} = -\ln\sum_i q_i = -\ln 1 = 0$ (we used Jensen for the concave $\ln$ with weights $p_i$). Equality only when $q = p$. Consequently the cross-entropy $H(p,q) = -\sum p_i\ln q_i = H(p) + \text{KL}(p\|q)$ is smallest exactly when $q = p$: this is why training with cross-entropy pushes predicted probabilities toward the true ones.
4. The log-likelihood bound (ELBO). If a model has hidden variables $z$, then $\ln p(x) = \ln\sum_z q(z)\frac{p(x,z)}{q(z)} \ge \sum_z q(z)\ln\frac{p(x,z)}{q(z)}$ (Jensen again). The right side is the lower bound that the EM algorithm and variational autoencoders maximise instead of the hard log of a sum.

A differentiable function $f$ (on a convex set) is convex if and only if for all $\mathbf{x},\mathbf{y}$

$$\boxed{\,f(\mathbf{y}) \;\ge\; f(\mathbf{x}) + \nabla f(\mathbf{x})^\top(\mathbf{y}-\mathbf{x})\,}$$

The right side is the first-order Taylor approximation (the tangent line or tangent plane) at $\mathbf{x}$. Convexity says it never over-estimates $f$. Strict inequality for $\mathbf{y}\ne\mathbf{x}$ means strictly convex; adding $+\frac\mu2\|\mathbf{y}-\mathbf{x}\|^2$ on the right means $\mu$-strongly convex.

Proof (convex $\Rightarrow$ tangent below). Put $\mathbf{d} = \mathbf{y}-\mathbf{x}$ and use convexity with a small weight $\theta$ on $\mathbf{y}$: $f(\mathbf{x}+\theta\mathbf{d}) \le (1-\theta)f(\mathbf{x}) + \theta f(\mathbf{y})$. Move $f(\mathbf{x})$ to the left and divide by $\theta$: $\dfrac{f(\mathbf{x}+\theta\mathbf{d}) - f(\mathbf{x})}{\theta} \le f(\mathbf{y}) - f(\mathbf{x})$. As $\theta\to0$ the left side tends to the directional derivative $\nabla f(\mathbf{x})^\top\mathbf{d}$. So $\nabla f(\mathbf{x})^\top\mathbf{d}\le f(\mathbf{y}) - f(\mathbf{x})$. $\blacksquare$

Proof (tangent below $\Rightarrow$ convex). Let $\mathbf{z} = \theta\mathbf{x}+(1-\theta)\mathbf{y}$. Apply the tangent inequality at $\mathbf{z}$ twice: $f(\mathbf{x}) \ge f(\mathbf{z}) + \nabla f(\mathbf{z})^\top(\mathbf{x}-\mathbf{z})$ and $f(\mathbf{y}) \ge f(\mathbf{z}) + \nabla f(\mathbf{z})^\top(\mathbf{y}-\mathbf{z})$. Multiply the first by $\theta$ and the second by $1-\theta$ and add. Since $\theta(\mathbf{x}-\mathbf{z}) + (1-\theta)(\mathbf{y}-\mathbf{z}) = \mathbf{0}$, the gradient terms cancel: $\theta f(\mathbf{x}) + (1-\theta)f(\mathbf{y}) \ge f(\mathbf{z})$. $\blacksquare$

The big consequence. If $\nabla f(\mathbf{x}^\star) = \mathbf{0}$ then the inequality gives $f(\mathbf{y}) \ge f(\mathbf{x}^\star) + \mathbf{0}^\top(\mathbf{y} - \mathbf{x}^\star) = f(\mathbf{x}^\star)$ for every $\mathbf{y}$. So for a differentiable convex function, a point is a global minimiser if and only if its gradient is zero. No second-derivative test is needed, and no distinction between local and global.

Let $f$ be twice differentiable on an open convex set. Then

$$f \text{ is convex} \iff \nabla^2 f(\mathbf{x}) \succeq 0 \ \text{ for every } \mathbf{x}.$$

"$\succeq 0$" means positive semi-definite: $\mathbf{v}^\top\nabla^2 f(\mathbf{x})\,\mathbf{v}\ge0$ for every direction $\mathbf{v}$, equivalently all eigenvalues $\ge 0$. In one variable this is just $f''(x)\ge0$.

• $\nabla^2 f(\mathbf{x}) \succ 0$ (all eigenvalues $\gt0$) everywhere $\Rightarrow$ strictly convex. (Not "if and only if": $x^4$ is strictly convex but $f''(0) = 0$.)
• $\nabla^2 f \succeq \mu I$ $\iff$ $\mu$-strongly convex. And $0 \preceq \nabla^2 f \preceq LI$ means convex and $L$-smooth (Chapter 3.5).

Why it works. In one variable: $f''\ge0$ means $f'$ is non-decreasing, so $f(y) - f(x) - f'(x)(y-x) = \int_x^y \big(f'(t) - f'(x)\big)\,dt \ge 0$, which is the tangent test. In many variables, restrict $f$ to a line: $g(t) = f(\mathbf{x}+t\mathbf{v})$. Then $g''(t) = \mathbf{v}^\top\nabla^2 f(\mathbf{x}+t\mathbf{v})\,\mathbf{v}$. A function is convex exactly when it is convex along every line, so we need $g''\ge0$ for every point and every direction $\mathbf{v}$: that is the definition of positive semi-definite.

Three important ML cases.

• Quadratic $\frac12\mathbf{x}^\top A\mathbf{x} + \mathbf{b}^\top\mathbf{x} + c$ ($A$ symmetric): the Hessian is the constant $A$, so it is convex iff $A\succeq0$.
• Least squares $\frac{1}{2n}\|X\mathbf{w}-\mathbf{y}\|^2$: Hessian $X^\top X/n$, and $\mathbf{v}^\top X^\top X\mathbf{v} = \|X\mathbf{v}\|^2\ge0$ for every $\mathbf{v}$. Always convex.
• Logistic loss: Hessian $\frac1n X^\top D X$ with $D = \text{diag}\big(\sigma_i(1-\sigma_i)\big)$, where each $\sigma_i(1-\sigma_i)\in(0,\tfrac14]$. Then $\mathbf{v}^\top X^\top DX\mathbf{v} = \sum_i D_{ii}(\mathbf{x}_i^\top\mathbf{v})^2\ge0$. Always convex.

A point $\mathbf{x}^\star$ is a local minimiser of $f$ over a feasible set $C$ if there is a radius $r\gt0$ such that $f(\mathbf{x}^\star)\le f(\mathbf{x})$ for every feasible $\mathbf{x}$ with $\|\mathbf{x}-\mathbf{x}^\star\|\le r$. It is a global minimiser if $f(\mathbf{x}^\star)\le f(\mathbf{x})$ for every feasible $\mathbf{x}$.

Theorem. Let $f$ be convex and $C$ a convex set. Then every local minimiser of $f$ over $C$ is a global minimiser.

Proof (by contradiction). Let $\mathbf{x}$ be a local minimiser, with radius $r$, and suppose some feasible $\mathbf{y}$ has $f(\mathbf{y}) \lt f(\mathbf{x})$.

1. For $\theta\in(0,1]$ let $\mathbf{z}_\theta = (1-\theta)\mathbf{x} + \theta\mathbf{y}$. It is feasible because $C$ is convex (the segment stays in $C$).
2. By convexity of $f$: $f(\mathbf{z}_\theta) \le (1-\theta)f(\mathbf{x}) + \theta f(\mathbf{y}) = f(\mathbf{x}) - \theta\big(f(\mathbf{x}) - f(\mathbf{y})\big) \lt f(\mathbf{x})$, because $f(\mathbf{x})-f(\mathbf{y})\gt 0$ and $\theta\gt0$.
3. The point $\mathbf{z}_\theta$ is at distance $\|\mathbf{z}_\theta - \mathbf{x}\| = \theta\|\mathbf{y}-\mathbf{x}\|$ from $\mathbf{x}$. Choose $\theta$ so small that this is at most $r$.
4. Then $\mathbf{z}_\theta$ is feasible, within the radius $r$ of $\mathbf{x}$, and strictly lower than $\mathbf{x}$: this contradicts "$\mathbf{x}$ is a local minimiser". So no such $\mathbf{y}$ exists. $\blacksquare$

Two companions. (1) The set of global minimisers is convex: if $\mathbf{x},\mathbf{y}$ both have the minimum value $m$ then every point between them has value $\le m$ by convexity, hence exactly $m$. (2) If $f$ is strictly convex the global minimiser is unique (previous sections).

What it needs. Both ingredients: a convex function and a convex feasible set (step 1 uses the set). With a non-convex constraint set, even a convex objective can have bad local minima: minimising $x^2$ over the two intervals $[-3,-2]\cup[1,2]$ has a local minimum at $x = -2$ (value 4) that is not global (the global one is $x=1$, value 1).

Compared with a general optimization problem, a convex problem (a convex function over a convex set) gives you:

1. Local $=$ global. Any local minimum is a global one (the previous section).
2. Optimality is checkable. For a differentiable convex $f$ (unconstrained), $\nabla f(\mathbf{x}^\star)=\mathbf{0}$ if and only if $\mathbf{x}^\star$ is a global minimiser. With constraints the condition becomes $\nabla f(\mathbf{x}^\star)^\top(\mathbf{y}-\mathbf{x}^\star)\ge0$ for every feasible $\mathbf{y}$ (you will see it as the KKT conditions in Chapter 3.9, which are necessary and sufficient for convex problems under mild conditions).
3. Any sensible descent method works, from any starting point: gradient descent, momentum, Newton, quasi-Newton, coordinate descent, ... with suitable step sizes they converge to the global optimum (for smooth convex problems; a method must also suit the problem, for example coordinate descent can stall on non-smooth ones). No restarts, no clever initialisation.
4. You know how fast. The rates of Chapter 3.5 are guarantees: $O(1/k)$ for convex $L$-smooth, linear for strongly convex.
5. Duality works well (Chapter 3.10). Tangent planes lie below the graph, and duality turns such lower bounds into a computable lower bound on the optimal value. For convex problems the best lower bound usually matches the optimum (strong duality). So a solver can certify "I am within $10^{-6}$ of the true optimum".
6. The solution set is nice: convex, and a single point when strictly convex.
7. Efficient algorithms exist: for the standard classes (linear, quadratic, second-order-cone and semidefinite programs) interior-point methods find an $\varepsilon$-accurate global solution in polynomial time.

Operations that preserve convexity (each one with its one-line reason):

1. Non-negative combinations. If $f_1,\dots,f_m$ are convex and $a_i\ge0$, then $\sum a_if_i$ is convex. Why: multiply each chord inequality by $a_i\ge0$ (the direction is kept) and add them.
2. Affine substitution. If $f$ is convex then $g(\mathbf{x}) = f(A\mathbf{x}+\mathbf{b})$ is convex. Why: $A(\theta\mathbf{x}+(1-\theta)\mathbf{y})+\mathbf{b} = \theta(A\mathbf{x}+\mathbf{b}) + (1-\theta)(A\mathbf{y}+\mathbf{b})$, so $g$'s chord test is $f$'s chord test at the transformed points.
3. Pointwise maximum. $\max(f_1,\dots,f_m)$ is convex. Why: $f_i(\theta\mathbf{x}+(1-\theta)\mathbf{y}) \le \theta f_i(\mathbf{x}) + (1-\theta)f_i(\mathbf{y}) \le \theta\max_j f_j(\mathbf{x}) + (1-\theta)\max_jf_j(\mathbf{y})$ for every $i$; take the max over $i$ on the left.
4. Composition rule. $g(h(\mathbf{x}))$ is convex if $h$ is convex and $g$ is convex and non-decreasing (for example $e^{h(\mathbf{x})}$, or $h(\mathbf{x})^2$ when $h\ge0$). Why (smooth one-variable case): $(g\circ h)'' = g''(h)\,h'^2 + g'(h)\,h''\ge0$ since $g''\ge0$, $g'\ge0$ and $h''\ge0$.

Standard bricks: affine functions; $x^2$ and $\|\mathbf{x}\|^2$; every norm (L1, L2, L-infinity) and $\|A\mathbf{x}-\mathbf{b}\|$; $\lvert x\rvert$, $\max(0,x)$; $e^x$; $-\ln x$ (for $x\gt0$); $x\ln x$; the softplus; the log-sum-exp $\ln\sum_i e^{x_i}$; and $\mathbf{x}^\top A\mathbf{x}$ with $A\succeq0$.

A convex optimization problem has the form

$$\min_{\mathbf{x}}\ f_0(\mathbf{x}) \quad\text{subject to}\quad f_i(\mathbf{x}) \le 0\ \ (i=1,\dots,m),\qquad A\mathbf{x}=\mathbf{b},$$

with $f_0$ and every $f_i$ convex, and only affine equality constraints. Then the feasible set is convex (an intersection of sublevel sets of convex functions and flat sets) and the objective is convex over it. (In Chapter 3.7 we will write these constraints as $g_i(\mathbf{x})\le0$ and $h_j(\mathbf{x}) = 0$.) A constraint such as $\|\mathbf{x}\|_2 = 1$ (a sphere, not a ball) is not affine and makes the problem non-convex.

Nuances (please keep them in mind).

• Non-convex problems can still be tamed. Matrix factorisation is convex in each factor when the other is fixed (alternating least squares exploits that). The last layer of a network, given fixed features, is just logistic or softmax regression: convex. Some non-convex problems (for example PCA, and certain factorisation problems under assumptions) have been proved to have no bad local minima.
• For deep networks there is no general guarantee. That training works well in practice is an empirical fact with partial explanations (over-parameterisation, benign-looking landscapes in experiments), not a theorem for arbitrary networks. Do not read "SGD finds flat minima" or "all local minima are good" as established laws.
• Convex relaxations trade exactness for tractability: the L1 norm replaces the count of non-zeros, giving the Lasso.

The standard form of a constrained optimization problem, for $\mathbf{x}\in\mathbb{R}^n$:

$$\min_{\mathbf{x}}\; f(\mathbf{x}) \quad \text{subject to} \quad g_i(\mathbf{x}) \le 0 \;\; (i = 1,\dots,m), \qquad h_j(\mathbf{x}) = 0 \;\; (j = 1,\dots,p).$$

• $f$ is the objective. Each $g_i(\mathbf{x}) \le 0$ is an inequality constraint ($m$ of them). Each $h_j(\mathbf{x}) = 0$ is an equality constraint ($p$ of them).
• How to convert: "maximise $f$" becomes "minimise $-f$". "$g(\mathbf{x}) \ge 0$" becomes "$-g(\mathbf{x}) \le 0$". "$h(\mathbf{x}) = c$" becomes "$h(\mathbf{x}) - c = 0$". "$a \le g(\mathbf{x}) \le b$" becomes two constraints, $a - g \le 0$ and $g - b \le 0$.

An equality constraint is a condition $h(\mathbf{x}) = 0$. The set of points that satisfy $p$ independent equality constraints in $\mathbb{R}^n$ is typically a surface with $n - p$ free directions (a curve for $n=2,\,p=1$; a surface for $n=3,\,p=1$; a curve for $n=3,\,p=2$).

If an equality constraint can be solved for one variable, substitution turns the problem into an unconstrained one in fewer variables. When it cannot be solved by hand, we need a more general tool: Lagrange multipliers.

An inequality constraint is a condition $g(\mathbf{x}) \le 0$. It splits the space into the allowed side ($g \le 0$), the wall ($g = 0$) and the forbidden side ($g \gt 0$).

At a point, the constraint is inactive if $g(\mathbf{x}) \lt 0$ (strictly inside, room to move) and active if $g(\mathbf{x}) = 0$ (touching the wall). You will use these two words constantly in the next chapters.

The feasible set (feasible region) is $$\mathcal{F} = \{\mathbf{x} : g_i(\mathbf{x}) \le 0 \text{ for all } i, \;\; h_j(\mathbf{x}) = 0 \text{ for all } j\}.$$ A feasible point is any $\mathbf{x}\in\mathcal{F}$. An optimal point $\mathbf{x}^\star$ is a feasible point with the smallest $f$ among all feasible points, and $p^\star = f(\mathbf{x}^\star)$.

• At a feasible point, the constraint $g_i$ is active if $g_i(\mathbf{x}) = 0$ and inactive if $g_i(\mathbf{x}) \lt 0$. Equality constraints are always active.
• A point where every inequality is inactive is an interior point (ignoring equalities). A feasible point with at least one active inequality is on the boundary.
• If the $g_i$ are convex functions and the $h_j$ are linear ("affine"), then $\mathcal{F}$ is a convex set (Chapter 3.6). Convex feasible regions make life much easier.
• Two warnings: $\mathcal{F}$ can be empty ($x \ge 2$ and $x \le 1$: the problem is infeasible), and a nonempty $\mathcal{F}$ can still have no best point (for example "minimise $x$ subject to $x \gt 0$" has no smallest value; the objective can get arbitrarily close to $0$ but never reach it).

Facts. Let $\mathcal{F}$ be the feasible set and $f_{\text{free}} = \min_{\mathbf{x}} f$ the unconstrained minimum value.

• $p^\star \ge f_{\text{free}}$: constraints can only make the best value worse or equal. Equality holds exactly when a free minimiser lies in $\mathcal{F}$.
• If $f$ is convex and no free minimiser is feasible, a constrained minimiser lies on the boundary of $\mathcal{F}$. (If it were strictly inside, nothing nearby would block it, so it would also be a free local minimum with $\nabla f = \mathbf{0}$, and for a convex $f$ that makes it a free global minimum: forbidden.)
• At a boundary optimum, $\nabla f(\mathbf{x}^\star) \ne \mathbf{0}$ in general. Instead, $-\nabla f$ ("downhill") points out of the region, along the wall's outward normal. The wall holds you back, and the strength of that hold is the multiplier you meet next.

A Lagrange multiplier $\lambda_j$ is a number attached to the equality constraint $h_j(\mathbf{x}) = 0$. At a (regular) constrained optimum $\mathbf{x}^\star$ there are numbers $\lambda_j$ with

$$\nabla f(\mathbf{x}^\star) + \sum_{j=1}^{p}\lambda_j\,\nabla h_j(\mathbf{x}^\star) = \mathbf{0}, \qquad h_j(\mathbf{x}^\star) = 0.$$

That is $n + p$ equations for the $n + p$ unknowns $(\mathbf{x},\boldsymbol\lambda)$. A multiplier can be positive, negative or zero. It also measures sensitivity: it tells how fast the optimal value changes if the constraint is loosened (Chapters 3.8 and 3.10 develop this). The equality case is derived properly in Chapter 3.8; inequalities get multipliers $\mu_i \ge 0$ in Chapter 3.9.

The Lagrangian of $\min f$ s.t. $g_i \le 0,\; h_j = 0$ is

$$L(\mathbf{x},\boldsymbol\lambda,\boldsymbol\mu) = f(\mathbf{x}) + \sum_{j=1}^{p}\lambda_j\,h_j(\mathbf{x}) + \sum_{i=1}^{m}\mu_i\,g_i(\mathbf{x}), \qquad \mu_i \ge 0.$$

• For a feasible $\mathbf{x}$ and any $\mu_i \ge 0$: $L(\mathbf{x},\boldsymbol\lambda,\boldsymbol\mu) \le f(\mathbf{x})$, because $h_j = 0$ and $\mu_i g_i \le 0$.
• The key identity: $\displaystyle\max_{\boldsymbol\lambda,\;\boldsymbol\mu\ge 0} L(\mathbf{x},\boldsymbol\lambda,\boldsymbol\mu) = \begin{cases} f(\mathbf{x}) & \mathbf{x}\text{ feasible},\\ +\infty & \text{otherwise.}\end{cases}$ (If a rule is broken, push its multiplier to infinity and $L$ blows up.) So the original problem equals $\displaystyle\min_{\mathbf{x}}\max_{\boldsymbol\lambda,\,\boldsymbol\mu\ge 0} L$.
• The derivative of $L$ with respect to a multiplier recovers the constraint: $\partial L/\partial\lambda_j = h_j(\mathbf{x})$.

For $\min f(\mathbf{x})$ s.t. $g_i(\mathbf{x}) \le 0$, $h_j(\mathbf{x}) = 0$, a point $\mathbf{x}^\star$ with multipliers $(\boldsymbol\lambda,\boldsymbol\mu)$ satisfies the KKT conditions if:

What they promise. (a) If $\mathbf{x}^\star$ is a local minimum and a constraint qualification holds (below), then multipliers exist and KKT holds. (b) If the problem is convex ($f$ and $g_i$ convex, $h_j$ affine), then any point satisfying KKT is a global minimum. So for convex problems KKT is a complete test. Chapter 3.9 studies each condition in depth.

Primal problem: $p^\star = \min_{\mathbf{x}} f(\mathbf{x})$ subject to $g_i(\mathbf{x}) \le 0$, $h_j(\mathbf{x}) = 0$.

Dual function (for $\boldsymbol\mu \ge 0$ and any $\boldsymbol\lambda$): $\;d(\boldsymbol\lambda,\boldsymbol\mu) = \displaystyle\min_{\mathbf{x}}\; L(\mathbf{x},\boldsymbol\lambda,\boldsymbol\mu)$ (more precisely the infimum, which may be $-\infty$).

Dual problem: $d^\star = \displaystyle\max_{\boldsymbol\lambda,\;\boldsymbol\mu \ge 0}\; d(\boldsymbol\lambda,\boldsymbol\mu)$.

Fact: $d$ is always concave (an upside-down convex function, Chapter 3.6; it is a minimum of functions that are linear in $(\boldsymbol\lambda,\boldsymbol\mu)$), so the dual problem is always a convex problem, even when the primal is not. The primal is "min over $\mathbf{x}$ of max over prices"; the dual swaps the order: "max over prices of min over $\mathbf{x}$". Details in Chapter 3.10.

Weak duality. For every $\boldsymbol\lambda$ and every $\boldsymbol\mu \ge 0$: $\;d(\boldsymbol\lambda,\boldsymbol\mu) \le p^\star$. Hence $d^\star \le p^\star$. The difference $p^\star - d^\star \ge 0$ is the duality gap. Weak duality holds for every problem, convex or not.

Proof. Let $\tilde{\mathbf{x}}$ be any feasible point. Then $h_j(\tilde{\mathbf{x}}) = 0$ and $\mu_i g_i(\tilde{\mathbf{x}}) \le 0$ (since $\mu_i \ge 0$, $g_i \le 0$), so $$d(\boldsymbol\lambda,\boldsymbol\mu) = \min_{\mathbf{x}} L(\mathbf{x},\boldsymbol\lambda,\boldsymbol\mu) \;\le\; L(\tilde{\mathbf{x}},\boldsymbol\lambda,\boldsymbol\mu) = f(\tilde{\mathbf{x}}) + \underbrace{\textstyle\sum_j\lambda_j h_j(\tilde{\mathbf{x}})}_{=\,0} + \underbrace{\textstyle\sum_i\mu_i g_i(\tilde{\mathbf{x}})}_{\le\,0} \;\le\; f(\tilde{\mathbf{x}}).$$ This holds for every feasible $\tilde{\mathbf{x}}$, so it holds for the best one: $d \le p^\star$. $\blacksquare$

Strong duality holds when $d^\star = p^\star$ (zero gap). Sufficient condition (Slater's condition): the problem is convex ($f$ and the $g_i$ convex, the $h_j$ affine) and there is a strictly feasible point, i.e. some $\mathbf{x}$ with $g_i(\mathbf{x}) \lt 0$ for every $i$ and $h_j(\mathbf{x}) = 0$. (If every $g_i$ is affine, it is enough that the problem has at least one feasible point.)

When strong duality holds and the optima $\mathbf{x}^\star$ and $(\boldsymbol\lambda^\star,\boldsymbol\mu^\star)$ exist, they satisfy the KKT conditions together. Conversely, for a convex problem, KKT points give zero duality gap. Chapter 3.10 proves and uses this.

A constraint qualification is a regularity condition on the constraints at $\mathbf{x}^\star$ that guarantees KKT multipliers exist at a local minimum. Common ones:

• LICQ (linear independence): the gradients of all active inequality constraints and of all equality constraints at $\mathbf{x}^\star$ are linearly independent. (In the example above, the single gradient $g'(0) = 0$ is not independent.) LICQ also makes the multipliers unique.
• Slater's condition (for convex problems): some point satisfies every inequality strictly ($g_i \lt 0$) and the equalities. (In the example, $x^2 \lt 0$ is impossible, so Slater fails.)
• Linear constraints: if every constraint is affine (a straight line, plane or half-space), no extra condition is needed.

Theorem (awareness level): if $\mathbf{x}^\star$ is a local minimum and a CQ holds there, then KKT multipliers exist. Without a CQ, they may not.

Penalty form and constraint form are two views of one idea. "Minimise loss subject to $\|\mathbf{w}\|^2 \le r^2$" and "minimise loss $+\ \lambda\|\mathbf{w}\|^2$" give the same solutions (for convex losses) for matching $r$ and $\lambda$: the multiplier of the constraint is $\lambda$ (Chapter 3.11). A softmax output satisfies the simplex rule automatically (it is built to), so no constraint solver is needed there.

(Real solvers such as SciPy's SLSQP combine these ideas, repeatedly solving small KKT systems. You rarely implement them yourself.)