論文の概要: Efficient Adaptive Regret Minimization
- arxiv url: http://arxiv.org/abs/2207.00646v1
- Date: Fri, 1 Jul 2022 19:43:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-09 13:22:52.580541
- Title: Efficient Adaptive Regret Minimization
- Title(参考訳): 適応レジスト最小化の効率化
- Authors: Zhou Lu, Elad Hazan
- Abstract要約: オンライン凸最適化では、プレイヤーは繰り返しゲーム全体に対して固定されたコンパレータに対する後悔を最小限にすることを目的としている。
既存の適応的後悔アルゴリズムは計算的なペナルティに悩まされる - 典型的には、ゲームの繰り返し回数で対数的に増加する乗法的因子の順序である。
本稿では,この計算ペナルティをゲーム繰り返し回数で2倍に対数的に減らし,最適な適応的再帰限界を最小限に抑える方法を示す。
- 参考スコア(独自算出の注目度): 35.121567896321885
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In online convex optimization the player aims to minimize her regret against
a fixed comparator over the entire repeated game. Algorithms that minimize
standard regret may converge to a fixed decision, which is undesireable in
changing or dynamic environments. This motivates the stronger metric of
adaptive regret, or the maximum regret over any continuous sub-interval in
time.
Existing adaptive regret algorithms suffer from a computational penalty -
typically on the order of a multiplicative factor that grows logarithmically in
the number of game iterations. In this paper we show how to reduce this
computational penalty to be doubly logarithmic in the number of game
iterations, and with minimal degradation to the optimal attainable adaptive
regret bounds.
- Abstract(参考訳): オンライン凸最適化では、プレイヤーは繰り返しゲーム全体の固定コンパレータに対する後悔を最小限に抑える。
標準的な後悔を最小限に抑えるアルゴリズムは、変化や動的環境では望ましくない固定された決定に収束する。
これにより、適応的後悔のより強い指標や、時間内の任意の連続的なサブインターバルに対する最大後悔が動機づけられる。
既存の適応的後悔アルゴリズムは、ゲーム繰り返し数で対数的に増加する乗法係数の順序によって、計算ペナルティに苦しむ。
本稿では,この計算ペナルティをゲーム反復回数の2倍対数に削減し,最適到達可能な適応的後悔限度まで最小分解する方法について述べる。
関連論文リスト
- Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret [10.700891331004799]
本稿では,非損失関数を用いた分散オンライン帯域最適化問題について検討する。
プレイヤーは敵を選択し、そのプレイヤーに任意の非線形損失関数を割り当てる。
予想されるアルゴリズムの後悔は、2点偏差を用いた既存のアルゴリズムに匹敵する。
論文 参考訳(メタデータ) (2024-09-24T02:37:33Z) - Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously [8.850922234275636]
スイッチング後悔は、トライアルシーケンスの任意のセグメンテーションに対して定義され、各セグメンテーションの静的後悔の和に等しい。
我々のアルゴリズムは非常に効率的で、時間軸の対数的な空間と時間単位の複雑さを持つ。
論文 参考訳(メタデータ) (2024-05-31T14:16:52Z) - Resetting the Optimizer in Deep RL: An Empirical Study [10.907980864371213]
深層強化学習における最適値関数の近似に着目する。
この単純な修正により,Atariベンチマークにおける深部RLの性能が大幅に向上することが実証された。
論文 参考訳(メタデータ) (2023-06-30T17:53:50Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - No-Regret Learning in Games with Noisy Feedback: Faster Rates and
Adaptivity via Learning Rate Separation [76.61911795703062]
学習者が他の最適化エージェントと連続したゲームに関わった場合の後悔の問題を考察する。
この場合、全てのプレイヤーが非相対的アルゴリズムに従えば、完全に敵対する環境に対してかなり低い後悔を達成することができる。
本稿では,最悪とベストケースの後悔の保証を円滑に補間する完全適応手法を提案する。
論文 参考訳(メタデータ) (2022-06-13T10:13:51Z) - Optimistic and Adaptive Lagrangian Hedging [11.698607733213226]
オンライン学習では、アルゴリズムは各ラウンドの敵によって選択される可能性のある損失のある環境と対戦する。
私たちは、後悔マッチングとヘッジを含むオンラインアルゴリズムのクラスであるLagrangian hedgingに楽観と適応的なステップを導入します。
論文 参考訳(メタデータ) (2021-01-23T23:32:40Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。