Timezone: »

Online Balanced Experimental Design
David Arbour · Drew Dimmery · Tung Mai · Anup Rao

Tue Jul 19 01:45 PM -- 01:50 PM (PDT) @ Ballroom 3 & 4

We consider the experimental design problem in an online environment, an important practical task for reducing the variance of estimates in randomized experiments which allows for greater precision, and in turn, improved decision making. In this work, we present algorithms that build on recent advances in online discrepancy minimization which accommodate both arbitrary treatment probabilities and multiple treatments. The proposed algorithms are computational efficient, minimize covariate imbalance, and include randomization which enables robustness to misspecification. We provide worst case bounds on the expected mean squared error of the causal estimate and show that the proposed estimator is no worse than an implicit ridge regression, which are within a logarithmic factor of the best known results for offline experimental design. We conclude with a detailed simulation study showing favorable results relative to complete randomization as well as to offline methods for experimental design with time complexities exceeding our algorithm, which has a linear dependence on the number of observations, by polynomial factors.

Author Information

David Arbour (Adobe Research)
Drew Dimmery (University of Vienna)
Tung Mai (Adobe Research)
Anup Rao (Adobe Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors