Press "Enter" to skip to content

Concentration for projected distributions

Photo of Sergey Germanovich Bobkov (1961 - ) a great explorer of gaussianity, isoperimetry, and concentration
Sergey Germanovich Bobkov (1961 - ) a great explorer of gaussianity, isoperimetry, and concentration

This post is devoted to a concentration inequality of Lipschitz functions for a class of projected probability distributions on the unit sphere of $\mathbb{R}^n$, $n\geq2$, \[ \mathbb{S}^{n-1}=\Bigr\{x\in\mathbb{R}^n:|x|:=\sqrt{x_1^2+\cdots+x_n^2}=1\Bigr\}. \]

Concentration. Consider a random vector $X$ of $\mathbb{R}^n$, $n\geq2$, and its Euclidean norm $|X|:=\sqrt{X_1+\cdots+X_n}$. Suppose that the law of $X$ satisfies to sub-Gaussian concentration inequality of Lipschitz functions, namely, for all $F:\mathbb{R}^n\to\mathbb{R}$ and all $r\geq0$, \begin{equation*} \mathbb{P}(|F(X)-\mathbb{E}F(X)|\geq r) \leq c\exp\Bigr(-\frac{r^2}{2C\|F\|_{\mathrm{Lip.}}^2}\Bigr). \end{equation*} for some constants $c,C > 0$. Then for all $F:\mathbb{R}^n\to\mathbb{R}$ and all $r\geq\sigma\|F\|_{\mathrm{Lip.}}$, \begin{align*} \mathbb{P}\Bigr( \Bigr|F\Bigr(\frac{X}{|X|}\Bigr)-\mathbb{E}F\Bigr(\frac{X}{|X|}\Bigr)\Bigr| \geq r \Bigr) &\leq2c\exp\Bigr(-\frac{\mu^2}{8C}\Bigr(\frac{r}{\|F\|_{\mathrm{Lip.}}}-\sigma\Bigr)^2\Bigr) \end{align*} where \[ \mu:=\mathbb{E}|X| \quad\text{and}\quad \sigma:=\mathbb{E}\Bigr|\frac{|X|}{\mu}-1\Bigr|. \] The quantity $\|F\|_{\mathrm{Lip.}}:=\sup_{x,y\in\mathbb{R}^n:x\neq y}\frac{|F(x)-F(y)|}{|x-y|}$ is the Lipschitz norm of $F$ with respect to the Euclidean norm on $\mathbb{R}^n$, and not with respect to the geodesic distance on $\mathbb{S}^{n-1}$.

The map $x\mapsto x/|x|$ is $1$-Lipschitz outside the unit ball, but is not Lipschitz at the origin. Instead of trying to compose functions, the idea is that since the real random variable $|X|$ is a Lipschitz function of $X$, it concentrates around its mean $\mu$, making $X/|X|$ close to $X/\mu$, which is a dilation of $X$, and which concentrates in turn!

If the law of $X$ is rotationnally invariant, then $X/|X|$ is uniformly distributed on $\mathbb{R}^n$.

The statement is dilation invariant, in the sense that if we replace $X$ by $\lambda X$ for some constant $\lambda > 0$, the left hand side is invariant, and the right hand side is also invariant, since $\mu$ and $C$ are replaced by $\lambda\mu$ and $\lambda C$ while $\sigma$ is invariant.

Since $X/|X|$ takes its values in the unit sphere $\mathbb{S}^{n-1}$, which has diameter $2$, we have $\bigr|F\bigr(\frac{X}{|X|}\bigr)-\mathbb{E}F\bigr(\frac{X}{|X|}\bigr)\bigr|\leq2\|F\|_{\mathrm{Lip.}}$, it follows that $\mathbb{P}\bigr( \bigr|F\bigr(\frac{X}{|X|}\bigr)-\mathbb{E}F\bigr(\frac{X}{|X|}\bigr)\bigr| \geq r \bigr)=0$ if $r > 2\|F\|_{\mathrm{Lip.}}$, as a consequence, the concentration inequality is useless when $r > 2\|F\|_{\mathrm{Lip.}}$.

