論文の概要: Revisiting Multi-Agent Asynchronous Online Optimization with Delays: the Strongly Convex Case

• arxiv url: http://arxiv.org/abs/2503.10013v1
• Date: Thu, 13 Mar 2025 03:49:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-14 15:51:05.746849
• Title: Revisiting Multi-Agent Asynchronous Online Optimization with Delays: the Strongly Convex Case
• Title（参考訳）: 遅延によるマルチエージェント非同期オンライン最適化の再検討:強凸の場合
• Authors: Lingchan Bao, Tong Wei, Yuanyu Wan,
• Abstract要約: 複数エージェントの非同期オンライン最適化を遅延で再検討し、各ラウンドで決定を下すにはエージェントの1つだけがアクティブになる。 本稿では,従来のフォロー・ザ・リーダーアルゴリズムであるFTDLの遅延型を提案する。
• 参考スコア（独自算出の注目度）: 14.550539239345582
• License:
• Abstract: We revisit multi-agent asynchronous online optimization with delays, where only one of the agents becomes active for making the decision at each round, and the corresponding feedback is received by all the agents after unknown delays. Although previous studies have established an $O(\sqrt{dT})$ regret bound for this problem, they assume that the maximum delay $d$ is knowable or the arrival order of feedback satisfies a special property, which may not hold in practice. In this paper, we surprisingly find that when the loss functions are strongly convex, these assumptions can be eliminated, and the existing regret bound can be significantly improved to $O(d\log T)$ meanwhile. Specifically, to exploit the strong convexity of functions, we first propose a delayed variant of the classical follow-the-leader algorithm, namely FTDL, which is very simple but requires the full information of functions as feedback. Moreover, to handle the more general case with only the gradient feedback, we develop an approximate variant of FTDL by combining it with surrogate loss functions. Experimental results show that the approximate FTDL outperforms the existing algorithm in the strongly convex case.
• Abstract（参考訳）: 我々は,複数エージェントの非同期オンライン最適化を遅延で再検討し,各ラウンドで決定を下すためにエージェントの1つだけがアクティブになり,その応答は未知の遅延の後,すべてのエージェントから受信される。 これまでの研究では、この問題に対して$O(\sqrt{dT})$ regret boundを定めているが、彼らは最大遅延$d$が理解できるか、フィードバックの到着順序が特別な性質を満たすと仮定している。 本稿では、損失関数が強く凸であるとき、これらの仮定は排除され、既存の後悔境界は$O(d\log T)$に大きく改善される。 具体的には、関数の強い凸性を利用するために、まず、関数の完全な情報をフィードバックとして必要とする古典的追従型アルゴリズムFTDLの遅延変種を提案する。 さらに、勾配フィードバックのみでより一般的なケースを扱うために、代理損失関数と組み合わせてFTDLの近似変種を開発する。 実験の結果, FTDL は強凸の場合, 既存のアルゴリズムよりも優れていることがわかった。

関連論文リスト

• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation [62.969796245827006]
  Delayed-PSVI は楽観的な値に基づくアルゴリズムであり、後続サンプリングによる雑音摂動により値関数空間を探索する。 我々のアルゴリズムは、未知の遅延が存在する場合に、$widetildeO(sqrtd3H3 T + d2H2 E[tau]$最悪の後悔を実現する。 遅延LPSVIのための勾配に基づく近似サンプリングスキームをLangevin動的に組み込んだ。
  論文  参考訳（メタデータ） (2023-10-29T06:12:43Z)
• Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent [63.43247232708004]
  非同期で実行される勾配降下は、大規模機械学習モデルのトレーニングにおいて重要な役割を果たす。 既存の一般化誤差境界は悲観的であり、非同期遅延と一般化の相関を明らかにすることはできない。 我々の理論的結果は、非同期遅延は遅延SGDアルゴリズムの一般化誤差を低減することを示唆している。
  論文  参考訳（メタデータ） (2023-08-18T10:00:27Z)
• Min-Max Optimization under Delays [26.830212508878162]
  大規模な機械学習問題では遅延と非同期は避けられない。 min-max最適化に類似した理論は存在しない。 たとえ小さな遅延であっても、エクストラグラディエントのような顕著なアルゴリズムが分岐する可能性があることを示す。
  論文  参考訳（メタデータ） (2023-07-13T16:39:01Z)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。 我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
  論文  参考訳（メタデータ） (2022-05-15T08:27:12Z)
• Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-fidelity Feedback [11.064341598231195]
  ブラックボックス最適化問題では,評価やシミュレーションオラクルのフィードバックによってのみ機能にアクセス可能な未知の目的関数を最大化することを目的としている。 ProCrastinated Tree Search (PCTS) と呼ばれる階層的楽観木探索(HOO)の汎用的拡張を提案する。 我々は,PCTSの遅延,雑音,多面的フィードバックによる後悔を定量化する汎用的証明手法を提案する。
  論文  参考訳（メタデータ） (2021-10-14T08:55:41Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
  オンライン凸最適化の問題点を未知の遅延で検討する。 まず、OGDの遅延変形を強凸関数に拡張する。 我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
  論文  参考訳（メタデータ） (2021-03-21T10:16:15Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。 我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
  論文  参考訳（メタデータ） (2020-10-12T20:53:52Z)

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

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