Exact computation of GMM estimators for instrumental variable quantile regression models

Le‐Yu Chen, Sokbae Lee

TL;DR

This paper provides a breakthrough for researchers using Instrumental Variable Quantile Regression (IVQR) by reformulating the estimation problem as a Mixed Integer Quadratic Programming (MIQP) problem. This approach allows for the exact computation of the global optimum for GMM estimators, bypassing the limitations of traditional heuristic methods or computationally expensive grid searches.

What Problem Does This Paper Address?

Quantile regression is a powerful tool for understanding how variables affect different parts of a distribution (e.g., the impact of education on the lowest vs. highest earners). However, when "endogeneity" is present—meaning a covariate is correlated with the error term—researchers must use Instrumental Variables (IV).

The standard approach for IV quantile regression involves the Generalized Method of Moments (GMM). The challenge is that the GMM objective function in these models is discontinuous and non-convex. Historically, this has forced researchers to choose between:

  1. Grid Search: Feasible only for one or two endogenous variables.
  2. Heuristics: Faster, but with no guarantee of finding the true global optimum.
  3. Smoothing: Easier to compute but requires choosing arbitrary tuning parameters that can bias results.

The authors aim to eliminate this "computational uncertainty" by providing a method that guarantees an exact solution.

Methods

The authors demonstrate that the IVQR GMM estimation problem can be equivalently formulated as a Mixed Integer Quadratic Programming (MIQP) problem.

The key technical innovation involves using "Big-M" constraints and binary indicator variables ($e_i$) to represent the discontinuous step functions inherent in quantile regression. By doing so, they transform a "nasty" non-convex optimization into a structured mathematical programming problem.

This allows researchers to leverage modern, highly optimized solvers like Gurobi or CPLEX. These solvers use branch-and-bound algorithms that not only find the global optimum but also provide a "gap" (a mathematical proof of how close the current best solution is to the theoretical optimum) if the user chooses to stop the computation early.

Datasets

The paper evaluates the algorithm using two primary sources:

  • Monte Carlo Simulations: A synthetic "location-scale" model with 100 observations. This setup was specifically designed with three endogenous covariates to test the algorithm's performance in higher-dimensional settings where traditional grid search would fail.
  • Fulton Fish Market Data: A classic empirical dataset from Graddy (1995) containing 111 observations of whiting transactions in New York. The goal was to estimate the price elasticity of demand for fish, using weather conditions at sea as instruments for price.

Key Insights and Ideas

  • Exactness Matters: The authors argue that heuristic uncertainty can lead to statistical behavior different from what theory predicts. By finding the exact GMM estimate, they align empirical practice with asymptotic theory.
  • Breaking the Dimensionality Barrier: While the popular "Inverse QR" method works well for a single endogenous variable, its complexity grows exponentially. The MIQP approach handles multiple endogenous variables much more gracefully.
  • The "Early Stopping" Benefit: Because MIQP solvers track lower bounds, researchers working with massive datasets can stop the solver early and still have a guaranteed bound on their approximation error—something heuristics cannot provide.

Key Results

  • Computational Efficiency: In simulations with three endogenous variables, the MIQP problems were solved relatively quickly on a standard desktop. Median computation times ranged from roughly 1.5 minutes ($\tau = 0.25$) to 5.5 minutes ($\tau = 0.5$).
  • Statistical Accuracy: The exact GMM estimator performed well in finite samples, showing low bias and root mean squared error (RMSE). The results closely matched the standard deviations predicted by asymptotic theory.
  • Empirical Findings: In the fish market application, the MIQP-based GMM estimates confirmed that demand elasticity is negative across the distribution. Interestingly, when adding "day-of-the-week" controls, the GMM estimates differed noticeably from previous "Inverse QR" results at the 0.25 quantile, suggesting that exact computation can indeed impact empirical conclusions.

Limitations and Future Work

  • Parametric Limitation: The current MIQP formulation is designed for parametric IVQR models. It is not directly applicable to semiparametric models (like partially linear models) that require a non-parametric first step.
  • Computational Scaling: While more robust than grid search, MIQP is still NP-hard. As the sample size ($n$) grows very large, the number of binary variables increases, which may eventually challenge even the best modern solvers.
  • Future Directions: The authors suggest extending this optimization framework to two-step semiparametric quantile IV estimators as a promising area for future research.

Summary updated

Abstract

Summary We show that the generalized method of moments (GMM) estimation problem in instrumental variable quantile regression (IVQR) models can be equivalently formulated as a mixed‐integer quadratic programming problem. This enables exact computation of the GMM estimators for the IVQR models. We illustrate the usefulness of our algorithm via Monte Carlo experiments and an application to demand for fish.
BibTeX
@article{chen2018exact,
  author = {Le‐Yu Chen and Sokbae Lee},
  title = {{Exact computation of GMM estimators for instrumental variable quantile regression models}},
  journal = {Journal of Applied Econometrics},
  year = {2018},
  doi = {10.1002/jae.2619},
}

Loading related content...

Figure