Statistics

Motivation

Chapter 4 showed that uniform convergence suffices for learnability; Chapter 26 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), measures its rate. The representativeness of a sample, $\sup_{h \in H}(L_D(h) - L_S(h))$, is the quantity that controls the excess risk of ERM, and the Rademacher complexity $R(F \circ S) = \frac1m\mathbb{E}_\sigma\sup_{f \in F}\sum_i\sigma_i f(z_i)$ estimates it from the sample itself: the symmetrization argument gives $\mathbb{E}\operatorname{Rep} \le 2\,\mathbb{E}R$ (Lemma 26.2), and McDiarmid's bounded-differences inequality turns expectations into high-probability statements, yielding the generalization bounds of Theorem 26.5, including the data-dependent ones in which the complexity is computed on the training set. A small calculus of Rademacher complexities follows, affine images, convex hulls, Massart's lemma for finite sets and the contraction lemma for Lipschitz compositions, and it is applied to linear classes with $\ell_2$ and $\ell_1$ constraints. The chapter's payoff is dimension-free generalization bounds for linear predictors with Lipschitz losses (Theorem 26.12), for hard-SVM (Theorems 26.13–26.14), and for predictors with low $\ell_1$ norm (Theorem 26.15).

Setting

For a loss class $F = \ell \circ H$ and a sample $S = (z_1, \dots, z_m)$, $\operatorname{Rep}_D(F, S) = \sup_{f \in F}(L_D(f) - L_S(f))$ (26.1), $F \circ S = \{(f(z_1), \dots, f(z_m)) : f \in F\}$, and for $A \subseteq \mathbb{R}^m$, $R(A) = \frac1m\mathbb{E}_\sigma[\sup_{a \in A}\sum_i\sigma_i a_i]$ with $\sigma$ uniform on $\{\pm1\}^m$ (26.5). The linear classes are $H_2 \circ S = \{(\langle w, x_i\rangle)_i : \|w\|_2 \le 1\}$ in a Hilbert space and $H_1 \circ S$ with $\|w\|_1 \le 1$ in $\mathbb{R}^n$ (26.14). Losses of the form $\ell(w, (x, y)) = \varphi(\langle w, x\rangle, y)$ with $a \mapsto \varphi(a, y)$ $\rho$-Lipschitz (26.18) cover the hinge and absolute losses.

Formalization targets

Goal: Theorem 26.5

Assume $|\ell(h, z)| \le c$ for all $z$ and $h \in H$. Then, each with probability at least $1 - \delta$ over $S \sim D^m$:

1. for all $h \in H$, $L_D(h) - L_S(h) \le 2\,\mathbb{E}_{S' \sim D^m}R(\ell \circ H \circ S') + c\sqrt{2\ln(2/\delta)/m}$;
2. for all $h \in H$, $L_D(h) - L_S(h) \le 2R(\ell \circ H \circ S) + 4c\sqrt{2\ln(4/\delta)/m}$;
3. for any $h^\star \in H$, $L_D(\mathrm{ERM}_H(S)) - L_D(h^\star) \le 2R(\ell \circ H \circ S) + 5c\sqrt{2\ln(8/\delta)/m}$.

Milestones

Lemma 26.2 (symmetrization); Lemma 26.8 (Massart); Lemma 26.9 (contraction); Theorem 26.12 (linear predictors with $\ell_2$ constraints); Theorem 26.13 (hard-SVM). Further items: Theorem 26.3, Lemma 26.4 (McDiarmid), Lemmas 26.6, 26.7, 26.10, 26.11, Theorem 26.14 and Theorem 26.15.

Significance

Rademacher complexity is the modern language of uniform convergence: it is data-dependent, it is dimension-free for linear classes, and it composes with Lipschitz losses, which is why the SVM bounds of this chapter do not depend on the dimension of $w$ and apply verbatim to kernel methods (Remark 26.2). Theorem 26.5 is the template every such bound follows, symmetrization plus McDiarmid, and the two data-dependent parts are the first bounds in the book that use the training set both to learn and to certify. Massart's lemma and the contraction lemma are the two tools that make the calculus work, the first converting finiteness into a logarithmic dependence, the second removing the loss function from the picture. Theorem 26.13 finally justifies the margin-based sample complexity $R^2\|w^\star\|^2/\epsilon^2$ of hard-SVM, and Theorem 26.14 gives a bound computable from the output alone.

Difficulty

Lemma 26.2 is the symmetrization argument: a ghost sample, the exchange of $z_j$ and $z'_j$ (26.7), the introduction of one Rademacher sign at a time (26.8)–(26.9), and the split of the supremum. Formally it needs Fubini over the product of $2m$ copies of $D$ and the sign average, and the measurability of the suprema, which the statements assume. McDiarmid's inequality is a martingale argument with Hoeffding's lemma at each step; it is the substantial probabilistic input, and Theorem 26.5 combines it with Lemma 26.2, a union bound and Hoeffding's inequality along the decomposition (26.10). Lemma 26.6 is the symmetry $\sigma \mapsto -\sigma$; Lemma 26.7 is the fact that a linear functional on the simplex is maximized at a vertex; Massart's lemma is the exponential-moment bound $\mathbb{E}e^{\sigma a} \le e^{a^2/2}$ with Jensen and an optimized scaling; the contraction lemma is Kakade and Tewari's coordinate-by-coordinate argument (26.12)–(26.13), which in a formal proof must be run as an induction over the coordinates. Lemmas 26.10 and 26.11 are Cauchy–Schwarz and Hölder followed by Jensen, respectively Massart on the $2n$ coordinate vectors. Theorem 26.12 chains contraction, Lemma 26.10 and Theorem 26.5 on the almost-sure event $\|x\| \le R$; Theorem 26.13 specializes it to the ramp loss with $B = \|w^\star\|$, where the hard-SVM output has zero empirical ramp loss; Theorem 26.14 is a union bound over the nested classes $\|w\| \le 2^i$ with $\delta_i = \delta/(2i^2)$; Theorem 26.15 repeats Theorem 26.12 with Lemma 26.11.

Formalization scope

The Rademacher complexity is a finite average over the $2^m$ sign vectors, so no measure on $\{\pm1\}^m$ is needed, and the supremum over $A$ is the real supremum over the subtype $A$; the theorems assume $A$ nonempty and bounded, which every evaluation set of a bounded loss class satisfies. Risks are Mission I's risk and empRisk, samples are Fin m-indexed under iidLaw, and probability statements bound the outer measure of the failure event. Expectations of suprema over uncountable classes are Bochner integrals, so Lemma 26.2, Theorem 26.3 and Theorem 26.5 carry explicit hypotheses that $S \mapsto \operatorname{Rep}_D(F, S)$ and $S \mapsto R(F \circ S)$ are measurable, the book's Remark 3.1 made visible; for the linear classes of §26.3–§26.4 these hold automatically when the Hilbert space is separable (the supremum over the ball is a supremum over a countable dense subset), which is why Theorems 26.12–26.14 assume SecondCountableTopology. McDiarmid's inequality is stated for a measurable function on a product of arbitrary probability measures. Theorem 26.13's error is $P[y\langle w_S, x\rangle \le 0]$, which dominates $P[y \ne \operatorname{sign}\langle w_S, x\rangle]$ whatever $\operatorname{sign}(0)$ is, and the hard-SVM learner is any map returning a minimum-norm margin-1 separator on separable samples; measurability of the learner is not needed because the bound is uniform over the ball. Theorem 26.14 is given with the constants of its proof, $\sqrt{4(\ln(4\log_2\|w_S\|) + \ln(1/\delta))/m}$ rather than the printed $\sqrt{\ln(4\log_2\|w_S\|/\delta)/m}$, and for $\|w_S\| \ge 2$, where $i = \lceil\log_2\|w_S\|\rceil$ satisfies $1 \le i \le 2\log_2\|w_S\|$ as the proof requires; the item text records this. Norms on $\mathbb{R}^n$ as Fin n → ℝ are sup norms (Lemma 26.11, Theorem 26.15), Euclidean norms are written out (Massart), and inner product spaces carry the Euclidean norm.

Not stated: Definition 26.1 (already Mission II's IsRepresentative), the validation heuristic (26.2)–(26.3), Remark 26.1 (the improved rate under separability, no proof), Remark 26.2.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 26. doi:10.1017/CBO9781107298019
• P. L. Bartlett, S. Mendelson, Rademacher and Gaussian complexities: risk bounds and structural results, Journal of Machine Learning Research 3, 2002.
• V. Koltchinskii, D. Panchenko, Rademacher processes and bounding the risk of function learning, in High Dimensional Probability II, Birkhäuser, 2000. doi:10.1007/978-1-4612-1358-1_29
• C. McDiarmid, On the method of bounded differences, in Surveys in Combinatorics, Cambridge University Press, 1989. doi:10.1017/CBO9781107359949.008
• S. M. Kakade, K. Sridharan, A. Tewari, On the complexity of linear prediction: risk bounds, margin bounds, and regularization, NIPS 2008.
• S. Boucheron, O. Bousquet, G. Lugosi, Theory of classification: a survey of some recent advances, ESAIM: Probability and Statistics 9, 2005. doi:10.1051/ps:2005018

Motivation

Every learning paradigm of the book so far, ERM, SRM, MDL, RLM, is defined by a hypothesis class: the learner searches a predefined set of functions. Nearest Neighbor is the first method that is not. It memorizes the training set and labels a new point by the labels of its closest neighbors, on the assumption that the features are relevant to the labels in a way that makes close-by points likely to share a label. Chapter 19 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), makes that assumption precise, a Lipschitz conditional probability, and proves a finite-sample guarantee: the expected error of the 1-NN rule on $m$ examples is at most twice the Bayes error plus $4c\sqrt d\, m^{-1/(d+1)}$ (Theorem 19.3). The classical results of Cover and Hart (1967) and Stone (1977) are asymptotic; the book insists, as it did in §7.4, on a bound that says what a finite sample buys under an explicit prior assumption. The chapter also proves that the exponential dependence on the dimension is not an artifact (Theorem 19.4, the curse of dimensionality) and, in its exercises, extends the analysis to the $k$-NN rule, whose error converges to $(1 + \sqrt{8/k})$ times the Bayes error (Theorem 19.5).

Setting

The instance domain $X$ carries a metric $\rho$; for the analysis $X = [0,1]^d$ with the Euclidean distance and $Y = \{0,1\}$ with the 0–1 loss. For a sample $S = (x_1, y_1), \dots, (x_m, y_m)$ and a point $x$, let $\pi_1(x), \dots, \pi_m(x)$ reorder the sample by distance to $x$. The $k$-NN rule returns the majority label among $y_{\pi_1(x)}, \dots, y_{\pi_k(x)}$; the 1-NN rule is $h_S(x) = y_{\pi_1(x)}$; in general, for $\varphi : (X \times Y)^k \to Y$, the $k$-NN rule with respect to $\varphi$ is $h_S(x) = \varphi\big((x_{\pi_1(x)}, y_{\pi_1(x)}), \dots, (x_{\pi_k(x)}, y_{\pi_k(x)})\big)$ (19.1).

