Transductive Rademacher Complexity and its Applications
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Transductive LearningSimilar Papers 제목 키워드 기반
Permutational Rademacher Complexity: a New Complexity Measure for Transductive Learning
Transductive learning considers situations when a learner observes $m$ labelled training points and $u$ unlabelled test points with the final goal of giving correct answers for the test points. This paper introduces a ne…
Learning TheoryTransductive LearningSharp Generalization of Transductive Learning: A Transductive Local Rademacher Complexity Approach
We introduce a new tool, Transductive Local Complexity (TLC), designed to analyze the generalization performance of transductive learning methods and inspire the development of new algorithms in this domain. Our work ext…
Generalization BoundsLearning TheoryTransductive LearningHypothesis Set Stability and Generalization
We present a study of generalization for data-dependent hypothesis sets. We give a general learning guarantee for data-dependent hypothesis sets based on a notion of transductive Rademacher complexity. Our main result is…
Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks
In recent years, several results in the supervised learning setting suggested that classical statistical learning-theoretic measures, such as VC dimension, do not adequately explain the performance of deep learning model…
Learning TheoryNode ClassificationIs Transductive Learning Equivalent to PAC Learning?
Much of learning theory is concerned with the design and analysis of probably approximately correct (PAC) learners. The closely related transductive model of learning has recently seen more scrutiny, with its learners of…
Binary ClassificationLearning TheoryPAC learningTransductive Learning