Minimax signal detection and separation rates

By [F1], each $V_{n,j}=G_{n,j}^2-1$ is centered with variance $2$. Independence within each row gives $\mathbb{E}{T}_n=0$ and $\mathrm{Var}(T_n)=2{\sum }_j{w}_{n,j}^2=1$. Thus the row standard deviation is $s_n=1>0$.

Fix $\delta >0$ and put $w_n^{\ast }={\max }_j{w}_{n,j}$. If $w_{n,j}=0$, its Lindeberg summand is zero. Otherwise $w_{n,j}\mathrm{\mid }{V}_{n,j}\mathrm{\mid }>\delta$ implies $\mathrm{\mid }{V}_{n,j}\mathrm{\mid }>\delta \mathrm{/}{w}_n^{\ast }$. Therefore ${\sum }_j\mathbb{E}\text{\hspace{0.17em}⁣}\left[w_{n,j}^2{V}_{n,j}^2{\mathbf{1}}_{\{w_{n,j}\mathrm{\mid }{V}_{n,j}\mathrm{\mid }>\delta \}}\right]\le \frac{1}{2}\mathbb{E}\text{\hspace{0.17em}⁣}\left[V^2{\mathbf{1}}_{\{\mathrm{\mid }V\mathrm{\mid }>\delta \mathrm{/}{w}_n^{\ast }\}}\right]\mathrm{.}$ Because $w_n^{\ast }\to 0$ and $V^2$ is integrable by [F1], the right side tends to zero by [F3]. This is the Lindeberg condition for the array $w_{n,j}{V}_{n,j}$.

The array in step 2.1 is centered and independent within rows, has finite second moments, and has row standard deviation $1$. By [F2] and the Lindeberg condition just proved, $T_n\Rightarrow N(0,1)$.

Put $w=z^2$. The hyperbolic series give $w\sinh w-q(\cosh w-1)={\sum }_{k\ge 1}\frac{(2k-q)w^{2k}}{(2k)!}\mathrm{.}$ Every coefficient is positive because $q<2$. Replacing $q$ by $2$ makes only the first coefficient zero and leaves every later coefficient positive. The positive denominators in $a,b$ therefore prove $a(z),b(z)>0$.

For fixed $z>0$ and $v>0$, put $f(v)=(\cosh (zv)-1-a(z)v^2)\mathrm{/}{v}^q$. Differentiation and the absolutely convergent series show that $\frac{f^{\mathrm{\prime }}(v)}{v^{1-q}}={\sum }_{k\ge 1}\frac{(2k-q)z^{2k}{v}^{2k-2}}{(2k)!}-(2-q)a(z)\mathrm{.}$ This expression is strictly increasing in $v$: its terms with $k\ge 2$ have strictly positive coefficients and positive powers. It is zero at $v=z$ by the definition of $a$. Consequently $f$ decreases to $z$ and increases after $z$. Direct substitution gives $f(z)=-b(z)$, so $\cosh (zv)-1\ge a(z)v^2-b(z)v^q$. Evenness proves the assertion for negative $v$, and direct substitution proves equality at $0,z,-z$.

The quotient representation of $\varphi$ in the Statement is continuous. To prove strict increase, write its numerator series before the factor $z^{2-q}$ as $P(w)={\sum }_{k\ge 1}{p}_k{w}^{2k}$ and its denominator as $Q(w)={\sum }_{k\ge 1}{q}_k{w}^{2k}$, where $p_k=(2k-2)\mathrm{/}(2k)!$ and $q_k=(2k-q)\mathrm{/}(2k)!$. The ratios $p_k\mathrm{/}{q}_k=(2k-2)\mathrm{/}(2k-q)$ strictly increase with $k$. Pairing terms with indices $k>\mathrm{\ell }$ in $P^{\mathrm{\prime }}Q-P{Q}^{\mathrm{\prime }}$ gives positive multiples of $(k-\mathrm{\ell })(p_k{q}_{\mathrm{\ell }}-p_{\mathrm{\ell }}{q}_k)w^{2k+2\mathrm{\ell }-1}$, so this derivative numerator is positive for $w>0$. The products and paired sums are justified first for finite partial sums and then by absolute convergence on compact intervals. Thus $P\mathrm{/}Q$ is strictly increasing; multiplying it by the positive strictly increasing function $z^{2-q}$ proves that $\varphi$ is strictly increasing.

