Chapter 7 Formula Sheet

One page for the whole chapter. Equation numbers are the book’s; the measured columns are this module’s.

§7.1 Gradient descent

what	equation	notes
the problem	$\min_{\mathbf{x}} f(\mathbf{x})$	Eq 7.4, $f$ differentiable
one step	$\mathbf{x}_1 = \mathbf{x}_0 - \gamma\big((\nabla f)(\mathbf{x}_0)\big)^\top$	Eq 7.5
the update	$\mathbf{x}_{i+1} = \mathbf{x}_i - \gamma_i\big((\nabla f)(\mathbf{x}_i)\big)^\top$	Eq 7.6, the whole algorithm
least squares by descent	$\lVert\mathbf{A}\mathbf{x} - \mathbf{b}\rVert^2$, $\ \nabla_{\mathbf{x}} = 2(\mathbf{A}\mathbf{x}-\mathbf{b})^\top\mathbf{A}$	Eq 7.9, 7.10
condition number	$\kappa = \sigma(\mathbf{A})_{\max}/\sigma(\mathbf{A})_{\min}$	§4.5; the aspect ratio of the valley
preconditioning	solve $\mathbf{P}^{-1}(\mathbf{A}\mathbf{x} - \mathbf{b}) = \mathbf{0}$	want $\kappa(\mathbf{P}^{-1}\mathbf{A})$ small and $\mathbf{P}^{-1}$ cheap

The transpose in Eq 7.6 is bookkeeping. Gradients are rows in this book (Eq 5.40), iterates are columns. In NumPy both are flat arrays, so the mistake is invisible until you reshape.

Step size on a quadratic

quantity	formula	Example 7.1 value
curvature bounds	$\mu = \lambda_{\min}$, $L = \lambda_{\max}$	$1.944615$, $20.055385$
condition number	$\kappa = L/\mu$	$10.313294$
divergence threshold	$\gamma < 2/L$	$0.099724$
fastest step size	$\gamma^\star = 2/(\mu+L)$	$0.090909$
convergence rate	$(\kappa-1)/(\kappa+1)$	$0.823217$
per-mode contraction	$\lvert 1 - \gamma\lambda\rvert$	must be under $1$ for every $\lambda$

Measured iteration counts to $10^{-8}$ from $\mathbf{x}_0 = (-3,-1)$: $1025$ at $\gamma = 0.01$, $112$ at the book’s $0.085$, $104$ at $0.090909$, $1280$ at $0.099$, $39113$ at $0.0997$, divergence from $0.0998$. The curve is a U, not a slide.

Adaptive step size, §7.1.1

• $f$ went up → the step was too large. Undo it and decrease $\gamma$. The undo is what buys monotonic convergence.
• $f$ went down → try a larger $\gamma$.

§7.1.2 Momentum

what	equation
the update	$\mathbf{x}_{i+1} = \mathbf{x}_i - \gamma_i\big((\nabla f)(\mathbf{x}_i)\big)^\top + \alpha\,\Delta\mathbf{x}_i$
the memory	$\Delta\mathbf{x}_i = \mathbf{x}_i - \mathbf{x}_{i-1} = \alpha\,\Delta\mathbf{x}_{i-1} - \gamma_{i-1}\big((\nabla f)(\mathbf{x}_{i-1})\big)^\top$
unrolled	$\Delta\mathbf{x}_i = -\gamma\sum_{j=0}^{i-1}\alpha^{\,j}\big((\nabla f)(\mathbf{x}_{i-1-j})\big)^\top$

Equations 7.11 and 7.12, with $\alpha \in [0,1]$. The unrolled form is an exponentially weighted moving average with effective window $1/(1-\alpha)$.

heavy-ball optimum on a quadratic	formula	Example 7.1 value
step size	$\gamma^\star = 4/(\sqrt\mu + \sqrt L)^2$	$0.115976$
momentum	$\alpha^\star = \big((\sqrt L - \sqrt\mu)/(\sqrt L + \sqrt\mu)\big)^2$	$0.275732$
rate	$(\sqrt\kappa - 1)/(\sqrt\kappa + 1)$	$\kappa$ became $\sqrt\kappa$

