Finite-Sample Concentration Bounds
Published:
This post summarizes some useful finite-sample concentration bounds.
Notations: $\mu=\mathbb{E}[X]$ and $\sigma^2=\text{Var}[X]$. For samples $X_1,\ldots,X_n$ of $X$, define $\overline{X}=\frac{1}{n}\sum\limits_{i=1}^nX_i$.
SubGaussian Tail Bounds
Suppose that $X$ is sub-Gaussian with mean $\mu=\mathbb{E}[X]$ and parameters $\sigma>0$, i.e., $$\mathbb{E}[\exp(t(X-\mu))]\leq \exp\left(\frac{\sigma^2t^2}{2}\right),\qquad \forall\ t\in\mathbb{R}.$$ Then the one-sided tail bound is given by $$\mathbb{P}(X-\mu\geq t)\leq \exp\left(-\frac{t^2}{2\sigma^2}\right),\qquad\forall\ t\geq 0.$$ and the two-sided tail bound is given by $$\mathbb{P}(|X-\mu|\geq t)\leq 2\exp\left(-\frac{t^2}{2\sigma^2}\right),\qquad\forall\ t\in\mathbb{R}.$$
Proof
By Chernoff bound, $$\begin{align*} \mathbb{P}(X-\mu\geq t)&\leq \inf\limits_{u\geq 0}\frac{\mathbb{E}[\exp(u(X-\mu))]}{\exp(ut)}\\ &\leq \inf\limits_{u\geq 0}\frac{\exp(\sigma^2u^2/2)]}{\exp(ut)}\\ &=\exp\left(-\frac{t^2}{2\sigma^2}\right). \end{align*}$$
SubExponential Tail Bounds
Suppose that $X$ is sub-exponential with parameters $(v, b)$, i.e., $$\mathbb{E}[\exp(t (X-\mu))]\leq \exp\left(\frac{v^2t^2}{2}\right),\qquad \forall\ |t|<\frac{1}{b}.$$ Then the one-sided tail bound is given by $$\mathbb{P}(X-\mu\geq t)\leq \begin{cases}e^{-\frac{t^2}{2v^2}} &, 0\leq t\leq \frac{v^2}{b}\\ e^{-\frac{t}{2b}} &, t> \frac{v^2}{b}\end{cases}\leq e^{-\frac{t^2}{2(v^2+bt)}},\qquad\forall\ t\geq 0.$$
Special Tail Bounds
| Name | Constraints on Variable | Finite-Sample Bound ($t>0$) | High-Probability Event (w.p. $\geq 1-\delta$) | Sample Complexity |
|---|---|---|---|---|
| Markov inequality | $X\geq 0$ | $\mathbb{P}(X\geq t)\leq \frac{\mu}{t}$ | ||
| Chebyshev inequality | $\sigma^2<\infty$ | $\mathbb{P}(|\overline{X}-\mu|\geq t\frac{\sigma}{\sqrt{n}})\leq \frac{1}{t^2}$ | $|\overline{X}-\mu|\leq \frac{\sigma}{\sqrt{n\delta}}$ | $\frac{\sigma^2}{\epsilon^2\delta}$ |
| Chernoff inequality | $\exp(t(X-\mu))$ exists for $t\in[0,b]$ $X\sim\mathcal{N}(\mu,\sigma^2)$ | $\mathbb{P}(\overline{X}-\mu\geq t)\leq \inf\limits_{0\leq u\leq b} \frac{\mathbb{E}[\exp(u(\overline{X}-\mu))]}{\exp(tu)}$ $\mathbb{P}(|\overline{X}-\mu|\geq t)\leq 2\exp\left(-\frac{nt^2}{2\sigma^2}\right)$ | $|\overline{X}-\mu|\leq\sigma\sqrt{\frac{2\log(2/\delta)}{n}}$ | $\frac{2\sigma^2\log(2/\delta)}{\epsilon^2}$ |
| Hoeffding's inequality | $a\leq X\leq b$ | $\mathbb{P}(|\overline{X}-\mu|\geq t)\leq 2\exp\left(- \frac{2nt^2}{(b-a)^2}\right)$ | $|\overline{X}-\mu|\leq (b-a)\sqrt{\frac{\log(2/\delta)}{2n}} $ | $\frac{(b-a)^2\log(2/\delta)}{2\epsilon^2}$ |
| Bernstein's inequality | $a\leq X\leq b$ | $\mathbb{P}(|\overline{X}-\mu|\geq t)\leq 2\exp\left(- \frac{nt^2}{2(\sigma^2+(b-a)t)}\right)$ | $|\overline{X}-\mu|\leq 4\sigma \sqrt{\frac{\log(2/\delta)}{n}}+\frac{4(b-a)\log(2/\delta)}{n}$ | |
| McDiarmid's inequality | $|f(x_1,\ldots,x_n)-f(x_1,\ldots,x_k',\ldots,x_n)|\leq L_k$ $\forall\ x,x'\in\mathbb{R}$, $\forall\ k$ | $\mathbb{P}(|f(X_1,\ldots,X_n)-\mathbb{E}[f(X_1,\ldots,X_n)]|\geq t)\leq 2\exp\left(-\frac{2t^2}{\sum\limits_{k=1}^nL_k^2}\right)$ | ||
| $\chi^2$ tail bound | $X\sim\chi^2(1)$ | $\mathbb{P}\left(|\overline{X}-1|\geq t\right)\leq 2\exp(-\frac{nt^2}{8})$, $\forall\ t\in(0,1)$. |
Bernstein's High Probability Event
Let $\delta= 2\exp\left(- \frac{nt^2}{2(\sigma^2+(b-a)t)}\right)$, we have that $$\begin{align*} t^2- \frac{2\log\left(2/\delta\right)}{n}(b-a)t- \frac{2\log\left(2/\delta\right)}{n}\sigma^2 = 0 \end{align*}$$ Note that $t\geq 0$, we have $$\begin{align*} t&=\frac{1}{2}\left[\frac{2\log\left(2/\delta\right)}{n}(b-a)+\sqrt{\left(\frac{2\log\left(2/\delta\right)}{n}\right)^2(b-a)^2+ \frac{8\log\left(2/\delta\right)}{n}\sigma^2}\right]\\ &\leq \frac{1}{2}\left[\frac{2\log\left(2/\delta\right)}{n}(b-a)+\sqrt{\left(\frac{2\log\left(2/\delta\right)}{n}(b-a)+ \sqrt{\frac{8\log\left(2/\delta\right)}{n}\sigma}\right)^2}\right]\\ &=\frac{1}{2}\left[\frac{2\log\left(2/\delta\right)}{n}(b-a)+\frac{2\log\left(2/\delta\right)}{n}(b-a)+ \sqrt{\frac{8\log\left(2/\delta\right)}{n}}\sigma\right]\\ &=2\sigma\sqrt{\frac{\log\left(2/\delta\right)}{n}}+ \frac{2\log\left(2/\delta\right)}{n}(b-a) \end{align*}$$