Understanding the effects of data parallelism and sparsity on neural network training
Authors: Namhoon Lee
Thalaiyasingam Ajanthan
Philip Torr
Martin Jaggi
Venue: ICLR 2021 Poster (2021)
Keywords: data parallelism
sparsity
neural network training

Abstract: We study two factors in neural network training: data parallelism and sparsity; here, data parallelism means processing training data in parallel using distributed systems (or equivalently increasing batch size), so that training can be accelerated; for sparsity, we refer to pruning parameters in a neural network model, so as to reduce computational and memory cost. Despite their promising benefits, however, understanding of their effects on neural network training remains elusive. In this work, we first measure these effects rigorously by conducting extensive experiments while tuning all metaparameters involved in the optimization. As a result, we find across various workloads of data set, network model, and optimization algorithm that there exists a general scaling trend between batch size and number of training steps to convergence for the effect of data parallelism, and further, difficulty of training under sparsity. Then, we develop a theoretical analysis based on the convergence properties of stochastic gradient methods and smoothness of the optimization landscape, which illustrates the observed phenomena precisely and generally, establishing a better account of the effects of data parallelism and sparsity on neural network training.

Published as a conference paper at ICLR 2021
UNDERSTANDING THE EFFECTS OF DATA PARALLEL- ISM AND SPARSITY ON NEURAL NETWORK TRAINING
Namhoon Lee
Thalaiyasingam Ajanthan
University of Oxford namhoon robots... ac.uk
Australian National University
thalad yas ingama
janthan@amu i edu.
Philip H. S. Torr
Martin Jaggi
University of Oxford
EPFL martin. jaggieepl.ch
phst@robots aw.
ABSTRACT
We study two factors neural network training: data parallelism and sparsity: here, data parallelism means processing training data in parallel using distributed systems (or equivalently increasing batch size), so that training can be accelerated; for sparsity, we refer to pruning parameters in neural network model, so as to re- duce computational and memory cost. Despite their promising benefits, however, understanding of their effects neural network training remains elusive. In this work, we first measure these effects rigorously by conducting extensive experi- ments while tuning all metaparameters involved in the optimization. As result, we find across various workloads of data set, network model, and optimization algorithm that there exists a general scaling trend between batch size and number of training steps to convergence for the effect of data parallelism, and further, dif- ficulty of training under sparsity. Then, we develop theoretical analysis based on the convergence properties of stochastic gradient methods and smoothness of the optimization landscape, which illustrates the observed phenomena precisely and generally, establishing better account of the effects of data parallelism and sparsity on neural network training.
INTRODUCTION
Data parallelism is a straightforward and common approach to accelerate neural network training by processing training data in parallel using distributed systems. Being model-agnostic, is applicable to training any neural networks, and the degree of parallelism equates to the size of mini-batch for synchronized settings, contrast to other forms of parallelism such as task or model parallelism. While its utility has attracted much attention in recent years, however, distributing and updating large network models at distributed communication rounds still remains a bottleneck (Dean et al, 2012 Hoffer et al. 2017 Goyal et al. 2017 Smith et al. 2018 Shallue et al. 2019 Lin et al. 2020)
Meanwhile, diverse approaches to compress such large network models have been developed, and network pruning the sparsification process that zeros many parameters of network to reduce computations and memory associated with these zero values - has been widely employed (Reed) 1993 Han et al.) 2015). In fact, recent studies discovered that pruning prior to training Lee et al.) 2019 Wang et al. 2020), and by separating the training process from pruning entirely, not only saves tremendous time and effort in finding trainable sparse networks, but also facilitates the analysis of pruned sparse networks in isolation. Nevertheless, there has been little study concerning the subsequent training of these sparse networks, and various aspects of the optimization of sparse networks remain rather unknown of yet.
be done at initialization
In this work, we focus on studying data parallelism and sparsity] and provide clear explanations for their effects neural network training. Despite surge of recent interest in their complementary
For the purpose of this work, equate data parallelism and sparsity to increasing batch size and pruning model parameters, respectively; explain these more in detail in Appendix B

---

Published as a conference paper at ICLR 2021
benefits in modern deep learning, there is lack of fundamental understanding of their effects. For example, (Shallue et al. (2019) provide comprehensive yet empirical evaluations on the effect of data parallelism, while Zhang al. (2019) use simple noisy quadratic model to describe the effect; for sparsity, [ee et al. (2020) approach the difficulty of training under sparsity solely from the perspective of initialization.
In this regard, we first accurately measure their effects by performing extensive metaparameter search independently for each and every study case of batch size and sparsity level. As result, we find a general scaling trend as the effect of data parallelism in training sparse neural networks, across varying sparsity levels and workloads of data set, model and optimization algorithm. Also, the critical batch size turns out to be no less with sparse networks, despite the general difficulty of training sparse networks. We formalize our observation and theoretically prove the effect of data parallelism based on the convergence properties of generalized stochastic gradient methods irre- spective of sparsity levels. We take this result further to understand the effect of sparsity based on Lipschitz smoothness analysis, and find that pruning results in a sparse network whose gradient changes relatively too quickly. Notably, this result is developed under standard assumptions used in the optimization literature and generally applied to training using any stochastic gradient method with nonconvex objective and learning rate schedule. Being precise and general, our results could help understand the effects of data parallelism and sparsity on neural network training.
SETUP
We follow closely the experiment settings used in Shallue al. (2019). We describe more details including the scale of our experiments in Appendix BJ and provide additional results in Appendix D The code can be found here: http:////ttbb.coo//mmmmmoollle//
Experiment protocol. For given workload (data set, network model, optimization algorithm) and study (batch size, sparsity level) setting, we measure the number of training steps required to reach a predefined goal error. We repeat this process for budget of runs while searching for the best metaparameters involved in the optimization (e.g., learning rate, momentum), so as to record the lowest number of steps, namely steps-to-result, as our primary quantity of interest. To this end, we regularly evaluate intermediate models on the entire validation set for each training run.
Workload and study. We consider the workloads as the combinations of the followings: (data set) MNIST, MaShi, CIFAR-IO; (network model) Simple-CNN, ResNet-8; (optimization algorithm) SGD, Momentum, Nesterov with either a fixed or decaying learning rate schedule. For the study setting, we consider a batch size from 2 up to 16384 and a sparsity level from 0% to 90%.
Metaparameter search. We perform quasi-random search tune metaparameters efficiently. More precisely, we first generate Sobol low-discrepancy sequences in a unit hypercube and convert them into metaparameters of interest, while taking into account predefined search space for each metaparameter. The generated values for each metaparameter is in length of the budget of trials, and the search space is designed based on preliminary experimental results.
Pruning. Sparse networks can be obtained by many different ways, and yet, for the purpose of this work, they must not undergo any training beforehand as measure the effects of data parallelism while training from scratch. Recent mruningat--inittalizatio approaches satisfy this requirement, and we adopt the connection sensitivity criterion in Lee et al. (2019) obtain sparse networks.
EXPERIMENTAL RESULTS
3.1 MEASURING THE EFFECT OF DATA PARALLELISM
First of all, we observe in each and every sparsity level across different workloads general scaling trend in the relationship between batch size and steps-to-result for the effects of data parallelism (see the 1st and 2nd columns in Figure I): Initially, we observe period of linear scaling where doubling the batch size reduces the steps to achieve the goal error by half (i.e., it aligns closely with the dashed line), followed by region of diminishing returns where the reduction in the required number of steps by increasing the batch size is less than the inverse proportional amount (i.e., it starts to digress from the linear scaling region), which eventually arrives maximal data parallelism (i.e., it hits
2

---

Published as a conference paper at ICLR 2021
Sparsit:: 0%
Sparsity: 90%
All sparsity
All sparsity (normalized)
211
Neader Vee Tpanky
Spansty 39%
Staps 26
2:1
Stape
Stepp
211
Stesps
214
2
27
2-1
size
size
size
Batch
(a) MNIST, Simple-CNe CNN, SGD
Sparsity: 0%
Spariiyy 90%
All sparsity
All sparsity (normalized)
2M
Spadly
%/
201
adly
bpasly
Staps
Staps
14
Batch
Batch
Batch
Batch
(b) MNIST, Simple-CNN, Momentum
Sparsity:
Sparsity:
sparsity
sparsity (normalized)
Spares Ph
Spanis
Spanity X01
1/2
Steps
Steps
Stops
27
27
24
Batch Size
Batch size
Batch size
Batch size
(c) Rashion-MNIST, Simple-CNNy CNN, Momentum
Sparsity:
Sparsity:
All sparsity
sparsity (normalizee)
Jearto Spartto
Spants
21
Stepss 7
Spanty X01
211
Steps
Steps
Batch size
Batch size
Batch size
(d) CIFAR- 10, Re Nesterov
Figure 1: Effects of data parallelism and sparsity neural network training for various workloads with a fixed (a-c) or decaying learning rate (d). Across all workloads and sparsity levels, the same scaling pattern is observed for the relationship between batch size and steps-to-resule tosuutt it starts with the initial phase of linear scaling, followed by the region of diminishing returns, and eventually reaches to maximal data parallelism. Also, the effect of data parallelism in training sparse networks is no worse than that of the dense counterpart, despite the general difficulty of training the former. When training using momentum based SGD,, the breakdown of the linear scaling regime often occurs much later at larger batch sizes for a network with higher sparsity. For example, in the case of workload (MNIST, Simple-CNN, Momentum), J, the critical batch size for the sparsity 90% network is around 2 whereas it is 2 for the sparsity 0% network (see the 4th column in row (b)). This potentially indicates that one can exploit large batch sizes more effectively when training sparse networks than densely parameterized networks. We supply more results in Appendix D
plateau) where increasing the batch size no longer decreases the steps to reach a goal error. The same trend is observed across various workloads of data set, network model, and optimization algorithm as well as different goal errors (see Appendix We note that our observation is consistent with the results of regular network training presented in Shallue et al. (2019); /Zhang al. (211))
3

---

Published as a conference paper at ICLR 2021
Sparsity: 0%
Sparsiy: 50%
Sparsity: 70%
Sparsity: 90%
210
Ninittan
21
St0p5
Stops
Stegs
20
Batch Size
Battch size
Batch Size
Batch size
Figure 2: Comparing different optimization algorithms for the effects of data parallelism and spar- sity on the workload (MNIST. Simple-CNN, (GDDMomentum/NNsteroo// and study {batch size (2-16384) sparsity levels (0, 50, 70, 90%) settings; there is no normalization or averaging. Across all sparsity levels, momentum optimizers (i.e., Momentum, Nesterov) record lower steps-to-result in large batch regime and have much bigger critical batch sizes than SGD without momentum. Identifying such patterns is crucial especially when training in resource constrained environments, as practitioners can potentially benefit from reducing the training time by deciding a critical batch size properly, while utilizing resources more effectively.
When we put the results for all sparsity levels together, we observe that training a sparser network takes a longer time; a data parallelism curve for higher sparsity usually lies above than that for lower sparsity (see the 3rd column in Figure D. For example, compared to the case of sparsity 0% (i.e., the dense, over-parameterized network), 90% sparse network takes about 2 - 4 times longer training time (or the number of training steps), consistently across different batch sizes (see Figure 12 in Appendix D.I for more precise comparisons). Recall that we tune all metaparameters independently for each and every study case of batch size and sparsity level without relying on a single predefined training rule in order to find the best steps-to-result. Therefore, this result on the one hand corroborates the general difficulty of training sparse neural networks against the ease of training overly parameterized neural networks.
On the other hand, when we normalize the y-axis of each plot by dividing by the number of steps the first batch size, we can see the phase transitions more clearly. As a result, we find that the regions of diminishing returns and maximal data parallelism appear no earlier when training sparse networks than the dense network (see the 4th column in Figure D This is quite surprising in that one could have easily guessed that the general optimization difficulty incurred by sparsification may influence the data parallelism too, at least to some degree; however, it turns out that the effects of data parallelism on sparse network training remain no worse than the dense case. Moreover, notice that in many cases the breakdown of linear scaling regime occurs even much later at larger batch sizes for higher sparsity case; this is especially evident for Momentum and Nesterov optimizers (e.g., compare training 90% sparse network using Momentum against 0% dense network). In other words, for sparse networks, critical batch size can be larger, and hence, when it comes to training sparse neural networks, one can increase the batch size (or design a parallel computing system for distributed optimization) more effectively, while better exploiting given resources. We find this result particularly promising since SGD with momentum is often the method of choice in practice.
We further show that momentum optimizers being capable of exploiting large batch sizes hold the same across different sparsity levels by displaying all plots together in Figure Overall, we believe that it important confirm the robustness of the data parallelism in sparse neural network training, which has been unknown thus far and difficult to estimate priori.
3.2 ANALYZING METAPARAMETER SEARCH
In this section, we analyze the metaparameter search used to measure the effect of data parallelism. We specifically investigate the workload (MNIST, Simple-CNN, Momentum] J where there are two metaparameters to tune (i.e., learning rate and momentum), to visualize all metaparameters easily in 2D figure (see Appendix D.2 for other results). The results are presented in Figure and we summarize our key findings below:
Our quasi-ran random search samples metaparameters efficiently, so that they are distributed evenly (without being cluttered in log-space) and flexibly (rather than sitting in grid with fixed spac-
4

---

Published as a conference paper at ICLR 2021
S: 0%%, B:
127
S: 0%. B: 120
12"
S: 1%0% 1024
10'
S: 0%% B: 8192
Momentuu
12.1
Momentum
Momentum
Momsnntum
30-1
2374
22-
4
44
4
12
10 10 13 10
10" 30
20
10
1E 30
10
12
10 10 1e
10
50
10
Learning rate
Learning rate
Learning rate
Learning rate
207
90%, 16
127
90% 120
S: 90% 8: 1024
10"
90%, 8192
Momentum
Momentum
Momentum
Momentum
23
50
32-4
te-
13
Learning
Learning
Learning rate
Figure 3: Metaparameter search results (100 samples in total) for Simple-CNN on MNIST trained using Momentum optimizer. Sparsity level (S) and batch size (B) are denoted at the top of each plot. The best trial that records the lowest steps to reach the goal (i.e., steps-to-result) is marked by gold star (+). Complete/incomplete refer to the trials of goal reached/not reached given maximum training step budget, while infeasible refers to the trial of divergence during training.
ing) within the search spaces. Also, the best metaparameters yield lowest steps (marked by gold star *) are located in the middle the search ranges rather than sitting at the search boundaries across different batch sizes and sparsity levels. This means that our experiments are designed reasonably well, and the results are reliable.
There are two distinguished regions (i.e., complete (+) and incomplete (A)) being separated by seemingly linear boundary as per the relationship between learning rate and momentum. This indicates that the optimization is being done by an interplay between these two metaparameters: one metaparameter is not chosen carefully with respect to the other (e.g., increase learning rate for fixed momentum), the optimizer may be stuck in a region spending time oscillating and eventually results in incomplete runs. This highlights the importance of performing metaparameter search, although is expensive, rather than relying on predetermined heuristic training strategies, in order to accurately measure the effect of data parallelism and avoid potentially suboptimal results.
The successful region (filled with blue circles o) becomes larger as with increasing batch size, showing that large batch training reaches given goal error in less number of training iterations than small batch training, and hence, yields more complete runs. Notably, the best learning rate tends to increase with increasing batch size too. This aligns well with the classic result in learning theory that large batch training allows using bigger learning rates (Robbins & Monro 1951; Bottou 1998; Krizhevsky 2014).
UNDERSTANDING THE EFFECTS OF DATA PARALLELISM AND SPARSITY
So far, have focused measuring the effects of data parallelism and sparsity neural network training, and as a result found two distinctive global phenomena across various workloads: scaling trend between batch size and steps-to-result, and training difficulty under sparsity. While our find-
ings align well with previous observations (Shallue et al. 2019: Zhang et al. 2019 Lee et al. 2020), it remains unclear as why occurs, and whether it will generalize. To this end, we establish theoretical results that precisely account for such phenomena based on convergence properties of generalized stochastic gradient methods in this section.
4.1 CONVERGENCE ANALYSIS FOR THE GENERAL EFFECTS OF DATA PARALLELISM
Let us begin with reviewing the convergence properties of stochastic gradient methods as the choice of numerical algorithms for solving optimization problems. Consider a generic optimization prob- lem where the objective is to minimize empirical risk with the objective function f Rm R
5

---

Published as a conference paper at ICLR 2021
prediction function h Rdd x R Rdy, and loss function 1: R Rd - R which yields the loss 1(h( w). y) given an input-output pair yz, y), where w E R" is the parameters of the prediction model h, and d, and d, denote the dimensions of input and output y. respectively. A generalized stochastic gradient method to solve this problem can be of the following form:
Wk+1 == W/ - T) Wk, Ex)
(I)
where 7/K is a scalar learning rate, ( {t) E I is a stochastic vector (e.g., unbiased estimate of the gradient f) with &a denoting random variable to realize data samples, either single sample as in the prototypical stochastic gradient method (Robbins & Monro [151]) or a set of samples as in the mini-batch version (Bottou| [99T). Given an initial iterate Wi, finds a solution by performing the above update iteratively until convergence.
Under the assumption of Lipschitz smoothness of and bounded variance of g, the convergence rate result states that for such generic problem with nonconvex objective and optimization method with a fixed 5 learning rate 7hs- = fj for all k satisfying 0 < fj S T.M. the expected average squared norm of gradients of the objective function guaranteed to satisfy the following inequality for all K N (Bottou et al. 2018
M 2(f(w1)-
E K Σ IVS((&)
+
K
Here, f(w1), foo. Vf((;;)) refer to the objective function's value at W1, lower bound, gradient at WA, respectively. Also, I. is the Lipschitz constant of Vf, and μ., M, MG denote scalar bounds in the assumption on the second moment of g( w.w&&a. {x). Note here that M is linked to batch size B as M x I/B. In addition, being i.i.d. samples as in experiments, then simply μ = 1 (Bottou al. 2018). In essence, this result shows that the average squared gradient norm on the left-hand side is bounded above by asymptotically decreasing quantity per K, indicating sublinear convergence rate of the method. We note further that the convergence rate for the mini-batch stochastic optimization of nonconvex loss functions is studied previously (Ghadimi et al. 2016 Wang & Srebro 2017), and yet, here reconsider it to analyze the effects of data parallelism.
Cx) ) is an unbiased estimate of V f(w)). which is the case for Ex
We now reformulate this result, such that is translated into form that matches our experiment set- tings and reveals the relationship between batch size and steps-to-result. We start by recognizing that the quantity on the left-hand side, the expected average squared norm of V ((wx) during the first K iterations, indicates the degree of convergence; for example, it gets smaller as training proceeds with increasing K. Thus, this quantity directly related to goal error to reach in our experiments, which is set to be fixed across different batch sizes for a given workload. This effectively means that training has stopped, and K will no longer contribute to decrease the bound of the quantity. Also, recall that we select the optimal learning rate 1f", out of extensive metaparameter search, to record the lowest number of steps to reach the given goal error, i.e., steps-to-result K*, Next, notice that the only factors that constitute the inequality in Eq. (2) are the Lipschitz constant L and the variance bound M, and if they are assumed to be tight in the worst case, the inequality becomes tight. Now are ready to provide the relationship between batch size (B) and steps-to tepssto-resulle (K*) as follows:
Proposition 4.1. Let = B[K=- Σ [VV((>)) the first K* iterations and 17" denote the optimal learning rate used to yield the lowest number of steps K* to reach e. Then,
[[()))]l3 ]|3]] denote degree of convergence achieved after
C1 + B
ALB n2gz
A
KJ ~
where C1
and
C2
(3)
t'tue"
where A = -2([[w1)) foo), ), 3 is the initial variance bound at batch size B 1 for given workload.
Proof. This result is obtained by recasting Eq. as outlined above. The proof is in Appendix A
(() f is differentiable and satisfies [[](()) - Vf < L||w - wlla. V(w, w c R". and (ii) there
exist scalars M 2 0, Mc 2 n² > O such that Egg [[99( [llg(w. We also consider the general decaying learning rate case and prove the same result in Appendix A.2
w.: [ < M + MallV (w:

---

Published as a conference paper at ICLR 2021
Simple-CNN
ResNet-8
25
Spanity
Spanity 0%
Lipschitz constant of WfF
Snandry: 0%
Spandry: 50%
Lipschitz constant of
6-
Spanity: 70%
Sparsity:
20
Sparait:
Spandty: 70%
5
15
10-
10
25 Steps (x10²)
20
40
Steps (x10²)
Figure 4: Lipschitz constant of ff measured locally over the course of training for networks with different sparsity levels. The more network pruned, the higher the Lipschitz constant becomes; e.g., for 0, 50. 70, 90% sparsity levels, the average Lipschitz constants are 0.57. 0.72, 0.81, 1.76 for Simple-CNN and 3.87, 8.74, 9.54, 11.18 for ResNet-8, respectively. This indicates that pruning results in network whose gradients are less smooth during training. We further provide additional training logs and explain how smoothness is measured in Appendix
This result precisely illustrates the relationship between batch size and steps- teessto--rssult. For example, when B is small, K* B. fitting the linear scaling regime (e.g.. B - 2B makes K* - (1/2) K*), whereas when B is large and asymptotically dominates the right-hand side, K* a C2. indicating the maximal data parallelism as K remains constant. In general. for moderate batch sizes, scaling B + 2n B results in K + 전 K* + (1 + )oz (rather than 2- K*), indicating diminishing returns.
Moreover, we prove the same relationship between B and K* (with different constant terms) for the general decaying learning rate case (see Appendix A..2). Therefore, this result not only well accounts for the scaling trend observed in the experiments, but also describes it more precisely and generally. Notably, the effect of data parallelism, which has only been addressed empirically and thus remained as debatable, is now theoretically verified and applicable to general nonconvex objectives. We will further relate our result to sparse networks via smoothness analysis in Section 4.2
4.2 LIPSCHITZ SMOOTHNESS FOR THE DIFFICULTY OF TRAINING SPARSE NETWORKS
Another distinct phenomenon observed in our experiments that the number of steps required to reach the same goal error for sparse networks is consistently higher than that for dense networks re- gardless of batch size (i.e., a whole data parallelism curve shifts upwards when introducing sparsity). This indicates the general difficulty of training sparse neural networks, and that sparsity degrades the training speed. In this section, we investigate what may cause this difficulty, and find a potential source of the problem by inspecting our theory of the effect of data parallelism to this end.
Let us begin with our result for the effect of data parallelism in Proposition 4.1 the coefficient e₁ (= ALB/ p22) that can shift whole data parallelism curve vertically, by the same factor across different batch sizes. Taking a closer look, we realize that it is the Lipschitz constant L that can vary quite significantly by introducing sparsity and hence affect c₁; and μ are fixed, and A and 3 can change by sparsity in a relatively minor manner (we explain this in detail in Appendix C). Specifically, L refers to the bound on the rate of change in V and is by definition a function of f. Also, sparsity introduced by pruning changes the prediction function h which is linked to f via the loss function L. Therefore, we posit that sparse neural network obtained by pruning will be lesy smooth (with higher Lipschitz constant) than the non- non-pruned dense network. To verify our hypothesis, we empirically measure the Lipschitz constant for networks with different sparsity levels over the course of the entire training process. The results presented in Figure
Notice that it is
As we can see, it turns out that the Lipschitz constant increases as with increasing sparsity level, and further, is consistently higher for sparse networks than for the dense network throughout training. This means that pruming results in sparse networks whose gradient changes relatively too quickly compared to the dense network; in other words, the prediction function h becomes less smooth after pruning. This is potentially what hinders training progress, and as a result, sparse networks require more time (i.e., steps-to-result) reach the same goal error.
7

---

Published as a conference paper at ICLR 2021
2: 0%, B1
1.0%% 01332
3: 3-255
5: 1%.% 2048
(2000)
01400
Stgps
1.5
271
22: 23 10
321
20 12
12
137 101
30
50%, Bi4
5 60% P.
95% Bi
5.63% D: 2008
5: 90%
1618
3.0
mncomio
Stor
Leaming Fate
tang rats
Leaming
Leariig ratc
Figure 5: Metaparameter search results the workload of (MNIST, Simple-CNN, SGD), where the metaparameter being tuned is the learning rate nj. The blue circles (+) denote successful runs (i.e., it reached the goal error), and the best trial that records the steps-to-resuld is marked by gold star (+); also, the grey triangles (A) and red crosses (x) refer incomplete and infeasible runs, respectively. The range ij shrinks as the sparsity level increases from 0% to 90%, indicating increased L based on the learning rate condition from the convergence properties satisfying 0 1/L.
Evidence of increased I Lipschitz constant for sparse networks can be found further in metaparameter search results presented Figure [ Notice that for each batch size, the size of the range for suc- cessful learning rate decreases when switching from 0 to 90% sparsity level. This is because the learning rate bound satisfying the convergence rate theory becomes n S 1/L L for a fixed batch size, and increased L due to sparsity shrinks the range of
We note that our findings increased Lipschitz constant for sparse networks are consistent with the literature over- pereparrmeteri networks such Li & Liang (2018), which can be seen the opposite of sparsity. 'he more input weights a neuron has, the less likely that a single parame- ter significantly changes the resulting activation pattern, and that wide layers exhibit convexity- -like properties in the optimization landscape Du et al. (2019). This even extends to non-smooth networks with ReLU activations, which are still shown exhibit pseudo-smoothness in the overparameterized regime Li& Liang 2018). We further show that our theory precisely explains the difficulty of train- ing sparse networks due decreased smoothness based on quantitative analysis Appendix [
In addition, we provide in Figure the training logs of the networks used for the Lipschitz smooth- ness analysis, in order show the correlation between the Lipschitz smoothness of network and its training performance; i.e,, sparsity incurs low smoothness of gradients (high L; see Figure and hence the poor training performance.
Simple-CNN
ResNet-8
0.200
2.00
Sparsity: 0%
Spars 6%
0.175
Sparsity: 50%
1.75
Sparsit 50%
Spanthy:: 70%
Sparchy: 70%
0.150
Spanity:: 90%
1.50
Sparcht: 507%
1.25
Loss
0.075
0.75
0.050
0.50
0.025
0.25
25 Steps (x10P)
Steps (x102)
Figure 6: Training logs of Simple-CN CNN and ResNet-8 used for the smoothness analysis. The sparse networks that recorded high Lipschitz constants show worse training performance, indicating that low smoothness may be the potential cause of hampering the training of sparse neural networks.
8

---

Published as a conference paper at ICLR 2021
5 DISCUSSION
Data parallelism with sparsity could have promising complementary benefits, and yet, little has been studied about their effects on neural network training thus far. In this work, accurately measured their effects, and established theoretical results that precisely account for the general characteristics of data parallelism and sparsity based on the convergence properties of stochastic gradient methods and Lipschitz smoothness analysis. We believe our results are significant, in that these phenomena, which have only been addressed partially and empirically, are now theoretically verified with more accurate descriptions and applied to general nonconvex settings.
While our findings render positive impacts to practitioners and theorists alike, there are remaining challenges. First, our experiments are bounded by available computing resources, and the cost of experiments increases critically for more complex workloads. Also, the lack convergence guar- antees for existing momentum schemes in nonconvex and stochastic settings hinders further theo- retical analysis. We hypothesize that ultimate understanding of the effect of data parallelism should be accompanied by study of the generalization capability of optimization methods. Nonetheless, these are beyond the scope of this work, and we intend to explore these directions as future work.
ACKNOWLEDGMENTS
This work was supported by the ERC grant FRC-2012-AdG 121162-HELIOS, EPSRC grant See- bibyte EP/M013774/L. EPSRC/MURI grant EP/N019474/L, the Australian Research Council Centre of Excellence for Robotic Vision (project number CE140100016), and the Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) 2N..2020-0-01336, Artificial Intelligence Graduate School Program (UNIST)). We would also like acknowledge the Royal Academy of Engineering and FiveAl.
REFERENCES
Martín Abadi et al. Tensorflow: A system for large-scale machine learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16), pp. 265-2832 2016.
Léon Bottou. Stochastic gradient learning in neural networks. Neuro Nimes, 1991.
Léon Bottou. Online learning and stochastic approximations. On-line learning in neural networks, 1998.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. NeurlPS, 2012.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. ICIR, 2019.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation meth- ods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2): 267-305. 2016.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint (oXiv:1706.0666 2017.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. NeurIPS, 2015.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the general- ization gap in large batch training of neural networks. NeurlPS, 2017.
Alex Krizhevsky, One weird trick for parallelizing convolutional neural networks. arXiv preprint arXiv: arXiv:1404.599) 5994, 2014.

---

Published as a conference paper at ICLR 2021
Namhoon Lee, Thalaiyasingam Ajanthan, and Philipp HS Torr. SNIP: Single-shot network pruning based on connection sensitivity. ICLR, 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip H. S. Torr. A signal propaga- tion perspective for pruning neural networks at initialization. ICLR, 2020.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. NeurlPS, pp. 8157-8166, 2018.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't 't use large mini-batches, use local sgd. ICLR, 2020.
Russell Reed. Pruning algorithms-a survey. Neural Networks, 1993.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statisties, pp. 400-407, 1951.
Christopher Shallue, Jaehoon Lee, Joseph Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George E Dahl. Measuring the effects of data parallelism on neural network training. JMLR, 2019.
Samuel I. Smith, Pieter-Jan Kindermans, Chris Ying, and Quoe Le. Don't decay the learning rate, increase the batch size. ICLR, 2018.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. ICLR, 2020.
Weiran Wang and Nathan Srebro. Stochastic nonconvex optimization with large minibatches. arXiv preprint arXiv: 7009 08728, 2017.
Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George Dahl, Chris Shallue, and Roger B Grosse. Which algorithmic choices matter which batch sizes? insights from noisy quadratic model. NeurIPS, 2019.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelcrates training: theoretical justification for adaptivity. ICLR, 2020.
A PROOF OF THE GENERAL EFFECT OF DATA PARALLELISM
This section provides the missing proofs in Section 4 The goal is to derive the relationship between batch size B and steps-to-result K* from the convergence rates of generalized stochastic gradient methods for both fixed and decaying learning rate cases. The result serves to account for the effect of data parallelism as a general phenomenon that must appear naturally at neural network training.
A.1 FIXED LEARNING RATE CASE
We first recognize that the expected average squared gradient norm on the left-hand side indicates the degree of convergence. Then, this quantity directly related the concept of goal error to reach in our experiments, and hence, reduces be small constant as soon as it is implemented as pre-defined goal error for a given workload. Thus, follows that
We start from the convergence rate result in Eq. (2).
7LM 2(S(w1) - Sox)
1
Kμn
[[ it effectively means that the training process Notice that by fixing = E Σ k=
has stopped, and therefore, K on the right-hand side will no longer contribute to decrease the bound of the quantity for particular learning rate 7 and batch size B.
Also, we select the optimal learning rate n² out of extensive metaparameter search, to record the lowest number of steps reach the given goal error, which denote steps-to-result K*.
Here, optimal simply refers the sense of yielding the lowest steps-to-result.
10

---

Published as a conference paper at ICLR 2021
Plugging in these yields the following:
c LM 2(f(wi) Soo)
(5)
K*
Next, notice that the only factors that constitute the inequality in Eq. (2) come from the assumptions made derive the convergence rate result, which are on the Lipschitz smoothness L and the vari- ance bound M, and if they are assumed to be tight in the worst case, the inequality becomes tight. Then, after making algebraic manipulation and taking the first-order Taylor approximation while substituting M = B/ B since the variance bound M is related to batch size B as M x 1/B (Bottou ct al. 2018), we obtain the following result:
A
K 2
(6)
17 TUE
P
A
ALM
TE 1.222
ALB
A
P
He
C1
ALB 1²z²2
A
+ C2
where c1
and C2 17-
B
Here, A = 2(f((w))- foo), 3 is the initial variance bound at batch size B == for given workload. Notice that A, L, B, f1 1j" all are constant or become fixed for a given workload. Also, the degree of metaparameter search quality is assumed be the same across different batch sizes, and hence, the result can be reliably used to interpret the relationshp between batch size and steps-to-result
A.2 DECAYING LEARNING RATE CASE
We could extend the convergence rate for fixed learning rate тソ Eq. any sequence of decaying learning rates 7) satisfying Σk=1 Me
and
Σ 20
co based on Theorem 4.10 in 1/
==
Bottou et (2018) as follows:
LM
K
2(B[J(w])] -oo)
E
K Σ me (
2 Th
Kμ
K₁
The requirements on learning rate Th are the classical conditions (Robbins & Monro 1951) that are assumed for convergence of any (sub)gradient methods, and cover nearly all standard and/or heuristical learning rate schedules employed in practice.
Now, the relationship between batch size and steps-to-result can be derived similarly as before. First, applying ē = [ Σ f(w
for the degree of convergence, and replacing with can rewritten as follows:
A (([()(())) - foo) for simplicity, Eq.
LM
A
ē
T
(8)
Kμ
Kμ
Plugging H = ΣK for selected by metaparameter search and steps-to-result, respectively, it becomes:
k= Th for finite constant from decaying learning rate, and further, H' and K*
LMH*
A
K*u
K*M
Finally, using the worst case tightness on L and M, substituting M B/B. and rearranging the terms, the effect of data parallelism for decaying learning rate case can be written as follows:
LMH H*
A
Kt
(10)
μiE
μE
LH* 3
μēB
μIE
LH*1
A
+ Ō2
where
and 02
B
pē
11

---

Published as a conference paper at ICLR 2021
Here, é, A, L, S. p all are constant become fixed for given workload.
This result, along with the case of fixed learning rate, establishes the theoretical account for the effect of data parallelism, by precisely and generally describing the relationship between batch size B and steps-to-resule K*, Further analysis of these results is referred to the main paper.
B SCALE OF OUR EXPERIMENTS
For given workload of (data set, network model, optimization algorithm| and for study setting of (batch size, sparsity level), we execute 100 training runs with different metaparameters to measure heepsto-result. At each run, we evaluate the intermediate models every 16 (for MNIST) 32 (for CIFAR-10) 10) iterations, on the entire validation set, to check if it reached a goal error. This means that, in order to plot the results for the workload of (MNIST, Simple-CNN, SGD) for example, one would need to perform, 14 (batch sizes; 2 to 214) x 4 (sparsity levels; 0, 50, 70, 90%) x 100 (runs) 40, 000 (max training iteration preset) / 16 (evaluation interval) 14. 000, 000 number of evaluations. Assuming that evaluating the Simple-CNN model on the entire MNIST validation (second per
set takes only a second on a modern GPU, will take 14, 000, 000 (evaluations) evaluation) 3600 (second per hour) = 3888 hours or 162 days.
Of course, there are multiple ways to reduce this cost; for instance, we may decide stop as soon as the run hits the goal error without running until the max training iteration limit. Or, simply reducing any factor listed above that contributes to increasing the experiment cost (e.g., number of batch sizes) can help to reduce the time, however, in exchange for the quality of experiments. We should also point out that this is only for one workload where we assumed that the evaluation takes only a second. The cost can increase quite drastically if the workload becomes more complex and requires more time for evaluation and training (e.g., CIFAR-10). Not to mention, we have tested for multiple workloads besides the above example, in order to confirm the generality of the findings in this work.
C MORE ON LIPSCHITZ SMOOTHNESS ANALYSIS
We measure the local Lipschitz constant of V based on a Hessian-free method as used in Zhang al. (2020). Precisely, the local smoothness (or Lipschitz constant of the gradient) at iteration is estimated as in the following:
VVs(w& + +7d) v.((w)]l2
i(wk)= = max 7E (4.26...1)
(11)
1/d1
where Wk+1 We and (0,1) for which we set to be 8 0.1. The expected gradient Vʃ is computed on the entire training set, and we measure i(wx) at every 100 iterations through- out training. This method searches the maximum bound on the smoothness along the direction between ff(w++1) and f((w)) based on the intuition that the degree of deviation of the linearly approximated objective function is bounded by the variation of gradient between WK+1 and Wa- Furthermore, while ReL.U networks (e.g., Simple-CNN, ResNet-8) can only be piecewise smooth, the smoothness can still be measured for the same reason that we measure gradient (i.e., it only requires differentiability).
We also empirically measure the changes in A and 9 by introducing sparsity. Recall that these are the other elements in (j that can be affected by sparsity along with Lipschitz constant L. When we mea- sure these quantities for Simple-CNI Cample-CNN, we obtain the following results: A./Aa se 4.68/4.66 1.00, and /./8a Ba RJ 107.33 107.39/ 29/399//9 /1/999.00 006 x 0.54; more precisely, A does not change much since neither f(wi) or (W changes much and /,/ 3a can be measured by the ratio of the variances of gradients between sparse and dense networks at B 1. We have already provided L,, La in Figure which makes L./Lo La &e 1.76/0.57 x 3.09. Here, s and denote sparse (90%) and dense, respectively. No- tice that if we combine all the changes in A, B, L due to sparsity, and compute c1.=/C1,a. it becomes 1.00 x 0.54 x 3.09 Ne 1.67. Importantly, C1.a/ Ci,d >> means that e1 has increased by sparsity, and since the increase in Lipschitz constant L played major role therein, these results indicate that the general difficulty of training sparse networks is indeed caused by reduced smoothness. We further
note that this degree of change fits roughly the range of kg /ka shown in Figure 12
12

---

Published as a conference paper at ICLR 2021
D ADDITIONAL RESULTS
In this section, we provide additional experiemental results that are not included the main paper. In Section D.I. we supplement more results for the effects of data parallelism and sparsity Figures 7 2 To II In Figure we we present the difference in ratio between sparse (90%) and dense networks across different batch sizes all workloads presented in this work. This result shows how much increase in steps-to-resuu is induced by introducing sparsity, and therefore, is used to study the general difficulty of training sparse neural networks. In Section D.2 we provide metaparameter search results for a subset of lorkloads studied in this work.
D.1
EFFECTS OF DATA PARALLELISM AND SPARSITY
Spardbo 65s
Spardhy 50t
Seartho: 201
Soantyy 51%
Al cpattty
spantry TerTebee
B31T AM
B0Y1
Fatm SDP
Buth
9300
(a) SGD
200
(b) Momentum
Spuraboo
Spandy: 70%
25%
Al spurs
apprrtily nakeedf
Batcssee siz
Palons
Bacc
9400
(c) Nesterov
Figure 7: Results for the effects of data parallelism for the workloads of (MNIST, Simple-CNN, SGD/MomenummNesterry | with a constant learning rate.
13

---

Published as a conference paper at ICLR 2021
botchatee
Belth A8
Botth sic
SGD
5
9973
B40
Batth
Botth size
(b) Momentum
bitohaiee
Eelth Ai
Dutth stc
(c) Nesterov
Figure 8: Results for the effects of data parallelism for the workloads of (Fashion-MNIST. Simple- CNN, SCD/Momentun/Nexcrro/ with constant learning rate and the goal error of 0.12.
Sparsity: 0%
Searsity: 70%
Sparsity: 30%
All sparity
All sparitty Isomaazoo
-1 -1
5005
Stuce
StOS
Satch
stoc
Babch
(a) SGD
(normaized
100
Staps
Stope
Daich sice
Swtch
Baich Loz
Batch sizw
(b) Momentum
Sparsity:
Sparsity:
Sparsity:
sparsty
2:14
Spatty
S:0
Scpps
Datch sice
Outchaize sice
Batch sioe
Baich Looe
Batch size
(c) Nesterov
Figure 9: Results for the effects of data parallelism for the workloads of (Fashion-MNISTT, Simple- CNN, SGD/Mommentu//Nestroo// with a constant learning rate and the goal error of 0.14.
14

---

Published as a conference paper at ICLR 2021
Spara by:
Spanity:
Aliparaty
spara (oommaledd) Sanp ls.
Grandy
Baach
Tanch size
Barch diz
Barch size
(a) SGD
Sporsity:
Sparsty: 90%
spardiy
sparsky
(norma
2"
Betrh
Betch
(b) Momentum
Spercity: 096
Stppa 222
Spanity: 90%
spardity
(sommerll
CINCK
(c) Nesterov
Figure 10: Results for the effects of data parallelism for the workloads of (CIFAR-10, ResNet-8, SCD/Mommnttu//Nsterroo } with linear learning rate decay.
Sparsity:
Sparsity: 90%
sparsity
sparsityy (narmaiized)
211
Band 10%
Saaely 896
2.0
20
Steps
211
24
22
27
Batch size
Batch size
Batch size
Batch size
(a) SGD
Sparsity: 0%
Sparsity: 90%
All sparsity
All spartityy (nammllize)
315
S1U5T5 200
2n
Eandly
Rausly 19c
Stops
27
Batch size
Batch
Batch
size
Momentum
Figure 11: Results for the effects of data parallelism for the workloads of (CIFAR-10, ResNet-8, SGD/Momentum) with constant learning rate.
15

---

Published as a conference paper at ICLR 2021
Momentum
Ralio Opparse to derett)
Relio Oparse to derae))
Relio (parree to derax)
9.0
2
311
20
Batch dize
Batch size
Batch size
(a) MNIST, Simple-CNN, SGDDMoomentum//Neeterv with a constant learning rate
SGD
Momentum
Nesterov
2.3
(sparse dense)
6.2
1.0
(sperse
2.8
1.4
12
2.
Batch size
Batch size
Batch 5ize
(b) Fashion-MNIST, Simple-CNN, SGDDMMomentun/Neseerv with a constant learning rate
SGD
Momentum
Nesterov
3,30
Ratio (sparse to denuel
denze:
Ratio (sparse to dense]
2.75
2.50
2.25
2.00
2.0
CIFAR-1O, ResNet-8, SCD/Moomentunn/Nesseeoy with linear learning decay
Momentum
Ratio Isparse to densa)
Ralio Isperse to denod)
4.3
WA
2.9
2.3
Batch size
Batch size
(d) CIFAR-10 10. ResNet-8, SGD/Momentum with a constant learning rate
Figure 12: Differences in ratio between (90%) sparse network's steps-to-result dense network's. s, across different batch sizes for all workloads presented in this work. The difference ranges between (1.5, 4.5) overall. Note that the ratio difference > 1 indicates that it requires more number of training iterations (i.e., steps-to-result) for sparse network compared to dense network. Also, the difference seems to decrease as batch size increases, especially for Momentum based optimizers. This potentially indicates that sparse neural networks benefit from large batch training, despite the general difficulty therein.
16

---

Published as a conference paper at ICLR 2021
D.2 METAPARAMETER SEARCH RESULTS
B.2
5.0% ARAM0O
0%
52. 17 rate S:
15" 12"
Learting
rote
Leaming
rate
5-0%,, 64
0:35,01
Sters
Learting 1ate
Leaming rats
Lear ning 1886
Leaming rate
Leaming rate
4.0 13000
55
of Learning sirring rade
Learting mote
Leaming mas
Leaming 188e
Leaming rate
Sleck
12
Leurning rate
rate
31
210
Stipe
1.0
Low
Led
90% R: 1026
1.90
92%
5192%, 8192
S. 90% 16364
2 1:
Stags
Staps
10
12
Figure 13: Meataparameter search results for the workloads of (MNIST, Simple-CNN, SGD) with a constant learning rate.
17

---

Published as a conference paper at ICLR 2021
5: B:
5.0%,
5: 0% 229
2040
D:15284
ZABANA GANGENENNN
Stape
1.5
ting
Learnang rañe
Laamiigg rate
Leaming
LearTin 1an2
2009
18254
StO05
Loarting 1956
Leaming rats
Lear ring loke
Leurning rate
Loariig rate AlAA
1.0
dull
Someroum
Momemuu
Somermum
Momeetium
Momantum
50%
5.00% 2525
2040
50%.
50053
Stare
Womenta
Momenuu
Momentum
Momentimm
Momentum
Figure 14: Meataparameter search results for the workloads of (MNIST, Simple-CNN, Momentum with a constant learning rate.
5: 0% 8.4
33
C% B 255 J.BB Dww.NRRErROEE
0% 2049
0.00 B: 8:16684 Diliieoooot
3.5
1.
Stupa
Learting Fa10
Mirggiigggnn rala
Corning ruts
Learning 1012
Learming rutc
90%,
2000
16364
200 oemeewtoooood
0372
Stock
Store
Loa raig ro00
Leaming raze
Loar ring rote
Loaming rate
Leariig rate
50..000 00000000000000.00 ais dlal
Momemmm
Nomemum
Nomentum
Nomentum
Nomertum
261
90%,
244
Momontum
Momonnum
Mumientum
Mumonnuum
Figure 15: Meataparameter search results for the workloads of (MNIST, Simple-CNN, Nesterov] with a constant learning rate.
18

---

Published as a conference paper at ICLR 2021
St0P
Siopa
Stept
Learsing rais
Leaming rala
Learting rate
Leurning r8ss
Leariing rata
50%,
5,938,6
34023
Stoss
Loar sing
Leaiingg rate
Leaiming
Lcar ring
Figure 16: Meataparameter search results for the workloads of (CIFAR-10, ResNet-8, SGD) with constant learning rate.
0.%%
2018
0% 16181
3010
2010
2.
ring nit
Learstee rate
Loar ralp
Learn no rote
Learning rate
Stips
Staps
2.50
Loarting rote
Learting rale
Learning rate
Learring rate
Loor 1ir rals
26-
Store
Momentun
Marremum
Mameentu
Marrentumn
Mamrentu
92% &
Stupa
22"
Momenium
Momenian
Nomertum
Momurtum
Momurtum
Figure 17: Mcataparameter search results for the workloads of |CIFAR-10, ResNet-8, Momentum) with a constant learning rate.
19

---

Published as a conference paper at ICLR 2021
5: 1%% B:
10% 8: 32
9%, 256
S. 1.0%
2048
16384
1.0
12554
rinng
Leamiing rase
ring olt
Leamming
Leariing
92%, 5:4
5: 10% 5:52
99%, B: 236
5.90% 2018
50% 28
5305
Steps
STEDS
Leae 1ing ESTO
corrang rate
ning rate
Learning rate
Leamiing r9ne
2.
30-
Store
Loa rinig rose
Leamiing rate
Loar ring olt
Louining ro0e
Loarning rall
SHips
Lear sing
Lear ring rate
Loar ning rote
Learning
Learnnng
5.0%,
0%
255
5009
Docay
12
steps
Decuy
90%,
90%
90% 2015
2e1
100%
20384
5206
Stece
3.3
30
0%. 2:
1.0%
0% 8 255
S: 0%.0 e. 2005
0% 19204
6
Desay
5: 30%
50%, 3:32
5: 90% t: 255 aeocaesuee
St 50% D: 2043 www.ppoooeeaaatt......
90% B: 10304
and awwibioobbt m00.
Docay fockar
Docay
Docay facter
Decay factor
Docay foodor
Figure 18: Meataparameter search results for the workloads of (CIFAR-10, ResNet-8, Nesterov) with a linear learning rate decay.
20

---

Published as a conference paper at ICLR 2021
E IMPLEMENTATION DETAILS
Data parallelism and sparsity. By data parallelism, we refer to utilizing a parallel computing system where the training data is distributed to multiple processors for gradient computations, so that the training process can be accelerated. For the purpose of this work, we consider the simplest setting synchronized distributed systems, in which the degree of parallelism equates to the size of mini-batch used for training on regular single-node system. This effectively means that the effect of data parallelism can be measured by increasing batch size. By sparsity, refer to pruning parameters in neural network model, such that the remaining parameters are distributed sparsely on the network. For the purpose of this work, we employ recent muning-at-initializaiio method to obtain sparse networks, since they must not undergo any training beforehand so to measure the effects of data parallelism while training from scratch.
Software and hardware. We used TensorFlow libraries (Abadi et al. 2016) and compute cluster with multiple nodes of CPUs (Intel Xeon Gold 5120 CPU @ 2.20GHz with 28 cores; in total) and GPUs (Tesla P100 and V V100; 16GB; 28 in total).
21


Reviews:
[{"review_id": "KcE-1oGudm_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "After reviewing the authors' response:\nThe authors have agreed to include missing sparsity level-results and have commented that such results are in line with the trends observed in other experiments.  Furthermore, the authors' response addressed all my questions and concerns, for which I'm raising my score.\n\n========================================\n\nThe authors explore the role of data parallelism (i.e., the optimal mini-batch size) and sparsity (via parameter pruning) in deep networks through extensive empirical experiments.  This effectively builds on the work of Shallue et al. (2019), by considering sparsity in addition to the previously explored behavior of data parallelism.  Assuming Lipschitz continuity and boundedness on the squared norm of the gradient, the authors then draw theoretical results exposing the role of data parallelism towards convergence for non-convex objectives (note this thus, of course, means local-optima convergence) for SGD with a fixed learning rate (the result for decaying learning rates is included in the appendix).\n\nThe main theoretical result is nice, and Lipschitz continuity in DNNs has been extensively studied recently.  In particular, it brings a theoretical understanding to optimizing the batch size, which has generally been understood in empirical/heuristic terms.  However, the paper makes certain leaps in logic and claims with regards to sparsity based on the provided evidence.  Specifically, in Figure 1 sparsity levels are missing from CIFAR-10 and Fashion-MNIST, and Section 3.2 and Appendix D.2 only consider sparsity \\in {0.0, 0.9}.  What happens at\nsparsity levels between 0 and 90%?  The paper makes many claims about the behavior of sparsity based experiments largely considering only these two sparsity levels, but there is not enough evidence to make general statements of the\n behavior of hyperparameters as a function of sparsity when only\n considering these two extremes.\n\nAlso, important experimental details and definitions are omitted from the paper which are necessary to fully understand these results and the soundness of the conclusions drawn from them.  Specifically:\n\n-What is the budget used for the experiments in Figure 3?  The budget\n is actually a hyperparameter of this experiment, and thus it would be\n important to see whether the linear boundary between\n complete/incomplete exists when the budget is either increased or\n decreased, i.e., does this trend generalize for other budgets?\n\n-The definition of \"infeasible\" in Figure 3 is unclear.  How can a\n trial diverge?  It seems like, given a budget, a trial would simply remain\n incomplete if the budget expired and it had not reached the goal.\n \n-How were the plots in Figure 2 were generated, i.e.,\n were they first normalized then averaged across datasets?  Were\n sparsity results for 50% and 70% included for both Fashion-MNIST and\n CIFAR-10 (one and both, respectively, were missing for these in\n Figure 1)?\n\n-There seem to be implicit assumptions in Section 4.1, specifically, that $f$ is bounded.  For instance, if $f_{\\inf}$ goes to either positive or negative infinity, Equation 2 does not say anything helpful.  Furthermore, for\n non-finite $f$, the  expected average squared norm of the gradient\n could grow at a rate faster than linear K, which would invalidate the\n claim in the paper: \"the expected average squared norm of... during\n the first K iterations, indicates the degree of convergence; for\n example, it gets smaller as training proceeds with increasing K.\"  It is important to be clear and precise for these theoretical results.\n\nOther comments:\n-The term \"maximal data parallelism,\" which describes the minibatch\nsize which minimizes the number of steps to convergece, seems\nmislabeled.  shouldn't this be minimal data parallelism?  The smallest\nminibatch size should be the most parallelizable disregarding\ndevice-to-host communication latency.\n\n-While it is ok to forward reference much of the experimental details\n to the Shallue paper, please at least list the deep learning package\n and hardware used to run the experiments in the paper.\n\n-\"This aligns well with the classic result in\nlearning theory that large batch training allows using bigger learning\nrates\" <- please include citation for this claim\n\n-Note that (bounds on) Lipschitz constants in DNNs may estimated via:\nFazlyab, Mahyar, et al. \"Efficient and accurate estimation of\nlipschitz constants for deep neural networks.\" Advances in Neural\nInformation Processing Systems. 2019.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "B2q6vkntYlf", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "The paper presents both practical (based on measurements) and theoretical result on the impact of data parallelism and sparsity on the training of neural networks. \n\nThe practical results are based on extensive measurements of different combination of three datasets, two network models, and four optimization algorithms. Further, the batch size is varied from 2 up to 16384 and the sparsity between 0% and 90%. \n\nIn find the practical results interesting and thorough, and they cover a large part of the design space in order to give a good picture of the impact of data parallelism and sparsity. The downside is that the results are in line what is expected when varying data parallelism and sparsity. Exactly where the different plateaus are and the exact slope of the curves varies of course with the selected datasets and network, but the main picture is as expected. \n\nRegarding the theoretical results I have not been able to dive into details of them, mainly due to my own limitations. However, at a high-level view they seem correct and may have some impact, but I leave it to more competent people judge the novelty and contribution of these results.\n\nOther comments/questions:\n* I could find any information about the hardware that you have run your experiments on. Should be included in a revised version.\n* The scales of the x-axis in Fig 1 is different in different diagrams, which makes a comparison harder.\n* The caption of Fig 1 is far too long, move the contents to the main text instead.\n* Very good with an extensive Appendix with a lot of measurements.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-gHygxCBn3", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "1) Summary\nThe manuscript studies the effect of batch size at different sparsity levels (achieved by applying connection sensitivity pruning) on the required number of optimisation steps to reach a certain accuracy. The goal is to understand the interplay between those fundamental parameters. The empirical evaluation is performed for different triples of dataset, network architecture and optimisation scheme. The theoretical analysis is based on established bounds on the expected gradient norm.\n\n2) Strengths\n+ The paper is well written, the figures and the structure of the text is clear and the experimental setup is concise.\n+ The empirical evaluation is very exhaustive and conclusive and allows to draw precise conclusions.\n+ Code will be released to reproduce the results. Data sets are public domain.\n+ The theoretical analysis is enlightning.\n\n3) Concerns\n- While the results are very interesting, the authors could have been more explicit on how the results of this work could help the ordinary neural network user setting parameters in practice by suggesting e.g. a rule of thumb.\n\n4) Remarks/Questions\n  a) I found the last sentence of the Introduction a little bold.\n  b) \"Data parallelism\" is a synonyme for \"batch size\" and \"sparsity\" is equivalent to \"pruning\". This could be made more clear in the abstract already.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: On the positive side, this is a quite nice empirical exploration of the interaction between data parallelism and sparsity for training neural networks. The experiments are broad and detailed. On the negative side, the empirical results recapitulate what would be expected and what has already been seen in the literature, as the authors themselves point out ("We note that our observation is consistent with the results of regular network training presented in (Shallue et al., 2019; Zhang et al., 2019)."). And the theory presented, while it does explain the results nicely, is a trivial reformulation of the standard convergence result given in Equation 2. So while this is an interesting paper and the reviewers rated it positively on average, the sparsity exploration is _much_ more novel than the data-parallelism exploration, and there are significant novelty weaknesses that need to be taken into consideration.
Decision: Accept (Poster)