Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

main_review: Originality:
This 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.
Quality:
The 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:
1) Definition 4: where PHi(VR(W)) is the i dimensional persistent homology of the Cech Vietoris-Rips complex on a finite point set …
2) 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.
3) Figure 7 (main text) is hard to read and poorly labelled.
4) In SM Fig. 1, please indicate in the caption that PCA is outside the bounds of the axis limits.
5) 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?
6) 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?
Clarity:
The 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 ‘?’.
Significance:
The 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.

I am satisfied by the author responses and will maintain the high score. 
limitations_and_societal_impact: Limitations are discussed in the manuscript. No negative societal impact expected from this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a measure of generalization based on persistence homology, a standard technique of topological data analysis.

The proposed measure, the persistence homology dimension (PHD), is computed on optimization trajectories during training.

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

From these main result of the paper, Proposition 1, then follows under assumption (H1) . 
The authors then proceed to remove the Feller requirement in Proposition. 2 using a recent result in the mathematics literature [Sch20].

Based on these results, an algorithm for computing PHD is proposed.

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

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

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

Ablation studies are additionally carried out.
main_review: This work addresses an important problem, predicting generalization, and approach it from an interesting perspective, that of TDA. 

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

Even so, as some have pointed out in the literature, correlative measures may be problematic and not indicative of a causal relationship [0,1].

For instance in [0], the authors write:
*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.*

Can the authors justify their choice of empirical methodology, over the Kendall's rank correlation and conditional mutual information as suggested by [1]?

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

Minor notes: Typo on line 256 "netowork"

[0] Fantastic  Generalization  Measures and  Where  to  Find  Them - Jiang et al. (2019)
https://arxiv.org/abs/1912.02178 

[1] NeurIPS 2020 Competition:Predicting Generalization in Deep Learning - Jiang et al. (2020)
https://arxiv.org/abs/2012.07976v1
limitations_and_societal_impact: A brief but adequate discussion of societal impacts is given in Section 6.

A brief discussion of limitations is given in Section 6, which could be expanded.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.
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_title: null

final_score: rating: 2: Strong rejection
review_content: 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. 

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.  

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

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

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

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_title: null

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)