Reducibility and Statistical-Computational Gaps from Secret Leakage

Abstract

Inference problems with conjectured statistical-computational gaps are ubiquitous throughout modern statistics, computer science and statistical physics. While there has been success evidencing these gaps from the failure of restricted classes of algorithms, progress towards a more traditional reduction-based approach to computational complexity in statistical inference has been limited. Existing reductions have largely been limited to inference problems with similar structure -- primarily mapping among problems representable as a sparse submatrix signal plus a noise matrix, which are similar to the common hardness assumption of planted clique. The insight in this work is that a slight generalization of the planted clique conjecture -- secret leakage planted clique -- gives rise to a variety of new average-case reduction techniques, yielding a web of reductions among problems with very different structure. Using variants of the planted clique conjecture for specific forms of secret leakage planted clique, we deduce tight statistical-computational tradeoffs for a diverse range of problems including robust sparse mean estimation, mixtures of sparse linear regressions, robust sparse linear regression, tensor PCA, variants of dense $k$-block stochastic block models, negatively correlated sparse PCA, semirandom planted dense subgraph, detection in hidden partition models and a universality principle for learning sparse mixtures. In particular, a $k$-partite hypergraph variant of the planted clique conjecture is sufficient to establish all of our computational lower bounds. Our techniques also reveal novel connections to combinatorial designs and to random matrix theory. This work gives the first evidence that an expanded set of hardness assumptions, such as for secret leakage planted clique, may be a key first step towards a more complete theory of reductions among statistical problems.

175 pages; subsumes preliminary draft arXiv:1908.06130; accepted for presentation at the Conference on Learning Theory (COLT) 2020

References in corpus (40)

• Simultaneous analysis of Lasso and Dantzig selector
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical physics of inference: Thresholds and algorithms
• Graph spectra and the detectability of community structure in networks
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Optimal detection of sparse principal components in high dimension
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Incoherence-Optimal Matrix Completion
• Computational and Statistical Tradeoffs via Convex Relaxation
• Model-based clustering based on sparse finite Gaussian mixtures
• Sparse Principal Components Analysis
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Sever: A Robust Meta-Algorithm for Stochastic Optimization
• Computational barriers in minimax submatrix detection
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• Alternating Minimization for Mixed Linear Regression
• Finding One Community in a Sparse Graph
• Guaranteed clustering and biclustering via semidefinite programming
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Spectral Experts for Estimating Mixtures of Linear Regressions
• Suboptimality of local algorithms for a class of max-cut problems
• Regularized EM Algorithms: A Unified Framework and Statistical Guarantees
• Typology of phase transitions in Bayesian inference problems
• Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems
• Information-theoretic thresholds for community detection in sparse networks
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• High Dimensional Robust Sparse Regression
• On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
• The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
• Non-Reconstructability in the Stochastic Block Model
• Robust Sparse Estimation Tasks in High Dimensions
• The estimation error of general first order methods
• Sum-of-squares lower bounds for planted clique
• Curse of Heterogeneity: Computational Barriers in Sparse Mixture Models and Phase Retrieval
• Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
• Counterexamples to the Low-Degree Conjecture

Cited by in corpus (4)

• Computational Barriers to Estimation from Low-Degree Polynomials
• Statistical Query Lower Bounds for Tensor PCA
• Hypothesis testing with low-degree polynomials in the Morris class of exponential families
• Precise Error Rates for Computationally Efficient Testing