Summary
This paper studies the interaction between learnability and several notions of "robust" learnability, wherein candidate distributions can be corrupted in various ways. The authors show an equivalence between learnability and a robust version of learnability in which a contaminated distribution can be added to the nominal distribution. The authors study how differential privacy interacts with learning, showing that DP can imply learnability under certain contamination models, but not others. Sample compression schemes are also explored.
**Overall assessment.** This paper is strong on several fronts. It considers a wide selection of problems related to distribution learnability. And the technical quality of the paper is high. On the negative side, I think the biggest drawback is the writing. The clarity with which a paper like this is written is crucial, as the results are of a technical nature, thus requiring careful, clear explanations so that the reader can follow along. In its current form, I think this paper falls short of the mark. If the authors can demonstrably improve the writing and presentation, I will raise my score accordingly.
Strengths
**Breadth of settings.** This paper considers numerous problem settings spanning additive (and subtractive) contamination, differential privacy, learnability (in the sense of PAC learning), and sample compression. One imagines that the scope of this paper could have been reduced, i.e., to the interaction of DP and learnability, and the paper would still constitute a solid contribution. In an age when it can be advantageous to increase one's throughput by spreading content over multiple publications, I appreciated that the authors endeavored to give the reader the full picture capturing how learnability manifests on all of these different axes.
**Soundness.** From what I can tell, the paper is quite sound. The paper presents informal discussions and in some cases informal proofs in the main text. The appendix is fully rigorous, with each main result proved in its own subsection.
Weaknesses
**Motivation/Relevance to practice.** There is little to no motivation for the problem under consideration. The authors begin the introduction with a description of the problem of distribution learning without mentioning why one might be interested in this problem and/or what bearing this problem has on practical ML settings. It's certainly worth noting that this is a more theoretical paper, but even still, I think that the paper would be stronger -- and would appeal to a wider audience -- if the authors motivated the problem in a more verbose way. As written, this paper would only be accessible or feel relevant to those who are already familiar with why distribution learning is a well-studied problem, which is a narrow slice of the ML/statistics community.
**Definitions.** I found the definitions on the first few pages hard to parse. The three definitions contained in Def. 1.1 are all almost exactly the same; they each differ by at most a couple of words. I think it would make much more sense to condense this by using some sort of meta-definition, and then listing the three definitions as special cases. This also applies to Definition 1.4. In the case of Definition 1.4, the only difference relative to Def. 1.1 seems to be that the learning algorithm is randomized, which could surely be summarized in a more concise way.
Another related point is that the authors state the definitions with relatively little context. It would be help to illustrate each of these definitions with an example or a figure. As I mentioned earlier, the differences between each of these definitions is relatively subtle, and it's asking a lot from the reader to keep all seven definitions on pages 2-3 in their heads at once, along with the fine distinctions that separate them.
**Writing.** Much of the prose is notably spare in a way that makes the paper more challenging to read. Results (e.g., Theorem 2.1) are often without any preamble. It would be worth thinking about reorganizing the paper so that each result is accompanied by an intuitive explanation of the relevance of the result and how it fits into the broader context of the paper. While I like the attempt to informally present the theorems before offering a more rigorous treatment after Section 1, I don't think that it works here. This is in part because it asks the reader to consider each result at three levels of abstraction. First, the results are stated informally in Section 1. Then, in the remainder of the main text, the same results are stated formally, but the proofs are informal or sketched. Finally, the full treatment is given in the appendix. I think that asking the reader to jump around at these different levels of abstraction is, in this case, confusing. Perhaps the authors could shorten the intro and stick to the results as stated from Section 2 onwards?
Relatedly, the intro seems too long here. The reader has to wait until page 5 to learn what the authors feel the contributions are. This dilutes the standard linear flow of ideas that characterizes papers that are easy to follow. To make the paper easier to follow, I would recommend rewriting the introduction so that (a) the problem of distribution learning is well-motivated, (b) the main results are discussed, but not stated, and (c) the contributions are listed by -- at the very latest -- the end of the second page.
**How is this "robust?"** One question that jumped out to me was as follows: How are the definitions in Definition 1.1 "robust?" I.e., what are they robust against? The authors claim that the name "robust learnability" is due to the fact that they are accounting for the ground truth distribution $p$ may not be an element of the class $\mathcal{C}$. Would it not be more accurate to call these definitions "agnostic" rather than "robust?" I can see how one would regard the corruption-based definitions in Def. 1.2 and Def. 1.3 as robust, because the distribution $p$ is mixed with a corrupted distribution. However, in the sense of Definition 1.1, I don't understand the use of the word "robust."
**Miscellaneous.**
* It looks like a some points the authors write $(\alpha,\eta)-robustly learnable and $\alpha-\eta$-robustly learnable (c.f. Def. 1.1(3) vis-a-vis Def 1.4(3)). It seems like it would be good to pick on notation and stick with it.
* Why is the TV distance chosen here? The authors assert that this distance metric makes sense, but they give no argument, leaving the reader with some confusion.
* It would be worth adding a discussion section after the main results but before the conclusion. After reading through the results, it would be useful if the authors could piece them together in the broader context of distribution learnability. The authors could also discuss how these results could lead to future research on this problem, and/or whether this could lead to new algorithms that would be of practical use.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.