Asymptotics of selective inference

Introduction

Selective inference is a recent research topic that studies valid inference after a statistical model is suggested by the data Fithian et al. (2014); Lee et al. (2013); Taylor et al. (2014, 2013). Classical inference tools break down at this point as the data used for the hypothesis test is allowed to be the data used to suggest the hypothesis. Specifically, instead of being given a priori, the hypothesis to test is dependent on the data, thus random. Formally, denoted by $\mathcal{E}^{*}=\mathcal{E}^{*}(y,X)$ is the model selection procedure, which generates a set of hypotheses to test, or perhaps parameters for which to form intervals. It is useful to think of $\mathcal{E}^{*}$ as a point process with values in ${\cal S}$, where ${\cal S}$ is some collection of questions of possible interest. Consider the following example,

where $e_{j}$ is the unit vector with only the $j$-th entry being $1$. Such functionals $\beta_{j,E}$ is essentially the best linear coefficients within the model consisting of only variables in $E$. Then the collection of possily interesting questions are

The data $(y,X)$ will then suggest a subset of interesting variables $E$, and $\mathcal{E}^{*}(y,X)$ designates the target for inference to be $\{\beta_{j,E},~{}j\in E\}$, the best linear coefficient within a model consisting of only the variables in $E$.

By inverting such tests, Lee et al. (2013) can also construct valid confidence intervals for $\beta_{j,E}$.

It is of course worth noticing that either the hypothesis $H_{0j}$ or the parameters $\beta_{j,E}$ are random as $E$ is suggested by the data. So the “Type-I error” (1) is not the classical Type-I error definition where the hypotheses are given a priori. Such inference framework is first considered in Berk et al. (2013), and we leave the philosophical discussions of such approach to Fithian et al. (2014).

Tibshirani et al. (2015) also considers uniform convergence of the statistics proposed by Taylor et al. (2014), but focuses mainly on the low dimensional case. In the high dimensional case, they have a negative result on the uniform convergence of the pivot. In this paper, we instead focus on the high dimensional case and state the conditions in which the pivot will converge. More specifically, $n$ is allowed to be of a logarithmic factor of the dimension $p$ for two common procedures introduced in Section 4.

In the works of Belloni et al. (2012); Meinshausen et al. (2012); Zhang & Zhang (2014); Javanmard & Montanari (2015), the authors proposed various ways of constructing confidence regions for the underlying parameters in the high-dimensional setting. One major difference between these works and our framework is that they try to achieve full model inference without using the data to choose a hypothesis. The advantage of such approach is robustness. But in the high-dimensional setting, with tens of thousands of potential variables, it is natural to use the data to select hypotheses of interest and perform valid inference only for those hypotheses. In addition, some of the full model inference works require conditions of linear underlying model Meinshausen et al. (2012); Javanmard & Montanari (2015) which the framework of selective inference does not require. For more philosophical discussions on the comparisons of the two approaches, see Fithian et al. (2014).

2 Organization of the paper

In Section 2, we formally introduce the methods for selective inference with certain model selection procedures, which we call affine selection procedures. In Section 3, we state the main theorem that will allow asymptotically valid inference. In Section 4, we will illustrate the applications of our results to two selective inference problems, selective inference after solving the LASSO at a fixed $\lambda$, and the covariance test for testing the global null in generalized linear models. We collect all the proofs in Section 5 and dicuss the directions of future research in Section 6.

Selective inference with affine selection procedures

We call $\mathcal{E}^{*}$ an affine selection procedure, if the selection event can be written as an affine set in the first argument of $\mathcal{E}^{*}$. Formally, $\mathcal{E}^{*}$ is an affine selection procedure if for each potential model to be selected $\mathcal{E}\in{\cal S}$,

The works of Lee et al. (2013); Lockhart et al. (2013); Taylor et al. (2014, 2013) have constructed valid p-values when the family $G$ is the Gaussian family. Formally, the pivotal function depends on the following quantities,

which is the CDF of the univariate Gaussian law $N(m,\sigma^{2})$ truncated to the interval $[a,b]$.

2 A pivotal quantity with Gaussian errors

Theorem 1 provides the construction of a pivotal function when the data is normally distributed and $\mathcal{E}^{*}$ is an affine selection procedure. We denote the response variables to be ${\cal Y}$ when $G$ is the Gaussian family to distinguish it from $y$ where $G$ is a more general location-scale family. Note all distributions in this paper are conditional on $X$, that is the law we consider are either ${\cal L}({\cal Y}|X)$ or ${\cal L}(y|X)$. All random variables have access to $X$ as if it were a constant.

where $\mathcal{E}^{*}(z,X)=\mathcal{E}\iff A(\mathcal{E},X)z\leq b(\mathcal{E},X)$ and

Moreover, marginalizing over the selection procedure $\mathcal{E}^{*}$, we have the following

The significance of Theorem 1 is that assuming the diagonal matrix $\Sigma$ is known, the only unknown parameter for the pivotal quantity (10) is $\eta^{T}\mu$. To test the hypothesis $H_{0}:\eta^{T}\mu=0$, we just need to plug in the value and then compute (10), which then can be used as a p-value to accept/reject the hypothesis. For example, if we take

where $e_{j}$ is the unit vector with only the $j$-th entry being $1$, $\eta^{T}\mu=\beta_{j,E}$. The quantity in (10) is pivotal and can be used to test the hypothesis $H_{0j}:\beta_{j,E}=0$, and control the “Type-I errpr” (1). Since $X$ is fixed, we use the shorthand

Asymptotics with non-Gaussian error

The main approach is to compare the distribution of the pivots (10) under the distribution ${\cal L}(y|X)$ with that under Gaussian distribution ${\cal L}({\cal Y}|X)$. In the latter case, the exact distribution is derived in Theorem 1. In the following, we establish the conditions where the above two distributions are comparable.

Note the pivotal quantity in (10) depends on $y$ either through the linear functions $\eta^{T}y$ or the maximum/minimum of linear functions $L_{\mathcal{E}^{*}}(y)$, $U_{\mathcal{E}^{*}}(y)$. In approximating the exact Gaussian theory with asymptotic results a quantity analogous to a Lipschitz constant (in $y$) will be necessary, expressing the changes in $\eta^{T}y$ as well as the upper and lower bounds $L_{\mathcal{E}^{*}}$ and $U_{\mathcal{E}^{*}}$. This, in some sense, describes the influence each $y_{i}$ can have on the pivotal quantity (10).

The quantity $M(\mathcal{E}^{*},\eta)$ measures the maximal influence any $y_{i}$ has on a smoothed version of the triple $(\eta(\mathcal{E}^{*})^{T}y,L_{\mathcal{E}^{*}}(y),U_{\mathcal{E}^{*}}(y))$. As $M(\mathcal{E}^{*},\eta)$ and $r(\mathcal{E}^{*})$ are critical in bounding the difference between ${\cal L}(y|X)$ and ${\cal L}({\cal Y}|X)$, it is important to get a sense of their size. Typically $r(\mathcal{E}^{*})$ is less than $p$, and we discuss the typical size of $M(\mathcal{E}^{*},\eta)$ through the following simple example:

where $e_{j}$ is the unit vector with only the $j$-th coordinate being $1$. Since we normalize the columns, it is not hard to verify $(X_{E}^{T}X_{E})^{-1}=O_{p}(1)$, and $\max_{ij}(X_{ij})=O_{p}(n^{-1/2})$, thus if the selected variables set always satisfies $|E|\ll n$, $\eta=O_{p}(n^{-1/2})$. Therefore $M(\mathcal{E}^{*},\eta)=O_{p}(n^{-1/2})$.

This is a very simple example which does not involve selection. In reality we will some meaningful selection procedure that uses the data so $M(\mathcal{E}^{*},\eta)$ would involve $A(\mathcal{E}^{*})$ and $b(\mathcal{E}^{*})$ as well. However, we will see through examples in Section 4 that it is still reasonable to assume $M(\mathcal{E}^{*},\eta)=O(n^{-1/2})$.

The following theorem compares the distribution of $(\eta(\mathcal{E}^{*})^{T}y,L_{\mathcal{E}^{*}}(y),U_{\mathcal{E}^{*}}(y))$ under ${\cal L}(y|X)$ and its Gaussian counterpart.

${\cal L}(y|X)$ has independent entries with mean vector $\mu$ and covariance matrix variance $\Sigma$ and finite third moments bounded by $\gamma$;

there exists $N=N(M(\mathcal{E}^{*},\eta),|{\cal S}|,r(\mathcal{E}^{*}),W)$, such that the following holds for $n,p\geq N$,

where $C(W,\gamma)$ is a constant depending only on the derivatives of $W$ and $\gamma$, and $\eta(\mathcal{E}^{*})$ is $\eta(\mathcal{E}^{*}(y))$ or $\eta(\mathcal{E}^{*}({\cal Y}))$ depending on the context.

