Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: Review of "A mechanism of ... deep learning"

This paper studies the generalization performance and implicit regularization of deep learning. In particular, the authors propose a novel technique called "random walk analysis" to study the nonlinearity of the neural network with respect to the input data points. Moreover, the authors prove that for a class of 1-d continuously differentiable functions, SGD can achieve O(n^{-2}) generalization error bound.

Overall this paper is well written and easy to follow. The linear approximation with respect to input parameter space is also interesting and seems to be useful in the generalization analysis. Besides, I have the following comments and concerns.

1. I am a little bit confused by the definitions "Priori generalization estimates" and "posterior data distribution". I would like to see clearer description in the introduction.
2. I would like to see more discussion on Theorem 2 in the surrounding text, it is quite unclear to me why Theorem 2 is important and how it can be related to the "implicit regularization".
3. I do not see the proof of (6) in Section 3.2.
4. It seems that the generalization results in this paper are difficult to be generalized to high-dimension regimes. For example, if you assume that each entry of the training data point is generated from the uniform distribution in the interval [0, v], the density of training sample would be \mu = n/(v^d), and the resulting generalization bound would be O(v^d/(n\delta)), which is extremely large.
5. It seems that the generalization results hold for any data distribution. However, it is widely known that if the training data is randomly labeled, the neural network trained by SGD cannot achieve small population risk, which contradicts the result in Theorem 4.


----------------------------
After reading the authors' response, I still think that the generalization results in this paper are not significant and important, and how the theoretical results can be related to the implicit regularization. Thus I would like to keep my score.

review_title: Official Blind Review #3

final_score: rating: 1: Reject
review_content: This paper studies the implicit regularization in deep learning under the over-parameterized setting. In specific, the authors study the neural network outputs and “pre-activation values” on line segments connecting two training data inputs and characterize an implicit regularization based on it. I have the following concerns:

First of all, it is not clear to me why Theorem 2 is relevant to “implicit regularization”. To my knowledge, implicit regularization or implicit bias statements in prior works cited in this paper are all about the convergence to a specific solution for underdetermined problems. For example, “among all solutions that fits the data, gradient descent converges to minimum distance solution to initialization (linear model square loss), maximum margin solution (linear model exponential loss), minimum nuclear norm solution (matrix sensing with small initialization)”. In comparison, Theorem 2 just gives some bounds that holds for every sgd iteration. I cannot see any connection between Theorem 2 and implicit regularization.

Moreover, the authors’ claim “the implicit regularization in over-parameterized DNNs has not been identified” is not correct. As the authors mentioned,  the neural network is close to its linear approximation model with respect to weight parameters at initialization. Therefore the implicit bias of (stochastic) gradient descent for DNNs in the over-parameterized regime is essentially implicit bias of (stochastic) gradient descent for linear models (for square loss). In Arora et al., 2019b it has been proved that infinitely wide neural networks trained with gradient flow converges to the NTK-based kernel regression solution.  So at least for gradient flow with square loss, the implicit bias of DNNs has been well-studied. In fact in a missed reference [2], essentially the implicit bias for both gradient descent and stochastic gradient descent has been studied. The remark “in most cases, the authors used GD to derive their results by the NTK analysis” is also not convincing. Allen-Zhu et al., 2018a,b, Allen-Zhu & Li, 2019 and missed references [1,2,3,4] all studied SGD of over-parameterized neural networks, and some are not exactly in the so-called NTK regime. The authors should also compare their generalization bounds with existing results for SGD (Allen-Zhu et al., 2018a, Allen-Zhu & Li, 2019) and [3].

Finally, Theorem 4 only considers one-dimensional models, which is not a very interesting problem setting. Its proof might also be flawed. In fact, the setting in Section 4 is not consistent with Theorem 1, since Theorem 1 requires that all inputs have unit norm and their last coordinate should be a constant. For one dimensional case, this means all inputs must be the same scalar! Even if we ignore the last coordinate assumption in Theorem 1, for 1D case all inputs are still reduced to +1 or -1’s. 


[1] Difan Zou, Yuan Cao, Dongruo Zhou, Quanquan Gu, Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
[2] Samet Oymak, Mahdi Soltanolkotabi, Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
[3] Yuan Cao, Quanquan Gu, Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
[4] Difan Zou, Quanquan Gu, An Improved Analysis of Training Over-parameterized Deep Neural Networks





