Venue: NeurIPS 2022 Conference

Reviews:

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, the authors study DRO with data geometry considered in the uncertainty set, making use of the so-called Geometric Wasserstein distance. The authors derive an approximate algorithm for the proposed GDRO and prove its convergence. Numerical experiments are performed to demonstrate the proposed GDRO framework over ERM and other DRO frameworks. 
strengths_and_weaknesses: Strengths: 
- An interesting framework proposed using the Geometric Wasserstein distance
- Extensive experiments

Weaknesses: 
- The whole paper is quite hard to follow due to: 
    - the lack of self-containedness—some rather non-standard notions are not well-defined or well-explained, or very hard to understand
    - unsatisfactory English writing (wrong grammar, choice of words, etc.)
    - inaccuracy in mathematics exposition, the lack of mathematical rigor and lots of abuse of notation
- Related works are not discussed in detail, e.g., DRO
- A lot of typos, typesetting and formatting issues 
- The settings and descriptions of the experiments are unclear


=============================
Post-rebuttal: Thanks the authors for their effort. The revised version has addressed my concerns and I have raised my score. Although it is allowed in this NeurIPS submission cycle, I think the authors should have provided sufficient experimental details in their initial submission. A lot of new content have been added in the revised version of the paper, including supplementary material, say for the experimental details. I feel it is quite unfair to assess the merits of the paper according to this updated version, comparing to other paper submissions. It appears to me that the authors was submitting unfinished work on the submission deadline and take advantage of the rebuttal phase. 
questions: The mathematics of this article is very hard to follow due to abuse of notation. For example, $p$ has been used to represent a lot of different notions. Various claims are also stated without proof or sufficient explanations (e.g., line 151). The use of English language should also be largely improved. The theoretical results also appear to be very trivial. The description of the experiments must be improved—we don’t even know what loss functions are used in the experiments. The exact DRO problems solved in the experiments, especially for the real-world data ones, are completely unstated. The authors also have to rectify the following issues: 

- Typesetting or formatting issues (non-exhaustive): 
    - You have to add spaces before all parentheses and citations 
    - Add punctuations at the end of display style equations
    - Format tables according to the instructions in the NeurIPS paper template—no vertical lines! 
    - Use italics instead of bold to emphasize words

- Typos or writing issues (non-exhaustive):
    - Line 42: $\mathcal{X}_2$—do you mean $\chi^2$? 
    - Line 60: $O(1/\sqrt{T})$
    - Line 109: large-scale~~d~~
    - Line 128: ~~cross section~~ cross-sectional
    - Line 129: ~~algorithmic~~ arithmetic
    - Line 137: Brenier
    - Line 146: $\delta(x_i)$ vs $\delta(x_i, y_i)$
    - Line 159: ~~alternate~~ alternating
    - Line 161: ascent~~s~~
    - Line 193: $\mathcal{R}_n$ vs $R_n$
    - Line 200: $\mathcal{GW}$ vs $GW$
    - Line 204: what is $\mathcal{R}(p)$? Not previously defined. 
    - Table 1: why adding underscores between “mean” and “error”? Use a dot for abbreviations instead of an underscore. 

limitations: Relevant discussion of limitations might appear in the paper but is hard to find.
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 proposed a novel Geometric Wasserstein DRO (GDRO) method by exploiting the discrete Geometric Wasserstein distance. A generically applicable approximate algorithm is derived for model optimization. Extensive experiments on both simulation and real-world datasets demonstrate its effectiveness. 
strengths_and_weaknesses: Pros:
1. The proposed method is well motivated and reasonable. This paper studied an important problem of DRO: the uncertainty set is too over-flexible such that it may include implausible worst-case distributions. To address this issue, the authors proposed to use Discrete Geometric Wasserstein distance to construct the uncertainty set, in order to constrain the uncertainty set within the data manifold. The method is somewhat novel and interesting. 

2. Both convergence rate and the bounded error rate are provided. And the superiority of the proposed method is also empirically demonstrated through experiments on both simulation and real-world datasets.

Cons:
1. Data from unseen distributions may fall out of the manifold constructed by training data. In this case, simply constraining the uncertainty set may not be helpful for OOD generalization.

2. Training efficiency. The authors use a graph to represent the manifold structure. It may be problematic for large-scale datasets since the graph needs to be estimated at every iteration.

3. In the experiments, the authors only compare with ERM and DRO-based methods. It would be a bonus if some general methods for  OOD generalization can be included. 
  
questions: 1. Since the manifold is constructed by the training set, is it still applicable for unseen distributions? Data from unseen distributions may fall out of the data manifold. 
2. Does the graph need to be updated at every iteration? If so, it would be time-consuming to estimate the manifold for large-scale datasets. 

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 the data geometry in the distributionally robust optimization (DRO) problems and proposes a novel framework called Geometric Wasserstein DRO (GDRO) to achieve their goal. The authors also provide some theoretical analyses, such as approximated optimization error and convergence rate, to theoretically show the strengths of GDRO. Finally, the experimental results show the effectiveness of the proposed approach.
strengths_and_weaknesses: Strengths:
- The motivation and contributions are good. This work attacks an overlooked issue in the DRO community and proposes a reasonable method to alleviate this. This would raise much more research attention in this direction.
- This paper presents some roughly decent theoretical guarantees, which support the effectiveness theoretically.

Weaknesses:
- This paper lacks comprehensive discussions about the related work. As we all know, DRO has attracted tremendous research interest in the machine learning community, and there are many studies about DRO.
- The proposed GDRO may has somewhat limitations, since it is not easy to apply to the deep neural networks (DNNs) (Perhaps I am wrong, but at least the authors do not mention it).

As a whole, despite some limitations, I believe the proposed method is a qualified work and could bring some new insights into the DRO community. Therefore, I tend to accept this paper.
questions: My major concerns are listed below:
- The authors should provide more discussions related to their work, including but not limited to the following concepts:
a)	Distributionally Robust Optimization with Markovian Data.
b)	Orthounimodal Distributionally Robust Optimization.
c)	Distributionally robust shape and topology optimization.
- Can the GDRO apply to large DNNs?
- In Thm.3.1, $\ell(\theta)$ is assumed to be convex. What about the non-convex?

==================================

My concerns about this work have been well addressed. I am happy to vote for its acceptance.
limitations: None
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 work aims to solve the problem that DRO is too “pessimistic” (the uncertainty set is too large) and often leads to poor results in practice. The motivation is that “high dimensional data approximately reside on low dimensional manifolds” (lines 6-7), so this work tries to constrain the uncertainty set on this low dimensional manifold. To do this, this work (i) uses the NN-Descent method to estimate the low dimensional manifold; (ii) formulates the GDRO objective and optimizes it with alternating optimization and proves that it converges. The authors then conduct a series of experiments on synthetic and real datasets and claim that the proposed method is better than existing DRO methods.
strengths_and_weaknesses: I really like the high-level idea of this paper. “DRO is too pessimistic” is a well-known open problem in this field, and this work tries to solve this problem by constraining the uncertainty set on a low dimensional manifold, which makes lots of sense. I also think that a lot of credit should be given to the authors for the theory part: The GDRO objective is nicely formulated, and optimizing this objective with alternating optimization makes sense. The convergence result is also very nice.

The major weaknesses of this work, however, come from the experiment section. Recall that the core motivation of this work is that “high dimensional data approximately reside on low dimensional manifolds” (lines 6-7), whereas there is a huge gap between the motivation and the experiments, which makes the experiments very confusing and unconvincing.

Take the first experiment in Section 4.1 as an example. First of all, the experimental setting is very confusing. I suppose that the task is to infer Y from (S, V). I also couldn’t find the definition of alpha_V, so I suppose that it is used to define V. Thus, in this task the input data is 2-dimensional, and (S, V) seems to also reside on a 2-dimensional manifold, which is the union of a number of 1-dimensional curves (if alpha_V is in [a, b] for some a and b). I don’t think this could be called “high dimensional data approximately residing on low dimensional manifolds”. 

Then the authors claim that GDRO is much better than other DRO on this task. I don’t know how the graph G_0 is estimated. I suppose that the authors just simply provide G_0 to the algorithm because NN-Descent is only used “for large-scaled datasets” (lines 109-110). So it seems to me that the reason why GDRO is so good is that G_0 leaks some additional information about the target distribution to it but not to other methods, not because it leverages the fact that the data resides on a low dimensional manifold.

Of course, it is nice that GDRO could utilize this additional leaked information from G_0. The question is: How to get this G_0 in practice? The authors propose to estimate G_0 with NN-Descent, but they don’t demonstrate how well NN-Descent can estimate G_0 on realistic tasks. If G_0 is not well estimated, and the target distribution is outside the estimated manifold, then I imagine that GDRO could completely fail.

Moreover, most of the tasks in the experiments are not really high-dimensional (<50 dimensions), and all tasks seem to follow some simple, unrealistic structures, which make it easier for GDRO to achieve high performances. It is questionable whether these good performances are transferable to real-world applications with realistic distribution shifts.

A valid experimental setting I would suggest the authors try is the following: The input data comes from a low dimensional manifold in a high dimensional space (at least 200 dimensions), but the structure of this manifold is unknown (for instance, introduce randomness into the manifold structure), so GDRO must first estimate G_0 by itself. This setting is closer to the authors’ motivation that “high dimensional data approximately reside on low dimensional manifolds”. Otherwise, it is always questionable whether the performance gain of GDRO comes from the information leakage from the provided G_0, rather than its ability to estimate and utilize the low-dimensional manifold.

In summary, I really like the high-level idea and the theory part of this paper, but the experiment section does require a lot of improvement. Currently, there is a huge gap between the authors’ motivation and the experiments, making the main conclusion of this paper highly debatable. For this reason, I recommend rejecting this paper for this time, and hope that the authors could resubmit after rewriting the experiment section.

****** Post Rebuttal ******
The authors have revised the paper as suggested, so I would like to raise my rating to accept.

questions: 1. I suggest the authors provide some numerical results to demonstrate how well NN-Descent can estimate the low-dimensional manifold. This is very important, because if the manifold is not well estimated and the target distribution is outside the estimated manifold, then GDRO could completely fail. Moreover, since the authors are using kNN, studying the effect of k is also important. If the method works for some k but not for others, then the authors need to elaborate on how to select a proper k with the training samples alone.

2. Could the authors clarify for which of the experiments is the graph G_0 directly provided to GDRO, and for which of them is the G_0 estimated by NN-Descent?

3. In Figure 3, on the Retiring Adults dataset, GDRO seems to maintain the same high performance regardless of the minor ratio. This is not a good signal. When does the performance of GDRO start to drop? For instance, does GDRO still have a very high performance when the minor ratio is 0.01? What about when the ratio is 0? If GDRO always has such a high performance, then I believe that either G_0 provides too much information to GDRO (for instance, the target distribution could be directly obtained from G_0), or there is a bug in the code.

limitations: The limitations are not sufficiently addressed.
review_title: null

Meta-review: metareview: The paper proposes a novel distributionally robust optimization formulation leveraging data geometry to construct the uncertainty set. After a lengthy discussion and revision process, the reviewers have reached a consensus acceptance recommendation, which I support.

Currently the reproducibility checklist (part 3a) states that the authors submitted code to reproduce their results along with the paper, but I do not see it as part of the supplementary material or as a link. Please provide code with the camera ready submission, or correct the checklist. 
confidence: Certain
Decision: Accept