Rethinking Parameter Counting: Effective Dimensionality Revisited
Authors: Gregory Benton
Wesley Maddox
Andrew Gordon Wilson
Venue:  (2021)
Keywords: effective dimension
hessian
generalization
double descent

Abstract: Neural networks appear to have mysterious generalization properties when using parameter counting as a proxy for complexity. Indeed, neural networks often have many more parameters than there are data points, yet still provide good generalization performance. Moreover, when we measure generalization as a function of parameters, we see double descent behaviour, where the test error decreases, increases, and then again decreases. We show that many of these properties become understandable when viewed through the lens of effective dimensionality, which measures the dimensionality of the parameter space determined by the data. We relate effective dimensionality to posterior contraction in Bayesian deep learning, model selection, width-depth tradeoffs, double descent, and functional diversity in loss surfaces,  leading to a richer understanding of the interplay between parameters and functions in deep models. We also show that effective dimensionality compares favourably to alternative norm- and flatness- based generalization measures.

Under review as a conference paper at ICLR 2021
RETHINKING PARAMETER COUNTING: EFFECTIVE DIMENSIONALITY REVISITED
Anonymous authors Paper under double-blind review
ABSTRACT
Neural networks appear to have mysterious generalization properties when using parameter counting as a proxy for complexity. Indeed, neural networks often have many more parameters than there are data points, yet still provide good general- ization performance. Moreover, when we measure generalization as a function of parameters, we see double descent behaviour, where the test error decreases, increases, and then again decreases. We show that many of these properties become understandable when viewed through the lens of effective dimensionality, which measures the dimensionality of the parameter space determined by the data. We relate effective dimensionality to posterior contraction in Bayesian deep learning, model selection, width-depth tradeoff', double descent, and functional diversity in loss surfaces, leading to a richer understanding of the interplay between parameters and functions in deep models. We also show that effective dimensionality compares favourably to alternative norm- and flatness- based generalization measures.
INTRODUCTION
Parameter counting pervades the narrative in modern deep learning. "One of the defining properties of deep learning is that models are chosen to have many more parameters than available training data. In light of this capacity for overfitting, it remarkable that simple algorithms like SGD reliably return solutions with low test error" (Dziugaite and Roy 2017). "Despite their massive size, successful deep artificial neural networks can exhibit remarkably small difference between training and test performance" (Zhang et al., 2017). "Increasing the number of parameters of neural networks can give much better prediction accuracy" (Shazeer et al., 2017). "Scale sensitive complexity measures do not offer explanation of why neural networks generalize better with over- parametrizzaation (Neyshabur et al., 2018). "We train GPT-3, an autoregressive language model with 175 billion parameters, 10x more than any previous non-sparse language model" (Brown et al., 2020). The number model parameters explicitly appears in many modern generalization measures, such as in Equations 20, 51, 52, 56, 57, 59, and 60 of the recent study by JJann et al. (2020). Phenomena such as double descent are a consequence of parameter counting. Parameter counting even permeates our language, with expressions such as overpparametrizationn for more parameters than data points.
But parameter counting can be a poor description of model complexity, model flexibility, and inductive biases. One can easily construct degenerate cases, such as predictions being generated by a sum of parameters, where the number of parameters is divorced from the statistical properties of the model. When reasoning about generalization, over-porane werrparametrizzttoon is besides the point: what matters is how the parameters combine with the functional form of the model.
Indeed, the practical success of convolutional neural networks (CNNs) for image recognition tasks is almost entirely about the inductive biases of convolutional filters, depth, and sparsity, for extracting local similarities and hierarchical representations, rather than flexibility (LeCun et al.) 1989 Szegedy al.) 2015). Convolutional neural networks have far fewer parameters than fully connected networks, yet can provide much better generalization. Moreover, width can provide flcxibility, but is depth that has made neural networks distinctive in their generalization abilities.
In this paper, we gain a number of insights into modern neural networks through the lens of effective dimensionaliry, in place of simple parameter counting. Effective dimensionality, defined by the eigenspectrum of the Hessian on the training loss (equation [ Section 2). was used by MacKay (1992a) measure how many directions in the parameter space had been determined in Bayesian

---

Under review as a conference paper at ICLR 2021
3.5
94
Train Loss Non(Hessian)
92
2.5
90
(Hessia
2.0
88
1.5
86
1.0
84
0.0
Width
Figure 1: A resolution of double descent. We replicate the double descent behaviour of deep neural networks using ResNet18 (He et al. 2016) on CIFAR-100, where train loss decreases to zero with sufficiently wide model while test loss decreases, then increases, and then decreases again.
Effective Dimensionality
100
Test Loss
Train Loss
Depth
1.75
80
1.50
70
20
28
1.6
12
20
Figure Left: Effective dimensionality as function of model width and depth for CNN on CIFAR-100. Center: Test loss function of model width and depth. Right: Train loss function of model width and depth. Yellow level curves represent equal parameter counts (1e5, 2e5, 4e5. 1.6.6). The green curve separates models with near-zero training loss. Effective dimensionality serves as good proxy for generalization for models with low train loss.
neural network. There is immense value in revisiting effective dimensionality in the context of modern deep learning. We demonstrate that effective dimensionality can be used explain phenomena such as double descent and width-depth trade-offs in architecture specification (Section 5}. We also show that effective dimensionality provides straightforward, scalable, and promising metric for generalization in modern deep learning, comparing to PAC-Bayes flatness and path-norm measures. two of the most successful measures in the recent study by [iang et al.] (2020) (Section (6). We additionally show how effective dimension can explain why subspace compression methods for neural networks (Izmailov et al., 2019 Li et al. 2018) can be so effective in practice, demonstrating function-spaci homogeneity smallest cigenvalues of the Hessian (Section 4.. We connect this finding with Bayesian Occam factors and minimum description length frameworks, providing an interpretation of effective dimensionality as model compression (Section 4.3) Moreover, we show that despite a seeming lack of determination in parameter space, neural network can be relatively well-determined in function space (Section 4
move in directions given by cigenvectors corresponding to the
Consider Figure [ where we see that once a model has achieved low training loss, the effective dimensionality, computed from training data alone, replicates double descent behaviour for neural networks. Models that are wider have both lower effective dimensionality and better generalization. Alternativly,, Figure we see that width and depth determine effective dimensionality different ways, though both are related to numbers of parameters. Remarkably, for models with low training loss (above the green partition), the effective dimensionality closely tracks generalization performance for each combination of width and depth. We also see that wide but shallow models overfit, while depth helps provide lower effective dimensionality. When two models have the same training loss they can be viewed as providing compression of the training data at the same fidelity, in which case the model with the lower effective dimensionality, and thus provides the better compression (Section capturing more regularities will tend to generalize better. In particular, effective dimension should be used to compare models with similarly low values training loss. this regime, we see that ED closely tracks generalization for both double descent and width-depth trade-offs.
4.3
2

---

Under review as a conference paper at ICLR 2021
2 POSTERIOR CONTRACTION, EFFECTIVE DIMENSION, AND THE HESSIAN
We consider a model, typically a neural network, f(z; with inputs I and parameters 0 E R We define the Hessian as the & x & matrix of second derivatives of the loss, Ha -Vo D), where D is the training data. To begin, we describe posterior contraction, effective dimensionality, and connections the Hessian.
2.1 THE HESSIAN AND THE POSTERIOR DISTRIBUTION
We begin by providing simple example ex- plaining the relationship between the posterior distribution over the model's parameter, the amount of posterior contraction from the prior, and the Hessian of the negative log posterior. Figure shows the prior and posterior distribu- tion for Bayesian linear regression model with a single parameter, with predictions generated by parameters drawn from these distributions. As expected, we see that the variance of the pos- terior distribution is significantly reduced from that of the prior; call the difference of the variance between the posterior and the prior the posterior contraction of the model. More specif- ically, as shown in Figure 3 the arrival data increases the curvature of the loss (negative log posterior) at the optimum. This increase in curvature the loss that accompanies certainty about the parameters leads to an increase in the eigenvalues of the Hessian of the Growth in eigenvalues of the Hessian of the loss corresponds to increased certainty about parameters.
0.76
Probabiity
0.50
> 0.0
028
-2
-6
6
Parameter
Prior
Posterior
Data
Figure 3: Left: A comparison of prior and pos- terior distributions in linear regression setting, demonstrating the decrease in variance referred to as posterior contraction. Right: Functions sam- pled from the prior and posterior distributions.
2.2 POSTERIOR CONTRACTION AND EFFECTIVE DIMENSIONALITY
When combined with the functional form of a model, a distribution over parameters p(0) induces a distribution over functions p( (z; 0)). The parameters are of little direct interest what matters for generalization is the distribution over functions (e.g. the right panel of Figure 3}. As parameter distributions concentrate around specific values expect to generate less diverse functions, the behavior seen in Figure 3 We show in Appendix that we can describe posterior contraction in Bayesian linear regression, y (/b3, o² I), with isotropic Gaussian prior, B ~ NO a² Tk);
A
post ( = 2
A 2
where X; are the eigenvalues of T 4/a2. the Hessian of the log likelihood, which is dependent on both the model and the training data. We refer to the summation in equation [ as the effective defining the effective dimensionality of
dimensionality of & 4/a². We generalize equation |
symmetric matrix E Ig kg xcck
as
Ner = Σ
A 2
(2)
in which X; are the eigenvalues of A and 0 is regularization constant MacKay
1992a
Typically as neural networks are trained we observe a gap in the eigenspectrum of the Hessian of the loss (Sagun et al. 2017); small number of eigenvalues become large while the rest are near zero. In computing effective dimensionality, eigenvalues much larger than z contribute a value of approximately one the summation, and eigenvalues much smaller than z contribute a value of approximately zero.
In discussing model generalization, use effective dimensionality short form for the effective dimen- sionality of the Hessian of the loss of trained model.
3

---

Under review as a conference paper at ICLR 2021
1.8
2
Test Loss
1.6
0.1
0.5
1.4
1.2
88
90
94 Effective Dimensionality
92
98 100
Figure 4: We see similarly strong relative relationship between effective dimensionality and test loss over wide range of regularization parameters z. Each point is the effective dimensionality computed for regularization parameter (varying colors) and particular width and depth, as in Figure 2 We use only models with low training loss (above the green partition in Figure 2 for this plot.
Therefore, the effective dimensionality explains the number of parameters that have been determined by the data, which corresponds to the number of parameters the model is using to make predictions. In comparing models of the same parameterization that achieve low loss on the training data, expect models with lower effective dimensionality to generalize better- - which empirically verified in Figures
I and 2 The intuition built using Figure 3 carries through to this approximation: as the eigenvalues of the Hessian increase, the eigenvalues of the covariance matrix in our approximation to the posterior distribution shrink, further indicating contraction around the MAP estimate.
Practical Computations For large neural networks computing the eigenvalues and eigenvectors of the Hessian of the loss is nontrivial. We estimate effective dimensionality by computing the dominant eigenvalues using the Lanczos algorithm implemented in GPyTorch, since many of the eigenvalues are typically close to zero and do not significantly contribute to the estimate (Gardner et al. 2018). Hessian vector products as implemented in Py'Torch take three backward passes; In our experiments, we compute 100 Hessian vector products to produce 100 eigenvalues, so that the cost is about 1.5x cost of standard training As a heuristic, one can set z using the connection with the prior to measure the number of relatively large eigenvalues. We use value of - = 1 in equation 2 for all experiments, and show in Figure Dhat effective dimensionality for model comparison is highly robust to different values of over the range of networks with near training loss in Figure? 2] For neural networks, the Hessian can have negative eigenvalues (e.g.. Sagun et al. 2017: Ghorbani al., 2019); however, these negative eigenvalues are in practice extremely small in magnitude compared to the positive ones, and do not practically impact the computations of effective dimensionality.
variance a² and & regularization,
The Hessian (and its effective dimensionality) is not invariant to re-parameterizations (e.g. ReLU rescaling and batch normalization) (MacKay 2003, Chapter 27). For this reason we assume fixed parameterization, as is the case in practice, and compare between models of the same parameterization.
RELATED WORK
MacKay (192a)) used effective dimensionality to measure posterior contraction in Bayesian neural networks. Effective dimensionality has also been used for measuring generalization error of kernel
methods (Caponnetto and Vito 2007).
Various connections between flatness and generalization have been explored via Occam factors (MacKay] 2003 Smith and Le (0118) and minimum description length (Hinton and Van Camp 1993
Achille and Soatto| 2018) Nakkiran et al. (2020) found generalization gains as neural net works become overparameterized, showing the double descent phenomenon (e.g., Belkin et al. 201 9a
Nakkiran et al. 2020) that occurs the width increases in residual and convolutional neural networks.
Flatness has also be considered in the PAC- -Byys literature (e.g., Dziugaite and Roy 2017 Jiang
al. 2020), with Jiang et al. (2020) showing that PAC- AAC-Bayesian measures of flatness, in the sense of
II Appendix I we provide an example of the insensitivity of effective dimensionality to the number of eigenvalues used.
4

---

Under review as a conference paper at ICLR 2021
Ner (Parameler Cow.)
Bayesian Linear Regression
Bayesian Neural Network
2000
Nert (Hoosian)
1503
80
100
1002
20
50
500
Number Data Points
Number Data Points
Parameter Covariance
Hessian
Figure 5: The effective dimensionality of the posterior covariance over parameters and the function- space posterior covariance. Red indicates the over-parameterizee setting, yellow the critical regime with & n, and green the nareeerrrametrizeed regime. In both models we see the expected increase in effective dimensionality in parameter space and decrease in effective dimensionality of the Hessian.
insensitivity random perturbations, perform well relative many generalization bounds. Zhou et al. 20188) used PAC-Bayesian compression arguments to construct non-vacuous bounds.
Our work shows that effective dimensionality can shed light number of phenomena in modern deep learning, including double descent, width-depth trade-offs, and Bayesian subspace inference, while providing a straightforward and compelling generalization metric, relative several of the highest performing metrics in Jiang et al. (2020). We provide an extended discussion of historical perspectives in Appendix [
POSTERIOR CONTRACTION AND FUNCTION-SPACE HOMOGENEITY
We demonstrate how the effective dimensionality of both the posterior parameter covariance and the Hessian of the loss provides insights into how a model adapts to data during training. Additionally show that in directions in which the posterior has not contracted, neural networks are insensitive to parameter perturbations. In other words, we show that although there are many flat directions in neural network posterior, the functions obtained by moving along those directions are remarkably homogeneous. Finally we relate insensitivity to parameter perturbations to Occam factors, connecting effective dimensionality data compression. These findings help explain the surprising success of subspace inference methods for capturing functional variability in low dimensional subspaces.
4.1 POSTERIOR CONTRACTION OF BAYESIAN MODELS
Theorem 4.1 (Posterior Contraction Bayesian Linear Models). Let $
(xx) E Bunk be feature map of n data observations, with k feutures, such that < k and assign isotropic prior for B ~ NOkk, [x] for parameters ] E IR... Assuming model of the form ~ N$33, ($3,0" I²In) the
posterior distribution of 3 has a k n directional subspace in which the variance is identical the prior variance.
Theorem 4.1 along with equivalent result for generalized linear models, is proven in Appendix F. Theorem 1.1 demonstrates why parameter counting often makes little sense: for a fixed data of size n, only min(n, k) parameters can be determined, leaving many dimensions in which the posterior is unchanged from the prior when k >> n.
While much effort has been spent grappling with the challenges of high dimensional parameter spaces for Bayesian neural networks, the practical existence of subspaces where the posterior variance has not collapsed from the prior suggests that both computational and approximation gains can be made from ignoring directions in which the posterior variance is unchanged from the prior. This observation helps explain the success of subspace based techniques (e.g., [immilov et al.) 2019) that marginalize the loss in lower dimensional space. For Bayesian linear models, the effective dimensionality of the parameter covariance the inverse of the Hessian, and as the effective dimensionality of the parameter covariance decreases, the effective dimensionality of the Hessian increases. Supporting this argument, in Figure 5 we demonstrate for both Bayesian linear models and Bayesian neural networks that the number of data points grows, the effective dimensionality of the posterior covariance decreases while the effective dimensionality of the Hessian increases until both are limited by the number of parameters. The details of the experimental setup for Figure are given in Appendix
5

---

Under review as a conference paper at ICLR 2021
Or gingil Model
Low Curvature Differences.
High Curvalure Differenoee
1.05
0.00
Absa DR 8
0.75
0.80
0.45
0.30
Modffed Decision Boundary
Decision Boundary
Figure 6: Swiss roll data. Left: Adam trained feed-forward, fully connected classifier. Center: Differences in original and perturbed classifier when parameters are perturbed in low curvature degenerate directions. Right: Differences in the original and perturbed classifier when parameters are perturbed in high curvature directions. Note the perturbation the center plot is approximately 100 times the size of that of the plot on the right!
4.2 FUNCTION-SPACE HOMOGENEITY
The previous section has demonstrated that parameters can be undetermined by the data; we now show that the function induced by the model unchanged in these directions.
Theorem 4.2 (Function-Spacc Homogeneity in Linear Models). Let + (xx) ) E Brnn be feature map of n. data observations, z, with n < k, and assign isotropic prior 3 ~ (0x,, parameters B E E The minimal eigenvectors of the Hessian define a k 6-1 dimensional subspace in which parameters can be perturbed without changing the training predictions in function space.
100k,o? o2 T for
The proof (along with an extension to generalized linear models) is given in Appendix F.2 Although there may be large regions in parameter -spcce that lead to low-loss models, many of these models may be homogencous in function space. We can interpret Theorem 4.2 in terms of the eigenvectors of the Hessian indicating which directions in parameter space have and have not been determined by the data. The dominant eigenvectors of the Hessian (those with the largest eigenvalues) correspond to the directions in which the parameters have been determined from the data and the posterior has contracted significantly from the prior. The minimal eigenvectors (those with the smallest eigenvalues) correspond to the directions in parameter space in which the data has not determined the parameters.
Figure o demonstrates that the results of Theorem 4.2 apply to neural networks well, with large perturbations to the parameters in undetermined directions having little effect on the classification boundary. As parameters (minimal eigenvectors of the Hessian), the functional form remains identical to the MAP estimate. Perturbations in determined directions (dominant eigenvectors of the Hessian) yield models that perform poorly on the training data and significantly deviate from the MAP estimate on the test set. The homogeneity found by taking perturbations undetermined parameter directions shows that even in cases with a lack of determination in parameter space, the functional form of the model is well specified by the data. Further results regarding function space homogeneity and the connection to loss surface structure, including the projection of the loss surface of the classifier shown in Figure onto random, low curvature, and high curvature bases, are given in Appendix A
perturbed in directions that have not been determined by the data
4.3 EFFECTIVE DIMENSIONALITY AS COMPRESSION
In Section 4.2 we show that effective dimensionality relates to the number of parameter directions in which the functional form of the model is sensitive perturbations, and that in the low curvature directions given by the Hessian eigenvectors corresponding to the smallest cigenvalues the model outputs are largely unchanged by perturbations to the parameters. The presence of these degenerate directions suggests that we can disregard high dimensional subspaces that contain little information about the model, for compression into a smaller subspace containing only the most important parameter directions given by the eigenvalues of the Hessian. This observation helps explain the practical success of such subspace approaches (Izmailov et al.) 2019 Li et al. 2018). In short, if two models have similar and low training loss, then the model with lower effective dimension will be providing a better compression the training data at a similar level of fidelity, and will therefore tend to generalize better. On the other hand, if models have different training loss or high training loss,

---

Under review as a conference paper at ICLR 2021
then it becomes harder to user effective dimensionality to predict generalization, as the models may not have learned much from the data, and therefore the level of compression becomes less relevant.
We can also understand the compression of the data provided by model in terms of minimum description length, by examining the Oceam factrr of the model evidence (MacKay 2003, Chapter 28). For model M with parameters 0, we find the Oceam factor in decomposing the evidence as,
M() p
p(D]0Mr,, p(0MrllM)drr (Ho/2xT)
Evidence 2
Likelihood
Occam Factor
in which Ho is the Hessian of the loss, and PMP is the MAP estimate of the parameters.
As the eigenvalues of the Hessian decay and the effective dimensionality decreases, the determinant of the Hessian also decreases, causing the Occam factor to increase, and the description length to decrease, providing better compression. |MacKay| (1992b) and [MacKay (2003) contains a further discussion of the connection between Occam factors and minimum description length.
DOUBLE DESCENT AND WIDTH-DEPTH TRADE-OFFS
5.1
DOUBLE DESCENT
Thus far, have simply demonstrated that effective dimensionality gives a better understanding of diversity in the context of the space of functions induced by neural networks. The phenomenon of double descent of the generalization performance in both linear and deep models has attracted recent attention (Belkin et al. 2019a; Nakkiran et al. 2020); here, we explain double descent as a function of effective dimensionality.
Following the experimental setup of Nakkiran et al. (2020), we train ResNet18s (He et al. 2016) with varying width parameters, reproducing their double descent curve In Figure we see effective dimensionality tracks remarkably well with generalization for models with low training loss displaying the double descent curve that is seen in the test error. We emphasize again that the effective dimensionality is computed using solely the training data, supporting the hypothesis that the eigenvalues of the Hessian matrix can provide good proxy for generalization performance. In Appendix H
we show similar findings for linear models and small neural networks.
In short, double descent is an artifact of overfitting. As the dimensionality of the parameter space continues to increase past the point where the corresponding models achieve zero training error, flat regions of the loss occupy a greatly increasing volume (Huang et al. 2019), and are thus more easily discoverable by optimization procedures such SGD. These solutions have lower effective dimensionality, and thus provide better compressions of the data, as in Section 4.3 and therefore better generalization. In concurrent work, WWilson and Izmailov (2020) show that exhaustive Bayesian model averaging over multiple modes eliminates double descent.
In addition to test loss, also demonstrate that effective dimensionality tracks double descent in test error in Figure 1.1 Appendix). Double descent is clearly present for test loss on CIFAR-101 100, but not test error. To produce double descent for test error, we follow the setup in Nakkiran et al. (0000) and introduce 20% label corruption, which increases the chance of overfitting.
5.2 NETWORKS OF VARYING WIDTH AND DEPTH
Double descent experiments typically only consider increases in width. However, it is depth which has endowed neural networks with distinctive generalization properties. Figure 2 we consider varying both the width and depth of a convolutional neural network on the CIFAR- TO0 dataset. In the region of near-zero training loss, separated by the green curve, we see effective dimensionality closely matches generalization performance. Moreover, wide but shallow models tend to overfit, providing low training loss, but high effective dimensionality and test loss. On the other hand, deeper models have lower test loss and lower effective dimensionality, showing that depth enables better compression of the data.
"See Appendix forrr training details.
7

---

Under review as a conference paper at ICLR 2021
With
Text Droe
Mig. PAC Bayas
leg Fath Nom
Cnty
Map.
log Path torm
(a) Double Descent, No Label Noise
(b) Double Descent, 20% Label Noise
Figure 7: Comparing effective dimensionality a generalization measure the path- log path-norm, PAC-Bayes, and magnitude aware PAC-Bayes flatness measures from Jiang et al.) (2020) for double descent (a) without and (b) with label noise. For models with low train loss, effective dimensionality most closely follows both test error and test loss.
EFFECTIVE DIMENSIONALITY AS A GENERALIZATION MEASURE
We have shown, for the first time, that generalization measure is able to track and explain double descent and width-depth trade-off's in modern deep networks. We now demonstrate that effective dimensionality is strong generalization measure by itself. For comparison, we choose path-norm and Bayyaaan based sharpness measures, due their good performance prior work (Jiang et al. 2020 Keskar et al. 2017 Neyshabur et al. 2017). We compute the norms as in Jiang et al. (2020) for a neural network function j (a;; 0) with input and weights O.
The path-norm describes the norm of all paths within network between input and output nodes, measuring the complexity traversing the network. The standard PAC-Bayesian flatness measure aims to measure the overall flatness of the solution by determining the size of the largest perturbation that can be made to the parameters such that the expected increase in training error remains low. We additionally compare to the magnitude aware PAC-Bayeses standard PAC-Bayesiann flatness measure, except that the perturbations to parameters are scaled by the magnitude of the weights in the network. Computation details given in Appendix [
flatness measure, which is similar the
We extend the results of Figure Tin Figure to include the path-norm and PAC-Bayesiar flatness measures. We display test loss, test error, and generalization measures, standardized by subtracting the sample mean and dividing by the sample standard deviation. We extend the results of Figure 2 the same fashion Figure 7 the Appendix in Figure A.13 We additionally show correlations with generalization in Tables and in the Appendix.
There are several key take- aways: (1) effective dimension overall provides better proxy for test loss and test етrоr than the PAC-Bayes or path-norm measures for double descent and width-depth trade-offs; (2) not all flatness-based generalization measures are equivalent, and in fact different flatness measures can provide wildly different behaviour; (3) effective dimension is more stable than the other measures. with relatively consistent behaviour across qualitatively similar datasets and models; (4) effective dimension is interpretable, providing clear connection with function-space and an explanation for why model should generalize, in addition to an association with generalization.
Not all flatness-based generalization measures are equivalent. In contrast to the PAC-Bayesian flatness measure considered in Jiang et al. (2020), effective dimension computes the number of directions in parameter space that are flat, determined by the curvature of the loss surface. Combined with our observations about function- space homogeneity Section 4.2 we see that effective dimension provides proxy for model compression and generalization in addition to providing correlation with performance. By contrast, the PAC-B BAC-Bayes flatness measure considers the size of the basin surrounding optimum, and is highly sensitive to the sharpest direction.
8

---

Under review as a conference paper at ICLR 2021
7 CONCLUSION
We have shown how the effective dimensionality of the Hessian of the loss can be used to gain insight into a range of phenomena, including double descent, posterior contraction, loss surface structure, subspace inference, and function-space diversity of models. As we have seen, simple parameter count- ing can be misleading proxy for model complexity and generalization performance; models with many parameters combined with particular functional form can give rise to simple explanations for data. Indeed, we have seen how depth and width have different effects on generalization performance, regardless of the total number of parameters in the model. In all cases, effective dimensionality tracks generalization performance for models with comparable training loss. Moving forward, we hope work will help inspire continued effort capture the nuanced interplay between the statistical properties of parameter space and function space understanding generalization behaviour, and highlight effective dimension relatively simple and robust generalization measure in modern deep learning.
REFERENCES
A. Achille and S. Soatto. Emergence of invariance and disentanglement in deep representations. The Journal of Machine Learning Research, 19(1):1947-190, 2018.
L. Bartlett, M. Long, G. Lugosi, and A. Tsigler. Benign overfitting linear regression. arXiv preprint arXiv: /906. 11300, 2019.
M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-leariing practice and the classical birs-variance trade-off. Proceedings of the National Academy of Sciences, 116(32): 15849-15854, 2019a.
M. Belkin, D. Hsu, and J. Xu. Two models of double descent for weak features. arXiv preprint arXiv:1903.0757,, 20111.,....77...199.b.. 2019b.
E. Bingham, J. P. Chen, M. Jankowikk, F. Obermeyer, N. Pradhan, T. Karaletsos, R. Singh, P. Szerlip, P. Horsfall, and N. D. Goodman. Pyro: Deep universal probabilistic programming. The Journal of Machine Learning Research, 20(1):973-978 2019.
S. Bös, W. Kinzel, and M. Opper. Generalization ability of perceptrons with continuous outputs. Physical Review E, 47(2): 1993.
T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, Shyam, G. Sastry, Askell, al. Language models are few-shot learners. arXiv preprint arXiv:2005. 14165, 2020.
A. Caponnetto and E. D. Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-366 2007. doi: 1007 1007
0011://101020000--016100000 URL 0000000000000000000 0196-8
Chaudhari, A. Choromanska, Soatto, Y. LeCun, C. Baldassi, C. Borgs, Chayes, L. Sagun, and R. Zecchina. Entropy-SGD: Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, 2019.
W. S. Cleveland. Robust locally weighted regression and smoothing scatterplots. Journal of the American statistical association, (246668)829-8366 1979.
E. Dobriban and S. Wager. High-dimensionnal asymptotics of prediction: Ridge regression and classification, Ann. Statist., 46(1):277-779, 02 2018. doi: 10.1214/17-AS1544,, URL https
//doi.org/10. 1ttp:/000..111111-00155554
G. K. Dziugaite and M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. Uncertainty in Artificial Intelligence (UAI), 2017.
Friedman, T. Hastie, and R. Tibshirami. The elements of statistical learning. Springer series in statistics New York, 2001.

---

Under review as a conference paper at ICLR 2021
K. Fukumizu, S. Yamaguch, Y.-i. Mototake, and M. Tanaka. Semi-fla minima and saddle points by embedding neural networks to overparameterization. In Advances in neural information processing systems, 2019.
R. Gardner, G. Pleiss, D. Bindel, K. Q. Weinberger, and A. G. Wilson. Gpytorch: Blackbox matrix- matrix gaussian process inference with gpu acceleration. In Advances in Neural Information Processing Systems, 2018.
B. Ghorbani, S. Krishnan, and Y. Xiao. An investigation into neural net optimization via hessian eigenvalue density. In International Conference on Machine Learning, 2019. URL arXiv
1901.
S. F. Gull. Developments in maximum entropy data analysis. In Maximum entropy and Bayesian methods, pages 53-71, Springer, 1989.
Hastie and R. Tibshirani. Generalized additive models. Chapman and Hall, London, 1990.
T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in High- High-Diiennsionl Ridgeless Least Squares Interpolation.
Nov. 2019.
K. He, X. Zhang, Ren, and Sun. Identity mappings in deep residual networks. In European conference on computer vision, pages 630-645. Springer, 2016.
G. E. Hinton and D. Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. Proceedings of the sixth annual conference on computational learning theory, pages 5-13, 1993.
S. Hochreiter and J. Schmidhuber. Flat Minima. Neural Computation, 9(1):1-42, 1997. URL https:// htt::://www.bbt www.wwww...fn.mmmm http:///aa///a/aaaaaaooo////////
M. D. Hoffman and A. Gelman. The no-u-turn sampler: adaptively setting path lengths in hamiltonian monte carlo. Journal of Machine Learning Research, 15(1):1593-1622 2014.
W. R. Huang, Z. Emam, M. Goldblum, L.. Fowl, J. K. Terry, F. Huang, and T. Goldstein. Understanding generalization through visualizations. arXiv preprint
2019.
Izmailov, D. Podoprikhin, T. Garipov, D. Vetrov, and A. G. Wilson. Averaging weights leads to wider optima and better generalization. In Uncertainty in Artificial Intelligence, 2018. URL
arXiv: 803. 05407
Izmailov, W. J. Maddox, P. Kirichenko, Garipov, D. Vetrov, and G. Wilson. Subspace inference for bayesian deep learning. Uncertainty in Artificial Intelligence (UAI), 2019.
Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures and where to find them. In International Conference on Learning Representations (ICLR), 2020.
URL arxii: 1912. 02178
N. S. Keskar, D. Mudigere, Nocedal, M. Smelyanskiy, and P. P. Tang. On large-batch training for deep learning: Generalization gap and sharp minima. International Conference on Learning Representations (ICLR), 2017. URL awwii:1609..... 04836
D. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR) arXiv:1412.6900 2015.
Y. LeCun, B. Boser, S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural Computation, 1(4):541-551, 1989. doi: 1.4.541
URL httpps://oi.. wwt.:o.gg.1111... 1ttp:/11..112//eecooooo 1989 1989
Y. LeCun, I. Kanter, and S. A. Solla. Eigenvalues of covariance matrices: Application to neural- network learning. Physical Review Letters, 66(18):2396, 1991.
C. Li, H. Farkhoor, R. Liu, and J. Yosinski. Measuring the intrinsic dimension of objective landscapes. arXiv preprint arXiv: 1804.08838 2018
10

---

Under review as a conference paper at ICLR 2021
D. J. MacKay. Bayesian model comparison and backprop nets. In Advances in neural information processing systems, pages 239-846, 1992a.
D. J. MacKay. Bayesian interpolation. Neural computation, 4(3):415 1992b.
D. MacKay, Information theory, inference and learning algorithms. Cambridge university press, 2003.
W. J. Maddox, T. Garipov, P. Izmailov, D. Vetrov, and A. G. Wilson. A simple baseline for bayesian uncertainty in deep learning. In Advances neural information processing systems, 2019.
D. Madras, J. Atwood, and A. D' D'Amour. Detecting extrapolation with local ensembles. arXiv preprint het.:191000953... 2019.
S. Mei and A. Montanari. The generalization enror of random features regression: Precise asymptotics and double descent curve. arXiv preprint /908. 05355, 2019.
J. E. Moody. Note on generalization, regularization and architecture selection in nonlinear learning systems. In Neural Networks for Signal Processing Proceedings of the 1991 IEEE Workshop. pages 1-10. IEEE, 1991.
E. Moody. The effective number of parameters: An analysis of generalization and regularization in nonlinear learning systems. In Advances in neural information processing systems, pages 847-854, 1992.
V. Muthukumar, K. Vodrahalli, and A. Sahai. Harmless interpolation noisy data in regression. arXiv preprint arXiv: (rXXv:9903.09/333 2019.
Nakkiran, G. Kaplun, Y. Bansal, Yang, B. Barak, and I. Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference Learning Representations (ICLR), 2020. URL arXiv: 191.:::1122.220
R. M. Neal and J. Zhang. High Dimensional Classification with Bayesian Neural Networks and Dirichlet Diffusion Trees. Feature Extraction: Foundations and Applications. Studies in Fuzziness and Soft Computing, pages 265-296. Springer, Berlin, Heidelberg, 2006. ISBN 978-3-540-35488-88 doi: 1007/ Uttthttss:://///ttett http://.............o//////-----
Guyon, M. Nikravesh, Gunn, and L. Zadeh, editors,
A. Nelder and W. Wedderburn. Generalized linear models. Journal of the Royal Statistical Society: Series A (General), 135(3):370 -84, 1972.
B. Neyshabur, Bhojanapalli, D. McAllester, and N. Srebro. Exploring generalization in deep learning. In Advances in Neural Information Processing Systems, pages 5947-5956, 2017.
B. Neyshabur, Z. Li, S. Bhojanapalli, Y. LeCun, and N. Srebro. The role of parametrizationn in generalization of neural networks. In International Conference on Learning Representations, 2018.
M. Opper, J. Kleinz, H. Kohler, and W. Kinzel. Basins of attraction near the critical storage capacity for neural networks with constant stabilities. Journal of Physics A: Mathematical and General, 22 (9):4407, 1989.
M. Opper, W. Kinzel, J. Kleinz, and R. Nehl. On the ability of the optimal perceptron to generalise. Journal of Physics A: Mathematical and General, 23(1 1):5511,,, 1990.
V. Papyan. The full spectrum of deepnet hessians at scale: Dynamics with sgd training and sample size. arXiv preprint arXiv: 18/ /. /.07062, 2018.
D. Phan, N. Pradhan, and M. Jankowiak. Composable effects for flexible and accelerated probabilistic programming in numpyro. arXiv preprint 152. 2019.
L. Sagun, L. Bottou, and LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond. In ICLR Workshop track, 2017. URL www.a::ivv111.0000

---

Under review as a conference paper at ICLR 2021
N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton, and Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. International Conference on Learning Representations (ICLR), 2017. URL 1221:1701100553
L. Smith and Q. V. Le. bayesian perspective generalization and stochastic gradient descent. In International Conference on Learning Representations (ICLR), 2018. URL arXiv: 1710
06451
Suzuki, Fast generalization error bound of deep learning from kemee perspective. A. Storkey and F. Perez-Cruz, editors, Proceedings of the Twenty-Firs International Conference Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pages 1397-1406, Playa Blanca, Lanzarote, Canary Islands, 09-11 Apr 2018. PMLR.
C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1-9, 2015.
A. G. Wilson and P. Izmailov. Bayesian deep learning and probabilistic perspective of generalization. arXiv preprint arXiv:2002.0879), 2020.
Z. Yao, A. Gholami, K. Keutzer, and M. Mahoney. Pyhessian: Neural networks through the lens of the hessian. arXiv preprint arXiv:1912.0714 2019.
C. Zhang. S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. International Conference Learning Representations (ICLRR, 2017. URL
T. Zhang. Learning bounds for kernel regression using effective data dimensionality. Neural Computatioon 177))2207-20988, 2005.
W. Zhou, V. Veitch, M. Austern, R. Adams, and P. Orbanz. Non-vacuous generalization bounds at the imagenet scale: pac-bayesian compression approach. In International Conference Learning Representations (ICLR), 2018.
12

---

Under review as a conference paper at ICLR 2021
CONTENTS
In Appendix A we study the loss surfaces of neural netwroks from their function space representations. Then in Appendix [B] give experimental details
experiments regarding the effective dimensionality of the posterior covariance. In Appendix C we describe how we computed the PAC Bayes norms Jiang al. (2020). We describe further related work on effective dimensionality in Appendix D In Appendix E we give proof' about posterior contraction for Bayesian linear models, while in Appendix we give proofs for the theorems on function space homoegeneity for linear and generalized linear models. In Appendix [ we describe how we trained the DNNs used in the paper. In Appendix H
we describe some further experiments on double descent and effective dimensionality. [Finally, in Appendix we examine the effect of the number of eigenvalues as well as repeated training runs on the effective dimensionality of the model.]
A LOss SURFACES AND FUNCTION SPACE REPRESENTATIONS
Recent works have discussed the desirability of finding solutions corresponding flat optima in the loss surface, arguing that such parameter settings lead to better generalization (Izmailov et al. K
2018; Keskar et al.) 2017). There are multiple notions of flatness in loss surfaces, relating both the volume of the basin in which the solution resides and the rate of increase in loss as one moves away from the found solution. As both definitions correspond to low curvature in the loss surface, is standard to use the Hessian of the loss to examine structure in the loss surface MMdras et al. (2019);
Keskar et al, (0177).
The effective dimensionality of the Hessian of the loss indicates the number of parameters that have been determined by the data. In highly over-pane wer--arameterized models we hypothesize that the effective dimensionality is substantially less than the number of parameters, i.e. Nerr a) p, since should be unable to determine many more parameters than we have data observations.
Recall from Section 2.2 the large eigenvalues of the Hessian have eigenvectors corresponding to directions in which parameters are determined. equation 2 dictates that low effective dimensionality (in comparison the total number of parameters) would imply that there are many directions in which parameters are not determined, and the Hessian has eigenvalues that are near zero, meaning that in many directions the loss surface is constant. We refer to directions in parameter space that have not been determined as degenerate for two reasons: (1) degenerate directions in parameter space provide minimal structure in the loss surface, shown in Section A.I (2) parameter perturbations in degenerate directions do not provide diversity in the function- representation of the model, shown Section A.2 We refer to the directions in which parameters have been determined, directions of high curvature, determined.
To empirically test our hypotheses regarding degenerate directions in loss surfaces and function space diversity, we train neural network classifier on 1000 points generated from the two-dimensional Swiss roll data, with a similar setup to Huang et al. (201)), using Adam with a learning rate of 0.01 Kingma and Ba 2015). The network is fully connected, consisting of 5 hidden layers each 20 units wide (plus a bias term), and uses ELU activations with a total of 2181 parameters. We choose a small model with wio-dimesioonal inputs so that can both tractably compute all the eigenvectors and eigenvalues of the Hessian and visualize the functional form of the model.
A.1 LOss SURFACES AS DETERMINED BY THE HESSIAN
To examine the loss surface more closely, we visualize low dimensional projections. To create the visualizations, we first define basis given by set of vectors, then choose a two random vectors, u and ū, within the span of the basis. We use Gram-Schmidt to orthogonalize V with respect to u, ultimately giving and v with u I v. We then compute the loss at parameter settings 0 on grid surrounding the optimal parameter set, 0", which are given by
- 0* + au + 3B
(4)
for various and (3 values such that all points the grid are evaluated.
By selecting the basis in which u and v are defined we can specifically examine the loss in determined and degenerate directions. Figure A.8 that in determined directions, the optimum appears
13

---

Under review as a conference paper at ICLR 2021
Full Surface
Top 3 Eigenvectors
Bottom 2000 Eigenvectors
-35
400
Figure A.8: Left: A random projection of the loss surface. Center: projection the loss surface in the top 3 directions in which parameters have been determined. Right: A projection of the loss surface the 2000 (out of 2181) directions which parameters have been determined the least. The rightmost plot shows that in degenerate parameter directions the loss is constant.
extremely sharp. Conversely, in all but the most determined directions, the loss surface loses all structure and appears constant. Even in degenerate directions, we deviate from the optimum far enough the loss will eventually become large. However to observe this increase in loss requires perturbations the parameters that are significantly larger in norm than 0*
A.2 DEGENERATE PARAMETERS LEAD TO HOMOGENEOUS MODELS
In this section show that degenerate parameter directions do not contain diverse models. This result is not at odds with the notion that flat regions in the loss surface can lead to diverse but high performing models. Rather, we find that there is subspace in which the loss is constant and one cannot find model diversity, noting that this subspace is distinct from those employed by works such as Izmailov et al. (2019) and and/Hunng al. (2019). This finding leads to an interpretation of effective dimensionality as model compression, since the undetermined directions do not contain additional functional information.
We wish to examine the functional form of models obtained by perturbing the parameters found through training, 0", Perturbed parameters are computed as
Bv
0
(5)
Bull2
where B Rexd a dimensional basis in which we wish to perturb 6", and v ~ (O, Ia). giving Bu as random vector from within the span of some specified basis (i.e. the dominant minimal eigenvectors). The value s is chosen to determine the scale of the perturbation, i.e. the length of the random vector by which the parameters
perturbed.
Experimentally, we find that in a region near the optimal parameters 0", i.e. $ funetion-space diversity of the model is contained within the subspace of determined directions. While the degenerate directions contain wide ranges of parameter settings with low loss, the models equivalent function space.
- 100001 1l22 22 the
Figure 6 shows the trained classifier and the differences in function-space between the trained classifier and those generated from parameter perturbations. We compare perturbations of size 11/2 sJ 10 in the direction of the 500 minimal eigenvectors and perturbations of size 0.1 in the directions of the maximum eigenvectors. directions of low curvature (center plot in Figure () still leads to classifier that labels all points identically. perturbation roughly 100 times smaller the size directions in which parameters have been determined leads to a substantial change in the decision boundary of the classifier.
perturbation from the trained parameters in the
However, the change in the decision boundary resulting from perturbations determined directions is not necessarily desirable. One need not perturb parameters in either determined or degenerate directions to perform downstream task such as ensembling. Here, we are showcasing the degeneracy of the subspace of parameter directions that have not been determined by the data. This result highlights that despite having many parameters the network could be described by a relatively low dimensional subspace.
[Finally, Figure A.9 demonstrates that the degenerate directions in parameter space lead to models that homogeneous in function space on both training and testing data. As increas-
14

---

Under review as a conference paper at ICLR 2021
Classification Homogeneil
1.0
Normalizad Loss
0.10
0.08
0.7
0.6
0.02
0.0
02
0.4
0.6
0.8
1.0
0.2
04
0.5
Perturbation Size
Perturbation Size
Low Curvature
High Curvature
Train
Test
Figure A.9: [Left: Loss, normalized by dataset size, both train and test sets as perturba- tions are made in high curvature directions and degenerate directions. Right: Classification homogeneity, the fraction of data points classified the same the unperturbed model, as per- turbations are made both high curvature and degenerate directions.]
ingly large perturbations are made in degenerate parameter directions, we still classify more than 99% both training and testing points the same as the unperturbed classifier.]
B EFFECTIVE DIMENSIONALITY OF THE POSTERIOR COVARIANCE
Linear Models: We construct (xx) with each row as an instance
200 dimensional
feature vector consisting of sinusoidal terms for each of 500 observations: (xx) (cos(TT). sin (TZz, cos(2 (ii(2xx)....... We assign the coefficient vector a prior 33 ~~ 2/, I).
and draw ground truth parameters 3 from this distribution. The model takes the form 3 (0, and y ~ N (0,,o²T). We randomly add data points one at a time while re-computing the poste- rior covariance. We compute the effective dimensionality, Neff (Eg)),.: where EgyD, is the posterior covariance of 8
Small Bayesian Neural Networks For the experiments with small Bayesian neural networks, we generate nonlinear function of the form, y = w1 w222 W3r (0.5 + 2² sin(4x)) with W/: ~ (O, 7) and ~ (0, 0.05²). and de-mean and standardize the inputs | We then construct Bayesian neural network with two hidden layers each with 20 units, no biases, and tanh activations, placing independent Gaussian priors with variance 1 all model parameters. We then run the No-U-Turn sampler (Hoffman and Gelman 2014) for 2000 burn-in iterations before saving the final 2000 samples from the approximated posterior distribution. Using these samples, compute the effective dimensionality of the sample posterior covariance, Cov p(e D) (0), and Hessian of the loss the MAP estimate in Figure 5 The trends of effective dimensionality for Bayesian neural networks are aligned with Bayesian linear regression, with the effective dimensionality of the Hessian (corresponding function space) increasing while the effective dimensionality of the parameter space decreases.
C COMPUTATION OF THE PAC BAYES NORMS
The path-norm the square root of the sum of the outputs produced by a forwards pass on an input of all ones,
Hpath-norm (f) = Σ f(1:02) 1/2
(6)
with the parameters 0 squared (Eq. 44 of Jiang et al. (2020)). Through squaring the weights and taking the square root of the output, we form a correspondence between the path-norm and the f norm of all paths within a network from an input node an output node (Neyshabur et al.) 2017).
Here we use a 5, however the results remain qualitatively the same as this parameter changes.
From the Bayesian neural network example in NumPyro (Phan et al. 22019] Bingham al. 2019 httpa
7/gi thub. com/ wwtpppyyooooppppppappppppppppppp httoopp///moor///ll////e//om
15

---

Under review as a conference paper at ICLR 2021
The PAC-Bayesian flatness measure of Jiang al. 2020)), adapted from Dziugaite and Roy 2017 and Keskar et al. (2017), is perturbation based and computed as
spaa-bayes-sharpess (f) r²
where a is the largest value such that
E0) [C(0 + D)] < D) 0.1.
(8)
In equation 8 L( D) is the prediction enror on the training dataset of the network with weights O as computed on data set D. This measure corresponds to a bound on parameter perturbations such that increases in training error remain beneath 0.1 in expectation in Jiang et al. (0220).
We additionally compare to the magnitude aware PAC- BAC-Bayes bound,
Mmag-ppn pae bar-bbyyye-sspppeee sharpaess (f)
(9)
o²2
where o' is the largest value such that
Eu-N(0.0=100+t [C(0+ u, D)] S ((,, + 0.1.
(10)
equation the variance of the perturbation to each parameter scaled according to the magnitude of that parameter, adding stability by accounting for differences in scales, and, implicitly, the size of the perturbation with the dimension of the parameter space. The value of is taken to be 0.001 as in Jiang al. (2020) and serves regularize the distribution, preventing the distribution from collapsing in the presence of weights that are close to O.
In general, path-norm acts only on model parameters, and is thus not directly connected to function- space or the shape of the loss. It should therefore be used with particular caution in comparing different architectures. Indeed, we found that path-norm tends to quickly saturate with increases in model size, with no preference between larger models even when these models provide very different generalization performance. We exhaustively considered how path-norm could be made provide reasonable performance on these problems. For smaller models, the path-norm is orders of magnitude larger than the path-norm computed on larger models. We therefore performed a log transform, which to our knowledge has not been considered before. We surprisingly found the log transform dramatically improves the correlation of path-norm to generalization performance for comparing amongst large convolutional nets and residual nets. However, this modified measure is still only associated with generalization, is highly sensitive to experimental details (e.g. size of models being compared), and does not provide any direct intuition for model comparison given its reliance parameters alone.
D HISTORICAL PERSPECTIVES ON EFFECTIVE DIMENSIONALITY
Here, we provided a detailed description of the history of effective dimensionality and related measures of flatness and generalization. Cleveland (1979) introduced effective dimensionality into the splines literature as a measure of goodness of fit, while Hastie and Tibshirani] (1990 Chapter 3) used it assess generalized additive models. Guul (1989) first applied effective dimensionality in a Bayesian setting for an image reconstruction task, while MacKay (1992a b) used it to compute posterior contraction in Bayesian neural networks, Moody (1992) argued for the usage of the effective dimensionality as proxy for generalization eгror, while Moody (191)) suggested that effective dimensionality could be used for neural network architecture selection. Zhang (2005) and Caponnetto and Vito (2077) studied the generalization abilities of kernel methods in terms of the effective dimensionality. Achille and Soatto (2088) argue that flat minima have low information content (many small magnitude cigenvalues of the Hessian) by connecting PAC-Bayesian approaches to information theoretic arguments, before demonstrating that low information functions learn invariant representations of the data.
Friedman et al. (2001 Chapter 7) use the effective dimensionality (calling it the effective degrees of freedom) compute the expected generalization gap for regularized linear models. Dobriban and Wager (2018) specifically tied the bias variance decomposition of predictive risk in ridge regression (e.g. the finite sample predictive risk under Gaussian priors) the effective dimensionality of the
16

---

Under review as a conference paper at ICLR 2021
feature matrix, + ob Hastie al. 22019), Muthukumar et al. (2019). Bartlett et al. (0119), Mei and Montanari )2019). and Belkin et al. (2019b) studied risk and generalization in over weer-paameterized linear models, including under model misspecification. [Bartlett et al. (2019) also introduced the concept of effective rank of the feature matrix, which has a similar interpretation to effective dimensionality.
Sagun et al. (2017) found that the eigenvalues of the Hessian increase through training, while Papyan (2018) and Ghorbani al. (2019) studied the eigenvalues of the Hessian for range of modern neural networks. Suzuki 2018) produced generalization bounds on neural networks via the effective dimensionality of the covariance of the functions at each hidden layer. Fukumizu et al. (2019) embedded narrow neural networks into wider neural networks and studied the flatness of the resulting minima in terms of their Hessian via a PAC-Bayesian approach.
Moreover, MacKay (2003) and Smith and Le (2018) provide an Occam factor perspective linking flatness and generalization. Related minimum description length perspectives can found in MacKay (2003) and [Hinton and Van Camp (1993). Other works also link flatness and generalization (e.g., Hochreiter and Schmidhuber,] 1997 Keskar et al.
2017: Chaudhari et al. 2019 [zmailov et al. 2018). with izmailov et (2018) and Chaudhari et al. (2019) proposing optimization procedures for flat minima.
To the best of our knowledge, Opper et al. 1989), Opper et al. 1990). Bös et al. (993)) and LeCun ctt al. [199T) introduced the idea that generalization lization error for neural networks can decrease, increase, and then again decrease with increases in parameters (e.g. the double descent curve) while Belkin et al. (2019a) re-introduced the idea into the modern machine learning community by demonstrating its existence wide variety of machine learning problems. Nakkiran al. (2020) found generalization gains as neural networks become highly overparameterized, showing the double descení phenomenon that occurs the width parameter of both residual and convolutional neural networks increased.
[Similar to our work, both Ghorbani et al. (2019) and Yao et al. (2019) use diffeernt implemen- tations of the Lanczos algorithm to estimate eigenvalues of the Hessian; however, they focus
on either estimating the spectral density (both) or on the trace of the Hessian (only Yao et al.
(, with Ghorbani al. 2019)'s work implemented in Tensorflow and Yao al. (0199) also implementing Lanczos in PyTorch.]
E MEASURING POSTERIOR CONTRACTION IN BAYESIAN GENERALIZED LINEAR MODELS
We first consider the over-parametrized case, k > n:
k
A post (0) = tr tr(Corppe) (0)) tr(CorppepD)( (0))
Σ Σ
2
()i t 2)-1 +
Σ a
i=1
t=1
1=--
a² +
ka² - -kk n)aa Σ
(): (a
Xi
-
1=1
(11)
A + tta+
where we have used Theorem 4.1 to assess the eigenvalues of the posterior covariance. When n > k. we have the simplified setting where the summation becomes instead of n, giving us that all of the cigenvalues are shifted from their original values to become X; + a and so
A X; + a
post. (0) = a
(12)
where >; is the ith eigenvalue of क TT/O22
17

---

Under review as a conference paper at ICLR 2021
E. CONTRACTION IN FUNCTION SPACE
We can additionally consider the posterior contraction in function space. For linear models, the posterior covariance on the training data in function space becomes
4 3 o² 2
(2
(13)
a2
while the prior covariance in function space is given by a - assumption that the features are normalized such that tr pp rank($p Now, we can simplify
T. We will make the simplifying
A
A ppnse()) (r(Coupp)(()) (C( o²
+ 0 02/02
i=1
d + 7 02/02
=
0² Σ
X; + 02/0²
02
= (a - X; + 02 /22
)j + o 02/
Simplifying and recognizing these summations as the effective dimensionalities of $ T q ($p $) we get that
and
Apoct (f) = (a²
-o?)Nes - 4 + ( () a0)
(14)
= = 20 ( 02 /2²
thereby showing that the posterior contraction in function space is explicitly tied to the effective dimensionality of the Gram matrix.
F POSTERIOR CONTRACTION AND FUNCTION-SPACE HOMOGENEITY PROOFS AND ADDITIONAL THBOREMS
In this section we complete the proofs Theorems and 4.2 and extend the results from linear models to generalized linear models.
F.1 PROOF AND EXTENSIONS TO THEOREM 4.1
Theorem (Posterior Contraction in Bayesian Linear Models). Let & = x(x) E Bank be a feature map of data observations, x, with n and assign isotoopic prior (0,,, a a²1,) for parameters B E & Assuming a model of the form y ~ N(33, I²I,) the posterior distribution of has an [k n1 directional subspace in which the variance identical the prior variance.
Proof. The posterior distribution of ,3 in this case is known and given as
3 N ((n)D), (E(D)
D|D ④ 2/0² So 1
+ y/o²
(15)
E ( 0/0² + 1
We want to examine the distribution of the cigenvalues of the posterior variance. Let $ T T/ VA,V be the cigendecomposition with eigenvalues A diag(?1.... Yr. On+1...., 0&); k of the eigenvalues are 0 since the gram matrix + T is at most rank [ni] by construction. Substitution into the posterior variance of yields,
④ 0 + - = (VAVT a V(A + -212)))61 -VT
(16)
V.VT
18

---

Under review as a conference paper at ICLR 2021
The cigenvalues of the posterior covariance matrix .......")). a²), where there are k - n eigenvalues that retain a
given by the entries of I,
((11 + a +-=.)) a-= .a........ value of o² [Therefore, the posterior covariance has - n directions in which the posterior variance is unchanged and directions in which it has contracted as scaled by the eigenvalues of the gram matrix & P.]
+ a
Generalized linear models (GLMs) do not necessarily have closed form posterior distribution. However, Neal and Zhang (006) give a straightforward argument using the invariance of the likelihood of GLMs to orthogonal linear transformation in order to justify the usage of PCA as a feature selection step. We can adapt their result to show that overparameterizee GLMs have k dimensional subspace which the posterior variance is identical to the prior variance.
Theorem F.1 (Posterior Contraction in Generalized Linear Models). We specify generalized linear model, E|Y] = 9 100--9-(0000 ($ and ar(Y))
Vg (33)), where & E RT*k a feature matrix of n observations and k features and f E E are the model parameters. In the overparameterized setting with isotropic prior on B, there exists a k - n dimensional subspace in which the posterior variance is identical to the prior variance.
Proof. First note that the likelihood of a GL.M takes as argument 4,3, thus transformations that leave 2 unaffected leave the likelihood, and therefore the posterior distribution, unaffected.
Let R be orthogonal matrix, R R RRT Ip. and 3 R3 N((0,22). If we assign a standard isotropic prior, to B then ,3 = R3 N/ 0² RIRR = 12). If we also rotate the feature matrix, = R E Raxk so that $ = & R3 = D33, showing that the likelihood and posterior remain unchanged under such transformations.
In the overparameterized regime, > n, with linearly independent features we have that & has rank most k and that are all O. This defines a n dimensional subspace of B3 E I which the the likelihood is unchanged. Therefore the posterior remains no different from the prior distribution in this subspace, or in other words, the posterior distribution has not contracted in k n dimensions.
therefore choose R to be a rotation such that R has exactly A columns
F.2 FUNCTION-SPAA HOMOGENEITY
Theorem (Function-Space Homogeneity in Linear Models), Let ((x) gank be a feature map of n data observations, with < k and assign isotropic prior B ~~ N(,,, = a²I,) for parameters B E R The minimal eigenvectors of the Hessian define a dimensional subspace in which parameters can be perturbed without changing the training predictions in ffunctionsspac
Proof. The posterior covariance matrix for the parameters is given by
② +
Egp
+ ta
-2
and therefore the Hessian of the log-likelihood is there are k- - n eigenvectors of the Hessian all with eigenvalue a -2, If we have some perturbation to the parameter vector that resides in the span of these eigenvectors we have
0² To + o By the result in Theorem 4.1
+ a +a-21a
= a-
@02
which implies u is in the nullspace of T ΦD By the properties of gram matrices we have that the nullspace of Φ T & is the same as that of 4b thus is also in the nullspace of Φ Therefore any prediction using perturbed parameters takes the form 9 = ( + u) = 43, meaning the function-space predictions on training data under such perturbations are unchanged.
Theorem F.2 (Function-Space Homogeneity in Generalized Linear Models). We specify generalized linear model, Y = g- (Φ3), where & E R k is a feature matrix of n observations and features and B E R the model parameters. In the overparameterized setting with isotropic prior on B, there exists a l n dimensional subspace in which parameters can be perturbed without changing the training predictions function space or the value of the Hessian.
19

---

Under review as a conference paper at ICLR 2021
2.0
Test Error
Effective Dimerrsioncllly
Train Error
1.5
Effective Dimensionality
1.0
0.5
0.0
500
200
300 350
Number of Features
Figure A.10: Demonstration of double descent for linear models with an increasing number of features. We plot the effective dimensionality of the Hessian of the loss. In the regime with near- zero train error, the test error is almost entirely explained by the effective dimensionality, which is computed on the train set alone. The red region corresponds to underparameterized models, yellow to critically parameterized models, and green to overparameterized models.
Proof. The Hessian of the log-likelihood for GLMMs can be written as a function of the feature map, T and the product of the feature map and the parameters, 3 i.e. B only appears multiplied by the feature map (Nelder and Wedderburn, 1972). We can then write H.g = f ②) Additionally predictions are generated by y = 9 (3)). Since & R"xP with n < < there is a nullspace of + with dimension at least n p. Thus for any E null( we have g ($ + =)) g- (bb,)
and /( ( [3+ + u), +)) = [ +) Hgg which shows that the training predictions and the Hessian remain unchanged.
G TRAINING DETAILS
For the double descent experiments in Figures and 2 following sources:
we use neural network architectures from the
CNNs
from
double /eceaa////r////aatta//////////// but also include an option to vary the depth,
R8sNet18
from
Specifically, train with SGD with a learning rate of 10-2 momentum of 0.9, weight decay of 10-4 (thus corresponding approximately to a Gaussian prior of with variance 1000) for 200 epochs with batch size of 128. The learning rate decays to 10-4 44 following the piecewise constant learning rate schedule in Izmailov et al.) (2018) Maddox et al. (019). beginning to decay at epoch 100. We use random cropping and flipping for data augmentation turning off augmentations to compute eigenvalues of the Hessian.
H DOUBLE DESCENT AND EFFECTIVE DIMENSIONALITY: FURTHER EXPERIMENTS
Linear Models
Although double descent is often associated with neural networks, we demonstrate similar behaviour with linear model with varying number of features: first drawing 200 data points (N, 1) and then drawing 20 informative features y 6, where ~ NO, 1). before drawing 20 features that are also just random Gaussian noise, where the total number of features in
the model For the test set, repeat the generative process. In Figure A.10 we show pronounced double descent curve in the test error as we increase the number features, which is mirrored by the effective dimensionality.
In Figure A.
we plot the effective dimensionality against the test error for the linear model example in Section A clear lincar-looking trend is observed, which corresponds to the models that have nearly zero training error. The bend near the origin is explained by models that do not have enough
pynb
20

---

Under review as a conference paper at ICLR 2021
capacity fit therefore, their effective dimensionality is very small. We observe similar trend for ResNets and CNNs.
Coresiaaton
Clickie Dimoriorsll
Effective dimensionality plotted against generalization gap (test error train error) for the linear model of Section [ Note that all but the very smallest models with effective dimensionality track nearly linearly with generalization error.
Figure A.11:
Small Neural Networks Finally, we consider several further experiments on two spirals prob- lem to test the effects of increasing depth and width serve sanity check for results both ResNets and CNNs. In Figure [A.12] we fix the number of data points to 3000, and vary the depth and 15
of the neural network (20 hidden units each layer, ELU activations) using between hidden units, training for 4000 steps as before. Here, we run each experiment with 25 repetitions and compute all of the eigenvalues of the Hessian at convergence (the largest model contains 6000 parameters). In the left panel, we see a pronounced double descent curve with respect to both effective dimensionality and test loss three hidden layer networks, varying the width of each layer between one and 30 units per layer. Here, we see only monotonic decrease in both test error and effective dimensionality with increasing width not helping that much in terms of test error the effective dimensionality is highest for the models with smallest size and slowly decreases as the width increased. These results serve as sanity check on our large-scale Lanczos results in the main text.
vary depth. In the right panel,
the same data points, but
Test loss
Test Error
Gen. Gap
Nef (Hessian)
0.9434
0.9188
0.9429
PAC-Bayes
00.8433
007777
-.8597
Mag. PAC-Bayes
0.7066
0.8270
0.6805
Path-Norm
0.5598
0.7216
0.5259
Log Path-Norm
0.9397
0.9846
0.9257
Table Sample Pearson correlation with generalization on double descent for ResNet18 of varying width on CIFAR-100 with training loss below 0.1.
Test loss
Test Error
Gen. Gap
Nej (Hessian)
0.9305
0.9461
0.9060
BayeBayes
-0.8619
-0.7916
-0.8873
Mag. PAC PAC-Bayes
0.8724
0.9225
0.8330
Path-Norm
0.7996
0.7721
0.7511
Log Path-Norm
0.9781
0.9402
0.9602
Table 2: Sample Pearson correlation with generalization for CNNs of varying width and depth on CIFAR-100 with training loss below 0.1.
Deep Networks In Figure A.15 we plot the effective dimensionality against the test error for the ResNet18s trained on CIFAR-100 with 20% data corruption. We show the sample Pearson correlation with respect test loss, dimensionality along with PAC-B Bay-Bayes, magnitude aware PAC-Bayee path norm, and the logarithm of the path norm in Table 3 Finally, in Figure A.14 we plot the PAC-Bayes and magnitude aware
and the generalization gap for the same dataset of effective
21

---

Under review as a conference paper at ICLR 2021
Increasing Depth
Increasing Width
Effectiv Dimennionailo
14
Effective Dimensionalty
34
22.
2.-
183
12:0
1390
1750
Parameters
Test Offective Dim
Final Loss
Figure A.12: Left: Increasing depth the spirals problem. Clearly is double descent curve where the test loss first increases before decreasing as function of depth. The effective dimensionality follows the same trend. Right: Increasing width the two spirals problem. Here, increased width produces constant test performance after the training loss reaches zero, and the effective dimensionality stays mostly constant. Shading represents two standard deviations as calculated by 25 random generations of the spirals data.
Test loss
Test Error
Gen. Gap
Nef (Hessian)
0.8772
0,87608
0.8578
-Bayss
0.6644
0.6424
0.7758
Mag. PAC- PAC-Bayes
0.6933
0.6728
0.7956
fith-Norm
0.6722
0.6478
0.7937
Log Norm
0.9585
0.9492
0.9836
Table 3: Sample Pearson correlation between generalization measures and the test loss, test error, and generalization gap for ResNet1 8s of varying width trained CIFAR-100 with 20% corruption that achieve a training loss below 0.1. Among these models effective dimensionality and path-norm are correlated with test loss, test error, and the generalization gap.
PAC-Bayes bounds on their raw scale for ResNet18s 8s trained on CIFAR-100 and on the 20% corrupted CIFAR-100 dataset. The trends are similar for the bounds across the two datasets, with the BAC-Bayes bound generally increasing width increases. The magnitude aware PAC-Bayes bounds also act similarly, decreasing as width increases.
I EFFECT OF NUMBER OF EIGENVALUES USED
[Figure| shows the model effective dimensionality for small MLPs trained on the two spi- rals problem from Section A.2 over 10 random initializations when vary how many eigen- values are used in the computation. From this experiment we see first that provided a large enough amount of the dominant eigenvalues to exactly how many eigenvalues are considered. Secondly, we observe that upon repeatedly initializing and training networks the effective dimensionality generally falls in the range of values, to some randomness in that we may find classifiers of different performance in each training run.]
used, effective dimensionality is insensitive
22

---

Under review as a conference paper at ICLR 2021
Test Loss
Test Error
6
Depth
4-
4
2.0
2
20
28
36
44
52
20
28
36
44
52
Ner(Hessian)
PAC Bayes
Mag. PAC Bayes
1.0
Measure (std)
6
00.5
Depth
4
2
-055
20
28
36
44
52
20
28
36
44
52
20
28
36
44
52
Path Norm
Log Path Norm
-1.5
Depth
-2.0
2
20
28
36 Width
44
52
20
28
52
Width
Figure A.13: Plots of all generalization errors considered by width and depth. The green curve separates models that achieve below 0.1 training error. Additionally, we standardize all measures and test eтrоr to 0 mean and unit variance for comparison.
PAC Bayes
Magnitude Aware PAC Bayes
30000
6000
25000
5000
20000
4000
Bound
Bound
15000
3000
10000
2000
5000
1000
40
60
20
40
60
Width
Width
CIFAR100
CIFAR100 Label Noise
Figure A.14: PAC-Bayes and magnitude aware PAC- Bayes bounds displayed their raw scale for both CIFAR-100 and the 20% corrupted CIFAR-100. All have a significant spike near a width of 20 which is when training loss first reaches zero. The standard PAC-Bayes bounds increase width increases, while the magnitude aware ones seem to decrease towards zero.
23

---

Under review as a conference paper at ICLR 2021
98
55
96
Wen(Hessian)
Test Error
92
45
90
88
10
20
30
40
50
60
84
Width
Nar(Hessian)
Error
Figure A.15: Double descent with respect to error as demonstrated ResNet18 on CIFAR-100 with 20% corruption. The effective dimensionality again tracks the double descent curve, this time present in the test error rather than loss.
Effective Dimensionalitt
$0
Number of Eigenvalues Used
Figure A.16: [Violin plots of effective dimensionality over 10 random initializations of the two spirals problem when the top eigenvalues are used to compute the model effective dimension- ality].
24


Reviews:
[{"review_id": "w7Fzl3jMUU", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper explores the effective dimensionality of the Hessian as a possible explanation for why neural networks generalize well despite being massively overparametrized.\n\nWhile I concur with the intuition, I think in the current state of the paper, some points could be improved and clarified.\n\n### Relationship between Hessian and posterior covariance\n\nWhile you mainly reason in the Bayesian framework about the posterior, it seems that networks in fig 1, 6, 7 are trained using ML. So why would the Hessian of the ML estimator relate to the covariance of the posterior?\n\n### Theorem 4.1\n\nTheorem 4.1 shows that even with $k \\gg n$ parameters, there are only $n$ directions in which the posterior covariance changes from the prior. But the rest of the discussion shows that the effective dimension actually decreases, which is not captured by your theorem. In this regard, I consider this theorem as an illustration of why the effective dimension does not increase with increasing number of parameters, a statement that is weaker than saying that the effective dimension actually decreases.\n\nTherefore, we can say that your argument for advocating in favor of using the effective dimension as a proxy for generalization is mainly empirical. Then I would have appreciated a more thorough ablation study, that would demonstrate that the correlation is still occuring while varying other hyperparameters.\n\n### Figures 4\n\nFig 4: can you precisely state what is plotted, i.e. for a fixed $z$ why do we have several datapoints?\n\n### Conclusion\n\nAs already said in the beginning I really like the idea of effective dimension playing an important role in generalization. I however think that relationship between the hessian of ML estimator and the covariance of the posterior, as well as the empirical study, should be improved before this is published.", "extra_scores": {}, "extra_text": {}}, {"review_id": "W5BOweb0sva", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "summary: \nThis paper provide a unified view of the generalization ability in the Bayesian deep learning framework through the effective dimensionality. The authors claim that some phenomenon in the deep learning such as generalization in #parameter >> #data settings, and double descent can be explained by the effective dimensionality. \n\nAlthough the theorem and experiments in the paper suggest that some of these properties can be explained by effective dimensionality, it is insufficient to convince that it substitutes other measures such as parameter counting. \nFor example, in Figure 2 abd 7, the effective dimensionality shows a very different behavior from test loss and test error when the width is small.　In other words, effective dimensionality does not seem to account for the first descent in Figure 2 and Figure 7 (although it follows the second descent well). \n\ntypos\n\n- p.17 in MEASURING POSTERIOR CONTRACTION IN BAYESIAN GENERALIZED LINEAR MODELS\n\n\t-- The numerator in the second line of equation (11): 1 - \\alpha^2(\\lambda_i + \\alpha^-2) -> \\alpha^2(\\lambda_i + \\alpha^-2) - 1?\n\t\t\n- p.18 in F.1 PROOF AND EXTENSIONS TO THEOREM 4.1\n  \n  -- \"...the posterior distribution of \\beta has an p-k directional subspace...\" -> \"...the posterior distribution of \\beta has an k-n directional subspace...\"?\n  \n  -- \"Therefore, the posterior covariance has p-n directions...\" -> \"Therefore, the posterior covariance has k-n directions...\"?", "extra_scores": {}, "extra_text": {}}, {"review_id": "CNy4lQWoIEa", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\n\nThe paper applies the effective dimensionality (introduced by MacKay, Gull and others) to study the generalization properties of large probabilistic models. Effective dimensionality is the number of parameters determined by the data (derived from the curvature of the posterior at the MAP estimate), and shown to be more informative than simple parameter counting. After demonstrating the usefulness of the effective dimensionality, the authors study double descent observed when training deep nets of increasing width/depth. The authors argue that double descent is an artifact that can be understood by studying the effective dimensionality of the model. They take a detailed look at width-depth trade-offs using numerical experiments. Moreover, they compare the effective dimensionality with other generalization measures and find a superior performance. \n\n# Assessment\n\nOverall, I enjoyed reading the paper. Most of the time it is well-written and provides some new insights into questions concerning generalization in probabilistic models. So I'm tending towards acceptance, but there are several problems with the current version of the paper. \n\n## Pros\n\n- Effective dimensionality is shown to be a useful quantity to understand generalization properties of probabilistic models in particular deep neural nets. \n\n- Effective dimensionality helps us understand width-depth trade-offs in deep learning. \n\n- Effective dimensionality is a metric for generalization solely based on the training data. \n\n## Cons\n\n- Effective dimensionality rests on the Laplace approximation (of the log posterior) which fails for multimodal posteriors. \n\n- Organization of material is suboptimal. For example, section 5 refers to figures 1 and 2, which already has been discussed in the Introduction. Occasional sloppiness in notation and wording. \n\n- Theorems are rather elementary; I'm not sure whether they should be highlighted as theorems. Validity for neural nets is only hypothesized and demonstrated empirically. Any analytical results? \n\n# Comments / Questions\n\n- The organization of paper a bit difficult to follow. Central results (Figs. 1 and 2) are already shown early in the paper and later explained in more detail... \n\n- There is no explanation as to why the effective dimensionality decreases with increasing width/depth (as shown in Figs. 1 and 2). Why do we see a decrease in effective dimensionality?\n\n- How stable is the calculation of effective dimensionality across different training runs?\n\n- If you are only computing the 100 largest eigenvalues, the effective dimensionality will always be smaller or equal to 100. Why do you restrict the effective dimensionality to a maximum of 100 in most of your experiments?\n\n- How much sense does effective dimensionality make for multimodal posteriors?\n\n- The use of the notion \"effective dimensionality\" is sometimes confusing: On the one hand, it is a property of any positive semi-definite matrix (Eq. 2). On the other hand, most of the time \"effective dimensionality\" is implicitly understood as \"the effective dimensionality of the model\" (i.e. $N_{eff}$ of the Hessian of minus log posterior). I would prefer to use $N_{eff}$ when you talk about the effective dimensionality of a specific matrix and \"effective dimensionality of the model\" when you mean $N_{eff}$ of the Hessian of minus log posterior. An instance where your ambiguous use of \"effective dimensionality\" leads to confusion can be found on page 5: \"For Bayesian linear models, the effective dimensionality of the parameter covariance is the inverse of the Hessian\" -- it's not clear to me what you mean by that...\n\n- Page 2: \"we expect models with lower effective dimensionality to generalize better\" -- why?\n\n- Page 3: Right before eq. (1): You specify \"$y \\sim \\mathcal N(f=\\Phi^T\\beta, \\sigma^2)$\". What do you mean by \"$f=...$\"? Shouldn't \"$f=$\" be removed? Moreover, in the theorems and their proofs you work with the transpose of $\\Phi$ since the model is $y\\sim \\mathcal N(\\Phi\\beta, \\sigma^2 I_n)$... Also the prior \"$\\beta \\sim \\mathcal N(0, \\alpha^2 I_N)$\" is not consistent with the theorems and the appendix where $k$ (sometimes $p$) is used to indicate the number of parameters. \n\n* Page 3: Right after eq. (1): \"where $\\lambda_i$ are the eigenvalues of $\\Phi\\Phi^T$, the Hessian of the log likelihood\". Strictly speaking $\\Phi\\Phi^T/\\sigma^2$ is the Hessian of minus log likelihood. Once again, please use one consistent model and notation in the main text and the appendix (either $y\\sim \\mathcal N(\\Phi^T\\beta, \\sigma^2 I_n)$ or $y\\sim \\mathcal N(\\Phi\\beta, \\sigma^2 I_n)$ -- I prefer the latter in which case the Hessian of minus log likelihood is $\\Phi^T\\Phi/\\sigma^2$ rather than $\\Phi\\Phi^T/\\sigma^2$...) and carefully adapt all expressions that are affected by your choice. \n\n- Page 6, Equation 3: Your Occam factor scales with $1/\\sqrt{\\mathrm{det}(\\mathcal H_\\theta)}$. What happens if the Hessian is singular (which is bound to happen for overparameterized models)? Comparison with MacKay's definition reveals that you should replace $\\mathcal H_\\theta$ with $\\mathcal H_\\theta + I_k / \\alpha^2$, which resolves the trouble with singular Hessians of minus log likelihood. \n\n- Also in other instances, you tend to focus on the Hessian of minus log likelihood, whereas MacKay looks at $A = - \\nabla\\nabla \\log p(\\theta|\\mathcal D, \\mathcal M) = \\mathcal H_\\theta + I_k/\\alpha^2$ (Hessian of minus log posterior / posterior curvature / inverse posterior covariance). I find this confusing. I think it would help to always clearly state, if you talk about the Hessian of minus log likelihood or the Hessian of minus log posterior. \n\n- Appendix: \"In the overparameterized regime, $k > n$, with linearly independent features we have that has rank at most $k$\" (page 18). This is incorrect, the rank is at most $n$. In both proofs: Why not argue using the SVD of the feature matrix? If $\\Phi = U\\Lambda V^T$ with column-orthogonal matrices $U, V$ such that $U^TU=V^TV = I_r$ (where rank $r \\le \\min(n,k)$), we have $\\Phi\\beta = U\\Lambda V^T\\beta$. Use projectors $P=VV^T$ and $P_\\perp=I_k - VV^T$ to decompose $\\beta$ into contributions that affect the prediction, $P\\beta$, and perturbations that do not change the prediction, $P_\\perp\\beta$ (also: $\\|\\beta\\|^2 = \\|P\\beta\\|^2 + \\|P_\\perp\\beta\\|^2$). $P$ projects into an $r$-dimensional linear subspace, $P_\\perp$ projects into the orthogonal space (dimension: $\\max(n,k) - r$) of neutral perturbations: $\\Phi\\beta=\\Phi(P + P_\\perp)\\beta = \\Phi P\\beta$ since $\\Phi P_\\perp = 0$. \n\n# Minor\n\n* Page 2: symbol $\\mathcal L$ (log likelihood) is not or only implicitly defined in the text\n\n* Page 5, Fig. 5, left panel: The tick labels on the right axis ($N_{eff}$) are very small (ranging from 0 to 4). Is this correct?\n\n* Page 6, Equation 3: It would be helpful to explain all symbols (i.e. $p(\\theta_{MP}|\\mathcal M)$ is the prior evaluated at the MAP estimate...)\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "46sZF6VHW84", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**: In this article, the authors revisited the idea of *effective dimensionality* as a complexity measure for large-scale machine learning systems, and in particular, modern deep neural networks. Theoretical arguments were provided for linear and generalized linear models (Theorem 4.1 and 4.2). Connections were made between the proposed effective dimensionality and the double descent phenomenon, width-depth trade-off, function-space homogeneity, and other generalization measures in the literature. Experiments on linear models as well as deep networks (ResNet18) were provided to support the effectiveness of the proposed metric.\n\n**Strong points**: The authors revisited the idea of *effective dimensionality* as a complexity measure for large-scale machine learning systems, and in particular, modern deep neural networks. Theoretical arguments were provided for linear and generalized linear models. Insightful discussions were made on the connection between the proposed effective dimensionality and the double descent phenomenon, width-depth trade-off, function-space homogeneity, and other norm- or flatness-based generalization measures. The paper is in general well-written.\n\n**Weak points**: The presentation of the article can be significantly improved. The contribution, from either a theoretical (Theorem 4.1 and 4.2 on Bayesian linear models with Gaussian prior, with generalized linear models in the appendix) or an empirical (ResNet18 on CIFAR-100) perspective, seems not enough for a clear accept.\n\n**Recommendation**: On account of the theoretical or empirical contributions of this work, I find this paper somewhat borderline. Nonetheless, according to the strong points I mentioned above and in particular, the interesting and novel insights offered by this paper into the understanding of deep neural nets, I'm more leaning toward an acceptance. \n\n**Detailed comments**: \n\n* P3 Section 2 \"matrix of second derivatives of the loss, $H_{\\theta} = - \\nabla \\nabla_{\\theta} \\mathcal L(\\theta, \\mathcal D)$\": what does $\\mathcal D$ mean here?\n* P3 Section 2.1 \"This increase in curvature of the loss that accompanies certainty about the parameters leads to an increase in the eigenvalues of the Hessian of the Growth in eigenvalues of the Hessian of the loss corresponds to increased certainty about parameters\": is this a **general** claim, how is this theoretically/empirically supported? And it is not clear, at least to me, how the same intuition built here extends to general cases as claimed by the authors below Figure 4 in P4.\n* are the (Hessian) eigenvalues assumed to be all **positive** in the definition of effective dimensionality? This may not be the case for neural networks.\n* \"Therefore, effective dimensionality explains the number of parameters that have been determined by the data\": at this point (of the article), it is not yet clear to me how the effective dimensionality defined above is connected to the data.\n* P4 Practical Computations: there exists a library called \"PyHessian: Neural Networks Through the Lens of the Hessian\" that can perform many eigenspectrum-based computations of the Hessian of deep neural nets, which might help to conduct experiments beyond the first $100$ eigenpairs of the Hessian, though honestly, I have not tried it myself.\n* Theorem 4.2 states the \"function-space homogeneity\" of a subspace of the Hessian, in the sense of the training prediction, how does this affect the test performance of the model?\n* Section 5.1: \"tracks remarkably well with generalization — displaying the double descent curve that is seen in the test loss\": this is not entirely true, the first (local) minimum of the effective dimensionality and of the test loss appear at a relatively different width. It seems to me that the proposed metric is more \"accurate\" for (nearly) interpolation models (i.e., models with zero or low training loss): this is also seen at the bottom of the left plot of Figure 2 where the effective dimensionality (with high training loss) is low, while it is not the case for test loss.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors re-state Mackay's definition of effective dimensionality and describe its connections to posterior contraction in Bayesian neural networks, model selection, width-depth tradeoffs, double descent, and functional diversity in loss surfaces. The authors claim the effective dimensionality leads to a richer understanding of the interplay between parameters and functions in deep neural networks models. In their experiments the authors show that effective dimensionality compares favourably to alternative norm- and flatness- based generalization measures.

Strengths:

1 - The authors include a description of how to compute a scalable approximation to the effective dimensionality using the Lanczos algorithm and Hessian vector products.

2 - The authors include some novel experimental results showing the effective dimensionality with respect to changes in width and depth. These results are informative in how changes in depth and width affect this metric in a different way. The same for the experiments with the double descent curve.

Weaknesses:

1 - For some reason the authors seem to have taken the concept of effective dimensionality from David Mackay's approximation to the model evidence in neural networks and ignored all the extra terms in such approximation. It is currently unclear why there is a need to do this and focus only on the effective dimensionality. Almost all the experiments that the authors describe could have been done using a similar approximation to Mackay's model evidence. It is unclear why is there a need to focus just on a part of Mackay's approximation. The fact that the authors state that the effective dimensionality is only meaningful for models with low train loss seems indicative that David Mackay's approximation to the model evidence would be a better metric.

2 - With the exception of the experiments for changes in the effective dimensionality as a function of the depth and width and the double descent curve, all the other experiments and results are expected and not new to anyone familiar with David Mackay's work.

3 - The experiments on depth and width are for only one dataset and may not be representative in general. The authors should consider other additional datasets. 

The authors should improve the paper, including a justification for using only the effective dimensionality and not David Mackay's approximation to the model evidence. They should also strengthen the experiments by comparing with David Mackay's approximation to the model evidence and should consider additional datasets as mentioned above.
Decision: Reject