A Smooth Computational Transition in Tensor PCA

• URL: http://arxiv.org/abs/2509.09904v1
• Date: Fri, 12 Sep 2025 00:21:20 GMT
• Title: A Smooth Computational Transition in Tensor PCA
• Authors: Zhangsong Li,
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an efficient algorithm for tensor PCA based on counting a specific family of weighted hypergraphs. For the order-$p$ tensor PCA problem where $p \geq 3$ is a fixed integer, we show that when the signal-to-noise ratio is $\lambda n^{-\frac{p}{4}}$ where $\lambda=\Omega(1)$, our algorithm succeeds and runs in time $n^{C+o(1)}$ where $C=C(\lambda)$ is a constant depending on $\lambda$. This algorithm improves a poly-logarithmic factor compared to previous algorithms based on the Sum-of-Squares hierarchy \cite{HSS15} or based on the Kikuchi hierarchy in statistical physics \cite{WEM19}. Furthermore, our result shows a smooth tradeoff between the signal-to-noise ratio and the computational cost in this problem, thereby confirming a conjecture posed in \cite{KWB22}.

Related papers

• The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model [0.0]
  We study the computational task of detecting and estimating correlated signals in a pair of spiked Wigner matrices.<n>An algorithm can leverage the correlation between the spikes to detect and estimate the signals even in regimes where efficiently recovering either $x$ from $X$ alone or $y$ from $Y$ alone is believed to be computationally infeasible.
  arXiv  Detail & Related papers  (2025-11-08T15:23:44Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Robust random graph matching in Gaussian models via vector approximate message passing [0.0]
  We propose an efficient random graph matching type algorithm that is robust under any adversarial perturbations of $n1-o(1)$ size.<n>Our algorithm is the first efficient random graph matching type algorithm that is robust under any adversarial perturbations of $n1-o(1)$ size.
  arXiv  Detail & Related papers  (2024-12-21T03:15:38Z)
• Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
  We develop a general efficient algorithm for em implicit moment tensor complexity.<n>By leveraging our implicit moment estimation algorithm, we obtain the first $mathrmpoly(d, k, 1/epsilon)$-time learning algorithms for the following models.
  arXiv  Detail & Related papers  (2024-11-23T23:13:24Z)
• A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
  We study the algorithmic problem of sparse mean estimation in the presence of adversarial outliers. Our main contribution is an algorithm for robust sparse mean estimation which runs in emphsubquadratic time using $mathrmpoly(k,log d,1/epsilon)$ samples.
  arXiv  Detail & Related papers  (2024-03-07T18:23:51Z)
• 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)
• Sparse PCA Beyond Covariance Thresholding [2.311583680973075]
  We show that for every $t ll k$ there exists an algorithm running in time $ncdot dO(t)$ that solves this problem as long as [ gtrsim fracksqrtntsqrtln(2 + td/k2)$. We provide time algorithms for the sparse planted vector problem that have better guarantees than the state of the art in some regimes.
  arXiv  Detail & Related papers  (2023-02-20T18:45:24Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  We study low rank approximation of tensors, focusing on the tensor train and Tucker decompositions. For tensor train decomposition, we give a bicriteria $(1 + eps)$-approximation algorithm with a small bicriteria rank and $O(q cdot nnz(A))$ running time. In addition, we extend our algorithm to tensor networks with arbitrary graphs.
  arXiv  Detail & Related papers  (2022-07-15T11:55:09Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• The Complexity of Sparse Tensor PCA [1.90365714903665]
  For any $1 leq leq k$, our algorithms recover the sparse vector for signal-to-noise ratio $lambda geq tildemathcalO (sqrtt cdot (k/t)p/2)$ in time. Even in the restricted case of PCA, known algorithms only recover the sparse vectors for $lambda geq tildemathcalO(k cdot r) while our algorithms require $lambda ge
  arXiv  Detail & Related papers  (2021-06-11T10:57:00Z)
• The Kikuchi Hierarchy and Tensor PCA [50.840260149979265]
  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.
  arXiv  Detail & Related papers  (2019-04-08T06:26:35Z)

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.