Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proves the convergence rate of gradient flow for training two-layer linear networks. In particular, this paper discusses the connection between initialization, optimization, generalization, and overparameterization. The results show that gradient flow can converge to the global minimum at a rate depending on the level of imbalance of the initialization. Moreover, the authors show that random initialization and overparameterization can implicitly constrain the gradient flow trajectory to converge to a point lying in a low-dimensional manifold, thus guarantees good generalization ability.

This paper is well organized. It is interesting that sufficient imbalance can guarantee global convergence of two-layer linear networks while other papers may require nearly zero initialization or wide enough networks. Besides, my detailed comments are as follows.

One drawback is that this paper still requires that the width be greater than n+m-1 (Theorem 1), while the network width condition proved in some existing works (listed as follows) does not depend on the number of training examples n (although they require random or orthogonal initialization), the authors may need to comment their network width conditions after Theorem 1 (currently the authors only say that “our results is not limited to extremely wide networks with random initialization’’).

[1] Du, S. S., & Hu, W., Width provably matters in optimization for deep linear neural networks. arXiv preprint arXiv:1901.08572.

[2] Hu, W., Xiao, L., & Pennington, J., Provable Benefit of Orthogonal Initialization in Optimizing Deep Linear Networks. In International Conference on Learning Representations.

[3] Zou, D., Long, P. M., & Gu, Q., On the Global Convergence of Training Deep Linear ResNets. In International Conference on Learning Representations.

The authors prove that the limit of gradient flow can be sufficiently close to the minimum-norm solution if the neural network is sufficiently wide. This conclusion is good and of certain importance to understand the optimization path of training linear networks. However, if the data matrix X is of full rank and D<n, the training objective is strongly convex. In this case, there is only one minimum, thus the convergence result Theorem 1 can directly imply the parameter convergence results in Theorem 2. 

Some experiments may be needed to verify the theory. In particular, theorem 1 only provides an upper bound result, thus cannot fully characterize the effect of the imbalance on the convergence. The authors may try initializations with different imbalances and plot the convergence curves to demonstrate the results in Theorem 1. Additionally, results in Theorem 2 may also need to be verified in experiments.

So far I can only see that the imbalance plays an important role in training two-layer linear networks, can you extend this to multi-layer cases? Will the imbalance at the initialization together with sufficient overparameterization still guarantee the convergence of gradient flow?

review_title: Interesting observation and theory, more detailed comparsions and some experiments are needed.

final_score: rating: 3: Clear rejection
review_content: This paper studies the optimization and generalization properties of a two-layer linear network. The considered setting is over-parameterized linear regression where the input dimension is D, number of samples is n<D, and the target dimension is m. The hidden width is h. The paper has two main results. The first result is exponential convergence of gradient flow to global minimum, where the convergence rate depends on the (m+n-1)-th singular value of an "imbalance" matrix. The second result shows that the solution found is close to the minimum L2 norm solution if certain orthogonality assumption is approximately satisfied at initially; then it was shown that if the width h is sufficiently large, then under a random initialization scheme, the solution found is close to the minimum L2 norm solution with a distance $1/\sqrt{h}$.

pros:
The results are not previously known to my knowledge. The proofs appear to be correct as far as I can tell.

cons:
My overall concern is the significance of the results. The results, while correct, do not contribute much to our understandings of optimization and generalization in deep learning. The ways in which the authors interpret the results are unsatisfactory or even misleading.

1) Thm 1 shows a convergence rate of $e^{-ct}$, where $c$ is the (m+n-1)-th singular value of an imbalance matrix. On the appearance this result seems to suggest that a larger $c$ is beneficial for convergence. However I believe this suggestion is incorrect and can be very misleading. Indeed, previous work (e.g. Arora et al. 2018a) has shown linear convergence under zero imbalance ($c=0$), as cited in the paper, but Thm 1 fails to capture that. I think in general this $e^{-ct}$ is a very loose bound that does not capture the real convergence rate (unless the authors can provide convincing evidence that suggests otherwise).

