Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms
Authors: Rayna Andreeva
Benjamin Dupuis
Rik Sarkar
Tolga Birdal
Umut Simsekli
Venue: NeurIPS 2024 poster (2024)
Keywords: Generalization bounds
persistent homology
metric space magnitude
deep neural networks
Primary area: learning_theory
TL;DR: We prove new topology-inspired generalization bounds and perform extensive experiments to test the introduced quantities.

Abstract: We present a novel set of rigorous and computationally efficient topology-based complexity notions that exhibit a strong correlation with the generalization gap in modern deep neural networks (DNNs). DNNs show remarkable generalization properties, yet the source of these capabilities remains elusive, defying the established statistical learning theory. Recent studies have revealed that properties of training trajectories can be indicative of generalization. Building on this insight, state-of-the-art methods have leveraged the topology of these trajectories, particularly their fractal dimension, to quantify generalization. Most existing works compute this quantity by assuming continuous- or infinite-time training dynamics, complicating the development of practical estimators capable of accurately predicting generalization without access to test data. In this paper, we respect the discrete-time nature of training trajectories and investigate the underlying topological quantities that can be amenable to topological data analysis tools. This leads to a new family of reliable topological complexity measures that provably bound the generalization error, eliminating the need for restrictive geometric assumptions. These measures are computationally friendly, enabling us to propose simple yet effective algorithms for computing generalization indices. Moreover, our flexible framework can be extended to different domains, tasks, and architectures. Our experimental results demonstrate that our new complexity measures exhibit a strong correlation with generalization error in industry-standard architectures such as transformers and deep graph networks. Our approach consistently outperforms existing topological bounds across a wide range of datasets, models, and optimizers, highlighting the practical relevance and effectiveness of our complexity measures.

