Generalization Error Bounds for Noisy, Iterative Algorithms
Authors:
- 1 June 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 546-550
Abstract
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.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Information-theoretic analysis of stability and bias of learning algorithms2016
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithmMathematical Programming, 2015
- Understanding Machine Learning2014
- Concentration Inequalities2013
- Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimizationAdvances in Computational Mathematics, 2006