Fugu-MT 論文翻訳(概要): Optimal Bounds for Adversarial Constrained Online Convex Optimization

論文の概要: Optimal Bounds for Adversarial Constrained Online Convex Optimization

arxiv url: http://arxiv.org/abs/2503.13366v3
Date: Wed, 09 Apr 2025 21:32:42 GMT
ステータス: 翻訳完了
システム内更新日: 2025-04-11 15:12:49.394132
Title: Optimal Bounds for Adversarial Constrained Online Convex Optimization
Title（参考訳）: 制約付きオンライン凸最適化のための最適境界
Authors: Ricardo N. Ferreira, Cláudia Soares,
Abstract要約: 後悔とCCVの両方で最適な$O(sqrtT)$バウンドが得られることを示す。制約関数に最小限のペナルティを課す新しい代理損失関数に基づいて、Follow-the-Regularized-Leader と Online Gradient Descent の両方が最適境界を達成することを示す。
参考スコア（独自算出の注目度）: 1.9336815376402723
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: Constrained Online Convex Optimization (COCO) can be seen as a generalization of the standard Online Convex Optimization (OCO) framework. At each round, a cost function and constraint function are revealed after a learner chooses an action. The goal is to minimize both the regret and cumulative constraint violation (CCV) against an adaptive adversary. We show for the first time that is possible to obtain the optimal $O(\sqrt{T})$ bound on both regret and CCV, improving the best known bounds of $O \left( \sqrt{T} \right)$ and $\tilde{O} \left( \sqrt{T} \right)$ for the regret and CCV, respectively. Based on a new surrogate loss function enforcing a minimum penalty on the constraint function, we demonstrate that both the Follow-the-Regularized-Leader and the Online Gradient Descent achieve the optimal bounds.
Abstract（参考訳）: 制約付きオンライン凸最適化(COCO)は、標準オンライン凸最適化(OCO)フレームワークの一般化と見なすことができる。各ラウンドでは、学習者がアクションを選択した後、コスト関数と制約関数が明らかにされる。目的は、適応的敵に対する後悔と累積的制約違反(CCV)を最小化することである。我々は、後悔とCCVの両方で最適な$O(\sqrt{T})$を得ることができ、最もよく知られた$O \left( \sqrt{T} \right)$と$\tilde{O} \left( \sqrt{T} \right)$のバウンドを改善した。制約関数に最小限のペナルティを課す新しい代理損失関数に基づいて、Follow-the-Regularized-Leader と Online Gradient Descent の両方が最適境界を達成することを示す。

関連論文リスト

$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)
Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文参考訳（メタデータ） (2024-02-14T07:52:00Z)
Optimal Algorithms for Online Convex Optimization with Adversarial Constraints [16.99491218081617]
COCOでは、そのラウンドのアクションを選択した後、学習者に凸コスト関数と凸制約関数を明らかにする。我々は、オンラインポリシーが、制限的な仮定なしで、同時に$O(sqrtT)$ regretと$tildeO(sqrtT)$ CCVを達成できることを示します。
論文参考訳（メタデータ） (2023-10-29T09:55:41Z)
Projection-Free Online Convex Optimization with Stochastic Constraints [0.0]
我々は制約付きオンライン凸最適化のためのプロジェクションフリーアルゴリズムを開発した。各種設定に対してサブ線形後悔と制約違反境界を推定する。我々は、制約違反を減らして、後悔と同じ成長をすることができることを証明している。
論文参考訳（メタデータ） (2023-05-02T11:27:34Z)
Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文参考訳（メタデータ） (2023-02-11T07:19:51Z)
A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文参考訳（メタデータ） (2022-09-15T16:59:19Z)
Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
論文参考訳（メタデータ） (2022-05-02T08:48:22Z)
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)
Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints [24.97580261894342]
本稿では,長期的制約を伴うオンライン凸最適化について考察する。新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
論文参考訳（メタデータ） (2021-06-09T15:18:06Z)
Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
論文参考訳（メタデータ） (2021-03-21T11:43:35Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。