Fugu-MT 論文翻訳(概要): Dynamic Correlation Clustering in Sublinear Update Time

論文の概要: Dynamic Correlation Clustering in Sublinear Update Time

arxiv url: http://arxiv.org/abs/2406.09137v1
Date: Thu, 13 Jun 2024 14:07:15 GMT
ステータス: 処理完了
システム内更新日: 2024-06-14 17:34:25.045907
Title: Dynamic Correlation Clustering in Sublinear Update Time
Title（参考訳）: サブ線形更新時間における動的相関クラスタリング
Authors: Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos Parotsidis,
Abstract要約: 動的ノードストリームにおける相関クラスタリングの古典的問題について検討する。この設定では、ノードは時間とともに追加またはランダムに削除され、各ノードペアは正または負のエッジで接続される。我々は,$O(1)$-approximationを$O$(polylog $n$)アモートした更新時間で維持するアルゴリズムを提案する。
参考スコア（独自算出の注目度）: 33.079608335361286
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the classic problem of correlation clustering in dynamic node streams. In this setting, nodes are either added or randomly deleted over time, and each node pair is connected by a positive or negative edge. The objective is to continuously find a partition which minimizes the sum of positive edges crossing clusters and negative edges within clusters. We present an algorithm that maintains an $O(1)$-approximation with $O$(polylog $n$) amortized update time. Prior to our work, Behnezhad, Charikar, Ma, and L. Tan achieved a $5$-approximation with $O(1)$ expected update time in edge streams which translates in node streams to an $O(D)$-update time where $D$ is the maximum possible degree. Finally we complement our theoretical analysis with experiments on real world data.
Abstract（参考訳）: 動的ノードストリームにおける相関クラスタリングの古典的問題について検討する。この設定では、ノードは時間とともに追加またはランダムに削除され、各ノードペアは正または負のエッジで接続される。目的は、クラスタを横断する正のエッジとクラスタ内の負のエッジの合計を最小化するパーティションを継続的に見つけることである。我々は,$O(1)$-approximationを$O$(polylog $n$)アモートした更新時間で維持するアルゴリズムを提案する。私たちの研究に先立ち、Behnezhad氏、Charikar氏、Ma氏、L. Tan氏は、エッジストリームの予測更新時間として$O(1)$$を5ドルで達成しました。最後に、実世界のデータに関する実験で理論解析を補完する。

関連論文リスト

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time [19.25942907402098]
動的相関クラスタリング問題について,textitadaptive$ edge label flipsを用いて検討した。相関クラスタリングでは、エッジを$(+)$または$(-)$とラベル付けした$n$-vertex完全グラフが与えられる。本稿では, 対数ロバスト性を持つ動的設定について考察する。ここでは, $textitadaptive$ adversary がアルゴリズムの現在の出力に基づいてエッジのラベルを反転させることができる。
論文参考訳（メタデータ） (2024-11-15T06:26:37Z)
Efficient k-Nearest-Neighbor Machine Translation with Dynamic Retrieval [49.825549809652436]
$k$NN-MTはドメイン固有の翻訳知識を保持するために外部データストアを構築する。適応検索(k$NN-MT-AR)は、$lambda$を動的に推定し、$lambda$が固定しきい値以下であれば$k$NN検索をスキップする。本稿では,バニラ$k$NN-MTを大幅に拡張した動的検索(k$NN-MT-DR)を提案する。
論文参考訳（メタデータ） (2024-06-10T07:36:55Z)
Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文参考訳（メタデータ） (2024-06-01T07:33:41Z)
Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文参考訳（メタデータ） (2024-02-14T07:52:00Z)
Minimizing Polarization in Noisy Leader-Follower Opinion Dynamics [17.413930396663833]
本稿では,ノイズの多いソーシャルネットワークにおけるリーダ・フォロワーの意見ダイナミクスに対する偏極最適化の問題について考察する。私たちは、すべてのリーダの意見が同一であり、変化のない、一般的なリーダフォローのDeGrootモデルを採用しています。目的関数が単調で超モジュラーであることを示し、その後、近似係数が1-1/e$の単純なグレディアルゴリズムを提案し、O((n-q)3)$時間で問題を解く。
論文参考訳（メタデータ） (2023-08-14T08:52:24Z)
Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文参考訳（メタデータ） (2023-07-14T16:11:22Z)
Improved Learning-augmented Algorithms for k-means and k-medians Clustering [8.04779839951237]
学習強化設定におけるクラスタリングの問題について考察し、そこでは、$d$次元ユークリッド空間のデータセットが与えられる。本稿では,クラスタリングコストを改良したセンターを生成する決定論的$k$-meansアルゴリズムを提案する。我々のアルゴリズムは、予測があまり正確でないときでも機能する。つまり、我々の限界は$alpha$を$/2$に保ち、以前の研究で$alpha$よりも1/7$に改善する。
論文参考訳（メタデータ） (2022-10-31T03:00:11Z)
Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文参考訳（メタデータ） (2022-06-16T17:10:57Z)
Maximizing Influence of Leaders in Social Networks [15.05158252504978]
我々は、$n$ノードと$m$エッジを持つソーシャルネットワークにおける意見力学のDeGrootモデルに対するエッジ加算問題を考察する。提案アルゴリズムは,100万以上のノードを持つ大規模ネットワークに対して,効率的かつ効果的であることを示す。
論文参考訳（メタデータ） (2021-06-11T02:31:46Z)
Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文参考訳（メタデータ） (2021-04-06T15:34:14Z)
Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks [14.636457985379746]
本稿では,有向ピアツーピアネットワーク上での分散強化学習(DisRL)のポリシー評価問題に対する非同期手法を提案する。ネットワークの他のノードを待つことなく、各ノードは隣人からの(おそらく遅れた)情報を使用して、いつでもローカルに値関数を更新できる。
論文参考訳（メタデータ） (2020-03-01T08:12:08Z)

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