論文の概要: An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints

• arxiv url: http://arxiv.org/abs/2412.08060v2
• Date: Wed, 12 Mar 2025 21:09:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-14 19:21:00.466450
• Title: An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints
• Title（参考訳）: 逆制約を考慮したオンライン凸最適化のための最適化アルゴリズム
• Authors: Jordan Lekeufack, Michael I. Jordan,
• Abstract要約: 逆制約を伴うオンライン凸最適化(OCO)について検討する。 本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。 以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
• 参考スコア（独自算出の注目度）: 55.2480439325792
• License:
• Abstract: We study Online Convex Optimization (OCO) with adversarial constraints, where an online algorithm must make sequential decisions to minimize both convex loss functions and cumulative constraint violations. We focus on a setting where the algorithm has access to predictions of the loss and constraint functions. Our results show that we can improve the current best bounds of $ O(\sqrt{T}) $ regret and $ \tilde{O}(\sqrt{T}) $ cumulative constraint violations to $ O(\sqrt{E_T(f)}) $ and $ \tilde{O}(\sqrt{E_T(g^+)}) $, respectively, where $ E_T(f) $ and $E_T(g^+)$ represent the cumulative prediction errors of the loss and constraint functions. In the worst case, where $E_T(f) = O(T) $ and $ E_T(g^+) = O(T) $ (assuming bounded gradients of the loss and constraint functions), our rates match the prior $ O(\sqrt{T}) $ results. However, when the loss and constraint predictions are accurate, our approach yields significantly smaller regret and cumulative constraint violations. Finally, we apply this to the setting of adversarial contextual bandits with sequential risk constraints, obtaining optimistic bounds $O (\sqrt{E_T(f)} T^{1/3})$ regret and $O(\sqrt{E_T(g^+)} T^{1/3})$ constraints violation, yielding better performance than existing results when prediction quality is sufficiently high.
• Abstract（参考訳）: 我々は,オンライン凸最適化(OCO)を逆制約付きで検討し,オンラインアルゴリズムは凸損失関数と累積制約違反の両方を最小限に抑えるために逐次決定をしなければならない。 本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。 O(\sqrt{T}) $ regret と $ \tilde{O}(\sqrt{T}) $ cumulative constraint violations to $ O(\sqrt{E_T(f)}) $ and $ \tilde{O}(\sqrt{E_T(g^+)}) $, $ E_T(f) $ と $E_T(g^+)$ は、損失と制約関数の累積予測誤差を表す。 最悪の場合、$E_T(f) = O(T) $ と $E_T(g^+) = O(T) $ (損失と制約関数の有界勾配を仮定すれば) は、以前の$O(\sqrt{T}) $の結果と一致する。 しかし、損失予測と制約予測が正確であれば、我々のアプローチは、後悔と累積的制約違反を著しく小さくする。 最後に、これを逐次的リスク制約付き対向的コンテキスト帯域の設定に適用し、楽観的境界である$O (\sqrt{E_T(f)} T^{1/3})$ regret and $O (\sqrt{E_T(g^+)} T^{1/3})$ constraints violation を得る。

関連論文リスト

• $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)
• Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints [31.526232903811533]
  我々はOCO(Optimistically Safe OCO)と呼ぶアルゴリズムを導入し、そのアルゴリズムが$tildeO(sqrtT)$ regretと制約違反がないことを示す。 静的線形制約の場合、これは同じ仮定の下で、以前の最もよく知られた $tildeO(T2/3)$ regret よりも改善される。 時間的制約の場合、当社の作業は、$O(sqrtT)$ regretと$O(sqrtT)$ cumulative violationを示す既存の結果を補完します。
  論文  参考訳（メタデータ） (2024-03-09T04:01:39Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Projection-Free Online Convex Optimization with Time-Varying Constraints [19.993839085310643]
  逆時間制約によるオンライン凸最適化の設定について検討する。 固定可能な集合を投影することが難しいシナリオによって動機付けられ、線形最適化オラクル(LOO)を通してのみこの集合にアクセスするプロジェクションフリーアルゴリズムを考える。 我々は、長さ$T$のシーケンスで、全体$T$をLOOに呼び出し、$tildeO(T3/4)$ regret w.r.t.の損失と$O(T7/8)$制約違反を保証します。
  論文  参考訳（メタデータ） (2024-02-13T21:13:29Z)
• Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition [29.809415829907525]
  本稿では,逆制約を伴う分散オンライン凸最適化について考察する。 エージェントはネットワークの後悔と累積的制約違反を最小限にするために協力する。 我々の知る限り、この論文は、(分散)オンライン凸最適化における(ネットワーク)累積制約違反境界を敵制約付きで達成した最初のものである。
  論文  参考訳（メタデータ） (2023-05-31T19:39:15Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• 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)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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