Formula Sheet

All formulas of the course on one page, in course order. Every block links to the section where it is explained. Terms are in the Glossary, the math behind the formulas in the Math Foundations.

How to read the bounds

Almost every bound has the form true risk $\le$ empirical risk + a term that shrinks with $n$, and it holds with probability at least $1-\delta$. The term decays like $1/\sqrt{n}$ (standard rate) or $1/n$ (fast rate). To decide whether a bound is useful, check whether the whole term goes to 0.

Decision theory (Lecture 1.1)

True risk and Bayes risk → True risk, Bayes risk

$$\begin{array}{c}R(f)=E(\ell (X,Y,f(X)))\\ R^{\ast }=\underset{f}{\inf }R(f)\end{array}$$

A function that attains $R^{\ast }$ is a Bayes classifier $f^{\ast }$.

Regression function and Bayes classifier for the 0-1 loss → Explicit form

$$\begin{array}{c}\eta (x)=P(Y=1\mid X=x)\\ f^{\ast }(x)=1⟺\eta (x)\ge \frac{1}{2}\end{array}$$

The error at $x$ is $\min (\eta (x),1-\eta (x))$, the Bayes risk is its expectation.

Posterior from priors and class conditionals → MAP

$$\eta (x)=\frac{{\pi }_{1}p(x\mid 1)}{{\pi }_{0}p(x\mid 0)+{\pi }_{1}p(x\mid 1)}$$

${\pi }_y$ = prior of class $y$, $p(x\mid y)$ = class conditional density. Maximum likelihood compares only $p(x\mid 1)$ and $p(x\mid 0)$ and ignores the priors.

Bayes decision rule with costs → Costs of errors

$$\text{predict }1⟺{\pi }_1{\ell }_{01}p(x\mid 1)>{\pi }_0{\ell }_{10}p(x\mid 0)⟺\eta (x)>\frac{{\ell }_{10}}{{\ell }_{01}+{\ell }_{10}}$$

${\ell }_{01}$ = cost of predicting 0 when $Y=1$, ${\ell }_{10}$ = cost of predicting 1 when $Y=0$. The decision boundaries are the points where the two weighted curves cross (reading a diagram).

Bayes error from the weighted densities

$$R^{\ast }=\int \min \{{\pi }_{0}p(x\mid 0),{\pi }_{1}p(x\mid 1)\}dx$$

Surrogate losses on a score $f(x)\in \mathbb{R}$, labels $\pm 1$ → Bayes predictors

Loss	$\ell (y,f(x))$
hinge	$\max (0,1-yf(x))$
squared	$\max (0,1-yf(x){)}^2$
exponential	$\exp (-yf(x))$
logistic	${\log }_2(1+\exp (-yf(x)))$

All four are classification-calibrated: thresholding their Bayes predictor at 0 gives the 0-1 Bayes classifier.

Squared loss → Regression

$$\begin{array}{c}{f}^{\ast }(x)=E(Y\mid X=x)\\ E|f(X)-Y{|}^2=E|f(X)-\eta (X){|}^2+E|\eta (X)-Y{|}^2\end{array}$$

Learning from finite samples (Lecture 1.2)

Consistency → Consistency

$$\forall \epsilon >0:\underset{n\to \infty }{\lim }P(R(f_n)-R^{\ast }>\epsilon )=0$$

Universally consistent: for every distribution $P$.

Empirical risk and ERM → Empirical risk, ERM

$$\begin{array}{c}{R}_n(f)=\frac{1}{n}\sum _{i=1}^n\ell (X_i,Y_i,f(X_i))\\ f_n=\underset{f\in \mathcal{F}}{\mathrm{argmin}}{R}_n(f)\end{array}$$

Estimation and approximation error → Definitions

$$R(f_n)-R(f^{\ast })=\underset{\text{estimation error}}{\underbrace{R(f_n)-R(\tilde{f})}}+\underset{\text{approximation error}}{\underbrace{R(\tilde{f})-R(f^{\ast })}}$$

$\tilde{f}$ = the best function in $\mathcal{F}$. A larger class raises the first term and lowers the second.

Bias-variance decomposition ($L_2$ loss, at a point $x$) → Bias-variance

$$E(f_n(x)-f^{\ast }(x){)}^2=\underset{\text{variance}}{\underbrace{E(f_n(x)-E{f}_n(x){)}^2}}+\underset{{\text{bias}}^2}{\underbrace{(E{f}_n(x)-f^{\ast }(x){)}^2}}$$

No Free Lunch → Propositions 7 to 9

On $m$ points there are $2^m$ possible true functions. Averaged over all of them, every classifier has the same error.

Perceptron (Lecture 2)

Classifier, update and linear loss → Algorithm, Linear loss

$$\begin{array}{c}f(x)=\mathrm{sign}(⟨w,x⟩)\\ \text{mistake}⟺y_t⟨w_{t-1},x_t⟩\le 0\Rightarrow w_t=w_{t-1}+y_t{x}_t\end{array}$$

This is SGD with step size 1 on $\ell =\max \{0,-y⟨w,x⟩\}$, started at $w_0=0$.

Margin → Margin

$$\rho =\underset{i}{\min }\frac{y_i⟨w,x_i⟩}{\Vert w\Vert }$$

Mistake bound and test error → Theorem 1, Theorem 2

$$\begin{array}{c}\#\text{mistakes}\le \frac{R^2}{{\rho }^2}\\ \text{test error}\le \frac{1}{n+1}E\left(\frac{R^2}{{\rho }^2}\right)\end{array}$$

$\Vert x_i\Vert \le R$, margin $\rho$ of a separating $w^{\ast }$. Neither bound depends on the dimension. Not separable, with slack $D$: at most $(R+D{)}^2/{\rho }^2$ updates (outlook).

Statistical learning theory (Lecture 3)

Hoeffding → Hoeffding’s inequality

$$\begin{array}{c}P(|S_n-E(S_n)|\ge \epsilon )\le 2\exp (-2n{\epsilon }^2)\\ S_n=\frac{1}{n}\sum _{i=1}^n{Z}_i,Z_i\in [0,1]\text{ independent}\end{array}$$

McDiarmid → McDiarmid’s inequality

$$P(|f(X_1,\dots ,X_n)-Ef|\ge \epsilon )\le 2\exp \left(\frac{-2{\epsilon }^2}{{\sum }_{i=1}^n{c}_i^2}\right)$$

$c_i$ = the most $f$ can change when only the $i$-th argument changes.

One fixed function → Fixed function

$$|R(f_0)-R_n(f_0)|\le \sqrt{\frac{\log (2/\delta )}{2n}}\text{with probability}\ge 1-\delta$$

One-sided: $\log (1/\delta )$. Sample size for accuracy $\epsilon$: of the order $1/{\epsilon }^2$.

Uniform convergence controls ERM → Uniform convergence

$$|R(f_n)-R(f_{\mathcal{F}})|\le 2\underset{f\in \mathcal{F}}{\sup }|R(f)-R_n(f)|$$

Finite class with $m$ functions → Union bound

$$R(f)\le R_n(f)+\sqrt{\frac{\log (2m)+\log (1/\delta )}{2n}}\text{for all }f\in \mathcal{F}$$

Shattering coefficient → Definition, Bound

$$\begin{array}{c}\mathcal{N}(\mathcal{F},n)=\underset{X_1,\dots ,X_n}{\max }|{\mathcal{F}}_{X_1,\dots ,X_n}|\\ R(f)\le R_n(f)+2\sqrt{\frac{\log \mathcal{N}(\mathcal{F},2n)-\log \delta }{n}}\end{array}$$

ERM is consistent if $\log \mathcal{N}(\mathcal{F},2n)/n\to 0$.

VC dimension and Sauer-Shelah → Sauer-Shelah

$$\begin{array}{c}\mathrm{VC}(\mathcal{F})=\max \{n:\mathcal{N}(\mathcal{F},n)=2^n\}\\ \mathcal{N}(\mathcal{F},n)\le \sum _{i=0}^d\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le (\frac{en}{d}{)}^d\end{array}$$

The growth function is either $2^n$ for all $n$ or polynomial.

