Generalization Error Bounds for Noisy, Iterative Algorithms

By Ankit Pensia, Varun Jog, Po-Ling Loh. 2018

130 citations recorded by the source corpus.

In statistical learning theory, generalization error is used to quantify the degree to which a supervised machine learning algorithm may overfit to training data. Recent work [Xu and Raginsky (2017)] has established a bound on the generalization error of empirical risk minimization based on the mutual information $I$($S$; W) between the algorithm input $S$ and the algorithm output W, when the loss function is sub-Gaussian. We leverage these results to derive generalization error bounds for a broad class of iterative algorithms that are characterized by bounded, noisy updates with Markovian structure. Our bounds are very general and are applicable to numerous settings of interest, including stochastic gradient Langevin dynamics (SGLD) and variants of the stochastic gradient Hamiltonian Monte Carlo (SGHMC) algorithm. Furthermore, our error bounds hold for any output function computed over the path of iterates, including the last iterate of the algorithm or the average of subsets of iterates, and also allow for non-uniform sampling of data in successive updates of the algorithm.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Where is the Information in a Deep Neural Network? (2019, methodology): “(Russo & Zou, 2019; Xu & Raginsky, 2017; Pensia et al., 2018; Negrea et al., 2019; Asadi et al., 2018) bound the generalization gap of a training algorithm using the Shannon Information in the weights and a notion of “information stability”.”
Improving Generalization by Controlling Label-Noise Information in Neural Network Weights (2020, background): “Pensia et al. (2018) upper bound I(w;S) when the training algorithm consists of iterative noisy updates.”
Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates (2019, methodology): “In recent work, Pensia, Jog, and Loh [23] perform a stepwise analysis of a family of noisy iterative algorithms that includes SGLD and the Langevin algorithm.”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, background): “A line of research tries to explain this phenomenon by studying the implicit regularization from stochastic gradient descent algorithm (Hardt et al., 2015; Pensia et al., 2018; Mou et al., 2017; Brutzkus et al., 2017; Li et al., 2017).”
Chaining Mutual Information and Tightening Generalization Bounds (2018, background): “We also discuss how our new bound gives a possible direction to explain the phenomenon described in [19] (see Remark 3), and to exploit regularization properties of some algorithms (see Section 4).”
An Information-Theoretic View for Deep Learning (2018, methodology): “Our analysis here is based on the work of [13] and [11].”