Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper analyzes the implicit bias of gradient descent on a wide two-layer network with standard parameterization and initialization and the squared loss. It is first proved that in this setting, gradient descent on both layers is close to gradient descent on the second layer. Then the implicit bias of gradient descent on the second layer is characterized for a 1-dimensional regression problem, which can also be generalized to the high-dimensional case. 

I think it is nice to have an explicit characterization of the minimum-kernel-norm solution. Moreover, the observation that gradient descent with the standard parameterization and initialization basically only trains the second layer is also interesting. 

However, the current presentation also has many limitations:
1. Theorem 1, 2 and 6 consider gradient descent on an adjusted training set. Specifically, Theorem 1 and 2 claim the existence of u and v, which are used to adjust the training set, but it seems that how to find u and v is not discussed. Moreover, above Theorem 6, it is said that "If u and v in the solution of (17) are small, then the solution is close to the solution of (16)." How should we find u and v? Can it be proved that u and v are small?
2. The function g given by Theorem 1 and 2 are similar to the results presented in (Savarese et al., 2019) and (Ongie et al., 2020). Can you include a detailed comparison with their results and proof techniques?
3. In Theorem 4, it is assumed that inf_n \lambda_\min (\Theta_n) > 0. However, this can usually be proved in the NTK setting, for example in (Simon S. Du, Xiyu Zhai, Barnabas Poczos, Aarti Singh. Gradient Descent Provably Optimizes Over-parameterized Neural Networks). Can this assumption be proved?
4. The appendices should be included. 
review_title: A characterization of the implicit bias of gradient descent on regression problems and two-layer networks

final_score: rating: 7: Good paper, accept
review_content: ######################################################################

1.  Paper Summary 

This work analyzes the implicit bias of gradient descent for wide, 1 hidden layer networks used for regression and provides a characterization of this bias in function space.  At a high level, as network width increases, gradient descent leads to a solution given by a variational problem penalizing the product of the curvature and the square of the second derivative.  The proof of this proceeds as follows: (1) The solution given by gradient descent on the network can be approximated by the solution by gradient descent on a linear model. (2) Under the standard initialization, the solution for the linear model can be approximated by that of a smaller linear model (corresponding to training the last layer).  (3) The implicit bias for this problem is linked to an alternate optimization problem. (4) The solution to this problem is given by solution to the the variational problem as network width goes to infinity.  

######################################################################

2. Strengths

2.1. The results are presented rigorously and the authors consider a number of generalizations involving (1) alternate distributions for weights/biases (2) univariate and multivariate regression (3) alternate nonlinearities. In particular, an extended discussion of generalizations is provided in Appendix O (some of the discussion points in O.3 - O.5 would be nice to include in a conclusion).

2.2. The empirical evidence presented in the main text and Appendix was very useful in providing an intuitive explanation around Theorem 1.  I also particularly liked that the authors provided an interpretation paragraph on page 2, which among other points addressed the reason for involving a linear adjustment to the training data.

2.3. The authors position their results well relative to a large number of related works.  Appendix C clarified a lot of the points regarding related work in the main text especially regarding comparisons between the results of this work and those of Savarese et al. 2019.  

######################################################################


3. Minor Limitations

3.1. While I found this to be an interesting and rigorous work, I feel it would be helpful if the authors could provide a bit more intuition around the technical results for the generalizations.  In particular, I found the interpretation and visualizations presented in the work very helpful for understanding the implicit bias described by Theorem 1. However, it would be helpful if the authors could provide a similar intuition for the multi-variate regression setting.

3.2. I found this work a bit difficult to read through due to the several jumps between equation references.  I think one thing that would help improve the readability is adjusting the Appendix such that related equations in the main text are above the related sections in the Appendix.  One example of this is the need to jump back and forth between equations 15, 16, 17 of the main text in Appendix D. 

3.3. I feel the authors could present some of the assumptions more clearly in the main text.  As a quick example, I believe the authors assume in equation (9) that grad_(theta) f(X, theta_0) has rank M (as is done in Appendix E), but unless I'm mistaken, this is not clearly stated in the main text, and it would be nice to understand how this rank requirement relates to the width n of the network (or whether this is not an obvious relationship).    

3.4. (Very Minor) I think this work could benefit from a discussion of how the implicit bias identified in this work could connect with generalization.  For example, is there any way to understand which curvature penalties would yield solutions that generalize better? 

######################################################################

4. Score and Rationale

I would vote for accepting this paper.  I found the result to be insightful in characterizing the inductive bias of 1 hidden layer fully connected networks used for regression.  The author's present a rigorous analysis, which they complement with a number of empirical and theoretical examples. 


######################################################################

5. Minor Comments

5.1. (Very minor style recommendation) The current introduction is a nice summary of related work, but I think the paper would be a bit more readable if the main results and discussion were placed in front of these related works and these works were merged with the other related works section. 

5.2. (Minor typo) The last sentence of Appendix C.2 appears to be incomplete.  


review_title: Detailed analysis of implicit bias in wide neural networks 

final_score: rating: 7: Good paper, accept
review_content: This paper presents a function space view of 2-layer ReLU neural networks and the implicit regularization associated with full-batch gradient descent for various initializations of the weights. In past work, it was shown that for very wide neural networks, the *global* minimizer of a loss plus weight decay regularizer corresponds amounts to regularizing the total variation of the second derivative of a function (and related results in higher dimensions). This paper explores the effective regularization associated with performing gradient descent on an *unregularized* squared error loss. The resulting regularizer is akin to a weighted 2-norm of the second derivative, where the weighting function depends on the distribution of the initial weights. This result addresses an important open problem, provides interesting insights into the role of initialization and implicit bias associated with training, and is supported by nice illustrations.  

The literature review is strong and covers much of the relevant literature. 

Much of the analysis seems to depend on the optimization occurring in the "kernel regime". It is unclear when this is or is not a reasonable model. This issue is particularly salient in light of the comparison of the results with the work of Savarese et al. Savarese considers explicit 2-norm weight decay regularization. Although the paper under review considers unregularized losses, there are multiple studies showing that gradient descent initialized near zero induces 2-norm regularization. So a natural thought is that the Savarese result would also extend (with some non-trivial technical work) to unregularized settings with gradient descent. With this in mind, I expected to see the Savarese norm as a special case of the results of the paper under review, but this is not the case. In particular, the function space regularization calculated in Savarese is NOT an RKHS norm, while the paper under review claims the function space regularization they find IS a kernel norm. I would like to see a more detailed discussion of this potential discrepancy. Section C.4 does not make this clear.

review_title: Intuitive but interesting insights into initialization and implicit regularization

final_score: rating: 6: Marginally above acceptance threshold
review_content: Update after the rebuttal: I would like to thank the authors for the detailed reply and for addressing raised issues in the submission. I appreciate the authors' rationale, but the "standard" structure of papers makes it is easier to follow. The same for a conclusion, for the authors it may be reiterating the same ideas, but personally I found conclusions the best place where one can quickly get a flavour what has been done in the paper to assess whether it is actually worth spending time reading it in details. Also, they are helpful in cases like this when a reader (me) is outside of the research field of the paper. Regarding discussions, I appreciate that there is discussion for Theorem 1, but there are theorems and propositions stated in the formal language only which would benefit by being repeated in plain English. If they are just technical results required for the main proof, they may be moved to appendix then.
Overall, I am increasing my score to reflect positive changes in the submission. 

There is a minor mistakes:
- In the first line of Conclusion: "obtained aN explicit"


=========================================================================================================


The paper considers the implicit bias (i.e. why neural networks generalise well) in gradient descent learning of wide neural networks for the regression problem. The theoretical results are first stated for wide ReLU network for a 1D regression problem. They are then generalised for multivariate regression and different activation functions. 

It is difficult for me to assess the main content of the paper, as it is outside of my comfort zone. Therefore, this review would be mostly a feedback on overall structure and clarity of the paper. 

Strong points:
* apparent solid and large theoretical analysis
* addressing the important problem of understanding why the neural networks and gradient descent lead to such successful results in various domains 

Weak points:
* the paper is not friendly for outsiders of the particular research avenue. It is packed with content without too much space to discussion of presented results to the point that the conclusion section is missing in the paper
* the structure of the paper is very odd which leads to future references that appear only 3 pages afterwards (see details below)

As mentioned I can't assess the main content of the paper, but with my educational guess I would recommend to reject the paper in the current version. Careful revision is required to make it a complete piece of work (add conclusion and discussion) and make it more accessible for wider machine learning audience.

In particular, for the above mentioned weak points:
* I appreciate space constrains, but probably some of the material can be moved to supplementary completely to allow discussions of the main results more. The theoretical findings are mostly presented in the formal language and there is a lack of plain English discussion on what this means and how it affect the bigger picture. And the paper has to have conclusion section and shouldn't end abruptedly
* It seems that Section 2 and 3 should be swapped as I cannot see the reason why notations and problem formulation are presented after the main results: for those who are inside the field and can understand Section 2 without introduction would not need then introduction in Section 3 at all. And those who do need Section 3 would not understand Section 2 without it. 
This also leads to these inconvenient future references. E.g., referring in Theorem (1) to eq.(5) that appears 3 pages after that is a questionable choice.

Some other suggestions/concerns:
1.	ReLU is introduced in the last paragraph in Introduction, but used in the previous paragraph
2.	NTK is defined well after it is used for the first time
3.	The last sentence in Section 2 – there was nothing before about different training trajectories
4.	Notation clash: in section 2 sigma denotes an activation function (different from ReLU) and in section 3 sigma denotes a parameter of initialisation distribution: Gaussian and uniform
5.	After eq. (7): “We will use subscript i to index neurons and subscript t to index time”, i is also used for training points.
6.	Strictly speaking n in equation between eq. (9) and (10) is not well-defined
7.	ASI is not defined
review_title: Too packed with Maths and abrupt 

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Summary**:
In this article, the authors characterized the implicit bias of gradient descent-based learning in the setting of wide single-hidden-layer neural networks with ReLU activation. More precisely, it was shown in Theorem 1 that the trained network output is "close" to that of the zero-training-error solution that is the "closest" to initialization when the number of neurons $n$ is large. In particular, such a "closest" solution is defined via the so-called *curvature penalty function* $1/\zeta$ that depends on the random initialization of the parameters. Theses results were shown in Theorem 1 to hold for *scalar* input with ReLU activation, and then generalized to *multi-dimensional* input with ReLU nonlinearity in Theorem 2 and to general homogeneous activation function in Corollary 3.

