PaperlayerView exact revision on arXiv

Source-linked AI summary

Variance Reduced Local SGD with Lower Communication Complexity

Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, Yifei Cheng

arXiv:1912.12844v1cs.LGcs.DCmath.OCstat.ML

TL;DR

Local SGD lowers communication but faces degraded convergence with non-identical worker data and typically relies on extra variance assumptions. The paper proposes VRL-SGD, which adds variance reduction to Local SGD. It is theoretically shown to retain linear iteration speedup with lower communication complexity, while experiments report stronger performance than Local SGD in the non-identical case.

  • Problem

    Non-identical worker data causes gradient variance that degrades Local SGD convergence, while prior analyses require extra assumptions such as bounded inter-worker variance.

  • Method

    VRL-SGD incorporates variance reduction into Local SGD to eliminate the dependency on gradient variance among workers.

  • Results

    VRL-SGD achieves linear iteration speedup with communication complexity O(T^1/2 N^3/2) for identical or non-identical data, and performs significantly better than Local SGD in the non-identical case.

  • Takeaways & Limitations

    VRL-SGD is more suitable than Local SGD for settings such as federated learning where worker data are non-identical.

  • Takeaways & Limitations

    The paper leaves deep-learning models with batch-normalization layers for future work because they may cause unstable convergence in the non-identical case.

Abstract

from arXiv · show

To accelerate the training of machine learning models, distributed stochastic gradient descent (SGD) and its variants have been widely adopted, which apply multiple workers in parallel to speed up training. Among them, Local SGD has gained much attention due to its lower communication cost. Nevertheless, when the data distribution on workers is non-identical, Local SGD requires $O(T^{\frac{3}{4}} N^{\frac{3}{4}})$ communications to maintain its \emph{linear iteration speedup} property, where $T$ is the total number of iterations and $N$ is the number of workers. In this paper, we propose Variance Reduced Local SGD (VRL-SGD) to further reduce the communication complexity. Benefiting from eliminating the dependency on the gradient variance among workers, we theoretically prove that VRL-SGD achieves a \emph{linear iteration speedup} with a lower communication complexity $O(T^{\frac{1}{2}} N^{\frac{3}{2}})$ even if workers access non-identical datasets. We conduct experiments on three machine learning tasks, and the experimental results demonstrate that VRL-SGD performs impressively better than Local SGD when the data among workers are quite diverse.

1 Introduction

Distributed SGD accelerates training with multiple workers, but communication limits synchronous methods and non-identical data degrades Local SGD. VRL-SGD adds variance reduction to lower communication complexity while retaining linear iteration speedup.

  • Motivation: Distributed optimization uses multiple workers to accelerate machine-learning training, but S-SGD communication costs hinder linear time speedup.S-SGD can achieve linear iteration speedup, meaning N workers reduce total iterations by N times.
  • Existing approach: Local SGD reduces communication rounds from O(T) to O(T/k) by averaging locally updated models every k iterations.This lowers communication frequency relative to S-SGD.
  • Challenge: Non-identical worker data creates gradient variance that significantly degrades Local SGD convergence, while prior methods require extra assumptions.Those assumptions include bounded inter-worker gradient variance, bounded gradients, or identical worker data.
  • Proposed method: VRL-SGD incorporates an additional variance-reduction component and removes the need for bounded gradient variance among workers.Its goal is to further reduce communication complexity in the non-identical case.
  • Theoretical contribution: Communication complexity decreases from O(T^3/4 N^3/4) to O(T^1/2 N^3/2) for non-identical data.The paper presents this reduction as supporting better time speedup.
  • Empirical evaluation: Experiments on three machine-learning tasks show VRL-SGD performs significantly better than Local SGD with different worker data distributions.With identical datasets, it maintains the same convergence rate as Local SGD.

2 Related Work

Related work reduces communication through gradient compression or less frequent synchronization, while variance-reduction methods address inter-worker variance. VRL-SGD combines variance reduction with Local SGD and is reported to improve communication complexity without extra assumptions.

  • Communication-efficient SGD: Distributed SGD methods reduce communication through lossy gradient representations or lower communication frequency.These approaches include inexact gradient approximations, partial data representations, and periodic model averaging.
  • Local SGD: Local SGD performs local updates and periodically averages models, achieving linear iteration speedup for strongly convex and non-convex problems.It has been used in large-scale machine-learning training.
  • Variance reduction: Standard variance-reduction methods such as SVRG, SAGA, and SARAH do not directly address gradient variance among distributed workers.Decentralized methods including EXTRA and D2 were developed to eliminate this inter-worker variance.
  • VRL-SGD: VRL-SGD incorporates variance reduction into Local SGD, reducing extra assumptions and improving communication complexity for non-identical data.The comparison framework distinguishes identical and non-identical datasets and treats bounded gradients or bounded inter-worker variance as extra assumptions.

