論文の概要: Optimal Algorithms for Online Convex Optimization with Adversarial Constraints
- arxiv url: http://arxiv.org/abs/2310.18955v2
- Date: Fri, 24 May 2024 16:07:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-27 23:46:28.532938
- Title: Optimal Algorithms for Online Convex Optimization with Adversarial Constraints
- Title（参考訳）: 逆制約を考慮したオンライン凸最適化のための最適アルゴリズム
- Authors: Abhishek Sinha, Rahul Vaze,
- Abstract要約: COCOでは、そのラウンドのアクションを選択した後、学習者に凸コスト関数と凸制約関数を明らかにする。
オンラインポリシは,制限的な仮定を伴わずに,$O(sqrtT)$ regretと$O(sqrtT)$ CCVを同時に達成可能であることを示す。
- 参考スコア（独自算出の注目度）: 16.99491218081617
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: A well-studied generalization of the standard online convex optimization (OCO) is constrained online convex optimization (COCO). In COCO, on every round, a convex cost function and a convex constraint function are revealed to the learner after the action for that round is chosen. The objective is to design an online policy that simultaneously achieves a small regret while ensuring a small cumulative constraint violation (CCV) against an adaptive adversary interacting over a horizon of length $T$. A long-standing open question in COCO is whether an online policy can simultaneously achieve $O(\sqrt{T})$ regret and $O(\sqrt{T})$ CCV without any restrictive assumptions. For the first time, we answer this in the affirmative and show that an online policy can simultaneously achieve $O(\sqrt{T})$ regret and $\tilde{O}(\sqrt{T})$ CCV. Furthermore, in the case of strongly convex cost and convex constraint functions, the regret guarantee can be improved to $O(\log T)$ while keeping the CCV bound the same as above. We establish these results by effectively combining the adaptive regret bound of the AdaGrad algorithm with Lyapunov optimization - a classic tool from control theory. Surprisingly, the analysis is short and elegant.
- Abstract（参考訳）: 標準オンライン凸最適化(OCO)のよく研究された一般化は、制約付きオンライン凸最適化(COCO)である。
COCOでは、各ラウンドにおいて、そのラウンドのアクションが選択された後、学習者に凸コスト関数と凸制約関数を明らかにする。
目的は,T$の地平線上で相互作用する適応的敵に対して,最小限の累積制約違反(CCV)を確保すると同時に,わずかな後悔を同時に達成するオンラインポリシーを設計することである。
COCOにおける長年のオープンな疑問は、オンラインポリシーが制限的な仮定なしで同時に$O(\sqrt{T})$ regretと$O(\sqrt{T})$ CCVを達成できるかどうかである。
初めてこれを肯定的に答え、オンラインポリシーが$O(\sqrt{T})$ regretと$\tilde{O}(\sqrt{T})$ CCVを同時に達成できることを示します。
さらに、強い凸コストと凸制約関数の場合、CCVを上と同じ境界に保ちながら、後悔の保証を$O(\log T)$に改善することができる。
我々は、AdaGradアルゴリズムの適応的再帰境界と、制御理論の古典的なツールであるリアプノフ最適化を効果的に組み合わせて、これらの結果を確立する。
驚くべきことに、分析は短くエレガントだ。
関連論文リスト
- $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization [16.99491218081617]
目的は、静的な後悔と累積的制約違反(CCV)を同時に最小化することである。
アルゴリズムは、$O(sqrtT)$と$mincV, O(sqrtTlog T)$のCCVの静的後悔を保証する。
論文 参考訳（メタデータ） (2025-02-07T15:47:04Z) - Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints [10.047668792033033]
本稿では,オンライン凸最適化(OCO)フレームワークの時間的逆制約による一般化について検討する。
この問題では、凸判定セットから実行可能な動作を選択した後、各ラウンドのコスト関数とともに凸制約関数を$X,$とする。
我々は,一ラウンドに1回,線形プログラム(LP)ソルバに1回コールする*プロジェクションフリー*オンラインポリシーを提案する。
論文 参考訳（メタデータ） (2025-01-28T13:04:32Z) - An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
逆制約を伴うオンライン凸最適化(OCO)について検討する。
本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。
以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
論文 参考訳（メタデータ） (2024-12-11T03:06:42Z) - Tight Bounds for Online Convex Optimization with Adversarial Constraints [16.99491218081617]
COCOでは、そのラウンドのアクションを選択した後、学習者に凸コスト関数と凸制約関数を明らかにする。
我々は、オンラインポリシーが、制限的な仮定なしで、同時に$O(sqrtT)$ regretと$tildeO(sqrtT)$ CCVを達成できることを示します。
論文 参考訳（メタデータ） (2024-05-15T12:37:03Z) - Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints [31.526232903811533]
我々はOCO(Optimistically Safe OCO)と呼ぶアルゴリズムを導入し、そのアルゴリズムが$tildeO(sqrtT)$ regretと制約違反がないことを示す。
静的線形制約の場合、これは同じ仮定の下で、以前の最もよく知られた $tildeO(T2/3)$ regret よりも改善される。
時間的制約の場合、当社の作業は、$O(sqrtT)$ regretと$O(sqrtT)$ cumulative violationを示す既存の結果を補完します。
論文 参考訳（メタデータ） (2024-03-09T04:01:39Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。
ソフトマージン条件下でのバニラQ関数の類似した結果を示す。
我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
論文 参考訳（メタデータ） (2023-02-05T14:22:41Z) - On Instance-Dependent Bounds for Offline Reinforcement Learning with
Linear Function Approximation [80.86358123230757]
本稿では,Bootstrapped and Constrained Pessimistic Value Iteration (BCP-VI) というアルゴリズムを提案する。
部分的なデータカバレッジの仮定の下で、BCP-VI は最適な Q-値関数に正のギャップがあるときに、オフライン RL に対して $tildemathcalO(frac1K)$ の高速レートを得る。
これらは、アダプティブデータからの線形関数近似を持つオフラインRLに対してそれぞれ、最初の$tildemathcalO(frac1K)$boundと絶対零部分最適境界である。
論文 参考訳（メタデータ） (2022-11-23T18:50:44Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。