Learning convex polytopes with margin
Preprint
Abstract
We present a near-optimal algorithm for properly learning convex polytopes in the realizable PAC setting from data with a margin. Our first contribution is to identify distinct generalizations of the notion of {\em margin} from hyperplanes to polytopes and to understand how they relate geometrically; this result may be of interest beyond the learning setting. Our novel learning algorithm constructs a consistent polytope as an intersection of about $t \log t$ halfspaces in time polynomial in $t$ (where $t$ is the number of halfspaces forming an optimal polytope). This is an exponential improvement over the state of the art [Arriaga and Vempala, 2006]. We also improve over the super-polynomial-in-$t$ algorithm of Klivans and Servedio [2008], while achieving a better sample complexity. Finally, we provide the first nearly matching hardness-of-approximation lower bound, whence our claim of near optimality.
Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- On the hardness of learning intersections of two halfspacesJournal of Computer and System Sciences, 2011
- Cryptographic hardness for learning intersections of halfspacesJournal of Computer and System Sciences, 2009
- Learning intersections of halfspaces with a marginJournal of Computer and System Sciences, 2008
- An algorithmic theory of learning: Robust concepts and random projectionMachine Learning, 2006
- Lectures on Discrete Geometry2002
- PAC Learning Intersections of Halfspaces with Membership QueriesAlgorithmica, 1998
- The complexity and approximability of finding maximum feasible subsystems of linear relationsTheoretical Computer Science, 1995
- Robust Trainability of Single NeuronsJournal of Computer and System Sciences, 1995
- Composite Geometric Concepts and Polynomial PredictabilityInformation and Computation, 1994
- On the complexity of polyhedral separabilityDiscrete & Computational Geometry, 1988