Abstract
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.
Introduction
Quantile regression is a powerful tool for understanding how variables affect different parts of a distribution, such as the impact of education on the lowest versus the 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 grid searches (feasible only for one or two endogenous variables), heuristics (faster but without global optimum guarantees), or smoothing (easier to compute but introduces bias via tuning parameters). This paper provides a breakthrough by reformulating the estimation problem as a Mixed Integer Quadratic Programming (MIQP) problem, allowing for the exact computation of the global optimum and eliminating computational uncertainty.
Methodology: The MIQP Formulation
The authors demonstrate that the IVQR GMM estimation problem can be equivalently formulated as an MIQP problem. The key technical innovation involves using "Big-M" constraints and binary indicator variables to represent the discontinuous step functions inherent in quantile regression. By doing so, they transform a 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.
Experimental Setup
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 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 Results and Insights
Computational Efficiency
In simulations with three endogenous variables, the MIQP problems were solved relatively quickly on a standard desktop. As shown in the performance table below, median computation times ranged from roughly 1.5 minutes (92 seconds at $\tau = 0.25$) to 5.5 minutes (333 seconds at $\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, detailed in the table below, closely matched the standard deviations predicted by asymptotic theory. By finding the exact GMM estimate, the authors align empirical practice with asymptotic theory, arguing that heuristic uncertainty can lead to statistical behavior different from what theory predicts.
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.
Conclusion and Future Work
While the MIQP approach handles multiple endogenous variables more gracefully than grid search and provides a guaranteed bound on approximation error, it has limitations. The current formulation is designed for parametric IVQR models and is not directly applicable to semiparametric models. Additionally, because MIQP is NP-hard, computational scaling may become a challenge as sample sizes grow very large. Future research may extend this optimization framework to two-step semiparametric quantile IV estimators.
Summary updated