Transductive Rademacher Complexity and its Applications
This work addresses the need for theoretical guarantees in transductive learning, particularly for graph-based algorithms, though it appears incremental as it builds on existing Rademacher complexity concepts.
The paper tackles the problem of deriving data-dependent error bounds for transductive learning algorithms by introducing a technique based on transductive Rademacher complexity, resulting in novel bounds for three well-known algorithms and a new PAC-Bayesian bound for mixtures.
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.