Year: 2021

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 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 and show that these are the solutions that generalize well. We then show that the low-rank simplicity bias exists even after training, using a wide variety of commonly used optimizers. We found this phenomenon to be resilient to initialization, 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 without changing the effective model capacity. Practically, we demonstrate that simply linearly over-parameterizing standard models at training time can improve performance on image classification tasks, including ImageNet.

heading: 1 INTRODUCTION
text: It has become conventional wisdom that the more layers one adds, the better a deep neural network (DNN) performs. This guideline is supported, in part, by theoretical results showing that deeper networks can require far fewer parameters than shallower networks to obtain the same modeling “capacity” (Eldan & Shamir (2016)). While it is not surprising that deeper networks are more expressive than shallower networks, the fact that state-of-the-art deep networks do not overfit, despite being heavily over-parameterized1 , defies classical statistical theory (Geman et al. (1992); Zhang et al. (2017); Belkin et al. (2019)).
The belief that over-parameterization via depth improves generalization is used axiomatically in the design of neural networks. Unlike conventional regularization methods that penalize model complexity (e.g., `1/`2 penalty), over-parameterization does not. Yet, like explicit regularization, over-parameterization appears to prevent the model from over-fitting (Belkin et al. (2018); Nakkiran et al. (2019a)). Why this implicit regularization works is still an ongoing area of research. Even in the zero-training error regime, it is commonly observed that increasing the number of parameters improves generalization performance. Currently, the status quo explanation for this phenomenon is that gradient descent in over-parameterized models acts as a nuclear norm regularizer (Gunasekar et al. (2017); Arora et al. (2019a); Li et al. (2020)).
This work provides a new set of observations that expand the growing body of work on overparameterization and highlights the central role of depth in finding solutions that map to low effective rank embeddings for both linear and non-linear networks. Mainly, we make series of empirical observations that indicate deep networks have an inductive bias to find lower effective rank embeddings. First, we observe that random deep networks are biased to map data to a feature space whose Gram matrix has a low effective rank. Next, we find that this low effective rank phenomenon exists even after training with gradient descent. We further observe that the bias towards low effetive rank embeddings exists in a wide variety of common optimizers — even optimizers that do not use gradient descent. Moreover, we find that regardless of the initialization, the effective rank of the
1e.g., Dosovitskiy et al. (2020) trains a 632 million parameter, 200+ layer model, on 1.3 million images.
converged solution is largely dependent on the depth of the model. This set of observations leads us to 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 then leverage our observations to demonstrate how one could use “depth" as a practical regularizer to achieve better generalization performance on standard benchmarks such as CIFAR (Krizhevsky et al. (2009)) and ImageNet (Russakovsky et al. (2015)).

heading: 2 PRELIMINARIES

heading: 2.1 NEURAL NETWORKS AND OVER-PARAMETERIZATION
text: Simple linear network A simple linear neural network transforms input x ∈ Rn×1 to output ŷ ∈ Rm×1, with a learnable parameter matrix W ∈ Rm×n,
ŷ = Wx. (1)
For notational convenience, we omit the bias term.
Over-parameterized linear networks One can over-parameterize a linear neural network by defining d matrices {Wi}di=1 and multiplying them successively with input x: ŷ = WdWd−1 · · ·W1x = Wex, (2) whereWe = ∏d i=1Wi. As long as the matrices are of the correct dimensionality — matrixWd hasm columns, W1 has n rows, and all intermediate dimensions {dim(Wi)}d−1i=2 ≥ min(m,n) — then this over-parameterization expresses the same set of functions as a single-layer network. We disambiguate between the collapsed and expanded set of weights by referring to {Wi} as the over-parameterized 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 in between the weights matrices:
ŷ = Wdψ(Wd−1 . . . ψ(W1(x))) (3)
In contrast to linear networks, non-linear models become more expressive as more layers are added.

heading: 2.2 EFFECTIVE RANK
text: We characterize the rank of a matrix using a continuous measure known as the effective rank:
Definition 1 (Effective rank; Roy & Vetterli (2007)). For any matrix A ∈ Rm×n, the effective rank ρ is defined as the Shannon entropy of the normalized singular values:
ρ(A) = − min(n,m)∑ i=1 σ̄i log(σ̄i),
where σ̄i = σi/ ∑ j σj are normalized singular values, such that ∑ i σ̄i = 1. Also referred to as the spectral entropy. Without loss of generality, we drop the exponentiation for convenience.
This measure gives us 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 in 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 closest definition of rank in which we threshold the smallest singular values after normalization (Appendix C). Similar to prior works, we refer to low effective rank as low rank here on out.

heading: 2.3 EMBEDDING MAPS
text: A parameteric function f{W} ∈ FW is a neural network parameterized with a set weights {W} = {W1, . . . ,Wd} that maps the input space to the output space X → Y . For a training dataset of
size q, the input and output data is X ∈ Rn×q and Y ∈ Rm×q. Then, the predicted output is Ŷ = Wdψ(Φ) = f{W}(X), where Φ ∈ Rn ′×q is the last-layer embedding and Wd ∈ Rm×n ′
is the last layer of the network.
We analyze the embedding space by computing the effective rank on the Gram/kernel matrix K ∈ Rp×p where p is the size of the test set. The ij-th entry of the Gram matrix corresponds to a distance kernel Kij = κ(φi, φj) where φi corresponds to the i-th column of Φ. We use the model’s intermediate features before the linear classifier and use cosine distance kernel 2, a common method for measuring distances in feature space (Kiros et al. (2015); Zhang et al. (2018)). Since the dimensionality of the Gram-matrix does not depend on the model parameters, we can compare neural networks with different modeling capacities in the zero training error regime.
Gram matrices are often used to analyze optimization and generalization properties of neural networks (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 to every training sample without 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 representations. Lower rank on held-out data indicates less excess variability and is indicative for studying generalization and robustness. The intuition becomes clearer in linear networks, since the rank of Gram matrix depends on the rank of the linear transformation computed by the network. We illustrate this empirically in Appendix L, where we see that there is a tight relationship between the rank of the linear weight matrix and the resulting Gram matrix.

heading: 2.4 LEAST SQUARES
text: Given a dataset X,Y generated from W ∗, the goal is to regress a parameterized function f{W}(·) to minimize the squared-distance ‖f{W}(X)− Y ‖22. The rank(W ∗) is a measure of the “intrinsic dimensionality” of the data and we refer to it as the task rank. In this work, we exclusively operate in the under-determined regime where we have fewer training examples than model parameters. This ensures that there is more than one minimizing solution.

heading: 3 THE INDUCTIVE PARAMETERIZATION BIAS OF DEPTH
text: Given that our models can always fit the data, what are the implications of searching for the solution in the over-parameterized model? In linear models, this is equivalent to searching for solutions in {Wi} versus directly in We. One difference is that the gradient direction∇{Wi}L({Wi}) is usually different than ∇WeL(We) for a typical loss function L (see Appendix I). The consequences of this difference have been previously studied in linear models by Arora et al. (2018; 2019a), where the
2cosine kernel: κ(φi, φj) = φiφ
T j
‖φi‖‖φj‖
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 a result from the perspective of parameter volume space.
Conjecture 1. Deeper networks have a greater proportion of parameter space that maps the input data to lower-rank embeddings; hence, deeper models are more likely to converge to functions that learn simpler embeddings.
We now provide a set of empirical observations that supports our conjecture. Our work and existing theoretical works on gradient descent biases are not mutually exclusive and are a likely compliment. We emphasize that we do not make any claims on the simplicity of the function, but only on the simplicity – lower effective rank – of the embeddings.

heading: 3.1 LOW-RANK SIMPLICITY BIAS OF DEEP NETWORKS
text: Observation 1. Randomly initialized deep neural networks 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 lower effective rank. We quantify this observation by computing the distribution over the effective rank of the Gram matrix in Figure 1. Here, the weights of the neural networks are initialized using uniform Wi ∼ U(·, ·) or Normal distributions Wi ∼ N (·, ·). The input, output, and intermediate dimensions are 32, giving parameters {Wi} ∈ Rd×32×32 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 small overlap and smoothen 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 ≈ (Wd−1:1X)T (Wd−1:1X). 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) ≤ min (rank(A), rank(B)) (Friedberg et al. (2003)). In Appendix L, we show that as the depth of the model increases, both the effective rank of the Gram matrix and the weights decrease together. Another way to interpret our observation is that for linear models, over-parameterization 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 cannot make the same claims.
Although uniformly sampling under the parameter distribution is an unbiased estimator of the volume of the parameter space, it is certainly possible that a sub-space of the parameters is more likely to be observed under gradient descent. Hence, by naively sampling networks, we may never encounter model parameters 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 2. Deep neural networks trained with gradient descent also learns to map data to simple embedding with low effective rank.
Figure 2 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). Training the model with gradient descent results in a distribution that is still largely dependent on depth; this reaffirms that the role of optimization does not remove the parameterization bias in deep models. In fact, if the 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.

heading: 3.2 IS THE LOW-RANK BIAS SPECIFIC TO GRADIENT DESCENT?
text: Observation 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 converge 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 directly show this in Figure 3 by ablating across various popular choices of optimizers on leastsquares 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 search. All models were trained to zero training error except for randomsearch. For random search, we randomly initialize the network 100, 000 times and take the best performing sam-
ple. As we have seen with gradient descent, the experiment indicates that even when we train with a wide suite of commonly used optimizers, the solution obtained by these models depends on how the model was originally parameterized.

heading: 3.3 CAN THE SIMPLICITY BIAS BE EXPLAINED SOLELY BY THE INITIALIZATION?
text: The previous set of experiments indicate that deeper networks are biased towards low-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 2 normally distributed weights becomes symmetric χ-squared distribution, with 1 degrees of freedom. Hence, one could argue that the converged solutions are low-rank because of the initialization bias.
Observation 4. Deep neural networks are biased towards learning low-rank embeddings regardless of the initialization.
To test whether the initialization of the model affects the rank of the converged solution. We optimize our network W ∈ Rd×32×32 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 4 (left), for models using default initialization, we show that increasing the number of layers decreases the effective rank of the Gram matrix at convergence. We repeat the experiment in Figure 4 (right) by initializing the over-parameterized models with the distribution associated with the 32-layer linear network. Following a similar trend to that of default initialization, we observe that deeper models learn embeddings that are a lower rank than the shallower counterparts. Although initialization is not insignificant, we see that the depth of the model has tight control over the solution in which the model explores. For deeper networks, the majority of the parameter volume is mapped to low-rank embedding (Observation 1), and therefore it is expected that a typical search algorithm
would likely encounter parameters that map to low-rank embeddings regardless of initialization. Similarly, for a shallower network, it would be easier to find a solution with higher rank embeddings.

heading: 3.4 RELATION TO RANDOM MATRIX THEORY
text: In linear models, we have a special case in which the low-rank embedding corresponds to low-rank weights. This enables us to make a natural connection to existing theoretical work from random matrix theory (RMT), which studies the spectral distribution under matrix multilpications (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 1. Let ρ be the effective rank measure defined in Definition 1. For a linear neural network with d-layers, where the parameters are drawn from the same Normal distribution {Wi}di=1 ∼ W , the effective rank of the weights monotonically decreases when increasing the number of layers when dim(W )→∞,
ρ (WdWd−1 . . .W1) ≤ ρ (Wd−1 . . .W1) Proof. See Appendix G.
The theory is preliminary and can only be understood in the context of an infinite width model with random matrices. Yet, we have found in practice that the empirical spectral distribution of finite-width models is well approximated by theory (see Appendix A). 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 to stimulate future research.

heading: 4 OVER-PARAMETERIZATION AS A REGULARIZER
text: Thus far, we have observed that depth acts as a bias for finding functions with low-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 a high-rank, or the network is made too deep, depth could have a converse effect on generalization. Ample evidence from prior works (Szegedy et al. (2015); He et al. (2016)) suggests that over-parameterization 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 as a prior rather than a 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 networks can be used to improve generalization and robustness to overfitting. However, increasing the number of non-linear layers also increases the modeling capacity, thereby making it difficult to isolate the effect of depth.
Nevertheless, 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 lowrank bias in the model without increasing the modeling capacity. The details of our linear overparameterization method are in Appendix B. We observe that such linear over-parameterization improves generalization performance on classification tasks. Furthermore, we find that such implicit regularization outperforms models trained with several choices of explicit regularization. Guo et al. (2020) made a similar empirical observation in the context of model compression where linear over-parameterization improves generalization, but why it works is unexplored.

heading: 4.1 IMAGE CLASSIFICATION WITH OVER-PARAMETERIZATION
text: Using the linear expansion rules in Appendix B, we over-parameterize various architectures and evaluate on a suite of standard image classification datasets: CIFAR10, CIFAR100, ImageNet. All models are trained using SGD with a 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 E).
In Figure 5, we compare a CNN trained without (left) and with (right) our over-parameterization (expansion factor d = 4) on CIFAR100. The CNN consists of 4 convolutional layers and 2 fully connected layers; the architecture details are in Appendix E. 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 σi(A) ≥ σi+1(A) for i < 1 ≤ min(m,n). We observe that both the individual effective weights and the Gram matrix of the overparameterized model is biased towards low-rank weights. Unlike the original, the majority of the singular values of the over-parameterized model are close to zero. When we take a closer look at the weights of the model, both the original and linearly over-parameterized models first exhibit rank contracting behavior throughout training, and then the rank starts to increase again – to the best of our knowledge, this is an unexpected training behavior in larger models that are not explained in prior works, possibly because the isometric, balanced initialization, and infinitesimal assumptions made in prior theoretical works do not hold in practice (visualized in Appendix D).
architecture ImageNet original over-param gain ↑
AlexNet (2x) 57.3 59.1 +1.8 ResNet10 (2x) 62.8 63.7 +0.9 ResNet18 (2x) 67.3 67.7 +0.4
Table 2: ImageNet: We show on existing architectures that linear over-parameterization can improve generalization performance. The benefit plateaus off when using deeper models. We did not see a noticeable improvement starting from ResNet34.
We further quantify the gain in performance from linear over-parameterization in Table 1. The learning rate is tuned per configuration, and we report the best test accuracy throughout the training. We try various over-parameterization configurations and find an expansion factor of 4 to be the sweet spot, with a 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 over-parameterizing models with < 20 layers on image classification.
We scale up our experiments to ImageNet, a large-scale dataset consisting of 1.3 million images with 1000 classes, and show that our findings hold in practical settings. For these experiments, we use standardized 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-parameterization to be reduced for deeper models. This is, in fact, what we observed in Table 2, with moderate gains in AlexNet and less for ResNet10 and even less for ResNet18. In fact, starting from ResNet34, we observe linearly over-parameterized models perform worse than the original. These experiments support our claim that adding too many layers can over-penalize the model.
To find out whether explicit regularizers can approximate the advantages of overparameterization, we directly compare the performance in Table 3 on CIFAR. These regularizers include popular `1 and `2 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 overparameterization to out-perform models trained with explicit regularizers. Moreover, we found that combining norm-based regularizers with over-parameterization further improves perfor-
mance. This discrepancy between implicit and explicit regularization may stem from the fact that over-parameterization receives a combined effect of both gradient descent’s implicit bias and model parameterization’s inductive bias. Therefore, one may need to jointly consider both biases to approximate its effect as an explicit regularizer correctly. Another reason could be that regularizers are inherently different than over-parameterization (Arora et al. (2018)). For example, a model trained with a regularizer will have a non-zero gradient, even at zero training loss, while the over-parameterized model will not.

heading: 5 DISCUSSION
text: We conclude by discussing several implications of our work:
Parameterization matters 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 is also parameterized matters. Even if two models span the same hypothesis space, the way we parameterize the hypothesis space can ultimately determine which solution the model will converge to – recent work has shown that networks with the better neural reparameterizations can find more effective solutions (Hoyer et al. (2019)). The automation of finding the right parameterization also has a 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 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 7 and a short extension to residual networks Appendix H). Understanding the biases induced by these reparameterizations may yield benefits in model analysis and architectural designs.
Deep over-parameterization vs. regularization We have argued that depth acts as an inductive bias toward simple (low-rank) solutions because the relative volume of simple solutions in deeper parameter space is larger, extending prior arguments by Valle-Perez et al. (2019). This effect is qualitatively different than explicit regularization in that it does not change the objective being minimized. Occam’s razor states that the best solution is the simplest that fits the data (as has been formalized in various notions of optimal inference (Solomonoff (1964))). Too strong an explicit regularizer can prefer simple solutions that do not fit the data, which is incorrect when the true solution is, in fact, complex. Picking a parameterization in which simple solutions are more prevalent but not enforced is an alternative way to approximate the idea of Occam’s razor. Our experiments, which show that explicit rank regularization underperforms compared to deep over-parameterization, suggest that this implicit regularization may have advantages.

heading: 6 RELATED WORKS
text: Linear networks Linear networks have been used in lieu of non-linear networks for analyzing the generalization capabilities of deep networks. 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-parameterization induces training acceleration which cannot be approximated by an explicit regularizer. Furthermore, Gunasekar et al. (2017) shows that linear models with gradient descent converge to a minimum nuclear norm solution on matrix factorization. More recently, Li et al. (2020) demonstrated gradient descent acts as a greedy rank minimizer in matrix factorization, and Bartlett et al. (2020; 2021) argues that gradient descent in over-parameterized models lead 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 regime is on matrix factorization with gradient descent under isometric assumptions (Tu et al. (2016); Ma et al. (2018); Li et 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. Note that these work focuses on why gradient descent finds low-rank solutions. Pennington et al. (2018) showed that the input-output Jacobian’s spectral distribution is determined by depth. For non-linear networks, understanding the biases has been mostly empirical, with the common theme that overparameterization 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). 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 act as an implicit regularizer during training. Simplicity bias Recent work has indicated that gradient descent in linear models find max-margin solutions Soudry et al. (2018); Nacson et al. (2019); Gunasekar et al. (2018). Separately, in the perspective of algorithmic information theory, Valle-Perez et al. (2019) demonstrated that deep networks’ parameter space maps to low-complexity functions. Furthermore, Nakkiran et al. (2019b) and Arpit et al. (2017) have shown that networks learn in stages of increasing complexity. Whether these aspects of simplicity bias are desireable has been studied by Shah et al. (2020). Complexity measures A growing number of work has found matrix norm to not be a good measure for characterizing neural networks. Shah et al. (2018) shows that minimum norm solution is not guaranteed 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 an alternative measure. Infinite-width 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 dimensionality of the output space.

heading: A RANDOM MATRIX THEORY IN FINITE MODELS
text: Random matrix theory makes an infinitely large matrix assumption to derive a deterministic spectral distribution of random matrices. This assumption is equivalent to making an infinite width neural network assumption. In Figure 6, we show that the empirical singular-value distribution closely follows that of the theoretical distribution. Even when using a very small weight matrix of size W ∈ R32×32, and more so on larger weight matrices W ∈ R256×256, the singular values sharpen when increasing the number of layers – reaffirming our Theorem 1 and our conjecture.
B EXPANDING A NON-LINEAR NETWORK
A deep non-linear neural network with l layers is parameterized by a set of l weights W = {W1, . . . ,Wl}. The output of the j-th layer is defined as φj = ψ(fWj (φj−1)), for some non-linear function ψ and input feature φj−1. The initial feature map is the input φ0 = x, and the output is the final feature map y = φl. We can expand a model by depth d by expanding all linear layers, i.e. redefining fWj → fWdj ◦· · ·◦fW 1j ∀ j ∈ {1, ..., l}. We illustrate this in Figure 7. We describe this operation for fully connected and convolutional layers.
Fully-connected layer A fully-connected layer is parameterized by weight W ∈ Rm×n. One can overparameterize W as a series of linear operators defined as ∏d i=1Wi. For example, when d = 2, W → W2W1, where W2 ∈ Rm×h and W1 ∈ Rh×n for some hidden dimension h. The variable h is referred to as the width of the expansion and can be arbitrarily chosen. In our experiments, we choose h = n unless stated otherwise. Note that h < min(m,n) would result in a rank bottleneck and explicitly reduce the underlying rank of the network.
Convolutional layer A convolutional layer is parameterized by weight W ∈ Rm×n×k×k, where m and n are the output and input channels, respectively, and k is the dimensionality of the convolution kernel. For convenience, we over-parameterize by adding 1×1 convolution operations. Wd ∗Wd−1 ∗ · · · ∗W1, where Wd ∈ Rm×h×1×1, Wd−1, ...,W2 ∈ Rh×h×1×1 and W1 ∈ Rh×n×k×k. Analogous to the fully-connected layer, we choose h = n to avoid rank bottleneck.
The work by Golubeva et al. (2021) explores the impact of width h. Similar to their findings, we observed using the larger expansion width to slightly improve performance. We use h = 2n for our ImageNet experiments.

