Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity

Haim Kaplan, Yishay Mansour, Uri Stemmer +1

We present a differentially private learner for halfspaces over a finite grid $G$ in ${\mathbb{R}}^d$ with sample complexity $\approx d^{2.5}\cdot 2^{{\log }^{\ast }|G|}$, which improves the…