betaFeedback

WorksMathematics

Consistency considerations for rare-event importance sampling

Abstract

We consider the problem of estimating a small probability p=P(X∈A)p = P(X \in A) by importance sampling with auxiliary density gg, where XX is drawn according to some density ff. We establish a simple necessary and sufficient condition for the consistency of the importance sampling estimator in triangular schemes where the dimension, the densities ff and gg and the set AA may evolve. It allows to refine the results of Chatterjee and Diaconis [Ann. Appl. Probab. 28 (2018), no. 2, 1099-1135] by establishing the exact minimal sample size required for consistency. Moreover, it allows to study the regime p→0p \to 0 which, despite being the relevant mathematical regime for rare-event estimations, has received very little attention so far. We perform an in-depth study of the hyperplane case A={x:x⊤u≥α}A = \{x: x^\top u \geq α\} with Gaussian densities, showing that in this case, the optimal importance sampling density considerably improves consistency compared to the standard Monte Carlo estimator. However, we conclude the paper with moment considerations which suggest that, whenever the Monte Carlo and optimal importance sampling estimators both converge, convergence may occur faster for the Monte Carlo estimator.

Introduction

Triangular importance sampling schemes for rare-event estimation

Let Y∈RdY \in\mathbb{R}^{d} be a random variable which is absolutely continuous with respect to Lebesgue measure with density ff (which we write Y∼fY \sim f) and h:Rd→Rh : \mathbb{R}^{d} \to\mathbb{R} measurable so that h(Y)h(Y) is integrable. Importance sampling is a widely used simulation technique [2, 9] to estimate E[h(Y)]\mathbb{E}[h(Y)] from samples from another distribution with density gg, called auxiliary distribution. The idea is simply to change measure to rewrite E[h(Y)]=E[ℓ(X)h(X)]\mathbb{E}[h(Y)] = \mathbb{E}[\ell(X)h(X)] with X∼gX \sim g and ℓ=f/g\ell= f/g the likelihood ratio between ff and gg, and then estimate E[ℓ(X)h(X)]\mathbb{E}[\ell(X)h(X)] by standard Monte Carlo with an i.i.d. sample drawn according to gg.

In this paper we are more specifically interested in the reliability context where one seeks to estimate a (small) probability p=P(Y∈A)p = \mathbb{P}(Y \in A): this corresponds to the case where h=ξAh = \xi_A, the indicator function of the set AA, and the corresponding importance sampling estimator is then given by

p^=1n∑i=1nℓ(Xi)ξA(Xi),Xi∼g i.i.d.,ℓ=fg.\hat{p} = \frac{1}{n} \sum_{i=1}^{n} \ell(X_i)\xi_A(X_i),\quad X_i \sim g\ \text{i.i.d.},\quad\ell= \frac{f}{g}.

Note that for this estimator to be well defined with the usual convention 00=0\frac{0}{0} = 0, one needs fξAf\xi_A to be absolutely continuous with respect to gg, i.e., g(x)=0⇒f(x)ξA(x)=0g(x) = 0 \Rightarrow f(x)\xi_A(x) = 0. The conditional distribution f∣A=fξA/pf|_A = f\xi_A/p is called the zero-variance auxiliary distribution since p^=p\hat{p} = p when g=f∣Ag = f|_A. When pp is small, controlling the absolute error p^−p\hat{p}-p is not necessarily insightful, and one rather turns to the relative estimator p^/p\hat{p}/p, leading to considering

p^p=1np∑i=1nℓ(Xi)ξA(Xi)=1n∑i=1nℓA(Xi),Xi∼g i.i.d.,ℓA=ℓξAp=fξApg=f∣Ag.(1)\frac{\hat{p}}{p} = \frac{1}{np}\sum_{i=1}^{n}\ell(X_i)\xi_A(X_i) = \frac{1}{n}\sum_{i=1}^{n}\ell_A(X_i),\quad X_i \sim g\ \text{i.i.d.},\quad\ell_A = \frac{\ell\xi_A}{p} = \frac{f\xi_A}{pg} = \frac{f|_A}{g}. \tag*{(1)}

The previous display shows that p^/p\hat{p}/p can be seen as the empirical mean of the likelihood ratios ℓA(Xi)\ell_A(X_i): thus, the key object of interest is the likelihood ratio ℓA=f∣A/g\ell_A = f|_A/g between the conditional distribution f∣Af|_A and the auxiliary distribution gg, rather than the original likelihood ratio ℓ=f/g\ell= f/g between ff and $g.

Since E[ℓA(X)]=1\mathbb{E}[\ell_A(X)] = 1, the law of large numbers readily entails that, for fixed problem parameters dd, ff, gg and AA, we have p^/p→1\hat{p}/p \to1 almost surely as n→∞n \to\infty. However, there are different reasons for considering triangular schemes where, for instance, AA and/or dd are not fixed. In reliability for instance, one is interested in estimating small probabilities, motivating the study of p^/p\hat{p}/p in the regime p→0p \to0. Moreover, there has recently been a surge of interest for high-dimensional importance sampling schemes [1, 3, 5, 18], corresponding to the regime d→∞d \to\infty. In such cases, we are in a triangular setting where the law of the summands ℓA(Xi)\ell_A(X_i) is not fixed and evolves together with the other problem parameters. The goal of this paper is to study this regime.

Both regimes have been studied in the literature, but mostly through moment-based criteria. In rare-event simulation, the regime p→0p \to0 is classically handled by requiring the relative second moment E[ℓA(X)2]=E[ℓA(YA)]\mathbb{E}[\ell_A(X)^2] = \mathbb{E}[\ell_A(Y_A)] to remain bounded (bounded relative error) or to satisfy log⁡E[ℓA(YA)]=o(log⁡(1/p))\log\mathbb{E}[\ell_A(Y_A)] = o(\log(1/p)) (logarithmic efficiency); large deviations theory is then the main tool to design efficient auxiliary distributions, see for instance [2, 12, 15] and [10] for the refinements of this approach. In the high-dimensional regime d→∞d \to\infty, the degeneracy of importance sampling has been pointed out in reliability [3] and in filtering [6], and the required sample size has been related to the second moment of the likelihood ratio [1] or to the Kullback–Leibler divergence [8, 16]. In this paper we take a distributional viewpoint and focus on the consistency of p^\hat{p}, i.e., on the minimal sample size ensuring p^/p⇒1\hat{p}/p \Rightarrow1.

Triangular setting

To formalize this, we consider in the rest of the paper a sequence of problems ((dr,fr,gr,Ar,nr),r≥1)((d_r,f_r,g_r,A_r,n_r), r \ge1) where for each r≥1r \ge1, dr∈N∖{0}d_r \in\mathbb{N} \setminus\{0\} is the problem dimension, Ar⊆RdrA_r \subseteq\mathbb{R}^{d_r} is measurable and frf_r and grg_r are drd_r-dimensional densities such that frξArf_r \xi_{A_r} is absolutely continuous with respect to grg_r. Moreover, we define pr=P(Y∈Ar)p_r = \mathbb{P}(Y \in A_r), Y∼frY \sim f_r. To avoid cumbersome notation, the dependency on rr is omitted from the notation, but every limiting regime, supremum or infimum is taken with respect to rr: for instance, d→∞d \to\infty means that dr→∞d_r \to\infty as r→∞r \to\infty, inf⁡p=inf⁡rpr\inf p = \inf_r p_r, etc. For simplicity, we will say in the sequel that p^\hat p is consistent if p^/p⇒1\hat p/p \Rightarrow1 with ⇒\Rightarrow referring to convergence in distribution. Note that since the dimension dd may evolve (e.g., in the high-dimensional regime d→∞d \to\infty), the sequence of models is not naturally coupled: this is why it is more natural to only ask for convergence in distribution rather than almost surely.

Notation

In the rest of the paper, if MM is a square matrix, ∥M∥op\lVert M\rVert_{\mathrm{op}} denotes its operator norm, det⁡(M)\det(M) its determinant and tr⁡(M)\operatorname{tr}(M) its trace. If MM is further symmetric, λmin⁡(M)\lambda_{\min}(M) and λmax⁡(M)\lambda_{\max}(M) denote its smallest and largest eigenvalue, respectively. Note that if MM is symmetric definite positive, then ∥M−1∥op=1/λmin⁡(M)\lVert M^{-1}\rVert_{\mathrm{op}} = 1/\lambda_{\min}(M) and ∥M∥op=λmax⁡(M)\lVert M\rVert_{\mathrm{op}} = \lambda_{\max}(M). Furthermore, with ff, gg and AA as introduced in § 1.2, XX and XiX_i denote random variables with density gg and YY and YAY_A denote random variables with density ff and f∣Af\mid_A, respectively. Moreover, for positive, deterministic sequences u=(ur)u = (u_r) and v=(vr)v = (v_r), we will write u≪vu \ll v or v≫uv \gg u to mean that u/v→0u/v \to0, or equivalently, v/u→+∞v/u \to+\infty.

Conditions for consistency, and relation with the Chatterjee–Diaconis approach

Closing the gap in the CD approach thanks to a simple necessary and sufficient condition

As explained in the abstract of their groundbreaking paper [8], Chatterjee and Diaconis have shown that, in a fairly general setting, a sample of size approximately eD(f∣A,g)e^{D(f\mid_A,g)} is necessary and sufficient for accurate estimation by importance sampling, where D(f∣A,g)=E[log⁡(ℓA(YA))]∈[0,∞]D(f\mid_A,g) = \mathbb{E}[\log(\ell_A(Y_A))] \in[0,\infty] is the Kullback–Leibler (KL) divergence between f∣Af\mid_A and gg, which exists provided that f∣Af\mid_A is absolutely continuous with respect to gg. In the sequel, we will refer for short to n≫eD(f∣A,g)n \gg e^{D(f\mid_A,g)} as the CD condition. Actually, although Chatterjee and Diaconis only mention the threshold eD(f∣A,g)e^{D(f\mid_A,g)} in their abstract, their results are more precise. Indeed, [8 Theorem 1.3] states that for any t≥0t \ge0 and δ∈(0,1)\delta\in(0,1),

E[∣p^p−1∣]≤e−t/4+2P(log⁡ℓA(YA)>D(f∣A,g)+t/2)if n=eD(f∣A,g)+t.(2)\mathbb{E}\left[\left|\frac{\hat p}{p}-1\right|\right] \le e^{-t/4}+2\sqrt{\mathbb{P}\left(\log\ell_A(Y_A)>D(f\mid_A,g)+t/2\right)} \quad\text{if } n=e^{D(f\mid_A,g)+t}. \tag*{(2)}

and

P(p^p≥1−δ)≤e−t/2+P(log⁡ℓA(YA)≤D(f∣A,g)−t/2)1−δif n=eD(f∣A,g)−t.(3)\mathbb{P}\left(\frac{\hat p}{p}\ge1-\delta\right)\le e^{-t/2}+\frac{\mathbb{P}\left(\log\ell_A(Y_A)\le D(f\mid_A,g)-t/2\right)}{1-\delta}\quad\text{if } n=e^{D(f\mid_A,g)-t}. \tag*{(3)}

Roughly speaking, tt needs to grow faster than the fluctuations of the log-likelihood ratio around its mean for these two upper bounds to vanish. This suggests that if tt is larger than these fluctuations, then p^\hat p will be consistent for n=eD(f∣A,g)+tn=e^{D(f\mid_A,g)+t} and not consistent for n=eD(f∣A,g)−tn=e^{D(f\mid_A,g)-t}. To formalize this, we will sometimes consider the following assumption.

Assumption 1. Let LL be a sequence of deterministic, positive numbers growing to +∞+\infty. We say that the fluctuations of the log-likelihood ratio around its mean are of the order of LL if D(f∣A,g)≫LD(f\vert_A,g)\gg L and if there exists a finite random variable Lˉ∞\bar{L}_{\infty} such that Lˉ⇒Lˉ∞\bar{L}\Rightarrow\bar{L}_{\infty}, where

Lˉ=log⁡(ℓA(YA))−D(f∣A,g)L.(4)\bar{L}=\frac{\log(\ell_A(Y_A))-D(f\vert_A,g)}{L}. \tag*{(4)}

When this assumption holds, then the CD bounds (2) and (3) readily imply the following result in terms of consistency.

Lemma 1. Assume that the fluctuations of the log-likelihood ratio around its mean are of the order of LL in the sense of Assumption 1, and let t≫Lt\gg L: then p^\hat{p} is consistent if n=eD(f∣A,g)+tn=e^{D(f\vert_A,g)+t} and not consistent if n=eD(f∣A,g)−tn=e^{D(f\vert_A,g)-t}.

Therefore, the CD approach leaves open the consistency of p^\hat{p} in the range between eD(f∣A,g)−Le^{D(f\vert_A,g)-L} and eD(f∣A,g)+Le^{D(f\vert_A,g)+L}: actually, there is a simple necessary and sufficient condition which allows to close this gap.

Theorem 1. p^/p⇒1\hat{p}/p\Rightarrow1 if and only if ℓA(YA)/n⇒0\ell_A(Y_A)/n\Rightarrow0.

Proof. Let χin=ℓA(Xi)/n\chi_i^n=\ell_A(X_i)/n, so that p^/p=∑i=1nχin\hat{p}/p=\sum_{i=1}^n\chi_i^n is a (triangular) sum of i.i.d. random variables. Since E(χin)=1/nE(\chi_i^n)=1/n, we have χin⇒0\chi_i^n\Rightarrow0 and so the triangular array (χin,1≤i≤n)(\chi_i^n,1\leq i\leq n) is, in the language of [11 Definition VII.2.33], infinitesimal. Therefore, according to [11 Theorem VII.2.35], we have p^/p⇒1\hat{p}/p\Rightarrow1 if and only if there exists a truncation function hh, i.e., a bounded function equal to the identity function in a neighborhood of 00, such that the following three conditions hold:

  • [β] nE[h(χ1n)]→1[\beta]\ nE[h(\chi_1^n)]\to1;

  • [γ] n{E[h(χ1n)2]−{E[h(χ1n)]}2}→0[\gamma]\ n\{E[h(\chi_1^n)^2]-\{E[h(\chi_1^n)]\}^2\}\to0;

  • [δ] nE[ϕ(χ1n)]→0[\delta]\ nE[\phi(\chi_1^n)]\to0 for all bounded, continuous functions ϕ:R→R\phi:\mathbb{R}\to\mathbb{R} which are 00 around 00.

In this case, [β][\beta] and [γ][\gamma] hold for all truncation functions. Let us assume that p^/p⇒1\hat{p}/p\Rightarrow1 and let us prove that ℓA(YA)/n⇒0\ell_A(Y_A)/n\Rightarrow0. We use repeatedly the change of measure formula E[φ(YA)]=E[ℓA(X)φ(X)]E[\varphi(Y_A)]=E[\ell_A(X)\varphi(X)] for any measurable, positive function φ\varphi. In particular, for any ε>0\varepsilon>0 we have

P(ℓA(YA)/n≥ε)=E(ℓA(X);ℓA(X)/n≥ε)=1−nE[h(χ1n)]P(\ell_A(Y_A)/n\geq\varepsilon)=E(\ell_A(X);\ell_A(X)/n\geq\varepsilon)=1-nE[h(\chi_1^n)]

with hh the truncation function h(x)=x1(∣x∣<ε)h(x)=x1(|x|<\varepsilon). Since p^/p⇒1\hat{p}/p\Rightarrow1, we have nE[h(χ1n)]→1nE[h(\chi_1^n)]\to1 by [β][\beta] giving ℓA(YA)/n⇒0\ell_A(Y_A)/n\Rightarrow0 as desired.

Let us now assume that ℓA(YA)/n⇒0\ell_A(Y_A)/n\Rightarrow0, and let us prove that p^/p⇒1\hat{p}/p\Rightarrow1, i.e., that [β][\beta], [γ][\gamma] and [δ][\delta] hold for h(x)=x1(∣x∣<ε)h(x)=x1(|x|<\varepsilon) for some ε>0\varepsilon>0. For [β][\beta] this is the same argument as above, since nE[h(χ1n)]=P(ℓA(YA)/n<ε)nE[h(\chi_1^n)]=P(\ell_A(Y_A)/n<\varepsilon). Let us now prove [γ][\gamma]. Since nEh(χ1n)→1nE h(\chi_1^n)\to1, we have n{E[h(χ1n)]}2→0n\{E[h(\chi_1^n)]\}^2\to0 and so we only have to prove that nE[h(χ1n)2]→0nE[h(\chi_1^n)^2]\to0. Changing measure gives

nE[h(χ1n)2]=1nE(ℓA(X)2;ℓA(X)/n≤ε)=E[h(ℓA(YA)/n)].nE\left[h(\chi_1^n)^2\right]=\frac{1}{n}E\left(\ell_A(X)^2;\ell_A(X)/n\leq\varepsilon\right)=E[h(\ell_A(Y_A)/n)].

Since ℓA(YA)/n⇒0\ell_A(Y_A)/n\Rightarrow0 by assumption and h(ℓA(YA)/n)h(\ell_A(Y_A)/n) is bounded, we get E[h(ℓA(YA)/n)]→0E[h(\ell_A(Y_A)/n)]\to0. Let us now prove [δ][\delta]. Since nE[ϕ(χ1n)];χ1n≥ε≤nsup⁡{ϕ(χ1n);χ1n≥ε}nE[\phi(\chi_1^n)];\chi_1^n\geq\varepsilon\leq n\sup\{\phi(\chi_1^n);\chi_1^n\geq\varepsilon\} it is enough to prove that nP(χ1n≥ε)→0nP(\chi_1^n\geq\varepsilon)\to0. We have

