論文の概要: Communication Efficient Decentralization for Smoothed Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2411.08355v1
- Date: Wed, 13 Nov 2024 05:59:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-14 16:09:58.218454
- Title: Communication Efficient Decentralization for Smoothed Online Convex Optimization
- Title（参考訳）: 平滑なオンライン凸最適化のための通信効率の良い分散化
- Authors: Neelkamal Bhuyan, Debankur Mukherjee, Adam Wierman,
- Abstract要約: マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。
各ラウンドにおいて、各エージェント$i$は、オンラインの方法で、強い凸打撃コスト関数$fi_t$を受け取る。
通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
- 参考スコア（独自算出の注目度）: 9.449153668916098
- License:
- Abstract: We study the multi-agent Smoothed Online Convex Optimization (SOCO) problem, where $N$ agents interact through a communication graph. In each round, each agent $i$ receives a strongly convex hitting cost function $f^i_t$ in an online fashion and selects an action $x^i_t \in \mathbb{R}^d$. The objective is to minimize the global cumulative cost, which includes the sum of individual hitting costs $f^i_t(x^i_t)$, a temporal "switching cost" for changing decisions, and a spatial "dissimilarity cost" that penalizes deviations in decisions among neighboring agents. We propose the first decentralized algorithm for multi-agent SOCO and prove its asymptotic optimality. Our approach allows each agent to operate using only local information from its immediate neighbors in the graph. For finite-time performance, we establish that the optimality gap in competitive ratio decreases with the time horizon $T$ and can be conveniently tuned based on the per-round computation available to each agent. Moreover, our results hold even when the communication graph changes arbitrarily and adaptively over time. Finally, we establish that the computational complexity per round depends only logarithmically on the number of agents and almost linearly on their degree within the graph, ensuring scalability for large-system implementations.
- Abstract（参考訳）: マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。
各ラウンドにおいて、各エージェント$i$は、オンライン方式で強凸打撃コスト関数$f^i_t$を受け取り、アクション$x^i_t \in \mathbb{R}^d$を選択する。
目的は、個々の打撃コスト$f^i_t(x^i_t)$、決定を変更するための時間的「切り替えコスト」、近隣エージェント間の決定の偏りを罰する空間的「相似コスト」の合計を含む、世界的な累積コストを最小化することである。
マルチエージェントSOCOのための最初の分散アルゴリズムを提案し,その漸近的最適性を証明する。
提案手法により,各エージェントは,グラフ内の隣接部分からのローカル情報のみを用いて操作することができる。
有限時間性能において、競合比の最適性ギャップは時間地平線$T$で減少し、各エージェントに利用可能なラウンドごとの計算に基づいて、都合よく調整できることを示す。
さらに,通信グラフが時間とともに任意かつ適応的に変化する場合でも,その結果は持続する。
最後に, 1ラウンドあたりの計算複雑性はエージェントの数にのみ対数的に依存し, グラフ内のその次数にほぼ線形に依存し, 大規模システム実装のスケーラビリティを確保する。
関連論文リスト
- Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。
我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。
我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
論文 参考訳（メタデータ） (2024-10-22T19:34:53Z) - Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。
この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。
本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-31T22:59:23Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - PRECISION: Decentralized Constrained Min-Max Learning with Low
Communication and Sample Complexities [25.153506493249854]
min-max最適化問題に対する適応型マルチエージェント学習手法を提案する。
また,反復回数を削減できるPrecisionというアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-05T00:26:10Z) - Multi-Agent congestion cost minimization with linear function
approximation [0.0]
この作業では、ソースノードからゴールノードにネットワークをトラバースする複数のエージェントについて検討する。
エージェントの目的は、最小限の全体的なコストで、分散的な方法でゴールノードへのパスを見つけることである。
本稿では,新しいマルチエージェント・コンジェクション・コスト最小化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-26T08:45:44Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous
Decentralized Optimization [37.85806148420504]
分散最適化環境では、$n$最適化ノードのネットワーク内の各エージェント$i$は、プライベート関数$f_i$を持つ。
最適化対応の選択ルールを導入し、高い2倍のコスト改善で隣人を選択する。
提案したセットワイズGSルールは,ネットワークの最大次数による高速化を実現する。
論文 参考訳（メタデータ） (2022-07-15T15:37:03Z) - Distributed Contextual Linear Bandits with Minimax Optimal Communication
Cost [48.288452411283444]
そこでは,$N$エージェントが協調して,$d$次元の特徴を持つ線形帯域最適化問題を解く。
本稿では,LinUCBアルゴリズムの分散バッチ除去版であるDisBE-LUCBを提案する。
我々は、DisBE-LUCBの通信コストがわずか$tildemathcalO(dN)$であり、その後悔は少なくとも$tildemathcalO(dN)$であることを示す。
論文 参考訳（メタデータ） (2022-05-26T05:56:23Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - The Min-Max Complexity of Distributed Stochastic Convex Optimization
with Intermittent Communication [61.60069865891783]
間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。
本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
論文 参考訳（メタデータ） (2021-02-02T16:18:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。