Appendix B
Math Reference
B.1Matrix Calculus Identities
For $\vx,\va\in\R^d$, $\mA\in\R^{d\times d}$, $\mX\in\R^{n\times d}$, $\vy\in\R^n$. Gradients are column vectors with the same shape as the variable.
| Function $f$ | Gradient $\nabla f$ |
|---|---|
| $\va\T\vx$ | $\va$ |
| $\vx\T\mA\vx$ | $(\mA+\mA\T)\vx$ ($2\mA\vx$ if $\mA$ symmetric) |
| $\norm{\vx}_2^2$ | $2\vx$ |
| $\norm{\vx}_2$ | $\vx/\norm{\vx}_2$ ($\vx\neq\mathbf 0$) |
| $\norm{\mX\vw-\vy}_2^2$ (in $\vw$) | $2\mX\T(\mX\vw-\vy)$ |
| $\log\sum_je^{x_j}$ | $\softmax(\vx)$ |
| $\sigma(z)=1/(1+e^{-z})$ | $\sigma(z)(1-\sigma(z))$ |
| $-\sum_ky_k\log\softmax(\vz)_k$ (one-hot $\vy$) | $\softmax(\vz)-\vy$ |
Matrix products. If $\mathbf C=\mA\mB$ and $\Loss$ is a scalar, then $\partial\Loss/\partial\mA=(\partial\Loss/\partial\mathbf C)\mB\T$ and $\partial\Loss/\partial\mB=\mA\T(\partial\Loss/\partial\mathbf C)$.
Chain rule. For $L=f(\vg(\vx))$, $\nabla_{\vx}L=\mathbf J_{\vg}(\vx)\T\nabla f(\vg(\vx))$.
Softmax Jacobian. For $\vs=\softmax(\vz)$, $\partial\vs/\partial\vz=\diag(\vs)-\vs\vs\T$.
B.2The Smoothness Upper Bound
Proposition B.1
If $\nabla f$ is $L$-Lipschitz, then $f(\vv)\le f(\vu)+\nabla f(\vu)\T(\vv-\vu)+\frac L2\norm{\vv-\vu}^2$ for all $\vu,\vv$.
Show proof
Let $\vd=\vv-\vu$ and $g(t)=f(\vu+t\vd)$. By the fundamental theorem of calculus,
$$\begin{aligned}f(\vv)-f(\vu)&=\int_0^1\nabla f(\vu+t\vd)\T\vd\dd t \\ &= \nabla f(\vu)\T\vd + \int_0^1\big(\nabla f(\vu+t\vd)-\nabla f(\vu)\big)\T\vd\dd t .\end{aligned}$$By Cauchy–Schwarz and the Lipschitz condition, the integrand is at most $\norm{\nabla f(\vu+t\vd)-\nabla f(\vu)}\norm{\vd}\le Lt\norm{\vd}^2$, and $\int_0^1Lt\dd t=L/2$.
This bound is the starting point of the descent lemma (Equation (3.6)).
B.3Common Distributions
| Distribution | Density or mass | Mean | Variance |
|---|---|---|---|
| Bernoulli$(\pi)$ | $\pi^x(1-\pi)^{1-x}$, $x\in\{0,1\}$ | $\pi$ | $\pi(1-\pi)$ |
| Categorical$(\bm\pi)$ | $\pi_k$, $k\in\{1..K\}$ | – | – |
| Binomial$(n,\pi)$ | $\binom nk\pi^k(1-\pi)^{n-k}$ | $n\pi$ | $n\pi(1-\pi)$ |
| Uniform$(a,b)$ | $1/(b-a)$ on $[a,b]$ | $(a+b)/2$ | $(b-a)^2/12$ |
| Exponential$(\lambda)$ | $\lambda e^{-\lambda x}$, $x\ge0$ | $1/\lambda$ | $1/\lambda^2$ |
| Gaussian $\Normal(\mu,\sigma^2)$ | $\frac{1}{\sqrt{2\pi}\sigma}e^{-(x-\mu)^2/2\sigma^2}$ | $\mu$ | $\sigma^2$ |
| Laplace$(\mu,b)$ | $\frac1{2b}e^{-|x-\mu|/b}$ | $\mu$ | $2b^2$ |
Multivariate Gaussian. $\Normal(\vmu,\mSigma)$ has density $(2\pi)^{-d/2}\det(\mSigma)^{-1/2}\exp(-\frac12(\vx-\vmu)\T\mSigma^{-1}(\vx-\vmu))$. If $\vx\sim\Normal(\vmu,\mSigma)$ then $\mA\vx+\vb\sim\Normal(\mA\vmu+\vb,\mA\mSigma\mA\T)$. Independent Gaussians add: $\Normal(\mu_1,\sigma_1^2)+\Normal(\mu_2,\sigma_2^2)=\Normal(\mu_1+\mu_2,\sigma_1^2+\sigma_2^2)$.
KL between Gaussians. In one dimension,
$$D_{\mathrm{KL}}\big(\Normal(\mu_1,\sigma_1^2)\,\Vert\,\Normal(\mu_2,\sigma_2^2)\big)=\log\frac{\sigma_2}{\sigma_1}+\frac{\sigma_1^2+(\mu_1-\mu_2)^2}{2\sigma_2^2}-\frac12 .$$B.4Conditioning Multivariate Gaussians
If $\vx=(\vx_a,\vx_b)$ is jointly Gaussian with mean $(\vmu_a,\vmu_b)$ and covariance blocks $\mSigma_{aa}$, $\mSigma_{ab}$, $\mSigma_{ba}=\mSigma_{ab}\T$, $\mSigma_{bb}$, then the conditional distribution of $\vx_a$ given $\vx_b$ is Gaussian with
$$\E[\vx_a\mid\vx_b]=\vmu_a+\mSigma_{ab}\mSigma_{bb}^{-1}(\vx_b-\vmu_b),\qquad \Cov(\vx_a\mid\vx_b)=\mSigma_{aa}-\mSigma_{ab}\mSigma_{bb}^{-1}\mSigma_{ba}.$$The mean is a linear regression of $\vx_a$ on $\vx_b$, and the covariance (the Schur complement) does not depend on the observed value. This formula gives the posterior of factor analysis (Section 13.8), the Kalman filter (Section 27.4), and Gaussian process regression. Two matrix identities often turn it into a cheaper form: the push-through identity $\mA\T(\mA\mA\T+\mathbf D)^{-1}=(\mI+\mA\T\mathbf D^{-1}\mA)^{-1}\mA\T\mathbf D^{-1}$ and the Woodbury identity $(\mathbf D+\mA\mA\T)^{-1}=\mathbf D^{-1}-\mathbf D^{-1}\mA(\mI+\mA\T\mathbf D^{-1}\mA)^{-1}\mA\T\mathbf D^{-1}$, which replace the inverse of a large matrix by the inverse of a small one when $\mA$ is tall.
B.5Constrained Optimization and Duality
Lagrange multipliers. To optimize $f(\vw)$ subject to equality constraints $h_j(\vw)=0$, look for stationary points of the Lagrangian $f(\vw)+\sum_j\nu_jh_j(\vw)$: at a constrained optimum, $\nabla f$ is a linear combination of the constraint gradients. Example: maximizing $\sum_jN_j\log\theta_j$ subject to $\sum_j\theta_j=1$ gives $\theta_j=N_j/\sum_kN_k$ (Section 8.4).
Inequality constraints and duality. For $\min f(\vw)$ subject to $g_i(\vw)\le0$, form $\mathcal L(\vw,\bm\alpha)=f(\vw)+\sum_i\alpha_ig_i(\vw)$ with $\alpha_i\ge0$, and the dual function $D(\bm\alpha)=\min_{\vw}\mathcal L(\vw,\bm\alpha)$, which is concave even when the primal is not convex. Then:
- Weak duality: $D(\bm\alpha)\le f(\vw)$ for every feasible $\vw$ and every $\bm\alpha\ge0$, so $d^*\le p^*$.
- Strong duality (Slater): if $f$ and the $g_i$ are convex and some $\vw$ satisfies every $g_i(\vw)<0$, then $d^*=p^*$.
- KKT conditions: under strong duality, $\vw^*$ and $\bm\alpha^*$ are optimal if and only if $\nabla_{\vw}\mathcal L(\vw^*,\bm\alpha^*)=\mathbf 0$ (stationarity), $g_i(\vw^*)\le0$ (primal feasibility), $\alpha_i^*\ge0$ (dual feasibility), and $\alpha_i^*g_i(\vw^*)=0$ (complementary slackness).
The SVM (Chapter 9) is the book’s main application; the dual is useful whenever it is easier to solve than the primal or exposes structure such as sparsity or inner products.
B.6Concentration Inequalities
Let $Z_1,\dots,Z_n$ be independent with mean $\mu$ and $\bar Z=\frac1n\sum_iZ_i$.
- Markov. For $X\ge0$ and $a>0$: $\Prob(X\ge a)\le\E X/a$.
- Chebyshev. $\Prob(|X-\E X|\ge a)\le\Var X/a^2$; applied to $\bar Z$, $\Prob(|\bar Z-\mu|\ge\gamma)\le\sigma^2/(n\gamma^2)$.
- Hoeffding. If $Z_i\in[a,b]$, then $\Prob(|\bar Z-\mu|>\gamma)\le2\exp\big(-2n\gamma^2/(b-a)^2\big)$ (Equation (11.1)): exponential rather than polynomial decay in $n$.
- Union bound. $\Prob(\bigcup_kA_k)\le\sum_k\Prob(A_k)$; with Hoeffding it gives uniform convergence over finite hypothesis classes (Chapter 11).
- Chernoff-type rule of thumb. To estimate a probability $p$ to within $\pm\gamma$ with confidence $1-\delta$, about $\log(2/\delta)/(2\gamma^2)$ samples suffice; for $\gamma=0.01$ and $\delta=0.05$, about $18{,}400$.
B.7Useful Inequalities and Identities
- Cauchy–Schwarz. $|\vu\T\vv|\le\norm{\vu}\norm{\vv}$, with equality iff $\vu,\vv$ are parallel.
- Jensen. For convex $f$, $f(\E X)\le\E f(X)$; for concave $f$ (such as $\log$) the inequality reverses.
- Log-sum-exp. $\max_jx_j\le\log\sum_je^{x_j}\le\max_jx_j+\log K$; compute it as $m+\log\sum_je^{x_j-m}$ with $m=\max_jx_j$.
- Geometric series. $\sum_{k=0}^{t-1}\beta^k=(1-\beta^t)/(1-\beta)$ for $\beta\ne1$.
- Bias–variance of an average. For $B$ variables with variance $\sigma^2$ and pairwise correlation $\rho$, the average has variance $\rho\sigma^2+(1-\rho)\sigma^2/B$.
- Exponential limit. $(1-1/n)^n\to e^{-1}$ and $(1+x/n)^n\to e^x$.
- Eigenvalue facts. $\tr\mA=\sum_j\lambda_j$, $\det\mA=\prod_j\lambda_j$; for symmetric $\mA$, $\max_{\norm\vv=1}\vv\T\mA\vv=\lambda_{\max}$.