02bf86214e264535e3412283e817deaa-AuthorFeedback.pdf

We thank the reviewers for their insightful feedback, and we appreciate the opportunity to improve our paper. We would like to emphasize that Theorem 1 is the most important contribution of our paper due to its generality. In the Gaussian case, our sample complexity result follows directly from the expression for the optimal loss. Response to Reviewer 2: We thank the reviewer for pointing us to Dohmatob's "Generalized No Free Lunch Theorem Finally, while Dohmatob's bounds become non-trivial only when the adversarial We will also add a clearer description of the "translate and pair in place" coupling. Comparisons with Sinha et al. are in Section 7 and we compare to Dohmatob above.