That $\gamma^\star$ is $16.3\%$ above the $2/L$ where plain descent diverges. Measured at that step size: $\alpha = 0.10$ diverges, $0.165$ takes $3900$ iterations, $\mathbf{0.28}$ takes $\mathbf{33}$, $0.9$ takes $343$, $0.99$ takes $3421$, and $\alpha \geq 1$ never converges. Momentum has a lower stability bound as well as an upper one.

Speedup against plain descent, measured: $2.69\times$ at $\kappa = 10$, $7.89\times$ at $100$, $23.64\times$ at $1000$, $71.36\times$ at $10^4$ — tracking $\sqrt\kappa$.

§7.1.3 Stochastic gradient descent

what	equation
loss as a sum	$L(\boldsymbol\theta) = \sum_{n=1}^{N} L_n(\boldsymbol\theta)$
negative log-likelihood	$L(\boldsymbol\theta) = -\sum_{n=1}^{N}\log p(y_n \mid \mathbf{x}_n, \boldsymbol\theta)$
batch update	$\boldsymbol\theta_{i+1} = \boldsymbol\theta_i - \gamma_i\sum_{n=1}^{N}\big(\nabla L_n(\boldsymbol\theta_i)\big)^\top$
mini-batch estimate	$\hat{\mathbf{g}}_B = \dfrac{N}{\lvert B\rvert}\sum_{n\in B}\big(\nabla L_n(\boldsymbol\theta)\big)^\top$

Equations 7.13, 7.14, 7.15. The only requirement is that the estimate be unbiased, $\mathbb{E}[\hat{\mathbf{g}}_B] = (\nabla L)^\top$ — not that it be accurate.

batch size $B$ (of $N = 2000$)	spread relative to $\lVert\nabla L\rVert$	bias over 3000 draws
$1$	$2.342$	$4.8\times10^{-2}$
$16$	$0.614$	$7.9\times10^{-3}$
$256$	$0.141$	$1.8\times10^{-3}$
$2000$	$\mathbf{0.000}$	$4.9\times10^{-14}$

Noise scales as $\dfrac{1}{\sqrt B}\sqrt{\dfrac{N-B}{N-1}}$ — the second factor is the finite-population correction, and it is why the noise hits exactly zero at $B = N$.

§7.2 Constrained optimization

what	equation
the problem	$\min_{\mathbf{x}} f(\mathbf{x})$ s.t. $g_i(\mathbf{x}) \leq 0$ for all $i$
indicator form	$J(\mathbf{x}) = f(\mathbf{x}) + \sum_i \mathbf{1}(g_i(\mathbf{x}))$, with $\mathbf{1}(z) = 0$ if $z\leq 0$ else $\infty$
the Lagrangian	$L(\mathbf{x}, \boldsymbol\lambda) = f(\mathbf{x}) + \boldsymbol\lambda^\top\mathbf{g}(\mathbf{x})$, $\ \boldsymbol\lambda \geq 0$
the dual function	$D(\boldsymbol\lambda) = \min_{\mathbf{x}} L(\mathbf{x}, \boldsymbol\lambda)$
the dual problem	$\max_{\boldsymbol\lambda\geq 0} D(\boldsymbol\lambda)$
recovering $J$	$J(\mathbf{x}) = \max_{\boldsymbol\lambda\geq 0} L(\mathbf{x}, \boldsymbol\lambda)$
minimax inequality	$\max_{\mathbf{y}}\min_{\mathbf{x}}\phi \leq \min_{\mathbf{x}}\max_{\mathbf{y}}\phi$
weak duality	$\min_{\mathbf{x}}\max_{\boldsymbol\lambda\geq 0} L \geq \max_{\boldsymbol\lambda\geq 0}\min_{\mathbf{x}} L$, i.e. $d^\star \leq p^\star$
stationarity	$\nabla f(\mathbf{x}^\star) + \mathbf{A}^\top\boldsymbol\lambda^\star = \mathbf{0}$
complementary slackness	for each $i$: $g_i(\mathbf{x}^\star) = 0$ or $\lambda_i^\star = 0$