As it is reasonable to assume $M(\mathcal{E}^{*},\eta)=O(n^{-1/2})$, it is reasonable to assume the RHS of (14) goes to zero. Thus the distribution of $(\eta(\mathcal{E}^{*})^{T}y,L_{\mathcal{E}^{*}}(y),U_{\mathcal{E}^{*}}(y))$ is close to that of $(\eta(\mathcal{E}^{*})^{T}{\cal Y},L_{\mathcal{E}^{*}}({\cal Y}),U_{\mathcal{E}^{*}}({\cal Y}))$. In the following, we discuss the conditions under which the pivotal quantity (10) converges.

2 Smoothness of the pivot

Note the bound in (14) also depends on $C(W,\gamma)$, the derivatives of $W$. Thus besides the influence of each $y_{i}$ on (10), it is also necessary to control the smoothness of the (10). In particular, the pivot in (10) takes the form of a truncated Gaussian cdf. Moreover, the smoothness (derivatives) of the truncated Gaussian cdf $F(x;\sigma^{2},m,a,b)$ can depend heavily on the truncation interval $[a,b]$. More specifically, a lower bound on the denominator of $F(x;\sigma^{2},m,a,b)$ puts some constraints on the width of the interval $[a,b]$ as well as its distance to the origin. In our context, $a,b$ corresponds to the upper and lower bounds appearing in (10). Formally, we assume the following assumption:

The first two conditions in (15) puts a lower bound on the width of the truncation interval $(L_{\mathcal{E}^{*}}(y_{n}),U_{\mathcal{E}^{*}}(y_{n}))$. The last two conditions makes sure the truncation will not appear too far from the origin and thus we will have reasonable behavior in the tail. $\delta_{n}$ is the rate at which the truncation interval will shrink (or the distance of the truncation interval to the origin). This rate will appear in the RHS of (14) and thus we impose a condition on $(\delta_{n},M(\mathcal{E}^{*}_{n},\eta_{n}),r(\mathcal{E}^{*}_{n}),|{\cal S}_{n}|)$ to ensure the convergence of the pivot (10).

3 Main result

Suppose we have a sequence of $y_{n}$ generated as above with means $\mu_{n}=\mu(X_{n})$, and variances $\Sigma_{n}=\Sigma(X_{n})$ and have finite third moments. We also assume Assumption 1 is satisfied with a sequence of $\delta_{n}$. Furthermore, let $\mathcal{E}^{*}_{n}$ be a sequence of affine selection procedures, $\eta_{n}=\eta(\mathcal{E}^{*}_{n})$, and the corresponding $M(\mathcal{E}^{*}_{n},\eta_{n})$, $r(\mathcal{E}^{*}_{n})$ and ${\cal S}_{n}$ properly defined as in Section 3.1. Then if

where $P(x;\sigma^{2},m,a,b)=2\min(F(x;\sigma^{2},m,a,b),1-F(x;\sigma^{2},m,a,b))$ is the two-sided pivot.

In the following section, we apply Theorem 3 to different selection procedures.

Examples

where $\sigma$ is known and the distribution $G$ has finite third moments, but is not necessarily Gaussian.

Tibshirani (1996) proposed the now famous LASSO. We get a sparse solution $\hat{\beta}$ by solving

where $\lambda>0$ is the fixed regularization parameter. We choose $\lambda$ as in Negahban et al. (2012). If we normalize the columns of $X$ to have norm $1$, Negahban et al. (2012) chooses $\lambda$ to be $O(\sqrt{\log p})$.

As in Lee et al. (2013), we solve (18) and get a solution $\hat{\beta}$. Now we consider the selection procedure based on $(E,z_{E})$, where

where $\hat{\beta}_{E}$ is $\hat{\beta}$ restricted to the active set $E$. Note this is different from the selection procedure based only on $E$ but is closely related, for detailed discussion see Lee et al. (2013). The authors in Lee et al. (2013) proved such selection procedure is equivalent to the affine constraints $A(E,z_{E})y\leq b(E,z_{E})$, where

To test the hypothesis $H_{0j}:\beta_{j,E}=0$ for any $j\in E$, we choose $\eta$ to be as in (11).

In this case, a simple calculation will put the number of possible states at $|{\cal S}|=2^{p}$, which will cause the bound in (14) to blow up when $p>n$. However, the choice of $\lambda=O(\sqrt{\log p})$ (Negahban et al., 2012) together with other conditions will ensure $|{\cal S}|$ is polynomial in $p$ with high probability.

