Theorem 8 — a learning method generalizes w.r.t. $\mathbf s^*$ iff it is weakly robust w.r.t. $\mathbf s^*$

Let $\mathcal Z$ be a measurable space of samples with a probability measure $\mu$, $\mathcal H$ a set of hypotheses, and $l : \mathcal H \times \mathcal Z \to [0, M]$ a loss that is non-negative, bounded by $M$ and measurable in its sample argument. Let $\mathcal A = \{\mathcal A^n\}_{n \in \mathbb N}$, $\mathcal A^n : \mathcal Z^n \to \mathcal H$, be a learning method, and fix a sequence of training samples $\mathbf s^* = (s^*_1, s^*_2, \dots)$. Then

that is, $\lim_n |\mathcal L(\mathcal A_{\mathbf s^*(n)}) - L(\mathcal A_{\mathbf s^*(n)}, \mathbf s^*(n))| = 0$ if and only if there are sets $\mathcal D_n \subseteq \mathcal Z^n$ with $\Pr_{\mathbf t(n) \sim \mu^n}(\mathbf t(n) \in \mathcal D_n) \to 1$ on which the average loss of $\mathcal A_{\mathbf s^*(n)}$ is uniformly within $o(1)$ of its training average loss.

The theorem says that a (weak) form of robustness is not only sufficient but also necessary for generalization: this is the sense in which Xu and Mannor call robustness an essential property of successful learning.

Formalization Note The training sequence is fixed and deterministic; all probabilities are over the test sample $\mathbf t(n) \sim \mu^n$, the product measure Measure.pi (fun _ : Fin n => μ). The standing assumption of the paper (Sect. 1.1) that $0 \le l \le M$ is a hypothesis; measurability of $l(h, \cdot)$, which the paper ignores, is added. See the definitions for the encoding of Eq. (6).