Statistics

Markov chain Monte Carlo turns hard integration problems into long simulations: to estimate an expectation $E_\pi f$ one runs a Markov chain with stationary distribution $\pi$ and reports the sample average $\bar f_n$. The ergodic theorem guarantees $\bar f_n \to E_\pi f$, but honest error bars require more: a central limit theorem

On general state spaces this is famously delicate - a merely ergodic chain with a square-integrable functional can fail the CLT, so the classical theory trades convergence rates (drift, minorization, geometric or polynomial total-variation rates) and mixing conditions ($\alpha$-, $\rho$-, $\varphi$-mixing) against moment conditions on $f$. This mission formalizes G. L. Jones's survey "On the Markov chain central limit theorem" (Probability Surveys, 2004): the drift-condition CLTs of Meyn-Tweedie and Jarner-Roberts, the classical mixing CLTs of Ibragimov-Linnik, Doukhan-Massart-Rio and Billingsley, the characterizations via uniform integrability and boundedness in probability, and their assembly into the summary theorem: six practically checkable regimes - from polynomial ergodicity with bounded functionals to uniform ergodicity with second moments - each of which guarantees the CLT for every initial distribution. The stationarity, total-variation and mixing infrastructure is general state space and reusable well beyond this mission.

Every time a streaming service guesses what you would rate a film you have never seen, it is solving a matrix completion problem: fill in the missing entries of a vast user-by-item table from the few that are observed. The question became famous during the Netflix Prize (2006-2009), and it looks hopeless - infinitely many matrices fit the observed entries - until one assumes the structure that makes recommendation possible: the table is essentially low rank, because tastes are governed by a few latent factors. In their landmark 2009 paper 'Exact Matrix Completion via Convex Optimization' (Foundations of Computational Mathematics), Emmanuel Candes and Benjamin Recht proved that an n-by-n matrix of rank r can be recovered exactly, with high probability, from only about n^1.2 * r * log n randomly observed entries - not by the NP-hard route of minimizing rank, but by minimizing the nuclear norm, a convex surrogate (the sum of the singular values) solvable efficiently. The proof, in the lineage of Candes-Romberg-Tao compressed sensing, turns on two ideas: an incoherence condition ensuring the singular vectors are spread out rather than spiky, and a dual certificate witnessing optimality, whose existence rests on delicate random-matrix concentration. It transformed a practical engineering puzzle into rigorous theory and seeded a decade of work across machine learning, signal processing, computer vision, and sensor localization. This mission formalizes the Candes-Recht exact-recovery theorem in Lean, decomposed into its dual-certificate construction and the probabilistic concentration reductions at its core.

Motivation

In best arm identification with fixed confidence, a learner samples $K$ unknown distributions (arms) sequentially and must, as early as possible, name the arm with the largest mean, while being wrong with probability at most a prescribed risk $\delta$. The problem models adaptive A/B/n testing, clinical and simulation-based selection among alternatives, and the "ranking and selection" problem of operations research and simulation optimization. The quantity of interest is the sample complexity $\mathbb E_{\boldsymbol\mu}[\tau_\delta]$, the expected number of samples a strategy takes before stopping.

Timeline of the question this mission formalizes:

• Chernoff (1959) introduced sequential tests based on generalized likelihood ratios for adaptive design of experiments, with a finite set of hypotheses (doi:10.1214/aoms/1177706205).
• Kaufmann, Cappé and Garivier (2016, JMLR) proved a change-of-measure lower bound on the sample complexity of every $\delta$-PAC strategy (arXiv:1407.4443).
• Garivier and Kaufmann (COLT 2016) identified the exact constant $T^*(\boldsymbol\mu)$ in that lower bound and gave the first strategy, Track-and-Stop, whose sample complexity matches it asymptotically as $\delta\to0$ (arXiv:1602.04589). This mission covers the upper-bound half of that paper.

Setting

