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
- 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).
- Online KMM: The authors derive a dual optimization problem resembling a Support Vector Machine with quadratic loss, allowing for a simple SGD update rule.
- 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.
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).
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