Venue: ICLR 2017 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper shows that when a larger mini-batch is used (in the serial setting), the number of samples needed to be processed for the same convergence guarantee is larger. A similar behavior is discussed for using multiple learners in asynchronous SGD. This behavior has been known in convex optimization (e.g., "Better Mini-Batch Algorithms via Accelerated Gradient Methods", NIPS 2011). There, the convergence is of the form O(1/\sqrt{bT}+1/T), and so using bT samples only lead to \sqrt{b} time improvement. This paper extends a similar result to the nonconvex case (but the underlying mathematics is mainly from [Ghadimi & Lan, 2013]). However, this behavior is also known and indeed has been summarized in the deep learning textbook (chapter 8). Hence, the novelty is limited.

The theoretical results in this paper suggest that it is best not to use mini-batch. However, using mini-batch is often beneficial in practice. As discussed in the deep learning textbook, using mini-batch allows using a larger learning rate (note that this paper assumes the same learning rate for both mini-batch sizes). Moreover, multicore architectures allows parallel execution of mini-batch almost for free. Hence, the practical significance of the results is also limited.

Other comments:
- Equation (4): since the same number of samples (S) is processed and S=MK, where M is the mini-batch size and K is the number of mini-batches processed (as mentioned in the first paragraph of section 2), when two different mini-batch sizes are considered (M_l and M_h), their K's should differ. However, the same K is used on the LHS of (4).

- Figures 1 and 2: As convergence speed is of main interest, why not show the training objective instead?
review_title: review

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper theoretically justified a faster convergence (in terms of average gradient norm attained after processing a fixed number of samples) of using small mini-batches for SGD or ASGD with smaller number of learners. This indicates that there is an inherent inefficiency in the speed-up obtained with parallelizing gradient descent methods by taking advantage of hardware. This paper looks good overall and makes some connection between algorithm design and hardware properties.

My main concern is that Lemma 1 looks incorrect to me. The factor D_f / S should be D_f/ (S*M) for me. Please clarify this and check the subsequent theorem.
review_title: Check Lemma 1

final_score: rating: null
review_content: I can't seem to find the complete proof of Theorem 2. The main body of the paper shows only the outline and states the complete proof is in the appendix, whereas the appendix also only shows the outline and states: "See the appendix for complete proof". Is the appendix showing the complete proof? If not, the proof needs to be added.

Minor: page 1: "...often it is often...", page 3: "alarger"
review_title: Clarifications

final_score: rating: null
review_content: Your theoretical results suggest that for SGD, not using mini-batch (i.e., mini-batch size = 1) is the best. On asynchronous SGD, your results suggest that using only 1 learner is best. These seem contradictory to the common practice. Can you please explain?
review_title: usefulness of mini-batch

final_score: rating: null
review_content: What is the improvement or difference between the result in this paper and Lian et al. 2015?
review_title: improvement over existing result

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper addresses the problem of the influence of mini-batch size on the SGD convergence in a general non-convex setting. The results are then translated to analyze the influence of the number of learners on ASGD. I find the problem addressed in the paper relevant and the theoretical part clearly written. The experimental evaluation is somehow limited though. I would like to see experiments on more data sets and more architectures, as well as richer evaluation, e.g. N=16 is a fairly small experiment. It would also enhance the paper if the experiments were showing a similar behavior of other popular methods like momentum SGD or maybe EASGD (the latter in distributed setting). I understand the last evaluation does not directly lie in the scope of the paper, though adding these few experiments do not require much additional work and should be done.
review_title: Interesting paper

Meta-review: The work addresses the question of whether mini-batching improves the convergence of stochastic gradient methods, in terms of the number of examples, in the general non-asymptotic/non-convex setting of Ghadimi and Lan. Similar results are already known (at least as folk theory) in simpler regimes, but this result is novel. The reviewers are mixed in their opinions of the paper, but AnonReviewer4 brings up a point that deserves further attention: the analysis assumes that the same step-size is used for different mini-batch sizes. Because of this assumption, the conclusion of the paper is misleading. One of the effects of increasing the mini-batch is to decrease the variance of the estimator, which allows a larger step-size. With this larger step-size the net effect of increasing the mini-batch can actually be positive even in terms of the number of examples. Fixing the step-size removes the chance for the mini-batch strategy to do better in theory, and there is indeed a large amount of empirical evidence that mini-batches can lead to practical improvements. I do think the authors should continue this work, but I think accepting the current version is problematic because of the current conclusion.
Decision: Reject