Efron-Stein PAC-Bayesian Inequalities
This provides theoretical tools for statisticians and machine learning researchers working with unbounded or complex data distributions, though it appears incremental as it extends existing Efron-Stein and PAC-Bayesian frameworks.
The paper tackles the problem of deriving concentration inequalities for random variables that are functions of independent variables, using the Efron-Stein variance estimate without moment assumptions, resulting in semi-empirical Bernstein-type bounds for unbounded cases and applications like PAC-Bayesian generalization bounds for unbounded losses.
We prove semi-empirical concentration inequalities for random variables which are given as possibly nonlinear functions of independent random variables. These inequalities describe concentration of random variable in terms of the data/distribution-dependent Efron-Stein (ES) estimate of its variance and they do not require any additional assumptions on the moments. In particular, this allows us to state semi-empirical Bernstein type inequalities for general functions of unbounded random variables, which gives user-friendly concentration bounds for cases where related methods (e.g. bounded differences) might be more challenging to apply. We extend these results to Efron-Stein PAC-Bayesian inequalities which hold for arbitrary probability kernels that define a random, data-dependent choice of the function of interest. Finally, we demonstrate a number of applications, including PAC-Bayesian generalization bounds for unbounded loss functions, empirical Bernstein type generalization bounds, new truncation-free bounds for off-policy evaluation with Weighted Importance Sampling (WIS), and off-policy PAC-Bayesian learning with WIS.