About learning a single Gaussian in total-variation distance

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$$

• 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. – Clement C. Feb 18 at 21:38

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 , the second two are good exercises.

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

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

• Thanks! But a specific reference would be very helpful :) – gradstudent Feb 25 at 16:39
• @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) – Clement C. Feb 25 at 17:10