VC bound → VC bound

$$R(f)\le R_n(f)+2\sqrt{\frac{d\log (2en/d)-\log \delta }{n}}$$

ERM is consistent w.r.t. $\mathcal{F}$ iff $\mathrm{VC}(\mathcal{F})<\infty$. Sample size of the order $d/{\epsilon }^2$.

VC dimensions to know → Linear, Margin, Neural networks

Class	VC dimension
linear classifiers in ${\mathbb{R}}^d$ (with offset)	$d+1$
hyperplanes with margin $\rho$, data in a ball of radius $R$	$\min \{R^2/{\rho }^2,d+1\}$
neural networks with $W$ weights	$O(W\log W)$

Rademacher complexity → Rademacher

$$\begin{array}{c}{\mathrm{Rad}}_n(\mathcal{F})=E\underset{f\in \mathcal{F}}{\sup }\frac{1}{n}\sum _{i=1}^n{\sigma }_{i}f(X_i)\\ R(f)\le R_n(f)+2{\mathrm{Rad}}_n(\mathcal{F})+\sqrt{\frac{\log (1/\delta )}{2n}}\end{array}$$

${\sigma }_i$ = independent fair coin flips with values $\pm 1$.

Algorithmic stability (Lecture 4)

Average and uniform stability → Definitions

$$\begin{array}{c}{\Delta }_{av}(A,n)=E(\frac{1}{n}\sum _{i=1}^n\ell (f(S_n),Z_i^{\prime })-\ell (f(S_n^i),Z_i^{\prime }))\\ {\Delta }_{\sup }(A,n)=\underset{i,S_n,S_n^i,Z}{\sup }|\ell (f(S_n),Z)-\ell (f(S_n^i),Z)|\end{array}$$

$S_n^i$ = $S_n$ with the $i$-th point replaced. Always ${\Delta }_{av}\le {\Delta }_{\sup }$.

Expected gap → Proposition 1

$$E(R(f(S_n))-R_{S_n}(f(S_n)))={\Delta }_{av}(A,n)$$

Stability bound → Theorem 2

$$\begin{array}{c}R(f(S_n))\le R_{S_n}(f(S_n))+{\beta }_n+(2n{\beta }_n+M)\sqrt{\frac{\log (1/\delta )}{2n}}\\ {\beta }_n={\Delta }_{\sup }(A,n)\end{array}$$

Loss bounded by $M$. The gap vanishes iff $\sqrt{n}{\beta }_n\to 0$ (which rates are good enough).

Strong convexity and smoothness → Strongly convex, Smooth

$$\begin{array}{c}f(y)\ge f(x)+\nabla f(x)(y-x)+\frac{\mu }{2}\Vert y-x{\Vert }^2\\ \Vert \nabla f(x)-\nabla f(y)\Vert \le \beta \Vert x-y\Vert \end{array}$$

$\mu$ is a lower bound on the curvature, $\beta$ an upper bound.

Stable algorithms → ERM, GD, SGD

Algorithm	Assumptions	${\Delta }_{\sup }$
ERM	loss $\mu$-strongly convex, $L$-Lipschitz	$\le \frac{4L^2}{\mu n}$
GD, SGD	convex, $\beta$-smooth, $L$-Lipschitz, ${\eta }_t<2/\beta$	$\le \frac{2L^2}{n}{\sum }_{t=1}^T{\eta }_t$
SGD	non-convex, ${\eta }_t\le c/t$	$\approx \frac{T^{1-1/(\beta c+1)}}{n}$

Regularization (Lecture 5)

Regularized risk → Principle

$$R_{reg,n}(f)=R_n(f)+\lambda \Omega (f)$$

Least squares → Full rank, General case

$$\begin{array}{c}\underset{w}{\min }\Vert Y-Xw{\Vert }^2:\\ w=(X^{t}X{)}^{-1}{X}^{t}Y(\mathrm{rank}(X)=d)\\ w=(X^{t}X{)}^{+}{X}^{t}Y\text{otherwise}\end{array}$$

Without full rank every $w+v$ with $Xv=0$ is also a solution.

