論文の概要: 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})$への依存を改善する。
この改善は、独立した興味を持つことができる新しい証明技術によって可能になった。
関連論文リスト
- Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
条件分布は機械学習の中心的な問題です
ペアデータとペアデータの両方を統合する新しい学習パラダイムを提案する。
我々のアプローチはまた、興味深いことに逆エントロピー最適輸送(OT)と結びついている。
論文 参考訳（メタデータ） (2024-10-03T16:12:59Z) - MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。
一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文 参考訳（メタデータ） (2024-05-29T18:36:59Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Rate Analysis of Coupled Distributed Stochastic Approximation for Misspecified Optimization [0.552480439325792]
パラメトリックな特徴を持つ不完全な情報を持つ分散最適化問題として$n$のエージェントを考える。
本稿では,各エージェントが未知パラメータの現在の信念を更新する分散近似アルゴリズムを提案する。
アルゴリズムの性能に影響を与える因子を定量的に解析し、決定変数の平均二乗誤差が$mathcalO(frac1nk)+mathcalOleft(frac1sqrtn (1-rho_w)right)frac1k1.5で有界であることを証明する。
論文 参考訳（メタデータ） (2024-04-21T14:18:49Z) - Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - Compressed and distributed least-squares regression: convergence rates
with applications to Federated Learning [9.31522898261934]
機械学習の勾配アルゴリズムに対する圧縮の影響について検討する。
いくつかの非バイアス圧縮演算子間の収束率の差を強調した。
我々はその結果を連合学習の事例にまで拡張する。
論文 参考訳（メタデータ） (2023-08-02T18:02:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。