論文の概要: Exact Community Recovery under Side Information: Optimality of Spectral Algorithms
- arxiv url: http://arxiv.org/abs/2406.13075v2
- Date: Mon, 10 Mar 2025 02:46:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-11 15:39:21.018867
- Title: Exact Community Recovery under Side Information: Optimality of Spectral Algorithms
- Title（参考訳）: サイドインフォメーションによる特定コミュニティリカバリ : スペクトルアルゴリズムの最適性
- Authors: Julia Gaudio, Nirmit Joshi,
- Abstract要約: 本研究では,ノードに分散した$side$$informationの存在下で,一般の2つのコミュニティブロックモデルにおいて,コミュニティの正確な回復の問題について検討する。
我々のスペクトルアルゴリズムはいわゆる$genie$-$aided$ $estimatorsを模倣できることを示す。
- 参考スコア（独自算出の注目度）: 1.4732811715354452
- License:
- Abstract: We study the problem of exact community recovery in general, two-community block models, in the presence of node-attributed $side$ $information$. We allow for a very general side information channel for node attributes, and for pairwise (edge) observations, consider both Bernoulli and Gaussian matrix models, capturing the Stochastic Block Model, Submatrix Localization, and $\mathbb{Z}_2$-Synchronization as special cases. A recent work of Dreveton et al. 2024 characterized the information-theoretic limit of a very general exact recovery problem with side information. In this paper, we show algorithmic achievability in the above important cases by designing a simple but optimal spectral algorithm that incorporates side information (when present) along with the eigenvectors of the pairwise observation matrix. Using the powerful tool of entrywise eigenvector analysis of Abbe et al. 2020, we show that our spectral algorithm can mimic the so called $genie$-$aided$ $estimators$, where the $i^{\mathrm{th}}$ genie-aided estimator optimally computes the estimate of the $i^{\mathrm{th}}$ label, when all remaining labels are revealed by a genie. This perspective provides a unified understanding of the optimality of spectral algorithms for various exact recovery problems in a recent line of work.
- Abstract（参考訳）: 本稿では,ノード分散$side$$information$の存在下で,一般の2つのコミュニティブロックモデルにおける正確なコミュニティ回復の問題について検討する。
ノード属性に対する非常に一般的な側情報チャネルと、ペアワイズ(エッジ)観測では、ベルヌーイおよびガウス行列モデルの両方を考慮し、Stochastic Block Model、Submatrix Localization、および$\mathbb{Z}_2$-Synchronizationを特別なケースとして捉える。
Dreveton et al 2024の最近の研究は、側面情報を伴う非常に一般的な正確な回復問題の情報理論の限界を特徴付けている。
本稿では,2つの観測行列の固有ベクトルとともに側情報(現在)を組み込んだ,単純だが最適なスペクトルアルゴリズムを設計することにより,上記の重要な場合におけるアルゴリズムの達成可能性を示す。
Abbeらによるエントリーワイド固有ベクトル解析の強力なツールを用いて、我々のスペクトルアルゴリズムはいわゆる $genie$-$aided$ $estimators$, where the $i^{\mathrm{th}}$ genie-aided estimator が $i^{\mathrm{th}}$ genie-aided estimator を最適に計算し、残っていたラベルがすべてジェニーによって露呈されたときに、その推定値を計算することができることを示す。
この観点は、近年の一連の作業において、様々な正確な回復問題に対するスペクトルアルゴリズムの最適性を統一的に理解する。
関連論文リスト
- Robust Graph-Based Semi-Supervised Learning via $p$-Conductances [49.0776396776252]
本研究では,データラベルが不足している,あるいは破損しているような状況下でのグラフに対する半教師付き学習の課題について検討する。
我々は、$p$-laplace と Poisson の学習方法を一般化した $p$-conductance learning という手法を提案する。
コンピュータビジョンと引用データセットの実証実験結果から,本手法が低ラベルレート, 劣化ラベル, 部分ラベルレジームにおける最先端の精度を実現することを示す。
論文 参考訳（メタデータ） (2025-02-13T01:11:25Z) - On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models [11.137244714693779]
半ランダムな敵に対するスペクトルアルゴリズムの堅牢性について検討する。
我々は,_unnormalized_Laplacian を用いたスペクトル二分法が強い整合性を持つ半ランダム逆数クラスを同定した。
論文 参考訳（メタデータ） (2024-12-18T20:35:02Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Compressive Recovery of Sparse Precision Matrices [5.557600489035657]
我々は,$d$変数の統計的関係を,mathbbRn times d$の$n$サンプル$Xのデータセットからモデル化するグラフの学習問題を考察する。
サイズ $m=Omegaleft((d+2k)log(d)right)$ ここで、$k$は基礎となるグラフのエッジの最大数である。
本稿では, グラフィカルラッソに基づく反復アルゴリズムを用いて, 具体的デノイザとみなす実用的リカバリを実現する可能性について検討する。
論文 参考訳（メタデータ） (2023-11-08T13:29:08Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - 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) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T08:25:26Z) - An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。
本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
論文 参考訳（メタデータ） (2021-06-08T23:38:29Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Analytic Characterization of the Hessian in Shallow ReLU Models: A Tale
of Symmetry [9.695960412426672]
我々は,スプリアスミニマの様々な家系でヘッセンを解析的に特徴付ける。
特に、$dge k$ 標準ガウス入力について、 (a) ヘッセンの $dk$ 固有値の内、$dk - O(d)$ が 0 に近づき、 (b) $Omega(d)$ 固有値は $k$ で線型的に増加することを証明している。
論文 参考訳（メタデータ） (2020-08-04T20:08:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。