Probability

Motivation

Richard Bellman's survey The theory of dynamic programming (Bull. Amer. Math. Soc. 60 (1954), 503–515, DOI 10.1090/s0002-9904-1954-09848-8) introduced dynamic programming to a general mathematical audience. It states the principle of optimality (§2, p. 504): "An optimal policy has the property that whatever the initial state and initial decisions are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decisions", and derives from it the functional equations of finite and infinite stochastic decision processes, (4.2) and (5.1) (p. 506).

The survey illustrates the method on a small number of worked examples. The second of them, §8 "Stochastic gold mining" (pp. 508–509), is the one with a sharp answer: a two-armed sequential allocation problem with an absorbing failure state, whose optimal policy is a simple index rule. It is an early instance of the allocation-index phenomenon later made general by Gittins and Jones (1974) and Gittins (1979), and the paper itself notes (p. 509) that the rule "is not valid generally in more complicated decision processes", citing a counterexample of Karlin and Shapiro. The full treatment is in Bellman's RAND report R-245 and his 1957 book Dynamic Programming.

Setting

Two gold mines, Anaconda ($A$) and Bonanza ($B$), hold amounts $x \ge 0$ and $y \ge 0$ of gold. A single machine can be used in either mine. A use in Anaconda succeeds with probability $p$: it then mines a fraction $r$ of the gold currently in Anaconda and the machine stays undamaged. With probability $1-p$ it mines nothing and the machine is destroyed. Bonanza behaves the same way with probability $q$ and fraction $s$. While the machine works, the operator chooses the next mine; the aim is to maximize the expected amount mined before the machine is destroyed.

The only information the operator ever receives is that the machine still works. A policy is therefore a choice sequence $\sigma = (\sigma_0, \sigma_1, \dots) \in \{A, B\}^{\mathbb N}$: the mine for use number $n$, applied if uses $0, \dots, n-1$ succeeded. With $a_n$, $b_n$ the numbers of $A$- and $B$-uses among the first $n$, use $n$ collects $g_n = r x (1-r)^{a_n}$ if $\sigma_n = A$ and $g_n = s y (1-s)^{b_n}$ if $\sigma_n = B$, and does so with probability $\prod_{k=0}^{n} \pi_{\sigma_k}$ ($\pi_A = p$, $\pi_B = q$). The expected return is

$$J(\sigma; x, y) = \sum_{n \ge 0} \Big(\prod_{k=0}^{n} \pi_{\sigma_k}\Big) g_n ,$$

and Bellman's (8.1) defines the optimal return

$$f(x, y) = \sup_\sigma J(\sigma; x, y).$$

In Lean these are expectedReturn p q r s σ x y and optimalReturn p q r s x y in the namespace BellmanTheoryDP.GoldMining.

Formalization targets

Milestone: the functional equation (8.2), p. 508

$$f(x, y) = \max\Big\{ p\,[r x + f((1-r)x, y)],\ q\,[s y + f(x, (1-s)y)] \Big\}.$$

Goal: the decision rule (8.3), p. 509, corrected

Write $V_A = p[rx + f((1-r)x, y)]$ and $V_B = q[sy + f(x, (1-s)y)]$ for the two branches of (8.2). For $0 < p, q, r, s < 1$ and $x, y \ge 0$:

$$\frac{prx}{1-p} > \frac{qsy}{1-q} \Rightarrow V_A > V_B, \qquad \frac{prx}{1-p} < \frac{qsy}{1-q} \Rightarrow V_A < V_B, \qquad \frac{prx}{1-p} = \frac{qsy}{1-q} \Rightarrow V_A = V_B .$$

The paper prints the rule with $(1-r)$ and $(1-s)$ in the denominators:

a. For $prx/(1 - r) > qsy/(1 - s)$, choose A, b. For $prx/(1 - r) < qsy/(1 - s)$, choose B, c. For $prx/(1 - r) = qsy/(1 - s)$, choose either.

and glosses it as "the locus of points where immediate expected gain over immediate expected loss is the same for both choices". The immediate expected loss is the probability of destroying the machine, $1-p$ (resp. $1-q$), not $1 - r$. As printed the rule is false: with $p = 1/2$, $r = 0.9$, $q = 0.9$, $s = 0.1$, $x = 1$, $y = 2$ the printed indices are $4.5 > 0.2$, but $V_A \approx 0.924 < V_B \approx 1.055$. The mission's goal is the corrected rule, the one the paper describes in words.

Companion: the index policy is optimal, p. 509

"Using this prescription, $f(x, y)$ may be computed recurrently": the choice sequence $\sigma^*$ generated by applying the corrected rule to the current amounts at every use satisfies $J(\sigma^*; x, y) = f(x, y)$.

Significance

The decision rule reduces an optimization over infinite sequences to comparing two explicit numbers, one per mine, each depending only on that mine's own data. This is the defining property of an index policy, and gold mining is one of the earliest problems where it was observed. The functional equation (8.2) is the concrete form, for this process, of the infinite-horizon equation (5.1) that the paper states formally.

Formalizing the example yields a complete machine-checked instance of the principle of optimality for an infinite-horizon stochastic process whose state space (the amounts left in the two mines) is infinite, where the supremum over policies is not attained trivially and the finite-horizon recursion does not apply directly. It also records, with a checked statement, the correction of the misprint in (8.3). No machine-checked proof of (8.2) or (8.3) is known to exist.

Difficulty

The equation (8.2) looks immediate, and the paper calls it "easily seen". The informal argument treats $f$ as the value of an optimal policy, but $f$ is a supremum over infinite sequences that need not be attained a priori, and the return of a sequence is an infinite series. The finite-horizon recursion (4.2) does not apply as it stands, because the process has no last stage and its state space, the amounts left in the two mines, is infinite.

The rule (8.3) compares the two optimal continuations $f((1-r)x, y)$ and $f(x, (1-s)y)$, which are themselves unknown. A comparison of the one-step gains alone does not decide it, as the misprinted rule shows. Parts a and b are strict preferences, so it is not enough to show that one choice is at least as good as the other.

Formalization scope

