# Uniform Generalization Bound on Time and Inverse Temperature for Gradient Descent Algorithm and its Application to Analysis of Simulated Annealing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 30 references that are in the map.
- First posted on arXiv 25 May 2022.

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

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints](https://mlsanity.com/paper/1707.05947/) (2017)
- [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [Global Non-convex Optimization with Discretized Diffusions](https://mlsanity.com/paper/1810.12361/) (2018)
- [Nonasymptotic estimates for Stochastic Gradient Langevin Dynamics under local conditions in nonconvex optimization](https://mlsanity.com/paper/1910.02008/) (2019)
- [Non-asymptotic bounds for sampling algorithms without log-concavity](https://mlsanity.com/paper/1808.07105/) (2018)
- [State-Dependent Temperature Control for Langevin Diffusions](https://mlsanity.com/paper/2011.07456/) (2020)
- [On stochastic gradient Langevin dynamics with dependent data streams: the fully non-convex case](https://mlsanity.com/paper/1905.13142/) (2019)
- [Generalization bound of globally optimal non-convex neural network training: Transportation map estimation by infinite dimensional Langevin dynamics](https://mlsanity.com/paper/2007.05824/) (2020)
- [Dimension-free convergence rates for gradient Langevin dynamics in RKHS](https://mlsanity.com/paper/2003.00306/) (2020)
- [On the diffusion approximation of nonconvex stochastic gradient descent](https://mlsanity.com/paper/1705.07562/) (2017)
- [Convergence rate of a simulated annealing algorithm with noisy observations](https://mlsanity.com/paper/1703.00329/) (2017)
- [Weak Convergence of Approximate reflection coupling and its Application to Non-convex Optimization](https://mlsanity.com/paper/2205.11970/) (2022)

## Abstract (arXiv)

In this paper, we propose a novel uniform generalization bound on the time and inverse temperature for stochastic gradient Langevin dynamics (SGLD) in a non-convex setting. While previous works derive their generalization bounds by uniform stability, we use Rademacher complexity to make our generalization bound independent of the time and inverse temperature. Using Rademacher complexity, we can reduce the problem to derive a generalization bound on the whole space to that on a bounded region and therefore can remove the effect of the time and inverse temperature from our generalization bound. As an application of our generalization bound, an evaluation on the effectiveness of the simulated annealing in a non-convex setting is also described. For the sample size n and time s, we derive evaluations with orders √n-1 log (n+1) and |(log)4(s)|-1, respectively. Here, (log)4 denotes the 4 times composition of the logarithmic function.