Learning Sums of Independent Random Variables with Sparse Collective Support

MaRDI QIDQ6304369arXivFDO

Authors Anindya De, Philip M. Long, Rocco A. Servedio

Publication date 18 July 2018

Published in arXiv

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

arXiv classification

cs.DScs.LGmath.STstat.TH

Abstract: We study the learnability of sums of independent integer random variables given a bound on the size of the union of their supports. For $mathcalAsubsetmathbf{Z}_{+}$, a sum of independent random variables with collective support $mathcalA$} (called an $mathcalA$-sum in this paper) is a distribution $mathbfS=mathbf{X}_1+cdots+mathbf{X}_N$ where the $mathbf{X}_i$'s are mutually independent (but not necessarily identically distributed) integer random variables with $cu{p}_{i}mathsfsupp(mathbf{X}_i)subseteqmathcalA.$ We give two main algorithmic results for learning such distributions: 1. For the case $|mathcalA|=3$, we give an algorithm for learning $mathcalA$-sums to accuracy $epsilon$ that uses $mathsfpoly(1/epsilon)$ samples and runs in time $mathsfpoly(1/epsilon)$, independent of $N$ and of the elements of $mathcalA$. 2. For an arbitrary constant $kgeq4$, if $mathcalA=a_1,\mathrm{...},a_k$ with $0leq{a}_1<\mathrm{...}<a_k$, we give an algorithm that uses $mathsfpoly(1/epsilon)cdotloglog{a}_k$ samples (independent of $N$) and runs in time $mathsfpoly(1/epsilon,log{a}_k).$ We prove an essentially matching lower bound: if $|mathcalA|=4$, then any algorithm must use $Omega(loglog{a}_4)$ 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 $mathcalA$ is not known to the learner.

This page was built for publication: Learning Sums of Independent Random Variables with Sparse Collective Support

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6304369)