Importance Sampling and Necessary Sample Size: An Information Theory Approach
Importance Sampling and Necessary Sample Size: An Information Theory Approach
复制标题
DOI：
10.1137/16m1093549
复制
发表时间：
2018-01-01
影响因子：
2
通讯作者：
Sanz-Alonso, Daniel
中科院分区：
文献类型：
--
作者：
Sanz-Alonso, Daniel
重要性抽样通过使用来自建议度量的样本来近似关于目标度量的期望。该方法在大类测试函数上的性能在很大程度上取决于两种测量之间的接近程度。我们得出一个一般的界限，需要举行的重要性抽样是成功的，并涉及目标和建议的样本大小之间的f-分歧。从一个新的和简单的信息论范式的重要性抽样的研究推导出的界。作为一般理论的例子，我们给出了关于样本容量的Kullback-Leibler和chi（2）-分歧，以及全变差和Hellinger距离的必要条件。我们的方法是非渐近的，它的一般性使我们能够区分这些指标的相对优点。不出所料，非对称发散比全变分或海林格给出了更清晰的边界。我们的结果扩展了现有的必要条件，并补充了足够的样本量所需的重要性抽样。
Importance sampling approximates expectations with respect to a target measure by using samples from a proposal measure. The performance of the method over large classes of test functions depends heavily on the closeness between both measures. We derive a general bound that needs to hold for importance sampling to be successful, and relates the f-divergence between the target and the proposal to the sample size. The bound is deduced from a new and simple information theory paradigm for the study of importance sampling. As examples of the general theory we give necessary conditions on the sample size in terms of the Kullback-Leibler and the chi(2)-divergences, and the total variation and Hellinger distances. Our approach is nonasymptotic, and its generality allows us to tell apart the relative merits of these metrics. Unsurprisingly, the nonsymmetric divergences give sharper bounds than total variation or Hellinger. Our results extend existing necessary conditions and complement sufficient ones on the sample size required for importance sampling.