Linear-Time Estimators for Propensity Scores

We present linear-time estimators for three popular covariate shift correction and propensity scoring algorithms: logistic regression(LR), kernel mean matching(KMM), and maximum entropy mean matching(MEMM). This allows applications in situations where both treatment and control groups are large. We also show that the last two algorithms differ only in their choice of regularizer ($\ell_2$ of the Radon Nikodym derivative vs. maximum entropy). Experiments show that all methods scale well.