論文の概要: Community Detection with a Subsampled Semidefinite Program
- arxiv url: http://arxiv.org/abs/2102.01419v1
- Date: Tue, 2 Feb 2021 10:31:57 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-03 16:18:28.527080
- Title: Community Detection with a Subsampled Semidefinite Program
- Title（参考訳）: サブサンプル半確定プログラムによるコミュニティ検出
- Authors: Pedro Abdalla and Afonso S. Bandeira
- Abstract要約: 半定的なプログラムは実行が遅い場合が多いため、スケッチなどのテクニックの高速化も考慮されることが多い。
Mixon と Xie は先日,ネットワークのサブサンプル部分グラフ上でのみ半定値プログラムを解き,計算コストを大幅に削減するスケッチフレームワークを提案している。
- 参考スコア（独自算出の注目度）: 4.077919509379151
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Semidefinite programming is an important tool to tackle several problems in
data science and signal processing, including clustering and community
detection. However, semidefinite programs are often slow in practice, so speed
up techniques such as sketching are often considered. In the context of
community detection in the stochastic block model, Mixon and Xie [9] have
recently proposed a sketching framework in which a semidefinite program is
solved only on a subsampled subgraph of the network, giving rise to significant
computational savings. In this short paper, we provide a positive answer to a
conjecture of Mixon and Xie about the statistical limits of this technique for
the stochastic block model with two balanced communities.
- Abstract（参考訳）: 半定型プログラミングは、クラスタリングやコミュニティ検出など、データサイエンスと信号処理のいくつかの問題に取り組むための重要なツールです。
しかし、半定義のプログラムは実際には遅いことが多いため、スケッチなどの技法の高速化がしばしば考慮される。
確率ブロックモデルにおけるコミュニティ検出の文脈において、Mixon と Xie [9] は、最近、ネットワークのサブサンプリングされたサブグラフにのみ半定値プログラムを解き、計算の大幅な節約をもたらすスケッチフレームワークを提案している。
本稿では,2つの平衡群をもつ確率的ブロックモデルに対するこの手法の統計的限界について,mixon と xie の予想に対する正の答えを提案する。
関連論文リスト
- Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Average-Case Communication Complexity of Statistical Problems [48.03761288397421]
通信の複雑さは、ストリーミング、スケッチ、クエリベースのモデルにおける下位境界を証明する主要なツールである。
本稿では,ランダムグラフやマトリクスに植木構造を組み込んだ問題に対して,入力分布を保存する一般還元法を提案する。
我々は,植林した傾斜地を検知・発見するために,二者間・多者間通信の下限を導出する。
論文 参考訳（メタデータ） (2021-07-03T03:31:37Z) - Streaming Belief Propagation for Community Detection [16.89299967467454]
現実世界のアプリケーションでは、ネットワーク構造は通常動的で、時間とともにノードが結合する。
ストリーミングブロックモデル(StSBM)と呼ばれる,時間とともに成長するネットワークのためのシンプルなモデルを提案する。
このモデルでは、投票アルゴリズムに基本的な制限があることが証明される。
また,ストリーミング・プロパゲーション(StreamBP)アプローチを開発し,特定の状況下で最適性を証明した。
論文 参考訳（メタデータ） (2021-06-09T04:36:09Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳（メタデータ） (2020-12-04T15:36:29Z) - A Three-Stage Self-Training Framework for Semi-Supervised Semantic
Segmentation [0.9786690381850356]
本稿では,セマンティックセグメンテーションのための3段階の自己学習フレームワークとして,包括的解を提案する。
本手法の鍵となる考え方は擬似マスク統計情報の抽出である。
次に、一貫性を強制するマルチタスクモデルを用いて擬似マスクの不確実性を減少させる。
論文 参考訳（メタデータ） (2020-12-01T21:00:27Z) - Sketch-based community detection in evolving networks [15.512086254435788]
時間変化ネットワークにおけるコミュニティ検出のアプローチを検討する。
このアプローチの中心となるのは、完全なネットワークの各スナップショットにある重要なコミュニティ構造をキャプチャする、小さなスケッチグラフを維持することだ。
すべての処理を並列に処理できるコミュニティ検出アルゴリズムを定式化する。
論文 参考訳（メタデータ） (2020-09-24T17:32:57Z) - Sketching semidefinite programs for faster clustering [9.645196221785694]
グラフクラスタリング問題(最小二分法)の半定緩和法(半定緩和法)をスケッチする方法を示す。
我々の分析は、より多くの信号がある場合、クラスタリングタスクは計算的に負担が少ないというメタステートをサポートします。
論文 参考訳（メタデータ） (2020-08-10T17:10:29Z) - A General Method for Robust Learning from Batches [56.59844655107251]
本稿では,バッチから頑健な学習を行う一般的なフレームワークについて考察し,連続ドメインを含む任意の領域に対する分類と分布推定の限界について考察する。
本手法は,一括分節分類,一括分節,単調,対数凹,ガウス混合分布推定のための,最初の頑健な計算効率の学習アルゴリズムを導出する。
論文 参考訳（メタデータ） (2020-02-25T18:53:25Z) - Seismic horizon detection with neural networks [62.997667081978825]
本稿では,複数の実地震立方体上での地平線検出にバイナリセグメンテーションを適用し,予測モデルのキューブ間一般化に着目したオープンソースの研究である。
本研究の主な貢献は,複数実地震立方体における地平線検出にバイナリセグメンテーションを適用し,予測モデルのキューブ間一般化に着目したオープンソースの研究である。
論文 参考訳（メタデータ） (2020-01-10T11:30:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。