<p><em>Disclaimer: I am biased, in that I will suggest a survey which I have written.</em></p>

<hr>

<p>What you seem to be looking for can be captured under the field of <em>distribution testing</em>, a subfield of Property Testing initiated in TCS by the work(s) of Batu, Fortnow, Rubinfeld, Smith, and White in 2000. </p>

<p>Most of the works in this field answers questions of the following sort:</p>

<blockquote>
  <p>Given i.i.d. sample from one (or several) unknown propbability distribution(s) over a known discrete domain, and a parameter $\varepsilon &gt; 0$, how to distinguish between (i) the distribution has some prespecified property of interest $\mathcal{P}$ and (ii) it is at distance at least $\varepsilon$ (in total variation distance/statistical distance/$\ell_1$ distance) from every distribution that has this property?</p>
</blockquote>

<p>For instance, defining the property to be the singleton $\{p\}$ (where $p$ is a known, fixed distribution of interest) you get the <em>identity testing</em> problem.</p>

<p>People have considered many variants, including varying the metric ($\ell_2$, Hellinger, Earthmover, $f$-divergences). It dates back to last year, but here is <a href="http://www.cs.columbia.edu/~ccanonne/files/misc/2015-survey-references.html" rel="noreferrer">a list of references</a> (from the second survey below).</p>

<p>There has been a lot of work in this area: I would suggest the following pointers and surveys:</p>

<ul>
<li><p>Chapter 11 of the <a href="http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html" rel="noreferrer">upcoming <em>Introduction to Property Testing</em></a> book by O. Goldreich</p></li>
<li><p><em>A Survey on Distribution Testing: Your Data is Big. But is it Blue?</em>
(C. Canonne, 2015)
<a href="http://eccc.hpi-web.de/report/2015/063/" rel="noreferrer">http://eccc.hpi-web.de/report/2015/063/</a></p></li>
<li><p><em>Taming Big Probability Distributions</em> (R. Rubinfeld, 2012)
<a href="https://people.csail.mit.edu/ronitt/papers/xrds-rr-dist.pdf" rel="noreferrer">https://people.csail.mit.edu/ronitt/papers/xrds-rr-dist.pdf</a></p></li>
</ul>

<p>(There are others -- see e.g. the <a href="https://people.csail.mit.edu/ronitt/sublinear.html" rel="noreferrer">surveys referenced by Ronitt Rubinfeld here</a> for property testing in general, and some discussion of distribution testing.)</p>

<p>Some slides:
<a href="http://www.cs.columbia.edu/~ccanonne/files/talks/candidacy-2015-04-20-columbia.pdf" rel="noreferrer">http://www.cs.columbia.edu/~ccanonne/files/talks/candidacy-2015-04-20-columbia.pdf</a></p>

<hr>

<p>Now, this is trying to address the question "after coming up with a (set of) hypotheses, how to <strong>test</strong> whether they are good. (Hence the testing and tolerant testing focus.) You may also want to start from the start, and ask how to <strong>learn</strong> the distribution itself, or the relevant parameter (i.e., <em>learning</em> instead of <em>testing</em>). Not surprisingly, this becomes distribution <em>learning</em> (or density estimation), with all its variants (proper learning, agnostic learning, etc.). I am a bit more out of my depth there, but if that's what you are after you may want to have a look at</p>

<ul>
<li><em>Learning Structured Distributions</em> (I. Diakonikolas, 2016)
Invited Book Chapter, Handbook of Big Data, Chapman and Hall/CRC.
<a href="http://www.iliasdiakonikolas.org/distribution-learning-survey.pdf" rel="noreferrer">http://www.iliasdiakonikolas.org/distribution-learning-survey.pdf</a> </li>
</ul>

<p>and things like this (slightly outdated) <a href="http://www.columbia.edu/~cs2035/stoc/stoc2014/tutorials.shtml#ede" rel="noreferrer">workshop from STOC'12.</a></p>

