@conference {1511862,
	title = {Private Center Points and Learning of Halfspaces},
	booktitle = {32nd Annual Conference on Learning Theory},
	volume = {vol 99},
	year = {2019},
	pages = {1{\textendash}14},
	abstract = {We present a private learner for halfspaces over an arbitrary finite domain\&nbsp;X⊂ℝd\&nbsp;with sample complexity\&nbsp;mathrmpoly(d,2log*|X|). The building block for this learner is a differentially private algorithm for locating an approximate center point of\&nbsp;m\&gt;poly(d,2log*|X|)\&nbsp;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 {\textquoteright}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\&nbsp;m=Ω(d+log*|X|), whereas for pure differential privacy\&nbsp;m=Ω(d log|X|).},
	url = {http://proceedings.mlr.press/v99/beimel19a.html},
	author = {Amos Beimel and Shay Moran and Kobbi Nissim and Uri Stemmer}
}
