Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary of review:

This paper provides a detailed analysis of gradient flow in (over-parametrized) two-layer linear neural networks. The main results state the precise dynamics of gradient flow for both symmetric and asymmetric matrix factorization, starting from certain spectral initialization. One novel insight that stems from the analysis is that for asymmetric matrix factorization, "imbalanced initializations", where the left and right singular values of the iterates differ, converges faster than "balanced initializations". Simulations further validate this insight.

Setting:

(i) Symmetric matrix factorization: Given a symmetric matrix Y, the problem is to solve a mean squared loss between Y and UU^T to factorize Y, where U is a (possibly over-parametrized) variable matrix.

(ii) Asymmetric matrix factorization: The asymmetric setting considers an asymmetric matrix Y and the asymmetric factorization of UV^T for factorizing Y.

Results

(i) This paper focuses on the convergence of the gradient flow of U for minimizing the mean squared loss, starting from spectral initializations. Informally, a spectral initialization has the same eigenspace as Y.

For these spectral initializations, the gradient flow paths essentially become coordinate-wise updates over every singular value. Then, the authors went on to state the precise dynamics of gradient flow for every singular value. The results imply that "large" singular values (of Y) converge faster than "small" singular values (of Y) in gradient flow.

(ii) This paper begins by studying spectral initializations, where $||U^TU - V^TV||_F$ is small, then discusses how to generalize their result to non-spectral initializations.

For spectral initializations, this paper observes crucially that $U^TU - V^TV$ is preserved throughout gradient flow. Hence if this quantity starts small, it will remain small throughout gradient flow. Furthermore, for "large" singular values of $U^TU - V^TV$, the results imply that these singular values converge faster than "small" singular values of $U^TU - V^TV$.

For non-spectral initializations, this paper observes that $U^TU - V^TV$ is still preserved during gradient flow, but this quantity now depends on how "balanced" the initializations of U, V are.

Criticism:

It would help improve my understanding of this paper if the authors clarify the following questions.

(a) The "acceleration" claim of this paper comes from comparing the results to a linear model baseline. However, I am not completely sold on this comparison. For example, what would the results imply if compared to properly parametrized U (and V)? Is there any provable advantage of over-parametrization in this setting?

(b) The result of Corollary 1 for symmetric matrix factorization, where larger eigenvalues converge faster than smaller eigenvalues, also appears in linear regression. In particular, the gradient flow of linear regression also shows similar patterns, where larger eigenvalues (of the sample covariance matrix) converge faster than smaller eigenvalues. Therefore, in my opinion, the results in Section 3 and 4 seem more novel compared to the results in Section 2.

(c) While the results state fairly precise dynamics of gradient flow, how well would they extend to settings with sampling errors? For example, what about matrix completion? Would your claim regarding "imbalanced initializations" still hold?

Writing

Overall, this paper is well-written and easy to follow. Although the paper would be easier to read if it is less dense. I do not quite understand the claims in Figure 2. You explained in Section 4 that you need $K \le m + n$ for identity initializations and Proposition 5, but here you say that k ranges from 50 to 200? Please clarify.
review_title:  A detailed analysis of gradient flow in two-layer linear neural networks

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies the implicit acceleration of gradient flow for training a two-layer linear model. Compared with the one-layer linear model, the authors show that gradient flow over an overparameterized two-layer linear model may achieve a faster convergence rate, given a nice data spectrum and proper initialization. Moreover, the authors investigate the convergence of gradient flow with an arbitrary initialization and show its connection to Riccati differential equations as well as the explicit regularization. Overall the idea is clearly presented, the experimental results also well back up the theory.

My main concern is that it may not be fair to compare the convergence rate in terms of gradient flow. For example, you can simply reparameterize the parameter by X -> 2X, and the acceleration can also be achieved from the perspective of gradient flow. I think in order to fairly compare the convergence between different parameterizations/initializations, gradient descent is a better choice. Back to the example of X->2X, in this case, the smoothness parameter will become larger, finally one can observe that the convergence rate of GD under this parameterization will remain unchanged. 

Regarding the convergence results, the authors still require strong conditions (parameter and data can be diagonalized simultaneously) on the initialization to prove the convergence of gradient flow. What happens if considering more general assumptions on the initialization, such as the random/orthogonal initialization used in the following papers? The authors may also need to compare the convergence rates of the derived results and those in the following papers.

