論文の概要: The Kikuchi Hierarchy and Tensor PCA

• arxiv url: http://arxiv.org/abs/1904.03858v3
• Date: Tue, 19 Aug 2025 18:39:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-21 16:52:41.013485
• Title: The Kikuchi Hierarchy and Tensor PCA
• Title（参考訳）: 菊池階層とテンソルPCA
• Authors: Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore,
• Abstract要約: テンソルPCA(主成分分析)問題に対して,ランタイムの増大を伴うアルゴリズムの階層化を提案する。 我々の階層は、SOS(sum-of-squares)階層に似ているが、代わりに統計物理学や関連するアルゴリズムにインスパイアされている。
• 参考スコア（独自算出の注目度）: 50.840260149979265
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime. Our hierarchy is analogous to the sum-of-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms such as belief propagation and AMP (approximate message passing). Our level-$\ell$ algorithm can be thought of as a linearized message-passing algorithm that keeps track of $\ell$-wise dependencies among the hidden variables. Specifically, our algorithms are spectral methods based on the Kikuchi Hessian, which generalizes the well-studied Bethe Hessian to the higher-order Kikuchi free energies. It is known that AMP, the flagship algorithm of statistical physics, has substantially worse performance than SOS for tensor PCA. In this work we 'redeem' the statistical physics approach by showing that our hierarchy gives a polynomial-time algorithm matching the performance of SOS. Our hierarchy also yields a continuum of subexponential-time algorithms, and we prove that these achieve the same (conjecturally optimal) tradeoff between runtime and statistical power as SOS. Our proofs are much simpler than prior work, and also apply to the related problem of refuting random $k$-XOR formulas. The results we present here apply to tensor PCA for tensors of all orders, and to $k$-XOR when $k$ is even. Our methods suggest a new avenue for systematically obtaining optimal algorithms for Bayesian inference problems, and our results constitute a step toward unifying the statistical physics and sum-of-squares approaches to algorithm design.
• Abstract（参考訳）: テンソルPCA(主成分分析)問題に対して,ランタイムの増大を伴うアルゴリズムの階層化を提案する。 我々の階層は、SOS(sum-of-squares)階層に似ているが、代わりに統計物理学や、信念の伝播やAMP(approximate message passing)といった関連するアルゴリズムにインスパイアされている。 我々のレベル$$ell$アルゴリズムは、隠された変数間の$$$ell$-wise依存を追跡する線形化メッセージパスアルゴリズムと考えることができる。 具体的には,Bethe Hessianを高次キクチ自由エネルギーに一般化する,菊池ヘシアンに基づくスペクトル法について述べる。 統計物理のフラッグシップアルゴリズムであるAMPは、テンソルPCAのSOSよりも著しく性能が悪いことが知られている。 本研究では,SOSの性能にマッチする多項式時間アルゴリズムを,階層構造が与えることを示すことによって,統計物理学的アプローチを「再考」する。 我々の階層は、サブ指数時間アルゴリズムの連続性も生み出しており、これらがSOSと同じランタイムと統計パワーの(客観的に最適な)トレードオフを達成することを証明している。 我々の証明は以前の研究よりもはるかに単純であり、また、ランダムな$k$-XOR式を論証する関連する問題にも適用できる。 ここでは、すべての順序のテンソルに対するテンソルPCAと、$k$が偶数であるときに$k$-XORに適用する。 提案手法は,ベイズ推論問題に対する最適アルゴリズムを体系的に獲得するための新しい手法を提案する。

関連論文リスト

• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
  本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。 そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。 我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
  論文  参考訳（メタデータ） (2023-01-23T19:13:25Z)
• Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix [1.74048653626208]
  我々は$similarity$matrix$W$で動作するアルゴリズムの性能を調査し、$W_ij$は$i$と$j$の両方を含むハイパーエッジの数を報告する。 ほぼ線形な実行時間を持つ単純かつ高効率なスペクトルアルゴリズムを設計し,min-bisectionしきい値を達成することを示す。
  論文  参考訳（メタデータ） (2022-08-23T15:22:05Z)
• Alternating Mahalanobis Distance Minimization for Stable and Accurate CP Decomposition [4.847980206213335]
  本稿では, テンソルの特異値とベクトルを導出するための新しい定式化を導入する。 このアルゴリズムのサブスウィープは、既知のランクの正確なCPDに対して超線形収束率を達成することができることを示す。 すると、アルゴリズムは各因子に対するマハラノビス距離を最適化するものであり、基底距離は他の因子に依存していると見なす。
  論文  参考訳（メタデータ） (2022-04-14T19:56:36Z)
• 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)
• A Fast PC Algorithm with Reversed-order Pruning and A Parallelization Strategy [22.31288740171446]
  PCアルゴリズムは観測データに基づく因果構造発見のための最先端のアルゴリズムである。 条件付き独立テストが実行された場合、最悪の場合、計算コストがかかる可能性がある。 これにより、タスクが数百から数千のノードを含む場合、アルゴリズムは計算的に難解になる。 本稿では、2つのノードを独立にレンダリングする条件セットが非特異であり、特定の冗長ノードを含む場合、結果の精度を犠牲にしない、という批判的な観察を提案する。
  論文  参考訳（メタデータ） (2021-09-10T02:22:10Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)

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

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