Permutational Rademacher Complexity

DOI10.1007/978-3-319-24486-0_14MaRDI QIDQ2835630zbMATH OpenOpenAlexFDO

Authors Ilya Tolstikhin, Nikita Zhivotovskiy, Gilles Blanchard

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.02910

zbMATH Keywords

concentration inequalitiesempirical processesRademacher complexitystatistical learning theorytransductive learning

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: 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 new complexity measure for transductive learning called Permutational Rademacher Complexity (PRC) and studies its properties. A novel symmetrization inequality is proved, which shows that PRC provides a tighter control over expected suprema of empirical processes compared to what happens in the standard i.i.d. setting. A number of comparison results are also provided, which show the relation between PRC and other popular complexity measures used in statistical learning theory, including Rademacher complexity and Transductive Rademacher Complexity (TRC). We argue that PRC is a more suitable complexity measure for transductive learning. Finally, these results are combined with a standard concentration argument to provide novel data-dependent risk bounds for transductive learning.

Recommendations

• Transductive Rademacher complexity and its applications
• Transductive Rademacher Complexity and Its Applications
• Rademacher complexity in Neyman-Pearson classification
• Researches on Rademacher complexities in statistical learning theory: a survey
• The Rademacher Complexity of Linear Transformation Classes
• On learning mixture models for permutations
• Rademacher Margin Complexity
• Rademacher Chaos Complexities for Learning the Kernel Problem

Cites work

• 10.1162/153244303321897690
• Concentration inequalities. A nonasymptotic theory of independence
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• scientific article; zbMATH DE number 1552503 (Why is no real title available?)
• scientific article; zbMATH DE number 2243369 (Why is no real title available?)
• Local Rademacher complexities
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• PAC-MDL bounds.
• The best constants in the Khintchine inequality
• Theory of Classification: a Survey of Some Recent Advances
• Transductive Rademacher complexity and its applications
• Weak convergence and empirical processes. With applications to statistics

Cited in

(7)

• Measuring distributional asymmetry with Wasserstein distance and Rademacher symmetrization
• Local Rademacher complexity: sharper risk bounds with and without unlabeled samples
• Transductive Rademacher complexity and its applications
• Transductive Rademacher Complexity and Its Applications
• Learning Permutations with Exponential Weights
• Simple and fast algorithm for binary integer and online linear programming
• Information-theoretic generalization bounds for transductive learning and its applications

This page was built for publication: Permutational Rademacher Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835630)