Bibliographic Details
| Title: |
Sharp Analysis of Power Iteration for Tensor PCA. |
| Authors: |
Yuchen Wu1 WUYC14@WHARTON.UPENN.EDU, Kangjie Zhou1 KANGJIE@STANFORD.EDU |
| Source: |
Journal of Machine Learning Research. Jan-Dec2024, Vol. 25, p1-42. 42p. |
| Subjects: |
Signal-to-noise ratio, Signals & signaling, Logical prediction, Algorithms, Literature |
| Abstract: |
We investigate the power iteration algorithm for the tensor PCA model introduced in Richard and Montanari (2014). Previous work studying the properties of tensor power iteration is either limited to a constant number of iterations, or requires a non-trivial dataindependent initialization. In this paper, we move beyond these limitations and analyze the dynamics of randomly initialized tensor power iteration up to polynomially many steps. Our contributions are threefold: First, we establish sharp bounds on the number of iterations required for power method to converge to the planted signal, for a broad range of the signal-to-noise ratios. Second, our analysis reveals that the actual algorithmic threshold for power iteration is smaller than the one conjectured in the literature by a polylog(n) factor, where n is the ambient dimension. Finally, we propose a simple and effective stopping criterion for power iteration, which provably outputs a solution that is highly correlated with the true signal. Extensive numerical experiments verify our theoretical results. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of Machine Learning Research is the property of Microtome Publishing and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
