Theorem 11: polynomial generalization bounds from hypothesis stability

Let $D$ be a probability distribution on $Z = X \times Y$ and let the cost function satisfy $0 \le c(y', y) \le M$. Let $A$ be a symmetric deterministic learning algorithm whose losses are measurable, and suppose that at sample size $m \ge 1$ it has hypothesis stability $\beta_1$ (Definition 3) and pointwise hypothesis stability $\beta_2$ (Definition 4). Draw the training set $S \sim D^m$. Then for every $\delta > 0$, with probability at least $1 - \delta$,

and, with probability at least $1 - \delta$,

Here $R$ is the generalization error, $R_{\mathrm{emp}}$ the empirical error and $R_{\mathrm{loo}}$ the leave-one-out error of $A_S$. The theorem shows that the two classical estimators of the risk deviate from it by $O(1/\sqrt{m\delta})$ whenever the algorithm's stability decays like $1/m$, without any capacity measure of the hypothesis space.

Formalization Note The two bounds are stated separately: the probability, under $D^m$, of the failure event $\{R > R_{\mathrm{emp}} + \cdots\}$ is at most $\delta$, and likewise for $R_{\mathrm{loo}}$. The paper prints the empirical bound with $12Mm\beta_2$ in place of $6Mm(\beta_1+\beta_2)$. Its proof bounds the replace-one term of Lemma 9, eq. (8), by $2\beta_2$, but one of the two summands is a hypothesis-stability term bounded by $\beta_1$; the bound the proof establishes is the one stated here, which coincides with the printed one when $\beta_1 = \beta_2$. The leave-one-out bound is as printed. The sample size is $m \ge 1$ (a training set has at least one point; at $m = 0$ the stability hypotheses are vacuous and the statement fails). The paper's proof goes through Lemmas 9 and 25, which need two distinct indices; at $m = 1$ the bounds still hold, by comparing $A_S$ with $A_\emptyset$ directly, so no restriction $m \ge 2$ is imposed.