On the Limitations of Fractal Dimension as a Measure of Generalization

• URL: http://arxiv.org/abs/2406.02234v2
• Date: Fri, 01 Nov 2024 16:22:33 GMT
• Title: On the Limitations of Fractal Dimension as a Measure of Generalization
• Authors: Charlie B. Tan, Inés García-Redondo, Qiquan Wang, Michael M. Bronstein, Anthea Monod,
• Abstract summary: Bounding and predicting the generalization gap of neural networks remains a central open problem in theoretical machine learning. There is a recent and growing body of literature that proposes the framework of fractals to model optimization trajectories of neural networks, motivating generalization bounds and measures based on the fractal dimension of the trajectory. This paper performs an empirical evaluation of these persistent homology-based generalization measures, with an in-depth statistical analysis.
• Score: 17.38382314570976
• License:
• Abstract: Bounding and predicting the generalization gap of overparameterized neural networks remains a central open problem in theoretical machine learning. There is a recent and growing body of literature that proposes the framework of fractals to model optimization trajectories of neural networks, motivating generalization bounds and measures based on the fractal dimension of the trajectory. Notably, the persistent homology dimension has been proposed to correlate with the generalization gap. This paper performs an empirical evaluation of these persistent homology-based generalization measures, with an in-depth statistical analysis. Our study reveals confounding effects in the observed correlation between generalization and topological measures due to the variation of hyperparameters. We also observe that fractal dimension fails to predict generalization of models trained from poor initializations. We lastly reveal the intriguing manifestation of model-wise double descent in these topological generalization measures. Our work forms a basis for a deeper investigation of the causal relationships between fractal geometry, topological data analysis, and neural network optimization.

Related papers

• Relative Representations: Topological and Geometric Perspectives [53.88896255693922]
  Relative representations are an established approach to zero-shot model stitching. We introduce a normalization procedure in the relative transformation, resulting in invariance to non-isotropic rescalings and permutations. Second, we propose to deploy topological densification when fine-tuning relative representations, a topological regularization loss encouraging clustering within classes.
  arXiv  Detail & Related papers  (2024-09-17T08:09:22Z)
• A PAC-Bayesian Perspective on the Interpolating Information Criterion [54.548058449535155]
  We show how a PAC-Bayes bound is obtained for a general class of models, characterizing factors which influence performance in the interpolating regime. We quantify how the test error for overparameterized models achieving effectively zero training error depends on the quality of the implicit regularization imposed by e.g. the combination of model, parameter-initialization scheme.
  arXiv  Detail & Related papers  (2023-11-13T01:48:08Z)
• Generalization Bounds with Data-dependent Fractal Dimensions [5.833272638548154]
  We prove fractal geometry-based generalization bounds without requiring any Lipschitz assumption. Despite introducing a significant amount of technical complications, this new notion lets us control the generalization error.
  arXiv  Detail & Related papers  (2023-02-06T13:24:48Z)
• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
  We study the generalization behavior of shallow neural networks (SNNs) by leveraging the concept of algorithmic stability. We consider gradient descent (GD) and gradient descent (SGD) to train SNNs, for both of which we develop consistent excess bounds.
  arXiv  Detail & Related papers  (2022-09-19T18:48:00Z)
• Predicting the generalization gap in neural networks using topological data analysis [33.511371257571504]
  We study the generalization gap of neural networks using methods from topological data analysis. We compute homological persistence diagrams of weighted graphs constructed from neuron activation correlations after a training phase. We compare the usefulness of different numerical summaries from persistence diagrams and show that a combination of some of them can accurately predict and partially explain the generalization gap without the need of a test set.
  arXiv  Detail & Related papers  (2022-03-23T11:15:36Z)
• Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks [19.99615698375829]
  We show that generalization error can be equivalently bounded in terms of a notion called the 'persistent homology dimension' (PHD) We develop an efficient algorithm to estimate PHD in the scale of modern deep neural networks. Our experiments show that the proposed approach can efficiently compute a network's intrinsic dimension in a variety of settings.
  arXiv  Detail & Related papers  (2021-11-25T17:06:15Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Post-mortem on a deep learning contest: a Simpson's paradox and the complementary roles of scale metrics versus shape metrics [61.49826776409194]
  We analyze a corpus of models made publicly-available for a contest to predict the generalization accuracy of neural network (NN) models. We identify what amounts to a Simpson's paradox: where "scale" metrics perform well overall but perform poorly on sub partitions of the data. We present two novel shape metrics, one data-independent, and the other data-dependent, which can predict trends in the test accuracy of a series of NNs.
  arXiv  Detail & Related papers  (2021-06-01T19:19:49Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Generalisation error in learning with random features and the hidden manifold model [23.71637173968353]
  We study generalised linear regression and classification for a synthetically generated dataset. We consider the high-dimensional regime and using the replica method from statistical physics. We show how to obtain the so-called double descent behaviour for logistic regression with a peak at the threshold. We discuss the role played by correlations in the data generated by the hidden manifold model.
  arXiv  Detail & Related papers  (2020-02-21T14:49:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.