Greedy Importance Sampling

Dale SchuurmansNeurIPS 1999 · OpenReview

Introduction

In probabilistic inference, we frequently need to calculate the expected value of a function $f(x)$ under a target distribution $P(x)$. When $P(x)$ is too complex to sample from directly, standard practice dictates using Importance Sampling (IS). In IS, we draw samples from a simpler "proposal" distribution $Q(x)$ and weight them to account for the difference between $Q(x)$ and $P(x)$.

However, standard IS has a significant Achilles' heel: variance. If the proposal distribution $Q$ misses the regions where $P$ is high (or where the product $f(x)P(x)$ is significant), the estimator becomes highly unreliable. This mismatch results in many samples with tiny weights and a few "lucky" samples with massive weights that entirely dominate the result.

While Markov Chain Monte Carlo (MCMC) methods like Metropolis-Hastings address this by "walking" toward high-probability regions, they introduce dependencies between samples, making them harder to parallelize and analyze. This paper introduces Greedy Importance Sampling, a technique that seeks a middle ground: it leverages the "intelligence" of a search-based method while maintaining the "independence" of traditional importance sampling.

The Greedy Importance Sampling Approach

The author proposes a series of extensions to standard importance sampling to explicitly search for high-probability regions without introducing bias.

Greedy Importance Sampling Algorithm and Path Dynamics

1. Block Sampling and Sliding Windows

Instead of weighting individual points in isolation, the algorithm samples a "block" of points. To handle large or unbounded spaces, it employs a "sliding window" of size $m$. For any sampled point, the algorithm finds $m-1$ successors by "climbing" a gradient and $m-1$ predecessors by "descending" it.

The "greedy" aspect of the method involves choosing the search direction based on the objective function $|f(x)P(x)|$. By explicitly guiding the sampler toward the regions that contribute most to the final expectation, the algorithm concentrates its computational effort where it matters most.

3. Unbiasedness via Careful Weighting

The core theoretical innovation is the weighting scheme. You don't have to sacrifice sample independence to get the benefits of local search; by treating a search trajectory as a single "block" unit, you can maintain the statistical properties of importance sampling.

To keep the estimator unbiased, the denominator of the weight must account for all possible starting points that could have led to the current sample. In 1D spaces, this involves handling "collisions" at local maxima. In higher dimensions, it involves managing "merging" search paths. The mathematical proof of unbiasedness relies on this specific denominator: the total $Q$-probability of the "predecessor tree" (all points that could lead to the current sample within $m$ steps).

Experimental Validation

The paper evaluates Greedy Importance Sampling using synthetic benchmarks designed to test specific distribution behaviors across varying dimensions.

  • 1-D Synthetic Problems: Across various configurations of $P, Q,$ and $f$ designed to test variance reduction and bias, Greedy IS consistently outperformed standard IS. It often reduced variance by a factor much greater than 2, easily offsetting the overhead of the "double sampling" used during the search phase.
  • 2-D Bivariate Gaussian: This test featured a highly correlated distribution where a "weak" proposal distribution $Q$ (like a standard normal) typically fails. Greedy IS achieved a standard deviation of 0.1374, significantly better than regular IS (0.1762) and vastly superior to MCMC methods like Gibbs (0.5464) or Metropolis (22.1212) for the specific sample size tested.
  • 6-D Kalman Filter: To represent a more "real-world" graphical model inference problem, the author tested a state estimation task in a dynamic probabilistic model. Greedy IS reduced the bias from 2.77 to 1.07 and slashed the standard deviation from 1.21 to 0.10 compared to standard importance sampling.

Limitations and Future Directions

While powerful, Greedy Importance Sampling comes with specific trade-offs:

  • The "Merge" Problem in High Dimensions: In high-dimensional discrete spaces, search paths frequently merge. Calculating the exact weights for an unbiased estimator requires exploring the full "predecessor tree," which can grow exponentially with the number of dimensions. Interestingly, the author notes that simply ignoring "merge" events acts as a surprisingly effective heuristic in continuous spaces, even if it sacrifices strict unbiasedness.
  • Computational Overhead: The greedy search requires evaluating the target distribution and its gradient multiple times per sample. While this drastically reduces variance, it increases the computational cost per sample.

For future work scaling to very high-dimensional problems, the author suggests utilizing Knuth’s algorithm for estimating the size of backtracking trees. This could keep the estimator computationally feasible and asymptotically unbiased, setting the stage for future comparisons against techniques like Hybrid Monte Carlo.

Summary updated

Abstract

I present a simple variation of importance sampling that explicitly search(cid:173) es for important regions in the target distribution. I prove that the tech(cid:173) nique yields unbiased estimates, and show empirically it can reduce the variance of standard Monte Carlo estimators. This is achieved by con(cid:173) centrating samples in more significant regions of the sample space.
BibTeX
@inproceedings{schuurmans1999greedy,
  author = {Dale Schuurmans},
  title = {{Greedy Importance Sampling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1999},
  url = {https://openreview.net/forum?id=H1-wtLbO-B},
}
Figure