---
title: Numerical Computation
module: Mathematical Background
moduleNumber: 0
lessonNumber: 3
order: 3
summary: >
  Machine learning runs on finite-precision arithmetic, where every number is
  approximated and every operation rounds. This lesson sets the numerical ground
  rules: overflow and underflow and the standard stabilizations, the condition
  number that measures how much a problem amplifies error, and the gradient-based
  optimization (first and second order, constrained and unconstrained) that
  every training loop runs.
topics: [Mathematical Background]
sources:
  - book: Goodfellow
    ref: "Ch. 4 — Numerical Computation"
  - book: Goodfellow
    ref: "§4.3 Gradient-Based Optimization; §4.4 Constrained Optimization"
---

A learning algorithm is a continuous-mathematics object (gradients, integrals,
matrix inverses) executed on a machine that stores real numbers in a finite
number of bits. The translation is lossy. Every real is rounded to the nearest
representable float, and the gap between adjacent floats grows with magnitude, so
arithmetic accumulates **rounding error** that a careless formula can amplify
without bound. Two failures dominate, and each has a standard remedy.[^gf-numerical]

## Overflow and underflow

A 64-bit float represents a number as a sign, a mantissa, and an exponent. The
exponent is bounded, so the representable magnitudes occupy a finite window: below
it numbers collapse to $0$, above it they saturate to $\pm\infty$.

> **Definition (Underflow).** Rounding a nonzero number near zero to $0$. It is
> dangerous when the zeroed quantity sits in a denominator (division by zero) or
> inside a logarithm ($\log 0 = -\infty$).

> **Definition (Overflow).** A number of large magnitude rounding to $\pm\infty$.
> Subsequent arithmetic propagates the infinity, and $\infty - \infty$ or
> $\infty/\infty$ becomes the indeterminate $\text{NaN}$ that poisons every value
> downstream.

For IEEE-754 double precision the boundaries are concrete: the largest finite
value is about $1.8 \times 10^{308}$ and the smallest positive normal value about
$2.2 \times 10^{-308}$. The function $\exp$ reaches these limits at tiny
arguments ($e^{x}$ overflows for $x \gtrsim 709$ and underflows for
$x \lesssim -745$), and that fragility makes softmax, a tower of exponentials, the
canonical place where numerical care is mandatory.[^gf-overflow]

$$
% caption: A float's representable window: below it $\exp(x)$ underflows to $0$,
% above it overflows to $+\infty$, finite only in between.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{green}{HTML}{1F9D4D}
  % the number line
  \draw[thick] (-6,0) -- (6,0);
  % tick marks for the safe window
  \draw[thick] (-3,0.15) -- (-3,-0.6);
  \node[below] at (-3,-0.55) {x = lower limit};
  \draw[thick] (3,0.15) -- (3,-0.6);
  \node[below] at (3,-0.55) {x = upper limit};
  \node[font=\footnotesize] at (0,-0.45) {input x};
  % safe region (green band)
  \draw[green, line width=2.2pt] (-3,0) -- (3,0);
  \node[green, anchor=south] at (0,0.2) {f\/inite (representable)};
  % underflow region (left)
  \draw[red, line width=2.2pt] (-6,0) -- (-3,0);
  \node[red, anchor=south, align=center] at (-4.5,0.2) {under-\\f\/low: $e^{x}$ rounds to 0};
  % overflow region (right)
  \draw[red, line width=2.2pt] (3,0) -- (6,0);
  \node[red, anchor=south, align=center] at (4.5,0.2) {over-\\f\/low: $e^{x}$ hits inf};
  % arrowheads on the line
  \draw[->, thick] (5.9,0) -- (6.1,0);
  \draw[->, thick] (-5.9,0) -- (-6.1,0);
\end{tikzpicture}
$$

### The softmax stability trick

The softmax turns a vector of scores into a probability distribution,

$$
\text{softmax}(x)_i = \frac{e^{x_i}}{\sum_{j=1}^n e^{x_j}}.
$$

Two ways this breaks: if every $x_i$ is large and positive, each $e^{x_i}$
overflows; if every $x_i$ is large and negative, every $e^{x_i}$ underflows to $0$
and the denominator becomes $0/0$. The fix exploits a shift-invariance. For any
constant $c$,

