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

• arxiv url: http://arxiv.org/abs/2305.12131v1
• Date: Sat, 20 May 2023 07:54:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-24 00:26:39.408881
• Title: Non-stationary Online Convex Optimization with Arbitrary Delays
• Title（参考訳）: 任意遅延を伴う非定常オンライン凸最適化
• Authors: Yuanyu Wan and Chang Yao and Mingli Song and Lijun Zhang
• Abstract要約: 本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtdT(P_T+1))$に削減できる改良アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 47.21966132874669
• 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 DOGD can attain an $O(\sqrt{dT}(P_T+1)$ dynamic regret bound in the worst case, where $d$ is the maximum delay, $T$ is the time horizon, and $P_T$ is the path length of comparators. More importantly, in case delays do not change the arrival order of gradients, it can automatically reduce the dynamic regret to $O(\sqrt{S}(1+P_T))$, where $S$ is the sum of delays. Furthermore, we develop an improved algorithm, which can reduce those dynamic regret bounds achieved by DOGD to $O(\sqrt{dT(P_T+1)})$ and $O(\sqrt{S(1+P_T)})$, respectively. The essential 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 both cases by deriving a matching lower bound.
• Abstract（参考訳）: オンライン凸最適化(oco: online convex optimization)は、勾配や他の関数の情報を任意に遅延させる任意の遅延を伴うが、近年注目を集めている。 定常環境に着目した従来の研究とは違って,非定常環境におけるOCOの遅延を調査し,コンパレータのシーケンスに対する動的後悔を最小限に抑えることを目的とする。 そこで本研究では,まず各遅延勾配に対して,到着順に応じて勾配降下ステップを実行する単純なアルゴリズムであるdogdを提案する。 その単純さにもかかわらず、新しい分析により、doddは最悪の場合に$o(\sqrt{dt}(p_t+1)$ dynamic regret bound($d$が最大遅延、$t$がタイムホライズン、$p_t$がコンパレータのパス長)に達することが示されている。 さらに重要なのは、遅延が勾配の到着順序を変えない場合、動的後悔は自動的に$O(\sqrt{S}(1+P_T))$に還元され、$S$は遅延の和である。 さらに,DOGDが達成した動的後悔境界を$O(\sqrt{dT(P_T+1)})$と$O(\sqrt{S(1+P_T)})$に削減できる改良アルゴリズムを開発した。 基本的なアイデアは、異なる学習率で複数の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)

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

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