Hiroki Naganuma

Local SGD入門: Periodic Averaging・FedAvg・非同期・分散最適化

長沼大樹 / Hiroki Naganuma · 更新:

2026年10月の再サーベイ： 研究史・重要文献・最近の進展を整理した新版を追加しました（2026年10月3日基準）。以下は従来のメモです。定義・適用条件の訂正は新版を参照してください。

定義

$K$ workersが共通初期値 $x_0$ から始め、worker $k$ が $H$ 回ローカル更新してから平均する 最小構成を考えます。

\[x_{t+1}^{(k)}=x_t^{(k)}-\eta_t g_t^{(k)}, \qquad x_{t+1}^{(k)}\leftarrow \frac{1}{K}\sum_{j=1}^K x_{t+1}^{(j)} \quad\text{if }t+1\in\mathcal I.\]

$\mathcal I$ は同期時刻の集合で、固定周期なら概ね ${H,2H,\dots}$ です。$H=1$ は 各stepで平均するsynchronous mini-batch SGD、$H>1$ がperiodic averagingを行うLocal SGDです。 Stich (ICLR 2019) は凸問題等の仮定下で、gradient計算量に 関してmini-batch SGDと同じrateを保ちながら通信回数を減らせる範囲を解析しています。 深層学習一般に同じ保証がそのまま成り立つ、という主張ではありません。

似た手法との境界

手法 集約先 主なデータ設定 参加 更新の特徴
synchronous SGD / DDP all-reduce等 通常は分割された中央dataset 全workerが毎step $H=1$
Local SGD 中央平均またはall-reduce 多くは同質workerを想定 通常は全worker $H>1$ stepごとにmodel averaging
Post-Local SGD 同上 data-parallel training 全worker 前半$H=1$、後半$H>1$
FedAvg server clientごとに非IID・不均衡になり得る 部分参加を許す 複数local epoch、sample数で重み付き平均
asynchronous local method server等 worker速度が異なる 更新到着順 stale updateを扱う必要
decentralized SGD peer-to-peer graph 各nodeにlocal data 中央serverなし mixing matrixで近傍通信

FedAvgはLocal SGDと数式的に重なる特殊設定を持ちますが、同義ではありません。 FedAvg原論文はclient dataの非IID性、 不均衡、local epoch、中央serverを前提に議論します。一方、 decentralized PSGDは中央平均器を使わず通信graph上で混合します。

何を比較すべきか

Context

重要人物 (更新途中)

Original Paper

LocalSGD / Local SGD Converges Fast and Communicates Little

概要

Post Local SGD / Don’t Use Large Mini-Batches, Use Local SGD

概要

Extrapolation for Large-batch Training in Deep Learning

欠落画像: 以前ここで参照していた extrapolatedsgd/algo1.png はrepository内に存在しません。 別画像への推測置換はせず、アルゴリズムは 原論文で確認してください。

概要

後続の研究

DiLoCo: Distributed Low-Communication Training of Language Models

概要

Asynchronous Local-SGD Training for Language Modeling

概要

実験結果

Findings

関連研究

Futurework

Distributed Deep Learning In Open Collaborations

概要

貢献

SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum

概要

LocalSGD との違い

検証

疑問

Communication-efficient SGD: From Local SGD to One-Shot Averaging

概要

本論文は、分散環境における確率的勾配降下法（SGD）の通信効率を改善するために、Local SGD を発展させ、通信回数を大幅に削減する新しいアプローチを提案しています。

これまでの研究との違いや新規性

従来の研究では、Local SGD は通信頻度を高めることで収束速度を向上させることが示されてきましたが、依然として通信回数が増加するため、並列化の効果が減少するという課題がありました。 本研究では、イテレーション数が増加するにつれて通信頻度を減少させる新しい Local SGD 手法を提案し、総通信回数を最小限に抑えながらも収束速度を維持することに成功しました。 また、従来の手法では収束率が T に依存していましたが、本研究では通信回数が T に完全に依存しないことを示し、これまでにない通信効率を達成しています。

Federated Learning の文脈

FedAvg（Federated Averaging）

Local SGD との違い

FedOpt（Federated Optimization）

Locally Adaptive Federated Learning

概要

Layer-wise and Dimension-wise Locally Adaptive Federated Learning

概要

Federated Learning with Buffered Asynchronous Aggregation

概要

その他の関連研究

Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication

概要

Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering