# Private Center Points and Learning of Halfspaces

arXiv: https://arxiv.org/abs/1902.10731 · HTML: https://mlsanity.com/paper/1902.10731/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2019.

## Built on by (most cited first, 14 of 14)

- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Easy Differentially Private Linear Regression](https://mlsanity.com/paper/2208.07353/) (2022)
- [~Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization](https://mlsanity.com/paper/2211.06387/) (2022)
- [Sentence-level Privacy for Document Embeddings](https://mlsanity.com/paper/2205.04605/) (2022)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [Multiclass versus Binary Differentially Private PAC Learning](https://mlsanity.com/paper/2107.10870/) (2021)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [On the Sample Complexity of Privately Learning Axis-Aligned Rectangles](https://mlsanity.com/paper/2107.11526/) (2021)
- [Differentially private multivariate medians](https://mlsanity.com/paper/2210.06459/) (2022)
- [Differentially Private Medians and Interior Points for Non-Pathological Data](https://mlsanity.com/paper/2305.13440/) (2023)
- [An tildeOptimal Differentially Private Learner for Concept Classes with VC Dimension 1](https://mlsanity.com/paper/2505.06581/) (2025)
- [On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data](https://mlsanity.com/paper/2209.08319/) (2022)
- [Private Component-by-Component Learning](https://mlsanity.com/paper/2610.05102/) (2026)

## Abstract (arXiv)

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