論文の概要: Constrained Online Convex Optimization without Slater's Condition

• arxiv url: http://arxiv.org/abs/2606.31480v1
• Date: Tue, 30 Jun 2026 10:54:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-01 18:27:19.185938
• Title: Constrained Online Convex Optimization without Slater's Condition
• Title（参考訳）: スレーター条件のない制約付きオンライン凸最適化
• Abstract要約: 制約に対しては、ほぼ最適な後悔と制約違反境界を達成する既存のアルゴリズムは、スレーターの条件のような規則性仮定に依存するのが一般的である。 このギャップを、アダプティブ・レギュレータをデュアルアップデートに組み込んだ、任意のプリミティブ・デュアルフレームワークで埋めます。 我々のアルゴリズムは、$O(sqrtT)$期待後悔と$O(sqrtTlog T)$期待累積制約違反を達成する。
• 参考スコア（独自算出の注目度）: 0.7646713951724009
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater's condition. For stochastic constraints and convex losses, our algorithm achieves $O(\sqrt{T})$ expected regret and $O(\sqrt{T}\log T)$ expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to $O(\log T)$ with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.
• Abstract（参考訳）: 我々は,対向的損失と確率的あるいは対向的制約を伴う制約付きオンライン凸最適化について検討した。 確率的制約に対しては、ほぼ最適の後悔と制約違反境界を達成する既存のアルゴリズムは、典型的にはスレーターの条件のような規則性仮定に依存するが、逆制約アルゴリズムは、かなり制限的な円周可能なコンパレータを使用することでこれらの仮定を避ける。 このギャップを、アダプティブ・レギュレータをデュアルアップデートに組み込んだ、任意のプリミティブ・デュアルフレームワークで埋めます。 正規化器はスレーターの条件によって引き起こされる負のドリフトに頼ることなく双対過程を安定化する。 確率的制約と凸損失に対して、我々のアルゴリズムは、$O(\sqrt{T})$期待後悔と$O(\sqrt{T}\log T)$期待累積制約違反を達成する。 さらに,本アルゴリズムは,後悔と制約違反に関して,同じ順序の高確率境界も認めていることを示す。 強い凸損失の場合、後悔境界は同じ順序の違反境界を持つ$O(\log T)$に改善される。 わずかな修正で、このフレームワークは敵の制約にも適用され、厳しい制約違反の保証を提供する。

関連論文リスト

• Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints [33.41566575424402]
  本研究では, エンフォリンエピソード制約マルコフ決定過程(CMDP)について, 双方の制約下で検討した。 ストラディらによって導入された最先端のベスト・オブ・ボディーズ・アルゴリズムを大幅に改善する新しいアルゴリズムを提案する。 Slater の条件を使わずにサブリニア制約違反を保証し,インフン制約された最適値に対してサブリニア$alpha$-regret を保証する。
  論文  参考訳（メタデータ） (2025-09-24T13:38: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)
• Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
  差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。 誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
  論文  参考訳（メタデータ） (2024-01-17T09:23:25Z)
• Multi-point Feedback of Bandit Convex Optimization with Hard Constraints [1.8130068086063336]
  本研究では,学習者が損失関数の部分的情報に基づいて決定列を生成することを目的とした制約付き帯域凸最適化について検討する。 我々は、累積的テクスト制約違反を制約違反の指標として採用する。 我々のアルゴリズムは、凸損失関数と時間変化制約に対して、$O(d2Tmaxc,1-c)$ regret bounds と $O(d2T1-fracc2)$ cumulative hard constraint violation bounds を得る。
  論文  参考訳（メタデータ） (2023-10-17T02:43:22Z)
• On Regularization and Inference with Label Constraints [62.60903248392479]
  機械学習パイプラインにおけるラベル制約を符号化するための2つの戦略、制約付き正規化、制約付き推論を比較した。 正規化については、制約に不整合なモデルを前置することで一般化ギャップを狭めることを示す。 制約付き推論では、モデルの違反を訂正することで人口リスクを低減し、それによってその違反を有利にすることを示す。
  論文  参考訳（メタデータ） (2023-07-08T03:39:22Z)
• Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback [0.0]
  本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。 我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
  論文  参考訳（メタデータ） (2023-01-26T18:04:26Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• 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)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)

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

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