Overview

Variance reduction studies how to make noisy estimates—such as gradients, Monte Carlo expectations, policy values, and experiment effects—more precise without simply collecting more samples. Common approaches include control variates, recursive estimators such as SVRG and STORM, importance and stratified sampling, and Rao-Blackwellization or shared randomness. The methods are studied in finite-sum optimization and sampling as well as reinforcement learning, diffusion-model training, Bayesian computation, and A/B testing, with evaluations often measuring variance, sample complexity, or convergence. A central tension is that lower estimator variance may require extra computation or stronger assumptions, and minimizing variance alone does not always improve downstream outcomes such as model quality.

Latest papers

114 papers14 papers in the last four weeks, down 33% on the four weeks before. 0.1% of all new papers.

Nov 11, 2026

Beyond Reweighting: Certified Improvements from New Transitions in Discrete MCMC

Optimizing transition probabilities on a fixed grap may leave substantial limitations on the efficiency of reversible Markov chain Monte Carlo (MCMC). We develop a framework for transition-support design that considers both allowed transitions and their stationary flows. For a fixed target distribution, observable, and node-flow budget, we derive a necessary and sufficient dual condition for support augmentation to strictly reduce the optimal value of the asymptotic variance, together with computable primal--dual certificates that establish improvements over every admissible original-support reweighting. We also construct a family in which adding a single edge reduces integrated autocorrelation time by an Ω(n)Ω(n) factor relative to optimal original-support weighting, demonstrating that structural limitations can impose arbitrarily large relative losses in estimation efficiency. To realize these gains, we investigate energy-informed edge selection and constrained stationary-flow optimization. Experiments on molecular and Ising state graphs distinguish the potential value of new transitions from the performance of kernels constructed on them: on identical augmented Ising supports, full weight optimization certifies strict improvements in 24/24 conditions, whereas degree-based Metropolis--Hastings weighting certifies none. Our results provide a principled approach to characterizing, certifying, and exploiting transition-support improvements in explicitly represented finite state spaces.
Nov 8, 2026

Variance-Reduced Stochastic Hessian-Driven Nesterov Acceleration with Adam-Style Preconditioning

Stochastic first-order methods use sampled gradients to reduce per-iteration costs, but estimation errors can slow convergence and, in some settings, cause divergence. To improve gradient accuracy while retaining acceleration, we develop scalar and diagonal versions of VR-Adam-SHANG for smooth stochastic convex optimization. The methods combine STORM-type recursive estimation, Adam-style preconditioning, and SHANG's accelerated interpolation and correction, using at most two stochastic gradient evaluations per iteration without full-gradient refreshes. Under unbiased sampling, bounded variance, and mean-square smoothness of gradient noise, polynomial steps with prescribed initialization yield O(1/K)O(1/K) mean-square gradient-estimation error and expected objective-gap bounds combining O(1/K2)O(1/K^2) initial-energy decay with an O(1/K)O(1/\sqrt K) stochastic term after KK iterations. These guarantees require neither monotonicity of the preconditioner nor a uniform positive lower bound on its eigenvalues. The analysis also establishes polynomial-step convergence of projected nonrecursive Adam-SHANG-s, filling a gap in its original theory. Experiments compare the methods at matched sample-gradient budgets. In every tested setting, at least one of the two versions achieves the lowest mean terminal objective gap among all compared methods.
Nov 5, 2026

Compressed Per-Player Local Methods for Multiplayer Federated Learning: Exact Convergence via Increment Sharing

Multiplayer Federated Learning (MpFL), introduced by Yoon et al. (2025), extends classical federated learning to settings where clients are rational players in a game with individual objectives and strategies, seeking an equilibrium. A natural baseline is Per-Player Local SGD (PEARL-SGD), where each player performs several local SGD steps before exchanging strategies through a central server. However, the original PEARL-SGD formulation does not extend cleanly to compressed communication. Directly compressing the players' strategies can prevent convergence to the equilibrium, even with deterministic gradients. To address this issue, we reformulate PEARL-SGD so that players communicate local strategy increments rather than the strategies themselves. Without compression, the two formulations are equivalent, but with compression, increment sharing preserves exact convergence, allowing us to design the communication-efficient compressed PEARL-SGD (C-PEARL-SGD). Beyond compression, we also consider variance reduction as another axis of improvement, introducing PEARL-SVRG and its compressed variant C-PEARL-SVRG. Under the original MpFL assumptions, we establish convergence guarantees for all variants through a unified parametric inequality. Numerical experiments, including distributed spectrum sensing, demonstrate the practical benefits of our methods over vanilla PEARL-SGD.
Nov 3, 2026

Post-stratified importance sampling

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.
Nov 2, 2026

The Cost of Mismatch: Noise Amplification in Zeroth-Order Reinforcement Learning

Zeroth-order (ZO) optimization has emerged as a promising approach for memory-efficient large language model (LLM) post-training, yet its reliability in reinforcement learning with verifiable rewards (RLVR) remains largely unexplored. Motivated by the distinct data regimes of on-policy RL and fixed-data optimization, we develop a generic variance-theoretic framework to investigate what limits the reliability of ZO gradient estimation. Our analysis reveals that estimation reliability is structurally determined by whether the two finite-difference evaluations are performed on matched data. On-policy reinforcement learning (RL) under the mismatched-data regime produces a 1/μ21/μ^2 oracle-noise amplification that sets an irreducible noise floor as the perturbation scale μμ decreases, whereas Boltzmann Targeted SFT (BOLT) under the matched-data regime eliminates this amplification via noise cancellation. We further derive convergence guarantees with explicit constants that cleanly separate the two regimes. These results motivate the ZO-BOLT algorithm, which builds on BOLT's matched-data advantage for reliable ZO optimization of an RLVR-aligned objective. Controlled perturbation-scale sweeps and matched-versus-mismatched end-to-end comparisons validate the predicted effect of data matching. Experiments across three models and two mathematical reasoning benchmarks further show that ZO-BOLT consistently improves over the pretrained baseline while retaining a near-inference memory footprint. The code is publicly available at https://github.com/lianmin-chen/the_cost_of_mismatch.
Oct 30, 2026

Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates

Multiple local updates are widely used in decentralized optimization to enhance communication efficiency, often in conjunction with stochastic gradients when exact gradient computation is costly. However, such algorithms generally converge only to a neighborhood of the optimum, whose size depends on the stepsize and the variance of gradient noise. Variance reduction has been incorporated into ADMM-based methods to achieve exact convergence in expectation, but their stepsizes typically scale inversely with both the square root of the network size and the cube of the number of local updates, leading to slow convergence as the network size or the number of local updates increases. In this paper, we propose a novel primal-dual-based decentralized optimization algorithm that integrates variance reduction with multiple local updates, with a stepsize independent of the network size and inversely proportional to the number of local updates (rather than its cube), thereby enabling significantly larger stepsizes and faster convergence. Moreover, to the best of our knowledge, we establish the first linear convergence guarantee in expectation for decentralized optimization with multiple local updates under stochastic gradients in the strongly convex setting. Beyond the theoretical guarantee, the proposed method exchanges only one variable per round, halving the communication cost compared with gradient-tracking-based methods. Numerical experiments further demonstrate its advantages in convergence speed and accuracy.
Oct 24, 2026

Hessian-Similar Optimization with Capped Participation: Lower Bounds and Virtual Masters