heading: C COMPARISONS OF RANK MEASURES AND KERNEL DISTANCE FUNCTIONS
text: The rank of a 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 a matrix to be full-rank. In addition, simply counting the number of non-zero singular values may not indicate what we care about in practice: the relative impact of the i-th basis compared to the j-th basis. In a typical image classification setup, we observed that the norm of the matrix often increases during training. This is highlighted by the nuclear norm in Figure 8. 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 thresholded-rank, where the smallest singular values are thresholded after normalization (re-weighting the singular values based on relative contribution). However, thresholded rank is very sensitive to the threshold value one chooses (shown below); hence we used effective rank to avoid this issue. Definition 2 (Effective rank). Roy & Vetterli (2007)
For any matrix A ∈ Rm×n, the effective rank ρ is defined as the Shannon entropy of the normalized singular values:
ρ(A) = − min(n,m)∑ i=1 σ̄i log(σ̄i),
where σ̄i = σi/ ∑ j σj are the normalized singular values such that ∑ i σ̄i = 1. It follows that ρ(A) ≤ rank(A). This measure is also known as 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 metrics 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 3 (Threshold rank). For any matrix A ∈ Rm×n, the threshold rank τ -Rank is the count of non-small singular values after normalization:
τ -Rank(A) = min(n,m)∑ i=1 1[σ̄i ≥ τ ],
where 1 is the indicator function, and τ ∈ [0, 1) is the threshold value. σ̄i 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 a drastically different scalar representation of rank can emerge. Potentially, a better usage of threshold rank is to measure the AUC when varying the threshold.
Related to the definition of the threshold rank, stable rank operates on the normalized squared-singular values:
Definition 4 (Stable rank). Vershynin (2018)
For any matrix, A ∈ Rm×n, the stable rank is defined as:
SRank(A) = ‖A‖2F ‖A‖2 =
∑ σ2i σ2max ,
Where σi 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 a 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-emphasizes the small singular values un-proportionately due to the squared-operator. We observed that the largest singular values often get over exaggerated in neural networks and hence we often found that SRrank converges to values close to 1, making insightful observations impractical.
Lastly, the nuclear norm has been considered as the de facto measure of rank for the task of matrix factorization/completion, with low nuclear-norm indicating that the matrix is low-rank:
Definition 5 (Nuclear norm). For any matrix A ∈ Rm×n, the nuclear norm operator is defined as:
‖A‖∗ = tr( √ AAT ) = min(n,m)∑ i σi(A)
Where σi 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 8 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-parameterized models with various depths on leastsquares.
In Figure 9, we repeat our least-squares experiments from our main paper using thresholded rank with various threshold values τ = {0.001, 0.005, 0.01}. We show that the effective rank indeed correlates well 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 in a 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 our observations. This is further highlighted in medium and low task-rank settings, where all models reach zero-training error, yet the test-loss differs.
Kernel distance functions In our work we used cosine kernels to construct the Gram matrices. 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 10 that Gram matrices constructed with kernel distance functions such as linear kernels and correlation kernels also exhibit the low-rank simplicity bias.

heading: D SINGULAR VALUE DYNAMICS OF WEIGHTS
text: In Figure 11, we visualize the singular values of the individual weights when training on CIFAR100 image classification for the first 120 epochs. The cross-sections indicate the singular value distribution at that specific epochs. For the over-parameterized model, the effective rank is computed on the effective weight. On the left, we plot the unnormalized singular values and observe that the norm of the singular values increases throughout training for all layers except for the last classification layer in the over-parameterized model. When we normalized the distribution by the largest singular value σ0 (right), we observed that the distribution becomes sharper early in training but does not change much throughout.
To get a better sense of how the distribution evolves over time by overlaying the distribution on top of each other. In Figure 12, 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.

heading: E TRAINING DETAILS AND MODEL ARCHITECTURE
text: 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 each step. For all the models, we use random-horizontal-flip and random-resize-crop for data augmentation. The training details for ImageNet can be found in https://github.com/pytorch/examples/blob/master/imagenet. When linearly over-parameterizing our models, we bound the variance of the weights using Kaiming initialization 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-parameterize 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 ∈ R32×32×3
Convolution 3→ 64, MaxPool, ReLU Convolution 64→ 128, MaxPool, ReLU
Convolution 128→ 256, MaxPool, ReLU Convolution 256→ 512, ReLU
GlobalMaxPool
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 ImageNet experiments (since we used up to 8x expansion). The one hyper-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 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.

heading: F DIFFERENTIAL EFFECTIVE RANK
text: 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/singular-value spectrum assumes a probability distribution in the asymptotic case.
Definition 6 (Differential effective rank). For any matrix A ∈ Rm×n as min(m,n) → ∞ the singular values assume a probability distribution p(σ). Then, we define the differential effective rank ρ as:
ρ(A) = − ∫ σ σ c log( σ c )p(σ)dσ (4)
where p(σ) is the singular value density function and c = ∫ σp(σ)dσ is the normalization constant.

heading: G PROOF OF THEOREM 1
text: To prove Theorem 1, we leverage the findings from random matrix theory, where the singular values assume a 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 W1 to WL are drawn i.i.d from a Gaussian. Characterizing such density function is, in general intractable, or otherwise very difficult. However, in the asymptotic case where dim(W ) → ∞ and W is square, the density function admits the following concise closed-form (Eq. 13 of Pennington et al. (2017) derived from Neuschel (2014)):
p(σ(φ)) = 2
π
√ sin3(φ) sinL−2(Lφ)
sinL−1((L+ 1)φ) σ(φ) =
√ sinL+1((L+ 1)φ)
sin(φ) sinL(Lφ) , (5)
where σ denotes singular values (parameterized by φ ∈ [0, πL+1 ]) and p denotes the probability density function of σ for σ ∈ [0, σmax], and σ2max = L−L(L+ 1)L+1. 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: ρ(W ) = − ∫ σmax 0 σ c log( σ c )p(σ) dσ , (6)
We now write this integral in terms of φ as the integration variable, such that we can leverage the density function in Eqn. 5. Using the change of variable, we have:
ρ(W ;L) = − ∫ π L+1
0
σ(φ)
c log(
σ(φ) c ) ( − p(σ(φ))σ′(φ) ) dφ , (7)
where σ′(φ) = ddφσ(φ). Note that the integral limits [0, σmax] on σ respectively translate 3 into [ πL+1 , 0] on φ. Computing the inner probability term, we get:
−p(σ(φ))σ′(φ) = 1 2π
( 1 + L+ L2 − L(L+ 1) cos(2φ)− (L+ 1) cos(2Lφ) + L cos(2(1 + L)φ) ) csc2(Lφ) .
As ρ(W ;L) is differentiable in L, ρ(W ;L) decreases in L if and only if dρdL < 0. Since integration and 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.
The integrand can be expressed as:
− σ(φ) c log( σ(φ) c ) ( − p(σ(φ))σ′(φ) ) = hv2 log(u) √ u , (8)
3note that the direction of integration needs to flip (by multiplying by -1) to account for flip of the upper and lower limits.
where the variables h, v and u are defined as:
h = 1
4π
( 1 + L(L+ 1)(1− cos(2φ))− (1 + L) cos(2Lφ) + L cos(2(1 + L)φ) ) v = csc(Lφ) (9)
u = LL
(L+ 1)L+1 csc(φ) sin−L(Lφ) sinL+1((L+ 1)φ) . (10)
Now it is straightforward to differentiate the integrand and show that it has the following form:
d
dL hv2 log(u)
√ u = v(h(2 + log(u))vu′ + 2 log(u)u(vh′ + 2hv′))
2 √ u
(11)
We should now integrate the above form w.r.t. φ from 0 to πL+1 and examine the sign of the integrated form. The Eqn. 11 is positive for smaller φ and negative for larger φ. Furthermore, the area under the positive region is smaller than the negative one; hence, the total value of the integral is negative. This completes the proof that the singular values decrease as a function of the number of layers.
The proof here considers the asymptotic case when dim(W )→∞. This limit case allowed us to use the probability distribution of the singular values. Although we do not provide proof for the finite case, our results demonstrate that it holds empirically in practice (see Figure 1).

heading: H EXTENSION TO RESIDUAL CONNECTIONS
text: 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-ofthe-art models today are more than just depth. From cardinality Xie et al. (2017) to normalization Ioffe & Szegedy (2015) and residual connections He et al. (2016), numerous facets of parameterization have become a fundamental recipe for a successful model (see Figure 7). Of these, residual connections have the closest relevance to our work.
What is it about residual connections that allow the model to scale arbitrarily in depth? while vanilla feed-forward networks cannot? One possibility is that beyond a certain depth, the rank of the solution space reduces so much that good solutions no longer exist. In other words, the implicit rank-regularization 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 tensor for convolutions). There are two interpretations of 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 13 confirm this intuition. ResNets, unlike linear networks, do not exhibit a monotonic rank contracting behavior and the effective rank plateaus after 8 layers, regardless of using batch-normalization or not. Furthermore, preliminary experiments on least-squares using linear residual networks indicate that the effective rank of the solution space is also bounded by the number of layers in the shortest and longest path from the inputs to the outputs. A thorough study on the relationship between residual connections and rank is left for future work.

heading: I LEAST-SQUARES LEARNING DYNAMICS
text: The learning dynamics of a linear network change when over-parameterized. Here, we derive the effective update rule on least-squares using linear neural networks to provide motivation on why they have differing update dynamics. For a single-layer linear network parameterized by W , without bias, the update rule is:
W (t+1) ←W (t) − η∇W (t)L(W (t), x, y) (12)
= W (t) − η∇W (t) 1
2 (y −W (t)x)2 (13)
= W (t) − η(W (t)xxT − yxT ) (14)
Where η is the learning rate. Similarly, the update rule for the two-layer network y = Wex = W2W1x can be written as:
W (t+1) 1 ←W (t) 1 − η(W (t) 2 ) T (W (t)e xx T − yxT ) (15)
W (t+1) 2 ←W (t) 2 − η(W (t)e xxT − yxT )(W (t) 1 ) T (16) (17)
Using a short hand notation for ∇L(t) = W (t)e xxT − yxT , we can compute the effective update rule for the two-layer network:
W (t+1)e = W (t+1) 2 W (t+1) 1 (18)
= W (t)e −
first orderO(η)︷ ︸︸ ︷ η(W
(t) 2 W (t)T 2 ∇L(t) +∇L(t)W (t)T 1 W (t) 1 ) + second orderO(η2)︷ ︸︸ ︷ η2∇L(t)W (t)Te ∇L(t) (19)
≈W (t)e − η(P2∇L(t) +∇L(t)PT1 ) (20)
Where P (t)i = W (t) i W (t)T i are the preconditioning matrices. The higher order terms can be ignored if the step-size is chosen sufficiently small.
(General case) For a linear network with d-layer expansion, the update for layer 1 ≤ i ≤ d is:
W (t+1) i ←W (t) i − η
weights> i︷ ︸︸ ︷ (W
(t) d · · ·W (t) i+1) T original gradient︷ ︸︸ ︷ (W (t)e xx T − yxT ) weights< i︷ ︸︸ ︷ (W (t) i−1 · · ·W (t) 1 ) T (21)
Denoting Wj:i = Wj · · ·Wi+1Wi for j > i, the effective update rule for the end-to-end matrix is:
W (t+1)e = ∏
1<i<d
W (t+1) i = ∏ 1<i<d (Wi − ηW (t)Td:i+1∇L(t)WTi−1:1) (22)
= W (t)e − η ∑
1<i<d
Wd:i+1W T d:i+1∇L(t)WTi−1:1Wi−1:1 +O(η2) + · · ·+O(ηd) (23)
≈W (t)e − η ∑
1<i<d
Wd:i+1W T d:i+1︸ ︷︷ ︸
left precondition
∇L(t)︸ ︷︷ ︸ original gradient WTi−1:1Wi−1:1︸ ︷︷ ︸ right precondition
(24)
The update rule for the general case has a much more complicated interaction of variables. For the edge i = 1 and i = p the left and right preconditioning matrix is an identity matrix respectively.

heading: J RANK-LANDSCAPE
text: We visualize the effective rank landscape of the effective weights in Figure 14 and Gram matrices in Figure 15. We use single and two-layer linear networks for effective-rank landscape. We use two-layer, and four-layer ReLU networks 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 is constructed by moving along random directions u, v. We observe that over-parameterized linear and non-linear models almost always exhibit a lower-rank landscape than their shallower counterparts.

heading: K GRAM MATRIX AND NON-LINEARITIES
text: In Figure 16, 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 popularized 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.

heading: L RELATIONSHIP BETWEEN WEIGHT AND EMBEDDINGS
text: 1.4 1.6 1.8 2.0 2.2 2.4 2.6 2.8
effective rank of weight
1.2
1.4
1.6
1.8
2.0
ef fe
ct iv
e ra
nk o
f k er
ne l
1
2
3
4
5
6
7
8
de pt
h
Figure 17: Rank relation of kernel and weight: Each point represents randomly drawn network. For each network, we compute the rank on the effective weight and also the linear kernel. The kernel is constructed from the MNIST dataset. The rank of the kernels and weights have a linear relationship.
We show that there is an almost one-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.

Review summaries:
This paper conduct several controlled experiments and arrive at the following results: - Deep networks (both linear and non-linear) are biased towards learning low-rank embeddings at initialization. - This low-rank bias exists even after the training is done regardless of the initialization or training algorithm.  This paper also proposes a new regularization method which is adding extra linear layers which does not increase the network's expressivity but biases the network more towards learning low-rank solutions.

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

The paper explores the effect of depth on a continuous estimate of rank (effective rank) of the data embeddings computed by feed-forward neural networks.  On artificial datasets, the paper shows that at initialization (with common uniform or normal weight distributions), the effective rank of both linear and non-linear MLPs decreases with depth, and this is preserved after training. The results does not extend to network architectures with skip-connections such as ResNets.  The authors claim that this low-rank bias of the embeddings help generalization on natural datasets, and show that a reparametrization of common architectures where the linear layers are replaced by products of linear layers improves test accuracy on CIFAR-10 and CIFAR-100.