• Representation. The mines are a two-element inductive type Mine; a policy is a function ℕ → Mine (ChoiceSeq). All quantities are real numbers. Randomized policies are mixtures of choice sequences and give no larger return, so they are not modelled. No restriction to stationary or Markov policies is made: $f$ is the supremum over all sequences.
• Parameter ranges. The paper does not state them. The theorems assume $0 < p, q, r, s < 1$ and $x, y \ge 0$ (zero amounts allowed). $p, q < 1$ keeps the indices $prx/(1-p)$, $qsy/(1-q)$ well defined.
• Series and supremum. $J$ is a real tsum and $f$ a real iSup. For the parameter ranges above the terms are nonnegative, the partial sums are bounded by $x + y$, and the family is bounded above, so neither Lean default value (0 for a divergent series or an unbounded supremum) arises; this is stated as the auxiliary theorem expectedReturn_le_add.
• Survival indexing. The gold of use $n$ is counted only if use $n$ itself succeeds, so the survival product runs over $k \le n$.
• The misprint. The goal and the index policy use $(1-p)$, $(1-q)$ in place of the printed $(1-r)$, $(1-s)$. The printed rule appears only as the quotation above.
• No trivializing encoding. $f$ is defined as the supremum of expected returns over all choice sequences, per (8.1); it is not defined as a solution of (8.2), as the value of the index policy, or as a limit of value iteration, any of which would make the milestone or the goal true by definition.
• Auxiliary theorems (not from the paper). The bound $0 \le J \le x + y$ with summability, the one-step unrolling $J(\sigma) = p[rx + J(\sigma'; (1-r)x, y)]$ when $\sigma_0 = A$ (and symmetrically), and the single-mine values $f(x, 0) = prx/(1 - p(1-r))$, $f(0, y) = qsy/(1-q(1-s))$ are included as footholds. They are not milestones.
• Related platform content. AllocationIndices.two_discount_index_policy_optimal (Gittins et al., Theorem 3.4) concerns Markov bandits whose rewards are discounted by $a^t$ at global time $t$; gold mining multiplies by the success probability of each use of the mine used, so it is a different model and is not reused. BertsekasDP.dp_algorithm_optimality is finite-horizon and does not give (8.2).

Contributions welcome: proofs of the auxiliary theorems, of (8.2), of the decision rule, and of the optimality of the index policy.

Selected references

• R. Bellman, The theory of dynamic programming, Bull. Amer. Math. Soc. 60 (1954), no. 6, 503–515. https://doi.org/10.1090/s0002-9904-1954-09848-8
• R. Bellman, Dynamic Programming, Princeton University Press, 1957.
• J. C. Gittins, Bandit processes and dynamic allocation indices, J. Roy. Statist. Soc. Ser. B 41 (1979), 148–177. https://doi.org/10.1111/j.2517-6161.1979.tb01068.x
• J. C. Gittins, K. D. Glazebrook, R. Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley, 2011. https://doi.org/10.1002/9780470980033

Motivation

In robust stochastic optimization a decision maker chooses a decision $x$ whose outcome depends on a random vector $\mathbf R$, but knows only the first two moments of $\mathbf R$: its mean vector $\mu$ and its covariance matrix $\Sigma$. The decision is evaluated by its worst-case expected utility over every distribution consistent with those moments. This model is standard in portfolio selection, where estimated means and covariances are the usual inputs, and in pricing and inventory problems with mean-variance information. It goes back to Scarf's min-max newsvendor (1958) and the Chebyshev-type moment bounds of Bertsimas and Popescu (2005).

For a linear outcome $x'\mathbf R$, such as the return of a portfolio with weights $x$, the robust objective is

$$U(x) = \min_{\mathbf R \sim (\mu,\Sigma)} E[u(x'\mathbf R)],$$

an optimization over an infinite-dimensional set of $n$-variate distributions. Popescu (2007) showed that this problem depends on $\mu$ and $\Sigma$ only through the scalar mean $\mu_x = x'\mu$ and variance $\sigma_x^2 = x'\Sigma x$. The multivariate robust problem then reduces to a univariate moment problem, and for many utilities to a parametric quadratic program. The reduction rests on one structural fact, the general projection property, which this mission formalizes.

Setting

Fix a dimension $n$. A law on $\mathbb R^n$ is a Borel probability measure on $\mathbb R^n$. For a vector $\mu \in \mathbb R^n$ and a real $n\times n$ matrix $\Sigma$, the mean-covariance class $\mathbb M^n_{(\mu,\Sigma)}$ is the set of laws $P$ under which every coordinate $R_i$ has a finite second moment and

$$\int R_i\,dP(R) = \mu_i, \qquad \int (R_i-\mu_i)(R_j-\mu_j)\,dP(R) = \Sigma_{ij} \qquad (1\le i,j\le n).$$

Writing $\mathbf R \sim (\mu,\Sigma)$ means that the law of $\mathbf R$ lies in $\mathbb M^n_{(\mu,\Sigma)}$. For $n=1$ the superscript is dropped: for real $m$ and $v$, $\mathbb M_{(m,v)}$ is the set of laws on $\mathbb R$ with finite second moment, mean $m$ and variance $v$.

For a vector $x \in \mathbb R^n$, the $x$-projection sends the law $P$ of $\mathbf R$ to the law of the scalar $\mathbf r = x'\mathbf R$, that is, to the pushforward of $P$ under $R \mapsto x'R$. Write $\mu_x = x'\mu$ and $\sigma_x^2 = x'\Sigma x$. The matrix $\Sigma$ is positive semidefinite, $\Sigma \succeq 0$, when $x'\Sigma x \ge 0$ for all $x$ (and $\Sigma$ is symmetric); $\Sigma^{1/2}$ denotes its positive semidefinite square root.

Formalization targets

Goal: Theorem 1 (General Projection Property)

For every $\mu \in \mathbb R^n$, every $\Sigma \succeq 0$ and every nonzero $x \in \mathbb R^n$, the $x$-projection maps $\mathbb M^n_{(\mu,\Sigma)}$ into and onto $\mathbb M_{(\mu_x,\sigma_x^2)}$:

$$\bigl\{\, \text{law of } x'\mathbf R \;:\; \mathbf R \sim (\mu,\Sigma) \bigr\} \;=\; \mathbb M_{(x'\mu,\; x'\Sigma x)}.$$

The "into" half says every projected law has the right mean and variance. The "onto" half says that every univariate law with mean $\mu_x$ and variance $\sigma_x^2$, however heavy-tailed or irregular, is the law of $x'\mathbf R$ for some $\mathbf R \sim (\mu,\Sigma)$. The degenerate case $x'\Sigma x = 0$ is included.

Milestones

1. The into half (§2.1, justification of (4)): $x'\mathbf R$ has mean $x'\mu$ and variance $x'\Sigma x$.
2. The degenerate case: if $x'\Sigma x = 0$ then $x'\mathbf R = x'\mu$ almost surely.
3. Standardization: if $\mathbf r \sim (m, v)$ with $v > 0$, then $v^{-1/2}(\mathbf r - m) \sim (0,1)$.
4. Normalization: for $x'\Sigma x > 0$, the vector $y = (x'\Sigma x)^{-1/2}\Sigma^{1/2}x$ satisfies $y'y = 1$.
5. Isotropic lift: if $y'y = 1$ and $\mathbf z \sim (0,1)$, there is $\mathbf Z \sim (0, I_n)$ with $y'\mathbf Z$ distributed as $\mathbf z$.
6. Affine image: if $\mathbf Z \sim (0,I_n)$ then $\mu + \Sigma^{1/2}\mathbf Z \sim (\mu,\Sigma)$, and $x'(\mu + \Sigma^{1/2}Z) = x'\mu + (x'\Sigma x)^{1/2}\,y'Z$ for every $Z$.

Significance

The result. Theorem 1 immediately yields Proposition 1 of the paper: for every objective $u$,

$$\min_{\mathbf R\sim(\mu,\Sigma)} E[u(x'\mathbf R)] = \min_{\mathbf r\sim(\mu_x,\sigma_x^2)} E[u(\mathbf r)],$$

with minima in the wide sense of infima. The robust objective is therefore a function of $(\mu_x, \sigma_x)$ alone, which makes every robust mean-covariance problem with a linear outcome a bicriteria mean-variance problem. The paper's later results use this: the two-point and one-point support properties, the parametric quadratic programming solution, and the portfolio applications (bonus schemes, value at risk). The projection property holds with no assumption on $u$, so it serves non-concave, discontinuous and quantile-based objectives alike.

Formalizing it. The theorem is proved in the paper; no machine-checked version is known. The mission produces a formal definition of mean-covariance classes that treats integrability honestly, a proof of the projection property, and through it a formally verified reduction of multivariate moment-robust problems to univariate ones. The paper's own construction of the lifted vector has a gap (see Difficulty), so a formal proof also records a corrected argument.

Difficulty

The into half is a computation with linearity of expectation. The difficulty is entirely in the onto half. Given an arbitrary univariate law with prescribed mean and variance, one must build an $n$-variate law with a prescribed full covariance matrix whose one-dimensional marginal in direction $x$ is exactly the given law. This is a coupling problem: the obvious approach, taking independent coordinates, fixes the marginal in direction $x$ as a convolution and cannot reproduce an arbitrary target. Taking $\mathbf R$ supported on the line through $\mu$ in a single direction reproduces the target law but has a rank-one covariance and fails whenever $\Sigma$ has rank above one.

The paper's appendix constructs the lift through conditional distributions of the remaining coordinates given the projected one. As printed, the conditional second-moment requirement it imposes cannot hold for unbounded targets, so that argument does not go through verbatim. The milestone for the lift states only the claim, not the printed construction.

The integrability bookkeeping is real work: every intermediate law must be shown to have finite second moments before its moments can be computed.

Formalization scope

• $\mathbb R^n$ is EuclideanSpace ℝ (Fin n) with its Borel σ-algebra; $x'R$ is the inner product $\langle x, R\rangle$; $x'\Sigma x$ is x.ofLp ⬝ᵥ S *ᵥ x.ofLp, where the matrix $\Sigma$ is named S (the symbol Σ is reserved in Lean).
• Laws are probability measures. Both classes require finite second moments (MemLp … 2), so that means and covariances are genuine integrals, not the default value $0$ that Lean assigns to non-integrable functions. The univariate class is parametrized by the variance $v = \sigma^2$, not by $\sigma$.
• The projection is the pushforward P.map (fun R => ⟪x, R⟫) under a continuous map. "Pathwise" identities in the paper become equalities of pushforward laws, or pointwise algebraic identities.
• $\Sigma^{1/2}$ is CFC.sqrt S, acting through Matrix.toEuclideanCLM, as in Mathlib's multivariateGaussian.
• The goal is stated as Set.MapsTo ∧ Set.SurjOn with both classes explicit. Its only hypotheses are $\Sigma \succeq 0$ and $x \ne 0$, as in the paper. No bound on $n$, no invertibility of $\Sigma$ and no positivity of $x'\Sigma x$ is assumed. Restricting the target to Gaussian, bounded or finitely supported laws, or dropping the finite-second-moment clause (which would admit Cauchy laws as "mean 0, variance 0"), would trivialize or change the theorem and is ruled out.
• Milestones 3, 4 and 6 assume $x'\Sigma x > 0$ (or $v > 0$), the case the proof treats after its first sentence; milestone 2 covers the complementary case.

Needed infrastructure: moments of pushforwards under linear and affine maps, a covariance calculus for coordinates of random vectors, and a coupling that realizes the isotropic lift. Mathlib's multivariateGaussian, stdGaussian and CFC.sqrt are available. A reusable lemma "the covariance of $A\mathbf Z + b$ is $A\,\mathrm{Cov}(\mathbf Z)A'$" would serve beyond this mission. Related platform work on moment-based ambiguity sets: Wasserstein Distributionally Robust Optimization II. Contributions of any milestone, and alternative proofs of the lift, are welcome.

Selected references

• I. Popescu, Robust Mean-Covariance Solutions for Stochastic Optimization, Operations Research 55(1):98–112, 2007. https://doi.org/10.1287/opre.1060.0353
• D. Bertsimas, I. Popescu, Optimal Inequalities in Probability Theory: A Convex Optimization Approach, SIAM Journal on Optimization 15(3):780–804, 2005. https://doi.org/10.1137/S1052623401399903
• H. Scarf, A Min-Max Solution of an Inventory Problem, in Studies in the Mathematical Theory of Inventory and Production, Stanford University Press, 1958.
• W. W. Rogosinski, Moments of Non-Negative Mass, Proceedings of the Royal Society A 245:1–27, 1958. https://doi.org/10.1098/rspa.1958.0062

Motivation

In stochastic linear optimization under bandit feedback a learner repeatedly chooses a point $x_t$ from a compact decision set $D\subset\mathbb R^n$ and observes only the random cost $\ell_t$ of that point, whose mean is $\mu\cdot x_t$ for an unknown vector $\mu$. The problem models online routing, ad placement and other sequential decisions with linearly structured costs. The quality of a learner is measured by its regret against the best fixed decision.

For the $K$-armed bandit the achievable regret for a fixed instance is logarithmic in the horizon $T$ (Lai and Robbins 1985; Auer, Cesa-Bianchi and Fischer 2002). Dani, Hayes and Kakade (COLT 2008) showed that for linear costs the picture depends on the geometry of $D$. Their Theorem 1 gives polylogarithmic regret when the decision set has a positive gap between the best and second-best extreme point (a polytope, for instance), and their Theorem 2 gives $O^*(n\sqrt T)$ regret for every decision set. Their Theorem 3 shows that the second rate cannot be improved in general: on a decision set with zero gap, every algorithm pays $\Omega(\sqrt T)$ in expectation.

Timeline:

• 2002: Auer, Using confidence bounds for exploitation–exploration trade-offs (JMLR 3), introduces confidence-bound algorithms for linear bandits on finite decision sets.
• 2008: Dani, Hayes and Kakade prove the $O^*(n\sqrt T)$ upper bound for ConfidenceBall₂ and the $\Omega(\sqrt T)$ lower bound on a product of circles, the subject of this mission. A hypercube lower bound for the adversarial setting appears in their NIPS 2007 paper.
• 2010: Rusmevichientong and Tsitsiklis, Linearly parameterized bandits (Math. OR 35), give $\Omega(n\sqrt T)$ lower bounds on the unit sphere.
• 2020: Lattimore and Szepesvári, Bandit Algorithms, Theorems 24.1 and 24.2, give minimax lower bounds on the hypercube and the unit ball with Gaussian noise.

Setting

The decision set is the unit circle $D_2=S^1=\{x\in\mathbb R^2: x_1^2+x_2^2=1\}$. An unknown mean vector $\mu\in\mathbb R^2$ is drawn once, uniformly from the circle $D_2/2$ of radius $1/2$; concretely $\mu=\mu(\theta)=\tfrac12(\cos\theta,\sin\theta)$ with $\theta$ uniform on $[0,2\pi)$.

On each round $t=1,\dots,T$ the algorithm plays $x_t\in D_2$ and observes a cost $\ell_t\in\{-1,+1\}$ with $\Pr(\ell_t=+1)=(1+\mu\cdot x_t)/2$, so that $\mathbb E[\ell_t]=\mu\cdot x_t$. Given the decision, the cost is independent of the past.

An algorithm may be randomised. It draws a seed $s$ once from a probability measure $\rho$ on a measurable space $S$, and chooses $x_t$ as a function of $s$ and the costs $\ell_1,\dots,\ell_{t-1}$ observed so far, measurably in $s$.

The regret over $T$ rounds is

$$R=\sum_{t=1}^T(\mu\cdot x_t-\mu\cdot x^*),\qquad \mu\cdot x^*=\min_{x\in D_2}\mu\cdot x,$$

so each round costs $r_t=\mu\cdot x_t+\tfrac12\ge0$ when $\|\mu\|=1/2$. The expected regret $\mathbb E R=\mathbb E_\mu\,\mathbb E(R\mid\mu)$ averages over the seed, the prior and the costs.

In the Lean development these objects are unitCircle, meanVec, optCost, RandomizedPolicy and expectedRegret in the namespace StochLinOpt.LowerBound.

Formalization targets

Goal: Theorem 3 for $n=2$

There is a universal constant $c>0$ such that for every randomised algorithm and every $T\ge1$,

$$\mathbb E R\ \ge\ c\sqrt T.$$

The constant is left existential, which is the form that survives any later improvement of the constant; it is chosen before the algorithm and before $T$.

Milestones

1. Section 6.1, Eq. (3). For $\|\mu_1\|=\|\mu_2\|=1/2$, $x\in S^1$, a posterior probability $p\in[0,1]$ of $\mu=\mu_1$ and a cost $\ell\in\{\pm1\}$, the Bayes-updated bias $b_{t+1}$ satisfies $|b_{t+1}-b_t|\le|(\mu_1-\mu_2)\cdot x|$, where $b_t=2p-1$.
2. Lemma 15. With $\varepsilon=\|\mu_1-\mu_2\|>0$ and the same data,

$$\mathbb E_\mu(r_t\mid\mathcal H_t)\ge\frac1{16}\Big(\varepsilon^2+\frac{|b_{t+1}-b_t|^2}{\varepsilon^2}\Big)\mathbf 1\{|b_t|\le1/2\}.$$

3. Theorem 4 (Freedman). For a martingale difference sequence $X_1,\dots,X_T$ bounded above by $b$, with conditional variance sum $V$, and all $a,v>0$,

$$\Pr\Big(\sum_i X_i\ge a,\ V\le v\Big)\le\exp\Big(\frac{-a^2}{2v+2ab/3}\Big).$$

Significance

The lower bound shows that the $\sqrt T$ dependence of the problem-independent upper bound (Theorem 2 of the same paper) is necessary. It also shows that the gap-dependent polylogarithmic rate of Theorem 1 cannot extend to decision sets without a gap, such as the sphere. Together with the upper bound it characterises the minimax regret of stochastic linear bandits in $T$ up to logarithmic factors, and in the paper's general-$n$ form it also underlies the claim that the price of bandit information is $\Theta^*(\sqrt n)$.

The result is proved in the paper for $n=2$ and has not been machine-checked. The mission produces a checked Bayesian lower bound over all randomised algorithms, with an explicit probability model for the protocol. Two related platform results are different theorems: BanditAlgorithm.linear_bandit_unit_ball_minimax_lower_bound (Lattimore–Szepesvári Theorem 24.2: unit ball, Gaussian noise, a worst-case $\mu$) and BanditAlgorithm.linear_bandit_hypercube_minimax_lower_bound (Theorem 24.1: hypercube). The $\{-1,+1\}$ costs, the circle and the uniform prior used here are not covered by either.

Difficulty

The obvious attempt is a two-point change-of-measure argument with a fixed pair of means at distance $\varepsilon$. It fails as stated because the decision set has no gap: an algorithm that plays close to the optimum of both candidates learns slowly but also pays little. The per-round trade-off between regret and information (Lemma 15) is exact only while the posterior is undecided, $|b_t|\le1/2$. Turning it into a bound on the whole horizon requires controlling how long the posterior stays undecided, which is a statement about a martingale whose step sizes are chosen by the algorithm; a concentration bound that ignores the accumulated conditional variance (Azuma–Hoeffding with worst-case steps) is too weak for this. The averaging step from a two-point prior to the uniform prior on the circle is also part of the formal work.

Formalization scope

Vectors are Fin 2 → ℝ with the dot product ⬝ᵥ; Euclidean norms are written through dot products, never with Lean's sup norm. Rounds are 0-indexed internally: the Lean index $t$ is the paper's round $t+1$. The expected regret is the exact finite expectation

$$\mathbb E R=\int_S\frac1{2\pi}\int_0^{2\pi}\sum_{\ell\in\{\pm1\}^T}\prod_{t=1}^T\frac{1+\ell_t\,\mu(\theta)\cdot x_t}{2}\;R\;d\theta\,d\rho(s),$$

so no infinite product of measures is needed. A randomised algorithm is a seeded policy, which covers every randomised algorithm. The optimal cost is the infimum of $\mu\cdot x$ over the compact circle and is attained. Every junk value in the model (a non-integrable integrand) could only make the lower bound harder to prove, never easier.

A statement over deterministic algorithms only, over a worst-case $\mu$ instead of the uniform prior, or with the constant allowed to depend on the algorithm or on $T$ would be a weaker theorem. The goal quantifies $\exists c>0$ before the algorithm and $T$, and fixes the prior.

Corrections relative to the printed paper:

• General $n$ is not stated. Theorem 3 as printed claims $\mathbb E R\ge\frac1{10}n\sqrt T$ for every even $n$. It is false for $n>10$: on $D_n$ with $\mu\in D_n/n$ each round has regret at most $1$, so at $T=1$ the claim would need $\mathbb E R\ge n/10>1$. The general case rests on Lemma 16, which has no proof. The goal is the $n=2$ case, which Section 6.1 proves.
• The constant. For $n=2$ the paper prints $\frac15\sqrt T$; its proof gives $c=\frac1{16}\min(\frac12-\frac1e,\frac1{64})=\frac1{1024}$. The proof's Freedman step prints $2\exp(-\frac{1/4}{1/8+\varepsilon/3})\le 2/e^2$; with $v=1/32$ the denominator is $1/16+\varepsilon/3$, and the bound $2/e^2$ then needs $\varepsilon=T^{-1/4}\le3/16$. Small $T$ is covered by the first round, whose expected regret is $1/2$. The goal leaves $c$ existential.
• Theorem 4. The printed variance sum runs to $n$; it runs to $T$. The conditioning is on a general filtration, and square-integrability of the steps is assumed so that the conditional variance is defined.
• Lemma 15. Its right side depends on the round-$t$ cost $\ell_t$, which is not part of $\mathcal H_t$; the Lean statement holds for either value of $\ell_t$.

Welcome contributions: a Lean proof of Freedman's inequality (reusable across the bandit and concentration missions on the platform); the averaging argument from two-point priors to the uniform prior; and the stopped-martingale bookkeeping for the bias sequence.

Selected references

• Varsha Dani, Thomas P. Hayes, Sham M. Kakade, Stochastic Linear Optimization under Bandit Feedback, Proceedings of the 21st Annual Conference on Learning Theory (COLT), 2008.
• David A. Freedman, On tail probabilities for martingales, The Annals of Probability 3(1):100–118, 1975. https://doi.org/10.1214/aop/1176996452
• Colin McDiarmid, Concentration, in Probabilistic Methods for Algorithmic Discrete Mathematics, Springer, 1998. https://doi.org/10.1007/978-3-662-12788-9_6
• Peter Auer, Using confidence bounds for exploitation–exploration trade-offs, JMLR 3:397–422, 2002. https://www.jmlr.org/papers/v3/auer02a.html
• Paat Rusmevichientong, John N. Tsitsiklis, Linearly parameterized bandits, Mathematics of Operations Research 35(2):395–411, 2010. https://doi.org/10.1287/moor.1100.0446
• Tor Lattimore, Csaba Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Chapter 24. https://doi.org/10.1017/9781108571401

Motivation

The book has characterized learnability through uniform convergence and through stability; Chapter 30 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), gives a third sufficient condition, compression: if a learning algorithm's output can be reconstructed from a small subsequence of $k$ training examples, then the error on the remaining examples estimates the true error, and the algorithm generalizes with a bound of order $k\log(m/\delta)/m$ (Theorem 30.2, Littlestone and Warmuth). The bound is a union bound over the $m^k$ possible index sequences of a held-out estimate that follows from Bernstein's inequality (Lemma 30.1), and in the consistent case it gives $L_D \le 8k\log(m/\delta)/m$ (Corollary 30.3). Classes admitting such compression schemes include axis-aligned rectangles ($k = 2d$), homogeneous halfspaces ($k = d$, through the minimal-norm point of the convex hull and Carathéodory's theorem), separating polynomials by reduction, and any margin-separable data ($k \le 1/\gamma^2$, through the Perceptron). Whether every class of finite VC dimension has a compression scheme of size $O(d)$ is Warmuth's problem, open when the book was written.

Setting

A sample $S = (z_1, \dots, z_m)$ is drawn i.i.d. from $D$; a selection rule picks $(i_1, \dots, i_k) \in [m]^k$ (repetitions allowed), a reconstruction map $B : Z^k \to H$ produces $A(S) = B(z_{i_1}, \dots, z_{i_k})$, and $V$ is the set of positions not selected, with $L_V$ the average loss over them. The loss takes values in $[0,1]$. A class $H$ has a compression scheme of size $k$ (Definition 30.4) if for every $m \ge 1$ there are such $A$ and $B$ with $B(S_{A(S)})$ correct on every sample labeled by a member of $H$; the unrealizable version (Definition 30.5) asks $B(S_{A(S)})$ to be an empirical risk minimizer on every sample.

Formalization targets

Goal: Theorem 30.2

For a $[0,1]$-valued loss, $k \ge 1$, $m \ge 2k$, any reconstruction map $B$ and any selection rule, with probability at least $1 - \delta$ over $S \sim D^m$,

$$L_D(A(S)) \le L_V(A(S)) + \sqrt{L_V(A(S))\,\frac{4k\log(m/\delta)}{m}} + \frac{8k\log(m/\delta)}{m}.$$

Milestones

Lemma 30.1 (the held-out Bernstein bound); Corollary 30.3 (the consistent case); Lemma 30.6 (realizable schemes give unrealizable schemes); the compression scheme of size $2d$ for axis-aligned rectangles (§30.2.1); the separation property of the minimal-norm point of the convex hull (§30.2.2). Further items: the size-$d$ scheme for homogeneous halfspaces and the margin scheme of §30.2.4.

Significance

Compression bounds are the cleanest generalization argument in the book: no complexity measure of the class enters, only the number of examples needed to encode the output, and the resulting bound is data-dependent through $L_V$. They explain why support vector machines and the Perceptron generalize in terms of the number of support vectors or updates, and they underlie the sample-compression view of learning that connects to Chapters 9 and 15. Lemma 30.6 shows that compression is robust to label noise in the binary case. The halfspace scheme is a small piece of convex geometry of independent interest, and Warmuth's question about VC classes, settled in the affirmative for finite size by Moran and Yehudayoff after the book appeared, remains open in the form $O(d)$.

Difficulty

Lemma 30.1 is Bernstein's inequality for the $n$ held-out losses with variance at most $L_D(h_T)$, followed by solving the resulting quadratic in $\sqrt{L_D}$ to move the risk from the right-hand side to $L_V$; the constant $4$ comes out of that step (the exact value is about $3.19$). Theorem 30.2 is a union bound over the $m^k$ index sequences with $\delta' = m^k\delta$, using $|V| \ge m - k \ge m/2$ and $\log(m^k/\delta') \le k\log(m/\delta')$, which needs $k \ge 1$; formally the event for the learner is contained in the union of the events of Lemma 30.1 for each fixed index sequence, so no measurability of the selection rule is needed. Corollary 30.3 is immediate. Lemma 30.6 applies the realizable scheme to the subsample on which an ERM hypothesis is correct. The rectangle scheme is bookkeeping about extremal coordinates. The halfspace scheme needs three facts: the minimal-norm point of the hull separates (a one-line perturbation argument), it lies on a face and hence is a convex combination of $d$ sample points (Carathéodory's theorem, in Mathlib, applied to a face), and it is the minimal-norm point of the hull of those $d$ points (uniqueness of the projection onto a convex set); the existence of the minimizer uses compactness of the hull. The margin scheme is the Perceptron convergence theorem of Mission VI applied to the batch algorithm, whose output is the sum of the updated examples.

Formalization scope

Samples are Fin m-indexed under Mission I's iidLaw, and probability statements bound the outer measure of the failure event. Lemma 30.1 splits a sample of size $k + n$ into its first $k$ and last $n$ entries; Theorem 30.2 takes an arbitrary selection rule $\mathrm{sel} : Z^m \to [m]^k$ and reconstruction map $B$, the held-out set being the positions not in the range of the selection, and requires $k \ge 1$ and $m \ge 1$ in addition to the book's $m \ge 2k$: for $k = 0$ the bound reads $L_D \le L_V$, which fails, and the book's derivation uses $k \ge 1$ in $\log(m^k/\delta') \le k\log(m/\delta')$. Compression schemes are defined for every $m \ge 1$, since for $m = 0$ there is no index to select, with indices allowed to repeat as in $[m]^k$ and with $B$'s outputs in $H$; the unrealizable version uses Mission XXIII's multiclass 0–1 loss. The halfspace results are stated for strictly separable $\pm1$-labeled samples, $y_i\langle w^\star, x_i\rangle > 0$, the book's "w.l.o.g. all labels positive" normalization; this avoids the boundary negatives that a realizable sample may contain under the $\operatorname{sign}(0)$ convention of Mission VI, and it is the setting in which the minimal-norm argument works. The scheme is stated as the existence of $d$ indices whose signed examples have a minimal-norm hull point separating the whole sample, which is the content of $A$ and $B$ without fixing how ties among faces are broken. Rectangles are closed boxes. The margin scheme uses Theorem 9.1's normalization.

Not stated: §30.2.3 (polynomials, a reduction), the bibliographic remarks, and the intermediate Carathéodory step as a separate item.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 30. doi:10.1017/CBO9781107298019
• N. Littlestone, M. K. Warmuth, Relating data compression and learnability, technical report, University of California, Santa Cruz, 1986.
• S. Floyd, M. K. Warmuth, Sample compression, learnability, and the Vapnik-Chervonenkis dimension, Machine Learning 21, 1995. doi:10.1007/BF00993593
• S. Ben-David, A. Litman, Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes, Discrete Applied Mathematics 86, 1998. doi:10.1016/S0166-218X(98)00000-6
• S. Moran, A. Yehudayoff, Sample compression schemes for VC classes, Journal of the ACM 63(3), 2016. doi:10.1145/2890490

Motivation

Chapter 17 introduced multiclass prediction; Chapter 29 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), asks the two questions the fundamental theorem answered for binary classes: which classes of multiclass predictors are PAC learnable with respect to the 0–1 loss, and with what sample complexity. Natarajan's dimension generalizes the VC dimension by shattering with two disagreeing label functions, and the multiclass fundamental theorem (Theorem 29.3) bounds the uniform-convergence, agnostic and realizable sample complexities in terms of it, up to logarithmic factors in the number of labels $k$; the only new ingredient in its proof is Natarajan's lemma, the multiclass substitute for Sauer's lemma. The chapter then computes or bounds the Natarajan dimension of the classes that matter, One-versus-All and general reductions to binary classifiers, and linear multiclass predictors (Theorem 29.7). Its last section is a warning: unlike the binary case, not all ERMs are equal, and with infinitely many labels a class can be learnable by one ERM and not by another, so learnability and uniform convergence come apart (Claim 29.9).

Setting

$H$ is a class of functions from $X$ to a finite label set $Y$ with $|Y| = k$. $C \subseteq X$ is shattered by $H$ if there are $f_0, f_1 : C \to Y$ with $f_0(x) \ne f_1(x)$ everywhere on $C$ such that every $B \subseteq C$ is realized by some $h \in H$ agreeing with $f_0$ on $B$ and with $f_1$ on $C \setminus B$ (Definition 29.1); $\operatorname{Ndim}(H)$ is the largest size of a shattered set (Definition 29.2). One-versus-All builds $T(\bar h)(x) = \operatorname{argmax}_i h_i(x)$ from $k$ binary classifiers, the smaller label on ties; a general reduction applies a rule $r : \{0,1\}^l \to [k]$ to $l$ binary classifiers; the linear class $H_\Psi$ predicts $\operatorname{argmax}_i\langle w, \Psi(x, i)\rangle$ for a class-sensitive feature map $\Psi : X \times [k] \to \mathbb{R}^d$ (29.1). The class of §29.4 has labels $P_f(X) \cup \{\ast\}$, the finite and cofinite subsets of $X$ plus a special label, and hypotheses $h_A(x) = A$ if $x \in A$ and $\ast$ otherwise; $A_{good}$ returns $h_\emptyset$ on an all-$\ast$ sample and $A_{bad}$ returns $h_{\{x_1, \dots, x_m\}^c}$.

Formalization targets

Goal: Theorem 29.3

There are absolute constants $C_1, C_2 > 0$ such that every class $H \subseteq Y^X$ with $\operatorname{Ndim}(H) = d$ satisfies

$$C_1\frac{d + \log(1/\delta)}{\epsilon^2} \le m^{UC}_H(\epsilon,\delta),\ m_H(\epsilon,\delta) \le C_2\frac{d\log k + \log(1/\delta)}{\epsilon^2}, \qquad C_1\frac{d + \log(1/\delta)}{\epsilon} \le m^{\mathrm{real}}_H(\epsilon,\delta) \le C_2\frac{d\log(kd/\epsilon) + \log(1/\delta)}{\epsilon},$$

the upper bounds by every ERM learner and the lower bounds for small $\epsilon, \delta$ and $d \ge 2$, in the format of Mission IV's Theorem 6.8.

Milestones

Lemma 29.4 (Natarajan: $|H| \le |X|^{\operatorname{Ndim}(H)}k^{2\operatorname{Ndim}(H)}$); Lemma 29.5 (the Natarajan dimension of One-versus-All is $O(kd\log(kd))$); Theorem 29.7 ($\operatorname{Ndim}(H_\Psi) \le d$); Claim 29.9(1) ($A_{good}$ needs $\frac1\epsilon\log\frac1\delta$ examples); Claim 29.9(2) ($A_{bad}$ fails with constant probability on $(|X|-1)/(6\epsilon)$ examples). Further items: the equality $\operatorname{Ndim} = \operatorname{VCdim}$ for two classes, and Lemma 29.6 for general reductions.

Significance

Theorem 29.3 is the multiclass fundamental theorem of Natarajan (1989) and Ben-David, Cesa-Bianchi, Haussler and Long (1995): finite Natarajan dimension characterizes multiclass learnability, and the sample complexity is linear in it, with the dependence on $k$ confined to logarithms. Natarajan's lemma is the combinatorial core, and the dimension bounds of §29.3 are what make the theorem usable: a One-versus-All scheme over a class of VC dimension $d$ costs $\tilde O(kd)$, and a linear multiclass predictor costs at most its number of parameters, so the multivector construction of Chapter 17 is learnable with $\tilde O(nk/\epsilon^2)$ examples. Claim 29.9 is a genuine phenomenon of Daniely, Sabato, Ben-David and Shalev-Shwartz (2011): in multiclass classification the choice of ERM matters, and the equivalence "learnable iff uniform convergence" of the binary theory is false, which is why Conjecture 29.10 about good ERMs is open in the form the chapter states it.

Difficulty

The equality with the VC dimension for two labels is a direct comparison of the two shattering definitions. Natarajan's lemma is a Sauer-type induction on $|X|$, in which a shattered set must be produced from two hypotheses that differ at a point; the exercise-level proof of the book becomes a careful double induction formally. Theorem 29.3's upper bounds follow the binary proof of Chapter 28 with Natarajan's lemma in place of Sauer's, hence Massart's lemma and Theorem 26.5 for the agnostic case and the double-sample argument for the realizable case; the lower bounds reduce to the binary ones by embedding a binary class into a multiclass one on a shattered set. These are long formal developments, and the theorem is stated with unspecified constants for that reason. Lemmas 29.5 and 29.6 are counting: a shattered $C$ has $2^{|C|} \le |H_C| \le |(H_{bin})_C|^k$, Sauer's lemma bounds the right side by $\big(\sum_{i \le d}\binom{|C|}{i}\big)^{k}$, and the resulting inequality is solved. For Lemma 29.5's printed $3kd\log(kd)$ this fails only at $(k, d) = (2, 1), (3, 1)$. There a shattered set splits by the label pair $\{f_0(x), f_1(x)\}$ into parts shattered by $\{B \setminus A : A, B \in H_{bin}\}$ (pairs $\{0, b\}$) or by $H_{bin}$ (other pairs). The first class has at most $31$ traces on $5$ points. Theorem 29.7 maps a shattered set into $\mathbb{R}^d$ by $\rho(x) = \Psi(x, f_0(x)) - \Psi(x, f_1(x))$, up to sign, and shows the image is shattered by homogeneous halfspaces; the tie-breaking rule decides which sign and which halfspace convention to use. Claim 29.9(1) is the bound $(1-\epsilon)^m \le \delta$; Claim 29.9(2) needs only that at most $(d-1)/2$ of the $d-1$ light points appear in the sample, an event of probability at least $1/3$ by Markov's inequality when $m \le (d-1)/(6\epsilon)$, which exceeds the claimed $e^{-1}/6$.

Formalization scope

Labels are an arbitrary finite type, shattering and the Natarajan dimension are stated with witnesses $f_0, f_1$ defined on all of $X$, and the dimension is a supremum in $\mathbb{N} \cup \{\infty\}$. The multiclass 0–1 loss, the ERM property, agnostic PAC learnability and uniform convergence are Mission I's generic notions; the realizable multiclass PAC property is defined here in the shape of Definition 3.1 with $D(\{h \ne f\})$ as the error, since Mission I's binary version is $\{0,1\}$-specific. Theorem 29.3 is stated exactly as Mission IV states Theorem 6.8, with existential constants, upper bounds for every ERM learner of a nonempty measurable class with the countable-approximation property (the measurability device of Remark 3.1), and lower bounds for $\epsilon < \epsilon_0$, $\delta < \delta_0$, $d \ge 2$. Argmax predictors, both One-versus-All and $H_\Psi$, break ties towards the smallest label; the book states this rule for One-versus-All, and some fixed rule is necessary for Theorem 29.7, since with arbitrary tie-breaking every function is an argmax predictor of the zero mapping. Lemmas 29.5 and 29.6 are stated per shattered set. Lemma 29.5 keeps the printed $3kd\log(kd)$, which is true although the book's step $|(H_{bin})_C| \le |C|^d$ fails for small $|C|$. Lemma 29.6 uses $2ld\log_2(2ld)$, which the counting supports, because the printed $3ld\log(ld)$ is false at $l = d = 1$. Theorem 29.3's uniform-convergence upper bound is stated for $d \ge 1$. At $d = 0$ the confidence term $\log(1/\delta)$ vanishes as $\delta \to 1$, the bound reaches $m = 1$, and a single example is not representative. The class of §29.4 has labels Option of the subtype of finite-or-cofinite sets, with the discrete σ-algebra, and the two ERMs are predicates fixing the output on all-$\ast$ samples; Claim 29.9(1) is stated for countable $X$ with measurable singletons and Claim 29.9(2) for finite $X$ of size at least $2$, with the proof's own distribution, $h_\emptyset$ as target, and every $\epsilon \in (0, 1/2)$ in place of the book's unspecified constant $a$.

Not stated: Corollary 29.8 (its lower bound $(k-1)(n-1)$ is cited, not proved), Conjecture 29.10, the exercises.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 29. doi:10.1017/CBO9781107298019
• B. K. Natarajan, On learning sets and functions, Machine Learning 4, 1989. doi:10.1007/BF00114804
• S. Ben-David, N. Cesa-Bianchi, D. Haussler, P. M. Long, Characterizations of learnability for classes of {0, …, n}-valued functions, Journal of Computer and System Sciences 50(1), 1995. doi:10.1006/jcss.1995.1008
• D. Haussler, P. M. Long, A generalization of Sauer's lemma, Journal of Combinatorial Theory A 71(2), 1995. doi:10.1016/0097-3165(95)90001-2
• A. Daniely, S. Sabato, S. Ben-David, S. Shalev-Shwartz, Multiclass learnability and the ERM principle, COLT 2011; Journal of Machine Learning Research 16, 2015.
• A. Daniely, S. Sabato, S. Shalev-Shwartz, Multiclass learning approaches: a theoretical comparison with implications, NIPS 2012.

Motivation

Chapter 6 stated the fundamental theorem of statistical learning: a binary class is learnable if and only if its VC dimension is finite, with sample complexity $\Theta((d + \ln(1/\delta))/\epsilon^2)$ in the agnostic case and $\Theta((d\ln(1/\epsilon) + \ln(1/\delta))/\epsilon)$ in the realizable case. Chapter 28 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), proves it. The agnostic upper bound is obtained from the Rademacher machinery of Chapter 26 with Sauer's lemma and Massart's lemma, up to a $\log(d/\epsilon)$ factor that only chaining removes (28.1). The agnostic lower bound comes in two parts: a two-point construction giving $m \ge 0.5\log(1/(4\delta))/\epsilon^2$, and a $d$-point construction giving $m \ge d/(512\epsilon^2)$ at confidence $1/8$, whose heart is Lemma 28.1, the optimality of the Maximum-Likelihood rule against the family of noisy distributions $D_b$. The realizable upper bound is proved through $\epsilon$-nets: with $m \ge \frac8\epsilon(2d\log(16e/\epsilon) + \log(2/\delta))$ examples a random sample hits every set of measure at least $\epsilon$ in the class (Theorem 28.3), so any hypothesis consistent with the sample has error below $\epsilon$. Mission IV states these bounds with unnamed constants; this mission gives the chapter's explicit ones.

Setting

$H$ is a class of functions $X \to \{0,1\}$ with the 0–1 loss and $\operatorname{VCdim}(H) = d$. For the upper bound, $A = \{(\mathbb{1}[h(x_i) \ne y_i])_i : h \in H\}$ is the loss set of a sample and $R(A)$ its Rademacher complexity. For the lower bounds, $C = \{c_1, \dots, c_d\}$ is a set shattered by $H$ and, for $b \in \{\pm1\}^d$ and $\rho \in (0,1)$, $D_b$ draws $c_i$ uniformly and labels it $b_i$ with probability $(1+\rho)/2$; for $d = 1$ these are the distributions $D_\pm$ of §28.2.1. The Maximum-Likelihood rule $A_{ML}$ predicts at each $c_i$ the majority of the labels seen at $c_i$. An $\epsilon$-net for $H$ with respect to $D$ is a sample meeting every $h \in H$ with $D(h) \ge \epsilon$ (Definition 28.2).

Formalization targets

Goal: Theorem 28.3

Let $\operatorname{VCdim}(H) = d$, $\epsilon \in (0,1)$, $\delta \in (0, 1/4)$ and $m \ge \frac8\epsilon\big(2d\log\frac{16e}{\epsilon} + \log\frac2\delta\big)$. Then with probability at least $1 - \delta$ over $S \sim D^m$, $S$ is an $\epsilon$-net for $H$.

Milestones

The two-sided deviation bound of §28.1 ($|L_D(h) - L_S(h)| \le 2\sqrt{(8d\log(em/d) + 2\log(4/\delta))/m}$ uniformly over $H$); the lower bound $m(\epsilon,\delta) \ge 0.5\log(1/(4\delta))/\epsilon^2$ of §28.2.1; Lemma 28.1; the lower bound $m(\epsilon, 1/8) \ge d/(512\epsilon^2)$ of §28.2.2; the realizable upper bound of §28.3 (ERM has error at most $\epsilon$ with probability $1 - \delta$ for the sample size of Theorem 28.3). Further items: the Rademacher bound $R(A) \le \sqrt{2d\log(em/d)/m}$, the explicit uniform-convergence sample complexity of §28.1, and the expectation lower bound $\rho/4$ of §28.2.2.

Significance

These are the theorems that make the VC dimension the right measure of learnability, with constants. The upper bounds show what the abstract machinery of Missions II, IV, XX buys when instantiated: Sauer plus Massart plus Theorem 26.5 gives the agnostic rate, and the double-sample symmetrization plus Sauer gives the realizable rate, sharper by a factor $1/\epsilon$ because $\epsilon$-nets need only one-sided control. The lower bounds are the No-Free-Lunch argument refined to quantify $\epsilon$ and $\delta$: the two-point distribution shows that confidence costs $\log(1/\delta)/\epsilon^2$, and the $d$-point family with Lemma 28.1 shows that the dimension costs $d/\epsilon^2$, through the exact optimality of majority voting and a binomial anti-concentration bound. Theorem 28.3 is also the basic $\epsilon$-net theorem of Haussler and Welzl, a result of independent importance in computational geometry.

Difficulty

The Rademacher bound is Sauer's lemma (Mission IV) plus Massart's lemma (Mission XX) with $\|a - \bar a\| \le \sqrt m$; the deviation bound is Theorem 26.5 applied to $\ell$ and $-\ell$ with a union bound; the explicit sample complexity is Lemma A.2, $x \ge 4a\log(2a) + 2b \Rightarrow x \ge a\log x + b$, which a formal proof must establish (the tangent inequality for $\log$ at $2a$). The two-point lower bound requires the binomial lower-tail estimate of Lemma B.11 and the algebra $\frac12(1 - \sqrt{1 - \sqrt{4\delta}}) \ge \delta$, valid for $\delta < 1/4$, the only nonvacuous range. Lemma 28.1 is a conditioning argument: fixing the instance indices and the labels off $c_i$, the contribution of $c_i$ is minimized by predicting the more likely $b_i$ given the labels at $c_i$, which is the majority; the formal proof must decompose the product measure $D_b^m$ over the positions $r$ with $x_r = c_i$. The expectation bound $\rho/4$ then needs Lemma B.11 again, $1 - e^{-a} \le a$, Jensen for $\sqrt{\cdot}$ and $\mathbb{E}[n_i] = m/d$, and the probability bound $1/8$ follows by Mission III's reverse Markov inequality with $\rho = 8\epsilon$. Theorem 28.3 is the double-sample argument: Claim 1 ($P[S \in B] \le 2P[(S,T) \in B']$, via a Chernoff bound that only needs $m\epsilon \ge 2\log 2$), Claim 2 (symmetrization by a random half, $P[(S,T) \in B'] \le e^{-\epsilon m/4}\tau_H(2m)$), Sauer's lemma, and Lemma A.2 once more. The realizable upper bound applies Theorem 28.3 to the error sets $\{x : h(x) \ne f(x)\}$, a class of the same VC dimension.

Formalization scope

All objects are those of the earlier missions: risks, samples and learners from Mission I, vcDim and the countable-approximation property PointwiseSeparable from Mission IV (the measurability device for suprema over $H$, used wherever a symmetrization or Rademacher argument is invoked), condLaw from Mission XIV for the distributions $D_b$, and rademacher, evalSet, lossClass from Mission XX. Probability statements bound the outer measure of the failure event under iidLaw. The Rademacher and deviation items require $m > d + 1$, the range in which Mission IV states Sauer's lemma in the form $(em/d)^d$; the explicit sample complexity of §28.1 implies this range, since its first term $432d\log(64d/\epsilon^2)/\epsilon^2$ dominates the possibly negative $8d\log(e/d)$, and Lemma A.2 holds for any real $b$, so the book's constants are used verbatim. The lower bounds take a shattered set as an injective $c : \mathrm{Fin}\ d \to X$ with the shattering property written out, use $D_b$ as condLaw of the uniform law on $C$, and state the excess risk against $\min_{h \in H}L_{D_b}(h)$ as $\exists h \in H$ with $L(h) + \epsilon \le L(A(S))$, or as a real infimum over $H$ in the expectation item; no measurability of the learner is needed because $D_b^m$ is atomic. Lemma 28.1 compares the sums over $b$ of the expected risks, the common term $\min_h L_{D_b}$ cancelling, for every majority rule with arbitrary tie-breaking. Theorem 28.3 and the realizable bound are stated for $\delta \in (0, 1/4)$, the theorem's own range; the realizable bound is the inner clause of Mission I's IsPACWith on that range rather than a sample-complexity function, since the theorem does not cover $\delta \ge 1/4$ with its formula.

Not stated: the realizable lower bound (an exercise), the remark that chaining removes the logarithm in (28.1), and the intermediate claims of the proof of Theorem 28.3 as separate items.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 28. doi:10.1017/CBO9781107298019
• 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
• A. Blumer, A. Ehrenfeucht, D. Haussler, M. K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM 36(4), 1989. doi:10.1145/76359.76371
• D. Haussler, E. Welzl, ε-nets and simplex range queries, Discrete and Computational Geometry 2, 1987. doi:10.1007/BF02187876
• M. Anthony, P. L. Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press, 1999. doi:10.1017/CBO9780511624216

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