What is the round complexity of Hessian-similar optimization when each round can contact at most ss of mm clients? Prior rates permit a free master or full participation and do not characterize strict caps. We count every one-vector query and reply. A hidden-client chain gives a lower bound for zero-respecting local algorithms with adaptive cohorts and random stopping: on strongly convex quadratics, the required rounds are Ω((m/s)min⁡{δa,δˉ/m}/μ log⁡(1/ε))Ω((m/s)\sqrt{\min\{δ_a,\barδ/\sqrt m\}/μ}\,\log(1/ε)) for s≤(m−2)/2s\leq(m-2)/2 in the high-accuracy, high-dissimilarity regime. Here μμ is strong convexity, while δaδ_a and δˉ\barδ bound anchor and average Hessian variation. To remove dependence on a poor anchor, virtual-master SVRS uses independent estimator and proximal cohorts and averages the proximal replies. With Catalyst, it reaches relative gap εε in O~(m/s+(m/s+m3/4/s)δˉ/μ)\tilde O(m/s+(\sqrt{m/s}+m^{3/4}/s)\sqrt{\barδ/μ}) expected rounds on quadratics with strongly convex clients, independent of δaδ_a. Combining this method with charged analyses of existing algorithms matches the lower bound's polynomial dependence for s≤ms\leq\sqrt m and s=Ω(m)s=Ω(m); the worst gap is O(m1/8)O(m^{1/8}). A held-out 12-seed synthetic study finds fewer rounds than tuned SVRP in nine of ten dip-family incomplete-cohort cells, versus two of 30 other cells. The lower bounds concern zero-respecting algorithms and do not cover unrestricted messages.
Oct 20, 2026

Variance Reduction with Delayed Feedback for Non-Convex Optimization

We study variance reduction for non-convex optimization when gradient evaluations return with a delay. The server can update the parameter while earlier evaluations remain unfinished. We first analyze an ordered recursive momentum estimator for stochastic optimization. Under average smoothness and bounded variance, its oracle complexity is O(1+σ2ε−2+LΔf(1+σ/ε+τ)ε−2)O(1+σ^2ε^{-2}+LΔ_f(1+σ/ε+τ)ε^{-2}), where the target is an expected squared gradient norm of at most ε2ε^2 and ττ bounds the feedback delay. We next study finite sums with nn components and obtain O(n+LΔf(n+min⁡{τ,n−1})ε−2)O(n+LΔ_f(\sqrt n+\min\{τ,n-1\})ε^{-2}) evaluations. An asynchronous snapshot variant continues updating during full-gradient computations under an explicit bound on their completion time. For the stochastic method, we further replace a maximum-delay bound by a bound on the weighted amount of missing feedback.
Oct 19, 2026

Fixed-Size Active Statistical Inference

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.
Oct 19, 2026

Learned Control Variates for Rare Grid-Outage Estimation at Electric Vehicle Charging Stations

Public charging of electric vehicles (EVs) adds a large and synchronized load to the distribution feeders. In most networks, it is rare to overload a feeder at the same time. When it does happen, the consequences can be severe: an overloaded feeder stresses its transformers and can trigger cascading outages across a city. Planners who design for high reliability therefore need to estimate very small outage probabilities. To that end, plain Monte Carlo estimation with an expensive grid simulator can require a prohibitively large number of runs for this task. To reduce the number of runs, we propose a control variate (CV) built from a learned classifier of the outage, trained on cheap observable features such as temperature and load forecasts. We show that for any binary learner, the variance reduction is an explicit function of its recall and false-positive rate. Furthermore, we show that control variate based on a Gaussian proxy of the load loses its effect as outages become rarer, while a learner with non-vanishing precision keeps removing a fixed fraction of the variance even in the extreme rare-event regime. We verify these results in numerical experiments using a feeder-overload simulator across three orders of magnitude of outage probability and obtain that even weak learner with a single feature can remove a quarter of the variance, while a boosted-tree learner is able to remove about 60%. We then apply the estimator to the feeder network of Surabaya, Indonesia, in which the Gaussian load model leaves every feeder three to seven times the one-day-in-ten-years blackout target. At the same simulation budget, planning the reserve with the learned CV and a 95% confidence limit reduces the city-wide blackout days by a third compared with Monte Carlo. These results show that learned control variates can help planners design distribution grids that stay reliable against rare outages.
Oct 18, 2026

Multifidelity Monte Carlo Estimator for High-Dimensional Quantities of Interest

