PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep learning with Elastic Averaging SGD

Sixin Zhang, Anna Choromanska, Yann LeCun

arXiv:1412.6651v8cs.LGstat.ML

TL;DR

The paper studies how to parallelize stochastic deep-learning optimization under parameter-communication constraints. It introduces elastic averaging variants that couple local workers to a master center, and reports improved training performance with reduced communication, alongside stability analysis and a stated scope limitation.

  • Problem

    Parallel SGD for large deep-learning models must achieve significant multi-GPU speedup under communication constraints, while many local optima make the setting non-trivial.

  • Method

    EASGD couples each worker’s local parameters to a master-held center through an elastic force, with synchronous, asynchronous, and momentum-based variants.

  • Results

    Experiments report improved test error and faster training than DOWNPOUR and other baselines, while reducing communication overhead; stability is analyzed for asynchronous EASGD and ADMM.

  • Takeaways & Limitations

    Allowing more local exploration through weaker coupling can improve deep-learning performance, while asynchronous EASGD remains stable under a simple stated condition.

  • Takeaways & Limitations

    The formulation assumes every worker can sample the entire dataset, and synchronous EASGD convergence analysis is deferred to the Supplement.

Abstract

from arXiv · show

We study the problem of stochastic optimization for deep learning in the parallel computing environment under communication constraints. A new algorithm is proposed in this setting where the communication and coordination of work among concurrent processes (local workers), is based on an elastic force which links the parameters they compute with a center variable stored by the parameter server (master). The algorithm enables the local workers to perform more exploration, i.e. the algorithm allows the local variables to fluctuate further from the center variable by reducing the amount of communication between local workers and the master. We empirically demonstrate that in the deep learning setting, due to the existence of many local optima, allowing more exploration can lead to the improved performance. We propose synchronous and asynchronous variants of the new algorithm. We provide the stability analysis of the asynchronous variant in the round-robin scheme and compare it with the more common parallelized method ADMM. We show that the stability of EASGD is guaranteed when a simple stability condition is satisfied, which is not the case for ADMM. We additionally propose the momentum-based version of our algorithm that can be applied in both synchronous and asynchronous settings. Asynchronous variant of the algorithm is applied to train convolutional neural networks for image classification on the CIFAR and ImageNet datasets. Experiments demonstrate that the new algorithm accelerates the training of deep architectures compared to DOWNPOUR and other common baseline approaches and furthermore is very communication efficient.

1 Introduction

The paper addresses parallel SGD for large deep-learning models on multiple GPUs, introducing EASGD to accelerate training while reducing communication overhead and maintaining test-error quality.

  • Parallelizing SGD for large-scale deep-learning models across multiple GPUs remains a major challenge because practical systems often use only a few GPU cards.The goal is significant speedup when training large convolutional neural networks.
  • EASGD links each worker’s local parameters to a master-held center variable through an elastic force.The center variable is updated by averaging parameters across time and workers.
  • EASGD provides fast-convergent minimization while outperforming DOWNPOUR and other baseline approaches in practice.
  • The method reduces communication overhead while maintaining high-quality performance measured by test error.It applies to parallelized convolutional-neural-network training.

2 Problem setting

The paper formulates stochastic optimization with multiple workers and a master, using local variables coupled to a center variable through a quadratic penalty. It targets parameter communication overhead while assuming workers can sample the entire dataset.

  • The optimization problem minimizes an expected stochastic loss F(x) in a parallel environment with p workers and a master.The model parameter is x, and the stochastic variable ξ follows distribution P.
  • Each worker has a local variable x_i, while the master stores a center variable x̃.The reformulated objective introduces local-worker variables alongside the center variable.
  • A quadratic penalty term ρ discourages local workers from falling into attractors far from the center variable.
  • The setting focuses on reducing parameter communication overhead, not data communication when data are distributed among workers.The paper assumes each worker can sample the entire dataset.
  • The communication-constrained setting remains non-trivial because the optimization landscape contains many local optima.

3 EASGD update rule

EASGD updates local workers and a master-held center through elastic coupling, with synchronous, asynchronous, and momentum-based variants. Its parameters control communication, exploration, exploitation, and update symmetry.

  • EASGD updates are obtained by taking gradient-descent steps with respect to each local variable x_i and the center variable x̃.The stochastic gradient is evaluated at each iteration using learning rate η.
  • The center update is a moving average over worker parameters in both space and time, with α = ηρ and β = pα.
  • Choosing β = pα creates elastic symmetry by applying an equal force α(x_i − x̃) to local and center updates.The symmetry influences algorithm stability.
  • Smaller ρ allows local variables to fluctuate farther from the center, giving workers more exploration while the master performs exploitation.
  • 3.1 Asynchronous EASGD: Asynchronous EASGD lets workers communicate after τ local gradient steps, making τ the communication period.Workers request the current center, compute an elastic difference, and send it to the master for updating.
  • 3.2 Momentum EASGD: EAMSGD replaces the local update with a Nesterov-momentum variant, and δ = 0 recovers original EASGD.
  • Experiments examine asynchronous EASGD and EAMSGD with relatively large τ to reduce communication overhead.

