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 ?



Draw samples from distribitions in the neighborhood of a fixed distribution
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.