Multifidelity Monte Carlo (MFMC) reduces the cost of estimating the statistics of quantities of interest (QoIs) computed via expensive high-fidelity model by using cheaper low-fidelity models as control variates. We extend MFMC to vector-valued QoIs by replacing the scalar control-variate coefficients with matrices and minimizing a weighted mean-squared error. The optimal full-matrix coefficients are available in closed form, and their variance reduction is summarized by an effective correlation that takes the place of the squared Pearson correlation in the closed-form MFMC design. Restricting the coefficients to block-diagonal, diagonal, and scalar classes gives a nested hierarchy of estimators with increasing variance reduction and increasing pilot-data demand, with closed-form coefficients for compatible weightings. For a scalar QoI obtained by linearly projecting the state, correcting the full state before projecting is never worse at the population level. Experiments on a Gaussian problem, a reduced-order model of an advection--diffusion problem, and a coarse-grid two-phase flow problem show that the best class depends on the pilot size relative to the number of covariance quantities it must estimate, and that reusing the pilot samples lowers the mean-squared error.
Oct 17, 2026

Gaussian Process Bandits with Paired Auxiliary Observations

Bayesian optimization (BO) is widely used for expensive black-box optimization, yet observation noise makes each evaluation less informative and slows posterior learning. Standard BO learns from costly outcomes gathered during optimization. In many applications, however, low-cost auxiliary data are available beforehand. We introduce Auxiliary-Informed Gaussian Process Bandit (AI-GPB), a variance-reduction method that combines an offline estimate of the auxiliary mean with a correction coefficient learned from paired online observations. Notably, it exploits correlation between paired observation errors without requiring the auxiliary mean to approximate the objective. We establish finite-sample GP confidence bounds and regret guarantees, including explicit cumulative and simple regret rates for Matérn kernels. Numerical experiments across continuous BO benchmarks with varied landscapes and dimensions show consistent reductions in cumulative and simple regret relative to vanilla GP-UCB, even when within-pair correlation is moderate and the auxiliary mean is estimated from noisy offline data.
Oct 15, 2026

Personalized Projected Ascent for Federated Stackelberg Optimization

Federated minimax problems, such as distributionally robust optimization and adversarial training, include an inner maximization variable built from each client's local data. These variables differ in meaning and dimension from one client to the next, so averaging them across clients, as standard federated minimax methods do, is ill-posed. We therefore study a federated minimax problem where the minimization variable x\mathbf{x} is shared and aggregated, while each client retains the maximization variable yi\mathbf{y}_i (personalized). Because these applications constrain yi\mathbf{y}_i to a compact convex set, we analyze projected ascent directly. We show that, in the nonconvex-concave regime, this projected personalized scheme attains the standard sublinear rate. In the nonconvex-PL regime, however, it hits a stepsize-invariant noise floor due to stochastic yi\mathbf{y}_i updates. To mitigate this, we propose VR-SGDA, incorporating a variance-reduced ascent step where each client maintains a private variable snapshot. By evaluating current and snapshot gradients on the same sample, the constant variance is replaced by a vanishing drift under a two-timescale regime. VR-SGDA eliminates the noise floor, attaining sublinear leading rates while preserving personalization and projection. Experiments on subpopulation-robustness and NLP adversarial training confirm both the worst-group robustness benefits and the two-timescale tracking mechanism.
Oct 13, 2026

Scaling Online Optimal Transport Minibatches for Flow Matching

A central challenge in scaling flow models is maintaining stability in training and integration. In flow matching, this stability depends critically on how source samples are paired with data. Independent random pairing introduces substantial stochasticity, motivating minibatch optimal transport (OT) to construct online source-target couplings that reduce this randomness (Tong et al., 2024). However, as applications extend to larger and higher-dimensional datasets, small minibatches can limit these benefits, while scaling the coupling to substantially larger minibatches at every iteration is computationally prohibitive. Moreover, how OT coupling affects the full stochastic gradient and integration remains theoretically unresolved. In this work, we develop a scalable online entropic OT approximation that enables substantially larger source-target couplings while preserving the benefits of OT. We close the theoretical gap for both unregularized and entropic OT by proving strict reductions in full stochastic-gradient variance and integration error relative to independent pairing, and further characterize how these improvements strengthen as the online coupling minibatch grows. Experiments on single-cell gene interpolation-flow and image-flow training validate these predictions, showing that larger online couplings consistently improve training stability and final generation performance.
Oct 13, 2026