The first nonzero numerator and denominator terms are $w^4\mathrm{/}12$ and $(2-q)w^2\mathrm{/}2$, respectively. Hence $\varphi (z)\sim \frac{z^{6-q}}{6(2-q)}(z\downarrow 0)\mathrm{.}$ The exponential representations instead give $\varphi (z)\sim z^{2-q}$ as $z\to \mathrm{\infty }$, since the ratio of its two bracketed expressions tends to one. Thus its endpoint limits are zero and infinity. Strict increase and [F3] give exactly one inverse value at each positive target. The inverse is continuous: values on either side of its value have images on either side of the target, which is the epsilon-delta criterion for the inverse at that target. The inverse power asymptotics follow by trapping $\varphi (z)$ between $(1\pm \eta )$ times its stated positive leading power and then taking the corresponding positive roots.

Expanding $a$ at zero gives $a(z)\sim z^2\mathrm{/}2$, so $\psi (z)\sim z^{-2}$. At infinity, $a(z)\sim e^{z^2}\mathrm{/}[2(2-q)]$, so $\psi (z)\sim (2-q)e^{-z^2}$. Combining these with the inverse asymptotics in step 3.1 proves all endpoint formulas for $z(x)$ and $d(x)$. In particular $z(x)$ is comparable to $x^{\kappa }$ at infinity. The functions $\psi (z)z^2$ and $\psi (z)(e^{z^2}-1)$ have finite limits at zero and infinity; continuity bounds them also on the intervening compact interval. Similarly $e^{z^2}\psi (z{)}^2(e^{z^2}-1)$ is bounded for $z\ge 1$, proving the three global bounds.

The definitions give $d(x)a(z(x))=x^{2\beta }\mathrm{/}2$ and $d(x)b(z(x))=x^{qs}\mathrm{/}2$, since $\varphi (z(x))=x^L$ and $L+2\beta =qs$. Also $a(z)z^2-b(z)z^q=\cosh (z^2)-1$. Thus $d(x{)}^2(\cosh (z(x{)}^2)-1)=\frac{1}{2}(d(x)z(x{)}^2{x}^{2\beta }-d(x)z(x{)}^q{x}^{qs})\mathrm{.}$ Near zero the integrands for $c_1,c_2,c_0$ are asymptotic to positive constants times $x^{4\beta }$, $x^{4\beta +4L\mathrm{/}(6-q)}$, and $x^{4\beta }$, respectively; those for $M_1,M_2$ have respective exponents $6\beta +2L\mathrm{/}(6-q)$ and $6\beta +10L\mathrm{/}(6-q)$. All these exponents exceed $-1$. At infinity each integrand is bounded by $C{x}^m{e}^{-c{x}^{2\kappa }}$ for suitable positive $C,c$ and some nonnegative $m$. This envelope is integrable: choosing an integer $k$ with $2\kappa k>m+2$ and using $e^{c{x}^{2\kappa }}\ge (c{x}^{2\kappa }{)}^k\mathrm{/}k!$ bounds it by a constant times $x^{-2}$ for large $x$. The integral of $x^{-2}$ on $[b,R]$ is $1\mathrm{/}b-1\mathrm{/}R$ by the compact fundamental theorem in [F4], and is bounded as $R\to \mathrm{\infty }$. The small-$x$ power bounds likewise integrate to $a^{p+1}\mathrm{/}(p+1)$ when $p>-1$. Compact intervals are covered by [F4]. The five improper integrals therefore exist, are finite, and are positive. Integrating the pointwise identity proves $c_0=(c_1-c_2)\mathrm{/}2>0$.

For fixed $n,h_0>0$, the large-$x$ bound $d(x)\le C{x}^{2\beta }{e}^{-c{x}^{2\kappa }}$ makes ${\sum }_i{h}_{0}d(i\mathrm{/}n)$ finite by comparison with a convergent power tail. There are only finitely many remaining indices, including those close to zero. Multiplying the pointwise inequality of step 2.1 by $h_i$ and using $h_{i}a(z_i)=h_0(i\mathrm{/}n{)}^{2\beta }\mathrm{/}2$ and $h_{i}b(z_i)=h_0(i\mathrm{/}n{)}^{qs}\mathrm{/}2$ proves the finite-vector scalar certificate in the Statement. This argument places no upper bound on the score coefficient $h_i$.

Let $f$ be any of the five integral integrands in step 5.1. On a fixed $[a,b]\subset (0,\mathrm{\infty })$, its mesh-$1\mathrm{/}n$ sums converge to its integral by trapping the sums between compact-interval upper and lower sums from [F4]; the two endpoint pieces have lengths at most $1\mathrm{/}n$ and bounded values. For small $x$, $f(x)\le C{x}^p$ with one of the positive exponents $p$ in step 5.1, so $\frac{1}{n}{\sum }_{i\mathrm{/}n<a}f(i\mathrm{/}n)\le C(a^{p+1}+\frac{a^p}{n})\mathrm{.}$ At infinity use the envelope $g(x)=C{x}^m{e}^{-c{x}^{2\kappa }}$, increasing $m,C$ if necessary. Its derivative has the sign of $m-2c\kappa x^{2\kappa }$, so it is eventually decreasing. Consequently its discrete tail is bounded by its integral tail plus one mesh term. First let $n\to \mathrm{\infty }$, then $a\downarrow 0$ and $b\to \mathrm{\infty }$. These two tail bounds prove the five full Riemann limits. Substituting $h_i=h_{0}d(i\mathrm{/}n)$ gives all five scaled sum equivalents, irrespective of how the positive factor $h_0$ varies with $n$.

The two scaling equations have the unique positive solution $n^L=\frac{c_1}{c_2}\frac{{\epsilon }^{2-q}}{r^2},h_0=\frac{r^2{\epsilon }^{-2}}{c_1{n}^{2\beta +1}}\mathrm{.}$ Let $V={\sum }_i{h}_i^2(\cosh (z_i^2)-1)$. Step 6.2 gives $V\sim U^2=c_0{h}_0^{2}n$ whenever $n\to \mathrm{\infty }$. For any feasible relaxed pair $(g_i,w_i)$ of finite cost $W$, expansion of the positive kernel gives $\cosh (zw)-1={\sum }_{k\ge 1}\frac{z^{2k}{w}^{2k}}{(2k)!}\mathrm{.}$ Apply [F5] to the arrays with entries $h_i{z}_i^{2k}\mathrm{/}\sqrt{(2k)!}$ and $g_i{w}_i^{2k}\mathrm{/}\sqrt{(2k)!}$ for finitely many $i,k$, and increase the truncations. It follows that ${\sum }_i{h}_i{g}_i(\cosh (z_i{w}_i)-1)\le \sqrt{VW}\mathrm{.}$ This is a deterministic kernel inequality, with no Gaussian probability space.

Multiply the scalar certificate in step 2.1 at $v=w_i$ by $h_i{g}_i$ and sum up to an index $m$. Step 7.1 bounds the left side by $\sqrt{VW}$, and the partial budget is at most ${\epsilon }^{-q}$. The partial energy is therefore bounded above independently of $m$ by the resulting inequality, so its full sum is finite. Increasing $m$ now yields $\sqrt{VW}\ge \frac{h_0}{2}(n^{-2\beta }{r}^2{\epsilon }^{-2}-n^{-qs}{\epsilon }^{-q})=\frac{h_0^{2}n}{2}(c_1-c_2)=U^2\mathrm{.}$ Thus every finite-cost feasible pair has $W\ge U^4\mathrm{/}V$, and infinite-cost pairs do not lower the infimum. Hence $J_{\epsilon }(r)\ge U^4\mathrm{/}V\sim U^2$.

Fix numbers $0<a<b<\mathrm{\infty }$ and $0<\eta <1$. Write $c_{j,[a,b]}$ for the integral defining $c_j$ restricted to $[a,b]$, for $j=0,1,2$. These constants are positive. Choose $n^{\mathrm{\prime }},h_0^{\mathrm{\prime }}>0$ from $c_{1,[a,b]}{h}_0^{\mathrm{\prime }}(n^{\mathrm{\prime }}{)}^{2\beta +1}=(1+\eta )r^2{\epsilon }^{-2},c_{2,[a,b]}{h}_0^{\mathrm{\prime }}(n^{\mathrm{\prime }}{)}^{qs+1}=(1-\eta ){\epsilon }^{-q}\mathrm{.}$ Division gives $\frac{n^{\mathrm{\prime }}}{n}={\left(\frac{c_{1,[a,b]}\mathrm{/}{c}_{2,[a,b]}}{c_1\mathrm{/}{c}_2}\frac{1-\eta }{1+\eta }\right)}^{1\mathrm{/}L},\frac{h_0^{\mathrm{\prime }}}{h_0}=(1+\eta )\frac{c_1}{c_{1,[a,b]}}{\left(\frac{n}{n^{\mathrm{\prime }}}\right)}^{2\beta +1}\mathrm{.}$ For this fixed window and margin these ratios are fixed positive constants. Hence $n^{\mathrm{\prime }}\to \mathrm{\infty }$ and $h_0^{\mathrm{\prime }}\to 0$ under the claimed hypotheses.

