distribution with parameter vector
$\bm{p}=(\overline{\Phi}(b_{j})+\delta_{n})_{j\leq s_{n}}$. (Note that
$a_{b}=\sqrt{2\log(n/s_{n})}+b$ here because we are in the Gaussian case
$\zeta=2$.) For some sequence $\delta_{n}^{\prime}\to 0$ we see that the false
negative rate is then

$\operatorname{FNR}(\theta,\varphi^{\hat{\ell}})=s_{n}^{-1}E_{\theta}[s_{n}-S]\leq
P_{\theta}(\hat{w}<w_{-})+s_{n}^{-1}E[N]\leq\Lambda_{\infty}+\delta_{n}^{\prime}.$
(58)

A concentration argument further yields that on an event of probability
tending to 1,

$S\geq s_{n}(1-\Lambda_{\infty})/2,$ (59)

which will be used in the next step. Indeed observe, using the assumption
$1-\Lambda_{\infty}>0$, that for $n$ large

$EN=s_{n}(\Lambda_{n}(\bm{b})+\delta_{n})\leq
s_{n}\Lambda_{\infty}+(1/4)s_{n}(1-\Lambda_{\infty}).$

Using this bound and Bernstein’s inequality (Lemma 5) yields

$P\big{(}N>s_{n}\Lambda_{\infty}+\tfrac{1}{2}s_{n}(1-\Lambda_{\infty})\big{)}\leq
P\big{(}N-EN>\tfrac{1}{4}s_{n}(1-\Lambda_{\infty})\big{)}\to 0,$

hence

$\displaystyle P_{\theta}\big{(}S<s_{n}(1-\Lambda_{\infty})/2\big{)}$
$\displaystyle=P_{\theta}\big{(}s_{n}-S>s_{n}\Lambda_{\infty}+s_{n}(1-\Lambda_{\infty})/2\big{)}$
$\displaystyle\leq
P\big{(}N>s_{n}\Lambda_{\infty}+\tfrac{1}{2}s_{n}(1-\Lambda_{\infty})\big{)}+P_{\theta}(\hat{w}<w_{-})\to
0.$

#### Step 3 (FDR control)

Let $V$ denote the number of false positives,

$V=\\#\\{i\not\in S_{\theta}:\ell_{i,\hat{w}}<t\\}.$

By (59), let $\mathcal{A}$ be an event of probability tending to 1 on which
$S\geq s_{n}(1-\Lambda_{\infty})/2$ and $\hat{w}<w_{+}$. Define

$V^{\prime}=\\#\\{i\not\in S_{\theta}:\ell_{i,w_{+}}<t\\}.$

Using monotonicity and applying Jensen’s inequality to the convex function
$x\mapsto x/(a+x)$ we obtain

$\operatorname{FDR}(\theta,\varphi^{\hat{\ell}})=E_{\theta}\Big{[}\frac{V}{(V+S)\vee
1}\Big{]}\leq
E_{\theta}\Big{[}\frac{V}{V+S}\mathbf{1}_{\mathcal{A}}\Big{]}+P_{\theta}(\mathcal{A}^{c})\\\
\leq
E_{\theta}\Big{[}\frac{V^{\prime}}{V^{\prime}+s_{n}(1-\Lambda_{\infty})/2}\Big{]}+o(1)\leq\frac{E_{\theta}V^{\prime}}{E_{\theta}V^{\prime}+s_{n}(1-\Lambda_{\infty})/2}+o(1).$
(60)

Next, Lemma 13 yields

$E_{\theta}V^{\prime}=(n-s_{n})P_{\theta}(\ell_{i,w_{+}}\leq t)\leq
2(n-s_{n})r(w_{+},t)\xi(r(w_{+},t))^{-3},$ (61)

where $r(w_{+},t)=w_{+}t(1-w_{+})^{-1}(1-t)^{-1}\asymp w_{+}$. We note that
$\xi(u)\sim(2\log(1/u))^{1/2}$ as $u\to 0$ by Lemma 18, so that using
$w_{+}\asymp(s_{n}/n)(\log n/s_{n})^{1/2}$, we have
$E_{\theta}V^{\prime}\lesssim s_{n}\log(n/s_{n})^{-1}=o(s_{n})$. Since we are
assuming $\Lambda_{\infty}<1$, this yields the bound

$\operatorname{FDR}(\theta,\varphi^{\hat{\ell}})\leq\frac{o(s_{n})}{o(s_{n})+s_{n}(1-\Lambda_{\infty})/2}+o(1)=o(1).$

Combined with the bound on the false negative rate, this concludes the proof.

######  Lemma 9.

Under the conditions of Theorem 5(i), there exist solutions $w_{-}\leq w_{+}$
to (56) and (57) respectively. Moreover, these solutions are almost surely
unique and satisfy

$w_{\pm}\asymp s_{n}(n-s_{n})^{-1}\tilde{m}(w_{\pm})^{-1}\asymp
s_{n}(n-s_{n})^{-1}(\log(n/s_{n}))^{1/2}\asymp(s_{n}/n)(\log n/s_{n})^{1/2}.$

###### Proof.

We follow the proof of [1, Lemma 5], adapting to allow for the weaker and
mixed signals considered here, and taking advantage of not targeting a rate of
convergence to simplify some aspects. We claim that, for some constants
$c,C>0$,

$\displaystyle\sum_{i\in S_{\theta}}m_{1}(\theta_{i},c(s_{n}/n)(\log
n/s_{n})^{1/2})$
$\displaystyle>(1+\nu)(n-s_{n})\tilde{m}(c(s_{n}/n)(\log(n/s_{n}))^{1/2})$
(62) $\displaystyle\sum_{i\in
S_{\theta}}m_{1}\big{(}\theta_{i},C(s_{n}/n)(\log n/s_{n})^{1/2}\big{)}$
$\displaystyle<(1-\nu)(n-s_{n})\tilde{m}\big{(}C(s_{n}/n)(\log
n/s_{n})^{1/2}\big{)},$ (63)

at least for $n$ large enough. It will follow by the intermediate value
theorem that there exist unique $w_{-},w_{+}$ solving (56) and (57)
respectively, and satisfying $(s_{n}/n)(\log n/s_{n})^{1/2}\lesssim w_{-}\leq
w_{+}\lesssim(s_{n}/n)(\log n/s_{n})^{1/2}$, since $\tilde{m}$ is continuous,
increasing and non-negative and $m_{1}(\tau,\cdot)$ is continuous and
decreasing for each fixed $\tau$ (see Lemma 15).

To prove the claim, note that also by Lemma 15 we have, for some
$c_{0},C_{0}>0$, any $\mu\in\mathbb{R}$ and asymptotically as $w\to 0$,

$\displaystyle c_{0}(\log(1/w))^{-1/2}$ $\displaystyle\leq\tilde{m}(w)$
$\displaystyle\leq C_{0}(\log(1/w))^{-1/2},$
$\displaystyle\phantom{\leq}m_{1}(\mu,w)$ $\displaystyle\leq 1/w.$

It follows that

$\displaystyle\sum_{i\in S_{\theta}}m_{1}(\theta_{i},C(s_{n}/n)(\log
n/s_{n})^{1/2})$ $\displaystyle\leq C^{-1}n(\log(n/s_{n}))^{-1/2},$
$\displaystyle(1-\nu)(n-s_{n})\tilde{m}(C(s_{n}/n)(\log(n/s_{n}))^{1/2})$
$\displaystyle\gtrsim(n-s_{n})(\log(n/s_{n}))^{-1/2},$

where the suppressed constant can be chosen independently of $C>0$ and
$\nu\in(0,1/2)$, for $n$ larger than some $N=N(C)$. The inequality (63)
follows, for $C$ large enough.

For the lower bound on (62) we observe that Lemma 15 further yields, for some
constants $\omega_{0}\in(0,1),M_{0}>0$ and all $w\leq\omega_{0}$, $\mu\geq
M_{0}$,

$m_{1}(\mu,w)\geq c_{1}\frac{\overline{\Phi}(\zeta(w)-\mu)}{w}T_{\mu}(w),$

where $T_{\mu}(w)$ is a function bounded below by 1. Recall that $\zeta$ is a
decreasing function satistfying
$\zeta(w)\leq(2\log(1/w)+2\log\log(1/w)+C)^{1/2}$ for a constant $C>0$ (see
Lemma 17) . In particular, note by a Taylor expansion that
$\zeta(c(s_{n}/n)(\log(n/s_{n}))^{1/2})\leq\sqrt{2\log(n/s_{n})}+o(1)$ and
hence, using also that $\overline{\Phi}$ is Lipschitz, for some $C_{1}>0$ and
some $o(1)$ not depending on $\bm{b}$ or $c$ we have for $n$ large and
$a_{b_{j}}\geq M_{0}$

$m_{1}(a_{b_{j}},c(s_{n}/n)(\log(n/s_{n}))^{1/2})\geq
C_{1}c^{-1}(n/s_{n})(\log(n/s_{n}))^{-1/2}(\overline{\Phi}(-b_{j})-o(1)).$

Observe also, recalling the definition (50), that
$\beta(x,w)\geq-\lvert\beta(0)\rvert/(1-\lvert\beta(0)\rvert)$ is lower
bounded by a constant, hence the same is true of $m_{1}(\tau,w)$ for all
$\tau$ and $w$ (including $\tau<M_{0}$). Let $\sigma$ denote a bijection
taking $i\in S_{\theta}$ to $\sigma(i)=j\in\\{1,\dots,s_{n}\\}$ such that
$\lvert\theta_{i}\rvert\geq b_{j}$. Noting that $\overline{\Phi}(-b_{j})=o(1)$
uniformly in $j$ such that $a_{b_{j}}\leq M_{0}$, we deduce that for some
constants $C_{2},c_{2}>0$ not depending on $c$

$\displaystyle\sum_{i\in
S_{\theta}}m_{1}(\theta_{i},\frac{cs_{n}(\log(n/s_{n}))^{1/2}}{n})$
$\displaystyle=$ $\displaystyle\sum_{i\in
S_{\theta},a_{b_{\sigma(i)}}<M_{0}}m_{1}(\theta_{i},\frac{cs_{n}(\log(n/s_{n}))^{1/2}}{n})+\sum_{i\in
S_{\theta},a_{b_{\sigma(i)}}\geq
M_{0}}m_{1}(\theta_{i},\frac{cs_{n}(\log(n/s_{n}))^{1/2})}{n}$
$\displaystyle\geq$ $\displaystyle-
C_{2}s_{n}+\frac{c_{2}n}{cs_{n}(\log(n/s_{n}))^{1/2}}\sum_{j\leq
s_{n}:a_{b_{j}}\geq M_{0}}(\overline{\Phi}(-b_{j})-o(1))$ $\displaystyle\geq$
$\displaystyle-
C_{2}s_{n}+\frac{c_{2}n}{cs_{n}(\log(n/s_{n}))^{1/2}}\big{(}\sum_{j\leq
s_{n}}(\overline{\Phi}(-b_{j})-o(1))\big{)}$
$\displaystyle=-C_{2}s_{n}+\frac{c_{2}n}{c(\log
n/s_{n})^{1/2}}(1-\Lambda_{\infty}-o(1)).$

Note that $s_{n}=o(n)$ implies $s_{n}=o(n/(\log(n/s_{n}))^{1/2})$. Since
$\Lambda_{\infty}<1$ we deduce that the left side of (62) is lower bounded by
a constant not depending on $c$ multiplied by $c^{-1}n(\log n/s_{n})^{-1/2}$,
while the right side, using the earlier upper bound on $\tilde{m}(w)$, is
upper bounded by a constant not depending on $c$ multiplied by
$n\log(n/s_{n})^{-1/2}$. Taking $c$ small enough yields the claim. ∎

######  Lemma 10.

Under the assumptions of Lemma 9, define $\hat{w},$ $w_{-}$ and $w_{+}$ as in
(46),(56) and (57) respectively. Then there exists $c>0$ such that

$\sup_{\theta\in\Theta_{\bm{b}}}P_{\theta}\big{(}\hat{w}\not\in(w_{-},w_{+})\big{)}\leq
e^{-cs_{n}}.$

###### Proof.

We adapt the proof of [17, Lemma S-4] or [1, Lemma 7] to the current setting
with no polynomial sparsity and multiple signal levels $b_{j}$.

Let us prove, for a constant $c>0$ depending only on an upper bound for
$\nu<1$, that

$P_{\theta}(\hat{w}<w_{-})\leq e^{-cs_{n}}.$

The proof that $P_{\theta}(\hat{w}>w_{+})\leq e^{-cs_{n}}$ is similar (see
also the similar proof below of Lemma 11), yielding the claim up to a factor
of 2 which can be removed by initially considering a $c^{\prime}>c$.

Let $S=L^{\prime}$ be the score function, that is, the derivative of the
likelihood $L$ defined in (47). Since $\hat{w}$ maximises $L(w)$, necessarily
$S(\hat{w})\leq 0$ or $\hat{w}=1$. If $\hat{w}<w_{-}$ then only the former may
hold, so that applying the strictly monotonic function $S$ (Lemma 12) we
obtain
$\\{\hat{w}<w_{-}\\}=\\{S(w_{-})<S(\hat{w})\\}\subseteq\\{S(w_{-})<0\\}$.
Hence,

$\displaystyle P_{\theta}(\hat{w}<w_{-})\leq P_{\theta}(S(w_{-})<0)$
$\displaystyle=P_{\theta}(S(w_{-})-E_{\theta}S(w_{-})<-E_{\theta}S(w_{-}))$
$\displaystyle=P_{\theta}\left(\sum_{i=1}^{n}W_{i}<-E\right),$

where we have introduced the notation
$W_{i}=\beta(X_{i},w_{-})-m_{1}(\theta_{i},w_{-})$ and
$E=E_{\theta}S(w_{-})=\sum_{i=1}^{n}m_{1}(\theta_{i},w_{-})$. For $n$ large,
$|W_{i}|\leq\mathcal{M}:=2/w_{-}$ a.s. (see Lemma 14), so that we may scale
the variables $W_{i}$ to apply the Bernstein inequality (Lemma 5) and obtain

$\displaystyle P_{\theta}(\hat{w}<w_{-})\leq
e^{-0.5E^{2}/(V_{2}+\mathcal{M}E/3)},$

where
$V_{2}=\sum_{i=1}^{n}\operatorname{Var}(W_{i})\leq\sum_{i=1}^{n}m_{2}(\theta_{i},w)$,
for $m_{2}(\theta_{i},w)=E_{\theta}(\beta(X_{i},w)^{2})$. In view of the
definition (56) of $w_{-}$, we have

$E=\sum_{i\in
S_{\theta}}m_{1}(\theta_{i},w_{-})-(n-s_{n})\tilde{m}(w_{-})=\nu(n-s_{n})\tilde{m}(w_{-}).$

We also note, using the bounds on $m_{2}$ in Lemma 16 that for some constants
$C,M_{0}>0$ and $n$ larger than some universal threshold,

$\displaystyle V_{2}$ $\displaystyle\leq\sum_{i\leq
n:|\theta_{i}|>M_{0}}m_{2}(\theta_{i},w_{-})+\sum_{i\leq
n:\lvert\theta_{i}\rvert\leq M_{0}}m_{2}(\theta_{i},w_{-})$
$\displaystyle\leq\frac{C}{w_{-}}\sum_{i\in
S_{\theta}:\lvert\theta_{i}\rvert>M_{0}}m_{1}(\theta_{i},w_{-})+C\sum_{i\leq
n:\lvert\theta_{i}\rvert\leq
M_{0}}\frac{\overline{\Phi}(\zeta(w_{-})-|\theta_{i}|)}{w_{-}^{2}}$
$\displaystyle\leq\frac{C}{w_{-}}\sum_{i\in
S_{\theta}}m_{1}(\theta_{i},w_{-})-\frac{C}{w_{-}}\sum_{i\in
S_{\theta}:\lvert\theta_{i}\rvert\leq
M_{0}}m_{1}(\theta_{i},w_{-})+Cs_{n}\frac{\overline{\Phi}(\zeta(w_{-})-M_{0})}{w_{-}^{2}}+Cn\frac{\overline{\Phi}(\zeta(w_{-}))}{w_{-}^{2}},$

with $\zeta$ defined as in (55). For the first term we use the definition (56)
of $w_{-}$, and for the second we use that $m_{1}(\theta_{i},w_{-})$ is
bounded below by a (negative) constant. By a standard normal tail bound
(included in Lemma 23), the bounds on $w_{-}$, the fact that
$\sqrt{2\log(1/w_{-})}\leq\zeta(w_{-})\lesssim\sqrt{\log(n/s_{n})}$ as $n\to
0$ (Lemmas 9 and 17) and that $\tilde{m}(w_{-})\asymp\zeta(w_{-})^{-1}$ (Lemma
15), we deduce for some constant $M_{1}$ that

$\overline{\Phi}(\zeta(w_{-})-M_{0})\asymp\frac{\phi(\zeta(w_{-})-M_{0})}{\zeta(w_{-})}\lesssim
w_{-}\tilde{m}(w_{-})e^{M_{1}\sqrt{\log(n/s_{n})}},$

so that, bounding $M_{1}\sqrt{\log(n/s_{n})}$ by $\log(n/s_{n})$, for $n$
large the third term is upper bounded by a constant multiple of

$s_{n}w_{-}^{-1}\tilde{m}(w_{-})e^{M_{1}\sqrt{\log(n/s_{n})}}\leq
nw_{-}^{-1}\tilde{m}(w_{-}).$

For the fourth term, by the same normal tail bound and the definition of
$\zeta$ we have
$\overline{\Phi}(\zeta(w_{-}))\asymp\phi(\zeta(w_{-}))/\zeta(w_{-})\asymp
w_{-}g(\zeta(w_{-}))/\zeta(w_{-})$, which is of order
$w_{-}(\zeta(w_{-}))^{-3}\asymp w_{-}/\zeta(w_{-})^{3}$, hence of order
$w_{-}\tilde{m}(w_{-})/\zeta(w_{-})^{2}$ because
$\tilde{m}(w_{-})\asymp\zeta(w_{-})^{-1}$. We deduce, recalling that
$s_{n}=o(n)$ implies automatically that $s_{n}\ll
n(\log(n/s_{n}))^{-1/2}\asymp n\tilde{m}(w_{-})$,

$V_{2}\lesssim
nw_{-}^{-1}\tilde{m}(w_{-})+w_{-}^{-1}s_{n}+nw_{-}^{-1}\tilde{m}(w_{-})/\zeta(w_{-})^{2}\lesssim
nw_{-}^{-1}\tilde{m}(w_{-}),$

so that

$\frac{V_{2}+\mathcal{M}E/3}{E^{2}}\lesssim\frac{nw_{-}^{-1}\tilde{m}(w_{-})}{(\nu(n-s_{n})\tilde{m}(w_{-}))^{2}}+\frac{1}{\nu
w_{-}(n-s_{n})\tilde{m}(w_{-})}\lesssim\frac{1}{\nu^{2}nw_{-}\tilde{m}(w_{-})}.$

This implies that $P_{\theta_{0}}(\hat{w}<w_{-})\leq
e^{-c\nu^{2}nw_{-}\tilde{m}(w_{-})}$ for some constant $c>0$. Now, by Lemma 9,
we have $nw_{-}\tilde{m}(w_{-})\asymp s_{n}$, yielding the desired bound on
the probability. ∎

We adapt Lemmas 9 and 10 slightly to apply even when $\Lambda_{\infty}=1$ or
$\lvert S_{\theta}\rvert<s_{n}$, in order to accommodate the settings of
Theorems 7 and 8.

######  Lemma 11.

Consider the setting of Theorem 8. For constants $C,D>0$ let
$\omega_{1}=C(\sigma_{n}/n)(\log(n/\sigma_{n}))^{1/2}$, where
$\sigma_{n}=\max(s_{n},D\log n)$. Then if $C$ and $D$ are suitably large, for
all $n$ large enough we have

$\sup_{\theta\in\Theta_{b}^{\prime}}P_{\theta}(\hat{w}>\omega_{1})\leq
n^{-1}.$ (64)

###### Proof.

We begin with a corresponding upper bound to (63). Using the bounds, found in
Lemma 15, that for some $c_{0},\omega_{0}>0$, any $\mu\in\mathbb{R}$ and any
$w<\omega_{0}$

$\tilde{m}(w)\geq c_{0}(\log(1/w))^{-1/2},\quad m_{1}(\mu,w)\leq 1/w,$

we note that
$\tilde{m}(\omega_{1})\asymp(\log(1/\omega_{1}))^{-1/2}\asymp(\log(n/\sigma_{n}))^{-1/2}$
because $n/\sigma_{n}\to\infty$, and we further deduce that for for $n$ large
enough, for any $\theta\in\Theta^{\prime}_{b}$ with support $S_{\theta}$ of
size $s_{\theta}\leq s_{n}$ we have

$\sum_{i\in
S_{\theta}}m_{1}(\theta_{i},\omega_{1})<(1-\nu)(n-s_{\theta})\tilde{m}(\omega_{1}),$
(65)

provided the constant $C$ in the definition of $\omega_{1}$ is large enough.

We now argue as in proving Lemma 10. Let $S=L^{\prime}$, for $L$ as in (47),
denote the score function. Necessarily $S(\hat{w})\geq 0$ or $\hat{w}=0$, and
we deduce that $\\{\hat{w}>\omega_{1}\\}\subset\\{S(\omega_{1})>0\\}$, hence

