Papers › The Broad Optimality of Profile Maximum Likelihood
The Broad Optimality of Profile Maximum Likelihood
Yi Hao, Alon Orlitsky
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 ℓ₁ distance, PML yields optimal Θ(k/(ε²logk)) 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; α-Renyi 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 ℓ₁ 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).
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections