論文の概要: Non-stationary Online Convex Optimization with Arbitrary Delays

• arxiv url: http://arxiv.org/abs/2305.12131v3
• Date: Sun, 23 Jun 2024 14:15:45 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-26 05:18:24.615348
• Title: Non-stationary Online Convex Optimization with Arbitrary Delays
• Title（参考訳）: 任意遅延を用いた非定常オンライン凸最適化
• Authors: Yuanyu Wan, Chang Yao, Mingli Song, Lijun Zhang,
• Abstract要約: 本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 50.46856739179311
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online convex optimization (OCO) with arbitrary delays, in which gradients or other information of functions could be arbitrarily delayed, has received increasing attention recently. Different from previous studies that focus on stationary environments, this paper investigates the delayed OCO in non-stationary environments, and aims to minimize the dynamic regret with respect to any sequence of comparators. To this end, we first propose a simple algorithm, namely DOGD, which performs a gradient descent step for each delayed gradient according to their arrival order. Despite its simplicity, our novel analysis shows that the dynamic regret of DOGD can be automatically bounded by $O(\sqrt{\bar{d}T}(P_T+1))$ under mild assumptions, and $O(\sqrt{dT}(P_T+1))$ in the worst case, where $\bar{d}$ and $d$ denote the average and maximum delay respectively, $T$ is the time horizon, and $P_T$ is the path-length of comparators. Furthermore, we develop an improved algorithm, which reduces those dynamic regret bounds achieved by DOGD to $O(\sqrt{\bar{d}T(P_T+1)})$ and $O(\sqrt{dT(P_T+1)})$, respectively. The key idea is to run multiple DOGD with different learning rates, and utilize a meta-algorithm to track the best one based on their delayed performance. Finally, we demonstrate that our improved algorithm is optimal in the worst case by deriving a matching lower bound.
• Abstract（参考訳）: ゆるやかな遅延を伴うオンライン凸最適化(OCO)が近年注目を集めている。 定常環境に着目した従来の研究とは違って,非定常環境におけるOCOの遅延を調査し,コンパレータのシーケンスに対する動的後悔を最小限に抑えることを目的とする。 そこで本研究では,まず,到着順に応じて遅延勾配の勾配降下ステップを実行する,単純なアルゴリズムであるDOGDを提案する。 その単純さにもかかわらず、我々の新しい分析では、DOGDのダイナミックな後悔は、控えめな仮定の下で$O(\sqrt{\bar{d}T}(P_T+1))$と$O(\sqrt{dT}(P_T+1))$で自動的に束縛され、最悪の場合は$O(\sqrt{dT}(P_T+1)$がそれぞれ平均遅延と最大遅延を表す。 さらに,DOGDが達成した動的後悔境界を$O(\sqrt{\bar{d}T(P_T+1)})$と$O(\sqrt{dT(P_T+1)})$に削減する改良アルゴリズムを開発した。 鍵となるアイデアは、異なる学習率で複数のDOGDを実行し、メタアルゴリズムを使用して、遅延したパフォーマンスに基づいて、最高のものを追跡することである。 最後に, 改良アルゴリズムは, 一致した下界を導出することにより, 最悪の場合において最適であることを示す。

関連論文リスト

• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Asynchronous Training Schemes in Distributed Learning with Time Delay [17.259708772713164]
  分散ディープラーニングの文脈では、固定重みや勾配の問題によってアルゴリズムの性能が低下する可能性がある。 本稿では,静的な重みや勾配の問題に対処する別のアプローチを提案する。 また,PC-ASGDの実用版として,トレードオフパラメータの決定を支援する条件を適用して提案する。
  論文  参考訳（メタデータ） (2022-08-28T07:14:59Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis [27.679514676804057]
  オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。 実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
  論文  参考訳（メタデータ） (2020-10-26T01:33:05Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。 我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
  論文  参考訳（メタデータ） (2020-10-12T20:53:52Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)

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

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