Stability and Generalization

Authors: Olivier Bousquet, André Elisseeff
Published: 2002
Journal: Journal of Machine Learning Research
Link: PDF

Summary

This foundational paper establishes the connection between algorithmic stability and generalization. It provides a framework for analyzing learning algorithms based on how sensitive they are to perturbations in the training data.

Key Contributions

1. Stability Definitions

The paper introduces several notions of algorithmic stability:

Uniform Stability: An algorithm $A$ is $\beta$-uniformly stable if for all datasets $S$ differing in at most one example: $\sup_{z} |L(A_S, z) - L(A_{S'}, z)| \leq \beta$

Hypothesis Stability: Measures stability in terms of the hypothesis space.

Point-wise Hypothesis Stability: $\mathbb{E}_{S,i}[|L(A_S, z_i) - L(A_{S^{\backslash i}}, z_i)|] \leq \beta_{ph}$

2. Generalization Bounds

Main Theorem: If an algorithm has uniform stability $\beta$, then with probability at least $1-\delta$: $R[A_S] \leq R_{emp}[A_S] + 2\beta + (4n\beta + M)\sqrt{\frac{\ln(1/\delta)}{2n}}$

where $R$ is the true risk, $R_{emp}$ is empirical risk, $n$ is sample size, and $M$ is loss bound.

3. Stability of Regularized Algorithms

For regularized ERM with strongly convex loss: $A_S = \arg\min_{f \in \mathcal{H}} \frac{1}{n}\sum_{i=1}^n L(f, z_i) + \lambda \|f\|_{\mathcal{H}}^2$

The stability coefficient is: $\beta \leq \frac{\kappa^2}{2\lambda n}$

where $\kappa$ is the bound on the kernel.

Mathematical Framework

Loss Function Properties

Assume loss function $L$ satisfies:

• Bounded: $0 \leq L(f, z) \leq M$
• Lipschitz in $f$: $|L(f, z) - L(f', z)| \leq c|f(x) - f'(x)|$

McDiarmid's Inequality

The proof uses concentration inequalities, particularly McDiarmid's bounded differences inequality:

If $f(x_1, \ldots, x_n)$ satisfies: $\sup_{x_i, x_i'} |f(\ldots, x_i, \ldots) - f(\ldots, x_i', \ldots)| \leq c_i$

Then: $P(f - \mathbb{E}[f] \geq t) \leq \exp\left(-\frac{2t^2}{\sum_i c_i^2}\right)$

Applications to Kernel Methods

Regularized Least Squares

For kernel ridge regression: $f_S = \arg\min_{f \in \mathcal{H}} \frac{1}{n}\sum_{i=1}^n (f(x_i) - y_i)^2 + \lambda \|f\|_{\mathcal{H}}^2$

Stability bound: $\beta \leq \frac{\kappa^2}{n\lambda}$

Support Vector Machines

For soft-margin SVM with hinge loss: $\beta \leq \frac{2\kappa^2}{n\lambda}$

Comparison with VC Theory

Approach	Bound Type	Depends On
VC Theory	Uniform over hypothesis class	VC dimension
Stability	Algorithm-specific	Stability coefficient

Advantages of Stability:

• Algorithm-specific bounds (often tighter)
• Applies to non-ERM algorithms
• Works for unbounded hypothesis classes

Impact on Machine Learning

This paper:

1. Unified framework: Connected stability to generalization
2. Practical bounds: Provided tighter bounds for regularized methods
3. Theoretical foundation: Enabled analysis of many learning algorithms

Citation

@article{bousquet2002stability,
  title={Stability and generalization},
  author={Bousquet, Olivier and Elisseeff, Andr{\'e}},
  journal={Journal of Machine Learning Research},
  volume={2},
  pages={499--526},
  year={2002}
}

Further Reading

• Shalev-Shwartz, S., et al. (2010). Learnability, stability and uniform convergence
• Hardt, M., et al. (2016). Train faster, generalize better: Stability of stochastic gradient descent
• Feldman, V. & Vondrak, J. (2019). High probability generalization bounds for uniformly stable algorithms