Improved Time-Uniform PAC-Bayes Bounds using Coin Betting

We propose a novel PAC-Bayes concentration inequality that implies a number of existing results including Bernoulli-KL (Maurer's) and empirical Bernstein inequalities.Our approach is based on the coin-betting framework that derives one of numerically tightest known time-uniform concentration inequalities through the regret analysis of online gambling algorithms.In particular, we derive the first PAC-Bayes concentration inequality based on the coin-betting approach that holds simultaneously for all sample sizes. Finally, we propose an efficient algorithm to numerically calculate confidence sequences from our bound, which often generates nonvacuous confidence sequences even with few samples, unlike the state-of-the-art PAC-Bayes bounds.