Understanding Machine Learning

Motivation

Chapters 2 and 3 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (Cambridge University Press, 2014, doi:10.1017/CBO9781107298019), set up the framework in which the whole book asks what learning is. A learner sees a sample drawn independently from an unknown distribution over examples, chooses a hypothesis from a class fixed in advance, and is judged by its risk, the expected loss on a fresh example. The natural rule is Empirical Risk Minimization: pick a hypothesis that does best on the sample. Chapter 2 shows that ERM over an unrestricted class overfits, that restricting the class is what makes learning possible, and that a finite class never overfits once the sample is larger than $\log(|H|/\delta)/\epsilon$ (Corollary 2.3). Chapter 3 turns this into a definition, Probably Approximately Correct learnability with its sample-complexity function $m_H(\epsilon, \delta)$, restates the finite-class result as Corollary 3.2, and then generalizes in two directions that the rest of the book lives in: the agnostic model, in which no hypothesis need be perfect and the learner competes with the best hypothesis in the class, and general loss functions, which cover regression, multiclass prediction and unsupervised tasks. Chapter 4 adds the notion of an ε-representative sample and of uniform convergence, the tool by which the finite-class result extends to the agnostic case; its definitions are included here since they complete the framework.

Setting

A domain $Z$ of examples, a class $H$ of hypotheses and a loss $\ell : H \times Z \to \mathbb{R}$. The risk of $h$ under a distribution $D$ is $L_D(h) = \mathbb{E}_{z \sim D}\,\ell(h, z)$ and its empirical risk on $S = (z_1, \dots, z_m)$ is $L_S(h) = \frac1m\sum_i \ell(h, z_i)$; a sample is drawn i.i.d., $S \sim D^m$; an ERM hypothesis minimizes $L_S$ over $H$; a learning algorithm maps samples of each size to hypotheses. In binary classification the examples are $(x, f(x))$ with $x \sim D$ over $X$ and $f$ a labeling function, and the true error is $L_{(D,f)}(h) = D(\{x : h(x) \ne f(x)\})$; the realizability assumption says some $h^\star \in H$ has $L_{(D,f)}(h^\star) = 0$. $H$ is PAC learnable if some sample-complexity function $m_H$ and algorithm guarantee, for all $\epsilon, \delta \in (0,1)$, all $D$ and all realizable $f$, true error at most $\epsilon$ with probability at least $1 - \delta$ from $m \ge m_H(\epsilon, \delta)$ examples; agnostic PAC learnability with respect to a loss asks instead for $L_D(h) \le \min_{h' \in H} L_D(h') + \epsilon$ for every distribution over $Z$.

Formalization targets

Goal: Corollary 3.2

Every finite hypothesis class is PAC learnable with sample complexity

$$m_H(\epsilon, \delta) \le \Big\lceil \frac{\log(|H|/\delta)}{\epsilon} \Big\rceil,$$

by the ERM rule: for a nonempty finite class of measurable hypotheses there is an ERM learner satisfying the PAC guarantee with that sample-complexity function.

Milestone

Corollary 2.3: under realizability, with $m \ge \log(|H|/\delta)/\epsilon$ examples, every ERM hypothesis has true error at most $\epsilon$ with probability at least $1 - \delta$.

Significance

Corollaries 2.3 and 3.2 are the first learning theorem of the book and the template for all later sample-complexity bounds: a bad hypothesis is consistent with an i.i.d. sample with probability at most $(1 - \epsilon)^m \le e^{-\epsilon m}$, and a union bound over the class turns this into a guarantee that holds uniformly over all distributions and all realizable labelings. Everything that follows, uniform convergence for finite classes, the fundamental theorem for classes of finite VC dimension, structural risk minimization, replaces the count $|H|$ by a finer measure of the class's complexity but keeps the argument. None of this is machine-checked. The mission fixes on the platform the objects that the rest of the series uses without change: risks, empirical risks, the product law of a sample, the ERM relation, and the four learnability notions of Definitions 3.1, 3.4, 4.1 and 4.3.

Difficulty

