# Scaling the Wild: Decentralizing Hogwild!-style Shared-memory SGD

Bapi Chatterjee
Department of Computer Science & Engineering
IIIT-Delhi, New Delhi, India
<EMAIL_ADDRESS>
&Vyacheslav Kungurtsev
Department of Computer Science
Czech Technical University in Prague
<EMAIL_ADDRESS>
Dan Alistarh
Institute of Science and Technology
Austria
<EMAIL_ADDRESS>

###### Abstract

Powered by the simplicity of lock-free asynchrony, Hogwilld! is a go-to
approach to parallelize SGD over a shared-memory setting. Despite its
popularity and concomitant extensions, such as PASSM+ wherein concurrent
processes update a shared model with partitioned gradients, scaling it to
decentralized workers has surprisingly been relatively unexplored. To our
knowledge, there is no convergence theory of such methods, nor systematic
numerical comparisons evaluating speed-up.

In this paper, we propose an algorithm incorporating decentralized distributed
memory computing architecture with each node running multiprocessing parallel
shared-memory SGD itself. Our scheme is based on the following algorithmic
tools and features: (a) asynchronous local gradient updates on the shared-
memory of workers, (b) partial backpropagation, and (c) non-blocking in-place
averaging of the local models. We prove that our method guarantees ergodic
convergence rates for non-convex objectives. On the practical side, we show
that the proposed method exhibits improved throughput and competitive accuracy
for standard image classification benchmarks on the CIFAR-10, CIFAR-100, and
Imagenet datasets. Our code is available at https://github.com/bapi/LPP-SGD.

##  1 Introduction

Stochastic gradient descent (Sgd) is described as

$x_{k+1}=x_{k}-\alpha_{k}\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554ptf(x_{k}),$
(1)

where after $k$ iterations, $x_{k}$ is the estimate of the solution to the
optimization problem: $\min_{x\in\mathbb{R}^{d}}f(x)$, $\alpha_{k}$ is step-
size, and
$\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554ptf(x_{k})$
is a random variable such that
${\mathbb{E}}[\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554ptf(x_{k})]=\nabla
f(x_{k})$. In machine learning applications, empirical loss
$f(x):\mathbb{R}^{d}\rightarrow\mathbb{R}$ of a model $x\in\mathbb{R}^{d}$
over a training set ${\mathcal{S}}$ is minimized using Sgd. Commonly, we
sample a (mini) batch $B_{k}\subseteq\mathcal{S}$ i.i.d. to compute
$\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554ptf(x_{k})=\nabla
f(x_{k},B_{k})$.

As the size of training set ${\mathcal{S}}$ grows, adapting Sgd to distributed
– centralized shared-memory-based and decentralized message-passing-based –
systems becomes imperative.

In a shared-memory setting, Hogwild! [Recht et al., 2011] is now a celebrated
approach, wherein multiple concurrent processes (or threads) asynchronously
compute
$\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554ptf(x_{k})$
to update a shared model $x\in\mathbb{R}^{d}$ without any lock. Subsequently,
Hogwild! saw developments such as Buckwild! [Sa et al., 2015], which uses
lower precision arithmetic. Recently, Kungurtsev et al. [2021] presented
PASSM$+$, which showed that on the shared-memory of a GPU, partial
backpropagation with respect to (w.r.t.) blocks of a convolutional neural
network (CNN) by concurrent processes can provably reduce the total training
cost while offering a surprisingly competitive optimization result. However,
none of these methods can scale beyond a single CPU or GPU.

In a decentralized setting, arguably, the most popular distributed SGD variant
is minibatch data-parallel SGD (Mb-sgd) [Bottou, 2012, Dean et al., 2012],
described as

$x_{k+1}=x_{k}-\alpha_{k}\frac{1}{|\mathcal{Q}|}\sum_{q\in\mathcal{Q}}\nabla
f(x_{k},B^{q}_{k}).$ (2)

Essentially, ${\mathcal{S}}$ is distributed over a set of workers/GPUs
$\mathcal{Q}$, thereby $B^{q}_{k}\subseteq\mathcal{S}$ is sampled locally by a
worker $q\in\mathcal{Q}$ at iteration $k$, thus
$\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554ptf(x_{k})=\frac{1}{|\mathcal{Q}|}\sum_{q\in\mathcal{Q}}\nabla
f(x_{k},B^{q}_{k})$. There has been a significant interest in Mb-sgd-based
deep neural network training with increasingly large number of GPUs, e.g.
Goyal et al. [2017], Akiba et al. [2017], You et al. [2017a], Mikami et al.
[2018], etc.

Though a simple scheme to scale with the number of GPUs, Mb-sgd consistently
communicates gradients after each computation step, thus incurring a high
communication and synchronization cost. An alternative approach is parallel or
local SGD (L-sgd) [Zinkevich et al., 2010, Zhang et al., 2016c], wherein
workers run SGD without any communication for several local steps, after which
they globally _average_ the resulting local models. Clearly, L-sgd reduces the
communication cost by reducing its frequency. Other techniques such as
qunatization [Alistarh et al., 2017] and sparsification [Stich et al., 2018],
applied to message-passing distributed Sgd, primarily address the high cost of
communication. Recently, these methods also have been combined with L-sgd such
as Basu et al. [2019], Koloskova et al. [2020]. Nonetheless, beyond using
larger mini-batches, none of them can scale the training locally on GPUs
though the contemporary GPUs efficiently host multiprocessing and thus
Hogwild! [MPS, 2020, Kungurtsev et al., 2021].

A major motivation for decentralizing Hogwild!-style approaches in a multi-GPU
setting is that models trained by large batch regimes generally have poor
quality. It was investigated by Keskar et al. [2019], who described this
behaviour in terms of sharpness of minima correlating the minibatch-size,
which degrades generalization. Our experiments also highlight this fact, see
Table 1. Leveraging multiple processes locally on each GPU can keep the batch-
size small.

To our knowledge, only attempt to decentralize Hogwild! was made by Hogwild!++
[Zhang et al., 2016a] – run Hogwild! locally on each CPU of a non-uniform-
memory-access (NUMA) machine and synchronize by averaging on a ring-graph
topology. Taking advantage of cache-locality, Hogwild!++ exhibited improved
throughput over Hogwild! for training a number of convex models. However,
Hogwild!++ does not have a convergence theory and no further development to
this approach is known.

In this paper, we describe the locally-partitioned-asynchronous parallel SGD
(Lpp-sgd), a new method that employs the following techniques:

  1. 1.

The model on each worker is shared by multiple processes that perform lock-
free partitioned gradient updates computed by partial backpropagation, thereby
reduces the total gradient computation cost.

  2. 2.

Dedicated processes on each worker concurrently perform the model averaging,
which is in-place, non-blocking, and overlaps the gradient computations – it
significantly reduces the cost of synchronization.

Method |  $U$ |  $B_{loc}$ |  Train Loss |  Train Acc. |  Test Loss |  Test Acc. |  Time (Sec) |  Speed-up
---|---|---|---|---|---|---|---|---
Mb-sgd |  1 |  128 |  0.016 |  99.75 |  0.234 |  92.95 |  1754 |  1.0x
Mb-sgd |  1 |  1024 |  0.023 |  99.51 |  0.293 |  91.38 |  1201 |  1.46x
Pl-sgd |  1 |  128 |  0.018 |  99.69 |  0.245 |  92.98 |  1603 |  1.09x
Pl-sgd |  1 |  1024 |  0.154 |  94.69 |  0.381 |  87.81 |  1159 |  1.51x
Lap-sgd |  4 |  128 |  0.012 |  99.83 |  0.270 |  92.92 |  1304 |  1.35x
Lap-sgd |  6 |  128 |  0.023 |  99.51 |  0.266 |  92.91 |  1281 |  1.37x
Lap-sgd |  4 |  256 |  0.010 |  99.90 |  0.280 |  92.93 |  1219 |  1.44x
Lpp-sgd |  4 |  128 |  0.019 |  99.62 |  0.270 |  92.98 |  1153 |  1.52x
Lpp-sgd |  6 |  128 |  0.021 |  99.58 |  0.262 |  92.84 |  1085 |  1.62x
Lpp-sgd |  4 |  256 |  0.019 |  99.65 |  0.267 |  92.95 |  1047 |  1.68x
Table 1: ResNet-20/Cifar-10 training for 300 epochs on 2 Nvidia GeForce RTX
2080 Ti GPUs. $U$ indicates the number of concurrent gradient updater
processes on each GPU. Throughout the training the local batch size is kept
identical across workers. In each case, the LR is warmed up for the first 5
epochs to scale from $\alpha_{0}$ to
$\alpha_{0}\times\frac{B_{loc}{\times}Q}{B_{loc{\mathchar 45\relax}base}}$,
where $B_{loc{\mathchar 45\relax}base}=128$, the number of workers $Q=2$ and
$\alpha_{0}=0.1$. In Pl-sgd, Lap-sgd, and Lpp-sgd, we average the model after
each gradient update for the first 150 epochs and thereafter averaging
frequency is set to 16 as in Lin et al. [2020]; other hyperparameters are
identical to theirs. The listed results are average of 3 runs with different
seeds.

In the case of full (non-partitioned) gradient update by each process to the
model throughout the training, we call it locally-asynchronous parallel SGD
(Lap-sgd). Essentially, Lap-sgd and Lpp-sgd decentralize Hogwild! and
PASSM$+$, respectively.

A key contribution of the presented work is the convergence theory – under the
standard assumptions, we prove that Lap-sgd and Lpp-sgd ergodically converge
with standard sublinear rate for non-convex objectives.

Experimental results in Table 1 give a glimpse of the efficacy of our
algorithms. In the experiemnts, we have included post local SGD (Pl-sgd),
which is a modified version of L-sgd by Lin et al. [2020]. Pl-sgd synchronizes
the distributed models more frequently during the initial phase of training to
address the issue of poor generalization of L-sgd.

Our focus in this work is on showcasing the strength of combination of shared-
memory and message-passing asynchrony for distributed SGD. Our method can be
easily extended to incorporate techniques such as lower precision arithmetic,
quantized and sparsified communication, etc.

##  2 System and Optimization Model

Notation |  Description
---|---
$\mathcal{Q}$, $Q$ |  Set of workers (GPUs), Number of workers.
$x^{q}$ |  Local shared model on worker $q\in\mathcal{Q}$.
$u^{q}$ |  A gradient updater process on worker $q\in\mathcal{Q}$.
$U^{q}$, $U$ |  Set of updater processes on $q$, Number thereof.
$a^{q}$, $P^{q}$ |  Averaging process on worker $q$, $\\{\\{a^{q}\\}\cup U^{q}\\}$.
$x^{q}_{i}$ |  $i^{th}$ block of the model (vector) $x^{q}$, where $i\in\mathcal{I}$.
$\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f$ |  Stochastic gradient of $f$ w.r.t. $i^{th}$ block.
$x^{q}[e]$ |  $e^{th}$ index of the local model (vector) $x^{q}$.
$x^{q}[a,b]$ |  Partition of $x^{q}$ from its $a^{th}$ to $b^{th}$ index.
$\mathcal{C}^{q}$ |  Shared iteration counter on worker $q\in\mathcal{Q}$.
Table 2:  Frequently used notations.

We consider a $d$-dimensional differentiable empirical risk function
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ and a finite training dataset
$\mathcal{S}$ as described before. We aim to iteratively converge at a state
$x^{*}$ of the model $x\in\mathbb{R}^{d}$ such that
$x^{*}\in\arg\min_{x\in\mathbb{R}^{d}}f(x)$.