nP(χ1n≥ε)=nP(ℓA(X)≥εn)=E(1ℓA(YA)/n;1ℓA(YA)/n≤1ε)=E(Z;Z≤1/ε)nP(\chi_1^n\geq\varepsilon)=nP(\ell_A(X)\geq\varepsilon n)=E\left(\frac{1}{\ell_A(Y_A)/n};\frac{1}{\ell_A(Y_A)/n}\leq\frac{1}{\varepsilon}\right)=E(Z;Z\leq1/\varepsilon)

with Z=1ℓA(YA)/nZ = \frac{1}{\ell_A(Y_A)/n} which, by assumption, converges in distribution to +∞+\infty. In particular, 1(Z≤1/ε)⇒0\mathbb{1}(Z \le1/\varepsilon) \Rightarrow0 and since Z1(Z≤1/ε)Z\mathbb{1}(Z \le1/\varepsilon) is bounded by 1/ε1/\varepsilon, the bounded convergence theorem implies that E(Z;Z≤1/ε)→0\mathbb{E}(Z; Z \le1/\varepsilon) \to0 which gives the desired result. □\square

Thanks to Theorem 1, the gap between the CD condition and the consistency of p^\hat p can be understood: on the one hand, eD(f∣A,g)/n=exp⁡{E[log⁡(ℓA(YA)/n)]}\mathrm{e}^{D(f\mid A,g)}/n = \exp\{\mathbb{E}[\log(\ell_A(Y_A)/n)]\} so that n≫eD(f∣A,g)n \gg\mathrm{e}^{D(f\mid A,g)} if and only if E[log⁡(ℓA(YA)/n)]→−∞\mathbb{E}[\log(\ell_A(Y_A)/n)] \to-\infty, while on the other hand, Theorem 1 states that p^/p⇒1\hat p/p \Rightarrow1 if and only if log⁡(ℓA(YA)/n)⇒−∞\log(\ell_A(Y_A)/n) \Rightarrow-\infty: thus, the difference between the CD condition and the consistency of p^\hat p lies in the potential discrepancy between the convergence in distribution and in the mean of the normalized log-likelihood ratio log⁡(ℓA(YA)/n)\log(\ell_A(Y_A)/n). Because log⁡(ℓA(YA))\log(\ell_A(Y_A)) is not of constant sign, there is no systematic link between the behavior of its mean and of its distribution and the behavior of the mean is governed by the behavior of the positive and negative parts:

E[log⁡(ℓA(YA)/n)]=E[log⁡+(ℓA(YA))]−E[log⁡−(ℓA(YA))]−log⁡n(5)\mathbb{E}[\log(\ell_A(Y_A)/n)] = \mathbb{E}[\log_+(\ell_A(Y_A))] - \mathbb{E}[\log_-(\ell_A(Y_A))] - \log n \tag*{(5)}

with log⁡+x=1(x≥1)log⁡x\log_+ x = \mathbb{1}(x \ge1)\log x and log⁡−(x)=−1(x≤1)log⁡x=log⁡+(1/x)\log_-(x) = -\mathbb{1}(x \le1)\log x = \log_+(1/x). For the record we state the following lemma which stems from the convexity inequality log⁡x≤x−1\log x \le x - 1.

Lemma 2. We have E[log⁡−(ℓA(YA))]≤1\mathbb{E}[\log_-(\ell_A(Y_A))] \le1.

This result shows that the potential discrepancy between the behavior in the mean and in distribution only owes to the behavior of the positive part of the log-likelihood ratio. In particular, this simple observation has the following consequence.

Lemma 3. If log⁡n≫D(f∣A,g)\log n \gg D(f\mid A,g), then p^\hat p is consistent. In particular, if sup⁡D(f∣A,g)<∞\sup D(f\mid A,g) < \infty, then p^\hat p is consistent for any n≫1n \gg1.

Proof. Assume that log⁡n≫D(f∣A,g)\log n \gg D(f\mid A,g), i.e., E[log⁡(ℓA(YA))]/log⁡n→0\mathbb{E}[\log(\ell_A(Y_A))]/\log n \to0. By (5) we have

E[log⁡+(ℓA(YA))]log⁡n=E[log⁡(ℓA(YA))]log⁡n+E[log⁡−(ℓA(YA))]log⁡n\frac{\mathbb{E}[\log_+(\ell_A(Y_A))]}{\log n} = \frac{\mathbb{E}[\log(\ell_A(Y_A))]}{\log n} + \frac{\mathbb{E}[\log_-(\ell_A(Y_A))]}{\log n}

and since E[log⁡−(ℓA(YA))]≤1\mathbb{E}[\log_-(\ell_A(Y_A))] \le1 this implies that E[log⁡+(ℓA(YA))]/log⁡n→0\mathbb{E}[\log_+(\ell_A(Y_A))]/\log n \to0. Since log⁡+(x)≥0\log_+(x) \ge0 this yields log⁡+(ℓA(YA))/log⁡n⇒0\log_+(\ell_A(Y_A))/\log n \Rightarrow0 which eventually implies that log⁡+(ℓA(YA))−log⁡n=log⁡n(log⁡+(ℓA(YA))/log⁡n−1)⇒−∞\log_+(\ell_A(Y_A))-\log n = \log n(\log_+(\ell_A(Y_A))/\log n - 1) \Rightarrow-\infty. Since log⁡−(ℓA(YA))\log_-(\ell_A(Y_A)) is tight (it is positive and its mean is bounded by 1 by Lemma 2), this implies that log⁡(ℓA(YA))−log⁡n⇒−∞\log(\ell_A(Y_A))-\log n \Rightarrow-\infty, i.e., ℓA(YA)/n⇒0\ell_A(Y_A)/n \Rightarrow0 and so we can conclude with Theorem 1. □\square

Of course, this result is far from being sharp as it settles the question in the regime n=eωn = \mathrm{e}^{\omega} with ω≫D(f∣A,g)\omega\gg D(f\mid A,g) whereas the action takes place for ω∼D(f∣A,g)\omega\sim D(f\mid A,g): however, the interest of the previous lemma lies in its simplicity, with no assumption whatsoever. Under Assumption 1, we can close the gap and get the precise minimal sample size required for the consistency of p^\hat p.

Lemma 4. Assume that the fluctuations of the log-likelihood ratio around its mean are of the order of LL in the sense of Assumption 1 and let n=eD(f∣A,g)+cLn = \mathrm{e}^{D(f\mid A,g)+cL} for some c∈Rc \in\mathbb{R}: then p^\hat p is consistent if P(Lˉ∞≥c)=0\mathbb{P}(\bar L_\infty\ge c) = 0 and not consistent if P(Lˉ∞>c)>0\mathbb{P}(\bar L_\infty> c) > 0. In particular, if Lˉ∞\bar L_\infty is unbounded above (i.e., P(Lˉ∞≥c)>0\mathbb{P}(\bar L_\infty\ge c) > 0 for every c∈Rc \in\mathbb{R}), then p^\hat p is consistent if and only if n=eD(f∣A,g)+tn = \mathrm{e}^{D(f\mid A,g)+t} for some t≫Lt \gg L.

Proof. Assume that Assumption 1 holds and let n=eD(f∣A,g)+cLn=e^{D(f\mid A,g)+cL} for some c∈Rc\in\mathbb{R}: the question is whether ℓA(YA)/n⇒0\ell_A(Y_A)/n\Rightarrow0 or not. Let ε∈(0,1)\varepsilon\in(0,1) and c−<c<c+c_-<c<c_+ two continuity points of Lˉ∞\bar{L}_\infty: since P(ℓA(YA)≥εn)=P(Lˉ≥(log⁡ε)/L+c)\mathbb{P}(\ell_A(Y_A)\geq\varepsilon n)=\mathbb{P}(\bar{L}\geq(\log\varepsilon)/L+c) with Lˉ⇒Lˉ∞\bar{L}\Rightarrow\bar{L}_\infty and L→∞L\to\infty, we have for rr large enough P(Lˉ≥c+)≤P(ℓA(YA)≥εn)≤P(Lˉ≥c−)\mathbb{P}(\bar{L}\geq c_+)\leq\mathbb{P}(\ell_A(Y_A)\geq\varepsilon n)\leq\mathbb{P}(\bar{L}\geq c_-) and so letting first r→∞r\to\infty and then c−↑cc_-\uparrow c and c+↓cc_+\downarrow c we obtain

P(Lˉ∞>c)≤lim inf⁡P(ℓA(YA)≥εn)≤lim sup⁡P(ℓA(YA)≥εn)≤P(Lˉ∞≥c)\mathbb{P}(\bar{L}_\infty>c)\leq\liminf\mathbb{P}(\ell_A(Y_A)\geq\varepsilon n)\leq\limsup\mathbb{P}(\ell_A(Y_A)\geq\varepsilon n)\leq\mathbb{P}(\bar{L}_\infty\geq c)

which proves the desired result. Assume now that Lˉ∞\bar{L}_\infty is unbounded above. Then the previous argument readily implies that p^\hat{p} is consistent if n=eD(f∣A,g)+tn=e^{D(f\mid A,g)+t} for some t≫Lt\gg L. If not, then by working along a subsequence we have sup⁡(t/L)<∞\sup(t/L)<\infty and along this subsequence, the previous arguments imply that P(ℓA(YA)/n≥ε)↛0\mathbb{P}(\ell_A(Y_A)/n\geq\varepsilon)\not\to0, so that p^\hat{p} is not consistent by Theorem 1. □\square

