Selective inference with a randomized response

Introduction

Tukey (1980) promoted the use of exploratory data analysis to examine the data and possibly formulate hypotheses for further investigation. Nowadays, many statistical learning methods allow us to perform these exploratory data analyses, based on which we can posit a model on the data generating distribution. Since this model is not given a priori, classical statistical inference will not provide valid tests that control the Type-I errors.

Selective inference seeks to address this problem, see Lee et al. (2013a); Lockhart et al. (2014); Lee & Taylor (2014); Fithian et al. (2014). Loosely speaking, there are two stages in selective inference. The first is the selection stage that explores the data and formulates a plausible model for the data distribution. Then we enter the inference stage that seeks to provide valid inference under the selected model which is proposed after inspecting the data. Inference under different models have been studied, notably the Gaussian families Lee et al. (2013a); Tian et al. (2015); Lee & Taylor (2014) as well as other exponential families Fithian et al. (2014).

In this work, we consider selective inference in a general setting that include nonparametric settings. In addition, we introduced the use of randomized response in model selection. A most common example of randomized model selection is probably the practice of data splitting. Assuming independent sampling, we can divide the data into two subsets, using the first for model selection and the second subset for inference. Though not emphasized, this split is often random. Hence, data splitting can be thought of as a special case of randomized model selection. To motivate the use of randomized selection and introduce the inference problem that ensues, we consider the following example.

Publication bias, (also called the “file drawer effect” by Rosenthal (1979)) is a bias introduced to scientific literature by failure to report negative or non-confirmatory results. We formulate the problem in the simple example below.

Suppose that we are interested in discovering positive effects and would only report the sample mean if it survives the file drawer effect, i.e.

Then what is the “correct” $p$-value to report for an observation $\bar{X}_{n,obs}$ that exceeds the threshold?

where $\Phi$ is the CDF of an $N(0,1)$ random variable. Therefore, we get a pivotal quantity

for the $\bar{X}_{n}$’s surviving the file drawer effect (1).

Randomized selection circumvents this problem. In the following, we propose a randomized version of the “file drawer problem”.

We assume the same setup of a triangular array of observations $X_{i,n}$ as in Example 1. But instead of reporting $\bar{X}_{n}$ when it survives the file drawer effect (1), we independently draw $\omega\sim G$, and only report $\bar{X}_{n}$ if

To compute the exact form of $P(t)$, we have to compute the convolution of $N(0,1)$ and $G$ which has explicit forms for many distributions $G$. Moreover, when $G$ is Logistic or Laplace distribution, we have

which leads to three scenarios for selection.

In this case, the dominant term for selection is $\sqrt{n}\mu_{n}$, and since we have a big positive effect, we would always report the sample mean $\bar{X}_{n}$ when $n$ is big. This corresponds to the selection event having probability tending to $1$ and the selective likelihood ratio goes to $1$ as well. In this case, there is very little selection bias, and the original law is a good approximation to the selective distribution for valid inference.

$\mu_{n}<-\delta<0$, for some $\delta>0$.

In this case, the dominant term is also $\sqrt{n}\mu_{n}$, but in the negative direction. As $n\to\infty$, the selection probability vanishes and the selective likelihood becomes degenerate. We almost never report the sample mean in this scenario, but in the rare event where we do, by no means can we use the original distribution for inference.

$-\delta<n^{1/2}\mu_{n}<\delta$, for some $\delta>0$.

This corresponds to local alternatives. In this case, the selective likelihood neither converges to $1$ or becomes degenerate. Rather, it becomes an indicator function of a half interval. Proper adjustment is needed for valid inference in this case.

It is in the second scenario that pivotal quantity (2) will not converge to $\textnormal{Unif}(0,1)$. Different distributions will have different behaviors in the tail. Since the conditioning event $n^{1/2}\bar{X}_{n}>2$ becomes a large-deviations event, we cannot expect it to behave like the normal distribution in the tail.

where $\bar{G}(t)=\int_{t}^{\infty}G(du)$ is the survival function of $G$. When $\mu_{n}<-\delta<0$ for some $\delta>0$, and $G$ is the Laplace or Logistic distribution so that $\bar{G}$ has an exponential tail, the dominant term $\exp(n^{1/2}\mu_{n})$ in both the numerator and the denominator will cancel out, making the selective likelihood ratio properly behaved in this difficult scenario.

It turns out that this selective likelihood ratio is fundamental to formalizing asymptotic properties of selective inference procedures. Its behavior determines not only the asymptotic convergence of the pivotal quantities like in (4), but also whether consistent estimation of the population parameters is possible with large samples.

Again in the negative mean scenario where $\mu_{n}<-\delta<0$, the sample mean $\bar{X}_{n}$ surviving the non-randomized “file drawer effect” cannot be a consistent estimator for the underlying means $\mu_{n}$ because it will always be positive. But if $\bar{X}_{n}$ is reported as in Example 2, it will be consistent for $\mu_{n}$ even if $\mu_{n}$ is negative and bounded away from . For detailed discussion, see Section 3.

In general, the behavior of the selective likelihood ratio can be used to study the asymptotic properties of selective inference procedures. We study consistent estimation and weak convergence for selective inference procedures in Section 3 and Section 5 respectively.

We are especially inspired by the field of differential privacy (c.f. Dwork et al. (2014) and references therein) to study the use of randomization in selective inference. Privatized algorithms purposely randomize reports from queries to a database in order to allow valid interactive data analysis. To our understanding, our results are the first results related to weak convergence in privatized algorithms, as most guarantees provided in the differentially private literature are consistency guarantees. Some other asymptotic results in selective inference have also been considered in Tibshirani et al. (2015); Tian & Taylor (2015), though these have a slightly different flavor in that they marginalize over choices of models.