$P_{\theta}(\hat{w}>\omega_{1})\leq
P_{\theta}(S(\omega_{1})-E_{\theta}S(\omega_{1})>-E_{\theta}S(\omega_{1}))\\\
=P_{\theta}\left(\sum_{i=1}^{n}W_{i}>-E\right),$

where $W_{i}=\beta(X_{i},\omega_{1})-m_{1}(\theta_{i},\omega_{1})$ and
$E=E_{\theta}S(\omega_{1})=\sum_{i=1}^{n}m_{1}(\theta_{i},\omega_{1})$. For
$n$ large $|W_{i}|\leq\mathcal{M}:=2/\omega_{1}$ a.s. (see Lemma 14), so that
we may scale the variables $W_{i}$ to apply the Bernstein inequality (Lemma 5)
and obtain

$\displaystyle P_{\theta}(\hat{w}>\omega_{1})\leq
e^{-0.5E^{2}/(V_{2}+\mathcal{M}E/3)},$

where
$V_{2}=\sum_{i=1}^{n}\operatorname{Var}(W_{i})\leq\sum_{i=1}^{n}m_{2}(\theta_{i},\omega_{1})$,
for $m_{2}(\theta_{i},w)=E_{\theta}(\beta(X_{i},w)^{2})$. In view of (65),

$-E=(n-s_{\theta})\tilde{m}(\omega_{1})-\sum_{i\in
S_{\theta}}m_{1}(\theta_{i},\omega_{1})>\nu(n-s_{\theta})\tilde{m}(\omega_{1}).$

Arguing as in the proof of Lemma 10, one obtains

$V_{2}\lesssim\omega_{1}^{-1}\sum_{i\in
S_{\theta}}m_{1}(\theta_{i},\omega_{1})+\omega_{1}^{-1}s_{n}+n\omega_{1}^{-1}\tilde{m}(\omega_{1})/\zeta(\omega_{1})^{2}\lesssim
n\omega_{1}^{-1}\tilde{m}(\omega_{1}),$

with the last bound following from (65). Inserting the bounds for $E,$ $V_{2}$
and $\mathcal{M}$ into the obtained bound on $P_{\theta}(\hat{w}>\omega_{1})$
yields for a constant $c=c(\nu)$

$P_{\theta}(\hat{w}>\omega_{1})\leq e^{-cn\omega_{1}\tilde{m}(\omega_{1})}.$

Recalling that $\tilde{m}(\omega_{1})\asymp(\log(n/\sigma_{n}))^{-1/2}$ we see
for $c^{\prime}$ not depending on $D$ that $P_{\theta}(\hat{w}>\omega_{1})\leq
e^{-c^{\prime}\sigma_{n}}$, and (64) follows upon choosing $D=D(c^{\prime})$
large enough. ∎

###  C.3 Proof of Theorem 7 ($\ell$-value upper bound)

Suppose $\theta\in\Theta_{b}$ and let us write the classification loss
$\operatorname{L_{C}}(\theta,\varphi^{\hat{\ell}})$ as the sum $V+(s_{n}-S)$,
where as in the proof of Theorem 5 we write $V=V(\hat{w})=\sum_{i\not\in
S_{\theta}}\varphi^{\hat{\ell}}_{i}$, $S=S(\hat{w})=\sum_{i\in
S_{\theta}}{\varphi^{\hat{\ell}}_{i}}$, with $S_{\theta}=\\{i:\theta_{i}\neq
0\\}$ denoting the support of $\theta$. It suffices to show that uniformly
over $\theta\in\Theta_{b}$, for some positive sequences $\delta_{n}\to 0$ and
$\nu_{n}\to 0$,

$\displaystyle
P_{\theta}\left[s_{n}-S\geq(\overline{\Phi}(b)+\delta_{n})s_{n}\right]$
$\displaystyle=o(1),$ (66) $\displaystyle
P_{\theta}\big{[}V>\nu_{n}s_{n}\big{]}$ $\displaystyle=o(1),$ (67)

To prove (66), for $\bm{b}=(b,b,\dots)$, we may embed the setting of Theorem 7
into that of Theorem 5(i). In the case of a fixed $b\in\mathbb{R}$, recall
that we argued in proving Theorem 5 (see before (58)) that on the event
$\hat{w}\geq w_{-}$, we have $s_{n}-S\leq N$, for $N$ a Poisson binomial $N$
with parameter vector $\bm{p}=(\overline{\Phi}(b_{j})+\delta_{n})_{j\leq
s_{n}}$ and for a sequence $\delta_{n}\to 0$. Then (66) follows by recalling
that $P(\hat{w}<w_{-})\to 0$ from Lemma 10, and by applying Bernstein’s
inequality (Lemma 5). In the case $b=b_{n}\to+\infty$ the same argument
applies upon replacing $\overline{\Phi}(b)$ by
$\Lambda_{\infty}=\lim\overline{\Phi}(b)=0$. In the case $b=b_{n}\to-\infty$,
since $S\geq 0$ we automatically have

$P_{\theta}\big{[}s_{n}-S\geq(1+\delta_{n})s_{n}\big{]}=0,$

so that (66) holds in all cases (with suitable substitutions).

To prove (67), one could similarly use the bound (61). Here, to allow for the
case $b=b_{n}\to-\infty$, we adapt this bound by appealing to Lemma 11, which
yields the existence of constants $C,D$ such that for large $n$

$P_{\theta}(\hat{w}>\omega_{1})\leq
n^{-1},\quad\omega_{1}=C\frac{\sigma_{n}}{n}\big{(}\log(n/\sigma_{n})\big{)}^{1/2},\leavevmode\nobreak\
\sigma_{n}=\max(s_{n},D\log n).$

Then, writing

$V^{\prime}=\\#\\{i\not\in S_{\theta}:\ell_{i,\omega_{1}}<t\\},$

we apply Lemmas 13 and 18 as in proving Theorem 5 to deduce that

$E_{\theta}V^{\prime}\lesssim
n\omega_{1}\log(1/\omega_{1})^{-3/2}\lesssim\sigma_{n}/(\log(n/\sigma_{n})),$

where we have used that $n/\sigma_{n}\to\infty$ to see that
$\log(1/\omega_{1})\asymp\log(n/\sigma_{n})$. When $\sigma_{n}=D\log(n)$ we
note that $\sigma_{n}/\log(n/\sigma_{n})$ is upper bounded by a constant. For
some $C^{\prime}>0$ we therefore have

$E_{\theta}V\leq nP_{\theta}(\hat{w}>\omega_{1})+E_{\theta}V^{\prime}\leq
1+E_{\theta}V^{\prime}\leq
C^{\prime}\max\Big{(}1,\frac{s_{n}}{\log(n/s_{n})}\Big{)}=o(s_{n}),$ (68)

where we have used that $s_{n}\to\infty$ and $n/s_{n}\to\infty$. Applying
Markov’s inequality we deduce
$P_{\theta}[V>\nu_{n}s_{n}]\leq\nu_{n}^{-1}s_{n}^{-1}E_{\theta}V$ tends to
zero if $\nu_{n}$ tends to zero sufficiently slowly. This proves (67),
including the cases $b=b_{n}\to\pm\infty$, and thus concludes the proof.

######  Remark 7.

A straightforward corollary of the above proof shows that the $\ell$-value
procedure is sparsity preserving. It suffices to show that
$P(V+S>2s_{n})=o(1)$, or that $P(V>s_{n})=o(1)$, which follows from the proof,
taking $\nu_{n}=1$.

######  Remark 8.

Let us provide an alternative proof of the $\ell$-value upper bound part of
Theorem 8, similar in spirit to the just obtained in-probability bounds. Write
$S_{\theta}=\\{i:\theta_{i}\neq 0\\}$, $s_{\theta}=\lvert S_{\theta}\rvert$,
$V=V(\hat{w})=\sum_{i\not\in S_{\theta}}\varphi^{\hat{\ell}}_{i}$ and
$S=S(\hat{w})=\sum_{i\in S_{\theta}}\varphi^{\hat{\ell}}_{i}$, and note as in
the previous proof of Theorem 8 (in Appendix A.4) that it suffices to show

$\sup_{\theta\in\Theta_{b}^{\prime}(s_{n})}E_{\theta}V=o(s_{n}),\quad\sup_{\theta\in\Theta_{b}^{\prime}(s_{n})}E_{\theta}[s_{\theta}-S]\leq
s_{n}\overline{\Phi}(b)+o(s_{n}).$

The first of these follows from taking a supremum in (68), whose proof we note
applies for $\theta\in\Theta_{b}^{\prime}(s_{n})$ not just
$\theta\in\Theta_{b}(s_{n})$.

The second is trivial in the case $b=b_{n}\to-\infty$ since $0\leq
s_{\theta}-S\leq s_{\theta}\leq s_{n}$ for
$\theta\in\Theta_{b}^{\prime}(s_{n})$. In the cases $b\in\mathbb{R}$ fixed and
$b=b_{n}\to+\infty$, note firstly an examination of the proofs of Lemmas 9 and
10 reveals that for some constants $c,c^{\prime}>0$, for any
$\theta\in\Theta_{b}(s)$ with $s\leq s_{n}$ we have

$P_{\theta}(\hat{w}<w_{-})\leq e^{-cs},\quad
w_{-}:=c^{\prime}(s/n)(\log(n/s))^{1/2}.$

In this setting the bound (58) reads that, for some sequence $\delta_{n}\to 0$
which can be chosen independently of $s$,

$\displaystyle E_{\theta}[s-S]$ $\displaystyle\leq
sP_{\theta}(\hat{w}<w_{-})+s(\overline{\Phi}(b)+\delta_{n})$
$\displaystyle\leq se^{-cs}+s(\overline{\Phi}(b)+\delta_{n})\leq
C(c)+s_{n}\overline{\Phi}(b)+o(s_{n}).$

The bound at stake then follows by taking the maximum over $0\leq s\leq s_{n}$
in the last display.

###  C.4 Background material for the $\ell$-value procedure

We gather results from [17] which are used in the proofs for this appendix.
Some of these results were originally formulated with dependence on $g$ and a
related parameter $\kappa\in[1,2]$; as in [1], we simplify such expressions
here by substituting the explicit form (45) for $g$, which has $\kappa=2$, and
using the bounds $\sup_{x}\lvert g(x)\rvert\leq 1/\sqrt{2\pi}$ and, for
$\lvert x\rvert\geq 2$, $x^{-2}/(2\sqrt{2\pi})\leq g(x)\leq
x^{-2}/\sqrt{2\pi}$.

######  Lemma 12.

The following functions are strictly decreasing (with probability 1 in the
case of random functions).