Comparison to the standard Monte Carlo estimator

Let p^MC=1n∑i=1nξA(Yi)\hat{p}^{\mathrm{MC}}=\frac{1}{n}\sum_{i=1}^{n}\xi_A(Y_i) with the YiY_i’s i.i.d. ∼f\sim f be the standard Monte Carlo estimator of pp: a natural question is whether importance sampling improves the situation compared to the standard Monte Carlo approach. The “improvement” can take different forms depending on the performance metric considered: here we focus on consistency and we typically would like the consistency of p^MC\hat{p}^{\mathrm{MC}} to imply that of p^\hat{p}. When this occurs, i.e. p^MC\hat{p}^{\mathrm{MC}} consistent implies p^\hat{p} consistent, we say that the importance sampling estimator p^\hat{p} is more consistent than the standard Monte Carlo estimator p^MC\hat{p}^{\mathrm{MC}}. Theorem 1 can help shed light on this question.

First, note that since ℓA(YA)=1/p\ell_A(Y_A)=1/p almost surely (a.s.) when g=fg=f, Theorem 1 readily entails that p^MC/p⇒1\hat{p}^{\mathrm{MC}}/p\Rightarrow1 if and only if np→∞np\to\infty. Next, since ξA(YA)=1\xi_A(Y_A)=1 a.s., we have

P(ℓA(YA)/n≥ε)=P(ℓ(YA)≥εnp)=P(g(YA)≤f(YA)/(εnp)).\mathbb{P}(\ell_A(Y_A)/n\geq\varepsilon)=\mathbb{P}(\ell(Y_A)\geq\varepsilon np)=\mathbb{P}(g(Y_A)\leq f(Y_A)/(\varepsilon np)).

By Theorem 1 we need this probability to vanish to have p^\hat{p} consistent, and we can distinguish two cases:

  • if p^MC\hat{p}^{\mathrm{MC}} is consistent, i.e., np→∞np\to\infty, then g(YA)g(Y_A) may be smaller than f(YA)f(Y_A) while having p^/p⇒1\hat{p}/p\Rightarrow1, but it should not be smaller than f(YA)/(np)f(Y_A)/(np): in this case we start from a consistent estimator (p^MC\hat{p}^{\mathrm{MC}}) and p^\hat{p} may remain consistent even if gg is worse than ff (i.e., puts less mass on AA);

  • but if p^MC\hat{p}^{\mathrm{MC}} is not consistent, i.e., np↛∞np\not\to\infty, then g(YA)g(Y_A) must typically be larger than f(YA)f(Y_A) by a factor 1/(np)1/(np) in order to ensure the consistency of p^\hat{p}: in this case, we start from a non-consistent estimator p^MC\hat{p}^{\mathrm{MC}} and provided gg puts more mass on AA, importance sampling can yield a consistent estimator.

A natural way to capture whether gg puts more mass on AA than ff or not is by considering the probability q:=P(X∈A)q:=\mathbb{P}(X\in A) of the rare event set AA under the auxiliary density gg. We note that nq→∞nq\to\infty is a necessary condition for the consistency of p^\hat{p} because the number of non-zero terms in (1) follows a binomial distribution with parameter (n,q)(n,q) so that if nq→c∈[0,∞)nq\to c\in[0,\infty), then P(p^=0)=(1−q)n→e−c>0\mathbb{P}(\hat{p}=0)=(1-q)^n\to e^{-c}>0 and we cannot have p^/p⇒1\hat{p}/p\Rightarrow1. Based on this simple consideration, the following lemma shows that if p^\hat{p} is more consistent than p^MC\hat{p}^{\mathrm{MC}}, then the probability qq can, to the very least, not be negligible compared to pp.

Lemma 5. If q≪pq \ll p, then p^\hat{p} is not more consistent than p^MC\hat{p}^{\mathrm{MC}}.

Proof. Assume that q≪pq \ll p and let n=1/pqn=1/\sqrt{pq}. Then np=p/q→∞np=\sqrt{p/q}\to\infty so that p^MC\hat{p}^{\mathrm{MC}} is consistent, while nq=q/p→0nq=\sqrt{q/p}\to0 so that p^\hat{p} is not consistent. □

On the other hand, the CD condition suggests to consider as auxiliary density a density close to the conditional density f∣Af|_A in the sense of the KL divergence: this is actually at the heart of the celebrated cross-entropy approach [14], which consists in choosing gg minimizing D(f∣A,g)D(f|_A,g) among a given family of auxiliary distributions. The next lemma exhibits a simple relation between qq and D(f∣A,g)D(f|_A,g) which implies that if gg is closer to f∣Af|_A than ff in the sense of the KL divergence, then necessarily q≥pq\geq p, i.e., AA has a larger probability under gg than under ff.

Lemma 6. We have q≥e−D(f∣A,g)q\geq e^{-D(f|_A,g)}. In particular:

  • if D(f∣A,g)≤D(f∣A,f)D(f|_A,g)\leq D(f|_A,f), then q≥pq\geq p;

  • if D(f∣A,g)≪D(f∣A,f)D(f|_A,g)\ll D(f|_A,f), then p^\hat{p} is more consistent than p^MC\hat{p}^{\mathrm{MC}}.

Proof. Let g∣A=gξA/qg|_A=g\xi_A/q be the density gg conditioned on AA. Since f∣Af|_A is assumed to be absolutely continuous with respect to gg, it is also absolutely continuous with respect to g∣Ag|_A and in particular, the two divergences D(f∣A,g∣A)D(f|_A,g|_A) and D(f∣A,g)D(f|_A,g) are well-defined. Moreover, since ξA(YA)=1\xi_A(Y_A)=1 a.s., we have g∣A(YA)=g(YA)/qg|_A(Y_A)=g(Y_A)/q which implies that

D(f∣A,g∣A)=E[log⁡(f∣A(YA)g∣A(YA))]=E[log⁡(qf∣A(YA)g(YA))]=log⁡q+D(f∣A,g).D(f|_A,g|_A)=\mathbb{E}\left[\log\left(\frac{f|_A(Y_A)}{g|_A(Y_A)}\right)\right]=\mathbb{E}\left[\log\left(\frac{qf|_A(Y_A)}{g(Y_A)}\right)\right]=\log q+D(f|_A,g).

Since D(f∣A,g∣A)≥0D(f|_A,g|_A)\geq0 this implies the desired first inequality q≥e−D(f∣A,g)q\geq e^{-D(f|_A,g)}. The inequality q≥pq\geq p then follows from the fact that f∣A(YA)=f(YA)/pf|_A(Y_A)=f(Y_A)/p a.s., so that D(f∣A,f)=−log⁡pD(f|_A,f)=-\log p. In particular, if D(f∣A,g)≤D(f∣A,f)D(f|_A,g)\leq D(f|_A,f), then e−D(f∣A,f)=p≤e−D(f∣A,g)≤qe^{-D(f|_A,f)}=p\leq e^{-D(f|_A,g)}\leq q.

To conclude, let us assume that D(f∣A,g)≪D(f∣A,f)D(f|_A,g)\ll D(f|_A,f): if p^MC\hat{p}^{\mathrm{MC}} is consistent, then n≫1/p=eD(f∣A,f)n\gg1/p=e^{D(f|_A,f)}: therefore, log⁡n≥D(f∣A,f)\log n\geq D(f|_A,f) for nn large enough, and so log⁡n≫D(f∣A,g)\log n\gg D(f|_A,g) which implies the consistency of p^\hat{p} by Lemma 3. □

We have seen that nq→∞nq\to\infty (i.e., the mean number of non-zero terms in the sum (1) defining p^\hat{p}) is a necessary condition for the consistency of p^\hat{p}. For the standard Monte Carlo estimator, this condition (which then reads np→∞np\to\infty) is also sufficient. A natural question is thus whether nq→∞nq\to\infty is also sufficient for consistency of p^\hat{p}: the next lemma, which is a direct consequence of Lemmas 4 and 6, shows that this is not necessarily the case.

Lemma 7. Assume that the fluctuations of the log-likelihood ratio around its mean are of the order of LL in the sense of Assumption 1, and that L‾∞\overline{L}_{\infty} is unbounded above. Then for n=eD(f∣A,g)+tn=e^{D(f|_A,g)+t} with 1≪t≪L1\ll t\ll L, p^\hat{p} is not consistent while nq→∞nq\to\infty.

Proof. For n=eD(f∣A,g)+tn=e^{D(f|_A,g)+t} with 1≪t≪L1\ll t\ll L, p^\hat{p} is not consistent by Lemma 4, while nq≥et→∞nq\geq e^t\to\infty by Lemma 6. □

Insight from the Gaussian setting

Some of the above ideas can be further explored in the Gaussian case where explicit expressions are available. So in this section, we assume that ff is the density of the standard Gaussian distribution N(0,I)\mathcal{N}(0,I), and we also consider gg a Gaussian density, with mean μ\mu and variance Σ\Sigma.