Equations 7.17–7.28. $D$ is always concave, because it is a pointwise minimum of functions affine in $\boldsymbol\lambda$ — however nonconvex $f$ and the $g_i$ are.

Equality constraints: replace $h_j = 0$ by $h_j \leq 0$ and $-h_j \leq 0$. The two non-negative multipliers enter only as a difference, so equality multipliers are unconstrained.

measured	value
minimax gap for $\phi = (x-y)^2$ on $[0,1]^2$	$0.25 - 0 = \mathbf{0.25}$, strict
Example 7.6 gap (convex)	$0.000\text{e}{+}00$
gap on $\min x^4 - 8x^2 + x$ s.t. $x \geq 0$ (nonconvex)	$\mathbf{1.984123}$, dual optimum attained at the infeasible $x = -2$

§7.3 Convexity

what	statement	equation
convex set	$\theta\mathbf{x} + (1-\theta)\mathbf{y} \in C$ for all $\theta \in [0,1]$	Def 7.2, Eq 7.29
convex function	$f(\theta\mathbf{x} + (1-\theta)\mathbf{y}) \leq \theta f(\mathbf{x}) + (1-\theta)f(\mathbf{y})$	Def 7.3, Eq 7.30
first order	$f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla_{\mathbf{x}}f(\mathbf{x})^\top(\mathbf{y}-\mathbf{x})$	Eq 7.31
second order	$\nabla^2_{\mathbf{x}}f(\mathbf{x})$ positive semidefinite	—
epigraph	$\{(\mathbf{x},t) : t \geq f(\mathbf{x})\}$ is a convex set iff $f$ is convex	—
concave	$f$ concave iff $-f$ convex	—
the problem	$\min f$ s.t. $g_i \leq 0$, $h_j = 0$, all convex	Eq 7.38

Equation 7.31 is the one that pays. Substitute $\nabla f(\mathbf{x}) = \mathbf{0}$ and it reads $f(\mathbf{y}) \geq f(\mathbf{x})$ for every $\mathbf{y}$ — a stationary point of a convex function is global, in one line.

Closure rules, Example 7.4

operation	preserves convexity	measured on $x^2$ and $e^{-x}$ over $[-2,3]$
$f_1 + f_2$	yes	min $f'' = +2.0498$, no chord violation
$\alpha f$, $\alpha \geq 0$	yes	scaling cannot flip an inequality
$\max(f_1, f_2)$	yes	min $f'' = +0.4951$, no chord violation
$f_1 - f_2$	no	min $f'' = -5.3872$, violation $0.57535$
$f_1 \cdot f_2$	no	min $f'' = -0.4120$, violation $0.28093$
$A \cap B$ (sets)	yes, any family	—
$A \cup B$, $A \setminus B$ (sets)	no	counterexample must be disjoint

Equation 7.30 is also called Jensen’s inequality; extended to a distribution it reads $f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$.

Sampling cannot establish convexity

$x^4 - 0.02x^2$ has minimum second derivative $-0.04$, so it is not convex — but the failure lives on $2.887\%$ of the domain with a worst chord violation of $9.9\times10^{-5}$. A million random chords catch it $0.2954\%$ of the time, and the rate does not improve with more sampling. Use the Hessian, or prove it from the closure rules.

Example 7.3, the negative entropy

$f(x) = x\log_2 x$, convex for $x>0$, with $\nabla_x = \log_2 x + 1/\log_e 2$ (Eq 7.32).

test	left side	right side	slack
chord at $x=2,4$, $\theta=0.5$	$f(3) = 4.754888$	$5$	$0.245112$
tangent at $2$, read at $4$	$f(4) = 8$	$6.885390$	$1.114610$
second derivative at $2$	$0.721350$ measured	$1/(2\ln 2) = 0.721348$	—

§7.3.1 Linear programming

