Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data

Xuxing Chen, Abhishek Roy, Yifan Hu, Krishnakumar Balasubramanian

This academic paper, titled "Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data," introduces a new way to handle causal inference in real-time environments. By reframing a classic econometrics problem as a modern optimization challenge, the authors provide a path to efficient, "fully online" causal modeling.

TL;DR

The authors develop two new streaming algorithms for Instrumental Variable Regression (IVaR) that require neither matrix inversions nor mini-batches. These algorithms achieve fast convergence rates ($O(1/T)$) and bypass the traditional "forbidden regression" pitfalls, making them ideal for massive, high-velocity data streams.

What Problem Does This Paper Address?

In many fields—from healthcare to online advertising—we want to know the causal effect of a variable $X$ on an outcome $Y$. However, unobserved "confounders" often influence both, making simple regression biased. Instrumental Variable (IV) analysis solves this by using a third variable, $Z$ (the instrument), which affects $X$ but has no direct link to $Y$.

Traditionally, this is solved via Two-Stage Least Squares (2SLS):

  1. Regress $Z$ on $X$ to get a "clean" estimate of $X$.
  2. Regress that estimate on $Y$.

The problem? In a streaming data setting (where data arrives one point at a time), 2SLS is computationally expensive because it often requires storing past data or performing costly matrix inversions ($O(d^3)$ complexity). Furthermore, errors in the first stage propagate to the second—a phenomenon known as "forbidden regression." Modern "minimax" alternatives exist but are often too complex to run efficiently in a purely online fashion.

Methods

The authors view IVaR through the lens of conditional stochastic optimization. They propose two primary algorithms:

  1. TOSG-IVaR (Two-Sample One-stage): This assumes a "two-sample oracle"—essentially, for a given instrument $Z$, you can observe two independent realizations of $X$. This allows the algorithm to construct an unbiased gradient estimator. Remarkably, this method doesn't even need to model the relationship between $Z$ and $X$; it just updates the main parameters directly.
  2. OTSG-IVaR (One-Sample Two-stage): This is for the more common scenario where you only get one sample at a time. It uses a "two-time-scale" approach where it updates the nuisance parameters (the $Z \to X$ relationship) and the main causal parameters simultaneously.

What’s new: Unlike previous stochastic methods, these do not require "mini-batches" (groups of data points) to stabilize the gradient. They work point-by-point, making them "fully online."

Datasets

The paper relies on synthetic numerical experiments to validate the theory.

  • The authors simulate various scenarios with different dimensions ($d_x, d_z$), noise levels, and degrees of endogeneity (how correlated the error terms are).
  • They test both linear models and non-linear models (using a mapping $\phi$).
  • They compare their results against a recent baseline for online 2SLS (Della Vecchia and Basu, 2024).

Key Insights and Ideas

  • Direct Objective Solving: Most recent IV research tries to turn the problem into a "minimax" (game-theoretic) problem. This paper shows that solving the original conditional expectation objective directly is not only possible but more efficient.
  • The Power of Two Samples: The "two-sample" trick is an "aha moment" for efficiency. If you can get two $X$ samples for one $Z$, you bypass the need to ever explicitly estimate the "first stage" of the regression, completely avoiding the "forbidden regression" problem.
  • Stability via Modification: Naive online 2SLS often diverges early on because the underlying matrices aren't "well-behaved." The authors' OTSG-IVaR uses a specific update structure that ensures the matrix products remain positive semi-definite, leading to much smoother convergence.

Key Results

  • Convergence Speed:
    • The two-sample algorithm achieves a convergence rate of $O(\log T / T)$, which is near-optimal.
  • The one-sample algorithm achieves $O(1/T^{1-\iota})$, which is significantly faster than many existing biased estimators.
  • Computational Efficiency: The per-iteration complexity is as low as $O(d_x)$ for the two-sample case. For context, traditional 2SLS is $O(d^3)$. This makes the proposed methods orders of magnitude faster for high-dimensional data.
  • Robustness: In simulations, the proposed algorithms showed much lower variance than the O2SLS baseline, especially when the "endogeneity" (the bias they are trying to fix) was high.

Limitations and Future Work

  • Linearity Bias: While the algorithms can handle non-linearities, the most rigorous convergence proofs in the paper are for linear models. Extending the full "any-time" theory to deep neural networks is a suggested next step.
  • Oracle Availability: The TOSG-IVaR algorithm is mathematically elegant but requires a "two-sample oracle," which might not be available in all real-world streaming scenarios (though it is common in A/B testing or when the instrument $Z$ is discrete).
  • Statistical Inference: The paper focuses on point estimation (finding the right number). It does not yet provide a way to calculate confidence intervals or p-values in a streaming fashion, which the authors identify as a key area for future research.

Summary updated

Abstract

We develop and analyze algorithms for instrumental variable regression by viewing the problem as a conditional stochastic optimization problem. In the context of least-squares instrumental variable regression, our algorithms neither require matrix inversions nor mini-batches thereby providing a fully online approach for performing instrumental variable regression with streaming data. When the true model is linear, we derive rates of convergence in expectation, that are of order $\mathcal{O}(\log T/T)$ and $\mathcal{O}(1/T^{1-\epsilon})$ for any $\epsilon>0$, respectively under the availability of two-sample and one-sample oracles respectively. Importantly, under the availability of the two-sample oracle, the aforementioned rate is actually agnostic to the relationship between confounder and the instrumental variable demonstrating the flexibility of the proposed approach in alleviating the need for explicit model assumptions required in recent works based on reformulating the problem as min-max optimization problems. Experimental validation is provided to demonstrate the advantages of the proposed algorithms over classical approaches like the 2SLS method.
BibTeX
@inproceedings{chen2024stochastic,
  author = {Xuxing Chen and Abhishek Roy and Yifan Hu and Krishnakumar Balasubramanian},
  title = {{Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=2RS0fL7Eet},
}
Figure