In this setting, an important auxiliary distribution is the optimal (in the sense of the KL divergence) Gaussian density gA=argmin⁡gD(f∣A,g)g_A = \operatorname*{argmin}_{g} D(f\mid_A,g) where the minimum runs over all Gaussian densities. It is well-known that gAg_A is the Gaussian density with mean μA:=E(YA)\mu_A := \mathbb{E}(Y_A) and covariance matrix ΣA:=Var⁡(YA)\Sigma_A := \operatorname{Var}(Y_A), see for instance [5, 14]. By construction, gAg_A decreases the KL divergence with f∣Af\mid_A and, based on the various results from the previous section, we expect it to improve the standard Monte Carlo estimator: we discuss some results quantifying this.

gAg_A puts more mass on AA

In the Gaussian setting it is well-known that

D(f∣A,gA)=−log⁡p−12L(ΣA)−12∥μA∥2(6)D(f\mid_A,g_A)=-\log p-\frac{1}{2}\mathcal{L}(\Sigma_A)-\frac{1}{2}\lVert\mu_A\rVert^2 \tag*{(6)}

where L(M)=tr⁡(M−I)−log⁡det⁡(M)≥0\mathcal{L}(M)=\operatorname{tr}(M-I)-\log\det(M)\ge0 is Stein’s loss between MM and the identity matrix II, which satisfies L(M)=0\mathcal{L}(M)=0 if and only if M=IM=I, see for instance [5 Lemma 3.5]. Combined with Lemma 6, this identity implies that, if X∼gAX\sim g_A,

P(X∈A)≥pe12L(ΣA)+12∥μA∥2.\mathbb{P}(X\in A)\ge p e^{\frac{1}{2}\mathcal{L}(\Sigma_A)+\frac{1}{2}\lVert\mu_A\rVert^2}.

Thus, gAg_A puts more mass on AA than ff, which is coherent with the intuition that gAg_A is a better auxiliary distribution than ff.

Hyperplane case: consistency improvement

By construction we have D(f∣A,gA)≤D(f∣A,f)D(f\mid_A,g_A)\le D(f\mid_A,f) (which is also readily visible on (6) since D(f∣A,f)=−log⁡pD(f\mid_A,f)=-\log p) but the improvement brought by gAg_A over ff is unclear. When inf⁡p>0\inf p>0, then D(f∣A,f)=−log⁡pD(f\mid_A,f)=-\log p is bounded and thus D(f∣A,gA)D(f\mid_A,g_A) also: therefore in this case, both estimators have the same consistency condition, namely n≫1n\gg1 by Lemma 3.

The case p→0p\to0 is much more challenging and, although this regime is at the heart of rare-event simulation, the consistency of p^\hat p for g=gAg=g_A does not seem to have been considered in the literature so far, even in the one-dimensional case d=1d=1. In this case the condition for consistency of the standard Monte Carlo estimator is n≫1/pn\gg1/p, and so a natural question is whether a suitable choice of gg may weaken this condition to n≫κn\gg\kappa for some κ≪1/p\kappa\ll1/p. The KL-based arguments of the previous section suggest that this will be the case if D(f∣A,gA)≪D(f∣A,f)D(f\mid_A,g_A)\ll D(f\mid_A,f): in view of (6), this requires a particular asymptotic behavior for L(ΣA)+∥μA∥2\mathcal{L}(\Sigma_A)+\lVert\mu_A\rVert^2, namely that L(ΣA)+∥μA∥2∼−2log⁡p\mathcal{L}(\Sigma_A)+\lVert\mu_A\rVert^2\sim-2\log p.

We do not know whether such an asymptotic relation holds for general sets AA and to get insight into this question, we consider the hyperplane case A={x:xTu≥α}A=\{x:x^{\mathsf{T}}u\ge\alpha\} with α→∞\alpha\to\infty and uu a sequence of dd-dimensional unit vectors (∥u∥=1\lVert u\rVert=1). This example may look quite specific, but it is justified for both theoretical and numerical reasons: from a theoretical perspective, it is a tractable case and from a numerical perspective, it is a standard test case considered in virtually any applied paper trying to assess the efficiency of some newly proposed importance sampling scheme, see for instance [3, 5, 17]. In this case, it is easy to see that

μA=muandΣA=I+(λ−1)uuTwith m=E(N∣N≥α) and λ=Var⁡(N∣N≥α)\mu_A = m u \quad\text{and} \quad\Sigma_A = I + (\lambda- 1)u u^{\mathsf{T}} \quad\text{with } m = \mathbb{E}(N \mid N \ge\alpha) \text{ and } \lambda= \operatorname{Var}(N \mid N \ge\alpha)

where here and in the sequel, N=YTuN = Y^{\mathsf{T}}u follows a standard, one-dimensional normal distribution. In particular, it follows that

D(f∣A,gA)=−log⁡p−12(λ−1−log⁡λ)−12m2.(7)D(f\mid_A,g_A) = -\log p - \frac{1}{2}(\lambda- 1 - \log\lambda) - \frac{1}{2}m^2. \tag*{(7)}

Careful asymptotic expansions for pp, λ\lambda and mm imply that D(f∣A,gA)D(f\mid_A,g_A) is bounded. More precisely, the following result holds.

Lemma 8. Consider the Gaussian setting and the hyperplane case A={x:xTu≥α}A = \{x : x^{\mathsf{T}}u \ge\alpha\} with α→∞\alpha\to\infty and uu a sequence of unit vectors. Then we have D(f∣A,gA)→12log⁡(2π/e)D(f\mid_A,g_A) \to\frac{1}{2}\log(2\pi/e). In particular, p^\hat{p} for g=gAg = g_A is consistent for any n≫1n \gg1.

This result therefore shows that, as far as consistency is concerned, gAg_A considerably improves the situation compared to the standard Monte Carlo estimator where the consistency condition is n≫1/pn \gg1/p. Whether such an improvement holds for general sets AA represents in our view an interesting open question.

Proof of Lemma 8. Using the Gaussian integration by parts formulas ∫α∞xke−x2/2 dx=αk−1e−α2/2+(k−1)∫α∞xk−2e−x2/2 dx\int_{\alpha}^{\infty} x^k e^{-x^2/2}\,dx = \alpha^{k-1}e^{-\alpha^2/2} + (k-1)\int_{\alpha}^{\infty}x^{k-2}e^{-x^2/2}\,dx for k=1,2k=1,2, we get

m=E(N∣N≥α)=1p∫α∞x2πe−x2/2 dx=e−α2/2p2π(8)m = \mathbb{E}(N\mid N\ge\alpha) = \frac{1}{p}\int_{\alpha}^{\infty}\frac{x}{\sqrt{2\pi}}e^{-x^2/2}\,dx = \frac{e^{-\alpha^2/2}}{p\sqrt{2\pi}} \tag*{(8)}

and

E(N2∣N≥α)=1p∫α∞x22πe−x2/2 dx=1p2π(αe−α2/2+∫α∞e−x2/2 dx)=αm+1\mathbb{E}(N^2\mid N\ge\alpha) = \frac{1}{p}\int_{\alpha}^{\infty}\frac{x^2}{\sqrt{2\pi}}e^{-x^2/2}\,dx = \frac{1}{p\sqrt{2\pi}}\left(\alpha e^{-\alpha^2/2}+\int_{\alpha}^{\infty}e^{-x^2/2}\,dx\right)=\alpha m+1

so that

λ=E(N2∣N≥α)−m2=αm+1−m2.(9)\lambda= \mathbb{E}(N^2\mid N\ge\alpha)-m^2=\alpha m+1-m^2. \tag*{(9)}

Thus, everything gets expressed in terms of pp, whose asymptotic expansion is well-known. Actually, to get the leading term in D(f∣A,gA)D(f\mid_A,g_A), we need to consider the following expansion:

p=e−α2/22π(1α−1α3+3α5+o(α−6)).(10)p=\frac{e^{-\alpha^2/2}}{\sqrt{2\pi}}\left(\frac{1}{\alpha}-\frac{1}{\alpha^3}+\frac{3}{\alpha^5}+o(\alpha^{-6})\right). \tag*{(10)}

From this expansion we readily get −log⁡p=α22+log⁡α+12log⁡(2π)+o(1)-\log p=\frac{\alpha^2}{2}+\log\alpha+\frac{1}{2}\log(2\pi)+o(1), while getting the expansions for the terms λ\lambda, log⁡λ\log\lambda and m2m^2 appearing in (7) is more involved. Starting from the asymptotic expansion (10) of pp and the expressions (8) and (9) of mm and λ\lambda in terms of pp, computation detailed below shows that

λ=o(1),log⁡λ=−2log⁡α+o(1)andm2=α2+2+o(1).\lambda=o(1),\quad\log\lambda=-2\log\alpha+o(1)\quad\text{and}\quad m^2=\alpha^2+2+o(1).

Plugging these expressions into (7), we obtain

