論文の概要: From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

• arxiv url: http://arxiv.org/abs/2609.20968v1
• Date: Thu, 17 Sep 2026 18:25:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-21 18:40:16.746238
• Title: From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences
• Title（参考訳）: スイッチングから動的レグレットへ:不偏乱列による簡易化
• Abstract要約: 本稿では、動的後悔の最小化を減らし、後悔の最小化を切り替える枠組みを提案する。 本研究は, コンベックスとexp-concaveの損失に対して, 最小値の最適値と一致した。
• 参考スコア（独自算出の注目度）: 40.138478711096354
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, attaining optimal bounds for strongly convex and exp-concave losses often involves intricate analysis. In this paper, we present a \textit{simple} framework that reduces dynamic regret minimization to switching regret minimization. As a result, we can derive dynamic regret bounds by using off-the-shelf algorithms with switching regret guarantees. The key idea of our reduction is to construct, for \textit{any} comparator sequence, an auxiliary random sequence that is unbiased at each round, with the controlled variance and a manageable number of switches. Combining this construction with suitable surrogate losses, we can decompose dynamic regret into the expected switching regret against the random sequence and its controlled variance. Theoretically, for strongly convex and exp-concave losses, we establish the $\widetilde{O}(T^{1/3}P_T^{2/3})$ dynamic regret bounds, where $T$ denotes the time horizon and $P_T$ denotes the path-length of the comparator sequence. Moreover, for general convex losses, the same reduction also recovers the $O(\sqrt{T(1+P_T)})$ dynamic regret bound. Notably, all our findings match the minimax optimal results for these three types of losses, highlighting the versatility of our proposed framework.
• Abstract（参考訳）: 非定常オンライン学習において、動的後悔は、オンライン学習者が時間変化のコンパレータシーケンスに対してどれだけうまく行動するかを示す尺度として注目されている。 かなりの進歩があったにも拘わらず、強い凸とexp-凹の損失に対して最適な境界に達することは、しばしば複雑な分析を伴う。 本稿では、動的後悔の最小化を減らし、後悔の最小化を切替える「textit{simple}」フレームワークを提案する。 その結果、既成のアルゴリズムを用いて、後悔の保証を切換えることで、動的後悔境界を導出することができる。 我々の削減の鍵となる考え方は、制御されたばらつきと管理可能なスイッチ数で各ラウンドで偏りのない補助的乱数列である「textit{any} comparator sequence」を構築することである。 この構成と適切な代理損失を組み合わせることで、動的後悔をランダムシーケンスとその制御された分散に対する切替後悔に分解することができる。 理論的には、強い凸とexp-凹の損失に対して、$\widetilde{O}(T^{1/3}P_T^{2/3})$ dynamic regret bounds, ここで$T$は時間地平線を表し、$P_T$はコンパレータ列のパス長を表す。 さらに、一般的な凸損失に対しては、同じ還元が$O(\sqrt{T(1+P_T)})$ dynamic regret boundを回復する。 特に,これらの3種類の損失に対して,すべての結果がminimax最適結果と一致し,提案したフレームワークの汎用性を強調した。

関連論文リスト

• Dynamic Regret Reduces to Kernelized Static Regret [63.36965242404415]
  本研究では,オンライン凸最適化において,任意のベンチマークシーケンスに対して低累積損失を達成することを目的とした動的後悔について検討する。 再生ケルネルヒルベルト空間 (RKHS) の形で適切な関数空間を構築することにより、最適$R_T(u_1,ldots,u_T) = MathcalO(sqrtsum_t|u_t-u_t-1|T)$ dynamic regret guarantee。
  論文  参考訳（メタデータ） (2025-07-07T21:09:33Z)
• Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability [65.99855403424979]
  混合可能性の概念を活用することで、動的後悔を著しく改善できることを示す。 固定共有更新を持つ指数重み付け法は,混合損失に対して$mathcalO(d T2/3 P_T2/3 log T)$ dynamic regretを達成できることを示す。
  論文  参考訳（メタデータ） (2025-06-12T12:00:08Z)
• An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
  線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。 R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-06-03T17:54:58Z)
• Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond [23.91519151164528]
  適切な学習設定で、Strongly Adaptiveアルゴリズムは、ほぼ最適な動的後悔を実現することができることを示す。 また, 適切なオンライン学習を行う場合, Exp-concaveの損失を伴って, 最適の動的後悔率を導出する。
  論文  参考訳（メタデータ） (2022-01-21T22:08:07Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR [13.165557713537389]
  我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。 我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
  論文  参考訳（メタデータ） (2021-11-22T21:52:47Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)

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

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