[1] Du, Simon S., and Wei Hu. "Width provably matters in optimization for deep linear neural networks." arXiv preprint arXiv:1901.08572 (2019). 

[2] Wu, Lei, Qingcan Wang, and Chao Ma. "Global convergence of gradient descent for deep linear residual networks." Advances in Neural Information Processing Systems. 2019. 

[3] Zou, Difan, Philip M. Long, and Quanquan Gu. "On the Global Convergence of Training Deep Linear ResNets". International Conference on Learning Representations.

[4] Hu, Wei, Lechao Xiao, and Jeffrey Pennington. "Provable Benefit of Orthogonal Initialization in Optimizing Deep Linear Networks." International Conference on Learning Representations.

The regularization term in Eq. (20) seems pretty similar to the commonly-used regularization in solving low-rank matrix problems [5,6] for balancing (but they use 1/16 weight), could you please briefly discuss their connections?

[5] Tu, Stephen, et al. "Low-rank solutions of linear matrix equations via Procrustes flow." International Conference on Machine Learning. PMLR, 2016.

[6] Wang, Lingxiao, Xiao Zhang, and Quanquan Gu. "A unified computational and statistical framework for nonconvex low-rank matrix estimation." Artificial Intelligence and Statistics. 2017.

Is the overparameterization necessary? From the presented theorems, I do not see whether the derived results have a dependency on the dimension of the matrix U or V. The authors may clearly specify why one needs to consider overparameterization linear models. For example, assume the data matrix has rank r, can the theory in this paper still hold if set the dimension of U or V as d*r?

=========== after reading rebuttal ===============

I do not agree with the author's response to my first comment. Considering parameterization $X = 2U$ (here I use the notation U to avoid the confusion), then the loss function becomes $L(U) = \frac{1}{2}\\|Y-2U\\| _2^2$ and the gradient flow with respect to $Z$ writes $\dot {U}= -2(2Z-Y)$. Then we have $\dot {X} = 2\dot{U} = -4(2U-Y) = -4(X-Y)$, which gives a rate $O(e^{-4t})$, which is faster than the $O(e^{-t})$ rate achieved without using this parameterization. Therefore, comparing the convergence rate in terms of gradient flow may still not be fair and valid. 

Based on this issue I would like to keep my score.
review_title: Some comparisons may be presented in a more detailed and precise way

final_score: rating: 7: Good paper, accept
review_content: 1.  Paper Summary 

This work analyzes the implicit acceleration of gradient flow for over-parameterized 2 layer networks (i.e. 1 hidden layer networks) used for matrix factorization.  By presenting a novel analysis connecting the gradient flow to Riccati type differential equations, this work demonstrates that imbalanced initializations can lead to acceleration.  The authors present convergence rates for symmetric and asymmetric matrix factorization under both spectral and non-spectral initializations.  The convergence rates for these settings are indeed faster than those in the linear model.  The authors lastly provide empirical results to support their theory.  
 

######################################################################

2. Strengths

2.1.  The connection between gradient flow and Riccati type differential equations is novel to the best of my knowledge and provides a simpler and clearer means of understanding implicit acceleration in over-parameterized models than prior works.  

2.2. The paper is written clearly and is easy to follow.  The authors present examples of acceleration under the simpler setting of spectral initialization before extending to the more nontrivial case of non-spectral initializations.  
 

######################################################################


3. Limitations

3.1.  I believe the authors are missing some references to related work.  In particular, below are some related works:

(1) https://arxiv.org/pdf/1810.02281.pdf - This work extends the notion of zero balancedness considered in the work by Arora et al. 2018 to the case of approximate balancedness.  The analysis presented in this work is for deep linear networks (more than 2 layers) and for gradient descent.  Technically, I believe this work does fall under the imbalanced case and also yields a fast convergence rate.  

(2) https://arxiv.org/abs/2003.06340 - This work analyzes spectral initialization under gradient descent in deep linear networks (of arbitrary layer structure).  In particular, this work also demonstrates linear (fast) convergence for gradient descent under spectral initialization (Proposition 2).  

I believe it is important for the authors to position their work with respect to the above works, but I do not feel that missing these references diminishes the novelty of the submitted work. 
 
3.2.  While the connection to Riccati type differential equations is interesting, it would be nice if the authors could discuss how similar analysis could be used for deep linear networks (at the moment there does not appear to be an obvious extension).  

