Online-to-PAC Conversions: Generalization Bounds via Regret Analysis
This work provides a novel theoretical tool for analyzing generalization in machine learning, potentially benefiting researchers in statistical learning theory by offering a unified approach to derive bounds, though it appears incremental as it builds on existing concepts.
The paper tackles the problem of deriving generalization bounds for statistical learning algorithms by introducing a new framework that connects online learning regret to generalization error, enabling the recovery of various standard bounds including PAC-Bayesian and information-theoretic guarantees.
We present a new framework for deriving bounds on the generalization bound of statistical learning algorithms from the perspective of online learning. Specifically, we construct an online learning game called the "generalization game", where an online learner is trying to compete with a fixed statistical learning algorithm in predicting the sequence of generalization gaps on a training set of i.i.d. data points. We establish a connection between the online and statistical learning setting by showing that the existence of an online learning algorithm with bounded regret in this game implies a bound on the generalization error of the statistical learning algorithm, up to a martingale concentration term that is independent of the complexity of the statistical learning method. This technique allows us to recover several standard generalization bounds including a range of PAC-Bayesian and information-theoretic guarantees, as well as generalizations thereof.