Constraint Qualifications in Partial Identification

Constraint Qualifications in Partial Identification

\onehalfspacing

Introduction

This paper connects two related but largely separate literatures, namely statistical analysis of stochastic programs and estimation and inference for (functions of) partially identified parameters. The bounds that are pervasive in the latter literature are often expressed as values of constrained optimization problems. As such, some similarity to stochastic programming is rather apparent and has been observed before. However, we uncover much deeper connections between these literatures.

Our discussion starts from the econometrics literature. In a seminal paper, Chernozhukov_Hong_etal2007aE provide a comprehensive analysis of consistency of criterion function-based set estimators and their convergence rates in partially identified models. Their work highlights the challenges a researcher faces in this context and puts forward possible solutions in the form of assumptions under which specific rates of convergence attain. While these assumptions can be dispensed with when the researcher's goal is to obtain a confidence set for the partially identified parameter vector that is --pointwise or uniformly-- consistent in level (e.g., AndrewsSoares2010E), related assumptions reappear when the aim is to obtain a confidence interval for a smooth function of the partially identified parameter vector that is --pointwise or uniformly-- consistent in level (e.g., PakesPorterHo2011, BCS14_subv).\footnote{We cite PakesPorterHo2011 because the published version PPHI_ECMA does not contain the inference procedure. However, this procedure has been used in influential papers Eizenberg,HoPakes14,Holmes11.} Some more recent contributions ChoRussell,Gafarov observe a connection to stochastic programming and show that inference becomes much more tractable under the so-called Linear Independence constraint qualification. Some obvious questions arise: How do all these assumptions relate? What is the trade-off between them and possibly other assumptions from the statistics literature?

For a sense of why consistent estimation of identified sets or their projections can be hard even in otherwise well-behaved moment inequality settings, consider Figure (ref). Both panels illustrate a detail of an identified set $\Theta_I$ defined as the collection of parameter values satisfying a finite number of moment inequalities (as in (ref) below, but without equality constraints). Each restriction is represented by a curve and excludes everything above that curve. The resulting $\Theta_I$ is shaded.\footnote{An exact algebraic description of the example in Figure (ref) is as follows. Let $\Theta=\mathbb{R}^2$ with typical element $\theta=(\theta_1,\theta_2)$ and let $\Theta_I=\{\theta:(\theta_2-1)^3+\theta_1E(X_1)\leq 0,(\theta_2-1)^3-\theta_1E(X_1)\leq 0\}$ for the left panel; for the right panel, additionally require $\theta_2\leq E(X_3)$, where $E(X_1)=E(X_2)=E(X_3)=1$. Looking ahead, the right panel of Figure (ref) and both panels of Figure (ref) are qualitative representations.} Suppose now that a researcher wants to find either (i) a set estimator of $\Theta_I$ that is consistent in Hausdorff distance (defined later) or (ii) an estimator of a linear projection of $\Theta_I$ (e.g., the identified set for a component of $\theta$), represented through the support function

in pre-determined direction $p$. (In the figure, $p=(0,1)$, i.e. we maximize $\theta_2$.) Even if all constraints' graphs can be estimated at a specific --e.g., parametric-- rate, it does not follow that their intersection estimates either object of interest at the same or indeed at any rate. For example, if estimators approximate the true constraints from below, the support function may be underestimated including in the limit.

The examples may appear “knife-edge." However, note that: (i) While we will, in this paper, take a pointwise perspective to simplify the analysis, the literature on partial identification is usually concerned with inference that is uniformly valid near such irregular cases because asymptotic approximations may otherwise be misleading. Indeed, this is emphasized in the abstract of CS17. (ii) Inference methods that are uniformly valid typically use “Generalized Moment Selection" methods (see again CS17 for details) that account for statistical uncertainty not only of moment conditions that are violated in sample, but also of ones that are local-to-binding. In these methods, the “overidentified" feature of the right-hand panel, i.e. the intersection of more than $d$ constraints at one point in $\mathbb{R}^d$, becomes typical of bootstrap d.g.p.'s. In addition, this feature characterizes the boundary case of overidentifying moment conditions, though some assumptions discussed below will exclude that case anyway.

