Heavy-Tailed Universality Predicts Trends in Test Accuracies for Very Large Pre-Trained Deep Neural Networks

Introduction

We are interested in the following general question.

Given two or more Deep Neural Networks (DNNs) with the same or similar architectures, trained on the same dataset, but trained with different solvers, parameters, hyper-parameters, regularization, etc., can we predict which DNN will have the best test accuracy, and can we do so without peeking at the test data?

This question is both theoretical and practical. Theoretically, solving this would help to understand why this class of machine learning (ML) models performs as well as it does in certain classes of applications. Practically, there are many motivating examples. Here are two.

Automating architecture search. Developing DNN models requires significant architecture engineering, so there is interest in automating the design of DNNs. Current methods can produce a series of DNNs subject to given general architecture constraints, but the models must be evaluated using cross validation (CV). DNNs have so many adjustable parameters that even when using CV it is possible to leak information from the test sets into the training data, thus producing brittle, non-robust models. It is thus of interest to have design principles and quality metrics that do not depend on the test data and/or the labels.

Fine-Tuning Pre-trained Models. Since one often does not have enough labeled data to train a large DNN from scratch, many modern engineering solutions can re-use widely-available pre-trained DNNs, fine-tuning them on smaller data sets. This technique often works extremely well for visual tasks, using DNNs pre-trained on ImageNet; and recently it has become feasible for complex natural language processing (NLP) tasks. Sometimes, however, these fine-tuned models become brittle and non-robust—due to overtraining, because information leaks from the test set into the training data. Here, it would also be very helpful to be able to fine-tune large, pre-trained DNNs without needing to peek at the test data.

To predict trends in the generalization accuracy of a series of DNN architectures, VC-like theories offer theoretical bounds on the generalization accuracy. Practically, such capacity metrics can guide the theoretical development of new regularizers for traditional ML optimization problems (e.g., counterfactual expected risk minimization ), but the bounds themselves are far too loose to be used directly. Moreover, since the early days of NN research, it was known that VC theory could (probably) not be directly applied to the seemingly wildly non-convex optimization problem implicitly posed by NNs. (This has caused some researchers to suggest we need to rethink regularization in DNNs entirely.)

In light of this, Liao et al. used an appropriately-scaled, data-dependent Product Norm capacity control metric to bound the worst-case generalization error for several small (non production-quality, but still interesting) DNN models, and they showed that the bounds are remarkably tight. There is, in fact, a large body of work on norm-based capacity control metrics, both recent, e.g., and , as well as much older . Much of this work has been motivated by the observation that parameter counting and more traditional VC-based bounds tend to lead to vacuous results for modern state-of-the-art DNNs, e.g., since modern DNNs are heavily over-parameterized and depend so strongly on the training data.

As with most theoretical studies, Liao et al.’s approach and intent differ greatly from ours. They seek worst-case complexity bounds, motivated to reconcile discrepancies with more traditional statistical learning theory, and they apply them (to quite small-scale NNs). To address our main question, we seek an average-case or typical case (for realistic large-scale NNs) complexity metric, viable in production to guide the development of better DNNs at scale. Bounding a small toy model does not necessarily mean that the individual weight matrix norms in production-quality DNNs will be directly comparable. In particular, it does not mean that we can directly compare the individual weight matrix norms across layers in different, and more complex, architectures. Also, Liao et al. had to modify the DNN optimization loss function. This means that their approach cannot be tested/evaluated on any existing pre-trained DNN architecture, e.g., the VGG and ResNet models, widely-used today in industry. Still, their results do suggest that a Product Norm may work well as a practical capacity metric for large, and perhaps even pre-trained, production-quality DNNs. We will evaluate this and show that it does. More generally, to predict trends in the test accuracies, one needs some more Universal empirical metric that transfers across DNN architectures.

Recent work by Martin and Mahoney suggests a Universal empirical metric to characterize the amount of Implicit Self-Regularization and, accordingly, the generalization capacity, for a wide range of pre-trained DNNs. A short version of is available as . The long version contains many more results and a much more detailed exposition. The metric (defined below) involves the power law (PL) exponents, $\alpha$, of individual layer weight matrices, $\mathbf{W}$, as determined by fitting the Empirical Spectral Density (ESD), $\rho(\lambda)$, to a PL distribution. Looking in detail at a series of models, like AlexNet, VGG, ResNet, etc, they observe that the (linear) layer weight matrices almost always follow a PL distribution, and fitted PL exponents nearly all lie within a universal range $\alpha\in$. Analysis of a small model (MinAlexNet) demonstrates that smaller PL exponents $\alpha$ correspond to better generalization. Subsequent work demonstrated Heavy-Tailed (HT) behavior in nearly every pre-trained architecture studied, e.g., across nearly $7500$ layer weight matrices (and 2D feature maps), including DNNs pre-trained for computer vision tasks on ImageNet, and for several different NLP tasks.

When one observes good empirical PL fits of ESDs of correlations of layer weight matrices, we say the DNN exhibits Heavy-Tailed behavior. Motivated by these empirical observations, and using the Universality properties of Heavy-Tailed Random Matrix Theory (HT-RMT), Martin and Mahoney developed a theory of Heavy-Tailed Self-Regularization (HT-SR) for DNNs . We build on and extend that theory here.

In Statistical Physics, Universality of PL exponents is very non-trivial, and it suggests the presence of a deeper, underlying, Universal mechanism driving the system dynamics . It is this Heavy Tailed Mechanistic Universality (HT-MU), as we call it, that originally motivated our study. HT-MU applies to the analysis of complicated systems, including many physical systems, traditional NNs , and even models of the dynamics of actual spiking neurons. Indeed, the dynamics of learning in DNNs seems to resemble a system near a phase transition, such as the phase boundary of spin glass, or a system displaying Self Organized Criticality (SOC), or a Jamming transition . Of course, we can not say which mechanism, if any, is at play. Instead, we use the machinery of HT-RMT as a stand-in for a generative model of the weight matrices in DNNs, to catalog and model the HT behavior of DNNs. Perhaps the most well-known Universality in RMT is associated with the Gaussian Universality class, where the sum of many random variables drawn from a wide range of distributions is “approximately Gaussian,” e.g., in the sense that the sum approaches a suitably-normalized Gaussian distribution. As briefly reviewed in Appendix A, HT Universality makes analogous (but, admittedly, more complicated) statements for random variables drawn from distributions in which the tails decay more slowly than those in the Gaussian Universality class . This Universality suggests that we look for a Universal Capacity Control Metric To be clear, this metric is Universal, not in the sense that it applies “universally” to every possible DNN, but in the Statistical Physics sense that it applies to matrices within/across HT “Universality” classes. to address our main question.

We evaluate the Product Norm capacity control metric on a wide range of large-scale pre-trained production-level DNNs, including VGG and ResNet series, demonstrating that it correlates well with reported average test accuracies across many series of models. While norm-based metrics have been applied to small models, to our knowledge, evaluating this metric to predict trends in test accuracies of large-scale pre-trained models has never (until now) been reported.

We introduce a new methodology to analyze the performance of large-scale pre-trained DNNs, using a phenomena observed in HT-SR Theory. We construct a Universal capacity control metric to predict average DNN test performance. This metric is a weighted average of layer PL exponents, $\hat{\alpha}$, weighted by the log Throughout, we use log base 10. of the Spectral norm (i.e., maximum eigenvalue $\lambda^{max}$) of layer correlation matrices:

We apply our Universal capacity control metric $\hat{\alpha}$ to a wide range of large-scale pre-trained production-level DNNs, including the VGG and ResNet series of models, as well as many others. This metric correlates very well with the reported average test accuracies across many series of pre-trained DNNs.

We provide a derivation for a relation between our Universal capacity control metric $\hat{\alpha}$ and the well known Product Norm capacity control metric, i.e, in the form of the average log of the squared Frobenius norm:

We do not make precise the error in “$\approx$” but our derivation makes clear that we expect the approximation to be good for smaller $\alpha$ and less good for larger $\alpha$.

There is a tradeoff here: our $\hat{\alpha}$ metric has two parameters ($\alpha$ and $\lambda^{max}$), as opposed to the Product Norm capacity control metric, which has one ($\|\cdot\|^{2}_{F}$), and it is more expensive to compute, but it does perform better. Informally, as opposed to looking only at the “size” or “shape” of a model, e.g., as with a norm-based metric, the parameters $\lambda_{l}^{max}$ and $\alpha_{l}$ take into consideration both the size and the shape of the model.

For both our Universal $\hat{\alpha}$ metric and the Product Norm metric, our empirical results are, to our knowledge, the first time such theoretical capacity metrics have been reported to predict (trends in) the test accuracy for pre-trained production-level DNNs. In particular, this illustrates the usefulness of these norm-based metrics beyond smaller models such as MNIST, CIFAR10, and CIFAR100. Our results, including for both our Universal metric and the Product Norm metric we consider, can be reproduced with the WeightWatcher package https://pypi.org/project/WeightWatcher/; and our results suggest that our “practical theory” approach is fruitful more generally for engineering good algorithms for realistic large-scale DNNs.

A shorter conference version of this paper, without the appendices, has appeared as .

Brief Overview of Heavy-Tailed Self-Regularization

Here, we briefly review Martin and Mahoney’s Theory of Heavy-Tailed Self-Regularization (HT-SR) . See Appendix A for more details.

Write the Energy Landscape (or optimization function, parameterized by $\mathbf{W}_{l}$s and $\mathbf{b}_{l}$s) for a typical DNN with $L$ layers, with activation functions $h_{l}(\cdot)$, and with $N\times M$ weight matrices $\mathbf{W}_{l}$ and biases $\mathbf{b}_{l}$, as:

Typically, this model would be trained on some labeled data $\{d_{i},y_{i}\}\in\mathcal{D}$, using Backprop, by minimizing the loss $\mathcal{L}$. For simplicity, we do not indicate the structural details of the layers (e.g., Dense or not, Convolutions or not, Residual/Skip Connections, etc.).

In the HT-SR Theory, we analyze the eigenvalue spectrum (the ESD) of the associated correlation matrices . From this, we can characterize the amount and form of correlation (and therefore the implicit self-regularizartion) present in the DNN’s weight matrices. For each layer matrix $\mathbf{W}_{l}$, of size $N\times M$, construct the associated $M\times M$ (uncentered) correlation matrix $\mathbf{X}_{l}$. Dropping the $L$ and $l,i$ indices, we have $\mathbf{X}=\frac{1}{N}\mathbf{W}^{T}\mathbf{W}.$ If we compute the eigenvalue spectrum of $\mathbf{X}$, i.e., $\lambda_{i}$ such that $\mathbf{X}\mathbf{v}_{i}=\lambda_{i}\mathbf{v}_{i},$ then the ESD of eigenvalues, $\rho(\lambda)$, is just a histogram of the eigenvalues. Using HT-SR Theory , we can characterize the correlations in a weight matrix by examining its ESD, $\rho(\lambda)$. It can be well-fit to a power law (PL) distribution, given as $\rho(\lambda)\sim\lambda^{-\alpha},$ which is (at least) valid within a bounded range of eigenvalues $\lambda\in[\lambda^{min},\lambda^{max}]$.

When we observe HT behavior in $\mathbf{W}$, or rather its correlation matrix $\mathbf{X}$, we essentially use HT-RMT as a generative model. We say that we model $\mathbf{W}$ as if it is a random matrix, $\mathbf{W}^{rand}(\mu)$, drawn from a Universality class of HT-RMT (i.e., VHT, MHT, or WHT, as defined below). To characterize this HT-MU behavior, we use a HT variant of RMT and use HT random matrices to elucidate different Universality classes. Let $\mathbf{W}(\mu)$ be an $N\times M$ random matrix with entries chosen i.i.d. from

where $W_{0}$ is the typical order of magnitude of $W_{i,j}$, and where $\mu>0$. There are at least 3 different Universality classes of HT random matrices, defined by the range $\mu$ takes on:

$0<\mu<2$: VHT: Universality class of Very Heavy-Tailed (or Lévy) matrices;

$2<\mu<4$: MHT: Universality class of Moderately Heavy-Tailed (or Fat-Tailed) matrices;

$4<\mu$: WHT: Universality class of Weakly Heavy-Tailed matrices.

Heavy-Tailed Mechanistic Universality and Capacity Control Metrics

From prior work , we expect that smaller PL exponents of the ESD imply more regularization and therefore better generalization. Since smaller norms of weight matrices often correspond to better capacity control , we would like to relate the empirical PL exponent $\alpha$ to the empirical Frobenius norm $\|\mathbf{W}\|_{F}$. At least naïvely, this is a challenge, since smaller PL exponents often correspond to larger matrix norms (and thus worse generalization!). See Appendices C and D for more details. To resolve this apparent discrepancy, we will exploit HT-MU to propose a Universal DNN complexity metric.

The PL exponent $\alpha$ is a complexity metric for a single DNN weight matrix, with smaller values corresponding to greater regularization . It describes how well that matrix encodes complex correlations in the training data. Thus, a natural class of complexity or capacity metrics to consider for a DNN is to take a weighted average There are several reasons we don’t want an unweighted average: an unweighted average behaves differently for HT random matrices than for well-trained DNN weight matrices, and so it would not be Universal; we want a metric that relates the $\alpha$ of HT-SR Theory with known capacity control metrics such as norms of weight matrices, and including weights permits this flexibility; we want weights to encode information that “larger” matrices are somehow more important; and unweighted averages, while sometimes providing predictive quality, do not perform as reliably well. See Appendices C and D for more details. of the PL exponents, $\alpha_{l,i}$, for each layer weight matrix $\mathbf{W}_{l,i}$:

Here, the smaller $\hat{\alpha}$, the better we expect the DNN to represent training data, and (presumably) the better the DNN will generalize. The main question is: what are good weights $b_{l,i}$?

As we now show, we can extract the weighted average $\hat{\alpha}$ directly from the more familiar Product Norm, by exploiting both HT Universality, and its finite-size effects, arising in DNN weight matrices.

Product Norm Measures of Complexity.

It has been suggested that the complexity, $\mathcal{C}$, of a DNN can be characterized by the product of the norms of layer weight matrices,

where $\|\mathbf{W}\|$ is, e.g., the Frobenius norm . (Here, we can use either $\|\mathbf{W}\|$ or $\|\mathbf{W}\|^{2}$, and one can view $\mathcal{C}$ as akin to a data-dependent VC complexity.) To that end, we consider a log complexity

and we define the average log norm of weight matrices (where $N_{L}$ is the number of layers) as

A Universal, Linear, PL–Norm Relation.

Based on our empirical results and theoretical considerations, we propose a simple linear relation between the (squared) Frobenius norm $\|\mathbf{W}\|^{2}_{F}$ of $\mathbf{W}$, the PL exponent $\alpha$, and the maximum eigenvalue $\lambda^{max}$ of $\mathbf{X}$ (i.e., the spectral norm $\|\mathbf{X}\|_{2}=\frac{1}{N}\|\mathbf{W}\|^{2}_{2}$):

To our knowledge, this is the first time this PL–Norm relation has been noted in the literature (although prior work has considered norm bounds for HT data ). A few comments on Eqn. (3.3). First, it provides a connection between the PL parameter $\alpha$ of HT-SR Theory and the weight norm $\|\mathbf{W}\|^{2}_{F}$ of more traditional statistical learning theory. Second, it has a structural form like that of the well-known Hausdorff dimension . Third, it shows that PL exponents can alternatively be interpreted (up to the $\frac{1}{N}$ scaling) as the Stable Rank in Log-Units:

Our justification for proposing Eqn. (3.3) is three-fold.

We derive Eqn. (3.3) in the special case of very small PL exponent, $\alpha\rightarrow 1$ ($\mu\rightarrow 0$), for an $N\times M$ matrix $\mathbf{W}^{rand}(\mu)$ (with $N=M$, or $Q=1$, where $Q=N/M$). In particular, while this is a limiting statement, we expect to observe small deviations from this when we are not in the limit.

For finite-size random matrices $\mathbf{W}^{rand}(\mu)$, we expect the MHT Universality class, $\mu\in(2,4)$, to behave like the VHT Universality class, $\mu\in(1,2)$. Because of this similarity, we expect that we can extend Eqn. (3.3), approximately, to larger PL exponents. For $N\sim\mathcal{O}(100-1000)$, $\alpha\log\lambda^{max}$ increases nearly linearly with $\log\|\mathbf{W}^{rand}(\mu)\|^{2}_{F}$ as $\mu$ increases. For larger $N$, the relation saturates for large $\mu$. See Appendix B.

As evidence of HT-MU, we observe empirically that Eqn. (3.3) also applies, approximately, to the real DNN weight matrices $\mathbf{W}$. We see that $\alpha\log\lambda^{max}$ is positively correlated with $\log\|\mathbf{W}\|^{2}_{F}$ as $\alpha$ increases, and even shows similar saturation effects at large $\alpha$. See Appendix C.

Finally, based on Eqn. (3.3), we choose the weights in Eqn. (3.1) to be the log of the corresponding maximum eigenvalues of $\mathbf{X}$. That is, for a given $l,i$, we have the weights in Eqn. (3.1) as

Then, we define the complexity metrics for Linear and Convolutional Layers as follows:

where, for Conv2D Layers, we relate the “norm” of the 4-index Tensor $\mathbf{W}_{l}$ to the sum of the $n_{l}=c\times d$ terms for each feature map. This lets us compare the Product Norm to the weighted average of PL exponents as follows:

Given these connections, in Section 4, we will use $\hat{\alpha}$ to analyze numerous pre-trained DNNs.

The PL–Norm Relation: Deriving a Special Case of Eqn. (3.3).

Here, we derive Eqn. (3.3) in the special case of very small PL exponent, as $\mu\rightarrow 0$, for an $N\times M$ random matrix $\mathbf{W}$, with $M=N,Q=1$, and with elements drawn from Eqn. (A.3). We derive Eqn. (3.3) at what is sometimes pejoratively known as “at a physics level of rigor.” That is fine, as our justification ultimately lies in our empirical results. Recall our goal: to derive a very simple expression relating fitted PL exponents and Frobenius norms that is usable by practical engineers working with state-of-the-art models, i.e., not simply small toy models. There is very little “rigorous” work on HT-RMT, less still on understanding finite-sized effects of HT Universality. Hopefully, our results will lead to more work along these lines. We seek a relation good in the region $\mu\in$, and we will extend the $\mu\sim 0$ results to this full region. That is, we establish this as an asymptotic relation for the VHT Universality class for very small exponents.

To start, recall that $\|\mathbf{W}\|_{F}^{2}=\mbox{Trace}[\mathbf{W}^{T}\mathbf{W}]=N\;\mbox{Trace}[\mathbf{X}].$ Since, $\mu\gtrsim 0$, the eigenvalue spectrum is dominated by a single large eigenvalue, it follows that

where $\lambda^{max}$ is the largest eigenvalue of the matrix $\mathbf{X}$ (with the $1/N$ normalization). Taking the log of both sides of this expression and expanding leads to

Thus, for a parameter $\alpha$ satisfying Eqn. (3.3), we have

The relation between $\alpha$ and $\mu$ for the VHT Universality class is given in Eqn. (A.4a) as $\alpha=\frac{1}{2}\mu+1.$ Thus, to establish our result, we need to show that

To do this, we use the relation of Eqn. (A.5) for the tail statistic, i.e., that $\lambda^{max}\approx N^{4/\mu-1}.$ Taking the log of both sides gives

Finally, we can form the Taylor Series for $\dfrac{1}{4/\mu-1}$ around, e.g., $\mu=1.15\approx 1$, which gives

This establishes the approximate—and rather surprising—linear relation we want for $\mu\in$ for the VHT Universality class of HT-RMT.

Empirical Results on Pre-trained DNNs

Here, we summarize our empirical results. We only consider Linear and Conv2D layers because we only examine series of commonly available, open source, pre-trained DNNs with these kinds of layers. All models have been trained on ImageNet, and reported test accuracies are widely available. Throughout, we use Test Accuracies for the Top1 errors (where Accuracy = 100 - Top1 error). We see similar results for Top5 errors. We emphasize that, for our analysis, we do not need to retrain these models—and we do not even need the test data!

We first look at the VGG class of models, comparing the log norm and the Universal $\hat{\alpha}$ metrics. See Figure 1 and Table 1 for a summary of the results. Figures 1(a) and 1(b) show both the average log Frobenius norm, $\langle\log\|\mathbf{W}\|_{F}\rangle$ of Eqn. (3.2), and the weighted average PL exponent, $\hat{\alpha}$ of Eqn. (3.4), as a function of the reported (Top1) test accuracy for the series of pre-trained VGG models, as available in the pyTorch package. https://pytorch.org/ These models include VGG11, VGG13, VGG16, and VGG19, as well as their more accurate counterparts with Batch Normalization, VGG11_BN, VGG13_BN, VGG16_BN and VGG19_BN. Table 1 provides additional details.

Across the entire series of architectures, reported test accuracies increase linearly as each metric, $\langle\log\|\mathbf{W}\|_{F}\rangle$ and $\hat{\alpha}$, decreases. Moreover, whereas the log norm relation has 2 outliers, VGG13 and VGG13_BN, the Universal $\hat{\alpha}$ metric shows a near perfect linear relation across the entire VGG series.

ResNet Models.

We next look at the ResNet class of models. See Figure 2 and Table 2 for a summary of the results. Here, we consider a set of 15 different pre-trained ResNet models, of varying sizes and accuracies, ranging from the small ResNet10 up to the largest ResNet152 models, as provided by the OSMR sandbox, https://github.com/osmr/imgclsmob developed for training large-scale image classification networks for embedded systems. Again, we compare the reported (Top1) test accuracy versus the average log norm $\langle\log\|\mathbf{W}\|_{F}\rangle$ and the Universal $\hat{\alpha}$ metrics.

As with the VGG series, both metrics monotonically decrease as test accuracies decrease for ResNet series, and both metrics have a few large outliers off the main line relation. See Figures 2(a) and 2(b). In particular, the log norm metric has several notable outliers, including resnet18_wd2, resnet18_wd3_d4, resnet34, and resnet10. The $\hat{\alpha}$ metric shows a slightly better relation, with resnet18_wd2 more in line, and the other 3 outliers a little less off the main line of correlation. The $\hat{\alpha}$ metric is as good or slightly better than average log norm metric for the Resnet series of models.

We see similar results for our Universal PL capacity control metric $\hat{\alpha}$ across a wide range of other pre-trained DNN models, described in next. In nearly all cases, the metric $\hat{\alpha}$ correlates well with the reported test accuracies, with only a three DNN architectures as exceptions. Overall the $\hat{\alpha}$ metric systematically correlates well with the generalization accuracy of a wide class of pre-trained DNN architectures—which is rather remarkable.

More Pre-trained Models.

We present results for eleven more series of pre-trained DNN architectures, eight of which show positive results, as with the VGG and ResNet series, and three of which provide counterexample architectures. See Table 3 for a summary.

The results that perform as expected are show in Figures 3, 4, 5, and 6. For each set of models, our Universal metric $\hat{\alpha}$ is smaller when, for the most part, the reported (Top 1) test accuracy is larger. This holds approximately true for the three of the four DenseNet models, with densenet169 as an outlier. In fact, this is the only outlier out of 26 DNN models in these 8 architectures. For all of the other pre-trained DNNs, smaller $\hat{\alpha}$ corresponds with smaller test error and larger test accuracy, as predicted by our theory.

Counterexamples.

In such a large corpus of DNNs, there are of course exceptions for a predictive theory. See Table 3 for the counterexamples. These are ResNeXt, MeNet, and FDMobileNet. For ResNeXt, there are only two models, and the $\hat{\alpha}$ is larger for the less accurate model. For MeNet, there are seven different models, and there is no discernible pattern in the data. Finally, for FDMobileNet, there are three different pre-trained models, and, again, the $\hat{\alpha}$ is larger for the less accurate models. We have not looked in detail at these results and simply present them for completeness.

Discussion and Conclusion

We have presented an unsupervised capacity control metric which predicts trends in test accuracies of a trained DNN—without peeking at the test data. See Appendix E for more discussion. Our work leads to a harder theoretical question: can one characterize properties of realistic DNNs to determine whether a DNN is overtrained—without peeking at the test data?

References

A Overview of Heavy-Tailed Self-Regularization

We review Martin and Mahoney’s Theory of Heavy-Tailed Self-Regularization (HT-SR) .

Write the Energy Landscape (or optimization function) for a typical DNN with $L$ layers, with activation functions $h_{l}(\cdot)$, and with $N\times M$ weight matrices $\mathbf{W}_{l}$ and biases $\mathbf{b}_{l}$, as:

Typically, this model would be trained on some labeled data $\{d_{i},y_{i}\}\in\mathcal{D}$, using Backprop, by minimizing the loss $\mathcal{L}$. For simplicity, we do not indicate the structural details of the layers (e.g., Dense or not, Convolutions or not, Residual/Skip Connections, etc.). Each layer is defined by one or more layer 2D weight matrices $\mathbf{W}_{l}$, and/or the 2D feature maps $\mathbf{W}_{l,i}$ extracted from 2D Convolutional (Conv2D) layers. (We have not yet analyzed LSTM or other complicated Layers.) A typical modern DNN may have anywhere between 5 and 5000 2D layer matrices. For each Linear Layer, we get a single $(N\times M)$ (real-valued) 2D weight matrix, denoted $\mathbf{W}_{l}$, for layer $l$. This includes Dense or Fully-Connected (FC) layers, as well as 1D Convolutional (Conv1D) layers, Attention matrices, etc. We ignore the bias terms $\mathbf{b}_{l}$ in this analysis. Let the aspect ratio be $Q=\frac{N}{M}$, with $Q\geq 1$. For the Conv2D layers, we have a 4-index Tensor, of the form $(N\times M\times c\times d)$, consisting of $c\times d$ 2D feature maps of shape $(N\times M)$. We extract $n_{l}=c\times d$ 2D weight matrices $\mathbf{W}_{l,i}$, one for each feature map $i=[1,\dots,n_{l}]$ for layer $l$.

In the HT-SR Theory, we analyze the eigenvalue spectrum (the ESD) of the associated correlation matrices . From this, we can characterize the amount and form of correlation, and therefore implicit self-regularizartion, present in the DNN’s weight matrices. For each layer weight matrix $\mathbf{W}$, of size $N\times M$, construct the associated $M\times M$ (uncentered) correlation matrix $\mathbf{X}$. Dropping the $L$ and $l,i$ indices, we have

If we compute the eigenvalue spectrum of $\mathbf{X}$, i.e., $\lambda_{i}$ such that $\mathbf{X}\mathbf{v}_{i}=\lambda_{i}\mathbf{v}_{i},$ then the ESD of eigenvalues, $\rho(\lambda)$, is just a histogram of the eigenvalues, formally written as

Using HT-SR Theory, we can characterize the correlations in a weight matrix by examining its ESD, $\rho(\lambda)$. It can be well-fit to a power law (PL) distribution, given as

which is (at least) valid within a bounded range of eigenvalues $\lambda\in[\lambda^{min},\lambda^{max}]$. We can determine $\alpha$ by fitting the ESD to a PL, using the commonly accepted Maximum Likelihood (MLE) method of Clauset et al. . This method works very well for exponents between $\alpha\in(2,4)$; and it is adequate, although imprecise, for smaller and especially larger $\alpha$ .

