Isoperimetric inequality for $\epsilon$-expansion of a set only along a certain subspace

Question

Let $\gamma_n$ be the standard gaussian distribution on $\mathbb R^n$. Let $V$ be a $k$-dimensional subspace of $\mathbb R^n$. Finally let $A$ be any (nonempty) Borel subset of $A$ with $\gamma_n(A) = p > 0$, and and for any $\epsilon\ge 0$, let $A^\epsilon_V$ denote the directional $\epsilon$-expansion of $A$ along $V$, defined by $$ \begin{split} A_V^\epsilon &:= A + V \cap B(x;\epsilon)\\ &= \{x \in \mathbb R^d \mid x = v + a,\text{ for some }a \in A,\text{ and }v \in V\text{ with }\|v\| \le \epsilon\}. \end{split} $$ Note that if $k = n$ (i.e if $V = \mathbb R^n$), then $$ A^\epsilon_V = A + B(x;\epsilon) = \{x \in \mathbb R^n \mid d(x,A) \le \epsilon\}, $$ the usual $\epsilon$-expansion of $A$, and the isoperimetric inequality tells us that $$ \gamma_n(A^\epsilon) \ge \Phi(\Phi^{-1}(p)+\epsilon). \tag{1} $$

Question 1. Is there an anologous bound for $\gamma_n(A_V^\epsilon)$ in terms of $p$, $k$, and $\epsilon$ ?

Now, let $V$ be drawn from the Haar measure on grassmanian of $k$-dimensional subspaces of $\mathbb R^n$.

Question 2. What is a good lower-bound (say, of the type (1)) of $\mathbb E_V[\gamma_n(A^\epsilon_V)]$ in terms of $p$, $k$, and $\epsilon$ ?

Note. I'd already be very happy for pointers papers studying these kinds of problems (directional expansions, etc.) or related things.

Answer 1

$\newcommand{\ep}{\varepsilon}\newcommand\R{\mathbb R}\newcommand{\de}{\delta}\newcommand{\vpi}{\varphi}\newcommand{\Ga}{\Gamma}$In Question 2 you wanted a good lower bound on $E_V P(X\in A_V^\ep)$, where $\ep>0$ and $X$ is a standard normal random vector in $\R^n$ and $E_V$ means the averaging over all $k$-dimensional subspaces $V$ of $\R^n$.

Consider first the case when the set $A$ one of the two half-spaces to one side of an affine hyperplane in $\R^n$. Then, in view of this answer, for each $x\in\R^n$, \begin{equation*} E_V 1(x\in A_V^\ep)=Q_{n,k}\Big(\frac{d(x,A)^2}{\ep^2}\Big), \tag{1} \end{equation*} where $1-Q_{n,k}$ is the cdf of the beta distribution with parameters $k/2,(n-k)/2$ and $d(x,A)$ is the shortest distance from $x$ to $A$. Equality (1) will hold if $A$ is bounded by a finite number of affine hyperplanes in $\R^n$ and the shortest distance from $x$ to the intersection of any two of these affine hyperplanes is $>\ep$.

