The Broad Optimality of Profile Maximum Likelihood

arXiv1906.03794MaRDI QIDQ6320215

Author name not available (Why is that?)

Publication date: 10 June 2019

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

k

and desired accuracy

v a r e p s i l o n

:

e x t b f D i s t r i b u t i o n e s t i m a t i o n

Under

e l l_{1}

distance, PML yields optimal

T h e t a (k / (v a r e p s i l o n^{2} l o g k))

sample complexity for sorted-distribution estimation, and a PML-based estimator empirically outperforms the Good-Turing estimator on the actual distribution;

e x t b f A d d i t i v e p r o p e r t y e s t i m a t i o n

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;

For integer

a l p h a > 1

, the PML plug-in estimator has optimal

k^{1 - 1 / a l p h a}

sample complexity; for non-integer

a l p h a > 3 / 4

, the PML plug-in estimator has sample complexity lower than the state of the art;

e x t b f I d e n t i t y t e s t i n g

In testing whether an unknown distribution is equal to or at least

v a r e p s i l o n

far from a given distribution in

e l l_{1}

distance, a PML-based tester achieves the optimal sample complexity up to logarithmic factors of

k

. Most of these results also hold for a near-linear-time computable variant of PML. Stronger results hold for a different and novel variant called truncated PML (TPML).

Has companion code repository: https://github.com/ucsdyi/PML

This page was built for publication: The Broad Optimality of Profile Maximum Likelihood

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6320215)