1
$\begingroup$

I am looking for the proof of this following result which I saw as being claimed as a "folklore" in a paper. It would be helpful if someone can share a reference where this has been shown!

Let $G$ be an $n-$dimensional Gaussian and let $\delta >0$. Then there exists a polynomial time algorithm that given $O(\frac {n^2}{\delta^2})$ independent samples from $G$ returns a probability distribution ${\bf P}$ so that with probability at least $\frac 2 3$ we have, $d_{\text{TV}}(G,{\bf P}) < \delta$


To clarify the notation of "TV" used above :

Given two distributions $\bf P$ and $\bf Q$ with p.d.fs (which we denote by the same symbols) we define the ``Total-Variation" distance between them as,

$ d_{\text{TV}}({\bf P},{\bf Q}) := \frac {1}{2} \int_{\bf x \in \mathbb{R}^n} \vert {\bf P}(\bf x) - {\bf Q}(\bf x) \vert d{\bf x} =: \frac {1}{2} ||{\bf P} - {\bf Q}||_1 $

$\endgroup$
  • 1
    $\begingroup$ A minor technical point: this is not really the definition of TV distance, rather a characterization (known as Scheffé's identity). The definition is $d_{\rm TV}(\mathbf{P},\mathbf{Q}) = \sup_S (\mathbf{P}(S)-\mathbf{Q}(S))$, where the supremum ranges over all measurable sets. $\endgroup$ – Clement C. Feb 18 at 21:38
4
$\begingroup$

Essentially, this follows from three facts:

  • learning a Gaussian in total variation distance $\delta$ is equivalent to learning its two parameters, $\mu,\Sigma$, to (respectively) $\ell_2$ and relative Frobenius norms $O(\delta)$. (Since then the "empirical Gaussian" with the mean and covariance you estimated will be $\delta$-close to the true Gaussian).

  • learning the mean $\mu$ to $\ell_2$ distance $\delta$ can be done with $O(\frac{n}{\delta^2})$ samples. (This is tight)

  • learning the covariance to relative Frobenius distance $\delta$ can be done with $O(\frac{n^2}{\delta^2})$ samples. (This is tight)

I suggest you try to prove these yourself. The first one follows from relatively "standard" facts about Gaussians [1], the second two are good exercises.

(If you really want a specific reference, I can try to dig some up.)


[1] Theorem 1.3 in this recent paper is overkill, but will do the job. https://arxiv.org/abs/1810.08693

$\endgroup$
  • $\begingroup$ Thanks! But a specific reference would be very helpful :) $\endgroup$ – gradstudent Feb 25 at 16:39
  • $\begingroup$ @gradstudent I'll try to find some. One reference (again, not the first, and that paper solves a much harder problem, but this lemma is relevant) for point 3 (covariance estimation) has a self-contained proof in arxiv.org/abs/1604.06443 (Section 4.2.2) $\endgroup$ – Clement C. Feb 25 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.