論文の概要: 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アルゴリズムの適応的再帰境界と、制御理論の古典的なツールであるリアプノフ最適化を効果的に組み合わせて、この結果を確立する。
驚くべきことに、分析は短くエレガントだ。
関連論文リスト
- 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) - 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) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。
ソフトマージン条件下でのバニラQ関数の類似した結果を示す。
我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
論文 参考訳（メタデータ） (2023-02-05T14:22:41Z) - Exploiting the Curvature of Feasible Sets for Faster Projection-Free
Online Learning [8.461907111368628]
我々はオンライン凸最適化(OCO)のための新しい効率的なプロジェクションフリーアルゴリズムを開発した。
我々は,LOOracleを1ラウンドに2回呼び出すOCOアルゴリズムを開発し,ほぼ最適の$widetildeO(sqrtT)を後悔する。
また, 一般凸集合に対して, 1ラウンド当たりのO(d)$ LO Oracleへのコール数を$widetilde O(d)$に設定するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-23T17:13:46Z) - 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) - Projection-free Online Learning over Strongly Convex Sets [24.517908972536432]
我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。
一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2020-10-16T05:42:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。