Lecture 6: Bernstein’s Inequality and Dimension Reduction
From sub-exponential tails to random projections
Lecture 5 showed that sums of independent sub-Gaussian variables add their variance proxies, a Pythagorean theorem for \(\psi_2\) control. Without \(\psi_2\) control on the summands, no Gaussian tail is available at all: a single heavy-tailed term dominates a sum no matter how many other terms are added to it. Bernstein’s inequality is what replaces the Gaussian tail when only \(\psi_1\) control, sub-exponential tails, is available. We then use it to answer a geometric question: how few dimensions does a random projection need in order to almost preserve all pairwise distances among \(n\) points?
1 Sums of independent random variables
Recall the Pythagorean theorem of Lecture 5. If \(X_1,\ldots,X_n\) are independent, mean-zero, and \(V_i\)-subgaussian, then \[ \mathbb E\exp\Big(\lambda\sum_{i=1}^nX_i\Big) =\prod_{i=1}^n\mathbb Ee^{\lambda X_i} \leq\prod_{i=1}^n\exp\Big(\frac{\lambda^2V_i}2\Big), \] so the sum is \(\big(\sum_iV_i\big)\)-subgaussian, and for every \(t\geq0\) \[ \mathbb P\Big\{\sum_{i=1}^nX_i>t\Big\} \leq\exp\left(-\frac{t^2}{2\sum_{i=1}^nV_i}\right). \]
Now suppose the \(X_i\) are controlled only in the \(\psi_1\) norm. A single variable with \(\|X\|_{\psi_1}<\infty\) has an exponential tail, by the Markov-inequality direction of the equivalence theorem in Lecture 5: \[ \mathbb P\{|X|\geq t\}\leq2\exp\left(-\frac t{\|X\|_{\psi_1}}\right) \qquad(t\geq0). \] This tail is genuinely heavier than Gaussian, and it does not go away when \(X\) is added to other independent variables. So a sum of \(\psi_1\)-controlled variables cannot satisfy an unconditional Gaussian tail bound, and a new inequality is needed.
Write \(K=\|X\|_{\psi_1}\). Since \(u\leq e^u-1\) for \(u\geq0\), \[ |\mathbb EX|\leq\mathbb E|X|\leq K\,\mathbb E\big(e^{|X|/K}-1\big)\leq K . \] By Cauchy–Schwarz, \[ \mathbb Ee^{|X-\mathbb EX|/(2K)} \leq e^{|\mathbb EX|/(2K)}\,\big(\mathbb Ee^{|X|/K}\big)^{1/2} \leq\sqrt{2e}, \] and Markov’s inequality gives, for every \(t\geq0\), \[ \mathbb P\{|X-\mathbb EX|\geq t\}\leq3\exp\left(-\frac t{2\|X\|_{\psi_1}}\right). \] So the centered variable has the same tail scale, up to a factor \(2\).
2 Bernstein’s condition
The Gaussian tail of Lecture 4 came from a bound on the moment generating function valid for every \(\lambda\). With only \(\psi_1\) control, or only a bound on \(\|X\|_{L^\infty}\), the same Gaussian-type bound still holds, but only for \(\lambda\) in a bounded window.
Lemma 1 (Bernstein’s condition) Let \(X\) be a random variable.
- If \(\|X\|_{\psi_1}<\infty\), then for every \(\lambda\) with \(|\lambda|\,\|X\|_{\psi_1}\leq\frac12\), \[ \mathbb Ee^{\lambda X}\leq\exp\!\big(\lambda\,\mathbb EX+4\lambda^2\|X\|_{\psi_1}^2\big). \]
- If \(\|X\|_{L^\infty}<\infty\), then for every \(\lambda\) with \(|\lambda|\,\|X\|_{L^\infty}\leq\frac12\), \[ \mathbb Ee^{\lambda X}\leq\exp\!\Big(\lambda\,\mathbb EX+\frac{\sqrt e}2\lambda^2\,\mathbb EX^2\Big). \]
Dividing by \(e^{\lambda\mathbb EX}\), both statements bound the moment generating function of the centered variable \(X-\mathbb EX\) by \(\exp(C_0\lambda^2\sigma^2)\) in the window, with \(\sigma^2=\|X\|_{\psi_1}^2\) and \(C_0=4\) in the first case, and \(\sigma^2=\mathbb EX^2\) and \(C_0=\sqrt e/2\) in the second.
Let \(M(\lambda)=\mathbb Ee^{\lambda X}\). Then \[ M(0)=1, \qquad M'(0)=\mathbb EX, \qquad M''(\lambda)=\mathbb E\big(X^2e^{\lambda X}\big). \] Taylor’s formula with integral remainder gives, for every \(\lambda\), \[ M(\lambda)=1+\lambda\,\mathbb EX+\int_0^\lambda(\lambda-s)M''(s)\,ds . \] If \(M''(s)\leq B\) on the interval between \(0\) and \(\lambda\), then \[ M(\lambda)\leq1+\lambda\,\mathbb EX+\frac{B\lambda^2}2 \leq\exp\Big(\lambda\,\mathbb EX+\frac{B\lambda^2}2\Big), \] using \(1+u\leq e^u\). It remains to bound \(M''\) in each case.
Part 1. Rescale so that \(\|X\|_{\psi_1}=1\), that is \(\mathbb Ee^{|X|}\leq2\), and take \(|\lambda|\leq\frac12\). Every Taylor term of \(e^{|X|}-1\) is at most the whole, so \[ \frac{\mathbb EX^4}{4!}\leq\mathbb E\big(e^{|X|}-1\big)\leq1, \qquad\text{i.e.}\qquad \mathbb EX^4\leq24 . \] By Cauchy–Schwarz and \(2|\lambda|\leq1\), \[ \begin{aligned} M''(\lambda)=\mathbb E\big(X^2e^{\lambda X}\big) &\leq\big(\mathbb EX^4\big)^{1/2}\big(\mathbb Ee^{2\lambda X}\big)^{1/2}\\ &\leq\sqrt{24}\,\big(\mathbb Ee^{|X|}\big)^{1/2} \leq\sqrt{48}<7 . \end{aligned} \] So \(B=7\) works, and \(7/2\leq4\). Undoing the rescaling gives the claim.
Part 2. Here \(|\lambda X|\leq|\lambda|\,\|X\|_{L^\infty}\leq\frac12\) pointwise, so \[ M''(\lambda)=\mathbb E\big(X^2e^{\lambda X}\big)\leq\sqrt e\,\mathbb EX^2 , \] a bound not depending on \(\lambda\) within the window. Take \(B=\sqrt e\,\mathbb EX^2\).
Part 2 uses the true second moment rather than a proxy, and is the sharper statement whenever \(X\) happens to be bounded. Part 1 needs only sub-exponential tails, at the cost of using \(\|X\|_{\psi_1}^2\) in place of \(\mathbb EX^2\).
3 Bernstein’s inequality
Corollary 1 (Bernstein’s inequality, \(\psi_1\) version) Let \(X=\sum_{i=1}^nX_i\) with \(X_1,\ldots,X_n\) independent. There is an absolute constant \(c>0\) such that, for every \(t\geq0\), \[ \begin{aligned} &\mathbb P\{|X-\mathbb EX|>t\}\\ &\quad\leq2\exp\left(-c\min\left\{\frac t{\max_i\|X_i\|_{\psi_1}},\ \frac{t^2}{\sum_i\|X_i\|_{\psi_1}^2}\right\}\right). \end{aligned} \]
Corollary 2 (Bernstein’s inequality, \(L^2\)–\(L^\infty\) version) Under the same hypotheses, for every \(t\geq0\), \[ \begin{aligned} &\mathbb P\{|X-\mathbb EX|>t\}\\ &\quad\leq2\exp\left(-c\min\left\{\frac t{\max_i\|X_i\|_{L^\infty}},\ \frac{t^2}{\sum_i\mathbb EX_i^2}\right\}\right). \end{aligned} \]
Both versions follow from the same argument. Let \(R\) be the maximum of the \(\|X_i\|_{\psi_1}\) (respectively \(\|X_i\|_{L^\infty}\)), let \(V\) be the sum of the \(\|X_i\|_{\psi_1}^2\) (respectively \(\mathbb EX_i^2\)), and let \(C_0=4\), which dominates the constants in both parts of Lemma 1.
Step 1: the moment generating function. For every \(\lambda\) with \(|\lambda|R\leq\frac12\), each \(X_i\) satisfies the hypothesis of Lemma 1, so by independence \[ \mathbb Ee^{\lambda(X-\mathbb EX)} =\prod_{i=1}^n\mathbb Ee^{\lambda(X_i-\mathbb EX_i)} \leq\exp\big(C_0\lambda^2V\big). \]
Step 2: Chernoff’s method. For \(t\geq0\) and \(0\leq\lambda\leq1/(2R)\), \[ \mathbb P\{X-\mathbb EX\geq t\} \leq\exp\big(C_0\lambda^2V-\lambda t\big). \] The exponent is a parabola in \(\lambda\), minimized at \(\lambda^*=t/(2C_0V)\). There are two cases.
Case 1: \(\lambda^*\leq1/(2R)\). The unconstrained minimizer is feasible, and it gives \[ \mathbb P\{X-\mathbb EX\geq t\}\leq\exp\left(-\frac{t^2}{4C_0V}\right). \]
Case 2: \(\lambda^*>1/(2R)\). Equivalently \(V<Rt/C_0\). Use the boundary value \(\lambda=1/(2R)\) instead: \[ \exp\left(-\frac t{2R}+\frac{C_0V}{4R^2}\right) \leq\exp\left(-\frac t{2R}+\frac t{4R}\right) =\exp\left(-\frac t{4R}\right). \] This is a weaker bound than the Gaussian one of Case 1 would be, since the Gaussian bound is the minimum of the parabola. It is the genuinely new, linear-in-\(t\) tail.
Combining the two cases, and using \(C_0=4\), \[ \mathbb P\{X-\mathbb EX\geq t\} \leq\exp\left(-\min\left\{\frac t{4R},\frac{t^2}{16V}\right\}\right) \leq\exp\left(-\frac1{16}\min\left\{\frac tR,\frac{t^2}V\right\}\right). \] The same argument applied to \(-X\) bounds the lower tail. A union bound over the two tails gives the claim with \(c=1/16\).
The two terms in the minimum trade off. For small \(t\) the Gaussian term \(t^2/V\) is the smaller one, and the tail is driven by the total variance-like quantity \(V\). Once \(t\) grows past the scale \(V/R\), the exponential term \(t/R\) takes over. From then on the tail is governed by the single heaviest summand, and averaging over the other terms cannot improve it.
4 Dimension reduction
Question. How large a dimension is needed to embed \(n\) points of a Euclidean space so that all pairwise distances are approximately preserved?
Let \(X\) be a \(K\times d\) matrix whose entries are i.i.d., mean-zero, of variance \(1\), and \(1\)-subgaussian. Standard Gaussian or Rademacher entries are examples. Fix a unit vector \(t\in\mathbb R^d\). The coordinates of \(Xt\) are \[ (Xt)_j=\sum_{\ell=1}^dX_{j\ell}\,t_\ell, \qquad 1\leq j\leq K, \] and they are i.i.d. across \(j\), since each uses its own row of \(X\). Each \((Xt)_j\) has mean zero and \[ \mathbb E(Xt)_j^2=\sum_{\ell=1}^dt_\ell^2=1 . \] Each summand \(X_{j\ell}t_\ell\) is \(t_\ell^2\)-subgaussian, so by the Pythagorean theorem of Lecture 5, \((Xt)_j\) is \(\big(\sum_\ell t_\ell^2\big)\)-subgaussian, that is, \(1\)-subgaussian. The sub-Gaussian–\(\psi_2\) comparison of Lecture 5 then gives \(\|(Xt)_j\|_{\psi_2}\leq2\), and directly from the definition of the Orlicz norms, \[ \big\|(Xt)_j^2\big\|_{\psi_1}=\big\|(Xt)_j\big\|_{\psi_2}^2\leq4 . \] So \(\|Xt\|_2^2\) is a sum of \(K\) independent, sub-exponential random variables, each of mean \(1\). This is exactly the setting of Bernstein’s inequality.
Proposition 1 (A random projection preserves one length) There is an absolute constant \(c>0\) such that, for every unit vector \(t\in\mathbb R^d\) and every \(\varepsilon\in(0,1]\), \[ \mathbb P\left\{\left|\frac1K\|Xt\|_2^2-1\right|>\varepsilon\right\} \leq2\exp\big(-cK\varepsilon^2\big). \]
Apply Corollary 1 to the sum \(\|Xt\|_2^2=\sum_{j=1}^K(Xt)_j^2\), whose mean is \(K\), at the level \(K\varepsilon\). Here \[ \max_j\big\|(Xt)_j^2\big\|_{\psi_1}\leq4, \qquad \sum_{j=1}^K\big\|(Xt)_j^2\big\|_{\psi_1}^2\leq16K , \] so the two terms in the minimum are at least \(K\varepsilon/4\) and \(K\varepsilon^2/16\). Since \(\varepsilon\leq1\), the minimum is at least \(K\varepsilon^2/16\).
A single random matrix \(\frac1{\sqrt K}X\) therefore preserves the length of a fixed vector with overwhelming probability once \(K\) is moderately large. Preserving every pairwise distance among \(n\) fixed points simultaneously is a union bound away.
Theorem 1 (Johnson–Lindenstrauss) Let \(x_1,\ldots,x_n\in\mathbb R^d\) with \(n\geq2\), and let \(\varepsilon\in(0,1)\). There is an integer \[ K\leq\frac{C\log n}{\varepsilon^2} \] and a linear map \(A:\mathbb R^d\to\mathbb R^K\) such that \[ (1-\varepsilon)\|x_i-x_j\|_2\leq\|Ax_i-Ax_j\|_2\leq(1+\varepsilon)\|x_i-x_j\|_2 \qquad\text{for all }1\leq i<j\leq n . \] Here \(C\) is an absolute constant.
Let \(A=\frac1{\sqrt K}X\) with \(X\) as above. For each pair \(i<j\) with \(x_i\neq x_j\), let \[ t_{ij}=\frac{x_i-x_j}{\|x_i-x_j\|_2}, \qquad\text{so that}\qquad \frac{\|Ax_i-Ax_j\|_2^2}{\|x_i-x_j\|_2^2}=\frac1K\|Xt_{ij}\|_2^2 . \] There are at most \(n^2/2\) such pairs. By Proposition 1 and a union bound, \[ \mathbb P\left\{\left|\frac1K\|Xt_{ij}\|_2^2-1\right|\leq\varepsilon\ \text{ for every pair }i<j\right\} \geq1-n^2\exp\big(-cK\varepsilon^2\big), \] which is positive as soon as \(K>2\log n/(c\varepsilon^2)\). Fix such a \(K\) and a matrix \(X\) in the event above. Then for every pair, \[ \sqrt{1-\varepsilon}\leq\frac{\|Ax_i-Ax_j\|_2}{\|x_i-x_j\|_2}\leq\sqrt{1+\varepsilon}, \] and \(\sqrt{1-\varepsilon}\geq1-\varepsilon\), \(\sqrt{1+\varepsilon}\leq1+\varepsilon\) give the claim. Pairs with \(x_i=x_j\) satisfy it trivially.
The embedding dimension depends only on the number of points, and only logarithmically. The ambient dimension \(d\) plays no role at all. The proof gives more than existence: a random matrix with the right scaling works with probability close to \(1\).
There are configurations of \(n\) points for which \(\log n\) dimensions are genuinely needed. Let \(x_j=e_j\) be the standard basis vectors of \(\mathbb R^n\), so that \[ \|e_i-e_j\|_2=\sqrt2\qquad\text{for all }i\neq j . \] Let \(\varepsilon\leq\frac14\) and let \(f\) be any map from \(\{e_1,\ldots,e_n\}\) into \(\mathbb R^k\) that preserves all pairwise distances up to a factor \(1\pm\varepsilon\). Translating, we may assume \(f(e_1)=0\). Then for every \(j\), \[ \|f(e_j)\|_2\leq(1+\varepsilon)\sqrt2\leq2 , \] so every \(f(e_j)\) lies in the ball \(2B_2^k\). On the other hand, for \(i\neq j\), \[ \|f(e_i)-f(e_j)\|_2\geq(1-\varepsilon)\sqrt2\geq1 . \] So \(\{f(e_j)\}_{j=1}^n\) is a \(1\)-separated subset of \(2B_2^k\). By the covering–packing comparison and the volume bound of Lecture 1, \[ n\leq M(2B_2^k,1)\leq N(2B_2^k,\tfrac12)=N(B_2^k,\tfrac14)\leq9^k , \] and therefore \(k\geq(\log n)/\log9\).
5 Where we go next
Bernstein’s inequality closes the calculus of sums we have been building since Lecture 4: Gaussian, sub-Gaussian, and now sub-exponential tails all fit into one Chernoff-method framework. The next lecture puts this machinery to work on a more structural question, coordinate embeddings, before we turn, over the following weeks, to the extreme singular values of random matrices.