# 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. Feb 18 '19 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 [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

• Thanks! But a specific reference would be very helpful :) Feb 25 '19 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) Feb 25 '19 at 17:10

In Appendix B of [Ashtiani et al., Neurips 2018]. https://arxiv.org/pdf/1710.05209.pdf

• In that paper, the paragraph at the end of Section 1.2 (starting with "Even for the case of a single Gaussian,") is highly misleading. There probably wasn't any published proof of this (which I'm not even sure about) because, again, it is considered folklore, and likely appears in lecture notes from decades ago. Apr 27 '20 at 17:30