$\displaystyle w$ $\displaystyle\mapsto S(w)=L^{\prime}(w),$ $\displaystyle w$
$\displaystyle\mapsto\ell_{i,w}(X),$ $\displaystyle w$
$\displaystyle\mapsto-\tilde{m}(w),$ $\displaystyle w$ $\displaystyle\mapsto
m_{1}(\tau,w),\quad\tau\in\mathbb{R}\text{ fixed,}$ $\displaystyle u$
$\displaystyle\mapsto\xi(u)=(\phi/g)^{-1}(u),$ $\displaystyle u$
$\displaystyle\mapsto\zeta(u).$

These monotonicity results can be found in [17], and see [1, Lemma 4] for most
proofs collected in one place.

######  Lemma 13 (Proposition 3 in [17]).

$P_{\theta}(\ell_{i,w}\leq t)\leq 2r(w,t)\xi(r(w,t))^{-3}$, where
$r(w,t)=wt(1-w)^{-1}(1-t)^{-1}$ and $\xi$ is as in (54).

######  Lemma 14 (Lemma S-20 in [17]).

Define $\beta(x,w)$ as in (50). Then there exists $c_{1}>0$ such that for any
$x\in\mathbb{R}$ and $w\in(0,1]$,
$\lvert\beta(x,w)\rvert\leq(\min(w,c_{1}))^{-1}$.

######  Lemma 15 (Lemmas S-21, S-23 and S-27 in [17], and using Lemma 17
below).

Define $\tilde{m}$ and $m_{1}$ as in (51), (52). Then $\tilde{m}$ is
continuous, non-negative and increasing. For fixed $\tau$ the function
$w\mapsto m_{1}(\tau,w)$ is continuous and decreasing. There exist
$\omega_{0},c,c^{\prime}>0$ such that for all $\tau\in\mathbb{R}$ and all
$w<\omega_{0}$

$\displaystyle c(\log(1/w))^{-1/2}$ $\displaystyle\leq\tilde{m}(w)$
$\displaystyle\leq c^{\prime}(\log(1/w))^{-1/2},$
$\displaystyle\phantom{\leq}m_{1}(\tau,w)$ $\displaystyle\leq 1/w.$

There exist constants $M_{0},C_{1}>0$ and $\omega_{0}\in(0,1)$ such that for
any $w\leq\omega_{0}$, and any $\mu\geq M_{0}$, with
$T_{\mu}(w)=1+\lvert\mu\rvert^{-1}\lvert\zeta(w)-\lvert\mu\rvert\rvert$,

$\displaystyle m_{1}(\mu,w)$ $\displaystyle\geq
C_{1}\frac{\overline{\Phi}(\zeta(w)-\mu)}{w}T_{\mu}(w).$

######  Lemma 16 (Lemma S-26 and Corollary S-28 in [17]).

Define $m_{2}$ as in (53). There exist constants $C>0$ and
$\omega_{0}\in(0,1)$ such that for any $w\leq\omega_{0}$ and any
$\mu\in\mathbb{R}$,

$m_{2}(\mu,w)\leq C\frac{\overline{\Phi}(\zeta(w)-\lvert\mu\rvert)}{w^{2}}.$

There exist $M_{0},C^{\prime}>0$ and $\omega_{0}\in(0,1)$ such that for any
$w\leq\omega_{0}$ and any $\mu\geq M_{0}$

$m_{2}(\mu,w)\leq C^{\prime}\frac{m_{1}(\mu,w)}{w}.$

######  Lemma 17 (Lemma S-14 in [17]).

Consider $\zeta(w)$ as in (55). Then $\zeta(w)\sim(2\log(1/w))^{1/2}$ as $w\to
0$. More precisely, for constants $c,C\in\mathbb{R}$ and for $w$ small enough,

$(2\log(1/w)+2\log\log(1/w)+c)^{1/2}\leq\zeta(w)\leq(2\log(1/w)+2\log\log(1/w)+C)^{1/2}.$

######  Lemma 18 (Lemma S-12 in [17]).

Consider $\xi$ as in (54). Then $\xi(u)\sim(2\log(1/u))^{1/2}$, and more
precisely, for $u$ small enough,

$\displaystyle\xi(u)$ $\displaystyle\geq\Big{(}2\log(1/u)+2\log\log(1/u)+2\log
2\Big{)}^{1/2}$ $\displaystyle\xi(u)$
$\displaystyle\leq\Big{(}2\log(1/u)+2\log\log(1/u)+6\log 2\Big{)}^{1/2}.$

The above bounds come from Lemma S-12 in [17]

$\displaystyle\xi(u)$ $\displaystyle\geq\left(-2\log u-2\log
g\left(\sqrt{-2\log(Cu)}\right)-\log(2\pi)\right)^{1/2};$
$\displaystyle\xi(u)$ $\displaystyle\leq\left(-2\log u-2\log
g\left(\sqrt{-4\log u}\right)-\log(2\pi)\right)^{1/2},$

where $C=\sqrt{2\pi}\sup_{x}\lvert g(x)\rvert$, by using
$x^{-2}/(2\sqrt{2\pi})\leq g(x)\leq x^{-2}/(\sqrt{2\pi})$ for $\lvert
x\rvert\geq 2$. For instance, for the lower bound we use

$\displaystyle-2\log g\left(\sqrt{-2\log(Cu)}\right)-\log(2\pi)$
$\displaystyle\geq 2\log(\sqrt{2\pi})+2\log(-2\log(Cu))-\log(2\pi)$
$\displaystyle\geq 2\log(2)+2\log(\log(1/u)+\log(1/C))$ $\displaystyle\geq
2\log 2+2\log(\log(1/u)),$

where the last inequality holds because $C\leq 1$.

##  Appendix D Materials for BH procedure

###  D.1 Definition

Recall that the BH procedure of level $\alpha$ is defined as follows (see,
e.g., [40]):

$\displaystyle\varphi^{BH}_{\alpha}$
$\displaystyle=(\mathbf{1}\\{|X_{i}|\geq\hat{t}\\})_{1\leq i\leq n};$ (69)
$\displaystyle\hat{t}$
$\displaystyle=\min\\{t\in\mathbb{R}\cup\\{-\infty\\}\>:\>\hat{G}_{n}(t)\geq
2\overline{F}(t)/\alpha\\};$ $\displaystyle\hat{G}_{n}(t)$
$\displaystyle=n^{-1}\sum_{i=1}^{n}\mathbf{1}\\{|X_{i}|\geq t\\}.$

###  D.2 Proof of Theorem 5(ii)

Let us prove, under the condition $\alpha=\alpha_{n}=o(1)$ with
$-\log\alpha=o((\log(n/s_{n}))^{1-1/\zeta})$, that

$\sup_{\theta\in\Theta_{\bm{b}}}\mathfrak{R}(\theta,\varphi^{BH}_{\alpha})=\sup_{\theta\in\Theta_{\bm{b}}}\operatorname{FNR}(\theta,\varphi^{BH}_{\alpha})+o(1)=\Lambda_{\infty}+o(1).$
(70)

The proof of Theorem 5(ii) follows because under polynomial sparsity, the
condition $-\log\alpha=o((\log(n/s_{n}))^{1-1/\zeta})$ is satisfied if
$-\log\alpha=o((\log n)^{1-1/\zeta})$.

First, by [8, 9] we have for all $\theta\in\Theta_{\bm{b}}$,

$\displaystyle\operatorname{FDR}(\theta,\varphi^{BH}_{\alpha})=\alpha(n-|S_{\theta}|)/n\leq\alpha,$
(71)

where $S_{\theta}$ denotes the support of $\theta$. This entails, since
$\alpha$ tends to $0$,

$\sup_{\theta\in\Theta_{\bm{b}}}\mathfrak{R}(\theta,\varphi^{BH}_{\alpha})=\sup_{\theta\in\Theta_{\bm{b}}}\operatorname{FNR}(\theta,\varphi^{BH}_{\alpha})+o(1).$

By Theorem 4, we have

$\sup_{\theta\in\Theta_{\bm{b}}}\mathfrak{R}(\theta,\varphi^{BH}_{\alpha})\geq\inf_{\varphi}\sup_{\theta\in\Theta_{\bm{b}}}\mathfrak{R}(\theta,\varphi)=\Lambda_{\infty}+o(1).$

It remains to prove

$\displaystyle\sup_{\theta\in\Theta_{\bm{b}}}\operatorname{FNR}(\theta,\varphi^{BH}_{\alpha})\leq\Lambda_{\infty}+o(1).$
(72)

To prove this bound we rely on the following inequalities: for all $t\geq 0$,

$\displaystyle P_{\theta}(\hat{t}>t)$ $\displaystyle\leq
P_{\theta}(\hat{G}_{n}(t)<2\overline{F}(t)/\alpha)=P_{\theta}(\hat{G}_{n}(t)-G_{n}(t)<2\overline{F}(t)/\alpha-
G_{n}(t)),$

where
$G_{n}(t)=E_{\theta}\hat{G}_{n}(t)=(1-s_{n}/n)2\overline{F}(t)+n^{-1}\sum_{i\in
S_{\theta}}(\overline{F}(t+\theta_{i})+\overline{F}(t-\theta_{i}))$.

Let $a_{n}^{*}=(\zeta\log(n/s_{n}))^{1/\zeta}$. Note that
$G_{n}(t)\geq(1-s_{n}/n)2\overline{F}(t)+(s_{n}/n)s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t-a_{n}^{*}-b_{j})$
and observe that $t\mapsto
s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t-a_{n}^{*}-b_{j})/\overline{F}(t)$
is a continuous increasing bijection from $[0,\infty]$ to $[1,\infty)$ by
Lemma 19. Hence, denoting by $t^{*}_{n}>0$ the only point $t>0$ (which exists
because $3/\alpha-2>1$) such that
$(1-s_{n}/n)2\overline{F}(t)+(s_{n}/n)s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t-a_{n}^{*}-b_{j})=3\overline{F}(t)/\alpha$,
we obtain

$\displaystyle P_{\theta}(\hat{t}>t^{*}_{n})$ $\displaystyle\leq
P_{\theta}(\hat{G}_{n}(t^{*}_{n})-G_{n}(t^{*}_{n})<-\overline{F}(t^{*}_{n})/\alpha)$
$\displaystyle\leq\exp\left(-0.5\frac{n^{2}\overline{F}^{2}(t^{*}_{n})/\alpha^{2}}{nG_{n}(t^{*}_{n})+(n/3)\overline{F}(t^{*}_{n})/\alpha}\right)$
$\displaystyle\leq\exp\left(-0.5\frac{n\overline{F}^{2}(t^{*}_{n})/\alpha^{2}}{s_{n}/n+(2\alpha+1/3)\overline{F}(t^{*}_{n})/\alpha}\right),$

by using Bernstein’s inequality (Lemma 5) and the fact that $G_{n}(t)\leq
2\overline{F}(t)+s_{n}/n$ for all $t$. Now, by Lemma 19 (using the conditions
on $\alpha=\alpha_{n}$), we have that $t^{*}_{n}\to\infty$ with
$t_{n}^{*}-a_{n}^{*}=o(1)$. Hence, with $C_{f}=C_{f}(\zeta)$ denoting the
Lipschitz constant of the noise c.d.f. $F$,

