The Kikuchi Hierarchy and Tensor PCA

• URL: http://arxiv.org/abs/1904.03858v3
• Date: Tue, 19 Aug 2025 18:39:57 GMT
• Title: The Kikuchi Hierarchy and Tensor PCA
• Authors: Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore,
• Abstract summary: For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime.<n>Our hierarchy is analogous to the sum-of-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms.
• Score: 50.840260149979265
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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-$\ell$ algorithm can be thought of as a linearized message-passing algorithm that keeps track of $\ell$-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.

Related papers

• Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity [4.655159257282136]
  A major consideration in algorithms for phase retrieval is robustness against measurement errors.<n>In this paper, we study efficient algorithms for robust phase retrieval with heavy-tailed noise.
  arXiv  Detail & Related papers  (2026-01-26T08:06:16Z)
• A Smooth Computational Transition in Tensor PCA [0.0]
  We propose an efficient algorithm for tensor PCA based on counting a specific family of weighted hypergraphs.<n>Our result shows a smooth tradeoff between the signal-to-noise ratio and the computational cost in this problem.
  arXiv  Detail & Related papers  (2025-09-12T00:21:20Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
  This paper improves the state-of-the-art rate of a first-order algorithm for solving entropy regularized optimal transport. We propose an accelerated primal-dual mirror descent algorithm with variance reduction. Our algorithm may inspire more research to develop accelerated primal-dual algorithms that have rate $widetildeO(n2/epsilon)$ for solving OT.
  arXiv  Detail & Related papers  (2023-01-23T19:13:25Z)
• Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix [1.74048653626208]
  We study the performance of algorithms which operate on the $similarity$matrix $W$, where $W_ij$ reports the number of hyperedges containing both $i$ and $j$. We design a simple and highly efficient spectral algorithm with nearly linear runtime and show that it achieves the min-bisection threshold.
  arXiv  Detail & Related papers  (2022-08-23T15:22:05Z)
• Alternating Mahalanobis Distance Minimization for Stable and Accurate CP Decomposition [4.847980206213335]
  We introduce a new formulation for deriving singular values and vectors of a tensor by considering the critical points of a function different from what is used in the previous work. We show that a subsweep of this algorithm can achieve a superlinear convergence rate for exact CPD with known rank. We then view the algorithm as optimizing a Mahalanobis distance with respect to each factor with ground metric dependent on the other factors.
  arXiv  Detail & Related papers  (2022-04-14T19:56:36Z)
• Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes [7.648784748888189]
  Selective Multiple Power Iterations (SMPI) is a new algorithm to address the important problem that consists in recovering a spike. We show that these unexpected performances are due to a powerful mechanism in which the noise plays a key role for the signal recovery. These results may have strong impact on both practical and theoretical applications.
  arXiv  Detail & Related papers  (2021-12-23T01:46:41Z)
• A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy [22.31288740171446]
  The PC algorithm is the state-of-the-art algorithm for causal structure discovery on observational data. It can be computationally expensive in the worst case due to the conditional independence tests are performed. This makes the algorithm computationally intractable when the task contains several hundred or thousand nodes. We propose a critical observation that the conditional set rendering two nodes independent is non-unique, and including certain redundant nodes do not sacrifice result accuracy.
  arXiv  Detail & Related papers  (2021-09-10T02:22:10Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  We study the fundamental task of list-decodable mean estimation in high dimensions. Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset. A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
  arXiv  Detail & Related papers  (2020-11-19T17:21:37Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.