Empirical Bernstein Bounds and Sample Variance Penalization. stat

We give improved constants for data dependent and variance sensitive confidence bounds, called em-pirical Bernstein bounds, and extend these inequal-ities to hold uniformly over classes of functions whose growth function is polynomial in the sam-ple size . The bounds lead us to consider sam-ple variance penalization, a novel learning method which takes into account the empirical variance of the loss function. We give conditions under which sample variance penalization is effective. In par-ticular, we present a bound on the excess risk in-curred by the method. Using this, we argue that there are situations in which the excess risk of our method is of order , while the excess risk of empirical risk minimization is of order . We show some experimental results, which confirm the theory. Finally, we discuss the potential applica-tion of our results to sample compression schemes.