Tight Bounds for Learning Polyhedra with a Margin
Provides a near-optimal algorithm for learning polyhedra with a margin, addressing a fundamental problem in computational learning theory.
The paper presents a PAC learning algorithm for intersections of k halfspaces with a margin ρ that runs in time poly(k, ε^{-1}, ρ^{-1}) · exp(O(√(n log(1/ρ) log k))), improving on prior exponential dependencies and matching lower bounds up to logarithmic factors.
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.