Algorithmic Stability

Definition

With $S_n^i$ = $S_n$ with the $i$-th point replaced by an independent $Z_i^{\prime }$: average stability ${\Delta }_{av}(A,n)=E\frac{1}{n}{\sum }_i(\ell (f(S_n),Z_i^{\prime })-\ell (f(S_n^i),Z_i^{\prime }))$; uniform stability ${\Delta }_{\sup }(A,n)={\sup }_{i,S_n,S_n^i,Z}|\ell (f(S_n),Z)-\ell (f(S_n^i),Z)|\ge {\Delta }_{av}$.

Formula

$$E(R(f(S_n))-R_{S_n}(f(S_n)))={\Delta }_{av},R(f(S_n))\le R_{S_n}(f(S_n))+{\beta }_n+(2n{\beta }_n+M)\sqrt{\frac{\log (1/\delta )}{2n}}$$

with ${\beta }_n={\Delta }_{\sup }(A,n)$ and loss $\le M$. The gap vanishes iff ${\beta }_n=o(1/\sqrt{n})$.

• Examples: averaging rule $2/n$; ERM with $\mu$-strongly convex, $L$-Lipschitz loss $4L^2/(\mu n)$; GD/SGD on convex smooth losses $\frac{2L^2}{n}{\sum }_t{\eta }_t$. 1-NN is not uniformly stable at rate $1/n$.
• Stability alone does not give consistency (constant predictors are stable); stability plus ERM does.
• The perceptron’s leave-one-out proof was an early instance of the principle.

Appears in

• Lecture 4, definitions
• Lecture 4, Proposition 1
• Lecture 4, Theorem 2
• Lecture 4, exam-style rate table
• Lecture 4, stability vs. consistency
• Lecture 2, first glimpse

Related concepts

• Strong Convexity
• Smoothness
• Leave-One-Out Error
• Generalization Bound