論文の概要: Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization
- arxiv url: http://arxiv.org/abs/2606.07496v1
- Date: Fri, 05 Jun 2026 17:51:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-08 14:33:29.879779
- Title: Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization
- Title（参考訳）: 強い凸最適化のための分散確率勾配の加速
- Authors: Ming Sun, Kun Yuan,
- Abstract要約: 我々は,Nesterov型原始双対とマルチラウンド高速ゴシップ平均化を組み合わせた分散アルゴリズムであるemphMulti-Gossip Accelerated DSGD (MG-ADSGD)を提案する。
キーとなるアイデアは、ゴシップ深さをミニバッチサイズに結合することで、追加の通信ラウンドがコンセンサス精度を向上し、勾配分散を低減することである。
- 参考スコア（独自算出の注目度）: 8.185454167395326
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decentralized stochastic optimization is a fundamental paradigm for large-scale learning over networks, where agents communicate only with their neighbors and no central coordinator is required. For strongly convex problems, communication efficiency is mainly determined by the condition number \(κ=L/μ\) and the network spectral gap \(1-β\). Although deterministic decentralized methods can simultaneously achieve accelerated \(\sqrtκ\) and \(1/\sqrt{1-β}\) dependences, no existing stochastic method attains both improvements at once. In this paper, we propose \emph{Multi-Gossip Accelerated DSGD} (MG-ADSGD), a decentralized stochastic algorithm that combines Nesterov-type primal--dual extrapolation with multi-round fast gossip averaging. The key idea is to couple the gossip depth with the mini-batch size so that additional communication rounds simultaneously improve consensus accuracy and reduce gradient variance. We show that MG-ADSGD achieves the communication complexity \[ \widetilde{\mathcal O}\!\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt{\fracκ{1-β}}\log\frac{1}ε \right), \] where \(ε\) denotes the target accuracy, \(n\) is the number of nodes, and \(σ^2\) is the gradient variance. To the best of our knowledge, this bound yields the best currently available communication complexity for decentralized stochastic strongly convex optimization, up to logarithmic factors that are independent of $ε$.
- Abstract（参考訳）: 分散確率最適化は、エージェントが隣人とのみ通信し、中央コーディネータを必要としないネットワーク上の大規模学習の基本的なパラダイムである。
強い凸問題に対して、通信効率は主に条件数 \(κ=L/μ\) とネットワークスペクトルギャップ \(1-β\) によって決定される。
決定論的非分散化法は、加速された \(\sqrtκ\) と \(1/\sqrt{1-β}\) の依存を同時に達成できるが、既存の確率的手法は両方の改善を同時に達成できない。
本稿では,Nesterov型原始-双対外挿法とマルチラウンド高速ゴシップ平均化を組み合わせた分散確率的アルゴリズムである \emph{Multi-Gossip Accelerated DSGD} (MG-ADSGD) を提案する。
キーとなるアイデアは、ゴシップ深さをミニバッチサイズに結合することで、追加の通信ラウンドがコンセンサス精度を向上し、勾配分散を低減することである。
MG-ADSGDは通信複雑性を[ \widetilde{\mathcal O}\!
\left( \frac{σ^2}{μnε}\log\frac{1}ε + \sqrt {\frac{1-β}}\log\frac{1}ε \right), \] ここで \(ε\) は目標精度を表し、 \(n\) はノードの数であり、 \(σ^2\) は勾配分散である。
我々の知る限り、この境界は、$ε$とは無関係な対数係数まで、分散確率的強凸最適化のために、現在利用可能な通信の複雑さとして最高のものとなる。
関連論文リスト
- Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
プッシュベースの分散通信は、情報交換が非対称である可能性のある通信ネットワークの最適化を可能にする。
我々は、グラディエント・プッシュ(SGP)アルゴリズムのための統一的な一様安定性フレームワークを開発する。
重要な技術的要素は、2つの量に束縛された不均衡認識の一般化である。
論文 参考訳（メタデータ） (2026-02-24T05:32:03Z) - DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication [71.60998478544028]
本稿では,分散学習グラフのための圧縮通信(termedfrac-CSGP)を用いた差分的プライベート・グラディエント・プッシュを提案する。
一般の非数学的かつ滑らかな目的関数に対して,本アルゴリズムは高精度かつ効率的な通信を実現するために設計されていることを示す。
論文 参考訳（メタデータ） (2025-12-15T17:37:02Z) - Unified Analysis of Decentralized Gradient Descent: a Contraction Mapping Framework [33.417831716314495]
分散勾配降下(DGD)と拡散は、分散機械学習におけるワークホースである。
本稿では,DGDの解析と拡散のための基本的フレームワークを提案する。
これらのツールの使用は、ノイズフリーとノイズフリーの両体制において、厳密な収束境界をもたらす。
論文 参考訳（メタデータ） (2025-03-18T15:36:36Z) - A Communication and Computation Efficient Fully First-order Method for Decentralized Bilevel Optimization [16.020878731214083]
本稿では,分散バイレベル最適化のための完全一階分散手法である$textC2$DFBを提案する。
$textC2$DFBは計算効率と通信効率の両方です。
論文 参考訳（メタデータ） (2024-10-18T02:00:45Z) - Accelerating Distributed Optimization: A Primal-Dual Perspective on Local Steps [4.471962177124311]
分散機械学習では、異なるデータを持つ複数のエージェントにまたがる線形変数が大きな課題となる。
本稿では,原変数上のラグランジアン収束を実現するフレームワークは,エージェント間通信を必要としないことを示す。
論文 参考訳（メタデータ） (2024-07-02T22:14:54Z) - A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization [49.17384566985762]
本稿では,分散合成(平滑+非平滑)最適化のための通信効率の良いMG-Skipを提案する。
直接接続されていないネットワークでは、MG-Skipはマルチゴシップ通信を強い凸設定でほとんどのイテレーションでスキップすることができる。
MG-Skipは、証明可能な通信加速を実現し、非滑らかな設定におけるローカル更新の利点を検証する。
論文 参考訳（メタデータ） (2023-12-19T05:13:16Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。
通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。
分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。
分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
論文 参考訳（メタデータ） (2020-10-02T10:41:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。