High probability generalization bounds for uniformly stable algorithms with nearly optimal rate

Understand

Algorithmic stability is a classical approach to understanding and analysis of the generalization error of learning algorithms.

• A notable weakness of most stability-based generalization bounds is that they hold only in expectation.
• Generalization with high probability has been established in a landmark paper of Bousquet and Elisseeff (2002) albeit at the expense of an additional $\sqrt{n}$ factor in the bound.
• Specifically, their bound on the estimation error of any $\gamma$-uniformly stable learning algorithm on $n$ samples and range in $[0,1]$ is $O(\gamma \sqrt{n \log(1/\delta)} + \sqrt{\log(1/\delta)/n})$ with probability $\geq 1-\delta$.