Poster
The Broad Optimality of Profile Maximum Likelihood
Yi Hao · Alon Orlitsky
East Exhibition Hall B, C #234
Keywords: [ Theory ] [ Information Theory ] [ Theory ]
[
Abstract
]
Abstract:
We study three fundamental statistical-learning problems: distribution estimation, property estimation, and property testing. We establish the profile maximum likelihood (PML) estimator as the first unified sample-optimal approach to a wide range of learning tasks. In particular, for every alphabet size and desired accuracy : \textbf{Distribution estimation} Under distance, PML yields optimal sample complexity for sorted-distribution estimation, and a PML-based estimator empirically outperforms the Good-Turing estimator on the actual distribution; \textbf{Additive property estimation} For a broad class of additive properties, the PML plug-in estimator uses just four times the sample size required by the best estimator to achieve roughly twice its error, with exponentially higher confidence; \textbf{-R\'enyi entropy estimation} For an integer , the PML plug-in estimator has optimal sample complexity; for non-integer , the PML plug-in estimator has sample complexity lower than the state of the art; \textbf{Identity testing} In testing whether an unknown distribution is equal to or at least far from a given distribution in distance, a PML-based tester achieves the optimal sample complexity up to logarithmic factors of . With minor modifications, most of these results also hold for a near-linear-time computable variant of PML.
Live content is unavailable. Log in and register to view live content