Ridge regression → Solution, Stability

$$\begin{array}{c}{w}_{n,\lambda }=\underset{w}{\mathrm{argmin}}\frac{1}{n}\Vert Y-Xw{\Vert }^2+\lambda \Vert w{\Vert }^2=(X^{t}X+n\lambda I_d{)}^{-1}{X}^{t}Y\\ {\Delta }_{\sup }\le \frac{2L^2}{\lambda n}\end{array}$$

$\lambda \Vert w{\Vert }^2$ is $2\lambda$-strongly convex. The stability bound needs a convex, $L$-Lipschitz loss.

Lasso and p-norms → Lasso, p-norms

$$\begin{array}{c}{w}_{n,\lambda }=\underset{w}{\mathrm{argmin}}\frac{1}{n}\Vert Y-Xw{\Vert }_2^2+\lambda \Vert w{\Vert }_1\\ \Vert w{\Vert }_p=(\sum _{i=1}^d|w_i{|}^p{)}^{1/p},\Vert w{\Vert }_0=\#\{i:w_i\ne 0\}\end{array}$$

Convex for $p\ge 1$. The lasso has no closed form; its solutions are sparse.

Linear model and rates (fixed design, excess risk) → Model, Rates

$$\begin{array}{c}{Y}_i=⟨X_i,{\theta }^{\ast }⟩+{\epsilon }_i\\ E({\epsilon }_i)=0,E({\epsilon }_i^2)={\sigma }^2\end{array}$$

Method	Rate	Depends on
OLS	${\sigma }^{2}d/n$	$d$, fast in $n$
ridge	$\sigma \Vert {\theta }^{\ast }{\Vert }_2\sqrt{d}/\sqrt{n}$	$\sqrt{d}$
lasso	$\sigma k\sqrt{\log d}/\sqrt{n}$	$k$-sparse ${\theta }^{\ast }$, only $\log d$
$L_0$	${\sigma }^{2}k\log d/n$	$k$-sparse ${\theta }^{\ast }$, fast in $n$

Bagging and boosting (Lecture 6)

Bagging → Bagging

$$\mathrm{Var}({\hat{\Theta }}_{bag})=\rho {\sigma }^2+(1-\rho )\frac{{\sigma }^2}{B}$$

$B$ estimates with variance ${\sigma }^2$ and pairwise correlation $\rho$.

AdaBoost → Algorithm

$$\begin{array}{c}{\epsilon }_t=\sum _i{D}_{i}1[h_t(x_i)\ne y_i]\\ w_t=\frac{1}{2}\log (\frac{1}{{\epsilon }_t}-1)\\ D_i\leftarrow \frac{D_i{e}^{-w_t{y}_i{h}_t(x_i)}}{Z}\end{array}$$

Start with uniform weights $D_i=1/n$. Output $\mathrm{sign}({\sum }_t{w}_t{h}_t(x))$. ${\epsilon }_t=\frac{1}{2}$ gives $w_t=0$.

Training error → Theorem 1

$$\begin{array}{c}\text{training error}\le \prod _{t=1}^{T}2\sqrt{{\epsilon }_t(1-{\epsilon }_t)}\le \exp (-2{\gamma }^{2}T)\\ \text{if every }{\epsilon }_t\le \frac{1}{2}-\gamma \end{array}$$

Test error → VC bound

$$\mathrm{VC}({\mathcal{H}}_T)\le T\cdot \mathrm{VC}(\mathcal{B})\log (T\cdot \mathrm{VC}(\mathcal{B}))$$

The margin bound does not depend on $T$.

Gradient boosting → Gradient boosting

Fit each new base learner to the negative gradient of the loss at the current predictions. AdaBoost is the case of the exponential loss.

Features and validity (Lecture 7)

Kernel → Kernel methods

$$k(x,y)=⟨\Phi (x),\Phi (y)⟩$$

Random Fourier features → Random features

$$\begin{array}{c}{Z}_j(x)=\cos ({\omega }_j^{\top }x+b_j)\\ {\omega }_j\sim \mathcal{N}(0,{\sigma }^{-2}{I}_d),b_j\sim \mathrm{Uniform}[0,2\pi ],j=1,\dots ,D\end{array}$$