We consider a set of workers $\mathcal{Q}$ distributed over a complete graph
structured network. We denote the number of workers as $Q=|\mathcal{Q}|$ and
assume that $Q\geq 2$. A worker $q\in\mathcal{Q}$ maintains a local estimate
$x^{q}$ of the model $x$. At initialization,
$x^{q}=x^{q^{\prime}}\leavevmode\nobreak\ \forall q,q^{\prime}\in\mathcal{Q}$.
We form, possibly overlapping, blocks of $x^{q}$ as
$x^{q}:=\cup_{i\in\mathcal{I}}x^{q}_{i}$, where $\mathcal{I}$ is a finite
index set.

A worker $q\in\mathcal{Q}$ spawns a set of concurrent updater processes
$U^{q}=\\{u^{q}\\}$ and a designated averaging process $a^{q}$. For
simplicity, $|U^{q}|=|U^{q^{\prime}}|=U\leavevmode\nobreak\
\forall\leavevmode\nobreak\ q,q^{\prime}\in\mathcal{Q}$. On each
$q\in\mathcal{Q}$, $x^{q}$ allows shared read/write access to the set of
concurrent processes $P^{q}=\\{\\{a^{q}\\}\cup U^{q}\\}$. We assume that each
of $u^{q}\in U^{q}$ on each of $q\in\mathcal{Q}$ have access to the entire
training dataset $\mathcal{S}$. Thereby, a $u^{q}\in U^{q}$ can compute a
minibatch stochastic gradient with respect to a block of parameters by
sampling a subset $B^{q}\subseteq\mathcal{S}$ typically selected i.i.d. by a
distribution $\mathcal{D}$ as
$\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(x^{q}):=\nabla_{x^{q}_{i}}f(x^{q},B^{q})$.
Thus,

$\begin{array}[]{l}\mathbb{E}_{\mathcal{D}}[\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(x)]=\nabla_{x^{q}_{i}}f(x),\end{array}$
(3)

The processes $p^{q}\in P^{q}$ maintain a shared iteration counter
$\mathcal{C}^{q}$, initialized to zero. The operation read&inc atomically
increments $\mathcal{C}^{q}$ and returns its value that was read before
incrementing. The operation read provides an atomic read. $\mathcal{C}^{q}$
essentially enables ordering the shared gradient updates, which determines the
averaging rounds $j$. Finally, we have the following standard assumptions on
$f$:

Lower bound.

$f(x)\geq f_{m}\leavevmode\nobreak\ \forall\leavevmode\nobreak\
x\in\mathbb{R}^{d}.$ (4)

$L$-Lipschitz Smoothness.

$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|\leavevmode\nobreak\
\forall\leavevmode\nobreak\ x,y\in\mathbb{R}^{d}.$ (5)

Bounded second moment.

$\mathbb{E}_{\mathcal{D}}[\|\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(x)\|^{2}]\leq
M^{2}\leavevmode\nobreak\ \forall\leavevmode\nobreak\ x\in\mathbb{R}^{d}.$ (6)

Bounded variance.

$\mathbb{E}_{\mathcal{D}}[\|\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(x)-\nabla_{i}f(x)\|^{2}]\leq\sigma^{2}\leavevmode\nobreak\
\forall\leavevmode\nobreak\ x\in\mathbb{R}^{d}.$ (7)

The bounded second moment assumption (6) is needed for Hogwild!-style updates,
see Nadiradze et al. [2021a].

##  3 Algorithm

Given: model $x\in\mathbb{R}^{d}$, training set $\mathcal{S}$, and sample
processing budget $T$ minibatches of size $B_{loc}$.

Steps of an updater process $u^{q}$:

Initialize $s=0$;

// Process-Local counter.

1 while  _$s\leq T$_ do

2 Read and increment the shared counter $\mathcal{C}^{q}$:
$s:=\texttt{read\&inc}(\mathcal{C}^{q})$;

3 Lock-free collect a snapshot $v^{q,s}$ of $x^{q}$:
$v^{q,s}[e]:=\texttt{read}(x^{q}[e])$, $\forall\leavevmode\nobreak\ 1\leq
e\leq d$;

4 Select a block $v^{q,s}_{i}$ following the Block Selection Rule and sample a
minibatch $B^{q}_{s}\subset\mathcal{S}$;

5 Use $B^{q}_{s}$ to compute a partial minibatch stochastic gradient w.r.t.
the block $v^{q,s}_{i}$:
$\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v^{q,s})$;

6 Lock-free update the model block $x^{q}_{i}$:
$x^{q}_{i}[e]\leavevmode\nobreak\ \mathrel{{-}{=}}\leavevmode\nobreak\
\alpha_{s}\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v^{q,s})[e]$,
$\forall\leavevmode\nobreak\ 1\leq e\leq length(v^{q,s}_{i})$;

7

Steps of the averaging process $a^{q}$:

Initialize $s_{cur}=s_{pre}=0$;

// Iteration counters to track updates in the model based on the shared
counter $\mathcal{C}^{q}$ and decide whether to synchronize.

Initialize $j=0$;

// Averaging round counter.

8 while  _$s_{cur}\leq T$_ do

9 Read the current value of the shared counter:
$s_{cur}:=\texttt{read}(\mathcal{C}^{q})$;

10 Compute $K_{j}$ corresponding to $s_{cur}$ following the Synchronization
Frequency Scheme;

11 if  _$s_{cur}-s_{pre}\geq K_{j}$_ then

12 Update counters: $s_{pre}:=s_{cur}$; $j:=j+1$;

13 Collect a lock-free snapshot $v^{q,j}$ of $x^{q}$:
$v^{q,j}[e]:=\texttt{read}(x^{q}[e])$, $\forall\leavevmode\nobreak\ 1\leq
e\leq d$ ;

14 Synchronize across the peers in $\mathcal{Q}$ to compute all-reduced-
average $\overline{v}_{j}:=\frac{1}{Q}\sum_{q\in\mathcal{Q}}v^{q,j}$;

15 Compute $\Delta v^{q,j}=\overline{v}_{j}-v^{q,j}$;

16 In-place lock-free update: $x^{q}[e]\leavevmode\nobreak\
\mathrel{{+}{=}}\leavevmode\nobreak\ \Delta v^{q}[e]$,
$\forall\leavevmode\nobreak\ 1\leq e\leq d$;

17

18

Algorithm 1 Steps of Lpp-sgd on a $q\in\mathcal{Q}$.

We describe Lpp-sgd in Algorithm 1, of which Lap-sgd is a special case. For
simplicity, the steps taken by individual processes are given as sequential
pseudocode, however, by implementation, each $a^{q},u^{q}\in P^{q}$ work
concurrently over the same address space associated with a worker
$q\in\mathcal{Q}$, and all $q\in\mathcal{Q}$ run in parallel.

#### Block partitions.

Considering a model implemented as an ordered list of tensors, a block is
essentially a sub-list of successively ordered tensors. More formally,
consider a local model estimate $x^{q}\in\mathbb{R}^{d}$ and a set of positive
integers $\\{b_{0},b_{1},\ldots,b_{U}\\}$ s.t. $b_{0}=0,\leavevmode\nobreak\
b_{U}=d\text{ and }\sum_{i=1}^{U}(b_{i}-b_{i-1})=d$. We form the blocks
$\\{x^{q}_{i}\\}_{i\in\mathcal{I}}$ ranked by the index set
$\mathcal{I}=\\{0,1,\ldots,U\\}$ s.t. $x^{q}:=\cup_{i\in\mathcal{I}}x^{q}_{i}$
as the following:

