Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
94,555 characters · 12 sections · 113 citation commands
Simple Inference on Functionals of Set-Identified Parameters Defined by Linear MomentsA previous version of this paper was circulated under the title “Inference on Functionals of Set-Identified Parameters Defined by Convex Moments." We are grateful to Ivan Canay, the associate editor, and two referees for excellent feedback that greatly improved the paper. We thank Victor Aguirregabiria, Bulat Gafarov, Christian Gourieroux, Jiaying Gu, Ismael Mourifie, Jeffrey Negrea, Adam Rosen, Brennan Thompson, Stanislav Volgushev and Yuanyuan Wan for helpful comments and discussion. We are also grateful to participants at the 7th Annual Doctoral Workshop in Applied Econometrics at the University of Toronto, as well as participants at the 2019 North America Summer Meeting of the Econometric Society at the University of Washington. This research was supported by the Social Sciences and Humanities Research Council of Canada. All errors are our own.
Keywords: Linear Programming, Partial Identification, Stochastic Programming, Subvector Inference
\thispagestyle{empty}
There is now a sizeable literature on inference procedures for partially identified models. However, many existing procedures require the researcher to perform a hypothesis test at every point in the parameter space in order to construct a confidence set, and so quickly become computationally prohibitive. Simple inference procedures familiar to applied researchers from the literature on point-identified models are also not easily transportable to the partial-identification setting due to the well-known uniformity issues that arise in these models.
This paper proposes a different approach to obtain uniformly valid inference for linear functionals or scalar subvectors of a partially identified parameter vector in models with linear moment inequalities. Instead of explicitly inverting a hypothesis test to construct a confidence set, the proposed procedure solves a certain set of bootstrap linear programs. We show that by perturbing the problem with a small amount of random noise, a simple nonparametric bootstrap procedure can become a uniformly valid method of confidence set construction. The unconventional approach to the problem has a number of interesting consequences. The benefits are that it is fast, conceptually simple, and valid under weak assumptions. The drawback is that the resulting confidence set has a coverage probability tending to 1 over the identified set, although it has exact coverage on an outer set under some additional assumptions. In this sense, the approach modifies the coverage objective in exchange for some practical benefits.
Our main theoretical framework builds on results from the Operations Research literature (e.g. shapiro1990concepts, shapiro1991asymptotic) to approximate the distribution of the value functions of linear programs with data-dependent constraints using a functional delta method. Bounding a linear functional over an identified set defined by linear moment inequalities amounts to solving two linear optimization problems: one maximization problem for the upper bound, and one minimization problem for the lower bound. The endpoints of the identified set for a linear functional of a partially identified parameter can thus be viewed as value functions of two linear programs. Under some conditions, the value functions of linear programs are known to be Hadamard differentiable with respect to the underlying data generating process. However, this form of differentiability only obtains under restrictive assumptions, and is not sufficient to construct uniformly valid confidence sets for a partially identified linear functional or scalar subvector.\footnote{This result is reminiscent of kasy2019uniformity, who emphasizes that failures of uniformity often result as failures of uniform versions of the delta method.}
In this paper we demonstrate the conditions under which the value functions of a linear program are uniformly Hadamard differentiable with respect to the underlying data generating process. The conditions required for this level of differentiability include nonempty interior of the feasible region/identified set, and the existence and uniqueness of both optimal solutions and Lagrange multipliers in the underlying linear programs.
Unfortunately, the conditions required for uniform Hadamard differentiability are high-level and difficult to verify. However, spingarn1979generic use Sard's Theorem from differential topology to demonstrate that a generic linear program has both a unique solution and unique Lagrange multipliers. In particular, by introducing small random perturbations to the constraints and objective function of a linear program we can ensure a unique solution and unique Lagrange multipliers with probability 1. Certain choices of the perturbation distribution also ensure that the perturbed feasible region has a nonempty interior. Thus, adding randomly drawn perturbations to a stochastic linear program ensures the high-level conditions for uniform Hadamard differentiability hold with probability 1. We then show that this idea can be combined with a functional delta method to construct a uniformly valid confidence set for the true unknown value of the functional or subvector of interest which has exact coverage over a slight expansion of the identified set. The randomness of the perturbation is essential for these theoretical results, which do not hold for non-stochastic perturbations.
The main tuning parameter in our method determines the support of the perturbations. The theoretical results suggest that even perturbations with extremely small support can correct any uniform Hadamard differentiability failure and allow our approach to obtain the correct asymptotic coverage. However, the current theory is silent on how to set the support of the perturbations to obtain good coverage properties in finite samples. We explore the finite sample impact of the support of the perturbations in simulations. We also compare the method to the methods of fang2021inference and gafarov2021inference in a variety of simulation examples, and show that the procedure has competitive coverage properties.
A survey of inference methods for partially identified models is provided in canay2017practical. The literature has focused on the construction of uniformly valid confidence sets, motivated by the fact that test statistics in moment inequality models have asymptotic distributions that are discontinuous in the moment slackness. In these cases, confidence sets that are only valid pointwise can be highly misleading.
For subvector inference, andrews2009validity and andrews2010inference proposed to project confidence sets constructed for the entire parameter vector. While these projection procedures are uniformly valid, they can be highly conservative. Both romano2008inference and bugni2017inference consider inverting profiled test statistics in order to construct confidence sets for subvectors, and kaido2019confidence provide a calibrated projection inference method for functionals of a partially identified parameter. The greatest advantage of our proposed procedure relative to these procedures is in terms of computational tractability, although we restrict attention to linear moment inequalities. Several recent working papers also study inference on functionals or subvectors. belloni2018subvector consider the problem of subvector inference in models with many moment inequalities. andrews2019conditional consider projection inference for conditional moment inequalities that are linear in nuisance parameters and that also have non-stochastic gradients conditional on some variable. Our approach does not require this special structure, although we require linear moment conditions. gafarov2021inference shows how to construct uniformly valid confidence sets in an optimization framework, although relies on a crucial high-level constraint qualification which is not required in our current approach. Finally, fang2021inference consider the related problem of testing for the existence of a solution to a linear system with known coefficients. In contrast, our proposed procedure is applicable with both fixed and data-dependent coefficients. However, it is important to keep in mind that our proposed approach “moves the goalpost” in the sense that exact coverage is obtained only on an outer set, and the coverage probability is $1$ over the identified set. This a consequence of our unconventional approach based on a global perturbation.
In a relevant paper, fang2018inference study the problem of performing inference using a functional delta method for Hadamard differentiable and Hadamard directionally differentiable functionals. They show that full differentiability of the functional of interest is both necessary and sufficient for consistency of the bootstrap when the underlying estimator is asymptotically Gaussian. In the current paper we demonstrate the conditions under which the value functions of a linear program are fully (and uniformly) Hadamard differentiable and show that a perturbation procedure ensures these conditions are satisfied.\footnote{shapiro1991asymptotic demonstrates Hadamard directional differentiability of the value function under various assumptions, and also comments on conditions that ensure (full) Hadamard differentiability. } Thus, our theoretical results and our proposed bootstrap procedure do not contradict the results of fang2018inference, and allow us to avoid explicitly estimating the Hadamard derivative. Pointwise inference using a functional delta method has also been previously considered in various contexts by kasy2016partial, masten2017inference, christensen2019counterfactual, and gunsilius2020path.
The current paper also has close connections to the literature on support function estimators, including beresteanu2008asymptotic, bontemps2012set, kaido2014asymptotically, and chandrasekhar2019best, among others. In particular, kaido2014asymptotically propose a pointwise valid procedure that can be used to construct confidence intervals for subvectors in models with convex moment conditions. Their results require both a constraint qualification and uniqueness of the optimal solutions; the “uniform versions” of these assumptions are very strong and high-level, which is a main motivation for the current paper. Their inference procedure uses a multiplier bootstrap applied to the score of the support function; in contrast, our approach directly bootstraps the support function after introducing a global perturbation.
Finally, the current paper is motivated by applications in partial identification with linear moment conditions. There have been a number of applications motivated by the influential papers of pakes2011imoment,pakes2015moment that involve linear moment inequalities. Other articles relying on linear moment conditions and/or linear programming are now legion in the literature on partial identification and include honore2006bounds, honore2006competing, manski2007partial, laffers2013note, freyberger2015identification, demuynck2015bounding, mogstad2018using, russell2019sharp, tebaldi2019nonparametric, torgovitsky2019nonparametric, and torgovitsky2019partial, among others. The procedure outlined in this paper is applicable to many of these works. Recently our proposed procedure has been used by gu2022partial to construct confidence sets for counterfactual probabilities in a nonseparable binary response model with endogenous regressors, an example with thousands of parameters and constraints.\footnote{In the current paper the number of constraints is assumed to be fixed throughout, and we do not address the case where the number of constraints can grow with the sample size. However, our asymptotic approximations can still be useful in many cases when the number of constraints is large relative to the sample size; for instance, when the constraints depend on the data only through a low dimensional estimated parameter, as is the case in gu2022partial. }
The remainder of the paper proceeds as follows. Section (ref) presents a simplified overview of the method. Section (ref) develops the methodology in detail. Section (ref) introduces the Monte Carlo exercises performed using our proposed procedure, and Section (ref) concludes. All appendices are included in the supplementary material. The proofs of all of the main results are provided in Appendix A. A modified version of our proposed procedure that always produces a nonempty confidence interval is presented in Appendix B. Two illustrative examples are presented in Appendix C, and details on our simulation designs are presented in Appendix D, along with some additional robustness exercises.\\
Notation: The product probability measure is denoted by $\text{Pr}_{P}$. To keep notation clean, we use $\E_{P}[ \,\cdot\,]$ to denote either the expectation with respect to $P$, or the expectation with respect to the product measure. We let $\E_{n}$ denote the expectation with respect to the empirical distribution $\mathbb{P}_{n}$, and we let $\E_{n}^{b}$ denote the expectation with respect to the bootstrap distribution $\mathbb{P}_{n}^{b}$. Issues of measurability are avoided in the main text, but are addressed in the appendix. We use $P_{n} \rsq P$ to denote weak convergence of a sequence of probability measures $\{P_{n}\}_{n=1}^\infty$ to a limiting probability measure $P$.
The goal of this section is to provide the intuition behind our approach and to provide a roadmap for the remainder of the paper. Our main motivation is to construct a uniformly valid confidence set for the scalar quantity $\psi_{0}:=\E_{P}[\psi(W,\theta_{0})]$, where $W \in \mathcal{W}\subset \mathbb{R}^{d_{w}}$ denotes the relevant finite-dimensional vector of random variables in the model, $\theta_{0} \in \Theta \subset \mathbb{R}^{d_{\theta}}$ is the true but partially identified parameter vector, and $\psi(w,\theta)$ is a function that is linear in $\theta$. We assume throughout that $\Theta$ is a compact polyhedron defined by $k_{\theta}$ linear constraints. We then consider a setting where the identified set $\Theta_{I}(P)$ is defined by $k_{m}$ linear moment inequalities:
where $k:= k_{m} + k_{\theta}$. Note that this formulation does not rule out moment equalities, since every moment equality can be written as a combination of two moment inequalities. Under our assumptions presented in the next section, the identified set $\Psi_{I}(P)$ for $\psi_{0}$ is an interval $[\Psi_{I}^{\ell b}(P),\Psi_{I}^{ub}(P)]$ with endpoints determined by the following linear programming problems:
We are then interested in constructing a random set $C_{n}^{\psi}(1-\alpha)$ that satisfies:
where $\mathcal{P}$ is some large class of DGPs. We now present some motivating examples which are revisited in our simulation exercises.
Our method of inference for $\psi_{0}$ relies on an approximation to the distribution of the sample analog value functions $\Psi_{I}^{\ell b}(\P_{n})$ and $\Psi_{I}^{ub}(\P_{n})$. Focusing on the lower bound value function $\Psi_{I}^{\ell b}(\P_{n})$, note that:
for any sequence $P_{n}$, where $t_{n}:= n^{-1/2}$ and $h_{n}:= t_{n}^{-1} (\P_{n} - P_{n})$. Under some conditions, if $P_{n}$ converges (in a sense to be made precise) to some $P$, then (ref) tends to a limit called a uniform Hadamard derivative.\footnote{In the proofs, we show that it is without loss of generality to assume $P_{n}$ converges weakly to some $P$, which we denote by $P_{n}\rsq P$. In particular, under our assumptions our class of DGPs $\mathcal{P}$ is tight and closed in the weak* topology. Combined with Prokhorov's Theorem (e.g. billingsley1968convergence Theorem 6.1), every sequence $\{P_{n}\}_{n=1}^{\infty}$ in $\mathcal{P}$ admits a weakly convergent subsequence converging to some $P \in \mathcal{P}$.} This is demonstrated in Theorem (ref) in the next section. Functions that are differentiable in this sense are said to be uniformly Hadamard differentiable (UHD), and are amenable to an application of the delta method. We show that the value function $\Psi_{I}^{\ell b}(\,\cdot\,)$ is UHD at $P$ if:
Condition (ii) implies that there cannot be more than $d_{\theta}$ binding constraints at any solution to the linear programs (ref) and (ref), and condition (iii) rules out cases when the solutions to (ref) and (ref) occur at a “flat face” of the identified set.\footnote{Similar conditions are encountered in hirano2012impossibility and kaido2014asymptotically.} All three conditions are high-level.
To make progress, we turn to the literature on genericity in linear programming problems. Intuitively, a generic property of a problem is a property that holds in “almost all” instances of the problem. In particular, consider the following linear programs, which are revised versions of (ref):
Here $\xi :=(\nu,\varepsilon) \in \mathbb{R}^{d_{\theta}}\times \mathbb{R}_{+}^{k}$ is a draw from some known distribution $P_{\xi}$. We call these random draws perturbations and call the linear programs (ref) and (ref) perturbed linear programs. In practice the perturbation $\xi$ can be drawn from any continuous distribution with convex support, although it must be independent of $W$. It is possible to show:
$P_{\xi}-$a.s, where $\Psi_{I,-}^{u b}(P,\xi)$ and $\Psi_{I,+}^{u b}(P,\xi)$ are the analogous upper bound perturbed value functions. That is, the perturbed programs can be used to outer-bound the identified set for $\psi_{0}$.
The results of spingarn1979generic imply that conditions (i), (ii) and (iii) hold for the perturbed linear programs $P_{\xi}-$a.s. at any $P \in \mathcal{P}$. This property implies that the value functions in the perturbed linear programs are UHD $P_{\xi}-$a.s.\footnote{The perturbation idea here appears to be similar the use of data-jittering in chandrasekhar2019best. bontemps2012set also study the generic differentiability of support functions.} Thus, for $P_{\xi}-$almost all perturbations $\xi$, we can use the functional delta method to approximate the distributions of the value functions $\Psi_{I,-}^{\ell b}(P,\xi)$, $\Psi_{I,+}^{\ell b}(P,\xi)$, $\Psi_{I,-}^{u b}(P,\xi)$, and $\Psi_{I,+}^{u b}(P,\xi)$, and can then use the inequality from (ref) to construct a uniformly valid confidence set for $\psi_{0}$. This idea is fully developed in Section (ref). Intuitively, the perturbation eliminates all over-identified solutions of the linear program, and ensures that a single basic solution of the perturbed linear program is picked out asymptotically.\footnote{We thank an anonymous referee for pointing out this perspective.} Inference is then done around this picked-out solution. The perturbation is designed in a way to ensure that using this solution for inference introduces at most a conservative distortion. We then show that a simple nonparametric bootstrap can be used to approximate the asymptotic distribution of the perturbed value functions. In the end, a confidence set $C_{n}^{\psi}(1-\alpha,\xi)$ for $\psi_{0}$ can be constructed as follows:
To understand the coverage properties of this confidence set, define:
where:
Intuitively, the set $\Psi_{I}(P,\xi)$ represents a relaxed version of the identified set $\Psi_{I}(P)$, where the relaxation is determined by the perturbation $\xi$. The set $\overline{\Psi}_{I}(P)$ then contains all possible sets $\Psi_{I}(P,\xi)$, and so represents a “maximally relaxed” version of the identified set for a given value of $\bar{\varepsilon}$. Under weak assumptions, Theorem (ref) states that the confidence set $C_{n}^{\psi}(1-\alpha,\xi)$ satisfies:
That is, our confidence set contains the true value $\psi_{0}$ with probability $1$ asymptotically over repeated draws from both the sampling distribution $\text{Pr}_{P}$ and the perturbation distribution $P_{\xi}$. Any tests based on inverting our confidence set will also have zero power for local alternatives drifting to a point in the identified set. However, under some additional assumptions, Theorem (ref) also shows that:
where $\widetilde{\Psi}_{\alpha}(P)$ is a set satisfying $\Psi_{I}(P) \subset \widetilde{\Psi}_{\alpha}(P) \subset \overline{\Psi}_{I}(P)$. In other words, the confidence set $C_{n}^{\psi}(1-\alpha,\xi)$ obtains exact uniform coverage over a set $\widetilde{\Psi}_{\alpha}(P)$ that lies between the identified set $\Psi_{I}(P)$ and the maximally relaxed version of the identified set from (ref). When the support of the perturbations is small, the identified set $\Psi_{I}(P)$ and the maximally relaxed set $\overline{\Psi}_{I}(P)$ are typically very close, implying that the confidence set $C_{n}^{\psi}(1-\alpha,\xi)$ has exact uniform coverage on a slight expansion of the identified set. In this sense the proposed approach moves the objective, obtaining exact coverage on an outer set in exchange for an inference procedure that is computationally and conceptually simple.
The randomness of the perturbation is essential for this theoretical result, which does not hold for non-stochastic perturbations. In particular, there can exist (at most) a $P_{\xi}-$null set $\Xi_{0} \subset \Xi$ for which the uniform coverage probability is below the nominal level. If a non-stochastic perturbation is used, and if this perturbation belongs to $\Xi_{0}$, then the coverage guarantee will fail. A randomly drawn perturbation lies outside of this problematic null set $P_{\xi}-$a.s., in which case our coverage results are guaranteed.
Our theoretical results require a positive and constant $\bar{\varepsilon}$ to construct the support of the perturbations $\Xi$ in Step 1 of the procedure above. The value of $\bar{\varepsilon}$ represents the upper bound on both the objective function and constraint perturbations. The uniform asymptotic validity of the proposed confidence set is not affected as long as $\bar{\varepsilon} > 0$, so in theory it may be chosen as small as desired. The fact that $\bar{\varepsilon}$ is not scale invariant also does not affect the asymptotic theory in the paper. However, the current theoretical results do not hold if $\bar{\varepsilon} = 0$ or if $\bar{\varepsilon} \downarrow 0$ as $n \to \infty$. In addition, the asymptotic theory is silent on the impact of $\bar{\varepsilon}$ in finite samples. We discuss some of the finite sample tradeoffs involved in picking $\bar{\varepsilon}$ in Section (ref) in a simulation example.
In the end, the computational advantage of the proposed procedure arises from the fact that we do not construct our confidence set by inverting hypothesis tests. Instead, our proposed procedure solves $4(B+1)$ linear programs, each of which can be solved in a fraction of a second even with thousands of parameters and constraints. The result is a confidence set $C_{n}^{\psi}(1-\alpha,\xi)$ that is valid under weak assumptions, can be computed in seconds, and that has exact uniform asymptotic coverage on a small expansion of the identified set.
In this section we introduce the assumptions required to prove the uniform asymptotic validity of our confidence set.
Note when $\mathcal{W}$ is finite or countable, we can equip $\mathcal{W}$ with the discrete topology, in which case every function on $\mathcal{W}$ becomes both continuous and Borel measurable, and the continuity requirement in Assumption (ref) is vacuous. In the next assumption, we take $\Theta \subset \mathbb{R}^{d_{\theta}}$ and $\mathcal{P} \subset \mathscr{P}$ with $\mathscr{P}$ the collection of all probability measures on $\mathcal{W}$.
The compactness of $\Theta$ in part (i) of Assumption (ref) is standard, and ensures that the identified set for our functional of interest is a closed interval. Part (i) also clarifies that all parameter space constraints are written as moment functions $m_{k_{m}+1}(w,\theta),\ldots,m_{k}(w,\theta)$, where $k:=k_{m}+k_{\theta}$, in order to simplify notation throughout. Part (ii) restricts $\mathcal{P}$ to be a class of DGPs satisfying a set of moment inequalities. Note that we do not rule out moment equalities.\footnote{In particular, $x=0$ can be written as $x \leq 0$ and $-x \leq 0$.} Part (iv) requires the existence of a bounded envelope function, and part (v) is a standard uniform moment condition.\footnote{The boundedness of the envelope $F$ is slightly stronger than the usual moment condition found in the literature, which typically has the form: $\sup_{P \in \mathcal{P}} \E_{P}|F(W)|^{2+a} < \infty$ for some $a>0$. However, in practice the existence of a bounded measurable envelope function is more easily verifiable.} Assumptions similar to part (vi) are also commonly found in the existing literature; for instance, bugni2017inference A.3(c) (coupled with compactness of $\Theta$) or kaido2019constraint Assumption E.4(ii).
In this section we provide conditions under which the value function of a linear program is UHD. A formal definition of a UHD functional is presented in Definition A.6 in the Supplementary Material. Let $I(\theta,P)$ be the set indexing the binding moment inequalities at $\theta$ for some probability measure $P \in \mathcal{P}$:
Furthermore, let $\theta_{\ell b}^{*}(P)$ and $\theta_{u b}^{*}(P)$ be any optimal solutions to the problems (ref) and (ref), and let $G(\theta,P)$ be the matrix formed by vertically stacking the row vectors $\{\nabla_{\theta} \E_{P}[m_{j}(W,\theta)] \}_{j \in I(\theta,P)}$.
Our first result shows that if $P \in \mathcal{P}$ satisfies conditions (NE), (CQ) and (US), then the value functions are UHD at $P$. The tangent cone $\mathcal{T}_{P}(\mathcal{F})$ in the following result is defined in Appendix A.2 of the Supplementary Material.
Theorem (ref) represents one of the key results in this paper, and shows that under our assumptions and conditions (NE), (CQ) and (US), the value functions of a linear program are UHD. Condition (NE) is required to ensure that the uniform Hadamard derivative is well-defined. This may not be the case if the identified set at $P$ consists of a single point, since in such cases it is possible to construct a sequence $P_{n} \in \mathscr{P}$ converging to $P \in \mathcal{P}$ such that $\Theta_{I}(P_{n})$ is empty for all $n$. However, condition (NE) rules out both moment equalities and point identification. In this sense, condition (NE) is quite restrictive. In the next subsection we show how the condition can be relaxed to allow for both moment equalities and point identification. Condition (CQ) implies the linear independence constraint qualification (LICQ) used in the study of optimality conditions for convex programs.\footnote{wachsmuth2013licq shows that the LICQ is the weakest constraint qualification under which the Lagrange multipliers are guaranteed to be unique. Constraint qualifications in various forms have appeared throughout the recent history of partial identification (e.g. beresteanu2008asymptotic, pakes2011imoment kaido2014asymptotically, freyberger2015identification, kaido2019confidence, gafarov2018delta, and gafarov2021inference). We refer to the recent paper of kaido2019constraint for a full comparison of the constraint qualifications used in the partial identification literature.} There are some cases where it may be easy to directly verify that condition (CQ) is satisfied; for example, when the gradients of the moment functions and objective functions are known. However, with data-dependent gradients condition (CQ) is a high-level condition. Condition (US) then imposes uniqueness of optimal solutions separately. If the problems (ref) and (ref) admit multiple solutions, the limiting optimal solutions (i.e. over a sequence $P_{n} \to P$ in $\mathcal{P}$) can differ from the optimal solutions at the limit (i.e. at $P \in \mathcal{P}$).\footnote{This is related to the Theorem of the Maximum, which guarantees only that the solution correspondence is upper hemicontinuous, but not lower hemicontinuous (and thus, not continuous).} In this case it is possible to show that the value functions $\Psi_{I}^{\ell b}(\cdot)$ and $\Psi_{I}^{u b}(\cdot)$ may not even be Hadamard differentiable, let alone UHD. A similar intuition applies to the Lagrange multipliers. Examples showing the failure of Hadamard differentiability when either (US) or (CQ) fails to hold are presented in Appendix C.
Failures of conditions (CQ) and (US) are illustrated in Figure (ref). Figure (ref)(a) shows that condition (CQ) fails when the number of binding constraints exceeds the dimension of the parameter space, in which case it is impossible for the gradients of the binding constraints to be linearly independent. Figure (ref)(b) also shows that condition (US) fails when the gradient of the objective function is parallel to the gradient of one of the constraints, so that the optimum is obtained along a “flat face” of the feasible region.
Unfortunately, all three conditions (NE), (CQ) and (US) are high-level, although in the next section we show that introducing a simple random perturbation ensures that conditions (NE), (CQ) and (US) are satisfied almost surely.
Let $\xi =(\nu,\varepsilon)\in \mathbb{R}^{d_{\theta}}\times \mathbb{R}_{+}^{k}$ be a random vector. We impose the following assumption on the distribution and support of $\xi$.
In practice the distribution $P_{\xi}$ is chosen by the researcher, and any distribution can be chosen so long as it satisfies Assumption (ref). For example, in the simulations in Section (ref), the perturbation $\xi$ is drawn uniformly from $\Xi:=[0, \bar{\varepsilon}]^{d_{\theta}+k}$ with $\bar{\varepsilon}=10^{-3}$. Importantly, the results ahead are not valid for $\bar{\varepsilon}=0$ or $\bar{\varepsilon}\downarrow 0$ as $n\to \infty$. The results also do not hold if $P_{\xi}$ is not absolutely continuous with respect to the Lebesgue measure; this rules out, for instance, non-stochastic perturbations.
Recall the linear programs (ref) and (ref) from Section (ref). These programs represent “perturbed” versions of the linear program (ref). Since $\varepsilon \in \mathbb{R}_{+}^{k}$, the perturbations to the moment inequalities enlarge the feasible region relative to the linear program (ref). From the inequality in (ref), the value functions of the perturbed linear programs can then be used to construct outer bounds for the value functions for the unperturbed programs.
Let us define a perturbed version of the identified set:
Furthermore, let $I(\theta,P,\xi)$ denote the set indexing the binding moment inequalities at $\theta$ for $P \in \mathcal{P}$ and $\xi \in \mathbb{R}^{d_{\theta}}\times \mathbb{R}_{+}^{k}$:
Now let $\theta_{\ell b,-}^{*}$ and $\theta_{\ell b,+}^{*}$ be any optimal solutions to the problems (ref) and (ref), and let $\theta_{u b,-}^{*}$ and $\theta_{u b,+}^{*}$ be any optimal solutions to the analogous upper bound problems. Let $G(\theta,P,\xi)$ be the matrix formed by vertically stacking the row vectors $\{\nabla_{\theta} \E_{P}[m_{j}(W,\theta)] \}_{j \in I(\theta,P,\xi)}$. We now present a definition of the “perturbed versions” of the regularity conditions from Definition (ref).
Definition (ref) is the analog of Definition (ref), except now all quantities depend on the random perturbation $\xi$. The following result is instrumental to our approach.
The proof of this Lemma uses a result from spingarn1979generic, which is in turn derived using Sard's Theorem from differential topology. Lemma (ref) implies that, for any $P \in \mathcal{P}$ satisfying Assumptions (ref) and (ref), conditions (NE), (CQ) and (US) can be made to hold a.s. \kern-0.25em by randomly perturbing the optimization problems in (ref) and (ref). Figure (ref) illustrates how the failure of conditions (CQ) and (US) from Figure (ref) can be restored after perturbing the objective function and constraints. We also work through two specific examples in Appendix C, showing how uniform Hadamard differentiability can be restored by perturbations.
Using Lemma (ref), we obtain a useful corollary to Theorem (ref).
Corollary (ref) gives us a way to ensure the value function of a linear program is UHD $P_{\xi}-$a.s., and is used to construct confidence sets in the next section. Although Corollary (ref) is stated for $\Psi_{I,-}^{\ell b}(\,\cdot\,,\xi)$ and $\Psi_{I,+}^{\ell b}(\,\cdot\,,\xi)$, the same result holds for the upper bound perturbed value functions. Again, since the result might fail to hold for $\xi$ in some $P_{\xi}-$null set $\Xi_{0} \subset \Xi$, stochastic perturbations are essential.
We now construct a confidence set for the true but partially identified value of a functional or scalar subvector of interest using the differentiability results of the previous sections. Our proposed procedure uses the nonparametric bootstrap, which we formalize as an assumption.
Our next result uses a functional delta method to approximate the distribution of the value functions of our perturbed linear programs. We state the result only for the perturbed program (ref), although it also holds without substantial modification for the perturbed program (ref), as well as for the analogous upper bound perturbed programs.
Lemma (ref) shows that the nonparametric bootstrap can be used to approximate the limiting distributions of the value functions of our perturbed linear programs, and immediately suggests a method of inference. Recall the “maximally relaxed” version of the identified set $\overline{\Psi}_{I}(P)$ from (ref). The following is our main theoretical result.
The result shows that, after introducing certain random perturbations, a simple nonparametric bootstrap procedure can be used to construct a uniformly valid confidence set for a partially identified functional. The first part of Theorem (ref) shows that the proposed confidence set is uniformly asymptotically valid, but very conservative. Intuitively, this comes from the use of a global and non-vanishing perturbation, which implies that our confidence set will never collapse to the identified set, but instead will collapse to an outer set. Any tests based on inverting our confidence set will also have zero power for local alternatives drifting to a point in the identified set. However, the power will generally be non-zero for points outside the identified set.\footnote{ In particular, this is also true for points outside $\Psi_{I}(P)$ but inside $\Psi_{I}(P,\xi)$ for a fixed perturbation draw $\xi$. To see the intuition, note that a fixed alternative $\psi^\dagger$ may lie outside $\Psi_{I}(P)$ and $\Psi_{I}(P,\xi_{1})$ but inside $\Psi_{I}(P,\xi_{2})$ for two different draws $\xi_{1}$ and $\xi_{2}$ from $P_{\xi}$. Studying the coverage of $\psi^\dagger$ by our confidence set requires taking repeated draws from $P_{\xi}$; intuitively, if $\psi^\dagger$ is outside $\Psi_{I}(P,\xi)$ for sufficiently many draws $\xi$ from $P_{\xi}$, our procedure will not have zero power at $\psi^\dagger$. } The second part of Theorem (ref) shows that the confidence set obtains exact uniform asymptotic coverage over a set $\widetilde{\Psi}_{\alpha}(P)$ that lies between the identified set $\Psi_{I}(P)$ and the maximally perturbed identified set $\overline{\Psi}_{I}(P)$. When $\overline{\Psi}_{I}(P)$ is close to $\Psi_{I}(P)$, this implies that the confidence set obtains exact coverage over a small expansion of the identified set. In this respect, the approach modifies the coverage objective slightly in exchange for computational tractability. While the choice of $\alpha$ does not influence the coverage result in (ref), it will influence the set $\widetilde{\Psi}_{\alpha}(P)$ satisfying (ref). The proof of the result proceeds by explicitly constructing a set $\widetilde{\Psi}_{\alpha}(P)$ satisfying the conditions stated in the Theorem. The proof shows that for any $\alpha_{1}<\alpha_{2}$ we have $\widetilde{\Psi}_{\alpha_{1}}(P) \subset\widetilde{\Psi}_{\alpha_{2}}(P)$; in other words, for an increasing sequence of $\alpha$'s, the outer sets that are covered exactly by our confidence set are also increasing.
In the end, the approach moves the goalpost, trading off exact coverage on an outer set for a confidence set that is valid under weak assumptions, and is computationally easy to construct. The description of our final recommended procedure can be found in Section (ref).
The main tuning parameter in our method is $\bar{\varepsilon}$, which governs the upper bound on the support of the perturbations for both the objective function and constraints. Theorem (ref) shows that, at least asymptotically, any choice of $\bar{\varepsilon}>0$ is sufficient to guarantee the coverage results in (ref) and (ref). This seems to suggests that $\bar{\varepsilon}>0$ should be chosen as small as possible, since this will produce the shortest confidence interval using our procedure. In that case, (ref) in Theorem (ref) also implies our confidence set has exact coverage on an outer set $\widetilde{\Psi}_{\alpha}(P)$ that will be very close to the identified set $\Psi_{I}(P)$. However, this reasoning can be misleading, since the choice of $\bar{\varepsilon}>0$ can have important impacts on the coverage of our confidence set in finite samples. In this subsection we explore the tradeoff between power and coverage associated with various choices of $\bar{\varepsilon}$ in finite samples. We then discuss the impact of taking multiple draws from the perturbation distribution, a practice we discourage. Throughout this section, $\xi$ is drawn from the uniform distribution on $[0,\bar{\varepsilon}]^{d_{\theta}+k}$ and $b_{n}=1/\sqrt{\log(n)}$.\footnote{The length of the identified set was large enough so that the quantile correction in (ref) in Step 5 of the procedure did not play a substantial role in this example.}
To gain insight into the role of $\bar{\varepsilon}$ in finite samples, we consider a simple generalization of a DGP analyzed by andrews2009invalidity.\footnote{This example is also considered in gafarov2021inference Section 3.3.2. } In particular, let:
Now set $\psi(W_{i},\theta) = \psi(\theta) = \theta$ (a scalar) and consider the following optimization problems:
It is straightforward to see that:
In particular, $P \mapsto \Psi_{I}^{\ell b}(P)$ is not Hadamard differentiable (and thus not UHD) under this DGP, since condition (CQ) is violated in the minimization problem. In finite samples, we expect the distortions in coverage when $\bar{\varepsilon}=0$ to be the largest when $L$ is large. We consider the case when $L=1$---which matches the DGP in andrews2009invalidity---and $L=10$. The latter DGP will emphasize the severe under-coverage that is possible in this simple example.
Figure (ref)(a) shows the coverage probability of our confidence set as a function of $\bar{\varepsilon}$ for $\alpha=0.1$, for various samples sizes, in the case when $L=1$. Figure (ref)(b) shows the case when $L=10$. For comparison, we also include the coverage probability at $n=10^{4}$ using the fang2021inference procedure, and both the primal and dual formulations of the gafarov2021inference procedure. The dual formulation is explictly recommended by gafarov2021inference for this DGP, since the constraint qualification assumptions in gafarov2021inference fail for the primal formulation but hold in the dual formulation.\footnote{C.f. gafarov2021inference section 3.3.2. } Since it is not always easy to tell when these assumptions fail, the primal formulation is included for comparison. Consistent with the discussion above, when $\bar{\varepsilon}=0$ the $90\%$ coverage probability is $0.79$ when $L=1$ and $0.408$ when $L=10$. The rate at which the coverage probability improves as $\bar{\varepsilon}$ becomes larger depends on the sample size. This is consistent with the theoretical predictions, which suggest that even small values of $\bar{\varepsilon}$ will lead to over-coverage in sufficiently large samples. However, it also illustrates a tradeoff in finite samples: as emphasized in Figure (ref)(b), when $\bar{\varepsilon}$ is “small” relative to sampling uncertainty, the perturbation may not be sufficient to correct the distortions in the coverage probability when the (unperturbed) value functions are not UHD. On the other hand, “large” values of $\bar{\varepsilon}$ relative to sampling uncertainty can lead to over-coverage in finite samples. Note that Figure (ref) is also informative about the effect of rescaling all moment inequalities by a positive constant, which is essentially equivalent to a rescaling of the value of $\bar{\varepsilon}$.\footnote{When each moment condition is re-scaled by a different amount, the effect in finite sample can be ambiguous. In unreported simulations, we found that re-scaling the variance of only $W_{i1}$ (for $L=1$ and $L=10$) had essentially no effect on the coverage probability. }
In comparison, the confidence sets of both fang2021inference and gafarov2021inference under-cover slightly for $n=10^4$ when $L=1$: the $90\%$ coverage probability for the fang2021inference procedure was $0.852$, and the $90\%$ coverage probability for the gafarov2021inference procedure was $0.790$ for the primal and $0.836$ for the dual. The fang2021inference procedure has similar coverage when $L=10$, at $0.842$. For the gafarov2021inference procedure, the $90\%$ coverage probability when $L=10$ is only $0.112$ for the primal formulation and $0.048$ for the dual formulation. Although the assumptions of gafarov2021inference hold for the dual formulation, the low coverage appears to result from the failure of the gafarov2021inference bias correction procedure when using the recommended tuning parameters.\footnote{All of the gafarov2021inference results were obtained using the tuning parameters $\mu_{n}$ and $\kappa_{n}$ recommended in Section 5.2 of gafarov2021inference. The coverage probability using the gafarov2021inference procedure improved only when the values of the tuning parameters were substantially increased. However, as illustrated in this section, our procedure also faces the same difficult problem of selecting appropriate tuning parameters for good finite sample performance. } For $n=10^4$, our procedure obtains nominal coverage at $\bar{\varepsilon}=0.008$ when $L=1$ and $\bar{\varepsilon}=0.049$ when $L=10$.
In addition to exploring the support of the perturbation, we also explore the consequences of drawing multiple perturbations with a simulation exercise. Our ultimate goal with this exercise is to discourage the practice of taking multiple perturbation draws. Since the length of our confidence set depends on the random draw $\xi$, for a fixed $\bar{\varepsilon}$ researchers may be tempted to draw multiple perturbations until a confidence set of favourable length is obtained. With larger values of $\bar{\varepsilon}$, redrawing the perturbation can have a large effect on the length of the confidence set. Although redrawing the perturbation a finite number of times is asymptotically valid for our procedure, it can have important impacts in finite sample.
To explore the impact of taking multiple perturbation draws, we again consider the example in (ref). For both $L=1$ and $L=10$, we consider redrawing the perturbation for the moment inequalities $1$, $10$, $100$ and $1000$ times, and take the smallest confidence set across all draws. Figure (ref) shows the $90\%$ coverage probability as a function of $\bar{\varepsilon}$ obtained from the various confidence sets using this procedure. While the coverage probability is increasing in $\bar{\varepsilon}$ for all confidence sets, the figure shows that---for a fixed $\bar{\varepsilon}$---taking many perturbation draws and selecting the most favorable draw may limit the ability of the perturbation to overcome coverage distortions due to UHD failures in finite sample. With $1000$ perturbation draws, the benefits of the perturbation are eliminated almost entirely. In the end, we recommend that researchers use the uniform distribution and take a single draw for the perturbation.
To provide additional evidence, we perform Monte Carlo experiments on the three empirical examples introduced in Section (ref). The examples show that the coverage is at least the nominal level for all samples sizes, and illustrate the conservative distortion that is possible in large samples. Throughout this section we also compare with the approaches of fang2021inference and gafarov2021inference. The details on all the DGPs considered in the simulations are provided in Appendix D. In all Monte Carlo exercises we take $\overline{B}=999$ bootstrap samples for each experiment. We implement each experiment $500$ times to compute the simulated coverage probability, which is determined by computing the worst case coverage probability across all points in the identified set. We consider various sample sizes $n\in \{250,500,10^3,10^4,10^5,10^6\}$. The large sample sizes are considered to illustrate the conservative nature of our confidence set, but also to alleviate concerns that our approach delivers confidence sets that are overly-wide relative to the identified set in large samples. For each DGP, $\xi$ is drawn from the uniform distribution on $[0,\bar{\varepsilon}]^{d_{\theta}+k}$ with $\bar{\varepsilon} = 10^{-3}$, and $b_{n}=1/\sqrt{\log(n)}$. In Appendix D.4 we explore the sensitivity of our results to the choice of $\bar{\varepsilon}$, and also explore the role of $\gamma(\alpha)$ from (ref).
In the missing data example, the partially identified parameter vector is the probability vector $P(Y=y,D=d)$ for $y \in \{1,2,3,4,5\}$ and $d \in \{0,1\}$. Thus, our parameter vector has $10$ elements. We then construct confidence sets for the unconditional mean of the variable $Y$ (see Appendix D for additional details). The simulation results are displayed in Table (ref). For all sample sizes and confidence levels the simulated coverage probability is above the nominal level. The conservative distortion from our procedure becomes especially obvious at sample sizes larger than $n=10^4$. For samples size $n=10^5$ and $10^6$ the coverage probability is $1$ for all the values of $\alpha$ we consider, although at these sample sizes our confidence set is very close to the identified set. Figure (ref) shows a comparison of the coverage probabilities of our method versus the methods of fang2021inference and gafarov2021inference for $n=10^3$ and $n=10^4$. For both sample sizes our proposed procedure is slightly more conservative.
For the interval valued regression example, the partially identified parameter vector is the $4 \times 1$ parameter $\theta$ in the regression $Y=X^\top\theta+\varepsilon$, where $Y$ is interval-valued (see Appendix D for more details). We construct confidence sets for the first component $\theta_{1}$ of this parameter vector. The worst case coverage probability over the identified set is displayed in Table (ref), and is above the nominal level for nearly all sample sizes and confidence levels. Figure (ref) then shows a comparison of the coverage probabilities of our method versus the method of fang2021inference and gafarov2021inference at various sample sizes. For $n=10^3$, our proposed procedure has similar performance to the procedure of gafarov2021inference, although we find the procedure of fang2021inference has more power at values of $\psi$ far from the identified set. At $n=10^4$, the rejection probabilities of the three procedures are quite close.
Finally, the simulation results for the counterfactual treatment example are displayed in Table (ref). This example compares two counterfactual treatment policies. The partially identified parameter is the full joint distribution of $(Y_{0},Y_{1},D)$ conditional on $X$ and $Z$, which has $32$ elements in our DGP. The functional of interest is $\E_{P}[Y^{A}-Y^{B}]$, the difference in expected outcomes under two counterfactual treatment assignments. See Appendix D for details. Similar to the previous examples, the worst case coverage probability over the identified set is above the nominal level for all sample sizes, and the conservative distortion becomes especially apparent at larger sample sizes. Unlike the missing data and interval valued regression examples, this example does not satisfy the assumptions in fang2021inference since the functional of interest has a data-dependent gradient. Thus, we only compare with the procedure of gafarov2021inference. Our proposed procedure has slightly better power than the procedure of gafarov2021inference for this example, although the differences are small.
Computation times for our proposed procedure and the procedure of fang2021inference and gafarov2021inference are displayed in Table (ref). All times are without any parallelization, which can be used to reduce the computational time of both our proposed method, and the method of fang2021inference. The results show that the method of gafarov2021inference is the fastest, followed by our method, and then followed by the method of fang2021inference.\footnote{Note the method of gafarov2021inference does not require any resampling procedure, which explains the computational advantage relative to our method.}
This paper proposes a simple procedure for constructing confidence intervals for functionals or scalar subvectors of a partially identified parameter vector. Our confidence interval is constructed by repeatedly solving perturbed bootstrap linear programs, and then selecting the appropriate quantiles of the resulting bootstrap distributions. The efficacy of algorithms for linear programming problems means our confidence set is computationally easy to construct. Uniform validity of our proposed procedure is proven under weak assumptions using genericity results for linear programming problems. We show that our perturbed linear programs are uniformly Hadamard differentiable almost surely with respect to a user-specified perturbation distribution, and use this result to apply a uniform functional delta method. The benefits of the approach are that it is fast, conceptually simple, and valid under weak assumptions. However, the resulting confidence set has a coverage probability tending to 1 over the identified set, and exact coverage on an outer set under some additional assumptions. In this sense, the approach modifies the coverage objective in exchange for some practical benefits. An unresolved question in the paper is how to choose the support of the perturbations in finite samples, although we believe the proposed perturbation approach has enough promise to justify this as a fruitful avenue of future research. \\
Disclosure Statement: The authors report there are no competing interests to declare.