Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper introduces the concept of "gradient confusion" to explain why neural networks train fast with SGD. They also study the effects of width, depth on gradient confusion. 
- The theoretical results assume that the data is sampled from a sphere and do not really give much insight into the effect of width and depth. 
- There are some confounding factors in the experiments and there needs to be a better comparison to some related work. 
Detailed review below:
Section 1:
- Please clarify how "gradient confusion" relate to the interpolation conditon of Ma et al, 2017 and the strong growth condition of Vaswani et al? 
- If we run SGD with a constant step-size, it will bounce around the optimal point in a ball with radius that depends on the step-size. If I keep decreasing the step-size, this radius shrinks. How does gradient confusion relate to the step-size? Is it upper-bounded by a quantity that depends on the step-size and the batch-size?
Section 2:
- Definition 2.1: Why should this condition hold for "all" points w? Isn't it necessary only at w^* or in a small neighborhood around it? 
- The gradient confusion parameter \eta should depend on the batch-size. Please clarify this. 
- Figure 1: Previous work (Ma et al, Vaswani et al, Gunasekhar, 2017) all have shown that fast convergence can be obtained using SGD with a constant step-size with over-parametrized models and explained it using interpolation. What is the additional insight from gradient confusion?
- "Suppose that there is a Lipschitz constant for the Hessian" - This is a strong assumption and a vague argument, that is confusing rather than insightful. Please justify why this is a valid assumption for neural network models.
Section 3:
- If E_i || \nabla f_i(w)  ||^2 = O(\epsilon) => gradient confusion = O(\epsilon). Isn't the E_i || \nabla f_i(w)  ||^2 exactly the strong growth condition in Vaswani, et al. Can the gradient confusion results be directly derived from the results in that paper? Please compare. Also compare and cite "Stochastic Approximation of Smooth and Strongly Convex Functions:
Beyond the O(1/T ) Convergence Rate", COLT 2019. 
Section 4:
- Please compare against the previous results that assumed the data to be sampled from a sphere. 
- Thm 4.1: The theorem bounds the probability that gradient confusion holds for a given \eta. But the bounds of section 3 are vacuous even if the theorem holds with probability one, but for a large value of \eta. There needs to be an upper bound on \eta. Please clarify this. 
- Please compare against the results of this paper by Arora et al: "On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization"
- For the effect of layer width, the analysis is only for the initializated weights and does not consider the optimization, which is what the paper claimed in the introduction. Am I missing something? Please justify this. The gradient confusion can decrease as the optimization progresses? 
Section 5:
- "We reduce the learning rate by a factor of 10" But all the theory is for a constant step-size. Please explain this discrepancy. 
- in Figure 2, in the second figure, why is there a sharp full in the pairwise cosine similarities. 
- In all these experiments, explain why the batch-size and the step-size is not a confounding factor?
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: 
[Summary]
This paper introduces gradient confusion, a bound on the negated dot product of gradients at two data points, and studies its effect on the optimization of neural networks with SGD. If gradient confusion is high, reducing the loss on one data point with SGD increases it on another data point. Theoretical results show that (1) with a fixed learning rate, lower gradient confusion results in faster learning, and (2) increasing the width and decreasing the depth of a network reduces gradient confusion. The experiments corroborate these findings and also show that batch normalization and skip connections can reduce gradient confusion and speed up the training. 

[Decision]
I vote for accepting this paper. Although most of the results mirror classical bounds that considered gradient variance, the introduced measure allows analyzing the speed of learning even if gradient variance itself is unbounded or hard to analyze. This can help with understanding the current architectures and designing new ones with desirable properties. 

[Comments]
Theorem 3.1 shows that, for a constant learning rate, gradient confusion controls the SGD noise floor. If the noise floor is small, convergence to a low error is possible with a larger learning rate, and this seems to be why reducing gradient confusion speeds up SGD. In the experiments, I would expect that the chosen learning rate for networks with low gradient confusion would generally be higher. Reporting the best learning rate schedule for each network can clarify if this is true.

Are the effects of width, depth, batch normalization, and skip connections on L and \mu in Theorem 3.1 well understood? It is possible that these architectural choices change the speed of learning by modifying these constants rather than just reducing gradient confusion.

In section G in the Appendix it is said: "In general, it is not tractable to prove the concentration results in section 4 using the covariance matrix of the gradients alone without further unrealistic assumptions...." Why is bounding the gradient variance under the assumptions like bounded weights and standard initialization hard (or impossible) and a different measure like gradient confusion is necessary?

[Minor remarks]
- In Section 5: "selected the run that achieved the lowest training loss value"->"selected the learning rate that achieved..."
-------------
After rebuttal: I have read the author's response, the other reviews, and the modification. The response addresses my questions. The new revision shows the proposed measure's practical significance and robustness to one sample. I raised my score. 
review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: This paper targets to understand some key factors that might influence the training speed of neural networks. It defines a concept called "gradient confusion" to quantify these factors. Roughly speaking, this term captures the disagreement of the descending directions suggested by different samples. 

On the positive side, to understand the training procedure is important to the deep learning community. The idea on "gradient confusion" is quite straightforward and easy to understand. The paper is clearly written. 

However, there are some essential drawbacks of the paper that make me lean towards rejecting it. 

First, this concept of "gradient confusion" is very similar to the "gradient diversity" introduced more than 2 years ago in [1]. The term proposed in [1] measures the "gradient confusion" relative to the average of gradient norms, and is an averaged case rather than the worst case version. (This actually brings a second issue of the "gradient confusion" which makes the definition less useful.) However the paper has not discussed this existing work and the contribution on top of it. 

Second, the "gradient confusion" is not a robust term even to one outlier sample. Since the definition in Eqn. (3) measures the worst case scenario, one could add an outlier sample that easily makes the eta arbitrarily large and the latter bound on the convergence will be meaningless. In comparison, the "gradient diversity" in [1] of the averaged value makes more sense to me. 

Third, the proposal of a new theory should be in favor of at least some applicable cases. In this paper, the take-home message seems to be when the samples are pushing the gradient towards the same direction, the training becomes faster, which is very legit and people believe this. However, what can we do about this? The authors fail to propose some interesting applications that could make use of the "gradient confusion" to help the training. For instance, the work of [1] has made use of the gradient diversity to accelerate distributed learning which could be one application. I encourage the authors to work towards some useful applications concerning this new concept.  

To sum up, I don't think this paper brings out some real contributions to the community and should not be accepted. 


[1]  Yin, Dong, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett. "Gradient diversity: a key ingredient for scalable distributed learning." arXiv preprint arXiv:1706.05699 (2017).
review_title: Official Blind Review #2

Meta-review: This paper introduces the concept of gradient confusion to show how the neural network architecture affects the speed of training. The reviewers' opinion on this paper varies widely, also after the discussion phase.  The main disagreement is on the significance of this work, and whether the concept of gradient confusion adds something meaningful to the existing literature with respect to understanding deep networks. The strong disagreement on this paper suggest that the paper is not quite ready yet for ICLR, but that the authors should make another iteration on the paper to strengthen the case for its significance.

Decision: Reject