Private Center Points and Learning of Halfspaces
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:269282, 2019.
Abstract
We present a private agnostic learner for halfspaces over an arbitrary finite domain $X\subset \R^d$ with sample complexity $\mathsf{poly}(d,2^{\log^*X})$. The building block for this learner is a differentially private algorithm for locating an approximate center point of $m>\mathsf{poly}(d,2^{\log^*X})$ points – a high dimensional generalization of the median function. Our construction establishes a relationship between these two problems that is reminiscent of the relation between the median and learning onedimensional thresholds [Bun et al. FOCS ’15]. This relationship suggests that the problem of privately locating a center point may have further applications in the design of differentially private algorithms. We also provide a lower bound on the sample complexity for privately finding a point in the convex hull. For approximate differential privacy, we show a lower bound of $m=\Omega(d+\log^*X)$, whereas for pure differential privacy $m=\Omega(d\logX)$.
Related Material