what	equation
primal	$\min_{\mathbf{x}\in\mathbb{R}^d}\mathbf{c}^\top\mathbf{x}$ s.t. $\mathbf{A}\mathbf{x} \leq \mathbf{b}$
Lagrangian	$L = \mathbf{c}^\top\mathbf{x} + \boldsymbol\lambda^\top(\mathbf{A}\mathbf{x}-\mathbf{b}) = (\mathbf{c}+\mathbf{A}^\top\boldsymbol\lambda)^\top\mathbf{x} - \boldsymbol\lambda^\top\mathbf{b}$
stationarity	$\mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda = \mathbf{0}$ — no $\mathbf{x}$ in it
dual	$\max_{\boldsymbol\lambda\in\mathbb{R}^m} -\mathbf{b}^\top\boldsymbol\lambda$ s.t. $\mathbf{c}+\mathbf{A}^\top\boldsymbol\lambda = \mathbf{0}$, $\boldsymbol\lambda \geq 0$

Equations 7.39–7.43. Primal: $d$ variables, $m$ constraints. Dual: $m$ variables, $d$ equality constraints. Solve whichever is smaller — a default, not a rule.

The optimum is always a vertex, and a vertex has exactly $d$ active constraints. The gradient of a linear objective is the constant $\mathbf{c}$, so there is no stationary point and no gradient method applies.

Example 7.5 measured: five feasible vertices of ten intersections, objective from $-74.16667$ to $+7$. $\mathbf{x}^\star = (37/3, 25/6)$, value $-445/6$, $\boldsymbol\lambda^\star = (13/6, 1/3, 0, 0, 0)$, gap $1.4\times10^{-14}$. Rotating $\mathbf{c}$ through $360°$: all five vertices win over contiguous arcs ($26.5°$ to $116.7°$) with exactly five switches — the answer jumps, it does not slide.

§7.3.2 Quadratic programming

what	equation
primal	$\min_{\mathbf{x}}\tfrac12\mathbf{x}^\top\mathbf{Q}\mathbf{x} + \mathbf{c}^\top\mathbf{x}$ s.t. $\mathbf{A}\mathbf{x} \leq \mathbf{b}$, $\mathbf{Q}$ positive definite
Lagrangian	$L = \tfrac12\mathbf{x}^\top\mathbf{Q}\mathbf{x} + (\mathbf{c}+\mathbf{A}^\top\boldsymbol\lambda)^\top\mathbf{x} - \boldsymbol\lambda^\top\mathbf{b}$
stationarity	$\mathbf{Q}\mathbf{x} + (\mathbf{c}+\mathbf{A}^\top\boldsymbol\lambda) = \mathbf{0}$ — $\mathbf{x}$ is present
solved for $\mathbf{x}$	$\mathbf{x} = -\mathbf{Q}^{-1}(\mathbf{c}+\mathbf{A}^\top\boldsymbol\lambda)$
dual Lagrangian	$D(\boldsymbol\lambda) = -\tfrac12(\mathbf{c}+\mathbf{A}^\top\boldsymbol\lambda)^\top\mathbf{Q}^{-1}(\mathbf{c}+\mathbf{A}^\top\boldsymbol\lambda) - \boldsymbol\lambda^\top\mathbf{b}$
dual	$\max_{\boldsymbol\lambda\in\mathbb{R}^m} D(\boldsymbol\lambda)$ s.t. $\boldsymbol\lambda \geq 0$ — no equalities

Equations 7.45–7.52. The single difference from the LP is whether the stationarity condition contains $\mathbf{x}$: if not it becomes a constraint on $\boldsymbol\lambda$ (Eq 7.42), if so it substitutes back (Eq 7.50).

Example 7.6 measured: $\mathbf{Q}$ eigenvalues $1.585786$ and $4.414214$; $\mathbf{x}^\star = (-1, -\tfrac12)$ with $f = -4.5$ against an unconstrained $-6.285714$, so the constraint costs $1.785714$; $\boldsymbol\lambda^\star = (0, 2.5, 0, 0)$; gap exactly zero. Equation 7.51 reproduces a direct evaluation of the Lagrangian to $1.8\times10^{-14}$ over $20{,}000$ random $\boldsymbol\lambda$.

§7.3.3 The convex conjugate

what	equation
Definition 7.4	$f^*(\mathbf{s}) = \sup_{\mathbf{x}}\big(\langle\mathbf{s},\mathbf{x}\rangle - f(\mathbf{x})\big)$
the line through a point	$y - f(x_0) = s(x - x_0)$
minimum intercept	$\inf_{x_0}\big(-sx_0 + f(x_0)\big)$; the conjugate is its negative
differentiable case	$f^*(s) := sx_0 - f(x_0)$ with $s = \nabla_x f(x_0)$
separable sums	$L(\mathbf{t}) = \sum_i \ell_i(t_i) \Rightarrow L^*(\mathbf{z}) = \sum_i \ell_i^*(z_i)$
Example 7.9	$\min_{\mathbf{x}} f(\mathbf{A}\mathbf{x}) + g(\mathbf{x}) = \max_{\mathbf{u}} -f^*(\mathbf{u}) - g^*(-\mathbf{A}^\top\mathbf{u})$

Equations 7.53–7.68. The transform acts on the function, not on $\mathbf{x}$ or $f(\mathbf{x})$. It needs neither convexity nor differentiability; convexity is what makes it invertible.

The slopes swap: if the slope of $f$ at $x$ is $s$, the slope of $f^*$ at $s$ is $x$.

$f$	$f^*$	domain of $f^*$
$x^2$	$s^2/4$	all of $\mathbb{R}$
$\tfrac12\mathbf{x}^\top\mathbf{A}\mathbf{x} + \mathbf{b}^\top\mathbf{x} + c$	$\tfrac12(\mathbf{s}-\mathbf{b})^\top\mathbf{A}^{-1}(\mathbf{s}-\mathbf{b}) - c$	all of $\mathbb{R}^D$
$\tfrac{\lambda}{2}\mathbf{y}^\top\mathbf{K}^{-1}\mathbf{y}$	$\tfrac{1}{2\lambda}\boldsymbol\alpha^\top\mathbf{K}\boldsymbol\alpha$	all of $\mathbb{R}^n$
$\sum_d x_d\log x_d$	$\sum_d e^{\,s_d - 1}$	all of $\mathbb{R}^D$
$\lvert x\rvert$	$0$	$[-1,1]$ only
$\max\{0, 1-\alpha\}$	$\beta$	$[-1,0]$ only

A kink in the primal becomes a domain boundary in the dual.

The double conjugate and the duality gap

$f^{**} = f$ when $f$ is convex; otherwise $f^{**}$ is the convex envelope. Measured on $x^4 - 3x^2$: $f^{**}$ is flat at $-2.25$ across $[-1.224745, 1.224745]$ and is $2.25$ below $f$ at the origin.

This is the Lagrangian duality gap seen from the other side. $D$ is always concave, so it can only represent a convex envelope; whatever the envelope flattens, the gap loses. Convex problems have zero gap because there is nothing to flatten.

The smoothed hinge, Exercise 7.11

$$h^*(\alpha) = \begin{cases} 0 & \alpha \geq 1\\[3pt] \dfrac{(1-\alpha)^2}{2\gamma} & 1-\gamma \leq \alpha \leq 1\\[5pt] 1 - \alpha - \dfrac\gamma2 & \alpha \leq 1-\gamma\end{cases}$$

Differentiable at both joins (measured slope jump $8.3\times10^{-8}$) and exactly $\gamma/2$ below the hinge on the linear branch — a measured $0.300000$ at $\gamma = 0.6$. Smoothing is never free.

§7.4 Where to go next