D(f∣A,gA)=α22+log⁡α+12log⁡(2π)+12−log⁡α−12α2−1+o(1)=12log⁡(2π/e)+o(1)D(f\mid_A,g_A)=\frac{\alpha^2}{2}+\log\alpha+\frac{1}{2}\log(2\pi)+\frac{1}{2}-\log\alpha-\frac{1}{2}\alpha^2-1+o(1)=\frac{1}{2}\log(2\pi/e)+o(1)

which is precisely the result announced. Let us now detail the computation for mm, λ\lambda and log⁡λ\log\lambda. Combining (8) and (10) gives m=α(1−α−2+3α−4+o(α−5))−1m=\alpha(1-\alpha^{-2}+3\alpha^{-4}+o(\alpha^{-5}))^{-1} and so using (1−ε)−1=1+ε+ε2+ε3+o(ε3)(1-\varepsilon)^{-1}=1+\varepsilon+\varepsilon^2+\varepsilon^3+o(\varepsilon^3) with ε=α−2−3α−4+o(α−5)\varepsilon=\alpha^{-2}-3\alpha^{-4}+o(\alpha^{-5}) we obtain

m=α(1+(α−2−3α−4)+(α−2−3α−4)2+(α−2−3α−4)3+o(α−5))=α(1+α−2−3α−4+α−4+o(α−5))\begin{aligned} m=\alpha\left(1+(\alpha^{-2}-3\alpha^{-4})+(\alpha^{-2}-3\alpha^{-4})^2+(\alpha^{-2}-3\alpha^{-4})^3+o(\alpha^{-5})\right) \\ &=\alpha\left(1+\alpha^{-2}-3\alpha^{-4}+\alpha^{-4}+o(\alpha^{-5})\right) \end{aligned}

and so m=α+α−1−2α−3+o(α−4)m=\alpha+\alpha^{-1}-2\alpha^{-3}+o(\alpha^{-4}). This allows to get the required expansion for m2m^2:

m2=α2(1+α−2−2α−4+o(α−5))2=α2(1+2α−2−4α−4+α−4+o(α−5))m^2=\alpha^2\left(1+\alpha^{-2}-2\alpha^{-4}+o(\alpha^{-5})\right)^2=\alpha^2\left(1+2\alpha^{-2}-4\alpha^{-4}+\alpha^{-4}+o(\alpha^{-5})\right)

which gives m2=α2+2−3α−2+o(α−3)m^2=\alpha^2+2-3\alpha^{-2}+o(\alpha^{-3}). Plugging in the previous expressions for mm and m2m^2 into the expression λ=αm+1−m2\lambda=\alpha m+1-m^2 of (9), we get

λ=α2+1−2α−2+1−α2−2+3α−2+o(α−3)=α−2+o(α−3).\lambda=\alpha^2+1-2\alpha^{-2}+1-\alpha^2-2+3\alpha^{-2}+o(\alpha^{-3})=\alpha^{-2}+o(\alpha^{-3}).

This finally allows to get the expansion log⁡λ=−2log⁡α+o(1)\log\lambda=-2\log\alpha+o(1) which achieves the proof. □

In practice, gAg_A is usually out of reach because the parameters mm, λ\lambda and uu are unknown. For this reason, modern algorithms resort to adaptive importance sampling [4, 7, 13, 14, 18] whereby these unknown parameters are first estimated in a preliminary step. This typically leads to considering auxiliary densities with mean μ\mu and variance Σ\Sigma given by

μ=γvandΣ=I+(κ−1)vvTwith γ∈R, κ>0 and v∈Rd with ∥v∥=1.(11)\mu=\gamma v \quad\text{and}\quad\Sigma=I+(\kappa-1)vv^{\mathsf{T}}\quad\text{with }\gamma\in\mathbb{R},\ \kappa>0\text{ and }v\in\mathbb{R}^{d}\text{ with }\lVert v\rVert=1. \tag*{(11)}

In recent algorithms, γ\gamma, κ\kappa and vv are estimations of the true parameters mm, λ\lambda and uu. Thus, it is interesting to study how the errors made in estimating these parameters propagates in the KL divergence: again, explicit formulas are available in the Gaussian setting and in the hyperplane case.

Lemma 9. Consider the Gaussian setting with gg the Gaussian density with mean μ\mu and variance Σ\Sigma given by (11), and consider also the hyperplane case A={x:xTu≥α}A=\{x:x^{\mathsf{T}}u\ge\alpha\} with α→∞\alpha\to\infty and uu a sequence of unit vectors. Then we have

D(f∣A,g)=D(f∣A,gA)+12L(Σ−1ΣA)+12(μ−μA)TΣ−1(μ−μA)(12)D(f\mid_A,g)=D(f\mid_A,g_A)+\frac{1}{2}\mathcal{L}(\Sigma^{-1}\Sigma_A)+\frac{1}{2}(\mu-\mu_A)^{\mathsf{T}}\Sigma^{-1}(\mu-\mu_A) \tag*{(12)}

with

L(Σ−1ΣA)=(1−⟨u,v⟩2)(1−λ)(κ−1−1)+λκ−1−1−log⁡(λκ−1)(13)\mathcal{L}(\Sigma^{-1}\Sigma_A)=(1-\langle u,v\rangle^2)(1-\lambda)(\kappa^{-1}-1)+\lambda\kappa^{-1}-1-\log(\lambda\kappa^{-1}) \tag*{(13)}

and

(μ−μA)TΣ−1(μ−μA)=κ−1(γ−m⟨u,v⟩)2+m2(1−⟨u,v⟩2).(14)(\mu-\mu_A)^{\mathsf{T}}\Sigma^{-1}(\mu-\mu_A)=\kappa^{-1}\left(\gamma-m\langle u,v\rangle\right)^2+m^2\left(1-\langle u,v\rangle^2\right). \tag*{(14)}

These expressions allow to recover the fact that D(f∣A,g)D(f\mid_A,g) will be small if Σ\Sigma is close to ΣA\Sigma_A and μ\mu to μA\mu_A, but they give precise quantifications to the extent to which we must have ⟨u,v⟩≈1\langle u,v\rangle\approx1, κ≈λ\kappa\approx\lambda and γ≈m\gamma\approx m. The value of the scalar product ⟨u,v⟩\langle u,v\rangle seems particularly important as if we do not have ⟨u,v⟩→1\langle u,v\rangle\to1, then we necessarily have D(f∣A,g)→∞D(f\mid_A,g)\to\infty.

Proof of Lemma 9. The relation (12) is well-known, see for instance [5 Lemma 3.5]. Since ΣA=I+(λ−1)uuT\Sigma_A = I + (\lambda- 1)uu^{\mathsf{T}} and Σ=I+(κ−1)vvT\Sigma= I + (\kappa- 1)vv^{\mathsf{T}}, we get Σ−1=I+(κ−1−1)vvT\Sigma^{-1} = I + (\kappa^{-1} - 1)vv^{\mathsf{T}} and so

Σ−1ΣA=I+(κ−1−1)vvT+(λ−1)uuT+(κ−1−1)(λ−1)(vTu)vuT.\Sigma^{-1}\Sigma_A = I + (\kappa^{-1} - 1)vv^{\mathsf{T}} + (\lambda- 1)uu^{\mathsf{T}} + (\kappa^{-1} - 1)(\lambda- 1)(v^{\mathsf{T}}u)vu^{\mathsf{T}}.

In particular, tr⁡(Σ−1ΣA−I)=κ−1−1+λ−1+(κ−1−1)(λ−1)⟨u,v⟩2\operatorname{tr}(\Sigma^{-1}\Sigma_A - I) = \kappa^{-1} - 1 + \lambda- 1 + (\kappa^{-1} - 1)(\lambda- 1)\langle u,v\rangle^2 and since det⁡(Σ−1ΣA)=λ/κ\det(\Sigma^{-1}\Sigma_A) = \lambda/\kappa, we get

L(Σ−1ΣA)=κ−1−1+λ−1+(κ−1−1)(λ−1)⟨u,v⟩2−log⁡(λ/κ)\mathcal{L}(\Sigma^{-1}\Sigma_A) = \kappa^{-1} - 1 + \lambda- 1 + (\kappa^{-1} - 1)(\lambda- 1)\langle u,v\rangle^2 - \log(\lambda/\kappa)

which can be rearranged to get (13). For the quadratic term, we have

(μ−μA)TΣ−1(μ−μA)=(γv−mu)T(I+(κ−1−1)vvT)(γv−mu)(\mu-\mu_A)^{\mathsf{T}}\Sigma^{-1}(\mu-\mu_A) = (\gamma v-mu)^{\mathsf{T}}\left(I+(\kappa^{-1}-1)vv^{\mathsf{T}}\right)(\gamma v-mu)

from which (14) can be derived by standard algebraic manipulation.

Opening discussion: does gAg_A improve the speed of convergence?

