Learning convex polyhedra with margin
Preprint
Abstract
We present an improved algorithm for {\em quasi-properly} learning convex polyhedra in the realizable PAC setting from data with a margin. Our learning algorithm constructs a consistent polyhedron as an intersection of about $t \log t$ halfspaces with constant-size margins in time polynomial in $t$ (where $t$ is the number of halfspaces forming an optimal polyhedron). We also identify distinct generalizations of the notion of margin from hyperplanes to polyhedra and investigate how they relate geometrically; this result may have ramifications beyond the learning setting.
Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- The VC-Dimension of K-Vertex D-PolytopesCombinatorica, 2020
- New Tools and Connections for Exponential-Time ApproximationAlgorithmica, 2018
- Lower Bounds Based on the Exponential-Time Hypothesis2015
- On Subexponential and FPT-Time InapproximabilityAlgorithmica, 2014
- Geometrical analysis of near polyhedral shapes with round edges in small crystalline particles or precipitatesJournal of Materials Science, 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
- Robust Trainability of Single NeuronsJournal of Computer and System Sciences, 1995
- On the complexity of polyhedral separabilityDiscrete & Computational Geometry, 1988