Tight Bounds for Learning Polyhedra with a Margin

2026/04/30 by Shyamal Patel, Santosh Vempala
Computer Science · #cs.DS #cs.LG

paper · pdf

arxiv created 2026/07/30 · arxiv updated 2026/07/31

Abstract

We give an algorithm for PAC learning intersections of k halfspaces with a ρ margin to within error ε that runs in time \textsfpoly(k, ε^-1, ρ^-1) ⋅ exp (O(√(n log(1/ρ) log k))). 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.

Citations

• Learning Functions of Halfspaces
• Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
• Improved Hardness Results for Learning Intersections of Halfspaces
• Reducing Isotropy and Volume to KLS: Faster Rounding and Volume Algorithms
• Learning convex polyhedra with margin
• The Average Sensitivity of an Intersection of Half Spaces
• Statistical Algorithms and a Lower Bound for Detecting Planted Clique
• A note on the sign degree of formulas

Related

• Learning convex polyhedra with margin
• Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
• A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
• Improved Hardness Results for Learning Intersections of Halfspaces