Put $g_i=h_0^{\mathrm{\prime }}d(i\mathrm{/}{n}^{\mathrm{\prime }})$ and $w_i=z(i\mathrm{/}{n}^{\mathrm{\prime }})$ when $a\le i\mathrm{/}{n}^{\mathrm{\prime }}\le b$, and set both to zero otherwise. There are finitely many nonzero coordinates. The compact-window maximum of $d$ is finite, so eventually $0\le g_i\le 1$. Compact Riemann convergence gives actual energy $(1+\eta +o(1))r^2{\epsilon }^{-2}$ and actual budget $(1-\eta +o(1)){\epsilon }^{-q}$, hence eventual feasibility. Its cost divided by $U^2$ tends to $\frac{c_{0,[a,b]}}{c_0}{\left(\frac{h_0^{\mathrm{\prime }}}{h_0}\right)}^2\frac{n^{\mathrm{\prime }}}{n}\mathrm{.}$ As $a\downarrow 0$, $b\to \mathrm{\infty }$, and $\eta \downarrow 0$, this expression tends to one by step 5.1 and the explicit ratios in step 8.2. For any fixed positive tolerance one may first fix a sufficiently wide window and small margin, and then take sufficiently small $\epsilon$. This proves $\mathrm{lim\hspace{0.17em}sup}{J}_{\epsilon }(r)\mathrm{/}{U}^2\le 1$ without choosing an infinite family of windows. With step 8.1 it proves $J_{\epsilon }(r)\sim U^2$. In particular, no untruncated claim that $h_{0}d(i\mathrm{/}n)\le 1$ has been used.

Substituting the value of $n$ from step 7.1 into $U=\sqrt{c_0}{h}_0\sqrt{n}$ gives $U=\frac{\sqrt{c_0}}{c_1}{\left(\frac{c_1}{c_2}\right)}^{-(2\beta +1\mathrm{/}2)\mathrm{/}L}{\epsilon }^{-[2q\alpha +1-q\mathrm{/}2]\mathrm{/}L}{r}^{(2qs+1)\mathrm{/}L}\mathrm{.}$ Since $D=L\mathrm{/}q$, this is precisely the stated power with exponents $A\mathrm{/}D$ and $B\mathrm{/}D$. Similarly $h_0^L=C_2{r}^{2(qs+1)}{\epsilon }^{-(2q\alpha +2-q)}$ for a parameter-only $C_2>0$, so $h_0\to 0$ is equivalent to $r=o({\epsilon }^{a_c})$. Finally $a_c-\frac{2-q}{2}=\frac{qL}{2(qs+1)}>0.$ Thus this condition also forces $n\to \mathrm{\infty }$ by the formula for $n^L$, while $n\to \mathrm{\infty }$ and $h_0\to 0$ plainly include $h_0\to 0$. This proves the asserted equivalence, the restricted power asymptotic, and all remaining claims.

For each row put $a_{n,j}=\mathbb{E}{X}_{n,j}^2$ and $v_n={\sum }_j{a}_{n,j}$. Finite products in [F1] allow us to integrate replacement coordinates with independent centered Gaussian laws of variances $a_{n,j}$; a zero variance means the point mass at zero. These products need not be coupled across rows. The supplied scalar density already has integral one, so [F3] gives its scaled probability laws without a separate Gaussian-normalization theorem. For $\varphi (t)=(2\pi {)}^{-1\mathrm{/}2}{e}^{-t^2\mathrm{/}2}$, direct differentiation gives ${\varphi }^{\mathrm{\prime }}(t)=-t\varphi (t)$. On $[-R,R]$, apply [F5] with $(u,v)=(t,\varphi (t))$ and then $(u,v)=(t^3,\varphi (t))$ to obtain ${\int }_{-R}^R{t}^2\varphi (t)dt=[-t\varphi (t){]}_{-R}^R+{\int }_{-R}^R\varphi (t)dt,$ ${\int }_{-R}^R{t}^4\varphi (t)dt=[-t^3\varphi (t){]}_{-R}^R+3{\int }_{-R}^R{t}^2\varphi (t)dt\mathrm{.}$ The boundary terms tend to zero by [F6]; [F7] and the supplied normalization $\int \varphi =1$ then give $\mathbb{E}{G}^2=1$ and $\mathbb{E}{G}^4=3$. Odd moments vanish by symmetry. Consequently a replacement coordinate $G_{n,j}$ has mean zero, variance $a_{n,j}$ and fourth moment $3a_{n,j}^2$.

