Learning convex polyhedra with margin
This work addresses the challenge of efficiently learning complex geometric structures for applications in machine learning and computational geometry, though it appears incremental as it builds on prior methods for learning with margins.
The paper tackles the problem of learning convex polyhedra from data with a margin in the realizable PAC setting, resulting in an algorithm that constructs a consistent polyhedron using about t log t halfspaces with constant-size margins in polynomial time, where t is the number of halfspaces in an optimal polyhedron.
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.