Although we have seen that p^\widehat{p} may significantly improve consistency compared to the standard Monte Carlo estimator p^MC\widehat{p}^{\mathrm{MC}}, it seems to us that an important, essentially open question is the following: when both estimators are consistent (e.g., if p^\widehat{p} is more consistent than p^MC\widehat{p}^{\mathrm{MC}} and np→∞np\to\infty), does p^\widehat{p} converge faster than p^MC\widehat{p}^{\mathrm{MC}}? Since

ζ(p^p−1)=∑i=1nZiwithZi=ζn(ℓA(Xi)−1),\zeta\left(\frac{\widehat{p}}{p}-1\right)=\sum_{i=1}^{n}Z_i \quad\text{with} \quad Z_i=\frac{\zeta}{n}\bigl(\ell_A(X_i)-1\bigr),

determining the speed of convergence (i.e., the scaling parameters ζ\zeta that makes this sum converge) boils down to studying a triangular sum of i.i.d. random variables as in Theorem 1. However, the arguments in the proof of Theorem 1 do not allow us to identify a simple condition for convergence.

In order to get insight into this question, we turn into looking at the moments E[ℓA(X)1+η]=E[ℓA(YA)η]\mathbb{E}[\ell_A(X)^{1+\eta}] = \mathbb{E}[\ell_A(Y_A)^\eta] of the summands, which are meant to give indication on their tail behavior and thus, ultimately, on the behavior of their sum. In general, moments of ℓA(X)\ell_A(X) are difficult to study because of the indicator function of the set AA which, in principle, prohibits general explicit expressions. For these reasons, moments of ℓA(YA)\ell_A(Y_A) are often controlled by neglecting the indicator function through the bound

E[ℓA(YA)η]≤1pη+1E[ℓ(Y)η].(15)\mathbb{E}[\ell_A(Y_A)^\eta] \le\frac{1}{p^{\eta+1}}\mathbb{E}[\ell(Y)^\eta]. \tag*{(15)}

This bound is insightful when inf⁡p>0\inf p > 0, but is extremely rough when p→0p\to0: however, as mentioned above, what happens in this case is essentially unknown.

In the Gaussian setting, the next lemma shows that explicit expressions, which allow to capture the dependency on AA, are available for small enough moments. Moreover, this result allows to precisely evaluate the gap in (15). Here and in the sequel, we consider again the Gaussian setting of Section 3 and we define μˉ=Σ−1μ\bar{\mu}=\Sigma^{-1}\mu and Δ=Σ−1−I\Delta=\Sigma^{-1}-I.

Lemma 10. Consider the Gaussian setting of § 3 and η>0\eta> 0. If η(∥Σ−1∥op−1)<1\eta(\lVert\Sigma^{-1}\rVert_{\mathrm{op}}-1)<1, then it holds that

E[ℓA(YA)η]=1pη+1E[ℓ(Y)η]×P((I−ηΔ)−1/2Y−η(I−ηΔ)−1μˉ∈A)(16)\mathbb{E}[\ell_A(Y_A)^\eta]=\frac{1}{p^{\eta+1}}\mathbb{E}[\ell(Y)^\eta]\times\mathbb{P}\left((I-\eta\Delta)^{-1/2}Y-\eta(I-\eta\Delta)^{-1}\bar{\mu}\in A\right) \tag*{(16)}

where

E[ℓ(Y)η]=exp⁡(ηD(f,g)+12L(I−ηΔ)+η22μˉT(I−ηΔ)−1μˉ).(17)\mathbb{E}[\ell(Y)^\eta]=\exp\left(\eta D(f,g)+\frac{1}{2}\mathcal{L}(I-\eta\Delta)+\frac{\eta^2}{2}\bar{\mu}^{\mathsf{T}}(I-\eta\Delta)^{-1}\bar{\mu}\right). \tag*{(17)}

Moreover, E[ℓ(Y)η]=∞\mathbb{E}[\ell(Y)^\eta]=\infty if η(∥Σ−1∥op−1)>1\eta(\lVert\Sigma^{-1}\rVert_{\mathrm{op}}-1)>1.

Proof. We have E[ℓ(Y)η]=∫fη+1/gη\mathbb{E}[\ell(Y)^\eta]=\int f^{\eta+1}/g^\eta and, starting from the expressions of ff and gg, one can express the ratio fη+1/gηf^{\eta+1}/g^\eta as

f(y)η+1g(y)η=(2π)−d/2[det⁡(Σ)]η/2exp⁡(1+η2(yT(I−δΣ−1)y+2δyTΣ−1μ−δμTΣ−1μ))\frac{f(y)^{\eta+1}}{g(y)^\eta}=(2\pi)^{-d/2}[\det(\Sigma)]^{\eta/2}\exp\left(\frac{1+\eta}{2}\left(y^{\mathsf{T}}(I-\delta\Sigma^{-1})y+2\delta y^{\mathsf{T}}\Sigma^{-1}\mu-\delta\mu^{\mathsf{T}}\Sigma^{-1}\mu\right)\right)

with δ=η/(1+η)\delta=\eta/(1+\eta). This shows that fη+1/gηf^{\eta+1}/g^\eta will be integrable if λmin⁡(I−δΣ−1)>0\lambda_{\min}(I-\delta\Sigma^{-1})>0, and not integrable if λmin⁡(I−δΣ−1)<0\lambda_{\min}(I-\delta\Sigma^{-1})<0. Since λmin⁡(I−δΣ−1)=11+η(1−η(∥Σ−1∥op−1))\lambda_{\min}(I-\delta\Sigma^{-1})=\frac{1}{1+\eta}(1-\eta(\lVert\Sigma^{-1}\rVert_{\mathrm{op}}-1)) this shows that ℓ(Y)η\ell(Y)^\eta is integrable if η(∥Σ−1∥op−1)<1\eta(\lVert\Sigma^{-1}\rVert_{\mathrm{op}}-1)<1 and not integrable if η(∥Σ−1∥op−1)>1\eta(\lVert\Sigma^{-1}\rVert_{\mathrm{op}}-1)>1. Let us now assume that η(∥Σ−1∥op−1)<1\eta(\lVert\Sigma^{-1}\rVert_{\mathrm{op}}-1)<1 and proceed with establishing (17) and (16). Let in the sequel V=(I−δΣ−1)−1V=(I-\delta\Sigma^{-1})^{-1} and z=δμˉz=\delta\bar{\mu}: then we have

yT(I−δΣ−1)y+2δyTΣ−1μ−δμTΣ−1μ=(y+Vz)TV−1(y+Vz)−zTVz−δμTΣ−1μy^{\mathsf{T}}(I-\delta\Sigma^{-1})y+2\delta y^{\mathsf{T}}\Sigma^{-1}\mu-\delta\mu^{\mathsf{T}}\Sigma^{-1}\mu=(y+Vz)^{\mathsf{T}}V^{-1}(y+Vz)-z^{\mathsf{T}}Vz-\delta\mu^{\mathsf{T}}\Sigma^{-1}\mu

so that

f(y)η+1g(y)η=[det⁡(Σ)]η/2exp⁡(1+η2(zTVz+δμTΣ−1μ))[det⁡(V/(1+η))]1/2h(y)\frac{f(y)^{\eta+1}}{g(y)^\eta}=[\det(\Sigma)]^{\eta/2}\exp\left(\frac{1+\eta}{2}\left(z^{\mathsf{T}}Vz+\delta\mu^{\mathsf{T}}\Sigma^{-1}\mu\right)\right)[\det(V/(1+\eta))]^{1/2}h(y)

with hh the Gaussian density with variance V/(1+η)=(I−ηΔ)−1V/(1+\eta)=(I-\eta\Delta)^{-1} and mean −Vz=−η(I−ηΔ)−1μˉ-Vz=-\eta(I-\eta\Delta)^{-1}\bar{\mu}. Integrating this identity implies that

E[ℓ(Y)η]=[det⁡(Σ)]η/2exp⁡(1+η2(zTVz+δμTΣ−1μ))[det⁡(V/(1+η))]1/2\mathbb{E}[\ell(Y)^\eta]=[\det(\Sigma)]^{\eta/2}\exp\left(\frac{1+\eta}{2}\left(z^{\mathsf{T}}Vz+\delta\mu^{\mathsf{T}}\Sigma^{-1}\mu\right)\right)[\det(V/(1+\eta))]^{1/2}

as well as (16) since E[ℓA(YA)η]=1pη+1∫Afη+1/gη\mathbb{E}[\ell_A(Y_A)^\eta]=\frac{1}{p^{\eta+1}}\int_A f^{\eta+1}/g^\eta. Therefore, in order to conclude the proof it remains to prove (17), i.e., in view of the above, that

η2log⁡det⁡(Σ)−12log⁡det⁡(I−ηΔ)+1+η2(zTVz+δμTΣ−1μ)=ηD(f,g)+12L(I−ηΔ)+η22μˉT(I−ηΔ)−1μˉ.\frac{\eta}{2}\log\det(\Sigma)-\frac{1}{2}\log\det(I-\eta\Delta)+\frac{1+\eta}{2}\left(z^{\mathsf{T}}Vz+\delta\mu^{\mathsf{T}}\Sigma^{-1}\mu\right) =\eta D(f,g)+\frac{1}{2}\mathcal{L}(I-\eta\Delta)+\frac{\eta^2}{2}\bar{\mu}^{\mathsf{T}}(I-\eta\Delta)^{-1}\bar{\mu}.

