Skip to main content
MathOverflow

Return to Answer

added 1113 characters in body
Source Link
Iosif Pinelis
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

Unconditional? Certainly not. E.g., suppose that $\mu$ is the standard Gaussian measure on $\mathbb R^d$ and $B$ is the ball of radius $r>0$ centered at $0$. Then for any $\delta\in(0,1)$, by the law of large numbers, $$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{(r+\epsilon)^2}d\Big)\to1$$ for $d\to\infty$ and $\epsilon\in(0,(1-\delta)\sqrt d-r\,]$, where $Z_1,Z_2,\dots$ are iid $N(0,1)$. So, asymptotically there is no decrease at all in $\epsilon\le(1-\delta)\sqrt d-r$. So, any bound of the form $1-\mu(B^\epsilon)\le\epsilon\,\text{poly}(\epsilon)$ will not hold in this example.

Added in response to the comment "What about for $\epsilon\le2\log(1/\mu(B))$?" by the OP: $\quad$ As above, let $\mu$ be the standard Gaussian measure on $\mathbb R^d$. As usual, let $\Phi$ denote the cdf of $N(0,1)$. Fix any real $a$ and let $B:=(-\infty,a)\times\mathbb R^{d-1}$. Then $\mu(B)=\Phi(a)$, $\epsilon_0:=2\log(1/\mu(B))=2\ln(1/\Phi(a))$, and $$g(\epsilon):=1-\mu(B^\epsilon)=1-\Phi(a+\epsilon)$$ decreases from the constant $g(0)=1-\Phi(a)$ to the constant $g(\epsilon_0)=1-\Phi(a+\epsilon_0)=1-\Phi(a+2\ln(1/\Phi(a)))>0$ as $\epsilon$ increases from $0$ to $\epsilon_0=2\ln(1/\Phi(a))$. So, $1-\mu(B^\epsilon)$ does not decrease polynomially in $\epsilon$ as $\epsilon$ increases from $0$ to $\epsilon_0=2\log(1/\mu(B))$.

In particular, taking here $a=0$, we see that $1-\Phi(a+\epsilon)$ decreases from $1-\Phi(0)=0.5$ only to $1-\Phi(2\ln2)\approx0.08$ as $\epsilon$ increases from $0$ to $2\log(1/\mu(B))$. Now taking $a=3$, we see that $1-\Phi(a+\epsilon)$ decreases from $\approx0.001350$ only to $\approx0.001338$ as $\epsilon$ increases from $0$ to $2\log(1/\mu(B))$ -- almost no decrease.

Unconditional? Certainly not. E.g., suppose that $\mu$ is the standard Gaussian measure on $\mathbb R^d$ and $B$ is the ball of radius $r>0$ centered at $0$. Then for any $\delta\in(0,1)$, by the law of large numbers, $$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{(r+\epsilon)^2}d\Big)\to1$$ for $d\to\infty$ and $\epsilon\in(0,(1-\delta)\sqrt d-r\,]$, where $Z_1,Z_2,\dots$ are iid $N(0,1)$. So, asymptotically there is no decrease at all in $\epsilon\le(1-\delta)\sqrt d-r$. So, any bound of the form $1-\mu(B^\epsilon)\le\epsilon\,\text{poly}(\epsilon)$ will not hold in this example.

Unconditional? Certainly not. E.g., suppose that $\mu$ is the standard Gaussian measure on $\mathbb R^d$ and $B$ is the ball of radius $r>0$ centered at $0$. Then for any $\delta\in(0,1)$, by the law of large numbers, $$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{(r+\epsilon)^2}d\Big)\to1$$ for $d\to\infty$ and $\epsilon\in(0,(1-\delta)\sqrt d-r\,]$, where $Z_1,Z_2,\dots$ are iid $N(0,1)$. So, asymptotically there is no decrease at all in $\epsilon\le(1-\delta)\sqrt d-r$. So, any bound of the form $1-\mu(B^\epsilon)\le\epsilon\,\text{poly}(\epsilon)$ will not hold in this example.

Added in response to the comment "What about for $\epsilon\le2\log(1/\mu(B))$?" by the OP: $\quad$ As above, let $\mu$ be the standard Gaussian measure on $\mathbb R^d$. As usual, let $\Phi$ denote the cdf of $N(0,1)$. Fix any real $a$ and let $B:=(-\infty,a)\times\mathbb R^{d-1}$. Then $\mu(B)=\Phi(a)$, $\epsilon_0:=2\log(1/\mu(B))=2\ln(1/\Phi(a))$, and $$g(\epsilon):=1-\mu(B^\epsilon)=1-\Phi(a+\epsilon)$$ decreases from the constant $g(0)=1-\Phi(a)$ to the constant $g(\epsilon_0)=1-\Phi(a+\epsilon_0)=1-\Phi(a+2\ln(1/\Phi(a)))>0$ as $\epsilon$ increases from $0$ to $\epsilon_0=2\ln(1/\Phi(a))$. So, $1-\mu(B^\epsilon)$ does not decrease polynomially in $\epsilon$ as $\epsilon$ increases from $0$ to $\epsilon_0=2\log(1/\mu(B))$.