1.2 Number of states |𝒮|𝒮|{\cal S}| for λ=O​(log⁡p)𝜆𝑂𝑝\lambda=O(\sqrt{\log p})

Suppose $X$ is column standardized to be mean zero and norm $1$, we first introduce the restricted strong convexity condition for matrix $X$.

Now we define the assumptions needed to ensure $|{\cal S}|$ is polynomial in $p$ with high probability.

$\epsilon_{i}$ are sub-Gaussian errors with known variance $\sigma^{2}$.

Following Negahban et al. (2012), Lemma 1 shows with the above assumptions, the effective size of $|{\cal S}|$ is polynomial in $p$ with high probability.

With Assumptions 2-4, if we solve (18) with $\lambda\geq 4\sigma\sqrt{\log p}$ and get active set $E$, then with probability at least $1-c_{1}\exp(-c_{1}\lambda^{2})$,

where $c_{1}$ is some constant that depends on $m$ and the subgaussian constant of the error $\epsilon$. Thus, with probability $1-c_{1}\exp(-c_{1}\lambda^{2})$,

The proof of Lemma 1 is deferred to the appendix. Having controlled $|{\cal S}|$, now we need to get a bound for the influences.

Assume we have normalized the design matrix $X$ columnwise so that each column has norm $1$. We further assume the following assumption on $X$,

Suppose we solve problem (18) with $X$ and get the active set $E$. Let $\phi_{\text{min}}$ be the smallest eigenvalue for submatrices of size less than $n\times|E|$, more specifically,

If we normalize the columns of $X$ to have norm $1$ and choose $\lambda=O(\sqrt{\log p})$ in (18) as in Negahban et al. (2012). Then we assume Assumption 1 is satisfied with $\delta_{n}=O((\sqrt{\log p_{n}})^{-1-\kappa})$, for any small $\kappa>0$.

To avoid long passage and stay focused on the main topic, we illustrate that Assumption 1 is satisfied with such $\delta_{n}$’s in the following simplified setup. However, the approach can be adapted to include more general cases.

Suppose Assumption 2-4 are satisfied. We further assume that $z_{E}=1$ and the matrix $(X_{E}^{T}X_{E})^{-1}$ is equicorrelated, i.e.

Then if $\|\beta_{n}^{0}\|_{\infty}=O(\lambda_{n})$, Assumption 1 is satisfied with $\delta_{n}=O(\lambda_{n}^{-1-\kappa})$, for any $\kappa>0$.

Note if we do not assume $z_{E}=1$, the last two conditions in Assumption 1 are still satisfied with $\delta_{n}=O(\lambda_{n}^{-1-\kappa})$ and the first two conditions can be satisfied with further assumptions. But we do not pursue the technical details here.

1.5 Convergence of selective tests in the Lasso problems

Suppose we solve the Lasso problem (18) and get active set $E$, and want to test the hypotheses $H_{0j}:\beta_{j,E}=0$, we can simply take $\eta$ to be as in (11). Now we summarize the above results and apply Theorem 3 to get the following corollary

Suppose we solve the Lasso problem (18) with $\lambda_{n}=4\sigma\sqrt{\log p_{n}}$, and Assumption 1-5 are satisfied and the $\delta_{n}$’s in Assumption 1 is chosen as $(\log p_{n})^{-\frac{1}{2}-\frac{1}{2}\kappa}$. If we further assume $\max|X_{ij}|=O(n^{-\frac{1}{2}})$, $\|\beta^{0}\|_{\infty}=O(\sqrt{\log p_{n}})$, and there exists $\kappa>0$ such that

One of the first results in selective inference was the covariance test Lockhart et al. (2013) which provided an asymptotic limiting distribution for the first step of the Lasso or LARS path. An exact version of this test under Gaussian errors was described in Taylor et al. (2013).

In the following, we generalize the covariance test for generalized linear models. Suppose ${\cal L}(y|x)$ is in an exponential family. More specifically,

where $\beta^{0}$ and $x$ are $p$-dimensional vectors and $\Lambda(\eta)$ is the cumulant generating function of the distribution.

The covariance test for the global null $H_{0}:\beta^{0}=0$ is based upon the the first knot on the solution path of (21), which is largest score statistic (in absolute values) at $\beta^{0}=0$,

The variable to achieve the maximum in (22) will be the first variable to enter the solution path.

The covariance test can also be viewed as a test for the coefficient with (potentially) the largest absolute values. A guess for such variable is the first variable to enter the solution path of (21). In other words, covariance tests select the target of inference based on $(j^{*},s^{*})$, where

and the test statistic is $\lambda_{1}=|x^{T}_{j^{*}}(y-\nabla\Lambda(0))|$.

The selection procedure is based on $(j^{*},s^{*})$ defined in (23), it is easy to see that it is equivalent to

Writing in the form of $A(j^{*},s^{*})y\leq b(j^{*},s^{*})$, we have

We notice that $\lambda_{1}=s^{*}x^{T}_{j^{*}}(y-\nabla\Lambda(0))$. Thus to test the global $H_{0}:\beta^{0}=0$, we simply take

The challenge in establishing a result for the covariance test for GLM is the lack of Gaussianity in the data distribution. The tools we develop in this paper, however, can circumvent this. But we first need to establish the resulting pivot which we can use to test the hypothesis $H_{0}:\beta^{0}=0$. Note that $y_{i}\mid x_{i}\overset{\text{ind}}{\sim}G(\mu(x_{i}),\sigma(x_{i})^{2})$, thus if $G$ were normal distribution, we will have an exact pivot by applying Theorem 1. This result is also given in Taylor et al. (2013). Formally, we have the following corollary.

Corollary 1 gives a pivot (24) which we can use to test the global null $H_{0}:\beta^{0}=0$ and control the “Type-I error” (1). In practice, we often normalized the columns of the design matrix $X$. In addition we may assume the observations $y_{i}$’s are independently distributed with the same marginal variance, i.e. $\Sigma=\sigma^{2}\text{I}$, then $U_{(j^{*},s^{*})}=\infty$ and $L_{(j^{*},s^{*})}$ simplifies to the second knot in the solution path $\lambda_{2}$, thus we have:

2.2 The conditions for the pivot to converge

Since $j^{*}\in\{1,\dots,p\}$, and $s^{*}\in\{-1,1\}$, the number of possible states $|{\cal S}|$ are naturally bounded by $2p$ and $r(\mathcal{E}^{*})=2p$. We assume $\Sigma=\sigma^{2}\text{I}$, and $X$ are normalized columnwise to have norm $1$. We first introduce the following condition on the design matrix $X$, which states that any two columns of $X$ cannot be too correlated.

Under Assumption 6, it is not hard to verify

Now we need to pick the $\delta_{n}$’s such that Assumption 1 holds. In particular, we choose $\delta_{n}=(\sqrt{\log p_{n}})^{-1-\kappa}$, for some $\kappa>0$. Now if we apply Theorem 3, we have the following result,

Suppose $y|X$ is generated independently coordinate-wise through the distribution in (20) with the same marginal variance. Assume the columns of $X$ have norm $1$, Assumption 6 is satisfied and $\max_{ij}|X_{ij}|=O(n^{-\frac{1}{2}})$. Then if

Proof of the theorems

Without loss of generality, we restrict our interest to the case $\mu=\mu(X)=0,\Sigma=\Sigma(X)=I$. This is possible since any affine selection procedure $\mathcal{E}^{*}$ applied to data with mean $\mu(X)\neq 0$ is equivalent to a centered affine selection procedure $\mathcal{E}^{*,0}$ applied to the centered data. Specifically, the linear part of $\mathcal{E}^{*,0}$ is the same as $\mathcal{E}^{*}$ and the offsets are related by

Further, note that all quantities in the theorems above are independent of $b$. Scaling of the errors is handled in a similar fashion.

Analogous to the proof in Lee et al. (2013), we prove Theorem 1.

To lighten notations, we suppress all dependencies on $X$ as it is assumed known. Note that $\{\mathcal{E}^{*}({\cal Y})=\mathcal{E}\}=\{A(\mathcal{E}){\cal Y}\leq b(\mathcal{E})\}$. Thus

Dropping the dependence on $\mathcal{E}$ for the moment,

In other words, $\{A{\cal Y}\leq b\}=\{A(\mathcal{E}){\cal Y}\leq b(\mathcal{E})\}=\{L_{\mathcal{E}}({\cal Y})\leq\eta^{T}{\cal Y}\leq U_{\mathcal{E}}({\cal Y})\},$ and

Note also from the derivation above that $(L_{\mathcal{E}}({\cal Y}),U_{\mathcal{E}}({\cal Y}))$ is independent of $\eta^{T}{\cal Y}$ for each $\mathcal{E}$. Thus if we condition on $\mathcal{E}^{*}$, $U_{\mathcal{E}^{*}}({\cal Y})$ and $L_{\mathcal{E}^{*}}({\cal Y})$, $\eta(\mathcal{E}^{*})^{T}{\cal Y}$ is distributed as a Gaussian r.v. with mean and variance $\|\eta(\mathcal{E}^{*})\|^{2}$ truncated at $U_{\mathcal{E}^{*}}$ and $L_{\mathcal{E}^{*}}$. Therefore,

Considering that conditional on $\mathcal{E}^{*}$, $\eta(\mathcal{E}^{*})^{T}{\cal Y}$ is independent of $U_{\mathcal{E}^{*}}$ and $L_{\mathcal{E}^{*}}$, we have (7). ∎

2 Smoothing the maxima of affine functions

In the proof of Theorem 2 and the related lemmas and corollaries, a technique developed by Chatterjee (2005) is frequently used. Roughly speaking, we want to study convergence of functions like $L_{\mathcal{E}}$ and $U_{\mathcal{E}}$ which can be expressed as maxima or minima of affine functions. These non-smooth functions are replaced by a smoothed surrogate at the cost of a factor appearing in their derivatives depending on the smoothing parameter.

Specifically, we are interested in how this smoothing affects the following quantities.

For any finite collection ${\cal F}$ of functions define

Now we define the smoothed maxima operator.

is a finite collection of thrice differentiable functions $v_{j}$’s. The maximum is taken coordinate-wise.

We define the smoothed maxima operator with parameter $\beta$ as

where the operators $\log$ and $\exp$ are applied coordinate-wise.

Suppose the range of $f,\Gamma(f,\beta)$, denoted as $\mathcal{R}(f),\mathcal{R}(\Gamma(f,\beta))\subseteq\mathcal{D}$ and let $h=g\circ f$, $h_{\beta}=g\circ\Gamma(f,\beta)$, then Lemma 5 gives a bound on $\|h-h_{\beta}\|_{\infty}$ and $\lambda_{3}(h_{\beta})$.

Assume the same notations as above, $s=|\mathcal{F}|$, then for $\beta\geq 1$

The proof of Lemma 5 will refer to the following lemma whose proof we leave in the Appendix.

We take $h=g\circ f$, and $h_{\beta}=g\circ\Gamma(f,\beta)$,

where the $\infty$ norm is the element-wise maximum absolute value. Thus we proved (28). Now let $f=(f_{1},f_{2},f_{3})$ and $v_{j}=(v_{1j},v_{2j},v_{3j})$, and define

Theorem 1.3 in Chatterjee (2005) proved that

Note \lambda_{3}\big{(}\Gamma(f,\beta)\big{)}=\max_{i=1,2,3}\lambda_{3}\big{(}\Gamma(f_{i},\beta)\big{)}, and that $\lambda_{3}({\cal F})=\max_{i=1,2,3}\lambda_{3}({\cal F}_{i})$, thus

This combined with Lemma 6 proves (29). ∎

3 Proof of Theorem 2

To prove Theorem 2, we first prove the following lemma. Recall our reduction to the standard Gaussian $N(0,I)$ in the beginning of Section 5.1. Lemma 7 is a simple adaption of Lindberg’s proof of the CLT.

The proof proceeds by following the Lindberg proof of the CLT for $h$. Define

We can break the absolute difference of the two expectations into $n$ parts,

where $|R^{l}|\leq\frac{1}{6}\|\partial_{l}^{3}h\|_{\infty}|y_{l}|^{3}$, $|T^{l}|\leq\frac{1}{6}\|\partial_{l}^{3}h\|_{\infty}|{\cal Y}_{l}|^{3}$. Moreover, because $y_{l}$’s and ${\cal Y}_{l}$’s are independent, $W^{l}$ is independent of both $y_{l}$ and ${\cal Y}_{l}$. Continuing, we see the first and second order differences cancel out,

Note that since $\{A(\mathcal{E}_{i},X)y\leq b(\mathcal{E}_{i})\},1\leq i\leq|{\cal S}|$ are disjoint and for any state $\mathcal{E}$

If we knew the above quantity was smooth with respect to the data, we can apply Lemma 7 directly. However, there are two non smooth expressions above: the maximum function over the states and in $L_{\mathcal{E}_{i}}$ and $U_{\mathcal{E}_{i}}$. We smooth each and optimize over the smoothing parameter.

