PaperlayerView exact revision on arXiv

Source-linked AI summary

Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization

Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, Viveck R. Cadambe

arXiv:1910.13598v2cs.LGcs.DCstat.ML

TL;DR

The paper studies how to reduce communication in distributed local SGD while retaining linear speedup, addressing limited theoretical understanding of periodic averaging. It tightens convergence analysis under the Polyak-Łojasiewicz condition, develops adaptive synchronization, and validates the theory experimentally. The main result is that O((pT)1/3) communication rounds suffice for linear speedup with error O(1/pT).

  • Problem

    Distributed optimization suffers from communication overhead, while the theoretical performance of local SGD with periodic model averaging remains incompletely understood.

  • Method

    The paper performs a tighter convergence analysis for local SGD on smooth, possibly non-convex objectives satisfying the Polyak-Łojasiewicz condition and introduces adaptive synchronization.

  • Results

    O((pT)1/3) communication rounds suffice for linear speedup with error O(1/pT), and the adaptive scheme is empirically validated on cloud and GPU clusters.

  • Takeaways & Limitations

    Local SGD can retain linear speedup with fewer communication rounds under the paper’s stated conditions, while adaptive synchronization provides a general communication-frequency strategy.

  • Takeaways & Limitations

    Whether linear speedup persists with much larger local-update periods, such as τ = O(T/log T), remains unclear and requires future investigation.

Abstract

from arXiv · show

Communication overhead is one of the key challenges that hinders the scalability of distributed optimization algorithms. In this paper, we study local distributed SGD, where data is partitioned among computation nodes, and the computation nodes perform local updates with periodically exchanging the model among the workers to perform averaging. While local SGD is empirically shown to provide promising results, a theoretical understanding of its performance remains open. We strengthen convergence analysis for local SGD, and show that local SGD can be far less expensive and applied far more generally than current theory suggests. Specifically, we show that for loss functions that satisfy the Polyak-Łojasiewicz condition, $O((pT)^{1/3})$ rounds of communication suffice to achieve a linear speed up, that is, an error of $O(1/pT)$, where $T$ is the total number of model updates at each worker. This is in contrast with previous work which required higher number of communication rounds, as well as was limited to strongly convex loss functions, for a similar asymptotic performance. We also develop an adaptive synchronization scheme that provides a general condition for linear speed up. Finally, we validate the theory with experimental results, running over AWS EC2 clouds and an internal GPU cluster.

1 Introduction

Distributed local SGD reduces communication by allowing workers to perform local updates before periodic model averaging, but its communication-efficiency theory remains limited. This paper tightens the analysis for non-convex objectives satisfying the Polyak-Łojasiewicz condition, introduces adaptive synchronization, and validates the results experimentally.

  • Motivation: Communication costs hinder scaling synchronous distributed SGD, motivating local updates with periodic model averaging across workers.In fully synchronous SGD, workers exchange updates every iteration; local SGD reduces this overhead by averaging models periodically.
  • Motivation: The key question is whether local SGD can use fewer communication rounds than existing schemes while retaining linear speedup.Prior results considered communication periods and round counts, but the paper targets a further reduction in communication.
  • Contributions: O((pT)1/3) communication rounds suffice for linear speedup O(1/pT) under smoothness and the Polyak-Łojasiewicz condition.The result applies to possibly non-convex loss functions and improves the known upper bound on local updates.
  • Contributions: The analysis does not require the bounded stochastic-gradient assumption used in prior work.This broadens the assumptions relative to the cited earlier result while preserving the stated linear-speedup guarantee.
  • Contributions: An adaptive synchronization scheme chooses communication frequency based on conditions for linear speedup and is empirically reported to outperform fixed periodic averaging.The paper also evaluates its theory on Amazon EC2 and an internal GPU cluster.

2 Other Related Work

The paper situates local periodic averaging among communication-reduction methods, contrasting it with asynchronous SGD, gradient compression, varying mini-batches, and prior averaging schemes. It also introduces LUPA-SGD as the paper's periodic-averaging algorithm.

  • Asynchronous parallel SGD: Asynchronous SGD reduces synchronization delay but can introduce convergence errors from stale gradients.Prior work studies bounded delays while preserving linear speedup in some convex settings.
  • Gradient compression based schemes: Gradient compression reduces communication cost by transmitting fewer bits through quantization, limited precision, or vector sparsification.
  • Periodic model averaging: One-shot averaging is empirically effective in some problems, but its ability to achieve linear speedup remains open and can yield inaccurate non-convex solutions.
  • Parallel SGD with varying mini-batch sizes: Exponentially increasing mini-batch sizes can achieve linear speedup with only log T algorithm iterations in distributed settings.
  • Empirical motivation: Increasing mini-batches can cause SyncSGD divergence, as shown for mini-batch size 1024 compared with 512 on Epsilon logistic regression.
  • Local periodic averaging: LUPA-SGD(τ) alternates τ local stochastic-gradient updates with model averaging across workers.The algorithm samples local mini-batches, computes stochastic gradients, updates local models, and periodically aggregates them.

