Sparse Detection Boundaries and Minimax Power

Why Detection Depends on Sparsity

A mean shift can be difficult to detect for two different reasons: each affected coordinate may be weak, or only a small fraction of coordinates may be affected. A test that accumulates small changes across many coordinates can work well in the first situation but miss a handful of conspicuous signals. Conversely, a maximum-coordinate test can find a few large shifts while overlooking many weak ones. The relevant question is therefore not just how large the mean vector is, but how its nonzero entries are distributed.

We study this trade-off in a Gaussian sequence model. It gives a clean benchmark for the detection rates of the quadratic and maximum tests introduced in the earlier material on high-dimensional mean testing. If the coordinates are standardized sample means, the signal size in this model is the original mean shift multiplied by the square root of the sample size and divided by the standard deviation.

Definition: Observe independent $X_1,\ldots,X_p$, where $X_j\sim N(\theta_j,1)$. Under the null hypothesis, $\theta=0$. Under a sparse alternative, exactly $s=\lfloor p^{1-\beta}\rfloor$ coordinates have mean $\mu>0$, and the rest have mean zero. Here $1/2<\beta<1$ indexes sparsity. We use the signal-strength scaling $\mu=\sqrt{2r\log p}$, with $r>0$. The support of the nonzero coordinates is unknown.

The alternatives are positive to keep the presentation focused on the detection boundary; the maximum test can then use the largest coordinate. Two-sided alternatives can be treated with absolute values, with the same first-order boundary. For a test $\phi$, which equals one when the null is rejected, its minimax sum of errors is

R_p(\phi)=P_0(\phi=1)+\sup_{\theta\in\Theta_{p,s,\mu}}P_\theta(\phi=0), \qquad R_p^*=\inf_\phi R_p(\phi),

where $\Theta_{p,s,\mu}$ is the set of all mean vectors with exactly $s$ entries equal to $\mu$ and all other entries zero. Detection is asymptotically possible when $R_p^*\to0$. When $R_p^*\to1$, no test can asymptotically distinguish the null from the hardest alternatives in this class. The boundary results below describe strict inequalities in $r$; behavior exactly on a boundary can depend on finer-order terms.

What the Maximum and Quadratic Tests See

The maximum test rejects when the largest coordinate exceeds a high null quantile. The largest of $p$ standard normal variables is on the scale $\sqrt{2\log p}$. Under an alternative, the largest signal coordinate is approximately $\mu+\sqrt{2\log s}$. Since $\log s\sim(1-\beta)\log p$, the signal maximum can separate from the null maximum when

\sqrt{2r\log p}+\sqrt{2(1-\beta)\log p}>\sqrt{2\log p}, \qquad r>\left(1-\sqrt{1-\beta}\right)^2.

This comparison gives the maximum-test boundary. The following derivation makes the strict-separation argument precise at the scale needed here.

Result: For $r>(1-\sqrt{1-\beta})^2$, a maximum-coordinate test can have both error probabilities tending to zero. For $r<(1-\sqrt{1-\beta})^2$, this maximum test does not achieve asymptotic power one at a null-calibrated threshold.

To see the separation, choose a threshold $t_p=\sqrt{2\log p}+c_p$, where $c_p\to0$ but $\sqrt{\log p}\,c_p\to\infty$. The null probability of exceeding this threshold tends to zero by the Gaussian tail bound and a union bound. Under the alternative, the maximum among the $s$ shifted coordinates is $\mu+\max_{j\in S}Z_j$, where the $Z_j$ are independent standard normals. Their maximum divided by $\sqrt{2\log s}$ converges in probability to one. Thus, above the displayed boundary, the signal maximum exceeds $t_p$ with probability tending to one. Below the boundary, it falls short of the null maximum on the leading $\sqrt{2\log p}$ scale; signals do not give this test consistent power. This conclusion concerns the maximum test, not all possible tests.

The quadratic statistic instead pools squared coordinates:

T=\sum_{j=1}^{p}(X_j^2-1).

Under the null, $E_0[T]=0$ and $\operatorname{Var}_0(T)=2p$. Under an alternative with $s$ shifted coordinates, the expectation is $s\mu^2$. Since a $N(\mu,1)$ variable has squared-value variance $2+4\mu^2$, independence gives

E_\theta[T]=s\mu^2,\qquad \operatorname{Var}_\theta(T)=2p+4s\mu^2.

A useful sufficient condition for consistent detection by a null-calibrated quadratic test is $s\mu^2/\sqrt p\to\infty$. Indeed, choose a threshold $a_p\sqrt p$ with $a_p\to\infty$ and $a_p=o(s\mu^2/\sqrt p)$. Chebyshev’s inequality makes the null rejection probability tend to zero. Under the alternative, the mean exceeds the threshold by an amount asymptotic to $s\mu^2$, and the variance divided by $(s\mu^2)^2$ tends to zero: the two terms are $2p/(s\mu^2)^2\to0$ and $4/(s\mu^2)\to0$. Thus the non-rejection probability also tends to zero.

Worked Example: A Dense Alternative Suited to a Quadratic Test

Let $s$ be of order $p^{0.7}$, and let $\mu=1$. Then $s\mu^2$ is of order $p^{0.7}$, while the null standard deviation of $T$ is $\sqrt{2p}$, of order $p^{0.5}$. Their ratio grows like $p^{0.2}$, so the quadratic statistic separates the alternative from the null.

For example, at $p=10{,}000$, take $s=630$. The alternative mean of $T$ is $630$, compared with null standard deviation $\sqrt{20{,}000}\approx141.4$. The standard-deviation ratio is about $4.46$. This finite-$p$ calculation is not itself an asymptotic guarantee, but it illustrates the increasing separation implied by the rate calculation.

In the sparse scaling $s\asymp p^{1-\beta}$ and $\mu^2=2r\log p$, the quadratic signal-to-noise ratio has order $p^{1/2-\beta}\log p$. It diverges when $\beta<1/2$, but tends to zero for every fixed $r$ when $\beta>1/2$. Thus, in the sparse range considered here, the unthresholded quadratic statistic does not capture the minimax boundary.

The Sparse Minimax Boundary

A test that counts exceedances above a chosen coordinate threshold can target signals that are individually too weak to dominate the overall maximum. Its threshold can be tuned to the unknown signal size in a theoretical comparison. Write the threshold as $u_q=\sqrt{2q\log p}$, where $0<q\leq1$. Under the null, the expected number of exceedances has order $p^{1-q}$, so its standard deviation has order $p^{(1-q)/2}$. If $q>r$, a shifted coordinate exceeds the threshold with probability of order $p^{-(\sqrt q-\sqrt r)^2}$. The expected signal-driven excess count therefore has order $p^{1-\beta-(\sqrt q-\sqrt r)^2}$.

For the excess count to dominate its null fluctuations, one needs

1-\beta-(\sqrt q-\sqrt r)^2>\frac{1-q}{2}.

Maximizing the left-minus-right difference over $q$ gives the adaptive sparse boundary. If $2\sqrt r\leq1$, the best choice is $q=4r$, and the inequality becomes $r>\beta-\tfrac12$. If $2\sqrt r>1$, the best available choice is $q=1$, and the inequality becomes $2\sqrt r-r>\beta$, or $r>(1-\sqrt{1-\beta})^2$. The transition occurs at $\beta=3/4$.

Theorem (sparse normal-means detection boundary): For $1/2<\beta<1$, define $$ \rho^*(\beta)= \begin{cases} \beta-\tfrac12, & \tfrac12<\beta\leq\tfrac34,\\ (1-\sqrt{1-\beta})^2, & \tfrac34<\beta<1. \end{cases} $$ If $r>\rho^*(\beta)$, there exist tests whose minimax sum of errors tends to zero. If $r<\rho^*(\beta)$, the minimax sum of errors tends to one. The first-order boundary is attained by a suitably chosen threshold-exceedance test; the second statement is a lower bound over all tests, not just coordinatewise procedures.

The upper-bound calculation above explains how thresholding reaches the boundary. The lower bound is the essential minimax part: no alternative test can do better. A standard way to establish it is to place a uniform prior on the possible supports and study the resulting likelihood ratio. Under the null, the likelihood ratio for this mixture is

L(X)=\binom{p}{s}^{-1}\sum_{|S|=s} \exp\left(\mu\sum_{j\in S}X_j-\frac{s\mu^2}{2}\right).

For the very sparse range, an untruncated second moment is insufficient because rare, exceptionally large coordinates dominate it. The lower-bound argument therefore truncates the likelihood contributions at the null extreme scale $\sqrt{2\log p}$. Gaussian tail bounds applied to the truncated first and second moments show that, when $r<\rho^*(\beta)$, the truncated mixture likelihood converges to one in null probability and its discarded tail has probability tending to zero under the null and the support-mixture alternative. Consequently, the mixture and null become indistinguishable in total variation. For any test, its worst-case type-II error is at least its average type-II error under this mixture; indistinguishability forces the sum of null and average alternative errors to tend to one. This yields the minimax lower bound. The truncation is what produces the change in boundary formula at $\beta=3/4$.

Worked Example: Moderately Sparse Signals

Take $\beta=0.6$. The minimax boundary is $\rho^*(0.6)=0.6-0.5=0.1$, while the maximum-test boundary is $(1-\sqrt{0.4})^2\approx0.135$. Choose $r=0.12$: the alternative has $s$ of order $p^{0.4}$, and $\mu=\sqrt{0.24\log p}$.

A threshold with $q=4r=0.48$ gives a null fluctuation exponent $(1-q)/2=0.26$. The signal-driven excess count has exponent $1-\beta-(\sqrt q-\sqrt r)^2=0.4-(\sqrt{0.48}-\sqrt{0.12})^2=0.28$. Since $0.28>0.26$, threshold exceedances can separate the hypotheses. The maximum boundary is not crossed, and the quadratic statistic’s sparse signal-to-noise ratio tends to zero. This is a regime where adaptation to a range of coordinate sizes matters.

Worked Example: Very Sparse Signals

Take $\beta=0.85$. Then $\rho^*(0.85)=(1-\sqrt{0.15})^2\approx0.375$. Choose $r=0.40$, so $\mu=\sqrt{0.8\log p}$ and $s$ is of order $p^{0.15}$. The maximum of the shifted coordinates is approximately \[ \sqrt{2\log p}\bigl(\sqrt{0.40}+\sqrt{0.15}\bigr) \approx1.020\sqrt{2\log p}. \] The null maximum is on the scale $\sqrt{2\log p}$. The strict excess in the leading constant means a calibrated maximum test has power tending to one, while the minimax boundary confirms that this is an attainable detection regime.

Which Test Is Appropriate?

The boundary comparison separates three patterns. When signals are dense, pooling squared coordinates can accumulate many weak contributions. In the sparse range $1/2<\beta\leq3/4$, the minimax boundary is lower than the maximum-test boundary except at the endpoint; intermediate thresholds can detect collections of moderately weak signals. For $\beta>3/4$, the minimax boundary equals the maximum-test boundary, so the maximum is first-order optimal. The boundaries are asymptotic rate statements: they do not determine finite-sample power, exact calibration, or the best choice of threshold for a particular data set.

If sparsity is known, a threshold can be selected for the relevant regime. If it is unknown, a single fixed threshold need not attain the boundary uniformly. Constructing procedures that adapt to unknown sparsity is a separate problem.

Common Pitfall

Wrong reasoning: “The alternative has $s$ nonzero coordinates, so its total squared signal is $s\mu^2$; therefore the quadratic test must be optimal for every sparsity level.” The total signal alone does not determine detectability. The quadratic test compares that total with fluctuations of order $\sqrt p$, while a maximum or thresholded count uses the locations and sizes of unusually large coordinates differently.

Correction: Compare the alternative’s effect with the noise scale of the particular statistic. For the quadratic statistic, the key ratio is $s\mu^2/\sqrt p$. For the maximum, compare the largest shifted coordinate with the null extreme scale. For minimax claims, also account for the lower bound: a test’s power does not establish that its rate is optimal.

Key takeaway: Sparse detection has a boundary in the joint parameters $(\beta,r)$. Quadratic pooling is suited to dense signals, the maximum is optimal for very sparse strong signals, and threshold-based adaptation reaches the lower boundary between those regimes.

Check Your Understanding

Use the model and asymptotic boundaries defined above.

For fixed $\beta$, what does increasing $r$ change in the sparse normal-means model?
At $\beta=0.7$, calculate the minimax boundary and compare it with the maximum-test boundary.
Why can the quadratic statistic fail in a sparse regime even when the alternative has a nonzero total squared signal?
For which sparsity range does the maximum-test boundary coincide with the minimax boundary?
Why does proving that one test has power tending to one not, by itself, establish a minimax detection boundary?