The milestone needs that, for a fixed measurable hypothesis whose true error exceeds $\epsilon$, the product law gives the event "zero empirical risk" probability at most $(1-\epsilon)^m$; this is the product structure of Measure.pi on the event that each labeled example lies in the measurable set where the hypothesis agrees with $f$, followed by $1 - \epsilon \le e^{-\epsilon}$, the union bound over the finite class and the observation that under realizability every ERM hypothesis has zero empirical risk, so a bad ERM hypothesis is a consistent bad hypothesis. The goal packages this as a learner: existence of an ERM hypothesis for every sample (a finite nonempty class has a minimizer), and the arithmetic of the ceiling.

Formalization scope

The framework is the book's, with the risk as a Bochner integral, the sample law as a product measure, ERM as a relation and learners as deterministic functions of the sample; failure probabilities are stated as upper bounds on the outer measure of the failure set, the strong form of "with probability at least $1 - \delta$"; the comparison with $\min_{h' \in H} L_D(h')$ is written without an infimum. Sample-complexity functions are carried explicitly: the book's $m_H$ as the minimal such function is not defined, and "$m_H \le f$" is stated as "the learner satisfies the guarantee with the function $f$". Hypotheses and labeling functions are assumed measurable (Remark 3.1). The union bound (Lemma 2.2) is Mathlib's measure_union_le and is not an item. Hypotheses: $\epsilon > 0$, $\delta \in (0,1)$, $H$ finite (and nonempty for the learner to exist).

Trivializing readings are excluded: the milestone's failure event ranges over every ERM hypothesis, and the goal quantifies over all distributions, all realizable labelings and all $\epsilon, \delta$. Welcome contributions: the product-law bound for a fixed hypothesis and the union bound over a finset, which every later mission of the series reuses.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapters 2–4. doi:10.1017/CBO9781107298019
• L. G. Valiant, A theory of the learnable, Communications of the ACM 27(11), 1984. doi:10.1145/1968.1972
• V. N. Vapnik, The Nature of Statistical Learning Theory, Springer, 1995. doi:10.1007/978-1-4757-2440-0
• D. Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation 100(1), 1992. doi:10.1016/0890-5401(92)90010-D

Motivation

Mission I of this series set up the statistical learning framework of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) and proved, in the book's Chapters 2 and 3, that finite classes are PAC learnable under the realizability assumption. Chapter 4 removes that assumption. Its idea is the one that organizes the rest of the theory: if the empirical risks $L_S(h)$ of all hypotheses in $H$ are simultaneously close to their true risks $L_D(h)$, then minimizing $L_S$ over $H$ is nearly as good as minimizing $L_D$ over $H$, whatever the distribution $D$ is. A sample with that property is called $\epsilon$-representative (Definition 4.1), and a class for which representative samples are guaranteed at some sample size is said to have the uniform convergence property (Definition 4.3). Lemma 4.2 turns representativeness into a guarantee for ERM, Corollary 4.4 turns uniform convergence into agnostic PAC learnability, Hoeffding's inequality (Lemma 4.5) gives uniform convergence for a single hypothesis, and a union bound gives it for a finite class: Corollary 4.6, the capstone, says every finite class with a loss in $[0,1]$ is agnostic PAC learnable by ERM with sample complexity $\lceil 2\log(2|H|/\delta)/\epsilon^2 \rceil$.

Setting

The framework is the UnderstandingML_Framework module of Mission I, cited here as a reference. A domain $Z$ is a measurable space, hypotheses form a type with a class $H$, and a loss $\ell : H \times Z \to \mathbb{R}$ is given. The risk is $L_D(h) = \mathbb{E}_{z \sim D}\,\ell(h,z)$, the empirical risk on $S = (z_1,\dots,z_m)$ is $L_S(h) = \frac1m \sum_i \ell(h, z_i)$, and a sample of size $m$ has the product law $D^m$. A hypothesis is an ERM hypothesis for $S$ if it lies in $H$ and minimizes $L_S$ over $H$; a learner is a function from samples of each size to hypotheses, and an ERM learner returns an ERM hypothesis on every sample.

