Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work presents a novel framework of "Sobolev regularization" effect of stochastic gradient descents for quantifying and establishing wideness of a global interpolating optimum in SGD. The key idea is that because the neural network input $x$ is multiplids to weights $W_1$ and then provided into the neural network, regularity properties of the weights near the interpolating global optimum imply regularity properties (wideness) of the minimum.
main_review: Overall, I feel that the viewpoint presented in this work is novel and worthy of publication. The key insight is that since the input $x$ and the neural network weights are first multiplied and then entered into the network, so regularity (stability) properties on $W$ can be transferred onto regularity (wideness/small Sobolev norm) properties with respect to $x$ is a very nice one.

I have one not-so-minor comment. Definition 5 seems to be incomplete; the relation between $W^*$ and $\tilde{W}^{\otimes k}_t$ is not completely specified. (All that is said is that $\{W_t\}$ is close to $W^*$.) I think the issue is that the authors have the mental model of an interpolating global minimum as an isolated minimum. However, there is some recent evidence that a connected set of global minima is a more accurate model.
https://proceedings.neurips.cc/paper/2018/hash/be3087e74e9100d4bc4c6268cdbe8456-Abstract.html
http://proceedings.mlr.press/v119/shevchenko20a.html
Can the authors comment on how having a connected set of interpolating global minima may or may not affect the analysis?
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper shows that due to the multiplicative structure of input data and first layer parameters in a MLP neural network the flat minima regularizes the norm of the gradient of the model and then explains its generalizability. It also shows that SGD actually regularizes higher-order moments of the gradient of the noise when it is close to an interpolating minima. Utilizing this property of SGD and multiplicative structure shows that SGD minimizes the Sobolev seminorms of the model. The presented analysis is based on quadratic estimation of the objective around the minima and uses linear stability analysis.       
main_review: Understanding the implicit regularization imposed by SGD has great importance in understanding the generalization performance in deep neural networks. This paper utilizes the product structure between the first layer parameter and the input data and discovers the relation between flat minima and the gradient norm or the Lipschitz constant of the model that improves the stability of the model. 

However, the major theoretical contribution of the paper is local and based on a quadratic approximation of the model around an interpolating local minima. The major part of the analysis is based on the existing results in the literature for quadratic models. 
Besides, it makes a bunch of assumptions and it does not explain which of them are true in a multi-layer perceptron model. 

In terms of the write-up, there are a bunch of typos here and there that need to be fixed such as stocahstic instead of stochastic in the title. 

My question


1- It is not clear how restrictive the assumptions the paper makes. It would be clarifying to explain if these assumptions are true for deep neural networks. 

2- The product structure has been shown that holds for MLP. Does it hold for other architectures such as CNN or transformers?

3- In practice we usually normalize the data, therefore some x_i could be very close to zero. Based on this, how tight do you think the upper bound in 4 could be?

4- You assume that SGD with fixed step size would converge to an interpolating solution. It would be helpful to explain under which condition this can happen and why you think MLP satisfies these requirements.   

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper extends previous stability analysis ([30]) to high-order moments of the iterator. They characterize the implicit regularization of SGD by showing that a stable global minimum must satisfy conditions regarding its flatness and non-uniformity. In addition, the authors build relations between the model function’s derivative w.r.t. the parameters and w.r.t. to the inputs. Using these relations, they provide upper bounds for the Sobolev seminorm of the model function at stable SGD interpolating solutions. In addition, under additional smoothness conditions, the authors were able to extend that last result to a neighborhood of the training data. Finally, the authors built upon the Sobolev regularization and use it to provide bounds on the generalization performance and adversarial robustness.
main_review: This paper examines theoretically how does SGD selects the global minima it converges to. Specifically, the authors analyze the implicit regularization effect and generalization performance of the solution found by SGD using a linear stability analysis. 

The paper main contributions are:
-	The authors prove upper bounds on the gradients’ moment at the solution found by SGD, assuming this solution is stable. These conditions also include control on the flatness and non-uniformity. This result provides a better characterization of the implicit bias of SGD.
-	The authors provide upper bounds for the Sobolev seminorm of the model function at stable SGD interpolating solutions. This implies that the Sobolev seminorms of the model on the training data are regularized by the linear stability. In addition, under some smoothness assumption, this result is extended to a neighborhood of the training data. These results suggest a possible explanation for the good generalization of flat minima.
-	Under additional assumptions on the data distribution, the authors provide bounds on the generalization error and adversarial robustness.

Clarity/writing: 

I enjoyed reading the paper. The paper is well written, the assumptions and results are clearly stated, and many explanations were provided throughout the paper. 

My main question:
-	Many of the upper bounds suggested in the paper include the norm of the first layer weights. Can the author extend on the assumption that the input layer weights are not very large?

Minor comments:
-	There is a typo in the title (Stocahstic --> Stochastic) 
-	I think that adding “sharpness” and “non-uniformity” as formal definitions will make the paper a bit clearer (these terms were explained verbally but it is easy to miss this)

---

Update: Thank you for the detailed rebuttal and for elaborating on the upper limit with experimental results. This helped to elevate my concern.

limitations_and_societal_impact: The authors thoroughly discussed the limitations of their results.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Prior work on minima stability for SGD considered linear stability in expectation using second order moment. This paper considers linear stability in higher moments, while providing necessary and sufficient conditions for it. Using these conditions and the multiplicative structure of neural networks, the authors show that the Sobolev semi-norm of SGD solutions (w.r.t. the input) is bounded from above. Then, under certain smoothness assumptions on the learned function and the target function, the authors prove generalization bounds and adversarial robustness.
main_review: The article is well written, and the proofs are rigorous. I carefully checked the proofs of Theorems 1-3, and they look fine. On the other proofs I went over more generally, and they also seem good. 

Here are my comments:
1.	Why should we consider higher moments for linear stability? E.g., why second order is not sufficient to say that a minimum is stable? If a minimum is not stable for some order but is stable in a lower order, what this tells us? Can a minimum be stable for any order? if so, does it have special properties?
2.	The bounds proved by the multiplicative property, namely Theorem 4-7, can be loose. For example, consider the simple case of a two-layer univariate network with ReLU activation (i.e. scalar input/output with a wide hidden layer). Since ReLU is positive homogenous we can arbitrarily increase the $ \ell_p $-norm of the first layer while preserving the function implemented by the network, and thus making the bounds trivial. This is true for any network with ReLU activation (or its variants).
3.	From 2., it is not true to say that SGD implicitly regulate the Sobolev semi-norm of the function implemented by the network, since there is no (proven) mechanism in SGD that keeps the the norm of the first layer small.
4.	The authors claim that Corollary 3 is more accurate than previous known result, which is written in Proposition 1 (see row 235), however I did not see any explanation nor proof for this claim (maybe I have missed it...).
5.	Most of the results hold only for the quadratic loss.
6.	I think that Lemma 1 is used to prove necessity in the proof of Theorem 1, and not sufficiency.

limitations_and_societal_impact: See above
review_title: null

Meta-review: All reviewers have praised the clarity of the paper as well as the soundness and novelty of the results. Some important questions regarding completeness of some definitions and applicability of the current assumptions have been raised in the reviews, which the authors have clarified with a strong rebuttal. I encourage the authors to incorporate these remarks in the camera ready version.
Decision: Accept (Spotlight)