PAC-Bayes learning bounds for sample-dependent priors

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-Rényi divergence and the l₁ distance. We show how to use these general bounds to derive learning bounds in the setting where the sample-dependent priors obey an infinite-Rényi divergence or l₁-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-Rényi divergence sensitivity condition.