Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a new regularization for deep linear networks. The analyses sections showed theoretical analysis empirical results of this regularizer in the context of 1-layer/deep networks and SGD/Adam optimizer in matrix completion tasks where the ground truth matrix is low-rank. The main experiment was conducted on a recommender system task, showing the proposed regularizer on very simple models could perform complicated methods. 
 
strengths_and_weaknesses: ## Strengths:
1. I quite like the style of studying simple tasks and the way that the authors interleave illustrative examples with theoretical analyses. 
2. The synthetic example is used to compare a wide range of alternative methods/regularizations, clearly showing the advantage of the proposal. 
2. The authors performed extensive parameter sweeps as described in the appendix. 
3. The authors are clearly technical in their analyses. 

## Weaknesses:
1. Writing is unclear to the extent that I cannot clearly see if the authors delivered the promise made in the introduction/contribution paragraph. I'm also not an expert in this field so could just be a background mismatch, but I find that the main message is overcomplicated and partially obscured by very scattered writing. 
2. This method does not seem to be directly applicable to nonlinear networks, but the main experiment might have demonstrated this but the description was not clear. 
3. The main experiment was only conducted in a single setting and dataset, which is somewhat lacking.
3. The main theoretical advantage seems to be some form of preconditioning, but the authors did not go deep enough to suggest why such preconditioning may be beneficial, apart from being pos-semidef.
3. Mathematical presentation needs to be thoroughly tidied up. 
4. The synthetic experiments are trained under full-batch, which does not really produce stochastic gradients.

## Details:
1. Line 54: depth is not necessary compared to deep linear networks, not any networks. I also find this statement and many other statements very strong, and then realize that the authors probably mean in the context of deep linear networks. 
2. Lines 30-31 say the task is to "recover the unseen entries", then in 58-62 the author describes that their regularizaton has an effect on the "rank and generalization", and the figure clearly does not give errors on how well the model recovers unseen entries. What exactly is the goal of the task? Is it to recover the unseen entries? To get the correct rank? Or test prediction which I assume is generalization? Please be clear here and everywhere.
3. Lines 120-121: This part describes how the student network weights are set up. The first time I read it, I thought the authors meant that they focused on rank-5 matrices in each layer, but then understood that the rank-5 applies to the teacher matrix $W^*$. 
4. 135: what is singular value separation? This is undefined in the paper but gets mentioned a lot later. I'm a non-expert but I think doesn't take an expert to understand, it must be some trends shown in the figures. 
5. Line 158: "the trajectory of ... its singular values $\sigma_i$" does not appear in the Lemma. Is this in equation (14) of the Appendix?
6.  I don't think the rates in equations (3) and (6) are ever proved in the appendix. 
7. Line 190, comparing figures 1 & 2, top rows, I don't think this statement is supported by the figures. The curves stabilize at mostly some iteration numbers. Further, the green curve in Test Error actually converges slower.
8. Section 4: I have no idea what the authors have done for the recommender system. Please use equations or give a reference.
9. Line 519: the authors should define the rank in the main text explicitly rather than giving a reference in the appendix. If an approximate rank is used, perhaps the authors should also try other possible rank definitions. 
10. Line 211: "evolves" -> "evolve"
questions: 1. Line 45: what does "acceleration" mean? Please specify or give examples here. Also, I don't think this paper later even partially answers this question, except by deferring it to some sort of preconditioning. 
1. In the main experiments, are the features produced by linear mapping or nonlinear networks? If it's nonlinear networks, how is the regularization applied? 
1. Line 291: what's meant by "without any factorizations"? Isn't the model itself a factorized representation of the data matrix?
1. I see that most derivations aim to express dynamics as preconditioned gradient descent, but could the authors justify why this particular preconditioning is good? Why not any preconditioning?
2. Buttom line of page 19 (For some reason, the line numbers disappear), I cannot think of why the last equality holds. What's the "factorization of Kronecker product"? I did a simple search but could not find any properties related to this line. 
limitations: The discussion mentions some limitations and future work, but should also discuss limitations of the experiment design, including full-batch training, a single matrix factorization task and a single dataset.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Deep Linear Neural Networks gradient descent implicitly regularizes towards low-rank solutions in the matrix completion/factorization tasks. This work proposes an explicit penalty term that mimics the rank minimization behavior of deep linear networks. The proposed method is invariant to depth. A depth 1 linear neural network equipped with the proposed penalty produces the same rank reduction with comparable performance as deep matrix factorization. The authors note that their proposed penalty works really well with Adam optimizer but not with Gradient Descent. They speculate that the observed behavior could be due to the interaction of inductive biases inherent to the optimizers with explicit regularizers. They conduct a series of experiments to demonstrate this difference between Adam and Gradient Descent. Finally, they run experiments on real world data - MovieLens100k and show that they perform competitively against the existing methods which often use specialized architecture, parametrization, additional side information, etc. 
strengths_and_weaknesses: Strengths:
* This work takes a unique approach towards rank minimization. They propose an explicit penalty that mirrors the implicit rank minimization of deep matrix factorization.
* The proposed method is depth invariant which is an interesting property. 
* The proposed method achieves better generalization and rank-reduction performance beyond many techniques even in low data regimes.
*  The authors note that their proposed penalty works really well with Adam optimizer but not with other optimizers such as Gradient Descent. The authors have done sufficient empirical evaluations to demonstrate the differences between the behavior of the penalty term under different optimizers.

