论文标题
秘密泄漏的降低性和统计计算差距
Reducibility and Statistical-Computational Gaps from Secret Leakage
论文作者
论文摘要
在现代统计，计算机科学和统计物理学中，统计计算差距的推理问题无处不在。尽管从限制类别的算法类别的失败中表现出了这些差距，但在统计推断中朝着更传统的基于基于还原的计算复杂性的方法取得了进展一直受到限制。现有的减少在很大程度上仅限于具有相似结构的推理问题 - 主要是在可表示为稀疏子质信号和噪声矩阵的问题之间绘制的，这与种植集团的常见硬度假设相似。 这项工作的见解是，对种植的集团猜想（秘密泄漏种植的集团）的略有概括产生了各种新的平均案例减少技术，从而在结构截然不同的问题中产生了降低的网络。 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子图，隐藏分区模型中的检测以及学习稀疏混合物的通用原理。特别是，种植集团猜想的$ K $ - 分支机构变体足以建立我们所有的计算下限。我们的技术还揭示了与组合设计和随机矩阵理论的新联系。这项工作提供了第一个证据，表明扩大的硬度假设（例如秘密泄漏种植的集团）可能是朝着统计问题减少的更完整理论的关键第一步。
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.