$S$ is $\epsilon$-representative with respect to $H$, $\ell$ and $D$ if $|L_S(h) - L_D(h)| \le \epsilon$ for every $h \in H$. $H$ has the uniform convergence property with the function $m^{UC}_H$ if for every $\epsilon, \delta \in (0,1)$ and every distribution $D$ over $Z$, a sample of $m \ge m^{UC}_H(\epsilon, \delta)$ i.i.d. examples is $\epsilon$-representative with probability at least $1 - \delta$. $H$ is agnostic PAC learnable with the function $m_H$ and the learner $A$ if $A$ returns hypotheses in $H$ and, for every $\epsilon, \delta \in (0,1)$, every $D$ and every $m \ge m_H(\epsilon,\delta)$, $L_D(A(S)) \le \min_{h' \in H} L_D(h') + \epsilon$ with probability at least $1 - \delta$ over $S \sim D^m$. As in Mission I, "with probability at least $1-\delta$" is an upper bound $\delta$ on the outer measure of the failure event, "$\min_{h' \in H} L_D(h') + \epsilon < L_D(h)$" is written as "$\exists h' \in H$, $L_D(h') + \epsilon < L_D(h)$", and sample-complexity functions are carried explicitly rather than as minimal functions.

Formalization targets

Goal: Corollary 4.6

Let $H$ be a finite hypothesis class, $Z$ a domain and $\ell : H \times Z \to [0,1]$ a loss function whose sections $\ell(h,\cdot)$ are measurable. Then

1. $H$ has the uniform convergence property with the function $m^{UC}_H(\epsilon,\delta) = \lceil \log(2|H|/\delta)/(2\epsilon^2) \rceil$;
2. every ERM learner for $H$ is an agnostic PAC learner with the function $m_H(\epsilon,\delta) = \lceil 2\log(2|H|/\delta)/\epsilon^2 \rceil$, which is $m^{UC}_H(\epsilon/2,\delta)$;
3. if $H$ is nonempty, $H$ is agnostic PAC learnable.

Milestones

Lemma 4.2. If $S$ is $\epsilon/2$-representative and $h_S$ is an ERM hypothesis for $S$, then $L_D(h_S) \le L_D(h) + \epsilon$ for every $h \in H$.

Corollary 4.4. If $H$ has the uniform convergence property with $m^{UC}_H$, then every ERM learner for $H$ is an agnostic PAC learner with the function $(\epsilon,\delta) \mapsto m^{UC}_H(\epsilon/2, \delta)$, and $H$ is agnostic PAC learnable as soon as an ERM learner exists.