$$
\text{softmax}(x)_i
= \frac{e^{x_i}}{\sum_j e^{x_j}}
= \frac{e^{-c}\,e^{x_i}}{e^{-c}\sum_j e^{x_j}}
= \frac{e^{x_i - c}}{\sum_j e^{x_j - c}}.
$$

Subtracting a constant from every logit leaves the softmax unchanged. Choose
$c = \max_j x_j$:

$$
\text{softmax}(x)_i = \frac{e^{x_i - \max_j x_j}}{\sum_j e^{x_j - \max_j x_j}}.
$$

> **Theorem (Softmax stability).** With $c = \max_j x_j$, every exponent
> $x_i - c \le 0$, so no term overflows ($e^{\le 0} \le 1$), and the largest term
> is exactly $e^{0} = 1$, so the denominator is $\ge 1$ and cannot underflow to
> zero. The shifted softmax is numerically safe for any input.

> **Proof.** By construction $x_i - c \le 0$ for all $i$, hence
> $0 < e^{x_i - c} \le 1$ — no overflow. The index $i^\star$ attaining the max
> gives $e^{x_{i^\star} - c} = e^0 = 1$, so $\sum_j e^{x_j - c} \ge 1 > 0$ — the
> denominator never underflows, and the ratio is well defined. $\qed$

### The log-sum-exp trick

A second hazard hides downstream. Cross-entropy needs $\log \text{softmax}(x)_i$,
and computing the softmax first then taking its log underflows: a correctly
computed but tiny probability rounds to $0$, and $\log 0 = -\infty$. Fold the log
into the exponentials instead. Starting from the definition and pulling the shift
through the logarithm,

$$
\log \text{softmax}(x)_i
= \log \frac{e^{x_i - c}}{\sum_j e^{x_j - c}}
= (x_i - c) - \log \sum_j e^{x_j - c},
\qquad c = \max_j x_j.
$$

The recurring quantity $\log \sum_j e^{x_j}$ is the **log-sum-exp** function, and
the same shift makes it safe:

$$
\LSE(x) = \log \sum_{j} e^{x_j}
= c + \log \sum_{j} e^{x_j - c},
\qquad c = \max_j x_j.
$$

> **Theorem (LSE stability).** $\LSE(x) = c + \log\sum_j e^{x_j-c}$
> overflows nowhere: every exponent is $\le 0$, the sum lies in $[1, n]$, and its
> log lies in $[0, \log n]$ — a bounded correction to the exact maximum $c$.

The shifted form also reveals $\LSE$ as a **smooth maximum**:
$\max_j x_j \le \LSE(x) \le \max_j x_j + \log n$, so it never exceeds
the true max by more than $\log n$, and equals it when one logit dominates. Library
softmax/cross-entropy implementations fuse all of this into a single numerically
stable kernel; never compute softmax and its log as two separate steps.[^stevens-softmax]

| Quantity | Naive form | Stable form ($c = \max_j x_j$) | Failure avoided |
| --- | --- | --- | --- |
| $\text{softmax}(x)_i$ | $e^{x_i} / \sum_j e^{x_j}$ | $e^{x_i - c} / \sum_j e^{x_j - c}$ | over/underflow |
| $\log \text{softmax}(x)_i$ | $\log\parens{e^{x_i}/\sum_j e^{x_j}}$ | $(x_i - c) - \log\sum_j e^{x_j - c}$ | $\log 0 = -\infty$ |
| $\LSE(x)$ | $\log \sum_j e^{x_j}$ | $c + \log \sum_j e^{x_j - c}$ | overflow of $e^{x_j}$ |

For example, take logits $x = (1000, 1001, 1002)$. The naive
denominator asks for $e^{1000} + e^{1001} + e^{1002}$, and each term overflows to
$+\infty$ in double precision (recall $e^x$ saturates near $x \approx 709$), so the
ratio returns $\infty/\infty = \text{NaN}$. Subtracting $c = 1002$ first,

$$
\text{softmax}(x) = \frac{(e^{-2}, e^{-1}, e^{0})}{e^{-2} + e^{-1} + e^{0}}
= \frac{(0.135, 0.368, 1.000)}{1.503}
\approx (0.090, 0.245, 0.665),
$$

which is exact and never leaves the safe window. The shift changed nothing
mathematically — only which intermediate values the machine had to hold.

## Poor conditioning

Even arithmetic that never overflows can be untrustworthy if the underlying
_problem_ amplifies small input changes into large output changes. The amplifier
is the **condition number**.

> **Definition (Condition number).** For a function $f$, the condition number
> measures how much a relative perturbation in the input is magnified into a
> relative perturbation in the output. For solving $A x = b$ with $A$ symmetric
> and invertible, it is the ratio of the largest to smallest eigenvalue magnitude,
> $$\kappa(A) = \frac{\max_i \abs{\lambda_i}}{\min_i \abs{\lambda_i}}.$$

When $\kappa(A)$ is large the matrix is **ill-conditioned**, and the solution
$x = A^{-1}b$ is highly sensitive to perturbations in $b$ (and to the rounding error
already present in $A$). Decompose $A = Q\Lambda Q^\top$; the inverse stretches the
component of $b$ along eigenvector $v_i$ by $1/\lambda_i$, so the direction of
smallest eigenvalue is magnified most:

$$
A^{-1} b = Q \Lambda^{-1} Q^\top b = \sum_i \frac{(v_i^\top b)}{\lambda_i}\, v_i.
$$

A perturbation $\delta b$ aligned with the small-eigenvalue direction is amplified
by $1/\lambda_{\min}$ while $b$ itself may only be of size $1/\lambda_{\max}$,
giving a worst-case relative error blowup of exactly $\kappa(A)$:

$$
\frac{\norm{\delta x} / \norm{x}}
     {\norm{\delta b} / \norm{b}} \le \kappa(A).
$$

> **Remark (Why it matters for learning).** Conditioning is not only a linear-solve
> concern. The Hessian of the loss plays the role of $A$ near a minimum, and a
> large $\kappa$ there means gradient descent crawls along the flat direction while
> bouncing across the steep one — the zig-zag pathology that motivates momentum,
> adaptive methods, and second-order optimization.[^gf-conditioning]

## Gradient-based optimization

Most deep-learning algorithms reduce to **optimization**: choosing $x$ to minimize
(or maximize) an **objective function** $f(x)$. When the goal is minimization we
call $f$ the **cost**, **loss**, or **error** function, and write the target as
$x^\star = \arg\min_x f(x)$.

> **Definition (Critical point).** A point where the derivative vanishes,
> $f'(x) = 0$ (or in many dimensions $\nabla f(x) = 0$). Critical points are the
> candidates for optima: a **local minimum** (lower than all neighbors), a **local
> maximum** (higher than all neighbors), or a **saddle point** (neither — lower
> along some directions, higher along others).

In one dimension the derivative $f'(x)$ gives the slope, and the update
$x \gets x - \eta\, f'(x)$ steps downhill: where the slope is positive we decrease
$x$, where negative we increase it. The generalization to many variables replaces
the derivative with the **gradient** $\nabla f(x)$, the vector of partial
derivatives $\brackets{\partial f/\partial x_1, \dots, \partial f/\partial x_n}^\top$.

> **Definition (Directional derivative).** The rate of change of $f$ at $x$ along a
> unit vector $u$ is $\nabla_u f(x) = u^\top \nabla f(x)$, the slope of the
> one-dimensional slice of $f$ taken in direction $u$.

To descend fastest we pick the direction $u$ that minimizes this slope:

$$
\min_{\norm{u} = 1} u^\top \nabla f
= \min_{\norm{u} = 1} \norm{u}\,\norm{\nabla f} \cos\theta
= \min_{\theta} \norm{\nabla f} \cos\theta,
$$

minimized at $\cos\theta = -1$, i.e. $u$ points _opposite_ the gradient. This is
the **method of steepest descent**: step against the gradient,

$$
x' = x - \eta\, \nabla f(x),
$$

with $\eta > 0$ the **learning rate** (step size).[^gf-gradient]