$\displaystyle\bigg{\lvert}s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t_{n}^{*}-a_{n}^{*}-b_{j})-s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})\bigg{\rvert}\leq
C_{f}\>\lvert t_{n}^{*}-a_{n}^{*}\rvert.$

This entails

$s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t_{n}^{*}-a_{n}^{*}-b_{j})\to
1-\Lambda_{\infty},$ (73)

which is positive by assumption. Since by definition of $t_{n}^{*}$ and
$\alpha=o(1)$ we have
$\overline{F}(t^{*}_{n})/\left(s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t_{n}^{*}-a_{n}^{*}-b_{j})\right)\asymp\alpha
s_{n}/n$, this gives $\overline{F}(t^{*}_{n})\asymp\alpha s_{n}/n$ and

$\displaystyle P_{\theta}(\hat{t}>t^{*}_{n})$ $\displaystyle\leq e^{-cs_{n}},$
(74)

for some universal constant $c>0$. It follows that

$\displaystyle\operatorname{FNR}(\theta,\varphi^{BH}_{\alpha})\leq
s_{n}^{-1}E_{\theta}\left(\sum_{i\in
S_{\theta}}\mathbf{1}\\{|X_{i}|<t^{*}_{n}\\}\right)+e^{-cs_{n}}.$ (75)

Now, since for all $i\in S_{\theta}$,
$P_{\theta}(|X_{i}|<t^{*}_{n})=1-P_{\theta}(|X_{i}|\geq t^{*}_{n})\leq
1-\overline{F}(t_{n}^{*}-|\theta_{i}|)$,

$s_{n}^{-1}E_{\theta}\left(\sum_{i\in
S_{\theta}}\mathbf{1}\\{|X_{i}|<t^{*}_{n}\\}\right)\leq
1-s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t_{n}^{*}-a_{n}^{*}-b_{j})\to\Lambda_{\infty},$
(76)

by (73). We have shown (72), and this finishes the proof of Theorem 5(ii).

######  Remark 9.

The following convergence rate can be obtained when $\Lambda_{\infty}<1$: for
a vector $\bm{b}$ that has coordinates with a fixed value in $\mathbb{R}$, and
taking $\alpha\asymp 1/(\log(n/s_{n}))^{1-1/\zeta}$, we have

$\sup_{\theta\in\Theta_{\bm{b}}}\mathfrak{R}(\theta,\varphi^{BH}_{\alpha})-\Lambda_{n}(\bm{b})\lesssim
1/(\log(n/s_{n}))^{1-1/\zeta}+e^{-cs_{n}}.$

Indeed, from the computations of the above proof, we get

$\displaystyle\sup_{\theta\in\Theta_{\bm{b}}}\mathfrak{R}(\theta,\varphi^{BH}_{\alpha})$
$\displaystyle\leq\alpha+1-s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t_{n}^{*}-a_{n}^{*}-b_{j})+e^{-cs_{n}}$
$\displaystyle\leq\alpha+1-s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}((t_{n}^{*}-a_{n}^{*})_{+}-b_{j})+e^{-cs_{n}}$
$\displaystyle\leq\Lambda_{n}(\bm{b})+\alpha+O((t_{n}^{*}-a_{n}^{*})_{+})+e^{-cs_{n}},$

and the claim follows from Lemma 19 point $(ii)$.

###  D.3 Proof of Theorem 7 (BH upper bound)

Consider the BH procedure $\varphi^{BH}_{\alpha}$ (69), for
$\alpha=\alpha_{n}=o(1)$ with $-\log\alpha=o((\log(n/s_{n}))^{1/2})$.
Recalling the definition (25) of the classification loss $L_{C}$, let us prove
that for any fixed real $b$ and any $\eta>0$,

$\sup_{\theta\in\Theta_{b}}P_{\theta}\left[\operatorname{L_{C}}(\theta,\varphi^{BH}_{\alpha})\geq(\overline{\Phi}(b)+\eta)s_{n}\right]=o(1),$
(77)

and that the same holds with $\overline{\Phi}(b)$ replaced by 0 when
$b=b_{n}\to+\infty$ or by 1 when $b=b_{n}\to-\infty$. This entails the BH part
of Theorem 7 under polynomial sparsity (11), because $-\log\alpha=o((\log
n)^{1/2})$ implies $-\log\alpha=o((\log(n/s_{n}))^{1/2})$ in that case.

Fix $\theta\in\ell_{0}[s_{n}]$ and denote by
$V=\sum_{i=1}^{n}\mathbf{1}\\{\theta_{i}=0\\}\mathbf{1}\\{\varphi_{i}^{BH}\neq
0\\}$ the number of false discoveries of $\varphi^{BH}$ and by
$W=\sum_{i=1}^{n}\mathbf{1}\\{\theta_{i}\neq
0\\}\mathbf{1}\\{\varphi_{i}^{BH}=0\\}$ the number of false non-discoveries of
$\varphi^{BH}$. Assume first $b\in\mathbb{R}$. We have

$\displaystyle
P_{\theta}\left[\operatorname{L_{C}}(\theta,\varphi^{BH}_{\alpha})\geq(\overline{\Phi}(b)+\eta)s_{n}\right]\leq
P_{\theta}\left[V\geq\eta s_{n}/2\right]+P_{\theta}\left[W\geq
s_{n}\overline{\Phi}(b)+\eta s_{n}/2\right].$

We have by Markov’s inequality and Lemma 20,

$\displaystyle P_{\theta}\left[V\geq\eta
s_{n}/2\right]\leq(\eta/2)^{-1}\frac{E_{\theta}V}{s_{n}}\leq(\eta/2)^{-1}\left(\frac{\alpha}{1-\alpha}+\frac{\alpha}{s_{n}(1-\alpha)^{2}}\right),$

hence $\sup_{\theta\in\Theta_{b}}P_{\theta}\left[V\geq\eta
s_{n}/2\right]=o(1)$. On the other hand, we have by using (74) (note that we
use $\Lambda_{\infty}=\overline{\Phi}(b)<1$ here)

$\displaystyle P_{\theta}\left[W\geq s_{n}\overline{\Phi}(b)+\eta
s_{n}/2\right]$ $\displaystyle=P_{\theta}\left[\sum_{i\in
S_{\theta}}\mathbf{1}\\{\lvert X_{i}\rvert<\hat{t}\\}\geq
s_{n}\overline{\Phi}(b)+\eta s_{n}/2\right]$ $\displaystyle\leq
P_{\theta}\left[\sum_{i\in S_{\theta}}\mathbf{1}\\{|X_{i}|<t_{n}^{*}\\}\geq
s_{n}\overline{\Phi}(b)+\eta s_{n}/2\right]+e^{-cs_{n}},$

where $t_{n}^{*}>0$ is defined as in Lemma 19, that is, as the only point
$t>0$ such that (78) holds. By (76), the random variable $\sum_{i\in
S_{\theta}}\mathbf{1}\\{\lvert X_{i}\rvert<t_{n}^{*}\\}$ is stochastically
upper-bounded by a Binomial distribution with parameter $s_{n}$ and
$q_{n}:=1-\overline{\Phi}(t_{n}^{*}-a_{n}^{*}-b)=\overline{\Phi}(b)+o(1)$ by
using Lemma 19. Applying Bernstein’s inequality (Lemma 5), we obtain

$\displaystyle P_{\theta}\left[\sum_{i\in S_{\theta}}\mathbf{1}\\{\lvert
X_{i}\rvert<t_{n}^{*}\\}\geq s_{n}\overline{\Phi}(b)+\eta s_{n}/2\right]$
$\displaystyle\leq P_{\theta}\left[\mathcal{B}(s_{n},q_{n})\geq
s_{n}\overline{\Phi}(b)+\eta s_{n}/2\right]$
$\displaystyle=P_{\theta}\left[\mathcal{B}(s_{n},q_{n})-s_{n}q_{n}\geq
s_{n}(\overline{\Phi}(b)-q_{n})+\eta s_{n}/2\right]$
$\displaystyle\leq\exp\left(-0.5s_{n}\frac{(\overline{\Phi}(b)-q_{n}+\eta/2)^{2}}{q_{n}+(\overline{\Phi}(b)-q_{n}+\eta/2)/3}\right)\leq
e^{-c^{\prime}s_{n}},$

for $n$ large enough and some constant $c^{\prime}>0$ only depending on $\eta$
(using the bound $q_{n}\leq 1$). This gives (77) for $b\in\mathbb{R}$.

When $b=b_{n}\to+\infty$ (so $\overline{\Phi}(b)\to 0$) and $\eta\in(0,1)$,
the same techniques as above lead to

$P_{\theta}\left[\operatorname{L_{C}}(\theta,\varphi^{BH}_{\alpha})\geq\eta
s_{n}\right]\leq(\eta/2)^{-1}\left(\frac{\alpha}{1-\alpha}+\frac{\alpha}{s_{n}(1-\alpha)^{2}}\right)+e^{-cs_{n}}+P_{\theta}\left[\mathcal{B}(s_{n},q_{n})\geq\eta
s_{n}/2\right],$

and this again shows (77) (with $\overline{\Phi}(b)$ replaced by $0$) because

$P_{\theta}\left[\mathcal{B}(s_{n},q_{n})\geq\eta s_{n}/2\right]\leq
2q_{n}/\eta=o(1)$

by Markov’s inequality.

Finally, when $b=b_{n}\to-\infty$ (so $\overline{\Phi}(b)\to 1$), we directly
use $W\leq s_{n}$, so that

$\displaystyle
P_{\theta}\left[\operatorname{L_{C}}(\theta,\varphi^{BH}_{\alpha})\geq(1+\eta)s_{n}\right]\leq
P_{\theta}\left[V\geq\eta
s_{n}\right]\leq\eta^{-1}\left(\frac{\alpha}{1-\alpha}+\frac{\alpha}{s_{n}(1-\alpha)^{2}}\right),$

by using again Markov’s inequality and Lemma 20. This shows (77) (with
$\overline{\Phi}(b)$ replaced by $1$) in that case.

###  D.4 Useful lemmas

######  Lemma 19.

In the setting of Theorem 5 with $a_{n}^{*}=(\zeta\log(n/s_{n}))^{1/\zeta}$
(recall $\bm{b}\in\mathbb{R}^{s_{n}}$ is such that $b_{j}>-a_{n}^{*}$, $1\leq
j\leq s_{n}$), the map

$\Psi:t\mapsto
s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t-a_{n}^{*}-b_{j})/\overline{F}(t)$

is continuous increasing from $\mathbb{R}$ to $[1,\infty)$ ($n$ being kept
fixed).

Let $t^{*}_{n}>0$ be the unique point $t>0$ such that

