論文の概要: Spectral Algorithms Optimally Recover (Censored) Planted Dense Subgraphs
- arxiv url: http://arxiv.org/abs/2203.11847v1
- Date: Tue, 22 Mar 2022 16:23:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-23 16:59:52.826582
- Title: Spectral Algorithms Optimally Recover (Censored) Planted Dense Subgraphs
- Title（参考訳）: スペクトルアルゴリズムによる植込み高密度グラフの最適検索
- Authors: Souvik Dhara, Julia Gaudio, Elchanan Mossel, and Colin Sandon
- Abstract要約: 本研究では, PDS の高密度部分グラフ問題 (PDS) と検閲された変種 (CPDS) のスペクトルアルゴリズムについて検討した。
本稿では,隣接行列の上位2つの固有ベクトルに基づく単純なスペクトルアルゴリズムにより,情報理論しきい値まで$Sstar$を復元可能であることを示す。
CDPSモデルでは、回復問題に対する情報理論限界を求め、さらに、符号付き隣接行列と呼ばれる特別な行列に基づくスペクトルアルゴリズムが情報理論しきい値まで$Sstar$を回復することを示す。
- 参考スコア（独自算出の注目度）: 6.760971938794954
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study spectral algorithms for the planted dense subgraph problem (PDS), as
well as for a censored variant (CPDS) of PDS, where the edge statuses are
missing at random. More precisely, in the PDS model, we consider $n$ vertices
and a random subset of vertices $S^{\star}$ of size $\Omega(n)$, such that two
vertices share an edge with probability $p$ if both of them are in $S^{\star}$,
and all other edges are present with probability $q$, independently. The goal
is to recover $S^{\star}$ from one observation of the network. In the CPDS
model, edge statuses are revealed with probability $\frac{t \log n}{n}$. For
the PDS model, we show that a simple spectral algorithm based on the top two
eigenvectors of the adjacency matrix can recover $S^{\star}$ up to the
information theoretic threshold. Prior work by Hajek, Wu and Xu required a less
efficient SDP based algorithm to recover $S^{\star}$ up to the information
theoretic threshold. For the CDPS model, we obtain the information theoretic
limit for the recovery problem, and further show that a spectral algorithm
based on a special matrix called the signed adjacency matrix recovers
$S^{\star}$ up to the information theoretic threshold.
- Abstract（参考訳）: 本研究では, 被植密度部分グラフ問題 (pds) のスペクトルアルゴリズムと, エッジ状態がランダムに欠落しているpdsの検閲変種 (cpds) について検討した。
より正確には、pdsモデルでは、$n$頂点と、サイズが$\omega(n)$のランダムな部分集合を考えると、2つの頂点が$s^{\star}$の場合に、確率が$p$の辺を共有し、他の辺は独立して$q$の確率を持つ。
目標は、ネットワークの1つの観測から$S^{\star}$を回収することだ。
cpdsモデルでは、エッジ状態は確率$\frac{t \log n}{n}$で明らかにされる。
pdsモデルでは、隣接行列の上位2つの固有ベクトルに基づく単純なスペクトルアルゴリズムが、情報理論のしきい値まで$s^{\star}$を回復できることが示されている。
Hajek、Wu、Xuによる以前の研究では、情報理論しきい値まで$S^{\star}$を回復するために、より効率的なSDPベースのアルゴリズムが必要だった。
CDPSモデルでは、回復問題に対する情報理論限界を求め、さらに、符号付き隣接行列と呼ばれる特別な行列に基づくスペクトルアルゴリズムが情報理論しきい値まで$S^{\star}$を回復することを示す。
関連論文リスト
- Exact Community Recovery (under Side Information): Optimality of Spectral Algorithms [1.4732811715354452]
一般の2つのコミュニティブロックモデルにおいて,コミュニティの正確な回復の問題について検討する。
正確な回復の情報理論的限界に対する側情報の影響を統一的に分析する。
論文 参考訳（メタデータ） (2024-06-18T21:48:59Z) - A Combinatorial Approach to Robust PCA [18.740048806623037]
敵の汚職下でのガウスデータの回復問題について検討する。
ガウスノイズは未知の$k$-次元部分空間$U subseteq mathbbRd$と、各データポイントのランダムに選択された座標が敵の制御に該当すると仮定する。
我々の主な結果は、$ks2 = O(d)$のとき、期待して$tilde O(ks/d)$のほぼ最適エラーまですべてのデータポイントを復元する効率的なアルゴリズムです。
論文 参考訳（メタデータ） (2023-11-28T01:49:51Z) - 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) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - Sparse random hypergraphs: Non-backtracking spectra and community
detection [10.503525445174464]
我々は、ハイパーグラフの非追跡演算子に基づくスペクトル法が、アンジェリーニらによって予想される一般化ケステン・スティグム検出しきい値まで高い確率で作用することを証明した。
これは、一般的な対称確率テンソルに従って$r$ブロックを生成するHSBMの予測しきい値を達成する最初の証明可能かつ効率的なアルゴリズムである。
論文 参考訳（メタデータ） (2022-03-14T17:45:03Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。
ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。
代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
論文 参考訳（メタデータ） (2021-06-03T07:22:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。