論文の概要: Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory
- arxiv url: http://arxiv.org/abs/2602.06902v1
- Date: Fri, 06 Feb 2026 17:50:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-09 22:18:26.508524
- Title: Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory
- Title（参考訳）: パラメータフリー動的レグレット:時間変動移動コスト、遅延フィードバック、記憶
- Authors: Emmanuel Esposito, Andrew Jacobsen, Hao Qiu, Mengxiao Zhang,
- Abstract要約: 移動コストを伴う非拘束型オンライン凸最適化(OCO)における動的後悔について検討した。
我々の主な貢献は、この設定に対する最初のコンパレータ適応動的後悔を確立する新しいアルゴリズムである。
- 参考スコア（独自算出の注目度）: 18.95079821752574
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study dynamic regret in unconstrained online convex optimization (OCO) with movement costs. Specifically, we generalize the standard setting by allowing the movement cost coefficients $λ_t$ to vary arbitrarily over time. Our main contribution is a novel algorithm that establishes the first comparator-adaptive dynamic regret bound for this setting, guaranteeing $\widetilde{\mathcal{O}}(\sqrt{(1+P_T)(T+\sum_t λ_t)})$ regret, where $P_T$ is the path length of the comparator sequence over $T$ rounds. This recovers the optimal guarantees for both static and dynamic regret in standard OCO as a special case where $λ_t=0$ for all rounds. To demonstrate the versatility of our results, we consider two applications: OCO with delayed feedback and OCO with time-varying memory. We show that both problems can be translated into time-varying movement costs, establishing a novel reduction specifically for the delayed feedback setting that is of independent interest. A crucial observation is that the first-order dependence on movement costs in our regret bound plays a key role in enabling optimal comparator-adaptive dynamic regret guarantees in both settings.
- Abstract（参考訳）: 本稿では,移動コストを伴う制約のないオンライン凸最適化(OCO)における動的後悔について検討する。
具体的には、移動コスト係数$λ_t$を時間とともに任意に変化させることにより、標準設定を一般化する。
我々の主な貢献は、この設定に対する最初のコンパレータ適応的動的後悔(英語版)を確立する新しいアルゴリズムであり、$\widetilde{\mathcal{O}}(\sqrt{(1+P_T)(T+\sum_t λ_t)})$ regret, ここで$P_T$は$T$以上のコンパレータ列のパス長である。
これにより、すべてのラウンドに対して$λ_t=0$の特別な場合として、標準OCOにおける静的および動的後悔の両方に対する最適保証が回復される。
結果の汎用性を示すために,遅延フィードバックによるOCOと,時間変化メモリによるOCOの2つの応用を検討した。
いずれの問題も時間的変化による移動コストに変換可能であることを示し、独立性のある遅延フィードバック設定に特化して、新たな削減を実現する。
重要な観察は、我々の後悔境界における移動コストへの第一次依存が、両方の設定において最適なコンパレータ適応動的後悔の保証を可能にする上で重要な役割を担っていることである。
関連論文リスト
- Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。
ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。
Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
論文 参考訳（メタデータ） (2023-05-20T07:54:07Z) - ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive
Non-Stationary Dueling Bandits [20.128001589147512]
本研究では,非定常デュエル帯域の問題について検討し,この問題に対する適応的動的後悔アルゴリズムを提案する。
ほぼ最適の $tildeO(sqrtStexttCW T)$ dynamic regret bound を示します。
論文 参考訳（メタデータ） (2022-10-25T20:26:02Z) - Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。
提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
論文 参考訳（メタデータ） (2022-05-02T08:48:22Z) - Dynamic Regret of Online Mirror Descent for Relatively Smooth Convex
Cost Functions [30.412826613009518]
リプシッツ連続性も均一な滑らか性も存在しない場合でも、動的後悔を束縛することは可能であることを示す。
次に、相対的に強い凸性の付加条件により、動的後悔は経路長と勾配変化によって境界付けられることを示す。
論文 参考訳（メタデータ） (2022-02-25T17:35:07Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。