論文の概要: Regret and Cumulative Constraint Violation Analysis for Distributed
Online Constrained Convex Optimization
- arxiv url: http://arxiv.org/abs/2105.00321v1
- Date: Sat, 1 May 2021 18:28:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-04 13:44:01.261663
- Title: Regret and Cumulative Constraint Violation Analysis for Distributed
Online Constrained Convex Optimization
- Title（参考訳）: 分散オンライン制約付き凸最適化における後悔と累積制約違反解析
- Authors: Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl H.
Johansson
- Abstract要約: 本稿では,エージェントネットワーク上の時間的制約を伴う分散オンライン凸最適化問題について考察する。
フルインフォメーションとバンディットフィードバックの2つのアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 24.97580261894342
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the distributed online convex optimization problem with
time-varying constraints over a network of agents. This is a sequential
decision making problem with two sequences of arbitrarily varying convex loss
and constraint functions. At each round, each agent selects a decision from the
decision set, and then only a portion of the loss function and a coordinate
block of the constraint function at this round are privately revealed to this
agent. The goal of the network is to minimize network regret and constraint
violation. Two distributed online algorithms with full-information and bandit
feedback are proposed. Both dynamic and static network regret bounds are
analyzed for the proposed algorithms, and network cumulative constraint
violation is used to measure constraint violation, which excludes the situation
that strictly feasible constraints can compensate the effects of violated
constraints. In particular, we show that the proposed algorithms achieve
$\mathcal{O}(T^{\max\{\kappa,1-\kappa\}})$ static network regret and
$\mathcal{O}(T^{1-\kappa/2})$ network cumulative constraint violation, where
$T$ is the total number of rounds and $\kappa\in(0,1)$ is a user-defined
trade-off parameter. Moreover, if the loss functions are strongly convex, then
the static network regret bound can be reduced to $\mathcal{O}(T^{\kappa})$.
Finally, numerical simulations are provided to illustrate the effectiveness of
the theoretical results.
- Abstract（参考訳）: 本稿では,エージェントネットワーク上の時間的制約を伴う分散オンライン凸最適化問題を考察する。
これは、任意に変化する凸損失と制約関数の2つの列による逐次決定問題である。
各ラウンドにおいて、各エージェントは決定セットから決定を選択し、その後、損失関数の一部と、このラウンドにおける制約関数の座標ブロックのみを、このエージェントにプライベートに開示する。
ネットワークの目的は、ネットワークの後悔と制約違反を最小限に抑えることである。
完全情報とバンディットフィードバックを備えた2つの分散オンラインアルゴリズムを提案する。
ネットワーク累積制約違反は制約違反を計測するために使用され、厳密な制約が違反した制約の影響を補償できる状況を排除する。
特に、提案アルゴリズムは、静的ネットワーク後悔とネットワーク累積制約違反を$\mathcal{O}(T^{\max\{\kappa,1-\kappa\}})$で達成し、$T$はラウンドの総数であり、$\kappa\in(0,1)$はユーザ定義のトレードオフパラメータであることを示す。
さらに、損失関数が強く凸であれば、静的ネットワークの後悔境界は$\mathcal{O}(T^{\kappa})$に縮めることができる。
最後に, 理論結果の有効性を説明するため, 数値シミュレーションを行った。
関連論文リスト
- Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - 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) - Projection-Free Online Convex Optimization with Stochastic Constraints [0.0]
我々は制約付きオンライン凸最適化のためのプロジェクションフリーアルゴリズムを開発した。
各種設定に対してサブ線形後悔と制約違反境界を推定する。
我々は、制約違反を減らして、後悔と同じ成長をすることができることを証明している。
論文 参考訳（メタデータ） (2023-05-02T11:27:34Z) - On Dynamic Regret and Constraint Violations in Constrained Online Convex
Optimization [17.412117389855222]
提案するアルゴリズムは,現在の動作の周囲に適度に選択された集合上の射影勾配勾配を追従する。
動的後悔と制約違反の両方が、連続する最適動作間の距離の和であるパス長によって順序的に束縛されていることを示す。
論文 参考訳（メタデータ） (2023-01-24T04:22:13Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - 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) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。