4 Stability analysis of EASGD and ADMM in the round-robin scheme

The round-robin analysis finds a simple stability condition for EASGD, while ADMM can become chaotic and its analytic stability condition remains unknown.

  • Round-robin scheme: The section analyzes asynchronous EASGD and ADMM in the round-robin scheme, where workers update sequentially and the master follows each activated worker.Each local worker is periodically updated, with the master using the latest local variables and multipliers in ADMM.
  • ADMM stability: ADMM can exhibit chaotic behavior and exponential divergence, whereas its analytic stability condition is still unknown.The comparison is made in the one-dimensional quadratic case without noise.
  • ADMM stability: ADMM updates compose linear maps whose overall composition can become unstable even when individual maps are stable.Some eigenvalues of the composite map can lie outside the unit circle, causing instability.
  • ADMM stability: The round-robin ADMM analysis evaluates its largest absolute eigenvalue numerically for p = 3 and p = 8.Figure 1 summarizes the resulting stability behavior as a function of η and ρ.
  • EASGD stability: EASGD composes symmetric linear maps, so stability of the composite map uses the same condition for every worker and does not depend on p.This follows from the symmetry induced by the elastic updates.
  • EASGD stability: For the EASGD eigenvalues, stability requires 0 ≤ η ≤ 2 and 0 ≤ α ≤ 4−2η.The condition is obtained by requiring the eigenvalue magnitudes to remain at most one.

5 Experiments

Experiments compare EASGD and EAMSGD with parallel and sequential baselines on CIFAR and ImageNet convolutional-network classification. The studies vary communication periods and worker counts while measuring loss and test error over wallclock time.

  • Methods and setup: Experiments compare EASGD and EAMSGD with DOWNPOUR, its variants, SGD, and their averaging and momentum variants.The evaluation includes both parallel and sequential comparator methods.
  • Methods and setup: The evaluation uses CIFAR-10 and ImageNet image classification with deep convolutional neural networks.These are the two benchmark datasets used in the experiments.
  • Methods and setup: The experiments run on a GPU cluster with four Titan GPUs per node, assigning one local worker to each GPU.The master’s center variable is stored and updated on a centralized parameter server.
  • CIFAR experiments: For CIFAR, communication periods τ = {1, 4, 16, 64} are examined with p = 4 local workers, using β = 0.98 for EASGD.The methods use the same initial parameter, while learning-rate ranges are explored for each communication period.
  • Worker-count experiments: For CIFAR, larger worker counts reduce the lowest achievable test error of EASGD or EAMSGD, potentially because more workers permit greater parameter-space exploration.The worker-count study uses p = {4, 8, 16} for CIFAR and p = {4, 8} for ImageNet.

6 Conclusion

The conclusion presents EASGD and its variants as stable, communication-constrained methods for parallel deep-network training, with experiments showing faster improvement than common baselines and reduced communication overhead.

  • Conclusion: EASGD and its variants target stochastic deep-neural-network training parallelized across multiple GPUs.The method is designed for the stochastic setting with parallel computation.
  • Conclusion: Experiments show quicker test-error improvement than common baselines such as DOWNPOUR and its variants.The conclusion also reports a stability advantage under communication constraints.
  • Conclusion: The paper provides round-robin stability analysis for asynchronous EASGD and a theoretical comparison with ADMM.It also introduces synchronous, asynchronous, and momentum-based variants.
  • Conclusion: EASGD reduces communication overhead while maintaining high-quality performance measured by test error.The approach is applied to parallelized convolutional-neural-network training.

7 Additional theoretical results and proofs

Theoretical analysis characterizes EASGD’s stability and mean-squared error in quadratic, multidimensional, and strongly convex settings. Under the stated conditions, increasing workers reduces asymptotic error, while the double-averaging sequence attains optimal asymptotic variance.

  • 7.1 Quadratic case: The center variable is stable when the eigenvalue conditions satisfy −1 < φ < γ < 1.For the quadratic analysis, these quantities are roots of a second-order polynomial determined by the learning rate and elastic coupling.
  • 7.1.1 Visualizing Lemma 7.1: Figure 5 shows substantial variance reduction as p increases, with reduced sensitivity to β and η at large p.The visualization uses theoretical MSE over learning rate, moving rate, processor count, and time; dark red denotes divergence.
  • 7.1.1 Visualizing Lemma 7.1: Increasing the number of workers reduces the EASGD center’s asymptotic MSE, which is of order 1/p.For fixed β, smaller β also decreases the MSE while allowing more exploration.
  • 7.2 Generalization to multidimensional case: The normalized double-averaging sequence converges weakly to a normal distribution with variance σ2/ph2 in one dimension.This asymptotic variance is described as optimal for fixed stable η and β.
  • 7.2 Generalization to multidimensional case: In multiple dimensions, weak convergence holds under η > 0, β > 0 and sufficient stability inequalities involving the largest eigenvalue h of A.The limiting covariance is V = A−1Σ(A−1)T.