$$
% caption: Gradient descent on a 1-D loss: each step moves downhill against the
% slope, walking the iterates toward the minimum where $f'(x)=0$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (-0.3,0) -- (6.4,0) node[right] {$x$};
  \draw[->, thick] (0,-0.3) -- (0,3.6) node[above] {loss};
  % the loss curve: a parabola f(x) = 0.42 (x-3)^2 + 0.3
  \draw[acc, very thick] plot[domain=0.2:5.8, samples=80] (\x, {0.42*(\x-3)*(\x-3)+0.3});
  % minimum at x=3
  \fill[green] (3, 0.3) circle (2.6pt);
  % iterate points walking down from the left
  \fill[acc] (0.5,3.0) circle (2.4pt);
  \fill[acc] (1.35,1.74) circle (2.4pt);
  \fill[acc] (2.05,0.69) circle (2.4pt);
  \fill[acc] (2.55,0.38) circle (2.4pt);
  % step arrows along the curve
  \draw[->, acc, thick] (0.5,3.0) -- (1.35,1.74);
  \draw[->, acc, thick] (1.35,1.74) -- (2.05,0.69);
  \draw[->, acc, thick] (2.05,0.69) -- (2.55,0.38);
  \node[acc, anchor=west] at (0.65,3.2) {start};
  \node[green, anchor=west] at (3.4,0.12) {\texttt{minimum}};
  \node[acc, anchor=west, align=left] at (4.1,2.2) {\texttt{each} \texttt{step}\\\texttt{descends} \texttt{loss}};
\end{tikzpicture}
$$

The full procedure is the base every later optimizer refines.

```algorithm
caption: $\textsc{SteepestDescent}(f, x_0, \eta)$ — first-order minimization
initialize $x \gets x_0$
repeat
  $g \gets \nabla f(x)$ // gradient at the current point
  $x \gets x - \eta \cdot g$ // step against the gradient
until $\norm{g} \le \epsilon$ // converged: gradient near zero
return $x$
```

## The Jacobian and the Hessian

When $f$ is vector-valued, $f : \mathbb{R}^m \to \mathbb{R}^n$, its first
derivatives form a matrix.

> **Definition (Jacobian).** For $f : \mathbb{R}^m \to \mathbb{R}^n$, the Jacobian
> $J \in \mathbb{R}^{n \times m}$ collects all first-order partials,
> $J_{ij} = \partial f_i / \partial x_j$.

For a scalar objective $f : \mathbb{R}^n \to \mathbb{R}$, the gradient's own
derivative (the matrix of second partials) is the **Hessian**, and it encodes
**curvature**.

> **Definition (Hessian).** The matrix of second partial derivatives,
> $H_{ij} = \partial^2 f / (\partial x_i\, \partial x_j)$. Where the second
> derivatives are continuous the Hessian is symmetric ($H_{ij} = H_{ji}$), so it
> has real eigenvalues and orthogonal eigenvectors. The second derivative along a
> unit direction $d$ is $d^\top H d$.

The Hessian sharpens the critical-point test. The **second-derivative test** reads
curvature off the eigenvalues of $H$ at a critical point:

| Hessian at critical point | Curvature | Classification |
| --- | --- | --- |
| $H \succ 0$ (all $\lambda_i > 0$) | bowl up in every direction | local **minimum** |
| $H \prec 0$ (all $\lambda_i < 0$) | dome down in every direction | local **maximum** |
| eigenvalues of mixed sign | up some ways, down others | **saddle point** |
| some $\lambda_i = 0$ | flat direction | test **inconclusive** |

### Curvature sets the step size

Approximate $f$ near the current point $x$ by its second-order Taylor expansion in
the gradient direction. Writing $g = \nabla f(x)$ and $H$ the Hessian at $x$, a
step of size $\eta$ along $-g$ gives

$$
f(x - \eta g) \approx f(x) - \eta\, g^\top g + \tfrac12 \eta^2\, g^\top H g.
$$

The middle term is the gain we want; the last term is the curvature penalty. If
$g^\top H g > 0$ the quadratic in $\eta$ is minimized by setting its derivative to
zero, $-g^\top g + \eta\, g^\top H g = 0$, giving the **optimal step size**

$$
\eta^\star = \frac{g^\top g}{g^\top H g}.
$$

