{{\widehat{S}}}$:

Get $\hat\beta_{{\widehat{S}}}$ from ${\cal D}_{2,n}$ by least squares.

Output $\hat{C}_{{\widehat{S}}} = \bigotimes_{j\in {\widehat{S}}} C(j)$ where $C(j) = \hat\beta_{{\widehat{S}}}(j) \pm z_{\alpha/(2k)} \sqrt{\hat\Gamma_n(j,j)}$ where $\hat\Gamma$ is given by (\[eq::Ga\]).

For $\gamma_{{\widehat{S}}}$:

Get $\hat\beta_{{\widehat{S}}}$ from ${\cal D}_{1,n}$. This can be any estimator. For $j\in {\widehat{S}}$ let $\hat\gamma_{{\widehat{S}}}(j) = \frac{1}{n}\sum_{i=1}^n r_i$ where $r_i = (\delta_i(j) + \epsilon \xi_i(j))$, $\delta_i(j) =  \left| Y_i - t_{\tau} \left( \hat\beta_{{\widehat{S}},j}^\top X_i \right) \right|  - \left|Y_i - t_{\tau} \left( \hat\beta_{{\widehat{S}}}^\top X_i \right)\right|$ and $\xi_i(j)\sim {\rm Unif}(-1,1)$. Let $\hat\gamma_{{\widehat{S}}} = (\hat\gamma_{{\widehat{S}}}(j):\ j\in {\widehat{S}})$.

Output $\hat{D}_{{\widehat{S}}} = \bigotimes_{j\in {\widehat{S}}} D(j)$ where $D(j) = \hat\gamma_{{\widehat{S}}}(j) \pm z_{\alpha/(2k)}\hat{\Sigma}(j,j)$, with $\hat{\Sigma}(j,j)$ given by .

------------------------------------------------------------------------

------------------------------------------------------------------------

[Median-Split]{}

[Input]{}: Data ${\cal D} = \{(X_1,Y_1),\ldots, (X_{2n},Y_{2n})\}$. Confidence parameter $\alpha$.\
[Output]{}: Confidence set $\hat{E}_{{\widehat{S}}}$.

Randomly split the data into two halves ${\cal D}_{1,n}$ and ${\cal D}_{2,n}$.

Use ${\cal D}_{1,n}$ to select a subset of variables ${\widehat{S}}$. This can be forward stepwise, the lasso, or any other method. Let $k= |{\widehat{S}}|$.

Write ${\cal D}_{2,n}=\{(X_1,Y_1),\ldots, (X_n,Y_n)\}$. For $(X_i,Y_i)\in {\cal D}_{2,n}$ let $$W_i(j) = 
|Y_i-\hat\beta_{{\widehat{S}},j}^\top X_i| - |Y_i-\hat\beta_{{\widehat{S}}}^\top X_i|,$$

Let $W_{(1)}(j) \leq \cdots \leq W_{(n)}(j)$ be the order statistics and let $E(j) = [W_{(n-k_2)}(j),W_{(n-k_1+1)}(j)]$ where $$k_1 =  \frac{n}{2} + \sqrt{n \log\left( \frac{2k}{\alpha}\right)},\ \ \ 
k_2 =  \frac{n}{2} - \sqrt{n \log\left( 