Local SGD

Overview

Data-parallel SGD usually synchronises after every step. Local SGD lets each worker take H steps on its own mini-batches and only then averages the models, so communication happens once per H steps 1808.07217 §3. The invariant all variants share: right after an averaging round every worker holds the same model, and between rounds the local models may drift apart [arxiv:1808.07217 alg. 2].

The same method raises a generalization question. If the local batch is B and H = 1 is replaced by H local steps, both schemes evaluate the same number of gradients per round, but their updates differ, so their test accuracy can differ 1808.07217 §1. Large global batches are the case where mini-batch SGD is known to lose accuracy, which is why the paper targets them 1808.07217 §1.

Variants

Local SGD with a fixed number of local steps

Each worker runs H SGD steps on its own data shard, then all models are averaged and every worker restarts from the average 1808.07217 §3. The paper also calls this federated averaging or parallel SGD [arxiv:1808.07217 §1]. Reported speed-ups, ResNet-20 on CIFAR-10 with local batch 128: H = 8 reaches 91.2% test accuracy 2.59× faster than the mini-batch baseline, and H = 2 reaches 92.57% 1.76× faster 1808.07217 §4.1. For ResNet-50 on ImageNet, local SGD reaches 75% top-1 at least 1.5× faster on a 16×2-GPU cluster 1808.07217 §4.1. Card: Don't Use Large Mini-Batches, Use Local SGD.

Post-local SGD

Post-local SGD runs ordinary mini-batch SGD (H = 1) until the first learning-rate decay, then switches to H local steps 1808.07217 §3. Before the switch the large-batch warm-up and schedule carry over unchanged [arxiv:1808.07217 §3]. The paper ties the switch to the first decay, which is 50% of training samples in the CIFAR runs 1808.07217 §3 1808.07217 app. A.4.1.

Reported accuracy, global batch K·B = 2048 on CIFAR-10 with ResNet-20: 93.02 ± 0.24 with H = 32, against 92.48 ± 0.17 for large-batch SGD and 92.63 ± 0.26 for small-batch SGD 1808.07217 §4.2. The post-local mean is above the large-batch mean in all six CIFAR rows of that table, across three models and two datasets 1808.07217 §4.2. On ImageNet, ResNet-50 at K·B = 4096 reaches 76.18 with post-local SGD and 75.87 with mini-batch SGD [arxiv:1808.07217 §4.2] 1808.07217 app. C.5.3. The appendix also tests starting after the second decay; the authors report more communication and a higher risk of sharp minima for that choice 1808.07217 app. C.2.

Hierarchical local SGD

Two levels of averaging. Workers inside a block synchronise after H local steps, and blocks synchronise after H_b block steps 1808.07217 §3 1808.07217 app. D.1. In the paper's ResNet-20 CIFAR-10 runs on 16 GPUs with H·H_b = 16, the setting with 8 nodes of 2 GPUs gives 91.41 ± 0.23 for H = 8, H_b = 2, against 90.02 ± 0.28 for H = 1, H_b = 16 [arxiv:1808.07217 app. D.3.1]. The paper attributes the gain to synchronising inside each node 1808.07217 app. D.3.1. This table uses different settings from the flat runs, so compare only within it 1808.07217 app. D.3. Implementation status of this variant is in the paper card.

Federated local surrogate with a global gradient term

This variant comes from federated learning over heterogeneous devices. Each device (UE) minimises a local surrogate instead of its plain loss: the local loss plus a term that pulls the device toward a global gradient estimate, scaled by a hyper-learning rate η, minus the device's gradient at the received model 1910.13067 §IV 1910.13067 eq. 2. The surrogate is solved only to a local accuracy θ, which is the test in 1910.13067 eq. 3. In the analysis the inner solver is gradient descent, and Lemma 1 gives the number of local rounds needed for that accuracy 1910.13067 lemma 1. Small θ means many local rounds and fewer global ones 1910.13067 §IV remark 2.

Each round, the server averages the uploaded models and the uploaded full local gradients with weights D_n / D, then broadcasts both 1910.13067 eq. 4 1910.13067 eq. 5 1910.13067 alg. 1. Algorithm 1 does not give an initial global gradient estimate 1910.13067 §IV. Under smoothness and strong convexity, the paper proves a linear rate Θ that depends on η, θ and the condition number ρ 1910.13067 §IV 1910.13067 eq. 10 1910.13067 eq. 11. The author-reported experiments compare against FedAvg on MNIST, FEMNIST and synthetic data, and the authors report lower training loss and higher test accuracy 1910.13067 §VI. The gains are not uniform across settings. For MNIST with local batch 20 the test-accuracy gain is about +1.3%, and for batch 40 about +0.7% with a −0.2% change in training loss 1910.13067 fig. 4. The paper also models wall-clock time and device energy on a shared wireless uplink and splits the resulting problem into three sub-problems 1910.13067 §V. Card: Federated Learning over Wireless Networks: Convergence Analysis and Resource Allocation.

Local SGD with sign compression

The paper also combines local steps with sign-based compression, with and without error feedback 1808.07217 §4.2 1808.07217 app. C.5.5. For EF-signSGD on CIFAR-100 (ResNet-20, K·B = 2048), accuracy rises from 68.19 ± 0.10 at H = 1 to 69.49 ± 0.21 at H = 64 1808.07217 app. C.5.5. Plain signSGD is not monotone in H on the same task: 68.32 at H = 32, then 68.12 at H = 64 1808.07217 app. C.5.5.

When to use which

Caveats the paper itself raises:

• Before the switch the method is mini-batch SGD with one synchronisation per step, so the whole-run saving is smaller than the saving in phase two 1808.07217 §3 1808.07217 §4.2. For ResNet-20 on CIFAR-10 with 16 GPUs, phase-two-only speed-ups are 17.33 (H = 16) and 20.80 (H = 32) 1808.07217 app. C.3.
• The speed-ups were measured on 8×2 GPUs with 10 Gbps Ethernet; they do not transfer to other interconnects without measurement 1808.07217 §4 1808.07217 app. C.3.
• Large-batch baselines were tuned: the learning rate scales with K, with a 5-epoch linear warm-up, and the multiplier grid was extended when its optimum sat on an edge 1808.07217 app. A.3 1808.07217 app. A.4.1. Matching the paper needs a comparable tuning budget.
• Gains are not uniform. On WikiText-2 with an LSTM, post-local SGD gives 86.85 ± 0.13 perplexity against 86.90 ± 0.49 for large batch, a difference inside the spread 1808.07217 app. C.5.2.
• Whether momentum buffers are averaged at synchronisation is not stated 1808.07217 app. A.4.1.
• The noise explanation for the generalization gap is the paper's argument 1808.07217 §5. Its isotropic-noise baseline reached 92.46 ± 0.27 against 93.02 ± 0.24 for post-local SGD on CIFAR-10, but the baseline was searched only over the grid given 1808.07217 app. C.5.4.
• The paper reports flatter minima for post-local SGD, shown by Hessian spectra and linear interpolation between solutions 1808.07217 §5.1.
• The federated variant's convergence result needs full-batch gradients, full participation and strongly convex, smooth losses [arxiv:1910.13067 §IV remark 5]. Its mini-batch and partial-participation results are experimental only 1910.13067 §VI. Sampling 10 of 100 devices per round is used in the main figures 1910.13067 fig. 4.
• The federated variant's η and θ rules depend on L, β and ρ, and the paper does not say how to estimate them 1910.13067 §IV. The grid for the FedAvg baseline's learning rate is described but its results are not reported 1910.13067 §VI.
• The wireless solution is a stationary point of a non-convex problem, not a proven global optimum 1910.13067 §V-C 1910.13067 theorem 2.

Implementation sketch

The common core, with the switch as a parameter. Plain mini-batch SGD is the case where the switch round is the first round.

# Local SGD with a switch to local steps  [arxiv:1808.07217 alg. 2]
# Input:  w0, K workers, T rounds, switch round t1, local steps H,
#         local batch B_loc, learning-rate schedule lr(t)
# Output: averaged model after T rounds

def local_sgd(w0, K, T, t1, H, B_loc, lr):
    # All workers start from the same model  [alg. 2]
    shared = w0
    local = [w0 for k in range(K)]
    for t in range(T):
        # One step per round before t1, H steps after  [§3]
        H_t = 1 if t < t1 else H
        for k in range(K):  # the workers run in parallel
            for h in range(H_t):
                # Step on this worker's own mini-batch  [alg. 2]
                g = gradient(local[k], sample(shard[k], B_loc))
                local[k] = local[k] - lr(t) * g
        # Average the local models and restart from the average  [§3]
        shared = sum(local) / K
        local = [shared for k in range(K)]
    return shared

Implementation notes:

• Average the models, as the main text does 1808.07217 §3. The algorithm box applies the learning rate a second time to the averaged difference 1808.07217 alg. 1, which double-scales the update if implemented literally.
• Hierarchical local SGD adds a second averaging level with its own period H_b over blocks 1808.07217 app. D.1.
• Compressed variants replace the averaged update with a compressed one 1808.07217 app. C.5.5.
• The federated variant replaces the local gradient step with a step on the corrected surrogate 1910.13067 eq. 2 1910.13067 eq. 7. Each device uploads its gradient as well as its model, so budget the uplink for both 1910.13067 alg. 1 1910.13067 §V-A.

Contradictions

No numerical disagreement between the two papers is known, but their gains are measured against different baselines and are not comparable. The first paper compares against large-batch and small-batch mini-batch SGD on image-classification benchmarks 1808.07217 §4.2. The second compares against FedAvg on federated benchmarks 1910.13067 §VI.

Within the first paper, the main text averages the local models [arxiv:1808.07217 §3], while the algorithm box applies the learning rate again to the averaged difference 1808.07217 alg. 1. Both are stated; see the notes above.

Papers

• Don't Use Large Mini-Batches, Use Local SGD: introduces post-local SGD and hierarchical local SGD, and studies generalization at large global batch sizes.
• Federated Learning over Wireless Networks: Convergence Analysis and Resource Allocation: a federated local surrogate with a global gradient term, a linear convergence result for strongly convex losses, and a wireless time and energy allocation.