Return to Answer

This is what I've come up with. It's too long to be a comment, so I decided to post it as an answer.

So, it was proven in LeCam, L. M. (1969). Théorie Asymptotique de la Décision Statistique, p35 that $D_{\text{Hell}}(\cdot\|\cdot)^2/2 \le TV(\cdot, \cdot) \le D_{\text{Hell}}(\cdot\|\cdot)$. On the other hand, Theorem 2 of this paper proves a powerful nonasymptotic tail bound on the $TV(P\|\hat{P}_N)$, namely

For every $\epsilon \ge \sqrt{k/N}$, one has $$ P(TV(P\|\hat{P}_N) > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon-\sqrt{k/N})^2\right). $$

Putting things together, we have

For every $\epsilon \ge 2\sqrt{k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N)^2 > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon/2-\sqrt{k/N})^2\right). $$

from which one may immediate recover a nonasymptotic sub-exponential tail bound for $D_{\text{Hell}}(P\|\hat{P}_N)$, as dreamed, for example

For every $\epsilon \ge 4\sqrt{5k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N) > \epsilon) \le \exp(-0.075N\epsilon). $$

This is what I've come up with. It's too long to be a comment, so I decided to post it as an answer.

So, it was proven in LeCam, L. M. (1969). Théorie Asymptotique de la Décision Statistique, p35 that $D_{\text{Hell}}(\cdot\|\cdot)^2/2 \le TV(\cdot, \cdot) \le D_{\text{Hell}}(\cdot\|\cdot)$. On the other hand, Theorem 2 of this paper proves a powerful nonasymptotic tail bound on the $TV(P\|\hat{P}_N)$, namely

For every $\epsilon \ge \sqrt{k/N}$, one has $$ P(TV(P\|\hat{P}_N) > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon-\sqrt{k/N})^2\right). $$

Putting things together, we have

For every $\epsilon \ge 2\sqrt{k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N)^2 > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon/2-\sqrt{k/N})^2\right). $$

from which one may immediate recover a nonasymptotic sub-exponential tail bound for $D_{\text{Hell}}(P\|\hat{P}_N)$, as dreamed, for example

For every $\epsilon \ge 4\sqrt{5k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N) > \sqrt{\epsilon}) \le \exp(-0.075N\epsilon^2). $$

This is what I've come up with. It's too long to be a comment, so I decided to post it as an answer.

So, tt was proven in LeCam, L. M. (1969). Théorie Asymptotique de la Décision Statistique, p35 that $D_{\text{Hell}}(\cdot\|\cdot)^2/2 \le TV(\cdot, \cdot) \le D_{\text{Hell}}(\cdot\|\cdot)$. On the other hand, Theorem 2 of this paper proves a powerful nonasymptotic tail bound on the $TV(P\|\hat{P}_N)$, namely

For every $\epsilon \ge \sqrt{k/N}$, one has $$ P(TV(P\|\hat{P}_N) > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon-\sqrt{k/N})^2\right). $$

Putting things together, we have

For every $\epsilon \ge 2\sqrt{k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N)^2 > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon/2-\sqrt{k/N})^2\right). $$

from which one may immediate recover a nonasymptotic sub-exponential tail bound for $D_{\text{Hell}}(P\|\hat{P}_N)$, as dreamed, for example

For every $\epsilon \ge 4\sqrt{5k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N) > \epsilon) \le \exp(-0.075N\epsilon). $$

This is what I've come up with. It's too long to be a comment, so I decided to post it as an answer.

So, it was proven in LeCam, L. M. (1969). Théorie Asymptotique de la Décision Statistique, p35 that $D_{\text{Hell}}(\cdot\|\cdot)^2/2 \le TV(\cdot, \cdot) \le D_{\text{Hell}}(\cdot\|\cdot)$. On the other hand, Theorem 2 of this paper proves a powerful nonasymptotic tail bound on the $TV(P\|\hat{P}_N)$, namely

For every $\epsilon \ge \sqrt{k/N}$, one has $$ P(TV(P\|\hat{P}_N) > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon-\sqrt{k/N})^2\right). $$

Putting things together, we have

For every $\epsilon \ge 2\sqrt{k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N)^2 > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon/2-\sqrt{k/N})^2\right). $$

from which one may immediate recover a nonasymptotic sub-exponential tail bound for $D_{\text{Hell}}(P\|\hat{P}_N)$, as dreamed, for example

For every $\epsilon \ge 4\sqrt{5k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N) > \epsilon) \le \exp(-0.075N\epsilon). $$

This is what I've come up with. It's too long to be a comment, so I decided to post it as an answer.

So, tt was proven in LeCam, L. M. (1969). Théorie Asymptotique de la Décision Statistique, p35 that $D_{\text{Hell}}(\cdot\|\cdot)^2/2 \le TV(\cdot, \cdot) \le D_{\text{Hell}}(\cdot\|\cdot)$. On the other hand, Theorem 2 of this paper proves a powerful nonasymptotic tail bound on the $TV(P\|\hat{P}_N)$, namely

For every $\epsilon \ge \sqrt{k/N}$, one has $$ P(TV(P\|\hat{P}_N) > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon-\sqrt{k/N})^2\right). $$

Putting things together, we have

For every $\epsilon \ge 2\sqrt{k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N)^2 > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon/2-\sqrt{k/N})^2\right). $$

from which one may immediate recover a nonasymptotic sub-exponential tail bound for $D_{\text{Hell}}(P\|\hat{P}_N)$, as dreamed.

This is what I've come up with. It's too long to be a comment, so I decided to post it as an answer.

So, tt was proven in LeCam, L. M. (1969). Théorie Asymptotique de la Décision Statistique, p35 that $D_{\text{Hell}}(\cdot\|\cdot)^2/2 \le TV(\cdot, \cdot) \le D_{\text{Hell}}(\cdot\|\cdot)$. On the other hand, Theorem 2 of this paper proves a powerful nonasymptotic tail bound on the $TV(P\|\hat{P}_N)$, namely

For every $\epsilon \ge \sqrt{k/N}$, one has $$ P(TV(P\|\hat{P}_N) > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon-\sqrt{k/N})^2\right). $$

Putting things together, we have

For every $\epsilon \ge 2\sqrt{k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N)^2 > \epsilon) \le \exp\left(-\frac{N}{2}(\epsilon/2-\sqrt{k/N})^2\right). $$

from which one may immediate recover a nonasymptotic sub-exponential tail bound for $D_{\text{Hell}}(P\|\hat{P}_N)$, as dreamed, for example

For every $\epsilon \ge 4\sqrt{5k/N}$, one has $$ P(D_{\text{Hell}}(P\|\hat{P}_N) > \epsilon) \le \exp(-0.075N\epsilon). $$