Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposes the hypothesis that deeper networks are inductively biased to find low-rank solutions (i.e., in the sense of gram matrix of features being low-rank) and presents empirical evidence to support the same. The authors thoroughly show that this inductive bias is a property of the parameterization of neural networks, and so remains resilient to changes in optimizer or initialization distribution. Based on this, they suggest linear over-parameterization as a way to further bias the network to low-rank solutions, which is then linked to increasing generalization performance. 


main_review: **Pros:**
- Analyzing the properties of parameterization in neural networks is an important aspect. (But, often this is sidelined in literature by overly focussing on, e.g.,  'implicit bias' of gradient descent)
- The experiments and ablations are, in general, well thought of (as they would be natural questions) and properly executed.
- The paper is nicely written and the figures are very elegant (so much so that I am inclined to ask for the code used to make them :))
- Linear over-parameterization is a nice strategy to boost performance. This also has the advantage that at inference one can just collapse the involved weight matrices into a single equivalent weight matrix, thereby leading to compact networks for deployment.

**Cons:**
- Continuous rank measure: (a) I understand the motivation behind using a continuous measure --- the usual, discrete rank is sensitive to measure --- but if careful (i.e., using high precision) rank can still be useful. To make claims about low-rank solutions, it is quite important that the authors actually illustrate what goes on with the true rank, or even say numerical rank (which thresholds at some level). Then, once having presented the case there, you can move on to continuous approximations. (b) Next, the choice of the particular continuous measure is not justified, except for the statement that "our observations are consistent with alternative measures" --- but I did not find where this is shown (the appendix only contains how other measures of rank behave during training). (c) Finally, in light of the above arguments, I would say it is rather sloppy to say "we use rank and effective rank interchangeably" --- without first having justified it. Also, given this is just one additional word, it will help to make your point precise, which otherwise only serves to confuse what is actually being used. 

- Link to generalization: Figure 4 is the quintessential figure behind my criticism. We can clearly observe that the generalization gap first decreases and then starts increasing with increasing depth. In contrast, effective rank has an unaffected monotonic decrease with increasing depth. It is also not the case that the task rank is high, but is lower than that of input or output. This raises the question how strongly the claim that 'lower effective rank, better generalization' is justified? A similar fact is also evident in the Tables 1-3 --- the expansion factor needs to be tuned to a sweet spot. All this only weakens the presented claims. (Note: I am not against linear over-parameterization as I also mention in the 'Pros' above, over here the concern is the claim about the benefit of low-rank inductive bias of depth.) As a result, there are likely some other missing factors in 'true story' concerning the benefit and inductive bias of depth, and thus the authors should actually reduce their claims in this regard. 

- Empirical aspects: (a) It is not a great practice to report the best test accuracy during the training (I know a lot of other works do it, but one is ideally not supposed to see the test performance except for a handful of occasions). (b) Plus, it is not clear how critical LR tuning is to reap the benefits of linear over-parameterization. What happens when used with default settings? (c) Do you also tune the LR decay for explicit regularizers in Table 3? (d) In all the comparisons, are the different networks at a comparable loss value? Since it is that what makes things comparable, not necessarily the same number of epochs.  

- Choice of the kernel: The cosine kernel seems quite harmless at first glance, however, it carries within it the normalization by the norms of the feature maps. If the scales are anything except for constant factors, then the value of the effective rank used here can also vary. This raises the question if simply the linear kernel is used, would the empirical observations about low-effective rank with increasing depth remain the same?

- Related work: Overall, this is covered nicely in the paper, but I do still have some minor comments. (i) Does the cited work by Arora et al show that solutions reached with increasing depth also have lower nuclear norm? I would guess this work only claims about increasing convergence rate. Can you clarify? (ii) The recent work of [1] also makes related claims the neural networks are inductively biased towards low-rank solutions, but with low-rank in the sense of the Hessian. Also, see therein the benefit of true, discrete rank to obtain precise theoretical statements and formulas. 

[1] Singh et. al. 2021, Analytic Insights into Structure and Rank of Neural Network Hessian Maps, https://arxiv.org/abs/2106.16225

- Miscellaneous: 
(i) Another thing which I would be curious to see is that if you compare the effective rank of the gram matrix across layers from the same network itself. What kind of trend does it have? If the low-rank claims with depth are considered to be true, I would expect it to hold within the layers of the network itself? (empirically, since the authors use the same width for all layers, the comparison should not be a problem)
(ii) Fig 5, "rank training dynamics": I believe it would make the figure complete if the authors add the plot for the effective rank as well. In any case, I guess the rank dynamics similar to that in Figure 9?


summary_of_the_review: The paper investigates an interesting hypothesis concerning the parameterization of neural networks, in that increasing depth leads to solutions that have lower effective rank. This is backed by various experiments and ablations, and is in itself convincing. However, a significant part of the paper focuses on consequently linking this to generalization --- but which remains questionable. This is because their empirical observations and theoretical statement (in the deep linear network case) indicate that increasing depth results in a monotonic decrease in the effective rank, but in practice, they find this holds up to some moderate depth and beyond which the performance deteriorates. This weakens their connection of low-rank gram matrix solutions to generalization. But not only that, there are some critical yet unexplained choices/aspects in their framework, such as: whether effective rank is the right measure of rank, what happens with the actual (discrete) rank, choice of the kernel, etc. which raises additional questions and further serves to dilute the claims.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper explores the effect of depth on a continuous estimate of rank (effective rank) of the data embeddings computed by feed-forward neural networks.

On artificial datasets, the paper shows that at initialization (with common uniform or normal weight distributions), the effective rank of both linear and non-linear MLPs decreases with depth, and this is preserved after training. The results does not extend to network architectures with skip-connections such as ResNets.

The authors claim that this low-rank bias of the embeddings help generalization on natural datasets, and show that a reparametrization of common architectures where the linear layers are replaced by products of linear layers improves test accuracy on CIFAR-10 and CIFAR-100.

main_review: The paper is well written and the claims are clear. However I'm not sure that the main claim is not trivial, after all, when matrices are multiplied, rank can either decrease or stay the same. Whether a low effective rank of the embeddings helps generalization is not very clear to me, the observed benefits of the proposed overparametrization might be just due to increased capacity. Notably, most modern deep architectures use skip connections, and as shown in appendix C, skip connections correspond to identity matrices which preserve the rank.

The connection to Solomonoff's theory of universal induction that the authors make seems far-fetched: in the Solomonoff ensemble shorter programs consistent with the data are preferred, while in deep learning deeper neural networks, which are longer programs, are preferred, which suggests that neural networks operate far from the idealized regime of Solomonoff induction.


summary_of_the_review: The paper presents somewhat interesting observations on the algebraic properties of feed-forward neural networks, however their relevance to the generalization power of such models is not entirely clear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper conduct several controlled experiments and arrive at the following results:
- Deep networks (both linear and non-linear) are biased towards learning low-rank embeddings at initialization.
- This low-rank bias exists even after the training is done regardless of the initialization or training algorithm.

This paper also proposes a new regularization method which is adding extra linear layers which does not increase the network's expressivity but biases the network more towards learning low-rank solutions.
main_review: Strengths:
- The paper is very well-written and I enjoyed reading it.
- It starts with a conjecture and then validates that through experiments.
- Using the effective rank as defined in Def. 1 is smart and it is continuous.
- I liked it very much that the authors investigate that whether the bias is due to initialization or the training procedure itself.
- This paper also does a good job at proving an overview of previous related work.

Weaknesses:
- I found most of the results to be discovered in related work in one form or another. As acknowledged by the authors, in several works by Arora et al. (2018 a,b; 2019 a,b) as well as Saxe et al. (2014) such a bias has been noted before.
    - I appreciate it if the authors can pinpoint the exact differences and help us identify the significance of this work.

- Figure 5 which seems to present a very important result of the paper is very hard to read.
    - The paper says: *train and test losses are overlayed on top of the distribution*. I believe it is not the loss but the accuracy. But still it is not clear to me whether the scale of both plots are the same or not. It would be better to add another set of ticks on the right side of the plots.
    - The paper says: *Both original and linearly over-parameterized models first exhibit rank contracting behavior throughout training, and then the rank starts to increase again - to the best of our knowledge, this is an unexpected training behavior in larger models that are not explained in prior works.* \
I cannot read any decrease or increase from the distribution heatmap. It would be best to show the effective rank through out the training.
    - I also do not know what the y-axis is. Is it the indices of the singular values? It is somewhat misleading that those with larger "negative log magnitude" are smaller.

- Finally, the std must be reported in tables 2 and 3 so that allows the reader to know how significant the gains are.

Other minor remarks:
- In Def. 1, it says "Without loss of generality, we drop the exponentiation for convenience." Which exponentiation?
- Throughout the paper, 'p' and 'q' are used to denote to size of dataset while 'n' and 'm' are dimensions. I found it somewhat unconventional.
- On page 3, the paper says: *Since the dimensionality of the Gram-matrix depends on the dataset size, we can compare neural networks with different modeling capacities in the zero training error regime.* \
I found this a bit confusing. I believe the reason is that "it does **not depend** on the number of parameter".

summary_of_the_review: As mentioned above, in summary,

(+) The paper is very well-written and easy to follow.\
(+) The finding are interesting and well supported by the experiments.\
(-) Most of the findings have been discovered before in related work. However, I might have missed something and am looking forward to hearing the authors opinion.
(-) Figure 5 is not clear at all. However, I believe it can be fixed easily and I would like to encourage the authors to modify it.
(+) Depth as a regularizer has been using by practitioners however. Nevertheless, increasing the depth by adding linear layers is still interesting.

Finally, I would like to let the authors know that I am willing to increase my score if the authors could kindly answer the questions above.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper argues that modern deep neural networks are effective in part because they incorporate a bias towards low-rank Gram matrices (where the Gram matrix is the product of the features with themselves).
main_review: By this point, we know quite alot about the biases towards low or high rank in finite and infinite neural networks, and the paper lacks alot of this nuance.

1. A priori, we know that finite width networks do exhibit a lower-rank structure than the corresponding infinite-width network, due to the low-rank bias in the Wishart distribution [1] (Appendix Fig. 5).  But this isn't exactly a point that has been emphasised in past work, so I wouldn't necessarily regard it as novelty-destroying, especially in light of the random matrix theory.
2. Infinite neural networks don't have a bias towards lower rank as they get deeper.  The kernel has a power-law structure which appears to remain consistent with depth [2,3].  
3. Low-rank fixed kernels aren't particularly likely to improve performance (which is why the lack of low-rank kernels in deep infinite neural networks is a good thing).  If the kernel became low-rank, then it assigns high probability only to linear combinations of a few output functions.  If the true function lies outside this class, then we expect poor performance.  Of course, if the true function lies within this class, then we expect a performance boost, but typically that only happens after training.
4. While trained networks indeed appear to have a low-rank bias [3], the bias is really towards the "output Gram matrix" formed by the product of the one-hot labels [3,4].  Typically, (for small label sets) this Gram matrix will be low rank.  But it doesn't have to be, and it doesn't represent a generic bias towards low-rank.  This is much more accurately described as just representation learning [3].

Thus, conjecture 1 requires _alot_ of nuance.  In particular, work comparing finite and infinite networks would lead us to expect a simpler top-layer kernel for a single, fixed, random initialisation of the weights.  But obviously we don't just use a single, fixed, random initialisation of the weights.  If you averaged over many different random initialisations, you'd end up with something much more like the infinite kernel, which isn't low-rank.  And if you trained, you'd drag the top-layer kernel towards the output Gram matrix, which is typically low-rank, but doesn't have to be.

As a final note, if the bias towards the low-rank output Gram matrix is baked into the objective, it is unsurprising that it occurs with any choice of optimiser.

I'd be willing to increase my score if these results are built in to the discussion.

[1] Aitchison, Yang, Ober.  Deep kernel processes.  ICML (2021).

[2] Yang, Salman. A fine-grained spectral perspective on neural networks. arXiv preprint arXiv:1907.10599

[3] Aitchison. Why bigger is not always better: on finite and infinite neural networks.  ICML (2020).

[4] Zavatone-Veth, Canatar, and Pehlevan. "Asymptotics of representation learning in finite Bayesian neural networks." arXiv preprint arXiv:2106.00651 (2021).
summary_of_the_review: Missing the understanding of these issues built up in the infinite neural network literature, and in the literature relating infinite to finite networks.
review_title: null

Meta-review: This paper experimentally investigate the inductive bias of deep neural networks tending to produce low rank embeddings of data, which is important to explain why over-parameterized DNN can generalize. In particular, the paper empirically finds that deeper networks are more likely to produce lower rank embedding through thorough numerical experiments with different network architectures, hyperparameters and so on. The authors also proposed a linear over-parameterization technique to induce low-rank bias and empirically justifies its effectiveness. 

Overall, this paper is well written, and the numerical experiments are carefully executed. However, the main drawback of the paper is that the low-rank inductive bias itself is a well known phenomenon and this paper gives a kind of additional confirmation to it. I acknowledge that there are several differences from existing papers, but overall we see rather limited insight from the results. Indeed, some of existing studies gave theoretical analyses to understand "why it happens", but this paper does not give a sufficiently novel insight to reveal the reason. 

To summarize the decision, this paper lacks deeper insight compared with existing work although the authors did a good job to execute through experiments. Therefore, it is a bit below the acceptance threshold.
Decision: Reject