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