論文の概要: Improved Guarantees for Constrained Online Convex Optimization via Self-Contraction

• arxiv url: http://arxiv.org/abs/2605.21107v1
• Date: Wed, 20 May 2026 12:40:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-21 19:19:56.670777
• Title: Improved Guarantees for Constrained Online Convex Optimization via Self-Contraction
• Title（参考訳）: 自己抽出による制約付きオンライン凸最適化のための保証の改善
• Authors: Dhruv Sarkar, Abhishek Sinha,
• Abstract要約: 我々は、逆選択された制約を伴う制約付きオンライン制約(COCO)について検討する。 強い凸損失に対して、我々のアルゴリズムは、$O(sqrtT)$後悔を維持しながら$mathsfCCV$を$O(sqrtT)$に改善する。
• 参考スコア（独自算出の注目度）: 7.798233121583888
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider Constrained Online Convex Optimization (COCO) with adversarially chosen constraints. At each round, the learner chooses an action before observing the loss and constraint function for that round. The goal is to achieve small static regret against the best point satisfying all constraints while also controlling cumulative constraint violation ($\mathsf{CCV}$). For strongly convex losses, state-of-the-art algorithms achieve $O(\log T)$ regret and $O(\sqrt{T \log T})$ $\mathsf{CCV}.$ The corresponding best-known bounds for convex losses is $O(\sqrt{T})$ regret and $O(\sqrt{T} \log T)$ $\mathsf{CCV}$. In this paper, we give a simple projection-based algorithm that simultaneously achieves $O(\log T)$ regret and $O(\log T)$ $\mathsf{CCV}$ for strongly-convex losses, yielding an exponential improvement in the $\mathsf{CCV}$. For the convex losses, our algorithm improves the $\mathsf{CCV}$ to $O(\sqrt{T})$ while maintaining the optimal $O(\sqrt{T})$ regret. The key to our improvement is a recent geometric result for self-contracted curves, which may be of independent interest.
• Abstract（参考訳）: 我々は、逆選択された制約を伴う制約付きオンライン凸最適化(COCO)を検討する。 各ラウンドで、学習者は、そのラウンドの損失と制約関数を観察する前に、アクションを選択する。 目標は、すべての制約を満たす最良の点に対して小さな静的後悔を達成すると同時に、累積的制約違反($\mathsf{CCV}$)を制御することである。 強い凸損失に対して、最先端のアルゴリズムは、$O(\log T)$ regret と $O(\sqrt{T \log T})$ $\mathsf{CCV} を達成する。 凸損失に対する最もよく知られた境界は、$O(\sqrt{T})$ regret と $O(\sqrt{T} \log T)$ $\mathsf{CCV}$である。 本稿では,強い凸損失に対して,$O(\log T)$ regret と $O(\log T)$ $\mathsf{CCV}$ を同時に達成し,$\mathsf{CCV}$ を指数関数的に改善する単純なプロジェクションベースアルゴリズムを提案する。 凸損失に対して、我々のアルゴリズムは、最適な$O(\sqrt{T})$を保ちながら、$\mathsf{CCV}$を$O(\sqrt{T})$に改善する。 我々の改善の鍵は、自己収縮曲線に対する最近の幾何学的結果であり、これは独立な興味を持つかもしれない。

関連論文リスト

• 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)
• 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)
• 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)
• 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)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。 強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
  論文  参考訳（メタデータ） (2021-03-21T11:43:35Z)
• 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)

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

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