CC BY-SA 3.0
2016-12-28T13:44:31.063Z
(also, if the above seems lacking, I'd be happy to dig deeper to provide more pointers)
Clement C.
CC BY-SA 3.0
2016-12-28T13:37:10.127Z
2016-12-28T13:43:44.353Z
2016-12-28T13:43:44.353Z
Clement C.
<p>Here is a start:</p>

<p>Paninski, "Variational minimax estimation of discrete distributions under KL loss",
<a href="https://papers.nips.cc/paper/2586-variational-minimax-estimation-of-discrete-distributions-under-kl-loss.pdf" rel="nofollow noreferrer">https://papers.nips.cc/paper/2586-variational-minimax-estimation-of-discrete-distributions-under-kl-loss.pdf</a></p>

<p>Orlitsky, Suresh, "Competitive Distribution Estimation: Why is Good-Turing Good"
<a href="https://papers.nips.cc/paper/5762-competitive-distribution-estimation-why-is-good-turing-good" rel="nofollow noreferrer">https://papers.nips.cc/paper/5762-competitive-distribution-estimation-why-is-good-turing-good</a></p>

<p>Valiant, Valiant, "The Power of Linear Estimators"
<a href="http://theory.stanford.edu/~valiant/papers/VVshort.pdf" rel="nofollow noreferrer">http://theory.stanford.edu/~valiant/papers/VVshort.pdf</a></p>

<p>Bhattacharya, Valiant, "Testing Closeness With Unequal Sized Samples"
<a href="https://papers.nips.cc/paper/5908-testing-closeness-with-unequal-sized-samples.pdf" rel="nofollow noreferrer">https://papers.nips.cc/paper/5908-testing-closeness-with-unequal-sized-samples.pdf</a></p>

<p>I'll be happy for others to add if I missed anything big...</p>

CC BY-SA 3.0
2016-12-20T06:44:43.610Z
I found the "Good-Turing Good" and "Linear Estimator" papers instructive. Thanks!
madman_with_a_box
CC BY-SA 3.0
2016-12-18T08:05:30.673Z
2016-12-18T08:05:30.673Z
Aryeh
<p>A common model is to assume independent samples from $p$ and construct some estimate $q$ from the samples. In the case of a discrete distribution, this is particularly well-studied theoretically (using $\ell_1$ aka "total variation" aka "statistical distance" as the most common measure of closeness). A recent paper is <a href="http://theory.stanford.edu/~valiant/papers/optlearning_arxiv.pdf" rel="nofollow noreferrer">"Instance Optimal Learning" by Valiant and Valiant</a>.</p>

CC BY-SA 3.0
2016-12-19T04:02:47.567Z
2016-12-19T04:02:47.567Z
usul
<p>Consider that you have a probability distribution <em>p</em> of some quantity X and you have obtained (via some algorithm) an estimate <em>q</em> of <em>p</em> according to some definition of closeness. Are there methods/papers that theoretically analyze and bound the estimate?</p>

<p>As a more concrete example, consider <a href="https://arxiv.org/abs/1506.02574" rel="nofollow noreferrer">this</a> paper which designs a streaming algorithm to estimate the degree distribution of a graph and defines a new notion of closeness called Relative-Hausdorff Distance (RHD). The paper experimentally validates their estimate to be close (according to RHD) to the actual distribution for several real-world graphs. I want to know if there are methods/references in literature that one can use to give provable (theoretical) guarantees of their closeness.</p>

<reference-request><graph-algorithms><approximation-algorithms><pr.probability>
Approaches for Theoretical Analysis of Estimates of Probability Distributions
madman_with_a_box
# Approaches for Theoretical Analysis of Estimates of Probability Distributions

(Asked by: username_0 on 2016-12-18)

Consider that you have a probability distribution *p* of some quantity X and you have obtained (via some algorithm) an estimate *q* of *p* according to some definition of closeness. Are there methods/papers that theoretically analyze and bound the estimate?

As a more concrete example, consider [this](https://arxiv.org/abs/1506.02574) paper which designs a streaming algorithm to estimate the degree distribution of a graph and defines a new notion of closeness called Relative-Hausdorff Distance (RHD). The paper experimentally validates their estimate to be close (according to RHD) to the actual distribution for several real-world graphs. I want to know if there are methods/references in literature that one can use to give provable (theoretical) guarantees of their closeness.

**Tags:** reference-request, graph-algorithms, approximation-algorithms, pr.probability

---

## 3 answers

### Answer by username_1 on 2016-12-28. Score: 4

*Disclaimer: I am biased, in that I will suggest a survey which I have written.*

---

What you seem to be looking for can be captured under the field of *distribution testing*, a subfield of Property Testing initiated in TCS by the work(s) of Batu, Fortnow, Rubinfeld, Smith, and White in 2000.

Most of the works in this field answers questions of the following sort:

> Given i.i.d. sample from one (or several) unknown propbability distribution(s) over a known discrete domain, and a parameter $\varepsilon > 0$, how to distinguish between (i) the distribution has some prespecified property of interest $\mathcal{P}$ and (ii) it is at distance at least $\varepsilon$ (in total variation distance/statistical distance/$\ell\_1$ distance) from every distribution that has this property?

For instance, defining the property to be the singleton $\{p\}$ (where $p$ is a known, fixed distribution of interest) you get the *identity testing* problem.

People have considered many variants, including varying the metric ($\ell\_2$, Hellinger, Earthmover, $f$-divergences). It dates back to last year, but here is [a list of references](http://www.cs.columbia.edu/~ccanonne/files/misc/2015-survey-references.html) (from the second survey below).

There has been a lot of work in this area: I would suggest the following pointers and surveys:

* Chapter 11 of the [upcoming *Introduction to Property Testing*](http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html) book by O. Goldreich
* *A Survey on Distribution Testing: Your Data is Big. But is it Blue?*
  (C. Canonne, 2015)
  <http://eccc.hpi-web.de/report/2015/063/>
* *Taming Big Probability Distributions* (R. Rubinfeld, 2012)
  <https://people.csail.mit.edu/ronitt/papers/xrds-rr-dist.pdf>

(There are others -- see e.g. the [surveys referenced by Ronitt Rubinfeld here](https://people.csail.mit.edu/ronitt/sublinear.html) for property testing in general, and some discussion of distribution testing.)

Some slides:
<http://www.cs.columbia.edu/~ccanonne/files/talks/candidacy-2015-04-20-columbia.pdf>

---

Now, this is trying to address the question "after coming up with a (set of) hypotheses, how to **test** whether they are good. (Hence the testing and tolerant testing focus.) You may also want to start from the start, and ask how to **learn** the distribution itself, or the relevant parameter (i.e., *learning* instead of *testing*). Not surprisingly, this becomes distribution *learning* (or density estimation), with all its variants (proper learning, agnostic learning, etc.). I am a bit more out of my depth there, but if that's what you are after you may want to have a look at

* *Learning Structured Distributions* (I. Diakonikolas, 2016)
  Invited Book Chapter, Handbook of Big Data, Chapman and Hall/CRC.
  <http://www.iliasdiakonikolas.org/distribution-learning-survey.pdf>

and things like this (slightly outdated) [workshop from STOC'12.](http://www.columbia.edu/~cs2035/stoc/stoc2014/tutorials.shtml#ede)

> **Comments:**
> **username_1**: (also, if the above seems lacking, I'd be happy to dig deeper to provide more pointers)  

---

### Answer by username_2 on 2016-12-18. Score: 1

Here is a start:

Paninski, "Variational minimax estimation of discrete distributions under KL loss",
<https://papers.nips.cc/paper/2586-variational-minimax-estimation-of-discrete-distributions-under-kl-loss.pdf>

Orlitsky, Suresh, "Competitive Distribution Estimation: Why is Good-Turing Good"
<https://papers.nips.cc/paper/5762-competitive-distribution-estimation-why-is-good-turing-good>

Valiant, Valiant, "The Power of Linear Estimators"
<http://theory.stanford.edu/~valiant/papers/VVshort.pdf>

Bhattacharya, Valiant, "Testing Closeness With Unequal Sized Samples"
<https://papers.nips.cc/paper/5908-testing-closeness-with-unequal-sized-samples.pdf>

I'll be happy for others to add if I missed anything big...

> **Comments:**
> **username_0**: I found the "Good-Turing Good" and "Linear Estimator" papers instructive. Thanks!  

---

### Answer by username_3 on 2016-12-19. Score: 0

A common model is to assume independent samples from $p$ and construct some estimate $q$ from the samples. In the case of a discrete distribution, this is particularly well-studied theoretically (using $\ell\_1$ aka "total variation" aka "statistical distance" as the most common measure of closeness). A recent paper is ["Instance Optimal Learning" by Valiant and Valiant](http://theory.stanford.edu/~valiant/papers/optlearning_arxiv.pdf).


---

