Curse of Dimensionality in Rare-Event Simulation

In rare-event simulation, importance sampling (IS) is widely used to improve the efficiency of probability estimation. Asymptotic optimality is a common efficiency criterion, which requires that the relative error of the estimator only grows subexponentially in the rarity parameter. Most studies, however, consider low-dimensional problems and the effect of dimensionality is seldom analyzed. Motivated by recent AI-related applications, we take a first step towards high-dimensional rare-event simulation and demonstrate that for very simple examples, IS proposals that utilize exponential tilting, arguably the most common IS approach, can suffer from the "curse of dimensionality". That is, while the growth rate of the relative error is polynomial in the rarity parameter thus leading to asymptotic optimality, the degree of the polynomial depends on the problem dimensionality. Therefore, when the dimension is high, the relative error can be huge even in the rarity parameter regime where IS is conventionally believed to work well.