3 Local SGD with Periodic Averaging

This section defines local SGD with periodic model averaging and states the assumptions used for its analysis. Workers independently perform local stochastic updates and synchronize every τ iterations.

  • Algorithm: LUPA-SGD(τ) uses distributed machines that sample independent mini-batches from the dataset to compute local stochastic gradients.The mini-batches are represented as independent realizations of a random subset of fixed cardinality.
  • Algorithm: After every τ iterations, workers average their local models to update the global parameters.The procedure alternates τ local updates with one communication round over T iterations.
  • Assumptions: The analysis assumes stochastic gradients are unbiased estimators of the corresponding full gradient.
  • Assumptions: The stochastic-gradient variance is bounded under the stated variance assumption.The passage identifies this as a standard assumption and notes that bounded variance is a stronger special case when C = 0.
  • Assumptions: The objective is assumed smooth and μ-PL, without requiring convexity.The PL condition generalizes strong convexity, and strongly convex objectives satisfy it.

4 Convergence Analysis

The convergence analysis establishes rates for LUPA-SGD under smoothness and the PL condition, linking local-update length to communication complexity. It attributes the improvement over prior work to weaker assumptions and a tighter analysis.

  • Analysis setup: The analysis rewrites the algorithm using the average model across p machines and relates it to perturbed SGD.
  • Main convergence result: The proof uses i.i.d. sampling and suitably chosen local updates to reduce stochastic-gradient variance and obtain linear speedup.
  • Main convergence result: O(1/pT) convergence error is achieved with an appropriate choice of the local-update period τ.The theorem's rate is stated for the LUPA-SGD algorithm under its listed assumptions.
  • Implications: The theorem also applies to μ-strongly convex objectives because strong convexity implies the μ-PL condition.
  • Implications: For σ² = 0 and C = 0, LUPA-SGD reduces to full-batch gradient descent, matching the corresponding convergence analysis.
  • Main convergence result: O((pT)^(1/3)) communication rounds suffice for linear speedup under the PL condition.The result is presented as an improved communication bound for local SGD.
  • Comparison with existing algorithms: The improvement over prior analysis uses the weaker PL assumption and a novel proof technique rather than a uniformly bounded stochastic-gradient assumption.The paper specifically contrasts its analysis with prior work relying on bounded variance and bounded gradients.

5 Adaptive LUPA-SGD

The paper proposes ADA-LUPA-SGD, an adaptive synchronization strategy that increases local updates while preserving theoretically supported linear speedup under stated conditions. Its analysis distinguishes this guarantee from exponential schedules with only O(log T) communication rounds.

  • Adaptive synchronization: Adaptive LUPA-SGD chooses communication periods using the convergence behavior and can increase the number of local updates across periods.The strategy treats each communication period as restarting from a new averaged model and uses an increasing sequence of local-update counts.
  • Adaptive synchronization: The adaptive algorithm preserves linear speedup when its sequence of local updates satisfies three stated conditions.The theorem analyzes arbitrary positive local-update sequences under the paper’s smoothness and PL-based assumptions.
  • Guarantee boundary: O(log T) communication rounds from exponentially increasing local-update periods do not satisfy these three conditions.The paper presents this as theoretical insight into how large local-update periods can be while retaining the analyzed guarantee, while noting that impossibility results remain future work.
  • Scope: The adaptive analysis targets communication-round reduction for a fixed number of model updates, unlike work optimizing convergence error with respect to wall-clock time.The authors state that a wall-clock model could extend the analysis to communication-computation trade-offs.

6 Experiments

Experiments evaluate LUPA-SGD and ADA-LUPA-SGD on large-scale logistic regression across cloud and GPU settings. They report convergence, machine-scaling, and adaptive-synchronization comparisons supporting faster convergence or fewer communications in the tested settings.

  • Experimental setup: The experiments use the Epsilon dataset with logistic regression, which satisfies the Polyak-Łojasiewicz condition.Epsilon contains 400,000 training samples, 100,000 test samples, and feature dimension 2000.
  • Experimental setup: The study runs across Amazon EC2 instances with PyTorch and an internal NVIDIA Tesla V100 cluster with TensorFlow.The authors use these distinct platforms and libraries to evaluate efficacy across settings.
  • Convergence: τ = 91 is used for LUPA-SGD in the normal-training experiment, while τ ≈ 5 corresponds to the compared prior setting.For seven epochs on five machines with minibatch size 128, the experiment has T = 21875 model updates.
  • Convergence: LUPA-SGD with higher τ converges to the same error level as SyncSGD faster in wall-clock time, including comparison with one-shot learning.Figure 2 compares SyncSGD, LUPA-SGD with τ = 5 and τ = 91, and one-shot averaging.
  • Speedup: LUPA-SGD with τ = 91 benefits from linear speedup as the number of machines increases when measuring time to reach ϵ = 0.35.The reported results average five repeated experiments.
  • Adaptive synchronization: ADA-LUPA-SGD reaches the same error level as fixed-period LUPA-SGD with fewer communications, using τ0 = 91 and τi = (1 + iα)τ0 with α = 1.09 for 10 rounds.The experiments increase τi linearly without using a function-value oracle.

