# The Role of Interactivity in Structured Estimation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 44 references that are in the map.
- First posted on arXiv 14 Mar 2022.

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

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy](https://mlsanity.com/paper/1702.00610/) (2017)
- [Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication](https://mlsanity.com/paper/1802.04705/) (2018)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [Fisher information under local differential privacy](https://mlsanity.com/paper/2005.10783/) (2020)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [Locally Private Hypothesis Selection](https://mlsanity.com/paper/2002.09465/) (2020)
- [The Role of Interactivity in Local Differential Privacy](https://mlsanity.com/paper/1904.03564/) (2019)
- [Interactive Inference under Information Constraints](https://mlsanity.com/paper/2007.10976/) (2020)
- [Near-Optimal Adaptive Compressed Sensing](https://mlsanity.com/paper/1306.6239/) (2013)
- [Interaction is necessary for distributed learning with privacy or communication constraints](https://mlsanity.com/paper/1911.04014/) (2019)
- [Information-constrained optimization: can adaptive processing of gradients help?](https://mlsanity.com/paper/2104.00979/) (2021)
- [Locally Private Learning without Interaction Requires Separation](https://mlsanity.com/paper/1809.09165/) (2018)
- [Tight Lower Bounds for Locally Differentially Private Selection](https://mlsanity.com/paper/1802.02638/) (2018)
- [Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit](https://mlsanity.com/paper/1907.08743/) (2019)
- [Event-Triggered State Observers for Sparse Sensor Noise/Attacks](https://mlsanity.com/paper/1309.3511/) (2013)
- [PAC Best Arm Identification Under a Deadline](https://mlsanity.com/paper/2106.03221/) (2021)

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

- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Distributed Linear Bandits under Communication Constraints](https://mlsanity.com/paper/2211.02212/) (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)
- [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)
- [Distribution-Aware Mean Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2410.09506/) (2024)

## Abstract (arXiv)

We study high-dimensional sparse estimation under three natural constraints: communication constraints, local privacy constraints, and linear measurements (compressive sensing). Without sparsity assumptions, it has been established that interactivity cannot improve the minimax rates of estimation under these information constraints. The question of whether interactivity helps with natural inference tasks has been a topic of active research. We settle this question in the affirmative for the prototypical problems of high-dimensional sparse mean estimation and compressive sensing, by demonstrating a gap between interactive and noninteractive protocols. We further establish that the gap increases when we have more structured sparsity: for block sparsity this gap can be as large as polynomial in the dimensionality. Thus, the more structured the sparsity is, the greater is the advantage of interaction. Proving the lower bounds requires a careful breaking of a sum of correlated random variables into independent components using Baranyai's theorem on decomposition of hypergraphs, which might be of independent interest.