8 Additional pseudo-codes of the algorithms

The additional pseudocode specifies worker and master procedures for DOWNPOUR and momentum DOWNPOUR, including initialization, communication, gradient computation, and momentum handling.

  • DOWNPOUR: DOWNPOUR initializes the center, local variables, velocities, and worker counters before repeating its processing loop.Its inputs include the learning rate η and communication period τ.
  • Momentum DOWNPOUR: Momentum DOWNPOUR separates worker and master procedures, with workers receiving the center, computing gradients, and sending them to the master.The worker pseudocode uses learning rate η and momentum term δ as inputs to the overall algorithm.
  • Momentum DOWNPOUR: The momentum DOWNPOUR master procedure is specified separately from worker behavior and initializes the center and worker velocities.The master pseudocode’s inputs include η and δ.

9 Experiments - additional material

The experiments use CIFAR and ImageNet image-classification setups with random crops, horizontal flips, and mini-batches of 128. Learning-rate ranges were explored consistently across methods and communication or worker settings.

  • ImageNet preprocessing: ImageNet inputs are resized so their smallest dimension is 256 pixels, rescaled to [0, 1], and randomly cropped to 3 × 221 × 221.
  • Shared preprocessing: Both datasets use horizontal flips and mini-batches of size 128 during training.
  • CIFAR preprocessing: CIFAR inputs are 3 × 32 × 32 RGB images, rescaled to [0, 1] and randomly cropped to 3 × 28 × 28.
  • Evaluation: Training and test metrics are computed from the center crop for both CIFAR and ImageNet experiments.
  • Learning-rate search: The experiments explored the same learning-rate set across methods for each communication period or worker count.
  • Learning-rate search: Tables 1–3 report learning rates explored for methods evaluated in the CIFAR and ImageNet figures.

9.4 Comparison of SGD, ASGD, MVASGD and MSGD

The single-worker comparisons evaluate convergence of training loss, test loss, and test error over wall-clock time on CIFAR and ImageNet. The learning-rate study further contrasts EAMSGD and EASGD under identical worker and communication settings.

  • Single-worker convergence: Figures 6 and 7 track training loss, test loss, and test error for SGD, ASGD, MVASGD, and MSGD over wall-clock time.The comparisons use the center variable on CIFAR and ImageNet experiments.
  • Single-worker convergence: The single-worker comparisons use p = 1 for SGD, ASGD, MVASGD, and MSGD.
  • Averaging protocol: For CIFAR, averaging for ADOWNPOUR and ASGD starts at the beginning of each experiment.
  • Averaging protocol: For ImageNet, ASGD averaging starts when the initial learning rate is first reduced.
  • Learning-rate dependence: With p = 16 and τ = 10 on CIFAR, higher η improves EAMSGD test performance but hurts EASGD performance through overfitting.
  • Learning-rate dependence: For both EASGD and EAMSGD, the learning rate giving the best training performance also gives the worst test performance.

9.6 Dependence of the communication period

The communication-period experiments compare EASGD and EAMSGD with different τ values and examine runtime breakdowns and wall-clock achievement of target test errors. EASGD remains similar across a wide τ range, while EAMSGD can worsen at large τ.

  • Communication period: EASGD shows very similar convergence for communication periods from τ = 1 through τ = 1000 on CIFAR.
  • Communication period: EAMSGD can become trapped at a worse loss level for τ = 100 on CIFAR, likely because of objective non-convexity.
  • Communication period: Gradually decreasing the learning rate is reported as a way to avoid the worse-loss behavior observed for EAMSGD at large τ.
  • Reproducibility: The runtime comparison was rerun three times with a new random seed and a faster cuDNN package.
  • Runtime breakdown: Table 4 breaks runtime into computation, data loading, and parameter communication for DOWNPOUR with τ = 1 and EASGD with τ = 10.
  • Wall-clock comparison: Figures 10 and 11 plot wall-clock time to reach target test errors against the number of local workers p for CIFAR and ImageNet.The CIFAR thresholds are 21%, 20%, 19%, and 18%; ImageNet thresholds are 49%, 47%, 45%, and 43%.
Loading 1412.6651v8…