Fugu-MT 論文翻訳(概要): A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate

論文の概要: A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate

arxiv url: http://arxiv.org/abs/2003.12423v1
Date: Fri, 27 Mar 2020 14:02:15 GMT
ステータス: 処理完了
システム内更新日: 2022-12-19 05:05:07.002953
Title: A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate
Title（参考訳）: 通信オーバーヘッド、計算複雑性、収束率のバランスをとる非凸最適化のためのハイブリッド次分散sgd法
Authors: Naeimeh Omidvar, Mohammad Ali Maddah-Ali, Hamed Mahdavi
Abstract要約: 通信負荷の少ない分散勾配降下法(SGD)を提案する。各イテレーションにおける計算複雑性を低減するために、ワーカノードは、方向微分をゼロ階勾配推定で近似する。
参考スコア（独自算出の注目度）: 28.167294398293297
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we propose a method of distributed stochastic gradient descent (SGD), with low communication load and computational complexity, and still fast convergence. To reduce the communication load, at each iteration of the algorithm, the worker nodes calculate and communicate some scalers, that are the directional derivatives of the sample functions in some \emph{pre-shared directions}. However, to maintain accuracy, after every specific number of iterations, they communicate the vectors of stochastic gradients. To reduce the computational complexity in each iteration, the worker nodes approximate the directional derivatives with zeroth-order stochastic gradient estimation, by performing just two function evaluations rather than computing a first-order gradient vector. The proposed method highly improves the convergence rate of the zeroth-order methods, guaranteeing order-wise faster convergence. Moreover, compared to the famous communication-efficient methods of model averaging (that perform local model updates and periodic communication of the gradients to synchronize the local models), we prove that for the general class of non-convex stochastic problems and with reasonable choice of parameters, the proposed method guarantees the same orders of communication load and convergence rate, while having order-wise less computational complexity. Experimental results on various learning problems in neural networks applications demonstrate the effectiveness of the proposed approach compared to various state-of-the-art distributed SGD methods.
Abstract（参考訳）: 本稿では,分散確率勾配勾配降下法(distributed stochastic gradient descent,sgd)を提案する。通信負荷を低減するため、アルゴリズムの各イテレーションにおいて、ワーカーノードはサンプル関数の方向微分であるスケーラを計算し、通信する。しかし、精度を維持するために、特定の反復数ごとに、確率勾配のベクトルを伝達する。各イテレーションの計算複雑性を低減するため、ワーカーノードは1次勾配ベクトルを計算するのではなく、2つの関数評価を行うことで、ゼロ次確率勾配推定による方向微分を近似する。提案手法は,ゼロ次法の収束率を高度に改善し,次々に高速な収束を実現する。さらに, 局所モデル更新と局所モデル同期のための周期的通信を行う通信効率の高い手法と比較して, 非凸確率問題の一般的なクラスとパラメータの合理的な選択に対して, 提案手法は, 順序的に計算複雑性を小さくしつつ, 通信負荷と収束率の同じ順序を保証していることを示す。ニューラルネットワーク応用における様々な学習問題に関する実験結果から,提案手法の有効性を,分散sgd法と比較した。

関連論文リスト

Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。本稿では,ZPDVR法とZPDVR法を提案する。
論文参考訳（メタデータ） (2024-05-28T02:27:53Z)
Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文参考訳（メタデータ） (2023-10-18T10:29:58Z)
Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文参考訳（メタデータ） (2023-01-30T15:46:39Z)
Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文参考訳（メタデータ） (2022-02-26T19:10:48Z)
A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
均質な分散凸最適化のためのNewtonアルゴリズムを解析し、各マシンが同じ人口目標の勾配を計算する。提案手法は,既存の手法と比較して,性能を損なうことなく,必要な通信ラウンドの数,頻度を低減できることを示す。
論文参考訳（メタデータ） (2021-10-07T17:51:10Z)
On Accelerating Distributed Convex Optimizations [0.0]
本稿では,分散マルチエージェント凸最適化問題について検討する。提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
論文参考訳（メタデータ） (2021-08-19T13:19:54Z)
Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descent [7.6860514640178]
分散強化学習のための新しいゼロ階最適化アルゴリズムを提案する。これにより、各エージェントはコンセンサスプロトコルを使わずに、コスト評価を独立してローカル勾配を推定できる。
論文参考訳（メタデータ） (2021-07-26T18:11:07Z)
Iterative Pre-Conditioning for Expediting the Gradient-Descent Method: The Distributed Linear Least-Squares Problem [0.966840768820136]
本稿では,サーバエージェントネットワークにおけるマルチエージェント線形最小二乗問題について考察する。エージェントの目標は、個々のローカルデータポイントを共有することなく、すべてのエージェントが保持する集合データポイントに最適に適合する線形モデルを計算することである。本稿では,データ点の条件付けによる劣化効果を緩和する反復的プレコンディショニング手法を提案する。
論文参考訳（メタデータ） (2020-08-06T20:01:18Z)
Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文参考訳（メタデータ） (2020-06-16T13:41:54Z)
Variance Reduction with Sparse Gradients [82.41780420431205]
SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。我々は、新しい空間演算子:ランダムトップk演算子を導入する。我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
論文参考訳（メタデータ） (2020-01-27T08:23:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。