Glossary

Every term of the course in one line, A to Z. In the “See” column, a lecture number (L3, L9.1, …) links to the lecture section, “Math” to the math foundations, every other link to the term’s concept page. Formulas are on the Formula Sheet.

Words that mean two things

• Bias is the inductive bias (what the learner assumes, L1.1), the bias term of the bias-variance decomposition (L1.2) and bias in data that leads to unfair decisions (L7, L9.1).
• Margin is the distance of the closest point to a hyperplane (L2) and the product $yf(x)$ of a scoring function (L1.1, the margin bound in L6).
• Consistent means $R(f_n)\to R^{\ast }$ (L1.2), but consistent w.r.t. $\mathcal{F}$ only means $R(f_n)\to R(f_{\mathcal{F}})$ (L3).
• Calibrated: a classification-calibrated loss gives the Bayes classifier after thresholding (L1.1); a score calibrated by group means the same probability in every group (L9.1).
• Stability: average stability equals the expected generalization gap, uniform stability gives the high-probability bound (L4).

0-9

Term	Meaning	See
0-1 loss	0 for a correct prediction, 1 for a wrong one; its risk is the probability of error	Loss and Risk

A

Term	Meaning	See
AdaBoost	boosting by reweighting: the weak learner $h_t$ with weighted error ${\epsilon }_t$ gets the vote $w_t=\frac{1}{2}\log (\frac{1}{{\epsilon }_t}-1)$, misclassified points gain weight	AdaBoost
AI Act	EU law that regulates AI applications by risk: prohibited, high, limited, minimal, plus rules for GPAI models	AI Regulation
Algorithmic stability	the learned function changes only a little when one training point is replaced; a stable algorithm generalizes	Algorithmic Stability
Almost sure convergence	$P({\lim }_i{U}_i=U)=1$; implies convergence in probability	L1.2
Approximation error	$R(\tilde{f})-R(f^{\ast })$, the price of the class $\mathcal{F}$; deterministic, shrinks when $\mathcal{F}$ grows	Estimation and Approximation Error
Average stability ${\Delta }_{av}$	expected loss change on the replaced point; equals the expected generalization gap (Proposition 1 of L4)	Algorithmic Stability

B

Term	Meaning	See
Bagging	bootstrap aggregation: average the estimates of $B$ bootstrap samples; variance $\rho {\sigma }^2+(1-\rho )\frac{{\sigma }^2}{B}$ instead of ${\sigma }^2$	Bagging
Base rate	$P(Y=1)$ within a group; different base rates make some fairness criteria incompatible	L9.1
Bayes classifier, Bayes predictor $f^{\ast }$	a function with the smallest possible risk; for the 0-1 loss: predict 1 iff $\eta (x)\ge \frac{1}{2}$	Bayes Classifier
Bayes decision rule	predict the label with the smallest conditional risk, using priors and the costs of the errors	Bayesian Decision Theory
Bayes risk $R^{\ast }$	${\inf }_{f}R(f)$, the best risk any function can reach	Bayes Classifier
Benign overfitting	an interpolator fits noisy labels exactly and still has a small test error	Benign Overfitting
$\beta$-smooth	the gradient is $\beta$-Lipschitz: an upper bound on the curvature	Smoothness
Bias (bias-variance)	how far the average prediction over training samples is from the truth	Bias-Variance Decomposition
Bias-variance decomposition	for the $L_2$ loss, pointwise: $E(f_n(x)-f^{\ast }(x){)}^2=\text{variance}+{\text{bias}}^2$	Bias-Variance Decomposition
Boosting	combine many weak learners with specific weights into a strong one; reduces bias	AdaBoost
Boosting class ${\mathcal{H}}_T$	all $\mathrm{sign}({\sum }_t{w}_t{h}_t)$ with $h_t$ from the base class; $\mathrm{VC}({\mathcal{H}}_T)\lesssim T\cdot \mathrm{VC}(\mathcal{B})\log (T\cdot \mathrm{VC}(\mathcal{B}))$	L6
Bootstrap	judge an estimate by recomputing it on resamples drawn from the data	L6

C

