We thank the reviewers for the valuable time they have invested during this difficult period to review the paper and

"The paper presents novel theoretical results that are highly relevant for the machine learning community" (Reviewer The results are impressive, non-trivial and interesting" (Reviewer 4). The remainder of this response mostly addresses suggestions and questions raised by Reviewers 1 and 3. Both Reviewers 1 and 3 ask us to elaborate on the differences between [JO19] and this paper. By contrast, this paper utilizes the distribution's structure, or even rough proximity to a structure, to identify a much Reviewer 1 writes, requires a "non-trivial" combination of VC theory and the filtering framework, allows us to remove Regarding Reviewer 1's specific question whether the technique also applies when the distributions underlying genuine We will add a similar explanation to the final version. This relation was explained in [JO19]. To enhance the reader's understanding of the context, in the final version of Please note that Section 3 of the paper starts by stating that "The current results extend several long lines of For the reader's benefit we will follow the reviewer's advice and We fully sympathize with the reviewer's desire to see more hard proofs in the We also note that Reviewer 4's response to question 2 seems We will try to accommodate Reviewer 1's request by including as much information Finally, Reviewer 3 asks about the time complexity of the paper's two efficient algorithms: learning piecewise Both algorithms have very reasonable complexities.