論文の概要: Low degree conjecture implies sharp computational thresholds in stochastic block model

• arxiv url: http://arxiv.org/abs/2502.15024v1
• Date: Thu, 20 Feb 2025 20:21:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-24 16:09:15.119252
• Title: Low degree conjecture implies sharp computational thresholds in stochastic block model
• Title（参考訳）: 低次予想は確率ブロックモデルにおけるシャープな計算しきい値を示唆する
• Authors: Jingqiu Ding, Yiding Hua, Lucas Slot, David Steurer,
• Abstract要約: 我々は(拡張)低次予想(対称ブロックモデルにおける[MW23]の最近の形式化)の影響について検討する。 我々は,Kesten-Stigum(KS)しきい値以下で,非リアルタイムアルゴリズムがコミュニティラベルを弱めに復元できることを確立した。 この結果から,ブロックモデルのパラメータの学習において,計算量と統計量との差があることが示唆された。
• 参考スコア（独自算出の注目度）: 3.7873597471903935
• License:
• Abstract: We investigate implications of the (extended) low-degree conjecture (recently formalized in [MW23]) in the context of the symmetric stochastic block model. Assuming the conjecture holds, we establish that no polynomial-time algorithm can weakly recover community labels below the Kesten-Stigum (KS) threshold. In particular, we rule out polynomial-time estimators that, with constant probability, achieve correlation with the true communities that is significantly better than random. Whereas, above the KS threshold, polynomial-time algorithms are known to achieve constant correlation with the true communities with high probability[Mas14,AS15]. To our knowledge, we provide the first rigorous evidence for the sharp transition in recovery rate for polynomial-time algorithms at the KS threshold. Notably, under a stronger version of the low-degree conjecture, our lower bound remains valid even when the number of blocks diverges. Furthermore, our results provide evidence of a computational-to-statistical gap in learning the parameters of stochastic block models. In contrast to prior work, which either (i) rules out polynomial-time algorithms for hypothesis testing with 1-o(1) success probability [Hopkins18, BBK+21a] under the low-degree conjecture, or (ii) rules out low-degree polynomials for learning the edge connection probability matrix [LG23], our approach provides stronger lower bounds on the recovery and learning problem. Our proof combines low-degree lower bounds from [Hopkins18, BBK+21a] with graph splitting and cross-validation techniques. In order to rule out general recovery algorithms, we employ the correlation preserving projection method developed in [HS17].
• Abstract（参考訳）: 対称確率ブロックモデルにおける(拡張された)低次予想(最近[MW23]で形式化された)の影響について検討する。 予想が成り立つと仮定すると、多項式時間アルゴリズムがケステン・スティグム(KS)しきい値以下でコミュニティラベルを弱回復できないことが証明される。 特に、確率が一定であれば、ランダムよりもはるかに良い真のコミュニティとの相関が得られる多項式時間推定器を除外する。 一方、KSしきい値以上の多項式時間アルゴリズムは、確率の高い真のコミュニティ[Mas14,AS15]と一定の相関を達成することが知られている。 我々の知る限り、我々はKSしきい値における多項式時間アルゴリズムの回復率の急激な推移を示す最初の厳密な証拠を提供する。 特に、低次予想のより強いバージョンの下では、ブロックの数が分岐しても下界は有効である。 さらに, 確率ブロックモデルのパラメータの学習において, 計算量と統計量との差があることを示す。 以前の作品とは対照的に、どちらの作品も (i)低次予想の下で、1-o(1)成功確率(ホプキンス18,BBK+21a)を用いた仮説検証のための多項式時間アルゴリズムを規定する、又は (II)エッジ接続確率行列[LG23]を学習するための低次多項式を除外し,本手法は,回復・学習問題に対するより強い下界を与える。 我々の証明は[Hopkins18, BBK+21a]の低次下界とグラフ分割とクロスバリデーション技術を組み合わせたものである。 一般的なリカバリアルゴリズムを除外するために,[HS17]で開発された相関保存投影法を用いる。

関連論文リスト

• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• A Unifying Theory of Thompson Sampling for Continuous Risk-Averse Bandits [91.3755431537592]
  本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。 大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。 リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
  論文  参考訳（メタデータ） (2021-08-25T17:09:01Z)
• Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
  標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。 私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
  論文  参考訳（メタデータ） (2020-11-12T18:58:51Z)
• Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent [29.684442397855197]
  我々は,高次元仮説テストの文脈において,最も普及している2つの制限された計算モデル,統計クエリフレームワークと低次コローラについて検討した。 テスト問題に関する穏やかな条件下では、2種類のアルゴリズムは本質的にはパワーで等価である。 提案手法では, スパースPCA, テンソルPCA, および植木クリッド問題のいくつかの変種に対して, 新たな統計的クエリローバウンドを求める。
  論文  参考訳（メタデータ） (2020-09-13T22:55:18Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)
• Non-Convex Exact Community Recovery in Stochastic Block Model [31.221745716673546]
  近年,対称ブロックモデル(SBM)に基づくグラフのコミュニティ検出が注目されている。 この問題の対数的疎度構造において、提案した2段階法は、$mathcalO(nlog2n/loglog n)$ timeにおいて、情報理論の限界まで正確に2つのコミュニティを復元できることを示す。 また, 提案手法の有効性を実証し, 理論的発展を補完するために, 合成データセットと実データセットの両方で数値実験を行った。
  論文  参考訳（メタデータ） (2020-06-29T07:03:27Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits [9.427635404752936]
  我々は2つのクラスタリングモデル、定数高階クラスタリング(CHC)とランク1高階クラスタリング(ROHC)に焦点を当てる。 我々は,CHCとROHCの検出/回復が統計的に可能である信号対雑音比の境界を同定する。 信号対雑音比がしきい値以上である場合に、信頼性の高い検出と回復を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-21T15:53:44Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。 これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
  論文  参考訳（メタデータ） (2020-05-07T19:59:51Z)

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

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