View in EDS

Sharp Analysis of Power Iteration for Tensor PCA.

Saved in:
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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 183637199
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Sharp Analysis of Power Iteration for Tensor PCA.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Yuchen+Wu%22">Yuchen Wu</searchLink><relatesTo>1</relatesTo><i> WUYC14@WHARTON.UPENN.EDU</i><br /><searchLink fieldCode="AR" term="%22Kangjie+Zhou%22">Kangjie Zhou</searchLink><relatesTo>1</relatesTo><i> KANGJIE@STANFORD.EDU</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Machine+Learning+Research%22">Journal of Machine Learning Research</searchLink>. Jan-Dec2024, Vol. 25, p1-42. 42p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Signal-to-noise+ratio%22">Signal-to-noise ratio</searchLink><br /><searchLink fieldCode="DE" term="%22Signals+%26+signaling%22">Signals & signaling</searchLink><br /><searchLink fieldCode="DE" term="%22Logical+prediction%22">Logical prediction</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Literature%22">Literature</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=183637199
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 42
        StartPage: 1
    Subjects:
      – SubjectFull: Signal-to-noise ratio
        Type: general
      – SubjectFull: Signals & signaling
        Type: general
      – SubjectFull: Logical prediction
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Literature
        Type: general
    Titles:
      – TitleFull: Sharp Analysis of Power Iteration for Tensor PCA.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Yuchen Wu
      – PersonEntity:
          Name:
            NameFull: Kangjie Zhou
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: Jan-Dec2024
              Type: published
              Y: 2024
          Identifiers:
            – Type: issn-print
              Value: 15324435
          Numbering:
            – Type: volume
              Value: 25
          Titles:
            – TitleFull: Journal of Machine Learning Research
              Type: main
ResultId 1