On the sample complexity of privately learning half-spaces

We present a differentially private learner for half-spaces over a finite domain $\mathcal{X}^d\subseteq\mathbb{R}^d$ with sample complexity $\tilde{O}(d\cdot\log^*\vert\mathcal{X}\vert)$, which improves over $\tilde{O}(d^{2.5}\cdot 8^{\log^*\vert\mathcal{X}\vert})$, the state-of-the-art result of [Kaplan et al., 2020]. The building block of our result is a novel differentially private algorithm that learns half-spaces by iteratively learning thresholds on angles.