PAC-Bayes bounds for stable algorithms with instance-dependent priors
Omar Rivasplata, Emilio Parrado-Hernandez, John S Shawe-Taylor, Shiliang Sun, Csaba Szepesvari
Abstract
PAC-Bayes bounds have been proposed to get risk estimates based on a training sample. In this paper the PAC-Bayes approach is combined with stability of the hypothesis learned by a Hilbert space valued algorithm. The PAC-Bayes setting is used with a Gaussian prior centered at the expected output. Thus a novelty of our paper is using priors defined in terms of the data-generating distribution. Our main result estimates the risk of the randomized algorithm in terms of the hypothesis stability coefficients. We also provide a new bound for the SVM classifier, which is compared to other known bounds experimentally. Ours appears to be the first uniform hypothesis stability-based bound that evaluates to non-trivial values.
BibTeX
@inproceedings{NEURIPS2018_38685413,
author = {Rivasplata, Omar and Parrado-Hernandez, Emilio and Shawe-Taylor, John S and Sun, Shiliang and Szepesvari, Csaba},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {PAC-Bayes bounds for stable algorithms with instance-dependent priors},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/386854131f58a556343e056f03626e00-Paper.pdf},
volume = {31},
year = {2018}
}