CUPED and Regression-Adjusted Variance Reduction

Summary

CUPED (Controlled-experiment Using Pre-Experiment Data; Deng, Xu, Kohavi & Walker, WSDM 2013) imports the Monte Carlo control variate trick into A/B testing. Replace each arm’s mean $\bar{Y}$ by $\bar{Y}-\theta \bar{X}$, where $X$ is a covariate measured before assignment. Because randomization guarantees $\mathbb{E}{X}^{(t)}=\mathbb{E}{X}^{(c)}$, the adjusted difference ${\Delta }_{cv}$ remains unbiased for the treatment effect, and with the optimal $\theta =\mathrm{cov}(Y,X)/\mathrm{var}(X)$ its variance is $\mathrm{var}(\Delta )(1-{\rho }^2)$. The best covariate is almost always the same metric in the pre-period. On Bing, CUPED cut variance by about 50%, equivalent to doubling traffic or halving run time. The one hard rule: never use a covariate that the treatment could have affected.

Overview

Online experiments chase effects of a fraction of a percent, and the required sample size grows as ${\sigma }^2/{\delta }^2$ (see ^ex-power and Power Analysis and Sample Size). Deng et al. list why simply adding traffic is not enough: effects are tiny, results are needed quickly (especially for harmful treatments), many features have low triggering rates, and traffic must be shared among many concurrent experiments. The alternative to increasing $n$ is decreasing ${\sigma }^2$.

The analysis framework is the two-sample $t$-test, with statistic $\Delta /\sqrt{\mathrm{var}(\Delta )}$ where $\Delta ={\bar{Y}}^{(t)}-{\bar{Y}}^{(c)}$ and, by independence of the arms, $\mathrm{var}(\Delta )=\mathrm{var}({\bar{Y}}^{(t)})+\mathrm{var}({\bar{Y}}^{(c)})$. So reducing the variance of the difference reduces to reducing the variance of each mean, which is exactly the problem studied in Monte Carlo simulation. The goal is an adjusted estimator ${\Delta }^{\ast }$ that is (i) still unbiased for the mean shift and (ii) lower variance, without the parametric commitments of a linear model (ANCOVA assumes $\mathbb{E}(Y\mid Z,X)={\theta }_0+\delta Z+{\theta }^{\top }X$ and homoscedastic errors) and without the machinery of semiparametric efficiency theory (Tsiatis 2006), to which the result is nonetheless equivalent.

Main Content

Stratification

Split the sampling region into $K$ strata with probabilities $w_k$ and form ${\hat{Y}}_{\text{strat}}={\sum }_k{w}_k{\bar{Y}}_k$. The variance decomposition (Deng et al. Sec. 3.1.1) is

$$\mathrm{var}(\bar{Y})=\sum _{k=1}^K\frac{w_k}{n}{\sigma }_k^2+\sum _{k=1}^K\frac{w_k}{n}({\mu }_k-\mu {)}^2\ge \sum _{k=1}^K\frac{w_k}{n}{\sigma }_k^2=\mathrm{var}({\hat{Y}}_{\text{strat}}),$$

so stratification removes the between-strata variance. Online, users cannot be sampled stratum by stratum because they arrive over time, but strata can be formed after the fact from pre-experiment variables (browser, country, heavy/light user), giving the post-stratified delta ${\Delta }_{\text{strat}}={\sum }_k{w}_k({\bar{Y}}_k^{(t)}-{\bar{Y}}_k^{(c)})$. Because the stratifying variable is pre-experiment it is independent of the treatment effect, which keeps ${\Delta }_{\text{strat}}$ unbiased.

Control variates

Control variate estimator ^def-control-variate

Given i.i.d. pairs $(Y_i,X_i)$ with $\mathbb{E}X$ known, define for any constant $\theta$

$${\hat{Y}}_{cv}=\bar{Y}-\theta \bar{X}+\theta \mathbb{E}X.$$

${\hat{Y}}_{cv}$ is unbiased for $\mathbb{E}Y$ and

$$\mathrm{var}({\hat{Y}}_{cv})=\frac{1}{n}(\mathrm{var}(Y)+{\theta }^2\mathrm{var}(X)-2\theta \mathrm{cov}(Y,X)).$$

Optimal coefficient and variance reduction (Deng et al. Eqs. 4-5) ^thm-cuped-variance

The variance of ${\hat{Y}}_{cv}$ is minimised at

$${\theta }^{\ast }=\frac{\mathrm{cov}(Y,X)}{\mathrm{var}(X)},$$

the OLS slope of $Y$ on $X$, giving

$$\mathrm{var}({\hat{Y}}_{cv})=\mathrm{var}(\bar{Y})(1-{\rho }^2),\rho =\mathrm{cor}(Y,X).$$

With several covariates $1-{\rho }^2$ becomes $1-R^2$ from the regression of $Y$ on $X$. More generally, among adjustments $\bar{Y}-\overline{f(X)}+\mathbb{E}f(X)$ the optimal $f$ is the regression function $\mathbb{E}(Y\mid X)$.

The CUPED observation

In simulation, the hard part of a control variate is knowing $\mathbb{E}X$. In an experiment we do not need it:

CUPED delta is unbiased (Deng et al. Sec. 3.2.2, Eq. 7) ^thm-cuped-unbiased

If $X$ is constructed only from information that precedes treatment, randomization implies $\mathbb{E}{X}^{(t)}=\mathbb{E}{X}^{(c)}$. Then

$${\Delta }_{cv}={\hat{Y}}_{cv}^{(t)}-{\hat{Y}}_{cv}^{(c)}=({\bar{Y}}^{(t)}-{\bar{Y}}^{(c)})-\theta ({\bar{X}}^{(t)}-{\bar{X}}^{(c)})$$

is unbiased for $\delta =\mathbb{E}\Delta$ (the unknown $\theta \mathbb{E}X$ terms cancel), and with $\theta ={\theta }^{\ast }$,

$$\mathrm{var}({\Delta }_{cv})=\mathrm{var}(\Delta )(1-{\rho }^2).$$

The same $\theta$ must be used in both arms; the simplest estimate is from the pooled treatment-plus-control sample.

Read the formula as: the in-experiment difference, corrected by the chance pre-experiment imbalance between the arms. If the treatment group happened to draw heavier users, ${\bar{X}}^{(t)}-{\bar{X}}^{(c)}>0$ and the raw delta is pulled down accordingly.

Stratification is a special case. With a categorical $X$, using the indicators $1\{X=k\}$ as control variates (whose means are the weights $w_k$) reproduces ${\hat{Y}}_{\text{strat}}$ exactly; the fitted coefficients are ${\hat{\theta }}_k={\bar{Y}}_k-{\bar{Y}}_0$ (Appendix A). Control variates therefore generalise stratification to continuous covariates and avoid having to estimate $w_k$.

Practical guidance (Secs. 4-5)

• Which covariate? Across a large class of metrics, the same metric measured in the pre-experiment period gives the largest reduction. In a 3-week A/A test on queries-per-user: entry-day alone gave 9-10%; pre-period queries-per-user gave more than 45%; both together added only 2-3%.
• How long a pre-period? Two forces compete. Correlation rises with a longer pre-period (better signal-to-noise for cumulative metrics). Coverage, the share of experiment users seen in the pre-period, rises with pre-period length but falls as the experiment runs longer (late arrivals are new or cookie-churned users). Reduction peaked at about two weeks of experiment; 1-2 weeks of pre-period is the recommendation, giving roughly 50% reduction over a wide range of durations.
• Missing pre-period data. Add a binary covariate “appeared in the pre-period” and set the missing $X$ to any constant. This is equivalent to stratifying on presence and then adjusting within the matched stratum.
• Beyond the pre-period. The requirement is only that the treatment cannot affect $X$. Information fixed at a user’s first appearance (e.g. entry day-of-week) or anything established before triggering qualifies, which is useful for low-trigger-rate features.
• Non-user metrics. For page-level metrics such as CTR = clicks / page views with user-level randomization, combine CUPED with the delta method: linearise both ratios and compute $\theta ={\beta }_1^{\top }\Sigma {\beta }_2/{\beta }_2^{\top }\Sigma {\beta }_2$ from the user-level covariance $\Sigma$ of (clicks, views, pre-clicks, pre-views) (Appendix B). Compare Standard Errors and Clustering.
• Where it fails. Revenue-per-user gained less than 5% because pre- and in-experiment revenue are weakly correlated. CUPED works best for metrics with stable heavy/light-user heterogeneity.

Post-treatment covariates bias the estimate (Sec. 5.3) ^warn-post-treatment

In an experiment known to increase queries-per-user, the in-experiment metric Distinct-Queries-per-user is an almost perfect correlate and shrinks the interval dramatically. But the treatment also raised DQ, so $\mathbb{E}{X}^{(t)}\ne \mathbb{E}{X}^{(c)}$ and the “corrected” delta came out significantly negative: a narrow interval around the wrong sign. This is the experimental version of conditioning on a mediator or collider; see Logic of Regression Adjustment.

Relation to regression adjustment

CUPED with one covariate is numerically the ANCOVA estimate from regressing $Y$ on treatment and centred $X$, but its justification is design-based: unbiasedness comes from randomization, not from the linear model being correct. The semiparametric literature (Yang & Tsiatis 2001; Tsiatis et al. 2008) shows ANCOVA-type estimators are asymptotically at least as efficient as the unadjusted test even under misspecification. Later work replaces the linear $\theta X$ with a machine-learned prediction $f(X)$ (Larsen et al. Sec. 2.1), following the optimal-$f$ remark above. This is the opposite use of regression to the one in Logic of Regression Adjustment: there, covariates remove confounding; here there is no confounding to remove, and covariates only soak up outcome variance.

Examples

Slowdown experiment (Sec. 5.1). Bing delayed responses by 250 ms. After two weeks on a small slice the CTR effect was borderline ($p$ just under 0.05); a much larger rerun confirmed it at $p=2\times 10^{-13}$. Re-analysing the original run with CUPED and two-week pre-period CTR as the covariate made the effect significant from day 1, and CUPED on half the users was still more sensitive than the raw $t$-test on all of them. Three later experiments showed reductions of 45%, 52% and 49% with one week of pre-period data.

Code sketch.

import numpy as np
 
def cuped(y, x_pre, treat):
    """y: in-experiment metric, x_pre: same metric pre-assignment, treat: 0/1."""
    theta = np.cov(y, x_pre)[0, 1] / np.var(x_pre, ddof=1)   # pooled, both arms
    y_adj = y - theta * (x_pre - x_pre.mean())
    d = y_adj[treat == 1].mean() - y_adj[treat == 0].mean()
    se = np.sqrt(y_adj[treat == 1].var(ddof=1) / (treat == 1).sum()
               + y_adj[treat == 0].var(ddof=1) / (treat == 0).sum())
    return d, se          # var ratio vs raw is about 1 - corr(y, x_pre)**2

With $\rho =0.7$ the variance falls by $49\%$, so an experiment planned for four weeks reaches the same power in about two.

Connections

• Online Experimentation - Overview — the sensitivity problem CUPED addresses.
• Power Analysis and Sample Size — replace ${\sigma }^2$ by ${\sigma }^2(1-{\rho }^2)$ in any sample-size formula.
• Logic of Regression Adjustment — same algebra, different purpose (precision rather than identification); both forbid post-treatment controls.
• Time-Based Regression Estimator for Geo Experiments — the geo analogue: pre-period control-geo sales predict the counterfactual and absorb variance.
• Geo-Experiment Design and Power Analysis — pre-period matching and stratification of geos is the design-stage counterpart of post-stratification.
• Confidence Sequences — variance-reduced, regression-adjusted estimates can be monitored sequentially; Howard et al.’s ATE sequence accepts arbitrary predictions of the potential outcomes for the same reason.
• The Experimental Ideal — randomization is what makes $\mathbb{E}{X}^{(t)}=\mathbb{E}{X}^{(c)}$.

See Also

• Randomization Inference - Overview
• Differences-in-Differences
• Type S and Type M Errors
• Activity Bias in Advertising
• Poststratification