A two-scale Complexity Measure for Deep Learning Models

Authors: massimiliano  datres
gian paolo leonardi
alessio  figalli
david  sutter
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 15:22:06

Abstract: We introduce a novel capacity measure 2sED for statistical models based on the effective dimension. The new quantity provably bounds the generalization error under mild assumptions on the model. Furthermore, simulations on standard data sets and popular model architectures show that 2sED correlates well with the training error. For Markovian models, we show how to efficiently approximate 2sED from below through a layerwise iterative approach, which allows us to tackle deep learning models with a large number of parameters. Simulation results suggest that the approximation is good for different prominent models and data sets.

Main paper: 
 introduction: 
 Deep learning models are achieving outstanding performances in solving several complex tasks such as image classification problems, object detection [19, 21] and natural language processing [8] . Over-parametrized regimes make DNNs able to extract valuable information from data [33] . Quite surprisingly DNNs typically exhibit impressive generalization capabilities after training [25, 33] without suffering of the expected overfitting. Finding appropriate complexity measures for deep learning models can help in understanding and quantifying their generalization capabilities. Hereafter we propose some essential features that, ideally, should characterize a complexity measure for parametric models: (P1) it should provide pre-training information consistent with post-training performances; (P2) its computation should be more efficient and scalable in comparison with a full training & validation process; (P3) in the case of a feedforward-type model, it should be "modular", i.e., computable in some iterative fashion 1 .Properties (P1)-(P3) are motivated by the goal of finding an efficient tool for model selection in the context of feedforward (stochastic) neural networks.Notions of complexity measures have appeared in the context of machine learning, with early studies focusing, e.g., on the complexity of decision tree models [7] and logistic regression models [10, 15, 9] . From the perspective of statistical learning theory, the Vapnik-Chervonenkis dimension, commonly called VC dimension [31] , is an established complexity measure defined in term of the largest number of points that can be shattered by a class of functions [13] . This complexity dimension has been used to establish data-independent generalization bounds for statistical models [30, 26] .Other notions of model complexity, specifically designed for deep learning models, have been more recently proposed, with the aim of quantifying the expressivity of a DNN [24, 27, 22, 14] . There is, however, a supported evidence that data-independent generalization bound are not universally effective [17, 4] . For this reason, data-dependent notions of complexity have also been introduced, like the Rademacher complexity and the Gaussian complexity. These notions of complexity evaluate the expected noise-fitting-ability of a function class over all data sets drawn according to an unknown data distribution. By means of such data-dependent complexity measures, one obtains generalization bounds that are considerably better than those involving the VC dimension [4, 26, 30] . In any case, computing or estimating the VC dimension, or the Rademacher complexity, is generally a challenging task, feasible only under strong model constraints. Some tight approximations and bounds have been obtained in some specific cases, however they are not general enough to be applicable to complex models like modern deep neural networks [32, 4, 3] . With the aim to provide more easily computable notions of complexity, other definitions have been considered based on the minimum description length (MDL) and on the notion of stochastic complexity [28, 12, 9] .Other complexity measures of more geometric flavour have been defined in terms of the Fisher information matrix (FIM) associated with the statistical model [29, 5, 2] . The geometric properties of the statistical manifold revealed by the FIM collectively contribute to our understanding of the intricate nature of the model, providing a geometric lens through which complexity can be defined, analyzed and interpreted.Our contributions. In Definition 4.1 we propose a notion of model complexity, called two-scale effective dimension (2sED), which is motivated by a metric-specific covering argument. We prove a generalization bound derived from 2sED, see Theorem 5.1, thereby theoretically substantiating its efficacy as a measure of complexity. Furthermore, we propose a modular version of the 2sED, called lower 2sED, that is specifically tailored for Markovian models. We finally present numerical simulations based on Monte Carlo approximations of 2sED and lower 2sED for various models and datasets. In particular, the experiments confirm properties (P1), (P2), and (P3) for the lower 2sED, thus promoting it as a potential effective tool for model selection. 
related works: 
 Recently, [5, 2] propose a notion of effective dimension, that is, a box-covering dimension related to the number of "Fisher boxes" of a given size that are needed to cover the parameter space. The size of such boxes represents a "scale" at which the model is analysed. Under suitable regularity assumptions on the statistical model and on the loss functional, the generalization error (i.e., the gap between the population error and the empirical error) can be controlled by an expression involving the effective dimension computed with respect to an explicit scale parameter, that depends on the number of samples defining the empirical error. On the one hand, the generalization bounds proved in [2, 1] require the logarithm of the FIM to be Lipschitz which excludes the case of over-parametrized models [16] . On the other hand, the original definition requires a global computation for the statistical model as a whole, hence it does not satisfy properties (P2) and (P3). Indeed, one of the main challenges in the computation of the effective dimension is to determine the eigenvalues of the Fisher information matrix. Note that, for high-dimensional models, even the storage of the Fisher information becomes impractical, despite sophisticated approximation methods such as K-FAC [23] . We focus to address the issues that affect the previous definition by proposing the 2sED and the lower 2sED for Markovian models. 
preliminaries: 
 Take X ⊂ R din and Y ⊂ R dout nonempty Borel sets, and denote by (X, Y ) ∈ X ×Y a pair of random vectors with (unknown) joint probability distribution p = p(x, y). Let (X 1 , Y 1 ), . . . , (X N , Y N ) be i.i.d. copies of (X, Y ). A dataset D := {(x i , y i ) : i = 1, . . . , N } is understood as a realization of the N random pairs considered before. A statistical model on the sample space X × Y is a collectionM Θ (X , Y) := {p ϑ : ϑ ∈ Θ} ,where p ϑ = p ϑ (x, y) is a joint probability distribution on X × Y for each ϑ ∈ Θ, and Θ ⊆ R d is a bounded domain called parameter space. In order to stress the functional relation between the input x and the output y, it is customary to assume p ϑ = p ϑ (y|x) p(x) of the form p ϑ (x, y) = p ϑ (y|x) p(x) where p ϑ (y|x) is a parametric conditional probability, and p(x) denotes the marginal of the unknown distribution p(x, y) on X . We will also assume that the parameter space Θ is equipped with a probability measure and we denote as E ϑ the expectation with respect to this measure.Under suitable regularity conditions,we define the Fisher information matrix as:EQUATIONwhere by a ⊗2 := a ⊗ a we mean a • a T (with the convention that a is a column vector) and l ϑ (x, y) := log p ϑ (x, y). In other words, the Fisher information matrix is the expectation of the orthogonal projector onto the direction of the gradient of the log-likelihood, scaled by the squared norm of that gradient. It is a symmetric and positive semidefinite d × d matrix. Its empirical version isF N (ϑ) = 1 N N i=1 (∇ ϑ l ϑ (X i , Y i ))) ⊗ (∇ ϑ l ϑ (X i , Y i )) , for some (X 1 , Y 1 ), . . . , (X N , Y N ) i.i.d. ∼ p ϑ . For each ϑ ∈ Θ and u, v ∈ R d , if F (ϑ)is smooth and positive-definite, then ⟨u, v⟩ ϑ := ⟨F (ϑ)u, v⟩ defines a Riemannian metric on the parameter space Θ, that from now on will be called Fisher metric (we shall adopt the same terminology also when the metric is degenerate). In general, the Fisher metric can be considered as the pull-back of a (possibly degenerate) Riemannian metric on M Θ (X , Y) [22] .We also define the pointed Fisher norm of a vector v ∈ R d as ∥v∥ A(ϑ) := ⟨A(ϑ)v, v⟩ and the corresponding balls of radius ε > 0 are referred as Fisher balls of radius ε defined as:EQUATIONSome further terminology must be recalled before discussing the generalization bounds. Given a loss function L, i.e., a continuous functionL : [0, +∞) × [0, +∞) → [0, +∞) such that L(a, b) = 0 if and only if a = b, we define the population risk R(ϑ) := E (x,y)∼p [L(p ϑ (y|x), p(y|x))],and the empirical riskR n (ϑ) := 1 n n i=1 L(p ϑ (Y i |X i ), p(Y i |X i )) ,where(X i , Y i ) i.i.d.∼ p, i = 1, . . . , n. Then, the generalization error is defined asEQUATION 
the two-scale effective dimension: 
 Here we consider a notion of complexity for a statistical model M Θ , that depends on the properties of the Fisher metric on the parameter space. Definition 4.1. Given 0 < ε < 1 and 0 ≤ ζ < 1, we define the two-scale effective dimension (or simply 2sED) asEQUATIONwhereF (ϑ) :=    d E ϑ [Tr F (ϑ)] F (ϑ) if E ϑ [Tr F (ϑ)] > 0 0 otherwiseis the normalized Fisher information matrix, so that whenever the statistical model is not trivial (i.e. not constant with respect to ϑ) the expectation of the trace of F satisfiesE ϑ [Tr F (ϑ)] = d .Note that d ζ (ε) is the convex combination of the dimension d of the parameter space with a slight variant of the effective dimension studied in [2] , which is obtained in the special case ζ = 0. Remark 4.2. The 2sED, as the original effective dimension, is inspired by the box-counting or Minkowsky dimension of the statistical manifold M Θ [5, 2] . Given a metric space (X, d) and a subset S ⊂ X, the box-counting dimension of S is defined asdim box (S) = lim ε→0 log N d (ε) | log ε| ,where N d (ε) is the minimum number of ε-size balls (with respect to the metric d) needed to cover S, also known as the ε-covering number of S. The box-counting dimension quantifies how fast N d (ε) changes as the radius ε approaches zero. Motivated by this notion of fractal dimension, we can define the effective dimension of a statistical model M ϑ at the scale ε asEQUATIONwhere N ϑ (ε) is the number of Fisher balls of size ε (defined in (2)) needed to cover Θ. The 2sED defined in ( 4) is motivated by an upper bound estimate of (5) which is computable for a given statistical model under reasonable regularity assumptions. Remark 4.3. Two parameters show up in the above definition: a micro-scale ε > 0 and an exponent ζ ∈ [0, 1) defining a meso-scale δ = ε ζ . The emergence of two scales is tied to the estimation argument for N ϑ (ε), which requires weaker assumptions compared to those in [5, 2] . The micro-scale is related to the size ε of Fisher balls that are used to cover a component of the parameter space, while the meso-scale ε ζ represents the size of the components of a partition of the parameter space, that needs to be fixed in order to localise and adapt the micro-scale covering. This covering argument plays a fundamental role in the proof of the generalization bound (Theorem 5.1). A more formal and detailed discussion of the covering argument is reported in the proof of Lemma B.2 in Appendix B. Note that when ζ = 0 we essentially obtain the effective dimension of [2] , up to a slight technical difference due to the presence of the square root of the normalized FIM F . More generally, the 2sED is a convex combination of the dimension of the parameter space and the effective dimension.  
generalization bounds: 
 It is known that the Fisher information of a statistical model degenerates asymptotically with the number of parameters [16] . This suggests that, in the case of a large (over-parametrized) model, like a deep neural network with high-dimensional layers, the corresponding Fisher information matrix F (ϑ) should have a lot of small (or possibly zero) eigenvalues. For this reason, in Theorem 5.1 below we will not require the Lipschitz regularity of log(F (ϑ)), as done in Theorem 1 of [2] , because this assumption would imply uniform positive lower bounds on the eigenvalue of F (ϑ). Without loss of generality, we directly assume F = F and Θ = [0, 1] d , as this can be enforced by a suitable scaling of the model.We list below a set of hypotheses, that will be required in the generalization bounds:(i) the map ϑ → p ϑ (y|x) is of class C 1,1 uniformly in (x, y);(ii) there exist two constants 0 < α 1 ≤ α 2 such thatα 1 ≤ p(x, y), p ϑ (x, y) ≤ α 2for all x ∈ X , y ∈ Y, ϑ ∈ Θ;(iii) the Fisher matrix field F (ϑ) is L-Lipschitz with respect to the Frobenius norm;(iv) the loss function L is bounded by 2b and is Λ-Lipschitz, for some b, Λ > 0;(v) the meso-scale parameter 1) .ζ satisfies ζ ∈ [ 2 3 ,Some comments about the previous properties are in order. First, property (i) is a mild regularity assumption on the model. Property (ii) prevents degeneration of both probability densities p(x, y) and p ϑ (x, y). The L-Lipschitz property (iii) is crucial to compare the pointed Fisher norm computed in different ϑ ∈ Θ and it is satisfied for instance by models of class C 1,1 (but possibly also by more general models). Lipschitz regularity and boundedness of the loss function L (property (iv)) are standard assumptions (see, e.g., [20] ). Finally, property (v) is structurally needed in the proof of the generalization bound (Theorem 5.1) and it is strictly related to the covering argument discussed Lemma B.2 in Appendix B. Theorem 5.1. Let us assume (i)-(v). Then, there exist explicit constants2 C, H, K, n 0 > 0 such that for any γ ∈ (0, 1], n ≥ n 0 , andε n = log n γn 3/8, we obtainEQUATION)The proof of Theorem 5.1 is given in Appendix B. Remark 5.2. Under the assumption that the eigenvalues of F are smaller than µ for some fixed µ > 0, the above result implies the existence of γ 0 > 0 such that, for 0 < γ < γ 0 , the right-hand side of ( 6) vanishes as n → ∞. The upper bound γ 0 is explicit and depends only on the dimension d and on the properties of the model, see (34). By choosing γ as above, the right-hand side of ( 6) gives an explicit upper bound of the generalization error, that is non-vacuous also for finite n (even though this can be granted only in the under-parametrized regime, i.e. for n large enough). 
the effective dimension of a markovian model: 
 Markovian models are a family of probabilistic models characterized by a sequential, feed-forwardtype structure, see the Markovian property stated below.Let us consider an integer L ≥ 2, a probability space (Ω, F, P), and a random vector X j : Ω → X j for j = 0, . . . , L. Given a parameter space Θ = Θ 1 × • • • × Θ L , a parametric statistical model M Θ (X 0 , . . . , X L ) satisfies the Markovian property if and only if for each p ϑ (x 0 , . . . , x L ) ∈ M Θ (X 0 , . . . , X L ) and for each ϑ = (ϑ 1 , . . . , ϑEQUATIONwhere ϑ 1 , . . . , ϑ L are the parameters associated to the model's distribution of X 1 , . . . , X L respectively. Many well-known and commonly used neural network architectures, such as feed-forward neural networks, can be interpreted as Markovian models with concentrated, Dirac-type probability distributions. A specific evaluation of the effective dimension of these models seems therefore particularly interesting. Exploiting the Markovian property, for j = 1, . . . , L we define:F (ϑ j |x j-1 ) := ˆXj (∇ ϑj l ϑj (x j |x j-1 )) ⊗2 p ϑj (dx j |x j-1 )where l ϑj (x j |x j-1 ) := log p ϑj (x j |x j-1 ) andF j = F j (ϑ 1 , . . . , ϑ j ) := E x0 E x1|x0 • • • E xj-1|xj-2 [F (ϑ j |x j-1 )],where E x0 and E xj |xj-1 denote the (conditional) expectations with respect to p(x 0 ) and p ϑj (x j |x j-1 ), respectively. Clearly F j is a symmetric and positive semidefinite d j × d j matrix (where d j is the dimension of Θ j ) and represents the j-th block of the Fisher information matrixEQUATION)We recall that the two-scale effective dimension (2sED) isEQUATIONwhere det j = det j (ϑ 1 , . . . , ϑ j ) := detI j + ε -1 F 1 2j and I j denotes the d j × d j identity matrix. Since F j depends on all the parameters of the previous blocks, it is not possible to directly factorize the multiple integral in (9) . Nevertheless, one obtains a more easily computable lower bound of d ζ (ε), called lower 2sED, by a single application of Jensen's inequality as hereafter described. Let d m ζ (ε) be the 2sED associated with the composition of the first m layers, m ≥ 2. Then:d m ζ (ε) -d m-1 ζ (ε) = 1 -ζ | log ε| log Θm Θm det m dϑ m dΦ m ≥ 1 -ζ | log ε| Θm Θm log det m dϑ m dΦ m ,where we have setΘm := Θ 1 × • • • × Θ m-1 anddΦ m = Φ m (dϑ 1 , . . . , dϑ m-1 ) := 1 m-1 j=1 |Θ j | m-1 j=1 det j dϑ 1 • • • dϑ m-1 .Now, a lower bound of d m ζ (ε) can be iteratively defined for m = 1, . . . , L as follows:EQUATION) EQUATION 
experiments: 
 In this section, we present experimental evidence that the behavior of the loss in the training of given parametric models is related both with 2sED (4) and the lower 2sED (10) . We compute d ζ and d ζ of different feed-forward neural networks (FNN) such as convolutional neural networks (CNN) and multi-layer perceptrons (MLP). The experiments rely on the computation of the exact eigenvalues via the numpy.linalg.eig function. As discussed in Section 8, an interesting research direction (which goes beyond the goal of this paper) would be to investigate strategies to efficiently compute the (lower) 2sED via a suitable approximation of the spectrum of F . The feed-forward neural network choice is justified by their architecture characterized by a Markovian dependency structure. Indeed, the flow of information in FNN is unidirectional from input to output, making them representable with a finite acyclic graph. We evaluate d ζ and d ζ on real-world datasets, including Covertype dataset [6] , MNIST dataset [11] , and CIFAR10 [18] . All simulations are conducted on a 12th Gen Intel(R) Core(TM) i9-12900KF equipped by a NVIDIA GeForce RTX 4090. In the worst-case scenario, the experiments required a maximum RAM memory consumption of 17 GB.Description of the models. To simplify notation and enhance readability, we denote with "MLP N 0 -N 1 -. . . -N n " a MLP with n linear layers, each with a width of N i for i = 0, . . . , N , followed by ReLU activation functions on all layers except the final layer n. If we denote with W i ∈ R Ni×Ni-1 the parameters of the i-th layer, we can describe "MLP N 0 -N 1 -. . . -N n " through n blocks of operations defined asO i (•) = ReLU (W i •) for i = 1, . . . , n. Similarly, "CNN N 0 -N 1 -. . . -N n1 |L 1 -. . . -L n2 "refers to a convolutional neural network with n 1 convolutional blocks each one of kernel size N i for i = 1, . . . , N 1 followed by a flattening layer and n 2 MLP blocks of width L i for i = 1, . . . , n 2 . Within each convolutional block, the operations of convolution, batch normalization, ReLU activation, and max pooling are performed sequentially. Moreover, the flattening operation is executed by applying a common convolutional kernel to all the channels of the last convolutional layer. Hence, given the input A ∈ R Nc×k×k the flattening operation F lat K : R Nc×k×k → R Nc is defined as follows:[F lat K (A)] l := A l:: ⋆ K = k i=1 k j=1A l,i,j K i,j , for l = 1, . . . , N c where A l:: denotes the R k×k obtained by fixing the first dimension at index l and K is a k × k convolutional kernel which is a parametric matrix in applications. This approach effectively reduce the number of parameters allowing us to compute the effective dimension in reasonable time.Introducing stochasticity. In applications, the core architectures of many deep learning models is deterministic, and the stochasticity is usually introduced in the training pipeline rather than in the model itself. This makes deep learning models, like MLPs and CNNs, incompatible with our setting. Therefore, we approximate deterministic feed-forward neural networks with stochastic variants, where the output of each block is Gaussian with mean the current block deterministic output and a small fixed variance σ 2 . In other words, if N is the number of blocks, the output of the i-th block O σ i is given byO σ i = O i + ν ∼ N (O i , σ 2 I), where O i is the deterministic output of the i-th block, ν ∼ N (0, σ 2 ). For all the subsequent experiments, we will specifically focus on the computation of 2sED and lower-2sED for ζ = 0 and consider the empirical Fisher information matrix FN . Note we compare different network topologies while keeping more or less the same number of parameters. Hence, the informative part of the definition of the (lower) 2sED automatically becomes the log ratio.Sharpness of lower 2sED. To empirically validate the lower 2sED, we compute d 0 and d 0 for different stochastic perturbations of feed-forward neural networks, also varying the covering radius ε. We keep constant both the 100 samples used to estimate FN and the 100 vectors of parameters employed for estimating the integrals appearing in ( 4) and (10) . The results are visualized in Figure 1a and Figure 1b . Notably, the lower bound is sharp in both the MLP and the CNN case suggesting the conclusions regarding model complexity obtained using d ζ (ε) are equivalent to those obtained when considering d ζ (ε) for all covering radius ε. It is also worth noticing that lower 2sED exhibits a sequential form, reducing the computational demands when investigating how the model's complexity changes by modifying only its final components.Dependence on σ 2 . We study now the impact of variance σ 2 on 2sED and lower 2sED. We vary the values of σ 2 while computing the d ζ and d ζ for different models on Covertype and MNIST dataset. Figure 4 and Figure 5 show that the impact of σ 2 on d ζ and d ζ is negligible.Stability of Monte Carlo estimates. Monte Carlo integration is crucial in the estimation of both the Fisher information matrix and the integral within Θ appearing in (4). To ensure the reliability of our results, we conduct a robustness analysis of the lower 2sED with respect to variations in the number of samples and parameterizations employed for integrals estimation. Figures 2a, 2b, 2c , 2d confirm the stability of the lower 2sED plots with respect to the number of points used in the Monte Carlo approximation. The 2sED is computed for three different models on Covertype, MNIST and Cifar10 dataset. Lower 2sED and training curves. Finally, we test the relationship between the lower 2sED and the loss minimization. We expect that models with higher values of the lower 2sED can achieve higher accuracy after training. Furthermore, it is crucial to gain a deeper understanding of the role played by the covering radius, denoted as ε, in the 2sED definition. We compute the lower 2sED for three different models with similar dimension on CIFAR10 and Covertype dataset. The dimension of these models is reported in Table 1 . MLP 54-10-2-10-25-7 is characterized by a bottleneck structure in the middle of its architecture. A loss of information due to this bottleneck is therefore expected as data are mapped into a significantly lower dimensional space. Consequently, the expressiveness of this model is expected to be lower compared to the other two models, even though it is bigger than MLP 54-16-7 in terms of number of parameters. In Figure 3a , this expected behaviour is effectively captured by the lower 2sE, as indicated by the lower position of the red curve in comparison to the other two curves.Furthermore, the position of the curves change varying the covering radius ε. The MLP 54-16-7 model exhibits greater expressiveness within this range of ϵ. Conversely, for smaller values of ϵ, MLP 54-13-11-9-7 appears to be more expressive. This behaviour is empirically validated by the experiments. In Figure 3c and Figure 3e we observe the training loss curve for the three models when trained with only 10000 and 100000 data respectively. Note that MLP 54-16-7 is the one achieving the lower training loss using 10000 data, while MLP 54-13-11-9-7 is consistently better with 100000 data. The empirical correlation between training losses and lower 2sED underscores the capacity of 2sED as a reliable measure for describing the training capabilities of neural networks. We conducted additional experiments, manipulating the number of training data points. The outcomes align consistently with the previously described results. This further confirms its effectiveness as a capacity metric.Other experiments. Other experiments in this direction are performed on the CIFAR10 and MNIST dataset and the results are reported in Figures 3b, 3d , 3f, 6, 7, 8, 9 varying batch sizes providing additional empirical evidence that supports our findings. 
conclusions: 
 We propose a novel complexity measure called 2sED strongly related with the geometric properties of the statistical manifold. This notion allows to bound the generalization error under mild assumptions on the model (see Theorem 5.1) to theoretically justify the 2sED as a complexity measure. At the same time, a modular version of the 2sED, called lower 2sED, specifically tailored for Markovian models, is introduced as a tight lower bound for the 2sED. The lower 2sED can be computed sequentially layer-by-layer, which drastically reduces the computational effort and the storage consumption compared to the original 2sED. Consequently, the lower 2sED can be computed for more complex (deeper) models than those considered in previous works.Finally, numerical simulations based on Monte Carlo approximation of the 2sED and the lower 2sED for various models and datasets are presented. The experiments remarkably confirm desirable properties (P1), (P2), and (P3) for the lower 2sED. These experiments show that the lower 2sED represents a tight approximation of the 2sED. The resulting relation between the scale parameter, the number of training data and the training error suggests that the lower 2sED is a reliable complexity measure that can be used as a tool for training-free model selection. Indeed, it can be accurately estimated for general models, distinguishing it from other complexity measures that are often challenging to compute directly and may only be estimated, often assuming a precise model structure.Limitations and Future perspectives. We study a new notion of complexity for deep learning models and we show empirical evidence that the lower 2sED effectively captures the training behaviour. However, the computation of the lower 2sED for large-scale machine learning models is complicated by the dimension of the FIM, whose eigenvalue problem is computationally intractable. In light of the theoretical nature of this work, the implementation of the 2sED has not been optimized. Exploring code optimization would be an interesting direction for future research and necessary to study the lower 2sED of bigger models.Therefore, an interesting research direction is to develop techniques for further reducing the computational cost of the lower 2sED. The main goal is to approximate the eigenvalue distribution of the FIM, rather than computing exactly each eigenvalue. This would consistently improve the effectiveness of the lower 2sED as a model selection criterion, e.g., in the step-by-step design of deep feedforward neural networks. Another avenue for future research is to design variants of 2sED and lower 2sED specifically adapted to very large neural networks, which characterize modern deep learning architectures. This not only would bring out a deeper understanding of the complexity and the generalization capabilities of huge machine learning models, but it could also provide more efficient approximations of the (lower) 2sED for them. 
 
 Appendix: In this section, we prove the following result.Proposition A.1. Let r denote the maximum rank of the Fisher matrix F (ϑ) and let µ > 0 be an upper bound for all the eigenvalues of F (ϑ), for all ϑ ∈ Θ. Then, for all ζ ∈ [0, 1) and 0 < ε < 1 we haved ζ (ε) ≤ ζd + r 1 -ζ + log(1 + µ 1/2 ) | log ε| (11)and, moreover,lim ε→0 d ζ (ε) = ζd + (1 -ζ)r .Proof. Let us fix ζ, ε as above. Denoting by r ϑ the rank of F (ϑ), we have:d ζ (ε) = ζd + log ffl Θ det(Id d + ε ζ-1 F 1/2 (ϑ)) dϑ | log ε| = ζd + log ffl Θ r ϑ i=1 (1 + ε ζ-1 λ 1/2 i (ϑ)) dϑ | log ε| ≤ ζd + log ffl Θ ε (ζ-1)r ϑ r ϑ i=1 (1 + λ 1/2 i (ϑ)) dϑ | log ε| ≤ ζd + log ε (ζ-1)r | log ε| + log ffl Θ r ϑ i=1 (1 + λ 1/2 i (ϑ)) dϑ | log ε| ,where λ i (ϑ) are the nonzero eigenvalues of F (ϑ). Notice that log fflΘ r ϑ i=1 (1 + λ 1/2 i (ϑ)) dϑ is finite. Indeed, 0 ≤ λ i (ϑ) ≤ µ by assumption. Then it holds 1 ≤ r ϑ i=1 (1 + λ 1/2 i (ϑ)) ≤ (1 + µ 1/2 ) r .This implies that1 ≤ Θ r ϑ i=1 (1 + λ 1/2 i (ϑ)) ≤ (1 + µ 1/2 )r and therefore (11) . We thus conclude thatEQUATION)To see the other inequality, let us consider A := {ϑ ∈ Θ : r ϑ = r}. Notice that A ⊂ Θ and hence |A| < ∞. Also, by continuity of the Fisher matrix, the set A has positive measure. Then, we haved ζ (ε) = ζd + log ffl Θ det(Id d + ε ζ-1 F 1 2 (ϑ)) dϑ | log ε| ≥ ζd + log ffl A det(Id d + ε ζ-1 F 1 2 (ϑ)) dϑ | log ε| = ζd + log ffl A det(Id d ϑ + ε ζ-1 F 1 2 0 (ϑ)) dϑ | log ε| ,where d ϑ is the number of non-zero eigenvalues of F (ϑ) and F0 (ϑ) is the diagonal d ϑ ×d ϑ containing only the d ϑ non-zero eigenvalues of F (ϑ) for all ϑ ∈ Θ. This yieldsd ζ (ε) ≥ ζd + log ffl A det(Id d ) + det(ε ζ-1 F 1 2 0 (ϑ)) dϑ | log ε| = ζd + log |A| | log ε| + log ffl A r i=1 ε ζ-1 λ 1 2 i (ϑ) dϑ | log ε| = ζd + log |A| | log ε| + log ffl A r i=1 ε ζ-1 λ 1 2 i (ϑ) dϑ | log ε| = ζd + r(ζ -1) log ε | log ε| + log ffl A λ 1 2 i (ϑ) dϑ | log ε| = ζd + r(1 -ζ) + log ffl A λ 1 2 i (ϑ) dϑ | log ε| .Notice now that since λ i (ϑ) ̸ = 0 for all ϑ ∈ Θ, it holds that log ffl A λ1 2i (ϑ) dϑ < ∞ and so:EQUATIONCombining ( 12) and ( 13), we concludelim ε→0 d ζ (ε) = ζd + r(1 -ζ) .We conveniently introduce additional terminology and a few of new definitions concerning d × d symmetric matrices and matrix fields. We denote by S d + (R) the set of real d × d symmetric and positive semidefinite matrices.A ∈ S d + (R) and x ∈ R d , |⟨Ax, x⟩| ≤ ∥A∥|x| 2 ,where ∥ • ∥ denotes the Frobenius norm (this is because the Frobenius norm bounds from above the operator norm). Let β > 0, then for A ∈ S d + (R) we define A β by replacing its eigenvalues smaller than β with β. In practice, we consider a spectral basis {u j } j=1,...d with its corresponding sequence of eigenvalues {λ j } j=1,...,d , then defineEQUATIONNote that this definition does not depend on the choice of the basis because the matrix A only depends on its eigenvalues and eigenspaces. Given a matrix fieldA : Θ → S d + (R), we define the pointed A norm of a (tangent) vector v ∈ R d at ϑ ∈ Θ as ∥v∥ A(ϑ) := ⟨A(ϑ)v, v⟩ . Let A ∈ S d + (R), we choose a spectral basis U = {u i } i=1..d for A and, for any v ∈ R d , we setEQUATIONwhere λ i is the eigenvalue corresponding to the eigenvector u i .Lemma B.1. Let A : Θ → S d + (R) be a L-Lipschitz matrix field. Then for all β > 0, v ∈ R d , andEQUATIONwhereEQUATIONProof. We first note thatEQUATION)To see this we write v in spectral coordinates and computeEQUATIONfollows. Now by (18) we obtain the conclusion:∥v∥ 2 A β (ϑ2) ≤ ⟨A β (ϑ 1 )v, v⟩ + |⟨(A β (ϑ 1 ) -A β (ϑ 2 ))v, v⟩| ≤ ⟨A β (ϑ 1 )v, v⟩ + β|v| 2 + |⟨A(ϑ 1 )v, v⟩ -⟨A(ϑ 2 )v, v⟩| + β|v| 2 ≤ ⟨A β (ϑ 1 )v, v⟩ + (2 + Lβ -1 |ϑ 1 -ϑ 2 |)β|v| 2 ≤ (3 + Lβ -1 |ϑ 1 -ϑ 2 |)∥v∥ 2 A β (ϑ1) ,where in the last inequality we have used the fact that Proof. The fact that any L-Lipschitz mapping from a subset of R d into R m admits an L-Lipschitz extension to the whole R d is classically known as Kirszbraun's Theorem. Consider now a partition Q of Θ made by closed cubes with mutually disjoint interior and side δ = δ(Q) = ε ζ , and let Q be one of these cubes. SetEQUATIONEQUATIONfix a generic ϑ Q ∈ Q and a spectral basisU Q for F (ϑ Q ). Then, the β-Fisher box centered in ϑ Q of radius ε > 0 is defined as Box β,ε (ϑ Q ) := ϑ ∈ Θ : [ϑ -ϑ Q ] F β (ϑ Q ),U Q < ε .Let S Q be the Euclidean ball circumscribed to Q. Consider a partition of R d by means of translated copies of Box β,ε (ϑ Q ), then the minimum number of such boxes that have a nonempty intersection with Q is bounded from above by the number k = k(Q, β, ε) of boxes that have a nonempty intersection with S Q . The volume of each copy of Box β,ε (ϑ Q ) is given by|Box β,ε (ϑ Q )| = d i=1 2ε λ i,β (ϑ Q ) .At the same time, the union of the covering boxes is contained inEQUATIONhence its volume is bounded from above by|B ρ | = α d ρ d , where α d = π d/2 / Γ(d/2 + 1)is the volume of an Euclidean ball of radius 1 in R d , and Γ(•) is Euler's Gamma function. Therefore we can estimate k from above by the ratio between the upper bound on the volume of the union of the boxes and the volume of a single box. We obtainEQUATIONwhere we have used the special rounding function Let us notice that for all ϑ ∈ S Q , the translated copy of Box β,ε (ϑ Q ) centered in ϑ is contained in the corresponding translated copy of B β,ε ′ (ϑ Q ) centered in ϑ, where:⌈x⌉ = min{k ∈ N : k ≥ max(x,B β,ε ′ (ϑ Q ) := {ξ ∈ Θ : ∥ξ -ϑ Q ∥ F β (ϑ Q ) < ε ′ } and ε ′ = √ dε. Indeed, let ϑ be the center of the translated copy Box of Box β,ε (ϑ Q ), then for each ξ ∈ S Q ∩ Box one has by definition [ξ -ϑ] F β (ϑ Q ),U Q < ε. Consequently we have ∥ξ -ϑ∥ F β (ϑ Q ) = d i=1 λ β,i (ϑ Q )|⟨ξ -ϑ, u i (ϑ Q )⟩| 2 ≤ √ d max i=1,...,d λ β,i (ϑ Q )|⟨ξ -ϑ, u i (ϑ Q )⟩| ≤ √ d[ξ -ϑ] F β (ϑ Q ),U Q ≤ ε ′Now we notice that for all ϑ ∈ S Q the translated copy ofB β,ε ′ (ϑ Q ) centered in ϑ is contained in B β,ε ′′ (ϑ), whereEQUATIONIndeed, let ϑ be the center of the translated copy B of B β,ε (ϑ Q ), then for each ξ ∈ S Q ∩ B one has by definition ∥ξ -ϑ∥ F β (ϑ Q ) < ε ′ . Consequently, by Lemma B.1 and by the fact that both ϑ and ϑ Q are contained in B R , one gets∥ξ -ϑ∥ F β (ϑ) ≤ ∥ξ -ϑ∥ F β (ϑ Q ) 3 + ω β (|ϑ -ϑ Q |) ≤ ε ′ 3 + ω β (|ϑ -ϑ Q |) ≤ ε d(3 + ω β (5 √ dδ)) ≤ ε d(3 + 5 √ dL) .where in the last step we have usedEQUATIONwith the last inequality following from the assumption ζ ≥ 2/3.The previous estimate shows that there exists a covering of Q by means of at most k Q balls of the form B j = B β,ε ′′ (ϑ j ), with j = 1, . . . , k Q . Therefore, by combining ( 19), ( 21) and ( 22), we getk Q ≤ k ≤ c d d i=1 δ 2 λ i (ϑ Q ) ε 2 ≤ c d d i=1 δ 2 d(3 + 5 √ dL)λ i (ϑ Q )/(ε ′′ ) 2 ≤ c d (d(3 + 5 √ dL)) d 2 |Q| d i=1 (ε ′′ ) -1 λ i (ϑ Q ) + δ -1 ≤ c d (d(3 + 5 √ dL)) d 2 ε -ζd |Q| d i=1 ε ζ ε ′′ λ i (ϑ Q ) + 1 ≤ c d (d(3 + 5 √ dL)) d 2 ε ′′ d(3 + 5 √ dL) -ζd |Q| d i=1 (ε ′′ ) ζ-1 (d(3 + 5 √ dL)) ζ λ i (ϑ Q ) + 1 ≤ c d (d(3 + 5 √ dL)) d 2 +ζd (ε ′′ ) -ζd |Q| d i=1 (ε ′′ ) ζ-1 λ i (ϑ Q ) + 1 ≤ c d (d(3 + 5 √ dL)) 3 2 d (ε ′′ ) -ζd |Q| d i=1 (ε ′′ ) ζ-1 λ i (ϑ Q ) + 1 ,where we have used that ⌈xy⌉ ≤ xy + 1 for all x, y ≥ 0. Therefore, by conveniently writing ε instead of ε ′′ , we obtain that the number k Q of β-Fisher balls of size ε that are needed to cover Q satisfiesEQUATION, where nowEQUATIONandC d = c d d 3d/2 (3 + 5 √ dL) 3d/2. Finally, if we denote by k(ε) the cardinality of the least number of β-Fisher balls of size ε that are needed to cover Θ, by summing over Q and choosing ϑ Q as a minimum point for det(I + ε ζ-1 F (ϑ)1 2 ) when ϑ ∈ Q, we obtain k(ε) ≤ C d ε -ζd ˆΘ det I + ε ζ-1 F (ϑ) 1 2 dϑ = C d ε -d ζ (ε) . Since ∥ • ∥ F β (ϑ) ≥ ∥ • ∥ F (ϑ)for all β > 0 and ϑ ∈ Θ, we finally obtain that k(ε) is also an upper bound for the covering number associated with Fisher balls, and this concludes the proof.The following result exploits the link between the generalization bound and the covering bound proved in Lemma B.2.Lemma B.3. Under the assumption of Theorem 5.1, there exist ε 0 , C, K > 0 such that for all ε ∈ (0, ε 0 ) we haveEQUATIONwhere k(ε) is a bound on the cardinality of a covering by Fisher balls of radius ε.Proof. As a first step, we need to "discretize" the estimate of the left-hand side of ( 25) at the microscale ε, using the previous covering lemma (Lemma B.2). By inspecting the proof of Lemma B.2, we notice that we can consider β-Fisher balls instead of Fisher balls for the covering, where β is defined in (24) . We also recall that the meso-scale δ is now given byEQUATIONNow we estimate each term in the right-hand side of ( 26) under the assumption |ϑ 1 -ϑ 2 | < 5 √ dδ. We set ϑ(t) = tϑ 1 + (1 -t)ϑ 2 for t ∈ [0, 1], and we estimate the first term:|R(ϑ 1 ) -R(ϑ 2 )| ≤ ˆX ×Y |L(p ϑ1 (y|x)) -L(p ϑ2 (y|x))| p(dx, dy) ≤ ˆX ×Y L(p ϑ(0) (y|x)) -L(p ϑ(1) (y|x)) p(dx, dy) = ˆX ×Y ˆ1 0 ∂ 1 L(p ϑ(t) (y|x), p(y|x)) ∇ ϑ p ϑ(t) (y|x), ϑ 2 -ϑ 1 dt p(dx, dy) ≤ ˆ1 0 ˆX ×Y ∂ 1 L(p ϑ(t) (y|x), p(y|x)) ∇ ϑ p ϑ(t) (y|x), ϑ 2 -ϑ 1 p(dx, dy)dt ≤ Λ ˆ1 0 ˆX ×Y ∇ ϑ p ϑ(t) (x, y), ϑ 2 -ϑ 1 p(dx, dy) dt = Λ ˆ1 0 ˆX ×Y ∇ ϑ log p ϑ(t) (x, y), ϑ 2 -ϑ 1 p ϑ(t) (x, y) p(dx, dy) dt = Λ ˆ1 0 ˆX ×Y ∇ ϑ log p ϑ(t) (x, y), ϑ 2 -ϑ 1 p(x, y) p ϑ(t) (dx, dy) dt ,where we have used the fundamental theorem of calculus, Fubini's theorem, the Λ-Lipschitzianity of L, and the fact that ∇ ϑ log p ϑ (y|x) = ∇ ϑ log p ϑ (x, y). Then, by Cauchy-Schwarz inequality, we obtain|R(ϑ 1 ) -R(ϑ 2 )| ≤ Λ ˆ1 0 E p ϑ(t) [p 2 (x, y)] 1/2 • F (ϑ(t))(ϑ 2 -ϑ 1 ), ϑ 2 -ϑ 1 1/2 dt ≤ Λ ˆ1 0 E p ϑ(t) [p 2 (x, y)] 1/2 • F β (ϑ(t))(ϑ 2 -ϑ 1 ), ϑ 2 -ϑ 1 1/2 dt ≤ ΛC 1 ˆ1 0 F β (ϑ(t))(ϑ 2 -ϑ 1 ), ϑ 2 -ϑ 1 1/2 dt ,for some constant C 1 > 0 depending on α 1 , α 2 , thanks to hypothesis (ii). Now, Lemma B.1 implies thatEQUATIONBy ( 27) and ( 23) we conclude thatEQUATIONwhere C 2 is a constant depending only on Λ, C 1 and the dimension d. Now, by a similar computation, we estimate the second term in the r.h.s. of ( 26):EQUATIONLet us setEQUATIONT := sup p ϑ (x, y) p(x, y) |∇ ϑ log p ϑ (x, y)| 2 ,where the supremum is computed w.r.t (x, y) ∈ X × Y and ϑ ∈ Θ. By assumptions (i) and (ii) we obtainT ≤ B sup |∇ ϑ log p ϑ (x, y)| 2 < ∞ , where B = α 2 /α 1 . Thus we also get 0 ≤ Z i (t) ≤ T |ϑ 2 -ϑ 1 | 2 . The expectation of Z i (t) is Z i (t) = E (x,y)∼p [Z i (t)] = ˆ ∇ log p ϑ(t) (x, y), ϑ 2 -ϑ 1 2 p ϑ(t) (x, y) p(x, y) p(dx, dy) = ˆ ∇ log p ϑ(t) (x, y), ϑ 2 -ϑ 1 2 p ϑ(t) (dx, dy) = F (ϑ(t))(ϑ 2 -ϑ 1 ), ϑ 2 -ϑ 1hence also = k(ε) ≤ C d ε -d ζ (ε) β-Fisher balls B 1 , .. . , B k of size ε. Let now η = Cε for some C > 0 to be chosen later, and evaluateIP sup ϑ∈Θ |S n (ϑ)| ≥ η ≤ IP    k j=1 sup ϑ∈Bj |S n (ϑ)| ≥ η    ≤ k j=1 IP sup ϑ∈Bj |S n (ϑ)| ≥ η .Now for all j = 1, . . . , k we bound the probability of an event involving the computation of the supremum of |S n (ϑ)| over B j with another one involving only the pointwise evaluation of S n at the center ϑ j of B j . Indeed by ( 28) and ( 29), and with ϑ, ϑ j respectively replacing ϑ 2 , ϑ 1 , we deduceIP sup ϑ∈Bj |S n (ϑ)| ≥ η ≤ IP |S n (ϑ j )| + sup ϑ∈Bj |S n (ϑ) -S n (ϑ j )| ≥ η ≤ IP    |S n (ϑ j )| + sup ϑ∈Bj   C 2 ∥ϑ -ϑ j ∥ F β (ϑj ) + α 2 ˆ1 0 1 n n i=1 Z i (t) 1/2 dt   ≥ η    ≤ IP |S n (ϑ j )| ≥ η 2 + IP ∃ t ∈ [0, 1] : 1 n n i=1 Z i (t) ≥ η 2 16 α 2 2 ,where in the last inequality we have used ∥ϑ -ϑ j ∥ F β (ϑj ) < ε = η C and required C ≥ 4C 2 . Owing to Lemma B.4 and (v), we getEQUATIONandEQUATIONBy (31) we findEQUATIONwhereEQUATION3 2 2 9-2ζ α 4 2 T 2 d and where the last inequality follows fromEQUATIONwhich can be enforced by a suitable choice of the constant C, as explained hereafter. Indeed, using Lemma B.1 and ( 23) we obtain∥ϑ -ϑ j ∥ 2 F β (ϑ(t)) ≤ (3 + ω β (t|ϑ -ϑ j |))∥ϑ -ϑ j ∥ 2 F β (ϑj ) ≤ 3 + ω β (t|ϑ -ϑ j |) ε 2 ≤ (3 + 5L √ d)ε 2 ≤ 3 + 5L √ d C 2 η 2 .Therefore, if we choose C such that(3 + 5L √ d) < C 2 32α 2 2 ,we obtain (33), as wanted. The proof of ( 32) is now complete.Finally, by ( 30) and (32) , and observing that the second exponential is the leading term, we getIP sup ϑ∈Θ |S n (ϑ)| ≥ η ≤ k i=1 IP sup ϑ∈Bi |S n (ϑ)| ≥ η ≤ 2 k(ε) exp - nη 2 2b 2 + exp -C 4 nη 4-2ζ ≤ 4 k(ε) exp -C 5 nη 8/3 ,where C 5 = min(C 4 , (2b 2 ) -1 ) and owing to 4 -2ζ < 3, which follows from assumption (v). In conclusion we obtain (25) Hence, the infinitesimality of the generalization bound as n → ∞ follows from 3 d/8 -K/γ < 0, as wanted.We recall Hoeffding's estimate, which is used in the proof of Lemma B. The appendix contains a comprehensive collection of figures and tables that complement and enhance the understanding of the main content presented in this document. These figures provide visual representations of the results related to the experiments section discussed in the main part of the paper.The results in Figure 4 and Figure 5 show that the impact of σ 2 on d ζ and d ζ is negligible. To avoid discrepancies, we fix the data and the parameters used to estimate both d ζ and d ζ via Monte Carlo integration. The meaningfulness of 2sED and lower 2sED for deterministic deep learning models is then enforced by taking the limit as σ 2 → 0. Here we are referring to the typical structure of a feedforward-type model, which is a composition of parametric layer maps.the constants can be computed/estimated in terms of the assumptions. 


Decision: This paper studies complexity measures that can inform model selection and generalization bounds. It draws ideas from notions of dimensionality of data and proposes a two-scale effective dimension to characterize model complexity, leading to a generalization bound under suitable assumptions. Since computing this quantity is in general hard, the paper furthermore proposes a modular approach (which is in fact part of their desiderata of complexity measures in the case of compositional models) to estimate this quantity for Markovian models. The paper is also accompanied by experiments on feed-forward neural networks. 

All reviewers agree in that the proposed results are interesting, the clarify of presentations is good, and that this work would be a valuable addition to the literature on learning theory - and I agree.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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: questions: How does the method fit into the existing literature on understanding the expressivity of neural networks?
limitations: limitations: I do not see any ethical and societal implications of the work that need to be discussed.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: The authors do an excellent job at stating their mathematical assumptions and computational bottlenecks. This paper honestly addresses its limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: -	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: 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?
limitations: limitations: Not all limitations are mentioned (e.g. experiments only show correlation of 2sED with the training loss and not the validation/ test loss).
paper_summary: paper_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.
strength_weakness: strength_weakness: + 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: 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$).
limitations: 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.

Comments: title: Reply to the authors' rebuttals
comment: 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.
I acknowledge the author's response. I am inclined to keep my score.
Thank you.
I thank the reviewers for their detailed response which has helped me be assured in my assessment. I believe this paper would be a good addition to the literature and stand by my rating of acceptance.
Thank you very much
Thanks, I see my mistake with the empirical FIM comment. I will raise the score.