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.
Description
[2005.08099] Reducibility and Statistical-Computational Gaps from Secret Leakage
Links and resources
Tags
community