2022/03/14 by Jayadev Acharya, Acharya, Jayadev, Clément L. Canonne +5 · 1 citation
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #Wireless Communication Security Techniques #cs.DM #cs.DS #cs.IT #cs.LG #math.IT #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.2203.06870
arxiv created 2022/03/14 · openalex publication_date 2022/03/14 · arxiv updated 2022/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.