Robust Importance Sampling for Rare Events via Constrained Gaussian Mixtures

Paweł Lorek; Rafał Nowak; Rafał Topolnicki; Tomasz Trzciński; Maciej Zięba

cs.LGOct 5, 2026

Robust Importance Sampling for Rare Events via Constrained Gaussian Mixtures

Authors: Paweł Lorek, Rafał Nowak, Rafał Topolnicki, Tomasz Trzciński, Maciej Zięba

Organizations: University of Wrocław · Tooploox · TRAILS University of Warsaw · Warsaw University of Technology · IDEAS Research Institute · Wrocław University of Science and Technology

Abstract

We study estimating rare-event probabilities $I = \mathbb{P}(g(\mathbf{X}) > γ)$ with $\mathbf{X} \sim \mathcal{N}(\boldsymbolμ, \boldsymbolΣ)$ and general $g : \mathbb{R}^d \to \mathbb{R}$ . We address this problem through importance sampling, and propose a framework that substantially improves efficiency and robustness over baselines such as crude Monte Carlo, adaptive cross-entropy, variational-inference-based methods (including reverse- and forward-KL approaches), as well as Safe-ICE, Subset Simulation, and Sequential Monte Carlo, drawing on ideas from both rare-event estimation and cross-entropy optimization. The key contribution has two parts: first, we separate the problem into coverage, to overcome the cold-start barrier, and fitting, to refine proposals once a meaningful signal is available; second, we constrain the final GMM proposal so that it has finite importance-sampling variance (since coverage alone is not sufficient -- without safeguards, importance sampling may still suffer from infinite variance). Together, these ingredients yield expressive proposals; finite variance does not by itself guarantee practical stability at a fixed sampling budget. Extensive experiments demonstrate substantial variance reduction, strong robustness across diverse benchmarks, and favorable cost--efficiency trade-offs, with the proposed approach often outperforming these baselines, particularly in high-dimensional and multimodal settings where competing methods frequently become unstable or fail. Our code is available at https://github.com/lorek/robust-cfi-is.

Figures & tables

{\small\boldsymbol{\theta}^{\prime}_{t}=\arg\max_{\boldsymbol{\theta}}\frac{1}{M}\sum_{i=1}^{M}{\mathbbm{1}}\!\big(g(\mathbf{X}_{i})\geq\gamma_{t}\big)\log p_{\boldsymbol{\theta}}(\mathbf{X}_{i})}

Algorithm 1 CFI: Coverage-First Initialization

$g$	$d$	$I_{\rm true}$	Best baseline by CoV			Best finite-var. method			Best proposed overall
			Method	log-err $\downarrow$	CoV $\downarrow$	Method	log-err $\downarrow$	CoV $\downarrow$	Method	log-err $\downarrow$	CoV $\downarrow$
$g_{1}$	2	4.79e-6	CMC	1.43e+00	3.92e-03	CFI-c+RKL-c	6.26e-03	7.24e-03	CFI-c+FKL-c+F	3.16e-03	3.92e-03
$g_{2}$	2	2.23e-3	CMC	4.14e-02	2.46e-03	CFI-c+FKL-c	3.39e-03	4.85e-03	CFI-c+RKL-c+F	2.87e-03	1.86e-03
$g_{3}$	2	4.21e-3	CMC	4.25e-02	3.31e-03	CFI-c+FKL-c	3.25e-03	4.35e-03	CFI-c+FKL-c+F	2.80e-03	3.31e-03
$g_{5}$	40	3.15e-5	fRKL-c	7.31e-02	3.19e-02	CFI-c+RKL-c	7.28e-02	4.30e-02	CFI-c+RKL-c+F	6.45e-02	2.99e-02
$g_{6}$	100	2.33e-4	fRKL-c	5.90e-03	6.08e-03	CFI-c+RKL-c	7.02e-03	6.12e-03	CFI-c+RKL-c+F	5.94e-03	5.43e-03

Table 2: Best methods by CoV at

R=10^{5}

simulator evaluations: baseline (CMC, fFKL-c, fRKL-c, CFI-u, AMS, Subset), theorem-covered proposed method with a final constrained GMM, and proposed method overall. Bold marks the overall lowest CoV.

Method	$g_{1}$	$g_{2}$	$g_{3}$	$g_{5}$	$g_{6}$	$g_{7}$	$g_{10}$
CMC	16	0	0	1	0	0	0
fRKL-c	0	0	0	0	0	0	0
fFKL-c	0	0	0	0	0	0	0
CFI-u	20	20	19	0	20	20	0
CFI-c	0	0	0	0	0	0	0
CFI-c+RKL-c	0	0	0	0	0	0	0

Table 3: Failure counts over 20 independent runs. This table measures reliability rather than conditional accuracy on successful runs.

