論文の概要: 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 を享受する。
さらに、より計算効率の良いアルゴリズムのバージョンを提供し、ベンチマークアルゴリズムと比較した数値実験を行う。
関連論文リスト
- Revisiting Projection-Free Online Learning with Time-Varying Constraints [35.573654458435854]
我々は制約付きオンライン凸最適化について検討し、そこでは決定は固定的で典型的には複雑な領域に属する必要がある。
いくつかのプロジェクションフリーな手法が$mathcalO(T3/4 sqrtlog T)$ regret boundと$mathcalO(T3/4 sqrtlog T)$ cumulative constraint violation (CCV) bound for general convex lossで提案されている。
本稿では,損失関数が強凸である場合に,この結果を改善し,さらにテクスチノーベルの後悔とCCV境界を確立する。
論文 参考訳（メタデータ） (2025-01-27T13:38:51Z) - 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) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Online Convex Optimization with Stochastic Constraints: Zero Constraint
Violation and Bandit Feedback [0.0]
本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。
我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
論文 参考訳（メタデータ） (2023-01-26T18:04:26Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Safe Online Bid Optimization with Return-On-Investment and Budget
Constraints subject to Uncertainty [87.81197574939355]
最適化問題と学習問題の両方について検討する。
我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。
より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
論文 参考訳（メタデータ） (2022-01-18T17:24:20Z) - Lazy Lagrangians with Predictions for Online Learning [24.18464455081512]
オンライン凸最適化における時間的差分制約による一般的な問題について考察する。
Follow-The-Regularized-Leaderイテレーションと予測適応動的ステップを組み合わせることで、新しい原始双対アルゴリズムを設計する。
我々の研究は、この制約されたOCO設定のためのFTRLフレームワークを拡張し、各最先端のグレディベースのソリューションより優れています。
論文 参考訳（メタデータ） (2022-01-08T21:49:10Z) - 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) - 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) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。