Localized Complexities for Transductive Learning
This work addresses the challenge of improving risk bounds in transductive learning for machine learning theorists, offering a novel theoretical framework that is incremental in building upon existing complexity measures.
The authors tackled the problem of deriving excess risk bounds in transductive learning by introducing two novel concentration inequalities for empirical processes under sampling without replacement, which incorporate function variance. They provided the first excess risk bounds based on localized complexities of hypothesis classes, enabling fast convergence rates in this setting, with a preliminary analysis applied to kernel classes.
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.