A General Framework for Symmetric Property Estimation
Moses Charikar, Kirankumar Shiragur, Aaron Sidford
Abstract
In this paper we provide a general framework for estimating symmetric properties of distributions from i.i.d. samples. For a broad class of symmetric properties we identify the {\em easy} region where empirical estimation works and the {\em difficult} region where more complex estimators are required. We show that by approximately computing the profile maximum likelihood (PML) distribution \cite{ADOS16} in this difficult region we obtain a symmetric property estimation framework that is sample complexity optimal for many properties in a broader parameter regime than previous universal estimation approaches based on PML. The resulting algorithms based on these \emph{pseudo PML distributions} are also more practical.
BibTeX
@inproceedings{NEURIPS2019_f19fec2f,
author = {Charikar, Moses and Shiragur, Kirankumar and Sidford, Aaron},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {A General Framework for Symmetric Property Estimation},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/f19fec2f129fbdba76493451275c883a-Paper.pdf},
volume = {32},
year = {2019}
}