This relation is easily established recalling that D(f,g)=12L(Σ−1)+12μˉTΣ−1μˉD(f,g)=\frac{1}{2}\mathcal{L}(\Sigma^{-1})+\frac{1}{2}\bar{\mu}^{\mathsf{T}}\Sigma^{-1}\bar{\mu} and L(M)=tr⁡(M−I)−log⁡det⁡(M)\mathcal{L}(M)=\operatorname{tr}(M-I)-\log\det(M).

Of course, depending on the set AA, we may have E[ℓA(YA)η]<∞\mathbb{E}[\ell_A(Y_A)^\eta]<\infty even if E[ℓ(Y)η]=∞\mathbb{E}[\ell(Y)^\eta]=\infty: for instance, consider η(∥Σ−1∥op−1)>1\eta(\lVert\Sigma^{-1}\rVert_{\mathrm{op}}-1)>1, so that E[ℓ(Y)η]=∞\mathbb{E}[\ell(Y)^\eta]=\infty by the previous lemma, but A={x:∥x∥≤1}A=\{x:\lVert x\rVert\leq1\} in which case ℓA\ell_A is bounded and so ℓA(YA)\ell_A(Y_A) has finite moments of all order. An inspection of the proof of Lemma 10 reveals that what happens is that E[ℓA(YA)η]∝∫ξA(y)e−Qη(y) dy\mathbb{E}[\ell_A(Y_A)^\eta] \propto\int\xi_A(y)e^{-Q_\eta(y)}\,\mathrm{d}y with QηQ_\eta a symmetric quadratic form. The condition η(∥Σ−1∥op−1)<1\eta(\lVert\Sigma^{-1}\rVert_{\mathrm{op}}-1)<1 ensures that QηQ_\eta is positive, which makes e−Qηe^{-Q_\eta} (and thus ξAe−Qη\xi_Ae^{-Q_\eta}) integrable. If η(∥Σ−1∥op−1)>1\eta(\lVert\Sigma^{-1}\rVert_{\mathrm{op}}-1)>1 then QηQ_\eta has negative eigenvalues, which makes e−Qηe^{-Q_\eta} not integrable since it diverges in the directions of the eigenvectors associated to the negative eigenvalues. However, this diverging behavior could be compensated by the indicator function ξA\xi_A: for instance, one can easily build Q=−uuT+Q+Q=-uu^\mathsf{T}+Q_+ with Q+Q_+ positive, such that e−Qe^{-Q} is not integrable while ξAe−Q\xi_Ae^{-Q} with A={x:∣uTx∣≤1}A=\{x:|u^\mathsf{T}x|\leq1\} is integrable.

However, the hyperplane case suggests that such a “cooperative” interplay between AA and gg may not necessarily be the case: indeed, in this case the indicator function does not change the tail behavior and so the condition for the existence of moments of ℓA(YA)\ell_A(Y_A) is the same as for ℓ(Y)\ell(Y).

Lemma 11. Consider the Gaussian setting of Section 3 with g=gAg=g_A, and the hyperplane case A={x:xTu≥α}A=\{x:x^\mathsf{T}u\geq\alpha\} with uu a unit vector and α∈R\alpha\in\mathbb{R}. For η>0\eta>0, we have E[ℓA(YA)η]<∞\mathbb{E}[\ell_A(Y_A)^\eta]<\infty if η(1/λ−1)<1\eta(1/\lambda-1)<1 and E[ℓA(YA)η]=∞\mathbb{E}[\ell_A(Y_A)^\eta]=\infty if η(1/λ−1)>1\eta(1/\lambda-1)>1.

This result is puzzling as, in the hyperplane case, we have λ→0\lambda\to0 when α→∞\alpha\to\infty: therefore, although g=gAg=g_A is a very good choice for consistency (cf. Lemma 8), it seems extremely bad in terms of tail behavior as ℓA(YA)\ell_A(Y_A) for g=gAg=g_A has very few moments (up to λ∼α−2\lambda\sim\alpha^{-2}) while the Monte Carlo estimator has all moments, since ℓA(YA)=1/p\ell_A(Y_A)=1/p for g=fg=f. Based on these considerations, and given that the hyperplane is usually a favorable test case, we conjecture that, although gAg_A dramatically improves consistency, in the regime np→∞np\to\infty where both p^MC\widehat{p}^{\mathrm{MC}} and p^\widehat{p} with g=gAg=g_A converge, then convergence may occur faster for p^MC\widehat{p}^{\mathrm{MC}} than for p^\widehat{p}.

References

  1. [1]Sergios Agapiou, Omiros Papaspiliopoulos, Daniel Sanz-Alonso, and Andrew M. Stuart, Importance sampling: intrinsic dimension and computational cost, Statist. Sci. 32 (2017), no. 3, 405–431.arxiv.org/abs/1511.06196
  2. [2]Søren Asmussen and Peter W. Glynn, Stochastic simulation: algorithms and analysis, Stochastic Modelling and Applied Probability, vol. 57, Springer, New York, 2007.DOI
  3. [3]Siu-Kui Au and James L. Beck, Importance sampling in high dimensions, Struct. Saf. 25 (2003), no. 2, 139–163.
  4. [4]Jason Beh, Jerome Morio, and Florian Simatos, Phase transition for conditional covariance matrices estimated by importance sampling, and implications for cross-entropy schemes in high dimension, 2025, Preprint, arXiv:2511.11351.arxiv.org/abs/2511.11351
  5. [5]Jason Beh, Yonatan Shadmi, and Florian Simatos, Insight from the Kullback–Leibler divergence into adaptive importance sampling schemes for rare event analysis in high dimension, Ann. Appl. Probab. 35 (2025), no. 2, 1083–1124.arxiv.org/abs/2309.16828
  6. [6]Thomas Bengtsson, Peter Bickel, and Bo Li, Curse-of-dimensionality revisited: collapse of the particle filter in very large scale systems, Probability and statistics: essays in honor of David A. Freedman, Inst. Math. Stat. Collect., vol. 2, Inst. Math. Statist., Beachwood, OH, 2008, pp. 316–334.DOI
  7. [7]Mónica F. Bugallo, Víctor Elvira, Luca Martino, David Luengo, Joaquín Míguez, and Petar M. Djurić, Adaptive importance sampling: the past, the present, and the future, IEEE Signal Process. Mag. 34 (2017), no. 4, 60–79.DOI
  8. [8]Sourav Chatterjee and Persi Diaconis, The sample size required in importance sampling, Ann. Appl. Probab. 28 (2018), no. 2, 1099–1135.arxiv.org/abs/1511.01437
  9. [9]Víctor Elvira and Luca Martino, Advances in importance sampling, Wiley StatsRef: Statistics Reference Online, Wiley, 2021.DOI
  10. [10]Paul Glasserman and Yashan Wang, Counterexamples in importance sampling for large deviations probabilities, Ann. Appl. Probab. 7 (1997), no. 3, 731–746.DOI
  11. [11]Jean Jacod and Albert N. Shiryaev, Limit theorems for stochastic processes, second ed., Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 288, Springer-Verlag, Berlin, 2003. MR MR1943877 (2003j:60001)
  12. [12]Pierre L’Ecuyer, Jose H. Blanchet, Bruno Tuffin, and Peter W. Glynn, Asymptotic robustness of estimators in rare-event simulation, ACM Trans. Model. Comput. Simul. 20 (2010), no. 1, Article 6.
  13. [13]Jason Papaioannou, Sebastian Geyer, and Daniel Straub, Improved cross entropy-based importance sampling with a flexible mixture model, Reliab. Eng. Syst. Saf. 191 (2019), 106564.DOI
  14. [14]Reuven Y. Rubinstein and Dirk P. Kroese, The cross-entropy method: a unified approach to combinatorial optimization, Monte-Carlo simulation and machine learning, Information Science and Statistics, Springer-Verlag, New York, 2004.
  15. [15]John S. Sadowsky and James A. Bucklew, On large deviations theory and asymptotically efficient Monte Carlo estimation, IEEE Trans. Inform. Theory 36 (1990), no. 3, 579–588.
  16. [16]Daniel Sanz-Alonso, Importance sampling and necessary sample size: an information theory approach, SIAM/ASA J. Uncertain. Quantif. 6 (2018), no. 2, 867–879.
  17. [17]Armin Tabandeh, Gaofeng Jia, and Paolo Gardoni, A review and assessment of importance sampling methods for reliability analysis, Struct. Saf. 97 (2022), 102216.DOI
  18. [18]Felipe Uribe, Jason Papaioannou, Youssef M. Marzouk, and Daniel Straub, Cross-entropy-based importance sampling with failure-informed dimension reduction for rare event simulation, SIAM/ASA J. Uncertain. Quantif. 9 (2021), no. 2, 818–847.arxiv.org/abs/2006.05496

Paper details

vlnc:W_p7fbmc8j
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents