# From Mutual Information to Expected Dynamics: New Generalization Bounds for Heavy-Tailed SGD

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 39 references that are in the map.
- First posted on arXiv 1 Dec 2023.

## Builds on (most cited first, 14 of 14)

- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks](https://mlsanity.com/paper/2111.13171/) (2021)
- [Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks](https://mlsanity.com/paper/2006.09313/) (2020)
- [Generalization Bounds: Perspectives from Information Theory and PAC-Bayes](https://mlsanity.com/paper/2309.04381/) (2023)
- [First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise](https://mlsanity.com/paper/1906.09069/) (2019)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [Generalization Bounds using Lower Tail Exponents in Stochastic Optimizers](https://mlsanity.com/paper/2108.00781/) (2021)
- [Generalization Bounds via Convex Analysis](https://mlsanity.com/paper/2202.04985/) (2022)
- [Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms](https://mlsanity.com/paper/2106.04881/) (2021)
- [A General Framework for the Practical Disintegration of PAC-Bayesian Bounds](https://mlsanity.com/paper/2102.08649/) (2021)
- [Algorithmic Stability of Heavy-Tailed SGD with General Loss Functions](https://mlsanity.com/paper/2301.11885/) (2023)

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

- [Uniform Generalization Bounds on Data-Dependent Hypothesis Sets via PAC-Bayesian Theory on Random Sets](https://mlsanity.com/paper/2404.17442/) (2024)
- [Algorithm- and Data-Dependent Generalization Bounds for Diffusion Models](https://mlsanity.com/paper/2506.03849/) (2025)
- [Tighter Generalisation Bounds via Interpolation](https://mlsanity.com/paper/2402.05101/) (2024)
- [Stability, Complexity and Data-Dependent Worst-Case Generalization Bounds](https://mlsanity.com/paper/2507.06775/) (2025)

## Abstract (arXiv)

Understanding the generalization abilities of modern machine learning algorithms has been a major research topic over the past decades. In recent years, the learning dynamics of Stochastic Gradient Descent (SGD) have been related to heavy-tailed dynamics. This has been successfully applied to generalization theory by exploiting the fractal properties of those dynamics. However, the derived bounds depend on mutual information (decoupling) terms that are beyond the reach of computability. In this work, we prove generalization bounds over the trajectory of a class of heavy-tailed dynamics, without those mutual information terms. Instead, we introduce a geometric decoupling term by comparing the learning dynamics (depending on the empirical risk) with an expected one (depending on the population risk). We further upper-bound this geometric term, by using techniques from the heavy-tailed and the fractal literature, making it fully computable. Moreover, as an attempt to tighten the bounds, we propose a PAC-Bayesian setting based on perturbed dynamics, in which the same geometric term plays a crucial role and can still be bounded using the techniques described above.