論文の概要: An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning
- arxiv url: http://arxiv.org/abs/2202.03836v1
- Date: Tue, 8 Feb 2022 12:58:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-09 16:12:55.393377
- Title: An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning
- Title(参考訳): 分散機械学習のための勾配追跡法の改良
- Authors: Anastasia Koloskova, Tao Lin, Sebastian U. Stich
- Abstract要約: トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
- 参考スコア(独自算出の注目度): 34.144764431505486
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider decentralized machine learning over a network where the training
data is distributed across $n$ agents, each of which can compute stochastic
model updates on their local data. The agent's common goal is to find a model
that minimizes the average of all local loss functions. While gradient tracking
(GT) algorithms can overcome a key challenge, namely accounting for differences
between workers' local data distributions, the known convergence rates for GT
algorithms are not optimal with respect to their dependence on the mixing
parameter $p$ (related to the spectral gap of the connectivity matrix).
We provide a tighter analysis of the GT method in the stochastic strongly
convex, convex and non-convex settings. We improve the dependency on $p$ from
$\mathcal{O}(p^{-2})$ to $\mathcal{O}(p^{-1}c^{-1})$ in the noiseless case and
from $\mathcal{O}(p^{-3/2})$ to $\mathcal{O}(p^{-1/2}c^{-1})$ in the general
stochastic case, where $c \geq p$ is related to the negative eigenvalues of the
connectivity matrix (and is a constant in most practical applications). This
improvement was possible due to a new proof technique which could be of
independent interest.
- Abstract(参考訳): トレーニングデータを$n$のエージェントに分散するネットワーク上での分散機械学習について検討し、各エージェントがローカルデータの確率的モデル更新を計算する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
勾配追跡(GT)アルゴリズムは、労働者の局所データ分布の違いを考慮し、重要な課題を克服することができるが、GTアルゴリズムの既知の収束率は、混合パラメータ$p$(接続行列のスペクトルギャップに関連する)への依存に関して最適ではない。
本稿では, 確率論的凸, 凸, 非凸設定におけるGT法をより厳密に解析する。
我々は、$p$から$\mathcal{O}(p^{-2})$から$\mathcal{O}(p^{-1}c^{-1})$への依存を改善し、$\mathcal{O}(p^{-3/2})$から$\mathcal{O}(p^{-1/2}c^{-1})$への依存を改善する。
この改善は、独立した興味を持つことができる新しい証明技術によって可能になった。
関連論文リスト
- Adam-like Algorithm with Smooth Clipping Attains Global Minima: Analysis
Based on Ergodicity of Functional SDEs [0.0]
我々は,グローバル化された非-1損失関数を切断したAdam型アルゴリズムが正規化された非-1エラー形式を最小化することを示す。
また、スムーズな群のエルゴード理論を適用して、逆温度と時間を学ぶためのアプローチを研究する。
論文 参考訳(メタデータ) (2023-11-29T14:38:59Z) - The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。
さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
論文 参考訳(メタデータ) (2023-11-09T14:29:25Z) - Compressed and distributed least-squares regression: convergence rates
with applications to Federated Learning [9.31522898261934]
機械学習の勾配アルゴリズムに対する圧縮の影響について検討する。
いくつかの非バイアス圧縮演算子間の収束率の差を強調した。
我々はその結果を連合学習の事例にまで拡張する。
論文 参考訳(メタデータ) (2023-08-02T18:02:00Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳(メタデータ) (2022-04-14T19:10:53Z) - High-Dimensional Inference over Networks: Linear Convergence and
Statistical Guarantees [20.701475313495884]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳(メタデータ) (2022-01-21T01:26:08Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。