The original work on HT-SR Theory considered NNs including AlexNet and InceptionV3 (as well as DenseNet, ResNet, and VGG), and it showed that for nearly every $\mathbf{W}$, the (bulk and tail) of the ESDs can be fit to a PL and the PL exponents $\alpha$ nearly all lie within the range $\alpha\in(1.5,5)$. Moreover, smaller exponents $\alpha$ are correlated with more implicit self-regularization and, correspondingly, better generalization . Subsequent work has shown that these results are ubiquitous. For example, upon examining nearly 10,000 layer weight matrices $\mathbf{W}_{l,i}$ across over 50 different modern pre-trained DNN architectures, the ESD of nearly every $\mathbf{W}$ layer matrix can be fit to a PL: $70-80\%$ of the time, the fitted PL exponent $\alpha$ lies in the range $\alpha\in(2,4)$; and $10-20\%$ of the time, the fitted PL exponent $\alpha$ lies in the range $\alpha<2$. For example, see Figure 7 for a histogram of results for ca. 7500 weight matrices from ImageNet. Of course, there are exceptions: in any real DNN, the fitted $\alpha$ may range anywhere from $\sim 1.5$ to $10$ or higher (and, of course, larger values of $\alpha$ may indicate that the PL is not a good model for the data). Still, overall, in nearly all large, pre-trained DNNs, the correlations in the weight matrices exhibit a remarkable Universality, being both Heavy Tailed, and having small—but not too small—PL exponents.

Heavy-Tailed Mechanistic Universality.

Here, we consider the question: what does it mean to say that DNN weight matrices exhibit Universality? This answer to this—and its implications—depends on your perspective, in particular, as a Mathematician or a Physicist.

In Statistics and Applied Mathematics, Universality typically refers to properties of systems that can be modeled by random matrices. The justification is that certain system properties can be deduced, without requiring knowledge of system details, from a few global quantities that are then used as parameters to define a random matrix ensemble . Of course, the DNN weight matrices are not random matrices—they are strongly-correlated objects—so it may seem odd that we can apply RMT to characterize them.

In Statistical Physics, Universality refers to a different, but related, phenomena. It arises in systems with very strong correlations, at or near a critical point or phase transition. It is characterized by measuring experimentally certain “observables” that display HT behavior, with common—or Universal—PL exponents. More importantly, it indicates that a specific Universal mechanism drives the underlying physical process, e.g., Self Organized Criticality, directed percolation, etc. . For this reason, we refer to the Universality observed in HT-SR, i.e., in the ESDs of (pre-trtained) DNN weight matrices, as Heavy-Tailed Mechanistic Universality (HT-MU).

For an illustration of what we mean by HT-MU, see Figure 8. When we observe HT behavior in $\mathbf{W}$, or rather its correlation matrix $\mathbf{X}$, we use HT-RMT as a generative model. We say that we model $\mathbf{W}$ as if it is a random matrix, $\mathbf{W}^{rand}(\mu)$, drawn from a Universality class of HT-RMT (i.e., VHT, MHT, or WHT, as defined below). Of course, we do not mean that $\mathbf{W}$ is itself random in any way. We simply use RMT as a stand-in generative model because the correlations in $\mathbf{W}^{rand}(\mu)$ resembles the correlations in $\mathbf{W}$. Indeed, RMT itself does not describe the behavior of a random matrix $\mathbf{W}$ per-se, but it characterizes its correlations (i.e., the eigenvalues of $\mathbf{X}$). Specifically, RMT describes the ESD, $\rho_{emp}(\lambda)$, its limiting, deterministic form $\rho_{\infty}(\lambda)$, as well as the finite-size scaling and fluctuations of the maximum eigenvalue, $\lambda^{max}$ . So, even though $\mathbf{W}$ is not random, we expect its ESD and maximum eigenvalue to behave as if they were drawn from some HT-random matrix $\mathbf{W}^{rand}(\mu)$.

Heavy-Tailed Random Matrix Theory.

To characterize this HT-MU behavior, we use a HT variant of RMT and use HT random matrices to elucidate different Universality classes. Let $\mathbf{W}(\mu)$ be an $N\times M$ random matrix with entries chosen i.i.d. from

where $W_{0}$ is the typical order of magnitude of $W_{i,j}$, and where $\mu>0$. These HT matrix models were first introduced in the Statistical Physics literature, where they are called Lévy Matrices when $0<\mu<2$ ; see also . More recently, there has been mathematical work on HT random matrices . There are at least 3 different Universality classes Results for $\mu=2,4$ are slightly different . We don’t describe them since we don’t expect to be able to resolve them numerically. Also, sometimes Lévy matrices are split into VHT for $1<\mu<2$ and EHT (Extremely Heavy-Tailed) for $0<\mu<1$, as the properties for these two parameter regimes are somewhat different . of HT random matrices, defined by the range $\mu$ takes on:

$0<\mu<2$: VHT: Universality class of Very Heavy-Tailed (or Lévy) matrices;

$2<\mu<4$: MHT: Universality class of Moderately Heavy-Tailed (or Fat-Tailed) matrices;

$4<\mu$: WHT: Universality class of Weakly Heavy-Tailed matrices.

Heavy-Tailed, Finite-Size Relations.

HT-RMT provides more than HT Universality classes. It also provides simple relations between the empirical observables, e.g., the PL exponent $\alpha$ and the maximum eigenvalue $\lambda^{max}$ of each $\mathbf{W}$, with the parameter(s) $\mu$ of our generative theory, i.e, of HT-RMT.

For the VHT Universality class, the PL tail of Eqn. (A.2) persists in the infinite $N\rightarrow\infty$ limit, for $Q$ fixed; and we have the linear relation between our observed exponent $\alpha$ and the theoretical $\mu$:

For the MHT Universality class, the PL tail of Eqn. (A.2) holds in the infinite $N\rightarrow\infty$ limit, for $Q$ fixed, for $\alpha$ in Eqn. (A.4a). At all finite sizes, however, $\alpha$ is still linear in $\mu$, but it displays very strong finite-size effects, empirically giving:

where $a,b$ depend strongly on $M,N$. (See Table 3 of for more details.) These strong finite-size effects characterize MHT distributions; and they are well-known in Statistical Physics . We will exploit these finite-size effects to develop our theory.

Finally, for both the VHT and the MHT Universality classes, the maximum empirical eigenvalue, $\lambda^{max}$, follows a Frechet distribution (i.e., an exponentially-truncated PL); and we expect it to scale with $N$ according to Extreme Value Theory (EVT) :

Eqns. (A.4) and (A.5) show that we have very simple relationships that apply to random matrices that lie within both the VHT and MHT Universality classes. The $\alpha$ and $\lambda^{max}$ are empirically-measurable quantities—of real or synthetic matrices—while $\mu$ is a parameter of the HT-RMT model. For us, the question is: how shall we use these relations?

Due to Heavy Tailed Mechanistic Universality (HT-MU), we expect Eqn. (A.5) to hold for matrices in these HT Universality classes (as evidenced by their ESD properties), e.g., DNN weight matrices $\mathbf{W}$ after training—even when the matrix is not itself a HT random matrix and therefore not governed by RMT or EVT. We shall use these Universal HT finite-size relations to derive a simple capacity control metric for our HT-SR Theory, and relate this to the well known Product Norm capacity control metric.

B The PL–Norm Relation: Finite-Size Effects

Here, we consider finite-size effects in Eqn. (3.3), both within and across HT Universality classes, i.e., for both VHT and MHT matrices. See Figure 9, which displays $\frac{\log\|\mathbf{W}\|^{2}_{F}}{\log\lambda^{max}}$ as a function of the fitted PL exponent $\alpha$, with varying sizes $N$ (with aspect ratio $Q=1$). Recall that $\alpha\approx\frac{1}{2}\mu+1$ for VHT random matrices (Eqn. (A.4a)), while $\alpha=a\mu+b$ for MHT random matrices (Eqn. (A.4b)), where $a,b$ strongly depend on $N$ and $M$. Thus, $\mu\in(0,2)$ for VHT matrices corresponds to $\alpha\in(1,2)$, while $\alpha\approx(2,5)$ for MHT matrices.

The numerical results in Figure 9 show that as $\alpha$ increases when $\alpha<2$, there exists a near-linear relation; and when $\alpha>2$, for $N,M$ large, the relation saturates, becoming constant, while for smaller $N,M$, there exists a near-linear relation, but with strong finite-size effects. These numerical results demonstrate that $\log\|\mathbf{W}\|^{2}_{F}\approx\alpha\log\lambda^{max}$ works very well for VHT random matrices, for $\alpha<2$, and that it works moderately well for MHT matrices and even some WHT matrices. In particular, for MHT matrices, in the finite-size regime, when $N,M\sim\mathcal{O}(100-1000)$, which is typical for modern DNNs, the PL-Norm relations holds, on average, quite well. This is precisely what we want in a practical engineering metric that is designed to describe average test accuracy.

C The PL–Norm Relation: Random Matrices versus Real Data

Here, we show, numerically, that Eqn. (3.3) holds qualitatively well and more generally than the special case derived previously, including into the MHT Universality class, for both random and real data. To illustrate this, we generate a large number of HT random matrices $\mathbf{W}^{rand}(\mu)$, with varying sizes $N$ (and $Q=1$), drawn from a Pareto distribution of Eqn. (A.3), with exponents $\mu\in[0.5,5]$. We then fit the ESD of each $\mathbf{W}^{rand}(\mu)$ to a PL using the method of Clauset et al. to obtain the empirical exponent $\alpha$. Figure 10(a) shows that there is a near-perfect relation between $\alpha\log\lambda^{max}$ and $\log\|\mathbf{W}\|^{2}_{F}$, for this random data. We also performed a similar PL fit for VGG11 weight matrices. (See Section 4 for some details on the VGG11 model.) Figure 10(b) shows the results, demonstrating for the VGG11 data an increasing relation until $\alpha\log\lambda^{max}\approx 2.5$, and a saturation after that point. Figure 10 illustrates (among other things Clearly, there are also differences between the HT random and the real DNN matrices, most notably that $\alpha\log\lambda^{max}$ achieves much larger values for the random matrices. This is discussed in more detail in Appendix D.): that multiplying $\alpha$ by $\log\lambda^{max}$ leads to a relation that increases linearly with the (log of the squared) Frobenius norm for HT random matrices; that the two quantities are linearly correlated for real DNN weight matrices; and that both random HT and real, strongly-correlated matrices show similar saturation effects at large PL exponents.

D Random Pareto versus Non-random DNN Matrices

When we use Universality, as we do in our derivation of the basic PL–Norm Relation, we would like a method that applies both to HT random matrices as well as to non-random, indeed strongly-correlated, pre-trained DNN layer weight matrices that (as evidenced by their ESD properties) are in a HT Universality class. To accomplish this, however, requires some care: while the pre-trained $\mathbf{W}$ matrices do have ESDs that display empirical signatures of HT Universality , they are not random Pareto matrices. Many of their properties, including their empirical Frobenius norms, behave very differently than that of a random Pareto matrix. (We saw this in Figure 10, which showed that $\alpha\log\lambda^{max}$ achieves much larger values for HT random matrices than real DNN weight matrices.)

