# Upper Bound for some random sequence

Define $$\{\xi_i\}$$ as a sequence of i.i.d. subgaussian random variables, which satisfies the (generalized) Hoeffding inequality \begin{align*} P\left(\left|\sum_{i=1}^n\xi_ia_i\right| > t \right) \leq 2 \exp \left(-\frac{t^2}{c\|a\|_2^2}\right) \end{align*} for any vector $$a=(a_1,\dots,a_n)$$ and some constant $$c>0$$. Meanwhile, for some $$n$$-dimensional parameter vector $$\theta$$ and its estimator $$\hat{\theta}$$ that is not independent of $$\xi$$, suppose that the descrepancy $$\delta=\hat{\theta}-\theta$$ satisfies $$\|\delta\|_2\leq C r_n$$ a.s. for some positive constant $$C$$ and (non-random) sequence $$r_n\to 0$$ as $$n\to \infty$$. Now we want to get a "good" upper bound for $$\left|\sum_{i=1}^n\xi_i\delta_i\right|$$ that holds with high probability. That is, we want to find a "good" sequence $$t_n$$ such that \begin{align*} P\left(\left|\sum_{i=1}^n\xi_i\delta_i\right| > t_n \right) \to 0. \end{align*} Intuitively, if the vector $$\delta$$ could be treated as non-random, we would get \begin{align*} P\left(\left|\sum_{i=1}^n\xi_i\delta_i\right| > t \right) \leq 2 \exp \left(-\frac{t^2}{c^2\|\delta\|_2^2}\right) \leq 2 \exp \left(-\frac{t^2}{c^2C^2 r_n^2}\right) \end{align*} by the Hoeffding inequality. Thus, if this is correct, putting $$t=cCr_n\sqrt{\log n} \equiv t_n$$ leads to the bound, $$\left|\sum_{i=1}^n\xi_i\delta_i\right|\leq t_n$$, which holds with probability greater than $$1-2/n$$.

My concern is that this argument is not mathematically rigorous. I think we have to be careful in uniformity and consider \begin{align*} P\left(\sup_{\delta:\|\delta\|_2\leq Cr_n}\left|\sum_{i=1}^n\xi_i\delta_i\right|>t\right), \end{align*} but how can we deal with this probability? Probably, as far as I've seen, some covering number technique will be helpful, but I'm not sure the actual operation... I'm grateful if someone kindly helps me how to do it.

I think that your approach is correct, basically if you know that $$\|\delta\|_2\le Cr_n$$ almost surely, you can get the bound : $$\mathbb P\left(\left|\sum_{i=1}^n\xi_i\delta_i\right|>t\right)\le \mathbb P\left(\sup_{\delta:\|\delta\|_2\leq Cr_n}\left|\sum_{i=1}^n\xi_i\delta_i\right|>t\right)\tag1$$ Then, to bound the probability on the RHS, you might want to apply a union bound over the set $$\{\delta:\|\delta\|_2\leq Cr_n\}$$, but its cardinal is infinite/uncountable so this approach can't work here. Usually in such situations, covering numbers are a good tool to circumvent these issues, but I believe that they are not needed here.

Indeed, by Cauchy-Schwarz inequality, you have that for all $$\delta \in\mathcal B_n := \{\delta:\|\delta\|_2\le Cr_n\}$$ : \begin{align}\left|\sum_{i=1}^n\xi_i\delta_i\right| &= \left|\langle\xi,\delta\rangle\right|\\ &\le \|\xi\|_2\cdot \|\delta\|_2\\ &\le \|\xi\|_2 \cdot Cr_n\end{align} Because this bound holds for all $$\delta\in\mathcal B_n$$, you can take the supremum over $$\delta$$, which implies that : $$\sup_{\delta\in\mathcal B_n}\left|\sum_{i=1}^n\xi_i\delta_i\right|\le\|\xi\|_2 \cdot Cr_n \tag2$$ Plugging this inequality back into $$(1)$$ gives : \begin{align}\mathbb P\left(\left|\sum_{i=1}^n\xi_i\delta_i\right|>t\right)&\le \mathbb P\left(\sup_{\delta\in \mathcal B_n}\left|\sum_{i=1}^n\xi_i\delta_i\right|>t\right)\\ &\le \mathbb P\left(\|\xi\|_2 \cdot Cr_n>t\right)\\ &= \mathbb P\left(\|\xi\|_2 >\frac{t}{Cr_n}\right)\\ &\le \mathbb P\left(\max_{1\le i\le n}|\xi_i| >\frac{t}{Cr_n\sqrt n}\right)\tag3\\ &\le 2n\exp\left(-\frac{t^2}{cnC^2r_n^2}\right)\tag4\end{align}

Where I used the fact that $$\{\|\xi\|_2>x\}\subseteq\{\|\xi\|_\infty>x/\sqrt n\}$$ for inequality $$(3)$$ and the sub-Gaussianity of $$\xi$$ for inequality $$(4)$$.

It now follows that by choosing $$t_n :=Cr_n\sqrt{cn\log (n^2)}$$, the bound $$\left|\sum_{i=1}^n\xi_i\delta_i\right|\leq t_n$$ will hold with probability greater than $$1-2/n$$.

(Addendum) Using covering numbers : Let $$\epsilon>0$$ and denote by $$\Delta_{n,\epsilon}$$ an $$\epsilon$$-covering of $$\mathcal B_n := \{\delta:\|\delta\|_2\le Cr_n\}$$ with respect to $$\|\cdot\|_2$$ of minimum cardinality. Now, for any $$\delta\in\mathcal B_n$$, there exists by definition $$\bar\delta\in\Delta_{n,\epsilon}$$ such that $$\|\delta-\bar\delta\|_2\le\epsilon$$.

Hence, \begin{align}\left|\sum_{i=1}^n\xi_i\delta_i\right| &=\left|\sum_{i=1}^n\xi_i(\delta_i-\bar\delta_i + \bar\delta_i)\right|\\ &\le \underbrace{\left|\sum_{i=1}^n\xi_i(\delta_i-\bar\delta_i)\right|}_{(*)} + \left|\sum_{i=1}^n\xi_i\bar\delta_i\right|\tag5\\ &\le \sup_{\nu:\|\nu\|_2\le \epsilon}\left|\sum_{i=1}^n\xi_i\nu_i\right| + \sup_{\bar\delta\in\Delta_{n,\epsilon}}\left|\sum_{i=1}^n\xi_i\bar\delta_i\right| \end{align}

Because the bound holds for all $$\delta\in\mathcal B_n$$, we can take the supremum and get that for all $$t>0$$ : \begin{align}\mathbb P\left(\sup_{\delta:\|\delta\|_2\leq Cr_n}\left|\sum_{i=1}^n\xi_i\delta_i\right|>t\right) &\le \mathbb P\left(\sup_{\nu:\|\nu\|_2\le \epsilon}\left|\sum_{i=1}^n\xi_i\nu_i\right| + \sup_{\bar\delta\in\Delta_{n,\epsilon}}\left|\sum_{i=1}^n\xi_i\bar\delta_i\right|>t\right)\\ &\le \mathbb P\left(\left\{\sup_{\nu:\|\nu\|_2\le \epsilon}\left|\sum_{i=1}^n\xi_i\nu_i\right|>t/2\right\}\right.\\ &\left.\bigcup \left\{ \sup_{\bar\delta\in\Delta_{n,\epsilon}}\left|\sum_{i=1}^n\xi_i\bar\delta_i\right|>t/2\right\}\right)\\ &\le\mathbb P\left(\left\{\sup_{\nu:\|\nu\|_2\le \epsilon}\left|\sum_{i=1}^n\xi_i\nu_i\right|>t/2\right\}\right)\tag{A}\\ &+\mathbb P\left(\left\{ \sup_{\bar\delta\in\Delta_{n,\epsilon}}\left|\sum_{i=1}^n\xi_i\bar\delta_i\right|>t/2\right\}\right)\tag{B} \end{align} Now, term $$(B)$$ can be easily bounded by applying a union bound, which will make the covering number appear : \begin{align}\mathbb P\left( \sup_{\bar\delta\in\Delta_{n,\epsilon}}\left|\sum_{i=1}^n\xi_i\bar\delta_i\right|>t/2\right)&\le\mathbb P\left( \bigcup_{\bar\delta\in\Delta_{n,\epsilon}}\left\{\left|\sum_{i=1}^n\xi_i\bar\delta_i\right|>t/2\right\}\right)\\ &\le 2|\Delta_{n,\epsilon}|\exp\left(-\frac{t^2}{4cC^2r_n^2}\right)\end{align} Where $$|\Delta_{n,\epsilon}|$$ denotes the cardinal of $$\Delta_{n,\epsilon}$$, and is by definition the $$\epsilon$$-covering number of $$\mathcal B_n$$.

This is good, but the issue is term $$(A)$$, which involves a supremum over an uncountable set. For that term, there isn't a better way (that I can think of) to get a useful bound than applying Cauchy-Schwarz as I did above and basically reproduce the derivations that lead to inequality $$(4)$$. This gives the following bound : $$\mathbb P\left(\sup_{\nu:\|\nu\|_2\le \epsilon}\left|\sum_{i=1}^n\xi_i\nu_i\right|>t/2\right)\le 2n\exp\left(-\frac{t^2}{4cn\epsilon^2}\right)$$ So that unwanted $$n$$ in the denominator appears again, which seems like bad news... but isn't that big of a deal !
Indeed, $$\epsilon$$ is arbitrary, so simply setting $$\epsilon\equiv\epsilon_n :=1/\sqrt n$$ makes that term disappear. I will let you figure out which values of $$t_n$$ give the high-probability bound you need, but it shouldn't be too hard to figure out at this point.

• Thank you so much for the response, but I suspect that there is a mistake in the last display; the inequality $\|\xi\|_2\leq \max_{i}|\xi_i|$ does not hold. We need an extra $\sqrt{n}$. Sep 5, 2022 at 15:24
• Yes, good catch ! Just edited my answer. Sep 5, 2022 at 17:34
• Yes, this is correct, but I don't think the bound is tight due to the extra $\sqrt{n}$ in (3). My intuition is that $\left|\sum_{i=1}^n\xi_i\delta_i\right|$ should not be broken and we stick to using the Hoeffding inequality. To this end, the covering number and union bound is needed... Sep 6, 2022 at 0:00
• Covering number argument seems to work indeed, see my edit. I thought that the term $(*)$ in equation $(5)$ not being almost surely bounded would be an issue but it is possible to work around it apparently. Let me know if you spot any mistakes Sep 6, 2022 at 9:38
• Thanks a lot! Let me read your answer carefully. I'd like to give you a comment later. Sep 6, 2022 at 12:43