In particular, taking here $a=0$, we see that $1-\Phi(a+\epsilon)$ decreases from $1-\Phi(0)=0.5$ only to $1-\Phi(2\ln2)\approx0.08$ as $\epsilon$ increases from $0$ to $2\log(1/\mu(B))$. Now taking $a=3$, we see that $1-\Phi(a+\epsilon)$ decreases from $\approx0.001350$ only to $\approx0.001338$ as $\epsilon$ increases from $0$ to $2\log(1/\mu(B))$ -- almost no decrease.

added 70 characters in body
Source Link
Iosif Pinelis
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

Unconditional? Certainly not, if I understood your question correctly. E.g., suppose that $\mu$ is the standard Gaussian measure on $\mathbb R^d$ and $B$ is the ball of radius $r>0$ centered at $0$. Then for any $\delta\in(0,1)$, by the law of large numbers, $$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{(r+\epsilon)^2}d\Big)\to1$$ for $d\to\infty$ and $\epsilon\in(0,(1-\delta)\sqrt d-r\,]$, where $Z_1,Z_2,\dots$ are iid $N(0,1)$. So, asymptotically there is no decrease at all in $\epsilon\le(1-\delta)\sqrt d-r$. So, any bound of the form $1-\mu(B^\epsilon)\le\epsilon\,\text{poly}(\epsilon)$ will not hold in this example.

Unconditional? Certainly not, if I understood your question correctly. E.g., suppose that $\mu$ is the standard Gaussian measure on $\mathbb R^d$ and $B$ is the ball of radius $r>0$ centered at $0$. Then for any $\delta\in(0,1)$, by the law of large numbers, $$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{(r+\epsilon)^2}d\Big)\to1$$ for $d\to\infty$ and $\epsilon\in(0,(1-\delta)\sqrt d-r\,]$, where $Z_1,Z_2,\dots$ are iid $N(0,1)$. So, asymptotically there is no decrease at all in $\epsilon\le(1-\delta)\sqrt d-r$.

Unconditional? Certainly not. E.g., suppose that $\mu$ is the standard Gaussian measure on $\mathbb R^d$ and $B$ is the ball of radius $r>0$ centered at $0$. Then for any $\delta\in(0,1)$, by the law of large numbers, $$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{(r+\epsilon)^2}d\Big)\to1$$ for $d\to\infty$ and $\epsilon\in(0,(1-\delta)\sqrt d-r\,]$, where $Z_1,Z_2,\dots$ are iid $N(0,1)$. So, asymptotically there is no decrease at all in $\epsilon\le(1-\delta)\sqrt d-r$. So, any bound of the form $1-\mu(B^\epsilon)\le\epsilon\,\text{poly}(\epsilon)$ will not hold in this example.

added 46 characters in body
Source Link
Iosif Pinelis
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

Unconditional? Certainly not, if I understood your question correctly. E.g., suppose that $\mu$ is the standard Gaussian measure on $\mathbb R^d$ and $B=\{0\}$$B$ is the ball of radius $r>0$ centered at $0$. Then for any $\delta\in(0,1)$, by the law of large numbers, $$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{\epsilon^2}d\Big)\to1$$$$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{(r+\epsilon)^2}d\Big)\to1$$ for $d\to\infty$ and $\epsilon\in(0,(1-\delta)\sqrt d\,]$$\epsilon\in(0,(1-\delta)\sqrt d-r\,]$, where $Z_1,Z_2,\dots$ are iid $N(0,1)$. So, asymptotically there is no decrease at all in $\epsilon\le(1-\delta)\sqrt d$$\epsilon\le(1-\delta)\sqrt d-r$.

Unconditional? Certainly not, if I understood your question correctly. E.g., suppose that $\mu$ is the standard Gaussian measure on $\mathbb R^d$ and $B=\{0\}$. Then for any $\delta\in(0,1)$, by the law of large numbers, $$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{\epsilon^2}d\Big)\to1$$ for $d\to\infty$ and $\epsilon\in(0,(1-\delta)\sqrt d\,]$, where $Z_1,Z_2,\dots$ are iid $N(0,1)$. So, asymptotically there is no decrease at all in $\epsilon\le(1-\delta)\sqrt d$.

Unconditional? Certainly not, if I understood your question correctly. E.g., suppose that $\mu$ is the standard Gaussian measure on $\mathbb R^d$ and $B$ is the ball of radius $r>0$ centered at $0$. Then for any $\delta\in(0,1)$, by the law of large numbers, $$1-\mu(B^\epsilon)=P\Big(\frac1d\sum_1^d Z_i^2>\frac{(r+\epsilon)^2}d\Big)\to1$$ for $d\to\infty$ and $\epsilon\in(0,(1-\delta)\sqrt d-r\,]$, where $Z_1,Z_2,\dots$ are iid $N(0,1)$. So, asymptotically there is no decrease at all in $\epsilon\le(1-\delta)\sqrt d-r$.

Source Link
Iosif Pinelis
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229