Notes / Concentration Inequalities
5.1 Suppose we have a random variable \(X \sim \mathbb {P}_X\) , sampled from the distribution \(\mathbb {P}_X\) . Let \(\mu = \mathbb {E}_{X \sim \mathbb {P}_X}[X]\) be its expectation. In general, \(|x - \mu |\) could
be very large. However, in many scenarios (especially when \(X\) takes a special form), \(|x - \mu |\) is very small with high
probability.
Lemma 5.1 (Markov's Inequality) . Let \(X\) be a nonnegative random variable. Then for all \(t > 0\) , \[ \mathbb {P}(X \geq t) \leq \frac {\mathbb {E}[X]}{t}. \]
Lemma 5.2 (Chernoff's Inequality) . For all \(t > 0\) , we have \[ \mathbb {P}(X \geq \mu + t) \leq \inf _{\lambda } \frac {\mathbb {E}[e^{\lambda (X-\mu )}]}{e^{\lambda t}} = e^{-h(t)}, \] where \[ h(t) = \sup _{\lambda } \lambda t - \log \mathbb {E}[e^{\lambda (X-\mu )}]. \]
Lemma 5.3 (Union Bound) . Suppose we have a collection of events \(\{E_s\}_{s \in [d]}\) . If \(\mathbb {P}(E_s^c) \leq \frac {\delta }{d}\) for all \(s\) , then \[ \mathbb {P}\!\left ( \bigcup _{s \in [d]} E_s \right ) \geq 1 - \delta . \]
5.1.1 Now we discuss an important type of random variables.
Definition 5.4 (Sub-Gaussian) . A random variable with \(\mu = \mathbb {E}[X]\) is \(\sigma \) -sub-Gaussian if there is a positive
number \(\sigma > 0\) such that \[ \mathbb {E}[e^{\lambda (X-\mu )}] \leq e^{\lambda ^2 \sigma ^2 / 2} \qquad \forall \lambda \in \mathbb {R}. \]
Proposition 5.5 (Hoeffding's Inequality) . Suppose \(X_i\) , \(i = 1, \ldots , n\) are independent, where \(X_i\) has mean \(\mu _i\) and is
\(\sigma _i\) -sub-Gaussian. Then
1. \(\sum _{i=1}^n X_i\) has mean \(\sum _{i=1}^n \mu _i\) and is sub-Gaussian with parameter \(\sqrt {\sum _{i=1}^n \sigma _i^2}\) .
2. \[ \mathbb {P}\!\left ( \sum _{i=1}^n (X_i - \mu _i) \geq t \right ) \leq \exp \!\left ( -\frac {t^2}{2 \sum _{i=1}^n \sigma _i^2} \right ). \]
Example 5.6 (Bounded random variable) . Let \(X \in P([a, b])\) . We claim that \(X\) is \((b-a)\) -sub-Gaussian.
Proof. Instead of a direct calculation, we use a series of tricks.
Trick 1: Let \(X' \stackrel {d}{=} X\) with \(X, X'\) independent. Then \[ \mathbb {E}_X[e^{\lambda (X-\mu )}] = \mathbb {E}_X[e^{\lambda X - \mathbb {E}_X[X']}] \] Trick 2: Use Jensen’s inequality to get \(e^{-\lambda \mathbb {E}[X']} \leq \mathbb {E}[e^{-\lambda X'}]\) . This gives \[ \leq \mathbb {E}_{X, X'}\, \mathbb {E}[e^{\lambda (X - X')}] \] Trick 3:
Introduce \(\varepsilon \sim \mathrm {Unif}(\{\pm 1\})\) with \(\varepsilon \) independent of \((X, X')\) . Then \(\varepsilon (X - X') \stackrel {d}{=} X - X'\) . \[ = \mathbb {E}_{\varepsilon , X, X'}\, \mathbb {E}[e^{\lambda \varepsilon (X - X')}] \] Using the tower property of conditional expectation, \[ = \mathbb {E}_{X, X'}\!\left [ \mathbb {E}_\varepsilon [e^{\lambda \varepsilon (X - X')} \mid X, X'] \right ] \] By the
\(1\) -sub-Gaussianity of \(\varepsilon \) , \[ \leq \mathbb {E}_{X, X'}[e^{\lambda ^2 (X - X')^2 / 2}] \] Since \((X - X')^2 \leq (b - a)^2\) by the boundedness of \(X, X'\) , \[ \leq e^{\lambda ^2 (b - a)^2 / 2}. {\qquad\square} \] □
Theorem 5.8 (Equivalent Conditions for Sub-Gaussians) . Let \(X\) be a random variable. Then the following are
equivalent:
(i) The tails of \(X\) satisfy \[ \mathbb {P}(|X| \geq t) \leq 2 \exp \!\left ( -\frac {t^2}{\kappa _1^2} \right ) \qquad \forall t \geq 0. \]
(ii) The moments of \(X\) satisfy \[ \|X\|_{L^p} = \left ( \mathbb {E}[|X|^p] \right )^{1/p} \leq \kappa _2 \sqrt {p}, \qquad \forall p \geq 1. \]
(iii) The moment generating function of \(X^2\) satisfies \[ \mathbb {E}[\exp (\lambda ^2 X^2)] \leq \exp (\kappa _3^2 \lambda ^2) \qquad \forall \lambda \text { such that } |\lambda | \leq \frac {1}{\kappa _3}. \]
(iv) The moment generating function of \(X^2\) is bounded at some point: \[ \mathbb {E}[\exp (X^2 / \kappa _4^2)] \leq 2. \] Moreover, if \(\mathbb {E}[X] = 0\) , then properties (i)–(iv) are also equivalent to
(v) The moment generating function of \(X\) satisfies \[ \mathbb {E}[\exp (\lambda X)] \leq \exp (\kappa _5^2 \lambda ^2 / 2) \qquad \forall \lambda \in \mathbb {R}. \] Here, \(\kappa _1, \ldots , \kappa _5\) are universal constants.
5.1.2 Let \(G \sim \mathcal {N}(0, 1)\) . Then \(G^2\) is not sub-Gaussian. This is because \(\mathbb {E}[G^2] = 1\) , and \begin{align*} \mathbb {E}[e^{\lambda (G^2 - 1)}] &= \frac {1}{\sqrt {2\pi }} \int _{-\infty }^{\infty } e^{\lambda (z^2 - 1)} e^{-z^2/2} \, dz \\ &= \begin {cases} \dfrac {e^{-\lambda }}{\sqrt {1 - 2\lambda }} & \lambda < 1/2 \\ \infty & \lambda \geq 1/2. \end {cases} \end{align*}
We can still derive a good but weaker tail bound for this kind of random variable.
Definition 5.9. A random variable \(X\) is \((\nu , \alpha )\) -sub-exponential if \[ \mathbb {E}[e^{\lambda (X - \mu )}] \leq e^{\lambda ^2 \nu ^2 / 2} \qquad \forall |\lambda | \leq \frac {1}{\alpha }. \]
We can see from this definition that sub-Gaussian variables are sub-exponential with any \(\alpha > 0\) .
Example 5.10. If \(G \sim \mathcal {N}(0, 1)\) , then \(G^2\) is \((2, 4)\) -sub-exponential.
Proof. We want to show that \[ \mathbb {E}[e^{\lambda (G^2 - 1)}] = \frac {e^{-\lambda }}{\sqrt {1 - 2\lambda }} \leq e^{2\lambda ^2} \qquad \forall |\lambda | \leq \frac {1}{4}. \] We can do this by comparing Taylor series. □
Proposition 5.11 (Bernstein Condition) . Suppose \(X\) has mean \(\mu \) and variance \(\sigma ^2\) . Suppose that \(\mathbb {E}[(X - \mu )^k] \leq \tfrac {1}{2} k! \, \sigma ^2 b^{k-2}\) for all \(k \geq 2\) .
Then \(X\) is \((\sqrt {2}\sigma , 2b)\) -sub-exponential.
Proof. We just need to show that the moment generating function is bounded. Do a Taylor expansion:
\begin{align*} \mathbb {E}[e^{\lambda (X-\mu )}] &= 1 + \frac {\lambda ^2 \sigma ^2}{2} + \sum _{k=3}^{\infty } \lambda ^k \frac {\mathbb {E}[(X-\mu )^k]}{k!} \\ &\leq 1 + \frac {\lambda ^2 \sigma ^2}{2} + \frac {\lambda ^2 \sigma ^2}{2} \sum _{k=3}^{\infty } (|\lambda | b)^{k-2}. \end{align*}
This is a geometric series, so we can simplify it: \begin{align*} &\leq 1 + \frac {\lambda ^2 \sigma ^2 / 2}{1 - b|\lambda |} \\ &\leq e^{(\lambda ^2 \sigma ^2 / 2) / (1 - b|\lambda |)}. \end{align*}
When \(|\lambda | \leq \tfrac {1}{2b}\) , \[ \leq e^{\lambda ^2 (\sqrt {2}\sigma )^2 / 2}. {\qquad\square} \] □
Lemma 5.12 (Bernstein's Inequality) . Let \(\{X_i\}_{i \in [n]}\) be independent with \(\mathbb {E}[X_i] = \mu _i\) and \(X_i\) \((\nu _i, \alpha _i)\) -sub-exponential. Then \(\sum _{i=1}^n (X_i - \mu _i)\) is
sub-exponential with parameters \(\nu _* = \sqrt {\sum _{i=1}^n \nu _i^2}\) and \(\alpha _* = \max _i \alpha _i\) . Moreover, \[ \mathbb {P}\!\left ( \frac {1}{n} \sum _{i=1}^n (X_i - \mu _i) \geq t \right ) \leq \begin {cases} e^{-n t^2 / (2 \nu _*^2)} & t \leq \nu _*^2 / \alpha _* \\ e^{-n t / (2 \alpha _*)} & t > \nu _*^2 / \alpha _*. \end {cases} \]
Theorem 5.13 (Strong Bernstein's Inequality) . Let \(X_1, \ldots , X_n\) be independent, mean-zero, with \(|X_i| \leq K\) for all \(i\) . Set \(\sigma ^2 = \sum _{i=1}^n \mathbb {E}[X_i^2]\) .
Then \[ \mathbb {P}\!\left ( \left | \sum _{i=1}^n X_i \right | \geq t \right ) \leq 2 \exp \!\left ( -\frac {t^2 / 2}{\sigma ^2 + K t / 3} \right ). \]
Example 5.15. Let \(Y = \sum _{i=1}^n Z_i^2\) with \(Z_i \sim \mathcal {N}(0, 1)\) . Then \(Y \sim \chi ^2(n)\) . Last time, we showed that \(Z_i^2\) is \(\mathrm {sE}(2, 4)\) , so \(Y \sim \mathrm {sE}(2\sqrt {n}, 4)\) . By Bernstein’s inequality, \[ \mathbb {P}\!\left ( \left | \frac {1}{n} \sum _{i=1}^n Z_i^2 - 1 \right | \geq t \right ) \leq 2 e^{-n t^2 / 8} \qquad \forall t \leq 1. \]
Here is a problem: Suppose we have \(\{u_1, u_2, \ldots , u_N\} \subseteq \mathbb {R}^d\) with a high dimension \(d\) . Can we find an \(F : \mathbb {R}^d \to \mathbb {R}^m\) with some small \(m\)
such that the distances are preserved? That is, we want \[ 1 - \delta \leq \frac {\|F(u_i) - F(u_j)\|_2^2}{\|u_i - u_j\|_2^2} \leq 1 + \delta , \qquad \forall i, j \in [N]. \]
How small can we make \(m\) ? The Johnson–Lindenstrauss lemma says that we can achieve this by
random projection.
Lemma 5.16 (Johnson–Lindenstrauss) . Let \(X \in \mathbb {R}^{m \times d}\) have entries \(X_{i,j} \overset {\mathrm {iid}}{\sim } \mathcal {N}(0, 1)\) , and let \(F : \mathbb {R}^d \to \mathbb {R}^m\) be defined as \(F(u) = \tfrac {1}{\sqrt {m}} X \cdot u\) . Then for any
fixed \(\{u_1, \ldots , u_N\} \subseteq \mathbb {R}^d\) , as long as \(m \gtrsim \tfrac {1}{\varepsilon ^2} \log \!\left (\tfrac {N}{\delta }\right )\) , with probability \(1 - \delta \) we have \[ 1 - \varepsilon \leq \frac {\|F(u_i) - F(u_j)\|_2^2}{\|u_i - u_j\|_2^2} \leq 1 + \varepsilon , \qquad \forall i, j \in [N]. \]
Proof. Denote \(Y_{i,j} = \frac {\|F(u_i) - F(u_j)\|_2^2}{\|u_i - u_j\|_2^2}\) . We claim that \(Y_{i,j} \sim \chi ^2(m)/m\) . Then Bernstein’s inequality will give \[ \mathbb {P}(|Y_{i,j} - 1| \geq t) \leq 2 e^{-m t^2 / 8} \qquad \forall t \leq 1. \] Using a union bound on all \(N(N-1) \leq N^2\)
pairs \(i \neq j\) , we get \[ \mathbb {P}\!\left ( \exists \, i, j \in [N] \text { s.t.\ } |Y_{i,j} - 1| \geq t \right ) \leq 2 N^2 e^{-m t^2 / 8} \qquad \forall t \leq 1. \] Setting the right-hand side equal to \(\delta \) , we can solve for \(m\) to get \[ m \geq \frac {8}{t^2} \log \!\left ( \frac {2 N^2}{\delta } \right ) = \frac {C}{t^2} \log \!\left ( \frac {N}{\delta } \right ). \]
Now let’s verify the claim that \(Y_{i,j} = \frac {\|F(u_i) - F(u_j)\|_2^2}{\|u_i - u_j\|_2^2} \sim \chi ^2(m)/m\) . Note that \[ \frac {1}{\sqrt {m}} X(u_i - u_j) \sim N\!\left ( 0, \frac {\|u_i - u_j\|_2^2}{m} I_m \right ), \] which implies that \[ \frac {\|X(u_i - u_j)\|_2^2}{m} \sim \frac {\|u_i - u_j\|_2^2 \cdot \chi ^2(m)}{m}. \] This proves the claim. □
Theorem 5.17 (Equivalent Conditions for sub-Exponentials) . The following statements are equivalent:
(a) \[ \mathbb {P}(|X| \geq t) \leq 2 \exp (-t / \kappa _1), \qquad \forall t \geq 0. \]
(b) \[ \|X\|_{L^p} = \left ( \mathbb {E}[|X|^p] \right )^{1/p} \leq \kappa _2 p, \qquad \forall p \geq 1. \]
(c) \[ \mathbb {E}[\exp (\lambda |X|)] \leq \exp (\kappa _3 \lambda ) \qquad \forall \lambda \text { s.t. } 0 \leq \lambda \leq \frac {1}{\kappa _3}. \]
(d) \[ \mathbb {E}[\exp (|X| / \kappa _4)] \leq 2. \] Moreover, if \(\mathbb {E}[X] = 0\) , then (a)–(d) are equivalent to
(e) \[ \mathbb {E}[\exp (\lambda X)] \leq \exp (\lambda ^2 \kappa _5^2 / 2) \qquad \forall |\lambda | \leq \frac {1}{\kappa _5}. \] Here, \(\kappa _1, \ldots , \kappa _5\) are universal constants.
Example 5.18. Let \(X_1 \sim \mathrm {sG}(\sigma _1)\) and \(X_2 \sim \mathrm {sG}(\sigma _2)\) be not necessarily independent with \(\mathbb {E}[X_1] = \mathbb {E}[X_2] = 0\) . We claim that \(X_1 X_2 \sim \mathrm {sE}(K \sigma _1 \sigma _2, K \sigma _1 \sigma _2)\) for some universal \(K\) .
Lemma 5.19 (Bennett's Inequality) . Let \((X_i)_{i \in [n]}\) be independent, where \(X_i - \mathbb {E}[X_i] \leq b\) a.s., and \(\nu _i^2 := \mathrm {Var}(X_i)\) for all \(i \in [n]\) . Then \[ \mathbb {P}\!\left ( \sum _{i=1}^n (X_i - \mathbb {E}[X_i]) \geq t \right ) \leq \exp \!\left ( -\frac {\sum _{i=1}^n \nu _i^2}{b^2} \, h\!\left ( \frac {b t}{\sum _{i=1}^n \nu _i^2} \right ) \right ), \] where \(h(u) = (1 + u) \log (1 + u) - u\) .
5.1.3
Lemma 5.20. Let \((X_i)_{i \in [n]}\) be a sequence of random variables. For any convex, strictly increasing \(\psi : \mathbb {R} \to \mathbb {R}_{\geq 0}\) , we have
\begin{align*} &\mathbb {E}\!\left [ \max _{i \in [n]} X_i \right ] \leq \psi ^{-1}\!\left ( \sum _{i=1}^n \mathbb {E}[\psi (X_i)] \right ), \\ &\mathbb {P}\!\left ( \max _{i \in [n]} X_i \geq t \right ) \leq \sum _{i=1}^n \frac {\mathbb {E}[\psi (X_i)]}{\psi (t)}. \end{align*}
Proof. \begin{align*} \mathbb {E}\!\left [ \max _{i \in [n]} X_i \right ] &= \mathbb {E}\!\left [ \psi ^{-1}\!\left ( \max _{i \in [n]} \psi (X_i) \right ) \right ] && \text {($\psi $ strictly increasing)} \\ &\leq \psi ^{-1}\!\left ( \mathbb {E}\!\left [ \max _{i \in [n]} \psi (X_i) \right ] \right ) && \text {(Jensen, $\psi ^{-1}$ concave)} \\ &\leq \psi ^{-1}\!\left ( \sum _{i=1}^n \mathbb {E}[\psi (X_i)] \right ) && \text {(max $\leq $ sum)}. {\qquad\square} \end{align*}
□
Example 5.21. For \(X_i \sim \mathrm {sG}(\sigma )\) , take \(\psi (u) = e^{\lambda u}\) . Optimizing over \(\lambda \) , we get \[ \mathbb {E}\!\left [ \max _{i \in [n]} X_i \right ] \leq \sigma \sqrt {2 \log n}. \]
This gives an important intuition: \(n\) sub-Gaussian random variables have maximum of order \(\sqrt {\log n}\) .