Term	Meaning	See
Calibration by group	$P(Y=1\mid \hat{Y}=y,A=a)=y$: a score means the same probability in every group	Fairness Criteria
Classical regime	$\mathcal{F}$ cannot interpolate the training data; the test risk is U-shaped	L1.2
Classification-calibrated	a surrogate loss whose Bayes predictor, thresholded at 0, is the 0-1 Bayes classifier	Surrogate Loss
Conditional risk	expected loss of predicting $\hat{y}$ at a fixed $x$; only the label is random	Bayesian Decision Theory
Consistency	$R(f_n)\to R^{\ast }$ in probability; a statement about the risk, not about $f_n\to f^{\ast }$	Consistency
Consistency w.r.t. $\mathcal{F}$	$R(f_n)\to R(f_{\mathcal{F}})$: only the estimation error goes to 0	L3
Construct validity	does the metric measure the concept we care about?	Validity
Convergence in probability	$P(|U_i-U|>\epsilon )\to 0$ for every $\epsilon >0$	L1.2
Counterfactual explanation	the smallest change of the input that flips the decision	Counterfactual Explanation
Counterfactual fairness	uses a causal model to ask what the outcome would have been had other variables been different	L9.1

D

Term	Meaning	See
Datasheet	documentation of a data set: motivation, composition, collection, recommended uses (Gebru et al. 2018)	L7
Decision stump	a tree with a single split; the usual weak learner in AdaBoost	AdaBoost
Demographic parity	$\hat{Y}\perp A$: both groups get positive decisions at the same rate (independence)	Fairness Criteria
Derived classifier	fairness post-processing: a randomized $\tilde{Y}$ from $\hat{Y}$ and $A$ with four probabilities $p_{ya}$	Fair Post-Processing
Design matrix $X$	$n\times d$ matrix with one training point per row	L5
Double descent	the test error rises towards the interpolation threshold and can fall again beyond it	Double Descent

E

Term	Meaning	See
Empirical risk $R_n$	average loss on the training points; for the 0-1 loss the training error	Loss and Risk
Empirical risk minimization (ERM)	pick $f_n={\mathrm{argmin}}_{f\in \mathcal{F}}{R}_n(f)$	Empirical Risk Minimization
Equal opportunity	equal true positive rates in all groups	Fairness Criteria
Equalized odds	$\hat{Y}\perp A\mid Y$: equal true and false positive rates in all groups (separation)	Fairness Criteria
Estimation error	$R(f_n)-R(\tilde{f})$; random, grows with the size of $\mathcal{F}$	Estimation and Approximation Error
Excess risk	risk minus the best possible risk, e.g. $R(f_n)-R^{\ast }$	Estimation and Approximation Error
Exponential loss	$\exp (-yf(x))$; the loss behind AdaBoost	Surrogate Loss
External validity	does the result carry over to other data and settings?	Validity

F

Term	Meaning	See
Feature attribution	a score per input feature for how much it mattered for one decision	Feature Attribution
Feature map $\Phi$	turns an object into a vector of numbers in ${\mathbb{R}}^d$	Kernel Methods
Feedback loop	predictions change the data the next model is trained on and become self-fulfilling	L9.1
Fixed design	the input points are fixed and only the labels are random; risk on these points	L5
Forward stagewise additive modeling	add one base function at a time and freeze the earlier ones; AdaBoost is the case of the exponential loss	L6

G

Term	Meaning	See
GAM	generalized additive model $f(x)={\sum }_i{f}_i(x_i)$; interpretable, and interventional SHAP recovers the $f_i$	SHAP
GDPR	EU data protection: lawful basis and consent, data minimization, purpose limitation, right to be forgotten	AI Regulation
Generalization bound	true risk $\le$ empirical risk + capacity term, with probability at least $1-\delta$	Generalization Bound
Generalization gap	$R(f_n)-R_n(f_n)$, true minus empirical risk of the learned function	L4
Generalized inverse $A^{+}$	inverts $A$ on the eigenvectors with non-zero eigenvalues (Moore-Penrose)	L5
GPAI model	general-purpose AI model in the AI Act; systemic risk above $10^{25}$ FLOPs of training compute	AI Regulation
Gradient boosting	fit each new base learner to the negative gradient of the loss	Gradient Boosting
Gradient descent	$w_{t+1}=w_t-\eta \nabla R_n(w_t)$	Stochastic Gradient Descent
Growth function	the shattering coefficient as a function of $n$; either $2^n$ or polynomial	Shattering Coefficient

H

Term	Meaning	See
Hinge loss	$\max (0,1-yf(x))$; a classification-calibrated surrogate	Surrogate Loss
Hoeffding’s inequality	independent $Z_i\in [0,1]$: $P(|S_n-E(S_n)|\ge \epsilon )\le 2\exp (-2n{\epsilon }^2)$	Hoeffding Inequality

I

