Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms

Authors: rayna  andreeva
benjamin  dupuis
rik  sarkar
tolga  birdal
umut  şimşekli
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:06:27

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.

Main paper: 
 introduction: 
 Generalization, a hallmark of model efficacy, is one of 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: ) between weights as in [10] or via the loss-induced pseudo-metric (ρ S ) as in [21] . (c) plots the average granulated Kendall coefficients for two of our generalization measures (E α and PMag( √ n)) in comparison to the state-of-the-art persistent homology dimensions [10, 21] for a range of models, datasets, and domains, revealing significant gains and practical relevance.EQUATIONwhere z ∈ Z := X × Y denotes the data, distributed according to a probability distribution µ z on the data space Z. In practice, as µ z is unknown, ML algorithms focus on minimizing the empirical risk,EQUATIONwhere S := (z 1 , . . . , z n ) ∼ µ ⊗n z := µ z ⊗ • • • ⊗ µ z , which means that (z 1 , . . . , z n ) are independent samples from µ z . In many applications, the minimization of ( 2) is achieved by discrete stochastic optimization algorithms, such as stochastic gradient descent (SGD) or the ADAM [40] method. Such algorithms generate a sequence of iterates in R d , denoted W S := {w k } k≥0 , which depends on the data S, the initialization w 0 ∈ R d , 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: G S (w k ) := R(w k ) -R S (w k ).(EQUATIONThe empirical risk (2) typically has numerous local minima, which raises the question of how to characterize their generalization properties. Recently, training trajectories (cf., Figure 1a ) have been shown to be paramount to answer this question [84, 28] . Indeed, these trajectories can quantify the quality of a local minimum in a compact way, because they depend simultaneously on the algorithm, the hyperparameters, and the data, which is crucial for obtaining satisfactory bounds [37] . A wide family of trajectory-dependent bounds has been developed [84, 28, 50, 4, 36] . For instance, several results on stochastic gradient Langevin dynamics [57, 64, 49] , continuous Langevin dynamics [57] and SGD [59] take into account the impact of the whole trajectory on the generalization error.Parallel to these developments, several studies have brought to light the empirical links between topological properties of DNNs and their generalization performance [58, 52, 66, 70, 83] , hereby making new connections with topological data analysis (TDA) tools [2] . These studies focus on the structural changes across the different layers of the network [51] or on the final trained network [66, 70, 83] , and are almost exclusively empirical. This partially inspired a new class of trajectorydependent bounds focusing on topological properties of the trajectories. In particular, recent studies [78, 21, 35, 22, 10, 3] have proposed to relate the generalization error to various kinds of intrinsic fractal dimensions [26, 53] that characterize the learning trajectory. Informally, these bounds provide the guarantee that with probability at least 1ζ, we have:EQUATIONwhere dim(W S ) 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 informationtheoretic quantity that takes different forms among different studies. Despite providing rigorous links between the topology of the trajectory and generalization, these bounds have major drawbacks. First and foremost, as noted in [75, 76, 13] , fractal-trajectory bounds, such as Equation ( 4), do not apply to discrete-time algorithms. This creates a discrepancy between these theoretical results and the TDAinspired methods to numerically evaluate them on commonly used discrete algorithms [10, 21, 3] . Additionally, existing bounds rely on intricate geometric assumptions, such as Ahlfors-regularity [78, 35] or geometric stability [21] , that are not realistic in a practical, discrete setting.Previous attempts were made to address this discretization issue. Specifically, under the assumption that the training dynamics possess a stationary measure µ ∞ w|S for T → ∞ (T is the number of iterations), it was shown in [13] that with probability 1ζ over S ∼ µ ⊗n z and w ∼ µ ∞ w|S , we have:EQUATIONwhere dim(µ w|S ) corresponds to the fractal dimension of the measure µ w (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 [71] or fine properties of the Markov transition kernels associated with the dynamics [35] . However, these studies also rely on impractical assumptions and involve intricate quantities which make them not amenable to numerical evaluation.Despite the theoretical limitations of existing topology-dependent generalization bounds, TDAinspired tools have been developed to numerically estimate the proposed intrinsic dimensions in practical settings. Two particular methods have emerged and successfully demonstrate correlation with the generalization error, based on persistent homology [10, 21] (PH-dim) and metric space magnitude [3] (magnitude dimension); these two dimensions are equivalent for compact metric spaces [3] . Because of the limitations discussed above, existing theories do not account for these experiments, conducted with finite-time discrete algorithms. Moreover, existing empirical studies [10, 21, 3, 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-inspired generalization bounds that rigorously apply to widely used discrete-time stochastic optimization algorithms, and experimentally test our new topological complexities 2 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 α-weighted lifetime sums [73, 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:sup w∈W SG S (w) ≲ (Topological complexity) + IT + log(1/ζ) n .• We then provide a flexible computational implementation based upon dissimilarity measures between neural nets (Figure 1b ), which enables quantifying generalization across different architectures and models, without the need for domain or problem-specific analysis as done in [39, 8] .• Unlike existing trajectory-based studies [10, 21] operating on 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 1c ).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 additional experiments. We will make our entire implementation publicly available under: https://github.com/rorondre/TDAGeneralization. 
technical background: 
 Our generalization indicators will be based upon α-weighted lifetime sums and magnitude, capturing different topological features, as we shortly dicsuss below. Let (X, ρ) be a finite pseudometric space. α-weighted lifetime sums. Persistent homology (PH) is an important concept in the analysis of geometric complexes [11] . We focus on the persistent homology of degree 0 (PH 0 ). Informally, it consists in tracking the "connected components" of a finite set at different scales. We provide in Sections A.3 and A.4 exact definitions of this notion. For simplicity, we present here an equivalent formulation of the α-weighted lifetime sums based on minimum spanning trees (MST) [42, 73] .A tree over X is a connected acyclic undirected graph (a set of edges) whose vertices are the points in X. Given an edge e linking the points a and b, we define its cost as |e| := ρ(a, b). An MST T on X is a tree minimizing the total cost e∈T |e|. The α-weighted lifetime sums E ρ α are then written as:∀α ≥ 0, E ρ α (X) := e∈T |e| α .The celebrated persistent homology dimension (PH-dim) [1] , of a compact pseudometric space (A, ρ) is then defined as dim ρ PH (A) = inf α≥0 {∃C > 0, ∀Y ⊂ A finite, E α (Y ) ≤ C}. The PH-dim has been proven to be related to generalization error for different pseudometrics ρ [10, 21] .Magnitude. Magnitude is a recently introduced topological invariant [46] which encodes many important 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 s > 0, we define a weighting of the modified space (X, sρ) as a map β : X → R, such that ∀a ∈ X, b∈X e -sρ(a,b) β(b) = 1. Given such a weighting β, the magnitude function of (X, sρ) is defined asEQUATIONThe parameter s > 0 should be interpreted as a "scale" through which we look at the set (X, ρ). 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 it to 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 ρ Mag (A) = lim s→∞ log Mag(sA) log(s). It is known that dim ρ PH and dim ρ Mag coincide for compact metric spaces [56, 73, 3] . As a result, dim ρ Mag has also been proposed as a topological generalization indicator [3] . Total mutual information. Prior intrinsic dimension-based studies relied on "mixing" assumptions ([78, Assumption H5], [10, Assumption H1], [76, 13] ) 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-theoretic (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 a total mutual information between the data S and the training trajectory W S . This term is denoted I ∞ (S, W S ) and measures the dependence between S and W. We refer to Appendix A.1 and [35, 81] for exact definitions. 
main theoretical results: 
 We now introduce our learning-theoretic setup (section 3.1) before delving into our main theoretical results in Sections 3.2 and 3.3.Random trajectories. The primary goal of our theory is to prove uniform 3 generalization bounds over the training trajectory {w k , k ≥ 0}. We are mostly interested in the behavior near local minima of R S . To this end, we observe the trajectory between iterations t 0 and T , where t 0 ∈ N is the number of iterations before reaching (near) a local minimum and T ≥ t 0 is the total number of iterations. Therefore, we consider the set W t0→T := {w i , t 0 ≤ i ≤ T }, which we call the random trajectory. Note that W t0→T is a set, i.e., it does not contain any information about the time-dependence. Moreover, our setup allows the random times t 0 and T to depend on the data S through the choice of a stopping criterion as opposed to being fixed predetermined times.General Lipschitz conditions. The topological quantities described in section 2, as well as the intrinsic dimensions introduced in prior works [78, 10, 3, 21, 22] , require a notion of distance between parameters (in R d ) to be computed. In the case of fractal-based 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 a more general family of pseudometrics on the parameter space R d . In order to fully characterize this family of pseudometrics, we define the data-dependent map L S : R d -→ R n by L S (w) = (ℓ(w, z 1 ), . . . , ℓ(w, z n )). To fit into our framework, a pseudometric must satisfy the following general Lipschitz condition. Definition 3.1 ((q, L, ρ)-Lipschitz continuity). For any pseudo-metric ρ on R d and q ≥ 1, we will say that ℓ is (q, L, ρ)-Lipschitz in w when ∀w,w ′ ∈ R d , ∥L S (w) -L S (w ′ )∥ q ≤ Ln 1/q ρ(w, w ′ ).A wide variety of distances have been proposed to compare the weights of two DNNs [19] . The above condition restricts our analysis to a family of pseudometrics containing the following examples. Example 3.2 (Data-dependent pseudometrics). For any p ≥ 1, we define the pseudometrics ρ(p) S (w, w ′ ) := n -1/p ∥L S (w) -L S (w ′ )∥ p . The case ρ (1)S corresponds to the "data-dependent pseudometric" used in [21] ; we will denote it ρ S := ρ (1)S . Example 3.3 (Euclidean distance). If ℓ(w, z) is L-Lipschitz continuous in w, i.e., |ℓ(w, z) - ℓ(w ′ , z)| ≤ L∥w -w ′ ∥ for all z, then ℓ is (p, L, ∥•∥ 2 )-Lipschitz continuous for every p ≥ 1.Assumptions. Given an (q, L, ρ)-Lipschitz continuous (pseudo-)metric, our approach relies only on a single assumption of a bounded loss function. For the case of the pseudometric ρ S (Example 3.2), this assumption is already made in [21, 22] . Assumption 1. We assume that the loss ℓ is bounded in [0, B], with B > 0 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 [21] , 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.In contrast to all existing fractal dimension-based bounds [78, 10, 13, 21] , we propose new generalization 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, E α and Mag, defined in section 2. We are now ready to state the first generalization bound in terms of the α-weighted lifetime sums, where we denote E ρ α for E ρ α (W t0→T ). Theorem 3.4. Let ρ be a pseudometric on R d . Supposes that Assumption 1 holds and that ℓ is (q, L, ρ)-Lipschitz, for q ≥ 1. Then, for all α ∈ [0, 1], with probability at least 1ζ, we have:sup t0≤i≤T G S (w i ) ≤ 2B 2 log (1 + K n,α E ρ α ) n + 2B √ n + 3B I ∞ (S, W t0→T ) + log(1/ζ) 2n , with K n,α := 2 (2L √ n/B) α .The term I ∞ (S, W t0→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 W t0→T and the data S ∼ µ ⊗n z . Such MI terms appear in previous works related to fractal-based generalization bounds [78, 13, 21, 35] . Our proof technique, presented in Appendix B.5, makes use of a recently introduced PAC-Bayesian framework for random sets [22] to introduce this MI term. It is also shown in [22] that the MI term I ∞ (S, W t0→T ) 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 S (ViT on CIFAR10).finite subsets of the trajectory are used in [10] to estimate the PH-dim, it does not provide any formal link between the generalization error and the value of E α . Therefore, the above theorem could not be cast as a corollary of these previous studies. Another important characteristic of the above theorem (as well as the results of section 3.3) is to be non-asymptotic, i.e., it is true for every n ∈ N * . This is an improvement over the fractal dimensions-based bounds presented in [78, 10, 21, 22] .Recent preliminary experimental results displayed a correlation between the generalization error of DNNs and magnitude [3] . To provide a theoretical justification for this behavior, it would be tempting to mimic the proof of Theorem 3.4 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 to our finite and discrete setting where the dimension is 0. Hence, we identify a new quantity, closely related to magnitude, while being more relevant to learning theory. With the notations of section 2, we fix a finite metric space (X, ρ) and a weighting β s : X -→ R of (X, sρ), where s > 0 is a "scale" parameter. We define the positive magnitude asEQUATIONwhere x + := max(x, 0) denotes the positive part of x. To avoid harming the readability of the paper, we refer to Appendix B.3 for the extension of PMag to the pseudometric case. Based on a new theoretical approach, we prove that the positive magnitude can be used to upper bound the generalization error (see the proof in Appendix B.7). This leads to the following theorem: Theorem 3.5. Let ρ be a pseudometric such that (W, λρ) admits a positive magnitude (according to Definition B.5) for every λ > 0. We assume that ℓ is (q, L, ρ)-Lipschitz continuous with q ≥ 1. Then, for any s > 0, we have with probability at least1 -ζ that sup t0≤i≤T G S (w i ) ≤ 2 s log PMag ρ (LsW t0→T ) + s B 2 n + 3B I ∞ (S, W t0→T ) + log(1/ζ) 2n .We now present a quick sketch of the proof of Theorem 3.5, in order to highlight its key elements.Proof. (Sketch) Let W be a data-dependent random compact set (e.g., W t0→T ). The proof is based on two technical elements. The first is 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:sup w∈W G S (w) ≲ Rad(ℓ, W t0→T ) + I ∞ (S, W t0→T ) + log(1/ζ) n ,where Rad(ℓ, W t0→T ) is the celebrated Rademacher complexity [5] , whose definition is given in Appendix A. The IT term (I ∞ ) in the above result is the same as in Theorem 3.4. Given a fixed (finite) set W and a big enough s, we establish Mag(sW) = PMag(sW). Moreover, we present in Figure 2a an empirical comparison of Mag and PMag, showing a small and almost monotonic relation between both quantities. Therefore, Theorem 3.5 may be seen as the first theoretical justification of the empirical relationship between magnitude and the generalization error observed in [3] .A natural choice for the scale s would be s ≈ √ n, ensuring a convergence rate in n -1/2 . However, our empirical evaluations (see section 5, in particular, Table 1 ) revealed that small values of s (we typically use s = 10 -2 ) can also provide good correlation with the generalization error. This could be explained by the fact that PMag(sW) → 1 as s → 0, i.e., the bound may not diverge when s → 0. For our topological complexities to be computationally efficient, we focus our experiments on fixed values of s (in √ n, 10 -2 ). We further analyze the sensitivity of part of our experiments to the value of s in Appendix D.2.2. We will omit the trajectory and denote Mag(s) and PMag(s). Remark 3.6. As it is explained in Appendix B.7, a key element in the proof of Theorem 3.5 is a newly discovered link between the celebrated Rademacher complexity [5] and positive magnitude. This is 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. 
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 [65, 7] . This setup is inspired by PH frameworks used in [10, 21] . 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 α is 1; similar to [10] , this is 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.linsys.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 a finite set (i.e., a trajectory) W ⊂ R d , the calculation of our topological complexities requires computing the distance matrix D ρ := (ρ(w, w ′ )) w,w ′ ∈W . For large DNNs, this may become challenging. Depending on ρ, 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-Lindenstrauss lemma [82] to project the trajectories onto a lower-dimensional 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 A.7 for details.• Case 2: If ρ is of the form ρ (q) S as in Example 3.2, then the computation of D ρ requires the evaluation of the model on the entire dataset at each iteration, which becomes intractable for large DNNs. In [21, Figure 3 ], the authors show that the PH-dim based on the pseudometric ρ S = ρ (1) S is very robust to a random subsampling of a training dataset, i.e. when ρ S is replaced by ρ B with B ⊆ S and |B|/|S| ≪ 1. Figure 2b shows that E α and positive magnitude are also robust to this subsampling. We mainly used |B|/|S| = 10%. We refer the reader to Appendix C.2 for details.Generalization error. Our theory, like many trajectory-based studies [78, 10, 21, 3] predicts upper bounds on the worst-case generalization error over the trajectory W t0→T . 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 t 0 and T (every 100 iterations) and reported (worst test riskfinal train risk) as the error in our experiments. This is consistent as we start the trajectory W t0→T from a weight w t0 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. 
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 a dataset, we start from a pre-trained weight vector w t0 , yielding high training accuracy on classification tasks. By varying the learning rate (η) and the batch size (b), we define a grid of 6 × 6 hyperparameters. For each pair (η, b), we compute the training trajectory W t0→T for 5 × 10 3 iterations. Unless specified, we use the ADAM optimizer [40] . Based on W t0→T , we estimate distance matrices as described in section 4. For the sake of clarity, we focus on 3 relevant pseudometrics: (i) the Euclidean distance ∥•∥ 2 as in [10] , (ii) the data-dependent pseudometric ρ S , used in [21, 3] , and (iii) the 01-loss distance. For (ii), ρ S 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 4). For the last one (iii) ρ is defined as in Example 3.2, but with ℓ being the 01-loss; we call it 01-pseudometric 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, 21, 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 CIFAR100 [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 τ ) 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., ψ LR for η and ψ BS for b); it measures the correlation when only this hyperparameter is varying. In Table 1 , we report τ , ψ LR and ψ BS , and the averaged GKC, Ψ := (ψ LR + ψ BS )/2, for several models, datasets and topological complexities. In Figures 4a and 4b , we represent our topological complexities in the plane (ψ BS , ψ LR ); 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 1, would not impact the correlation between generalization and topological complexities that is observed in our experiments.As explained above, we focus our main experiments on the quantitiesE 1 , Mag( √ n), PMag( √ n),Mag(10 -2 ) and PMag(10 -2 ), each computed for the 3 pseudometrics discussed above (∥•∥ 2 , ρ S , 01). In the interest of comparison, we also compute the PH-dim (proposed in [10] for the ∥•∥ 2 and in [21] for ρ S ), which is thus tested for the first time on transformers and GNNs. Performance on vision transformers. We see in Table 1 and Figure 3 (additional graphical representation is given in Appendix D.1) 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 on small architectures, is less scalable to industry-standards models with more parameters. Figure 4a , including all (model, dataset) pairs for the pseudometric ρ S , 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, dim PH has a small or negative ψ BS , indicating that it has less ability to explain generalization for varying batch-sizes. As it was observed in [21] for PH-dim, our complexities computed from the pseudometric ρ S 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 encapsulate different data domains. In particular, 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, 8] . The results of Table 1 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( √ n) performs significantly well for GNNs, and in particular better than PMag( √ n). This points us towards the idea that further theory would be desirable to formally relate magnitude to the generalization error in that case 4 .Comparison of the topological complexities. In Table 1 and Figures 3 and 4a , it can be seen that E 1 and PMag( √ n) perform equally well for the image and graph experiments across multiple datasets, models, and data domains. We see in Table 1 that most topological complexities perform better with data-dependent metrics (i.e., ρ S and 01) than with the Euclidean distance, for transformer-based experiments. This extends results obtained for PH-dim in [21] , for smaller architectures. However, the poor performance of Euclidean-based complexities may also be partially caused by the projections applied to the Euclidean distance matrices to make them memory-wise computable (see section 4). This is a remaining limitation of our algorithms. On the other hand, the 01 and ρ S data-dependent pseudometrics seem to 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 ρ S and obtained from the SGD trajectories, exhibits high GKCs. This observation agrees with the results in [21] . Figure 3 further displays the typical behavior of several topological complexities for ViT and CIFAR10. In addition to the correlation of our proposed complexities being stronger than for the PH-dim, we observe that E α and PMag( √ n) seem to better correlate with the generalization gap for small learning rates. Finally, it is consistently observed in Table 1 and Figures 4a and 4b that using a relatively high value of the (positive) magnitude scale (s = √ n) 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 CIFAR10 and Swin for CIFAR100 in Table 1 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. 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 α-weighted lifetime sums and a new variant of metric space magnitude, which we called positive magnitude. Compared to previous studies, we require fewer assumptions and operate in a discrete setting in which our proposed quantities are fully computable. Our algorithms are flexible enough to be seamlessly integrated with diverse data domains and tasks. These advantages of our framework allowed us to create a computationally cheap experimental setup, as close as possible to the theoretical setup. We thus provided a comprehensive suite of experiments with several industry-relevant 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, we are not aware of existing techniques to evaluate the MI between random sets and the dimensionality of W t0→T (billions of parameters) could make a direct computation intractable. Nevertheless, our work focuses on 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 is explicit. Moreover, a better understanding of the behavior of positive magnitude for small values of the scale factor s would be a necessary improvement. Regarding our experiments, a 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We specified in Section C the compute resources we used to run our experiments.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 in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 • Released models that have a high risk for misuse or dual-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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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] Justification: Our algorithms to evaluate the topological complexities that we propose, as well as the baselines, make use of existing libraries and codes that are clearly stated in Sections 4 and 5.Guidelines:• The answer NA means that the paper does not 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 a URL. • The name of the license (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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, a version of our code that contains the algorithms described in the paper, along with documentation provided in a README.md file. Our code will be made publicly available and will be clearly documented regarding what are the existing and new assets, as it 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 as 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 is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
 
 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:• Appendix A 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 a few additional theoretical contributions. • In Appendix C, we show the experimental details needed to reproduce our experiments.• Finally, Appendix D is dedicated to additional empirical results.The following definition is a precise definition of the total mutual information term that appears in our main theoretical results. The reader may consult [81, 35, 22] for further information on this notion. Definition A.1 (Total mutual information). Let X and Y be two random elements defined on a probability space (Ω, 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:I ∞ (X, Y ) = log sup A P X,Y (A) P X ⊗ P Y (A).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, 10, 3, 13] . We stress the fact that our proposed bounds are simpler.Rademacher complexity [6, 77] is a 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 ∈ Z n , a set W ⊂ R d and ϵ = (ϵ 1 , . . . , ϵ n ) some iid Rademacher random variable. 5 Whenever it is defined, we will call Rademacher complexity of ℓ over W the following quantity:Rad(ℓ, W, S) := 1 n E ϵ sup w∈W n i=1 ϵ i ℓ(w, z i ) .Rademacher complexity has already been used in [21, Theorem 3.4] to relate the generalization error to the so-called data-dependent fractal dimension. Part of our theory is based on a recent extension of such arguments in the data-dependent setting [22] .The goal of this short subsection is to present a few notions of persistent homology, which is necessary for a better understanding of our contributions.Persistent homology [24, 14, 11] 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, 25] , to materials science [34] , finance [45] , robotics [9] , sensor networks [18] and a lot more [61] . The types of datasets which are 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 to light empirical links between persistent homology and DNNs [70, 17, 66] . In particular, recent studies have related the worst-case generalization error to several concept of intrinsic dimensions defined through persistent homology [10, 21] . 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 ∈ N (denoted PH k ). Intuitively, PH k keeps track of the number of "holes of dimension k" in a set when looked at different scales. However, in our work and as in [10, 21] , we only use PH 0 , whose presentation is simpler. In this section, to avoid harming the readability of the paper, we only present a high-level introduction to PH 0 that is sufficient to understand our work. The interested reader may consult [11, 15, 87] for a more in-depth introduction to persistent homology.We first start by introducing briefly homology, which is a 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 a set K of finite sets closed under the subset relation: if σ ∈ K and τ ⊂ σ, then τ ∈ K.In the above definition, σ is a 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 a simplex in K. Definition A.5. A simplicial k-chain is the formal sum of k-simplices,EQUATIONwhere each r i ∈ R, where R is a fixed commutative ring with additive identity 0 and multiplicative identity 1, and σ i ∈ K.K k 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 K k . For each generator σ, the boundary of σ is the sum of all (k -1)-faces of σ. Definition A.6. The boundary of a k-simplex σ = (x 0 , . . . , x k ) is the (k -1)-chainEQUATIONwhere (x 0 , . . . , xi , . . . , x k ) is the (k -1)-simplex spanned by all vertices without x i .It is common that the coefficients for homology are considered to be restricted to Z 2 , which is the field with 2 elements, 0 and 1, where 1 + 1 = 0. However, the theory extends to homoogy with coefficeints in any field (and since every field is a ring, the definitions in terms of rings are more general). Definition A.7. A chain complex is a sequence of abelian groups A k with homomorphisms (called boundary maps)∂ k : A k → A k-1 , such that ∂ k-1 • ∂ k = 0 for all k.We should note that when considering coefficients in Z 2 , 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 a finite simplicial complex K isEQUATIONwhere ker and im are the kernel and image respectively of the boundary operator.In order to define the simplicial complexes of use in TDA, we need to first understand what a nerve is. Definition A.9 (Nerve). A simplicial complex associated to a collection of sets is called a nerve. The sets are the vertices of the complex, and a simplex belongs to a complex iff its vertices have a non-empty intersection, Nrv = {α ⊆ S | ∩ A∈α A ̸ = ∅}.Definition A.10 ( Čech complex). The Čech complex of X for radius r is Čech r (X) = Nrv{B(x, r) | x ∈ X}, where B(x, r) is the closed ball of radius r ≥ 0, centered at x.In other words, the Čech complex is the nerve of the ball neighbourhoods of a set of points X ⊆ R n . The Čech complex faithfully captures the topology of the space, but it is not computed in practice due to its high computational cost. Instead, a 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 to the Čech complex, and therefore it can be seen as an approximation.We first need to introduce the notion of a clique complex to explain what the VR is. Definition A.11 (Clique complex). The clique complex for a graph G = (V, E) consists of all cliques of G, which are all simplices α ⊆ V for which E contains all edges of α.Now we have explicitly states all the necessary components in order to 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, Ripsr (X) = {α ∈ X | ||u -v|| ≤ 2r} for all u, v ∈ α.Now that we have defined the most important complex in TDA, we proceed to explain how we can derive important topological information at multiple scales by introducing the concept of a filtration. Definition A.13. Given a simplicial complex K, a filtration is a totally ordered set of subcomplexes K i of K, indexed by nonnegative integers, such that for i ≤ j, K i ⊆ K j .Definition A.14 (Filtered simplicial complex). A simplicial complex, K, together with a filtration (functionf : K → R such that f (σ) ≤ f (τ ) whenever σ is a face of τ ). The sublevel set at a value r ∈ R is f -1 (-∞, r], which is a subxomplex of K. Let r 0 < r 1 < • • • < r m bethe values of the simplices, andK i = f -1 (-∞, r i ], then we call K 0 ⊆ K 1 ⊆ • • • ⊆ K m 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 r evolves as the radius r 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 of 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 is recorded in a set of intervals known as barcodes, which can be represented as a multiset of points in R 2 , where the coordinates correspond to the birth and death points of each interval.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-standard (though equivalent) definition of PH 0 .Definition A.15 (Persistent homology of degree 0 (PH 0 )). Let (X, ρ) be a finite metric space and N its cardinality. For each time 6 t ≥ 0, we construct an undirected graph G t , whose edges are given by:∀x, y ∈ X, {x, y} ∈ G t ⇐⇒ ρ(x, y) ≤ δ.There exists a finite set of times 0 < t 1 • • • < t k < +∞ such that the number of connected components in G ti changes compared to G t for t < t i . Let c i be the number of connected components in G ti . By convention we set c 0 = N and t 0 = 0 and define n i := c ic i-1 . PH 0 is then defined as the following multiset (the notation {{•}} denotes multisets):PH 0 :=       t 1 , . . . , t 1 n1 times , t 2 , . . . , t k , . . . , t k n k times       .Remark A.16 (Vietoris-Rips filtration). The above is a simplified high-level definition of PH 0 . More formally, the construction of the family of graphs G t corresponds to the construction of the so-called Vietoris-Rips filtration of X, of which we only kept the simplices of dimension 1, see [11] for more details.We now use PH 0 to give the definitions of the quantities of interest in our work. The following is a definition of the quantity E α already mentioned in section 2, but seen through the lens of persistent homology. As it will be explained in Appendix A.4, these definitions are equivalent. Definition A.17 (α-weighted lifetime sums). With the same notations as in Definition A.15, we define the α-weighted lifetime sums as:∀α ≥ 0, E ρ α (X) := t∈PH 0 t α .Remark A.18 ("birth" and "death" times). PH k is usually defined as a multiset of birth and death times, tracking the appearance and disappearance of "holes of dimension k" during the construction of the Vietoris-Rips filtration of X. In the particular case of PH 0 , all birth times are 0 and the times that we constructed correspond to 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 of neural networks in prior works [10, 21] . Definition A.19 (Persistent homology dimension of degree 0). Given a compact metric space (X, ρ), we define the PH dimension of degree 0 by:dim ρ PH (X) := inf {α ≥ 0, ∃C > 0, ∀A ⊆ X finite, E α (A) ≤ C} .It has been shown in [42, 73] that for any compact metric space, the PH dimension defined above is equal to the celebrated upper box-counting dimension [26, 54] .The persistent homology dimension used in existing generalization bounds [10, 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 of 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 to MSTs which will play an important role in our proofs.In this section let us fix a finite metric space (X, ρ). Let us first specify our notations for trees. A tree T on X is a connected undirected graph. We represent T by its set of edges, which are denoted a → b (or equivalently b → a as the graph is undirected). For an edge e of the form a → b, we define its length by |e| = ρ(a, b). Definition A.20 (Minimum spanning tree). Let us define the cost of a tree by the sum of the length of its edges, i.e.,E MST 1 (T ) := e∈T |e|.An MST of X is defined as a tree with minimal cost. A consequence of the greedy algorithm to find such an MST [16] is that an MST T is also minimal for any of the following costs:E MST α (T ) := e∈T |e| α , with α ≥ 0.Our interest in this notion comes from several results that are summed up in the following theorem.The reader can refer to [1, 73, 11] for more details. Theorem A.21 (Link between MST and persistent homology). There is a bijection between the two following multisets:• The multiset of the lifetimes in the persistent homology of degree 0 of the Vietoris-Rips complex of X.• The multiset of the length of the edges of an MST of X.Therefore, if we fix some α ≥ 0, the weighted α-sum associated to the persistent homology of degree 0 of the Vietoris-Rips complex of X is equal to the cost E α of an MST of X, ie:E MST α (T ) = E α (X). In all the following, we will use the notation E α to denote both quantities.Let us restate formally a few standard definitions. The reader may refer to [46, 55, 56] for more details on the notions of magnitude, weighting, and positive definite metric spaces. In this section, we fix a finite metric space (X, ρ). Some of the presented concepts will be later extended to pseudometric spaces in Appendix B.2.As before, the similarity matrix [46] of X is defined by M (a, b) = e -ρ(a,b) , for a, b ∈ 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 a function β :X -→ R such that ∀a ∈ X, b∈X e -ρ(a,b) β(b) = 1.If such a weighting exists, the magnitude of X is defined by:Mag(X) := b∈X β(b).It is easily seen that this definition is independent of the choice of weighting β. When a weighting exists, we say that X "has magnitude".Based on such a definition, it is natural to inquire, whether such a 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 now define, according to [46] . Definition A.23 (Positive definite space). X is positive definite if the similarity matrix M is 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 p ∈ [1, 2] and d ≥ 1, every finite subset of (R d , ∥•∥ p ) is positive definite.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 in 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 to derive uniform generalization bounds in terms of fractal dimensions [78, 35, 13, 21, 22] , which we aim to improve in this study.For x ∈ X and r > 0, we denote the closed ball centered at x and or radius r by Br (x) := {y ∈ X , ρ(x, y) ≤ r}. We can now define covering and packing. Definition A.25 (Covering number). Let δ > 0, the covering number N ρ δ (X) is the cardinality of a minimal set of points N such that:X ⊆ x∈N Bδ (x).Remark A.26. There exist several conventions for the definition of such numbers [26, 53, 82] , all of which are equivalent up to absolute constants and in particular induce the same fractal dimensions on X (see [26] ). Definition A.27 (Packing number). Let δ > 0, the covering number N ρ δ (X) is the cardinality of a maximal set of disjoint closed balls with centers in X.In our implementation of Euclidean-based topological quantities, we use sparse random projections to project the weight vectors from R d to a lower dimensional subspace. This is necessary because of memory constraints. Indeed, storing the full trajectory W t0→T ⊂ R d (in our experiments Tt 0 = 5 × 10 3 ) can become intractable for large models.Given a finite set of points W ⊂ R d and ϵ > 0.Let N ≥ O log |W| ϵ 2, Johnson-Lindenstrauss lemma [82, 27] ensures the existence of a linear map P : R d -→ R N such that:∀w, w ′ ∈ W, (1 -ϵ) ∥w -w ′ ∥ 2 ≤ ∥P w -P w ′ ∥ 2 ≤ (1 + ϵ) ∥w -w ′ ∥ 2 .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 on sparse random projections. We use the implementation provided in scikit-learn [63] . More precisely, we used a 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 we used have a small enough number of parameters to avoid the use of random projections.A.8 A note on the connection to Topological Deep Learning Topological deep learning (TDL) is a 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.In this section, we present the proofs of our main theoretical contributions. We divide our proofs into two groups of subsections:• Sections B.1,B.2 and B.3 focus on the extension (in a very natural way) of the quantities appearing in our bounds in pseudometric spaces. The main outcome of this analysis is the definition of positive magnitude in the pseudometric case. Note that Appendix B.1 is not a contribution of 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 our main results, we 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 [21] to naturally extend the persistent homology dimension to pseudometric spaces. Definition B.1 (Metric identification). Let (X, ρ) be a pseudometric space. We can define an equivalence relation on X by a ∼ b ⇐⇒ ρ(a, b) = 0. The associated quotient space, which is denoted X /∼ is a metric space for the naturally induced metric, which we still denote ρ. 7 We will also use the canonical projection, π : X -→ X /∼. These notations will be used throughout the text.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 [21, Lemma B.9 ].). Let (X, ρ) be a finite pseudometric space and α ≥ 0, then we have:E α (X) = E α ( X /∼)where the pseudometric ρ (and its metric identification) have been omitted from the notation.Based on Theorem A.21, the above result is also true when E α represents the cost of a MST of X.In this section, we fix (X, ρ) a finite pseudometric space. We denote by X /∼ its metric identification and by π : X -→ 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, we first need to verify that it provides a well-posed definition of magnitude. This follows from the following lemma.Lemma B.3. We assume that the finite pseudometric space (X, ρ) has magnitude. Then magnitude is independent of the choice of weighting.Proof. The proof is straightforward and identical to the metric case. Let β, β ′ be two weightings, we have:a∈X β(a) = a∈X b∈X e -ρ(a,b) β ′ (b)β(a) = b∈X β ′ (b) a∈X e -ρ(a,b) β(a) = b∈X β ′ (b).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 if X /∼ has magnitude, in which case we have:Mag(X) = Mag ( X /∼) .Proof. We decompose X into equivalence classes as:X = ā∈ X /∼ ā =: i∈I āi ,where denotes disjoint union and the points (a i ) i∈I ∈ X I represent each equivalence class. We denote by ā the equivalence class of a ∈ X.Let β : X -→ R be any function. We have:EQUATION=⇒ : If X has magnitude, then we take β to be a weighting of X, we define:∀ā ∈ X /∼, β(ā) := b∈ā β(b).By Equation (11) , β is a weighting of X /∼.⇐= : if β is a weighting of X /∼, then we define:∀a ∈ X, β(a) := 1 |ā| β(ā),where |ā| denotes the cardinality of ā. By Equation (11) , β is a weighting of X.Let us extend our new notion of positive magnitude in finite pseudometric spaces. This is a 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 metric identification X /∼ is positive definite. Let β : X /∼ -→ R be a weighting of X /∼, then we define the positive magnitude of X, denoted PMag, by:PMag(X) = x∈ X /∼ β(x) + ,where x + := max(x, 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 is 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 (X, ρ) be a finite pseudometric space whose metric identification X /∼ is positive definite. Let β : X /∼ -→ R be a weighting of X /∼, we define the canonical weighting β 0 : X -→ R on X by:∀a ∈ X, β 0 (a) := 1 |π(a)| β(π(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) = x∈X β 0 (x) + .The next proposition is a 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 p ∈ [1, 2] and S ∈ Z n , then every finite subset of (R d , ρS ) admits a positive magnitude, and therefore it also has a canonical weighting.Proof. Let W := {w 1 , . . . , w N } be a finite set in R d . We have∥L S (w) -L S (w ′ )∥ p = n 1/p ρ (p) S (w, w ′ ).Therefore, if we denote by w the equivalence class of w in the metric identification, it is clear that w = w′ ⇐⇒ L S (w) = L S (w ′ ). Hence, the map φ S := n -1/p L S naturally extends to an isometry between metric spaces:W /∼ ∼ -→ φ S (W) ⊂ finite R n .By Theorem A.24, the finite set φ S (W) is positive definite, hence it is also the case of W /∼. Therefore W admits a positive magnitude by definition.The following is deduced from the transcription of the results of [22] to our setting. It is the starting point of our persistent homology-based analysis.Theorem B.9. Let ρ be a pseudometric on R d . Suppose that Assumption 1 holds and that ℓ is (q, L, ρ)-Lipschitz, for q ≥ 1. Then, for all δ > 0, with probability at least1 -ζ over µ ⊗n z ⊗ µ ⊗∞ u , sup t0≤i≤T G S (w i ) ≤ 2Lδ + 2B 2 log N ρ δ (W t0→T ) n + 3B I ∞ (S, W t0→T ) + log(1/ζ) 2n .The proof of this theorem will be given in the next subsection. Before discussing this proof, a few remarks are in order.Covering bounds, such as B.9 have been used in [78, 13, 10, 21] to 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:dim ρ B (X) := lim sup δ→0 log N ρ δ (X) log(1/δ).By using a similar procedure, we see that our framework could be used to introduce intrinsic dimensions associated to a wide range of pseudometrics, as soon as they satisfy a (q, L, ρ)-Lipschitz continuity assumption.However, arguments based on these intrinsic dimensions only make sense in the limit T → ∞, which makes little sense in 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 [55, 3] . Our approach is to replace the intrinsic dimensions by the "intermediary quantities" used to define them. This leads to the results presented in the next two subsection.Before going to the 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 < +∞. However, note that one could consider T = +∞ without much technical difficulties.The setup is the following: let (F (R d ), T ) denote the set of all finite subsets of R d , endowed with a σ-algebra T .We consider the following probability distribution on F (R d ):EQUATION)As it is discussed in [22, Section 5.4], we make the following technical measure-theoretic assumption. Assumption 2. The probability measure µ ⊗n z is a strictly positive Borel measure. Moreover, for every A ∈ T , the map S → ρ S (A) is continuous.The following example highlights the fact this is a very mild assumption. Example B.10. If the data space Z is countable and the data distribution µ z has no null mass, then the above assumption is automatically satisfied with respect to the discrete topology. Theorem B.9. Let ρ be a pseudometric on R d . Suppose that Assumption 1 holds and that ℓ is (q, L, ρ)-Lipschitz, for q ≥ 1. Then, for all δ > 0, with probability at least1 -ζ over µ ⊗n z ⊗ µ ⊗∞ u , sup t0≤i≤T G S (w i ) ≤ 2Lδ + 2B 2 log N ρ δ (W t0→T ) n + 3B I ∞ (S, W t0→T ) + log(1/ζ) 2n .Proof. Let us fix some ζ ∈ (0, 1). First note that thanks to Assumption 2, we have that ρ S is absolutely continuous with respect to π, µ ⊗n z -almost surely. Therefore, we can introduce its Radon-Nykodym derivative, denoted by dρ S /dπ. 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 1ζ, we have, for any λ > 0:sup t0≤i≤T R(w i ) -R S (w i ) ≤ 2Rad(ℓ, W t0→T , S) + 1 λ dρ S dπ (W t0→T ) + log(1/ζ) + λ 9B 2 8n ,with Rad(ℓ, W t0→T , S) a Rademacher complexity term, defined by:Rad(ℓ, W t0→T , S) := E ϵ sup w∈W t 0 →T 1 n n i=1 ϵ i ℓ(w, z i ) ,where ϵ := (ϵ 1 , . . . , ϵ n ) is a vector of independent centered Bernoulli random variables.By [22, Lemma 16] , we have almost surely that:dρ S dπ (W t0→T ) ≤ I ∞ (W t0→T , S).Therefore, by optimizing the choice of the parameter λ in the above equation, we have that:EQUATIONWe now perform a covering argument very similar to classical covering arguments for Rademacher complexity [77] . Let us fix some δ > 0 and introduce (x 1 , . . . , x N ρ δ (W t 0 →T ) ) the centers of a minimal δ-covering of W t0→T for pseudometric ρ. For any w ∈ W t0→T , there exists j such that ρ(w, x j ) ≤ δ. Therefore we have:sup w∈W t 0 →T 1 n n i=1 ϵ i ℓ(w, z i ) ≤ sup 1≤j≤N ρ δ (W t 0 →T ) 1 n n i=1 ϵ i ℓ(x j , z i ) + 1 n n i=1 ϵ i (ℓ(w, z i ) -ℓ(x j , z i )) ≤ sup 1≤j≤N ρ δ (W t 0 →T ) 1 n n i=1 ϵ i ℓ(x j , z i ) + 1 n n i=1 |ℓ(w, z i ) -ℓ(x j , z i )| ≤ sup 1≤j≤N ρ δ (W t 0 →T ) 1 n n i=1 ϵ i ℓ(x j , z i ) + n -1/q ∥L S (w) -L S (x j )∥ q ,where the last line comes from Hölder's inequality.We can now apply Massart's lemma on the first term and the (q, L, ρ)-Lipschitz continuity of ℓ on the second term, this gives us:Rad(ℓ, W t0→T , S) ≤ Lδ + B 2 log N ρ δ (W t0→T ) n ,which concludes the proof.We now present the proofs of our persistent homology-based bounds, ie, the results of section 3.2.The following lemma is a pseudometric version of a classical result of fractal geometry [26] . Lemma B.11 (Covering and packing in pseudometric spaces). Let (X, ρ) be a pseudometric space, δ > 0, and x 1 , . . . , x P δ (X) a maximal δ-packing of X for pseudometric ρ. Then we have:N ρ 2δ (X) ≤ P ρ δ (X).Proof. Let us fix δ > 0 and let (x 1 , . . . , x P ρ δ (X) ) be centers of a maximal packing of X with closed δ-balls. Let us assume that:X\ 1≤i≤P ρ δ (X) B2δ (x i ) ̸ = ∅,so that we can take some x 0 belonging to the above non-empty set. Now let us fix i ∈ {1, . . . , P ρ δ (X)} and w ∈ Bδ (x i ). By the triangle inequality and the definition of w and x 0 , we have:ρ(x 0 , x i ) >2δ ≤ ρ(x 0 , w) + ρ(w, x i ) ≤δ .Therefore, we have ρ(x 0 , w) > δ, and hence Bδ (x i ) ∩ Bδ (x 0 ), so that we construct a bigger δ-packing, by adding x 0 to (x 1 , . . . , x P ρ δ (X) ), which is absurd. Therefore, we have X\ 1≤i≤P ρ δ (X) B2δ (x i ) = ∅, hence the result.The next lemma asserts that E α is increasing (with respect to the inclusion of sets), if and only if α ≤ 1. This is the reason why we require α ∈ [0, 1] in Theorem 3.4. Lemma B.12. Let (X, ρ) be a non-empty finite pseudometric space, α ∈ [0, 1] and δ > 0. Then we have:E ρ α (X) ≥ P ρ δ (X) 2 δ αProof. We refer to Figure 5 for a graphical illustration of the main technical elements of this proof.In the case where P ρ δ (X) = 1, the result is obvious. In the rest of the proof we assume that P ρ δ (X) ≥ 2 In all the following, we fix α ∈ [0, 1] and δ > 0. We also denote P := P ρ δ (X). Without loss of generality, we can assume P ≥ 2.We fix T an MST of X, represented by a set of edges denoted x → y, with x, y ∈ X 2 (note that we identify x → y and y → x). It is a classical result that there are |X| -1 edges. For an edge e of the form a → b, we denote its length by |e| := ρ(a, b).For a, b ∈ X, with a ̸ = b, we denote by {a → b} the shortest path between a and b. More precisely, we represent it as a list of edges, denoted a = a 0 → a 1 • • • → a K = b, for some K. When the context is clear, we identify {a → b} to the set of its edges a → b.Let us introduce (x 1 , . . . , x P ) a maximal δ-packing of X by closed.For every i ∈ {1, . . . , P }, as T is connected, there exists y i ∈ X such that y i / ∈ Bδ (x i ) and y i is the only point in the path {x i → y i } that does not belong to the ball Bδ (x i ).For each i, we denote e i the only edge in {x i → y i } to which y i belongs, i.e. e i is of the form z i → y i , with z i ∈ Bδ (x i ). By construction, those edges e i are the only ones that can be shared by several paths {x i → y i }.I := {i ∈ {1, . . . , P } , ∀j ̸ = i, e i / ∈ {x j → y j }} , K := {1, . . . , P } \I.Let us consider i ∈ K. Let us assume that we have j, j ′ ∈ {1, . . . , P } such that e i ∈ {x j → y j } and e i ∈ {x j ′ → y j ′ }. If we denote e i as z i → y i , we have that z i ∈ Bδ (x i ), by definition of y i . Therefore, by definition of y j , we have z i = y j (because Bδ (x i ) ∩ Bδ (x j ) = ∅). We have similarly z i = y j ′ and thus y j = y j ′ . By definition of y j and y j ′ we also have y i ∈ Bδ (x j ) ∩ Bδ (x j ′ ), which is absurd, by definition of packing. We conclude the following: ∀k ∈ K, ∃!j ̸ = i, e i ∈ {x j → y j } .For k ∈ K, we denote the corresponding j by φ(k).By definition of K, it is clear that φ(k) ∈ K. Moreover, as y φ(i) = z i ∈ Bδ (x i ), this implies that φ 2 (i) = i. Therefore, we have constructed an involution,φ : K -→ K, such that ∀k ∈ K, φ(k) ̸ = k.This implies that the cardinality of K is even and that we can write K = K 1 K 2 , with:|K 1 | = |K 2 |, φ(K 1 ) = K 2 .The outcome of this construction is that we now have disjoint paths given by the (x i → y i ) i∈I and the (x k → x φ(k) ) k∈K1 . Therefore, we get the following lower bound on E α (X).E α (X) ≥ i∈I e∈{xi→yi} |e| α + k∈K1 e∈{x k →x φ(k)} |e| α .As α ∈ [0, 1], we have that:E α (X) ≥ i∈I   e∈{xi→yi} |e|   α + k∈K1    e∈{x k →x φ(k)} |e|    α .By the triangle inequality, and by definition of packing, we have:E α (X) ≥ i∈I δ α + k∈K1 δ α = δ α (|I| + |K 1 |) ≥ 1 2 P ρ δ (X)δ α ,which concludes the proof.Figure 5 : Geometric representation of the proof of Lemma B.12. It represents a point cloud (w i ) i , the centers of the 3 packing balls (blue) and the minimum spanning tree T (red), so that the sum of the lengths of the edges of T is exactly E 1 , see Appendix A.Theorem 3.4. Let ρ be a pseudometric on R d . Supposes that Assumption 1 holds and that ℓ is (q, L, ρ)-Lipschitz, for q ≥ 1. Then, for all α ∈ [0, 1], with probability at least 1ζ, we have:sup t0≤i≤T G S (w i ) ≤ 2B 2 log (1 + K n,α E ρ α ) n + 2B √ n + 3B I ∞ (S, W t0→T ) + log(1/ζ) 2n , with K n,α := 2 (2L √ n/B) α .Proof. For better clarity, we assume T < +∞. Let us fix some ζ ∈ (0, 1), δ > 0, and α ≥ 0. By Theorem B.9, we have, with probability at least 1ζ:sup t0≤i≤T R(w i ) -R S (w i ) ≤ 2Lδ + 2B 2 log N ρ δ (W t0→T ) n + 3B I ∞ (S, W t0→T ) + log(1/ζ) 2n .We now bound the covering number appearing in the above equation. By Lemma B.12, we have:E ρ α (W t0→T ) ≥ 2 -α-1 P ρ δ/2 (W t0→T ) -1 δ α .Moreover, by Lemma B.11, we have:E ρ α (W t0→T ) ≥ 2 -α-1 [N ρ δ (W t0→T ) -1] δ α .We now combine this with our generalization bound by choosing the value:δ := B L √ n ,and we get that with probability at least 1ζ, we have:sup t0≤i≤T R(w i ) -R S (w i ) ≤ 2B √ n + 2B 2 log(1 + K n,α E ρ α (W t0→T )) n + 3B I ∞ (S, W t0→T ) + log(1/ζ) 2n , with: K n,α := 2 2L √ n B α .It leads to the desired result.Lemma B.13. Let W ⊂ R d be a finite set and ϵ := (ϵ 1 , . . . , ϵ n ) and ρ a pseudometric such that (W, λρ) admits a positive magnitude (according to Definition B.5) for every λ > 0. We assume that ℓ is (L, q, ρ)-Lipschitz continuous with q ∈ [1, 2]. Then, for any λ > 0, we have:E ϵ exp λ n sup w∈W n i=1 ϵ i ℓ(w, z i ) ≤ e λ 2 B 2 2n PMag ((Lλ)W) .where PMag is the positive magnitude, see Appendix B.3Proof. We first remark that, by Hölder's inequality and the (L, q, ρ)-Lipschitz condition, we have:∀w, w ′ ∈ W, ρ S (w, w ′ ) ≤ n -1/q ∥L S (w) -L S (w ′ )∥ q ≤ Lρ(w, w ′ ).Let us fix some λ > 0. As (W, λρ) admits a positive magnitude, we can introduce a canonical weighting β : W -→ R. By definition of a weighting, we have∀a ∈ W, b∈W e -λρ(a,b) β(b) = 1.Moreover, for any ϵ ∈ {-1, 1} n , we introduce:a ϵ := argmax a∈W n i=1 ϵ i ℓ(a, z i ).With those notations, we can compute:1 ≤ b∈W e -λρ(aϵ,b) β + (b) ≤ b∈W e -λ L ρ S (aϵ,b) β + (b) = b∈W exp - λ Ln i=1 |ℓ(a ϵ , z i ) -ℓ(b, z i )| β + (b) ≤ b∈W exp - λ Ln n i=1 ϵ i (ℓ(a ϵ , z i ) -ℓ(b, z i )) β + (b) = exp - λ Ln n i=1 ϵ i ℓ(a ϵ , z i ) b∈W exp λ Ln n i=1 ϵ i ℓ(b, z i ) β + (b).Therefore, by dividing by the first term on the right-hand side and using the independence of the ϵ i , we deduce that:E ϵ exp λ Ln sup w∈W n i=1 ϵ i ℓ(w, z i ) ≤ E ϵ b∈W exp λ Ln n i=1 ϵ i ℓ(b, z i ) β + (b) = b∈W n i=1 E ϵ e λ Ln ϵiℓ(b,zi) β + (b).By Hoeffding's lemma, we have:E ϵ exp λ Ln sup w∈W n i=1 ϵ i ℓ(w, z i ) ≤ e λ 2 B 2 2nL 2 b∈W β + (b) = e λ 2 B 22nL 2 PMag (λW) . The result follows by the change of variable λ = ΛL. Theorem 3.5. Let ρ be a pseudometric such that (W, λρ) admits a positive magnitude (according to Definition B.5) for every λ > 0. We assume that ℓ is (q, L, ρ)-Lipschitz continuous with q ≥ 1. Then, for any s > 0, we have with probability at least1 -ζ that sup t0≤i≤T G S (w i ) ≤ 2 s log PMag ρ (LsW t0→T ) + s B 2 n + 3B I ∞ (S, W t0→T ) + log(1/ζ) 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 1ζ:sup t0≤i≤T R(w i ) -R S (w i ) ≤ 2Rad(ℓ, W t0→T , S) + 3B I ∞ (S, W t0→T ) + log(1/ζ) 2nBy Jensen's inequality, we have, for all λ > 0:Rad(ℓ, W t0→T , S) ≤ 1 λ log E ϵ exp λ n sup w∈W t 0 →T n i=1 ϵ i ℓ(w, z i ) .Therefore, we can apply Lemma B.13 to write that, for all s > 0:Rad(ℓ, W t0→T , S) ≤ s B 2 2n + 1 s log PMag (LsW t0→T ) .We deduce that for all s > 0, we have with probability at least 1ζ that:sup t0≤i≤T R(w i ) -R S (w i ) ≤ s B 2 n + 2 s log PMag (LsW t0→T ) + I ∞ (S, W t0→T ) + log(1/ζ) 2n .Remark B.14 (Link between magnitude and positive magnitude). Let W ⊂ R M be a finite set (for some M ), of cardinality N , and ρ a metric on W. If we denote the similarity matrix, for a given value of s > 0, by M s (a, b) = e -ρ(a,b) , then it is clear that:M s -→ s→∞ I N .Moreover, by continuity of the inverse, this implies that the weighting associated to s > 0, i.e. β s : W → R, satisfy:∀a ∈ W, β s (a) -→ s→∞ 1.From this, we first deduce that, for s → ∞, we have Mag ρ (sW) → N . Moreover, by continuity of the inverse, this means that, up to a certain s, the weighting (β s (a)) a∈W only has positive elements. Therefore, this implies that, for s big enough, one has Mag ρ (sW) = PMag ρ (sW).Thanks to our definitions for positive magnitude in pseudometric spaces, given in Appendix B.3, this observation extends to the pseudometric case.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 us fix S ∈ Z n and consider a set W ⊂ R d that is compact 8 with respect to the pseudometric ρ S . For every λ > 0, we assume that A possesses a weighting µ λ (which is a finite measure on A) with respect to pseudometric λρ S , in the sense of [56, Definition 3.3 ]. Then we have, for any λ > 0:E ϵ exp λ n sup a∈A n i=1 ϵ i ℓ(w, z i ) ≤ e λ 2 B 2 2n PMag (λA) .where PMag is the positive magnitude of the compact space (A, λρ S ) which, according to [56] , can be defined as:PMag (λA) = (µ λ ) + (A),where (µ λ ) + denotes the positive part of the measure µ λ .In this section, we give additional details regarding the models, datasets, and hyperparameters used in our experiments.C. The design of the ViT has been modified to accommodate for the small datasets as per [68] . Our implementation is 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-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 [29] . Then we verified that the finetuned weights achieved 100% training performance, and then they were the starting point of our computational framework. We ran the transformer experiments on 18 NVIDIA 2080Ti GPUs, and the graph experiments on 18 Intel Xeon Silver 4114 CPUs.We will briefly talk about the details of GraphSage [32] and GatedGCN [12] , prior works we use in our experiments. GraphSage [32] is an improvement over the GCN (Graph ConvNets) model [41] and it incorporates each node's own features from the previous layer in an explicit way by the update equation:h l+1 i = ReLU(U l Concat(h l i , Mean j∈Ni h l j )),where N i is the neighbourhood of node i, h l i is the feature vector and U l ∈ R d×2d . We use the graph-pooling version of GraphSage, with the following update equation:h l+1 i = ReLU(U l Concat(h l i , Max j∈Ni ReLU(V l h l j ))),where V l ∈ R d×d . GatedGCN (Gated Graph ConvNet) [12] uses the following update equation:h l+1 i = h l i + ReLU(BN(U l h l i + j∈Ni e l ij ⊙ V l h l i )),where U l , V l ∈ R d×d , ⊙ is the Hadamard product, and the edge gates e l ij have the following definitions:e l ij = σ(ê l ij ) j ′ ∈Ni σ(ê l ij ) + ϵ , êl ij = êl-1 ij + ReLU(BN(A l h l-1 i + B l h l-1 i + C l êl-1 ij )),where σ is the sigmid funciton, ϵ is a small constant for numerical stability, A l , B l , C l ∈ R d×d , and BN stands for Batch Normalization.We used the code provided by [23] , which relies on the dgl 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 18 Intel Xeon Silver 4114 CPUs. Each experiment (one fixed batch size and learning rate) was run on a single CPU and 18 experiments were run on the server at any given time (on different CPUs).Hyperparameters shared among experiments.. For the Vision Transformers experiments, we varied the learning rate range [10 -5 , 10 -3 ], and batch size in the range [8, 256] . For the graph experiments, [10 -6 , 10 -4 ], and batch size in the range [8, 256] . For all experiments, we used 0.1 proportion of the training data for the computation of the pseudo matrix, apart from CaiT and Swin on CIFAR100, where we used 0.09 proportion of the training data due to memory constraints. All experiments use a 6 × 6 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 -3 ], and the batch size between [8, 256] , and data proportion for the computation of the pseudo-distance (ρ S ) of 10% (see section 4).ViT on CIFAR100. We selected 6 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 (ρ S ) of 10% (see section 4).CaiT on CIFAR10. We selected 6 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 (ρ S ) of 10% (see section 4).CaiT on CIFAR100. We selected 6 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 (ρ S ) of 9% (see section 4).Swin on CIFAR10. We selected 6 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 (ρ S ) of 10% (see section 4).Swin on CIFAR100. We selected 6 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 (ρ S ) of 9% (see section 4).GatedGCN. We selected 6 values for the learning rate in the range [10 -6 , 10 -4 ], the batch size between [8, 256] and data proportion for the computation of the pseudo-distance (ρ S ) of 10% (see section 4). We note that for due to 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 -4 ], the batch size between [8, 256] , and data proportion for the computation of the pseudo-distance (ρ S ) of 10% (see section 4).model on the whole dataset at each iteration (this is a similar problem to the one encountered for the computation of the data-dependent distance matrices, discussed in section 4). Previous studies on worst-case TDA-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).In our work, we argue that the true worst-case generalization error may however have a 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 acc test-worst and substracted it from the final train accuracy (acc train-final ) to obtain the "generalization gap" G S reported in our main experiments, i.e., G S := acc train-finalacc test-worst .Note that in addition to being a good proxy to 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 G S , we present here a few additional experiments using the final accuracy gap as a generalization measure (it is denoted Accuracy gap in the figures.) In the case of a ViT on CIFAR10, this is shown in Figure 7 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 [10, 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 (Ψ goes from 0.20 to 0.36). This may explain why we observed poor performance of PH-dim in Figure 4a . Second, we observe that the correlation seems to 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] . As is explicitly shown by Theorem 3.5, using (positive) magnitude as a topological complexity requires choosing the scale parameter s > 0. In our main experiments, we experimented with both s = √ n (justified to obtain the expected 1/ √ n in the generalization bound) and s = 0.01 (in order to compare with using a small value for s). We can see in Table 1 that both settings give relatively satisfactory results. Note that in our setting we have √ n ≈ 223.6.We present in Figure 9 the observed correlation between positive magnitude and generalization error for several intermediary values of s. This experiment was made with a ViT on the CIFAR10 dataset, using the ADAM optimizer. We observe a relative stability of the correlation Ψ with respect to s. In this particular case, the correlation is extremely stable for higher values of s while it displays more variability for smaller values of s. Further experiments would be necessary to understand whether this behavior is general and could then lead to the discovery of more stable magnitude-related complexities, which we leave for future work. Experiment made with ViT on CIFAR10 and ADAM optimizer.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 a ViT on the CIFAR10 dataset and the ADAM optimizer, we observe very similar performance E 1 , PMag( √ nW t0→τ ) and the gradient variance. Note that the fact that E 1 and PMag( √ nW t0→τ ) yield similar correlation was already observed on Table 1 . This tends to suggest that these three complexity measures may be able to capture similar aspects of the geometry around a local minimum. Remark D.1. It should be noted that the primary goal of the introduced topological complexity measure is not to outperform existing measures such as a gradient variance but rather to demonstrate the empirical importance of the topology of the trajectory for generalization error.We compare the performance of the different metrics by using the granulated Kendall's coefficients introduced in [37] . The experiments presented here use 3 different Vision Transformers (ViT [79] ,CaiT [80] , Swin [48] ) on CIFAR10 and CIFAR100. As a baseline, we use the dim PH introduced in [10] and the data-dependent dimension with the pseudometric dim PH from [21] .Here we present the full results on each dataset and model. They can be found in Table 4 for CaiT and CIFAR10, 6 for Swin and CIFAR10, 3 for ViT and CIFAR100 and 5 for CaiT and CIFAR100. The plots from each experiment for every computed quantity can be found in (the remaining 3 quantities for ViT and CIFAR10). In Table 1 , 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-MNIST. We can observe a nice correlation, outperforing dim-PH in most experiments. As it was observed for the transformer-based experiments, the correlation seems to be better for the data-dependent-metrics. This is an important fact, as no sparse random projection 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. It also shows that all quantities seem to yield better correlations in the absence of random projections, at least in the GNN expsriments.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 it was observed for the transformer-based experiments, the correlation seems to be better for the data-dependent-metrics. This is an important fact, as no sparse random projection was used to compute the Euclidean distance matrices in the GNN experiments 9 . 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 can be seen on these plots. Indeed, Mag(0.01) and PMag(0.01) seem to be almost constant and near 1. This indicates that the scale choice s = 0.01 was not suited for these experiments; this behavior was already reflected in Table 1 through very low Kendall's coefficients, indicating the absence of meaningful correlation. However, Mag( √ n) and PMag( √ n) provide significantly better correlation, which supports our main claims, as s = √ n has been argued in section 3.3 to be a 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 fact in Table 1 by imposing our granulated Kendall's coefficients implementation to return zeros in the absence of correlation, hence the small numbers observed in this case. That being said, this behavior should not be seen as an issue. Indeed, PH-dim with 01-pseudometric consists (in theory) in estimating the dimension of a subset of a discrete hypercube, which is always 0. The reason we still reported PH-dim for this pseudometric is for consistence and to test the implementation of [10, 21] in this non-standard setting; it is however not theoretically grounded. Answer: [No] Justification: In our paper, we conducted experiments on a variety of models (vision transformers, graph neural networks) that are significantly bigger than the ones previously used in the trajectory-dependent generalization literature. As the cost of these experiments is extremely high, both in terms of computational time (it requires evaluating the model on a large part of the data at each iterations in order to compute the distance matrices) and memory (storing the trajectories). Moreover, for each (model -dataset) pair, we run the experiments on 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 a 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, our extensive set of experiments does support the significance of these results. Moreover, it should be noted that we partially base our empirical study on the granulated Kendall's coefficients, which are 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 error bars, confidence intervals, or statistical significance tests, at 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. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 are out of range (e.g. negative error 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.We use ≲ in informal statements to indicate that absolute constants and/or small terms are missing.Our term "topological complexity" should not be confused with the homonym topological invariant.By "uniform", we mean the worst error over a set; it should not be confused with uniform convergence.We shall underline that, while Mag with the Euclidean distance was empirically proposed as a complexity measure in[3], a theoretical justification for Mag results in Table1is still missing for moderate values of s.A Rademacher random variable is defined by P(ϵi = 1) = P(ϵi = -1) = 1/2.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 to do with the number of iterations appearing in the rest of the paper.Indeed, if a ∼ b, then we have ∀c ∈ X, ρ(a, c) = ρ(b, c).As we did in Appendix B.3, the positive magnitude of compact spaces should be properly extended to pseudometric spaces, we omit the details as it is very similar to the case treated in this paper.A sparse random projection was not necessary as these models have less parameters than the tramsformers considered above 


Decision: 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

Reviews: review: paper_summary: paper_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.
Experiments 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.
strength_weakness: strength_weakness: Maybe I get this wrong but in line 113, is $Y\subset X$ or $Y\subset A$?
questions: questions: 1.- Have you explore the situation of use compact metric spaces? 

2.- Have you explore the situation of change the metric to a non-euclidean one?

3.- In line 182, what do you mean by $\mu_z^{\otimes n}$?
limitations: limitations: Lack of understanding of IT terms.
paper_summary: paper_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.
- 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.
- 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.
strength_weakness: strength_weakness: - Concerns Regarding Assumptions
  - This bound only holds under bounded losses. Thus, as the upper bound B increases, the bound becomes vacuous and diverges under unbounded losses.
  - 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.
  - 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.

- Concerns Regarding Mutual Information in the Bound
  - 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.
  - 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.
  - 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.

- Challenges in Handling Hyperparameters and Lack of Detailed Discussion
  - 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.

- Lack of Comparison with Other Information-Theoretic Quantities or Metrics Strongly Correlated with Generalization
  - 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.
  - Thus, it remains uncertain how the proposed measure compares to other evaluation metrics in terms of superiority.

Citation:
- Jiang et al. (2019):  Jiang et al. Fantastic Generalization Measures and Where to Find Them. ICLR2020. https://openreview.net/forum?id=SJgIPJBFvH
- 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
- Harutyunyan et al. (2021): Harutyunyan et al. Information-theoretic generalization bounds for black-box learning algorithms. NeurIPS2021. https://arxiv.org/abs/2110.01584
- Steinke et al. (2020): Steinke et al. Reasoning About Generalization via Conditional Mutual Information. COLT2020. https://arxiv.org/abs/2001.09122
questions: 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.

- **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?

- **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?

- **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.

- **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: 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.
- 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.
paper_summary: paper_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".

In 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.
strength_weakness: strength_weakness: 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.
questions: questions: Can you further clarify your use of the term "connected components"? 
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? (After all for the neural tangent kernel at infinite width wouldn't all weights be updated with each gradient step?)

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?

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?
limitations: 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.
paper_summary: paper_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. 

Namely, 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

$$\sup_{w \in W} G(w) \leq \sqrt{\frac{\text{Topological quantity } + \text{(Information theory quantity)} + \log(\zeta^{-1})}{n}}$$

with probability $1 - \zeta$. The work focuses on building actual topological quantities that make this claim true, proposing two possible candidates: 
- The _$\alpha$-weighted lifetime sums_ that (roughly) computes the maximum spanning tree of $W$ and then assign a weight to it, 
- 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). 

Contrary 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). 

Experimentally, 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.
strength_weakness: strength_weakness: 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 (*). 

While 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. 

I 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. 

(*) Note that I quickly parsed the supplementary material, which I found quite enlightening, but cannot guarantee the correctness of its content.
questions: 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"?

2. 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?

3. 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: Limitations have been discussed by the authors, which is appreciated.

Comments: title: Thank you
ty
Aknowledgements
Thanks
comment: Thanks for your response!
We are grateful to the reviewer for their positive feedback. As we mentioned in the rebuttal, we will improve the clarity of the paper in the final version by implementing the changes we discussed.
We sincerely thank the reviewer for considering our feedback and updating their score. We are glad that our responses could address their concerns. We are incorporating these into the revision.
> the appendix is 26 pages long, and not 40 as claimed by the reviewer.

Yes indeed I must admit that I went for the lazy evaluation "length of the pdf - main body = 40 pages", not accounting for references, neurips checklist etc. The authors are right, the appendix is shorter than what my initial comment suggest, and the section dedicated to delayed technical proofs is "only" 8 pages long. 

Nonetheless, it is important to confess that I did not investigate these proofs in detail and, as such, cannot guarantee the correctness of the work. I appreciate that the authors took time to explain them in their rebuttal and I am leaning toward supporting the paper (which is reflected by my positive note and average confidence).
We understand that the reviewer finds the appendix to be important for the grasp of our paper. So, we would like to clarify its content.  First, let us highlight that the appendix is 26 pages long, and not 40 as claimed by the reviewer.
1) Having proofs in the appendix (Appendix B) is standard for NeurIPS papers and helps readability of our paper. The grasp of the proofs are not needed for the grasp of the ideas in our paper.
2) Our exposition of the persistent homology (Appendix A) should not be seen as a set of missing definitions but rather as a little treatise of the background material included for making our paper self-contained. We could have cited the relevant resources only, but we instead opted for including the relevant content from those references as a small section. We hope that such non-crucial sections can help the uninformed reader for understanding our paper.
3) The remaining part of the appendix (Appendix C) is dedicated to experimental setting details and additional empirical results. These experiments mainly support the empirical findings reported in the main paper, and provide detailed analyses of the content reported in the main paper.

In the final version of the paper, we will use the extra page to include, in the main paper, a summary of the main ideas contained in the appendix, in particular a sketch of proof and comments on the additional experiments. We hope that the reviewer reconsiders their evaluation in the light of these.
First and foremost, I would like to express my gratitude to the authors for their detailed feedback. I also apologize for my misunderstanding regarding the nature of the generalization error bounds presented in this paper, which are worst-case generalization bounds rather than algorithm-dependent bounds. I misunderstood this point in the section discussing mutual information.

The authors have effectively addressed my concerns. In addition to this clarification, I find the analytical approach and the insights gained from the bounds to be particularly interesting. I now believe the paper makes a sufficient contribution to warrant acceptance at NeurIPS. Therefore, I have decided to raise my score.
Thank you for response. I retain my recommendation for accept pending any discussions with other reviewers.
Thank you for taking time answering my review. 

As i said, my main concern with the work is that it contains a lot of technical content deferred to the appendix that I could not review in detail. Otherwise I'm fine with it; so I must discuss with point with the AC and other reviewers in the next discussion period.