論文の概要: High-dimensional optimization for multi-spiked tensor PCA

• arxiv url: http://arxiv.org/abs/2408.06401v1
• Date: Mon, 12 Aug 2024 12:09:25 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-14 19:38:59.949733
• Title: High-dimensional optimization for multi-spiked tensor PCA
• Title（参考訳）: マルチスパイクテンソルPCAの高次元最適化
• Authors: Gérard Ben Arous, Cédric Gerbelot, Vanessa Piccolo,
• Abstract要約: 本研究では,2つの局所最適化アルゴリズム,オンライン勾配勾配(SGD)と勾配流のダイナミクスについて検討する。 勾配流の場合、第1のスパイクを効率的に回収するアルゴリズムしきい値も$Np-2$である。 この結果は, 推定器とスパイクの相関関係を記述した低次元系の詳細な解析によって得られた。
• 参考スコア（独自算出の注目度）: 8.435118770300999
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the dynamics of two local optimization algorithms, online stochastic gradient descent (SGD) and gradient flow, within the framework of the multi-spiked tensor model in the high-dimensional regime. This multi-index model arises from the tensor principal component analysis (PCA) problem, which aims to infer $r$ unknown, orthogonal signal vectors within the $N$-dimensional unit sphere through maximum likelihood estimation from noisy observations of an order-$p$ tensor. We determine the number of samples and the conditions on the signal-to-noise ratios (SNRs) required to efficiently recover the unknown spikes from natural initializations. Specifically, we distinguish between three types of recovery: exact recovery of each spike, recovery of a permutation of all spikes, and recovery of the correct subspace spanned by the signal vectors. We show that with online SGD, it is possible to recover all spikes provided a number of sample scaling as $N^{p-2}$, aligning with the computational threshold identified in the rank-one tensor PCA problem [Ben Arous, Gheissari, Jagannath 2020, 2021]. For gradient flow, we show that the algorithmic threshold to efficiently recover the first spike is also of order $N^{p-2}$. However, recovering the subsequent directions requires the number of samples to scale as $N^{p-1}$. Our results are obtained through a detailed analysis of a low-dimensional system that describes the evolution of the correlations between the estimators and the spikes. In particular, the hidden vectors are recovered one by one according to a sequential elimination phenomenon: as one correlation exceeds a critical threshold, all correlations sharing a row or column index decrease and become negligible, allowing the subsequent correlation to grow and become macroscopic. The sequence in which correlations become macroscopic depends on their initial values and on the associated SNRs.
• Abstract（参考訳）: 高次元状態におけるマルチスパイクテンソルモデルの枠組みの中で,2つの局所最適化アルゴリズム,オンライン確率勾配勾配勾配(SGD)と勾配流のダイナミクスについて検討した。 このマルチインデックスモデルは、$r$未知の直交信号ベクトルを$N$次元単位球内で推定することを目的としたテンソル主成分分析(PCA)問題から生じる。 自然初期化から未知のスパイクを効率的に回収するために必要なサンプル数と信号対雑音比(SNR)の条件を決定する。 具体的には、各スパイクの正確なリカバリ、すべてのスパイクの置換のリカバリ、信号ベクトルによる正しいサブ空間のリカバリの3つのタイプを区別する。 オンラインSGDでは、ランク1テンソルPCA問題[Ben Arous, Gheissari, Jagannath 2020, 2021]で特定された計算しきい値と整合して、サンプルスケーリングを$N^{p-2}$とするすべてのスパイクを復元することが可能である。 勾配流の場合、第1のスパイクを効率的に回収するアルゴリズムしきい値も$N^{p-2}$である。 しかし、その後の方向を復元するには、サンプルの数を$N^{p-1}$にスケールする必要がある。 この結果は, 推定器とスパイクの相関関係を記述した低次元系の詳細な解析によって得られた。 特に、1つの相関が臨界しきい値を超えると、行または列インデックスを共有するすべての相関が減少し、無視され、その後の相関が成長してマクロ化される。 相関がマクロとなるシーケンスは、初期値と関連するSNRに依存する。

関連論文リスト

• Stochastic gradient descent in high dimensions for multi-spiked tensor PCA [8.435118770300999]
  マルチスパイクテンソルモデルにおけるオンライン勾配勾配の高次元におけるダイナミクスについて検討する。 我々は、スパイクが「逐次除去」と呼ばれるプロセスで順次回収されることを発見した。
  論文  参考訳（メタデータ） (2024-10-23T17:20:41Z)
• Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
  ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。 得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。 我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
  論文  参考訳（メタデータ） (2024-10-07T15:02:48Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。 i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。 その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
  論文  参考訳（メタデータ） (2024-04-18T16:46:08Z)
• Sliding down the stairs: how correlated latent variables accelerate learning with neural networks [8.107431208836426]
  入力累積に符号化された方向に沿った潜伏変数間の相関が高次相関から学習を高速化することを示す。 この結果は2層ニューラルネットワークのシミュレーションで確認された。
  論文  参考訳（メタデータ） (2024-04-12T17:01:25Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Retire: Robust Expectile Regression in High Dimensions [3.9391041278203978]
  ペナル化量子化法と期待回帰法は、高次元データの異方性検出に有用な手段を提供する。 我々は,頑健な期待回帰(退職)を提案し,研究する。 提案手法は半平滑なニュートン座標降下アルゴリズムにより効率よく解けることを示す。
  論文  参考訳（メタデータ） (2022-12-11T18:03:12Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  我々は、ラベルが$r$のニューロンを持つターゲットネットワークの符号によって決定されるとき、勾配流が方向収束することを示す。 我々の結果は、標本サイズによらず、幅が$tildemathcalO(r)$である、緩やかなオーバーパラメータ化をすでに維持しているかもしれない。
  論文  参考訳（メタデータ） (2022-05-18T16:57:10Z)
• Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks [83.58049517083138]
  勾配勾配勾配を用いた2層ReLUネットワークについて検討する。 SGDは単純な解に偏りがあることが示される。 また,データポイントと異なる場所で結び目が発生するという経験的証拠も提供する。
  論文  参考訳（メタデータ） (2021-11-03T15:14:20Z)
• The Heavy-Tail Phenomenon in SGD [7.366405857677226]
  最小損失のHessianの構造に依存すると、SGDの反復はエンフェビーテールの定常分布に収束する。 深層学習におけるSGDの行動に関する知見に分析結果を変換する。
  論文  参考訳（メタデータ） (2020-06-08T16:43:56Z)

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

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