論文の概要: Breaking the $O(\sqrt{T})$ Cumulative Constraint Violation Barrier while Achieving $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization

• arxiv url: http://arxiv.org/abs/2603.20671v1
• Date: Sat, 21 Mar 2026 06:19:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-24 19:11:39.031552
• Title: Breaking the $O(\sqrt{T})$ Cumulative Constraint Violation Barrier while Achieving $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization
• Title（参考訳）: O(\sqrt{T})$ Cumulative Constraint Violation Barrier と $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization
• Authors: Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze,
• Abstract要約: 目的は、静的な後悔と累積的な制約違反を同時に最小化することである。 CCVは、後悔が$O(sqrtT)$であることを保証する全てのアルゴリズムに対して$(sqrtT)$であり、最悪のケース入力は$dge 2$である、と広く信じられている。
• 参考スコア（独自算出の注目度）: 4.167459103689586
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action $x_t \in \mathcal{X} \subset \mathbb{R}^d$, a convex loss function $f_t$ and a convex constraint function $g_t$ that drives the constraint $g_t(x)\le 0$ are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions $f_t$ and $g_t$ for all $t$ ahead of time, and chooses a static optimal action that is feasible with respect to all $g_t(x)\le 0$. In recent prior work Sinha and Vaze [2024], algorithms with simultaneous regret of $O(\sqrt{T})$ and CCV of $O(\sqrt{T})$ or (CCV of $O(1)$ in specific cases Vaze and Sinha [2025], e.g. when $d=1$) have been proposed. It is widely believed that CCV is $Ω(\sqrt{T})$ for all algorithms that ensure that regret is $O(\sqrt{T})$ with the worst case input for any $d\ge 2$. In this paper, we refute this and show that the algorithm of Vaze and Sinha [2025] simultaneously achieves regret of $O(\sqrt{T})$ regret and CCV of $O(T^{1/3})$ when $d=2$.
• Abstract（参考訳）: 制約付きオンライン凸最適化の問題は、各ラウンドで学習者がアクション $x_t \in \mathcal{X} \subset \mathbb{R}^d$、凸損失関数 $f_t$、凸制約関数 $g_t$、制約を駆動する$g_t(x)\le 0$ にコミットすると、考慮される。 目的は、損失関数と制約関数を事前に知っているベンチマークに対して、静的な後悔と累積的制約違反(CCV)を同時に最小化し、すべての$t$に対して$f_t$と$g_t$を選択し、すべての$g_t(x)\le 0$に対して可能な静的な最適アクションを選択することである。 最近の先行研究では、Sinha と Vaze [2024] は $O(\sqrt{T})$ と CCV of $O(\sqrt{T})$ または (特定の場合では $O(1)$ の CCV、例えば $d=1$ の eg を持つアルゴリズムが提案されている。 CCV は $Ω(\sqrt{T})$ であり、後悔が $O(\sqrt{T})$ であることを保証する全てのアルゴリズムに対して$d\ge 2$ に対して最悪のケース入力を持つと広く信じられている。 本稿では,Vaze と Sinha [2025] のアルゴリズムが$O(\sqrt{T})$の後悔と$O(T^{1/3})$のCCVを同時に達成していることを示す。

関連論文リスト

• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  我々は、最近提案された$ell$-smoothness条件$|nabla2f(x)|| le ellleft(||nabla f(x)||right),$$$L$-smoothnessと$(L_0,L_1)$-smoothnessを一般化する関数を持つ凸最適化問題の一階法について検討する。
  論文  参考訳（メタデータ） (2025-08-09T08:28:06Z)
• Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints [16.99491218081617]
  逆制約を伴うオンライン凸最適化問題を再検討する。 我々は,$tildeO(sqrtdT+Tbeta)$ regretと$tildeO(dT1-beta)$ CCVを実現するオンラインポリシーを提案する。
  論文  参考訳（メタデータ） (2025-05-10T17:23:10Z)
• $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)
• 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)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。