INSIGHT FROM THE KULLBACK-LEIBLER DIVERGENCE INTO ADAPTIVE IMPORTANCE SAMPLING SCHEMES FOR RARE EVENT ANALYSIS IN HIGH DIMENSION

• 成果类型: Article
• 署名作者: Beh, Jason; Shadmi, Yonatan; Simatos, Florian
• 署名单位: Universite de Toulouse; National Office for Aerospace Studies & Research (ONERA); Technion Israel Institute of Technology; Universite de Toulouse; Institut Superieur de l'Aeronautique et de l'Espace (ISAE-SUPAERO); National Office for Aerospace Studies & Research (ONERA)
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/24-AAP2136
• 发表日期: 2025
• 页码: 1083-1124
• 关键词: cross-entropy method; mixture; distributions; curse

摘要

We study two adaptive importance sampling schemes for estimating the probability of a rare event in the high-dimensional regime d - oc with d the dimension. The first scheme is the prominent cross-entropy (CE) method, and the second scheme, motivated by recent results, uses as auxiliary distribution a projection of the optimal auxiliary distribution on a lower-dimensional subspace. In these schemes, two samples are used: the first one to learn the auxiliary distribution and the second one, drawn according to the learned distribution, to perform the final probability estimation. Contrary to the common belief that the sample size needs to grow exponentially in the dimension to make the estimator consistent and avoid the weight degeneracy phenomenon, we find that a polynomial sample size in the first learning step is enough. We prove this result assuming that the sought probability is bounded away from 0. For CE, insight is provided on the polynomial growth rate which remains implicit. In contrast, we study the second scheme in a simple computational framework assuming that samples from the conditional distribution are available. This makes it possible to show that the sample size only needs to grow like rd with r the effective dimension of the projection, which highlights the potential benefits of these projection methods.