論文の概要: Distributed Online Convex Optimization with Adversarial Constraints:
Reduced Cumulative Constraint Violation Bounds under Slater's Condition
- arxiv url: http://arxiv.org/abs/2306.00149v1
- Date: Wed, 31 May 2023 19:39:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 19:38:20.931434
- Title: Distributed Online Convex Optimization with Adversarial Constraints:
Reduced Cumulative Constraint Violation Bounds under Slater's Condition
- Title（参考訳）: 逆制約付き分散オンライン凸最適化:スレーター条件下での累積拘束振動境界の低減
- Authors: Xinlei Yi, Xiuxian Li, Tao Yang, Lihua Xie, Yiguang Hong, Tianyou
Chai, and Karl H. Johansson
- Abstract要約: 本稿では,逆制約を伴う分散オンライン凸最適化について考察する。
エージェントはネットワークの後悔と累積的制約違反を最小限にするために協力する。
我々の知る限り、この論文は、(分散)オンライン凸最適化における(ネットワーク)累積制約違反境界を敵制約付きで達成した最初のものである。
- 参考スコア（独自算出の注目度）: 29.809415829907525
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers distributed online convex optimization with adversarial
constraints. In this setting, a network of agents makes decisions at each
round, and then only a portion of the loss function and a coordinate block of
the constraint function are privately revealed to each agent. The loss and
constraint functions are convex and can vary arbitrarily across rounds. The
agents collaborate to minimize network regret and cumulative constraint
violation. A novel distributed online algorithm is proposed and it achieves an
$\mathcal{O}(T^{\max\{c,1-c\}})$ network regret bound and an
$\mathcal{O}(T^{1-c/2})$ network cumulative constraint violation bound, where
$T$ is the number of rounds and $c\in(0,1)$ is a user-defined trade-off
parameter. When Slater's condition holds (i.e, there is a point that strictly
satisfies the inequality constraints), the network cumulative constraint
violation bound is reduced to $\mathcal{O}(T^{1-c})$. Moreover, if the loss
functions are strongly convex, then the network regret bound is reduced to
$\mathcal{O}(\log(T))$, and the network cumulative constraint violation bound
is reduced to $\mathcal{O}(\sqrt{\log(T)T})$ and $\mathcal{O}(\log(T))$ without
and with Slater's condition, respectively. To the best of our knowledge, this
paper is the first to achieve reduced (network) cumulative constraint violation
bounds for (distributed) online convex optimization with adversarial
constraints under Slater's condition. Finally, the theoretical results are
verified through numerical simulations.
- Abstract（参考訳）: 本稿では,対向制約を伴う分散オンライン凸最適化について考察する。
この設定では、エージェントのネットワークが各ラウンドで決定を行い、その後、損失関数の一部と制約関数の座標ブロックのみを各エージェントにプライベートに開示する。
損失関数と制約関数は凸関数であり、ラウンドごとに任意に変化する。
エージェントはネットワークの後悔と累積的制約違反を最小限に抑えるために協力する。
新しい分散オンラインアルゴリズムが提案されており、$\mathcal{o}(t^{\max\{c,1-c\}})$ network regret bound と$\mathcal{o}(t^{1-c/2})$ network cumulative constraints violation bound を達成している。
スレーターの条件が成り立つとき(すなわち、不等式制約を厳密に満たす点が存在する)、ネットワーク累積制約違反境界は$\mathcal{O}(T^{1-c})$に還元される。
さらに、損失関数が強凸であれば、ネットワークの後悔境界は $\mathcal{o}(\log(t))$ に縮小され、ネットワーク累積制約違反境界は $\mathcal{o}(\sqrt{\log(t)t})$ と $\mathcal{o}(\log(t))$ にそれぞれスレーター条件なしで還元される。
最善の知識として,本論文は,スレイター条件下での逆制約を伴う(分散)オンライン凸最適化のための(ネットワーク)累積的制約違反境界を初めて達成した。
最後に, 数値シミュレーションにより理論結果を検証した。
関連論文リスト
- Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - 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) - Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed
Bandit with Constraints [4.879346089164413]
ブラックボックスの報酬関数 $f(x)$ を、連続空間上のブラックボックス制約関数 $g(x)leq 0$ に最適化する。
本稿では,楽観的かつ悲観的なGPバンディット学習を取り入れたペナルティベース手法であるRectified Pessimistic-Optimistic Learning framework (RPOL)を提案する。
論文 参考訳（メタデータ） (2022-11-27T04:28:16Z) - The Sample Complexity of Online Contract Design [120.9833763323407]
オンライン環境での隠れアクションの主エージェント問題について検討する。
各ラウンドにおいて、主席は、各結果に基づいてエージェントへの支払いを指定する契約を投稿する。
エージェントは、自身のユーティリティを最大化する戦略的な行動選択を行うが、プリンシパルによって直接観察できない。
論文 参考訳（メタデータ） (2022-11-10T17:59:42Z) - Private Isotonic Regression [54.32252900997422]
部分順序集合 (poset) $mathcalX$ と任意のリプシッツ損失関数に対する等調回帰の問題を考察する。
約$mathrmwidth(mathcalX) cdot log|mathcalX| / n$, ここで$mathrmwidth(mathcalX)$はポーズの幅である。
上記の境界は本質的に最良であることを示す。
論文 参考訳（メタデータ） (2022-10-27T05:08:07Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - 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) - Regret and Cumulative Constraint Violation Analysis for Distributed
Online Constrained Convex Optimization [24.97580261894342]
本稿では,エージェントネットワーク上の時間的制約を伴う分散オンライン凸最適化問題について考察する。
フルインフォメーションとバンディットフィードバックの2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-01T18:28:53Z) - Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。
一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。
本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
論文 参考訳（メタデータ） (2020-06-22T17:38:14Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。