论文标题
关于竞争分析和高度最大可能性的最佳精度
On the Competitive Analysis and High Accuracy Optimality of Profile Maximum Likelihood
论文作者
论文摘要
[Acharya等人的惊人结果。 [2017]表明，要估计离散分布的对称特性，插入了最大化观察到的频率多频率的可能性（也称为剖面最大可能性（PML）分布）的可能性，与任何估计器相比，与任何对称性质相比，都具有竞争力。具体而言，给定从离散分布的$ n $观察值，如果某些估计器会产生错误$ \ varepsilon $，最多最多$δ$，然后插入PML分布会导致错误$ 2 \ varepsilon $带有概率，最多$δ\ cdot \ cdot \ cdot \ exp \ exp（3 \ \ sqrt {n} n}）$。在本文中，我们加强了上述结果并表明，使用仔细的链条参数，可以将误差概率降低到$δ^{1-c} \ cdot \ exp \ exp（c'n^{1/3+c}）$ for notimalissmissial small常数$ c> 0 $和一些常数$ c'> 0 $。特别是，我们表明PML分布是对排序分布的最佳估计器：它是$ \ varepsilon $ - 以$ \ ell_1 $ clus in true分布的距离$ n =ω（k/（k/（\ varepsilon^2 \ k））$ n = for $ k $，$ n = varepsilon^log k）$和$ \ varepsilon \ varepsil \ neformation最佳样本复杂性和最大的误差制度，其中经典的经验分布分别是优化的。 为了加强对PML的分析，关键要素是采用PML分布的新型“连续性”特性，并构建一条合适的量化PML或“覆盖率”链。我们还构建了一个基于近似浓度的分配分布的新型基于近似值的估计量，而没有任何样品分裂，作为副产品，我们在多项式近似误差和Poisson近似值的最大系数之间获得了更好的权衡。
A striking result of [Acharya et al. 2017] 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 $\varepsilon$ with probability at most $δ$, then plugging in the PML distribution incurs an error $2\varepsilon$ with probability at most $δ\cdot \exp(3\sqrt{n})$. 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}\cdot \exp(c'n^{1/3+c})$ for arbitrarily small constants $c>0$ and some constant $c'>0$. In particular, we show that the PML distribution is an optimal estimator of the sorted distribution: it is $\varepsilon$-close in sorted $\ell_1$ distance to the true distribution with support size $k$ for any $n=Ω(k/(\varepsilon^2 \log k))$ and $\varepsilon \gg 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.
