The Low-Rank Simplicity Bias in Deep Networks
Authors: Minyoung Huh
Hossein Mobahi
Richard Zhang
Brian Cheung
Pulkit Agrawal
Phillip Isola
Venue: Accepted by TMLR ()

Abstract: Modern deep neural networks are highly over-parameterized compared to the data on which they are trained, yet they often generalize remarkably well. A flurry of recent work has asked: why do deep networks not overfit to their training data? In this work, we make a series of
empirical observations that investigate and extend the hypothesis that deeper networks are inductively biased to find solutions with lower effective rank embeddings. We conjecture that this bias exists because the volume of functions that maps to low effective rank embedding
increases with depth. We show empirically that our claim holds true on finite width linear and non-linear models on practical learning paradigms and show that on natural data, these are often the solutions that generalize well. We then show that the simplicity bias exists
at both initialization and after training and is resilient to hyper-parameters and learning methods. We further demonstrate how linear over-parameterization of deep non-linear models can be used to induce low-rank bias, improving generalization performance on CIFAR and
ImageNet without changing the modeling capacity.

Published in Transactions on Machine Learning Research (3/2023)
The Low-Rank Simplicity Bias in Deep Networks
Minyoung Huh MIT CSAIL
minhohh edu
Hossein Mobahi Google Research
kmobahii@ggaaie
Richard Zhang Adobe Research
richang Dadobe. com
Brian Cheung MIT CSAIL & BCS
cheungb@mit. edu
Pulkit Agrawal MIT CSAIL
pulkitag@mil. edu
Phillip Isola
phillipi@mit.ccm edu
MIT CSAIL
Reviewed OpenReview: https: // openreview. net/ forum? id= bC&NWDm1
Abstract
Modern deep neural networks are highly wer-parameterized compared to the data which they are trained, yet they often generalize remarkably well. A flurry of recent work has asked: why do deep networks not overfit to their training data? In this work, we make series of empirical observations that investigate and extend the hypothesis that deeper networks are inductively biased to find solutions with lower effective rank embeddings. We conjecture that this bias exists because the volume of functions that maps to low effective rank embedding increases with depth. We show empirically that our claim holds true on finite width linear and non-linear models on practical learning paradigms and show that natural data, these are often the solutions that generalize well. We then show that the simplicity bias exists at both initialization and after training and is resilient to hyper-paramcters and lcarning methods. We further demonstrate how linear troeeerraaettii of deep non-linear models can be used to induce low-rank bias, improving generalization performance on CIFAR and ImageNet without changing the modeling capacity.
1 Introduction
It has become conventional wisdom that the more layers one adds, the better a deep neural network (DNN) performs. This guideline supported, part, by theoretical results showing that deeper networks can require far fewer parameters than shallower networks to obtain the same modcling "capacity" (Eldan & Shamir, 2016). While it is not surprising that deeper networks that state-of-the-art deep networks do not overfit, despite being heavily wer-parameterized, defies classical statistical theory (Geman et al., 1992; Zhang et al., 2017; Belkin et al., 2019) e.g., Dosovitskiy et al. (2020) trains a 632 million parameter, 200+ layer model, on 1.3 million images.
more expressive than shallower networks, the fact.
The belief that reeeeerromettiiitiioon via depth improves generolization is used axiomatically in the design of neural networks. Unlike conventional regularization methods that penalize model complexity (e.g. f penalty), over-parameterization does not. Yet, like explicit regularization, over-pare parraatterizzaiionn appears to prevent the model from over-fitting (Belkin al., 2018; Nakkiran et al., 2019a). While there has been

---

