TCSLib

228 Boolean Analysis — Gaussian Bobkov

228.1 Overview

Normalized Boolean-block derivatives approximate the Euclidean coefficient length of a smooth derivative family. Passing to the Gaussian limit proves Bobkov bounds for probability-valued functions with bounded Lipschitz derivatives.

228.2 Declarations

Lemma 228.1 Length under coordinate perturbations
✓

For a finite set \(I\), a real scalar \(P\), and vectors \(d,g\in \mathbb R^I\), \(\sqrt{P^2+\sum _i d_i^2}\le \sqrt{P^2+\sum _i g_i^2}+\sqrt{\sum _i(d_i-g_i)^2}\).

Lemma 228.2 Length bound for a repeated gradient
✓

Let \(n\ge 0\), \(m\gt 0\), \(P\in \mathbb R\), \(d\in \mathbb R^{n\times m}\), \(g\in \mathbb R^n\), and \(e\ge 0\). If \(|d_{ij}-g_i/\sqrt m|\le e\) for every \(i,j\), then \(\sqrt{P^2+\sum _{i,j}d_{ij}^2}\le \sqrt{P^2+\sum _i g_i^2}+\sqrt{nm}\, e\).

Lemma 228.3 Bounded continuous Bobkov integrand
✓

Let \(\Phi ,\varphi \) be the standard Gaussian distribution function and density, and let \(\overline I(p)=\varphi (\Phi ^{-1}(p))\) for \(0\lt p\lt 1\), with \(\overline I(p)=0\) elsewhere. Let \(f:\mathbb R^n\to [0,1]\) be continuous, and let \(D(z)\) be a continuous family of real linear functionals on \(\mathbb R^n\) with \(\| D(z)\| \le M\) for all \(z\), for some real \(M\). Then \(z\mapsto \sqrt{\overline I(f(z))^2+\sum _i(D(z)e_i)^2}\) is a bounded continuous function.

Lemma 228.4 Vanishing accumulated block error
✓

For every \(n\ge 0\) and \(C\in \mathbb R\), \(\sqrt{n(m+1)}\, 2C/(m+1)\to 0\) as \(m\to \infty \).

Lemma 228.5 Bobkov bound on normalized Boolean blocks
✓

Let \(\Phi ,\varphi \) be the standard Gaussian distribution function and density, and let \(\overline I(p)=\varphi (\Phi ^{-1}(p))\) for \(0\lt p\lt 1\), with \(\overline I(p)=0\) elsewhere. Let \(f:\mathbb R^n\to [0,1]\) be differentiable with derivative family \(D(z)\), globally \(C\)-Lipschitz in operator norm for the maximum norm, where \(C\ge 0\). Write \(|D(z)|_2=\sqrt{\sum _{i=1}^n(D(z)e_i)^2}\). For independent uniform bits \(X_{ij}\), put \(S_r(X)_i=r^{-1/2}\sum _{j=1}^r(-1)^{X_{ij}}\). For every \(m\gt 0\), \(\overline I(\mathbb E f(S_m(X)))\le \mathbb E\sqrt{\overline I(f(S_m(X)))^2+|D(S_m(X))|_2^2}+\sqrt{nm}\, 2C/m\).

Lemma 228.6 Smooth Gaussian Bobkov inequality
✓

Let \(\Phi ,\varphi \) be the standard Gaussian distribution function and density, and let \(\overline I(p)=\varphi (\Phi ^{-1}(p))\) for \(0\lt p\lt 1\), with \(\overline I(p)=0\) elsewhere. Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). Let \(f:\mathbb R^n\to [0,1]\) be differentiable with derivative family \(D(z)\), globally \(C\)-Lipschitz in operator norm for the maximum norm, where \(C\ge 0\). Write \(|D(z)|_2=\sqrt{\sum _{i=1}^n(D(z)e_i)^2}\). If also \(\| D(z)\| \le M\) for every \(z\), for some \(M\in \mathbb R\), then \(\overline I(\int f\, d\gamma _n)\le \int \sqrt{\overline I(f(z))^2+|D(z)|_2^2}\, d\gamma _n(z)\).

Lemma 228.7 Integrability of bounded gradient length
✓

Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). Let \(D(z)\) be a continuous family of real linear functionals on \(\mathbb R^n\) and let \(M\in \mathbb R\) satisfy \(\| D(z)\| \le M\) for all \(z\). Then \(z\mapsto \sqrt{\sum _i(D(z)e_i)^2}\) is \(\gamma _n\)-integrable.

Lemma 228.8 Separated smooth Gaussian Bobkov bound
✓

Let \(\Phi ,\varphi \) be the standard Gaussian distribution function and density, and let \(\overline I(p)=\varphi (\Phi ^{-1}(p))\) for \(0\lt p\lt 1\), with \(\overline I(p)=0\) elsewhere. Let \(\gamma _n\) be standard Gaussian measure on \(\mathbb R^n\). Let \(f:\mathbb R^n\to [0,1]\) be differentiable with derivative family \(D(z)\), globally \(C\)-Lipschitz in operator norm for the maximum norm, where \(C\ge 0\). Write \(|D(z)|_2=\sqrt{\sum _{i=1}^n(D(z)e_i)^2}\). If also \(\| D(z)\| \le M\) for every \(z\), for some \(M\in \mathbb R\), then \(\overline I(\int f\, d\gamma _n)\le \int \overline I(f)\, d\gamma _n+\int |D(z)|_2\, d\gamma _n(z)\).