We provide the first computationally efficient, differentially private algorithms for agnostically learning halfspaces.
In particular, we study three different settings of agnostic learning:
- improper learning under Gaussian and log-concave marginals;
- proper learning under Gaussian marginals;
- semi-agnostic learning under Gaussian marginals.
In all three aforementioned settings, the added cost in the sample complexity due to privacy matches the respective non-private sample complexity, implying that we get privacy for free.