Algorithmic stability and generalization

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}$,

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

Let $(\mathsf{X},{\mathrm{\Sigma }}_X)$ and $(\mathsf{Y},{\mathrm{\Sigma }}_Y)$ be nonempty measurable instance and label spaces, and equip $\mathsf{Z}=\mathsf{X}\times \mathsf{Y}$ with ${\mathrm{\Sigma }}_Z={\mathrm{\Sigma }}_X\otimes {\mathrm{\Sigma }}_Y$. Let $P$ be a probability measure on $(\mathsf{Z},{\mathrm{\Sigma }}_Z)$, let $\mathcal{F}$ be a nonempty class of measurable functions $f:(\mathsf{X},{\mathrm{\Sigma }}_X)\to (\mathbb{R},\mathcal{B}(\mathbb{R}))$, and let $\mathrm{\ell }:\mathbb{R}\times \mathsf{Y}\to [0,\mathrm{\infty })$ be measurable with respect to $\mathcal{B}(\mathbb{R})\otimes {\mathrm{\Sigma }}_Y$. For $f\in \mathcal{F}$ and $z=(x,y)$ write $L_f(z)=\mathrm{\ell }(f(x),y)$, $R_P(f)={\int }_{\mathsf{Z}}{L}_f(z)P(dz)$, and ${\widehat{R}}_S(f)=m^{-1}{\sum }_{i=1}^m{L}_f(Z_i)$. Let $S=(Z_1,\dots ,Z_m)$ have product law $P^m$ on $({\mathsf{Z}}^m,{\mathrm{\Sigma }}_Z^{\otimes m})$, with $m\ge 1$, and let $A$ be a deterministic, permutation-invariant size-indexed learning rule that outputs members of $\mathcal{F}$ and assume the maps $(S,z)\mapsto L_{A_S}(z)$ and $(S,z)\mapsto L_{A_{S\setminus i}}(z)$ for every $i\in [m]$ are jointly measurable with respect to ${\mathrm{\Sigma }}_Z^{\otimes m}\otimes {\mathrm{\Sigma }}_Z$. Assume also that the sample-dependent risk, empirical-risk, and leave-one-out maps in the conclusions are measurable. Assume $0\le L_{A_T}(z)\le M<\mathrm{\infty }$ for every full or deleted sample $T$ and every $z\in \mathsf{Z}$, and assume $A$ has uniform deletion stability with a finite nonincreasing sequence $({\beta }_n{)}_{n\ge 1}$. Define $R_{\mathrm{l}\mathrm{o}\mathrm{o}}(A,S)=m^{-1}{\sum }_{i=1}^m{L}_{A_{S\setminus i}}(Z_i)$, using the size-$m$ deletion output. Then

${\mathbb{E}}_{S\sim P^m}[R_P(A_S)-{\widehat{R}}_S(A_S)]\le 2{\beta }_m\text{and}{\mathbb{E}}_{S\sim P^m}[R_P(A_S)-R_{\mathrm{l}\mathrm{o}\mathrm{o}}(A,S)]\le {\beta }_m\mathrm{.}$

Moreover, for every sample $S$ and index $i\in [m]$,

$\mathrm{\mid }{R}_P(A_S)-R_P(A_{S\setminus i})\mathrm{\mid }\le {\beta }_m\mathrm{.}$

All three conclusions are choice-free.

Bousquet and Elisseeff, Lemma 7 and proof, printed pp. 504–505, give the expected generalization and leave-one-out identities under the deletion convention. Full JMLR paper PDF

Mohri, Rostamizadeh, and Talwalkar, Theorem 14.2 and complete proof, printed pp. 334–336, give the corresponding replacement-stability argument. Full second-edition book PDF

Assume the Axiom of Choice. Let $(\mathsf{X},{\mathrm{\Sigma }}_X)$ and $(\mathsf{Y},{\mathrm{\Sigma }}_Y)$ be nonempty measurable instance and label spaces, and equip $\mathsf{Z}=\mathsf{X}\times \mathsf{Y}$ with ${\mathrm{\Sigma }}_Z={\mathrm{\Sigma }}_X\otimes {\mathrm{\Sigma }}_Y$. Let $P$ be a probability measure on $(\mathsf{Z},{\mathrm{\Sigma }}_Z)$, let $\mathcal{F}$ be a nonempty class of measurable functions $f:(\mathsf{X},{\mathrm{\Sigma }}_X)\to (\mathbb{R},\mathcal{B}(\mathbb{R}))$, and let $\mathrm{\ell }:\mathbb{R}\times \mathsf{Y}\to [0,\mathrm{\infty })$ be measurable with respect to $\mathcal{B}(\mathbb{R})\otimes {\mathrm{\Sigma }}_Y$. For $f\in \mathcal{F}$ and $z=(x,y)$ write $L_f(z)=\mathrm{\ell }(f(x),y)$, $R_P(f)={\int }_{\mathsf{Z}}{L}_f(z)P(dz)$, and ${\widehat{R}}_S(f)=m^{-1}{\sum }_{i=1}^m{L}_f(Z_i)$. Let $S=(Z_1,\dots ,Z_m)$ have product law $P^m$ on $({\mathsf{Z}}^m,{\mathrm{\Sigma }}_Z^{\otimes m})$, with $m\ge 1$, and let $A$ be a deterministic, permutation-invariant size-indexed learning rule that outputs members of $\mathcal{F}$ and has a nonincreasing uniform deletion-stability sequence $({\beta }_n{)}_{n\ge 1}$. Assume the maps $(S,z)\mapsto L_{A_S}(z)$ and $(S,z)\mapsto L_{A_{S\setminus i}}(z)$ for every $i\in [m]$ are jointly measurable on the sample/test product space, and all sample-dependent risk, empirical-risk, and leave-one-out maps in the conclusions are measurable, and assume $0\le L_{A_T}(z)\le M<\mathrm{\infty }$ for every full or deleted sample $T$ and every $z\in \mathsf{Z}$. Define $R_{\mathrm{l}\mathrm{o}\mathrm{o}}(A,S)=m^{-1}{\sum }_{i=1}^m{L}_{A_{S\setminus i}}(Z_i)$ using the size-$m$ deletion output. For each $\delta \in (0,1)$, the following two bounds hold separately, each with probability at least $1-\delta$ over $S\sim P^m$:

$R_P(A_S)\le {\widehat{R}}_S(A_S)+2{\beta }_m+(4m{\beta }_m+M)\sqrt{\frac{\log (1\mathrm{/}\delta )}{2m}},$

$R_P(A_S)\le R_{\mathrm{l}\mathrm{o}\mathrm{o}}(A,S)+{\beta }_m+(4m{\beta }_m+M)\sqrt{\frac{\log (1\mathrm{/}\delta )}{2m}}\mathrm{.}$

The displayed probability guarantees are separate and need not hold on the same event.

The natural logarithm in the confidence terms is defined by The natural logarithm as the inverse of the exponential function.

Its positivity on arguments greater than $1$ follows from Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm.

Bousquet and Elisseeff, Theorem 12 and full proof, printed pp. 507–509, give these two separate bounds under deletion stability. Full JMLR paper PDF

Mohri, Rostamizadeh, and Talwalkar, Theorem 14.2 and complete proof, printed pp. 334–336, give the corresponding replacement-stability bound. Full second-edition book PDF

Let $(\mathsf{X},{\mathrm{\Sigma }}_X)$ and $(\mathsf{Y},{\mathrm{\Sigma }}_Y)$ be nonempty measurable instance and label spaces. Let $\kappa \ge 0$, and let $\mathcal{H}$ be a real Hilbert space of ${\mathrm{\Sigma }}_X$-measurable real-valued functions on $\mathsf{X}$ with kernel sections $K_x\in \mathcal{H}$ satisfying $f(x)=⟨f,K_x{⟩}_{\mathcal{H}}$ and $\mathrm{\parallel }{K}_x{\mathrm{\parallel }}_{\mathcal{H}}^2=K(x,x)\le {\kappa }^2$ for every $x\in \mathsf{X}$. Let $\lambda >0$ and $\sigma \ge 0$, and let $c:\mathbb{R}\times \mathsf{Y}\to [0,\mathrm{\infty })$ be measurable with respect to $\mathcal{B}(\mathbb{R})\otimes {\mathrm{\Sigma }}_Y$, convex in its first argument, and $\sigma$-Lipschitz there, meaning $\mathrm{\mid }c(u,y)-c(v,y)\mathrm{\mid }\le \sigma \mathrm{\mid }u-v\mathrm{\mid }$ for all $u,v\in \mathbb{R}$ and $y\in \mathsf{Y}$. For every $n\ge 1$, every indexed sample $S=((x_1,y_1),\dots ,(x_n,y_n))$, and every retained index set $J\subseteq [n]$, define $A_{n,J}$ as the unique attained minimizer over $f\in \mathcal{H}$ of

Assume every such minimum is attained. For a size-$m$ sample, write $A_S:=A_{m,[m]}(S)$ and $A_{S\setminus i}:=A_{m,[m]\setminus \{i\}}(S{\mathrm{\mid }}_{[m]\setminus \{i\}})$, so the deleted objective retains the original denominator $m$. Then the resulting size-indexed rule is permutation-invariant and has uniform deletion stability

${\sup }_{S\in (\mathsf{X}\times \mathsf{Y}{)}^m,1\le i\le m,(x,y)\in \mathsf{X}\times \mathsf{Y}}\mathrm{\mid }c(A_S(x),y)-c(A_{S\setminus i}(x),y)\mathrm{\mid }\le {\beta }_m,{\beta }_m:=\frac{{\sigma }^2{\kappa }^2}{2\lambda m}\mathrm{.}$

For fixed $\lambda$, this stability envelope is nonincreasing in $m$. The conclusion supplies no uniform bounded-loss constant $M$; any such hypothesis for a concentration bound must be checked separately.

Bousquet and Elisseeff, equations (19)–(20), Lemmas 20–21, and Theorem 22 with proof, printed pp. 512–515; equation (20) keeps denominator $m$ after deletion. Full JMLR paper PDF

Mohri, Rostamizadeh, and Talwalkar, Proposition 14.4 with proof, printed pp. 337–339; this gives the corresponding replacement-stability coefficient, with its distinct convention. Full second-edition book PDF