論文の概要: Non-Convex Joint Community Detection and Group Synchronization via
Generalized Power Method
- arxiv url: http://arxiv.org/abs/2112.14204v1
- Date: Tue, 28 Dec 2021 16:17:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-31 03:19:27.393676
- Title: Non-Convex Joint Community Detection and Group Synchronization via
Generalized Power Method
- Title（参考訳）: 一般化パワー法による非凸ジョイントコミュニティ検出とグループ同期
- Authors: Sijin Chen, Xiwei Cheng, Anthony Man-Cho So
- Abstract要約: 本稿では,コミュニティ検出とグループ同期を同時に行うための汎用電力方式(GPM)を提案する。
このアルゴリズムは、$O(n2n$)$log2n$)を3.5$の時間で正確に回収できることが示されている。
- 参考スコア（独自算出の注目度）: 23.62113376505929
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper proposes a Generalized Power Method (GPM) to tackle the problem of
community detection and group synchronization simultaneously in a direct
non-convex manner. Under the stochastic group block model (SGBM), theoretical
analysis indicates that the algorithm is able to exactly recover the ground
truth in $O(n\log^2n)$ time, sharply outperforming the benchmark method of
semidefinite programming (SDP) in $O(n^{3.5})$ time. Moreover, a lower bound of
parameters is given as a necessary condition for exact recovery of GPM. The new
bound breaches the information-theoretic threshold for pure community detection
under the stochastic block model (SBM), thus demonstrating the superiority of
our simultaneous optimization algorithm over the trivial two-stage method which
performs the two tasks in succession. We also conduct numerical experiments on
GPM and SDP to evidence and complement our theoretical analysis.
- Abstract（参考訳）: 本稿では,コミュニティ検出とグループ同期の問題を,直接非凸方式で同時に行うための一般化電力法(GPM)を提案する。
確率的群ブロックモデル(SGBM)の下では、理論解析により、アルゴリズムは$O(n\log^2n)$時間で基底真理を正確に回復することができ、$O(n^{3.5})$時間で半定値プログラミング(SDP)のベンチマーク手法を著しく上回っている。
さらに、GPMの正確な回復に必要な条件として、パラメータの低い境界が与えられる。
新しい境界は、確率的ブロックモデル(SBM)の下での純粋コミュニティ検出のための情報理論しきい値に反し、2つのタスクを連続的に実行する自明な2段階法よりも並列最適化アルゴリズムが優れていることを示す。
また,pgmとsdpの数値実験をエビデンスに実施し,理論解析を補完する。
関連論文リスト
- A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
Generalized Category Discovery (GCD) は、ラベル付きベースデータを用いて、ベース画像と新規画像の両方を分類することを目的としている。
現在のアプローチでは、コサイン類似性に基づく共起行列 $barA$ の固有の最適化に不適切に対処している。
本稿では,これらの欠陥に対処するNon-Negative Generalized Category Discovery (NN-GCD) フレームワークを提案する。
論文 参考訳（メタデータ） (2024-10-29T07:24:11Z) - Harmonic Path Integral Diffusion [0.4527270266697462]
本稿では,連続多変量確率分布から抽出する新しい手法を提案する。
本手法では,状態空間の起点を中心とするデルタ関数を$t=0$とし,ターゲット分布に$t=1$で変換する。
これらのアルゴリズムは他のサンプリング手法、特にシミュレートおよびパス積分サンプリングと対比し、解析制御、精度、計算効率の点でそれらの利点を強調した。
論文 参考訳（メタデータ） (2024-09-23T16:20:21Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms [45.90015262911875]
不均一な環境で分散SGDのための非同期型アルゴリズムを解析する。
また,本分析の副産物として,ランダムなきついSGDのような勾配型アルゴリズムの保証を示す。
論文 参考訳（メタデータ） (2023-10-31T13:44:53Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳（メタデータ） (2023-03-02T05:08:15Z) - Sampling with Mollified Interaction Energy Descent [57.00583139477843]
モーフィファイド相互作用エネルギー降下(MIED)と呼ばれる新しい最適化に基づくサンプリング手法を提案する。
MIEDは、モル化相互作用エネルギー(MIE)と呼ばれる確率測度に関する新しいクラスのエネルギーを最小化する
我々は,制約のないサンプリング問題に対して,我々のアルゴリズムがSVGDのような既存の粒子ベースアルゴリズムと同等に動作することを示す。
論文 参考訳（メタデータ） (2022-10-24T16:54:18Z) - Scaling up Stochastic Gradient Descent for Non-convex Optimisation [5.908471365011942]
本稿では,共有並列計算問題に対する新しいアプローチを提案する。
2つの戦略を統一されたフレームワークに組み合わせることで、DPSGDはより良い取引計算フレームワークになります。
深層学習(DRL)問題と深層学習(DRL)問題(アドバンテージアクター - A2C)についてDPSGDにより潜在ゲインを達成できる。
論文 参考訳（メタデータ） (2022-10-06T13:06:08Z) - Utilising the CLT Structure in Stochastic Gradient based Sampling :
Improved Analysis and Faster Algorithms [14.174806471635403]
粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。
近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。
この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
論文 参考訳（メタデータ） (2022-06-08T10:17:40Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳（メタデータ） (2020-12-28T17:19:32Z) - Non-Convex Exact Community Recovery in Stochastic Block Model [31.221745716673546]
近年,対称ブロックモデル(SBM)に基づくグラフのコミュニティ検出が注目されている。
この問題の対数的疎度構造において、提案した2段階法は、$mathcalO(nlog2n/loglog n)$ timeにおいて、情報理論の限界まで正確に2つのコミュニティを復元できることを示す。
また, 提案手法の有効性を実証し, 理論的発展を補完するために, 合成データセットと実データセットの両方で数値実験を行った。
論文 参考訳（メタデータ） (2020-06-29T07:03:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。