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


3 Answers 3


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 (from the second survey below).

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

(There are others -- see e.g. the surveys referenced by Ronitt Rubinfeld here 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

and things like this (slightly outdated) workshop from STOC'12.

  • $\begingroup$ (also, if the above seems lacking, I'd be happy to dig deeper to provide more pointers) $\endgroup$
    – Clement C.
    Dec 28, 2016 at 13:44

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

  • $\begingroup$ I found the "Good-Turing Good" and "Linear Estimator" papers instructive. Thanks! $\endgroup$ Dec 20, 2016 at 6:44

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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