So, for such $A$ and $\ep\downarrow0$, \begin{equation*} E_V P(X\in A_V^\ep)=EE_V 1(X\in A_V^\ep)=EQ_{n,k}\Big(\frac{d(X,A)^2}{\ep^2}\Big)+O(\ep^2). \tag{1'} \end{equation*} Further, by the isoperimetric inequality, \begin{equation*} P(0<d(X,A)\le\ep)\ge g(p)\ep\,(1+o(1)), \end{equation*} where $p:=P(X\in A)$ and \begin{equation*} g(p):=\frac d{d\ep}\,\Phi(\Phi^{-1}(p)+\ep)\Big|_{\ep=0}=\vpi(\Phi^{-1}(p)), \end{equation*} where $\vpi:=\Phi'$, the standard normal pdf. So, \begin{equation*} \begin{aligned} &E_V P(X\in A_V^\ep)-P(X\in A) \\ & =\int_0^\ep Q_{n,k}\Big(\frac{\de^2}{\ep^2}\Big)P(d(X,A)\in d\de) +O(\ep^2) \\ &\ge\int_0^\ep Q_{n,k}\Big(\frac{\de^2}{\ep^2}\Big)g(p)\,d\de\,(1+o(1)) +O(\ep^2) \\ &=c_{n,k}\,\ep g(p)\,(1+o(1)) +O(\ep^2), \end{aligned} \end{equation*} where \begin{equation} c_{n,k}:=\int_0^1 Q_{n,k}\big(z^2\big)\,dz =\frac{\Ga((k+1)/2)/\Ga(k/2)}{\Ga((n+1)/2)/\Ga(n/2)}\Big[\sim\sqrt{\frac kn}\text{ if }n>k\to\infty\Big]. \end{equation} Thus, \begin{equation*} \liminf_{\ep\downarrow0}\frac{E_V P(X\in A_V^\ep)-P(X\in A)}\ep \ge c_{n,k}\,\vpi(\Phi^{-1}(p)). \tag{2} \end{equation*} Integrating this, we get \begin{equation*} E_V P(X\in A_V^\ep)\ge\Phi\big(\Phi^{-1}(p)+c_{n,k}\,\ep\big) \end{equation*} for all real $\ep>0$.

Inequality (2) turns into the equality if the set $A$ is one of the two half-spaces to one side of an affine hyperplane in $\R^n$.

By approximation, (2) should hold at least for all convex $A$ and probably for all Borel $A$.

---

As for Question 1, the only lower bound on $P(X\in A_V^\ep)$ in general is the trivial lower bound $p=P(X\in A)$ -- for any natural $n\ge2$, any natural $k<n$, any real $\ep>0$, and any $p\in(0,1)$. Indeed, let the set $A$ be one of the two half-spaces to one side of an affine hyperplane in $\R^n$ such that $P(X\in A)=p$. Let $V$ be any $k$-dimensional subspace of $\R^n$ parallel to the mentioned affine hyperplane. Then $A_V^\ep=A$ for all real $\ep>0$, and hence $P(X\in A_V^\ep)=P(X\in A)$.

Answer 2

I provide a complete solution for the case where $A$ is the intersection of $N = \mathcal O(\mathrm{poly}(n))$ half-spaces $H_i := \{x \in \mathbb R^n \mid x^\top w_i \le b_i\}$, where each $w_i$ is a unit-vector in $\mathbb R^n$ and $b_i \in \mathbb R$.

At the moment, I'm unable to extend the argument to arbitrary convex sets.

---

Claim 1. For any subspace $V \subseteq \mathbb R^n$, define $r(V) := \min_{i \in [N]} \|P_Vw_i\| \in [0,1]$, where $P_V$ is the orthogonal projector for $V$. Then, we have the set inclusion $$ A^{r(V)\cdot\epsilon} \subseteq A^\epsilon_V, $$ where $A^\delta := \{x \in \mathbb R^n \mid \mbox{dist}(x,A) \le \delta\}$ is the usual $\delta$-expansion of $A$ at level $\delta>0$.

Proof. If $\epsilon = 0$, both sets are equal to $A$ and there is nothing to prove. Otherwise, let $x \in A^{r(V)\epsilon}$. Then, $\mbox{dist}(x,A) \le r(V) \epsilon$. Now, it is well-known that the distance from a point to the intersection of a collection of sets is at least equal to the largest distance between the point and any of the sets. Using this fact, one computes $$ \begin{split} \frac{1}{\epsilon}\cdot\max_{i \in [N]}(x^\top w_i-b_i)_+ &= \frac{1}{\epsilon}\cdot \max_{i \in [N]} \mathrm{dist}(x,H_i)\\ &\le \frac{\mbox{dist}(x,A)}{\epsilon}\\ &\le r(V)\\ &:= \min_{i \in [N]}\|P_Vw_i\|\\ &= \min_{i \in [N]}\sup_{v \in V \cap B_d}v^\top w_i\\ &= \sup_{v \in V \cap B_d}\min_{i \in [N]}v^\top w_i. \end{split} $$ Thus, $\exists v \in V \cap B_d$ such that $x^\top w_i - b_i \le \epsilon v^\top w_i$, i.e $(x-\epsilon v)^\top w_i \le b_i$ for all $i \in [N]$. We conclude that $x \in A^\epsilon_V$. $\quad\quad\Box$

Let $p:=\mathbb P(X \in A)$. Since $X$ has gaussian concentration, we have

$$ \mathbb P(0 < \mbox{dist}(x,A) \le \epsilon) \ge g(p)\epsilon(1+o_\epsilon(1)), $$ where $g(p):= \dfrac{{\rm d}}{{\rm}d\epsilon}\Phi(\Phi^{-1}(p)+\epsilon)\bigg|_{\epsilon=0} = \varphi(\Phi^{-1}(p))$ is the gaussian isoperimetric profile.

Strategy. With these auxiliary results in place, the rest of the proof is analogous to user @Iosif's post, starting from after formula (1'),

like so $$ \begin{split} \mathbb P(X \in A^\epsilon_V ) - P(X \in A) &\ge \mathbb P(X \in A^{r(V)\epsilon}) - P(X \in A)\\ &= \int_0^{r(V)\epsilon} \mathbb P(\mbox{dist}(X,A) \in {\rm d}\delta)\\ &\ge \int_0^{r(V)\epsilon} g(p){\rm d}\delta(1+o_\epsilon(1))\\ &= r(V)\epsilon g(p)(1+o_\epsilon(1)). \end{split} $$ We deduce that $$ \liminf_{\epsilon \to 0^+}\frac{\mathbb P(X \in A^\epsilon_V ) - P(X \in A)}{\epsilon} \ge r(V)g(p) = r(V)\varphi(\Phi^{-1}(p)). $$ Integrating w.r.t $\epsilon$ then gives the following

Result for general subspace. For any subspace $V \subseteq \mathbb R^n$, it holds that $$ \mathbb P(X \in A^\epsilon_V) \ge \Phi(\Phi^{-1}(p)+r(V)\epsilon). $$

The following corollary solves our initial problem.

(Result for random subspace). Let $V \subseteq \mathbb R^n$ be a uniformly-random $k$-dimensional subspace of $\mathbb R^n$. Then, for any $t \in (0,\sqrt{k/n})$ it holds w.p. $1-e^{-\Omega(t^2d)}$ that $$ \mathbb P(X \in A^\epsilon_V) \ge \Phi(\Phi^{-1}(p)+(\sqrt{k/n}-t)\epsilon). $$

Proof. For each $i \in [N]$, the quantity $\|P_V w_i\|^2 = w_i^\top P_V w_i$ has gaussian concentration around its expected value of $\mathbb E_V[\mbox{trace}(P_V)] = k/n$. It then follows from a basic union bound (since $N$ is only polynomial in $n$) that $r(V) \ge \sqrt{k/n}-t$ w.p $1-e^{-\Omega(t^2d)}$ over $V$. The claim then follows from the previous result. $\quad\quad\Box$.

Answer 3

This post solves the problem (hopefully) in case where $A$ is a closed convex set with "sufficiently smooth" boundary.

---

Preliminaries

Let $S_{n-1}$ be the unit-sphere in $\mathbb R^n$ and consider the mapping $u_A:\mathbb R^n \setminus A \to S_{n-1}$ defined by $$ u_A(x):= (x-\Pi_A(x))/d_A(x), $$ where $\Pi_A(x)$ is the closest point in $A$ from $x$ and $d_A(x):=\|x-\Pi_A(x)\| = \inf_{a \in A}\|x-a\|$ is the distance of $x$ from $A$. It is a classical result that $d_A$ is convex and continuously differentiable on the open set $\mathbb R^n \setminus A$, with derivative given by $\nabla d_A(x) = u_A(x)$. We will need the following condition.

Smoothness condition (SC1). $u_A$ is $L$-Lipschitz on $\mathbb R^n \setminus A$, for some $L \in [0,\infty)$.

As we will see later, the value of the smoothness condition (SC1) is that it allows us to compare $A^\varepsilon_V$ and $A^\varepsilon$ via differential calculs.

Examples and non-examples. Thanks to this post, we know the following: https://mathoverflow.net/a/412746/78539

• (1) If $A$ is convex body (i.e compact and convex) of the form $A := \{x \in \mathbb R^n \mid f(x) \le 0\}$ for some $\mathcal C^2$ convex function with $\min f < 0$, then the smoothness condition (SC1) is satisfied.
• (2) If $A$ is such that the polar cone of $A-x$ has dimension $\ge 2$ for some $x \in \partial A$ (e.g, if $A$ is a closed convex polytope with at least one vertex), then the smoothness condition (SC1) is not satisfied.

---

The result and proof

We now state the main theorem which will be proved in the remainder of this post

Theorem. Suppose $A$ is a closed convex set which satisfies the smoothness condition (SC1). Let $V$ be any subspace of $\mathbb R^n$ (random or not!) such that $$ \mathbb P(\|P_Vu_A(x)\| \ge \alpha) \ge \beta,\text{ for all }x \in \mathbb R^n \setminus A, \tag{*} $$ where $P_V$ is the orthogonal projector for $V$ and $\alpha,\beta \in (0,1]$ are constants. Then, for any $\varepsilon \in [0,2\alpha/L]$, we have the lower-bound $$ \mathbb E_V \mathbb P_X(X \in A^\varepsilon_V) \ge \Phi(\Phi^{-1}(p)+\alpha\varepsilon)\cdot \beta, $$ where $p:=\mathbb P(X \in A)$.

Of course, the above result can be nontrivial only when $\beta > p$.

