Proof of Theorem 11: the replace-one term is at most $\beta_1 + \beta_2$

Let $D$ be a probability distribution on $Z = X \times Y$, let the cost satisfy $0 \le c(y', y) \le M$, and let $A$ be a symmetric deterministic learning algorithm whose losses are measurable. Suppose that, at sample size $m$, $A$ has hypothesis stability $\beta_1$ (Definition 3) and pointwise hypothesis stability $\beta_2$ (Definition 4). Let $S = (z_1, \dots, z_m) \sim D^m$, let $z'_i \sim D$ be independent of $S$, and let $S^i$ be $S$ with $z_i$ replaced by $z'_i$. Then for every index $i$,

This converts the replace-one quantity in Lemma 9, eq. (8), into the two remove-one stability notions of the paper.

Formalization Note The paper prints the bound $2\beta_2$. Its argument splits the quantity, by the triangle inequality, into $\mathbb E_S[|\ell(A_S,z_i) - \ell(A_{S^{\setminus i}},z_i)|] \le \beta_2$ and $\mathbb E_{S,z'_i}[|\ell(A_{S^{\setminus i}},z_i) - \ell(A_{S^i},z_i)|]$. In the second term $z_i$ is not in $S^i$ and $(S^i)^{\setminus i} = S^{\setminus i}$, so it is an instance of Definition 3 and is bounded by $\beta_1$, not $\beta_2$. The statement here is the bound the argument proves; it agrees with the printed one when $\beta_1 = \beta_2$. Expectation over $(S, z'_i)$ is the integral against $D^m \otimes D$.