Learning convex bodies is hard

Abstract

We 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.

Cited by in corpus (6)

• Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression
• Near-Optimal Evasion of Convex-Inducing Classifiers
• Query Strategies for Evading Convex-Inducing Classifiers
• Efficient learning of simplices
• Geometric Methods for Robust Data Analysis in High Dimension
• Nested Barycentric Coordinate System as an Explicit Feature Map