Learning Functions of Halfspaces

Josh Alman, Shyamal Patel, Rocco A. Servedio

We give an algorithm that learns arbitrary Boolean functions of $k$ arbitrary halfspaces over ${\mathbb{R}}^n$, in the challenging distribution-free Probably Approximately Correct (P…