Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-186 | 19th November 2016 12:38

A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation



The advent of data science has spurred interest in estimating properties of discrete distributions over large alphabets. Fundamental symmetric properties such as support size, support coverage, entropy, and proximity to uniformity, received most attention, with each property estimated using a different technique and often intricate analysis tools.

Motivated by the principle of maximum likelihood, we prove that for all these properties, a single, simple, plug-in estimator—profile maximum likelihood (PML) —performs as well as the best specialized techniques. We also show that the PML approach is competitive with respect to any symmetric property estimation, raising the possibility that PML may optimally estimate many other symmetric properties.

ISSN 1433-8092 | Imprint