The Optimal Sub-Gaussian Normalisation for Randomised Monotone Functions

Abstract: 

arXiv page: https://arxiv.org/abs/2312.01265

Site: https://sites.google.com/view/rabeetourky

Let $\mathcal{M}$ denote the class of randomised monotone functions on $\mathbb{R}$ with values in $[0,1]$, and let $U_{\mathcal{M}}\colon \mathbb{R}_{+} \to \mathbb{R}_{+}$ be the minimal function for which

\[

\mathbb{P}\left\{ \sqrt{\eta_f}\, \sup_{t\in\mathbb{R}} \bigl| f_Z(t) - \mathbb{E}[f_Z(t)] \bigr| \ge \varepsilon \sqrt{U_{\mathcal{M}}(\eta_f)} \right\} \le 2 e^{-2\varepsilon^2}

\]

holds for every member $f_Z$ of $\mathcal{M}$ with finite effective sample size $\eta_f$ and every positive $\varepsilon$. We prove that for every $x > 1$,

\[

\left| \sqrt{U_{\mathcal{M}}(x)} - \sqrt{\log_4 x} \right| \le 2 \min\left\{ 1,\, \frac{2\ln(e + \ln x)}{\sqrt{\ln x}} \right\}.

\]

The optimal adjustment $\sqrt{U_{\mathcal{M}}(x)}$ matches $\frac{1}{\sqrt{2\ln 2}}\sqrt{\ln x}$ for all $x > 1$, with residuals bounded as above.