Tight Bounds for Learning Polyhedra with a Margin

Abstract

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