WorksMathematics
Consistency considerations for rare-event importance sampling
Abstract
We consider the problem of estimating a small probability by importance sampling with auxiliary density , where is drawn according to some density . We establish a simple necessary and sufficient condition for the consistency of the importance sampling estimator in triangular schemes where the dimension, the densities and and the set 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 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 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 be a random variable which is absolutely continuous with respect to Lebesgue measure with density (which we write ) and measurable so that is integrable. Importance sampling is a widely used simulation technique [2, 9] to estimate from samples from another distribution with density , called auxiliary distribution. The idea is simply to change measure to rewrite with and the likelihood ratio between and , and then estimate by standard Monte Carlo with an i.i.d. sample drawn according to .
In this paper we are more specifically interested in the reliability context where one seeks to estimate a (small) probability : this corresponds to the case where , the indicator function of the set , and the corresponding importance sampling estimator is then given by
Note that for this estimator to be well defined with the usual convention , one needs to be absolutely continuous with respect to , i.e., . The conditional distribution is called the zero-variance auxiliary distribution since when . When is small, controlling the absolute error is not necessarily insightful, and one rather turns to the relative estimator , leading to considering
The previous display shows that can be seen as the empirical mean of the likelihood ratios : thus, the key object of interest is the likelihood ratio between the conditional distribution and the auxiliary distribution , rather than the original likelihood ratio between and $g.
Since , the law of large numbers readily entails that, for fixed problem parameters , , and , we have almost surely as . However, there are different reasons for considering triangular schemes where, for instance, and/or are not fixed. In reliability for instance, one is interested in estimating small probabilities, motivating the study of in the regime . Moreover, there has recently been a surge of interest for high-dimensional importance sampling schemes [1, 3, 5, 18], corresponding to the regime . In such cases, we are in a triangular setting where the law of the summands 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 is classically handled by requiring the relative second moment to remain bounded (bounded relative error) or to satisfy (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 , 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 , i.e., on the minimal sample size ensuring .
Triangular setting
To formalize this, we consider in the rest of the paper a sequence of problems where for each , is the problem dimension, is measurable and and are -dimensional densities such that is absolutely continuous with respect to . Moreover, we define , . To avoid cumbersome notation, the dependency on is omitted from the notation, but every limiting regime, supremum or infimum is taken with respect to : for instance, means that as , , etc. For simplicity, we will say in the sequel that is consistent if with referring to convergence in distribution. Note that since the dimension may evolve (e.g., in the high-dimensional regime ), 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 is a square matrix, denotes its operator norm, its determinant and its trace. If is further symmetric, and denote its smallest and largest eigenvalue, respectively. Note that if is symmetric definite positive, then and . Furthermore, with , and as introduced in § 1.2, and denote random variables with density and and denote random variables with density and , respectively. Moreover, for positive, deterministic sequences and , we will write or to mean that , or equivalently, .
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 is necessary and sufficient for accurate estimation by importance sampling, where is the Kullback–Leibler (KL) divergence between and , which exists provided that is absolutely continuous with respect to . In the sequel, we will refer for short to as the CD condition. Actually, although Chatterjee and Diaconis only mention the threshold in their abstract, their results are more precise. Indeed, [8 Theorem 1.3] states that for any and ,
and
Roughly speaking, 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 is larger than these fluctuations, then will be consistent for and not consistent for . To formalize this, we will sometimes consider the following assumption.
Assumption 1. Let be a sequence of deterministic, positive numbers growing to . We say that the fluctuations of the log-likelihood ratio around its mean are of the order of if and if there exists a finite random variable such that , where
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 in the sense of Assumption 1, and let : then is consistent if and not consistent if .
Therefore, the CD approach leaves open the consistency of in the range between and : actually, there is a simple necessary and sufficient condition which allows to close this gap.
Theorem 1. if and only if .
Proof. Let , so that is a (triangular) sum of i.i.d. random variables. Since , we have and so the triangular array is, in the language of [11 Definition VII.2.33], infinitesimal. Therefore, according to [11 Theorem VII.2.35], we have if and only if there exists a truncation function , i.e., a bounded function equal to the identity function in a neighborhood of , such that the following three conditions hold:
;
;
for all bounded, continuous functions which are around .
In this case, and hold for all truncation functions. Let us assume that and let us prove that . We use repeatedly the change of measure formula for any measurable, positive function . In particular, for any we have
with the truncation function . Since , we have by giving as desired.
Let us now assume that , and let us prove that , i.e., that , and hold for for some . For this is the same argument as above, since . Let us now prove . Since , we have and so we only have to prove that . Changing measure gives
Since by assumption and is bounded, we get . Let us now prove . Since it is enough to prove that . We have
with which, by assumption, converges in distribution to . In particular, and since is bounded by , the bounded convergence theorem implies that which gives the desired result.
Thanks to Theorem 1, the gap between the CD condition and the consistency of can be understood: on the one hand, so that if and only if , while on the other hand, Theorem 1 states that if and only if : thus, the difference between the CD condition and the consistency of lies in the potential discrepancy between the convergence in distribution and in the mean of the normalized log-likelihood ratio . Because 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:
with and . For the record we state the following lemma which stems from the convexity inequality .
Lemma 2. We have .
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 , then is consistent. In particular, if , then is consistent for any .
Proof. Assume that , i.e., . By (5) we have
and since this implies that . Since this yields which eventually implies that . Since is tight (it is positive and its mean is bounded by 1 by Lemma 2), this implies that , i.e., and so we can conclude with Theorem 1.
Of course, this result is far from being sharp as it settles the question in the regime with whereas the action takes place for : 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 .
Lemma 4. Assume that the fluctuations of the log-likelihood ratio around its mean are of the order of in the sense of Assumption 1 and let for some : then is consistent if and not consistent if . In particular, if is unbounded above (i.e., for every ), then is consistent if and only if for some .
Proof. Assume that Assumption 1 holds and let for some : the question is whether or not. Let and two continuity points of : since with and , we have for large enough and so letting first and then and we obtain
which proves the desired result. Assume now that is unbounded above. Then the previous argument readily implies that is consistent if for some . If not, then by working along a subsequence we have and along this subsequence, the previous arguments imply that , so that is not consistent by Theorem 1.
Comparison to the standard Monte Carlo estimator
Let with the ’s i.i.d. be the standard Monte Carlo estimator of : 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 to imply that of . When this occurs, i.e. consistent implies consistent, we say that the importance sampling estimator is more consistent than the standard Monte Carlo estimator . Theorem 1 can help shed light on this question.
First, note that since almost surely (a.s.) when , Theorem 1 readily entails that if and only if . Next, since a.s., we have
By Theorem 1 we need this probability to vanish to have consistent, and we can distinguish two cases:
if is consistent, i.e., , then may be smaller than while having , but it should not be smaller than : in this case we start from a consistent estimator () and may remain consistent even if is worse than (i.e., puts less mass on );
but if is not consistent, i.e., , then must typically be larger than by a factor in order to ensure the consistency of : in this case, we start from a non-consistent estimator and provided puts more mass on , importance sampling can yield a consistent estimator.
A natural way to capture whether puts more mass on than or not is by considering the probability of the rare event set under the auxiliary density . We note that is a necessary condition for the consistency of because the number of non-zero terms in (1) follows a binomial distribution with parameter so that if , then and we cannot have . Based on this simple consideration, the following lemma shows that if is more consistent than , then the probability can, to the very least, not be negligible compared to .
Lemma 5. If , then is not more consistent than .
Proof. Assume that and let . Then so that is consistent, while so that is not consistent. □
On the other hand, the CD condition suggests to consider as auxiliary density a density close to the conditional density in the sense of the KL divergence: this is actually at the heart of the celebrated cross-entropy approach [14], which consists in choosing minimizing among a given family of auxiliary distributions. The next lemma exhibits a simple relation between and which implies that if is closer to than in the sense of the KL divergence, then necessarily , i.e., has a larger probability under than under .
Lemma 6. We have . In particular:
if , then ;
if , then is more consistent than .
Proof. Let be the density conditioned on . Since is assumed to be absolutely continuous with respect to , it is also absolutely continuous with respect to and in particular, the two divergences and are well-defined. Moreover, since a.s., we have which implies that
Since this implies the desired first inequality . The inequality then follows from the fact that a.s., so that . In particular, if , then .
To conclude, let us assume that : if is consistent, then : therefore, for large enough, and so which implies the consistency of by Lemma 3. □
We have seen that (i.e., the mean number of non-zero terms in the sum (1) defining ) is a necessary condition for the consistency of . For the standard Monte Carlo estimator, this condition (which then reads ) is also sufficient. A natural question is thus whether is also sufficient for consistency of : 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 in the sense of Assumption 1, and that is unbounded above. Then for with , is not consistent while .
Proof. For with , is not consistent by Lemma 4, while 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 is the density of the standard Gaussian distribution , and we also consider a Gaussian density, with mean and variance .
In this setting, an important auxiliary distribution is the optimal (in the sense of the KL divergence) Gaussian density where the minimum runs over all Gaussian densities. It is well-known that is the Gaussian density with mean and covariance matrix , see for instance [5, 14]. By construction, decreases the KL divergence with 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.
puts more mass on
In the Gaussian setting it is well-known that
where is Stein’s loss between and the identity matrix , which satisfies if and only if , see for instance [5 Lemma 3.5]. Combined with Lemma 6, this identity implies that, if ,
Thus, puts more mass on than , which is coherent with the intuition that is a better auxiliary distribution than .
Hyperplane case: consistency improvement
By construction we have (which is also readily visible on (6) since ) but the improvement brought by over is unclear. When , then is bounded and thus also: therefore in this case, both estimators have the same consistency condition, namely by Lemma 3.
The case is much more challenging and, although this regime is at the heart of rare-event simulation, the consistency of for does not seem to have been considered in the literature so far, even in the one-dimensional case . In this case the condition for consistency of the standard Monte Carlo estimator is , and so a natural question is whether a suitable choice of may weaken this condition to for some . The KL-based arguments of the previous section suggest that this will be the case if : in view of (6), this requires a particular asymptotic behavior for , namely that .
We do not know whether such an asymptotic relation holds for general sets and to get insight into this question, we consider the hyperplane case with and a sequence of -dimensional unit vectors (). 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
where here and in the sequel, follows a standard, one-dimensional normal distribution. In particular, it follows that
Careful asymptotic expansions for , and imply that is bounded. More precisely, the following result holds.
Lemma 8. Consider the Gaussian setting and the hyperplane case with and a sequence of unit vectors. Then we have . In particular, for is consistent for any .
This result therefore shows that, as far as consistency is concerned, considerably improves the situation compared to the standard Monte Carlo estimator where the consistency condition is . Whether such an improvement holds for general sets represents in our view an interesting open question.
Proof of Lemma 8. Using the Gaussian integration by parts formulas for , we get
and
so that
Thus, everything gets expressed in terms of , whose asymptotic expansion is well-known. Actually, to get the leading term in , we need to consider the following expansion:
From this expansion we readily get , while getting the expansions for the terms , and appearing in (7) is more involved. Starting from the asymptotic expansion (10) of and the expressions (8) and (9) of and in terms of , computation detailed below shows that
Plugging these expressions into (7), we obtain
which is precisely the result announced. Let us now detail the computation for , and . Combining (8) and (10) gives and so using with we obtain
and so . This allows to get the required expansion for :
which gives . Plugging in the previous expressions for and into the expression of (9), we get
This finally allows to get the expansion which achieves the proof. □
In practice, is usually out of reach because the parameters , and 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 and variance given by
In recent algorithms, , and are estimations of the true parameters , and . 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 the Gaussian density with mean and variance given by (11), and consider also the hyperplane case with and a sequence of unit vectors. Then we have
with
and
These expressions allow to recover the fact that will be small if is close to and to , but they give precise quantifications to the extent to which we must have , and . The value of the scalar product seems particularly important as if we do not have , then we necessarily have .
Proof of Lemma 9. The relation (12) is well-known, see for instance [5 Lemma 3.5]. Since and , we get and so
In particular, and since , we get
which can be rearranged to get (13). For the quadratic term, we have
from which (14) can be derived by standard algebraic manipulation.
Opening discussion: does improve the speed of convergence?
Although we have seen that may significantly improve consistency compared to the standard Monte Carlo estimator , it seems to us that an important, essentially open question is the following: when both estimators are consistent (e.g., if is more consistent than and ), does converge faster than ? Since
determining the speed of convergence (i.e., the scaling parameters 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 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 are difficult to study because of the indicator function of the set which, in principle, prohibits general explicit expressions. For these reasons, moments of are often controlled by neglecting the indicator function through the bound
This bound is insightful when , but is extremely rough when : 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 , 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 and .
Proof. We have and, starting from the expressions of and , one can express the ratio as
with . This shows that will be integrable if , and not integrable if . Since this shows that is integrable if and not integrable if . Let us now assume that and proceed with establishing (17) and (16). Let in the sequel and : then we have
so that
with the Gaussian density with variance and mean . Integrating this identity implies that
as well as (16) since . Therefore, in order to conclude the proof it remains to prove (17), i.e., in view of the above, that
This relation is easily established recalling that and .
Of course, depending on the set , we may have even if : for instance, consider , so that by the previous lemma, but in which case is bounded and so has finite moments of all order. An inspection of the proof of Lemma 10 reveals that what happens is that with a symmetric quadratic form. The condition ensures that is positive, which makes (and thus ) integrable. If then has negative eigenvalues, which makes 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 : for instance, one can easily build with positive, such that is not integrable while with is integrable.
However, the hyperplane case suggests that such a “cooperative” interplay between and 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 is the same as for .
Lemma 11. Consider the Gaussian setting of Section 3 with , and the hyperplane case with a unit vector and . For , we have if and if .
This result is puzzling as, in the hyperplane case, we have when : therefore, although is a very good choice for consistency (cf. Lemma 8), it seems extremely bad in terms of tail behavior as for has very few moments (up to ) while the Monte Carlo estimator has all moments, since for . Based on these considerations, and given that the hyperplane is usually a favorable test case, we conjecture that, although dramatically improves consistency, in the regime where both and with converge, then convergence may occur faster for than for .
References
- [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]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]Siu-Kui Au and James L. Beck, Importance sampling in high dimensions, Struct. Saf. 25 (2003), no. 2, 139–163.
- [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]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]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]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]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]Víctor Elvira and Luca Martino, Advances in importance sampling, Wiley StatsRef: Statistics Reference Online, Wiley, 2021.DOI
- [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]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]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]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]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]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]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]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]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