論文の概要: Decentralized Online Convex Optimization with Unknown Feedback Delays

• arxiv url: http://arxiv.org/abs/2601.07901v1
• Date: Mon, 12 Jan 2026 12:59:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-14 18:27:18.90302
• Title: Decentralized Online Convex Optimization with Unknown Feedback Delays
• Title（参考訳）: 未知のフィードバック遅延を考慮した分散オンライン凸最適化
• Authors: Hao Qiu, Mengxiao Zhang, Juliette Achddou,
• Abstract要約: 本稿では,D-OCOを時間的・エージェント的に異なるフィードバック遅延下で研究する。 既存のアルゴリズムでは、エージェントの合計遅延に関する事前知識を前提としており、遅延パラメータとネットワークパラメータの両方に最適な依存を被っている。 改良されたO N $sqrt$ d tot + N $sqrt$ T (1-$2) 1/4 の後悔境界を実現する新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 12.543159785477952
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decentralized online convex optimization (D-OCO), where multiple agents within a network collaboratively learn optimal decisions in real-time, arises naturally in applications such as federated learning, sensor networks, and multi-agent control. In this paper, we study D-OCO under unknown, time-and agent-varying feedback delays. While recent work has addressed this problem (Nguyen et al., 2024), existing algorithms assume prior knowledge of the total delay over agents and still suffer from suboptimal dependence on both the delay and network parameters. To overcome these limitations, we propose a novel algorithm that achieves an improved regret bound of O N $\sqrt$ d tot + N $\sqrt$ T (1-$σ$2) 1/4 , where T is the total horizon, d tot denotes the average total delay across agents, N is the number of agents, and 1 -$σ$ 2 is the spectral gap of the network. Our approach builds upon recent advances in D-OCO (Wan et al., 2024a), but crucially incorporates an adaptive learning rate mechanism via a decentralized communication protocol. This enables each agent to estimate delays locally using a gossip-based strategy without the prior knowledge of the total delay. We further extend our framework to the strongly convex setting and derive a sharper regret bound of O N $δ$max ln T $α$ , where $α$ is the strong convexity parameter and $δ$ max is the maximum number of missing observations averaged over agents. We also show that our upper bounds for both settings are tight up to logarithmic factors. Experimental results validate the effectiveness of our approach, showing improvements over existing benchmark algorithms.
• Abstract（参考訳）: ネットワーク内の複数のエージェントが協調してリアルタイムに最適な決定を学習する分散オンライン凸最適化(D-OCO)は、フェデレーション学習、センサネットワーク、マルチエージェント制御などのアプリケーションで自然に発生する。 本稿では,D-OCOを時間的・エージェント的に異なるフィードバック遅延下で研究する。 最近の研究(Nguyen et al , 2024)ではこの問題に対処しているが、既存のアルゴリズムではエージェントの遅延に関する事前の知識を前提としており、遅延パラメータとネットワークパラメータの両方に最適でない依存に悩まされている。 これらの制限を克服するために、O N $\sqrt$ d tot + N $\sqrt$ T (1-$σ$2) 1/4 という改良された後悔境界を達成する新しいアルゴリズムを提案する。 我々のアプローチは、近年のD-OCO(Wan et al , 2024a)の進歩に基づいているが、分散通信プロトコルを介して適応的な学習率メカニズムを重要視している。 これにより、各エージェントは、全遅延の事前知識を必要とせずに、ゴシップベースの戦略を用いて、ローカルで遅延を推定できる。 我々はさらに、我々のフレームワークを強い凸設定にまで拡張し、O N $δ$max ln T $α$ のよりシャープな後悔境界を導出する。 また、両方の設定の上限が対数的要因に厳密であることも示しています。 実験により提案手法の有効性を検証し,既存のベンチマークアルゴリズムに比較して改良を加えた。

関連論文リスト

• Revisiting Multi-Agent Asynchronous Online Optimization with Delays: the Strongly Convex Case [14.550539239345582]
  複数エージェントの非同期オンライン最適化を遅延で再検討し、各ラウンドで決定を下すにはエージェントの1つだけがアクティブになる。 本稿では,従来のフォロー・ザ・リーダーアルゴリズムであるFTDLの遅延型を提案する。
  論文  参考訳（メタデータ） (2025-03-13T03:49:25Z)
• Fully First-Order Methods for Decentralized Bilevel Optimization [17.20330936572045]
  本稿では,エージェントが隣人とのみ通信する分散二段階最適化(DSBO)に焦点を当てる。 本稿では,既存の作品に広く採用されている2次オラクルよりもはるかに安価な1次オラクルのみを必要とする新しいアルゴリズムである,分散グラディエントDescent and Ascent with Gradient Tracking (DSGDA-GT)を提案する。
  論文  参考訳（メタデータ） (2024-10-25T06:11:43Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。 遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
  論文  参考訳（メタデータ） (2024-03-25T22:49:56Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
  本研究では,N$エージェントのネットワークが協調して線形帯域最適化問題を解く分散線形帯域幅について検討する。 ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズム DLUCB を提案する。 私たちのアイデアは、より困難な、安全な盗賊の設定にもかかわらず、自然界に広まっています。
  論文  参考訳（メタデータ） (2020-12-01T07:33:00Z)

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

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