Despite a lot of theoretical efforts, very little is known about mechanisms of implicit regularization by which the low complexity contributes to generalization in deep learning. In particular, causality between the generalization performance, implicit regularization and nonlinearity of activation functions is one of the basic mysteries of deep neural networks (DNNs). In this work, we introduce a novel technique for DNNs called "random walk analysis" and reveal a mechanism of the implicit regularization caused by nonlinearity of ReLU activation. Surprisingly, our theoretical results suggest that the learned DNNs interpolate almost linearly between data points, which leads to the low complexity solutions in the over-parameterized regime. As a result, we prove that stochastic gradient descent can learn a class of continuously differentiable functions with generalization bounds of the order of O(n −2 ) (n: the number of samples). Furthermore, our analysis is independent of the kernel methods, including neural tangent kernels.
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.