%0 Conference Paper
%B 32nd Annual Conference on Learning Theory
%D 2019
%T Private Center Points and Learning of Halfspaces
%A Amos Beimel
%A Shay Moran
%A Kobbi Nissim
%A Uri Stemmer
%X We present a private learner for halfspaces over an arbitrary finite domain X⊂ℝ^{d} with sample complexity mathrmpoly(d,2^{log∗|X|}). The building block for this learner is a differentially private algorithm for locating an approximate center point of m>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 one-dimensional 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=Ω(d+log^{∗}|X|), whereas for pure differential privacy m=Ω(d log|X|).
%B 32nd Annual Conference on Learning Theory
%V vol 99
%P 1–14
%G eng
%U http://proceedings.mlr.press/v99/beimel19a.html