Learning Convex Bodies is Hard
Learning Convex Bodies is Hard
复制标题
学习凸体很难
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Navin Goyal
中科院分区：
文献类型：
--
作者：
Luis Rademacher;Navin Goyal
我们证明了，在$RR^d$中学习凸体，给定来自凸体的随机样本，需要$2^{Omega（sqrt{d/eps}）}$样本。通过学习凸体，我们的意思是找到一个与输入体最多有$eps$相对对称差的集合。为了证明下界，我们构造了一个很难学习的凸体族。我们构造这个族是非常简单的，并且基于纠错码。
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.