Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper inscribes in the direction of providing quantitative understanding on the dynamics and implicit bias of gradient-based optimisation. The authors focus on regression problems in architectures with one-hidden-layer of finite width, ReLU activations and mean-squared error loss. The inputs are fixed and assumed to be pairwise orthogonal. The results are non-asymptotic, holding for any input dimension and training set size.
The contribution is threefold. First, they show global convergence of gradient flow to zero training loss if initialised at sufficiently small norm.  Second, they show an implicit bias of gradient flow towards minimum $\ell_2-$norm interpolator again when starting from sufficiently small initialisation norm. Third, they characterise four different training phases traversed by the dynamics: (i) initial alignment of the neurons along one of two key directions while keeping a small norm, (ii) positively-aligned neurons grow in norm until fitting the positive labels, while the other do not move, (iii) the same for negatively aligned neurons until fitting negative labels, (iv) final convergence. The orthogonality assumption on the inputs is crucial to allow this separation between alignment and norm-growth phases. The authors also show that a saddle-to-saddle dynamics takes place, starting close to the saddle point at the origin and getting trapped for a long time close to a saddle point between phases (ii) and (iii). 
The theoretical results are confirmed on a toy dataset of 2 unidimensional data points with a bias.


strengths_and_weaknesses: Overall I find that the paper is well written. The motivations behind the analysis are relevant and clearly stated in the introduction.
To the best of my knowledge, the analysis of the implicit bias of gradient descent on finite-width one-hidden-layer ReLU networks is novel. Interestingly, the analysis is non asymptotic in the input dimension, dataset size and time.

The assumption of a fixed dataset seems to me a significant limitation towards understanding the generalisation properties in relation to the statistics of the data. It would be interesting if the authors could discuss more about the difficulty of averaging over some given data distribution. The pairwise orthogonality assumption on the inputs is also a significant limitation in terms of the learning ability of the network, given that the number of samples is limited to the input dimensionality.

I also find that the experimental validation of the results is a bit poor and it would be interesting to see the paper findings confirmed on higher dimensional datasets. In particular, it would be interesting to test whether the observed training phenomena still hold true on non-orthogonal but more realistic datasets.

Finally, the manuscript is not completely clear to me in a couple of points:

- The paragraph “Feature learning and small initialisation” (lines 38-45) seems to suggest that the large initialisation case is not interesting since it leads to the lazy training regime. However, it is not clear and should be clarified whether the analysis presented in this paper has been already derived for the precise setting under consideration at large initialisation norm.
- At line 110, the authors write that their gradient flow description holds for the infinitesimal step-size limit of "(stochastic) gradient descent" implying that as the step size vanishes there is no distinction between SGD and GD. If the authors want to keep this comment they should justify it providing a reference or an explanation in support of this claim.


questions: I would be interested if the authors could discuss the following points:

a - What are the main limitations of extending the present analysis to the finite-step-size case and multi-pass stochastic gradient descent?

b - What are the main limitations of extending the present analysis to generic losses other than the square one?

In [1], the authors discuss the necessity of an initial alignment with the target function for gradient descent to converge to a solution. Could you comment on how to reconcile the findings in [1] with the result of this paper that GD dynamics can align with the relevant directions? It seems to me that the main discrepancy is again related to the pairwise orthogonality assumption that limits the training set size, which prevents to reconcile the present setting with the dynamics of population loss. Could the authors comment more on this point?


Reference:

[1] Emmanuel Abbe, Elisabetta Cornacchia, Jan Hazla, Christopher Marquis Proceedings of the 39th International Conference on Machine Learning, PMLR 162:33-52, 2022.
limitations: The main limitations of the work regard the restrictiveness of the assumptions to pairwise orthogonal data and fixed dataset, which prevents from obtaining an understanding of the generalisation properties of the GD algorithm.
The main weakness in my opinion is the experimental setup, which could be improved in the ways I have described above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies gradient flow dynamics for two-layer ReLU network with square loss and orthogonal inputs. In particular, authors showed that using small initialization gradient flow will converge to the minimum variation norm interpolator. The theoretical analysis consists of complete training dynamics analysis and highlights an interesting saddle to saddle dynamic. Experiment results are also provided to support the theoretical results.
strengths_and_weaknesses: Originality
1. This work considered the regression setting with small initialization and orthogonal inputs and showed that gradient flow is biased towards minimum variation norm. This result is different from previous implicit bias results and gives understanding of implicit regularization under new settings.

