Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: 
This paper attempts to answer the implicit bias of SGD via a stability analysis on a single hidden layer univariate ReLU network. The main result is that a stable solution that can be found by a larger learning rate must be smoother. In detail, they show the weighted L1 norm of the second derivative is upper bounded by roughly $2/\eta$, where $\eta$ is the learning rate. 
main_review: This paper presents an interesting result about implicit regularization of SGD, that the stable local minimum which can be found by SGD must be smooth enough, depending inversely on the learning rate. The key observation is that for this specific single layer univariate network, the spectrum of the hessian at interpolating solution forms an upper bound for the weighted integral of the absolute value of the second derivative with respect to the input. One main technical contribution is that the authors also manage to deal with the case of non-smooth case. Experiments in Figure 1 also suggest the theory in this paper captures the phenomena in practical training pretty well.

However, the analysis in the paper doesn't give a complete story for the implicit bias of SGD, because a priori, it's not clear if SGD is always converging to a linearly stable solution. Moreover, it's not even clear if SGD is converging to any solution. On the other hand, note both the gradient and its noise vanish at any interpolation solution, thus even if a solution is not stable, SGD will not necessarily deviate it without stronger noise assumptions, which is non-vanishing at global minimum. In the analysis of the paper, the authors actually don't use any property about the noise, no matter if it's SGD noise, isotropic noise, or even just noiseless full-batch GD. The stability result still applies.

Therefore, the main message of this paper should be interpreted as, strong stability solution of SGD with a large learning rate is smooth but not "the function implemented by the network upon convergence gets smoother as the learning rate increases", as stated in the abstract, which is kind of overselling.

I also have a question about the claim that "a trained model tends to be smoother at the center of the training distribution". Is this verified by experiments or only from the upper bound? As far as I can see, the derivation of the upper bound is quite crude (e.g. fixing $u$ to be all one vector) and use $\min(g^+,g^-)$ to lower bound $g^+$ or $g^-$ and there's room to further tighten the bound. For example, if the authors don't use $\min(g^+,g^-)$ but $g^+$ or $g^-$ directly, does the weight in the bound still peak in the middle?

Overall, I found the idea of this paper quite novel and interesting. The writing is also clear and the paper is easy to follow. Thus I tend to accept the paper and would like to improve the score if the authors could give satisfactory answers to my above questions.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The goal of this paper is to extend existing results on stable minima found by SGD to the non-differentiable setting of ReLU networks. 

In particular, in its main contribution (Theorem 1) the paper shows that the solution found by SGD for 1-dimensional ReLU networks has bounded second derivative, under a weighted total variation norm. Moreover, this weighted norm is controlled by the step-size of SGD.

This implies that also for ReLU networks, SGD with large learning rate is biased towards smooth solutions. 
main_review: Strengths:
- The paper is to best of my knowledge the first work which analyzes minima stability in the non-differentiable setting of 1D ReLU networks. I found Theorem 1 a rather interesting and (to me) non-trivial result. 
- The theoretical results are to some extend confirmed by the experiments in Fig. 2. 

Weaknesses:
- The mathematical analysis framework used to deal with the non-differentiable setting appears not fully rigorous. 
- As mentioned in the paper, for ReLU nets f'' is a sum of Dirac measures, so it does not makes sense to talk about f''(x). This is due to the fact that the singular measure f'' does not have a density with respect to the Lebesgue measure dx. The mathematically rigorous formulation of the integral would be \int g(x) d|f''|(x), where |.| denotes the total variation of the measure f''.  In that context, I did not fully understand the meaning of |f''(x_j)| < \infty in Theorem 1. Does it mean that the input data points do not lie at the "jump points" of the function? This would seem like a quite strong restriction.  
- A more extensive empirical evaluation/demonstration of Theorem 1 would in my opinion greatly improve the work, e.g., plotting \int g(x) d|f''|(x) for different step-sizes \eta, and comparing it to 1 / \eta. 

Comments:
- I believe it needs to be assumed somewhere in Sec. 2.2 that \theta* is in the interior of one of the S_m? Otherwise, its gradient in (11) is not uniquely defined. Most likely this is not a strong assumption, since a tiny perturbation of \theta* should not influence the result. 

limitations_and_societal_impact: In this paper, a rather simplified setting is considered (1-hidden layer ReLU networks with one-dimensional inputs and outputs). Perhaps it can be mentioned to what extend the results can be generalized to the higher-dimensional setting. 

