CSE 599: Analytic and geometric methods in TCS

• A random process is a collection \(\{X_t : t \in T\}\) of random variables. For the next few lectures, we will considered symmetric processes, i.e., those where \(X_t\) and \(-X_t\) have the same law for every \(t \in T\).

• We equip the index set \(T\) of such a process with the natural \(\ell_2\) metric

  \[d(s,t) \seteq \sqrt{\E(X_s-X_t)^2}.\]

• A fundamental example is that of a Gaussian process, where the family \(\{X_t : t \in T\}\) is a jointly normal family of random variables. When \(T\) is finite, any such family can be described as follows: \(T \subseteq \R^n\) for some \(n \geq 1\), and \(X_t = \langle g,t\rangle\), where \(g=(g_1,\ldots,g_n)\) is a standard \(n\)-dimensional gaussian, i.e., the coordinates \(g_1,\ldots,g_n\) are i.i.d. \(N(0,1)\) random variables.

  In this case the geometry of the metric space \((T,d)\) is Eucliean, since \(d(s,t) = \|s-t\|_2\).

  Also note that the metric \(d(s,t)\) completely describes the covariance structure of the process, and therefore characterizes it (this is a special property of jointly normal families of random variables).

• We will be concerned with extrema of such a process, and to that end we study the quantity

  \[\E \max_{t \in T} X_t\,.\]

• A random process \(\{ X_t : t \in T \}\) is called sub-gaussian if there is some constant \(c > 0\) such that

  \[\begin{equation}\label{eq:sg-tail} \Pr[X_s - X_t > \lambda] \leq \exp\left(- c\lambda^2/d(s,t)^2\right) \end{equation}\]

  In particular, Gaussian processes are sub-gaussian with \(c=1/2\).

  Another example is a Bernoulli process, i.e. a family of random variables defined thusly: For some subset \(T \subseteq \R^n\),

  \[\left\{ \e_1 t_1 + \e_2 t_2 + \cdots + \e_n t_n : t = (t_1,\ldots,t_n) \in T \right\},\]

  where \(\e_1,\ldots,\e_n \in \{-1,1\}\) are i.i.d. uniformly random signs.

• Diameter bound: When the index set \(T\) is finite, we can use the tail bound \eqref{eq:sg-tail} to give a simple upper bound on \(\E \max_{t \in T} X_t\).

  Fix some \(t_0 \in T\) and note that \(\E \max_{t \in T} X_t = \E \max_{t \in T} (X_t-X_{t_0})\). Now applying a union bound gives

  \[\P\left[\max_{t \in T} (X_t-X_{t_0}) > \lambda\right] \leq |T| \exp\left(- c\lambda^2/\Delta^2\right)\,,\]

  where \(\Delta \seteq \max \{ d(t,t_0) : t \in T \}\).

  A simple calculation gives the conclusion

  \[\E \max_{t \in T} X_t \lesssim \Delta \sqrt{\log |T|}\,.\]

Recall that we consider a subgaussian process \(\{X_t : t \in T\}\) and equip \(T\) with the distance \(d(s,t) = \sqrt{\E(X_s-X_t)^2}\).

• Chaining: Instead of applying a naive union bound to control \(X_t - X_{t_0}\) for every \(t \in T\), we can break every such difference into parts and then bound each part. This potentially reduces the number of events we need to take a union bound over.

  For instance, given three random variables \(X_0,X_1,X_2,X_3\), we could write

  \[\begin{eqnarray*} X_3 - X_0 &=& (X_3 - X_1) + (X_1 - X_0) \\ X_2 - X_0 &=& (X_2 - X_1) + (X_1 - X_0) \\ X_1 - X_0 &=& X_1 - X_0\,. \end{eqnarray*}\]

• Generic chaining upper bound: For sub-gaussian processes, we can control \(\E \max_{t \in T} X_t\) using chaining.

  Fix some \(t_0 \in T\) and a sequence of finite sets

  \[\{t_0\} = T_0 \subseteq T_1 \subseteq T_2 \subseteq \cdots \subseteq T_n \subseteq \cdots \subseteq T\,,\]

  with cardinalities bounded by \(\abs{T_n} \leq 2^{2^n}\) for every \(n \geq 1\).

  Then we have:

  \[\begin{equation}\label{eq:gc-ub} \E \max_{t \in T} X_t \lesssim \max_{t \in T} \sum_{n \geq 0} 2^{n/2} d(t,T_n)\,, \end{equation}\]

  where \(d(t,T_n) = \min_{s \in T_n} d(s,t)\).

• Dudley’s entropy bound: If \(\{X_t : t \in T\}\) is a subgaussian process, then

  \[\begin{equation}\label{eq:dudley} \E \max_{t \in T} X_t \lesssim \sum_{n \geq 1} 2^{n/2} e_n(T)\,, \end{equation}\]

  where \(e_n(T)\) is the largest distance \(d\) such that there are \(2^{2^n}\) points \(y_1,y_2,\ldots,y_{2^{2^n}}\) in \(T\) with \(d(y_i,y_j) \geq d\) for all \(i \neq j\).

  Easy exercise: Show that Dudley’s entropy bound follows from the generic chaining upper bound \eqref{eq:gc-ub}.

• Covering numbers: Let \(N(T,d,\e)\) denote the smallest number \(N\) such that the metric space \((T,d)\) can be covered by \(N\) balls of radius \(\e\), and consider the quantity

  \[C_T \seteq \sum_{h=-\infty}^{\infty} 2^h \sqrt{\log N(T,d,2^{h})}\,.\]

  Up to a factor of \(2\), this is equivalent to the more elegant expression \(\int_0^{\infty} \sqrt{\log N(T,d,\e)} \,d\e\). It is an exercise to show that

  \[C_T \asymp \sum_{n \geq 1} 2^{n/2} e_n(T)\,.\]

  Exercise: Show that for any metric space \((T,d)\), it holds that

  \[\begin{equation}\label{eq:CT} \sum_{n \geq 1} 2^{n/2} e_n(T) \asymp \sum_{h=-\infty}^{\infty} 2^h \sqrt{\log N(T,d,2^h)}\,. \end{equation}\]

• Analysis of the probability simplex

  Let \(T = \{ x \in \R^n : x_1,\ldots,x_n \geq 0, x_1+\cdots+x_n = 1 \}\) denote the probability simplex.

  Lemma 1: For this \(T\), let \(X_t = \langle g,t\rangle\), where \(g=(g_1,\ldots,g_n)\) is a standard \(n\)-dimensional Gaussian. Then \(\E \max_{t \in T} X_t \asymp \sqrt{\log n}\).

  This is because the maximum of the linear functional \(t \mapsto \langle g,t\rangle\) is achieved at a vertex of the convex body \(T\) which is equal to the convex hull of the standard basis vectors: \(T = \mathrm{conv}(e_1,\ldots,e_n)\). Thus \(\max_{t \in T} \langle g,t\rangle = \max \{ g_i : i =1,\ldots,n\}\), and therefore

  \[\E \max_{t \in T} \langle g,t\rangle = \E \max(g_1,\ldots,g_n) \asymp \sqrt{\log n}.\]

  Let us now see that the entropy bound \eqref{eq:dudley} is far from tight in this simple case. We will use the formulation via covering numbers coming from the equivalence \eqref{eq:CT}.

  Consider vectors \(t \in T\) with \(t_i \in \{0,1/k\}\) for $i=1,\ldots,n$. There are \({n \choose k} \geq \left(\frac{n}{k}\right)^k\) such vectors. For \(k \leq \sqrt{n}\), we have \((n/k)^k \gtrsim 2^{k \log n}\), and it is possible to choose a proportional subset of those vectors (e.g., a random subset will suffice) such that

  \[d(t_i,t_j) \gtrsim \left(k \cdot \frac{1}{k^2} \right)^{1/2} \asymp k^{-1/2}, \qquad i \neq j\,.\]

  It follows that for \(k \leq \sqrt{n}\), we have $\log N(T,d,k^{-1/2}) \gtrsim k \log n$. Consider then the \(\approx \log n\) values of \(h\) for which \(1 \leq 2^h \leq \sqrt{n}\).

  This gives us \(\approx \log n\) values of \(h\) for which

  \[2^{-h} \sqrt{\log N(T,d,2^{-h})} \gtrsim 2^{-h} \cdot 2^h \sqrt{\log n} = \sqrt{\log n}\,.\]

  Therefore Dudley’s bound \eqref{eq:CT} is \(\gtrsim (\log n) \cdot \sqrt{\log n} = (\log n)^{3/2}\). (Recall that the correct bound, given by Lemma 1, is \(\sqrt{\log n}\).)

• We have seen that if \(\{X_t : t \in T \}\) is a symmetric sub-Gaussian process equipped with the distance \(d(s,t) = \sqrt{\E(X_s-X_t)^2}\), then for any sequence \(\{t_0\} = T_0 \subseteq T_1 \subseteq \cdots \subseteq T_h \subseteq \cdots T\) with \(|T_h| \leq 2^{2^h}\), we have a chaining upper bound

  \[\E \max_{t \in T} X_t \lesssim \max_{t \in T} \sum_{h \geq 0} 2^{n/2} d(t,T_h)\,.\]

  Let us define \(\gamma_2(T,d)\) as the best possible chaining upper bound, i.e., the infimum of the RHS over all compliant sequences \(\{T_h\}\). This is Talagrand’s famous \(\gamma_2\) functional, and it may be surprising that it characterizes (up to constants) the expected supremum of a Gaussian process.

  Majorizing-measures theorem (Fernique-Talagrand): If \(\{X_t : t\in T \}\) is a centered Gaussian process, then

  \[\E \max_{t \in T} X_t \asymp \gamma_2(T,d)\,.\]

• Random signed sums: Suppose that \(\e_1,\e_2,\ldots,\e_n\) is a sequence of independent, symmetric random variables and we define the random process:

  \[\left\{ X_t = \e_1 t_1 + \e_2 t_2 + \cdots + \e_n t_n : t \in T \right\}\,,\]

  where \(T \subseteq \R^n\). Then classical concentration bounds show that \(\{X_t : t\in T\}\) is subgaussian, and it is straightforward to calculate the distance (by expanding the square):

  \[d(s,t) = \|s-t\|_2\,.\]

  The chaining upper bound gives \(\E \max_{t \in T} X_t \lesssim \gamma_2(T,d)\). Let us now use this to understand the Hypergraph sparsification problem.

• Hypergraph sparsification. Consider a weighted hypergraph \(H=(V,E,w)\) where \(\{w_e : e \in E\}\) are nonnegative edge weights. We associated to \(H\) the quadratic expression

  \[Q_H(x) = \sum_{e \in E} w_e \max_{u,v \in e} (x_u-x_v)^2\,.\]

  If \(H\) were a graph (where \(|e|=2\) for every \(e \in E\)), this would correspond to the quadratic form of the graph Laplacian.

  Our goal is to find another hypergraph \(\tilde{H} = (V,\tilde{E},\tilde{w})\) with \(\tilde{E} \subseteq E\) and such that

  \[\begin{equation}\label{eq:sparse-approx} |Q_H(x)-Q_{\tilde{H}}(x)| \leq \e Q_H(x),\qquad \forall x \in \R^n\,, \end{equation}\]

  where \(\e > 0\) is some accuracy parameter. Moreover, we would like \(\abs{\tilde{E}}\) to be small, ideally near-linear in \(\abs{V}\) (while \(\abs{E}\) could be as large as \(2^{\abs{V}}\)).

• Independent random sampling. Suppose we have a probability distribution \(\{\mu_e : e \in E\}\). Let us form \(\tilde{H}\) by sampling \(M\) edges \(e_1,e_2,\ldots,e_M\) independently from \(\mu\) and setting the edge weights in \(\tilde{H}\) so that

  \[Q_{\tilde{H}}(x) = \frac{1}{M} \sum_{k=1}^M \frac{w_{e_k}}{\mu_{e_k}} Q_{e_k}(x)\,,\]

  where we define \(Q_e(x) = \max_{u,v \in e} (x_u-x_v)^2\).

  Note that \(\E[Q_{\tilde{H}}(x)] = Q_H(x)\) for all \(x \in \R^n\), and to establish a bound like \eqref{eq:sparse-approx}, it makes sense to study the quantity

  \[\E \max_{Q_H(x) \leq 1} |Q_H(x) - Q_{\tilde{H}}(x)|.\]

• Passing to a sub-Gaussian process. Let \(\hat{H}\) be an independent copy of \(\tilde{H}\) and write

  \[\begin{eqnarray*} \E_{\tilde{H}} \max_{Q_H(x) \leq 1} |Q_H(x) - Q_{\tilde{H}}(x)| &= \E_{\tilde{H}} \max_{Q_H(x) \leq 1} |\E_{\hat{H}}[Q_{\hat{H}}(x)]-Q_{\tilde{H}}(x)| \\ &= \E_{\tilde{H}} \max_{Q_H(x) \leq 1} |\E_{\hat{H}} [Q_{\hat{H}}(x)-Q_{\tilde{H}}(x)]| \\ &\leq \E_{\hat{H},\tilde{H}} \max_{Q_H(x) \leq 1} |Q_{\hat{H}}(x)-Q_{\tilde{H}}(x)|\,, \end{eqnarray*}\]

  where we have used convexity to pull out the expectation: \(\abs{\E X} \leq E \abs{X}\) and \(\max(\E X_1,\ldots,\E X_k) \leq \E \max(X_1,\ldots,X_k)\)

  Note that for any choice of signs \(\e_1,\ldots,\e_M \in \{-1,1\}\), we have

  \[\begin{eqnarray*} |Q_{\hat{H}}(x)-Q_{\hat{H}}(x)| &= \frac{1}{M} \left|\sum_{k=1}^M \left(\frac{w_{\hat{e}_k}}{\mu_{\hat{e}_k}} Q_{\hat{e}_k}(x)- \frac{w_{\tilde{e}_k}}{\mu_{\tilde{e}_k}} Q_{\hat{e}_k}(x)\right)\right| \\ &= \frac{1}{M} \left|\sum_{k=1}^M \e_k \left(\frac{w_{\hat{e}_k}}{\mu_{\hat{e}_k}} Q_{\hat{e}_k}(x)- \frac{w_{\tilde{e}_k}}{\mu_{\tilde{e}_k}} Q_{\hat{e}_k}(x)\right)\right|. \end{eqnarray*}\]

  because \(\tilde{e}_k\) and \(\hat{e}_k\) have the same law. Define \(t_k(x) \seteq \frac{w_{e_k}}{\mu_{e_k}} Q_{\hat{e}_k}(x)\) and then we have

  \[\max_{Q_H(x) \leq 1} |Q_{\hat{H}}(x)-Q_{\tilde{H}}(x)| \leq \frac{2}{M} \E_{(\e_1,\ldots,\e_M)} \max_{Q_H(x) \leq 1} \left|\sum_{k=1}^M \e_k t_k\right| = \frac{4}{M} \E_{(\e_1,\ldots,\e_M)} \max_{Q_H(x) \leq 1} \sum_{k=1}^M \e_k t_k(x)\,,\]

  where we take the expectation over i.i.d. uniformly random signs, and we removed the absolute values using symmetry of the process.

  So now to bound the quantity we cared about initially, it suffices to bound \(\max_{Q_H(x) \leq 1} \sum_{k=1}^M \e_k t_k(x)\) for every choice of hyperedges \(e_1,\ldots,e_M\). Of course, this is a sub-Gaussian process, and so we are led to the study of \(\gamma_2(T,d)\), where \(T = \{ x \in \R^n : Q_H(x) \leq 1\}\), and

  \[d(x,y) = \left(\sum_{k=1}^M \left(\frac{w_{e_k}}{\mu_{e_k}} (Q_{e_k}(x)-Q_{e_k}(y))\right)^2\right)^{1/2}\]

• Abstracting out the norm sparsification problem. Note that each \(\sqrt{Q_e(x)}\) for \(e \in E\) is actually a norm on \(\R^n\) (technically it is only a seminorm since \(Q_e(x)=0\) does not entail \(x=0\)).

  Thus we can consider the following related problem: Suppose that \(N_1,N_2,\ldots,N_m\) are (semi)norms on \(\R^n\) and we want to bound

  \[\E \max_{x \in T} \sum_{k=1}^m \e_k N_k(x)^2\,,\]

  where \(T \subseteq \R^n\) and \(\e_1,\ldots,\e_m\) are i.i.d. random signs. Again, this is a sub-Gaussian process equipped with the distance

  \[d(x,y) = \left(\sum_{k=1}^M (N_k(x)^2 - N_k(y)^2)^2\right)^{1/2}.\]

  In the next lecture, we will find upper bounds on \(\gamma_2(T,d)\) for this faimly of problems.