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

• arxiv url: http://arxiv.org/abs/2211.03827v1
• Date: Mon, 7 Nov 2022 19:23:51 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-09 15:53:42.062200
• Title: Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models
• Title（参考訳）: ランダム超完全モデル上のテンソルパワー反復の収束に対する下限
• Authors: Yuchen Wu and Kangjie Zhou
• Abstract要約: テンソルパワー反復を任意の真の成分に収束させるためには、テンソルの多くのステップが必要であることを示す。 我々は、テンソル分解の一般的な目的関数が、電力反復経路に沿って厳密に増大していることを証明する。
• 参考スコア（独自算出の注目度）: 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.
• 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)

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

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