# Learning convex polyhedra with margin

arXiv: https://arxiv.org/abs/1805.09719 · HTML: https://mlsanity.com/paper/1805.09719/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2018.

## Built on by (most cited first, 4 of 4)

- [Colloquium: Advances in automation of quantum dot devices control](https://mlsanity.com/paper/2112.09362/) (2021)
- [Learning Safety Constraints for Large Language Models](https://mlsanity.com/paper/2505.24445/) (2025)
- [On the complexity of PAC learning in Hilbert spaces](https://mlsanity.com/paper/2303.02047/) (2023)
- [Tight Bounds for Learning Polyhedra with a Margin](https://mlsanity.com/paper/2604.14614/) (2026)

## Abstract (arXiv)

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.