The features stay fixed and only the output weights are learned. Random ReLU features: $(w_j^{\top }x+b_j{)}_{+}$.

Four notions of validity → Validity

Validity	Question
statistical	is the difference more than chance?
internal	is it really caused by the model?
external	does it carry over to other data and settings?
construct	does the metric measure the intended concept?

Overparameterized learning (Lecture 8)

Minimum norm solution ($n<d$, GD started at $w_0=0$) → Theorem 1

$$w^{\star }=X^{\top }(X{X}^{\top }{)}^{-1}y$$

Benign overfitting in the toy setup (true function 0) → Theorem 3

$$\text{risk}={\sigma }^2\frac{n}{d-n-1}\to 0\text{for }d\gg n$$

Excess risk in both regimes (isotropic Gaussian inputs) → Theorem 4

$$\begin{array}{c}n>d+1:\frac{{\sigma }^{2}d}{n-d-1}\\ d>n+1:\underset{\text{variance}}{\underbrace{\frac{{\sigma }^{2}n}{d-n-1}}}+\underset{\text{bias}}{\underbrace{\Vert {\theta }^{\ast }{\Vert }^2\frac{d-n}{d}}}\end{array}$$

Both sides go to $\infty$ at the interpolation threshold $d\approx n$.

Why large models → Robust interpolation, NTK

$$\begin{array}{c}p\gtrsim nd\text{ parameters for interpolation with Lipschitz constant 1}\\ K_{NTK}(x,x^{\prime })=⟨{\nabla }_{w}f(w_0,x),{\nabla }_{w}f(w_0,x^{\prime })⟩\end{array}$$

Fairness (Lecture 9.1)

Group criteria → Demographic parity, Equalized odds, Predictive parity

Criterion	Formula	In a confusion table per group
demographic parity	$P(\hat{Y}=1\mid A=0)=P(\hat{Y}=1\mid A=1)$	equal $(TP+FP)/n$
equalized odds	$\hat{Y}\perp A\mid Y$	equal $TPR=\frac{TP}{TP+FN}$ and $FPR=\frac{FP}{FP+TN}$
equal opportunity	equal true positive rates	equal $TPR$
predictive parity	$Y\perp A\mid \hat{Y}$	equal $\frac{TP}{TP+FP}$
calibration by group	$P(Y=1\mid \hat{Y}=y,A=a)=y$

With different base rates, demographic parity and predictive parity cannot both hold, and neither can equalized odds and predictive parity (impossibility).

Derived classifier (post-processing) → Post-processing

$$\begin{array}{c}{p}_{ya}=P(\tilde{Y}=1\mid \hat{Y}=y,A=a)\\ {\mathrm{TPR}}_a(\tilde{Y})=p_{1a}{\mathrm{TPR}}_a+p_{0a}(1-{\mathrm{TPR}}_a)\end{array}$$

The same formula holds for the false positive rate.

Explainability and law (Lecture 9.2)

SHAP → Definition

$${\Phi }_i(f,x)=\sum _{S\subseteq F\setminus \{i\}}\frac{|S|!(|F|-|S|-1)!}{|F|!}[v(x,S\cup \{i\})-v(x,S)]$$

$F$ = all features. The values add up: ${\sum }_i{\Phi }_i=f(x)-Ef(X)$.

Value functions → Observational vs. interventional

$$\begin{array}{c}{v}_{obs}(x,S)=E[f(X)\mid X_S=x_S]\\ v_{int}(x,S)=E_{X_{\bar{S}}}f(x_S,X_{\bar{S}})\end{array}$$

SHAP for a GAM $f(x)={\sum }_i{f}_i(x_i)$ (interventional) → Theorem 1

$${\Phi }_i=f_i(x_i)-E{f}_i(X_i)$$

EU AI Act → AI Act

Risk categories: prohibited, high, limited, minimal. GPAI models count as systemic risk above $10^{25}$ FLOPs of training compute.

Related

• Course: Overview · Glossary · Concepts · Math Foundations