Tight Bounds for Learning Polyhedra with a Margin

We give an algorithm for PAC learning intersections of $k$ halfspaces with a $ρ$ margin to within error $varepsilon$ that runs in time $textsf{poly}(k, varepsilon^{-1}, ρ^{-1}) cdot exp left(O(sqrt{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.