論文の概要: Exact Community Recovery (under Side Information): Optimality of Spectral Algorithms
- arxiv url: http://arxiv.org/abs/2406.13075v1
- Date: Tue, 18 Jun 2024 21:48:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-21 23:58:20.554571
- Title: Exact Community Recovery (under Side Information): Optimality of Spectral Algorithms
- Title（参考訳）: 特定コミュニティ・リカバリ(側方情報) : スペクトルアルゴリズムの最適性
- Authors: Julia Gaudio, Nirmit Joshi,
- Abstract要約: 一般の2つのコミュニティブロックモデルにおいて,コミュニティの正確な回復の問題について検討する。
正確な回復の情報理論的限界に対する側情報の影響を統一的に分析する。
- 参考スコア（独自算出の注目度）: 1.4732811715354452
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this paper, we study the problem of exact community recovery in general, two-community block models considering both Bernoulli and Gaussian matrix models, capturing the Stochastic Block Model, submatrix localization, and $\mathbb{Z}_2$-synchronization as special cases. We also study the settings where $side$ $information$ about community assignment labels is available, modeled as passing the true labels through a noisy channel: either the binary erasure channel (where some community labels are known while others are erased) or the binary symmetric channel (where some labels are flipped). We provide a unified analysis of the effect of side information on the information-theoretic limits of exact recovery, generalizing prior works and extending to new settings. Additionally, we design a simple but optimal spectral algorithm that incorporates side information (when present) along with the eigenvectors of the matrix observation. Using the powerful tool of entrywise eigenvector analysis [Abbe, Fan, Wang, Zhong 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（参考訳）: 本稿では,Bernolli と Gaussian のどちらの行列モデルも考慮し,Stochastic Block Model, submatrix Localization, $\mathbb{Z}_2$-synchronization を特別なケースとして捉え,コミュニティの正確な回復の問題を考察する。
コミュニティ割り当てラベルについて$side$$information$が利用可能で、ノイズの多いチャネルを通して真のラベルを渡すようにモデル化されている。
我々は,情報理論上の情報理論的限界に対する側情報の影響を統一的に分析し,先行作業を一般化し,新たな設定に拡張する。
さらに、行列観測の固有ベクトルとともに、サイド情報(現在)を組み込んだ、単純だが最適なスペクトルアルゴリズムを設計する。
エントリーワイド固有ベクトル解析の強力なツール [Abbe, Fan, Wang, Zhong 2020] を用いて、我々のスペクトルアルゴリズムはいわゆる $genie$-$aided$ $estimators$, where $i^{\mathrm{th}}$ genie-aided estimator が $i^{\mathrm{th}}$ラベルの値を最適に計算し、残っていたラベルがすべてジェニーによって露呈されたときに、その推定値を計算することを示す。
この観点は、近年の一連の作業において、様々な正確な回復問題に対するスペクトルアルゴリズムの最適性を統一的に理解する。
関連論文リスト
- 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) - Semi-Supervised Laplacian Learning on Stiefel Manifolds [67.29074577550405]
我々は、ララシアグラフの非プラサート一般化の枠組みを改革する。
低ラベルレートでの教師付きサンプルの臨界中心性に対処する。
私たちのコードは提出のためにオンフットコノニマス化されています。
論文 参考訳（メタデータ） (2023-07-31T20:19:36Z) - 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) - Spectral Algorithms Optimally Recover (Censored) Planted Dense Subgraphs [6.760971938794954]
本研究では, PDS の高密度部分グラフ問題 (PDS) と検閲された変種 (CPDS) のスペクトルアルゴリズムについて検討した。
本稿では,隣接行列の上位2つの固有ベクトルに基づく単純なスペクトルアルゴリズムにより,情報理論しきい値まで$Sstar$を復元可能であることを示す。
CDPSモデルでは、回復問題に対する情報理論限界を求め、さらに、符号付き隣接行列と呼ばれる特別な行列に基づくスペクトルアルゴリズムが情報理論しきい値まで$Sstar$を回復することを示す。
論文 参考訳（メタデータ） (2022-03-22T16:23:43Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。