Theorem 1: a $(K,\epsilon(\cdot))$-robust algorithm has $|\mathcal L(\mathcal A_s) - l_{\mathrm{emp}}(\mathcal A_s)| \le \epsilon(s) + M\sqrt{(2K\ln 2 + 2\ln(1/\delta))/n}$ w.p. $\ge 1-\delta$

Let $\mu$ be a probability measure on a measurable space $\mathcal Z$, $\mathcal H$ a set of hypotheses and $l : \mathcal H \times \mathcal Z \to \mathbb R$ a loss with $0 \le l(h,z) \le M$ for all $h, z$ and $l(h, \cdot)$ measurable for every $h$. Let $n \ge 1$ and let $\mathcal A : \mathcal Z^n \to \mathcal H$ be a learning algorithm that is $(K, \epsilon(\cdot))$-robust (Definition 2). Let the training set $\mathbf s$ consist of $n$ i.i.d. draws from $\mu$. Then for every $\delta > 0$, with probability at least $1 - \delta$,

where $\mathcal L(\mathcal A_{\mathbf s}) = \mathbb E_{z\sim\mu}\, l(\mathcal A_{\mathbf s}, z)$ is the expected error and $l_{\mathrm{emp}}(\mathcal A_{\mathbf s}) = \frac1n\sum_{i=1}^n l(\mathcal A_{\mathbf s}, s_i)$ the training error.

This is the main generalization bound of Xu and Mannor's robustness framework: an algorithm whose loss varies by at most $\epsilon(\mathbf s)$ within each cell of a fixed partition of the sample space into $K$ cells generalizes, with a complexity term depending only on $K$ and not on the hypothesis class.

Formalization Note "With probability at least $1-\delta$" is stated as: the outer measure under $\mu^n$ (on Fin n → Z) of the set of training sets violating the inequality is at most $\delta$; this requires no measurability of $\mathbf s \mapsto \mathcal A_{\mathbf s}$. Measurability of $l(h,\cdot)$ and of the partition cells is added to the paper's model, which ignores measurability. $n \ge 1$ is assumed (the paper's "n IID draws"); at $n = 0$ Lean's $1/0 = 0$ would make the claim false. For $\delta > 2^K$ the radicand is negative and the square root is $0$; the statement stays true there.