論文の概要: Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models

• arxiv url: http://arxiv.org/abs/2211.03827v3
• Date: Sun, 23 Mar 2025 22:04:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-25 21:22:48.557198
• Title: Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models
• Title（参考訳）: ランダムオーバーコンプリートモデルにおけるテンソルパワーイテレーションの収束に対する下界
• Authors: Yuchen Wu, Kangjie Zhou,
• Abstract要約: ランダムなオーバーコンプリート状態からパワーイテレーションのダイナミクスを新たに解析する。 驚くべきことに、任意の真の成分に電力反復を収束させるためには、緊張的に多くのステップが必要であることが示される。 テンソル分解の一般的な目的関数がパワーパスに沿って厳密に増大していることを証明する。
• 参考スコア（独自算出の注目度）: 1.6567105237454636
• License:
• Abstract: 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.
• Abstract（参考訳）: テンソル分解は統計学や機械学習において強力なプリミティブであり、潜在変数モデルやガウスの混合を学習するといった問題に多くの応用がある。 本稿では、過完全乱数テンソルを分解するためにパワーイテレーションを使うことに焦点をあてる。 テンソルパワーイテレーションの性質を研究する過去の研究は、非自明なデータ独立な初期化を必要とするか、あるいは不完全な状態に制限されている。 さらに、いくつかの論文では、(入力次元の観点から)対数的に多くの反復がテンソル成分の1つを回復するのに十分なことを暗黙的に示唆している。 ここでは、テンソルランクがその次元よりもはるかに大きいオーバーコンプリート状態におけるランダム初期化からテンソルパワー反復の力学を新たに解析する。 意外なことに、テンソルパワー反復の真成分への収束には多項式的な多くのステップが必要であることが示され、これは以前の予想に反する。 一方, 数値実験により, テンソルパワー・イテレーションは, 多項式時間で幅広いパラメータのテンソル成分を復元することに成功した。 さらに実証的な証拠を補うために、テンソル分解の一般的な目的関数が電力反復経路に沿って厳密に増加することを証明した。 提案手法は, 近似メッセージパッシング (AMP) アルゴリズムの解析に応用されたガウス条件付け法に基づく。 この議論の主な要素は条件付き補題であり、AMP型解析を非局所的極限に一般化し、パワーメソッドの多項式的に多くの反復を可能にする。

関連論文リスト

• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• Sharp Analysis of Power Iteration for Tensor PCA [1.9571840167193135]
  リヒャルトおよびモンタナリ2014で導入されたテンソルPCAモデルのパワーアルゴリズムについて検討する。 まず、植込み信号に収束するためにパワーメソッドに必要なイテレーション数について、鋭い境界を定めます。 第二に、我々の分析は、実力の閾値がポリログ(n)因子によって推測されるものよりも小さいことを明らかにしている。
  論文  参考訳（メタデータ） (2024-01-02T05:55:27Z)
• Scalable CP Decomposition for Tensor Learning using GPU Tensor Cores [47.87810316745786]
  本研究では,エクサスケールテンソル分解を支援する圧縮型テンソル分解フレームワークを提案する。 ベースラインと比較すると、エクスカスケール・テンソルは8000倍のテンソルをサポートし、スピードアップは6.95倍である。 また,本手法を遺伝子解析とテンソル層ニューラルネットワークを含む実世界の2つの応用に適用する。
  論文  参考訳（メタデータ） (2023-11-22T21:04:59Z)
• Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
  我々は、ある微分方程式のオイラー・マルヤマ離散化のように見える、より一般で幅広いマルコフ連鎖、伊藤鎖を考える。 伊藤鎖の法則と微分方程式の間の$W_2$-距離の有界性を証明する。
  論文  参考訳（メタデータ） (2023-10-09T18:38:56Z)
• Decomposition of linear tensor transformations [0.0]
  本研究の目的は, 正確なテンソル分解のための数学的枠組みを開発することである。 論文では3つの異なる問題を導出する。
  論文  参考訳（メタデータ） (2023-09-14T16:14:38Z)
• Faster Robust Tensor Power Method for Arbitrary Order [15.090593955414137]
  emphTensor Power Method (TPM) はテンソルの分解において広く使われている手法の1つである。 我々はスケッチ法を適用し、$widetildeO(np-1)$の出力$p$と dimension$n$tensorで実行時間を達成することができる。
  論文  参考訳（メタデータ） (2023-06-01T07:12:00Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• Error Analysis of Tensor-Train Cross Approximation [88.83467216606778]
  我々は, テンソル全体の精度保証を行う。 結果は数値実験により検証され、高次テンソルに対するクロス近似の有用性に重要な意味を持つ可能性がある。
  論文  参考訳（メタデータ） (2022-07-09T19:33:59Z)
• Spectral Learning on Matrices and Tensors [74.88243719463053]
  テンソル分解は行列法で欠落する潜伏効果を拾うことができることを示す。 また,効率的なテンソル分解法を設計するための計算手法についても概説する。
  論文  参考訳（メタデータ） (2020-04-16T22:53:00Z)
• On Recoverability of Randomly Compressed Tensors with Low CP Rank [29.00634848772122]
  測定値の数がモデルパラメータの次数と同じであれば、テンソルは復元可能であることを示す。 我々の証明は, 集合被覆手法を用いて, CPDモデルの下でのテキスト制限等尺性(R.I.P.)を導出することに基づいている。
  論文  参考訳（メタデータ） (2020-01-08T04:44:13Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。