review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This paper suggests a new technique to analyze the implicit regularization caused by ReLU activations. They bound the generalization error by two terms: 1) one term that represents the distance between the trained network output and a piecewise linear function built based on the set of training points and 2) another term that represents the distance between the piecewise linear approximation and the desired target. The first term is bounded using a random walk type of analysis, which to the best of my knowledge is novel.
I find this technique rather interesting and technically sound, although I do have a number of concerns and I'm at the moment more on the reject side, although I will re-consider my score if the authors can provide satisfactory answers.

Generalization to more complex activation functions
If I understand correctly, the interpolation technique between two points only works for ReLU functions. If one were to try to generalize the analysis to more complex non-linear functions by using a more complex interpolation schemes, wouldn’t you then have a random walk in high-dimensions? If so, wouldn’t that be a problem given the different properties of Brownian motion in high-dimensions?

Generalization to smooth activation functions
Another question related to the previous one is whether one could hope to generalize the analysis to smooth activation functions. I believe this is also a drawback of combinatorial techniques such as Hanin and Rolnick which have to rely on the discrete nature of the breakpoints.

Generalization bound is only derived for 1-d functions
Theorem 2 is derived for each dimension independently while the generalization results in Theorem 4 are for 1-dimensional inputs. Where is the difficulty in generalizing these results to higher dimensions?

Prior work on generalization of SGD
I was really expecting a discussion about how the generalization bound derived in this paper compares to prior work, e.g.
Hardt, Moritz, Benjamin Recht, and Yoram Singer. "Train faster, generalize better: Stability of stochastic gradient descent." arXiv preprint arXiv:1509.01240 (2015).
Kuzborskij, Ilja, and Christoph H. Lampert. "Data-dependent stability of stochastic gradient descent." arXiv preprint arXiv:1703.01678 (2017).
Brutzkus, Alon, et al. "Sgd learns over-parameterized networks that provably generalize on linearly separable data." arXiv preprint arXiv:1710.10174 (2017).
And many others…
For instance the bound derived in Hardt et al. is also of the order O(n^-2). The bounds in Kuzborskij are also data-dependent and so are yours since your generalization bound depends on the density of the training points. Can you comment on this? What specific insights do we gain your analysis?

Noise SGD
My understanding is that the authors assume that the noise of SGD is Gaussian. Although this is commonly used when analyzing SGD, there is evidence that the noise is actually not Gaussian, see e.g.
Daneshmand, Hadi, et al. "Escaping saddles with stochastic gradients." arXiv preprint arXiv:1803.05999 (2018).
Simsekli, Umut, Levent Sagun, and Mert Gurbuzbalaban. "A tail-index analysis of stochastic gradient noise in deep neural networks." arXiv preprint arXiv:1901.06053 (2019).
I feel this is worth pointing out and one could perhaps also extend this analysis to Heavy-tail noise. I would expect that the results would still hold in expectation but perhaps with a slightly worse probability.

Influence step size SGD
Using larger step sizes in the SGD updates increase the influence of the noise. I was expecting this to somehow be captured in your analysis but I fail to see where it appears. Can you comment on this? 

Proof Lemma 3
The derivation of Eq. 10 does not seem completely justified in the proof in the appendix. The authors essentially prove that the length of the gradient gap is bounded by |S| but why is the coefficient \omega distributed according to a normal distribution. It seems to me that you need the noise of SGD to be Gaussian for such statement to hold. Can you confirm this? If so, I think this needs to be clearly stated as an assumption since -- as pointed out above -- this is not necessarily true in practice.

Minor: proof Theorem 2
It seems rather trivial but for completeness, you should write the proof of Eq. (6) in Theorem 2. 

“A priori estimates”
This is a terminology that is often used in the paper but never defined. What do you mean by “a priori” in this context?

Minor comment
I would move footnote 3 directly in the main step. I think it is important to point out that the steps of the random walk correspond to the breakpoints.

review_title: Official Blind Review #1

Meta-review: This paper analyzes a mechanism of the implicit regularization caused by nonlinearity of ReLU activation, and suggests that the learned DNNs interpolate almost linearly between data points, which leads to the low complexity solutions in the over-parameterized regime. The main objections include (1) some claims in this paper are not appropriate; (2) lack of proper comparison with prior work; and many other issues in the presentation. I agree with the reviewers’ evaluation and encourage the authors to improve this paper and resubmit to future conference.

Decision: Reject