Effective dimension of machine learning models
Authors: Amira Abbas
David Sutter
Alessio Figalli
Stefan Woerner
Venue: Submitted to ICLR 2023 (2023)
Keywords: Generalization
capacity
effective dimension

Abstract: Making statements about the performance of trained models on tasks involving new data is one of the primary goals of machine learning, i.e., to understand the generalization power of a model. Various capacity measures try to capture this ability, but usually fall short in explaining important characteristics of models that we observe in practice. In this study, we propose the local effective dimension as a capacity measure which seems to correlate well with generalization error on standard data sets. Importantly, we prove that the local effective dimension bounds the generalization error and discuss the aptness of this capacity measure for machine learning models.

Under review as a conference paper at ICLR 2023
EFFECTIVE DIMENSION OF MACHINE LEARNING MODELS
Anonymous authors Paper under double-blind review
ABSTRACT
Making statements about the performance of trained models on tasks involving new data one of the primary goals of machine learning, i.e. understand the generalization power of a model. Various capacity measures try to capture this ability, but usually fall short in explaining important characteristics of models that we observe in practice. In this study, we propose the local effective dimension as capacity measure which seems to correlate well with generalization error standard data sets. Importantly, we prove that the local effeective dimension bounds the generalization error and discuss the aptness of this capacity measure for machine learning models.
INTRODUCTION
The essence of successful machine learning lies in the creation of model that is able to learn from data and apply what it has learned to new, unseen data (Goodfellow et al.] 2016). The latter ability is termed the generalization performance of a machine learning model and has proven to be notoriously difficult to predict priori (Zhang et al.] 2021). The relevance of generalization is rather straightforward: if one already has insight on the performance capability of model class, this will allow for more robust models to be selected for training and deployment. But how does one begin to analyze generalization without physically training models and assessing their performance on new data thereafter? This age-old question has a rich history and is largely addressed through the notion of capacity. Loosely speaking, the capacity of model relates to ability express a variety of functions (Vapnik et al. 1994). The higher model's capacity, the more functions it is able to fit. In the context of generalization, many capacity measures have been shown mathematically bound the error model makes when performing task on new data, i.e. the generalization error (Vapnik & Chervonenkis, 1971: Liang et al. 2019: Bartlett et al. 2017). Naturally, finding a capacity measure that provides tight generalization error bound, and in particular, correlates with generalization error across a wide range of experimental setups, will allow us to better understand the generalization performance of machine learning models.
Interestingly, through time, proposed capacity measures have differed quite substantially, with trade- off' apparent among each of the current proposals (Jiang al., 2019). The perennial VC dimension has been famously shown to bound the generalization error, but it does not incorporate crucial attributes, such data potentially coming from distribution, and ignores the learning algorithm employed which inherently reduces the space of models within a model class that an algorithm has access (Vapnik et al. 1994). Arguably, one of the most promising contenders for capacity which attempts to incorporate these factors are norm- based capacity measures, which regularize the margin distribution of model by a particular norm that usually depends on the model's trained parameters (Bartlett et al., 2017 Neyshabur et al., 2017b] 2015). Whilst these measures incorporate the distribution of data, as well as the learning algorithm, the drawback is that most depend on the size of the model, which does not necessarily correlate with the generalization error in certain experimental setups (Zhang et al. 2021).
To this end, we present the local effective dimension which attempts to address these issues. By capturing the redundancy of parameters in a model, the local effective dimension is modified from (Berezniuk al.) [2020] Abbas et al., (021) to incorporate the learning algorithm employed, in addition to being seale invariant and data dependent. The key results from our study can be summarized follows:

---

