3
$\begingroup$

I am trying to prove or disprove that the empirical distribution can learn any continuous distribution w.r.t the total variation distance. The context is the one of statistical learning.
I am quite sure that the proposition is false, but I might likely be wrong. I have looked online and into some books, but I couldn't find a similar formulation for the problem, so if you know some literature that would also be appreciated.


(edit: as pointed out in the comment, the distance I am defining here coincides with the total variation distance in this context.)

I am considering distributions on the real numbers and the set $$ \mathcal F = \{ g \in \mathcal C^b(\mathbb R) \ \mid \ \lVert {g}\rVert_\infty \leq 1 \} $$ and the corresponding F-divergence $$ d_\mathcal F (\mu \mid \nu ) = \sup_{g \in \mathcal F} \Big | \int_\mathbb R g \ d\mu - \int_\mathbb R g\ d\nu \ \Big | .$$

I need to prove (or negate) the following:

For any $\mu$ continuous probability distribution, given i.i.d samples $X_1, \dots , X_n$ from $\mu$, prove that the empirical distribution $\tilde \mu _n = \frac{1}{n} \sum_{i=1}^n \delta_{X_i} $ converges in probability to $\mu$ w.r.t $d_\mathcal F $, i.e. $$ P( d_\mathcal F (\mu \mid \tilde \mu_n ) > \epsilon) \xrightarrow[ n \to \infty ]{} 0, \text{ } \ \forall \epsilon>0 $$

With $\delta_x$ I am denoting Dirac's delta.

Some more information and my considerations

It can be proved that convergence w.r.t to $d_\mathcal F$ is equivalent to convergence with respect to $$ \tilde d (\mu \mid \nu ) = \sup_{g \in \mathcal C^c(\mathbb R) \\ \lVert {g}\rVert_\infty \leq 1 } \Big | \int_\mathbb R g \ d\mu - \int_\mathbb R g\ d\nu \ \Big | .$$ This might be helpful in proving the proposition, since $\mathcal C^c(\mathbb R)$ is separable: the countable and dense subset could be used to take care of the $\sup$ I believe, but I don't exactly see how. Moreover, I don't see how am I supposed to use the density of $\mu$.

Despite Chebyshev's inequality/WLLN proves convergence for any single $g \in \mathcal F$, with rate indipendent from $g$ $$ P\Big (\Big | \int_\mathbb R g \ d\mu - \int_\mathbb R g\ d\tilde \mu_n \ \Big | > \epsilon \Big ) \leq \frac{Var(g(X_1))}{\epsilon^2 n} \stackrel{g(X) \in [-1,1] \ P \ a.s. }{\leq} \frac{1}{\epsilon^2 n} $$ it seems quite hard to me that such convergence can happen uniformly over $g$.

One could restrict the problem to the subset of functions in $\mathcal F$ s.t. $\mathbb E [g(X_1)] = 0 $ by taking the expected value inside the random variable, but that isn't much and I'm not even sure if that would be a good idea.

I have been thinking of using some trivial continuous distribution (such as the gaussian or uniform distributions) as a counterexample, but proving that converge doesn't happen in such case is still hard: my main problem is taking care of the $\sup$ inside the probability.

Maybe there's some known theorem which can be used and is going over my head: Glivenko-Cantelli guarantees that $\tilde \mu _n $ learns any probability distribution w.r.t to the divergence corresponding to the half-line's indicators, but I don't think that helps.

$\endgroup$
2
  • 1
    $\begingroup$ Isn't $d_{\mathcal F}$ the total variation distance (or a multiple thereof) ? If you were to consider measures on a compact interval, e.g. $[0,1]$ then $TV$ gives the same topology as Wasserstein, and the statement is true. I don't know the answer in the unbounded case. $\endgroup$ Commented Sep 20, 2023 at 11:22
  • $\begingroup$ @GabrielRomon that is true, $d_\mathcal F$ coincides with the total variation distance on continuous distributions (but I don't know whether it's equivalent or not for general measures). I will add that into the question, thank you $\endgroup$
    – pppp0l
    Commented Sep 20, 2023 at 11:43

1 Answer 1

2
$\begingroup$

The proposition is false: the empirical distribution does not learn all continuous distributions w.r.t. $d_{TV}$.

Some days ago I found a proof: it holds that $$ d_{TV}(\mu \ || \ \nu) = \sup_{g \in \mathcal F} \big | \mathbb E_\mu [g] - \mathbb E_\nu [g] \big |, $$ where $\mathcal F$ is the set of measurable functions bounded by 1 (there could be a 2 factor depending on your definition of $d_{TV}$). Once one utilises this, the proof is trivial.

For a given $n\in \mathbb N$, for samples $X_1, \dots , X_n$ one can consider $$ f_n(x) = 1 - \unicode{x1D7D9} _{\{X_1, \dots , X_n\}} $$ which is in $\mathcal F$ for any sample realisation. Since it is Borel a.e. 1 it is s.t. $$ \mathbb E_\mu [f_n] = 1$$ for any continuously distributed $\mu$. On the other side, $$\mathbb E_\mu [f_n] = \frac{1}{n} \sum_{i=1}^n f_n({X_i}) = 0 .$$ So $$ d_{TV}(\mu \ || \ {\tilde \mu_n}) = \sup_{g \in \mathcal F} \big | \mathbb E_\mu [g] - \mathbb E_{\tilde \mu_n} [g] \big | \geq \big | \mathbb E_\mu [f_n] - \mathbb E_{\tilde \mu_n} [f_n] \big | = 1.$$ Since for any realisation of $X_1, \dots , X_n$ there is such an $f_n$, we cannot have probability convergence to any continuously distributed $\mu$.

I couldn't initially think of such a proof since I was still thinking about continuous functions $f_n$ to disprove the convergence, but once one finds the $f_n$ above one also sees how to build a continuous one. Since the proof seems correct to me, I'll close the question.

$\endgroup$
2
  • 1
    $\begingroup$ According to this paper, p. 1438 it holds that $d_{\textrm{TV}}(\mu,\mu_n)=1$. $\endgroup$
    – Snoop
    Commented Oct 16, 2023 at 15:46
  • $\begingroup$ @Snoop that totally makes sense, but I think that with the above definition it is equal to 2 (I have often seen $d_{TV}$ defined in an equivalent way which results in a divergence smaller of a factor $\frac{1}{2}$) $\endgroup$
    – pppp0l
    Commented Oct 18, 2023 at 15:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .