論文の概要: Simultaneously Achieving Sublinear Regret and Constraint Violations for
Online Convex Optimization with Time-varying Constraints
- arxiv url: http://arxiv.org/abs/2111.07707v1
- Date: Mon, 15 Nov 2021 12:23:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-16 23:59:57.593163
- Title: Simultaneously Achieving Sublinear Regret and Constraint Violations for
Online Convex Optimization with Time-varying Constraints
- Title（参考訳）: 時変制約付きオンライン凸最適化のための部分線形後悔と制約違反の同時達成
- Authors: Qingsong Liu, Wenfei Wu, Longbo Huang, Zhixuan Fang
- Abstract要約: 我々は,オンライン凸最適化(OCO)問題に対して,長期的制約と時間的制約を伴う新しい仮想キューベースのオンラインアルゴリズムを開発した。
本アルゴリズムは,サブ線形動的後悔と制約違反を同時に実現した最初のパラメータフリーアルゴリズムである。
- 参考スコア（独自算出の注目度）: 26.473560927031176
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: In this paper, we develop a novel virtual-queue-based online algorithm for
online convex optimization (OCO) problems with long-term and time-varying
constraints and conduct a performance analysis with respect to the dynamic
regret and constraint violations. We design a new update rule of dual variables
and a new way of incorporating time-varying constraint functions into the dual
variables. To the best of our knowledge, our algorithm is the first
parameter-free algorithm to simultaneously achieve sublinear dynamic regret and
constraint violations. Our proposed algorithm also outperforms the
state-of-the-art results in many aspects, e.g., our algorithm does not require
the Slater condition. Meanwhile, for a group of practical and widely-studied
constrained OCO problems in which the variation of consecutive constraints is
smooth enough across time, our algorithm achieves $O(1)$ constraint violations.
Furthermore, we extend our algorithm and analysis to the case when the time
horizon $T$ is unknown. Finally, numerical experiments are conducted to
validate the theoretical guarantees of our algorithm, and some applications of
our proposed framework will be outlined.
- Abstract（参考訳）: 本稿では,オンライン凸最適化(oco)問題に対する長期的および時間的制約のある仮想キュー型オンラインアルゴリズムを開発し,動的後悔と制約違反に関して性能解析を行う。
我々は、双対変数の新しい更新規則と、時間変化制約関数を双対変数に組み込む新しい方法を設計する。
我々の知る限り、我々のアルゴリズムはサブ線形動的後悔と制約違反を同時に達成する最初のパラメータフリーアルゴリズムである。
また,提案アルゴリズムは,Slater条件を必要としないなど,多くの面で最先端のアルゴリズムよりも優れている。
一方,逐次制約の変動が時間にわたって十分に滑らかである実用的で広く研究されている制約付きoco問題に対して,本アルゴリズムは$o(1)$制約違反を実現する。
さらに、時間的地平線$T$が未知の場合までアルゴリズムと解析を拡張します。
最後に,提案手法の理論的保証を検証するために数値実験を行い,提案手法の応用について概説する。
関連論文リスト
- A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
伝統的な数学的プログラミングの解法は制約付き最小化問題を解くのに長い計算時間を必要とする。
ペナルティに基づくガードレールアルゴリズム(PGA)を提案する。
論文 参考訳（メタデータ） (2024-05-03T10:37:34Z) - Online Non-convex Optimization with Long-term Non-convex Constraints [2.033434950296318]
Follow-the-Perturbed-Leader型アルゴリズムを提案する。
提案アルゴリズムは,長期(極値)制約のある河川汚染源同定問題に対処するために適用された。
論文 参考訳（メタデータ） (2023-11-04T15:08:36Z) - Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms
for Optimization under Orthogonality Constraints [8.59102802625914]
本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。
まず、この方法はスティーフェル多様体に拡張される。
また、コスト関数が多くの関数の平均である場合、分散と還元のアルゴリズムも検討する。
論文 参考訳（メタデータ） (2023-03-29T07:36:54Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。