Adaptive Sample Allocation under Heterogeneous Variance

63 concepts41 papers2 proposals

When running an A/B test, a clinical trial, or a Monte Carlo simulation, the standard operating procedure is almost always uniform allocation. We split web traffic 50/50 between two features, randomize patients equally across treatment arms, or pull samples uniformly from a data distribution.

This equal-allocation approach relies on a hidden, often false assumption: homoscedasticity, or the idea that all groups exhibit the same internal variance. In the real world, different groups are frequently heteroscedastic. One treatment might have highly predictable outcomes, while another is wildly volatile.

As Kaufmann et al. demonstrate in On the Complexity of A/B Testing, uniform sampling is mathematically suboptimal when variances differ. Equal allocation wastes valuable sampling budget on low-variance groups that are already well-understood, while leaving high-variance groups under-sampled and uncertain. To minimize the overall uncertainty of an experiment, we must allocate samples where the noise is highest. This insight forms the foundation of Adaptive Neyman Allocation.

The Intuition: Why Equal Allocation Fails

To understand why uniform sampling fails, consider the task of estimating the Average Treatment Effect (ATE) between a treatment group ($A$) and a control group ($B$). The variance of our ATE estimator is the sum of the variances of the individual group means:

$$\text{Var}(\widehat{\text{ATE}}) = \frac{\sigma_A^2}{n_A} + \frac{\sigma_B^2}{n_B}$$

If we have a fixed total sample budget $N = n_A + n_B$, how should we divide it? If $\sigma_A^2 = \sigma_B^2$, a 50/50 split ($n_A = n_B$) minimizes the total variance. But what if the treatment group is highly unpredictable, meaning $\sigma_A^2$ is four times larger than $\sigma_B^2$?

If we stick to an equal split, the first term ($\frac{4\sigma_B^2}{N/2}$) contributes far more to our overall error than the second term ($\frac{\sigma_B^2}{N/2}$). By shifting samples away from the quiet control group and into the volatile treatment group, we can drastically reduce the total variance of our estimator without needing more data.

The mathematically optimal solution to this budget allocation problem is known as Neyman Allocation: the number of samples assigned to a group should be directly proportional to its standard deviation ($n_k \propto \sigma_k$). As Deep et al. show in Asymptotically Optimal and Computationally Efficient Average Treatment Effect Estimation in A/B testing, adjusting assignment ratios to match running standard deviations can reduce the total sample size required to reach a target precision by up to 50%.

Uniform Allocation (50/50):
[ Arm A: Low Variance  ] -> [■■■■■■■■■■] (Over-sampled; precision wasted)
[ Arm B: High Variance ] -> [■■■■■■■■■■] (Under-sampled; high uncertainty)

Neyman Allocation (Proportional to σ):
[ Arm A: Low Variance  ] -> [■■■■]      (Sufficient precision)
[ Arm B: High Variance ] -> [■■■■■■■■■■■■■■■■] (More samples to conquer noise)

The Sequential Challenge: Learning Variances on the Fly

Neyman allocation provides an elegant theoretical target, but it introduces a practical catch: we cannot allocate samples based on variance if we do not know the variances in advance.

To resolve this, researchers use sequential, response-adaptive experimental designs. The experiment starts with a balanced allocation to gather baseline data, estimates the variances of each arm on the fly, and dynamically updates the assignment probabilities for subsequent participants. Early theoretical foundations laid by Chambaz et al. in Targeting the Optimal Design in Randomized Clinical Trials with Binary Outcomes and No Covariate: Theoretical Study proved that these adaptive randomization strategies successfully converge to the optimal "oracle" design over time.

However, moving from asymptotic convergence to finite-time guarantees is challenging. Every time an algorithm misestimates the true variance early in an experiment, it deviates from the optimal allocation ratio. This deviation accumulates what is known as Neyman regret—the gap between the variance achieved by an online algorithm and the theoretical minimum variance of the oracle Neyman allocation.

