Efficient Proper Agnostic Learning of Halfspaces

Anindya De, Elchanan Mossel, Shivam Nadimpalli +1

We give a proper membership-query algorithm for agnostically learning halfspaces under the uniform distribution on $\{\pm 1{\}}^n$. Given query access to an arbitrary function $f:\{\p…