Fugu-MT 論文翻訳(概要): $\tilde{O}(\sqrt{T})$ Regret and Polylogarithmic Constraint Violation for COCO

論文の概要: $\tilde{O}(\sqrt{T})$ Regret and Polylogarithmic Constraint Violation for COCO

arxiv url: http://arxiv.org/abs/2610.03983v1
Date: Fri, 02 Oct 2026 19:47:09 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-12 21:10:02.975228
Title: $\tilde{O}(\sqrt{T})$ Regret and Polylogarithmic Constraint Violation for COCO
Title（参考訳）: $\tilde{O}(\sqrt{T})$ Regret and Polylogarithmic Constraint Violation for COCO
Abstract要約: 対向凸損失と制約を伴う制約付きオンライン凸最適化について検討した。オンライン政策が(O(sqrtTlog T))後悔と(O(log2T))$mathsfCCV$を達成できることを示す。
参考スコア（独自算出の注目度）: 7.798233121583888
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: We study constrained online convex optimization with adversarial convex losses and constraints ($\mathsf{COCO}$). At each round $t\in[T]$, a learner selects $x_t$ from a $d$-dimensional convex decision set $\mathcal X$, after which an adaptive adversary reveals a convex cost function $f_t$ and constraint function $g_t$. Consequently, the learner incurs cost $f_t(x_t)$ and constraint violation $\max\{0,g_t(x_t)\}$, and aims to simultaneously minimize regret and cumulative constraint violation ($\mathsf{CCV}$) over the entire horizon. Existing algorithms achieve $O(\sqrt{T})$ regret and $\widetilde O(\sqrt{T})$ $\mathsf{CCV}$. We show that an online policy can achieve $O(\sqrt{T\log T})$ regret and $O(\log^2 T)$ $\mathsf{CCV}$, reducing the $\mathsf{CCV}$ from polynomial to polylogarithmic while retaining near-optimal regret. Our approach combines continuous Hedge with elimination on shrinking feasible sets. The key observation is that whenever the mean of the Hedge distribution violates a constraint, Grünbaum's inequality guarantees that a constant fraction of the Hedge probability mass is eliminated. We use an adaptive learning-rate schedule and a potential function coupling the surviving volume with the learning rate to convert this probability-mass reduction into a bound of $O(\log^2 T)$ on the $\mathsf{CCV}$.
Abstract（参考訳）: 対向凸損失と制約を伴う制約付きオンライン凸最適化について検討した(\mathsf{COCO}$)。各ラウンド $t\in[T]\ において、学習者は、(d$ 次元凸決定集合 $\mathcal X$ から $x_t$ を選択し、その後、適応的敵が凸コスト関数 $f_t$ および制約関数 $g_t$ を明らかにする。その結果、学習者はコスト $f_t(x_t)$ と制約違反 $\max\{0,g_t(x_t)\}$ を発生させ、全地平線上での後悔と累積的制約違反(\mathsf{CCV}$)を同時に最小化する。既存のアルゴリズムは、(O(\sqrt{T})\)後悔と(\widetilde O(\sqrt{T})\)$\mathsf{CCV}$を達成する。オンライン政策は, ほぼ最適の後悔を保ちつつ, 多項式から多元対数への$\mathsf{CCV}$を減らし, $O(\sqrt{T\log T})$後悔, $O(\log^2 T)$ $\mathsf{CCV}$を達成することができることを示す。我々のアプローチは、連続ヘッジと、可約集合の縮小の除去を組み合わせている。鍵となる観察は、Hedge分布の平均が制約に反するたびに、Grünbaumの不等式は、Hedge確率質量の定数分数を排除することを保証しているということである。適応的な学習率スケジュールと、残量と学習率を結合したポテンシャル関数を用いて、この確率質量減少を$\mathsf{CCV}$上の(O(\log^2T)\)境界に変換する。

関連論文リスト

Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文参考訳（メタデータ） (2026-09-07T01:38:41Z)
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)
Truly Adapting to Adversarial Constraints in Constrained MABs [33.41566575424402]
本研究では,Emphmulti-armed bandit (MAB) 問題の制約付き変種について検討した。本稿では,$widetildemathcalO(sqrtT+C)$ regretと$widetildemathcalO(sqrtT+C)$ positive violationを実現するアルゴリズムを提案する。次に、損失に対して盗聴フィードバックのみが利用可能である場合に、これらの保証を拡張する方法を示す。
論文参考訳（メタデータ） (2026-02-16T08:07:11Z)
Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization [64.88607416000376]
普遍性と適応性の両方を達成する新しいアプローチであるUniGradを紹介し、UniGrad.CorrectとUniGrad.Bregmanの2つの異なる実現法を提案する。どちらのメソッドも勾配の変動に適応し、強い凸関数に対する $mathcalO(log V_T)$ regret とexp-concave関数に対する $mathcalO(d log V_T)$ regret を同時に達成する。
論文参考訳（メタデータ） (2025-11-25T05:23:10Z)
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)
On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文参考訳（メタデータ） (2021-12-03T21:42: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)

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

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