3.3.  (Minor) The authors briefly mention that discrete time convergence rates can be derived from continuous time counterparts using symplectic integrators in the introduction, but it would be nice if there were a more rigorous connection between the related work and the rates presented in the submitted work.  


######################################################################

4. Score and Rationale

My recommendation is to accept the paper.  I believe the main strength of the paper was in providing a well-presented, rigorous, and novel analysis for understanding acceleration in over-parameterized matrix factorization.  The connection to Riccati type differential equations and identifying dynamical invariants presents an interesting alternative means of gaining intuition around implicit acceleration in over-parameterized networks.  


######################################################################

5. Comments

5.1.  I believe the Y in equation 3 should be m x m instead of m x n for the symmetric case. 

5.2.  I feel that the notation could be made a bit easier to follow in Section 3 & 4. In particular, I believe bar(U), bar(V) are overloaded to represent diagonal matrices in definition 3, but these quantities are assumed to be non-diagonal for the remainder of the work.  As this is an important point, I feel that it could be emphasized a bit more.  

5.3.  I feel that there could be more intermittent references to prior results throughout the work.  For example, the symmetric matrix factorization problem is discussed extensively in https://papers.nips.cc/paper/7195-implicit-regularization-in-matrix-factorization.pdf.  Similarly, invariance and convergence rate for gradient descent and under spectral initialization is discussed in https://arxiv.org/abs/2003.06340.  

5.4.  There is an important distinction between the matrix factorization problems considered in this work and prior work.  Namely, the matrix Y has fully observed entries whereas in some prior works, Y is not completely observed.  I think the analysis may get a bit more tricky for the case of unobserved entries, but the authors could maybe point this out.  
review_title: Interesting Approach to Understanding Implicit Acceleration

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper considers the gradient flow dynamic for two-player linear neural networks. In detail, it studies the implicit acceleration of gradient flow brought by overparameterization and shows the reason for implicit acceleration is the existence of conservation law. It studies the convergence for gradient flow under both balanced or imbalanced linear networks, and with spectral or non-spectral initialization. Compared with previous work, this work is the first to provide an explicit characterization of the gradient flow with respect to their eigenvalues. Experiment results suggest that such an implicit acceleration indeed exists. 

Here are my detailed comments.

- Page 2, (2): why call (2) ‘a symmetric one-layer linear model’? Does that suggest $m = n$? The same issue holds for (3). Is $Y$ in (3) the same as that in (2)?

- An interesting observation is that under the spectral initialization, for the symmetric case, the convergence rate of the eigenvalues does not depend on the initial value of $X_0$ (it is $e^{-4t|\sigma_i|}$). However, for the asymmetric case, the convergence rate is $e^{-t\sqrt{4\sigma_i^2 + \lambda_0^2}}$, which explicitly depends on the initial matrix $X_0$. Can the authors make more comments about that?

- The ‘acceleration’ compared with original gradient flow over $X$ suggests that by a matrix factorization, the convergence of eigenvalues varies may be accelerated according to the eigenvalues over the data matrix $Y$. Is it true that in the worst case, say for some $i$, $\sigma_i \approx 0$, then the convergence speed of $\sigma_i(t)$ will decrease to 0? In that case, can we still call it ‘acceleration’?

- In Proposition 5, the authors build the convergence results for the case $\Lambda_{Q_0} = \lambda_0 I_k$ for the general non-spectral initialization case. However, I hardly can find a non-spectral initialization case satisfying such a condition. Can the authors provide some examples?



review_title: Review for 'Implicit Acceleration of Gradient Flow in Overparameterized Linear Models'

Meta-review: This paper studies the implicit acceleration of gradient flow in over-parameterized two-layer linear models. The authors show that the amount of acceleration depends on the spectrum of the data without assuming small, balanced, or spectral initialization for the weights, and establish interesting connections between matrix factorization and Riccati differential equations.  While this paper provides some interesting results regarding implicit acceleration in training linear neural networks, the reviewers raised quite a few questions and concerns about some claims made in the paper, as well as an inadequate comparison with previous work. Even after the author's response and reviewer discussion,  the reviewers' doubts are still not completely cleared away. I feel the current form of the paper is slightly below the bar of acceptance, and encourage the authors to carefully address reviewers' comments in the revision.
Decision: Reject