Venue: NeurIPS 2022 Conference

Reviews:

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 first define an $\epsilon$-coreset for the Wasserstein DRO problem as the following (modification of the geometric coresets to the underlying setting):  the coreset is a weighted (desirably sparse weights) modification of the empirical distribution of the training set whose worst-case risk would be very close (driven by $\epsilon$) to the worst-case empirical risk for any feasible solution. The same definition is reused by the authors to guarantee a similar bound on the objective value of the dual of nature's optimization problem (the worst-case risk), and such weights give the *dual* coreset, which the authors coin. They then show these two definitions are identical under some mild continuity/smoothness assumptions on the loss function. By exploiting the nature of the dual problem, the authors derive an efficient algorithm to construct a coreset (with high probability). The coreset WDRO approach is shown to outperform some benchmark methods on well-known machine learning datasets.
strengths_and_weaknesses: Strength:
- I believe the paper is solving a very interesting problem. The results and proofs all look correct to me, and the simplicity of the algorithm to construct the dual coreset is positively surprising.

Weakness:
- The numerical experiments look very limited compared to the theoretical richness of the paper. It would be great to see more modern computational experiments with more visualizations. There are some unexplained steps (e.g., why is $\gamma = 7$). 
questions: - The distance metric used in the Wasserstein ball is typically named the feature-label distance/metric. Perhaps the authors can cite resources to show the reader this is the most common metric used?
- It would be great to see further numerical experiments in the main text, and for space, the proof of Lemma 1 can be moved into the Appendix?
- Can the authors compare their coreset-WDRO logistic regression with the standard one in [40]?
- I am specifically wondering to what extent can the coreset approach generalize the findings in [41] and [11]. For example, can we characterize the worst-case distributions as in the standard-setting? Can we prove finite-sample guarantees? Would the worst-case distributions look different than the non-coreset approaches? I believe the answers will be affirmative, however, it would be interesting to see further connections with the results derived for the pure Wasserstein settings.

Minor comments:
- Please capitalize "wasserstein" in references.
- Please change alignment $\arg \underset{x}{\max}$ to $\underset{x}{\arg \max }$
limitations: The authors carefully explain the limitations. I do not believe there is an immediate risk of the negative social impact of this work, as it is rather an enhancement technique for an already well-known set of methods.
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 paper introduces a method for computing a coreset for Wasserstein distributionally robust optimization (WRDO) problems by looking at the dual WRDO problem and extending the concept of coresets for the dual. Supported by their theoretical analysis, the authors introduce an algorithm which exploits characteristics of the dual which make the coreset computation easier and prove a sample complexity, which holds with probability proportional to the dataset size. Finally, the paper shows how the proposed coresets could be computed for SVMs, logistic regression, and robust regression problems.
strengths_and_weaknesses: 
**Strengths**

The sound theoretical analysis, clarity of writing, and significance of the contribution all sum up to a strong submission. I also appreciate how the
authors managed to also include experiments employing their coreset algorithm, albeit only in the Appendix.

**Weaknesses**

I believe the major weaknesses in the paper are the presentation and positioning with regards to related work. Especially as someone not deeply familiar with related literature, I found the related work section particularly weak, simply mentioning related problems and not clearly communicating why coresets for WRDO problems fill an important gap left by existing work on similar problems. To be clear, I mean specific citations, not only a motivation discussion as done in the introduction, which was appropriate.

On the presentation side, I believe the problem is on the choice of content to be part of the main paper versus appendix. Some details are somewhat less relevant, for instance Proposition 1, the proof of Lemma 1, full proof of Theorem 2. Considering the wider audience of NeurIPS and that the content would be present in the appendix for the more interested readers, including the experiments in the main paper would have been a better choice to communicate the authors' findings.
questions: Minor points:
- l. 159, 237: def of $r_i$ missing $p$ as superscript?
- l. 248: is the sentence missing a period or not finished?

limitations: I believe that for being a theoretical paper, this makes the limitations clearer by nature. The authors provide full theoretical analyses and proofs to the claims made.
review_title: null

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 constructs a unified framework to construct the ϵ-coreset for the general WDRO problems to reduce the high computational complexity of WDRO. To circumvent the complexity of directly constructing coreset for WDRO, the paper uses dual ϵ-coreset and proposes a more practical “grid sampling” framework and evaluates its performance for several WDRO problems.
strengths_and_weaknesses: Strengths:
The paper is clearly structured and logically coherent. The purpose of this paper is to optimize the WDRO problem by corset method, which has certain research significance. 
The paper simplified the traditional coreset by solving its dual reformulation, which was innovative to a certain extent. 
The paper gave a very detailed derivation process for the bound of λ and gave a detailed theoretical analysis of the setting of the algorithm parameters of epsilon1, epsilon2 and epsilon3.

