PAC-Bayes bounds’ parameter optimization via events’ space discretization: new bounds for losses with general tail behaviors

In this paper, we present new parameter-free high-probability PAC-Bayes bounds for losses with different tail behaviors: 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. Finally, we extend all previous results to anytime-valid bounds using a simple technique applicable to any existing bound.