Probability

Motivation

The book is discriminative almost throughout: it learns predictors, not distributions, following Vapnik's advice not to solve a more general problem as an intermediate step. Chapter 24 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), presents the generative alternative: assume a parametric form for the data distribution and estimate its parameters. The maximum likelihood principle is introduced on Bernoulli and Gaussian samples, shown to be empirical risk minimization for the log-loss, and analyzed through the decomposition of the true log-loss risk into a relative entropy plus an entropy (24.5), which explains both its consistency under a correct model and its overfitting on small samples. Naive Bayes and linear discriminant analysis show how generative assumptions reduce the number of parameters and make the Bayes classifier linear (24.8). The chapter's main theorem concerns the Expectation-Maximization algorithm of Dempster, Laird and Rubin for latent-variable models such as Gaussian mixtures: EM never decreases the log-likelihood (Theorem 24.3), because it is an alternate maximization of a lower bound $G(Q, \theta)$ that touches the likelihood at the posterior (Lemma 24.2). The chapter ends with Bayesian reasoning and the rule of succession.

Setting

A Bernoulli sample $S = (x_1, \dots, x_m)$ has log-likelihood $L(S;\theta) = \log(\theta)\sum_i x_i + \log(1-\theta)\sum_i(1-x_i)$ and estimator $\hat\theta = \frac1m\sum_i x_i$ (24.1); a Gaussian sample has $L(S;(\mu,\sigma)) = -\frac1{2\sigma^2}\sum_i(x_i-\mu)^2 - m\log(\sigma\sqrt{2\pi})$. The log-loss is $\ell(\theta, x) = -\log P_\theta[x]$ (24.4); on a finite domain, $D_{RE}[P\|Q] = \sum_x P[x]\log(P[x]/Q[x])$ and $H(P) = \sum_x P[x]\log(1/P[x])$. A latent-variable model is a parametric joint $P_\theta[X = x, Y = y]$, $y \in [k]$, with $L(\theta) = \sum_i\log\sum_y P_\theta[X = x_i, Y = y]$; $F(Q,\theta) = \sum_i\sum_y Q_{i,y}\log P_\theta[X = x_i, Y = y]$, $G(Q,\theta) = F(Q,\theta) - \sum_i\sum_y Q_{i,y}\log Q_{i,y}$ over the set $\mathcal{Q}$ of row-stochastic matrices, and EM alternates the E-step $Q^{(t+1)}_{i,y} = P_{\theta^{(t)}}[Y = y \mid X = x_i]$ (24.10) with the M-step $\theta^{(t+1)} \in \operatorname{argmax}_\theta F(Q^{(t+1)}, \theta)$ (24.11).

Formalization targets

Goal: Theorem 24.3

For a positive parametric joint $P_\theta[X = x, Y = y]$, a sample $x_1, \dots, x_m$, and any run $\theta^{(0)}, \theta^{(1)}, \dots$ of EM (each M-step returning some maximizer of $F(Q^{(t+1)}, \cdot)$), the log-likelihood never decreases:

$$L(\theta^{(t+1)}) \ge L(\theta^{(t)}) \quad\text{for all } t.$$

Milestones

Equation (24.2) (Hoeffding for the Bernoulli estimator); the Gaussian maximum likelihood estimates of §24.1.1; Equation (24.5) (the risk decomposition $D_{RE}[P\|P_\theta] + H(P)$); Equation (24.8) (the LDA log-likelihood ratio is affine); Lemma 24.2 (EM as alternate maximization of $G$, with $G(Q, \theta) \le L(\theta)$ and equality at the posterior). Further items: Gibbs' inequality, the Bernoulli maximum likelihood estimator (24.1)/(24.3), Exercise 1 (the biased variance estimate), Equation (24.6), the overfitting example of §24.1.3, Exercise 3 / (24.14), the weighted-centroid M-step (24.13), and the rule of succession of §24.5.

Significance

Theorem 24.3 is the guarantee that makes EM a sensible algorithm: it does not find the maximum likelihood estimate, but it climbs monotonically, and Lemma 24.2 identifies why, the E-step chooses the tightest lower bound $G(Q, \cdot)$ at the current parameter and the M-step maximizes it. This variational view underlies a large part of modern latent-variable inference. Equation (24.5) is the information-theoretic content of maximum likelihood: the true risk is the entropy of the data plus the relative entropy to the model, so the best parameter is a projection of the data distribution onto the model class, and Gibbs' inequality is what makes that projection meaningful. The Bernoulli and Gaussian computations are the standard first examples, and Equation (24.8) is the reason linear classifiers appear in generative modeling. On the platform, the mission adds the relative entropy on finite domains, the EM objects, and Gaussian-integral identities that later probabilistic work can reuse.

Difficulty

The Bernoulli and Gaussian maximum likelihood facts are calculus, but as global maximization statements they need the concavity of $\log$ and an explicit completion of squares rather than the book's stationary-point argument; the Gaussian case reduces to minimizing $\sigma \mapsto \frac{m\hat\sigma^2}{2\sigma^2} + m\log\sigma$. Equation (24.5) is a finite-sum identity; Gibbs' inequality is Jensen for $\log$ with the equality case, or the elementary $\log t \le t - 1$. Lemma 24.2 is Jensen's inequality applied row by row to $\sum_y Q_{i,y}\log(P_\theta[X = x_i, Y = y]/Q_{i,y})$, with care at entries $Q_{i,y} = 0$, where the convention $0\log 0 = 0$ is exactly Lean's junk value; Theorem 24.3 chains the lemma's three parts as the book does. The Gaussian expectation identities (Exercise 1 and (24.6)) require the moments of gaussianReal and Fubini over the product law. Hoeffding's inequality (24.2) is Mission II's Theorem for Bernoulli variables; the overfitting example is the inequality $\log(1-\theta) \ge -2\theta$ on $[0, 1/2]$. The rule of succession is a Beta-function identity provable by integration by parts.

Formalization scope

Parametric families are functions from a parameter type to real-valued probabilities or densities, following the book's convention (p. 344) that $P[X = x]$ denotes either; no measure-theoretic densities are needed except in the two Gaussian-integral items, which use gaussianReal and the i.i.d. law of Mission I, and in the two Bernoulli probability items, which use the Bernoulli law of Mission XIV. Lean's log 0 = 0 is handled explicitly: the EM items assume a positive joint, since with junk logarithms Theorem 24.3 is false (the M-step could pick a parameter with a zero component and inflated $F$), while the entropy terms $Q\log Q$ use the convention $0\log 0 = 0$ that the book intends; the Bernoulli maximum likelihood statement ranges over $\theta \in (0,1)$; the log-loss decomposition and Gibbs' inequality take the second distribution positive. The M-step is a predicate ("some maximizer"), so Assumption 24.1 is not modeled, and an EM run is any sequence of such steps. The Gaussian maximum likelihood statement requires a nonconstant sample, without which the likelihood is unbounded; the overfitting example is stated for $\theta^\star \le 1/2$, the range on which the book's inequality $(1-\theta)^m \ge e^{-2\theta m}$ holds. Equation (24.8) is stated as a matrix identity for any symmetric $M$ in place of $\Sigma^{-1}$; the soft k-means M-step is stated as the weighted-centroid minimization it amounts to.

Not stated: Naive Bayes (24.7), which is a rewriting of Bayes' rule; the mixture density itself and the E-step formula (24.12); the Bayesian derivations (24.16) and maximum a posteriori estimation; Exercise 2.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 24. doi:10.1017/CBO9781107298019
• A. P. Dempster, N. M. Laird, D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society B 39(1), 1977. doi:10.1111/j.2517-6161.1977.tb01600.x
• C. F. J. Wu, On the convergence properties of the EM algorithm, Annals of Statistics 11(1), 1983. doi:10.1214/aos/1176346060
• T. M. Cover, J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006. doi:10.1002/047174882X
• C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006.

Motivation

Dimensionality reduction maps data in $\mathbb{R}^d$ to $\mathbb{R}^n$, $n \ll d$, by a linear map $x \mapsto Wx$, for computational reasons, for generalization (Chapter 19's curse of dimensionality) and for interpretability. Chapter 23 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019), studies three ways to choose $W$. Principal Component Analysis chooses the pair of compression and recovery matrices that minimizes the total squared reconstruction error, and the answer is the eigenvectors of $\sum_i x_ix_i^\top$ for the largest eigenvalues (Theorem 23.2). Random projections choose $W$ with independent Gaussian entries, and the Johnson–Lindenstrauss lemma says that the norms of any finite set of vectors are then preserved up to $1 \pm \epsilon$ with $n = O(\epsilon^{-2}\log|Q|)$ (Lemma 23.4). Compressed sensing exploits sparsity: a matrix with the restricted isometry property compresses every $s$-sparse vector losslessly (Theorem 23.6), the reconstruction can be done by $\ell_1$ minimization, a linear program, with an error bound that degrades gracefully for approximately sparse inputs (Theorem 23.8, due to Candès), and Gaussian random matrices with $n = O(s\log d)$ rows are RIP with high probability (Theorem 23.9).

Setting

Vectors are functions $\mathbb{R}^d$ with $\|v\|_2^2 = \sum_i v_i^2$, $\|v\|_1 = \sum_i|v_i|$ and $\|v\|_0 = |\{i : v_i \ne 0\}|$. The PCA problem (23.1) is $\operatorname{argmin}_{W \in \mathbb{R}^{n \times d}, U \in \mathbb{R}^{d \times n}}\sum_{i=1}^m\|x_i - UWx_i\|_2^2$, and $A = \sum_i x_ix_i^\top$. A random matrix has independent $N(0, v)$ entries, $v = 1$ in Lemma 23.3 and $v = 1/n$ afterwards. $W$ is $(\epsilon, s)$-RIP if $\big|\|Wx\|_2^2/\|x\|_2^2 - 1\big| \le \epsilon$ for every $x \ne 0$ with $\|x\|_0 \le s$ (Definition 23.5); $v_I$ is $v$ restricted to an index set $I$.

Formalization targets

Goal: Theorem 23.2

Let $x_1, \dots, x_m \in \mathbb{R}^d$, $A = \sum_i x_ix_i^\top$, and let $u_1, \dots, u_n$ be eigenvectors of $A$ for its $n$ largest eigenvalues, formalized as the first $n$ columns of a spectral decomposition $A = V\operatorname{diag}(D)V^\top$ with $V^\top V = I$ and $D$ nonincreasing. Then $U = [u_1 \cdots u_n]$ with $W = U^\top$ minimizes (23.1): for every $U', W'$,

$$\sum_i\|x_i - UU^\top x_i\|^2 \le \sum_i\|x_i - U'W'x_i\|^2.$$

Milestones

Lemma 23.1 (the reduction of (23.1) to orthonormal $U$ and $W = U^\top$); Lemma 23.4 (Johnson–Lindenstrauss); Theorem 23.6 (exact $\ell_0$ recovery under RIP); Theorem 23.8 (Candès' $\ell_1$ recovery bound); Theorem 23.9 (Gaussian matrices are RIP). Further items: Equation (23.3), Exercise 2, Remark 23.1 (the optimal value $\sum_{i>n}D_{i,i}$), the eigenvector transfer of §23.1.1, Lemma 23.3, Theorem 23.7, Lemma 23.10, Lemma 23.11 and Lemma 23.12.

Significance

Theorem 23.2 is the Eckart–Young–Mirsky theorem in the form the book states it: PCA is the optimal linear compression-and-recovery scheme in the least-squares sense, and its solution is spectral. The Johnson–Lindenstrauss lemma is the basic tool of randomized dimensionality reduction, with a bound independent of $d$, and the book's variant with explicit constants is what later chapters and the compressed-sensing proofs use. Theorems 23.6–23.9 together are the three "surprising results" of compressed sensing: information-theoretic recoverability from RIP, efficient recovery by convex relaxation, and the existence of RIP matrices by randomness; their proofs, Candès' cone argument and Baraniuk–Davenport–DeVore–Wakin's net-plus-union-bound, are among the cleanest in applied mathematics and are natural formalization targets. On the platform, the mission introduces Gaussian random matrices as product measures and the RIP predicate, usable by later work on sparse recovery.

Difficulty

Lemma 23.1 requires building an orthonormal basis of the range of $UW$, padded to $n$ vectors when the range has smaller dimension, and the identity $\|x - Vy\|^2 = \|x\|^2 + \|y\|^2 - 2y^\top V^\top x$; Equation (23.3) is a trace computation. Theorem 23.2 combines (23.3), the change of basis $B = V^\top U$ with $B^\top B = I$, the bound $\sum_i B_{j,i}^2 \le 1$ from extending $B$ to an orthogonal matrix, and Exercise 2, a rearrangement inequality; Remark 23.1 adds $\operatorname{trace}(A) = \sum_j D_{j,j}$. Lemma 23.3 is the concentration of a $\chi^2_n$ variable (Lemma B.12), which must itself be established from the Gaussian moment generating function; the Johnson–Lindenstrauss lemma is then a union bound. Theorem 23.6 is a two-line contradiction with RIP applied to $x - \tilde x$. Theorem 23.8 is the substantial one: the partition of $[d]$ into blocks of $s$ largest remaining entries, the bound $\|h_{T_j}\|_2 \le s^{-1/2}\|h_{T_{j-1}}\|_1$, the $\ell_1$-minimality inequality (23.8), Lemma 23.10, and the two claims combined through (23.5); a formal proof must handle the last, possibly shorter block, which the book's "assume $d/s$ is an integer" sidesteps. Lemma 23.11 is a volumetric net bound; Lemma 23.12 applies the Johnson–Lindenstrauss lemma to the image of an $\epsilon/4$-net of the unit sphere of $\mathbb{R}^s$ and closes the gap by the "smallest $a$" argument, and Theorem 23.9 is a union bound over index sets.

Formalization scope

Vectors are plain functions Fin d → ℝ with explicit norms, and matrices are Mathlib matrices, so the objectives are finite sums with no coercions between normed spaces. Random matrices are functions Fin n → Fin d → ℝ with the product of Gaussian laws gaussianReal 0 v, applied through Matrix.of; probability statements bound the outer measure of the failure event, and the failure events of Lemmas 23.4 and 23.12 are written with $\ge \epsilon$ so that the book's strict conclusions follow. "Eigenvectors corresponding to the $n$ largest eigenvalues" is formalized as the first $n$ columns of a spectral decomposition with nonincreasing diagonal, which is exactly the set of such systems and avoids Mathlib's eigenvalue ordering conventions. Minimizers ($\tilde x$, $x^\star$, $x_s$) are arbitrary elements of the argmin.

Five statements are given as their proofs support them, and the item texts say so. Lemma 23.3 and the Johnson–Lindenstrauss lemma are stated for $\epsilon \le 3/4$: the printed range $\epsilon \in (0, 3)$ (and $\epsilon \le 3$) is false, since the $\chi^2_n$ upper tail decays like $e^{-n(\epsilon - \ln(1+\epsilon))/2}$, slower than $e^{-\epsilon^2 n/6}$ for $\epsilon > 0.785$ (at $\epsilon = 2.9$ it fails for $n = 10$); the audit found this. Lemma 23.1 as printed, "every solution has orthonormal columns and $W = U^\top$", is false, since $(cU, W/c)$ has the same objective as $(U, W)$; the item states what the proof shows, that every $(U, W)$ is dominated by some $(V, V^\top)$ with $V^\top V = I$, which is all that (23.2) needs. Theorem 23.9 is stated with $n \ge 216\,s\log(72d/(\delta\epsilon))/\epsilon^2$: Lemma 23.12 with $\epsilon/3$ (so that $(1 \pm \epsilon/3)^2$ lies within $1 \pm \epsilon$) and $\delta/d^s$, followed by a union bound over the at most $d^s$ index sets, gives these constants, and the printed $100$ and $40$ are not reached by the argument. Theorem 23.8's proof assumes $d/s$ is an integer for simplicity; the statement is given without that assumption, since only the last block of the partition can be short and the block inequality still holds. Lemma 23.3 has $x \ne 0$, and the Johnson–Lindenstrauss lemma $n \ge 1$, since for $n = 0$ its $\epsilon$ is $0$ and the conclusion fails.

Not stated: §23.1.2 (implementation), Remarks 23.2–23.3, §23.4 (the comparison of PCA and compressed sensing), Exercises 1 and 3–6.

Selected references

• S. Shalev-Shwartz, S. Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, Chapter 23. doi:10.1017/CBO9781107298019
• W. B. Johnson, J. Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Contemporary Mathematics 26, 1984. doi:10.1090/conm/026/737400
• E. J. Candès, The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathématique 346(9–10), 2008. doi:10.1016/j.crma.2008.03.014
• R. Baraniuk, M. Davenport, R. DeVore, M. Wakin, A simple proof of the restricted isometry property for random matrices, Constructive Approximation 28, 2008. doi:10.1007/s00365-007-9003-x
• D. L. Donoho, Compressed sensing, IEEE Transactions on Information Theory 52(4), 2006. doi:10.1109/TIT.2006.871582
• E. J. Candès, T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory 51(12), 2005. doi:10.1109/TIT.2005.858979

Motivation

Lecture 5 of the Les Houches lectures on deep learning at large and infinite width (arXiv:2309.01592, Section 5, lectures by B. Hanin) shows that a random ReLU network evaluated at a single input can be solved exactly. The statistics of the network depend on depth $L$ and width $n$ through the inverse temperature $\beta = 5\sum_{\ell=1}^{L} 1/n_\ell \approx 5L/n$. The input–output Jacobian is the simplest quantity where this can be seen. Its second moment does not depend on depth or width. Its fourth moment grows like $e^{\beta}$, which gives a quantitative sense in which the regime where both $L$ and $n$ are large is controlled by $L/n$ rather than by $L$ or $n$ alone. The lectures derive this through a combinatorial sum-over-paths formalism developed in Hanin's earlier papers (references [20–22] of the notes).

Setting

Fix a depth $L\ge 1$ and widths $n_0,\dots,n_{L+1}\ge 1$. Let $\mu$ be a probability measure on $\mathbb R$ that has a density with respect to Lebesgue measure, is symmetric ($\mu(-A)=\mu(A)$), and has variance $\int t^2\,d\mu=1$. The weights are

$$W^{(\ell)}_{ij}=\Big(\tfrac{2}{n_{\ell-1}}\Big)^{1/2}\widehat W^{(\ell)}_{ij},\qquad \widehat W^{(\ell)}_{ij}\ \text{i.i.d.}\sim\mu,\qquad 1\le\ell\le L+1,$$

all biases are $0$, and the preactivations at an input $x\in\mathbb R^{n_0}$ are

$$z^{(1)}=W^{(1)}x,\qquad z^{(\ell+1)}=W^{(\ell+1)}\,\mathrm{ReLU}\big(z^{(\ell)}\big)\quad(1\le\ell\le L),\qquad \mathrm{ReLU}(t)=\max(t,0).$$

The network output is $z^{(L+1)}(x)\in\mathbb R^{n_{L+1}}$. The input–output Jacobian has entries $\partial z^{(L+1)}_q/\partial x_p$. A path is a tuple $\gamma=(\gamma(0),\dots,\gamma(L+1))$ with $\gamma(\ell)\in\{1,\dots,n_\ell\}$, and $\Gamma_{p,q}$ is the set of paths with $\gamma(0)=p$ and $\gamma(L+1)=q$. Along a path, $W^{(\ell)}_\gamma=W^{(\ell)}_{\gamma(\ell)\gamma(\ell-1)}$ and $\xi^{(\ell)}_{\gamma}=\mathbf 1\{z^{(\ell)}_{\gamma(\ell)}(x)>0\}$.

Formalization targets

Goal: second moment of the Jacobian (eq. (124))

For every fixed input $x\neq0$ and all $p,q$,

$$\mathbb E\Big[\Big(\frac{\partial z^{(L+1)}_q}{\partial x_p}\Big)^2\Big]=\frac{2}{n_0}.$$

Milestones

1. Eq. (123): the output is a sum over paths, $z^{(L+1)}_q=\sum_p x_p\sum_{\gamma\in\Gamma_{p,q}}\prod_{\ell=1}^{L+1}W^{(\ell)}_\gamma\prod_{\ell=1}^{L}\xi^{(\ell)}_\gamma$.
2. Proposition 5.2: at a fixed input $x\neq 0$, the output has the same law as the output $W^{(L+1)}D^{(L)}W^{(L)}\cdots D^{(1)}W^{(1)}x$ of a deep linear network with dropout. Here the $D^{(\ell)}$ are diagonal with i.i.d. Bernoulli$(1/2)$ entries, independent of the weights.
3. Section 5.4, first exercise: almost surely, $\partial z^{(L+1)}_q/\partial x_p=\sum_{\gamma\in\Gamma_{p,q}}\prod_\ell W^{(\ell)}_\gamma\prod_\ell\xi^{(\ell)}_\gamma$.
4. Section 5.4, first exercise (conclusion): the law of $\partial z^{(L+1)}_q/\partial x_p$ is the same for all $x\neq0$.
5. Section 5.5, fourth moment: $\mathbb E[(\partial z^{(L+1)}_q/\partial x_p)^4]=\frac{c}{n_0^2}\exp\big(5\sum_{\ell=1}^L\frac1{n_\ell}+O(L/n^2)\big)$. This is stated under the extra hypothesis $\int t^4\,d\mu=3$ (see Formalization scope).

Significance

Identity (124) says that, with the initialization $C_W=2$ and zero biases, the typical size of the input–output Jacobian does not depend on depth or width. This is the exact form of the "criticality" of ReLU at $C_W=2$. The fourth-moment statement shows that the fluctuations are not controlled in this way: they grow exponentially in $\beta\approx 5L/n$. Together with Proposition 5.2, these results turn questions about deep random ReLU networks at one input into questions about products of random matrices with dropout. As far as the drafter knows, these statements have not been machine-checked before. The mission asks for formal proofs of the lecture's exact identities.

Difficulty

The ReLU network is not a linear function of the weights. Its activation pattern $\xi^{(\ell)}$ depends on the weights of all earlier layers, so the path sum cannot be averaged term by term without first showing that the activation pattern is, in distribution, independent of the weights. That is the content of Proposition 5.2, which is argued only in sketch form in the notes. On top of that, the Jacobian must be identified with the path sum almost surely: at inputs where a preactivation vanishes the network is not differentiable. This requires the density assumption on $\mu$ and a separate treatment of layers in which every neuron is inactive.

Formalization scope

• Widths form a sequence n : ℕ → ℕ; only $n_0,\dots,n_{L+1}$ are used. The normalized weights are coordinates of the product measure $\mu^{\otimes}$ on a finite index set (weightLaw). The Bernoulli masks are coordinates of the uniform product measure on Bool (maskLaw).
• The Jacobian entry is the Fréchet derivative (fderiv) of $y\mapsto z^{(L+1)}_q(y)$ at $x$ applied to the $p$-th basis vector. Mathlib returns $0$ at points of non-differentiability, which form a null event for $x\neq0$.
• The notes write $W^{(\ell)}_\gamma=W^{(\ell)}_{\gamma(\ell-1)\gamma(\ell)}$. The formalization uses the orientation $W^{(\ell)}_{\gamma(\ell)\gamma(\ell-1)}$, which matches the row/column convention of the network recursion.
• Fourth moment. For a general $\mu$ the claim in §5.5 appears to need a correction. An informal computation (not part of this draft's verified content) gives a boundary term $2(\mu_4-3)(1/n_1+1/n_L)$ in the exponent, which is of order $1/n$ rather than $L/n^2$ unless $\mu_4=\int t^4d\mu=3$ (for example Gaussian $\mu$). The milestone is therefore stated under the extra hypothesis $\mu_4=3$. The constant $c>0$ and the $O(\cdot)$ constant may depend on $\mu$ only.
• An integral of a non-integrable function is $0$ in Mathlib. The goal therefore also asserts integrability of the squared Jacobian, because $2/n_0\neq0$.

Selected references

• Y. Bahri, B. Hanin, A. Brossollet, V. Erba, C. Keup, R. Pacelli, J. B. Simon, Les Houches Lectures on Deep Learning at Large & Infinite Width, 2023. arXiv:2309.01592
• B. Hanin, M. Nica, Products of Many Large Random Matrices and Gradients in Deep Neural Networks, Comm. Math. Phys., 2020. arXiv:1812.05994

Motivation

At infinite width a randomly initialized network is a Gaussian process (Mission I of this series). Real networks have finite width $n$, and the leading departure from Gaussianity is measured by the connected four-point function $\kappa_4$. It captures both correlations between neurons and non-Gaussian fluctuations. Lecture 4 of the Les Houches lectures (arXiv:2309.01592, lectures by B. Hanin) states the central finite-width result, Theorem 4.2: $\kappa_4$ is of order $1/n$ and obeys an explicit layer-to-layer recursion up to $O(n^{-2})$. At criticality this gives the effective depth $L/n$ as the parameter controlling finite-width effects. The result was first derived at a physics level of rigor by Yaida (2020) and in Roberts–Yaida–Hanin (2022), and later derived more mathematically by Hanin (reference [19] of the notes).

Setting

A network of depth $L$ with widths $n_0,\dots,n_{L+1}$ and nonlinearity $\sigma$ has preactivations $z^{(1)}=b^{(1)}+W^{(1)}x$ and $z^{(\ell+1)}=b^{(\ell+1)}+W^{(\ell+1)}\sigma(z^{(\ell)})$. The parameters are independent, with $W^{(\ell)}_{ij}\sim\mathcal N(0,C_W/n_{\ell-1})$ and $b^{(\ell)}_i\sim\mathcal N(0,C_b)$, where $C_b\ge0$ and $C_W>0$ (eqs. (118)–(119)). At a single input $x$, write $\langle f\rangle_K$ for the average of $f$ against $\mathcal N(0,K)$. The infinite-width kernel is $K^{(1)}=C_b+C_W|x|^2/n_0$ and $K^{(\ell+1)}=C_b+C_W\langle\sigma^2\rangle_{K^{(\ell)}}$ (eq. (120)). The parallel susceptibility is $\chi_\parallel^{(\ell)}=C_W\,\partial_K\langle\sigma^2\rangle_K|_{K=K^{(\ell)}}$. The normalized connected four-point function is

$$\kappa^{(\ell)}_4=\tfrac13\Big(\mathbb E\big[(z^{(\ell)}_i)^4\big]-3\,\mathbb E\big[(z^{(\ell)}_i)^2\big]^2\Big).$$

Formalization targets

Goal: Theorem 4.2, recursion for $\kappa_4$

If the hidden widths satisfy $n\le n_\ell\le An$, then $\kappa^{(\ell)}_4=O(n^{-1})$ and

$$\kappa^{(\ell+1)}_4=\frac{C_W^2}{n_\ell}\,\mathrm{Var}_{K^{(\ell)}}\big[\sigma^2\big]+\big(\chi^{(\ell)}_\parallel\big)^2\kappa^{(\ell)}_4+O(n^{-2}),$$

with constants independent of the widths.

Milestones

1. Proposition 4.3: $AW\sim\mathcal N(A\mu,A\Sigma A^{T})$ for $W\sim\mathcal N(\mu,\Sigma)$.
2. Lemma 4.4: conditional on $z^{(\ell)}$, the vector $z^{(\ell+1)}$ is Gaussian with covariance $\Sigma^{(\ell)}I$, where $\Sigma^{(\ell)}=C_b+\frac{C_W}{n_\ell}\sum_j\sigma(z^{(\ell)}_j)^2$; moreover $\kappa^{(\ell+1)}_4=\mathrm{Var}[\Sigma^{(\ell)}]$.
3. Section 4.8, exercise: $\kappa^{(\ell)}_4=\mathrm{Cov}\big((z^{(\ell)}_i)^2,(z^{(\ell)}_j)^2\big)$ for $i\neq j$.
4. Theorem 4.2, criticality (ReLU, $C_b=0$, $C_W=2$, uniform width): $\kappa^{(L+1)}_4/(K^{(L+1)})^2=C_\sigma L/n+O_L(n^{-2})$.
5. Theorem 4.2, expansion of observables: $\mathbb E f(z^{(\ell)}_1,\dots,z^{(\ell)}_m)=\langle f\rangle_{G^{(\ell)}}+\frac{\kappa^{(\ell)}_4}{8}\big\langle\big(\sum_j\partial_j^4+\sum_{j_1\neq j_2}\partial_{j_1}^2\partial_{j_2}^2\big)f\big\rangle_{K^{(\ell)}}+O(n^{-2})$.

Significance

Theorem 4.2 is the first quantitative statement that finite-width networks at initialization are not Gaussian processes. The size of the deviation is $1/n$ per layer, and it accumulates linearly in depth at criticality. This is the basis for the claim of Lecture 4 that $L/n$ controls correlations between neurons, fluctuations and, in later lectures, feature learning. As far as the drafter knows these statements have not been machine-checked. Lemma 4.4 and the covariance exercise are exact finite-width identities and are natural first targets.

Difficulty

The next layer is Gaussian only conditionally, with a random variance $\Sigma^{(\ell)}$ that is an average over $n_\ell$ dependent neurons. Establishing the recursion to order $n^{-2}$ requires expanding Gaussian averages around the mean of $\Sigma^{(\ell)}$ and controlling all higher cumulants of this collective observable uniformly in the widths. The nonlinearity is only assumed polynomially bounded, so smoothness must come from Gaussian averaging, not from $\sigma$.

Formalization scope

• Mission I's definitions (LesHouchesWidth_GaussianMLP: the network mlpZ, stdGaussianParams, nngpKernel, uniformWidths) are reused. Mission I must be launched first, and its definition then added to this proposal as a reference item.
• New definitions (LesHouchesWidth_FiniteWidth): gaussAvg, gaussAvgVec, gaussVarSq, chiParallel, PolyBounded, kappa4, dressedTwoPoint, collectiveSigma.
• "$n_1,\dots,n_L\simeq n$" is encoded as $n\le n_\ell\le An$ for a fixed $A\ge1$. The $O(\cdot)$ constants may depend on all fixed data ($C_b,C_W,\sigma,L,n_0,n_{L+1},x,A$, and $m,f$ where relevant) but not on $n$ or on the widths.
• "Reasonable" $\sigma$ is taken to mean measurable and polynomially bounded, and the kernel is assumed nondegenerate: $K^{(\ell)}>0$ for $1\le\ell\le L+1$, as the density-based definition of $\langle\cdot\rangle_K$ in Section 4.2 requires. "Reasonable" test functions $f$ are taken to be smooth with polynomially bounded derivatives of all orders.
• The expansion of observables is stated with $\kappa^{(\ell)}_4$ in front of the correction. The printed $\kappa^{(\ell+1)}_4$ appears to be an index slip: with $\kappa^{(\ell)}_4$ the formula reproduces $\mathbb E[z^4]=3G^2+3\kappa_4$ and $\mathbb E[z_1^2z_2^2]=G^2+\kappa_4$ exactly.
• The criticality statement is formalized for ReLU at $C_b=0$, $C_W=2$, the one critical example in the notes where $K^{(\ell)}$ is constant. For $\sigma=\tanh$ the notes' "$\simeq$" is asymptotic in depth and is not formalized here.

Selected references

• Y. Bahri, B. Hanin, A. Brossollet, V. Erba, C. Keup, R. Pacelli, J. B. Simon, Les Houches Lectures on Deep Learning at Large & Infinite Width, 2023. arXiv:2309.01592
• S. Yaida, Non-Gaussian processes and neural networks at finite widths, MSML 2020. arXiv:1910.00019
• D. A. Roberts, S. Yaida, B. Hanin, The Principles of Deep Learning Theory, Cambridge University Press, 2022. arXiv:2106.10165
• B. Hanin, Random Fully Connected Neural Networks as Perturbatively Solvable Hierarchies, 2022. arXiv:2204.01058

Motivation

A fully connected neural network with random Gaussian weights defines a random function of its input. Lecture 1 of the Les Houches lectures on deep learning at large and infinite width (arXiv:2309.01592, lectures by Y. Bahri) explains that, when the hidden layers become infinitely wide, this random function becomes a Gaussian process (the "neural network Gaussian process", NNGP). Its covariance kernel is computed by an explicit layer-to-layer recursion. The observation goes back to Neal (1996) for one hidden layer. It was extended to deep networks by Matthews et al. and Lee et al. (2018). It underlies Bayesian inference with infinitely wide networks (Section 1.6) and the analysis of signal propagation at large depth (Section 1.7). Lecture 2 introduces Wick's theorem, the tool for computing moments of Gaussian vectors that the lectures then use for finite-width corrections.

Setting

A network of depth $L$ with widths $n_0,\dots,n_{L+1}$ and nonlinearity $\varphi$ maps an input $x\in\mathbb R^{n_0}$ to preactivations

$$z^{(1)}_i=b^{(1)}_i+\sum_{j}W^{(1)}_{ij}x_j,\qquad z^{(\ell+1)}_i=b^{(\ell+1)}_i+\sum_{j}W^{(\ell+1)}_{ij}\,\varphi\big(z^{(\ell)}_j\big),$$

with independent $b^{(\ell)}_i\sim\mathcal N(0,\sigma_b^2)$ and $W^{(\ell)}_{ij}\sim\mathcal N(0,\sigma_w^2/n_{\ell-1})$ (eqs. (1)–(3) and (5); layers are indexed as in Lectures 4–5, so $z^{l}$ of Lecture 1 is $z^{(l+1)}$ here). For a $2\times2$ covariance $\Sigma$ write $F_\varphi(\Sigma_{11},\Sigma_{12},\Sigma_{22})=\mathbb E_{(u_1,u_2)\sim\mathcal N(0,\Sigma)}[\varphi(u_1)\varphi(u_2)]$ (eq. (15)). The NNGP kernel is

$$K^{(1)}(x,x')=\sigma_b^2+\sigma_w^2\,\frac{x\cdot x'}{n_0},\qquad K^{(\ell+1)}(x,x')=\sigma_b^2+\sigma_w^2F_\varphi\big(K^{(\ell)}(x,x),K^{(\ell)}(x,x'),K^{(\ell)}(x',x')\big).$$

A pairing of $\{1,\dots,2m\}$ is a partition into $m$ two-element blocks.

Formalization targets

Goal: Result 1 (single hidden layer)

For a network with one hidden layer of width $n$, fixed inputs $x_1,\dots,x_m$ and output width $n_2$, as $n\to\infty$ the vector $(z^{(2)}_i(x_a))_{i\le n_2,\,a\le m}$ converges in distribution to a centered Gaussian with covariance

$$\mathbb E\big[z^{(2)}_i(x_a)z^{(2)}_j(x_b)\big]\to\delta_{ij}K^{(2)}(x_a,x_b).$$

Milestones

1. Eq. (10): $\mathbb E[z^{(1)}_i(x)z^{(1)}_i(x')]=K^{(1)}(x,x')$.
2. Eqs. (9), (11): $\mathbb E[z^{(2)}_i(x)z^{(2)}_i(x')]=K^{(2)}(x,x')$ at every finite width.
3. Eq. (16): closed form of $F_{\mathrm{ReLU}}$ (the arc-cosine kernel).
4. Result 2 (Wick's theorem): $\mathbb E[z_{\mu_1}\cdots z_{\mu_{2m}}]=\sum_{\text{pairings}}\prod K_{\mu_k\mu_{k'}}$ for $z\sim\mathcal N(0,K)$, and odd moments vanish.

A further item states the deep version of the limit, eqs. (13)–(14), in the simultaneous-width limit. It is included as a supporting theorem rather than a milestone.

Significance

Result 1 and its deep extension identify the prior over functions induced by random initialization. They also make the NNGP kernel the central computational object of the infinite-width theory. The finite-width covariance identities (9)–(11) are exact and explain where the recursion comes from. Formula (16) makes the recursion explicit for ReLU. Wick's theorem is the basic tool of the finite-width perturbation theory of later lectures. These are classical results. The mission asks for their formal proofs against a single shared model of random networks that the later missions of this series reuse.

Difficulty

Result 1 is a multivariate central limit theorem for sums of $n$ i.i.d. vectors whose entries are products of a Gaussian weight and a nonlinear function of Gaussian first-layer preactivations. No assumption beyond square-integrability of $\varphi$ against the relevant Gaussians is imposed, so the CLT must be applied in its $L^2$ form. The deep limit is harder: for $L\ge2$ the hidden preactivations are not Gaussian at finite width, and one must control a triangular array in which the widths of all layers grow together. The ReLU formula (16) is an explicit but delicate Gaussian integral over a cone.

Formalization scope

• The parameters are coordinates of i.i.d. standard Gaussians (stdGaussianParams), scaled by $\sigma_b$ and $\sigma_w/\sqrt{n_{\ell-1}}$ (mlpBias, mlpWeight). This is equality in law with the prior (5).
• Bivariate Gaussian averages use Mathlib's multivariateGaussian. Convergence in distribution is stated with bounded continuous test functions: $\mathbb E\,g(Z_n)\to\int g\,d\mathcal N(0,C)$ for every bounded continuous $g$.
• The one-hidden-layer goal assumes only that $\varphi$ is measurable and that $\varphi^2$ is integrable against $\mathcal N(0,K^{(1)}(x_a,x_a))$ for each input. The deep statement assumes $\varphi$ continuous with a linear envelope $|\varphi(u)|\le c+M|u|$, the condition used by Matthews et al. (2018). The notes defer to the references for these conditions.
• Pairings are fixed-point-free involutions of $\{0,\dots,2m-1\}$.

Selected references

• Y. Bahri, B. Hanin, A. Brossollet, V. Erba, C. Keup, R. Pacelli, J. B. Simon, Les Houches Lectures on Deep Learning at Large & Infinite Width, 2023. arXiv:2309.01592
• R. M. Neal, Bayesian Learning for Neural Networks, Springer, 1996. doi:10.1007/978-1-4612-0745-0
• A. G. de G. Matthews, M. Rowland, J. Hron, R. E. Turner, Z. Ghahramani, Gaussian Process Behaviour in Wide Deep Neural Networks, ICLR 2018. arXiv:1804.11271
• Y. Cho, L. K. Saul, Kernel Methods for Deep Learning, NeurIPS 2009.

Motivation

Chapter 5 of Kearns and Vazirani, An Introduction to Computational Learning Theory (MIT Press, 1994, doi:10.7551/mitpress/3897.001.0001), asks what happens to PAC learning when the labels are unreliable. In the classification noise model of Angluin and Laird, each label returned by the oracle is flipped independently with a fixed probability $\eta < 1/2$. The algorithms of Chapter 1 collapse at once: the elimination algorithm deletes a correct literal on the strength of a single mislabeled example, and the tightest-fit rectangle may not exist. The chapter's remedy is to learn from statistics: an algorithm that forms its hypothesis only from estimates of probabilities of simple events is insensitive to occasional wrong labels. Kearns's statistical query model makes this precise, replacing the example oracle by an oracle that returns the probability of any predicate of a labeled example to within a tolerance, and the main theorem (5.3) shows that every class learnable from statistical queries is PAC learnable in the presence of classification noise. The proof rests on a single identity, Equation (5.2), that expresses the true value of a statistical query in terms of three quantities that can each be estimated from noisy examples, and on the observation that a hypothesis's disagreement with the noisy label is an affine function of its true error, which lets the best of several candidate hypotheses be recognized without clean data.

Setting

The framework is that of Mission I. The noisy example law is that of $(x, b)$ with $x \sim D$ and $b = c(x)$ flipped with probability $\eta$. A statistical query is a predicate $\chi$ of a labeled example with value $P_\chi = \Pr_{x \sim D}[\chi(x, c(x)) = 1]$. The inputs split into $X_1$, where the label matters to $\chi$, and $X_2$, where it does not; $p_1 = D(X_1)$ and $D_1$ is $D$ conditioned on $X_1$. For conjunctions over $\{0,1\}^n$, $p_0(z)$ is the probability that a literal $z$ is set to $0$ and $p_{01}(z)$ the probability that it is $0$ on a positive example; $z$ is significant if $p_0(z) \ge \epsilon/8n$ and harmful if $p_{01}(z) \ge \epsilon/8n$.

Formalization targets

Goal: Equation (5.2)

For $0 \le \eta < 1/2$ and every statistical query $\chi$,

$$P_\chi = p_1 \cdot \frac{\Pr_{EX^\eta_{CN}(c, D_1)}[\chi = 1] - \eta}{1 - 2\eta} + \Pr_{EX^\eta_{CN}(c, D)}[\chi = 1 \wedge x \in X_2],$$

the probabilities on the right being taken under the noisy oracle.

Milestones

The §5.2 analysis behind Theorem 5.2 (the conjunction of all significant, non-harmful literals has error at most $\epsilon/2$); the product estimate bound of p. 115 ($AB - 2\tau' \le \hat A\hat B \le AB + 3\tau'$); the identity of p. 117 ($\gamma_h = \eta + (1 - 2\eta)\,\mathrm{error}(h)$).

Significance

Equation (5.2) is the entire mechanism of noise-tolerant learning in the statistical query model: the noisy oracle cannot be de-noised example by example, but the probability of any predicate can be recovered exactly from noisy probabilities, because on the inputs where the label matters the noise acts as a known affine contraction and on the others it acts not at all. Together with the p. 117 identity, which turns hypothesis selection into a comparison of noisy disagreement rates, and the Chernoff bounds of Mission IV, it yields Theorem 5.3 and hence noise-tolerant algorithms for every class the book has learned so far (conjunctions, decision lists, $k$-CNF). The §5.2 analysis is the first statistical-query algorithm and shows the pattern: a hypothesis defined by thresholds on a few probabilities, with enough slack between the thresholds that estimates suffice. None of this is machine-checked. The formalization fixes the noisy example law on the platform's sample framework and proves the exact identities on which the noise-tolerant simulation depends.

Difficulty

Equation (5.2) is a computation with the pushforward of a product measure: one must express the noisy law on $X_1$ as a mixture of the clean law and its label-flipped image, solve the affine relation for the clean probability, and combine with the restriction to $X_2$, where the flipped and unflipped labels give the same value of $\chi$; the degenerate case $D(X_1) = 0$, in which the conditional measure is zero and the first term vanishes, must be handled separately. The p. 117 identity is the same computation without the split. The §5.2 analysis is two union bounds over the $2n$ literals after the observation that a literal of the target is never harmful and that a literal of the hypothesis is never insignificant. The product lemma is elementary arithmetic with a case split at $A < \tau'$.

Formalization scope

The noisy oracle is a measure on labeled examples obtained by mapping the product of $D$ and a Bernoulli($\eta$) coin; the conditional $D_1$ is Mathlib's conditional measure; queries are arbitrary measurable predicates of a labeled example, with no tolerance or query-count bookkeeping. Theorem 5.3 itself, the definitions of efficient learnability from statistical queries (Definition 14) and of efficient noisy PAC learnability (Definition 13), Theorem 5.1, Theorem 5.2 as a statement about an algorithm with oracle access, and Corollary 5.4 are not stated: they quantify over query algorithms and their running times, for which this series has no model; the mission carries their exact probabilistic content. The error-propagation analysis of §5.4.2–5.4.3 with tolerance $\tau/27$ and the guessing resolution $\Delta$ is not stated beyond the product lemma, since the factor $1/(1-2\eta)$ is not in $[0,1]$ and the book's constant does not account for it. Hypotheses: $0 \le \eta < 1/2$ for the decomposition, $0 \le \eta \le 1$ for the disagreement identity, $\epsilon > 0$ for the conjunction analysis, all reals in $[0,1]$ for the product lemma.

Trivializing readings are excluded: the decomposition is an exact identity for every measurable query, and the conjunction bound is for the exact thresholds $\epsilon/8n$ with the union bound's $\epsilon/2$. Welcome contributions: the mixture representation of the noisy law, the restriction of a pushforward to $X_2$, and the two union bounds.

Selected references

• M. J. Kearns, U. V. Vazirani, An Introduction to Computational Learning Theory, MIT Press, 1994, Chapter 5. doi:10.7551/mitpress/3897.001.0001
• D. Angluin, P. Laird, Learning from noisy examples, Machine Learning 2(4), 1988. doi:10.1007/BF00116829
• M. Kearns, Efficient noise-tolerant learning from statistical queries, Journal of the ACM 45(6), 1998. doi:10.1145/293347.293351
• M. Kearns, M. Li, Learning in the presence of malicious errors, SIAM Journal on Computing 22(4), 1993. doi:10.1137/0222052

Motivation

Chapter 4 of Kearns and Vazirani, An Introduction to Computational Learning Theory (MIT Press, 1994, doi:10.7551/mitpress/3897.001.0001), asks whether the PAC model's demand for arbitrarily small error and confidence is essential. A weak learning algorithm need only, with some fixed positive probability, output a hypothesis that beats random guessing by a fixed margin. Schapire's theorem, the chapter's main result, says that this apparently much weaker requirement is equivalent to the original one: any weak learner can be converted, by running it on carefully filtered distributions and combining its hypotheses by majority votes, into a strong learner. The construction is boosting, which became one of the most influential ideas in machine learning. The chapter proves the equivalence in two steps. Boosting the confidence is elementary: run the learner several times and validate. Boosting the accuracy is the substance: a modest procedure that combines three hypotheses, each with error at most $\beta$ on its own distribution, into a majority with error at most $g(\beta) = 3\beta^2 - 2\beta^3 < \beta$, applied recursively until the error is driven below the target. The Chernoff bounds of the Appendix, the book's workhorse for estimating probabilities from samples, are what makes the validation steps rigorous.

Setting

The framework is that of Mission I. A class $C$ is weakly learnable using $H$ if for some advantage $\gamma > 0$, confidence $\delta_0 > 0$ and sample size $m$, an algorithm outputs hypotheses in $H$ that, for every target in $C$ and every distribution, have error at most $1/2 - \gamma$ with probability at least $\delta_0$; the algorithm's prediction $L(S)(x)$ is a measurable function of the sample and the instance together, as it is for every algorithm. Given a hypothesis $h_1$, the filtered distribution $D_2$ gives weight $1/2$ to the instances on which $h_1$ errs and $1/2$ to those on which it is correct, preserving relative weights within each part, and $D_3$ is $D$ conditioned on $h_1 \ne h_2$; the modest procedure outputs $\mathrm{majority}(h_1, h_2, h_3)$. Ternary majority trees over $H$ are the closure of $H$ under the majority of three. For confidence boosting, $k$ independent samples yield $k$ hypotheses, and a fresh sample selects the one with the fewest mistakes. Bernoulli trials are $m$ independent coin flips with success probability $p$.

Formalization targets

Goal: Theorem 4.9

If $C$ is weakly PAC learnable using measurable hypotheses in $H$, then $C$ is PAC learnable using the class of ternary majority trees with leaves from $H$: for all $\epsilon, \delta \in (0, 1/2)$ some sample size and some algorithm outputting majority trees achieve error at most $\epsilon$ with probability at least $1 - \delta$, for every target in $C$ and every distribution.

Milestones

Theorem 9.2 (the additive and multiplicative Chernoff bounds); the two facts of §4.2 behind confidence boosting (independent runs all fail with probability at most $(1 - \delta_0)^k$; the fewest-mistakes selection loses at most $\gamma$ with probability at least $1 - 2k e^{-m\gamma^2/2}$); Lemma 4.1 (the modest procedure: error at most $g(\beta)$).

Significance

Theorem 4.9 is one of the landmark results of learning theory: it shows that the PAC model has no intermediate strength, that Occam learning, weak learning and strong learning coincide, and that the resources of a strong learner can be bounded polylogarithmically in $1/\epsilon$ in memory and hypothesis size. Its constructive proof is the first boosting algorithm, ancestor of AdaBoost and of gradient boosting. Lemma 4.1 is the analytic core, a clean inequality about three hypotheses and three distributions in which the filtered distribution is exactly calibrated so that $h_1$ has no advantage on it. The Chernoff bounds are the concentration inequalities invoked throughout the book, and their formalization on the product law of Bernoulli trials makes every later "estimate to within $\gamma$ with confidence $1 - \delta$" step reusable. None of these is machine-checked in this form; the boosting theorem in the sample-complexity sense is, to our knowledge, not formalized anywhere.

Difficulty

Lemma 4.1 is a computation with conditional measures: writing $\mathrm{error}_D$ of the majority as the weight of the instances on which $h_1$ and $h_2$ both err plus $\beta_3$ times the weight of their disagreement, mapping weights under $D_2$ back to $D$ by the factors $2(1 - \beta_1)$ and $2\beta_1$ (Equation (4.1)), and maximizing the resulting polynomial in $\beta_1, \beta_2, \beta_3, \gamma_1, \gamma_2$; the degenerate cases where a conditioning event is null must be handled separately. The Chernoff bounds require the exponential moment method on a finite product measure. The confidence-boosting facts are the product bound for independent blocks and Hoeffding plus a union bound. The goal is a genuine construction: from a large sample of $D$ one must simulate the recursive algorithm Strong-Learn, whose calls to the weak learner on filtered distributions are served by rejection sampling from the remaining examples, bound the depth of the recursion by the growth of $g^{-1}$ iterates (Lemma 4.2), bound the number of examples consumed at each node (Lemmas 4.3–4.7) and allocate the confidence over all the places the simulation can fail; then package the result as a deterministic function of a sample of fixed size. An alternative route is available: weak learnability with a fixed sample size forces a finite VC dimension (a class shattering a large set defeats any fixed-size learner on the uniform distribution over it), after which Theorem 3.3 gives a consistent strong learner; but its hypotheses lie in $C$, not in the majority trees over $H$, so it does not prove the stated conclusion.

Formalization scope

The weak-learning hypothesis is the book's with constants $\gamma, \delta_0$ in place of the inverse polynomials, which is what the definition says for a fixed class; hypotheses in $H$ are required to be measurable, and the weak learner jointly measurable in the sample and the instance, because Strong-Learn runs it on distributions filtered through its own earlier outputs and the analysis integrates over the earlier samples (for an arbitrary function the combined failure event need not be measurable, and outer-measure bounds on separate runs do not combine); the conclusion is the book's hypothesis class, the majority trees over $H$, built as an inductive predicate. Filtered distributions use Mathlib's conditional measure, so that a null conditioning event yields the zero measure; Lemma 4.1 is stated for $0 \le \beta \le 1/2$ and holds in those degenerate cases too. The confidence-boosting milestone states the two probabilistic facts rather than the composite algorithm, whose sample indexing across runs and validation is bookkeeping; the selection rule is any rule minimizing mistakes. Chernoff's bounds are stated with non-strict inequalities in the events, for $0 \le p \le 1$ and $0 < \gamma \le 1$. Running time, the recursion-depth and sample-size lemmas with unspecified constants (4.2–4.8), and Exercises 4.1–4.3 are not stated.

Trivializing readings are excluded: the weak-learning guarantee is uniform over all targets and distributions with an advantage strictly positive, the strong conclusion is for every $\epsilon, \delta$, and Lemma 4.1 requires all three error bounds on their respective distributions. Welcome contributions: Lemma 4.1 itself, the Hoeffding bound on the product law, and the rejection-sampling lemma that turns a sample of $D$ into a sample of a filtered distribution.

Selected references

• M. J. Kearns, U. V. Vazirani, An Introduction to Computational Learning Theory, MIT Press, 1994, Chapter 4 and Chapter 9. doi:10.7551/mitpress/3897.001.0001
• R. E. Schapire, The strength of weak learnability, Machine Learning 5(2), 1990. doi:10.1007/BF00116037
• Y. Freund, Boosting a weak learning algorithm by majority, Information and Computation 121(2), 1995. doi:10.1006/inco.1995.1136
• W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58(301), 1963. doi:10.1080/01621459.1963.10500830
• H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Annals of Mathematical Statistics 23(4), 1952. doi:10.1214/aoms/1177729330

Motivation

The bandit processes that motivated the index theorem are sampling processes: an arm is a population from which one draws i.i.d. observations whose distribution has an unknown parameter, and each draw both earns something and teaches something. Chapter 7 of Gittins, Glazebrook and Weber, Multi-armed Bandit Allocation Indices (2nd ed., doi:10.1002/9780470980033), develops the theory of such processes in the Bayesian setting: the state of the process is the current posterior for the parameter, continuing it samples the next value from the predictive distribution and moves to the new posterior. When the observations are themselves the rewards one has a reward process, the classical Bayesian multi-armed bandit; when the aim is to find as quickly as possible an individual whose measurement reaches a target $T$ (a compound active enough to warrant further testing, in the drug-screening problem from which the index theorem came) one has a target process, which is a job that completes when the target is reached. Two questions organize the chapter. When can the index be written down without any optimization, and when do symmetries of the model reduce the index to a function of fewer variables? The first is answered by the notion of a favourable prior (Section 7.3): if no run of observations below the target can raise the current probability of success, then the index is that probability, exactly, by Proposition 2.7. The second is answered by the invariance theorems of Section 7.4: a location parameter with a conjugate prior gives $\nu(\bar x, n) = \bar x + \nu(0, n)$, a scale parameter gives $\nu(\bar x, n) = \bar x\,\nu(1, n)$, and for target processes the target can be absorbed into the state, $\nu(\bar x, n, T) = \nu(\bar x - T, n, 0)$. These identities are what make the tables of Chapter 8 one-dimensional.

Setting

A sampling model consists of a likelihood $f(\cdot \mid \theta)$, a family of priors $\pi(\cdot \mid p)$ on the parameter indexed by the parameters $p$ of a conjugate family, and the Bayes update $p \mapsto p_x$ of those parameters after observing $x$; the family is conjugate if the posterior of $\pi(\cdot \mid p)$ given $X = x$ is $\pi(\cdot \mid p_x)$. The predictive distribution is $f(\cdot \mid p) = \int f(\cdot \mid \theta)\pi(d\theta \mid p)$. The reward process moves from $p$ to $p_x$ with $x \sim f(\cdot \mid p)$ and earns $r(p) = \int x f(x \mid p)dx$. The target process with target $T$ moves to the completion state $C$ if $x \ge T$ and to $p_x$ otherwise, earning the current probability of success $r(p) = f([T, \infty) \mid p)$, and $0$ in $C$. A state $p$ is favourable if $r(p_{x_1 \cdots x_m}) \le r(p)$ for every finite sequence of observations $x_i < T$. For the invariance theorems the parameters are $(\bar x, n)$ with the update $((n\bar x + x)/(n+1), n+1)$; $\mu$ is a location parameter of the likelihood if $f(\cdot \mid \mu + c)$ is $f(\cdot \mid \mu)$ shifted by $c$, and $\bar x$ is a location parameter of the prior family if $\pi(\cdot \mid \bar x + c, n)$ is $\pi(\cdot \mid \bar x, n)$ shifted by $c$; scale parameters are defined with $x \mapsto bx$, $b > 0$. The Gittins index is that of the Bandit Algorithms model on these chains.

Formalization targets

Goal: Theorem 7.9 (in the form of Corollary 7.10)

If $\mu$ is a location parameter of a reward process with a conjugate prior family in which $\bar x$ is a location parameter and the parameters update as the sample mean and count, then for every $n > 0$

$$r(\bar x + c, n) = r(\bar x, n) + c \quad\text{and}\quad \nu(\bar x, n) = \bar x + \nu(0, n),$$

under the standing assumptions that the observations have a mean and the discounted rewards of the chain are integrable.

Milestones

Proposition 7.4 (favourable state: $\nu = r$); Example 7.5 (Bernoulli target process, $\nu(\alpha, \beta) = \alpha/(\alpha + \beta)$); Example 7.6 (normal target process with known variance, $\nu(\bar x, n) = \Phi(\bar x (1 + n^{-1})^{-1/2})$ for $\bar x \ge 0$); Theorem 7.11 (scale parameter: $\nu(\bar x, n) = \bar x\,\nu(1, n)$); Theorem 7.17 (target process with a location parameter: $\nu(\bar x, n, T) = \nu(\bar x - T, n, 0)$).

Significance

Theorem 7.9 and its companions are the reason the Gittins index of the normal reward process is tabulated as a function of $n$ alone and that of the exponential process as a function of $n$ and one ratio; every computational method of Chapter 8 starts by reducing the state space with them. Proposition 7.4 is the source of every closed-form index in the book: it identifies the states in which sampling for information is worthless, so that the index collapses to the immediate expected reward, and Examples 7.5 and 7.6 show that for the Bernoulli target process this is every state and for the normal target process every state with a nonnegative posterior mean. The formalization gives the platform its first Bayesian sampling-process model, in which the state is a posterior and conjugacy is stated through the posterior kernel of the likelihood, and its first index identities on unbounded-reward chains, which is where the integrability assumptions of the Bandit Algorithms model do real work.

None of this is machine-checked. The invariance theorems are stated in the proper-prior form of the corollaries, with the model's symmetry as hypotheses, so that they apply to any conjugate family with the stated structure rather than to a particular density.

Difficulty

The invariance theorems require showing that the chain of parameters from the shifted (scaled) state is the image of the chain from the original state under the shift (scaling) of trajectories, which is an equivariance of the Ionescu–Tulcea construction with respect to a measurable bijection commuting with the kernel; that stopping times are carried to stopping times; that the discounted reward of a stopping time shifts by $c$ times the discounted time; and that the supremum of a nonempty bounded set of reals shifts and scales accordingly. Boundedness of the set of ratios is where the integrability assumption enters. Proposition 7.4 is the chain-level statement that all rewards along every trajectory from a favourable state are at most $r(p)$, which needs an induction on the trajectory law of the target chain, followed by the argument of Proposition 2.7. Example 7.6 needs the monotonicity of $\bar x_m (1 + 1/(n+m))^{-1/2}$ in the observations below the target, a small inequality, plus the Gaussian probability of a half-line as the current probability of success; Example 7.5 needs only that $\alpha/(\alpha + \beta + m)$ decreases.

Formalization scope

The sampling model is a structure with Markov likelihood and prior kernels and a jointly measurable update; the predictive distribution is the kernel composition; conjugacy is an almost-everywhere identity between Mathlib's posterior of the likelihood with respect to the prior and the prior at the updated parameters, and is carried as a hypothesis of the invariance theorems and of Proposition 7.4 so that their subject is the Bayesian process. For the parameters $(\bar x, n)$ it is required on $n > 0$ only (IsConjugateOn): a proper prior has $n > 0$, and conjugacy at every $(\bar x, n) \in \mathbb{R}^2$ is impossible with a location parameter, since at $n = -1$ the update divides by zero and sends every observation to one state, which made the first draft's location theorems vacuous. The chains are built with Kernel.map of product kernels, so their measurability is structural, and the target process lives on P ⊕ Unit with the completion state absorbing. The book's improper priors are replaced by proper conjugate families with the location or scale structure of Corollaries 7.10 and 7.12, as those corollaries do; the discrete-time correction factor of Section 2.8 is not applied since it cancels in every identity stated. The two examples are built directly from a uniform or Gaussian seed with the transition probabilities the book computes (the beta and normal posterior computations of Exercise 7.1 are not formalized). Hypotheses: $a \in (0, 1)$; integrable observations and L&S Assumption 35.6 for the reward processes; $n > 0$ for the invariance theorems and $\bar x > 0$ for the scale theorem; $\alpha, \beta > 0$; $\bar x \ge 0$ and $n > 0$ for the normal example.

Trivializing readings are excluded: the indices are the genuine suprema of the Bandit Algorithms definition with integrable rewards, the update rule is the book's and not a free parameter, and the favourability condition ranges over all finite observation sequences. Welcome contributions: the equivariance of the trajectory measure under a state bijection commuting with the kernel, the transport of stopping times, and the reward bound along the target chain from a favourable state.

Selected references

• J. Gittins, K. Glazebrook, R. Weber, Multi-armed Bandit Allocation Indices, 2nd ed., Wiley, 2011, Chapter 7. doi:10.1002/9780470980033
• J. C. Gittins, D. M. Jones, A dynamic allocation index for the sequential design of experiments, in Progress in Statistics (J. Gani, ed.), North-Holland, 1974.
• D. M. Jones, Search Procedures for Industrial Chemical Research, PhD thesis, University of Wales, 1975.
• H. Raiffa, R. Schlaifer, Applied Statistical Decision Theory, Harvard University Press, 1961.
• T. S. Ferguson, Mathematical Statistics: A Decision Theoretic Approach, Academic Press, 1967.
• T. Lattimore, C. Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Chapters 34–35. doi:10.1017/9781108571401