<p>Essentially, this follows from three facts:</p>

<ul>
<li><p>learning a Gaussian in total variation distance <span class="math-container">$\delta$</span> is equivalent to learning its two parameters, <span class="math-container">$\mu,\Sigma$</span>, to (respectively) <span class="math-container">$\ell_2$</span> and relative Frobenius norms <span class="math-container">$O(\delta)$</span>. <em>(Since then the "empirical Gaussian" with the mean and covariance you estimated will be <span class="math-container">$\delta$</span>-close to the true Gaussian).</em></p></li>
<li><p>learning the mean <span class="math-container">$\mu$</span> to <span class="math-container">$\ell_2$</span> distance <span class="math-container">$\delta$</span> can be done with <span class="math-container">$O(\frac{n}{\delta^2})$</span> samples. <em>(This is tight)</em></p></li>
<li><p>learning the covariance to relative Frobenius distance <span class="math-container">$\delta$</span> can be done with <span class="math-container">$O(\frac{n^2}{\delta^2})$</span> samples. <em>(This is tight)</em></p></li>
</ul>

<p>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.</p>

<p><em>(If you really want a specific reference, I can try to dig some up.)</em></p>

<hr>

<p>[1] Theorem 1.3 in this recent paper is overkill, but will do the job. <a href="https://arxiv.org/abs/1810.08693" rel="nofollow noreferrer">https://arxiv.org/abs/1810.08693</a> </p>

CC BY-SA 4.0
2019-02-25T16:39:19.280Z
Thanks! But a specific reference would be very helpful :)
gradstudent
CC BY-SA 4.0
2019-02-25T17:10:48.047Z
@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 https://arxiv.org/abs/1604.06443 (Section 4.2.2)
Clement C.
CC BY-SA 4.0
2019-02-18T18:34:08.557Z
2019-02-19T06:22:08.320Z
2019-02-19T06:22:08.320Z
Clement C.
<p>In Appendix B of [Ashtiani et al., Neurips 2018]. <a href="https://arxiv.org/pdf/1710.05209.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1710.05209.pdf</a></p>

CC BY-SA 4.0
2020-04-27T17:30:10.547Z
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.
Clement C.
CC BY-SA 4.0
2020-03-02T09:58:55.337Z
2020-03-02T09:58:55.337Z
user43170
<p>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! </p>

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

<hr>

<p>To clarify the notation of "TV" used above : </p>

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

<p><span class="math-container">$ 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 $</span></p>

CC BY-SA 4.0
2019-02-18T21:38:18.487Z
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.
<ds.algorithms><machine-learning><lg.learning><st.statistics>
About learning a single Gaussian in total-variation distance
gradstudent
# About learning a single Gaussian in total-variation distance

(Asked by: username_0 on 2019-02-18)

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 $

**Tags:** ds.algorithms, machine-learning, lg.learning, st.statistics
> **Comments:**
> **username_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.  

---

## 2 answers

### Answer by username_1 on 2019-02-18. Score: 4 | Accepted answer

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>

> **Comments:**
> **username_0**: Thanks! But a specific reference would be very helpful :)  
> **username_1**: @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 https://arxiv.org/abs/1604.06443 (Section 4.2.2)  

---

### Answer by username_2 on 2020-03-02. Score: 2

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

> **Comments:**
> **username_1**: 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.  

---