Term	Meaning	See
i.i.d.	independent and identically distributed; how the training points are drawn	Math
Implicit regularization	the optimizer picks one special solution among many, e.g. GD from 0 finds the minimum norm solution	Implicit Regularization
Individual fairness	individuals that are similar under a pre-specified metric get similar treatment	L9.1
Inductive bias	the assumptions about what we look for; without one, learning is impossible (No Free Lunch)	Inductive Bias
Inductive inference	from specific examples to a general rule; the conclusion can be wrong	L1.1
Internal validity	is the effect really caused by the model, and not by artifacts or confounders?	Validity
Interpolation threshold	as many parameters as data points; the peak of the double descent curve	Double Descent
Interventional value function	fix $x_S$ and draw the other features from their marginal distribution	SHAP

K

Term	Meaning	See
Kernel, kernel trick	$k(x,y)=⟨\Phi (x),\Phi (y)⟩$, computed without computing $\Phi$	Kernel Methods

L

Term	Meaning	See
Lasso	least squares $+\lambda \Vert w{\Vert }_1$; sparse solutions, no closed form	Lasso
Law of large numbers	the empirical mean converges to the expectation; for a fixed $f$, $R_n(f)\to R(f)$	Math
Least squares	minimize $\Vert Y-Xw{\Vert }^2$; $w=(X^{t}X{)}^{-1}{X}^{t}Y$ if $X$ has full rank	Least Squares Regression
Leave-one-out	train without one point, test on it; the average is an unbiased estimate of the generalization error	Leave-One-Out Error
LIME	explains one decision by a linear model fitted on samples around $x$	LIME
Linear loss	$\max \{0,-y⟨w,x⟩\}$; the perceptron is SGD on it	L2
Lipschitz	$|f(x)-f(y)|\le L\Vert x-y\Vert$	Math
Loss function	$\ell (x,y,y^{\prime })\ge 0$: how expensive it is to predict $y^{\prime }$ when the truth is $y$	Loss and Risk

M

Term	Meaning	See
MAP	maximum a posteriori: predict the label with the largest posterior; for the 0-1 loss this is the Bayes classifier	Bayesian Decision Theory
Margin (hyperplane)	smallest distance of a training point to the hyperplane, ${\min }_i{y}_i⟨w,x_i⟩/\Vert w\Vert$	Margin
Margin (score)	$yf(x)$; positive iff the point is classified correctly	Margin
Margin bound	test error bound for boosting that does not depend on $T$	L6
Maximum likelihood	predict the label with the largest $p(x\mid y)$; ignores the priors	Bayesian Decision Theory
McDiarmid’s inequality	concentration for a function of independent variables whose value changes by at most $c_i$ in coordinate $i$	L3
Measurement procedure	the device that records the construct; machine learning learns the measurement, not the construct	Measurement and Construct
Minimum norm solution	the interpolating $w$ with the smallest norm, $X^{\top }(X{X}^{\top }{)}^{-1}y$	Implicit Regularization
Mistake bound	the perceptron makes at most $R^2/{\rho }^2$ mistakes on separable data	Perceptron
Modern regime	$\mathcal{F}$ is large enough to interpolate the training data	L1.2

N

Term	Meaning	See
Neural tangent kernel (NTK)	very wide networks train like a kernel method with $⟨{\nabla }_{w}f(w_0,x),{\nabla }_{w}f(w_0,x^{\prime })⟩$; no feature learning	Neural Tangent Kernel
No Free Lunch	averaged over all possible true functions, all classifiers perform the same	No Free Lunch Theorem

O

Term	Meaning	See
Observational value function	average $f$ over the points with $X_S=x_S$ (conditional distribution)	SHAP
OLS	ordinary least squares, no regularizer; excess risk ${\sigma }^{2}d/n$ in the fixed design	L5
Over-parameterized regime	more parameters than data points; the model can interpolate	L8
Overfitting	classical regime: the class is too large, low approximation error, high estimation error	L1.2

P

Term	Meaning	See
PAC learnable	strong: error $\le \epsilon$ with probability $\ge 1-\delta$ for all $\epsilon ,\delta$; weak: error $\le \frac{1}{2}-\gamma$; both are equivalent	L6
Perceptron	after every mistake update $w\leftarrow w+y_t{x}_t$; SGD with step size 1 on the linear loss	Perceptron
Plug-in classifier	estimate $\eta$ from the data and threshold the estimate like the Bayes classifier	L1.2
Predictive parity	$Y\perp A\mid \hat{Y}$: a prediction means the same in every group (sufficiency)	Fairness Criteria
Protected attribute $A$	sensitive attribute such as gender or race	L9.1
Proxy	a measurable stand-in for the construct, e.g. health care cost for illness	Measurement and Construct

R

Term	Meaning	See
Rademacher complexity	how well $\mathcal{F}$ can fit random $\pm 1$ labels	Rademacher Complexity
Random design	the data is random and we care about the test error	L5
Random features	basis functions with random, frozen parameters; only the output weights are learned; they approximate a kernel	Random Features
Random forest	bagged decision trees; each split chooses its dimension from a random subset ($m\approx d/3$)	Random Forest
Regression function $\eta$	$\eta (x)=E(Y\mid X=x)$; for labels 0 and 1 it is $P(Y=1\mid X=x)$	Bayes Classifier
Regularization	minimize $R_n(f)+\lambda \Omega (f)$ with a regularizer $\Omega$ that measures complexity	Regularization
Representation learning	learn the features from raw data instead of fixing them by hand	L7
Ridge regression	least squares $+\lambda \Vert w{\Vert }^2$; $w=(X^{t}X+n\lambda I_d{)}^{-1}{X}^{t}Y$ (Tikhonov)	Ridge Regression
Robust interpolation	interpolating with Lipschitz constant about 1 needs $p\gtrsim nd$ parameters (Bubeck and Selke)	L8

S

Term	Meaning	See
Sauer-Shelah lemma	VC dimension $d$: $\mathcal{N}(\mathcal{F},n)\le {\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{n}{i}\right)\le (en/d{)}^d$	L3
Scoring function	a real-valued $f$; the classifier is $\mathrm{sign}(f(x))$	Surrogate Loss
SGD	stochastic gradient descent: a gradient step on one random training point	Stochastic Gradient Descent
SHAP	Shapley values of the features for one prediction	SHAP
Shattering	$\mathcal{F}$ realizes all $2^n$ labelings of the points	VC Dimension
Shattering coefficient $\mathcal{N}(\mathcal{F},n)$	the largest number of labelings $\mathcal{F}$ produces on $n$ points	Shattering Coefficient
Sparsity	many coefficients exactly 0; the lasso gets it from the corners of the ${\ell }_1$ ball	Lasso
Spiky-smooth	an interpolator with narrow spikes at the training points that is smooth everywhere else	Benign Overfitting
Statistical validity	is the difference more than chance?	Validity
Strong convexity	$\mu$-strongly convex: a lower bound $\mu$ on the curvature	Strong Convexity
Strongly consistent	the risk converges to $R^{\ast }$ almost surely	Consistency
Surrogate loss	a convex loss on a real score used instead of the 0-1 loss (hinge, squared, exponential, logistic)	Surrogate Loss
Symmetrization	compare with a ghost sample, so the supremum runs over finitely many labelings	L3

T

Term	Meaning	See
Target construct	the concept we want to measure, often not observable	Measurement and Construct
Tikhonov regularization	regularizer $\lambda \Vert w{\Vert }^2$, as in ridge regression; makes ERM strongly convex and stable	Ridge Regression
True risk $R(f)$	$E(\ell (X,Y,f(X)))$, the expected loss on new data	Loss and Risk

U

Term	Meaning	See
Underfitting	classical regime: the class is too small, high approximation error	L1.2
Uniform convergence	${\sup }_{f\in \mathcal{F}}|R_n(f)-R(f)|\to 0$ in probability; sufficient and necessary for ERM to be consistent	Uniform Convergence
Uniform stability ${\Delta }_{\sup }$	worst-case loss change when one training point is replaced	Algorithmic Stability
Union bound	$P({\bigcup }_i{A}_i)\le {\sum }_{i}P(A_i)$; gives the bound for finite classes	Math
Universal approximation	two-layer networks with a continuous, non-polynomial activation approximate every continuous function on a compact set	Universal Approximation
Universally consistent	consistent for every distribution $P$; kNN is (Stone 1977)	Consistency

V

Term	Meaning	See
Validity	four notions: statistical, internal, external, construct	Validity
Variance (bias-variance)	how much the prediction changes from one training sample to another	Bias-Variance Decomposition
VC dimension	the largest $n$ such that some $n$ points are shattered	VC Dimension

W

Term	Meaning	See
Weak learner	only slightly better than random guessing: error $\frac{1}{2}-\gamma$	L6

X

Term	Meaning	See
XGBoost	an efficient implementation of gradient boosting with trees	L6

Related

• Course: Overview · Formula Sheet · Concepts · Math Foundations