7 Conclusion and Future Work

The paper strengthens the theory of periodic averaging for distributed non-convex optimization, preserves linear speedup with an improved local-update bound, and introduces an adaptive schedule validated experimentally. It leaves the achievable scale of local updates and corresponding lower bounds unresolved.

  • Conclusion: The paper improves the known bound on local updates while preserving linear speedup for distributed non-convex optimization.The conclusion states that experiments validate the theoretical results.
  • Conclusion: The adaptive algorithm decides the number of local updates as training proceeds.This extends the paper beyond fixed periodic averaging.
  • Future work: Whether linear speedup persists with larger local updates, such as τ = O(T/log T), remains unclear.The authors identify this as a future direction requiring further investigation.
  • Future work: Lower bounds for the number of local updates needed to achieve linear speedup with fixed minibatch size remain an open research question.The conclusion also connects this question to determining the maximum allowable τ without performance decay.

Supplementary Material Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization

The supplementary material introduces notation used throughout the appendix, including the inner product between vectors.

  • Notation: The appendix defines notation for ease of exposition in its subsequent analysis.This notation section precedes the appendix’s technical material.
  • Notation: The inner product between vectors x and y is denoted by ⟨x, y⟩.The notation is used for vector relationships in the appendix.

A Proof of Theorem 1

The proof of Theorem 1 decomposes the convergence bound into terms controlled by successive lemmas, then selects a decreasing learning rate to make key coefficients non-positive. It combines bounds on stochastic-gradient variance, model disagreement, and recursive error terms to obtain the theorem's final upper bound.

  • Term-by-term bounds: The proof bounds the second, first, and third terms of the main inequality separately using assumptions on smoothness, unbiased stochastic gradients, sampling, and local updates.These bounds are introduced through Lemmas 1–3 and then combined in the main recursion.
  • Learning-rate choice: Choosing η_t = 4/[μ(t+a)] with a = ατ + 4 makes the relevant coefficients non-positive and cancels the effect of B_t in the recursion.The proof selects α through two positivity conditions and uses monotonicity properties of η_t, Δ_t, and B_t.
  • Final recursion: The resulting recursion is iterated after introducing ζ(t) = E[F(x̄(t)) − F*], yielding the final bound used to conclude Theorem 1.The proof explicitly plugs the auxiliary lemmas into the main inequality and recursively applies the resulting relation.
  • Term-by-term bounds: The average-model disagreement is related to stochastic-gradient variance and bounded using unbiased estimation, independent mini-batch sampling, and the variance assumption.The argument proceeds by relating disagreement to gradient differences, applying unbiasedness, and then bounding the resulting terms.

B.6 Proof of Lemma 6

The proof of Lemma 6 iterates the established recursion after applying the learning-rate bounds and controlling the remaining summation terms. The resulting upper bound is then used directly in the theorem analysis.

  • Recursive bound: The proof starts from the bound supplied by Lemma 5 and multiplies the recursion by z_t before iterating it.The argument uses the auxiliary quantities z_t and A_k to organize the recursive bound.
  • Recursive bound: The non-increasing learning rate is used to control one of the recursive terms during the iteration.This monotonicity property supplies the justification for the corresponding inequality.
  • Term control: The remaining terms are bounded separately, including a finite-sum calculation involving squared integers, before the upper bound is assembled.The proof invokes the closed form for the sum of squares in controlling these terms.
  • Conclusion: The assembled inequality produces the concluding bound, while the proof of Theorem 2 extends the argument and reuses the rest of Theorem 1's proof.Lemma 7 and Lemma 8 provide the corresponding theorem-2 recursion and learning-rate reduction.

D Convergence analysis for full-batch GD

The full-batch GD analysis studies a decreasing learning rate under smoothness and the Polyak–Łojasiewicz condition. Under explicit conditions on the rate parameters, it derives an O(1/T^3) convergence rate.

  • Setup: The analysis considers centralized GD with p = 1 and learning rate η_t = a/[μ(t+b)].The rate is chosen in the same general form used in the local-SGD convergence analysis.
  • PL-based recursion: The smoothness-based descent inequality is converted using the PL condition into a recursion for the optimization error.The PL condition supplies the step linking gradient magnitude to function suboptimality.
  • Rate derivation: The final inequality establishes that the O(1/T^3) rate is achievable for centralized full-batch GD with this learning-rate schedule.The conclusion follows from the final bound derived in Eq. (73).
  • Rate derivation: Under 2a > 3 and b > max(...), multiplying the recursion by (t+b)^2 enables telescoping-style summation.The proof uses the parameter condition 2a ≥ 3 in the subsequent inequality.
Loading 1910.13598v2…