Quality
1. The quality of this paper is overall good. The results and limitations are clearly discussed. Proof sketch of the main result is provided. Proofs of the theoretical results are included in the appendix.

Clarity
1. The paper is overall well-written and easy-to-follow.

Significance
1. Understanding implicit regularization of gradient flow/gradient descent is an important and active research problem towards understanding overparametrized neural networks.
2. Analyzing the whole training dynamics and showing its convergence to a minimum norm interpolator is not an easy work, even in such simplified setting. It is great for authors to prove such a result.
3. The condition on width of neural networks seems need to be exponential in number of training samples to satisfy Assumption 3, when using the gaussian random initialization. It would be better if authors could make it clear when discussing Assumption 3.
4. The condition on the scale of the initialization also seems need to be exponentially small. I would not view this as a major limitation, since using an exponentially small initialization is common in the implicit bias literature.

questions: I would appreciate if the following questions could be answered:

1. I was wondering if the Assumption 3 can be weakened in some settings so that the required width of neural network can only be polynomial in relevant parameters.

2. I was wondering the exact requirement on \lambda^*, which I did not find in Lemma 12 (line 149)

limitations: The limitations of the work are clearly discussed. This is a theoretical work thus I don’t see any potential negative social impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides a detailed and quantitative characterization of the gradient flow dynamics of a one-hidden-layer ReLU network on orthogonal data. The results require some additional assumptions: square loss function, regression task, balanced and small initialization, and the width is large enough. Under these assumptions, the authors showed that the gradient flow process can be divided into 4 phases and characterized each phase precisely. The implications of the characterizations of this training process include: training loss will converge to zero, the weights will converge towards some minimum $\ell_2$-norm solution, and the training trajectory will encounter a non-zero strict saddle point. The authors also did experiments to validate their theoretical results.
strengths_and_weaknesses: Strengths:

- This paper studies an important problem in this field, i.e., the training dynamics of neural networks. This work characterized the training dynamics in detail in a simplified setting (gradient flow of regression task with one-hidden-layer wide ReLU network, orthogonal input, square loss, and small and balanced initialization), and this dynamics has several indications which align with previous works' conjectures or empirical observations, including global convergence, implicit bias towards minimum $\ell_2$-norm solution, and saddle to saddle dynamics.

- This paper is well-written and well-structured, making it easy to read. The notations are well-defined, and the intuitions behind the lemmas and the implications of the theoretical results are discussed in detail. Besides, the authors provided figures (especially Figure 1) to illustrate the training process, which could help with the readers' understanding of the theoretical results.

- The authors did experiments on synthetic orthogonal data to validate their theoretical results. They also did experiments for non-orthogonal cases, which provided intuitions about the similarities and differences between orthogonal and non-orthogonal settings.

- The theoretical proofs in this paper appear to be correct, and the related works are adequately cited. Besides, the experimental settings are provided in detail, making them easily reproducible.

Weaknesses:

- The input orthogonality requirement might be a bit strong, and it limits the number of training data to be no more than the input dimension. Although the authors did some experiments on non-orthogonal inputs, the training dynamics of neural networks still seem a bit unclear and hard to characterize. It might be better if the authors could provide more intuitions/observations in more general cases.

- The requirements for $\lambda^*$ and the width of the network are not explicitly stated and discussed in the main text, which might make it hard to understand the results quantitatively. It could be better if the authors could move the upper bound of $\lambda^*$ to the main text, and discuss more about the network width requirement. For instance, if the weights are initialized i.i.d. from the unit sphere, we might need exponentially (in the number of training data) many neurons to ensure that Assumption 3 is true with high probability.

Typos:

- In Figure 1, the end of Early Alignment phase should be $-\frac{\epsilon\ln(\lambda)}{||D_-||}$ instead of $-\frac{\epsilon\ln(\lambda)}{||D_+||}$ according to Lemma 2.
questions: - As mentioned in the "weaknesses" section above, it might be better if the authors could give more theoretical intuitions or empirical observations/evidence about neural network training dynamics in more general settings. It could also be better if the authors could provide quantitative requirements and more discussions about the initialization and width of the network.

- Are there more implications for neural network training in practical settings that could be provided by the results in this paper? It would be very interesting if these results could provide guidance on training neural networks in real-world applications, and currently this connection seems a little weak.
limitations: This paper is mostly theoretical and focuses on very fundamental problems in neural network optimization, and I do not see any immediate negative societal impact of this work. The authors also adequately addressed the limitations of this paper in Section 3.2.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies gradient flow dynamics of shallow ReLU networks for regression with square loss. Authors consider a setting of orthogonal inputs in the regime of vanishingly small initialization. In this setting, they provide a characterization of stages of gradient flow on square loss (see Fig. 1), which allows them to draw a few qualitative results about training dynamics: convergence to nearly min-norm interpolator, justification of initial alignment phenomenon and “saddle-to-saddle” behavior of dynamics. Notably, the analysis does not exploit overparameterization and a main technical assumption (A3) (except the data orthogonality) on existence of neurons for which input and last layer weight agree on sign with the label is a mild one (or at least weaker than the one considered previously in related to zero-loss convergence papers).
strengths_and_weaknesses: Strengths:
- Precise characterization of training dynamics under “non-lazy” regime: more specifically, timeline of dynamics ( covered by Lemmas 2-5 )
- Analysis does not require over-parameterization
- A theoretically justified “saddle-to-saddle” behavior conjectured in few related works
- A few interesting supplementary results, e.g., that only for a particular choice of subgradient the dynamics are well-defined.

Weaknesses:
- Orthogonality assumption on data (which ultimately allows for such precise characterization of dynamics). This is the main weak point of the paper, as it is hard to understand where current technique will be of any insight in general (although, authors do a fair job of elaborating on it in the corresponding section)
- A few results in the related literature worth discussing are missing

questions: I suggest that authors add a few missing relevant references accompanied by discussion:
- “A type of generalization error induced by initialization in deep neural networks” by Yaoyu Zhang et al., 2020 - shows convergence to the closest to init interpolator for lazy training regime (which in some cases might result in selecting the min-norm one)
- There are a few references on generalization capabilities of “min-norm” interpolators (although mostly for linear models), e.g. “Tight bounds for minimum l1-norm interpolation of noisy data” by Guillaume Wang et al., 2022, which would be helpful to add for completeness in corresponding discussion.
- “Gradient dynamics of shallow univariate ReLU networks” by Williams et al., 2019 - shows implicit bias in case of univariate regression depending on the init scale.

Authors should be a bit more explicit about stating that the result holds for a particular sequence (lambda->0) and that at any non-zero lambda dynamics approach but not exactly min-norm, and that the selected min-norm solution might not be unique, and that there is no description (as far as I understood) of a particular min-norm solution selected (e.g. if it is the closest to init?) . Although some of these points can be inferred from statements alone, I would suggest enhancing them for a broader audience.

limitations: Authors thoroughly discuss the limitations of the proposed approach.
review_title: null

Meta-review: metareview: This paper studies the gradient flow dynamics for a one-hidden layer ReLU network with square loss and orthogonal inputs. In particular, the authors show that gradient flow converges towards a global minimum for sufficiently small initialization and that the solution consists in the minimum $\ell_2$ norm interpolator. Interesting insights are provided on the various phases of the dynamics, which is characterized by an initial alignment, followed by fitting the positive labels, then the negative ones and a final convergence. A saddle to saddle dynamics (conjectured in earlier work) is also unveiled.

The assumption of orthogonal inputs is rather strict, and it is the main weakness of the paper. That being said, the reviewers and this AC agree that the results of this paper are novel and interesting for the NeurIPS community. Hence, I am happy to recommend acceptance. As a final note, I would like to encourage the authors to include in the camera ready the discussions related to the feedback received from the reviewers (in particular, the experiments in higher dimensional settings).

confidence: Certain
Decision: Accept