Outlier-Robust Wasserstein DRO
Authors: Sloan Nietert
Ziv Goldfeld
Soroosh Shafiee
Venue: NeurIPS 2023 poster (2023)
Keywords: distributionally robust optimization
robust statistics
optimal transport
Wasserstein distance
TL;DR: We introduce, analyze, and implement a framework for DRO which is robust to both Wasserstein and TV corruptions

Abstract: Distributionally robust optimization (DRO) is an effective approach for data-driven decision-making in the presence of uncertainty. Geometric uncertainty due to~sampling or localized perturbations of data points is captured by Wasserstein DRO (WDRO), which seeks to learn a model that performs uniformly well over a Wasserstein ball centered around the observed data distribution. However, WDRO fails to account for non-geometric perturbations such as adversarial outliers, which can greatly distort the Wasserstein distance measurement and impede the learned model. We address this gap by proposing a novel outlier-robust WDRO framework for decision-making under both geometric (Wasserstein) perturbations and non-geometric (total variation (TV)) contamination that allows an $\varepsilon$-fraction of data to be arbitrarily corrupted. We design an uncertainty set using a certain robust Wasserstein ball that accounts for both perturbation types and derive minimax optimal excess risk bounds for this procedure that explicitly capture the Wasserstein and TV risks. We prove a strong duality result that enables tractable convex reformulations and efficient computation of our outlier-robust WDRO problem. When the loss function depends only on low-dimensional features of the data, we eliminate certain dimension dependencies from the risk bounds that are unavoidable in the general setting. Finally, we present experiments validating our theory on standard regression and classification tasks.

Outlier-Robust Wasserstein DRO
Sloan Nietert Cornell University nietertêcs. coaeeeeoooeeeelleeeeeeee
Ziv Goldfeld Cornell University goldfeld@cconell.cc edu
Soroosh Shafiee Coreell University shaf chaflee@cornell. edu
Abstract
Distributionally robust optimization (DRO) is an effective approach for data-driven docision-making in the presence of uncertainty. Geometric uncertainty due to sam- pling localized perturbations of data points is captured by Wasserstein DRO (WDRO), which seeks to learn a model that performs uniformly well over a Wasser- stein ball centered around the observed data distribution. However, WDRO fails to account for non-geometric perturbations such as adversarial outliers, which can greatly distort the Wasserstein distance measurement and impede the learned model. We address this gap by proposing a novel outlier-robust WDRO framework for decision-making under both geometric (Wasserstein) perturbations and non- geometric (total variation (TV)) contamination that allows an E- e-fraction of data to arbitrarily corrupted. We design an uncertainty set using a certain robust Wasser- stein ball that accounts for both perturbation types and derive minimax optimal excess risk bounds for this procedure that explicitly capture the Wasserstein and TV risks. We prove strong duality result that enables tractable convex reformula- tions and efficient computation of our outlier-robust WDRO problem. When the loss function depends only on now-dimensional features of the data, we eliminate certain dimension dependencies from the risk bounds that are unavoidable the general setting. Finally, we present experiments validating our theory standard regression and classification tasks.
Introduction
The safety and effectiveness various operations rely on making informed, data-driven decisions in uncertain environments. Distributionally robust optimization (DRO) has emerged powerful framework for decision-making in the presence of uncertainties. In particular, Wasserstein DRO (WDRO) captures uncertainties of geometric nature, e.g., due to sampling or localized (adversarial) perturbations of the data points. The WDRO problem is a two-player zero-sum game between a learner (decision-maker), who chooses decision distribution v from an ambiguity set defined as the p- Wasserstein ball of a prescribed radius around the observed data distribution f.. Namely, WDRO is given by]l
O, and Nature (adversary), who chooses
inf BEO D. (w.
sup
Ez [C(0, 2)],
whose solution Ô E ④ is chosen to minimize risk over the Wasserstein ball with respect to (w.r.t)) the loss function É. WDRO has received considerable attention in many fields, including machine learning estimation and filtering 336
6
46), and chance constraint programming I2 55
In many practical scenarios, the observed data may be contaminated by non- geometric perturbations, such adversarial outliers. Unfortunately, the WDRO problem from I is not suited for handling this
Here, Wp(,, v) == inf in (. ||x - dz, v)) 1/P is the theepeaaeee Wasserstein metric between μ and R. where IT(44, v) is the set of all their couplings.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

issue, even a small fraction of outliers can greatly distort the W, measurement and impede decision- making. this work, we address this gap by proposing a novel outlier-robust WDRO framework that can learn well-performing decisions even in the presence of outliers. We couple it with comprehensive theory of excess risk bounds, statistical guarantees, and computationaaly--accaaale reformulations, as well as supporting numerical results.
1.1 Contributions
We consider scenario where the observed data distribution jJ is subject to both geometric (Wasser- stein) perturbations and non- gen-eeeettric (total varia- tion (TV)) contamination, which allows an e-fraction of data be arbitrarily corrupted. Namely, if j is the true (unknown) data distribution, then the Wasserstein perturbation maps it to some p'' with Wplu', p.) S p. and the TV contamination step fur- ther produces P with Í TV I (e.g., in the spe- cial case of the Huber model (28] j - (1- 1) +ea where a is an arbitrary noise distribution). To enable robust decision- decision-making under this model, we replace the Wasserstein ambiguity set in (T) with ball w.r.t. the recently proposed outlier-robust Wasserstein dis- tance W p [38 39. The W distance (see ( ahead) filters out the e- e-fraction of mass from the contami- nated distribution that contributed most to the trans- portation cost, and then measures the W, distance post-filtering. To obtain well-performing solutions for our WDRO problem, the W. ball is intersected with set that encodes standard moment assumptions the uncorrupted data distribution, which are necessary for meaningful outlier- estimation guarantees.
0
P
0
P
1 (1 - E)p + t
1 SE
Figure 1: A visual depiction of a clean measure μ (PR) and corrupted observation P(R) satisfying W5 p)) S p.
p
We establish minimax optimal excess risk bounds for the decision i that solves the proposed outlier- robust WDRO problem. The bounds control the gap EE [[0(0, Z)] - B[e(O., 2)}, where Z ~ y follows the true data distribution and 0, argming E[e(0, Z)] is the optimal decision. subject to regularity properties of l. = =(...). -). In turn, our bounds imply that the learner can make effective decisions using outlicr-robust WDRO based on the contaminated observation js, so long l. has low variational complexity. The bounds capture this complexity using the Lipschitz or Sobolev seminorms of l, and clarify the distinct effect of each perturbation (Wasserstein versus TV) on the quality of the learned solution. We further establish their minimax optimality when p 1. by providing a matching lower bound in the setting when an adversary picks a class of Lipschitz functions over which the learner must perform uniformly well. The excess risk bounds become looser as the data dimension d grows. We show that this degradation is alleviated when the loss function depends on the data only through k-dimensional affine features, by providing risk bounds that adapt instead of d.
We then move to study the computational side of the problem, which may initially appear intractable due non-convexity of the constraint set. We resolve this via a cheap preprocessing step that computes a coarse robust estimate of the mean 34 and replaces the original constraint set (that involves the true mean) with a version centered around the estimate. We adapt our excess risk bounds to this formulation and then prove strong duality theorem. The dual form is reminiscent of the one for classical WDRO with adaptations reflecting the constraint the clean distribution family and the partial transportation under WF. Under additional convexity conditions on the loss, we further derive dimensioiiii convex reformulation. The optimization results are also adapted to the setting with low-dimensional features. Using the developed machinery, we present experiments that validate our theory on simple regression//cassiicatiio tasks and demonstrate the superiority of the proposed approach over classical WRDO, when the observed data is contaminated.
an pnnciently-computabbe
1.2 Related Work
Distribationally robust optimization. The Wasserstein distance has emerged as powerful tool for modeling uncertainty in the data generating distribution. was first used to construct an ambiguity set around the empirical distribution in [40]. Recent advancements in convex reformulations and

---

