Convergence rates for optimised adaptive importance samplers

Akyildiz Omer Deniz; Miguez Joaquin

摘要

Adaptive importance samplers are adaptive Monte Carlo algorithms to estimate expectations with respect to some target distribution which adapt themselves to obtain better estimators over a sequence of iterations. Although it is straightforward to show that they have the same O(1/root N) convergence rate as standard importance samplers, where N is the number of Monte Carlo samples, the behaviour of adaptive importance samplers over the number of iterations has been left relatively unexplored. In this work, we investigate an adaptation strategy based on convex optimisation which leads to a class of adaptive importance samplers termed optimised adaptive importance samplers (OAIS). These samplers rely on the iterative minimisation of the chi(2)-divergence between an exponential family proposal and the target. The analysed algorithms are closely related to the class of adaptive importance samplers which minimise the variance of the weight function. We first prove non-asymptotic error bounds for the mean squared errors (MSEs) of these algorithms, which explicitly depend on the number of iterations and the number of samples together. The non-asymptotic bounds derived in this paper imply that when the target belongs to the exponential family, the L-2 errors of the optimised samplers converge to the optimal rate of O(1/root N)and the rate of convergence in the number of iterations are explicitly provided. When the target does not belong to the exponential family, the rate of convergence is the same but the asymptotic L-2 error increases by a factor root rho(star), where rho(star) - 1 is the minimum chi(2)-divergence between the target and an exponential family proposal.

机译：自适应重要采样器是自适应蒙特卡罗算法，以估计关于某些目标分布的预期，该目标分布适应自身以获得一系列迭代序列获得更好的估计。虽然表明它们具有与标准重要性采样器相同的O（1 / root n）收敛速度，但是N是Monte Carlo样本的数量，相对留下了迭代次数的自适应重要性采样器的行为未开发的。在这项工作中，我们研究了基于凸优化的适应策略，这导致了一类称为优化的自适应重要性采样器（OAI）的自适应重要性采样器。这些采样器依赖于奇（2）的迭代最小化 - 指数家庭提案与目标之间的程度。分析的算法与自适应重要采样器的类密切相关，这最小化了权重函数的方差。我们首先向这些算法的平均平方误差（MSES）证明非渐近误差界限，这明确取决于迭代的数量和一起样本的数量。在本文中导出的非渐近界意味着当目标属于指数族时，优化采样器的L-2误差会聚到O（1 /根N）的最佳速率和数量中的收敛速率明确提供迭代。当目标不属于指数家庭时，会聚速率相同，但渐近L-2误差由因子根rho（星）增加，其中rho（星） - 1是最小chi（2） - 目标与指数家庭提案之间的分歧。

Convergence rates for optimised adaptive importance samplers

摘要

著录项

相关主题

期刊订阅