weakness of gradient descent	remedy	reference
first-order, ignores curvature	acceleration methods	Nesterov (2018)
long valleys	conjugate gradients	Shewchuk (1994)
—	Newton, using the Hessian	Goh (2017); Bottou et al. (2018)
Hessian too expensive	quasi-Newton, L-BFGS	Nocedal and Wright (2006)
Euclidean geometry is wrong	mirror descent, natural gradient	Beck and Teboulle (2003); Toussaint (2012)
kinks, non-differentiability	subgradient methods	Shor (1985); Bertsekas (1999)
datasets too large for batch	stochastic gradient descent	Hazan (2015); Bottou et al. (2018)
duality and convexity	—	Boyd and Vandenberghe (2004); Bertsekas (2009)
convex analysis foundations	—	Rockafellar (1970); Hiriart-Urruty and Lemaréchal (2001)

Recall card

• Equation 7.6 is the whole of unconstrained optimisation in this book: x minus gamma times the gradient, transposed. Everything else in Chapter 7 repairs it or constrains it.
• Two numbers govern a quadratic: mu and L. The ceiling is 2 over L, the fastest step is 2 over (mu plus L), and the rate is (kappa minus 1) over (kappa plus 1). On Example 7.1 those are 0.099724, 0.090909 and 0.823217.
• Iterations against step size form a U. 104 at the optimum, 39113 at 0.0997, divergence from 0.0998. And a step just past the ceiling can improve for 24 iterations before turning — check the growth factor, not the first few steps.
• Momentum changes the exponent, not the constant. O(kappa) becomes O(root kappa), measured 2.69 times faster at kappa 10 and 71.36 times at kappa ten thousand. Its step size 0.115976 is 16.3 percent ABOVE the plain ceiling, and at that step size too LITTLE momentum diverges.
• SGD needs unbiased, not accurate. At batch size one the typical gradient error is 2.34 times the norm of the true gradient. Keep the N over batch-size factor, or the effective learning rate silently tracks the batch size.
• Mini-batch noise falls as one over root B times root of (N minus B) over (N minus 1). The second factor is why the noise is exactly zero at a full batch.
• Equation 7.18 is right and useless; Equation 7.20 replaces the infinite wall with a linear slope. For non-negative multipliers the Lagrangian is a lower bound at any feasible point, and its maximum over the multipliers rebuilds the indicator.
• Weak duality always holds and D is always concave, however nonconvex the primal — because D is a pointwise minimum of functions affine in lambda. That is duality’s structural payoff; tightness is a separate question.
• The gradient does not vanish at a constrained optimum. The condition is grad f plus A-transpose lambda equals zero: flat where you are free, pushed where you are pinned. Complementary slackness says a slack constraint has zero price.
• Equality multipliers are unconstrained, because splitting an equality into two inequalities makes their two non-negative multipliers enter only as a difference.
• Convexity means every chord stays above the curve, its epigraph is a convex set, its tangent is a global lower bound, and its Hessian is positive semidefinite. Any one of those implies the others.
• Sampling can disprove convexity and never prove it. A function failing on under 3 percent of its domain by 1e-4 passes 99.7 percent of random chord tests, at any sample size.
• Only non-negative weighted sums and maxima are safe. Difference and product both broke convexity on x squared and exp of minus x. Intersection of sets is safe for any family; union and difference need disjoint counterexamples.
• One recipe for both duals: write the Lagrangian, collect the x terms, set the x-derivative to zero. If that condition has no x it is a CONSTRAINT and the dual is an LP; if it has x it SUBSTITUTES and the dual is a concave quadratic.
• An LP optimum is always a vertex with exactly d active constraints, because a linear objective has a constant nonzero gradient and therefore no stationary point. Rotating the objective makes the answer jump between corners.
• Definition 7.4 re-indexes a function by SLOPE instead of position, recording the negated intercept of each supporting line. The slopes swap: the derivative of f-star at s is the x that achieved the supremum.
• f-star-star is f for convex functions and the convex envelope otherwise, and that lost envelope IS the Lagrangian duality gap. The chapter’s two duality sections are one idea.
• A kink in the primal becomes a domain boundary in the dual. The hinge’s conjugate is finite only on a box, and smoothing it by a proximal round trip costs exactly gamma over two in uniform accuracy.

Next: Chapter 8 turns these methods on real data — empirical risk, model selection, and the gap between fitting and generalising.