论文标题
自适应财产估计的高精度限制
On the High Accuracy Limitation of Adaptive Property Estimation
论文作者
论文摘要
近年来，自适应（或统一）方法在估计离散分布的对称属性方面取得了成功，其中首先获得了独立于目标属性的分布估计量，然后将估算器插入目标属性中作为最终估计器。已经提出了几种这样的方法并被证明是适应性的最佳选择，即它们在低精度内实现了大量属性的最佳样品复杂性，尤其是对于大估计误差$ \ varepsilon \ gg gg n^{ - 1/3} $，其中$ n $是样本量。 在本文中，我们表征了所有此类方法的高精度限制或适应性的惩罚。具体而言，我们表明，在一个温和的假设下，分布估计器接近预期的真实分配分布，任何自适应方法都无法在精确度$ \ varepsilon \ ll n^{ - 1/3} $中获得每$ 1 $ -Lipschitz属性的最佳样品复杂性。特别是，这一结果反驳了[Acharya等人的猜想。 [2017年]，在所有$ \ varepsilon $的范围内，最大可能性（PML）插件方法是最佳的，并确认[Han and Shiragur，2021]中的猜想是他们对PML的竞争性分析很紧。
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 $\varepsilon\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 $\varepsilon \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 $\varepsilon$, and confirms a conjecture in [Han and Shiragur, 2021] that their competitive analysis of the PML is tight.
