論文の概要: Optimistic Safety for Linearly-Constrained Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2403.05786v1
- Date: Sat, 9 Mar 2024 04:01:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-13 12:19:57.233579
- Title: Optimistic Safety for Linearly-Constrained Online Convex Optimization
- Title(参考訳): 線形制約付きオンライン凸最適化の最適安全性
- Authors: Spencer Hutchinson, Tianyi Chen, Mahnoosh Alizadeh
- Abstract要約: 我々は、プレイヤーがノイズの多いフィードバックを受け、常に満たさなければならない静的線形制約の問題を考える。
楽観的安全性の新たな設計パラダイムを活用することで,この問題に対して, $tildemathcalO(sqrtT)$ regret というアルゴリズムを提案する。
我々は,アルゴリズムがこのような設定で同じ後悔の保証を享受しており,期待する制約に反することはないことを示す。
- 参考スコア(独自算出の注目度): 35.43232638653937
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The setting of online convex optimization (OCO) under unknown constraints has
garnered significant attention in recent years. In this work, we consider a
version of this problem with static linear constraints that the player receives
noisy feedback of and must always satisfy. By leveraging our novel design
paradigm of optimistic safety, we give an algorithm for this problem that
enjoys $\tilde{\mathcal{O}}(\sqrt{T})$ regret. This improves on the previous
best regret bound of $\tilde{\mathcal{O}}(T^{2/3})$ while using only slightly
stronger assumptions of independent noise and an oblivious adversary. Then, by
recasting this problem as OCO under time-varying stochastic linear constraints,
we show that our algorithm enjoys the same regret guarantees in such a setting
and never violates the constraints in expectation. This contributes to the
literature on OCO under time-varying stochastic constraints, where the
state-of-the-art algorithms enjoy $\tilde{\mathcal{O}}(\sqrt{T})$ regret and
$\tilde{\mathcal{O}}(\sqrt{T})$ violation when the constraints are convex and
the player receives full feedback. Additionally, we provide a version of our
algorithm that is more computationally efficient and give numerical experiments
comparing it with benchmark algorithms.
- Abstract(参考訳): 未知の制約下でのオンライン凸最適化(OCO)の設定は近年大きな注目を集めている。
本研究では,プレイヤーが無音のフィードバックを受け取り,常に満たさなければならない静的線形制約を伴うこの問題を考察する。
楽観的安全性の新たな設計パラダイムを活用することで,この問題に対して, $\tilde{\mathcal{O}}(\sqrt{T})$ regret を満足するアルゴリズムを提供する。
これにより$\tilde{\mathcal{O}}(T^{2/3})$の過去の最良後悔境界は改善されるが、独立雑音のわずかに強い仮定と不愉快な逆数のみを使用する。
そして,時間的確率線形制約の下でこの問題をOCOとして再キャストすることにより,我々のアルゴリズムはそのような設定で同じ後悔の保証を享受し,期待する制約に反することはないことを示す。
これはocoの時間的制約の下での文献に寄与し、最先端のアルゴリズムは$\tilde{\mathcal{o}}(\sqrt{t})$ regret と $\tilde{\mathcal{o}}(\sqrt{t})$ violation を享受する。
さらに、より計算効率の良いアルゴリズムのバージョンを提供し、ベンチマークアルゴリズムと比較した数値実験を行う。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Second Order Methods for Bandit Optimization and Control [37.70434692823672]
我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。
また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
論文 参考訳(メタデータ) (2024-02-14T04:03:38Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Online Convex Optimization with Stochastic Constraints: Zero Constraint
Violation and Bandit Feedback [0.0]
本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。
我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
論文 参考訳(メタデータ) (2023-01-26T18:04:26Z) - New Projection-free Algorithms for Online Convex Optimization with
Adaptive Regret Guarantees [21.30065439295409]
オンライン凸最適化(OCO)のための効率的なテキストプロジェクションフリーアルゴリズムを提案する。
提案アルゴリズムは,テキストインファシブルプロジェクション(textitinfeasible projections)と呼ばれる新しい,効率的なアプローチによるテクスタイトライン勾配降下アルゴリズムに基づいている。
我々は、全体として$O(T)$コールを使用して分離オラクルを呼び出し、$O(sqrtT)$アダプティブな後悔と$O(T3/4)$アダプティブな期待された後悔を保証します。
論文 参考訳(メタデータ) (2022-02-09T20:56: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) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。