Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables

2015/05/04 by Ilias Diakonikolas, Daniel M. Kane, Diakonikolas, Ilias +3
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Correctness #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #FOS: Mathematics #Fast Fourier transform #Fourier transform #Information Theory (cs.IT) #Integer (computer science) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Mathematical analysis #Mathematics #Order (exchange) #Random variable #Statistics #Statistics Theory (math.ST) #Total variation #cs.DS #cs.IT #cs.LG #math.IT #math.ST #stat.TH

paper · pdf · doi:10.48550/arxiv.1505.00662

Main differences from v1: Changed title and restructured introduction. Added new sample optimal algorithm. Generalized sample lower bound for any value of k

openalex publication_date 2015/05/04 · arxiv created 2015/11/23 · arxiv updated 2015/11/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the structure and learnability of sums of independent integer random variables (SIIRVs). For k ∈ ℤ₊, a k-SIIRV of order n ∈ ℤ₊ is the probability distribution of the sum of n independent random variables each supported on \0, 1, …, k-1\. We denote by \cal S_n,k the set of all k-SIIRVs of order n. In this paper, we tightly characterize the sample and computational complexity of learning k-SIIRVs. More precisely, we design a computationally efficient algorithm that uses \widetildeO(k/ε²) samples, and learns an arbitrary k-SIIRV within error ε, in total variation distance. Moreover, we show that the \em optimal sample complexity of this learning problem is Θ((k/ε²)√(log(1/ε))). Our algorithm proceeds by learning the Fourier transform of the target k-SIIRV in its effective support. Its correctness relies on the \em approximate sparsity of the Fourier transform of k-SIIRVs -- a structural property that we establish, roughly stating that the Fourier transform of k-SIIRVs has small magnitude outside a small set. Along the way we prove several new structural results about k-SIIRVs. As one of our main structural contributions, we give an efficient algorithm to construct a sparse \em proper ε-cover for \cal S_n,k, in total variation distance. We also obtain a novel geometric characterization of the space of k-SIIRVs. Our characterization allows us to prove a tight lower bound on the size of ε-covers for \cal S_n,k, and is the key ingredient in our tight sample complexity lower bound. Our approach of exploiting the sparsity of the Fourier transform in distribution learning is general, and has recently found additional applications.

Citations

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
• Learnability and the Vapnik-Chervonenkis dimension
• Settling the Polynomial Learnability of Mixtures of Gaussians
• Polynomial Learning of Distribution Families

Related

• Learning and Covering Sums of Independent Random Variables with Unbounded Support
• Learning Sums of Independent Random Variables with Sparse Collective Support
• The Fourier Ratio and complexity of signals
• Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes
• Fundamental Limits of Learning High-dimensional Simplices in Noisy Regimes