Inference in a class of optimization problems: confidence regions and finite sample bounds on errors in coverage probabilities

Joël L. Horowitz, Sokbae Lee, V Bentkus, D Bertsimas, A King, R Mazumder, R Blundell, A Duncan, C Meghir, C Bontemps, T Magnac, E Maurin, F Bugni, I Canay, X Shi, A Shaikh, X Chen, T Christensen, E Tamer, V Chernozhukov, D Chetverikov, K Kato, C Hansen, M Jansson, C Clopper, E Pearson, J Freyberger, C Gounaris, R Misener, C Floudas, K Ho, A Pakes, A Rosen, V Jeyakumar, H Wolkowicz, H Kaido, F Molinari, J Stoye, P Kline, M Tartari, G Lugosi, S Mendelson, C Manski, S Minsker, M Rai, V Spokoiny, M ZhilovaJournal of Business and Economic Statistics 2019

TL;DR

This paper introduces three novel methods for constructing confidence intervals for partially identified parameters that arise from optimization problems. Crucially, these methods provide finite-sample guarantees on the coverage probability of these intervals, addressing a key limitation of existing asymptotic approaches. This is particularly important in econometrics and related fields where sample sizes are often moderate.

What Problem Does This Paper Address?

In many econometric models, parameters of interest are not uniquely determined by the data but rather lie within a "partially identified" set. This often arises when dealing with optimization problems, such as those involving shape restrictions, discrete games, or grouped data. Existing inference methods for these parameters typically rely on asymptotic approximations, which can be unreliable in finite samples. The core challenge this paper tackles is to develop methods that provide rigorous, finite-sample guarantees on the accuracy of confidence intervals for these partially identified parameters, specifically by bounding the error in coverage probabilities.

Methods

The paper proposes three distinct methods for constructing confidence intervals and, more importantly, for deriving finite-sample lower bounds on their coverage probabilities.

  1. Method 1 (Normal Approximation): This method leverages multivariate normal approximations to the distribution of sample averages. It relies on a generalization of the Berry-Esseen theorem to bound the approximation error. This approach is relatively general but can lead to looser bounds, especially in moderate sample sizes, due to weak assumptions on the underlying data distribution.
  2. Method 2 (Sub-Gaussian Assumption): This method tightens the bounds by assuming that the components of the underlying random variables are sub-Gaussian. This assumption imposes stronger restrictions on the tail behavior of the distributions, leading to more precise finite-sample guarantees.
  3. Method 3 (Vector Sub-Gaussianity): This is the strongest assumption, requiring the entire vector of random variables to be sub-Gaussian in a vector sense. This leads to the tightest bounds among the three methods, but at the cost of a more restrictive assumption.

All methods aim to provide finite-sample lower bounds on the coverage probability of confidence intervals for the partially identified function $f(\psi)$. The paper also discusses how to estimate unknown population parameters that appear in these bounds.

Datasets

The paper uses data from the 1980 and 1990 U.S. censuses for an empirical application related to labor supply. It also mentions data from the 1960 and 1970 U.S. censuses for an additional empirical example on log weekly wages. No new datasets are introduced.

Key Insights and Ideas

  • Finite-Sample Guarantees are Crucial: The paper strongly emphasizes the need for finite-sample bounds on coverage probabilities, arguing that asymptotic approximations are insufficient and potentially misleading in many applied settings.
  • Hierarchy of Assumptions, Hierarchy of Bounds: The three proposed methods demonstrate a clear trade-off: stronger assumptions about the data distribution (sub-Gaussianity) lead to tighter, more informative finite-sample bounds.
  • Partially Identified Parameters are Common: The paper highlights that partially identified parameters are not niche problems but arise in various standard econometric applications, underscoring the practical relevance of their methods.
  • Optimization Problems as a Unifying Framework: The paper frames inference for partially identified parameters within the context of optimization problems, providing a unified approach for diverse applications.

Key Results

The paper provides theoretical results establishing finite-sample lower bounds on the coverage probabilities of confidence intervals for partially identified parameters. These bounds are shown to be tighter under stronger assumptions about the data distribution. Monte Carlo experiments and empirical examples illustrate the practical performance of the proposed methods, showing that they can yield informative confidence intervals and that the tighter bounds from Methods 2 and 3 are indeed more precise in practice. The empirical application to labor supply data demonstrates how these methods can be used to obtain meaningful bounds on policy-relevant parameters.

Limitations and Future Work

  • Dependence on Unknown Parameters: A significant limitation acknowledged is that the finite-sample bounds often depend on unknown population parameters, which are difficult to estimate. While the paper discusses estimation strategies, these estimated bounds are asymptotic and do not provide finite-sample validity themselves.
  • Computational Complexity: For some applications, especially those involving bilinear constraints, solving the optimization problems required for inference can be computationally intensive, necessitating the use of mixed integer programming.
  • Extension to Other Parameterizations: The paper focuses on cases where the population optimization problem involves first moments. Extending the formulation to cases where the optimization problem contains other population parameters is suggested as an open question.
  • Sub-Gaussian Assumption: While Method 2 and 3 offer tighter bounds, they rely on sub-Gaussian assumptions, which might not always hold in practice. The paper does conduct sensitivity analysis with a non-sub-Gaussian distribution, showing similar results.

Summary updated

Abstract

This paper describes a method for carrying out inference on partially identified parameters that are solutions to a class of optimization problems. The optimization problems arise in applications in which grouped data are used for estimation of a model's structural parameters. The parameters are characterized by restrictions that involve the unknown population means of observed random variables in addition to the structural parameters of interest. Inference consists of finding confidence intervals for the structural parameters. Our theory provides a finite-sample bound on the difference between the true and nominal probabilities with which a confidence interval contains the true but unknown value of a parameter. We contrast our method with an alternative inference method based on the median-of-means estimator of The results of Monte Carlo experiments and empirical examples illustrate the usefulness of our method.
BibTeX
@article{horowitz2019inference,
  author = {Joël L. Horowitz and Sokbae Lee and V Bentkus and D Bertsimas and A King and R Mazumder and R Blundell and A Duncan and C Meghir and C Bontemps and T Magnac and E Maurin and F Bugni and I Canay and X Shi and I Canay and A Shaikh and X Chen and T Christensen and E Tamer and V Chernozhukov and D Chetverikov and K Kato and V Chernozhukov and C Hansen and M Jansson and C Clopper and E Pearson and J Freyberger and J Horowitz and C Gounaris and R Misener and C Floudas and K Ho and A Pakes and K Ho and A Rosen and J Horowitz and J Horowitz and S Lee and V Jeyakumar and H Wolkowicz and H Kaido and F Molinari and J Stoye and P Kline and M Tartari and G Lugosi and S Mendelson and C Manski and S Minsker and M Rai and V Spokoiny and M Zhilova},
  title = {{Inference in a class of optimization problems: confidence regions and finite sample bounds on errors in coverage probabilities}},
  journal = {Journal of Business and Economic Statistics},
  year = {2019},
}
Figure