High curvature ($g^\top H g$ large) shrinks $\eta^\star$: a steep, narrow valley
demands tiny steps; low curvature permits large ones.

$$
% caption: Near $x_0$ the function (blue) is matched by its second-order Taylor
% parabola (green), whose curvature $f''$ sets the bowl width.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % axes
  \draw[->, thick] (-0.3,0) -- (6.4,0) node[right] {$x$};
  \draw[->, thick] (0,-0.3) -- (0,3.7) node[above] {$f(x)$};
  % true function f(x) = 0.9 + 0.30(x-3)^2 + 0.06(x-3)^3
  % at x0=3: f=0.9, f'=0, f''=0.60 — the osculating parabola matches all three
  \draw[acc, very thick] plot[domain=0.6:5.4, samples=110]
    (\x, {0.9 + 0.30*(\x-3)*(\x-3) + 0.06*(\x-3)*(\x-3)*(\x-3)});
  \node[acc, anchor=south] at (5.1,2.35) {$f$};
  % expansion point x0 = 3 (the shared tangency)
  \fill[black] (3,0.9) circle (2.4pt);
  \node[anchor=north west] at (3.1,0.85) {$x_0$};
  % osculating parabola: 0.9 + 0.30(x-3)^2 — same value, slope, curvature at x0
  \draw[green, very thick, densely dashed] plot[domain=1.1:4.9, samples=90]
    (\x, {0.9 + 0.30*(\x-3)*(\x-3)});
  \node[green, anchor=west] at (0.4,3.3) {Taylor parabola};
\end{tikzpicture}
$$

### The condition number of the Hessian

When the Hessian's eigenvalues differ wildly, a single scalar learning rate cannot
serve every direction at once.

> **Definition (Condition number of the Hessian).** The ratio
> $\kappa(H) = \lambda_{\max} / \lambda_{\min}$ of largest to smallest eigenvalue.
> Large $\kappa(H)$ means strongly **ill-conditioned** curvature: the loss is a
> long, thin valley.

A step large enough to make progress along the gentle (small-$\lambda$) direction
overshoots and oscillates along the steep (large-$\lambda$) direction; a step small
enough to be stable on the steep direction barely moves on the gentle one. Gradient
descent is forced to compromise and **zig-zags** down the valley, taking many steps
to cross what is geometrically a short distance.

$$
% caption: Contours of a well-conditioned bowl (left, $\kappa\approx1$, circular)
% and an ill-conditioned one (right, $\kappa$ large, elongated). Steepest descent
% moves straight in on the left but must zig-zag on the right.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % --- left: well-conditioned (circular) ---
  \foreach \r in {0.4,0.8,1.2,1.6} \draw[acc] (0,0) circle (\r);
  \fill[black] (0,0) circle (1.6pt);
  \draw[->, red, very thick] (-1.35,1.0) -- (0,0);
  \node[font=\footnotesize, anchor=north] at (0,-1.9) {well-conditioned};
  \node[font=\footnotesize, anchor=north] at (0,-2.35) {cond.\ number near 1};
  % --- right: ill-conditioned (elongated) ---
  \begin{scope}[xshift=6cm]
    \foreach \r in {0.4,0.8,1.2,1.6} \draw[acc] (0,0) ellipse ({\r*1.9} and {\r*0.55});
    \fill[black] (0,0) circle (1.6pt);
    \draw[->, red, very thick] (-2.9,0.85) -- (-1.5,-0.35);
    \draw[->, red, very thick] (-1.5,-0.35) -- (-0.7,0.3);
    \draw[->, red, very thick] (-0.7,0.3) -- (-0.2,-0.12);
    \draw[->, red, very thick] (-0.2,-0.12) -- (0,0);
    \node[font=\footnotesize, anchor=north] at (0,-1.9) {ill-conditioned};
    \node[font=\footnotesize, anchor=north] at (0,-2.35) {cond.\ number large};
  \end{scope}
\end{tikzpicture}
$$

### Newton's method

Second-order methods address this by using $H$ to rescale the step
per-direction. Expand $f$ to second order around $x_0$ and minimize the
approximation exactly. The quadratic model is

