Efficient profile maximum likelihood for universal symmetric property estimation
Efficient profile maximum likelihood for universal symmetric property estimation
复制标题
通用对称属性估计的有效轮廓最大似然
DOI：
10.1145/3313276.3316398
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Sidford, Aaron
中科院分区：
文献类型：
--
作者：
Charikar, Moses;Shiragur, Kirankumar;Sidford, Aaron
估计分布的对称属性，例如支持大小、覆盖范围、熵、均匀距离，是算法统计中最基本的问题之一。虽然这些特性已经得到了广泛的研究，并且已经产生了单独的最优估计器，但在最近的惊人工作中，Acharya等人提供了一个对每个估计器都具有竞争力的单一估计器。他们表明，分布上近似最大化轮廓似然（PML）的属性值，即频率的观测频率的概率，相对于广泛的估计器是样本竞争的。不幸的是，在此工作之前，没有已知的多项式时间算法来计算这样的近似值或使用PML来获得通用插件估计器。在本文中，我们提供了一种算法，该算法从一个分布中给定样本，在近线性时间内计算一个近似的PML分布，其乘法误差为exp（n2/3polylog(n)）。推广Acharya等人的工作，我们表明我们的算法产生了一个通用的插件估计器，可以与广泛的估计器竞争，精度可达n = Ω（n−0.166）。此外，我们提供了有效的多项式时间算法，用于计算PML的ad维泛化（对于constant），该算法允许对分布之间的对称关系进行通用插件估计。
Estimating symmetric properties of a distribution, e.g. support size, coverage, entropy, distance to uniformity, are among the most fundamental problems in algorithmic statistics. While these properties have been studied extensively and separate optimal estimators have been produced, in striking recent work Acharya et al. provided a single estimator that is competitive for each. They showed that the value of the property on the distribution that approximately maximizesprofile likelihood (PML), i.e. the probability of observed frequency of frequencies, is sample competitive with respect to a broad class of estimators. Unfortunately, prior to this work, there was no known polynomial time algorithm to compute such an approximation or use PML to obtain a universal plug-in estimator.In this paper we provide an algorithm that, givennsamples from a distribution, computes an approximate PML distribution up to a multiplicative error of exp(n2/3polylog(n)) in nearly linear time. Generalizing work of Acharya et al. we show that our algorithm yields a universal plug-in estimator that is competitive with a broad range of estimators up to accuracy є = Ω(n−0.166). Further, we provide efficient polynomial-time algorithms for computing ad-dimensional generalization of PML (for constantd) that allows for universal plug-in estimation of symmetric relationships between distributions.
登录
查看更多内容
DOI：
10.1073/pnas.1607774113
发表时间：
2016-11-22
影响因子：
11.1
作者：
Orlitsky, Alon;Suresh, Ananda Theertha;Wu, Yihong
通讯作者：
Wu, Yihong
DOI：
10.1214/19-aos1927
发表时间：
2017-11
期刊：
ArXiv
影响因子：
--
作者：
Yanjun Han;Jiantao Jiao;T. Weissman;Yihong Wu
通讯作者：
Yanjun Han;Jiantao Jiao;T. Weissman;Yihong Wu
大字母分布之间 KL 散度的估计
DOI：
10.1109/isit.2016.7541473
发表时间：
2016
期刊：
2016 IEEE International Symposium on Information Theory (ISIT)
影响因子：
--
作者：
Yuheng Bu;Shaofeng Zou;Yingbin Liang;V. Veeravalli
通讯作者：
V. Veeravalli
不同元素问题的样本复杂度
DOI：
10.4171/msl/1-1-2
发表时间：
2018
期刊：
Mathematical Statistics and Learning
影响因子：
--
作者：
Wu, Yihong;Yang, Pengkun
通讯作者：
Yang, Pengkun
DOI：
10.1109/ita.2014.6804280
发表时间：
2014-04
期刊：
2014 Information Theory and Applications Workshop (ITA)
影响因子：
--
作者：
P. Vontobel
通讯作者：
P. Vontobel