A distribution $D$ over $X \times Y$ has marginal $D_X$ and conditional probability $\eta(x) = P[y = 1 \mid x]$; the Bayes optimal rule is $h^\star(x) = \mathbb{1}[\eta(x) > 1/2]$, and the standing assumption is that $\eta$ is $c$-Lipschitz: $|\eta(x) - \eta(x')| \le c\|x - x'\|$. In the formalization a distribution with conditional probability $\eta$ is written condLaw DX η: draw $x \sim D_X$, then $y \sim \mathrm{Bernoulli}(\eta(x))$. Every distribution with a regression function is of this form, so nothing is lost.

Formalization targets

Goal: Theorem 19.3

For $X = [0,1]^d$, $Y = \{0,1\}$, a distribution $D$ over $X \times Y$ whose conditional probability $\eta$ is $c$-Lipschitz, and $h_S$ the result of the 1-NN rule on $S \sim D^m$,

$$\mathbb{E}_{S \sim D^m}[L_D(h_S)] \le 2L_D(h^\star) + 4c\sqrt d\, m^{-\frac{1}{d+1}}.$$

Milestones

Lemma 19.1 (the Lipschitz reduction: $\mathbb{E}_S[L_D(h_S)] \le 2L_D(h^\star) + c\,\mathbb{E}_{S,x}\|x - x_{\pi_1(x)}\|$); Lemma 19.2 (the expected mass of the sets among $C_1, \dots, C_r$ missed by an i.i.d. sample of size $m$ is at most $r/(me)$); Theorem 19.4 (for integer $c \ge 2$ and every learning rule there is a distribution with $c$-Lipschitz $\eta$ and Bayes error $0$ on which the rule's expected error is at least $1/4$ whenever $2m \le (c+1)^d$); Lemma 19.7 (the majority of $k \ge 10$ independent Bernoulli labels errs, against a label drawn from their mean $p$, at most $(1 + \sqrt{8/k})$ times as often as $\mathbb{1}[p > 1/2]$); Theorem 19.5 (the $k$-NN bound $\mathbb{E}_S[L_D(h_S)] \le (1 + \sqrt{8/k})L_D(h^\star) + (6c\sqrt d + k)m^{-1/(d+1)}$). Lemma 19.6, the $k$-fold version of Lemma 19.2 with bound $2rk/m$, is a further item.

Significance

Theorem 19.3 is the book's answer to the question it raised in §7.4: consistency results say that the 1-NN error converges to twice the Bayes error, but not how fast, and the rate necessarily depends on the distribution. The Lipschitz constant $c$ and the dimension $d$ are exactly the prior knowledge the rule relies on, and Theorem 19.4 shows through the No-Free-Lunch theorem that a sample of size exponential in $d$ is genuinely required for some distributions in the class. Theorem 19.5 quantifies what larger $k$ buys, the factor $2$ improving to $1 + \sqrt{8/k}$, at the price of the additive term growing linearly in $k$. On the platform, this mission introduces the conditional-probability model of a distribution over $X \times \{0,1\}$ and the Bayes rule, which Chapters 24 (generative models) and the nonparametric parts of the book use again, and the box-cover argument of Lemma 19.2, a small combinatorial-probability tool of independent use.

Difficulty

Lemma 19.1 is a computation once the expectation over $S$ and $(x, y)$ is decomposed as the book does: sample the unlabeled points first, find the nearest neighbor, then draw the two labels; the identity $P[y \ne y'] = 2\eta(x)(1 - \eta(x)) + (\eta(x) - \eta(x'))(2\eta(x) - 1)$ and $L_D(h^\star) = \mathbb{E}_x\min\{\eta, 1 - \eta\} \ge \mathbb{E}_x\,\eta(1 - \eta)$ finish it. Formally the work is in the decomposition itself, which is Fubini for condLaw and the product law, and in the measurability of the rule, which the statement assumes. Lemma 19.2 is $\mathbb{E}[\mathbb{1}[C_i \cap S = \emptyset]] = (1 - P[C_i])^m \le e^{-P[C_i]m}$ and $\max_a ae^{-ma} \le 1/(me)$. Theorem 19.3 covers the cube by boxes of side $\varepsilon$, applies Lemma 19.2 to the boxes and sets $\varepsilon = 2m^{-1/(d+1)}$; a formal proof must handle $1/\varepsilon$ not being an integer (take $T = \lceil 1/\varepsilon \rceil$ boxes per side, so $r \le (2/\varepsilon)^d$ when $\varepsilon \le 1$, which is what the book's $2^d\varepsilon^{-d}$ already allows for) and the regime $m < 2^{d+1}$, where the trivial bound $\mathbb{E}\|x - x_{\pi_1(x)}\| \le \sqrt d$ suffices. Theorem 19.4 is the No-Free-Lunch theorem on the grid of spacing $1/c$, plus the observation that any $\{0,1\}$-valued function on the grid extends to a $c$-Lipschitz $[0,1]$-valued function on the cube (McShane). Lemma 19.6 is Chernoff's bound below the mean; Lemma 19.7 is the delicate one: Chernoff with the function $h(a) = (1 + a)\log(1 + a) - a$ and the inequality $(1 - 2p)e^{-kp + \frac k2(\log(2p) + 1)} \le \sqrt{8/k}\,p$ for $p \in [0, 1/2]$, $k \ge 10$, which the book states without proof. Theorem 19.5 assembles Lemmas 19.6 and 19.7 along the four steps of Exercise 4; to reach the book's constants with an integer number of boxes one takes $T = \lceil m^{1/(d+1)}/2.07 \rceil$ boxes per side and Chernoff at $\delta = 1/3$ in Lemma 19.6, or notes that the bound is trivial unless $m^{1/(d+1)} > 6c\sqrt d + k$.

Formalization scope

Labels are Bool; bernoulliLaw p is the Bernoulli law on Bool, condLaw DX η the distribution with marginal DX and conditional probability η, and bayesRule η the Bayes rule. The cube is the subtype cube d of EuclideanSpace ℝ (Fin d), so its metric is Euclidean and its Borel structure is inherited; the Lipschitz hypothesis is LipschitzWith c η with c : ℝ≥0, together with η x ∈ [0,1] (a conditional probability). A $k$-NN rule is a learner h with IsKNNRuleWith k φ h: for every sample of size $m \ge k$ and every $x$ there is some reordering of the sample by distance to $x$ whose first $k$ entries feed $\varphi$; ties are therefore broken arbitrarily, and the theorems hold for every choice. Majority votes predict $1$ iff strictly more than half of the $k$ labels are $1$, the book's $\mathbb{1}[p' > 1/2]$ of Lemma 19.7. The nearest-neighbor distance is nnDist S x = ⨅ i, dist x (S i).1. Expectations over $S \sim D^m$ are Bochner integrals against iidLaw D m (Mission I), and the expectation statements assume the rule is measurable in $(S, x)$, the book's Remark 3.1; without it the integrals would be junk. Lemmas 19.2 and 19.6 are stated for arbitrary measurable subsets of an arbitrary measurable space, as in the book, with $m \ge 1$ (for $m = 0$ the left side is $\sum_i P[C_i]$ while Lean reads $r/(0 \cdot e)$ as $0$). Lemma 19.7 uses the product of Bernoulli laws on Fin k → Bool.

Two statements are given as their proofs support them, and the deviations are recorded in the item texts. Theorem 19.4 takes $c \ge 2$ an integer (the grid has spacing $1/c$), fixes $m$ with $2m \le (c+1)^d$ before choosing the distribution (Theorem 5.1 produces a distribution per $m$), and concludes that the expected true error is at least $1/4$ (Equation (5.2) in the proof of Theorem 5.1; the book's "greater than $1/4$" is what its proof gives for $2m < (c+1)^d$ only in the form of that expectation). Theorem 19.5 keeps the book's constants; the drafter checked that they are reachable with an integer number of boxes. Not stated: the general weighted-average rules of §19.1 beyond (19.1), the efficient implementation of §19.3, Exercise 3 (a one-line inequality, absorbed into the proof of Theorem 19.5).

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 19. doi:10.1017/CBO9781107298019
• T. Cover, P. Hart, Nearest neighbor pattern classification, IEEE Transactions on Information Theory 13(1), 1967. doi:10.1109/TIT.1967.1053964
• C. J. Stone, Consistent nonparametric regression, Annals of Statistics 5(4), 1977. doi:10.1214/aos/1176343886
• L. Devroye, L. Györfi, G. Lugosi, A Probabilistic Theory of Pattern Recognition, Springer, 1996. doi:10.1007/978-1-4612-0711-5
• L.-A. Gottlieb, A. Kontorovich, R. Krauthgamer, Efficient classification for metric data, COLT 2010; IEEE Transactions on Information Theory 60(9), 2014. doi:10.1109/TIT.2014.2339840

Motivation

The sample complexity of learning halfspaces in $\mathbb{R}^d$ grows with $d$, which is bad news when features are many or infinite. Chapter 15 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) introduces the support vector machine, the learning rule that replaces dimension by geometry. Among the halfspaces separating a sample, Hard-SVM picks the one of largest margin, the distance from the hyperplane to the nearest example (Claim 15.1, Lemma 15.2); if the data are separable with margin $\gamma$ and lie in a ball of radius $\rho$, the resulting classifier has error $O(\rho/(\gamma\sqrt m))$ whatever the dimension (Theorem 15.4), and the Perceptron of Chapter 9 makes at most $(\rho/\gamma)^2$ updates (Remark 15.1). Soft-SVM drops separability by allowing slack variables, and Claim 15.5 identifies it with regularized hinge-loss minimization, so that the stability theory of Chapter 13 applies: the hinge loss is $\|x\|$-Lipschitz (Claim 15.6), and Corollary 15.7 gives an expected-risk bound depending only on the norms of the data and of the comparison halfspace. The chapter closes with the optimality conditions that explain the name: the Hard-SVM solution is a combination of the examples on the margin (Theorem 15.8, via the Fritz John conditions, Lemma 15.9).

Setting

Vectors live in $\mathbb{R}^d$ as in Mission VI; labels are real numbers, with $y \in \{\pm 1\}$ as a hypothesis wherever the book needs it. A sample is linearly separable if some halfspace $(w, b)$ has $y_i(\langle w, x_i\rangle + b) > 0$ for all $i$, and the margin of $(w, b)$ on the sample is $\min_i y_i(\langle w, x_i\rangle + b)$. Hard-SVM solutions are minimizers of $\|w\|$ subject to $y_i(\langle w, x_i\rangle + b) \ge 1$, formalized as a relation; the minimizer is unique whenever the constraints are feasible, and the homogenous version sets $b = 0$. A distribution over $\mathbb{R}^d \times \{\pm 1\}$ is separable with a $(\gamma, \rho)$-margin if some unit $w^\star$ (and $b^\star$) has $y(\langle w^\star, x\rangle + b^\star) \ge \gamma$ and $\|x\| \le \rho$ almost surely. Soft-SVM is the problem $\lambda\|w\|^2 + \frac1m\sum\xi_i$ under $y_i(\langle w, x_i\rangle + b) \ge 1 - \xi_i$, $\xi_i \ge 0$; its homogenous form is the regularized loss minimization rule of Mission IX for the hinge loss $\max\{0, 1 - y\langle w, x\rangle\}$, and the 0–1 loss is $\mathbb{1}[y\langle w, x\rangle \le 0]$. Expectations over samples are integrals against $D^m$, with the measurability conventions of Mission IX.

Formalization targets

Goal: Corollary 15.7, last part

For $D$ on $\{\|x\| \le \rho\} \times \{\pm 1\}$ almost surely, $B > 0$, and the Soft-SVM learner with $\lambda = \sqrt{2\rho^2/(B^2 m)}$: $\mathbb{E}_S[L^{0-1}_D(A(S))] \le \mathbb{E}_S[L^{hinge}_D(A(S))]$, and for every $w$ with $\|w\| \le B$, $\mathbb{E}_S[L^{hinge}_D(A(S))] \le L^{hinge}_D(w) + \sqrt{8\rho^2 B^2/m}$.

Milestones

Claim 15.1. The distance from $x$ to $\{v : \langle w, v\rangle + b = 0\}$ with $\|w\| = 1$ is $|\langle w, x\rangle + b|$.

Lemma 15.2. For a sample with both labels present, the normalized Hard-SVM output has unit norm and margin at least that of every unit-norm halfspace.

Theorem 15.4. Under homogenous $(\gamma, \rho)$-separability, with probability at least $1 - \delta$ the 0–1 risk of the Hard-SVM output is at most $\sqrt{4(\rho/\gamma)^2/m} + \sqrt{2\log(2/\delta)/m}$.

Claim 15.5. Every feasible slack vector has average at least the hinge loss, and the hinge losses are feasible slacks.

Claim 15.6. For $y \in \{\pm 1\}$, $w \mapsto \max\{0, 1 - y\langle w, x\rangle\}$ is $\|x\|$-Lipschitz.

Corollary 15.7, first parts. For every $u$, $\mathbb{E}_S[L^{hinge}_D(A(S))]$ and $\mathbb{E}_S[L^{0-1}_D(A(S))]$ are at most $L^{hinge}_D(u) + \lambda\|u\|^2 + 2\rho^2/(\lambda m)$.

Theorem 15.8. The homogenous Hard-SVM solution is $\sum_{i \in I}\alpha_i x_i$ with $I = \{i : |\langle w_0, x_i\rangle| = 1\}$.

Lemma 15.9. Fritz John conditions, in the correct form with a multiplier on $\nabla f$.

Further items: Exercise 15.1 (the two Hard-SVM formulations agree) and Exercise 15.2 (the Perceptron makes at most $(\rho/\gamma)^2$ updates).

Significance

SVM is the bridge between the statistical theory of Part I and the kernel methods of Chapter 16: because the bounds of Theorem 15.4 and Corollary 15.7 involve only $\rho$, $\gamma$ and $B$, the same algorithm can be run after an embedding into a huge or infinite-dimensional feature space, and Theorem 15.8, that the solution lies in the span of the examples, is what makes the embedding computable. Corollary 15.7 is also the first place where the abstract machinery of Chapter 13 is applied to a specific learning rule.

Nothing here is machine-checked. One correction is built in: the Fritz John lemma is stated with the multiplier $\alpha_0 \ge 0$ on $\nabla f(w^\star)$ and nonnegative multipliers not all zero, since the printed form, with $\nabla f(w^\star)$ unweighted and $\alpha$ unrestricted, fails already for $f(w) = w$ and $g_1(w) = w^2$ on the line. Theorem 15.8 is unaffected: its constraints are affine, so the multiplier on $\nabla f$ can be taken to be $1$.

Difficulty

Claim 15.6 and Claim 15.5 are short inequalities and the intended entry points, and Exercise 15.2 is Theorem 9.1 of Mission VI with $B \le 1/\gamma$ and $R \le \rho$. Claim 15.1 is the book's computation with the foot of the perpendicular $v = x - (\langle w, x\rangle + b)w$ and a Pythagorean inequality for every other point of the hyperplane, packaged as an infimum distance. Lemma 15.2 is the rescaling argument of the book, together with the observation that both labels force $w_0 \ne 0$; Exercise 15.1 needs the positivity of the optimal margin on a separable sample. Corollary 15.7 is Corollaries 13.8 and 13.9 of Mission IX for the hinge loss, whose Lipschitz constant is $\|x\|$ only on the support of $D$, so the stability argument must be run with the almost-sure bound; the 0–1 clause is the pointwise inequality $\ell_{0-1} \le \ell_{hinge}$. Theorem 15.4 is the content of §26.3: Rademacher complexity of the class of norm-bounded halfspaces, the contraction lemma for the ramp loss, the observation that the Hard-SVM output has zero ramp loss on the sample and norm at most $1/\gamma$, and a concentration step, all of which will be items of the Rademacher mission. Theorem 15.8 is the KKT theorem for a strictly convex quadratic with affine constraints (Slater's condition holds), and Lemma 15.9 is the general Fritz John theorem for differentiable data, whose proof goes through a separation or penalty argument; neither is in Mathlib.

