論文の概要: Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously
- arxiv url: http://arxiv.org/abs/2405.20824v1
- Date: Fri, 31 May 2024 14:16:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-03 14:27:53.944582
- Title: Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously
- Title（参考訳）: オンライン凸最適化: 任意のセグメンテーションを同時に切り替える最適レギュレータ
- Authors: Stephen Pasteris, Chris Hicks, Vasilios Mavroudis, Mark Herbster,
- Abstract要約: スイッチング後悔は、トライアルシーケンスの任意のセグメンテーションに対して定義され、各セグメンテーションの静的後悔の和に等しい。
我々のアルゴリズムは非常に効率的で、時間軸の対数的な空間と時間単位の複雑さを持つ。
- 参考スコア（独自算出の注目度）: 8.850922234275636
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the classic problem of online convex optimisation. Whereas the notion of static regret is relevant for stationary problems, the notion of switching regret is more appropriate for non-stationary problems. A switching regret is defined relative to any segmentation of the trial sequence, and is equal to the sum of the static regrets of each segment. In this paper we show that, perhaps surprisingly, we can achieve the asymptotically optimal switching regret on every possible segmentation simultaneously. Our algorithm for doing so is very efficient: having a space and per-trial time complexity that is logarithmic in the time-horizon. Our algorithm also obtains novel bounds on its dynamic regret: being adaptive to variations in the rate of change of the comparator sequence.
- Abstract（参考訳）: オンライン凸最適化の古典的な問題を考察する。
静的後悔の概念が定常問題に関係しているのに対し、切替後悔の概念は非定常問題により適している。
スイッチング後悔は、トライアルシーケンスの任意のセグメンテーションに対して定義され、各セグメンテーションの静的後悔の和に等しい。
本稿では,おそらく驚くべきことに,可能なセグメンテーションを同時に行うことで,漸近的に最適な切替後悔を実現することができることを示す。
我々のアルゴリズムは非常に効率的で、時間軸の対数的な空間と時間単位の複雑さを持つ。
また,このアルゴリズムは,コンパレータ配列の変化率の変動に適応することによる,その動的後悔の新たな限界も得る。
関連論文リスト
- Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Efficient Adaptive Regret Minimization [35.121567896321885]
オンライン凸最適化では、プレイヤーは繰り返しゲーム全体に対して固定されたコンパレータに対する後悔を最小限にすることを目的としている。
既存の適応的後悔アルゴリズムは計算的なペナルティに悩まされる - 典型的には、ゲームの繰り返し回数で対数的に増加する乗法的因子の順序である。
本稿では,この計算ペナルティをゲーム繰り返し回数で2倍に対数的に減らし,最適な適応的再帰限界を最小限に抑える方法を示す。
論文 参考訳（メタデータ） (2022-07-01T19:43:11Z) - No-Regret Learning in Games with Noisy Feedback: Faster Rates and
Adaptivity via Learning Rate Separation [76.61911795703062]
学習者が他の最適化エージェントと連続したゲームに関わった場合の後悔の問題を考察する。
この場合、全てのプレイヤーが非相対的アルゴリズムに従えば、完全に敵対する環境に対してかなり低い後悔を達成することができる。
本稿では,最悪とベストケースの後悔の保証を円滑に補間する完全適応手法を提案する。
論文 参考訳（メタデータ） (2022-06-13T10:13:51Z) - Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。
提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
論文 参考訳（メタデータ） (2022-05-02T08:48:22Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Continuation Path with Linear Convergence Rate [18.405645120971496]
経路追従アルゴリズムは、一連のサブプロブレムを順次解決する合成最適化問題によく用いられる。
本稿では,経路追従アルゴリズムの一次双対解析と,対象問題に対する線形収束率を保証するために,各サブプロブレムがどの程度正確に解けるかを決定する。
スパーシリティ誘導ペナルティによる最適化を考慮し、正規化パラメータに対するアクティブセットの変化を分析する。
論文 参考訳（メタデータ） (2021-12-09T18:42:13Z) - Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for
Mixable/Exp-Concave Losses [0.0]
動的環境における対数的静的後悔を伴う混合損失関数のオンライン最適化について検討する。
文献では,スイッチ1回あたりのほぼ対数的後悔を1時間あたりのポリノミカルな複雑さで達成できることが確認できた。
論文 参考訳（メタデータ） (2021-09-28T15:06:31Z) - Optimistic and Adaptive Lagrangian Hedging [11.698607733213226]
オンライン学習では、アルゴリズムは各ラウンドの敵によって選択される可能性のある損失のある環境と対戦する。
私たちは、後悔マッチングとヘッジを含むオンラインアルゴリズムのクラスであるLagrangian hedgingに楽観と適応的なステップを導入します。
論文 参考訳（メタデータ） (2021-01-23T23:32:40Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。