Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.
2) 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.
3) 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.
4) 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.
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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: •	This paper gives significant improvement over prior work, and is applicable to many common random variables.

•	The 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.

•	Neat 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.

•	pg. 9: compilcation → complication

questions: •	Do your results give any implications for concentration of sums of independent random variables?

•	It would have been nice to see example corollaries for certain types of random variables in the main text. 

•	The 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. 

•	Towards 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.



limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

In 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. 
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. 

The 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!

While 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. 
questions: My central question is in the section on strength and weaknesses. 
limitations: The authors have addressed limitations to my satisfaction.
review_title: null

Meta-review: metareview: The authors address the fundamental problem of learning the sum of n independent random variables (not necessarily identically distributed). They concentrate on the setting where the variables have infinite support. In general, it's known that the sample complexity for this problem is not bounded, but they get around this barrier by making parametric assumptions on the distributions of the variables. 

The reviewers appreciated the strength of the results, and the authors engaged with them to dispel remaining questions. It is not exactly clear where an application of the results here would make a concrete impact; the authors hint in the rebuttal that understanding the "delicate structure" of sums of independent random variables is important in game theory and stochastic combinatorial optimization, but this is not made explicit. In any case, the theoretical contributions are solid enough to merit acceptance.
confidence: Certain
Decision: Accept