Skip to main content
deleted 1 character in body
Source Link
Denis Serre
  • 52.3k
  • 10
  • 146
  • 300

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 ana $n$$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.

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 an $n$ 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.

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.

Bumped by Community user
fixed typo
Source Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

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

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

Lemma. Suppose $f:\mathbb{S}^{d-1} \to \mathbb{R}$ is $L$-LipshitzLipschitz 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 an $n$ 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.

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

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

Lemma. Suppose $f:\mathbb{S}^{d-1} \to \mathbb{R}$ is $L$-Lipshitz 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 an $n$ 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.

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

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 an $n$ 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.

Source Link

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

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

Lemma. Suppose $f:\mathbb{S}^{d-1} \to \mathbb{R}$ is $L$-Lipshitz 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 an $n$ 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.