Method	Estimate	Var. reduction	log-error	CoV
fRKL-d, $\lambda=0.1$	4.773e-06	1.73e+03	5.06e-02	7.53e-02
fRKL-c	4.80e-06	2.95e+04	1.59e-02	1.82e-02
CFI-c+RKL-c	4.79e-06	1.87e+05	6.26e-03	7.24e-03
CFI-c+RKL-c+F	4.79e-06	7.77e+05	3.55e-03	3.95e-03

Table 4: Comparison with Hesterberg-style defensive importance sampling on

g_{1}

using

K=16

R=10^{5}

, and 20 independent evaluation runs. The non-defensive rows are reproduced from Table 6 .

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

\widehat{\nabla}_{\boldsymbol{\theta}}L_{t}=\frac{1}{M}\sum_{i=1}^{M}(1+\eta_{i}-b_{t-1})\,\nabla_{\boldsymbol{\theta}}\log p_{\boldsymbol{\theta}}(\mathbf{X}_{i})\Big|_{\boldsymbol{\theta}=\boldsymbol{\theta}^{\prime}_{t-1}}

Appendix

Algorithm 2 RKL – Reverse-KL (Variational Inference)

Table 8

Model		Optimum	IS variance
${\mathcal{N}}\,(\mu,1)$	FKL	$\mu^{*}=4.2256$	$4.5162\cdot 10^{-9}$
${\mathcal{N}}\,(\mu,1)$	RKL ( $\tau=0.1$ )	$\mu^{*}=4.2036$	$4.5045\cdot 10^{-9}$
${\mathcal{N}}\,(\mu,\sigma^{2})$	FKL	$(4.2256,\,0.0467)$	$\infty$
${\mathcal{N}}\,(\mu,\sigma^{2})$	RKL ( $\tau=0.1$ )	$(3.2782,\,0.4306)$	$\infty$

Appendix

Table 5: Motivating example: optimal proposals obtained by FKL and RKL and the resulting IS variance for

{\mathbb{P}}\,(X>4)

Method	Estimate	Var. reduction	log-error	CoV
fRKL-d, $\lambda=0.1$	4.773e-06	1.73e+03	5.06e-02	7.53e-02
fRKL-d, $\lambda=0.2$	4.810e-06	1.71e+03	6.52e-02	7.55e-02
fRKL-d, $\lambda=0.3$	4.866e-06	1.07e+03	8.54e-02	9.33e-02
fRKL-d, $\lambda=0.4$	4.828e-06	1.03e+03	6.24e-02	9.49e-02
fRKL-d, $\lambda=0.5$	4.955e-06	8.29e+02	8.66e-02	9.76e-02

Appendix

Table 12: Sensitivity of the Hesterberg-style defensive baseline on

g_{1}

with

K=16

R=10^{5}

, and 20 independent evaluation runs.

(a) Total training time
Method	$g_{1}$ ( $d=2$ )	$g_{6}$ ( $d=100$ )
fFKL-c	$\sim 3000$	$\sim 1570$
fRKL-c	$\sim 55$	$\sim 340$
CFI-c	$\sim 5$	$\sim 8$
CFI-c+FKL-c	$\sim 60$	$\sim 234$

Appendix

Table 13: Indicative training times in seconds. Panel (a) reports total training time; panel (b) reports separately measured operations on

g_{7}

Method	log-err	CoV	log-err/var_red
CMC	3.89e-01	1.45e-01	3.89e-01
CFI-c	1.42e-01	1.34e-01	3.48e-02
CFI-c+RKL-c	1.57e-02	6.79e-03	5.37e-06
CFI-c+FKL-c	1.76e-01	1.45e-01	9.89e-02

Appendix

Table 14: Scalability experiment on the high-dimensional ResNet benchmark (

d=174

K=16

). Results are averaged over 20 independent seeds.

Figure 3: Variance reduction ( $y$ -axis) relative to CMC, as a function of the smoothing parameter $\tau$ ( $x$ -axis) for RKL-c (red) and RKL-u (blue).

$\rho$	CoV	$\text{log-err}/\text{var\_red}$
0.05	$4.28\cdot 10^{-2}$	$6.40\cdot 10^{-4}$
0.10	$4.02\cdot 10^{-2}$	$4.23\cdot 10^{-4}$
0.25	$4.30\cdot 10^{-2}$	$4.88\cdot 10^{-4}$
0.30	$3.76\cdot 10^{-2}$	$3.02\cdot 10^{-4}$
0.50	$3.81\cdot 10^{-2}$	$4.10\cdot 10^{-4}$

Appendix

Table 15: Sensitivity to

\rho

for CFI-c+RKL-c on

g_{5}

(

d=40

), with fixed

\alpha=0.75

$\alpha$	CoV	$\text{log-err}/\text{var\_red}$
0.25	$4.77\cdot 10^{-2}$	$4.44\cdot 10^{-4}$
0.50	$4.62\cdot 10^{-2}$	$4.90\cdot 10^{-4}$
0.75	$4.30\cdot 10^{-2}$	$4.88\cdot 10^{-4}$
0.90	$3.86\cdot 10^{-2}$	$3.95\cdot 10^{-4}$

Appendix

Table 16: Sensitivity to

\alpha

for CFI-c+RKL-c on

g_{5}

(

d=40

), with fixed

\rho=0.25

Panel of Figure 4 — Figure 4: Multimodal example: contour plot with gradient field (left) and surface plot (right). Gradient ascent trajectories initialized near the origin are attracted to $\boldsymbol{\mu}_{1}$ and $\boldsymbol{\mu}_{2}$ , while $\boldsymbol{\mu}_{3}$ has a very small basin of attraction.

Figure 5: Runaway example: the function grows unbounded in certain directions, causing gradient ascent trajectories to diverge instead of approaching relevant level sets.

Benchmark	Dimension $d$	Input	Threshold $\gamma$	Reference ${\mathbb{P}}\,(g(\mathbf{X})>\gamma)$
$g_{1}$	2	A	0	4.7934e-6
$g_{2}$	2	A	0	2.22668e-3
$g_{3}$	2	A	0	4.2073e-3
$g_{5}$	40	A	-403.6636	3.1500e-5
$g_{6}$	100	A	3.5	2.3262e-4
$g_{7}$	62	A	5.15715	6.00e-5

Appendix

Table 17: Summary of benchmark settings used in the experiments.

Panel of Figure 6 — Figure 6: Evolution of the proposal distribution during training for estimating ${\mathbb{P}}\,(g_{1}(\mathbf{X})>0)$ with $\mathbf{X}\sim{\mathcal{N}}\,(\boldsymbol{\mu}^{(A)},\boldsymbol{\Sigma}^{g_{10}})$ and $K=6$ . Top to bottom: CFI-c, FKL-c initialized from CFI-c, and the subsequent flow-based refinement (+Flow).

Panel of Figure 7 — Figure 7: Selected snapshots from fFKL-c training for estimating ${\mathbb{P}}\,(g_{1}(\mathbf{X})>0)$ with $\mathbf{X}\sim{\mathcal{N}}\,(\mathbf{0},I_{2})$ .

Explore similar work

Rare Event Estimation via Iterative Unalignment
Sep 21, 2026Hanming Yang, Daksh Mittal, Jing Dong +1Rare Events Monte Carlo
Decision, Risk, and Operations Division, Columbia Business School
Steering Diffusion Models to Rare Events with Sequential Monte Carlo
Oct 6, 2026Aavash Subedi, Tim Reichelt, Christopher Williams +3
Department of Statistics University of Oxford · Department of Physics University of Oxford · Department of Statistics University of British Columbia
Pliable rejection sampling
Apr 24, 2026Akram Erraqabi, Michal Valko, Alexandra Carpentier +1Rejection Sampling Rejection
MILA, Universit´e de Montr´eal, Montr´eal, QC H3C 3J7, Canada · INRIA Lille - Nord Europe, SequeL team, 40 avenue Halley 59650, Villeneuve d’Ascq, France · Institut für Mathematik, Univertät Potsdam, Germany, Haus 9 Karl-Liebknecht-Strasse 24-25, D-14476 Potsdam +1

Sep 21, 2026, cs.LGJ/K move · Enter open · S save

Rare Event Estimation via Iterative Unalignment

Hanming Yang, Daksh Mittal, Jing Dong, Hongseok Namkoong

Decision, Risk, and Operations Division, Columbia Business School

Rare Events Monte Carlo Stochastic

Open paper AskPDF arXiv

As agents are deployed with increased autonomy, even extremely rare events along their stochastic output trajectories can occur and prove catastrophic. Safe deployment therefore does not depend on whether these events can occur, but on how often they might. We study the problem of estimating the probability of rare events that arise from stochastic variation in the agent's own actions. Estimating this type of risk requires searching over the combinatorially vast space of trajectories. Naive Monte Carlo is computationally prohibitive in this regime, and constructing effective importance sampling (IS) proposals requires coordinated changes to a context-dependent chain of conditional distributions. We develop a new IS method that perturbs the original model's weights to construct the proposal. The proposal is itself a differentiably parameterized language model, enabling gradient-based search over weight space. We formulate an objective that combines a differentiable surrogate for event amplification and an adaptive regularization scheme that dynamically balances amplification against estimator stability. We evaluate our approach on

\sim

120M and

\sim

2.6B models across three event families spanning 300+ rare events as rare as

10^{-9}

, with reference probabilities computed with

<10\%

relative standard error. In our most verifiable settings, we observe that our IS estimator achieves over

800\times

compute-weighted efficiency gains over naive Monte Carlo for events with probabilities lower than

10^{-7}

. Our implementation is available at https://github.com/namkoong-lab/iterative-unalignment.

Abstract

Explore similar work

Rare Event Estimation via Iterative Unalignment

Steering Diffusion Models to Rare Events with Sequential Monte Carlo

Pliable rejection sampling