# On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 35 references that are in the map.
- First posted on arXiv 17 Sep 2022.

## Builds on (most cited first, 16 of 16)

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Learning Halfspaces with Massart Noise Under Structured Distributions](https://mlsanity.com/paper/2002.05632/) (2020)
- [Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12](https://mlsanity.com/paper/1709.02753/) (2017)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Heavy Hitters and the Structure of Local Privacy](https://mlsanity.com/paper/1711.04740/) (2017)
- [Empirical Risk Minimization in Non-interactive Local Differential Privacy: Efficiency and High Dimensional Case](https://mlsanity.com/paper/1802.04085/) (2018)
- [Self-training Converts Weak Learners to Strong Learners in Mixture Models](https://mlsanity.com/paper/2106.13805/) (2021)
- [Empirical Risk Minimization in the Non-interactive Local Model of Differential Privacy](https://mlsanity.com/paper/2011.05934/) (2020)
- [Private Center Points and Learning of Halfspaces](https://mlsanity.com/paper/1902.10731/) (2019)
- [Efficient Private Algorithms for Learning Large-Margin Halfspaces](https://mlsanity.com/paper/1902.09009/) (2019)
- [Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible](https://mlsanity.com/paper/1706.03316/) (2017)
- [Interaction is necessary for distributed learning with privacy or communication constraints](https://mlsanity.com/paper/1911.04014/) (2019)
- [Locally Private Learning without Interaction Requires Separation](https://mlsanity.com/paper/1809.09165/) (2018)
- [Noninteractive Locally Private Learning of Linear Models via Polynomial Approximations](https://mlsanity.com/paper/1812.06825/) (2018)

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

- [Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model](https://mlsanity.com/paper/2310.07367/) (2023)

## Abstract (arXiv)

In this paper, we study the problem of PAC learning halfspaces in the non-interactive local differential privacy model (NLDP). To breach the barrier of exponential sample complexity, previous results studied a relaxed setting where the server has access to some additional public but unlabeled data. We continue in this direction. Specifically, we consider the problem under the standard setting instead of the large margin setting studied before. Under different mild assumptions on the underlying data distribution, we propose two approaches that are based on the Massart noise model and self-supervised learning and show that it is possible to achieve sample complexities that are only linear in the dimension and polynomial in other terms for both private and public data, which significantly improve the previous results. Our methods could also be used for other private PAC learning problems.