The sum of the replacement coordinates has law $N(0,v_n)$. One can verify this using only scalar integration: for positive variances $a,b$, Fubini and the substitution $y=t-x$ make the sum density the convolution of the two scalar densities. Completing the square in $x^2\mathrm{/}a+(t-x{)}^2\mathrm{/}b$ and using [F3] together with the given unit Gaussian integral makes that convolution $(2\pi (a+b){)}^{-1\mathrm{/}2}\exp (-t^2\mathrm{/}(2(a+b)))$. Induction gives the assertion for every finite row, and zero-variance coordinates have no effect. The absolute integrals here are finite because they are probability densities.

Let $f$ be bounded and $C^3$ on $\mathbb{R}$, with bounded first, second and third derivatives. In the finite product integral replace $X_{n,j}$ by $G_{n,j}$ one coordinate at a time. Conditional on the other coordinates, the constant, linear and quadratic terms of the Taylor expansion of $f$ at their sum have the same integrals, since both coordinates have mean zero and variance $a_{n,j}$. The two remainders are bounded by [F4]. Fubini is legitimate since $f$ is bounded and the displayed moments are finite. Summing the telescoping differences therefore gives $\mathrm{\mid }\mathbb{E}f(S_n)-\mathbb{E}f({\sum }_j{G}_{n,j})\mathrm{\mid }\le \mathrm{\parallel }{f}^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{\infty }}{\sum }_j(\mathbb{E}\mathrm{\mid }{X}_{n,j}{\mathrm{\mid }}^3+\mathbb{E}\mathrm{\mid }{G}_{n,j}{\mathrm{\mid }}^3)\mathrm{/}6$.

Cauchy--Schwarz, first for each coordinate integral and then for the finite index sum, gives ${\sum }_j\mathbb{E}\mathrm{\mid }{X}_{n,j}{\mathrm{\mid }}^3\le ({\sum }_j\mathbb{E}{X}_{n,j}^2{)}^{1\mathrm{/}2}({\sum }_j\mathbb{E}{X}_{n,j}^4{)}^{1\mathrm{/}2}\to 0$. Also $a_{n,j}^2\le \mathbb{E}{X}_{n,j}^4$, by expanding the nonnegative integral of $(X_{n,j}^2-a_{n,j}{)}^2$. Hence ${\sum }_j{a}_{n,j}^2\to 0$, and the same calculation with the Gaussian fourth moments in step 1.1 gives ${\sum }_j\mathbb{E}\mathrm{\mid }{G}_{n,j}{\mathrm{\mid }}^3\le (3v_n{\sum }_j{a}_{n,j}^2{)}^{1\mathrm{/}2}\to 0$. Both Cauchy--Schwarz inequalities follow by expanding a nonnegative square and minimizing its scalar coefficient, for the coordinate integral and the finite index sum respectively. Thus the replacement error in step 2.2 tends to zero for each such test $f$.

For $\eta >0$, a concrete $C^3$ cutoff is obtained by integrating the nonnegative polynomial $s^3(1-s{)}^3$ on $[0,1]$, normalizing its integral to one, and extending the resulting cumulative function by zero and one outside that interval. Its first three derivatives join continuously at the endpoints. Translate, rescale and subtract this function from one to bound ${\mathbf{1}}_{(-\mathrm{\infty },t]}$ from below and above by bounded $C^3$ functions that differ only on $[t-\eta ,t+\eta ]$. Apply step 3.1 to these two fixed cutoffs. By step 2.1 the replacement sum has variance $v_n\to v>0$; its probability of this interval is at most $2\eta \mathrm{/}\sqrt{2\pi v_n}$, and its distribution at each fixed endpoint converges to $\mathrm{\Phi }$ scaled by $\sqrt{v}$. Taking $n\to \mathrm{\infty }$ and then $\eta \downarrow 0$ proves $\mathbb{P}(S_n\le t)\to \mathrm{\Phi }(t\mathrm{/}\sqrt{v})$ for every real $t$.

Finally fix $\delta >0$. Choose finitely many increasing real grid points so that the two tails of the limiting normal law each have mass below $\delta$ and its mass between consecutive grid points is below $\delta$. Such a finite grid exists because its density is bounded and its total integral is one. Step 4.1 gives convergence at every grid point simultaneously. Between consecutive points monotonicity of the two distribution functions bounds their difference by the largest grid-point difference plus $\delta$; the tail intervals have the same bound using zero and one. Thus the supremum in the Statement has limsup at most $\delta$. Letting $\delta \downarrow 0$ proves the asserted uniform convergence. All replacements were finite products of supplied probability laws, and the only additional choice hypothesis remains [A1].