論文の概要: Online Convex Optimization with Stochastic Constraints: Zero Constraint
Violation and Bandit Feedback
- arxiv url: http://arxiv.org/abs/2301.11267v1
- Date: Thu, 26 Jan 2023 18:04:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-27 12:56:23.547300
- Title: Online Convex Optimization with Stochastic Constraints: Zero Constraint
Violation and Bandit Feedback
- Title（参考訳）: 確率的制約によるオンライン凸最適化:ゼロ制約違反とバンディットフィードバック
- Authors: Yeongjong Kim, Dabeen Lee
- Abstract要約: 本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。
我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies online convex optimization with stochastic constraints. We
propose a variant of the drift-plus-penalty algorithm that guarantees
$O(\sqrt{T})$ expected regret and zero constraint violation, after a fixed
number of iterations, which improves the vanilla drift-plus-penalty method with
$O(\sqrt{T})$ constraint violation. Our algorithm is oblivious to the length of
the time horizon $T$, in contrast to the vanilla drift-plus-penalty method.
This is based on our novel drift lemma that provides time-varying bounds on the
virtual queue drift and, as a result, leads to time-varying bounds on the
expected virtual queue length. Moreover, we extend our framework to
stochastic-constrained online convex optimization under two-point bandit
feedback. We show that by adapting our algorithmic framework to the bandit
feedback setting, we may still achieve $O(\sqrt{T})$ expected regret and zero
constraint violation, improving upon the previous work for the case of
identical constraint functions. Numerical results demonstrate our theoretical
results.
- Abstract（参考訳）: 本稿では,オンライン凸最適化と確率的制約について検討する。
本研究では,一定の回数の反復を繰り返すと,o(\sqrt{t})$制約違反を保証し,o(\sqrt{t})$制約違反でバニラドリフトプラスペナルティ法を改善するドリフトプラスペナルティアルゴリズムの変種を提案する。
我々のアルゴリズムは、バニラドリフトプラスペナルティ法とは対照的に、時間軸$t$の長さに従わない。
これは、仮想キュードリフトの時間変化バウンダリを提供し、その結果、期待される仮想キュー長の時間変化バウンダリをもたらす、我々の新しいドリフトレンマに基づいている。
さらに,このフレームワークを2点の帯域フィードバックの下で,確率制約付きオンライン凸最適化に拡張する。
アルゴリズムフレームワークを帯域フィードバック設定に適応させることで、同じ制約関数の場合の以前の作業を改善して、期待された後悔とゼロ制約違反を達成できることが示される。
数値結果は理論的な結果を示している。
関連論文リスト
- 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 Stochastic Constraints [0.0]
我々は制約付きオンライン凸最適化のためのプロジェクションフリーアルゴリズムを開発した。
各種設定に対してサブ線形後悔と制約違反境界を推定する。
我々は、制約違反を減らして、後悔と同じ成長をすることができることを証明している。
論文 参考訳（メタデータ） (2023-05-02T11:27:34Z) - Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。
本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
論文 参考訳（メタデータ） (2023-02-11T07:19:51Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed
Bandit with Constraints [4.879346089164413]
ブラックボックスの報酬関数 $f(x)$ を、連続空間上のブラックボックス制約関数 $g(x)leq 0$ に最適化する。
本稿では,楽観的かつ悲観的なGPバンディット学習を取り入れたペナルティベース手法であるRectified Pessimistic-Optimistic Learning framework (RPOL)を提案する。
論文 参考訳（メタデータ） (2022-11-27T04:28:16Z) - 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 Strongly Convex Optimization with Unknown Delays [30.931538196386672]
オンライン凸最適化の問題点を未知の遅延で検討する。
まず、OGDの遅延変形を強凸関数に拡張する。
我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
論文 参考訳（メタデータ） (2021-03-21T10:16:15Z) - Efficient Optimistic Exploration in Linear-Quadratic Regulators via
Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。
有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。
我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文 参考訳（メタデータ） (2020-07-13T16:30:47Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。