論文の概要: On the Relation Between Interval Regret and Dynamic Regret

• arxiv url: http://arxiv.org/abs/2609.34423v1
• Date: Mon, 28 Sep 2026 06:40:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 20:50:04.903609
• Title: On the Relation Between Interval Regret and Dynamic Regret
• Title（参考訳）: 区間レグレットと動的レグレットの関係について
• Abstract要約: インターバルな後悔とダイナミックな後悔が2つの代表的なパフォーマンス指標として紹介されている。 最適間隔後悔を持つアルゴリズムは、自動的に最適ダイナミック後悔を達成するべきであると広く予想されている。 局所的な適応性を利用して最適な動的後悔を得る方法を示す。
• 参考スコア（独自算出の注目度）: 72.1530234801628
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Non-stationary online learning has attracted much attention in recent years, as static regret is insufficient to guide algorithm design in changing environments. To address this limitation, interval regret and dynamic regret have been introduced as two representative performance metrics that strengthen static regret in complementary directions. Interval regret requires an online algorithm to achieve competitive static regret over every local time interval, whereas dynamic regret evaluates performance against an arbitrary sequence of time-varying comparators. Despite their importance, the relation between these metrics has long remained unclear. Prior work has often regarded interval regret as the stronger notion, based on the intuition that local guarantees should naturally induce global guarantees. Consequently, it is widely conjectured that an algorithm with optimal interval regret should automatically attain optimal dynamic regret. In this paper, we first establish a negative result that refutes this intuition of a metric-level implication. Specifically, for both convex and curved functions (including exp-concave and strongly convex functions), we show that there exist instances in which an algorithm with optimal interval regret nevertheless fails to achieve optimal dynamic regret. We then show how to leverage local adaptivity to obtain optimal dynamic regret. In particular, optimal dynamic regret can be attained by invoking an interval regret minimization process over an enlarged Euclidean ball containing the original convex feasible domain and using a suitable domain-converted surrogate loss. This reduction applies to both convex and curved functions. As a byproduct, we obtain the first proper and efficient algorithm with optimal dynamic regret for exp-concave functions, improving prior results while significantly simplifying the analysis.
• Abstract（参考訳）: 静的な後悔は、変化する環境におけるアルゴリズム設計を導くのに不十分であるため、近年、非定常オンライン学習が注目されている。 この制限に対処するため、相補的な方向における静的な後悔を強化する2つの代表的なパフォーマンス指標として、インターバル後悔とダイナミック後悔が導入された。 インターバル後悔は、ローカル時間間隔毎に競合する静的後悔を達成するためにオンラインアルゴリズムを必要とするが、動的後悔は、任意の時間変化のコンパレータに対してパフォーマンスを評価する。 これらの指標の重要性にもかかわらず、これらの指標の関係は長い間不明である。 先行研究は、局所的な保証が自然に世界的な保証を導き出すという直感に基づいて、インターバル・後悔をより強い概念とみなすことが多い。 したがって、最適間隔の後悔を持つアルゴリズムは、自動的に最適な動的後悔を達成するべきであると広く推測されている。 本稿では,まず,この計量レベル含意の直観を否定する否定的な結果を確立する。 具体的には、凸関数と曲線関数(exp-concave関数と強凸関数を含む)の両方に対して、最適間隔後悔を持つアルゴリズムが最適動的後悔を達成できない事例が存在することを示す。 次に、局所的な適応性を活用して最適な動的後悔を得る方法を示す。 特に、元の凸可能領域を含む拡大ユークリッド球にインターバル後悔最小化プロセスを呼び起こし、適切なドメイン変換サロゲート損失を用いることで、最適な動的後悔を実現することができる。 この還元は凸関数と曲線関数の両方に適用される。 副産物として、exp-concave関数に対して最適に動的に後悔し、解析を著しく単純化し、事前結果を改善した最初の固有かつ効率的なアルゴリズムを得る。

関連論文リスト

• Online Learning with Gradient-Variation Interval Regret [54.59204826681113]
  そこで本研究では,勾配変動を伴う時間間隔のリフレッシュなスケーリングを実現するオンライン学習アルゴリズムを提案する。 提案手法では, よりシンプルで効率的な2層オンラインアンサンブル構造を用いて, 高い理論的保証を実現する。
  論文  参考訳（メタデータ） (2026-06-02T16:16:45Z)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。 インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。 これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
  論文  参考訳（メタデータ） (2023-09-27T21:54:52Z)
• Dynamic Regret of Adaptive Gradient Methods for Strongly Convex Problems [0.0]
  我々は、動的後悔の概念を通じて、強い凸条件でADAGRAD(M-ADAGRAD)の変種を通り抜ける。 我々は、環境の非定常性を本質的に反映する最小化シーケンスのパス長という観点で、後悔すべき境界を示す。
  論文  参考訳（メタデータ） (2022-09-04T12:40:57Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  非定常環境におけるオンライン凸最適化について検討する。 パフォーマンス指標として動的後悔を選択します。 本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-07T14:10:57Z)
• Minimizing Dynamic Regret and Adaptive Regret Simultaneously [60.17824125301273]
  動的後悔と適応的後悔を同時に最小化できる新しいオンラインアルゴリズムを提案する。 我々の理論的保証は、あるアルゴリズムが任意の間隔で動的後悔を最小化できるという意味でさらに強い。
  論文  参考訳（メタデータ） (2020-02-06T03:32:37Z)

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

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