Formalization scope

Hard-SVM and Soft-SVM are relations and learners, not programs; the margin is a real infimum over the sample; the ramp loss is defined but its bounds belong to Chapter 26. Theorem 15.4 is stated for any learner that returns the Hard-SVM solution whenever the sample is feasible, which is almost surely the case under the margin assumption, and bounds the failure event in outer measure. Corollary 15.7 carries the measurability conventions of Mission IX. The Fritz John lemma is stated correctly rather than as printed. The duality of §15.4, the SGD implementation of §15.5 (whose guarantee needs the trajectory bound of §14.5.3 rather than Theorem 14.11 as stated in Mission X), Exercises 15.3 and 15.4, and Remark 15.2 are not stated.

Trivializing readings are excluded: both labels must be present for the normalized Hard-SVM output, the margin assumption and the support condition are almost sure with respect to $D$, and the risks are genuine integrals. Welcome contributions: the uniqueness of the Hard-SVM minimizer, the KKT conditions for affine constraints, and the pointwise comparison of the 0–1, ramp and hinge losses.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 15. doi:10.1017/CBO9781107298019
• C. Cortes, V. Vapnik, Support-vector networks, Machine Learning 20(3), 1995. doi:10.1007/BF00994018
• B. E. Boser, I. M. Guyon, V. N. Vapnik, A training algorithm for optimal margin classifiers, Proceedings of COLT, 1992. doi:10.1145/130385.130401
• F. John, Extremum problems with inequalities as subsidiary conditions, in Studies and Essays Presented to R. Courant, 1948.
• N. Cristianini, J. Shawe-Taylor, An Introduction to Support Vector Machines, Cambridge University Press, 2000. doi:10.1017/CBO9780511801389

Motivation

