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 arepsilon that runs in time extsf{poly}(k, arepsilon^{-1}, rho^{-1}) dot exp left(O(sqrt{n log(1/rho) log k})right). Notably, this improves on prior work which had an exponential dependence on either k or rho^{-1} and matches known cryptographic and Statistical Query lower bounds up to the logarithmic factors in k and rho in the exponent. Our learning algorithm extends to the more general setting when we are only promised that most points have distance at least rho from the boundary of the polyhedron, making it applicable to continuous distributions as well.

PAC-Bayesian Bounds on Constrained f-Entropic Risk Measures
PAC learning PDFA from data streams
Constant-Factor Approximation for the Uniform Decision Tree

Source: arXiv cs.LG | 2026-04-17