Learning Populations of Parameters
Consider the following estimation problem: there are n entities, each with an unknown parameter p i ∈ [0, 1], and we observe n independent random variables, X 1 , . . . , X n , with X i ∼ Binomial(t, p i ). How accurately can one recover the "histogram" (i.e. cumulative density function) of the p i 's? While the empirical estimates would recover the histogram to earth mover distance Θ(
1 distance between the CDFs), we show that, provided n is sufficiently large, we can achieve error O( 1 t ) which is information theoretically optimal. We also extend our results to the multi-dimensional parameter case, capturing settings where each member of the population has multiple associated parameters. Beyond the theoretical results, we demonstrate that the recovery algorithm performs well in practice on a variety of datasets, providing illuminating insights into several domains, including politics, sports analytics, and variation in the gender ratio of offspring.
In this paper, authors study the problem of learning a set of Binomial parameters in Wasserstein distance and demonstrate that sorted set of probabilities can be learned at a rate of (1/t) where t is the parameter in the Binomial distribution. The result seems interesting and I had a great time reading it. However, I would like to understand the technical novelty of the paper better.
Can the authors please expand on the differences between this paper and one of the cited papers: “Instance optimal learning of discrete distributions”, by Valiant and Valiant? To be more specific:
In many of the discrete learning problems, Poisson approximation holds i.e., Binomial (t,p_i) ~ Poisson (tp_i). Hence, the proposed problem is very similar to estimating n Poisson random variables with means tp_1, tp_2, \ldots tp_n.  Similarly the problem in the VV paper boils down to estimating many Poisson random variables. Hence, aren't they almost the same problem?
Furthermore, in VV’s paper, they use empirical estimates for large Poisson random variables (mean > log n), and use a moment based approach for small Poisson random variables (mean < log n). In this paper, authors use moment based approach for small Poisson random variables (mean < t). In both the cases, the moment based approach yields an improvement of 1/poly(mean) ~1/poly(t) improvement in earthmovers / Wasserstein’s distance.
Given the above, can you please elaborate the differences between the two papers?
Few other questions to the authors:
1. In Theorem 1: What is the dependence of t in the term O_{delta, t}(1/\sqrt{n}).
2. In Theorem 1: s is not known in advance, it is a parameter to be tuned/ supplied to the algorithm. Hence, how do you obtain min_s in the right hand side of the equation?  
3. Why Wasserstein’s distance? 
4. Good-Turing approach (McAllester Schapire ‘00) seems to perform well for instance optimality of discrete distributions in KL distance (Orlitsky Suresh ‘15). However, VV showed that Good-Turing does not work well for total variation distance. In your problem, you are looking at Wasserstein’s distance. Can you please comment if you think Good-Turing approaches work well for this distance? Can you given example / compare these approaches at least experimentally?
Edits after the rebuttal:
Changed to Good paper, accept.
> For ANY value of t, there exist dists/sets of p_i's such that the VV and Good-Turing approaches would recover dists that are no better (and might be worse?) than the empirical distribution (i.e. they would get a rate of convergence > O(1/sqrt(t)) rather than the O(1/t) that we get).
Can you please add these examples in the paper, at least in the appendix? It would be also nice if you can can compare with these approaches experimentally.
> Suppose p_i = 0.5 for all i, t=10, and n is large. The analogous "poissonized" setting consists of taking m<--Poi(5n) draws from the uniform distribution over n items, and the expected number of times the ith item is seen is distributed as Poi(5). Poi(5) has variance 5, though Binomial(10,0.5) has variance 10/4 = 2.5, and in general, for constant p, Poi(t*p) and Binomial(t,p) have constant L1 distance and variances that differ by a factor of (1-p). 
While I agree that they have a constant L1 distance, I still am not convinced that these problems are 'very different'. Do you believe that your algorithm (or a small variation of it)  would not work for the problem where the goal is to estimate n Poisson random variables? If so / no, please comment. If not, at least say something about it in the paper. 
> [A "bad" construction is the following: consider a distribution of p_i's s.t. the corresponding mixture of binomials approximates a Poisson, in which case VV and Good-Turing will conclude wrongly that all the p_i's are identical.]
I do not agree with this comment too. Note that for this argument to work it is not sufficient to approximate each Poisson coordinate with a  mixture of binomials coordinate. One has to approximate a Poisson product distribution over n coordinates, with a mixture of binomial random variables with n coordinates. I believe this task gets harder as n-> infty.
> It depends on the distribution (and is stated in the theorem), but can be as bad as 2^t.
Please mention it in the paper.