$\displaystyle x^{q}_{i}$
$\displaystyle:=\left\\{\begin{array}[]{lr}x^{q}[1,d],&\leavevmode\nobreak\
\text{if}\leavevmode\nobreak\ i=0,\\\
x^{q}[b_{i-1}+1,b_{i}],&\leavevmode\nobreak\ \text{if}\leavevmode\nobreak\
i>0.\end{array}\right.$ (10)

Essentially, block $x^{q}_{0}$ represents the entire model vector $x^{q}$
whereas other blocks form disjoint partitions of $x^{q}$.

For a CNN model, $x^{q}$ represents list of its layers (tensors). We partition
it into blocks $\\{x^{q}_{1},\ldots,x^{q}_{U}\\}$ of lengths
$\\{b_{i}-b_{i-1}\\}_{i=1}^{U}$. The choice of the integers $b_{i}$s are such
that the aggregated cost of concurrent partial backpropagation starting from
the output layer to these blocks could be minimized [Kungurtsev et al., 2021].

#### Block Selection Rule.

In Lap-sgd, each $u^{q}\in U^{q}$ selects $x^{q}_{0}$, i.e. full model,
throughout the training. In Lpp-sgd as well, during the initial phase of
training, say, while $s\leq T_{st}$ for $s$ read at line 1 in Algorithm 1,
each $u^{q}$ selects the full model $x^{q}_{0}$. After that, in alternate
iterations, select the full model $x^{q}_{0}$ and the block
$x^{q}_{rank(u^{q})}$: $rank(u^{q})\in\\{1,\ldots,U\\}$.

#### Discussion on the Rule.

As described in Kungurtsev et al. [2021], we have total potential savings of
$F\frac{(c-1)}{2}$ floating point operations (flops) in $c$ concurrent partial
gradient computation steps by $c$ processes, where $F$ flops is the cost of
full gradient computation. Kungurtsev et al. [2021] also showed that partial
gradient updates throughout the training causes poor optimization results. We
observed that at line 3 Algorithm 1 by selecting $s\leq T/10$ roughly, it
consistently resulted in the desired optimization quality. Thus, for about
$9T/20$ iterations we perform partial gradient computation.

#### Synchronization Frequency Scheme.

Our approach to fix the synchronization frequency $K_{j}$ is similar to that
of post local SGD [Lin et al., 2020]: $K_{j}=1$ until $T/2$ minibatches are
processed, i.e. until $s_{cur}$ reads up to $T/2$ at line 1 in Algorithm 1,
where $T$ is the total number of minibatches to be processed; thereafter we
increase $K_{j}$ to $H>1$. Typically, we choose $H=8,\leavevmode\nobreak\ 16$,
etc.

##  4 Experiments

In this section, we present experimental evaluation of Lap-sgd and Lpp-sgd
against Mb-sgd and Pl-sgd schemes.

Distributed training. We use CNN models ResNet-20 [He et al., 2016],
SqueezeNet [Iandola et al., 2017], and WideResNet-16x8 [Zagoruyko and
Komodakis, 2016] for the 10-/100-class image classification tasks on datasets
Cifar-10/Cifar-100 [Krizhevsky, 2009]. We also train ResNet-50 for a
1000-class classification problem on the Imagenet [Russakovsky et al., 2015]
dataset. We keep the sample processing budget identical across the methods
i.e. the training procedure terminates on performing an equal number of epochs
(full pass) on the training set. Our data sampling is i.i.d. – we partition
the sample indices among the workers that can access the entire training set;
the partition indices are reshuffled every epoch following a seeded random
permutation based on epoch-order.

Platform specification. We use the following specific settings: (a) S1: two
Nvidia GeForce RTX 2080 Ti GPUs, (b) S2: four Nvidia GeForce RTX 2080 Ti GPUs,
(c) S3: two S2 settings connected with a 100 GB/s infiniband link, and (d) S4:
eight Nvidia V100 GPUs on a cluster. Other system-related details are given in
the Appendix D.

Implementation framework. We used open-source Pytorch 1.5 Paszke et al. [2017]
library. For cross-GPU/cross-machine communication we use NCCL [NCCL, 2020]
primitives provided by Pytorch. Mb-sgd is based on DistributedDataParallel
Pytorch module. The Pl-sgd implementation is derived from the author’s code
LocalSGD [2020] and adapted to our setting. The autograd package of Pytorch
allows specifying the leaf tensors of the computation graph of the CNN loss
function w.r.t. which gradients are needed. We used this functionality in
implementing partial gradient computation in Lpp-sgd.

Locally-asynchronous Implementation. We use a process on each GPU, working as
a parent, to initialize the CNN model and share it among the spawned child-
processes. The child-processes work as updaters $u^{q}\in U^{q}$ on a GPU
$q\in\mathcal{Q}$ to compute the gradients and update the model. Concurrently,
the parent-process, instead of remaining idle, as it happens commonly with
such designs, acts as the averaging process $a^{q}$, thereby productively
utilizing the entire address space occupied over the GPUs. The parent- and
child-processes share the iteration and epoch counters.

Hyperparameters (HPs). Each of the methods use identical momentum and weight-
decay for a given CNN/dataset case; we rely on their previously used values
[Lin et al., 2020]. The LR schedule for Mb-sgd and Pl-sgd are identical to Lin
et al. [2020]. For the Lpp-sgd and Lap-sgd, we used cosine annealing schedule
without any intermediate restart [Loshchilov and Hutter, 2017]. Following the
well-accepted practice, we warm up the LR for the first 5 epochs starting from
the baseline value used over a single worker training. In some cases, a grid
search [Pontes et al., 2016] suggested that for Lpp-sgd warming up the LR up
to 1.25$\times$ of the warmed-up LR of Lap-sgd for the given case, improves
the results. Additional details are in Appendix.

Experimental Results:
Result tables use these abbreviations: Tr.L.: Training Loss, Tr.A.: Training
Accuracy, Te.L.: Test Loss, Te.A.: Test Accuracy, and $T$: Time in Seconds.
The asynchronous methods have inherent randomization due to process scheduling
by the operation system. Irrespective of that, in each micro-benchmark we take
the mean of 3 runs with different random seeds unless otherwise mentioned.

$U$ |  $B_{loc}$ |  Tr.A. |  Te.A. |  $T$
---|---|---|---|---
4 |  128 |  99.62 |  92.81 |  1304
6 |  128 |  99.85 |  92.92 |  1266
8 |  128 |  99.62 |  92.64 |  1259
4 |  256 |  99.72 |  92.83 |  1219
6 |  256 |  99.90 |  92.24 |  1166
Table 3: Lap-sgd.

$K$ |  $\mathbf{P}$ |  Tr.A. |  Te.A. |  $T$
---|---|---|---|---
1 |  150 |  99.76 |  93.01 |  1266
4 |  150 |  99.85 |  92.78 |  1263
8 |  150 |  99.62 |  93.08 |  1262
8 |  0 |  99.78 |  92.83 |  1263
16 |  150 |  99.90 |  93.16 |  1261
Table 4: Lap-sgd.

Concurrency on GPUs. GPU on-device memory is a constraint. However, once the
data-parallel resources get saturated, allocating more processes degrades the
optimization quality vis-a-vis performance. For instance, as shown in Table 4
– the average performance for different $U$ and $B_{loc}$ for training
ResNet-20/Cifar-10 by Lap-sgd on setting S1– there is apparently no advantage
beyond 6 and 8 concurrent processes with batch-sizes 128 and 256,
respectively.

Method |  $B_{loc}$ |  $U$ |  Tr.L. |  Te.L. |  Tr.A. |  Te.A. |  $T$
---|---|---|---|---|---|---|---
Lap-sgd |  64 |  4 |  0.007 |  1.341 |  99.98 |  75.97 |  1564
Lpp-sgd |  64 |  3 |  0.008 |  1.554 |  99.97 |  75.42 |  1376
Mb-sgd |  128 |  - |  0.007 |  1.348 |  99.97 |  73.29 |  2115
Mb-sgd |  512 |  - |  0.034 |  1.918 |  99.64 |  63.74 |  2076
Pl-sgd |  128 |  - |  0.020 |  1.354 |  99.81 |  72.38 |  2108
Pl-sgd |  512 |  - |  0.393 |  1.758 |  88.91 |  60.47 |  1976
Table 5: WideResNet-16x8 on Cifar-100 over the setting S3. Method |  $B_{loc}$ |  $U$ |  Tr.L. |  Te.L. |  Tr.A. |  Te.A. |  $T$
---|---|---|---|---|---|---|---
Lap-sgd |  128 |  4 |  0.004 |  0.385 |  99.95 |  92.48 |  1251
Lpp-sgd |  256 |  3 |  0.007 |  0.355 |  99.89 |  92.55 |  1027
Mb-sgd |  1024 |  - |  0.003 |  0.325 |  99.97 |  91.50 |  1580
Mb-sgd |  128 |  - |  0.005 |  0.294 |  99.93 |  92.41 |  2243
Pl-sgd |  1024 |  - |  0.005 |  0.329 |  99.93 |  91.99 |  1202
Pl-sgd |  128 |  - |  0.006 |  0.283 |  99.91 |  92.51 |  1843
Table 6: SqueezeNet on Cifar-10 over the setting S1.

Method |  $B_{loc}$ |  $U$ |  |  $\mathbf{Q}$ |  Tr.A. |  Te.A. |  $T$ |  |  $\mathbf{Q}$ |  Tr.A. |  Te.A. |  $T$ |  |  $\mathbf{Q}$ |  Tr.A. |  Te.A. |  $T$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Lap-sgd |  64 |  4 |  (1) |  2 |  100.0 |  94.92 |  6368 |  (7) |  4 |  100.0 |  94.91 |  3092 |  (13) |  8 |  100.0 |  94.69 |  1562
Lpp-sgd |  64 |  3 |  (2) |  2 |  99.97 |  94.89 |  5551 |  (8) |  4 |  99.96 |  94.87 |  2724 |  (14) |  8 |  99.99 |  93.78 |  1377
Mb-sgd |  128 |  - |  (3) |  2 |  100.0 |  93.98 |  8265 |  (9) |  4 |  100.0 |  94.22 |  4045 |  (15) |  8 |  100.0 |  93.83 |  2116
Mb-sgd |  512 |  - |  (4) |  2 |  95.68 |  88.42 |  7920 |  (10) |  4 |  99.87 |  89.46 |  3913 |  (16) |  8 |  87.54 |  73.97 |  2076
Pl-sgd |  128 |  - |  (5) |  2 |  99.99 |  94.21 |  8293 |  (11) |  4 |  99.98 |  94.02 |  4022 |  (17) |  8 |  99.98 |  94.18 |  2105
Pl-sgd |  512 |  - |  (6) |  2 |  95.34 |  88.33 |  7829 |  (12) |  4 |  98.52 |  84.45 |  3784 |  (18) |  8 |  89.19 |  81.80 |  1977
Table 7: WideResNet-16x8/Cifar-10 training in the settings S1: $\mathbf{Q}=2$,
S2: $\mathbf{Q}=4$, and S3: $\mathbf{Q}=8$.

Synchronization Frequency. As mentioned, we follow the strategy introduced by
Pl-sgd of setting $K=1$ for an initial set of iterations followed by
increasing $K$. However, unlike Pl-sgd, intuitively, with our non-blocking
synchronization among GPUs, the increment events on the shared-counter
$\mathcal{C}^{q}$ are “grouped” on the real-time scale if the updater
processes $u^{q}$ do not face delays in scheduling, which we control by
allocating an optimal number of processes to maximally utilize the compute
resources. For instance, Table 4 lists the results of 5 random runs for 300
epochs over setting S1 of ResNet-20/Cifar-10 training with $B_{loc}=128$ and
$U=6$ with different synchronization frequencies $K$. $\mathbf{P}$ denotes the
number of epochs up to which $K$ is necessarily $1$. This micro-benchmark
indicates that the overall latency and the final optimization result of our
method may remain robust under small changes in $K$, which may not necessarily
be the case with Pl-sgd.

Scalability. Table 4 presents the results of WideResNet-16x8/Cifar-10 training
in the settings S1, S2, and S3. We observe that in each setting the relative
performance of different methods are approximately consistent. We observe a
perfect scalability with the number of GPUs. Interestingly, increasing
$B_{loc}$ from 128 to 512 does not improve the latency by more than $\sim$4%
of Mb-sgd and Pl-sgd– this non-linear scalability of data-parallelism was also
observed by Lin et al. [2020]. However, there is clear degradation in
optimization results by larger $B_{loc}$ for Mb-sgd and Pl-sgd. On the other
hand, Lap-sgd and Lpp-sgd not only speeds-up the training but also
consistently improve on the baseline generalization accuracy.

Other Cifar-10/Cifar-100 Results. Performance of the methods on
WideResNet-168/Cifar-100 and SqueezeNet/Cifar-10 for 200 epochs are available
in Tables 5 and 6, respectively. The relative latency of the methods are as
seen in Table 4, whereas, in each case Lpp-sgd recovers or improves the
baseline results.

Method |  $B_{loc}$ |  $U$ |  Tr.L. |  Te.L. |  Tr.A. |  Te.A. |  $T$
---|---|---|---|---|---|---|---
Lap-sgd |  32 |  4 |  0.823 |  77.97 |  1.215 |  76.58 |  54243
Lpp-sgd |  32 |  4 |  0.834 |  77.31 |  1.257 |  76.11 |  48066
Mb-sgd |  128 |  - |  0.809 |  78.63 |  1.220 |  76.07 |  52395
Pl-sgd |  128 |  - |  0.818 |  78.22 |  1.223 |  76.12 |  50402
Table 8: ResNet-50/Imagenet Training results.

Imagenet Training Results. We used the setting S4 for training ResNet-50 on
1000-classes Imagenet dataset. The computational resources of a GPU for
ResNet-50/Imagenet training are almost saturated, which can be seen in higher
latency of Lap-sgd in Table 8. Yet, we observe that Lpp-sgd exhibits improved
performance with competitive generalization accuracy indicating the efficacy
of partial back-propagation.

Method |  $U$ |  $B_{loc}$ |  Tr.A. |  Te.A. |  $T$
---|---|---|---|---|---
Mb-sgd |  1 |  1024 |  95.84 |  85.67 |  1324
Pl-sgd |  1 |  1024 |  93.67 |  84.69 |  1304
Lap-sgd |  4 |  256 |  99.87 |  92.90 |  1232
Lpp-sgd |  4 |  256 |  99.59 |  92.83 |  1071
Table 9: LARS performance.

LR Tuning strategy. It is pertinent to mention that the techniques, such as
LARS [You et al., 2017b], which provide an adaptive LR strategy for large-
batch regimes over many GPUs, with each worker locally processing a small
batch, are insufficient in the case $B_{loc}$ is increased. For example, see
Table 9, which lists the average performance of 5 runs on the setting S1 to
train ResNet-20/Cifar-10 using Mb-sgd and Pl-sgd combined with LARS with
$\eta=0.001$ [You et al., 2017b]. We proportionately scale the LR from
$\alpha_{0}$ to $\alpha_{0}\times\frac{B_{loc}{\times}Q}{B_{loc{\mathchar
45\relax}base}}$, where $B_{loc{\mathchar 45\relax}base}=128$, $Q=2$ and
$\alpha_{0}=0.1$. Evidently, LARS did not help Mb-sgd and Pl-sgd in checking
the poor generalization due to larger $B_{loc}$.

##  5 Convergence Theory

Note that, unlike Lap-sgd or Lpp-sgd, the previous works on Local SGD
analyses, e.g. Zhou and Cong [2017], Stich [2018], Haddadpour et al. [2019],
etc. did not have to consider either lock-free multiple local gradient
updates, or in-place overlapping model updates by averaging. Clearly,
significant challenges arise in our case because (a) the snapshots used for
gradient computations are inconsistent due to the lock-free concurrent
gradient updates, and (b) they also could potentially have been read from the
local shared-memory before the last averaging across workers could take place
– a novel challenge for any analysis.

Nevertheless, we firstly need to fix a sequence of model estimates for
convergence. To this end, we define an abstraction comprising two auxiliary
variables as described below. For simplicity we use a constant LR $\alpha$ in
this discussion.

#### Minor iteration view:

In the local lock-free setting of each worker $q\in\mathcal{Q}$, we follow the
elastic consistency model of Nadiradze et al. [2021a] for shared-memory
asynchronous SGD. Now, because we are working at the level of blocks, we
define the operation $-|_{i}$ to denote subtraction from the $i^{th}$ block.
For example, if $a=\begin{pmatrix}1&2&3&4\end{pmatrix}^{T}$ and
$b=\begin{pmatrix}-10&-20\end{pmatrix}^{T}$, we have that
$a-|_{[2,3]}b=\begin{pmatrix}1&12&23&4\end{pmatrix}^{T}$. With that,
considering worker $q$, the ${t+1}^{st}$ minor iteration view after the
$j^{th}$ averaging round, assuming that the $s^{th}$ ($s$ is a read value of
the shared counter $\mathcal{C}^{q}$) snapshot $v^{q,s}$ was used for partial
stochastic gradient computation is defined by the following iteration:

$\begin{array}[]{l}w_{j,t+1}^{q}:=w_{j,t}^{q}-|_{i}\alpha\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v^{q,s}).\end{array}$
(11)

#### Major iteration view:

Let $K_{j}^{q}$ be the final minor iteration count on worker $q$ before the
$(j{+}1)$st synchronization round, we define the $j^{th}$ major iteration view
as

$\begin{array}[]{l}\bar{x}_{j}:=\frac{1}{Q}\sum_{q=1}^{Q}w_{j,K_{j}^{q}}^{q}.\end{array}$
(12)

This $\bar{x}_{j}$ is the averaged iterate that we take as the reference
sequence in our convergence theory. At initialization,
$\bar{x}_{0}=v^{q,0}\leavevmode\nobreak\ \forall\leavevmode\nobreak\
q\in\mathcal{Q}$. The update rule of $\bar{x}_{j}$ can be written as

$\begin{array}[]{l}\bar{x}_{j+1}=\frac{1}{Q}\sum_{q=1}^{Q}\left[\bar{x}_{j}-|_{i}\alpha\sum_{t=0}^{K_{j}^{q}}\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v^{q,s})\right].\end{array}$
(13)

To streamline these views, we use the following notions:

  1. 1.

The Snapshot Order of a minor iteration view is the value of $\mathcal{C}^{q}$
before the snapshot collection.

  2. 2.

The Update Order of a minor iteration view is defined as the order of the
atomic read steps of the model before starting its update with a local
gradient by a process.

  3. 3.

The Iteration Order of the $t^{th}$ minor iteration after the $j^{th}$ major
iteration is the tuple $(j,t)$.

More detail on these orders are provided in Appendix A. It is pertinent to
mention here that the selection of a block $i\in\mathcal{I}$ depends on the
worker $q$ and the iteration order $(j,t)$. Thus, precisely expressing,
$i\equiv i(q,j,t)$. Table 10 lists out some extra notations that we will be
frequently using in this discussion in addition to those listed out in Table
2.

Notation |  Description
---|---
$w^{q}_{j,t}$, $w_{u}^{q}$, $w^{q,s}$ |  The minor iteration view with iteration order $(j,t)$, with update order $u$, with snapshot order $s$.
$v^{q}_{j,t}$, $v_{j,t}^{q}[e]$ |  Snapshot vector to compute a partial stochastic gradient for the minor iteration $(j,t)$, its $e^{th}$ index.
$\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v^{q}_{j,t})$ |  Stochastic gradient of $f(v^{q}_{j,t})$ w.r.t. its $i(q,j,t)^{th}$ block.
Table 10: Additional frequently used notations.

With these views, in order to obtain a converging sequence of averaged
iterates, we need to place a reasonable bound on the inconsistencies due to
gradient computations for minor iterations using the snapshots that may have
components read before the latest major iteration. To this end, we describe a
stochastic delay model as described below.

Because the read and updates at the level of indexes of the model vector are
atomic, we have the following:

$\begin{array}[]{l}v^{q}_{j,t}[e]\in\cup_{k\in\\{0,1,\ldots,u\\}}\\{w^{q}_{k}[e]\\},\end{array}$
(14)

where $e\in i(q,j,t)$ and $i(q,j,t)\subseteq\\{1,2,\ldots,d\\}$ and $u$ is the
update order of minor iteration $(j,t)$. Essentially, relation (14) captures
the fact that a component of an inconsistent snapshot would belong to a
historical minor iteration view. Notice that, as the lock-free read and
updates of the shared model work at the level of indexes, we have an advantage
of dropping the dependence of the expressions over the blocks
$i\in\mathcal{I}$ in the convergence analysis. We can now define the event
describing relation (14) as the following.

#### Delay Event and Probability.

Define $\mathbb{I}^{q,k,e}_{j,t}$ as the event that
$v^{q}_{j,t}[e]=w^{q}_{k}[e]$, and $p^{q,k,e}_{j,t}$ as its probability, for
some $j\geq 0$, $0\leq t\leq K_{j}^{q}$, and $0\leq k\leq u$, where $u$ is the
update order of minor iteration view $(j,t)$. We call
$\mathbb{I}^{q,k,e}_{j,t}$ a delay event. Notice that, defining this event
captures the possibility that $v^{q}_{j,t}$ could have been collected at a
minor iteration before the synchronization round $j$.

#### Assumptions Governing the Asynchronous Computation.

In the non-convex setting, in general, we can simply hope that the objective
function decrease achieved by local asynchronous SGD update with a gradient
computed after an averaging step outweighs the potential worst-case increase
that might take place due to an update by a gradient computed before the
averaging step. In order to derive an expected decrease in the objective, we
need to bound the probability of an increase, which means bounding the
probability that a component of the snapshot was collected at a minor
iteration older than the previous averaging.

The significant quantity that separates these expected favorable and
unfavorable iterations is,

$\mathbb{P}\left[\cap_{e}\cup_{l\geq k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right],$

where $u$ is the update order of minor iteration $(j,t)$ and $k$ is the update
order of the minor iteration just after the $j^{th}$ synchronization round.
This quantity is _the probability that every component of the inconsistent
snapshots were due to the minor iterations after $a^{q}$ performed averaging_.

######  Assumption 5.1.

For all $(j,t,q)$ it holds that the quantity

$\bar{\mathbf{p}}^{(j,t,q)}:=\mathbb{P}\left[\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]$

satisfies that there exists $p_{0}>0$ such that
$\bar{\mathbf{p}}^{(j,t,q)}>p_{0}$ for all $(j,t,q)$.

Assumption 5.1 implies that an inconsistent snapshot read at line 1 to compute
a partial stochastic gradient does not consist of components updated by minor
iterations too differing in their update orders.

#### Elastic Consistency.

For lock-free local updates, we can make a statement to bound the error in the
sense of Elastic Consistency of Nadiradze et al. [2021a]. In particular, if
$s$ is the snapshot order of minor iteration $(j,t)$, it holds that,

$\mathbb{E}\left[\left\|w^{q}_{j,t}-v^{q,s}\right\||\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]\leq\alpha^{2}B^{2}.$ (15)

In inequation (15) the event $\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}$ used for conditioning is precisely the cases
where the snapshots for computing partial stochastic gradients were taken
after the last averaging round, i.e., if every component satisfies this
condition then the elastic consistency bound holds.

Note that under this condition, the maximum delay in terms of number of local
asynchronous SGD updates is $\tau_{max}=\bar{K}:=\max_{j,q}K^{q}_{j}$. Thus,
following Appendix B.6 of Nadiradze et al. [2021a], the following Lemma
defines the Elastic consistency constant:

######  Lemma 5.1.

$B=\sqrt{d}\bar{K}M$, where $d$ is the dimension of the model, $\bar{K}$ is
the maximum minor iteration count defined above, and $M$ is as defined for the
second moment bound in Equation 6.

We now present the main theorem proposing the ergodic convergence for a
general non-convex objective:

######  Theorem 5.1.

Under the Assumptions 3, 4, 5, 6, 7, defining $f_{m}$, $L$, $M$, $\sigma$ and
the stochastic delay model described by Assumption 5.1, it holds that,

$\begin{array}[]{l}\frac{1}{Q}\sum_{j=1}^{J}\sum_{q=1}^{Q}\sum_{t=0}^{K_{j}^{q}}\left\\{[\alpha
C_{1}-\alpha^{2}C_{2}]\mathbb{E}\left\|\nabla_{i}f(v^{q,s})\right\|^{2}\right.\\\
\left.+[\alpha
C_{3}-\alpha^{2}C_{4}]\mathbb{E}\left\|\nabla_{i}f(\bar{x}_{j})\right\|^{2}\right\\}\leq
f(\bar{x}_{0})-f_{m}\end{array}$ (16)

where $C_{1}$, $C_{2}$, $C_{3}$, and $C_{4}$ depend on $L$, $B$, $M$, $\sigma$
and probabilistic quantities defining the asynchronous computation.

Thus for any set of such constants, if sufficiently small
$\alpha=\Theta(1/\sqrt{J})$ is chosen then Algorithm 1 ergodically converges
with the standard $O(1/\sqrt{J})$ rate for nonconvex objectives.

The core idea to prove Theorem 5.1 is arguing that the worst-case increase in
the objective due to ”bad gradient updates”, which are computed over the
snapshots collected before the last averaging, are bounded. With such a bound
we then derive the convergence of the ”good updates” along the lines of
standard local SGD analysis such as Zhou and Cong [2017]. We defer the
detailed proof to Appendix A.

Distributed Speedup and Local scalability:

Distributed speedup with the number of workers $Q$ can be ascertained from the
dependence on $Q$ in Theorem 5.1. In implementation, the proposed methods
exhibit an almost linear data-parallel speedup w.r.t. $Q$, as shown in Table
4, where the effect of synchronization and communication costs is limited.

Formally, now consider, for instance Yu et al. [2019]; in their presentation
of interpreting linear speedup from the convergence theory, the learning rate
$\alpha$ is declared to be proportional to $\sqrt{Q}$. In effect, since, in
practice, the gradient updates are averaged across workers, the effective
$\alpha$ is always divided by $Q$. So then we can consider, in the context of
Theorem 5.1, scaling $\alpha$ by $Q$ to attempt obtaining linear speedup
effectively. However, this change would add an additional factor of $Q$ to the
$\alpha^{2}$ terms in (16), which will negatively balance the effect away from
linear speedup, the extent of which will depend on the particular constants.

Additional results indicating linear speedup for local SGD appear in
Haddadpour et al. [2019]. However, they use an additional assumption of a $PL$
inequality, which can relate the gradient norm to the objective value even for
nonconvex functions. While their technical analysis is impressive and
interesting, we restrict our theoretical results to considering the most
general case.

Local Scalability, i.e., speedup with the number of local updater processes
$U$, of asynchronous shared memory SGD can, in theory, achieve linear speedup
while $U$ is bounded by $O(\sqrt{T})$, where $T$ is the total number of
minibatch updates [Lian et al., 2015], if the delay probabilities are not
affected by the number of processes. However, in practice, scheduling an
additional process on a GPU has substantial overhead, which does influence the
delay probabilities, thus limiting the speedup. For Lpp-sgd the more
partitions the blocks are separated across, the smaller the size of gradient
update, which decays the theoretical speedup. However, in practice, the
reduced gradient computation cost of partial backpropagation handsomely
improves the balance towards faster performance.

##  6 Related Work

In the shared-memory setting, Hogwild! Recht et al. [2011] is now a celebrated
approach to scale SGD. However, it remains applicable to a centralized setting
of a single worker, thus, is not known to have been practically utilized for
fast large scale CNN training. Its success led to designs of variants which
targeted specific system aspects of a multi-core machine. For example,
Buckwild! Sa et al. [2015] proposed using restricted precision training on a
CPU.

As mentioned Hogwild!++ [Zhang et al., 2016b], has a decentralized design
targeted to NUMA machines, thus, it resembles Lap-sgd. However, there are
significant differences, which we discuss in Appendix C. In the local setting
of a GPU, the partial backpropagation of Lpp-sgd derives from PASSM$+$
[Kungurtsev et al., 2021], however, unlike them our gradient updates are lock-
free. Nonetheless, the similarities end there only – Lpp-sgd is a
decentralized method unlike PASSM$+$.

Periodic model averaging after several sequential local updates is now a
popular approach for distributed SGD: Woodworth et al. [2020a], Stich [2019],
Basu et al. [2019], Nadiradze et al. [2021b]. This method has been analyzed
with various assumptions on the implementation setting and the problem: Khaled
et al. [2020], Woodworth et al. [2020b], Koloskova et al. [2020]. Yet, unlike
us, none of these methods utilize shared-memory asynchrony or partial
backpropagation. Wang et al. [2020] proposed Overlap-local-SGD, wherein they
suggested to keep a model copy at each worker, very similar to Hogwild!++,
which is simultaneously averaged when sequential computation for multiple
iterations happen locally. They showed by limited experiments that it reduced
the communication overhead in a non-iid training case based on Cifar-10,
however, not much is known about its performance in general cases.

Chen et al. [2016] report that asynchrony causes performance degradation based
on limited empirical observations on specific hardware. Yet, others [Regatti
et al., 2019] showed that asynchrony favors generalization on a distributed
parameter server. Our work empirically, as well as with analytical insights,
establishes that asynchronous noise – from concurrent updates and from
distributed averaging – is a boon for the generalization performance.

##  7 Generalization Discussion

In Lin et al. [2020], the model of SGD algorithms as a form of a Euler-
Maruyama discretization of a Stochastic Differential Equation (SDE) presents
the perspective that the batch size can correspond to the inverse of the
injected noise. Whereas distributed SGD combined stochastic gradients as such
effectively results in an SGD step with a larger batch size, local SGD, by
averaging models rather than gradients, maintains the noise associated with
the local small-batch gradients. Given the well-established benefits of
greater noise in improving generalization accuracy (e.g. Smith and Le [2018]
and others), this presents a heuristic argument as to why local SGD tends to
generalize better than distributed SGD. In the Appendix we present an
additional argument for why local SGD generalizes well.

However, we see that our particular variation with asynchronous local updates
and asynchronous averaging seems to provide additional generalization accuracy
above and beyond local SGD. We provide the following explanation as to why
this could be the case, again from the perspective of noise as it would appear
in a SDE. Let us recall three facts,

  1. 1.

The noise appearing as a discretization of the Brownian motion term in the
diffusion SDE, and, correspondingly the injected noise studied as a driver for
increased generalization in previous works on neural network training is
i.i.d.,

  2. 2.

Clearly, the covariances of minibatch gradients as statistical estimates of
the gradients at model estimates $x$ and $x^{\prime}$ are going to be more
similar when $x$ and $x^{\prime}$ are closer together,

  3. 3.

Locally asynchronous gradients computed via snapshots taken before a previous
all-to-all averaging step, and thus far from the current state of the model in
memory, present additional noise, though they provide additional challenge for
the convergence theory (see Section 5).

Thus, effectively, the presence of these “highly asynchronous” stochastic
gradients, while being potentially challenging from the convergence
perspective, effectively brings the analogy of greater injected noise for
local SGD by inducing greater probabilistic independence, i.e., the injected
noise, for these updates, is far close to the i.i.d. noise that appears in a
discretized SDE.

##  8 Conclusion

Picking from where Golmant et al. [2018] concluded referring to their
findings: “These results suggest that we should not assume that increasing the
batch size for larger datasets will keep training times manageable for all
problems. Even though it is a natural form of data parallelism for large-scale
optimization, alternative forms of parallelism should be explored to utilize
all of our data more efficiently”, we introduced a fresh approach in the
direction to address the challenging trade-off of optimization quality vs.
scalability.

There are a plethora of small scale model and dataset combinations, where the
critical batch size–after which the returns in terms of convergence per wall-
clock time diminish–is small relative to existing system capabilities (Golmant
et al. [2018]). To such cases Lpp-sgd becomes readily useful.

We observed that for ResNet-50/Imagenet training the performance gain of Lpp-
sgd over Pl-sgd is roughly 5%. However, as other benchmarks showed,
predictively, this will reasonably change on higher end GPUs, such as NVIDIA
A100 with 40 GB memory and 624 teraflops peak performance. As an outlook, we
considerately did not include the distributed scalability techniques such as
quantized [Alistarh et al., 2017] or sparsified- [Seide et al., 2014, Alistarh
et al., 2018] communication, or for that matter, decentralized scalability
methods such as SGP [Assran et al., 2019]. These approaches can always
supplement a locally scalable scheme, which is the focus of this work. Our
future goal includes combining Lpp-sgd and these techniques.

In the experiments, we observed that the system-generated noise in some cases
effectively improved the generalization accuracy. The empirical findings
suggest that the proposed variant of distributed Sgd has a perfectly
appropriate place to fit in the horizon of efficient optimization methods for
training deep neural networks. As a general guideline for the applicability of
our approach, we would suggest the following: monitor the resource consumption
of a GPU that trains a CNN, if there is any sign that the utilization was less
than 100%, try out Lpp-sgd instead of arduously, and at times unsuccessfully,
tuning the hyperparameters in order to harness the data-parallelism.

## References

  * Akiba et al. [2017] Takuya Akiba, S. Suzuki, and K. Fukuda.  Extremely large minibatch sgd: Training resnet-50 on imagenet in 15 minutes.  _ArXiv_ , abs/1711.04325, 2017.
  * Alistarh et al. [2017] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and M. Vojnovic.  Qsgd: Communication-efficient sgd via gradient quantization and encoding.  In _NIPS_ , 2017.
  * Alistarh et al. [2018] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli.  The convergence of sparsified gradient methods.  In _Advances in Neural Information Processing Systems_ , pages 5977–5987, 2018.
  * Assran et al. [2019] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael G. Rabbat.  Stochastic gradient push for distributed deep learning.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _ICML_ , 2019\.
  * Basu et al. [2019] Debraj Basu, Deepesh Data, Can Karakus, and Suhas N. Diggavi.  Qsparse-local-sgd: Distributed SGD with quantization, sparsification and local computations.  In _NeurIPS 2019_ , pages 14668–14679, 2019.
  * Berglund [2011] Nils Berglund.  Kramers’ law: Validity, derivations and generalisations.  _arXiv preprint arXiv:1106.5799_ , 2011.
  * Bottou [2012] Léon Bottou.  Stochastic gradient descent tricks.  In _Neural networks: Tricks of the trade_ , pages 421–436. Springer, 2012.
  * Cartis and Scheinberg [2018] Coralia Cartis and Katya Scheinberg.  Global convergence rate analysis of unconstrained optimization methods based on probabilistic models.  _Mathematical Programming_ , 169(2):337–375, 2018\.
  * Chen et al. [2016] Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz.  Revisiting distributed synchronous sgd.  _arXiv preprint arXiv:1604.00981_ , 2016.
  * Dai and Zhu [2018] Xiaowu Dai and Yuhua Zhu.  Towards theoretical understanding of large batch training in stochastic gradient descent.  _arXiv preprint arXiv:1812.00542_ , 2018.
  * Dean et al. [2012] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Quoc V. Le, Mark Z. Mao, Marc’Aurelio Ranzato, Andrew W. Senior, Paul A. Tucker, Ke Yang, and Andrew Y. Ng.  Large scale distributed deep networks.  In _26th Annual Conference on Neural Information Processing Systems 2012_ , pages 1232–1240, 2012.
  * Golmant et al. [2018] Noah Golmant, Nikita Vemuri, Zhewei Yao, Vladimir Feinberg, A. Gholami, Kai Rothauge, M. Mahoney, and Joseph E. Gonzalez.  On the computational inefficiency of large batch sizes for stochastic gradient descent.  _ArXiv_ , abs/1811.12941, 2018.
  * Goyal et al. [2017] Priya Goyal, P. Dollár, Ross B. Girshick, P. Noordhuis, L. Wesolowski, Aapo Kyrola, Andrew Tulloch, Y. Jia, and Kaiming He.  Accurate, large minibatch sgd: Training imagenet in 1 hour.  _ArXiv_ , abs/1706.02677, 2017.
  * Haddadpour et al. [2019] Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck R. Cadambe.  Local SGD with periodic averaging: Tighter analysis and adaptive synchronization.  In _NeurIPS_ , pages 11080–11092, 2019.
  * He et al. [2016] Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 770–778, 2016.
  * Iandola et al. [2017] Forrest N. Iandola, Matthew W. Moskewicz, K. Ashraf, Song Han, W. Dally, and K. Keutzer.  Squeezenet: Alexnet-level accuracy with 50x fewer parameters and ¡1mb model size.  _ArXiv_ , abs/1602.07360, 2017.
  * Keskar et al. [2019] Nitish Shirish Keskar, Jorge Nocedal, Ping Tak Peter Tang, Dheevatsa Mudigere, and Mikhail Smelyanskiy.  On large-batch training for deep learning: Generalization gap and sharp minima.  In _5th International Conference on Learning Representations, ICLR 2017_ , 2019.
  * Khaled et al. [2020] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik.  Tighter theory for local SGD on identical and heterogeneous data.  In _AISTATS_ , volume 108 of _Proceedings of Machine Learning Research_ , pages 4519–4529. PMLR, 2020.
  * Koloskova et al. [2020] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U. Stich.  A unified theory of decentralized SGD with changing topology and local updates.  In _ICML_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 5381–5393. PMLR, 2020.
  * Krizhevsky [2009] A. Krizhevsky.  Learning multiple layers of features from tiny images.  2009\.
  * Kungurtsev et al. [2021] V. Kungurtsev, Malcolm Egan, Bapi Chatterjee, and Dan Alistarh.  Asynchronous stochastic subgradient methods for general nonsmooth nonconvex optimization.  _AAAI_ , 2021.
  * Lian et al. [2015] Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu.  Asynchronous parallel stochastic gradient for nonconvex optimization.  In _Neural Information Processing Systems 2015_ , pages 2737–2745, 2015.
  * Lin et al. [2020] Tao Lin, S. Stich, and M. Jaggi.  Don’t use large mini-batches, use local sgd.  _ICLR_ , 2020.
  * LocalSGD [2020] LocalSGD.  https://github.com/epfml/LocalSGD-Code.  2020\.
  * Loshchilov and Hutter [2017] I. Loshchilov and F. Hutter.  Sgdr: Stochastic gradient descent with warm restarts.  In _ICLR_ , 2017.
  * Mikami et al. [2018] Hiroaki Mikami, Hisahiro Suganuma, Pongsakorn U.-Chupala, Yoshiki Tanaka, and Y. Kageyama.  Imagenet/resnet-50 training in 224 seconds.  _ArXiv_ , abs/1811.05233, 2018.
  * MPS [2020] Nvidia MPS.  https://docs.nvidia.com/deploy/mps/index.html.  2020\.
  * Nadiradze et al. [2021a] Giorgi Nadiradze, Ilia Markov, Bapi Chatterjee, Vyacheslav Kungurtsev, and Dan Alistarh.  Elastic consistency: A general consistency model for distributed stochastic gradient descent.  In _AAAI_ , 2021a.
  * Nadiradze et al. [2021b] Giorgi Nadiradze, Amirmojtaba Sabour, Peter Davies, Ilia Markov, Shigang Li, and Dan Alistarh.  Decentralized {sgd} with asynchronous, local and quantized updates, 2021b.
  * NCCL [2020] NCCL.  https://docs.nvidia.com/deeplearning/nccl/index.html.  2020\.
  * Paszke et al. [2017] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer.  Automatic differentiation in pytorch.  2017\.
  * Pontes et al. [2016] F. J. Pontes, Gabriela da F. de Amorim, P. Balestrassi, A. P. Paiva, and J. R. Ferreira.  Design of experiments and focused grid search for neural network parameter optimization.  _Neurocomputing_ , 186:22–34, 2016.
  * Recht et al. [2011] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu.  Hogwild: A lock-free approach to parallelizing stochastic gradient descent.  In _Advances in neural information processing systems_ , pages 693–701, 2011.
  * Regatti et al. [2019] Jayanth Regatti, Gaurav Tendolkar, Yi Zhou, Abhishek Gupta, and Yingbin Liang.  Distributed sgd generalizes well under asynchrony.  _2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 863–870, 2019.
  * Russakovsky et al. [2015] Olga Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Zhiheng Huang, A. Karpathy, A. Khosla, M. Bernstein, A. Berg, and Li Fei-Fei.  Imagenet large scale visual recognition challenge.  _International Journal of Computer Vision_ , 115:211–252, 2015.
  * Sa et al. [2015] C. D. Sa, Ce Zhang, K. Olukotun, and C. Ré.  Taming the wild: A unified analysis of hogwild-style algorithms.  _Advances in neural information processing systems_ , 28:2656–2664, 2015.
  * Seide et al. [2014] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu.  1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns.  In _INTERSPEECH_ , pages 1058–1062, 2014.
  * Smith and Le [2018] Samuel L Smith and Quoc V Le.  A bayesian perspective on generalization and stochastic gradient descent.  In _International Conference on Learning Representations_ , 2018.
  * Stich [2018] Sebastian U Stich.  Local sgd converges fast and communicates little.  _arXiv preprint arXiv:1805.09767_ , 2018.
  * Stich [2019] Sebastian U. Stich.  Local SGD converges fast and communicates little.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.
  * Stich et al. [2018] Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi.  Sparsified sgd with memory.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Wang et al. [2020] Jianyu Wang, Hao Liang, and G. Joshi.  Overlap local-sgd: An algorithmic approach to hide communication delays in distributed sgd.  _ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 8871–8875, 2020.
  * Woodworth et al. [2020a] Blake E. Woodworth, Kumar Kshitij Patel, and Nati Srebro.  Minibatch vs local SGD for heterogeneous distributed learning.  In _NeurIPS 2020_ , 2020a.
  * Woodworth et al. [2020b] Blake E. Woodworth, Kumar Kshitij Patel, Sebastian U. Stich, Zhen Dai, Brian Bullins, H. Brendan McMahan, Ohad Shamir, and Nathan Srebro.  Is local SGD better than minibatch sgd?  In _ICML_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 10334–10343. PMLR, 2020b.
  * You et al. [2017a] Y. You, Z. Zhang, J. Demmel, K. Keutzer, and Cho-Jui Hsieh.  Imagenet training in 24 minutes.  2017a.
  * You et al. [2017b] Yang You, Igor Gitman, and B. Ginsburg.  Large batch training of convolutional networks.  _arXiv: Computer Vision and Pattern Recognition_ , 2017b.
  * Yu et al. [2019] Hao Yu, Rong Jin, and Sen Yang.  On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization.  In _International Conference on Machine Learning_ , pages 7184–7193. PMLR, 2019.
  * Zagoruyko and Komodakis [2016] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  _ArXiv_ , abs/1605.07146, 2016.
  * Zhang et al. [2016a] Huan Zhang, Cho-Jui Hsieh, and V. Akella.  Hogwild++: A new mechanism for decentralized asynchronous stochastic gradient descent.  _2016 IEEE 16th International Conference on Data Mining (ICDM)_ , pages 629–638, 2016a.
  * Zhang et al. [2016b] Huan Zhang, Cho-Jui Hsieh, and Venkatesh Akella.  Hogwild++: A new mechanism for decentralized asynchronous stochastic gradient descent.  In _2016 IEEE 16th International Conference on Data Mining (ICDM)_ , pages 629–638. IEEE, 2016b.
  * Zhang et al. [2016c] Jian Zhang, C. D. Sa, Ioannis Mitliagkas, and C. Ré.  Parallel sgd: When does averaging help?  _ArXiv_ , abs/1606.07365, 2016c.
  * Zhou and Cong [2017] Fan Zhou and Guojing Cong.  On the convergence properties of a $k$-step averaging stochastic gradient descent algorithm for nonconvex optimization.  _arXiv preprint arXiv:1708.01012_ , 2017.
  * Zinkevich et al. [2010] Martin Zinkevich, M. Weimer, Alex Smola, and L. Li.  Parallelized stochastic gradient descent.  In _NIPS_ , 2010.

