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 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.