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

arXiv: https://arxiv.org/abs/2211.03827 · HTML: https://mlsanity.com/paper/2211.03827/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 43 references that are in the map.
- First posted on arXiv 7 Nov 2022.

## Builds on (most cited first, 21 of 21)

- [Tensorizing Neural Networks](https://mlsanity.com/paper/1509.06569/) (2015)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [The estimation error of general first order methods](https://mlsanity.com/paper/2002.12903/) (2020)
- [Learning Mixtures of Gaussians in High Dimensions](https://mlsanity.com/paper/1503.00424/) (2015)
- [Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method](https://mlsanity.com/paper/1407.1543/) (2014)
- [Polynomial-time Tensor Decompositions with Sum-of-Squares](https://mlsanity.com/paper/1610.01980/) (2016)
- [Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updates](https://mlsanity.com/paper/1402.5180/) (2014)
- [On the Optimization Landscape of Tensor Decompositions](https://mlsanity.com/paper/1706.05598/) (2017)
- [Finite Sample Analysis of Approximate Message Passing Algorithms](https://mlsanity.com/paper/1606.01800/) (2016)
- [A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models](https://mlsanity.com/paper/2208.03313/) (2022)
- [Fast and robust tensor decomposition with applications to dictionary learning](https://mlsanity.com/paper/1706.08672/) (2017)
- [On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition](https://mlsanity.com/paper/1802.07301/) (2018)
- [Subspace power method for symmetric tensor decomposition](https://mlsanity.com/paper/1912.04007/) (2019)
- [Adversarial Examples in Random Neural Networks with General Activations](https://mlsanity.com/paper/2203.17209/) (2022)
- [Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms](https://mlsanity.com/paper/1504.05287/) (2015)
- [Smoothed Analysis in Unsupervised Learning via Decoupling](https://mlsanity.com/paper/1811.12361/) (2018)
- [Landscape analysis of an improved power method for tensor decomposition](https://mlsanity.com/paper/2110.15821/) (2021)
- [A Robust Spectral Algorithm for Overcomplete Tensor Decomposition](https://mlsanity.com/paper/2203.02790/) (2022)
- [Fast algorithm for overcomplete order-3 tensor decomposition](https://mlsanity.com/paper/2202.06442/) (2022)

## Built on by (most cited first, 3 of 3)

- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)

## Abstract (arXiv)

Tensor decomposition serves as a powerful primitive in statistics and machine learning, and has numerous applications in problems such as learning latent variable models or mixture of Gaussians. 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. Here we present a novel analysis of the dynamics of tensor power iteration from random initialization in the overcomplete regime, where the tensor rank is much greater than its dimension. 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 in polynomial time. 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.