Lemma 4.5 (Hoeffding's inequality). For a probability measure $D$, a measurable $\theta$ with $a \le \theta \le b$ almost surely and mean $\mu = \int \theta\,dD$, and $\epsilon > 0$,

$$D^m\Big[\Big|\tfrac1m \textstyle\sum_{i=1}^m \theta(\omega_i) - \mu\Big| > \epsilon\Big] \le 2\exp\!\big(-2m\epsilon^2/(b-a)^2\big).$$

Significance

Chapter 4 is where the book's account of learnability becomes distribution-free in the agnostic sense: nothing is assumed about $D$ beyond being a probability distribution, and the guarantee is relative to the best hypothesis in the class. Lemma 4.2 and Corollary 4.4 are the reduction that every later generalization bound in the book (VC dimension, Rademacher complexity, covering numbers, compression) plugs into: prove uniform convergence, get ERM learnability. Corollary 4.6 is the first instance, and its $\log|H|/\epsilon^2$ dependence, against the $\log|H|/\epsilon$ of the realizable case, is the standard illustration of the price of agnosticism. Hoeffding's inequality is stated in the form the book uses everywhere afterward, for the product law of one distribution, with an almost-sure range bound and the mean written as an integral.

Nothing here is machine-checked. Mathlib has no Hoeffding inequality for sums of i.i.d. bounded variables on a product measure in this form, so Lemma 4.5 is a genuine contribution; its proof in the book's Appendix B goes through Hoeffding's lemma on the moment generating function of a bounded centered variable and the Chernoff bounding method, both of which will be needed by the concentration results of later missions.

Difficulty

Lemma 4.2 is three inequalities on real numbers and is the intended entry point. Corollary 4.4 is Lemma 4.2 applied on the complement of the failure event of uniform convergence at $\epsilon/2$: the failure set of the learner is contained in the failure set of representativeness, and outer measure is monotone. Hoeffding's inequality is the substantial item: one needs the moment generating function bound $\mathbb{E}\,e^{\lambda(\theta-\mu)} \le e^{\lambda^2(b-a)^2/8}$ (Lemma B.7 of the book, by convexity of the exponential on $[a,b]$), independence of the coordinates under Measure.pi to factor the expectation of the product, Markov's inequality, and the optimization over $\lambda$; the two tails are treated separately and added. The degenerate cases are genuine: for $m = 0$ the bound is $2$ and the claim holds trivially, and for $a = b$ Lean's convention $x/0 = 0$ makes the bound $2$ again. Corollary 4.6 combines Hoeffding for each $h \in H$ with a union bound over the finite class and an arithmetic step showing that $m \ge \log(2|H|/\delta)/(2\epsilon^2)$ gives $2|H|e^{-2m\epsilon^2} \le \delta$; the empty class makes the uniform convergence clause vacuous. The second and third clauses of the goal then follow from Corollary 4.4, the third by exhibiting an ERM learner, which exists for a nonempty finite class by choosing a minimizer of $L_S$.

Formalization scope

The four items live in the general loss framework, not the binary-classification special case, because the chapter is stated for an arbitrary loss; Mission I's IsRepresentative and HasUniformConvergenceWith already carry the chapter's definitions, so no new definition module is introduced. Losses in Corollary 4.6 are real-valued with the range condition $\ell(h,z) \in [0,1]$ for every $z$ and measurability of $\ell(h,\cdot)$ for $h \in H$, which is what the book's "$\ell : H \times Z \to [0,1]$" and Remark 3.1 give. The book's "$m_H(\epsilon,\delta) \le \cdots$" is stated as "the guarantee holds with the function $\lceil \cdots \rceil$", the same convention as Mission I. In Corollary 4.4 the ERM clause is universal over ERM learners, matching "the ERM paradigm is a successful agnostic PAC learner" for every choice of minimizer; the existence of an ERM learner is a separate hypothesis for the learnability clause because a class with no minimizers on some sample has no ERM rule. Hoeffding's inequality is on i.i.d. coordinates of Measure.pi; the book's "$E[\theta_i] = \mu$" is the definition of $\mu$ rather than an assumption.

Trivializing readings are excluded: the failure events are bounded in outer measure, so measurability of the events is not a loophole; representativeness is required for every $h \in H$; the sample-complexity functions are the book's, with ceilings. Welcome contributions: Hoeffding's lemma on bounded centered variables, the factorization of the moment generating function under Measure.pi, and a reusable union bound over a finite class.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 4 and Appendix B. doi:10.1017/CBO9781107298019
• W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58(301), 1963. doi:10.1080/01621459.1963.10500830
• V. N. Vapnik, A. Ya. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and its Applications 16(2), 1971. doi:10.1137/1116025
• S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence, Oxford University Press, 2013, Chapter 2. doi:10.1093/acprof:oso/9780199535255.001.0001

Motivation

Missions I and II of this series showed that finite hypothesis classes are learnable, with and without the realizability assumption, by empirical risk minimization. Chapter 5 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) asks the converse question: is prior knowledge, in the form of a restricted hypothesis class, really necessary? Could there be a universal learner, an algorithm that, given enough examples from any distribution, outputs a predictor of low risk? The No-Free-Lunch theorem (Theorem 5.1) answers no: for binary classification with the 0–1 loss over a domain $X$, for every learning algorithm and every training-set size $m$ smaller than $|X|/2$ there is a distribution on which the learner fails with probability at least $1/7$, even though that distribution is perfectly predictable by some function $f$, so that another learner (ERM over $\{f\}$) succeeds. The consequence for the framework is Corollary 5.2: over an infinite domain, the class of all functions is not PAC learnable. This is the first lower bound of the book and the reason the rest of it is about the complexity of hypothesis classes rather than about universal algorithms.

Setting

