CS Paper Radar

Post-stratified importance sampling

Yuling Yao, Sergei Tikhonov

cs.LG stat.MEstat.CO ·submitted 2026-11-03 17:21 UTC · v1

Abstract

Importance sampling is a building block of modern statistical computing, but the weighted estimate is prone to high or infinite variance. Moreover, its empirical standard error is often unreliable, leaving importance sampling without practical uncertainty quantification. Motivated by multilevel regression and poststratification (MRP) in survey sampling, we propose post-stratified importance sampling (PIS) for estimating target expectations from proposal draws. PIS reformulates arbitrarily high-dimensional weighting into two one-dimensional probabilistic modeling problems: regression for the conditional mean given the importance ratio and marginal density estimation for the importance ratio. Different modeling choices yield a family of PIS estimators, encompassing ordinary importance sampling as a special case. We develop a model-based implementation that combines one-dimensional Gaussian process regression for the conditional mean and score-informed heavy-tailed density estimation for the marginal law, using both the observed weights and the available density evaluations. We study the oracle gains of PIS and establish consistency under general and model-specific conditions. Simulations and applications to cross-validation demonstrate improvements in estimation accuracy and uncertainty quantification.

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Best-of-N policy evaluation for inference-time alignment

cs.LG cs.AIstat.ML ·2026-10-07 ·Jonas Schweisthal, Yuxin Wang, Athiya Deviyani, Stefan Feuerriegel, Dennis Frauen
similarity 0.63
Abstract · Preprint

Best-of-N (BoN) is a common inference-time alignment method that selects the highest-scoring response among N samples from a reference model. Evaluating BoN policies from logged data is challenging under sample-only access because standard off-policy estimators require density ratios that depend on unavailable response likelihoods. In this paper, we propose a sample-only framework for evaluating and selecting BoN policies without access to these likelihoods. We show that the order-statistic structure of BoN allows the required density ratios to be expressed through score-rank probabilities that are estimable from samples alone. We then develop a doubly robust estimator of the BoN policy value (BoN-DR) that efficiently reuses a shared auxiliary sample pool across candidate budgets. We establish valid asymptotic inference even under reward estimator misspecification and prove the efficiency of our BoN-DR estimator. Since larger budgets can amplify errors in the score function and lead to reward overoptimization, we derive two selection rules: (i) maximizing the estimated policy value and (ii) maximizing a lower confidence bound on the improvement over the reference policy, which accounts for estimation uncertainty and provides a no-harm guarantee. Across synthetic experiments and GSM8K with multiple reference and reward models, our framework accurately estimates BoN policy values and selects effective sampling budgets.

0.18

Beyond Effective Sample Size: Effective Number of Proposals for Adaptive Importance Sampling

cs.LG stat.ML ·2026-08-15 ·Ali Mousavi, Victor Elvira
similarity 0.61
Abstract

Population-based adaptive importance sampling (AIS) methods use a set of proposal densities to approximate complex target distributions. Their performance is commonly assessed through effective sample size (ESS) and related weight-based diagnostics, which measure the concentration of normalized importance weights. However, a large ESS only indicates that the normalized sample weights are not strongly concentrated; it does not describe how the proposal components are arranged in the sampling space. In population-based AIS, several proposal components may generate samples in the same region of the target, so the sample weights can appear well balanced even though the effective number of distinct proposal components is small. This letter introduces the effective number of proposals (ENP), a similarity-aware proposal-level diagnostic for population-based AIS. ENP combines the total normalized weight assigned to each proposal with a redundancy measure computed from similarities among target-weighted samples, estimating the number of non-redundant empirical proposal contributions to the approximation. We establish basic effective-number properties and show that ENP detects proposal collapse and duplication missed by standard ESS. We also illustrate its use as a targeted feedback signal for proposal rejuvenation.

0.04

Multiple Importance Sampling for Guided Speculative Inference

cs.LG cs.IT ·2026-10-23 ·Joseph Rowan, Ashish J. Khisti
similarity 0.59
Abstract · 9 pages, 1 figure. Presented at the IEEE ISIT 2026 Workshop on Information Theory for Large Language Models (IT4LLM)

We study an extension of the Guided Speculative Inference (GSI) algorithm for test-time-scaling of large language models (LLMs) to a novel setting where an ensemble of smaller LLMs proposes draft reasoning steps which are later verified by a larger base model and a process reward model. Using the established framework of multiple importance sampling (MIS), we introduce weighting schemes to aggregate samples from a diverse collection of proposal distributions. We provide new bounds on the KL divergence from the optimal reward-tilted target distribution and the expected reward degradation, then demonstrate that the well-known balance heuristic is optimal. Compared to GSI with a single well-tuned drafter, combining several diverse LLMs while retaining the same total number of samples maintains competitive pass-at-$N$ downstream performance while being mathematically robust to situations where the support of a single draft model does not cover that of the target, where GSI may fail.

0.26

SAUSS: Stochastic Approximation with Unbiased Simulated Scores for Limited Dependent Variable Models

cs.LG stat.MEecon.EM ·2026-08-26 ·Sokbae Lee, Yuan Liao, Myung Hwan Seo, Youngki Shin
theory similarity 0.58
Abstract

