Using Hoeffding's inequality we know that for iid bounded random variables

\begin{align} \mathbb{P}(|\hat{\mu} -\mu| > \epsilon) \leq 2\exp(-2\epsilon^2n) \end{align}

where $\hat{\mu}$ is the sample average of n bounded random variables in $[0,1]$. Now suppose I have J such estimators, $\hat{\mu}_k,\ k=1,\ldots,J$. I am interested in the following concetration

\begin{align} \mathbb{P}(|\hat{\mu}_{(1)} -\mu_{(1)}| > \epsilon) \end{align}

$\hat{\mu}_{(1)}$ is the maximum of the estimators and $\mu_{(1)}$ is the corresponding mean. One can show that $|\hat{\mu}_{(1)} -\mu_{(1)}|$ is 1-Lipschitz and for sub-gaussian random variables

\begin{align} \mathbb{P}(|\hat{\mu}_{(1)} -\mu_{(1)}| > \epsilon) \leq 2\exp\left(-\frac{\epsilon^2}{2}\right) \end{align}

However, I want to use the original Hoeffding bound without any sub-gaussian assumption. So I use each of the J estimators to create a bound.

\begin{align} \mathbb{P}(|\hat{\mu}_{(1)} -\mu_{(1)}| > \epsilon) &\leq \mathbb{P}(|\hat{\mu}_{(1)} -\mu| > \epsilon) && \tag{Jensen's Inequality} \\ &\leq 2\sum_{k=1}^J \mathbb{P}(\hat{\mu}_k - \mu> \epsilon) && \tag{Union Bound}\\ & \leq 2\sum_{k=1}^J \exp(-2\epsilon^2n) = 2J\exp(-2\epsilon^2n) && \tag{Hoeffding's} \\ \end{align}

Unlike the previous sub-gaussian bound which was non-asymptotic, the above bound goes to zero with large n. I want to extend this idea to second maximum. However, I don't know how to go from $\mathbb{E}[\hat{\mu}_{(2)}]$ to $\mu$ because the second maximum function is neither convex nor concave. I started doing the following.

\begin{align} \mathbb{P}(|\hat{\mu}_{(2)}| > \epsilon) &\leq 2\mathbb{P}(\hat{\mu}_{(2)} > \epsilon) \\ &= 2\mathbb{P}\left(\left\{\exists s,t \in [J], s \ne t: \epsilon < \hat{\mu}_s \leq \hat{\mu}_t \right\}\right) \\ &= 2\mathbb{P}\left(\bigcup_{s=1}^J \bigcup_{\substack{t=1 \\s \ne t}}^J \left\{\epsilon < \hat{\mu}_s \leq \hat{\mu}_t \right\}\right) \\ &\leq 2\sum_{s=1}^J\sum_{\substack{t=1 \\s \ne t}}^J \mathbb{P}(\epsilon < \hat{\mu}_s \leq \hat{\mu}_t) && \tag{Union Bound} \\ &= 2(J-1)\sum_{s=1}^J\mathbb{P}(\epsilon < \hat{\mu}_s) && \tag{i.i.d} \end{align}

Can someone share ideas on how to incorporate mean in the following argument and get concentration for $\mathbb{P}(|\hat{\mu}_{(2)} - \mu_{(2)}|) $


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.