Permutational Rademacher Complexity - A New Complexity Measure for Transductive Learning
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.
Cite
Text
Tolstikhin et al. "Permutational Rademacher Complexity - A New Complexity Measure for Transductive Learning." International Conference on Algorithmic Learning Theory, 2015. doi:10.1007/978-3-319-24486-0_14Markdown
[Tolstikhin et al. "Permutational Rademacher Complexity - A New Complexity Measure for Transductive Learning." International Conference on Algorithmic Learning Theory, 2015.](https://mlanthology.org/alt/2015/tolstikhin2015alt-permutational/) doi:10.1007/978-3-319-24486-0_14BibTeX
@inproceedings{tolstikhin2015alt-permutational,
title = {{Permutational Rademacher Complexity - A New Complexity Measure for Transductive Learning}},
author = {Tolstikhin, Ilya O. and Zhivotovskiy, Nikita and Blanchard, Gilles},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2015},
pages = {209-223},
doi = {10.1007/978-3-319-24486-0_14},
url = {https://mlanthology.org/alt/2015/tolstikhin2015alt-permutational/}
}