Variance Reduction

Variance reduction encompasses techniques that improve the precision of Monte Carlo estimators without increasing the sample size. Beyond importance sampling, the toolkit includes stratified sampling (partitioning the domain and sampling proportionally), antithetic variates (using negatively correlated samples to cancel fluctuations), and control variates (exploiting correlation with a tractable quantity to reduce residual variance).

These methods share a common principle: they replace pure randomness with structured randomness that respects known properties of the target. The more structure you can exploit, the less pure Monte Carlo you need — but the more assumptions you make. Variance reduction is therefore a spectrum from pure random sampling to deterministic quadrature, and the optimal point on that spectrum depends on what you know about the problem before you begin. This spectrum mirrors the broader epistemic tension in computational modeling between tractability and fidelity.

Methods and Their Structure

Stratified sampling divides the domain into subregions (strata) and samples proportionally from each. The variance reduction comes from ensuring that all regions are represented, eliminating the possibility of random undersampling of important areas. The method assumes knowledge of how to partition the domain — knowledge that is often unavailable in high-dimensional spaces.

Antithetic variates introduce negative correlation between sample pairs. If one sample is above the mean, its antithetic partner is below. The covariance between pairs cancels some of the variance, reducing the overall estimator variance. This is particularly effective for monotonic functions but can increase variance for non-monotonic ones.

Control variates exploit correlation between the target quantity and a quantity whose expected value is known. The residual (target minus predicted from the control) has lower variance than the target itself. The effectiveness depends on the strength of the correlation — a weakly correlated control variate provides little benefit.

Quasi-Monte Carlo methods replace random samples with deterministic sequences (low-discrepancy sequences) that cover the domain more uniformly than random samples. The Star discrepancy measure quantifies how uniformly a sequence covers the space. The theoretical variance reduction can be dramatic, but the sequences are sensitive to the dimensionality of the problem.

Variance Reduction in Machine Learning

In modern machine learning, variance reduction appears under different names but with the same structural logic:

Bootstrapping and bagging reduce variance by averaging multiple estimators trained on resampled data. The variance of the average is lower than the variance of any individual estimator because the errors are (ideally) uncorrelated.

Variance reduction in reinforcement learning addresses the high variance of Monte Carlo policy gradient estimates. Techniques like Actor-Critic methods introduce a baseline (a control variate) to reduce the variance of the gradient estimate without introducing bias. The baseline is typically a value function estimate that predicts the expected return.

Stochastic gradient descent variance reduction methods like SVRG (Stochastic Variance Reduced Gradient) maintain a full gradient estimate and use it to reduce the variance of stochastic gradient estimates. The method achieves the convergence rate of full gradient descent with the per-iteration cost of stochastic gradient descent.

In each case, the principle is the same: knowledge about structure (the value function, the full gradient, the correlation between estimators) is converted into computational efficiency.

The Epistemology of Variance Reduction

Variance reduction is not merely a technical optimization. It is a philosophical stance about the relationship between knowledge and computation. The claim is that computational efficiency can be gained by exploiting prior knowledge — not by acquiring more data, but by using the data we have more intelligently.

This stance has a dark side. The more structure we assume, the more we risk model misspecification — imposing a structure that does not match reality. A poorly chosen control variate can increase variance. A mis-specified stratification can bias the estimator. The epistemic trade-off is real: we cannot reduce variance without making assumptions, and every assumption is a potential error.

The connection to epistemic infrastructure is direct. The algorithms we teach, the software we distribute, and the benchmarks we use all embody assumptions about structure. When a deep learning framework defaults to a particular initialization scheme or optimization algorithm, it is making a variance reduction choice — implicitly asserting that certain structures are more likely than others. These defaults are not neutral. They are epistemic commitments that shape what models get built and what questions get asked.

Variance reduction is not a technical refinement. It is a philosophical claim: that knowledge about structure can be converted into computational efficiency. The conversion rate is the real measure of what we know. But the conversion is not free. Every assumption we make to reduce variance is a bet, and some bets are wrong. The art of variance reduction is the art of knowing which bets to make — and having the humility to recognize when we have made the wrong ones.