Projected normal laws. Consider the Gaussian case $X\sim\mathcal{N}(m,\Sigma)$, $m\in\mathbb{R}^n$, $\Sigma\in\mathrm{Sym}^+_{n\times n}(\mathbb{R})$. Then the sub-Gaussian concentration of Lipschitz functions holds with \[ c=2 \quad\text{and}\quad C=\|\Sigma\|_{\mathrm{op.}}=\max_{|x|=1}\langle\Sigma x,x\rangle. \] The law of $X/|X|$ is known as the projected normal distribution on $\mathbb{S}^{n-1}$.

Let us further specialize to the isotropic case $(m,\Sigma)=(0,I_n)$. Then the law of $X/|X|$ is uniform, moreover $\|\Sigma\|_{\mathrm{op.}}=1$, $X_1,\ldots,X_n$ are i.i.d. $\mathcal{N}(0,1)$, and \[ \mu =\mathbb{E}(\chi(n)) =\sqrt{2}\frac{\Gamma(\frac{n+1}{2})}{\Gamma(\frac{n}{2})} \sim_{n\to\infty}\sqrt{n} \quad\text{while}\quad \sigma\sim_{n\to\infty}\frac{1}{\sqrt{\pi n}}, \] and these asymptotic estimates correspond to LLN and CLT for $X_1^2+\cdots+X_n^2$ and express the thin-shell phenomenon for the isotropic log-concave distribution $\mathcal{N}(0,I_n)$.

Proof. By replacing $r$ with $r/\|F\|_{\mathrm{Lip.}}$, we can assume without loss of generality that $\|F\|_{\mathrm{Lip.}}=1$. The concentration inequality, used with $F=\left|\cdot\right|$, gives, for all $\rho > 0$, \[ \mathbb{P}(||X|-\mu|\geq\rho \mu) \leq c\exp\Bigr(-\frac{\rho^2\mu^2}{2C}\Bigr). \] On the event $A_\rho=\{||X|-\mu| < \rho \mu\}$, \[ \Bigr|F\Bigr(\frac{X}{|X|}\Bigr)-F\Bigr(\frac{X}{\mu}\Bigr)\Bigr| \leq|X|\frac{||X|-\mu|}{|X|\mu} =\frac{||X|-\mu|}{\mu} \leq\rho. \] Moreover, we have \[ \Bigr|\mathbb{E}F\Bigr(\frac{X}{|X|}\Bigr)-\mathbb{E}F\Bigr(\frac{X}{\mu}\Bigr)\Bigr| \leq\mathbb{E}\Bigr|F\Bigr(\frac{X}{|X|}\Bigr)-F\Bigr(\frac{X}{\mu}\Bigr)\Bigr| \leq\sigma. \] Therefore, on $A_\rho$, \[ \Bigr|F\Bigr(\frac{X}{|X|}\Bigr)-\mathbb{E}F\Bigr(\frac{X}{|X|}\Bigr)\Bigr| \leq \Bigr|F\Bigr(\frac{X}{\mu}\Bigr)-\mathbb{E}F\Bigr(\frac{X}{\mu}\Bigr)\Bigr| +\bigr(\rho+\sigma\bigr). \] Therefore, for all $r\geq(\rho+\sigma)$, using again the concentration, \begin{align*} \mathbb{P}\Bigr( \Bigr|F\Bigr(\frac{X}{|X|}\Bigr)-\mathbb{E}F\Bigr(\frac{X}{|X|}\Bigr)\Bigr| \geq r \Bigr) &\leq \mathbb{P}(A_\rho^c)+\mathbb{P}\Bigr( \Bigr|F\Bigr(\frac{X}{\mu}\Bigr)-\mathbb{E}F\Bigr(\frac{X}{\mu}\Bigr)\Bigr| \geq r-(\rho+\sigma) \Bigr)\\ &\leq c\exp\Bigr(-\frac{\rho^2}{2C}\mu^2\Bigr) +c\exp\Bigr(-\frac{(r-(\rho+\sigma))^2}{2C}\mu^2\Bigr). \end{align*} It remains to select or optimize over $\rho$. Let us take $\rho=r-(\rho+\sigma)$, which gives $\rho=\frac{1}{2}(r-\sigma)$, which satisfies $r\geq(\rho+\sigma)$. This gives, for all $r\geq\sigma$, \begin{align*} \mathbb{P}\Bigr( \Bigr|F\Bigr(\frac{X}{|X|}\Bigr)-\mathbb{E}F\Bigr(\frac{X}{|X|}\Bigr)\Bigr| \geq r \Bigr) &\leq2c\exp\Bigr(-\frac{(r-\sigma)^2}{8C}\mu^2\Bigr). \end{align*}

