Recent Advances on Generalization Bounds

Abstract. Bounding generalization ability of learning algorithms re- mains a challenging open problem in Statistical Learning Theory for more than 40 years, starting with pioneer works of Vapnik and Chervonenkis. Many improvements has been made recently in this field and many mathematical techniques are developed to apply generalization bounds for learning algorithms design. Most important issues are briefly reviewed in the first part of the tutorial.

In the second part a permutational probabilistic framework is introduced and a combinatorial technique is presented for obtaining tight data dependent generalization bounds. It is based on a detailed representation of the internal structure of the classifier set via a multipartite graph called the splitting and connectivity (SC) graph. Combinatorial generalization bounds based on statistical properties of the SC-graph are shown to be exact in some nontrivial particular cases. Some practical applications of SC-bounds are considered.