where $\mathcal{F}_{L},\mathcal{F}_{U}$ are the collections of affine functions

We define the smoothing parameter $\beta=1/\delta$, for some $0<\delta<1$. Then

Next, we smooth the maximum over states. Define

We also define the smoothed maxima for $\max_{1\leq i\leq|S|}W_{\mathcal{E}_{i}}(z)$,

From (33) in Lemma 7 together with (40) and (41), we have

Notice that for the last inequality to hold, we require $\delta\leq 1$. But the optimal $\delta^{5}=O(nM(\mathcal{E}^{*},\eta)^{3}/[\log|{\cal S}|+\log r(\mathcal{E}^{*})])$, which will go to since the numerator shrinks to while the denominator goes to $\infty$ as $n,p\to\infty$. Therefore, the inequality holds.

4 Proof of Theorem 3

Now let’s turn to the proof of our main result, Theorem 3,

For the convenience of notation, we denote $P(x;\sigma^{2},m,a,b)$ by $P(x;a,b)$, omitting $\sigma^{2},m$ in the following proof. Define

We claim that for any small $\frac{1}{4}>\delta>0$, we can find a thrice differentiable function $\widetilde{P}_{\delta}$ such that

where $K_{1}$ and $K_{3}$ are defined in Corollary 3.

On the other hand, we plug in $\Psi\circ\widetilde{P}_{\delta}$ as the $W$ in Theorem 2, then for any sequence of $\widetilde{P}_{\delta_{n}}$,

If we choose a subsequence $\delta_{n}\rightarrow 0$, such that the right hand side of (44) goes to zero, then

Discussion

This work proves a generic framework in which asymptotic results hold for many selective inference problems. It is, however, not directly applicable to some other procedures. Further work may include,

Fixed $\lambda$ for generalized linear model.

Our work derives a theory for inference after the affine selection procedure. However, inference for a fixed $\lambda$ for the generalized linear regression is not an affine selection procedure. A plausible solution will be to approximate the loss function of GLM by a quadratic form and bound the difference between the quadratic form and the GLM loss function. However, this is still an open question.

Apply the result to nonparametric problems.

It is a big step to remove the Gaussian assumptions required by Lee et al. (2013) which restricts our attention to Gaussian families. Without the Gaussian constraints, we can consider some exponential families and potentially some nonparametric problems as well.

Acknowledgements We thank Jason Lee for the proof of Lemma 1 provides a polynomial bounds on the number of selection states. We also thank Will Fithian and Rob Tibshirani for discussions on potential applications of our result. We also thank the anonymous reviewer who has read our paper so carefully and provide constructive advice for reorganization.

References

Appendix A Proof of Lemma 6

Using the chain rules, we have the second derivatives with respect to $x_{l},~{}l=1,2,\dots,n$ as

and the third derivatives with respect to $x_{l},~{}l=1,2,\dots,n$ as

For $r=1$, the conclusion is obviously true with the constant $c=3$. For $r=2$, the terms involving the partial derivatives of $f$ are

Note the first type of terms are bounded by $\lambda_{2}(f)^{1/2}\cdot\lambda_{2}(f)^{1/2}$ and the second type of terms are bounded by $\lambda_{2}(f)$. If we take $c=12$, $|\partial_{l}^{2}g\circ f|\leq cC_{2}(g)\lambda_{2}(f)$. On the other hand,

For $r=3$, an equation similar to (48) will give us $|\partial_{l}g\circ f|^{3}\leq 27C_{3}(g)\lambda_{3}(f)$. Meanwhile,

For the third derivatives $\partial_{l}^{3}g\circ f$, the terms that involve $f$ are,

which are all bounded by $\lambda_{3}(f)$ and therefore $\lambda_{3}(g\circ f)\leq 57C_{3}(g)\lambda_{3}(f)$. In summary, we can take $c=57$. ∎

Appendix B Existence of smooth approximation P~~𝑃\widetilde{P}

We prove the existence of such functions as claimed in the proof of Theorem 3. Define $P(x,a,b)=P(x;\sigma^{2},m,a,b)$. We first prove the following lemma,

Then, on $D(\delta)$ for any $\delta<1/4$ we have

on $D(\delta)$ for $\delta<1/4$ as well as

For $\delta<1/4$ and any multi-index $\alpha=(\alpha_{1},\alpha_{2},\alpha_{3})$ we have

