The Kikuchi Hierarchy and Tensor PCA
The Kikuchi Hierarchy and Tensor PCA
复制标题
DOI：
10.1109/focs.2019.000-2
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Alexander S. Wein;A. Alaoui;Cristopher Moore
中科院分区：
文献类型：
--
作者：
Alexander S. Wein;A. Alaoui;Cristopher Moore
对于张量PCA（主成分分析）问题，我们提出了一个新的层次结构，越来越强大的算法，随着运行时间的增加。我们的层次结构类似于平方和（SOS）层次结构，但受到统计物理学和相关算法（如置信传播和AMP（近似消息传递））的启发。我们的level-t算法可以被认为是一个线性化的消息传递算法，它跟踪隐藏变量之间的t-方向依赖关系。具体来说，我们的算法是基于菊池海森，它概括了良好的研究贝特海森高阶菊池自由能的谱方法。众所周知，AMP，统计物理学的旗舰算法，张量PCA的性能比SOS差得多。在这项工作中，我们“赎回”统计物理方法，我们的层次结构给出了一个多项式时间算法匹配的SOS的性能。我们的层次结构也产生了连续的次指数时间算法，我们证明，这些实现了相同的（从理论上讲，最佳的）运行时间和统计功率之间的权衡SOS。我们的证明比以前的工作简单得多，也适用于反驳随机k-XOR公式的相关问题。我们在这里提出的结果适用于张量PCA的所有订单的张量，和k-XOR当k是偶数。我们的方法提出了一种新的途径，系统地获得贝叶斯推理问题的最佳算法，我们的研究结果构成了统一的统计物理和平方和算法设计的方法的一步。
For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime. Our hierarchy is analogous to the sum-of-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms such as belief propagation and AMP (approximate message passing). Our level-t algorithm can be thought of as a linearized message-passing algorithm that keeps track of t-wise dependencies among the hidden variables. Specifically, our algorithms are spectral methods based on the Kikuchi Hessian, which generalizes the well-studied Bethe Hessian to the higher-order Kikuchi free energies. It is known that AMP, the flagship algorithm of statistical physics, has substantially worse performance than SOS for tensor PCA. In this work we 'redeem' the statistical physics approach by showing that our hierarchy gives a polynomial-time algorithm matching the performance of SOS. Our hierarchy also yields a continuum of subexponential-time algorithms, and we prove that these achieve the same (conjecturally optimal) tradeoff between runtime and statistical power as SOS. Our proofs are much simpler than prior work, and also apply to the related problem of refuting random k-XOR formulas. The results we present here apply to tensor PCA for tensors of all orders, and to k-XOR when k is even. Our methods suggest a new avenue for systematically obtaining optimal algorithms for Bayesian inference problems, and our results constitute a step toward unifying the statistical physics and sum-of-squares approaches to algorithm design.