# Generalization Bounds for Gradient Methods via Discrete and Continuous Prior

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 75 references that are in the map.
- First posted on arXiv 27 May 2022.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Entropy-SGD: Biasing Gradient Descent Into Wide Valleys](https://mlsanity.com/paper/1611.01838/) (2016)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Stochastic modified equations and adaptive stochastic gradient algorithms](https://mlsanity.com/paper/1511.06251/) (2015)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates](https://mlsanity.com/paper/1911.02151/) (2019)
- [Tightening Mutual Information Based Bounds on Generalization Error](https://mlsanity.com/paper/1901.04609/) (2019)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms](https://mlsanity.com/paper/2004.12983/) (2020)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [Generalization Error Bounds for Noisy, Iterative Algorithms](https://mlsanity.com/paper/1801.04295/) (2018)
- [On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs)](https://mlsanity.com/paper/2102.12470/) (2021)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [On the role of data in PAC-Bayes bounds](https://mlsanity.com/paper/2006.10929/) (2020)
- [Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks](https://mlsanity.com/paper/2006.09313/) (2020)
- [On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning](https://mlsanity.com/paper/1902.00621/) (2019)

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

- [Learning Trajectories are Generalization Indicators](https://mlsanity.com/paper/2304.12579/) (2023)
- [Parameter-Efficient Fine-Tuning for Continual Learning: A Neural Tangent Kernel Perspective](https://mlsanity.com/paper/2407.17120/) (2024)
- [Towards Auto-Regressive Next-Token Prediction: In-Context Learning Emerges from Generalization](https://mlsanity.com/paper/2502.17024/) (2025)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Gradient-Discrepancy Acquisition for Pool-Based Active Learning](https://mlsanity.com/paper/2605.02609/) (2026)

## Abstract (arXiv)

Proving algorithm-dependent generalization error bounds for gradient-type optimization methods has attracted significant attention recently in learning theory. However, most existing trajectory-based analyses require either restrictive assumptions on the learning rate (e.g., fast decreasing learning rate), or continuous injected noise (such as the Gaussian noise in Langevin dynamics). In this paper, we introduce a new discrete data-dependent prior to the PAC-Bayesian framework, and prove a high probability generalization bound of order O(frac1n· sumt=1T(γt/varepsilont)2left|gtright|2) for Floored GD (i.e. a version of gradient descent with precision level varepsilont), where n is the number of training samples, γt is the learning rate at step t, gt is roughly the difference of the gradient computed using all samples and that using only prior samples. left|gtright| is upper bounded by and and typical much smaller than the gradient norm left|nabla f(Wt)right|. We remark that our bound holds for nonconvex and nonsmooth scenarios. Moreover, our theoretical results provide numerically favorable upper bounds of testing errors (e.g., 0.037 on MNIST). Using a similar technique, we can also obtain new generalization bounds for certain variants of SGD. Furthermore, we study the generalization bounds for gradient Langevin Dynamics (GLD). Using the same framework with a carefully constructed continuous prior, we show a new high probability generalization bound of order O(frac1n + fracL2n2sumt=1T(γt/σt)2) for GLD. The new 1/n2 rate is due to the concentration of the difference between the gradient of training samples and that of the prior.