A Two-Scale Complexity Measure for Deep Learning Models

Summary

This paper proposes a new capacity measure for a general statistical model, called two-scale effective dimension (2sED), and provides an upper bound (under some assumptions on the model) on the generalisation error for this model based on the proposed measure. Then, the authors show how to lower bound the proposed 2sED for Markovian models such as feed-forward neural networks.

Strengths

The authors obtain a nice upper bound on the generalisation error for any statistical model (including deep learning models) that satisfies some key conditions (please see my comment on these conditions below).

Weaknesses

+ Theorem 5.1 is obtained thanks to some assumptions on the statistical model, some of them look very hard to verify for practical deep neural networks (DNNs). For example, the assumption (iii) that the Fisher matrix $F(\upsilon)$ is $L$-Lipchitz looks too ideal, and I don't know there exists any DNNs such that this assumption holds. + Notations are not consistent: for example (2) and (19).

Questions

+ Please explain why (iii) holds for some deep neural networks (DNNs)? Can you give an example of a DNN such that this assumption holds? + Please explain the last step in the proof of Lemma B.1. + What is $S_{\epsilon}$ in the line 456? + Please explain the last equality in p.15 (refer to the definition of $d_{\zeta}(\epsilon)$ in (4)). + The definition of $d_{\zeta}(\epsilon)$ in (9) looks not the same as (4) (for example, as $L=1$).

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

This is a theoretical research paper, hence the negative society impact of this work is not direct. The authors mention some technical limitations of this work in Section 7.

Summary

In this work, a new measure of model complexity, 2sED, is introduced. It is used to derive a new generalization bound for statistical models. A special case of 2sED is shown for Markovian models. Experiments show that the complexity measure correlates with the training loss of neural networks.

Strengths

1. Addresses an important and challenging topic. 2. Solid mathematical results. 3. Clearly written.

Weaknesses

- The main weakness is that the significance of the results are not clear. Concretely, it seems that when using the empirical Fisher matrix (as in the experiments), the generalization bound has the same value for all models that perfectly fit the training set. Therefore, it is not clear how this result can facilitate model selection. Furthermore, it is not clear how the bound can shed light on the generalization performance of neural networks, since 2sED is not simple to analyze. - Some technical details are missing. (1) The derivation of 2sED from the effective dimension (2) Explicit example of a Markovian model (e.g., a feed-forward network). - The empirical results are limited showing correlation only with the training loss and not the validation/test loss which is the main goal.

Questions

- Does the generalization bound have the same value for all networks that perfectly fit the training set, if the empirical Fisher matrix is used? - Does 2sED satisfy (P2) in line 19?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Not all limitations are mentioned (e.g. experiments only show correlation of 2sED with the training loss and not the validation/ test loss).

Summary

This paper proposes a two-scale complexity measure that can be used to derive generalisation bounds on the empirical risk. This measure is intuitive and comes from the box-counting dimension of the parameter space with the Fisher metric. From what I can understand, authors please correct me if I'm wrong, the idea is that under the Fisher geometry, this describes how complex the parameter space is. We are seeking to identify the intrinsic complexity ( or stand in, dimension ) of this space as a surrogate for how difficult our modelling problem is. It seems natural to me that then the effective dimension of parameter space would then control the generalisation error.

Strengths

This is a very nicely written learning theory paper. I find the complexity measure defined very well motivated and the definitions given by the authors striking a good balance between mathematical precision and applicability to large deep learning architectures. The mathematical proofs are well presented and the correct amount of detail in the main text is given for a conference paper. The true strength of this paper is the simplicity of what the authors are proposing as a complexity measure. I believe that the Fisher information is the correct Hilbert space to analyse such complexity and intrinsic dimensions are natural here. The theory is shown to correlate with simple experiments.

Weaknesses

This paper fall folly to a hard problem with both fractal dimensions and Fisher information matrices. Computing the eigenvalues of the FIM is a computationally intensive task and hinders the current proposed method. Further, it is well known that box-counting dimensions can be extremely difficult to estimate, particularly when boxes may not cover the target set efficiently. Both of this computational bottlenecks prevent this work being directly applicable to analysis of deep learning models.

Questions

My first question is does this work bare any similarity to the following papers: A. Camuto, G. Deligiannidis, M. A. Erdogdu, M. Gurbuzbalaban, U. Simsekli, and L. Zhu, "Fractal structure and generalization properties of stochastic optimization algorithms", NeurIPS (Spotlight), vol. 34, 2021. B. Dupuis, G. Deligiannidis, and U. Simsekli, "Generalization Bounds with Data-dependent Fractal Dimensions", ICML, 2023. In particular, the latter paper employs techniques from TDA to look at a range of box-covering sizes and add stability to the proposed method in this way. Do the authors think that possibly making their complexity measure a barcode could help make the derived statistic more stable? My second question moves to the practical aspect of the authors work. Can the authors put in a section on the approximation of eigenvalues for their method? It has been hinted toward in the OOD literature that the FIM of large neural networks has a sparse structure. There are eigenvalue methods for sparse matrices which I think to benefit the authors work and believe this is worth putting in the main text to assist the community with evaluating the method. My last question is: box-counting dimensions are typically a surrogate for some form of Hausdorff dimension. Do the authors think that simple Fisher boxes are the best choice or could another way of covering the desired sets be more appropriate in practice. I also usually understand that we typically need lower and upper box-counting dimensions, can the bound derived in the authors main theorem be also compared with what we might expect with the lower/upper box counting dimensions if these are not equal?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

The authors do an excellent job at stating their mathematical assumptions and computational bottlenecks. This paper honestly addresses its limitations.

Summary

The authors introduce a new complexity measure for machine learning models. The complexity measure induces generalization bounds and admits approximations for Markovian models. The authors show that this method is helpful for estimating the generalization error on several feed-forward neural networks.

Strengths

- The authors study a fundamental problem in theoretical machine learning and introduce a novel approach to this problem - Unlike many other complexity metrics, this one admits efficient approximations in many settings - Empirically, the model seems to have predictive utility in terms of predicting model performance

Weaknesses

- A more thorough discussion of previous work on the expressivity of neural networks (and how this method fits into that literature), would be helpful to better evaluate the strength of the contributions.

Questions

How does the method fit into the existing literature on understanding the expressivity of neural networks?

Rating

6

Confidence

1

Soundness

3

Presentation

3

Contribution

3

Limitations

I do not see any ethical and societal implications of the work that need to be discussed.

Reply to the authors' rebuttals

Thank you very much for your answers to my questions. Although the assumption (iii) looks too ideal, but I understand that getting rid of this condition is too challenging in a short time. Hence, I raised my score to 5.