Transductive Rademacher Complexity and its Applications

Abstract

We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher averages for particular algorithms, in terms of their "unlabeled-labeled" representation. This technique is relevant to many advanced graph-based transductive algorithms and we demonstrate its effectiveness by deriving error bounds to three well known algorithms. Finally, we present a new PAC-Bayesian bound for mixtures of transductive algorithms based on our Rademacher bounds.

References in corpus (1)

• Explicit Learning Curves for Transduction and Application to Clustering and Compression Algorithms

Cited by in corpus (4)

• Regression adjustment in completely randomized experiments with a diverging number of covariates
• Rademacher Complexity Bounds for a Penalized Multiclass Semi-Supervised Algorithm
• Generalization error bounds for kernel matrix completion and extrapolation
• Concentration inequalities on the multislice and for sampling without replacement