Learning Convex Bodies Is Hard
Abstract
We show that learning a convex body in $\RR^d$, given random samples from the body, requires $2^{\Omega(\sqrt{d/\eps})}$ samples. By learning a convex body we mean finding a set having at most $\eps$ relative symmetric difference with the input body. To prove the lower bound we construct a hard to learn family of convex bodies. Our construction of this family is very simple and based on error correcting codes.
Cite
Text
Rademacher and Goyal. "Learning Convex Bodies Is Hard." Annual Conference on Computational Learning Theory, 2009.Markdown
[Rademacher and Goyal. "Learning Convex Bodies Is Hard." Annual Conference on Computational Learning Theory, 2009.](https://mlanthology.org/colt/2009/rademacher2009colt-learning/)BibTeX
@inproceedings{rademacher2009colt-learning,
title = {{Learning Convex Bodies Is Hard}},
author = {Rademacher, Luis and Goyal, Navin},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2009},
url = {https://mlanthology.org/colt/2009/rademacher2009colt-learning/}
}