論文の概要: Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics
- arxiv url: http://arxiv.org/abs/2610.38206v1
- Date: Wed, 28 Oct 2026 03:01:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-31 05:25:12.364649
- Title: Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics
- Title（参考訳）: A averageaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part II: Langevin Dynamics
- Abstract要約: 局所マルコフ連鎖は非形式的なコールドスタートからアルゴリズムしきい値までずっと成功できることを示す。
その結果,局所マルコフ連鎖は非形式的コールドスタートからアルゴリズムしきい値までずっと成功できることを示した。
- 参考スコア（独自算出の注目度）: 5.281099132799764
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the tensor principal components analysis (tensor PCA) problem on the sphere, in which we are asked to recover an unknown vector in $\mathcal{S}_N=\{x\in\mathbb{R}^N:\lVert x\rVert^2=N\}$ from a noisy observation of its $k$-th tensor power, for a fixed $k\ge3$. Tensor PCA exhibits a well-studied information-computation gap: global algorithms such as spectral methods and sum-of-squares work above an algorithmic threshold, below which we know matching lower bounds (against these and some other restricted models of computation). In contrast, local algorithms such as Markov chains were only known to succeed from a random initialization at a polynomially larger signal-to-noise ratio, and were believed to be inferior to global algorithms for tensor PCA. Continuing the program initiated in Part I [arXiv:2610.16705], we show that spherical Langevin dynamics, when supplemented with annealing and ergodic averaging, achieves polynomial-time strong recovery above the algorithmic threshold from a uniformly random initialization. Together with Part I, our results demonstrate that local Markov chains can succeed all the way down to the algorithmic threshold from an uninformative cold start.
- Abstract（参考訳）: 球面上のテンソル主成分解析(テンソルPCA)問題は、固定された$k\ge3$に対して、k$-番目のテンソルパワーのノイズ観測から、$\mathcal{S}_N=\{x\in\mathbb{R}^N:\lVert x\rVert^2=N\}$の未知ベクトルを復元するよう求められている。
スペクトル法や2乗和のような大域的アルゴリズムはアルゴリズムのしきい値より上で動作し、下記の下位境界が一致する(これらに加えて、いくつかの制限された計算モデルも含む)。
対照的にマルコフ連鎖のような局所アルゴリズムは、多項式的に大きい信号-雑音比でのランダム初期化からのみ成功し、テンソルPCAのグローバルアルゴリズムよりも劣ると考えられていた。
第1部 [arXiv:2610.16705] で開始されたプログラムを継続すると, 球面ランゲヴィンダイナミクスがアニーリングとエルゴード平均化を補うと, 均一にランダムな初期化からアルゴリズムしきい値を超える多項式時間強い回復が得られることを示す。
パートIとともに,局所マルコフ連鎖が非形式的コールドスタートからアルゴリズムしきい値までずっと成功できることを示した。
関連論文リスト
- Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part I: Glauber Dynamics [5.281099132799764]
主成分分析(テンソルPCA)問題では、未知ベクトルを$pm1N$で復元するよう依頼される。
エルゴード平均化を補足したグラウバー力学は,アルゴリズムのしきい値を超える強い回復を達成できることを示す。
論文 参考訳（メタデータ） (2026-10-12T12:41:41Z) - Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity [4.655159257282136]
位相探索のアルゴリズムにおける主要な考慮事項は、測定誤差に対する堅牢性である。
本稿では,重み付き雑音を用いたロバスト位相探索のための効率的なアルゴリズムについて検討する。
論文 参考訳（メタデータ） (2026-01-26T08:06:16Z) - A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA [8.435118770300999]
本研究では,最大SNRに伴うスパイクの回復に必要なサンプルの複雑さが,シングルスパイクの場合のよく知られたアルゴリズムしきい値と一致することを示す。
重要なステップとして、高次元の軌道力学を捉えるスパイクと相互作用の詳細なキャラクタリゼーションを提供する。
論文 参考訳（メタデータ） (2024-08-12T12:09:25Z) - Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
論文 参考訳（メタデータ） (2024-04-29T14:33:24Z) - Higher degree sum-of-squares relaxations robust against oblivious
outliers [14.58610686291355]
我々は、$Y=X*+N$という形の推定モデルを考える。
本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
論文 参考訳（メタデータ） (2022-11-14T13:09:12Z) - Selective Multiple Power Iteration: from Tensor PCA to gradient-based
exploration of landscapes [7.648784748888189]
Selective Multiple Power Iterations (SMPI) はスパイクを回復する重要な問題に対処する新しいアルゴリズムである。
これらの予期せぬ性能は、ノイズが信号の回復に重要な役割を果たす強力なメカニズムに起因していることを示す。
これらの結果は、実用的および理論的応用の両方に強い影響を与える可能性がある。
論文 参考訳（メタデータ） (2021-12-23T01:46:41Z) - Lattice partition recovery with dyadic CART [79.96359947166592]
我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。
この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。
本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。
我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
論文 参考訳（メタデータ） (2021-05-27T23:41:01Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - The Kikuchi Hierarchy and Tensor PCA [50.840260149979265]
テンソルPCA(主成分分析)問題に対して,ランタイムの増大を伴うアルゴリズムの階層化を提案する。
我々の階層は、SOS(sum-of-squares)階層に似ているが、代わりに統計物理学や関連するアルゴリズムにインスパイアされている。
論文 参考訳（メタデータ） (2019-04-08T06:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。