論文の概要: Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA
- arxiv url: http://arxiv.org/abs/2408.06401v2
- Date: Thu, 19 Dec 2024 09:30:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-20 13:27:54.129576
- Title: Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA
- Title(参考訳): 高次元最適化のためのランゲヴィンダイナミクス--マルチスパイクテンソルPCAの場合
- Authors: Gérard Ben Arous, Cédric Gerbelot, Vanessa Piccolo,
- Abstract要約: 本研究では,最大SNRに伴うスパイクの回復に必要なサンプルの複雑さが,シングルスパイクの場合のよく知られたアルゴリズムしきい値と一致することを示す。
重要なステップとして、高次元の軌道力学を捉えるスパイクと相互作用の詳細なキャラクタリゼーションを提供する。
- 参考スコア(独自算出の注目度): 8.435118770300999
- License:
- Abstract: We study nonconvex optimization in high dimensions through Langevin dynamics, focusing on the multi-spiked tensor PCA problem. This tensor estimation problem involves recovering $r$ hidden signal vectors (spikes) from noisy Gaussian tensor observations using maximum likelihood estimation. We study the number of samples required for Langevin dynamics to efficiently recover the spikes and determine the necessary separation condition on the signal-to-noise ratios (SNRs) for exact recovery, distinguishing the cases $p \ge 3$ and $p=2$, where $p$ denotes the order of the tensor. In particular, we show that the sample complexity required for recovering the spike associated with the largest SNR matches the well-known algorithmic threshold for the single-spike case, while this threshold degrades when recovering all $r$ spikes. As a key step, we provide a detailed characterization of the trajectory and interactions of low-dimensional projections that capture the high-dimensional dynamics.
- Abstract(参考訳): 我々は,マルチスパイクテンソルPCA問題に着目し,ランゲヴィンダイナミクスによる高次元の非凸最適化について検討した。
このテンソル推定問題は、最大推定値を用いてノイズの多いガウステンソル観測から$r$隠れ信号ベクトル(スパイクス)を復元することを含む。
本稿では, スパイクを効率よく回収するために必要な試料数について検討し, テンソルの順序を表す$p \ge 3$ と $p=2$ を区別して, 信号-雑音比(SNR)の分離条件を決定する。
特に,最大SNRに関連するスパイクの回収に必要なサンプルの複雑さは,シングルスパイクの場合のよく知られたアルゴリズムしきい値と一致し,このしきい値は,すべての$r$スパイクの回収時に低下することを示した。
重要なステップとして、高次元のダイナミクスを捉える低次元射影の軌跡と相互作用の詳細な特徴を与える。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。