# The Role of Interactivity in Local Differential Privacy

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

## Key facts

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

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

- [Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses](https://mlsanity.com/paper/2106.09779/) (2021)
- [Private Non-Convex Federated Learning Without a Trusted Server](https://mlsanity.com/paper/2203.06735/) (2022)
- [Shuffle Private Stochastic Convex Optimization](https://mlsanity.com/paper/2106.09805/) (2021)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Task-aware Privacy Preservation for Multi-dimensional Data](https://mlsanity.com/paper/2110.02329/) (2021)
- [Transfer Learning In Differential Privacy's Hybrid-Model](https://mlsanity.com/paper/2201.12018/) (2022)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Private and Communication-Efficient Algorithms for Entropy Estimation](https://mlsanity.com/paper/2305.07751/) (2023)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [Federated Learning of Quantile Inference under Local Differential Privacy](https://mlsanity.com/paper/2509.21800/) (2025)
- [Locally differentially private estimation of nonlinear functionals of discrete distributions](https://mlsanity.com/paper/2107.03940/) (2021)
- [Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph](https://mlsanity.com/paper/2509.16180/) (2025)
- [SLDP: Semi-Local Differential Privacy for Density-Adaptive Analytics](https://mlsanity.com/paper/2602.18910/) (2026)

## Abstract (arXiv)

We study the power of interactivity in local differential privacy. First, we focus on the difference between fully interactive and sequentially interactive protocols. Sequentially interactive protocols may query users adaptively in sequence, but they cannot return to previously queried users. The vast majority of existing lower bounds for local differential privacy apply only to sequentially interactive protocols, and before this paper it was not known whether fully interactive protocols were more powerful. We resolve this question. First, we classify locally private protocols by their compositionality, the multiplicative factor k ≥ 1 by which the sum of a protocol's single-round privacy parameters exceeds its overall privacy guarantee. We then show how to efficiently transform any fully interactive k-compositional protocol into an equivalent sequentially interactive protocol with an O(k) blowup in sample complexity. Next, we show that our reduction is tight by exhibiting a family of problems such that for any k, there is a fully interactive k-compositional protocol which solves the problem, while no sequentially interactive protocol can solve the problem without at least an tilde Omega(k) factor more examples. We then turn our attention to hypothesis testing problems. We show that for a large class of compound hypothesis testing problems --- which include all simple hypothesis testing problems as a special case --- a simple noninteractive test is optimal among the class of all (possibly fully interactive) tests.