Tight Bounds for Learning Polyhedra with a Margin
arXiv:2604.14614v1 Announce Type: cross
Abstract: We give an algorithm for PAC learning intersections of $k$ halfspaces with a $\rho$ margin to within error $\varepsilon$ that runs in time $\textsf{poly}(k, \varepsilon^{-1}, \rho^{-1}) \cdot \exp \lef…