$(1-s_{n}/n)2\overline{F}(t)+(s_{n}/n)s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t-a_{n}^{*}-b_{j})=3\overline{F}(t)/\alpha.$
(78)

Then the following holds when $\Lambda_{\infty}<1$:

  * (i)

Choosing $\alpha\to 0$ with $-\log\alpha=o((\log(n/s_{n}))^{1-1/\zeta})$, we
have $t^{*}_{n}-a_{n}^{*}\to 0$.

  * (ii)

Choosing $\alpha\asymp 1/(\log(n/s_{n}))^{1-1/\zeta}$, we moreover have

$(t_{n}^{*}-a_{n}^{*})_{+}\lesssim 1/(\log(n/s_{n}))^{1-1/\zeta}.$

Point $(ii)$ above allows us to obtain the convergence rate mentioned in
Remark 9.

The proof of Lemma 19 takes inspiration from Section S-2.3 in [36], but
requires new arguments, because here the model is not a mixture model, and
different signal strengths are allowed. Throughout the proof, we denote
$t_{n}^{*}$ by $t_{n}$ for short. First observe that $-\log\overline{F}$ is
increasing on $\mathbb{R}$: its derivative is $f/\overline{F}>0$. It is also
strictly convex: its second derivative is
$(f^{\prime}\overline{F}+f^{2})/\overline{F}^{2}$ which, noting that
$f^{\prime}(x)=-\lvert x\rvert^{\zeta-1}f(x)\operatorname{sign}(x)$, is given
by

$(-\log\overline{F})^{\prime\prime}=\frac{f(x)\lvert
x\rvert^{\zeta-1}}{\overline{F}^{2}}\big{(}f(x)/\lvert
x\rvert^{\zeta-1}-\operatorname{sign}(x)\overline{F}(x)\big{)},$

which is positive (using Lemma 23 for the case $x>0$), so that
$f/\overline{F}$ is strictly increasing and $-\log\overline{F}$ is strictly
convex.

Let us write $\Psi_{j}(t)=\overline{F}(t-a_{n}^{*}-b_{j})/\overline{F}(t)$ for
$1\leq j\leq s_{n}$. Since the function $f/\overline{F}$ is increasing on
$\mathbb{R}$, for all $t\in\mathbb{R}$, we have

$(\log\Psi_{j})^{\prime}(t)=\frac{f(t)}{\overline{F}(t)}-\frac{f(t-a_{n}^{*}-b_{j})}{\overline{F}(t-a_{n}^{*}-b_{j})}>0$

hence each $\Psi_{j}$ is increasing and thus so is $\Psi$. Also, by Lemma 23,
when $t$ is large ($n$ is fixed here), we have

$\displaystyle(\log\Psi_{j})^{\prime}(t)$ $\displaystyle\geq
t^{\zeta-1}-(t-a_{n}^{*}-b_{j})^{\zeta-1}(1+(\zeta-1)t^{-\zeta})$
$\displaystyle=t^{\zeta-1}(1-(1-(a_{n}^{*}+b_{j})/t)^{\zeta-1}(1+(\zeta-1)t^{-\zeta}))\geq
t^{\zeta-1}(\zeta-1)(a_{n}^{*}+b_{j})/2,$

so that $\Psi_{j}(t)$ has limit $\infty$ when $t\to\infty$. This proves the
first claim of the lemma.

Now, let us denote

$\tau_{n}=\frac{3/\alpha-2(1-s_{n}/n)}{s_{n}/n};\>\>\>\tau_{n}^{*}=\Psi(a_{n}^{*})$

so that the threshold under study is $t_{n}=\Psi^{-1}\left(\tau_{n}\right)$
while the ‘oracle’ threshold is $a_{n}^{*}=\Psi^{-1}(\tau_{n}^{*})$. Let us
prove point $(i)$, that is, $t_{n}-a_{n}^{*}=o(1).$

#### Lower bounding $t_{n}$

Observe that $\tau_{n}\geq\frac{n}{s_{n}\alpha}\to\infty$ so that
$t_{n}=\Psi^{-1}\left(\tau_{n}\right)$ tends to $+\infty$. Since
$s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(t_{n}-a_{n}^{*}-b_{j})/\overline{F}(t_{n})=\tau_{n}$,
we have $\tau_{n}\overline{F}(t_{n})\leq 1$ and thus
$t_{n}\geq\overline{F}^{-1}(\tau_{n}^{-1})\geq\overline{F}^{-1}\left(\frac{s_{n}\alpha}{n}\right)$,
which by Lemma 23 implies

$t_{n}\geq\left(\zeta\log\left(\frac{n}{\alpha s_{n}}\right)-\zeta\log(\zeta
L_{\zeta})-(\zeta-1)\log\left(\zeta\log\left(\frac{n}{s_{n}\alpha}\right)-\zeta\log
L_{\zeta}\right)\right)^{1/\zeta}.$

By Taylor expanding this gives that for $n$ large $a_{n}^{*}-t_{n}\leq
c\frac{\log\log(n/(\alpha s_{n}))}{\log(n/(\alpha s_{n}))^{1-1/\zeta}}\leq
c^{\prime}\frac{\log\log(n/s_{n})}{\log(n/s_{n})^{1-1/\zeta}}$ for some
constants $c,c^{\prime}>0$ depending only of $\zeta$ (note that we have used
$-\log\alpha=o(\log(n/s_{n}))$).

#### Upper bounding $t_{n}$

Obtaining the upper bound on $t_{n}$ is slightly more involved and relies on
the following inequality: for all $\eta\geq 0$,

$\log\left(\frac{\Psi(a_{n}^{*}+\eta)}{\Psi(a_{n}^{*})}\right)\geq\log\left(\frac{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j}+\eta)}{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})}\right)+\eta\>(a_{n}^{*})^{\zeta-1}.$
(79)

The proof of (79) is as follows: since $-\log\overline{F}$ is increasing
convex, we have

$\displaystyle\log\left(\frac{\Psi(a_{n}^{*}+\eta)}{\Psi(a_{n}^{*})}\right)$
$\displaystyle=\log\left(\frac{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j}+\eta)}{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})}\right)-\log\left(\frac{\overline{F}(a_{n}^{*}+\eta)}{\overline{F}(a_{n}^{*})}\right)$
$\displaystyle\geq\log\left(\frac{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j}+\eta)}{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})}\right)+\eta\frac{f(a_{n}^{*})}{\overline{F}(a_{n}^{*})},$

and (79) comes from
$\frac{f(a_{n}^{*})}{\overline{F}(a_{n}^{*})}\geq(a_{n}^{*})^{\zeta-1}$ by
Lemma 23.

Now we propose to show the following claim: for any constant $B>0$, we have

$(t_{n}-a_{n}^{*})_{+}\leq\frac{(\log(\tau_{n}/\tau_{n}^{*}))_{+}-\log\left(\frac{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j}+B)}{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})}\right)}{(a_{n}^{*})^{\zeta-1}}$
(80)

provided that

$\log(\tau_{n}/\tau_{n}^{*})\leq\log\left(\frac{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j}+B)}{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})}\right)+B(a_{n}^{*})^{\zeta-1}.$
(81)

For this, assume $t_{n}\geq a_{n}^{*}$ (or equivalently
$\tau_{n}\geq\tau_{n}^{*}$), otherwise the result is trivial. We apply (79)
firstly with $\eta=B$ to obtain

$\displaystyle\log\left(\frac{\Psi(a_{n}^{*}+B)}{\Psi(a_{n}^{*})}\right)\geq\log\left(\frac{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j}+B)}{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})}\right)+B(a_{n}^{*})^{\zeta-1}\geq\log(\tau_{n}/\tau_{n}^{*})=\log\left(\frac{\Psi(t_{n})}{\Psi(a_{n}^{*})}\right),$

which gives $t_{n}\leq a_{n}^{*}+B$. Hence applying (79) a second time, now
with $\eta=t_{n}-a_{n}^{*}\in[0,B]$, we obtain

$\displaystyle\log\Big{(}\frac{\tau_{n}}{\tau_{n}^{*}}\Big{)}=\log\left(\frac{\Psi(t_{n})}{\Psi(a_{n}^{*})}\right)\geq\log\left(\frac{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j}+B)}{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})}\right)+(t_{n}-a_{n}^{*})(a_{n}^{*})^{\zeta-1},$

which proves the claim.

Let us now compute an upper bound for $\log(\tau_{n}/\tau_{n}^{*})$. By Lemma
23 and by definition of $\Psi$, we have

$\displaystyle\tau_{n}^{*}=\Psi(a_{n}^{*})$
$\displaystyle=s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})/\overline{F}(a_{n}^{*})\geq
s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})(a_{n}^{*})^{\zeta-1}/f(a_{n}^{*})$
$\displaystyle=L_{\zeta}s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})(a_{n}^{*})^{\zeta-1}n/s_{n}.$

Hence, we get, since $\tau_{n}\leq 3n/(s_{n}\alpha)$,

$\displaystyle\log(\tau_{n}/\tau_{n}^{*})$
$\displaystyle\leq\log\left(\frac{3/\alpha}{L_{\zeta}s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})(a_{n}^{*})^{\zeta-1}}\right)$
$\displaystyle=C-\log\left(s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})\right)+\log\left(\frac{1}{\alpha(\log(n/s_{n}))^{1-1/\zeta}}\right),$
(82)

for some constant $C>0$ only depending on $\zeta$. Now observe that, with
$C_{f}=C_{f}(\zeta)$ denoting the Lipschitz constant of the noise c.d.f. $F$,

$\displaystyle\log\left(\frac{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j}+B)}{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})}\right)\geq\log\left(1-\frac{C_{f}B}{s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})}\right)\geq-\log
2,$ (83)

for $n$ large by choosing for $B$ any positive constant smaller than
$(1-\Lambda_{\infty})/(2C_{f})$ (recall
$\lim_{n}s_{n}^{-1}\sum_{j=1}^{s_{n}}\overline{F}(-b_{j})=1-\Lambda_{\infty}>0$
by assumption). In particular, the condition (81) is satisfied when
$-\log\alpha=o((\log(n/s_{n}))^{1-1/\zeta})$ (and for this choice of $B$).
Hence, (80) holds. Now, combining the latter with the bounds (82) and (83), we
obtain that $(t_{n}-a_{n}^{*})_{+}=o(1)$, which establishes point $(i)$
(recall $(a_{n}^{*}-t_{n})_{+}=o(1)$ from the lower bound part). In addition,
when $\alpha\asymp 1/(\log(n/s_{n}))^{1-1/\zeta}$, we obtain by combining
again (80), (82) and (83), that $(t_{n}^{*}-a_{n}^{*})_{+}\lesssim
1/(\log(n/s_{n}))^{1-1/\zeta}$, which establishes point $(ii)$.

######  Lemma 20.

