Vector version of concentration of Lipschitz functions on sphere (Levy's Lemma)

Question

Levy's Lemma asserts Lipschitz functions of vectors chosen uniformly from the unit hypersphere concentrate:

Lemma. Suppose $f:\mathbb{S}^{d-1} \to \mathbb{R}$ is $L$-Lipschitz on the unit hypersphere. Then, if $\vec{x}$ is drawn uniformly from the $d$-dimensional unit hypersphere, for some constant $C>0$, \begin{equation*} \mathbb{P}[ |f(\vec{x}) - \mathbb{E}[f(\vec{x})]| > \epsilon ] \leq 2\exp\left( \frac{-C(d+1)\epsilon^2}{L^2} \right). \end{equation*}

I am interested in 2-norm bounds for the vector case ($f:\mathbb{S}^{d-1}\to\mathbb{R}^n$ and $f$ satisfies $\|f(\vec{x}) - f(\vec{y})\|_2 \leq L \| \vec{x}-\vec{y}\|_2$). In particular, I am wondering whether a $d$ dependence is necessary? I have tried searching for such a result as I imagine this problem is standard, but haven't seemed to find the right keyword.

Answer 1

One can avoid the $n$-dependence. Let $H$ be a Hilbert space, endowed with the norm $\|\cdot\|$. Given $f:\mathbb{S}^{d-1}\to H$ which is $L$-Lipschitz, the goal is to prove a concentration inequality for $f$. Let $Y=(Y_1,\ldots, Y_d)$ be a Gaussian vector in $\mathbb R^d$, with mean $0$ and covariance matrix $I$. Recall that $Y/|Y|$ is uniformly distributed on $\mathbb{S}^{d-1}$, where $|Y|$ is the Euclidean norm of $Y$.

The $\chi^2$ variable $|Y|^2$ satisfies the inequality: $$P(|Y|^2<d/2)=P\Bigl(d-|Y|^2 \ge 2\sqrt{d \cdot d/16} \Bigr)\le e^{-d/16} \tag{*}$$ by [1], eq. (4.4).

Define $g:\mathbb R^d \to H$ by $$g(y):=f\circ \psi, \quad \text{where} \quad \psi(y)=\frac{y}{|y| \vee \sqrt{d/2} } \,.$$

Since $\psi$ is Lipschitz with constant $c_1=\sqrt{2/d}$, we infer that $g$ is Lipschitz with constant $c_1 L$.

Next, consider the Doob Martingale $M_k:=E[g(Y) |Y_1,\ldots,Y_k]$ for $k=0,1,\ldots,d$.

We can apply Pinelis' Theorem 3.3. from [2] to this Martingale to obtain the desired concentration for $g(Y)$. Finally note that $(*)$ implies that $$P[g(Y) \ne f(Y/|Y|)] \le e^{-d/16} \,.$$

[1] Laurent, B. ; Massart, P.
Adaptive estimation of a quadratic functional by model selection.
Ann. Statist. 28 (2000), no. 5, 1302–1338. https://projecteuclid.org/journalArticle/Download?urlid=10.1214%2Faos%2F1015957395

[2] Pinelis, Iosif. "Optimum bounds for the distributions of martingales in Banach spaces." The Annals of Probability (1994): 1679-1706. https://projecteuclid.org/journals/annals-of-probability/volume-22/issue-4/Optimum-Bounds-for-the-Distributions-of-Martingales-in-Banach-Spaces/10.1214/aop/1176988477.pdf