In CLIP-OGD: An Experimental Design for Adaptive Neyman Allocation in Sequential Experiments, Dai et al. framed this tracking problem as an online optimization task. By utilizing online gradient descent (OGD) with clipped propensity scores, the authors proved that an experiment can actively minimize its Neyman regret. They also highlighted a fundamental trade-off: you cannot simultaneously maximize participant outcomes (the goal of traditional multi-armed bandits) and minimize the variance of your treatment effect estimate.

Recently, Neopane et al. achieved an exponential theoretical improvement in Logarithmic Neyman Regret for Adaptive Estimation of the Average Treatment Effect. While previous state-of-the-art methods suffered a square-root regret ($O(\sqrt{T})$), the authors introduced an algorithm called ClipSMT that guarantees a logarithmic Neyman regret ($O(\log T)$), proving that adaptive variance tracking can be incredibly tight even in finite samples.

Asymmetric Risks and Optimistic Tracking

When designing algorithms to track Neyman allocation in real time, we must account for a critical mathematical asymmetry. In Optimistic Algorithms for Adaptive Estimation of the Average Treatment Effect, Neopane et al. point out that the precision of an ATE estimate is far more sensitive to under-sampling an arm than to over-sampling it.

If an algorithm mistakenly underestimates the variance of a noisy arm early on, it will drastically cut its sample allocation. Because the arm receives very few samples, its variance estimate remains stagnant and incorrect, causing the overall estimator variance to explode. Conversely, if the algorithm over-samples a low-variance arm, the statistical penalty is mild, and the extra data quickly corrects the variance estimate.

To protect against catastrophic under-sampling, modern tracking algorithms borrow the "optimism in the face of uncertainty" principle from the multi-armed bandit literature. Algorithms like OPTrack construct upper confidence bounds for the standard deviations of each arm. When an arm's variance is highly uncertain, the algorithm optimistically over-samples it. This ensures that the system aggressively explores uncertain arms, refines its variance estimates, and safely converges to the true Neyman allocation.

Generalizing the Principle

The core insight of variance-proportional sample allocation extends far beyond simple A/B tests and clinical trials. It serves as a powerful tool across machine learning and statistical computing wherever heteroscedasticity appears:

  • Stratified Monte Carlo Integration: In numerical integration, uniform sampling across a domain is highly inefficient if certain sub-regions contain sharp peaks or high volatility. Carpentier et al. demonstrate in Finite Time Analysis of Stratified Sampling for Monte Carlo and subsequent work that adaptively allocating the remaining evaluation budget to high-variance strata minimizes the total integration risk. Similarly, in Bayesian computation, Fu et al. use clustering to partition data and allocate Stochastic Gradient MCMC samples based on the internal variance of each cluster, accelerating convergence.
  • Experimental Noncompliance: In real-world trials, participants do not always comply with their assigned treatments. In Efficient Adaptive Experimentation with Noncompliance, Oprescu et al. show that noncompliance dilutes the experimental signal. To maintain a high signal-to-noise ratio, the optimal experimental design must dynamically over-sample groups where compliance is low or outcome noise is high.
  • Distributed and Matrix Systems: In federated learning, Song et al. apply this principle to client selection, allocating communication slots proportionally to the internal diversity (variance) of client clusters to stabilize model updates. In matrix estimation, Shin et al. introduce an Adaptive Power Method that concentrates a fixed observation budget on the highest-variance rows of a matrix, minimizing vector estimation errors in sparse networks.

By abandoning the rigid assumption of uniform variance and actively directing resources toward noise, adaptive sample allocation transforms heteroscedasticity from a statistical hurdle into an opportunity for massive efficiency gains.

Key Foundational Work

Targeting the Optimal Design in Randomized Clinical Trials with Binary Outcomes and No Covariate: Theoretical Study (2011) — contributed 2 concept elements to this direction.
Finite Time Analysis of Stratified Sampling for Monte Carlo (2011) — contributed 1 concept elements to this direction.
On Auditing Elections When Precincts Have Different Sizes (2008) — 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_neyman_allocation_fd85f345,
  title = {Neyman allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/neyman-allocation/rdr_fd85f345f866460a84c78bc9e813d461},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_neyman_allocation_fd85f345_v1,
  title = {Neyman allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/neyman-allocation/rdr_fd85f345f866460a84c78bc9e813d461/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake