Adaptive Sampling for Estimating Probability Distributions

Shubhanshu Shekhar, Tara Javidi, Mohammad GhavamzadehICML 2020 · OpenReview

When dealing with a limited budget of samples, how should you allocate them across multiple unknown discrete distributions to ensure you learn them all uniformly well? This paper tackles this exact problem, proposing a unified "optimistic tracking" algorithm based on Upper Confidence Bounds (UCB). The proposed strategy works across various distance metrics—including $\ell_2^2$, $\ell_1$, $f$-divergence, and separation distance—and is backed by theoretical regret bounds and matching lower bounds that prove its near-optimality.

The Challenge of Uniform Estimation

Imagine you are a pollster with a limited budget of $n$ surveys, and you want to estimate the political preferences of $K$ different demographic groups. Some groups might heavily favor one candidate, meaning their distribution is highly skewed and requires fewer samples to estimate accurately. Other groups might be completely undecided, representing a uniform distribution that requires significantly more samples to pin down.

If your goal is to ensure your worst estimate across all groups is as accurate as possible, how do you distribute your surveys?

This is the classic problem of allocating samples to learn $K$ distributions "uniformly well" (minimizing the maximum estimation error). If the true distributions were known in advance, an "oracle" could perfectly calculate the optimal allocation. However, since they are unknown, an algorithm must adaptively sample to discover the distributions while simultaneously driving the allocation toward the optimal ratio. While previous multi-armed bandit research has heavily explored estimating the means of distributions, this paper generalizes the challenge to estimating entire probability distributions using standard statistical distance measures.

The Optimistic Tracking Algorithm

To solve this, the authors formulate the problem as a minimax optimization and propose a general Optimistic Tracking Algorithm. The approach breaks down into three core steps:

  1. Unified Objective Function: The authors define a class of well-behaved (concave-convex) objective functions. For each distance metric ($\ell_2^2$, $\ell_1$, $f$-divergence, separation distance), they derive an approximate objective function $\phi(c_i, T_i)$ that decouples the problem. Here, $c_i$ is a parameter depending solely on the true distribution $i$, and $T_i$ is the number of samples allocated to it.
  2. Optimistic Tracking (UCB): Because the true complexity $c_i$ is unknown, the algorithm maintains a high-probability upper bound (an optimistic estimate) for $c_i$ based on the samples collected so far.
  3. Adaptive Allocation: At each step, the algorithm plugs these optimistic estimates into the objective function and allocates the next sample to the distribution that currently exhibits the highest estimated error.

This approach is a novel extension of the Upper Confidence Bound (UCB) principle, adapted from standard bandit problems to the complex space of probability distribution estimation.

Key Insights

  • Decoupling Complex Metrics: The authors demonstrate that the expected error for complex distance metrics can be cleanly approximated by a function that separates the underlying distribution's complexity ($c_i$) from the sample count ($T_i$).
  • Handling $f$-divergences via Taylor Expansion: For metrics like KL-divergence, a closed-form objective function isn't mathematically possible. The authors cleverly bypass this by using a higher-order Taylor approximation to create a surrogate objective function that fits their general tracking framework.
  • Fundamental Limits of Adaptive Sampling: The authors don't just provide an algorithm; they prove it is fundamentally tight. By deriving algorithm-independent lower bounds, they show that the deviation from the oracle allocation achieved by their optimistic tracking scheme cannot be substantially improved by any adaptive algorithm.

Theoretical and Empirical Results

The authors mathematically bound the "regret"—the difference in maximum error between their algorithm's allocation and the perfect oracle allocation. They achieve a regret of $\tilde{\mathcal{O}}(n^{-3/2})$ for $\ell_2^2$, $\tilde{\mathcal{O}}(n^{-3/4})$ for $\ell_1$ and separation distances, and $\tilde{\mathcal{O}}(n^{-5/2})$ for KL-divergence. Furthermore, they proved an algorithm-independent lower bound of $\Omega(\sqrt{n})$ on the allocation deviation, establishing the near-optimality of their approach.

Beyond the theory, the authors evaluated their algorithms using synthetic datasets, simulating discrete distributions where one is uniform and the other is skewed.

Adaptive vs. Uniform Allocation

In these experiments, the adaptive scheme (A) significantly outperformed a naive uniform allocation (U), especially when the true distributions were highly skewed. The adaptive method consistently achieved lower error rates.

Adaptive vs. Greedy Allocation

Additionally, the optimistic tracking algorithm demonstrated lower variance and better stability than greedy (G) or forced-exploration baseline strategies, which often suffered from high variance and instability during the allocation process.

Limitations and Future Work

While the theoretical bounds are tight, they currently depend on the support size ($l$) and the number of distributions ($K$) being fixed and relatively small.

The authors suggest several promising avenues for future work to address these limitations:

  1. Scaling up: Handling large support sizes ($l$) by integrating specialized large-alphabet estimators, and managing a massive number of distributions ($K$) by assuming structural similarities between different arms.
  2. Reinforcement Learning: Applying this framework to efficiently learn the transition dynamics (models) of finite Markov Decision Processes (MDPs).
  3. New Metrics: Extending the theoretical analysis to Wasserstein distances.

Summary updated

Abstract

We consider the problem of allocating a fixed budget of samples to a finite set of discrete distributions to learn them uniformly well (minimizing the maximum error) in terms of four common distanc...
BibTeX
@inproceedings{shekhar2020adaptive,
  author = {Shubhanshu Shekhar and Tara Javidi and Mohammad Ghavamzadeh},
  title = {{Adaptive Sampling for Estimating Probability Distributions}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=u3Fy3BE0TyjE},
}
Figure