##  Appendix A Convergence Theory

The convergence analysis of our algorithm requires precise modelling and
ordering of concurrent processes in time – the gradient updates by processes
$u^{q}$ at line 1 and the vector difference updates by process $a^{q}$ at line
1 for lock-free averaging – in Algorithm 1 on the model $x^{q}$ in the shared-
memory setting of a worker $q\in\mathcal{Q}$. To this end, we define the
following orders.

#### Snapshot Order.

The snapshot collections over the shared memory of a worker $q\in\mathcal{Q}$
are ordered by the shared-counter $\mathcal{C}^{q}$ as read at line 1 in
Algorithm 1. Correspondingly, the partial gradients, as computed using these
snapshots, get ordered too. We define the snapshot order of a gradient update
as the order by value of $\mathcal{C}^{q}$ of the snapshot collections.

#### Update Order.

The updates at each of the components of the model vector $x^{q}$ are atomic
by means of fetch&add. Furthermore, each process $u^{q}$ updates the
components of $x^{q}$ in the same order (from left to right). This would
enable us to order the partial gradient updates by when they write over a
common model component. However, given that there are independent lock-free
updates over the blocks of the model, we can not use any particular component,
for example, the first component of $x^{q}$, to order the gradient updates. To
overcome this issue, we assume that each time before updating the model at
line 1 in Algorithm 1, an updater process $u^{q}$ atomically accesses the
reference (pointer) to $x^{q}$ over the shared memory. Thus, we order the
updates by their atomic access to this reference. We call this order the
update order.

#### Iteration Order.

Because a single designated process $a^{q}$ on each worker $q\in\mathcal{Q}$
performs averaging, the synchronization rounds (corresponding the vector
difference updates at line 1 in Algorithm 1) have a natural order, which is
also the order of the major iteration views as defined in Section 4. Now,
similar to the update order as defined above, we assume that each time before
$a^{q}$ starts writing over the model $x^{q}$, it atomically accesses the
memory-reference to it. Thereby, we have a well-defined arrangement of the
gradient updates before or after a particular averaging update over the shared
model. Thus we define the iteration order of a gradient update as the
dictionary order $(j,t)$ to denote that it is the $t^{th}$ gradient update
after the $j^{th}$ averaging round.

With the above description, each of the minor iteration views as defined in
Section 5 has well-defined snapshot, update, and iteration orders. With that,
we define the following delay model.

###  A.1 The Proof Overview

The proof follows the structure of the ergodic convergence proof of K-step
local SGD given in Zhou and Cong [2017], wherein in each round of averaging
there are $\sum K^{q}_{j}$ total updates to the model vector associated with
the $q\in\mathcal{Q}$ workers.

Insofar as the local asynchronous SGD updates are computed over the snapshots
close to the globally synchronized model vector at the last averaging step,
there is an expected amount of descent, relative to the value at the last
averaging step, achieved from these steps. The task of the convergence theory
is to quantify how much descent can be guaranteed, and then this is to be
balanced with the amount of possible ascent that could occur from computing
SGD updates at snapshots collected far from the one at the last averaging
step.

In particular, we need to bound the worst-case increase in the objective due
to SGD updates computed over the snapshots collected before the updates by the
last averaging and scale it based on the probability that such an old snapshot
is used for the computation.

#### Good and Bad Iterates.

To balance these two cases, the analysis takes an approach, inspired partially
by the analysis given in Cartis and Scheinberg [2018] of separating these as
“good” and ”bad” iterates: the ”good” iterates correspond to snapshots (all
components thereof) for SGD updates at line 1 read after the last snapshot
(all components thereof) for averaging at line 1 was taken in Algorithm 1,
with some associated guaranteed descent in expectation, whereas the “bad”
iterates are those read before that. Thus we split the expected descent as
expected descent with a “good” iterate multiplied by its probability, added
with the worst case ascent of a “bad” iterate multiplied by its probability.

By considering the stochastic process governing the amount of asynchrony as
being governed by probabilistic laws, we can characterize the probability of a
“good” and “bad” iterate and ultimately seek to balance the total expected
descent from one, and worst possible ascent in the other, as a function of
these probabilities.

###  A.2 Proof of Main Convergence Theorem

Recall the major iteration views $\bar{x}_{j}$ are defined as the average of
the last minor iteration views. Restating its update rule here for reference
in this section,

$\bar{x}_{j+1}=\frac{1}{Q}\sum_{q=1}^{Q}\left[\bar{x}_{j}-|_{i}\alpha\sum_{t=0}^{K_{j}^{q}}\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v^{q}_{j,t})\right],$
(17)

where $|_{i}$ is the block-restricted subtraction as we defined in Section 5.

We are now ready to prove the convergence Theorem. The structure of the proof
will follow Zhou and Cong [2017], who derives the standard sublinear
convergence rate for local SGD in a synchronous environment for nonconvex
objectives.

######  Theorem A.1 (Restatement of Theorem (5.1)).

Under Assumptions 3, 4, 5, 6, and 7 together with Assumptions 5.1 on delay
probabilities, it holds that,

$\begin{array}[]{l}\frac{1}{Q}\sum_{j=1}^{J}\sum_{q=1}^{Q}\sum_{t=0}^{K_{j}^{q}}\left\\{[\alpha
C_{1}-\alpha^{2}C_{2}]\mathbb{E}\left\|\nabla_{i}f(v^{q}_{j,t})\right\|^{2}+[\alpha
C_{3}-\alpha^{2}C_{4}]\mathbb{E}\left\|\nabla_{i}f(\bar{x}_{j})\right\|^{2}\right\\}\leq
f(\bar{x}_{0})-f_{m}\end{array}$ (18)

where $C_{1}$, $C_{2}$, $C_{3}$, and $C_{4}$ depend on $L$, $B$, $M$, $\sigma$
and probabilistic quantities defining the asynchronous computation. Thus there
exists a set of such constants s. t. if
$\alpha=\Theta\left(\frac{1}{\sqrt{J}}\right)$ then Algorithm 1 ergodically
converges with the standard $O(1/\sqrt{J})$ rate for nonconvex objectives.

###### Proof.

We begin with the standard application of the Descent Lemma,

$\begin{array}[]{l}f(\bar{x}_{j+1})-f(\bar{x}_{j})\leq-\langle\nabla
f(\bar{x}_{j}),\frac{1}{Q}\sum_{q=1}^{Q}\sum_{t=0}^{K_{j}^{q}}\alpha\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v_{j,t}^{q})\rangle+\frac{L}{2}\left\|\frac{1}{Q}\sum_{q=1}^{Q}\sum_{t=0}^{K_{j}^{q}}\alpha\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v_{j,t}^{q})\right\|^{2}\end{array}$
(19)

Now, since
$\mathbb{E}\left[\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v_{j,t}^{q})\right]=\nabla_{i}f(v_{j,t}^{q})$
using the unbiasedness Assumption 3,

$\begin{array}[]{l}-\mathbb{E}\langle\nabla
f(\bar{x}_{j}),\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v_{j,t}^{q})\rangle=-\frac{1}{2}\left(\|\nabla_{i}f(\bar{x}_{j})\|^{2}+\mathbb{E}\|\nabla_{i}f(v_{j,t}^{q})\|^{2}-\mathbb{E}\|\nabla_{i}f(v_{j,t}^{q})-\nabla_{i}f(\bar{x}_{j})\|^{2}\right)\end{array}$
(20)

