Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models

• URL: http://arxiv.org/abs/2211.03827v1
• Date: Mon, 7 Nov 2022 19:23:51 GMT
• Title: Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models
• Authors: Yuchen Wu and Kangjie Zhou
• Abstract summary: We show that tensorly many steps are necessary for convergence of tensor power iteration to any true component. We prove that a popular objective function for tensor decomposition is strictly increasing along the power iteration path.
• Score: 3.7565501074323224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tensor decomposition serves as a powerful primitive in statistics and machine learning. In this paper, we focus on using power iteration to decompose an overcomplete random tensor. Past work studying the properties of tensor power iteration either requires a non-trivial data-independent initialization, or is restricted to the undercomplete regime. Moreover, several papers implicitly suggest that logarithmically many iterations (in terms of the input dimension) are sufficient for the power method to recover one of the tensor components. In this paper, we analyze the dynamics of tensor power iteration from random initialization in the overcomplete regime. Surprisingly, we show that polynomially many steps are necessary for convergence of tensor power iteration to any of the true component, which refutes the previous conjecture. On the other hand, our numerical experiments suggest that tensor power iteration successfully recovers tensor components for a broad range of parameters, despite that it takes at least polynomially many steps to converge. To further complement our empirical evidence, we prove that a popular objective function for tensor decomposition is strictly increasing along the power iteration path. Our proof is based on the Gaussian conditioning technique, which has been applied to analyze the approximate message passing (AMP) algorithm. The major ingredient of our argument is a conditioning lemma that allows us to generalize AMP-type analysis to non-proportional limit and polynomially many iterations of the power method.

Related papers

• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Sharp Analysis of Power Iteration for Tensor PCA [1.9571840167193135]
  We investigate the power algorithm for the tensor PCA model introduced in Richard and Montanari 2014. Our contributions are threefold: First, we establish sharp bounds on the number of iterations required for power method to converge to the planted signal. Second, our analysis reveals that the actual threshold for power is smaller than the one conjectured in literature by a polylog(n) factor.
  arXiv  Detail & Related papers  (2024-01-02T05:55:27Z)
• Scalable CP Decomposition for Tensor Learning using GPU Tensor Cores [47.87810316745786]
  We propose a compression-based tensor decomposition framework, namely the exascale-tensor, to support exascale tensor decomposition. Compared to the baselines, the exascale-tensor supports 8,000x larger tensors and a speedup up to 6.95x. We also apply our method to two real-world applications, including gene analysis and tensor layer neural networks.
  arXiv  Detail & Related papers  (2023-11-22T21:04:59Z)
• Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
  We consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Differential Equation. We prove the bound in $W_2$-distance between the laws of our Ito chain and differential equation.
  arXiv  Detail & Related papers  (2023-10-09T18:38:56Z)
• Decomposition of linear tensor transformations [0.0]
  The aim of this paper is to develop a mathematical framework for exact tensor decomposition. In the paper three different problems will be carried out to derive.
  arXiv  Detail & Related papers  (2023-09-14T16:14:38Z)
• Faster Robust Tensor Power Method for Arbitrary Order [15.090593955414137]
  emphTensor power method (TPM) is one of the widely-used techniques in the decomposition of tensors. We apply sketching method, and we are able to achieve the running time of $widetildeO(np-1)$ on the power $p$ and dimension $n$ tensor.
  arXiv  Detail & Related papers  (2023-06-01T07:12:00Z)
• 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)
• Error Analysis of Tensor-Train Cross Approximation [88.83467216606778]
  We provide accuracy guarantees in terms of the entire tensor for both exact and noisy measurements. Results are verified by numerical experiments, and may have important implications for the usefulness of cross approximations for high-order tensors.
  arXiv  Detail & Related papers  (2022-07-09T19:33:59Z)
• Spectral Learning on Matrices and Tensors [74.88243719463053]
  We show that tensor decomposition can pick up latent effects that are missed by matrix methods. We also outline computational techniques to design efficient tensor decomposition methods.
  arXiv  Detail & Related papers  (2020-04-16T22:53:00Z)
• On Recoverability of Randomly Compressed Tensors with Low CP Rank [29.00634848772122]
  We show that if the number of measurements is on the same order of magnitude as that of the model parameters, then the tensor is recoverable. Our proof is based on deriving a textitrestricted isometry property (R.I.P.) under the CPD model via set covering techniques.
  arXiv  Detail & Related papers  (2020-01-08T04:44:13Z)

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.