Sharper bounds for uniformly stable algorithms

Understand

Deriving generalization bounds for stable algorithms is a classical question in learning theory taking its roots in the early works by Vapnik and Chervonenkis (1974) and Rogers and Wagner (1978).

• In a series of recent breakthrough papers by Feldman and Vondrak (2018, 2019), it was shown that the best known high probability upper bounds for uniformly stable learning algorithms due to Bousquet and Elisseef (2002) are sub-optimal in some natural regimes.
• To do so, they proved two generalization bounds that significantly outperform the simple generalization bound of Bousquet and Elisseef (2002).
• Feldman and Vondrak also asked if it is possible to provide sharper bounds and prove corresponding high probability lower bounds.