Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables
Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables
复制标题
独立整数随机变量之和的近乎最优学习和稀疏覆盖
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Alistair Stewart
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;D. Kane;Alistair Stewart
对于k∈Z+，n阶∈Z+的k-SIIRV是{0，1，…，k−1}上n个相互独立的随机变量之和的离散概率分布。本文证明了两个主要结果：·在全变差距离(L1距离)下，我们给出了一个从独立样本中学习k个SIIRV的最优算法。我们的算法使用e
For k ∈ Z+, a k-SIIRV of order n ∈ Z+ is the discrete probability distribution of the sum of n mutually independent random variables each supported on {0,1,...,k −1}. We denote by Sn,k the set of all k-SIIRV’s of order n. In this paper we prove two main results: • We give a near-sample optimal and computationally efficient algorithm f or learning kSIIRVs from independent samples under the total variation distance (L1 distance). Our algorithm uses e