Weaknesses：
The experimental part of the paper was insufficient, and it was recommended to add some comparative experiments with other WDRO methods.

questions: The formula symbols in the paper are a little different from the standard formula symbols, it would be easier to understand if they were standardized. And the proof of the paper is relatively complex and abstract, can it be analyzed with some chart and graph?
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
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: The paper proposes a method to reduce the complexity of Wasserstein distributionally robust optimization (WDRO) in machine learning via coresets. Instead of considering the full structure of the Wasserstein ball for the worst-case distribution, the paper approximates this worst-case distribution by a coreset. The authors then propose an implementation for this idea by formulating the “dual coreset” for the dual of the WDRO problem and constructing it empirically using a grid partition framework.


-------- Update: following the discussion at the rebuttal phase, I increased my score evaluation to 5.
strengths_and_weaknesses: Originality: The paper appears to be the first to employ the coreset treatment for the worst-case formulation in WDRO problems. The numerical routine for coreset construction seems to be an extension of previous methods [1, 2]. 

Clarity: A severe clarity issue with the paper is the lack of experimental results in the main paper. The evaluation context, and the competitive edge of the method are also not made clear. The proof section could be hard to follow without the re-stated theorems and the placement of Theorem 1 does not follow the order of introduction in the main paper.  Because the clarity of the paper is poor, I still have difficulty in judging the originality and the true significance of this paper. [Further comments in the next section]

Significance: While the paper is the first to solve WDRO with the coreset treatment, the effectiveness of this approach is not clear due to the limited experiments. Thus, I doubt the significance of the paper in advancing our state of the art.
questions: 1. I doubt if ``coreset” is the correct terminology that we would like to study in this setting. In my limited understanding, a coreset should be task-agnostic and model-agnostic. However, the coreset in this paper is both task-dependent and task-agnostic, moreover this coreset also depends on the size of the ambiguity set $\theta$. This raises the following issues:

If we change the model (say, from logistic regression to SVM),  then we need to find the coreset again.
If we change the radius of the Wasserstein ambiguity set, then we need to find the coreset again.

This seems to be very inefficient for MLOps because trying different models and tuning the radius are what we do everyday. Rerunning the coreset algorithm of this paper everytime we make tiny changes to the workflow is counterproductive.

[I think this paper is more similar to the idea of data distillation rather than coreset]

2. It is not clear how the sparsity of $W$ is imposed by the algorithm. Can the authors please elaborate on this sparsity?

3. A practical problem is as follows: Assume that I need to train a Wasserstein DRO logistic regression with radius $\theta = 1$, and I have one million samples. I want to find a coreset with one thousand samples, how can I use the results of this paper to accomplish this?

4. I believe that the main paper has to be self-contained, and the reviewers are not obliged to read the appendix. However, the authors are relegating the numerical experiments to the appendix, and the main paper is ending abruptly. 

5. The demonstration for applications is severely limited. Particularly, the authors only evaluate the application in adversarially robust binary classification over MNIST and LETTER, and the application in adversarially robust regression over Appliances Energy. The effectiveness of the method in other relevant tasks such as out-of-distribution robustness, worst-group robustness, etc., is not discussed. The reported results only compare the proposed method with a strawman method of UNISAMP, instead of other established WDRO methods. The details for the UNISAMP are also not clear, to which I assume the uniform sampling is an alternative approach to constructing the coreset in place of the proposed grid partition.


Minor comments:
- Some drawings and visualizations may help explain the algorithm more clearly
limitations: Maybe a few lines of societal impact may be useful to the reader, e.g.: is the coreset method sensitive to (adversarial/poison) attacks?
review_title: null

Meta-review: metareview: From the reviewers' comments and my own reading of the paper, the idea of bringing the notion of coreset from computational geometry to bear on the WDRO problem is novel and has the potential of further development. The authors should carefully address the reviewers' comments in the revision.
confidence: Certain
Decision: Accept