# Interaction is necessary for distributed learning with privacy or communication constraints

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

## Key facts

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

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

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Bounding the Excess Risk for Linear Models Trained on Marginal-Preserving, Differentially-Private, Synthetic Data](https://mlsanity.com/paper/2402.04375/) (2024)
- [Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?](https://mlsanity.com/paper/2607.02896/) (2026)
- [Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation](https://mlsanity.com/paper/2608.02538/) (2026)
- [On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data](https://mlsanity.com/paper/2209.08319/) (2022)
- [Learning versus Refutation in Noninteractive Local Differential Privacy](https://mlsanity.com/paper/2210.15439/) (2022)
- [Private Blind Model Averaging - Distributed, Non-interactive, and Convergent](https://mlsanity.com/paper/2211.02003/) (2022)

## Abstract (arXiv)

Local differential privacy (LDP) is a model where users send privatized data to an untrusted central server whose goal it to solve some data analysis task. In the non-interactive version of this model the protocol consists of a single round in which a server sends requests to all users then receives their responses. This version is deployed in industry due to its practical advantages and has attracted significant research interest. Our main result is an exponential lower bound on the number of samples necessary to solve the standard task of learning a large-margin linear separator in the non-interactive LDP model. Via a standard reduction this lower bound implies an exponential lower bound for stochastic convex optimization and specifically, for learning linear models with a convex, Lipschitz and smooth loss. These results answer the questions posed in citepSmithTU17,DanielyF18. Our lower bound relies on a new technique for constructing pairs of distributions with nearly matching moments but whose supports can be nearly separated by a large margin hyperplane. These lower bounds also hold in the model where communication from each user is limited and follow from a lower bound on learning using non-adaptive statistical queries.