approximations of the WDRO problem, as discussed in 8 20 351,
have brought notable computa- and
tional advantages. Additionally. WDRO is linked to various forms of variation 9 regularization, which contribute to its success in practice. Robust generalization
Lipschitz 7
44
guarantees can also be provided by WDRO via measure concentration argument or transportation
[1 53 544. Several works have raised concerns regarding the sensitivity of standard DRO to outliers [24 27 58). An attempt to address this was proposed in [56) using a refined risk function based on family of f-divergences. This formulation aims to prevent DRO from overfitting to potential outliers but is not robust to geometric perturbations. Further, their risk bounds require moment condition to hold uniformly over θ in contrast our bounds that depend only on 8,. We are able to address these limitations by setting a WDRO framework based on partial transportation. While partial OT has been previously used in the context of DRO problems, it was introduced to address stochastic programs with side information in 17 rather than to account for outlier robustness. Another closely related line of work is presented in 4 where the ambiguity set is constructed using an f-divergence to mitigate statistical errors and the Prokhorov distance to handle outlier data. The proposed model is both computationally efficient and statistically reliable. However, they have not investigated its minimax optimality or robustness against the Huber contamination model, which we aim to do in this paper. Additionally, best-case favorable analysis approach has been proposed in [29] to address outlier data. This approach is an alternative to the worst-case distributionally robust method. However, it requires solving a non-convex optimization problem. significantly impacting its scalability, and is not accompanied by any proof of minimax optimality.
inequalities [8] 30 31
Robust statisties. The problem of learning from data under TV e-corruptions dates back to (28). Over the years, various robust and sample-efficient estimators, particularly for mean and scale parameters, have been developed in the robust statisties community; see [4] for a comprehensive
survey. The theoretical computer science community, on the other hand, has focused on developing computationally efficient estimators that achieve optimal estimation rates in high dimensions [B] 16].
Relatedly, the probably approximate correct (PAC) learning framework has been well-studied in
[88] developed a unified robust estimation framework based on minimum distance estimation that gives sharp population- and promising finite-sample guarantees for mean and covariance estimation, as well linear regression. Their analysis centers on generalized resilience quantity, which is essential to our work. We are unaware of any results in the settings above which extend to combined TV and W, corruptions. Finally, our analysis relies on the outlier-robust Wasserstein distance from 38 39,, which was shown to yield an optimal minimum distance estimate for robust distribution estimation under Wp loss.
similar models I IQ. Recently,
2 Preliminaries
Notation. Consider closed, non-empty set 2 C Rd equipped with the Euclidean norm || I1. continuously differentiable function / 2 + R is called a-smooth if [[]())VV/(( < for all 2, z' E Z. The perspective function of lower semi-continuous (l.s.c.) and convex function I is (I A) == Xf(x=/A) for X > 0, with (2 A) = lima-so (z(=/A) when X = 0. The convex conjugate of f is f*(y)= == supzeR= y x - fxx We denote by Xa the indicator function of 2, that is. x=) = 0 if z E Z and x=(=)= = 30 otherwise. The convex conjugate of Xz. denoted by x2 is termed as the support function of Z.
al|=-=/||,
We use M(Z) for the set of signed Radon measures on 2 equipped with the TV norm TI = 22), and write μ S v for set- set-wise inequality. The class of Borel probability measures on Z is denoted by P(Z). We write [Z)] for expectation of f(Z) with Z ~ fc, when clear from the context, the random variable is dropped and we write E, Let E,, denote the covariance matrix of 1 E P2(2). Define P2(2) == (u P(2): inf 2022 F | 7 20 < oo). The forwad of if through μ E P(Z) is f= =
((f(()=)((-((())) (-),, and, for A C P(Z), write f*A= == (f# μ E A). The pth order homogeneous Sobolev (semi) of continuously differentiable f Z + R w.r.t. J I| == E,, || /|pp The set of integers up to n E N is denote by [m]] we also use the shorthand [x]+ = max f2. 0). We write S, R,
x for inequalities/equality up to absolute constants.
Classical and outlier-robust Wasserstein distances. For p E [1, co). the p- Wasserstein distance between p. E (2) is W, (H, = inf (E, [||X - ) 1/p where I( v) = { e P(Z?): T(- x Z) p. (2 22 x -) 1/3 is the set of all their couplings. Some basic properties of
3

---

Wp are (see, e.g., 42 ): (i) Wp is a metric on P2( (ii) the distance is monotone in the order, ie., Wp I Wg for p S q: and (ii) W, metrizes weak convergence plus convergence pth moments: Wp(Pn,H) u) + 0 if and only if pa + μl and [|=]|/dum (x) + ||=])=du(xx)
To handle corrupted data, we employ the s-outler-robust p- Wasserstein distance defined by inf
(2, = inf Wp(n', 1/)
Wp(u,²").
('EP(R I1 jn'=nl Sv
EEEP(R") |I'=vVITVS
The second equality is useful consequence of Lemma 4 in [39 (sce Appendix for details, along with an interpretation of W as a partial OT distance).
Robust statisties. Resilience is standard sufficient condition for population Simmi robust statistics bounds 49 188. The p- Wasserstein resilience of measure μ E ((Z) is defined by
Ep(
sup sup N'
Wp(p',p).
and that of family 9 S P(R) by (G suppes [p(,,, e). The relation between W, resilience and robust estimation is formalized in the following proposition.
Proposition (Robust estimation under Wp resilience [39). Fix 0 E S 0.49. For any clean
distribution y E G C P and corrupted measure ý E P(Z) such that W [i, μ)) S p. the minimum
distance estimate argminweg (y,,, (t) satisfies Wp p)) S p (9 2
Throughout, we focus on the bounded covariance class Geov = {u P(Z) Σ la).
Proposition 2 (Wp resilience bound for Goov (3)). Fixing 0 S & & 0.99 and 1 S S 2, we have (roon $) S s/e-/111/2.
3 Outlier-robust WDRO
We perform stochastic optimization with respect to an unknown data distribution μ., given access only corrupted version j.. We allow both localized Wasserstein perturbations, that map p to some jí' with (p) S and TV E-contamination that takes μí to fı with || μe TV S E. Equivalently, both perturbations are captured by Wp, μ1) S + To simplify notation, we henceforth suppress the dependence of the loss function É on the model parameters E O, writing é for E(0,-) for a specific function and (E(0,-) (((0,-)]eel }aee for the whole class. Our full model is as follows.
Setting A: Fix a p- Wasserstein radius 2 and TV contamination level E E [0.0.49]. Let C R E(=) be family of real- valued loss functions on 2, such that each e E is ls.cc with sup 1+||=||" < oc, and fix a class C PZ) encoding distributional assumptions. We consider the following model: Nature selects a distribution μ E 9, unknown to the learner; (ii) The learner observes a corrupted measure ja E P(Z) such that W (4) S pi
(iii) The learner selects a decision E L and suffers excess risk [,, inf 1.)
We seek a decision-making procedure for the learner which provides strong excess risk guarantees when t, = argmin c y, [{] is appropriately "simple." To achieve this, we introduce the E-outlie-- robust p- Wasserstein DRO problem:
inf
sup
[e]
(OR-WDRO)
EEC veg: (B.M))
3.1 Excess Risk Bounds
We quantify the excess risk of decisions made using OR-WDRO for the two most popular choices of order, 1, 2. Proofs are provided in Supplement B
WWile not metric. W5 is symmetric and satisfies an approximate triangle inequality (39). Proposition 3). p If a minimizer does not exist for either problem, an infimizing sequence will achieve the same guarantee. WWe defer explicit modeling of sampling to Section 3.2 but note that the following results immediately transfer to the sample setting long is taken to be larger than Wp(An, 1) with high probability.

---

Theorem (OR-W WDRO risk bound). Under Setting A, let é minimize c = 2(1 -/) the excess risk bounded by
Then, writing
1 (G, |14 (cp + (g. 28)) + ac(pp 2r,(9,
[eelltap(e 2n
1, 6. Lipschitz
E [x,[ee]
= 2, l. a-smooth
Note that c = (1) since E S 0.49. These bounds imply that the learner make effective decisions when E. has low variational C In contrast, there are simple regression settings with TV corruption that drive the excess risk of standard WDRO results as a special case of a general bound in terms of the W, regularizer, defined by Ry (2; E) == SuP/eP(() ( (K()
infinity. Our proof derives both
E. [C] E,, (.. Introduced in [18) this quantity appears implicitly throughout the WDRO literature. In particular, for each E L, derive the following bound:
E.[e] - E S Ry Cc + 2T (Tp(G.2=):))
TV
whose radius reveals the effect of each perturbation (viz. Wasserstein versus TV) the quality of the decision. The first bound of the theorem follows by plugging in p = 1 and controlling R,,1 via
Kantorovich duality. The second bound uses p 2 and controls Ry,2 by replacing with its Taylor expansion about ~ μ.. We now instantiate Theorem for the bounded covariance class Goov-
Corollary (Risk bounds for Goov). Under the setting of Theorem 1 with g S Goovs we have
[1(elltip vdl), [14 (p vd) + a(p² + +d),
p = 1, Lipschitz.
E. E.I.
p = 2, l, a-smooth
Since Goor encodes second moment constraints, T2 (2 8) is independent of e. Therefore, the first bound is preferable as & + 0 if (ell)n)a)))) R ||e I1.p. while the second is better when
8 211 and ||++|| ()) < l|e. Iipp- Distinet trade-offs observed under stronger tail bounds
like sub- Gaussiamity, i.e., for GoubG l P(Z): Eple!0' 10:00(12 (Z- (Z-R(21)² S 2, V0 Sd
Corollary 2 (Risk bounds for Gsubs)). Under the setting of Theorem 7 with G S GsubG, the excess [f=] bounded up constants by risk [4] Ex
[|e, 1le (p vd+ log odtlog! !
1, Lipschitz
||e, (eellinaa) (p+ + / (d- })² +o ( (d+ = 2, a-smooth
Remark 1 (Comparison to MDE under W We note that the excess risk Ry.p (cp + 2T, 2=); (G, from (3) can alternatively be obtained by performing standard p-WDRO with expanded radius cp 2r (9, 2s) around the minimum distance estimate j = arginingeg Wi (ū, v). However, obtaining f an expensive preprocessing step, and we are unaware of any efficient algorithms for such MDE in the finite-sample setting. In Supplement D we explore recentering WDRO around a tractable estimate obtained from iterative filtering [15), but find the resulting risk to be highly suboptimal. Furthermore. the improvements to our risk bounds under oow-dimensional structure, which are derived in Section 4 do not extend to decisions obtained from these alternative procedures.
We now show that Theorem cannot be improved in general. In particular, the first bound is minimax optimal over Lipschitz loss families when μ E Geov-
Proposition 3 (Lower bound). Fix Z = Rd and [0. 0.49). For any L > 0, there exists family L S Lipp (IR"), independent of e, such for any decision rule D : P(2) - L there exists pair (n, (i) E Genv P(2) with W (1) S p satisfying (D()) infrec [, 2 T. + vile)
Each family L encodes a multivariate regression problem. Our proof combines a one-dimensional lower bound of [49] for linear regression with lower bounds of (39 for robust estimation under W1-
'The same bounds hold up to additive slack if only a-appoxximately optimal for DR-WDDRO..
Under W perturbations, one may perform outlier-robust WDRO using any p' E [L,p] pl. which may be advantageous in terms of the TV component of the excess risk.
5

---

3.2 Statistical Guarantees
We next formalize finite-sample model and adapt our excess risk bounds to it.
Setting B: Fix P, L. 9 as in Setting A, and let Zi..... 2n be identically and independently dis- tributed (i..d.) according to μ E G, with empirical measure ji, π Di=1 6z, Upon observing these clean samples, Nature applies a Wp perturbation of size po. producing {2i}i= with empirical mea- sure N4 such that Wy (4,)) S po- Finally, Nature corrupts up to Len]] samples obtain )= with empirical measure i.n such that 1| p'llTv n Σ 1 [2, * 2,) S e. Equivalently, the final dataset satisfies W (n) S Po The learner is now tasked with selecting E & given Jin.
The results from Section apply whenever P Po Wp( (ta). In particular, we obtain the following corollary as an immediate consequence of Theorem ! and Theorem 3.1 of [32].
Corollary 3 (Finite-sample risk bounds). Under Setting B, fix
L minimizing WR-WDRR centered at ji = Pn with p 2 Pu + 100 E/,, P.)].. Then the excess risk bounds of Theorem hold with probability least 0.99. Ifg E {Geov. GsubG p 1, and d 2 3, or if = GsubG. p 2,
and d 2 5, then ((, Pn)] ] S Vdn
Remark 2 (Smaller radius). In the classic WDRO setting with Po = 0. the radius p can be taken significantly smaller than n n-14 if L and μ are sufficiently well-behaved. For example, [18] proves that p Ö(n -1/3) gives meaningful risk bounds when μ satisfies T2 transportation inequality While this high-level condition may be hard to verify in practice, Supplement [E) shows that this improvement be lifted to an instance of our outlier-robust WDRO problem.
3.3 Tractable Reformulations and Computation
For computation, we restrict to μ E Geov. Initially, WDRO may appear intractable, since Geov non-convex when viewed as a subset of the cone (2). Moreover, enforcing mem- bership to this class is non-trivial. To remedy these issues, we use a cheap preprocessing step to obtain a robust estimate 2g E of the mean E,,[Z], and we optimize over the modified class G2(a, 20) == {v E P(Z)= : Ezll - =a < )²). with o 2 || - Ez[Z]]| + vd taken so that μ E (2 Finally, for technical reasons, we switch to the oie-sided robust distance (5(ullv) = inf /nfpreeers Wp(n', Altogether, we arrive at the modified DRO problem
inf VEC (a.a)) (PA. WP)
sup
Ey
which, as stated next, admits risk bounds matching Corollary D upp to empirical approximation error. Proposition 4 (Risk bound for modified problem). Consider Setting with G S Gaov. Fix 2g E Z such that ||20- [2]| < E = O(po + vd), and suppose that Wp p)) S 6. Take E minimizing with p (po + (1 =)- TTtll//ttptpoooooo (Gcov. and a = vd E. We then have
||e. (po + Vile + +5),
p= 1, Lipschitz + + vd+ p 2, L. a-smooth
B2 1 - [,,
||e-1l (po + Vd + 8) + a
Parameters p. a are taken so that E G2(0, zo) and W (5 (1)) S Noting this, the proof mirrors that of Theorem using a Wp resilience bound for G2 =0). To ensure W (p( < 8 with decent probability, one should take 8 to be an upper bound on supveg (.Wp(on,")) When p 2, this quantity is only finite if Z is bounded or if G encodes stronger tail bounds than Goov (see, e.g., (32)).
For efficient computation, procedure for solving (4. The former is achieved by taking a coordinate- -wise trimmed mean.
must specifyy robust mean estimation algorithm to obtain 2g and
Proposition 5 (Coarse robust mean estimation). Consider Setting with G C Gauv and & S 1/3. For n = (log(d)), there is a trimmed mean procedure, which applied coordinate-wil to returns 20 E dRdd with ||--- [Z]] S vd + Po with probability at least 0.99, in time Ö
{ {2.) in
"In general, (2.)2 may be any measurable function of { (2 and independent randomness such that W5 (..)) S Po-
We say that E Tb(r) if W2(,, p) // VTH(vlpp) for all E P2(Z), where H(rl(z) is relative entropy.

---

More sophisticated methods, e.g., iterative filtering [13], achieve dimension free estimation guarantees the cost of additional sample and computational complexity. We will return to these techniques in Section 4 but overlook them for now since they do not impact worst-case excess risk bounds.
We next show that that the inner maximization problem of 4 can be simplified to minimization problem involving only two scalars provided the following assumption holds.
Assumption 1 (Slater condition 1). Given the distribution
jin and the fixed point 2o. there exists Vg ((2) such that (/) < and Ero [|| zo zoll²] o². Additionally, we require p >> O.
Notice that Assumption D iindeed holds for vn = μ as applied in Proposition
Proposition 6 (Strong duality). Under Assumption 7 for any E L and 20 Rd
have
sup (E Wij(inlluS)
Ey[e]=
inf AIRRZ
X10² X2p + +a+ 1- Ep. [(( )2,
(5)
aER
where E(2; d1, a) == suPsez [C(E) -1lle z011 - >21lE =112 - a)
The minimization problem over (A1. )2, a) is instance of stochastic convex optimization, where the expectation of the implicit function Z is taken w.r.t. the contaminated empirical measure An, In contrast, the dual reformulation for classical WDRO only involves x2 and takes the expectation of the implicit function [(2; A2) supsez {(E) A2ll< =I|? w.r.t. Ph- The additional λ variable above introduced to account for the clean family G2(o, 2a), and the of partial transportation under WE results in the introduction of the operator [+]+ and the decision variable
Remark 3 (Connection to conditional value at risk (CVaR)). The CVaR of Borel measurable loss function & acting random vector Z μ1 E P(Z) with risk level E E (0, 1) is defined
1
inf + o
Ez~z [1((Z) - aa]]
CVaR is also known as expected shortfall and is equivalent to the conditional expectation of ((Z), given that above an e threshold. This concept often used in finance to evaluate the market risk of portfolio. With this definition, the result of Proposition 6 can be written as
[e] inf \102+ +ho++app*CCalll +VVaR c.a W WS
sup vEC2(a.20):
sup ((g) -Alle zol12 >2 7
A1,22ER4
EEZ
When + 0 and 0o, whence CVaR reduces to expected value and the constrained class G2(a, 20) expands to P(Z), the dual formulation above reduces to that classical WDRO 21
Evaluating requires solving a maximization problem, which could be in itself challenging. To overcome this, we impose additional convexity assumptions, which are standard for WDRO [35 43
Assumption (Convexity condition). The loss é a pointwise maximum of finitely many concave functions, i.e., E(g) = maxje(J] (E), , for some J E N. where é, is real-valued, I.s.c., and concave" The set Z is closed and convex. The atoms of i., are the relative interior of Z.
Theorem 2 (Convex reformulation). Under Assumption for any E L satisfying Assumption and 2g E Rdd, we have
7
inf
\loz + A2pp +a M--t Eiejn) 8; a R. A1 A2 S,, Sly C. Vi A
s.t.
sup (o..( W (5
[[][[=
8, (-())* (Ct))
+ z 2 +
N,. -g + PP(C >2) + xxx - -a,
vi (m), vj E [J] viE [n], Vj E [J],
c 3 + + + + 00, 112 < X1T
where Py is the perspective function (i.e. Pr(C, >h(c/A)) of
Generallyy any continuous function can be approximated arbitrarily well by a maximum of finitely many concave functions. However, the number of functions needed may be arbitrarily large in general. Fortunately. some losses like the -o norm || max (+1) σz; require only poly(d) pieces.
7

---

p=1 X(xER* |1]))))()) (ي-1)² p>l.
(()
(6)
p ||||
The minimization problem in Theorem finite- dinensiieniio convex program. In Section use this result in conjunction with Proposition efficiently perform outlier-robust WDRO.
5
We conclude this section by characterizing the worst-case distribution, i.e., the optimal adversarial strategy, for our outlier-robust WDRO problem. To that end, we need the primal formulation below.
Theorem (Worst-case distribution), Under Assumption
1 for any i E L satisfying Assumption
and E R we have
max
- -Ensiennii1 P-e, (Cij, 9i))
s.t.
4i RR, Eúj E Edj
vi E [Ml Vi [n]
EjEM qis S m[1-c]
sup (a.20)) W. (f.
E2
EO.DENN Pij =
EOSEMMIX Pi- 9úz Zi, 9is) S
[OJEEMLII ((H Oij 2o. 9b)) S o²
The discrete distribution v* E(s)E Vi 0i achieves the worst-case expectation on the left- hand side, where (Ty (())MM))))) are optimizers of the maximization problem on the right and Q == ((i,j) E [m] x
[J] : T3 (0)>0)) 0).
The maximization problem from Theorem iss is the conjugate dual of the minimization in Theorem 2 Subsequently, we propose systematic approach for constructing discrete distribution based solution derived from the maximization problem that achieves the worst-case expected loss.
Remark 4 (Comparison to WDRO worst-case distribution). Recall that our robust WDRO approach reduces to the classic WDRO approach as = 0 and - co. Consequently, this implies that the constraints ΣE{(J ęi I 11/(n(1 2)) and (i.)ee()) P( - 20 qt)) I 0² can be dropped under this specific choice of and a. As a result, our construction simplifies to the approach presented in 35 Theorem 4.4] for WDRO problems.
Remark 5 (Parameter tuning). In practice, E, Po. and the relevant tail bound may be unknown. Thus, in Appendix we consider learning under Setting B with G Geov (a) for potentially unknown E, a, and Po. First, observe that knowledge of upper bounds these parameters is sufficient to attain risk bounds scaling in terms of said upper bounds. This approach avoids meticulous parameter tuning but may result in suboptimal risk. To efficiently match our risk bounds with known parameters, show that is necessary and sufficient to know Po and at least one of or (up to constant factors).
4 Low-Dimensional Features
While Proposition shows that the excess risk bounds from Theorem cannot be improved in general, finer guarantees can be derived when the optimal loss function depends only on k-dimennional affine features of the data. Defining g(k) the union of the projections {U # p. J 9} over U E R with UUT T0 improve the excess risk bound of Theorem for this setting.
Theorem 4 (Excess risk bound). Under Setting A, let minimize (OR-WDRO), and assume that 1/p, -11//,, have
t, Lo A for an affine map A RRd + & and some f: R* +R. Writing c=2(1=21111-- 2(1-a)
[|ealltap (cp 27 (M)), 22)), [1eall (cp+2rz2000 2=)) + jap (x)))
p 1, l, Lipschitz
E, [ - [.
p= 2,l, l, a-smooth
This dependence (k)) rather than G ((d) is substantial improvement when k < d.
If G is closed under isometries, like Goov, then (k) {U*u f E G) for any such U.

---

Corollary 4 (Risk bounds for Geov). Under the setting of Theorem
4 with g - Geov, we have
[1e vkE). [1l + vk) + alp² + +k), p - 2, l. a-smooth.
p = 1, l. Lipschitz
1 - [x(e.
We again have matching lower bound for the Lipschitz setting, this time using k-variate regression. Proposition 7 (Lower bound). Fix 2 = R2 and E [0, 0.49.. For any 2 0, there exists family C - L (IRC), independent of E, such that each E L decomposes as E = & A for A E R Rxx and I2 + RR and such that for any decision rule D: : P(2) + L there exists a pair (H, pi) E Gcov x P(Z) with (i (1) S satisfying [a)] - infrec [, 2 L(p Vk+v/
For computation, we turn to slightly modified n-sample contamination model. Our analysis for the low-dimensional case only supports additive TV corruptions (sometimes called Huber contamination).
Setting B': Fix p. S, C. G as in Setting A, and fix m [(1 a)nl for some n E N. Let Zi,..., Z. be drawn i.i.d. from E G, with empirical measure jim = 1 2 i-1 8x,- Upon observing these clean samples, Nature applics a Wp perturbation of size po. producing { { with empirical measure p'n such that Wp pmm) S po. Finally, Nature adds [sn] samples to obtain [Z:) with empirical measure j.n such that I'm S lin Equivalently, the final dataset satisfies W (pnmillimm)) S Po-
As before, we modify (OR- WDRO) using a centered alternative to Geov- Defining Scov((: zu) = o² Ja), we consider the outlier-robust WDRO problem
{u E P(Z): : I[Z - =0 - 20)
inf EEC
sup véSeov ( (or,a)):W (P
[e]
To start, provide corresponding risk bound which matches Corollary when k = O(1).
4
Proposition 8 (Risk bound for modified problem). Consider Setting B' with S Gcov. and assume
l. = L A for affine A Rd - B and { Rt +R Fix 20 Z such that |0 |,| S E
O(po + 1). and assume W, Wp( 1)) S 5. If minimizes 7 with = Po + 8 and 1 1 E, then
[1e.lluap (Vipo + Vkk +ō),
p = 1, f. Lipschitz
1, E
[1 + vk + 8) + (VTspo + vk++)
p = 2, l, a-smooth
Here, the stronger requirement for the robust mean estimate, the restriction to additive contamination, and the need to optimize over the centered Geov class rather than G2 all stem from the fact that the resilience term Tp((Gew)): ),,e) scales with vi rather than vd. Fortunately, efficient computation still possible. First, we employ iterative filtering [15] for dimension-free robust mean estimation.
Proposition (Refined robust mean estimation). Consider Setting B or B' with G = Goov and E S 1/12. For ((d),, there exists an iterative filtering algorithm which takes ju, as input. runs in time Ö(nd)), and outputs 2o E IRd such that || - E,, S po + with probability at least 0.99.
The analysis requires care when = 1, since W1 perturbations can arbitrarily increase the initial covariance bound. Fortunately, this increase can be controlled by trimming out few samples.
Next, we show that computing the inner worst-case expectation in (7) can be simplified into a minimization problem involving only a scalar and positive semidefinite matrix provided the following assumption holds (which is indeed the case in the setting of Proposition 88)
Assumption 3 (Slater condition II). Given the distribution jú,, and fixed point 20, there exists vo E P2)) such that W (f((alllo)) < and Eu, [[2 - - 20) - zo) 1 Ia. Further, we require p O. Proposition 10 (Strong duality). Under Assumption for any & E L and E Rd,, we have
- t +a+ 1- 1
sup DEGoow (d.20):
[e] =
inf Are
Tr(Ai]
Ex [[(: a2)]
W, [pp
AdER .aER
where 7(2; A2, = supeez [((E) - T A1 A211s - 21I² - -
The minimization problem over the variables (A1, Ag, a) belongs to the class of stochastic convex optimization problems. As before, show that under the convexity condition from Assumption we obtain a tractable reformulation that does not involve extra optimization problem for evaluating غ

---

Theorem 5 (Convex reformulation). Under Assumption 3 for any l E L satisfying Assumption and 2g E R we have
inf
- A120 + o² Tr[Ai] + 22p + a mI-e) Eie(n) i8
8.b.
a A1 E Q4, 22 E R,, S RT,
Ty E R Si.. Sij 52 E R
sup E, (EGoor(a,2)) W; (P
8 x (-()))))( + Tij + 2, Sij
+ PP x2) X2 a, We M /A M [J]
+ + where Pa is the perspective function of h defined in 6
2 =o, ( 3/ <AT Wi [
5 Experiments
Lastly, we implement our tractable reformulations and validate their excess risk bounds. Fixing 2 X x y = Rd-1 x R. we focus on linear regres- sion with the mean absolute deviation loss, i.e.,
Excess Risk for Varied 5 Sample Size and M Method
excess risk (mesr stoskktt devistion)
standard
OR-WARR R
OR WE--ORRD w/ w OR WORO w/ -
2.5
L = (t)(x, - 10 x yl : 0 E RR.. The ex- periments below were run in 80 minutes on an M1
MacBook Air with 16GB RAM. See Supplement [ for full details and additional experiments treating classification and multivariate regression. Code
available at https://ggi thub. com/ sbnietert/ outlier-robust- WDRO
22
55
60
70
300
#samples
Fix 2 = Rdd for d 2, = 0.1, and 0, gd-2 Taking X ~ (0, we fix clean data (X,0TX) ~ a and corrupted data (X,Y) ~ ā such that (X, Y) = (X.0, X p) with probability
Excess Risk for Varied Dimension and Method
12-
Jmean absolue deviatton)
OR-WORD =G,
OR WORD W/G -G
1 1- and (X,
X) with probabil-
2.6
ity e, so that
fix d 10, p (ūll)))) S p. In Figure ? (top), we 8 and compare the excess risk
3.0
Eg1oo [., of standard WDRO and outlier- robust WDRO with G = G2. described by Propo- sition and implemented via Theorem 2 The re- sults are averaged over T 20 runs for sample size E {10, 20, 50, 75, 100). We run outlier-robust WDRO with corruption fraction E e0 achiev- ing low excess risk when & 2 e as predicted. In (bottom)) highlight the Section[Jimprove. ments due to low-dimensional structure, we fix n = 20, C = 100 and compare the excess risk of oublier-rouust WDRO with G = G2 to that with G = Goov, as described by Proposition and implemented via Theorem 5 We average over T = 10 runs and present results for dimension de (5, 10, 25, 40). Confidence bands in both plots depict the top and bottom 10% quantiles among 100 bootstrapped means from the I' runs. Implementations were performed in MATLAB using the YALMIP toolbox
12
10
20
25
30
dimension
Figure Excess risk of standard WDRO and several forms of outlier- robust WDRO for linear regression under W, and TV corruptions, with varied sample size and dimension.
33 and the Gurobi and SeDuMi solvers 23 50
6 Concluding Remarks
In this work, we have introduced a novel framework for outlier-robust WDRO that allows for both geometric and non-gcometric perturbations of the data distribution, as captured by W, and TV, respectively. We provided minimax optimal excess risk bounds and strong duality results, with the latter enabling efficient computation via convex reformulations. There numerous directions for future work, including refined statistical guarantees for & Po + -1/d and convex reformulations for distribution families beyond Geov- Overall, our approach enables principled, data-driven decision- making in realistic scenarios where observations may be subject to adversarial contamination.
10

---

References
[1] D. Angluin and P. Laird. Learning from noisy examples. Machine Learning, 2:343-370, 1988.
[2] D. Bartl, S. Drapeau, J. Obloj, and J. Wiesel, Robust uncertainty sensitivity analysis. arXiv preprint arXiv:2006. /2022, 2020.
[3] A. Ben-Tal and M. Teboulle. An old-new concept of convex risk measures: The optimized certainty equivalent. Mathematical Finance, 17(3):449-476, 2007.
[4] A. Bennouna, R. Lucas, and B. Van Parys. Certified robust neural networks: Generalization and corruption resistance. In International Conference on Machine Learning. 2023.
[5] A. Bennouna and B. Van Parys. Holistic robust data-driven decisions. arXiv preprint arXiv:2207.09560, 2022.
[6] Blanchet, W. Glynn, J. Yan, and Zhou. Multivariate distributionally robust convex regression under absolute error loss. In Advances in Neural Information Processing Systems, 2019.
[7] J. Blanchet, Y. Kang, and K. Murthy. Robust Wasserstein profile inference and applications to machine learning. Journal of Applied Probability, 56(3):830- 857, 2019.
[8] Blanchet and K. Murthy. Quantifying distributional model risk via optimal transport. Mathe- matics of Operations Research, 44(2):565-66) 600, 2019.
[9] J. Blanchet, K. Murthy, and N. Si. Confidence regions in Wasserstein distributionally robust estimation. Biometrika, 109(2):25--315, 2022.
[10] N. H. Bshouty, N. Eiron, and E. Kushilevitz. PAC learning with nasty noise. Theoretical Computer Science, 288(2):255-217 275, 2002.
[11] R. Chen and I. Paschalidis. robust learning approach for regression models based on distributionally robust optimization. Journal of Machine Learning Research, 19(1)5517-564 2018.
[12] Z. Chen, D. Kuhn, and W. Wiesemann. Data-driven chance constrained programs over Wasser- stein balls. Operations Research (Forthcoming). 2022.
[13] Y. Cheng, I. Diakonikolas, and R. Ge. High-dimensional robust mean estimation in nearly-lineas time. In ACM-SIAM Symposium on Discrete Algorithms, 2019.
[14] L. Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142, 2012.
[15] Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and Stewart. Being robust (in high dimensions) can be practical. In International Conference on Machine Learning, 2017.
[16] I. Diakonikolas and D. Kane. Algorithm High- DieeenDimessin Robust Statistics. Cambridge University Press, 2022.
[17] A. Esteban- and J. M. Morales. Distributionally robust stochastic programs with side information based on trimmings. Mathematical Programming. 195(1-2):1069-1100 2022.
[18] R. Gao. Finite-sample guarantees for Wasserstein distributionally robust optimization: Breaking the curse of dimensionality, Operations Research (Forthcoming). 2022.
[19] R. Gao, X. Chen, and A. J. Kleywegt. Wasserstein distributionally robust optimization and variation regularization. Operations Research (Forthcoming). 2022.
[20] R. Gao and A. Kleywegt. Distributionally robust stochastic optimization with Wasserstein distance. Mathematics of Operations Research, 4 2023.
[21] R. Gao and Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. Mathematics of Operations Research, 48(2):603-655. 2023.

---

[22] R. Gao, L. Xie, Y. Xie. and H. Xu. Robust hypothesis testing using Wasserstein uncertainty sets, Advances in Neural Information Processing Systems, 2018.
[23] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https://tww/ /wW surobi.com
[24] T. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang. Fairness without demographies in repeated loss minimization. International Conference on Machine Learning. 2018.
[25] J.-B. Hiriart-Urruty and C. Lemaréchal. Fundamentals of Convex Analysis. Springer. 2004.
[26] S. Hopkins, J. Li, and F. Zhang. Robust and heavy-tailed mean estimation made simple, via regret minimization. In Advances in Neural Information Processing Systems, 2020.
[27] W. Hu, G. Niu, I. Sato, and M. Sugiyama. Does distributionally robust supervised learning give robust classifiers? In International Conference on Machine Learning, 2018
[28] J. Huber. Robust Estimation of Location Parameter. The Annals of Mathematical Statistics, 35(1):73-101, 1964.
[29] N. Jiang and W. Xie. Distributionally favorable optimization: A framework for data-driven makisi with endogenous outliers. Optimization Online, 2023.
[30] Y. Kwon, W. Kim, J.-H. Won, and M. C. Paik. Principled learning method for Wasserstein distributionally robust optimization with local perturbations. In International Conference on Machine Learning, 2020.
[31] Lee and M. Raginsky. Minimax statistical learning with Wasserstein distances. In Advances in Neural Information Processing Systems, 2018.
[32] Lei. Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces. Bernoulli, 26(1):767 - 798, 2020.
[33] Lofberg. YALMIP: toolbox for modeling and optimization in MATLAB. IEEE international conference robotics and automation, pages 284-289. IEEE, 2004.
[34] G. Lugosi and S. Mendelson. Robust multivariate mean estimation: the optimality of trimmed mean. The Annals of Statistics, 49(1):393-44) 410, 2021.
[35] Mohajerin Esfahani and D. Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1-2):115-
2018
[36] V. A. Nguyen, D. Kuhn, and P. Mohajerin Esfahani. Distributionally robust inverse covariance estimation: The Wasserstein shrinkage estimator. Operations Research, 70(1):490-515, 2022.
[37] V. A. Nguyen, S. Saafferzaaeh-bbadeee D. Kuhn, and P. Mohajerin Esfahani. Bridging Bayesian and minimax mean square eгror estimation via Wasserstein distributionally robust optimization. Mathematics of Operations Research, 48( 1)31, 2023.
[38] S. Nietert, R. Cummings, and Z.. Goldfeld. Outlier-robust optimal transport: duality, structure, and statistical analysis. In International Conference on Artificial Intelligence and Statisties, 2022.
[39] S. Nietert, R. Cummings, and Z. Goldfeld. Robust estimation under the Wasserstein distance. arXiv preprint arX1v:2302.01237, 2023.
[40] G. Pflug and D. Wozabal. Ambiguity in portfolio selection. Quantitative Finance, 7(4):435 442, 2007.
[41] E. M. Ronchetti and P. J. Huber. Robust Statistics. John Wiley & Sons Hoboken, 2009.
[42] F. Santambrogio. Optimal Transport for Applied Mathematicians. Springer, 2015.
12

---

[43] S. Setfieezaaeh-Abbaaee L. Aolaritei, F. Dörfler, and D. Kuhn. New perspectives on regular- ization and computation optimal transport-base baseed distributionally robust optimization. arXiv preprini 230xv:2303330000, 2023.
[44] S. Shafieezadeh-Abadee D. Kuhn, and P. Mohajerin Esfahani. Regularization via mass trans- portation. Journal of Machine Learning Research, 20(103):1-68 2019.
[45] S. Shafieezadeh-Abadeh P. Mohajerin Esfahani, and D. Kuhn. Distributionally robust logistic regression. In Advances in Neural Information Processing Systems, 2015.
[46] S. Shaficezadeh-Abadee V. A. Nguyen, D. Kuhn, and P. Mohajerin Esfahani. Wasserstein distributionally robust Kalman filtering, In Advances in Neural Information Processing Systems, 2018.
[47] A. Shapiro. On duality theory of conic linear problems. In M. Á. Goberna and M. López, editors, Semi-Infinite Programming, pages 135-165. Kluwer Academic Publishers, 2001.
[48] A. Sinha, H. Namkoong, and J. Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference on Learning Representations, 2018.
[49] Steinhardt, M. Charikar, and G. Valiant. Resilience: A criterion for learning in the presence of arbitrary outliers. In Innovations in Theoretical Computer Science Conference, 2018.
[50] F. Sturm. Using SeDuMi 1.02, A MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 1((14))625-653, 1999.
[51] 7. Tu, J. Zhang, and D. Tao. Theoretical analysis of adversarial learning: A minimax approach. In Advances Neural Information Processing Systems, 2019.
[52] C. Villani. Topics in Optimal Transportation. American Mathematical Society, 2003.
[53] R. Volpi, H. Namkoong, O. Sener, J. Duchi, V. Murino, and S. Savarese. Generalizing to unseen domains via adversarial data augmentation. In Advances in Neural Information Processing Systems, pages 5339-5349, 2018.
[54] Y. Wang, X. Ma, J. Bailey, J. Yi, B. Zhou, and Q Gu. On the convergence and robustness of adversarial training. International Conference on Machine Learning, 2019.
[55] W. Xie. On distributionally robust chance constrained programs with Wasserstein distance. Mathematical Programming, 186(1):115-155, 2021.
(56) R. Zhai, C. Dan, Z. Kolter, and P. Ravikumar. DORO: Distributional and outlier robust optimization. In International Conference on Machine Learning, 2021.
[57] J. Zhen, D. Kuhn, and W. Wiesemann. A unified theory of robust and distributionally robust op- timization via the prinall-oost-epaal--dlll---ss principle. Operations Research (Forthcoming). 2023.
[58] B. Zhu, J. Jiao, and J. Steinhardt. Generalized resilience and robust statistics. The Annals of Statistics, 50(4):2256 2283, 2022.
[59] S. Zhu, L. Xie, M. Zhang, R. Gao, and Xie. Distributionally robust weighted k-nearest neighbors. In Advances in Neural Information Processing Systems, 2022.
13

---

A Preliminary Results on Robust OT and Wasserstein DRO
We first recall properties of the robust Wasserstein distance W; which will be used throughout the supplement. To start, we show that our definition coincides with another based on partial OT, considered in [39]. In what follows, we fix p 2 1, write cP(2) = {cp : P(2)), and, for J., c2),), we define II,,,)) = cll(p/c,v/ v/c) and Wp(n, v)" = cWp(u/e,//c).
Lemma (W5 as partial OT). Fix E [0, 11. For any U, E P(Z), we have
wz(,,)) = inf Vp(m',v) ('EP(Z) II/'SE
inf
Wp(u,v))
inf Wp(u',/), ('('E(1-3)P((2) / S'S
a (2EP(Z) -uIlTVE
Proof. We write W (4, v/) for the rightmost expression; this is definition of W. considered in [3). We first show that W (1, I Wā(,, v). Fix any je' feasible for the W problem. Then, by the approximate triangle inequality for Wž, (Proposition 3 of (39),, we have
W W v) S (H, W, v) S W))
Indeed, writing c = (n (2) 2 1 - e, the last inequality uses that W (M, n²) S W n', = = O. Infimizing over feasible μ' gives that (5( v) S (5( v).
For the other direction, take any p², n',v' feasible for the W. problem. Let т E 11(H,, v') be any optimal coupling for the Wp(u', ,²) problem, and write μ² =p' -v (u- v/) E P(Z). Defining the coupling n' (Id, Id) Id) v') ))E M(n", p), compute
/
"p(u",u)e
x ull dn (x, =
|| u11 d=(x,)) Wp(kl,z))
2x2
zxz
By construction, ||~" U||TV s, and so W5(,,)) S Wp(u', v/) Infimizing over feasible μl, gives that u) < (1, v).
We thus inherit several results for W, given in 39
Lemma 2 (Approximate triangle inequality (3)). J,
E P(Z) and 61, [0, 11, then W (j4, D) W (1, + W (K, v)-
Lemma (W5 modulus of continuity, [39], Lemma 3). For any 9 S P(Z), we have
W,(a, (1 1/2 2T (9,
sup
a,9 (S,
Lemma (One-sided vs. two-sided WS.. For u, V E P(Z). we have
(H S (1 -1 -1p-) (p, (p,
Proof. Fix any 1/, (1 - =)P(() with p' S μ and v/ <v.. By design, we have W5(H(lb) S Wo (o(
S Wp(i-et' = (1 -//WW ( v') + (U,
+ WW
Infimizing over pl and v and applying Lemmal
giiees the lemma.
Next, we specify explicit constants for the W, resilience of Geov. Our analysis goes through the related notion of mean resilience 44), defined by T(H,E) sup , E [Z] E,, [|]
We say that Z Lemma 5 (W, resilience for G2 and Geou). Fix s E [0,1) and 2 0. For 1 < < 2, we have sG) < 1/e1/p-1/2 -1/p, Moreover, we have Tp (Goov s) < (p2
P(Z) is (ro, e)-resilient in mean under W, if μ E T(TO, s) or μ E (T. e).
14

---

Proof. Fix any Z ~ E G2(0, 20). By definition, we have E[[ - 20|1)) = Ei|l - 20 -
o² = (o Thus, standard bounds (c.g., Lemma E.2 of (58) give that || - 2o is (
,)- re-rsiiieet in mean. By Lemma 7 of [39], we thus have that Z is (20E//-112(11
2e 2, rrrssilett under Wp. This gives the first result. For the second, we observe that for Z ~ 14 E Sco we have Bi|l [E[ tr(Ep) S vdo.
Lastly, we turn to the W, regularizer.
Lemma (Controlling Wp regularizer, [8. Lemmas and 2). For any 8 E we have Rv (p: !) S
pllp with equality if E is convex. For a-smooth E, we have [R (p; f) - p pllel S
aap
The factor of 1/2 under smoothness was not present in Lemma 2 of [1]. since the proof only used
that (()))=((x))) ((=)) (=n) (= - =0)1 S al|= zoll². instead of the tight upper bound of / ||| =ol? -
This quantity naturally bounds the excess risk of standard WDRO.
Lemma 7 (WDRO excess risk bound). Under Setting A with & = O, the standard WDRO estimate
argminngg wttppuuuuuuPPP) Ey]d] satisfies E, [,, S Ru L.).
Proof. We bound
E,A Eple,]
sup vEP(Z) Sy
Ey10] Eple.]
(Wp(u.P) S p)
sup vEP(Z)
[y[c,] - [.1
(optimality of è
Wp(MA)Sp
sup
Ey[C.] - F.,.
(W, triangle inequality)
vEP(2)
Wplusu)S2p
(2p la):
as desired.
Note that this bound does not incorporate the distributional assumptions encoded by G.
B Proofs for Section 3
B.1 Proof of Theorem i
We compute
[e En[ V
sup PEg
Ey[ [.
(p G. W5(ū, S p)
sup PEg
[x[ - [.
( optimal for OR- WDRO
SP
sup Pgg
Ex E.
(Lemma
W (M.P)
sup PEg
[y - [,
(Lemma 3
sup >EP(Z) W,(em)550422,,(0225
E [e] 10
(g C P(Z))
Rup (cp + 2T, (G, 2)
Combining this bound with Lemma 6 gives the theorem.
15

---

B.2 Proof of Corollary 1
The corollary follows as an immediate consequence Theorem and the resilience bounds of Proposition
B.3 Proof of Corollary 2
The corollary follows
immediate consequence of Theorem | and the resilience bound Tp Tp(Suub,,)) & Vd + p-pp-+ p+ log e// established in 33 Theorem 2].
B.4 Proof of Proposition
For ease of presentation, suppose 2m even. Consider Rd as R x R fix w R with ||m|| = and let L consist of the following loss functions:
l- y) L|( + y
l- y) = L|| y/
(x, L|| + y- w|
L (xr = L|| - y - -yl
Fixing corrupted measure do. we consider the following candidates for the clean measure ja:
14,0 = (1 =) + = (0,
p=_0 (1 =)6 1c)
μ4,1 = (1 (
+ - =dd (O, Ia/E)
|-,1 == (1 - =) =
La/e),
where Td is the identity map. By design, ( (olllooo)) (i(lll++))) and Wi (i(lll,,,1) are all at most and p4.00, M- 11,1, P-11 Goov. Moreover,
14,00 Ep-,o ll Ep-, [(+..] Ey_,, [6-1]] =0
_l = Ep .o 1..4.ol = Ep 1 = E,, [[+,,1] = 2L B2- Lvde Ey,, !e_,o
Ex [4,1l = -E44, [e_ -l_, = Ep_,, [l_ = L||w||| = Lp.
Thus, for any & = D(Ā) E C. there exists μ E {u- 1- o, u4, 14.1I W_,1 } such that
EEC E [ inf 1,, [. 2 L max(p, v vd L(p
B.5
Proof of Proposition
Since j Goov. have
Ep [|| 20|1
< E, Z - [,[111 + E2 - 20ll
= =rr(",) : + |, zoll
I Vd + |2, zoll S
Consequently, we have μ E G2(a, 20). Next, we bound
(5(mmllm)) = inf
Wp(P,
vEP(Z)
"$ TLL
inf uN (2ZE)(Z) Wp(x, n²) Wo(p(,
vs 1 Pr.
inf Ky (2) Mp(p,H') + Tp(M,E)
(definition of Tp)
vS Ph
16

---

(1 5) i W (Mn, (4) + (1(
(Lemma
$ (1 - c) (po + 8) + Tp Ec =.
Writing g' = G2(a, zo) and mirroring the proof of Theorem
|
we have for each & E L that
E
E, <
sup WEG' w (
RE [e] Ex(()
sup VEG' W
Ep - EE
@e optimal for 4
sup MEg' w (2.
Be - E,,!
(I (Lemma
sup VEg'
E2 En[d]
(Lemma
Wo(thw)sopt2rp(0)
sup vEP(Z)
Ey [e] - E
Wn(m:w)Sopt21p(99
Ruplccp+ 2Tp ,
S Rn (cp 80 (2e) 2 2=) 2::)
(Lemma 5
When p 1, we bound the regularizer radius by
cp 2E - 2=) 2 Po - 8 TI (9cov, c) + (Vd+ + $ Po P Vdd,
using Lemma 5 Similarly, when p
bound the radius by
cp + 80 2=) S Po + 5 + (2 é) + (Vd + po) S Pa 8 Vd.
Taking { == l, and applying Lemma 7 gives the proposition.
B.6 Proof of Proposition
To start, we fix d 1. Given 0 < and E P(R) with cumulative distribution function (CDF) Fe, define the t-timmmin Tv( E P(R) as the law of F-1 (U), where U ~ Unif([>, 1 - and let m. (v) = Er, [z) denote the y-trimmed mean. If v |Al ΣaEA A da is uniform over
finite set {al 02
an) and yn an integer, have (, (I-24)m Ei at.
Our robust mean estimate when 1 is 2g = my (j²)) with 7 = 1/3. The smaller choice of y = gives tighter guarantees at the cost of increased sample complexity; we keep the larger choice since we only require a coarse estimate.
Lemma 8. Consider Setting B with d = L Geov. PD 0. E S 1/3. Fix sample size n ((lol((/))) for 0 < 1/2. Then, |m,((pn) - Ep [2]] S with probability at least - 8.
Proof. This follows by Proposition 1.18 of [16] applied to the distribution j with corruption fraction 7, = 4y/3 < 1/2, and resilience bound r(Goov,2 S vT S 1.
Now, since we free to permute the order of the TV and W, corruptions (see Lemmal 1. there exist {W R with empirical measure 24, E ((R) such that ||l 1ia--fan Pulllr S and W (Z (in.4p Pn) I Pa- By Lemma 8 have (v,) E, [Z] S 1. Of course,
do not observe Vn, so this result is not immediately useful. To apply this fact, we use that T,, is an approximate Wasserstein contraction.
Lemma 9. a 3 E P(R) and 0 S < 1/2, then (T,T((a), (5)) & - (1-27) -/PW> B).
Proof. Writing Fa and Fg for the CDFs of a and respectively, we compute
W,(T,((a), (,))) 1 2
F (1) Fg (1)
17

---

1 24 [ (1a (1) 1- 2y
as desired.
Applying Lemma 9 we bound
(pa)
En|2]|
_ mm (un) - E,12 + - my (Px)
mm (Vn) |, (l(T,(um)) ((n))
+ W1 (Prr, Ain)
1 + Po-
This matches the proposition statement when d =
For general > 1, we propose the coordinate-wise trimmed estimate 20 E TRd given by (z0); (e, s (.). Plugging in t- 1/(100d) into Lemma g and taking a union bound over coordinates, we condition on the 0.99 probability event that the one-dimensional bound holds for all coordinates. We can then bound
d (m (e) (ūn)) Eulee 21)
= - E
x + Σ Wiee # pn eJ kim)
< + W (1 (2)
$ + pb:
as desired. The penultimate inequality is a consequence of the reverse Minkowski inequality. Lemma 10. Fix a, 3 E P(Rd) Write a; = or # a and 3: c. 3, E for their coordinate-wise marginals. We then have
Σ Wi WI(,,)))
(8)
Proof. Take (X, Y) to be an optimal coupling for the (i B) problem. Writing A; || 1Y;-XX x, for E [d], the right hand side of (8) can written as the 1/2 norm Σ Allh/2. We then bound
d
d Σ
Wi(ai, 3,)² < Σ 1Aali S
A
1/2
where the final inequality follows by the reverse Minkowski inequality for I,2/2
B.7 Proof of Proposition
We have
E. - zoll3 S 0²,
sup rEG2(o,00): WS(A, IP)SP
[e]
sup M¹ vEP(Z)
Eele]
Ez Z' Z|1"] S p":
n² < 1 An
a Ell .v)
Exe(nl m, By, ||| 20|1 S o².
Σ Evenn m, Ex, |||2, - 2, S p",
sup MER" M. (2)
Σ #EIn
m; E,, [e]
0 S my S mi-Ea Vi E [n]
Eiejnl mi = 1
where the first equality follows from the definitions of G2 20) and W (5 The second equality holds because inn 1 Eie(n) Öz,, which implies that the distributions μí, and take the form
18

---

u'= u'=EEe EiEn v= may, and T = mzdz, & v4, respectively. Note that the distribution models the probability distribution of the random variable Z condition on the event that Z' 3, Using the definition of the expectation operator and introducing the positive measure i/ myy for every i E [no], we arrive at
Eiejn] S2 |12 20 (2)vv((() S so²,
Σiginl S2 || dz)) S pp,
sup (o Wy (5x
Ey = sup
Σ Bu:10]: 0 mi m(1-s] Vi [n],
mER"
Mun 20
iE(n]
E (i)nn] my =
Jz dv (z:) mi, vi [n]]
s 2 max (o, r; a}, Vi E [n],
Aoo + A2p + +a+ + Eieln] 8i n(1 E)
inf AR r.RER", .aER
2 ((E) - >11l5 - zol 2 - x21l - Z, lp:
AA E 2, vi E [n]
where the second equality follows from strong duality, which holds because the Slater condition outlined in [47 Proposition 3.4] is satisfied thanks to Assumption] [ The proof concludes by removing
the decision variables r and and using the definition of pn.
B.8 Proof of Theorem 2
The proof requires the following preparatory lemma. We say that the function f is proper f(z) > -oo and dom(f) * 0.
Lemma 11. The The followings hold.
(i) Let f(x) >g(x= - zo), where A 2 and Rdd - R is l...c and convex. Then,
f'(y) = u + Ag"(y/A)
(ii) Let f(x) = || for some p 2 1. Then, (y( = h(y). where the function is defined as in (6).
(iii) Let f(x) = x Ex for some Σ > 0. Then, f f(y) = t.0" Σー -yyEE1 y-
Proof. The claims follows from 25 S Proposition 1.3.1 ]. 57
Lemma B.8 (ii)) and 25
SE,
Example 1.1.3), respectively.
Proof of Theorem
By Proposition 6 and exploiting the definition of A.. we have
inf aor² + A2p" +a+ + m(1-e) Eis(n) 81
s.t. a a R, X1, A2 E R4, 8 E ERRT
sup :o))( W, 1PP)PP
E =
8, 2 sup E(L) - >>alle- - -2012- A2llE - Z,I1p - a Vi E [n]
EEZ
inf 2 + >up + m(1-s) Eie(m) 84
1
s.t.
R. \1 X E RR, $ RT
8, 2 sup (E) - -1llE- - =0ll2
EEZ
-X2115 Ze (nl
where the second equality follows form Assumption
2 For any fixed i E [n] and j E [J]. we have
sup (E(E) >11le 20 d21lE 2.
EEZ
inf (ct) + + + mj + 27 cT + PMlc +x) -a
s.t. Ti RR, C3.,, E Rd, ct + + + =0, |c, < A1T
19

---

where the equality is result of strong duality due to [77 Theorem 2] and Lemma 11 The claim follows by substituting all resulting dual minimization problems into ( and eliminating the corre- sponding minimization operators.
n
B.9
Proof of Theorem 3
Thanks to Remark
we have
sup vEDr(a,20): 1V
Ep
inf A1,22ER
\10² X2pp + CVaRR-e,f.
sup {(E) SEZ
-11l55- - -2ol1- -2ol?->xup -22lls -11"
inf
sup
\10² A2p +
Σ sE/n]
m4
sup KEZ
E(E)
A1llE -oll? 2 -2111 Z
A2,2gER meM,
where M₁ == {m E E4 : my S 1/(nn11- =)), vi E [n]. Eienn m, 1}. and the equality follows
-
from the primal representation of the CVaR as coherent risk measure Example 4. and the fact that Pn is discrete. By Assumption
2
we have
sup meM,
Σ
m; sup gEZ
E(E)
>11lE 20112 111-- --221e- 2:11"
iE|n]
sup sup Σ meM, 2 iE/n]
((Eig) A1 XIllEej -zol? 2 ->2llEej 1//1"
mi max (E(J]
4ss ((E))) - A111s, 20112 xel1EN Z
sup sup gEC, E2 (LJ)El
where Q. = {q E RRXJ EjEMJ 9- S -(i-,). Vi [m]. (L.)EMMi hi 1}, and the last equality easily follows by introducing the variables 9ú as means to merge the variables m, and the maximum operator. Note that the final supremum problem is nonconvex linearity between 9tj and Eiy. Using the definition of the perspective function and the simple variable substitution Eig Eig/qtj. however, one convexify this problem and arrive at
have bi-
sup vEGg(m.)))= (F.
Ex = inf ALA
sup qEQ. 2
{ {oYKz + A2p
Σ
(1E))
P111111 Zizzo 9is) 122 Uz 95)
Note that strong duality holds similar to the proof of [57 Section 6]. This allows to interchange the infimum and supremum without changing the optimal value the problem. Then, infimizing over λ₁ and λe and noticing that the resulting supremum problem is solvable, since the feasible set is compact, conclude the first part of the proof. Following the discussion in [57] & 6]. is easy to show that the proposed discrete distribution v" solves the worst-case expectation problem. The details omitted for brevity. This concludes the proof.
C Proofs for Section
C.1 Proof of Theorem 4
We start with the following lemma.
Lemma 12. Under the setting of Theorem we may decompose t.- = -o Q Q Baxd with
QQT Ty and some e R d For any such decomposition, we have
sup
Ey[fa]
sup
VEG
DEG
W (M.
20

---

Proof. To start, we decompose A(2) RQ + 20. where Q E R with QQT = I4, R R and 2g E RR* Note that the orthogonality condition ensures that Q" isometrically embeds IR* into R We then choose ((w)= [(wtw + 20).
Next, given v E 9, we have Q# E (()) with W @# & (e(u, and [y E Thus, the RHS supremum is always least large as the LHS. It remains show the reverse.
Fix 9 with (K, @.) Take any v' (((TR)) with (,(u, S p and I| - Q S 6.
Write x = Q E 9 and x' = Q Since Q is an isometric embedding, we have & E g,
(,,,,, x²) W,(,,v/) S p. and | TV | Q# pl|TV E. Finally, we have E, E, 1
Thus, the RHS supremum is no greater than the LHS, and we have the desired equality.
Writing Pa = #1, we mirror the proof of Theorem 1 and bound
E 1.
sup MEg Wj. (
Ep[e] E,[c.]
(p G. W W5 S)
sup wec W (R.P))
[x[ - (e,)
( optimal for (OR-WDRO)
sup vegik) a
[y Eyn 1
(Lemma 12
sup peg(A) Wf (vi
E, Bus 18]
(Lemma
sup veg(t
Eg E [e]
(Lemma
2c)
sup
EyI -Bual
(G S P(2))
MEP(2)
W,((m=)) (g .2))
Rpu. (ep + 2T (G 2));
To obtain the theorem, we apply Lemma 6 and observe that [|ε]|Lip = I|c:1lap and [
[|e. (1 (since QT an isometric embedding from g* into R2)).
C.2 Proof of Corollary
This follows an immediate consequence of Theorem 4 Hand Corollary
1
C.3 Proof of Proposition 7
We simply instantiate the lower bound construction from Proposition in R viewed subspace of Rd Extending each E L to Rd by f(z) = ((21k)), the same lower bound applies with d +- k. 0
C.4 Proof of Proposition g
For Z ~ E Goov and 20, w E Rdd, we bound
E E(w² (Z - 20)(2 - 20) Tw] 1/2 " T (Z - 20) 20
< E T (Z E121) ww (EEZ) zn)l
| + 1|=0 E(2]11).
Consequently, we have l E Ge + I W W 14) < Wp(U'm u1) S Pa + 8 p. Decomposing l, = o Q as in Lemma 12 and writ- ing (1k = Q41,, the same approach applied in the proof of Theorem lgives
E E| 20) S Geuv (a, 20). Moreover, we have
E, - Epl(.] 5 Ru (cp (Q (o, 2x);
21

---

S Ry (cp + glookok +);0)
When 1, we bound the regularizer radius by
cp + (Ookke) S po + + (1+ Po) S Vipo + Vhe +
using Lemma Similarly, when p = 2, we bound the radius by
op +p S pa + + (1+ (o) 2 Vkpo + vk+
We then conclude as in Theorem 4
C.5 Proof of Proposition 9
Since iterative filtering works by identifying a subset of samples with bounded covariance and Wp perturbations can arbitrarily increase second moments when p < 2, it is not immediately clear how to apply this method. Fortunately, W2 perturbations have a bounded affect on second moments, and, by trimming out a small fraction of samples, we can ensure that a W, step is bounded under W2-
Lemma 13. For any ur, E P(R4)) and O < S 1, there exists o' E P((R)) with || w||TV ST such that W1 Vu,,,' v') S W1 (1,, v) and Woe (1u, v/) & Wi(j,
Proof. Let (X, Y) be coupling of and with X||| YlI = Wi WI( v). Writing A = XX - YII. the event that W1 (n. / has probability least - 7 by Markov's inequality. We shall take v' be the law of Y = E + 1x). By design, ||/ - w/|TV S % and
Wi / < B|JxX -| - < Wi (1,
Finally, we bound W v/) = | I Wi(u,))/7.
For consistency between Settings and B', we let m = n if we are the former. Thus, both cases, we have (p Pmm)) S Pa and || nr, IV S E = 1/12. is well known that the empirical measure Pm will inherit the bounded covariance of μ for m sufficiently large, so long as a small fraction of samples are trimmed out. In particular, by Lemma A.18 of [15] and our sample complexity requirement, there exists a uniform discrete measure ag over a subset of h = (1 - Eo/ 120)m points, and Ea, 2 Ta with probability at least 0.99.
such that B.,, / B [2]l X
Moreover, applying Lemma 13 with = Eu/ 120, there exists 3 E P(R with |1, - M'm ITv S E and W2 Pm)) I 240pa/Eg- Combining, we have that W htt///2000/11000/0/ (a pm)) =
W Wfle0/00 (ark < 240po/En- and so there exists E -((Te)) such that W.o(ax, K) S 240po/80 and || - -uullTv - /60. The W bound implies that Σ, J O(1 0(1+ TT.
Thus, by the proof of Theorem 4.1 in [26] and our sample complexity requirement, the iterative filtering algorithm (Algorithm I therein, based on that of (15) applied with an outlier fraction of 61 61/60eg 1/10 returns reweighting of jrn whose mean 20 Rdd is within ( pa/ VEa) 0(1 + po) of that of k. Thus, we obtain
11:0 E [2]|
<
E2 |Z] - | + +0 - Po)
< EE,, [2] - |2 0 (11+p po)
< 0(1 + Po).
as desired.
C.6
Proof of Proposition 10
We have
I, 20) Z 20) = old.
sup (EGeor(0,20): (5.
Ex
sup #. (E)(
Ey
Ex Z' Z|P1 & P
n' < -
22

---

EvEra my Ey,
MnBy (Z; 20)(Z; z0) old,
EiE(n) m, Bu, 1| - Z+11"] S p",
sup mER 2 M, (P(()) E2(
Σ iE/ml
m, Eyg [e]
0 I mi S "([-eej vi [n],
EvE(n) mi =
EieM J2(21 20) - 20) T dv((z)) 3 Iol
Eie(n) 12 11 (e S Pp,
1 Eu:19: : 0 S mi "(1-e)) Vi [n].
sup
mER 1/ 19
sE|nl
EiElm my m==1 =1
Sz dz/(2))) mi, vi [n]
where the first equality follows from the definitions of G Goog (a, 20) and (2nnnlll) The second and the third equalities follow from the same variable substitution as in the proof of Proposition 6 The last optimization problem admits the dual form
Eietal n(1-E)
2n A1 + a Tr[An] + App +a
inf AE ".EER",aER
8, 2 max (0, rs aa, E [m],
r; 2 ( - AAE + 2 A1 d2llE - Z.P, E 2, [r]
Strong duality holds thanks to Assumption 3 and 47 Proposition 3.4]. The proof of the second claim concludes by removing the decision variables and and using the definition of iin.
C.7 Proof of Theorem
By Proposition 10 and exploiting the definition of ua. we have
sup E [
vEScov (a,20): W, P)S
inf
-20 A1 + Tr(Aii] + A28 +a+ n11 8) iE(n
8i
s.t.
A U A2 E R,, S R7
9; 2 sup {(E) - T AIE + 24 EEZ
A120 >2lls - 1 -a Vi [n]
inf
-20 A + o Tr(A1] + Aap
Σ
n(1 - sEin]
s.t.
A E 0 A2 R4, E R
(10)
9; sup (5(t) 5 An 2 A A2IlE 2,1 a Vie [n) [J]
EE2
where the second equality follows form Assumption
For any fixed i E [m] and j E [J], we have
sup 6E2
(E(E) - < Ar + 25 A 2g
d211E
1 a
{{ inf
2, ct + b2h(CW//2, x2(33)
s.t. Gi, G. C,
+ +
c
+ C 2A1
where the equality is result of strong duality due to 57 Theorem 2] and Lemma II The claim
follows by introducing the epigraph variable Tıj for the term ) and substituting all resulting dual minimization problems into (TO) and eliminating the corresponding minimization operators. Note that by the Schur complement argument, we have
(T) S
A
Si
G
[c)))
T
4Tgy
0,
which implies that the resulting reformulation is indeed convex.
23

---

D Comparison to WDRO with Expanded Radius around Minimum Distance Estimate (Remark I
First, we prove the claimed excess risk bound for WDRO with an expanded radius around the minimum distance estimate P = ja 9, == argminves (v, ūi. We write c 2 -) as in Theorem I
Lemma 14. Under Setting A, ler l argmin SUPWE Ey for the expanded radius p' cp + (Tp(G, We then have (2) [e, & (cp + 2 2T, 22);
Proof. Since (1, (i) 3 and E G, we have (G ( S p. Thus, Lemma gives that W2: (ū. p1) S 2p. By Lemma we then have Wp((, I cp + 2Tp(G, (G,,,2 25), and so Lemma gives the desired result.
In practice, are unaware of efficient finite-sample algorithms to compute j.. For the class Ganv instead propose the spectral reweighing estimate já = ju e) == argminyeP,(2)..v -hmo [E where || llop is the matrix operator norm (see 26 for varied applications of spectral reweighing). In practice, when jí Kn is an n--ample empirical measure, one can efficiently obtain feasible measure whose objective value is optimal up to constant factors for the problem with & 3e, using the iterative filtering algorithm [55. We work with the exact minimizer já for convenience, but our results are robust such approximate solutions.
Lemma 15. Under Setting A with 9 Guov. p and O S 0.2, we have Wi( S Vdp + de, and this bound is tight; that is, there exists an instance (H. E Geor P(R.) with (i ji) S P such that W1 (u) Z Vdp+ + Vdl.. Consequently, the WDRO estimate ė argmingez (MPEP(())W E, [6] satisfies E,l(] E [.] s ( + vdE);
Proof. Upper bound: For the upper bound on W1 estimation error, fix any j E P(R)) with (i p) S p. Take any p' P(Rd) such that W1 p) S p and I| TV S By Lemma 13 there exists a E P(R") with (i p)) S p. W2(a, n)) S 2/e, and |a a S 2s. Fixing an optimal coupling π E II(a, ()) for the W2(a, (1) problem and letting (Z, W) ~ ग, we bound
E op
sup RE3
B (Z B[Z))]
< sup B (Z [ 1 < | 11 + W2(0, #E8 1
Thus, E Geov (1 + 2/E). Write 3 == (aaR)Raa) a A jú, and note that this midpoint measure is feasible for the problem defining j.. Hence, we have
1 |Epllop S 11Egllop < sup Es ( (Z- (ZlB)(Z)) $ 1 2= 1Eallop 0gga-1
1 (1 PV
S 1 2
and so i E (eov(( - 21)-1 + p )- Moreover, we have / S 4s. Thus, using Lemma aadd the fact that is bounded away from we bound
WI a) s Wi (1h, (anatrert u AA) + Wi
Na) (Taa))xat Na) S Vdp+ + dde.
By the triangle inequality, we have Wi n1) S Vdp + Vdle. The risk bound follows by Lemma Taking the final error measurement using distance between means instead of W1, we observe that | |2 S p+ VE.
Lower bound: To see that this guarantee cannot be improved, fix clean measure μ = ôg E Geov. and consider the corrupted measure jı (1 3:)6, + 22 (4 f e + -5_ge) + =N _ constructed so that Wi (ft, μu) S p. Intuitively. iterative filtering seeks to drive down the operator norm of covariance matrix and will thus focus on removing mass from the second mixture component.
To formalize this, we decompose the output of filtering as (1 - 2s) (1 3s 7)60 + a + 3, where 0 S r < 2s and ax 3 E M4 (Rd) such that a < 2s 256 ge: + =6_gar) and B < eN (0, T La). We have + (2e (<)R)) + (E 3(R)) 2= by the definition of p. Further note that || E |2] X
24

---

+ E by the bounds above. Now suppose for sake of contradiction that ((R S E/2.. Then
a(RR)) 2 e/2, and so we bound
V En EAlzi
[2]]
E
V 2(1 2τ)
4
0 O
V8e
On the other hand, another feasible outcome for spectral reweighing is n² F - 3e f
eV p² 100g Ia), for which we have || of f if S cp² for sufficiently small constant However, if > cp², then lower bound of ((Vde) suffices. This bound holds even without Wasserstein perturbations; see the Jcov lower risk bound of (((de) in Theorem 2 of 38
IVVE Since > v8, this contradicts optimality
We now suppose that ((RR) 2 2/2. Let ~ NO,, To0 and write F for the CDF of Z (which has scaled XI distribution). We then have f || dz(z) | || I (1/2) Z Vdp.
using concentration of xa about its mean. Thus, W1 (z, p) 2 [ [I
2 2 vdp.
E Smaller Robustness Radius for Outlier-Robust WDRO (Remark 2
In the classical WDRO setting with Po 0, the radius p can often be taken significantly smaller than n n-1/d if C and μ are sufficiently well-behaved. In particular, when satisfies Tr transportation inequality, [8 proves that p Ö(n 1/2) gives meaningful risk bounds. Recall that μ T2(T) if
W2(v. & vTH(vl)m), VU E P2(2),
where H(vilm) = [g log(dv (du))dv denotes relative entropy when v < l (and is +oo otherwise). We note that T2 is implied by the log-Sobole inequality, which holds for example when l has strongly log-concave density. Under T2. [8] shows the following.
Proposition 11 (Example 3 in (8). Fix Z Id E. T, T.B 0, and a-smooth and L-Lipschitz function f RR + R. Consider the parameterized family of loss functions L = ={xx, y) (x, y) = f(0 x y) 0 E }}, where O C 10 E Rd ||0|| < B}. Fix p E P(Z) whose first marginal
μх = p(- x R) satisfies μx= E T2(T) and such that inface En X -Y) 0. Write
sup (f X) AE E2 (5 X, YY
L
80.
inface (' X, X,
For 1, >>> O, define
Tt + dlog(2 + 2Bm))
20(1 + d log(2 + 2Bn))
1
Pn.
n
n
2L+ +BB X + 2² (ar, + Puy Eu[(++ Ball + Var, ((L+ 1)
8,
2rB2r1(1 - dlog(2 + 2Bm)
Th
Y
Then, with probability at least 2/n 2e we have
F. [6) Ep., [to]] s (p...2(Pri to) 5,, nn VO e.
(11)
We note that 111 is stated without the absolute value the right hand side, but that this strengthened result holds due to the discussion after [88. Theorem 1]. This generalization bound immediately gives the following excess risk bound.
25

---

Corollary 5. Assume n 2 800. Fix Pu. Sn The and L as in Proposition 77 with t 7, and take Eg E L minimizzin with p = 2 and radius p = Pn- Then, with probability at least 0.99, we have
B - (6o - Pa pallool(m2a())) opp on + 1/o 40 E O
Proof. By Proposition and 18 Remark IJ, we have
E (gl [ [6) - 2R 2(pn (o) + 25, + 2m A0 E O
with probability at least 2/n 2e- 0.995. Since Eg a-smooth, Lemma 6 gives that E - [6]] < 2prl Le 4ell (.)(())))))))))))))))))))) 2ap + 28, + 2m,. 40 E θ
with probability at least 0.995. By Markov's inequality, we can substitute ün, with μ at the cost of constant factor blow-up in excess risk and decrease in the confidence probability to, say, 0.99. m
In the example above, excess risk is controlled by the 2- Wassersttei regularizer with radius Pr.
On 0n2-)/ up to O(n-l) correction terms, which is significantly smaller that the typical radius size of O 1/d). We shall now lift this improvement to the outlier-robust setting. Similar to Proposition we perform outlier-robust DRO with a modified choice of A. This time, writing G2(0) U zo Ga, 20), we have the following.
Proposition 12 (Outlier-robust WDRO under T2). Assume > 800 and E Geov- Fix Pro 8n, Th- and L in Proposition 77 with t 8, and take Lg minimizing (OR-WDRO) with center Pn. radius Po + 15p + 200 d, and A = G2(15vd + Pn)). Then, with probability at least 0.99, we have
Epleg [g) - Eplcol S [ (po Pa + vd) + app + Pr. + v + 8n + 4O E E.
Proof. Noting that Goov G2(vd), we have by Markov's inequality that ün G2(15vd) with probability at least 0.995. In other words, there exists 2p Z such that W2(Ann 82g) & 15vd.
Thus, for any v P(Z) with Wo ((n.
v) Pr. we have W2(1, d2o) S 15vd Pa. and so
E G2(15vd + pn). By Lemmas and 5 this implies that
Wa(Amlle) < (5 v) + T2(1)
s Po + Pn +815vd Pn)(1 =))
< p.
Next, by Proposition 11 0 E θ that
with probability at least 1 1/400 + 2 > 0..985, we have for each
E, Eulcol S Epa [eal + Ram.2(Paiig) - -E, [eol + 56, + nm
Epp. lCol +
sup vEP(Z)
Ey(Cg] - [6l - (eo + 8, + n
Wa (2
= =E legl +
sup (E9a(15v(tpp) W)
Eyleol - Epp. (Pa)
- -E, + 5n + Tn
< E.p. [Cg)
sup (1 (S 1M)SP
(ell E.p (ca)
- EEy(Co) + 8n + Tn-
Let 2( 1-s 1-26
Using optimality of & and Lemma further bound
26

---

Egleg] Ep160]
sup (15
Eylcol Ep. lcal
+ Ep [col -Epleol + 8n + t/2
sup (155(15)t (1.
Bylcol Ep, [6]]
+ Rann2(Prie)) =28n + 27
sup (E5g(15 Wi (Pn.
Ey[Co] Ep, [6]]
+ Ran.2(Phi 28n 2mm
sup (155(15))
[y[[o]] EE [col + Rpni(priio) 28n + 2mm
R 2 (cp + (p 22) + 72 (A, 25); (s), + Rin, 2 (pri Le) 28, + 2mm
3 [1 (1 (pu Pr. + vd) + apo + P + vd)² + 5, 7/--
As in Corollary 5 we can substitute ia with μe at the cost of a constant factor increase in excess risk
along with small decrease in the confidence probability (in this case, sufficiently small such that the total failure probability is at most 0.01).
The main goal of Proposition 12 was to demonstrate that one can expect improved excess risk bounds for outlier-robust WDRO in situations where such improvements hold for standard WDRO. We conjecture that similar guarantees hold for additional settings and under milder assumptions like the Ti inequality. but leave such refinements for future work. In particular, for the class Geov, it would be desirable to prove such bounds when p 1, so that the TV contribution to the risk vanishes as -
F Parameter Tuning (Remark
To clarify the parameter selection process, we consider Setting B with the class g Geov (a), p = 1, and 1/3. We aim to efficiently achieve excess risk
E I,, <
|1e|1lupp (pu + ovde ovdn-
(12)
matching Proposition
when
-= argmingee
sup
[e]
(13)
mE92(d, 2o): Wi (SS.P)S
for some parameter guesses o, é, and á. and a robust mean estimate zo. First, we observe that the coordinate-wit trimmed mean estimate from Proposition 5]is computed without knowledge of the parameters, so safe to assume that || - |E,[2]]| S Vd + Pa- If the parameter guesses are conservative, i.c., o 2 they too large, i.e., ā Sa. E, and X S Po vddd-11// 1/d this gives the desired excess risk.
and P 2 Pa W, (H. A.,, then we may still employ Proposition 4 If
We now explore what prior knowledge of o, E. and Po is needed to obtain such guesses. First, we show that effective learning is impossible without knowledge of Po. even for standard WDRO (i.c., E = 0, σ = o0). For ease of presentation, we present the following lower bound without sampling. Lemma 16. There exists a family of loss functions C over R. such that, for any C' > 0 and decision rule D P(R) L, there are p. jt E P(R) such that E,, (D()) > C(infeec Ep [ + Wi(p, [
Proof. Let C = {Eo 0 > 0}. where (z(z) = z/0 + 0. By design, we have || 1/0. Let ōg and write D(ū) la for some θ > 0. We then set μ 6, for 10 This gives
[,,i)(a) (p)
10C20
27

---

and
2p inf (p(p) + -inf 850
inf [ + Wi Alle FEC
+ = 2 2p vsocè.
6>0 0
Thus, we have E, ((ū) > infrec E,( + Wi (1r, [ as desired.
Thus, assume in what follows that = Po is known. Moreover, require knowledge of at least one of E and σ. both are unknown, then is information theoretically impossible to meaningfully distinguish inliers from outliers (see Exercise 1.7b of [16] for discussion of this issue in the setting of robust mean estimation). If is known, then we can choose ē as 2 for the smallest i such that the supremum of Eq. (13) is feasible (or, equivalently, such that the associated dual is bounded for some fixed E C). We can overshoot by at most factor of two and thus achieve the desired risk bound. Using binary search, this adds a multiplicative overhead logarithmic in the ratio of the initial guess for a and its true value. The same approach can be employed if a is known but not E.
G Additional Experiments
We now provide several experiments in addition to those in the main body. Code again provided at https://gi http::///ggggaalooocco////ooorrr
-robsttttDD
First, in Fig. 3 we extend the experiment summarized Fig. (top) include runs with é = e and varied Wasserstein radius á E {o/2, p. 2p}. For this simple learning problem and perturbation model, we find that the choice worst case, selection of و can be critical, demonstrated by Lemma 16
plays minor role in the resulting excess risk. We emphasize that, in the
Next, we consider linear classification with the hinge loss, i.e. L = {la y) = ma 1 y(0 } E Rd-1)] This time (to ensure that the re- sulting optimization problem is convex), ap- proach supports Fuclidean Wasserstein perturbations in the feature space, but Wasserstein perturba- tions in the label space (this corresponds to using Z =dd1 R equipped with the (extended) norm [<=,,)) v)ll = || + oc 1 # 0}. We consider clean data (X, Y = s0 X)) ~ where ~
Excess Risk for Varied Sample Size and Method
eXCeSS absotute deviation
WOR
D11-W010 5
DH DI--WRDD w/ 5
OR WDRO 0000
(0 1)) The corrupted data (X, Y) ~ satisfies (X, Y) = (X + pel, Y) with probability 1 and (X (100X, -Y) with probability E, so that (ū S p. In Figure 4 (left), we fix d d= and compare the excess risk E,, EE, ] of standard WDRO and outlier-robust WDRO with G = G2. as described by Proposition 4 and implemented via Theorem 2 The results are averaged over = 20 runs for sample size n E (10. 20, 50, 75, 100). We note that this example cannot drive the excess risk of standard WDRO to infinity, so the separation between standard and oublier-rousst WDRO is less striking than regression, though still present.
#samples
Figure 3: Excess risk of standard WDRO and outlier-robust WDRO for linear regression under W, and TV corruptions, with varied sample size and dimension.
We further present results for multivariate regression. This time, we consider Z = Bddc equipped with the & norm, and use the loss family L {fss (x, v) |M y/1 : AM E [gxdd. We consider clean data (X, Y M. X) μ., where M, Rexd and X have standard normal entries. The corrupted data (XX, Y) j satisfies (X, Y) (X + pel, Y) with probability (X, =
and with probability E. so that Wg(Aalpp)) S p. In Figure (right), we fix d= 10 and & = 3, and compare the excess risk E, por [..[ of standard WDRO and outlier- robust WDRO with g = G2. as described by Proposition and implemented via Theorem 2 The results are averaged over T 10 runs for sample size E {10, 20, 50, 75, 100). We are restricted to low & since the é, norm in the losses is expressed as the maximum of 2* concave functions (specifically, we use that (x y) ( (Mx - y)).
Finally, turn to classification task with image data. We train robust linear classifier to distinguish
28

---

12
Excess Classification Risk with WDRO
exCeSS rikk (r. meso aboolute deviation)
20*
Excess Linear Regression Risk with WDRO
slandard WDRO
standard WORD WDRC
excess risk (hinge loss]
DR WDRD
-07
10
0.3
10"
0.4
02
10
20
30
40
50 #samples
00
70
100
20
40
50
80
10
100
#samples
Figure 4: Excess risk of standard WDRO and outlier-robust WDRO for classification and multivariate linear regression under W, and TV corruptions, with varied sample size.
between the MNIST 14 digits "3" and "8" when 10% of training labels are flipped uniformly at ran- dom, using outlier-robust WDRO with g G2 and the hinge loss, as above, applied with E
MNIST Classification Accuracy
classification accuracy 1%% correc)
regular WBB0
DR-WORR
and
0.01. To ensure tractability, first pass the images through principal component analysis to re- duce the input to 50 dimensions, and again Theorem 2 for implementation. In Fig. 5 we plot the classification accuracy of our robust classifier com-
0.85 0.8
pared to one learned via standard WDRO for training set size E {10, 20, 50, 100, 150}. averaged over = 10 runs. In this case, we do not witness a noticeable improvement over standard WDRO. We suspect that the relevant 92 class is too large to be of significant use in this high-dimensional setting.
0.75
sample size
Figure 5: Classification accuracy of standard WDRO and outlier-robust WDRO predictors for MNIST digit classification under random label flips, with varied number of training samples.
For all experiments, confidence bands are plotted representing the top and bottom 10% quantiles among 100 bootstrapped means from the T runs. The additional experiments were performed on an MI Macbook Air with 16GB RAM in roughly 30 minutes each.
29


Reviews:
[{"review_id": "5caiuSfjNW", "reviewer": "Reviewer_vYVj", "summary": "This paper introduces a novel approach to make Wasserstein distributionally robust optimization problems robust to adversarial outliers including geometric perturbations and non-geometric contamination of the data. This goal is achieved by considering relevant Wasserstein ball which includes both type of adversarial attacks. Later, the authors provides strong duality results which allows them to improve the computation complexity of the proposed outlier-robust WDRO problem.", "questions": "- What is the definition for $\\theta$ performing uniformly well over Wasserstein ball (stated in Line 29)? \n- I could not see the definition of $\\Sigma_\\mu$ in the paper. ", "limitations": "The Assumption 2 can be challenging to maintain/check in practice. Moreover, this application might also be hard to implement on large datasets such as classification problems on MNIST or FMNIST. That being said, I don't see these possible limitations as a major problem considering the theoretical novelty of this work. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a well written paper with novel contributions. The robustness of WDRO to the outliers is a very natural problem and the authors proposed a Wasserstein distance based constraints to provide robustness. This is particularly hard if we do not make any presumptions on the distribution of data; therefore, I find the contributions of this paper to be significant to the literature. There might be some concerns that I have mentioned in the weaknesses part, but, overall I am impressed by the work done here. \n", "weaknesses": "As I have mentioned at the strengths part, I believe this paper has a novel contribution to the robust optimization literature. Some few weaknesses that I observed was that authors assumed the readers have prior knowledge on relation between adverserial attacks and Wasserstein and TV perturbations. These are not so obvious for me and might be useful to include some discussion/motivation about how these attacks can be associated with claimed perturbations in metric space. \n\nI believe it would strengthen the paper if authors can obtain some results on larger datasets. Considering the time constraint of the conference, I believe it would be sufficient to add one large dataset to experiments. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback. We address their concerns below:\n\n**Relation between adversarial attacks and Wasserstein/TV perturbations:** Thank you for bringing this up. We will add the new Figure 1, along with accompanying discussion, to the introduction to clarify the nature of our allowed perturbations. Intuitively, the perturbation set $\\mathcal{B}_{\\varepsilon,\\rho}(\\mu) := \\\\{\\tilde{\\mu} : \\mathsf{W}_p^\\varepsilon(\\tilde{\\mu},\\mu) \\leq \\rho\\\\}$ describes the following adversary. First, the $\\mathsf{W}_p$ perturbation of radius $\\rho$ enables the adversary to geometrically move samples of $\\mu$ around for a total $L^p$ displacement cost of $\\rho$, to arrive at a new distribution $\\mu'$. The $\\varepsilon$-TV perturbation further enables mixing $\\mu'$ with an arbitrary outlier mass $\\alpha$ to generate the distribution $\\tilde\\mu=(1-\\varepsilon)\\mu'+\\varepsilon\\alpha$. More formally, the adversary replaces each sample $X \\sim \\mu$ with $X + \\Delta(X)$, for some (potentially stochastic) displacement map $\\Delta : \\mathbb{R}^d \\to \\mathbb{R}^d$ such that $\\mathbb{E}[\\|\\Delta(X)\\|^p | \\mathcal{E}] \\leq \\rho^p$, where $\\mathcal{E}$ is some event with probability $1-\\varepsilon$.\n\n**Results on larger datasets:** Our approach can indeed scale to more complex data sets. As a proof of concept, we compare standard and outlier-robust WDRO (implemented via Theorem 2) for binary classification between two MNIST digit categories with 10\\% of training labels flipped, see the new Figure 3.\nTraining linear classifiers with hinge loss on 10, 20, 50, and 100 training digits (each naively reduced to 50 dimensions), we found that our approach consistently outperformed standard WDRO in classification accuracy. For the final version, we will extend this test to larger dimensions and training set sizes, and include the results in our Section 5.\n\n**Uniform performance over Wasserstein ball:** On Line 29, the sentence \"$\\hat{\\theta} \\in \\Theta$ performs uniformly well over the Wasserstein ball\" was intended to be a qualitative description of Eq. 1. Indeed, the minimizer $\\hat{\\theta}$ is selected to incur low risk $\\mathbb{E}_{Z \\sim \\nu}[\\ell(\\theta,Z)]$ w.r.t. any distribution $\\nu$ lying within Wasserstein distance $\\rho$ of the observed data distribution $\\tilde{\\mu}$. We will adjust the phrasing to emphasize that we are optimizing for such a uniform risk bound, rather than suggesting that the performance of $\\hat{\\theta}$ is similar for all such $\\nu$ (assuming this was the cause for confusion).\n\n**Definition of $\\Sigma_\\mu$:** $\\Sigma_\\mu \\in \\R^{d \\times d}$ denotes the covariance matrix of a probability measure $\\mu \\in \\mathcal{P}(\\R^d)$. We will include this definition in the final version.\n\n**Strength of Assumption 2:** Generally, any continuous function can be approximated arbitrarily well by a maximum of finitely many concave functions. However, the number of needed functions can be arbitrarily large, which raises efficiency concerns in practice.\nFor instance, the $\\ell\\_1$-norm $\\|z\\|\\_1 = \\max_{\\sigma \\in \\{\\pm 1\\}^d} \\sum\\_{i=1}^d \\sigma\\_i z\\_i$ requires $2^d$ concave functions, whereas the $\\ell\\_\\infty$-norm $\\|z\\|\\_\\infty = \\max_{i \\in [d], \\sigma \\in \\{\\pm 1\\}} \\sigma z\\_i$ requires only $2d$. We will add a discussion of this limitation to the final version. The question of how to efficiently perform outlier-robust WDRO for loss functions requiring $\\exp(d)$ concave pieces is an interesting avenue for future research. In such cases, it may be appropriate to apply gradient methods directly to our dual form (Eq. 6)."}, {"review_id": "18FKhukv8s", "reviewer": "Reviewer_zQim", "summary": "This paper introduces an outlier-robust Wasserstein Distributionally Robust Optimization (DRO) framework that aims to capture both geometric uncertainties and non-geometric perturbations, such as adversarial outliers. By utilizing the outlier-robust Wasserstein distance, the proposed framework allows for the arbitrary corruption of a fraction of the data. The authors design an uncertainty set using a robust Wasserstein ball and derive minimax optimal excess risk bounds. They also establish a strong duality for efficient computation. The resulting problem involves tuning three parameters:\n\n- the bounded covariance parameter $\\sigma$,\n  \n- the radius of the ambiguity set $\\rho$,\n  \n- and the contamination parameter $\\varepsilon$.\n  \n\nMoreover, the authors address dimension dependencies in risk bounds for low-dimensional features by introducing the projection robust optimal transport. The paper concludes with experimental validation of the theory on regression and classification tasks.", "questions": "- Would it be possible to provide further elaboration on the process of determining suitable parameter values for $\\rho$, $\\varepsilon$, and $\\sigma$?\n- In the proof of Proposition 7 (Appendix B.8), is the constraint $\\sum_{i\\in [n]}m_i = 1$ included to ensure that $\\mu^\\prime$ is a valid probability distribution? It appears that in the problem mentioned above l566, the constraint should be $0 \\leq r_i \\leq s_i$ rather than the constraint $0 \\leq s_i \\leq r_i$.\n- In lines 48-49, it appears that the term $W_p^\\varepsilon$ is defined in reference to outlier-robust optimal transport, rather than the partial optimal transport as described in [D], which focuses on transporting partial mass from the source distribution to the target distribution.", "limitations": "Unless I missed it, I believe the authors do not expand on the limitations of their approach. It would help to add a short section discussing that. This work does not have a negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper replaces the Wasserstein distance with the outlier-robust Wasserstein distance to tackle the case that the observed distribution is contaminated with outliers.\n- The authors establish the excess risk bounds of decisions for the cases $p=1,2$.\n- The authors derive tractable reformulation by replacing $\\mathcal{G}_{\\text{cov}}$ and leveraging dual of the problem.\n- The low-dimensional features are considered to address the problem of dimension dependency.", "weaknesses": "- In Remark 3 and Appendix E, the paper briefly touches on the selection of the parameter $\\varepsilon$. However, the overall discussion on parameter selection is limited. The model introduced in the paper involves several parameters, such as $\\rho$, $\\varepsilon$, and $\\sigma$, which may not be fully independent. Therefore, a more comprehensive discussion about the tuning of these parameters is warranted.\n  \n- In the experiments, the paper exclusively uses the standard Wasserstein DRO (WDRO) as the baseline for comparison. However, considering that both models aim to address the outlier challenge, it would be valuable to include DFO [A], which is another model specifically designed for handling outliers, as a reasonable baseline for comparison.\n  \n- The presence of a few missing references should be addressed in order to enhance the completeness and accuracy of the paper. In Section 4, it would be beneficial to include references [B, C, D], which introduce the concepts of Wasserstein projection pursuit and projection robust Wasserstein, respectively.\n\n[A] Jiang, Nan, and Weijun Xie. \"DFO: A Framework for Data-driven Decision-making with Endogenous Outliers.\" (2022).\n\n[B] Huang, Minhui, Shiqian Ma, and Lifeng Lai. \"A riemannian block coordinate descent method for computing the projection robust wasserstein distance.\" *International Conference on Machine Learning*. PMLR, 2021.\n\n[C] Paty, François-Pierre, and Marco Cuturi. \"Subspace robust Wasserstein distances.\" *International conference on machine learning*. PMLR, 2019.\n\n[D] Niles-Weed, Jonathan, and Philippe Rigollet. \"Estimation of wasserstein distances in the spiked transport model.\" *Bernoulli* 28.4 (2022): 2663-2688.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback. We address their concerns below:\n\n**Parameter selection:**\nThank you for this important question. Please see **Common Response 1**. We further provide a proof of our claim therein that knowledge of $\\rho$ is necessary for meaningful risk bounds under adversarial Wasserstein perturbations.\n\nLower bound (Necessity of knowing $\\rho$): We construct a family of one-dimensional loss functions $\\mathcal{L}$ and an observed distribution $\\tilde{\\mu} \\in \\mathcal{P}(\\R)$ against which any decision $\\hat{\\ell} \\in \\mathcal{L}$ chosen as a function only of $\\tilde{\\mu}$ must suffer risk\n$$\n \\E_\\mu[\\hat{\\ell}] \\gg \\inf\\_{\\ell \\in \\mathcal{L}} \\E\\_\\mu[\\ell] + \\mathsf{W}\\_1(\\tilde{\\mu},\\mu) \\\\|\\ell\\\\|\\_{\\mathrm{Lip}}\n$$\nfor some clean distribution $\\mu \\in \\mathcal{P}(\\R)$.\n\nSpecifically, we consider the family $\\mathcal{L} = \\{ \\ell_\\theta: \\theta > 0 \\}$, where \n$$\\ell_\\theta(z) := \\frac{z}{\\theta} + \\theta.$$\nAssume that the learner observes $\\tilde{\\mu} = \\delta_0$ and selects decision $\\hat{\\ell} = \\ell_{\\hat{\\theta}}$ for $\\hat{\\theta} > 0$. If the true distribution was $\\mu = \\delta_\\rho$, then the optimal decision would have been $\\theta_\\star = \\sqrt{\\rho}$. In this case, the learner suffers excess risk\n$$\n    \\ell_{\\hat{\\theta}}(\\rho) - \\ell_{\\theta_\\star}(\\rho) = \\frac{\\rho}{\\hat{\\theta}} + \\hat{\\theta} - 2\\sqrt{\\rho} = \\left(\\sqrt{\\rho/\\hat{\\theta}} - \\sqrt{\\hat{\\theta}}\\right)^2.\n$$\nAs $\\rho \\to \\infty$, this far exceeds the desired lower bound of $ \\mathsf{W}\\_1(\\tilde{\\mu},\\mu) \\cdot\\\\|\\ell\\_{\\theta\\_\\star(\\rho)}\\\\|\\_{\\mathrm{Lip}} = \\rho \\cdot \\rho^{-1/2} = \\sqrt{\\rho}$. This construction fails when $\\rho$ is known, since the learner may simply select $\\hat{\\theta} = \\sqrt{\\rho}$.\n\n**Comparison to [A]:** Thank you for this reference. We will include [A] in our related work and add it as a baseline for comparison. We would like to emphasize, however, that the DFO approach requires solving a non-convex optimization problem, significantly impacting its scalability. Further, this method is not accompanied by any proof of minimax optimality.\n\n**Missing references:** We will update our related work and discussion to include these citations. We note that the notion of robustness considered in these papers is distinct from ours  (although we do employ such sliced distances in our analysis for Section 4).\n\n**Unit mass constraint:** We thank the reviewer for raising this important point. Our tractable dual reformulation is indeed missing a Lagrange multiplier corresponding to the constraint that probability distributions have unit mass. The corrected dual is\n$$\n\\sup\\_{\\nu \\in \\cG\\_2(\\sigma,z\\_0):\\\\, \\mathsf{W}\\_p^\\ep(\\tilde{\\mu}\\_n\\\\|\\nu) \\leq \\rho} \\E\\_\\nu[\\ell] = \\inf\\_{\\substack{\\lambda\\_1, \\lambda\\_2 \\in \\R\\_+ \\\\\\\\ \\alpha \\in \\R}} \\lambda\\_1 \\sigma^2 + \\lambda_2 \\rho^p + \\alpha + \\frac{1}{1-\\ep} \\E\\_{\\tilde{\\mu}\\_n} \\big[\\\\,\\overline{\\ell}(\\cdot\\,;\\lambda\\_1,\\lambda\\_2, \\alpha)  \\big],\n$$\nwhere $\\overline{\\ell}(z;\\lambda\\_1,\\lambda\\_2, \\alpha) := \\sup\\_{\\xi \\in \\mathcal{Z}} \\\\,\\big[\\\\,\\ell(\\xi) - \\lambda\\_1 \\| \\xi - z\\_0 \\|^2 - \\lambda\\_2 \\| \\xi - z \\|^p - \\alpha \\big]\\_+$.\nRecalling the conditional variance at risk defined by $\\mathrm{CVaR}\\_{1-\\ep, \\mu} [\\ell(Z)] = \\inf\\_{\\alpha \\in \\R} \\alpha + \\frac{1}{1 - \\ep} \\E\\_{Z \\sim \\mu} \\big[[\\ell(Z) - \\alpha]\\_+\\big]$, this can be restated as\n$$\n\\inf\\_{\\lambda\\_1, \\lambda\\_2 \\in \\R\\_+ } \\lambda\\_1 \\sigma^2 + \\lambda\\_2 \\rho^p +  \n\\mathrm{CVaR}\\_{1-\\ep, \\tilde{\\mu}\\_n} \\left[ \\sup\\_{\\xi \\in \\mathcal{Z}} \\\\, \\ell(\\xi) - \\lambda\\_1 \n\\| \\xi - z\\_0 \\|^2 - \\lambda\\_2 \\| \\xi - Z \\|^p \\right].\n$$\nWhen $\\ep \\to 0$ and $\\sigma \\to \\infty$, CVaR reduces to the standard expected value and the minimizing value for $\\lambda_1$ is 0; we thus recover the classic WDRO dual as a special case.\n\nIn the new Figure 2, we display experiments updated with this correction. Results are essentially unchanged, with the exception of reduced performance when $\\ep$ is too small. Indeed, the corrected dual form invalidates Remark 3 (it relies on an insensitivity of the incorrect dual to $\\ep$ that is no longer the case). We will replace this with a remark on parameter selection as described in **Common Response 1**. We are currently investigating theoretical justification for the strong performance without the constraint and will include our findings in the final version.\n\n\\textbf{Outlier-robust vs. partial OT:} We note that our definition of outlier-robust OT $\\RWp$ corresponds to a partial OT distance up to a constant prefactor:\n$$\n\\RWp(\\mu,\\nu)^p = (1-\\ep)^{-1}\\inf\\_{\\substack{\\pi \\in \\Pi(\\mu,\\nu)\\\\\\\\\\pi\\_1 \\leq \\mu, \\pi_2 \\leq \\nu\\\\\\\\\\pi(\\mathcal{Z} \\times \\mathcal{Z}) = 1-\\ep}} \\int \\|x - y\\|^p d \\pi(x,y).\n$$\n\n**Limitations:** Thank you for this suggestion. We will add a discussion of limitations before the conclusion. In particular, we will reiterate the required knowledge of problem parameters and discuss the practical implications of Assumption 2 (see response to Reviewer vYVj)."}, {"review_id": "XgQt0mYYch", "reviewer": "Reviewer_ZiUC", "summary": "It is well known that Wasserstein distances do not commute well with total variation distance - a slight perturbation in TV can change the Wasserstein distance by a lot. This means that models that are robust to corruptions in the data distribution in Wasserstein distance can still be vulnerable to outliers or corruptions in TV sense. This paper addresses this problem by considering robustness with respect to both TV and Wasserstein. The paper studies worst-case excess risk w.r.t. corruptions in a new distance termed the 'outlier robust Wasserstein distance'. The authors derive upper and lower bounds on the worst-case excess risk for families of distributions that are either sub-Gaussian or have bounded covariance. The upper bounds depend on a recently introduced term called the \"resilience\" of a probability measure. Intuitively, resilience of a measure quantifies the deviation in expectation of a function (in this case the loss function) when taken w.r.t. a measure in a probability ball around the original measure. The authors also propose a tractable reformulation of the min-max problem via strong duality. Finally, the authors tighten their results for the case when the true distribution lies on a low dimensional linear subspace, by extending their results to corruptions in outlier robust max-sliced Wasserstein distance. The authors also verify their excess risk bounds on a toy dataset for linear regression problem with mean absolute deviation loss. \n\n", "questions": "- Proposition 3: Is this lower bound valid for p = 2, or only for p = 1? The loss function family is only assumed to be Lipsclitz and not $\\alpha$-smooth, whereas for the upper bound, the loss is assumed to be $\\alpha$-smooth for the case of p = 2. \n- Proposition 4 could just be a remark. \n- Something is broken in reference [38]. Are you sure this is the correct reference? I did not find a Proposition 3.4 in it. Also, as I have stated previously, I would very much like a closer comparison of the strong duality result with that of Gao and Kleywegt. Do both the results become identical if one of the lambda's is zero?\n- Do the results of section 4 still go through if the max-sliced wasserstein distance is replaced with the sliced wasserstein distance that takes expectation over all slices instead of max?\n- Lemma 5, which seems crucial to the proof of Theorem 1, is taken from [12], supposedly a forthcoming paper, which I am unable to access anywhere. So, I am unable to check Theorem 1 fully. ", "limitations": "Yes. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- significance: the problem of incorporating outlier robustness into the framework of wasserstein distributionally robust optimization (WDRO) is of significance to both ML and optimization communities, and has already received some recent interest. This paper makes progress on this significant problem. \n- novelty: I think the upper and lower bounds on the min-max excess risk are novel. The strong duality result appears to be a generalization of Gao and Kleywegt's result on strong duality for WDRO, but I think it is is non-trivial. ", "weaknesses": "- **Contextualizing the work within related literature**: Although the paper is overall well written, I wish it did a better job at contextualizing their results properly by comparing it with the two special cases of WDRO without TV corruption and of TV robustness without WDRO. For WDRO without TV corruption for example, a natural point of comparison is [this](https://optimization-online.org/wp-content/uploads/2016/04/5396.pdf) paper by Gao and Kleywegt. One point of comparison could be the existence and the form of the worst-case distribution in the min-max risk. This question is answered for the WDRO without TV corruption in Gao and Kleywegt's paper but this paper does not address it at all, which seems odd to me. For TV corruption without WDRO (aka Huber contamination), there are several works from the robust statistics community.\n- **Usefulness on top of stricter WDRO**: I think Remark 1 deserves much more discussion. From proposition 1 it is clear that the new compound model of outlier robust WDRO can be subsumed under plain vanilla DRO by increasing the budget of the Wasserstein contamination in proportion to the resilience of the true distribution. Then, how much additional utility do we gain by analyzing the min-max excess risk under the compound model in detail? I must admit I don't understand what the authors mean by the expensive pre-processing step for WDRO. Please explain this to me satisfactorily, and I am willing to change my opinion on this particular weakness. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback. We address their concerns below:\n\n**Contextualization w/in related work:**\nThanks for raising this fair point. We will add further discussion that compares our results to those in the literature when either $\\varepsilon = 0$ or $\\rho = 0$. \n\nFor WDRO without TV corruptions (i.e., when $\\varepsilon=0$), we will add worst-case distribution results and show how both our strong dual and the said distribution reduce to those of standard WDRO as $\\varepsilon\\to 0$ and $\\sigma\\to\\infty$. For the dual, after introducing a slight correction to our formulation (see **Unit mass constraint** in response to Reviewer zQim), we indeed recover the classic WDRO dual as a special case in the above limit. For the worst-case distribution, we will derive its existence and structure á la Gao and Kleywegt. Specifically, we can show under the setting of Theorem 2 that $$\n    \\sup\\_{\\substack{\\nu \\in \\cG\\_2(\\sigma,z\\_0):\\\\\\\\ \\RWp(\\tilde{\\mu}\\_n\\\\|\\nu) \\leq \\rho}} \\E\\_\\nu[\\ell]\n    = \\left\\\\{\n    \\begin{array}{cll}\n        \\max & \\sum\\_{(i,j) \\in [n]\\times [J]} P\\_{\\ell\\_j}(\\xi\\_{ij}, q\\_{ij})  \\\\\\\\\n        \\mathrm{s.t.} & q\\_{ij} \\in \\R\\_+, \\xi\\_{ij} \\in \\R^d & \\forall i \\in [n], \\forall j \\in [J] \\\\\\\\\n        & \\xi\\_{ij} \\in q\\_{ij} \\cdot \\mathcal Z & \\forall i \\in [n], \\forall j \\in [J] \\\\\\\\\n        & \\sum\\_{j \\in [J]} q\\_{ij} \\leq \\frac{1}{n(1-\\varepsilon)} & \\forall i \\in [n] \\\\\\\\\n        & \\sum\\_{(i,j) \\in [n]\\times  [J]} q\\_{ij} = 1 \\\\\n        & \\sum\\_{(i,j) \\in [n]\\times  [J]} P\\_{\\| \\cdot\\|^p} (\\xi\\_{ij} - q\\_{ij} \\tilde Z\\_i , q\\_{ij}) \\leq \\rho \\\\\\\\\n        & \\sum\\_{(i,j) \\in [n]\\times  [J]} P\\_{\\| \\cdot\\|^2} (\\xi\\_{ij} - q\\_{ij} z\\_0 , q\\_{ij}) \\leq \\sigma^2\n    \\end{array}\n    \\right.\n    $$\nThe discrete distribution $\\nu^\\star = \\sum\\_{(i,j) \\in \\mathcal Q} q\\_{ij}^\\star \\delta\\_{ \\xi\\_{ij}^\\star / q\\_{ij}^\\star}$ achieves the worst-case expectation on the left-hand side, where $(q\\_{ij}^\\star, \\xi\\_{ij}^\\star)_{(i,j) \\in [n]\\times [J]} $ are optimizers of the maximization problem on the right and $\\mathcal Q := \\\\{(i,j) \\in [n] \\times [J] : q\\_{ij}^\\star > 0 \\\\}$. Note that we recover the classic worst-case distribution when $\\ep = 0$ and $\\sigma \\to \\infty$. Moreover, a non-constructive argument based on counting active constraints guarantees that some worst-case distribution exists with support size $n+2$. \n\nFor the robust statistics setting without Wasserstein perturbations ($\\rho = 0$), we will add comparison to existing work on robust supervised learning (e.g., results of [47] for robust linear regression or those of [45] with a Wasserstein radius of 0). In general, our results improve upon existing risk bounds by scaling with the complexity of the optimal hypothesis for the clean data, rather than requiring a uniform complexity bound for the hypothesis class.\n\n**Usefulness on top of stricter WDRO:** We agree that this warrants further discussion. Please see **Common Response 2**.\n\n**Proposition 3:** The lower bound is valid as stated for any $p \\geq 1$ (since the worst-case Wasserstein perturbation we construct is a translation). However, as the bound is in terms of the Lipschitz constant $L$, rather than the Sobolev norm and smoothness constant, it is best viewed as proving the tightness for the $p=1$ component of Theorem 1.\n\n**Proposition 4:** We will convert this statement into a remark.\n\n**Reference 38:** Thanks for pointing this out, some reference numbers were broken in the supplement. The corrected reference should be [36] (\"On duality theory of conic linear programs,\" A. Shapiro).\n\n**Average vs. max-sliced $\\mathsf{W}\\_p$ in Section 4:** An average-sliced version of $\\mathsf{W}\\_p$ will not suffice for the Section 4 results; our proof of Lemma 8 in Appendix D requires the Wasserstein bound to hold uniformly over all $k$-dimensional projections since we do not know the relevant map $M \\in \\R^{k \\times d}$ in advance.\n\n**Lemma 5:** This result is from [12], which while not yet officially published in *Operations Research*, is available on the INFORMS website (with DOI 10.1287/opre.2022.2383), and on arXiv with identifier 2009.04382."}, {"review_id": "g95gfmxO1z", "reviewer": "Reviewer_L4Xq", "summary": "This paper empowers WDRO with the ability to resist outliers, building upon the outlier-robust Wasserstein distance $W_p^\\epsilon$. The excess risk of the solution to both the outlier-robust WDRO and its empirical version is given. An improved bound of the excess risk is derived for the setting of low-dimensional features. The optimization algorithm for the outlier-robust WDRO is developed with the dual form of the minimax problem. Empirical study validates the effectiveness of the proposed method with a simple regression setting involving both Wasserstein and Total Variance contaminiation.", "questions": "1. Why doesn't the dual form of outlier-robust WDRO in Proposition 7 reduce to that of WDRO when $\\epsilon \\rightarrow 0$, even if neglecting $\\lambda_1$? Specifically, the operator $[\\cdot]_+$ claimed to be vital for outlier-robust WDRO does not disappear when outlier-robust WDRO reduce to WDRO. \n\nSome typos:\n\n- Line 158: $\\nu$ v.s. $\\mu$\n- Supplementary Line 565: In second equality, it might be $s_i\\geq r_i$ and $s_i \\geq 0$.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. DRO is known to be over-pessimistic in the existence of outliers. Empowering Distributionally Robust Optimziation with robustness against noisy labels is important. The outlier-robust Wasserstein distance is a well-developed revision of the original Wasserstein distance to account for certain degree of contamination. Thus, constructing the uncertainty set of DRO with $W_p^\\epsilon$ is both significant and reasonable.\n2. The theoretical analysis of the excess risk of the proposed method is sound and comprehensive. The results quantify how the solution adapts to given geometric and TV contamination. The effectiveness of the empircial algorithm is also guaranteed by the empirical bound of excess risk.", "weaknesses": "1. The effectiveness of outlier-robust WDRO is theoretically guaranteed by the excess risk bound. My main concern is over the **advantage** of outlier-robust WDRO v.s. WDRO. As is stated by the authors, the excess risk of outlier-robust WDRO is upper bounded by the $W_p$ regularizer with a larger Wasserstein radius. The authors also recognize that the same upper bound could be achieved by a radius-expanded WDRO. Two advantages of WDRO given in Remark 1 are not convincing. \n\n- The authors claim that a heavy preprocessing step is required by WDRO to estimate the exact radius. However, in practical settings beyond simulated experiments, the exact parameters of contamination levels $\\rho, \\epsilon$  are also latent. Either an estimate or tuning of the radius is necessary for both WDRO and the outlier-robust version. \n- The authors prove an improved bound of the excess risk for outlier-robust WDRO in the setting of low-dimensional features and claim that the bound of WDRO could not be improved, which is unsupported. A tight bound of the excess risk of WDRO with low-dimensional features might be given to consolidate the author's claim. Otherwise, an inequality between the excess risk of WDRO and its outlier-robust version might be given similarly to Eq.4. Furthermore, the proposed low-dimensional feature setting is somewhat impractical because the exact dimension $k$ is typically unknown in real datasets. \n\nIn the experiment section, I suppose the radius for WDRO is selected to be the true contaminaton radius. The curve of performances of WDRO and outlier-robust version with increasing radius might demonstrate their gap more convincingly.\n\n2. I am concerned if the formulation of outlier-robust WDRO (eq.3) is well defined. Consider a simple case where all the samples of $\\tilde \\mu$ are discretely distributed on $2/\\epsilon$ points, one of which is denoted by $(x_0,y_0)$. By arbitarily modifying $y_0$ to $y'$ we get a new distribution $\\nu(y')$. According to Line 131 we have $W_p^\\epsilon(\\tilde \\mu, \\nu) =0$. Thus, all the $\\nu(y')$ is included in the uncertainty set of the correspondong $W_p^\\epsilon$ DRO. However, the risk of a given predictor on the group of $\\nu(y')$ could be unbounded since $y'$ is unconstrained. As a consequence, there might be no solution to eq.3. Intuitively, though eq.3 incorporates the clean distribution into the uncertainty set, it might also include more dirty distributions since the outlier-robust Wasserstein distance tolerates a small fraction of outliers, but the risk on these outliers could be unbounded. Therefore, I'm concerned if the porposed outlier-robust DRO would be biased towards more dirty distributions instead of recovering the clean one.\n\n3. I am also concerned with the selection of the radius $\\rho$ of outlier-robust WDRO. As is indicated by Theorem 1, larger $\\rho$ leads to higher excess risk while Line 203 states that the excess risk bound only stands for $\\rho \\geq \\rho_0 + W_p(\\mu, \\hat \\mu_n)$, implying that $\\rho$ shall not be too small. Since both $\\rho_0$ and $W_p(\\mu, \\hat \\mu_n)$ are unavailable in practical settings, the selection of the parameter seems tricky. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful feedback. We address their concerns below:\n\n**Comparison to WDRO with expanded radius:**  We agree that this warrants further discussion. Please see **Common Response 2**.\n\n**Tight performance bound for WDRO with expanded radius with low-dimensional features:** As discussed in **Common Response 2**, the bounds $\\mathsf{W}\\_1(\\hat{\\mu},\\mu) \\lesssim \\rho + \\sqrt{d\\ep}$ and $\\mathsf{W}\\_1(\\check{\\mu},\\mu) \\lesssim \\sqrt{d}\\rho + \\sqrt{d\\ep}$, which guarantee that the Wasserstein ball contains the true distribution, are tight in general. Moreover, we can show that the performance of standard WDRO with any arbitrary radius $\\rho'$ is tightly characterized by the Wasserstein regularizer from [11] with that radius, even if the reference loss function depends only on $k$-dimensional features. Combining the above claims, if we perform standard WDRO centered around either $\\hat{\\mu}$ or $\\check{\\mu}$ and choose the radius $\\rho'\\in\\\\{\\rho + \\sqrt{d\\ep},\\sqrt{d}\\rho + \\sqrt{d\\ep}\\\\}$ as above, we cannot recover the excess risk bound of Theorem 3 unless $k = \\Omega(d)$. \n\nFurther, we are currently working to prove a stronger lower bound that will establish a clear separation between our approach and standard WDRO with expanded radius. Namely, we seek to show that any choice of $\\rho'$ around these centers (even if the corresponding Wasserstein ball does not contain $\\mu$) will incur suboptimal excess risk. We will report any findings in that direction in the final version.\n\n**Parameter selection:** We agree that this is an important practical concern. Please see **Common Response 1**.\n\n**Impracticality of low-dimensional features:** Section 4 applies to the setting where the loss functions depend only on $k$-dimensional features. Importantly, this is a property of the loss family $\\mathcal{L}$, not the data. Although one may seek to match this dimension with an unknown latent dimension of the data, in practice $k$ is often fixed due to tractability or interpretability concerns (e.g., with linear regression, we have $k=1$). In that sense, the parameter $k$ can be viewed as known to the learner.\n\n**Experiments with varied radius:** Thank you for this suggestion. We will add experiments to the final version which vary $\\rho$ as well as $\\ep$. In the worst case, selecting $\\rho$ too small can lead to unbounded risk (see **Common Response 1**), though this may not occur in our simple regression environment.\n\n**Well-definedness of outlier-robust WDRO:** In the proposed example, so long as $\\mathcal{A}$ is encoding meaningful moment bounds, $\\nu(y')$ does not belong in the uncertainty set for arbitrary $y'$. For example, if $\\mathcal{A} = \\mathcal{G}\\_\\mathrm{cov}$, observe that the variance level $\\\\|\\Sigma\\_{\\nu(y')}\\\\|\\_{\\mathrm{op}} \\to \\infty$ as $\\\\|y' - y\\_0\\\\| \\to \\infty$. That is, we only have $\\nu(y') \\in \\mathcal{G}_\\mathrm{cov}$ for appropriately small perturbations. Incorporating distributional knowledge of the clean data is essential to obtain meaningful risk bounds (not only in our setting, but throughout robust statistics).\n\n**Radius selection:** Our analysis indeed relies upon $\\rho$ being taken sufficiently large. By the argument described in **Parameter selection** above, knowledge of $\\rho\\_0$ is necessary to obtain meaningful risk bounds. As discussed in Proposition 4, $\\mathsf{W}\\_p(\\mu,\\hat{\\mu}\\_n)$ is bounded by $O(\\sqrt{d}n^{-1/d})$ with high probability if $\\mu \\in \\mathcal{G}\\_\\mathrm{cov}$, so no additional knowledge is necessary.\n\n**Recovering classic WDRO when $\\ep = 0$:** As noted by Reviewer zQim, our stated dual form was actually missing an extra Lagrange multiplier (corresponding to the unit mass constraint for probability distributions). The corrected form is provided under **Unit mass constraint** in our response for that reviewer, and it indeed recovers the classic WDRO dual when $\\ep = 0$ and $\\sigma \\to \\infty$.\n\n**Typos:** Thanks for noticing these; we will fix them in the final version."}]

Author rebuttal:
$\newcommand{\cG}{\mathcal{G}}\newcommand{\ep}{\varepsilon}\newcommand{\RWp}{\mathsf{W}_p^\ep}\newcommand{\E}{\mathbb{E}}\newcommand{\R}{\mathbb{R}}\newcommand{\sg}{\sigma}\newcommand{\mr}{\mathrm}$**Common Response:**

We thank the reviewers for their time and feedback. Below we provide a common response to shared concerns.

**1. Parameter selection:**
Selection of $\rho$, $\sg$, and $\ep$ appearing in Eq. 8 and its tractable dual reformulation is a key practical consideration. First, we observe that knowledge of valid upper bounds on these parameters is sufficient to attain excess risk bounds scaling in terms of said upper bounds. This approach avoids meticulously tuning the parameters but may result in suboptimal risk. Below, we discuss methods for parameter selection that attain optimal minimax risk.

First, we note that knowledge of $\rho$ is necessary to attain meaningful risk bounds against adversarial Wasserstein perturbations, even for standard WDRO (i.e., $\ep = 0$, $\sg \to \infty$). See the beginning of our response to Reviewer zQim for a proof of this claim. In the popular setting where $\rho$ models only sampling error (i.e., $\rho_0 = 0$ in the setting of Section 3.2), without adversarial perturbations, knowledge of one of $\sg$ or $\ep$ is enough to tune $\rho$. If $\sg$ is known, then one may select $\rho = O(\sg n^{-1/d})$, as discussed in Proposition 4 (where $\sg \leq \sqrt{d}$ by the covariance bound). If $\sg$ is unknown but $\ep$ is known, we can show that the bootstrapped estimate $\hat{\rho} = 2\mathsf{W}\_p^{2\ep}(\tilde{\mu}\_{S}, \tilde{\mu}\_{[n] \setminus S})$ gives near optimal guarantees, where $S$ is a uniformly random $n/2$-sized subset of $[n]$.

Next, we address tuning $\sg$ and $\ep$, assuming henceforth that $\rho$ is known or was tuned as described above, based on knowledge of one of them. In general, knowing at least one of $\sg$ or $\ep$ is necessary to obtain non-trivial risk bounds, even in the easier problem without Wasserstein perturbations (i.e. $\rho = 0$). Otherwise, it is information theoretically impossible to meaningfully distinguish inliers from outliers (see Exercise 1.7b of "Algorithmic High-Dimensional Robust Statistics" by Diakonikolas and Kane, 2022, for a discussion of this issue in the setting of robust mean estimation).

The first step of our approach is to obtain an accurate robust mean estimate, which we discuss next. If $\ep$ is known but $\sg$ is unknown, then the mean estimation algorithms we employ are fully specified and we may proceed with outlier-robust WDRO. In the opposite case, when $\sg$ is known but $\ep$ is unknown, we employ a halving trick, dividing a guess $\hat{\ep}$ by two until an appropriate $\hat{\ep}$-trimmed variance of the observed data is $O(\sg)$. 

Having an accurate robust mean estimate, to run the main robust WDRO procedure, we can learn the missing parameter via an analogous halving trick. Namely, we use a binary search to set the missing parameter as small as possible, such that the primal problem (Eq. 5) is feasible (corresponding to the tractable dual (Eq. 6) being bounded). The number of search steps scales logarithmically with the ratio of the initial guess to the true value.

We will add a remark and a Supplement section to expand on the above in the final version.

**2. Comparison to WDRO w/ expanded radius:**
We agree that the discussion in Remark 1 should be significantly expanded, which we will do in the revision to account for the points below. As mentioned in the remark, the main issue with running vanilla WDRO with an expanded radius is that the Wasserstein ball must be centered around the output of a complicated minimum distance estimation (MDE) procedure, namely $\hat{\mu} = \mr{argmin}_{\nu \in \cG} \mathsf{W}_1^\ep(\tilde{\mu} \| \nu)$. While [28] provides a statistical analysis for this estimate, the procedure they propose for finite-sample computation is a heuristic one based on Wasserstein GANs, which lacks formal guarantees. 

An efficient alternative to the MDE-based approach is possible for the class $\cG\_\mr{cov}$ using the popular iterative filtering method [8], but the resulting (sharp) risk bounds are suboptimal. Specifically, we can prove that iterative filtering returns a distribution $\check{\mu}$ with $\mathsf{W}\_1(\check{\mu},\mu) \lesssim \sqrt{d}\rho + \sqrt{d\ep}$ (and that this guarantee is tight). Performing vanilla WDRO around $\check{\mu}$ with radius $\sqrt{d}\rho + \sqrt{d\ep}$ yields excess risk $\\|\ell\\|\_\mr{Lip} (\sqrt{d}\rho + \sqrt{d\ep})$. This bound is suboptimal in dependence on $\rho$ by a $\sqrt{d}$ factor (compare to our Corollary 1), which becomes prohibitive as dimension grows. We are working to prove a stronger lower bound, showing that vanilla WDRO around $\check{\mu}$ with any radius leads to suboptimal excess risk, and will report any findings in the final version. 

Even if we ignore the tractability of finding $\hat{\mu}$, we are unaware of any theory which would allow matching our risk bounds from Section 4 for $k$-dimensional features using standard WDRO. Although the MDE estimate satisfies the stronger (and also tight) approximation guarantee $\mathsf{W}\_1(\hat{\mu},\mu) \lesssim \rho + \sqrt{d\ep}$, running standard WDRO with this radius leads to the same risk bounds from Corollary 3, but with $\sqrt{d\ep}$ instead of $\sqrt{k\ep}$. Again, as $k\ll d$, this results in a significant worsening of the bound. 

Lastly, although somewhat subjective, our approach can be viewed as more holistic and interpretable than WDRO with expanded radius. The outlier-robust Wasserstein distance is tailored to account for the considered adversarial model, the strong duality clearly reveals the effect of the different parameters, and the characterization of worst-case distribution (see **Contextualization w/in related work** in response to Reviewer ZiUC) further elucidates the problem structure.

Meta-review: The collective feedback from the reviews is positive, underscoring the significance of the problem tackled, commendable theoretical insights, and the clarity of the writing. The authors' rebuttal seems to have aptly addressed prevailing methodological concerns, including matters of parameter selection, an error in the dual formula, and comparisons with existing literature. The inclusion of new numerical results during the rebuttal phase is a praiseworthy addition. I recommend acceptance.
Decision: Accept (poster)