On the role of data in PAC-Bayes bounds
This work addresses a theoretical limitation in PAC-Bayes bounds for researchers in statistical learning theory, offering an incremental improvement by optimizing prior selection.
The paper tackles the suboptimality of PAC-Bayes bounds based on oracle priors by showing that data-dependent oracle priors can yield stronger bounds, sometimes making the difference between vacuous and nonvacuous bounds, as demonstrated with nonvacuous bounds on MNIST and Fashion MNIST datasets.
The dominant term in PAC-Bayes bounds is often the Kullback--Leibler divergence between the posterior and prior. For so-called linear PAC-Bayes risk bounds based on the empirical risk of a fixed posterior kernel, it is possible to minimize the expected value of the bound by choosing the prior to be the expected posterior, which we call the oracle prior on the account that it is distribution dependent. In this work, we show that the bound based on the oracle prior can be suboptimal: In some cases, a stronger bound is obtained by using a data-dependent oracle prior, i.e., a conditional expectation of the posterior, given a subset of the training data that is then excluded from the empirical risk term. While using data to learn a prior is a known heuristic, its essential role in optimal bounds is new. In fact, we show that using data can mean the difference between vacuous and nonvacuous bounds. We apply this new principle in the setting of nonconvex learning, simulating data-dependent oracle priors on MNIST and Fashion MNIST with and without held-out data, and demonstrating new nonvacuous bounds in both cases.