PAC-Bayes Learning Bounds for Sample-Dependent Priors
Pranjal Awasthi, Satyen Kale, Stefani Karp, Mehryar Mohri
Abstract
We present a series of new PAC-Bayes learning guarantees for randomized algorithms with sample-dependent priors. Our most general bounds make no assumption on the priors and are given in terms of certain covering numbers under the infinite-Renyi divergence and the L1 distance. We show how to use these general bounds to derive leaning bounds in the setting where the sample-dependent priors obey an infinite-Renyi divergence or L1-distance sensitivity condition. We also provide a flexible framework for computing PAC-Bayes bounds, under certain stability assumptions on the sample-dependent priors, and show how to use this framework to give more refined bounds when the priors satisfy an infinite-Renyi divergence sensitivity condition.
BibTeX
@inproceedings{NEURIPS2020_2e85d722,
author = {Awasthi, Pranjal and Kale, Satyen and Karp, Stefani and Mohri, Mehryar},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {4403--4414},
publisher = {Curran Associates, Inc.},
title = {PAC-Bayes Learning Bounds for Sample-Dependent Priors},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/2e85d72295b67c5b649290dfbf019285-Paper.pdf},
volume = {33},
year = {2020}
}