Improving massive experiments with threshold blocking
- 5 July 2016
- journal article
- research article
- Published by National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 113 (27) , 7369-7376
Abstract
Inferences from randomized experiments can be improved by blocking: assigning treatment in fixed proportions within groups of similar units. However, the use of the method is limited by the difficulty in deriving these groups. Current blocking methods are restricted to special cases or run in exponential time; are not sensitive to clustering of data points; and are often heuristic, providing an unsatisfactory solution in many common instances. We present an algorithm that implements a widely applicable class of blocking—threshold blocking—that solves these problems. Given a minimum required group size and a distance metric, we study the blocking problem of minimizing the maximum distance between any two units within the same group. We prove this is a nondeterministic polynomial-time hard problem and derive an approximation algorithm that yields a blocking where the maximum distance is guaranteed to be, at most, four times the optimal value. This algorithm runs in O ( n log n ) time with O ( n ) space complexity. This makes it, to our knowledge, the first blocking method with an ensured level of performance that works in massive experiments. Whereas many commonly used algorithms form pairs of units, our algorithm constructs the groups flexibly for any chosen minimum size. This facilitates complex experiments with several treatment arms and clustered data. A simulation study demonstrates the efficiency and efficacy of the algorithm; tens of millions of units can be blocked using a desktop computer in a few minutes.Keywords
Funding Information
- DOD | Office of Naval Research (N00014-15-1-2367)
This publication has 34 references indexed in Scilit:
- Adjusting Treatment Effect Estimates by Post-Stratification in Randomized ExperimentsJournal of the Royal Statistical Society Series B: Statistical Methodology, 2012
- Multivariate Continuous Blocking to Improve Political Science ExperimentsPolitical Analysis, 2012
- Multivariate Matching Methods That Are Monotonic Imbalance BoundingJournal of the American Statistical Association, 2011
- Simple, Efficient Estimators of Treatment Effects in Randomized Trials Using Generalized Linear Models to Leverage Baseline VariablesThe International Journal of Biostatistics, 2010
- Using Regression Models to Analyze Randomized Trials: Asymptotically Valid Hypothesis Tests Despite Incorrectly Specified ModelsBiometrics, 2009
- Comment: The Design and Analysis of Gold Standard Randomized ExperimentsJournal of the American Statistical Association, 2008
- Variance identification and efficiency analysis in randomized experiments under the matched‐pair designStatistics in Medicine, 2008
- Optimal multivariate matching before randomizationBiostatistics, 2004
- Optimal Matching for Observational StudiesJournal of the American Statistical Association, 1989
- A unified approach to approximation algorithms for bottleneck problemsJournal of the ACM, 1986