Coresets for Wasserstein Distributionally Robust Optimization Problems
Authors: Ruomin Huang
Jiawei Huang
Wenjie Liu
Hu Ding
Venue: NeurIPS 2022 Accept (2022)
Keywords: coreset
robust optimization
wasserstein distance

Abstract: Wasserstein distributionally robust optimization (\textsf{WDRO}) is a popular model to enhance the robustness of machine learning with ambiguous data. However, the complexity of \textsf{WDRO} can be prohibitive in practice since solving its ``minimax'' formulation requires a great amount of computation. Recently, several fast \textsf{WDRO} training algorithms for some specific machine learning tasks (e.g., logistic regression) have been developed. However, the research on designing efficient algorithms for general large-scale \textsf{WDRO}s is still quite limited, to the best of our knowledge. \textit{Coreset} is an important  tool for compressing large dataset, and thus it has been widely applied to  reduce the computational complexities for many optimization problems. In this paper, we introduce a unified framework to construct the $\epsilon$-coreset for the general \textsf{WDRO} problems. Though it is challenging to obtain a conventional coreset for \textsf{WDRO}  due to the uncertainty issue of ambiguous data, we show that we can compute a ``dual coreset'' by using the strong duality property of \textsf{WDRO}. Also, the error introduced by the dual coreset can be theoretically guaranteed for the original \textsf{WDRO} objective. To construct the dual coreset, we propose a novel  grid sampling approach that is particularly suitable for the dual formulation of \textsf{WDRO}. Finally, we implement our coreset approach and illustrate its effectiveness for several \textsf{WDRO} problems in the experiments. See \href{https://arxiv.org/abs/2210.04260}{arXiv:2210.04260} for the full version of this paper. The code is available at \url{https://github.com/h305142/WDRO_coreset}.

Coresets for Wasserstein Distributionally Robust Optimization Problems
Ruomin Huang!
Jiawei Huang?2
Wenjie Liu?
Hu Ding"
Schooo of Data Science
School of Computer Science and Technology
University of Science and Technology China
Department of Computer Science, City University of Hong Kong {hrm, hjw0330, 1wj1217) @mail. ustc. edu. cn, hhudingusstc.. edu. cn
Abstract
Wasserstein distributionally robust optimization (WDRO) is popular model enhance the robustness of machine learning with ambiguous data. However, the complexity of WDRO be prohibitive in practice since solving its "min- imax" formulation requires a great amount of computation. Recently, several fast WDRO training algorithms for some specific machine learning tasks (e.g.. logis- tic regression) have been developed. However, the research on designing efficient algorithms for general large-scale WDROs still quite limited, the best of our knowledge. Coreset is an important tool for compressing large dataset, and thus it has been widely applied to reduce the computational complexities for many optimization problems. In this paper. we introduce a unified framework to con- challenging
struct the e-coreset for the general WDRO problems. Though to obtain conventional coreset for WDRO due to the uncertainty issue of am- biguous data, we show that we can compute a "dual coreset" by using the strong duality property of WDRO. Also, the eгror introduced by the dual coreset can be theoretically guaranteed for the original WDRO objective. To construct the dual coreset, we propose novel grid sampling approach that is particularly suitable for the dual formulation WDRO. Finally, we implement our coreset approach and illustrate its effectiveness for several WDRO problems in the experiments. See 1000022210004266 for the full version of this paper. The code is available at https: http//githubb com 1305142/ WDRD coreset.
Introduction
In the past decades, number of optimization techniques have been proposed for solving machine learning problems [89]. However, real-world optimization problems often suffer from the issue of data ambiguity that can be generated by natural data noise, potential adversarial attackers [B]] the constant changes of the underlying distribution (e.g.. continual learning [42]). As a consequence, obtained dataset usually cannot be fully trusted. Instead it is actually perturbation of the true distribution. The recent studies have shown that even small perturbation can seriously destroy the final optimization result and could also yield unexpected error for the applications like classification
and pattern recognition [20: 50]
The "distributionally robust optimization (DRO)" is elegant model for solving the issue of ambiguous data. The idea follows from the intuition of game theory [[]]. Roughly speaking, the
"Corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

DRO aims to find solution that is robust against the worst-case perturbation within range of possible distributions. Given empirical distribution P,, n Σ de; where 0g. is the Dirac point mass at the i-th data sample ç,, the worst-case empirical risk at the hypothesis @ is defined as Re (0) = sup [R[ Here u(P..) is the ambiguity set consisting of all possible distri- QEL((P..)
butions of interest, and -(---) is the non-negative loss function. The DRO model has shown its promising advantage for enhancing the robustness for many practical machine learning problems, such as logistic regression |5 support vector machine [29]] convex regression [S], neural net-
works | A8]. etc.
In this paper, we consider one of the most representative DRO models that is defined by using opti- mal transportation [62]] Wasserstein distance is a popular measure for representing the difference between two distributions; it indicates the minimum cost for transporting one distribution to the other. For p 2 1, the p-th order Wasserstein distance between two probability distributions TP and I supported on E is
inf (TET((P / d'(s, (dE, de")
W (P,, =
where -): a metric on E. and [I(F, is the set of all joint probability distributions on E x E with the marginals IP and PP, By using the above Wasserstein distance (II, we can define the ambigu- ity set (TP,) be the p-th order Wasserstein ball Ba have the p-th order Wasserstein distance at most a > 0 to the given empirical distribution Pn. The
which covers all the distributions that
use of Wasserstein ball is discrepancy-bes based approach for choosing the ambiguity set [+ section
5]. Also let
R (0) o.p
E ((((EE)
sup
GEB.,, (F.))
denote the corresponding worst-case empirical risk. The Wasserstein distributionally robust opti- mization (WDRO) problem [27] is to find the minimizer
O_ arg min R2 (0) arg min sup #ee (EBr.p(Pa)
(3)
where θ is the feasible region in the hypothesis space. It is easy to see that the WDRO is minimax optimization problem.
Compared with other robust optimization models, the WDRO model enjoys several significant ben- efits from the Wasserstein metric, especially for the applications in machine learning [[.5% E6:; i:; I8). The Wasserstein ball captures much richer information than the divergence-based discrepancies for the problems like pattern recognition and image retrieval [33;; B3; 17]]. has also been proved that the WDRO model yields theoretical quality guarantees for the "out-of-sample robustness [TK)]
However, due to the intractability of the the inner maximization problem (2). challenging to directly solve the minimax optimization problem (L)) As shown in the work of Esfahani and Kuhn
[[3]], the WDRO problem (G) usually has tractable reformulations [45; 35t B01 2%; 2I; EI Although
these reformulations are polynomial-ting solvable, the off-the- shell solvers can be costly for large- scale data. Another approach is directly solve the minimization problem and the maximization problem alternatively [[9]] under finite-support assumption. Gao and Kleywegt [[Z7] proposed routine to compute the finite structure of the worst-case distribution in theory. Nevertheless still takes a high computational complexity if the Wasserstein ball has large support size. Several fast WDRO training algorithms for some specific machine learning tasks, e.g., SVM and logistic regression by Li et al. [31], 32), have been developed recently; but it is unclear whether their methods can be generalized to solve other problems.
Therefore, it is urgent to develop efficient algorithmic techniques for reducing the computational complexity of the WDRO problems. Coreset a popular tool for compressing large datasets, which was initially introduced by Agarwal et al. in computational geometry [M]]. Intuitively, the coreset an approximation of the original input data, but has much smaller size. Thus any existing algorithm can run on the coreset instead and the computational complexity can be largely reduced. The coresets techniques have been widely applied for many optimization problems such as clustering and regression (we refer the reader to the recent surveys coresets [36; [4]). Therefore natural

---

idea is to consider applying the coreset technique to deal with large-scale WDRO problems. Below we introduce the formal definition of the coreset for WDRO problems.
Definition (e-coreset) Let be any given small number in (0,1). An e-coresel for the WDRO problem (L) a sparse nonnegative mass vector W = [wi...., Wnl. such that the total mass Wi 1 and the induced distribution F,, Σ wodg satisfies
RO E = +) (0,
(4)
where Rig,
[R( is the worst-case empirical risk of the coreset.
sup (P..
It is worth to emphasize that the above coreset for WDRO is fundamentally different from the conventional coresets [[=)]. The main challenge for constructing the coreset of WDRO is from the "uncertainty" issue, that is, have consider all the possible distributions in the Wasserstein ball ( and more importantly, when the parameter vector 0 varies, the distribution that achieves the worst-case empirical risk also changes inside (IPP.).
1.1 Our Contribution
In this paper, we propose novel framework to construct the e-coresets for general WDRO problems. To the best of our knowledge, this is the first coreset algorithm for Wasserstein distributionally robust optimization problems. Our main contributions are twofold.
-From coresets to dual coresets. As mentioned before, it is challenging directly construct the coresets for the WDRO problems. Our key observation is inspired by the strong duality property of the WDRO model [I* R [77]. We introduce the "dual coreset" for the dual formulation of the WDRO problems. We can neatly circumvent the "uncertainty" issue in Definition through the dual form. Also, prove that the dual coreset can yield theoretically quality-guarannn coreset as Definition II.
-How to compute the dual coresets. Further, we provide a unified framework to construct the dual coresets efficiently. The sensitive-sampling based coreset framework usually needs to compute the "pseudo-dimension" of the objective function and the "sensitivities" of the data items, which can be very difficult to obtain [[=]] (the pseudo-dimension measures how complicated the objective function is, and the sensitivity of each data item indicates its importance to the whole input data set). Therefore we consider to apply the spatial partition approach that was initiated by Chen [S]]; roughly speaking, partition the space into logarithmic number of regions, and take uniform sample from each region. This partition approach needs to compute the exact value the Moreau- Yosida regularization [[Σ], which is key part in the dual formulation of WDRO (the formal definition shown in Proposition M... However, this value often hard to obtain for general E and general ((:;)) For instance, suppose E admits conic representation and the learning model is SVM, then computing the Moreau- Yosida regularization equivalent to solving a convex conic programming [4 corollary 3. 3.1 For some machine learning problems, it is usually relatively easier estimate the bounds of the Moreau-Yoses generalize the spatial partition idea and propose a more practical "grid sampling" framework. By using this framework, we only need to estimate the upper and lower bounds of the Moreau-Yoste regularization instead of the exact value. We also prove that a broad range of objective functions can be handled under this framework.
regularization [if Theorem 3.30]. Based on this observation, we
Due to the space limit, leave the omitted proofs, discussions and experimental results to the full version of this paper [25)].
1.2 Other Related Works
A number of coreset-based techniques have been studied before for solving robust optimization problems. For example, Mirzasoleiman et al. [[4]] designed an algorithm to generate coreset to approximate the Jacobian of a neural network so as to train against noisy labels. The outlier-resistant
coresets were also studied for computing the robust center-based clustering problems [[L5) 16; 24;; [12].
For the general continuous and bounded optimization problems [[)], Wang al. [ proposed
3

---

dynamic framework to compute the coresets resisting against outliers. Several other techniques also have been proposed for dealing with large-scale DRO problems, such as the PCA based dimension reduction methods [T0) [ and the stochastic gradient optimization methods [Z]].
2 Preliminaries
We assume the input-output space E = X Y with X R and Y C R, and let P(E) denote the set Borel probability distributions supported on E. For S I n, each data sample is a random vector distribution P, 1 2 =i=1 dg. is induced by the dataset (Si.....En. En), where ōg. is the Dirac point mass at &.- We endow =\t with the distance d(E,; E I|,,, xyyl 1// Myl. where || Il stands for an arbitrary norm of Ih and the positive parameter "y" quantifies the transportation cost on the label. This distance function is used for defining the Wasserstein distance (II). We assume that (=, is a complete metric space.
[24, y4) drawn from some underlying distribution P E P(3). The empirical
In the rest of this paper, we consider the WDRO problems satisfying the following two assumptions. The first assumption is on the smoothness and boundedness of 0. Similar assumptions have been widely adopted in the machine learning field [566 (:3]]
Assumption (Smoothness and Boundedness of
(i) (Boundedness) The feasible region θ of the parameter space for the WDRO problem is within a closed Euclidean ball B(faacc 1p) centered at some "anchor" point fanc with radius lp > 0:
Ie
(ii) (Lipschitz Smoothness)) There exists a constant I, 0, such that for any & E E and any 0,, 02 [B(0anc: 1p). have |e (01, - (02, {) < T. |0] 02112-
The second assumption states that the loss function {(0,E) continuous and has a bounded growth rate on data ç. The detailed growth rate functions are discussed in Section N
Assumption 2 (Continuity and Bounded Growth Rate of E)
(i) (Continuity) The loss function E(O,-) is continuous for any 0 O;
(ii) (Bounded Growth Rate) There exists some positive continuous growth rate function C(0) and Eu such that
((0,E) < C(0) (1 d (E,Eo))
for any 0 E O and any & E
Now we state the strong duality for the WDRO, which is an important property to guarantee the correctness of our dual coreset method.
Proposition 1 (Strong duality IL3: 9 IZI) For any upper semi-continuous ((0,)), :), any 0 and any nominal distribution IP with finite p-th moment, the worst-case risk satisfies
R (0) = inf aoo + " (B))),
(5)
A20
where H=,00 = =. (1(00, X, E) and h(0 = sup Xd)((, is the Moreau- Yosida ÇEE
regularization [38]. We use x²( to denote the X allaining the infimum in (S).
Remark the definition of h, for any given 0 O, we can deduce that there always exists some XE < oo attaining the infimum of (SS).
For the sake of convenience, we abbreviate ( (0), ((, H=- X. x (0), and (1, A) = h(0, A, E.). We define the asymptotic growth rate function
((0.E) (0,
x0) limsup
d (o)
a(E.Eo)-oo
"The methods proposed in this paper can be easily extended to other types of smoothness, e.g., gradient L Lipschitz continuity.

---

use T(0) to denote this upper bound so as to conclude the continuity of h.(.,)) -) in the following two claims. Here Eo is the point in Assumption (ii).
Claim (Continuity of h; on 0) For each E {I,...,m) and any fixed 2 we have (0, h, X)I S L| 8111,
for any 0, 0' E θ with x(0),<(0') S X.
Claim (Continuity of h; on A) For each E (1,...,7) n. and any fixed E Rdd, we have
(0,(0, (, X') & max[r (), X1, Ax, 2 k(0), where r((0,)) = min (/ E(O, () - (s) - h,(0, A}} is the closest distance between & and all the Çs that attain the supremum of ((O, (x) E.
ÇEE
Remark 2 The reason that we let X 2 x0) in the above claims is that each h (0, X) goes to infinity if> < k()). Without loss of generality suppose (v, x(0)) < in this paper.
3 From Coresets to Dual Coresets
In this section, we provide the concept of "dual coreset" and prove that sufficient to guarantee the correctness with respect to the WDRO coreset. First, we present the definition of the dual coreset via directly combining Proposition M and Definition MI. Suppose an interval depending on 0 (we will discuss this assumption in detail later).
Definition (Dual e-Coreset) A dual e-coreset for the WDRO (e) a sparse non-negative
mass vector W [w.,..., Wn) such that the total mass Σ wt = 1 and
n
H(O, = Σ E (1)
(6)
for any E O and X E I.
Remark 3 Note that we require the approximation guarantee holds not only for any 0 E θ, but also for any X I in the above definition. This is also key difference to the traditional coresets.
By the discussion in Remark D. we know C [k))), we directly let = [x(0), oc). the dual coreset of Definition Q requires approximate the queries from all À x:(0), which is too strong and can be even troublesome for the coreset construction. Below we show that a bounded sufficient for guaranteeing dual coreset to be qualified WDRO coreset.
Given a nen-negative mass vector
[wi,... w,,), the corresponding weighted empirical distri- bution P,, = Σn= wedg.- Recall that we define parameter (O) for duality in Proposition
Together with Assumption 2 we show the boundedness of the X. (0) (abbreviated ,. (0) for convenience) for P,, Let [n] (1.2, ,n.. The following result is key to relax the requirement for the dual coreset in Definition Ø
Lemma (Boundedness of X.) Given the empirical distribution P,, Σ pg. define the
value max(fd(E, Eo)) that is the largest distance from the data samples to &a- Here is iE|m)]
defined in Assumption (ū)) For any 0 E O and any mass vector W, the X.(0) of the corresponding weighted empirical distribution PP,, is no larger than
1 21
c(0)
2P-1
(7)
OP
where c(O) is defined in Assumption c(0) 2--1
(ii).
142--1 05
IIt is possible that (0, x()) = 0o. e.g. 6(0, è) is the loss function of ordinary linear regression. In this case, the argument in this paper still holds with slight modification.
5

---

Algorithm Dual e-Coreset Construction
Input: The empirical distribution F,. - og,, the Lipschitz constant L, the "anchors" Onnc and Ame. and corresponding radii lp and la: the parameter E (0, 1); lower bound oracle (;(::) and upper bound oracle b.(:.-) -) for i E [n]
1. Compute A = 1 -i=1 a;(0 Aane) and B = 1 +ii bi(Oamer danc).
2. Let N llog n initialize W 10,0,-- 0] IR"
3. The dataset {EI.... En } is partitioned into (N + 1)² cells {Ciy10 S i,j S N) (I2).
4. For each C, * 0, 0 S i.j S N:
(a) take a sample Qy from Cipy uniformly at random, where the size [Quy depends the parameters e, lp. la and L (the exact value will be discussed in our fol- lowing analysis in Section H.2);
(b) for each sample & E Qej. assign the mass of quantity w = x
|Ctyl
Output: the mass vector W
[Wi, "2. ... wn] as the dual e-coreset.
Remark 4 (i) In practice, we usually normalize the dataset before training machine learning model, which implies that is not large. (ii) It is worth noting that the above lemma can help us to compute an upper bound for (0). For example, if letting W = 1 H. ((i directly yields an upper bound.
The following theorem shows that the query region [x<(0) (()] is sufficient for obtaining a coreset of the WDRO problem (G).
Theorem (Sufficiency the bounded query region) If we let query region T= (()) in Definition D the dual 6-coreset defined in such way also satisfies the coreset of Definition I1
Therefore in the rest of this paper, we let I = [m((); r00 in Definition Theorem M also implies the following corollary. So we can only focus on solving the dual WDRO problem (B) on the obtained dual e-coreset.
Corollary Given a 2 1, we suppose the parameter vector 0g yields an a-approximation obtained on the dual e-coreset. Then Og is also an (a approxiiaaai of the original WDRO (E).
To end this section, similar to B(Oanc: 1p) in Assumption A (i), define an interval Danc - la, Aane la] centered at some "anchor" point >ane > 0 with radius la > 0. To ensure that [i=()), [()] is within the interval [Aae
la. Aane la] for all 0 O, we let Aane max (xa0xe(0a r(0) 22 and la = Aane-
4 The Construction of Dual Coresets
Following the results of Section we show how to compute a qualified dual coreset in this section. Suppose we can evaluate the lower and upper bounds for each h.(-,.) with respect to given couple (Nanc: Oanc), namely, we have
ag )anc) S (0,nne Aanc) S bi(Onnc: Aanc)
for 1 sisn n. We defer the details for obtaining such upper and lower bounds for each application to Section 6
4.1 The Construction Algorithm
We show the dual e-coreset construction procedure in Algorithm II where the high-level idea is based on the following grid sampling.
Grid sampling. Let N [log n... Given the anchor (Oancy )ame), the dataset based on the lower bounds a; (fancc Aanc) and upper bounds by (f >anc) separately. Let A Σi= a:(( (f(onee )ane) and B """ (anc)) Then we have the following partitions.
conduct the partitions over
Ao = (Es a, (0 Aane) S A},
(8)
A₁ (E 2/-12/1 1/--1 A a, (aanc Aane) < 1 N.
(9)

---

Bo = (6: b Aane) S B).
(10)
B3 (E: 2 B < b, )mne) 2
(11)
We denote the lower bound and upper bound partitions A = {Au:... AA and B [B..... .BN] respectively. Then, we compute the intersections over A and to generate the "grid":
C= (C, = A,n N).
(12)
It is easy to see that C is collection of disjoint "cells" and U Cyf P. For each &N E Ciy, we have 1.j
2 A S h4 (fancr dnnc) S 2
(13)
where = 0 if = 0 and [4 = otherwise. Through the grid partition C, we can take a set of samples Qi, from Cj uniformly random, and assign the weight |Csrl. each sample.
m!
Remark (i) The grid sampling a variance reduction technique in the Monte- Carlo methods [U9]] since the grid partition is also a stratification for (0an, Aanc) shown in (LE). If we consider only the upper bounds (n Annc) or the lower bounds ag (g(0ane >anc), the obtained partition is not valid stratification for h2 (fanc Aanc). (ii) If we can obtain the exact value of he (a(nn Xane), )
i.e. a, (0 ) (f Aanc) = h4 (fanc: Aane), then the grid partition exactly the spatial partition that was studied before 19% 5.
4.2 Theoretical Analysis
In this section we analyze the complexity of Algorithm theory. Recall that we define (0. X) = min (.) ()),5) (S,( h0, ^)} in Claim m The following theorem provides an
ÇEE
asymptotic sample complexity of Algorithm M To state the theorem clearly, we define two notations (0, X).
R = max (rf (I((0)))) and H 1Ein]
min 928 AE(Maan - Panneccl
9C6
((B
2 - ) in the Algorithm M Then the returned W is B+ B+LL+ 1.LL++RU
Theorem Set 1Qyl-1100
AH
a qualified dual e-coreset with probability at least 1. The construction time is O(n time where tb is the time complexity for computing the lower bound o, (,(annc Nane) and the upper bound be(Oance >ane) ) for each h2 (,(0nnc, Aanc))
n,"
Remark 6 Note that the value H 2 mingge E=,((0,)) which should not be too small in practice since the loss function E((x-) usually contains positive penalty terms. The value of R will be discussed in Section E
We show the sketched proof of Theorem D below. Based on the continuity of ha(r)) and the Hoeffd- ing's 's inequality [22]], for a fixed couple (0, A), we provide an upper bound on the sample complexity first. The bound ensures that the estimation for each cell Ci₃ has a bounded deviation with high probability.
Lemma 2 Let 8 be a given positive number. We fix couple (8, E B(Oanc: 4p) x [K(0), and take a uniform sample Qiz from Cij with the sample size
1 0 (2' - p4 24 A 211, + 28 log 1
(14)
Then, we have the probability
Prob
Σ
hy (x
Σ (x
26 S m
(15)
1Ctbl
EUEQU
EEECiS
*0(g)= = O'g polylog( (2fff Rly

---

We aggregate the deviations from all the cells to obtain the overall estimation error for the coreset.
To guarantee the approximation quality of (K), we need design sufficiently small value of the deviation 8 for each cell Ci under our grid partition framework.
Lemma In Lemma 2 we set the deviation ó -1(2/-1 + 22-1))2-100 have
for 0 S i, S N. Then we 2
Prob (((()))) - H(0, & 3c, (0 )anc)
21 21- - (N 1)
(16)
To generalize the result of Lemma B to the whole feasible region (B(ancc: 4p) [0. 21a). we apply the discretization idea. Imagine to generate the axis axis-parallel grid with side length salp x ezla inside
(0 x [0, 2/a]; the parameters ez and é3 are small numbers that will be determined in our following analysis. For each grid cell we arbitrarily take (6, X) as its representative point. Let G be the set of the selected representative points; it is easy to see the cardinality |G] 1..0 ). of
Through taking the union bound over all (0, X) G for (LT)), obtain the following Lemma R
Lemma With probability at least (N + Gl,, we have
A) () (0, A) - 3e, H (fanc: Aane) for all (0, E G.
(17)
By using the above lemmas, are ready to prove Theorem
Proef Theorem 2 For any () E BBaancc la) x (=(0).((0) we let (0', E be the repre- sentative point of the cell containing (0. A). Then have ||0 8'112 Ealp and X Al ezla
Without loss of generality, we assume X 2 X. By using the triangle incquality, we have
(0,(0, (n (()
(1ha(0',>') - hu (0, + [/x (0, X'1
(18)
<Leglp Rezla.
(By Claim D. Claim M and X 222
The above inequality implies
(H A) H(00, S Rezla + Tagl
(19)
and
(H(0 A) H < Rezla + Leslp
(20)
Overall we have (0, H(O,))I
< (0, H (0', + H (8', - - (0', x1) H (0', H (0,
(21)
<3e1ll H1 (Oanc; )anc) + (Rezla Leghp)
(By Lemma and (2
By setting 6 = 9n 6
He He
R. C3 =
614, and 7 = a(N+1)110 and substituting them into (Il)) we
He
obtain the sample complexity stated in Theorem 0
5
Applications
In this section, we show several WDRO problems that their complexities can reduced by using our dual coreset method.
5.1 Binary Classification
For the binary classification, Y= (-1,11 and the loss function E(0,E) = L(y 8T where L(-) is non-negative and non- -on-inceaasing function. Let || || be the dual norm of || on I We consider Support Vector Machine (SVM) and logistic regression problems. The SVM takes the hinge loss L(z)= max (0, 2} and the logistic regression takes the logloss L(z) log(1 + exp(==)). X = m and p 1, by the result of Shafieezadeh-Ahann these two problems we have:
al. [H6) Theorem 3.11], for both of
8

---

R R k(0) ((0) ||0||=: (0, = (.( h,(0, = ( 10 x1);,, L( yr v1 (T,)).)))))))))))){ -Xy for any À 2 k(0).
X = [0, 1mth is m-dimennioonl hypercube with side length 1 > 0, (0, A) in fact is the optimal objective value of a convex constrained programming problem. Therefore we cannot obtain the exact value of (0, X) easily. To remedy this issue, we can invoke the upper and lower bounds of (0, X) and conduct the grid sampling to efficiently construct the coreset.
5.2 Regression
For the regression problem, Y R and the loss function E(0,E) = L(0 y). where L(-) is non- negative function. Let || be the dual norm of || on m+ We consider the robust regression problem that takes the Huber loss L(z) = ==²² if ||| S and L(z) = 8 (|21 - 15) otherwise for some 8 2 O. If p- and X RR", by the result of Shafieezadeh-Abeee Abhh-h-bbehhhhh al. [96. Theorem 3.1], we have
R R= = c()) = 611(0, -))l=:
* =((0,A)=b((6 h,( = L(0 x2 y4) for any A 2 x(0).
6 Experiments
Our experiments were conducted on server equipped with 2.4GHZ Intel CPUs and 256GB main memory. The algorithms are implemented in Python. We use the MOSEK [2] to solve the tractable reformulations of WDROs. Our code is available at https://github. http:/thww..cmm////////////d
Coreset.
Compared methods. We compare our dual coreset method DUALCORE with the uniform sam- pling approach UNISAMP, the importance sampling approach IMPSAMP [5]]]. the layer sampling approach LAY
[2 and the approach that directly runs on the whole training set WHOLE.
Datasets. We test the algorithms for the SVM and logistic regression problems two real datasets: MNIST[[8] and LETTER([). To simulate the scenarios with contaminated datasets, we perform poisoning attacks to the training set of LETTER. Specifically, and ALFA attack from [54]] We add the standard Gaussian noise (O, 1) to the training set of MNIST and randomly flip 10% of the labels. The dual coreset algorithm for the robust regression problem is evaluated on the real dataset APPLIANCES ENERGY
the MIN-MAX attack from [26]
Results. Let 8 and be the coreset size and the training set size, respectively. We set & to and fix the parameter ? 7 for all the instances 8 (recall that y is used for defining the distance d(E;,E)) = || - æ, + 7 were repeated by 50 independent trials. We report the obtained worst-case risk R (0.) for each method in table M1 Ø and B. Due to the space limit, the detailed experimental results are placed the full version of this paper [25].
indicate the compression
2 1/: - ByD- The experiments of each instance
7 Conclusion
In this paper, we consider reducing the high computational complexity of WDRO via the coreset method. We relate the coreset to its dual coreset by using the strong duality property WDRO, and propose novel grid sampling approach for the construction. To the best of our knowledge, our work is the first systematically study on the coreset of WDRO problems in theory. We also implement our proposed coreset algorithm and conduct the experiments to evaluate its performance for several WDRO problems (including the applications mentioned in Section D. Following our work, there also exist several important problems deserving to study in future. For example, it is in- teresting to consider the coresets construction for other robust optimization models (e.g., adversarial training (20)).
'e let 7, which was same as the value set in [1]] We refer readers for detailed discussion to the full version of this paper (25].

---

UNISAMP
IMPSAMP
LAYERSAMP
DUALCORE
1%
0.72518=0.1266
0.7048440.0915
0.70988=0.084
0.68933=0.0587
2%
0.64630=0.0344
0.65798=0.0447
0.63911=000305
0.63708=0.0557
3%
0.0010
0.63015=0.0933
0.01991=0.0199
0.62546=0.0225
4%
0.0017
0.0083
0.61616-00000
0.61292
5%
0.61338+-0011
0.11324+0.0137
0.61013+000069
0.60986-00000
6%
0.60823+
0.0031
0.60749 0.0119
0.00556=0.0092
7%
0.60716=0.0082
0.6059=000083 0.61198-0.0013
0.60381=0.0073
8%
0.60640=0.007
0.60936=0000008
0.60376=000078
0.60238-0.0062
9%
0.60677+00.0866 0.60395+000066
0.60235=0.007
0.60056-0.00466
10%
0.60220=0.0069
0.60574=10.09
0.60007=000041
0.60113=0.0071
Table 1: Worst-case risk of logistic regression on LETTER, WHOLF=
UNISAMP
IMPSAMP
LAYERSAMP
DUALCORE
1%
0.6870710.1091
0.66576110.003
0.7057710.1277
0.6786620.1173
2%
0.59376=000566
0.60895-000683
0.55967-0.0529
0.59850=0.0548
3%
0.56860=100036
0.57346:1.0053
0.56705-10.0377
0.56689=0.0347
4%
0.55050=0.04009 000000
0.54366=0.0336
0.53634-0.007
5%
0.53218=000234
0.54212:+0.0295
0.52981=000182
0.50217=0.019
6%
0.5346+10.02 0248
0.53835=10.288
0.52496=0.011
0.52835=0.0184
7%
0.00784+0.0225
0.0027
0.52039-0.015
0.52025=0.0147
8%
0.52246
0.0019
0.51845+0.0116
9%
0.52025 +0.0153
0.52402+000200 0.51768++0.016
0.0094
0.51196-0.0054
10%
0.51458+ +0.0083
0.51578
0.51066 0.0065
Table 2: Worst-case risk of SVM on LETTER, W90LF=0049334 0.1
UNISAMP
IMPSAMP
DUALCORE
%
28.57655:0.0005
28.5764910.000
28.57627 0.0002
2%
28.57619+00.000
28.57617+000000
28.57607 10.0001
3%
18.57609:0.000
28.5761
28.57598
0.0001
4%
28.57600
28.57601 0.00001
28.57593
0.0001
5%
28.57595+0
28.5759810.0001
28.57588-10
6%
28.5759311
28.57594=0.0001
28.57587=0
7%
28.5759
28.57592=0.0001
2
8%
28.57589#0
28.57589=0
28.57584
9%
28.57589
28.57589#0
28.57583
10%
28.57588+0
28.57588=0
28.57582-
Table 3: Worst-case risk of Huber regression APPLIANCES ENERGY, WHOLE-28.57578.
100. LAYERSAMP coinsides with DUALCORE for Huber regression. This because h, ((0,;)) for Huber regression (See Section 5.2).
Acknowledgements
The research of this work was supported in part by National Key R&DD program China through grant 2021 YFA 1000900 and the Provincial NSF of Anhui through grant 2208085MF163. We also want to thank the anonymous reviewers for their helpful comments.
References
[1] K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. J. ACM, 51(4):606-635 2004.
[2] M. ApS. MOSEK Optimizer API for Python 9.3.20, 2019. URI. https::/ddcss com/ latest/pythonnpi//neee html.
10

---

[3] B. Biggio and F. Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Pattern Recognit., 84:317-331, 2018.
[4] Blanchet and K. Murthy, Quantifying distributional model risk via optimal transport. Math- ematics of Operations Research, 44(2):565-600 6000 2019.
[5] Blanchet, P. W. Glynn, Yan, and Z. Zhou. Multivariate distributionally robust convex regression under absolute error loss. Advances in Neural Information Processing Systems, 32, 2019.
[6] Blanchet, Y. Kang, and Murthy, Robust Wasserstein profile inference and applications to machine learning. Journal of Applied Probability, 56(3):830-857, 2019.
[7] I.. M. Candanedo, V. Feldheim, and D. Deramaix. Data driven prediction models of energy use of appliances a low-energy house. Energy and buildings, 140:81-97, 2017.
[8] C.-C. Chang and C.-J. Lin. Libsvm: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
[9] K. Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM Journal on Computing, 39(3):923-94) 2009.
[10] Cheng, R. L. Chen, H. N. Najm, A. Pinar, C. Safta, and J. Watson. Distributionally robust optimization with principal component analysis. SIAM J. Optim., 28(2):187--181, 2018.
[11] M. Cheramin, J. Cheng, R. Jiang, and K. Pan. Computationally efficient approximations for distributionally robust optimization. Optimization online, 2020.
[12] H. Ding, H. Yu, and Wang. Greedy strategy works for k-center clustering with outliers and coreset construction. In M. A. Bender, O. Svensson, and G. Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPles, pages 40:1 40:16. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019.
[13] P. Esfahani and D. Kuhn. Data-driven distributionally robust optimization using the Wasser- stein metric: Performance guarantees and tractable reformulations. Mathematical Program- ming, 171, 05 2015. doi: 10. 0011077/110007-011-177-11
[14] D. Feldman. Core-sets: An updated survey. Wiley Interdiscip. Rev. Data Min. Knowl, Discow., 10(1), 2020.
[15] D. Feldman and M. Langberg. A unified framework for approximating and clustering data. In L. Fortnow and P. Vadhan, editors. Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 569-578. ACM, 2011.
[16] D. Feldman and L. Schulman. Data reduction for weighted and outlier-resistant clustering. In Rabani, editor, Proceedings of the Twenty- Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1343-1354, SIAM, 2012.
[17] R. Gao and A. J. Kleywegt. Distributionally robust stochastic optimization with Wasserstein distance. arXiv preprint 160.00260 2016.
[18] R. Gao, X. Chen, and A. J. Kleywegt. Wasserstein distributional robustness and regularization in statistical learning. CoRR, abs/1712.060SD 2017.
[19] E. Gobet. Monte-Carlo methods and stochastic processes: from linear to non-linear. Chapman and Hall/CRC, 2016.
[20] I. Goodfellow. P. McDaniel, and N. Papernot. Making machine learning robust against adver- sarial inputs. Communications of the ACM, 61(7)566-66, 2018.
[21] G. A. Hanasusanto and D. Kuhn. Conic programming reformulations of two-stage distribu- tionally robust linear programs over Wasserstein balls. Operations Research, 66(3):449-86) 869, 2018.
11

---

[22] W. Hoeffdingg Probability inequalities for sums of bounded random variables. In The collected works of Wassity Hoeffding, pages 409-426. Springer, 1994.
[23] J. Huang, R. Huang, W. Liu, N. Freris, and H. Ding. A novel sequential coreset method for gradient descent algorithms. In International Conference on Machine Learning, pages 4412- 4422. PMLR, 2021.
[24] L. Huang, S. H. Jiang, J. Li, and X. Wu. Epsilon-coresets for clustering (with outliers) in doubling metrics. In M. Thorup, editor, 59th IEEE Annual Symposium on Foundations of Com- puter Science, FOCS 2018, Paris, France, October 7-9, 2018. pages 814-825. IEEE Computer Society, 2018.
[25] R. Huang. J. Huang, W. Liu, and H. Ding. Coresets for Wasserstein distributionally robust optimization problems, 2022. URL
04260,
[26] W. Koh, J. Steinhardt, and P. Liang. Stronger data poisoning attacks break data sanitization defenses. CoRR, abs/1811 11881111074111 2018.
[27] D. Kuhn, P. M. Esfahani, V. A. Nguyen, and Shafieezadeh-Abadeh Wasserstein distribution- ally robust optimization: Theory and applications in machine learning. In Operations research management science in the age of analytics, pages 130-166. Informs, 2019.
[28] Y. LeCun, C. Cortes, and C. Burges. Mnist handwritten digit database, 2010.
[29] C. Lee and S. Mehrotra. A distributionally-rouu approach for finding support vector ma- chines. Available from Optimization Online, 2015.
[30] D. Levy. Y. Carmon, J. C. Duchi, and A. Sidford. Large-scale methods for distributionally robust optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, edi- tors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[31] J. Li, S. Huang, and A. M.-C. So. A first-order algorithmic framework for distributionally robust logistic regression. Advances in Neural Information Processing Systems, 32, 2019.
[32] Li, C. Chen, and M.-C. So. Fast epigraphaa projection-based incremental algorithms for Wasserstein distributionally robust support vector machine. Advances in Neural Information Processing Systems, 33:4029-4039 2020.
[33] H. Ling and K. Okada. An efficient earth mover's distance algorithm for robust histogram comparison. IEEE transactions on pattern analysis and machine intelligence, 2955):840-853, 2007.
[34] B. Mirzasoleiman, K. Cao, and J. Leskovec. Coresets for robust training of deep neural net- works against noisy labels. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
[35] P. Mohajerin Esfahani, S. Shafierradeh-Ahadehh G. A. Hanasusanto, and D. Kuhn. Data-driven inverse optimization with imperfect information. Mathematical Programming, 167(1):191- 234, 2018
[36] A. Munteanu and Schwiegelshohn. Coreoess- and history: theoreticians design pattern for approximation and streaming algorithms. Künstliche Intell., 32(1):37-53, 2018.
[37] H. Namkoong and J. C. Duchi. Stochastic gradient methods for distributionally robust opti- mization with f-divergences. In D. D. Lee, M. Sugiyama, U. von Luxburg, I. Guyon, and Gamett, editors, Advances in Neural Information Processing Systems 29: Annual Confer- ence on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2208-2216, 2216, 2016.
R.
[38] N. Parikh and S. Boyd. Proximal algorithms. Foundations and Trends optimization, 1(3): 127-239, 2014.
12

---

[39] G. C. Pflug and A. Pichler. The problem of ambiguity in stochastic optimization. In Multistage Stochastic Optimization, pages 229-255. Springer, 2014.
[40] K. Postek, D. den Hertog, and B. Melenberg. Computationally tractable counterparts of distri- butionally robust constraints on risk measures. SIAM Review, 58(4))603-66) 650, 2016.
[41] H. Rahimian and S. Mehrotra. Distributionally robust optimization: A review. arXiv preprini arXiv: 05659, 2019.
[42] M. B. Ring. Child: A first step towards continual learning. In Learning learn, pages 261- 292. Springer, 1998.
[43] Y. Rubner, C. Tomasi, and I.. Guibas. The earth mover's distance as metric for image retrieval. International journal of computer vision, 40(2):99-121, 2000.
[44] S. Sagawa, W. Koh, T. B. Hashimoto, and P. Liang. Distributionally robust neural networks. In International Conference Learning Representations, 2019.
[45] S. Shaficezadeh Abadeh, P. M. Mohajerin Esfahani, and D. Kuhn. Distributionally robust logistic regression. Advances in Neural Information Processing Systems, 28, 2015,
[46] S. Shafierzadeh-Abader D. Kuhn, and P. M. Esfahani. Regularization via mass transportation. Journal of Machine Learning Research, 20(103):1-68, 2019.
[47] S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014. ISBN 978-1-10-705713-5.
[48] A. Sinha, H. Namkoong, and J. C. Duchi. Certifying some distributional robustness with principled adversarial training. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
[49] Sra, S. Nowozin, and S. J. Wright. Optimization for machine learning. Mit Press, 2012.
[50] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. J. Goodfellow, and R. Fergus. Intriguing properties of neural networks. In Y. Bengio and LeCun, editors, 2nd International Conference Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
[51] M. Tukan, A. Maalouf, and D. Feldman. Coresets for near-convex functions. Advances in Neural Information Processing Systems, 33:997-1009, 2020.
[52] C. Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[53] Z. Wang, Y. Guo, and H. Ding. Robust and fully-dynamic coreset for seadinoou--and-bountd learning (with outliers) problems. M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 14319-14331, 2021.
[54] H. Xiao, B. Biggio, B. Nelson, H. Xiao, C. Eckert, and F. Roli. Support vector machines under adversarial label contamination. Neurocomputing, 160:53-62, 2015. doi: n0.1016/j.neucom. 201 4.....8.01..
[55] H. Xu, C. Caramanis, and Mannor. Robustness and regularization of support vector ma- chines. Journal of machine learning research, 10(7), 2009.
[56] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In
T. Fawcett and N. Mishra, editors, Machine Learning. Proceedings of the Twentieth Interna- sional Conference (ICMI. 2003), August 2 21-24, 2003, Washington, DC, USA, pages 928-936. AAAI Press, 2003.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Some proofs are left to the full version of this paper due to the space limit.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material settings experiments and code are placed the full version of this paper.
URL)? [Yes] The full
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The full settings of experiments are placed in the full version of this paper.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] The full experiments results are left to the full version of this paper.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] The full settings experiments placed in the full version of this paper.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material or URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/eurating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "_ZWOc-k4EW", "reviewer": "Reviewer_hEQP", "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.\n\n\n-------- Update: following the discussion at the rebuttal phase, I increased my score evaluation to 5.", "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:\n\nIf we change the model (say, from logistic regression to SVM),  then we need to find the coreset again.\nIf we change the radius of the Wasserstein ambiguity set, then we need to find the coreset again.\n\nThis 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.\n\n[I think this paper is more similar to the idea of data distillation rather than coreset]\n\n2. It is not clear how the sparsity of $W$ is imposed by the algorithm. Can the authors please elaborate on this sparsity?\n\n3. 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?\n\n4. 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. \n\n5. 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.\n\n\nMinor comments:\n- 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? ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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]. \n\nClarity: 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]\n\nSignificance: 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OSn_K7XteZ_", "reviewer": "Reviewer_TFqK", "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.", "questions": "Minor points:\n- l. 159, 237: def of $r_i$ missing $p$ as superscript?\n- l. 248: is the sentence missing a period or not finished?\n", "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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n**Strengths**\n\nThe sound theoretical analysis, clarity of writing, and significance of the contribution all sum up to a strong submission. I also appreciate how the\nauthors managed to also include experiments employing their coreset algorithm, albeit only in the Appendix.\n\n**Weaknesses**\n\nI 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.\n\nOn 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "B5iGJaNzBJ", "reviewer": "Reviewer_9nry", "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.", "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?\n- 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?\n- Can the authors compare their coreset-WDRO logistic regression with the standard one in [40]?\n- 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.\n\nMinor comments:\n- Please capitalize \"wasserstein\" in references.\n- 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- 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.\n\nWeakness:\n- 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$). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4EPFKxbF61i", "reviewer": "Reviewer_ts4N", "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.", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe 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. \nThe paper simplified the traditional coreset by solving its dual reformulation, which was innovative to a certain extent. \nThe 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.\n\nWeaknesses：\nThe experimental part of the paper was insufficient, and it was recommended to add some comparative experiments with other WDRO methods.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept