§11.3: Borell’s Isoperimetric Theorem

If we believe that the Majority Is Stablest Theorem should be true, then we also have to believe in its “Gaussian special case”. Let’s see what this Gaussian special case is.

Suppose $f : {\mathbb R}^n \to [-1,1]$ is a “nice” function (smooth, say, with all derivatives bounded) having $\mathop{\bf E}[f] = 0$. You’re encouraged to think of $f$ as (a smooth approximation to) the indicator $\pm 1_A$ of some set $A \subseteq {\mathbb R}^n$ of Gaussian volume $\mathrm{vol}_\gamma(A) = \tfrac{1}{2}$. Now consider the Boolean function $g : \{-1,1\}^{nM} \to \{0,1\}$ defined by \[ g = f \circ \text{BitsToGaussians}_{M}^{n}. \] Using the multidimensional Central Limit Theorem, for any $\rho \in (0,1)$ we should have \[ \mathbf{Stab}_\rho[g] \xrightarrow{M \to \infty} \mathbf{Stab}_\rho[f], \] where on the left we have Boolean noise stability and on the right we have Gaussian noise stability. Using $\mathop{\bf E}[g] \to \mathop{\bf E}[f] = 0$, the Majority Is Stablest Theorem would tell us that \[ \mathbf{Stab}_\rho[g] \leq 1 – \tfrac{2}{\pi}\arccos \rho + o_\epsilon(1), \] where $\epsilon = \mathbf{MaxInf}[g]$. But $\epsilon = \epsilon(M) \to 0$ as $M \to \infty$. Thus we should simply have the Gaussian noise stability bound \begin{equation} \label{eqn:vol12-Borell} \mathbf{Stab}_\rho[f] \leq 1 – \tfrac{2}{\pi}\arccos \rho. \end{equation} (By a standard approximation argument this extends from “nice” $f : {\mathbb R}^n \to [-1,1]$ with $\mathop{\bf E}[f] = 0$ to any measurable $f : {\mathbb R}^n \to [-1,1]$ with $\mathop{\bf E}[f] = 0$.) Note that the upper bound \eqref{eqn:vol12-Borell} is achieved when $f$ is the $\pm 1$-indicator of any halfspace through the origin; see Corollary 20. (Note also that if $n = 1$ and $f = \mathrm{sgn}$, then the function $g$ is simply $\mathrm{Maj}_M$.)

The “isoperimetric inequality” \eqref{eqn:vol12-Borell} is indeed true, and is a special case of a theorem first proved by Borell [Bor85].

Borell’s Isoperimetric Theorem (volume-${\frac{\mathbf 1}{\mathbf 2}}$ case) Fix $\rho \in (0,1)$. Then for any $f \in L^2({\mathbb R}^n,\gamma)$ with range $[-1,1]$ and $\mathop{\bf E}[f] = 0$, \[ \mathbf{Stab}_{\rho}[f] \leq 1 – \tfrac{2}{\pi}\arccos \rho, \] with equality if $f$ is the $\pm 1$-indicator of any halfspace through the origin.

Remark 41 In Borell’s Isoperimetric Theorem, nothing is lost by restricting attention to functions with range $\{-1,1\}$, i.e., by considering only $f = \pm 1_A$ for $A \subseteq {\mathbb R}^n$. This is because the case of range $[-1,1]$ follows straightforwardly from the case of range $\{-1,1\}$, essentially because $\sqrt{\mathbf{Stab}_\rho[f]} = \|\mathrm{U}_{\sqrt{\rho}} f\|_2$ is a convex functional of $f$; see the exercises.

More generally, Borell showed that for any fixed volume $\alpha \in [0,1]$, the maximum Gaussian noise stability of a set of volume $\alpha$ is no greater than that of a halfspace of volume $\alpha$. We state here the more general theorem, using range $\{0,1\}$ rather than range $\{-1,1\}$ for future notational convenience (and with Remark 41 applying equally):

Borell’s Isoperimetric Theorem Fix $\rho \in (0,1)$. Then for any $f \in L^2({\mathbb R}^n, \gamma)$ with range $[0,1]$ and $\mathop{\bf E}[f] = \alpha$, \[ \mathbf{Stab}_{\rho}[f] \leq \Lambda_\rho(\alpha). \] Here $\Lambda_\rho(\alpha)$ is the Gaussian quadrant probability function, discussed in Exercise 5.33, and equal to $\mathbf{Stab}_\rho[1_H]$ for any (every) halfspace $H \subseteq {\mathbb R}^n$ having Gaussian volume $\mathrm{vol}_\gamma(H) = \alpha$.

We’ve seen that the volume-$\tfrac{1}{2}$ case of Borell’s Isoperimetric Theorem is a special case of the Majority Is Stablest Theorem, and similarly, the general version of Borell’s theorem is a special case of the General-Volume Majority Is Stablest Theorem mentioned at the beginning of the chapter. As a consequence, proving Borell’s Isoperimetric Theorem is a prerequisite for proving the General-Volume Majority Is Stablest Theorem. In fact, our proof in Section 7 of the latter will be a reduction to the former.

The proof of Borell’s Isoperimetric Theorem itself is not too hard; one of five known proofs, the one due to Mossel and Neeman [MN12], is outlined in the exercises. If our main goal is just to prove the basic Majority Is Stablest Theorem, then we only need the volume-$\tfrac{1}{2}$ case of Borell’s Isoperimetric Inequality. Luckily, there’s a very simple proof of this volume-$\tfrac{1}{2}$ case for “many” values of $\rho$, as we will now explain.

Let’s first slightly rephrase the statement of Borell’s Isoperimetric Theorem in the volume-$\tfrac{1}{2}$ case. By Remark 41 we can restrict attention to sets; then the theorem asserts that among sets of Gaussian volume $\tfrac{1}{2}$, halfspaces through the origin have maximal noise stability, for each positive value of $\rho$. Equivalently, halfspaces through the origin have minimal noise sensitivity under correlation $\cos \theta$, for $\theta \in (0,\frac{\pi}{2})$. The formula for this minimal noise sensitivity was given as inequality (2) in our proof of Sheppard’s Formula. Thus we have:

Equivalent statement of the volume-${\frac{\mathbf 1}{\mathbf 2}}$ Borell Isoperimetric Theorem Fix $\theta \in (0,\frac{\pi}{2})$. Then for any $A \subset {\mathbb R}^n$ with $\mathrm{vol}_\gamma(A) = \tfrac{1}{2}$, \[ \mathop{\bf Pr}_{\substack{(\boldsymbol{z}, \boldsymbol{z}') \\\text{$\cos \theta$-correlated}}}[1_A(\boldsymbol{z}) \neq 1_A(\boldsymbol{z}')] \geq \tfrac{\theta}{\pi}, \] with equality if $A$ is any halfspace through the origin.

In the remainder of this section we’ll show how to prove this formulation of the theorem whenever $\theta = \frac{\pi}{2\ell}$, where $\ell$ is a positive integer. This gives the volume-$\tfrac{1}{2}$ case of Borell’s Isoperimetric Inequality for all $\rho$ of the form $\arccos\frac{\pi}{2\ell}$, $\ell \in {\mathbb N}^+$; in particular, for an infinite sequence of $\rho$’s tending to $1$. To prove the theorem for these values of $\theta$, it’s convenient to introduce notation for the following noise sensitivity variant:

Definition 42 For $A \subseteq {\mathbb R}^n$ and $\delta \in {\mathbb R}$ (usually $\delta \in [0,\pi]$) we write $\mathbf{RS}_A(\delta)$ for the defined by \[ \mathbf{RS}_A(\delta) = \mathop{\bf Pr}_{\substack{(\boldsymbol{z}, \boldsymbol{z}') \\ \cos \delta\text{-correlated}}}[1_A(\boldsymbol{z}) \neq 1_A(\boldsymbol{z}')]. \]

The key property of this definition is the following:

Theorem 43 For any $A \subseteq {\mathbb R}^n$ the function $\mathbf{RS}_A(\delta)$ is subadditive; i.e., \[ \mathbf{RS}_A(\delta_1 + \cdots + \delta_\ell) \leq \mathbf{RS}_A(\delta_1) + \cdots + \mathbf{RS}_A(\delta_\ell). \] In particular, for any $\delta \in {\mathbb R}$ and $\ell \in {\mathbb N}^+$, \[ \mathbf{RS}_A(\delta) \leq \ell \cdot \mathbf{RS}_A(\delta/\ell). \]


Proof: Let $\boldsymbol{g}, \boldsymbol{g}’ \sim \mathrm{N}(0,1)^n$ be drawn independently and define $\boldsymbol{z}(\theta) = (\cos\theta)\boldsymbol{g} + (\sin\theta)\boldsymbol{g}’$. Geometrically, as $\theta$ goes from $0$ to $\frac{\pi}{2}$ the random vectors $\boldsymbol{z}(\theta)$ trace from $\boldsymbol{g}$ to $\boldsymbol{g}’$ along the origin-centered ellipse passing through these two points. The random vectors $\boldsymbol{z}(\theta)$ are jointly normal, with each individually distributed as $\mathrm{N}(0,1)^n$. Further, for each fixed $\theta, \theta’ \in {\mathbb R}$ the pair $(\boldsymbol{z}(\theta), \boldsymbol{z}(\theta’))$ constitute $\rho$-correlated Gaussians with \[ \rho = \cos\theta \cos\theta' + \sin\theta \sin\theta' = \cos(\theta' - \theta). \] Now consider the sequence $\theta_0, \dots, \theta_\ell$ defined by the partial sums of the $\delta_i$’s, i.e., $\theta_j = \sum_{i = 1}^j \delta_i$. We get that $\boldsymbol{z}(\theta_0)$ and $\boldsymbol{z}(\theta_\ell)$ are $\cos(\delta_1 + \cdots + \delta_\ell)$-correlated, and that $\boldsymbol{z}(\theta_{j-1})$ and $\boldsymbol{z}(\theta_{j})$ are $\cos\delta_j$-correlated for each $j \in [\ell]$. Thus \begin{align} \mathbf{RS}_A(\delta_1 + \cdots + \delta_\ell) &= \mathop{\bf Pr}[1_A(\boldsymbol{z}(\theta_0)) \neq 1_A(\boldsymbol{z}(\theta_\ell))] \nonumber\\ &\leq \sum_{j=1}^\ell \mathop{\bf Pr}[1_A(\boldsymbol{z}(\theta_{j})) \neq 1_A(\boldsymbol{z}(\theta_{j-1}))] = \sum_{j=1}^\ell \mathbf{RS}_A(\delta_j), \label{eqn:ellipse-union-bound} \end{align} where the inequality is the union bound. $\Box$

With this subadditivity result in hand, it’s indeed easy to prove the equivalent statement of the volume-$\tfrac{1}{2}$ Borell Isoperimetric Theorem for any $\theta \in \{\frac{\pi}{4}, \frac{\pi}{6}, \frac{\pi}{8}, \frac{\pi}{10}, \dots\}$. As we’ll see in Section 7, the case of $\theta = \frac{\pi}{4}$ can be used to give an excellent UG-hardness result for the Max-Cut CSP.

Corollary 44 The equivalent statement of the volume-$\tfrac{1}{2}$ Borell Isoperimetric Theorem holds whenever $\theta = \frac{\pi}{2\ell}$ for $\ell \in {\mathbb N}^+$.


Proof: The exact statement we need to show is $\mathbf{RS}_A(\frac{\pi}{2\ell}) \geq \frac{1}{2\ell}$. This follows by taking $\delta = \frac{\pi}{2}$ in Theorem 43 because \[ \mathbf{RS}_A(\tfrac{\pi}{2}) = \mathop{\bf Pr}_{\substack{(\boldsymbol{z}, \boldsymbol{z}') \\ 0\text{-correlated}}}[1_A(\boldsymbol{z}) \neq 1_A(\boldsymbol{z}')] = \tfrac12, \] using that $0$-correlated Gaussians are independent and that $\mathrm{vol}_\gamma(A) = \frac12$. $\Box$

Remark 45 Although Sheppard’s Formula already tells us that equality holds in this corollary when $A$ is a halfspace through the origin, it’s also not hard to derive this directly from the proof. The only inequality in the proof, \eqref{eqn:ellipse-union-bound}, is an equality when $A$ is a halfspace through the origin, because the elliptical arc can only cross such a halfspace $0$ or $1$ times.

Remark 46 Suppose that $A \subseteq {\mathbb R}^n$ not only has volume $\tfrac{1}{2}$, it has the property that $x \in A$ if and only if $-x \not \in A$; in other words, the $\pm 1$-indicator of $A$ is an odd function. (In both statements, we allow a set of measure $0$ to be ignored.) An example set with this property is any halfspace through the origin. Then $\mathbf{RS}_A(\pi) = 1$, and hence we can establish Corollary 44 more generally for any $\theta \in \{\frac{\pi}{1}, \frac{\pi}{2}, \frac{\pi}{3}, \frac{\pi}{4}, \frac{\pi}{5}, \dots\}$ by taking $\delta = \pi$ in the proof.

2 comments to §11.3: Borell’s Isoperimetric Theorem

  • Matt Franklin

    Maybe two small typos in last sentence before Borell’s Isoperimetric Thm (p. 340 in book):
    “range $\{ 0, 1 \}$ rather than range $\ -1, 1 \}$ maybe should be “range $[ 0, 1 ]$ rather than range [ -1, 1 ]$

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>