A two-scale Complexity Measure for Deep Learning Models
Authors: Massimiliano Datres
Gian Paolo Leonardi
Alessio Figalli
David Sutter
Venue: NeurIPS 2024 poster (2024)
Keywords: Statistical learning theory
complexity measures
covering number estimates
Fisher metric
Markovian models.
Primary area: learning_theory

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.

A two-scale Complexity Measure for Deep Learning Models
Massimiliano !22 Gian Paolo Leonardi Alessio Figalli", David Sufter
1 Department of Mathematics, University of Trento, Trento DSH, Bruno Kessler Fondation, Trento Department of Mathematics, ETH. Zurich
IBM Quantum, IBM Research Europe, Zurich
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 layerwise iterative approach, which allows tackle deep learning models with large number of parameters. Simulation results suggest that the approximation is good for different prominent models and data sets.
Introduction
Deep learning models achieving outstanding performances in solving several complex tasks such as image classification problems, object detection [19] 21] and natural language processing g over-parametrized regimes make DNNs able 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 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 full training & validation process;
(P3) in the case of feedforward-type model, it should be "modular". i.e., computable in some iterative fashion!
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 77] and logistic regression models [T0] 15 9. From the perspective of statistical learning theory, the Hapnik-Chervoneer
dimension, commonly called VC dimension BT. an established complexity measure defined in term of the largest number of points that can be shattered by class of functions [3]. This complexity dimension has been used
'Here referring the typical structure of feedforward-type model, which is composition of parametric layer maps.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to establish intepedddeen 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- saeee-iitin-abiiltt of function class over all data sets drawn according to 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 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 the notion of stochastic complexity 28 12 99.
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 be defined, analyzed and interpreted.
Our contributions. In Definition 4.1 we propose notion of model complexity, called two-scale effective dimension (2sED), which motivated by a metrie-specific covering argument. We prove 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 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.
2 Related works
propose 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 "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 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 1 require the logarithm of the FIM to be Lipschitz which excludes the case of over-parametrized models [6]. On the other hand, the original definition requires 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- -igensimensi models, even the storage of the Fisher information becomes impractical, despite sophisticated approximation methods such as K-FAC (23). We focus address
Recently, 5
the issues that affect the previous definition by proposing the 2sED and the lower 2sED for Markovian models.
3 Preliminaries
Take X' C TR and ) C Reou nonempty Borel sets, and denote by (X, Y) E X'xy pair of random vectors with (unknown) joint probability distribution p = p(x, y). Let (X1, Vi).... (XN, Yx) be i...d. copies of (X, Y). A dataset D == {(I,, Vi) = ...... N) is understood as realization of the N random pairs considered before. statistical model on the sample space X' x y is collection
M, = {ps 0 E E
where pa = po y) a joint probability distribution on X' y for each 1 E θ, and θ S TRd is bounded domain called parameter space. In order to stress the functional relation between the input

---

and the output y, it is customary to assume pa = ppl p(z) of the form po(x, y) = (v())z) p(œ)
where Po (g)y) ()) is parametric conditional probability, and p(z) denotes the marginal of the unknown distribution p(2; v) on X. We will also assume that the parameter space @ is equipped with probability measure and we denote as Ey the expectation with respect this measure.
Under suitable regularity conditions, we define the Fisher information matrix as:
F()): ((x,))r LVV La y)) @ (Va (a y))l
where by a2 a @ a we mean a a² (with the convention that a is a column vector) and (0, y) log pa( y). In other words, the Fisher information matrix is the expectation of the orthogonal projector onto the direction the gradient of the log-likelihood, scaled by the squared norm of that gradient. It is symmetric and positive semidefinite d x d matrix. Its empirical version
(x( N
@ (Vo
YJ))
for some (X1, Yi),.... (XN, YN) fiddd positive-definite, then (u. 6)a == (F(0)u, v) defines a Riemannian metric on the parameter space O that from now will be called Fisher metric (we shall adopt the terminology also when the metric degenerate). general, the Fisher metric can be considered as the pull-back a (possibly degenerate) Riemannian metric on (M X ) 22
Pg. For each i O and u, Rd, if F(O) is smooth and
We also define the pointed Fisher norm of vector E Rd as ||o||ar0) V (A(d)e, u) and the corresponding balls of radius > 0 are referred as Fisher balls of radius e defined as:
Be = {0 e 1 follF(r.) <c)
Some further terminology must recalled before discussing the generalization bounds. Given a loss function E, i.e., continuous function & : [0, +oo) [0, +xx) - [0, +00) such that L(a, b) = 0 if
and only a = b, we define the population risk
R(0) ((p0))p(((
and the empirical risk
Rn, (0) == Σ [(px(V(\Xx,,(xxxxx))) 1=1
where (X,, Y.) iidd 1.. Then, the generalization error is defined
|R - R2 bloo = sup [R(0) R,, (0))
(3)
dE@
The two-scale effective dimension
Here consider notion of complexity for statistical model Me, that depends the properties of the Fisher metric on the parameter space.
Definition 4.1. Given 0 simply 2sED) as
and < 1, define the two-scale effective dimension (or
log E. det (1o+
de(e) = <d+ (1 (1-()
(4)
[og[<s-1]]
where
d Ea F(Oy F(J)
if ET 0
F(0)
otherwise
is the normalized Fisher information matrix, so that whenever the statistical model is not trivial (i.e.
not constant with respect to H) the expectation of the trace of f satisfies
Es [r F(O)] = d.
3

---

Note that dc(E) is the convex combination of the dimension d of the parameter space with 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, inspired by the box-counting or Minkowsky dimension of the statistical manifold Me [5] 22
Given a metric space (X, d) and
subset C X, the box-counting dimension of S is defined as
log Ma(e)
dimbboa (S) lim
log sl
where Ma(e) is the minimum number e-size balls (with respect to the metric d) needed to cover S, also known as the e-covering number of S. The box-counting dimension quantifies how fast Na(e) changes as the radius approaches zero. Motivated by this notion fractal dimension, we can define the effective dimension of statistical model Mo at the scale as
( log No
(5)
log #l
where (E) is the number Fisher balls of size E (defined in
2 needed to cover + The 2sED
defined in (4) is motivated by upper bound estimate of (5) which is computable for given
statistical model under reasonable regularity assumptions.
Remark 4.3. Two parameters show up in the above definition: a micro-scale = >> O and an exponent eS. The emergence of two scales is tied the estimation
S E [0. 1) defining meso-scale argument for Na(e), which requires weaker assumptions compared to those in [5 2 The micro-scale related to the size e of Fisher balls that are used to cover component of the parameter space, while the meso-scale el represents the size of the components of partition of the parameter space, that needs to be fixed in order to localise and adapt the micro-scale covering. This covering argument plays 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 a convex combination of the dimension of the parameter space and the effective dimension.
Remark 4.4. The effective dimension (e( can be shown converge to Çd + (1 () + O, where è == maxage rank (())), see Proposition A.1 The proof follows the strategy of Remark 1 of [2), and is presented in Appendix A for completeness.
5 Generalization bounds
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 deep neural network with high-dimensional layers, the corresponding Fisher information matrix F(0) 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 of (2). because this assumption would imply uniform positive lower bounds on the eigenvalue of F(0). Without loss of generality, we directly assume F = f and θ [0, 1jd, this can be enforced by a suitable scaling of the model.
We list below set of hypotheses, that will be required in the generalization bounds:
(i) the map 0 + (ylax) is class 1 uniformly in (z, y):
(ii) there exist two constants 0 < 01 S a2 such that
an S p(z v), (0( < 02
for all x X, E E,
(iii) the Fisher matrix field F(0) is L-Lipschitz with respect to the Frobenius norm;
(iv) the loss function L is bounded by 2h and is A-Lipschitz, for some b, A > 0;
(v) the meso-scale parameter satisfies Ç [ 1).

---

Some comments about the previous properties are in order. First, property (i) is mild regularity assumption on the model. Property (ii prevents degeneration of both probability densities p(z, y) and (ar, y). The T--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 (but possibly also by more general models). Lipschitz regularity and boundedness of the loss function L. (property (iv)) are standard assumptions (see, c.g.. (20).. Finally, property (v) is structurally needed 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 (v)(v). Then, there exist explicit constant 2 C, K,K,K, no > 0 such that for any y (0, 1}, no. and En
3/8
log n 7m
obtain
P sup [R()) R,) CEn BEG
S HEn Hen do(en))
(6)
The proof of Theorem 5.1 is given in Appendix B
Remark 5.2. Under the assumption that the eigenvalues F are smaller than for some fixed j > the above result implies the existence of % such that, for 0 < < "Yo, the right-hand side of (6) vanishes as n + cc. The upper bound "lo is explicit and depends only on the dimension and on the properties of the model, upper bound of the generalization error, that is non-vacuous also for finite n (even though this can be granted only in the mnder-parametrized regime, i.e. for large enough).
(34). By choosing 7 as above, the right-hand side of (6 gives explicit
The effective dimension of a Markovian model
Markovian models are a family of probabilistic models characterized by a sequential. feed-forward: type structure, see the Markovian property stated below.
Let consider integer I, > 2, a probability space (2,,, and random vector X, : . X2 for j = 0, L. Given a parameter space @ = θ x ... x Δ,, a parametric statistical model Mo Xr, satisfies the Markovian property if and only if for each po po
Ma X1) and for each = ( 0z) E θ O x x θr we have:
Po IL) p(=))pe, (x1 (Zo) po, (Z1|
(7)
where 0,,..., 0g are the parameters associated to the model's distribution of XI...., Xu respec- tively. Many well-known and commonly used neural network architectures, such as ferd-forward neural networks, can be interpreted as Markovian models with concentrated, Dirac-type probability distributions. specific evaluation of the effective dimension these models seems therefore particularly interesting. Exploiting the Markovian property, for j = l,.... I. we define:
F(Ug|15-1)= = / (o, po (dx (x,-1) x;
where l0, (z, (x)-1) == log po, (x, (x,-1) and
F3 = (
0,) = E.n Ex, Iao ". F(,
where E.g and Eu,, 2, denote the (conditional) expectations with respect to p(ro) and pa, (2y (z,--)) respectively. Clearly F; is symmetric and positive semidefinite dj x d, matrix (where dj is the dimension of θ and represents the j-th block of the Fisher information matrix
Fi (((0))
0
F2(01, 02)
F(0)
(8)
:
0
02)
"th constants be computed/estimated in terms of the assumptions.
5

---

We recall that the two-scale effective dimension (2sED) is
dc(c) = Çd + 1- S log f
ff Je. j=1
II
det d0, ... ...d0m..
llog El
where del; (0).()).....
0,) = det (I, ( and Ij denotes the dj x dj identity matrix.
Since F3 depends on all the parameters of the previous blocks, is not possible to directly factorize the multiple integral in (9) Nevertheless, one obtains more easily computable lower bound of de(e), called lower 2sED, by a single application of Jensen's 's inequality as hereafter described. Let d (E) be the 2sED associated with the composition the first m. layers, m 2 2. Then:
1 1-5 log (foente delm dm d4m
deh d 1m-1
(e)
log el
S f
fo
z log El e Sem
log detm d8 m m m
where we have set θ = O₂ x
O and
11 det, d0g ... ...d ddm-1-
dΦ = (d0 de m-
O
/=1
Now, lower bound of (E) can be iteratively defined for 1,.... , L follows:
1 1- C log ff det(I + - Cd 1-c log fo del d0,
(e))= = <d +
1log
,e,
logge
(10)
(c) (e)+ 1-5 if ff log detm d0m dde loog T om
From now on we set d = de and call it the lower effective dimension of the Markovian model Me.
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 (TO). We compute de and de 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 cigenvalues via the linaly.inalg..oom 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 ferw-fo neural network choice is justified by their architecture characterized by Markovian dependency structure. Indeed, the flow of information in FNN unidirectional from input to output, making them representable with finite acyclic graph. We evaluate d, and de real-world datasets, including Covertype dataset () MNIST dataset [11, and CIFAR 10 [1]. All simulations are conducted on a 12th Gen Intel(R) Core(TM) 19-12900KT equipped by 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 No- N1-... -N," a MLP with linear layers, each with width of N, for i O,..., N. followed by ReLU activation functions on all layers except the final layer n. If we denote with W E Nox the parameters of the i-th layer, we can describe "MLP Ng-NN-...-b -N, through blocks of operations defined as Oz(-) = ReLU refers to a convolutional neural network with nı convolutional blocks each one kernel size N; for i 1...., N1 followed by flattening layer and MIP blocks of width L, for i = 1,..., /12- 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
for i = 1...., n. Similarly. "CNN No-N1-... -NN L

---

applying common convolutional kernel to all the channels of the last convolutional layer. Hence, given the input A R.xkk the flattening operation Flatx Nexx follows:
RN is defined as
[Flalx AL:
AL. Kijs
==
for I = .I....,N,
1,...., N₂ where Ap: denotes the Rx obtained by fixing the first dimension at index / and K a k x convolutional kernel which is parametric matrix 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 the training pipeline rather than in the model itself. This makes deep learning models, like MLPs and CNNs, incompatible with 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 small fixed variance o². In other words, if N is the number of blocks, the output of the i-th block Oç is given by
Og 10(+,N(00,,"))
where O2 is the deterministic output of the i-th block, (N( 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 Fx. Note we compare different network topologies while keeping more 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, compute dg and do for different stochastic perturbations of feed-forward neural networks, also varying the covering radius E. We keep constant both the 100 samples used to estimate FN and the 100 vectors of parameters employed for estimating the integrals appearing in and T0). The results are visualized in Figure
Ta and Figure
lb
155
2062
362
2522
253
(a)
(b)
Figure 1: (a) Difference between 2sED and lower 2sED can not be appreciated, which means that the second is tight lower bound of the first. Here, the lower 2sED and 2sED of M 54-16-7 using 100 Covertype samples and 100 vectors of parameters for the Monte Carlo estimation of F is shown; Lower 2sED and 2sED of CNN 7-5] 10-50-4-0-4-10 using 100 MNIST samples and 100 vectors of parameters for the Monte Carlo estimation of FN are extremely close.
Notably, the lower bound is sharp in both the MLP and the CNN case suggesting the conclusions regarding model complexity obtained using (e) are equivalent those obtained when considering d<(s) for all covering radius It is also worth noticing that lower 2sED exhibits 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 o² on 2sED and lower 2sED. We vary the values of x² while computing the de and de for different models on Covertype and MNIST dataset. Figure 4 and Figure F that the impact of 2 on de and de is negligible.
Stability of Monte Carlo estimates. Monte Carlo integration crucial in the estimation of both the Fisher information matrix and the integral within O appearing in 4). To ensure the reliability of our

---

results, we conduct 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 2sHD computed for three different models on Covertype, MNIST and Cifarl0 dataset.
54-18-1
MJP 54:33-119-7
550
223-32-9-7
200
400
200
100
80
6.00
101000
6.2
And
(b)
1000
4035
7-410
3002
CMH:543320-500
3000
2200
3535
2002
1300
1000
1930
4.0
699
400)
Ind00
6000
Ledto
(c)
Figure 2: (a) Stability of the lower 2sED of CNNs estimated using 100 Covertype samples and 100 vectors of parameters for the Monte Carlo approximation with the corresponding error margin; (b) Stability of the lower 2sED of MLPs estimated using 1000 Covertype samples and 1000 vectors of parameters for the Monte Carlo approximation with the corresponding error margin; (c) Stability of the lower 2sED of CNNs estimated using 100 Covertype samples and 100 vectors of parameters for the Monte Carlo approximation with the corresponding error margin; (d) Stability the lower 2sED of CNNs estimated using 500 Covertype samples and 100 vectors of parameters for the Monte Carlo approximation with the corresponding error margin.
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, is crucial to gain a deeper understanding of the role played by the covering radius, denoted as E, 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 [ MLP 54-10-2-10-25-7 is characterized by bottleneck structure in middle of its architecture. A loss information due to this bottleneck is therefore expected as data are mapped into 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- 16-7 in terms of number of parameters. In Figure Bal 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 s. The MLP 54-16-7 model exhibits greater expressiveness within this range of c. Conversely, for smaller values of e, MLP 54-13-11--511 1-9-7 appears to be more expressive. This behaviour 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 MIP 54-16-7 the one achieving the lower training loss using 10000 data, while MLP 54- 14-133-1--9- 1-9-7 is consistently better
8

---

Table 1: Number of model's parameters
MODEL
NUMBER OF PARAMETERS
ML. 54-16-7
976
MLP 54-13-11-9-7
1007
MLP 54-10-2-10-25-77
1005
CNN 7-5-10-50-34-10
4493
CNN
10034
CNN 3-6-5-3) 10-50-34--0
10041
M.P 54 16:3311:-
0232
422
705
2000
101000
0.0
R.00
1000
Lecton
(a)
(b)
OWN 3W.35340099M1
54-3311--3
3N333330050331
M.P 25122115557
14
1.2
Sparss
550079
2.5
1.4
1.5
1.4
1.2
1.5
20007s
520079
Figure 3: (a) Estimated lower 2sED of three different MLP architectures using 100 Covertype samples and 100 different vectors of parameters for the Monte Carlo estimation of Fx: (b) Estimated lower 2sED of three different CNN architectures using 100 CIFAR10 10 samples and 100 different vectors of parameters for the Monte Carlo estimation of F Fx: (c) Training loss plots of MLPs on 10000 random
Covertype samples using Adam with learning rate 1e and batch size 64; (d) Training loss plots of CNNs on CIFARIO 10 using Adam optimizer with learning rate le-3 and batch size 512((e) Training loss plot of MLPs a batch size 64; (f) Training loss plots of CNNs on augmented CIFARIO (double the original size) using Adam optimizer with learning rate le and batch size 512.
100000 Covertype samples using Adam optimizer with learning rate 1e-3 and

---

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 capacity metric.
Other experiments. Other experiments in this direction are performed on the CIFARIO and MNIST dataset and the results are reported in Figures 3b
3d
31
8
varying batch sizes providing
additional empirical evidence that supports our fidings.
8 Conclusions
We propose 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 complexity measure. At the same time, modular version of the 2sED, called lower 2sED. specifically tailored for Markovian models, is introduced as 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 often challenging to compute directly and may only be estimated, often assuming a precise model structure.
Limitations and Future perspectives. We study 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. light 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 develop techniques for further reducing the com- putational 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-stey design of deep feedforward neural networks. Another avenue for future research 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 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.
10

---

References
[1] Amira Abbas, David Sutter, Alessio Figalli, and Stefan Woerner. Effective dimension of machine learning models. arXiv preprint wxXh:2212.04487. 2021.
[2] Amira Abbas, David Sutter, Christa Zoufal, Aurélien Lucchi, Alessio Figalli, and Stefan Woerner. The power of quantum neural networks. Nature Computational Science, 1(6):403-409 2021.
[3] Peter I. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc- dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, (0(1):2285-201,, 2019.
[4] Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 442-44222 2002.
[5] Oksana Berezniuk, Alessio Figalli, Raffaele Ghigliazza, and Kharen Musaelian. A scale- dependent notion of effective dimension. arXiv:2001.1088 2020.
[6] Jock Blackard, Covertype.
UCI
Machine Learning Repository, 1998.
DOI:
[7] Breiman, Friedman, Stone, and R Olshen. Classification and regression trees (crc, boca raton, fl). 1984.
[8] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[9] Nicola Bulso, Matteo Marsili, and Yasser Roudi. On the complexity of logistic regression models, Neural computation, 31 31(8):1992-1623, 2019.
[10] Vladimir Cherkassky, Xuhui Shao, Filip M Mulier, and Vladimir N Vapnik. Model complexity control for regression using vc generalization bounds. IEEE transactions on Neural Networks, 1055)10075-0089, 1999.
[11] Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web]. IEEE signal processing magazine, 29(6):141-142) 2012.
[12] Peter D Grünwald. The minimum description length principle. MIT press. 2007.
[13] Trevor Hastie, Robert Tibshirani, Jerome H Friedman, and Jerome H Friedman. The elements of statistical learning: data mining. inference, and prediction, volume 2. Springer, 2009.
[14] Xia Hu, Lingyang Chu, Jian Pei, Weiqing Liu, and Jiang Bian. Model complexity of deep learning: A survey. Knowledge and Information Systems, 63:2585-2619, 2021.
[15] Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. Advances neural information processing systems, 21, 2008
[16] Ryo Karakida, Shotaro Akaho, and Shun-ichi Amari. Universal statistics of fisher information in deep neural networks: Mean field approach. In The 22nd International Conference on Artificial Intelligence and Statisties, pages 1032-1044 PMLR, 2019.
[17] Michael Kearns, Yishay Mansour, Andrew Y Ng, and Dana Ron. An experimental and theoretical comparison of model selection methods. In Proceedings of the Eighth Annual Conference on Computational Learning Theory, pages 21-30, 1995.
[18] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research). URL httt:://ww. cs. toronto. edu/kriz/cifar huml, 5(4):1, 2010.
[19] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 25, 2012.

---

[20] Mohammad Lashkari and Amin Gheibi. Lipschitzness effect of loss function on generalization performance of deep neural networks trained by adam and adamw optimizers. arXiv preprint arXiv:2303. 16464, 2023.
[21] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436-444 2015.
[22] Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, geometry, and complexity of neural networks. In The 22nd international conference artificial intelligence and statistics, pages 888-896. PMLR, 2019.
[23] James Martens and Roger Grosse. Optimizing neural networks with Kronecker-factored approximate curvature. In Proceedings of the 32nd International Conference on International Conference on Machine Learning- Volume 37, ICML' 15, page 2408 -417. JMLR.org. 2015.
[24] Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. Advances neural information processing systems, 27, 2014.
[25] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:1412.6614 2014.
[26] Guillermo Valle Pérez and Ard A Louis. Generalization bounds for deep learning. CoRR, vol. abs/2012.04115. 15, 2020.
[27] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha expressive power of deep neural networks. In international conference on machine learning. pages 2847-2854. PMLR, 2017.
On the
[28] Jorma Rissamen. Stochastic complexity learning. journal of computer and system sciences, 55(1):89-95, 1997.
[29] Jorma Rissanen. Fisher information and stochastic complexity. IEEE transactions information theory, 42(1) (:4--44747, 1996.
[30] Shai Shalev-Shwartz and Shai Ben-David, Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[31] Vladimir Vapnik. The nature of statistical learning theory. Springer science business media, 1999.
[32] Vladimir Vapnik, Esther Levin, and Yann Le Cun. Measuring the ve-dimension of a learning machine. Neural computation, 6(5):851-876 1994.
[33] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-
1 115, 2021.
12

---

A Asymptotic property of dc(=)
In this section, we prove the following result.
Proposition A.1. Let denote the maximum rank of the Fisher matrix F(0) and let p > be an
upper bound for all the eigenvalues of F()), for all E O. Then, for all Ç E [0,1) and 0 < E < we have
de(s) S cd+ (- log + 22/2)
(11)
log El
and, moreover,
lim d<(e)= (1 <)P. 6-0
Proof. Let us fix S, as above. Denoting by the rank of (11), we have:
d<(e) çd+ log fo det( + 5 == d0
logg
log fo IT (1 + 5 X 1/2 (0)) d0
(d +
llogs
e 1)ro
(1 + A 1/2 (0)) do
S (d + log
logss
S {d+ + log elge(s-
log fo I (1 X3 1/22 (0))
loggl
log El
where Xx) are the nonzero eigenvalues of (0). Notice that log fo 11 (1+ X (0)) d0 is finite.
Indeed, 0 S (d) S by assumption. Then it holds
1 II (1 (1+ (0)) S 2122
This implies that
1 $ f
and therefore
11 We thus conclude that
lim dc(e) çd (1 - C)F.
(12)
To see the other inequality, let us consider A {0 θ |A| < oo. Also, by continuity of the Fisher matrix, the set A has positive measure. Then, we have
f}. Notice that A C θ and hence
= <d+ log fo det(IId + + ( du
=
logge
2 (d+ log fa det(Ida + + F (1) d0
logel
=dd+ log fa det(Idd, + + f (U) d0
logel
13

---

where de is the number of non zero cigenvalues of (() and Fo(O) is the diagonal de do containing only the do non-zero eigenvalues of F(0) for all & e. This yields
log fa det(Tdd) + det(cs- Fg (0)) d0
de(6) 2 (d
|log el
log |A]
log fa IT.= ex (V) d9 +
= =d++
lloge|
log al
log |A]
log fa II e6 X (0)d0 dd
-dd+
lloget
log el
loge
log fA 23 (V)
= (d i(c - 1)
+
Tlggs
flogel
log fa A3 (0) d0
fd ()
llog El
Notice now that since (x(1) for all d θ holds that log fa A (0) di < co and
log fA A (0) do
lim
=0
log El
Therefore
lim de(e) 2 (d+ 6
(13)
Combining 12 and
13
we conclude
lim de(e) Çd + f(1 ().
B Proof of the generalization bound
We conveniently introduce additional terminology and few of new definitions concerning d symmetric matrices and matrix fields. We denote by S (R) the set of real d x d symmetric and positive semidefinite matrices.
Recall that, for all A E 5 (R) and x E Rdd
(Ax, æ²) S ||A|||=]
where || Il denotes the Frobenius norm (this is because the Frobenius norm bounds from above the operator norm). Let 3 > O, then for A E S (R) define Ag by replacing its eigenvalues smaller than 3 with B3 In practice, we consider a spectral basis (u, }==....d with its corresponding sequence of eigenvalues (Ai)j=1.....d then define
Ag Σ max(Aj,B)uu uy.
(14)
Note that this definition does depend the choice of the basis because the matrix A only depends on its cigenvalues and cigenspaces. Given matrix field A : e + S (IR), we define the pointed A norm of a (tangent) vector E Rd at i E θ as
|I / (A(d)o,
Let A E (R), choose spectral basis U (ushe for A and, for any Rd,, we set
[o]A, == max im I....d / A.l
(15)
where X, is the eigenvalue corresponding the eigenvector u4
14

---

Lemma B.1. Let 0: - 84 (R) be L-Lipschitz matrix field. Then for all B > 0, v E R and 1,, 02 Q one has
| s (3 + woll01 -
(16)
where
wa(t) = LB-
(17)
Proof.
We first note that
K(A As)u, u>} 8lo12.
(18)
To see this we write spectral coordinates and compute
(AA As)u, v)
(A, - (ax Σ
E (2 s 3l1,
j=1
J: 7,
whence 18] follows. Now by 18 obtain the conclusion:
||ll s (As(D1)e, ((Aa(00)) - As(
s (As(di)e, + B/v + (((())), - (A(02)u, 2) + B|u|
- () + (2 (2+
1 (2+
02 8/lu2
- (3+ LB- - 02>)1|lll (l))))))
where in the last inequality we have used the fact that
d
Σ max(A B) B) 8/0/2.
Lemma B.2. Let 0 <
and assume that the Fisher matrix field F(0)
is L-Lipschitz Then, F admits an L-Lipschitz extension to the whole R& and θ can be covered by Ca dc(e) Fisher balls of radius E, where (E( is in (4), and Ca is dimensional constant.
Proof. The fact that any L-Lipschitz mapping from a subset of Id into R admits an L-Lipschitz extension the whole Rd is classically known Kirszbraun's 's Theorem. Consider a partition Q of θ made by closed cubes with mutually disjoint interior and side = 8(Q) = ES, and let Q be one of these cubes. Set
B = e2 =2 2-2
(19)
fix a generic 90 E Q and a spectral basis Ug for F(02). Then, the 3-Fisher box centered in 1h of radius 0 is defined as
Boxs,
θ [0 f <e)
Let Sq be the Euclidean ball circumscribed to Q. Consider a partition of Rdd by means of translated copies of (ox), then the minimum number of such boxes that have nonempty intersection with Q is bounded from above by the number intersection with Sq. The volume of each copy of Box (9Q) is given by
i(Q, 8,E) of boxes that have nonempty
2
Boxg, (12)
II
(0)
At the same time, the union of the covering boxes contained SQ + Bzeva /B i.c. in Euclidean
ball B, with
p P= va
Vd8,
(20)
vB
hence its volume is bounded from above by |Bpl Oaa 0², where aa = m + 1) is the volume of an Euclidean ball of radius 1 in Rd and I(.)) is Euler's Gamma function. Therefore
15

---

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 single box. We obtain
ad (
ad 5/2
|Bp
k
(exx,,(0Q))
II==1
VAr,((0))
(o0)(10)
(v0)
(1
S ca II
Gd
(21)
3
3
where we have used the special rounding function
[x]
min (A N: k max(x,
(note that [x] for all æ), and where ca ad(5 Note that, by Stirling's formula ['x +) (2Tx(x/e)= valid as toc, we deduce that ca < (25me/8)4/2 < 6 for d large enough.
Let notice that for all 1 Sq. the translated copy of (0x) centered in 1 is contained in the corresponding translated copy of B (0q) centered in 0, where:
BB. (0)) = {E θ || - -elleaa(0o) <e'}
and E' = de. Indeed, 8 be the center the translated copy Box of Boxp, then for each & E Sq n Box one has by definition |g - 0) F2(2)))) < Consequently we have
E 00l
Aa.:(0e)((E - U, (0e)))
< max i=l...,d
AB,(0O))(E u((o)))
vdlg 0)
<
Now we notice that for all 0 E Sq the translated copy of B centered in d is contained in BB. (1), where
e" = = d(3 d(3L)vaL).
(22)
Indeed, let i be the center of the translated copy B of Bs,, (do). then for each & Siq B one has by definition || - + (()))) < e'. Consequently, by Lemma B.I and by the fact that both 8 and dq contained in BR. one gets
lkg 0llFs(0) & lgg -- (ll v 3 wa(1 P2l)
< e' V w 021)
< v 1(3 wg(5v(8))
s 4(3 5vdL).
where in the last step we have used
wg(5Vdā) /V 5VdL.
(23)
with the last inequality following from the assumption Ç <> 2/3.
16

---

The previous estimate shows that there exists covering of Q by means of at most ko balls of the
form B, B3, (V;), with j ........ Therefore, by combining (9)). (2I) and 22 we get
8 (0Q)
kg s k ca II
E²
d
S Ca II
V 6 1113+55-00 (30
x co(d(3+
(A(00)++++++
==1
s ca(d(3+ 5vaL))
(1(00)) +1
e"
(s")S-1
S ca(d(3+5val)) 5vVl)))
d(3+ -VV+)
10
(d(3 + 5VdL)}s (A(00)+ +
-9d < cald(3 ((d(3+5vdd))+ <d (s")-cu 1Q)
II
(5"))--1
(1(00)) (6"))-11\((000)) +1)
=
(=") (A(00) +1)
s ca(d(33
i=1
where we have used that [xy] S xy++ of e", obtain that the number ly of B-Fisher balls of size e that are needed to cover Q satisfies
+ 1 for all x, y 2 O. Therefore, by conveniently writing e instead
kg S Cae II (1+06-1 1=1
C. Ec==-dQQ det (I+66~F((OQ))
where
1-c
8 d(3 5Tvv))
(24)
and Ca = 13 5V/L)33/2 of B-Fisher balls of size e that are needed to cover θ, by summing over Q and choosing tg as minimum point for det(! + F when 9 E Q, we obtain
Finally, if we denote by k(E) the cardinality of the least number
A(e) < Sd [ det (T+ (T=)== do = Ca -d(le)
Since ||- (0)) 2 || ((o) for 3 > and E we finally obtain that k(e) is also an upper bound for the covering number associated with Fisher balls, and this concludes the proof. L
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 Eo, C, O such that for all e E (0, 6o) we have
sup
( Rr, (1) CE S <4(EE) exp (-Kne*/s)
(25)
where k(5) is a bound on the cardinality of a covering by Fisher balls of radius e.
Proof. As a first step, we need to "discretize" the estimate of the left-hand side of (25) at the micro- scale using the previous covering lemma (Lemma B.2 By inspecting the proof of Lemma B.2
17

---

notice that we can consider 5-Fisher balls instead of Fisher balls for the covering, where B is defined in (2 We also recall that the meso-scale 8 is now given by
c
8
dd(3 + 5Lvd)
Since (0) R(d) R, (1). for all 01, 02 we have
(s,( S., = R(0)) (R,(0) R, (12)).
(26)
Now we estimate each term the right-hand side of (26 under the assumption |01 021 5v
We set (tt) t0 + (1 - t)22 for E [0, 1]. and we estimate the first term:
[
IR(0)) R(V2) 1
((po, dy)
xxy
S xxy
((por))(lx)) - ((por)(01=)) p(dr, dy)
I' 0, (.ClnaaaWWbheerttssssaaaaaaaaa 0.) all p(dee dy)
$ 1/0 /
oi) dy)dt
xxx
SA A / / |xXx
K (oPooce(E, - 0,) pidz, dy)
= A L. /xxy V (o 01)l pocc v) pldx, dy) dt
= L/' S ( (vo log Pacn - v1 u p(x,8) Paçe dy) dt,
where we have used the fundamental theorem of calculus, Fubini's theorem, the A-Lipschitziantty of C. and the fact that V log = Vo log y). Then, by Cauchy-Schward inequality, we obtain
R(O1) R(02) < A / Epoco (2.,v))1
- 01), - 011 01)²² 1/2
dt
s L( Epacy 1²² (2( (F)(0())(()) 01),02 - 0,) 1/2
dt
< AC1 (/' (Fa(0(0)))))))))))) 01),
1/2 dt.
for some constant C > 0 depending on a, ag thanks to hypothesis (ti). Now, Lemma B. implies
that
(Pa(0())(2 01), 02 - 31 s (3 w 011)) 0 0111
(27)
By and
23
we conclude that
IR(1)) R(02)) S AC1 ( (3 + wo(() 011)) -11))) dt 1|0 01 (111))(0))
C2 02 01 (o))):
(28)
where C22 is constant depending only A, C₁ and the dimension d.
18

---

Now, by similar computation, we estimate the second term in the r.h.s. of 26)
1/2
[R - R2,(22222))) SA L.'
poro) (X,, Vi)
(X
V (X,, -01)
71
p( Yi)
1/2
Po(1) (Xi, (i)p(Xi,
dt
1/2
V log Pa (X (2) - -01) Pa(t) (X Yi) p(Xi, Y;)
$ 02
dt.
A=1
(29)
Let us set
-1)) PPoce)(Xs,Y) Yi)
V log Yi, 01)
Z,(t)
and
= sup pa(a, 1) V log po (x. w) p(z. y)
where the supremum is computed w.r.t (z, y) E x y and O. By assumptions (i) and (ii) we obtain
T $ sup V a log po (2; 1² < 80,
where B a2/01. Thus also get
0 5 (t) - T/ - 0112.
The expectation of Z,(t) is
/ ( VVloogoacs (I, v). 01)
pocc((z,)) 3) plz, y)
Zt(t)= (x.r)) [(..)))p[(((())
p(dz, dy)
/ (ooggoco)(z, 9). 02 0.) (ox,)(dx,d) dy)
(((()))( 01) - 01)
hence also 1 n Σi= (t) has the same expectation, by independence of the Zt)
Now, from Lemma
B.2 we know that θ can be covered with A: = k(E) I Cae-de(s) 3-Fisher balls Let now 17 Ce for some C' > 0 to be chosen later, and evaluate
B,...., Bg of size
sup (s)( 2 7 s U Wee
k Σ j=1
U sup (S) 2 17 dEB
sup |S, (s) 21 (0))
deB,
Now for all j = 1, 1,..., k we bound the probability of an event involving the computation of the supremum of Ss, (1) over B, with another one involving only the pointwise evaluation of S, the center Úy of By. Indeed by (28) and (29). and with 0, 0, respectively replacing 12, 01. we deduce
P sup BEB,
(x) 2 2
1
P
[8,
+ sup ()Sm - (n 2 DEB,
C2|lu - 011le7(05) + + /''
(
1/2
< P
[5,)))] + sup de
2i(0)
dt
2
n1
i=1
<
<P
(P(15.(0))
" ) 2
+ P
3t E [0 1 Σ 2,(t) >
1/²
16ag a
19

---

where in the last inequality we have used ||0 - (0)) <E= = C and required C 2 4C2. Owing
Lemma B. and (v). we get
P (1,,( = - 7) - 2 exp
nuj²
(30)
26
and
2m
P
Σ 1=1
Ze(t) 110 - 031 ( 25
s 2xx
(31)
(T -0,1
By
31
find
1 Σ P [0
n/
P
(i) 2
16 }
i=1
11º
P
||0 0 0 ((())
32 0z
2i(t) - 1100 - -0,112 2 57²
+ +P
Σ
32 oz
1=1
n³
P |10 0))lF=(0(00)
+ 2eexp
(-
32 0z
29 T2 2T
0312
2 exp 1-2nnn4-29
(32)
where
C
C. 3229 26 T2
and where the last inequality follows from
1²2
|| - 0,11
(33)
32 32
which can be enforced by a suitable choice of the constant C, as explained hereafter. Indeed, using Lemma B.1 and (23 we obtain
||0 2 1P (0(0))
- (3 + wp(1 05
- (3 -gt+0(t(--011) 0,)))
3 3+5LVd 7
< (3+ 5L+
C
Therefore, if we choose C' such that
C2
(3+5LVd) <
32a
we obtain 33 as wanted. The proof of (32) now complete.
Finally, by
30 and 32
and observing that the second exponential is the leading term, we get
sup [(,) 2 n)
P
sup JEB;
S,(0)) 1)
1=1
< 2kk(e)
exp
r27? 212
+ exp (-Caron 2C)
4kk() exp
(-Csny88/3)
where Cs min(C4, (263)-1) and owing to 4 - 2 < 3, which follows from assumption (v). In
conclusion we obtain (25) with K 88/
20

---

3/8
Proof of Theorem 3.7
We choose 7 and let En
Jog y
and K be in Lemma B.3 By
combining Lemma B with Lemma B.3 we obtain
(K log n
sup [R(0) - Rn (d)) 2 Cen dEG
S 4 4k(()) exp
7
S Hendd(En)
where C' is in Lemma B.3 and H 4Ca-
We can now explain Remark 5.2 by noting that, if we choose
8K
< y 70 3d(1 + log(1 + 22/2))
(34)
with K as in Lemma B.3 then the generalization bound becomes infinitesimal as n +00. Indeed, by the upper estimate (11) we have
dc(e) çd +d (1-s+ log(1 (1 + 12/22) S d(1 log(1 +2² d,
|log())]
whenever eex(-11) so that
(dn()
-de(en) En
logn n < 3d/3/ K/7
yn
(35)
Hence, the infinitesimality of the generalization bound as > co follows from 3d/8 K/7 0, as wanted.
We recall Hoeffding's 's estimate, which is used in the proof of Lemma B.3
Lemma B.4 (Hoeffding' estimate). Let Zi, i = 1, ..... be independent random variables, such that Zg [a, b) almost surely. Define Vn 1 Ei=1 Z; and take E > 0, then
2n
P P(VV -VV]]] 2 e) S 22exp
(- a)
C Figures
The appendix contains 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 show that the impact of a² on de and de is negligible. To avoid discrepancies, we fix the data and the parameters used to estimate both de and de via Monte Carlo integration. The meaningfulness of 2sED and lower 2sED for deterministic deep learning models is then enforced by taking the limit as x² O.
Table 2: Number of parameters of CNNs
MODEL.
NUMBER OF PARAMETERS (d)
CNN 10-50-3-03
4493
CNN 10-50--30-
4753
CNN 5-4-3110-50-34-10
4985
21

---

o² 0²=1e-
600
o² o²= le -4
0² =e
550
0² le
o² le -7
500
2sED
450
400
350
300
0.1
0.01
0.001
0.0001
le-05
1e-10
le:25
2e-50
1e-75
1e:100
1e-200
1e-300
(covering radius)
Figure 4: Impact of 2² de for MLP 54-16-7. The 2sED is estimated with fixed seed varying o².
3500
0² = le
3000
0² = le 5
0² = 1e -6
2500
2 = le
lower 2sED
2000
1500
1000
500
0.1
0.01
0.001
0.0001
1e-05
le-10
1e-25
2e-50
1e-75
1e-100
1e:200
1e:300
E (covering radius)
Figure 5: Impact of o² on de for CNN 5-7|10-50-34-10, The 2sED is estimated with fixed seed
varying a
22

---

4000
CNN 5-7/10-50-34-10
CNN 7-5/10-50-34-10
3500
CNN 5-4-3/10-50-34-10
3000
lower 2dED
2500
2000
1500
1000
500
0.1
0.01
0.001
0.0001
1e-05
1e-10
1e-25
2e-50
1e-75
1e-100
1e-200
1e:300
E (covering radius)
Figure 6: This figure plots the lower 2sED of CNNs estimated using 100 MNIST samples and 100
vectors of parameters for the Monte Carlo approximation.
CNN 7-5/10-50-34-10
CNN 5-7/10-50-34-100
CNN 5-4-3110-50-34-10
1.0
Training Loss
0.6
0.0
40
Epochs
Figure 7: Training loss plots of CNNs on MNIST using Adam with learning rate 1e and a batch size 256.
23

---

CNN 7-5/10-50-34-10
CNN 5-7/10-50-34-10
CNN 5-4-3110-50-34-10
1.0
Training Loss
0.6
20
30
40
50
Epochs
Figure 8: Training loss plots of CNNs on MNIST using Adam with learning rate le and a batch
size 512.
CNN 7-5/10-50-34-10
CNN 5-7|10-50-34-10
CNN 5-4-3110-50-34-10
Training Loss
1.5
1.0
0.5
10
20
30
40
50
Epochs
Figure 9: Training loss plots of CNNs on MNIST using Adam with learning rate le and a batch size 2048.
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction do reflect and summarize the paper's contribu- tions and scope. The sections afterwards present more technical details including proof of mathematically rigorous statements.
Justification:
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our generalization bound (the technical main result of the paper) requires certain assumptions the statistical model which stated explicitely and precisely in the mathematical theorem. Our simulation results could be further expanded in future project build up more confidence in the practical performance of bounds.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: As you will see our paper is entirely rigorous. Some of the authors are pure mathematicians.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: You can see in the "Experiments" section that all our simulations transparent and can be reproduced with minimal effort.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No].
Justification: The main contribution of this paper is a theoretical result on complexity measures for deep learning models. Datasets are public and referenced in the experiments section, while the code can be casily reproduced using definitions and the experimental setting described in the main body this work.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
The training details are described in the captions of the experimental results' figures, providing enough information to appreciate our claims. The experimental evidence of this work involves only the training.
Justification:
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
25

---

Justification: We report the enror margin for the Monte Carlo approximation of the 2sED. All the other experiments are performed for different model architectures and datasets providing enough statistical significance of our claiming.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We have provided info about the machine specifics and the memory consump- tion but not on the execution time because the focus of the paper is more on the theoretical validation and only partially on the computational efficiency of the lower 2sED, which could quite likely improved in the future (see the limitations discussed point and the Future Perspectives section).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Yes it does.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is a theoretical result on learning theory and hence has not direct, neither positive nor negative, societal impacts.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Due the theoretical fundamental nature of work, this question does apply.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use existing assets.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not introduce any assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
26

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects
27


Reviews:
[{"review_id": "4sUeOqTe7L", "reviewer": "Reviewer_iesa", "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.", "questions": "How does the method fit into the existing literature on understanding the expressivity of neural networks?", "limitations": "I do not see any ethical and societal implications of the work that need to be discussed.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors study a fundamental problem in theoretical machine learning and introduce a novel approach to this problem\n- Unlike many other complexity metrics, this one admits efficient approximations in many settings\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and the positive feedback.\nWe are happy to add a more thorough discussion of previous work on the expressivity of neural networks to the manuscript. \nThe effective dimension (ED) is a rather novel capacity measure that has been introduced recently (by Figalli et al.). Later a generalization bound has been proven (see https://www.nature.com/articles/s43588-021-00084-1) which justifies calling it a capacity measure. In https://arxiv.org/pdf/2112.04807 some of us presented an overview (see Table 1) how the ED relates to other (more standard) capacity measures. \nIn the submitted work we further develop the ED by finding a solution to its main weakness, namely that it is hard to evaluate (like many other capacity measures too). We show that for Markov models we can approximate the ED efficiently.", "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": "", "extra_scores": {}}, {"review_id": "9pSKvAwIrB", "reviewer": "Reviewer_aPDv", "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.", "questions": "My first question is does this work bare any similarity to the following papers:\n\nA. 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.\n\nB. Dupuis, G. Deligiannidis, and U. Simsekli, \"Generalization Bounds with Data-dependent Fractal Dimensions\", ICML, 2023.\n\nIn 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?\n\nMy 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. \n\nMy 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": "The authors do an excellent job at stating their mathematical assumptions and computational bottlenecks. This paper honestly addresses its limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "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. \n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and the positive feedback.\nYour summary of the paper is correct and very nice.\nYour  “weakness” comment is also correct. Computing the eigenvalues of FIM is computationally intensive (as the FIM get’s very large). One main contribution of our work is that we show in the case of Markov models we can compute the ED efficiently in an iterative fashion (layer-by-layer).\n\n**Answer to your Question 1 [regarding similarities to existing works]**\n\nWe thank the reviewer for pointing out other work that can be potentially related to a more geometric notion of complexity. \nThe first work studies more the generalization properties after training of a machine learning model using the box-counting dimension (with respect to the Euclidean metric) of the support of the invariant measure induced on the parameter set by the training process. Even if the box-counting dimension is computed with respect to the Euclidean metric and the model architecture arises only in the support of the invariant measure, it is an interesting research question to study the 2sED replacing the Lebesgue measure with the invariant measure induced by the training process.  \nThe second article is much more related with the 2sED. Their idea is to include some geometrical properties of the loss into the generalization bound, but their metric (see (8)) is different than the Fisher metric used in our work in general. The main difference is that the 2sED introduces a “fractal dimension” which is data-dependent, in the sense that the 2sED of a set of hypotheses varies based on the amount of training data at disposal. This connection is incorporated in the scale parameter appearing in the definition and we believe it is an important feature of the 2sED, since it seems to correlate well with the training loss. Also, the connection between the box-counting dimension and the persistent homology dimension holds at the limit of the covering radius (see (Kozma et al.,2005;) cited in the second article).\n\n\n**Answer to your Question 2 [regarding practical aspects]**\n\nWe agree with the reviewers, in the final version we will add an extra section pointing out some methods for the eigenvalues approximation.\n\n\n**Answer to your Question 3 [regarding box counting dimension]** \n\nThe choice of the Fisher boxes becomes natural if we consider the Riemannian metric induced by the FIM over the statistical manifold. In principle one could define other metrics, but the one induced by the FIM seems to be the most used and validated by the literature (see reference [30], [6], [23] ). \nThe lower and upper box-counting dimensions are related with the existence of the limit in the definition of the Minkowski–Bouligand dimension. The 2sED is inspired by the box-counting dimension but the radius of the covering sets is decided in relation to the number of training samples (think of it as a resolution at which you look at the model). Therefore the limit on the covering radius is not present in the definition of the 2sED.", "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": "", "extra_scores": {}}, {"review_id": "NoTVWHSc9c", "reviewer": "Reviewer_MhtR", "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.", "questions": "-\tDoes the generalization bound have the same value for all networks that perfectly fit the training set, if the empirical Fisher matrix is used?\n-\tDoes 2sED satisfy (P2) in line 19?", "limitations": "Not all limitations are mentioned (e.g. experiments only show correlation of 2sED with the training loss and not the validation/ test loss).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tAddresses an important and challenging topic.\n\n2.\tSolid mathematical results.\n\n3.\tClearly written.", "weaknesses": "-\tThe 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.\n\n-\tSome 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).\n\n-\tThe empirical results are limited showing correlation only with the training loss and not the validation/test loss which is the main goal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and the feedback.\n\nWe next answer the questions/comments raised:\n\n**(1) Main weakness regarding the significance:**\n\nIt is correct that 2sED is in general expensive to calculate. However, we show that for the case of Markov models we have a lower bound that can be computed efficiently and that performs well in practice (in the sense that it is close to 2sED for these models). We further want to emphasize that the 2sED may be computationally expensive to compute for a general model, but it is still much easier to compute than other complexity measures in general, like the VC dimension and the Rademacher complexity that can only be estimated.\n\n\n\n**(2) Comment regarding technical technical details missing:**\n\nWe have described how feed-forward and convolutional neural networks can be seen as Markovian models in the experiment section. Furthermore, there is no way to pass from the effective dimension to the 2sED. It is another definition inspired by the same motivation. \nWe are happy to add these details in an updated version of the manuscript. \n\n\n\n**(3) Comment regarding the limited empirical experiments:**\n\nOur empirical analysis of the correlation between the (lower) 2sED and the post-training performances of neural networks with different topologies but with a similar number of parameters is supported by various experiments conducted on qualitatively different datasets and networks. Moreover, one has to take into account that our work contains a consistent theoretical part, and the experiments are meant to illustrate some features and potentials of the (lower) 2sED in the context of Markov models/feedforward networks. \n\n\n**(4) Question “Does the generalization bound have the same value for all networks that perfectly fit the training set, if the empirical Fisher matrix is used?”**\n\nEven if the empirical FIM is used, having two models that perfectly fit the training set would mean that $1/n \\sum_j \\nabla_\\theta \\log p^i_\\theta (x_j,y_j) = 0$ for $i=1,2$ where $p^i_\\theta$ is the probability distribution associated to the two models respectively and $\\theta$ is the optimal point. This does not imply that the empirical FIM of the two models is the same since the sum of the tensor product is not the tensor product of the sums. Indeed, the FIM and the empirical FIM evaluated in the optimal point are meant to give some information about the curvature of the log-likelihood around the optimal point.\n\n**(5) Question: “Does 2sED satisfy (P2) in line 19?”**\n\nBoth the 2sED and the lower 2sED satisfy assumption (P2) in the case of the Markovian model. The main advantage of using the lower 2sED is that the bias introduced by a Monte Carlo estimation of the integral is reduced by the fact that, except for the first integral, the integral is outside the logarithm. \n\n\n**Concluding comments:**\n\nWe thank the reviewer for the constructive feedback again. We hope that our explanations above were helpful in removing some criticism about the submitted manuscript.", "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": "", "extra_scores": {}}, {"review_id": "BnOwPy5htu", "reviewer": "Reviewer_5Uzy", "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.", "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?\n+ Please explain the last step in the proof of Lemma B.1.\n+ What is $S_{\\epsilon}$ in the line 456?\n+ Please explain the last equality in p.15 (refer to the definition of $d_{\\zeta}(\\epsilon)$ in (4)).\n+ The definition of $d_{\\zeta}(\\epsilon)$ in (9) looks not the same as (4) (for example, as $L=1$).", "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.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "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. \n+  Notations are not consistent: for example (2) and (19).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and the feedback.\nWe next answer the criticism/questions:\n\n\n**(1) Weakness comment about the notation:**\n\nThank you for the comment. We will make the notation consistent.\n\n\n**(2) Question regarding Assumption (iii)**\n\nWe agree with the reviewer that assumption (iii) is quite strong. However, the proof of Theorem 5.1  can be easily changed using Fisher balls (more similar to the classical Euclidean balls) instead of the Fisher boxes assuming only the Lipschitz regularity of the FIM. This assumption is much weaker than assuming the Lipschitz regularity of the eigenvectors and it is satisfied by, for instance, FNN with a sigmoid activation function (or other smooth enough activation functions). We will update the paper with the new proof as soon as possible. We thank the reviewer again for the comment that helped us to improve our result. \n\n\n**(3) Question regarding the last step in Proof of Lemma B.1:**\n\nHere are additional explanations with the new balls:\n$$||v||^2_{A_{\\beta}(\\theta_1)}  = <A_{\\beta}(\\theta_1)v,v> = \\sum_{i=1}^d \\lambda_{i,\\beta}(\\theta_1)|<v,u_i(\\theta_1)>|^2 \\ge \\beta |v|^2$$\n\n\n**(4) Question about S_{epsilon} in line 456:**\n\nTypos, it should be $S_Q$.\n\n\n**(5) Question about last equality in p.15:**\n\nThis follows from writing the integral as $\\epsilon$ to the $\\log_{\\epsilon}$ of the integral and changing the base of the logarithm from $\\epsilon$ to $e$. \n\n\n**(6) Question regarding def (9) vs def (4):**\n\nFor Markovian models, the two definitions coincide since the FIM factorizes and hence det(F) is the product of the determinant of each block. We write F instead of $\\hat{F}$ just for convenience as explained in line 148 page 4.\n\n\n**Concluding comments:**\n\nWe thank the reviewer for the constructive feedback again. We hope that our explanations above make clear that the assumptions of Thm. 5.1 are clearly there but are not as restrictive as they may seem at first sight (assumption (iii) can be weakened as said in the answer to question (2)). We also want to highlight that totally removing (or even relaxing) the assumption does not seem possible to us (without losing the generalization bound given by Thm 5.1).", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)