Skip to main content
edited title
Link
passerby51
  • 1.7k
  • 9
  • 17

Lipschitz functions that saturate the Lipschitz inequality on the average (part 1)

deleted 438 characters in body
Source Link
passerby51
  • 1.7k
  • 9
  • 17

Consider a 1-Lipschitz function $f: \mathbb R^n \to \mathbb R$ satisfying the inequality \begin{align*} |f(x) - f(y)| \le \|x-y\|_2, \;\forall x,y \in \mathbb R^n. \end{align*} For $n \ge 2$, can we find a 1-Lipschitz function that saturates the above inequality on the average?

To make the notion of "on the average" precise, let $x$ and $y$ be independent standard Gaussian vectors, i.e., $x,y \sim N(0,I_n)$. One can show that $$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1.$$ while $$\mathbb E\|x-y\|_2 \asymp \sqrt{n}.$$ Is there a 1-Lipschitz function $f : \mathbb R^n \to \mathbb R$ such that $$\mathbb E|f(x) - f(y)| \asymp \sqrt{n}?$$ Here $\asymp$ means inequalities go in both directions up to constants.

A related question is determining the order of $$ \sup_{f \in \text{Lip}(1)}\mathbb E|f(x) - f(y)| $$ where $\text{Lip}(1)$ is the set of $1$-Lipschitz functions from $\mathbb R^n$ to $\mathbb R$.

EDIT: For the Gaussian case, the answer is negative as was pointed out by Iosif Pinelis. How about when $x$ has independent sub-Gaussian coordinates with O(1) sub-Gaussian norms. The result $$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1$$ still holds per Theorem 3.1.1 here. Can we find such $f$ in this case (e.g., say $x_i \sim \text{Unif}(-1,1)$)?

Consider a 1-Lipschitz function $f: \mathbb R^n \to \mathbb R$ satisfying the inequality \begin{align*} |f(x) - f(y)| \le \|x-y\|_2, \;\forall x,y \in \mathbb R^n. \end{align*} For $n \ge 2$, can we find a 1-Lipschitz function that saturates the above inequality on the average?

To make the notion of "on the average" precise, let $x$ and $y$ be independent standard Gaussian vectors, i.e., $x,y \sim N(0,I_n)$. One can show that $$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1.$$ while $$\mathbb E\|x-y\|_2 \asymp \sqrt{n}.$$ Is there a 1-Lipschitz function $f : \mathbb R^n \to \mathbb R$ such that $$\mathbb E|f(x) - f(y)| \asymp \sqrt{n}?$$ Here $\asymp$ means inequalities go in both directions up to constants.

A related question is determining the order of $$ \sup_{f \in \text{Lip}(1)}\mathbb E|f(x) - f(y)| $$ where $\text{Lip}(1)$ is the set of $1$-Lipschitz functions from $\mathbb R^n$ to $\mathbb R$.

EDIT: For the Gaussian case, the answer is negative as was pointed out by Iosif Pinelis. How about when $x$ has independent sub-Gaussian coordinates with O(1) sub-Gaussian norms. The result $$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1$$ still holds per Theorem 3.1.1 here. Can we find such $f$ in this case (e.g., say $x_i \sim \text{Unif}(-1,1)$)?

Consider a 1-Lipschitz function $f: \mathbb R^n \to \mathbb R$ satisfying the inequality \begin{align*} |f(x) - f(y)| \le \|x-y\|_2, \;\forall x,y \in \mathbb R^n. \end{align*} For $n \ge 2$, can we find a 1-Lipschitz function that saturates the above inequality on the average?

To make the notion of "on the average" precise, let $x$ and $y$ be independent standard Gaussian vectors, i.e., $x,y \sim N(0,I_n)$. One can show that $$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1.$$ while $$\mathbb E\|x-y\|_2 \asymp \sqrt{n}.$$ Is there a 1-Lipschitz function $f : \mathbb R^n \to \mathbb R$ such that $$\mathbb E|f(x) - f(y)| \asymp \sqrt{n}?$$ Here $\asymp$ means inequalities go in both directions up to constants.

A related question is determining the order of $$ \sup_{f \in \text{Lip}(1)}\mathbb E|f(x) - f(y)| $$ where $\text{Lip}(1)$ is the set of $1$-Lipschitz functions from $\mathbb R^n$ to $\mathbb R$.

added 421 characters in body
Source Link
passerby51
  • 1.7k
  • 9
  • 17

Consider a 1-Lipschitz function $f: \mathbb R^n \to \mathbb R$ satisfying the inequality \begin{align*} |f(x) - f(y)| \le \|x-y\|_2, \;\forall x,y \in \mathbb R^n. \end{align*} For $n \ge 2$, can we find a 1-Lipschitz function that saturates the above inequality on the average?

To make the notion of "on the average" priceprecise, let $x$ and $y$ be independent standard Gaussian vectors, i.e., $x,y \sim N(0,I_n)$. One can show that $$\mathbb E \big|\|x\| - \|y\|\big| \asymp 1.$$$$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1.$$ while $$\mathbb E\|x-y\|_2 \asymp \sqrt{n}.$$ Is there a 1-Lipschitz function $f : \mathbb R^n \to \mathbb R$ such that $$\mathbb E|f(x) - f(y)| \asymp \sqrt{n}?$$ Here $\asymp$ means inequalities go in both directions up to constants.

A related question is determining the order of $$ \sup_{f \in \text{Lip}(1)}\mathbb E|f(x) - f(y)| $$ where $\text{Lip}(1)$ is the set of $1$-Lipschitz functions from $\mathbb R^n$ to $\mathbb R$.

EDIT: For the Gaussian case, the answer is negative as was pointed out by Iosif Pinelis. How about when $x$ has independent sub-Gaussian coordinates with O(1) sub-Gaussian norms. The result $$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1$$ still holds per Theorem 3.1.1 here. Can we find such $f$ in this case (e.g., say $x_i \sim \text{Unif}(-1,1)$)?

Consider a 1-Lipschitz function $f: \mathbb R^n \to \mathbb R$ satisfying the inequality \begin{align*} |f(x) - f(y)| \le \|x-y\|_2, \;\forall x,y \in \mathbb R^n. \end{align*} For $n \ge 2$, can we find a 1-Lipschitz function that saturates the above inequality on the average?

To make the notion of "on the average" price, let $x$ and $y$ be independent standard Gaussian vectors, i.e., $x,y \sim N(0,I_n)$. One can show that $$\mathbb E \big|\|x\| - \|y\|\big| \asymp 1.$$ while $$\mathbb E\|x-y\|_2 \asymp \sqrt{n}.$$ Is there a 1-Lipschitz function $f : \mathbb R^n \to \mathbb R$ such that $$\mathbb E|f(x) - f(y)| \asymp \sqrt{n}?$$ Here $\asymp$ means inequalities go in both directions up to constants.

A related question is determining the order of $$ \sup_{f \in \text{Lip}(1)}\mathbb E|f(x) - f(y)| $$ where $\text{Lip}(1)$ is the set of $1$-Lipschitz functions from $\mathbb R^n$ to $\mathbb R$.

Consider a 1-Lipschitz function $f: \mathbb R^n \to \mathbb R$ satisfying the inequality \begin{align*} |f(x) - f(y)| \le \|x-y\|_2, \;\forall x,y \in \mathbb R^n. \end{align*} For $n \ge 2$, can we find a 1-Lipschitz function that saturates the above inequality on the average?

To make the notion of "on the average" precise, let $x$ and $y$ be independent standard Gaussian vectors, i.e., $x,y \sim N(0,I_n)$. One can show that $$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1.$$ while $$\mathbb E\|x-y\|_2 \asymp \sqrt{n}.$$ Is there a 1-Lipschitz function $f : \mathbb R^n \to \mathbb R$ such that $$\mathbb E|f(x) - f(y)| \asymp \sqrt{n}?$$ Here $\asymp$ means inequalities go in both directions up to constants.

A related question is determining the order of $$ \sup_{f \in \text{Lip}(1)}\mathbb E|f(x) - f(y)| $$ where $\text{Lip}(1)$ is the set of $1$-Lipschitz functions from $\mathbb R^n$ to $\mathbb R$.

EDIT: For the Gaussian case, the answer is negative as was pointed out by Iosif Pinelis. How about when $x$ has independent sub-Gaussian coordinates with O(1) sub-Gaussian norms. The result $$\mathbb E \big|\|x\|_2 - \|y\|_2\big| \asymp 1$$ still holds per Theorem 3.1.1 here. Can we find such $f$ in this case (e.g., say $x_i \sim \text{Unif}(-1,1)$)?

added 205 characters in body
Source Link
passerby51
  • 1.7k
  • 9
  • 17
Loading
Source Link
passerby51
  • 1.7k
  • 9
  • 17
Loading