Learning convex bodies is hard

Simple item page
dc.creatorGoyal, Navin
dc.creatorRademacher, Luis
dc.date2009-04-07
dc.date.accessioned2026-07-07T13:01:37Z
dc.date.available2026-07-07T13:01:37Z
dc.descriptionWe show that learning a convex body in $\RR^d$, given random samples from the body, requires $2^{Ω(\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.
dc.identifierhttps://arxiv.org/abs/0904.1227
dc.identifierhttp://arxiv.org/abs/0904.1227
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/226211
dc.subjectMachine Learning
dc.subjectComputational Geometry
dc.titleLearning convex bodies is hard
dc.typetext

Files

Collections

arXiv