We conclude this section with some more examples.

2 Linear regression

Randomized selection in this setting is a natural extension of these works. Fithian et al. (2014) proposed to use a subset of data for model selection, which yields a significant increase in power. In this work, we study general randomized selection procedures. Consider the following example.

Due to the sparsity of the solution of LASSO Tibshirani (1996)

3 Nonparametric selective inference

All the previous works on selective inference assume a parametric model like the Gaussian family or the exponential family. In this work, we allow selective inference in a non-parametric setting. Consider the following examples.

Suppose in a classification problem, we observe independent samples,

4 Outline of the paper

There are three main advantages of applying randomization for selective inference,

Consistent estimation under the selective distribution

Weak convergence of selective inference procedures

In the following sections, Section 2 gives the setup of selective inference and introduced selective likelihood ratio, which is the key for studying consistent estimation and weak convergence of selective inference procedures. Section 4 focuses on linear regression models with different randomization schemes, demonstrating the increase in power. Section 5 proposes an asymptotic test for the nonparametric settings. Theorem 9 proves that the central limit theorem holds under the selective distribution with mild conditions. Applications to the two examples in Section 1.3 are discussed. This is a result for fixed dimension $p$. Finally, Section 6 discusses the possibility of extending our work to the setting, when multiple selection procedures are performed on different randomizations of the original data. One application is selective inference after cross validation for the square-root LASSO Belloni et al. (2011).

Selective Likelihood Ratio

where ${\cal Q}$ is loosely defined as being made up of “potentially interesting statistical questions”.

Since we use the data to choose the model $M$, it is only fair to consider the conditional distribution for inference,

Therefore, we seek to control the selective Type-I error:

where $M$ is the selected family of distributions in the range of $\widehat{\cal Q}$ and $H_{0}\subset M$ is the null hypothesis. Selective intervals for parametric models $M$ can then be constructed by inverting such selective hypothesis tests, though only the one-parameter case has really been considered to date.

Similar to the selective inference we defined above, we seek to control the selective Type-I error,

Moreover, we also want to achieve good estimation, which makes

2 Selective likelihood ratio

with the same sufficient statistic $T(y)$ and natural parameters $\theta$.

Furthermore, to test $H_{0j}:\theta_{j}=0$, we consider the following law,

The first claim of the lemma is quite straight-forward using the relationship in (13). The second claim is a Lehmann–Scheffe (c.f. Chapter 4.4 in Lehmann (1986)) construction which was proposed in Fithian et al. (2014), to construct tests for one of the natural parameters treating the others as nuisance parameters. For detailed construction of such tests in the linear regression setting, see Section 4.

Consistent Estimation After Model Selection

In this section, we leave the parametric setup and consider general models $M$. In particular, we study the consistency of estimators under the selective distribution for arbitrary models. We first introduce the framework of asymptotic analysis under the selective model. Then we state conditions for consistent estimation in Lemma 3 and conclude with examples.

For any model $M$, which is a collection of distributions, we define its corresponding selective model, which is the collection of corresponding selective distributions,

In order to make meaningful asymptotic statements, we consider a sequence of randomized selection procedures $(\widehat{\cal Q}^{*}_{n})_{n\geq 1}$ and models $(M_{n})_{n\geq 1}$ with each $M_{n}$ in the range of $\widehat{\cal Q}^{*}_{n}$.

The following lemma states the conditions for consistency of $\hat{\theta}_{n}$ under the sequence of corresponding selective models $(M_{n}^{*})_{n\geq 1}$,

Consider a sequence $(\widehat{\cal Q}_{n}^{*},M_{n})_{n\geq 1}$ of randomized selection procedures and models. Suppose the selective likelihood ratios satisfies, for some $p>1$,

Further, if $\hat{\theta}_{n}$ is uniformly consistent for $\theta_{n}$ in probability, then $\hat{\theta}_{n}$ is uniformly consistent for $\theta_{n}$ in probability under the sequence $(M_{n}^{*})_{n\geq 1}$.

We illustrate the application of Lemma 3 through our “file drawer effect” examples in Section 1.1.

where we independently draw $\omega\sim G$.

By law of large numbers, we easily see that if we always report $\bar{X}_{n}$, it will be an unbiased estimator for $\mu_{n}$. However, since we only observe the sample means surviving the file drawer effect. Will $\bar{X}_{n}$ still be consistent for $\mu_{n}$?

In the most difficult scenario discussed in Section 1.1, where $\mu_{n}<-\delta<0$ for some $\delta>0$, $\bar{X}_{n}$ cannot be a consistent estimator for $\mu_{n}$ in Example 1. This is easy to see as Example 1 will only report positive sample means. A remarkable feature of randomized selection is that consistent estimation of the population parameters is possible even when the selection event has vanishing probabilities. In fact, the following lemma states that when $G$ is a Logistic distribution, $\bar{X}_{n}$ is consistent for $\mu_{n}$ after the randomized file drawer effect in Example 2.

Before we prove the lemma, we want to point out that although the selection procedure in Example 2 is different from that in Example 1 because of randomization, $\sqrt{n}\mu_{n}$ is still the dominant term in selection. Note that

