論文の概要: Bethe Hessian Recovery through the Kesten-Stigum Regime

• arxiv url: http://arxiv.org/abs/2610.41802v1
• Date: Fri, 30 Oct 2026 14:30:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 22:05:31.771075
• Title: Bethe Hessian Recovery through the Kesten-Stigum Regime
• Title（参考訳）: ケステン・スティグム・レジームによるヘッセンの回復
• Abstract要約: ベーテ・ヘッセンの固有ベクトルはブロックモデルにおいてケステン・スティグムしきい値まで弱回復することを示す。 これにより、以前のリカバリ保証が拡張され、十分な規模の$d$が必要になった。
• 参考スコア（独自算出の注目度）: 0.11458853556386794
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that outlier eigenvectors of the Bethe Hessian achieve weak recovery in the stochastic block model down to the Kesten-Stigum threshold, for every fixed common expected degree $d>1$. This extends previous recovery guarantees, which required $d$ to be sufficiently large. This threshold is information-theoretically optimal for the symmetric two-community model and is conjectured to mark the limit of efficient recovery in broader symmetric models. Our result matches the recovery guarantees of non-backtracking spectral methods while using Hermitian $n\times n$ matrices. To do this, we identify recursive formulas for the negative outlier eigenvalues and show that their eigenspaces have nonvanishing overlap with the corresponding planted eigenspaces. The proof constructs approximate eigenvectors from the planted labels on the limiting Poisson tree, with weights given by its Green's function, and transfers these approximations to the finite graph.
• Abstract（参考訳）: ベーテ・ヘシアンの外部固有ベクトルはケステン・スティグムしきい値までの確率的ブロックモデルの弱い回復を、固定された共通次数$d>1$に対して達成することを示した。 これにより、以前のリカバリ保証が拡張され、十分な規模の$d$が必要になった。 このしきい値は、対称二コミュニティモデルに対して情報理論的に最適であり、より広い対称モデルにおける効率的な回復の限界を示すと推測される。 この結果は,Hermitian $n\times n$ matricesを用いて,非バックトラックスペクトル法の回復保証と一致した。 これを実現するために, 負のアウトレイア固有値に対する再帰公式を同定し, それらの固有空間が対応する植込み固有空間と重複しないことを示す。 この証明は、制限されたポアソン木上の植木ラベルから近似固有ベクトルを構成し、そのグリーン函数によって与えられる重みを持ち、これらの近似を有限グラフに転送する。

関連論文リスト

• Robust Latent Variable Graphical Models: Exact Recovery and Fundamental Limits [1.7430416823420511]
  スパース行列として分解されるガウス精度行列のロバストな推定について検討した。 我々は,フロベニウス推定,グラフ復元,慣性回復のための情報理論上の限界を証明した。
  論文  参考訳（メタデータ） (2026-10-19T11:19:49Z)
• Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards [1.370633147306388]
  $text-mathrmNPTS_mathrmSG$はアンカーフリーの非パラメトリックトンプソンサンプリングアルゴリズムである。 我々は、$text-mathrmNPTS_mathrmSG$が、$log n$の先頭の順にインスタンス依存の下位境界と一致することを証明した。
  論文  参考訳（メタデータ） (2026-06-08T08:26:37Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Row-stochastic matrices can provably outperform doubly stochastic matrices in decentralized learning [10.686669655748702]
  分散学習は、不均一ノード重みが$$の重み付きグローバル損失を伴うことが多い。 重み付きヒルベルト空間フレームワーク $L2(mathbbRd)$ を開発し、ユークリッド解析より厳密な収束率を得る。 そして、より小さなスペクトルギャップであっても、行確率的設計がより高速に収束する十分な条件を導出する。
  論文  参考訳（メタデータ） (2025-11-24T02:58:38Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• Random Forest Weighted Local Fréchet Regression with Random Objects [18.128663071848923]
  本稿では,新しいランダム森林重み付き局所Fr'echet回帰パラダイムを提案する。 最初の方法は、これらの重みを局所平均として、条件付きFr'echet平均を解くことである。 第二の手法は局所線形Fr'echet回帰を行い、どちらも既存のFr'echet回帰法を大幅に改善した。
  論文  参考訳（メタデータ） (2022-02-10T09:10:59Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2020-10-08T17:59:05Z)
• The Generalized Lasso with Nonlinear Observations and Generative Priors [63.541900026673055]
  我々は、幅広い測定モデルで満たされるガウス下測度を仮定する。 この結果から, 局所埋込特性を仮定して, 均一回復保証まで拡張できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-22T16:43:35Z)

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

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