## Instance Optimal Learning of Discrete Distributions

by Gregory Valiant and Paul Valiant.

The main result in this paper is that knowing the historgram of the distribution (or, equivalently, knowing the distriburtion up to a relaling of its elements) does not help much when trying to learn the distribution. In other words, an algorithm is presented such that given $n$ samples from an arbitrary distribution $p$ performs almost as well as any algorithm that is given the histogram of $p$ (i.e., the set $\{(v,h_p(v))\in(0,1]\times\N:h_p(v)=|\{i:p(i)=v\}|\}$) along with these $n$ samples.