Data Amplification: A Unified and Competitive Approach to Property Estimation
Estimating properties of discrete distributions is a fundamental problem in statistical learning. We design the first unified, linear-time, competitive, property estimator that for a wide class of properties and for all underlying distributions uses just 2n samples to achieve the performance attained by the empirical estimator with n √ log n samples. This provides off-the-shelf, distribution-independent, "amplification" of the amount of data available relative to common-practice estimators. We illustrate the estimator's practical advantages by comparing it to existing estimators for a wide variety of properties and distributions. In most cases, its performance with n samples is even as good as that of the empirical estimator with n log n samples, and for essentially all properties, its performance is comparable to that of the best existing estimator designed specifically for that property.
This paper considers estimation of functionals of distributions in the high-dimensional regime, and designs an estimator that “amplifies” the amount of data required to attain the same error as compared to the plug-in approach.  In particular, the least squares error of functional estimation employing order n\sqrt{\log n} samples to compute the plug-in estimator can be matched by their estimator in just order n samples. The estimator uses a variant of the plug-in estimator for higher probabilities, and a polynomial smoothing technique for low probabilities, with a data-dependent threshold to decide whether a particular symbol probability is low or high.   The estimator runs in inear-time in number of samples, is competitive with the plug-in estimator with a larger number of samples, simple to compute, and sees improvement in simulations. The rates improve upon the plug-in estimator in the high dimensional regime where the support size is greater than the number of samples.  The paper is well-written and easy to follow, and I liked reading it. However, I did have a few concerns with some parts of it, in particular about how significant such an amplification result really is. These are listed in detail below:  Concerns:  1. As the authors mention is Section 4, Theorem 1 only really provides improvement over the least squares estimate when the loss of empirical (plug-in) estimator is slowly decaying ( log^{-\eps} n). In particular, this means that even with data amplification and substituting n for n\sqrt{n}, the rate of the improved estimator can only be improved in the second (double logarithmic) term. While such slow rates are understandable in high dimensions, the afforded improvement seems miniscule here.  2. As a counter to the point above, the authors show that for some functionals, the rate of the plug-in estimate beyond which one gains improvement can actually be as low as log^{-2} n. In this case, too, it seems like the amplification afforded would only be doubly logarithmic in the rate.  3. While the two points are not major weaknesses (the simulations seem to address whether or not an improvement is actually seen in practice), the paper would benefit from a discussion of the fact that the targeted improvement is in the (relatively) small n regime.  4. The paper would benefit from a more detailed comparison with related work, in particular making a detailed comparison to the time complexity and competitiveness of prior art.  Minor: 1. The proofs repeatedly refer to the Cauchy inequality, but it might be better given audience familiarity to refer to it as the Cauchy-Schwarz inequality.  Post-rebuttal: I have read the authors' response and am satisfied with it. I maintain my vote for acceptance.