Seminar: Efficient universal estimators for symmetric property estimation

Given i.i.d samples from an unknown distribution, estimating its symmetric properties is a classical problem in information theory, statistics, operations research, and computer science. Symmetric properties are those that are invariant to label permutations and include popular functionals such as entropy and support size. Over the past decade, this question has received great attention leading to computationally efficient and sample optimal estimators for various symmetric properties. Most of these estimators were property specific and the design of a single estimator that is sample optimal for any symmetric property remained a central open problem in the area. In a seminal result, Acharya et. al. showed that computing an approximate profile maximum likelihood (PML), a distribution that maximizes the likelihood of the observed multiset of frequencies, allows statistically optimal estimation of any symmetric property. However, since its introduction by Orlitsky et. al. in 2004, efficient computation of an approximate PML remained a well-known open problem. In our work, we resolved this question by designing the first efficient algorithm for computing an approximate PML distribution. In addition, our investigations have led to a deeper understanding of various computational and statistical aspects of PML and universal estimators. En route to achieving these results, our work has led to the design of better algorithms for deterministic permanent approximation, new rounding algorithms, faster optimization methods and novel techniques for statistical analysis.