Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables
Ilias Diakonikolas, Daniel M. Kane, Alistair M. Stewart · 2015
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 for learning k-SIIRVs from independent samples under the total variation distance (L1 distance). Our algorithm uses Õ(k/2) samples and runs in Õ(k3/2) time. The sample size of our algo-rithm is optimal up to logarithmic factors, as Ω(k/2) samples are information-theoretically necessary to learn a single random variable supported on {0, 1,..., k − 1}. • We prove nearly tight bounds on the size of -covers for Sn,k under the total variation dis-tance. In particular, we show that for all k, n ∈ Z+ and ≤ 1/k, Sn,k admits an -cover of size n·(1/)O(k·log(1/)) that can be constructed in polynomial time. We also prove a nearly matching lower bound: For k ∈ Z+ and n = Ω(log(1/)) any -cover for Sn,k has size at least n · (1/)Ω(k·log(1/)). Using the structural understanding obtained from our construc-tion, we prove that the sample complexity of learning 2-SIIRVs is Ω((1/2) log(1/)). The unifying idea of our upper bounds is an analysis of the structure of the Fourier Transform of k-SIIRVs. Our learning algorithm relies on a structural property of the Fourier transform of k-SIIRVs, namely that it has small effective support. Our lower bounds employ a combination of geometric and analytic arguments.