# Asymptotic optimality of adaptive importance sampling

arXiv: https://arxiv.org/abs/1806.00989 · HTML: https://mlsanity.com/paper/1806.00989/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2018.

## Built on by (most cited first, 9 of 9)

- [Adaptive Importance Sampling meets Mirror Descent: a Bias-variance tradeoff](https://mlsanity.com/paper/2110.15590/) (2021)
- [Active Measurement: Efficient Estimation at Scale](https://mlsanity.com/paper/2507.01372/) (2025)
- [SGD with Coordinate Sampling: Theory and Practice](https://mlsanity.com/paper/2105.11818/) (2021)
- [Adaptive importance sampling for heavy-tailed distributions via α-divergence minimization](https://mlsanity.com/paper/2310.16653/) (2023)
- [Generative Bayesian Optimization: Generative Models as Acquisition Functions](https://mlsanity.com/paper/2510.25240/) (2025)
- [Global convergence of optimized adaptive importance samplers](https://mlsanity.com/paper/2201.00409/) (2022)
- [A Quadrature Rule combining Control Variates and Adaptive Importance Sampling](https://mlsanity.com/paper/2205.11890/) (2022)
- [Adaptive Doubly Robust Estimator from Non-stationary Logging Policy under a Convergence of Average Probability](https://mlsanity.com/paper/2102.08975/) (2021)
- [Importance sampling based active learning for parametric seismic fragility curve estimation](https://mlsanity.com/paper/2109.04323/) (2021)

## Abstract (arXiv)

Adaptive importance sampling (AIS) uses past samples to update the textitsampling policy qt at each stage t. Each stage t is formed with two steps : (i) to explore the space with nt points according to qt and (ii) to exploit the current amount of information to update the sampling policy. The very fundamental question raised in this paper concerns the behavior of empirical sums based on AIS. Without making any assumption on the allocation policy nt, the theory developed involves no restriction on the split of computational resources between the explore (i) and the exploit (ii) step. It is shown that AIS is asymptotically optimal : the asymptotic behavior of AIS is the same as some "oracle" strategy that knows the targeted sampling policy from the beginning. From a practical perspective, weighted AIS is introduced, a new method that allows to forget poor samples from early stages.