A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent
This work addresses generalization analysis for machine learning practitioners using SGD, offering an incremental improvement with a new adaptive sampling method.
The paper tackles the generalization error of randomized learning algorithms, particularly stochastic gradient descent (SDG), by combining PAC-Bayes and algorithmic stability to derive bounds that hold for all posterior distributions, including data-dependent ones, and proposes an adaptive sampling algorithm for SGD. The result shows that adaptive sampling reduces empirical risk faster and improves out-of-sample accuracy on a benchmark dataset.
We study the generalization error of randomized learning algorithms -- focusing on stochastic gradient descent (SGD) -- using a novel combination of PAC-Bayes and algorithmic stability. Importantly, our generalization bounds hold for all posterior distributions on an algorithm's random hyperparameters, including distributions that depend on the training data. This inspires an adaptive sampling algorithm for SGD that optimizes the posterior at runtime. We analyze this algorithm in the context of our generalization bounds and evaluate it on a benchmark dataset. Our experiments demonstrate that adaptive sampling can reduce empirical risk faster than uniform sampling while also improving out-of-sample accuracy.