Timezone: »

 
Poster
A General Framework for Symmetric Property Estimation
Moses Charikar · Kirankumar Shiragur · Aaron Sidford

Thu Dec 12 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #228
in Theory -- Learning Theory »

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.

Keywords: Information Theory · Learning Theory · Theory
[ Paper]  [ Slides] 

Author Information

Moses Charikar (Stanford University)
Kirankumar Shiragur (Stanford University)
Aaron Sidford (Stanford)

More from the Same Authors