Fugu-MT 論文翻訳(概要): Exact and rapid linear clustering of networks with dynamic programming

論文の概要: Exact and rapid linear clustering of networks with dynamic programming

arxiv url: http://arxiv.org/abs/2301.10403v1
Date: Wed, 25 Jan 2023 04:36:41 GMT
ステータス: 処理完了
システム内更新日: 2023-01-26 15:54:51.608163
Title: Exact and rapid linear clustering of networks with dynamic programming
Title（参考訳）: 動的プログラミングによるネットワークの厳密かつ迅速な線形クラスタリング
Authors: Alice Patania, Antoine Allard, Jean-Gabriel Young
Abstract要約: 本研究では,ノードが暗示的あるいは物理的位置を単一次元に持つクラスタリングネットワークの問題点について検討する。臨界ギャップ法やその他の戦略のような既存のアルゴリズムは、近似解のみを提供する。我々は,強欲な時間に最適解を返す動的プログラミング手法を導入する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of clustering networks whose nodes have imputed or physical positions in a single dimension, such as prestige hierarchies or the similarity dimension of hyperbolic embeddings. Existing algorithms, such as the critical gap method and other greedy strategies, only offer approximate solutions. Here, we introduce a dynamic programming approach that returns provably optimal solutions in polynomial time -- O(n^2) steps -- for a broad class of clustering objectives. We demonstrate the algorithm through applications to synthetic and empirical networks, and show that it outperforms existing heuristics by a significant margin, with a similar execution time.
Abstract（参考訳）: 本稿では,高次階層や双曲型埋め込みの類似性次元など,ノードが単一次元における暗示的あるいは物理的位置を持つクラスタリングネットワークの問題について検討する。臨界ギャップ法や他の欲望戦略のような既存のアルゴリズムは近似解のみを提供する。ここでは、幅広いクラスタリング対象に対して多項式時間(O(n^2)ステップ)で証明可能な最適解を返す動的プログラミング手法を提案する。合成および経験的ネットワークへの応用を通してアルゴリズムを実証し、同様の実行時間で既存のヒューリスティックスよりも優れていることを示す。

関連論文リスト

Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
論文参考訳（メタデータ） (2024-05-28T10:28:45Z)
Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
エージェントが隣人としか通信できないネットワーク上での分散マルチレベル最適化の問題について検討する。ネットワーク化されたエージェントが1つの時間スケールで異なるレベルの最適化問題を解くことができる新しいゴシップに基づく分散マルチレベル最適化アルゴリズムを提案する。提案アルゴリズムは, ネットワークサイズと線形にスケーリングし, 各種アプリケーション上での最先端性能を示す。
論文参考訳（メタデータ） (2023-10-10T00:21:10Z)
Fast inference of latent space dynamics in huge relational event networks [0.0]
巨大イベントネットワークに対処可能な確率に基づくアルゴリズムを提案する。本研究では,解釈可能な潜在空間に埋め込まれたネットワークコミュニティのダイナミクスを推定するための階層的戦略を提案する。大規模ネットワークでフレームワークを実現するには、機械学習最適化の方法論を借りる。
論文参考訳（メタデータ） (2023-03-29T15:18:56Z)
On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文参考訳（メタデータ） (2022-06-30T05:29:52Z)
Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent Signals: Application to Hyperspectral Imaging [71.57324258813675]
相互依存信号のデータセットは、列が強い依存を示す行列として定義される。ニューラルネットワークは、事前に構造として機能し、基礎となる信号相互依存性を明らかにするために使用される。ディープ・アンローリングとディープ・平衡に基づくアルゴリズムが開発され、高度に解釈可能で簡潔なディープ・ラーニング・ベース・アーキテクチャを形成する。
論文参考訳（メタデータ） (2022-03-29T21:00:39Z)
Efficient Direct-Connect Topologies for Collective Communications [2.9394897655215555]
ワークロードに関連する帯域幅のトレードオフに対して,レイテンシに最適化された直接接続トポロジを構築するためのアルゴリズムフレームワークを提供する。提案手法は,与えられたクラスタサイズと度合いの様々なトポロジとスケジュールを合成し,与えられたワークロードの適切なトポロジとスケジュールを特定する。
論文参考訳（メタデータ） (2022-02-07T16:59:05Z)
An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees [4.007017852999008]
本稿では,ノードの側情報を持つクラスタネットワークに対して,新たな反復アルゴリズムを提案する。このアルゴリズムは文脈対称性ブロックモデルの下で最適であることを示す。
論文参考訳（メタデータ） (2021-12-20T12:04:07Z)
Network Clustering for Latent State and Changepoint Detection [0.0]
本稿では,ネットワーククラスタリングのタスクに対する凸アプローチを提案する。コンベックスネットワーククラスタリングのための効率的なアルゴリズムを提案し,その有効性を合成例で示す。
論文参考訳（メタデータ） (2021-11-01T21:51:45Z)
Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training [10.14260510961573]
機械学習アプローチを用いて、オンラインアロケーション(二部マッチング)のアルゴリズムを見つけるという課題に対処する。本稿では,従来のオンライン予算マッチング問題であるAdWords問題に着目し,理論的および実用的意義の両面から考察する。
論文参考訳（メタデータ） (2020-10-16T14:33:11Z)
A black-box adversarial attack for poisoning clustering [78.19784577498031]
本稿では,クラスタリングアルゴリズムのロバスト性をテストするために,ブラックボックス対逆攻撃法を提案する。我々の攻撃は、SVM、ランダムフォレスト、ニューラルネットワークなどの教師付きアルゴリズムに対しても転送可能であることを示す。
論文参考訳（メタデータ） (2020-09-09T18:19:31Z)
Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
論文参考訳（メタデータ） (2020-06-15T02:57:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。