Generalizing self-normalized importance sampling with couplings
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.
Tom: We're looking at the paper: "Generalizing self-normalized importance sampling with couplings".
Paper summary: Tom: So we're looking at this paper titled "Generalizing self-normalized importance sampling with couplings." Essentially, they're tackling a huge problem in statistics and machine learning: estimating expectations when you can't write down the normalizing constant for your probability density function.
Jane: That sounds really abstract. What does that mean for us in practice? Is this about making our models run faster or just getting better numbers?
Tom: It's about variance reduction. They take the self-normalized importance sampling, which is the standard way to handle these tricky estimation problems, and they show it can have really high variance when you're dealing with rare events or posterior predictive distributions in Bayesian statistics <ref:2406.19974#pg2>.
Lu: The core idea they push is reframing the task not as estimating one expectation, but as estimating a ratio of two integrals instead <ref:2406.19974#pg3>. This new framework lets them get samples from a joint proposal distribution in an extended space, where two of the marginals act like proposals for each integral they need to estimate.
Meng: A ratio of two integrals sounds complicated. If this is about variance reduction, what's the actual payoff on a production system? Does it mean we can run these complex Bayesian models without needing ten times more samples?
Lalam: From my perspective, this paper is focused on providing guidance for minimizing the asymptotic variance of an estimator when you have unnormalized PDFs <ref:2406.19974#pg2>. It lays out a way to decompose that variance into three terms, which lets you target the third term for reduction based on how correlated your numerator and denominator estimates are.
Jane: So they’re suggesting we can use this structure to improve the standard self-normalized importance sampling estimator without necessarily changing the basic sampling process too much. That's a big idea because it builds on existing adaptive importance sampling methods <ref:2406.19974#pg2>.
Tom: Exactly. The paper proposes a two-stage optimization strategy to adapt those marginals using any existing method, and then in a second stage, you choose the coupling between them to maximize that variance reduction term <ref:2406.19974#pg3>. That sounds like a lot of tuning for an engineer.
Lu: They concretely suggest specific couplings, like multivariate normal or student t couplings, and they propose using first-order stochastic optimization to select the coupling in the second stage <ref:2406.19974#pg3>. This gives us something tangible to work with instead of just a theoretical decomposition.
Meng: If we're looking at deployment, how hard is it to implement this two-stage process? Does it require a lot of upfront modeling effort before you even start sampling? I'm worried about the computational cost at scale <ref:2406.19974#pg2>.
Lalam: The paper shows that this framework puts things under a unifying umbrella for ratio estimation using importance sampling, generalizing older works that either didn't introduce dependence, were restricted to specific marginal families, or used restricted types of dependence <ref:2406.19974#pg3>. This suggests it could be applicable across different modeling scenarios.
Paper summary: Jane: It seems like the real value here is in how it structures the problem so we can systematically look for variance reduction, rather than just tweaking parameters randomly to see if something improves. That's a shift from trial and error to a more guided approach <ref:2406.19974#pg3>.
Tom: I agree. The paper demonstrates that you can leverage the dependence between the numerator and denominator estimators to reduce variance, which is what they call exploiting the third term in their asymptotic variance decomposition <ref:2406.19974#pg3>. That's a concrete mechanism for improving accuracy on difficult problems like rare events.
Lu: What this means for representation learning is that if you can formulate your estimation as a ratio, you have a systematic way to choose the joint distribution that best captures the relationship between the two parts of your integral estimation <ref:2406.19974#pg3>. It pushes us toward building representations where this ratio structure is natural.
Meng: So, if I'm looking at running these on real traffic data, does this framework help me choose a good coupling without needing to solve the whole optimal transport problem from scratch every time? That sounds computationally intensive <ref:2406.19974#pg3>.
Lalam: The paper states that they can use existing adaptive importance sampling or variational inference algorithms in the first stage to adapt those marginals, which makes it more accessible for current workflows <ref:2406.19974#pg3>. It’s about adapting what you already have to get better samples.
Jane: That makes sense. It's not a complete rewrite of everything; it's an enhancement to the existing framework by adding this specific way to parameterize the dependence between the estimators <ref:2406.19974#pg3>. It’s about generalization, which is important when moving from lab results to real-world applications.
Tom: So, if you're building a complex system involving Bayesian inference and you hit high variance, this paper gives you a structural roadmap—a decomposition into three terms—to guide your efforts toward the best variance reduction <ref:2406.19974#pg3>. It’s about knowing where to look for improvement.
Lu: And the coupling selection part is key because it's what translates that theoretical decomposition into a practical distribution you actually sample from, like multivariate normal or student t couplings <ref:2406.19974#pg3>. That choice directly impacts how much variance you save in practice.
Meng: I’m still concerned about the complexity of choosing that optimal coupling, but if the paper shows concrete choices like those mentioned, maybe we can start testing those instead of guessing <ref:2406.19974#pg3>. We need to know what breaks at scale <ref:2406.19974#pg2>.
Lalam: The paper's contribution is showing that this generalization is powerful because it handles cases where previous work was either too restrictive or didn't introduce the necessary dependence between the numerator and denominator estimators <ref:2406.19974#pg3>. This means it’s a broader tool than just one specific technique.
Paper summary: Jane: It sounds like the authors are showing that by viewing things as ratios of integrals, we can get a more interpretable way to understand and reduce the variance in these difficult estimation problems <ref:2406.19974#pg3>. That’s a really clear way to frame it for someone who isn't deep into the math right now.
Tom: So, to sum up, this paper introduces a framework that treats expectation estimation as estimating a ratio of two integrals, which lets you decompose the variance and then optimize the coupling between those two parts to get better results than standard self-normalized importance sampling <ref:2406.19974#pg3>. It’s about systematically reducing variance in hard statistical estimations.
Lu: And they show that this approach works by using a joint proposal distribution in an extended space, which is the key to parameterizing that dependence between the estimators effectively <ref:2406.19974#pg3>. This is pushing us toward more sophisticated ways of representing our models to capture these relationships better.
Meng: So, for deployment, it means we might need to invest time figuring out how to construct that joint distribution and then run those two stages of optimization before we can see any real gains in accuracy <ref:2406.19974#pg3>. It’s not a plug-and-play solution yet.
Jane: It sounds like the implication for the world is that for problems where standard sampling methods struggle with high variance, there's a structured mathematical path to guide you toward a better estimator <ref:2406.19974#pg3>. It moves us beyond just applying existing tools to finding new ways to construct them.
Tom: The authors are essentially providing the blueprint for generalizing self-normalized importance sampling by focusing on the ratio structure and leveraging coupling choices <ref:2406.19974#pg3>. That’s what they call Generalizing self-normalized importance sampling with couplings, and it seems like a solid foundation for future variance reduction techniques.
Lu: And I think the real power here is that it gives us a unifying framework, which means we don't have to invent a new sampling trick every time we face a problem involving ratio estimation using importance sampling <ref:2406.19974#pg3>. It connects different ideas in one place.
Meng: If this framework can be adapted to our specific modeling constraints, then it could help us understand exactly where our current methods are failing at scale versus where they might succeed with targeted optimization <ref:2406.19974#pg2>.
Jane: So, the paper is about taking a known difficult method and giving it a deeper mathematical structure so we can systematically optimize its performance instead of just running it hoping for the best <ref:2406.19974#pg3>. That’s a big step forward in making these complex estimations more reliable.
Tom: It's definitely an interesting direction, focusing on the decomposition of variance and using coupling choices to target that reduction, which is what they do with the asymptotic variance terms <ref:2406.19974#pg3>. That's the core technical contribution here.
Conclusion: Tom: So, we're wrapping up on this paper, "Generalizing self-normalized importance sampling with couplings." It basically shows how you can take that standard self-normalized method and make it way more accurate by looking at the relationship between the two parts of your estimation.
Jane: I want to start by asking what that actually means for us when we're doing these kinds of complex statistical estimations. Is this just some theoretical math, or does it help us get better numbers in real-world scenarios?
Lu: It’s a framework for minimizing the variance of an estimator when you can’t write down the full normalizing constant for your probability density function. The authors show that by viewing the task as estimating a ratio of two integrals, you can systematically decompose how that variance is built up into three separate parts.
Meng: So if I'm dealing with rare events or posterior predictive distributions, what does this decomposition tell me about where I should focus my effort to reduce error?
Lalam: The main idea is that the third part of the variance decomposition corresponds to the covariance between your numerator and denominator estimates. If you can choose a joint distribution that makes those two estimates highly correlated, you get a big reduction in variance there.
Tom: That sounds like we’re essentially trying to find a clever way to correlate our samples so they give us more reliable results for things that are hard to estimate. But what's the practical setup for doing this?
Jane: The paper proposes a two-stage optimization process. First, you adapt your existing importance sampling methods using any technique you already have, and then in a second stage, you choose the coupling between those adapted marginals to maximize that variance reduction term.
Lu: They suggest concrete examples like multivariate normal or student t couplings for that second stage. They even show how you can use first-order stochastic optimization to pick the best coupling by estimating its gradient using pathwise or score function methods.
Meng: I’m worried about the computational cost of that second stage optimization. If it requires solving a whole optimal transport problem every time, it won't scale for production models.
Lalam: The authors say that existing adaptive importance sampling algorithms can actually handle the first stage of adapting those marginals, which makes this framework more accessible for current workflows. It’s about improving what you already do with smarter coupling choices.
Tom: So the authors are providing a blueprint to move beyond just plugging in standard methods and instead guide your efforts toward where the variance reduction is mathematically possible.
Jane: I think the implication is that we don't have to invent a whole new sampling trick every time we face these ratio estimation problems. This framework unifies different ideas under this structure.
Lu: Exactly. It connects different concepts in one place, showing how to use the structure of the integral ratio itself to find better joint distributions and thus better estimators for expectations involving unnormalized PDFs.
Meng: If this framework can be adapted to our specific modeling constraints, then it could help us understand exactly where our current methods are failing at scale versus where they might succeed with targeted optimization.
Lalam: I'm confident the authors have shown a solid path forward here. This paper provides the structure we need to systematically look for variance reduction in hard statistical estimations.
Tom: It’s a blueprint for generalizing self-normalized importance sampling, showing how to use coupling choices and variance decomposition to get more reliable results without just throwing more samples at the problem.
Jane: And once you understand this framework, it opens the door to exploring new ways of constructing representations where this ratio structure is natural for your data.
School of Mathematics, University of Edinburgh, UK
stat.CO, stat.ME
Submitted: 2024-06-28
Updated: 2026-11-18
Comments: Substantial update
License: http://creativecommons.org/licenses/by/4.0/
The gist: An essential problem in statistics and machine learning is the estimation of expectations involving probability density functions (PDFs) with intractable normalizing constants The selfnormalized…
Key concepts
- Importance Sampling (IS)
- A method used in Monte Carlo simulations to approximate integrals. It works by sampling from a different probability distribution (the proposal) and weighting those samples by the ratio of the target density function to the proposal density, allowing estimation of expectations.
- Self-Normalized Importance Sampling (SNIS)
- The standard technique for estimating expectations when the normalizing constant of a probability density function is unknown. It normalizes importance sampling weights to improve consistency, but it suffers from high variance in difficult problems like rare events.
- Ratio of Two Integrals
- The core idea of the new framework is to reframe the estimation task as calculating a ratio between two integrals. This perspective allows for a more structured asymptotic variance decomposition, which is key to designing a better estimator.
- Optimal Joint Distribution (Coupling)
- This refers to the ideal joint probability distribution used when sampling from an extended space. The framework optimizes this distribution by maximizing a term related to covariance, effectively choosing the best way to couple the two marginal distributions ($q_1$ and $q_2$) for variance reduction.
Terminology
Summary
An essential problem in statistics and machine learning is the estimation of expectations involving probability density functions (PDFs) with intractable normalizing constants The selfnormalized importance sampling (SNIS) estimator, which normalizes the importance sampling (IS) weights, has become the standard approach due to its simplicity However, the SNIS has been shown to exhibit high variance in challenging estimation problems, e. p. 0 Generalizing self-normalized importance sampling with
couplings
Nicola Branchini
and
V´ıctor Elvira
School of Mathematics, University of Edinburgh, UK
July 1, 2024
Abstract
An essential problem in statistics and machine learning is the estimation of expectations
involving probability density functions (PDFs) with intractable normalizing constants. The selfnormalized importance sampling (SNIS) estimator, which normalizes the importance sampling
(IS) weights, has become the standard approach due to its simplicity.Where the paper says it
Problem Formulation and SNIS Limitations
Importance sampling (IS) is a methodological framework that generalizes the Monte Carlo (MC) principle to approximate integrals The self-normalized importance sampling (SNIS) estimator is the de facto standard approach in problems where the normalizing constant of p is unknown The SNIS estimator can be obtained by replacing the IS weights in the UIS estimator with their normalized counterparts While µpN SNIS is consistent just as µpN UIS and asymptotically normal, characterizing its MSE is more complicated because it is a ratio of two integrals The asymptotic variance of µpN SNIS admits an interpretable decomposition with three terms by exploiting the perspective that views the estimator as implicitly estimating a ratio of two integrals
The Proposed Framework and Decomposition
The new framework exploits the interpretation of the estimation problem as estimating a ratio of two integrals It considers samples from a joint distribution in an extended space, with two of its marginals playing the role of proposals used to estimate each integral The asymptotic variance decomposition is given by Proposition 1 as V8 q rµpN SNISs = χ2 pq q1q1q χ2 pq q2q2q - 2¨˚˚˝ Cpqqhkkkkkkkkikkkkkkjj, where the third term Cpqq has a direct correspondence with CovqrIpN,ZpN s
Designing the Optimal Joint Distribution
The framework proposes a two-stage optimization strategy to adapt the marginals using any existing AIS method, while the coupling can be chosen and adapted in a second stage The optimal joint distribution Q 1:2pdx1, dx2q is defined by maximizing CpQ 1:2q subject to constraints on the marginals q1 and q2 This optimization problem can be reformulated as a Kantorovich optimal transport problem
Coupling Selection and Practical Implementation
Concrete coupling choices such as Multivariate Normal and Student-t couplings are proposed for the framework A natural approach for stage (2) is first-order stochastic optimization to maximize Cp θq, where the gradient can be estimated using pathwise or score function methods The framework allows existing AIS or VI algorithms to adapt the marginals q1 and q2 in the first stage
Performance and Conclusion
Experiments demonstrate that significantly more accurate estimates of expectations are achieved with a judicious choice of coupling informed by the general framework The optimized coupling converges to u1 u2 in one example, which gives the best performance and outperforms TABI and SNIS The framework highlights the limitations of existing approaches and paves the way for further variance reduction techniques The core underlying idea behind µpN GenSNIS of improving variance by correlating the estimates can be applied to give a generalization of bridge sampling
References
[1] Sergios Agapiou, Omiros Papaspiliopoulos, Daniel Sanz-Alonso, and Andrew M Stuart. Importance sampling: Intrinsic dimension and computational cost
[2] Omer Deniz Akyildiz. Global convergence of optimized adaptive importance samplers
[3] Omer Deniz Akyildiz and Joaqu´ın M´ıguez. Convergence rates for optimised adaptive impor- tance samplers
[4] Dimitri P Bertsekas and John N Tsitsiklis. Gradient convergence in gradient methods with errors
[5] Zdravko I Botev. The normal law under linear restrictions: simulation and estimation via minimax tilting
[6] L´eon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning
[7] Monica F Bugallo, Victor Elvira, Luca Martino, David Luengo, Joaquin Miguez, and Petar M Djuric. Adaptive importance sampling: The past, the present, and the future
[8] Olivier Capp´e, Arnaud Guillin, Jean-Michel Marin, and Christian P Robert. Population monte carlo
[9] Gabriel Cardoso et al. Br-snis: Bias reduced self-normalized importance sampling
[10] Guillaume Carlier, Victor Chernozhukov, Gwendoline De Bie, and Alfred Galichon. Vector quantile regression and optimal transport, from theory to numerics
[11] Sourav Chatterjee and Persi Diaconis. The sample size required in importance sampling
[12] Ming-Hui Chen and Qi-Man Shao. Monte carlo methods for estimating ratios of normalizing constants
[13] Ming-Hui Chen and Qi-Man Shao. Monte carlo methods for bayesian analysis of constrained parameter problems
[14] Ming-Hui Chen and Qi-Man Shao. Monte carlo estimation of bayesian credible and hpd intervals
[15] Victor Chernozhukov, Alfred Galichon, Marc Hallin, and Marc Henry. Monge–Kantorovich depth, quantiles, ranks and signs
[16] Nicolas Chopin, Omiros Papaspiliopoulos, et al. An introduction to sequential Monte Carlo
[17] Jean-Marie Cornuet, Jean-Michel Marin, Antonietta Mira, and Christian P. Robert. Adaptive multiple importance sampling
[18] Tiangang Cui, Sergey Dolgov, and Robert Scheichl. Deep importance sampling using tensor trains with application to a priori and a posteriori rare events
[19] Claudia Czado. Analyzing dependent data with vine copulas
[20] Jyotishka Datta and Nicholas Polson. Inverse probability weighting: the missing link between survey sampling and evidence estimation
[21] George Deligiannidis, Arnaud Doucet, and Michael K Pitt. The correlated pseudomarginal method
[22] Luc Devroye. Nonuniform random variate generation. Handbooks in operations research and management science, 13:83–121, 2006
[23] Aymeric Dieuleveut, Gersende Fort, Eric Moulines, and Hoi-To Wai. Stochastic approximation beyond gradient for signal processing and machine learning
[24] Randal Douc, Arnaud Guillin, J-M Marin, and Christian P Robert. Minimum variance importance sampling via population monte carlo
[25] Arnaud Doucet, Will Grathwohl, Alexander G Matthews, and Heiko Strathmann. Score-based diffusion meets annealed importance sampling
[26] Yousef El-Laham, V´ıctor Elvira, and M´onica Bugallo. Recursive shrinkage covariance learning in adaptive importance sampling
[27] V. Elvira, L. Martino, D. Luengo, and M. F. Bugallo. Generalized multiple importance sampling
[28] V´ıctor Elvira and Emilie Chouzenoux. Optimized population monte carlo
[29] V´ıctor Elvira and Luca Martino. Advances in importance sampling
[30] V´ıctor Elvira, Luca Martino, David Luengo, and M´onica F Bugallo. Improving population monte carlo: Alternative weighting and resampling schemes
[31] V´ıctor Elvira, Luca Martino, and Christian P Robert. Rethinking variational inference for probabilistic programs with stochastic support
[32] Michael Evans and Tim Swartz. Methods for approximating integrals in statistics with special emphasis on bayesian integration problems
[33] Yanqin Fan and Marc Henry. Vector copulas
[34] Edwin Fong and Chris C Holmes. Conformal bayesian computation
[35] Gabriel Frahm. Generalized elliptical distributions: theory and applications
[36] Lea Friedli, David Ginsbourger, Arnaud Doucet, and Niklas Linde. An energy-based model approach to rare event probability estimation
[37] Christian Genest, JJ Quesada Molina, and JA Rodr´ıguez Lallena. De l’impossibilit´e de construire des lois a marges multidimensionnelles donn´ees a partir de copules
[38] John Geweke. Bayesian inference in econometric models using monte carlo integration
[39] Charles J Geyer. Estimating normalizing constants and reweighting mixtures
[40] Paul Glasserman. Performance continuity and differentiability in monte carlo optimization
[41] Adam Golinski, Yee Whye Teh, Frank Wood, and Tom Rainforth. Amortized monte carlo integration
[42] Ambuj Goyal, Philip Heidelberger, and Perwez Shahabuddin. Measure specific dynamic importance sampling for availability simulations
[43] Thomas Guilmeau, Nicola Branchini, Emilie Chouzenoux, and V´ıctor Elvira. Adaptive importance sampling for heavy-tailed distributions via alpha-divergence minimization
[44] Jun Han and Qiang Liu.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Optimization of proposal distributions can be decoupled into two stages: adapting marginals using any existing adaptive importance sampling or variational inference algorithm, and then selecting a coupling to maximize the third term of the asymptotic variance as shown in Proposition 2. This allows for a framework where
adaptation can be carried out both for marginals and for the coupling.
-
The improved AI system can estimate expectations involving unnormalized probability density functions with better variance control by using a joint distribution in an extended space, denoted Q1:2, to parameterize the dependence between the numerator and denominator estimators. This provides a
two-stage framework suitable to be integrated with existing or new AIS and/or variational inference (VI) algorithms.
-
The system can utilize a general method to sample from a joint distribution with two given marginals of possibly different parametric families, even when the joint distribution itself is not in a known family. This addresses the limitation where
the need for two different parametric families can easily arise in practice.
-
The AI system can implement coupling adaptation using first-order stochastic optimization to iteratively maximize Eq. (16), which targets an asymptotically optimal coupling C1:2, thereby explicitly controlling the term CpQ1:2q that affects the asymptotic variance.
Abstract
Estimating expectations under distributions known up to a normalizing constant is a fundamental challenge in statistics. The self-normalized importance sampling (SNIS) estimator is widely used for its simplicity. However, SNIS suffers from high variance in some applications, such as Bayesian sensitivity or outlier analysis. Further, there is a lack of general methods to select a proposal tailored to SNIS. We introduce a generalization of SNIS by exploiting its interpretation as a ratio of two IS estimators. We sample from a joint distribution, whose marginals play the role of proposals for numerator and denominator, thereby including existing two-proposal methods as special cases. Our perspective allows us to develop new theory for SNIS. We show that an appropriate selection of the joint can bring the asymptotic variance from infinite to finite. We prove sufficient and necessary sample size results for generalized SNIS valid under infinite variance, inspired by Chatterjee & Diaconis (2018). Differently from existing results: ours further apply for non-square integrable functions, show the role of the dependence between numerator and denominator, and connect with the known optimal SNIS proposal of Hesterberg (1988). We demonstrate the benefits of the proposed methodology across applications in Bayesian sensitivity and outlier analysis.
Sources
- Inverse Probability Weighting: from Survey Sampling to Evidence Estimation
- Advances in Importance Sampling
- An energy-based model approach to rare event probability estimation
- On the Convergence of Adam and Beyond
- Adaptive Importance Sampling via Stochastic Convex Programming
Related papers
- Sticky Manifold Piecewise Deterministic Monte Carlo for Bayesian Model Averaging
- A perturbation theory for Feynman-Kac models and their particle interpretations
- Fast Functional Clustering via Closed-Form Covariance Updates
- A fast non-reversible sampler for Bayesian mixture models
- Inventory and Assortment Optimization under General Choice: A Unified Approximation Framework
- Least squares variational inference