# Tight Bounds for Learning Polyhedra with a Margin

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 42 references that are in the map.
- First posted on arXiv 16 Apr 2026.

## Builds on (most cited first, 5 of 5)

- [Sampling and Integration of Logconcave Functions by Algorithmic Diffusion](https://mlsanity.com/paper/2411.13462/) (2024)
- [Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms](https://mlsanity.com/paper/2008.02146/) (2020)
- [Improved Hardness Results for Learning Intersections of Halfspaces](https://mlsanity.com/paper/2402.15995/) (2024)
- [Learning convex polyhedra with margin](https://mlsanity.com/paper/1805.09719/) (2018)
- [Learning Functions of Halfspaces](https://mlsanity.com/paper/2603.08700/) (2026)

## Abstract (arXiv)

We give an algorithm for PAC learning intersections of k halfspaces with a ρ margin to within error varepsilon that runs in time textsfpoly(k, varepsilon-1, ρ-1) · exp left(O(√n log(1/ρ) log k)right). Notably, this improves on prior work which had an exponential dependence on either k or ρ-1 and matches known cryptographic and Statistical Query lower bounds up to the logarithmic factors in k and ρ in the exponent. Our learning algorithm extends to the more general setting when we are only promised that most points have distance at least ρ from the boundary of the polyhedron, making it applicable to continuous distributions as well.