Minimax Optimal Nonparametric Estimation of Heterogeneous Treatment Effects

Zijun Gao, Yanjun Han

Abstract

A central goal of causal inference is to detect and estimate the treatment effects of a given treatment or intervention on an outcome variable of interest, where a member known as the heterogeneous treatment effect (HTE) is of growing popularity in recent practical applications such as personalized medicine. In this paper, we model the HTE as a smooth nonparametric difference between two less smooth baseline functions and determine the tight statistical limits of the nonparametric HTE estimation as a function of the covariate geometry. In particular, a two-stage nearest-neighbor-based estimator throwing away observations with poor matching quality is near minimax optimal. We also establish the tight dependence on the density ratio without the usual assumption that the covariate densities are bounded away from zero, where a key step is to employ a novel maximal inequality which could be of independent interest.

Introduction: The Challenge of HTE Estimation

In causal inference, the Heterogeneous Treatment Effect (HTE) refers to how a treatment affects different individuals based on their specific characteristics (covariates, $x$). Mathematically, it is defined as the difference between two response functions: $\tau(x) = \mu_1(x) - \mu_0(x)$, where $\mu_1$ is the response under treatment and $\mu_0$ is the response under control.

A fundamental challenge is that we never observe both outcomes for the same individual. Most standard nonparametric methods estimate $\mu_1$ and $\mu_0$ separately and subtract them. However, in many real-world scenarios, the treatment effect $\tau$ is much "simpler" or smoother than the complex baseline functions $\mu_1$ and $\mu_0$. This paper investigates whether $\tau$ can be estimated faster than the baselines themselves and how the "geometry" of the data—specifically the overlap between treatment and control groups—limits accuracy.

Methodology: Two-Stage Selective Matching

The authors analyze two scenarios: a Fixed Design, where covariates are on a grid with a specific shift, and a Random Design, where covariates are sampled from unknown densities. For the more realistic random design, they propose a novel two-stage nearest-neighbor estimator:

  1. Stage 1: For a specific query point $x_0$, the algorithm identifies the $m_1$ nearest neighbors in the control group.
  2. Stage 2: For each of those control neighbors, it finds the closest match in the treatment group. Crucially, the algorithm then discards the pairs with the worst matching distances, retaining only the $m_2$ best pairs.
  3. Estimation: The HTE is estimated by averaging the differences of these high-quality pairs.

This "selective matching" is the key innovation. By strategically throwing away data that is poorly matched, the estimator reduces bias more significantly than it increases variance, leading to superior performance compared to standard differencing methods.

Key Results and Theoretical Insights

The paper proves that this two-stage estimator is "near minimax optimal," meaning no other estimator can perform significantly better in the worst-case scenario. A critical finding is that the accuracy of HTE estimation is fundamentally tied to the $L_\infty$ distance of the covariate matching, rather than just the raw sample size.

Regime Shifts in Error Rates

The minimax rate exhibits three distinct behaviors depending on the noise level ($\sigma$) and the density ratio ($\kappa$). The authors identify a "matching bias" term that dominates when noise is low and a "variance" term that dominates when noise is high.

Error exponents for fixed and random designs across different baseline smoothness levels ($\beta_\mu$).

As shown in the figures above, the error exponent remains constant across a range of noise levels before shifting as the noise becomes the dominant factor. In simulations, the "Selected Matching" algorithm consistently showed lower Root Mean Squared Error (RMSE) than standard differencing-based estimators, particularly as dimensionality or group imbalance increased.

Mathematical Innovation and Future Work

To establish these rates without assuming covariate densities are "bounded away from zero," the authors developed a novel maximal inequality of the Hardy-Littlewood type. This allows the framework to handle regions where data is sparse.

Despite these advances, challenges remain. The current random design analysis focuses on cases where HTE smoothness $\beta_\tau \leq 1$. Extending this to higher-order smoothness ($\beta_\tau > 1$) is difficult due to the complexity of constructing high-order "pseudo-observations" in random space. Additionally, future work may focus on making the estimator "adaptive," allowing it to learn optimal parameters like the number of neighbors directly from the data.

Summary updated

Abstract

A central goal of causal inference is to detect and estimate the treatment effects of a given treatment or intervention on an outcome variable of interest, where a member known as the heterogeneous treatment effect (HTE) is of growing popularity in recent practical applications such as the personalized medicine. In this paper, we model the HTE as a smooth nonparametric difference between two less smooth baseline functions, and determine the tight statistical limits of the nonparametric HTE estimation as a function of the covariate geometry. In particular, a two-stage nearest-neighbor-based estimator throwing away observations with poor matching quality is near minimax optimal. We also establish the tight dependence on the density ratio without the usual assumption that the covariate densities are bounded away from zero, where a key step is to employ a novel maximal inequality which could be of independent interest.
BibTeX
@inproceedings{gao2020minimax,
  author = {Zijun Gao and Yanjun Han},
  title = {{Minimax Optimal Nonparametric Estimation of Heterogeneous Treatment Effects}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=_deQljmCnMU},
}
Figure