Divergence between Probability Distributions from Samples via the Chamfer Distance Suppose I have two probability distributions $P$ and $Q$. I want to compute a divergence/distance between them. I do not have access to their densities, but I can draw samples $x\in D \subset \mathbb{R}^m$ from them. Let $X = \{x_i\mid x_i\sim P\}_{i=1}^n$ and $Y = \{y_j\mid y_j\sim Q\}_{j=1}^n$. Ideally, I'd like to be able to compute this fairly quickly as well.
There are a few simple candidates: the Earth Mover's (Wasserstein) distance (EMD) is good, but this one is a bit costly. I can use kernel density estimation, and then estimate the KL divergence with a Monte Carlo estimator (e.g., here or here), or fit a probability distribution to $X$ and $Y$ (e.g. Gaussian or GMM), and then come up with a distance (e.g. based on parameters or analytic KL divergences say), but simple distributions don't fit well, this has too many parameters I need to tweak, and it seems unnecessarily complex. (The Monte Carlo KL estimates didn't perform well either; I'd like to avoid density estimation). There's also the Hausdorff distance which has some probabilistic connections but depends wildly on $n$. I haven't yet explored kernelized maximum mean discrepancy much, which seems promising though.
However, I have seen quite a few papers lately use the Chamfer Distance (it is not a metric, but it is some form of divergence nonetheless) as an efficient (yet still quite effective in practice) substitute for the EMD. (e.g. see [1], [2]).
It is written $$ \mathcal{D}_C[X,Y] = \frac{1}{|X|} \sum_{x\in X} \min_{y\in Y} d(x,y) + \frac{1}{|Y|} \sum_{y\in Y} \min_{x\in X} d(x,y) $$
where $d:D\times D\rightarrow\mathbb{R}^+$ is some distance metric, e.g. $d(x,y)=||x-y||_2^2$. Basically, for each point in one set, we get the closest point in the other set, and compute the distance between them - summing the result over the set, and then doing the same for the other set. Sometimes the normalizing fractions are left out. 
My questions:


*

*Is there a probabilistic connection to using this on samples? E.g., for a particular $d$, is there a well-known continuous divergence that this approximates/bounds?

*Can $\mathcal{D}_C$ be used as a reasonable (pseudo)-distance between $P$ and $Q$? For example, can we guarantee that, as $n\rightarrow\infty$, if $D_C[X,Y]\rightarrow 0$, then, say, the KL or JS-divergence must also shrink to zero or be bounded by it? What sort of assumptions would be needed for this?

 A: Question 1: Continuous probabilistic Extension
Here's a possible continuous extension of $\mathcal D_C$ stated in terms of probability theory
$$\mathfrak{D}_C[P,Q]=\mathbb{E}_{x\sim P}\left[ \inf_{y\in\operatorname{supp} Q} d(x,y)\right] + \mathbb{E}_{x\sim Q}\left[ \inf_{y\in\operatorname{supp} P} d(x,y)\right]$$
where $\mathbb E_{x\sim P}$ is expectation with $P$-distributed $x$ and $\operatorname{supp} P$ is the support  of the probability measure $P$.
It is unclear to me how easily one can estimate this via sampling, but focusing on the first term we can get some intuition. Let $\{x_1,\ldots,x_n\}$ and $\{y_1,\ldots,y_m\}$ be i.i.d. samples of $P$ and $Q$ (resp.) and note that since $d(x,y)\geq 0$ we have
$$ 
\mathbb{E}_{x\sim P}\left[ \inf_{y\in\operatorname{supp} Q} d(x,y)\right] 
\leq 
\mathbb{E}_{x\sim P}\left[ \min_j d(x,y_j)\right] \approx \frac{1}{n}\sum_{i=1}^n \min_j d(x_i,y_j).$$
Question 2a: Is $\mathcal D_C[X,Y]$ a (psuedo)-metric?
No. The Chamfer distance you wrote with $d(x,y)=\|x-y\|^2$ is neither a metric or pseudo-metric because it does not satisfy the triangle inequality. This is mentioned in your second reference (page 4 where Chamfer distance is introduced) but for a concrete counter-example consider $A=\{0\}$, $B=\{1,2\}$, and $C=\{3\}$. Then $\mathcal D_C[A,C]=3^2+3^2=18$ but $\mathcal D_C[A,B]=\mathcal D_C[B,C]=1^2+\tfrac{1}{2}(1^2+2^2)=3.5$. This counter-example also works if you use $d(x,y)=\|x-y\|$.
Question 2b: $\mathcal D_C[X,Y] \to 0$ implies KL or JS divergence $\to 0$?
No. Let $\Omega\subseteq\mathbb{R}^m$ be the unit ball and consider any two probability distributions $P\neq Q$ with support $\Omega$. Let $X_n=\{x_1,\ldots,x_n\}$ and $Y_n=\{y_1,\ldots,y_n\}$ be i.i.d. samples from $P$ and $Q$ respectively. Let $H$ denote the Hausdorff distance and note that since $X_n\subseteq \Omega$ we have
$$ H(\Omega,X_n) = \sup_{p\in \Omega} \min_{x\in X_n} \|p-x\|.$$
Note that as $n\to\infty$ we have $H(\Omega,X_n)\to 0$ almost surely (if not, then there would be some disk $D\subseteq \Omega$ which didn't receive any samples, but that would happen with probability $(1-P(D))^n$ which vanishes as $n\to\infty$ since $P(D)>0$). Applying the same argument to $Y_n$ we have that (almost surely) for any $0<\delta<\tfrac{1}{2}$ we can choose an $N$ so that $H(\Omega,X_N),H(\Omega,Y_N)<\delta$. By triangle inequality we have
$$ H(X_N,Y_N)\leq H(X_N,\Omega) + H(\Omega, Y_N) < 2\delta $$
which implies that
$$ \forall x\in X_N\quad \min_{y\in Y_N} \|x-y\|<2\delta$$
$$ \forall y\in Y_N\quad \min_{x\in X_N} \|x-y\|<2\delta$$
Since $d(x,y)=\|x-y\|^2$ in the OP and $2\delta<1$ we have,
$$ \forall x\in X_N\quad \min_{y\in Y_N} d(x,y)<2\delta$$
$$ \forall y\in Y_N\quad \min_{x\in X_N} d(x,y)<2\delta$$
Thus,
$$ \mathcal D_C[X_N,Y_N] < \frac{1}{N}\sum_{x\in X_N} 2\delta + \frac{1}{N}\sum_{y\in Y_N} 2\delta = 4\delta$$
Since $0<\delta<\tfrac{1}{2}$ was arbitrary, we can conclude that $\lim_{n\to\infty} \mathcal D_C[X_n,Y_n]=0$ (almost surely). However, since $P\neq Q$ were general measures with support $\Omega$, they in general have nonzero KL or JS divergence.
