Learning Convex Bodies is Hard
By Luis Rademacher, Navin Goyal. 2009
25 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Battista Biggio
- Fabio Roli
- Blaine Nelson
- Giorgio Fumera
- Benjamin I. P. Rubinstein
- Anthony D. Joseph
- J. Doug Tygar
- Ling Huang
Citations in the corpus
- Query Strategies for Evading Convex-Inducing Classifiers (2010, background): “eek (2005) for evading linear classifiers. Our algorithms for evading convex-inducing classifiers do not require fully estimating the classifier’s boundary (which is hard in the general convex case; see Rademacher and Goyal, 2009) or otherwise reverse-engineering the classifier’s state. Instead, we dire”