論文の概要: Dynamic Regret Analysis of Safe Distributed Online Optimization for
Convex and Non-convex Problems
- arxiv url: http://arxiv.org/abs/2302.12320v1
- Date: Thu, 23 Feb 2023 20:34:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 15:17:36.128967
- Title: Dynamic Regret Analysis of Safe Distributed Online Optimization for
Convex and Non-convex Problems
- Title(参考訳): 凸・非凸問題に対する安全な分散オンライン最適化の動的回帰解析
- Authors: Ting-Jui Chang, Sapana Chaudhary, Dileep Kalathil, Shahin Shahrampour
- Abstract要約: 本稿では,未知の線形安全性制約に対する安全な分散オンライン最適化について述べる。
全てのエージェントは、推定可能なセットを構築するためにパラメータを協調的に推定し、最適化フェーズにおけるアクション選択の安全性を確保する。
- 参考スコア(独自算出の注目度): 14.1081872409308
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper addresses safe distributed online optimization over an unknown set
of linear safety constraints. A network of agents aims at jointly minimizing a
global, time-varying function, which is only partially observable to each
individual agent. Therefore, agents must engage in local communications to
generate a safe sequence of actions competitive with the best minimizer
sequence in hindsight, and the gap between the two sequences is quantified via
dynamic regret. We propose distributed safe online gradient descent
(D-Safe-OGD) with an exploration phase, where all agents estimate the
constraint parameters collaboratively to build estimated feasible sets,
ensuring the action selection safety during the optimization phase. We prove
that for convex functions, D-Safe-OGD achieves a dynamic regret bound of
$O(T^{2/3} \sqrt{\log T} + T^{1/3}C_T^*)$, where $C_T^*$ denotes the
path-length of the best minimizer sequence. We further prove a dynamic regret
bound of $O(T^{2/3} \sqrt{\log T} + T^{2/3}C_T^*)$ for certain non-convex
problems, which establishes the first dynamic regret bound for a safe
distributed algorithm in the non-convex setting.
- Abstract(参考訳): 本稿では,線形安全制約の未知集合に対する安全な分散オンライン最適化について述べる。
エージェントのネットワークは、各エージェントに部分的に観察可能なグローバルな時間変化関数を、共同で最小化することを目的としている。
したがって、エージェントは、後見において最善の最小化系列と競合する安全な一連のアクションを生成するために、局所的な通信に従事しなければならず、これらの2つのシーケンス間のギャップは動的後悔によって定量化される。
提案する分散安全なオンライン勾配勾配降下法(D-Safe-OGD)は,各エージェントが協調的に制約パラメータを推定し,推定可能な集合を構築し,最適化フェーズにおける行動選択の安全性を確保する。
凸関数に対して、D-Safe-OGD は $O(T^{2/3} \sqrt{\log T} + T^{1/3}C_T^*)$ の動的後悔境界を達成する。
さらに、ある非凸問題に対して$O(T^{2/3} \sqrt{\log T} + T^{2/3}C_T^*)$の動的後悔境界が証明される。
関連論文リスト
- Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence
and Variance Reduction [26.9632099249085]
AdaSPSとAdaSLSと呼ばれる2種類の新しいSPSとSLSを提案し、非補間条件における収束を保証する。
我々は, AdaSPS と AdaSLS に新しい分散低減技術を導入し, $smashwidetildemathcalO(n+1/epsilon)$グラデーション評価を必要とするアルゴリズムを得る。
論文 参考訳(メタデータ) (2023-08-11T10:17:29Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳(メタデータ) (2023-07-17T09:55:35Z) - Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。
我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
論文 参考訳(メタデータ) (2023-07-05T13:52:10Z) - Safe Linear Bandits over Unknown Polytopes [39.177982674455784]
安全線形バンディット問題(英: safe linear bandit problem、SLB)は、線形プログラミングのオンライン手法である。
ポリトープ上でのSLBの有効性とスムーズな安全性のトレードオフについて検討した。
論文 参考訳(メタデータ) (2022-09-27T21:13:32Z) - Log Barriers for Safe Black-box Optimization with Application to Safe
Reinforcement Learning [72.97229770329214]
本稿では,学習時の安全性維持が不可欠である高次元非線形最適化問題に対する一般的なアプローチを提案する。
LBSGDと呼ばれるアプローチは、慎重に選択されたステップサイズで対数障壁近似を適用することに基づいている。
安全強化学習における政策課題の違反を最小限に抑えるためのアプローチの有効性を実証する。
論文 参考訳(メタデータ) (2022-07-21T11:14:47Z) - Decentralized Safe Multi-agent Stochastic Optimal Control using Deep
FBSDEs and ADMM [16.312625634442092]
本稿では,障害発生時のマルチエージェント制御のための,安全でスケーラブルな分散ソリューションを提案する。
分散化は、各エージェントの最適化変数、コピー変数、隣人への拡張によって達成される。
安全なコンセンサスソリューションを実現するために,ADMMベースのアプローチを取り入れた。
論文 参考訳(メタデータ) (2022-02-22T03:57:23Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳(メタデータ) (2021-12-29T02:42:59Z) - Safe Online Convex Optimization with Unknown Linear Safety Constraints [0.0]
安全なオンライン凸最適化の問題について検討し、各ステップの動作は一連の線形安全制約を満たす必要がある。
線形安全性制約を指定するパラメータはアルゴリズムでは未知である。
安全なベースライン動作が可能であるという仮定の下で、SO-PGDアルゴリズムは、後悔する$O(T2/3)$を達成していることを示す。
論文 参考訳(メタデータ) (2021-11-14T19:49:19Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。