The framework is the UnderstandingML_Framework module of Mission I, cited as a reference. Binary classification over a domain $X$ uses examples in $X \times \{0,1\}$, hypotheses $h : X \to \{0,1\}$ and the 0–1 loss, so the risk of $h$ under a distribution $D$ over $X \times \{0,1\}$ is $L_D(h) = D(\{(x,y) : h(x) \ne y\})$, computed as the integral of the 0–1 loss. A learner is a function from samples of each size to hypotheses, and a sample of size $m$ has the law $D^m$. PAC learnability of a class $H$ (Definition 3.1) requires a sample-complexity function $m_H$ and a learner $A$ such that for every $\epsilon, \delta \in (0,1)$, every distribution $D$ over $X$ and every measurable labeling function $f$ realizable by $H$, samples of size $m \ge m_H(\epsilon,\delta)$ yield $L_{(D,f)}(A(S)) \le \epsilon$ with probability at least $1-\delta$.

Two conventions specific to this mission. The domain $X$ is assumed to have measurable singletons (the book's Remark 3.1 assumes away measurability issues); this makes the finitely supported distributions of the proof honest probability measures and makes every $L_D(h)$ under them a genuine integral. And "$m$ smaller than $|X|/2$" is written $2m < |X|$ in the extended natural numbers, so that an infinite domain satisfies it for every $m$.

Formalization targets

Goal: Theorem 5.1 (No-Free-Lunch)

Let $A$ be any learning algorithm for binary classification with respect to the 0–1 loss over a domain $X$ with measurable singletons, and let $m$ be a training-set size with $2m < |X|$. Then there exists a probability distribution $D$ over $X \times \{0,1\}$ such that

1. there is a measurable $f : X \to \{0,1\}$ with $L_D(f) = 0$;
2. there is a measurable set $E$ of samples of size $m$ with $D^m(E) \ge 1/7$ on which $L_D(A(S)) \ge 1/8$.

Milestones

Lemma B.1 (Appendix B). If $Z$ takes values in $[0,1]$ and $E[Z] = \mu$, then for every $a \in (0,1)$, $P[Z > 1-a] \ge (\mu - (1-a))/a$, and consequently $P[Z > a] \ge (\mu - a)/(1-a) \ge \mu - a$.

Equation (5.2). Under the hypotheses of Theorem 5.1 there are $D$ and a measurable $f$ with $L_D(f) = 0$ and $\mathbb{E}_{S \sim D^m}[L_D(A(S))] \ge 1/4$.

Corollary 5.2. For an infinite domain $X$ with measurable singletons, the class of all functions $X \to \{0,1\}$ is not PAC learnable.

Two further items: Exercise 5.1, the passage from an expectation of at least $1/4$ to a probability of at least $1/7$ of exceeding $1/8$ for a $[0,1]$-valued variable; and Exercise 5.3, the $k$-fold version of Equation (5.2), with bound $1/2 - 1/(2k)$ when $km \le |X|$, $k \ge 2$ and $X$ is nonempty.

Significance

The No-Free-Lunch theorem is the book's first impossibility result and the conceptual pivot of Part I: it shows that learnability is a property of the pair (hypothesis class, learner) and not of the learner alone, and it motivates the bias–complexity tradeoff of §5.2 and the VC-dimension of Chapter 6, whose lower bound (Theorem 6.7, the "only if" direction of the fundamental theorem) is proved by the same symmetrization argument. Corollary 5.2 is the statement that the class of all functions has infinite sample complexity, the negative half of the characterization of learnable classes.

Nothing here is machine-checked. The proof is combinatorial and elementary but has real content for a formalization: a finite subset $C$ of the domain, the $2^{2m}$ labelings of $C$, the uniform distribution on $C$ labeled by each of them, an exchange of a maximum, an average and a minimum over labelings and sample sequences, and a pairing argument on labelings that differ at exactly one unseen point. Lemma B.1 is a reverse Markov inequality for bounded variables that later chapters also use.

Difficulty

Lemma B.1 is Markov's inequality applied to $1 - Z$ and is the entry point; Exercise 5.1 is its instance with $a = 1/8$ and $\mu \ge 1/4$, giving $(1/4 - 1/8)/(7/8) = 1/7$, together with the inclusion of $\{\theta > 1/8\}$ in $\{\theta \ge 1/8\}$. Theorem 5.1 follows from Equation (5.2) and Exercise 5.1 once one knows that $S \mapsto L_D(A(S))$ is, under the finitely supported $D^m$, almost everywhere equal to a measurable function with values in $[0,1]$; the set $E$ is the intersection of the event with the finite support of $D^m$, which is measurable because singletons are. Equation (5.2) is the heart of the mission. One picks $C \subseteq X$ of size $2m$ (available because $2m < |X|$), lets $D_i$ be uniform on $C$ labeled by the $i$-th function $f_i : C \to \{0,1\}$ extended by $0$ off $C$, and computes $\mathbb{E}_{S \sim D_i^m}[L_{D_i}(A(S))]$ as an average over the $(2m)^m$ sequences of instances, which requires identifying $D_i^m$ as a finitely supported measure on sequences, that is, the product of finitely supported measures. The inequalities (5.4)–(5.6) exchange max, average and min and restrict to the unseen points, and the pairing argument shows that for each unseen point the average over $i$ of the indicator that $A$ errs on it is exactly $1/2$. Exercise 5.3 is the same argument with $|C| = km$, where at least $(k-1)m$ points are unseen. Corollary 5.2 takes $\epsilon < 1/8$, $\delta < 1/7$, $m = m_H(\epsilon,\delta)$ and a set $C$ of size $2m$ in the infinite domain, and derives the contradiction from Theorem 5.1 via the identification of $L_D$ for $D$ uniform on $C$ labeled by $f$ with the true error $L_{(D_X, f)}$ of Definition 3.1, where $D_X$ is uniform on $C$; the case $m = 0$ is handled separately with a single point.

Formalization scope

The items are stated in the joint-distribution form of the book's Chapter 5, with $D$ over $X \times \{0,1\}$ and $L_D$ the risk under the 0–1 loss, rather than in the $(D, f)$ form of Definition 3.1; Corollary 5.2 is the bridge and is stated with the framework's PACLearnable. Witness labeling functions are required to be measurable, because a non-measurable $f$ would make $L_D(f) = 0$ true by Lean's convention for non-integrable functions rather than by content. Clause (2) of Theorem 5.1 is stated in the inner form (a measurable set of probability at least $1/7$ inside the event) rather than as a lower bound on the outer measure of the event, which for a non-measurable event would be the weaker statement. The size condition uses ENat.card, so infinite domains satisfy it. Learners are deterministic functions of the sample; the book's argument goes through for randomized learners by averaging, but the framework does not model them.

Trivializing readings are excluded: the distribution must be a probability measure, the failing set must be measurable with an honest lower bound, and the witness $f$ must be measurable. Welcome contributions: the finitely supported product law on sequences, the averaging identity (5.3), and the pairing argument on labelings of $C$.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 5 and Appendix B. doi:10.1017/CBO9781107298019
• D. H. Wolpert, W. G. Macready, No free lunch theorems for optimization, IEEE Transactions on Evolutionary Computation 1(1), 1997. doi:10.1109/4235.585893
• A. Ehrenfeucht, D. Haussler, M. Kearns, L. Valiant, A general lower bound on the number of examples needed for learning, Information and Computation 82(3), 1989. doi:10.1016/0890-5401(89)90002-3
• V. N. Vapnik, Statistical Learning Theory, Wiley, 1998.

Motivation

The fundamental theorem of Mission IV says that a class of binary classifiers is PAC learnable exactly when its VC-dimension is finite. That leaves out classes one would like to learn, such as all polynomial classifiers over the line, whose VC-dimension is infinite although each degree separately is learnable. Chapter 7 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) relaxes the definition. In nonuniform learnability (Definition 7.1) the sample size may depend on the hypothesis the learner is competing with: the learner must, for every $h \in H$, eventually do as well as $h$ up to $\epsilon$, but how soon may depend on $h$. The chapter's main result (Theorem 7.2) characterizes the nonuniformly learnable classes of binary classifiers as the countable unions of agnostic PAC learnable classes. The learning rule behind it is Structural Risk Minimization (SRM): write $H = \bigcup_n H_n$, weight the pieces, and minimize the empirical risk plus a confidence term that grows with the index (Theorems 7.3–7.5). Applied to a countable class described by a prefix-free code, SRM becomes the Minimum Description Length rule and yields a quantitative form of Occam's razor (Lemma 7.6, Theorem 7.7). The chapter closes the circle with a No-Free-Lunch result for the relaxed notion (Remark 7.2, Exercise 7.5).