3 Preliminary

The paper studies data-parallel training with potentially different worker distributions and defines a finite-sum local-loss problem. Its analysis assumes smooth local functions and bounded within-worker stochastic-gradient variance, but not bounded inter-worker variance.

  • Problem definition: The setting uses N workers that collaboratively train a model while potentially accessing data with different distributions.The i-th worker's data distribution is denoted D_i.
  • Problem definition: Each worker's local loss is defined as f_i(x) := E_{ξ_i∼D_i}[f_i(x, ξ_i)].This expresses the local objective as an expectation over the worker-specific data distribution.
  • Notations: The notation includes local models x_t^i and the average model over all N workers, denoted x̂_t.The last and penultimate communication iterations are represented by t′ and t′′.
  • Assumptions: The analysis assumes L-Lipschitz gradients for all local functions and bounded stochastic-gradient variance within each worker.These assumptions are stated as standard assumptions for distributed-algorithm analysis.
  • Assumptions: Unlike previous Local SGD analyses, the paper does not require bounded gradient variance among workers, bounded gradients, or identical worker data distributions.This distinction targets the non-identical setting.

4 Algorithm

VRL-SGD extends Local SGD with variance-reduction steps while retaining periodic local updates, reducing communication without assuming identical worker data. Its communication-period bound applies in both identical and non-identical cases.

  • Algorithm: VRL-SGD maintains local models and averages them every k steps, while adding gradient-based variance reduction between communications.The method computes a deviation term and uses a stochastic approximation gradient for local updates.
  • Algorithm: VRL-SGD with k = 1 is equivalent to S-SGD, while k > 1 reduces communication rounds by k times compared with S-SGD.Setting the variance-reduction term to zero makes VRL-SGD equivalent to Local SGD.
  • Communication complexity: O(T^1/2/N^3/2) is the communication-period bound attained by VRL-SGD in both identical and non-identical cases.Local SGD has the weaker non-identical-case bound O(T^1/4/N^3/4).
  • Variance reduction: The variance-reduction update drives the worker-gradient discrepancy toward zero near a local minimum, whereas Local SGD’s corresponding discrepancy cannot converge to zero under non-identical data.This provides the paper’s explanation for VRL-SGD’s faster convergence in the non-identical case.

5 Theoretical Analysis

The analysis bounds the expected squared gradient norm of the average model and derives convergence, warm-up, linear-speedup, and communication-complexity consequences. VRL-SGD removes dependence on worker gradient variance in the stated non-identical-case guarantees.

  • Convergence analysis: The analysis bounds the expected squared gradient norm of the average model, the metric used to establish non-convex convergence rates.The bound is developed under the theorem’s learning-rate and communication-period assumptions.
  • Special case: When k = 1, C = 0 and VRL-SGD is equivalent to S-SGD, whose convergence is independent of worker gradient variance.This follows from the theorem’s definition of C and the algorithmic equivalence.
  • Warm-up: With a warm-up setting k = 1 initially, the convergence result is not related to the extent of non-iid data.Under this setting, the variable C becomes 0.
  • Linear speedup: O(1/(NT)) is VRL-SGD’s convergence rate, requiring O(1/(Nϵ^2)) iterations for an ϵ-optimal solution and yielding linear iteration speedup.The rate is stated as consistent with S-SGD and Local SGD.

6 Experiments

Experiments compare VRL-SGD with Local SGD, EASGD, and S-SGD across three tasks under identical and non-identical data partitions. VRL-SGD matches S-SGD’s convergence in the non-identical case, while all methods are similar in the identical case.

  • Experimental settings: The experiments use LeNet on MNIST, TextCNN on DBPedia, and transfer learning on tiny ImageNet.Each GPU is treated as one worker, and the study evaluates both identical and non-identical data access.
  • Non-identical case: In the non-identical case, VRL-SGD converges at the same rate as S-SGD, while Local SGD converges slowly or may not converge.The comparison uses training loss versus epochs, with non-identical partitions maximizing data variance among workers.
  • Non-identical case: Under the same communication period, VRL-SGD converges much faster than Local SGD in the non-identical case.Local SGD must use a smaller period to match the convergence rate, increasing communication cost; EASGD performs worst under the same period.
  • Identical case: In the identical case, all algorithms have similar convergence rates, and VRL-SGD, EASGD, and Local SGD converge as fast as S-SGD.This occurs when workers observe unbiased stochastic gradients.

