Variance Reduction via Randomized Quasi-Monte Carlo

16 concepts8 papers2 proposals

When we approximate a complex integral or estimate a gradient in machine learning, our default tool is the Monte Carlo (MC) method. We draw independent, uniformly distributed random samples and average them. The appeal of Monte Carlo lies in its simplicity and statistical guarantees: the resulting estimator is unbiased, and the Central Limit Theorem allows us to easily calculate confidence intervals.

However, pure randomness has a glaring flaw: points chosen completely at random tend to clump together, leaving large, unsampled gaps in the domain. Because of this clumping, the error of a standard Monte Carlo estimation decreases at a sluggish rate of $\mathcal{O}(N^{-1/2})$, meaning that to cut your error in half, you need four times as many samples.

To fix this, mathematicians developed Quasi-Monte Carlo (QMC) methods. Instead of using random points, QMC uses deterministic "low-discrepancy" sequences (such as Sobol' or Halton sequences) designed to fill space as evenly as possible. By actively pushing points away from each other, QMC achieves a significantly faster error convergence rate, often approaching $\mathcal{O}(N^{-1})$.

But QMC introduces a new dilemma: because the sequences are entirely deterministic, we lose the ability to easily estimate variance or construct confidence intervals from the samples themselves. Furthermore, if a deterministic grid happens to align poorly with the periodicities of our target function, it can introduce systematic bias.

Randomized Quasi-Monte Carlo (RQMC) resolves this tension. It provides a "best of both worlds" framework that injects a controlled layer of randomness into deterministic, low-discrepancy sequences. RQMC preserves the uniform, space-filling properties of QMC (maintaining the fast $\mathcal{O}(N^{-1})$ convergence) while ensuring that the estimators are statistically unbiased and amenable to straightforward error estimation.


The Core Intuition: Random, Yet Rigid

How can a sequence of points be simultaneously random and perfectly uniform?

Imagine placing a rigid grid of evenly spaced points onto a square table. If you look at any single point, its position is fixed. Now, imagine picking up the entire grid and shifting it by a random horizontal and vertical distance, wrapping any points that fall off the edge back around to the opposite side.

Pure Monte Carlo (Clumpy)        Quasi-Monte Carlo (Rigid Grid)     Randomized QMC (Shifted Grid)
   .  ..       .                     o   o   o   o                      .   .   .   .
 .      .    .   .                   o   o   o   o                      .   .   .   .
   .  .        .                     o   o   o   o                      .   .   .   .

From the perspective of an observer who doesn't know the shift distance, the absolute position of any individual point on the table is completely random and uniformly distributed. However, the relative distances between the points remain perfectly preserved. The points can never clump together because the underlying rigid structure prevents it.

In practice, researchers use sophisticated randomization techniques beyond simple shifting. As noted by Jansen et al. and Arnold et al., methods like digital b-ary shifting and Owen's scrambling manipulate the digital digits of low-discrepancy sequences. This scrambling ensures that every point is individually distributed according to a uniform distribution, making the resulting integral estimator completely unbiased, while the joint distribution of the points retains its low-discrepancy, space-filling property.


Smoothing Gradients in Machine Learning

This dramatic reduction in variance makes RQMC a powerful drop-in replacement for standard sampling in optimization problems, where noisy gradient estimates can cause algorithms to stall or diverge.

Variational Inference

In Bayesian machine learning, Variational Inference (VI) optimizes a lower bound on the model evidence by taking gradients of expectations. In Quasi-Monte Carlo Variational Inference, Buchholz et al. et al. demonstrated that replacing standard Monte Carlo samples with randomized low-discrepancy sequences drastically reduces gradient variance. This allows optimization to converge orders of magnitude faster and locate better local optima.

Building on this, Owen and Liu paired RQMC with second-order optimization methods like L-BFGS in Quasi-Monte Carlo Quasi-Newton in Variational Bayes. Quasi-Newton methods rely on changes in gradients to estimate the curvature of the optimization landscape, making them notoriously sensitive to noise. By leveraging the highly accurate, low-variance gradients provided by RQMC, the authors successfully unlocked the efficiency of second-order optimization for complex probabilistic models.

Reinforcement Learning

A similar bottleneck exists in continuous control reinforcement learning, where evaluating a policy requires sampling actions from a continuous space. In Policy Learning and Evaluation with Randomized Quasi-Monte Carlo, Arnold et al. et al. applied digital shifts and matrix scrambling to policy evaluation. By covering the action space more uniformly than standard random sampling, they achieved significantly lower variance in policy gradient estimates, accelerating training across a variety of continuous control tasks.


Handling Difficult and Unbounded Integrands

Classical QMC theory provides strict error bounds via the Koksma-Hlawka inequality, but these bounds rely on the assumption that the target function is smooth and bounded (specifically, having finite Hardy-Krause variation). Real-world problems, however, are rarely so well-behaved; they frequently feature singularities, heavy tails, or infinite domains. Recent work in RQMC focuses heavily on overcoming these limitations.

Importance Sampling and Robust Estimators

For unbounded functions common in finance and statistics, Hejing Wang showed in Randomly Shifted Lattice Rules with Importance Sampling and Applications that combining randomly shifted lattice rules with importance sampling can preserve the superior $\mathcal{O}(N^{-1})$ convergence rate. The importance sampling maps the unbounded domain to a manageable structure, while the randomized lattice rules ensure uniform coverage.

When integrands contain severe singularities or heavy-tailed noise, standard averages can still be skewed by outliers. To address this, Gobet et al. introduced a framework in Accelerated convergence of error quantiles using robust randomized quasi Monte Carlo methods that combines robust statistical estimators (such as median-of-means) with Nested Uniform Scrambling (NUS). The NUS preserves the low-discrepancy properties required for variance reduction, while the robust estimators reduce sensitivity to outliers, yielding provably tighter confidence intervals for challenging functions.

Expanding Theoretical Foundations

On a foundational level, the strict requirements of classical QMC theory are being rewritten. In Quasi-Monte Carlo Beyond Hardy-Krause, Jiang and Bansal 0001 developed a randomized algorithm that constructs low-discrepancy point sets using a new measure of function variation. Their approach completely bypasses the limitations of the Hardy-Krause framework, proving a "best of both worlds" theoretical bound that guarantees performance at least as good as standard Monte Carlo, while scaling optimally when the function allows it.


Broadening the Scope: Exploration and Physics

Beyond calculating expectations for optimization, the space-filling nature of RQMC makes it highly effective for global exploration and physical simulations.

In global optimization, purely deterministic sampling can get trapped in unhelpful patterns or miss optima due to rigid grid alignment. In Batch sequential adaptive designs for global optimization, Xiao et al. et al. utilized randomized quasi-random sequences to generate candidate points for parallel batch optimization. The randomization step breaks the rigid alignment of pure QMC, preventing points from clustering and ensuring thorough exploration of high-dimensional hyper-parameter spaces.

Similarly, numerical simulations of quantum mechanics often rely on Markov Chain Monte Carlo (MCMC) to simulate lattice systems, which scales at the standard $\mathcal{O}(N^{-1/2})$ rate. In Quasi-Monte Carlo methods for lattice systems: A first look, Jansen et al. et al. demonstrated that applying scrambled and shifted RQMC sequences to harmonic and anharmonic oscillators achieves an error scaling of $\mathcal{O}(N^{-1})$ or better, opening the door for faster, highly accurate simulations in lattice field theories.

Key Foundational Work

Quasi-Monte Carlo methods for lattice systems: A first look (2014) — contributed 1 concept elements to this direction.
Quasi-Monte Carlo Variational Inference (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_randomized_quasi_monte_carlo_a9883432,
  title = {randomized quasi-Monte Carlo},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-quasi-monte-carlo/rdr_a98834328b1346f1a0dfd34b3c8169eb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_randomized_quasi_monte_carlo_a9883432_v1,
  title = {randomized quasi-Monte Carlo},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-quasi-monte-carlo/rdr_a98834328b1346f1a0dfd34b3c8169eb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake