Sparse Gaussian mean estimation communication–risk conjecture

Let $P\in\mathcal{P}_s$ be a distribution with mean, and suppose a protocol estimates that mean with mean-squared loss $R$ and communication cost $C$. The parameters are the sparsity level $s$, dimension $d$, noise variance $\sigma^2$, and number of machines and samples $m,n$.

Sparse estimation tradeoff conjecture. If some protocol estimates the mean for any distribution $P\in\mathcal{P}_s$ with mean-squared loss $R$ and communication cost $C$, then

$$C\cdot R \gtrsim \frac{sd\sigma^2}{mn},$$

where $\gtrsim$ hides logarithmic factors and potential corner cases.

This conjecture asserts that the proposed sparse-parameter protocol has an essentially optimal communication–risk tradeoff, modulo logarithmic factors and possible boundary cases; the source gives no resolution.