Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper analyzes the implicit bias of gradient flow/descent on a two-layer leaky-ReLU network. Specifically, assuming the data points are nearly orthogonal, Theorem 3.2 gives an accurate characterization of the KKT point of the margin maximization problem: all data points are support vectors, the first layer is of rank 2, and a closed-form solution is given. In Theorem 3.4, it is further shown that gradient flow converges to this solution. Section 4 focuses on gradient descent, and shows that with nearly orthogonal data and smoothed leaky-ReLU activation, the stable rank of the network is bounded by a universal constant. Empirical supports are also provided.
strength_and_weaknesses: This paper provides interesting and accurate characterizations of the implicit bias of gradient flow/descent with nearly-orthogonal data and leaky-ReLU activation. Specifically, although the network can be highly over-parameterized, this paper shows that the classical or stable rank stays small. One weakness is that the near orthogonality condition is a little restrictive, as it implies linear separability. Lemma 3.3 shows that it holds with Gaussian inputs, but it requires $d\ge n^2$, which does not hold in practice. Can you discuss how this assumption is used in your proof, and why linear separability is not enough?
clarity,_quality,_novelty_and_reproducibility: The paper is well-written.
summary_of_the_review: This paper gives interesting results on the implicit bias of gradient descent with nearly-orthogonal data and leaky-ReLU activation. I recommend for acceptance.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper is concerned with the implicit bias of gradient flow and gradient descent in two-layer fully connected neural networks with leaky ReLU activations when the training data are nearly-orthogonal. For gradient flow, this paper leverages the implicit bias for homogeneous neural networks to show that gradient flow produces a neural network with rank at most two. For gradient descent, this paper shows that a single step of gradient descent suffices to sufficiently reduce the rank of the network and the rank remains small throughout training. Finally, several experiments are provided to verify the effectiveness of the proposed method.

strength_and_weaknesses: Strengths: the paper characterizes the implicit bias of common gradient-based optimization algorithms for two-layer leaky ReLU networks trained on high-dimensional datasets. It presents that small initialization variance is important for gradient descent’s ability to quickly produce low-rank networks.
Weaknesses: The clear and precise definition of "high-dimensional data" is missing. What exactly are "high-dimensional data"? I understand random data in high-dimensions are almost always nearly orthogonal to each other. Please be more careful when stating the 'near-orthogonality' of data dealt with in the paper. Can we quantify the required "near-orthogonality" of data? Furthermore, the idea, analysis, and technical tools used in this paper are mainly adapted from the literature, in e.g., Lyu & Li (2019), Ji & Telgarsky (2020), Lyu et al. (2021). Third, I am not sure whether this so-called "implict bias" pertains to the network itself intrinsically, since if some of the assumptions on the data/gradient flow algorithms would make the "implict bias" not hold. Some existing works on two-layer ReLU or leaky ReLU learning are missing and closely related. See e.g., the landscaple and local/global optimality of (Leaky) ReLU networks in Laurent, et al, The multilinear structure of ReLU networks, in ICML, 2018; Laurent, et al, Deep linear networks with arbitrary loss: All local minima are global, in ICML, 2018; as well as the global optimality of SGD on training ReLU networks and the rank-2 solutions of regularized relu training in e.g., Wang, et al. Learning relu networks on linearly separable data: Algorithm, optimality, and generalization. IEEE TSP, 2019, and Yang, et al. Learning two-layer relu networks is nearly as easy as learning linear classifiers on separable data. IEEE TSP, 2021.  Ergen & Pilanci, (2020, June). Convex geometry of two-layer relu networks: Implicit autoencoding and interpretable models. In International Conference on Artificial Intelligence and Statistics. PMLR. Last, can the results generalzie to three-layer or deep ReLU networks of practical interest? Or please at least discuss its implications for training deep relu networks.

Comments:
i) This paper investigates the implicit bias of gradient flow and gradient descent in two-layer fully-connected neural networks with leaky ReLU activations when the training data are nearly-orthogonal. However, the paper still focuses on two-layer neural networks and also only the leaky ReLU activations. More comparison of the work in context shall be included, as well as its practical hints for ReLU networks and deeper networks.
ii) On Page 1, "We consider fully-connected two-layer networks with m neurons where the first layer weights are trained and the second layer weights are fixed at their random initialization." Although fixing the second-layer weights does seem to harm the representation of the 2-layer network, which is indeed used in most existing works, this (considerably) makes the learning problem much easier. Nonconvex optimization often comes from the symmetry or rotation, if one fixes the second-layer and breaks the symmetry/or elliminates the scaling issue. It would be much more meaningful to study the landscape and learning behaviour of the two-layer networks.
iii) Could you please list the pros and cons of your offline method compared with the online method in Lyu & Li (2019) and Ji & Telgarsky (2020)? In addition, could you explain how does different choices affect the result?
iv) In the experiments, this paper verifies the theoretical results in two-layer ReLU networks with bias terms trained by SGD only on CIFAR-10. More datasets and tests shall be conducted for validation.
v) There are some mistakes in grammar and sentences, such as "...and consider training that starts from a..." and "...when the labels y are some nonlinear function of t..." These indistinct expressions abate the readability of this paper.



clarity,_quality,_novelty_and_reproducibility: The paper is clear, but the presentation can be improved. The quality of this paper looks fine, but some unclear "asumptions" on the data along with the treat of ReLU networks only undermine the contributions of the paper. Plus, lack of discussions of related works further makes it difficult to judge the novelty of the results. 


summary_of_the_review: This paper is concerned with the implicit bias of gradient flow and gradient descent in two-layer fully connected neural networks with leaky ReLU activations when the training data are nearly-orthogonal. I believe the paper shalle be improved in providing a detailed comparison of related works on assumptions on the data, activation functions, global/local optimality, and other interesting findings. Overall, the contribution of the present paper is below the bar for ICLR.
------------------------------------------------------
I have looked at the the authors' replies as well as the comments of other reviewers. I agree that the paper contributes new ideas and technical proofs for understanding training of leaky ReLU networks. I have updated my score. It would be good to see all the corrections in the revision.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors studied the implicit bias of gradient flow and gradient descent for two-layer leaky-ReLU networks with nearly orthogonal data. It is shown that gradient flow will asymptotically converge to a network with rank at most 2 and linear decision boundary. Such a network is also approximately a max-margin linear predictor. For gradient descent, it is shown that with small enough initialization, a single step could reduce the rank of weight matrix to constant and the rank of weight matrix will remain constant throughout training. Experiments are also provided to support the theoretical results.
strength_and_weaknesses: Strength:
- The paper is well-written and easy to follow.
- Understand the implicit bias of neural networks is an important problem and current paper provides an answer in the two-layer leaky-ReLU network with nearly orthogonal data setting.
- The results are clearly stated with proof ideas discussed in the main text and full proofs in the appendix.
- I found the section 5 that discusses the implication of the result quite interesting: it not only discusses the benefits of such implicit bias, but also gives examples where such implicit bias is harmful.

Weaknesses:
- As mentioned in the conclusion section by authors, the results heavily rely on leaky ReLU and cannot be applied to ReLU. Such leaky parameter $\gamma$ also has impact on the convergence point, such as point 7 in Theorem 3.2. It is unclear how to generalize the results to other activations and non-nearly-orthogonal data.

clarity,_quality,_novelty_and_reproducibility: Clarity:
- The paper is overall well-written and easy to follow.

Quality:
- The quality of paper is overall good. The results are clearly stated with proof ideas discussed in the main text and full proofs in the appendix.
	

Novelty:
- The results appear to be interesting and novel. 

Reproducibility:
- This is a theoretical work so there are no experiments to be reproduced. The full proof are given in the appendix (I didn’t check them).

summary_of_the_review: In summary, this work studied the implicit bias of two-layer leaky ReLU network with nearly orthogonal data. It shows that the convergence point has a low (stable) rank weight matrix and a linear decision boundary. The results seem to be new and interesting. Therefore, I’m currently leaning towards accept.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: This paper considers learning high dimensional linearly separable data with a one-hidden layer network with Leaky ReLU activations. The high dimensional data assumption entails that the norm of the data points is significantly larger than the pairwise correlation between different points. The assumption holds for random high dimensional data such as a Gaussian distribution. It is shown that a network where the first layer is trained with gradient flow has the following properties: (1) It converges to a zero training error solution (2) The solution has rank at most 2. (3) The solution has a linear decision boundary (4) It converges to a certain max margin solution which is not necessarily the max margin linear separator. Results for gradient descent are also presented where a bound on the stable rank is proved.
strength_and_weaknesses: Strengths:
1. Strong theoretical results in a challenging setup.
2. New theoretical techniques that might be useful in other settings.
3. Very well written.
4. Novel empirical findings.


Weaknesses:

Nothing major. 
Two minor weaknesses:
1. The fact that “high dimensional data” is used throughout can be a bit of an over statement. For example, consider classifying MNIST digits, e.g., 0 digit vs. 1 digit. This problem is high dimensional, while I guess that the assumption in the paper is not satisfied. For example, there can be two data points of a 0 digit that have a large pairwise correlation. Maybe “random high dimensional data” is more accurate.
2. There are only a few experiments. There are many interesting experiments that can be included. For example, the theoretical finding on D_XOR is very interesting because usually networks solve the XOR problem. I guess that this is because of the high noise and low norm of the cluster centers. In any case, it would be interesting to see that the network indeed fails on this data empirically and converges to a linear classifier.



clarity,_quality,_novelty_and_reproducibility: As described above, the work is of high quality, very clear and has novel theoretical results.
summary_of_the_review: Strong and novel theoretical results in a challenging setting and very well written. Highly recommend for acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper gives an accurate characterization of the implicit bias induced by the gradient flow to train two layer leaky-ReLU networks. The gradient flow induces a small stable rank (almost rank 2) at an early stage of the optimization and converges to a solution with an approximate-max-margin. In particular, it is shown that the small scale of initialization is important to have small stable rank implicit bias in the beginning of the optimization.  

This paper gives a precise characterization of the implicit bias of the gradient flow in a high dimensional setting where the inputs are nearly orthogonal. It is also important to show the small stable rank implicit bias. This kind of phenomenon has also been pointed out by the existing literature in different settings, but this research gives another (important) example to the literature. Overall, the writing is good.   
One of the main drawbacks of this paper is that it assumes near orthogonality of the input, which is a bit restrictive. Another weakness is its numerical experiment. The experiment is conducted on a toy synthetic dataset. However, these drawbacks do not hurt the value of this paper.  

In summary, this paper gives a new and interesting theoretical work for the implicit bias of 2 layer neural networks. The theory is solid. The writing is good. Hence, I recommend acceptance in ICLR. 


justification_for_why_not_higher_score: Overall the quality of the paper is high. However, the assumption in the paper is a bit restrictive. If such restrictions were relaxed, this paper would deserve oral presentation. 
justification_for_why_not_lower_score: This paper gives fairly high quality theoretical analysis. The implicit bias of the gradient flow is one of the biggest issues in the literature and it plays an important role to analyze the effectiveness of feature learning. This paper gives a precise and clear characterization on this topic. Hence, I think this paper deserves the spotlight presentation.
Decision: Accept: notable-top-25%