A reader familiar with constraint qualifications in optimization problems will recognize that both panels of Figure (ref) violate some of these qualifications. Conversely, a reader who is very familiar with the partial identification literature might recognize that they violate assumptions in CHT, PPHI, and elsewhere. We ask if this reflects deeper relations between these bodies of literature. The answer will be affirmative: Under a background assumption of continuous differentiability of moment conditions and abstracting from details of “how uniformly" the assumptions are stated, the literature on partial identification already invokes constraint qualifications; for examples, we show that both papers just cited rely on the Mangasarian-Fromowitz constraint qualification. This implies some previously unrecognized (to our knowledge) logical relations between assumptions made in econometrics.

Some references to the literatures that we connect are as follows. MolinariHOE gives a current overview over the field of partial identification. CS17 provide a definitive treatment of the literature on moment inequalities. We will define constraint qualifications below but refer to baz:she:she06 for a textbook treatment and to BonnansShapiroBook for a textbook on perturbation analysis of stochastic programs.

Assumptions

This section clarifies the general setup and introduces a broad array of assumptions from the literature. For the reader's convenience, these assumptions, and some results that we will explain later, are summarized in Table (ref).

We assume throughout that the model is correctly specified and that individual moment conditions are well-behaved. Specifically, the identified set $\Theta_I$ is characterized by $J$ constraints, namely $J_1\le J$ moment inequalities and $J_2\equiv J-J_1$ moment equalities:

where the functions $(m_1(\cdot),\dots,m_J(\cdot))$ are known up to $\theta \in \Theta$. Then we impose:

These assumptions are standard in the literature. The requirement that $\Theta_I \subset \operatorname{int}(\Theta)$ may appear stronger than the comparable one in CHT, i.e. their condition M2. However, the latter imposes continuous differentiability of moment conditions on a small enlargement of $\Theta$, so it does constrain $\Theta_I$ to be interior to the set on which local linear approximation of moment conditions is valid. This is how we use the assumption, and we could analogously weaken it.

We next state numerous assumptions that are inspired by the aforementioned literature in econometrics. We first state them in a way that maximizes resemblance to the original formulation, subject to the unification that assumptions are stated pointwise (not uniformly) over d.g.p.'s and that their local implications near extreme points of $\Theta_I$ are extracted. Universal constants invoked in assumptions need not take the same value across appearances.

Define the support set of $\Theta_I$ as $$ S(p,\Theta_I) \equiv \{\theta \in \Theta_I: p'\theta=s(p,\Theta_I)\},$$ where the support function $s(\cdot)$ is defined in (ref), and the supporting hyperplane as $$ H(p,\Theta_I) \equiv \{\theta \in \Theta: p'\theta=s(p,\Theta_I)\}.$$ Any element of $S(p,\Theta_I)$ is also called a support point. We use $\theta^*$ to denote a generic support point; to economize on subscripts and because we consider $p$ fixed, we suppress dependence of $\theta^*$ on $p$. Recall also that a constraint is active at $\theta$ if $E(m_j(X,\theta))=0$. Let

denote the set of active inequality constraints and

the full active set of (equality or inequality) constraints at $\theta$.

We first adapt two assumptions, “Degeneracy" and “Polynomial Minorant," from CHT. These are essential for getting rate results for consistency of analog estimators of $\Theta_I$; in particular, Polynomial Minorant ensures rate results for a relaxed sample analog of $\Theta_I$, and Degeneracy allows one to drop the relaxation. We weaken the assumptions insofar as they are only imposed at support points. Also, we do not adapt the high-level Conditions C.2 and C.3 from CHT because, being about sample objects, they restrict the sampling process and not just population moments. To keep these issues separate, we focus on the sufficient conditions that stand in for the assumptions in a moment inequalities setting (i.e., CHT's displays 4.5 and 4.6).

This “degeneracy" assumption ensures that for any support point $\theta^*$, there exists a nearby point where moment inequalities hold with slack and whose membership in $\Theta_I$ is therefore easy to determine. In particular, we show in the proof of Theorem (ref) that Assumption (ref) precludes the existence of equality constraints.

In the original version, the equivalent of (ref) was stated using Hausdorff distance, i.e. $d_H(\Theta_I,\Theta_I^{-\varepsilon}) \leq M\varepsilon$, where $d_H(A,B)=\max\{\max_{a \in A} d(a,B),\max_{b \in B} d(b,A)\}$ for generic sets $A,B$ with typical elements $a,b$. However, $\max_{\theta \in \Theta_I^{-\varepsilon}} d(\theta,\Theta_I)=0$ because $\Theta_I^{-\varepsilon} \subset \Theta_I$, so here and in the original, only the implied restriction on $\max_{\theta \in \Theta_I} d(\theta,\Theta_I^{-\varepsilon})$ is nonvacuous. We localize it by restricting $\theta$ to a neighborhood of the support point.

This “minorant" assumption ensures that the population criterion increases not too slowly as one moves away from $\Theta_I$. Loosely speaking, it prevents “weak identification" problems. Next, BCS impose a polynomial minorant condition as well.\footnote{In the respective originals, both assumptions raise the r.h.s. to a power $\gamma>0$, hence “polynomial minorant." However, in both cases, $\gamma$ is restricted in ways that imply $\gamma=1$ in the present setting.}

It bears emphasis that the last two assumptions are logically independent. Assumption (ref) forces the population criterion to increase (to first order) as we move away from $\Theta_I$. Assumption (ref) enforces an analogous increase as we move away from the support set $S(p,\Theta_I)$ along the supporting hyperplane. This does not imply Assumption (ref) because it only applies as one leaves $\Theta_I$ in selective directions. But it also is not implied because the directions considered in Assumption (ref) may be tangential to $\Theta_I$, in which case the increase in $d(\theta,\Theta_I)$ may be of low order. Indeed, Assumption (ref) may be considered restrictive: By not allowing directions to be tangential to $\Theta_I$ without also being tangential to $S(p,\Theta_I)$, it excludes smooth maxima, e.g. any identified set whose entire boundary is a smooth manifold.\footnote{Consider the single moment inequality $\theta_1^2+\theta_2^2-E(X) \leq 0$, with $E(X)=1$ and $p=(0,1)$. Then $S(p,\Theta_I)$ is a singleton at $\theta^*=(0,1)$. Let $\theta=(\zeta,1)$, then $\theta_1^2+\theta_2^2-E(X)=\zeta^2$, whereas $d(\theta,S(p,\Theta_I))=\zeta$, violating Assumption (ref) as $\zeta \to 0$; at the same limit, we have $d(\theta,\Theta_I)=\sqrt{1+\zeta^2}-1>\zeta^2/4$, so that Assumption (ref) holds. We note that this and other easy counterexamples to Assumption (ref) do not seem to be counterexamples to the BCS profiling method. We leave to future research the question whether this illustrates the possibility of relaxing their assumptions.}

We next adapt (in this order) assumptions 3, 4(a), and 4(b) from PPHI. These are modified in a few ways: PPHI assume that the support point $\theta^*$ is unique; this assumption is removed. Assumptions are also localized by only looking at $\theta$ near $\theta^*$; this makes the first of them meaningfully weaker. At the same time, PPHI impose assumptions uniformly over d.g.p.'s; to keep this paper focused, such uniform statements are removed throughout.\footnote{To compare the statements of assumptions, also keep in mind notational conventions: PPHI write moment conditions as $E(m_j(\cdot))\geq 0$, set $p=(-1,0,\dots,0)$, and use $1$-subscripts to denote first components of vectors, so that $t_1$ there would be $-p't$ here.}

Brief intuitions for these are as follows. Assumption (ref) ensures that $\Theta_I$ is contained in a cone that has $\theta^*$ as apex and does not otherwise intersect $H(p,\Theta_I)$. In particular, this implies uniqueness of $\theta^*$ (although we will not use this feature) and pointiness of the tangent cone (defined later) at $\theta^*$. Assumption (ref) ensures that locally to $\theta^*$, there exists a direction in which all moment expectations, hence their maximum, strictly decrease. Note in particular that this excludes equality constraints -- while this implication is not explicit in PPHI, they treat equalities as conjunctions of two inequalities, and the assumption cannot possibly hold for both. PPHI point out that their assumption is inspired by CHT's Degeneracy (i.e., our Assumption (ref)), which also excludes equalities. Indeed, both assumptions force $\Theta_I$ to have an interior, and we will have more to say about their relation later. Assumption (ref) enforces that the criterion is strictly increasing in many directions from $\theta^*$, including all that have positive inner product, and some that have negative inner product, with $p$.\footnote{The restriction $\delta<0$ in Assumption (ref) correctly reflects our source. However, we considered the possibility that (in our notation) $\delta>0$ was intended. The assumption then becomes weaker. Specifically, along the lines of our main result below, one can show that it is then equivalent to $\max_{j \in \mathcal{J}^*(\theta^*)} D_j(\theta^*)p >0$ and is implied by Assumption (ref).}

We finally recall some classic constraint qualifications. This requires some standard notation that we will also use later. For any $\theta \in \Theta_I$, define the tangent cone $$ \mathcal{T}(\theta) \equiv \biggl\{t \in \mathbb{R}^d: \exists \{\theta_m\}_{m=1}^{\infty} \subset \Theta_I, \theta_m \to \theta, \lim_{m \to \infty} \frac{\theta_m-\theta}{\Vert \theta_m-\theta \Vert} = \frac{t}{\Vert t \Vert} \biggr\} \cup \{0\} $$ as well as the linearized cone $$ \mathcal{L}(\theta) \equiv \bigl\{t \in \mathbb{R}^d: D_j(\theta)t \leq 0,j \in \mathcal{J}_1^*(\theta);D_j(\theta)t = 0,j \in \{J_1+1,\dots,J\} \bigr\}. $$ We will only invoke these objects for support points $\theta^* \in S(p,\Theta_I)$. Recall that $\mathcal{T}(\theta) \subseteq \mathcal{L}(\theta)$ baz:she:she06.

Both cones are illustrated in Figure (ref). They coincide in “nice" examples like the right panel of Figure (ref) (indeed, this “niceness" is the Abadie constraint qualification defined below) but they may disagree, as in the left panel which reprises the left panel from Figure (ref).

We can then state the following constraint qualifications in decreasing order of restrictiveness.

Of course, the LICQ requires at most $d$ active constraints, making it quite restrictive.

These conditions are frequently invoked in the statistical literature. For example, Shapiro90,Shapiro1991aAOR,Shapiro93 uses either LICQ or uniqueness of Lagrange multipliers, and these two assumptions are essentially the same Wachsmuth. In econometrics, ChoRussell and Kaido:Santos use LICQ; andrews_roth_pakes and Gafarov restrict attention to linear constraints and thereby impose ACQ.

Results

Restating Some Assumptions, and a First Set of Equivalences

We next restate some of these assumptions, exploiting their localization or using the language of constraint qualifications. Between our “localization" of assumptions and the language of tangent cones, several of the assumptions we just introduced can be stated more succinctly. In what follows, recall that $\mathcal{J}^*(\theta)$, defined in (ref), is the active set of (equality or inequality) constraints at $\theta$. Specifically, define:

Then we have:

Econometric Assumptions as Constraint Qualifications

We now present our main insight: Several of the above assumptions are equivalent, or very close to, constraint qualification assumptions, and there are numerous logical relations between them. Our main result, which is also visualized in Figure (ref), follows.

Tightness of Theorem (ref)

We next clarify that Theorem (ref) is tight, i.e., no implication that is not indicated in Figure (ref) holds true. This subsection can be skipped without loss of continuity.

Let $m_j(X,\theta) = \mu_j(\theta) +X_j$ for functions $\mu_j:\Theta \mapsto \mathbb{R}$ defined below and suppose that all $X_j$ are standard normal; thus, $E(m_j(X,\theta))/\sigma_j(\theta)=\mu_j(\theta)$. Also, $\Theta=[-1,1]^2$. All examples are constructed s.t. the support point of interest is $\theta^*=(0,0)$. Direction of projection is $p=(0,1)$ unless explicitly indicated otherwise. There are no equality constraints, so for the purpose of these examples, “MFCQ and no equalities" is just MFCQ.

\paragraph{Neither Assumption (ref) nor (ref) imply either (ref) or (ref) (ACQ).}

We start with this example because several others build on it. Qualitatively, it is the left panel of Figure (ref). The linear cone $\mathcal{L}(\theta^*)$ is spanned by $\{(0,1),(0,-1)\}$, the tangent cone $\mathcal{T}(\theta^*)$ is spanned only by $\{(0,-1)\}$. The one direction, $t=(0,-1)$, that is in $\mathcal{T}(\theta^*)$ is tangential to all constraints. The example violates ACQ (and all stronger assumptions) as well as (ref) but fulfills (ref) as well as (ref).

\paragraph{Assumption (ref) does not imply (ref) (MFCQ).}

This example adds a third constraint to the first example; compare the right panel of Figure (ref). Both $\mathcal{L}(\theta^*)$ and $\mathcal{T}(\theta^*)$ are spanned by $(0,-1)$. The example therefore fulfills (ref) (and by implication ACQ) but not MFCQ.

\paragraph{Assumption (ref) (ACQ) does not imply (ref).}

Here, $\mathcal{L}(\theta^*)=\mathcal{T}(\theta^*)=\{t:p't\leq 0\}$, so that ACQ is fulfilled. However, (ref) is violated in direction $t=(1,0)$:

\paragraph{Assumption (ref) does not imply (ref) (ACQ).}

In this example (which is inspired by a well-known counterexample to ACQ), we have that $\mathcal{L}(\theta^*)$ is spanned by $\{(-1,-1),(1,-1)\}$ but $\mathcal{T}(\theta^*)$ is spanned by $(0,-1)$ only.

\paragraph{Assumption (ref) does not imply (ref) or (ref).}

In this example, $\mathcal{L}(\theta^*)$ and $\mathcal{T}(\theta^*)$ coincide and are spanned by $\{(-1,0),(1,-1)\}$, contradicting both (ref) and (ref). Assumption (ref), which here only applies if we move in direction $(1,0)$ from $\theta^*$, is fulfilled.

Discussion

Our findings inform a number of clarifying remarks on the existing literature.

Verifying Assumptions in Some Examples

In this section, we discuss how these restrictions apply to two well-understood examples of partial identification. It will become clear that one cannot take for granted that they “typically" hold and that verifying them could be intricate in more involved examples. That is part of our message: We point out that many of them are basically constraint qualifications, and it is well known that constraint qualifications can be subtle to verify.

The examples are visualized in Figure (ref), which is designed to resemble Figure (ref). Note that in the second example, $\Theta_I$ has zero measure.

Linear regression with interval outcome data and discrete regressors

Consider a linear regression model:

where $Z=(Z_1,\dots,Z_d)$ is a $d\times 1$ random vector with $Z_1=1$. We assume that $Z$ has $k$ points of support denoted $\mathcal Z=\{z^1,\dots,z^k \in \mathbb{R}^d\}$ with $\max_{r=1,\dots,k}\Vert z^r \Vert<M<\infty$. The researcher observes $\{W_0,W_1,Z\}$ with $P(W_0\le W \le W_1|Z=z^r)=1,r=1,\dots,k$, where $\pi^r=P(Z=z^r)>0,r=1,\dots,k$ are assumed known. Suppose that $W_0$ and $W_1$ take values in $\mathcal W\subset\mathbb R$. An important special case is missing data, where $W_0$ and $W_1$ both equal the true $W$ if the latter is observed and correspond to some bound on it otherwise.

The identified set is characterized by the following moment inequalities.

Equivalently,

Define the following objects.

Note that, since $D_j$ does not depend on $\theta$, we drop its argument.

By (ref)-(ref), the identified set is a polytope characterized by $k$ pairs of parallel constraints

See the left panel of Figure (ref) for an illustration with $k=3$. Each support point is either a vertex of the polytope or a point in the relative interior of a non-singleton support set. We therefore analyze subcases below. Note that, since the gradients $z^1,\dots,z^k$ of the constraints in (ref) are known, one knows without data which case applies.

We first establish conditions implying MFCQ. For $j=1,\dots,2k$, define:

We call $H_j$ a hyperplane and $H_j^-$ a half space. Let $\operatorname{ri}(A)$ denote the relative interior of $A$. A $(d-1)$-dimensional flat face in $\mathbb R^d$ is called a facet. Similarly, a $\ell$-dimensional element of a $d$-dimensional polytope is called a $\ell$-face, where $1\le\ell\le d-2$. For example, a $1$-face is an edge in a 3 dimensional polytope.

We conclude by mentioning other conditions. The identified set $\Theta_I$ is a finite polytope, hence any projection is the value of a linear program. This immediately clarifies that ACQ obtains, which furthermore means that Assumptions (ref) and (ref) coincide. Both restrict $\mathcal{L}(\theta^*)$, which locally just coincides with $\Theta_I$, to not intersect the supporting hyperplane other than at $\theta^*$. This will hold iff the support set is a singleton, i.e. a vertex. Finally, the solution to a linear program is necessarily well-separated, so that Assumption (ref) holds.

A Simple Entry Game

Two-player entry games are a workhorse example of partial identification since Tamer03. We analyze the game specified in BCS but without covariates. The equilibrium concept is pure strategy Nash equilibrium (PSNE). Firm $1$ respectively $2$ enters if

where $(A_1,A_2)\in\{0,1\}^2$ are the firms' actions, $(\theta_1,\theta_2)\in [0,1]^2$ are the interaction parameters, and $(\varepsilon_1,\varepsilon_2)$ are observed by the players but not by the researcher. This system is incomplete: For certain realization of $(\varepsilon_1,\varepsilon_2)$, both $(1,0)$ and $(0,1)$ are PSNE and the model is silent on which is played. Hence, different (stochastic) selection mechanisms picking an equilibrium in the region of multiplicity can be coupled with different values of $\theta$ to yield the same distribution of observables $(A_1,A_2)$. Nonetheless, inference can be carried out by bounding the likelihood of different outcomes from below by the respective probabilities of them being unique PSNE. In this simple example, this exhausts all the information in the model and data, leading to a sharp identification region. See BMM_ECMA for characterizations of sharp identification regions in more complex models.

In this model,

Letting $\pi_{jk}=\Pr(A_1=j,A_2=k)$ and assuming (as in BCS) that $(\varepsilon_1,\varepsilon_2)$ are distributed independently uniformly on $[0,1]$, we have

Geometrically, the identified set $\Theta_I$ is an arc segment. The right panel of Figure (ref) depicts its true shape if $\pi_{01}=\pi_{10}=\pi_{11}=1/3$.

Consider now the problem of bounding $\theta_2$ from above; all other bounds on individual parameters are similar. Guessing that (ref)-(ref) will bind at the solution, one can easily solve for

Furthermore, the linear and tangent cone are tangent to (ref) and are spanned by $(\pi_{10}+\pi_{11},-\pi_{11}/(\pi_{10}+\pi_{11}))$. This vector has strictly negative inner product with $p=(0,1)$. We conclude:

However, fulfillment of some of these assumptions is delicate in that it depends on $\theta^*$ being an exposed point of $\Theta_I$. Other directions of optimization (e.g., $p=(1,-1)$, corresponding to testing the null that $\theta_1=\theta_2$) have $\theta^*$ in the relative interior of $\Theta_I$, i.e. at a point where only (ref) is active. Assumptions (ref), (ref), and (ref) will then fail.

Conclusion

The literature on partial identification uses constraint qualifications in many ways: To ensure Hausdorff consistency or rates of convergence for simple estimators of identified sets Yildiz2012, to justify inference for the full parameter vector $\theta$ (CHT) or subvectors ChoRussell,Gafarov, or to justify efficiency bounds Kaido:Santos. However, some of these uses are implicit, making it difficult even for expert readers to compare assumptions. We provide a guide to how different high-level assumptions relate to each other and to well-known constraint qualifications. A simple, important message is that several high-level assumptions are tightly related to the Mangasarian-Fromowitz constraint qualification and are essentially mutually equivalent. We believe that this provides useful guidance to readers trying to make sense of the large menu of inference methods for partially identified vectors and subvectors CS17,MolinariHOE. For example, it clarifies costs and benefits relative to work that has weak-to-no geometric regularization, mostly at the expense of computational effort.