# Learning and Covering Sums of Independent Random Variables with Unbounded Support

arXiv: https://arxiv.org/abs/2210.13313 · HTML: https://mlsanity.com/paper/2210.13313/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 24 Oct 2022.

## Builds on (most cited first, 15 of 15)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Optimal Testing for Properties of Distributions](https://mlsanity.com/paper/1507.05952/) (2015)
- [Near-optimal-sample estimators for spherical Gaussian mixtures](https://mlsanity.com/paper/1402.4746/) (2014)
- [Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians](https://mlsanity.com/paper/1312.1054/) (2013)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [Properly Learning Poisson Binomial Distributions in Almost Polynomial Time](https://mlsanity.com/paper/1511.04066/) (2015)
- [Sparse Covers for Sums of Indicators](https://mlsanity.com/paper/1306.1265/) (2013)
- [The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications](https://mlsanity.com/paper/1511.03592/) (2015)
- [Query Complexity of Approximate Equilibria in Anonymous Games](https://mlsanity.com/paper/1412.6455/) (2014)
- [On the Structure, Covering, and Learning of Poisson Multinomial Distributions](https://mlsanity.com/paper/1504.08363/) (2015)
- [Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables](https://mlsanity.com/paper/1505.00662/) (2015)
- [A Size-Free CLT for Poisson Multinomials and its Applications](https://mlsanity.com/paper/1511.03641/) (2015)
- [Playing Anonymous Games using Simple Strategies](https://mlsanity.com/paper/1608.07336/) (2016)
- [Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack](https://mlsanity.com/paper/1712.00918/) (2017)
- [Learning Sums of Independent Random Variables with Sparse Collective Support](https://mlsanity.com/paper/1807.07013/) (2018)

## Built on by (most cited first, 2 of 2)

- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Transfer Learning Beyond Bounded Density Ratios](https://mlsanity.com/paper/2403.11963/) (2024)

## Abstract (arXiv)

We study the problem of covering and learning sums X = X1 + cdots + Xn of independent integer-valued random variables Xi (SIIRVs) with unbounded, or even infinite, support. De et al. at FOCS 2018, showed that the maximum value of the collective support of Xi'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 poly(1/ε) bypassing the aforementioned lower bound. We further address question (ii) in the general setting where each variable Xi has unimodal probability mass function and is a different member of some, possibly multi-parameter, exponential family E that satisfies some structural properties. These properties allow E to contain heavy tailed and non log-concave distributions. Moreover, we show that for every ε > 0, and every k-parameter family E that satisfies some structural assumptions, there exists an algorithm with tildeO(k) · poly(1/ε) samples that learns a sum of n arbitrary members of E within ε in TV distance. The output of the learning algorithm is also a sum of random variables whose distribution lies in the family 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.