2018/07/18 by Anindya De, De, Anindya, Philip M. Long +3
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Statistics Theory (math.ST) #cs.DS #cs.LG #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.1807.07013
Conference version in FOCS'18; Journal version to appear in JMLR
arxiv created 2020/11/12 · arxiv updated 2020/11/13
We study the learnability of sums of independent integer random variables given a bound on the size of the union of their supports. For A ⊂ Z+, a sum of independent random variables with collective support A (called an A-sum in this paper) is a distribution S = X1 + ⋯ + XN where the Xi's are mutually independent (but not necessarily identically distributed) integer random variables with ∪i supp(Xi) ⊆ A. We give two main algorithmic results for learning such distributions: 1. For the case | A | = 3, we give an algorithm for learning A-sums to accuracy ε that uses poly(1/ε) samples and runs in time poly(1/ε), independent of N and of the elements of A. 2. For an arbitrary constant k ≥ 4, if A = \ a1,...,ak\ with 0 ≤ a1 < ... < ak, we give an algorithm that uses poly(1/ε) ⋅ log log ak samples (independent of N) and runs in time poly(1/ε, log ak). We prove an essentially matching lower bound: if |A| = 4, then any algorithm must use Ω(log log a4) samples even for learning to constant accuracy. We also give similar-in-spirit (but quantitatively very different) algorithmic results, and essentially matching lower bounds, for the case in which A is not known to the learner.