Agnostic Learning Nonconvex Function Classes
Abstract
We consider the sample complexity of agnostic learning with respect to squared loss. It is known that if the function class F used for learning is convex then one can obtain better sample complexity bounds than usual. It has been claimed that there is a lower bound that showed there was an essential gap in the rate. In this paper we show that the lower bound proof has a gap in it. Although we do not provide a definitive answer to its validity. More positively, we show one can obtain “fast” sample complexity bounds for nonconvex F for “most” target conditional expectations. The new bounds depend on the detailed geometry of F , in particular the distance in a certain sense of the target’s conditional expectation from the set of nonuniqueness points of the class F .
Cite
Text
Mendelson and Williamson. "Agnostic Learning Nonconvex Function Classes." Annual Conference on Computational Learning Theory, 2002. doi:10.1007/3-540-45435-7_1Markdown
[Mendelson and Williamson. "Agnostic Learning Nonconvex Function Classes." Annual Conference on Computational Learning Theory, 2002.](https://mlanthology.org/colt/2002/mendelson2002colt-agnostic/) doi:10.1007/3-540-45435-7_1BibTeX
@inproceedings{mendelson2002colt-agnostic,
title = {{Agnostic Learning Nonconvex Function Classes}},
author = {Mendelson, Shahar and Williamson, Robert C.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2002},
pages = {1-13},
doi = {10.1007/3-540-45435-7_1},
url = {https://mlanthology.org/colt/2002/mendelson2002colt-agnostic/}
}