To me, it seems that the analysis does not seem to easily extend to this higher-dimensional setting. In the one-dimensional case, the second derivative of the function can be represented by a sum of Dirac measures, while in the higher-dimensional setting quite complicated scenarios can appear.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies a single hidden layer univariate ReLU network. The authors show that stable solutions learned by SGD will be functions whose second derivative has bounded weighted L1 norm. Besides, the learned function gets smoother as the learning rate increases.
main_review: This paper shows that the earned stable solutions will be smoother if we increase the learning rate. Overall this paper is well organized. The results are interesting and seem solid. However, I still have the following concerns:

1.  Because the NN function f is a pice-wise linear function for both input x and parameter \theta. Thus the classical second derivative |f''(x)| doesn't exist. It would be much better if the authors can give the weak definition of |f''(x)| in the main part of the paper rather than in the appendix(line 112). Besides, I get quite confused about the condition |f''(x_j)| < \infty (line 174) because f''(x) is sum of weighted Dirac delta function. The authors may want to add some comments on it.

2. In the definition of linear stability and generalized linear stability(Definition 1 &2), there is a parameter $\epsilon$. Why doesn't $\epsilon$ show up in the condition of Theorem 1&2?

3. Currently, the result of theorem 2 could not hold for the overparameterized setting where the neuron number k > > n, the input dimension also needs to be set as 1.  Could the result of this paper be generalized to the setting without those limitations?
limitations_and_societal_impact: Yes, the authors adequately addressed the limitations and potential negative social impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the smoothness of the functions represented by single variate two-layer neural networks at minima with different flatness, and connect this smoothness with the implicit bias of (stochastic) gradient descent to flat minima. Firstly, for a twice differentiable minimum found by SGD, an upper bound for the leading eigenvalue of the loss function's Hessian matrix (with respect to parameters) is derived depending on the learning rate. Then, a weighted L1 norm of the second derivative of the model function (with respect to input data) is upper bounded by the Hessian's leading eigenvalue. Combining these two bounds, the weighted L1 norm of the model function's second derivative is bounded by a quantity depending on the learning rate. This result implies that SGD with bigger learning rate finds flatter minima, and thus finds smoother functions. The result only considers the minima found by optimization algorithms, hence it is independent with initialization. 

For neural networks with ReLU activation, minima are sometimes not differentiable. The analysis above is extended to this case and similar bounds are also provided. The theorem works in the mildly over-parameterized case in which the number of neurons is slightly bigger than the number of training data. 

Numerical experiments show that GD with bigger learning rate can indeed find smoother functions, especially in the region where training data are densely distributed. This observation is consistent with the theoretical results. 
main_review: Flat minima are widely known to have better generalization performance than their sharp counterparts. Many works have explored the connection between algorithms and flatness. Some of them build connection between algorithms and the flatness of the minima they found, while others design new algorithms which can find flatter minima. This work, however, build a more complete theoretical understanding by also addressing another problem: the implicit regularization mechanism of flat minima. The authors show that models at flat minima usually represent smoother functions, which (partially) explains why flat minima generalize better. Exploring the connection between the landscape in the parameter space and the landscape in the input data space seems like a promising way to study the implicit regularization of optimization algorithms. 

Some major comments and concerns are:
1. The bounds on \lambda_max only depend on the learning rate, and are independent with batch size, and actually this bound is trivial. Hence, the bounds work for full batch GD and do not distinguish GD and SGD, which means the additional implicit regularization effect of SGD is not shown by the results. In practice, though, SGD is usually observed to have better performance than GD. Bounds for the minima found by SGD depending on both the learning rate and the batch size are derived in existing works, such as [52] cited in the paper. Is it possible to derive similar finer bounds for the smoothness of the model functions? 

2. The analysis is conducted in a restrictive setting: single variate two-layer neural networks. This limits the insights provided by and the potential application of the theory. What is the hardness of extending the analysis to high dimensional setting? If theoretical extension is nontrivial, numerical experiments of the high dimensional problem may also show the generality of the theory. 

3. On line 135-136, the authors said "in the setting of ReLU networks, this (approximate) common eigenvector assumption holds true" regarding to the assumptions in Lemma 2 above. It there any justification of this claim?
limitations_and_societal_impact: The authors have adequately addressed the limitations. Since this is a theoretical study, I do not think there will be any direct negative societal impact.
review_title: null

Meta-review: This work analyzes the prediction surface of weights reached by descent methods, arguing it is smooth on average (integral of second derivative is small).  Reviewers are supportive, but had many detailed comments, to which the authors in turn gave detailed responses. 
 I believe incorporating these discussions and comments in revisions will greatly strengthen the paper, and urge the authors to do so.
Decision: Accept (Poster)