Plug-in Estimators for Conditional Expectations and Probabilities

Steffen GrünewälderAISTATS 2018

TL;DR

This paper provides a rigorous theoretical foundation for "plug-in" estimators—a simple approach where you estimate conditional probabilities and expectations by simply replacing unknown distributions with empirical data. By linking these estimators to Vapnik-Chervonenkis (VC) theory, the author proves that they achieve fast, uniform convergence rates ($n^{-1/2}$) even over complex, infinite families of sets and functions, all while remaining computationally efficient to evaluate.

What Problem Does This Paper Address?

In machine learning, we are constantly "conditioning." We want to know the probability of an event $A$ given $B$, or the expected value of a reward given a specific state in a Reinforcement Learning (RL) environment.

When the number of possible conditions is small, this is easy. But in modern ML, we often condition on high-dimensional, continuous, or even infinite sets of events (e.g., the infinite state space of a robot). Providing statistical guarantees for these estimates is a major challenge in non-parametric statistics. Existing methods, like kernel-based estimators, often come with high computational costs or restrictive assumptions about the underlying function space (like requiring it to be a specific type of Hilbert space). This paper seeks a simpler, more "natural" estimator that works across broad classes of functions with provable convergence rates.

Methods

The author utilizes the plug-in principle. To estimate a conditional expectation $E[f|B]$, you simply take your $n$ samples and replace the true probability measure $P$ with the empirical measure $P_n$ (the distribution of your actual data points).

The core technical contribution is linking this simple estimator to VC-theory and Empirical Process theory.

  • VC-Classes: The author uses VC-dimension to measure the "complexity" of the sets we are conditioning on.
  • Donsker Classes: These are used to bound the errors uniformly over large families of functions.
  • Approximation of $\sigma$-algebras: Since we can't condition on every possible infinitesimal event at once, the paper describes how to approximate complex, infinite $\sigma$-algebras (like the Borel sets on a cube) using sequences of simpler, finite partitions that grow with the sample size.

Datasets

This is a theoretical statistics paper and does not use empirical datasets for training or evaluation. Instead, it uses a running mathematical example of $d$-dimensional hypercubes in $\mathbb{R}^d$ to demonstrate how the proposed rates of convergence apply to practical geometric sets used in density estimation.

Key Insights and Ideas

  • Simplicity is a Feature: Unlike kernel methods that require "up-front" costs for inference, plug-in estimators can be evaluated in linear time relative to the number of samples.
  • The "Small Probability" Hurdle: A major difficulty in conditioning is that the set $B$ we condition on might have a very small (or zero) probability, which makes the estimator explode. The author introduces a technique to control this by lower-bounding the size of sets we estimate relative to the sample size $n$.
  • Uniformity Matters: The paper doesn't just prove the estimator works for one specific set; it proves it works uniformly over entire classes of sets (like all possible hypercubes). This is crucial for ML models that need to generalize across a whole state space.
  • Bridging Elementary and Advanced Probability: The paper shows how to move from "elementary" conditioning (on a single event $B$) to "Kolmogorov" conditioning (on an entire $\sigma$-algebra) using the same VC-theoretic tools.

Key Results

  • Convergence Rates: The author derives convergence rates of $n^{-1/2}$ for elementary conditioning when the conditioning sets belong to a VC-class.
  • The $\alpha$ Trade-off: For more complex cases where we condition on very small sets, the paper establishes a rate of $n^{\alpha-1/2}$, where $\alpha \in [0, 1/2)$ controls the minimum size of the sets we can reliably estimate.
  • Kolmogorov Estimators: The paper provides the first systematic analysis of plug-in estimators for Kolmogorov’s conditional expectations, showing they are "sensible" and converge at the expected $n^{-1/2}$ rate under finite conditions.

Limitations and Future Work

  • i.i.d. Assumption: The current proofs assume data is Independent and Identically Distributed (i.i.d.). In fields like Reinforcement Learning, data is often dependent (the next state depends on the current one), so extending these results to dependent processes is a key next step.
  • Minimax Optimality: It remains an open question whether these $n^{-1/2}$ rates are "minimax optimal" (the best possible theoretical rate) or if they can be improved under stronger assumptions about the density of the data.
  • Real-world Benchmarking: As a theoretical work, the paper does not test these estimators on real-world noisy data, which would be necessary to see how they compare to more complex kernel or neural network-based conditional estimators in practice.

Summary updated

BibTeX
@inproceedings{grunewalder2018plug,
  author = {Steffen Grünewälder},
  title = {{Plug-in Estimators for Conditional Expectations and Probabilities}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
}
Figure