**Strong points**:
This paper provides a precise characterization of the implicit bias of (full-batch) gradient descent method in training single-hidden-layer NN, by studying the resulting solution in the setting of large network width. The major contribution of this work, I believe, is to provide *explicit* characterization of the impact of the distribution of the random initialization on the resulting solution, which is then connected to cubic spline interpolation.

**Weak points**:
My first concern is that the proposed analysis seems somewhat incremental (compared to previous efforts discussed in P4) and fails to provide sufficiently novel insights on the implicit bias of gradient descent: it is good to have the explicit form as in (1) that depends on the random initialization and the second derivative, and I believe it worth more than a single paragraph of discussion and a single figure to illustrate its practical implications, e.g., how does the number of training sample $M$ come into play? Can similar behaviors be empirically observed beyond the single-hidden-layer model, even without proof? how should we choose the initialization scheme in different problems?

My second concern is the organization of the paper: I do not understand why the authors have chosen to present the long and complex theorems in Section 2 before introducing the models and notations in Section 3, this makes the paper, at least for me, much harder to read and follow. Also, I do not understand why the authors have chosen to present the model and notations in Sec 3.1 and 3.2 in the general context of $L$-hidden-layer neural networks: none of the technical results are concerned with this "deep" case and I personally find this only creates unnecessary confusion.

**Recommendation**:
I find this paper borderline, and according to the weak points mentioned above, I'm more leaning toward a reject.

**Detailed comments**:
* abstract: "of the second derivative": the second derivative of what with respect to what?
* Theorem 1: "for which $f(x, \theta^*)$ attains zero training error": $f(\cdot)$ is not yet defined, and it would also be helpful to recall the definition of $C^2(S)$ in (1).
* Below (9): it would be helpful to clarify the conditions under which Lee et al. (2019, Theorem H.1) hold and if they are compatible with the assumptions for instance in Theorem 1 of the present article.
* Above (10): "gradient descent training of a wide network or of the linearized model giveS similar trajectories and solutions in function space": the argument on the "trajectory" is not reflected in the last equation in P5, which only characterizes the network output.
* Above (10): "converge to the unique global minimum": how is the uniqueness ensured here?
* Above (11) footnote 1: is this a claim? If yes, it would be helpful to point out in which Section of the appendix is this proved.
* After (11): not sure to understand why the change in $b^{(2)}$ is also negligible compared to that of $W^{(2)}$.
* Theorem 4: it would be helpful to clarify whether $\lambda_\max(\hat \Theta_n)$ is of order $O(1)$ with respect to $n$, that is, does $\eta < \frac{2}{n \lambda_\max(\hat \Theta_n)}$ mean the the step size should scale like $O(n^{-1})$ in the $n \to \infty$ limit?
review_title: Somewhat incremental contribution? And the paper organization can be clearly improved.

Meta-review: This paper analyzes the implicit bias of gradient descent of infinite width 2-layer neural networks with ReLU activation. It is shown that the dynamics of gradient descent to optimize the 2-layer NN converges to the optimization dynamics on the random feature model in the infinite width limit. Then, it is shown that the gradient descent converges the minimal L2 norm solution from the initial parameters which yields regularization on a weighted integration of second order differentiation. Although this type of analysis has been given in the existing work, this paper gives its explicit form in 1-dimension input setting.

This paper reveals an interesting fact about the implicit regularization that would be educationally valuable. On the other hand, I should mention that there is room for improvement in its theoretical contribution and moreover its novelty is rather limited.
1. Although the explicit formulation of the implicit regularization is informative, the minimum norm bias itself is already pointed out by existing work and this work follows the line. Especially, regularization on the second order derivative has been already pointed out by previous work (although they are 1-norm regularization).
2. The logical jump from the original data to the adjusted data is still not convincing. It is explained that some numerical experiments show the linear term is negligibly small, which means the problems (15) and (17) are very close. However, this excuse does not make sense for this kind of "theoretical" work. The logic used here should be clarified to make the theoretical framework complete.

The evaluations by the reviewers indicate that this paper is on the borderline, and I also feel that some more additional strong point would be required so that this paper is accepted. I encourage the authors to go in this direction and make the analysis more detailed so that the theoretical framework would get more completed.

Minor comment:
Theorem 4 overlaps the result given by the following paper [R1]. It is recommended that the relation and novelty compared with that paper is discussed.

[R1] E, W., Ma, C. & Wu, L. A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics. Sci. China Math. 63, 1235–1258 (2020).
Decision: Reject