Fugu-MT 論文翻訳(概要): High-dimensional optimization for multi-spiked tensor PCA

論文の概要: 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に依存する。

関連論文リスト

Guaranteed Nonconvex Low-Rank Tensor Estimation via Scaled Gradient Descent [4.123899820318987]
本稿では,テンソル因子を直接推定するスケールド勾配降下法(ScaledGD)を提案する。理論上、ScaledGD は基底真理低ランクテンソルの条件数に依存しない定数速度で線形収束を達成する。虚弱条件下での低ランクテンソル推定の収束速度を加速する上でのScaledGDの有効性を示す数値的な例を提供する。
論文参考訳（メタデータ） (2025-01-03T08:26:01Z)
Permutation recovery of spikes in noisy high-dimensional tensor estimation [8.435118770300999]
マルチスパイクテンソル問題に対する高次元流れのダイナミクスについて検討する。我々の研究は, 正確な回収に必要なSNRの試料分離条件を決定する論文[Ben A, Gerbelot, Langevin]に基づく。
論文参考訳（メタデータ） (2024-12-19T08:59:49Z)
Stochastic gradient descent in high dimensions for multi-spiked tensor PCA [8.435118770300999]
マルチスパイクテンソルモデルにおけるオンライン勾配勾配の高次元におけるダイナミクスについて検討する。我々は、スパイクが「逐次除去」と呼ばれるプロセスで順次回収されることを発見した。
論文参考訳（メタデータ） (2024-10-23T17:20:41Z)
Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文参考訳（メタデータ） (2023-11-07T17:39:17Z)
Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文参考訳（メタデータ） (2021-08-25T21:30:27Z)
Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文参考訳（メタデータ） (2021-06-29T12:49:54Z)
Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文参考訳（メタデータ） (2021-05-27T23:41:01Z)
Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文参考訳（メタデータ） (2020-10-19T15:23:18Z)
Spatio-Temporal Tensor Sketching via Adaptive Sampling [15.576219771198389]
適応型サンプリングを用いてテンソルスライスを時間的ストリーミング形式で圧縮する新しいテンソル分解フレームワークであるSkeTenSmoothを提案する。ニューヨーク市のYellow Taxiデータによる実験によると、SkeTenSmoothはメモリコストとランダムサンプリング率を大幅に削減する。
論文参考訳（メタデータ） (2020-06-21T23:55:10Z)
The Heavy-Tail Phenomenon in SGD [7.366405857677226]
最小損失のHessianの構造に依存すると、SGDの反復はエンフェビーテールの定常分布に収束する。深層学習におけるSGDの行動に関する知見に分析結果を変換する。
論文参考訳（メタデータ） (2020-06-08T16:43:56Z)
Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。この場合、最先端の結果を上回る新たな複雑さが証明される。本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
論文参考訳（メタデータ） (2020-05-21T17:05:27Z)

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

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