English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of covering and learning sums $X = X_1 + \cdots + X_n$of independent integer-valued random variables $X_i$ (SIIRVs) with unbounded,or even infinite, support. De et al. at FOCS 2018, showed that the maximumvalue of the collective support of $X_i$'s necessarily appears in the samplecomplexity of learning $X$. In this work, we address two questions: (i) Arethere general families of SIIRVs with unbounded support that can be learnedwith sample complexity independent of both $n$ and the maximal element of thesupport? (ii) Are there general families of SIIRVs with unbounded support thatadmit proper sparse covers in total variation distance? As for question (i), weprovide a set of simple conditions that allow the unbounded SIIRV to be learnedwith complexity $\text{poly}(1/\epsilon)$ bypassing the aforementioned lowerbound. We further address question (ii) in the general setting where eachvariable $X_i$ has unimodal probability mass function and is a different memberof some, possibly multi-parameter, exponential family $\mathcal{E}$ thatsatisfies some structural properties. These properties allow $\mathcal{E}$ tocontain heavy tailed and non log-concave distributions. Moreover, we show thatfor every $\epsilon > 0$, and every $k$-parameter family $\mathcal{E}$ thatsatisfies some structural assumptions, there exists an algorithm with$\tilde{O}(k) \cdot \text{poly}(1/\epsilon)$ samples that learns a sum of $n$arbitrary members of $\mathcal{E}$ within $\epsilon$ in TV distance. The outputof the learning algorithm is also a sum of random variables whose distributionlies in the family $\mathcal{E}$. En route, we prove that any discrete unimodalexponential family with bounded constant-degree central moments can beapproximated by the family corresponding to a bounded subset of the initial(unbounded) parameter space.

Learning and Covering Sums of Independent Random Variables with Unbounded Support