PAC-Bayes bounds for stable algorithms with instance-dependent priors

Rivasplata, Omar, Parrado-Hernandez, Emilio, Shawe-Taylor, John S., Sun, Shiliang, Szepesvari, Csaba

Neural Information Processing Systems 

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.