Uniform stability for randomized learning rules

Fix a supervised prediction problem with observation space $\mathsf{Z}=\mathsf{X}\times \mathsf{Y}$, measurable predictor class $\mathcal{F}$, and nonnegative measurable loss $\mathrm{\ell }$. Write $L_f(x,y)=\mathrm{\ell }(f(x),y)$ for $f\in \mathcal{F}$. Fix a sample size $n\ge 1$. A randomized learning rule at this sample size consists of internal randomness $U_n$ with law $Q_n$, independent of the sample, and an output $A_n(S,U_n)\in \mathcal{F}$ for every ordered sample $S\in {\mathsf{Z}}^n$. Assume the expected test losses below are finite. For $\epsilon \ge 0$, the rule has uniform replacement stability at level $\epsilon$ if, for every pair $S,S^{\mathrm{\prime }}\in {\mathsf{Z}}^n$ differing in at most one coordinate, and every test observation $z\in \mathsf{Z}$,

$\mid {\mathbb{E}}_{U_n}{L}_{A_n(S,U_n)}(z)-{\mathbb{E}}_{U_n}{L}_{A_n(S^{\mathrm{\prime }},U_n)}(z)\mid \le \epsilon \mathrm{.}$

The absolute value is outside expectation over the internal randomness. No permutation-invariance condition is imposed on the learning rule.

Hardt, Recht, and Singer, Definition 2.1: full arXiv paper.

Matni, Lecture 16, Definition 1: full lecture notes.