We now split the last term by the two cases and use Equation 15,

$\begin{array}[]{l}\mathbb{E}\|\nabla_{i}f(v_{j,t}^{q})-\nabla_{i}f(\bar{x}_{j})\|^{2}\\\
=\mathbb{E}\left[\|\nabla_{i}f(v_{j,t}^{q})-\nabla_{i}f(\bar{x}_{j})\|^{2}|\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]\mathbb{P}\left[\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]\\\
\quad+\mathbb{E}\left[\|\nabla_{i}f(v_{j,t}^{q})-\nabla_{i}f(\bar{x}_{j})\|^{2}|\left(\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right)^{c}\right]\times\mathbb{P}\left[\left(\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right)^{c}\right]\\\
\leq\alpha^{2}B^{2}\mathbb{P}\left[\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]+2\left(\|\nabla_{i}f(\bar{x}_{j})\|^{2}+\mathbb{E}\|\nabla_{i}f(v_{j,t}^{q})\|^{2}\right)\mathbb{P}\left[\left(\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right)^{c}\right]\end{array}$

and thus combining with equation 20 we get the overall bound,

$\begin{array}[]{l}-\mathbb{E}\langle\nabla
f(\bar{x}_{j}),\stackrel{{\scriptstyle\sim}}{{\smash{{\nabla}}\rule{0.0pt}{4.73611pt}}}\kern-4.30554pt_{i}f(v_{j,t}^{q})\rangle\\\
\qquad\leq-\frac{1}{2}\left(\|\nabla_{i}f(\bar{x}_{j})\|^{2}+\mathbb{E}\|\nabla_{i}f(v_{j,t}^{q})\|^{2}-\alpha^{2}B^{2}\right)\times\mathbb{P}\left[\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]\\\
\qquad\qquad+\frac{1}{2}\left(\|\nabla_{i}f(\bar{x}_{j})\|^{2}+\mathbb{E}\|\nabla_{i}f(v_{j,t}^{q})\|^{2}\right)\mathbb{P}\left[\left(\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right)^{c}\right]\\\
\qquad\leq-\left(\|\nabla_{i}f(\bar{x}_{j})\|^{2}+\mathbb{E}\|\nabla_{i}f(v_{j,t}^{q})\|^{2}\right)\mathbb{P}\left[\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]\\\
\qquad\qquad+\frac{1}{2}\left(\|\nabla_{i}f(\bar{x}_{j})\|^{2}+\mathbb{E}\|\nabla_{i}f(v_{j,t}^{q})\|^{2}\right)+\frac{\alpha^{2}B^{2}}{2}\end{array}$
(21)

Combining these, we get,

$\begin{array}[]{l}\frac{1}{Q}\sum_{q=1}^{Q}\sum_{t=0}^{K_{j}^{q}}\alpha\left[\mathbb{P}\left[\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]-\alpha\left(QK_{j}^{q}+\frac{B}{2}\right)\right]\times\mathbb{E}\|\nabla_{i}f(v_{j,t}^{q})\|^{2}\\\
+\frac{1}{Q}\sum_{q=1}^{Q}\sum_{t=0}^{K_{j}^{q}}\alpha\left[\mathbb{P}\left[\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]-\frac{\alpha
B^{2}}{2}\right]\mathbb{E}\|\nabla_{i}f(\bar{x}_{j})\|^{2}\\\ \leq
f(\bar{x}_{j})-f(\bar{x}_{j+1})\end{array}$ (22)

Summing over $j$ obtains the expression in Theorem A.1 with
$C_{1}=\mathbb{P}\left[\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]$, $C_{2}=QK_{j}^{q}+\frac{B}{2}$,
$C_{3}=\mathbb{P}\left[\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]$, and $C_{4}=\frac{B^{2}}{2}$, whereof,
Assumption 5.1 ensures the existence of $C_{1}$ and $C_{3}$. ∎

Remark In order to achieve _asymptotic_ convergence, Assumption 5.1 can be
relaxed further, in particular, it just cannot be summable, i.e., the
condition,

$\sum_{j=1}^{\infty}\sum_{q=1}^{Q}\sum_{t=0}^{K^{q}_{j}}\mathbb{P}\left[\cap_{e}\cup_{l\geq
k}^{u}\mathbb{I}^{q,l,e}_{j,t}\right]=\infty$

is sufficient for guaranteeing asymptotic convergence.

#### Discussion.

Now, let us consider two extreme cases: if there is always only one local
stochastic gradient update for all workers for all major iterations $j$, i.e.,
$K_{j}^{q}\equiv 1$, _any_ delay means reading a vector in memory before the
last major iteration, and thus the probability of delay greater than zero must
be very small in order to offset the worst possible ascent.

On the other hand, if in general $K_{j}^{q}>>\tau$, then while the first
$\tau$ minor iteration views could be as problematic at a level depending on
the probability of the small delay times, for $t>\tau$ clearly the vector
$v^{q}_{j,t}$ satisfies Equation 15.

Thus we can sum up our conclusions in the following statements:

  1. 1.

Overall, considering distribution for the delays, the higher the mean,
variance, and thickness of the tails of this distribution, the more
problematic convergence would be,

  2. 2.

The larger the quantity of local updates each worker performs in between
averaging, the more likely a favorable convergence would occur.

The first is of course standard and obvious. The second presents the
interesting finding that if you are running asynchronous stochastic gradient
updates on local shared memory, performing local SGD with a larger gap in time
between averaging results in more robust performance.

This suggests a certain fundamental _harmony_ between asynchronous concurrency
and local SGD, more “aggressive” locality, in the sense of doing more local
updates between averaging, coincides with expected performance gains and
robustness of more “aggressive” asynchrony and concurrency, in the sense of
delays in the computations associated with local processes.

In addition, to contrast the convergence in regards to the block size, which
in turn depends on the number of updater processes, clearly the larger the
block, equivalently, smaller the number of updater processes the faster the
overall convergence, since the norms of the gradient vectors appear. An
interesting possibility to consider is if a process can roughly estimate or
predict when averaging could be triggered, robustness could be gained by
attempting to do block updates right after an expected averaging step, and
full parameter vector updates later on in the major iteration.

##  Appendix B An Argument for Increased Generalization Accuracy

###  B.1 Wide and Narrow Wells

In general it has been observed that whether a local minimizer is wide or
narrow, or how “flat” it is, seems to affect its generalization properties
[Keskar et al., 2019]. Motivated by investigating the impact of batch size on
generalization, Dai and Zhu [2018] analyzed the generalization properties of
SGD by considering the escape time from a “well”, i.e., a local minimizer in
the objective landscape, for a constant stepsize variant of SGD by modeling it
as an overdamped Langevin-type diffusion process,

$dX_{t}=-\nabla f(X_{t})dt+\sqrt{2\epsilon}dW_{t}$

In general “flatter” minima have longer escape times than narrow ones, where
the escape time is the expectation in the number of iterations (defined as a
continuous parameter in this sense) until the iterates leave the well to
explore the rest of the objective landscape. Any procedure that increases the
escape time for flatter minima as compared to narrower ones should, in theory,
result in better generalization properties, as it is more likely then that the
procedure will return an iterate that is in a narrow minimizer upon
termination.

Denote with indexes $w$ for a “wide” valley local minimizer and $n$ for a
“narrow” value, which also corresponds to smaller and larger minimal Hessian
eigenvalues, respectively.

The work Berglund [2011] discusses the ultimately classical result that as
$\epsilon\to 0$, the escape time from a local minimizer valley satisfies,

$\mathbb{E}[\tau_{e}]=He^{C/\epsilon}$

and letting the constant $H$ depend on the type of minimizer, it holds that
that $H_{w}>H_{n}$, i.e., this time is longer for a wider valley.

We also have from the same reference,

$\mathbb{P}[\tau_{e}>s\mathbb{E}[\tau_{e}]]=e^{-s}$

###  B.2 Averaging

We now contrast two procedures and compare the difference in their escape
times for narrow and wider local minimizers. One is the standard SGD, and in
one we perform averaging every $\tau_{a}$ time. In each case there are $Q$
workers, in the first case running independent instances of SGD, and in the
other averaging their iterates. We average the models probabilistically as it
results in a randomized initialization within the well, and thus the escape
time is a sequence of independent trials of length $\tau_{a}$ with an initial
point in the well, i.e., escaping at time $\tau_{e}$ means that there are
$Q\left\lceil{\frac{\tau_{e}}{\tau_{a}}}\right\rceil$ trials wherein none of
the $Q$ sequences escaped within $\tau_{a}$, and then one of them escaped in
the next set of $Q$ trials.

For ease of calculation, let us assume that
$\tau_{a}=\frac{1}{2}\mathbb{E}[\tau^{w}_{e}]=2\mathbb{E}[\tau^{n}_{e}]$,
where $\tau^{w}_{e}$ and $\tau^{n}_{e}$ are the calculated single process
escape time from a wide and narrow well, respectively.

If any one of the local runs escapes, then there is nothing that can be said
about the averaged point, so a lack of escape is indicated by the case for
which all trajectories, while periodically averaged, stay within the local
minimizer value.

Now consider if no averaging takes place, we sum up the probabilities for the
wide valley that they all escape after time $(i-1)\tau$ time and, given that
they do so, not all of them escape after $i\tau_{a}$.

$\begin{array}[]{l}\mathbb{E}[\tau^{w}_{e}]\leq\sum_{i=1}^{\infty}P(\tau^{w}_{e}>(i-1)\tau_{a})^{Q}(1-P(\tau^{w}_{e}>\tau_{a}i|\tau^{w}_{e}>(i-1)\tau_{a})^{Q})i\tau_{a}\\\
\qquad\leq\sum_{i=1}^{\infty}\left(e^{-\frac{Q(i-1)}{2}}\left(1-e^{-\frac{Q}{2}}\right)\tau_{a}i\right)\end{array}$

For the narrow well this is,

$\begin{array}[]{l}\mathbb{E}[\tau^{n}_{e}]\geq\sum_{i=1}^{\infty}P(\tau^{n}_{e}>(i-1)\tau_{a})^{Q}(1-P(\tau^{n}_{e}>\tau_{a}i|\tau^{n}_{e}>(i-1)\tau_{a})^{Q})(i-1)\tau_{a}\\\
\qquad\qquad\geq\sum_{i=1}^{\infty}\left(e^{-2Q(i-1)}\left(1-e^{-2Q}\right)\tau_{a}(i-1)\right)\end{array}$

The difference in the expected escape times satisfies,

$\begin{array}[]{l}\mathbb{E}[\tau^{w}_{e}-\tau^{n}_{e}]\leq\sum_{i=1}^{\infty}\left[\left[\left(e^{-\frac{Q(i-1)}{2}}\left(1-e^{-\frac{Q}{2}}\right)\right)-\left(e^{-2Q(i-1)}\left(1-e^{-2Q}\right)\right)\right](i-1)\right.\\\
\qquad\qquad\qquad\left.+\left(e^{-\frac{Q(i-1)}{2}}\left(1-e^{-\frac{Q}{2}}\right)\right)\right]\tau_{a}\end{array}$

Recall that in the case of averaging, if escaping takes place between
$(i-1)\tau_{a}$ and $i\tau_{a}$ there were no escapes with less that
$\tau_{a}$ for $M$ processors multiplied by $i-1$ times trials, and at least
one escape between $(i-1)\tau_{a}$ and $i\tau_{a}$, i.e., not all did not
escape between these two times.

The expected first escape time for any trajectory among $Q$ from a wide
valley, thus, is,

