On the High Accuracy Limitation of Adaptive Property Estimation

Yanjun Han

Research output: Contribution to journalConference articlepeer-review


Recent years have witnessed the success of adaptive (or unified) approaches in estimating symmetric properties of discrete distributions, where the learner first obtains a distribution estimator independent of the target property, and then plugs the estimator into the target property as the final estimator. Several such approaches have been proposed and proved to be adaptively optimal, i.e. they achieve the optimal sample complexity for a large class of properties within a low accuracy, especially for a large estimation error ε ≫ n−1/3 where n is the sample size. In this paper, we characterize the high accuracy limitation, or the penalty for adaptation, for general adaptive approaches. Specifically, we obtain the first known adaptation lower bound that under a mild condition, any adaptive approach cannot achieve the optimal sample complexity for every 1-Lipschitz property within accuracy ε ≪ n−1/3. In particular, this result disproves a conjecture in [Acharya et al., 2017a] that the profile maximum likelihood (PML) plug-in approach is optimal in property estimation for all ranges of ε, and confirms a conjecture in [Han and Shiragur, 2021] that their competitive analysis of the PML is tight.

Original languageEnglish (US)
Pages (from-to)910-918
Number of pages9
JournalProceedings of Machine Learning Research
StatePublished - 2021
Event24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021 - Virtual, Online, United States
Duration: Apr 13 2021Apr 15 2021

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'On the High Accuracy Limitation of Adaptive Property Estimation'. Together they form a unique fingerprint.

Cite this