Simulated maximum likelihood is widely used in latent-variable models where likelihood evaluation requires intractable integrals or probabilities. With a fixed number of simulation draws, its estimating equation is generally biased. We develop Stochastic Approximation with Unbiased Simulated Scores (SAUSS), combining score simulation with stochastic gradient descent. The Hajivassiliou--McFadden identity, an instance of Fisher's identity, expresses the likelihood score as the conditional expectation of the complete-data score given the observed data. Exact conditional draws yield an unbiased simulated score for any fixed number of draws. The estimator averages stochastic gradient iterates computed using mini-batches of fixed size regardless of sample size, avoiding repeated full-sample likelihood evaluations. Under local regularity and initialization conditions, we establish asymptotic normality and a functional central limit theorem for the partial-sum process of the iterates under multi-pass sampling from an observed sample. These results support plug-in and random-scaling confidence intervals that remain asymptotically valid when algorithmic uncertainty is non-negligible relative to sampling uncertainty. We develop multinomial probit as a leading application. In simulations and two applications, SAUSS returns estimates in every reported run, including cases where the simulated maximum likelihood implementation returns none. When both return estimates, SAUSS gives comparable estimates in less time.

0.21

Robust Importance Sampling for Rare Events via Constrained Gaussian Mixtures

cs.LG ·2026-10-05 ·Paweł Lorek, Rafał Nowak, Rafał Topolnicki, Tomasz Trzciński, Maciej Zięba
top venuecode/data similarity 0.56
Abstract · Accepted at NeurIPS 2026

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.

0.46

Fixed-Size Active Statistical Inference

cs.LG ·2026-10-19 ·Erik Skalnes, Michael Oberst
publishedcode/data similarity 0.56
Abstract · Accepted at NeurIPS 2026 (poster). 49 pages. Code: https://github.com/oberst-lab/fixed-size-asi ; Python package: https://pypi.org/project/c…

Variance reduction techniques improve the efficiency of drawing conclusions from data. Recent proposals for variance-reduction use two complementary techniques to reduce variance: incorporating machine learning predictions into estimators and weighted sampling. A popular weighted sampling algorithm is Poisson Sampling (PS), which independently flips a biased coin at each unit and includes all heads in the sample. A fundamental flaw with PS is that it has a random sample size, which presents practical challenges and introduces variance into the estimator. We show that a fixed-size alternative, known in survey sampling as Conditional Poisson Sampling (CPS), is a drop-in replacement for PS on general multivariate Z-estimation problems, which include convex M-estimation considered in prior work. Notably, we show that the asymptotic variance of CPS is no worse than that of PS, and can be substantially better in realistic scenarios where predictions are imperfect. We illustrate these advantages on both synthetic and real datasets, and release a Python package implementing CPS. In light of our contributions, there is no need to suffer a variable sample size.

0.48

Learning to Bias: Machine Learning-Enhanced Particle Filters

cs.LG stat.ML ·2026-09-24 ·Apoorv Srivastava, Eric Darve
similarity 0.55
Abstract · 29 pages, 9 figures, including appendices

Sequential inference estimates latent states from noisy and incomplete observations. Particle Filters (PFs), a class of Monte Carlo methods based on importance sampling, provide a flexible framework for this task, but often suffer from poor sample efficiency and unfavorable scaling with dimension, partly due to suboptimal proposal distributions. We address these challenges by integrating learned proposals into the PF framework. We introduce Neural Optimal Particle Filters (NOPFs), which learn an amortized approximation to the optimal proposal from offline simulated one-step conditioning tuples. The learned proposal is used as a drop-in replacement in standard PF updates, with samples corrected by standard importance weights so that the method asymptotically targets the same filtering distribution under standard support and density-evaluation assumptions. Across stochastic nonlinear benchmarks of varying inference complexity, NOPFs improve sample efficiency and distributional accuracy over standard PF baselines with modest computational overhead. The approach integrates data-driven proposal learning into classical inference without altering the underlying filtering objective.

0.34

LUCID: Local Understanding of Covariate Importance with Conditional Density Estimation

cs.LG stat.ML ·2026-10-26 ·Yixiao Wang, Srikar Katta, Jon Donnelly, Emanuele Borgonovo, Cynthia Rudin
similarity 0.54
Abstract

Computing local-level variable importance (VI) is critical for understanding machine learning models. Local permutation-based VI metrics offer a simple yet powerful approach, measuring how much a model's output changes when perturbing its inputs. However, existing perturbation strategies often ignore feature dependence or account for it only through restricted approximations. Perturbing a feature without fully respecting this dependence can generate unrealistic counterfactuals, thereby evaluating the model in regions unsupported by the observed data distribution. We address this gap by introducing a new model-agnostic local VI metric and estimator, Local Understanding of Covariate Importance with conditional Density estimation (LUCID). LUCID perturbs features of interest using plausible values drawn from the full conditional distribution given the remaining observed features. We establish theoretical connections between LUCID and existing VI measures, and provide an estimator with convergence guarantees and uncertainty quantification. Finally, we demonstrate LUCID's stable performance and practical utility across simulated and real-world examples.

0.20