Learning and Covering Sums of Independent Random Variables with Unbounded Support
Authors: Alkis Kalavasis
Konstantinos Stavropoulos
Manolis Zampetakis
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distribution Learning
Sums of Independent Random Variables
Covering
Density Estimation

Abstract: 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 infinite support. De et al. at FOCS 2018, showed that even when the collective support of $X_i$'s is of size $4$, the maximum value of the support necessarily appears in the sample complexity of learning $X$. In this work, we address two questions: (i) Are there general families of SIIRVs with infinite 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 infinite support that admit proper sparse covers in total variation distance? As for question (i), we provide a set of simple conditions that allow the infinitely supported SIIRV to be learned with complexity $ \text{poly}(1/\epsilon)$ bypassing the aforementioned lower bound. We further address question (ii) in the general setting where each variable $X_i$ has unimodal probability mass function and is a different member of some, possibly multi-parameter, exponential family $\mathcal{E}$ that satisfies some structural properties. These properties allow $\mathcal{E}$ to contain heavy tailed and non log-concave distributions. Moreover, we show that for every $\epsilon > 0$, and every $k$-parameter family $\mathcal{E}$ that satisfies some structural assumptions, there exists an algorithm with $\widetilde{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 output of the learning algorithm is also a sum of random variables within the family $\mathcal{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.

Learning and Covering Sums of Independent Random Variables with Unbounded Support
Alkis Kalavasis National Technical University of Athens
Konstantinos Stavropoulos
The University of Texas at Austin kstavrop@utexas.cek
xalavasiisllkismmall. ntua.
Manolis Zampetakis University of California, Berkeley mzampet@berkeley. edu
Abstract
+.... Xn of in- dependent integer- valued random variables X₁ (SIRVss) with infinite support. De ct al. [2018) at FOCS 2018, showed that even when the collective support of X, Is of size 4, the maximum value of the support necessarily appears in the sample complexity of learning X. In this work, we address two questions: (i) Are there general families of SIRRVs with infinite support that be learned with sample complexity independent of both n and the maximal element of the support? (ii) Are there general families of SIIRVs with infinite support that admit proper sparse covers in total variation distance? As for question (i), we provide a set of simple conditions that allow the infinitely supported SIRV to be learned with complexity (10)( bypassing the aforementioned lower bound. We further address ques- tion (ii) the general setting where each variable X, has unimodal probability mass function and is different member of some, possibly mulli-parammttr, expo- nential family & that satisfies some structural properties. These properties allow E to contain heavy tailed and non log-concave distributions. Moreover, we show that for every e 0, and every k- k-parameter family E that satisfies some structural assumptions, there exists an algorithm with poly(1/e) samples that learns a sum of arbitrary members of & within in TV distance. The output of the Iearn- ing algorithm is also a sum of random variables within the family 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.
We study the problem of covering and learning sums X
1 Introduction
In this paper, we revisit the problem of learning distributions the form X = X1 +... + Xn, where N and the terms X; are independent integer random variables. We focus on the cases where each X, has unbounded, even infinite support. Our work follows the literature
learning
distributions from independent samples (see e.g., [Dasguptal 1999, Rabani et al., 2014 Acharya jet al. 2015 Canonne 2013 2020 Diakonikolas et al. 2019 Moitra and Valiant 2010]. that has been introduced in Kearns et al. 1994]. In this problem,
observe independent samples from
random variable X, which is a priori known to belong to class of distributions C, and the goal is to compute another random variable X' such that drv X') S The main question ask follows: Given C, how many samples from X do we need to compute the estimate X If the output X' belongs C, we say that we have properly learned X.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The problem of learning distributions is closely related to the problem of sparsely covering class of distributions. Given a class C' of distributions, an e-cover for this class a C2 of distributions such that, for every D E C. there exists a D' E Ce such that drv (D, D') S 6. If C. S C, then C. called a proper cover. Clearly, the existence of a (small) cover for a class C is interesting by its own. Furthermore, once we have designed a cover C.,, then there exist generic algorithms, e.g., the tournament procedure [Daskalakis and Kamath 2014), that uses C. to produce a learning algorithm with sample complexity (loog(C.)))e and running time Ó
A fundamental problem in distribution learning arises when the elements of the class C can be ex- pressed as sum X = X1 + + X, of n E N independent but not identical random variables (SIIRVs). This problem has been extensively studied in the Theoretical Computer Science literature in the last decade. The seminal work of Daakalakiss and Papadimitriou [0155). Daskalakis et al. et al. [2016a] settled the fundamental problem of covering and learning sums
[2015a], Diakonikolas 2015a,,,iakonikolaa X of independent but not identical Bernoulli random variables, where they prove the surprising result that the number of samples needed for learning the random variable X in this case is indepen- dent of n and almost the same as the number of samples needed to learn a single Bernoulli random variable. Subsequently, Daskalakis et al. 2013). Diakonikolas et al. [2016b] solved the problem of learning sums of integer random variables with support from 0 to m 1 and otherwise follow arbi- trary distribution using (mm/²)) samples (again independent of n). Follow-up works have also con- sidered multidimensional distributions again with bounded support size [Daskalakis et al. 2015b 2016 Diakonikolas et al., 2016c]. This line of work has found applications in Game Theory for computing equilibrium anonymous games [Daskalakis al.) 2016 Diakonikolas al.) 2016c]
Goldberg and Turchetta| [017 Cheng et al. [017]. in Mechanism Design for designing auctions [Goldberg and Tang 2015]. and Stochastic Optimization (De 2018). Crucially, such applications make use of the delicate structure of such sums (reflected in proper sparse covers) and are not nec-
essarily implied by the learning results. In fact, learning SIRVSs could also be seen as a fundamental (and not trivial) application of the corresponding covering results.
All the previous work in this literature considered learning sums of random variables whose sup- port is bounded in size and the maximum elements in the support are also bounded. In particular, Daskalakis et al. 2013) observed that if the support of the terms is unbounded, then the sample complexity of learning the distribution of the sum will depend on the number of terms in the worst case, even under the assumption that the terms have bounded moments. Moreover, the recent work of et al. (2018) showed that, even when the size of the support is 4, there should be a dependence of sample complexity on the maximum value of their support in general. both in Game Theory and in Stochastic Optimization, it is natural to encounter random variables with large or even infinite support. In these cases, any algorithm whose sample or time complexity depends the support size or the maximum value of the random variable can be very inefficient or even useless. The above discussion gives rise to our first challenge:
many settings though,
Challenge 1 (Infinite Support). When is possible learn SIRVss with infinite support with number of samples independent of n and the maximun element of the support?
Note that, in our setting, the bounds of De et al. 2018 are only interesting from a qualitative per- spective, since they focus on the (very weak) dependence of the sample complexity on the maximum value of the collective support (for which they provide tight bounds), but they enable doubly expo- nential dependence on the size of the collective support in their upper bounds.
Proper sparse covering (and hence proper learning due to the covering method), is quite delicate requirement: To the best of our knowledge, the only known results for properly covering sums of independent univariate random variables, apply to the class of Poisson Binomial distributions (Daskalakis and Papadimitriou (2015). Diakonikolas et al. (2016c]) and the class of m-SIIVVs s (each summand is supported on O to m 1) (Diakonikolas et al. (2016a). ). This is the second challenge:
Challenge 2 (Proper Covers). Are there general families of SIRVVs with infinite support that admit proper sparse covers in total variation distance?
1.1 Our Contribution
We initiate the study of SIRVVs with unbounded and even infinite support (SHURVVs). There are two aspects of our work. First, we overcome the aforementioned lower bounds with an appropriate set of simple assumptions Under our assumptions, we prove that the sample complexity of the

---

learning problem is independent from the number of terms, giving an answer to Challenge I (see Section 2 Our result is important from a theoretical perspective, since in the distribution learning setting there is a lack of tight combinatorial characterization of the sample complexity, unlike, for example, the case of binary classification. The standard upper bound, metric entropy, includes, in our case, a dependence on the number of terms. Second, we give an answer to Challenge 2 (and then to Challenge|] [T by properly covering (and then learning) SIRVss with structured distributions. In particular, we focus on SIIRVs where each term is member of given exponential family of distributions E, which we call E-SIRRVs or SHIERVs. The exponential family paradigm is a multi- parametrie, extremely expressive framework that captures many interesting families of distributions. Our results identify delicate structural properties for quite broader class of random variables than what has been previously known and, importantly, demonstrate that the size of the support is not an utter impediment in acquiring such delicate results. We present our result on SHERVV in Section 3
Results for SHERRV. Our main results concern the family E-SHIVV of X = x1 +... Xa. Fach X; a member of an exponential family of distributions &, that the probability mass function of X; 2 is proportional to the quantity exp(-a: Tz))), where T 2 + ER is the vector
at the point of sufficient statistics of and a; is the vector of parameters of X; that belongs to the parameter space A S IR* of E. So in our setting, for every X; the sufficient statistics T are the same but the parameter vector a; is different for every i. The sum X will be called an ( of order n.
Informal Assumptions 1 (Assumption 2). Assume that there exist constants L, 7, A > 0 so that the exponential family & = (r() is well-defined and:
1. (Geometry) A is closed. path-connected and its conical hull is a polyhedral cone.
2. (Modes) Every distribution in & is unimodal and the modes lie in [-L, L).
3. (Bounded Moment) Every distribution in & has fourth central moment at most B.
4. (Variance) The variance of each distribution in & is lower bounded by 7.
5. (Covariance) For any a in the convex hull of A, it holds Cova(T(W)) 3 A Ix-
For discussion on the minimality of our assumptions, we refer to Sections 2 and 3 In the next results, the set A' is a superset of A C IR* (see the discussion after the statements).
7 for any > O, there exists a set of distributions C. that c-covers the family of (r(A)-SIIRVs of order n in total variation distance. The set C has size (n/e))(8) + poly(11) and each element of an Er (A')- SIRVV of order (n)).
Informal Theorem 1 (Weakly-Proper Covering Theorem 3). Under Assumption
Informal Theorem 2 (Learning Theorem 4). Under Assumption given m = k- Ō(1/e) samples from an unknown (A)) X of order n, there exists an algorithm that outputs X so that drv (x. S e with high probability. Moreover, X is an -A''))-SIIVV of order O(n).
Weakly-Proper Covering, We say that a cover is a weakly- SHRVVs of order n if its elements belong to the family of (AA'))SSIRRY with parameters in slightly larger set A' C I& and with possibly more than terms. In the rest of the paper, we mostly stick with the term proper for brevity (see also Appendix (.anndix(A...I)... We think of A as input to the problem, but we focus on the various challenges arising by the nature of this problem instead of possible adversarial selections of A.
cover for the family of (rA)-
and The covering result gives an answer to Challenge and the learning one provides an algorithm with sample complexity independent of n and the maximum element of the support (Challenge I In the above informal theorem, we have treated the relevant parameters of the exponential family E (e.g., B) as constants. If we also consider the accuracy to be constant, the learner runs in time n O(k), The assumptions about the central moments as well as the covariance matrix are standard. The assumption regarding the geometry of A is mild, technical assumption, that has, however, important technical implications. The variance lower bound is a substitute of particularly subtle and most probably not omnipotent - technical tools that can be used to discard low variance terms in special cases. Finally, the assumption about the modes provides the structure needed to apply the most powerful tool we possess to confront Challenge D quantitative versions of the Central Limit Theorem. Moreover, Challenge 2
restricts the flexibility we have in applying such a tool, which we believe to indicate that our assumption about modes is, in some sense, essential for our purposes.
3

---

Our Assumptions 1 do not exclude any reasonable exponential family and our methods capture (among others) Geometric, Bernoulli, Poisson, Zeta, Gamma, Gaussian, Laplacian distributions and interpolations thereof (see Appendix H. For instance, our results apply to sums with both Gaussian and Laplacian terms. In particular, the naturally occuring Zeta distributions (Zipf"s law (Chao and Zipi 1949)) are not log-concave and no non-trivial learning results are known on sums thereof, even without requiring proper learning.
Technical Contributions. For a more detailed discussion about our novel technical features, we refer to Sections 3.3 and 3.4 First, we provide a fundamental structural result about exponential families that satisfy our assumptions, by reducing the problem of properly sparsely covering an exponential family as such the standard problem of covering a bounded subset of E (for some k E N) in Euclidean distance. The main challenge, which familiar results about exponential families do not resolve, that the parameter space of the exponential family may be unbounded. We show that a bounded subset of the parameter space approximately generates any distribution in the family (Theorem 6). which we believe to be of independent interest. To this end, we identify an analogy between the geometry of exponential families and polyhedral theory; we essentially reduce proba- bilistic properties of exponential family distributions to geometric properties of polyhedral cones, for which we settle a novel result (Theorem 8). We also prove that for any distribution with pa- rameter vector that has a sufficiently large (yet bounded) norm, the number of important points of the support is bounded, which leads to the resolution of the main technical challenge. Secondly, provide a continuity argument which implies that for any E-SIRV X of order n, there exists some E-SIIRV Y which is the sum of i..dd random variables in the family & such that the distance between the expectation of X and the expectation of Y, as well as the distance hetween the variance of X and the variance of Y are bounded. This is important in order prevent our learning algorithm from running in time exponential to the number of terms n. Moreover, our proofs require meticulously selecting and handling tools from previous work, well as accounting for various technical details.
Limitations and Impact. Our results are of theoretical nature and we do not identify any direct potential negative societal impact.
2 Warm-Up: Structure and Learning of SHIRRVs
We show, as warm-up, that there exists set of assumptions under which learning in total variation distance the distribution of an unknown sum of (at most) independent random variables with possibly unbounded support can be done using number of independent samples that does not increase with n. particular, let 'D be family of distributions over Z. We consider sums of independent integer- valued random variables of order of the form X = Eie(eel X,, where n' S n, X; D; E D. We call X D-SIIRV (or SIIURV, i.e., sum of independent integer random variables with unbounded support) of order n.
Assumption 1. We make the following assumptions for the family of distributions D.
1. Every distribution in D is (la) unimodal and (1b) the mode is assigned probability at most equal to 1 1 for some constant 7 E (0, 1) (common for all distributions DiP
2. Every mode of any distribution 'D lies within a (common) interval of constant length L >>0 O.
3. The fourth central moment E [[W E[W]]*] of each distribution in D is upper bounded > 0 (uniformly for all distributions in D).
by a constant
Minimality of Assumption 1 Removing condition I (unimodality and bound on the mass as- signed on the mode) would activate lower bound on the sample complexity (Observation 1.3 from Daskalakis et al. (203)) that involves some dependence sample complexity independent from n. The terms considered in the lower bound all have zero as mode (essentially satisfying condition 2 in the case of multimodal distributions) and all of their moments are upper bounded by a sequence of values (stronger than condition 33. They are, however, not unimodal and they assign almost all of their mass to zero (condition I does not hold). Waiving condition 2 enables one to form a family which does not have a sparse cover, even when the sums
the number of terms nı; aim for
A unimodal distribution could have many consequent modes, each assigned equal amount of mass.

---

only have a single term. In particular, we can consider sequence of arbitrarily shifted Bernoulli distributions with parameter 1/2, each of which has a distance least equal to 1/2 from any other distribution of the sequence. Moreover, the aforementioned sequence does not violate conditions or g Finally, condition is important, since it rules out, for example, the case of containing all Geometric distributions (enabling probability of success arbitrarily close to 0). In this case, there is some constant e > 0 such that we may consider an infinite sequence of geometric distributions with diminishing success probabilities Pn. = 2- with pairwise statistical distance at least E. The degree of the moment we assume to be bounded is 4, which is useful in the dense case, to establish the rate of convergence of the sum to discretized Gaussian distribution; importantly, the degree is constant. We get the following result.
Theorem (Learning). Set n E NN and D some family of distributions satisfying Assumption 7 Let e, E (0, 1) and X be an unknown D-SIIRV of order n. There exists an algorithm (Figure 7 with the following properties: Given n, e, 6, L, B,y and sample access to X, the algorithm uses m 0 (22 log(1 ( + (polyy B, 1/,, 1/c) log(L)) samples from X and, in time poly(m, [,
outputs (succint description of a) distribution X with drv (x, (X,X) X) S c, with probability 1 8.
Theorem I is based on common technique used in problems related to SIIRVs, which uses quan- titative versions of the Central Limit Theorem (like Lemma 19 of Chen et al. (2010) to reduce the learning problem into two sub- problems; covering DD in total variation distance and estimating the variance and expectation of the unknown SIRVV.
Theorem 2 (Structure of SIIURVs). Set n E N and D some family of distributions satisfying Assumption 7 For any > O, and any D-SIIRV X of order n, there exists some Y such that drv (X, Y) S e and either (i) Y is a random variable among L candidates that are independent from the particular X (sparse form) or (ii) Y is discretized Gaussian random variable with E E[X] = B[Y] and Var(X) = Var(Y) (dense form).
Hence, the learner first rums two different learning procedures, corresponding the sparse and dense forms of Theorem 2 For the sparse case, runs a tournament over the possible candidates and in the dense one, it computes the parameters of the (potentially) nearby discretized Gaussian. From the two procedures, two hypotheses are obtained and finally hypothesis testing is performed in order select the correct one. Our focus on the Gaussian approximation is the reason why we assumed that condition (T) holds. In principle, there might be ways to relax Assumption [ learn SHURVS (independently from n) with different techniques, but we are particularly interested in using the Gaussian upproximation in the dense case (compare, e.g., with the approach of Daskalakis et al. (2013)) since it will be pivotal to our main technical and conceptual contribution outlined in the following section.
3 Structure and Proper Learning of SHEERVs
In the seminal work of Daskalakis and Papadimitriou 2015), it was shown that the class of Poisson Binomial Distributions (i.e., sums of independent indicator random variables) has a structure with similar properties as the one presented in Theorem 2 Crucially, however, their results had an addi- tional property. In both sparse and dense cases, the candidate distributions (i.e., the representatives of the class) were Poisson Binomial Distributions themselves (namely, the class admitted proper sparse covers). The result unlocked the possibility of proper learning for PBDs (see Daskalakis let al. (2]5aa,, Diakonikolas et al. (20 with sample complexity independent from the number of terms. Besides the result of Daskalakis and Papadimitriou (2015). to the best of our knowledge, there are no further known results for properly covering sums of integer-valued (univariate) random variables, with terms in some structured structured-parameeee parametric family of distributions
We provide significantly general results for the structure of sums of integer (and unbounded) random variables, under the condition that the terms belong in any fixed exponential family that satisfies a set of assumptions. Our results imply proper learning with sample complexity independent from the number of terms. We consider exponential families supported on the whole (unbounded) set of integer numbers, although our results could be extended to exponential families supported on some subset of Z, like No.
Diakonikolas et al. 20166a provide proper sparse covers for the class of m-SIIRVs; nevertheless, this family does not have the "structure" we focus this work since it is nonparametric.
5

---

3.1 Preliminaries and Definitions
Exponential Families. For E No. A C R and T 2 - R& we denote with (AA the exponential family with sufficient statistics T and parameter space A. If (r) for some a E A. then Pr(W = x & exp(-a T())) for any z E Z. We will use Pra = x] (similarly Ea [W] and Var (W) for expectation and variance correspondingly) to refer to the probability that W = x given that W ~ Er(a), whenever it is clear that the distribution of W belongs in ET()
SHIERVs. We will consider distributions of sums of the form X = [i X,, where n' n, (X+); independent and X; (r(a,) (a.) with a, A. We call this class of distributions E (A)-SIIVVs of order n or simply SIEERVs when n, A and T are clear by the context.
Set Operators. We say that Op is an extensive set operator on I& if for any set A C R we have that A S 0p.A C R We use the following extensive set operators: For the definitions of the convex hull Conv and the conical hull Cone operators, we refer to ( and (2). The g-conical hull operator g-Cone.A = A U (ConeA') \ B (0)), i.e.. the g-Cone operator inserts in A all points of the conical hull of A with norm least p. For additional notation, we refer the Appendix A.I A.I
3.2 Main results
Our results for (AA)S-IIIVS hold under the following set of assumptions about E (AA.
Assumption 2. Let k E N, T: Z + R and A C RR. Denote A, e-Cone and Ag ConvAg for e > We assume that there exists some constant @ > O so that the exponential family r (Ap) is well-defined and the following hold:
1. The parameter space A is closed and its conical hull Cone is a polyhedral cone.
2. Every distribution in (Agg is unimodal.
3. There exists some constant L >> O such that every mode of every distribution in (rp) lies within the interval [-L, L).
4. There exists some constant B > such that every distribution in (A₂)) has fourth central moment that is upper bounded by B, i.e., E. I E. [a[W]] S B, for any a Ag
5. There exists some constant such that Cov (T()) = A Lxs for any a E Ag
6. The parameter space A path-connected.
7. There exists some constant 7 >> 0 such that Var (W) 2 7, for any a E A.
correspond to conditions Assumption I but we make some additional ones. In particular, variants of assumption (5) have been used in the past (see Diakonikolas et al. [202]] )) e.g., for parameter estimation in exponential families and essentially ensure that parameter vectors close in Euclidean distance correspond to distributions close in statistical distance. Assumptions (6) and (7) are important only the case that the number of terms n in the sum is large. As- sumption (7) ensures that as the number of terms increases, the distribution approaches its limit (i.e., the discretized Gaussian distribution), with some constant rate. fact, the variance lower bound is substitute of particularly subtle but specialized technical tools that can be used to discard low variance terms some specific cases (e.g., see the so called massage step of Daskalakis and Papadimitriou 2015 which refers to Poisson Binomial Distributions and our own Appendix H.2 which refers to sums of independent geometric RVs, namely, Poisson Negative Binomial Distribu- tions). Finally, assumption (6) implies some kind of continuity with respect to the parameter vector which is important for proper learning so that the behavior of a sum of a large number of terms can be described by constant number of parameter vectors (in our case exactly one). For discussion on the verification of the assumptions, see Appendix H.4
Assumptions
'In general, an exponential family E over is also defined in terms of some carrier measure h E + IR. so that if W ~ E, then Pr(W æ) x h(x)) exp(-= (a a T(x)) and denote W ~ (a)). We can reduce this setting to A by considering A' = Ax x (1) and T' (T. log, (h(x))).

---

We stress that assumptions (2)(5) are imposed on a slightly expanded exponential family (by ex- tending the parameter space A Ag). ) In fact, our analysis involves the study of the influence that changes in the parameter vector have on the corresponding distribution, given some properties gen- erated by our assumptions. Extending the space on which such properties hold enables the study of a wider range of changes of the parameter vector. On the contrary, assumption 7 is imposed on A (and not its extended version). It essentially excludes some parameter vectors with large norms, but, in general, it does not imply that A is bounded. In general, A should be though of as the space of parameters for the input and Ag A) the space of parameters for the output.
Theorem 3 (Structure of SHERRVs). Set E NN and (A) some exponential family satisfying Assumption 2 Let Ag = g-ConeA. There exists some value 0 = ((A,T) > such that, for any E E (0, 1) and any (A)SS-IIIV X of order there exists some random variable Y such that drv (X, Y) S E and either (i) Y is an (A(A))-SIRV among ( p.)(,,,,), candi- dates (spurse form) or (ii) Y is sum of i.i.d. ET (r(())) variables among (1²² (oly(B, O ((eAA) 1)* candidates (dense form).
The role of the quantity 9 is thoroughly discussed in Appendix E. Roughly, the parameter space A and the trajectory of the sufficient statistics T(x), E Z are associated with finite number of polyhedral cones which are important parts of the structure of the family Er(A), The value of 0 depends on the geometry of the specified polyhedral cones.
The structural result implies a proper learning algorithm (Figure 2 which roughly applies the tour- nament method and hypothesis selection routines over the cover both in the sparse and (after an additional important step) in the dense case (see Proposition 25). For the learning result, we assume access to some sample and evaluation oracles (see Appendix B.2 Such access is needed in order to apply hypothesis testing over our covers in a formal sense. Let D be a distribution over Z. Consider the sample oracle EX(D) that, when invoked, returns sample with law D and the approximate evaluation oracle EVALp (3) that, when invoked with query x E Z, returns a value q that satisfies D1=)/(1 + B) S 9 S (1 + D(r))) for some B 0 (this oracle is used in De et al. (2014). Below, the relation between 3 and the desired learning accuracy é is provided by De et al.
2014]. Finally,
assume that the cover of Theorem 3 (the set of candidate distributions) of radius can be constructed in time To- = (A, n, L, B, A, 7,0, T) (see Remark for a discussion on the runtime).
Theorem 4 (Learning SIIERVs). Set n N and (A) some exponential family satisfying As-
sumption 2 Let Ag e-Cone There exists 0 = -(A,,) > O such that for any e, ó E (0, 1) there existy an algorithm (Figure 2 with the following properties: Given n, E, B, I,, A,,, 0 and
(i) sample access to an unknown ET(A) (A)) X of order n, (ü) EX(2(,,0') o2)) any p. 0² and (iii (D) and evaluation oracle access to EVALD (3) any D E ET (Ap) for some B 2 0 with (1 + 8)2 < 1 + c/8, the algorithm uses m = O log(1 + k -(1) poly(B, +) log( (*A) samples from X and, in time (mly(m. 2 2²-0(1/²)) (Bl((BB , (eA T2), outputs (succint description of a) distribution X which satisfies drv (X, X) c, with probability 1 - 8. Moreover, X is an (Ag) of order (vB) (B/7)) n.
In particular, for the dense case hypothesis, the learner runs in two steps. First, similarly to the learner of Theorem it estimates the expectation and the variance of X by Ö(1/e²) samples, thereby specifying discretized Gaussian that close to X. However, as a second step, it runs the tournament hypothesis testing procedure between the estimated Gaussian and the candidate
distributions of the dense form. Importantly, the tournament selection does not need to use real samples from X, but, instead, it generates draws from the Gaussian.
In the following sections, we analyze the structural result of Theorem 3 which is our main technical
contribution. In Appendix HH.2] we provide an example corollary of our methods for the case of Poisson Negative Binomial Distributions (Theorem 37).
3.3 Sparsifying the Parameter Space of an Exponential Family
We first solve the proper covering problem in the simplest possible case of n = 1, i.e., we provide sparse covers for any exponential family (T(A) satisfying (some of the assumptions in) Assumption 2 The following result constitutes the main building block of our analysis in the case of general n (see Section 3.4) The proof of this Theorem can be found at the Appendix
7

---

Theorem 5 (Sparsifying the Parameter Space), Under assumptions
2 13 and (5) there
exists 0- = 0(A, T) > O, so that for any e (0, 1), there exists B S e-Cone with [B| S (0 A + VA c0
AA log( so that, for any A. dTv &T(()) e, for some b E B.
+
The idea behind Theorem 5 has two parts. First, we show that, although our assumptions do not exclude the possibility that unbounded, there exists some bounded set A'' S A := &- A so that (AA') covers (A) in TV distance. Second, due to assumption (5) Lemmal 14 and Pinsker's inequality, we may discretize A' (with standard sparse covers in Euclidean distance) to get a sparse cover for &T (AA) (which will also be a proper sparse cover for &T (A)). In the rest of the current section, we will discuss about the main technical challenge, namely the proof of the first part of our idea, which is formally stated in the following theorem (for the proof, see Appendix E.I).
Theorem 6 (Bounding the Parameter Space). Under assumptions I 2 (3) and 4 there exists 0 (AA, T) 0, such that for any E E (0, and any a E A, there exists b E g-ConeA with |ba|| S (e + ( -I((1/e)+
+ ln(B)
29 + O })) so that (rr(Er(a),&r(()) S.
In order to bound the parameter space, one has analyze the behavior of a distribution Er(a) E Er (A) as the norm of the parameter vector increases (and its direction is fixed). Any point x E Z assigned by (r) mass proportional to exp(- a T(x)). Let Ma be the set of modes of {r)),, i.., the set of (global) maximizers of its probability mass function. Note that rescaling alter the positions of the modes, since the order of the quantities a (xx) (for x
does not E Z) is preserved. Moreover, as the norm of the parameter vector increases, the distribution (a) tends to become the uniform distribution over Ma.
It turns out, however, that the direction of a affects the rate with which (r(a) tends to its limit. Consider, for example, the case T(x) (z, x²) and as = r(1, 1 + 5), for some 8 and O. The distribution (r(as) has a unique mode on x = 0, but as 5 tends to 0. for any fixed r, the point x 1 tends to become a mode of (as)) Therefore, it possible that there exists some integer x such that for any fixed parameter vector norm 2 there are directions à in A so that (rā) assigns
mass arbitrarily close the mass it assigns to a mode. Bounding the parameter space is, hence, not straightforward, since there is no uniform (over the directions in A) threshold for the parameter vector's norm upon which every distribution close to its limit. In other words, orthogonally projecting the parameter vectors with large norms on any fixed radius sphere does not work. We, therefore, have to develop some further geometric intuition.
We claim that, under assumptions [ 2 3 and (4). there is a way to project (not necessarily orthogonally) any given parameter vector A with large norm on an origin-centered sphere with bounded radius so that the resulting distribution is close to E (a) in TV distance. We prove our claim in two steps. First, we prove our claim with respect to new notion of distance between distributions (instead of TVV distance), which we call structural distance. For this step, we establish an interesting connection between exponential families and polyhedral cones. Second, we prove that by picking the radius of the sphere on which we project to be large enough, the bounds in structural distance from the previous step imply bounds in total variation distance.
We proceed with a formal definition of the structural distance, which is a distance metric (Lemma 10 In nutshell, structural distance is the minimum possible relative threshold, such that two distributions agree (in relative terms) on every point of their domain with mass higher than the threshold (i.e., any significant point).
Definition 1 (Structural Distance). Consider two discrete distributions D2 over X and let P; = m Di(x), i = {1,2}. The structural distance (D, D2) between Dj and D2 is the minimum [0, 1] such that for any x E X, at least one of the following holds:
(z(x)) Se. & D2(x) S. P2, or (1i) (((e)/p=D((x))))
For any e E [0, 1], and any discrete distribution D over X. let D(s) denote the truncation of D on the points x such that D(x) 2 e max,cx D(y). Then, the structural distance between two distributions Dj and D2 can be described as the minimum threshold c [0, 1] so that the distributions D and D(e) are identical. In that sense, structural distance measures the degree in which two distributions have the same structure (on significant points). Two distributions with different modes have struc- tural distance (maximum possible). Structural distance is meaningful when the two distributions
8

---

(or one of them) can be contrived to have the same structure on significant points, which we prove to be possible in the context of exponential families. We prove the following lemma.
Lemma 7 (Structural Distance and Bounding Norms), Under assumptions ① 2 and 3 there
exists some constant 0 > O such that for any r 2 @ and any a E A with |a]| 2 there exists some
b E Ag and ||b]| so that (sT(Er(a), &T(b) S e 0-r
The proof of Lemma 7 can be found in Appendix ingredients of the proof. Let translate Definition in terms of the parameter vectors of exponential families. In particular, let a E A and b E Ag and Ma (resp. MM) be any mode of (a) (resp. Er (6)). Then d (Ez(a), Ey (b)) = means that for any E Z either (T(x) (Ma)) 2 (a
However, we will now outline the main
and b. (T(x) - ((M)) 2 (xr is not significant) or a (T T(Ma)) - b. is significant). Therefore, reducing the norm of without moving significantly in structural distance corresponds to a geometric problem regarding the parameter and the sufficient statistics vectors. In particular, given some a E AA with large norm, b should be chosen so that the quantities b v for E E and some sequence (U2)s of vectors that depends on a are constrained to be (i) equal to a a.v, when a 0z is small and (ii) large when a U2 is large. The number of constraints for b infinite, since x E 2. However, due to unimodality, one can show that only a finite number of them is crucial (the others can be trivially satisfied); we then make use of (Ag o g-Cone.A and) the following (to the best of our knowledge) novel theorem we prove about the geometry of polyhedral cones.
Theorem 8. Consider any polyhedral cone C S IR,, h E N, where C = fu= H u 2 0} for some matrix H E Rext,, I. E N is a description of C as an intersection of halfspaces. Then there exists some 0 > 0 such that for any u E C with [|u]| 2 L, there exists u' E C with ||''|| = so that for any column h of H at least one of the following is true:
(1) Either h.u 2 0 and h.u'
uu 2 0, (ii) h h-u- h.
The idea behind Theorem (see Appendix E.3) is to subtract from u a vector within the nullspace of the matrix Hf. where 1 is the set of indices of columns of such that h u is small. order to pick the correct vector, we use, additionally, a pivot vector w which satisfies h 2 0 for any interesting column of H. The vector which we subtract from u depends on the projections of u and w on the nullspace of Hf. We believe that Theorem 8 is of independent interest.
Structural Distance & TV Distance. The last step towards Theorem 6 is to show that Lemma can be transformed in terms of TV distance (see Appendix [E.]. We stress that structural distance is a local metric, since is defined in the terms of property that every point of the domain satisfies independently. while TV distance is a global metric since it expresses the total difference between two distributions over the whole domain. Therefore, the main technical complication here is that the support is infinite and it is not clear whether structural distance implies bounds for the TV distance. The complication resolved by the following lemma, whose general form (Lemma 35) is in fact also useful in other parts of the proof of Theorem 3a aadd states that when the parameter vector's norm is large enough, then almost all the mass lies within an bounded length interval around the mode. Its proof is based on the bounded central moments assumption (4)
Lemma 9 (Informal (See Lemma 35). Under assumptions ( and (4. there exists some natu- ral number l O(v such that for any E e-ConeA and any mode Ma of ET(a) we have Pra IW - MMll > f S exp(-[|all/e) O(1).
3.4 Sparsifying SHIERVs
We now consider distributions of the form X = Eiejy X,, where n' S n, (X1), independent and X; ~ (aa) for E A. When ní' is small, then the distribution can be approximated term by term, by setting e of Theorem 5 eqqual to e/n', since the total error of approximation is at most equal to the sum of the errors for each term. When n' is large, the distribution of X resembles the distribution of discretized Gaussian random variable, due to the Berry-Esseeet type bound of Lemma 19 Assumption (7) ensures that the variance of X will be large enough, but also that the shift distance (i.e., drv (X, X + 1)) will be small enough. In particular, for unimodal distributions, the shift distance of single term equals the mass assigned to the mode. Using more general version of Lemma | (see Lemma 355. we show that the variance lower bound implies an upper bound for the mass on the mode.
9

---

We only need to account for the case of large n' and, in fact, find some critical value regit N with respect to which sparse and dense cases are split. In the dense case, the distribution of X can be represented by its mean and variance alone. The goal is, therefore, to find some SUEERV Y that is also close to a discretized Gaussian and E [ E[Y] and Var(X) R Var(Y). We prove in Lemma 36 that (under assumptions ( and
(W) and Ea [W] are continuous functions of a on A (and by assumption @ A is path connected). Therefore, one might hope that, although E[ is sum of many different quantities of the form Ea, [ with a, E A (and simi- larly Var(X), due to independence), continuity implies the existence a single parameter vector b in A which expresses the total behavior of the quantities Var(X) and E| E[X]. It turns out that the correct way to define is as the parameter vector for which Var(X) / = Varo Ep [W]. The reason ratios are used is to eliminate the influence of the number of terms n' (which the pa- rameter vector has no influence on). The idea is to use some kind of intermediate value theorem to prove the existence of b, motivated by the fact that in the case E[X.]
O for any í E [n']. then / E[X] E [min,g(w] Var (x.) E X.) max Var X:)/ E[X,]]- However, there needs to be a careful handling for the cases that E[X, = 0 or E[X,] < 0 for some i E [n/]. The ran- dom variable Y is selected to be SUEER of order m [ / Eg [W]] consisting of i.dd terms (Y))e(m)) each following the distribution (b).
Finally, we observe that b A and Theorem can be used once again with accuracy e/m to discretize the parameter space and provide a sparse cover for the dense case.
Acknowledgments and Disclosure of Funding
We thank Dimitris Fotakis for useful discussions on various stages of this work. Alkis Kalavasis was supported by the Hellenic Foundation for Research and Innovation (H.F..I.)) under the "First Call for H.F.R.I. Research Projects to support Faculty members and Researchers and the procure- ment of high-cost research equipment grant", project BALSAM, HFRI-FM17-1424, Konstantinos Stavropoulos was supported by the NSF AI Institute for Foundations of Machine Learning (IFML) and by scholarship from Bodossaki Foundation. Manolis Zampetakis was supported by the Army Research Office (ARO) under contract W91 1-NN-17-1-0300 as part of the collaboration between US DOD, UK MOD and UK Engineering and Physical Research Council (EPSRC) under the Multidis- ciplinary University Research Initiative (MURI).
References
Anindya De, Philip M Long, and Rocco A Servedio. Learning sums of independent random vari- ables with sparse collective support. In FOCS, pages 297-308, 2018. uttp:tts::///ee jmlr. htts/pppperssvolmmm2////// 1-0---331188-881 531. pdf
Sanjoy Dasgupta. Learning mixtures of gaussians. In 40th Annual Symposium Foundations of Computer Science (Cat. No. 99CB37039), pages 634-644. IEEE, 1999.
Yuval Rabani, Leonard J Schulman, and Chaitanya Swamy. Learning mixtures of arbitrary dis- tributions over large discrete domains. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 207-224, 2014.
Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. In Proceedings of the 28th International Conference on Neural Information Processing Systems Volume 2, NIPS'15 15, page 3591 Cambridge, MA, USA, 2015. MIT
Press.
Clément L Canonne. Big data on the rise? In International Colloquium on Automata, Languages, and Programming, pages 294-305. Springer, 2015.
Clément L Canonne. A survey distribution testing: Your data is big, but is it blue? Theory of Computing, pages 1-100, 2020.
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742-866 2019.
10

---

Ankur Moitra and Gregory Valiant. Settling the polynomial learnability of mixtures of gaussians. In 2010 IEEE 51 Annual Symposium on Foundations of Computer Science, pages 93-102. IEEE, 2010.
Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert Schapire, and Linda Sellie. On the learnability of discrete distributions. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 273-282, 1994.
Constantinos Daskalakis and Gautam Kamath. Faster and sample near-optimal algorithms for proper learning mixtures of gaussians. In Conference on Learning Theory, pages 1183-1213. PMLR, 2014.
Constantinos Daskalakis and Christos Papadimitriou. Sparse covers for sums of indicators. Proba- bility Theory and Related Fields, 162(3-4):77--05,, 2015.
Constantinos Daskalakis, Ilias Diakonikolas, and Rocco Servedio. Learning poisson binomial distributions. Algorithmicu, 72(1):31-337, 2015a. URL http:p////aaxi..r///p/pp/.t 2702.
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Optimal learning via the fourier transform for sums of independent integer random variables. In Conference on Learning Theory, pages 831-849, 2016a.
Constantinos Daskalakis, Ilias Diakonikolas, Ryan ODonnell, Rocco A Servedio, and Li-Yang Tan. Learning sums of independent integer random variables. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 217-226. IEEE, 2013.
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart.
The fourier transform of poisson multi- nomial distributions and its algorithmic applications. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1060-1073, 2016b.
Constantinos Daskalakis, Gautam Kamath, and Christos Tzamos. On the structure, covering, and learning of poisson multinomial distributions. In 2015 IEEE 56th Annual Symposium on Founda- lions of Computer Science, pages 1203-1217. IEEE, 2015b.
Constantinos Daskalakis, Anindya De, Gautam Kamath, and Christos Tzamos. A size-free clt for poisson multinomials and its applications. In Proceedings of the forty-eighth annual ACM sym- posium on Theory of Computing, pages 1074-1086, 2016.
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Properly learning poisson binomial distri- butions in almost polynomial time. In Conference on Learning Theory, pages 850-878, 2016c.
Paul W Goldberg and Stefano Turchetta. Query complexity of approximate equilibria in anonymous games. Journal of Computer and System Sciences, 90:80-98, 2017.
Yu Cheng, Ilias Diakonikolas, and Alistair Stewart. Playing anonymous games using simple strate- gies. In Proceedings of the Twenty-Eighth Anmual ACM-SIAM Symposium Discrete Algo- rithms,, pages 616-631. SIAM, 2017.
Paul W Goldberg and Bo Tang. Auction design with revenue target. In International Symposium on Algorithmic Game Theory, pages 137-149. Springer, 2015.
Anindya De. Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium Discrete Algorithms, pages 1286-1305. SIAM, 2018.
Yuen Ren Chao and George Kingsley Zipf. Human behavior and the principle of least effort: An introduction to human ecology. Language, 26:394, 1949.
Louis HY Chen, Larry Goldstein, and Qi-Man Shao. Normal approximation by Stein's 's method. Springer Science & Business Media, 2010.

---

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, and Yuxin Sun. Outlier-robust learning of ising models under dobrushin's condition. Mikhail Belkin and Samory Kpotufe, edi- tors, Proceedings of Thirty Fourth Conference Learning Theory, volume 134 of Proceed- ings of Machine Learning Research, pages 1645-1682. PMIR, 15-19 Aug 2021. URL https: //proceedings. mlr hateesssvv34//iaaonnon 1ttml html
Anindya De, Ilias Diakonikolas, and Rocco A Servedio. Learning from satisfying assignments. In Proceedings of the twenty-sixth anmual
symposium on Discrete algorithms, pages SIAM, 2014. URL https://coreeeeeee wttpoo/lad///pp/////// / pdf
H. Minkowski. Geometrie der Zahlen (Erste Lieferung). Teubner, 1896.
H. Weyl. Elementare Theorie der konvexen Polyeder. Commentarii Mathematici Helvetici, page 7:290-306, 1935.
Yannis G Yatracos. Rates of convergence of minimum distance estimators and kolmogorov's en- tropy. The Annals of Statistics, pages 768-774, 1985.
Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Near-optimal- sample estimators for spherical gaussian mixtures. In Proceedings of the 27th International Con- ference on Neural Information Processing Systems- Volume 1, pages 1395-1403, 2014.
N. L. Johnson and C. A. Rogers. The Moment Problem for Unimodal Distributions. The Annals of Mathematical Statistics, 22(3):433 439, 1951. doi: 10.1214aoms/1117722999 URL https:
//doi.org/10. 11t.//11//////77999000000
AD Barbour. Asymptotic expansions in the poisson limit theorem. The Annals of Probability, pages 1987.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Challenges 2 and Section L.I
(b) Did you describe the limitations of your work? [Yes] Through specifying our as-
sumptions (see Assumption I and 2).
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See the final paragraph of the Introduction ("Limitations and Impact").
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tion and 2
(b) Did you include complete proofs of all theoretical results?
[Yes] See Appendices B
and
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi-
mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "lWvN8oDJ1om", "reviewer": "Reviewer_HJNQ", "summary": "This paper considers a specific problem in structured distribution learning, namely learning random variables that are expressed as sums of n integer-valued independent random variables (SIIRVs).  Previous work considered the setting of bounded support and bounded maximal support element. Interestingly, it was known that for unbounded support, the sample complexity includes dependence on n. Also, for bounded support of size 4, sample complexity includes dependence of maximal support element. This paper focuses on the infinite support case and finds assumptions on distributions such that the sample complexity is independent of n and the maximal support element. For the exponential family, under certain further assumptions, it shows that proper learning is possible.\n\nIn general, the learning algorithm is a hypothesis selection between two sets of candidate distributions, one that’s close when n is large (“dense form”) and the other that’s close when n is small (“sparse form”). The former is a discretized Gaussian with identical first and second moments and the latter is a cover of the family of distribution that each of the n random variables are drawn from. For proper learning, both the sparse and dense covers are mandated to also be in the specified exponential-SIIRVs. For the dense case in particular, the algorithm runs a tournament procedure with an estimated discretized Gaussian and a separate dense cover. Bulk of the later part of the paper focuses on showing that even when the parameter space of the exponential family is unbounded, sparse covers can be found. ", "questions": "My central question is in the section on strength and weaknesses. ", "limitations": "The authors have addressed limitations to my satisfaction. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Learning SIIRVs has received attention and found applications in Game Theory, Stochastic optimization etc. This paper takes a step towards understanding the problem in the infinite support case which is practically important. In my view, the paper’s key technical contribution is the structural result: i.e., to identify assumptions under which SIIRVs can be covered ‘properly’. As I explain below, because of the fact that this is a strength, it is also a weakness. Having said that, the assumptions certainly cover a wide-range of practical distributions. Other technical contributions involve identifying covers even when the parameter space is unbounded which was not obvious at first glance. \n\nThe paper is well presented and clear. My only minor complaint about the presentation is not motivating the proper learning requirement well in the introduction (Section 1). Some of the motivation comes in the start of Section 3 which would have been good to know in the introduction!\n\nWhile the authors somewhat justify some assumptions pointing to previous work and their necessity in their proofs, it would strengthen the paper if distributions were identified where all but one assumption fails to hold and the resultant sample complexity is shown to have some dependence on n. In other words, I wasn’t fully convinced that the assumptions that the paper proposes are minimal. Since the assumptions are in my view, the strength of the paper, some more explanation geared to showing that these are minimal would greatly strengthen the paper. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "S8ZNHHshWJP", "reviewer": "Reviewer_vvMx", "summary": "This paper studies the problem of learning a random variable X which can be written as the sum of n independent integer random variables X_1, ..., X_n (X is called a SIIRV). They mainly consider the question of learning X up to low total variation distance if the X_i's are \"sufficiently nice\" distributions. This paper's main contribution is to show that such learning can occur if the X_i's all satisfy some set of assumptions. The number of samples of sample variables X that are needed is quite low, having no dependence on the support size of the distribution (which could be unbounded), and almost no dependence on n, the number of independent variables that are summed to get X. Their techniques are based on covering arguments that demonstrate that there is a small but dense set of SIIRVs in the space of possible random variables X.", "questions": "My main question refers to the above, where I ask whether there are some important families of distributions that your methods can learn properly but previous methods were unable to learn. Alternatively, I would be interested in more understanding of how reasonable the assumptions in Assumption 1 and Assumption 2 are in real distributions.", "limitations": "Yes.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) This paper appears to be technically impressive, though it was very hard for me to judge as I am not an expert in this area.\n2) The authors also mention several applications of this learning problem - while I do not know about the importance of this problem, the stated applications seem reasonable.\n3) One concern I have with this problem is that there are a very large number of assumptions that need to be made about the exponential family. While many distributions satisfy these assumptions (Poisson, Bernoulli, Gaussian, etc.), there are probably much easier ways to learn sums of these random variables. (For instance, learning sums of Poissons is easy as it is just another Poisson.) So, it is unclear whether there are important families of distributions that this paper tackles but previous techniques were unable to tackle.\n4) Another concern I have is that this algorithm seems highly impractical. While the sample complexity is reasonable, the runtime is exponential and therefore probably wouldn't be as valuable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CK-v74CuKsL", "reviewer": "Reviewer_9A41", "summary": "This paper considers distributions of sums of independent, integer-valued random variables. The authors study both covering and learning the distributions arising from these sums. In contrast to prior work, the authors address the case where the random variables have infinite support. The results apply to sums of random variables sampled, where each random variable is sampled from an exponential family. The random variables appearing in the sum do not necessarily have the same distribution; rather, their parameters are assumed to come from a common parameter space. Under some assumptions on the parameter space, the authors give a covering guarantee. The covering result guarantees the existence of a set of distributions that cover the sum distribution, such that each covering distribution is drawn from an exponential family whose parameters appear in a slightly enlarged version of the original parameter space. The accompanying learning algorithm samples a random variable which is close in total variational distance to the summation distribution, and also corresponds to an enlargement of the exponential family parameter space.", "questions": "•\tDo your results give any implications for concentration of sums of independent random variables?\n\n•\tIt would have been nice to see example corollaries for certain types of random variables in the main text. \n\n•\tThe authors did a great job of motivating and justifying their assumptions. Are the assumptions easy to verify? It would be nice to give sample calculations, or examples of sufficient conditions. \n\n•\tTowards the question of proper learning, the authors show that SIIRVs can be nearly properly learned, by a limited expansion of the parameter space. It would be an interesting future direction to explore nearly proper learning in other contexts; perhaps comment on this.\n\n\n", "limitations": "Yes", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "•\tThis paper gives significant improvement over prior work, and is applicable to many common random variables.\n\n•\tThe writing an presentation are excellent. The problem is well-motivated, with a thorough description of prior work. The techniques are well-motivated and explained at a high level.\n\n•\tNeat techniques: structural results for exponential families, cones, and distribution distance (“structural distance”). Interestingly, the results show that even when the parameter space of an exponential family is unbounded, there is a bounded subspace that approximately generates any distribution in the family. The result is proven by relating probabilistic properties of exponential families to geometric properties of cones.\n\n•\tpg. 9: compilcation → complication\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept