TransWikia.com

Gaussian concentration of measure, equivalent definitions

Mathematics Asked by Monty on January 12, 2021

I need some help going between two equivalent definitions.

First some notation :

$bullet$ For $Asubseteq mathcal{X}$ and $r>0$ define what is called the r-blowup of $A$ as begin{equation}
A_r = { x in mathcal{X} : d(x,A)<r }.
end{equation}

$bullet$ We have a metric probability space $(mathcal{X},d,mu)$, i.e $(mathcal{X},d)$ is a Polish space, and $mu$ a probability measure on its Borel sets.

Now I am going to give two definitions for $mu$ satisfying a Gaussian concentration of measure. Can anyone show how to go from one definition to the other (of course with a change of constants).


$textbf{Def.1}$
$mu$ is said to have Guassian concentration on $(mathcal{X},d)$ if there exists $K,kappa >0 $ such that

begin{equation}label{Gauss concentration}
textit{whenever}~~mu(A)geq frac{1}{2} ~~ textit{it implies} ~~ mu(A_r)geq 1-K e^{-kappa r^2}
end{equation}

$textbf{Def.2}$
We say $mu$ has Gaussian concentration of measure if there exists $K,kappa >0$ and some $r_0>0$, such that
begin{equation}
textit{whenever}~~mu(A)geq frac{1}{2} ~~ textit{it implies} ~~ mu(A_r) geq 1-Ke^{-kappa(r-r_0)^2} ~~ forall rgeq r_0
end{equation}


[1, Page 103] claims that we can go between the two with a change of constants, how? Note going from $textbf{Def.1}$ to
$textbf{Def.2}$ is fine just replace $r$ by $r-r_0$.

[1] Raginsky, Sason. Concentration of Measure Inequalities in Information Theory, Communications and Coding. 2014

One Answer

As you mentioned, it is easy to go from Definition $1$ to Definition $2$.

Let $K$, $kappa$, and $r_0$ be the constants in Definition 2. We will now find constants $K'$ and $kappa'$ for Definition $1$. Set $K' := max(K,1)e^{4 kappa' r_0^2}$ and $kappa':= kappa/4$ to be the constants in Definition 1. We will show that these constants suffice by considering two cases:

Case 1: $r in [0,2r_0]$. We have that $$ K' exp(- kappa'r^2) = max(K,1)exp(kappa'(4r^2_0 - r^2)) geq 1, $$ and thus the desired inequality $mu(A_r)geq 1 - K' exp(- r^2)$ holds trivially.

Case 2: $r geq 2r_0$. We have the following series of inequalities: $$ begin{aligned}1 - mu(A_r) &leq K e^{- kappa (r - r_0)^2} \ &leq K e^{- kappa r^2/4}\ &leq K'e^{- kappa r^2/4} = K'e^{- kappa' r^2}, end{aligned} $$ where we used that $K leq K'$ and $|r - r_0| geq r/2 $ for $r geq 2r_0$.

Correct answer by Ankitp on January 12, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP