論文の概要: 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ラウンドあたりの計算複雑性はエージェントの数にのみ対数的に依存し, グラフ内のその次数にほぼ線形に依存し, 大規模システム実装のスケーラビリティを確保する。

関連論文リスト

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• 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)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• PRECISION: Decentralized Constrained Min-Max Learning with Low Communication and Sample Complexities [25.153506493249854]
  min-max最適化問題に対する適応型マルチエージェント学習手法を提案する。 また,反復回数を削減できるPrecisionというアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-05T00:26:10Z)
• 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)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。 本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
  論文  参考訳（メタデータ） (2021-02-02T16:18:29Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。