Learnability Beyond Uniform Convergence
Abstract
The problem of characterizing learnability is the most basic question of statistical learning theory. A fundamental result is that learnability is equivalent to uniform convergence of the empirical risk to the population risk, and that if a problem is learnable, it is learnable via empirical risk minimization. The equivalence of uniform convergence and learnability was formally established only in the supervised classification and regression setting. We show that in (even slightly) more complex prediction problems learnability does not imply uniform convergence. We discuss several alternative attempts to characterize learnability. This extended abstract summarizes results published in [5, 3].
Cite
Text
Shalev-Shwartz. "Learnability Beyond Uniform Convergence." International Conference on Algorithmic Learning Theory, 2012. doi:10.1007/978-3-642-34106-9_3Markdown
[Shalev-Shwartz. "Learnability Beyond Uniform Convergence." International Conference on Algorithmic Learning Theory, 2012.](https://mlanthology.org/alt/2012/shalevshwartz2012alt-learnability/) doi:10.1007/978-3-642-34106-9_3BibTeX
@inproceedings{shalevshwartz2012alt-learnability,
title = {{Learnability Beyond Uniform Convergence}},
author = {Shalev-Shwartz, Shai},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2012},
pages = {13-16},
doi = {10.1007/978-3-642-34106-9_3},
url = {https://mlanthology.org/alt/2012/shalevshwartz2012alt-learnability/}
}