  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.
