  We consider the problem of estimating the mean of a sequence of random
elements $f(X_1, \theta)$ $, \ldots, $ $f(X_n, \theta)$ where $f$ is a fixed
scalar function, $S=(X_1, \ldots, X_n)$ are independent random variables, and
$\theta$ is a possibly $S$-dependent parameter. An example of such a problem
would be to estimate the generalization error of a neural network trained on
$n$ examples where $f$ is a loss function. Classically, this problem is
approached through concentration inequalities holding uniformly over compact
parameter sets of functions $f$, for example as in Rademacher or VC type
analysis. However, in many problems, such inequalities often yield numerically
vacuous estimates. Recently, the \emph{PAC-Bayes} framework has been proposed
as a better alternative for this class of problems for its ability to often
give numerically non-vacuous bounds. In this paper, we show that we can do even
better: we show how to refine the proof strategy of the PAC-Bayes bounds and
achieve \emph{even tighter} guarantees. Our approach is based on the
\emph{coin-betting} framework that derives the numerically tightest known
time-uniform concentration inequalities from the regret guarantees 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. We demonstrate its tightness showing that by \emph{relaxing} it
we obtain a number of previous results in a closed form including Bernoulli-KL
and empirical Bernstein inequalities. Finally, we propose an efficient
algorithm to numerically calculate confidence sequences from our bound, which
often generates nonvacuous confidence bounds even with one sample, unlike the
state-of-the-art PAC-Bayes bounds.
