論文の概要: Discounted Online Convex Optimization: Uniform Regret Across a Continuous Interval

• arxiv url: http://arxiv.org/abs/2505.19491v1
• Date: Mon, 26 May 2025 04:20:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-27 16:58:43.161815
• Title: Discounted Online Convex Optimization: Uniform Regret Across a Continuous Interval
• Title（参考訳）: Discounted Online Convex Optimization: Unform Regretが継続的インターバルにまたがる
• Authors: Wenhao Yang, Sifan Yang, Lijun Zhang,
• Abstract要約: DNP (Discounted-Normal-Predictor) と呼ばれる割引アルゴリズムが2人の専門家の判断を組み合わせられることを示す。 分析の結果、DNPは2人の専門家の判断を組み合わせられることが明らかとなった。
• 参考スコア（独自算出の注目度）: 14.477697136416852
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reflecting the greater significance of recent history over the distant past in non-stationary environments, $\lambda$-discounted regret has been introduced in online convex optimization (OCO) to gracefully forget past data as new information arrives. When the discount factor $\lambda$ is given, online gradient descent with an appropriate step size achieves an $O(1/\sqrt{1-\lambda})$ discounted regret. However, the value of $\lambda$ is often not predetermined in real-world scenarios. This gives rise to a significant open question: is it possible to develop a discounted algorithm that adapts to an unknown discount factor. In this paper, we affirmatively answer this question by providing a novel analysis to demonstrate that smoothed OGD (SOGD) achieves a uniform $O(\sqrt{\log T/1-\lambda})$ discounted regret, holding for all values of $\lambda$ across a continuous interval simultaneously. The basic idea is to maintain multiple OGD instances to handle different discount factors, and aggregate their outputs sequentially by an online prediction algorithm named as Discounted-Normal-Predictor (DNP) (Kapralov and Panigrahy,2010). Our analysis reveals that DNP can combine the decisions of two experts, even when they operate on discounted regret with different discount factors.
• Abstract（参考訳）: オンライン凸最適化(OCO)では、非定常環境での過去における最近の歴史のさらなる重要性を反映して、新しい情報が到着すると過去のデータを優雅に忘れるように、$\lambda$-discounted regretが導入された。 割引係数$\lambda$が与えられると、適切なステップサイズのオンライン勾配降下が$O(1/\sqrt{1-\lambda})$ discounted regretを達成する。 しかし、実際のシナリオでは$\lambda$の値は決まっていないことが多い。 これは、未知の割引係数に適応する割引アルゴリズムを開発することが可能かという、重大なオープンな疑問を引き起こす。 本稿では, 円滑なOGD(SOGD)が均一な$O(\sqrt{\log T/1-\lambda})$割引された後悔を達成し, 連続する間隔で$\lambda$のすべての値を同時に保持することを示す新しい分析を提供することにより, この疑問に肯定的に答える。 基本的な考え方は、異なる割引要因を扱うために複数のOGDインスタンスを維持し、その出力をDNP(Discounted-Normal-Predictor)と呼ばれるオンライン予測アルゴリズムによって逐次集約することである(Kapralov and Panigrahy, 2010)。 分析の結果、DNPは2人の専門家の判断を組み合わせられることが明らかとなった。

関連論文リスト

• Better Rates for Random Task Orderings in Continual Linear Models [50.11453013647086]
  以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 実現可能な最小二乗の設定において、新しい最期境界を開発し、それらを連続学習に応用する。 タスクを繰り返しないランダム化だけで、十分に長いタスクで破滅的な忘れを防げることが、初めて証明された。
  論文  参考訳（メタデータ） (2025-04-06T18:39:45Z)
• Online Convex Optimization with a Separation Oracle [10.225358400539719]
  本稿では,オンライン凸最適化(OCO)のための新しいプロジェクションフリーアルゴリズムを提案する。 我々のアルゴリズムは、$widetildeO(sqrtdT + kappa d)$の償却バウンダリを達成し、ラウンド毎に$widetildeO(1)の呼び出ししか必要としない。
  論文  参考訳（メタデータ） (2024-10-03T13:35:08Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Degeneracy is OK: Logarithmic Regret for Network Revenue Management with Indiscrete Distributions [13.310272407473809]
  我々は、従来のネットワーク収益管理(NRM)問題について、意思決定を受理/退避し、IIDの到着を$T$で検討する。 本モデルでは,O(log2 T)$ regret を実現するオンラインアルゴリズムを開発した。 2階成長の仮定を追加して、$O(log T)$ regretを達成する2番目の結果を得る。
  論文  参考訳（メタデータ） (2022-10-14T17:52:19Z)
• Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
  円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。 提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
  論文  参考訳（メタデータ） (2022-05-02T08:48:22Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)

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

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