Draw samples from distribitions in the neighborhood of a fixed distribution

Question

Disclaimer

Sorry in advance for vagueness. I'm still trying to get my ideas right on this one.

Setup

So, let $P$ be a distribution on a Euclidean space $X$ with an $\ell_p$ metric, and let $P_\epsilon$ be another distribution on $X$ whose Wasserstein distance (or KL diverence, for simplicity and as a starting point) from $P$ is at most $\epsilon$.

Question

• What is an effective way for sampling from $P_\epsilon$ given that sampling from $P$ is easy ? Alternative, how to compute expectations w.r.t $P_\epsilon$, i.e computing things like $\mathbb E_{x \sim P_\epsilon}[f(x)]$, or $\max_{P_\epsilon} \mathbb E_{x \sim P_\epsilon}[f(x)]$ for a smooth function $f$ ?

• Is this problem linked to another well-studied problem ?

Answer 1

Maybe to add to the point of calculating $\max_{P_\varepsilon} \mathbb{E}_{P_\varepsilon}[f]$: I will write this a bit more in line with the literature I will refer to. Let $(X, d)$ be some polish space and a probability measure $\bar{\nu} \in \mathcal{P}(X)$ fix. Then the problem is \begin{equation} \Phi(f) :=\sup_{\nu \in \mathcal{P}(X):\\ W_1(\bar{\nu},\nu) \leq \varepsilon} \int f d\nu \end{equation}

This problem is well studied, even for more general "transport distances" (Wasserstein distances but with more general cost functions, not just metrices).

More or less, one has a dual representation, which for the above example reads \begin{equation} \Phi(f) = \inf_{\lambda \geq 0}\left( \lambda \varepsilon + \int_{X} \sup_{y \in X} \left(f(y) - \lambda d(x,y)\right) \bar{\nu}(dx)\right). \end{equation}

Aside from the fact that this can be numerically solved in some cases (see first source below), it also has a kind of sampling interpretation (This isn't in the literature I think, and more of a personal viewpoint):

To evaluate $\int f d\bar\nu$ one could of course simple sample points $x\sim \bar\nu$ and take as sample value $f(x)$.

To evaluate $\sup_{\nu \in \mathcal{P}(X):\\ W_1(\bar{\nu},\nu) \leq \varepsilon} \int f d\nu$, the duality formula motivates a similar scheme. Pretending that $\lambda$ is fix, one can sample points $x \sim \bar{\nu}$ and points $y_{x,1},...,y_{x,N}$ in a neighborhood of $x$ and take as one sample value $\sup_{i=1,...,N} f(y_{x,i}) - \lambda d(x,y_{x,i})$. (Finding $\lambda$ and including the term $\lambda \varepsilon$ must be done as well of course)

Sources:

https://link.springer.com/article/10.1007/s10107-017-1172-1 (first paper in this respect afaik, but not quite so general. Includes a linear programming formulation for the dual in case that $\bar\nu$ is sum of diracs)

https://arxiv.org/pdf/1604.01446.pdf (more general duality, see Theorem 1)

An interesting extension is studied in https://arxiv.org/pdf/1706.10186.pdf (See Theorem 2.4 for the duality) which includes problems of the form \begin{equation} \sup_{\nu \in \mathcal{P}(X)} \int f d\nu - \varphi(W_1(\bar\nu,\nu)) \end{equation} which reduces to $\Phi(f)$ if $\varphi(x) = \infty$ for $x \geq \varepsilon$ and $\varphi(x) = 0$, else.

Answer 2

E.g., for the Wasserstein distance $W_1(P,Q)$ between two probability measures $P$ and $Q$ one has the following duality formula: \begin{equation} W_1(P,Q)=\sup\Big\{\Big|\int f\,dP-\int f\,dQ\Big|\colon \text{Lip}(f)\le1\Big\}, \end{equation} where Lip$(f)$ is the Lipschitz constant for a function $f$. It then trivially follows that $|\int f\,dP_\epsilon-\int f\,dP|\le\epsilon$ for any $1$-Lipschitz function $f$ if $W_1(P_\epsilon,P)\le\epsilon$. (Of course, $\int f\,dP$ -- or simply $Pf$ or $P(f)$ -- is a simpler and better notation for what people in some research fields write as $\mathbb E_{x \sim P}[f(x)]$. If a probability measure $\mathbb P$ is fixed, then it may be better to write $\mathbb Ef$ instead of $\int f\,d\mathbb P$.)