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: The paper presents novel bounds that hold for the DRO hypothesis. Interestingly, unlike ERM, uniform bounds are not required and for MMD-DRO the final bound depends only on the optimal hypothesis. Also, unlike local RA bounds, there is no dependence on few other hypothesis.

The bound follows from the key theorem3.1, which though is a simple observation, seems to be special to DRO and does not hold for ERM etc. The final bound for MMD-DRO is presented in theorem4.1. Again, though a simple derivation, is nevertheless interesting.

Apart from the main results, the paper presents other discussions on related bounds, and section 5, where a technical requirement in theorem 4.1 is dropped.

Finally, simulations supporting the theory are presented.
strengths_and_weaknesses: The paper is very well-written and is a pleasure to read. The result in theorem4.1 is indeed interesting as it has no dependence on any other hypothesis than the optimal.

The bounds also open up many interesting questions, while they explain why DRO performs well in practice. Though the work tries to answer some of them in section5,appD etc., the work would have been far more stronger with a deeper discussion of them. A couple of these questions I summarize in the subsequent section.

Overall, I feel the main strength of the work is the elegant bounds, while weakness is perhaps presentation of a bit fewer results than a good article would contain.
questions: 1. While the methodology proposed is general, details are given only for the MMD-DRO case. Another related case that has been shown to be promising is the Wasserstein-DRO case. Can this case be analysed in detail? Will it also lead to bounds dependent on f^* only? why/why not?

2. Distributional shift is another related case. Can Appendix D be expanded into a main section providing some insights?
limitations: Yes, insightful discussions are presented in sec4.2.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, authors present generalization bounds on the solution from distributionally robust optimization (DRO). In contrast to the hypothesis class complexity in ERM, DRO bounds presented depend on the ambiguity set geometry and its compatibility with the true loss function. They instantiate the DRO bound by using the maximum mean discrepancy DRO distance metric. Their analysis derives generalization bounds that depend solely on the true loss function, independent of any other candidates in the hypothesis class.
strengths_and_weaknesses: **Strengths**: 
- Author presents an alternate route avoiding dependency on the complexity class of the function to obtain generalization bounds on the solution from distributionally robust optimization. 
- A general DRO bound in Theorem 3.1 is provided before instantiating it in the MMD DRO framework. 

**Weakness**: 

- The main result in the paper is hard to parse, mainly because of a missing Problem setup section. It would be great if the authors can add a small section describing the notation and the setup very clearly. 
- In equation 8, what is the probability measure for the first term in RHS, i.e., what is the measure under which this probability is evaluated $\mathrm{P}(P \not \in \mathcal{K})$? 
- While the related work section covers papers on DRO, it misses discussion and references to some other papers where an alternative non-traditional approach has been explored in the context of deep learning[1,2,3]. The generalization bounds presented in these papers also don't directly depend on the complexity of the underlying hypothesis class. 
- Extension to MMD DRO is discussed. While the result is interesting and in specific situations tighter than the usual uniform convergence bound. However, the significance and practical relevance of this result are not clear to me. Specifically, it would be insightful to expand on the last sentence in abstract: "...we hope our findings can open the door for a better understanding of DRO, especially its benefits on loss minimization and other machine learning applications."
- Experimental details are missing. While authors redirect the reader to a reference [9] from their paper, authors are encouraged to add more details on the experiments. 
- (Minor) Conclusion section with a discussion on limitations and future work is missing. 
- Other minor issues or issues that hinder understanding: 
  - Theorem 3.1, line 173, What is the first word "DRO"? if it $f_DRO = ...$

[1] Jiang et al. 2021. Assessing Generalization of SGD via Disagreement https://arxiv.org/abs/2106.13799

[2] Garg et al. 2021. RATT: leveraging unlabeled data to guarantee generalization https://arxiv.org/abs/2105.00303

[3] Zhou et al. 2020.  On uniform convergence and low-norm interpolation learning. https://arxiv.org/abs/2006.05942
questions: See questions in the detailed weaknesses above. 
limitations: This work has no potential negative societal impact. However, no discussion on limitations or future work is provided. It would insightful if the authors could elaborate on this in the context of the last sentence in the abstract.
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: The authors present a DRO framework to derive generalization bounds, where the bounds crucially depend on the chosen ambiguity set, but not on the complexity of the hypothesis class, as opposed to existing ERM-type generalization bounds. The authors then exemplify the presented genearlization bounds for the maximum mean discrepancy (MMD) ambiguity set.
strengths_and_weaknesses: Strengths: I agree with the authors that most existing DRO works derive upper-confidence-type results where a data-driven decision f_data and a corresponding upper-confidence bound $J_{data}$ are generated with the corresponding statistical certificate $P[ E[\ell(f_{data},z)] <= J_{data} ]>= 1-\beta$. This work presents “true” generalization bounds quantifying the excess risk. Therefore, this approach clearly is novel and of high interested to a learning community.

Weaknesses: I think in the presented framework, there could me more properties being explored. For example, can you derive explicit generalization bounds for ambiguity sets other than MMD, e.g., f-divergence balls, moment-ambiguity sets? Moreover, how would a decision maker decide which ambiguity set to choose?


Post-Revision Comment:
I would like to thank the authors for the careful revision and for providing convincing explanations to all my questions. I will raise my rating to 7 and recommend acceptance of this paper. 
questions: 1) In Theorem 4.1, how can you practically verify the assumption \|\ell(f^*,.)\|_H \leq M? Since you don’t know f^*, I guess you require a uniform bound of the form \sup_{f\in H} \ell(f,.)? How would you practically estimate M?
2) Do you have any idea how tight the bound in Theorem 4.1 is? Do there exist lower bounds?
3) Let us assume to be in the setting of Theorem 5.1. How do you compute f^*_DRO? Is there a tractable reformulation? Is that similar to [18]?

In general the paper is well written and easy to follow. I just have the following (minor) suggestions to improve the presentation:
1) I don’t see the benefit of introducing the non-standard notation of P\ell(f,.) for E_P[\ell(f,z)]. I find this notation mathematically imprecise (since P is a probability measure and therefore cannot act on functions, unless you overload notation. Moreover, I find this notation confusing and would prefer to use the expected value notation.
2) Please correct the following typos:
- line 121, “bals
- line 290, “supremum
3) As you mention distributional shifts in transfer learning, there is a recent DRO-related work on that topic you might want to compare your work against (Sutter, Krause, Kuhn, NeurIPS 2021, Robust Generalization despite Distribution Shift via Minimum Discriminating Information)
4) It would be nice to remind the reviewer about the definition of a Sobolev space (required to understand Theorem 5.1)
limitations: I see the “usual” DRO limitations also in this work, which are: (i) assumption of iid data, (ii) subjectivity of which ambiguity set to choose and (iii) need of a tractable reformulation to solve the DRO problem.

There are, however, good answers in the DRO literature to all three limitations, so I assume the presented framework in subsequent works can address these limitations.
review_title: null

Meta-review: metareview: The paper gives generalization bounds out of distributionally robust optimization (DRO). Unlike standard bounds, e.g., ERM, that depend on the complexity of the function space, the presented DRO bounds depend on the ambiguity set geometry and its compatibility with the true loss function. The authors instantiate their DRO bounds through the maximum mean discrepancy DRO distance, the interesting aspect being the sole dependence on the loss of the best in class hypothesis.
An interesting viewpoint that may spur further investigation in the theory of generalization bounds.



confidence: Certain
Decision: Accept