A Strongly Quasiconvex PAC-Bayesian Bound

Niklas Thiemann, Christian Igel, Olivier Wintenberger, Yevgeny Seldin
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:466-492, 2017.

Abstract

We propose a new PAC-Bayesian bound and a way of constructing a hypothesis space, so that the bound is convex in the posterior distribution and also convex in a trade-off parameter between empirical performance of the posterior distribution and its complexity. The complexity is measured by the Kullback-Leibler divergence to a prior. We derive an alternating procedure for minimizing the bound. We show that the bound can be rewritten as a one-dimensional function of the trade-off parameter and provide sufficient conditions under which the function has a single global minimum. When the conditions are satisfied the alternating minimization is guaranteed to converge to the global minimum of the bound. We provide experimental results demonstrating that rigorous minimization of the bound is competitive with cross-validation in tuning the trade-off between complexity and empirical performance. In all our experiments the trade-off turned to be quasiconvex even when the sufficient conditions were violated.

Cite this Paper

BibTeX
@InProceedings{pmlr-v76-thiemann17a, title = {A Strongly Quasiconvex PAC-Bayesian Bound}, author = {Thiemann, Niklas and Igel, Christian and Wintenberger, Olivier and Seldin, Yevgeny}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {466--492}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/thiemann17a/thiemann17a.pdf}, url = {https://proceedings.mlr.press/v76/thiemann17a.html}, abstract = {We propose a new PAC-Bayesian bound and a way of constructing a hypothesis space, so that the bound is convex in the posterior distribution and also convex in a trade-off parameter between empirical performance of the posterior distribution and its complexity. The complexity is measured by the Kullback-Leibler divergence to a prior. We derive an alternating procedure for minimizing the bound. We show that the bound can be rewritten as a one-dimensional function of the trade-off parameter and provide sufficient conditions under which the function has a single global minimum. When the conditions are satisfied the alternating minimization is guaranteed to converge to the global minimum of the bound. We provide experimental results demonstrating that rigorous minimization of the bound is competitive with cross-validation in tuning the trade-off between complexity and empirical performance. In all our experiments the trade-off turned to be quasiconvex even when the sufficient conditions were violated.} }
Endnote
%0 Conference Paper %T A Strongly Quasiconvex PAC-Bayesian Bound %A Niklas Thiemann %A Christian Igel %A Olivier Wintenberger %A Yevgeny Seldin %B Proceedings of the 28th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Steve Hanneke %E Lev Reyzin %F pmlr-v76-thiemann17a %I PMLR %P 466--492 %U https://proceedings.mlr.press/v76/thiemann17a.html %V 76 %X We propose a new PAC-Bayesian bound and a way of constructing a hypothesis space, so that the bound is convex in the posterior distribution and also convex in a trade-off parameter between empirical performance of the posterior distribution and its complexity. The complexity is measured by the Kullback-Leibler divergence to a prior. We derive an alternating procedure for minimizing the bound. We show that the bound can be rewritten as a one-dimensional function of the trade-off parameter and provide sufficient conditions under which the function has a single global minimum. When the conditions are satisfied the alternating minimization is guaranteed to converge to the global minimum of the bound. We provide experimental results demonstrating that rigorous minimization of the bound is competitive with cross-validation in tuning the trade-off between complexity and empirical performance. In all our experiments the trade-off turned to be quasiconvex even when the sufficient conditions were violated.
APA
Thiemann, N., Igel, C., Wintenberger, O. & Seldin, Y.. (2017). A Strongly Quasiconvex PAC-Bayesian Bound. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 76:466-492 Available from https://proceedings.mlr.press/v76/thiemann17a.html.

Related Material