$$
f(x) \approx f(x_0) + (x - x_0)^\top g + \tfrac12 (x - x_0)^\top H (x - x_0),
\qquad g = \nabla f(x_0).
$$

Setting the gradient of the right-hand side to zero,

$$
\nabla\brackets{\cdots} = g + H (x - x_0) = 0
\;\Longrightarrow\;
x - x_0 = -H^{-1} g,
$$

yields the **Newton step**

$$
x^\star = x_0 - H^{-1} \nabla f(x_0).
$$

> **Theorem (Newton on a quadratic).** If $f$ is exactly quadratic with positive
> definite Hessian $H$, Newton's method reaches the global minimum in a single
> step from any starting point. Where gradient descent needs $O(\kappa(H))$ steps,
> Newton needs one — the $H^{-1}$ factor undoes the conditioning by rescaling each
> eigendirection by $1/\lambda_i$.

$$
% caption: On an ill-conditioned bowl, gradient descent (red) zig-zags while the
% Newton step (green), rescaled by $H^{-1}$, jumps to the minimum directly.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % elongated contour ellipses (ill-conditioned bowl), wide in x, narrow in y
  \foreach \r in {0.5,1.0,1.5,2.0,2.5}
    \draw[black] (0,0) ellipse ({\r*1.7} and {\r*0.6});
  % minimum at center
  \fill[black] (0,0) circle (2.4pt);
  \node[anchor=north] at (0,-0.12) {min};
  % start point on the upper left
  \coordinate (s) at (-3.4,1.25);
  \fill[red] (s) circle (2.4pt);
  \node[red, anchor=south east] at (-3.3,1.3) {start};
  % gradient descent zig-zag (red): bounces across the narrow axis
  \draw[red, very thick, ->] (s) -- (-2.0,-0.55);
  \draw[red, very thick, ->] (-2.0,-0.55) -- (-1.1,0.55);
  \draw[red, very thick, ->] (-1.1,0.55) -- (-0.5,-0.3);
  \draw[red, very thick, ->] (-0.5,-0.3) -- (-0.18,0.12);
  \node[red, anchor=west] at (-1.9,-0.95) {gradient descent};
  % newton step (green): straight to the minimum
  \draw[green, very thick, ->] (s) -- (0,0);
  \node[green, anchor=west] at (0.4,1.2) {Newton step};
\end{tikzpicture}
$$

The power comes at a cost: forming and inverting $H$ is $O(n^3)$ in the parameter
count $n$, intractable for deep networks with millions of parameters, which is why
practice relies on cheaper approximations. A second problem is subtler.

> **Remark (Saddle points).** Newton's method finds critical points, not minima —
> it solves $\nabla f = 0$. Near a **saddle point** the Hessian has mixed-sign
> eigenvalues, and the Newton step is _attracted_ to the saddle rather than
> escaping it, the opposite of what optimization wants. In high-dimensional
> non-convex losses saddle points vastly outnumber minima,[^gf-saddle] so naive Newton is
> hazardous; the [second-order and approximate
> methods](/deep-learning/optimization/second-order-and-approximate-methods)
> lesson develops the saddle-free and quasi-Newton repairs.

| Method | Step | Cost / iter | Conditioning | Saddle behavior |
| --- | --- | --- | --- | --- |
| Gradient descent | $-\eta\, g$ | $O(n)$ | $O(\kappa)$ steps to converge | steps away (slowly) |
| Newton's method | $-H^{-1} g$ | $O(n^3)$ | 1 step on a quadratic | attracted to saddles |

## Constrained optimization

Often we minimize $f$ not over all of $\mathbb{R}^n$ but over a **feasible set**
$\mathbb{S}$ carved out by constraints. The standard form has equality and
inequality constraints,

$$
\min_x f(x) \quad \text{subject to} \quad
g_i(x) = 0,\quad h_j(x) \le 0.
$$

The **method of Lagrange multipliers** converts this constrained problem into an
unconstrained one by folding each constraint into the objective with its own
multiplier.

> **Definition (Lagrangian).** With multipliers $\lambda_i$ for the equalities and
> $\alpha_j \ge 0$ for the inequalities,
> $$\mathcal{L}(x, \lambda, \alpha) = f(x) + \sum_i \lambda_i\, g_i(x) + \sum_j \alpha_j\, h_j(x).$$
> The constrained minimizer is a stationary point of $\mathcal{L}$ in $x$,
> balanced against the multipliers.

At an equality-constrained optimum the objective's gradient must be parallel to the
constraint's, $\nabla f = -\lambda \nabla g$; otherwise a move along the
constraint surface would still decrease $f$. The general first-order optimality
conditions are the **Karush–Kuhn–Tucker (KKT)** conditions.

> **Theorem (KKT conditions).** At a constrained optimum $x^\star$ there exist
> multipliers $\lambda, \alpha$ with: **stationarity** $\nabla_x \mathcal{L} = 0$;
> **primal feasibility** $g_i(x^\star) = 0$, $h_j(x^\star) \le 0$; **dual
> feasibility** $\alpha_j \ge 0$; and **complementary slackness**
> $\alpha_j\, h_j(x^\star) = 0$ for every $j$.

Complementary slackness encodes a clean dichotomy: each inequality is either
**inactive** ($h_j < 0$, and its multiplier $\alpha_j = 0$ — the constraint does
not bind) or **active** ($h_j = 0$, and $\alpha_j \ge 0$ — the constraint pins the
solution to the boundary).[^gf-kkt] The figure shows the active case, where the optimum
leaves the unconstrained minimum and rests against the boundary.

$$
% caption: With the unconstrained minimum outside the feasible region (shaded),
% the constrained optimum sits where a loss contour is tangent to the boundary.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \definecolor{red}{HTML}{C0392B}
  % feasible region: a half-plane to the lower-left of a line, shaded
  \draw[black, fill=black!8] (-2.6,-2.2) -- (2.4,-2.2) -- (-2.6,2.8) -- cycle;
  \draw[black, thick] (2.4,-2.2) -- (-2.6,2.8) node[anchor=south east, black, pos=0.12] {boundary};
  \node[black, anchor=north west] at (-2.5,-1.4) {feasible region};
  % loss contours centered at the unconstrained minimum (outside feasible set)
  \coordinate (um) at (1.7,1.5);
  \foreach \r in {0.55,1.1,1.65,2.2}
    \draw[acc] (um) circle (\r);
  \fill[acc] (um) circle (2.4pt);
  \node[acc, anchor=south] at (1.7,3.85) {unconstrained min};
  % constrained optimum: tangent point of a contour with the boundary
  \fill[green] (0.0,0.05) circle (2.6pt);
  \node[green, anchor=north] at (-0.6,-2.4) {constrained optimum};
  \draw[green] (-0.5,-2.25) .. controls (-0.4,-1.4) and (-0.15,-0.6) .. (-0.05,-0.05);
  % gradient of f at the optimum, normal to the boundary
  \draw[->, red, very thick] (0.0,0.05) -- (0.85,0.9);
  \node[red, anchor=east] at (0.35,0.95) {grad $f$};
\end{tikzpicture}
$$

## Mixed precision and low-bit training

The overflow/underflow window this lesson treats for double precision has become a
front-line engineering concern, because modern training deliberately uses _fewer_
bits.

**Mixed precision and the two 16-bit formats.** Training in 16-bit floats halves
memory and roughly doubles throughput on modern accelerators, but the choice of
format comes down to an overflow/underflow tradeoff. **IEEE fp16** has a 10-bit
mantissa and only 5 exponent bits, so its representable window stops around
$6.5 \times 10^4$ and $6 \times 10^{-8}$ — small gradients underflow to zero.
**bfloat16** keeps 8 exponent bits (the same dynamic range as fp32, up to
$\sim 3 \times 10^{38}$) at the cost of a 7-bit mantissa, trading precision for
range precisely because underflow, not rounding, is what breaks training. This is
the window diagram of this lesson made into a hardware decision (Micikevicius et
al., 2017).

**Loss scaling.** When fp16 is unavoidable, **loss scaling** multiplies the loss by
a large constant $S$ before back-propagation, shifting every gradient up into the
representable window, then divides by $S$ before the weight update. It is the
softmax shift trick in reverse: rescale to dodge the boundary, then undo the
rescale, changing nothing mathematically while keeping every intermediate in the
safe range.

