PAC-Bayes-Empirical-Bernstein Inequality
We present a PAC-Bayes-Empirical-Bernstein inequality. The inequality is based on a combination of the PAC-Bayesian bounding technique with an Empirical Bernstein bound. We show that when the empirical variance is significantly smaller than the empirical loss the PAC-Bayes-Empirical-Bernstein inequality is significantly tighter than the PAC-Bayes-kl inequality of Seeger (2002) and otherwise it is comparable. Our theoretical analysis is confirmed empirically on a synthetic example and several UCI datasets. The PAC-Bayes-Empirical-Bernstein inequality is an interesting example of an application of the PAC-Bayesian bounding technique to self-bounding functions.
This paper derives a new empircal PAC Bayesian bound 
      by combining an existing (non-empircal) PAC Bayesian Berstein bound (i.e., 
      involving the true variance of the loss values) with a PAC Bayesian 
      analysis of the concentration of the empirical variance around its true 
      value. This new bound has the advantage of being tighter when the 
      empirical variance is small compared to the empirical loss. Experiments on 
      real and empirical data with simple models compare the new bound with the 
      usual empirical PAC Bayesian bound confirming the advantage. While 
      this is a well written paper that make a novel contribution to the PAC 
      Bayesian literature it is a incremental and only marginally significant 
      one. As the authors' claim, the newer bound is only really useful for 
      analysing cases when there is a large mismatch between the model class and 
      the data generating distribution. Although the idea of applying a 
      PAC Bayesian bound to the difference between empirical and true variances 
      is original and addresses a shortcoming in the existing work, it appears 
      that the steps from there were fairly routine, leaning heavily on 
      techniques developed in other recent papers. That said, the definitions 
      and proofs all seem to be correct and are logically organised. 
      Minor suggestions: 1. Put an article ("a" or "the") before 
      all singular uses of "PAC-Bayes-Empirical-Berstein inequality" and the 
      like. For example, the opening sentence of the abstract should be "We 
      present a PAC-Bayes-Empirical-Bernstein inequality..." 2. You 
      should define $KL(\rho\|\pi)$ or otherwise make clear in which direction 
      the relative entropy is defined.