Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper focuses on improving the condition of overparameterization for stochastic gradient descent on overparameterized shallow neural networks. The authors first present a general global convergence result for SGD on a finite-sum compositional optimization problem, and then apply this general result to two-layer neural networks with smooth activation functions to obtain a sufficient condition of overparameterization of order $O(m^2 / \sqrt{b})$, where $m$ is the sample size and $b$ is the mini-batch size. 
main_review: While the results of this paper look correct and rigorous, I have a major concern about the significance and novelty of the paper.

First of all, the $O( m^2 / \sqrt{b} )$ condition on overparameterization in fact requires additional assumptions on the data (or data distribution) that is not covered by Assumptions 1-4 in this paper. This result relies on an estimated order of $\sigma_{\mathrm{min}} (X^{*t}) $ that is derived by assuming X is uniform. This is a very strong data distribution assumption. With this additional assumption, it is not fair to compare the condition $\sigma_{\mathrm{min}} (X^{*t}) $ with the other works in Table 1. For example, in order to compare the result with existing works considering the separable data assumption, the authors should derive additional guarantees of $\sigma_{\mathrm{min}} (X^{*t}) $ based on this separable data assumption, as is done in Oymak & Soltanolkotabi (2020). 

Moreover, the discussion on Ji & Telgarsky (2020), Chen et al. (2021), and Daniely (2020) is too vague and not convincing. It still seems that these works have already proved better conditions of overparameterization than this paper. Since these works also highlight the improvement of overparameterization conditions, the authors should consider adding them to Table 1 and discuss the differences between this work and existing works in detail.

At last, as given in Table 1 in this paper, the result in this paper is only better than Oymak & Soltanolkotabi (2020) in the sense that (i) this paper considers the training of parameters on both layers, while Oymak & Soltanolkotabi (2020) only considers the training of the first layer (however, in literature, it is widely believed that the difficulty of the analysis lies mainly on the training of the first layer parameters); (ii) this paper gives results for different mini-batch sizes. However, this paper also has a disadvantage compared to Oymak & Soltanolkotabi (2020), as this paper requires a smooth activation function, while Oymak & Soltanolkotabi (2020) works for ReLU activation. Therefore, the result of this paper can be quite incremental compared to Oymak & Soltanolkotabi (2020). 


Typos:

1. The sample size is denoted as n in Table 1. However, in the latter part of the paper, the notation of sample size is m.

2. The notation $\nabla h_j(w^i)$ Equation (4) is not consistent with that in the discussion below it $\nabla h_j(\Phi(w^i))$



summary_of_the_review: My major concern about this paper is its significance and novelty. Based on this concern, I would like to recommend rejection.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: This paper first analyzes the convergence of SGD under assumptions of PL condition on loss function and growth condition on stochastic gradients. Then, it considers a two-layer neural network with some special setting, and claims that this network with quadratic loss satisfies both PL condition and growth condition, and hence SGD converges.
main_review: The results presented in this paper are already known in the literature. Please check the two highly related papers: Liu et al (2021), Liu et al (2020).

>Specifically, assuming PL condition on the loss function, convergence of SGD is already obtained in Liu et al (2021), with an exponential learning rate. This covers Theorem 1 of this submission. 

>The concepts of near-isometry (definition 4) and length of trajectory (proposition 1) are also similarly established in Liu et al (2021). Near-isometry corresponds to the so-called uniform conditioning of NTK (neural tangent kernel), and proposition 1 corresponds to the “existence of solution” in a neighborhood ball.

>PL conditions are shown on neural networks in Liu et al (2021). I noticed that Liu et al (2021) includes deep neural networks, as well as shallow ones. But this submission only considers shallow networks, with more assumptions (assumption 3 & 4).

The proof of the growth condition of the shallow network is incorrect. In section 2, the theory assumes growth condition on stochastic gradients, i.e., derivative of loss w.r.t. the model *parameters*. However, when proving a shallow network satisfies growth conditions in the proof of theorem 2, the paper analyzes a different object:  derivative of loss w.r.t. the model *output*.