$\begin{array}[]{l}\mathbb{E}[\tau^{a,w}_{e}]\leq\sum_{i=1}^{\infty}\left(\mathbb{P}[\tau^{w}_{e}>\tau_{a}]^{(i-1)Q}(1-\mathbb{P}[\tau^{w}_{e}>\tau_{a}]^{Mi})\tau_{a}i\right)\\\
\qquad\leq\sum_{i=1}^{\infty}e^{-\frac{(i-1)Q}{2}}(1-e^{-\frac{iQ}{2}})\tau_{a}i\end{array}$

And now with averaging, the escape time from a narrow valley satisfies

$\begin{array}[]{l}\mathbb{E}[\tau^{a,n}_{e}]\geq\sum_{i=1}^{\infty}\left(\mathbb{P}[\tau^{n}_{e}>\tau_{a}]^{(i-1)Q}(1-\mathbb{P}[\tau^{n}_{e}>\tau_{a}]^{Qi})\tau_{a}(i-1)\right)\\\
\qquad\geq\sum_{i=1}^{\infty}e^{-2(i-1)Q}(1-e^{-2iQ})\tau_{a}(i-1).\end{array}$

Thus the difference in the expected escape times satisfies

$\begin{array}[]{l}\mathbb{E}[\tau^{a,w}_{e}-\tau^{a,n}_{e}]\leq\sum_{i=1}^{\infty}\left[\left[e^{-\frac{(i-1)Q}{2}}(1-e^{-\frac{iQ}{2}})-e^{-2(i-1)Q}(1-e^{-2iQ})\right](i-1)+e^{-\frac{(i-1)Q}{2}}(1-e^{-\frac{iQ}{2}})\right]\tau_{a}.\end{array}$

It is clear from the above expressions that the upper bound for the difference
is larger in the case of averaging. This implies that averaging results in a
greater difference between the escape times between wider and narrow local
minimizers, suggesting that, on average if one were to stop a process of
training and use the resulting iterate as the estimate for the parameters,
this iterate would more likely come from a flatter local minimizer if it was
generated with a periodic averaging procedure, relative to standard SGD. Thus
it should be expected, at least by this argument that better generalization is
more likely with periodic averaging.

Note that since they are both upper bounds, this isn’t a formal proof that in
all cases the escape times are more favorable for generalization in the case
of averaging, but a guide as to the mathematical intuition as to how this
could be the case.

##  Appendix C More on Related Work

The main contribution of the present work is the algorithm Lpp-sgd, where the
shared models on each worker receive partial asynchronous gradient updates
locally in addition to being averaged across the workers in a non-blocking
fashion. On the other hand, in Lap-sgd each local gradient update is on the
full model vector. In the existing literature, a variant of celebrated
Hogwild! [Recht et al., 2011], called Hogwild!++ [Zhang et al., 2016b] was
proposed, which harnesses the non-uniform-memory-access (NUMA) architecture
based multi-core computers. In this method, threads pinned to individual CPUs
on a multi-socket mainboard with access to a common main memory, form
clusters. In principle, the proposed Lap-sgd may resemble Hogwild!++. However,
there are important differences:

  1. 1.

At the structural level, the averaging in Hogwild!++ is binary on a ring graph
of thread-clusters. Furthermore, it is a token based procedure where in each
round only two neighbours synchronize, whereas in Lap-sgd it is all-to-all.

  2. 2.

In Hogwild!++ each cluster maintains two copies of the model: a locally
updating copy and a buffer copy to store the last synchronized view of the
model, whereby each cluster essentially passes the “update” in the local model
since the last synchronization to its neighbour. However, this approach has a
drawback as identified by the authors: the update that is passed on a ring of
workers eventually “comes back” to itself thereby leading to divergence, to
overcome this problem they decay the sent out update. By contrast, Lap-sgd
uses no buffer and does not track updates as such. Averaging the model with
each peer, similar to L-sgd, helps each of the peers to adjust their
optimization dynamics.

  3. 3.

It is not known if the token based model averaging of Hogwild!++ is sufficient
for training deep networks where generalization is the core point of concern.
As against that, we observed that our asynchronous averaging provides an
effective protocol of synchronization and often results in improving the
generalization.

  4. 4.

Comparing the thread-clusters of Hogwild!++ to concurrent processes on GPUs in
Lap-sgd, the latter uses a dedicated process that performs averaging without
disturbing the local gradient updates thereby maximally reducing the
communication overhead.

  5. 5.

Finally, we prove convergence of Lap-sgd for non-convex problems, by contrast,
Hogwild!++ does not have any convergence guarantee.

Thus, in its own merit, Lap-sgd is a novel distributed Sgd method. However, to
our knowledge, this is the first work to suggest averaging the models on
distributed workers, where locally they are asynchronously updated with
partial stochastic gradients, which is the proposed method Lpp-sgd.

##  Appendix D Experiments and Hyperparameters

#### System Details.

More detail on the specific settings: (a) S1: two Nvidia GeForce RTX 2080 Ti
GPUs and an Intel(R) Xeon(R) E5-1650 v4 CPU running @ 3.60 GHz with 12 logical
cores, (b) S2: four Nvidia GeForce RTX 2080 Ti GPUs and two Intel(R) Xeon(R)
E5-2640 v4 CPUs running @ 2.40 GHz totaling 40 logical cores, (c) S3: two S2
settings connected with a 100 GB/s infiniband link, and (d) S4: eight Nvidia
V100 GPUs, 2 each on 4 nodes in a supercomputing cluster; each node contains
two Intel(R) Xeon(R) CPUs running @ 2.70 GHz totaling 72 logical cores; the
nodes on the cluster are managed by slurm and connected with 100 GB/s
infiniband links.

#### Nvidia Multi-process Service.

It is pertinent to mention that the key enabler of the presented fully non-
blocking asynchronous implementation methodology is the support for multiple
independent client connection between a CPU and a GPU. Starting from early
2018 with release of Volta architecture, Nvidia’s technology Multi-process
Service (MPS) efficiently support this. For more technical specifications
please refer to their doc-pages MPS [2020]. Now, we present extra experimental
results.

#### Hyperparameters’ Details.

The hyperparameters of the experiments are provided in Table 13. In each of
the experiments, we have a constant momentum of 0.9. In each of them, as
mentioned before, we use standard multi-step diminishing learning rate
scheduler with dampening factor $\gamma$ at designated epochs for the methods
Mb-sgd and Pl-sgd, whereas, we use cosine annealing for the methods Lap-sgd
and Lpp-sgd without restart. Cosine annealing starts immediately after warm-
up, which in each case happens for the first 5 epochs. For Lpp-sgd, we fix
initially $E_{st}$ number of epochs when we perform full asynchronous SGD
updates i.e. Lap-sgd.

More Cifar-10/Cifar-100 Results. Performance of the methods for
ResNet-20/Cifar-100 for 300 epochs and SqueezeNet/Cifar-100 for 200 epochs are
available in Tables 11 and 12, respectively. In Lap-sgd, Lpp-sgd, and Pl-sgd
we use $K=1$ up to 150 and 100 epochs in the two respective experiments and
after that $K=16$. In summary, as seen before, the relative latency of the
methods are as seen in Table 4, whereas in each case Lap-sgd and Lpp-sgd
recovers or improves the baseline training results.

Method |  $B_{loc}$ |  $U$ |  Tr.L. |  Te.L. |  Tr.A. |  Te.A. |  $T$
---|---|---|---|---|---|---|---
Lap-sgd |  128 |  6 |  0.295 |  1.191 |  92.23 |  69.43 |  1285
Lap-sgd |  128 |  4 |  0.299 |  1.198 |  92.15 |  69.78 |  1325
Lpp-sgd |  128 |  6 |  0.404 |  1.173 |  88.69 |  69.47 |  1085
Lpp-sgd |  128 |  4 |  0.378 |  1.161 |  89.50 |  69.75 |  1154
Mb-sgd |  1024 |  - |  0.464 |  1.212 |  86.46 |  67.04 |  1244
Mb-sgd |  128 |  - |  0.360 |  1.111 |  89.93 |  69.73 |  1754
Pl-sgd |  1024 |  - |  0.373 |  1.152 |  89.48 |  67.97 |  1198
Pl-sgd |  128 |  - |  0.379 |  1.099 |  89.29 |  69.67 |  1613
Table 11: ResNet-20 on Cifar-100 over the setting S1. Method |  $B_{loc}$ |  $U$ |  Tr.L. |  Te.L. |  Tr.A. |  Te.A. |  $T$
---|---|---|---|---|---|---|---
Lap-sgd |  128 |  4 |  0.037 |  1.549 |  99.56 |  70.17 |  1263
Lpp-sgd |  128 |  4 |  0.070 |  1.504 |  98.79 |  69.97 |  1071
Mb-sgd |  1024 |  - |  0.043 |  1.294 |  99.60 |  68.30 |  1584
Mb-sgd |  128 |  - |  0.049 |  1.178 |  99.29 |  70.06 |  2134
Pl-sgd |  1024 |  - |  0.061 |  1.259 |  99.25 |  68.46 |  1209
Pl-sgd |  128 |  - |  0.062 |  1.207 |  99.00 |  69.38 |  1857
Table 12: SqueezeNet on Cifar-100 over the setting S1. Exp. |  Model |  Dataset |  Epochs |  $\underline{B_{loc}}$ |  $\underline{\alpha}$ |  $\alpha^{w}_{DP}$ |  $\alpha^{w}_{LAP}$ |  $\alpha^{w}_{LPP}$ |  $\gamma$ |  Dampen -ing at |  Wt. decay |  $T_{st}$
---|---|---|---|---|---|---|---|---|---|---|---|---
Table 1 |  ResNet-20 |  Cifar-10 |  300 |  128 |  0.1 |  0.2 |  0.2 |  0.25 |  0.1 |  150, 225 |  0.0005 |  50
Table 4 |  WideResNet-16x8 |  Cifar-10 |  200 |  128 |  0.1 |  – |  – |  – |  0.2 |  60, 120, 160 |  0.0001 |  20
Table 5 |  WideResNet-16x8 |  Cifar-100 |  200 |  128 |  0.1 |  0.8 |  0.8 |  1.0 |  0.2 |  60, 120, 160 |  0.0001 |  20
Table 6 |  SqueezeNet |  Cifar-10 |  200 |  128 |  0.1 |  0.2 |  0.2 |  0.25 |  0.2 |  60, 120, 160 |  0.0001 |  20
Table 8 |  ResNet-50 |  Imagenet |  90 |  32 |  0.0125 |  0.8 |  0.1 |  0.125 |  0.1 |  30, 60, 80 |  0.00005 |  9
Table 11 |  ResNet-20 |  Cifar-100 |  300 |  128 |  0.1 |  0.2 |  0.2 |  0.25 |  0.1 |  150, 225 |  0.0005 |  50
Table 12 |  SqueezeNet |  Cifar-100 |  200 |  128 |  0.1 |  0.2 |  0.2 |  0.25 |  0.2 |  60, 120, 160 |  0.0001 |  20
Table 13: Hyperparameters used in the experiments. $\underline{\alpha}$:
Initial Learning Rate (LR), $\alpha^{w}_{DP}$: Warmed-up LR for Data-parallel
methods Mb-sgd and Pl-sgd with standard batch size $\underline{B_{loc}}$ on
each GPU (for large local batch sizes we scale the LR in the ratio of used
batch size and $\underline{B_{loc}}$), $\alpha^{w}_{LAP}$: Warmed-up LR for
Lap-sgd, $\alpha^{w}_{LPP}$: Warmed-up LR for Lpp-sgd. In general, we follow
the standard LR warm-up strategy as discussed before: warm up for the first 5
epochs to scale from $\underline{\alpha}$ to
$\underline{\alpha}\times\frac{B_{loc}{\times}Q}{\underline{B_{loc}}}$, where
$Q$ is the number of workers. “Dampening at” are the epoch counts where we
dampen $\alpha^{w}_{DP}$ by the multiple $\gamma$ following the standard
multi-step diminishing LR tuning scheme.