The Role of Interactivity in Structured Estimation
  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.
