Transductive Rademacher Complexity and Its Applications
Abstract
We present data-dependent error bounds for transductive learning based on transductive Rademacher complexity. For specific algorithms we provide bounds on their Rademacher complexity based on their "unlabeled-labeled" decomposition. This decomposition technique applies to many current and practical graph-based algorithms. Finally, we present a new PAC-Bayesian bound for mixtures of transductive algorithms based on our Rademacher bounds.
Cite
Text
El-Yaniv and Pechyony. "Transductive Rademacher Complexity and Its Applications." Journal of Artificial Intelligence Research, 2009. doi:10.1613/JAIR.2587Markdown
[El-Yaniv and Pechyony. "Transductive Rademacher Complexity and Its Applications." Journal of Artificial Intelligence Research, 2009.](https://mlanthology.org/jair/2009/elyaniv2009jair-transductive/) doi:10.1613/JAIR.2587BibTeX
@article{elyaniv2009jair-transductive,
title = {{Transductive Rademacher Complexity and Its Applications}},
author = {El-Yaniv, Ran and Pechyony, Dmitry},
journal = {Journal of Artificial Intelligence Research},
year = {2009},
pages = {193-234},
doi = {10.1613/JAIR.2587},
volume = {35},
url = {https://mlanthology.org/jair/2009/elyaniv2009jair-transductive/}
}