# Locally Private Learning without Interaction Requires Separation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2018.

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

- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model](https://mlsanity.com/paper/2310.07367/) (2023)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data](https://mlsanity.com/paper/2209.08319/) (2022)
- [Private Blind Model Averaging - Distributed, Non-interactive, and Convergent](https://mlsanity.com/paper/2211.02003/) (2022)
- [Smooth Sensitivity for Learning Differentially-Private yet Accurate Rule Lists](https://mlsanity.com/paper/2403.13848/) (2024)

## Abstract (arXiv)

We consider learning under the constraint of local differential privacy (LDP). For many learning problems known efficient algorithms in this model require many rounds of communication between the server and the clients holding the data points. Yet multi-round protocols are prohibitively slow in practice due to network latency and, as a result, currently deployed large-scale systems are limited to a single round. Despite significant research interest, very little is known about which learning problems can be solved by such non-interactive systems. The only lower bound we are aware of is for PAC learning an artificial class of functions with respect to a uniform distribution (Kasiviswanathan et al. 2011). We show that the margin complexity of a class of Boolean functions is a lower bound on the complexity of any non-interactive LDP algorithm for distribution-independent PAC learning of the class. In particular, the classes of linear separators and decision lists require exponential number of samples to learn non-interactively even though they can be learned in polynomial time by an interactive LDP algorithm. This gives the first example of a natural problem that is significantly harder to solve without interaction and also resolves an open problem of Kasiviswanathan et al. (2011). We complement this lower bound with a new efficient learning algorithm whose complexity is polynomial in the margin complexity of the class. Our algorithm is non-interactive on labeled samples but still needs interactive access to unlabeled samples. All of our results also apply to the statistical query model and any model in which the number of bits communicated about each data point is constrained.