Understanding Circulant Permutation to Extend the CMinHash Estimator

CMinHash promises a new direction for designing MinHash algorithms with reduced variance and storage space via circulant permutations. However, the original variance analysis is difficult to extend to other MinHash estimators. We present a new approach that gives explicit and easily comparable approximate variance expressions, and use it to analyze the Minner estimator. Numerical experiments show that our variance expression matches the empirical mean square error (MSE) of estimates. Our work thereby demonstrates how to apply circulant permutation to other MinHash estimators and compute their approximate variance.
Oct 9, 2026

Adaptive Variance Reduction across Smoothness and Noise Conditions

In this paper, we study adaptive stochastic non-convex optimization under unknown smoothness and noise conditions. Our algorithms require no smoothness constant, noise bound, initial function gap, or oracle-regime label. We first propose a fixed-budget method that combines normalized momentum, recursive variance reduction, and a fresh gradient stage, followed by fresh validation of the candidates. We prove that the same output has expected gradient norm O(T−1/4)O(T^{-1/4}) under objective smoothness and bounded noise variance, O(T−1/3)O(T^{-1/3}) under average smoothness, and O(T−1/2)O(T^{-1/2}) for noiseless gradients, where TT counts individual gradient evaluations. We then develop an anytime algorithm whose three optimization paths preserve their endpoints across reporting and budget-extension boundaries. The same three rates hold at every deterministic query budget, although the algorithm receives no information about the budget TT. The analysis combines a scale potential, a uniform second-moment bound, and accounting for candidates retained through unfinished blocks. An optional sample-mean selector further reduces cumulative validation work from O(T)O(T) to O(T2/3)O(T^{2/3}) while preserving these rates.
Oct 9, 2026

Randomized Momentum Transport with Cheap Predictors

Momentum methods such as STORM and second-order momentum track the gradient by adding a transport correction to momentum, at the cost of an extra oracle call per iteration. We introduce randomized momentum transport, which evaluates the correction with probability qq and otherwise uses a cheap prediction, with importance weighting that preserves the conditional mean and adds (q−1−1)(q^{-1}-1) times the prediction loss to the variance. Under transport-bias, second-moment, and residual-control assumptions, linear minimization oracle (LMO) updates, including normalized, sign, and exact spectral (Muon) directions, retain an O(T−1/3)O(T^{-1/3}) stationarity bound for each fixed q>0q>0 with a single-gradient initialization. For unnormalized STORM, some q<1q<1 lowers the leading coefficient of our sufficient gradient budget if and only if the gradient-difference noise modulus exceeds the smoothness constant, by at most about 10%10\%. An online diagonal predictor admits a regret-to-convergence guarantee. At approximately equal oracle cost, querying a quarter of the corrections lowers the final training loss by 1818 to 43%43\% on MNIST1D and raises the test accuracy of Hessian-vector transport on CIFAR-10 by 1.51.5 points.
Oct 9, 2026

Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

Standard Policy Gradient (PG) algorithms suffer from high estimation variance because they rely on Monte Carlo updates. While off-policy variance reduction mitigates this problem, establishing optimal sample complexity currently requires either restrictive assumptions, such as uniformly bounded importance weights, or impractical second-order operations. In this work, we introduce Loopless Variance-Reduced PG (LVR-PG), a unified theoretical framework that abstracts a class of first-order estimators that integrate recursive updates with defensive importance sampling, including known estimators such as PAGE-PG and STORM-PG. We prove that this algorithmic class achieves O~(ε−2)\tilde{\mathcal{O}}(ε^{-2}) last-iterate global convergence under weak gradient domination for general parametric policies. We establish this guarantee using purely first-order updates, with minimal assumptions and without gradient preconditioners. By extending state-of-the-art lower bounds to continuous parametric policies, we establish an Ω(ε−2)Ω(ε^{-2}) sample complexity limit, confirming our framework is minimax-optimal up to logarithmic factors and horizon terms.
Oct 8, 2026

