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

Abstract

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-$k^2$ 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-$k^2$ 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 ${\mathbb{F}}_r^t$. 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.

arXiv commentPreliminary version (subsumed by expanded version at arXiv:2005.08099), 65 pages

References in corpus (23)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical physics of inference: Thresholds and algorithms
• Optimal detection of sparse principal components in high dimension
• Incoherence-Optimal Matrix Completion
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Computational barriers in minimax submatrix detection
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Algorithmic thresholds for tensor PCA
• Finding One Community in a Sparse Graph
• Suboptimality of local algorithms for a class of max-cut problems
• Typology of phase transitions in Bayesian inference problems
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
• Sum-of-Squares Lower Bounds for Sparse PCA
• Efficient Algorithms for Outlier-Robust Regression
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness
• Average-case Hardness of RIP Certification
• Robust Sparse Estimation Tasks in High Dimensions
• Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program
• Sum of squares lower bounds for refuting any CSP
• Universality of Computational Lower Bounds for Submatrix Detection
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• How Hard Is Robust Mean Estimation?

Cited by in corpus (4)

• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Counterexamples to the Low-Degree Conjecture
• Clustering a Mixture of Gaussians with Unknown Covariance