On the Competitive Analysis and High Accuracy Optimality of Profile Maximum Likelihood

Yanjun Han, Kirankumar ShiragurSODA 2021 · OpenReview

TL;DR

This paper significantly improves the theoretical guarantees for Profile Maximum Likelihood (PML) estimation, showing it's not just competitive but optimally accurate for estimating symmetric properties of discrete distributions, especially in challenging high-accuracy regimes. The authors introduce novel techniques for analyzing PML and develop a new, stable estimator for sorted distributions.

What Problem Does This Paper Address?

Estimating properties of discrete probability distributions is fundamental in many fields. A key challenge is finding a universal estimator – one that performs well across a wide range of properties (like entropy, support size, etc.) without needing to know the specific property beforehand. The Profile Maximum Likelihood (PML) distribution, which maximizes the likelihood of observed data, emerged as a promising candidate for such a universal estimator. However, previous work showed that while PML is "competitive" (its error is at most twice that of the best specialized estimator, with a slightly worse failure probability), the exact error bound had a suboptimal exponent. This paper tackles the question of whether PML can achieve higher accuracy and better failure probability guarantees, particularly in the challenging regime where the desired accuracy ($\epsilon$) is very high relative to the sample size ($n$), specifically when $\epsilon \gg n^{-1/3}$.

Methods

The core of the paper's contribution lies in a refined analysis of the PML distribution. The authors introduce a novel "continuity" property of PML distributions, which allows them to "pool together" similar PML distributions. This is achieved through a sophisticated "chaining argument" involving a hierarchy of "coverings" (quantized versions) of PML distributions. This technique significantly reduces the error probability amplification factor from $\exp(O(\sqrt{n}))$ to $\exp(O(n^{1/3+c}))$.

Additionally, to achieve these improved guarantees, the authors construct a new estimator for the sorted distribution (a fundamental object in estimating properties of distributions). This estimator is designed to be stable and avoid "sample splitting" – a common but instability-inducing technique in prior work. It relies on a novel "smoothed local moments" approach and a single linear program, leading to near-optimal concentration properties.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and estimator construction for discrete distributions, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • PML's True Power: The paper demonstrates that PML isn't just a good "universal" estimator; it's optimally accurate in a broad range of scenarios, especially when high precision is required. This elevates PML's status from a competitive heuristic to a theoretically optimal tool.
  • Continuity is Key: The novel insight is that PML distributions exhibit a form of "continuity." By exploiting this, the authors can build a more refined analysis that avoids the loose union bounds of previous work.
  • Breaking Free from Sample Splitting: The development of a stable estimator for sorted distributions without sample splitting is a significant technical achievement. This approach not only improves stability but also leads to better trade-offs in approximation theory.
  • The $n^{-1/3}$ Threshold: The paper highlights $n^{-1/3}$ as a critical threshold for achieving optimal accuracy and concentration for universal estimators of symmetric properties. This suggests a fundamental limit or phase transition in this area.

Key Results

  • Improved Error Probability for PML: The PML plug-in estimator's error probability amplification is reduced from $\exp(O(\sqrt{n}))$ to $\exp(O(n^{1/3+c}))$, a significant theoretical improvement.
  • Optimality for Sorted Distributions: The paper proves that the PML distribution is an optimal estimator for the sorted distribution in the $\ell_1$ distance, achieving the information-theoretically optimal sample complexity for accuracy $\epsilon \gg n^{-1/3}$.
  • New Sorted Distribution Estimator: A novel estimator for sorted distributions is introduced, achieving optimal sample complexity and near-optimal concentration properties without sample splitting.
  • Better Approximation Theory Trade-offs: As a byproduct, the paper achieves improved trade-offs between polynomial approximation error and coefficient magnitudes in Poisson approximation of 1-Lipschitz functions.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, focusing on asymptotic guarantees and optimal rates. While the methods are general, empirical validation on real-world datasets would be valuable.
  • Computational Complexity: While the paper mentions that their estimator can be solved in polynomial time, the exact computational complexity of the proposed PML computation and the new sorted distribution estimator is not the primary focus. Further investigation into practical efficiency might be warranted.
  • Conjecture on Unified Methodologies: The authors conjecture that the $n^{-1/3}$ threshold might be a price for any unified methodology for symmetric property estimation. Proving this conjecture would further solidify the significance of their findings.
  • Generalization: The paper focuses on discrete distributions. Extending these techniques to continuous distributions or other statistical models could be a fruitful direction.

Summary updated

Abstract

A striking result of Acharya et al. [ADOS17] showed that to estimate symmetric properties of discrete distributions, plugging in the distribution that maximizes the likelihood of observed multiset of frequencies, also known as the profile maximum likelihood (PML) distribution, is competitive compared with any estimators regardless of the symmetric property. Specifically, given n observations from the discrete distribution, if some estimator incurs an error ∊ with probability at most δ, then plugging in the PML distribution incurs an error 2∊ with probability at most . In this paper, we strengthen the above result and show that using a careful chaining argument, the error probability can be reduced to δ1 – c · exp(c′n1/3 + c) for arbitrarily small constants c > 0 and some constant c′ > 0. The improved competitive analysis leads to the optimality of the PML plug-in approach for estimating various symmetric properties within higher accuracy ∊ ≫ n–1/3. In particular, we show that the PML distribution is an optimal estimator of the sorted distribution: it is ∊-close in sorted ℓ1 distance to the true distribution with support size k for any n = Ω(k/(∊2 log k)) and ∊ ≫ n–1/3, which are the information-theoretically optimal sample complexity and the largest error regime where the classical empirical distribution is sub-optimal, respectively. In order to strengthen the analysis of the PML, a key ingredient is to employ novel “continuity” properties of the PML distributions and construct a chain of suitable quantized PMLs, or “coverings”. We also construct a novel approximation-based estimator for the sorted distribution with a near-optimal concentration property without any sample splitting, where as a byproduct we obtain better trade-offs between the polynomial approximation error and the maximum magnitude of coefficients in the Poisson approximation of 1-Lipschitz functions.
BibTeX
@inproceedings{han2021competitive,
  author = {Yanjun Han and Kirankumar Shiragur},
  title = {{On the Competitive Analysis and High Accuracy Optimality of Profile Maximum Likelihood}},
  booktitle = {SODA},
  year = {2021},
  url = {https://openreview.net/forum?id=rARdUTWjo7},
}
Figure