Estimating Great Expectations Under Autoregressive Language Models with Potentials

Many applications of language models require estimating the expectation of a test functional under the model. Obtaining precise estimates can be computationally expensive. We show how to improve estimation precision by exploiting next-token conditional probabilities available as a by-product of sampling. Our approach uses potentials: real-valued functions of prefixes that induce an additive decomposition of the test functional. We construct a family of estimators parameterized by these potentials and derive conditions for variance reduction. Across applications including entropy estimation, watermark detection, and rare-event probability estimation, our estimators achieve substantial variance reductions relative to Monte Carlo and importance sampling baselines at comparable computational cost.
Oct 7, 2026

Transformed Samplers with Variance Reduction

Markov chain Monte Carlo (MCMC) methods are the standard tool for computing expectations under complex probability distributions. Control variates reduce the variance of the resulting estimates, but a good control variate requires solving the Poisson equation of the sampler, which rarely admits a closed-form solution. Exact solutions are available when the sampler's kernel has a known spectral decomposition on a simple reference density. In our work, we extend these solutions to general targets through a learned change of variables. A bijection, such as a normalizing flow, is trained so that the target becomes close to the reference in a latent space, and we show that Markov kernels and their Poisson solutions are transformed by any bijection. Running such samplers in the latent space then yields explicit control variates, and the estimator is consistent under mild tail conditions on the map and target. Importance sampling (IS) from the flow is the limiting case of the same construction and the control variates apply to it as well. Experiments on synthetic targets and real posteriors compare the procedure against state-of-the-art samplers and control variates.
Oct 7, 2026

Dataset Pruning from First Principles: A Label-Free Linear Programming Approach

Dataset pruning reduces a large training set to a representative subset while preserving model performance. Existing geometry-based methods typically assume that nearby points in embedding space share similar properties. Rather than imposing this assumption, we derive geometric selection criteria by reformulating unbiased subset selection as a variance minimization problem. Unbiasedness ensures that unweighted subset averages recover full-dataset averages in expectation, including losses and gradients at fixed model parameters. Specifically, we characterize a family of unbiased subset selection algorithms as a high-dimensional polytope. In this context, minimizing the expected sampling variance is a linear objective. Differences in sampling variance, averaged over rigid motions, admit closed-form pairwise expressions. Because the polytope has high dimension, directly applying standard linear programming is impractical. We instead use these expressions to construct an efficient vertex walk that optimizes an approximation of the variance objective while preserving unbiasedness, yielding a method that requires neither labels nor model training during selection. Across CIFAR-10, MNIST, and CelebA benchmarks, our method matches or exceeds uniform sampling in mean test accuracy at every evaluated budget and outperforms competing geometric methods in several settings, particularly at small selection budgets. Beyond dataset pruning, the same framework reduces stochastic-gradient variance by increasing diversity within mini-batches while keeping the batch size unchanged.
Oct 5, 2026

Robust Importance Sampling for Rare Events via Constrained Gaussian Mixtures

We study estimating rare-event probabilities I=P(g(X)>γ)I = \mathbb{P}(g(\mathbf{X}) > γ) with X∼N(μ,Σ)\mathbf{X} \sim \mathcal{N}(\boldsymbolμ, \boldsymbolΣ) and general g:Rd→Rg : \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.
Oct 4, 2026

SteadySplats: Resampling of Low-Variance Gaussians for High-Fidelity Stochastic Rendering

Stochastic order-independent transparency enables efficient and elegant rendering of primitive-based radiance fields like 3D Gaussian Splatting models, but remains impractical due to the inherent visible noise in the output. We propose a principled approach to minimize high-frequency noise, addressing its sources at the representation and image synthesis level. During stochastic rendering, our history-based spatial resampling scheme drastically accelerates image convergence, while temporal importance resampling ensures coherence under camera movement. During training, a color regularizer implicitly reduces the variance along view rays in the 3DGS models. With these properties, our optimized, Vulkan-based renderer effectively mitigates output noise at low and high sample counts, achieving a substantial 13~dB PSNR increase in quality over previous stochastic methods at 1 sample per pixel and quickly converging to sorted 3DGS with an average L1 error of less than 10−410^{-4}.
Oct 4, 2026

ResOPD: Tail Residualization for Sparse On-Policy Distillation

On-policy distillation (OPD) trains a student model on self-generated trajectories, but transmitting dense teacher distributions across long reasoning traces creates prohibitive communication and memory bottlenecks. Practical systems therefore rely on sparse teacher interfaces, typically transmitting either the sampled-token score or a small Top-kk distribution. However, this sparse setting faces a fundamental dilemma: sampled-token estimators are unbiased but suffer from severe gradient variance, whereas directly optimizing Top-kk objectives introduces systematic bias. To improve this trade-off, we propose ResOPD (On-Policy Distillation with Tail Residualization), which provides unbiased full-vocabulary reverse KL gradient estimation under on-policy sampling, with substantial variance reduction under the same sparse payload in the evaluated settings. ResOPD aggregates the unobserved vocabulary into an observable coarse tail event, computes its exact aggregate gradient, and samples only the fine-grained within-tail residual, which requires no additional teacher queries or forward passes. Extensive experiments demonstrate that ResOPD substantially reduces gradient variance, stabilizes online training dynamics, and improves downstream performance across the evaluated settings. These results establish ResOPD as an efficient, plug-and-play variance reduction primitive for sparse on-policy distillation.
Oct 3, 2026

Variance-Optimal Control Variates for Learning with Black-box Feedback

Modern models increasingly learn through black-box oracles such as humans, optimization solvers, and external tools that provide feedback without exposing their internal mechanisms. A common remedy is to learn an (action-)value function as a control variate. In this paper, we first observe that even an exact action-value function can be arbitrarily far from variance-optimal. We show that this gap arises because the value function minimizes the noise in each action's own gradient term, while an action can still affect the rest of the gradient estimator through shared parameters. A simple unbiased correction, at no extra oracle cost, can still reduce its variance by an arbitrarily large factor. Motivated by this, we then prove that the residual variance can be decomposed exactly by actions with no cross terms. This decomposition yields a closed-form variance-minimizing correction for neural-network parameters, which can be computed by a simple projection. Empirically, our correction consistently reduces the variance left by the value function and improves learning across all tasks. The source code for all experiments is available at https://github.com/Zihao-Kevin/black_box_opt.
Sep 29, 2026

Tail-Influence Sampling for CVaR Policy Evaluation

Policies with similar mean returns can differ sharply in rare failures, yet estimating lower-tail conditional value-at-risk (CVaR) accurately can require many costly rollouts. When different conditional components of a stochastic workflow can be queried separately, we ask how to allocate a fixed evaluation budget to estimate a fixed policy's CVaR most accurately. We derive a tail influence for each queryable conditional law that aggregates how its uncertainty affects CVaR across every Bellman reuse. Its variance yields the fixed-design efficiency bound and the oracle Neyman allocation. Tail-Influence Sampling (TIS) estimates these influence scales from a pilot model and reallocates fresh queries toward kernels that matter most for the tail; a visitation-anchored variant protects against pilot underallocation. Under fixed dimension and a positive quantile margin, TIS attains oracle asymptotic variance and first-order MSE including pilot cost, while the anchored variant is within a factor two of the oracle. We also characterize an exact-grid regime in which tail- and mean-optimal allocations coincide. On CliffWalking, TIS reduces MSE by 41% versus learned occupancy and 76% versus complete rollouts at the same charged transition budget. In frozen language-model review workflows, anchored TIS beats an equally regularized mean-influence blend in 23 of 24 MMLU-Pro settings and reaches 2.4-3.4×\times lower MSE than rollouts on six-call FinQA reviews.
Sep 27, 2026

OSCC: Certified Observation-Safe Coupling Optimization for Gradient-Noise Control in Imperfect-Information Learning