Under review as a conference paper at ICLR 2023
Table I: Overview of established capacity measures and desirable properties. The first property is whether the measure can be mathematically related to the generalization error via an upper bound. The second states whether this bound is good in practice, i.c., that the measure correlates with the generalization eгrоr in various experimental setups, such as (Zhang et al. 2021). Scale invariance corresponds to the measure being insensitive to inconsequential transformations of the model, such as multiplying a neural network's s weights by a constant. Data and training dependence refers to measure accounting for data drawn from a distribution and the learning algorithm employed. Finite data merely implies that the measure can handle finite data. Lastly, efficient evaluation refers to the possibility of estimating the capacity measure in polynomial time (in the number data).
VC-
Rademacher
Margin- based
Norm- based
Sharpness- based
Local
dimension complexity
ED
Generalization bound
2. Correlation with generalization
X
X
X
3. Scale invariant
X
X
X
v
Data dependent
X
V
/
Training dependent
V
6. Finite data
7. Efficient evaluation
X
The local effective dimension, unlike its predecessors, includes training dependence as well as other desirable properties summarized in Table
We prove that the local effective dimension bounds the generalization error trained model with finite data (see Theorem 4.1
The local effective dimension largely depends the Fisher information, which is often approximated in practice (Kunstner et al. 2019). We rigorously quantify the sensitivity of the local effective dimension when evaluated with an approximated Fisher information (see Proposition 3.2)
Lastly, we empirically show that the local effective dimension correlates well with gener- alization error various experimental setups using standard data sets. The local effective dimension is found to decrease in line with the generalization error as network increases in size. Similarly, the measure increases in line with the generalization error when models are trained on randomized training labels.
PRELIMINARIES
In this section, we provide an overview of relevant literature and concise introduction to generaliza- tion error bounds and the Fisher information.
2.1 RELATED WORK
We briefly discuss relevant capacity measures proposed in literature, but defer (Jiagg al. 2019 for more comprehensive overview. Given a model class, Vapnik et al. showed that the VC dimension can provide an upper bound on generalization error (Vapnik et al., 1994). While this was crucial first step in using capacity to understand generalization, the VC dimension rests on unrealistic assumptions, such as access infinite data, and ignores things like training dependence and the fact that data, more reasonably, comes from a distribution (Holden & Niranjan 1995). The closely-related Rademacher complexity relaxes some the assumptions made on the model class, but still suffers similar issues to the VC dimension (Yin et al. 2019: Wang et al. (2088). Since then, myriad of capacity measures aiming to circumvent these problems and provide tighter generalization error bounds, have been proposed. Margin-based capacity measures stemmed from the work of Vapnik and Chervonenkis in 1974 who pointed out that generalization error bounds based on the VC dimension may be significantly enhanced in the case of linear classifiers that produce large margins. In (Bartlett et al.) 1998). it was shown that the phenomenon where boosting models (no matter how large you make them) do not overfit data, could also be explained by the large margins these boosting models achieved. Since the
2

---

Under review as a conference paper at ICLR 2023
grand mystery in modern deep learning can be characterized by the same phenomenon extremely large overparameterized neural networks that seemingly do not overfit data - seems natural to try extend the idea of margin bounds to these model families. Moreover, margin- -ased approaches allow us to leverage the fact that learning algorithms, like gradient decent, produce classifiers with large margins on training data Unfortunately, looking at margins in isolation does not say much about the performance of deep neural networks on unseen data. There have been recent investigations on how to add normalization such that margin- based measures become informative, Most of these proposals involve the incorporation of the Lipschitz constant of a network, which is simply the product of the spectral norms of the weight matrices (Bartlett et al., 2017). These normalized margin- based techniques gave rise to form-based capacity measures which appear promising, however, it is still unclear how to perform this normalization and often, the normalization depends on some factor that scales with the size of the model, which is undesirable in the case of deep neural networks (Neyshabur ctt al. 2015).
Another interesting proposal for measuring capacity came about by trying to characterize the local minima achieved by deep networks after training (Keskar et al. 2016 Hochreiter Schmidhuber 1997). These so-called sharpness- based measures often depend on the Hessian, which incorporates notion of curvature at a particular point in the loss landscape. It was believed that sharper minima led to better generalization properties, although this was later shown to be incorrect sharpness measures were usually not scale invariant and thus, did not correlate well with generalization error in various scenarios (Dinh et al., 2017).
This leads us to the purpose of this study where we introduce and motivate the local effective dimension as capacity measure. The effective dimension arises from the principle of minimum description length and thus, tries to capture existing redundancy in a statistical model (Berezniuk et al.
2020) Cover & Thomas | [Rissanen 1996). Redundancy has been widely studied in deep learning
through techniques like pruning and model compression (Yeom et al., 2021 Molchanov et al. 2019
Wiedemann et al. 2020 Tung & Mori 2020 Cheng et al. 2018 2017 Tishby & Zaslavsky 2015).
Interestingly, attempts to connect redundancy/minimum description to generalization performance
have also been studied in (Hinton & van Camp 1993; Achille & Soatto 2018 MacKay| [992).
and the idea was used to compare the capacity of quantum and classical machine learning models in (Abbas et al. (02T). We refine the existing definitions of the effective dimension, which in turn leads us to the creation of a local version that conveniently meets the criteria presented in Table [
2.2 GENERALIZATION ERROR
typical first step in motivating use for a capacity measure is to prove that it bounds the generalization error. Informally, all generalization error bounds have the same structure
generalization error I estimate of error + complexity penalty,
which attempts to relate generalization error an empirical estimate of the error, plus complexity penalty captured by the proposed capacity measure. Since empirical estimates correspond to the train- ing error on available data, which can mostly be trained to zero with very deep networks in practice, the capacity term is usually of most relevance. More formally, suppose we are given a hypothesis class, H. of functions mapping from X' to y, a training set S, = ((x1, ((x1,))) )........ (Ii, yn)} E (X' x )) where the data pairs (Iz, v/5) are drawn i.i.d. from some unknown joint distribution p. and let é: y x y - TR be a loss function. The machine learning task is to find a particular hypothesis h E H that minimizes the expected risk, defined R(h)- ;= E(z.g)>pl((he (1((2)) ())]. Since only have access to training set Sn, a good strategy to find the best hypothesis E H is to minimize the so called empirical risk, defined as R., (h) := Σ. E(h(xz), y.). The difference between the expected and the empirical risk is known as the generalization error gap. This gap gives us an indication as to whether a hypothesis h H will perform well on unseen data, drawn from the unknown joint distribution p (Neyshabur et al. 2017a). Therefore, an upper bound on the quantity
sup [R(h) - (h),,), kEW
'A beautiful review of margin bounds is encapsulated in (Anthony & Bartlett 2009) where lower bounds are proved for certain function classes.
3

---

Under review as a conference paper at ICLR 2023
which vanishes grows large, is of considerable interest Capacity measures help quantify the expressiveness and power of H. Thus, the quantity in equation is typically bounded by an expression that depends some notion of
et al. 1994).
2.3 FISHER INFORMATION
The Fisher information has many interdisciplinary interpretations (Frieden 2004). In machine learning, several capacity measures incorporate the Fisher information different ways (Liang et al. 2019; Tsuda et al. 2004). It is also crucial quantity in the effective dimension and is thus, briefly introduced here.
Consider a parameterized statistical model p(æ, y; 0) ply|æ; 0)p(z) which describes the joint relationship between data pairs (x. for all x X. E y and A E S RR. The input distribution, p(z), is a prior distribution over the data and the conditional distribution, p(y[æ; 0) describes the input-output relation generated by the model for a fixed O. The full parameter space forms a Riemannian space which gives rise to Riemannian metric, namely, the Fisher information which we can represent in matrix form
a 30
F(0)= E (xx _ logp(z, y; 0) log p(x, y: 0)
By definition, the Fisher information matrix is positive semidefinite and hence, its eigenvalues are non-negative. In practical applications where d typically large, there exists sophisticated techniques to efficiently approximate the Fisher information matrix. This is discussed in Appendix F.3
3 EFFECTIVE DIMENSION
The origin of the effective dimension arose from a simple operational question: Is it possible to quantify the number of parameters that are truly active in a statistical model In the case of deep neural networks, it has already been shown that many parameters are inactive, inspiring better design techniques (Han al., 2015). Measuring parameter activeness can made mathematically precise with tools from statistics and information theory. In particular, the effective dimension unites the principle minimum description length with the Kolmogorov complexity of model (Rissanen) 1996, Cover & Thomas (006)) We introduce the global effective dimension here and refer the interested reader to (Berezniuk et al. 2020; Abbas et al. 202I) for more details.
3.1 GLOBAL EFFECTIVE DIMENSION
To shorten notation we write
7/n
Knny
(2)
2x log n
for n E N, which represents the number of data samples available, and a constant y (2x logn
1].
Definition 3.1. The global effective dimension of a statistical model Me {p(.;; 0) Rd) with respect N and y (2 f2g log
1]. is defined
2 2log Vo So Vdet (ida Kn,7 F())) d0
dn,)(M)) =
(3)
log Knnyy
where Ve = So dl R4 is the volume of the parameter space and Kn,; is defined in equation The matrix F() gaxd is the normalized Fisher information matrix defined as
2
Ve
Piy(0) [ (i)
where F(O) [ddd denotes the Fisher information matrix of p(. :):
2 assume that the loss function Lipschitz continuous which implics that equation vanishes as n + oo.
A parameter is considered active if has a sufficiently large influence the outcome of its statistical model, i.c. varying the parameter changes the model.
4

---

Under review as a conference paper at ICLR 2023
For conciseness, simply denote the global effective dimension as dn,7- The global effective dimension converges to the maximal rank of the Fisher information matrix F := maxøge re E f1,2.... ...., d} in the limit of n - oc, where ra denotes the rank of F(0). Thus, it often makes sense to standardize the measure by looking at the normalized effective dimension, denoted by dn.7 dn.z/ d, which gives proportion of active parameters relative the total number of parameters in the model.
We prove that the global effective dimension is continuous as function of the Fisher information matrix. Since the Fisher information is typically approximated in practice, such statement relevant ensure small deviations the Fisher information do not exacerbate possible deviations in the global effective dimension (see Section for more details)
Proposition 3.2 (Continuity of the effective dimension). Let N. Y (2 (2=log log ,1, and consider two statistical models Me and M'a with C Rdd und corresponding Fisher information matrices F and F', respectively. Then.
a ,,,,,,,,,,,
(dn,(Me) dn,
1
1
max BE9
V F(O) F((0)
6(F)
o(F))
(F( + (FF(FF)
log Kin.y
where Co is dimensional constant, Kn,y is defined equation and
((F) = 1
Vo So (dee(F(())))
(FF)= =max {log
(11 Ve
/ det(ida +(B))d)
log 1 Ve
/ (dct(F(8))ao)
The proof is given Appendix B Proposition 3.2 is informative for statistical models Me and M' with corresponding Fisher information matrices F and F' such that o(F) 0 and o(F") 0, re- spectively. This unavoidable consequence is due to lim,-+50 (MM) = max rank [ (0)) and lim, (M,)
7' maxsee rank (F)())).. Hence, effective dimension is not continuous as + co. This is consistent with Proposition 3.2 where in the case of f < d or Fl < d, we have ((F)
that when * F' the
o(F") O, respectively.
Remark 3.3 (Stabilized computation of the effective dimension). For large d, sufficiently large and models with a full rank Fisher information matrix, the effective dimension of order d. This implies that del del(ida + Kn,P((0 is exponentially large in d, which makes direct calculation of the effective dimension via Aaaaaiinnnummicullll challenging when large models are considered. This can be circumvented by rewriting the effective dimension as
(M,)
2 log Kin
log
(
111 Vo
exp
log det (ida Kn, knn))(0)) dB
Noting that
log det (ida + Kn, F(n)
1
ir log (ida + Kn.g Kn.FF(0)) F(0))
2
d
2 log (1 (1 (F(0))) =: z(0),
(4)
where >e( (()) denotes the i-th eigenvalue of F(0). The quantity z(0) can be computed without any under- overflow problems for large n and d. Choosing Ç maxoce z(0) then gives
2C
Vo ( cxp (z(0) <) a8
(M,)
log
log Kn.
log Kn.7
which is numerically stable expression for the effective dimension.
*This proposition also holds for the local effective dimension introduced in Definition 3.4

---

Under review as a conference paper at ICLR 2023
3.2 LOCAL EFFECTIVE DIMENSION
While the global effective dimension has nice properties, an important aspect to note is that incorporates the full parameter space θ In practice, however, training models with a learning algorithm inherently restricts the space of parameters that model truly has access to. Once a model trained, only fixed parameter set E is considered, which chosen to minimize a certain loss function. This leads us to the introduction of the local effective dimension which accounts for dependence on the training algorithm. To achieve this, we define an e-ball around a fixed parameter set 0 E O C Rd for 0 as
(.(0)) = 10 E θ 10 0- S c).
with volume V, == [B.(B.) d0.
Definition 3.4. The local effective dimension of statistical model Me (p(:-00) 0 E O}
around 6* O with respect to n N. y E ( ing 1]. and > 1/V is defined
n
2oog (t. IB Vdet (idaa + Kn,, F(0)) d0)
(Mn(MB,(0)))
log Kn.y
for Kn, given by equation 2 The matrix F(O) E Bddd is the normalized Fisher information matrix defined as
Ve
(o) = - (B)) (r(F (o)
where F(0)= E Rddd denotes the Fisher information matrix of ;))
For case of notation, we denote the local effective dimension as da.y.e. From Definition 3.4 we immediately see that the local effective dimension scale invariant as it depends on the normalized Fisher information matrix, as well as training dependent, since the training determines 6*. Via its dependence on the Fisher information, the local effective dimension also incorporates an assumed distribution for the data and is built for finite data, summarized in Table Proposition 3.2 further proves that the local effective dimension is continuous in the Fisher information matrix.
The computationally dominant part in evaluating the local effective dimension is the calculation of the Fisher information matrix. Luckily, this is a well-studied problem with existing proposals for efficient evaluation (Kunstner et al. 2019 Martens & Grosse 2015). Since we only require the eigenvalues of the Fisher matrix for the local effective dimension, we can further exploit these Fisher approximations and do not need to store d x d matrix (see Section E.3 for more details). Additionally, the integral over the e-ball can be evaluated efficiently with Monte-Carlo type methods.
To complete the criteria from Table I it remains show that the local effective dimension bounds and correlates with the generalization error, which is illustrated next.
4 GENERALIZATION AND THE LOCAL EFFECTIVE DIMENSION
Understanding the role of the local effective dimension in the context of generalization requires rigorous relationship to be defined. We demonstrate this relationship through the generalization error, bounded by the local effective dimension.
4.1 GENERALIZATION ERROR BOUND
Consider machine learning models described by stochastic maps, parameterized by some 0 θ and a loss function as a mapping é P())) x P())) + R where P())) denotes the set of distributions on y. The following regularity assumption on the model Me (x(s)0)) : +) is assumed:
e 0 p(::0)
(5)
is -I-Lipschitz continuous w.r.t. the supremum norm

---

Under review as a conference paper at ICLR 2023
θ satisfying equation 5 such that F(O) has full rank for all 8 E θ, and | log F(O) I A for some A 2 O and all 0 E H. Furthermore, let E P(Y) x P()) I-B/2BBB for B 0 be loss function that is Lipschitz continuous with constant M2 in the first argument with respect to the total variation distance. Then, there exists dimensional constant ca such that for 0 O N, 2xx log
Theorem 4.1. Let = and consider statistical model Me. {p(-..; :
y
11. and 1/ V we have
4Mc
Angre Knn
exp (-
16T 16 log
P
sup (0+)
IR(0) (O)
S ca(1 +
B
where M M2 Kn,ry is defined in equation 2 and dn is the local effective dimension dn, (MB.())))
Theorem assumes that the loss function is Lipschitz continuous. This excludes some popular loss functions such as the relative entropy. Hence, in Appendix C functions that are log-Lipschite
we extend Theorem 4.1 to include loss
4.2 PROOF OF THEOREM
Let (0", (r) denote the number of boxes of side length r required to cover the set B,(0*) the length being measured with respect to the metric (0")
Lemma 4.2. Under the assumption of Theorem 4.1
we have for any & (0,
nc²
P sup
IR(0) (00)))R,(00) (B-)
[n) 2 26) s (2
4M
exp
2B²
Proof. If we replace the full parameter space, θ, by the relevant reduced space, B_ (6')), ), the proof of this lemma follows directly from (Abbas et al.) [2021] Lemma 2 in the Supplementary Information) we set a 1.
Lemma 4.3, Under the assumption of Theorem 4.1 there exists dimensional constant such that
(B))
s ca(l + eA)a Kn.
Proof. If we choose θ Bi (0*) instead of [-1, 1] we can then rescale (0*) - B, (0*), F(0) + F(ed), 1//n-+/ (01-+/(ee/nng 1/(e/n), and r + r/e In other words, the number of balls of radius needed to cover B, (0*) is equal to the number of balls of radius r/c needed to cover Bi (0*). Then, constants ea and & exist such that
NB) (0) = ()8((0)(r/4)
é Vi S Vdet (ida + pe F(ed) do
$ ca((1 + caed)a
2² Ve Saloo Vdet (ida + Z = do
= ca(1 + cded)a
Hence, choosing (e/r)² Kn.y gives
(9*)
< ca(1 + cdeA)a
Kn.
dnares
which proves the assertion of the lemma.
'We say that a function f is log- Lipsciise with constant Lf ff)) - f(v)l S L| log(e + 1/1x v()-
'Recall that by assumption of Theorem 4.1 have > 1/v7.
7

---

Under review as a conference paper at ICLR 2023
Thanks to Lemmas 4.2 and 4.3 we can deduce Theorem 4.1 For & = 4Mc/ Ven. find
16T log
sup (EB.18")
[R(0)) - (n) 2 4Me/ Vinn
- 22NB.100) (e/ (e/n))n)) exp
B2y
Ange
cxp (-
16x2/222 16 M222 log
I 20al1 + cA)a
Knn
B2y
which completes the proof]]
4.3 REMARKS ON THE GENERALIZATION ERROR BOUND
Ideally, the generalization bound from equation 4.1 should be non-vacuous. This occurs if the right- hand side is smaller than one, equivalently, when the logarithm of the right-hand side is negative. Table 2 demonstrates that a choice for 7 E 22x log 1] such that the bound remains non-vacuous, is n reasonable in practical settings where we set 7 = 0.003, but could become vacuous in deeper regimes. For more details, see Appendix
EMPIRICAL RESULTS
In this section, we perform experiments verify whether the local effective dimension captures the true behaviour of generalization error in various regimes. We use standard fully-connected feedforward neural networks with two hidden layers and vary the model size by altering the number of neurons in the hidden layers. All training was conducted with batched stochastic gradient descent, with experimental setups identical to those of (Liang et al. 2019) The details can be found in Appendix B
We consider both shallow and deep regimes by training models on MNIST and CIFARTO data sets, with the latter requiring far more parameters for the training to converge to zero error. Within these regimes, we conduct two experiments respectively: first, we incrementally increase the model size, train to zero error and calculate the local effective dimension, along with the generalization error; second, we replicate the experiment from (Zhang et al. (021) by fixing the model size and randomizing the training labels by an increasing proportion, training the local effective dimension and generalization error. In all calculations, we perform simulations using the K-FAC approximation of the Fisher information from (Martens & Grosse 2015). K-FAC crucially allows computation of the local effective dimension in very large parameter spaces and we further exploit the block structure of this approximation for computation of the eigenvalues of the Fisher information matrix (Goorge 2021).
error and calculating
Regardless of the regime and particular experiment conducted, the local effective dimension seems to move in line with the generalization error. In Figures [(a) and 2(a) we see this for an increasing model size shown on the horizontal axes (with notably much larger models used to learn the CIFAR10 data set). As the models get larger, they are able to perform better on the learning task at hand and their generalization error declines accordingly, as does the (normalized) local effective dimension. The error bars represent the standard deviation around the mean of 10 independent training runs A lower normalized local effective dimension as the model size increases, intuitively implics increasing redundancy, also suggested in (Frankle & Carbin 2018), and motivates pruning techniques (Karnin 1990).
fix the model size to d x 10 and d = 107 respectively. Here, the horizontal axis marks the level at which the labels of the training data have been randomized. We begin 20% randomization 100% in increments of 20%. At all points, we train to zero training loss or terminate at 600 epochs and plot the resulting normalized local effective dimension and generalization error. Naturally, the generalization performance worsens as we randomize more labels since the network is fitting more and more noise that has been artificially introduced. Interestingly, the local effective dimension captures this behaviour too increasing with the generalization error-
In Figures 1(b) and 2(b)
The full rank assumption the Fisher information matrix Theorem 4.1 can he relaxed following the
ideas from (Abhas et al, 202T Remark 2).
We include results with the ADAM optimiser in the appendix.
8

---

Under review as a conference paper at ICLR 2023
0.40
0102)
dimarneinm
-0.00
normelln mnnde effectivee dimerrss iimeresionn
gemetallizttoon eTror
11422
01288
0.41
normalloos womallorrrr.... edffection
generuliatoon
0440
-0.094
0924
10.40
00.80
0122
-0.80
0825
0125)
0.00
20030
30000
42000
1000
5000
7000
5000
3000
100000
model
(#f parameters)]
percentage of randoniized labels
(a) Model size
(b) Random labels
Figure 1: MNIST (a) Normalized local effective dimension and generalization error plotted different model sizes (standard feedforward networks with two hidden layers and varying number of neurons). The parameter n. is fixed to equal the size of the training set, i.e. 60000. (b) Normalized local effective dimension and generalization error over different percentages of randomized labels on the training data. Here, the model size fixed to d 10
0.30
000
1131
normalired effortive dimoension
0.75
generaataation arvor
C70
0.0
geerslization error
0.26
1.30
000
0.20
6425
fired offivee
11:01
6000
0.6
6.75
0.5
045
D30
30 31
model size (# parameters)
percentage of randomiaed labels
(a) Model size
(b) Random labels
Figure 2: CIFARIO (a) Normalized local effective dimension and generalization error plotted over different model sizes. The number of parameters required to train CIFARIO far greater than the number of training samples (n = 50000). We observe that the local effective dimension moves in line with the declining generalization error as the model is made larger. (b) Normalized local effective dimension and generalization error over different percentages of randomized labels on the training data. Here, the model size is fixed to Rs 107.
indicating that more and more parameters need to become "active" to fit this noise. This result is independent of the regime, deep or shallow.
DISCUSSION
Whilst the search for a good capacity measure continues, we believe that the local effective dimension serves as a promising candidate. Besides being able correlate with the generalization error in different experiments, the local effective dimension incorporates data, training and does not rest on unrealistic assumptions. It's intuitive interpretation as measure of redundancy in a model, along with proof of generalization error bound, suggests that the local effective dimension can explain the performance of machine learning models in various regimes. Investigation into the tightness of the generalization bound, in particular for specific model architectures and in the deep learning regime (where bounds are typically vacuous), would be beneficial in further understanding the local effective dimension's 's connection to generalization. Additionally, empirical analyses involving bigger models, different data sets and other training techniques/optimnzzz could shed more light on the practical usefulness of this promising capacity measure.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Amira Abbas, David Sutter, Christa Zoufal, Aurelien Lucchi, Alessio Figalli, and Stefan Woemnr: The power of quantum neural networks. Nature Computatiional Science, (0) 409, 2021. doi: 10. - 00084
(028/44358-0011-00033 ott.://00000//ttttta//////ooo... http://0.....r11.111111000110010
Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep representations. Journal of Machine Learning Research, 19(50)11334, 2018. URL http://
html
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 2009.
Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire. Boosting the margin: expla- nation for the effectiveness voting methods. The Annals of Statistics, 26(5):1631 1686, 1998. doi: /1///o//1024611552 URL http://o..ooo/ /tt.::ccppe//o....rrr.1.11////// 1ttp.////000111///////4444111110
Peter L Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normaaizeed margin bounds for neural networks. In Advances in Neural Information Processing Systems 30, pp. 6240 6249. Curran Associates, Inc., 2017. URL htttp://paapes.niiss.oo
7204 -pw.taaa--------leeeee---------e http:/-mmmmmiiiiiaaaaaaaooooaaao -ow.eue--------eeeeeeeeeeeeaaao-
pdf
Mikhail Belkin, Daniel Hsu, Siyuan Ma. and Soumik Mandal. Reconciling modern machine-
learning practice and the classical 201 trade-off. Proceedings of the National
Academy of Sciences, 116632):5884- 2019. doi: 10. 10.1073/pnas. 19030701 10.00///a...00000001111..1 URL (tI.ttps/
www pww.ppasss....... org/ htt////i//aab/// wtt.a///...111111111 1903070116
Oksana Berezniuk, Alessio Figalli, Raffaele Ghigliazza, and Kharen Musaelian, scale-dependent
notion of effective dimension, 2020. httpss/t: wwtp 10872
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. A survey of model compression and acceleration for deep neural networks, 2017. URL UtR.httppe///arri....oooa///////
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. Model compression and accelcration for deep neural networks: The principles, progress, and challenges. IEEE Signal Processing Magazine, 35 (1):126-136, 2018.
doi: 10. 00.11999S...001.27666660
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley Interscience, 2006. ISBN 047124195 doi: 10.1002/047174882XX
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 1019-1028, PMLR, 06-11 Aug 2017. URL
V70
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks, 2018. https::t:: org/ abs/ /103..1133..00 03635
B. Roy Frieden. Science from Fisher Information: A Unification. Cambridge University Press, 2004. doi: 10. 10.10177/CB097785116666
Thomas George. NNGeometry: Easy and Fast Fisher Information Matrices and Neural Tangent Kernels in PyTorch. Zenudo, February 2021. doi:
URL https
//doi.org/10.555 001555281222no .ato:odd..53359 4532597
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http:
/www.deepleernniggbob.
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruming. trained quantization and Huffman coding, 2015. URL https: : h/tp///xx.vv////// abs/1510 00149
10

---

Under review as a conference paper at ICLR 2023
Geoffrey E. Hinton and Drew Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the Sixth Annual Conference on Computational Learning Theory, COLT 93, pp. 5-13, 1993. ISBN 0897916115. doi: 10. 10.1145516633044166306 URL https: /ww. www.doo...g.ooooooooooooooooe. 10t.11115111000000
68306.
Sepp Hochreiter and Jürgen Schmidhuber. Flat Minima. Neural Computation, 9(1):1-42.011 1997.
ISSN 0899-7667. doi: 10. 1662necc. 1997.9.1.1 URL https:///ol /
1997. 1.1
Sean B. Holden and Mahesan Niranjan. On the practical upplicability of VC dimension bounds. Neural Computation, (66::1265-1288 1995. doi: 10.1162/neco. 1995.7.6. 1265..
Yiding Jiang. Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where find them, 2019. URL https::/aaxxiiii org/abs
1912. 02178
E.D. Karmin. A simple procedure for pruning brop-proonnttiion trained neural networks. IEEE Transactions on Neural Networks, 1(2):239-22) 242, 1990. doi: 10.1 109/79..202..6
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima, 2016. URL
https://arxiv. orgg 609, 04836
Frederik Kunstner, Philipp Hennig, and Lukas Balles. Limitations of the empirical Fisher approximation for natural gradient descent. In Advances in Neural Information Processing Systems 32, pp. 4166-4167. 2019. Sttp://papers nips. cc/ paper/
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-Rat metric, geometry, and complexity of neural networks. volume 89 of Proceedings of Machine Learning Research. pp. 888-888888 896. PMLR, 16-18 Apr 2019. URL http:tttppppcceeeeeee mwlpgssmmlr.... mlr. www..r.ressvvvv
liangl 9a.
Zhibin Liao, Tom Drummond, Ian Reid, and Gustavo Carneiro. Approximate fisher information matrix to characterise the training of deep neural networks. JEEE Transactions Pattern Analysis and Machine Intelligence, PP:1-1, 10 2018. doi: 2811099TPA
David JC MacKay. Bayesian interpolation. Neural computation, 4(3):415 447, 1992.
Wesley Maddox, Gregory Benton, and Andrew Gordon Wilson. Rethinking parameter counting in deep models: Effective dimensionality revisited. arXiv preprint arXiv:2003.02133, 2020.
James Martens and Roger Grosse. Optimizing neural networks with Kronecker-factored approximate curvature. In Proceedings of the 32nd International Conference International Conference 2015. doi:
Machine Learning Volume 37, pp.
Pavlo Molchanov, Arun Mallya, Stephen Tyree, Iuri Frosio, and Jan Kautz. Importance estimation for neural network pruning. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11256- 11264, 2019. doi: 10.1109/CVPR.2019.0111
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. volume 40 of Proceedings of Machine Learning Research, pp. 03-06.0 Jul 2015. PMLR. URL htllattp://prcceedinntt m http:://pp.peeeennn.oo.eeeeeeees html
Paris, France,
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in neural information processing systems, pp. 5947-5956. 2017a. doi: 3.555/3295222.32953333
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian approach to spectrally margin bounds for neural networks, 2017b. URL https: ///axiv/ brg//bbs/1077 09564
11

---

Under review as a conference paper at ICLR 2023
Adam Paszke al. Pytorch: An imperative style, high-performance deep learning li-
brary. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. 8035.
Curran Associates, Inc., 2019. URL http::/pppprs..euriiiao..
9015
ibrary.
pdf
Jeffrey Pennington and Pratik Worah. The spectrum of the fisher information matrix mitrixooaisnggllehhdedeee
layer neural network. 2018. htt.hhtp://ppeoe cs.cc..c............. http:.hccc....eeee///aaaaaaaaa/a pdf
J. Rissanen. Fisher information and stochastic complexity. IEEE Transactions on Information Theory, 42(1))40-47, 1996. doi: 00.1109/8,44177
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 IEEE Information Theory Workshop (ITW), pp. 1-5, 2015. doi: 10.1 10.10999...2155773311699
Koji Tsuda, Shotaro Akaho, Motoaki Kawanabe, and Klaus-Robert Müller. Asymptotic properties of the Fisher kernel. Neural Comput., 16(1):115-137, jan 2004, ISSN 0899-7667. doi: 10.1162/ 08997660460734022,
Frederick Tung and Greg Mori. Deep neural network compression by in-parallel muuiingquuatizaatnnn IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(3):568 579, 2020. doi:
10.1109/TPAMI.200 28886192.
V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264-20) 280, 1971. doi: 10.1137/1 16025. /tt.:/pp:://o...rr//11111133/
Vladimir Vapnik, Esther Levin, and Yann Le Cun. Measuring the VC-dimension of learning machine. Neural computation, 6(5):851-876, 1994. doi: (ac1162/ncco.1994...5522
Huan Wang, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. Identiffyng generalization properties in neural networks, 2018. URL
Simon Wiedemann, Klaus-Rober Müller, and Wojciech Samek. Compact and computationally efficient representation of deep neural networks. IEEE Transactions on Neural Networks and Learning Systems, 31(3)7772-785, 2020. doi:
Seul-Ki Yeom, Philipp Seegerer, Sebastian Lapuschkin, Alexander Binder, Simon Wiedemann, Klaus-Robert Müller, and Wojeiech Samek. Pruning by explaining: A novel criterion for deep neural network pruning. Pattern Recognition, 115:107899, 2021. ISSN 0031-3203. doi:
http:///www....0../oo/aaooooogop 20711 URL httpt:tt:///tt...t. ssceoee//artccee/1//500122222222
8c encedi rect. com/
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 7085-7094. PMLR, 09-15 Jun 2019. URL httpt::t// https::/pprcceeiinggs mlr press/v97 http///7/yyii 1 httml
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commun, ACM, 64(3):107-115, feb 2021. ISSN 0001-0782, doi: 10. 10.1145/344677, URL http::::://o.....11.11..11
A BENEFITS OF THE LOCAL EFFECTIVE DIMENSION
When deciding what a good measure of capacity for a model, in particular for deep neural networks which are notoriously difficult to understand in generalization context, it is helpful to check whether the capacity measure satisfies certain criteria which we highlight in Table [ The first criterion is whether the measure be mathematically related to the generalization error via an upper bound. This is the main contribution of our work, where we essentially show that the local effective dimension indeed bound the generalization error. The question of whether one
12

---

Under review as a conference paper at ICLR 2023
obtain tighter generalization bounds using the effective dimension, for specific models, is left for future research. However, there are several interesting pieces work that could be relevant for this direction, such as (Pennington & Worah 2018) who investigate the spectrum of the Fisher information for a single layer neural network with infinite width. Since the effective dimension depends largely the eigenvalues of the Fisher matrix, this would be convenient place start this investigation. Additionally, the work in (Pennington & Worah, 2018) shows that a single linear layer network produces Fisher information spectrum which converges in the infinite width limit. In this setting, the generalization bound based on the effective dimension reduces to something quite trivial which depends primarily on n, since the number of data determines how many eigenvalues are counted in the local effective dimension. We hope that future studies can improve the bound we present this work, as we do not yet explore any optimality results.
distribution Marchenko-Pasee
The second criterion for well-proposed capacity measure tries to address whether the generalization bound using the capacity measure is actually good in practice, i.e., that the measure correlates with the generalization eπror in various experimental setups, such as (Zhang al. 2021). Through our numerical experiments in Section
we answer this with an affirmative answer.
Another crucial property for capacity is scale invariance, which corresponds to the measure being insensitive to inconsequential transformations of the model, such as multiplying a neural network's weights by constant. Since the local effective dimension is function of the Fisher information, which is inherently scale invariant, this requirement is naturally accounted for in the local effective dimension.
A good capacity measure should also account for data and training dependence, i.e. the fact that data is drawn from distribution and one imposes learning algorithm. Once again, the Fisher information incorporates the data distribution, and the purpose of the localization of the effective dimension to account for training dependence.
A capacity measure should also be realistic in the sense that it should allow for finite data, which always the case in practice. The local effective dimension not only allows for finite data, but is structured for this realistic purpose to include the amount of data available as resolution parameter. This creates a beautiful operational meaning for the local ED that depends on the amount of data one has in practice.
Lastly, capacity measure should be computationally efficient to evaluate (in polynomial time in the number of data). Thanks to various approximations of the Fisher information, this too is possible for the local effective dimension and is explained in Appendix F..
B PROOF OF PROPOSITION 3.2
We denote the maximal rank of F and F' by F and F', respectively, and define the function
f(t) = Ve / det (ida/ (Far ty F(0) + (1- F((O) do.
(6)
=:G
We consider a modified version of the effective dimension, defined as
dn.s(F) 2 log f(1
2 2oo f(0)
and
dn)(F')
+ 7' log Kn.
log Kn,y
The triangle inequality then gives (F) - (F')(F) (F)
+ (dn, (F)
dnn (d') dn (nn((F))
We next bound all the three terms. For the first and the last one, recall (Abbas et al. 2021, Supple- mentary Information, Section 2) that
2
(
Ve (
1
dn, (F) S ++
log
det(idu + F(0))d0)
log Kn,
13

---

Under review as a conference paper at ICLR 2023
and for A {0 :
log Ve / Vdee(F(o))ao).
(F) 2 +
log Kin,7
Recalling that
Ve / V det(ida + F(0))a0) --log -log
1
Ve So v det det(F(())dd)
}
((F) = max log
gives Idn,, (4²) dn, (F) -
(F=)
2x((F and (F") (Fn
It thus remains bound
log Ka.
log Mine
middle term in equation 7
To do so note that
llog f(1) log f(0)) < /
lf'(t) dt.
f(t)
We can bound the numerator of the integral
lf((t) E /
d
det(ida/ /ioiaa///nn /kn. Gt) d0
Ve
dt
Co.d | /F(() -F
s Ve
(((())
dA
F(0) V F(())
s Ca max
(8)
where the constant Cj depends on d,
-F and
F7 F'1-1
Using the fact that + (det A) concave on the space of Hermitian positive definite matrices gives
det (ida/ VFn,y + Gi) 2 det (ida/ /an. + G1) + t) det (ida/ /kn.y + Go) Go) td det (ida/ /Knn, + G1) + (1 -1) +)d det (ida/ Vhing + Go)
1/d
Hence we have f(t) 2 1a f(1) + (1 - f() Combining this with equation gives
log /(1) - log [(0) < Ca max deB
[(0)= F((O)
(df(1) (1 - f()) di dt +
(1o 1/2
< Ca max 9E8
V F(0) - V F'(0)
1/2 (1 f(2 dt
f*((I)
F(0) F'(0)
(F1) + f(1)
( ((())
< Ca max 9EB
Combining this with
dn,n(F) dn))(F))
llog f(1) - f(0)
Kn,7
almost completes the proof. The final thing to note is that
f(0) 1 ( det (ida/ Vting + v Fi(0)) ao 2 Vo / det (v (VF(()) do.
Ve and similarly for f(1).
14

---

Under review as a conference paper at ICLR 2023
C GENERALIZATION BOUND FOR LOG-LIPSCHITZ LOSS FUNCTIONS
In this appendix we prove a generalization of Theorem 4.1 where the loss function is assumed to be log-Lipschitz continuous instead of Lipschitz continuous.
Theorem C.1. Consider the same setting as in Theorem 4.1 with e (1/ 11. but the loss function hog-Lipschitz continuous with constant M2 in the first argument with respect to the total variation distance. Then
2Mc VKn,
Vin.y M2c
IP
sup (0+)
[R(0) (o)
log
e+
S ca(1 EA)a
2mM2e
log (et
Vin.
))
exp
Ko, B2
M2e
(9)
where M M1 M2 and Ka.y is defined equation
To prove Theorem C.I we need preparatory lemma. Lemma C.2. Under the assumption of Theorem
C.I we have for any & E (0, 1)
ng²
sup RR(0) - R.)) 2 (0*)
s 22NB.
exp
2B²
where r(g) defined as the unique value such that 2M log(e + Mar) E/2
Proof. Let r E P(X) and & & P(Y) denote the observed input and output distributions, respectively. Then using the log-Lipschitz assumption of the loss function, we find
[R(0:) - R(02)
Ena 01 - E.g (1 (2)
=
Enq [1 - (3)))))))))))))))
1
< M,E, (1
log e
(p(ylz;01)r(e -
plula (2)(())))
1
< M2 11p()) 01) p(y) 02) log e+
[p(v|2;01) - - 02)
< M2M1 ||0 82l1.c log c+
(10)
110 82
where the penultimate step uses that R e + log(e + 1/z) is monotone together with Hölder's s inequality. The final step follows from the Lipschitz continuity assumption of the model. Equivalently we see that
1
R. (0,) R., (02) < M2M, |10, 02 log (e 100
(11)
Oz
Combining equation
10 with equation 11 gives for S(0) = R(A) - (n(
1
[S(1)) - S(2)) < M, |00 0211oo log ee 110 021l
(12)
Assume that (6*) can be covered by is subsets B BR, i.. B.()") B1 U...U. Bg. Then. for any & > 0,
[S(O] 2 { = IP ÜÚ sup ((()
P
sup (0
<
sup #E
|S(O) 26). (13)
REN,
With the convention that if M, 0 M2 0.
15

---

Under review as a conference paper at ICLR 2023
where the inequality is due to the union bound.
Finally, let = (rr) and let BI...., Bk be balls of radius r centered at .y..... Ox covering (0*). Recalling that by assumption r(E) is such that 2M Mar log(e + Mar) E/2 find for all i ,
P sup |S(0] (50))22)) SP [S())] < 2 5 2
(14)
BEB.
To see this recall that since 10 0, S r, by definition of r and using the monotonicity of x +
log(e + 1/2), Inequality equation 12 implies [S( S(O,) - E/2. Hence, if ((O) 2 must
be that [5(0:)] 2 5- This in turn implies equation 14
To conclude, we apply Hoeffding's s inequality, which yields
P
[(())) 2
5) 2)
(IR(0)) R. (0,) 2
S 2exp
-n
(15)
2
2132
Combined with equation 3 we obtain
k
k
E
sup (0*)
|S(O)
_
sup |S(0) 26) OEB,
[S(0))
2
2
-
S (r) exp
2
where the second step uses equation 14 The final step follows from equation 15 and by recalling that
k = (r)..
Proof of Theorem Choosing r </ Win., implies
2.M M2
ee Von.
log
(16)
Viny
M2e
via the relation between r and & given in Lemma
C.2
Hence Lemma
C.2
implies
ng²
P
sup BEB.
RR(0) (0) 2
< (AA)B((0))
exp
Vkn,
2B²
n
< 2ca(1 + cA)d
Knn
exp
2B²
=ca((1 + eA)a
Kn.y
exp
2nM22
loo
(e+
Vin,7
2)
K B2
Mge
where the second step uses Lemma and the final step follows from equation
[6
D REMARKS ON THE GENERALIZATION ERROR BOUND
Lemma 4.2
implies that lim PSSupEEE, (0-) R(()) R. (0) 2 () = for & E (0, 1). As result, to ensure that the generalization bound in equation 4.1 is meaningful, the right-hand side must vanish as n + oc. This depends on the problem setting, particular, on the parameters e > 1/v and E 2xr log n 1]. There is some flexibility in choosing these parameters, with a "critical" scaling obtained if 211/ log(n)) 10 In the case where = O(1/n²) for < 1,, the generalization bound 2n log 1
gets vacuous for sufficiently large n., regardless of the choice of the constant 7 E
Ideally, the generalization bound from equation 4. should be non-vacuous, This occurs if the right- hand side smaller than one, or equivalently, when the logarithm of the right-hand side negative.
1'In this case, the eter y can control behaviour the generalization bound as n oc.
in the right-hand side of equation 4.1 balance each other and the hyperparam-
Recall that choosing 7 dependent n would conflict with the geometric interpretation of the effective
dimension (Berezniuk et al. 2020 Abhas (02T).
16

---

Under review as a conference paper at ICLR 2023
Table 2 demonstrates that choice for ? 2 log such that the bound remains non non-vacuous, reasonable in practical settings where we set y = 0.003. As a result, we plot the accompanying error bound En. the local effective dimension and the logarithm of the right-hand side of equation 4. which remains negative, for increasing values of n.
Table 2: Evaluation of the generalization bound equation 4.1 for feedforward neural network
trained on MNIST. The model sets d R 10 1/v/, CA.d 2vd. and B M - 1. Even = 0.003 such that the generalization bound non- vacuous, i.e., the RHS of equation 4.1 is < In fact, the log RHS of equation 4.1 is strongly negative, implying that the RHS is virtually zero. Following equation 4.1 1/n.
when setting e 1/vn. we can still
the error bound is given by
En = 4Me 2x log /1/2
4v 2n log
71
8V5
dayme
&n
log RHS of equation 4.1
5 10
23174
0.00132
-98507
10
25285
0.00068
91335
2 x 10"
27594
0.00034
-79921
x 10
31106
0.00014
-59307
10?
33933
0.00007
-40316
E EXPERIMENTAL SETUP
Here, we explain the models and techniques used for the experiments in this study. All models constituted fully-connected feedforward neural networks with leaky relu activation functions. We used 2 hidden layers for all architectures, but varied the number of neurons per layer depending on the experiment. Training was done with stochastic gradient descent, with batch sizes equal to 50. In the instances where the CIFAR10 data set used, we performed standard transformation of the data by normalizing and cropping from the center. For more details on this transformation, (Zhang al. 2021
E.1 INCREASING MODEL SIZE
In Figures ((a) and ((a) we train feedforward neural networks on the MNIST and CIFAR1O data sets respectively. In both cases, we plot the model size on the x-axis and incrementally increase the number neurons both hidden layers, thereby increasing
number of parameters the model. For MNIST, we do not need to train very large models to achieve zero training error, thus, we vary the number parameters from 2 x 10 to 10 On the other hand, for CIFAR10, 10, we train models with parameters ranging from 5 10a to 10T. In MNIST, the training and test split is 60000 and 10000 images respectively. For CIFARIO, it is 50000 and 10000.
We train every model for 200 epochs and plot the resulting generalization errors, approximated by the test error. We also plot the normalized local effective dimension for every model using the trained parameter set 8* For this,
= 6 104 (which is the size of both training sets) and set y 1.
In both Figures, we repeat the entire experiment 10 times with different parameter initialization and plot the average generalization error and average normalized local effective dimension trials, with error bars depicting 1 standard deviation above and below the mean values. As expected, the local effective dimension declines along with the generalization error in both shallow (MNIST) and deep (CIFAR10) regimes.
these 10
E.2 RANDOMIZATION EXPERIMENT
In Figures I(b) and 2(b) we train models on the MNIST and CIFARIO data sets respectively. In this experiment, both models are fixed to d z 10S for MNIST and z5 10 for CIFAR1O. What we vary the proportion of training labels that are replaced with random labels (as originally done in (Zhang eet al. 2021)). We begin by randomizing 20% of the training labels as shown on the x-axis. We train the models training emror terminate after 600 epochs and plot the resulting generalization
17

---

Under review as a conference paper at ICLR 2023
error and effective dimension. Thereafter, we increase the proportion of random labels in increments of 20%, until 100% randomization and plot the generalization error and normalized local effective dimension after training, each time.
This entire process is repeated 10 times with different parameter initialization and we plot the average generalization error and average normalized local effective dimension over increasing label randomization. Unsurprisingly, the generalization error increases as we increase the level of randomization since the network essentially learning to fit more and more noise and thus, does not generalize well. Interestingly, the local effective dimension moves in line with this trend and increases over increasing randomization too. This could be interpreted as the network requiring more and more parameters to forcefully fit the increasing noise levels that would not naturally occur. Thus, the local effective dimension captures the correct generalization behaviour, even in this artificial set. up where most capacity measures fail to explain generalization performance.
While in the case of noisy labels, deep neural networks seem to overfit regardless of how deep you make them, it is worthwhile to mention other progress in understanding deep learning through experiments aiming to probe the nature of overfitting. One particular analysis involves the study of memorization of overparameterized models which produces "double descent" curve rather than the traditional U-shaped risk curve (Belkin et al., 2019). The details of the double descent phenomenon are very subtle and depend several interrelating factors such as the distribution of data, the optimizer used (i.e. the trained parameters) and the notion of capacity employed. Given that the local effective dimension accounts for these factors through the nature of its definition and it is able to capture overfitting in an overparameterized regime induced through artificial noise in the labels, we postulate that the local effective dimension through training would also track the double descent risk curve accordingly. Thus far, we have conducted various experiments that calculate the local effective dimension after training is complete, but the measure should intuitively inform us about local information around any set of parameters. Thus, one could also extend the analysis to look at the local effective dimension throughout training, which should mirror the double descent phenomenon containing various regimes of under- and overfitting as in the work of (Maddox et al.) 2020) who employ a different notion of effective dimension.
E.3 ESTIMATING THE LOCAL EFFECTIVE DIMENSION
In all calculations involving the local effective dimension, there are two assumptions made. First, we use a fixed parameter set chosen after training to estimate the local effective dimension and assume it is a good approximation of the average of sampling in e-ball around 0". In other words, we ignore the integral over B,(**) ) in Definition 3.4 and simply use the trained parameter set to compute the local effective dimension. In Table 3 check the sensitivity of the local effective dimension by comparing this "midpoint" approximation to sampling in an e-ball around 0 and conclude that the approximation is sufficiently close and thus helps reduce computational time. We use the more efficient reformulation from Remark 3.3 to calculate the local effective dimension with multiple samples and take e 1/vn.
Table 3: Evaluation of the local effective dimension for feedforward neural network trained on CIFARIO with d 10 We plot values for the normalized local effective dimension d calculated with increasing samples from an e-ball around the trained 0", where = /n. The midpoint approximation uses the single 0* after training. For completeness, we include the unnormalized local effective dimension dn,,,e e and the average of the z0)) values generated from each sample as defined in equation
Samples
Midpoint
50
100
200
500
1000
0.21815588
0.21815937
0.21816021
0.21815975
0.218159262
0.21815838
21 2189499.62
2189534.66 6.68
2189543.14
2189538.55 53
2189533.61
2189524.72
Average of 2(8)
N/A
7407283.05
7407306.34
7407286.62
7407213.06
7407150.42
The second assumption made is that the Fisher information matrix can be approximated by the empirical Fisher information matrix. From (Liao et al. 2018). we acknowledge that this assumption does not always necessarily hold. Thus, the continuity statement from Proposition 3.2 becomes
18

---

Under review as a conference paper at ICLR 2023
relevant ensure errors introduced by the estimate of the empirical Fisher do not strongly propagate in the calculation of the local effective dimension.
Through the empirical Fisher information assumption, further exploit work done in (Martens & Grosse 2015) and use the Coonecker-Factores Approximation (K-FAC) Fisher matrix in the estimation of the effective dimension. The K-FAC Fisher allows to estimate the eigenvalues of the empirical Fisher information much more efficiently for large models. We slightly extend the PyTorch (Paszke et al.) 2019) implementation developed in (George 2021). We refer the interested reader to (Martens & Grosse 2015) for more details. The K-FAC estimate constitutes several block matrices which comprise diagonal block estimate of the empirical Fisher estimate. The block matrices relate to the hidden layers used in a neural network model. Conveniently, these block matrices can be further factorized into tensor product of two smaller matrices. Thus, to calculate the eigenvalues of the K-FAC Fisher, it suffices to compute the eigenvalues of the block matrices, and thereby take advantage their tensor decomposition. We extend the PyTorch K-FAC implementation from (George 2021) to include a function that computes all the eigenvalues. Thereafter, the estimation of the local effective dimension follows from equation Due to these approximations and the code implementation in (George 2021).
would like highlight that computational bottleneck lies solely with training the model when d is very large. The memory and time overhead for computing the local effective dimension with the K-FAC Fisher is highly efficient and could, for example, run on a laptop with modest memory for a model with d = 10000000 in just few minutes.
E.4 ADDITIONAL EXPERIMENTS
In order to validate the robustness our results with different optimizers, we have conducted the same experiment as in Figure 2 using the ADAM optimizer. As was the case with stochastic gradient descent, we see that the relationship between generalization and the local (normalized) effective dimension still holds.
000
1021
HOSEL aarrealleedd Mizedd eeee dineeetoon
graeralzation ervor
012
072
1013
011
0.84
10
goneco.icntton
100 TOCTTA Good elleeti
03
19
model size (# parameters)
percentapo of randomized labels
(a) Model size
(b) Random labels
Figure 3: CIFARIO with ADAM (a) Normalized local effective dimension and generalization error plotted over different model sizes. The number of parameters required to train CIFAR (0 is far greater than the number of training samples (n 50000). We observe that the local effective dimension moves in line with the declining generalization error the model is made larger, even with training using a different optimizer (ADAM as opposed to SGD in Figure 3 (b) Normalized local effective dimension and generalization error different percentages of randomized labels on the training data. Here, the model size is fixed to d Rs 10" and training using the ADAM optimizer.
19


Reviews:
[{"review_id": "ZIw5B4v64c", "reviewer": "Reviewer_x2eo", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose \"local effective dimension\" (LED) as a measure of the capacity of a machine learning model. They show that it appears to correlate with generalization error on standard data sets and they prove that it bounds the generalization error. They compare their proposed measure to a number of others, including VC-dimension and Rademacher complexity.", "summary_of_the_review": "The paper is very promising in terms of nearly all aspects. It addresses an important topic, it proposes a reasonable candidate measure, it contains substantial technical justification for the measure, and it empirically evaluates the performance of the measure. However, the empirical evaluation is sparse, and readers have insufficient evidence to conclude whether the measure is worth pursuing. The authors are clearly in the best position to provide that evidence, but the current paper does not provide it. The paper would be acceptable given a far more extensive empirical evaluation (and assuming, of course, that the results of that evaluation continue to show the measure to be effective).", "strength_and_weaknesses": "\\+ The review of prior work is highly readable and interesting. It does a good job of categorizing and describing the intuitions behind prior work, rather than merely providing a large list of papers.\n\n\\+ The paper is well-written and clear.\n\n– Section 2 is confusing, in parts. The discussion at the beginning would be clearer if the authors provided a better description of what is meant by an \"estimate of error.\"  Also, the discussion of Fisher information in Section 2.2 is completely unmotivated.\n\n– The concept of effective dimension would appear to require knowledge of the distribution of the data. For example, consider a simple logistic regression model with k+1 parameters, where k is the number of predictor variables. If each variable X_2...X_k are copies of X_1, then the potential for the model to fit an arbitrary target variable Y is much smaller than if X_2...X_k are independent.\n\n– The results in Figure 2 are less impressive than they might appear. What the graphs show clearly is that LED decreases with the number of parameters and increases with the percentage of randomized labels (as does generalization error). By adjusting scales, LED has been made to match the beginning and end points of the generalization error curve. To their credit, the authors don't over-interpret this evidence (\"...the local effective dimension seems to move in line with the generalization error.\" and \"Whilst the search for a good capacity measure continues, we believe that the local effective dimension serves as a promising candidate.\"). However, some readers may not be so thoughtful.\n\n– The authors provide only preliminary empirical evidence of the utility of LED. The experiments that are provided are interesting. However, the results are given for only two data sets and only one type of model and training method. Sample size is not varied, nor are characteristics of the data (e.g., number of variables or level of randomization of the predictor variables).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EUSOEpGrMLl", "reviewer": "Reviewer_c3zn", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "A complexity measure called the local effective dimension is proposed for bounding the generalization error of a supervised learning model. Local effective dimension is related to the Fisher information matrix constrained to a particular region of parameter space, with that parameter region intended to capture the fact that only a certain area of parameter space is explored during training. A list of desirable properties of generalization bounds is presented and it is claimed that local effective dimension satisfies all the desirable properties, unlike previously available generalization theory methodologies.  Theoretical results are presented showing that local effective dimension provides a bound on generalization error. Experimental results using MNIST and CIFAR10 show that local effective dimension empirically correlates with generalization error. ", "summary_of_the_review": "A generalization measure is presented which is related to Fisher information and which appears to correlate with test error empirically, given some neural net experiments with image data. However, numerous misstatements are made about VC theory, the tightness of the bounds presented is unclear and the empirical results are not well benchmarked.", "strength_and_weaknesses": "The writing is reasonably clear, for the most part. This is certainly a strength of the paper.\n\nMy expertise is not primarily in learning theory although I did publish a little bit on learning theory early in my career, so I know VC dimension better than some of the more recent competing generalization measures the paper discusses. It concerns me greatly that there are several statements regarding VC theory (in Table 1 with the x's and checks and in the text) that are just flatly wrong.\n\n1) Table 1 claims VC dimension is not \"scale invariant\" and describes scale invariance as being insensitive to inconsequential transformations such as multiplying a neural net's weights by a constant. Bounds on the VC dimension of a neural net with a given architecture can be obtained which hold for the entire class of functions implementable by any choice of weights for the architecture, so I fail to see how VC dimension in any sense fails to be \"scale invariant\".\n\n2) Table 1 claims VC dimension is not data dependent, but there is a related measure, VC entropy, which depends on the expected number of dichotomies for a given input distribution (see e.g. https://www.shivani-agarwal.net/Teaching/E0370/Aug-2011/Lectures/3.pdf)  so the VC framework is in fact capable of taking into account data distributions.\n\n3) Page 2 and Table 1 both claim VC dimension assumes access to infinite data. I don't understand this claim at all , but it is simply wrong. VC theory provides a generalization bound for a given function class and a given finite training sample size N. It may indeed tend to be a loose bound when N is not very large, but there is no meaningful sense in which it assumes access to infinite data.\n\n4) Table 1 claims VC dimension does not provide \"efficient evaluation\", yet there are well known bounds on the VC dimension of neural nets as a function of hidden units and connectivity which are trivial to compute, so this claim is not correct, either.\n\nTo be honest, I did not have time to go through every line of the derivation of local effective dimension in this paper very carefully, but given the volume of incorrect statements about VC dimension here, I do not have high confidence in the correctness of the core results of the paper.\n\nMy other concerns are as follows:\n\n1) The experimental results merely show that local effective dimension correlates with test error. They do appear to do any benchmarking, i.e., they do not show that it correlates with test error better than competing methods .\n\n2) The discussion section says it would be beneficial to investigate the tightness of the bounds, conceding that no such investigations of tightness are presented here. It's hard to judge the significance of the results without any such measure of tightness.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AQWsivSjQZg", "reviewer": "Reviewer_Ec2u", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to analyze generalization via a notion called local effective dimension, which captures the local properties of a function class. The notion of the local effective dimension is derived from the previous notion of the global effective dimension, and the authors try to generalize the global notion into a local version. As the authors claimed, the new local version has some interesting benefits, such as being algorithm-dependent. The authors finally validate the local effective dimension both theoretically and empirically.\n\nAlthough the whole idea is interesting, I feel puzzled by the theoretical part (see weaknesses). Maybe I missed some details, and the authors can point them out. I do not mind increasing my ratings if these concerns are answered properly. \n\n", "summary_of_the_review": "It would be nice to see the author response on the correctness of the paper. ", "strength_and_weaknesses": "Strength:\n1. The authors propose a new measure called the local effective dimension. The new notion has some interesting properties, e.g., algorithm-dependent. \n2. The authors validate the new notion empirically and find that it works well in practice. \n3. This paper considers a very important topic generalization. \n\nWeakness:\n1. [Major concern]  Maybe I lose some details. I am not sure that the generalization bound holds. In this paper, the local version means that the bounds are derived around $\\theta^*$. Although the authors claim that $\\theta^*$ is a *fixed* parameter, in practice, it is usually the trained parameter. Therefore, $\\theta^*$ is data- and algorithm-dependent and therefore is related to the training set. \nSo, when generalizing the notion from the global version to the local version, some arguments may dramatically fail due to the dependency of $\\theta^*$. For example, in Lemma 4.2, the authors use covering number-type techniques, but it may not work around the trained parameter $\\theta^*$ (because the reference point is all around $\\theta^*$ and therefore, one cannot apply Hoeffding). Could the author explain more about that?\n\n2. In the experiment, the authors show that the local effective dimension is correlated to generalization error. However, the theoretical results seem to imply that the local effective dimension is on a power exponent. I am not sure that this experiment can validate the theorem.\n\n3. Since there is a sharpness term in estimating effective dimension. It seems that the sharpness term cannot be directly derived in practice. Did the authors consider the estimation error on the sharpness when deriving the bound?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9m9Qw-_g06", "reviewer": "Reviewer_g1fU", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a new capacity measure for characterizing the generalization called \"global effective dimension\". \n\nThe definition is based on Fisher information. The authors also show that this measure can provide the error of uniform convergence.", "summary_of_the_review": "This paper presents a new notion for characterizing the error of uniform convergence. The numerical results show that unlike VC dimension and Radamacher complexity this measure can correlate well with the generalization error. The main issue with the paper is that there is not intuitive explanation of this measure. Also, its connections with other notions such as VC dimension and Radamacher complexity is not clear.", "strength_and_weaknesses": "Questions:\n\n1- In the definition of the Fisher Information, is the expectation over the data generating distribution? it is not very clear from the paper. \n\n2- The definition of the effective dimension, there are lots of integrals. What are the necessary and sufficient conditions for the existence of the integrals?\n\n3- In the case of deterministic classifiers, for instance VC classes for binary classification, how can we define the effective dimension?\n\n4- Why is the Lebesgue msr chosen as the base measure for measuring the volume? \n\n5- The authors should provide more intuition behind their definition.\n\n6- what is the connection of the effective dimension to other well-known measures such as Radamacher complexity and VC dimension? \n\n7- The authors miss an important result on the uniform convergence: \n\n [1] Uniform convergence may be unable to explain generalization in deep learning Vaishnavh Nagarajan, J. Zico Kolter\n\nIt is interesting to discuss the counter examples in [1] in your paper.\n\n8- What are some examples for which we can theoretically find the effective dimension?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject