# From Augmentation to Decomposition: A New Look at CUPED in 2023

Alex Deng1 Luke Hagar2 Nathaniel Stevens 2 Tatiana Xifara1
Lo-Hua Yuan1 Amit Gandhi1
1 Airbnb 2 University of Waterloo
{alex.deng, tatiana.xifara, lohua.yuan<EMAIL_ADDRESS>
{nstevens<EMAIL_ADDRESS>
###### Abstract

Ten years ago, CUPED (Controlled Experiments Utilizing Pre-Experiment Data)
(Deng et al., 2013) mainstreamed the idea of variance reduction leveraging
pre-experiment covariates. Since its introduction, it has been implemented,
extended, and modernized by major online experimentation platforms (Xie and
Aurisset, 2016; Guo et al., 2021; Poyarkov et al., 2016; Jin and Ba, 2023;
Cosgrove et al., 2022). Many researchers and practitioners often interpret
CUPED as a regression adjustment (Lin, 2013; Tsiatis et al., 2008). In this
article, we clarify its similarities and differences to regression adjustment
and present CUPED as a more general augmentation framework which is closer to
the spirit of the 2013 paper. We show that the augmentation view naturally
leads to cleaner developments of variance reduction beyond simple average
metrics, including ratio metrics and percentile metrics. Moreover, the
augmentation view can go beyond using pre-experiment data and leverage in-
experiment data, leading to significantly larger variance reduction. We
further introduce metric decomposition using approximate null augmentation
(ANA) as a mental model for in-experiment variance reduction. We study it
under both a Bayesian framework and a frequentist optimal proxy metric
framework. Metric decomposition arises naturally in conversion funnels, so
this work has broad applicability.

##  1 Introduction

The CUPED method proposed by Deng et al. (2013) was inspired by the method of
control variates from stochastic simulation (Asmussen and Glynn, 2008; Owen,
2013). CUPED is a model-free method that relies only on the observation that
any pre-experiment difference between two randomized groups is pure noise due
to randomization and should be $0$ in expectation. The model-free aspect is at
the heart of CUPED; there is no assumption of a relationship of any form
between the covariates and the target metric, as long as they have a nonzero
correlation to exploit. Also, the authors developed the theory directly on
estimators (of metrics and $\Delta$’s), instead of modeling individual
subject-level data points like regression models do. However, many blogs and
papers citing CUPED often interpret it as a regression adjustment method,
focusing on defining it in terms of averages of individual residuals.

2023 marks a decade since CUPED’s initial publication. In this work, we
present CUPED as an augmentation framework which is closer to the spirit of
the in initial proposal in the 2013 paper. We show that the augmentation view
naturally leads to variance reduction beyond simple average metrics; it easily
handles ratio metrics and percentile metrics as well. Moreover, the
augmentation view can go beyond using pre-experiment data and leverage in-
experiment data, leading to significantly larger variance reduction. We
further introduce metric decomposition as a mental model for in-experiment
variance reduction and present a Bayesian variance reduction framework. Metric
decomposition arises naturally in conversion funnels, so this work has broad
applicability.

#### Notation

Henceforth, we denote the observed metric value from the treatment and control
groups as $M_{t}$ and $M_{c}$, the unknown true average treatment effect (ATE)
as $\delta$, and we use $\widehat{\delta}=M_{t}-M_{c}$ to denote the naive
estimate of $\delta$ based on the difference between two metric values. This
is also denoted as $\Delta$.

##  2 CUPED as Augmentation

###  2.1 Three Simple Insights that Underlie CUPED

#### First insight: Augmentation with Mean-Zero Term

For any estimator $\widehat{\delta}$ of $\delta$, define a new estimator

$\widehat{\delta}^{*}=\widehat{\delta}+\widehat{\delta}_{0}\ $ (1)

such that $\mathbb{E}\left[\widehat{\delta}_{0}\right]=0$ . Then
$\widehat{\delta}^{*}$ is also an estimator of $\delta$ and is unbiased if
$\widehat{\delta}$ is. Thus, the CUPED estimator is a mean-preserving
augmentation of any existing estimator. The purpose of the augmentation is to
find an augmentation such that
$\mathrm{Var}\left[\widehat{\delta}^{*}\right]<\mathrm{Var}\left[\widehat{\delta}\right]\
.$

#### Second Insight: Optimal Variance Reduction from a Linear Family

The second insight of CUPED is that variance reduction is almost guaranteed
with any mean-zero augmentation $\widehat{\delta_{0}}$! This is because any
mean-zero augmentation can be multiplied by a scalar $\theta$ yielding a whole
family of mean-zero augmentations
$\widehat{\delta}^{*}(\theta)=\widehat{\delta}+\theta\widehat{\delta_{0}}$,
with variance
$\mathrm{Var}\left[\widehat{\delta}^{*}(\theta)\right]=\mathrm{Var}\left[\widehat{\delta}\right]+\theta^{2}\mathrm{Var}\left[\widehat{\delta}_{0}\right]+2\theta\text{Cov}\left[\widehat{\delta},\widehat{\delta}_{0}\right]$.
This variance is minimized when

$\theta\equiv-\frac{\text{Cov}\left[\widehat{\delta}_{0},\widehat{\delta}\right]}{\mathrm{Var}\left[\widehat{\delta}_{0}\right]}$

with minimum variance

$\mathrm{Var}\left[\widehat{\delta}^{*}(\theta)\right]=\mathrm{Var}\left[\widehat{\delta}\right]\times\left(1-\frac{\text{Cov}\left[\widehat{\delta}_{0},\widehat{\delta}\right]^{2}}{\mathrm{Var}\left[\widehat{\delta}\right]\mathrm{Var}\left[\widehat{\delta}_{0}\right]}\right)=\mathrm{Var}\left[\widehat{\delta}\right]\times\left(1-\text{Corr}\left[\widehat{\delta},\widehat{\delta_{0}}\right]^{2}\right)\
.$

The amount of variance reduction from augmentation by $\widehat{\delta_{0}}$
is equal to the correlation between the augmentation term and the existing
estimator $\text{Corr}\left[\widehat{\delta},\widehat{\delta_{0}}\right]^{2}$.
Any mean-zero augmentation is like a direction of gradient descent, and
variance is optimally reduced with an appropriate choice of step size.

#### Third Insight: Existence of Mean-Zero Augmentation

The final insight of CUPED is that mean-zero augmentations are abundant if we
tap into pre-experiment period data. Let $M(\mathbf{X}_{pre})$ be any metric
computed from a (multivariate) signal $\mathbf{X}$ on pre-experiment period
data (e.g., $\overline{f(\mathbf{X})}$ or a percentile, etc.). Then
$\Delta_{pre}(M)=M(\mathbf{X}_{pre})_{t}-M(\mathbf{X}_{pre})_{c}$ is a mean-
zero augmentation.

###  2.2 Relation to Regression Adjustment

When the metric of interest is a simple average and the naive estimator of ATE
is the difference in means $\widehat{\delta}=\Delta(Y)$, and the augmentation
is also a difference in means $\Delta(Y)^{*}=\Delta(Y)-\theta\Delta(X)$, CUPED
is often compared to regression adjustment of the form

$Y_{i}=\alpha+\delta A_{i}+\beta X_{i}+\epsilon_{i}\,.$ (ANCOVA1)

and

$Y_{i}=\alpha+\delta A_{i}+\beta X_{i}+(\gamma X_{i})A_{i}+\epsilon_{i}\,,$
(ANCOVA2)

where $A_{i}$ is the treatment assignment assignment indicator. Tsiatis et al.
(2008) showed both ANCOVA1 and ANCOVA2 estimate $\delta$ asymptotically by

$\overline{Y_{t}}-\overline{Y_{c}}-(\overline{f(X_{t})}-\overline{f(X_{c})})\,,$

for some function $f$. Therefore, we can see ANCOVA1 and ANCOVA2 are both
asymptotically special cases of CUPED. The difference between ANCOVA1 and
ANCOVA2 relates to the choice of how to fit the function $f(X)$ using
treatment and control data. The linear regression coefficient estimator is
$\mathrm{Cov}(X,Y)/\mathrm{Var}[X]$, where the denominator $\mathrm{Var}[X]$
is the same for treatment and control. However, $\mathrm{Cov}[X,Y]$ differs
from treatment to control due to the treatment effect. ANCOVA1 pools the data
together and fits a linear regression. In this case we have

$\mathrm{Cov}[X,Y]=p\mathrm{Cov}_{T}[X,Y]+(1-p)\mathrm{Cov}_{C}[X,Y]\,,$

where $\mathrm{Cov}_{T}(X,Y)$ and $\mathrm{Cov}_{C}(X,Y)$ are the covariances
in the treatment and control groups respectively. Note that $p$ is the
proportion of all units in the treatment group. On the other hand, ANCOVA2
uses

$\mathrm{Cov}[X,Y]=(1-p)\mathrm{Cov}_{T}[X,Y]+p\mathrm{Cov}_{C}[X,Y]\,.$

For CUPED, the optimal $\theta$ is

$\theta^{*}=\frac{Cov[\overline{Y_{t}},\overline{X_{t}}]+Cov[\overline{Y_{c}},\overline{X_{c}}]}{Var[\overline{X_{t}}]+Var[\overline{X_{c}}]}\
.$ (2)

This $\theta$ asymptotically converges to
$(1-p)\mathrm{Cov}_{T}[X,Y]+p\mathrm{Cov}_{C}[X,Y]$. Hence CUPED with this
arrangement of $\theta$ is asymptotically equivalent to ANCOVA2. Because
$\mathrm{Cov}[\overline{Y_{t}},\overline{X_{t}}]=\mathrm{Cov}_{T}[X,Y]/n_{t}$
and
$\mathrm{Cov}[\overline{Y_{c}},\overline{X_{c}}]=\mathrm{Cov}_{C}[X,Y]/n_{c}$,
we can see covariances are weighted inversely proportional to the sample
sizes. This explains why it is better to weight $\mathrm{Cov}_{T}[X,Y]$ by
$1-p$ and $\mathrm{Cov}_{C}[X,Y]$ by $p$, instead of using a more
straightforward choice of $p$ for $\mathrm{Cov}_{T}[X,Y]$ and $1-p$ for
$\mathrm{Cov}_{C}[X,Y]$ as in ANCOVA1. From here we also see ANCOVA2 is
theoretically better than ANCOVA1, as advocated by (Lin, 2013). In practice
this difference is small unless $p$ is far from 0.5 and
$\mathrm{Cov}_{T}[X,Y]$ is very different from $\mathrm{Cov}_{C}[X,Y]$. When
$p=0.5$, ANCOVA1 and ANCOVA2 are equivalent.

##  3 Advantages of the Augmentation View

In the previous section we showed that CUPED is asymptotically equivalent to
ANCOVA2 when applied to simple average metrics, and CUPED is also
asymptotically equivalent ANCOVA1 when the treatment and control groups are
the same size. But the advantage of CUPED is its augmentation view can
naturally lead to variance reduction beyond simple average metrics. The
augmentation term does not even need to be related to a difference of metric
values in the treatment and control groups. We summarize the advantages of the
CUPED augmentation view as follows.

#### Flexible Metric Form

As an augmentation to any estimator of interest, it is clear that the theory
of CUPED doesn’t depend on the metric being an average; CUPED can also be
applied to percentile metrics and ratio metrics straightforwardly. These are
common challenges when practitioners try to implement CUPED with the
regression residual interpretation.

#### Flexible Augmentation Form

The augmentation $\widehat{\delta_{0}}$ does not have to be in the form of a
difference of two metric values. One recent development of this idea is
illustrated in Deng et al. (2023b), where the augmentation term
$\widehat{\delta_{0}}$ is constructed from matching and balancing methods in
observational causal inference.

##  4 Metric Decomposition with Approximately Null Augmentation (ANA)

We can extend the augmentation view further and consider an augmentation that
is not guaranteed to have mean zero. This is motivated by the idea of metric
decomposition, where we decompose a metric into two components where treatment
effects are believed to be mostly captured in one of the two components.
Specifically, let

$M=M_{1}+M_{2}~{}~{}~{}\text{and}~{}~{}~{}\Delta(M)=\Delta(M_{1})+\Delta(M_{2})$

where the true effect also has the decomposition
$\delta=\delta_{1}+\delta_{2}$. If $\delta_{1}$ is close to 0 in most cases,
and $M_{1}$ accounts for a significant portion of variation in $M$, treating
$\Delta(M_{1})$ as an augmentation and using
$\Delta(M_{2})=\Delta(M)-\Delta(M_{1})$ can yield significant variance
reduction.

Compared to CUPED, we no longer have the guarantee that the augmentation has
mean zero. We call this scenario approximate null augmentation (ANA). Let
$\undertilde{\Delta}=(\Delta_{1},\Delta_{2})$ be the decomposed vector of
$\Delta(M_{1})$ and $\Delta(M_{2})$, and let
$\undertilde{\delta}=(\delta_{1},\delta_{2})$ be the vector of true effect for
the two components. Then

$\undertilde{\Delta}\sim\undertilde{\delta}+\undertilde{\varepsilon}$

where $\undertilde{\varepsilon}$ has known covariance matrix $\Sigma(n)$ and
is assumed to be approximately normally distributed due to the Central Limit
Theorem. The effect $\undertilde{\delta}$ follows a bivariate normal
distribution with variance-covariance matrix $\Lambda$. Taking an empirical
Bayes approach, assuming $\undertilde{\delta}$ has mean $(0,0)$, we can
estimate $\Lambda$ from a set of historical experiments with many realization
of $\undertilde{\Delta}$. Our inference target is
$\delta=\delta_{1}+\delta_{2}$.

###  4.1 Bayesian Variance Reduction

The first research question we studied is how decomposing a metric into two
components changes the Bayesian posterior distribution for $\delta$. In the
simple normal-normal model, assuming $\undertilde{\delta}$ has mean $0$ and
covariance $\Lambda$, we know

$\mathrm{E}\left[\undertilde{\delta}|\undertilde{\Delta}\right]=S\undertilde{\Delta}\
~{}~{}~{}\text{and}~{}~{}~{}\mathrm{Var}\left[\undertilde{\delta}|\undertilde{\Delta}\right]=(I-S)\Lambda$

where $S=\Lambda(\Lambda+\Sigma)^{-1}$. Since
$\delta=(1,1)\cdot\undertilde{\delta}$, we derive the posterior mean to be

$\displaystyle\mathrm{E}\left[\delta|\Delta_{1},\Delta_{2}\right]=C^{-1}\left[(\Lambda_{11}+\Lambda_{12})(\Lambda_{22}+\Sigma_{22})-(\Lambda_{12}+\Sigma_{12})(\Lambda_{12}+\Lambda_{22})\right]\Delta_{1}$
$\displaystyle+C^{-1}\left[(\Lambda_{12}+\Lambda_{22})(\Lambda_{11}+\Sigma_{11})-(\Lambda_{12}+\Sigma_{12})(\Lambda_{11}+\Lambda_{12})\right]\Delta_{2}\,,$
(3)

where
$C=\Lambda_{11}\Lambda_{22}+\Lambda_{11}\Sigma_{22}+\Lambda_{22}\Sigma_{11}+\Sigma_{11}\Sigma_{22}-\Lambda_{12}^{2}-2\Lambda_{12}\Sigma_{12}-\Sigma_{12}^{2}$.

Alternatively, without the ANA metric decomposition,

$\mathrm{E}\left[\delta|\Delta\right]=A\Delta\
,\quad\mathrm{Var}\left[\delta|\Delta\right]=A\sigma^{2}\ ,$

where $A=\frac{\lambda^{2}}{\lambda^{2}+\sigma^{2}}$ with
$\lambda^{2}=\Lambda_{11}+\Lambda_{12}+\Lambda_{21}+\Lambda_{22}$ and
$\sigma^{2}=\Sigma_{11}+\Sigma_{12}+\Sigma_{21}+\Sigma_{22}$. ANA metric
decomposition naturally leads to variance reduction under the Bayesian
framework. We proved that

$1^{T}\cdot(I-S)\Lambda\cdot 1<A\sigma^{2}\,.$

The proof is omitted here but we will demonstrate the finding using empirical
results.

###  4.2 Frequentist Optimal Proxy Metric with Variance Reduction

As an extension of CUPED, ANA can be used as a frequentest estimator and
analyzed as a proxy metric of the form
$\Delta^{*}:=\Delta_{2}+\theta\Delta_{1}$. Comparing to the Bayesian posterior
mean, the main difference is that we do not put a shrinkage factor on the
signal component $\Delta_{2}$, and only shrink the ANA component $\Delta_{1}$.

######  Theorem 1.

Among ANA estimators $\Delta^{*}:=\Delta_{2}+\theta\Delta_{1}$, the mean
squared error $\mathrm{E}[(\delta-\Delta^{*})^{2}]$ is minimized when

$\theta=\frac{\Lambda_{11}-\Sigma_{12}}{\Lambda_{11}+\Sigma_{11}}\,.$ (4)

The correlation between $\delta$ and $\Delta^{*}$ is maximized when

$\theta=\frac{(\Lambda_{12}+\Sigma_{12})(\Lambda_{12}+\Lambda_{22})-(\Lambda_{11}+\Lambda_{12})(\Lambda_{22}+\Sigma_{22})}{(\Lambda_{12}+\Sigma_{12})(\Lambda_{11}+\Lambda_{12})-(\Lambda_{12}+\Lambda_{22})(\Lambda_{11}+\Sigma_{11})}\,.$
(5)

#### Minimizing Effect Prediction Error

The ANA estimator with (4) minimizes the effect prediction error. It is a
generalization of CUPED in the sense that when $\Lambda_{11}=0$,
$\theta=-\Sigma_{12}/\Sigma_{11}$ reduces to CUPED.

#### Maximizing Correlation

Tripuraneni et al. (2023) propose an alternative objective in which interest
lies in maximizing the correlation between the true effect and the estimate.
Comparing (5) to (4.1), we see that the ANA estimator
$\Delta_{2}+\theta\Delta_{1}$ that maximizes the correlation between $\delta$
and $\Delta^{*}$ is simply a rescaled Bayesian posterior mean estimator such
that $\Delta_{2}$ receives no shrinkage.

##  5 Empirical Results

We applied Approximate Null Augmentation to 25 early stage ranking experiments
at Airbnb. These early stage experiments run for roughly 1 week taking a small
percentage of total traffic. The main target metric of interest is booking per
guest. To construct the ANA, we leverage counterfactual ranking results. That
is, for each search, we compare the ranked results produced by the treatment
and control ranker. If a click on a booked listing is ranked in close
proximity according to both rankers, or if a click is from the map and both
rankers would show the listing on the map, then the attributed booking from
this click would be approximately the same regardless of the treatment
assignment. In addition, we use a utility model to attribute a user’s booking
to searches (Deng et al., 2023a). The end result is for each booking, we can
construct an ANA component representing a fraction of the booking that both
rankers would have contributed almost equally.

The effect covariance $\Lambda$ and the average covariance of the noise
$\undertilde{\varepsilon}$ were estimated to be (after scaling by the same
constant)

$\Lambda=\begin{pmatrix}0.576&-0.896\\\
-0.896&4.329\end{pmatrix}\quad\text{and}\quad
E[\Sigma]=\begin{pmatrix}4.020&0.169\\\ 0.169&0.811\end{pmatrix}\ .$

We find the first ANA component $\Delta_{1}$ displays a variance 5 times
larger than the second component $\Delta_{2}$; while the variance of the
effect for the ANA component is less less than 1/7 of $\Delta_{2}$. If the ANA
component has theoretical mean $0$, then the variance of the effect should
also be $0$. A close to $0$ effect variance and a large noise variance (both
relative, comparing to $\Delta_{2}$) mean CUPED using ANA can lead to
significant variance reduction with a small bias trade-off.

$\Delta$ | $\Delta_{1}$ | $\Delta_{2}$ | $\text{ANA}_{corr}$ | $\text{ANA}_{err}$
---|---|---|---|---
4/25 | 2/25 | 8/25 | 8/25 | 8/25
Table 1: Number of statistically significant results out of 25 experiments.
CUPED with ANA maximizing correlation and minimizing error has the same number
of significant results as using Component 2 only ($\theta=0$). Figure 1: Left:
Bayesian posterior using bivariate decomposed model is smaller than without
decomposition. Right: Bivariate model produces larger absolute Bayesian
Z-score.  Figure 2: ANA maximizing correlation has a slightly smaller variance
than ANA minimizing error (Left); but slightly larger variance than
$\Delta_{2}$ (Right). Difference in variances in these 25 experiments are all
very small.

Table 1 demonstrates that using ANA with $\theta=0$ ($\Delta_{2}$), or
maximizing correlation, or minimizing error all lead to more statistically
significant results, compared to the original $\Delta$ before decomposition.
Figure 1 shows that the posterior variance is greatly reduced with the
bivariate model. Furthermore, the Bayesian Z-score (posterior mean divided by
posterior standard deviation) has a greater absolute value under the bivariate
model. Figure 2 compares variances of ANA with $\theta=0$ ($\Delta_{2}$), ANA
maximizing correlation, and ANA minimizing error. All three produces similar
variances.

## References

  * (1)
  * Asmussen and Glynn (2008) Soren Asmussen and Peter Glynn. 2008.  _Stochastic Simulation_.  Springer-Verlag.
  * Cosgrove et al. (2022) Laura Cosgrove, Jen Townsend, and Jonathan Litz. 2022\.  Deep Dive Into Variance Reduction.  https://www.microsoft.com/en-us/research/group/experimentation-platform-exp/articles/deep-dive-into-variance-reduction/.
  * Deng et al. (2023a) Alex Deng, Michelle Du, Anna Matlin, and Qing Zhang. 2023a.  Variance Reduction Using In-Experiment Data: Efficient and Targeted Online Measurement for Sparse and Delayed Outcomes. In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_. 3937–3946.
  * Deng et al. (2013) Alex Deng, Ya Xu, Ron Kohavi, and Toby Walker. 2013\.  Improving the sensitivity of online controlled experiments by utilizing pre-experiment data. In _Proceedings of the 6th ACM WSDM Conference_. 123–132.
  * Deng et al. (2023b) Alex Deng, Lo-Hua Yuan, Naoya Kanai, and Alexandre Salama-Manteau. 2023b.  Zero to hero: Exploiting null effects to achieve variance reduction in experiments with one-sided triggering. In _Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining_. 823–831.
  * Guo et al. (2021) Yongyi Guo, Dominic Coey, Mikael Konutgan, Wenting Li, Chris Schoener, and Matt Goldman. 2021\.  Machine Learning for Variance Reduction in Online Experiments.  _arXiv preprint arXiv:2106.07263_ (2021).
  * Jin and Ba (2023) Ying Jin and Shan Ba. 2023\.  Toward Optimal Variance Reduction in Online Controlled Experiments.  _Technometrics_ 65, 2 (2023), 231–242.
  * Lin (2013) Winston Lin. 2013\.  Agnostic notes on regression adjustments to experimental data: Reexamining Freedman’s critique.  _The Annals of Applied Statistics_ 7, 1 (2013), 295–318.
  * Owen (2013) Art B Owen. 2013\.  Monte Carlo theory, methods and examples.  (2013).
  * Poyarkov et al. (2016) Alexey Poyarkov, Alexey Drutsa, Andrey Khalyavin, Gleb Gusev, and Pavel Serdyukov. 2016.  Boosted decision tree regression adjustment for variance reduction in online controlled experiments. In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. 235–244.
  * Tripuraneni et al. (2023) Nilesh Tripuraneni, Lee Richardson, Alexander D’Amour, Jacopo Soriano, and Steve Yadlowsky. 2023\.  Choosing a Proxy Metric from Past Experiments.  _arXiv preprint arXiv:2309.07893_ (2023).
  * Tsiatis et al. (2008) Anastasios A. Tsiatis, Marie Davidian, Min Zhang, and Xiaomin Lu. 2008.  Covariate adjustment for two-sample treatment comparisons in randomized clinical trials: A principled yet flexible approach.  _Statistics in Medicine_ 27 (2008).
  * Xie and Aurisset (2016) Huizhi Xie and Juliette Aurisset. 2016.  Improving the sensitivity of online controlled experiments: Case studies at netflix. In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM, 645–654.