Private Center Points and Learning of Halfspaces
This work addresses privacy-preserving machine learning for halfspaces, with potential broader applications in differentially private algorithm design, though it appears incremental by building on prior relationships between median and threshold learning.
The paper tackles the problem of learning halfspaces with differential privacy by introducing a private algorithm that achieves sample complexity polynomial in dimension and a function of domain size, and provides lower bounds for privately finding points in convex hulls. The result includes concrete lower bounds: Ω(d + log*|X|) for approximate privacy and Ω(d log|X|) for pure privacy.
We present a private learner for halfspaces over an arbitrary finite domain $X\subset \mathbb{R}^d$ with sample complexity $mathrm{poly}(d,2^{\log^*|X|})$. The building block for this learner is a differentially private algorithm for locating an approximate center point of $m>\mathrm{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|)$.