Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: summary: 
This 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. 

Although 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. 
For 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). 

typos

- p.17 in MEASURING POSTERIOR CONTRACTION IN BAYESIAN GENERALIZED LINEAR MODELS

	-- The numerator in the second line of equation (11): 1 - \alpha^2(\lambda_i + \alpha^-2) -> \alpha^2(\lambda_i + \alpha^-2) - 1?
		
- p.18 in F.1 PROOF AND EXTENSIONS TO THEOREM 4.1
  
  -- "...the posterior distribution of \beta has an p-k directional subspace..." -> "...the posterior distribution of \beta has an k-n directional subspace..."?
  
  -- "Therefore, the posterior covariance has p-n directions..." -> "Therefore, the posterior covariance has k-n directions..."?
review_title: Official Blind Review#4 

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper explores the effective dimensionality of the Hessian as a possible explanation for why neural networks generalize well despite being massively overparametrized.

While I concur with the intuition, I think in the current state of the paper, some points could be improved and clarified.

### Relationship between Hessian and posterior covariance

While 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?

### Theorem 4.1

Theorem 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.

Therefore, 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.

### Figures 4

Fig 4: can you precisely state what is plotted, i.e. for a fixed $z$ why do we have several datapoints?

### Conclusion

As 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.
review_title: Interesting avenue, but requires improvements

final_score: rating: 6: Marginally above acceptance threshold
review_content: # Summary

The 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. 

# Assessment

Overall, 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. 

## Pros

- Effective dimensionality is shown to be a useful quantity to understand generalization properties of probabilistic models in particular deep neural nets. 

- Effective dimensionality helps us understand width-depth trade-offs in deep learning. 

- Effective dimensionality is a metric for generalization solely based on the training data. 

## Cons

- Effective dimensionality rests on the Laplace approximation (of the log posterior) which fails for multimodal posteriors. 

- 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. 

- 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? 

# Comments / Questions

- 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... 

- 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?

- How stable is the calculation of effective dimensionality across different training runs?

- 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?

- How much sense does effective dimensionality make for multimodal posteriors?

- 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...

- Page 2: "we expect models with lower effective dimensionality to generalize better" -- why?

- 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. 

* 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. 

- 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. 

- 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. 

- 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$. 

# Minor

* Page 2: symbol $\mathcal L$ (log likelihood) is not or only implicitly defined in the text

* 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?

* 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...)


review_title: Interesting insights into generalization in deep learning based on the effective dimensionality 

final_score: rating: 6: Marginally above acceptance threshold
review_content: **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.

**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.

**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.

**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. 

**Detailed comments**: 

* 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?
* 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.
* are the (Hessian) eigenvalues assumed to be all **positive** in the definition of effective dimensionality? This may not be the case for neural networks.
* "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.
* 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.
* 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?
* 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.
review_title: A borderline paper with interesting insights? 

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