Weaknesses:
* The proposed method is depth invariant. If the authors could list potential areas where this could be useful, it would immensely help the paper.
* It would be great if the authors could throw some theoretical insight into the reason behind performance discrepancy between various optimizers.
questions: If the authors could address the following weaknesses, I'd be more than happy to increase the scores -
* The proposed method is depth invariant. If the authors could list potential areas where this could be useful, it would immensely help the paper.
* It would be great if the authors could throw some theoretical insight into the reason behind performance discrepancy between various optimizers.
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a penalty for gradient descent that consists of the ratio between the nuclear (trace) norm of the weight matrix and its Frobenius norm. The paper shows analytically and empirically, in the task of matrix completion, that linear networks trained with the proposed penalty exhibit a large degree of independence on depth, as long as the models are optimised with Adam (or Adamax), but not with vanilla gradient descent. In particular, the paper presents results that show that in the degenerate case, that is a 1-layer linear network, the model trained with Adam and the proposed penalty achieves generalisation similar to deep networks as well as low rank and spectral sparsity.
strengths_and_weaknesses: This is, to the best of my judgement, an overall very good paper. First of all, the paper makes a very concrete contribution: the proposal of a penalty for gradient descent. The authors present a set of experiments that analyse 1) baseline conditions without the penalty, 2) the impact of the penalty on both vanilla gradient descent and models optimised with Adam, with particular attention to 3) the degenerate case (depth 1). Furthermore, the paper extends the empirical analysis by studying other optimisers and penalties, as well as some experiments on a real world data set (movies recommendations). With this experimental setup, the authors find an interesting result, namely that the proposed penalty induces certain degree of depth independence when the models are optimised with Adam but not with natural gradient descent. The paper provides a theoretical analysis of the dynamics under certain common assumptions and shows empirical results that analyse the generalisation performance, the rank of the weight matrix and the dynamics of the 1st and 5th singular values. 

In terms of significance, I believe these are interesting results that can encourage further research into understanding the optimisation dynamics of neural networks and the interplay between implicit and explicit regularisation, which are topics that have attracted significant interest in the last decade. In terms of originality, the authors claim that the proposed penalty is novel and I am myself not aware of previous work proposing it, though I am not sufficiently up to date with the most recent literature on this specific domain.

The paper is very well written, much better than the average submission I have reviewed at machine learning conferences. The introduction is very clear and it smoothly motivates the problem by summarising the relevant related works and gaps in the literature. Section 2, on related work is easy to follow and concise. Then, the core section of the paper, Section 3, is very reasonably structured, following a logical order (setup, baseline models without penalty, models with the penalty, the degenerate case and other optimisers and penalties. The paper ends with a brief section where the role of the penalty is analysed on a real world data set and a discussion. I would also like to note that I have not identified any typo, which is extremely rare in the papers I have reviewed.

Regarding quality, I think the paper is technically sound, the analyses seem correct to my judgement (though I have not thoroughly reviewed all the supplementary material) and the results support the claims. Furthermore, I would like to highlight that the authors humbly discuss the significance of their paper, in light of what the paper does show and does not show, as well as the limitations and aspects that are left for future work. This is, as well, and unfortunately, rare in machine learning submissions, but I highly appreciate it.

I can identify some weaknesses, but these are minor and most are actually mentioned by the authors in Section 5. These mostly have to do with the limited scope of the experiments and analyses, which leave some open questions, such as: the role of the penalty on non-linear networks, on other tasks and data sets, whether other penalties can achieve the same depth-independence, a more thorough analysis of why the penalty only works with Adam and whether the same dynamics could be induced with a modification of the penalty on vanilla gradient descent. Since it is impossible to address all these questions properly in a single paper and the authors actually mention them, I consider these weaknesses minor, or not at all. 

Finally, one aspect that could be improved in the paper is the fact that the results (plots) from the empirical analyses seem to reflect single experiments. I think the conclusions and insights would be stronger if repetitions were carried out (with various initialisation seeds, for instance, and, ideally, choices of $\Omega$) in order to obtain a measure of the confidence intervals for the dynamics.
questions: * Question: While the main claim is that the proposed penalty induces depth invariance with Adam, in Figure 2 we see some differences in the test error dynamics (bottom left) across different depths. In particular, with 2 layers, the dynamics are qualitatively very different and the model achieves lower error than with more layers. What do the authors think this is due to?
* Suggestion: include repetitions in the experimental setup in order to obtain confidence intervals for the experimental analysis.
* Suggestion: the actual proposed penalty is only expressed in the middle of a paragraph in Section 1. I think it would be clearer to include the explicit equation of the optimisation (Eq. 1) with the penalty. This would make it easier for future readers.
* Suggestion: the title of Section 3.5, "Comparative performance" seems quite general. I would consider making it more specific, such as "Comparison with other penalties and optimisers". 
* Suggestion: same goes for the title of Section 4. How about "Results on real-world data"?
limitations: As mention above, the authors do briefly but explicitly discuss the limitations of their paper.
review_title: null

final_score: 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.
review_content: summary: The authors develop a novel regularization method that improves the performance of shallow linear neural networks on tasks that can be represented as low-rank matrix completion/factorization. They offer theoretical results for analyzing such models under vanilla gradient descent vs. ADAM, and show that an adaptive scheme allows shallower networks to converge to better solutions.
strengths_and_weaknesses: Strengths

The proposed method is simple and effective, supported by thorough theoretical and empirical justification.
The experiments are logical and comprehensive (including appendix), with good interesting results that are easy to interpret.
The text is clear and well-written. The figures are also clear.


Weaknesses

In general, it would be helpful to be even more explicit about the connection between the forms of the various dynamics equations and the empirical results. For example, it would be nice to plot the predicted trajectories of the singular values against the actual trajectories. I still don't have good intuition for the behavior of the dynamics equations, so highlighting different regimes of behaviors would be helpful. For example, when the authors say that a term may accelerate convergence (line 168-9, 202), it would be helpful to describe (or give intuition for) the conditions under which such acceleration occurs, before jumping to the empirical demonstrations that acceleration is indeed observed. How does the convergence rate or error scale with effective rank of the underlying matrix (Appendix experiment does not really answer this)?

As the authors acknowledge in limitations, the scope of their findings is fairly narrow. Even though this is a theory paper, perhaps the motivation could be strengthened by noting that shallow networks are extremely fast and lightweight and thus could find use in applications where these attributes are important.

The title would suggest a very different line of work than what is being examined. Indeed, it is a little misleading in the sense that the paper's main results pertain to depth-1 and depth-2 linear networks, whereas the title writes "deep networks". IMO the title should highlight that the authors develop a novel regularization method that is effective for shallow networks. The title also suggests that the authors design a novel implicit regularization scheme, whereas it seems that implicit regularization refers to an existing property of gradient-based methods (the tendency to favor low-norm solutions). It seems that this implicit regularization is innate to both SGD and Adam, but it would be clearer if the authors instead highlight the property of adaptive optimizers that makes them more effective in the regime studied.
questions: Either make each lemma a theorem / corollary, or explicitly state the overarching theorem.

Line 168-9: It would be helpful to characterize the condition under which normalization will dampen or accelerate the trajectory. Why does it accelerate in the case you specified?

Line 230-1: "This similarly holds for un-regularized Adam" is confusing after reading the previous sentence, and suggests the opposite of what you want to say. Reword / swap the order.

Eqn (6): GD -> GF

I think the appendix should include explicit proofs of Lemmas 2 and 3. Even if they are easy to compute, it will still help some readers follow along more easily.

Add bolding to Table 1 to highlight that your penalty is superior for all the adaptive optimizers.
limitations: The authors acknowledge that the connection between linear and nonlinear networks in this context is not explored, and that the gradient flow regime may not hold in some practical settings. The authors point to good future directions.
review_title: null

Meta-review: metareview: All reviewers recommended that the paper be accepted, and I accordingly recommend the same. I encourage the authors to take into account suggestions made by reviewers so as to further improve the text towards the camera-ready version.
confidence: Certain
Decision: Accept