The notations of the paper are not consistent and ambiguous, which makes it hard to read. For example, in Eq.(13) and the sentence after, matrix Z is discussed, but Z is never defined before.


References:

Liu, et al. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks, 2021.

Liu, et al. On the linearity of large non-linear models: when and why the tangent kernel is constant. NeurIPS, 2020.

================ Edited after author feedback ================

Thanks for the authors for the feedback.

The paper seems properly cited the anonymous paper. So, I removed the dual submission concern flag in the ethic review part.

As for the high similarities with prior works, I never "acknowledged that there are *significant* differences between" the current submission and  prior works, e.g., [Liu et al., 2020]. The concepts and main logic are highly similar to prior works I mentioned above. 

I have read the other reviews and agree that this paper lacks novelty, and that main concepts and methods are already known in prior works. So, I would like to keep my score unchanged.




summary_of_the_review: 1. Known results
2. incorrect proof
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proved that a two-layer neural network with smooth activation and proper initialization can converge linearly to a global minima of training loss using mini-batch SGD when the width is larger than $\Omega(m^2/\sqrt{b})$ where $m$ is the number of training data and $b$ is batch size. As the batch size increases, this provides an interpolation between the quadratic result for SGD and the sub-quadratic result for full-batch GD. To prove this result, the authors first provide a general convergence result for SGD on a particular class of functions and then apply this framework to 2-layer neural networks to derive the width requirement.
main_review: -Strengths:

1. This paper provided a better width requirement bound for linear convergence in two-layer neural network training by generalizing techniques from previous results and taking batch size into consideration. Specifically, compared to (Oymak & Soltanolkotabi, 2020), this paper enables the training for both layers instead of a single layer. Besides, compared to (Anonymous), this paper enables training using mini-batch SGD instead of GD.

2. This paper is generally well-organized and easy to follow. It also provided detailed proof sketches with a few remarks, making the proof easy to understand.

3. The related works appear to be adequately cited and compared in detail.

-Concerns:

1. The novelty of this paper might be somewhat limited, and this is my major concern of this paper. I will explain in detail in the following paragraphs.

1.1 The learning dynamics of neural networks in this paper are still in the lazy regime, and the proof ideas are of similar styles as previous papers in this area. Specifically, as shown in Lemma 1, the authors require that the weights do not move far (i.e., larger than a constant) from the initialization to ensure the local smoothness and bound the eigenvalues of the Jacobian. The bound on minimum eigenvalue of the Jacobian ensures linear convergence, which results in bounded weight change and then induces bounds on eigenvalues of the Jacobian. Therefore, the learning dynamics in this paper still require a lot of things (including weights, Jacobian matrices, etc.) to remain close to initialization, which should be considered as lazy regime. This is different from the neural network training in practice since empirically the weights of neural networks usually move far from initialization.

1.2 The novelty of the techniques used in this paper seems a bit limited. The bounds for local smoothness $\beta_\Phi$, eigenvalues of $\Phi^*(w_0)$, initial function value, and preservation of "near-isometry" during training all come from (Anonymous). Furthermore, the idea of bounding the probability that the weights leave the local neighborhood of the initialization exists in Theorem 3.1 of (Oymak & Soltanolkotabi, 2019) and Theorem 2.6 of (Oymak & Soltanolkotabi, 2020). This paper provided a new way of bounding the expected length of SGD trajectory (Proposition 1), enabled training for the second-layer weights, and generalized SGD to mini-batch SGD by introducing the batch size $b$ (Theorem 2) to interpolate between (Anonymous) and (Oymak & Soltanolkotabi, 2020). The techniques used in these steps seem specific to the particular setting in this paper and might not generalize. Thus, the technical novelty of this paper might be a bit limited.

2. The results in this paper only apply to smooth activation functions with bounded Hermite norm, which is a bit strong, and the width requirement also depends on the smoothness factor and Hermite norm. Most previous works hold for ReLU activations, as also shown in Table 1.

-Minor Comments:

1. The statement of Theorem 1 might need to be further clarified about the randomness. When stating Theorem 1, the authors said "with probability at least $1-\zeta$", and the result still has the expectation notation. It would be better if the authors could clarify what randomness goes into the "$1-\zeta$" part and what randomness is the expectation taken over. One possible way might be to define the event that SGD travels outside the neighborhood of the initialization and state Theorem 1 in a similar way as Theorem 2.6 in (Oymak & Soltanolkotabi, 2020).

-Typos: 

1. Definition 3, "$\frac1c$" -> ""$\frac1b$""
2. $\rho_\Phi$ is used in Proposition 1 but not formally defined until Lemma 3, so it is better to move the definition earlier.
3. "$\simeq$" is used in Lemma 2 and Section 3.1 but is not formally defined.

---------------------Update--------------------------

Thank the authors for their responses. I have read all other reviews and the authors' responses to all the reviewers, and I have decided to keep my score unchanged. The authors' responses address some of my concerns, e.g., their main results do not directly require the weights during training remain close enough to the initialization. However, my major concern (the novelty of the proof techniques, which is also shared by the other reviewers) still remains because most of the results/methods used in this paper already exist in the literature. Therefore, I would like to keep my score and tend to recommend rejection.
summary_of_the_review: I tend to vote for rejecting this paper. Despite generalizing the linear convergence result to mini-batch SGD and improving the width requirement to sub-quadratic, my major concern about this paper is its limited novelty, as explained in the "Concerns" section above.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: 1. This paper proves that SGD converges to a global minimum in certain non-convex problems assuming the loss function satisfies a growth condition. The proof relies on assuming that the initial Jacobian matrix is non-singular and shows that it stays non-singular since SGD iterates remain close to the initialization. 
2. The paper then applies the above analysis to a two-layer neural network and proves that a subquadratic scaling on the width is sufficient for global convergence assuming the minibatch size grows with the number of training samples. For constant batch size, it requires quadratic over-parameterization. Furthermore, an interpolation between subquadratic and quadratic scaling is given depending on the batch size. 
main_review: Pros:
1. This paper relaxed the over-parameterization requirement in two-layer neural networks for the SGD algorithm, which is certainly an important direction.
2. The proof involves bounding the distance to initialization for SGD iterates, which is much more challenging than for GD. I think the techniques here can be useful in future studies in SGD convergence. 

Cons:
1. I am concerned about the novelty of the proof. It seems to me that the proof is very similar to the NTK analysis in the sense that it argues the Jacobian matrix is full-rank during the training because the SGD iterates stay close to the initialization. I wonder if there is any conceptual difference between this proof and the NTK argument. 
2. In section 3.1, the authors assumed that $m\geq d_0^2$ and claimed it's the case in practice. I think in practice the number of training samples $(m)$ is much smaller than the square of input dimension $(d_0^2).$ For example, in CIFAR the input dimension is $32\times 32\times 3=3072$ and there are only $50000$ training samples; in ImageNet the input dimension is $256\times 256\times 3=196608$ and there are only 1M samples. 
3. One of the messages of this paper is that a smaller batch size requires a wider neural network. Is there any empirical experiment that can support this claim? Otherwise, this might just be an artifact of the analysis.
summary_of_the_review: The main result of this paper is proving the subquadratic width scaling for SGD convergence in two-layer neural networks assuming the batch size grows with the number of training samples. I understand that the analysis requires new techniques to bound the distance of SGD iterates to its initialization, but I think the proof is conceptually the same as NTK analysis and am concerned about its novelty. Therefore, I think this paper is marginally below the acceptance threshold. I will be willing to raise my score if my concerns are addressed. 

------------------

Thanks for the response. After reading the response and other reviews, I decided to keep my original score. My major concern is still the novelty of the proof.
review_title: null

Meta-review: This paper shows SGD enjoys linear convergence for shallow neural networks under certain assumptions. However, reviewers reach the consensus that this paper lacks technical novelty. The meta reviewer agrees and thus decides to reject the paper.
Decision: Reject