Localized Complexities for Transductive Learning
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheoryTransductive LearningSimilar Papers 제목 키워드 기반
Transductive Learning Is Compact
We demonstrate a compactness result holding broadly across supervised learning with a general class of loss functions: Any hypothesis class $H$ is learnable with transductive sample complexity $m$ precisely when all of i…
Learning TheoryPAC learningTransductive LearningOptimal Mistake Bounds for Transductive Online Learning
We resolve a 30-year-old open problem concerning the power of unlabeled data in online learning by tightly quantifying the gap between transductive and standard online learning. In the standard setting, the optimal mista…
Sharp 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 LearningIs 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 LearningEarly stopping for kernel boosting algorithms: A general analysis with localized complexities
Early stopping of iterative algorithms is a widely-used form of regularization in statistics, commonly used in conjunction with boosting and related gradient-type algorithms. Although consistency results have been establ…