論文の概要: Finite-Time Convergence Rates of Decentralized Stochastic Approximation
with Applications in Multi-Agent and Multi-Task Learning
- arxiv url: http://arxiv.org/abs/2010.15088v2
- Date: Thu, 16 Jun 2022 14:24:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-02 06:24:20.428791
- Title: Finite-Time Convergence Rates of Decentralized Stochastic Approximation
with Applications in Multi-Agent and Multi-Task Learning
- Title(参考訳): 分散確率近似の有限時間収束率とマルチエージェント・マルチタスク学習への応用
- Authors: Sihan Zeng, Thinh T. Doan, Justin Romberg
- Abstract要約: 本研究では, 雑音測定により, 演算子の根元を求めるためのデータ駆動手法について検討する。
エージェントのネットワークは、それぞれ独自の演算子とデータ観測を持ち、分散化された通信グラフ上で集約演算子の固定点を協調的に見つける。
我々の主な貢献は、各エージェントで観測されたデータがマルコフ過程からサンプリングされるとき、この分散近似法を有限時間で解析することである。
- 参考スコア(独自算出の注目度): 16.09467599829253
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a decentralized variant of stochastic approximation, a data-driven
approach for finding the root of an operator under noisy measurements. A
network of agents, each with its own operator and data observations,
cooperatively find the fixed point of the aggregate operator over a
decentralized communication graph. Our main contribution is to provide a
finite-time analysis of this decentralized stochastic approximation method when
the data observed at each agent are sampled from a Markov process; this lack of
independence makes the iterates biased and (potentially) unbounded. Under
fairly standard assumptions, we show that the convergence rate of the proposed
method is essentially the same as if the samples were independent, differing
only by a log factor that accounts for the mixing time of the Markov processes.
The key idea in our analysis is to introduce a novel Razumikhin-Lyapunov
function, motivated by the one used in analyzing the stability of delayed
ordinary differential equations. We also discuss applications of the proposed
method on a number of interesting learning problems in multi-agent systems.
- Abstract(参考訳): 本研究では, 確率近似の分散変種について検討し, 雑音下での操作者の根を求めるデータ駆動手法について検討した。
エージェントのネットワークは、それぞれ独自の演算子とデータ観測を持ち、分散化された通信グラフ上で集約演算子の固定点を協調的に見つける。
我々の主な貢献は、各エージェントで観測されたデータがマルコフ過程からサンプリングされた場合、この分散確率近似法の有限時間解析を提供することである。
比較的標準的な仮定の下では、提案手法の収束速度は、サンプルが独立である場合と基本的に同じであり、マルコフ過程の混合時間を考慮したログ係数によってのみ異なることを示す。
この分析の鍵となる考え方は、遅れた常微分方程式の安定性を解析するために用いられる新しいラズミヒン・リャプノフ関数を導入することである。
また,複数エージェントシステムにおける興味深い学習問題に対する提案手法の適用について述べる。
関連論文リスト
- Scalable Decentralized Algorithms for Online Personalized Mean
Estimation [13.489730726871423]
本研究は,各エージェントが実数値分布からサンプルを収集し,その平均値を推定する,オーバーアーキシング問題の簡易版に焦点を当てた。
1つは信念の伝播からインスピレーションを得ており、もう1つはコンセンサスに基づくアプローチを採用している。
論文 参考訳(メタデータ) (2024-02-20T08:30:46Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳(メタデータ) (2024-01-29T02:08:40Z) - A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。
提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文 参考訳(メタデータ) (2021-10-07T17:51:10Z) - Decentralized Local Stochastic Extra-Gradient for Variational
Inequalities [125.62877849447729]
我々は、不均一(非IID)で多くのデバイスに分散する問題データを持つ領域上での分散変分不等式(VIs)を考察する。
我々は、完全に分散化された計算の設定を網羅する計算ネットワークについて、非常に一般的な仮定を行う。
理論的には, モノトン, モノトンおよび非モノトンセッティングにおける収束速度を理論的に解析する。
論文 参考訳(メタデータ) (2021-06-15T17:45:51Z) - Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic
Approximation under Markovian Noise [2.0305676256390934]
2つの連結非線形作用素の根を探すためのシミュレーションベースアプローチである,いわゆる2時間スケール近似について検討する。
特に、マルコフプロセスによってメソッド内のデータが生成されるシナリオを考える。
演算子とマルコフ過程に関するかなり標準的な仮定の下で、この方法によって生成される平均二乗誤差の収束率を 0 に特徴づける公式を提供する。
論文 参考訳(メタデータ) (2021-04-04T15:19:19Z) - Contrastive learning of strong-mixing continuous-time stochastic
processes [53.82893653745542]
コントラスト学習(Contrastive Learning)は、ラベルのないデータから構築された分類タスクを解決するためにモデルを訓練する自己指導型の手法のファミリーである。
拡散の場合,小~中距離間隔の遷移カーネルを適切に構築したコントラスト学習タスクを用いて推定できることが示される。
論文 参考訳(メタデータ) (2021-03-03T23:06:47Z) - A Decentralized Approach to Bayesian Learning [26.74338464389837]
機械学習に対する分散型アプローチを動機として,分散ランゲヴィン力学の形式を取り入れた協調学習を提案する。
解析の結果,マルコフ連鎖の初期KL偏差は指数関数的に減少していることがわかった。
ローカルに利用可能なデータを持つ個々のエージェントの性能は、中央集権的な設定と同等であり、レートは大幅に改善されている。
論文 参考訳(メタデータ) (2020-07-14T03:59:17Z) - Learning while Respecting Privacy and Robustness to Distributional
Uncertainties and Adversarial Data [66.78671826743884]
分散ロバストな最適化フレームワークはパラメトリックモデルのトレーニングのために検討されている。
目的は、逆操作された入力データに対して頑健なトレーニングモデルを提供することである。
提案されたアルゴリズムは、オーバーヘッドがほとんどない堅牢性を提供する。
論文 参考訳(メタデータ) (2020-07-07T18:25:25Z) - Local Stochastic Approximation: A Unified View of Federated Learning and
Distributed Multi-Task Reinforcement Learning Algorithms [1.52292571922932]
エージェントのネットワーク上での局所近似について検討し、エージェントのローカル演算子からなる演算子のルートを見つけることを目的とする。
我々は,各エージェントのデータをマルコフプロセスから生成し,従って依存する場合に,この手法の有限時間性能を特徴付けることに重点を置いている。
論文 参考訳(メタデータ) (2020-06-24T04:05:11Z) - Batch Stationary Distribution Estimation [98.18201132095066]
サンプル遷移の組を与えられたエルゴードマルコフ鎖の定常分布を近似する問題を考える。
与えられたデータに対する補正比関数の復元に基づく一貫した推定器を提案する。
論文 参考訳(メタデータ) (2020-03-02T09:10:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。