論文の概要: Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)
- arxiv url: http://arxiv.org/abs/2607.10808v1
- Date: Sun, 12 Jul 2026 15:36:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-14 15:40:48.546493
- Title: Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)
- Title（参考訳）: 制約付きオンライン凸最適化(COCO)のためのOGD+投影アルゴリズムにおける累積拘束振動の低次境界
- Abstract要約: 目的は、静的な後悔と累積的な制約違反を同時に最小化することである。
本稿では,OGD+プロジェクションアルゴリズムのCCVが$(Tfracd-12d)$であることを示す。
- 参考スコア（独自算出の注目度）: 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$. Currently, the best known algorithm is OGD+Projection algorithm of [Vaze and Sinha, 2025] that has simultaneous regret of $O(\sqrt{T})$ and CCV of $O(T^{1/3})$ for $d=2$ [Balasundaram et al., 2026], and simultaneous regret of $O(\sqrt{T})$ and CCV of $O(\sqrt{T})$ for any $d$ [Sarkar and Sinha, 2026]. In this paper, we show that the CCV of the OGD+Projection algorithm is $Ω(T^{\frac{d-1}{2d}})$. This is the first such lower bound result.
- 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$に対して可能な静的な最適アクションを選択することである。
現在最もよく知られているアルゴリズムは、[Vaze and Sinha, 2025]のOGD+射影アルゴリズムで、$O(\sqrt{T})$と$O(T^{1/3})$を同時に、$d=2$[Balasundaram et al , 2026]に対して$O(\sqrt{T})$とCCVを同時に、$O(\sqrt{T})$を任意の$d$[Sarkar and Sinha, 2026]に対して$O(\sqrt{T})$とCCVを繰り返す。
本稿では,OGD+射影アルゴリズムのCCVが$Ω(T^{\frac{d-1}{2d}})$であることを示す。
これが最初の下界の結果である。
関連論文リスト
- Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions [5.533296779866529]
損失関数を$f_t'$sに拡張して、時間とともに変更できるようにします。
サブリニアなオンラインアルゴリズムはいつでも、運動コストが$left(log Tright)$であることを示す。
論文 参考訳（メタデータ） (2026-09-10T08:13:27Z) - Sharp Optimal Algorithm for Derivative-Free Stochastic Convex Optimization in One Dimension [80.40589035328607]
我々は、ガウス雑音の零次オラクルを用いて凸関数 $f : [0,1] から [0,1] への最小化の問題を研究する。
計算効率のよいO(1/sqrtT)$収束率を求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-07-14T16:10:33Z) - Improved Guarantees for Constrained Online Convex Optimization via Self-Contraction [7.798233121583888]
我々は、逆選択された制約を伴う制約付きオンライン制約(COCO)について検討する。
強い凸損失に対して、我々のアルゴリズムは、$O(sqrtT)$後悔を維持しながら$mathsfCCV$を$O(sqrtT)$に改善する。
論文 参考訳（メタデータ） (2026-05-20T12:40:27Z) - Breaking the $O(\sqrt{T})$ Cumulative Constraint Violation Barrier while Achieving $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization [4.167459103689586]
目的は、静的な後悔と累積的な制約違反を同時に最小化することである。
CCVは、後悔が$O(sqrtT)$であることを保証する全てのアルゴリズムに対して$(sqrtT)$であり、最悪のケース入力は$dge 2$である、と広く信じられている。
論文 参考訳（メタデータ） (2026-03-21T06:19:35Z) - 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) - Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。
我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。
我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。