Uniform algorithmic stability under deletion

Let $\mathcal{Z}$ be an observation set, let $\mathcal{H}$ be a set of hypotheses, and let $L:\mathcal{H}\times \mathcal{Z}\to [0,\mathrm{\infty })$ be a loss. A deterministic size-indexed learning rule consists, for every integer $n\ge 1$ and every retained index set $J\subseteq [n]$, of a map $A_{n,J}$ from the indexed observations $(z_j{)}_{j\in J}$ to $\mathcal{H}$; the original sample size $n$ remains an input to this rule. For $S=(z_1,\dots ,z_n)$ write $A_S:=A_{n,[n]}(S)$ and $A_{S\setminus i}:=A_{n,[n]\setminus \{i\}}(S{\mathrm{\mid }}_{[n]\setminus \{i\}})$ for the output after deleting indexed observation $i$. The rule is permutation-invariant if simultaneous reordering of the observations and relabeling of their retained indices leaves each output unchanged. Given a nonnegative sequence $({\beta }_n{)}_{n\ge 1}$, the rule has uniform deletion stability with coefficients $({\beta }_n)$ if, for every $n\ge 1$, every $S\in {\mathcal{Z}}^n$, every $i\in [n]$, and every $z\in \mathcal{Z}$,

$$\mathrm{\mid }L(A_S,z)-L(A_{S\setminus i},z)\mathrm{\mid }\le {\beta }_n\mathrm{.}$$

The sequence is nonincreasing when ${\beta }_{n+1}\le {\beta }_n$ for every $n\ge 1$. This is the deletion convention. If $S^{\mathrm{\prime }}$ differs from $S$ only at coordinate $i$, then $S\setminus i=S^{\mathrm{\prime }}\setminus i$, and the triangle inequality gives $\mathrm{\mid }L(A_S,z)-L(A_{S^{\mathrm{\prime }}},z)\mathrm{\mid }\le 2{\beta }_n$ for every $z$; the resulting replacement bound has coefficient $2{\beta }_n$.

Bousquet and Elisseeff, Definition 6 and the following inequality, printed p. 504, define uniform stability by deleting one indexed observation and state the coefficient-$2{\beta }_n$ replacement consequence. Full JMLR paper PDF

Mohri, Rostamizadeh, and Talwalkar, Definition 14.1, use a replacement-sample convention. Full second-edition book PDF