Since both $\sqrt{n}(\bar{X}_{n}-\mu_{n})$ and $\omega$ are $O_{p}(1)$ random variables, the dominant term $\sqrt{n}\mu_{n}\rightarrow-\infty$, would ensure that the selection event has vanishing probabilities in Example 2 as well. Thus it is particularly impressive that Example 2 gives consistent estimation where Example 1 cannot. The proof of Lemma 4 is deferred to the appendix.

We also verified this theory of consistent estimation through simulations. Figure 1 shows the empirical distributions of the sample mean $\bar{X}_{n}$ after the file drawer effect in Example 1 or the “randomized” file drawer effect in Example 2. They are marked with “blue” colors or “red” colors respectively. We set the true underlying mean to be $\mu_{n}=\mu=-1$ and mark it with the dotted vertical line in Figure 1. The upper panel Figure 1(a) is simulated with $n=100$ and the lower panel Figure 1(b) is simulated with $n=250$. We notice that in both simulations, the sample mean in Example 1 concentrates around the thresholding boundary, which is positive. Thus, these sample means can not be possibly for the underlying mean $\mu=-1$. However, the existence of randomization allows us to report negative sample means. As a result, the sample mean in Example 2 will be consistent for $\mu=-1$. We see that as we increase sample size $n$, the sample means concentrates closer to $\mu=-1$.

Inference in linear regression models

with $\sigma^{2}$ known or unknown or the saturated model,

with known variance. Now we consider some randomized selection procedures and inference after selection.

In the introduction, we introduced data splitting Cox (1975) as a special case of randomized selective inference. In Fithian et al. (2014), the term data carving was introduced to demonstrate that data splitting is inadmissible. In data splitting (and data carving) inference makes most sense in the selected model $M_{sel}(E)$, hence we should think of $\widehat{\cal Q}$ as returning a subset $E$ of variables selected.

However, there are two disadvantages with this randomization scheme. First, it is computationally difficult to aggregate over all random splits. Second, it seems difficult to consider the saturated model $M_{sat}$ for inference, which is more robust to model misspecifications. To overcome those difficulties, we introduce other randomization schemes below.

2 Additive noise and more powerful tests

One major advantage of using a randomized response $y^{*}$ for selective inference is that these procedures yield much more powerful tests, at a small cost of on the quality of the selected models. In other words, small amount of randomization is cause a small loss in the model selection stage, but we gain much more power in the inference stage.

and ${\cal I}(\theta)$ is the non-selective Fisher information for $\theta$ in $M_{sat}$ or $M_{sel}(E)$. The parameters $\theta$ depend on which of the two models we are considering.

In the saturated model $M_{sat}$, the score statistic is $V=\frac{y-\mu}{\sigma^{2}}.$ Since $\widehat{\cal Q}(y^{*})$ is measurable with respect to $y^{*}$,

Since $y$ and $y^{*}=y+\omega$ are both normal distributions with covariance matrices,

In the selected model $M_{sel,E}$, the score statistic is $V=\frac{X_{E}^{T}(y-X_{E}\beta_{E})}{\sigma^{2}}.$ Similarly,

When there is no randomization $\gamma=0$, we potentially have no leftover Fisher information. This corresponds to a very rare selection event. However after randomization, even with very extreme selection, there is always leftover Fisher information, which makes the selective tests more powerful. Consider the following examples.

Moreover, the increase in leftover Fisher information with randomization is not specific to Gaussian randomizations. For example, in Figure 1 when we use Logistic randomization, we also observe that under the selective distribution with randomization, $\bar{X}_{n}$ has a much bigger variance than without randomization. As discussed above, this variance multiplied by $n^{2}$ is exactly the leftover Fisher information, which explains why selective procedures after randomization will have better performances than without.

We investigate the relationship between the leftover Fisher information and the length of confidence intervals constructed by inverting the pivot in (4). Specifically, in Example 2, after observing a reported sample mean, we want to report confidence intervals for the underlying mean $\mu$.

Figure 2 demonstrates the selective intervals (solid lines) after (3) with $\omega$ being either Gaussian or Logistic noises. The sample size $n=100$. Unlike the nominal confidence intervals (dashed lines), the selective intervals are valid with $90\%$ coverage for the underlying mean. Since Lemma 3 gives a lower bound of $(1-\tau){\cal I}(\mu)$, we would intuitively expect the selective confidence intervals to be $1/(1-\tau)$ the length of the nominal intervals. This is verified in Figure 2(a), when we observe really negative sample means. (The sample means can be negative because we added randomization.) On the other hand, for Logistic randomization in Figure 2(b), the intervals are slightly wider than the nominal intervals around the $2/\sqrt{n}$, but narrow to roughly the nominal size on both sides of the truncation point. This indicates that added logistic noise might preserve more information than Gaussian additive noise. Both additive noises improve significantly over a non-randomization scheme (c.f. Figure 3 in Fithian et al. (2014)).

Of course, the increase in power and shortening of selective confidence intervals does not come without a price. Because we select with a randomized response, we are likely to select a worse model. But the trade-off between model quality and power is highly in favor of randomization. See the following example.

2.2 Linear regression with added noise

Back to the general setup of linear regression models, we select a model by solving LASSO with the randomized response $y^{*}=y+\omega$ and return the active set $E$ of the solution (as in (7)). Then per Lemma 2, we can construct valid selective tests in both $M_{sat}$ and $M_{sel}(E)$. For instance, in $M_{sel}(E)$, we can construct tests for the hypothesis $H_{0j}:\beta_{j}=0,~{}j\in E$ based on the law,