We prove for $\alpha=(0,0,1)$, and similar proofs can be extend to other multi-index $\alpha$ as well. Since $P(x,a,b)=2\min(F(x;a,b),1-F(x;a,b))$, we only need to prove for $F(x;a,b)$.

Finally, we put the lemma and the corollary together and prove the following lemma.

There exists a thrice differentible approximation $\widetilde{P}$ to $P$ that satisfies,

$\widetilde{P}(x,a,b)$ is supported on $\{(x,a,b):a\leq x\leq b\}$,

$C_{3}(\widetilde{P})\leq K_{3}\dfrac{1}{\delta^{6}}$ on the set $D(\delta)$,

$\left\|{\widetilde{P}}\right\|_{\infty}\leq(K_{1}+1)\delta$ on the set $D(\delta)$.

Let $P_{\delta}$ be the smoothed version of $P$ for the minimum function in $P=2\min(F,1-F)$, and $\left\|{P_{\delta}-P}\right\|_{\infty}\leq\delta$. Let $\widetilde{P}_{\delta}=P_{\delta}I_{\delta^{2}}(x,a,b)$, where $I_{\delta^{2}}(x,a,b)$ is the smoothed version of the indicator function on $\{a\leq x\leq b\}$. $I_{\delta^{2}}(x,a,b)$ also satifies the condition that

$I_{\delta^{2}}(x,a,b)$ also satisfies $C_{3}(I_{\delta^{2}})\leq\dfrac{1}{\delta^{6}}$, for some universal constant $C$. Thus it is not hard to verify that $C_{3}(\widetilde{P}_{\delta})\leq K_{3}\frac{1}{\delta^{6}}$.

Appendix C LASSO related proofs

We first introduce the following Lemma in Negahban et al. (2012).

If we assume the same assumptions and notations as in Lemma 1, then with probability at least $1-c_{1}\exp(-c_{1}\lambda^{2})$, the following two inequalities hold:

where $k$ is the number of nonzero entries in $\beta^{0}$ and $\hat{\beta}$ is the solution to (18)

According to Lemma 10, we assume both (49) and (50) hold. This happens with probability $1-c_{1}\exp(-c_{1}\lambda^{2})$. For any $j$,

Combining the two inequalities, we have that

holds with probability $1-c_{1}\exp(-c_{1}\lambda^{2})$. ∎

C.2 Proof of Lemma 2

Note $X_{E}^{\dagger}=(X_{E}^{T}X_{E})^{-1}X_{E}^{T}$. According to the assumption assumed in Lemma 2, $\phi_{\text{min}}>\nu$. Thus for any possible active set $E$,

The above result can be easily obtained using Singular Value Decomposition on $X_{E}$. Therefore, we have

C.3 Proof of Lemma 3

Without loss of generality, we assume $\beta^{0}=0$. We first see that for any fixed $E$, and $\eta_{n}$ chosen as in (11), the upper and lower bound simplies to

Note that the first two equations of (15) are automatically satisfied in this case. Without loss of generality, we assume $L_{\mathcal{E}^{*}}>0$, and noticing $L_{\mathcal{E}^{*}}\leq\max_{\mathcal{E}}L_{\mathcal{E}}$, we have

Since $\max_{\mathcal{E}}L_{\mathcal{E}}(y_{n})$ is the maximum of at most $p^{cK}$ sub-Gaussian variables, thus the RHS is bounded by $O(e^{-\lambda_{n}^{\kappa}})=O(p^{-\kappa})$, which goes to . ∎

C.4 Proof of Lemma 4

with probability at least $1-c_{1}\exp(-c_{1}\lambda_{n}^{2})$.

We modify the selection procedure $\mathcal{E}^{*}_{n}$ on the small probability event. More specifically, we define $\widetilde{\mathcal{E}}^{*}_{n}$ as

It is easy to see that $\widetilde{\mathcal{E}}^{*}_{n}$ is also an affine selection procedure. which differs from $\mathcal{E}^{*}_{n}$ only on the event $\{|E_{n}|>cK\}$. Thus the pivots formed with $\mathcal{E}^{*}_{n}$ and $\widetilde{\mathcal{E}}^{*}_{n}$ converge in probability,

Therefore, we only need to consider the asymptotic distribution of the pivot with $\widetilde{\mathcal{E}}^{*}_{n}$ as the selection procedure. Note that for $\widetilde{\mathcal{E}}^{*}_{n}$,

Now with our choice of $\delta_{n}$’s, it is easy to rewrite the condition in Theorem 3 as