Measure concentration inequalities

1 Background

Overviews include

• Roman Vershynin’s High-Dimensional Probability: An Introduction with Applications in Data Science (Vershynin 2018)
• Thomas Lumley’s super simple intro to chaining and controlling maxima.
• Dasgupta, Asymptotic Theory of Statistics and Probability (DasGupta 2008) is practical, and despite its name, introduces some basic non-asymptotic inequalities
• Raginsky and Sason, Concentration of Measure Inequalities in Information Theory, Communications and Coding (Raginsky and Sason 2012)
• Tropp, An Introduction to Matrix Concentration Inequalities (Tropp 2015) high-dimensional data! free!
• Boucheron, Bousquet & Lugosi, Concentration inequalities (Boucheron, Bousquet, and Lugosi 2004) (Clear and brisk but missing some newer stuff)
• Boucheron, Lugosi & Massart, Concentration inequalities: a nonasymptotic theory of independence (Boucheron, Lugosi, and Massart 2013). Haven’t read it yet.
• Massart, Concentration inequalities and model section (Massart 2007). Clear, focussed, but brusque. Depressingly, by being applied it also demonstrates the limitations of its chosen techniques, which seem sweet in application but bitter in the required assumptions. (Massart 2000) is an earlier draft.
• Lugosi’s Concentration-of-measure Lecture notes as good, especially for treatment of Efron-Stein inequalities. This taxonomy is used in his Combinatorial statistics notes.
• Terry Tao’s lecture notes
• Divergence in everything: erasure divergence and concentration inequalities
• Talagrand’s opus that is commonly credited with kicking off the modern fad, particularly the part due to the chaining method. (Talagrand 1995)
• Luca Trevisan wrote an example-driven explanation of Talagrand generic chaining.

2 Markov

For any nonnegative random variable $X,$ and $t>0$ $$\mathbb{P}\{X\ge t\}\le \frac{\mathbb{E}X}{t}$$ Corollary: if $\varphi$ is a strictly monotonically increasing non-negative-valued function then for any random variable $X$ and real number $t$ $$\mathbb{P}\{X\ge t\}=\mathbb{P}\{\varphi (X)\ge \varphi (t)\}\le \frac{\mathbb{E}\varphi (X)}{\varphi (t)}$$

3 Chebychev

A corollary of Markov’s bound is with $\varphi (x)=x^2$ is Chebyshev’s: if $X$ is an arbitrary random variable and $t>0,$ then $$\mathbb{P}\{|X-\mathbb{E}X|\ge t\}=\mathbb{P}\{|X-\mathbb{E}X{|}^2\ge t^2\}\le \frac{\mathbb{E}[|X-\mathbb{E}X{|}^2]}{t^2}=\frac{\mathrm{Var}\{X\}}{t^2}$$ More generally taking $\varphi (x)=x^q(x\ge 0),$ for any $q>0$ we have $$\mathbb{P}\{|X-\mathbb{E}X|\ge t\}\le \frac{\mathbb{E}[|X-\mathbb{E}X{|}^q]}{t^q}$$ We can choose $q$ to optimize the obtained upper bound for the problem in hand.

4 Hoeffding

Another one about sums of RVs, in particular for bounded RVs with potentially different bounds.

Let $X_1,X_2,\dots ,X_n$ be independent bounded random variables, in the sense that $a_i\le X_i\le b_i$ for all $i.$ Define the sum of these variables $S_n=\sum _{i=1}^n{X}_i.$ Let $\mu =\mathbb{E}[S_n]$ be the expected value of $S_n.$

Hoeffding’s inequality states that for any $t>0$,

$$\mathbb{P}(S_n-\mu \ge t)\le \exp (-\frac{2t^2}{\sum _{i=1}^n(b_i-a_i{)}^2})$$

and

$$\mathbb{P}(S_n-\mu \le -t)\le \exp (-\frac{2t^2}{\sum _{i=1}^n(b_i-a_i{)}^2}).$$

For example, consider $X_1,X_2,\dots ,X_n$ independent random variables taking values in $[0,1]$. For $S_n=\sum _{i=1}^n{X}_i$ and $\mu =\mathbb{E}[S_n],$ Hoeffding’s inequality becomes:

$$\mathbb{P}(S_n-\mu \ge t)\le \exp (-\frac{2t^2}{n}).$$

Cool, except my variates are rarely bounded. What do I do then? Probably Chernoff or Bernstein bounds.

5 Chernoff

Taking $\varphi (x)=e^{sx}$ where $s>0$, for any random variable $X$, and any $t>0$, we have $$\mathbb{P}\{X\ge t\}=\mathbb{P}\{e^{sX}\ge e^{st}\}\le \frac{\mathbb{E}[e^{sX}]}{e^{st}}.$$ $s$ is a free parameter we choose to make the bound as tight as possible.

That’s what I was taught in class. The lazy (e.g., me) might not notice that a useful bound for sums of RVs can be derived from this result because this tells us about the Laplace transform (i.e. Moment-generating function), which tells us about sums.

For independent random variables $X_1,X_2,\dots ,X_n$, let $S_n=\sum _{i=1}^n{X}_i$. We have $$\mathbb{P}(S_n\ge t)\le \underset{s>0}{inf}\frac{\mathbb{E}[e^{s{S}_n}]}{e^{st}}.$$ If $X_i$ are i.i.d., then $$\mathbb{P}(S_n\ge t)\le \underset{s>0}{inf}\frac{(\mathbb{E}[e^{s{X}_1}]{)}^n}{e^{st}}.$$

6 Bernstein inequality

Another one about bounded RVs. For independent zero-mean random variables $X_1,X_2,\dots ,X_n$ with $\mathbb{P}(|X_i|\le M)=1,$

$$\mathbb{P}(\sum _{i=1}^n{X}_i\ge t)\le \exp (-\frac{t^2/2}{\sum _{i=1}^n\mathbb{E}[X_i^2]+Mt/3})$$

7 Efron-Stein

Let $g:{\mathcal{X}}^n\to \mathbb{R}$ be a real-valued measurable function of n variables. Efron-Stein inequalities concern the difference between the random variable $Z=g(X_1,\dots ,X_n)$ and its expected value $\mathbb{E}X$ when $X_1,\dots ,X_n$ are arbitrary independent random variables.

Define ${\mathbb{E}}_i$ for the expected value with respect to the variable $X_i$, that is, $${\mathbb{E}}_{i}Z=\mathbb{E}[Z\mid X_1,\dots ,X_{i-1},X_{i+1},\dots ,X_n]$$ Then $$\mathrm{Var}(Z)\le \sum _{i=1}^n\mathbb{E}\left[{(Z-{\mathbb{E}}_{i}Z)}^2\right]$$

Now, let $X_1^{\prime },\dots ,X_n^{\prime }$ be an independent copy of $X_1,\dots ,X_n$. $$Z_i^{\prime }=g(X_1,\dots ,X_i^{\prime },\dots ,X_n)$$ Alternatively, $$\mathrm{Var}(Z)\le \frac{1}{2}\sum _{i=1}^n\mathbb{E}\left[{(Z-Z_i^{\prime })}^2\right]$$ Nothing here seems to constrain the variables here to be real-valued, merely the function $g$, but apparently they do not work for matrix variables as written — we need to see matrix Efron-Stein results for that.

8 Kolmogorov

🏗

9 Gaussian

For the Gaussian distribution. Filed there, perhaps?

10 Sub-Gaussian

🏗

E.g. Hanson-Wright.

11 Martingale bounds

🏗

12 Khintchine

Let us copy from wikipedia:

Heuristically: if we pick $N$ complex numbers $x_1,\dots ,x_N\in \mathbb{C}$, and add them together, each multiplied by jointly independent random signs $\pm 1$, then the expected value of the sum’s magnitude is close to $\sqrt{|x_1{|}^2+\cdots +|x_N{|}^2}$.

Let ${{\epsilon }_n}_{n=1}^N$ i.i.d. random variables with $P({\epsilon }_n=\pm 1)=\frac{1}{2}$ for $n=1,\dots ,N$, i.e., a sequence with Rademacher distribution. Let $0<p<\mathrm{\infty }$ and let $x_1,\dots ,x_N\in \mathbb{C}$. Then

$$A_p{(\sum _{n=1}^N|x_n{|}^2)}^{1/2}\le {\left(\mathrm{E}{\left|\sum _{n=1}^N{\epsilon }_n{x}_n\right|}^p\right)}^{1/p}\le B_p{(\sum _{n=1}^N|x_n{|}^2)}^{1/2}$$

for some constants $A_p,B_p>0$. It is a simple matter to see that $A_p=1$ when $p\ge 2$, and $B_p=1$ when $0<p\le 2$.

13 Empirical process theory

🏗

14 Matrix concentration

If we fix our interest to matrices in particular, some fun things arise. See Matrix concentration inequalities

15 Jensen gap

See Jensen gaps.

16 Incoming

• Rademacher Concentration Inequalities – Almost Sure
• Useful inequalities cheat sheet

17 References