论文标题
具有无限支持的独立随机变量的学习和覆盖总和
Learning and Covering Sums of Independent Random Variables with Unbounded Support
论文作者
论文摘要
我们研究覆盖和学习的问题$ x = x_1 + \ cdots + x_n $的独立整数值随机变量$ x_i $（siirvs），具有无限甚至无限的支持。 de等。在FOCS 2018上，表明$ x_i $的集体支持的最大值必然出现在学习$ x $的样本复杂性中。在这项工作中，我们解决了两个问题：（i）SIIRVS的一般家庭有无界的支持，可以通过$ n $和支持的最大元素进行样本复杂性学习吗？ （ii）是否有一般的SIIRV家族具有无界支撑的SIIRV家族，可以承认在总变化距离处的适当稀疏覆盖物？至于问题（i），我们提供了一组简单的条件，使无界的SIIRV以复杂性$ \ text {poly}（1/ε）$绕过上述下限。我们进一步解决了一个问题（ii）在总体环境中，每个变量$ x_i $都具有单峰概率质量函数，并且是某些（可能是多参数，指数族$ \ MATHCAL {e} $）的不同成员，可以满足某些结构属性。这些属性允许$ \ MATHCAL {E} $包含重型尾部和非log-concave发行版。此外，我们表明，每$ε> 0 $，以及每个满足某些结构性假设的每一个$ k $ - 参数$ \ Mathcal {e} $，都存在一个具有$ \ tilde {o}（o}（k）（k）\ cdot \ cdot \ cdot \ cdot \ text {poly}（poly}（1/ε）$ n $ n $ n $ n $ n $ n $ n的算法， $ε$在电视距离上。学习算法的输出也是随机变量的总和，其分布位于family $ \ Mathcal {e} $。在途中，我们证明，与对应于初始（无限）参数空间的有界子集的家族，都可以近似具有有界恒定中心矩的界定恒定中心矩的任何离散的单峰指数族。
We study the problem of covering and learning sums $X = X_1 + \cdots + X_n$ of independent integer-valued random variables $X_i$ (SIIRVs) with unbounded, or even infinite, support. De et al. at FOCS 2018, showed that the maximum value of the collective support of $X_i$'s necessarily appears in the sample complexity of learning $X$. In this work, we address two questions: (i) Are there general families of SIIRVs with unbounded support that can be learned with sample complexity independent of both $n$ and the maximal element of the support? (ii) Are there general families of SIIRVs with unbounded support that admit proper sparse covers in total variation distance? As for question (i), we provide a set of simple conditions that allow the unbounded SIIRV to be learned with complexity $\text{poly}(1/ε)$ bypassing the aforementioned lower bound. We further address question (ii) in the general setting where each variable $X_i$ has unimodal probability mass function and is a different member of some, possibly multi-parameter, exponential family $\mathcal{E}$ that satisfies some structural properties. These properties allow $\mathcal{E}$ to contain heavy tailed and non log-concave distributions. Moreover, we show that for every $ε> 0$, and every $k$-parameter family $\mathcal{E}$ that satisfies some structural assumptions, there exists an algorithm with $\tilde{O}(k) \cdot \text{poly}(1/ε)$ samples that learns a sum of $n$ arbitrary members of $\mathcal{E}$ within $ε$ in TV distance. The output of the learning algorithm is also a sum of random variables whose distribution lies in the family $\mathcal{E}$. En route, we prove that any discrete unimodal exponential family with bounded constant-degree central moments can be approximated by the family corresponding to a bounded subset of the initial (unbounded) parameter space.
