Sharper bounds for uniformly stable algorithms
  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. This paper is devoted to
these questions: firstly, inspired by the original arguments of Feldman and
Vondrak (2019), we provide a short proof of the moment bound that implies the
generalization bound stronger than both recent results (Feldman and Vondrak,
2018, 2019). Secondly, we prove general lower bounds, showing that our moment
bound is sharp (up to a logarithmic factor) unless some additional properties
of the corresponding random variables are used. Our main probabilistic result
is a general concentration inequality for weakly correlated random variables,
which may be of independent interest.
