Export Reviews, Discussions, Author Feedback and Meta-Reviews

Note: References present in the paper are referred to by their numerical citations as used in the paper. Summary of Paper The paper seeks to establish a connection between algorithmic stability and generalization performance. Notions of algorithmic stability have been proposed before and linked to the generalization performance of learning algorithms [6,11,13,14] and have also been shown to be crucial for learnability [14]. This paper first establishes that for Vapnik's general setting of learning, a probabilistic notion of stability, is necessary and sufficient for the training losses to converge to test losses uniformly for all distributions. The paper then presents some discussions on how this notion of stability can be interpreted to give results in terms of the capacity of the function class or the size of the population.