§9.5: Applications of hypercontractivity

With the $(2,q)$- and $(p,2)$-Hypercontractivity Theorems in hand, let’s revisit some applications we saw in Sections 1 and 2.

We begin by deducing a generalization of the Bonami Lemma:

Theorem 21 Let $f : \{-1,1\}^n \to {\mathbb R}$ have degree at most $k$. Then $\|f\|_q \leq \sqrt{q-1}^k \|f\|_2$ for any $q \geq 2$.

Proof: We have \[ \|f\|_q^2 = \|\mathrm{T}_{1/\sqrt{q-1}} \mathrm{T}_{\sqrt{q-1}} f\|_q^2 \leq \|\mathrm{T}_{\sqrt{q-1}} f\|_2^2 \] using the $(2,q)$-Hypercontractivity Theorem. (Here we are extending the definition of $\mathrm{T}_\rho$ to $\rho > 1$ via $\mathrm{T}_\rho f = \sum_j \rho^j f^{=j}$; see also Remark 8.29.) The result now follows since \[ \|\mathrm{T}_{\sqrt{q-1}} f\|_2^2 = \sum_{j = 0}^k (q-1)^j \mathbf{W}^{j}[f] \leq (q-1)^k \sum_{j=0}^k \mathbf{W}^{j}[f] = (q-1)^k \|f\|_2^2. \qquad \Box \]

Using a trick similar to the one in our proof of the $(4/3,2)$-Hypercontractivity Theorem you can use this to deduce $\|f\|_2 \leq (1/\sqrt{p-1})^k \|f\|_p$ when $f$ has degree $k$ for any $1 \leq p \leq 2$; see the exercises. However a different trick yields a strictly better result, including a finite bound for $p = 1$:

Theorem 22 Let $f : \{-1,1\}^n \to {\mathbb R}$ have degree at most $k$. Then $\|f\|_2 \leq e^{k} \|f\|_1$. More generally, for $1 \leq p \leq 2$ it holds that $\|f\|_2 \leq (e^{\frac{2}{p}-1})^k\|f\|_p$.

Proof: We prove the statement about the $1$-norm, leaving the case of general $1 \leq p \leq 2$ to the exercises. For $\epsilon > 0$, let $0 < \theta < 1$ be the solution of $\frac12 = \frac{\theta}{1} + \frac{1-\theta}{2+\epsilon}$ (namely, $\theta = \tfrac{1}{2}\frac{\epsilon}{1+\epsilon}$). Applying the general version of Hölder’s inequality and then Theorem 21, we get \[ \|f\|_2 \leq \|f\|_{2+\epsilon}^{1-\theta} \|f\|_1^{\theta} \leq \sqrt{1+\epsilon}^{k(1-\theta)}\|f\|_{2}^{1-\theta} \|f\|_1^\theta. \] Dividing by $\|f\|_2^{1-\theta}$ (which we may assume is nonzero) and then raising the result to the power of $1/\theta$ yields \[ \|f\|_2 \leq \left((1+\epsilon)^{\frac{1-\theta}{2\theta}}\right)^k \|f\|_1 = \left((1+\epsilon)^{\frac{1}{\epsilon} +\frac12}\right)^k \|f\|_1. \] The result follows by taking the limit as $\epsilon \to 0$. $\Box$

In the linear case of $k = 1$, Theorems 21 and 22 taken together show that $c_p \|\sum_i a_i \boldsymbol{x}_i\|_2 \leq \|\sum_i a_i \boldsymbol{x}_i\|_p \leq C_p \|\sum_i a_i \boldsymbol{x}_i\|_2$ for some constants $0 < c_p < C_p$ depending only on $p \in [1,\infty)$. This fact is known as Khintchine's Inequality.

Theorem 21 can be used to get a strong concentration bound for degree-$k$ boolean functions. Chernoff tells us that the probability a linear form $\sum a_i {\boldsymbol{x}}_i$ exceeds $t$ standard deviations decays like $\exp(-\Theta(t^2))$. The following theorem generalizes this to degree-$k$ forms, with decay $\exp(-\Theta(t^{2/k}))$:

Theorem 23 Let $f : \{-1,1\}^n \to {\mathbb R}$ have degree at most $k$. Then for any $t \geq \sqrt{2e}^{k}$ we have \[ \mathop{\bf Pr}_{{\boldsymbol{x}} \sim \{-1,1\}^n}[|f({\boldsymbol{x}})| \geq t \|f\|_2] \leq \exp\left(-\tfrac{k}{2e} t^{2/k}\right). \]

Proof: We may assume $\|f\|_2 = 1$ without loss of generality. Let $q \geq 2$ be a parameter to be chosen later. By Markov’s Inequality, \[ \mathop{\bf Pr}[|f({\boldsymbol{x}})| \geq t] = \mathop{\bf Pr}[|f({\boldsymbol{x}})|^q \geq t^q] \leq \frac{\mathop{\bf E}[|f({\boldsymbol{x}})|^q]}{t^q}. \] By Theorem 21 we have \[ \mathop{\bf E}[|f({\boldsymbol{x}})|^q] \leq (\sqrt{q-1}^k)^q \|f\|_2^q = (q-1)^{(k/2)q} \leq q^{(k/2)q}. \] Thus $\mathop{\bf Pr}[|f({\boldsymbol{x}})| \geq t] \leq (q^{k/2}/t)^q$. It’s not hard to see that the $q$ which minimizes this expression should be just slightly less than $t^{2/k}$. Specifically, by choosing $q = t^{2/k}/e \geq 2$ we get \[ \mathop{\bf Pr}[|f({\boldsymbol{x}})| \geq t] \leq \exp(-(k/2)q) = \exp\left(-\tfrac{k}{2e} t^{2/k}\right) \] as claimed. $\Box$

We can use Theorem 22 to get a “one-sided” analogue of Theorem 7, showing that a low-degree function exceeds its mean with noticeable probability:

Theorem 24 Let $f : \{-1,1\}^n \to {\mathbb R}$ be a nonconstant function of degree at most $k$. Then \[ \mathop{\bf Pr}_{{\boldsymbol{x}} \sim \{-1,1\}^n}\bigl[f({\boldsymbol{x}}) > \mathop{\bf E}[f]\bigr] \geq \tfrac14 e^{-2k}. \]

Proof: We may assume $\mathop{\bf E}[f] = 0$ without loss of generality. We then have \[ \tfrac{1}{2} \|f\|_1 = \tfrac{1}{2} \left(\mathop{\bf E}[f \cdot \boldsymbol{1}_{\{f({\boldsymbol{x}}) > 0\}}] – \mathop{\bf E}[f \cdot (1-\boldsymbol{1}_{\{f({\boldsymbol{x}}) >0\}})]\right) = \mathop{\bf E}[f \cdot \boldsymbol{1}_{\{f({\boldsymbol{x}}) > 0\}}]; \] hence, \[ \tfrac14 \|f\|_1^2 = \mathop{\bf E}[f \cdot \boldsymbol{1}_{\{f({\boldsymbol{x}}) > 0\}}]^2 \leq \mathop{\bf E}[f^2]\cdot \mathop{\bf E}[\boldsymbol{1}_{\{f({\boldsymbol{x}}) > 0\}}^2] \leq e^{2k}\|f\|_1^2 \cdot \mathop{\bf Pr}[f({\boldsymbol{x}}) > 0] \] using Cauchy–Schwarz and Theorem 22. The result follows. $\Box$

Next we turn to noise stability. Using the $(p,2)$-Hypercontractivity Theorem we can immediately deduce the following generalization of Corollary 8:

Small-Set Expansion Theorem Let $A \subseteq \{-1,1\}^n$ have volume $\alpha$; i.e., let $1_A : \{-1,1\}^n \to \{0,1\}$ satisfy $\mathop{\bf E}[1_A] = \alpha$. Then for any $0 \leq \rho \leq 1$, \[ \mathbf{Stab}_{\rho}[1_A] = \mathop{\bf Pr}_{\substack{{\boldsymbol{x}} \sim \{-1,1\}^n \\ \boldsymbol{y} \sim N_{\rho}({\boldsymbol{x}})}}[{\boldsymbol{x}} \in A, \boldsymbol{y} \in A] \leq \alpha^{\frac{2}{1+\rho}}. \] Equivalently (for $\alpha > 0$), \[ \mathop{\bf Pr}_{\substack{{\boldsymbol{x}} \sim A \\ \boldsymbol{y} \sim N_{\rho}({\boldsymbol{x}})}}[\boldsymbol{y} \in A] \leq \alpha^{\frac{1-\rho}{1+\rho}}. \]

In other words, the $\delta$-noisy hypercube is a small-set expander for any $\delta > 0$: the probability that one step from a random ${\boldsymbol{x}} \sim A$ stays inside $A$ is at most $\alpha^{\delta/(1-\delta)}$. It’s also possible to derive a “two-set” generalization of this fact using the Two-Function Hypercontractivity Theorem; we defer the discussion to Chapter 10 since the most general result requires the non-weak form of the theorem. We can also obtain the generalization of Corollary 12:

Corollary 25 Let $f : \{-1,1\}^n \to \{-1,1\}$. Then for any $0 \leq \rho \leq 1$ we have $\mathbf{Inf}_i^{(\rho)}[f] \leq \mathbf{Inf}_i[f]^{\frac{2}{1+\rho}}$ for all $i$.

Finally, from the Small-Set Expansion Theorem we see that indicators of small-volume sets are not very noise-stable and hence can’t have much of their Fourier weight at low levels. Indeed, using hypercontractivity we can deduce the Level-1 Inequality from Chapter 5.4 and also generalize it to higher degrees.

Level-$k$ Inequalities Let $f : \{-1,1\}^n \to \{0,1\}$ have mean $\mathop{\bf E}[f] = \alpha$ and let $k \in {\mathbb N}^+$ be at most $2\ln(1/\alpha)$. Then \[ \mathbf{W}^{\leq k}[f] \leq \left(\tfrac{2e}{k}\ln(1/\alpha)\right)^k \alpha^2. \] In particular, defining $k_\epsilon = 2(1-\epsilon)\ln(1/\alpha)$ (for any $0 \leq \epsilon \leq 1$) we have \[ \mathbf{W}^{\leq k_\epsilon}[f] \leq \alpha^{\epsilon^2}. \]

Proof: By the Small-Set Expansion Theorem, \[ \mathbf{W}^{\leq k}[f] \leq \rho^{-k} \mathbf{Stab}_{\rho}[f] \leq \rho^{-k} \alpha^{2/(1+\rho)} \leq \rho^{-k} \alpha^{2(1-\rho)} \] for any $0 < \rho \leq 1$. Basic calculus shows the right-hand side is minimized when $\rho = \frac{k}{2\ln(1/\alpha)} \leq 1$; substituting this into $\rho^{-k} \alpha^{2(1-\rho)}$ yields the first claim. The second claim follows after substituting $k = k_\epsilon$; see the exercises. $\Box$

For the case $k = 1$, a slightly different argument gives the sharp Level-1 Inequality $\mathbf{W}^{1}[f] \leq 2 \alpha^2 \ln(1/\alpha)$; see the exercises.

6 comments to §9.5: Applications of hypercontractivity

Leave a Reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>