論文の概要: Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models

• arxiv url: http://arxiv.org/abs/2610.08872v1
• Date: Tue, 06 Oct 2026 05:43:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 21:58:22.521049
• Title: Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models
• Title（参考訳）: Slow Beats Fasts at the Kesten-Stigum Threshold: Minimax, Fisher-information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models (特集:エネルギー・エネルギー)
• Abstract要約: 本研究は,$q$コミュニティを用いた疎対称計算ブロックモデルにおけるコミュニティリカバリについて検討する。 我々はKesten-Stigumしきい値$d2=1$と、その下の情報計算ギャップの3つの特徴を得る。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study community recovery in the sparse symmetric stochastic block model with $q$ communities, average degree $d$ and signal strength $λ$ through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold $dλ^2=1$ and of the information-computation gap below it. First, on each community-size profile the minimax risk of any class of rules closed under averaging and vertex relabeling equals its Bayes risk under the uniform prior; the posterior mean is the unique Bayes rule and is admissible, and the Bayes risk of degree-$D$ polynomial rules is the trivial risk times $1-\mathrm{Corr}_D^2$. Combined with known low-degree and information-theoretic results, this gives the gap as a worst-case statement: for $q\ge 5$ there is a window below the threshold in which no low-degree rule beats the trivial risk asymptotically, while an exponential-time rule does on a set of labelings of probability $1-o(1)$. Second, the Fisher information about $λ$ carried by cycle counts is a series with terms of order $k(dλ^2)^k$, convergent exactly when $dλ^2<1$; below the threshold the relative error of every unbiased cycle-based estimator of $λ^k$ stays above an explicit constant, and every cycle-count test has success probability bounded below one. Third, the derivative of belief propagation at its uninformative fixed point multiplies a random perturbation by $|λ|\sqrt{d}$ per iteration, and one EM step taken there leaves $λ$ unchanged. A signal-to-noise computation recovers the condition $dλ^{1/χ}>1$ of Chin et al. for $q=n^χ$ communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to $3\times 10^5$ vertices confirm the threshold for $q=2$, the hard window for $q=5$, and the many-community scaling.
• Abstract（参考訳）: 我々は, 統計的決定理論とフィッシャー情報を用いて, 平均次数$d$, 信号強度$λ$のスパース対称確率ブロックモデルを用いて, コミュニティ回復について検討し, ケステン・スティグムしきい値$dλ^2=1$の3つの特徴と, その下の情報計算ギャップのキャラクタリゼーションを得る。 第一に、各コミュニティサイズプロファイルにおいて、平均と頂点の許容の下で閉じた任意の種類の規則のミニマックスリスクは、そのベイズリスクに等しい; 後平均は、一意のベイズ則であり、許容できる; 次数$D$多項式規則のベイズリスクは、自明なリスク時間である: $1-\mathrm{Corr}_D^2$。 既知の低次および情報理論の結果と組み合わせると、このギャップは最悪のケースで、$q\ge 5$に対して、低次ルールが自明なリスクを漸近的に打ち負かさず、指数時間ルールが確率1-o(1)$のラベリングのセットで行うようなしきい値の下に窓がある。 第二に、サイクルカウントが持つ$λ$に関するフィッシャー情報(Fisher information about $λ$ carried by cycle counts)は、次数$k(dλ^2)^k$, convergent exactly if $dλ^2<1$; under the threshold of every unbiased cycle-based estimator of $λ^k$ の相対誤差は明示的な定数以上であり、全てのサイクルカウントテストは1以下の成功確率を持つ。 第三に、その非形式的不動点における信念伝播の微分は、反復ごとに$|λ|\sqrt{d}$でランダムな摂動を乗算し、そこで取られたEMステップは$λ$である。 a signal-to-noise computes recovery the condition $dλ^{1/a}>1$ of Chin et al for $q=n^n$ community and identifieds Personal PageRank as a walk count with suboptimal weights。 最大$3\times 10^5$の頂点を持つネットワークの実験では、$q=2$、$q=5$のハードウインドウ、および多言語スケーリングのしきい値が確認されている。

関連論文リスト

• Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning [55.29259818039367]
  オフラインアルゴリズムに任意の制御値オラクルが与えられるとき, 一般のマトロイドに対する非負のサブモジュラー対象について検討する。 本アルゴリズムは,非単調な目的に対して1/e$,単調な目的に対して1/e$の制限係数を保持する。 結果として、オフラインからオフラインへの還元は、一般的なマトロイド制約のサブモジュラー報酬に対するシングルバンドCMABアルゴリズムをもたらす。
  論文  参考訳（メタデータ） (2026-08-12T14:54:15Z)
• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。 我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
  論文  参考訳（メタデータ） (2026-08-06T19:49:48Z)
• A Complexity Measure for Active Learning in Multi-group Mean Estimation [8.550300650352732]
  マルチグループ平均バンドレート$d$-armed banditsにおけるemphmax-riskによるアクティブラーニングの目的について検討した。 学習者は、最悪の不確実性指数を最小限に抑えるために、$d$グループ全体で$T$サンプルの予算を適応的に割り当てる。 滑らかなクラスに対しては、$mathrmVLC$ は分散-フィッシャー情報の再パラメータ化であり、共通族に対する閉形式値を持つ。
  論文  参考訳（メタデータ） (2026-06-12T17:54:26Z)
• How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysis [53.063298916923976]
  r*(x) = *(langle *, xrangle)$ と $x sim N(0, I_d)$ でガウスの単一インデックスモデルでフィードバックを研究する。 まず、報酬重み付きサンプルから隠れた方向を*$で学習し、次に重み付きリッジ回帰により読み出し層に適合する2段階のニューラル報酬モデルを分析する。
  論文  参考訳（メタデータ） (2026-05-23T22:00:38Z)
• When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias [15.113649527486276]
  良性オーバーフィッティングが線形レートで失敗することを示します。 この局所化機構は信号の存在下で持続するべきであるが、正確な信号-雑音分解は未解決の問題である。
  論文  参考訳（メタデータ） (2026-05-07T14:14:09Z)
• Adaptive Confidence Intervals in Efron's Gaussian Two-Groups Model [28.636700996382558]
  敵のノイズに満ちた性質により、Efronのガウス的二群分数モデルにおいて、ヌル位置パラメータ$$に対する信頼区間を研究する。 信頼区間の最小最適長を、未知の割合の汚染と全てのノイズに満ちた敵に対して、所定のカバレッジレベルで特徴付ける。
  論文  参考訳（メタデータ） (2026-04-28T22:40:54Z)
• Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning [61.07540493350384]
  自己蒸留(英: Self-distillation, SD)とは、教師自身の予測と地道の混合で学生を訓練する過程である。 任意の予測リスクに対して、各正規化レベルにおいて、最適に混合された学生がリッジ教師に改善されることが示される。 本稿では,グリッド探索やサンプル分割,再構成なしに$star$を推定する一貫したワンショットチューニング手法を提案する。
  論文  参考訳（メタデータ） (2026-02-19T17:21:15Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

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

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