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.
105,197 characters · 22 sections · 87 citation commands
Simple subvector inference on sharp identified set in affine models
\setcounter{page}{1}
Strong econometric assumptions can lead to poor estimates. Sometimes, moment inequalities can provide alternative estimates under weaker assumptions. Linear models with interval-valued outcome data are a good example.\footnote{Other examples of affine-moment inequalities include monotone instrumental variables (manski2000monotone, Freyberger201541) and models with missing data (manski2003partial).} It is common practice to replace income-bracket data with the corresponding midpoints when estimating the returns to schooling (trostel2002estimates). However, the conventional approach is applicable only under strong assumptions about the distribution of the residual term.\footnote{Another common approach is to assume Gaussian distribution for the residuals and apply the maximum likelihood method (stewart1983least). } The affine moment inequality approach to interval-valued data proposed by manski2002inference can set-identify the return to schooling without such strong assumptions.
Multiple methods can be used to construct confidence sets (CS) for parameters defined by moment inequalities. The pioneering procedures of chernozhukov2007estimation and andrews2010inference (AS) and their subsequent refinements by bugni2014inference (BCS) and kaido2015inference (KMS) are powerful statistical methods that solve this inference problem in the small-dimensional case. Some applications, such as panel or semiparametric regression models with interval-measured outcome variables, have a high-dimension parameter space, which poses a computational challenge for the existing procedures.\footnote{For example, trostel2002estimates consider a panel regression with more than 60 variables that include country fixed effects, time effects, exogenous demographic control variables, and their interactions.}
I propose a novel regularized support function estimator for the lower and upper extremes of the identified set for an element $\theta_{1}$ of an unknown parameter vector $\typVector{\theta}\in\R^{d}$ in models defined by affine moment equalities and inequalities. In the example of returns to schooling, $\theta_{1}$ corresponds to the returns to schooling and $\typVector{\theta}\in\R^{d}$ to the full vector of the regression coefficients. The novel estimator has a closed-form asymptotic Gaussian distribution, which I use to construct uniformly valid confidence bounds and confidence intervals for $\theta_{1}$. The proposed set has valid asymptotic coverage probability uniformly over a class of data-generating processes (DGP). Uniformity in DGP is a desirable property, as it results in better coverage-probability control in small samples compared to point-wise analogs in nonregular statistical models such as the affine moment inequality model.
The regularized support function proposed in this paper is a solution to a convex quadratic program that minimizes the sum of $\theta_{1}$ and a penalty $\mu_{n}\left\Vert \typVector{\theta}\right\Vert ^{2}$ with $\mu_{n}\to0$, subject to the sample moment restrictions. If the set of optima for $\mu_n=0$ is not a singleton, this additional convex term selects the optimum with the minimal norm as $n$ increases. The standard errors are computed using the sample variance of the weighted moment conditions at the unique optima. To correct the asymptotic bias resulting from the regularization exactly, I suggest using the argmin of the regularized program with a larger tuning parameter $\kappa_{n}\to0$. If $\kappa_{n}/\mu_{n}\to\infty$ as $n\to\infty,$ then the bias correction does not affect the asymptotic distribution of the estimator. To achieve a uniformly valid confidence interval (CI), I replace the exact correction with an upper bound on the maximum of $\mu_{n}\left\Vert \typVector{\theta}\right\Vert ^{2}$ over the argmin set of the nonregularized program.
The proposed CIs have several attractive statistical and computational properties that make them viable in high-dimensional affine moment inequality models.
First, the estimator of the regularized support function has an asymptotically linear (Bahadur-Kiefer) representation that provides an easy-to-compute asymptotic standard error. Consequently, this paper is the first to propose a closed-form estimator of the bounds on $\theta_{1}$ convex moment inequality models with asymptotic Gaussian distribution in the non-regular case (in the absence of strict convexity). In contrast, the estimator of the ordinary support function estimator used in the existing literature (beresteanu2008asymptotic, kaido2014asymptotically, Freyberger201541 (2015, FH), gafarov2018delta, among others) can have a non-Gaussian asymptotic distribution, which complicates uniform inference. To establish the uniform remainder bound in the Bahadur-Kiefer expansion, I developed a novel second-order directional envelope theorem, which is a theoretical result of independent interest.
Second, the proposed approach requires only a fraction of the computational time of the existing uniform procedures if $\typVector{\theta}$ has a large number of dimensions. The computational cost is low since it involves only four quadratic programs, it does not require any resampling, and it depends on covariance of the moment conditions at two points. In the asymptotic analysis, I only consider the case of a fixed dimension of $\theta$ and a fixed number of inequalities for analytical simplicity. The goal of the present study is to focus on the computational difficulties resulting from the high-dimensional moment inequalities. (There are recent papers that are concerned with the impact of the growing number of inequalities on the statistical properties of the inference procedures; see, for example, belloni2018subvector.)
The computation time for my procedure increases slowly in the dimension of $\theta\in\R^{d}$ and takes only 0.1 second for $d=20$ and $k=40$ moment inequalities and 2.5 seconds for $d=100$ and $k=200$. As a result, the proposed method can address parameter $\theta$ with a large dimension and a large number of moment conditions. In contrast, the existing uniform-inference methods for moment inequalities proposed by AS, KMS, and BCS are based on costly nonconvex optimization. In fact, despite the fact that the moment inequalities are convex (linear) the standardized moment conditions are not convex which can potentially result in creation of multiple local optima which complicate computation for these statistical procedures (see Appendix Sections (ref) and (ref)).
I provide an example of an affine moment inequality model by showing that the number of local optimal solutions in existing uniform procedures (AS, BCS, and KMS) can grow exponentially with dimension $d$. As a result, the procedures take more computational time and can produce misleadingly short CIs if the optimization routine fails to find the global optimum. It takes 100 seconds to compute the CI of AS in an affine model with $d=20$ and $k=40$ moment inequalities which is 1000 times longer than the newly proposed method.
The simulation evidence suggests that {the computational speed gains} come without a substantial loss of statistical power. In the non-regular cases, the proposed uniform CIs have length properties that are not worse than those of the existing uniform methods. (The proposed uniform CI has a length within simulation error from the projection CI of AS in the Monte Carlo (MC) design considered in this paper.) In the regular cases, the novel confidence bounds attain the efficiency bound of the usual support function estimators (as shown in kaido2014asymptotically).
The proposed idea of regularizing support functions for linear moment inequality inference gained a subsequent development in a recent work cho2023simple.\footnote{The first draft of cho2023simple was circulated on 27 May 2019 on Arxiv depository two years after the initial distribution of the present paper as a PhD dissertation chapter in gafarov2017essays.} The authors argue that if one is satisfied with an inference on an enlarged identified set, one can simply regularize the moment inequalities by adding random noise to their coefficients under milder regularity conditions. This operation restores a Gaussian limit of the perturbed estimated support function, allowing conventional bootstrap inference on the enlarged identified set. Since the inference is done on the enlarged identified set, one does not need to impose any constraint qualification conditions on the moment inequalities --- they are satisfied automatically with probability 1 after adding the random noise to the coefficients. Unfortunately, this approach results in confidence sets with zero power against all local alternatives corresponding to other nested enlargements of the identified set. In practical terms, it means that the confidence sets can be very conservative if too much noise was added or fail to control size in small samples if the added noise was insufficient (there is no theory that would determine the minimal level of required noise for a given sample size). In contrast, the theory provided in the present paper explicitly studies the impact of the choice of tuning parameters on the size of the regularized identified set. Such an analysis requires imposing constraint qualification conditions on the moment inequalities (Assumption (ref)). Under these conditions, Theorem (ref) shows that for sufficiently small value of the tuning parameters $\mu_n$ and $\kappa_n$ both lower and upper bounds based on the regularized value function coincide exactly with the nonregularized support function in the regular case when the set of primal solutions is a singleton. More generally, under the maintained assumptions, the regularized estimators remain consistent for the bounds on the sharp (non-enlarged) identified set, thus providing non-trivial local power against the relevant alternatives.
Identified sets defined by affine inequalities appear in various economic applications, in particular those dealing with discrete variables and shape restrictions. Linear models with interval outcome, which were originally studied in manski2002inference and haile2003inference, are just one example of affine inequalities. Other examples include bounds on marginal effects in dynamic discrete choice panel models (honore2006bounds, torgovitsky2016nonparametric, torgovitsky2018partial), bounds on average treatment effects (kasy2016partial, Laffer2018, russell2017sharp), nonparametric IV models with shape restrictions (manski2000monotone, Freyberger201541), errors in variables (MOLINARI200881), intersection bounds (honore2006bounds2), revealed preference restrictions (kline2016bounding), and game-theoretic models (syrgkanis2017inference). This paper focuses on the case with finitely many affine unconditional inequalities that are non-overidentifed and that result in a non-empty identified set. This, of course, rules out many interesting economic applications that involve overidentifying moment inequalities shi2018estimating, or where moment inequalities are nonlinear pakes2015moment.
I also contribute to the growing literature on inference on non-differentiable functions and regularized estimators. Bounds on components of a parameter characterized by linear moment conditions considered in this paper are an example of a nondifferentiable (nonregular) function of a parameter (the expectation of the data) that has an asymptotically normal estimator (the sample mean). Distributions of nondifferentiable functions of the normal estimator are hard to approximate using standard methods. (See Section (ref) for a detailed discussion.) I propose differentiable lower and upper bounds that converge to the nondifferentiable function of interest as the sample size grows. Since the bounds are regular parameters themselves, the standard delta method and bootstrap can be used to conduct one-sided or two-sided inference on the bounds. In the regular case, these bounds collapse and coincide with the original parameter of interest, which results in a $\sqrt{n}$-consistent and asymptotically normal estimator. In the non-regular case, the bounds converge at a slower rate and result in a locally biased estimator, which is acceptable for valid one-sided inference.
Another interesting statistical problem that appears in many applications is inference for extrema of finitely many means of random variables. It is known as intersection-bounds problem (hall2010bootstrap and chernozhukov2013intersection) and can be framed as a value of a linear program. The regularized support function estimator can also be used for uniform delta-method CSs in this setting (see Appendix Section (ref)). The approach considered here is expected to have statistical properties similar to chernozhukov2013intersection, but has the advantage of closed-form standard errors and critical values, which correspond to the standard normal distribution.
The paper is structured as follows. Section (ref) describes the setup, gives examples, and summarizes the available literature. Section (ref) provides the main results, applies them to uniform inference on projections, and discusses extensions (overidentified inequality models, joint CSs, characterization of argmin sets). Section (ref) provides the results of the Monte Carlo experiments. Section (ref) concludes.
The following notational conventions are used. $\bydef$ denotes definitions. $\expect\left[\cdot\right]$ denotes expectation with respect to a probability distribution $\measTrue$. Uppercase English letters denote random variables (scalar, vector, or matrix valued), and lowercase letters denote the corresponding realizations, for example, $\Data_i$ and $\data_i$. $\measEmp$ denotes the empirical distribution and $f\left(0^+\right)$ denotes $\lim_{x\downarrow0}f\left(x\right)$. The vector $\ej\bydef(0,...1,...0)'$ is the $j$-th coordinate vector, where 1 occurs at position $j$. $\ej$ is the projector on the $j$-th coordinate. The symbol $\jSet$ denotes a finite set of indices $\jSet\bydef\{i_1,...,i_\ell\}\subset\numbers$ and $\jMat\bydef(e_{i_1},...,e_{i_\ell})^\prime$ as a coordinate projection matrix in the corresponding Euclidean space. $\left|\jSet\right|$ denotes the cardinality of the set $\jSet$. u.h.c. stands for upper-hemicontinuous correspondence.
Consider a support function for a polygon $\setID\subset\R^{d}$ (a set defined by a system of linear equalities and inequalities) that depends on a data generating process parametrized by a measure $\measTrue$ evaluated at a direction $e_1\bydef(1,0,\dots)^\prime \in\R^d$,\footnote{See, for example, rockafellar1970convex}
The set $\setID$, also referred to as an identified set for a parameter vector $ {\theta}\in\R^{d}$, consists of all solutions to the following system of affine moment equalities/inequalities:
Here, $\moment{W}{\theta} \bydef \sum_{\ell=1}^d \Data_{j\ell} \theta_\ell -\Data_{j(d+1)}$. I consider a setup with finitely many unconditional moment functions (that is, $\left|\setEq\cup\setIneq\right|=k$, $\card{\setEq}=p$, $0\leq p \leq d$, $k<\infty$). The random matrix corresponding to an individual observation $\Data$ has probability measure $\measTrue$ with sample space $\R^{k\times\left(d+1\right)}$,
The econometrician observes an i.i.d. sample $\left\{ \data_{i}\in\R^{k\times\left(d+1\right)}|\,i=1,...,n\right\} $ of random matrix $W$. There is a straightforward way to extend the analysis to the case of dependent data as long as a CLT for averages of $\data_{i}$ remains valid.
This setup reduces to a finite-dimensional parametric statistical model once the support function evaluated at $e_1$ is represented as a linear program,
Here, the coefficients on the left-hand side, $\Ap$, and the right-hand side, $\bp$, taken together constitute matrix $\expect \Data \bydef (\Ap|\bp)$. It means $W$’s expectation is a $k\times (d + 1)$ matrix whose first $d$ columns is $A_P$ and the last column is the $k$-dimensional vector $b_p$. Following optimization theory terminology, I occasionally refer to the support function at $e_1$ as value of program (ref) and to the corresponding argmin set as the set of optimal solutions.
The focus on the first coordinate of $\theta$ as an objective of (ref) is without loss of generality. As discussed in Section (ref), the support function evaluated at any unit direction vector $a\in\R^d$ can be represented in the form (ref) after some redefinition of the parameter space (matrices $ \Ap$ and $\bp $ can be functions of the unit vector $a$).
To ensure boundedness of the support function, I assume that system ((ref)) includes inequalities that make the identified set compact,
for some constants $\underline{c},\bar{c}\in\R^d_+$. Moreover, I impose the following assumption:
This assumption implies that $\funLValO<+\infty$. It is valid whenever the model corresponding to (ref) is correctly specified.
Under Assumption (ref), support functions evaluated at $\pm e_j$ characterize projections of $\setID$ on individual coordinates $j$ of $\theta$. In particular, the marginal (projected) identified set for the coordinate $\theta_{1}$ can be represented as an interval $\setMarginal=\left[\funLValO,\funUValO\right]$, where the bounds are support functions evaluated at directions $\eOneVec$ and $-\eOneVec$. Indeed, the upper bound can also be written as a (minus) support function at $e_1$,
The analysis for the upper bound is analogous to the one for the lower bound, so from here on I focus on the lower bound.
The polygon-shaped identified sets considered in this paper appear in many econometric models that feature discrete data, as mentioned in the introduction. Many of these applications are concerned with instrumental variables. I use the linear IV model with interval outcome manski2002inference,chernozhukov2007estimation to illustrate ideas throughout the paper. Other applications of the proposed method include monotone IV manski2000monotone and nonparametric IV Freyberger201541.
Consider a linear model for a random vector $(Y,X,Z)$ satisfying $$\expect\left[Y- {\theta}^{\prime} X| Z\right] =0,$$ where $\theta\in\R^d$ is the vector of regression coefficients. The true outcome $Y$ is unobserved; only its a.s. bounds $\left[\underline{Y},\overline{Y}\right]$ are observed. Suppose that the vector of instrumental variables $Z$ has finite support $\left\{ z_{1},\dots, z_{K}\right\} \subset\R^{d}$. In this case, the model implies a polygon-shaped identified set $\setID$ for $\theta$ defined by a set of moment inequalities,
These inequalities can be represented in the standard form ((ref)) with $p=0$, $k=2K$, and the following observation matrix:
If it is known a priori that for some support points $j$ $$\expect\left[\underline{Y}\Ch{ Z= z_{j}} \right] = \expect\left[\overline{Y}\Ch{ Z= z_{j-K}} \right],$$ then one can replace the corresponding pair of inequalities with a single equality,
In this case, $p$ (the number of equality restrictions) is equal to the number of such support points. One can further incorporate additional shape restrictions information such as signs of components of $ {\theta}$ in the form of linear inequalities to narrow the identified set.
This example appears in the context of the estimation of return to schooling using survey data. trostel2002estimates study economic returns to schooling for 28 countries using data from the International Social Survey Programme from 1985 to 1995. They estimate the conventional mincer1974schooling model of earnings (the human capital earnings function), which has $Y$, the log of hourly wages, satisfying
where the first regressor, $ X_{1}$, is the years of schooling; the other components of $X$ play a role of additional controls. The component $\theta_{1}$ is then interpreted as the return to schooling. It is equal to the percentage change in wages due to an additional year of schooling. To correct for the endogeneity bias in $\theta_{1}$ resulting from omitting the latent ability variable, one can use an instrument vector $Z$ that correlates with $X_{1}$ (for example, an indicator of whether a good school is in proximity or an indicator of the quarter of birth).
Exact measurements of $Y$ are not available for some countries (including the US); only hourly-income- bracket data $\left[\underline{Y},\overline{Y}\right]$ are available.
Instrumental variables $Z$ (coinciding with the control variable) considered in trostel2002estimates take discrete values. The variables include annual fixed effects, union status, marital status, age and age squared, and country-year dummies (in the case of the aggregate equation). With inclusion of the country and time effects, $d$ can be larger than 60. Because of the large number of support points for $Z$, the corresponding system (ref) would also have a large number of linear moment inequalities $k$.
The conventional technique to estimate IV regression with interval-outcome data is to replace the interval data with the corresponding midpoints and estimate the model using the OLS method. This technique is valid only under the unreasonably strong condition
If Equation (ref) is violated, then the OLS estimator with midpoints is inconsistent for the true parameter $\theta$.\footnote{The OLS is, however, consistent for the best linear predictor of the midpoint that may not have the desirable economic interpretation; see, for example, shi2020uniform.} Without assuming that (ref) is satisfied, support function estimators (defined below) provide consistent bounds on marginal identified sets of the true parameter $\theta$ beresteanu2008asymptotic,bontemps2012set.
When constructing valid CSs on projections of identified sets, strictly speaking, one needs only a lower bound on the support function at $e_1$ in (ref). Other applications may instead require estimators of an upper bound on the (minimum) value of an optimization problem. The upper bound can be used, for example, to bound the set of optimal solutions or to construct a consistent inner estimator of a convex identified set bugni2017inference.
Following beresteanu2008asymptotic the parameter $\funLValO$ (the support function at $e_1$) can be estimated using a sample analog,
where the observations $W_i$ are independent copies of the random matrix $W$. The asymptotic distribution of this estimator has been extensively studied in the case of the strictly convex identified set. The strict convexity implies that the support function at $e_1$, $\hat{\underline{v}}_n$ , is differentiable in the sample mean $\sMean W_i$ (under additional regularity conditions discussed below). As a consequence, its sample analog has an asymptotic Gaussian distribution, admits of bootstrap inference, and attains semiparametric efficiency kaido2014asymptotically. In contrast to the strictly convex case, the Gaussian limit is not guaranteed anymore in the general (non-deterministic) linear moment inequality model (kaido2014asymptotically only allow for deterministic linear inequalities under particular regularity conditions).
The stochastic programming approach shapiro1991asymptotic enables an asymptotic analysis of the support function estimators for a fixed direction in the general convex case, which includes the linear moment inequality model. In this section, I briefly review the two main ideas in this approach, Lagrangian duality of convex programs and the delta method for directionally differentiable functions. I conclude with an overview of the alternative inference approaches and their relation to stochastic programming methods.
The Lagrangian duality theory provides additional, often more convenient, formulations of convex programs. Namely, the (primal) program in (ref) has the same value as its Lagrangian dual formulation,
given Assumption (ref). Iff the dual program has a bounded set of solutions $\argminL(\measTrue)$, the support function for a given direction has bounded directional derivatives in $\Ap,\bp$ (defined precisely below). Proposition 5.45 in bonnans2013perturbation provides a necessary and sufficient condition for $\argminL(\measTrue)$ to be bounded:
Condition (ref) enables another, Lagrangian min/max, representation of (ref), which is particularly convenient for computing derivatives of the support function in a given direction for the delta-method-based inference procedures. Suppose that $\Lambda\subset{\R}^{p}\times\R_{+}^{k-p}$ is some compact set that contains $\argminL(\measTrue)$. The support function for a given direction $ e_1$ can then be represented as bonnans2013perturbation
The directional derivative for the value of this min/max program is provided by a corresponding envelope theorem shapiro2014lectures. Namely, the envelope theorem gives a derivative of any perturbed version of the min/max program,
with respect to a scalar $t$ for any uniformly converging sequence of directions $h_t\bydef(h_{A,t},h_{b,t})\to(h_{A},h_{b})$. The derivative takes the form
where $\argminT(\measTrue)$ and $\argminL(\measTrue)$ are sets of primal and dual optima for (ref). Both sets can be nonsingletons as illustrated below.
The derivative (ref) depends on particular optimal primal and dual solutions that are selected by a given perturbation $(h_{A},h_{b})$, unless both sets of solutions are singletons. I refer to parameter values $\Ap$ and $\bp$ resulting in nonsingleton (primal or dual) solutions as nonregular.
shapiro1991asymptotic proposes a generalization of the delta method for the directionally differentiable functions of asymptotic normal estimators. Under Condition (ref), the sample analog of $\funLValO$ has a solution (and thus is well defined) with probability approaching 1. Theorems 3.4 and 3.5 in shapiro1991asymptotic provide an asymptotic distribution of the sample support function in a given direction. It takes form
where $\eG(P)\bydef(\eG_{A}(P),\eG_{b}(P))$ is the limiting zero-mean Gaussian process for $\eG_n(P)\bydef\frac{1}{\sqrt{n}} \sum_{i=1}^n(\data_i-\expect \Data)$ indexed by $\measTrue$. In general, the limit (ref) is non-Gaussian since either of the two sets $\argminT$ and $\argminL$ can be non-singleton. (It does reduce to a Gaussian distribution when both sets are singletons.)
Several robust methods have been designed for inference on components of $\theta$ defined by moment inequalities (nonlinear, in general). The dominant approach has been to test individual values of $\theta$ or their subvectors and then to invert the tests chernozhukov2007estimation,andrews2001testing,andrews2019inference,chernozhukov2019inference, cox2019simple,kaido2019confidence. The main advantage of the test-inversion approach is that fixing $\theta$ simplifies the asymptotic distribution of the test statistics and allows for valid inference under weak assumptions (in particular, one can allow for an empty true identified set as in andrews2019spuriousinference).
Although having attractive statistical properties, the test-inversion methods can become computationally intractable in settings with high-dimensional parameters $\theta$ since they are based on grid search and resampling methods.\footnote{See further discussion of the computational issues in Appendix (ref).} In contrast, delta-method inference using the support function estimators for a fixed direction proposed in this paper remains a computationally tractable (frequentist) option in high-dimensional settings such as mentioned in Section (ref) since it fully uses the linear programming structure of the problem.
Inference using the sample support function for a fixed direction in the non-regular case faces three challenges: (i) nondifferentiability makes the standard bootstrap inconsistent Fang2018inference; (ii) discontinuity in the directional derivative (ref) results in poor (uniform) approximation of (ref) by the numerical bootstrap dumbgen1993nondifferentiable,Hong2018numerical; (iii) the estimator is necessarily (asymptotically) biased hirano2012impossibility. The regularized support function estimator proposed in the next section addresses these challenges in a robust and computationally tractable way.
The main source of inference complications, the lack of smoothness in the support function, resolves itself when the sets of primal, $\argminT,$ and dual, $\argminL,$ optima are singletons (see equations (ref) and (ref)). Consequently, my proposal is to consider a regularized support function at $e_1$ that has a unique solution and approximates the original support function from a known direction, either from above or from below. \footnote{If both primal and dual solutions of the regularized program are unique, all the directional derivatives of the regularized support function at $e_1$ given by (ref) coincide and are given by formulas
where $\argminT \mnP$ and $\argminL\mnP$ are, correspondingly, the primal and dual solutions of the regularized program with a regularization parameter $\mn$. } Since the direction of such a regularization bias is known, the corresponding estimators of the regularized support function at $e_1$ admit standard one-sided delta-method and bootstrap inference based on the normal limiting distribution.
Without regularization, both primal and dual solutions of (ref) can be non-singletons. To keep the problem analytically tractable, I focus on the case in which the dual set is a singleton by assumption, and I propose a regularization for the primal problem. In this way, I can explicitly consider only the bias from the primal regularization and develop the necessary bias correction. Appendix Section (ref) discusses the complementary case of dual regularization.
The following regularized primal program is strictly convex for any $\mu>0$ and hence has a unique primal solution $\argminT (\mu, P)$ and approximates the optimal value of program ((ref)):
The corresponding dual program has a unique solution $\argminL(\mu,P)$ iff the set of constraints satisfies the linear independence constraint qualification (LICQ; see shapiro1991asymptotic and wachsmuth2013licq),
The set of DGPs that satisfy LICQ is not closed since a limit of a sequence of linearly independent matrices can be a reduced rank matrix. This means that depending on the size of the smallest singular value of the gradients of the set of binding constraints at any point may be arbitrary small while still satisfying LICQ. As a result, the dual solutions $\argminL(\mu,P)$ may be arbitrary large, implying large derivatives of $\minV\mnP $ and may require very high sample sizes for reasonable precision of the delta-method inference (see equation (ref) in Lemma (ref) in Appendix Section (ref) for details). In the next section, I provide sufficient conditions for LICQ that explicitly ensure that the class of DGP under consideration is closed, so that we can uniformly control the quality of the delta-method inference within this class. Then I illustrate these conditions in the context of Example (ref).
LICQ is often considered hard to verify kaido2019constraint. In fact, a direct test of this assumption would face two problems: (i) the set $\setID$ is unknown but can only be estimated with an error; (ii) the set of binding inequalities at each $\theta$ is also unknown. Because of their multiple-testing nature, both problems would complicate inference beyond the practical level. Moreover, LICQ does not provide an explicit bound on the dual variables required for uniform validity analysis.
Some authors, including hsieh2017inference, make a high-level assumption about boundedness of the dual variables. Others (KMS and andrews2019inference) focus on test inversion and thus only require restriction on non-degenerate covariance matrix of the moment functions. Both KMS and andrews2019inference compute critical values of a test at a particular point $\theta$ which they then invert. (kaido2019confidence additionally propose a method for computationally efficient interpolation of confidence sets based on test inversion.) KMS, for example, only need a bounded dual variable for each of the bootstrap draws for their purposes. The local linear program that is used in KMS bootstrap has a bounded dual variables almost surely under the aforementioned covariance constraints since its inequality constraints have random bootstrapped coefficients. In contrast, I need stronger assumptions to be able to estimate the nuisance parameter, the argmin set $\argminT(\mnP)$ and the dual solutions $\argminL(\mnP)$, which allows me to avoid the test inversion stage and achive compuational gains.
I propose a sufficient condition for LICQ in the form of bounds on the values of two auxiliary optimization programs. The values of these programs, in turn, explicitly characterize an upper bound on the dual variables, allowing for a uniform asymptotic analysis. Specifically, within this class of DGP satisfying this assumption, we can uniformly control the quality of the delta-method inference by establishing an explicit uniform bound on the relevant second-order directional derivatives.
To introduce the sufficient conditions for LICQ, I use the following notation. For any $\jSet\subset\setIneq$, let the matrix $\activeMat=(e_{i_1},...,e_{i_\ell})^\prime$ correspond to $ \activeSet\bydef \setEq \cup \jSet = \{i_1,...,i_\ell\} $, a set of active constraints. Let $\eta_1(\cdot)$ be the smallest left singular value function of a matrix; that is, $\eta_1(A) \bydef \sqrt{ \min_{u}( u^\prime A A^\prime u/ u^\prime u ) }$ . The sufficient conditions can now be formulated as the following two assumptions on every submatrix $\activeMat (\Ap|\bp)$ that include all $p$ equality constraints and either $d-p$ or $1+(d-p)$ inequality constraints.
Assumption (ref) can be summarized using two characteristics:
These numbers measure how close a given DGP $\measTrue$ to a violation of LICQ condition in population and determine how many observations are required to meet LICQ and have non-empty feasible set for a sample analog of program (ref) with a given probability (see Lemma (ref) in Appendix).
Both characteristics $\eta(\measTrue)$ and $ s(\measTrue)$ can be consistently estimated using a plug-in approach. As long as a sample analog of $\setID$ is nonempty, sample analogs of $\eta(\measTrue)$ and $ s(\measTrue)$ will be generically positive. In principle, a critical value can be obtained for a formal test of hypothesis $\eta(\measTrue)\geq \underline{\eta}$ and $s(\measTrue)\geq \underline{s}$ for any given pair of numbers $\underline{\eta},\underline{s}$ along the lines of cragg1997inferring.\footnote{See also Appendix Remark (ref) for an alternative representation of Assumption (ref) as a single characteristic minimal bound on a different subset of submatrices of $ (\Ap|\bp)$.} I leave this formal test for future research.
Assumption (ref) rules out more than $d$ binding inequality constraints at any point $\theta\in\setID$. There are some special empirical applications resulting in a singleton identified set $\setID$ in which such overidentifying inequality constraints can appear, which can result in multiplicity of dual solutions.\footnote{See, for example, gafarov2014identification and shi2018estimating who consider cases of infinitely many inequality conditions.} This multiplicity can be eliminated using a regularization of the dual program (ref); that is, Assumption (ref) can be relaxed within the framework proposed in this paper, but such an extension is left for future research. I briefly discuss this proposal in Appendix Section (ref).
It is instructive to see what Assumption (ref) implies for our running example.
Appendix Section (ref) contains further technical details about Assumption (ref).
Clearly, for any positive $\mu$, the value of the regularized program (ref) $\minV(\mu\measTrue)$ is larger than $\minV (\measTrue)$ by at least $\mu\ltwo{\argminT(\mu,\measTrue)}^{2}$. A tempting approach would be to correct for this regularization bias by subtracting $\mu\ltwo{\argminT(\mu,\measTrue)}^{2}$. Unfortunately, this correction makes the corrected value function $\minV(\mu,\measTrue)-\mu \ltwo{\argminT(\mu,\measTrue)}^{2}$ non-differentiable in the paramteters $A_P,b_P$ if the non-regularized value function $\minV (\measTrue)$ itself is non-differentiable. So to preserve differentiability of the bias-corrected value function, which is crucial for delta-method inference, one cannot use argmin of the actual regualrized programm for bias corrections. Instead, I suggest to tighten the bounds on $\minV (\measTrue)$ using one the following two corrections,
where $\argminT(\kappa,\measTrue)$ is an argmin of the regularized program (ref) with a larger tuning parameter $\kappa$ instead of $\mu$, $\theta^*$ is any point in $ \argminT(\measTrue)$. As $\mu$ and $\kappa$ shrink to zero, these bounds continuously shrink to $\minV (\measTrue)$ above and below, respectively. The expressions in (ref) provide valid conservative bounds from above and below for $\minV(\measTrue)$ that are useful for uniform one-sided inference (coverage probability in this case can be higher than nominal level). For the remainder of the paper, the focus will be on the confidence bounds that cover $\minV (\measTrue)$ from below. So $\minVout(\mu,\measTrue) $ will play the major role. The uses of $\minVin(\mu,\kappa,\measTrue)$ for uniform inference are discussed in Appendix Section (ref)
Although for a given DGP $P$, characterized by $(A_P,b_P)$, the cutoff $\bar{\mu}(\measTrue)$ is well defined, it can change discontinuously as a result of a small change in $(A_P,b_P)$. It makes a consistent estimation of $\bar{\mu}(\measTrue)$ a challenging task. So instead of trying to estimate $\bar{\mu}(\measTrue)$, I suggest using two appropriately chosen shrinking sequences $\mu_n$ and $\kappa_n$ instead of fixed tuning parameters $\mu$ and $\kappa$.
The gap between $\minV(\measTrue)$ and $\minVout(\mu_n,\measTrue) $ is at least $\mu_n (\ltwo{\theta^*}^{2}-\ltwo{\argminT(\mu_n,\measTrue)}^2)\geq0$; for $ \minVin(\mu_n,\kappa_n,\measTrue) $ the gap is at most $\mu_n (\ltwo{\argminT(\mu_n,\measTrue)}^{2}-\ltwo{\argminT(\kappa_n,\measTrue)}^2)\leq0$. In the nonregular case, that is where $\argminT(\measTrue)$ is non-singleton, the gap for $\minVout(\mu_n,\measTrue) $ is shrinking to $0$ at rate $\mu_n$ which still results in a consistent estimators of $\minV (\measTrue)$ at rate $\mu_n$ that can be slightly slower than the regular parametric rate $1/\sqrt{n}$ (for example, $ {\sqrt{\ln{n}}}/{\sqrt{n}}$). As a result, the corresponding confidence sets cover the projections of the sharp identified set, not an enlargement of it (in contrast to other studies, including cho2023simple, who do not use consistent estimators of the sharp bounds on the identified set and study an enlarged identified set instead). The gap for $\minVin(\mu_n,\kappa_n,\measTrue)$ becomes exactly equal to zero for some sufficiently large $n$ in both regular and nonregular cases, resulting in exact corresponding point-wise one-side confidence sets.
Consider the analog estimator of $\funLVal[\mu_{n}]$ for some sequence $\mu_{n}$,
As we shall see in this subsection, this estimator admits an asymptotic linear (Bahadur-Kiefer) expansion with an explicit approximation error, which determines the precision of asymptotic normal and bootstrap inference. This allows me to establish the validity of the corresponding inference methods uniformly over a reasonable class of DGP. Uniform asymptotic validity is crucial for small-sample performance of inference methods in the presence of possible discontinuous changes of the asymptotic distribution of estimators (for example, $\funLValHat[\mu_{n}]$) with respect to DGP parameters (for example, $\measTrue$).
I consider the class of all measures $\Measures=\Measures(\underline{\eta},\underline{s},\varepsilon,\bar{M})$ that satisfy Assumptions (ref)-(ref) with some positive constants $\underline{\eta}$, $\underline{s}$, $\varepsilon$, and $\bar{M}$.
To summarize, every $\measTrue\in \Measures$ satisfies $\setID\neq \emptyset$, $\eta(\measTrue)>\underline{\eta}$, $s(\measTrue)>\underline{s}$, and $\expect\left\Vert \Data\right\Vert^{2+\varepsilon} < \bar{M}^{2+\varepsilon}$.
The class $\Measures$ includes DGPs (parameterized by measure $\measTrue$) with multiplicity of primal solutions of (ref) but assumes uniqueness of dual solutions. This property is necessary to show that program (ref) has a nonempty sample argmin and a unique vector of Lagrange multipliers in large enough samples with probability approaching 1 uniformly in $\measTrue\in\Measures$ as $n\to\infty$ (see Lemma (ref) in Appendix Section (ref)). As discussed in Section (ref), one can study a case with multiple dual solutions and a unique primal solution in a similar way (see Appendix Section (ref)).
A Bahadur-Kiefer expansion of estimator defined in program (ref) can be established using the envelope theorem (ref). As discussed in Section (ref), this theorem typically holds for the sample support function at $e_1$ . However, this theorem does not provide bounds on the higher-order directional derivatives. So, without additional assumptions, the directional delta method of shapiro1991asymptotic does not provide means to evaluate the error of the asymptotic approximation of the sample support function at $e_1$ by (ref). Since the limiting distribution changes discontinuously with the DGP $\measTrue$, poor performance of asymptotic methods based on the limit (ref) should be expected when the parameter $\measTrue$ is close to a discontinuity point. In other words, inference procedures that estimate (ref) directly (for example, subsampling or directional bootstrap) will inevitably be only point-wise valid and can have poor finite-sample performance in such cases. (It is an implication of the impossibility theorem of hirano2012impossibility for a functional that is directionally differentiable.)
In contrast, the regularized support function at $e_1$ admits a stronger version of the envelope theorem that provides a bound on the error of the linear approximation uniformly over $\measTrue\in\Measures$. I developed this novel bound using a second-order directional Taylor expansion of a system of generalized inequalities that define the optimal solutions to the regularized program (see Lemmas (ref) and (ref) in Appendix Section (ref)). Using this result, the asymptotic linear (Bahadur-Kiefer) representation of the value function in program (ref) follows almost immediately (see Lemma (ref) in Appendix Section (ref)):
The first term on the right-hand side of this representation is a scaled sample average of a zero-mean random variable, which admits a uniform Gaussian approximation. (Indeed, the binding constraints have zero mean at $\argminT$, while the nonbinding constraints are multiplied by zero dual variables $\argminL$.) The residual term $O_\Measures(1)$ denotes a uniformly tight sequence of a random process indexed by $\measTrue\in\Measures$. Analogously, I denote any random sequence as $ o_\Measures(1)$ if $\lim_{n\to\infty}\sup_{\measTrue \in \mathcal{P}}\measTrue\left( \ltwo{\zeta_n(\measTrue) }\geq \epsilon \right) =0$.
The Bahadur-Kiefer representation (ref) is important for three reasons. First, it suggests a coupling of $\funLValHat[\mu_{n}]$ with a Gaussian process (through the Yurinsky theorem). Second, it implies uniform validity of the optimization-free score bootstrap, which is particularly computationally convenient. Third, it suggests an analog estimator of the asymptotic variance of the regularized support-function estimator,
where $\funLArgHat[\mu_{n}]$ and $\funLLagrangeHat[\mu_{n}]$ are, respectively, the optimum and the vector of Lagrange multipliers of ((ref)), which are provided by common constraint-optimization software packages.
These implications are summarized in the following theorem.
The coupling with a Gaussian random process (ref) is a strong approximation result, which can be understood using a geometric interpretation. The distance between the difference $ \sqrt{n} ( \funLValHat[\mu_{n}]- \minV\mnP )$ and some sequence of zero-mean Gaussian r.v.s $ N\left(0,\funLStd[\mu_{n}][\measTrue][2]\right)$ converges to zero with the same uniform rate for all DGP $\measTrue \in \mathcal{P}$. This property is stronger than conventional CLT-type results, since it does not require the existence of a limiting distribution for the approximating Gaussian variables.
Theorems (ref) and (ref) can be used to construct uniformly valid confidence bands (one-sided CS) for $\minV(\measTrue)$. The corresponding generic algorithm takes the following form:
The following subsections explain specific implementations of this algorithm for uniformly valid CSs for a projection of the identified set on a single coordinate or multiple coordinates and for the argmin set of a linear program with estimated coefficients.
Let's revisit one of the primary objects of interest in the moment-inequality models: CSs on projections of the identified set, $\setMarginal\bydef\left[\funLValO,\funUValO\right]$ .
Theorems (ref) and (ref) suggest that the outer-bound estimator for the minimal value,
is asymptotically unbiased (in the regular case) or biased downward (in the nonregular case). (Some downward bias is acceptable since the purpose of CSs is to cover the lowest point $\funLValO$ from below.) To achieve this property, the estimator $\theta^*\left(\measEmp\right)$ should have a norm that is not smaller than the minimal norm in $ \argminT(\measTrue)$ with probability approaching 1. We can use an estimator $\theta^*\left(\measEmp\right)$ that converges to the point with the coordinates
where
By definition, $\ltwo{\theta^*}\geq \ltwo{\theta}$ for any $\theta \in \argminT(\measTrue)$. (See the proof of consistency in Lemma (ref) in Appendix A.)
This bound on $\ltwo{\theta^*}$ has two attractive properties. First, it can be (uniformly) consistently estimated using only $2k$ linear programs, which can be easily computed even in models with a very large-dimension $k$ and a large number of inequalities using interior-point numerical optimization methods. Second, in the regular case, in which $\argminT(\measTrue)$ is a singleton, this estimator is asymptotically unbiased since it converges to $ \ltwo{\theta^*} = \ltwo{\argminT(\measTrue)} $. So for any such fixed $\measTrue$, by Theorem (ref) we have $\minV^{out}(\mu_{n},\measTrue)=\minV(\measTrue)$ for sufficiently small $\mu_n$; that is, it is possible to construct CIs with correct (nonconservative) coverage in the regular case.
Using the bias-corrected estimator $\minV^{out}(\mn,\measEmp)$ and its analog for the upper bound, $\maxV^{out}(\mn, \measEmp)$, I construct the following delta-method CSs:
Here, $z_{1-\alpha}$ is $1-\alpha$ quantiles of the standard Gaussian distribution and
for some small positive number $\sigma_0$. $\mbox{CB}_{\alpha,n,\Measures}$ is a one-sided CB for $\funLValO$ (and for $\theta_1$ as well), $\mbox{CI}^{\theta_1}_{\alpha,n,\Measures}$ is a two-sided CI that covers any $\theta_1$ in the identified set, and $\mbox{CI}_{\alpha,n,\Measures}^{\mathcal{S}}$ is a two-sided CI (based on the Bonferroni inequality) that covers the entire maginal identified set $\setMarginal$. The tuning parameter $\sigma_0$ is introduced to guarantee the nominal coverage in the cases in which only nonstochastic constraints are binding at the optimal solutions corresponding to the support functions; otherwise, this degeneracy can lead to superconsistent support-function estimators with a non-Gaussian limiting distribution. One can set $\sigma_0=0$ if this concern is not appropriate in a particular application.
As before, let $\Measures$ contain all measures $\measTrue$ that satisfy Assumptions (ref)--(ref) with some uniform positive constants $\underline{\eta}$, $\underline{s}$, $\varepsilon$, and $\bar{M}$.
Note that the worst-case (that is, the smallest) asymptotic coverage probability of $\mbox{CB}_{\alpha,n,\Measures}$ is exactly equal to $1-\alpha$ for a fixed regular DGP such that $\argminT(\measTrue)$ is a singleton and $\lim_{n\to\infty}\funLStd[\mu_{n}][\measTrue][2]>\sigma_0\geq 0 $. For a nonregular DGP (or sequence of DGPs), the asymptotic coverage can only be larger than $1-\alpha$. How conservative is $\mbox{CB}_{\alpha,n,\Measures}$ in the nonregular case? We can evaluate it by comparing its average length with that of a confidence bound that has exact point-wise asymptotic coverage probability in a Monte Carlo study (see Section (ref)). Theorem (ref) in Appendix Section (ref) provides an alternative bias correction that remains non-conservative in the non-regular case and results in shorter point-wise confidence bounds. This approach is based on using an estimator of the inner bound $\minVin(\mu,\kappa,\measTrue)$.
I conclude this section with a brief discussion of the tuning parameters. The theory of optimal choice of tuning parameter is beyond the scope of this paper. The following considerations, however, can provide some guidance for the optimal choice. Theorem (ref) suggests that the tuning parameters should be smaller than $ \bar{\mu}(\measTrue)$ to avoid the bias in the first-order asymptotic distribution. This choice is infeasible since $\bar{\mu}(\measTrue)$ is unknown, so one has to let $\kappa_n$ and $\mn$ go to zero. The optimal rates of $\kappa_n$ and $\mn$ should balance the higher-order variance and the worst-case bias. A specific choice of the tuning parameters is discussed in Section (ref).
It is trivial to extend the analysis to $$\underline{v}(\measTrue;a)=\displaystyle\min_{ {\theta}\in\setID} a^\prime {\theta}$$ for any $a\in R^d$ with $\ltwo{a}=1$. Indeed, Assumptions (ref)--(ref) are invariant with respect to orthogonal transformations of the coordinates; that is, they are satisfied for the following program (with $\tilde{\theta}=U^\prime \theta$, $\tilde{\Ap} = \Ap U$, and $a^\prime= \eOne U $ for any orthogonal matrix $U$):
We can think of $\tilde{\Ap}$ as a coefficient matrix under a different measure $\tilde{\measTrue}$, $A_{\tilde{\measTrue}}$. The set of measures $\Measures$ from Section (ref) includes $\tilde{\measTrue}$ corresponding to all orthogonal transformations of $\Ap$.
The identified set $\setID$ is convex, so any projection of it can be characterized using support functions for a corresponding direction. One can construct a joint CS for $\setID$ as follows. For any set of directions $\mathcal{A}\subset R^d$, take $$ \text{CS}^\mathcal{A}_{\alpha,n} = \{\theta| a\in\mathcal{A} , a^\prime \theta \leq -\minV^{out} (\mn,\measEmp;-a) + c_{1-\alpha}n^{-1/2} \max\{\underline{\sigma}(\mn,\measEmp;-a),\sigma_0\}\},$$ where $c_{1-\alpha}$ is $1-\alpha$ quantiles of the maximum of the corresponding asymptotic Gaussian variables (also known as $\sup t$ statistics) that can be estimated using multiplier bootstrap enabled by the asymptotic linear representation, (ref).\footnote{ I leave full analysis of mulitplier bootstrap procedure in this setup for future work; see additional discussion in Appendix Section (ref).} One can also use the Bonferroni inequality-based standard Gaussian critical value $c_{1-\alpha}= z_{1-\alpha/|\mathcal{A}|}$.
Choosing the set of directions appropriately $\mathcal{A}$, we can construct joint CSs for projections of $\setID$ on any subvectors $\theta$. If $\mathcal{A}$ has finitely many elements, $ \text{CS}^\mathcal{A}_{\alpha,n}$ is a polygon. So we can plot it directly without performing test inversion as in the one-dimensional case. The confidence set $\mbox{CI}_{\alpha,n,\Measures}^{\mathcal{S}}$ is a particular case of $ \text{CS}^\mathcal{A}_{\alpha,n}$ corresponding to $\mathcal{A}=\{e_1,-e_1\}$ and the Bonferroni estimate of $c_{1-\alpha}$. It seems natural to construct a joint CS for $\theta$ based on directions that correspond to the normal vectors of the moment conditions. For simplicity, assume that $p=0$. The original system (ref) may have some inequalities that are slack for any point $\theta\in\setID$. We can characterize the identified set $\setID$ as the solution to a tight system of inequalities
where
Every inequality in system (ref) is active at least at one point in $\setID$ (any point in the argmax of (ref)). Programs (ref) meet Assumptions (ref)--(ref), and therefore the outer estimators $ \hat{\underline{b}}_j^\text{out}$ are half-median unbiased with the corresponding standard error estimators $\hat{\sigma}_j$. Then the following polyhedron CS will cover any point $\theta\in\setID$ with asymptotic probability of at least $1-\alpha$ uniformly over $\measTrue\in\Measures$, $$ \text{CS}^\mathcal{N}_{\alpha,n} =\big \{\theta \big| e_j^\prime \hat{A}_P \theta \leq \hat{\underline{b}}_j^\text{out} + z_{1-\frac{\alpha}{k}} n^{-1/2} \max\{\hat{\sigma}_j,\sigma_0\} , j\in\setIneq \big\},$$ where $z_{1-\frac{\alpha}{k}}$ is the critical value of the standard normal r.v. and $k$ is the number of (in)equality restrictions. The generalization to the case $p\neq0$ is straightforward.
In this Monte Carlo study our goal is to evaluate how the confidence bound's length and the corresponding coverage probability depends on a number of key factors: (i) how close gradients of the relevant moment inequality to the non-regular case (i.e. being collinear with the vector $e_1$) ; (ii) how tuning parameter choice affects the conservativeness of confidence bounds; (iii) how the dimension of the problem and the number of inequalities affect length, coverage and computational time for the proposed methods. The last exercise in the list also involves a comparison with the AS projection implemented using KMS EM computational algorithm.
To illustrate the advantages of uniform coverage compared to point coverage, we can study a simple design with $k=4$ moment inequalities where the angle $\omega$ between the gradient of one of the faces of the identified set and vector $e_1$ varies continuously. The expectation of the moment inequalities can be parametrized as follows
The shape of this set is a parallelogram analogous to the one in Figure (ref) in with $\rho\geq0$. The parameter $\omega\in[0^{\circ},36^{\circ}]$ defines the angle between the normal vectors of the rear sides of the parallelogram and the horizontal axis. The value $\omega=0^{\circ}$ corresponds to a square-shaped identified set, also referred to as a non-regular case because the sides are orthogonal to the gradient of the objective function. All other values are termed regular. In the vicinity of $\omega=0^{\circ}$ pointwise valid $\mbox{CB}_{\alpha,n}$ may have a coverage probability below the nominal level because it lacks uniform validity. The expectation $\expect W$ is parameterized to guarantee $\argminT_1=\argminT_2=-1$ and $\argmaxT_1=\argmaxT_2=1$ for all values of $\omega$. The components of $W_i$ are independent Gaussian random variables with variance $s_2^{2}=0.01$. For each value of $\omega$, I compute the frequency of coverage and the excess average length over the identified set for $\mbox{CB}_{\alpha,n}$ and $\mbox{CB}_{\alpha,n,\Measures}$ based on the sample sizes $n\in\{100,10000\}$. The number of MC simulations is $1000$ for every combination of $n$ and $\omega$. The focus is on the nominal coverage probability $\alpha=0.95$.
As the main choice of tuning parameters, I use $\mu_n = \hat\mu_0 \sqrt{n^{-1}\ln\ln n}$ and $\kappa_n = \hat\mu_0 \sqrt{n^{-1}\ln n}$ , where $$\hat\mu_0 = \sqrt{\frac{1}{n}\sum_{i=1}^n \big( \argminL^\prime(0,\measEmp)\data_i e_1 - \frac{1}{n}\sum_{i=1}^n \argminL^\prime(0,\measEmp)\data_i e_1 \big)^2 }.$$ While a theory of optimal choice of $\hat\mu_0$ is beyond the scope of this paper, this particular choice has some advantages: (i) $\hat\mu_0$ depends only on the behavior of the relevant moment inequalities as selected by non-zero components of $ \argminL^\prime(0,\measEmp)$; (ii) it does not depend on the dimension of the parameters $\theta$, since only the first column of $w_i$ is involved; (iii) it has the same scale as the standard deviation of the relevant components of $w_i$ which justifies our perturbation analysis (the impact of the regularization term $\mu_n \ltwo{\theta}^2$ is larger than the sample variation, $\sim \hat\mu_0 n^{-1/2}$). As a result, this choice resulted in a good alignment of the theoretical predictions with the simulations, as can be seen below.
To appreciate the importance of uniformly valid confidence bounds, we start our study with point-wise valid confidence bounds $\mbox{CB}_{\alpha,n}$. Figure (ref) panel (a) shows the corresponding coverage frequency for a small sample size $n=100$ and a large sample with $n=10,000$. For values of $\omega$ that are far from $0$, both sample sizes have observed a frequency of covering the correct bound of the identified set for $\theta_1$ close to the nominal coverage probability of $\alpha=0.95$. The same is true for the nonregular case with $\omega = 0$. However, in the vicinity of the nonregular case $\omega \in (0,4^\circ]$, large sample sizes are necessary to achieve a satisfactory coverage frequency. In contrast, the coverage frequency for the corresponding sample sizes for the uniformly valid confidence bounds $\mbox{CB}_{\alpha,n,\Measures}$ given on Figure (ref) panel (b) is uniformly at least as large as $\alpha$ for all values of $\omega$. One can see that the only point on Figure (ref) panel (b) with coverage is significantly higher than $\alpha=0.95$ for $n=10,000$ is $\omega = 0$, that is, for most designs (or equivalently, directions of the support function), the uniformly valid confidence bounds $\mbox{CB}_{\alpha,n}$ have exact coverage.
The difference in coverage frequencies of $\mbox{CB}_{\alpha,n}$ and $\mbox{CB}_{\alpha,n,\Measures}$ can be understood by considering the behavior of the corresponding average excess length of the bounds, i.e. the Monte Carlo average of the difference between the corresponding confidence bounds and the true bound of the identified set $\argminT_1=-1$. Figure (ref) panel (c) compares the lengths of the two bounds for the small sample case $n=100$ where the point-wise inference becomes unreliable. One can see that the confidence bounds should have an excess length approximately equal to $0.025$ to match the coverage frequency with the nominal probability $\alpha$ in the proximity of $\omega =0$. The length of $\mbox{CB}_{\alpha,n,\Measures}$ is larger than necessary for $\omega=0$, while $\mbox{CB}_{\alpha,n}$ has the correct length for $\omega=0$, but is too short in the neighborhood $ (0,4^\circ]$. For values $\omega\geq 5$ both confidence bounds have approximately the same length, which also corresponds to the correct coverage probability predicted by Theorems (ref) and Appendix Theorem (ref).
First, consider the effect of the tuning parameter $\mu_n$ on the coverage probability for the uniformly valid confidence bounds $\mbox{CB}_{\alpha,n,\Measures}$. Figure (ref) panel (a) compares the coverage frequency of $\mbox{CB}_{\alpha,n,\Measures}$ for the sample size $n=100$ as a function of $\omega$ for two choices: (i) $\hat\mu_0 \sqrt{n^{-1}\ln\ln n}$ (baseline) and (ii) $\hat\mu_0 \sqrt{n^{-1}\ln n} $ (large). The baseline option has slightly less conservative coverage in the neighborhood of the nonregular design ($\omega=0$) and similar performance for other values of $\omega$. As a result, the baseline option is used for all the other simulations.
Unlike its uniform counterpart, the point-wise valid confidence interval $\mbox{CB}_{\alpha,n}$ depends on additional tuning parameter sequence $\kappa_n$. Theorem (ref) claims that for one-sided bounds $\mbox{CB}_{\alpha,n}$, the asymptotic coverage is exactly equal to $\alpha$ as long as $\kappa_n$ shrinks to zero slower than $\mu_n$. This allows values of $\kappa_n$ to be smaller than $\mu_n$ and still result in (point-wise) valid inference. Figure (ref) panel (b) compares three choices: (i) $\kappa_n= \hat\mu_0 \sqrt{n^{-1}\ln n} > \mu_n$; (ii) $ \kappa_n=\mu_n$; (iii) $ \kappa_n=0<\mu_n$. From the practitioner's perspective, options (ii) and (iii) are attractive since they only require the specification of one tuning parameter $\mu_n$. Both additional choices (ii) and (iii) result in valid point-wise coverage in large samples (see Appendix Figures (ref) and (ref)).
For $n=100$, $\omega>4^\circ$ all three options have nearly indistinguishable coverage frequency. The behavior is notably different between the three for $ \omega \in [0,4^\circ]$. Choice (ii) still results in a lower probability of coverage than the required probability, but the problematic neighborhood $[0,2^\circ]$ is smaller than for choice (i). The choice $\mu_n=\kappa_n$ for $n=10,000$ is particularly in good alignment with the nominal coverage $\alpha=0.95$. The choice (iii) essentially results in $\mbox{CB}_{\alpha,n}$ being the same length as $\mbox{CB}_{\alpha,n,\Measures}$ (see Appendix Figure (ref)). The similar performance in simulation suggests that $\mbox{CB}_{\alpha,n}$ with $\kappa_n=0$ may have uniformly valid coverage like $\mbox{CB}_{\alpha,n,\Measures}$. However, a formal study of uniform validity for $\mbox{CB}_{\alpha,n}$ with $\kappa_n=0$ is more difficult to conduct than for $\mbox{CB}_{\alpha,n,\Measures}$.
In this section, we study the effect of the dimension of $\theta$ on the coverage probability and the length of the confidence bounds. The design of the constraints matrix $\expect W=\expect (\Ap|\bp)$ is given by
The first line corresponds to an equality constraint that depends on a unit vector with direction $a\in\R^{d-1}$. This equality constraint is deterministic, that is, $\operatorname{Var}W_{1j}=0$ for all $j=1,\dots,d+1$. Other constraints are inequality constraints with coefficients that are i.i.d Gaussian r.v. with $\operatorname{Var}W_{ij}=0.01$ for all $j=1,\dots,d+1$ and $i=2,\dots,(1+2d)$. The identified set for the first coordinate $\theta_1$ in this design corresponds to values of a support function of a $d-1$ dimensional rectangular box $[-1,1]^2\times[-1/\sqrt{d-3},1/\sqrt{d-3}]^{d-3}$ in direction $a$ (and $-a$). As before, the focus is on the lower bound, since by design the upper bound is symmetric. When $d=3$ and $a=(1,0)^\prime$, this design reduces to the two-dimensional design considered in the previous subsection with $\omega=0$.
We consider two possible values for $a$: (a) regular case, $a=\iota_{d-1}/\sqrt{d-1}$; (b) nonregular case, $a=(1,0,\dots,0)'\in\R^{d-1}$. In the regular case $\argminT = (-\iota_2,-\iota_{d-3}/\sqrt{d-3})$. In the nonregular case, the argmin set $\argminT$ is a convex hull of $2^{d-1}$ corner points with coordinates $(-1,\pm1,\pm1/\sqrt{d-3})$. Every such corner point has the same distance to $0$, equal to $\sqrt{3}$, for $d>2$ regardless of the dimension $d$. This normalization was chosen to make performance comparisons as dimension grows while keeping the diameter of the identified set fixed. In this way, we isolate the effect of the number of dimensions and constraint from the effect of the diameter of the identified on the dual variables. By design, the asymptotic variance of the regularized estimators will not change with the dimension. We used $n=1000$ data points and $N=1000$ Monte Carlo simulations. We use the first option for the tuning sequences, namely $\mu_n = \hat\mu_0 \sqrt{n^{-1}\ln\ln n}$ and $\kappa_n = \hat\mu_0 \sqrt{n^{-1}\ln n}$.
First, consider the coverage probability of the confidence bounds $\mbox{CB}_{\alpha,n}$ and $\mbox{CB}_{\alpha,n,\Measures}$. Panel (a) in Figure (ref) shows that in the regular case both the uniform and the point-wise valid confidence set have a coverage frequency that is within the simulation error bound from the nominal coverage probability of $\alpha=0.95$. At the same time, the coverage of the two procedures becomes noticeably different from each other for $d>40$. It suggests that the size of the neighborhood where the uniform inference becomes important gets wider with $d$. The nonregular design provided on panel (b) in Figure (ref) shows that uniformly valid confidence bounds have a coverage frequency nearly equal to $100\%$. The point-wise bounds $\mbox{CB}_{\alpha,n}$ are less conservative for all $d$, but still reach the $100\%$ coverage frequency for $d\geq21$. It suggests that the sample size required for exact asymptotic coverage for $\mbox{CB}_{\alpha,n}$ gets larger as dimension grows.
The probability of coverage above the nominal level $\alpha=0.95$ in the nonregular case with high dimension $d$ reflects the fact that as the number of corner points increases exponentially with $d$. As a result, the nonregularized support function gets increasingly biased as it has asymptotic distribution of a minimum of $2^{d-1}$ Gaussian r.v. as evident from (ref). Fortunately, this extreme conservatism only appears in the worst possible case. For a randomly chosen direction of a support function $a\in\R^{d-1}$, the performance is expected to be closer to that of panel (a) of Figure (ref), at least for sufficiently large sample sizes $n$.
As a benchmark, I use $\mbox{CB}_{\alpha,n,AS}$---one-sided confidence bounds for $\argminT_1$ based on andrews2010inference with Bonferroni critical values implemented using the fast E-A-M algorithm of kaido2015inference. This choice of benchmark is one of the fastest available uniformly valid procedure in the literature. The two alternative approaches, bugni2014inference and kaido2015inference, can provide uniformly valid CSs with a potentially shorter average length than $\mbox{CB}_{\alpha,n,AS}$. However, both are expected to take considerably more time to compute because they add time-consuming profiling or calibration steps. AS results are only available in the nonregular case because of the software restrictions.\footnote{The code is available at https://molinari.economics.cornell.edu/programs.html. This code is highly optimized for the case of inference on bounds on individual coordinates of the identified set. The code does not allow making confidence sets for arbitrary directions $a$.} Nevertheless, AS is not adaptive and is expected to have a similar length regardless of whether we compute the bounds in regular or nonregular directions $a$. The coverage probability equal to the confidence sets to $100\%$ also applies to $\mbox{CB}_{\alpha,n,AS}$. Figure (ref) shows that for $d\geq9$ for $n=1000$, the uniformly valid $\mbox{CB}_{\alpha,n,\Measures}$ is less conservative than $\mbox{CB}_{\alpha,n,AS}$.
The main advantage of $\mbox{CB}_{\alpha,n,\Measures}$ compared to $\mbox{CB}_{\alpha,n,AS}$ is the computational gain that is achieved because of two factors: (i) using only linear and convex quadratic programs; (ii) no need to use multi-start procedures for global optimization of non-convex programs. Other alternative procedures like KMS and BCS would have additional burden of computing simulation-based critical values and are expected to be much slower. Note that the computational cost does not depend on whether the design is regular or not, so Figure (ref) compares the average computation time as a function of dimension $d$ on a modern multi-core laptop.\footnote{All simulations are using 2023 Macbook Pro with M2 Max CPU (12 cores) and 96 GB of RAM. The EAM algorithm for $\mbox{CB}_{\alpha,n,AS}$ takes advantage of all 12 cores. } The computational time for the delta-method for regularized support functions grows very slowly with dimension $d$; the average time for $d=100$ is about 2 seconds. In contrast, $\mbox{CB}_{\alpha,n,AS}$ is already nearly 1000 times slower for $d=21$.
This paper demonstrated that the regularization approach provides a fast way to construct point-wise and uniform CSs for a $\theta_{1}$ that is comparable to or shorter than those of the existing literature. Monte Carlo simulations showed that the proposed CSs have good finite sample coverage properties. The computational benefits of the new approach are particularly prominent if the dimension of $\theta$ is large. The regularization framework can be extended in a number of ways to allow for overidentification and joint inference. The proposed approach is attractive in applications such as a linear model with an interval-valued outcome variable and a large number of regressors and in problems with parameters represented as intersection bounds.
Focus on the affine inequalities simplifies the large sample analysis. However, there are many interesting applications that characterize the identified set for the structural parameters using non-linear moment conditions, in particular, among the structural models of the industrial organization pakes2015moment. Analysis of such non-linear moment inequalities goes beyond the scope of the current study, but would be a promising direction of future research.