Timezone: »

 
Poster
Data Amplification: Instance-Optimal Property Estimation
Yi Hao · Alon Orlitsky

Tue Jul 14 07:00 AM -- 07:45 AM & Tue Jul 14 08:00 PM -- 08:45 PM (PDT) @ Virtual
in Poster Session 1 »
The best-known and most commonly used technique for distribution-property estimation uses a plug-in estimator, with empirical frequency replacing the underlying distribution. We present novel linear-time-computable estimators that significantly ``amplify'' the effective amount of data available. For a large variety of distribution properties including four of the most popular ones and for every underlying distribution, they achieve the accuracy that the empirical-frequency plug-in estimators would attain using a logarithmic-factor more samples. Specifically, for Shannon entropy and a broad class of Lipschitz properties including the $L_1$ distance to a fixed distribution, the new estimators use $n$ samples to achieve the accuracy attained by the empirical estimators with $n\log n$ samples. For support-size and coverage, the new estimators use $n$ samples to achieve the performance of empirical frequency with sample size $n$ times the logarithm of the property value. Significantly strengthening the traditional min-max formulation, these results hold not only for the worst distributions, but for each and every underlying distribution. Furthermore, the logarithmic amplification factors are optimal. Experiments on a wide variety of distributions show that the new estimators outperform the previous state-of-the-art estimators designed for each specific property.
Keywords: Computational Learning Theory · Information Theory and Estimation · Learning Theory · Non-parametric Methods · Statistical Learning Theory
[ Slides] 

Author Information

Yi Hao (University of California, San Diego)
Alon Orlitsky (UCSD)

More from the Same Authors