Importance sampling (IS) is a fundamental tool for estimating expectations when we cannot sample directly from a target distribution $p(x)$. Instead, we draw samples from a "proposal" distribution $q(x)$ and weight them by the ratio $w = p(x)/q(x)$. While simple in theory, IS is notoriously fragile: if $q(x)$ is thin in regions where $p(x)$ is thick, the weights explode, leading to estimators with massive or even infinite variance.
Modern research has shifted from using static, "convenient" proposals to Adaptive Importance Sampling (AIS), where the proposal distribution is treated as a learnable model that evolves to match the target. By integrating neural networks, geometric optimization, and local search, these methods transform IS from a passive estimation tool into an active search for probability mass.
The Geometry of Proposal Adaptation
The core challenge of AIS is determining how to move $q(x)$ toward $p(x)$. A common objective is to minimize the $\chi^2$-divergence between the two, which directly relates to the variance of the importance weights. Joaquı́n Mı́guez has shown that framing this as a convex optimization problem allows for non-asymptotic error bounds, proving that adaptive samplers can achieve optimal convergence rates over time in Convergence rates for optimised adaptive importance samplers.
To navigate complex landscapes, researchers increasingly use the target's own geometry. Víctor Elvira and colleagues introduced GRAMIS in Gradient-based Adaptive Importance Samplers, which uses gradients and Hessians to "steer" proposals. To prevent multiple proposals from collapsing onto the same mode, they incorporate a physical "repulsion term," ensuring the sampler maintains coverage of multi-modal distributions. For non-smooth or constrained targets, the PNAIS algorithm by Víctor Elvira uses proximal optimization to handle non-differentiable regions, as detailed in A Proximal Newton Adaptive Importance Sampler.
Neural Proposals and Amortized Inference
The rise of deep generative models has provided a powerful new class of proposal distributions. Rather than simple Gaussians, researchers now use Normalizing Flows (NFs) and Variational Autoencoders (VAEs) to capture intricate, high-dimensional structures.
- Normalizing Flows: James A. Brofos demonstrated in Adaptation of the Independent Metropolis-Hastings Sampler with Normalizing Flow Proposals that NFs can be trained on-the-fly to serve as proposals for Independent Metropolis-Hastings, capturing complex multimodality that traditional MCMC misses.
- Variational Importance Sampling: Chengrui Li and team proposed VIS in Forward $\chi^2$ Divergence Based Variational Importance Sampling, which minimizes the forward $\chi^2$ divergence in log-space. This approach is more stable than standard Variational Inference and prevents the model from ignoring rare but critical data patterns.
- Unrolling Particles: In the context of temporal data, Fernando Gama developed a way to "unroll" particle filters into neural networks, learning optimal sampling distributions directly from raw measurements in Unrolling Particles: Unsupervised Learning of Sampling Distributions.
Balancing Exploration and Exploitation
AIS faces a classic "chicken and egg" problem: to build a good proposal, you need to know where the target's mass is, but to find that mass, you need a good proposal. If the sampler exploits known high-density regions too aggressively, it may miss isolated peaks (modes) elsewhere in the space.
Xiaoyu Lu and colleagues addressed this by reframing AIS as a multi-armed bandit problem in On Exploration, Exploitation and Learning in Adaptive Importance Sampling. Their algorithm, Daisee, uses a UCB-style "optimism boost" to ensure the sampler continues exploring the space even as it begins to exploit known modes. This balance is crucial for high-dimensional problems where the target distribution is often "peaky" and sparse.
Hybridizing with Local Search and Structure
When the target distribution is extremely complex, purely statistical adaptation may be insufficient. Hybrid methods combine the global reach of IS with the local precision of search algorithms.
Dale Schuurmans has pioneered several such approaches. Greedy Importance Sampling (GIS), introduced in Monte Carlo Inference via Greedy Importance Sampling, uses local search to find high-probability regions and then applies a weighting scheme to maintain an unbiased estimate. Similarly, Antithetic Markov Chain Sampling (AMCS) in Variance Reduction via Antithetic Markov Chains launches paired Markov chains from sampled points to "hunt" for influential modes.
Other researchers exploit the structural properties of the problem. For example, Anshumali Shrivastava showed that Locality Sensitive Hashing (LSH) can act as an "informative sampler in disguise," allowing for sub-linear computation of partition functions in A New Unbiased and Efficient Class of LSH-Based Samplers and Estimators for Partition Function Computation in Log-Linear Models. In the domain of discrete logic, Kuldeep S. Meel combined IS with knowledge compilation to create PartialKC, an anytime model counter that converges rapidly to exact counts by leveraging the structural efficiency of the CCDD language in Fast Converging Anytime Model Counting.
Black-box and Distributed Inference
A significant limitation of traditional IS is the requirement to know the analytical form of the proposal density $q(x)$ to calculate the weights. Qiang Liu bypassed this in Black-box Importance Sampling by using kernelized Stein discrepancy to calculate weights without needing the proposal's density. This "black-box" approach allows for much more flexible sampling strategies.
Finally, to handle "Big Data," Qiang Liu also developed Importance Weighted Consensus Monte Carlo in Importance Weighted Consensus Monte Carlo for Distributed Bayesian Inference, which enables distributed Bayesian inference by splitting data across machines and using importance weights to stitch the local posteriors back together accurately.