For all $\theta\in\mathbb{R}^{n}$, considering the BH procedure
$\varphi^{BH}_{\alpha}$ (69) at some level $\alpha\in(0,1)$, then
$V=\sum_{i=1}^{n}\mathbf{1}\\{\theta_{i}=0\\}\mathbf{1}\\{\varphi_{i}^{BH}\neq
0\\}$ satisfies

$E_{\theta}V\leq\frac{\alpha}{1-\alpha}\sum_{i=1}^{n}\mathbf{1}\\{\theta_{i}\neq
0\\}+\frac{\alpha}{(1-\alpha)^{2}}.$ (84)

###### Proof.

To prove (84), we follow the proof of Proposition 7.2 in [36] (or
alternatively, that of Lemma 7.1 in [10]). Recall that we have

$\displaystyle E_{\theta}V$
$\displaystyle=E_{\theta}\sum_{i=1}^{n}\mathbf{1}\\{\theta_{i}=0\\}\mathbf{1}\\{|X_{i}|\geq\hat{t}\\}$

with $\hat{t}=\max\\{t\in\mathbb{R}\cup\\{\infty\\}\>:\>\hat{G}_{n}(t)\geq
2\overline{F}(t)/\alpha\\}$ and
$\hat{G}_{n}(t)=n^{-1}\sum_{i=1}^{n}\mathbf{1}\\{|X_{i}|\geq t\\}$. Now
consider the BH procedure applied to the $X_{i}$’s where we have plugged
$X_{i}=+\infty$ on $S_{\theta}=\\{i\>:\>\theta_{i}\neq 0\\}$, that is, with
threshold
$\hat{t}^{0}=\max\\{t\in\mathbb{R}\cup\\{\infty\\}\>:\>|S_{\theta}|/n+n^{-1}\sum_{i\notin
S_{\theta}}\mathbf{1}\\{|X_{i}|\geq t\\}\geq 2\overline{F}(t)/\alpha\\}$.
Clearly, we have $\hat{t}^{0}\leq\hat{t}$, so that

$\displaystyle E_{\theta}V$ $\displaystyle\leq
E_{\theta}\sum_{i=1}^{n}\mathbf{1}\\{\theta_{i}=0\\}\mathbf{1}\\{|X_{i}|\geq\hat{t}^{0}\\}.$

Denote $n_{0}=|S_{\theta}^{c}|$ for short. From classical multiple testing
theory (see, e.g., Lemma 7.1 in [42]), the latter is the expected number of
rejections of the step-up procedure with critical values
$(\alpha(k+|S_{\theta}|)/n)_{1\leq k\leq n_{0}}$ and restricted to the
$p$-value set $\\{2\overline{F}(|X_{i}|),i\notin S_{\theta}\\}$. Now from
Lemma 4.2 in [22] (applied with “$n=n_{0}$”, “$\beta=\alpha$” and
“$\tau=\alpha/n$”), the latter equals

$\displaystyle\alpha\frac{n_{0}}{n}\sum_{i=0}^{n_{0}-1}{n_{0}-1\choose
i}(|S_{\theta}|+i+1)i!(\alpha/n)^{i}$ $\displaystyle\leq\alpha\sum_{i\geq
0}(|S_{\theta}|+i+1)\alpha^{i}=\frac{\alpha}{1-\alpha}|S_{\theta}|+\alpha/(1-\alpha)^{2}.$

∎

##  Appendix E Sparsity preserving procedures

Here we show that a large class of procedures are sparsity preserving in the
sense of Definition 1. The following lemma will be useful.

######  Lemma 21.

For any $\Theta\subset\ell_{0}[s_{n}]$ and any multiple testing procedure
$\varphi$, we have for any $u>1$ and $\theta\in\Theta$,

$P_{\theta}\left[\sum_{i=1}^{n}\varphi_{i}(X)>us_{n}\right]\leq
P_{\theta}\left[\operatorname{FDP}(\theta,\varphi)>1-u^{-1},\sum_{i=1}^{n}\varphi_{i}(X)\geq
s_{n}\right]\leq\frac{u}{u-1}\operatorname{FDR}(\theta,\varphi).$ (85)

In particular, we have

  * (i)

for any sequence $A=(A_{n})_{n}$ for which $A_{n}\geq 2$, any sequence of
procedures $\varphi$ with vanishing FDR in the sense of

$\sup_{\theta\in\Theta}\operatorname{FDR}(\theta,\varphi)=o(1)$

is sparsity preserving up to the multiplicative factor $A=(A_{n})_{n}$ over
$\Theta$, that is, $\varphi\in\mathcal{S}_{A}(\Theta)$ with Definition 1.

  * (ii)

for any sequence $A=(A_{n})_{n}$ for which $A_{n}\to\infty$, any sequence of
procedures $\varphi$ with an FDP bounded uniformly in probability away from
$1$ when at least $s_{n}$ rejections are made, in the sense that for some
fixed $t<1$,

$\sup_{\theta\in\Theta}P_{\theta}\left(\operatorname{FDP}(\theta,\varphi)>t,\sum_{i=1}^{n}\varphi_{i}(X)\geq
s_{n}\right)=o(1)$

is sparsity preserving up to the multiplicative factor $A=(A_{n})_{n}$ over
$\Theta$, that is, $\varphi\in\mathcal{S}_{A}(\Theta)$ with Definition 1.

An easy consequence of Lemma 21(i) is that the BH procedure taken at a level
$\alpha_{n}\to 0$ satisfies the sparsity preserving condition on
$\Theta=\ell_{0}[s_{n}]$ for any sequence $A=(A_{n})_{n}$ with $A_{n}\geq 2$
for all $n$ (recall that the FDR of this procedure is at most $\alpha_{n}$,
see (71)). By (30) the same is true of the oracle procedure defined after
(27). Using Theorem 1 of [17], the $\ell$-value procedure also has a vanishing
FDR (under polynomial sparsity), so that Lemma 21(i) also ensures that the
$\ell$-value procedure is sparsity preserving on $\Theta=\ell_{0}[s_{n}]$.
Recall that Remark 7 in Appendix 8 noted sparsity-preservingness of the
$\ell$-value procedure on $\Theta=\ell_{0}[s_{n}]$ without requiring
polynomial sparsity. Finally Corollary 5 to follow uses Lemma 21(ii) to prove
that the BH procedure at a fixed level $\alpha<1$ is sparsity preserving.

###### Proof.

Letting $V=\sum_{i=1}^{n}\mathbf{1}\\{\theta_{i}=0\\}\varphi_{i}(X)$, we have
for all $u>1$,

$\displaystyle\left\\{\sum_{i=1}^{n}\varphi_{i}(X)>us_{n}\right\\}$
$\displaystyle\subset\left\\{V>(u-1)s_{n}\right\\}\cap\left\\{\sum_{i=1}^{n}\varphi_{i}(X)\geq
s_{n}\right\\}$
$\displaystyle\subset\left\\{\frac{V}{V+s_{n}}>\frac{(u-1)s_{n}}{(u-1)s_{n}+s_{n}}\right\\}\cap\left\\{\sum_{i=1}^{n}\varphi_{i}(X)\geq
s_{n}\right\\}$
$\displaystyle\subset\left\\{\operatorname{FDP}(\theta,\varphi)>1-u^{-1}\right\\}\cap\left\\{\sum_{i=1}^{n}\varphi_{i}(X)\geq
s_{n}\right\\},$

because the function $x\in[0,\infty)\mapsto\frac{x}{x+s_{n}}$ is non-
decreasing. We conclude the proof of (85) by taking probabilities and using
Markov’s inequality. Parts $(i)$ and $(ii)$ are immediate consequences. ∎

######  Corollary 5.

The BH procedure taken at a fixed level $\alpha<1$ is sparsity preserving up
to any multiplicative factor $A=(A_{n})_{n}$ with $A_{n}\to\infty$ over any
parameter set $\Theta\subset\ell_{0}[s_{n}]$.

###### Proof.

From (69), letting $\hat{k}=\sum_{i=1}^{n}\varphi^{BH}_{i}$, we have
$2\overline{F}(\hat{t})=\alpha\hat{k}/n$. Thus, for all
$\epsilon\in(0,1-\alpha)$,

$\displaystyle
P_{\theta}\left(\operatorname{FDP}(\theta,\varphi^{BH})>\alpha+\epsilon,\sum_{i=1}^{n}\varphi_{i}^{BH}\geq
s_{n}\right)$
$\displaystyle=P_{\theta}\left(\sum_{i=1}^{n}\mathbf{1}\\{\theta_{i}=0\\}\mathbf{1}\\{2\overline{F}(|X_{i}|)\leq\alpha\hat{k}/n\\}>(\alpha+\epsilon)\hat{k},\hat{k}\geq
s_{n}\right)$ $\displaystyle\leq\sum_{k\geq
s_{n}}P_{\theta}\left(\sum_{i=1}^{n}\mathbf{1}\\{\theta_{i}=0\\}\mathbf{1}\\{2\overline{F}(|X_{i}|)\leq\alpha
k/n\\}>(\alpha+\epsilon)k\right)$ $\displaystyle\leq\sum_{k\geq
s_{n}}P_{\theta}\left(\sum_{i=1}^{n-s_{n}}\mathbf{1}\\{U_{i}\leq\alpha
k/n\\}>(\alpha+\epsilon)k\right)\leq\sum_{k\geq
s_{n}}P_{\theta}\left(\sum_{i=1}^{n}\mathbf{1}\\{U_{i}\leq\alpha
k/n\\}>(\alpha+\epsilon)k\right),$

for $U_{i}$, $1\leq i\leq n$, i.i.d. variables uniformly distributed on
$(0,1)$. Now, we have by Bernstein’s inequality (Lemma 5), for any $k\geq
s_{n}$,

$\displaystyle P_{\theta}\left(\sum_{i=1}^{n}\mathbf{1}\\{U_{i}\leq\alpha
k/n\\}>(\alpha+\epsilon)k\right)$ $\displaystyle\leq
P_{\theta}\left(\sum_{i=1}^{n}\mathbf{1}\\{U_{i}\leq\alpha k/n\\}-\alpha
k>\epsilon k\right)$ $\displaystyle\leq\exp\left(-0.5\frac{(\epsilon
k)^{2}}{\alpha k+\epsilon k/3}\right)\leq\exp(-c\epsilon^{2}k),$

for some universal constant $c>0$ (which can be chosen independent of $\alpha$
by bounding $\alpha$ by $1$). It follows that

$\displaystyle
P_{\theta}\left(\operatorname{FDP}(\theta,\varphi^{BH})>\alpha+\epsilon,\sum_{i=1}^{n}\varphi_{i}^{BH}\geq
s_{n}\right)$ $\displaystyle\leq\sum_{k\geq
s_{n}}\exp(-c\epsilon^{2}k)\leq(1-e^{-c\epsilon^{2}})^{-1}e^{-c\epsilon^{2}s_{n}}=o(1).$

The result follows from Lemma 21(ii). ∎

