# Generalization Bounds with Data-dependent Fractal Dimensions

arXiv: https://arxiv.org/abs/2302.02766 · HTML: https://mlsanity.com/paper/2302.02766/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 67 references that are in the map.
- First posted on arXiv 6 Feb 2023.

## Builds on (most cited first, 30 of 34)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017)
- [Reasoning About Generalization via Conditional Mutual Information](https://mlsanity.com/paper/2001.09122/) (2020)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Ripser: efficient computation of Vietoris-Rips persistence barcodes](https://mlsanity.com/paper/1908.02518/) (2019)
- [Deep Learning with Topological Signatures](https://mlsanity.com/paper/1707.04041/) (2017)
- [Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks](https://mlsanity.com/paper/1710.11029/) (2017)
- [How much does your data exploration overfit? Controlling bias via information usage](https://mlsanity.com/paper/1511.05219/) (2015)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [Neural Persistence: A Complexity Measure for Deep Neural Networks Using Algebraic Topology](https://mlsanity.com/paper/1812.09764/) (2018)
- [Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks](https://mlsanity.com/paper/2111.13171/) (2021)
- [Chaining Mutual Information and Tightening Generalization Bounds](https://mlsanity.com/paper/1806.03803/) (2018)
- [Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks](https://mlsanity.com/paper/2006.09313/) (2020)
- [A Variational Analysis of Stochastic Gradient Algorithms](https://mlsanity.com/paper/1602.02666/) (2016)
- [Computing the Testing Error without a Testing Set](https://mlsanity.com/paper/2005.00450/) (2020)
- [Information-theoretic generalization bounds for black-box learning algorithms](https://mlsanity.com/paper/2110.01584/) (2021)
- [Connectivity-Optimized Representation Learning via Persistent Homology](https://mlsanity.com/paper/1906.09003/) (2019)
- [Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks](https://mlsanity.com/paper/2106.03795/) (2021)
- [Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network](https://mlsanity.com/paper/1909.11274/) (2019)
- [Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers](https://mlsanity.com/paper/2108.00781/) (2021)
- [Hypothesis Set Stability and Generalization](https://mlsanity.com/paper/1904.04755/) (2019)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [Persistent Homology and the Upper Box Dimension](https://mlsanity.com/paper/1802.00533/) (2018)
- [giotto-ph: A Python Library for High-Performance Computation of Persistent Homology of Vietoris-Rips Filtrations](https://mlsanity.com/paper/2107.05412/) (2021)

## Built on by (most cited first, 15 of 15)

- [Knowledge Overshadowing Causes Amalgamated Hallucination in Large Language Models](https://mlsanity.com/paper/2407.08039/) (2024)
- [From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression](https://mlsanity.com/paper/2310.01687/) (2023)
- [On the Limitations of Fractal Dimension as a Measure of Generalization](https://mlsanity.com/paper/2406.02234/) (2024)
- [Approximating Metric Magnitude of Point Sets](https://mlsanity.com/paper/2409.04411/) (2024)
- [Tighter Generalisation Bounds via Interpolation](https://mlsanity.com/paper/2402.05101/) (2024)
- [T-REGS: Minimum Spanning Tree Regularization for Self-Supervised Learning](https://mlsanity.com/paper/2510.23484/) (2025)
- [Generalization at the Edge of Stability](https://mlsanity.com/paper/2604.19740/) (2026)
- [IdEst: Assessing Self-Supervised Learning Representations via Intrinsic Dimension](https://mlsanity.com/paper/2606.03338/) (2026)
- [Generalization of Graph Neural Networks through the Lens of Homomorphism](https://mlsanity.com/paper/2403.06079/) (2024)
- [A practical generalization metric for deep networks benchmarking](https://mlsanity.com/paper/2409.01498/) (2024)
- [A Quotient Homology Theory of Representation in Neural Networks](https://mlsanity.com/paper/2502.01360/) (2025)
- [Stability, Complexity and Data-Dependent Worst-Case Generalization Bounds](https://mlsanity.com/paper/2507.06775/) (2025)
- [Concentration bounds for intrinsic dimension estimation using Gaussian kernels](https://mlsanity.com/paper/2512.04861/) (2025)
- [A Survey on Data-Dependent Worst-Case Generalization Bounds](https://mlsanity.com/paper/2605.13913/) (2026)
- [Fourier fractal dimension to predict the generalization of deep neural networks](https://mlsanity.com/paper/2606.08308/) (2026)

## Abstract (arXiv)

Providing generalization guarantees for modern neural networks has been a crucial task in statistical learning. Recently, several studies have attempted to analyze the generalization error in such settings by using tools from fractal geometry. While these works have successfully introduced new mathematical tools to apprehend generalization, they heavily rely on a Lipschitz continuity assumption, which in general does not hold for neural networks and might make the bounds vacuous. In this work, we address this issue and prove fractal geometry-based generalization bounds without requiring any Lipschitz assumption. To achieve this goal, we build up on a classical covering argument in learning theory and introduce a data-dependent fractal dimension. Despite introducing a significant amount of technical complications, this new notion lets us control the generalization error (over either fixed or random hypothesis spaces) along with certain mutual information (MI) terms. To provide a clearer interpretation to the newly introduced MI terms, as a next step, we introduce a notion of "geometric stability" and link our bounds to the prior art. Finally, we make a rigorous connection between the proposed data-dependent dimension and topological data analysis tools, which then enables us to compute the dimension in a numerically efficient way. We support our theory with experiments conducted on various settings.