Fugu-MT 論文翻訳(概要): Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints

論文の概要: Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints

arxiv url: http://arxiv.org/abs/2505.06709v1
Date: Sat, 10 May 2025 17:23:10 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-13 20:21:49.004271
Title: Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints
Title（参考訳）: 逆制約付きオンライン凸最適化のための制約違反($\tilde{O}(\sqrt{T})$
Authors: Abhishek Sinha, Rahul Vaze,
Abstract要約: 逆制約を伴うオンライン凸最適化問題を再検討する。我々は,$tildeO(sqrtdT+Tbeta)$ regretと$tildeO(dT1-beta)$ CCVを実現するオンラインポリシーを提案する。
参考スコア（独自算出の注目度）: 16.99491218081617
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: We revisit the Online Convex Optimization problem with adversarial constraints (COCO) where, in each round, a learner is presented with a convex cost function and a convex constraint function, both of which may be chosen adversarially. The learner selects actions from a convex decision set in an online fashion, with the goal of minimizing both regret and the cumulative constraint violation (CCV) over a horizon of $T$ rounds. The best-known policy for this problem achieves $O(\sqrt{T})$ regret and $\tilde{O}(\sqrt{T})$ CCV. In this paper, we present a surprising improvement that achieves a significantly smaller CCV by trading it off with regret. Specifically, for any bounded convex cost and constraint functions, we propose an online policy that achieves $\tilde{O}(\sqrt{dT}+ T^\beta)$ regret and $\tilde{O}(dT^{1-\beta})$ CCV, where $d$ is the dimension of the decision set and $\beta \in [0,1]$ is a tunable parameter. We achieve this result by first considering the special case of $\textsf{Constrained Expert}$ problem where the decision set is a probability simplex and the cost and constraint functions are linear. Leveraging a new adaptive small-loss regret bound, we propose an efficient policy for the $\textsf{Constrained Expert}$ problem, that attains $O(\sqrt{T\ln N}+T^{\beta})$ regret and $\tilde{O}(T^{1-\beta} \ln N)$ CCV, where $N$ is the number of experts. The original problem is then reduced to the $\textsf{Constrained Expert}$ problem via a covering argument. Finally, with an additional smoothness assumption, we propose an efficient gradient-based policy attaining $O(T^{\max(\frac{1}{2},\beta)})$ regret and $\tilde{O}(T^{1-\beta})$ CCV.
Abstract（参考訳）: 逆制約付きオンライン凸最適化問題(COCO)を再検討し、各ラウンドで学習者に凸コスト関数と凸制約関数を提示する。学習者は、T$ラウンドの地平線上で、後悔と累積制約違反(CCV)を最小化することを目的として、オンライン形式で設定された凸決定から行動を選択する。この問題の最もよく知られているポリシーは、$O(\sqrt{T})$ regret と $\tilde{O}(\sqrt{T})$ CCV である。本報告では, 後悔と引き換えにCCVを著しく小さくする, 驚くべき改善について述べる。具体的には、任意の有界凸コストと制約関数に対して、$\tilde{O}(\sqrt{dT}+ T^\beta)$ regret と $\tilde{O}(dT^{1-\beta})$ CCV を達成するオンラインポリシーを提案し、$d$ は決定集合の次元であり、$\beta \in [0,1]$ はチューナブルパラメータである。まず、決定集合が確率的単純集合であり、コストと制約関数が線型であるような特別な場合を$\textsf{Constrained Expert}$問題として考える。新しい適応的小さめの遺言境界を活用すれば、$\textsf{Constrained Expert}$問題に対して、$O(\sqrt{T\ln N}+T^{\beta})$ regret と $\tilde{O}(T^{1-\beta} \ln N)$ CCVに達し、$N$は専門家の数である。元の問題は、カバー引数によって$\textsf{Constrained Expert}$問題に還元される。最後に、さらなる滑らかさを仮定して、$O(T^{\max(\frac{1}{2},\beta)})$ regret および $\tilde{O}(T^{1-\beta})$ CCV となるような効率的な勾配に基づくポリシーを提案する。

論文の概要: Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints

関連論文リスト