7 Conclusion & Future Work

VRL-SGD incorporates variance reduction into Local SGD and is theoretically shown to achieve optimal communication complexity and linear iteration speedup for nonconvex objectives in both identical and non-identical data settings. The paper reports experimental effectiveness and identifies batch normalization in deep learning as future work because it may destabilize non-identical-case convergence.

  • VRL-SGD incorporates variance reduction into Local SGD to reduce communication complexity.
  • VRL-SGD achieves linear iteration speedup with communication complexity O(T^1/2 N^3/2) whether workers access identical or non-identical data.
  • VRL-SGD is experimentally effective, performing significantly better than Local SGD in the non-identical case while matching its convergence rate otherwise.
  • Future work will study deep learning models with batch normalization, which may cause unstable convergence in the non-identical case.
  • The proof develops bounds on partially accumulated local gradients and the difference between local and average models under learning-rate and communication-period conditions.

C Proof of Theorem 5.1

The proof of Theorem 5.1 derives a convergence result for Algorithm 1 by combining smoothness, independence, variance, and communication-period bounds under explicit learning-rate conditions.

  • Theorem 5.1 assumes γ ≤ 1/(2L) and 72k^2γ^2L^2 ≤ 1 for Algorithm 1's convergence result.
  • The proof applies L-smoothness of the local and global objectives to relate successive average-model values to gradient terms.
  • Independence across workers and stochastic-gradient steps enables the expectation equalities and bounds used in the proof.
  • Cauchy’s inequality and the Lipschitz-gradient assumption bound intermediate terms before summation over t = 0 to T − 1.
  • The proof substitutes the local-model difference bound into the main inequality and uses 72k^2γ^2L^2 ≤ 1 to conclude.

D Proof of Corollary 5.2

The proof of Corollary 5.2 specializes Theorem 5.1 by selecting the learning rate and imposing iteration and communication-period conditions, then derives the stated final convergence result.

  • Corollary 5.2 sets the learning rate γ according to the theorem’s conditions to obtain a specialized convergence guarantee.
  • The specialization requires bounds involving T, k, L, σ^2, and N to ensure the theorem’s assumptions hold.
  • The proof obtains the final result by substituting the parameter conditions into equation (34).

E More Experiments

The experiments vary worker-gradient variance through b and compare Local SGD with VRL-SGD variants across communication periods. VRL-SGD converges better under non-identical data, while warm-up makes it less sensitive to variance.

  • The experiment adjusts b to control the variance among workers and compares convergence across communication periods k.
  • Local SGD converges more slowly than VRL-SGD-W and VRL-SGD when the communication period k is relatively large.
  • VRL-SGD without warm-up depends on b, whereas VRL-SGD-W is not sensitive to b.
  • The variance of v_i in VRL-SGD and VRL-SGD-W converges to zero, while Local SGD’s gradient variance remains constant and depends on b.
  • The results show better convergence for VRL-SGD than Local SGD in the non-identical case and greater robustness to worker variance with warm-up.

F The Analysis of Parameter k

The experiments compare algorithms under different communication periods k in the non-identical case. VRL-SGD remains faster than Local SGD at larger k, although its convergence is affected when k becomes very large.

  • Comparison across communication periods: VRL-SGD converges as fast as S-SGD, while Local SGD and EASGD converge more slowly in the tested setting.The passage notes that Local SGD requires smaller periods, such as k = 2 or k = 5, to improve convergence.
  • Effect of larger k: With larger k, VRL-SGD is affected by much larger communication periods but remains faster than Local SGD and EASGD.This observation is reported as consistent with the theoretical analysis.
  • Figure 5 settings: k = 10 for LeNet, k = 25 for TextCNN, and k = 10 for Transfer Learning in Figure 5.
  • Figure 6 settings: k = 40 for LeNet, k = 100 for TextCNN, and k = 40 for Transfer Learning in Figure 6.
Loading 1912.12844v1…