Chapters 12 and 13 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) leave binary classification for the general framework in which a hypothesis is a vector $w \in \mathbb{R}^d$ and the loss $\ell(w, z)$ is a convex function of $w$. Convexity makes the ERM problem tractable (Lemma 12.11), but Examples 12.8 and 12.9 show that convexity, even with a bounded class, does not by itself make a problem learnable: one-dimensional linear regression with the squared loss defeats every learner. The chapter therefore isolates two families, the convex-Lipschitz-bounded and the convex-smooth-bounded problems (Definitions 12.12 and 12.13), and Chapter 13 proves that both are learnable, not by ERM but by Regularized Loss Minimization with Tikhonov regularization, $A(S) \in \operatorname{argmin}_w L_S(w) + \lambda\|w\|^2$. The proof goes through a new idea: stability. Theorem 13.2 expresses the expected overfitting $\mathbb{E}[L_D(A(S)) - L_S(A(S))]$ exactly as the expected effect of replacing one training example, strong convexity of the regularized objective bounds that effect (Lemma 13.5, Corollaries 13.6 and 13.7), and balancing the regularization against the fit gives oracle inequalities (Corollaries 13.8 and 13.10) and sample-complexity guarantees (Corollaries 13.9 and 13.11), with ridge regression as the worked example (Theorem 13.1).

Setting