Proof. For any $x \in \mathbb R^n$ and sufficiently small $\varepsilon > 0$, we have the following chain of implications $$ \begin{split} x \not\in A^\epsilon_V &\implies x-\varepsilon v \not \in A\,\forall v \in V \cap B_n\\ &\implies d_A(x-\varepsilon v) > 0\,\forall v \in V \cap B_n\\ &\implies d_A(x) > \varepsilon v^\top u_A(x)-L\varepsilon\|v\|^2/2,\forall v \in V \cap B_n\\ &\implies d_A(x) > \varepsilon v^\top u_A(x)-L\varepsilon^2/2,\forall v \in V \cap B_n\\ &\implies d_A(x) > \varepsilon z^\top P_Vu_A(x) - L\varepsilon^2/2\,\forall z \in B_n\\ &\implies d_A(x) > \varepsilon \|P_Vu_A(x)\|-L\varepsilon^2/2. \end{split} $$ where

• the 3rd line is because the distance-to-$A$ function $d_A$ is differentiable on $\mathbb R^n \setminus A$, and its derivative $u_A$ is $L$-Lipschitz by hypothesis, and
• the fifth line is because $P_V z \in V \cap B_n$ for all $z \in B_n$.

By a contrapositive argument, we have established that $$ \begin{split} A^\varepsilon_V\setminus A &\supseteq \{x \in \mathbb R^n \setminus A \mid d_A(x) \le \varepsilon \|P_Vu_A(x)\|-L\varepsilon^2/2\}\\ & \supseteq \{x \in \mathbb R^n \mid 0 < d_A(X) \le \alpha\varepsilon-L\varepsilon^2/2,\, \|P_Vu_A(x)\| \ge \alpha\}. \end{split} \tag{1} $$

Thus, for each $x \in \mathbb R^n$, sufficiently small $\varepsilon > 0$, we have

$$ \begin{split} \mathbb E_V[1_{\{x \in A^\varepsilon_V\setminus A\}}] &\ge 1_{\{0 < d_A(x) \le \alpha \varepsilon - L\varepsilon^2/2\}}\cdot 1_{\{x \in \mathbb R^n\setminus A\}} \cdot \mathbb P_V(\|P_Vu_A(x)\| \ge \alpha)\\ &= 1_{\{0 < d_A(x) \le \alpha \varepsilon - L\varepsilon^2/2\}}\cdot \beta, \end{split} $$

Taking expectations w.r.t $X$ then gives $$ \begin{split} \mathbb E_V\mathbb P_X(X \in A^\varepsilon_V) - \mathbb P(X \in A) &= \mathbb E_V\mathbb P_X(X \in A^\varepsilon_V\setminus A)\\ &= \mathbb E_X\mathbb P_V(X \in A^\varepsilon_V\setminus A)\\ &= \mathbb E_X\mathbb E_V[1_{\{X \in A^\varepsilon_V\setminus A\}}]\\ &\ge \mathbb E_X[1_{\{0 < d_A(X) \le \alpha\varepsilon-L\varepsilon^2\}}]\cdot \beta\\ &=\mathbb P(0 < d_A(X) \le \alpha\varepsilon-L\varepsilon^2)\cdot\beta\\ &= \mathbb P(0 < d_A(X) \le \alpha\varepsilon-L\varepsilon^2)\cdot\beta. \end{split} $$

Now, for sufficiently small $\varepsilon$, one has

$$ \mathbb P(0 < d_A(X) \le \alpha\varepsilon-L\varepsilon^2/2) \ge \alpha g(p)\varepsilon(1+o_\varepsilon(1)), $$ where $g$ is the gaussian isoperimetric profile defined in the other answers. The remainder of the proof follows exactly the same path as the others. $\Box$

Corollary. Let $V$ be uniform over the Grassmannian of $k$-dimensional subspaces of $\mathbb R^n$. Then, under the above smoothness condition, it holds for every $t \in (0,\sqrt{k/n})$ and $\varepsilon \in [0,2\alpha_t/L]$ with $\alpha_t := \sqrt{k/n}-t$ that $$ \mathbb E_V\mathbb P_X(X \in A^\varepsilon_V) \ge \Phi(\Phi^{-1}(p)+\alpha_t\varepsilon)\cdot (1-e^{-\Omega(t^2d)}). $$

Proof. Follows from previous theorem and the fact that $$ \inf_{x \in \mathbb R^n\setminus A}\mathbb P(\|P_Vu_A(x)\| \ge \sqrt{k/n}-t) \ge \inf_{\theta \in S_{n-1}}\mathbb P(\|P_V\theta\| \ge \sqrt{k/n}-t) \ge 1-e^{-\Omega(t^2d)}, $$ where the last step is via chi-squared concentration (as in the other answers). $\quad\quad\quad\Box$