論文の概要: Regret and Cumulative Constraint Violation Analysis for Online Convex
Optimization with Long Term Constraints
- arxiv url: http://arxiv.org/abs/2106.05135v1
- Date: Wed, 9 Jun 2021 15:18:06 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-10 14:54:25.823242
- Title: Regret and Cumulative Constraint Violation Analysis for Online Convex
Optimization with Long Term Constraints
- Title（参考訳）: 長期制約付きオンライン凸最適化における後悔と累積制約違反解析
- Authors: Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl H.
Johansson
- Abstract要約: 本稿では,長期的制約を伴うオンライン凸最適化について考察する。
新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
- 参考スコア（独自算出の注目度）: 24.97580261894342
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers online convex optimization with long term constraints,
where constraints can be violated in intermediate rounds, but need to be
satisfied in the long run. The cumulative constraint violation is used as the
metric to measure constraint violations, which excludes the situation that
strictly feasible constraints can compensate the effects of violated
constraints. A novel algorithm is first proposed and it achieves an
$\mathcal{O}(T^{\max\{c,1-c\}})$ bound for static regret and an
$\mathcal{O}(T^{(1-c)/2})$ bound for cumulative constraint violation, where
$c\in(0,1)$ is a user-defined trade-off parameter, and thus has improved
performance compared with existing results. Both static regret and cumulative
constraint violation bounds are reduced to $\mathcal{O}(\log(T))$ when the loss
functions are strongly convex, which also improves existing results. %In order
to bound the regret with respect to any comparator sequence, In order to
achieve the optimal regret with respect to any comparator sequence, another
algorithm is then proposed and it achieves the optimal
$\mathcal{O}(\sqrt{T(1+P_T)})$ regret and an $\mathcal{O}(\sqrt{T})$ cumulative
constraint violation, where $P_T$ is the path-length of the comparator
sequence. Finally, numerical simulations are provided to illustrate the
effectiveness of the theoretical results.
- Abstract（参考訳）: 本稿では,長期的制約を伴うオンライン凸最適化について考察する。
累積制約違反は、厳格な制約が違反した制約の効果を補償できる状況を排除する制約違反を計測するための指標として用いられる。
新たなアルゴリズムが最初に提案され、静的後悔に対する$\mathcal{O}(T^{\max\{c,1-c\}})$boundと累積制約違反に対する$\mathcal{O}(T^{(1-c)/2})$boundを実現している。
静的な後悔と累積的な制約違反境界は、損失関数が強い凸であるときに$\mathcal{O}(\log(T))$に還元され、既存の結果も改善される。
% コンパレータ列に対する後悔を拘束するために、任意のコンパレータ列に対する最適な後悔を達成するために、別のアルゴリズムが提案され、最適な$\mathcal{O}(\sqrt{T(1+P_T)})$ regret と $\mathcal{O}(\sqrt{T})$ cumulative constraint violation, ここで$P_T$はコンパレータ列のパス長である。
最後に, 理論結果の有効性を説明するため, 数値シミュレーションを行った。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。
R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2024-06-03T17:54:58Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Multi-point Feedback of Bandit Convex Optimization with Hard Constraints [1.8130068086063336]
本研究では,学習者が損失関数の部分的情報に基づいて決定列を生成することを目的とした制約付き帯域凸最適化について検討する。
我々は、累積的テクスト制約違反を制約違反の指標として採用する。
我々のアルゴリズムは、凸損失関数と時間変化制約に対して、$O(d2Tmaxc,1-c)$ regret bounds と $O(d2T1-fracc2)$ cumulative hard constraint violation bounds を得る。
論文 参考訳（メタデータ） (2023-10-17T02:43:22Z) - Distributed Online Convex Optimization with Adversarial Constraints:
Reduced Cumulative Constraint Violation Bounds under Slater's Condition [29.809415829907525]
本稿では,逆制約を伴う分散オンライン凸最適化について考察する。
エージェントはネットワークの後悔と累積的制約違反を最小限にするために協力する。
我々の知る限り、この論文は、(分散)オンライン凸最適化における(ネットワーク)累積制約違反境界を敵制約付きで達成した最初のものである。
論文 参考訳（メタデータ） (2023-05-31T19:39:15Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Regret and Cumulative Constraint Violation Analysis for Distributed
Online Constrained Convex Optimization [24.97580261894342]
本稿では,エージェントネットワーク上の時間的制約を伴う分散オンライン凸最適化問題について考察する。
フルインフォメーションとバンディットフィードバックの2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-01T18:28:53Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z) - Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。
一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。
本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
論文 参考訳（メタデータ） (2020-06-22T17:38:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。