Learning a Neuron by a Shallow ReLU Network: Dynamics and Implicit Bias for Correlated Inputs

Summary

The authors analyze the dynamics and implicit bias of gradient flow with the square loss when learning a single ReLU neuron using a one-hidden-layer ReLU network. They assume that the training data are correlated with the teacher neuron (the angles are smaller than $\pi/4$), and that gradient flow starts from a small and balanced initialization. They give a non-asymptotic convergence analysis. In the limit where the initialization scale tends to zero, the resulting network has rank $1$. Namely, all non-zero neurons point in the direction of the teacher neuron. On the other hand, the resulting network might not have minimal Euclidean norm. Thus, there is an implicit bias for rank minimization but not for norm minimization.

Strengths

Understanding convergence and implicit bias in overparameterized networks is an important question, that has attracted much interest in recent years. The paper gives a detailed analysis of the trajectory and implicit bias. The analysis is under strong assumptions (single-neuron teacher, correlated training data, small and balanced initialization, etc.), but these assumptions are present also in existing results, and the analysis of gradient flow is challenging even under such assumptions. Finally, the paper is well-written.

Weaknesses

In Assumption 1: - Item (iv): why is it a measure-zero event? - Items (iv) and (v): I think that the assumptions should specify properties of the training data and the training algorithm. Then, the properties of the trajectory should be shown using these assumptions. Can you specify items (iv) and (v) as assumptions on the data+algorithm? Other than that, I don’t have major concerns. An obvious limitation is the strong assumptions, and specifically the assumption on the correlated training data, but as I already mentioned, I think that it is reasonable here.

Questions

See the “weaknesses” section.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors discussed the limitations.

Summary

The paper studies the problem of learning a single ReLU using a 2-layer ReLU network using gradient flow on both layers. The main assumption is that the data is correlated with the target neuron, while other milder assumptions are also used (e.g. specific initialization and spectral assumption on the data matrix). The main result is a two-phase convergence to a global minimum. Several experiments are also given.

Strengths

- The main convergence result is novel AFAIK, and shows an interesting convergence dynamic, where in the first phase the learned weights either align with the target neuron or deactivate, and in the second phase converge to a global minimum. - The connection between the global minima of the problem and the minimal norm solution in Section 7 is interesting and brings forward the question of whether minimizing the empirical loss results in a minimal norm solution, which was studied in previous works too (e.g. Vardi et al 2022). - The experimental part shows empirically the behavior of the angles between the learned weights and the target neuron.

Weaknesses

- The assumption that the data is correlated with the target neuron is pretty strong. The motivation for taking an angle of at most \pi/4 between each data point and the target neuron is also not clear. What changes if the angle is larger\smaller? I think the authors should elaborate more on this assumptions, and what breaks if it is not assumed. To compare, other papers about studying a single neuron usually consider a data distribution spread in all directions (e.g. Frei et al. 2020, Yehudai & Shamir 2020). - The presentation of the main result is not clear. I think there should be a single Theorem stating the convergence result, with an explicit convergence rate. Currently, there is no single result just a lemma for each phase, and it is difficult to parse the main out-take of the paper. In such a paper, I think the convergence rate of the entire procedure is crucial to fully understand the quality of the result. - The paper is very technical, and in my opinion, doesn’t provide enough intuition to understand the quantities that are used. For example, the definition of \delta in line 238. Can’t \delta be zero or at least exponentially small (if the angle between two data points is very close to \pi/2). - The result in Section 7 is interesting but not quite clear. What does the quantity M represents? What can we say about the dataset itself so that either option (i) or (ii) of Theorem 8 is applied? - I think that claiming that the implicit bias for the problem studied here is to minimize the norm is a bit misleading. As I understand it, all the learned weights either align with the target neuron or deactivate, this means that the solution converges to a specific form of rank-1 matrix (where each row is either v^* or 0).

Questions

- What changes if we assume that the angle between the data samples and the target neurons is \alpha, where \alpha > \pi/4? - What is the total convergence rate of gradient flow for learning a single neuron? - Is it possible to extend the result to gradient flow? or possibly SGD? - Is there an explicit condition on the dataset that can be given so that the set of interpolators also minimizes the norm of the predictor

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors do address adequately to the limitations of the paper, although I think it is important to elaborate more on the main assumption about the dataset.

Summary

This paper studies how a two-layer ReLU network can fit a single neuron. The authors consider the case where all training points are correlated with the teacher neuron and show that gradient flow from small initialization can converge to a zero-loss solution. They divide the training into two stages. In the first stage, the neurons are small and will align with the teacher neuron or deactivate, depending on the sign of the output weight, and in the second stage, the aligned neurons will grow and fit the target function. In addition, they show that as the initialization scale goes to $0$, gradient flow converges to a rank-$1$ solution.

Strengths

* Overall, the presentation is clear, and the main text is relatively easy to follow (see the weakness part of the review for some minor issues.) * The use of the yardsticks $\omega_j$ is interesting. * The geometric argument for the second phase seems novel and may be of independent interest. * Theorem 8, which shows the set of balanced rank-1 interpolating networks and the set of minimum-norm interpolating networks can be the same or disjoint, depending on a certain quantity, is surprising.

Weaknesses

* The presentation is overall clear, but the notations are cumbersome. * For example, I don't think using $w$ and $\omega$ simultaneously is a good idea, especially when they co-occur a lot and represent two closely related objects. * The detailed definitions of $\delta$ and $S_l$ can be moved into the appendix, and define them informally in the main text and maybe briefly explain how small can $\delta$ be and the intuition behind $S_l$. * I personally don't like the $\exp(-n)$ initialization scale, though I will accept it as it has been used in previous works. I think it is somewhat cheating because, with it, you can make sure the norm of the neurons is sufficiently small so that you can ignore them for any polynomially long time. * The setting is quite restricted and unrealistic as it requires the angle of all inputs and the teacher vector to be smaller than $\pi / 4$.

Questions

* Is it possible to adapt your strategy to the Gaussian inputs case? This seems to be a more natural generalization to the orthogonal input setting. * Could you intuitively explain the meaning of the conditions in the definition of $S_l$?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This is a theoretical work and I cannot see any potential negative societal impacts.

Summary

Convergence and implicit bias of non-linear networks is an important open question in deep learning theory. The paper studies these questions in the case of regression with ReLU networks with a single teacher neuron. It proves that at a vanishing initialization scale the student neurons align with the teacher (or gets deactivated). It also shows an interesting counter example such that the implicit bias as initialization tends to zero need not be a minimum norm interpolator.

Strengths

a) Going beyond the orthogonal data, the paper proposes an interesting setting which helps analyse the case of correlated inputs. b) The geometric technique to study the convergence after the alignment phase is novel. c) The scenario proposed where the implicit bias as $\lambda \to 0$ is a rank minimizing one instead of a minimum norm interpolator is a very interesting contribution.

Weaknesses

a) The setting is simplified: there is only a single teacher neuron and all the labels are only positive. It directly that neurons (at least yardstick neurons) with negative last layer decreases in norm. The assumption that the inputs are correlated further ensures that they are deactivated. This makes the analysis easier. b) The technical analysis follows the same strategy as Boursier et. al. Some aspects are easier as there is only one saddle to escape.

Questions

a) It is mentioned in the contributions there exists a case where that the minimum norm interpolator is rank 2 instead of rank 1. Can the authors comment how the non-linearity plays a role here? Can the authors a simple example providing a more detailed illustration?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

a) The experiments are conducted with synthetic data and only in the case of single teacher neuron. It would interesting some empirical evidence in the case of more than one teacher if the phenomenon characterized in the paper holds in more generality.