Coupled rollouts can reduce the noise of counterfactual action comparisons, but two issues prevent standard common-random-number constructions from serving as a general learning primitive in imperfect-information environments. First, an invalid coupling may expose hidden state, synchronize endogenous policy randomness, or misalign chance events after counterfactual histories diverge. Second, in multi-action policy optimization, lower return-contrast variance is not by itself the relevant objective: the optimizer depends on the return covariance matrix after projection through the local policy-gradient geometry. We introduce observation-safe counterfactual coupling (OSCC), a framework that defines an admissible class through marginal preservation, information-state safety, branch-local policy randomness, semantic event alignment, and trace-before-oracle replay. We derive a gradient-aware coupling criterion showing that, for marginal-preserving couplings, policy-gradient noise changes are determined by policy-Jacobian-weighted off-diagonal return covariance. This motivates OSCC-Select, a calibration-only selector that chooses among independent, root-only, continuation-only, and fully coupled rollouts using separate safety and gain certificates. Its gain target combines projected gradient noise with measured physical sampling cost and falls back to independent sampling whenever a simultaneous lower confidence bound does not certify improvement. On 100,000 fixed-root Leduc comparisons, the fully coupled CP-GRPO instantiation reduces return-contrast variance from 41.1158 to 18.1441, a 55.87% reduction, while preserving the declared branch marginals. With three actions, OSCC-Select chooses continuation coupling and attains gradient-noise trace 0.0783 versus 0.0917 for return-variance selection. Increasing calibration from 64 to 2,048 groups raises certification from 0.327 to 0.995.
Sep 23, 2026

Private Decentralized Optimization with Noise Reduction and Bias Correction

Private decentralized learning is affected by sampling noise, privacy noise, and decentralized bias under heterogeneous data. We propose Private Recursive Decentralized Optimization (PRDO). PRDO uses recursive estimation with same-batch gradient differences to reduce estimation errors caused by sampling and privacy noise, while its Exact Diffusion component corrects decentralized bias arising from data heterogeneity. Our analysis establishes a nonconvex convergence bound without assuming uniformly bounded data heterogeneity across nodes. It further gives a sufficient condition under which recursive gradient differences yield strictly lower query sensitivity than private Exact Diffusion, together with an example that rigorously satisfies this condition. Experiments show improved accuracy over the evaluated baselines.
Sep 22, 2026

Gaussian Flow-Matching Schedules: Implications for Sampling and Training

Flow-matching schedules affect both sampling dynamics and the variance of the regression target. For centered commuting Gaussians, we show that a direction-dependent schedule decomposes into two independent design choices: a variance path, which fully determines the intermediate laws and probability flow, and a factorization, which leaves this flow unchanged while controlling irreducible regression variance. On the sampling side, we analyze finite-step Euler accuracy and derive a necessary drift bound for exact N -step sampling, connecting the geodesic and the logarithmic path. On the training side, for any fixed path, we derive closed-form factorizations that either minimize time-averaged regression variance or make it constant along the path.
Sep 20, 2026

Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments

Online controlled experiments, or A/B tests, are widely used to estimate causal effects on digital platforms. A central challenge is to improve experimental sensitivity, or statistical power, without increasing the experimental sample size. Stratified sampling is a classical variance reduction technique; however, its effectiveness depends critically on how the strata are constructed. We thus propose an optimization-based stratification framework for stratified sampling using optimal multi-way decision trees. Our method, called Optimal Multi-way Stratification Trees (OMST), formulates stratification as a path-selection problem over a feature graph. The selected paths define interpretable stratification rules and are optimized using an exact variance-minimizing binary optimization formulation under continuous proportional allocation and a Neyman-type optimal allocation. We incorporate supervised optimal binning to generate outcome-relevant candidate splits for numerical features. Furthermore, we introduce reduction procedures for redundant candidate paths and assignment constraints, substantially reducing the optimization problem size. Experiments on both a real-world and a simulated dataset demonstrate that OMST achieves comparable or superior variance reduction to existing methods while maintaining shallow and interpretable stratification trees.