論文の概要: Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback
- arxiv url: http://arxiv.org/abs/2412.03983v1
- Date: Thu, 05 Dec 2024 08:58:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-06 14:39:21.060982
- Title: Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback
- Title（参考訳）: 線形予算制約と部分フィードバックを用いた安全かつ効率的なオンライン凸最適化
- Authors: Shanqi Liu, Xin Liu,
- Abstract要約: 本稿では,未知の線形予算制約を伴うオンライン凸最適化について検討する。
本稿では,安全かつ効率的なLyapunov-Optimizationアルゴリズム(SELO)を提案する。
- 参考スコア（独自算出の注目度）: 3.5554907645160605
- License:
- Abstract: This paper studies online convex optimization with unknown linear budget constraints, where only the gradient information of the objective and the bandit feedback of constraint functions are observed. We propose a safe and efficient Lyapunov-optimization algorithm (SELO) that can achieve an $O(\sqrt{T})$ regret and zero cumulative constraint violation. The result also implies SELO achieves $O(\sqrt{T})$ regret when the budget is hard and not allowed to be violated. The proposed algorithm is computationally efficient as it resembles a primal-dual algorithm where the primal problem is an unconstrained, strongly convex and smooth problem, and the dual problem has a simple gradient-type update. The algorithm and theory are further justified in a simulated application of energy-efficient task processing in distributed data centers.
- Abstract（参考訳）: 本稿では,制約関数の勾配情報と帯域幅フィードバックのみを観測する,未知の線形予算制約を伴うオンライン凸最適化について検討する。
我々は, 安全かつ効率的なリアプノフ最適化アルゴリズム(SELO)を提案し, 後悔と累積制約違反をゼロとする$O(\sqrt{T})を実現できる。
この結果はまた、SELOが予算が堅く、違反を許さない場合に、$O(\sqrt{T})$後悔することを意味する。
提案アルゴリズムは, 主問題に制約がなく, 凸が強く, 滑らかな問題であり, 双対問題に単純な勾配型更新がある原始双対アルゴリズムに類似しているため, 計算効率がよい。
このアルゴリズムと理論は、分散データセンターにおけるエネルギー効率の高いタスク処理のシミュレーション適用においてさらに正当化される。
関連論文リスト
- Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。
本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。
本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
論文 参考訳（メタデータ） (2024-10-03T07:44:40Z) - A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
伝統的な数学的プログラミングの解法は制約付き最小化問題を解くのに長い計算時間を必要とする。
ペナルティに基づくガードレールアルゴリズム(PGA)を提案する。
論文 参考訳（メタデータ） (2024-05-03T10:37:34Z) - Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。
提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。
決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
論文 参考訳（メタデータ） (2023-11-18T23:06:33Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - 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) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳（メタデータ） (2021-09-23T17:38:24Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Efficient Projection-Free Algorithms for Saddle Point Problems [39.88460595129901]
複雑な制約を伴う凸凸凸凹点問題に対するプロジェクションフリーアルゴリズムについて検討する。
条件勾配スライディングとMirror-Proxを組み合わせることで、バッチ設定で$tildeO (1/sqrtepsilon)$評価と$tildeO (1/epsilon2)$線形最適化しか必要としないことを示す。
論文 参考訳（メタデータ） (2020-10-21T15:05:53Z) - Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。
このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。
本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
論文 参考訳（メタデータ） (2020-08-13T08:56:24Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。