Time-Independent Information-Theoretic Generalization Bounds for SGLD
Futoshi Futami Masahiro Fujisawa
We provide novel information-theoretic generalization bounds for stochastic
gradient Langevin dynamics (SGLD) under the assumptions of smoothness and
dissipativity, which are widely used in sampling and non-convex optimization
studies. Our bounds are time-independent and decay to zero as the sample size
increases, regardless of the number of iterations and whether the step size is
fixed. Unlike previous studies, we derive the generalization error bounds by
focusing on the time evolution of the Kullback--Leibler divergence, which is
related to the stability of datasets and is the upper bound of the mutual
information between output parameters and an input dataset. Additionally, we
establish the first information-theoretic generalization bound when the
training and test loss are the same by showing that a loss function of SGLD is
sub-exponential. This bound is also time-independent and removes the
problematic step size dependence in existing work, leading to an improved
excess risk bound by combining our analysis with the existing non-convex
optimization error bounds.