# Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Aug 2019.

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

- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap](https://mlsanity.com/paper/2205.13527/) (2022)
- [Sparse Mean Estimation in Adversarial Settings via Incremental Learning](https://mlsanity.com/paper/2305.15276/) (2023)

## Abstract (arXiv)

This paper develops several average-case reduction techniques to show new hardness results for three central high-dimensional statistics problems, implying a statistical-computational gap induced by robustness, a detection-recovery gap and a universality principle for these gaps. A main feature of our approach is to map to these problems via a common intermediate problem that we introduce, which we call Imbalanced Sparse Gaussian Mixtures. We assume the planted clique conjecture for a version of the planted clique problem where the position of the planted clique is mildly constrained, and from this obtain the following computational lower bounds: (1) a k-to-k2 statistical-computational gap for robust sparse mean estimation, providing the first average-case evidence for a conjecture of Li (2017) and Balakrishnan et al. (2017); (2) a tight lower bound for semirandom planted dense subgraph, which shows that a semirandom adversary shifts the detection threshold in planted dense subgraph to the conjectured recovery threshold; and (3) a universality principle for k-to-k2 gaps in a broad class of sparse mixture problems that includes many natural formulations such as the spiked covariance model. Our main approach is to introduce several average-case techniques to produce structured and Gaussianized versions of an input graph problem, and then to rotate these high-dimensional Gaussians by matrices carefully constructed from hyperplanes in mathbbFrt. For our universality result, we introduce a new method to perform an algorithmic change of measure tailored to sparse mixtures. We also provide evidence that the mild promise in our variant of planted clique does not change the complexity of the problem.