Private Center Points and Learning of Halfspaces

02/27/2019
by   Amos Beimel, et al.
0

We present a private learner for halfspaces over an arbitrary finite domain X⊂R^d with sample complexity mathrmpoly(d,2^^*|X|). The building block for this learner is a differentially private algorithm for locating an approximate center point of m>poly(d,2^^*|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+^*|X|), whereas for pure differential privacy m=Ω(d|X|).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset