Applications of Empirical Processes in Learning Theory: Algorithmic Stability and Performance Guarantees
We study two key properties of learning algorithms: their generalization ability and their stability with respect to perturbations. To analyze these properties, we focus on concentration inequalities and tools from empirical process theory. We obtain theoretical results and demonstrate their applications to machine learning. First, we demonstrate how the Contraction Lemma for Rademacher averages can be used to obtain tight performance guarantees for learning methods [3]. In particular, we derive risk bounds for a greedy mixture density estimation procedure. We prove that, unlike what is suggested in the literature, the number of terms in the mixture is not a bias-variance trade-off for the performance. Our upper bound asserts that the estimation error decreases as the number of terms in the mixture increases. Next, we study stability properties of general learning algorithms [1]. We show how various stabilities upper- and lower-bound the bias and variance of several estimators of the expected performance. Furthermore, we prove a generalization of the bounded-difference concentration inequality of McDiarmid for almost-everywhere-smooth functions. Experiments are performed to ascertain the utility of stability measures in practical applications. We provide a solution [2] to an open problem regarding the stability of a specific learning algorithm called Empirical Risk Minimization (ERM). This algorithm is of central importance in Learning Theory. By studying the suprema of the empirical process, we prove that ERM over Donsker classes of functions is stable in the L1 norm. Hence, as the number of samples grows, it becomes less and less likely that a perturbation of o( p n) samples will result in a very different empirical minimizer. Asymptotic rates of this stability are proved under metric entropy assumptions on the function class. Through the use of a ratio limit inequality, we also prove stability of expected errors of empirical minimizers. Finally, we investigate applications of the above stability result. In particular, we focus on procedures that optimize an objective function, such as k-means and other clustering methods. We demonstrate that stability of clustering is closely related to the notion of “realizability” in Learning Theory. Furthermore, our result on stability of ERM delineates a phase transition between stability and instability of clustering methods. Stability is the most widely used empirical quality measure for clustering, and our results make progress towards building a theoretical foundation for clustering methods.