Asynchronous Stochastic Subgradient Methods for General Nonsmooth Nonconvex Optimization
Authors: Vyacheslav Kungurtsev
Malcolm Egan
Bapi Chatterjee
Dan Alistarh
Venue:  (2020)
Keywords: optimziation
stochastic optimization
asynchronous parallel architecture
deep neural networks

Abstract: Asynchronous distributed methods are a popular way to reduce the communication and synchronization costs of large-scale optimization. Yet, for all their success, little is known about their convergence guarantees in the challenging case of general non-smooth, non-convex objectives, beyond cases where closed-form proximal operator solutions are available.
This is all the more surprising since these objectives are the ones appearing in the training of deep neural networks.

In this paper, we introduce the first convergence analysis covering asynchronous methods in the case of general non-smooth, non-convex objectives. Our analysis applies to stochastic sub-gradient descent methods both with and without block variable partitioning, and both with and without momentum. It is phrased in the context of a general probabilistic model of asynchronous scheduling accurately adapted to modern hardware properties. We validate our analysis experimentally in the context of training deep neural network architectures. We show their overall successful asymptotic convergence as well as exploring how momentum, synchronization, and partitioning all affect performance.

Under review as a conference paper at ICLR 2020
ASYNCHRONOUS STOCHASTIC SUBGRADIENT METH- ODS FOR GENERAL NONSMOOTH NONCONVEX OPTI- MIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Asynchronous distributed methods are a popular way reduce the communication and synchronization costs of large-scale optimization. Yet, for all their success, little is known about their convergence guarantees in the challenging case of general non-smooth, non-convex objectives. beyond cases where closed-form proximal operator solutions are available. This is the more surprising since these objectives are the ones appearing in the training of deep neural networks.
In this paper, we introduce the first convergence analysis covering asynchronous methods in the case of general non-smooth, non-convex objectives. Our analysis applies to stochastic sub wub-gradient descent methods both with and without block vari- able partitioning, and both with and without momentum. It is phrased in the context of general probabilistic model of asynchronous scheduling accurately adapted modern hardware properties. We validate our analysis experimentally in the context of training deep neural network architectures. We show their overall successful asymptotic convergence as well as exploring how momentum, synchronization, and partitioning all affect performance.
INTRODUCTION
Training parameters arising in Deep Neural Net architectures is difficult problem in several ways (Goodfellow et al. 2016). First, with multiple layers and nonlinear activation functions such as sigmoid and softmax functions, the ultimate optimization problem is nonconvex. Second, with ReLU activation functions and max-pooling in convolutional structures, the problem is nonsmooth, i.e., is not differentiable everywhere, although typically the set of non-differentiable points is set of measure zero the space of the parameters. Finally, in many applications it is unreasonable to load the whole sample size in memory to evaluate the objective function (sub)gradient, thus samples must be taken, necessitating analysis in probabilistic framework.
The analysis of parallel optimization algorithms using shared memory architectures, motivated by applications machine learning, was ushered in by the seminal work of Recht et al.) (2011) (although precursors exist, the references therein). Further work refined this analysis, e.g. (Liu & Wright 2015) and expanded it to nonconvex problems, e.g. (Lian et al., 2015). However, in all of these results, very simplistic model of asynchronous computation is presented analyze the problem. Notably, it is assumed that every block of the parameter, among the set of blocks of iterates being optimized, has a fixed, equal probability of being chosen at every iteration, with certain vector of delays that determine how old each block is that is stored in the cache relative to the shared memory. As one can surmise, this implies complete symmetry with regards to cores reading and computing the different blocks. This does not correspond to asynchronous computation in practice. In particular, in the common Non-Uniform Memory Access (NUMA) setting, practical experience has shown that can be effective for each core to control set of blocks. Thus, the choice of blocks will depend on previous iterates, which core was last to update, creating probabilistic dependence between the delay vector and the choice of block. This exact model is formalized in CCnnelli et al., which introduced a new probabilistic model of asynchronous parallel optimization and presented a coordinate- wise updating successive convex approximation algorithm.

---

Under review as a conference paper at ICLR 2020
In this paper, we interested in studying parallel asynchronous stochastic subgradient descent for general nonconvex nonsmooth objectives, such as the ones arising in the training of deep neural network architectures. Currently, there is work in the literature specifically addressing this problem. The closest related work is given by Zhuu et al. (2018) and & [i 2018). which consider asynchronous proximal gradient methods for solving problems of the form ((x) + g(x), where f is smooth and nonconvex, and g(x) is nonsmooth, with an easily computable closed form prox expression. This restriction applies to the case of training neural network which has no ReLUs or max pooling in the architecture itself, i.e., every activation is a smooth function, and there is an additional regularization term, such as an l1. These papers derive expected rates of convergence. In the general case, where the activations themselves are nonsmooth-for instance in the presence of Rel.UUsthere is no such additive structure, and no proximal operator exists to handle away the non-smoothness and remove the necessity of computing and using subgradients explicitly in the optimization procedure.
This general problem of nonsmooth nonconvex optimization is already difficult (see, c.g., Bagirov et al. (2014). ). and the introduction of stochastically uncertain iterate updates creates an additional challenge. Classically, the framework of stochastic approximation, with stochastic estimates of the subgradient approximating elements in a differential inclusion that defines a flow towards minimization of the objective function, is standard, effective approach to analyzing algorithms for this class of problems. Some texts on the framework include Kushner & Yin (2003), which we shall reference extensively in the paper, and Borkar (2008). See also Ermol' alsolErmol ev & Norkin (1998) and Ruszczyúski (1987) for some classical results in convergence of stochastic algorithms for nonconvex nonsmooth optimization. Interest in stochastic approximation has resurfaced recently sparked by the popularity of Deep Neural Network architectures. For instance, see the analysis of nonconvex nonsmooth stochastic optimization with an eye towards such models in Davis et al. (2018) and Majewski et al. (2018).
In this paper, we provide the first analysis for nonsmooth nonconvex stochastic subgradient methods in parallel asynchronous setting, in the stochastic approximation framework. For this, we employ the state of the art model of parallel computation introduced in Cannelli et al.] which we map onto the analysis framework Kusherr & Yin (2003). We prove show that the generic asynchronous stochastic subgradient methods considered are convergent, with probability 1, for nonconvex nonsmooth functions. This is the first result for this class of algorithms, and combines the state of the art in these two areas, while extending the scope of the results therein. Furthermore, given the success of momentum methods (see, e.g., [Zhang et al.] (2017)) we consider the momentum variant of the classical subgradient method, again presenting the first convergence analysis for this class of algorithms.
We validate our analysis numerically by demonstrating the performance of asynchronous stochastic subgradient methods of different forms on the problem of ResNet deep network training. We shall consider variants of asynchronous updating with and without write locks and with and without block variable partitioning, showing the nuances in terms of convergence behavior as depending on these strategies and properties of the computational hardware.
PROBLEM FORMULATION
Consider the minimization problem
min f(z),
(I)
where f : R" + R is locally Lipschitz continuous (but could be nonconvex and nonsmooth) and furthermore, it is computationally infeasible to evaluate f(x) or an element of the Clarke subdifferential (x))
The problem T has many applications in machine learning, including the training of parameters in deep neural networks. In this setting. fxx is loss function evaluated on some model with x as its parameters, and dependant on input data A E R=xm and target values E RT of high dimension, i.e., f(x) [(:; (A, y)). with a parameter optimize with respect the loss function. In cases of practical interest, f decomposable in finite-sum form,
M
f(x)
1 M
Σ
(m)(;
1=1
where 1: Rm Rm= - R represents the training loss and ((A,, y:}} is partition of (A, y).y).
2

---

Under review as a conference paper at ICLR 2020
We are concerned with algorithms that solve ( in distributed fashion, i..., using multiple processing cores. In particular, we are analyzing the following inconsistent read scenario: before computation begins, each core is allocated block of variables IS, for which it is responsible to update. At each iteration the core modifies a block of variables i*, chosen randomly among I5. Immediately after core completes its k-th iteration, it updates the shared memory. A lock is only placed on the shared memory when a core writes to it, thus the process of reading may result in computations of the function evaluated variable values that never existed memory, c.g., block is read by core then core 3 updates block 2, then core 1 reads block 2, and now block is operating on vector with the values in blocks 1 and 2 not simultaneously at their present local values at any point in time in shared memory. We shall index iterations to indicate when a core writes new set of values for the variable into memory.
We let d = (d" d be the vector of delays for each component of the variable used to evaluate the subgradient estimate, thus the j-th component of that is used in the computation of the update dhe is actually not = but xj""
In this paper, we are interested in applying stochastic approximation methods, of which the classic stochastic gradient descent forms a special case. Since f in (T) is in general nonsmooth, will exploit subgradient methods. Denote by 5 the set of mini- batche used to compute an element of
tlee ); 5*=). The set of minibatches gh is chosen uniformly at random from (A, y). independently at each iteration. By the central limit theorem, the error is asymptotically Gaussian the total size of the data well as the size of the mini-batches increases.
the subgradient g((= "" :....
Asynchronous System Specification. We consider shared-memon memory system with p processes concur- rently and asynchronoully performing computations on independent compute-cores. We interchange- ably use the terms process and core. The memory allows remcuureen-radccccmeuueee--tee access. The shared-memory system offers word-sized atomic r read and fetch- -chhannnaddd (faa) primitives. Processes use faa update the components of the variable.
(CRCW
2.1 ALGORITHM DESCRIPTION
We now recall the stochastic subgradient algorithm under asynchronous updating in Algorithm| | from the perspective of the individual cores. The update of the iterate performed by
Ugke- -ull + 9,k,5
iike
kot1
kec the
(1 mm) R
where is the momentum constant, required to satisfy 0 <
Algorithm Asynchronous Stochastic Subgradient Method for an Individual Core
Input: Tp. core
1: while Not converged do
2: Sample from the variables I, corresponding to c. Sample ç.
3: Read te from the shared memory
4: Compute subgradient estimate *c, local to ke
5: Write, with a lock, to the shared memory vector partition u,k, = m7kkkk + g,kec
6: Update, with a lock, to the shared memory vector partition I,Ke = T,te m)) usre
7: he ke
8: end while
ANALYSIS
For the discrete time probabilistic model of computation introduced in Cannelli et al., we must present the basic requirements that must hold across cores. In particular, is reasonable to expect that some core is entirely faulty, or exponentially deccelerates in its computation, convergence should not be expected to be attained. Otherwise we wish to make the probabilistic assumption
The proposed method will work even if only CREW access is available hecause of partitioning of variables.
3

---

Under review as a conference paper at ICLR 2020
governing the asynchronous update scheduling general as possible in allowing for a variety of possible architectures.
The details of the probabilistic assumptions technical and left to the Supplementary Material. It can be verified that the stochastic approxmation framework discussed in the next section detailing the convergence satisfies these assumptions.
We have the standard assumption about the stochastic sub-grab gradient estimates. These assumptions hold under the standard stochastic gradient approach wherein one samples some subset & S {1, M) of mini-batches uniformly from the set of size [ subsets of {1, M), done independently at each iteration. This results in independent noise each iteration being applied to the stochastic subgradient term. From these mini-batches &, subgradient is taken for each j & and averaged. Assumption 3.1. The stochastic subgradient estimates g(z, {) satisfy.
1. Eg (o(2; {) E 0f B(x)
2. Egg [dist(g(a;; az; E) 0z())) o²
3. (1((2;)) E) & Bg w.p. 1.
where B(x) defines bias term that is zero if f(-) is continuously differentiable at
We provide some more details on the "global" model asynchronous stochastic updating in Supplementary material.
3.1 CONTINUOUS TIME MODEL AND STOCHASTIC PROCESS
In this section, we shall redefine the algorithm and its associated model presented in the previous section in framework appropriate for analysis from the stochastic approximation perspective.
Consider the Algorithm described as such, for data block with respective iteration k.
1 Tu + m))
Σ m YY,,
(2)
where Y5 is the estimate of the partial subgradient with respect to block variables indexed by i at local iteration j.
In the context of Algorithm the step size is defined to be the subsequence {)**t) ((((()) ; } where I the iteration index for the core corresponding to block Thus takes the subsequence of nt for which e i is the block of variables being modified.
The step YR,4 corresponding to g(rk, {) satisfics,
Yo.s = (0 2x- (... P
Bk, + 8M
We denote gs(e (z) to denote selection of some element of the subgradient, with respect to block i, of f(x).. The quantity 8M,, represents a Martingale difference, satisfying 5M,, = M
MR.; for some Martingale Mr, sequence of random variables which satisfies E[M2,1 < x: and E| E[M+-1, < k] = Ma.: with probability I for all k. It holds that Ma. < oo and Mf O. Finally, it holds that Ex,, [ [&M
E[M,11, MMsal[M,-1.
These are standard conditions implied by the sampling procedure in stochastic gradient methods, introduced by the original Robbins-Monro method (Robbins & Monro 1985).
In Stochastic Approximation, the standard approach is to formulate a dynamic system or differential inclusion that the sequence of iterates approaches asymptotically. For this reason, we introduce real time into the model of asynchronous computation, looking at the actual time elapsed between iterations for each block
Define ōTR to be the real elapsed time between the k-th and k + 1-st iteration for block i. We let Tk.: = Σド=o 8ry, and define for a 2 0. ((()) = min Ty 2 a) the first iteration at or after a. We assume now that the step-size sequence comes from underlying real function, i.e.,
Tr (s)
8TK, Te,
4

---

Under review as a conference paper at ICLR 2020
satisfying Jo ((s)ds co, where < (s) + 0 as s + 0c, There are T(s) s such that lim sUPeSIST(s)
2(3) 7(++))
(3)
We now define new a-algebras FR.s and Fr. defined to measure the random variables
(fro), (Y5-1, j, with T3, < T (Tz. J, with T3 I Tk+1,s)) and, { (Y5-1,4 3, with T3 S T (Tz j. with T3 S T++1i))
indicating the set of events up to, and up to and including the computed noisy update at k; respectively,
Note that each of these constructions is still consistent with core updating different blocks at random, with θT arising from an underlying distribution for 8TK,o(i)-
Let us relate these o-algebras to those in the previous section. Note that this takes subsets of random variables (i* , for which & is such that 3 i (in the original notation of k). The form of Yi,; defined above incorporates the random variable d² and gh as in which components are updated and the age of the information used by where the subgradient is evaluated, as well as ç by the presence of the Martingale difference noise.
For any sequence Za.i write Zg, 2p.(o)+k.b where po( is the least integer greater than or equal to a. Thus, let θrg, denote the inter-update times for block i starting at the first update at or after a, and Th. the associated step sizes.
Now let o0, (o), and for l: 2 0, 2 k+1, 2k, + (1 m)hk Σラ=1 k -yy.
k-1 We consider f2 - Tj.t and पे k-1 dr,.
We introduce piecewise constant interpolations of the vectors in real-time given by,
(t) 2h (t) f2.0.
(t) fg tE [TK Th41,)
and (1) = TE for t 17,00 th 1..l We also have,
(T)(((t)) t2. t 10,,077 1..1 2² = 87 (TF (f)) 27(1
Now detail the assumptions the real delay times. These ensure that the real-time delays do not grow without bound, either on average, or on relevantly substantial probability mass. Intuitively, this means that it is highly unlikely that any core deccelerates exponentially in its computation speed. Assumption 3.2. It holds that {ōTg,ö k ii uniformly integrable.
Assumption 3.3. There exists a function u8.1. and random variables k and a random se- quence 11,4 such that
E BTE (4, - 4 A.tt.). v(.1))
and there is such that for any compact set A,
k+m-1
lim m,k.d
Eg +1.) - u, ( (UZZ), ( =
j=k
Assumption 3.4. It holds that,
k4m
lim m.k.a m
17.139 = 0
(4)
This assumption holds if, e.g., the set such that f(.) is not continuously differentiable at x is of measure zero, which is the case for objectives of every DNN architecture the authors are aware of.
5

---

Under review as a conference paper at ICLR 2020
3.2 CONVERGENCE
As mentioned earlier, the primary goal of the previous section is to define a stochastic process that approximates some real-time process asymptotically, with this real-time process defined by dynamies for which at the limit the path converges to a stationary point. In particular, we shall see that the process defined for the iterate time scale approximates the path of differential inclusion,
(t) (.f(x(t))
(5)
and we shall see that this path defines stationary points of f(-)-
We must define the notion of an invariant set for differential inclusion (DI). Definition 3.1. A set A C R" is an invariant set for a DI i g(x) for all E A, there is solution (t). -o0 < oo that lies entirely in and satisfies x: z0)) = 20-
Now state main result. Its complete proof can be found in the Supplementary Material. Theorem 3.1. Let all the stated Assumptions hold. Then, the following system of differential inclusions.
T((1) L. (=((( 1,(1) E (.(((((())) ((())(())) E 0,S((())
(6)
holds for any satissfing 3.3 On large intervals [0,T], 80(())) (.) spends nearly all of its time, with the fraction going to one as oo and a + 00 in a small neighborhood of a bounded invariant set of 55)
This Theorem shows weak convergence. The extension to convergence with probability one is straightforward and described in the Supplementary material.
3.2.1 PROPERTIES OF THE LIMIT POINT
Finally, we wish to characterize the properties of this invariant set. From Corollary 5.11 (Davis et al. 2018). we can conclude that problems arising in training of deep neural network architectures, f(y, aL) with 1(-) one of several standard loss functions, including logistic Hinge loss, and 0; = P (VV((z)); or ===== 11=1.... 1.... L layers, are activation functions, which are piece-wise defined to be log xr e", max (0, x) or log(1 + ex),, are such that their set of invariants (x*) } for its
wherein f())
associated differential inclusion satisfies 0 E af(**) ), and furthermore the values f(**) ) for any iterative algorithm generating {a*} such that = + x", " an invariant of f(z), converge.
Note that the differential inclusions defined above ensure asymptotic convergence to block-wise stationarity, i.e., 0 E 0. (z) for all J. It clear, however, that every stationary point is also block- wise stationary, i.e., that 0 (f)) implies 0 E 0.f(2) for all In practice, the set of block-wise stationary points which are not stationary is not large. One can alternatively consider a variant of the algorithm wherein every core updates the entire vector (thus there is no block partitioning) but locks the shared memory whenever it either reads of writes from it. The same analysis applies to such a procedure. In particular, this amounts to z (1,...77) n,. for all k and every limit of x (1) either + 2o or + oo is a critical point of fxx and, with probability one, asymptotically the algorithm converges a critical point of fxx (i.e., x such that 0f(x)).
NUMERICAL RESULTS
Methods. We describe an experimental evaluation comparing the following algorithms:
WIASSM: Write Inconsistent Asynchronous Stochastic Subgradient Method with lock-free read and updates of øg.i. This procedure applied to smooth stronglyconwer and smooth nonconvex
f(x) known as HogWild! in Recht et al. (2011) and AsySG-incon in Lian et al. (2015). respectively, in the literature. Convergence analysis of Wildi and AsySG-incon additionally required sparsity of x. They have no provable convergence guarantee for nonsmooth nonconvex models.
WCASSM: Write Consistent Asynchronous stochastic subgradient method. WCASSM differs from WIASSM in its use of locks to update Ix,; to make consistent writes. AsySG-con in Lia et al. (2015) its counterpart for smooth nonconvex f(x and sparse sr.

---

Under review as a conference paper at ICLR 2020
1
0.0012
1
0.001
WIASSM
Top1Match %
0.6
CrosEntropyLoos
0.0008
WEASSM
PASSM
TopIMatch %
0.6
0.0006
SGD
0.0004
WIASSM
WIASSM
PASSM
0.0002
WCASSM
8
WCASSM
120
163
200
160
200
80
160
20
Epochs
Epochs
Epochs
(a) Train Accuracy.
(b) Test Loss.
(c) Test Accuracy.
Figure 1: We plotted the train accuracy and generalization (test) loss and accuracy trajectories for the methods. SGD runs single process, whereas the asynchronous methods run 10 concurrent processes. In this set of experiments we have momentum correction. The WIASSM and WCASSM demonstrate better convergence per epoch compared to PASSM. Note that, the single process executing of GPUs PASSM matches that of SGD inferring that
SGD iterations has better opportunity to CUDA threads there is concurrent by multiple processes. The per epoch performance amount of subgradient updates are almost identical: in the former it is done collectively by all the concurrent processes accessing disjoint set of tensors, whereas, in the latter it is done by a single process using comparable amount of parallization.
0.001
SGD
Top1Match
0.8
CrostEntopyLos
0.0006
0.0008
WIASSM
PASSM WCASSM
Mop1Match %
0.6
0.8
SGD
SGD
WIASSM
0.0004
0.4
WIASSM
PASSM
0.0002
PASSM
WCASSM
WCASSM
200
160
200
160
200
Epochs
Epochs
Epochs
(a) Train Accuracy.
(b) Test Loss.
(c) Test Accuracy.
Figure 2: Same setting as Fig We used a momentum = 0.9. It can be observed that with momentum correction the convergence of PASSM improves significantly. Mitliagkas et al. |Mitliakaa) et al. 2016) experimentally showed that the degree of asynchrony directly relates to momentum; our experiments show that the relative gain in terms of convergence per epoch momentum correction is better for PASSM that exhibits more asynchrony compared to WCASSM, which uses locks for write consistency.
PASSM: The presented Partitioned Asynchronous Stochastic Subgradient Method. We read as well as update æg,; lock-free asynchronously.
SGD: Sequential data-parallel Stochastic Gradient Descent method.
Elyper-parameters. For each of the methods, adopt a decreasing step size strategy * (ad x 7)/Vk, where a >> is constant for the jth processing core. is fixed initially. In each of the methods we use an L2 penalty in the form of a weight-decay of 0.0005. Additionally, introduced L1 penalty of 0.0001 that simply gets added the gradients after it has been put through the L. penalty. accordance with the theory, we explored the effect of momentum correction: we have two of benchmarks, one without momentum and another with a constant momentum of 0.9 while checking the convergence with epochs. In all of the above methods we load particular, learning rate
the datasets in mini-batches of size 64. We keep the hyper-parametent and mini-batch-size identical across methods for the sake of statistical fairness. In a shared-ment memoryy setting, there is not much to exploit on the front of saving on communication cost as some existing works do Goyal et al. (2017); and the computing units, see the system setting and the implementation below, are anyway utilized to their entirety by way of efficient data patt--paallelization.
Dataset and Networks. We used CIFAR data set RGB images Krizhevsky (2009). It contains 50000 labeled images for training and 10000 labeled images for testing. We trained well known
7

---

Under review as a conference paper at ICLR 2020
0.0012
0.001
0.0012
SGB
GouuErespyoos
0.0000
GrovEitrooooos
WCASSM
0.0000
0.0006
0.0000
WICSSMDD
0.0006
0.0006
0.000M
0.0004
0.0001
0.0000
0.0000
0.0000
0
10
15
Minutes
Minutes
Minutes
(a) SGD vs. HW.
(b) SGD vs. PASSM.
(c) SGD vs. ASSM.
Figure 3: This set of figures presents the train-loss trajectory against time (in minutes) while comparing asynchronous methods- running 5 and 10 concurrent processes with sequential SGD, We used momentum = 0.9 in each of them. As described, a separate concurrent process keeps on saving snapshot of the shared model an interval of minute, simultancously with the training processes. Firstly, it can be observed that the convergence of PASSM is faster compared to the other two asynchronous methods for identical number of processes. This can be understood in terms of block partitioning the model across processes: it helps reducing the synchronization cost and thereby potentially speeds up the data processing per unit time. Furthermore, we clearly gain in terms of convergence per unit time when we increase the number of processes in PASSM. In contrast, we note that the use of locks by WCASSM actually slows it down when we increase the number of processes. This set of experiments demonstrate that PASSM has better convergence with respect to wall-clock time in addition to the scalability with parallel resources.
CNN model Resnet18 8 He et al. (2016). ResNet18 has a blocked architecture - of residual blocks totaling 18 convolution layers. Each residual block is followed by a ReLU activation causing non- linearity. Evidently, training of this neural network offers general nonsmooth nonconvex optimization problems.
System Specification. We benchmarked the implementations on NUMA workstation 2 sockets, 10 cores apiece, running 2.4GHz (Intel(R) Xeon(R) E5- 2640), HT enabled 40 logical cores, Linux 1.18.0-0.bo.. 1-amd64 (Debian 9) containing 4 Nvidia GeForce GTX 1080 GPUs. For fair evaluation of scalability with cores, we bind the processes restricting their computations in particular, the cost of data load to individual CPU cores. In this setting, to evaluate the scalability with respect to wall-clock-time by increasing the availability of parallel resources, we run the experiments with and 10 processes, which do not migrate across CPU sockets. For evaluation with respect to time, we employed a separate concurrent process that keeps on saving a snapshot of the shared model at an interval of 1 minute.
Asynchronous Implementation. We implemented the asynchronous methods using the open-source Pytorch library Paszke et al. (2017) and the multi-processing framework of Python. Given the multi- GPU environment, which could excellently exploit data- Satalparallll computation, therefore, we used the nn Dat aP arallel () module of Pytorch library. Thereby, CNN instance is centrally allocated on one of the GPUs and computations - forward pass to compute the model over a computation graph and backward pass to compute the sub-gradients thereon employ peer GPUs by replicating the central instance on them for each mini-batch in a data-pat data-parallel way. Effectively, the computation of stochastic subgradients happen over each GPU and they are summed and added to the central instance. Note that, this way of implementation exploits parallel resources while effectively simulating a shared- memory asynchronous environment.
Model Partitioning. Unlike PASSM, the methods WIASSM, WCASSM and SGD do not partition the model and compute the stochastic subgradients over the entire computation graph of a CNN via backpropagation provided by the autograd module of Pytorch. PASSM partitions the list of leaves, which are tensors corresponding to the weights and biases, of the computation graph into blocks. While computing the stochastic subgradients with respect to a block, we switch off the requires_grr flag of the tensors corresponding to other blocks during backpropagation. This particular implementation component results in some savings in stochastic sub- -oodggrddeett computation with respect layers relatively closer to the output. Keeping this in view, we assigned blocks containing 8; 2 [L/p] parameter components, where L is the model size and p is the number of processes, to the processes P. computing stochastic sub- aub-gradients corresponding to layers closer to output. Whereas, the process that computes sub- aab-gradient of the layer-block closest to the input is assigned a block containing less than [L/p] parameter components. The assignments 8; aim balance computation
8

---

Under review as a conference paper at ICLR 2020
0.8
0.7
ToptMachh
0.8
ToptMecch-%
0.8
0.6
0.5
0.4
+ Massm((ps)
Top
0.3
WEASSM
0.2
0.2
P45SMig100
WCASSM/--101
Minutes
Minutes
Minutes
(a) SGD vs. HW.
(b) SGD vs. PASSM.
(c) SGD vs. ASSM.
Figure 4: Same setting as in the Fig momentum 0.9, We plotted test-accuracy in terms of Top1 correct match % vs time (in minutes). In can be observed that PASSM offers faster convergence per unit time in accuracy well compared to the other two asynchronous methods.
load, however, it varies across layers depending on the size of the assigned leaves in terms of parameter component. Nevertheless, blocked architecture such as ResNet does not allow much scope of computation-cost saving on this count: we observed an insignificant difference in average processing time for the same number of epochs irrespective of switching off the requi i res_gre grad flag. Notice that, this is not model parallelization and the stochastic subgradient computation with respect to a leaf depends on the computation path leading to the output. Irrespective of partitioning the model, the multi-GPU-bases data-parallel implementation utilizes replication and data partitioning over GPUs while processing mini-batch.
The experimental observations are described in Figures
and
Summary. The block partitioning design of PASSM has its efficiency in the following: 1) it reduces the cost of optimization per process, since the parameter partitioned. Note that, in case of neural networks, where backpropagation processes almost the entire computation graph irrespective of the location of the leaf, in particular in a blocked architecture such as ResNet, PASSM clearly misses out saving subgradient computation cost by way of parallelization: it can be significantly better if the subgradients with respect to the blocks could be computed independently; and 2) reduces memory traffic and potential write conflicts between processors which we observe in terms of better convergence per unit time. And finally, it is pertinent to highlight that we also observed that momentum correction improves the convergence per epoch of the block partitioning approach whose performance was way lower if we did not use it.
5 DISCUSSION AND CONCLUSION
In this paper we analyzed the convergence theory of asynchronous stochastic subgradient descent. We found that the state of the art probabilistic model on asynchronous parallel architecture applied to the stochastic subgradient method, with and without the use of momentum, consistent with standard theory in stochastic approximation and asymptotic convergence with probability one holds for the method under the most general setting of asynchrony.
We presented numerical results that indicate some possible performance variabilities in three types of asynchrony: block partitioning inconsistent read (for which the above convergence theory applies), full-variable-updae consistent write (for which the above convergence theory also applies), and full-variable-update inconsistent read/write (for which no convergence theory exists).
REFERENCES
Adil Bagirov, Napsu Karmitsa, and Marko M Mäkelä. Introduction to Nonsmooth Optimization: theory, practice and software. Springer, 2014.
Billingsley. Convergence of probability measures. Wiley, 1968.
Patrick Billingsley. Convergence of probability measures. John Wiley & Sons, 2013.
Vivek S Borkar. Stochastic approximation: dynamical systems viewpoint. Baptism's 91 Witnesses, 2008.
Loris Cannelli, Francisco Facchinei, Vyacheslav Kungurtsev, and Gesualdo Scutari. Asynchronous parallel algorithms for nonconvex optimization. Mathematical Programming, pp. 1-34.

---

Under review as a conference paper at ICLR 2020
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D Lee. Stochastic subgradient method converges on tame functions. arXiv preprint arXiv:1804.07795, 2018.
Paul Dupuis and Harold Kushner. Stochastic approximation and large deviations: Upper bounds and wp convergence. SIAM Journal on Control and Optimization, 108-113, 1989.
Yu M Ermol' ev and VI Norkin. Stochastic generalized gradient method for nonconvex nonsmooth stochastic optimization. Cybernetics and Systems Analysis, 34(2):196-215 1998.
Stewart N Ethier and Thomas G Kurtz. Markov processes: characterization and convergence, volume 282. John Wiley & Sons, 2009.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016.
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training imagenet in 1 hour. CoRR, abs/ 706.02677, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Tech Report, 2009.
Harold Kushner and G George Yin. Stochastic approximation and recursive algorithms and applica- tions, volume 35. Springer Science & Business Media, 2003.
Zhize and Jian Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 5564-5574, 2018.
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 2737-2745, 2015.
Liu and Stephen J Wright. Asynchronous stochastic coordinate descent: Parallelism and conver- gence properties. SIAM Journal on Optimization, 25(1):351-376, 2015.
Szymon Majewski, Blažej Miasojedow, and Eric Moulines. Analysis of nonsmooth stochastic approximation: the differential inclusion approach. arXiv preprint / 2018
Ioannis Mitliagkas, Ce Zhang. Stefan Hadjis, and Christopher Ré. Asynchrony begets momentum, with application to deep learning. In 2016 54th Annual Allerton Conference Communication, Control, and Computing (Allerton), pp. 997-1004, 2016.
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.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances neural information processing systems, pp. 693-701, 2011.
Herbert Robbins and Sutton Monro. A stochastic approximation method. In Herbert Robbins Selected Papers, pp. 102-109. Springer, 1985.
Andrzej Ruszczyíski. A linearization method for nonsmooth stochastic programming problems. Mathematics of Operations Research, 12(1):32-49, 1987.
Jian Zhang, Joannis Mitliagkas, and Christopher Ré. Yellowfin and the art of momentum tuning. CoRR, abs/ 706.0371, 2017.
Rui Zhu, Di Niu, and Zongpeng Li. Asynchronous stochastic proximal methods for nonconvex nonsmooth optimization. arXiv preprint IrXiv:1802.08800 2018.
10

---

Under review as a conference paper at ICLR 2020
6 APPENDIX A: GLOBAL SHARED MEMORY ASYNCHRONOUS STOCHASTIC SUBGRADIENT MODEL
Here we give a few more details describing the relation of the probabilistic model of asynchrony to the underlying hardware properties, as modeled in Cannelli et al.
In this section, we present & as a global counter, indicating sequential updates of any block among the variables.
In iteration k the updated iterate z+ depends on random vector Ç* - (d",d" ). The distribution
of < depends on the underlying scheduling or message passing protocol. We use the following formulation, which applies to a variety of architectures.
S*) be the stochastic process representing the evolution of the blocks and minibatches used, as well as the iterate delays. The o-algebra is obtained as follows. Let the cylinder C* ( & {w E wotk = < and define j - (C*) and F & o the
Let ço:e A
cylinder o-algebra on f2.
Consider the conditional distribution of ck+1 given ço:kk
(CC*+1(00R+))
P( 0 ((C()((ok))
we have the following assumptions on the probabilities of block selection and the delays, Assumption 6.1. The random variables ç* satisfy,
1. There exists a such that d S 8 for all j and k. Thus each d E D a {o...., 53".
2. For all i and c0ck-1 such that pça. 1 ((C > O, holds that,
Σ dED
P( (((+,d,))l( 2 Pmin
for some pmin O.
3. It holds that,
p p ((CER:: lim Pn((s of)
The first condition indicates that there is some maximum possible delay in the vectors, that each element of used in the computation of s.11 is not too old. The second is an irreducibility condition that there is positive probability for any block or minibatch be chosen, given any state of previous realizations of {C*}. The last assumption indicates that the set of events in Ω that asymptotically go to zero in conditional probability are of measure zero.
In order to enforce global convergence, we wish to use a diminishing step-size. However, at the same time, as synchronization is to be avoided, there must not be a global counter indicating the rate of decrease of the step-size. In particular, each core will have its own local step size " .A) where c is the core, and, defining the random variable 2 as the component of (1...., 2) that active at iteration k. the random variable denoting the number of updates performed by core cx, denoted by ukk) is given by vkk A Σ I(Z' )²).
In addition, noting that it has been observed that in practice, partitioning variable blocks across cores more efficient than allowing every processor to have the ability to choose across every variable block (Liu & Wright 2015). Thus partition the blocks of variables across cores. We can thus denote R as being defined uniquely by it, the block variable index updated iteration
*t ()
Note that lim inf
in probability is implied by
Σ
Pr((i, ()) +
iEck dED.
11

---

Under review as a conference paper at ICLR 2020
for some subsequence, which is antithetical Assumption 3.1, Part 2. Thus, note that the stepsizes gotc" .) satisfy, where the limit of the sequence taken in probability,
2 R)
lim
0,
R-000
which is assumption for the analysis of asynchronous parallel algorithms in Borkar (2008).
We are now ready to present Algorithm perspective.
2 This presented from the "global" iteration counter
Algorithm Asynchronous Stochastic Subgradient Method
Input: 20.
1: while Not converged and kt < kimux do
2: Having realized ço:k sample {5t
(it, (
3: Update MA2 mux. + g((=1 d4 I2 ,...,
In eh) J (1 m)) u
d2
de
4: Update z/ k+1
5: Set & = k: +
6: end while
APPENDIX B: PRELIMINARY ASSUMPTIONS AND LEMMAS
Lemma 7.1. It holds that (Yaas (Y is uniformly integrable. Thus, so is aok-iyg;ke 3,8 k,
[ m² Aa-jj -y Ejmn m
Proof. Uniform integrability of {Yr,s, Yg, k. integrability {ΣA=1 m m E m 3,3 k; i} follows from 0 < m < 1 and the fact that geometric sum of uniformly integrable sequence is uniformly integrable.
i} follows from Assumption 3.2, part 3. The uniform
Lemma 7.2. It holds that, for any K > O, and all 1,
sup kcK
Σ
T + 0
j=k-
in probability as a + cc.
Proof. As o + cc, by the definition of Th. Nh. - 0 and since by Assumption 3.1 max di 8, for
all k K, E Th. < 0r O.
(e
Now we define some terminology arising in the theory of weak convergence. We present result indicating sufficient conditions for property called tightness.
Theorem 7.1. (Kushner Yin 2003 Theorem 7.3.3) Consider a sequence of processes (Ax(-) with paths in D(- xc) such that for all 0 and each t in dense set of (-20, oo) there is compact set Ks.t such that.
inf P (t) K5.1] 2 1 1 5,
for any T x>0 O,
lim lim sup sup sup E [min [[An(T +) A.(T),, 0
n IrisT $58
then (Ax()) is tight in D o0)
12

---

Under review as a conference paper at ICLR 2020
If a sequence is tight then every weak sense limit process is also continuous time process. We say that (t) converges weakly to if,
LE -
for any bounded and continuous real-valued function F(-) on R"
Weak convergence is defined in terms of the Skorohod topology, a technical topology weaker than the topology of uniform convergence on bounded intervals, defined in [Billingseyy (1968). Convergence of a function fn (-) to f()) in the Skorohod topology is equivalent to uniform convergence on each bounded time interval.
denote by [1 oo) the j-fold product space of real-valued functions on the interval [0, oc) that are right continuous with left-hand limits, with the Skorohod topology. It is complete and separable metric space.
Much of the proof of the main Theorem can be taken from the analagous result in Chapter 12 of Kush ner & Yin (2003), which considers a particular model of asynchronous stochastic approximation. As introduced slightly different model from the literature, some of the details of the procedure are now different, and furthermore we introduced momentum to the algorithm, and thus in the next section indicate how treat the distinctions in the proof and show that the result still holds.
APPENDIX C: PROOF OF THEOREM
By Theorem 8.6, Chapter 3 in Ethier & Kurtz (2099) sufficient condition for tightness of
sequence {An(-)) } is that for each ò O and each I in dense set in (-o0, (x),,,), there a compact set Kg,, such that inf, (1) E K&,]] 2 5 and for each positive T, lims-+ lim sup,, suppr|sT, E [T + s) An(T))]= = 0.
Now since YE,5 is uniformly bounded, and YE,() (-) is its interpolation with jumps only at being equal to some TR it holds that for all i,
lim lim sup P
sup STT
(t [ (t) 2 =0
and by the definition of the algorithm,
lim lim sup IP
sup 1T $58
(t, + 8) 22,(()] 2 1) =0
which implies.
lim lim sup E 6-10
sup 1ST,s56
10 (1 + =2,(001 =0
and the same argument implies tightness for (T(()), N7, Nz)()) by the uniform boundedness of {8Tīke and bounded, decreasing Th, and positive ug, (z, o 1. along with Assumption 3.4. Lipschitz continuity follows from the properties of the interpolation functions. Specifically, the Lipschitz constant of xzf (.) is By-
All of these together imply tightness of a.) as well. Thus,
{x7 (2), 77 ()) (7), NT)):)
tight in 4 oo). This implies the Lipschitz continuity of the subsequence limits with probability one, which exist in the weak sense by Prohorov's 's Theorem, Theorems 6.1 and 6.2 (Billingsley 2013).
As - oo we denote the weakly convergent subsequence's 's weak sense limits by,
()))).
Note that,
(x(()) = (1) #x(1) = (N), (t(T((t)) -t.
13

---

Under review as a conference paper at ICLR 2020
For more details, see the proof of Kushner & Yin 20033 Let,
Theorem 8.2.1).
(1) = Ek=r (1 m)ôTE, Ei= m m
(t) = =K IkEp(o) ÖTh, (1 m) Ej ml ( A k-j-ld 9)1.1 (t)
26 kk-j-ldh-11 "155 (t) (t),.., DK I ()) ( (t))
(1) = )k=p(o) 8T (f" (t))
(1) -()) 20 (1 m) TTK Ei
= (T) 0i,0
(t) = (t) (t)
Now for any bounded continuous and real-valued function h(-), ) an arbitrary integer p, and and t, and 8j 2 real, have
E (TT (s)) (V(())
E (GE
- Gt
My)
E[h(T (8,), 2 ((++)))))
Now the term involving M equals zero from the Martingale property. The term involving 8 is
zero due Assumption 3.4
We claim that the term involving G goes by Lemma 7.2 (1 (t), ..., 2f ia 1 (t) (t), + I- + (t) well. By the upper semicontinuity of the subgradient, it holds that there exists (2) E 0:f( (t)) such that 2h -4
well. Since =k,; + x; it holds that,
g:((0g h (1) 2l (. g. (*g((t)
as a - oo. Thus each term in the sum converges to ge (;( (4)). Now, given j. as k co, the boundedness assumptions and stepsize rules imply that 9, (t) + gi(()())). On the other hand 1-m" as l: > oc and j + oo, m² gi ( + O. Thus Σ m² (x% - 1-m (#) > I-m 9. (.g and the claim has been shown.
Thus the weak sense limit of lim WT(-) Wi(+) satisfies
E [M(r)(s)), (((()())) (Wi(t
W(()))
and thus by Kushner & Yin (2003 Theorem 7.4.1) is martingale and is furthermore a constant with probability one by the Lipschitz continuity of by Kushner & Yin 2003 Theorem 4.1.1). Thus,
W(I) = +() a(0) S (((())) = 00
where g(t(s)) E (f((s))) and the conclusion holds.
CONVERGENCE WITH PROBABILITY ONE
The previous Theorem showed that under the conditions described the algorithm, there a weakly convergent subsequence to an invariant set. We can now use the results in Dupuis & Kushner' (1989) to infer from weak convergence, probability one convergence the sequence of iterates.
For this, shall use the machinery developed in Dupuis & Kushner (1989), which establishes conditions for which a weakly convergent stochastic approximation algorithm approximating continuous ODE converges with probability one, under certain conditions. One study the proof structure to quickly reveal that with minor modifications the results carry through. In particular, when b appears the proof, one can replace it with an element the differential inclusion, and the limit point is replaced by the invariant set. Assumption 2.1 in Dupuis & Kushner (1899) is now associated
14

---

Under review as a conference paper at ICLR 2020
with set-valued map Stx, Φ), and by the noise structure of the assumptions, it can easily be that exists for all possible values of x T and & in the notation of the paper. One can see that the uniqueness appears once in the beginning of the proof of Theorem 3.1 with the existence of this I such that the trajectory lies in a specific ball around the limit point for f 2 Ti. This can be replaced by the trajectory lying in this ball around the invariant set, for Ti defined the supremum of such Ti associated with every possible subgradient, i.e., element of the DI. Since the subgradient is compact set and is upper semicontinuous, this supremum exists. Finally, note that Assumption 3.2 is as Assumption 4.1 in Dupuis & Kushner (1989) and thus similarly implies Theorem 4. and Theorem 5.3. This proves that as -> w.p.1 x (.) converges to invariant set of the differential inclusion.
15


Reviews:
[{"review_id": "ryeuKR4lqH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a convergence analysis for asynchronous optimisation in the case where non-smoothness imposes the use of sub gradients and non-convexity (combined with asynchrony) introduces more challenging staleness (delay) issues than in the convex case.\n\nstrength:\nthe paper tackles one of the hardest settings to be analysed in distributed optimisation, and packages it in a readable continuous-time framework.\n\nweakness: \nas far as I went into the details, I couldn't understand how the authors tackle one the biggest problem in non-convex + asynchrony: coherence of gradients. \n\nSpecifically, my sole question to the authors is how does their analysis take into account (sub)gradients that are delayed *and* not in the same half-space as the current non-biased estimator of the gradient ? These (sub)-gradients will act in an almost malicious manner. (as usual in distributed computing, where asynchrony can be modelled by a malicious scheduler).\nMaybe my reading made me miss where this is handled, if a precise pointer is given I will upgrade my score.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1lhLbyaFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a model to study asynchronous stochastic subgradient methods for minimizing a nonsmooth nonconvex function. Studying stochastic subgradient methods in the nonsmooth nonconvex setting is already very challenging. Throwing asynchronous updates into the mix further complicates the analysis. This is overcome by proposing a model for asynchrony which captures the salient features of computation platforms, while being amenable to analysis.\n\nThe main drawback of this paper is that the experiments seem to suggest that, although asynchronous methods do a good job optimizing training metrics (loss, accuracy), the models they train do not generalize as well as using synchronous SGD. This demotivates the need for the theory developed in this paper - rather, the theory is ahead of it's time. The paper could be significantly strengthened by reporting an example application where using an asynchronous stochastic subgradient method is advantageous for training deep networks.\n\nThe notation and discussion in Sec 3.1 is pretty heavy. Can you explain how this model differs from other models of asynchrony, e.g., as put forward in the well-known book by Bertsekas and Tsitsiklis on Parallel and Distributed Computation?\n\nThe main convergence result (Theorem 1) holds for a continuous-time process, following the typical analysis of stochastic approximation algorithms. However, practitioners rarely use a diminishing step size, especially for training deep networks. Is it possible to quantify the effect of using a constant step size? (E.g., in stochastic approximation analyses for smooth functions, one typically gets a \"law of large numbers\" which ensures convergence of the average, and a \"central limit theorem\" which bounds the distance of any realization of the process to its mean. Is there an analogous CLT for this setting?)\n\nIn the experiments, the SGD with DataParallel is effectively using a mini-batch size that is 3-5x larger than that of a single worker. In this case one would expect to be able to use a larger learning rate too (since there is less noise). Evidence for this is provided in Goyal et al., \"ImageNet in 1 hour\". Did you try tuning the learning rate separately for each method?\n\nHow were the parameters of the deep CNNs used in the experiments divided into blocks? This choice should affect the average time to evaluate a block gradient, right? Computing the gradient of parameters in the lowest layer requires doing a full forward and backward, while computing the gradient of higher layers should be faster since it doesn't require a full backward pass. Did you measure the average time to compute a block gradient, and could you report it in the paper? Did you divide into blocks based on layer? Are all parameters within the same block part of the same filter at a given layer?\n\nThe last paragraph of Sec 4 talks about the necessity of momentum, but it isn't clear what evidence this claim is based on.\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1ekmR9sFB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes convergence of asynchronous methods on general non-smooth and non-convex functions (typically arising from deep leaning). Stochastic sub-gradient asynchronous methods are of particular challenging when coupled with complicated hardware behavior of modern NUMA architecture. To validate the analysis, and study the impact of momentum, variable partitioning, numerical experiments on deep learning training are given.\n\nA major concern to me is that the assumptions made in the analyze may be too restrictive. For example, Assumption 3.1.1 regarding the unbiasedness of the stochastic sub-gradients may not hold for since the Clarke sub-differentiation is not additive. The Clarke sub-differentiation of |x| and -|x| are not included in their average which is zero, therefore the Assumption 3.1.1 is not true for tame functions (as cited in the paper) . If this assumption were not true, all the proof arguments based on Martingale differences may not be follow to prove Theorem 3.1. \n\nThere are a few typos which make the paper hard to understand. Is the momentum variable  u_i^kc in Algorithm 1 a central variable, as x_i? It seems to be yes since the update needs a lock. But why there is an kc on its index, which is not the case for x_i? \n\nIn terms of numerical results, the system specification is not so clear to me why it includes a diverse asynchronous system settings. Even though Figure 1 shows convergence in terms cross-entropy loss, which is not directly related to validate Theorem 3.1 since it is not clear what is going on with x_t.\n\nThe paper would be of great interest if the global shared memory asynchronous model is made more precise in the main body of the paper. At a first glace, it is not clear what is the benefit (or what insights) using this model to analyze these algorithms, compared to simplistic models in literature. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers an interesting theoretical question. However, it would add to the strength of the paper if it was able to meaningfully connect the considered model as well as derived methodology to the challenges and performance that arise in practice. 
Decision: Reject