Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processes

We analyze the generalization gap (gap between the training and test errors) when training a potentially over-parametrized model using a Markovian stochastic training algorithm, initialized from some distribution θ0 ~ p0. We focus on Langevin dynamics with a positive temperature β-1, i.e. gradient descent on a training loss L with infinitesimal step size, perturbed with β-1-variances Gaussian noise, and lightly regularized or bounded. There, we bound the generalization gap, at any time during training, by √(βmathbbE L (θ0) + log(1/δ))/N with probability 1-δ over the dataset, where N is the sample size, and mathbbE L (θ0) =O(1) with standard initialization scaling. In contrast to previous guarantees, we have no dependence on either training time or reliance on mixing, nor a dependence on dimensionality, gradient norms, or any other properties of the loss or model. This guarantee follows from a general analysis of any Markov process-based training that has a Gibbs-style stationary distribution. The proof is surprisingly simple, once we observe that the marginal distribution divergence from initialization remains bounded, as implied by a generalized second law of thermodynamics.