To illustrate this, we generate a large number of HT random matrices $\mathbf{W}^{rand}(\mu)$, with exponents $\mu\in[0.5,5]$, as described in Section 3. We then fit the ESD of each $\mathbf{W}^{rand}(\mu)$ to a PL using the method of Clauset et al. to obtain the empirical PL exponent $\alpha$. Figure 11(a) displays the relationship between the (log of the squared) Frobenius norm and the $\mu$ exponents for these randomly-generated Pareto matrices. (Similar but noisier plots would arise if we plotted this as a function of $\alpha$, due to imperfections in the PL fit.) We did the same for the weight matrices (extracted from the Conv2D Feature Maps) from the pre-trained VGG11 DNN, again as described in Section 3. Figure 11(b) displays these results, here as a function of $\alpha$.

From Figures 11(a) and 11(b), we see that the properties of $\|\mathbf{W}\|^{2}_{F}$ differ strikingly for the random Pareto versus real/ron-random DNN weight matrices, and thus care must be taken when applying these Universality principles to strongly correlated systems. For a random Pareto matrix, $\mathbf{W}^{rand}(\mu)$, the Frobenius norm $\|\mathbf{W}^{rand}(\mu)\|^{2}_{F}$ decreases with increasing exponent $(\mu)$; and there is a modest finite-size effect. (In addition, as the tails of the ESD $\rho(\lambda)$ get heavier, the largest eigenvalue $\lambda^{max}$ of $\mathbf{X}$ scales with the largest element of $\mathbf{W}^{rand}(\mu)$.) For the weight matrices of a pre-trained DNN, however, the Frobenius norm $\|\mathbf{W}\|^{2}_{F}$ increases with increasing exponent $(\alpha)$, saturating at $\alpha\approx 3$. This happens because, due to the training process, the $\mathbf{W}$ matrices themselves are highly-correlated, and not random matrices with a single large, atypical element. This is easily seen by simply randomizing the elements of a real DNN weight matrix, and computing the ESD again. In spite of this, the ESD $\rho(\lambda)$ of these pre-trained correlations matrices $\mathbf{X}$ display Universal HT behavior . In addition, as shown in Figure 10(b), Eqn. (3.3) is approximately satisfied, in the sense that $\alpha\log\lambda^{max}$ is positively correlated with $\log\|\mathbf{W}\|^{2}_{F}$. This is one of the remarkable properties of HT-MU.

E Additional Discussion

We have presented an unsupervised capacity control metric which predicts trends in test accuracies of a trained DNN—without peeking at the test data. This complexity metic, $\hat{\alpha}$ of Eqn. (3.4), is a weighted average of the PL exponents $\alpha$ for each layer weight matrix, where $\alpha$ is defined in the recent HT-SR Theory , and where the weights are the largest eigenvalue $\lambda^{max}$ of the correlation matrix $\mathbf{X}$. We examine several commonly-available, pre-trained, production-quality DNNs by plotting $\hat{\alpha}$ versus the reported test accuracies. This covers classes of DNN architectures including the VGG models, ResNet, DenseNet, etc. In nearly every class, and except for a few counterexamples, smaller $\hat{\alpha}$ corresponds to better average test accuracies, thereby providing a strong predictor of model quality. We also show that this new complexity metric $\hat{\alpha}$ is approximately the average log of the squared Frobenius norm of the layer weight matrices, $\langle\log\|\mathbf{W}\|_{F}^{2}\rangle$, when accounting for finite-size effects:

This provides an interesting connection between the Statistical Physics approach to learning (from Martin and Mahoney , that we extend here) and methods such as that of Liao et al. , who use norm-based capacity control metrics to bound worst-case generalization error.

It is worth emphasizing that we are taking a very non-standard approach (at least for the DNN and ML communities) to address our main question. We did not train/retrain lots and lots of (typically rather small) models, analyzing training/test curves, trying to glean from them bits of insight that might then extrapolate to more realistic models. Instead, we took advantage of the fact that there already exist many (typically rather large) publicly-available pre-trained models, and we analyzed the properties of these models. That is, we viewed these publicly-available pre-trained models as artifacts of the world that achieve state-of-the-art performance in computer vision, NLP, and related applications; and we attempted to understand why. To do so, we analyzed the empirical (spectral) properties of these models; and we then extracted data-dependent metrics to predict their generalization performance on production-quality models. Given well-known challenges associated with training, we suggest that this methodology be applied more generally.

Finally, one interesting aspect of our approach is that we can apply these complexity metrics across related DNN architectures. This is in contrast to the standard practice in ML. The equivalent notion would be to compare margins across SVMs, applied to the same data, but with different kernels. One loose interpretation is that a set of related of DNN models (i.e., VGG11, VGG13, etc.) is analogous to a single, very complicated kernel, and that the hierarchy of architectures is analogous to the hierarchy of hypothesis spaces in more traditional VC theory. Making this idea precise is clearly of interest.

We expect our result will have applications in the fine-tuning of pre-trained DNNs used for transfer learning, as in NLP and related applications. Moreover, because we do not need to peek at the test data, our approach may prevent information from leaking from the test set into the model, thereby helping to prevent overtraining and making fined-tuned DNNs more robust. Finally, our work also leads to a much harder theoretical question: is it possible to characterize properties of realistic DNNs to determine whether a DNN is overtrained—without peeking at the test data?