論文の概要: Improving the Transient Times for Distributed Stochastic Gradient Methods

• arxiv url: http://arxiv.org/abs/2105.04851v1
• Date: Tue, 11 May 2021 08:09:31 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-12 13:42:52.867867
• Title: Improving the Transient Times for Distributed Stochastic Gradient Methods
• Title（参考訳）: 分散確率勾配法における過渡時間の改善
• Authors: Kun Huang and Shi Pu
• Abstract要約: 拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。 EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。 我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
• 参考スコア（独自算出の注目度）: 5.215491794707911
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the distributed optimization problem where $n$ agents each possessing a local cost function, collaboratively minimize the average of the $n$ cost functions over a connected network. Assuming stochastic gradient information is available, we study a distributed stochastic gradient algorithm, called exact diffusion with adaptive stepsizes (EDAS) adapted from the Exact Diffusion method and NIDS and perform a non-asymptotic convergence analysis. We not only show that EDAS asymptotically achieves the same network independent convergence rate as centralized stochastic gradient descent (SGD) for minimizing strongly convex and smooth objective functions, but also characterize the transient time needed for the algorithm to approach the asymptotic convergence rate, which behaves as $K_T=\mathcal{O}\left(\frac{n}{1-\lambda_2}\right)$, where $1-\lambda_2$ stands for the spectral gap of the mixing matrix. To the best of our knowledge, EDAS achieves the shortest transient time when the average of the $n$ cost functions is strongly convex and each cost function is smooth. Numerical simulations further corroborate and strengthen the obtained theoretical results.
• Abstract（参考訳）: 我々は,ネットワーク上の$n$コスト関数の平均を協調的に最小化するため,各エージェントがローカルコスト関数を持つ分散最適化問題を考察する。 確率勾配情報が得られると仮定して,Exact Diffusion法およびNIDSに適応した適応段差付き精度拡散(EDAS)と呼ばれる分散確率勾配アルゴリズムについて検討し,非漸近収束解析を行う。 我々は、edasが強凸および滑らかな対象関数を最小化する集中確率勾配降下 (sgd) と同じネットワーク独立収束率を漸近的に達成するだけでなく、アルゴリズムが漸近収束率に近づくのに必要な過渡時間を特徴付けるだけでなく、$k_t=\mathcal{o}\left(\frac{n}{1-\lambda_2}\right)$、ここでは1-\lambda_2$が混合行列のスペクトルギャップを表す。 我々の知る限り、EDASは、$n$コスト関数の平均が強く凸であり、各コスト関数が滑らかである場合に最も短い過渡時間を達成する。 数値シミュレーションは、得られた理論結果をさらにコーポレートし、強化する。

関連論文リスト

• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。 所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
  論文  参考訳（メタデータ） (2024-05-23T11:46:03Z)
• Adaptive Federated Learning Over the Air [108.62635460744109]
  オーバー・ザ・エア・モデル・トレーニングの枠組みの中で,適応勾配法,特にAdaGradとAdamの連合バージョンを提案する。 解析の結果,AdaGrad に基づくトレーニングアルゴリズムは $mathcalO(ln(T) / T 1 - frac1alpha の速度で定常点に収束することがわかった。
  論文  参考訳（メタデータ） (2024-03-11T09:10:37Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence [9.11726703830074]
  本稿では,通信制限条件下で分散最適化問題を解くことを検討する。 CEDASと呼ばれる圧縮精密拡散法について述べる。 特に、いつ時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時
  論文  参考訳（メタデータ） (2023-01-14T09:49:15Z)
• Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data [7.513100214864646]
  収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。 適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
  論文  参考訳（メタデータ） (2022-03-29T17:59:10Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method [3.860616339202303]
  本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。 エージェントは問題を解くためにzo座標法を近似する。
  論文  参考訳（メタデータ） (2021-03-24T03:07:46Z)
• A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimization [0.0]
  減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。 ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。 $mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
  論文  参考訳（メタデータ） (2021-02-19T12:22:56Z)
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
  我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。 我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
  論文  参考訳（メタデータ） (2020-10-19T15:23:18Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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