論文の概要: Almost-Optimal Local-Search Methods for Sparse Tensor PCA

• arxiv url: http://arxiv.org/abs/2506.09959v1
• Date: Wed, 11 Jun 2025 17:33:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 06:35:03.17161
• Title: Almost-Optimal Local-Search Methods for Sparse Tensor PCA
• Title（参考訳）: スパーステンソルPCAのほぼ最適局所探索法
• Authors: Max Lovig, Conor Sheehan, Konstantinos Tsirkas, Ilias Zadik,
• Abstract要約: 局所探索法は統計応用に広く用いられている。 最近の研究では「局所計算的」なギャップが明らかになっている。 そこで我々は,このギャップを「埋める」ための一連の局所探索手法を提案する。
• 参考スコア（独自算出の注目度）: 10.249620437941
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Local-search methods are widely employed in statistical applications, yet interestingly, their theoretical foundations remain rather underexplored, compared to other classes of estimators such as low-degree polynomials and spectral methods. Of note, among the few existing results recent studies have revealed a significant "local-computational" gap in the context of a well-studied sparse tensor principal component analysis (PCA), where a broad class of local Markov chain methods exhibits a notable underperformance relative to other polynomial-time algorithms. In this work, we propose a series of local-search methods that provably "close" this gap to the best known polynomial-time procedures in multiple regimes of the model, including and going beyond the previously studied regimes in which the broad family of local Markov chain methods underperforms. Our framework includes: (1) standard greedy and randomized greedy algorithms applied to the (regularized) posterior of the model; and (2) novel random-threshold variants, in which the randomized greedy algorithm accepts a proposed transition if and only if the corresponding change in the Hamiltonian exceeds a random Gaussian threshold-rather that if and only if it is positive, as is customary. The introduction of the random thresholds enables a tight mathematical analysis of the randomized greedy algorithm's trajectory by crucially breaking the dependencies between the iterations, and could be of independent interest to the community.
• Abstract（参考訳）: 局所探索法は統計学的な応用に広く用いられているが、興味深いことに、その理論の基礎は低次多項式やスペクトル法のような他の推定器のクラスと比較して、まだ未解明のままである。 注意すべき点として、近年の研究では、よく研究されているスパーステンソル主成分分析(PCA)の文脈において、局所マルコフ連鎖法の幅広いクラスが他の多項式時間アルゴリズムと比較して顕著な低パフォーマンスを示す「局所計算的」なギャップが明らかになっている。 本研究では、このギャップをモデルの複数の状態において最もよく知られた多項式時間プロシージャに「確実に閉ざす」一連の局所探索手法を提案する。 本フレームワークは,(1)モデルの後部(正規化)に適用される標準グリーディおよびランダム化グリーディアルゴリズム,(2)ランダム化グリーディアルゴリズムが提案された遷移を受理する新しいランダム閾値変種を含む。 ランダムしきい値の導入により、反復間の依存関係を決定的に破ることによって、ランダム化された欲求アルゴリズムの軌道の厳密な数学的解析が可能になる。

関連論文リスト

• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms [14.33758865948252]
  我々は2つの有名なバンディットアルゴリズム、Minimum Empirical Divergence (MED)とThompson Sampling (TS)を再検討する。 MEDがこれらのモデルすべてに最適であることを示すとともに、最適性がすでに知られているTSアルゴリズムの簡単な後悔解析も提供する。
  論文  参考訳（メタデータ） (2023-03-10T16:43:48Z)
• Bregman Power k-Means for Clustering Exponential Family Data [11.434503492579477]
  我々は、ブレグマン発散の下でのハードクラスタリングに関する古典的な研究のアルゴリズム的進歩を橋渡しする。 ブレグマン発散のエレガントな性質は、単純で透明なアルゴリズムで閉形式更新を維持できる。 シミュレーション実験の徹底的な実証分析と降雨データに関するケーススタディを考察し,提案手法はガウス以外の様々なデータ設定において,既存のピア手法よりも優れていることを示した。
  論文  参考訳（メタデータ） (2022-06-22T06:09:54Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。 ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。 ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
  論文  参考訳（メタデータ） (2022-06-14T12:30:11Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)
• A General Method for Robust Learning from Batches [56.59844655107251]
  本稿では,バッチから頑健な学習を行う一般的なフレームワークについて考察し,連続ドメインを含む任意の領域に対する分類と分布推定の限界について考察する。 本手法は,一括分節分類,一括分節,単調,対数凹,ガウス混合分布推定のための,最初の頑健な計算効率の学習アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2020-02-25T18:53:25Z)

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

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