On the High Accuracy Limitation of Adaptive Property Estimation

Abstract

Recent years have witnessed the success of adaptive (or unified) approaches in estimating symmetric properties of discrete distributions, where one 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 $\epsilon \gg n^{-1/3}$ where $n$ is the sample size. In this paper, we characterize the high accuracy limitation, or the penalty for adaptation, for all such approaches. Specifically, we show that under a mild assumption that the distribution estimator is close to the true sorted distribution in expectation, any adaptive approach cannot achieve the optimal sample complexity for every $1$-Lipschitz property within accuracy $\epsilon \ll n^{-1/3}$. In particular, this result disproves a conjecture in [Acharya et al. 2017] that the profile maximum likelihood (PML) plug-in approach is optimal in property estimation for all ranges of $\epsilon$, and confirms a conjecture in [Han and Shiragur, 2021] that their competitive analysis of the PML is tight.

References in corpus (9)

• Testing composite hypotheses, Hermite polynomials and optimal estimation of a nonsmooth functional
• Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance
• Estimating a probability mass function with unknown labels
• Maximum Likelihood Estimation for Learning Populations of Parameters
• Dualizing Le Cam's method for functional estimation, with applications to estimating the unseens
• Profile Entropy: A Fundamental Measure for the Learnability and Compressibility of Discrete Distributions
• A General Framework for Symmetric Property Estimation
• A constrained risk inequality for general losses
• Optimal Estimation of Change in a Population of Parameters

Cited by in corpus (1)

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