Localized Complexities for Transductive Learning


Ilya Tolstikhin, Gilles Blanchard, Marius Kloft ;
Proceedings of The 27th Conference on Learning Theory, PMLR 35:857-884, 2014.


We show two novel concentration inequalities for suprema of empirical processes when sampling without replacement, which both take the variance of the functions into account. While these inequalities may potentially have broad applications in learning theory in general, we exemplify their significance by studying the transductive setting of learning theory. For which we provide the first excess risk bounds based on the localized complexity of the hypothesis class, which can yield fast rates of convergence also in the transductive learning setting. We give a preliminary analysis of the localized complexities for the prominent case of kernel classes.

Related Material