{'fraction_non_alphanumeric': 0.047258710757214585, 'fraction_numerical': 0.020560937262260992, 'mean_word_length': 4.093304401735896, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 37, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Over-Conservativeness of Variance-Based Efficiency Criteria and Probabilistic Efficiency in Rare-Event Simulation

In rare-event simulation, an importance sampling (IS) estimator is regarded as efficient if its relative error, namely the ratio between its standard deviation and mean, is sufficiently controlled. It is widely known that when a rare-event set contains multiple"important regions"encoded by the so-called dominating points, IS needs to account for all of them via mixing to achieve efficiency. We argue that in typical experiments, missing less significant dominating points may not necessarily cause inefficiency, and the traditional analysis recipe could suffer from intrinsic looseness by using relative error, or in turn estimation variance, as an efficiency criterion. We propose a new efficiency notion, which we call probabilistic efficiency, to tighten this gap. In particular, we show that under the standard Gartner-Ellis large deviations regime, an IS that uses only the most significant dominating points is sufficient to attain this efficiency notion. Our finding is especially relevant in high-dimensional settings where the computational effort to locate all dominating points is enormous.


Introduction
We study the problem of estimating the probabilities of rare events with Monte Carlo simulation, which falls in the domain of rare-event simulation (Bucklew 2004, Juneja and Shahabuddin 2006, Rubino and Tuffin 2009). Traditionally, rare-event simulation is of wide interest to a variety of areas such as queueing systems (Dupuis et al. 2007, Dupuis and Wang 2009, Blanchet and Mandjes 2007, Blanchet and Lam 2014, Kroese and Nicola 1999, Ridder 2009, Sadowsky 1991, Szechtman and Glynn 2002, highly dependable computer systems and communication networks (Tuffin 2004, Lewis and Böhm 1984, Goyal et al. 1992, Carrasco 1992, Shahabuddin 1994, Kesidis et al. 1993, financial risk management (Glasserman 2003, Glasserman and Li 2005, Glasserman et al. 2008) and insurance modeling (Asmussen 1985, Asmussen andAlbrecher 2010). More recently, with the rapid development of intelligent physical systems such as autonomous vehicles and personal assistive robots , Arief et al. 2021, rare-event simulation is also applied to assess their risks before deployments in public, where the risks are often quantified by the probabilities of violations of certain safety metrics such as crash or injury rate , O' Kelly et al. 2018, Zhao et al. 2016. The latter problems typically involve complex AI-driven underlying algorithms that deem the rare-event structures rough or difficult. The current work is motivated from the importance of handling such type of rare-event problems (e.g., the U.S. National Artificial Intelligence Research and Development Strategic Plan (Kratsios 2019) lists "developing effective evaluation methods for AI" as a top priority) and provides a step towards rigorously grounded procedures in this direction.
The starting challenge in rare-event simulation is that, by its own nature, the target rare events seldom occur in the simulation experiment when using crude Monte Carlo. In other words, to achieve an acceptable estimation accuracy relative to the target probability, the required simulation size could be huge in order to obtain sufficient hits on the target events. Statistically, this issue is manifested as a large ratio between the standard deviation (per run) to the mean, known as the relative error, that determines the order of a required sample size. In the large deviations regime where the target probability can depend exponentially on the rarity parameter, this in particular means the required sample size is exponentially large.
To address the inefficiency of crude Monte Carlo, a range of variance reduction techniques have been developed. Among them, importance sampling (IS) (Siegmund 1976) has been broadly applied to improve the efficiency. IS uses an alternative probability measure to generate the simulation samples, and then reweighs the outputs via likelihood ratio to guarantee unbiasedness. The goal is that by using this alternate estimator than simply counting the frequency of hits in crude Monte Carlo, one can achieve a small relative error with a much smaller sample size.
To this end, it is also widely known that IS is a "delicate" technique, in the sense that the IS probability measure needs to be carefully chosen in order to achieve a small relative error. In the typical large deviations setting, the suggestion is to tilt the probability measure to the "important region". The delicacy appears when there are more than one important regions, in which case all of them need to be accounted for. More specifically, in the light-tailed regime, these important regions are guided precisely by the so-called dominating points, which capture the most likely scenario in a local region of the rare event. Despite the tempting approach to simply shift the distribution center to the globally most likely scenario, it is well established that if not all the dominating points are included in the IS mixture distribution, then the resulting estimator may no longer be efficient in terms of the relative error (see, for instance, the seminal work Glasserman and Wang (1997)).
Our main goal in this paper is to argue that, in potentially many light-tailed problems, the inclusion of all the dominating points in an IS could be unnecessary. Our study is motivated from high-dimensional settings where finding all dominating points could be computationally expensive or even prohibitive, yet these problems may arise in recent safety-critical applications (e.g., Arief et al. (2021), Webb et al. (2018), Bai et al. (2022)).
To intuitively explain the unnecessity, let us first drill into why all the dominating points are arguably needed in the literature in the first place. Imagine that a rare event set E comprises two disjoint "important" regions, say E 1 and E 2 , and the dominating points are correspondingly a 1 and a 2 , which are sufficiently "far away" from each other, and a 1 has say a higher density than a 2 .
Roughly speaking, if an IS scheme only focuses on E 1 and tilts the distribution center towards a 1 , then there is a small chance that the sample from this IS distribution hits E 2 , so that the contribution from this sample in the ultimate estimator is non-zero and, moreover, may constitute a large likelihood ratio and consequently elicit a large variance. This unfortunate event of falling into a secondary important region is a source of inefficiency according to the relative error criterion. Now let's take a step back and think about the following: How likely does the "unfortunate" event above occur? In a typical Monte Carlo experiment, we argue -and we will see clearly in experiments -that this could be very unlikely, to the extent that we shouldn't be worried at all with a reasonable simulation size. Yet, according to the relative error criterion, it seems necessary to worry about this, because it contributes to the variance of the estimator in each single run. This points to that using variance to measure efficiency in rare-event simulation could be too loose to begin with. This variance measure, in turn, comes from the Markov inequality that converts relative error into a sufficient relative closeness between the estimate and target probability with high confidence. In other words, this Markov inequality itself could be the source of looseness.
This motivates us to propose what we call probabilistic efficiency. Different from all the efficiency criteria in the literature, including asymptotic efficiency (also known as asymptotic optimality or logarithmic efficiency) and bounded relative error (Juneja andShahabuddin 2006, L'Ecuyer et al. 2010), probabilistic efficiency does not use relative error. Instead, it is a criterion on achieving relative closeness directly. A distinctive element in probabilistic efficiency is the control on the simulation size itself, that we only allow it to grow moderately with the underlying rarity parameter.
This moderate simulation size, which is often the only feasible option in experiments, suppresses the occurrence of the unfortunate event of falling into a secondary important region. This way, while the variance could blow up, the high-confidence closeness between the estimate and target probability could still be retained.
With this new framework, we show that under standard assumptions in the widely used Gartner-Ellis large deviations regime, an IS that uses only the most significant dominating points is sufficient to ensure probabilistic efficiency. The Gartner-Ellis regime has been used across different applications such as queueing (Ridder 2009, Szechtman and Glynn 2002, Blanchet and Lam 2014, communication systems (Smith et al. 1997, Chen et al. 1993) and finance (Zhang et al. 2009, Glasserman and Li 2005, Glasserman et al. 2008. Our results thus stipulate that in all these problems, in order to obtain a good estimate relative to the ground-truth rare-event probability, we only need to exponentially tilt to the most significant dominating point when there is only one such point, without the use of any mixture. This is a sharp contrast to the established IS recipe. Moreover, this makes the construction of IS in closer line with the large deviations theory that governs the rare-event probability asymptotic. More specifically, in large deviations, the most significant dominating point coincides with the minimizer of the so-called rate function that controls the exponential decay rate of the probability. Our theory thus postulates that to attain probabilistic efficiency, it suffices to consider only this rate function minimizer when constructing the IS.
We close this introduction with further discussions of our study in relation to existing works.
First, we contrast our probabilistic efficiency with the notion of "well-estimated" in the dependability literature (Definition 3 in Tuffin (2004)). The latter asserts that all the paths which contribute most significantly to the target quantity need to occur sufficiently likely under the IS distribution. This notion is intuitively similar to the scheme of tilting the most significant dominating points which we suggest, but there are substantial differences in the motivations, implications, and also some technicality. First is that Tuffin (2004) uses well-estimated as a sufficient condition to guarantee the efficiency in estimating the variance, not only the rare-event probability itself. In contrast, our work proposes to remove variance as an efficiency criterion, a motive that is essentially orthogonal to Tuffin (2004), and we propose the tilting of only the most significant dominating points as being sufficient to ensure our new criterion of probabilistic efficiency. Our key message is that the existing proposal that suggests using all dominating points, not only the most significant ones, is an over-conservative approach and hence worth our remedy. Regarding technicality, Tuffin (2004) focuses on dependable systems where the target probability decays polynomially instead of exponentially in the rarity parameter as in our setting. Under his framework, there are only countably many points in the sample space, and thus the target probability or variance can be more readily decomposed (i.e., one could explicitly quantify the "contribution" of each point), while in our possibly continuous setting the contribution of each point is less easy to determine. Lastly, well-estimated requires that all the significant paths are no longer rare (i.e., of order O(1)) under IS, while we require a less stringent subexponential decay.
Second, we caution that probabilistic efficiency is not meant to replace existing variance-based efficiency criteria, but rather to complement them especially in situations where identifying all dominating points is infeasible due to problem complexity. In problems where the latter is not an issue, it remains "safer" to use existing criteria, as probabilistic efficiency relies on a more subtle sample size requirement, namely that it is not exponentially large. While this condition is reasonable for realistic problems, it would warrant future experimental diagnostics to detect violations of such a condition. Third, we note that our variance-free approach can potentially be adapted to rareevent estimation problems to streamline IS construction beyond the considered light-tailed large deviations regime. However, for some of these problems (e.g., heavy-tailed problems; Blanchet and Glynn 2008, Hult and Svensson 2012, Chen et al. 2019, the efficiency gain appears less dramatic than ours which possesses an exponential speed-up. Moreover, the Gartner-Ellis paradigm that we consider in this paper is arguably the most widely used and forms the basis of analysis for many rare-event problems. In the following, we first introduce in more detail the background of rare-event simulation and the established efficiency criteria in the literature, all of which involve estimation variance or relative error (Section 2). Then we show several motivating numerical examples to illustrate how excluding some dominating points in IS appear to give similar and sometimes even better performances than including all these points, the latter suggested predominantly in the literature (Section 3). This motivates our new notion of probabilistic efficiency to explain the observed numerical phenomena (Section 4) and the analysis of efficiency guarantees using this new notion (Section 5). We then show further numerical results to validate our theory and performances of our estimators (Section 6). Finally, we give some cautionary notes about probabilistic efficiency which involve the risk of under-estimation, and suggest some future directions (Section 7).

Problem Setting and Existing Framework
We consider an indexed family of rare events {A γ } γ , where γ denotes a "rarity parameter" such that as γ → ∞, the event A γ becomes rarer so that P (A γ ) → 0. Our goal is to estimate p = p(γ) := P (A γ ) using Monte Carlo simulation. Here, the index γ is introduced for modeling purpose so that we can speak of asymptotic rate, which is customary in the rare-event simulation literature.

Crude Monte Carlo and Relative Error
To motivate the various notions that we would discuss momentarily, let us consider using crude Monte Carlo to estimate p. This means we utilize the unbiased estimator Z = I Aγ for p, where I Aγ denotes the indicator variable on the event A γ . Suppose we generate the output Z independently n times, and constructp as their sample mean. Intuitively, when p is tiny, this estimatorp is most likely zero unless n is a huge number, since a long trial length is needed to land at the rare event To describe the above challenge mathematically, we consider the following criterion. For a given tolerance level ε > 0 (e.g., 5%), we would like an estimatorp to satisfy for a certain 0 < δ < 1 when using a simulation size n. In (1), the closeness betweenp and p, which represents the error ofp in estimating p, is measured relative to the magnitude of p itself. This is because for tiny p, the estimation is only meaningful if the error is small enough relative to this tiny quantity. Linking to crude Monte Carlo, outputting merelyp = 0, as likely to happen thereby, would be viewed as incurring a substantial error, i.e., lying in the event |p − p| > δp in (1). Put in another way, we argue that a huge sample size n is needed for crude Monte Carlo to attain (1).
Note that by Chebyshev's inequality, we get that for any 0 < δ < 1, Hence, n ≥ V ar(Z) εδ 2 p 2 implies that P (|p−p| > δp) ≤ ε for ε > 0. This means that V ar(Z) εδ 2 p 2 is a sufficient size for n to achieve (1). This quantity depends on the ratio between the standard deviation V ar(Z) and the mean p, which is known as the relative error. Here, for crude Monte Carlo the relative error is Consequently, the sufficient size for n also blows up as p → 0. In particular, if p decays exponentially in γ -a typical scaling in large deviations, then the required n to achieve (1) also scales exponentially.

Importance Sampling and Asymptotic Efficiency
The above challenge motivates variance reduction techniques to reduce the sample size requirement.
Among the most popular is IS. In this approach, we generate samples from an alternate measurẽ P whereP satisfies P I Aγ P (i.e., P I Aγ is absolutely continuous with respect toP ), and use Z = I Aγ dP dP as an unbiased output for p, where dP dP is the Radon-Nikodym derivative, or the so-called likelihood ratio, between P andP . Though this output is always unbiased thanks to the likelihood ratio adjustment, the performance of the IS estimator in terms of variability heavily depends on the choice of the IS probability measureP . In the literature, several efficiency criteria for IS estimators have been developed. A common criterion is asymptotic efficiency (Asmussen and Glynn 2007, Heidelberger 1995, Juneja and Shahabuddin 2006: Definition 1 (Asymptotic efficiency). The IS estimator Z = I Aγ dP dP underP is said to achieve asymptotic efficiency if lim γ→∞ log(Ẽ(Z 2 )) log p = 2 whereẼ(·) denotes the expectation underP .
From (2) and its subsequent discussion, asymptotic efficiency implies that the required simulation size n to attain a prefixed relative error grows only subexponentially in − log p. As a stronger requirement, Z is said to have a bounded relative error if lim sup γ→∞ V ar(Z) p 2 < ∞, which implies that the required simulation size remains bounded no matter how small p is. The criterion of bounded relative error is sometimes too strict to achieve, so we focus on asymptotic efficiency in this paper. More efficiency criteria could be found in Juneja andShahabuddin (2006), L'Ecuyer et al. (2010), .

Large Deviations and Dominating Points
In the large deviations setting, the classical notion of dominating points is used to guarantee asymptotic efficiency of IS (Sadowsky and Bucklew 1990). To explain, let us first recall the so-called rate function in the large deviations theory which, intuitively speaking, measures the likelihood of hitting each point on an exponential scale. More specifically, we consider the standard Gartner-Ellis regime as follows (Dembo andZeitouni 2009, Bucklew 2004). Without loss of generality consider γ log E(e x Xγ ), x ∈ R d as the scaled logarithmic moment generating function. We denote D(f ) = {x : f (x) < ∞} as the domain of a function f . With these, we assume the following: Assumption 1. µ γ (x) satisfies the following conditions: 1. µ(x) = lim γ→∞ µ γ (x) exists for any x ∈ R d , where we allow ∞ both as a limit value and as an element of the sequence {µ γ (x)}; 3. µ is essentially smooth, i.e., D(µ) • is non-empty, µ is differentiable everywhere in D(µ) • and µ is steep.
Then we define the rate function I(y) = sup x∈R d {x y − µ(x)}, y ∈ R d as the Legendre transform of µ. For any set E ⊂ R d , we denote I(E) = inf y∈E I(y). We make the following assumptions for the set E: Under these assumptions, we have the following result (e.g., adapted from Dembo and Zeitouni (2009) Theorem 3.3.6): Theorem 1 (Gartner-Ellis Theorem). Suppose that Assumption 1 holds. For any Borel set If additionally Assumption 2 holds, then Assumptions 1 and 2 are standard light-tailed conditions on A γ , which guarantee the considered probability P (A γ ) to decay exponentially in γ with decay rate I(E). The rate function I(y) can be viewed as a measurement on the likelihood of hitting y in the exponential scale. The most likely point to hit among E is hence given by the minimizer of I(y) over E, resulting in the overall exponential decay rate I(E). Note that, by Theorem 1, we have − log p = Θ(γ) as γ → ∞, and hence subexponential (or exponential) in − log p is equivalent to subexponential (or exponential) in γ.

Now we present the concept of dominating points and sets:
Definition 2 (Dominating Set). Suppose that Assumptions 1 and 2 hold. We call A = {a 1 , . . . , a r } ⊂ ∂E a dominating set for E if 1. For each i, a i ∈ D(I) • and there exists a unique s a i ∈ R d such that ∇µ(s a i ) = a i ; We call any point in A a dominating point. For two dominating points a and a , we say a is more significant than a if I(a) < I(a ). Illustration of rare-event set E = E1 ∪ E2 and dominating points.
Dominating points can be understood as the "local minimizers" of the rate function I in the sense that a i is the minimizer of I in E ∩ {x ∈ R d : s a i (x − a i ) ≥ 0}. To understand this, first, Condition 1 in Definition 2 stipulates that s a i is the gradient of I(x) at the point a i . Then, in Condition 2, a i can be seen as the minimizer of I(x) over the set {x ∈ R d : s a i (x − a i ) ≥ 0}, a fact that follows from the first-order optimality condition in convex function minimization. Thus, Condition 2 stipulates that any point in the rare-event set E has an I value not less than one of the a i 's. Geometrically, any points in the set E must lie in the half-space tangentially cut by one of the a i 's (i.e., the "backyard" of the a i ). Figure 1 is an illustration of a rare-event set E = E 1 ∪ E 2 and the dominating set {a 1 , a 2 }. Here, a 1 is the global minimum rate point in E, but E 2 is not covered by {x : s a 1 (x − a 1 ) ≥ 0}, so a 2 is included in the dominating set. Finally, we note that Condition 3 in Definition 2 enforces the dominating set to be the minimal set of points such that the geometric properties in Conditions 1 and 2 are satisfied.
Note that dominating points may not be local minimizers of the rate function I in E (even though they are minimizers in E ∩ {x ∈ R d : s a i (x − a i ) ≥ 0} as discussed above). Nonetheless, the most significant dominating points are indeed global minimizers of I in E. This is presented in the following theorem: Theorem 2. Suppose that Assumptions 1 and 2 hold, and A = {a 1 , . . . , a r } is a dominating set for E. Then I(E) = min i=1,...,r I(a i ). That is to say, the most significant dominating points are global minimizers of I in E.
We should also point out that dominating set defined according to Definition 2 may not be unique. Advantageously, the theory and estimators we present will flexibly apply to any such dominating set.

Asymptotically (In)efficient Importance Samplers
We are now ready to describe the main message of this section, which is the established recipe in constructing efficient IS. The standard proposal is to use a mixture of exponentially tilted distributions, where each exponential tilting is with respect to each dominating point. In particular, suppose that A = {a 1 , . . . , a r } is a dominating set. Then the IS distribution isP such that Here, e s a i Xγ −γµγ (sa i ) dP is the exponential tilting towards the dominating point a i and α i 's are the mixing weights. The IS (3) is well known to be asymptotically efficient: Proposition 1 (Mixture IS is asymptotically efficient). Suppose Assumptions 1 and 2 hold, and the dominating set has finite cardinality, i.e., r < ∞. Then the IS distribution (3) with any fixed α i 's is asymptotically efficient.
While the proof of Proposition 1 is standard, we include it in the Appendix for self-containedness.
Here, we describe the key intuition in justifying the necessity of mixture. First, the likelihood ratio in the considered mixture IS is Xγ −γµγ (sa i ) and it satisfies that for any i, In the exponent in the rightmost expression of (4), the second term γ(s a i a i − µ γ (s a i )) is approximately γI(a i ), and the first term is the "overshoot" of the sampled X γ compared to the dominating point a i . That is, if X γ is in the "backyard" of a i , then this term s a i (X γ − γa i ) ≥ 0. The definition of dominating set, especially Condition 2 in Definition 2, guarantees any (1/γ)X γ in E must have s a i (X γ − γa i ) ≥ 0 for at least one of the i's. Thus, by decomposing the second moment of Z = I Aγ L according to the backyards of a i 's, we can ensure that the magnitude of the likelihood ratio, when X γ lies inside the rare event set, is properly controlled. More precisely, Then the second moment of the IS satisfies which is approximately bounded by r i=1 e −2γI(a i ) /α 2 i and hence e −2γI(E) in the exponential scale, thus verifying asymptotic efficiency.
On the other hand, if we miss some dominating points in the construction of the mixture IS, then asymptotic efficiency may fail to be attained. Below we give a simple example to demonstrate this.
Proposition 2 (Missed dominating point leads to violation of asymptotic efficiency).

Suppose that we want to estimate
, and hence Z is not asymptotically efficient by definition.
In this example, the dominating points are 1 and −2, and N (γ, γ) is the exponential tilt towards the first dominating point 1 (for Gaussian distribution, exponential tilting amounts to a mean shift).
Here, by considering only this point, it is possible that a generated X γ satisfies (1/γ)X γ ∈ (−∞, −2] while the overshoot s 1 (X γ − γ1), as explained for (4), takes a very negative value. This scenario contributes significantly to the overall variance and ultimately violates asymptotic efficiency.
Our main insight in this paper is a rebuke of the above viewpoint. More specifically, we argue that missing inferior dominating point, such as the example in Proposition 2, can still result in a good IS according to our beginning criterion (1). A core ingredient of this assertion is to question the use of asymptotic efficiency, or more generally variance-based efficiency criteria. Before delving into the theory, let us first present some numerical results to shed light on how much difference it makes to use different numbers of dominating points in the IS mixture. This is the focus of our next section.

Motivating Experimental Results
We run three numerical examples to demonstrate that missing dominating points in IS construction, while provably leads to asymptotic inefficiency, could perform well empirically. This thus suggests an inadequacy in using asymptotic efficiency, or more generally variance-based criteria, to measure the performances of rare-event estimators. Besides, the computationally demanding example in Section 3.3 justifies the motivation why we seek to reduce the number of used dominating points in the IS mixture.

Large Deviations of an I.I.D. Sum
We consider the problem of estimating the tail probability involving a sum of random variables, where Y 1 , Y 2 , ... are i.i.d and we are interested in We consider m as the rarity parameter γ presented in Section 2. Using the notation in the Gartner-Ellis regime, we have X γ = S m and E = (−∞, −a] ∪ [a, ∞). Then µ(x) = log E(e xY 1 ) and we suppose Assumption 1 is satisfied. By Theorem 1, when |EY 1 | < a, if s a and s −a satisfy ∇µ(s a ) = a and ∇µ(s −a ) = −a, then we have For this problem, Glasserman and Wang (1997) (3), the idea is similar in that it accounts for both dominating points). In our experiment, we follow Glasserman and Wang (1997) to set Y 1 = A − B with A ∼ N (1.5, 1), B ∼ Exp(1) and A, B independent, and a = 1.5 (in this case, s a = ( √ 5 − 1)/2, s −a = −2 + √ 2, and I(a) ≈ 0.2902, We run numerical experiments with m = 10, 30, 50 and 100. The results using 10 4 samples are shown in Table 1. By comparing the numbers in the second and third rows, we observe thatα(m) andβ(m) have very similar empirical performances. However, note that: Proposition 3. Under the problem specification above,β(m) is asymptotically efficient whilê α(m) is not. In fact,Ẽ(α 2 (m)) → ∞ as m → ∞ whereẼ denotes the expectation under the exponential tilting towards a.
In view of Proposition 3,α(m) is arguably a very poor estimator as it bears an exploding variance.
We therefore see an apparent discrepancy between empirical performances and theoretical guidance -The theoretically bad variance does not result in poor empirical performances. Proposition 3 is proved in Glasserman and Wang (1997), where the asymptotic efficiency ofβ(m) follows from their Proposition 1, while the variance behavior ofα(m) appears in their Theorem 1.

Overshoot Probability of Random Walk
We consider the problem of estimating the overshoot probability of the finite-horizon maximum of a random walk. We define the probability of interest as where S m = m i=1 Y i and Y i 's are Gaussian distributed with mean 0, standard deviation σ, and pairwise correlation −0.02, i.e., corr(Y i , Y j ) = −0.02 for any i, j ∈ {1, ..., d} with i = j. Suppose that the rarity parameter is γ = 1/σ 2 → ∞. We note that we can reformulate this target rare x i ≥ a} with x i denoting the ith element in x. This decomposition allows us to construct an IS estimator using the d dominating points corresponding to each half-space H m . More specifically, in this example, I(y) = 1 2 y Σ −1 y, and the dominating points, ranking from the most to the least significant (i.e., increasing rate function value), are a 1 = aΣe d In our experiments, we fix a and vary σ for different rarity levels. In addition, we set d = 10.
We generate 10 4 samples from IS distributions using a varying, partial list of dominating points.
That is, we choose the IS distributions for X γ as 1 k k i=1 φ(x; γa i , γΣ), where φ(x; a, b) denotes the Gaussian density with mean a and variance b, for k = 1, . . . , d. The performances of these IS estimators are shown in Table 2. We observe that these estimators with different numbers of dominating points all perform similarly. In particular, we present the cases with σ = 0.2 and σ = 0.3 respectively in Figure 2. We observe that in both cases the performances of the IS estimators are almost independent of the number of used dominating points, with the probability estimates all comparable while using more dominating points slightly increases the CI width.
On the other hand, Proposition 1 implies that the IS using all dominating points is asymptotically efficient while we have: Proposition 4. Under the problem specification above, the IS estimator that exponentially tilts towards the most significant dominating point a 1 , i.e., X γ distributed as N (γa 1 , γΣ), is not asymptotically efficient.
Thus, like in Section 3.1, there appears a mismatch between theoretical guidance and empirical observation. The asymptotic inefficiency of simple exponential tilting towards only the most significant dominating point does not result in a poor experimental performance.  Simulation results for the random walk experiment. Point estimates and CI widths for IS estimators using different numbers of dominating points.

Robustness Assessment for an MNIST Classification Model
We consider a rare-event probability estimation problem from an image classification task. Our goal is to estimate the probability of misclassification when the input of a prediction model is perturbed by tiny noise. This probability estimate is of interest as a robustness measure of the  prediction model (Webb et al. 2018). More specifically, suppose that the prediction model g is able to predict the label of input x 0 , i.e. g(x 0 ) = c where c is the true label of x 0 . Then P (g( where ε is a random perturbation can be used to measure the robustness of g. In particular, we consider the classification problem on MNIST dataset which contains 70,000 images of handwritten digits and each image consists of 28 × 28 pixels. We train a 2-ReLU-layer neural network with 20 neurons in each layer using 60,000 training data, which achieves approximately 95% of testing data accuracy in predicting the digits. We perturb a fixed input (that is correctly predicted) with a Gaussian noise with mean 0 and standard deviation σ on each of the 784 dimensions to assess the robustness of the prediction. Note that the rarity of this problem is determined by the value of σ, and we let the rarity parameter γ = 1/σ 2 → ∞. The target rare event can be reformulated as 1 γ X γ ∈ {x : g(x 0 + x) = c)} where X γ = γε. We apply mixtures of exponential tiltings as IS estimators for this problem, namely by considering the IS distribution 1 k k i=1 φ(x; γa i , γI), where φ(x; a, b) denotes the Gaussian density with mean a and variance b as in Section 3.2, for k = 1, 2, . . .. Here a i , i = 1, 2, . . . denote the dominating points. In order to compute these points, we apply the scheme introduced in  and Bai et al. (2022), which sequentially searches for dominating points by minimizing the rate function on the rare-event set that excludes the half-spaces cut from previous more significant dominating points. In the Gaussian case with piecewise linear rare-event set boundary as in our current example, each iteration amounts to finding the highest-density point on a piecewise-linearboundary set, which can be conducted using mixed integer programming (see Algorithm 1 in the Appendix). Due to the high dimensionality of the input space and the complexity of the neural network predictor, the number of dominating points in this problem is huge. We implemented this sequential searching algorithm and it took a week to find the first 100 dominating points. Since we stopped the algorithm prematurely, the actual number of dominating points can be much larger.
We run IS distributions with different numbers of dominating points (ranging from 1 to 41) and magnitudes of σ (ranging from 0.1 to 0.2) and report the estimated probabilities and CIs. We use 10 5 samples for IS estimators and 10 7 samples for crude Monte Carlo estimators.
Figures 3a and 3b show the results. Missing less significant dominating points does not seem to make noticeable differences in this problem. As shown in Figure 3a, when we fix the rarity of the problem, the estimate is not sensitive to the number of dominating points. The CI width has an increasing trend as the number of dominating points gets larger, indicating that additional dominating points can in fact even hurt performances.
In Figure 3b, we vary the rarity of the problem and compare the performances of different IS estimators and crude Monte Carlo. Note that estimates using crude Monte Carlo are unavailable for rarer configurations due to its inefficiency. We observe that the estimates from different IS estimators overlap visually in all considered cases, which indicates that the differences among these estimates are negligible. We also note that these estimates are consistent with the crude Monte Carlo estimates (when available), which shows their correctness.
Nonetheless, once again we have an apparent mismatch between theoretical inefficiency and good empirical performances: Proposition 5. Under the problem specification above, the IS estimator that exponentially tilts towards the most significant dominating point, i.e., X γ distributed as N (γa 1 , γI), is not asymptotically efficient.

Probabilistic Efficiency
Section 3 shows that IS estimators that miss some dominating points could perform competitively compared to estimators that consider all of them, thus suggesting a gap between the notion of asymptotic efficiency and empirical performances. In light of this, we propose the concept of probabilistic efficiency as a relaxation of asymptotic efficiency. The key of probabilistic efficiency is to consider the high-probability relative discrepancy of the estimator from the ground truth directly, instead of using the relative error or equivalently the estimation variance. The latter, as can be seen in the arguments in Section 2, provides a sufficient, but not necessary, condition on the required sample size. In particular, there is an intrinsic looseness brought by the Markov or Chebyshev inequality (2) that converts relative error into the required sample size.
To proceed, we first define the following: Definition 3 (Minimal relative discrepancy). For any estimatorp of p and any ε > 0, the minimal relative discrepancy ofp, at tolerance level ε, is given by The minimal relative discrepancy δ ε (p, p) measures the relative accuracy of the estimatorp, in that it gives the smallest relative discrepancy ofp from p that can be achieved with probability 1 − ε.
Thus the smaller is δ ε (p, p), the more accurate isp. Note that in (7), the probabilityP is the one generating the estimatorp.
We say thatp is probabilistically efficient if δ ε (p, p) can be made small in some sense, without needing to use a gigantic amount of computation. More precisely, we propose the following notions: Definition 4 (Probabilistic Efficiency). Suppose that {A γ } γ is an indexed family of rare events and p = P (A γ ) → 0 as γ → ∞. Consider an estimatorp obtained from n = n(γ) independent replications of Z. For any ε > 0, we define δ ε (p, p) as in (7). Then 1. We call Z strongly probabilistically efficient if we can choose n subexponential in − log p such that, for any ε > 0, lim γ→∞ δ ε (p, p) = 0; 2. We call Z weakly probabilistically efficient if we can choose n subexponential in − log p such that, for any ε > 0, lim sup γ→∞ δ ε (p, p) < 1.
Note that strong probabilistic efficiency matches the usual notion in statistical estimation. That is, the estimator approaches the target parameter as γ → ∞. In contrast, weak probabilistic efficiency only cares about a correct magnitude. While this may appear less desirable, in rare-event estimation a correct magnitude can be viewed as sufficient as the target quantity is very small, and this weaker notion allows more flexibility in constructing estimators. We also contrast our proposed probabilistic efficiency with a notion named probabilistic bounded relative error proposed in Tuffin and Ridder (2012), where the IS measure is randomly chosen and efficiency is achieved if the resulting random relative error of the IS estimator is bounded by some constant with high probability, which is conceptually different from our notion.
The following shows that probabilistic efficiency is a relaxation of asymptotic efficiency: Proposition 6. If Z is asymptotically efficient, then Z is strongly probabilistically efficient.
Proof of Proposition 6. For any unbiased estimator Z, we have that for any ε > 0, and hence by definition, If Z is asymptotically efficient, V ar(Z) p 2 grows at most subexponentially in − log p, so we could choose n subexponentially growing in − log p such that lim γ→∞ δ ε (p, p) = 0 for any ε > 0. By definition, Z is strongly probabilistically efficient.
While asymptotic efficiency implies strong probabilistic efficiency, we note that these two notions are not equivalent. In Section 3, Propositions 3-5 show that asymptotic efficiency does not hold for the considered IS estimators in all the presented examples, but Theorem 10 in Section 6.1 will show that strong probabilistic efficiency actually holds for all of them.
Now we explain how probabilistic efficiency helps us understand the influence of missing some dominating points. Recall the example where A γ = { 1 γ X γ ∈ E} and E comprises two disjoint and faraway pieces E 1 and E 2 . The dominating points are respectively a 1 and a 2 (recall Figure 1). Denote p j = P ( 1 γ X γ ∈ E j ), j = 1, 2, and we assume that p 2 is exponentially smaller than p 1 . If we focus on E 1 and simply use the exponential tilting towards a 1 as the IS distribution, then we face the risk of having a sample falling into E 2 while the associated likelihood ratio is very high, which leads to asymptotic inefficiency. However, experimentally if we run the simulation with a moderate sample size, then most likely none of the samples fall into E 2 . Conditional on not hitting E 2 , we actually get an estimate close to p 1 , which is in turn close to p. In other words, even if the resulting IS estimator is not asymptotically efficient, it could still give a good estimate in terms of its distance to p, as long as the sample size is not overly big. The latter is precisely the paradigm of probabilistic efficiency.
More concretely, we have the following theorem: Theorem 3 (Achieving strong probabilistic efficiency). Suppose that {A γ } γ is an indexed family of rare events and p We have an asymptotically efficient IS estimator for p 1 obtained from Z 1 = I A 1 γ dP dP underP . This implies that there exists n = n(γ) growing subexponentially in − log p such that V ar(Z 1 ) 3.p 2 :=P (A 2 γ ) satisfies that np 2 → 0 as γ → ∞. Letp be the sample mean of n independent replications of Z = I Aγ dP dP underP . For any ε > 0, define δ ε (p, p) as in (7). Then we have Hence Z is strongly probabilistically efficient.
Proof of Theorem 3. Suppose that we sample ω 1 , . . . , ω n underP . Let Clearlyp =p 1 +p 2 . For simplicity, denote Then we have thatP where the second inequality follows from a union bound, the third inequality follows from p 1 ≤ p and that |p 2 − p 2 | >δp impliesp 2 > 0, the fourth inequality follows from Chebyshev's inequality in the first term and a union bound in the second term, and the last equality follows from the definitions in (8) and (9). Thus δ ε (p, p) ≤ δ. Finally, δ → 0 by a direct use of the assumptions.
Similarly, if we relax the assumption that p 1 /p → 1 as γ → ∞, we get sufficient conditions for weak probabilistic efficiency: Theorem 4 (Achieving weak probabilistic efficiency). Suppose that {A γ } γ is an indexed family of rare events and p = P (A γ ) → 0 as γ → ∞. We write A γ = A 1 γ ∪ A 2 γ where A 1 γ and A 2 γ are two disjoint events. Denote p j = P (A j γ ), j = 1, 2. Assume that We have an asymptotically efficient IS estimator for p 1 obtained from Z 1 = I A 1 γ dP dP underP . This implies that there exists n = n(γ) growing subexponentially in − log p such that V ar(Z 1 ) Letp be the sample mean of n independent replications of Z = I Aγ dP dP underP . For any ε > 0, define δ ε (p, p) as in (7). Then we have Hence Z is weakly probabilistically efficient.
Proof of Theorem 4. Following the proof of Theorem 3, we still get Under the conditions of Theorem 4, now lim sup γ→∞ δ = 1 − c < 1. By the definition, Z is weakly probabilistically efficient.
We note that in Theorems 3 and 4, A 1 γ and A 2 γ could be very general events. In particular, when we use dominating points to decompose the rare-event set, A 1 γ and A 2 γ are not necessarily each governed by only one dominating point but could be more as long as the assumptions hold.
Moreover, there can be multiple ways to split A γ into A 1 γ and A 2 γ , and as long as one of these ways validates the assumptions in Theorem 3 or 4 then probabilistic efficiency is guaranteed. This provides flexibility in using Theorems 3 and 4; Sections 6.1.2 and 6.1.3 will demonstrate this in some specific examples.
According to the theorems, supposing that we have found some dominating points while the remaining ones are known to be less significant and "far from" the current ones, we could simply use the current mixture IS distribution instead of keep searching. The remaining question is how we could detect that the remaining dominating points are negligible, i.e. the assumptions of the theorem are satisfied. Besides, probabilistic efficiency only implies that the point estimate is reliable in some sense. This raises questions on inference such as the construction of valid CIs. In the next section, we will make these discussions precise and show our answers under minimal assumptions in the standard Gartner-Ellis regime.

Probabilistically Efficient Estimation in the Gartner-Ellis Regime
We study probabilistically efficient IS in the widely used Gartner-Ellis regime introduced in Section 2. Our key result is that probabilistic efficiency can be readily achieved by using only the most significant dominating points, under essentially no more assumptions than what is needed to derive the Gartner-Ellis large deviations asymptotic.
We first consider the case where there is only one most significant dominating point, which is a common scenario (e.g., in all the examples in Section 3): Theorem 5 (Using the most significant dominating point is probabilistically efficient).
Consider the problem of estimating p = P ( 1 γ X γ ∈ E). Suppose that Assumptions 1 and 2 hold. Suppose also that the dominating set A has finite cardinality with a unique most significant dominating point a, i.e., I(a) < I(ã) for all otherã ∈ A. Then the IS distributionP given by the exponential tilting towards a, i.e., is strongly probabilistically efficient.
Theorem 5 stipulates that we only need the most significant dominating point in constructing an efficient IS. This result, which is in sharp contrast to the established IS recipe that suggests using all dominating points, explains the good empirical performance of the "poor" estimators in Section 3. Moreover, the proposal in Theorem 5 is in closer line with the Gartner-Ellis asymptotic theory, in that the use of the most significant dominating point, which is also the minimizer of the rate function (recall Theorem 2), governs both the large deviations asymptotic and the construction of efficient IS. Lastly, regarding the assumptions needed, the only additional condition beyond the standard Gartner-Ellis assumptions (i.e., Assumptions 1 and 2) is the finite cardinality of the dominating set. In fact, if we have multiple most significant points, we have a natural generalization: Theorem 6 (Mixing most significant dominating points). Consider the problem of esti- . Suppose that Assumptions 1 and 2 hold. Suppose also that the dominating set A has finite cardinality with k most significant dominating points a 1 , . . . , a k , i.e., I(a 1 ) = · · · = I(a k ) < I(a ) for all a ∈ A \ {a 1 , . . . , a k }. Then the IS distributionP given by the mixture of exponential tiltings towards a 1 , . . . , a k , i.e., That is, we use mixture to account for all the most significant dominating points when there are multiple of them. The proofs of Theorems 5 and 6 amount to verifying the assumptions in Theorem 3 using the Gartner-Ellis conditions. In particular, Conditions 1 and 2 in Theorem 3 can be routinely verified, while Condition 3 is checked by showing thatp 2 is in fact exponentially decaying in γ, which requires an application of the Gartner-Ellis theorem under the IS distribution.
The verification of Condition 3 especially reveals a key phenomenon that, under the exponential tilting to the most significant dominating point(s), the probability of an IS sample hitting onto the "backyards" of other dominating points is exponentially small, which in turn fulfills the notion of probabilistic efficiency.
Proofs of Theorems 5 and 6. We focus on Theorem 6 since Theorem 5 is a special case therein.
It suffices to verify all the assumptions in Theorem 3. For A γ = { 1 γ X γ ∈ E}, by Theorem 1, p = P (A γ ) satisfies that lim γ→∞ 1 γ log p = −I(E) < 0, so p → 0 as γ → ∞. If k = |A|, then the IS estimator from (11) already uses all the dominating points and thus is asymptotically efficient by Proposition 1. Hence, from now on, we assume that k < |A|. For convenience, we denote a k+1 as a next most significant point other than a 1 , . . . , a k , i.e., I(a k+1 ) > I(a 1 ) = · · · = I(a k ) and I(a k+1 ) ≤ I(a ) for all Second, by the definition, {a 1 , . . . , a k } is a dominating set for E 1 , so the IS estimator Z 1 = I( 1 γ X γ ∈ E 1 ) dP dP (ω) is asymptotically efficient by Proposition 1. This verifies Assumption 2 in Theorem 3. Third, we would prove thatp 2 decays exponentially in γ (hence also exponentially in − log p), and hence np 2 → 0 for subexponentially growing n which verifies Assumption 3 in Theorem 3.

Indeed, we havep
where dP i dP (ω) = e s a i Xγ −γµγ (sa i ) . DenoteẼ i ,μ γ,i andĨ i as the corresponding expectation, scaled logarithmic moment generating function and rate function underP i . Then, underP i , we havẽ . Then the rate function is For any y ∈ E 2 , we have that I(y) ≥ I(a k+1 ) and that s a i (y − a i ) ≤ 0 for i = 1, . . . , k, and thusĨ i (y) = From the above derivations, Assumption 1 still holds forP i . By Theorem 1, Overall, we havep 2 decays exponentially in γ.
Now we have verified all the assumptions in Theorem 3.
We comment that if we know any one of the most significant points, say a, among several such points, satisfies is the rare-event probability "contributed" from a, then using the IS that exponentially tilts only to a, i.e., (10), is weakly probabilistically efficient. This can be shown by a similar argument to the proofs of Theorems 5 and 6 above. Such an approach is in contrast to using the IS mixture in (11) suggested by Theorem 6 that achieves strong, instead of only weak, probabilistic efficiency.
Nonetheless, knowing p 1 /p → c typically requires information on the multiplicative factor in front of the exponential decay dictated by the large deviations rate function, which in turn requires derivation of exact asymptotic that is only known for a relatively small number of problems.
Next, besides point estimates, we investigate inference using probabilistically efficient IS estimators, in particular how to construct (asymptotically) valid CIs. First, we consider the interval whereV is the sample variance and M γ = max i=1,...,k 1 α i e −γ(s a i a i −µγ (sa i )) is deterministic. The following theorem provides an asymptotic coverage guarantee for this CI: Theorem 7 (Constructing confidence intervals with probabilistically efficient estimators). Under the same setting as Theorem 6, suppose we sample X (1) , . . . , X (n) i.i.d. fromP and let Usep andV to respectively denote the sample mean and sample variance of Z (i) 's. If n is subexponentially growing in − log p (or γ) as γ → ∞, then, for any In Theorem 7, note that even if we neglect the higher-order term (in terms of n) 7 log(4/α)Mγ 3(n−1) , the CI half-width is 2 log(4/α) times V n , which is more conservative than the Central Limit Theorem (CLT) based interval where z 1−α/2 is the (1 − α/2)-quantile of the standard normal distribution. For instance, when α = 0.05, we have 2 log(4/α) ≈ 2.96, while z 1−α/2 ≈ 1.96. Our next theorem shows that, under stronger conditions, the CLT-based CI (13) is also asymptotically valid.
Under the same setting as Theorem 6, suppose we sample X (1) , . . . , X (n) i.i.d. fromP and let Usep andV to respectively denote the sample mean and sample variance of Z (i) 's. In this case, we could choose n subexponentially growing in − log p (or γ) such Theorem 8 tightens the interval in Theorem 7 to using the CLT-based critical value z 1−α/2 with a more careful choice of sample size n.
Finally, we prove that if we use all the dominating points in the mixture, so that the estimator satisfies the classical notion of asymptotic efficiency, then, under conditions similar to Theorem 8, the CLT-based interval possesses an even stronger guarantee that the asymptotic coverage probability is exactly 1 − α.
Consider the problem of estimating p = P ( 1 γ X γ ∈ E). Suppose that Assumptions 1 and 2 hold, and the dominating set is finite. The IS estimator is Z = I( 1 γ X γ ∈ E) dP dP (ω) underP given by (3). We sample X (1) , . . . , X (n) i.i.d. fromP and let Z (i) = I( 1 γ X (i) ∈ E) dP dP , i = 1, . . . , n. Usep andV to respectively denote the sample mean and sample variance of Z (i) 's. In this case, we could choose n at least subexponentially growing in − log p (or γ) such that We make several remarks regarding the properties of the CLT-based CI I 2 in Theorems 8 and 9. First, it appears that probabilistically efficient samples sacrifice some looseness in terms of CI coverage compared to asymptotically efficient samples, as the guarantee is valid in Theorem 8 but exact in Theorem 9. Second, in Theorem 8, like Theorem 7, the sample size n is required to be not overly big, manifested by the subexponential growth requirement. This is in contrast to Theorem 9 that does not impose any upper bound on n. This ties to the key idea of probabilistic efficiency that, when the sample size is not overly big, there is a negligible chance of any sample hitting the rare-event region not corresponding to the most significant points. Thus the CI constructed from a probabilistically efficient estimator, much like the point estimate, is valid only when the sample size is not overly big, while asymptotically efficient estimators do not impose such a restriction. Lastly, we see the requirement on n given by → 0 in Theorems 8 and 9. While these conditions can be difficult to verify in practice, we should note that they are lower bound requirements, and imposed not only for CIs constructed from probabilistically efficient estimators, but also for classical asymptotically efficient estimators as well (to our best knowledge, conditions on the adequacy of sample size to attain CI coverage guarantees for these classical estimators is not known in the literature). In the next section, we will investigate the performances of all these CIs with reasonable sample sizes.
Lastly, to close this section, we briefly note that Algorithm 1 in Appendix A shows generally how to identify and compute dominating points, sequentially starting from the most significant one.
Moreover, Appendix B studies parallel results to this section for an alternative asymptotic regime to Gartner-Ellis that could be suitable for some situations involving highly complex systems.

Further Numerical Experiments and Discussions
We have shown several examples in Section 3 where IS estimators using only one or a small number of dominating points perform competitively compared with asymptotically efficient IS estimators that use all dominating points. In fact, we have shown in each example in Sections 3.1, 3.2 and 3.3 that the simple estimator using the most significant dominating point is not asymptotically efficient.
In this section, we argue that they are all probabilistically efficient, which is a direct consequence of Theorem 5. We then numerically assess the validity of the conditions in Theorem 3, which forms the underlying basis in justifying probabilistic efficiency. Finally, we test the confidence intervals constructed using our probabilistically efficient estimators discussed in Section 5 and compare with intervals constructed from asymptotically efficient estimators.

Verifying Conditions for Probabilistic Efficiency
We first state the strong probabilistic efficiency of all the proposed estimators that use only the most significant dominating points in Section 3: Theorem 10. Under the problem specifications in Sections 3.1, 3.2 and 3.3, the IS estimators that use only the most significant dominating points, namelyα(m) in Section 3.1, X γ distributed as N (γa 1 , γΣ) in Section 3.2 and N (γa 1 , γI) in Section 3.3, are all strongly probabilistically efficient.
Next, we validate the underpinning mechanism of how probabilistic efficiency arises in these examples. Note that the main basis of the strong probabilistic efficiency of these estimators, which Table 3 Estimates of p1 and p2 for the i.i.d sum example in Section 3.1 with 10 4 samples. m 10 30 50 100 p 1 8.33 × 10 −3 1.59 × 10 −5 3.59 × 10 −8 1.33 × 10 −14 p 1 /p 0.992 ≈ 1 ≈ 1 ≈ 1 p 2 6.56 × 10 −5 3.15 × 10 −11 1.85 × 10 −17 6.68 × 10 −33 p 2 /p 0.008 1.98 × 10 −6 5.16 × 10 −10 5.00 × 10 −19 p 8.40 × 10 −3 1.59 × 10 −5 3.59 × 10 −8 1.33 × 10 −14 follows from Theorem 5, is Theorem 3. In particular, Theorem 3 states three conditions that allow one to conclude strong probabilistic efficiency. Among them, the second condition is a property about asymptotic efficiency for an estimator that applies to a more restrictive rare-event set, which has been well-established in the asymptotic efficiency literature (basically, by mixing the exponential tiltings towards all the dominating points associated with the more restrictive rareevent set). Conditions 1 and 3 are more delicate. In the setting with a unique most significant dominating point, say a, the former requires a small proportion of the "contribution" from the less significant dominating points other than a over the total rare-event probability, i.e., p 2 /p → 0 where . The latter requires a small probability of sampling any points in the rare-event set that does not belong to the backyard of a, i.e.,P (some of the n samples hits Our next goal is to assess the smallness and decreasing trends (as rarity grows) of p 2 /p and P (some of the n samples hits A γ \ {s a (x − a) ≥ 0}) that drive Theorem 3.
6.1.1. Large Deviations of an I.I.D. Sum. For the experiment in Section 3.1, we use the probabilistically efficient estimatorα(m). Correspondingly, we have p 1 = P (S m ≥ am) and p 2 = P (S m ≤ −am). Table 3 shows these values as m varies, which we approximate respectively by using estimatorsβ 1 (m) = exp(−s a S m + mµ(s a ))I {Sm≥am} andβ 2 (m) = exp(−s −a S m + mµ(s −a ))I {S m ≤−am} , with s a , s −a defined in Section 3.1, generated by the same IS samples used in β(m). From Table 3, we observe that the estimate of p 2 /p is 0.008 with m = 10 and decreases to 5.00 × 10 −19 as m = 100. This shows that p 2 /p is small and approaches 0 as m increases, which matches Condition 1 in Theorem 3 (m is the rarity parameter here).
Next, we examinep 2 =P (S m ≤ −am). We generate 10 7 samples from the strongly probabilistically efficient IS distribution. We observe that none of the samples fall into {S m ≤ −am}, which indicates thatp 2 is extremely small so thatP (some of the n samples hits A γ \ {s a (x − a) ≥ 0}), with n = 10 4 in our experiment here, is close to zero. This matches Condition 3 of Theorem 3.
This close-to-1 probability, unfortunately, is quite different from what our Condition 3 in Theorem 3 would entail and cannot explain the good performance of our probabilistically efficient estimator.
To this end, we verify the conditions in Theorem 3 using an alternative construction of A 1 γ and Here, in our previous construction, we have chosen the A 1 γ to be the half-space cut by a dominating point and it turns out that the correspondingp 2 is not small and thus the condition of Theorem 3 appears to fail. However, as discussed right after Theorem 4, our main theorems allow more flexibility in choosing our A 1 γ , and as long as we find a suitable way to construct A 1 γ to satisfy the needed conditions, Theorem 3 can be used to explain our estimator's good performance.
Here is how we can construct a suitable alternative A 1 γ for Theorem 3. From the proofs of Propositions 4 and 5, we know that our probabilistically efficient estimator is not asymptotically Table 6 Estimates of p2 with 10 4 samples,p1 andp2 with 10 7 samples, andp hit with n = 10 4 for random walk example in Section 3.2, where we use In other words, if we split the rare- }}, then our probabilistically efficient estimator is asymptotically efficient for estimating P (A 1 γ ) because (x + a 1 ) Σ −1 (x + a 1 ) ≥ 4a 1 Σ −1 a 1 for all x ∈ A 1 γ . This implies that, with these choices of A 1 γ and A 2 γ , we satisfy Condition 2 in Theorem 3 (since the IS estimator using the most significant dominating point is asymptotically efficient for estimating P (A 1 γ )). Next we check Conditions 1 and 3 in Theorem 3. We define p 1 = P (A 1 γ ), p 2 = P (A 2 γ ),p 1 =P (A 1 γ ), andp 2 =P (A 2 γ ) for our newly constructed A 1 γ and A 2 γ . We first show p 2 /p → 0 and np 2 → 0. We where p old 2 andp old 2 refer to the p 2 andp 2 evaluated using our old constructions A 1 γ = A γ ∩ {s a (x − a) ≥ 0} and A 2 γ = A γ \ {s a (x − a) ≥ 0}. By p old 2 /p → 0 and np old 2 → 0 as γ → ∞ from Theorem 5 we have p 2 /p → 0 and np 2 → 0. That is, our current new construction A 1 γ for Theorem 3 would satisfy the conditions therein, and we would like to numerically verify especially Conditions 1 and 3.
Indeed, to estimate p 2 , we construct an IS estimator that mixes the exponential tiltings towards the dominating points for H i ∩ {(x + a 1 ) Σ −1 (x + a 1 ) ≤ 4a 1 Σ −1 a 1 } with i = 1, ..., 10. To estimatep 1 andp 2 , we directly generate samples from the probabilistically efficient IS distribution. We definẽ p hit =P (some of the n samples hits A 2 γ ) and estimatep hit through 1 − (1 −p 2 ) n with n = 10 4 . The results are presented in Table 6. We observe that the values of p 2 /p are now extremely small (smaller than 10 −8 in all cases). Furthermore, the values ofp 2 are also small, which lead top hit < 0.01 in all cases when σ varies from 0.2 to 0.3. These results now justify Conditions 1 and 3 of Theorem 3 and explain the good performance of our probabilistically efficient estimator in the experiment.
We also observe that some individual relative contribution slightly increases in this experiment.
However, these increases do not affect the decreasing trend of the total relative contribution of the less significant dominating points. For example, p a 2 /p and p a 3 /p both increase slightly as σ decreases (from 0.1074 and 0.0035 with σ = 0.2 to 0.1313 and 0.0042 with σ = 0.17 respectively), but the relative contribution of the rest of the less significant dominating points (excluding the first 10) is 0.0812, 0.0658, 0.0633, and 0.0362 for σ = 0.2, 0.19, 0.18, 0.17 respectively, which vanishes fast as σ decreases. Table 8 shown to illustrate the contributions of the dominating points a 2 , ..., a 10 forp 2 . Again, we find that p 2 decreases from 0.0090 to 0.0085 as σ decreases from 0.2 to 0.17, i.e., the problem becomes rarer.
From the individual contribution, we observe that all the probabilitiesp a 3 , ...,p a 10 decrease rapidly, exceptp a 2 that slightly increases as σ decreases. We use the value ofp 2 to estimate probabilitỹ p hit =P (some of the n samples hits A γ \ {s a (x − a) ≥ 0}) through 1 − (1 −p 2 ) n . The last row in Table 8 presents the results with n = 10 4 (the sample size we use in Section 3). Like in Section 6.1.2, we observe that there are samples falling into A γ \ {s a (x − a) ≥ 0} with approximately probability 1 and hence this result cannot explain the good performance of our probabilistically efficient estimator.
Similar to Section 6.1.2, we consider an alternative construction of A 1 γ and A 2 γ = A γ \ A 1 γ to explain our performance. From the proofs of Propositions 4 and 5, we know that our probabilistically efficient estimator is not asymptotically efficient if and only if min x∈Aγ (x + a 1 ) (x + a 1 ) < 4a 1 a 1 . We split the rare-event set A γ into two parts, namely A 1 γ = {A γ ∩ {(x + a 1 ) (x + a 1 ) ≥ 4a 1 a 1 }} and A 2 γ = {A γ \ {(x + a 1 ) (x + a 1 ) ≥ 4a 1 a 1 }}, and our probabilistically efficient estimator is asymptotically efficient for estimating the probabilities of A 1 . The use of our newly constructed A 1 γ for Theorem 3 can be theoretically shown to satisfy Conditions 1 and 3 therein like in Section 6.1.2.
We now check the numerical values of p 2 andp 2 to verify these conditions. We use the mixture of all 100 dominating points as the IS distribution for estimating p 2 . We generate 10 6 samples for σ varying from 0.17 to 0.2 and find no samples falling into A 2 γ , which indicates that p 2 (and hence p 2 /p) is extremely small in all cases. We generate 10 6 samples from the probabilistically efficient IS distribution to estimatep 2 and observe no samples hitting A 2 γ for the same range of σ. In this case, p hit =P (some of the n samples hits A 2 γ ) with n = 10 4 would be close to zero due to the extremely small values ofp 2 . These results match Conditions 1 and 3 of Theorem 3 and hence explain the good performance of our probabilistically efficient estimator in the experiment.

Two-sided Overshoot Probability of a Random Walk. So far we have considered
examples on strongly probabilistically efficient estimators. Here, we consider an additional example where we use a weakly probabilistically efficient estimator. We follow the problem setting in Section 3.2, where we consider the overshoot probability of the finite-horizon maximum of a random walk. However, we modify the probability of interest as where we replace S m = m i=1 Y i by its absolute value. The rest of the settings are the same as in Section 3.2, i.e., we have Y i 's are Gaussian distributed with mean 0, standard deviation σ, pairwise correlation −0.02, and rarity parameter γ = 1/σ 2 → ∞. The target rare event is In this case, the rate function is still I(y) = 1 2 y Σ −1 y and there are two most significant dominating points a 1 = aΣe d For this experiment, we first introduce an asymptotically efficient estimator. From Proposition 1, we know that the IS estimator using dominating points a 1 , ..., a d , −a 1 , ..., −a d with a 1 , ..., a d defined in Section 3.2 is asymptotically efficient. Next, we show the IS estimator using the dominating point a 1 is a weakly probabilistically efficient estimator and is not asymptotically efficient: Theorem 11. Under the problem specifications in Section 3.2 and rare-event probability defined in (14), the IS estimator that use only one of the most significant dominating points, namely a 1 in Section 3.2, and X γ distributed as N (γa 1 , γΣ) in Section 3.2, is weakly probabilistically efficient but not asymptotically efficient.
Compared to the one-sided overshoot example in Section 3.2, here the rare-event set has two most significant dominating points a 1 and −a 1 . Because we only use the first one instead of mixing both of the most significant dominating points in our IS, we only have p 1 /p → 1/2 instead of 0 and thus weak probabilistic efficiency instead of strong probabilistic efficiency holds as guided by Theorem 4.
To empirically verify Theorem 4, let us consider a partition of the rare event set We define p 1 = P (A 1 γ ), p 2 = P (A 2 γ ),p 1 =P (A 1 γ ), andp 2 =P (A 2 γ ), whereP is the IS distribution exponentially tilted using the dominating point a 1 . In our experiments, we set d = 10, fix a 1 , −a 1 and vary σ for different rarity levels. For each case, we Table 9 Point estimates (and 95% CIs) from the asymptotically efficient estimator and the weakly probabilistically efficient estimator for the two-sided overshoot probability. "AE" denotes the asymptotically efficient estimator and "PE" denotes the weakly probabilistically efficient estimator.  Table 10 Estimates of p1, p2,p1 andp2 with 10 7 samples, andp hit with n = 10 4 for two-sided overshoot probability.  Table 9. We observe that although our weakly probabilistically efficient estimator underestimates the rare-event probability in all considered cases, the estimates have relatively tight CIs and provide a good estimation on the magnitude of the rare-event probability, i.e., the estimates are around 0.5 of the estimates given by the asymptotically efficient estimator.
In Table 10, we investigate the numerical values of p 1 , p 2 ,p 1 andp 2 and check the values of p 1 /p andp hit =P (some of the n samples hits A 2 γ ) with n = 10 4 . We estimate p 1 and p 2 using the asymptotically efficient estimator with 10 7 independently generated samples. For the estimation ofp 1 andp 2 , we generate 10 7 samples using the weakly probabilistically efficient IS distribution.
We observe that in all cases the values of p 1 /p are very close to 1/2. On the other hand, the probabilities of falling into A 2 γ are all below 10 −6 , which lead top hit valued smaller than 0.01. These results verify the conditions in Theorem 4 that explain the weak probabilistic efficiency of the IS estimator.

Illustration of Confidence Intervals
We investigate the performances of the CIs proposed in Section 5. In particular, we construct CIs (12) and (13) from probabilistically efficient estimators, namely the IS schemes using only the most significant point in Sections 3.1, 3.2 and 3.3. For convenience, we call interval (12) the "loose CI" and interval (13) the "tight CI", since the latter has a shorter length and matches the CLT-based interval. For comparison, we also construct CI (13) from asymptotically efficient estimators. In particular, for the settings in Sections 3.1 and 3.2, these estimators are built from mixtures of Table 11 Highly accurate point estimates (and 95% CI) using asymptotically efficient estimators for the problem in Section 3.1. The estimates are computed with 10 7 samples for m = 10, 30, 50 and 5 × 10 6 samples for m = 100.
In the experiments, we compare the coverage rates of all three intervals described above. These coverage rates are obtained from a large number of experimental repetitions. Since the ground truths of these problems are unknown, we run a gigantic amount of simulation runs using either asymptotically efficient estimators or crude Monte Carlo to obtain highly accurate estimates, which serve as the "truths" when estimating the coverage of the CIs. The exact number of simulation runs used in our ISs, number of experimental repetitions, and number of runs to approximate the ground truths are specified in the discussion of each example below.  Table 11. Our probabilistically efficient estimatorα(m) is computed using 10 4 independently generated samples. From this, we apply CIs (12) and (13). We also construct CIs (13) using asymptotically efficient estimatorβ(m) (which is used to approximate the ground truth) with 10 4 independently generated samples. We approximate the coverage rates using 10 5 experimental iterations. Moreover, we compute the average CI width for each type of CIs. The experiment results are shown in Table 12.
From Table 12, we observe that the coverage rates of tight CIs by our probabilistically efficient estimator are close to 95% in three out of the four cases, but is 3% below 95% in one case (m = 10).
On the other hand, the loose CIs are valid but perform conservatively with more than 99% coverage rates and wider average widths in all cases. The tight CIs by asymptotically efficient estimators provide valid coverage in all four cases. In the problems with rarer probabilities (i.e. m = 30, 50, 100), the tight CIs by probabilistically efficient estimators perform similarly as the CIs by asymptotically efficient estimators in terms of both CI width and coverage. This shows the competitiveness of CIs using probabilistically efficient estimators for rarer problems.
6.2.2. Overshoot Probability of a Random Walk. For the experiment in Section 3.2, we use the asymptotically efficient estimator that mixes all dominating points to approximate the Table 12 Coverage rates and average CI widths of the loose confidence intervals ("Loose CI by PE"), the tight confidence intervals ("Tight CI by PE") for probabilistically efficient estimators, and the tight confidence intervals for asymptotically efficient estimators ("Tight CI by AE") in the experiments of Section 3.  Table 13. Our probabilistically efficient estimator is computed using 10 4 independently generated samples. We construct CIs (12) and (13) based on this estimator. For comparison we also construct CI (13) from asymptotically efficient estimator using 10 4 samples independently generated from the ones used to approximate the ground truth. We use 10 5 experimental repetitions to estimate the coverage rates of all CIs. The coverage rates and average widths are presented in Table 14.
From Table 14, the loose CIs perform conservatively with near to 99% coverage rates in all cases.
On the other hand, the tight CIs constructed from our probabilistically efficient estimators have coverage rates below 95% in most of the cases. Moreover, as σ decreases (the probability become rarer), the coverage rates first drop from around 0.93 (with σ = 0.3) to around 0.89 (with σ = 0.2), then they improve as σ further decreases and reaches around 95% when σ = 0.1. The tight CIs by asymptotically efficient estimators have more stable coverage rates than the CIs by probabilistically efficient estimators, but also suffer under-coverage in several cases (e.g., 0.86 with σ = 0.28). We also observe that the tight CIs by the probabilistically efficient estimators have better average widths than the CIs by the asymptotically efficient estimators with smaller σ (e.g. σ = 0.1, 0.12).
The results show the validity of the CIs with probabilistically efficient estimators as σ → 0, but also that the coverage rate may not always monotonically improve as the problem becomes rarer.

MNIST Example.
For the experiment in Section 3.3, we use 10 10 runs of crude Monte Carlo to approximate the ground truths, which are shown in Table 15. Note that the estimate for σ = 0.17 is relatively less accurate than other estimates, revealed by the CI width in the magnitude of around 0.1 of the probability estimate. We obtain our probabilistically efficient estimator by generating 10 4 independent samples and construct CIs (12) and (13) based on this estimator. Since locating all dominating points to construct asymptotically efficient estimator is computationally infeasible in this example, we use IS estimators that mix the most significant 100 dominating points (the number of dominating points obtained from our sequential mixed integer programming procedure in Algorithm 2) as a proxy. We construct CI (13) from this estimator using 10 4 samples. Table 13 Higly accurate point estimates (and 95% CI) using asymptotically efficient estimators for the problem in Section 3.2. The estimates are computed with 10 7 samples.  We use 10 5 experimental repetitions to estimate the coverage rates and average widths of the CIs from probabilistically efficient estimators and 10 3 repetitions for the CIs from IS estimators using 100 dominating points (we use repetition size 10 3 instead of 10 5 because of the long computational time caused by a large number of mixtures in the IS distribution). The results are presented in Table 16.
From Table 16, we observe that in three out of the four cases, the tight CIs constructed from probabilistically efficient estimators provide coverage rates that are slightly below 95%. Similar to the previous random walk overshoot problem, the coverage rates are closer to 95% for rarer problems (e.g., the coverage is 94.9% for σ = 0.17). The under-coverage is alleviated when we use more than one dominating point, as shown in the row of "Tight CI by AE" (where we use 100 dominating points). On the other hand, the loose CIs have higher than nominal coverage rates in all cases, but are conservative since the rates are around 97.5% − 99.5%. Again, we observe the  Table 16 Coverage rates and average CI widths of the loose confidence intervals ("Loose CI by PE"), the tight confidence intervals ("Tight CI by PE") for probabilistically efficient estimators, and the tight confidence intervals for asymptotically efficient estimators ("Tight CI by AE") in the experiments of Section 3. validity of the CIs with probabilistically efficient estimators as the rare-event probability decreases, which validates our analysis.

Summary of Experimental Observations on Confidence Interval Construc-
tion. From the CI construction for the three examples in Section 3.1 investigated above, we draw several conclusions: 1) Tight CIs by probabilistically efficient estimators appear to have close to the nominal coverage rate when the problem is rare enough; 2) Loose CIs by probabilistically efficient estimators tend to over-cover, and also have correspondingly larger widths than other methods; 3) Tight CIs by asymptotically efficient estimators appear to give more accurate coverage rates for a larger range of rarity levels than the tight CIs by probabilistically efficient estimators, even though they could still under-cover in some cases; 4) When tight CIs by probabilistically efficient and asymptotically efficient estimators both have accurate coverage rates, their widths appear to be comparable. Overall, it appears that tight CIs by asymptotically efficient estimators are more robust with respect to the rarity level of the problem, which is also in line with the comparison between Theorems 8 and 9 (recall the discussion right after Theorem 9). Nonetheless, recall that one motivation of us proposing the notion of probabilistic efficiency is that asymptotically efficient estimators, which require using more dominating points in their mixtures, could be computationally challenging to construct.

Future Work
We conclude the paper with further discussions on the potential risk of the current framework and some future directions.

Developing Diagnosis for Finite-Sample Under-Estimation
Similar to the established notion of asymptotic efficiency in the rare-event simulation literature, our probabilistic efficiency framework is asymptotic. For a fixed rarity parameter γ and given simulation size n in practice, more work needs to be investigated to judge whether the obtained estimate is reliable or not. In particular, a risk of missing dominating points is finite-sample under-estimation.
To be more specific, we look at the following example.
Example 1. Suppose that our goal is to estimate p = P ( 1 γ X γ ∈ (−∞, −k] ∪ [1, ∞)) where X γ ∼ N (0, γ) and k > 1. In this case, the most significant dominating point is 1, so we consider choosing X γ ∼ N (γ, γ) as the IS distribution. That is, the IS estimator is Z = I( 1 γ X γ ∈ (−∞, −k] ∪ [1, ∞))e −Xγ +γ/2 with X γ ∼ N (γ, γ). We generate independent samples Z (1) , . . . , Z (n) and usep = 1 n n i=1 Z i to estimate p. When 1 < k < 3, the relative error of Z grows exponentially in γ (or − log p), so Z is not asymptotically efficient (see the proof of Proposition 2). On the other hand, from our previous derivations, Z is strongly probabilistically efficient, so we can still get a reliable estimate when γ is sufficiently large. However, in the finite-sample case where k is close to 1 and γ is not large, if n is chosen as a moderate size, then it could happen that {X ≤ −kγ} is not hit and hence we would get an estimate close to p 1 = P ( 1 γ X γ ≥ 1), but p 2 = P ( 1 γ X γ ≤ −k) is not negligible compared to p 1 . In other words, we under-estimate p. As a specific example, let k = 1.01 and γ = 16.
Example 1 shows that under finite parameter value and finite sample, it could be hard to tell whether we can safely drop less significant dominating points. A good aspect about the conclusion in this example, however, is that the under-estimation is arguably acceptable in relative term (i.e., the estimate is still in the same magnitude as the ground truth), pointing to an estimation resembling weak probabilistic efficiency. We should emphasize that a similar concern applies to asymptotically efficient estimators as well. That is, it is difficult to guarantee whether the sample size n is large enough to give a reliable estimate for a given setup and rarity parameter value.
Nevertheless, increasing n would improve the performance of asymptotically efficient estimators, but for probabilistic efficiency, we do not have the luxury of increasing n since our framework requires n to be moderate in size. This points to more need of developing diagnostic methods to detect under-estimation due to finite-sample effects in the future.

Further Developing Theory of IS with Missed Dominating Points
Despite the presence of under-estimation risks described above, we maintain our motivation of probabilistic efficiency as a theory to allow one to use few dominating points in problems where finding all of them is infeasible. In fact, what we have focused on in this paper is only one theory where dropping dominating points is valid, among other possibilities. To support this, we revisit Example 1: Example 2 (Example 1 continued). Consider the problem setting in Example 1. When k ≥ 3, the relative error of Z grows only polynomially in γ (or − log p), and hence Z is asymptotically efficient (see the proof of Proposition 2). The intuitive explanation is thatp 2 =P ( 1 γ X γ ≤ −k) is extremely small which mitigates the blow-up of the likelihood ratio. More rigorously, when , and henceẼ(Z 2 )/p 2 = Θ( √ γ) which grows polynomially in − log p = Θ(γ).
Example 2 shows that sometimes the missed dominating points are so rare that missing them does not even harm the asymptotic efficiency. Here, explaining the validity of IS with missed dominating points does not require probabilistic efficiency, but instead an alternate analysis of asymptotic efficiency that is tighter than the standard approach in the literature. Nonetheless, this phenomenon does not apply to our proposed estimators in Sections 3 and 6, as we have mathematically verified the asymptotic inefficiency in our considered estimator in each example.
More generally, we conclude our paper with Figure 4, which shows the relations among different efficiency criteria and IS with missed dominating points. In this paper, we have built sufficient conditions to achieve strong probabilistic efficiency with missed dominating points. Example 2, on the other hand, gives an example in achieving asymptotic efficiency with missed dominating points. Our immediate future endeavor is to fill in the regions in Figure 4 that are not covered by the current work, including the scenario depicted by Example 2, relaxing the current sufficient conditions of probabilistic efficiency to allowp 2 to be less tiny, achieving weak instead of strong probabilistic efficiency with missed dominating points, and moreover, to understand the "complementary" regions where missing dominating points would be guaranteed to violate the efficiency notions. In summary, this work serves as a first step in a new line of analysis aiming to relax existing variance-based efficiency criteria in rare-event simulation to be applicable to larger-scale and more complex problems.

Appendix A: Algorithms
Algorithm 1 shows a procedure to obtain dominating sets. We briefly explain the idea here. First we minimize I(x) over x ∈ E and get the first dominating point a 1 . If E ⊂ {x ∈ R d : s a 1 (x−a 1 ) ≥ 0}, then we know that {a 1 } is a dominating set and hence we could stop. Otherwise, we minimize I(x) over x ∈ E \ {x ∈ R d : s a 1 (x − a 1 ) ≥ 0} to get the second dominating point a 2 . Then we check whether E ∈ By repeating this process, we would finally get a dominating set A = {a 1 , . . . , a r } with I(a 1 ) ≤ · · · ≤ I(a r ).
Algorithm 1: Sequentially find all the dominating points. Input: Rarity parameter γ, rare-event set E ⊂ R d , rate function I(y), function a → s a .
Output: Dominating set A.
Find a dominating point a r+1 by solving the optimization problem a r+1 = arg min

Appendix B: A New Alternative Asymptotic Regime and Theoretical Guarantees
In this section, we investigate a new regime that A γ = {X ∈ E} and E = {x ∈ R d : g(x) ≥ γ} where X ∈ R d and g : R d → R is a function. We propose this setting as it arises as a generic representation of recent problems in intelligent system safety testing (Bai et al. 2022). There, g could be highly complicated and leads to a gigantic number of dominating points, which in turn motivates the consideration of dropping most of them and our notion of probabilistic efficiency. We note that technically this setting is slightly different from the classical Gartner-Ellis regime in terms of the position of the scaling parameter γ (see, e.g. Sadowsky and Bucklew 1990), but conceptually similar.
In Section B.1, we adapt the notions of rate function and dominating points to this new regime. Then we state the assumptions under which we could build on Theorem 3 to obtain reliable point estimates and CIs as in Section 5. We note that this new regime is harder to analyze as the rare-event set E can change in a complicated way with γ, and thus inevitably our assumptions are relatively restrictive and need to be verified case by case. In Section B.2, we consider the special (but important) case where X follows a Gaussian distribution and g is piecewise linear, in particular propose a simple stopping strategy to determine whether it is safe to stop searching for the remaining dominating points. Throughout this section, we write α(γ) ∼ β(γ) if α(γ)/β(γ) is subexponential in − log p(γ).

B.1. Guarantees for General Input Distribution
We define µ(x) = log Ee x X , x ∈ R d as the cumulant generating function of X and I(y) = sup x∈R d {x y − µ(x)}, y ∈ R d as its Legendre transform. For any set E ⊂ R d , we denote I(E) = inf y∈E I(y). Parallel to Assumptions 1 and 2, we make the following two assumptions.
The concepts of dominating set and dominating points are also similar, but now they change with γ: Definition 5 (Dominating Set (New Regime)). Suppose that Assumptions 3 and 4 hold. We call For each a ∈ A, there exists a unique s a ∈ R d such that ∇µ(s a ) = a; 2. E ⊂ a∈A {x ∈ R d : s a (x − a) ≥ 0}; 3. A \ {a} does not satisfy the first two conditions for any a ∈ A.
We call any point in A a dominating point. For two dominating points a and a , we say a is more significant than a if I(a) < I(a ).
Suppose that A = {a 1 , . . . , a r } is a dominating set. Then the corresponding mixture IS distribution is given Like the discussion in Section 2, we could split the rare-event set as E = r i=1 E i where E i 's are disjoint and a i ∈ E i ⊂ {x ∈ R d : s a i (x − a i ) ≥ 0}. Note that s a i (x − a i ) ≥ 0 still implies that I(x) ≥ I(a i ). Now, the likelihood ratio is given by L(ω) := dP dP (ω) = 1 r i=1 α i e s a i X−µ(sa i ) and it satisfies that for any i, Hence we have that Thus, supposing we have a large deviations asymptotic given by p = P (X ∈ E) ∼ e − min i I(a i ) , then combining with (15) will give us that the IS estimator is asymptotically efficient.
Now we consider using a partial list of dominating points. In particular, we can still sequentially fill in the dominating set A = {a 1 , . . . , a r } where a i = arg min{I(y) : y ∈ E, s a j (y − a j ) < 0, j = 1, . . . , i − 1} and hence I(a 1 ) ≤ · · · ≤ I(a r ), and suppose that we have a stopping strategy k = k(γ) with 1 ≤ k ≤ r before locating all the dominating points. We choose the mixture IS distribution given by Unlike in (11), we no longer assign an individual weight α i to each dominating point a i . Instead, we only consider the uniform mixture for simplicity, since now the number of dominating points r and k can both potentially change with γ.
First of all, we summarize the basic assumptions on the problem setting to ensure that there exists a dominating set with moderate size: Assumption 5. Consider the problem of estimating p = P (X ∈ E) with E = {x ∈ R d : g(x) ≥ γ} where X ∈ R d is a random vector and g is a function. Assume that 1. p → 0 as γ → ∞; 2. Assumption 3 holds for the cumulant generating function of X under P ; 3. Assumption 4 holds for E; 4. For any γ, there exists a dominating set for E, denoted as A = {a 1 , . . . , a r } where a i = arg min{I(y) : y ∈ E, s a j (y − a j ) < 0, j = 1, . . . , i − 1} and hence I(a 1 ) ≤ · · · ≤ I(a r ). Besides, r = r(γ) grows at most subexponentially in − log p.
Now consider a stopping strategy k = k(γ) and the corresponding IS distribution (16). Under Assumption Corresponding to the settings in Theorem 3, we let A j γ = {X ∈ E j }, j = 1, 2. We introduce Assumptions 6 and 7.
Roughly, Assumption 6 implies that p 2 is exponentially smaller than p 1 and Assumption 7 implies that E 2 is hardly hit even underP . Applying Theorem 3, we have that Theorem 12 (Attaining probabilistic efficiency with a partial list of dominating points (new regime)).
Similar to Section 5, we can also construct asymptotically valid CIs with the sample mean and sample variance.
Similar to Section 5, the CI in Theorem 13 is more conservative than the CLT-based intervalp±z 1−α/2 V n . If additionally the following assumption holds, then the CLT-based CI is also asymptotically valid: Similar to Lemma 2, Assumption 8 serves to control the Berry-Esseen error bound. To be more concrete, with this additional assumption, we have: Theorem 14 (Constructing tight confidence intervals (new regime)). Assume that Assumptions 5, 6, 7 and 8 hold. The IS estimator is Z = I(X ∈ E) dP dP (ω) underP given by (16). We sample X (1) , . . . , X (n) i.i.d. fromP and let Z (i) = I(X (i) ∈ E) dP dP , Z (i) 1 = I(X (i) ∈ E 1 ) dP dP , i = 1, . . . , n. Usep andV to respectively denote the sample mean and sample variance of Z (i) 's. In this case, we could choose n subexponentially growing in − log p such that k 2 e −2I(a 1 ) That is,p ± z 1−α/2 V n is an asymptotically valid (1 − α)-level CI for p.
In the above, Assumptions 5, 6, 7 and 8 are technical conditions that need to be analyzed case by case.
The next Section B.2 focuses on a specific but important problem setting where we show how to verify all these conditions.

B.2. Guarantees for Gaussian Input Distribution
. Moreover, we suppose that g is a piecewise linear function. Related theoretical guarantees for piecewise linear function of Gaussian input can be found in Bai et al. (2022).
We use the following natural stopping strategy. First, fix a constant C > 1. Then, we sequentially find the dominating points where we stop as long as (a k+1 − λ) there is no such k, then we let k = r, the number of all dominating points. The IS distribution is chosen as . We summarize these in Algorithm 2. We have the following theorem suggesting that under the above setting, all the assumptions listed in Section B.1 are satisfied.
Find a dominating point a k+1 by solving the optimization problem Update k ← k + 1; 8 End 9 Sample X 1 , . . . , X n from the mixture distribution 1 k k i=1 φ(x; a i , Σ). 10 Compute the IS estimatep = 1 n n i=1 I(g(X i ) ≥ γ)L(X i ) where the likelihood ratio function is .
Theorem 15 (Verification of assumptions for Gaussian inputs). Suppose that X ∼ N (λ, Σ) under P where λ ∈ R d and Σ ∈ R d×d is positive definite. E = {x ∈ R d : g(x) ≥ γ} where g is a piecewise linear function. C > 1 is a constant. Assume that for any γ, P (X ∈ E) > 0 and λ / ∈ E. For any γ, we use the stopping strategy described above (more precisely Algorithm 2) to sequentially find dominating points a 1 , a 2 , . . . , a k in decreasing significance and set up the IS distribution X ∼ 1 and E 2 = E \ E 1 . Then Assumptions 5, 6, 7 and 8 hold.
Note that in Theorem 15, all assumptions including Gaussianity and piecewise linear g are all straightforward to verify. With Theorem 15, we thus get the following corollaries from Theorems 12, 13 and 14: Corollary 1 (Probabilistic efficiency for Gaussian inputs). Under the settings in Theorem 15, the IS estimator Z = I(X ∈ E) dP dP is strongly probabilistically efficient.
Corollary 2 (Confidence intervals for Gaussian inputs). Under the settings in Theorem 15, we sample X (1) , . . . , X (n) i.i.d. fromP and let Z (i) = I(X (i) ∈ E) dP dP . Usep andV to denote the sample mean and sample variance of Z (i) 's. We could choose n subexponentially growing in − log p such that for any 0 < α < 1, Corollary 3 (Tight confidence intervals for Gaussian inputs). Under the settings in Theorem 15, we sample X (1) , . . . , X (n) i.i.d. fromP and let Z (i) = I(X (i) ∈ E) dP dP . Usep andV to denote the sample mean and sample variance of Z (i) 's. We could choose n subexponentially growing in − log p such that for any While the choice of C (as long as it is > 1) does not affect the guarantee on strong probabilistic efficiency or the asymptotic validity of the CIs, it does affect the accuracy of the estimates for a given, finite γ. In particular, it is often the case that in practice we only need to solve one problem for a fixed γ instead of solving a series of problems with varying γ. In this scenario, as long as (a 2 − λ) we can pick a C > 1 such that we would stop our dominating point search at k = 1, i.e., use only the first point. Note that this does not imply that for this choice of C we have k = 1 for any γ. Thus, the finiteness of the rarity parameter comes into play in a subtle way.

Appendix C: Proofs
Proof of Theorem 2. First, we know that I(a i ) = s a i a i − µ(s a i ) for i = 1, . . . , r. For any Thus, for any x ∈ E, there exists i such that s a i (x − a i ) ≥ 0, and hence I(x) ≥ I(a i ). Therefore, I(E) = inf x∈E I(x) ≥ min i=1,...,r I(a i ). On the other hand, a 1 , . . . , a r ∈ ∂E ∩ D(I) • and I is differentiable in D(I) • , so I(E) ≤ min i=1,...,r I(a i ). Overall we have I(E) = min i=1,...,r I(a i ).
Proof of Proposition 1. We could split the rare-event set as . Now, the likelihood ratio is given by α i e s a i Xγ −γµγ (sa i ) and it satisfies that for any i, Hence we have that and Thus, using Theorem 1, we have that which verifies that the IS estimator is asymptotically efficient.
Proof of Proposition 2. We derive the growth rate of the relative error for a more general case. Suppose under P and the IS distribution is chosen as X γ ∼ N (γ, γ) underP . This is the setup of Examples 1 and 2. There are two dominating points, 1 and −k, and 1 is the more significant one. Under the IS distribution, the likelihood ratio is L = e −Xγ +γ/2 and the IS estimator is whereΦ denotes the tail distribution function of standard normal distribution. It is known thatΦ(x) = Θ( 1 x e −x 2 /2 ) as x → ∞, and henceẼ( Proofs of Propositions 4 and 5. We first show a general result on IS estimator that exponentially tilts to the most significant dominating point. Consider a rare-event set E with a 1 as the most significant dominating point. We estimate the target rare event { 1 γ X γ ∈ E} using the IS estimator with likelihood ratio L = 1 e s a 1 Xγ −γµγ (sa 1 ) .
By definition, the IS estimator is not asymptotically efficient if and only if min y∈E (y + a 1 − 2λ) Σ −1 (y + In order to check the existence ofỹ such that (ỹ + a 1 − 2λ) Σ −1 (ỹ + a 1 − 2λ) < 4(a 1 − λ) Σ −1 (a 1 − λ), we can formulate the following optimization and check whether the objective is negative for the optimal (or any feasible) solution. Since the objective function is quadratic on the decision vector y, the tractability of the optimization problem (18) is determined by the feasible region E. In the example in Section 3.2, we have Since each H m is a half-space and hence convex, we can independently solve min y∈Hm (y + a 1 − 2λ) Σ −1 (y + a 1 − 2λ) − 4(a 1 − λ) Σ −1 (a 1 − λ), for m = 1, ..., d. Since the feasible region of the above optimization associated with any H m is a subset of the original problem (18), any solution with negative objective indicates that the IS estimator with dominating points a 1 is not asymptotically efficient. In the example in Section 3.3, we formulate the problem (18) as a mixed integer programming problem following the treatment of the rare-event set formed by machine learning predictors in Bai et al. (2022). Using this approach, we can show that the IS estimators with the most dominating points are not asymptotically efficient for both examples considered in Sections 3.2 and 3.3.
To prove Theorem 7, we need the following lemma:

Now we prove Theorem 7:
Proof of Theorem 7. Following the notation in Section 4, we split p 1 andV 1 respectively denote the sample mean and sample variance of Z Similar to the derivation of (17), we know that 0 ≤ Z (i) 1 /M γ respectively, we get that P   p 1 >p 1 + 2V 1 log(4/δ) n + 7 log(4/δ)M γ 3(n − 1) Find α = α (γ) such that 7 log(4/α )M γ 3(n − 1) That is, Clearly α > α and log(4/α ) < log(4/α). From the proof of Theorem 6, we have that either (i) k = r and p 2 = 0 or (ii) k < r and lim sup γ→∞ 1 γ log p 2 ≤ −I(a k+1 ) < −I(a 1 ). Moreover, we have 1 Thus, for subexponentially growing n, we have 3(n−1)p 2 7Mγ → 0 and hence α → α as γ → ∞. We replace δ with α in (19), and then we getP Therefore,P   |p − p| > 2V log(4/α) n + 7 log(4/α)M γ 3(n − 1) To prove Theorem 8, we first prove a lemma regarding the variance V ar(Z 1 ). In particular, we have assumed that V ar(Z 1 ) cannot be "too large", while this lemma implies that it cannot be "too small" as well. As we will see, this lemma is used to control the error of the normal approximation in analog to the Berry-Esseen theorem in order to argue the validity of I 2 .

Then we get thatP
First, we have thatẼ|Z . From the proof of Theorems 6 and 7, we know that − 1 γ log p 1 → −I(a 1 ) and − 1 γ log M γ → −I(a 1 ). Thus lim sup γ→∞ 1 γ logẼ|Z (1) 1 − p 1 | 3 ≤ −3I(a 1 ). By Lemma 2, we get thatẼ grows at most subexponentially in γ. Hence under the assumptions we could choose n as required in the theorem. In particular, we have that

2CẼ|Z
(1) Now we analyze x. We know that  .
Proof of Theorem 10. The conclusion follows from Theorem 5, by checking, for each setting in Sections 3.1, 3.2 and 3.3, Assumptions 1 and 2 hold and the most significant dominating point is unique. Since we have µ(x) = 1.5x + 0.5x 2 − log(1 + x) for the case in Section 3.1 and µ(x) = λ x + 1 2 x Σx for the cases in Sections 3.2 and 3.3, we verify the conditions in Assumption 1. On the other hand, since all rare-event sets in these examples are closed and contain unique optimal solutions for minimizing the corresponding rate function I(x), we can verify Assumption 2 and the uniqueness of most significant dominating point.
Proof of Theorem 11. We check the three conditions in Theorem 4 to show the probabilistic efficiency of the IS estimator using the dominating point a 1 . Using the notation in Section 6.1.4, we note that A 1 γ only one most significant dominating point a 1 and A 2 γ only one most significant dominating point −a 1 , while I(a 1 ) = I(−a 1 ). This indicates that p 1 /p 2 → 1 as γ → ∞ and hence p 1 /p → 1/2 as γ → ∞. Then, following the argument in Section 6.1.2, the IS estimator using the dominating point a 1 is asymptotically efficient for A 1 γ . Lastly we havep 2 → 0 exponentially fast and hence we have np 2 → 0 with subexponentially growing sample size n. We conclude that the IS estimator using the dominating point a 1 is weakly probabilistically efficient.
On the other hand, based on Proposition 4, the IS estimator using the dominating point a + is not asymp- Proof of Theorem 12. We only need to verify the conditions in Theorem 3. First, from Assumption 6, we get that p 2 is exponentially smaller than p 1 , and hence p 1 p → 1 as γ → ∞. Second, Let Z 1 = I(X ∈ E 1 ) dP dP underP . Clearly {a 1 , . . . , a k } is a dominating set for E 1 . Similar to (15), we get that V ar(Z 1 ) ≤ k 2 e −2I(a 1 ) ≤ r 2 e −2I(a 1 ) . Assumption 6 gives that p 1 ∼ e −I(a 1 ) , and hence Z 1 is an asymptotically efficient estimator for p 1 . Third, Assumption 7 implies that np 2 → 0 for any n subexponentially growing in − log p. Therefore, all the conditions in Theorem 3 hold.
By Berry-Esseen theorem, we know that for any x ∈ R P   √ n(p 1 − p 1 ) V ar(Z  .
Finally, it is clear that the number of dominating points will not grow exponentially in − log p = Θ((a 1 − λ) Σ −1 (a 1 − λ)). Therefore, Assumption 5 is satisfied in this problem setting.