Setting

The framework is that of Missions I, II and IV: examples in a domain $Z$, a hypothesis type with a class $H$, a loss $\ell$, risk $L_D$ and empirical risk $L_S$, learners as functions of the sample, the uniform convergence property with an explicit rate $m^{UC}_H$, agnostic PAC learnability, and for binary classification the 0–1 loss, the VC-dimension and pointwise separability. The new module adds Definition 7.1 with an explicit rate $m^{NUL}$ and, as in Definition 3.4, learners whose outputs lie in $H$; the same notion for a family of learners indexed by the confidence $\delta$, since the SRM and MDL rules take $\delta$ as an input; the rate $\epsilon_n(m,\delta) = \inf\{\epsilon \in (0,1) : m^{UC}_{H_n}(\epsilon,\delta) \le m\}$ of Equation (7.1), which is meaningful only when that set is nonempty; the index $n(h) = \min\{n : h \in H_n\}$ of Equation (7.4); the SRM rule as a minimizer of $L_S(h) + \epsilon_{n(h)}(m, w(n(h))\delta)$ over the admissible hypotheses, those whose index has positive weight and a defined rate; prefix-free description languages $d : H \to \{0,1\}^*$ and the MDL rule; and shattering of an infinite set.

Formalization targets

Goal: Theorem 7.2

For a class $H$ of measurable binary classifiers over a domain with measurable singletons, every subclass of which is pointwise separable, $H$ is nonuniformly learnable if and only if there are classes $H_n$ with $\bigcup_n H_n = H$, each agnostic PAC learnable.

Milestones

Theorem 7.3. If $H = \bigcup_n H_n$ is nonempty and each $H_n$ has the uniform convergence property, then $H$ is nonuniformly learnable (general loss).

Theorem 7.4. For weights $w(n) \in [0,1]$ with partial sums at most $1$, uniformly convergent pieces $H_n$ with rates $m^{UC}_{H_n}$, $\delta \in (0,1)$, any $D$ and any $m$: with probability at least $1-\delta$, for every $n$ with $w(n) > 0$ at which $\epsilon_n(m, w(n)\delta)$ is defined and every $h \in H_n$, $|L_D(h) - L_S(h)| \le \epsilon_n(m, w(n)\delta)$.

Theorem 7.5. With $w(n) = 6/(\pi^2 n^2)$ and $H_0 = \emptyset$, every family of learners implementing the SRM rule satisfies the nonuniform guarantee with rate $m^{NUL}(\epsilon,\delta,h) = m^{UC}_{H_{n(h)}}(\epsilon/2,\ 6\delta/(\pi n(h))^2)$.

Lemma 7.6 (Kraft). For a prefix-free set $S$ of binary strings, every finite subfamily satisfies $\sum_{\sigma} 2^{-|\sigma|} \le 1$.

Theorem 7.7. For a prefix-free description language on a class with a $[0,1]$-valued loss, $m \ge 1$ and $\delta > 0$: with probability at least $1-\delta$, every $h \in H$ satisfies $L_D(h) \le L_S(h) + \sqrt{(|h| + \ln(2/\delta))/(2m)}$.

Further items: nonuniform learnability is implied by agnostic PAC learnability (§7.1); a nonuniformly learnable class of binary classifiers is a countable union of classes of finite VC-dimension (Exercise 7.5 (1)–(2)); a class shattering an infinite set admits no countable cover by classes of finite VC-dimension (Exercise 7.5 (3)) and is not nonuniformly learnable; over an infinite domain the class of all measurable classifiers is not nonuniformly learnable (Remark 7.2).

Significance

Theorem 7.2 is the second characterization theorem of the book's Part I and the one that explains why model selection works: any class that can be stratified into learnable pieces is learnable in the nonuniform sense, with the price of not knowing the index paid in sample size rather than in principle. SRM is the abstract form of every penalized learning rule, and the MDL bound of Theorem 7.7 is the cleanest instance, a bound in which the only property of the hypothesis that matters is the length of its description. Remark 7.2 shows the relaxation is not free: even nonuniformly, no learner handles all classifiers over an infinite domain.

Nothing here is machine-checked. The chapter's arguments are short but they combine everything before them: Hoeffding, the union bound with weights, the VC lower bound of Corollary 6.4 and the fundamental theorem. Three places where the book's statements need care are recorded in the formalization: the rate $\epsilon_n$ is an infimum that may be undefined for small $m$; the SRM rule takes $\delta$ as an input and so is a family of learners; and the fundamental theorem's uniform-convergence direction needs a measurability condition, which appears in Theorem 7.2 as hereditary pointwise separability.

Difficulty

The relaxation remark is a direct comparison of two definitions. Kraft's inequality is the coin-tossing argument of the book or an induction on the maximal length: it is the intended entry point. Theorem 7.4 is Theorem 7.3's engine: for each index and each $\epsilon$ in the set of Equation (7.1), the uniform convergence property bounds the failure by $w(n)\delta$; the passage from "every $\epsilon$ in the set" to the infimum uses continuity of the outer measure along an increasing union; the union over $n$ uses countable subadditivity and the partial-sum condition. Theorem 7.5 is Theorem 7.4 on the good event together with the two inequalities of the book's proof, using that the target is admissible when $m \ge m^{UC}_{H_{n(h)}}(\epsilon/2, w(n(h))\delta)$ and that admissibility of the SRM output gives the bound for it. Theorem 7.3 asks for a single learner: SRM with a confidence schedule $\delta_m \to 0$ chosen so that, for each fixed index, the rate at level $\delta_m$ eventually falls below any $\epsilon$, together with an approximate minimizer within $1/m$; the target hypothesis is admissible for $m$ large. Theorem 7.7 is Theorem 7.4 with singleton pieces and the weights $2^{-|h|}$, a one-sided Hoeffding bound for each $h$, and Kraft's inequality. Exercise 7.5 (3) is the combinatorial construction of the book's hint, disjoint finite subsets $K_n$ of the shattered set with $|K_n| > \mathrm{VCdim}(H_n)$ and a labeling that no $H_n$ realizes. The first half of Theorem 7.2 is Corollary 6.4 applied to the nonuniform learner at fixed $\epsilon_0, \delta_0$, with constants chosen so that the two probability bounds actually contradict; the second half is the fundamental theorem on each piece followed by Theorem 7.3.

Formalization scope

Learners output hypotheses in $H$, in Definition 7.1 as in Definition 3.4. The rate $\epsilon_n$ is an infimum over the set of Equation (7.1), and every statement that uses it is guarded by the nonemptiness of that set; the weight $w(n)$ may be $0$, and $H_0 = \emptyset$ encodes the book's indices $1, 2, \dots$. The SRM rule minimizes over admissible hypotheses, and an SRM family is one that returns an admissible minimizer whenever some hypothesis is admissible, which is the book's assumption that the argmin is attained (automatic for the 0–1 loss). Theorem 7.4's sum condition is on partial sums, and Kraft's inequality is on finite subfamilies, so no divergent series is silently zero. Theorem 7.7 assumes a $[0,1]$-valued loss and $m \ge 1$. The binary-classification results assume measurable singletons and measurable hypotheses; Theorem 7.2 also assumes every subclass pointwise separable, which every class over a countable domain satisfies. Definition 7.8 (consistency) and the Memorize algorithm of §7.4 are not stated.

Trivializing readings are excluded: outputs in $H$ keep the risk an honest integral, the rate is never a junk infimum of the empty set, and the failure events are bounded in outer measure. Welcome contributions: a reusable weighted union bound over a countable family of uniform-convergence events, the continuity argument for the infimum rate, and the shattered-set combinatorics of Exercise 7.5.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 7. doi:10.1017/CBO9781107298019
• V. N. Vapnik, The Nature of Statistical Learning Theory, Springer, 1995. doi:10.1007/978-1-4757-2440-0
• J. Rissanen, Modeling by shortest data description, Automatica 14(5), 1978. doi:10.1016/0005-1098(78)90005-5
• A. Blumer, A. Ehrenfeucht, D. Haussler, M. K. Warmuth, Occam's razor, Information Processing Letters 24(6), 1987. doi:10.1016/0020-0190(87)90114-1
• L. G. Kraft, A device for quantizing, grouping, and coding amplitude modulated pulses, MSc thesis, MIT, 1949.

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.

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

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