**Cheap curvature.** The $O(n^3)$ Newton step this lesson rules out for large $n$
has practical stand-ins. **K-FAC** (Martens and Grosse, 2015) approximates the
Hessian (really the Fisher information) as a Kronecker product of two small
per-layer factors, each cheap to invert, capturing the conditioning that plain
gradient descent ignores without ever forming the full matrix — the standard way
second-order ideas reach real networks.[^mixedprec][^kfac]

## Takeaways

- **Underflow** (nonzero $\to 0$, deadly in denominators and logs) and
  **overflow** ($\to \pm\infty \to \text{NaN}$) are the two finite-precision
  failures; $\exp$ hits both at modest arguments.
- **Softmax** is stabilized by subtracting $\max_j x_j$ from every logit (leaving
  the result unchanged); the **log-sum-exp** identity
  $\LSE(x) = c + \log\sum_j e^{x_j - c}$ keeps $\log\text{softmax}$
  finite; always fuse them, never compute softmax then log.
- The **condition number** $\kappa = \lambda_{\max}/\lambda_{\min}$ measures how
  much a problem amplifies error; ill-conditioned Hessians make gradient descent
  zig-zag.
- **Steepest descent** steps against the gradient; **critical points** classify by
  the **Hessian** eigenvalues (the second-derivative test), and curvature
  $g^\top H g$ sets the optimal step $\eta^\star = g^\top g / g^\top H g$.
- **Newton's method** $x \gets x - H^{-1}\nabla f$ jumps to the minimum of a
  quadratic in one step but costs $O(n^3)$ and is attracted to **saddle points**.
- **Constrained** problems fold constraints into the **Lagrangian**; the **KKT
  conditions** (stationarity, feasibility, dual feasibility, complementary
  slackness) characterize the optimum, which an active inequality pins to the
  feasible boundary.

[^gf-numerical]: **Goodfellow**, _Deep Learning_, Ch. 4 — Numerical Computation: finite-precision arithmetic as the substrate of every learning algorithm, where rounding, overflow, and underflow are first-class concerns.
[^gf-overflow]: **Goodfellow**, _Deep Learning_, §4.1 — Overflow and Underflow: how $\exp$ saturates at modest arguments and why softmax is the canonical site demanding numerical care.
[^stevens-softmax]: **Stevens**, _Deep Learning with PyTorch_, Ch. 7 — softmax and cross-entropy are fused into a single stable kernel (`log_softmax` + `nll_loss`); never compose softmax and its log as separate ops.
[^gf-conditioning]: **Goodfellow**, _Deep Learning_, §4.2 — Poor Conditioning: the condition number $\kappa(A) = \abs{\lambda_{\max}}/\abs{\lambda_{\min}}$ as the amplifier of input error, and the Hessian's $\kappa$ as the cause of zig-zagging descent.
[^gf-gradient]: **Goodfellow**, _Deep Learning_, §4.3 — Gradient-Based Optimization: steepest descent as stepping against $\nabla f$, the directional derivative $u^\top\nabla f$ minimized opposite the gradient.
[^gf-saddle]: **Goodfellow**, _Deep Learning_, §4.3.1 — Beyond the Gradient: in high-dimensional non-convex losses saddle points dominate, making naive Newton steps hazardous because they are attracted to critical points of any type.
[^gf-kkt]: **Goodfellow**, _Deep Learning_, §4.4 — Constrained Optimization: the Lagrangian and the KKT conditions (stationarity, primal/dual feasibility, complementary slackness) characterizing a constrained optimum.
[^mixedprec]: Micikevicius, Narang, Alben, Diamos, Elsen, Garcia, Ginsburg, Houston, Kuchaiev, Venkatesh, Wu (2017), _Mixed Precision Training_, arXiv:1710.03740 — fp16 vs. bf16 dynamic-range tradeoffs and loss scaling to keep gradients inside the representable window.
[^kfac]: Martens and Grosse (2015), _Optimizing Neural Networks with Kronecker-factored Approximate Curvature_, ICML — a Kronecker-product approximation to the Fisher/Hessian that makes an approximate second-order step tractable for deep networks.