The Broad Optimality of Profile Maximum Likelihood

Code

• github.com/ucsdyi/PML
  OfficialIn papernone★ 0

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 : Distribution estimation Under _1 distance, PML yields optimal (k/(^2 k)) sample complexity for sorted-distribution estimation, and a PML-based estimator empirically outperforms the Good-Turing estimator on the actual distribution; 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; -R\'enyi entropy estimation For integer >1, the PML plug-in estimator has optimal k^1-1/ sample complexity; for non-integer >3/4, the PML plug-in estimator has sample complexity lower than the state of the art; Identity testing In testing whether an unknown distribution is equal to or at least far from a given distribution in _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).

Reproductions