Let us now give an example of a (randomized) non-sparsity-preserving procedure
for which some FDR/FNR tradeoff is possible.

######  Example 3.

Given a real $b$ and for $\varphi^{*}$ a procedure satisfying (12), define a
(randomized) procedure $\tilde{\varphi}$ as follows: given a Bernoulli
variable $Z$ with success probability $\pi\in[0,1]$, let

$\tilde{\varphi}=\tilde{\varphi}(X,Z)=(1-Z)\varphi^{*}(X)+Z.$

With probability $\pi$, the test $\tilde{\varphi}$ equals the trivial test
$1$, so rejects all null hypotheses. Then

$\sup_{\theta\in\Theta_{b}}\operatorname{FDR}(\theta,\tilde{\varphi})=\pi\frac{n-s_{n}}{n}+(1-\pi)\sup_{\theta\in\Theta_{b}}\operatorname{FDR}(\theta,\varphi^{*})=\pi(1+o(1)),$

while the FNR is controlled at level

$\sup_{\theta\in\Theta_{b}}\operatorname{FNR}(\theta,\tilde{\varphi})=\pi\cdot
0+(1-\pi)\sup_{\theta\in\Theta_{b}}\operatorname{FNR}(\theta,\varphi^{*})=(1-\pi)\overline{\Phi}(b)(1+o(1)).$

In particular, for $\pi>0$, the procedure $\tilde{\varphi}$ trades a gain of
$\pi\overline{\Phi}(b)$ in terms of the FNR with a loss of $\pi$ in terms of
the FDR. The procedure $\varphi^{*}$ is not sparsity preserving, as it makes
$n\gg s_{n}$ rejections with probability $\pi>0$.

##  Appendix F Link between conservative testing and almost full recovery

We state a lemma to illustrate the link between conservative testing and
almost full recovery.

######  Lemma 22.

If a test $\varphi$ achieves almost full recovery with respect to the Hamming
loss over a subset
$\Theta_{s_{n}}\subset\ell_{0}[s_{n}]\backslash\ell_{0}[s_{n}-1]$, that is,
$\sup_{\theta\in\Theta_{s_{n}}}E_{\theta}\operatorname{L_{C}}(\theta,\varphi)/s_{n}=o(1)$,
then it also allows for conservative testing over $\Theta_{s_{n}}$, that is,
$\sup_{\theta\in\Theta_{s_{n}}}\mathfrak{R}(\theta,\varphi)\to 0$.

Conversely, suppose $\varphi$ allows for conservative testing over
$\Theta_{s_{n}}$, and that the number of false discoveries
$V(\varphi)=\sum_{i:\theta_{i}=0}\varphi_{i}$ of $\varphi$ concentrates around
its mean in that,

$\sup_{\theta\in\Theta_{s_{n}}}P_{\theta}[\lvert
V(\varphi)-E_{\theta}V(\varphi)\rvert>E_{\theta}V(\varphi)/2]=o(1).$ (86)

Then $\varphi$ achieves almost full recovery with respect to the Hamming loss
over $\Theta_{s_{n}}$.

###### Proof of Lemma 22.

Recall that the FDP of $\varphi$ can be written $V/\\{\max(V+S,1)\\}$, where
$V=V(\varphi)$ is the number of false discoveries of $\varphi$ and
$S=S(\varphi)$ the number of true discoveries.

First suppose $\varphi$ achieves almost full recovery with respect to the
Hamming loss. This can be written $E[V]+E[s_{n}-S]=o(s_{n})$ uniformly over
$\Theta$. Let $\mathcal{A}=\\{V+S>s_{n}/2\\}$, then using Markov’s inequality,

$P_{\theta}[\mathcal{A}^{c}]\leq P_{\theta}[s_{n}-S\geq
s_{n}/2]\leq\frac{2}{s_{n}}E_{\theta}[s_{n}-S]$

so that $P_{\theta}[\mathcal{A}^{c}]=o(1)$. On the other hand,

$\operatorname{FDR}(\theta,\varphi)=E_{\theta}\left[\frac{V}{(V+S)\vee
1}\right]\leq\frac{2}{s_{n}}E_{\theta}\left[V\mathbf{1}_{\mathcal{A}}\right]+P_{\theta}[\mathcal{A}^{c}],$

which implies FDR$(\theta,\varphi)=o(1)$ over $\Theta$, while
FNR$(\theta,\varphi)=o(1)$ follows from $E_{\theta}[s_{n}-S]=o(s_{n})$.

Conversely, suppose $\varphi$ allows for conservative testing over $\Theta$.
Then FNR$(\theta,\varphi)=o(1)$ implies $E_{\theta}[s_{n}-S]=o(s_{n})$. Set
$\mathcal{B}=\\{|V(\varphi)-E_{\theta}V(\varphi)|\leq
E_{\theta}V(\varphi)/2\\}$. By assumption $P_{\theta}[\mathcal{B}^{c}]=o(1)$
over $\Theta$. Then

$\operatorname{FDR}(\theta,\varphi)=E_{\theta}\left[\frac{V}{(V+S)\vee
1}\right]\geq\frac{E_{\theta}V/2}{3E_{\theta}V/2+s_{n}}P_{\theta}[\mathcal{B}]=\psi(E_{\theta}V/s_{n})(1+o(1)),$

where $\psi$ is the bijective continuous map $x\to x/(3x+2)$ from $(0,\infty)$
to $(0,1/3)$. By assumption $\operatorname{FDR}(\theta,\varphi)=o(1)$. As
$\psi^{-1}$ is continuous at $0$ with limit $0$, one gets
$EV_{\theta}/s_{n}=o(1)$ which implies combined with the control of
$E[s_{n}-S]$ that $\varphi$ achieves almost full recovery with respect to the
Hamming loss. ∎

##  Appendix G Properties of Subbotin distributions

######  Lemma 23.

Let $f(\cdot)$ be defined by (15). Then
$\overline{F}(x)=\int_{x}^{+\infty}f(u)du$ has the following properties:

  * •

for any $x>0$, we have

$\displaystyle\overline{F}(x)$ $\displaystyle<f(x)/x^{\zeta-1}\,;$ (87)

  * •

for any $t\in(0,1/2)$ s.t. $\overline{F}^{-1}(t)\geq 1$, we have

$\displaystyle\overline{F}^{-1}(t)$
$\displaystyle\leq(\zeta\log(1/t)-\zeta\log L_{\zeta})^{1/\zeta}\,;$ (88)

The following holds:

  * •

for any $x>0$,

$\displaystyle\overline{F}(x)$
$\displaystyle\geq\frac{f(x)}{x^{\zeta-1}}\bigg{[}1+(\zeta-1)x^{-\zeta}\bigg{]}^{-1}\,;$
(89) $\displaystyle\overline{F}(x)$
$\displaystyle\geq\frac{f(x)}{x^{\zeta-1}}\zeta^{-1}\>\mbox{ if $x\geq 1$}\,;$
(90)

  * •

for any $t\in(0,1/2)$ s.t. $\overline{F}^{-1}(t)\geq 1$, we have

$\displaystyle\overline{F}^{-1}(t)$
$\displaystyle\geq\left(0\vee\bigg{\\{}\zeta\log(1/t)-\zeta\log(\zeta
L_{\zeta})-(\zeta-1)\log\left(\zeta\log(1/t)-\zeta\log
L_{\zeta}\right)\bigg{\\}}\right)^{1/\zeta}.$ (91)

###### Proof.

Let $\psi(u)=u^{\zeta}/\zeta+\log L_{\zeta}$, so that, restricting to $u>0$,

$f(u)=e^{-\psi(u)},\quad\psi^{\prime}(u)=u^{\zeta-1},\quad\psi^{-1}(v)=(\zeta
v-\zeta\log
L_{\zeta})^{1/\zeta},\quad\psi^{\prime\prime}(u)=(\zeta-1)u^{\zeta-2},$

and thus for instance $\psi^{\prime}\circ\psi^{-1}(v)=(\zeta v-\zeta\log
L_{\zeta})^{1-1/\zeta}$,
$\psi^{\prime\prime}(u)/(\psi^{\prime}(u))^{2}=(\zeta-1)u^{-\zeta}$.
Inequality (87) holds because
$\overline{F}(x)=\int_{x}^{+\infty}e^{-\psi(u)}du<(\psi^{\prime}(x))^{-1}\int_{x}^{+\infty}\psi^{\prime}(u)e^{-\psi(u)}du=f(x)/\psi^{\prime}(x)$.
Expression (88) follows from (87) applied with $x=\overline{F}^{-1}(t)\geq 1$.
Indeed, the latter entails
$L_{\zeta}^{-1}\exp(-\overline{F}^{-1}(t)^{\zeta}/\zeta)>tx^{\zeta-1}\geq t$,
from which (88) follows by applying the function $\log(\cdot)$ to both sides
of the inequality. To prove (89), write for any $x>0$,

$\displaystyle\frac{\psi^{\prime\prime}(x)}{\psi^{\prime}(x)^{2}}\overline{F}(x)$
$\displaystyle\geq\int_{x}^{+\infty}\frac{\psi^{\prime\prime}(u)}{\psi^{\prime}(u)^{2}}e^{-\psi(u)}du=\bigg{[}-\frac{e^{-\psi(u)}}{\psi^{\prime}(u)}\bigg{]}_{x}^{\infty}-\overline{F}(x)=\frac{f(x)}{\psi^{\prime}(x)}-\overline{F}(x),$

by using an integration by parts. Expressions (89) and (90) follow. Finally,
let us prove (91). From (90) used with $x=\overline{F}^{-1}(t)$, we get $\zeta
t(\overline{F}^{-1}(t))^{\zeta-1}\geq e^{-\psi(\overline{F}^{-1}(t))}$ and
thus $-\log(\zeta
t)-(\zeta-1)\log(\overline{F}^{-1}(t))\leq\psi(\overline{F}^{-1}(t))$. Hence,
by (89), we obtain

$\log L_{\zeta}\vee\left(-\log(\zeta
t)-(1-1/\zeta)\log(\zeta\log(1/t)-\zeta\log
L_{\zeta})\right)\leq\psi(\overline{F}^{-1}(t))$

and thus (91). ∎

######  Lemma 24.

For any $a\geq 0$ and any $x\in\mathbb{R}$,

$f(x-a)/f(x)\geq\exp\big{(}a\lvert
x-a\rvert^{\zeta-1}\operatorname{sign}(x-a)\big{)}.$

###### Proof.

Since $\zeta>1$, observe that $-\log f(x)=\zeta^{-1}\lvert x\rvert^{\zeta}+c$
is differentiable with increasing derivative $\lvert
x\rvert^{\zeta-1}\operatorname{sign}(x)$. It follows, using $a\geq 0$, that
$-\log f(x)\geq-\log f(x-a)+a\lvert
x-a\rvert^{\zeta-1}\operatorname{sign}(x-a)$, and hence the claim. ∎