Let $H\_0$ and $H\_1$ be two distributions. The Neyman-Pearson lemma says that of all rejection regions $R$ with fixed probability $\alpha$ under $H\_0$, the one with maximal probability under $H\_1$ is the set of the form $R = \{x: \frac{p\_1(x)}{p\_0(x)} \ge c\}$ with $c$ chosen such that $\mathbb{P}\_{x \sim H\_0}(x \in R) = \alpha$.
The power of the test is then $\mathbb{P}\_{x \sim H\_1}(x \in R)$.


In my case, $H\_0 = \mathcal{N}(0, \tau^2 I\_d)$ and $H\_1 = \mathcal{N}(\mu, \sigma^2 I\_d)$ with $\tau > \sigma$. The dimension is high (hundreds of thousands).


For this choice of $H\_0$ and $H\_1$, computing the rejection region in closed form does not appear to be possible, so I'd like to compute an upper bound on the power of the NP test at level $\alpha$ without actually computing the rejection region.


Are there any generic methods to compute an upper bound on the power of a Neyman-Pearson test at level $\alpha$? I'm looking for an exact bound, not an approximate bound based on e.g. the CLT.


In textbooks and papers, I've seen many ways to upper-bound the power as a function of $c$ (the likelihood ratio threshold), but none to upper-bound the power as a function of $\alpha$. That said, if I had a right tail bound on $\frac{p\_1(x)}{p\_0(x)}$ under $H\_1$ and a left tail bound on $\frac{p\_1(x)}{p\_0(x)}$ under $H\_0$, I could combine those to get an upper bound on the power as a function of $\alpha$.



upper bound on power of neyman-pearson hypothesis test
$\renewcommand{\P}{\operatorname{\mathsf P}}
\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\la}{\lambda}
\newcommand{\D}{\overset{\text{D}}=}
\newcommand{\eD}{\overset{\text{D}}\to} 
\newcommand{\si}{\sigma}
\newcommand{\tZ}{\tilde Z}$


Let $(X\_1,\dots,X\_d)$ be the observed normal random vector. Then the Neyman--Pearson test will reject $H\_0$ if $S:=\sum\_1^d(X\_i-k\mu\_i)^2<c$, where $\mu=:(\mu\_1,\dots,\mu\_d)$ and $c$ is a critical value and 
\begin{equation\*}
 k:=\frac{\tau^2}{\tau^2-\sigma^2}. \tag{0.1}
\end{equation\*}
With $\al\in(0,1)$ fixed, for large $d$ the hypotheses $H\_0$ and $H\_1$ will be too easy to distinguish from each other (so that the power be close to $1$) unless $H\_0$ and $H\_1$ are close enough to each other. The following rather natural conditions will provide for that: 
\begin{equation\*}
 d\to\infty,\quad\tau^2\to\tau\_0^2\in(0,\infty),\quad \frac{\tau^2-\si^2}{\si^2}=\frac{\tau^2}{\si^2}-1\sim\frac{w^2}{\sqrt d},\quad \frac{\|\mu\|^2}{\si^2}\sim b^2 \tag{0.2}
\end{equation\*}
for some fixed $w,b$ in $(0,\infty)$, so that 
\begin{equation\*}
 \tau\sim\si,\quad k\sim\frac{\sqrt d}{w^2}\to\infty. \tag{0.3}
\end{equation\*}


Let $Z,Z\_1,Z\_2,\dots$ be iid standard normal random variables. 
Under $H\_0$, by the spherical symmetry, 
\begin{equation\*}
 S\D\sum\_1^d(\tau Z\_i-k\mu\_i)^2
 \D\tau^2((a\_0+Z\_1)^2+Z\_2^2+\dots+Z\_d^2), 
% \eD\tau^2(a\_0^2+d+Z\sqrt{2d}), 
\end{equation\*}
where $\D$ means the equality in distribution and 
\begin{equation\*}
 a\_0^2:=(k/\tau)^2\|\mu\|^2\sim k^2b^2\sim\frac{b^2}{w^2}\,d\to\infty. \tag{1}
\end{equation\*} 
By the central limit theorem, 
\begin{equation\*}
 \frac{Z\_2^2+\dots+Z\_d^2-d}{\sqrt d}\eD Z\sqrt2,
\end{equation\*}
where $\eD$ means the convergence in distribution. Also, by (1), 
\begin{equation\*}
 \frac{(a\_0+Z\_1)^2-a\_0^2}{\sqrt d}=\frac{2a\_0Z\_1+Z\_1^2}{\sqrt d}\to\frac{2b}w\,Z\_1 
\end{equation\*}
pointwise and hence in distribution. Thus, under $H\_0$,
\begin{equation\*}
(H\_0):\quad \frac{S/\tau^2-(a\_0^2+d)}{\sqrt d}\eD \frac{2b}w\,Z\_1+Z\sqrt2\D\la Z,\quad \la:=\sqrt{\frac{4b^2}{w^2}+2}. \tag{2}
\end{equation\*}


Similarly, under $H\_1$, 
\begin{equation\*}
 S\D\sum\_1^d(\si Z\_i-(k-1)\mu\_i)^2
 \D\si^2((a\_1+Z\_1)^2+Z\_2^2+\dots+Z\_d^2), 
% \eD\si^2(a\_1^2+d+Z\sqrt{2d}), 
\end{equation\*}
where 
\begin{equation\*}
 a\_1^2:=((k-1)/\si)^2\|\mu\|^2\sim a\_0^2\sim\frac{b^2}{w^2}\,d\to\infty, \tag{3}
\end{equation\*}
and hence, under $H\_1$,
\begin{equation\*}
(H\_1):\quad \tZ:=\frac{S/\si^2-(a\_1^2+d)}{\la \sqrt d}\eD Z; \tag{3.1}
\end{equation\*}
cf. (2). 


Choosing now the critical value 
\begin{equation\*}
 c:=\tau^2(a\_0^2+d+z\_\al\la\sqrt{d}), \tag{3.2}
\end{equation\*}
where $z\_\al:=\Phi^{-1}(\al)$ and $\Phi$ is the standard normal cdf, we see that the size of the test is 
\begin{equation\*}
 \P\_{H\_0}(S<c)=\P\_{H\_0}\Big(\frac{S-\tau^2(a\_0^2+d)}{\la\sqrt d}<z\_\al\Big)\to\P(Z<z\_\al)=\al, 
\end{equation\*}
as desired. 


Recalling (3.1), (3.2), (1), (3), (0.3), (0.2), the relation $k^2-(k-1)^2\sim2k$, and the definition of $\la$ in (2), for the power of the test we now have 
\begin{align\*}
 \P\_{H\_1}(S<c)&=\P\_{H\_1}\Big(\tZ<z\_\al\frac{\tau^2}{\si^2}
 +\frac{\tau^2-\si^2}{\la\si^2}\,\sqrt d
 +\frac{[k^2-(k-1)^2]\|\mu\|^2}{\la\si^2\sqrt{d}}\Big) \\ 
& \to\Phi\Big(z\_\al+(w^2+2b^2/w^2)\Big/\sqrt{\frac{4b^2}{w^2}+2}\Big), 
\end{align\*}
which latter is $>\al$, and it is close to $1$ if either $w$ or $b$ is large, which seems to agree with the intuition.


