More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity
This work provides incremental improvements in theoretical machine learning by offering more flexible and tighter generalization bounds for researchers and practitioners.
The paper tackles the problem of deriving high-probability PAC-Bayes bounds for various loss types, resulting in new bounds for bounded losses that are tighter and interpretable, parameter-free bounds for losses with general tail behaviors using a novel discretization technique, and extensions to anytime-valid bounds.
In this paper, we present new high-probability PAC-Bayes bounds for different types of losses. Firstly, for losses with a bounded range, we recover a strengthened version of Catoni's bound that holds uniformly for all parameter values. This leads to new fast-rate and mixed-rate bounds that are interpretable and tighter than previous bounds in the literature. In particular, the fast-rate bound is equivalent to the Seeger--Langford bound. Secondly, for losses with more general tail behaviors, we introduce two new parameter-free bounds: a PAC-Bayes Chernoff analogue when the loss' cumulative generating function is bounded, and a bound when the loss' second moment is bounded. These two bounds are obtained using a new technique based on a discretization of the space of possible events for the ``in probability'' parameter optimization problem. This technique is both simpler and more general than previous approaches optimizing over a grid on the parameters' space. Finally, using a simple technique that is applicable to any existing bound, we extend all previous results to anytime-valid bounds.