Strong and weak stability of randomized learning algorithms

An algorithm is called stable at a training set S if any change of a single point in S yields only a small change in the output. Stability of the learning algorithm is necessary for learnability in the supervised classification and regression setting. In this paper, we give formal definitions of strong and weak stability for randomized algorithms and prove non-asymptotic bounds on the difference between the empirical and expected error.