論文の概要: Tight Bounds for Online Convex Optimization with Adversarial Constraints
- arxiv url: http://arxiv.org/abs/2405.09296v1
- Date: Wed, 15 May 2024 12:37:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-16 13:36:32.787413
- Title: Tight Bounds for Online Convex Optimization with Adversarial Constraints
- Title（参考訳）: 逆制約を考慮したオンライン凸最適化のためのタイト境界
- Authors: Abhishek Sinha, Rahul Vaze,
- Abstract要約: COCOでは、そのラウンドのアクションを選択した後、学習者に凸コスト関数と凸制約関数を明らかにする。
我々は、オンラインポリシーが、制限的な仮定なしで、同時に$O(sqrtT)$ regretと$tildeO(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 small cumulative constraint violation (CCV) against an adaptive adversary. 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. We establish this result 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では、各ラウンドにおいて、そのラウンドのアクションが選択された後、学習者に凸コスト関数と凸制約関数を明らかにする。
目的は、適応的な敵に対して小さな累積制約違反(CCV)を保証しながら、小さな後悔を同時に達成するオンラインポリシーを設計することである。
COCOにおける長年のオープンな疑問は、オンラインポリシーが制限的な仮定なしで同時に$O(\sqrt{T})$ regretと$O(\sqrt{T})$ CCVを達成できるかどうかである。
初めてこれを肯定的に答え、オンラインポリシーが$O(\sqrt{T})$ regretと$\tilde{O}(\sqrt{T})$ CCVを同時に達成できることを示します。
我々は、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) - Revisiting Projection-Free Online Learning with Time-Varying Constraints [35.573654458435854]
我々は制約付きオンライン凸最適化について検討し、そこでは決定は固定的で典型的には複雑な領域に属する必要がある。
いくつかのプロジェクションフリーな手法が$mathcalO(T3/4 sqrtlog T)$ regret boundと$mathcalO(T3/4 sqrtlog T)$ cumulative constraint violation (CCV) bound for general convex lossで提案されている。
本稿では,損失関数が強凸である場合に,この結果を改善し,さらにテクスチノーベルの後悔とCCV境界を確立する。
論文 参考訳（メタデータ） (2025-01-27T13:38:51Z) - 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) - Optimal Algorithms for Online Convex Optimization with Adversarial Constraints [16.99491218081617]
COCOでは、そのラウンドのアクションを選択した後、学習者に凸コスト関数と凸制約関数を明らかにする。
我々は、オンラインポリシーが、制限的な仮定なしで、同時に$O(sqrtT)$ regretと$tildeO(sqrtT)$ CCVを達成できることを示します。
論文 参考訳（メタデータ） (2023-10-29T09:55:41Z) - 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) - 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) - Policy Finetuning: Bridging Sample-Efficient Offline and Online
Reinforcement Learning [59.02541753781001]
本稿では、学習者が「参照ポリシー」にさらにアクセス可能なオンラインRLの政策微調整に関する理論的研究を開始する。
我々はまず、$varepsilon$$widetildeO(H3SCstar/varepsilon2)$のエピソード内で、ほぼ最適ポリシーを求める鋭いオフライン還元アルゴリズムを設計する。
次に、Omega(H3SminCstar, A/varepsilon2)$のサンプル複雑性を、任意のポリシー微調整アルゴリズムに対して低いバウンドで設定します。
論文 参考訳（メタデータ） (2021-06-09T08:28:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。