Efron-Stein PAC-Bayesian Inequalities

Ilja Kuzborskij, Csaba SzepesváriarXiv 2019 · OpenReview

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.

Introduction

In statistical learning theory, concentration inequalities are the primary tools used to guarantee that a model's performance on training data generalizes to unseen data. Traditional tools, such as Hoeffding’s or McDiarmid’s inequalities, typically require functions or data to be strictly bounded within a known range. While Bernstein-type inequalities offer tighter bounds by incorporating variance, they often still require control over higher-order moments, which implicitly necessitates boundedness.

In practice, many real-world machine learning scenarios involve unbounded variables, such as heavy-tailed loss functions or the extreme importance weights found in Reinforcement Learning (RL). To apply standard concentration results to these problems, practitioners often resort to artificial truncation or clipping, which introduces bias and requires sensitive hyperparameter tuning. This paper introduces a new class of "semi-empirical" concentration inequalities and PAC-Bayesian bounds that eliminate the need for boundedness by leveraging a data-dependent Efron-Stein variance proxy.

Methodology

The authors derive their results through three primary mathematical innovations:

1. Semi-Empirical Efron-Stein (ES) Variance Proxy

Rather than relying on worst-case theoretical constants, the authors define a variance proxy based on how sensitive a function is to coordinate-wise perturbations—specifically, swapping out one data point at a time. This "semi-empirical" proxy depends on both the underlying distribution and the specific observed sample, allowing the bound to adapt to the actual complexity of the data.

2. The Method of Mixtures

To prove these bounds, the authors must tune a sensitivity parameter ($\lambda$) within their exponential inequalities. While standard approaches often use union bounds, this work introduces the method of mixtures to PAC-Bayesian analysis. By integrating the parameter over a Gaussian distribution, the authors provide a mathematically elegant way to tune the bounds analytically, avoiding the slackness often introduced by discrete union bounds.

3. PAC-Bayesian Extension

Using the Donsker-Varadhan change-of-measure lemma, the authors extend their results from fixed functions to data-dependent function classes. This allows the framework to be applied to models where the function itself is chosen based on the training data, such as neural networks or complex predictors.

Key Theoretical Results

The paper establishes several foundational results for concentration without boundedness:

  • General Concentration (Theorems 1 & 3): The authors derive semi-empirical concentration inequalities for fixed functions and their PAC-Bayesian equivalents for data-dependent functions. Crucially, these hold without any boundedness assumptions on the random variables.
  • Fast Rates for Unbounded Losses: The framework provides generalization bounds for unbounded loss functions. When the variance proxy (the sum of squared losses) is small, the bound achieves a "fast rate," scaling with $1/n$ rather than the standard $1/\sqrt{n}$.
  • Truncation-Free RL Bounds: The authors establish high-confidence lower bounds for off-policy evaluation and learning using Weighted Importance Sampling (WIS). These bounds link the estimate's confidence directly to the Effective Sample Size (ESS) without requiring artificial clipping of importance weights.

Applications: Solving the WIS Truncation Problem

A significant practical application of this work is in off-policy Reinforcement Learning. Weighted Importance Sampling (WIS) is frequently used to estimate the value of a target policy using data from a behavior policy. Because WIS relies on probability ratios, weights can explode toward infinity. Previous theoretical frameworks required truncating these weights to maintain mathematical tractability. This paper’s inequalities handle unbounded variables naturally, providing a sound way to bound WIS performance without the bias introduced by truncation.

Limitations and Future Directions

While the framework is robust, it possesses some technical nuances. The semi-empirical variance proxy is asymmetric, meaning its value can depend on the specific ordering of data points in a sequence (though this effect is weak for normalized sums). Additionally, the bounds introduce a free parameter $y$ that must be selected by the user; while a problem-agnostic choice like $y = 1/n^2$ is effective, it incurs a small logarithmic penalty.

Future research may explore applying these semi-empirical results to analyze the excess risk of Gibbs predictors, further extending the utility of Efron-Stein PAC-Bayesian inequalities within statistical learning theory.

Summary updated

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.
BibTeX
@misc{kuzborskij2019efron,
  author = {Ilja Kuzborskij and Csaba Szepesvári},
  title = {{Efron-Stein PAC-Bayesian Inequalities}},
  year = {2019},
  eprint = {1909.01931},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.01931},
}
Figure