Private Center Points and Learning of Halfspaces

2019/02/27 by Beimel, Amos, Moran, Shay, Nissim, Kobbi +1 · 2 citations
#Artificial Intelligence (cs.AI) #Computational Geometry (cs.CG) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1902.10731

Abstract

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=Ω(dlog|X|).

Cited by

• Adaptive Privacy Budgeting
• Solving Linear Programs with Differential Privacy

Related

• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
• Efficient Private Algorithms for Learning Large-Margin Halfspaces
• Privately Learning Thresholds: Closing the Exponential Gap
• Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems
• Robust and Private Learning of Halfspaces