where $\eta=(X_{E}^{\dagger})^{T}e_{j}$, $e_{j}$ is the $j$-th column of the identity matrix, $P_{E\backslash j}$ is the projection matrix onto the column space of $E$ but orthogonal to $\eta$, and $A_{E},~{}b_{E}$ are the appropriate matrix and vector corresponding to LASSO selection. This is a UMPU test due to the Lehmann–Scheffe construction (Fithian et al., 2014) and controls the selective Type-I error (11). Although, we cannot compute the explicit forms of (20), the selection events in (20) are polyhedrons and thus a hit-and-run or Hamiltonian Monte Carlo algorithm Pakman & Paninski (2012) can be used for sampling.

Figure 3 compares inference in the additive Gaussian noise scheme to the data carving procedure proposed in Fithian et al. (2014) as well as data splitting. In $M_{sel}(E)$, the probability of screening (i.e. selecting $E$ including all the nonzero $\beta$’s) is a surrogate for the quality of the model. As additive noise uses a different randomization scheme than data splitting and data carving, we vary the amount of randomization used in each scheme and match on the probability of screening. Thus Figure 3 is like an ROC curve for the trade-off between model quality and power of tests. The $x$-axis goes in the direction of increased randomization, with the left most point corresponding to no randomization at all. We see even with a small randomization that barely affects model selection, we can substantially lower the Type-II error from $0.2$ to less than $0.05$. The trade-off is highly in favor of (small) randomization. We see in Figure 3 that additive noise lowers the Type-II error by almost half than data carving for the same screening probability and they both clearly dominate data splitting. For the concrete setup of the simulation, see Chapter 7 of Fithian et al. (2014).

Weak convergence and selective inference for statistical functionals

Throughout this section, we assume the dimension $p$ is fixed. We are interested in establishing a pivotal quantity for $T_{n}=T(D_{n})$ like (4) in Example 2 where $T_{n}$ is the sample mean after the randomized “file drawer effect”. It turns out we have an exact pivotal quantity if $T_{n}$ is normally distributed. To lighten notation, we suppress the script $n$ in the following lemma, which is a finite sample result valid for any $n$. We prove the lemma in Section 7.

Of course the pivot in (22) is very difficult to compute explicitly, and we need to use sampling schemes like in (20). But in a nutshell, $P(T;\eta^{T}\mu,\Sigma)$ is simply a CDF transform of the law

After introducing the null statistic, Lemma 7 is agnostic to the selected model $M_{sel,E}$, where $\mu=X_{E}\beta_{E}$ or the saturated model $M_{sat}$, where the parameter is simply $\mu$. The nuances between the two models in terms of sampling is that the saturated model condition on $N$ (treating it as part of $V_{\eta}$), but selected model integrate over $N$.

Lemma 7 is written with $T$ implicitly being the approximate average of $n$ i.i.d variables, hence the distribution $N(\mu,\frac{\Sigma}{n})$. Linearizable statistics are of particular interest as they converge to $N(\mu,\frac{\Sigma}{n})$ due to central limit theorem. In the following, we seek to establish conditions under which the pivot $P(T;\mu,\Sigma)$ will be asymptotically $\textnormal{Unif}(0,1)$.

In other work on asymptotics of selective inference Tian & Taylor (2015); Tibshirani et al. (2015), the setup considered is usually the saturated model $M_{sat}$. These works considered asymptotics of selective inference marginalized over the range of $\widehat{\cal Q}^{*}$. In contrast, we consider the convergence for any particular selected model $M_{n}$, under the conditional law of the selection event $\{M_{n}\in\widehat{\cal Q}^{*}_{n}\}$. Specifically, we allow weak convergence of the pivot in (22) in the sequence of selected models $(M_{n})_{n\geq 1}$. As explained above, selected models integrate over the null statistics while saturated models condition on those, thus the selective tests should have more power provided that the selected model is believable. In the saturated model, our result provides a finer measure of convergence than in Tian & Taylor (2015). On the other hand, Tian & Taylor (2015) allows high-dimensional setting in some cases while we consider fixed dimension $p$.

Similar to the asymptotic setting in Section 3, we consider the convergence of $P(T_{n};\eta^{T}\mu_{n},\Sigma_{n})$ under a sequence of models $(M_{n})_{n\geq 1}$ selected by a sequence of selection procedures $(\widehat{\cal Q}^{*}_{n})_{n\geq 1}$. $(T_{n})_{n\geq 1}$ is a sequence of linearizable statistics defined in Definition 6, with asymptotic mean $\mu_{n}$ and asymptotic covariance matrix $\frac{\Sigma_{n}}{n}$.

It will be convenient to rewrite the likelihood ratio in terms of the normalized vector $Z_{n}=\sqrt{n}(T_{n}-\mu_{n})$

where $\partial^{k}$ denotes the k-fold differentiation with respect to the $p$-dimensional vector $s$, $\|\cdot\|$ denotes element wise maximum.

Now we state our selective central limit theorem, which we prove in Section 7.

Moreover, assume $\xi_{i,n}$ has uniformly bounded moment generating function in some neighbourhood of . Namely, $\exists a>0$, such that

Then, for any $g$ with uniformly bounded derivatives up to third order

where $K$ depends only on the bounds on the derivatives of $g$, the constants $C_{1},C_{2},C_{3}$ and the dimension $p$. Thus the convergence is uniform in $(M_{n})_{n\geq 1}$ for models satisfying (28), (29) and (30).

2 Revisit the “file drawer problem”

In Examples 1 and 2, we considered only reporting an interval or a $p$-value about $\mu_{n}$ when $n^{1/2}\bar{X}_{n}>2$ or $n^{1/2}\bar{X}_{n}+\omega>2$. This is an example where we do not really select a model, but rather select only a proportion of the data to report. The selective distribution simply refers to the law of the reported sample means, which pass the threshold.

The data we observe is $D_{n}=(X_{1,n,\dots,X_{n,n}})$ with the linearizable statistic $T_{n}$ simply being the sample mean $\bar{X}_{n}$. Example 1 corresponds to the degenerate randomization of adding 0 to $\bar{X}_{n}$. Work of Tian & Taylor (2015) show that in order for the corresponding pivot to converge weakly we can take, for $\Delta<0$ fixed

That is, $\bar{X}_{n}$ will satisfy a selective CLT when the population mean is not too negative.

On the other hand, in Example 2, the pivot in (22) is of the form,

When $G$ is the Logistic noise, then condition (28) and (30) can be verified. Formally, we have the following lemma whose proof we defer to the appendix,

If $G=\textnormal{Logistic}(\kappa)$, with $\kappa$ being the scale parameter, then if centered $X_{i,n}$’s have moment generating functions in the neighbourhood of zero, then the pivot $P(\bar{X}_{n})$ is asymptotically $\textnormal{Unif}(0,1)$.

In other words, with Logistic randomization noise, we can take the sequence of models to be

Requiring exponential moments is stricter than the third moment condition in (32), but we would have a stronger conclusion, namely weak convergence uniformly over all $\mu_{n}$’s.

3 Two-sample median problem

with $R=O(n^{-3/4}\log n)$ with probability $1$.

Our (randomized) selection algorithm $\widehat{\cal Q}^{*}$ reports

This pivot strikes a similarity with the pivot in (33) for Example 2 with the truncation threshold $2$ being replaced by $\sqrt{n}T_{2}$ and plugging in the appropriate means and variances of the medians. A result similar to Lemma 10 can be established, which ensures convergence of the pivot uniformly for any underlying medians $(\mu_{1},\mu_{2})$.

In order to construct the above pivot, we need knowledge of the variance $\sigma^{2}_{1}$. Without selection, there are natural estimates of this variance. One may ask, how will inference be affected if we plug this estimate into our pivot? We revisit this question in Section 5.5.

4 Affine selection events

In this section, we discuss the special case of affine selection events (regions). This combined with the asymptotic result in Theorem 9 applies to more general settings. In particular, it allows us to approximate non-affine regions. For a concrete example, see Section 5.4.1.

We again normalize $T$ to be $Z=\sqrt{n}(T-\mu)$, then the selection event can be rewritten as

where $\sqrt{n}\mu=\Delta$, $Z$ converges to $N(0,\Sigma)$.

Lower bound: We assume there is some norm $h$, such that

Smoothness: Suppose $G$ has density $g$, we assume the first 3 derivatives of $g$ are integrable,

where the norm on the left-hand side is the maximum element-wise of the partial derivatives.

The above two conditions essentially require $G$ to be differentiable and have heavier tails than (or equal to) exponential tails. In fact we prove that the lower bound and smoothness conditions ensure that (28) are satisfied under the local alternatives introduced below.

For the sequence of selected model $(M_{n})_{n\geq 1}$, we define the local alternatives of radius of $B$ to be the set all sequences $(\mu_{n})_{n\geq 1}$, such that

where $d_{h}(\cdot,\cdot)$ is the distance induced by the norm $h$.

The notion of local alternatives is natural in the asymptotic setting as we expect even a small effect size will be more prominent when we collect more and more data.

Formally, we have the following lemma, whose proof is deferred to the appendix.

Suppose $G$, $K_{M}$ satisfy the lower bound and smoothness conditions, then condition (28) are satisfied under the local alternatives.

Now, we are left to verify conditions (29) and (30). Condition (29) is essentially a moment condition on the centered statistics $\xi_{i,n}-\mu_{n}$, which we have to assume. Condition (30) can be verified using the well known results in multivariate CLT (see Gotze (1991)). To be rigorous, we state the following lemma, which we also prove in the appendix.

Unlike the sample mean and sample median examples, the pivot is difficult to compute explicitly in this case. However, as we discuss in the beginning of Section 5, the pivot is essentially the CDF transform of the conditional law (23), which we can sample from. As discussed above, we can just take $\omega$ to be from a Logistic distribution.

Now we apply the above theory to logistic regression.

Selective inference in this setting has not been considered before. Without the Gaussian assumptions Lee et al. (2013a) does not apply. The parametric setting of this problem has been discussed in Fithian et al. (2014), but computation of the selective tests are mostly infeasible for general $X$. Finally, the asymptotic result by Tian & Taylor (2015) does not apply here as the framework require exactly affine selection regions, which is not the case in this setting.

Suppose the solution to (38) has nonzero entry set $E$, then our target of inference $\beta_{E}^{*}$, the unique population minimizer which satisfies

Selective inference in this setting is carried out conditioned on $(E,s_{E})$, the active set and its signs. We first introduce the following notations,

where $X$ is the feature matrix, and $X_{E}$, $X_{-E}$ is the columns corresponding to the active set and inactive set respectively. By law of large numbers, we have

Now we introduce our linearizable statistics and show that the conditioning event $(E,s_{E})$ can be expressed as affine regions of these statistics.

Suppose $E$ is the active set of the solution of (38), and we denote

as the unpenalized MLE restricted to the selected variables $E$.

The following statistic $T$ is linearizable with asymptotic mean $(\beta_{E}^{*},\rho)$ and variance $\Sigma/n$,

The proof of this lemma is also deferred to the appendix.

Thus using Lemma 12 and Lemma 13, we can conclude under local alternatives, the pivot (22) converges to $\textnormal{Unif}(0,1)$. To test $H_{0j}:\beta_{j}^{*}=0$, we take $\eta=e_{j}$, and sample

In Lemma 14, we assume the covariance matrix $\Sigma$ is known. In applications, we can bootstrap it. But is it valid to plug in the bootstrap estimate of $\Sigma$?

5 Plugging in variance estimates

In Section 5.3 we derived quantities that were asymptotically pivotal for the best median, up to an unknown variance. In the sample median case, by (35), the variance of the sample median is approximately $[4nf(m)^{2}]^{-1}$, where $f(m)$ is the PDF evaluated at the median $m$. A simple consistent estimator for $f(m)$ is to take $1/2\pm\frac{1}{\sqrt{n}}$ quantiles $a_{n}$ and $b_{n}$, then

is consistent for $f(m)$ based on which we get a consistent estimator for $\sigma_{1}^{2}$.

Figure 4 is some simulation results for the two-sample medians problem. In each case, we take the sample size for each treatment group to be $500$, and generate the noise from a skewed distribution $N(0,1)+0.5\textnormal{Exp}(1)$. We standardize it such that the noise has median under the null hypothesis. We use additive logistic noise with scale $\kappa=0.8$ for randomization. The better group is decided using the randomized sample median, and selective inference is carried out. In Figure 4(a), the pivot with plugin variance estimate $\widehat{\sigma}$ in (41) is plotted under both the null hypothesis $H_{0}:\mu_{better}=0$ and the $H_{A}:\mu_{better}>\frac{1}{\sqrt{n}}$. The pivot has reasonable power even for identifying local alternatives. The pivot is almost exactly $\textnormal{Unif}(0,1)$ under the null hypothesis with the sample size $n=500$. In fact, it is very close at a relatively small sample size $n=50$ justifying the application of asymptotics in the nonparametric setting. Figure 4(b) further illustrates the difference in the unselective v.s. selective distribution and its convergence to its theoretical limit. We see that there is a clear shift in selective distribution that calls for adjustment for the selection. For sample size $n=500$, the empirical selective distribution converges to our theoretical distribution.

Multiple Randomizations of the Data

Most of the examples above focus on a single randomization $\omega$ on the data, which we use for model selection. We naturally want to extend it to multiple randomizations, and multiple randomized selections, which will collectively suggest a model for inference. In this section, we allow multiple randomizations in a possibly sequential fashion and discuss how inference can be carried out.

Consider the case where we first choose a regularization parameter by cross-validation, and then fit the square-root LASSO problem Belloni et al. (2011) at this parameter,

where $\lambda$ is picked from a fixed grid $\Lambda=[\lambda_{1},\dots,\lambda_{k}]$. The discussion below is not specific to selection by square-root LASSO.

The model selected by cross-validated square-root LASSO involves two steps of selection. We denote by $y_{\text{CV}}$ the response for selecting the randomization parameter, and $y_{\text{select}}$ the response vector for fitting the square-root LASSO at the selected regularization parameter $\lambda$. Both vectors are randomized version of the original vector $y$. Inference after cross validation requires combining two steps of randomized selection. Consider the following procedure.

First, we randomize $y$ to get the vector $y_{\text{CV}}$ and $y_{\text{select}}$

Note the intermediate vector $y_{\text{inter}}$ is introduced convenience of sampling. The above is just one of the plausible randomization schemes.

After having randomized, we select $\lambda$ with $K$-fold cross-validation using $y_{\text{CV}}$:

where $CV_{K}(y,X,\lambda)$ is the usual $K$-fold cross-validation score with coefficients estimated by the square-root LASSO. Alternatively, one could compute the cross-validation score using the OLS estimators of the selected variables. Note that we have left implicit the randomization that splits observations into groups. That is $\hat{\lambda}$ in (44) above is a function of $(y_{\text{CV}},X,\omega)$ where $\omega$ is a random partition of $\{1,\dots,n\}$ into $K$ groups. When we sample $y_{\text{CV}}$ below, we redraw $\omega$ each time.

The subset of variables and signs is selected using the square-root LASSO with response $y_{\text{select}}$:

After seeing the selected variables $\hat{E}$, we perform inference in the selected model $M_{sel}(\hat{E})$. Since $M_{sel}(\hat{E})$, we will still have an exponential family after selection. Per Lemma 2, we sample from the following law,

The additional conditioning on the signs are for computational reasons. In fact, recent development in Harris et al. (2016) proposes sampling schemes that overcome these difficulties, so that we do not need to condition on this additional information.

To sample from the above law, we use a Gibbs-type sampler, which iterate over $y$, $y_{\text{inter}}$, $y_{\text{CV}}$ and $y_{\text{select}}$, conditional on the other three and the selection event. It includes the following steps.

Using the conditional independence of $y_{\text{CV}}$ and $y_{\text{select}}$ given $y_{\text{inter}}$, we have

This is the computational bottleneck, as we do not have good description for the selection event for cross validation. A brute-force sampling scheme will be computationally expensive, as we need to refit the model over a grid of $\lambda$’s. Thus, we do not update $y_{\text{CV}}$ too often.

The conditional independence of $y_{\text{select}}$ and $y_{\text{CV}}$ given $y_{\text{inter}}$ implies,

Tian et al. (2015) has given an explicit description of the selection event

Thus hit-and-run sampling provides a tractable sampling scheme.

This is a simple step. Because the selection event is based on $y_{\text{CV}}$ and $y_{\text{select}}$, we have

This is also simple with our randomization scheme. Note that $y$ is conditionally independent of $y_{\text{select}}$ and $y_{\text{CV}}$ given $y_{\text{inter}}$,

Since we condition on $P_{E\backslash j}y$, we essentially take $y$ and project out the update on the space orthogonal to that of $X_{j}$.

A chain that iterates through the above four steps will give us samples from the desired distribution for inference.

2 Collaborative selective inference

One of the motivations of the reusable holdout described in Dwork et al. (2014) is that it allows a data analyst to repeatedly query a database yet still be able to approximately estimate expectations even after asking many questions about the data. Another version of this model may be that several groups wish to model the same data and then, as a consortium, decide on a final model and be able to approximately estimate expectations in this final model. We might call this collaborative selective inference.

Now suppose that the $L$ groups choose models $\hat{M}_{l}^{*}=\widehat{\cal Q}_{l}(y^{*}_{l})\in\sigma(y^{*}_{l})$ and convene to discuss what the best model is $M$. For every choice of $L$ models $(M_{1},\dots,M_{L})$ and final model $M$, the following selective distribution can be used for valid selective inference

When the $y^{*}_{l}$’s are conditionally independent given $y$ then it is clear that

It is possible that the consortium has beforehand decided on an algorithm that will choose a best model automatically, determined by some function ${\cal S}(M_{1},\dots,M_{L})$. In this case, one should use the selective distribution

When the models in question are parametric, perhaps Gaussian distributions, and the randomization is additive Gaussian noise the central data bank can explicitly lower bound the leftover information by

This quantity is expressible in terms of the marginal variance of $y$ and the central data bank’s noise generating distribution for $y^{*}(y,\omega)=(y+\omega_{1},\dots,y+\omega_{L})$. By maintaining a lower bound on the above quantity, the central data bank can maintain a minimum prescribed information in the data for final estimation and/or inference. In a sequential setting, where valid inference is desired at each step, maintaining a lower bound may involve releasing noisier and noisier versions of $y$. Sampling under this scheme seems quite difficult, and we leave it as an area of interesting future research.

Proof

To prove Theorem 9, we first prove the following lemma, which might be of independent interest.

for some $n_{0}\geq 1$, where $C(p)$ is a constant only dependent on the dimension.

Lemma 15 can be seen as an extension of the result by Chatterjee (2005) in the sense that the author in Chatterjee (2005) established result for the case $\Omega=0$. The proof is also an adaptation of the technique in Chatterjee (2005).

We also define for any $n$ and $0\leq k\leq n$,

Let $\partial_{i}$ be the derivative with respect to the $i$-th row $S[i]$. Using Taylor’s expansion at $S_{n,k}^{-}$, we have

where the precise form of the Taylor remainder $R_{n,i}$ depends on realizing the laws $F_{n,i}$ and $F_{n,i}^{-}$ on the same probability space. In order to not introduce new notation, we have avoided explicitly writing out this construction, directing readers to Chatterjee (2005) for details. Nevertheless,

where $\xi_{i,n}^{0}$ are centered version of $\xi_{i,n}$ and $c_{1}$ is some dimension dependent constant.

Let $C(\Omega)$ be the constant s.t $\Omega(\cdot)\leq C(\Omega)\|\cdot\|_{1}$, $C(\Omega)$ only depends on the dimension $p$. Thus, using the independence of the $\xi_{i,n}$’s,

Now we bound these two expectations. By the exponential moment condition (29) and Lemma 17, it is easy to conclude the first term is bounded by

The second expectation is bounded by $\gamma$, an upper bound on the third moment of $\xi_{i,n}^{0}$,

and summing over $n$ terms, we have the conclusion of the lemma. ∎

Now we prove the main theorem, Theorem 9.

per condition (30) and $C(g)$ is a bound on $g$. ∎

2 Proof of Lemma 7

References

Appendix A Proof of Lemma 1

First we normalize the sample mean as $Z=\sqrt{n}(\bar{X}_{n}+0.5)$ and rewrite the pivot as

and $\Phi$ is the CDF of the standard normal distribution. As $n\to\infty$, we can use Mills ratio to approximate the normal tail. Specifically, denote $b_{n}=\frac{1}{2}\sqrt{n}+2$,

We study the behavior of $-b_{n}(Z-b_{n})$ for $Z>b_{n}$. By studying its distribution, we will also see that $Z-b_{n}\overset{p}{\to}0$, for $Z>b_{n}$, thus the term

Now we study the distribution of $b_{n}(Z-b_{n})$ conditioning on $Z>b_{n}$. Since $\bar{X}_{n}$ is a translation of a binomial distribution divided by $n$, we can rewrite $Z$ in terms of a Binomial distribution, which will be useful for calculating the conditional distribution of $b_{n}(Z-b_{n})$. Specifically,

Noticing that $\frac{k}{n-k+1}\leq\frac{m}{n-m+1}$, for any $k\leq m$, thus

Now let $m=\frac{1}{4}n-\sqrt{n}$, and use the above inequality $j=\frac{t\sqrt{n}}{2b_{n}}$ times, we have

We can draw two conclusions from (50). First, conditional on $Z>b_{n}$, $Z-b_{n}\overset{p}{\rightarrow}0$, which implies the first term in the pivot approximation (49) $R_{n}\to 1$. Moreover, (50) shows that the overshoot $b_{n}(Z-b_{n})$ is not $\textnormal{Exp}(1)$ distributed in the limit. In fact, we can conclude its limit (if existed) is strictly stochastically dominated by an $\textnormal{Exp}(1)$. Thus,

and hence the pivot does not converge to $\textnormal{Unif}(0,1)$. ∎

Appendix B Proof of Lemma 14

We first prove that $T$ is in fact a linearizable statistic. Since $\bar{\beta}_{E}$ is the restricted MLE, we see that

Thus we can conclude that $T$ is a linearizable statistic with

Now we rewrite the selection event in terms of $(T,\omega)$. Using the KKT conditions of (38),

Plugging in the equalities in the KKT conditions, we will have,

Using the inequalities in the KKT conditions, we have the selection event is $\{A_{M}T+B_{M}\omega\leq b_{M}\}$ with $A_{M}$, $B_{M}$ and $b_{M}$ defined in the lemma.

Appendix C Proofs related to Logistic noise

Throughout the article, logistic noise has played an important role in all the examples.

The following lemma on the tail behavior of the logistic distribution is crucial to all the proofs with added logistic noise. Let $G$ be the CDF of $\textnormal{Logistic}(\kappa)$, with $\kappa$ being the scale parameter. $g$ is the PDF of $G$.

where $\widetilde{C}_{k}$’s are universal constants.

where $h_{0}(x)=(1+x)^{-2}$. For $j\geq 1$, define $h_{j}(x)=x\cdot h^{\prime}_{j-1}(x)$. By induction, I claim that for each $j$, $h_{j}$ is rational such that the polynomial in the numerator is of order 2 less than the denominator, and the denominator polynomial is bounded below by 1. Hence, $h_{j}$’s are bounded on the interval $$. Now, it is not hard to see that

for universal $c_{j,k}$’s and $k=0,1,2,\dots$. ∎

Now we state the following lemmas which are foundations of the proofs of various lemmas in the article.

Assume $T_{n}$ is a decomposable statistic and $\xi_{i,n}$ has mean , variance $\sigma^{2}$, and centered exponential moments in a neighbourhood of zero, i.e satisfies condition (29). Denote $Z_{n}=\sqrt{n}(T_{n}-\mu_{n})$, then

In Example 2, if we normalize the sample mean $Z_{n}=\sqrt{n}(\bar{X}_{n}-\mu_{n})$, we can rewrite the selective likelihood ratio and the pivot as

for some $C_{1}$ only depending on $\kappa$.

Noticing the lower bound in (52), we have

On the other hand, using the upper bounds in (53), we have for $k=1,2,3$,

Since $x^{-1}$ is convex on the positive axis, it is hard to see

The term $\exp(-\kappa\sqrt{n}\left|\mu_{n}\right|)$ cancels with the one in the denominator, thus (55) holds for $k=0$ as well.

Analogously, similar bounds can be derived for the derivatives of $\overline{P}(Z)$ as well, thus we have the conclusion of the lemma. ∎

The proof of Lemma 4 is a simple application of Lemma 17 and Lemma 18.

By law of large numbers, we know that $\bar{X}_{n}$ is consistent for $\mu$ unselectively. Thus, using the result by Lemma 3, we only need to verify that the selective likelihood is integrable in $L^{q}$. For simplicity, we take $q=2$.

First notice from (54) that the selective likelihood ratio is bounded by a multiple of $\exp[\kappa|Z|]$. Then by Lemma 17,

The proof of Lemma 10 uses results in Lemma 18 and Lemma 15

It follows simply from (54) that condition (28) are satisfied with the norm function $\Omega$ simply being the absolute value function. Therefore, we only need to verify (30). Note for $\mu_{n}=\mu<0$

Appendix D Proofs related to affine selection regions

The quantity that appears in both the pivot and the selective likelihood ratio is

where $\omega\sim G$. The associated selective likelihood in terms of $z$ is

We first rewrite the pivot in terms of $U$.

If we assume the lower bound condition, then under the local alternatives with radius $B$, i.e. $d_{h}(0,K-A\Delta)\leq B$, we have

where $C(\Phi,h)$ is a constant only depending on the normal distribution $\Phi=N(0,\Sigma)$ and the norm $h$ in the local alternatives condition.

We first see that the lower bound condition gives the following lower bound.

Finally, since the $\exp(-h(Au))$ has uniformly bounded derivatives up to the third order, we have

Suppose the smoothness and the lower bound conditions are satisfied, then for local alternatives with radius $B$,

The smoothness condition implies the following upper bound. For a multi-index $\alpha$, we have

Therefore, from the smoothness condition,

This combined with Lemma 19 gives the conclusion of the lemma. ∎

Next, we derive the exponential bounds on the derivatives of the pivot $P(z;\Delta)$ with respect to $z$.

Assuming the conditions of Lemma 12, for a multi-index $\alpha$ up to the order of $3$,

To get a lower bound on the denominator, note (57)

Therefore, the denominator will be lower bounded by

On the other hand, the upper bound (59) ensures,

Note the derivatives of the pivot will be a polynomial in terms of the form,

and therefore, it is easy to get the conclusion of the lemma. ∎

D.2 Proof of Lemma 13

Using Lemma 19 and the following lemma, we can easily prove Lemma 13.

Proof of Lemma 22 uses the well known results of Berry-Esseen Theorem. A multivariate extension can be found in Gotze (1991).

Thus the difference in the two probabilities is

where $C_{3}$ only depends on the dimension $p$. The last inequality is a direct application of equation (1.5) in Gotze (1991). ∎