Learning convex bodies is hard TeX Export

@article{citeulike:4303195, 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.}, archivePrefix = {arXiv}, author = {Goyal, Navin and Rademacher, Luis}, citeulike-article-id = {4303195}, citeulike-linkout-0 = {http://arxiv.org/abs/0904.1227}, citeulike-linkout-1 = {http://arxiv.org/pdf/0904.1227}, day = {7}, eprint = {0904.1227}, keywords = {algorithmic-complexity, coding, convex}, month = {Apr}, posted-at = {2009-04-12 17:16:53}, priority = {2}, title = {Learning convex bodies is hard}, url = {http://arxiv.org/abs/0904.1227}, year = {2009} }

TY - JOUR ID - citeulike:4303195 L3 - citeulike-article-id:4303195 N2 - 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. TI - Learning convex bodies is hard KW - algorithmic-complexity KW - coding KW - convex AU - Goyal, Navin AU - Rademacher, Luis PY - 2009/Apr/07/ UR - http://arxiv.org/abs/0904.1227 ER -