Skip to yearly menu bar Skip to main content


Contributed Talk
in
Workshop: PAC-Bayes Meets Interactive Learning

Improved Time-Uniform PAC-Bayes Bounds using Coin Betting

Kyoungseok Jang · Kwang-Sung Jun · Ilja Kuzborskij · Francesco Orabona


Abstract:

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.

Chat is not available.