Uniform case. If the law of $X$ is rotationally invariant, for instance when $X\sim\mathcal{N}(0,I_n)$, then $U:=X/|X|$ follows the uniform distribution on $\mathbb{S}^{n-1}$, and the concentration inequality of Milman and Schechtman states that for all $F:\mathbb{S}^{n-1}\to\mathbb{R}$ and $r\geq0$, \[ \mathbb{P}(|F(U)-\mathbb{E}F(U)|\geq r) \leq2\exp\Bigr(-\frac{nr^2}{2\|F\|_{\mathrm{Lip.}}^2}\Bigr), \] where the Lipschitz constant is with respect to the geodesic distance on $\mathbb{S}^{n-1}$.

Further comments. The concentration of Lipschitz functions for the uniform distribution on $\mathbb{S}^{n-1}$ dates back at least to Milman and Schechtman, as a consequence of the Lévy isoperimectric inequality for the uniform distribution on the sphere. In high-dimension, as $n\to\infty$, its gives the concentration of Lipschitz functions for the standard normal distribution, which can also be deduced from the Gaussian isoperimetric inequality of Sudakov and Tsirelson, or from the logarithmic Sobolev inequality of Gross via the Herbst argument, or from the Talagrand transportation inequality, or from the infimum convolution inequality of Maurey. It can also be deduced quickly from an elementary covariance representation, see [H]. We also refer to [AJS] for better prefactor constants and a detailed bibliography.

The idea of writing this post came after a question asked by Anthony Nguyen, a PhD student in signal processing at INRIA and École normale supérieure Paris-Saclay.

Further reading.

  • [Lé] Paul Lévy
    Problèmes concrets d'analyse fonctionnelle
    Gauthier-Villars, 1951
  • [MS] Vitali Davidovich Milman, Gideon Schechtman, with an appendix by Mikhaïl Gromov
    Asymptotic theory of finite dimensional normed spaces
    Springer, 1986
  • [B] Christer Borell
    The Brunn-minkowski inequality in Gauss space
    Inventiones mathematicae, 1975
  • [ST] Vladimir Nikolaevich Sudakov, Boris Semyonovich Tsirelson
    Extremal properties of half-spaces for spherically invariant measures
    Journal of Soviet Mathematics, 1978
  • [Le] Michel Ledoux
    The concentration of measure phenomenon
    AMS, 2001
  • [M] Bernard Maurey
    Some deviations inequalities
    Geometric & Functional Analysis (GAFA), 1(2), 188-197 (1991)
  • [T1] Michel Talagrand
    A new isoperimetric theorem and its application to concentration of measure phenomena
    Geometric & Functional Analysis (GAFA), 1(2), 211–223 (1991)
  • [T2] Michel Talagrand
    Transportation cost for Gaussian and other product measures
    Geometric & Functional Analysis (GAFA), 6(3), 587–600 (1995)
  • [BG] Sergey Germanovich Bobkov, Frederich Götze
    Exponential integrability and transportation cost related to logarithmic Sobolev inequalities
    Journal of Functional Analysis, 163(1), 1–28 (1999)
  • [H] Christian Houdré
    Covariance representation and an elementary proof of the Gaussian concentration inequality
    https://arXiv.org/abs/2410.06937
  • [AJS] Guillaume Aubrun, Justin Jenkinson, Stanislaw J. Szarek
    Optimal constants in concentration inequalities on the sphere and in the Gauss space
    https://arXiv.org/abs/2406.13581
    Leave a Reply

    Your email address will not be published.

    This site uses Akismet to reduce spam. Learn how your comment data is processed.

    Syntax · Style · .