On the Role of Data in PAC-Bayes Bounds

Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, Daniel Roy
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:604-612, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-karolina-dziugaite21a, title = {On the Role of Data in {PAC-Bayes} Bounds}, author = {Dziugaite, Gintare Karolina and Hsu, Kyle and Gharbieh, Waseem and Arpino, Gabriel and Roy, Daniel}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {604--612}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/karolina-dziugaite21a/karolina-dziugaite21a.pdf}, url = {https://proceedings.mlr.press/v130/karolina-dziugaite21a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T On the Role of Data in PAC-Bayes Bounds %A Gintare Karolina Dziugaite %A Kyle Hsu %A Waseem Gharbieh %A Gabriel Arpino %A Daniel Roy %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-karolina-dziugaite21a %I PMLR %P 604--612 %U https://proceedings.mlr.press/v130/karolina-dziugaite21a.html %V 130 %X 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.
APA
Dziugaite, G.K., Hsu, K., Gharbieh, W., Arpino, G. & Roy, D.. (2021). On the Role of Data in PAC-Bayes Bounds. Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:604-612 Available from https://proceedings.mlr.press/v130/karolina-dziugaite21a.html.

Related Material