Hypotheses are vectors in $\mathbb{R}^d$ with the Euclidean norm, as in Mission VI; risk, empirical risk, the product law of a sample and agnostic PAC learnability are those of Mission I. A problem is convex when $H$ is convex and every $\ell(\cdot, z)$ is convex; it is convex-Lipschitz-bounded with parameters $\rho, B$ when moreover $\|w\| \le B$ on $H$ and every $\ell(\cdot, z)$ is $\rho$-Lipschitz on $\mathbb{R}^d$, and convex-smooth-bounded with parameters $\beta, B$ when every $\ell(\cdot, z)$ is nonnegative and differentiable with a $\beta$-Lipschitz gradient. Lipschitzness and smoothness are required on all of $\mathbb{R}^d$ because the RLM rule is unconstrained and its outputs need not lie in $H$. The RLM rule is a relation: $w$ is an output on $S$ if it minimizes $L_S(w) + \lambda\|w\|^2$ over $\mathbb{R}^d$, and a learner implements the rule if all its outputs are minimizers. For the losses of the chapter the minimizer exists and is unique. Given $S = (z_1, \dots, z_m)$ and a further example $z'$, $S^{(i)}$ is $S$ with $z_i$ replaced by $z'$; a learner is on-average-replace-one-stable with rate $\epsilon(m)$ if $\mathbb{E}_{(S,z') \sim D^{m+1},\, i \sim U(m)}[\ell(A(S^{(i)}), z_i) - \ell(A(S), z_i)] \le \epsilon(m)$ for every distribution. Strong convexity is Mathlib's StrongConvexOn, which is Definition 13.4 verbatim.

Expectations over samples are integrals against product laws. For them to be genuine, the theorems about arbitrary learners assume a jointly measurable loss bounded by a constant and a measurable learner, and the theorems about RLM assume a jointly measurable, nonnegative loss bounded at the origin and a measurable learner; for RLM the latter is automatic, since the minimizer is unique.

Formalization targets

Goal: Corollary 13.9

For a convex-Lipschitz-bounded problem with parameters $\rho, B > 0$ and the RLM learner with $\lambda(m) = \sqrt{2\rho^2/(B^2 m)}$: for every distribution, every $m \ge 1$ and every $w \in H$, $\mathbb{E}_S[L_D(A(S))] \le L_D(w) + \rho B\sqrt{8/m}$; hence for every $\epsilon > 0$ and $m \ge 8\rho^2B^2/\epsilon^2$, $\mathbb{E}_S[L_D(A(S))] \le L_D(w) + \epsilon$.

Milestones

Examples 12.8–12.9. Linear regression on $\mathbb{R}$ with the squared loss is not agnostic PAC learnable, over $H = \mathbb{R}$ or over $H = [-1, 1]$.

Theorem 13.2. For any measurable learner and $m \ge 1$, $\mathbb{E}_S[L_D(A(S)) - L_S(A(S))]$ equals the replace-one expectation of (13.6).

Lemma 13.5. $\lambda\|w\|^2$ is $2\lambda$-strongly convex; a strongly convex function plus a convex one is strongly convex; at a minimizer $u$ of a $\lambda$-strongly convex $f$, $f(w) - f(u) \ge \frac\lambda2\|w - u\|^2$.

Corollary 13.6. For a convex $\rho$-Lipschitz loss and $\lambda > 0$, RLM satisfies $\ell(A(S^{(i)}), z_i) - \ell(A(S), z_i) \le 2\rho^2/(\lambda m)$ for every $S, z', i$, is stable with that rate, and has $\mathbb{E}_S[L_D(A(S)) - L_S(A(S))] \le 2\rho^2/(\lambda m)$.

Corollary 13.7. For a convex, nonnegative, $\beta$-smooth loss and $\lambda \ge 2\beta/m$, the replace-one expectation is at most $(48\beta/(\lambda m))\,\mathbb{E}[L_S(A(S))]$, and at most $48\beta C/(\lambda m)$ if $\ell(0, z) \le C$.

Corollary 13.8. $\mathbb{E}_S[L_D(A(S))] \le L_D(w^*) + \lambda\|w^*\|^2 + 2\rho^2/(\lambda m)$ for every $w^*$.

Corollary 13.10. $\mathbb{E}_S[L_D(A(S))] \le (1 + 48\beta/(\lambda m))\,\mathbb{E}_S[L_S(A(S))] \le (1 + 48\beta/(\lambda m))(L_D(w^*) + \lambda\|w^*\|^2)$.

Corollary 13.11. A convex-smooth-bounded problem with $\ell(0, z) \le 1$ is learned by RLM with $\lambda = \epsilon/(3B^2)$ once $m \ge 150\beta B^2/\epsilon^2$.

Theorem 13.1. Ridge regression on the unit ball with labels in $[-1, 1]$, $\lambda = \epsilon/(3B^2)$ and $m \ge 150 B^2/\epsilon^2$ has $\mathbb{E}_S[L_D(A(S))] \le \min_{\|w\| \le B} L_D(w) + \epsilon$.

Further items: Lemma 12.11, the hinge loss as a convex surrogate of the 0–1 loss, the stability-implies-no-overfitting remark of §13.2, and the ridge regression system (13.4)–(13.5).

Significance

Stability is the third route to learnability in the book after uniform convergence and nonuniform learnability, and the only one that applies to convex-Lipschitz-bounded problems in general, for which uniform convergence can fail (the book's Exercise 13.2). The chain from strong convexity through replace-one stability to oracle inequalities is the template for the analysis of every regularized learner, and Theorem 13.2 is an exact identity, not a bound. Ridge regression, support vector machines (Chapter 15) and the regularized algorithms of later chapters are all instances.

Nothing here is machine-checked. The sample sizes of Corollary 13.11 and Theorem 13.1 are the book's $150$. Chaining Corollary 13.10 as printed would need $216$, but the derivation of Corollary 13.7 actually gives the stability rate $20\beta/(\lambda m)$, with which $90$ suffices.

Difficulty

Lemma 12.11 and the hinge surrogate are direct. Lemma 13.5 is elementary but part (3) needs the limit $\alpha \to 0$ of the strong-convexity inequality at a minimizer. Examples 12.8–12.9 require constructing the two finitely supported distributions of the book and computing the risk of a fixed output on each; the probability that all $m$ examples are of the second type is at least $0.99$ under both, and the deterministic learner's output on that sample decides which distribution defeats it. Theorem 13.2 is the exchangeability argument of the book: $\mathbb{E}[\ell(A(S), z')] = \mathbb{E}[\ell(A(S^{(i)}), z_i)]$ because swapping $z_i$ and $z'$ preserves the product law; the formal work is the measure-preserving transposition on $Z^{m+1}$ and the integrability of the functions involved. Corollaries 13.6 and 13.7 follow the book's pointwise derivation from (13.7) to (13.11) and (13.12) to (13.14), where the smooth case uses the self-boundedness $\|\nabla\ell\|^2 \le 2\beta\ell$ of nonnegative smooth functions and the inequality $(a + b)^2 \le 3(a^2 + b^2)$; passing to expectations then uses Theorem 13.2 and, for the smooth case, the symmetry $\mathbb{E}[\ell(A(S^{(i)}), z')] = \mathbb{E}[\ell(A(S), z_i)]$. Corollaries 13.8 to 13.11 are the arithmetic of the book once (13.16), $\mathbb{E}[L_S(A(S))] \le L_D(w^*) + \lambda\|w^*\|^2$, is in hand, with the corrected constant for 13.11. The ridge system is the gradient condition for a strongly convex quadratic, and Theorem 13.1 is Corollary 13.11 applied to $\frac12(\langle w, x\rangle - y)^2$, which is $\|x\|^2$-smooth with $\ell(0, z) = y^2/2 \le 1/2$ on the support. In every expectation statement the measurability of $S \mapsto A(S)$ for the RLM rule, which the theorems take as a hypothesis, is provable from uniqueness of the minimizer and is worth a lemma.

Formalization scope

Losses are real-valued functions of a vector and an example; Lipschitz and smoothness conditions are global on $\mathbb{R}^d$. The RLM rule is a minimizer relation with the regularization parameter as an explicit argument, and Corollary 13.9's learner uses a parameter depending on $m$. Stability quantifies over $m \ge 1$ and averages over the replaced index. Expectation statements carry measurability hypotheses that make every integral genuine, and the theorems about arbitrary learners assume a bounded loss. The minimum over $H$ is stated as "for every $w \in H$", so no minimizer is needed. Definitions 12.1–12.9 and Claims 12.4–12.9 (general convex analysis) are not restated, nor are Examples 12.10–12.11, the discussion of §12.3 beyond the surrogate property, Remark 13.1, and Exercises 12.1–12.4 and 13.1–13.2.

Trivializing readings are excluded: the nonlearnability examples are stated as negations of the framework's learnability, the stability identity is an equality with both sides genuine integrals, and the constants of the oracle inequalities are the book's. Welcome contributions: the transposition invariance of product laws behind Theorem 13.2, the bound $\|A(S)\|^2 \le L_S(0)/\lambda$ for RLM outputs, the measurability of the RLM minimizer, and the self-boundedness inequality (12.6).

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapters 12 and 13. doi:10.1017/CBO9781107298019
• O. Bousquet, A. Elisseeff, Stability and generalization, Journal of Machine Learning Research 2, 2002.
• S. Shalev-Shwartz, O. Shamir, N. Srebro, K. Sridharan, Learnability, stability and uniform convergence, Journal of Machine Learning Research 11, 2010.
• A. N. Tikhonov, On the stability of inverse problems, Doklady Akademii Nauk SSSR 39(5), 1943.
• S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. doi:10.1017/CBO9780511804441

Motivation

Boosting answers a question raised by Kearns and Valiant: can a learner that is only slightly better than random guessing be turned into one that is arbitrarily accurate? Chapter 10 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) defines γ-weak learnability (Definition 10.1), the PAC requirement with the accuracy $\epsilon$ replaced by the fixed value $1/2 - \gamma$, and presents AdaBoost, the algorithm of Freund and Schapire that, given weak hypotheses, reweights the training set round by round and outputs a weighted majority vote. The chapter's main result (Theorem 10.2) is that the training error of AdaBoost's output decreases as $e^{-2\gamma^2 T}$ in the number of rounds. Since the output is a halfspace over the predictions of $T$ base hypotheses, the chapter then bounds the VC-dimension of that class (Lemma 10.3), so that the number of rounds becomes a knob for the bias–complexity tradeoff. Example 10.1 shows a concrete weak learner, ERM over decision stumps for the class of 3-piece classifiers on the line, and the chapter remarks that, statistically, weak learnability is no easier than strong learnability: a class of infinite VC-dimension is not weakly learnable either.

Setting

The framework is that of Missions I and IV: binary classification over a domain $X$ with the 0–1 loss, distributions $D$ over $X$ with a labeling function $f$, learners as functions of the sample, the VC-dimension, and ERM. Labels and hypotheses are Boolean, with $\pm 1$ values obtained through $\operatorname{sgn}(\text{true}) = 1$, $\operatorname{sgn}(\text{false}) = -1$, and $\operatorname{sign}(z)$ is true exactly when $z > 0$. A γ-weak learner for $H$ with the function $m_H : (0,1) \to \mathbb{N}$ returns, for every $\delta$, every $D$ and every measurable $f$ realizable by $H$, a hypothesis with $L_{(D,f)}(h) \le 1/2 - \gamma$ with probability at least $1 - \delta$ once $m \ge m_H(\delta)$; the failure event is bounded in outer measure as in Definition 3.1.

AdaBoost is formalized as a deterministic function of the sample $S = (x_1, y_1), \dots, (x_m, y_m)$ and of the sequence of weak hypotheses $h_0, h_1, \dots$ that the weak learner returned. The distributions are defined by recursion: $D^{(0)}$ is uniform, $\epsilon_t = \sum_i D^{(t)}_i \mathbb{1}[h_t(x_i) \ne y_i]$, $w_t = \frac12 \log(1/\epsilon_t - 1)$, and $D^{(t+1)}_i \propto D^{(t)}_i \exp(-w_t y_i h_t(x_i))$; the output after $T$ rounds is $x \mapsto \operatorname{sign}(\sum_{t < T} w_t h_t(x))$. Rounds are indexed from $0$, so $D^{(0)}$ is the book's $D^{(1)}$. The class $L(B, T)$ of Equation (10.4) consists of the functions $x \mapsto \operatorname{sign}(\sum_{t=1}^T w_t h_t(x))$ with $h_t \in B$. Decision stumps over $\mathbb{R}$ are the threshold functions $x \mapsto [\theta < x]$ and their negations $x \mapsto [x \le \theta]$; a 3-piece classifier is $b$ outside $[\theta_1, \theta_2]$ and $-b$ inside, with $\theta_1 < \theta_2$.

Formalization targets

Goal: Theorem 10.2

If $\gamma > 0$ and every round $t < T$ has $0 < \epsilon_t \le 1/2 - \gamma$, then the empirical 0–1 risk of AdaBoost's output after $T$ rounds is at most $\exp(-2\gamma^2 T)$.

Milestones

§10.1. A class of infinite VC-dimension is not γ-weak-learnable for any $\gamma > 0$ (domain with measurable singletons, measurable hypotheses).

Example 10.1. There is one sample-size function with which every ERM learner over the decision stumps is a $1/12$-weak learner for the 3-piece classifiers.

Exercise 10.3. For a nonempty sample and $\epsilon_t \in (0,1)$, the error of $h_t$ under $D^{(t+1)}$ is exactly $1/2$.

Lemma 10.3. If $T \ge 3$ and $\mathrm{VCdim}(B) = d \ge 3$, then $\mathrm{VCdim}(L(B,T)) \le T(d+1)(3\log(T(d+1)) + 2)$.

Further item: Exercise 10.4 (1), $\mathrm{VCdim}(B) \le \mathrm{VCdim}(L(B,T))$ for $T \ge 1$.

Significance

Theorem 10.2 is the reason AdaBoost works and the template for every analysis of boosting: a potential function, here $\frac1m \sum_i e^{-y_i f_t(x_i)}$, bounds the 0–1 training error and contracts by the factor $2\sqrt{\epsilon_{t}(1-\epsilon_{t})} \le \sqrt{1 - 4\gamma^2}$ at every round. Lemma 10.3 supplies the other half of the picture, an estimation-error bound growing only like $T \cdot \mathrm{VCdim}(B)$ up to logarithms, so that Theorem 6.8 turns the pair into a generalization guarantee for boosting. The remark of §10.1 places weak learning in the statistical landscape of Part I: the VC-dimension characterizes it too, and the gain of boosting is computational.

Nothing here is machine-checked. Two points where the book's text needs care are built into the statements. The weight $w_t$ is undefined when $\epsilon_t = 0$, and the algorithm's normalization then divides $0$ by $0$; in Lean the logarithm of a negative number is $0$, so with $\epsilon_t = 0$ the formal algorithm would ignore a perfect weak hypothesis and the bound could fail. The theorems therefore assume $\epsilon_t > 0$, which is the case in which the book's formulas are defined. And the book's derivation of "infinite VC-dimension implies not weakly learnable" from the lower bound of Theorem 6.8 at $\epsilon = 1/2 - \gamma$ uses that bound outside the range in which Chapter 28 proves it; the statement itself is true, by the $km$-point form of the No-Free-Lunch argument (Exercise 5.3 of Mission III) and Lemma B.1.

Difficulty

Exercise 10.4 (1) is a one-line embedding of $B$ into $L(B, T)$ with the weights $(1, 0, \dots, 0)$ and is the entry point. Exercise 10.3 is the computation of the book: after the update, the weight of the mistakes of $h_t$ is $e^{w_t}\epsilon_t$ and the weight of the correct examples is $e^{-w_t}(1 - \epsilon_t)$, and with $e^{w_t} = \sqrt{(1-\epsilon_t)/\epsilon_t}$ these are equal. Theorem 10.2 needs, by induction on the round, the closed form $D^{(t)}_i = e^{-y_i f_{t}(x_i)}/\sum_j e^{-y_j f_{t}(x_j)}$ of the distribution, the pointwise bound $\mathbb{1}[\operatorname{sign}(f(x)) \ne y] \le e^{-y f(x)}$ for the sign convention used, the telescoping product (10.2), the identity $Z_{t+1}/Z_t = 2\sqrt{\epsilon_t(1-\epsilon_t)}$, the monotonicity of $a(1-a)$ on $[0, 1/2]$ and $1 - a \le e^{-a}$. Lemma 10.3 counts dichotomies: Sauer's lemma bounds the restrictions of $B$ to a shattered set by $(em/d)^d$, choosing $T$ of them gives $(em/d)^{dT}$, the halfspaces of $\mathbb{R}^T$ contribute $(em/T)^T$ by Theorem 9.2, and the inequality $2^m \le m^{(d+1)T}$ is solved with Lemma A.1; the finite-VC lower bound $m \le d + 1$ handles small $m$, and the numeric slack of the book's chain must be checked. Example 10.1 combines a geometric observation, that one of the three regions of a 3-piece classifier has mass at most $1/3$ and a stump agrees with the other two, with the agnostic guarantee for ERM over the stumps from Theorem 6.7, applied with accuracy $1/12$; the best stump may only approach error $1/3$ because constant functions are not stumps, and the slack absorbs this. The §10.1 remark is the argument sketched above.

Formalization scope

AdaBoost is a function of the sample and of the returned weak hypotheses; the weak learner's randomness and its failure probability (Remark 10.2) are not modelled, and Theorem 10.2 is the deterministic statement the book proves. Rounds are indexed from $0$. The output uses $\operatorname{sign}(0) =$ negative, consistently with Mission VI. The class $L(B,T)$ is a set of functions, so Lemma 10.3 is a statement about the VC-dimension of Mission IV, with the bound taken in $\mathbb{N} \cup \{\infty\}$ through the integer part of the real right-hand side and the natural logarithm. Decision stumps are closed under negation, as the book's $\operatorname{sign}(x - \theta)\cdot b$; constant functions are not stumps. The efficient ERM for decision stumps (§10.1.1), the face-recognition features (§10.4), Exercises 10.1, 10.2, 10.4 (2)–(3) and 10.5 are not stated. The claims of §10.3 that piecewise-constant classifiers with $T$ pieces lie in $L(\text{stumps}, T)$ and that this class shatters $T+1$ points depend on treating $\operatorname{sign}(x - (-\infty))$ as a stump and on the sign convention; with real thresholds, $L(\text{stumps}, 2)$ does not shatter three points under either convention, so these claims are not stated.

Trivializing readings are excluded: the weak-error hypotheses are strict where the book's formulas require it, the VC bounds are in $\mathbb{N} \cup \{\infty\}$, and the weak-learner guarantee quantifies over all distributions and all realizable labelings. Welcome contributions: the closed form of $D^{(t)}$, the contraction identity for $Z_{t+1}/Z_t$, and the dichotomy count behind Lemma 10.3.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 10. doi:10.1017/CBO9781107298019
• Y. Freund, R. E. Schapire, A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences 55(1), 1997. doi:10.1006/jcss.1997.1504
• R. E. Schapire, The strength of weak learnability, Machine Learning 5(2), 1990. doi:10.1007/BF00116037
• M. Kearns, L. Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, Journal of the ACM 41(1), 1994. doi:10.1145/174644.174647
• R. E. Schapire, Y. Freund, Boosting: Foundations and Algorithms, MIT Press, 2012.

Motivation

Part II of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) turns from the theory of learnability to hypothesis classes that can actually be learned by algorithms, and it starts with the family that almost every practical method is built on: linear predictors. Chapter 9 introduces the affine functions $L_d$ and the three classes obtained by composing them with a link: halfspaces for classification, linear regression for real-valued prediction, and logistic regression in between. For each class it gives an ERM algorithm and the guarantee that goes with it. For halfspaces in the separable case the algorithm is Rosenblatt's Perceptron, and the guarantee is the classical mistake bound (Theorem 9.1): the number of updates is at most $(RB)^2$, where $R$ bounds the data and $B$ is the norm of the smallest vector separating it with margin one. The chapter then computes the VC-dimension of halfspaces (Theorems 9.2 and 9.3), which by the fundamental theorem of Mission IV makes them learnable, derives the Least Squares normal equations for regression, and observes that the logistic loss is convex, the property later chapters exploit.

Setting

Vectors live in $\mathbb{R}^d$ with its Euclidean inner product and norm. The affine functions are $h_{w,b}(x) = \langle w, x\rangle + b$, homogenous when $b = 0$; a halfspace hypothesis is $x \mapsto \operatorname{sign}(\langle w, x\rangle + b)$, formalized as a Boolean predictor that is true exactly when $\langle w, x\rangle + b > 0$ (the book leaves $\operatorname{sign}(0)$ unspecified; the VC computations do not depend on the convention). A sample $(x_1, y_1), \dots, (x_m, y_m)$ with labels $y_i \in \{\pm 1\}$ is separable if some $w$ has $y_i\langle w, x_i\rangle > 0$ for all $i$; the constants of Theorem 9.1 are $B = \inf\{\|w\| : \forall i,\ y_i\langle w, x_i\rangle \ge 1\}$ and $R = \max_i \|x_i\|$. The Batch Perceptron starts at $w^{(0)} = 0$ and, while some example has $y_i\langle w^{(t)}, x_i\rangle \le 0$, adds $y_i x_i$; since the algorithm may pick any mistaken example, a run is any sequence of updates obeying this rule, and the theorem is stated for all runs. For regression the loss is $(h(x) - y)^2$ and the Least Squares system is $Aw = b$ with $A = \sum_i x_i x_i^\top$, written as the linear map $w \mapsto \sum_i \langle x_i, w\rangle x_i$, and $b = \sum_i y_i x_i$. The logistic function is $\varphi_{sig}(z) = 1/(1 + e^{-z})$ and the logistic loss is $\log(1 + \exp(-y\langle w, x\rangle))$. The learning-theoretic notions (ERM, PAC and agnostic PAC learnability, VC-dimension) are those of Missions I and IV.

Formalization targets

Goal: Theorem 9.1 (Perceptron convergence)

For a separable sample with labels in $\{\pm 1\}$, every run of the Batch Perceptron of $T$ iterations satisfies $T \le (RB)^2$, and some run of at most $(RB)^2$ iterations ends with $y_i\langle w^{(T)}, x_i\rangle > 0$ for every $i$.

Milestones

Equation (9.1). A sample is separable if and only if some $w$ satisfies $y_i\langle w, x_i\rangle \ge 1$ for all $i$.

Theorem 9.2. The VC-dimension of the homogenous halfspaces in $\mathbb{R}^d$ is $d$.

Theorem 9.3. The VC-dimension of the halfspaces in $\mathbb{R}^d$ is $d+1$.

Least Squares (9.6). The system $Aw = b$ always has a solution, and $w$ solves it if and only if $h_w$ is an ERM hypothesis for the squared loss over the homogenous linear predictors.

Further items: Exercise 9.3, the tightness of Theorem 9.1 (for every $m$ a sample with $R \le 1$, $(BR)^2 \le m$ and a run of exactly $m$ updates); the learnability of halfspaces by ERM, a consequence of Theorem 9.3 and the fundamental theorem; Exercise 9.2, $A$ is invertible iff the $x_i$ span $\mathbb{R}^d$; and the convexity of the logistic loss in $w$.

Significance

The Perceptron bound is one of the oldest results of learning theory (Novikoff 1962) and the model for every mistake bound in the online-learning chapters: it is independent of the dimension and of the number of examples, depending only on the geometry of the data through $R$ and $B$. Theorems 9.2 and 9.3 are the first VC-dimension computations of a class used in practice and give, through Theorem 6.8, the sample complexity $\Theta((d + \log(1/\delta))/\epsilon)$ of learning halfspaces. The normal equations are the algorithmic content of linear regression, and the convexity of the logistic loss is why logistic regression is tractable in the nonseparable case, where ERM for halfspaces with the 0–1 loss is hard.

Nothing here is machine-checked in this form. Mathlib has the inner-product geometry, the Cauchy–Schwarz inequality, linear algebra of finite-dimensional spaces and convexity of compositions, but neither the Perceptron nor the VC-dimension of halfspaces.

Difficulty

Equation (9.1) is a rescaling and the intended entry point. The convexity of the logistic loss is the composition of the convex function $\log(1 + e^{-t})$ with the linear map $w \mapsto y\langle w, x\rangle$. Exercise 9.2 is the identification of the kernel of $\sum_i \langle x_i, \cdot\rangle x_i$ with the orthogonal complement of the span. The normal equations require showing that a convex quadratic is minimized exactly where its gradient vanishes, and that $b$ lies in the range of $A$, which is the span of the $x_i$. Theorem 9.1 is the book's proof: by induction on the run, $\langle w^*, w^{(T)}\rangle \ge T$ and $\|w^{(T)}\|^2 \le TR^2$ for any feasible $w^*$, then Cauchy–Schwarz, and finally the passage from a feasible $w^*$ to the infimum $B$; the existence clause follows because a run can be extended as long as the stopping condition fails and all runs are bounded. Theorem 9.2 is the linear-dependence argument of the book, with a case analysis on the signs of the coefficients and on which side is nonempty, and the shattering of the standard basis; Theorem 9.3 lifts it to $\mathbb{R}^{d+1}$ by appending a constant coordinate. The learnability of halfspaces is Theorem 6.7 applied to a class that must be shown measurable, nonempty, of finite VC-dimension and pointwise separable; the last needs rational approximations $(w_n, b_n)$ in which the offset moves below $b$ more slowly than $w_n$ approaches $w$, so that boundary points keep their label.

Formalization scope

Halfspaces are Boolean predictors with $\operatorname{sign}(0)$ negative; the classes are sets of functions, so the VC-dimension is that of Mission IV. The Perceptron is a relation on sequences, not a program: this captures the algorithm's freedom to choose any mistaken example and makes the bound apply to all implementations. $B$ is an infimum, which is attained (the feasible set is closed and the norm is coercive), but the theorem does not need attainment. $R$ is a real supremum over the finite index set, equal to $0$ for the empty sample, where every run has length $0$. The Least Squares statement is about the homogenous class and the sample $i \mapsto (x_i, y_i)$, with ERM in the sense of Mission I; the bias term is handled by the book's reduction, appending a constant coordinate, and is not formalized separately. The learnability item states qualitative learnability and the ERM guarantee with an unspecified sample-complexity function; the quantitative rate is Theorem 6.8 of Mission IV. Linear programming (§9.1.1), the pseudo-inverse (§9.2.1), polynomial regression (§9.2.2), Exercises 9.1 and 9.4–9.6 are not stated.

Trivializing readings are excluded: labels are constrained to $\pm 1$, runs must start at $0$ and update only on mistakes, the VC equalities are in $\mathbb{N} \cup \{\infty\}$, and the ERM equivalence is a biconditional. Welcome contributions: the two Perceptron invariants as separate lemmas, the shattering of the standard basis, and the pointwise separability of halfspaces.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 9. doi:10.1017/CBO9781107298019
• F. Rosenblatt, The perceptron: a probabilistic model for information storage and organization in the brain, Psychological Review 65(6), 1958. doi:10.1037/h0042519
• A. B. J. Novikoff, On convergence proofs on perceptrons, Proceedings of the Symposium on the Mathematical Theory of Automata 12, 1962.
• S. Agmon, The relaxation method for linear inequalities, Canadian Journal of Mathematics 6, 1954. doi:10.4153/CJM-1954-037-2
• S. Ben-David, H. U. Simon, Efficient learning of linear perceptrons, Advances in Neural Information Processing Systems 13, 2001.