Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks
Authors: Tolga Birdal
Aaron Lou
Leonidas Guibas
Umut Simsekli
Venue: NeurIPS 2021 Poster (2021)
Keywords: generalization
persistent homology
intrinsic dimension
deep networks

Abstract: Disobeying the classical wisdom of statistical learning theory, modern deep neural networks generalize well even though they typically contain millions of parameters. Recently, it has been shown that the trajectories of iterative optimization algorithms can possess \emph{fractal structures}, and their generalization error can be formally linked to the complexity of such fractals. This complexity is measured by the fractal's \emph{intrinsic dimension}, a quantity usually much smaller than the number of parameters in the network. Even though this perspective provides an explanation for why overparametrized networks would not overfit, computing the intrinsic dimension (\eg, for monitoring generalization during training) is a notoriously difficult task,  where existing methods typically fail even in moderate ambient dimensions. In this study, we consider this problem from the lens of topological data analysis (TDA) and develop a generic computational tool that is built on rigorous mathematical foundations. By making a novel connection between learning theory and TDA, we first illustrate that the generalization error can be equivalently bounded in terms of a notion called the 'persistent homology dimension' (PHD), where, compared with prior work, our approach does not require any additional geometrical or statistical assumptions on the training dynamics. Then, by utilizing recently established theoretical results and TDA tools, we develop an efficient algorithm to estimate PHD in the scale of modern deep neural networks and further provide visualization tools to help understand generalization in deep learning. Our experiments show that the proposed approach can efficiently compute a network's intrinsic dimension in a variety of settings, which is predictive of the generalization error. 

Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks
Tolga Birdal
Aaron Lou Stanford University
Stanford University
aar aaronlou@ att.saatnooroooooo edu
Leonidas Guibas
Umut Şimşekli INRIA & ENS PSL Research University umut s simsekli@ inria. fr
Stanford University guibas@ca. stanford.edu
Abstract
Disobeying the classical wisdom of statistical learning theory, modern deep neural networks generalize well even though they typically contain millions of parameters. Recently, has been shown that the trajectories of iterative optimization algorithms can possess fractal structures, and their generalization error can be formally linked to the complexity such fractals. This complexity is measured by the fractal's s intrinsic dimension, quantity usually much smaller than the number of parameters in the network. Even though this perspective provides an explanation for why overparametrized networks would not overfit, computing the intrinsic dimension (e.g-, for monitoring generalization during training) a notoriously difficult task, where existing methods typically fail even in moderate ambient dimensions. In this study, we consider this problem from the lens of topological data analysis (TDA) and develop generic computational tool that is built on rigorous mathematical foundations. By making novel connection between learning theory and TDA, we first illustrate that the generalization error can be equivalently bounded in terms of notion called the 'persistent homology dimension' (PHD), where, compared with prior work, our approach does not require any additional geometrical statistical assumptions on the training dynamics. Then, by utilizing recently established theoretical results and TDA tools, we develop an efficient algorithm estimate PHD in the scale of modern deep neural networks and further provide visualization tools help understand generalization in deep learning. Our experiments show that the proposed approach can efficiently compute a network's 's intrinsic dimension in a variety of settings, which is predictive of the generalization error.
Introduction
In recent years, deep neural networks (DNNs) have become the de facto machine learning tool and have revolutionized variety fields such as natural language processing [DCLT18), image perception [KSH12, RBH+21], geometry processing [QSMG17, 2BL and 3D vision [DBI18, GLW* 21]. Despite their widespread use, little known about their theoretical properties. Even now the iop-performing DNNs are designed by trial-and-error, pesky, burdensome process for the average practitioner [EMH+ 19). Furthermore, even if top-performing architecture found, large class of real-woris datasets.
difficult to provide performance guarantees
This lack of theoretical understanding has motivated plethora of work focusing on explaining what, how, and why a neural network learns. To answer many of these questions, one naturally examines the generalization error, measure quantifying the differing performance on train and
35th Conference on Neural Information Processing Systems (NcurIPS 2021)

---

test data since this provides significant insights into whether the network is learning or simply memorizing [ZBH 221. However, generalization in neural networks particularly confusing as refutes the classical proposals of statistical learning theory such as uniform bounds based on the Rademacher complexity [BM02] and the Sopnik-Chervonenkis (VC) dimension [Vap68].
Instead, recent analyses have started focusing on the dynamics of deep neural networks, INBMS17, BO18, GJ16] provide analyses on the final trained network, but these miss out on critical train- ing patterns. To remedy this, a recent study [SSDE20] connected generalization and the heavy tailed behavior of network trajectories-a phenomenon which had already been observed in prac- tice [SSG19, SGN+ 19, SZTG20, GSZ21, CWZ 21, HM20, MM19]. [SSDE20] further showed that the generalization error can be linked the fractal dimension of a parametric hypothesis class (which can then be taken as the optimization trajectories). Hence, the fractal dimension acts as a "capacity metric' for generalization.
While [SSDE20] brought a new perspective to generalization, several shortcomings prevent ap- plication in everyday training. In particular, their construction requires several conditions which may be infeasible in practice: (i) topological regularity conditions on the hypothesis class for fast computation, (ii) a Feller process assumption on the training algorithm trajectory, and that (iii) the Feller process exhibits a specific diffusive behavior near a minimum. Furthermore, the capacity metries in [SSDE20] are not optimization friendly and therefore can't be incorporated into training.
In this work, we address these shortcomings by exploiting the recently developed connections between fractal dimension and topological data analysis (TDA). First, by relating the box dimension [Sch09] and the recently proposed persistent homology (PH) dimension [Sch20]. we relax the assumptions in [SSDE20] to develop a topological intrinsic dimension (ID) estimator. Then, using this estimator we develop general tool for computing and visualizing generalization properties in deep learning. Finally, by leveraging recently developed differentiable TDA tools [CHU17, CHN19], we employ our ID estimator to regularize training towards solutions that generalize better, even without having access to the test dataset.
Our experiments demonstrate that this new measure of intrinsic dimension correlates highly with generalization error, regardless of the choice of optimizer. Furthermore, a proof of concept, we illustrate that our topological regularizer is able to improve the test accuracy and lower the generalization error. In particular, this improvement is most pronounced when the learning rate/batch size normally results in a poorer test accuracy.
Overall, our contributions summarized as follows:
We make a novel connection between statistical learning theory and TDA in order develop generic computational framework for the generalization error. We remove the topological regularity condition and the decomposable Feller assumption on training trajectories, which were required in [SSDE20]. This leads to a more generic capacity metric.
Using insights from our above methodology, we leverage the differentiable properties of persistent homology to regularize neural network training. Our findings also provide the first steps towards theoretically justifying recent topological regularization methods [BGND* + 19, CNBW19].
We provide extensive experiments to illustrate the theory, strength, and flexibility of our framework.
We believe that the novel connections and the developed framework will open new theoretical and computational directions in the theory of deep learning. To foster further developments at the the intersection of persistent homology and statistical learning theory, we release our source code under: http://wwww..o.ooaa/aaoooonnonna
2
Related Work
Intrinsic dimension in deep networks Even though large number of parameters are required to train deep networks [FC18], modern interpretations of deep networks avoid correlating model over-fitting or generalization to parameter counting. Instead, contemporary studies measure model complexity through the degrees of freedom of the parameter space [JFH15, GJ16), compressibility (pruning) [BO18] or intrinsic dimension [ALMZ19, LFLYI8, MWH+ 18). Tightly related to the ID, Janson el al. [JFH15] investigated the degrees of freedom [Ghr10] in deep networks and expected difference between test error and training error. Finally, LDMNet [ZQH+ + 18] explicitly penalizes the ID regularizing the network training.

---

Generalization bounds Several studies have provided theoretical justification to the observations that trained neural networks live in lower-dimensional space, and this related to the generalization performance. In particular, compression-basee generalization bounds [AGNZ188, SAM+20, SAN20, HJTW21, BSE+21] have shown that the generalization error of a neural network can be much lower if it can be accurately represented in lower dimensional space. Approaching the problem from geometric viewpoint, [SSDE20] showed that the generalization error can be formally linked to the fractal dimension of parametric hypothesis class. This dimension indeed the plays role of the intrinsic dimension, which can be much smaller than the ambient dimension. When the hypothesis class is chosen the trajectories of the training algorithm, [SSDE20] further showed that the error can be linked to the heavy-tail behavior the trajectories.
Deep networks & topology Previous works have linked neural network training and topologial invariants, although all analyze the final trained network [FGFAEV2I]. J. For example, in [RTB- 19), the authors construct Neural Persistence, measure neural network layer weights. They further- more show that Neural Persistence reflects many of the properties of convergence and can classify weights based on whether they overfit, underfit, or exactly fit the data. In parallel line of work, [DZF19] analyze neural network training by calculating topological properties of the underlying graph structure. This is expanded upon in [CMEM20], where the authors compute correlations between neural network weights and show that the homology is linked with the generalization error.
However, these previous constructions have been done mostly in adhoc manner. As result, many of the results are mostly empirical and work must still be done to show that these methods hold theoretically. Our proposed method, by contrast, is theoretically well-motivated and uses tools from statistical persistent homology theory to formally links the generalization error with the network training trajectory topology.
We also would like to note that prior work has incorporated topological loss functions to help normalize training. In particular, [BGND+ 19] constructed topological normalization term for GANs to help maintain the geometry of the generated 3d point clouds.
3 Preliminaries & Technical Background
We imagine a point cloud W = {wo E Rd) as geometric realization of a d-dimensional topological space W c. W c Rd. (z(z) C IRd denotes the closed ball centered around æ E Rd with radius 6.
Persistent Homology From topological perspective, W can be viewed a cell complex composed of the disjoint union of k-dimensional balls or cells a E W glued together. For 0, 1, 2. we form a chain complex C(W)- = ... -...C++ (.W) Dx+1, (+V) 2e by se- quencing chain groups (+V),, whose elements are equivalence classes of cycles, via boundary maps Os (+)) CW) with 0 = O. In this paper, we work with finite simplicial complexes restricting the cells to be simplices.
Kipe
Dii
B,
The ttth homology group or k-dimensional homology is then defined as the cquivalence classes of k-dimensional cycles who differ only by a bound- ary, or in other words, the quotient group H₂ = Z (W)/P Y& (W) where Zy (WV)
Figure 1: A visualization of Vietoris-Rips complex computed using persistent homology (PH).
ker as and Yx(W)) = im ōk+1- The generators or ba- sis of Ho(W), (W)) and Hz(W) describe the shape of the topological space W by its connected components, holes and cavities, respectively. Their ranks are related to the Betti numbers i.e. 3a rank(H
Definition 1 (Čech and Vietoris fieps Complexes). For W set of fine points in a metric space, the Čech cell complex Čech, (W) is constructed using the intersection of r-balls around W, (WW:: Čech, Cech,(W) {Q C W : B, + 0}. The construction of such complex is intricate. Instead, the Vietoris-Ke Rips complex VR,(WW closely approximates (ech, using only the pairwise distances or the intersection of two r-balls [RB21]: W, VR,(W) {Q c W Vz, E
Q, (x) n (2') (oa)++ # 0}.
3

---

Definition 2 (Persistent Homology). PH indicates multi-scale version of homology applied over filtration [Wi]: == VR(W) S W, W, keeping track of holes created (bor)) or filled (died) as increases. Each persistence module PH₂ (HR(W) = { keeps track of a single k-persistence cycle "K. from birth to death. denote the entire lifetime of cycle 7 as T(r)) and its length as [T(>)] = death(?) - birth(y)- We will also use persistence diagrams, 2D plots of all persistence lifetimes (death birth). Note that for PHo, the Čech and VR complexes are equivalent.
Lifetime intervals are instrumental in TDA as they allow for extraction of topological features or summaries. Note that, each birth-death pair can be mapped to the cells that respectively created and destroyed the homology class, defining a unique map for a persistence diagram, which lends itself to differentibility (BGND+1] 19, CHN19, CHU17J. We conclude this brief section by referring the interested reader to the well established literature of persistent homology [Car14, EH10] for thorough understanding.
Intrinsic Dimension The intrinsic dimension of a space can be measured by using various notions. In this study, we will consider two notions of dimension, namely the upper-box dimension (also called the Minkowski dimension) and the persistent homology dimension. The box dimension is based on covering numbers and can be linked to generalization via [SSDE20), whereas the PH dimension based on the notions defined earlier in this section.
We start by the box dimension.
Definition 3 (Upper-Bon, Box Dimension). For a bounded metric space W. let Ns(W) denote the maximal number of disjoint closed 5-balls with centers in W. The upper box dimension is defined as:
dimBox W lim sup (Iog(N((WW)//ogg(((0))
(1)
6-40
We proceed with the PH dimension. First let define intermediate construct, which will play key role in our computational tools.
Definition (a- (a-Weighted Lifetime Sum). For a finite set W CWW C IRd, the weighted 7th homology lifetime sum is defined follows:
E (W)
Σ
[4(7)1,
(2)
(VR(W)))(W))
where PVR(V)(W)) is the i-dimensional persistent homology of the Čech complex on a finite point set W contained in W and [17] is the persistence lifetime as explained above.
Now, we are ready define the PH dimension, which the key notion in this paper.
Definition (Persistent Homology Dimension). The Pll--dmmnssinn of a bounded metric space W is defined as follows:
dimpn W = inf {a E. C; EC 0, V finite W CW]
(3)
In words, dimpu W is the smallest exponent a for which E is uniformly bounded for all finite subsets of W.
4 Generalization Error via Persistent Homology Dimension
In this section, will illustrate that the generalization enror can be linked to the PHg dimension. Our approach is based on the following fundamental result.
Theorem ([KLS06, Sch19]). Let W I be bounded set. Then, holds that:
dimp W == dimp W dimpox W.
In the light of this theorem, we combine the recent result showing that the generalization error can be linked to the box dimension [SSDE20], and Theorem 1, which shows that, bounded subsets of dd the box dimension and the PH dimension of order 0 agree.

---

By following the notation of [SSDE20], we consider standard supervised learning setting, where the data space is denoted by Z X D, and X' and y respectively denote the features and the labels. We assume that the data is generated via an unknown data distribution 'D and we have access (=1,...,2,) 2n), with the samples {2,) are independent and
to training set of n points, i.e., identically (i.i.d.) drawn from D.
We further consider parametric hypothesis class W C R4, that potentially depends S. We choose W to be optimization trajectories given by training algorithm A. which returns the entire (random) trajectory of the network weights the time frame [0. 77, such that [A(S)]e = wy being the network weights returned by A at 'time' t, and is continuous iteration index. Then, in the set W, we collect all the network weights that appear the optimization trajectory:
W = {w E RR E [0, w = [A(S)]+}
where we will set T without loss of generality.
To measure the quality of a parameter vector w E W. we use a loss function : R x + R4, such that f(w, 2) denotes the loss corresponding and empirical risks respectively by R(w) == E. [e[[(w, 2)] and R(w, = n Σ f(w, 2,). The generalization error is hence defined as [R(w, S) - R(w)].
single data point We then denote the population
We now recall [SSDE20, Asssumption H4], which is form of algorithmic stability [BE02]. Let us first introduce the required notation. For any > 0, consider the fixed grid on F
(2h 1)8
(2ja 1)6
G=
: E Z,i=
2v7
2vd
and define the set N8 = {u E G: Ba + 0), that is the collection of the centers of each ball that intersect W.
HI. Let - = (2 x x 2 ...) denote the countable product endowed with the product topology and let be the Borel o-algebra generated by n Let 3, be the sub-o sub-o-algebras of generated
Rd. n 2 1} and { {w N&):
by the collections of random variables given by (R(w,
8 Q W. G,n 2 1} respectively. There exists a constant M > 1 such that for any E
B E @ we have IP [[An MP [A]A]](BB
The next result forms our main observation, which will lead to our methodological developments. Proposition Let W C Ie be a (random) compact set. Assume that H/ holds, is bounded by B and L-Lipschitz continuous in Then, for sufficiently large, we have
[dmmp + 1] log" (mL2) ()L2)
log(7M/7)
sup [R( - R(w)] S /B wEW
(4)
7
with probability at least 1 7 over S Den
Proof. By using the same proof technique as ISSDE20, Theorem 21. we can show that (4) holds with dimBox W in place of dimpu W. Since W is bounded, we have dim W dimpu by Theorem 1. The result follows.
This result shows that the generalization error of the trajectories of a training algorithm is deeply linked to its topological properties as measured by the PH dimension. Thanks to novel connection, we have now access to the rich TDA toolbox, to be used for different purposes.
4.1 Analyzing Deep Network Dynamics via Persistent Homology
By exploiting TDA tools, our goal in this section is to develop an algorithm to compute dimpn W for two main purposes. The first goal is to predict the generalization performance by using dimpH- By this approach, we can use dimpH for hyperparameter tuning without having access to test data. The second goal incorporate dimpH as a regularizer to the optimization problem in order to improve generalization. Note that similar topologiaal regularization strategies have already been proposed
5

---

Algorithm 1: Computation of dimMpH
input :'he set of iterates W = {wi) 1=1 smallest sample size Amnin and a skip step A, a output output:dimpp :dimp W
3 n f- Romin. E 4
while K do
W, & Sample(W,n) a) // randon sampling
Wn < vR(Wn) // Vietoris-Rips filtration
Eli + (VV.)) (vE [(()) / // compute lifetime sums from PH
n+ +
m, b fitline (log(nmin A: K), log(E)) // power law on F((W)
10 dimpnW + 1-m
[BGND + 19, CNBW19] without formal link to generalization. In this sense, our observations form the first step towards theoretically linking generalization and TDA.
In (SSDE20), to develop computational approach, the authors first linked the intrinsic dimension to certain statistical properties of the underlying training algorithm, which can be then estimated. To do so, they required an additional topological regularity condition, which necessitates the existence of an 'Ahlfors regular' measure defined on W, i.e., a finite Borel measure μe such that there exists S Tu- This
s, ru > where < ar I (x), S br* < co, holds for all x W,0 assumption was used to link the box dimension to another notion called Hausdorff dimension, which can be then linked to statistical properties of the training trajectories under further assumptions (see Section 1). An interesting asset of our approach is that, we do not require this condition and thanks to the following result, we are able to develop an algorithm to directly estimate dimpnW, while staying agnostic to the finer topological properties of W.
Proposition 2. Let W C Rdd be a bounded set with dimpu W d:. Then, for all & >> 0 and (0, d' + e), there exists a constant Da,e, such that the following inequality holds for all N and all collections Wn = [wi,...; W with wi E WW
n.
E (WW & Da,en 2=
(5)
Proof. Since W is bounded, we have dimmox = d' by Theorem 1. Fix & 0. Then, by Definition 3, there exists on = do(E) > 0 and a finite constant Ce > 0 such that for all S dg the
following inequality holds:
No(W) S C_8-(a++e),
(6)
Then, the result directly follows from [Sch20, Proposition 21].
This result suggests a simple strategy to estimate an upper bound of the intrinsic dimension from persistent homology. In particular, we note that rewriting (5) for logarithmic values give us that
(1 (1-3a) a (1-a+t cc) log n + log Da. 2 log Eq
d'
If log F. and log n are sampled from the data and give an empirical slope m, then we see that d' S - In many cases,
that d' _ (as further explained in Sec. 5.2), so take 1-m as our PH dimension estimation. We provide the full algorithm for computing this from sampled data in Alg. Note that our algorithm similar to that proposed in [AAF+20], although our method works for sets rather than probability measures. In our implementation we compute the homology by the celebrated Ripser package [Bau21] unless otherwise specified.
On computational complexity. Computing the Vietoris Rips complex is an active area of research, as the worst-case time complexity meaningless due to natural sparsity [Zom10). Therefore, to calculate the time complexity of our estimator, we focus on analyzing the PH computation from the output simplices: calculating PH takes O(p") time, where w < 2.4 the constant of matrix multiplication and is the number of simplices produced in the filtration [BP19]. Since compute

---

cnn-9 on mnist
fon-5 on mnist
ton-7 on mnist
cnn-9 on citar10
1.0
24
0.17
0.12
0:12
1.5
0.14
1.5
0.12
1/6
0.12
1.2
Accurncy
1.4
Test Acquiao
Accuracy
1.8
Text Acpuracy
0.00
0.00
0
88
$8.2
99.4
99.6
90.2
58.4
50.5
80.0
87.5
98
88.5
50
72
74
76
78
00
2.2
0.00
P1--Immrooon
0.04
1.8
0.03
1.0
1,5
00:
0.075
1/8
Textl
1.6
67.8
Figure 2: PH-dimension vs test accuracy for different models and datasets. The rows correspond to the model and dataset, and the columns correspond to the batch size (50 and 100 for the top and bottom row respectively). The graphed points are marked with different colors corresponding to the learning rate. Note that the PH dimension is inversely correlated with test accuracy and is thus positively correlated with generalization error.
with 0th order homology, this would imply that the computational complexity is Onn"), where n is the number of points. In particular, this means that estimating the PH dimension would take (kk"") time, where k is the number of samples taken assuming that samples evenly spaced in [0, n).
4.2 Regularizing Deep Networks via Persistent Homology
Motivated by our results in proposition 2, we theorize that controlling dimpH W would help in reducing the generalization error. Towards this end, we develop a regularizer for our training procedure which seeks to minimize dimph W during train time. we let L be our vanilla loss function, then we will instead optimize over our topological loss function LA := C + À dimpH W, where X Z 0 controls the scale of the regularization and W now denotes a sliding window of iterates (e.g., the latest 50 iterates during training). This way, we aim to regularize the loss by considering the dimension of the ongoing training trajectory.
In Alg. 1, we let wy be the stored weights from previous iterations for {1..... K 1} and let wk the current weight iteration. Since the persistence diagram computation and linear regression are differentiable, this means that our estimate for dimpH is also differentiable, and, if ww is sampled as in Alg. 1, connected in the computation graph with wk. We incorporate our regularizer into the network training using PyTorch [PGM+ 19] and the associated persistent homology package torchph [CHU17, CHN19].
Experimental Evaluations
This section presents our experimental results in two parts: (i) analyzing and quantifying generaliza- tion in practical deep networks on real data, (ii) ablation studies on random diffusion process. In all the experiments we will assume that the intrinsic dimension is strictly larger than 1, hence we will set a = 1, unless specified otherwise. Further details are reported the supplementary document.
5.1 Analyzing and Visualizing Deep Networks
Measuring generalization. We first verify our main claim by showing that our persistent homol- ogy dimension derived from topological analysis of the training trajectories correctly measures of generalization. To demonstrate this, we apply our analysis to wide variety of networks, training procedures, and hyperparameters. 7-layer (f fully connected networks, and a 9-layer convolutional netowork (cnn-9) on MNIST, CIFARIO 10 and CIFAR 100 datasets for multiple batch sizes and learning rates until convergence. For AlexNet, we consider 1000 iterates prior convergence and, for the others, we only consider 200. Then, we estimate dimph on the last iterates by using Alg. 1. For varying n, we randomly pick n of last iterates and compute E.. and then we use the relation given in (5).
particular, we train AlexNet [KSH12], a 5-layer (fen-5) and
7

---

am Citarto
Eatch Size 64
Betch Size 100
Barch Size 128
2.2
22
22
2
2
1.0
1.8
1.8
1.8
Test Gap
1.8
Test Gap
1.6
Test Gop
27
26
29
30
31
27
28
29
30
31
27
28
29
30
31
2.5
2.6
0mgy Citer000
2.45
2.5
RMSSprp
2.45
Adam
2.4
2.5
2.4
235
2.45
Gap
2.3
2,3
244
30
40
Figure 3: (Estimated) persistent homology dimension vs generalization error (training accuracy test accuracy) for different datasets (top row CIFARIO, bottom row CIFARI00) and optimizers on AlexNet. We plot the data points and lines of best fit. Note that the PH dimension is directly correlated with the generalization error and is consistent across datasets and optimizers.
We obtain the ground truth (GT) generalization error as the gap between training and test accura- cies. Fig. 2 plots the PH-dimension with respect to test accuracy and signals strong correlation of our PH-dimension and actual performance gap. The lower the PH-dimension, the higher the test accuracy. Note that this results aligns well with that of [SSDE20]. The figure also shows that the intrinsic dimensions across different datasets can be similar, even if the parameters of the models can vary greatly. This supports the recent hypothesis that what matters for the generalization is the effective capacity and not the parameter count. In fact, the dimension should be as minimal as possible without collapsing important representation features onto the same dimension. The findings in Fig. 2 are further augmented with results in Fig. 3, where a similar pattern is observed on AlexNet and CIFARIOO.
Can dimpH capture intrinsic properties of trajectories? After revealing that our ID estimation gauge for generalization, we set out investigate whether it really hinges on the intrinsic properties of the data. We train several instances of 7-fcn for different learning rates and batch sizes. We compute the PH-dimension of each network using training trajectories. We visualize the following in the rows of Fig. 4 sorted by dimpH: (i) 200 x 200 distance matrix of the sequence of iterates wi...., W/K (which the basis for PH computations), (ii) corresponding log E estimates as we sweep over n in an increasing fashion, (iii) persistence diagrams per each distance matrix. It clear that there is a strong correlation between dimpH and the structure of the distance matrix. As dimension increases, matrix of distances become non-uniformly pixelated. The slope estimated from the total edge lengths the second row a quantity proportional to our dimension. Note that the slope decreases as our estimte increases (hence generalization tends to decrease). We further observe clusters emerging in the persistence diagram. The latter has also been reported for better generalizing networks, though using a different notion of topological space [BGND* 19].
Is dimph a real indicator of generalization? To quantitatively assess the quality of our complexity measure, we gather two statistics: (i) we report the average p-value over different batch sizes for AlexNet trained with SGD on the Cifar100 dataset. The value of p 0.0157 < 0.05 confirms the statistical significance. Next, we follow the recent literature [JFY* 20] and consult the Kendall correlation coefficient (KCC). Similar to the p-value experiment above, we compute KCC for SIDX for different batch sizes (64, 100, 1 128) and attain (0.933, 0.357, (1733) respectively. Note that, a positive correlation signals that the test gap closes as dimru decreases. Both of these experiments agree with our theoretical insights that connect generalization to a topological characteristic of a neural network: intrinsic dimension of training trajectories.
Effeet of different training algorithms. We also verify that our method is does not require assumptions on the training algorithm. In particular, we show that our above analyses extend to both the RMSProp [TH12] and Adam [KB15] optimizer. Our results are visualized in Fig. 3. We plot the dimension with respect to the generalization error for varying optimizers and batch sizes: our results verify that the generalization error (which is inversely related to the test accuracy) is
aggostic and
8

---

dump 2.2935
du 2.0355
dim 2.0059
di 1.947
dimpx 1.5784
dim 1.7579
dii 1.6568
Dist. matr.
4
logiE
10
10
Pers. Diag.
10
24
Hg
2
<10
100
X10
x10
x10
x10
x10*
Figure 4: We visualize topological information for 7-layer fully connected network on CIFARIO 10 data. In the top row, we visualize the distance matrices computed between network weights corresponding to the last 200 iterations of training. In the middle, we visualize the corresponding behavior of our estimator as we increase the number of samples. In the bottom row, we visualize the O-th order persistent diagrams for the full data. As our PH dimension decreases, the matrix becomes more segmented, the estimator slope decreases, and the persistent diagram becomes sparser. We provide more information about these results in the supplement.
positively correlated with the PH dimension. This corroborates our previous results in Fig. 2 and in particular shows that our dimension estimator of test gap is indeed algorithm-agnostie.
Encouraging generalization via regularization dimPH. We furthermore verify that our topological regularizer is able to help control the test gap in accordance with our theory. We train a Lenet-5 network [LBBH98] on C0far10 [Kri09] and compare clean trianing with a training with our topological regularizer with X set to 1. We train for 200 epochs with batch size of 128 and report the train and test accuracies in Fig. over a variety of learning rates. We tested over 10 trials and found that, with p < 0.05 for all cases except Ir = 0.01, the results are different.
Figure 5: Effect of regularization on test ac-
Our topologiaal optimizer is able to produce the best improvements when our network is not able to converge well. These results show that our regularizer behaves as expected: the regularizer is able to recover poor training dynamics. We note that this experiment uses simple architecture and as such, it presents a proof of concept. We do not aim for the state of the art results. Furthermore, we directly compared our approach with the generalization estimator of [CMEM20], which most closely resembles our construction. In particular, we found their method does not scale and is often numerically unreliable. For example, their methodology grows quadratically with respect to number of network weights and linearly with the dataset size, while our method does not scale much beyond memory usage with vectorized computation. Furthermore, for many of our test networks, their metric space construction (which is based off of the correlation between activation functions and used for the Vietoris-Rips complex) would be numerically brittle and result in degenerate persistent homology. These prevent [CMEM20) to be applicable in this scenario.
curacy for various learning rates. Our regular- ization consistently able to produce higher accuracies, and this effect is more pronounced when the network has lower test accuracy.
5.2 Ablation Studies
To assess the quality of our dimension estimator, we now perform ablation studies, on a synthetic data whose the ground truth ID is known. To this end, we use the synthetic experimental setting

---

Figure 6: Estimated intrinsic dimension vs ground-truth intrinsic dimension for different dimension estimators on synthetic diffusion data. Our PHo (yellow) and PH,RANSAC (purple) estimators coincide as the linear regression step of our computation is well behaved. We note that our persistent homology dimension estimation is able to accurately recover the ground truth.
presented in [SSDE20) (see the supplementary document for details), and we simulate d 128 dimensional stable Levy process with varying number of points 100 S n S 1500 and tail indices 1 S B < 2. Note that the tail index equals the intrinsic dimension in this case, which is order of magnitude lower for this experiment.
Can dimpH match the ground truth ID? We first try to predict the GT intrinsic dimension running Alg. 1 on this data. We also estimate the TwoNN dimension [FdRL17] to quantify how the state of the art IDD estimators correlate with GT in such heavy tailed regime. Our results are plotted in Fig. 6. Note that as increases our estimator becomes smoother and well approximates the GT up to slight over-estimation, a repeatedly observed phenomenon [CCCR15]. TwoNN does not guarantee recovering the box-dimension. While it is found to be useful in estimating the ID of data ALMM29)), we find it to be less desirable in heavy-tailed regime as reflected in the plots Our supplementary material provides further results on other, non-dynamics like synthetic dataset such as points on a sphere where TwoNN can perform better. We also include a robust line fitting variant of our approach THo--RNNSCC where random sample consensus is applied iteratively. Though, as our data is not curlier-crrupptdd, we do not observe a large improvement.
Effect of on dimension estimation. While our theory requires a to be smaller than the intrinsic dimension of the trajectories, in all of our experiments is of curiosity whether such choice hampers our estimates. To see the effect, estimates in Fig. 7. It is observed (blue curve) that our dimen- sion estimate follows U-shaped trend with increasing a. We indicate the GT ID by a dashed red line and our estimate as a dashed green line. Ideally, these two horizontal lines should overlap. It is noticeable that, given the oracle for GT ID, it might be possible to optimize for an a*. Yet, such information is not available for the deep networks. Never- theless, a seems to yield reasonable performance and we leave the estimation of a better a for future work. We provide additional results in our supplementary material.
fix a 1.0. It
vary in range [0.5, 2.5] and plot our
Figure dimpH estimate versus vari- ous a on the synthetic diffusion data. Our estimate of provides a very good estimate for wide variety of intrinsic di- mensions.
Conclusion
In this paper, we developed novel connections between dimpH of the training trajectory and the generalization error. Using these insights, we proposed a method for estimating the dimpH from data and, unlike previous work [SSDE20], our approach does not presuppose any conditions on the trajectory and offers a simple algorithm. By leveraging the diffcrentiabiliiy of PH computation, we showed that different setups.
use dimrh as regularizer during training, which improved the performance in
Societal Impact and Limitations. We believe that our study will not pose any negative societal or ethical consequences due to its theoretical nature. The main limitation of our study is that it solely considers the terms Ea whereas PH offers much richer structure. Hence, as our next step, we will explore finer ways to incorporate PH in generalization performance. We will further extend our results in terms of dimensions of measures by using the techniques presented in [CDE* 21].
10

---

Acknowledgements
Umut Şimşekli's 's research supported by the French government under management of Agence Nationale de la Recherche part of the "Investissements d' d'avenir" program, reference ANR-19. P3IA-0001 (PRAIRIE 31A Institute).
References
[AAF*20]
Henry Adams, M. Aminian, Elin Farnell, M. Kirby, C. Peterson, Joshua Mirth, R. Neville, P. Shipman, and C. Shonkwiler. A fractal dimension for measures via persistent homology. arXiv: Dynamical Systems, pages 1-31, 2020.
[AGNZI8]
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In Proceedings of the 35th Interna- tional Conference on Machine Learning, volume 80, pages 254-265- PMLR, 10-15 Jul 2018.
[ALMZ19]
Alessio Ansuini, Alessandro Laio, Jakob H Macke, and Davide Zoccolan. Intrinsic dimension of data representations in deep neural networks. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), volume 32. Curran Associates, Inc., 2019.
[Bau21]
Ulrich Bauer. Ripser: efficient computation of vietoris-rips persistence barcodes, February 2021. Preprint.
[BE02]
Olivier Bousquet and André Elisseeff. Stability and generalization. JMLR, 2(Mar), 2002.
[BGND 19]
Rickard Fabril-aabr,,sson,, Bradley J Nelson, Anjan Dwaraknath, Primoz Skraba, Leonidas J Guibas, and Gunnar Carlsson. A topology layer for machine learning. arXiv preprint arXiv: 12200, 2019.
[BM02]
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463- 482, 2002.
[BO18] Léonard Blier and Yann Ollivier. The description length of deep learning models. In S. Bengio, H. Wallach, H. Larochelle. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), volume 31. Curran Associates, Inc., 2018
[BP19]
Jean-Daniel Boissonnat and Siddharth Pritam, Computing Persistent Homology of Flag Complexes via Strong Collapses. In 35th International Symposium Computa- tional Geometry (SoCG 2019), volume 129 of Leibniz International Proceedings in Informatics (LIPlcs), pages 55:1-55:15. 2019.
[BSE+21] Melih Barsbey, Milad Sefidgaran, Murat A Erdogdu, Gaël Richard, and Umut Şimşekli. Heavy tails in sgd and compressibility of overparametrized neural networks. In NeurlPS, 2021.
[Car14]
Gunnar Carlsson. Topological pattern recognition for point cloud data. Acta Numerica, 23:289-368, 2014.
[CCCR15]
Campadelli, E Casiraghi, C Ceruti, and Rozza. Intrinsic dimension estima- tion: Relevant techniques and a benchmark framework. Mathematical Problems in Engineering. 2015, 2015.
[CDE*21] Alexander Camuto, George Deligiannidis, Murat A Erdogdu, Mert Gürbüzzalabaa, Umut Şimşekli, and Lingjiong Zhu. Fractal structure and generalization properties of stochastic optimization algorithms. In NeurIPS, 2021.
[CHN19]
M. Dixit C. Hofer, R. Kwitt and M. Niethammer. Conneciiiiy-oppimizee representa- tion leamiing via persistent homology. In ICML, 2019.
(CHU17]
Niethammer Hofer, R. Kwitt and A. Uhl. Deep learning with topological signatures. In NIPS, 2017.

---

[CMEM20]
C. Comeanu, M. Madadi, S. Escalera, and A. Martínez. Computing the testing error without a testing set. 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 2674-2663 2020.
[CNBW19] Chao Chen, Xiuyan Ni, Qinxun Bai, and Yusu Wang. A topological regularizer for classifiers via persistent homology. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2573-2582. PMLR, 2019.
[CWZ*21] Alexander Camuto, Xiaoyu Wang, Lingjiong Zhu, Chris Holmes, Mert Gürbüzbalaban, and Umut Şimyekli. Asymmetric heavy tails and implicit bias in gaussian noise injections. ICML, 2021.
[DBI18] Haowen Deng. Tolga Birdal, and Slobodan Ilic. Ppfnet: Global context aware local features for robust 3d point matching. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 195-205, 2018
[DCLT18] Jacob Devlin, MlingWWei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- training of deep bidirectional transformers for language understanding, arXiv preprint arXiv:18IO. 04805, 2018.
[DZF19]
P. Dollár, C. L. Zitnick, and P. Frossard. What does it mean learn in deep networks and, how does one detect adversarial attacks 2019.
[EH10]
Herbert Edelsbrunner and John Harer. Computational topology: an introduction.
American Mathematical Soc., 2010.
[EMH+ 19]
Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, et al. Neural architecture search: A survey. Journal of Machine Learning Research, 20(55):1-21, 2019.
[FC18]
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2018.
[FdRL17)
Elena Facco, Maria d' d'Errico, Alex Rodriguez, and Alessandro Laio. Estimating the intrinsic dimension of datasets by a minimal neighborhood information. Scientific reports, 7(1):188, 2017.
[FGFAEV21] David Pérez Fernández, Asier Gutiérrez-Fandiño, Jordi Hemengol-Estapts and Marta Villegas. Determining structural properties of artificial neural networks using algebraic topology. arXiv preprint arXiv:2101.0777 2021.
[Ghrl0]
Robert Ghrist. Configuration spaces, braids, and robotics. In Braids: Introductory Lectures Braids, Configurations and Their Applications, pages 263-304 World Scientific, 2010.
[GJ16]
Tianxiang Gao and Vladimir Jojie. Degrees of freedom in deep neural networks. UAI' 16, page 232-241. AUAI Press, 2016.
[GLW+21]
Zan Gojeic, Or Litany, Andreas Wieser, Leonidas J. Guibas, and Tolga Birdal. Weakly supervised learning of rigid 3d scene flow. In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition (CVPR), pages 5692-5703, June 2021.
[GSZ21]
Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail -til phenomenon in sgd. In International Conference on Machine Learning, pages 3964-3975. PMLR, 2021.
[HJTW21] Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang. Generalization bounds via distillation. In International Conference on Learning Representutions, 2021.
[HM20]
Liam Hodgkinson and Michael W. Mahoney. Multiplicative noise and heavy tails in stochastic optimization. arXiv:2006.06293 [cs, math, stat], June 2020.
[JH155]
Lucas Janson, William Fithian, and Trevor J Hastie. Effective degrees of freedom: a flawed metaphor. Biometrika, 102(2):479 485, 2015.
[F
Yiding Jiang, Pierre Foret. Scott Yak, Daniel M Roy, Hossein Mobahi, Gintare Karolina Dziugaite, Samy Bengio, Suriya Gunasekar, Isabelle Guyon, and Behnam Neyshabur. Neurips 2020 competition: Predicting generalization in deep learning (version 1.1). Technical report, Technical Report Preprint: December 16, 2020.
12

---

[KB15]
Curran Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR,
2015.
[KIS006]
Gady Kozma, Zvi Lotker, and Gideon Stupp. The minimal spanning tree and the upper box dimension, Proceedings of the American Mathematical Society, 134(4): 1187, 2006.
[Kri09]
A. Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[KSH12]
Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet elassification with deep convolutional neural networks. Advances in neural information processing systems, 25:1097-1100 105, 2012.
[LBBH98]
Y. LeCun, L. Bottou, Yoshua Bengio, and P. Haffner. Gradient-based learning applied to document recognition. 1998.
[LFLY18]
Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In International Conference on Learning Representations, 2018.
[MM19]
Charles H Martin and Michael W Mahoney. Traditional and heavy-tailed self regular- ization in neural network models. In International Conference on Machine Learning (ICML), 2019.
[MWH 18]
Xingjun Ma, Yisen Wang, Michael Houle, Shuo Zhou, Sarah Erfani, Shutao Xia, Sudanthi Wijewickrema, and James Bailey. Dimensionality-drin learning with noisy labels. International Conference on Machine Learning, pages 3355-3364. PMLR, 2018.
[NBMS17]
Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Nati Srebro. Explor- ing generalization in deep learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[PGM+19]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmai- son, Andreas Kopf, Edward Yang, Zachary Vetioo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style. high-performance deep learning library. In H. Wal- lach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages Associates, Inc., 2019.
[QSMG17] Charles Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 652-660, 2017.
[RB21]
Yohai Reani and Omer Bobrowski. Cycle registration in persistent homology with applications in topological bootstrap. arXiv preprint arXiv:2101.00698, 2021.
[RBH+21] Davis Rempe, Tolga Birdal, Aaron Hertzmann, Jimei Yang. Srinath Sridhar, and Leonidas J. Guibas. Humor: 3d human motion model for robust pose estimation. In Proceedings of the IEEF/CVF International Conference on Computer Vision (ICCV), pages 11148-11444 1149, October 2021.
19)
Bastian Alexander Rieck, Matteo Togninalli, Christian Bock, Michael Moor, Max Horn, Thomas Gumbsch, and K. Borgwardt. Neural persistence: A complexity measure for deep neural networks using algebraic topology. ArXiv, abs/18 181.0944, 2019.
[SAM*20 20]
Taiji Suzuki, Hiroshi Abe, Tomoya Murata, Shingo Horiuchi, Kotaro Ito, Tokuma Wachi, So Hirai, Masatoshi Yukishima, and Tomoaki Nishimura. Spectral pruning: Compressing deep neural networks via spectral analysis and its generalization error. In International Joint Conference on Artificial Intelligence, pages 2839-22 2009922846664 2020.
[SAN20]
Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura. Compression based bound for com-compeessed network: unified generalization error analysis of large compressible deep neural network. In International Conference on Learning Representations, 2020.
13

---

[Sch09]
Manfred Schroeder. Fractals, chaos, power laws: Minutes from an infinite paradise. Courier Corporation, 2009.
[Sch19]
Benjamin Schweinhart. Persistent homology and the upper box dimension. Discrete & Computational Geometry, pages 1-34, 2019.
[Sch20]
Benjamin Schweinhart. Fractal dimension and the persistent homology of random geometric complexes. Advances in Mathematics, 372: 172:107291, 2020.
IŞGN* 19]
Umut Şimşekli, Mert Gürbüüzaalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprini arXiv: 19/2.000/ 2019.
[SSDE20]
Umut Simsekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. In Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
[SSG19]
Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference Machine Learning, pages 5827-5837. PMLR, 2019.
[SZTG20]
Umut Simsekli, Lingjiong Zhu, Yee Whye Teh, and Mert Gurbuzhalaban. Fractional underdamped langevin dynamics: Retargeting sgd with momentum under heavy-tailed gradient noise. In International Conference on Machine Learning, pages 8970-8980. PMLR, 2020.
[TH12]
T. Tieleman and G. Hinton. Lecture 3--RssProp: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
[Vap68]
Vladimir Vapnik. On the uniform convergence of relative frequencies events to their probabilities. In Doklady Akademii Nauk USSR, volume 181, pages 781-787, 1968.
[ZBH*21]
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Un- derstanding deep learning (still) requires rethinking generalization. Communications of the ACM, 6473):107-115, 2021.
[ZBL+20] Yongheng Zhao, Tolga Birdal, Jan Eric Lenssen, Emanuele Menegatti, Leonidas Guibas, and Federico Tombari. Quaternion equivariant capsule networks for 3d point clouds. European Conference on Computer Vision, pages 1-19. Springer, 2020.
[Zom10]
Afra Zomorodian. Fast construction of the vietoris-rips complex. Computers & Graphics, 34(3):263-217 2010.
[ZQH+18] 18]
Wei Zhu, Qiang Qiu, Jiaji Huang, Robert Calderbank, Guillermo Sapiro, and Ingrid Daubechies. Ldmnet: Low dimensional manifold regularized neural networks. In Pro- ceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2743-2751, 2018.
14


Reviews:
[{"review_id": "SMvrQKgk7sO", "reviewer": "Reviewer_MbMP", "summary": "This paper proposes a measure of generalization based on persistence homology, a standard technique of topological data analysis.\n\nThe proposed measure, the persistence homology dimension (PHD), is computed on optimization trajectories during training.\n\nA theoretical connect between PHD and generalization is made using existing results in the literature: first the equivalence of PHD and the box-dimension [KLS06, Sch19], and second that the generalization error may be bounded under the box dimension (under the assumption that the optimization dynamics follow a Feller process).\n\nFrom these main result of the paper, Proposition 1, then follows under assumption (H1) . \nThe authors then proceed to remove the Feller requirement in Proposition. 2 using a recent result in the mathematics literature [Sch20].\n\nBased on these results, an algorithm for computing PHD is proposed.\n\nThe authors proceed to perform an empirical evaluation of how well PHD predicts generalization for select deep network architectures (alexnet, cnn-9, fcn-5, fcn-7), datasets (mnist, cifar-10, cifar-100), and training hyperparameters (learning rate, batch size).\n\nThe authors visualize these results in Figures 2 and 3, where in Figure 3 the authors claim that PHD \"directly\" correlates with generalization error across experimental settings. Linear trends are evident in the plots, however no measures of goodness of fit are given.\n\nIn addition, a novel loss regularizer is proposed based on their PHD measure. The effect on generalization of his regularizer is studied, but small differences are shown.\n\nAblation studies are additionally carried out.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work addresses an important problem, predicting generalization, and approach it from an interesting perspective, that of TDA. \n\nI have some doubts about the empirical evaluation of PHD's predictive ability of generalization. No quantitative measures are given. There indeed appears to be trends in Figures 2 and 3, but their strength is unclear.\n\nEven so, as some have pointed out in the literature, correlative measures may be problematic and not indicative of a causal relationship [0,1].\n\nFor instance in [0], the authors write:\n*Correlation with Generalization: Evaluating measures based on correlation with generalization is very useful but it can also provide a misleading picture. To check the correlation, we should vary architectures and optimization algorithms to produce a set of models. If the set is generated in an artificial way and is not representative of the typical setting, the conclusions might be deceiving and might not generalize to typical cases... Another pitfall is drawing conclusion from changing one or two hyper-parameters (e.g changing the width or batch-size and checking if a measure would correlate with generalization). In these cases, the hyper-parameter could be the true cause of both change in the measure and change in the generalization, but the measure itself has no causal relationship with generalization. Therefore,one needs to be very careful with experimental design to avoid unwanted correlations.*\n\nCan the authors justify their choice of empirical methodology, over the Kendall's rank correlation and conditional mutual information as suggested by [1]?\n\nUsing the measure for regularization is a natural and interesting idea. However it's empirical evaluation appears weak in Figure 5, i.e. < +2%, except for the high learning rate case. I would like to see error bars on this experiment to gauge it's significance.\n\nMinor notes: Typo on line 256 \"netowork\"\n\n[0] Fantastic  Generalization  Measures and  Where  to  Find  Them - Jiang et al. (2019)\nhttps://arxiv.org/abs/1912.02178 \n\n[1] NeurIPS 2020 Competition:Predicting Generalization in Deep Learning - Jiang et al. (2020)\nhttps://arxiv.org/abs/2012.07976v1", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A brief but adequate discussion of societal impacts is given in Section 6.\n\nA brief discussion of limitations is given in Section 6, which could be expanded.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "PsvdUkMZD2Z", "reviewer": "Reviewer_pbGK", "summary": "The authors establish a relationship between the generalization error of trajectories obtained from a training algorithm and the persistent homology (PH) dimension. The theoretical contribution of this work involves combining two results: (1) box dimension of a bounded set can be computed using PH0 dimension [KLS06, Sch19], and (2) previous work linking box dimension and generalization error [SSDE20]. Based on these theoretical findings, the authors propose a simple algorithm to compute PH dimension directly, by performing a line fit on 0-dimensional topological features derived from weights in previous training iterations. This algorithm is based on mild assumptions, in contrast to previous work on computing the fractal dimension of training trajectories. Experiments applying this algorithm to a variety of networks (including AlexNet, CNNs and FCNs trained on MNIST, CIFAR10 and CIFAR100) and training algorithms (SGD, RMSprop and Adam) show that the PH dimension is inversely correlated with test accuracy. Next, the authors took advantage of the differentiability of persistent homology to incorporate the PH dimension computed from previous iterates as a regularizer to control the generalization error. The topological regularizer improved performance on the test dataset, especially at high learning rates where the unregularized network has low test accuracy. Finally, the authors performed ablation studies using synthetic data generated from β-stable Levy processes that exhibit heavy-tails observed in network trajectories. PH dimension outperformed other intrinsic dimension estimators in these tests, with varying number of points, ambient dimensions and line fitting procedures.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nThis work combines previous theoretical results to propose a practical methodology for estimating intrinsic dimension using topological data analysis (TDA). Novel contributions include verification of the proposed PH dimension calculation algorithm on synthetic data and its practical application in multiple networks to demonstrate its usefulness in quantifying generalization error. The proposed regularization, based on PH dimension, is shown to be effective at controlling generalization error during training. All related work, datasets, and models are cited.\nQuality:\nThe exposition is technically sound, and theoretical findings are supported by experiments. The authors provide context for their work within the broader scope of intrinsic dimension estimation, manifold reconstruction, bounds of generalization error, and the application of TDA to analyze deep networks. The authors clearly state that the α parameter should be smaller than the intrinsic dimension in theory, but the experiments were performed with fixed α = 1. I suggest the following improvements:\n1) Definition 4: where PHi(VR(W)) is the i dimensional persistent homology of the Cech Vietoris-Rips complex on a finite point set …\n2) Please consider including computational complexity and/or runtime performance of estimating PH dimension and the extra training time required when using PH dimension as a regularizer.\n3) Figure 7 (main text) is hard to read and poorly labelled.\n4) In SM Fig. 1, please indicate in the caption that PCA is outside the bounds of the axis limits.\n5) In SM Fig. 7, consider using the same axis limits for all figures to allow for easy comparison. The observed changes in the persistence diagrams corresponding to changes in the intrinsic dimension are not explained. Why do points move closer to or away from the diagonal?\n6) Similar to comment (3) above, the visualization of distance matrices (Fig. 4 in the main text, SM Figs. 5 and 6) showing non-uniform pixelation merits further explanation. How are the rows and columns of these matrices organized? Can the non-uniform pixelation be quantified and what does it represent?\nClarity:\nThe main paper and the supplementary material are very well organized and clearly written. I discovered only a few typos and grammatical mistakes that can easily be corrected. Reference to Fig. 5 in the supplement shows up as a ‘?’.\nSignificance:\nThe analysis of generalization error associated with various training algorithms is important for uncovering how deep networks learn and operate. This work is a significant contribution in this direction. The authors describe a practical algorithm, based on solid theoretical foundations, for estimating the intrinsic dimension of training trajectories and link it to generalization error. As demonstrated in this manuscript, the PH dimension can be used to evaluate different hyperparameters and control generalization loss during training. Higher-dimensional topological features computed from training trajectories may yield more insight in the future.\n\nI am satisfied by the author responses and will maintain the high score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed in the manuscript. No negative societal impact expected from this work.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 "}, "extra_text": {}}, {"review_id": "HMxT2qkysgG", "reviewer": "Reviewer_PP68", "summary": "The relationship between generalized loss of NN and Intrinsic Dimension by Persistent homology is mathematically proved. They also propose a normalization term based on the theory presented. In addition, we experimentally verify the theoretical results and confirm the effectiveness of the proposed algorithm.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "For the normalization term of NN loss, many methods exist, but many are experimental and few have been mathematically proven. Mathematical analysis is necessary for the future development of technology. This paper logically shows that the generalization of NN can be adjusted by intrinsic dimension based on persistent homology. Most of the theories presented are based on previous results, but they are well developed for the generalization of NNs. Although the proposed normalization term is a simple one, it seems to be significant just because it shows the mathematical implications. Many normalization terms have been proposed in the past. In this paper, only the effect for one problem is shown, but in practical terms, comparison with other normalization terms may be necessary. In addition, since persistent homology is generally computationally expensive, future evaluation in terms of computational complexity will be necessary.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't believe there are any negative effects, and I think this is something that can be developed in the future, but for practical purposes, it needs more testing.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "-BsbvO97bdH", "reviewer": "Reviewer_J8S7", "summary": "The paper proposes to use an estimator of the intrinsic dimension (ID)  based on topological data analysis for two goals, both important in neural network theory: (1) as a proxy of  the test accuracy, which allows estimating it without performing explicitly any validation and (2) as a regularizer, by adding an ID-dependent term to the loss. A part of the paper is devoted to derive (or recall from the literature) rigorous properties of this ID estimator. \n", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The quality of the presentation is in general poor and the results of the numerical tests seem to me already present in the literature, and  in a case possibly flawed.  \n\nFig 2: the x axis are not labeled. Fig 3: the dataset on which the tests are performed is not specified. If the x axis (not labeled) is  the difference between test and train accuracy, then this  ranges between 30 and 40. IThese differences are enormous, for any dataset mentioned in the paper, pointing to possible flaws in the model. Fig.  4 is unreadable, even by magnifying it. Its message is, at least to me, obscure. In the middle panel we see points approximately lying on a line, which is floating up and down across the panels. What do we learn from this? the bottom lines the two sets of points are labeled H_0 and infinity. What does this mean? Fig 7 is also unreadable. The axis labels are missing. The different panels are also not labeled. \n\nThe idea of regularizing learning by controlling the ID is not new. It was introduced in ref [MA] https://arxiv.org/abs/1806.02612  (2018). This is a key reference that should be cited and discussed. The results illustrated in the manuscript on this important point are not really convincing: in fig 5 it is shown that with the learning rate which allows obtaining the best test accuracy the effect of ID regularization  is practically zero (65 % with and without regularization). Moreover, an accuracy of 65 % in cifar10 is way below the state of the art for this dataset which is 95 % for convolutional NNs, and almost 99 % for architectures exploiting transformers (see for example https://paperswithcode.com/sota/image-classification-on-cifar-10). Also this points to possible flaws.\n\nThe intrinsic dimensions reported in fig 2 and 3 are of order 2, while those reported in ref ALMZ19 and [MA] range between 10 and 100, for the Imagenet dataset. The reason for this qualitative discrepancy should be discussed. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "the limitations of the approach are discussed only shortly, possibly due to length constraints. But I do not see this as the main  problem of the poper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper identifies a notion of intrinsic dimension that can be rigorously linked to generalization performance. Given the scarceness of rigorous results in this field, it is an important achievement. It backs up the theoretical results by numerical experiments. A number of reviewers pointed out the difficulty to read and interpret the figures. It is important that the authors make on effort on that point before publication. The reviewers seem mostly convinced by the authors answers. After the rebuttal, reviewer J8S7 acknowledges the originality of the theoretical contribution of the paper (its main strength), but remains partially convinced by the answers concerning the large gap in terms of performance with respect to the state of the arts networks. I completely agree with reviewer J8S7 that such performance gap is a source of doubts. Therefore, I invite the authors to or discuss in details the reasons for that gap, and the choice behind these experiments despite this gap (that can be closed with simple networks), as they discuss in their response; or to improve the generalization. Otherwise, it gives an impression that the results of the paper may only apply in trivial regimes of (lack of) learning and therefore would not be relevant to applications. That being said, I have no doubts that all these improvements will be implemented by the authors and will only improve the overall quality.
Decision: Accept (Poster)