Topological Generalization Bounds for Cessrrete-Time Stochastic Optimization Algorithms
Rayna Andreeva" !
Benjamin Dupuis Rik Sarkar', Tolga Birdal' Umut Şimşeklit22
School of Informatics, University of Edinburgh, UK 2 INRIA, France
3 CNRS, Ecole Normale Supérieure PSL. Research University, France Department of Computing, Imperial College London, UK
indicate equal contributions.
Abstract
We present a novel of rigorous and computationally efficient topology-based complexity notions that exhibit a strong correlation with the generalization gap in modern deep neural networks (DNNs). DNNs show remarkable generalization properties, yet the source of these capabilities remains elusive, defying the estab- lished statistical learning theory. Recent studies have revealed that properties of training trajectories can be indicative of generalization. Building this insight, state-of-the-ar methods have leveraged the topology of these trajectories, partie- ularly their fractal dimension, to quantify generalization. Most existing works compute this quantity by assuming continuous- or infinite-time training dynam- ics, complicating the development of practical estimators capable of accurately predicting generalization without access to test data. In this paper, we respect the discrete- timet nature of training trajectories and investigate the underlying topologi- cal quantities that can be amenable to topological data analysis tools. This leads new family of reliable topological complexity measures that provably bound the generalization error, eliminating the need for restrictive geometric assumptions. These measures computationally friendly, enabling effective algorithms for computing generalization indices. Moreover, our flexible framework can be extended different domains, tasks, and architectures. Our perimental results demonstrate that our new complexity measures correlate highly with generalization error in industry-standare architectures such as transformers and deep graph networks, Our approach consistently outperforms existing topolog- ical bounds across wide range of datasets, models, and optimizers, highlighting the practical relevance and effectiveness of our complexity measures.
propose simple yet
Introduction
Generalization, hallmark model efficacy, is one the most fundamental attributes for certifying any machine learning model. Modern deep neural networks (DNN) display remarkable generalization
abilities that defy the current wisdom of machine learning (ML) theory [85 86). The notion can be formalized through the risk minimization problem, which consists of minimizing the function:
R(w) = Ezan, [f( [)],
(1)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

P.. 10
Ps, = 10-4
00
fee www surdaad Kosld
4in2
12 10"
11.1
dare
PAlaaiV tour))
Por
01A030
Gat
dini
(a) MDS Trajectory Embeddings
(b) Distance Matrices of Trajectories
(c) Our Topological Generalization Measures
Figure I: We devise novel class of complexity measures that capture the topological properties of discrete training trajectories. These generalization bounds correlate highly with the test performance for a variety of deep networks, data domains and datasets. Figure shows different trajectories (a)
embedded using multi dilti-dimensooall scaling based on the distance-matrices matrices (b) computed using either
the Euclidean distance (Il ll2) between weights as in [IO] or via the loss- loss-induced pseudo-metric (ps)
as in [21]. (c) plots the average granulated Kendall coefficients for two of our generalization measures
,E,, and PMag( /n)) in comparison the aate-of-theearr persistent homology dimensions (TO) 21
for a range models, datasets, and domains, revealing significant gains and practical relevance.
where = Z := X' x y denotes the data, distributed according to a probability distribution μa, on the data space Z. In practice, Hl is unknown, ML algorithms focus minimizing the empirical risk,
1 n Rs(w)
l(w, 21);
where S :- (21, (Z1,..,,2n) Zn)
8 M4. which means that (Zı,..., 2n) are independent samples from Pzz. In many applications, the minimization of (2) is achieved by discrete stochastic optimization algorithms, such as stochastic gradient descent (SGD) the ADAM 440] method. Such algorithms generate a sequence of iterates in R" denoted Wss == {w> I220 which depends on the data S, the initialization wo Ra, and some additional randomness U, e.g., the random batch indices in SGD. The generalization error characterizing the model's performance is then defined as:
Gs(w)) == R(wx)) - (wx).
(3)
The empirical risk (2) typically has numerous local minima, which raises the question of how to characterize their generalization properties. Recently, training trajectories (cf., Figure TT] have been shown to be paramount to answer this question 84 28) Indeed, these trajectories can quantify the quality of local minimum in a compact way, because they depend simultaneously hyperparameters, and the data, which is crucial for obtaining satisfactory bounds
the algorithm,
37 A wide 4 36 For instance, several
family of
bounds has been developed 88 28, 50
results on stochastic gradient Langevin dynamics [57 64 49]. continuous Langevin dynamics [57
and SGD (9) take into account the impact of the whole trajectory on the generalization error.
Parallel these developments, several studies have brought light the empirical links between
83 hereby making new connections with topological data analysis (TDA) tools 2]. These studies focus on
topological properties of DNNs and their generalization performance [58] 52 66 70
the structural changes across the different layers of the network [5]) or on the final trained network
(66] 70 83), and are almost exclusively empirical. This partially inspired a new class of trajectory- dependent bounds focusing on topological properties of the trajectories. In particular, recent studies
10 3 have proposed relate the generalization error various kinds of intrinsic fractal dimensions 266] 53 that characterize the learning trajectory. Informally, these bounds provide the guarantee that with probability at least - C, we have
778 21 35 22
sup Gs(w) tim(Ws) + IT + log(1/C)
wEWs
where dim(Ws) denotes various equivalent fractal dimensions, in particular the persistent homology dimension (PH-dim) [10. 21 and the magnitude dimension [3]. The term IT is an information- theoretic quantity that takes different forms among different studies. Despite providing rigorous links
We use S in informal statements indicate that absolute constants and/or small terms missing.

---

between the topology of the trajectory and generalization, these bounds have major drawbacks, First and foremost, as noted in 75 76 [., fractal- trajectory bounds, such as Equation ( do not apply to discrete-time algorithms. This creates a discrepancy between these theoretical results and the TDA- inspired methods to numerically evaluate them on commonly used discrete algorithms [T] 21 Additionally, existing bounds rely on intricate geometric assumptions, such as Ahffors-regularity or geometric stability [21]. that are not realistic in a practical, discrete setting.
78 35
Previous attempts were made to address this discretization issue. Specifically, under the assumption that the training dynamies possess stationary measure Hwis for T + 0o (T is the number of iterations), it was shown in 13 that with probability 1 - over S ~ _ and w wwls we have:
dim(pu]s) + IT + log(1/C)
Gs(w) S
(5)
where dim(pwis) corresponds to the fractal dimension of the measure phe (see 67 for formal definitions). While this was an important step, this bound only becomes practically relevant when the number of iterations grows to infinity, which is never attained in real-life experiments. Other attempts make use of so-called finite fractal dimensions [7]] or fine properties of the Markov transition kernels associated with the dynamics [35]. However, these studies also rely impractical assumptions and involve intricate quantities which make them not amenable to numerical evaluation.
dependeent generalization bounds, TDA- Despite the theoretical limitations of existing estimate the proposed intrinsic dimensions in inspired tools have been developed to numerically practical settings. Two particular methods have emerged and successfully demonstrate correlation with the generalization error, based on persistent homology IO, 21 (PH-dim) and metric space magnitude 33 (magnitude dimension); these two dimensions are equivalent for compact metric spaces B. Because of the limitations discussed above, existing theories do not account for these experiments, conducted with finite-time discrete algorithms. Moreover, existing empirical studies [0 78 only consider very simple models and small (image) datasets. Because of their lack of theoretical foundations, it is not clear whether they could be extended to more practical setups.
Contributions. In this paper, we investigate the building blocks of PH and magnitude dimensions, in order to propose new topology-inspirel generalization bounds that rigorously apply widely used discrete-time time stochastic optimization algorithms, and experimentally test our new topological complexities" on practically relevant DNN architectures. Our detailed contributions are as follows:
We start by establishing the first theoretical links between generalization and a new kind of computationally thrifty topological complexity measure, the a-weighted lifetime sums 77 74
We propose and elaborate on another novel topological complexity, positive magnitude (PMag), a slightly modified version of magnitude [46] 55). We rigorously link PMag with the generalization error, by relying on a new proof technique. Overall, our generalization bounds, rooted in TDA, admit the following generic form:
(Topological complexity) IT + log(1/()
sup Gs(w) S wEWs
n
We then provide flexible computational implementation based upon dissimilarity measures between neural nets (Tp, which enables quantifying generalization across different architec- tures and models, without the need for domain problem-specific analysis done in [39 g
Unlike existing trajectory-based studies [10, operating small models, our experimental
evaluation is extensive. We consider several vision transformers (20) and graph neural networks (GNN) [30] trained on multiple datasets spanning regular and irregular data domains (cf. Figure(p)) Our results demonstrate that the novel measures we introduce correlate strongly with the test performance across different architectures, hyperparameters and data modalities.
All the proofs of the main results are presented in the appendix, along with addi- tional experiments. We will make our entire implementation publicly available under:
"Our term "topological complexity" should not be confused with the homonym topological invariant.
3

---

2
Technical Background
Our generalization indicators will be based upon a-weighted lifetime sums and magnitude, capturing different topological features, as we shortly dicsuss below. Let p) be finite pseudometric space.
a-weighted lifetime sums. Persistent homology (PH) is an important concept in the analysis of
geometric complexes [T]]. We focus on the persistent homology of degree (PH"). Informally, consists in tracking the "connected components" of finite set at different scales. We provide in
Sections A.3 and A..4exacc definitions of this notion. For simplicity, we present here an equivalent formulation of the a-weighted lifetime sums based minimum spanning trees (MST) 42 73).
tree over X is connected acyclic undirected graph (a set of edges) whose vertices are the points in X. Given an edge e linking the points and b, we define its cost as |e| := p(a. b). An MST ' on X a tree minimizing the total cost ΣEET |e). The a-weighted lifetime sums E% are then written as:
Ya 2 0, (X) = EeETler.
The celebrated persistent homology dimension (PH-dim) [. of a compact pseudometric space (A, p) is then defined as (A) = inf, {3C > 0, VY C A finite, E,, (Y) I C). The PH-dim has been proven to be related to generalization error for different pseudometrics 11 21).
Magnitude. Magnitude is a recently introduced topological invariant 46 which encodes many impor-
tant invariants from geometric measure theory and integral geometry 46 55 (56.. Magnitude can be
interpreted as the effective number of distinct points in a space [46]. For 8 >> O, we define weighting
of the modified space (X, sp) as map : X + R. such that Va E X, ΣbEx a=ap(a.) B(b) 1.
Given such weighting 3, the magnitude function of (x, is defined
Mag (sX) := Σ oEx 8(a).
(6)
The parameter O should be interpreted as a "scale" through which we look at the set (X, p). We present in Appendix[A.5 additional properties of this function. Note that magnitude is usually defined in metric spaces; we show in Appendix B..2 that we can seamlessly extend
the pseudometric setting. Magnitude can be extended to (infinite) compact spaces [46 (55 and, as for PH, an intrinsic dimension, the magnitude dimension, can be defined from magnitude by the formula dim (A)
lim +00
log Mag(sA)
It is known that dinfu and dimning coincide for compact metric spaces
log(*)
556
73 3
As a result, dimbag has also been proposed as topological generalization indicator [3].
Total mutual information. Prior intrinsic dimension based studies relied on "mixing" assumptions (178) Assumption H5], [TO Assumption H1], 76 [3) or various mutual information terms [35] 21 to take into account the statistical dependence between the data and the training trajectory. Recently, a new framework was proposed in [22 to unify these approaches by proving data-dependent uniform generalization bounds using simpler and smaller information -oarmattio--thoretiic (IT) terms. By leveraging these methods, we derive new generalization bounds involving the same IT terms for all our introduced topological complexities. More precisely, they take the form of total mutual information between the data S and the training trajectory Ws. This term is denoted (= (S, Ws) and measures the dependence between S and W. We refer to Appendix I. and [35 81 for exact definitions.
3 Main Theoretical Results
We now introduce our learning- -hhooretic setup (section 3.1 before delving into our main theoretical results in Sections 3.2 and 3.3
3.1 Mathematical setup
Random trajectories. The primary goal of our theory is to prove uniform generaaizaann bounds over the training trajectory (Wk, & 2 0J. We are mostly interested in the behavior near local minima of R.g To this end, we observe the trajectory between iterations to and T', where to E IN the number of iterations before reaching (near) a local minimum and T 2 to is the total number of iterations.
By "uniform", we mean the worst
set; it should not be confused with uniform convergence.

---

Therefore, we consider the set W (w;, to <isT), which we call the random trajectory. Note that Wo-T is set, i.e. it does not contain any information about the aime-eppndeecc. Moreover, our setup allows the random times to and 7 to depend on the data S through the choice of a stopping criterion as opposed to being fixed predetermined times.
well as the General Lipschitz conditions. The topologiaal quantities described in section
intrinsic dimensions introduced in prior works [78] [0, 3 21[221, require a notion of distance between parameters (in Rd) to be computed. In the case of fractal-
generalization bounds, two cases have already been considered: the Euclidean distance [78] and the data-dependent pseudometric defined in 21. In our work, we emphasize that both examples are particular cases of more general family of pseudometrics on the parameter space R In order to fully characterize this family of pseudometries, we define the data-dependent map Ls Rd - R by Ls(w) = (f(w, 21 21)..... L(w, zn)). To fit into our framework, a pseudometric must satisfy the following general Lipschitz condition.
Definition 3.1 ((q, L. -iipschti continuity). For any pseudo-metric on R and 2 1, we will say that l is (g, L, p) Lipsccitz in w when Vw, w' E R [[s( - Ls(w"),, (1lg I Ln Ln /(p w').
wide variety of distances have been proposed to compare the weights of two DNNs 19. The above condition restricts analysis to family of pseudometries containing the following examples. Example 3.2 (Data-dependent pseudometrics). For any p 2 we define the pseudometrics (2) (w, w²) := n 1/p
(1) corresponds to the "data-dependent 1-1// [[ (w) Ls(w") pp- The case Pg
pseudometric" used in [21]: we will denote it ps := PS Example 3.3 (Euclidean distance). If E(wc =) is I--Lipschitz continuous in w, i.e., |e(w, =) f(w', =) S T.|lw - w'll for all 2, then l (p, L,, Il-lla)-Lipschitz continuous for every p 2 1.
Assumptions. Given an (q, L. p) -ippsssctt continuous (pseudo- (pseudo-)metric, our approach relies only on a single assumption of a bounded loss function. For the case of the pseudometrie ps (Example 3.2).
this assumption is already made in 21 [22].
Assumption 1. We assume that the loss l is bounded in [0, B), with B > a constant.
The boundedness of is classically assumed in the fractal / TDA literature 21 35 22
In particular,
this assumption is valid for the usual 0 - 1 loss. In [2D) it is shown that the proposed theory seems to be experimentally valid even for unbounded losses. Our experimental findings suggest that this observation also applies to our work.
3.2 Persistent homology related generalization bounds
10 13 21), we propose new general- In contrast to all existing fractal dimension-based bounds 78
ization bounds that apply to practical discrete stochastic optimizers with a finite number of iterations. To this end, our key idea involves replacing the intrinsic dimension with intermediary quantities that are used to compute them numerically. Following [10 3. this points us towards the two quantities, We now ready state the first generalization bound in terms of the a-weighted lifetime sums, where we denote E, for E% (Weg-r))
E. and Mag, defined in section 2
Theorem 3.4. Let p be pseulometric on Rd. Supposes that Assumption 7 holds and that E is (g, L, -Lipschhit,, for 2 1. Then, for all a E [0, 1), with probubility at least
C, we huve;
2 log (1 KnaDE)
2B Vn
Iao (S, Wi, Wi)+r) + log(1/C)
sup Gs(w:) S /B/ SoSiST
+ 3BV
n
2n
with Kn,a == 2 (2LL/n/BB)
The term (S, Wto-T) is the total mutual information (MI) term that is defined in Sections
2 and
A.1 It measures the statistical dependence between the random set We-+r and the data S
Such MI terms appear in previous works related to fractal-based generalization bounds [78] 13 21
Our proof technique, presented in Appendix B.5], makes use of recently introduced PAC- May-Bayesian
framework for random sets (22 to introduce this MI term. It is also shown in [22 that the MI term
Ino (S, WT is tighter than those appearing in the aforementioned works.
We highlight the fact that Theorem 3.4 is fundamentally different from the persistent homology dimension (PH-dim) based bounds studied in 10 21. Indeed, while the growth of E. for increasing
5

---

14
1 I'paaudometric al-pseudommtrit
Relative varlation (%)
12
PMag(vm)
10a
PMag(vm)
104
101
10a
10a
1
10a
Mag(v/)
Proportion the data (%)
(a) Comparison of Mag and PMag.
(b) Relative variation of Ei and Mag.
Figure 2: Left: Comparison of Mag and PMag (for /n)), for different (pseudo)metrics (ViT on CIFAR10). Right: relative variation of the quantities E. (W and Mag(vnWW,,- - with
(1) respect to the proportion of the data used to estimated Ps (ViT on CIFAR1O).
finite subsets of the trajectory used in [00 estimate the PH-dim, it does not provide any formal link between the generalization error and the value E.. Therefore, the above theorem could not be cast corollary of these previous studies. Another important characteristic of the above theorem (as well as the results of section 3.3) to be non-asymptotic, i.e., is true for every n E IN* This is an improvement over the fractal dimensions-basee bounds presented in [78
22
3.3 Positive magnitude (PMag) and related generalization bounds
Recent preliminary experimental results displayed a correlation between the generalization error of DNNs and magnitude
(3. To provide theoretical justification for this behavior, it would be tempting to mimic the proof Theorem and build on existing covering arguments. However, while lower bounds of magnitude in terms of covering numbers have been derived in [56], they appear to be impractical in our case. Another possibility would be to use the magnitude dimension bounds of 3. Yet, this could not apply our finite and discrete setting where the dimension is Hence, identify a new quantity, closely related to magnitude, while being more relevant to learning theory. With the notations of section 2
we fix finite metric space (X, p) and weighting B, X R of (X, sp), where s > 0 is a "scale" parameter. We define the positive magnitude as
AP 0, (sX) == == 300)==Exxx(0ex (a(4))+
where 24 := max(x, 0) denotes the positive part of æ. To avoid harming the readability of the paper, refer Appendix B.3 for the extension of PMag to the pseudometric case. Based a new theoretical approach, we prove that the positive magnitude can be used to upper bound the generalization enror (see the proof in Appendix B.7). This leads the following theorem:
Theorem 3.5. Let be pseudometric such that (W, Xp) admits a positive magnitude (according to Definition B.5 for every > We assume that l (q. L, p))..i-shshhhit continuous with q 2 Then,
for any > 0, we have with probability at least 1 that
B² + 3B
I (S. + log log(1/()
sup Gs(w;) < SISTST
log PMag" (LsW
n
2n
now present quick sketch of the proof of Theorem
3.5 order to highlight its key elements.
Proof. (Sketch) Let W be data-dependent random compact set (e.g., W The proof is based on two technical elements. The first a framework recently proposed in [22] for uniform generalization bounds for random sets. These results give that with high probability we have a bound of the form:
Loo (S, W W))-T) log(1/C)
sup Gs(w) S (ad Weg++) + wEW
n
where Rad(e, Wo is the celebrated Rademacher complexity Appendix A.2 The second technical element is new link between the Rademacher complexity of compact set and its positive magnitude. This result is discussed in Appendix B.7
5 whose definition is given in

---

-ATAASE
VIT VIT-CIFARIO
SWIN CIFARIOO
GRAPHSAGE MNIST
GATEDGCN MIIIST
COMPL.-METRIC
4as
W
LL
Vas
V
LL
Vus
dimpn ps 21
0.93
0.13
0.61
-047
0.11
0.50
0.23
-0.25
-0.27
-0.35
0.15
0.11
-0.06
Mag(y/)- Ps
0.68
0.62
0.65
0.64
0.56
0.47
0.51
0.53
0.69
0.71
0.70
0.79
0.85
0.97
0.91
0.88
Mag(0.01)-
0.41
0.55
0.50
0.47
0.39
0.33
0.24
0.10
0.17
0.36
9.35
0.35
0.49
(M)
0.91
0.67
0.79
0.85
0.69
0.47
0.58
0.62
0.59
0.45
0.53
0.59
0.75
0.97
0.85
0.84
PMag(0.01)- Ps
0.36
0.40
0.50
0.80
0.71
0.58
0.64
0.68
0.24
0.10
0.17
0.36
0.35
0.35
0.35
0.49
Ea-p5 Ps
0.95
0.67
0.81
0.86
0.47
0.58
0.62
0.67
0.74
0.70
0.72
0.48
0.72
0.74
dimpu 11:11 10
0.93
0.67
0.13
0.61
0.47
0.34
0.51
0.32
0.81
0.56
0.51
0.12
0.70
0.29
0.33
Mag(y/) ||| 1
0.95
-0.59
0.13
0.73
0.71
-0.57
0.07
0.53
0.75
0.77
0.76
0.61
0.77
0.76
0.77
0.52
Mag(0.01)-
|
0.95
0.60
0.17
0.72
0:44
0.12
0.53
0.75
0.74
0.74
0.60
0.60
0.47
PMag(yn)
11-1
0.95
-0.59
0.18
0.73
0.71
-0.57
0.07
0.53
0.75
0.74
0.74
0.60
9.77
0.93
0.85
0.54
PMag(0.01)-
1-1
0.55
0.71
0.63
0.51
0.58
0.75
0.35
0.51
0.60
-0.47
0.26
Eu -HHll
0.95
0.32
0.76
0.74
0.74
0.75
0.74
0.74
0.60
0.77
0.84
0.54
dimyu 01 20
0.95
-0.26
0.37
0.72
0.64
0.04
0.34
0.51
0.0
-0.13
-0.07
0.0
0.14
0.00
0.07
0.00
Mag(y/n)
0.95
0.67
0.81
0.88
0.69
0.47
0.58
0.62
0.64
0.68
0.66
0.75
0.78
0.85
0.82
0.82
(ag(0.01)-
0.33
0.59
0.75
0.27
0.44
0.50
0.11
0.12
0.26
0.10
0.25
PMag(v1)- 01
0.95
0.64
0.80
0.89
0.69
0.47
0.58
0.62
0.63
0.65
0.64
0.74
9.76
0.83
0.79
0.80
(Maa(0
0.84
0.36
0.60
0.49
0.57
0.13
0.11
0.12
0.26
0.10
0.25
E, 01
0.95
0.67
0.81
0.87
0.69
0.47
0.58
0.61
0.63
0.68
0.66
0.74
0.78
0.85
0.82
0.82
Table 1: Correlation coefficients associated with the different topological complexities.
The IT term (Ix) in the above result is the same as in Theorem 3.4 Given a fixed (finite) set W and big enough 8, we establish Mag(sW) PMag( (sW). Moreover, present in Figure 2a an empirical comparison of Mag and PMag, showing a small and almost monotonic relation between both quantities. Therefore, Theorem 3.3 may be seen as the first theoretical justification of the empirical relationship between magnitude and the generalization error observed in (3).
natural choice for the scale s would be s = vnn, ensuring a convergence rate in 1/2 However, our empirical evaluations (see section [5] in particular, Table I revealed that small values of s (we typically use 10-2) can also provide good correlation with the generalization error. This could be explained by the fact that PMag(sW) - 1 as 8 + O, i.e., the bound may not diverge when s -> O. For our topological complexities to computationally efficient, we focus our experiments on fixed values of s (in { (vn. 10 10-2)). ). We further analyze the sensitivity of part of our experiments to the value of in Appendix D.2.2 We will omit the trajectory and denote Mag(s) (s) and PMag(s).
Remark 3.6. As is explained in Appendix B.7 a key element the proof of Theorem 3.5 is newly discovered link between the celebrated Rademacher complexity [5] and positive magnitude. This an additional contribution of our work, which might be of independent interest. Moreover, this relation extends beyond the case of finite sets and applies in particular to compact trajectories (or hypothesis sets) W. We refer the reader to Remark B.15 and lemma B.16 for more details.
4 Computational Considerations
We now detail the numerical estimation of the topological complexities mentioned above.
Computation of E,,. We compute E., by using the giotto-ph library introduced in 665 77 This setup is inspired by PH frameworks used in [10 This technique uses the equivalent formulation of E,, in terms of PH (see Appendix A.3 for details). Theorem 3.4] and its proof (presented in Appendix B.6) suggest that the relevant value of a is 1; similar to 10 this what we used in our experiments.
Computation of Mag and PMag. Different methods exist to evaluate magnitude [47]. We use the Krylov approximation method (72, which is based on pre-conditioned conjugate gradient iteration, implemented in the Python library krypy wlissys. Cg to solve for the magnitude weights. We then sum over the weights to compute Mag, and sum over the positive weights to obtain PMag.
Distance matrix estimation. Given finite set (i.e.. a trajectory) W C. Id, the calculation of our topological complexities requires computing the distance matrix D, == [o(w, w') ww,)), For large DNNs, this may become challenging. Depending on p, we propose the following solutions.
Case 1: If is the Euclidean distance, for large DNNs (in our case for the transformer experiments) storing the whole trajectory is challenging. In that case, we use sparse random projections inspired by the Johnson-Linde Lindenstrauss lemma [82] to project the trajectories onto a lower-dimensional
7

---

subspace. We use the implementation in scikit-learn [63] so that, with high probability, the relative variation of the distance matrices is at most 5%, see Appendix AA77 for details.
Case 2: If p is of the form PS as Example 3.2 then the computation of Dp requires the evaluation of the model on the entire dataset at each iteration, which becomes intractable for large (1)
DNNs. In 21 Figure 3]. the authors show that the PH-dim based on the pseudometric ps = Ps is very robust to a random subsampling of a training dataset, i.e. when ps is replaced by Pg with B S and |B||||| << 1. Figure 2b shows that Ea and positive magnitude are also robust this subsampling. We mainly used [T/|s| = 10%. We refer the reader to Appendix C.2 for details.
Generalization error. Our theory, like many rrajectory-based studies [78 bounds on the worst-case generalization error over the trajectory WopTT. Yet, experiments in previous works mainly reported the error at the last iteration. To estimate the worst-case error in a computationally feasible way, we periodically evaluated the test risk between times ln and T (every 100 iterations) and reported (worst test risk final train risk) as the error in our experiments. This consistent as we start the trajectory Woo-T from weight Wto already in a local minimum. Our main conclusions are still valid if the final generalization gap is used. This observation, which is to the best of our knowledge new, is briefly discussed in Appendix D.2.1
10 21 predicts upper
5 Empirical Analysis
In what follows, we study our bounds on a variety of datasets and model architectures. We first explain the setup and the evaluation metrics before delving into the results and analysis.
Setup. Given a DNN and dataset, we start from a pre-trained weight vector Wto yielding high training accuracy on classification tasks. By varying the learning rate (1)) and the batch size (b), we define a grid of 6 x 6 hyperparameters. For each pair (π) b). we compute the training trajectory W for x 10 iterations. Unless specified, we use the ADAM optimizer [40]. Based on Woo-rT we estimate distance matrices as described in section 4 For the sake of clarity, we focus on 3 relevant pseudometrics: (i) the Euclidean distance| I|-11, as in 10 (ii) the data-dependent pseudometric ps- used in [21 3 and (iii) the 01-loss distance. For (ii), PS is computed based on the surrogate loss used in training (e.g., the cross-entropy loss), while the reported generalization error is always based on accuracy gap (01-loss) which is of interest in most applications (see section T.. For the last one (iii) p is defined as in Example B.2. but with é being the 01-loss; we call it 01 oo-psuudoeerric and denote it by 01 in the tables. This last setup matches exactly our theoretical requirements.
In terms of DNN architectures, we focus on practically relevant models, while previous studies mainly considered small networks [10 35 76). We examine two different families of architectures. The first family consists of vision transformers (ViT [79], CaiT 80) Swin 48), see Table 2). each evaluated on both the CIFAR10 44 and CIFAR 100 [43 datasets. Moreover, we also tested our theory on graph neural networks (GNN) architectures, namely GatedGCN 12 and GraphSage [32 trained on the Super-pixel MNIST dataset (23). To the best of our knowledge, this is the first time these kinds of topological complexities have been evaluated on transformers and GNNs. We ran the experiments on 18 NVIDIA 2080Ti (11 GB) GPUs.
Granulated Kendall's coefficients. We assess the correlation between our complexities and the
generalization error by using the granulated Kendall's coefficients (GKC) (37) While the classical
Kendall's coefficients (KC) (38) (denoted 7) measures the correlation between two quantities, it
may fail to capture their causal relationship. Instead, one "granulated" coefficient is defined in (37) for each hyperparameter (i.e., 인t. for 7) and uBs for b): it measures the correlation when only this hyperparameter is varying. In Table [ we report т, 4/LR and 4/uss and the averaged GKC, := (1 + + ps)s/, /2, for several models, datasets and topological complexities. In Figures 4a and we represent our topological complexities in the plane (4/Bs: LLRR): the red square indicates the region of best correlation (the coefficients are in [-1, 1], their sign is the sign of the correlation). It should be noted that a scaling of this constant B, coming from Assumption I would not impact the correlation between generalization and topological complexities that is observed in our experiments.
4b
5.1 Analysis
As explained above, we focus our main experiments on the quantities E,, Mag(vn), PMag( (V)))VV).
Mag(10-2) and PMag(105 (10-2), each computed for the 3 pseudometrics discussed above (1I 112- PS- 01). In the interest of comparison, we also compute the PH-dim (proposed in [10] for the ||-11/ and in 21 for ps), which is thus tested for the first time transformers and GNNs.
8

---

22x10
Butch sice
10
Betch size
10-1
10
poative magnitude
1.
Learning nate
Leaenino rate
1.x10
256
14x10
10
120
256
10
10
30
10 Generaliaaton gap
10
Genoralication gop
Gonereliaation gap
Figure 3: ps-based complexity measures vs. generalization gap for a ViT trained on CIFAR10:
dimpH (left), PMag(vin vn) (middle), and Ej (right).
Performance on vision transformers. We see in Table I and Figure 3 (additional graphical representation is given in Appendix [DI] that our proposed topological complexities consistently outperform the PH dimensions across several vision transformer models and datasets. This suggests that PH-dim, previously tested only small architectures, is less scalable to industry-standant models with more parameters. Figure 4a including all (model, dataset) pairs for the pseudometric Ps. reveals important observations. First, we notice that the GKC of our topological complexities are both positive and close to 1. indicating that they are indeed good measures of generalization. We note that for most models and datasets, dimpH has a small or negative Bhs indicating that it has less ability to explain generalization for varying batch-sizes. As it was observed in [2]] for PH- PH-dim, our complexities computed from the pseudometric ps correlate very well with the generalization gap while this gap is based on the 01 loss.
Performance on GNNs. An important aspect of our framework is the ability to seamlessly encapsu- late different data domains. In partieular, the possibility of using different pseudometrics can help define topological complexities that naturally take into account the internal symmetries of GNNs, without any model-specific analysis (39 g The results of Table I and Figure 4a confirm that our proposed topological complexities outperform PH-dim and correlate strongly with the generalization error for GNNs. Additionally, it may be observed that Mag( (R) performs significantly well for GNNs, and in particular better than PMag( vn). This points us towards the idea that further theory would be desirable formally relate magmitude to the generalization error in that case
Comparison of the topological complexities. In Table and Figures 3 and 4a it can be seen that E₁ and PMag( vл) perform equally well for the image and graph experiments across multiple datasets, models, and data domains. We see in Table that most topological complexities perform better with data-dependent metrics (i.e., ps and 01) than with the Euclidean distance, for transformer based experiments. This extends results obtained for PH-dim in (1], for smaller architectures. However, the poor performance of Euclidean basad complexities may also be partially caused by the projections applied to the Euclidean distance matrices make them memory-wise computable (see section This is a remaining limitation of our algorithms. On the other hand, the 01 and ps data-dependent pseudometrics seem yield similar performance in all experiments.
Ablations. In Figure 4b we reveal that changing the optimizer has little effect on the observed correlation (for the same model and dataset). Interestingly, we note that the PH-dim, computed with pseudometric ps and obtained from the SGD trajectories, exhibits high GKCs. This observation agrees with the results 21. F further displays the typical behavior of several topological complexities for ViT and CIFAR1O. In addition to the correlation of our proposed complexities being stronger than for the PH-dim, we observe that E., and PMag( vn) seem to better correlate with the generalization gap for small learning rates. Finally, it is consistently observed in Table and Figures 4a and 44b that using a relatively high value of the (positive) magnitude scale (s = vn) yields better correlations than small values (s 10 2)- However, both cases still provide satisfying correlation, comforting the robustness of magnitude as a generalization indicator.
Due to limited space, we present all the correlation coefficient of one transformer model ViT for CIFARIO and Swin for CIFAR100 in Table as illustrative examples for each dataset. The remaining
results appear in the Appendix, Tables 4 6 3 and 5 and they all follow a similar trend. Further empirical results and illustrations of this behavior are provided in Appendix D
WWe shall underline that, while Mag with the Euclidean distance was empirically proposed as complexity measure in B3) theoretical justification for Mag results in Table is still missing for moderate values of

---

1.00
1.00
0.75
0.75
0.50
0.25
0.25
Optimizers metric
Model dataset
SGD-Ps
0.00
ViT CIFAR10
0.00
SGD-Eucl.
CIFAR100
SGD-01
-0.25
CalT CIFAR1O
-0.25
ADAM-pi
Topological quantities
Topological quantities
-0.50
Swin CIFAR10
-0.50
ADAM-01
PMag(vi)
RMSprop-PA
PMag(Vi)
GatedGCN MNIST
PMag(0.01)
RMSprop-Eud.
PMag(0.01 dimm:
1.00
GraphSage MNIST
dimps
1.00
RMSprop-01
-1.00
-0.75 00.50 -0.25 0.00
0.25 Wos
0.50 1.00
-1.00 -0.50
00.25
0.00
0.25
0.50
0.75
1.00
Pbo
(a) pseudometric
(b) Comparison of optimizers for ViT on CIFAR1O.
Figure 4: Granulated Kendall coefficients for several models, datasets and topological quantities. Note that our framework is directly applicable to graph networks.
Conclusion
In this paper, we proved novel generalization bounds based on several topological complexities coming from TDA, namely a-weighted lifetime sums and variant of metric space magnitude, which we called positive magnitude. Compared to previous studies, we require fewer assumptions and operate discrete setting which our proposed quantities are fully computable. Our algorithms flexible enough to be seamlessly integrated with diverse data domains and tasks. These advantages of framework allowed us create computationally cheap experimental setup, close as possible to the theoretical setup. We thus provided comprehensive suite of experiments with several andustry-relevann architectures across vision transformers and graph neural networks, which have not been explored yet in this literature. We show that our proposed topological complexities correlate well with the generalization error, outperforming the previously studied intrinsic dimensions.
Limitations & future work. The main limitation of our theory is the lack of understanding of the IT terms, while they are still smaller than most prior works. The presence of this term renders our bounds not fully computable in practice. Indeed, the MI between random sets and the dimensionality of W (billions of parameters) could make a direct computation intractable. Nevertheless, our work focuses improving the topological part of the existing bounds. Our main goal is to demonstrate a correlation with the generalization error rather than directly quantifying the generalization. Our experiments show that the introduced complexities are important and meaningful in addition to being amplified in the first part of the bound, as the dependence explicit. Moreover, a better understanding of the behavior of positive magnitude for small values of the scale factor would be necessary improvement. Regarding our experiments, refinement of the estimation techniques of the topological complexities would be beneficial. Despite experimenting with practically relevant architectures, our future works also include scaling up our empirical analysis to include larger models and datasets, in particular large language models, which are still beyond the scope of this study.
not aware of existing techniques to evaluate
Acknowledgments
We would like to thank the reviewers Neurips 2024, who helped to significantly improve this paper. R.A. is supported by the United Kingdom Research and Innovation (grant EPP/S0241XX/I UKRI Centre for Doctoral Training in Biomedical AI at the University of Edinburgh, School of Informatics. U.$. is partially supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' l'avenir" program, reference ANR-19- P3IA-0001 (PRAIRIE 3IA Institute). B.D. and U.$. partially supported by the European Research Council Starting Grant DYNASTY - 101039676. T.B. is partially supported by the Royal Society Research Grant RGRRIVA 12241402. TB was supported by UKRI Future Leaders Fellowship [grant number MR/Y018818//1 18/8/].
Broader impact. Certifying generalization is key for safe and trusted Al systems, hence we believe that our study may have positive societal impact.
10

---

References
[1] Henry Adams, Manuchehr Aminian, Elin Farnell, Michael Kirby, Joshua Mirth, Rachel Neville, Chris Peterson, and Clayton Shonkwiler. A fractal dimension for measures via persistent homology. In Topological Data Analysis: The Abel Symposium 2018, pages 1-31. Springer, 2020.
[2] Henry Adams and Michael Moy. Topology applied to machine learning: From global to local. Frontiers in Artificial Intelligence, 4:668302, 2021.
[3] Rayna Andreeva, Katharina Limbeck, Bastian Rieck, and Rik Sarkar. Metric space magnitude and generalisation in neural networks. In Proceedings of 2nd Annual Workshop on Topology. Algebra, and Geometry in Machine Learning (TAG-ML), volume 221 of Proceedings of Machine Learning Research, pages 242-253., PMLR, 2023.
[4] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks, May 2019.
[5] Perter L. Barlett and Shahar Mendelson. Rademacher and Gaussian Complexities: Risk Bounds and Structural Result. Journal of Machine Learning Research, 2002.
[6] Peter Bartlett and Shahar Mendelson. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of Machine Learning Research, 2002.
[7] Ulrich Bauer. Ripser: Efficient computation of Vietoris-Rip persistence barcodes. Journal of Applied and Computational Topology, 5(3):391-423, September 2021.
[8] Arash Behboodi, Gabriele Cesa, and Taco Cohen. A pac-bayesian generalization bound for equivariant networks. Advances in Neural Information Processing Systems, 14:5554-5666 2022.
[9] Subhrajit Bhattacharya, Robert Ghrist, and Vijay Kumar. Persistent homology for path planning uncertain environments. IEEE Transactions on Robotics, (1 550, 2015.
[10] Tolga Birdal, Aaron Lou, Leonidas Guibas, and Umut Simsekli. Intrinsic dimension, persistent homology and generalization in neural networks, Advances in Neural Information Processing Systems, 34:6776-678,, 2021.
[11] Jean-Daniel Boissonat, Frédéric Chazal, and Mariette Yvinec. Geometrical and Topological Inference. Cambridge Texts in Applied Mathematics. Cambridge University Press, 2018.
[12] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint arXiv:1711.07553,200 2017.
[13] Alexander Camuto, George Deligiannidis, Murat A Erdogdu, Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. Fractal structure and generalization properties of stochastic optimization algorithms. Advances in neural information processing systems, 34:18774-18788 2021.
[14] Gunnar Carlsson. Topological pattern recognition for point cloud data*. Acta Numerica, 23:289-368, May 2014.
[15] Frédéric Chazal and Bertrand Michel. An introduction to topological data analysis: fundamental and practical aspects for data scientists. Frontiers in artificial intelligence, 4:108, 2021.
[16] Thomas H. Cormen, Charles E. Leiserson. Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.
[17] Ciprian A Corneanu, Meysam Madadi, Sergio Escalera, and Aleix M Martinez. What does mean to learn in deep networks? and, how does one detect adversarial attacks? In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition, pages 4757-4766, 2019.
11

---

[18] Vin De Silva and Robert Ghrist. Coverage in sensor networks via persistent homology. Algebraic Geometric Topology, 7(1):339 358, 2007.
[19] Claire Donnat and Susan Holmes. Tracking network dynamics: a survey of distances and similarity metrics, 2018.
[20] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An Image is Worth 16x16 16 Words: Transformers for Image Recognition at Scale, June 2021.
[21] Benjamin Dupuis, George Deligiannidis, and Umut Simsekli. Generalization bounds using data-dependent fractal dimensions. In International Conference on Machine Learning, pages 1922-8968. PMLR, 2023.
Dupuis
[22] Benjamin Dupuís, Paul Viallard, George Deligiannidis, and Umut Simsekli. Uniform gener- alization bounds on data-dependent hypothesis sets via pac-bayesian theory random sets, 2024.
[23] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-45, 2023.
[24] Herbert Edelsbrunner and John Harer. Computational Topology an Introduction Semantic Scholar. American Mathematical Society, 2010.
[25] Kevin Emmetr, Benjamin Schweinhart, and Raul Rabadan. Multiscale topology of chromatin folding. In 9th EAI International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS), pages 177-180, 2016.
[26] Kenneth Falconer. Fructal Geometry Mathematical Foundations and Applications Third Edition. Wiley, 2014.
[27] Carlos Fernandez-Granda Lecture 5; random projections, 2016.
[28] Jingwen Fu, Zhizheng Zhang, Dacheng Yin, Yan Lu, and Nanning Zheng. Learning Trajectories are Generalization Indicators, October 2023.
[29] Hanan Gani, Muzammal Naseer, and Mohammad Yaqub. How to train vision transformer on small-scale datasets? arXiv preprint urXiv:2210.07244 2022.
[30] M. Gori, G. Monfardini, and F. Scarselli. new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference Neural Networks, 2005., volume 2, pages 729-734 vol. 2, 2005.
[31] Mustafa Hajij, Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzmán-Sáenz Karthikeyan Natesan Ramamurthy, Tolga Birdal, Tamal K Dey, Soham Mukherjee, Shreyas N Samaga, et al. Topological deep learning: Going beyond graph data. arXiv preprint TTfi:22060006006 2022.
[32] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[33] Allen Hatcher. Algebraic Topology. Cambridge University Press, 2002.
[34] Yasuaki Hiraoka, Takenobu Nakamura, Akihiko Hirata, Emerson Escolar, Kaname Matsue, and Yasumasa Nishiura. Hierarchical structures of amorphous solids characterized by persistent homology. Proceedings of the National Academy of Sciences, 113(26):003--7440, 2016.
[35] Liam Hodgkinson, Umut Şimşekli, Rajiv Khanna, and Michael W. Mahoney. Generaliza- tion Bounds using Lower Tail Exponents in Stochastic Optimizers. Proceedings of the 39th International Conference on Machine Learning. July 2022.
[36] Ahmed Imtiaz. Humayun, Randall Balestriero, and Richard Baraniuk. Training Dynamics of 1,977/ October 2023.
Deep Network Linear Regions.
12

---

[37] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic Generalization Measures and Where Find Them. ICLR 2020, December 2019.
[38] Maurice G. Kendall. A new reasure of rank correlation. Biometrika, 1938.
[39] Bobak T Kiani, Thien Le, Hannah Lawrence, Stefanie Jegelka, and Melanie Weber. On the hardness of learning under symmetries. arXiv preprint arXiv:2401.0186% 2024.
[40] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
[41] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: (eee:::00900777 2016.
[42] Gady Kozma, Zvi Lotker, and Gideon Stupp. The minimal spanning tree and the upper box dimension. Proceedings of the American Mathematical Society, 184(4):1133-118,, 2006.
[43] Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009.
[44] Alex Krizhevsky, Vinod Nair, and Geoffrey E. Hinton. The cifar-10 dataset, 2014.
[45] Gregory Leibon, Scott Pauls, Daniel Rockmore, and Robert Savell. Topological structures in the equities market network. Proceedings of the National Academy of Sciences, 105(52):20589- 20594, 2008.
[46] Tom Leinster. The magnitude of metric spaces. Documenta Mathematica, 18:857-903 2013.
[47] Katharina Limbeck, Rayna Andreeva, Rik Sarkar, and Bastian Rieck. Metric space magnitude for evaluating the diversity of latent representations, 2024.
[48] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF international conference on computer vision, pages 10012-10022, 2021.
[49] Xuanyuan Luo, Luo Bei, and Jian Li. Generalization Bounds for Gradient Methods via Discrete and Continuous Prior, October 2022.
[50] Kaifeng Lyu, Zhiyuan Li, and Sanjeev Arora. Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction, January 2023.
[51] German Magai. Deep neural networks architectures from the perspective of manifold learning. In 2023 IEEE 6th International Conference on Pattern Recognition and Artificial Intelligence (PRAI), pages 1021-1031. IEEE, 2023.
[52] German Magai and Anton Ayzenberg. Topology and geometry of data manifold in deep learning. arXiv preprint arXiv:2204.0888 08624, 2022.
[53] Pertti Mattila. Geometry of Sets and Measures Euclidean Spaces. Cambridge University Press, 1999.
[54] Pertti Mattila, Manuel Moran, and Jose-manual Rey. Dimension of a measure, Studia mathe- matica 142 (3), 2000.
[55] Mark W Meckes. Positive definite metric spaces. Positivity, 17())733-757, 2013.
[56] Mark W Meckes. Magnitude, diversity, capacities, and dimensions metric spaces. Potential Analysis, 42(()) 572, 2015.
[57] Wenlong Mou, Liwei Wang. Xiyu Zhai, and Kai Zheng. Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints. In Proceedings of the 31st Conference Leurning Theory. arXiv, July 2017.
[58] Gregory Naitzat, Andrey Zhitnikov, and Lek-Heng Lim. Topology of deep neural networks. Journal of Machine Learning Research, 21(184):1-40, 2020.
[59] Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M. Roy. Information- Theoretic Generalization Bounds for Stochastic Gradient Descent, August 2021.
13

---

[60] Monica Nicolau, Arnold Levine, and Gunnar Carlsson. Topology based data analysis identifies a subgroup of breast cancers with unique mutational profile and excellent survival. Proceedings of the National Academy of Sciences, 108(17):7665-7770 2011.
[61] Nina Otter, Mason A Porter, Ulrike Tillmann, Peter Grindrod, and Heather A Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, 6:1-38, 2017.
[62] Theodore Papamarkou, Tolga Birdal, Michael Bronstein, Gunnar Carlsson, Justin Curry, Yue Gao, Mustafa Hajij, Roland Kwitt, Pietro Liò, Paolo Di Lorenzo, al. Position paper: Chal- lenges and opportunities in topological deep learning. arXiv preprint arXiv:2402.0888 2024.
[63] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-28 22300, 2011.
[64] Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization Error Bounds for Noisy, Iterative Algorithms. 2018 IEEE International Symposium on Information Theory (ISIT), January 2018.
[65] Julián Burella Pérez, Sydney Hauke, Umberto Lupo, Matteo Caorsi, and Alberto Dassatti. Giotto-ph: A Python Library for High-Performance Computation of Persistent Homology of Vietoris-Rips Filtrations, August 2021.
[66] David Pérez-Fermández, Asier Gutiérrez-Fandiño, Jordi Armengol-Estape and Marta Villegas. Characterizing and measuring the similarity of neural networks with persistent homology. arXiv preprint a1Xiv:2101.07752, 2021.
[67] Yakov B Pesin. Dimension theory in dynamical systems: contemporary views and applications. University of Chicago Press, 2008
[68] Maithra Raghu, Thomas Unterthiner, Simon Kornblith, Chiyuan Zhang, and Alexey Dosovitskiy, Do vision transformers see like convolutional neural networks? Advances in neural information processing systems, 34:121 16-11288, 2021.
[69] Patrick Rebeschini. Algorithmic fundations of learning, 2020.
[70] Bastian Rieck, Matteo Togninalli, Christian Bock, Michael Moor, Max Horn, Thomas Gumbsch, and Karsten Borgwardt. Neural persistence: A complexity measure for deep neural networks using algebraic topology. arXiv preprint arXiv:1812.09766 2018.
[71] Sarav Sachs, Umut Şimşekli, and Tim van Erven. Generalization Guarantees via Algorithm- dependent Rademacher Complexity preprint. COLT 2023, 2023.
[72] Shilan Salim. The q-spredd dimension and the maximum diversity of square grid metric spaces. PhD thesis, University of Sheffield, 2021.
[73] Benjamin Schweinhart. Fractal dimension and the persistent homology of random geometric complexes. Advances in Mathematics, 372:107291, 2020.
[74] Benjamin Schweinhart. Persistent homology and the upper box dimension. Discrete & Compu- lational Geometry, 65(2)333--364, 2021.
[75] Milad Sefidgaran, Amin Gohari, Gaël Richard, and Umut Şimşekli. Datt-Diitottion Theoretic Generalization Bounds for Stochastic Learning Algorithms, June 2022.
[76] Milad Sefidgaran and Abdellatif Zaidi. Data-dependent Generalization Bounds via Variable-Size Compressibility, January 2024.
[77] Shai Schwer-- and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014.
[78] Umut Simsekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. Advances in Neural Information Processing Systems, 33:5138-511 2020.
14

---

[79] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa. Alexandre Sablayrolles, and Hervé Jégou. Training tata-efffiiiet image transformers & distillation through attention. In International conference machine learning, pages 10347-10357. PMLR, 2021.
[80] Hugo Touvron, Matthieu Cord, Alexandre Sablayrolles, Gabriel Synnaeve, and Hervé Jégou. Go- ing deeper with image transformers. In Proceedings of the IEEE/CVF international conference on computer vision, pages 32 42, 2021.
[81] Tim van Erven and Peter Harremoës. Rényi Divergence and Kullback-Leibler Divergence. IEEE Transactions on Information Theory, 6077):777,-3820, July 2014.
[82] Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Number 47 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2020.
[83] Satoru Watanabe and Hayato Yamana. Topological measurement of deep neural networks using persistent homology. Annals of Mathematics and Artificial Intelligecee, 90(1):75-922 2022.
[84] Jing Xu, Jiaye Teng, Yang Yuan, and Andrew Yao. Towards Algoriigg Dependent Generalization: A Case Study Overparameterized Linear Regression. Advances in Neural Information Processing Systems, (6:79698-79733, December 2023.
[85] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR 2017, February 2017.
[86] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commmications of the ACM, 64(3):107- 115, February 2021.
[87] Afra Zomorodian. Topological data analysis. Advances in applied and computational topology, 70:1-39, 2012.
15

---

Appendix
We now provide additional technical details and proofs that are omitted from the paper, followed by experimental evidence complementing our main paper. We organize the appendix as follows:
presents additional technical background related to information theory, Rademacher complexity, and the various topological quantities that appear in our work. In Appendix B we present the omitted proofs of all our theoretical results, as well as few additional theoretical contributions.
Appendix A
In Appendix we show the experimental details needed to reproduce our experiments.
C
Finally, Appendix is dedicated additional empirical results.
A Additional technical background
A.1
Information--heoretic quantities
The following definition is a precise definition of the total mutual information term that appears in our main theoretical results. The reader may consult [8T 35 22 for further information this notion.
Definition A.1 (Total mutual information). Let X and Y be two random elements defined probability space (S2, F, P) (note that the codomains of X and Y may be distinct). We define the total mutual information between X and Y by the following formula:
Px,((A)
Lo (X, log
sup A
Px
Px
Such a term has already been used in the fractal-based generalization literature [35 22 Other works used intricate variants of this total mutual information term 21 proposed bounds are simpler.
13
We stress the fact that
A.2 Rademacher complexity
Rademacher complexity 6 777 is central tool in learning theory. As part of our theory uses this notion, we now provide its definition and introduce some notation.
Definition A.2 (Rademacher complexity on a hypothesis set), Let us fix a dataset S E Z", a set W C Rd and = (c1..... 6n) some iid Rademacher random variable Whenever it is defined, will call Rademacher complexity of l over W the following quantity:
Rad(e, W.S) = EE, n
sup WEW W
e,l(w, 2;)
Rademacher complexity has already been used in 21 Theorem 3.4] to relate the generalization error to the so-called data- dependeenndnnt fractal dimension. Part of our theory is based on a recent extension of such arguments the deta-dependent setting (22]
A.3 Persistent homology
The goal of this short subsection is to present a few notions of persistent homology, which is necessary for better understanding of our contributions.
is an important subfield of TDA, capable of providing myriad of new insights for analysing data by extracting meaningful topological features. It has demonstrated its usefulness in a very diverse set of applications from biology (60 255, to materials science (34), finance 45). robotics [9 sensor networks [18] and lot more [61]. The types of datasets which amenable to this kind of analysis are finite metric spaces (known as point-cloud datasets). images, networks and also level-sets of functions. More recently, several studies have brought light empirical links between persistent homology and DNNs 70 17 66). In particular, recent studies have related the
Persistent homology [24] 14
A Rademacher random variable is defined by P(q PP -1) 1/2.
16

---

worst-case generalization enror to several concept of intrinsic dimensions defined through persistent homology [T0 2T) As mentioned in the introduction, our goal is to extend these last studies to more practical settings.
In general. persistent homology is defined for any degree k E (denoted PH*). Intuitively, PH* keeps track of the number of "holes of dimension k" in set when looked at different scales. However, in our work and in [10 21], we only use PH whose presentation is simpler. In this section, to avoid harming the readability of the paper, we only present high-level introduction to PH that is sufficient to understand our work. The interested reader may consult [5 87) for a more in-depth introduction to persistent homology.
We first start by introducing briefly homology, which is classical concept in algebraic topology. We only introduce the most essential concepts for understanding persistent homology. For a more detailed introduction, please consult [33].
Definition A.3. A simplicial complex is set K of finite sets closed under the subset relation: if a E K and C σ, then E K.
In the above definition, a is simplex (plural simplices) and is a face of its coface.
Definition A.4. An abstract simplicial complex K. is a finite collection of simplices where a face of any simplex K. is also simplex in K.
Definition A.S. A simplicial k-chain is the formal sum of k-simplices.
N
(8)
where each ri E R, where a fixed commutative ring with additive identity and multiplicative identity 1, and Ø; E I.
XC is the set of simplicial k-chains with addition over R, which is an R-module. Then, the set of all k-simplices of the complex K. is a set of generators for KA.. For each generator a, the boundary of the sum of all (k- - fa-fae a.
Definition A.6. The boundary of k-simplex ( 2k) is the (k- 1)-chain
(x(a) Σ (2o. fi, xk).
where (JO.... Li, E....., .
) is the (k: 1) simmmpe spanned by all vertices without x;.
is common that the coefficients for homology are considered to be restricted to Σ2, which the field with 2 elements, 0 and 1, where 1 + = 0. However, the theory extends to homoogy with coefficeints any field (and since every field ring, the definitions in terms of rings are more general).
Definition A.7. A chain complex is sequence of abelian groups Aş with homomorphisms (called boundary maps) 0g As A such that 0.-1
for all k.
We should note that when considering coefficients in Zg, a k-chain can be seen as a finite collection of k-simplices.
Introduce topological invariants: simplicial homology groups and Betti numbers.
Definition A.8 (Simplicial Homology group). The n-th (simplicial) homology group of finite simplicial complex K. is
Ha ker a /im0
(10)
where ker and im are the kernel and image respectively of the boundary operator.
In order define the simplicial complexes of use in TDA, need to first understand what nerve is. Definition A.9 (Nerve). A simplicial complex associated to collection of sets is called nerve. The sets are the vertices of the complex, and a simplex belongs to a complex iff its vertices have non-empty intersection, Nrv {a S A * 0}.
17

---

Definition A.10 (Čech complex). The Čech complex of X for radius r is Čech, = (xx E X}, where Bi r) is the closed ball of radius r 2 0, centered at æ.
In other words. the Čech complex the nerve of the ball neighbourhoods of a set of points X S R". The Čech complex faithfully captures the topology of the space, but it is not computed in practice due to its high computational cost. Instead, different complex called Vietoris-Rips (VR) is used due to ease of construction for higher dimensions. It can be shown that the VR complex is not always homotopy equivalent the Čech complex, and therefore it can be seen as approximation.
We first need to introduce the notion a clique complex to explain what the VR is.
Definition A.11 (Clique complex). The clique complex for graph G (V, E) consists of all cliques of G, which are all simplices S V for which E contains all edges of o..
Now we have explicitly states all the necessary components in order define the main complex used in TDA, the Vietoris-Rips complex.
Definition A.12 (Vietoris- Rips complex). The Vietoris-Rips complex of X for radius r is the clique complex of the 1-skeleton of the Čech complex of X and r, Ri), = {a X ||u - all S 2r3 for all u E a.
Now that we have defined the most important complex TDA, we proceed explain how we can derive important topological information at multiple scales by introducing the concept of filtration.
Definition A.13. Given a simplicial complex K. a filtration is a totally ordered set of subcomplexes KC of K, indexed by nonnegative integers, such that for i S j. K' C K'.
Definition A.14 (Filtered simplicial complex). A simplicial complex. K., together with filtration (function f : I. + E such that (a) S f(T) whenever
face of 7). The sublevel at a value r E R is (-oo, which is a subxomplex of IC. Let To < < .... < I'm be the values of the simplices, and K.; f- (-o0, ri]. then we call Koo C Kr C ... S Kmm the sublevel set filtration of f.
When you start with a simplicial complex K. and you filter it according to a filtration f. it is clear that the homology of K,, evolves as the radius increases. For example, new connected components can be formed, loops can appear or disapper, cavities can form. What persistent homology does, and where the importance of the filtering comes in is that now we have the tools to track the topological changes associated with the different stages the filtering process, and to associate a lifetime to them (track when a topological feature has first appeared and at which stage of the filtration it will disappear). This essential topological information recorded in a set of intervals known as barcodes, which can be represented as multiset of points in R², where the coordinates correspond to the birth and death points of each interval.
A.3.1 Persistent homology of degree (alternative approach)
For the rest of the this section, we only focus on homology in dimension 0, and provide an alternative and perhaps easier to understand interpretation. Please note that the following definition is a simplified and non- sta-dtad (though equivalent) definition of PH?.
Definition A.15 (Persistent homology of degree 0 (PH"). Let (X. p) be finite metric space and N its cardinality. For each time > O, we construct an undirected graph Gt, whose edges are given by:
Ya, y E X, {a.y} E G. = p(a,y) S 5.
There exists finite set of times 0 < t ... < ts < too such that the number of connected components Gr, changes compared to G, fort < t. Let be the number of connected components in Gt,- By convention we set co = N and to = 0 and define n; == G - G-1- PH then defined as the following multiset (the notation {{-} denotes multisets):
PH
t2
times
Th times
"We use the term time for the scalar t, as it is classically done in the study of persistent homology. Note that this has nothing do with the number of iterations appearing in the rest of the paper.
18

---

Remark A.16 (Vietoris-Ripp filtration. The above is a simplified high-level definition of PH More formally, the construction of the family of graphs G, corresponds the construction of the so-called Vietoris-Rips filtration of X, of which we only kept the simplices of dimension 1, see [1 for more details.
We now use PH to give the definitions of the quantities of interest in our work. The following is definition of the quantity Ea already mentioned in section 2 but seen through the lens of persistent homology. As will be explained in Appendix these definitions are equivalent.
Definition A.17 (c-weighted lifetime sums). With the same notations as in Definition A.15 define the a- w-wehhtted lifetime sums as:
Ya 2 O, E (X)
Σ C.
DEPH
Remark A. ("birth" and "death" times). PH is usually defined as multiset of birth and death times, tracking the appearance and disappearance of "holes of dimension ke during the construction of the Vietoris-Rips filtration of X. In the particular case of PH all birth times are and the times that we constructed correspond the death times.
We end this section by giving the definition of the PH dimension, which has been shown to be theoretically and empirically related to the generalization error neural networks in prior works 10 21]
Definition A.19 (Persistent homology dimension of degree 0). Given a compact metric space (X, p). we define the PH dimension of degree 0 by:
dimpn(X) == inf {a 2 0, 3C 0, AA S X finite, Ea(A) S C}.
that for any compact metric space, the PH dimension defined above equal to the celebrated upper box-counting dimension 226 [4
has been shown 42 73
A.4 Minimum spanning tree
The persistent homology dimension used existing generalization bounds [0 21 is closely related to another notion of intrinsic dimension, called minimum spanning tree (MST) dimension 42] in the sense that the PH and MST dimensions bounded metric spaces are identical. The link between persistent homology and MST is even deeper than the equality between the induced dimensions, as noted by (73. In this section, we define quantities related MSTs which will play an important role in our proofs.
In this section let fix a finite metric space (X, Let us first specify our notations for trees. tree T on X is a connected undirected graph. We represent T by its set of edges, which are denoted + b (or equivalently b + a as the graph is undirected). For an edge e of the form - b, we define its length by |e| = p(a, b).
Definition A.20 (Minimum spanning tree). Let us define the cost of a tree by the sum the length of its edges, i.e.,
E MST (T) = Σ lel-
(
eET
An MST of X is defined as a tree with minimal cost. A consequence of the greedy algorithm to find such MST [16] is that MST T is also minimal for any of the following costs:
MST a
(T) = Σ 1e)0
eET
with a 2 0.
Our interest in this notion comes from several results that summed up in the following theorem. The reader can refer to 73 for more details.
Theorem A.21 (Link between MST and persistent homology). There a bijection between the two following multisets:
19

---

The multiset of the lifetimes in the persistent homology of degree 0 of the Vietoris- Riip complex of X.
The multiset of the length of the edges of MST of X.
Therefore, we fix some O, the weighted o--uum associated the persistent homology of degree O of the Vietoris-Ripe complex of X is equal to the cost Ea of an MST of X, ie:
EAST (T) = (x()).
In all the following, we will use the notation Ea to denote both quantities.
A.5
Magnitude
Let us restate formally a few standard definitions. The reader may refer to 46 details on the notions of magnitude, weighting, and positive definite metric spaces. In this section, we fix a finite metric space (X, p). Some of the presented concepts will be later extended to pseudometric spaces in Appendix [B.2]
55 56 for more
As before, the similarity matrix [46 of X is defined by M(a, b) e -(abb), for o, E X. We now define weightings and magnitude of X, according to [46, Section 2.1].
Definition A.22 (Weighting and magnitude). A weighting of X is function 3 X - RR such that Va X, Ee-((,)) B(b) =
BEX
such a weighting exists, the magnitude of X is defined by:
Mag( X) == ----20 ((b.
DEX
is easily seen that this definition is independent of the choice of weighting 3. When a weighting exists, say that X "has magnitude".
Based on such definition, it is natural to inquire, whether such weighting exists. This question has been studied by several authors [46] [55][]] [56]. This question appears to be related to the notion of positive definite space, which we define, according to [46).
Definition A.23 (Positive definite space). X is positive definite if the similarity matrix M positive definite.
It is clear that positive definite spaces have magnitude. More interestingly, we have the following result, which ensures that most metric spaces considered in this study are positive definite.
Theorem A.24 46 55)). Let E [1,2] and 2 1, every finite subset of (RR II-Ily)) is positive definite.
A.6 Covering and packing numbers
In this section, we fix a compact pseudometric space (X, and give definitions of covering and packing numbers. These quantities have long been of primary interest learning theory, in particular through the classical covering arguments for Rademacher complexity [77 69]. More recently, limits of covering arguments have been leveraged by several authors derive uniform generalization bounds in terms of fractal dimensions [78] 35
13 21
22
which we aim to improve in this study.
For X and E E X, p(xx y) I r.. We can now define covering and packing. Definition A.25 (Covering number). Let 5 > 0, the covering number (x) is the cardinality of minimal set of points N such that:
0, denote the closed ball centered
and radius by (x)
x U Bb(x).
#EN Remark A.26. There exist several conventions for the definition of such numbers 26 53 82 which are equivalent up to absolute constants and in particular induce the same fractal dimensions on X (see (26)..
all of
Definition A.27 (Packing number). Let 8 > O, the covering number NX( is the cardinality of maximal set of disjoint closed balls with centers in X.
20

---

A.7 About Johnson-LLindenstraae lemma
In our implementation Euclidean baseddee--aaedd topological quantities, we use sparse random projections to project the weight vectors from R to lower dimensional subspace. This is necessary because of memory constraints. Indeed, storing the full trajectory Wo- Rd (in our experiments T - lo 5 x 10º) can become intractable for large models.
Given a finite of points W C R and 0. Let N 2 O (
Johnson-Lindeenstrauss
lemma ensures the existence of a linear map P: Rd - R such that:
Yw, w' E W, (1 - ||0 - w'1l < PPw - Pw'l 11 s (1 + | - w w'll"
In practice, the linear maps suggested by this result can be obtained through subgaussian random projections [82] Section 9.3]
In our work, as the purpose of Johnson- Lindenstrauss embeddings is mainly memory optimization, we have to rely sparse random projections. We use the implementation provided in scikit-learn 63
More precisely, we used relative variation of 5%.
Finally, it should be noted that these projection techniques were only used for the vision transformer experiments, as the GNNs that used have small enough number of parameters avoid the use of random projections.
A.8 note on the connection to Topological Deep Learning
Topological deep learning (TDL) is rapidly evolving field that uses topological features to understand and design deep learning models [62] 31.. Our topological complexity measures can be seen as a direction towards addressing the Open Problem 7 mentioned in [62] concerning the discovery of topological properties of internal representations that are linked to generalization.
B Omitted proofs of the theoretical results
In this section, present the proofs of our main theoretical contributions. We divide proof's into two groups of subsections:
Sections B. B.2 and B.3 focus on the extension (in very natural way) of the quantities appearing in our bounds pseudometric spaces. The main outcome of this analysis the definition of positive magnitude in the pseudometric case. Note that Appendix [.]] is not a contribution this paper. We placed it in this section to improve the readability of the paper.
In sections
B.4
B.5
B.6 and
B.7 we present the proof of our main theoretical results.
Before, proving main results, define the notion of metric identification, which will be used in several of the following subsections. This is the same setting that was used in to naturally extend the persistent homology dimension to pseudometric spaces.
Definition B.1 (Metric identification). Let (X, be pseudometric space. We can define an equivalence relation on by a < p(a, b) 0. The associated quotient space, which is denoted X/~ is metric space for the naturally induced metric, which we still denote p We will also use the canonical projection.
π 7: X/2o
These notations will be used throughout the text.
B.1 Persistent homology and MST in pseudometric spaces
In this short subsection, we first restate results proven in (21). regarding persistent homology in pseudometric spaces. The main result is the following proposition, which has been proven inside the proof of [2]] Lemma B.9].
Indeed, if 6, then have Ve X, p(a, c) p)b,c).
21

---

Proposition B.2 (22 Let (X,p) be a finite pseudometric space and a 2 0, then we have:
(x E. (X/~)
where the pseudometric p (and its metric identification) have been omitted from the notation.
Based on Theorem A.21
above result also true when E., represents the cost MST of
B.2 Magnitude in pseudometric spaces
In this section, we fix (X, p) finite pseudometric space. We denote by x/~ its metric identification and by т
x/> the canonical projection.
We directly extend Definition A.22 to the pseudometric case. In order for this definition to make sense in our context, first need to verify that provides well-posed definition of magnitude. This follows from the following lemma.
Lemma B.3. We assume that the finite pseudometric space (X, p) has magnitude. Then magnitude independent of the choice of weighting.
The proof is straightforward and identical to the metric case. Let B, 3 be two weightings, we have:
Proof.
Σ B(a)= = ΣΣ
e b(a.b) (b)))(a)
Σ DEX
(((b) Σ
(plab)3(aa) = Σ B((b).
aEX
aeX BEX
aex
BEX
In the following theorem, we show that magnitude is invariant through metric identification.
Theorem B.4 (Invariance of magnitude through metric identification). X has magnitude if and only X/" has magnitude, in which case we have:
Mag(X) X) = Mag (x/~).
Proof. We decompose X into equivalence classes as:
x=
II
xEX/~
iE!
where II denotes disjoint union and the points (as)ier E X represent each equivalence class. We denote by à the equivalence class of E X.
Let B X R be any function. We have:
Va X,
Σ e pla,b)) 3(b)
Σe
p(a,a.)
Σ (().
(11)
bEX
iE!
BEa.
X has magnitude, then we take be a weighting of we define:
Va V/E B(a) = Σ 3(b).
bea
By Equation
II
is a weighting of X/~
: if 3 is weighting of X/~, then define:
Ya X, B(a) = 3(a),
where denotes the cardinality af By Equation
|I
3 is weighting of X.
22

---

B.3 Definition of positive magnitude in the pseudometric case
Let us extend our new notion of positive magnitude in finite pseudometric spaces. This rather complicated task. Indeed we need to ensure that the positive magnitude is independent of the choice of weighting, which is not true in general. For this reason. we restrict our definition to pseudometric spaces whose metric identification is positive definite and we choose one particular weighting.
Definition B.5 (Positive magnitude in finite pseudometric spaces), Let (X, be a finite pseudometric space whose metrie identification X/~ positive definite. Let [3 x/> - R. be weighting of x/~, then we define the positive magnitude of X, denoted PMag, by:
PMag(X) = Σ B(z)+1 2EX/~
where 24 = max(a, 0) denotes the positive part of x. We will say that X admits a positive magnitude if its metric identification x/- is positive definite.
Note that X/> admits a unique weighting because it is positive definite. However, X still admits several weightings in general. The above definition ensures that the definition of positive magnitude independent of any choice of weighting. For the need of our proofs, we will need to introduce weightings in pseudometric spaces, whose sums of positive parts yield the positive magnitude. This is possible by using the following definition, which corresponds to a "good" choice of weighting in finite pseudometric spaces.
Definition B.6 (Canonical weighting). Let p), be finite pseudometric space whose metric identification X/~ is positive definite. Let 3 x/~ - R a weighting of x/>, we define the canonical weighting 8 X - R X by:
Ya E X, (a) [Taa] ((*(a)),
where क. X > X/> is the canonical surjection.
The following lemma is then obvious but crucial to some of our theoretical results.
Lemma B.7. With the notation of the previous definition, we have:
PMag(X) = Σ (z)+
xEX
The next proposition is consequence of Theorem A.24, it shows that the pseudometrics considered in practice in our work (and in our experiments) admit a positive magnitude.
Proposition B.8. Let [1,2] and S E 2", then every finite subset of (R3, RRg magnitude, and therefore also has canonical weighting.
(p) admits positive
Proof. Let W = -W WN) be a finite set in Rd. We have
[w)) Ls(w') = 1/2
(p) ps (w, w').
Therefore, if we denote by the equivalence class of in the metric identification, is clear that
wh = (sww)= Ls(w)). Hence, the map iss n 11/PLs naturally extends to an isometry
between metric spaces:
w/~ ups (W)
C R
By Theorem A.24 the finite set (ps (W) is positive definite, hence it is also the case of W/>, Therefore W admits positive magnitude by definition.
B.4 Warm-up: covering bounds
The following deduced from the transcription of the results of 22 to our setting. is the starting point of our persistent domology-basee analysis.
23

---

Theorem B.9. Let be pseudometric on R Suppose that Assumption holds and that is (g. L. p)- Lipschiitz for 2 Then, for all with probability least 1 - over μ p p
2 log N2 N2 + 3B
160 W Who log(L/C)
sup Gs(w,) 2L8 + 2B SSSST
n
2n
The proof of this theorem will be given in the next subsection. Before discussing this proof, a few remarks in order.
Covering bounds, such as B.9 have been used 78 13 10 introduce fractal dimensions (more precisely through the notion of upper box-counting dimension) into the generalization bounds. This is done via the following definition of the aforementioned upper box-counting dimension:
log No
dimg (X) = lim sup
1og(1/8)
5-+0
By using a similar procedure, we see that our framework could be used to introduce intrinsic dimensions associated to wide range of pseudometrics, soon as they satisfy (g, L, p)-Lipschitz continuity assumption.
However, arguments based on these intrinsic dimensions only make sense in the limit T > oc, which makes little sense practical settings. To address this issue, we take inspiration from two other notions that are equal to the upper box-counting dimension (and therefore lay the ground of the numerical approximation of this dimension), namely the PH-dimension [42 73 10] 21 and the magnitude dimension 3). Our approach is replace the intrinsic dimensions by the "intermediary quantities" used to define them. This leads to the results presented in the next two subsection.
B.5 Proof of Theorem B.9
we specify our theoretical setup, which is the one introduced in [22]. In this section, we prove our results in the case T +00. However, note that one could consider T = +oo without much technical difficulties.
Before going to the proof of Theorem
B.9
The setup is the following: let (F(R"), T) denote the set of all finite subsets of Rd, endowed with a-algebra T.
We consider the following probability distribution on F(RR)):
YAET. ((A)= (s(d) (S).
(12)
As is discussed in [22 Section 5.4], we make the following technical measure-theoretic assumption. Assumption 2. The probability measure nn is strictly positive Borel measure. Moreover, for every T, the map S + (A) continuous.
The following example highlights the fact this a very mild assumption. Example B. B.10. If the data space Z is countable and the data distribution μs has no null mass, then the above assumption is automatically satisfied with respect the discrete topology.
Theorem B.9. Let be a pseudometric on Rd. Suppose that Assumption holds and that is (g, L. Lippshitz, for q 2 Then, for all with probability least 1 over _ p @os
sup Gs(wi) 2LS + 2B 2log No (WW.-T)) + 3B LSSiST
(S, W log(1/()
2n
Proof. Let us fix some Ç (0, 1). First note that thanks to Assumption 2 we have that ps is absolutely continuous with respect to u1 -almost surely. Therefore, we can introduce its Radon- Nykodym derivative, denoted by dps/dz.
Thanks to the above notation, we can apply the data-dependent Rademacher complexity bound of 22
Theorem 10] to obtain that with probability at least -, we have, for any À 0:
( dps (Wi,+r) + log(1/{) +
9B2
(R(w:) Rs(w:)) < 2Rad(E, WIG+T, S)+ + X dr
sup to STST
8n
24

---

with Rad(e, Wo S) Rademacher complexity term, defined by:
1 n 72
Rad(e, Woo+I, : E.
sup wE
Σ
al(w,z))
where 6 := (61,...,, En) is vector of independent centered Bernoulli random variables.
By 22 Lemma 16], have almost surely that:
dps (Wo--T) S (V
Therefore, by optimizing the choice of the parameter À in the above equation, we have that:
sup (R(w;) Rs (u:)) - 2Rad(E, We. S) + 3BV Tox (S, Wt -r) + log(1/C) (13) toSiST
2n
We now perform a covering argument very similar to classical covering arguments for Rademacher complexity (77). Let us fix some > 0 and introduce (#1,...,, NWW, the centers of minimal
d-covering of W T for pseudometric p. For any Wo- there exists such that p(w, xty) 8.
Therefore we have:
" Σ (el(w,21)
1
sup
sup IS/SNE(W x n
el(a, 21)
Σ
(l(ww, 2i) A( 2:)
WEW W 1=1
n
1
sup 1515 1W
Gl(ay,20 21)
[[(w, 2i) Elxj, 21)
1=1
i=
c,((z,; ( 21) + - [s((w) - Ls(2,)]l
1/9
sup (W
where the last line comes from Hölder's inequality.
We can now apply Massart's lemma on the first term and the (g, L, p) Lipschitz continuity of on the second term, this gives us:
2 2oog Ng (W
Rad(e, W L8 + B
n
which concludes the proof.
B.6 Persistent homology bounds
We now present the proofs of our persistent homology based bounds, ie, the results of section 3.2
The following lemma is pseudometric version of a classical result of fractal geometry 26
Lemma B.11 (Covering and packing in pseudometric spaces). Let (X,p) be a pseudometric space, 8 > 0, and {ri,...,,Ppp, (x)) maximal 5-packing of X for pseudometric p. Then we have:
No (X) & (X).
Proof. Let fix 8 0 and let (II...., 2 px) be centers of a maximal packing of X with closed 8-balls. Let assume that:
X
U
B2s(2;) #0,
(SiSPf(X)
that take some Ti belonging the above non-empty set. Now let us fix i E (1,..., Pf (X)) and w E BB(x)). By the triangle inequality and the definition of w and Wy, we have:
p( .1). $ p(zo, w) + p(u, x2)
25
25

---

Therefore, we have p(ro, w) > 8, and hence (z(z,) n BB(zo), so that we construct a bigger ö-packing, by adding To to (21...., (f((x)) which absurd.
Therefore, we have X UisiSpp(x) (2, = 0, hence the result.
The next lemma asserts that Ea is increasing (with respect to the inclusion of sets), if and only if S 1. This is the reason why we require [0, in Theorem 3.4
Lemma B.12. Let (X, p) be a non-empty finite pseudometric space, [0, 1] and ö > 0. Then we have:
(X) 8 2
(x)
Proof. We refer to for a graphical illustration of the main technical elements of this proof. In the where (X) 1, the result is obvious. In the rest of the proof assume that (x( 2
In all the following, we fix a E [0, 1] and >> 0. We also denote P Pf(() Without loss of generality, we can assume p 2 2.
We fix T an MST of X, represented by set of edges denoted æ + y. with x; X (note that we identify x + y and y + x)). It is a classical result that there are |X| edges. For edge of the form + b, we denote its length by le| == p(a,b).
For a. b E X, with # b, we denote by {a + b} the shortest path between and b. More precisely, we represent it as list edges, denoted = an - 01 ....... + og = b, for some K. When the context is clear, identify {a b} to the set of its edges - b.
Let us introduce (I1...., pp) p) maximal 5-packing of X by closed.
For every i E {l,..., P). as T is connected, there exists yi E X such that & Bs(x;) and is the only point in the path {a: + yi that does not belong the ball Bs(x;).
For each i, we denote e; the only edge in {z; - yi to which y; belongs, iee e, is the form + Yi. with 2, B5(x,,. By construction, those edges e, are the only ones that can be shared by several paths {x; + }.
Let us introduce the following set of indices:
: (i (I....,P), P), Vj # e, f ki} K (L= P)
Let us consider i E K. Let us assume that we have j.j' E {l...., P} such that e, E {z, yy} and E {xzz + yy If we denote e; as + Vs. we have that E BB(x;), by definition of y4- Therefore, by definition of yj. we have = (because (z(z,) n Br(x,) ) = -). We have similarly 2 = Uy and thus y/, yy-- By definition Y/j and y/ we also have y: E B2,),) n Bo(ry)), which absurd, by definition of packing. We conclude the following:
Vk: E K, Eij + i, e, E {xz - シ3}
For K, we denote the corresponding by (kk).
By definition of K, it is clear that (pk) E K. Moreover, as Up(()) 2, E Bs(x;), this implies that (1) = i. Therefore, we have constructed an involution,
ip K K,
such that Vk K, =pk)) A k. This implies that the cardinality of K is even and that can write K K1 1I K2, with:
K1| = [22), p(Ki)
K2-
The outcome of this construction is that now have disjoint paths given by the (#x Vi)eez and the (I& + ()) )EK, Therefore, we get the following lower bound on E.
Ex 2 Σ
le|a Σ
Σ
NET AE (
kEKi
eE (o
26

---

As E [0, 11, we have that:
E. (x) (m)
lel
Σ
Σ lel
keKi
By the triangle inequality, and by definition of packing, have:
(x)
8
+
Σ
8" = 8 (14) [Ka)+
2 (X)x'
2
kE 1
which concludes the proof.
104
E
Figure 5: Geometric representation of the proof of Lemma B.12 It represents point cloud (w:), )a, the centers the packing balls (blue) and the minimum spanning tree T (red), so that the sum of the lengths of the edges of T is exactly Ei, see Appendix A
Theorem 3.4. Let p be a pseudometric on Rd. Supposes that Assumption | holds and that is (g, L. Lipsschtz,, for 2 1. Then, for all [o, 1), with probability least I S. we have:
2 log (1 + Kn,a E.))
2B
(S, We, (6,+T) + log(1/C)
sup Gs(w;) S 2B SoSiST
3B 3BV
Vn
2n
with Kn,a 2 (2L
Proof. For better clarity, we assume T < +00. Let us fix some Ç E (0, 1), 8 > 0, and a 2 0. By Theorem B.9, we have, with probability at least 1 Ç:
2 log (W + 3BV (S, W10 + log(1/S)
sup (R(w)) (w:)))) < 2L8 2B SISTT
n
2n
We now bound the covering number appearing the above equation. By Lemma B.12 we have:
E (Waa-r)
- 2 a-
a-1 [Ps (W)-))) - 8
Moreover, by Lemma B.1l we have:
E (Wt.
2 2 2- a-
(W - 1)50.
We now combine this with our generalization bound by choosing the value:
B
= T
and we get that with probability least - -. we have:
(R(ws) Rs(w:)) < + +2BB
2B
2 log(1 + Kn (W(,-))
sup STSTT
Vn
n
Tno (S, log log(1/()
+ 3BV
2n
27

---

with:
2 22L
K Kn,a =
B
leads to the desired result.
B.7 Proof of the magnitude- generalization bounds
Lemma B.13. Let W C R be a finite sel and e == (e1,...., E and a pseudometric such that (W. Xp) admits a positive magnitude (according to Definition B.S) for every > We assume that E is (L, Lipsschti continuous with E [1,2]. Then, for any X O, we have:
}
Eg
exp
sup Σ e,elw, 2.) TE
S ee 228²
PMag ((LA)W).
wEW i=1
where PMag is the positive magnitude, Appendix B.3
Proof. We first remark that, by Hölder's inequality and the (L, 9, P)-Liscchitz condition, we have:
Vw, w' E W, ps(w, w') S n -1/4 Ls(w) - Lw(w")ll ااا s Lp(w,
Let us fix some À > 0. As (W, Ap) admits positive magnitude, we can introduce a canonical weighting 3 W R. By definition of weighting, we have
Va E EWWW
Σ (-paba,)) 3(b) 1.
BEW
Moreover, for any E (-1,1)", we introduce:
ag argmax
el((a,)))
With those notations, we can compute:
S Σ
b) (b)
Σ
(a. (b)
bEW
Σ bEW
lla (lb, -((b, (4)
exp
Ln
Σ
((l(ae, - - (+)
exp
Ln 1=1
beW
exp
24)
Σ
exp
E
cdl(b, 21) B.(().
Ln
Ln
bEW
Therefore, by dividing by the first term on the right-hand side and using the independence of the es we deduce that:
T
}
cil(b, zi) } (b)
E, exp
sup In weW
Σ cel(w, zi)
S E
Σ exp
LOE
Σ
E
((b22)(()))))) (4()).
NEW
By Hoeffding's lemma, have:
}
Ex
exp
sup wEW
Σ cf(w,, 2i)
<
22 e 2
Σ (b)
Ln
bEW
e
PMag (XW).
The result follows by the change of variable À = AL.
28

---

Theorem 3.5. Let be pseudometric such that (W, Xp) admits a positive magnitude (according to
Definition B.5 for every A > We assume that E (q. L, p)) -ipschhtt continuous with q 2 Then,
for any O, we have with probubility at least 1 that
B²
Too (S, Woo+T) + (og(1/()
sup Gs(ws) - log PMag (LSWoo-T) + + 3B SSsis
2n
Proof. The beginning of the proof is completely similar to the proof of B.9 up to Equation 13
More precisely, we have that with probability at least ç:
Toc (S, W -T) + log(1/C)
sup (R(w:) Rs(w))) 2Rad(e, Wo 5) +BB SISST
3BV
2n
By Jensen's 's inequality, we have, for all 0:
Σ }
n
Rad(E, W -To 8) S log E
exp
sup n wEW
Cel(w, 2i)
+
Therefore, we can apply Lemma B.13 write that, for all 0:
B²
(e Wo-TT, -T, 5) S
log PMag (I.
2n
We deduce that for all 8 > O, we have with probability at least 1 - that:
sup foSiST
(R(w:) Rs(ws)) S
B²
2
log PMag (LsWio-TT) v
(S, Weo + log( log(1/()
m
2n
Remark B.14 (Link between magnitude and positive magnitude). Let W C RM be finite set (for some M), of cardinality N, and a metric on W. If we denote the similarity matrix, for given value > 0. by (a b) = e p(a.)) then is clear that:
M,
IN-
Moreover, by continuity of the inverse, this implies that the weighting associated to > i.e. 3, : W R, satisfy:
Va E W, (a 1.
From this, we first deduce that, for 00, we have Mag"(sM + N. Moreover, by continuity of the inverse, this means that, up to a certain s, the weighting (3,(a)) Je only has positive elements. Therefore, this implies that, for big enough, one has Mag" (sW) PMag"(sW)
Thanks to our definitions for positive magnitude pseudometric spaces, given Appendix B.3 this observation extends to the pseudometric case.
Remark B.15 (Extension to infinite sets). There exist extensions of the definition of magnitude beyond finite sets [55] (56). More specifically, weightings are then represented by measures on the set. It is clear from the above proofs that we can extend the positive magnitude in this setting and that the proof would follow similar lines. Therefore, our theory provides upper bounds of Rademacher complexity in terms of positive magnitude in more general cases than the one we use in this work.
In particular, the present reasoning could be extended to compact random sets W. The next lemma is the extension of Lemma B.13 to the compact setting. The proof follows very similar lines as Lemma B.13
Lemma B.16. Let fix S n and consider set W C R& that is compac with respect to the pseudometric ps. For every X > O, we assume that A possesses a weighting μ* (which is a finite
X
As we did in Appendix B.3 the positive magnitude of compact spaces should be properly extended to pseudometric spaces, omit the details is very similar the case treated in this paper.
29

---

measure on A) with respect to pseudometric Xps, in the sense of (56) Definition 3.3]. Then we have, for any O:
}
2an²
E
exp
sup
Geww, zi)
PMag (AA).
Ti a
where PMag is the positive magnitude of the compact space (A, Aps) which, according to [56]. can be defined as:
PMag (AA) (ux)4 (A),
where ( denotes the positive part of the measure JAx-
C Additional Experimental Details
In this section, give additional details regarding the models, datasets, and hyperparameters used in our experiments.
C.1
Experimental setting
C.1.1
Vision Transformers Architecture and implementation details
Table 2: Architecture details for the vision transformers (taken from
29
WS refers Window Size.
MODEL
DATASET
DEPTH
PATCH SizE
TOKEN DIM
HEADS
MIP-RATIO
WS
#PARAMS
VIT
79
CIFAR10
9
192
12
2
2697610
VIT
79
CIFAR 100
9
192
12
2
2714980
SWIN
48
CIFARIO
[2.4.6]
96
[3.6.12]
2
7048612 4
SWIN
48
CIFARI00
[2.4.6]
96
[3.6.12]
2
4
7083262
CAIT
80
CIFAR10
24
192
4
2
8053450
CAIT
80
CIFARIO0 100
24
192
4
2
8070820
The design of the VIT has been modified to accommodate for the small datasets per [6 Our implementation based on the [29]. which is based on the timm library with the architecture parameters presented in Table 2 The implementation of Swin is based on the Swin- Twin-Transformer libarary and the implementation of CaiT is predominantly based on the timm library with some modifications. The full version can be found in the supplementary code.
Instead of training from scratch, which is extremely time-consuming. we used the pre-trained weights available from the GitHub repository of the paper [29], we further fintetuned them for 100 epochs on the dataset CIFAR10 or CIFAR100 to achieve the optimum performance reported in the paper (9). Then we verified that the finetuned weights achieved 100% training performance, and then they were the starting point our computational framework. We ran the transformer experiments on 18 NVIDIA 2080Ti GPUs, and the graph experiments on 18 Intel Xeon Silver 41 CPUs.
C.1.2 GNN Architecture and implementation details
will briefly talk about the details of GraphSage K2) and GatedGCN 12] prior works we use in
experiments. GraphSage [22 is improvement over the GCN (Graph ConvNets) model [1] and it incorporates each node's 's own features from the previous layer in an explicit way by the update equation:
H ReLUUU MeanjeN, h[)),
where N₂ is the neighbourhood of node i, h is the feature vector and T dRdx2d, We use the graph-pooling version of GraphSage, with the following update equation:
H1 ReLUU('CConaat(1, Max ReLU(V')))))
30

---

where V E Rddd GatedGCN (Gated Graph ConvNet) 12 uses the following update equation:
1 1 = hy + ReLLUUBN(UU + Σ do (oyov')))
JEN:
where Uh, V Raxd, @ is the Hadamard product, and the edge gates eg have the following definitions:
a(tT)) e EyEN. o(e,))
2 = ReLJU(B((A'N +B + C'elj
where a is the sigmid funciton, e a small constant for numerical stability, A B¹, Ct E Rdxd and BN stands for Batch Normalization.
We used the code provided by (23), which relies on the dg1 library implementation of GraphSage and GatedGCN, We trained GraphSage and GatedGCN until 100% training accuracy, following the setup in [23]. All experiments were ran on Intel Xeon Silver 4114 CPUs. Each experiment (one fixed batch size and learning rate) was run on single CPU and 18 experiments were run on the server at any given time (on different CPUs).
C.2 Hyperparameter details
Hyperparameters shared among experiments. For the Vision Transformers experiments, varied the learning rate range [10-6, 1000000 10-3), and batch size the range 256]. For the graph used 0.1
experiments, [10 10 10= and batch size in the range [8, 256). For all experiments, proportion of the training data for the computation of the pseudo matrix, apart from CaiT and Swin 100, where we used 0.09 proportion of the training data due memory constraints. All experiments use a 6 x grid of hyperparameters which is specified as follows.
VIT on CIFAR10. We selected 6 values for the learning rate in the range [10-5, 10 1010001000 and the batch size between [8, 256], and data proportion for the computation of the pssudo-distance (ps) of 10% (see section
VIT on CIFAR100. We selected values for the learning rate in the range [10-5, 5 10 10-31, and the batch size between [8, 256], and data proportion for the computation of the pseudo-distance (ps) of 10% (see section
CaiT on CIFARIO. We selected values for the learning rate in the range [10-5, 10-3), batch size between [8, 256), and data proportion for the computation of the pseudo-distance (ps) of 10% (see
section
CaïT on CIFAR100. We selected values for the learning rate in the range 110-5, 10 31, batch size between 88 256]. and data proportion for the computation of the pseudo-distance (ps) of 9% (see
section
Swin on CIFAR10. We selected values for the learning rate the range [10-b, 10-31, batch size between [8, 256). and data proportion for the computation of the pseudo-distance (ps) of 10% (see
section
Swin on CIFAR100. We selected values for the learning rate in the range [10-5, 10-3], batch size between [8, 256). and data proportion for the computation of the pseudo-distance (ps) of 9% (see section
GatedGCN. We selected 6 values for the learning rate in the range [10-6, 10=*), the batch size
between [8, 256] and data proportion for the computation of the pseudo- distance (ps) of 10% (see section 4). We note that for due time constraints, the experiments with batch sizes of 8 and 256 for the Euclidean metric were not complete.
GraphSage. We selected 6 values for the learning rate in the range [10-6, 10-2), the batch size between [8, 256), and data proportion for the computation of the pseudo-distance (ps) of 10% (see section
31

---

Average granulated Kendall
0.6
0.4
dimpw [6]
PMag(vn) (ours)
0.0
E1 (ours)
CIFAR10 12
Swin CIFAR100 +| la
GatedGCN
MNIST -
GraphSage -1
CIFAR10 01
CIFAR100 01
GatedGCN MNIST - 01
GraphSage MNIST
VIT
Swin
Figure 6: Comparison of topological complexities for different models, datasets, and pscudometrics. The results visual representation of some results from Table I they complete Fig. 1.c in the main par of the paper.
VIT on CIFARIO (Adam). We selected values for the learning rate in the range [10-5, 10-3), and the batch size between (8, 256), and data proportion for the computation of the pseudo-distance (ps) of 10% (see section 4).
VIT on CIFARIO (SGD). We selected values for the learning rate in the range [5 x 10 10-3, 10 10-1). and the batch size between [8, 256]. and data proportion for the computation of the pscudo-distance
(ps) of 10% (see section
VIT on CIFARIO (RMSprop). We selected 6 values for the learning rate in the range [10-6, 10-31 and the batch size between [8, 512). and data proportion for the computation of the pseudo-distance
(ps) of 10% (see section
D Additional experimental results
In this section, we present additional empirical results, in addition to what was already presented in the main part of this document. We divide this section into three parts. Additional graphical representation of our main experimental results is presented in Appendix D.I Then, we quickly explore in Appendix [D.2] additional ablation studies and comparison of our proposed topological complexities with complexity notion that is more standard in the literature, namely gradient variance [37] In Appendix D.3 we report additional experiments based on vision transformers and in Appendix D.4 we include additional illustrations of the GNN experiments.
D.1
Additional graphical representations
In this section, we include additional bar plots, shown in Figure 6 which are meant to provide more visual support to understand the results of Table Figure complltes the bar plots shown Figure
D.2
Further ablations and comparison with other complexity metrics
D.2.1 About the final accuracy gap and the worst accuracy gap
Our main theoretical results, presented section 3 apply to the worst-case generalization error over the trajectory, i.e. on the quantity sup (R(wx) - Rg(w))). However, computing this quantity over the whole trajectory may be extremely expensive it requires evaluating the
32

---

model on the whole dataset at each iteration (this is similar problem to the one encountered for the computation of the data-dependent distance matrices, discussed in section on worst-case TDAA-inspired generalization bounds circumvented this issue by reporting the final accuracy gap as the "generalization error" in their experiments (as it is the case in our work, most existing experiments consist of classification tasks).
Previous studies
In our work, we argue that the true worst-case generalization error may however have different behavior than the final accuracy gap. In order to estimate this quantity in a computationally friendly way, we used the following procedure: we periodically estimated the test accuracy during the training. computed its minimum value acCrsst-orst and substracted it from the final train accuracy (aCCarain-ina)) to obtain the "generalization gap" Gg reported in our main experiments, i.e.,
Gg = aCCCrain final
a00tt worst-
Note that in addition being a good proxy the true error appearing in our theory, the above quantity could be of independent experimental interest.
In order to assess that our main conclusions remain valid if the final accuracy gap is used instead of Gs, present here few additional experiments using the final accuracy gap generalization measure (it is denoted Accuracy gap in the figures.) In the case a VIT on CIFAR1O, this shown in Figure and Figure 8 We observe that our proposed topological complexities also correlate very well with the final accuracy gap, and outperform the previously proposed PH dimensions [00 21].
In addition to these findings, we make two additional new observations. First, the Ph dim, while outperformed by our proposed metric, has better granulated Kendall's coefficients when compared to the final accuracy gap than the worst generalization error (V/ goes from 0.20 0.36). This may explain why we observed poor performance of PH-dim in Figure 4a Second, we observe that the correlation seems be slightly less good with the final accuracy gap, especially for high learning rates, which seems to be similar behavior to what was reported in 21
10-1
10-1
20-1
x 10
Batch size
22 10
positive magnitad
Batch size
1.8x10'
E.aphs
10
Belth siie
Learring
512
222
10a4
10-4
10
10-4
Acceracy gap
Accurscy gap
Accursiy Shp
(a) E.
(b) PMag(Vn)
(c) dimpH
Figure 7: ViT on CIFAR10 with Ps ps-pseudometric, using the final accuracy gap generalization measure.
3.0
304
107
2x'0'
10-4
10-4
Laarting raB
1.x100
57
20
Lavring FRE
3.4x
222
20-4
14x 10
57
12x
223
10
Accuracy
accursc
(a) E.
(b) (Mag(Vn)
(c) dimpp
Figure 8: ViT on CIFAR1O with 01 -leuudoometrie using the final accuracy gap as generalization measure.
33

---

D.2.2 Sensitivity to the scale parameter in magnitude experiments
As is explicitly shown by Theorem 3.5 using (positive) magnitude as a topological complexity requires choosing the scale parameter s > In our main experiments, we experimented with both vn (justified to obtain the expected 1/ /n in the generalization bound) and 0.01 (in order to compare with using a small value for 8). We can see in Table | that both settings give relatively satisfactory results. Note that in our setting we have /ni R 223.6.
We present Figure the observed correlation between positive magnitude and generalization error for several intermediary values of This experiment was made with a ViT on the CIFARIO dataset, using the ADAM optimizer. We observe relative stability of the correlation V/ with respect s. In this particular case, the correlation is extremely stable for higher values of s while it displays more variability for smaller values of Further experiments would be necessary understand whether this behavior is general and could then lead to the discovery of more stable magnitude-reaate complexities, which we leave for future work.
Granulated Kendall Coefficient
0.01
0.1
200
400
500
1000
Scale parameters
Figure 9: Sensitivity analysis of the scale parameter for positive magnitude 7Mag(sWio-r Experiment made with ViT on CIFARIO and ADAM optimizer.
D.2.3 Comparison with gradient variance as a generalization measure
In this short subsection, we investigate the performance comparison of our proposed topological complexities with the more widely used gradient variance, which appears for instance in [37].
In this experiment, conducted with VIT the CIFAR10 dataset and the ADAM optimizer, observe very similar performance between E,, PMag( (ong,,,WW>>> and the gradient variance. Note that the fact that E, and PMag( VnW yield similar correlation was already observed Table 1 This tends to suggest that these three complexity measures may be able to capture similar aspects of the geometry around local minimum.
1.0
Granulated Kendall
0.8
0.6
0.4
GKC (B5)
0.2
Avg GKC
GV
Figure 10: Comparison of the granulated Kendall coefficients of topological complexities gradient variance (GV), MLR denoted GKC (LR), vBs is denoted GKC (BS) and the averaged coefficient denoted Avg GKC. Experiment made with ViT CIFAR10 and ADAM optimizer.
34

---

Remark D.I. It should be noted that the primary goal of the introduced topological complexity measure is not to outperform existing measures such gradient variance but rather to demonstrate the empirical importance of the topology of the trajectory for generalization error.
D.3 Vision Transformers additional experiments
We compare the performance of the different metries by using the granulated Kendall's coefficients
introduced in [37] The experiments presented here use 3 different Vision Transformers (ViT [79].
CaiT [8), Swin [88] on CIFAR10 and CIFAR100. As a baseline, we use the dimpu introduced in
10 and the data-dependent dimension with the pseudometric dimpu from [21].
Here present the full results each dataset and model. They he found in Table for Cai' and CIFARIC 10. for Swin and CIFARIO, 3 for ViT and CIFAR 100 and for CaiT and CIFAR 100. The plots from each experiment for every computed quantity be found in (the remaining 3 quantities for VIT and CIFARIO).
Satch siz2
Batch dize
102
posttre maggibulle
16
Leamiing rote
ph dim
Batch dize
10
10th
5.6
1000
40>
12
10
10:4
10
Goneralisatin gap
Generaiization DAP
Genersiization gap
10-2
Batch
posttove wwgpttode small
meanitude small
1.000
Learming catoe
54
128
10
128
256
10t
1.002
128
256
10
Generalisatin
Generalization gap
Coneralization
Figure 1I: ViT on CIFARIO with PS
1.17 10
10
5.36
Leuraing Pate
10a
16
32
64
2 10"
66
138
128
1.12
Concralizaion
Genorulization
Gencralisation
1.0x 107
Batch size
9,
pootiiee masgituueee cHall
1.5x10'
4'.
16
Leasinng rate
size
Botch size
3.8x
3.2x
52
2x
64
64
11x
128
128
10P
10
Contraltzatinn
Generatization
Generalization
Figure 12: ViT on CIFARIO with ||2
35

---

107
16
10
244x100
2.2 10m
Learning rete
103
Batch
10
Batch
10
Batch
16
16
1.4 1.0
10
10
32
10
32
1.2x10
10
Geseralizatio
Goneralisation
Generalization
10
10-3
10-2
1,004 10"
Butthh size
10a
10'
seajntulle small
1.003 10
Knarning nate
256
10
10"
128
256
10
10
Geteralization
Ocneralication gop
Ooneratization gop
Figure 13: ViT on CIFAR1O with 01 -eeeudoomerric
Table 3: Correlation coefficients for all quantities for VIT model and CIFAR100 dataset. The corresponding plots are presented in Figures 14
Figure
15
and Figure T6
METRIC
COMPLEXITY
a/as
VF
T
E.
0.78
0.71
0.74
0.70
Mag( vn)
0.78
0.71
0.74
0.72
Mag (0.01)
0.15
0.11
0.13
0.17
Ps
PMag( vn)
0.78
0.71
0.74
0.72
PMag (0.01)
0.62
0.61
0.56
dimpH 21
0.77
-0.71
0.03
0.36
E.,
0.77
0.51
0.64
0.67
Mag(0.01)
B
0.77
-0.69
0.04
0.50
Mag(v
0.77
-0.45
0.16
0.54
|| 1/2
PMag
0.82
0.53
0.68
0.66
PMag( /
0.78
-0.45
0.16
0.54
dimpp 110
0.77
-0.71
0.03
0.37
E.
0.77
0.71
0.74
0.70
Mag(
0.77
0.71
0.74
0.71
Mag (0.01)
0.68
0.51
0.59
0.59
01
PMag(
0.77
0.71
0.74
0.70
PMag(0.01)
0.72
0.71
0.71
0.63
dimpH
0.73
0.02
0.37
0.57
36

---

L8x
Batch size
1.7x10
10'
1.x
16
Learting nate
Batth 6lte
11x
101
1.3x
256
250
1:2X10f
Goneralization gap
Generalization
Goneralization gap
1.035 1055x110
pouttee mww.mmmemuuuue aroal!
1.42 10"
Learning naher
207
1.015
Batch 6t20
10
Batch sica
-10
Batch size
-10
16
39
Generalisation
Generaltzation
Generalization
Figure 14: ViT on CIFAR100 with ps
10"7
10-2
10a
1.175
1.10"
64
Batch slzu
10:1
3X.00
Betch stoc
10
1.16% 10
13B
10
Learingg
1.155
256
2x
120
250
1.145 10"
20
20
25
20
Generaliaaiio
Generalization
Generalizarion
16-3
1.6
prodtie magehuudee Garee
1.8
Leasing rate
Batch stzx
1.3
size
3.2
64
64
3.1 107
130
Gencralustun
Concraliaution
Goncrolication
Figure 15: VIT on CIFAR100 with
|| 112
10
20
10
302
1.a
Leaminn mibe
Batch
10-4
20a
Batch size
1.4
1.0 1.0
128
256
10
32
64
161
64
1.2
10-1
20
25
20
20
30
10
10
10
1.008
smell
1.006
20z
Batch
10-4
Batch size
10
1,004
Batch
-00
16
30t
64
22
64
1.002
64
32
120
256
20
20
Gescrulization
Oeneratication
Figure 16: ViT on CIFARI00 with 01 -l-pseudometric
37

---

Table 4: Correlation coefficients for all quantities for CaiT model and CIFAR10 dataset. The corresponding plots can be seen in Figures 17
18
and 19
METRIC
COMPLEXITY
LL
4/as
V
Ea
0.91
0.33
0.62
0.78
Mag(vn)
0.91
0.33
0.62
0.75
(0.00.
0.75
0.29
0.52
0.69
PMag( (V)
0.91
0.33
0.62
0.75
P PMag(0.01
0.87
0.38
0.62
0.75
dimpa 21
0.91
-0.19
0.36
0.75
E.
0,91
0.38
0.64
0.85
Mag( (ng())))
0.89
-0.42
0.23
0.73
Mag(0.01 (0.01)
3
0.91
-0.15
0.37
0.77
1.112
PMag(
0.89
-0.42
0.23
0.73
PMag(0 (0.01
0.53
0.26
0.4
0.48
dimpH 10
0.91
-0.31
0.30
0.67
Ea
0,91
0.33
0.62
0.84
Mag( ml)
0,91
0.33
0.77
Mag(0.01)
0.86
0.33
0.60
0.76
01
PMag( (
0,91
0.33
0.62
0.79
P PMag(0.00)
0,88
0.44
0.66
0.71
dimpH
0.91
-0.13
0.39
0.78
10
10
2.4110"
10-2
10
pesttive manuitiuee
1.6
128
10a
13B
1.2x10
13B
250
256
236
13
10a2
10
12
10a9
10
12
10*9
Gencrelization gap
pap
gap
10-1
1.025 10"
Batch size
10a
posntiee magnitute
Loaniing matt
2.015 10a
10'
1.055 10
250
16a
109
10
Generalitation ghp
Generalication gap
Generalization gap
Figure 17: CaiT CIFARI0 with ps-pseudometric.
38

---

5x30
Learang Pat
1.4K10
32
32
32
64
64
1:33
1:12%10
Gonerslization pap
Conérsitzation gap
Gonerslization gap
Batca dise
6x100
Leambu PM
megntture
3.0
1.0000
32
32
1.2x10
2x:00
Generulization gap
Coneralization gap
Generalization gap
Figure 18: CaiT on CIFAR10 with || ||2 distance.
10
109
poattrve megnitude
2x 10"
Learing 1at
Banch
Batch
1.8
Batch
107
32
32
32
86
10-
32
Generalization
Generailzation
Generaltzaton
posd cosprttude emeal
1.0
1.003
Learning rabc
Batch sice
10th
Babch sice
30-1
236
128
30
101
1,001
128
128
10-4
10
256
10-1
10f
10
Generalization gap
Generalization gap
Ganeralitation gap
Figure 19: CaïT on CIFAR10 with 01 -pseudometric.
16-3
10
10-3
Batch
1.8 1.8x100
10a
1.8
10-4
10-4
$ 1.4
1.5
256
Learing
16
32
22
1.3 10'
64
10²
64
10a
10:3
10
10
1.015
1.1155 10
Lourting rate
201
Batch sice
10:1
Batcch size
10
Batch sizt
20
16
16
1.0075 x 10
16
10a
1.085 10"
10a
Generatization
Goncralization
Gencralication
Figure 20: CaiT CIFAR100 with psppsuudometric.
39

---

Table 5: Correlation coefficients for all quantities for CaiT model and CIFAR100 dataset. The corresponding plots can be seen in 20
21 and
METRIC
COMPLEXITY
Fa
0.67
0.13
0.40
0.54
Mag( VrL
0.67
0.13
0.40
0.52
Mag(0.01)
0.47
-0.18
0.14
0.36
PMag( [T)
0.67
0.13
0.40
0.53
PMag(0 (0.01)
0.76
0.53
0.64
0.71
dimpu 21
0.67
-0.13
0.27
0.56
Eg
0.67
0.40
0.53
0.64
Mag(v/2
0.68
0.33
0,50
0.65
(0.00.
0.66
-0.33
0.17
0.54
11
PMag( V n
0.68
0.33
0,50
0.65
PMag(0.. (0.01
0.62
0.09
0.36
0.43
dimpH 10
0.64
-0.09
0.28
0.50
E. Mag(v
0.67
0.13
0.40
0.52
0.67
0.13
0.40
0.57
Mag(0.01)
0.61
0.18
0.40
0.43
01
PMag( v
0.67
0.11
0.39
0.53
P (M.0(0001
0.65
0.41
0.53
0,48
01 LOSS
0.58
0.07
0.32
0.57
1.175 10
1.17 10"
8x188
Learingg rala
10:1
Betch
18
Betchates stez
10
1.145 10"
256
10
256
10"1
1.14x 10f
256
20
30
35
20
25
30
25
20
5-10
10
18
2.3x100
10-7
2x
18
8x.00
14x
Batsh size
Betch sier
Betch siee
Learsing
3x
144
64
128
1x
120
120
107
Generailation
Ceneraltaation
Coneralization
Figure 21: CaiT CIFAR100 with
40

---

16
10
23 10
104
107
Batch
18'4
Batch
10
1.x0000 10
256
128
16
16
14x
10-1
32
30
10
Generaiizaiion
Geteralizaionn
Ganeralization
16
10
10
x.004x100
magnitulle small
1.033 x0
Learning retee
20r
Battch sint
10:4
Betthh sint
10
16
16
100"x100'
101
1.001
120
250
10
Generniization
Generalizaion
20
25
Ooneraliaation gap
30
35
Figure 22: CaiT on CIFARI00 with 01-pseudometric.
Table 6: Correlation coefficients for all quantities for Swin model and CIFAR1O. The corresponding plots are Figure 24 and
METRIC COMPLEXITY
4/1
a/as
T
E.
0.97
0.58
0.77
0.86
Mag( n))
0.97
0.57
0.77
0.84
Mag(0.01)
0.87
0.58
0.72
0.75
ps
PMag( (vn)
0.98
0.55
0.77
0.87
PMag (0.01)
0.76
0.20
0.48
0.65
dimpH 21
0.97
-0.57
0.19
0.67
E.,
0.97
-0.04
0.46
0.84
Mag( \T)
0.97
-0.43
0.27
0.77
Mag(0.01)
3
0.98
-0.22
0.38
0.80
PMag( (
0.27
0.77
PMMa(0.00
0.51
0.53
0.52
0.47
dimpH 110
0.95
-0.57
0.18
0.69
Ea
0.97
0.58
0.77
0.84
Mag( (n) m))
0.97
0.58
0.77
0.86
(0.00.01)
0.94
0.48
0.71
0.79
01
PMag(v/
0.98
0.58
0.78
0.87
PMag((.01)
0.92
0.42
0.67
0.78
dimpH
0.93
-0.28
0.32
0.69
41

---

1.8x10
Learning note
Batch sime
Botch sice
1.6x
Botch sice
10P
255
256
10
Goneralization gap
Generaitzation
Generalization gap
107
Ratch
postte mwg.neteeunueeo sToal!
1.023 10
10a
32
Learning nahe
magnhuue
64
60"
Batch alse
10-
Batch site
11
1.055
128
256
1.01 10"
10
12
Generalisation
Generaltzation
Generalization
Figure 23: Swin on CIFAR10 with ps- ps-pseudometric.
10
53100
10
10
10a
XX.8
Learding PO
Batch dbe
10
Batch dise
Batch dise
16.
18
20
10
1x
x.13x.1
256
256
250
16-
10
12
10
12
10
12
2xx00*
Batch size
1'707
sagnituse emall
16
Leamtngg rabi
1x100
1.x
64
32
3x.00
1.3%.10
Generailtation gap
Generalization gap
Generaiization Dap
Figure 24: Swin on CIFAR10 with
1|2-
10
2013
2.4x100
10
10"
30'
Learinn rihe
307
Satch
10-4
Batthh
10
1.6 10
Batch
16
32
32
32
64
10a
64
1:2x10
64
10:3
10
10
1.004 10"
1.7
neggntudee small
10a
64
Leaming rile
Satch
10-4
Battch
16
32
64
54
32
2.081 x
107
Figure 25: Swin on CIFARIO with 01 Ol-pseudometric.
42

---

Table Correlation coefficients for all quantities for Swin model and CIFAR100. See Figures 26 27 and 28 for the corresponding plots.
METRIC COMPLEXITY
4/LR
V
Ea
0.69
0.47
0.58
0.62
Mag(v
0.56
0.47
0.51
0.51
Mag(0.01)
0.31
0.47
0.39
0.33
PMag(v (
0.69
0.47
0.58
0.63
P PMMag(0.01
0.71
0.58
0.64
0.68
dimpH 22
0.69
-0.47
0.11
0.50
Fa
0.69
0.22
0.46
0.63
Mag(v/n (n)
0.71
-0.57
0.07
0.53
11
Mag(0.01
3
0.69
-0.44
0.12
0.53
PMag(
n1
0.71
-0.57
0.07
0.53
PMag(0.00
0.64
0.51
0.58
0.46
dimpu 10
0.69
-0.47
0.11
0.45
E.-
0.69
0.47
0.58
0.61
Mag( T6)
0.47
0.58
0.62
(a.(0.01)
0.61
0.27
0.44
0.50
01
PMag( (v)
0.69
0.47
0.58
0.62
PMag(0.01)
0.65
0.49
0.57
0.54
dimpH
0.64
0.04
0.34
0.51
1.0x100 10x
Batch size
10a
p90itive meaprituee
101
16x
10
15x100
L4x10
107
40'
64
12x10
125
256
356
10
22.5
25.0
27.5
50,0
22.5
27.5
32,5
22.5
25.0
27.3
32.5
deteraltatiin gAP
Seseratiation ghe
Generalization ghp
1014x101
posiitee magiitale smoll
10a
Batch size
Learsing Pite
diz
x.06
1.004 10
1.002 10
10-5
10-t
10"
10
22.5
27.5
20.0
32.5
23.5
22.5
23.5
25.0
30.0
Generaliaaton gap
Gencrolization gap
Generulizatin gap
Figure 26: Swin on CIFAR100 with ps-pseudometric.
43

---

10
101
megnebade
2.200
Batth sice
#x
10
1.35
1.15X
10"
Leurting mate
1:148
128
250
256
22.5
25.0
27.5
22.5
27.5
30.0
52.5
10
22.5
23.0
32.5
10-4
Generallaation
Generalization pap
16a
5x.00
1.8
Leariing mdt
dice
Bacch cise
10
2.4K.00P
13B
2x:00
2x
128
256
Gencraltation
22.5
25.0
27.5
35.0
32.5
22.5
25.0
Conoratization Dap
32.5
10
Figure 27: Swin on CIFAR100 with || -112-
16-
10-
2x Butch
307
307
Learing
E14410
302
1.2x 10"
128
128
256
255
10
22.5
25.0
27.5
30.0
325
225
25.0
27.5
30,0
32.5
22.5
25.0
27.5
30,0
32,5
gip
gip
10
10
10
aice
1.0025 10
Learing ritte
1.002 x 107
1.0015 10"
307
1.01 x 10
255
128
128
1.0005 x 10
30a
255
255
16-1
22.5
25.0
27.5
30.0
3255
22.5
25.0
27.5
30.0
32.5
22.5
25.0
27.5
30,0
32.5
gAp
gap
gag
Figure 28: Swin on CIFAR 10 with 01.
44

---

vn has been argued D.4 Graph Neural Networks Additional Experiments
In T we already presented the correlation coefficients for all quantities for the GNN models considered in our study (GraphSage. GatedGCN) (23 (we have selected the models which achieve 100% training accuracy)) and Graph-MNNIST. We can observe nice correlation, outperforing dim-PPi in most experiments. As it was observed for the transformer-based experiments, the correlation seems be better for the wee---dddeee-eeerrieee was used to compute the Euclidean distance matrices in the GNN experiments (it was not necessary as these models have less parameters than the tramsformers considered above). This shows that the fact the data-dependent pseudometrics outperform the Euclidean distance also happens in the absence of these projections. also shows that all quantities seem to yield better correlations in the absence of random projections, at least in the GNN expsriments.
This is an important fact, as no sparse random projection
The corresponding plots for GatedGCN can be seen in Figure 32 with the pseudometric, Figure 33 for the Euclidean and 34 for 01. The plots for GraphSage are reported in Figure 29 Figure 30 and Figure 31
We can observe a strong correlation on these figures, outperforing dim-PH in most cases. As was observed for the transformer-based experiments, the correlation seems to be better for the data-dependent-mettie
This is an important fact, as no sparse random projection was used to compute the Euclidean distance matrices in the GNN experiments" This shows that data-dependent pseudometrics outperform the Euclidean distance also in the absence of these projections. In addition, all quantities seem to yield better correlations in the absence of random projections, at least in the GNN expsriments.
Interestingly, a few failure cases be seen these plots. Indeed. Mag and PMag (0.01) seem to be almost constant and near 1. This indicates that the scale choice 8 = 0.01 was not suited already reflected in Table [ through very low Kendall's
for these experiments; this behavior coefficients, indicating the absence of meaningful correlation. However, Mag( /n) and PMag( Vn) provide significantly better correlation, which supports our main claims,
in section 3.3 to be particulary relevant choice of scale factor.
Note finally that the PH-dim plots for the 01-pseudometric failed to produce numbers in these graphs experiments (this is why they are either missing or look irrelevant). As before, we gave away this granulated Kendall's 's coefficients implementation to return zeros
fact in Table by imposing in the absence of correlation, hence the small numbers observed this case. That being said, this issue. Indeed, PH-dim with 01 oe-pseuuometric consists (in theory) in
behavior should not be seen estimating the dimension of a subset of a discrete hypercube, which is always O. The reason we still reported PH-dim for this pseudometric is for consistence and to test the implementation of [T0 21 in this non-standard setting; it is however not theoretically grounded.
A sparse random projection was not necessary as these models have less parameters than the tramsformers considered above
45

---

101
Batch sioe
6'"
pantive magretuals
Loarning AAt
107
K-002
120
250
10a4
32
64
32
2''
Generalzation
Goneralization
Goneralization
3.408
32
Leaming mite
4.003 10
128
1.0
tol
6.402 x
10"
2.6
3.8
2.0
3.2
10
2.5
2.8
2.0
2.2
10
2.6
2.8
2.0
2,2
10
Generrliicttion gop
gap
Goncralication gup
Figure 29: GraphSage on MNIST with Ps ps-pseudometric.
1.13X10F
poodfoe magiitule
1.12100
Pabs
gh
10P
128
128
256
250
2.5
3,0
3.2
10
28
3.0
1.08 100
2.8
3,0
3.2
10-4
Generalization gap
Generalisation gAP
Generalization gap
10-4
postbb cwwgetettttn maggiti small
magnkule cnal
1.008 100
Louriigg rate
3x
sicc
1.000 10
60x
2x
x.002
138
138
138
2.6
2.8
3.0
3.2
356
10
3.6
3.0
3.3
256
20th
10º
2.6
2.8
3.0
356
10
Cenoralization gap
Generalization gap
Generalization gap
Figure 30: GraphSage on MNIST with ||
||2.
Butch
Betch
10"
1.05
1.025 130
10
sice
18
Lesming
10'1
2.6
2.8
2.0
2,2
10
2.6
2.0
2.0
2.2
255
2.0
3,0
3,3
9
gap
Goneraliaation gap
Genoralication gap
1
10
Batch size
Betchh alze
Batch
procctttn congritaate soAal!
256
23B
3.0
3.2
2.5
2.0
Generalizaionn
Ganecaliaaioo
Figure 31: GraphSage on MNIST with 01.
46

---

Batch dioe
Battch 653m
10
64
1.28
Leamiing
256
10P
101
10
2.8
3.0
2.3
10
2.0
2.0
3:2
10'
10-4
Gcneraliaation gap
Genoralization gop
Goneralization gap
10
Betch
Batch sice
small
1.082 10
32
16
Leaming nute
84
3.0025 10"
250
122
10
138
256
10'
1.0009
10
10
2.5
3.0
Generatization
Cenerallzation
Generalization gap
Figure 32: GatedGCN on MNIST with ps pppeeddoomrrric.
10
10
10-1
10
magnitude
Learting mi
1.133 10
10-4
10
100
Batch dize
Batch size
Barch size
10
16
1p?
16
16
1:118>10'
Genoralication
Generaliation
Goneralization
neggnttutee seaul
10a
10"
64
magiitale sabil
64
120
1.00 10"
128
10t4
10
10
10a
3x 10"
pootave
x.00
2.8
2.5
3.1
128
10
10
2.8
2.5
3.0
3.1
10
10"
2.8
2.0
3.1
10
Generalization gap
Gener alizationn goo
Genoralization gop
Figure 33: GatedGCN on MNIST with || 1|2-
10a
positive inggnuude
40*
Leaming releo
60
magnituds
256
10
10
10a
2.8
10th
10"
3.0
10
Generalitation gap
Goneralization gap
Generalzation
10
10-4
Batich dize
Batch size
mnsgitudde
Goneralication
Generalization
Figure 34: GatedGCN on MNIST with 01.
47

---

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]
Justification: We clearly stated our contributions in the introduction and abstract. These contributions then detailed in the main part of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss several theoretical and empirical limitations of our work in Sections 4 [ Moreover, a paragraph following the conclusion is dedicated to highlighting the most important limitations and discussing future works.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
48

---

Answer: [Yes]
Justification: All our assumptions are clearly stated. We additinoally include technical measure-theoretic considerations [.5] showing the level of rigour our mathematical analysis. It should be noted that all the proofs of the theoretical results are presented in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: 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 whether the code and data are provided or not)?
Answer: [Yes]
Justification: The models, datasets and optimizers of all our epxcimrents are clearly stated. Moreover, all the details of the hyperparameters we used for both training the neural networks and evaluating our topological complexities are clearly stated in Sections 5 Moreover, we specify the exact algorithms that we use to compute the proposed topological complexities.
C.2
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
49

---

(d)
reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide the essential part of our code part of the supplementary material. This code submission contains a README, md file that contains instructions to first test the code and then run experiments. The code will be made publicly available upon acceptance of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
cublic/guidest htaaai//guiies//oeeuubbnisssss
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
7 wttpp..ccppubllle http:/uiiisssseee /tt////ooeSSeeieeeeeeeeeeee wttpSSubmmsiiioooooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
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]
Justification: We provide in Sections 5 and C.2 the full details of hyperparameters and optimizers, models and datasets used to train the neural networks in our experiments. Moreover, all hyperparameters used to evaluate explicitely mentioned in the paper, this includes in particular the number iteratiosn the trajectory, the proportion of the data used to evaluate the data-dependent distance matrices.
proposed topological complexities are
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
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?
50

---

Answer: [No]
Justification: In our paper, we conducted experiments variety of models (vision transformers, graph neural networks) that are significantly bigger than the ones previously used in the trajectory-dependentt generalization literature. As the cost of these experiments is extremely high, both in terms of computational time (it requires evaluating the model on large part of the data at each iterations in order compute the distance matrices) and memory (storing the trajectories). Moreover, for each (model - dataset) pair, we run the experiments a grid of hyperparameters, corresponding to 36 different set of hyperparameters each time. Therefore, we were not able to perform numerous epxeriments for each model/dataset. However, the fact that our experiments have good performance accross variety of models and datasets and on a grid of hyperparameters. Therefore, while we do not explicitly study the statistical significance of the resented results, extensive set of experiments does support the significance these results. Moreover, should be noted that we partially base our empirical study the granulated Kendall's ' coefficients, which more relevant than the classical Kendall's coefficient to capture causal relationships.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative еттог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
We specified in Section C the compute resources we used to run our experi- ments.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
51

---

Does the research conducted in the paper conform, in every respect. with the NeurIPS Code of Ethics https//tt...aarre...cccppaa/eeaa
Question:
Answer: [Yes]
Justification: Our paper follows the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We included broader impact statement following the conclusion, at the end the main part this document. As understading the generalization properties modern neural networks is key to trustworthy Al systems, we believe that our work may inspire future research having a positive societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Our submitted code only allows one to compute various topological complex- ities and compare them to the generalization error observed when training deep learning models. There is no risk that this could be misued.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
52

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: 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?
Answer: [Yes]
Our algorithms to evaluate the topological complexities that we propose, as well as the baselines, make use of cxisting libraries and codes that are clearly stated in Sections 4 and
Justification:
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pawerssi.ppwwiiie........ thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We include, as part of the submission, version of code that contains the algorithms described in the paper, along with documentation provided in README. md file. Our code will be made publicly available and will be clearly documented regarding what are the existing and new assets, as is done in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
53

---

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 as details about compensation (if any)?
Answer: [NA]
Justification: Our paper includes neither crowdsourcing experiments nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
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 the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not include research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
54


Reviews:
[{"review_id": "WBBZxOHYAo", "reviewer": "Reviewer_xNox", "summary": "The paper makes significant contributions by establishing new theoretical connections between generalization and topological complexity measures, specifically $\\alpha$-weighted lifetime sums and positive magnitude. The authors introduce these novel measures and link them to generalization error using innovative proof techniques.\nExperiments show that these measures correlate highly with generalization error across various architectures and datasets. The work offers simpler, less restrictive generalization bounds, removing the need for complex geometric assumptions. These flexible measures are adaptable to different domains, tasks, and architectures, providing practical, theoretically justified tools for understanding and predicting generalization in modern deep neural networks.", "questions": "1.- Have you explore the situation of use compact metric spaces? \n\n2.- Have you explore the situation of change the metric to a non-euclidean one?\n\n3.- In line 182, what do you mean by $\\mu_z^{\\otimes n}$?", "limitations": "Lack of understanding of IT terms.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The authors establishes new theoretical connections between generalization and topological complexity measures, specifically focusing on $\\alpha$-weighted lifetime sums and positive magnitude. Also, introduces and elaborates on new topological complexity measures, such as the positive magnitude, which is a modified version of the magnitude measure. These measures are linked to generalization error using new proof techniques.\nThe paper respects the discrete-time nature of training trajectories and investigates topological quantities suitable for practical topological data analysis tools, which leads to computationally efficient measures. It proposes generalization bounds that are simpler and less restrictive compared to existing methods, removing the need for complex geometric assumptions and making them more practical.", "weaknesses": "Maybe I get this wrong but in line 113, is $Y\\subset X$ or $Y\\subset A$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their interesting comments.\n\n> Maybe I get this wrong but in line 113, is $Y\\subset X$ or $Y\\subset A$?\n\nWe thank the reviewer for pointing out this minor typo in the definition of the PH dimension. Indeed, we have replaced $Y\\subset X$ by $Y\\subset A$ in the final version of the paper.\n\n> 1.- Have you explore the situation of use compact metric spaces?\n\nWe thank the reviewer for this interesting question/comment. Since we are interested in discrete optimizers, the most pertinent setting is that of discrete (even finite in practice) trajectories. However, it is interesting to ask whether our theory extends to random compact sets. As we hinted in Remark B.15 in the appendix, Theorem 3.5 (for positive magnitude) could be extended to such a compact setting. On the other hand, the extension of Theorem 3.4, involving $\\alpha$-weighted lifetime sums, might be more complicated as the definition of $E_\\alpha$ makes an explicit use of the finiteness of the set. However, we believe the main ideas of Theorem 3.4 could still be used to obtain interesting bounds in the compact setting and leave this question for future work. We have now added a further remark about it in the revision.\n\n> 2.- Have you explore the situation of change the metric to a non-euclidean one?\n\nAs we explain in Section 3.1 (about the mathematical setup), our framework encompasses a wide range of metrics and pseudometrics, as long as they satisfy the condition given by Definition 3.1. In particular, an important part of our experiments uses the so-called data-dependent pseudometrics on $\\mathbb{R}^d$, which we denote by $\\rho_S^{(p)}$ in the paper. These pseudometrics are typically non-Euclidean on $\\mathbb{R}^d$. While we use these non-Euclidean metrics, one can see in Example 3.2 that $\\rho_S^{(p)}$ results from the Euclidean distance on $\\mathbb{R}^n$ applied on the embedding $L_S(w)$ of $w$. It could be interesting to explore other non-Euclidean possibilities, which we leave for future work. For instance, if the loss is supported on a Riemannian manifold, then the associated metric could serve as a non-Euclidean metric to compute the topological complexities. One of the goals of our works is to leave the door open to such possibilities.\n\n> In line 182, what do you mean by $\\mu_z^{\\otimes n}$?\n\nFirst, as defined in the introduction, the notation $\\mu_z$ corresponds to the unknown data distribution. We used the notation $\\mu_z^{\\otimes n}$ as a shortcut for the product measure $\\mu_z \\otimes \\dots \\otimes \\mu_z$. Therefore, the notation $(z_1,\\dots,z_n) \\sim \\mu_z^{\\otimes n}$ means that the data points $z_i$ are sampled i.i.d. from the distribution $\\mu_z$. We now made these notations more precise in the paper.", "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": "tBONwE6VlK", "reviewer": "Reviewer_9Fve", "summary": "- The authors provided a novel topological-complexity-based uniform generalization error bound, constructed on the $\\alpha$-weighted lifetime sums or positive magnitude. This bound shows better correlation with the generalization error compared to existing bounds.\n- The authors proposed an implementation scheme based on dissimilarity measures between neural networks, enabling the quantification of generalization across different model architectures without the need for domain or problem-specific analysis.\n- The authors confirmed that their topological complexity term exhibits better correlation with the actual generalization gap in large-scale neural networks, such as ViT and GNN.", "questions": "The following questions primarily stem from the Weaknesses section. Please review these alongside the Weaknesses section and provide your comments. If the concerns and questions raised in the Weaknesses and Questions sections are appropriately addressed, I will consider increasing the score.\n\n- **Discussion on the Validity of Assumptions**: Could you provide a more detailed discussion on the impact of the upper bound $B$ of the bounded loss and how it affects the bound value? Specifically, for cases like the bound in Theorem 3.4, where the topological complexity is multiplied by $B$, it would be helpful to understand to what $B$ could potentially negate the correlation with the topological distance, either theoretically or numerically. Additionally, could you elaborate on the validity of the $(1,L,\\rho)$-Lipschitz continuity assumption?\n\n- **Mutual Information in the Bound**: Please provide a more detailed discussion on the mutual information term appearing in the bound. Can this quantity be upper-bounded by a constant, thus ensuring uniform convergence? Or could this potentially be unbounded and thus become a fundamental limitation?\n\n- **Sensitivity to Hyperparameter Settings ($s$ and $\\tau$)**: How do the evaluation metrics and experimental results vary with the hyperparameter settings, such as $s$ and $\\tau$? If feasible within the rebuttal period, it would be beneficial to discuss this sensitivity. If there is a valid reason for not addressing this, please explain.\n\n- **Comparison with Gradient Variance and Other Mutual Information Terms**: Does the topological complexity in the proposed bound achieve better correlation with generalization compared to gradient variance and mutual information terms, which are known to correlate well with generalization performance? If the derived topological complexity demonstrates a stronger correlation, it could significantly contribute to future research directions. Providing theoretical and experimental evidence would be beneficial. If there is a valid reason for not making this comparison, please explain.", "limitations": "- This paper is a theoretical study aimed at providing a more realistic evaluation of generalization error. The data used in the experiments, such as MNIST, are open-source, which indicates that potential negative social impacts are appropriately controlled.\n- While limitations are discussed in Section 6, there appear to be additional potential limitations as mentioned in the questions above. Addressing these would provide a more comprehensive understanding of the research's boundaries and enhance the validity of the study.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- More Realistic Generalization Error Bound\n  - This paper addresses a significant limitation of previous topological complexity-based generalization error bounds, which only hold under discrete parameter updates based on SGD or Adam, or when the number of iterations is taken to infinity. By overcoming this limitation, the bound provided in this paper offers a more practical and realistic understanding of generalization performance.\n  - Additionally, the paper presents a method to compute this complexity for large-scale neural networks such as ViTs and GNNs, enhancing its practical applicability.\n- Innovative Combination of Two Interesting Topological Metrics for Generalization Error Bound\n  - The authors leverage the fact that the $\\alpha$-weighted lifetime sums based on minimum spanning trees, a quantity from persistent homology, are related to a pseudo metric, and apply this to generalization error analysis.\n  - They also focus on a topological quantity called Magnitude and its connection to metric spaces, successfully providing another generalization error bound.\n  - These achievements are the result of effectively combining techniques from topological data analysis, which goes beyond mere application and demonstrates significant originality.\n- Correlation with Generalization Performance Confirmed through Numerical Experiments on Large-Scale Neural Networks\n  - The proposed topological complexity is computationally feasible even for large-scale neural networks. This is crucial for understanding the generalization performance of models like LLMs in the future.", "weaknesses": "- Concerns Regarding Assumptions\n  - This bound only holds under bounded losses. Thus, as the upper bound B increases, the bound becomes vacuous and diverges under unbounded losses.\n  - Additionally, the relationship between the upper bound B of the loss and the topological complexity is unclear, making the overall interpretation of the bound difficult. For instance, under large B, the correlation of the topological complexity might be negated, resulting in a bound that does not correlate well overall. Providing an intuitive discussion on this aspect would help clarify the significance of the bound.\n  - I am not well-versed in the assumptions based on pseudo metrics, so I cannot assess the validity of the (1,L,\\rho)-Lipschitz continuity assumption. However, as the authors mentioned, this assumption limits the applicability of the bound to certain pseudo metrics like the Euclidean distance or data-dependent pseudo metrics.\n\n- Concerns Regarding Mutual Information in the Bound\n  - Although the authors reference literature to assert that the mutual information in their proposed bound is tighter than the information-theoretic quantities in traditional bounds, they do not provide concrete methods for calculating or estimating this quantity.\n  - This means that while some terms in the proposed generalization error bound are computable, the bound as a whole is not computationally evaluable. Thus, although the topological quantities used in the bound correlate with generalization performance, this does not guarantee the overall tightness of the bound. In practice, even if the topological complexity decreases, an increase in mutual information could render the bound vacuous.\n  - The paper claims that the proposed bound is a uniform generalization bound. Therefore, it is necessary to discuss whether this bound achieves uniform convergence. If the mutual information term can be bounded by a constant, uniform convergence might be guaranteed, but this is not trivial and depends on the behavior of this quantity. Otherwise, the bound might fail to ensure uniform convergence.\n\n- Challenges in Handling Hyperparameters and Lack of Detailed Discussion\n  - If I understand correctly, the evaluation of the bound and topological complexity is closely related to the iteration step \\tau at which the measurement begins and the scale value s in PMag, both of which need to be determined for the bound to hold. These settings carry the risk of arbitrariness in evaluating generalization error. However, the paper does not provide sufficient discussion on the correlation between these changes and generalization performance (incidentally, there is a notation conflict between Kendall’s coefficients and \\tau here). For instance, providing more candidates for s and analyzing the sensitivity of the correlation degree to changes in its value, or verifying the variation in experimental results under multiple starting point candidates \\tau, would allow for a minimum level of discussion.\n\n- Lack of Comparison with Other Information-Theoretic Quantities or Metrics Strongly Correlated with Generalization\n  - The numerical experiments presented in this study focus solely on topological complexity and compare the contributions of this research with existing studies in terms of correlation with the generalization gap. As a result, the relationship between topological quantities and generalization, and their standing in the context of other discussions, such as generalization based on, e.g., gradient variance (e.g., Jiang et al. (2019)) or mutual information (e.g., Russo and Zou (2016); Harutyunyan et al. (2021); Steinke et al. (2020)), remains unclear.\n  - Thus, it remains uncertain how the proposed measure compares to other evaluation metrics in terms of superiority.\n\nCitation:\n- Jiang et al. (2019):  Jiang et al. Fantastic Generalization Measures and Where to Find Them. ICLR2020. https://openreview.net/forum?id=SJgIPJBFvH\n- Russo and Zou (2016): D. Russo and J. Zou. Controlling bias in adaptive data analysis using information theory. AISTATS2016. https://proceedings.mlr.press/v51/russo16.html\n- Harutyunyan et al. (2021): Harutyunyan et al. Information-theoretic generalization bounds for black-box learning algorithms. NeurIPS2021. https://arxiv.org/abs/2110.01584\n- Steinke et al. (2020): Steinke et al. Reasoning About Generalization via Conditional Mutual Information. COLT2020. https://arxiv.org/abs/2001.09122", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful review. Below we address all the raised concerns. We hope that the reviewer reconsiders their score in the light of our comments.\n\nBefore delving further, we would like to point out that our main focus is to obtain not just theoretical insights but also empirically meaningful quantities. We stress the importance of the latter, the extensive suite of evaluations proving that our topological quantities are meaningful and exhibit strong correlations. Our paper presents the first topological measures with an extensive set of experiments, obtained on practical models and complex data domains.\n\nWe have now included additional discussion on all the points listed below.\n\n**Validity of the assumptions.**\n> Bounded loss\n\nLet us emphasize that the bounded loss assumption is realistic in several practical settings (eg, for the $0-1$ loss) and that it has been largely used in the literature on topological bounds [17,18,29].\n\nIn Thm. 3.4, the scaling of $B$ will not affect the correlation. Indeed, if we multiply the loss by $c>0$, ie, $\\ell':=c\\ell$, and consider the data-dependent pseudometric $\\rho_S$, then $E_1$ is also multiplied by $c$, hence the observed correlation is independent of the scaling factor. We now expand on these details in the paper.\n\n>  Lipschitz assumption \\& applicability\n\nFirst the $(1,1,\\rho_S)$-Lipschitz condition is always satisfied for the data-dependent pseudometric $\\rho_S$. Indeed, by definition, $\\Vert L_S(w) - L_S(w') \\Vert = n \\rho_S(w,w')$.\nThe $(1,L,\\rho)$-Lipschitz condition becomes non-trivial when $\\rho$ is the Euclidean distance. In that case, it requires $\\ell(w,z)$ to be Lipschitz, which is relatively standard. \n\nIn our paper, we encapsulated both scenarios inside a single condition to identify the more general structure and pave the way for the use of other distances between models. Thus, our Lipschitz condition should not be seen as a limitation but rather a generalization.\n\n**Mutual Information.**\nThe MI term measures the dependence between the data $S$ and a random set $\\mathcal{W}$. Its presence is inherited from prior topology-based generalization studies, which face the same issues [17,18,8,11,69,29]. These bounds can be decomposed as the sum of a topological and an MI part, yet, in prior works the topological part suffered from major drawbacks, which is the main focus of our paper. We aim at improving the topological part of the bound.\nObtaining a clearer understanding of the remaining part is an important direction for our future research.\n\n> No method to estimate the MI term\n\nWe agree with the reviewer that the very complex structure of the MI term raises several difficulties. (1) we are not aware of existing techniques to evaluate MI between random sets and (2) the dimensionality of $\\mathcal{W}$ (billions of parameters), could make a direct computation intractable.\nWhile these render the MI term uncomputable (as we mention in the limitations), our work focuses on the topological part.\nOur experiments show that these complexities are important and meaningful in addition to being amplified in the first part of the bound, as the dependence is explicit. \n\nNevertheless, as acknowledged by the reviewer, our definition of MI is much simpler than the prior works making it intuitive to understand.\n\n> Can this ensure uniform convergence?\n\nWe thank the reviewer for this very pertinent question.\nLet us first highlight that our use of the term \"uniform\" refers to the bound being uniform over the trajectory, i.e., we look at the worst-case error over the trajectory.\nIn this context, our convergence is uniform. \n\nAs mentioned above, convergence can be ensured with similar information-theoretic terms (which we could use in our work) for particular algorithms, like SGLD [18]. However, in the most general case (eg, a deterministic algorithm), it could lead to vacuous bounds. We acknowledged this lack of understanding in the limitations and we will add further comments. \n\n**Sensitivity to hyperparameters.**\nWe thank the reviewer for suggesting this interesting sensitivity experiment.\nWe performed an analysis of the sensitivity to $s$ for the ViT and CIFAR10 in Fig. 1.a (rebuttal pdf). We observe that the correlation is relatively stable near the two values of $s$ used in our study.\n\nNote that our choice of $\\sqrt{n}$ is theoretically motivated (see lines 216 to 221), and the choice of small $s$ comes from evidence in prior work. We have added these sensitivity experiments in the paper.\n\nWe introduced the parameter $\\tau$ for two reasons: (1) to allow the use of pretrained weights and (2) to capture the geometric properties of the trajectory near a local minimum. Therefore, $\\tau$ is chosen to ensure that the training is near convergence.\nWe did not try to tune the parameter $\\tau$ in any way.\n\nThank you for catching the conflict of notations, we will replace $\\tau$ by $t_0$.\n\n**Comparison with other terms.**\nAs suggested by the reviewer, we conducted a small-scale experiment to compare our complexities with the gradient variance [31] in Fig. 1.b (rebuttal pdf). These preliminary results indicate a comparable correlation performance while slightly favoring our method. \nWe have now included this experiment with gradient variance in the final version and will extend it to further settings.\n\nOn the other hand, the numerical comparison with conditional mutual information (CMI) bounds requires a rigorous re-adaptation of our models and datasets to the CMI analysis, which is not doable within the rebuttal period, but we will consider to try this experiment for the final version. \nWe also point out that our complexities are expected to be much less computationally demanding than CMI. Indeed, one can evaluate them based on a single training and no supersample of data is necessary.\n\nFinally, let us reiterate that, as opposed to most existing works, our measures are meant for the worst-case generalization error (see Section 4).", "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": "EIeuidrj7q", "reviewer": "Reviewer_4cSo", "summary": "Prior work has sought to provably bound the generalization of a neural network based on a complexity measures, eg using some form of evaluation of mutual information between the data and the training path, however such proofs have relied on the topologies from the asymptotic infinite training case and other impractical assumptions. This paper seeks to extend the provable generalization bounds to a practical training regime with discrete time steps. They attempt to make such complexity measures more tractable by, rather than a full derivation of those intrinsic dimension measures utilized in prior works, looking to leverage instead those dependent underlying variables on which intrinsic dimension is based, which are more accesible during training, resulting the the measures of \"alpha weighted lifetime sums\" and \"magnitude\".\n\nIn addition to the forms of experimental validation comparing the complexity measures to a resulting generalization gap, the scope of the paper includes extensive theoretical discussions that are slightly beyond the competence of this reviewer to fully evaluate, and so this review should be considered as taking much of these aspects at \"face value\". That being said, relying on assumption of rigor in such aspects, I believe the scope of the paper and implications of the claims would likely merit some form of recognition from the conference, like an oral presentation or spotlight.", "questions": "Can you further clarify your use of the term \"connected components\"? \nShould we interpret that as the number or ratio of weights impacted by a gradient update step? \nAm I interpretting correctly that with increased connectivity we could expect improved generatlization or is that too simplistic? (After all for the neural tangent kernel at infinite width wouldn't all weights be updated with each gradient step?)\n\nDo you expect that the generalization bounds are asymptotic towards scale of foundation models or can such assumptions be comparably extended to models of limited scope and scale?\n\nCan you clarify how training may be conducted in this form, eg for a simple supervised learning setup, am I correct in assuming that it would it be possible to replace the performance metric but the labels corresponding to training data still be required?", "limitations": "It would be hard to fully validate the claims of \"provable generalization bound\" without some more significant survey of the appendices, which are outside the competence of this reviewer.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- Originality\nI have seen some manner of complexity measures as a form of performance metric discussed in prior work, including things like sharpness measures, however I have yet to see anyone claim bounded forms of generalization guarantees accessible during intermediate stages of training, suggesting that this could be a significant improvement towards such applications.\n\n    - Quality\nThe paper was ambitious in scope and for the most part appeared dense in significance. \n\n    - Clarity\nSome of the benchmarking was more intuitive as the complexity compared to generalization charts as opposed to the Table 1 for instance, I don't know if that could be simplified in some fashion (sometimes less information is better and save the half page of numbers to the appendix for instance).\n\n    - Significance\nTaken at face value the availability of a provable form of generalization guarantee efficiently available in real time during training is potentially quite significant towards mainstream practice.", "weaknesses": "It is hard be this reviewer to fully assess the theoretical merit of the derivations, and hope that some of the other reviewers may be more competent in this sense.", "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 their insightful comments on our work.\n\n> Some of the benchmarking was more intuitive as the complexity compared to generalization charts as opposed to the Table 1 for instance, I don't know if that could be simplified in some fashion \n\nWe believe that Table 1 is quite informative (though compact) as it summarizes a lot of our empirical findings. In order to provide more visual representations of our results, we provided in Fig. 4.c a graphical representation of the performance of our topological complexities in the plane $(\\psi_{\\mathrm{bs}},\\psi_{\\mathrm{lr}})$. This figure contains part of the information of Table 1 along with additional pair (model, dataset). Fig. 1.c is also a graphical representations of the values of $\\Psi$ reported in the table. These two figures therefore contain most of the information from the table. In the next version of the paper, we have completed them by additional plots similar to Fig. 1.c (see Fig. 2.a in the rebuttal pdf for an example). Note moreover that a wide range of plots in the appendix represent the topological complexities against the generalization error. \n\n> It is hard be this reviewer to fully assess the theoretical merit of the derivations\n\nIn order to improve the clarity of the paper, we now added to the main text (thanks to the additional page) a sketch of proof for our main results in the next version of the paper.\n\n> Can you further clarify your use of the term \"connected components\"?\n\nIndeed, our use of the term \"connected components\" in Section 2 might not have been clear enough. It should be understood as follows: given a distance parameter $\\delta>0$ and a point cloud $W$ (which could be one of our training trajectories for instance), we can construct a graph by connecting each pair of points at distance at most $\\delta$ and count the number of connected components of the obtained graph. What we meant by \"tracking the “connected components” of a finite set at different scales\" consists in observing the evolution of these connected components when varying $\\delta$. While this is just an informal introduction to the concept of persistent homology, we provide in Appendix A a more formalized description. In the next version of the paper, we are now more precise about it.\n\n> Should we interpret that as the number or ratio of weights impacted by a gradient update step? Am I interpretting correctly that with increased connectivity we could expect improved generatlization or is that too simplistic?\n\nThe reviewer is right in noticing that if only a ratio of weights are affected by the gradient steps, then the trajectory will be lower dimensional, which might make our topological complexities smaller. However, this is only a particular case and a too simple view of what is happening during training. The topological properties of the trajectory are the consequence of a complex iterative algorithm (see for instance reference [11] in the paper), and capture information that is more complicated than the ratio of updated weights.  The emergence of connected components is considered in a complex recursive way, it is not related to the ratio of weights that are updated. Finally, the NTK is a specific limit with a particular scaling scheme, we do not believe that it can be compared to the observed behavior in our paper. \n\n> Do you expect that the generalization bounds are asymptotic towards scale of foundation models or can such assumptions be comparably extended to models of limited scope and scale?\n\nWhile our work was the first to compute topological generalization measures on neural architecture with real practical interest, applying the same procedures on large language models or other foundation models would still be far too computationally expensive. \n\nHowever, one could imagine a setup where neural networks are embedded in a lower dimensional representation and compute the topological quantities associated with the trajectories in this lower dimensional space. While additional theory would be necessary to understand the true impact of this compression procedure, this might open the door to the computation of topological measures for foundation models. This could be a direction for future research.\n\n> Can you clarify how training may be conducted in this form, eg for a simple supervised learning setup, am I correct in assuming that it would it be possible to replace the performance metric but the labels corresponding to training data still be required?\n\nRegardless of the training procedure, the dataset, and the model, we need two things to compute our topological complexities: a training trajectory and a pseudometric satisfying the condition of Definition 3.1. If the metric is chosen carefully, it could theoretically be applied to any large model as soon as suitable computational resources are available. An interesting setting happens when a large model (eg, a foundation model) is finetuned on a dataset different from the dataset used for pretraining. In that case, to compute our topological complexities, one would only need the dataset used for the fine-tuning procedure and the training data for the inital large model would not be needed.", "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": "s3dy6OtDEy", "reviewer": "Reviewer_bXXR", "summary": "This paper proposes a method to upper-bound the generalization gap $G(w)$ (discrepancy between the empirical risk and the theoretical risk for a given parameter $w$ of our model) by tractable _topological_ quantities. \n\nNamely, given a set $W = \\{w_\\tau,\\dots,w_T\\}$ (typically, a sequence of iterates for a SGD between iterations $\\tau$ and $T$, where $w_\\tau$ is already near a local minima of the empirical risk), the authors derive bounds of the form\n\n$$\\sup_{w \\in W} G(w) \\leq \\sqrt{\\frac{\\text{Topological quantity } + \\text{(Information theory quantity)} + \\log(\\zeta^{-1})}{n}}$$\n\nwith probability $1 - \\zeta$. The work focuses on building actual topological quantities that make this claim true, proposing two possible candidates: \n- The _$\\alpha$-weighted lifetime sums_ that (roughly) computes the maximum spanning tree of $W$ and then assign a weight to it, \n- The _positive magnitude_ that (roughly) computes the positive mass of $\\beta = K_s^{-1} \\mathbb{1}$, where $K_s$ can be understood as a Gaussian/Laplace kernel on $W$ for some distance $\\rho$ and bandwith $s$ (and $\\mathbb{1}$ is a vector full of $1$s). \n\nContrary to previous similar works, their theoretical results directly hold in (mostly) practical situations: they do not require observing a time-continuous trajectory and the quantities involved are (at least theoretically) directly computable (in practice, this requires approximation). \n\nExperimentally, the authors observe through an extensive set of experiments that the upper-bound they propose performs better, in terms of correlation with the actual generalization gap, than the other kind of topological upper-bound previously introduced.", "questions": "1. Could you give (for, say, theorem 3.4) a sort of \"sketch of proof\" and more intuition on \"why this should be true\"?\n\n2. Related to above, in Thm 3.4 (and 3.5), the r.h.s. depends on many parameters on which the l.h.s. doesn't. For instance, it seems that I could pick a different $\\rho$ or $\\alpha$ without affecting the l.h.s. Is that correct? Could I just try to find a $\\rho$ that makes $E_\\alpha^\\rho$ close to $1$ in order to improve my bound?\n\n3. Still in Thm 3.4, would it be in some sense possible that we pick $\\alpha$ below the PH-dim of (roughly speaking) the possible support of the random set $W$, in which case (here again, this is informal) it may be possible that $E_\\alpha$ is unbounded?", "limitations": "Limitations have been discussed by the authors, which is appreciated.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The work proposes an original and promising approach to tackle an important question. \n\nContrary to most previous works, the experiments go way beyond \"toy-models\", and the results are reported on modern architectures like transformers, showing that the method is usable in practice on \"real\" setups. Experimental results are extensively reported, supporting the reproducibility of the work. \n\nThe presentation of related works / comparison of SotA (with which I am not completely familiar) seems to be quite comprehensive.", "weaknesses": "In my opinion, the main weakness is that the (main) paper is kinda far from being self-contained and it is somewhat hard to get an intuitive grasp on the proposed approach. The appendix (about 40 pages!) contains crucial information (proofs, missing definitions, etc.) that couldn't be carefully investigated (*). \n\nWhile the contribution itself is seemingly solid, this prevents me from claiming that the work is theoretically sounded and limit the understanding if one stick to reading the main paper. For instance, if one looks at Theorem 3.4, I cannot understand the role of $\\tau$ and $T$ (as far as I can tell, they only appear in $I_\\infty$ in the rhs, but since this term is not defined I do not know what happend if, say, $T = \\ŧau$ or $T = +\\infty$). Similarly, without reading the proofs, I have no clue on why taking $\\alpha = 1$ should be natural, what is the role played by the constant $q$ in the $(q,L,\\rho)$-Lipschitz assumption, etc. \n\nI understand that being comprehensive is impossible given the space limitation, but I believe that it is part of the contribution to produce an accessible less-than-10-pages-long presentation of the work. \n\n(*) Note that I quickly parsed the supplementary material, which I found quite enlightening, but cannot guarantee the correctness of its content.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time spent on the paper and their insightful comments. \n\nWe address below the main questions (alongside weaknesses).\n\n**Could you give (for, say, theorem 3.4) a sort of \"sketch of proof\" and more intuition on \"why this should be true\"?**\n\nFirst, we would like to point our that even though the appendix is long, most of it is dedicated to additional empirical results and figures, while the proofs are a relatively short portion of the appendix.\n\nIncluding a sketch of proof is a very good suggestion from the reviewer. In the next version of the paper, we now include a sketch of proof of Theorem 3.4. The general idea is the following: we build on Corollaries 26 and 27 of the reference [18] of our paper, to get a bound of the worst-case generalization error as (this is an informal statement, in particular we omit absolute constants and less relevant terms, refer to the paper for more details):\n$$\nG \\lesssim \\sqrt{\\frac{N_\\delta}{n}} + \\sqrt{\\frac{\\mathrm{IT}}{n}},\n$$\nwhere $N_\\delta$ is a covering number of the trajectory and $\\mathrm{IT}$ is an information-theoretic term. First, we use lemma 16 of [11] to show that $\\mathrm{IT}\\leq I_\\infty$, where $I_\\infty$ is the mutual information term appearing in Theorem 3.4. Second, we bound $N_\\delta$ in terms of packing numbers, denoted $P_\\delta$ (see Definition A.15), which we further bound in terms of $E_1$ (or in general $E_\\alpha$ for $\\alpha \\leq 1$) using a geometric construction displayed on Figure 2.b (rebuttal pdf). We have now included this figure to the paper to provide more intuition on the proof technique, which is based on this geometric observation. \n\nFor theorem 3.5, we can mention that the key difference is Lemma B.13, whose proof is short but contains the essential ideas behind this theorem. It relies on properties of magnitude that are detailed in the appendix.\n\n\n**Related to above, in Thm 3.4 (and 3.5), the r.h.s. depends on many parameters on which the l.h.s. doesn't. For instance, it seems that I could pick a different $\\rho$ or $\\alpha$ without affecting the l.h.s. Is that correct? Could I just try to find a $\\rho$ that makes $E_\\alpha^\\rho$ close to $1$ in order to improve my bound?**\n\n It is true that some of our bounds depend on free parameters. \nAs noted by the reviewer, this is in particular true for the constant $\\alpha \\in [0,1]$ and the pseudometric $\\rho$, as soon as $\\rho$ satisfies the regularity condition given by Definition 3.1. Let us discuss these two quantities separately.\n\n> Choice of $\\alpha$\n\n First, regarding the choice of $\\alpha$, the only pertinent choice in general seems to be $\\alpha=1$, which is what we choose in our experiments. The reason why this choice is natural is that the $\\alpha$-weighted lifetime sums tend to be higher when $\\alpha$ gets smaller. In the case where the random set is finite, $E_0$ even corresponds to the cardinality of the set and does not capture any meaningful topological behavior (moreover, it goes to infinity when the size of the set goes to infinity). The reviewer may consult [61] for better intuition about the behavior of this quantity.\n\n> Choice of $\\rho$ and $q$\n\n Second, for the choice of $\\rho$, the possibilities might not always be numerous. Indeed, $\\rho$ must satisfy a $(q,L,\\rho)$ condition as in Definition 3.1. The choice of $\\rho$ impacts the bound both by affecting the topological quantity ($E_\\alpha^\\rho$ in the case of Theorem 3.4) and the value of $q$ and $L$. It should be noted that the pseudometrics $\\rho_S^{(q)}$ (with $q\\geq 1$) appear in Example 3.2 always satisfy the $(q,1,\\rho_S^{(p)})$-Lipschitz condition. In that particular case, it seems that choosing $\\rho_S := \\rho_S^{(1)}$ is the best choice because of Hölder's inequality: $\\forall q \\geq 1,~ \\rho_S \\leq \\rho_S^{(q)}$. The fact that $q=1$ is a good choice is particularly apparent in the proof of Theorem 3.5, for this exact reason. When more pseudometrics are admissible, the reviewer is right to notice that there could be an optimal choice giving the best bound. In the final version of the paper, we discuss in more detail the choice of these parameters. \n\n> I cannot understand the role of $\\tau$ and $T$\n\nThe meaning of these parameters is that we collect the training trajectory between iterations $\\tau$ and $T$. While it is technically possible to chose $\\tau=T$, it means that the trajectory would be reduced to a single point and therefore it does not contain any interesting topological information. Similarly, taking $T\\to\\infty$ seems to be possible under mild assumptions, even though it is not our focus. \n\nNote that our topological complexities also depends implicitly on $\\tau$ and $T$, as they are evaluated on the trajectory between iterations $\\tau$ and $T$.\n\n **Still in Thm 3.4, would it be in some sense possible that we pick $\\alpha$ below the PH-dim of (roughly speaking) the possible support of the random set $W$, in which case (here again, this is informal) it may be possible that $E_\\alpha$ is unbounded?**\n\n This is a pertinent question from the reviewer. In the case that is of more interest for our experiments, the random set $W$ is finite, which makes the $\\alpha$-weighted lifetime sums bounded for any value of $\\alpha$. That being said, if one extends our theory to infinite sets (which is technically possible for most aspects, even though some statements should be reformulated), the value of $\\alpha$ should indeed be carefully chosen with respect to the dimension of the set. Even in our experimental setting, if the size of the set goes to infinity, it might be pertinent to take into account the dimension of the \"limiting set\" to tune the value of $\\alpha$, keeping in mind that it must satisfy $\\alpha \\in [0,1]$. However, this setting is largely theoretical as the sets are large but finite in practice. In the final version of the paper, we added a discussion about this interesting question from the reviewer.", "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:
The rebuttal pdf includes figures that are mentioned in some of our answers to the reviewers.

Fig. 1.a analyses the sensitivity to $s$ of the correlation between the generalization error and $\mathrm{PMag}(s\mathcal{W})$.
Fig. 1.b is a preliminary result regarding the comparison of our topological complexities with gradient variance.
Fig. 2.a is a visual representation of some results of Table 1, it completes Fig. 1.c. in the paper.
Fig. 2.b is a graphical representation of (part of) the proof of Theorem 3.4.

Meta-review: First I want to thank all of the reviewers for the work they put in and for the authors on engaging with the reviewers and correcting several things in the paper following the discussion. 

Given the review and the quality of work, i am more than happy to recommend this paper for acceptence to NeurIPS.

Best wishes,

    AC
Decision: Accept (poster)