Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: After reviewing the authors' response:
The 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.

========================================

The 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).

The 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
sparsity 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
 behavior of hyperparameters as a function of sparsity when only
 considering these two extremes.

Also, 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:

-What is the budget used for the experiments in Figure 3?  The budget
 is actually a hyperparameter of this experiment, and thus it would be
 important to see whether the linear boundary between
 complete/incomplete exists when the budget is either increased or
 decreased, i.e., does this trend generalize for other budgets?

-The definition of "infeasible" in Figure 3 is unclear.  How can a
 trial diverge?  It seems like, given a budget, a trial would simply remain
 incomplete if the budget expired and it had not reached the goal.
 
-How were the plots in Figure 2 were generated, i.e.,
 were they first normalized then averaged across datasets?  Were
 sparsity results for 50% and 70% included for both Fashion-MNIST and
 CIFAR-10 (one and both, respectively, were missing for these in
 Figure 1)?

-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
 non-finite $f$, the  expected average squared norm of the gradient
 could grow at a rate faster than linear K, which would invalidate the
 claim in the paper: "the expected average squared norm of... during
 the first K iterations, indicates the degree of convergence; for
 example, it gets smaller as training proceeds with increasing K."  It is important to be clear and precise for these theoretical results.

Other comments:
-The term "maximal data parallelism," which describes the minibatch
size which minimizes the number of steps to convergece, seems
mislabeled.  shouldn't this be minimal data parallelism?  The smallest
minibatch size should be the most parallelizable disregarding
device-to-host communication latency.

-While it is ok to forward reference much of the experimental details
 to the Shallue paper, please at least list the deep learning package
 and hardware used to run the experiments in the paper.

-"This aligns well with the classic result in
learning theory that large batch training allows using bigger learning
rates" <- please include citation for this claim

-Note that (bounds on) Lipschitz constants in DNNs may estimated via:
Fazlyab, Mahyar, et al. "Efficient and accurate estimation of
lipschitz constants for deep neural networks." Advances in Neural
Information Processing Systems. 2019.

review_title: Interesting theoretical results, however, some empirical claims are drawn without enough evidence

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

The 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%. 

In 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. 

Regarding 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.

Other comments/questions:
* I could find any information about the hardware that you have run your experiments on. Should be included in a revised version.
* The scales of the x-axis in Fig 1 is different in different diagrams, which makes a comparison harder.
* The caption of Fig 1 is far too long, move the contents to the main text instead.
* Very good with an extensive Appendix with a lot of measurements.

review_title: The paper presents a practical and theoretical evaluation of the impact of data parallelism and sparsity on neural network training. Extensive measurements confirm the practical / earlier general knowledge, while the theoretical results seems novel.

final_score: rating: 7: Good paper, accept
review_content: 1) Summary
The 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.

2) Strengths
+ The paper is well written, the figures and the structure of the text is clear and the experimental setup is concise.
+ The empirical evaluation is very exhaustive and conclusive and allows to draw precise conclusions.
+ Code will be released to reproduce the results. Data sets are public domain.
+ The theoretical analysis is enlightning.

3) Concerns
- 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.

4) Remarks/Questions
  a) I found the last sentence of the Introduction a little bold.
  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.
review_title: Interesting theoretical and empirical study of the interplay of batch size on the required number of optimisation steps at different pruning levels

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)