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

Vitaly Feldman, Jan Vondrak

Algorithmic stability is a classical approach to understanding and analysis of the generalization error of learning algorithms. A notable weakness of most stability-based generaliz…