A canonical one-parameter exponential family is a family of laws $\nu_\theta$, $\theta\in\Theta$, on $\mathbb R$ with density $\exp(\theta x-b(\theta))$ with respect to a reference measure $\xi$; $b$ is twice differentiable and strictly convex, and $\nu_\theta$ has mean $\dot b(\theta)$. Bernoulli, Poisson and Gaussian laws with known variance are examples. The divergence $d(\mu,\mu')$ is the Kullback–Leibler divergence between the members with means $\mu$ and $\mu'$.

A bandit model $\boldsymbol\mu=(\mu_1,\dots,\mu_K)$ assigns a member of the family to each arm. The class $\mathcal S$ consists of models with a unique optimal arm $a^*(\boldsymbol\mu)$. At each round $t=1,2,\dots$ the learner picks an arm $A_t$ as a function of past observations, observes a reward drawn from that arm's law, and at a stopping time $\tau_\delta$ recommends an arm. $N_a(t)$ is the number of draws of arm $a$ in the first $t$ rounds and $\hat\mu_a(t)$ its empirical mean.

With $\mathrm{Alt}(\boldsymbol\mu)=\{\boldsymbol\lambda\in\mathcal S: a^*(\boldsymbol\lambda)\ne a^*(\boldsymbol\mu)\}$ and $\Sigma_K$ the probability simplex, the characteristic time is

and the maximizer $w^*(\boldsymbol\mu)$ are the optimal proportions of arm draws.

Track-and-Stop combines two ingredients:

• a sampling rule that tracks the plug-in proportions $w^*(\hat{\boldsymbol\mu}(t))$ while forcing each arm to be drawn about $\sqrt t$ times: C-Tracking tracks the cumulated sum of projections of $w^*(\hat{\boldsymbol\mu}(s))$ onto $\Sigma^{\epsilon_s}_K=\{w\in\Sigma_K: w_a\ge\epsilon_s\}$, $\epsilon_s=(K^2+s)^{-1/2}/2$; D-Tracking draws an under-sampled arm when some $N_a(t)<\sqrt t-K/2$, and otherwise the arm maximizing $t\,w^*_a(\hat{\boldsymbol\mu}(t))-N_a(t)$;
• Chernoff's stopping rule, which stops at the first $t$ at which some arm $a$ beats every other arm $b$ in a generalized likelihood ratio test, $Z_{a,b}(t)>\beta(t,\delta)$, here with $\beta(t,\delta)=\log(r(t)/\delta)$.

Formalization targets

Goal: Theorem 14 (p. 13)

For $\alpha\in[1,e/2]$ and $r(t)=O(t^\alpha)$, Chernoff's stopping rule with $\beta(t,\delta)=\log(r(t)/\delta)$ combined with C-Tracking or D-Tracking satisfies

for every $\boldsymbol\mu\in\mathcal S$.

Milestones

• Lemma 15 (p. 20): greedy tracking of cumulated proportions $P(k)$ keeps $\max_i|N_i(n)-P_i(n)|\le K-1$.
• Lemma 7 (p. 7): C-Tracking ensures $N_a(t)\ge\sqrt{t+K^2}-2K$ and $\max_a|N_a(t)-\sum_{s<t}w^*_a(\hat{\boldsymbol\mu}(s))|\le K(1+\sqrt t)$.
• Lemma 8 (p. 7): D-Tracking ensures $N_a(t)\ge(\sqrt t-K/2)_+-1$, and proportions within $3(K-1)\epsilon$ of $w^*(\boldsymbol\mu)$ after a time $t_\epsilon$ that does not depend on the trajectory, once the plug-in targets are within $\epsilon$.
• Proposition 9 (p. 8): under either rule, $N_a(t)/t\to w^*_a(\boldsymbol\mu)$ almost surely.
• Lemma 18 (p. 27): an explicit $x$ with $c_1x\ge\log(c_2x^\alpha)$ for $\alpha\in[1,e/2]$.
• Proposition 13 (p. 11): with any sampling rule whose proportions converge almost surely to $w^*$, $\tau_\delta<\infty$ almost surely and $\limsup_{\delta\to0}\tau_\delta/\log(1/\delta)\le\alpha T^*(\boldsymbol\mu)$ almost surely.

Significance

Theorem 1 of the same paper shows $\mathbb E_{\boldsymbol\mu}[\tau_\delta]\ge T^*(\boldsymbol\mu)\,\mathrm{kl}(\delta,1-\delta)$ for every $\delta$-PAC strategy, and $\mathrm{kl}(\delta,1-\delta)\sim\log(1/\delta)$. Theorem 14 with $\alpha=1$ therefore shows that the lower bound is attained: $T^*(\boldsymbol\mu)$ is the exact asymptotic sample complexity of best arm identification in exponential family models, and Track-and-Stop is asymptotically optimal.

The result is proved in the paper. What is not available is a machine-checked proof for exponential families. The platform already holds a Lean development of the Gaussian case following Lattimore and Szepesvári, Bandit Algorithms, Ch. 33, stated for one existentially chosen policy with a different threshold. This mission asks for the universal statement: every run of either tracking rule, for every exponential family, with the paper's thresholds. The tracking lemmas (Lemmas 15, 7, 8) are deterministic combinatorics and reusable by any tracking-based algorithm.

Difficulty

The obvious argument plugs the almost-sure behaviour of Proposition 13 into an expectation. That step fails: almost-sure convergence of $\tau_\delta/\log(1/\delta)$ does not control $\mathbb E[\tau_\delta]$, because on the rare events where the empirical means are far from $\boldsymbol\mu$ the stopping time may be very large. Theorem 14 needs a quantitative concentration of $\hat{\boldsymbol\mu}(t)$ on events whose complements have summable probability, which in turn relies on the forced exploration guaranteed by the $\sqrt t$ lower bounds on $N_a(t)$ (the concentration step of App. D, Lemmas 19–20).

A second obstacle is the regularity of $w^*$: the tracking lemmas only transfer convergence of $\hat{\boldsymbol\mu}(t)$ to convergence of $N_a(t)/t$ through the continuity of $\boldsymbol\mu\mapsto w^*(\boldsymbol\mu)$ on $\mathcal S$, proved from the characterization of $w^*$ in §2.2 (Proposition 6). The GLR statistic also needs its closed form (7) near $\boldsymbol\mu$, which requires the empirical means to lie in the interior of the mean space.

Formalization scope

• Model. The exponential family is a structure $(\xi,\Theta,b)$ with $\Theta$ a nonempty open interval, each $\nu_\theta$ normalized, $b$ twice continuously differentiable and $\ddot b>0$ on $\Theta$. Openness and $\ddot b>0$ are added to the paper's "convex, twice differentiable"; strict convexity is what makes $\nu^\mu$ unique. Bandit models are parameter vectors $\theta\in\Theta^K$ with $K\ge2$; arms are indexed $0,\dots,K-1$. $\mathcal S$ is the set of parameter vectors with a unique arm of largest mean $\dot b(\theta_a)$.
• Protocol. Policies, the trajectory law $\mathbb P_{\boldsymbol\mu}$, pull counts, empirical means and $T^*(\boldsymbol\mu)$ are the platform's published definitions (BanditPolicy, BanditTrajectory, TrackAndStop). $T^*$ uses Kullback–Leibler divergences of the arm laws over the class $\mathcal S$ and takes values in $[0,\infty]$. Trajectory coordinate $t$ is round $t+1$. An arm never drawn has empirical mean $0$.
• Target map. $w^*(\hat{\boldsymbol\mu}(t))$ is undefined in the paper when $\hat{\boldsymbol\mu}(t)\notin\mathcal S$ (an unsampled arm, ties, a mean outside $\dot b(\Theta)$). Every tracking statement quantifies over every target map with values in $\Sigma_K$ that returns optimal proportions on $\mathcal S$, over every choice of $L^\infty$ projections, and over every tie-breaking, including randomized ones.
• Stopping rule. The two maxima in $Z_{a,b}(t)$ are suprema over $\Theta$ in the extended reals. $Z_{a,b}(t)>\beta$ is written without subtracting infinities. The stopping time is the first $t\ge1$ at which the test succeeds, $+\infty$ if none. "$r(t)=O(t^\alpha)$" is $r(t)\le Dt^\alpha$ for $t\ge1$; $r>0$ is added so that $\log(r(t)/\delta)$ is defined.
• Values in $[0,\infty]$. Expectations of $\tau_\delta$, the ratios and $T^*$ live in $[0,\infty]$. No statement converts them to reals, so an infinite expected stopping time is never read as $0$.
• Corrections, disclosed. Proposition 9's printed $\mathbb P_w$ is $\mathbb P_{\boldsymbol\mu}$. Lemma 18 adds $c_2/c_1^\alpha>1$ and $x>0$, without which its expressions are undefined.
• Ruled out. Specializing to Gaussian arms, or asserting that some sampling policy achieves the bound, would restate existing platform results and is not this theorem: the goal is about every C-Tracking or D-Tracking run in every exponential family.
• Welcome contributions. Exponential-family facts ($\dot b$ is the mean, the KL formula, concentration of empirical means); the continuity of $w^*$ (Proposition 6, App. A.3); Lemma 17 (App. B.2), from which Lemma 8 follows; the closed form (7) of the GLR statistic.

Selected references

• A. Garivier, E. Kaufmann, Optimal Best Arm Identification with Fixed Confidence, COLT 2016, JMLR W&CP 49. arXiv:1602.04589v2
• E. Kaufmann, O. Cappé, A. Garivier, On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models, JMLR 17, 2016. arXiv:1407.4443
• H. Chernoff, Sequential Design of Experiments, Ann. Math. Statist. 30(3), 1959. doi:10.1214/aoms/1177706205
• T. Lattimore, C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Ch. 33. doi:10.1017/9781108571401

Motivation

Best arm identification with fixed confidence is the pure-exploration counterpart of the multi-armed bandit problem. A learner faces $K$ unknown reward distributions ("arms"), samples them sequentially, and must stop and name the arm with the largest mean, being wrong with probability at most a prescribed $\delta$. The question is how many samples this requires. It arises in adaptive A/B testing, in the selection of the best of several simulated systems (ranking and selection in simulation optimization), and in clinical trials that must declare the best treatment with a guaranteed error rate.

Lower bounds for this problem were first stated in terms of the gaps between means (Mannor and Tsitsiklis, 2004). Kaufmann, Cappé and Garivier (2016) replaced ad hoc changes of measure by a single "transportation" lemma relating expected sample counts, Kullback–Leibler divergences and the error probability. Garivier and Kaufmann (COLT 2016, arXiv:1602.04589v2) combine this lemma over all alternative models at once, in the spirit of Graves and Lai (1997), and obtain a lower bound whose constant $T^*(\boldsymbol\mu)$ is exactly matched, as $\delta \to 0$, by their Track-and-Stop strategy. This mission formalizes that lower bound (Theorem 1 of the paper, p. 3).

Setting

A canonical one-parameter exponential family is given by a reference measure $\xi$ on $\mathbb R$, an open interval $\Theta \subset \mathbb R$ and a function $b$, twice continuously differentiable on $\Theta$ with $\ddot b > 0$, such that the laws $\nu_\theta$ with density $\exp(\theta x - b(\theta))$ with respect to $\xi$ are probability measures for $\theta \in \Theta$. The mean of $\nu_\theta$ is $\dot b(\theta)$. Bernoulli laws and Gaussian laws of known variance are examples.

A bandit model is a vector $\theta = (\theta_1, \dots, \theta_K) \in \Theta^K$; arm $a$ returns i.i.d. rewards with law $\nu_{\theta_a}$ and mean $\mu_a = \dot b(\theta_a)$. Arm $a^*(\boldsymbol\mu)$ is the unique optimal arm if $\mu_{a^*} > \mu_a$ for every $a \ne a^*$. Let $\mathcal S$ be any set of bandit models of the family each having a unique optimal arm, and put $\mathrm{Alt}(\boldsymbol\mu) = \{\boldsymbol\lambda \in \mathcal S : a^*(\boldsymbol\lambda) \ne a^*(\boldsymbol\mu)\}$.

A strategy consists of a sampling rule $\pi$ (the arm $A_t$ drawn at round $t$ depends, possibly with extra randomization, on the first $t - 1$ observations), a stopping time $\tau$ of the natural filtration $\mathcal F_t = \sigma(A_1, X_1, \dots, A_t, X_t)$, and an $\mathcal F_\tau$-measurable decision $\hat a_\tau$. It is $\delta$-PAC on $\mathcal S$ if for every $\boldsymbol\mu \in \mathcal S$, $\mathbb P_{\boldsymbol\mu}(\tau < \infty) = 1$ and $\mathbb P_{\boldsymbol\mu}(\hat a_\tau \ne a^*(\boldsymbol\mu)) \le \delta$. $N_a(t)$ is the number of draws of arm $a$ among the first $t$ rounds.

Write $d(\mu_a, \lambda_a) = \mathrm{KL}(\nu_{\theta_a}, \nu_{\lambda_a})$ for the divergence between two arm laws, $\mathrm{kl}(x, y) = x\log\frac{x}{y} + (1 - x)\log\frac{1 - x}{1 - y}$, and $\Sigma_K$ for the probability simplex on the $K$ arms. The characteristic time is defined by eq. (1):

Formalization targets

Goal: Theorem 1 (p. 3)

For $\delta \in (0, 1/2]$, every $\delta$-PAC strategy on $\mathcal S$ and every $\boldsymbol\mu \in \mathcal S$,

The statement fixes no constant beyond those of the paper, and it holds for every $\delta$, not only in the limit.

Milestone: eq. (2) (p. 4)

For every $\boldsymbol\lambda \in \mathcal S$ with $a^*(\boldsymbol\lambda) \ne a^*(\boldsymbol\mu)$,

This is Lemma 1 of Kaufmann et al. (2016), which the paper quotes without proof; Theorem 1 follows from it for every alternative simultaneously.

Significance

Theorem 1 identifies $T^*(\boldsymbol\mu)$ as the exact problem-dependent complexity of fixed-confidence best arm identification: since $\mathrm{kl}(\delta, 1 - \delta) \sim \log(1/\delta)$, it gives $\liminf_{\delta \to 0} \mathbb E_{\boldsymbol\mu}[\tau_\delta]/\log(1/\delta) \ge T^*(\boldsymbol\mu)$, and the paper's Track-and-Stop strategy attains this rate (the subject of mission IV of this series). The bound also explains which proportions of draws an optimal strategy must use: the maximizer $w^*(\boldsymbol\mu)$ of eq. (1) (mission II).

Both results are proved in the literature. Neither is formalized in the paper's generality. The platform holds the textbook form of Lattimore and Szepesvári (Theorem 33.5), which is stated for an arbitrary class with the weaker constant $\log(1/(4\delta))$; for $\delta \le 1/2$, $\mathrm{kl}(\delta, 1 - \delta) \ge \log(1/(2.4\delta)) > \log(1/(4\delta))$, so Theorem 1 is strictly stronger. A formal proof here yields the transportation lemma for exponential families on the platform's infinite-horizon bandit model, which later missions (II–IV, and any lower bound by change of measure) can reuse.

Difficulty

The obvious proof applies the finite-horizon divergence decomposition $\mathrm{KL}(\mathbb P^n_{\boldsymbol\mu}, \mathbb P^n_{\boldsymbol\lambda}) = \sum_a \mathbb E_{\boldsymbol\mu}[N_a(n)]\,d(\mu_a, \lambda_a)$ at a deterministic horizon $n$. That fails here: $\tau$ is random and unbounded, the decision is $\mathcal F_\tau$-measurable, and the relevant divergence is between the laws of the stopped observations. The step from a fixed horizon to a stopping time, together with the data-processing inequality that turns the error guarantees under two models into $\mathrm{kl}(\delta, 1 - \delta)$, is the central difficulty. A second, smaller difficulty is to identify the paper's divergence $d$ and its means $\dot b(\theta)$ with the measure-theoretic KL divergence and mean of the arm laws of the exponential family.

Formalization scope

Lean namespace OptimalBAI.LowerBound. The bandit protocol is the platform's (BanditAlgorithm.BanditPolicy, banditTrajMeasure, IsBanditStoppingTime, IsSoundBAI, baiComplexity); $\mathrm{kl}$ is the platform's bernoulliRelativeEntropy and $N_a(t)$ is trajPullCount. Conventions:

• arms are Fin K, 0-based (the paper's arm $a$ is index $a - 1$); trajectory coordinate $t$ is round $t + 1$;
• $\Theta$ is a nonempty open interval and $\ddot b > 0$ on $\Theta$ (added: the paper says $b$ is convex and twice differentiable; strict convexity is what makes "the unique distribution with mean $\mu$" meaningful); the paper's $d$ is written as the KL divergence of the arm laws (its first equality on p. 3), and the unique optimal arm is defined through the parameter means $\dot b(\theta_a)$;
• $\mathcal S$ is an arbitrary set of models with a unique optimal arm, not the specific set the paper fixes from p. 4 on;
• $\delta$-PAC keeps both halves of the paper's definition (almost-sure stopping and error at most $\delta$);
• $T^*(\boldsymbol\mu)$, divergences and expectations of $\tau$ take values in $[0, \infty]$, never truncated to reals; $T^* = 0$ when $\mathrm{Alt}(\boldsymbol\mu) = \emptyset$ and $T^* = \infty$ when the supremum in eq. (1) is $0$;
• $\delta \le 1/2$ is added. The paper states $\delta \in (0, 1)$, but the theorem and eq. (2) are false for $\delta \in (1/2, 1)$: with two unit-variance Gaussian arms, drawing arm 1 once and naming arm 1 exactly when the fractional part of the reward is below $1/2$ is $0.9$-PAC, while $T^*(\boldsymbol\mu) \to \infty$ as the two means merge. At $\delta = 1/2$ the bound is $0$.

A statement with $\log(1/(4\delta))$ in place of $\mathrm{kl}(\delta, 1 - \delta)$, or restricted to Gaussian arms, is the platform's existing textbook theorem and does not count as this mission's goal; nor does any version that drops the almost-sure stopping clause or truncates $\mathbb E[\tau]$ or $T^*$ to real numbers.

Needed infrastructure: the transportation lemma at a stopping time (data processing for KL through an $\mathcal F_\tau$-measurable event, Wald-type identity for the stopped log-likelihood ratio), the identities "mean of $\nu_\theta$ $= \dot b(\theta)$" and "KL of two family members $= b(\theta') - b(\theta) - \dot b(\theta)(\theta' - \theta)$", and $\mathbb E[\tau] = \sum_a \mathbb E[N_a(\tau)]$. All are reusable beyond this mission. Contributions of any of these lemmas, of eq. (2) alone, or of the Gaussian and Bernoulli special cases as stepping stones are welcome.

Selected references

• A. Garivier, E. Kaufmann, Optimal Best Arm Identification with Fixed Confidence, COLT 2016 (JMLR W&CP 49), arXiv:1602.04589v2. https://arxiv.org/abs/1602.04589
• E. Kaufmann, O. Cappé, A. Garivier, On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models, Journal of Machine Learning Research 17(1), 2016. https://arxiv.org/abs/1407.4443
• T. L. Graves, T. L. Lai, Asymptotically Efficient Adaptive Choice of Control Laws in Controlled Markov Chains, SIAM Journal on Control and Optimization 35(3), 1997. https://doi.org/10.1137/S0363012994275440
• S. Mannor, J. N. Tsitsiklis, The Sample Complexity of Exploration in the Multi-Armed Bandit Problem, Journal of Machine Learning Research 5, 2004. https://www.jmlr.org/papers/v5/mannor04b.html
• T. Lattimore, C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Chapter 33. https://doi.org/10.1017/9781108571401

Motivation

Chapter 2's tail bounds mostly rest on moment-generating-function control, obtained either directly (sub-Gaussianity) or through explicit combinatorial arguments (Hoeffding, bounded differences). The entropic method offers a different, more structural route: bound a specific information-theoretic quantity — the $\varphi$-entropy of $e^{\lambda X}$ — and convert that bound mechanically into a tail bound via a short ODE argument (the Herbst argument). This method's real payoff appears once it is combined with the tensorization property of entropy across independent coordinates, which is what lets it handle Lipschitz functions of many independent variables — including cases, such as separately convex functions, that elude the purely martingale-based techniques of Chapter 2. This mission formalizes the entropic method's two foundational entropy-to-tail conversions and its central Lipschitz-concentration application, following Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint (Cambridge University Press, 2019), Chapter 3.

Setting

For $\varphi(u):=u\log u$ ($u>0$), $\varphi(0):=0$, the $\varphi$-entropy of a nonnegative random variable $Z$ is $H(Z):=\mathbb E[Z\log Z]-\mathbb E[Z]\log\mathbb E[Z]$ (Eqs. (3.1)-(3.2)). Writing $\varphi_X(\lambda):=\mathbb E[e^{\lambda X}]$ for the moment generating function of $X$, the entropy of $e^{\lambda X}$ has the explicit form $H(e^{\lambda X}) = \lambda\varphi_X'(\lambda) -\varphi_X(\lambda)\log\varphi_X(\lambda)$ (Eq. (3.3)).

A function $f:\mathbb R^n\to\mathbb R$ is separately convex if, for each coordinate $k$, the univariate function obtained by fixing every coordinate but the $k$-th is convex — strictly weaker than joint convexity of $f$ itself. $f$ is $L$-Lipschitz with respect to the Euclidean norm if $|f(x)-f(x')|\le L\|x-x'\|_2$ for all $x,x'$.

Formalization targets

Goal — Theorem 3.4 (separately convex Lipschitz concentration)

Let $\{X_i\}_{i=1}^n$ be independent, each supported on $[a,b]$, and $f$ separately convex and $L$-Lipschitz. Then for all $\delta>0$,

Milestone — Proposition 3.2 (the Herbst argument)

If $H(e^{\lambda X})\le\tfrac12\sigma^2\lambda^2\varphi_X(\lambda)$ for all $\lambda\in I$ ($I=[0,\infty)$ or $\mathbb R$), then $\log\mathbb E[e^{\lambda(X-\mathbb E[X])}]\le \tfrac12\lambda^2\sigma^2$ for all $\lambda\in I$ — the basic entropy-to-sub-Gaussian-tail conversion.

Milestone — Proposition 3.3 (the Bernstein entropy bound)

The sub-exponential analogue: if $H(e^{\lambda X})\le\lambda^2\{b\varphi_X'(\lambda)+ \varphi_X(\lambda)(\sigma^2-b\mathbb E[X])\}$ for $\lambda\in[0,1/b)$, then $\log\mathbb E[e^{\lambda(X-\mathbb E[X])}]\le\sigma^2\lambda^2(1-b\lambda)^{-1}$ on the same range.

Significance

Propositions 3.2 and 3.3 are the two basic entropy-to-tail conversions the entire chapter's entropic method rests on — every subsequent Lipschitz-concentration result in the chapter (including Theorem 3.4 and the more advanced Theorem 3.24) is obtained by first establishing an entropy bound of one of these two forms and then invoking the corresponding proposition. Theorem 3.4 is itself the direct analogue, for independent bounded variables, of Chapter 2's Gaussian Lipschitz concentration (Theorem 2.26) — but crucially requires the extra hypothesis of separate convexity, which the Gaussian case does not need and which cannot be dropped in general.

Formalizing it. No faithful prior art exists on the platform. The one candidate flagged in BRIEF.md, Talagrand.lipschitz_concentration, was read in full: it is a weighted-Hamming- distance concentration bound for functions on a finite-alphabet product space Fin n → α, proved via Talagrand's convex-distance method — a different underlying space (finite alphabet vs. real-valued bounded coordinates) and a different Lipschitz norm (weighted Hamming vs. Euclidean) from Theorem 3.4, and not reused here. A search for "log-Sobolev" and "Herbst" turned up bousquet_herbst_cgf_le_phi_via_herbst/bousquet_herbst_cgf_le_phi_double_integration: these are abstract calculus lemmas about a generic function $G$ satisfying an ODE-type growth condition ($G''\le ve^x$), concluding $G(L)\le v(e^L-1-L)$ — a genuinely different statement shape from Proposition 3.2/3.3's entropy-to-CGF conversions (which conclude a quadratic, not exponential, bound on $\log\mathbb E[e^{\lambda(X-\mathbb EX)}]$), and not a faithful match. All three theorems here are drafted as open goals (:= by sorry).

Difficulty

The naive approach to Theorem 3.4 — try to adapt the bounded-differences (martingale) method of Chapter 2 directly — fails, because the bounded-differences method needs $f$ to have small coordinatewise oscillation in an absolute sense, while separate convexity alone gives no such uniform bound (a separately convex function can vary arbitrarily fast within the interior of its domain, only its slope is controlled by the Lipschitz condition). The entropic method sidesteps this by working with the $\varphi$-entropy of $e^{\lambda f(X)}$ directly: entropy has a tensorization property across independent coordinates (not itself part of this mission, but what the entropic method's proof of Theorem 3.4 uses) that reduces a multivariate entropy bound to a sum of "one coordinate at a time" contributions, each of which convexity and the Lipschitz condition jointly control — a route with no analogue in the bounded-differences approach.

Formalization scope

Separate convexity and Euclidean-Lipschitzness are both restated locally in this chapter's own sub-namespace (HighDimStat.Concentration), per this book series' rule against importing another chapter's draft definitions, even though Chapter 2 already defines an IsLLipschitz for the same Euclidean condition. φ_X'(\lambda)$ (Proposition 3.3) is realized via Mathlib's deriv, a legitimate way to state a hypothesis on a derivative without separately proving differentiability, appropriate at the draft-statement stage. Explicit Integrable` hypotheses guard the Bochner integral's junk value on non-integrable functions throughout (trap 2), not literal in the book's own propositions but implied by what "the entropy $H(e^{\lambda X})$ exists" (an explicit qualifier the book itself makes when introducing Eq. (3.2)) means.

Goal substitution, disclosed. BRIEF.md recommends Theorem 3.24 (the two-sided, jointly convex analogue) as the primary goal, but explicitly names Theorem 3.4 as a fallback "if 3.24's dependence on the unnumbered transportation-cost inequality (Eq. 3.73, attributed to Samson) proves too heavy to state faithfully in the time available." Theorem 3.24's proof route depends on Theorem 3.19 (a general "transportation cost implies concentration" result for an abstract metric measure space, itself needing a from-scratch formalization of the transportation-cost inequality (3.58) and the concentration function $\alpha_{P,(\mathcal X,\rho)}$) plus the unproven-in-chapter Eq. (3.73). Building this full stack faithfully was judged to exceed this chunk's time budget; Theorem 3.4 is drafted instead, using this mission's own budget on Propositions 3.2 and 3.3 (the two most load-bearing entropy-to-tail conversions of the chapter) rather than the heavier transportation-cost machinery. Theorem 3.19, Theorem 3.24, and Eq. (3.73) are all out of scope for this mission and named here as natural follow-on work.

Selected references

• M. J. Wainwright, High-Dimensional Statistics: A Non-Asymptotic Viewpoint, Cambridge University Press, 2019. DOI: 10.1017/9781108627771. Chapter 3.
• M. Ledoux, The Concentration of Measure Phenomenon, American Mathematical Society, 2001.
• I. Herbst, unpublished (the argument bearing his name is attributed in Ledoux (2001) and standard references on log-Sobolev inequalities).

Motivation

In best arm identification with fixed confidence, a learner samples $K$ unknown distributions ("arms") one at a time, and must eventually stop and name the arm with the largest mean, with an error probability at most a prescribed risk $\delta$, while using as few samples as possible. The problem goes back to the sequential design of experiments (Chernoff, 1959; Even-Dar, Mannor and Mansour, 2006) and underlies adaptive A/B testing, clinical trial design and hyperparameter selection.

Any fixed-confidence strategy consists of three parts: a sampling rule, a stopping rule and a decision rule. Garivier and Kaufmann (arXiv:1602.04589, COLT 2016) proposed the Track-and-Stop strategy, the first shown to match the asymptotic lower bound on the expected sample complexity. Its stopping rule is a generalized likelihood ratio (GLR) test, Chernoff's stopping rule. Its correctness, the guarantee that the recommended arm is wrong with probability at most $\delta$, must hold whatever the sampling rule, which is what allows the sampling rule to be tuned freely for efficiency. This mission formalizes that guarantee for Bernoulli arms, Theorem 10 of the paper, with its explicit threshold $\beta(t,\delta) = \log(2t(K-1)/\delta)$.

Setting

The arms are $\mathcal A = \{1,\dots,K\}$. A Bernoulli bandit model is a mean vector $\boldsymbol\mu = (\mu_1,\dots,\mu_K) \in [0,1]^K$: pulling arm $a$ returns reward $1$ with probability $\mu_a$ and $0$ otherwise, independently of the past. The class $\mathcal S$ contains the models with a unique optimal arm $a^*(\boldsymbol\mu)$, i.e. $\mu_{a^*} > \mu_i$ for all $i \ne a^*$.

At round $t$ the learner chooses an arm $A_t$ as a (possibly randomized) function of the past observations and observes a reward $X_t$. Write $N_a(t)$ for the number of pulls of arm $a$ among the first $t$ rounds, $s_a(t)$ for the number of those pulls that returned $1$, and $\hat\mu_a(t) = N_a(t)^{-1}\sum_{s \le t} X_s \mathbb 1\{A_s = a\}$ for the empirical mean. The likelihood of arm $a$'s observations under mean $u$ is $p_u(\underline X^a_{N_a(t)}) = u^{s_a(t)}(1-u)^{N_a(t)-s_a(t)}$.

The GLR statistic for "arm $a$ is at least as good as arm $b$" is

Chernoff's stopping rule with exploration rate $\beta(t,\delta)$ is

and the decision rule recommends $\hat a_{\tau_\delta} \in \operatorname{argmax}_a \hat\mu_a(\tau_\delta)$.

The Krichevsky–Trofimov (KT) distribution on binary sequences $x \in \{0,1\}^n$ is $\mathrm{kt}(x) = \int_0^1 \big(\pi\sqrt{u(1-u)}\big)^{-1} p_u(x)\,\mathrm du$, the Bernoulli likelihood mixed over the Beta$(1/2,1/2)$ prior.

Formalization targets

Goal: Theorem 10

For every $\delta \in (0,1)$, every sampling strategy, and the threshold $\beta(t,\delta) = \log\big(2t(K-1)/\delta\big)$,

Milestone: Lemma 11 (Willems, Shtarkov and Tjalkens, 1995)

$\mathrm{kt}$ is a probability law on $\{0,1\}^n$, and for $n \ge 1$,

Milestone: the pairwise crossing bound of Appendix C.1

With $T_{a,b} = \inf\{t : Z_{a,b}(t) > \beta(t,\delta)\}$, for all arms with $\mu_a < \mu_b$,

Significance

Theorem 10 decouples correctness from efficiency. Because the guarantee holds for every sampling strategy, any sampling rule, including the C-Tracking and D-Tracking rules of Track-and-Stop, the uniform rule, or a heuristic, inherits $\delta$-correctness as soon as it is paired with Chernoff's stopping rule at this threshold. The asymptotic optimality result of the paper (Theorem 14) then only has to control the sample complexity. The threshold is explicit, with no unspecified constant, in contrast to the deviational threshold of Proposition 12.

The result is proved in the paper, in Appendix C.1, and rests on Lemma 11, which the paper quotes from the universal coding literature without proof. As far as the platform's catalog shows, none of these results is formalized. The platform holds a machine-checkable statement of the analogous result for Gaussian arms with the Lattimore–Szepesvári threshold (BanditAlgorithm.chernoff_stopping_rule_sound, Lemma 33.7 of Bandit Algorithms), which is a different model and a different threshold. Formalizing Theorem 10 adds a proof of Lemma 11 (the KT regret bound, reusable in information theory and universal prediction), the Bernoulli GLR statistic, and a change of measure from the true bandit law to a Bayesian mixture law on the trajectory space.

Difficulty

The obvious approach bounds, for each fixed $t$, the probability that $Z_{a,b}(t)$ exceeds $\beta(t,\delta)$ by a concentration inequality and sums over $t$. This fails: the sampling strategy is arbitrary and adaptive, so $N_a(t)$ and $N_b(t)$ are random and depend on the past rewards, and a fixed-sample-size deviation bound does not apply; a union bound over the possible values of the counts loses more than the threshold allows. The maximum likelihood in the numerator of $Z_{a,b}$ is also not a probability density, so the likelihood ratio cannot directly be read as a change of measure. The argument must control the whole trajectory law under an arbitrary randomized policy, and must handle empty samples (an arm never pulled contributes likelihood $1$) and the boundary means $0$ and $1$.

Formalization scope

The formalization is in Lean 4 with Mathlib and reuses the platform's canonical bandit model: StochasticBandit, BanditPolicy (a Markov kernel per round from the observed history to the next arm, so randomized strategies are included), banditTrajMeasure (the law of the infinite trajectory, where coordinate $s$ is round $s+1$) and IsSoundBAI from BanditTrajectory; bernoulliBandit from bernoulliRelativeEntropy; and only the pull counts trajPullCount and empirical means trajEmpiricalMean from TrackAndStop. The Gaussian GLR and threshold of TrackAndStop are not used.

Conventions committed to:

• Arms are Fin K. Bernoulli means range over $[0,1]$, degenerate laws included; the paper's exponential-family mean space is $(0,1)$, so the $[0,1]$ statement implies the paper's.
• $Z_{a,b}(t)$ is defined as the ratio of the two maxima over $[0,1]^2$, not by the closed form (7), which holds only when $\hat\mu_a(t) \ge \hat\mu_b(t)$. Both maxima are attained and positive.
• The stopping rule ranges over $t \ge 1$; at $t = 0$ there is no observation and the paper's $\beta(0,\delta) = \log 0$ is undefined. $\tau_\delta = \infty$ when the rule never fires.
• The decision rule is quantified: the goal holds for every recommendation that maximizes the empirical mean at $\tau_\delta$, whatever the tie-breaking.
• Probabilities of events are outer measures under the trajectory law; no measurability is assumed.
• $K \ge 1$ only. For $K = 1$ the statement is trivially true (no suboptimal arm).

Disclosed deviations from the page: Lemma 11's ratio bound is stated for $n \ge 1$, since at $n = 0$ the printed bound reads $1 \le 0$; the use of the lemma in Appendix C.1 is unaffected. Appendix C.1 calls the result "Proposition 10" (a slip for Theorem 10) and prints the KT density as $1/\sqrt{\pi u(1-u)}$ (a slip for $1/(\pi\sqrt{u(1-u)})$ of Lemma 11, which is the normalized one); the formalization follows Lemma 11.

A trivializing formalization is ruled out: stating the result for Gaussian arms or with the Lattimore–Szepesvári threshold is the platform's existing Lemma 33.7 and is not Theorem 10, and a free decision rule without the argmax hypothesis would make the claim false rather than faithful.

Contributions welcome: a proof of Lemma 11; a change-of-measure lemma for banditTrajMeasure under a mixture of environments; and the union-bound reduction from the goal to the pairwise claim.

Selected references

• A. Garivier, E. Kaufmann, Optimal Best Arm Identification with Fixed Confidence, COLT 2016 (JMLR W&CP 49), arXiv:1602.04589v2, 2016. https://arxiv.org/abs/1602.04589
• F. M. J. Willems, Y. M. Shtarkov, T. J. Tjalkens, The context-tree weighting method: basic properties, IEEE Transactions on Information Theory 41(3), 1995. https://doi.org/10.1109/18.382012
• R. Krichevsky, V. Trofimov, The performance of universal encoding, IEEE Transactions on Information Theory 27(2), 1981. https://doi.org/10.1109/TIT.1981.1056331
• H. Chernoff, Sequential design of experiments, Annals of Mathematical Statistics 30(3), 1959. https://doi.org/10.1214/aoms/1177706205
• T. Lattimore, C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Chapter 33. https://doi.org/10.1017/9781108571401

Why robustify a sampled stochastic program

Many decision problems under uncertainty take the form of a stochastic program: choose a decision $v$ from a feasible set $\mathcal F$ to maximise the expected utility $\mathbb E_{x\sim\mu}[f(v,x)]$, where the distribution $\mu$ of the uncertain parameter $x\in\mathbb R^m$ is known only through i.i.d. samples $x_1,\dots,x_n$. The standard remedy, sample average approximation, maximises $\frac1n\sum_i f(v,x_i)$ instead. Its consistency (convergence of the optimal expected utility of its solutions to the true optimum) is classical, but it needs regularity assumptions of its own, for example those of King and Wets (Stochastics and Stochastic Reports, 1991), cited on p. 98 of the paper; the paper presents its construction as a route to consistency under weaker conditions.

Robust optimization (RO) takes a different route: it protects each sample by an uncertainty set and optimises against the worst point in it. Xu, Caramanis and Mannor (Math. Oper. Res. 2012) show that RO over several overlapping uncertainty sets is equivalent to a distributionally robust stochastic program (their Theorem 2.1, the subject of mission I of this series). Section 3 of the paper uses that equivalence to show that a specific robustification of the sampled problem, with $\ell_\infty$ boxes of shrinking radius around each sample, is consistent under only boundedness and equicontinuity of $f$. This mission formalizes that result, Theorem 3.1.

Setting

Equip $\mathbb R^m$ with the sup norm $\|z\|_\infty=\max_k|z_k|$, its Borel $\sigma$-algebra and Lebesgue measure $dx$. The data are:

• a set of decisions $V$ and a nonempty feasible set $\mathcal F\subseteq V$;
• a utility $f:V\times\mathbb R^m\to\mathbb R$, Borel measurable in $x$ for each $v$;
• a true density $h^*$ on $\mathbb R^m$ (nonnegative, $\int h^*\,dx=1$) and i.i.d. samples $x_1,x_2,\dots$ with distribution $h^*(x)\,dx$;
• radii $\epsilon(n)>0$.

For a sample $x_1,\dots,x_n$ the boxes are $\mathcal Z_i=\{x_i+\delta\mid\|\delta\|_\infty\le\epsilon(n)\}$, and the box-robust sample objective is

The RO solution $v(n)$ is a maximiser of $J_n$ over $\mathcal F$. The equicontinuity modulus of $f$ is

The proof works with the distribution set $\mathcal P_n$ of probability measures $\mu$ with $\mu(\bigcup_{i\in S}\mathcal Z_i)\ge|S|/n$ for every $S\subseteq\{1,\dots,n\}$, and with the uniform box kernel density estimator

Formalization targets

Goal: Theorem 3.1 (p. 98)

Assume $|f(v,x)|\le C$ for all $v,x$; $d(\epsilon)\to0$ as $\epsilon\downarrow0$; $\epsilon(n)\downarrow0$ and $n\epsilon(n)^m\uparrow\infty$. Then for every choice of maximisers $v(n)$, with probability one,

Milestones (proof of Theorem 3.1, p. 99)

1. $h_n$ is the density of a probability measure in $\mathcal P_n$.
2. $J_n(v)\le\int f(v,x)\,h_n(x)\,dx$ for every $v$.
3. Oscillation over a box: $\sup_{\mathcal Z_i}f(v,\cdot)-\inf_{\mathcal Z_i}f(v,\cdot)\le d(2\epsilon(n))$.
4. Eq. (7): with $M_n=C\int|h_n-h^*|\,dx$, for every $v$,

5. Strong $L^1$ consistency of the box kernel density estimator: if $\epsilon(n)\to0$ and $n\epsilon(n)^m\to\infty$, then $\int|h_n-h^*|\,dx\to0$ almost surely.

Milestones 1–4 are deterministic statements about a fixed sample; milestone 5 is the only probabilistic input.

Significance

Theorem 3.1 gives consistency of a tractable robust reformulation of a sampled stochastic program under conditions the paper notes are weaker than those of King and Wets for sampled stochastic programs: $f$ need only be bounded and equicontinuous in $x$, uniformly in $v$, and the true distribution need only have a density. It also gives an explicit schedule for the size of the uncertainty set, $\epsilon(n)\to0$ with $n\epsilon(n)^m\to\infty$, the bandwidth condition of kernel density estimation. Section 4 of the paper applies the same distributional interpretation to regularised learning methods such as the support vector machine and the Lasso.

The result is proved in the paper, with the $L^1$ consistency of kernel density estimators (Devroye 1983; Devroye and Györfi 1985) cited rather than proved. No part of it is formalized in Lean or on this platform as far as a search of the platform found. A complete development would produce, besides Theorem 3.1, a machine-checked strong $L^1$ consistency theorem for kernel density estimators, which is a basic result of nonparametric statistics in its own right.

Difficulty

The deterministic part (milestones 1–4) is measure-theoretic bookkeeping: the kernel integrates to one only because the box is a sup-norm ball of volume $(2\epsilon)^m$, and every infimum and supremum must be handled with care, since $f$ need not attain them.

The obstacle is milestone 5. Almost-sure $L^1$ convergence of $h_n$ to an arbitrary density $h^*$, with no continuity or support assumption, does not follow from the strong law of large numbers applied pointwise: $h_n(x)$ is an average of $n$ terms whose law changes with $n$ through $\epsilon(n)$, and almost-sure convergence at each fixed $x$ does not give convergence of the integral along a single sample path. The theorem needs both a bias estimate valid for every integrable density and a concentration estimate for the random $L^1$ error. Mathlib has Lebesgue differentiation and the strong law, but no kernel density estimator and no such concentration result.

Formalization scope

• $\mathbb R^m$ is Fin m → ℝ, whose Mathlib norm is the sup norm; boxes are Metric.closedBall. The integrals $\int f(v,x)h^*(x)\,dx$ are Bochner integrals against Lebesgue measure of integrable integrands.
• The samples are a sequence X : ℕ → Ω → Fin m → ℝ on a probability space, independent (iIndepFun) and each with law volume.withDensity h*; $x_1,x_2,\dots$ become X 0, X 1, …, and the $n$-th problem uses the first $n$. "With probability one" is ∀ᵐ ω ∂P.
• The goal quantifies over every selection $v(n)$ of maximisers, with no measurability assumed; a version with one chosen maximiser would be weaker and is ruled out.
• Readings and corrections of the printed text:
  • the kernel argument printed $(x-x_i)/\epsilon$ on p. 98 is read as $(x-x_i)/\epsilon(n)$, as the proof on p. 99 writes it;
  • "$\max_{v,x}|f(v,x)|\le C$" is read as the uniform bound $|f|\le C$ and the "max" in $d(\epsilon)$ as a supremum;
  • "$d(\epsilon)\downarrow0$" is read as $d(\epsilon)\to0$ as $\epsilon\downarrow0$;
  • implicit hypotheses made explicit: $\mathcal F\ne\emptyset$, $\epsilon(n)>0$, measurability of $f(v,\cdot)$, $h^*$ a Lebesgue density;
  • the monotonicity in "$\epsilon(n)\downarrow0$, $n\epsilon(n)^m\uparrow\infty$" is kept in the goal; milestone 5 uses the limits only, as the paper states it;
  • the paper's $M_n$ ("there exists $\{M_n\}\to0$") is made explicit as $M_n=C\int|h_n-h^*|$, so Eq. (7) is stated for every sample.
• Remark 3.2 and Appendix B (an integrable envelope in place of boundedness) are not part of this mission.
• Every real infimum and supremum ranges over a nonempty set of values bounded by $C$ in absolute value, so no statement holds through a junk value; a formalization in which the supremum over $\mathcal F$ or the box infimum could be vacuous is excluded.
• The definitions (boxes, $\mathcal P_n$, the kernel, the estimator, $J_n$, $d$) live in one definition file. $\mathcal P_n$ duplicates, with weights $1/n$, the distribution set of mission I; the duplication is deliberate because draft missions cannot import each other.
• Welcome contributions: the kernel density estimator and its strong $L^1$ consistency as reusable infrastructure, and any of the deterministic milestones.

Selected references

• H. Xu, C. Caramanis, S. Mannor, A Distributional Interpretation of Robust Optimization, Mathematics of Operations Research 37(1):95–110, 2012. https://doi.org/10.1287/moor.1110.0531
• L. Devroye, The equivalence of weak, strong and complete convergence in $L_1$ for kernel density estimates, Annals of Statistics 11(3):896–904, 1983.
• L. Devroye, L. Györfi, Nonparametric Density Estimation: The $L_1$ View, Wiley, 1985.
• A. J. King, R. J.-B. Wets, Epi-consistency of convex stochastic programs, Stochastics and Stochastic Reports 34(1), 1991 (reference [22] of the paper).

Motivation

Algorithmic stability asks how much the output of a learning algorithm changes when its training sample is perturbed. Since Devroye and Wagner (IEEE Trans. Inf. Theory 1979) it has served as a route to generalization bounds that does not go through the complexity of the hypothesis class. Bousquet and Elisseeff (JMLR 2002) popularised uniform stability, and Mukherjee, Niyogi, Poggio and Rifkin (Adv. Comput. Math. 2006) showed that for empirical risk minimisation in supervised learning, a leave-one-out type of stability is necessary and sufficient for consistency.

Shalev-Shwartz, Shamir, Srebro and Sridharan (JMLR 11, 2010) study stability in Vapnik's General Learning Setting, where uniform convergence can fail even though the problem is learnable. In Appendix A.2 they compare replace-one and leave-one-out (LOO) stability. For an empirical risk minimiser they prove that LOO stability is equivalent to consistency and to generalization, provided each property holds with one rate for all distributions (Theorem 31, p. 2667). This mission formalizes that theorem and the lemmas of Section 5.3 on which its proof rests.

Timeline:

• 1979, Devroye–Wagner: leave-one-out estimates for local rules.
• 2002, Bousquet–Elisseeff: uniform stability implies generalization.
• 2002, Kutin–Niyogi (UAI 2002): a taxonomy of stability notions.
• 2006, Mukherjee et al.: LOO stability characterises consistency of ERM in supervised learning.
• 2010, Shalev-Shwartz et al.: in the General Learning Setting, for ERMs, LOO stability, universal consistency and universal generalization are equivalent (Theorem 31). Universally consistent AERMs need not be LOO stable (Example 6).

Setting

A learning problem consists of an instance space $\mathcal Z$ with a $\sigma$-algebra, a nonempty hypothesis class $\mathcal H$, and an objective $f:\mathcal H\times\mathcal Z\to\mathbb R$ with $|f(h;z)|\le B$ for all $h,z$. For a probability measure $\mathcal D$ on $\mathcal Z$:

• the risk is $F(h)=\mathbb E_{z\sim\mathcal D}[f(h;z)]$ and the optimal risk is $F^*=\inf_{h}F(h)$;
• for a sample $S=(z_1,\dots,z_m)\sim\mathcal D^m$ of $m$ i.i.d. draws, the empirical risk is $F_S(h)=\frac1m\sum_{i}f(h;z_i)$, and $F_S(\hat h_S)=\inf_hF_S(h)$ denotes the minimal empirical risk;
• a learning rule $A$ maps each sample of size $m\ge1$ to a hypothesis $A(S)$. It is an ERM if $F_S(A(S))=F_S(\hat h_S)$ for every sample. It is an AERM with rate $\varepsilon_{\mathrm{erm}}$ if $\mathbb E[F_S(A(S))-F_S(\hat h_S)]\le\varepsilon_{\mathrm{erm}}(m)$;
• $A$ is consistent with rate $\varepsilon$ if $\mathbb E_{S\sim\mathcal D^m}[F(A(S))-F^*]\le\varepsilon(m)$. It generalizes with rate $\varepsilon$ if $\mathbb E[|F(A(S))-F_S(A(S))|]\le\varepsilon(m)$, and it on-average generalizes if $|\mathbb E[F(A(S))-F_S(A(S))]|\le\varepsilon(m)$;
• writing $S^{\setminus i}$ for $S$ with $z_i$ removed, $A$ is LOO stable with rate $\varepsilon$ (Definition 29) if

A rate is a sequence $\varepsilon(m)$ that is non-increasing and tends to $0$. A property holds universally if it holds under every $\mathcal D$ with one and the same rate.

Formalization targets

Goal: Theorem 31

For an ERM $A$:

The statement has no rates. Each side asserts that some rate exists and serves every distribution.

Milestones

In the order the proof uses them:

1. Utility Lemma 12: $\mathbb E|X-\mathbb EX|\le B/\sqrt m$ for the mean $X$ of $m$ i.i.d. variables bounded by $B$.
2. Utility Lemma 13: $X\le Y$ a.s. implies $\mathbb E|X|\le|\mathbb EX|+2\mathbb E|Y|$.
3. Lemma 14: an AERM that on-average generalizes with rate $\varepsilon_{\mathrm{oag}}$ generalizes with rate $\varepsilon_{\mathrm{oag}}+2\varepsilon_{\mathrm{erm}}+2B/\sqrt m$.
4. Lemma 15: under the same hypotheses the rule is consistent with rate $\varepsilon_{\mathrm{oag}}+\varepsilon_{\mathrm{erm}}$.
5. Lemma 16 (Main Converse Lemma): in a learnable problem, $\mathbb E|F_S(\hat h_S)-F^*|\le2\varepsilon_{\mathrm{cons}}(m')+2B/\sqrt m+2Bm'^2/m$ for $2\le m'\le m/2$.
6. Lemma 17: Eq. (12), together with an AERM that is consistent, gives generalization with rate $\varepsilon_{\mathrm{emp}}+\varepsilon_{\mathrm{erm}}+\varepsilon_{\mathrm{cons}}$.
7. First display of the proof of Theorem 31: a generalizing ERM is LOO stable with rate $\varepsilon_{\mathrm{gen}}(m-1)$.
8. Second display: a LOO stable ERM on-average generalizes on samples of size $m-1$ with rate $\varepsilon_{\mathrm{stable}}(m)+2B/m$.