Permutation Complexity Bound on Out-Sample Error
Abstract
We define a data dependent permutation complexity for a hypothesis set \math{\hset}, which is similar to a Rademacher complexity or maximum discrepancy. The permutation complexity is based like the maximum discrepancy on (dependent) sampling. We prove a uniform bound on the generalization error, as well as a concentration result which means that the permutation estimate can be efficiently estimated.
Cite
Text
Magdon-Ismail. "Permutation Complexity Bound on Out-Sample Error." Neural Information Processing Systems, 2010.Markdown
[Magdon-Ismail. "Permutation Complexity Bound on Out-Sample Error." Neural Information Processing Systems, 2010.](https://mlanthology.org/neurips/2010/magdonismail2010neurips-permutation/)BibTeX
@inproceedings{magdonismail2010neurips-permutation,
title = {{Permutation Complexity Bound on Out-Sample Error}},
author = {Magdon-Ismail, Malik},
booktitle = {Neural Information Processing Systems},
year = {2010},
pages = {1531-1539},
url = {https://mlanthology.org/neurips/2010/magdonismail2010neurips-permutation/}
}