Published in Transactions on Machine Learning Research (3/2023)
0.08
Deep nets struggle to fit high- rank linear functions: We report the training loss of neural networks of different depths opti- mized to solve linear regression. The rank of the underlying linear function is varied in the range [1, 14,. While shallow networks achieve zero train- ing loss, the training loss worsens with increased depth and task rank (sce Appendix F for training details).
Figure 1:
task rank 1
0.07
task rank 4
training loss
0.06
rank
0.05
task rank
task rank 64
0.04
0.03
0.02
0.01
0.0
10
20
30
40
50
60
number of layers
an extensive effort to analyze the effect of the implicil regalarization of over-paraaeeterizaion on neural networks (sce Section 6), prior investigations have been mostly limited lincar models for thcorctical analysis have been left as an under-explored side observation. This work aims to further the existing efforts by providing extensive empirical experiments and analysis linear and lonerr networks for practical learning paradigms.
Our analysis begins with a non-intuitive observation that pver-parumelerizalion hurls the ability to overfit simple linear functions. We trained ReLU networks with varying depths on a set of linear regression tasks Y W For some randomly sampled X, we minimize the least-squares error between the prediction Y and the ground-truth targets Y. In Figure 1, we plot the converged loss when varying the depth of the model and the underlying rank of the task: rank(W") {1, 16, 32, 64). The results reveal that deeper networks touted for their ability to model complex functions struggle to fit even (high-rank) linear functions. In contrast, shallower networks perfectly minimize the loss.
One explanation of these results is improper optimization of neural network parameters. We used standard SGD based optimizers and experimented with a wide range typer-parametern that we detail in Appendix F. While there may exist an optimization algorithm that can perfectly minimize training error, we do not know of such an optimizer. At first, our result might seem be at odds with the work of Zhang et al. (2017) observing that deep networks (8 layers) can achieve zero training error on random data. However, our results are consistent because Zhang et al. (2017) did not experiment with deeper networks, and predicting labels from images is (loosely speaking) not a full rank prediction problem.
The sccond possibility is our hypothesis that deep over-paramcterized networks are biased to find low effective runk solutions. Results in Figure corroborate this hypothesis, but the problem is that the concept of rank is not defined for a non-linear network. However, it is still possible to study the effective rank of the feature embeddings learned by the penultimate layer of the neural network. In the case of linear neural network, the embedding and parameter rank are equivalent. In the remainder of this work, we probe the relationship between the elfective rank of the embedding and depth. Our findings indeed strengthen the hypothesis that. deeper networks find lower effective rank solutions.
Prior work has shown that over- seee-paramtteizeee linear networks find minimum norm solutions (Gunasekar et al., 2017; Arora et al., 2019a), which in special cases, equivalent to finding low-rank solutions. Valle-Peree et al. (2019) also suggested that deep non-linear networks are "simple functions", but does not make any connection to the depth of the network nor explain why the model would likely converge "simple function". Here, "simple function" is measured by the Lempel-Ziv complexity of the output from randomly initialized boolean network. Our work ties together these two lines of rescarch by investigating how the hypothesis space of the network changes when the network is wver-parameterized with depth. We specifically study the relationship between the rank of the embedding - the effective rank computed on the linear kernel of the network's output features and depth for both linear and non-tinear networks.
The fact that deeper networks are primed to learn solutions that have low effective rank embedding may also explain why they generalize despite being over-parameterized most natural data (e.g., images) actually lies
2

---

Published in Transactions on Machine Learning Research (3/2023)
low-dimensional manifold, and common problems such classification require predicting quantities that are much lower-dimensional than the inputs.
In summary, this work provides a new set of observations that expand the growing body of work on over- parameterization. Mainly, we make a series of empirical observations that indicate deep nets have an inductive bias to find lower rank embeddings.
We observe that deep nets, even at initialization, are biased to map data into low-rank embeddings. We observed this bias to exist after training with gradient descent.
We observe that the bias towards low-rank embeddings exists in a wide variety of common optimizers, even those that do not use gradient descent (c.g., random-scarch).
We find that even if we initialize the networks be low or high rank, the effective rank of the converged solution is largely dependent on the depth of the model.
This set of observations leads us conjecture that deeper networks are implicitly biased to find lower effective rank embeddings because the volume of functions that map to low effective rank embeddings increases with depth.
We leverage obsorvations to demonstrate linear wen-parameteriization by "depth" can be used to achieve better generalization performance on CIFAR (Krizhevsky et al., 2009) and ImageNet (Russakovsky el al., 2015) without increasing modeling capacity.
2 Preliminaries
2.1 Neural networks and Over aueepaaramtttiizaiion
Simple linear network
A simple linear neural network transforms input Rax1 output ÿ e R=x1 with a learnable parameter matrix W Rmxn,
i Wx.
(1)
For notational convenience, we omit the bias term
Over-parameterized lincar networks
One can over-parameteerize a linear neural network by defining d matrices [Wi)d= and multiplying them successively with input
i = WWWWain Wi Wa
(2)
where We = WT= W.. As long as the matrices are of the correct dimensionality matrix Wa has m columus, W1 has rows, and all intermediate dimensions (dim(W.)) 2 min(m, n) then this parameterizationn expresses the same set of functions as single-layer network. We disambiguate between the collapsed and expanded set of weights by referring to {W;} as the over- peeepearaeeeri weights and We as the end-to-end or the effective weights.
Non-linear networks
For non-linear network, activation function & (e.g. ReLU) is interleaved between the weights:
Wab (Wi
(3)
In contrast to linear networks, non-linear models become more expressive as more layers are added.
2.2 Effective rank
We characterize the rank of matrix using a continuous measure known as the effective rank:
3

---

Published in Transactions on Machine Learning Research (3/2023)
linear network
non-linear network (ReLU)
normal distribution
uniform distribution
normal distribution
uniform distribution
unnormalized mazdalzee P(o(k)
30
30
30
30
25
20
20
20
20
15
15
15
10
10
10
10
5
1.0
1.2
1.4
1.6
2.0 2.2
1.0 1.2
1.4
1.6
1.8
2.2
1.0 1.2
1.6
1.8
2.0 2.2
1.0 effective rank p(K)
1.2
1.4
1.8 2.0 2.2
effective rank p(K)
effective rank p(K)
effective rank p(K)
depth!
depth
depth
depth
depth
The approximated probability density function (PDF) of the effective rank over the Gram matrix is computed from features of the networks. The Gram matrix is computed with 256 random inputs, and we use 4096 network parameter samples to approximate the cumulative distribution function. The CDF is used to compute the PDF via the finite difference method. We apply Savitzky & Golay (1964) filter to smoothen out the approximation. There exists more probability mass for lower effective rank embeddings when adding more layers. The experiment is repeated for both normal and uniform distributions. For linear networks, the effective paramcters are fixed across depth, while for non-linear networks, this is not the case.
Figure 2:
Deep networks are biased toward low effective rank:
Definition 2.1 (Effective rank). (Roy & Vetterli, 2007) For any matrir A Rm*x, the effective rank p is defined as the Shannon entropy of the normalized singular volues:
min(n.m)
p(A) =
Σ 2=1
of log((),))
where o, =, are normalized singular values, such that o; =1 1. Also referred to as the spectral entropy. Without loss of generality, we drop the exponentiation for convenience.
This measure gives a meaningful representation of "continuous rank", which is maximized when the magnitude of the singular values are all equal and minimized when a single singular value dominates relative to others. The effective rank provides us with a metric that summarizes the distribution envelope. Effective rank has been used prior works (Arora et al., 2019a; Razin & Cohen, 2020; Baratin et al., 2021) and we use this measure extensively throughout our work. We have also found that our observations are consistent with the closest definition of rank in which we threshold the smallest singular values after normalization (Appendix D).
2.3 Embedding maps
A parameteric function f(w) E Fw is neural network parameterized with set weights (W) (W1.... Wal that maps the input space to the output space X' + V. For dataset of size g, the input and output data is X E gaxg and Y E Rmxq, Then, the predicted output is = Wav(4)= f(w)(X, where & E 18 xg is the last-layer embedding and Wa e poxn' is the last layer of the network.
We analyze the embedding space by computing the effective rank the Gram Gram/kernel matrix K E Rexp where is the size of the test set. The ij-th entry of the Gram matrix corresponds to distance kernel Kgj k(d;, Φj) where o; corresponds to the i-th column of 4. We use the model's intermediate features before the linear d.e?"
classifier and use cosine distance kernel: k(Ø,, 03) |To. || a common method for measuring distances in feature space (Kiros al., 2015: Zhang et al., 2018). We observed our findings be consistent with other common choices of dot-product distance functions such linear kernels and correlation kernels (Appendix D).
4

---

Published in Transactions on Machine Learning Research (3/2023)
Figure 3: Distribution of non-linear nets at convergenee: Rank distribution after training the network to zero-training error with gradient descent. The dotted line indicates the initial dis- tribution, the solid line indicates the converged distribution, and the green line indicates the task rank. Despite all models having the same func- tional capacity, the model's ability to find the underlying solution depends on the original pa- rameterization of the network. Despite all models achieving zero-training error, models of different depth recover different underlying solutions. In this experiment, the model with depth of or 8 finds a better generalizing solution on held-out set than models with more fewer layers.
unnormalized P(p(k)
16
depth
14
depth 2
12
depth
10
depth 8
8
depth 16
4
2
0.5
1.0
1.5
2.0
2.5
effective rank p(K)
The dimensionality of the Gram-matrix depends the data samples and does not depend on the model parameters. For non-linear networks, we make comparisons at the zero training error regime.
Gram matrices are often used to analyze the optimization and generalization properties of neural net- works (Zhang et al., 2019; Du et al., 2018; 2019; Wu et al., 2019; Arora et al., 2019b). In natural data, it is often assumed that we are trying to discover a low-rank relationship between the input and the label. For example, a model that overfits every training sample without inferring any structure on the data will generally have test gram-matrix that higher rank than that of model that has learned parsimonious representations. A lower rank held-out data indicates less excess variability and is indicative of studying generalization and robustness. The intuition becomes clearer in linear networks since the rank of the Gram matrix depends on the rank of the lincar transformation computed by the network. We illustrate this empirically in Appendix L, where we see that there is light relationship ionship between the effective-rank of the linear weight matrix and the effective-rank the resulting Gram matrix.
2.4 Least squares
Given a dataset X, Y generated from W the goal is to regress a parameterized function f4wy() to minimize the squarod--istance (W(W)() 100--ypp Y The rank(W") is a mcasure of the "intrinsic dimensionality" of the data, and we refer to it as the lask rank. In this work, we exclusively operate the under-determined regime where we have fewer training examples than model parameters. This ensures that there is more than one minimizing solution.
3 The parameterization bias of depth
Given that models can always fit the data, what the implications of scarching for the solution in the over-parameterized model? In linear models, this is equivalent to searching for solutions in (W.) versus directly in W.. One difference is that the gradient direction ((W.))((W.)) is usually different than Vw.C(W, for a typical loss function L (see Appendix J). The consequences of this difference have been previously studied in linear models by Arora et al. (2018; 2019a), where the over- over-parameterized update rule has been shown to accelerate training and encourage singular values to decay faster, resulting in low nuclear-norm solution. Here we motivate result from the perspective of parameter volume space.
Conjecture 3.1. Deeper networks have greater proportion of parameter space that maps the inpul dala to lower-rank embeddings; hence, deeper models are more likely to converge to functions that learn simpler embbediigg.
We now provide a of empirical observations that supports our conjecture. Our work and existing theoretical works gradient descent. biases are not mutually exclusive and likely complement. We emphasize that.
5

---

Published in Transactions on Machine Learning Research (3/2023)
linear
tanh
relu
leaky relu
selu
gelu
siren
22-
siren
ralu
2
2.1
solu
looky rolu
linear
effective rank
2.0
gelu
16 depth
4
188
1.7
1.6
1.-
2
depth
Figure 4: Gram matrices of networks: Gram matrices of neural networks trained with various non- linearities and depth. Since increasing the number of non-lineat layers increases the functional expressivity of the network, the Gram matrix is computed using the cosine distance on the features of the test set near zero-training loss. Increasing the number of layers decreases the effective rank of the Gram matrix on a variety of non-linear activation functions. The Gram matrix is hierarchically clustered (Rokach & Maimon (2005)) for visualization. We observe the emergence of block structures in the Gram matrix as we increase the number of layers, indicating that the embeddings become lower rank with depth.
we do not make any claims on the simplicity of the function, but only on the simplicity lower effective rank of the embeddings.
3.1 Low-rank simplicity bias of deep networks
Observation 3.1. Randomly initialized deep nets are biased to correspond to Gram matrices with a low effective rank.
When sampling random neural networks, both linear and non-linear, we observed that the Gram matrices computed from deeper networks have a lower effective rank. We quantify this observation by computing the distribution over the effective rank the Gram matrix Figure 2. Here, the weights of the neural networks are initialized using uniform W; ~ U(s:) or Normal distributions W, N(..). The input, output, and intermediate dimensions are 32, giving parameters (W,) E Rdx32x32 for a network with d layers. We draw 4096 random parameter samples and compute the effective rank on the resulting Gram matrix. We see that the distribution density shifts towards the left (lower effective rank) when increasing the number of layers. These distributions have a small overlap and senothen out with increased depth. This observation shows that depth correlates with lower effective rank embeddings.
The low-rank bias becomes more intuitive in linear models as there is a simple way to relate the Gram matrix to the weights of the model K x () X).. Intuitively, if any constituent matrices are low-rank, then the product of matrices will also be low-rank the product of matrices can only decrease the rank of the resulting matrix: rank(AB) I min (rank(A), rank(B)) (Friedberg et al., 2003). In Appendix L, show that the depth of the model increases, both the effective rank of the Gram matrix and the weights decrease together. Another way to interpret our obsorvation is that for linear models, weerpaarameterization does not increase the expressivity of the function but re-weights the likelihood of a subset of parameters the hypothesis class. For non-linear models, we cannol make the same claims.
Although uniform sampling under the parameter distribution an unbiased estimator of the volume of the parameter space, is certainly possible that a sub-space of the parameters more likely to be observed under gradient descent. Hence, by naively sampling networks, may never encounter model parameters

---

Published in Transactions on Machine Learning Research (3/2023)
that gradient descent explores. In light of this, we repeat our experiment above by computing the PDF on randomly sampled parameters after taking n gradient descent steps.
Observation 3.2. Deep neural networks trained with gradient descent also learn to map dala to simple embedding with low effective rank.
Figure 3 illustrates the change in distribution as we train our model to convergence using gradient descent. Each randomly drawn network sample is trained to minimize the least-squares error. The initial distribution is plotted with dotted lines, and the converged distribution is plotted with solid lines. As the model is trained, the distribution of the rank shifts towards the ground-truth rank (green line) but is constrained by the depth of the model. We highlight that while the observation would have been trivial and expected if the model recovered the exact ground-tuuth rank at zero-trainin vero-training error. However, the surprising observation is that even if these models achieved zero-training error, the effective rank of the recovered solution depends on the depth of the network deeper models find lower effective rank solutions, implying that generalization properties would vary based on the parameterization of the models. Since the observed bias stems from the model's parameterization, the same bias must also exist under other common and natural choices of optimizers. We investigate this claim in the next section.
In Figure 4, we further visualize the learned Gram matrices when varying the depth of the model. The Gram matrices trained with various non-linear activation functions also emit the same low-rank simplicity bias. These activation functions include standard functions such as ReLU and Tanh as well as recently popularizod non-linear functions such as GeLU ((Hendrycks & Gimpel, 2016)), and the sinusoidal activation function from SIREN ((Sitzmann et al., 2020)). By hierarchically clustering (Rokach & Maimon, 2005) these Kernels, we can directly observe the emergence of block structures in the Gram matrices as we increase the number of layers, implying that the embeddings become lower rank with depth.
3.2 Is the low-rank bias specific to gradient descent?
Observation 3.3. Deep neural networks trained with common and natural choices of optimizers also exhibit the low-rank embedding bias.
The low-rank bias of deep networks has been primarily studied under the context of first-order gradient decent (Arora et al., 2018; 2019a): how and why does gradient descent converye to low nuclear norm solution. In contrast, our conjecture focuses on the bias of parameterization of the network and not on the bias introduced by the gradient descent. Since parameterization bias exists regardless of the optimizer choice, we would expect to observe the low-rank simplicity bias on a wide range of optimizers. We dircctly show this in Figure 5 by ablating across various popular choices of optimizers on least-squares with linear networks. Here, we compare against Nesterov (Nesterov (1983); momentum), ADAM (Kingma & Ba (2015); hessian approximator), L-BFGS (Liu & Nocedal (1989); second-order), CMA-ES (Hansen et al. (2003); evolutionary- search), and random scarch. All models were trained to zero training error except for random search. For random search, we randomly initialize the network 100, 000 times and take the best performing sample. As we have seen with gradient descent, the experiment indicates that even when we train with a wide suite of commonly used optimizors, the solution obtained by these models depends on how the model was originally parameterized.
3.3
Can the bias be explained solely by initialization?
The previous set of experiments indicates that deeper networks are biased towards low effective-rank embedding at both initialization and convergence. In these experiments, the random settings of neural networks had different initial distributions. This happens because, even if the individual weights are normally distributed, the weights constructed from a series of matrix multiplications result in a distribution that has a high density around zero. For example, the product of normally distributed weights becomes symmetric x-squared distribution, with degrees of freedom. Hence, one could argue that the converged solutions have low effective rank because of the initialization bias.
7

---

Published in Transactions on Machine Learning Research (3/2023)
effective rank @ convergence
dapth
depth
depth 4
dapth
Low-rank bias & optimizers: Least-squares trained on linear neural networks using various optimization methods, The rank of the converged Gram matrix is correlated with the depth of the network. The experiment re- peated times. Except for Random Search, all models achieve O training loss. While the solution achieved depends on the optimizer, the underlying low-rank bias of depth persists across optimizers and is not specific to gradient descent. All models have the same functional expressivity.
Figure 5:
3.4
3.2
2.8
2.6
2.4
2.2
1.8
sgd
nesterov
lofgs
cma-ees random
optimizers
search
default initialization
low-rank initialization
text
ras
converped
2042
trah
In tallattio
convereed
effective rank
offecttvve rank
0.2
02
loss
loos
1.0
15
depth
depth
depth
depth
Figure 6: Bias of parameterization: The effective rank of the Gram matrix from initialization convergence on various depth. For each depth, we train linear network using gradient descent on least squares regression. We repeat our experiments 5 times with different seeds, and we report the median of these runs. The rank at initialization and convergence is indicated by white and colored dots, respectively, For deeper models, the effective-rank is lower at initialization because the product of normally distributed weights is no longer normally distributed. On the right, we initialize the networks with the same low-rank distribution weights as the 32-layer model. We observe that shallower networks tend to converge to higher rank embeddings. All models in this experiment have the same functional expressivity. While it may seem that non-zero training error at high-depth is under-fitting due to poor optimization choices, we exhaustively search the optimization hyper-parameters. We list. the optimization choices in the A.
Observation 3.4. Deep neural networks are biased towards learning low effective- embeddings and are insensitive to initialization.
To test whether the initialization of the model affects the effective rank of the converged solution. We optimize our network W E [dx32x32 on least-squares where the task-rank is set to 24. All models are trained for 4000 epochs using gradient descent, and the best learning rate is chosen for each depth. In Figure (left), for models using default initialization, we show that increasing the number layers decreases the effective rank of the Gram matrix at convergence. We repeat the experiment in Figure (right) by initializing the over-parameterized models with the distribution associated with the 32-layer linear network. Following similar trend to that of default initialization, observe that deeper models learn embeddings that are lower effective rank than the shallower counterparts Although initialization is not insignificant, we see that the depth of the model has light control over the solution which the model explores. For deeper net works,,, the majority of the parameter volume mapped to low effective rank embedding (Observation 3.1), and therefore is expected that a typical scarch algorithm would likely encounter paramcters that map to low effective rank embeddings regardless of initialization. Similarly, for a shallower network, it would be casier find a solution with higher effective rank embeddings.
8

---

Published in Transactions on Machine Learning Research (3/2023)
3.4 Relation to random matrix theory
In linear models, we have special case in which the low-rank embedding corresponds to low-rank weights. This enables us to make natural connection to existing theoretical work from random matrix theory (RMT), which studics the spectral distribution under matrix multiplications (Akemann et al., 2013a;b; Burda et al., 2010). We leverage the results from (Pennington et al., 2017; Neuschel, 2014) to show the following:
Theorem 3.1. Let be the effective rank measure defined in Definition 2.1. For linear neural network with d d-layers, where the parameters are drawn from the same Normal distribution {W.) ~ W, the effective rank of the weights monolonically decreases when increasing the reamber of layers when dim(W) + 00
P PWWdWa1....Wy W1) PWWo-.... ...)
Proof. See Appendix H.
Given the current set of mathematical tools, our preliminary theory depends on many assumptions, such infinite width networks and the distribution of the weights; this is akin to many existing theoretical works. Yet, we have observed in practice that the empirical spectral distribution of finite-width models is well approximated by random matrix theory (see Appendix B) in practice. We emphasize that the main contribution of our work is on the empirical theory of the low-rank bias of deep networks; nonetheless, we show that there is a natural theoretical connection to RMT in hopes of stimulating future works.
4 Over-paaametterizaton as a regularizer
Thus far, we have observed that depth acts as a bias for finding functions with low effective rank embeddings. As one could imagine, this inductive bias of depth could be used to help but also hurt generalization performance. Our observations indicate that the low-rank simplicity bias helps when the true function we are trying to approximate is low-rank. On the contrary, if the underlying mapping is high-rank the network is made too deep, depth could have a converse effect generalization. Ample evidence from prior works (Szegedy et al., 2015; He et al., 2016) suggests that over-paramett parameterriiziionn of non-linear models improves generalization on fixed datasets, but blindly increasing the number of layers without bells & whistles (e.g., batch-norm, residual connection, etc.) hurts (He et al., 2016).
Fortunately, networks are trained on natural data, where often the goal is to discover a low-rank relationship between the input and the label. Hence, the inductive bias of depth acts prior rather than bug. As noted by Solomonoff (1964) theory of inductive inference, the simplest solution is often the best solution, suggesting that low-rank mapping in neural nelworks can be used to improve generalization and robust.nss to overfitting. However, increasing the number of non non-linear layers also increases the modeling capacity, thereby making it difficult to isolate the effect of depth.
Neverth since a non-linear network is composed of many linear components, such as fully connected and convolutional layers, we can over-parameterize these linear layers to induce a low-rank bias in the model without increasing the modeling capacity. The details of our linear preeraarrtttttiitiionn method are in Appendix C. We observe that such linear over parametrrization improves generalization performance classification tasks. Furthermore, we find that such implicit regularization outperforms models trained with several choices of explicit regularization. Guo et al. (2020) made similar empirical observation in the context of model compression where linear over- over-parameterizatioo improves generalization, but why it works is unexplored.
4.1 Image classification with over-parameterization
Using the linear expansion rules in Appendix C, we over- paramearaeteriiee various architectures and evaluate on a suite of standard image classification datasots: CIFAR10, CIFAR100, ImageNet. All models are trained using SGD with momentum of 0.9. For data augmentation, we apply a random horizontal flip and random-resized crop. We follow standard training procedures and only modify the network architecture (see Appendix F).
9

---

Published in Transactions on Machine Learning Research (3/2023)
original
over-parameterized
1.0
1.0
aemmyBeu Boj angefou
singular values
0.5 accuracy
0.5
18
accuracy
rrccheuuer
0.0
0256
0258
0
30
60
90
120
150
180
0
30
60
90
120
150
180
training epochs
training epochs
Figure Training dynamics: Singular values of the Gram matrix for both original (left) and linearly wwer-parameterized (right) model throughout training. The models are trained on CIFAR100 using SGD. Since the first few singular values dominate the distribution, we plot the negative log magnit ude of the normalized singular values to better visualize how the intermediate singular values change. The singular values sorted from largest to smallest o; 0i+1 (top to bottom in the figure) where blue means large and red means small. The original and the wee-parameterizee models are functionally equivalent and use the same colorbar and scale. The dotted lines (--) indicate the learning step schedule, and train and test accuracies are overlayed on top of the distribution. The werrparameterized model learns lower rank embedding and exhibits less overfitting, and has better gencralization. See Figure 14 and Figure 15 in the Appendix for the dynamics of the individual weights.
In Figure 7, we compare CNN trained without (left) and with (right) our over- over-param pree-paramtterization (expansion factor d = 4) on CIFAR100. The CNN consists of convolutional layers and 2 fully connected layers; the architecture details are in Appendix F. We overlay the dynamics of the singular values of the Gram matrix throughout training. The spectral distribution is normalized by the largest singular value and are sorted in descending order (A) 2 (A) for i S min(m,,)) We observe that both the individual effective weights and the Gram matrix of the over-parameteriied model is biased towards low-rank weights. Unlike the original, the majority of the singular values of the wee-paarmeteriieed model are close to zero. When we take closer look at the weights of the model, both the original and linearly over-parameeterized models first exhibit effective rank contracting behavior throughout training, and then the effective 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, possibly because the isometric, balanced initialization, and infinitesimal assumptions made in prior theoretical works do not hold in practice (visualized in Appendix E).
We further quantify the gain in performance from linear wve-pparameterizationn in Table 1. The learning rate is tuned per configuration, and report the best test accuracy throughout the training. We try various wwer-parameterizatoon configurations and find an expansion factor of 4 to be the sweet spot, with gain of +6.3 for CIFAR100 and +2.8 for CIFAR10. The optimal expansion factor depends on the depth of the original network, and in general, we observe a consistent improvement for weerparameterizing models with 20 layers on image classification.
We scale up our experiments to ImageNet, large-scale dataset consisting of 1.3 million images with 1000 classes, and show that our findings hold in practical settings. For these experiments, architectures: AlexNet (Krizhevsky et al,, 2012) which consists of 8-layers, and ResNet10 / ResNet18 (He et al., 2016) which consists of 10 and 18 layers, respectively. If our prior observations hold true, we would expect the gain in performance from over-parameetrriation to be reduced for deeper models. This is, in fact, what we observed Table 3, with moderate gains in AlexNet and less for ResNet10 and even less for ResNet18. In fact, starting from ResNet34, we observe lincarly over-pan wer-parameterized models perform worse than the original. These experiments support our claim that adding too many layers can over-pent per-penaliiz the model.
standardized
10

---

Published in Transactions on Machine Learning Research (3/2023)
Expansion
CIFARIO
CIFAR100
Over-parammeteriattoo ablations: A nonlinear CNN with 4 convolution and 2 linear lay- ers trained on CIFAR10 and CIFAR100 with various degrees of linear over-parameterization As have observed with least-squares experiments, there is in- deed a sweet spot of depth that is best for general- ization. Here we see that linear-vverprramttriaatt by 4x performs the best. All models are function- ally equivalent and have the same effective number of parameters.
Table 1:
Factor
FC
Conv
Becuracy
gain
accuracy
gain
x1
86.9
57.0
82
87.1
T0.2
58.4
FT.4
x2
87.8
+0.9
61.0
+4.0
X2
89.1
+2.2
61.2
+4.22
X4
87.3
10,4
50.7
T2.7
x4
89.1
+2.2
61.3
+4.3
89.0
+2.1
63.5
+6.5
X8
83.9
-1.00
55.8
F18
x8
88.5
+1.6
61.6
+4.6
x8
88.0
+1.1
61.5
+4.5
CIFAR10
CIFARI00
Table 2: Explicit regularizers: Com- parison of models trained with vari- ous regularizers. While explicit low- rank regularizers all result in improved performance, lincar won-parameterized
regularization
neruracy
gain
aceutary
gain
(baseline)
$6.9
37.0
low-rank initialization
86.8
-0.1
37.2
+0.2
Eg norm
87.2
+0.3
37.0
+0.0
f1 norm
87.4
10.5
60.0
+3.0
nuclesar nörin
87.0
FO.1
38.1
FC1
deep networks consistently outperform explicit regularizers. The accuracy is computed over the average of runs. In- dividual runs have < 0.3% variability in the test performance. All models have the same effective number of paramcters.
effective rank
$6.9
+0.00
37.2
+0.2
stable rank Sonyal et al. (2019)
87.6
+0.9
58.3
+133
frobenius norm Yoshida & Miyato (2017)
87.0
+0.1
59.2
+2.2
over-param (x2)
89.1
+2.2
61.2
+42
over-param [x2) f2
+2.7
over-param (x2) 4
89.7
+288
63.3
+6.3
To find out whether explicit regularizers can approximate the advantages of rre-parameterrzation, we directly compare the performance in Table 2 CIFAR. These regularizers include popular ( and lz norm-based regularizers and commonly-used pseudo-measures of rank. These pseudo-measures of rank, such as effective rank and nuclear norm, require one to compute the singular value decomposition, which is computationally infeasible on large-scale models. Although we found explicit rank regularizers to help, we observed over- paramoterization to outperform models trained with explicit regularizers. Morcover, we found that combining norm-based regularizers with over-parameterization further improves performance. This discrepancy between implicit and explicit regularization may stem from the fact that over- over- pree-aarmetttiiztiinn receives a combined effect of both gradient descent's 's implicit bias and model parameterization' 'ss inductive bias. Therefore, explicit regularizer correctly. Another
may need to jointly consider both biases approximate its effect reason could be that regularizers are inherently different than par-aaaatttrizaiionn (Arora et al., 2018). For example, a model trained with a regularizer will have non-zero gradient, even at zero training loss, while the over-parametent model will not.
5 Discussion
One of the main ingredients in any machine learning algorithm is the choice of hypothesis space: what is the set of functions under consideration for fitting the data? Although this is a critical choice, how the hypothesis space also parometerized matters. Even two models span the same hypothesis space, the way we parameterize the hypothesis space can ultimately determine which solution the model will converge recent work has shown that networks with better neural reparamcterizations can find more effective solutions (Hoyer et al., 2019). The automation of finding the right parameterization also has relationship to neural architecture search (Zoph & Le, 2017), but architecture search typically conflates the search for better hypothesis spaces with the search for better parameterizations of a given hypothesis space. In this work, we have explored just one way of reparameterizing neural nets stacking linear layers which does not change the hypothesis space, but many other options exist (see Figure 10 and a short extension to residual networks Appendix 1). Understanding the biases induced by these reparameterizations may yield benefits in model analysis and design.
We encourage the readers to look at the appendix for additional experiments and FAQs
11

---

Published in Transactions on Machine Learning Research (3/2023)
ImageNet over-param
Table 3: ImageNet: We show on existing architec- tures that linear prrrpparamttrttzation can improve generalization performance. The perrpaarameterized models have the same number of effective parameters compared to the original. The benefit plateaus when using deeper models. We did not see a noticeable improvement starting from ResNet33.
architecture
original
gain f
AlexNet [saayers = 8) (x2)
57.3
59.1
+1.8
ResNet10 MMayers 10] (x2)
62.8
63.7
+0.9
ResNet18 [Mayrrs 18] (x2)
67.3
67.7
+0.4
6 Related works
Linear networks Linear networks have been used in lieu of non-linear networks for analyzing the generalization capabilities of deep nets. These networks have been widely used for analyzing learning dynamics (Saxe et al., 2014) and forming generalization bounds (Advani et al., 2020). Notable work from (Arora et al., 2018) shows that over parameterrriiinnnn induces training acceleration which cannot be approximated by an explicit regularizer. Furthermore, (Gunasckar al., 2017) shows that lincar models with gradient descent converge to a minimum nuclear norm solution on matrix factorization. More recently, (Li et al., 2020) demonstrated that gradient descent acts as greedy rank minimizer in matrix factorization, and (Bartlett et al., 2020; 2021) argues that gradient descent in parrpaaamtteried models leads to benign overfitting. Although mainly used for simplifying theory, (Bell-Kligler et al., 2019) demonstrate the practical applications of deep linear networks.
Low-rank bias Deep linear neural networks have been known to be biased towards low-rank solutions. One of the most widely studied regimes on matrix factorization with gradient descent under isometric assumptions (Tu et al., 2016; Ma et al., 2018; Li al., 2018), and further studied on least-squares (Gidel et al., 2019). (Arora et al., 2019a) showed that matrix factorization tends to low nuclear- norm solutions with singular values decaying faster in deeper networks. Complimentary to the analysis of wee-parametteizzttinn there has been theoretical work focused on understanding the aligument of gradients in deep networks. Mainly, the works of (Ji & Telgarsky, 2018; 2020) demonstrate that deep networks, under exponential loss, result in low-rank gradients. Note that the aforementioned works focus on why gradient descent finds low-rank solutions. (Pennington et al., 2018) showed that the spectral distribution of the input-output Jacobian is determined by depth. For non-linear networks, understanding the biases has been mostly empirical, with the common theme that over- parametrrization of depth or width improves generalization (Neyshabur et al., 2015; Nichani et al., 2020; Golubeva et al., 2021; Hestness et al., 2017; Kaplan et al., 2020). These aforementioned theories have also been adopted for auto-encoding (Jing et al., 2020) and model compression, (Guo et al., 2020). The notion of low-rank bias has some relevance to observations that deep features of similar classes have an inductive bias to be mapped to similar classes Oyallon (2017). More recently, (Pezeshki et al., 2020) have observed that SGD learns to capture statistically dominant features, which leads to learning low-rank solutions, and (Baratin et al., 2021) observed that the alignment of the features acts as an implicit regularizer during training.
Simplicity bias Recent work has indicated that gradient descent in linear models finds max-margin solutions (Soudry et al., 2018; Nacson al., 2019; Gunasekar al., 2018). Separately, in the perspective of algorithmic information theory, (Valle-Perez et al., 2019) demonstrated that deep nets' parameter space maps to low-complexity functions. Yang & Salman (2019) extends this observation beyond ReLU networks by analyzing the spectral distribution of the NTK/CK, Furthermore, (Nakkiran et al., 2019b), and (Arpit et al., 2017) have shown that networks learn in stages of increasing complexily. Whether these aspects of simplicity bias are desirable has been studied by (Shah et al., 2020).
Complexity measures A growing number works have found matrix norm to not be a good measure for characterizing neural networks. (Shah et al., 2018) shows that the minimum norm solution is not guarantcod to generalize well. These findings are echoed by (Razin & Cohen, 2020), which demonstrates that implicit regularization cannot be characterized by norms and proposes rank as alternative measure.
12

---

Published in Transactions on Machine Learning Research (3/2023)
References
Advani, M. S., Saxe, A. M., and Sompolinsky, H. High-dimensional dynamics of generalization error in neural networks. Newral Networks, 132:428 446, 2020.
Aitchison, L. Why bigger is not always better: on finite and infinite neural networks. In International Conference on Machine Learning, pp. 156-164. PMLR, 2020.
Aitchison, L., Yang, A., and Ober, S. W. Deep kernel processes. In International Conference on Machine Learning, pp. 130 140. PMLR, 2021.
Akemann, G., Ipsen, J. R., and Kieburg, M. Products of rectangular random matrices: singular values and progressive scattering. Physical Review E, 88(5))052118, 2013a.
Akemann, G., Kieburg, M., and Wei, L. Singular value correlation functions for products of wishart random matrices. Journal of Physics A: Mathemalical and Theoretionl, 46(27))275205, 2013b.
Arora, S., Cohen, N., and Hazan, E. On the optimization of deep networks: Implicit acceleration by overparameteriiaaton. In ICML, 2018.
Arora, S., Cohen, N., Hu, W., and Luo, Y. Implicit regularization in deep matrix factorization. Advanees in Neural Information Processing Systems, 32, 2019a.
Arora, S., Du, S., Hu, W., Li, Z., and Wang, R. Fine- sine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp- 322 332. PMLR, 2019b.
Arpit, D., Jastrzebski, S., Ballas, N., Krueger, D., Bengio, E., Kanwal, M. S., Maharaj, T., Fischer, A., Courville, A., Bengio, Y., et al. A closer look at memorization in deep networks. In International Conference on Machine Learning, pp. 233-242. PMLR, 2017.
Baratin, A., George, T., Laurent, C., Hjelm, R. D., Lajoie, G., Vincent, P., and Lacoste-Julien, S. Implicit regularization via ncural feature alignment. In International Conference on Artificial Intelligence and Slatistics, pp. 2269 2277. PMLR, 2021.
Bartlett, P. L.,, Long, P. M., Lugosi, G., and Tsigler, A. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(4)):0003330077 2020.
Bartlett, P. L., Montanari, A., and Rakhlin, A. Deep learning: a statistical viewpoint. ar preprint UrXiv:2103.09177 2021.
Belkin, M., Hsu, D., Ma, S., and Mandal, S. Reconeiling modern machine learning practice and the bias-variance trade-off. arXiv preprint arXiv:1812.11118 2018.
Belkin, M., Hsu, D., Ma, S., and Mandal, S. Reconciling modern machine-learning practice and the classical bias variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849 15854, 2019.
BligeKligler, S., Shocher, A., and Irani, M. Blind super-resolution kernel estimation using an internal-gan. In Advances Newral Information Processing Systems, 2019.
Burda, Z., Jarosz, A., Livan, G., Nowak, M. A., and Swiech, A. Eigenvalues and singular values of products of rectangular gaussian random matrices. Physical Review E, 82(6):061114,, 2010.
Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 words: Transformers for image recognition at scale. Xrviv preprint 2010 11929, 2020.
Du, S., Lee, J., Li, H., Wang, L., and Zhai, X. Gradient descent finds global minima of deep neural networks.
Tn International Conference on Machine Learning, pp. 1675-1685. PMLR, 2019.
13

---

Published in Transactions on Machine Learning Research (3/2023)
Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes verrparametterized neural networks. arXiv preprint 1rxix:1810002000 2018.
Eldan, R. and Shamir, O. The power of depth for feedforward neural networks. In Conference on learning theory, pp. 907 940. PMLR, 2016.
Friedberg, S., Insel, A., and Spence, L. Linear Algebra. Featured Titles for Lincar Algebra (Advancod) Series. Pearson Education, 2003. ISBN 9780130084514. URL https://books google com/books?id ?id= HCUUADAAIAAJ.
Geman, S., Bienenstock, E., and Doursat, R. Neural networks and the blas/variance dilemma. Neural computation, 4(1):1 58, 1992.
Gidel, G., Bach, F., and Lacoste-Julien, S. Implicit regularization of discrete gradient dynamics linear neural networks. In Advonces in Neural Information Processing Systems, pp. 3202-3211, 2019.
Golubeva, A., Neyshabur, B., and Gur-Ari, G. Are wider nets better given the same number of parameters? In International Conference Learning Representations, 2021.
Goodfellow, 1. J., Vinyals, O., and Saxe, A. M. Qualitatively characterizing neural network optimization problems. International Conference on Learning Representations, 2015.
Gunasekar, S., Woodworth, B. E., Bhojanapalli, S., Neyshabur, B., and Srebro, N. Implicit regularization in matrix factorization. In Advances in Neurol Information Processing Systems, pp. 6151-6159, 2017.
Gunasekar, S., Lee, J. D., Soudry, D., and Srebro, N. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9461-9471, 2018.
Guo, S., Alvarez, J. M., and Salzmann, M. Expandnets: Linear over-paramettrization to train compact convolutional networks. In Advances in Neural Information Processing Systems, 2020.
Hansen, N., Müller, S. D., and Koumoutsakos, Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary computalion, 11(1):1-18, 2003.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Hendryeks, D. and Gimpel, K. Gaussian error lincar units (gelus). arXiv preprint arXiv:1606.cm 2016.
Hestness, J., Narang, S., Ardalani, N., Diamos, G., Jun, H., Kianinejad, H., Patwary, M., Ali, M., Yang, Y., and Zhou, Y. Deep learning scaling is predictable, empirically. arXiv preprint arXi::1712.0044 2017.
Hoyer, S., Sohl-Dickstein, J., and Greydamus, S. Neural reparameterizztion improves structural optimization. arXiv preprint Xiv: 1909.000000 1909.04240. 2019.
loffe, S. and Szegedy, C. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
Ji, Z. and Telgarsky, M. Gradient descent aligns the layers of deep lincar networks. arXiv preprint 2018.
Ji, Z. and Telgarsky, M. Directional convergence and aligmment in deep learning. Advances in Neural Information Processing Systems, 33:17176-17186, 2020.
Jing. I.., Zbontar, J., et al. Implicit rank-minimizing autoencoder. In Advances in Neural Information Processing Systems, volume 33, 2020.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. Xixio preprint or orXi::2001.088 008361, 2020.
14

---

Published in Transactions on Machine Learning Research (3/2023)
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In Bengio, Y. and LeCun, Y. (eds.), 3rd International Conference on Learning Representations, TCLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http://arxiv.on httgg/////11.//////////
http:p///arav..orggaaa///...... 6980.
Kiros, R.,, Zhu, Y., Salakhutdinov, R.,, Zemel, R. S., Torralba, A., Urtasun, R., and Fidler, S. Skip-thought vectors. In Advances in Nearal Information Processing Systems, 2015.
Krishevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
Krizhevsky, A., Sutskever, L., and Hinton, G. E. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Li, Y., Ma, T., and Zhang, H. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning Theory, pp. 2-47. PMLR, 2018.
Li, Z., Luo, Y., and Lyu, K. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint XrXiv:2012. 09839, 2020.
Liu, D. C. and Nocedal, J. On the limited memory bigs method for large scale optimization. Mathematical programming, 45(1):503-528, 1989.
Ma, C., Wang, K., Chi, Y., and Chen, Y. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pp. 2345-3354. PMLR, 2018.
Mises, R. and Pollaczek- Dollacze--Gerrinerr, H. Praktische verfahren der gleichungsauflösnng ZAMM-Journal of Applied Mathemalics and Mechanics /eeiiss//Ziiiliiiiie für Angewandle Mathematik und Mechanik, 9(1):58 77, 1929.
Montavon, G., Braun, M. L., and Müller, K.-R. Kernel analysis of deep networks. Journal of Machine Learning Research, 12(9), 2011.
Nacson, M. S., Lee, J., Gunasekar, S., Savarese, H. P., Srebro, N., and Soudry, D. Convergence gradient descent on separable data, In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3420 3428. PMLR, 2019.
Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B., and Sutskever, Deep double descent: Where bigger models and more data hurt. arXiv preprint arXio: 191,0022,,2 2019a.
Nakkiran, P., Kaplun, G., Kalimeris, D., Yang, T., Edelman, L., Zhang, F., and Barak, B. Sgd on neural networks learns functions of increasing complexity. arXiv preprint arxiv:1905. 1.5..1160 1604, 2019b.
Nesterov, Y. A method for unconstrained convex minimization problem with the rate of convergence o (1/k" 2). In Doklady an ussr, volume 269, pp. 543-547, 1983.
Neuschel, T. Plancherel rotach formulae for average characteristic polynomials of products of ginibre random matrices and the fuss-co catalan distribution. Random Matrices: Theory and Applications, 3500)01450003, 2014.
Neyshabur, B., Tomioka, R., and Srebro, N. In search of the real inductive bias: On the role of implicit regularization in deep learning. In International conference machine learning, 2015.
Nichani, E., Radhakrishnan, A., and Uhler, C. Do deeper convolutional networks perform better? arXiv preprint PrXiw:2010.09611 2020.
Oyallon, E. Building a regular decision boundary with deep networks. In Proceedings of the IEEE Conference Computer Vision and Pottern Recognition, pp. (0645114, 2017.
15

---

Published in Transactions on Machine Learning Research (3/2023)
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, I., Desmaison, A., Kopl, A., Yang, E.,, DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. Pytorch: An imperative style, high-performance deep learning library. In Wallach, H., Larochelle, H., Beygelzimer, A., Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances Newral Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019.
Pennington, J., Schoenholz, S. S., and Ganguli, S. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. In Aduances in nearal information processing systems, 2017.
Pennington, J., Schoenholz, S., and Ganguli, S. The emergence of spectral universality in deep networks. In International Conference on Artificial Intelligence and Statistics, pp. 1924-1932. PMLR, 2018.
Pezeshki, M., Kaba, S.-O., Bengio, Y., Courville, A., Precup, D.; and Lajoie, G. Gradient starvation: A learning proclivity in neural networks. arXiv preprint ar arXic:2011.0966. 2020.
Razin, N. and Cohen, N. Implicit regularization in deep learning may not be explainable by norms, In Advances in neural information processing systems, 2020.
Rokach, L. and Maimon, O. Clustering methods. In Data mining and knowledge discovery handbook, pp- 321 352. Springer, 2005.
Roy, O. and Vetterli, M. The effective rank: A measure of effective dimensionality. In 2007 15th European Signal Processing Conference, pp. 606 610. IEEE, 2007.
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., et al. Imagenct large scale visual recognition challenge. International journal of computer vision, 2015.
Sanyal, A., Torr, P. H., and Dokania, P. K. Stable rank normalization for improved generalization in neural networks and gans. Xix preprind arXiw: 110.1190003353 2019.
Savitzky, A. and Golay, M. J. Smoothing and differentiation of data by simplified least squares procedures. Analytical chemistry, 3688):1627-163) 1964.
Saxe, A. M., Mcclelland, J. L., and Ganguli, S. Exact solutions to the nonlinear dynamics of learning in deep linear neural network. In In International Conference Learning Representations. Citeseer, 2014.
Shah, H., Tamuly, K., Raghunathan, A., Jain, P., and Netrapalli, P. The pitfalls of simplicity bias in neural networks. arXiv preprint Xiv:20006. 07710, 2020.
Shah, V., Kyrillidis, A., and Sanghavi, S. Minimum norm solutions do not always generalize well for perr-aaramttrrieed problems. In stat, volume 1050, pp. 16, 2018.
Sitzmann, V., Martel, J., Bergman, A., Lindell, D., and Wetzstein, G. Implicit neural representations with periodic activation functions. Advances in Neural Information Processing Systems, 33, 2020.
Solomonoff, R. J. A formal theory of inductive inference. part i. Information and control, 7(1):1 22, 1964.
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 191)):2822-288 2878, 2018.
Szegedy, C.,, Liu, W., Jia, Y., Sermanet, P., Reed, S., Anguelov, D., Erhan, D., Vanhoucke, V., and Rabinovich, A. Going deeper with convolutions. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1 9, 2015.
Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., and Recht, B. Low-rank solutions of linear matrix equations via procrustes flow. In International Conference on Machine Learning, pp. 964-973. PMLR, 2016.
Valle-Perez, G., Camargo, C. Q., and Louis, A. A. Deep learning generalizes because the parameter- faratitor-function map is biased towards simple functions. In International Conference Learning Represendations, 2019.
16

---

Published in Transactions on Machine Learning Research (3/2023)
Vershynin, R. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Wu, X., Du, S. S., and Ward, R. Global convergence of adaptive gradient methods for an werrparameterize neural network. Xiv preprint 1rXim1902.00111 2019.
Xie, S., Girshick, R., Dollár, P., Tu, 2.,, and He, K. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1492 1500, 2017.
Yang, G. and Salman, H. A fine-grained spectral perspective on neural networks. 1rXiv:1907.1083 2019.
ar preprint
Yoshida, Y. and Miyato, T. Spectral norm regularization for improving the generalizability of deep learning. arXiv preprinl ar Xrx 10941, 2017.
Zavatone- Veth, A., Canatar, A.; Ruben, B., and Pehlevan, C. Asymplotics of representation learning finite bayesian neural networks. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
Zhang, G., Martens, J., and Grosse, R. B. Fast convergence of natural gradient descent for wer-parameterized neural nelworks. In Advances in Neural Information Processing Systems, pp. 8082 8093, 2019.
Zhang, R., Isola, P., Efros, A. A., Shechtman, E., and Wang, O. The unrcasonable effectiveness of deep features as perceptual metric. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2018.
Zoph, B. and Le, Q V. Neural architecture search with reinforcement learning. In International Conference Learning Representations, 2017.
17

---

Published in Transactions on Machine Learning Research (3/2023)
Appendix
promise practical insights for grounded mathematical explanation (see related works). These assumptions are used to derive theoretical guarantees and often require: lincar assumptions, infinite width networks, dynamical isometries, gradient flow dynamic, or a specific learning paradigm such as matrix completion. In addition, low nuclear norm bias is not necessarily the same as low-rank bias, in which low-rank bias is more closely knit to the spectral bias. Hence, it is unclear whether muclear norm is the only explana- tion for the low-rank bias and whether these expla- nations hold true in practice. In light of empiricism, we provide a scries of investigations on the role of wver-parameterizalinn with the hopes to better guide our theoretical and practical understanding of deep networks.
A Frequently asked questions
Q: Why use effective rank?
A: Effective rank was popularized in the deep learn- ing community by Arora et al. (2019a) and has since been a common lool for measuring rank and analyz- ing the spectral properties of linear layers in neural networks (Razin & Cohen, 2020; Baratin et al., 2021). The entropic definition of the normalized singular values make effective rank a natural measure for com- puting the effective dimensionality of matrices. The effective rank operates on the distribution of the sin- gular values and not the non-zero counts. Due to numerical imprecisions of modern computation and stochasticity in our algorithms, we often find the rank of the matrix to be full-rank. This requires us to pick a threshold to zero out the smallest singular values after normalization (re-weighting the singular values based on their relative contribution). However, threshold rank is sensitive to the chosen threshold value (sce Figure 12) and therefore, we chose effective rank to cireumvents these issues.
To our knowledge, our work is the first to extensively study the existence of low-rank bias in non-linear networks. We extend our observations to practical learning paradigms. We show that the low-rank bias exists even before and after training, and highlight, that gradient descent is not the sole explanation.
Q: How does our work differ with Arora et al. (2019a)?
Alterantive measures, such as nuclear norm, has been commonly used in prior works; but, due to its un- bounded nature, it is not invariant to scaling (see Ap- pendix D).
Arora et al. (2019a) study the implicit bias of gradient descent in over-parameterized models. Contributions of their work include:
Extends the conjecture of Gunasekar et al. (2017) that gradient descent in linear matrix factorization results in low nuclear norm so- lution.
Q: Does depth always improve gencralization?
A: No, we do not claim that over-parameterization will always improve generalization. Like any regular- izers, over-regularizing your model hurls performance, as we have seen with linear models that are made too deep (He et al., 2016). When the true underlying func- tion is low-rank (as is typically with natural data), the bias toward low-rank kernels beneficial as training will tend to find a good fit that also matches the true structure of the data (and therefore generalizes well). When the true function is not low-rank, the bias will have an adverse effect (see Figure 12).
The observation is that deeper linear models can better solve low-rank matrix factorization problems using gradient descent on toy tasks. Provides theory, under isometric assumptions, how depth plays a role in the learning dy- namics of gradient descent in linear networks. "The dynamics promote solutions that have a few large singular values and many small ones, with a gap that is more extreme the deeper the matrix factorization is".
Q: Are comparisons made at comparable loss value?
Our work provides new insights in the role of over- parameterization in many ways. We highlight few of these differences below:
A: Yes, our experiments either assume the models have reached zero training error or have the same modeling capacity.
We extend the observation on simplicity bias to linear and non-linear finite networks. Our observations do not depend on any isometric assumptions, and we show that it holds even in practical problem setups
Q: What is the contribution of work?
A: While there is ample evidence that low nuclear norm bias exists in ovrrpaaramtterized models (Gu- nasckar et al., 2017; Arora et al., 2019a; Li et al., 2020), these theoretical works make assumptions that com-
We show that the parameterization bias exists regardless of training. That is, even with
18

---

Published in Transactions on Machine Learning Research (3/2023)
or without optimization, models are biased lowards low effective rank mappings.
standard deviation. For the sake of making the ta- bles readable, we have decided to omit the standard deviations in the tables.
We show that implicit bias exists beyond gra- dient descent, whereas prior theory only ap- plied to models optimized with gradient de- scent.
Q: What is the relevance of analyzing the gram matrix in non-linear model?
Even at zero-training error, models with dif- ferent depths but the same capacity will con- verge to different solutions, and ultimately exhibit different generalization properties. We show that even in practical learning paradigms, such as classification on CIFAR10 and ImageNet, deep networks exhibit the low effective rank bias.
The relevance of analyzing the gram matrix in non- linear models is not straightforward. This is because depth with non-linear layers can increase functional expressivity while also decreasing the rank. Hence, we should consider comparing models' gram-matrix when either the models have the same functional power or when the models that are being compared are operating in the zero-training error regine.
In summary: while prior works have primarily studied the bias of worrpprramctrrization under the context of gradient descent, our work focuses on bringing attention to another missing piece in understanding why over-parameterized models converge to low-rank solutions a phenomenon which is often credited why deep networks generalize (Gunasekar et al., 2017; Arora ct al., 2019a; Razin & Cohen, 2020).
There are many reasons why one would want to ana- lyze the gram matrix in non-linear models (Montavon et al., 2011). Under the conditions of functional equiv- alence or zero-training error, one can make relative comparisons on how the data is being mapped on held out data. In natural data, it is often assumed that are trying to discover low-rank relation- ship between the imput and the label. For example, a model that overfits to every training sample with- out inferring any structure on the data will generally have a test gram-matrix that is higher rank than that of a model that has learned parsimonious represen- tations. Furthermore, the low-rank gram matrix is also a good indicator of the variability in the data mapping. Lower rank on held out data indicates loss excess variability and therefore could be a good for analyzing robustness.
Q: Is the low-rank phenomena trivial obser- vation? While this is true and well-known for linear models with discrete rank, our work is making a more subtle statement that the spectral distribution of the weights becomes more concentrated as models are made deeper the entropy of the spectral distribu- tion decreases. In addition, our empirical findings are not directly predicted by the fact that multiplying matrices reduces rank: the networks also exhibit this effective rank reducing behavior at initialization and also convergence. is also unknown whether these behaviors would still persist for non-linear networks.
Q: Relationship to infinitely wide networks?
Analyzing the spectral properties of deep networks has also been studied under infinite width neural networks. (Aitchison et al., 2021) have observed that deep kernel processes with fixed, non-learned kernels exhibit a lower-rank structure, where the kernel follows power- law structure with depth. (Yang & Salman, 2019) shows that NTKs also exhibit this simplicity bias. For Gaussian processes, (Aitchison, 2020; Zavatone- Veth et al., 2021) further demonstrates that the rank of the "output Gram matrix" is restricted to the dimension- ality of the output space.
Q: Could the benefits of the proposed over- parametrization might be just due to in- creased capacity? Throughout our paper, we demonstrated that even when the model does not have increased capacity, linearly over parr-aaaamteeizee models improve generalization (See Figure 6, Figure 7, Ta- ble 1, Table 3, Table 2). Furthermore, even when all models achieve the same training error, we demon- strated that the resulting generalization properties are different (See Figure 12). We showed empirically that that model parameterization ultimately determines the likelihood of the hesot space deep models put higher probability weight on lower effective rank embedding.
Q: What are the standard deviation on these classification experiments? In supervised classifi- cations, the standard deviations are very small. All the experiments in our work have less than < 0.3%
19

---

Published in Transactions on Machine Learning Research (3/2023)
B Random matrix theory in finite models
1.0
depth 2
norma lizeddidd singular values
1.0
depth
lized singular values
1.0
depth
death
depth
probabiity p(a)
0.8
death
0.8
Jepdi
depth 1s
0.8
diptti 8
depph
0.6
0.6
0.6
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
180
singular va (o)
singular va lue indicies
singular value indicies
(a) Theoretical
(b) Empirical W E R32x32
(c) Empirical W R 256
Figure 8: Theoretical and empirical singular-value distributions: We show that even on finite matrices, the singular-value distribution matches that of the theoretical distribution. This implies that deeper finite-width linear neural networks should have lower effective rank in practice. The theoretical distribution uses an unnormalized probability distribution.
Random matrix theory makes an infinitely large random matrix assumption (square or rectangular); one can think of them as infinitely wide neural networks. This infinitely large matrix assumption used to derive a deterministic spectral distribution (singular-valuc distribution) random matrices. In Figure 8, we show that the empirical spectral distribution closely follows that of the theoretical distribution derived in (Pennington et al., 2017; Neuschel, 2014). Even when using very small weight matrix of size W 3R3x33 and more larger weight matrices W 2256x256 the singular values are dominated by just few values when increasing the number of layers.
romalzss singuar volues
depth
depth
normal alzedd singu values
depn
death 2
depth
depth 4
depth
nor alized singular
commalss alocd singulrr
62-
22
204
221
100
130
singularvauee value incldies
singular value indiclos
singllar value indicios
singular value indiccess
(a) Kernel rank W g32x32 (b) Kernel rank W C 333xx22
(c) Kernel rank W 2256x256 (d) Kernel rank W E 2526xx26 256
Figure 9: Singular value distribution of Gram matrices: Similar to the singular-value distribution the weights, the singular-value distribution of gram matrices also become sharper, lower effective rank, with increased depth.
In a similar light, we can also empirically observe the gram matrices' spectral distribution. As shown in Figure 9, we observed that gram matrices also exhibit almost the same trend predicted by random matrix theory. It is natural to assume that the theory has no practical meaning when the networks are trained, and the weight matrices are no longer random. Hence we trained the models to convergence on lcast-squares objective and observed the spectral distribution to maintain ils depth-wise separation as observed during initialization. These observations help reaffirm our conjecture and further motivate the potential usefulness of random matrix theory in understanding the role of over- parameterizationn in deep networks.
20

---

Published in Transactions on Machine Learning Research (3/2023)
C Expanding non-linear network
A deep non-lincar neural network with layers is paramcterized by a set of weights W = (W1,..., W,). The output of the j-th layer is defined as 0j = [vW[,, (d)- for some non-linear function v and input feature Φy-1- The initial feature map is the input 6 = z, and the output is the final feature map y = Φt. We can expand model by depth d by expanding all linear layers, Lc. redefining fw, - Sw Twaoo... fwy V E (1,...). We illustrate this in Figure 10. We describe this operation for fully connected and convolutional layers.
F
reperareterize
Rell
Faeli
Libear
Libear
Linear
Fully-connected layer A fully-connected layer is parame- terized by weight W R=xx One as scries of linear operators defined as I W,. For example, when d = 2, W + W,W1,, where W2 E Imxx and W1 E hhxx for some hidden dimension h. The variable h referred to as the width of the expansion and can be arbitrarily chosen. In our experiments, we choose n unless stated otherwise. Note that h min(m,n) n) would result in rank bottleneck and explicitly reduce the underlying rank of the network.
beith
Residast
Cardinelity
betcheure
pee-paarameterie W
Figure 10: Linear reparameterization: For reparameterize any linear model F, functionally equivalent layer layer another (shown in the box below). In this work we mainly explore reparameterization Batch-norm and any other running-statisties driven normalization layers are linear only at test time.
depth.
Convolutional layer A convolutional layer is parameterized by weight W E R.xxxkax, where m and n are the output and input channels, respectively, and & is the dimensionality of the convolution kernel. For convenience, we over-parameterize by adding 1 convolution operations. Wa* * Wa-1 * Wi, where Wa E [mxhxix1, Wa.,,.., W22 E 1axxxxxx and W1 E Bbxxxkxk; Analogous the fully--connectdd layer, we choose n avoid rank bottleneck.
The work by Golubeva et al. (2021) explores the impact of width h. Similar to their findings, observed using the larger expansion width to slightly improve performance. We use h = 2n for our ImageNet experiments.
21

---

Published in Transactions on Machine Learning Research (3/2023)
D Comparisons of rank measures and kernel distance functions
Depth 1
Depth 2
Depth 4
100
affact rank
slable rank
PUC lear POrTm
threshold
86
120
training
training
training epoch
training epoch
Figure 11: Comparing rank-measures: Comparison between various pseudo-metrics of rank when varying the number of layers. The threshold is set to r 0.01 for threshold rank.
The rank matrix - which defines the number of independent basis in practice can often be a sub-optimal measure. For deep learning, fluctuations in stochastic gradient descent and numerical imprecision can easily introduce noise that causes matrix be full-rank. In addition, simply counting the number of non-zero singular values may not indicate what we care about practice: the relative impact of the i-th basis compared to the j-th basis. In typical image classification sctup, we observed that the norm of the matrix often increases during training. This is highlighted by the nuclear norm in Figure 11. Coupled with numerical imprecisions, we found that the weights of the matrix are often always full rank.
A rank measure closest to the true definition of rank would be thresholdedrrank, where the smallest singular values are thresholded after normalization (re-weighting the singular values based on relative contribution). However, thresholded rank is very sensitive the threshold value one chooses (shown below); hence we usod
effective rank to avoid this issue.
22

---

Published in Transactions on Machine Learning Research (3/2023)
Definition D.1 (Effective rank). (Roy & Vetterli, 2007)
For any matric A Rmxx", the effective rank is defined as the Shannon entropy of the normalized singular values:
min(n.m)
p(A)
Σ
log(o.))
where o; = oil Ei oJ are the normalized singular values such that o = 1. It follows that p(A) S rankl (A). This measure is also known us the spectral entropy.
The effective rank has been previously used as a surrogate measure for measuring the rank of neural network weights ((Arora et al., 2019a)). We now state other various metries that have been used as a pseudo-measure of matrix rank. One obvious alternative is to use the original definition of rank after normalization:
Definition D.2 (Threshold rank). For any matria E RR the threshold rank T Rank the count of non-small singular values after normalization:
min(n.m)
R-Rak((A)
Σ
where is the indicator function, and (0, is the threshold value. o, are the normalized singular values defined above.
It is worth noting that not normalizing the singular values results in the numerical definition of rank. As stated before, the threshold rank depends largely on the threshold value and therefore drastically different scalar representation of rank can emerge. Polentially, a better usage of threshold rank is to measure the AUC when varying the threshold.
Related the definition of the threshold rank, stable rank operates on the normalized squared-singular values:
Definition D.3 (Stable rank). (Vershynin, 2018)
For any malria, A Rmx,, the slable ronk is defined as:
|||| ||A|||
ΣΦe ②
SRank(A)
maz
Where ae are the singular values of A.
Stable-rank provides the benefit of being efficient to approximate via the power iteration (Mises & Pollaczek- Geiringer, 1929). In general, stable-rank is good proxy for measuring the rank of the matrix and has been used in prior works such as (Nichani et al., 2020). This is not necessarily true when the singular values have a long tail distribution, which under-emphasizzs the small singular values un- proportionately due to the squared-operator. We observed that the largest singular values often get over exaggerated neural networks and hence we often found that SRrank converges values close to 1, making insightful observations impractical.
Lastly, the nuclear norm has been considered the de facto measure of rank for the task of matrix factorization cecooization/cooppetiion with low quclear-norm indicating that the matrix is low-rank:
23

---

Published in Transactions on Machine Learning Research (3/2023)
Definition D.4 (Nuclcar norm). For any matrix A E Rmx,, the nuclear norm operator is defined as: min(n.m)
||||, - tr(v tr(VA7) - Σ (A
Where oe are the singular values of A.
Nuclear norm, however, has obvious flaws of being an un-normalized measure. The nuclear norm is dictated by the magnitude of the singular values and not the ratios. Therefore, the nuclear norm can be made arbitrarily large or small without changing the output distribution.
The comparisons of these metrics are illustrated in Figure 11 where effective rank has the closest behavior to that of the thresholded rank. The metrics are computed on the end-to-end weights throughout the training. We use linear over- parammeteteee models with various depths on least-squares.
In Figure 12, we repeat our least-squares experiments from our main paper using thresholded rank with various threshold values with the thresholded rank. As stated above, we observe that the rank drastically changes depending on the threshold value. We also run the same experiment on varying task-ranks of 30, 16, and 4. Although all models span the same set of functions (same effective weight dimensionality), the resulting generalization performance differs depending on the depth of the model. In a high task-rank setting, the generalization error increases with depth, while generalization error decreases with depth low task-rank setting. This indicates the parameterization of the model determines the hypothesis space the model explores during training, which aligns with our conjecture and observations. This is further highlighted in medium and low task-rank settings, where all models reach zero-training error, yet the test-loss differs.
(0.001, 0.005, 0.01}. We show that the effective rank indeed correlates well
Kernel distance functions In our work we used cosine kernels to construct the Gram matricos. Cosine kernels are normalized linear kernels and we found it to produce cleaner results. Cosine kernels has been commonly used as distance function to measure similarity between features (Zhang et al., 2018). We further show in Figure that Gram matrices constructed with kernel distance functions such as linear kernels and correlation kernels also exhibit the low-rank simplicity bias
24

---

Published in Transactions on Machine Learning Research (3/2023)
Train test loss
Effective rank
Thresholded rank
Threshold r 0.001
Threshold r 6.066
Threshold 0.01
High task rank
Effective rank
Depth
Threshold r= 0.001
Threshold y 0.055
Threshold r 0.01
Medium rank
elfective mink
Loss
effective
effective
effectiv
Depth
Threshold = 0.001
Threshold 0.065
Threshold 0.00
Low rank
Eflective rark
Rank
Rank
Lose
00
Depth
Figure 12: Least-sqaures ablation: Least-squares experiment using both effective-rank and thresholded rank measure. We run the experiments on various task-ranks 30, 16, 4. For thresholded rank, we use various threshold values of = (0.001, 0.005, 0.01} and show that it correlates well with effective rank. The thresholded rank has downside of being sensitive to the threshold values, and one has to subjectively tune the suitable threshold, making it suboptimal choice. The figure shows that depending on the rank the task, the generalization performance depends the depth. When the task rank is high, shallower models perform better, and when the task rank is low, deeper models perform better. This aligus with our observation the model parameterization biases the hypothesis search space in neural networks even if the models effectively the same and span the same set of functions.
Train / test loss
Linear kernel
Cosine kernel
Correlation kernel
test
Elfective rank
Loss
Effactive
0
Effective
1.2
25
35
15
Depth
Figure 13: Kernel ablation: We ablate our least-squares experiments by using varions kernel distance functions. Cosine kernels are normalized version of linear kernels, and peanseon-correlation kernels are another way of normalizing linear kernels. We that all kernels show the same behavior.
25

---

Published in Transactions on Machine Learning Research (3/2023)
E
Singular value dynamics of weights
Unnormalized singular values
Normalized singular values
Original
Over-parameterized (4x)
Original
Over-parameterized (4x)
Conv1
to Reppinan
12
adiiies
Trann spochs
30
Conv2
Conv3
Conv4
FC1
FC2
Figure 14: Dynamics per layer: The singular values of the individual weights during CIFAR100 training. On the left have the unnormalized singular values, and the right the distributions are scaled by the largest singular values. We uniformly subsample 24 singular values for the visualization. The cross sections are provided to help visualize the distribution at that specific epoch. The individual lines track the singular values a, over time.
In Figure 14, we visualize the singular values of the individual weights when training on CIFAR100 image classification for the first 120 epochs. The cross-soctions indicate the singular value distribution at that specific epochs. For the prer-paramterrize model, the effective rank is computed on the effective weight. On the left, plot the unnormalized singular values and observe that the norm of the singular values
26

---

Published in Transactions on Machine Learning Research (3/2023)
Normalized magnitude
Initial distribution (Epoch O)
Singular values first decreases
Singular la values slowly increases
(Epoch 47)
(Epoch 180)
Original
0.6
0.4
0.2
0.0
Over-parameterized (4x)
0
100
200
300
400
500
0
100
200
300
400
500
0
100
200
300
400
500
Normelized magnitude
Initial distributian
Singular values first decreases
Singular values slowly increases
(Epoch D)
(Epoch
(Epoch 180)
0.6
0.4
0.2
0.0
100
200
300
400
500
0
100
200
300
400
500
0
100
200
300
400
500
Singularvalue indicies
Singular value indicies
Singular indicies
Figure 15: Dynamics overlay: We overlay the singular values of the Conv4 weights. We observed that the effective rank first rapidly decreases early on the training and then bounces back up slowly throughout the rest.
increases throughout training for all layers except for the last classification layer in the over-parameeeriieed model. When we normalized the distribution by the largest singular value (right), we observed that the distribution becomes sharper early in training but does not change much throughout.
To get better sense how the distribution evolves over time by overlaying the distribution on top each other. In Figure 15, we overlay the distribution on top of each other for Conv4 weights and observed that the effective-rank first decays rapidly and then slightly increases throughout the rest of the training. This dynamical behavior, to our knowledge, is not explained in prior theoretical works and could highlight the dissonance between the assumptions made in theory do not fully describe behaviors observed in practice.
27

---

Published in Transactions on Machine Learning Research (3/2023)
F Training details and model architecture
For Figure 1, we trained ReLU network with input, output, and the hidden dimension of 64; the larger the width, the more pronounced the effects seemed to be. We chose 64 due to the run time of these models. We train the model using SGD with a momentum of 0.9, and we do not use weight decay. We observed that very deop networks become very sensitive to the learning rate. Therefore, we tuned the learning rate per model. For each model we trained using the learning rates [1.0, 0.5, 0.2, 0.05, 0.02, 0.01, 0.005, 0.002, 0.001] and chose the best performing learning rate. A heuristics we found somewhat helpful is setting the learning rate as 17 Va for some depth d. The weights are initialized using normal distribution and linearly swept through
the scale of the variance. We found the gain of v2, the default gain of Kaiming initialization (He et al., 2016), to work the best. We tried 5 different seeds for each task-rank and also 5 different initialization seed for the neural network and observed consistent result. All models are trained for 24000 epochs as we observed deeper models take long time to converge. For shallower models, it is sufficient to train them for roughly 1000 epochs. We also experimented with learning rate schodulers but only helped a little. For all modcls, we stop the learning rate by a factor of 10 at epoch 18000. For all experiments rank(W")) = {1, 16, 32, 64], we use total of 128 training samples. Using a different. number of training samples results in similar observations. We experimented with both SGD and GD and observed the same phenomena. For SGD, we used a mini-batch size of 32. When the rank of the underlying function is high, we found that it required significantly more fine-grained tuning of the hyper-parameters.
All models for image classification are trained using PyTorch (Paszke et al., 2019) with RTX 2080Ti GPUs. We use stochastic gradient descent with a momentum of 0.9. For CIFAR experiments, the initial learning rate is individually tuned (0.02 for most cases); and we train the model for 180 epochs. We use a step learning rate scheduler at epoch 90 and 150, decreasing the learning rate by a factor of 10 cach step. For all the and random--rsize-croo for data augmentation.
models, we use randon-horiiootal-aae
The training details for ImageNet can be found in http://ggittbb..coppotooohhcc imagenet. When linearly preeaaaramttiiiinngg our models, we bound the variance of the weights using Kaiming initialization ion (He et al., 2016), a scaled Normal distribution. This allows us to have the same output variance, regardless of the number of layers we over- pverpaaraeeterize our models by. We found this to be critical for stabilizing our training. We also found it important to re-tune the weight decay for larger models on ImageNet. The architecture used for the CIFAR experiments is:
CIFAR architecture
RGB image y E 32323223
Convolution 3 > 64, MaxPool, ReLU Convolution 64 > 128, MaxPool, ReLU Convolution 128 + 256, MaxPool, ReLU
Convolution 256 + 512, ReLU
GlobalMaxIPoo
Fully-Connected 512 + 256, ReLU
Fully-Connected 256 + num classes
We tuned the learning rate per model as deeper models (8x expansion or more) become sensitive to the initial learning rate. This was critical for the least-squares experiments but not so much for CIFAR and ImageNett experiments (since we used up to 8x expansion). The one typer-parameter that we found that needed tuning was the weight decay in ImageNet classification. A typical 2x or 4x expansion does not require much tuning
28

---

Published in Transactions on Machine Learning Research (3/2023)
at all. The learning rate scheduler was originally tuned to the baseline and was held fixed. The learning rate decay for baselines with explicit regularizers was tuned.
For least-squares experiments, we were unable to achieve zero-training error for very deep networks using various common optimization tricks. We argue that the parametric bias of depth the reason why these models are unable overfit to high-rank data. While is certainly possible that an optimizer or optimization setting would allow to reach zero-training error, we were unable to find such setting and common optimization techniques. Given an SGD optimizer, we tuned learning rates (f0.1, 0.05, 0.01, 0.005, 0.001)); momentum ((f0.1, 0.5, 0.9, 0.99)), learning rate schedulers (none, step, decay on plateau, cosine)). We found the best set of hyperparameters that minimizes the training loss is with momentum set to 0.9 and using decay plateau scheduler. For an over-parameterized linear network of depth 16, and underlying task rank set to 24, we show that even with the best set of hyper pappe--praamters, the training loss cannot. be perfectly minimized:
by sweeping across
train epochs
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
0.1
nan
nan
nan
nan
nan
nan
nan
nan
nan
nai
initial learning rate
0.05
0.12
0.09
0.08
0.08
0.08
0.08
0.08
0.08
0.08
0.08
0.01
0.29
0.20
0.17
0.14
0.13
0.12
0.11
0.11
0.10
0.10
0.005
0.40
0.29
0.23
0.20
0.18
0.17
0.
0.14
0.14
0.13
0.001
0.71
0.58
0.49
0.44
0.40
0.38
0.31
0.29
Figure 16: Training error vs learning-rate: Training error with varying learning rates for least-squares trained linear network with depth of 24.
29

---

Published in Transactions on Machine Learning Research (3/2023)
G Differential effective rank
To analyze the effective rank as a function of the number of layers, we define a differential variant of the effective rank. This formulation allows us to use the fact that the eigen/sing siigg/saanaaaaauee spectrum assumes a probability distribution in the asymptotic case.
Definition G.1 (Differential effective rank). For any matrix A E R as min min(m,n) n) + oo the singular values assume probability distribulion p(o). Then, we define the differential effeclive rank p as:
((A) 1000=-opp Omaa 0
log( ))(o)do
(4)
where p(o) is the singular value densily funclion and mm eplar)do is the normalization constant.
H Proof of Theorem
To prove Theorem 3.1, we leverage the findings from random matrix theory, where the singular values assume probability density function. Specifically, we use the density function corresponding to the singular values of the matrix W composed of the product of L individual matrices W = WL.... W1, where the components of the matrices Wi to W, are drawn i.idd from Gaussian. Characterizing such density function is, in general intractable, or otherwise very difficult. However, in the asymptotic case where dim(W) + co and W is square, the density function admits the following concise closod-form (Eq. 13 of Pennington et al. (2017) derived from Neuschel (2014)):
2
sin sin (Lx)
sin sin + 1)6) sin( sin sin (L
p(a(o))
π sin ((L 1)6) o( V
where denotes singular values (parameterized by [0, 1) and p denotes the probability density function of for E [0, maxx) and d = L ( 11)4t1 The parametric probability density function spans the whole singular value spectrum when sweeping the variable Φ
We are interested in computing the effective rank of W. Using the above density function, we can write it in the form:
> do )
p(W) p(W)=-) mmax
log( 1og("))lo
(6)
c
We now write this integral in terms of the integration variable, such that we can leverage the density function in Eqn. 5. Using the change of variable, have:
PW:L) = - LA (Φ) log (- do
(7)
where d'()) = do (0)) Note that the intogral limits [0, mmaxl on respectively translate into [,, 0] on d where,
-p((()))
1 (1+ 2T
(L+ + 1) cos(2Lo) coos(2(1 + 1)0) cscc (LØ).
In the following, we treat L as a continuous variable, and show that p(W: L) is decreasing L. This is sulficient for proving p(W:L) L) results in a decreasing sequence at integer values of L.
As L) is differentiable in L, L) decreases in L if and only if de 0. Since integration and dz
differentiation are w.r.t. different variables, they commute; we can first compute the derivative of the integrand w.r.t. L and then integrate w.r.t. and show that the result. is negative.
note that the direction integration needs to flip (by multiplying by -1) account flip of the upper lower limits.
30

---

Published in Transactions on Machine Learning Research (3/2023)
With abuse of notation, rewrite Equ. by making the dependency of functions L explicit.
पीं olo L.) PW;L) f c(L)
log( d(, L. )p(a(s, L))o' do d()
(8)
where d'...) denotes partial derivative of o(...) w.r.t. its first argument.
We now proceed with differentiating P w.r.t. L. Notice that, besides the integrand, the integral limit depends L as well. Thus can be handled using Leibniz integral rule for differentiation, which yields,
Op OT.
( L) ((o.L) L) (LL)
log(
cLt) )lol L)) I7I
( OT. L+1
π
(9)
Jo in δ (o(o_L) log( - )p(o(o, L))o'(0, Li) do
(10)
Oe cL) dL)
It is easy to verify Chat,
L( cLL)
log( (o.LL) 0 c(L)
lim
(11)
L+1
(I. (I+ [coos( (L.cosl
1+1)
cosl
1+1
T.)
csc2
I+I
Lx
lim p(o(o, L))o (o. =
(12)
9- 1+1 L+1
2T
Consequently,
([ c(L)
o ( (o) c(L)
log(
=0
(13)
This allows us to drop the first term in
to express it more compactly as, at
de
3p
z d L)
I(0,L) c(L)
)l(a(o, L))o' (b. 1)) dø.
OL c(L) log(
(14)
OT.
Tt is messy but straightforward to compute at è from 0
o(o.L) cLL log( o(ob)) dp
at) (( L)) (b, 1.). Integrating that w.r.t.
a L+1 leads to a negative expression, thus < 0. BT.
The proof here considers the asymptotic case when dim(W) - co. This limit case allowed us to use the probability distribution of the singular values. Although we do not provide proof for the finite case, results demonstrate that holds empirically in practice (see Figure 2).
31

---

variance Published in Transactions on Machine Learning Research (3/2023)
Extension to residual connections
This work concentrates our analysis on depth and its role in both linear and non-linear networks. Yet, the ingredients that make up what we know as state-of-the-art models today are more than just depth. From cardinality (Xie et al., 2017) to normalization (Toffe & Szegedy, 2015) and residual connections (He et. al., 2016), numerous facets of parameterization have become fundamental recipe for successful model (see Figure 10). Of these, residual connections have the closest relevance to our work.
feodfonward
media
3.25
feed-ooward
effective rank
resi (oatch nom)
3.0
2.75
2.5
2.25
2.0
1.5
What is it about residual connections that allow the model to scale arbitrarily in depth? while vanilla feed-forve forward networks cannot? One possibility is that beyond certain depth, the rank of the solution space reduces much that good solutions no longer exist. In other words, the implicit. rank-regularizzation of depth may take priority over the fit to training data. Residual connections are essentially "skip connections" that can be expressed as W- - W + I, where I is the identity matrix (Dirac lensor for convolutions). There are two interpretations what these connections do: one is that identity preservation prevents the rank-collapse of the solution space. The other interpretation is that residual connections reduce the effective depth the number of linear operators from the input to the output (e.g., ResNet50 and ResNet101 have the same effective depth), which prevents rank-collapse of the solution space. Results in Figure 17 confirm this intuition. ResNets, unlike linear networks, do not exhibit a monotonic rank contracting behavior and the effective rank plateaus after layers, regardless of using batcl-nnormlliztiion or not. Furthermore, preliminary experiments on least-squares using lincar residual networks indicate that the effective rank of the solution space is also bounded by the number of layers the shortest and longest path from the imputs to the outputs. A thorough study on the relationship between residual connections and rank is left for future work.
10
15
20
25
30
depth
Figure 17: Residual connections: The effective rank of linear models trained with and without resid- ual connection on a low-rank least-squares problem. Contrary feed-forward networks, residual networks maintains the effective rank of the weights even when adding more layers. Residual networks without batch- normalization suffer from unstable output after layers.
32

---

Published in Transactions on Machine Learning Research (3/2023)
J Least-squares learning dynamics
The learning dynamnic of a linear network change when wer-parameterized. Here, we derive the effective update rule on least-squares using linear neural networks to provide molivation on why they have differing update dynamics. For a single-layer linear network parameterized by W, without bias, the update rule is:
w(++1) t ((() Woo.o 2. v)
(15)
wW( wr 1 (V- w))
(16)
((( n(((()) (xx -yx"
(17)
Where 1) the learning rate. Similarly, the update rule for the two-layer network y War WyW1r i can be written as:
W W1O) ( - yx²)
(18)
whet1) w! -n(W!" 2x" yx yx²)
(19)
(20)
Using a short hand notation for vC( W(()) xx. yo² we can compute the effective update rule for the two-layer network:
W(++1) (((+1)) (+((t))(((t))
(21)
first order O())
second order O(1²²)
= W(O)) - (W W ( + W w(() + O
(22)
W(()) (P VC PT)
(23)
Where p!O) w are the preconditioning matrices. The higher order terms can be ignored the step-size is chosen sufficiently small.
(General case) For linear network with d-layer expansion, the update for layer 1 S i is:
weights >
original gradient
weights <
w((++)) w((t) (w w yT (W you yx (w 1(9
(24)
Denoting W₁ = W, ... -.+ W, for j > i, the effective update rule for the end-to-end matrix is:
((++1)= = II ((++1)
II (W;
(IT VLO 1-11
(25)
d:f+1
1<idd
1<<dd
((t))
Σ
Wait WT dift
- -n W.-1 + +0(1) + +(1))
(26)
Ieied
2 ((!) 1) Σ Wast1
WT d+++
V
W W 111
(27)
Icied
left. precondition original gradient right precondition
The update rule for the general case has a much more complicated interaction of variables. For the edge i and p the left and right preconditioning matrix is identity matrix respectively.
33

---

Published in Transactions on Machine Learning Research (3/2023)
K
Rank-landscape
We visualize the effective rank landscape of the effective weights in Figure 18 and Gram matrices in Figure 19. We use single and bwo-layer linear networks for effective-rank landscape. We use two-layer, and lour-layer ReLU worksrks for the Gram matrix and are constructed from 128 randomly sampled input data. For both methods, all the weights are sampled from the same distribution. The landscape constructed by moving along random directions u, v. We observe that prer-parameterized linear and non-lincar models almost always exhibit lower-rank landscape than their shallower counterparts.
uu effective rank p(W,)
effective p(W,)
11.0
ne
2.
0g
455 magnitude
20
magnitude
10 magnitude of
magnitude
05
65
00
10
15
15
20
single-layer
two-layer
Figure 18: Rank landscape: The landscape of the effective rank p of a linear function W, parameterized either by a single-layer network (Wa W) or two-layer linear network (W, = W2W1). The visualization illustrates a simplicity bias of depth, where the two-layer model has relatively more parameter volume mapping to lower rank We. Both models are initialized to the same end-to-end weights We the origin. Motivated by Goodfellow et al. (2015), the landscapes are generated using 2 random parameter directions u, to compute f(a, = p(W u + 3 v) for the single-layer model and f(a, 3) p((W2 + a d2 + 02) (W1 + a un + -.)))) for the two-layer model (u [ui [u1, [vl, v2))-
effective rank p(k)
effective rank ((K)
magnituce ol
35 0.5
0.
15 10
magnifudo
3.
R5
.0
magnitude of y
00
magnitudk of y
5.0
05
16
55
18
15
20
two-layer
four-layer
Figure 19: Kernel rank landscape: The landscape of the elfective rank computed on the kernels constructed from random features.
34

---

Published in Transactions on Machine Learning Research (3/2023)
L
Relationship between weight and embeddings
8
2.0
effective rank of kemel
7
1.8
1.6
1.4
1.2
2
2.2
2.4
effective rank of weight
Rank relation of kernel and weight: Each point represents randomly drawn network. For each network, we compute rank on the effective weight and also linear kernel. The kernel is constructed from the MNIST dataset. The rank of the kernels and weights have linear relationship.
Figure 20:
We show that there is almost onc-to-one relationship between the effective rank of the weights and the effective rank of the Gram matrices in deep linear models. The figure plots this relationship for random deep linear networks applied to random subsets of the MNIST dataset. Moreover, it becomes apparent that the number of layers dictates the rank of the embedding as well as the weights.
35

---

Published in Transactions on Machine Learning Research (3/2023)
M
Noisy linear regression with least-squares
We extend our lcast-squares analysis under noisy observation to study the interaction between noisc and the low-rank bias of the deep worksrks We consider the standard linear regression with the least-squares objective with additive Gaussian noise:
Y= WX + +N
(28)
In noisy linear regression, even if the intrinsic dimensionality of W is low, the noise in the observation makes the relation between X and Y appear as full-rank. We consider two instantiations of noise injection, one in which the noise is sampled once (static) and another in which noise is resampled every iteration (stochastic). While the training loss noisy, the test loss computed on samples drawn from a noiscless system. In the presence of low-rank bias, even under noisy observations, deeper networks should be biased toward finding low-rank solution. Hence, deeper networks should not overfit to the noise and result in better generalization.
To test this hypothesis, we repeat the least-squares experiment under noisy observation (see Figure 21). We set rank(W)= = 24, for W E TR32x32 and add varying levels of noise a E (0.1, (0.1,0.3, 0.3, 0.5) to the training labels. For all varying depths, we initialize the network to the same distribution and train the network with SGD and learning-rate scheduler (decay-on-plateau). Note that the y-axis is scaled higher than the figures in the main paper to ensure we the same y-axis across different noise levels. For all noise levels, we observed that deeper networks converge towards low-rank solutions, and we find that the swect-spot depth that yields the best test performance varies for each setting. The experiments yielded few surprising observations:
For static additive noise, the noise can be overfitted by the model. In this setting, we observed that shallower networks perfectly overfit to the noise while deeper networks cannot. Unlike the noiseless least squares, doeper networks resulted better test performance. The shallower networks find solutions that much higher effective rank. The observation implies that depth regularizes the model from overfitting to the noise.
For stochastic additive noise, the noise cannot be overfitted by the model. In this setting, we observed that the deeper networks found an even lower effective rank solution than the noiscless counterpart. Ultimately, while shallower networks perform worse than their noise-less counterpart, the deeper networks perform on par better. We hypothesize that the stochasticity and simplicity bias leads to lower effective rank solutions.
In both settings of noisy least-squares, we observed that the simplicity bias of depth still persists. We observed that depth improves generalization performance by underfitting the noise the data. This may explain why deep networks generalize well under weak supervision and corrupted labels. These observations further suggest that under noisy data, one should increase the depth to mitigate overfitting to noise.
36

---

Published in Transactions on Machine Learning Research (3/2023)
2.5
24
20
1.5
loss
effective
1.8-
1.0m
14
1.4
0.5
8
1.2
0.0
10
20
30
10
20
30
depth
depth
(a) (reference) 0
effective Pank
lectivve rank
1.2
14
12-
0.5
0
22
0
depth
dapth
depth
depth
(b) (static) 0.1
(c) (stochastic)
0.1
24-
20
offective rank
effective r9ni
1.5
02-
6
02
6
6
depth
depth
depth
depth
(d) (static)
0.3
(e) (stochastic)
a
20
effective rank
elfective rank
1L 12
8
depth
depth
depth
depth
( (static)
(g) (stochastic) a
Figure 21: Noisy least-squares: Experiments investigating how noise affects the simplicity bias of depth.
37


Reviews:
[{"review_id": "vMhx1UMnBn", "reviewer": "Reviewer_diZQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n* The authors study a problem of interest to the machine learning theory community.\n \n* Similar observations about increased network depth inducing low-rank representations have been made in various contexts- for example, cf. several papers by Arora, Cohen, and other authors ca. 2019 onwards. Most of these earlier results are optimization-focused: they study a particular optimization method (usually, gradient descent) and show that the network weights obtained via this method eventually exhibit (some definition of) low-rankness. This paper can be viewed as an addition to the body of work, making the case that it is not just due to the optimization routine: the very representation itself inductively biases towards low-rankness. I found the case made by the paper to be fairly compelling. \n\n**Weaknesses**\n\n- My impression was that the paper made interesting observations, but did not provide any particular insights that were not known already. The NTK style results of Yang/Salman (2019), and earlier results by Valle-Perez et al (2018) already had made the case that deeper networks exhibit increasing spectral bias (although perhaps with a slightly different set assumptions than the current paper). Again, this may not be a dealbreaker for acceptance to TMLR: the empirics are fairly thorough and well thought out -- but wanted to highlight this nonetheless.\n\n- I found that a lot of important details of the main paper were deferred to various Appendices, impeding the paper's flow. (For example, the main results of Section 2.3, 3.1, insights into the theory in 3.4, the stuff on linear overparameterization, etc are all key to the overall discussion.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary**\n\nIn this paper, the authors make a number of (empirical) observations about the inductive bias of deep neural network architectures. Ablating cross various choices of models, hyper-parameters, optimizers, datasets, and number of training epochs, they show that deeper networks generally lead to lower (effective) rank feature embeddings, a phenomenon that they call \"low-rank simplicity bias\".\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Critical**\n\n- May be helpful to mathematically define (feature) embedding rank, at least informally, the first time it is introduced (Page 2). It only becomes clear in Section 2.3.\n- I was mildly thrown off a few times by the somewhat fungible use of \"low-rank\" and \"low-effective-rank\". The authors make the case early on that the two are qualitatively equivalent, but that's not always the case. For example, Observation 3.1 (or Figure 2) is interesting in that low effective rank is exhibited at initialization but I would be surprised if random feature embeddings also exhibited low (standard) rank. Please reconsider carefully the use of \"low-rank\" in such places.\n\n**Other comments**\n\n- Consider remaking Figs 2,3,4,5 to be better accessible to color-challenged readers; it was a bit hard for me to separate the various curves. Different-shaped markers for each line plot might help.\n- Page 8: Typo: \"multilpications\"\n- Just a style point, but consider renaming 'FAQ' in the appendix as something else? Not common to see an FAQ list in papers.", "broader_impact_concerns": "None to report.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "N2wemQkVSt", "reviewer": "Reviewer_tssy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* I find Figure 1 to be a good demonstration of the difficulty of neural networks in fitting high rank ground truth functions. This is an interesting experimental control to observe this.\n\n* The argument in Figure 2, that the effective rank of feedforward networks decrease with increasing depth is interesting and well reflected in Figure 2 for Linear and non-linear ReLU networks.\n\n\n*However, this is only for randomly initialised networks which is not very surprising (or highly practically relevant) as the product of matrices or linear transformations are bound to decrease the rank unless all matrices are aligned which is a low probability event under random initialisation. What would be an interesting observation is if it also holds for neural network under convergence. This is what the authors target in Figure 3, but the results do not make that point as all it does it tries to get closer to the ground truth in its rank from its initialisation. Thus networks with smaller initialisation rank end up with larger initialisation rank and networks with larger initialisation rank end up with smaller ones. This is again expected of any function irrespective of what the true bias is. Given the observation regarding initialisation and that the ground truth is low-rank, Figure 3 is quite uninformative to me. If the initialisation is at rank x and the target is rank y and if the training gets you closer to the ground truth in terms of parameter recovery,  then is exactly what you would expect.\n\n* This is further illustrated in Figure 6 but there once the depth is large enough to be relevant for deep network in practice (e.g. greater than 10), there is barely any change in rank.\n\n1. Thus, my overall conclusion for this observation of rank vs depth is that the argument holds for initialisation, which immediately follows from standard linear algebra but the evidence provided in the paper for networks used in practice is not convincing.\n\n2. My second and perhaps bigger criticism is that paper ignores many relevant works. It is already well known that neural networks are biased towards learning low dimensional representations. In particular Oyallon [2017] and Sanyal et. al 2018 study this specific problem. However, neither has been cited in this work. While Oyallon [2017]  studies how the  rank changes with depth, Sanyal et. al. 2018 also shows this phenomenon in practice, studies how a lower dimensionality improves robustness as well as generalisation and also proposes a specific regulariser to induce it in neural networks. All of these are claimed as novel in this work.\n\n3. For linear networks, which is studied extensively in this paper has also been shown to tend towards low rank solutions in previous work with gradient flow. In particular, Ji and Telgarsky [2019 and 2020] showed that in linear networks with one dimensional output, gradient flow on commonly used exponential loss functions like cross entropy tend to networks where each layer is of rank one. Again both of these works are not cited.\n\n4. There aren't enough details about what exactly is used for the algorithms in Table 1, 2, 3. Are all the networks of similar parametric complexity ? Or do the ones mentioned as \"over-parameterised\" actually have more parameters than the baseline? that would make the comparison very unfair. \nAlso what is the exact algorithm used to minimise the effective rank and the stable rank ? Are these from already existing algorithms like stable rank normalisation, if not, are there guarantees that they are actually minimising the stable rank etc ?\n\n\nOyallon Edouard. \"Building a regular decision boundary with deep networks.\" 2017.\n\nSanyal, Amartya, et al. \"Robustness via deep low-rank representations.\" 2018.\n\nJi, Ziwei, and Matus Telgarsky. \"Gradient descent aligns the layers of deep linear networks.\" 2019\n\nJi, Ziwei, and Matus Telgarsky. \"Directional convergence and alignment in deep learning.\"  2020\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In my opinion, the contributions of the paper can be summarised as follows\n* The effective rank of representations of neural networks decreases as the network gets deeper. This holds both at initialisation and at convergence.\n*  The paper argues this with a volume argument, which says that for deeper networks, the number of solutions that have a low rank are large. \n* The paper also discusses its impact on generalisation.\n* Finally, the paper proposes a regularisation objective using over-parameterisation to further exploit this bias.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Include the relevant citations and discuss what are the main differences to their work and which claims are novel to this paper and which are not etc.\n* Table 1,2,3 needs error bars or some form of confidence intervals in order to be statistically significant.\n* Table 2 needs a discussion of the various methods used to achieve the regularisations.  Please discuss how you regularise the various quantities and why the methods are sound. The method of Spectral Normalisation and Stable Rank Normalisation already exists in literature and they should be used to minimise stable rank (and if necessary spectral norm).\n* There should also be a comparison of the over-parameterisation approach to reduce rank to the LR Layer used to reduce rank in Sanyal et. al. 2018.\n* The baselines should have comparable parametric complexity as the number of parameters is often a confounder in DNN experiments.\n* Finally, the authors should argue better why their experiments show the low rank bias at convergence holds in light of my arguemnts in the previous section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hRooA34xv5", "reviewer": "Reviewer_6vzF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "=============== Strength ===============\n\nThe paper is well organized and relatively easy to follow, especially the main contributions and claims are highlighted and crystal clear.\n\nExperiments are also dense and cover many aspects of the claims to provide comprehensive support.\n\nIn appendix, there is even a Q&A section to further define the scope of the paper and clarify statements.\n\nIn literature, implicit bias often associates with learning algorithms. This paper aims at a novel perspective and studies the implicit bias of network architectures. To my knowledge, this is an interesting and stimulating direction both to theorists and practitioners.\n\n=============== Weakness ===============\n\nMany of the empirical justifications are based on a simple noiseless linear regression model.\n\nIn real data experiments, the performance leaves a large gap to the state-of-the-art. For example, in CIFAR10, the best test accuracy in paper hits slightly less than 90%. However, ResNet and EfficientNet can easily achieve over 98% accuracy. Such a performance gap undermines the value of augmenting linear layers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provides a thorough study on the bias towards low-rankness induced by increasing depth in neural networks. The main discoveries are\n\n1). in linear regression, increasing the depth of linear layers leads to low effective rank embeddings;\n\n2). in practical data sets, e.g., CIFAR10 and CIFAR100, augmenting linear layers can improve performance.\n\nTo support the above discoveries, many experimental results are provided as well as a related theoretical study.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It is interesting to study noisy linear regression problems. Does the low-rank bias still hold when noise can potentially deteriorate the intrinsic structures?\n\nThe authors tried some small network architectures for CIFAR10 and CIFAR100 tasks. The performance gain of augmenting linear layers is statistically consistent. However, the improvement would be of more importance, if the improvement also appears on some state-of-the-art models.\n\nIn Figure 6, the training loss is not zero for deep networks. Thus the comparison of effective ranks might not be very convincing.\n\nThe statement of Theorem 3.1 is not very precise. The proof in Appendix H assumes all the matrices are square and then sends the dimension to infinity.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The key contribution of the paper is a thorough investigation of the low-rank bias of non-linear neural networks, with a focus on toy datasets. The Authors demonstrate that increasing depth in neural networks decreases a measure of the rank of model weights for both toy and realistic neural networks. Experiments suggest a causal relationship between the low-rank bias and generalization performance.

The paper received borderline reviews. Two reviewers voted for rejection. The third reviewer voted for acceptance after rebuttal.

One major criticism focused on the fact that results are not fully novel. My understanding is that similar observations can be found in the literature. For example, Figure 6 of Oyallon et al shows a metric related to effective rank decreasing with depth. Ji et al study linear networks (which are the significant focus of the paper) and show a form of low-rank bias under certain stringent assumptions. Somewhat related simplicity bias shows that deep neural networks have a bias toward learning simple functions (e.g. not learning high-frequency components of the input-output mapping).

The paper presents a potentially misleading narrative behind the key contributions. The Authors state in the introduction that “we stumbled upon a rather unexpected discovery that provides clues into why and when over-parameterization could help”. However, the discovery they have stumbled upon could be arguably deduced from existing results in the literature.

A view that is more in line with TMLR focus on correctness is presented in the Appendix. I agree that “our work is the first to extensively study the existence of low-rank bias in non-linear networks”. I would ask the Authors to revise the introduction to give a more objective view of the field.

My take is that the results are likely to be valuable to the community interested in the foundations of deep learning, even if the conclusions could be largely deduced from existing literature.

The second major criticism focused on the correctness of results. In particular, it indeed doesn’t seem to be surprising that in the toy task summarized in Figure 3 networks converge towards the rank of the training data. This is expected from the perspective of just fitting well the training set. According to my understanding, this indeed should be clarified in the paper or a different experiment should be run.

Another issue that was raised is that too much focus is on experiments on toy data. I think it is a valid criticism. However, image classification results (C10, C100, Imagenet) do suggest that there is a causal link between rank and generalization in deep neural networks, at least in image classification. (It was also raised that it is an unfair advantage that Authors added parameters. I would say it is OK because there is no nonlinearity between the added weight matrices).
Despite criticisms, I think there are important strengths to the paper. I mostly agree with Authors' statement “our work is the first to extensively study the existence of low-rank bias in non-linear networks”, with the caveat that results still focus very strongly on toy tasks.

All in all, I am recommending acceptance conditional on addressing some of the key criticisms. I would ask the Authors to rewrite  the introduction in order to make a clearer exposition of the existing works. I would also ask the Authors to add more context about Figure 3 or show analogous results on real data.
Decision: Accept (poster)