Efron-Stein PAC-Bayesian Inequalities
Ilja Kuzborskij DeepMind Csaba Szepesvári DeepMind
Abstract
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.
中文速览
如何在不对随机变量做任何有界性假设的情况下，给出既依赖数据又足够精确的集中不等式（concentration inequality），是统计学习理论中长期悬而未决的难题。本文引入「半经验 Efron-Stein 方差代理」——它同时依赖样本和分布——作为刻画随机变量波动的核心量，并以此证明了一族无需有界性假设的指数型集中不等式，进而将其推广到 PAC-Bayesian 框架，得到对任意概率核（posterior）均成立的泛化界。基于这套工具，作者给出了无界损失函数下的 PAC-Bayesian 泛化界、经验 Bernstein 型泛化界，以及带加权重要性采样（Weighted Importance Sampling）的离策略评估与学习的无截断界，在多个场景中均比现有方法更易应用且更为精确。这项工作的意义在于，它为实际中普遍存在的无界随机变量提供了真正可用的理论保障，填补了经典有界差分方法在重尾或无界情形下的空白。
原文 arXiv:1909.01931;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1909.01931v2