Linear-Time Estimators for Propensity Scores

Deepak Agarwal, Lihong Li, Alexander J. SmolaAISTATS 2011 · OpenReview

Abstract: Propensity scoring is a critical tool for causal inference, yet traditional batch optimization methods scale poorly with large datasets. This paper introduces linear-time online algorithms for Logistic Regression, Kernel Mean Matching (KMM), and Maximum Entropy Mean Matching (MEMM). By leveraging stochastic gradient descent and MCMC-based estimation, these methods achieve scalability to millions of instances while maintaining the accuracy of batch counterparts.

Introduction

In many real-world scenarios—ranging from clinical trials to web analytics—randomized controlled trials are often impractical or impossible. In these cases, researchers must rely on observational data where the "treatment" and "control" groups may differ significantly in their underlying characteristics. This discrepancy, known as covariate shift, can lead to biased conclusions if not properly addressed.

To correct for this, researchers use propensity scoring to calculate a weight—the Radon-Nikodym derivative (RND)—for each instance in the treatment group, effectively reweighting the distribution to match the control group. However, traditional methods like Kernel Mean Matching (KMM) and Maximum Entropy Mean Matching (MEMM) involve complex optimization problems that typically scale at $O(n^2)$ or $O(n^3)$, rendering them unusable for modern "Big Data" applications.

A Unified Online Framework

This research provides a unified framework that converts these batch algorithms into linear-time ($O(n)$) online versions. The authors demonstrate that KMM and MEMM are fundamentally similar: both aim to match the means of distributions in a high-dimensional feature space, differing only in their regularization approach ($L_2$ norm for KMM vs. relative entropy for MEMM).

Online Implementations

  1. Logistic Regression (LR): Propensity scoring is recast as a binary classification problem. By predicting group membership (treatment vs. control), the density ratio can be estimated using standard Stochastic Gradient Descent (SGD).
  2. Online KMM: The authors derive a dual optimization problem resembling a Support Vector Machine with quadratic loss, allowing for a simple SGD update rule.
  3. Online MEMM: To handle the complex log-partition function inherent in MEMM, the paper proposes two solutions: a Metropolis-Hastings (MH) sampler for gradient estimation and a moving average approach (ADC) to approximate the denominator.

Experimental Evaluation

Convergence and Accuracy

The researchers first validated the online algorithms using the GISETTE benchmark dataset (handwritten digits). The goal was to ensure that the $O(n)$ online estimators converged to the same results as the computationally expensive batch versions.

Online vs. Batch convergence

As shown in Figure 1, the weights generated by the online algorithm align almost perfectly with the batch solutions, proving that computational efficiency does not require a sacrifice in accuracy.

Scalability and Bias Reduction

To test scalability, the algorithms were applied to a Yahoo! Front Page dataset containing 4 million user records and 5,000 features. In this experiment, a "naive" estimate of user visits was compared against the ground truth (a perfectly uniform sample).

Bias reduction on Yahoo! dataset

The results in Figure 5 highlight the effectiveness of the proposed methods. While the naive estimate suffered from a massive 24% bias due to non-random treatment assignment, all three online propensity scoring methods (LR, KMM, and MEMM variants) successfully eliminated this bias, bringing the estimates in line with the control group.

Conclusion

By moving from batch optimization to online stochastic updates, this work enables propensity scoring to scale to industrial-sized datasets. While Logistic Regression remains the most straightforward to implement, the unified framework for KMM and MEMM provides researchers with a robust toolkit for bias reduction in massive observational studies. Future work may further refine MCMC sampling techniques to improve the stability of entropic methods in highly non-linear feature spaces.

Summary updated

BibTeX
@inproceedings{agarwal2011linear,
  author = {Deepak Agarwal and Lihong Li and Alexander J. Smola},
  title = {{Linear-Time Estimators for Propensity Scores}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=txK3TL61Umg},
}
Figure