That said, I do think Thm 1 is an interesting theoretical result and the proof is clever. I'm concerned about the practical relevance and the possibly misleading message it sends.

Another weakness is that Thm 1 only considers gradient flow but not gradient descent. 

2) Thm 2 and its interpretations are unsatisfactory in a number of ways.

First, we know that just doing a normal linear regression using gradient descent (starting from 0) leads to the minimum L2 norm solution. So now we go through all the trouble in the 2-layer net and finally show we can find a solution that's almost as good as linear regression -- what's the point of doing that?
Of course, one may argue that we are studying a toy model in order to better understand deep learning. However, the main message from this result can be also conveyed in linear regression -- as shown in Sec 4.1, the main step is to find an invariant manifold for gradient flow such that the minimizer in that manifold must be the min-norm solution; for linear regression, such manifold also exists, which is just the span of the data points. 

Second, the initialization used ($1/h$ variance in both layers) is unconventional. It's different from the standard 1/fan_in initialization or the NTK parameterization. What happens if we use those more standard initializations? And what happens if we make the initialization smaller, e.g. $1/h^2$, or $1/h^{100}$? Would those change the result? The scale of the initialization is very important in this line of work (such as NTK), so this should be addressed clearly.
(The authors actually claim that as $h\to\infty$ we would get the NTK solution, following Jacot et al (on page 7). I actually don't think Jacot et al.'s work directly implies this, because this paper uses a different initialization scale.)

Third, the authors try to differ this result from all the NTK results, but the theorem is exactly showing that the final solution is close to the NTK solution. Isn't this a bit ironic?

Fourth, the authors claim "this is the first non-asymptotic bound regarding the generalization of linear networks in the global sense." Maybe check out these papers:
Implicit Bias of Gradient Descent on Linear Convolutional Networks,
Implicit Regularization in Matrix Factorization.
Also, many NTK papers also have non-asymptotic bounds. For 2-layer linear networks, one should be able to easily get a bound on the distance of the learned model and the min-norm solution -- might be better than Thm 2.


-------- after rebuttal --------

Thanks to the authors for the response and the updated manuscript. My assessment stays the same, and below are my additional comments.

1. About Appendix E

Thanks for the clarification about the initialization scaling. However, this raises more concern about the significance of the result. In Appendex E, it is shown that the scaling considered in the paper and the NTK scaling lead to the **same** gradient flow dynamics. This suggests that we are actually still in the kernel regime, in contrary to the main motivation and the claims in the paper. (As for the time rescaling issue, it doesn't matter in gradient flow since the difference can be absorbed by rescaling the learning rates.)

Appendix E also mentions that several previous papers used a small multiplier $\kappa$ to make the initial network small. The authors claim that this makes the convergence rate slower. I don't think this affects the convergence rate, but it only affects the width requirement (see e.g. [1]). In fact, in stead of using this multiplier, there is another way to make the output zero without changing the NTK and without requiring a larger width, that is to use an anti-symmetric initialization -- see e.g. [2][3][4][5].

[1] Arora et al. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks

[2] Chizat et al. On lazy training in differentiable programming

[3] Hu et al.  Simple and effective regularization methods for training on noisily labeled data with generalization guarantee

[4] Bai and Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks

[5] Zhang et al. A type of generalization error induced by initialization in deep neural networks

2. About the motivating questions

This paper proposes to answer two questions in the introduction. The first question is "Is the kernel regime, which requires impractical bounds on the network width, necessary to achieve good generalization?" First, I don't think this paper answers this question since the considered regime is still basically the same as the kernel regime. Second, even if it does, this question itself is not valid, since there are numerous previous theoretical works that study generalization outside the kernel regime, in more interesting settings, e.g. [6][7][8][9] and many more (none of which are mentioned in the paper).

[6] Allen-Zhu and Li. Backward Feature Correction: How Deep Learning Performs Deep Learning

[7] Allen-Zhu and Li. What Can ResNet Learn Efficiently, Going Beyond Kernels?

[8] Wei et al. Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel

[9] Woodworth et al. Kernel and Rich Regimes in Overparametrized Models.

The second main question in the introduction is "Does generalization depends explicitly on acceleration? Or is acceleration required only due to the choosing an initialization outside the good generalization manifold?" I genuinely cannot understand this question.

3. In the updated manuscript the authors state "To the best of our knowledge, this is the first non-asymptotic bound regarding the generalization property of wide linear networks under random initialization in the global sense." This is still false (and insignificant) since the stated result is a direct consequence of previous NTK work.

4. I certainly understand that understanding deep learning is very challenging so it's a natural step to start with simple models. However I think this paper in its current form has limited significance and has major issues in how it discusses previous work, main motivations and contributions, etc., for reasons described in the review.
review_title: concerns about significance

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: #### General Comments
A proper initialization plays an important role in the success of over-parameterized models such as deep neural networks and high dimensional models.  However, the explicit role of initialization in theoretical results of an algorithm has not been stated well to my knowledge.  The main task of this paper is to  present a novel analysis of overparametrized single-hidden layer linear networks, which formally connects initialization, optimization, and overparametrization with generalization performance. Specially,  it is shown that the squared loss converges exponentially at a rate that depends on the level of imbalance of the initialization.
With respect to linear networks, the paper makes the following three main contributions:
（1） The role of initialization of the gradient flow on the convergence is characterized explicitly.  
  (2) The stationary point of the gradient flow is sufficiently close to the min-norm solution in the linear case.
（3） Random initialization for large wide  linear networks ensures that the dynamics of the network parameters 
      are constrained to a low-dimensional manifold. 
Overall, this is a written- well paper with significant novelty.  The results seem interesting in the deep learning theory literature. 
#### Specific Comments
(1) For Theorem 2,  the network width is required to be a polynomial of the input dimension D, which may be loose in some practical network structures.  I wonder whether such constrain can be relaxed further? it will be better that some quantitative comparison with those related work is made. 
(2) When noisy gradient descent is considered,   is the current analysis  still applicable to the case and similar results can be derived?  
(3) If an activation function is added such that the hypothesis class is nonlinear,  is the adopted analysis still valid? if not, what is the additional challenges? 
review_title: Comments to "On the Explicit Role of Initialization on the Convergence  and Generalization Properties of Overparametrized Linear Networks"

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper analyzes the convergence of gradient descent optimizing overparametrized linear nn, and proves a exponential convergence rate. Moreover, the paper proposes the distance of the optimizer to the smallest norm solution, which is justified in other papers such as Montanari, etc. as the generalizable solution. Thus the solution that SGD outputs has good generalization as well.
I believe overall the result is good, and the points are stated clearly. I have the following suggestions:

1. If the space is allowed in appendix, the algebra proving that (9) is time invariant can be provided, rather than "one can easily check". This intermediate step is critical for the full proof so I'd like to check it. (with this I can raise score to 6)
2. A sketch of Montanari paper about the property of $\hat \Theta$ can be discussed in the appendix. 
3. Regarding the thm, it would be definitely sufficient for the conference if anything can be suggested with RELU activation. In NTK work that's just another kernel so it's easy to extend, but it might be hard here, I'm not sure.
4. More literature review. I think Rong Ge has some papers about the landscape of matrix factorization problem so it's great to compare with them in detail, even if in appendix.
5. In appendix, it's also great to prove that under a certain initialization, what is the expectation/value of high probability of the imbalance singular value.
6. How does amount of data affect generalization bound? I think it's 1/\sqrt{n} in NTK work, any a similar behavior here?
review_title: Good result

Meta-review: The authors provide a new analysis of learning of two-layer linear networks with gradient flow, leading to some novel optimization and generalization guarantees incorporating a notion of the imbalance in the weights.  While there was some diversity of opinion, the prevailing view was that the results were not sufficiently significant for publication in ICLR.
Decision: Reject