Generalization Bounds for (Wasserstein) Robust Optimization
Authors: Yang An
Rui Gao
Venue: NeurIPS 2021 Poster (2021)
Keywords: Distributionally robust optimization
Lipschitz regularization
gradient regularization
generalization bound

Abstract: (Distributionally) robust optimization has gained momentum in machine learning community recently, due to its promising applications in developing generalizable learning paradigms. In this paper, we derive generalization bounds for robust optimization and Wasserstein robust optimization for Lipschitz and piecewise Hölder smooth loss functions under both stochastic and adversarial setting, assuming that the underlying data distribution satisfies transportation-information inequalities. The proofs are built on new generalization bounds for variation regularization (such as Lipschitz or gradient regularization) and its connection with robustness.

Generalization Bounds for (Wasserstein) Robust Optimization
Yang An Department of Mathematics Columbia University Bangan@@athh.ollee columbia. edu
Rui Gao Department of IROM
University of Texas Austin, rui gaw.gcaomccommbs.oomm www.att.eeeocoooo.m... edu
Abstract
(Distributionally) robust optimization has gained momentum in machine learning community recently, due to its promising applications in developing generalizable learning paradigms. In this paper, we derive generalization bounds for robust opti- mization and Wasserstein robust optimization for Lipschitz and piecewise Hölder smooth loss functions under both stochastic and adversarial setting, assuming that the underlying data distribution satisfies transprraaionninoomaaoonn information inequalities. The proofs are built on new generalization bounds for variation regularization (such Lipschitz gradient regularization) and its connection with robustness.
Introduction
Consider the following stochastic optimization problem of seeking a function f 2 - IR from the hypothesis space F as minimize the expected loss:
min JE3
{ Ltree (f) = Ex ... [X
Here the data follows some underlying distribution Pirue on A In practice, Pirue often replaced with its empirical estimate P,, Σi= 83s, where ô is the Dirac measure:
min JE3
( = Ex-P, [f))
The discrepancy between IP Ptree and P, may resulted from
(i) The sampling error of F,, when data are independently drew from Prree:
Non-i.i.d data, e.g., r''s 's's are samples from a Markov chain with stationary distribution Ptree
(iii) The deploying environment is (adversarially) different from the data-collecting environment.
Such discrepancy largely contributes the poor generalization behavior of empirical risk minimiza- tion. To tackle this issue, robust optimization [4, 37, 38] studies
min EE
(Jie)
= max
{ "2 f(x))
: (- (1)) S {e}
(RO)
{x E
Here [1, oo]: the uncertainty set, denoted by Lg)(),, describes the data perturbations to hedge against; and the radius e > 0 specifies the level of robustness. In similar spirit, Wasserstein robust optimization [15, 7, 19] studies
min
( max (Ee~P[f(e)) (IP,P, < <et F
(WO)
Here the distributional uncertainty set, denoted by P (p) consists of all probability distributions that are close to P, in p- Wasserstein distance. When p co, (WO) and (RO) coincide. Both problems have received increasing attentions in machine learning; see [25] for survey.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

When data is generated stochastically, such as i..dd or Markovian (see (i)(ii) above), we would like to choose the radius& o = Pn adaptive to the sample size, so that the robust loss can balance between performance and robustness. More precisely, en should be large enough so that the robust loss dominates the true loss with high probability, but not be too large to produce an inferior solution. When the testing environment is adversarially different from the training environment (see (iii) above), consider the adversarial loss minimization
{ Cg (f:0) =- max [Ez=e[f(x) (p,,.. S se] FE
min
(Adv)
PE(P(())
where the radius e captures the difference between the training and testing environments. When I Pirue not available, surrogate problem (WO) based on P,, often considered. In this case, @ is often fixed and we hope that the robust solution yielding from (WO) generalizes well.
The goal of this paper is to provide a comprehensive analysis of the generalization capability of the above robust learning paradigms. Specifically, in the stochastic setting, under proper choice of the radius Pn. we derive finite-sample guarantees for (RO) and (WO). In the adversarial setting, we derive generalization bounds for (Adv) with a small fixed radius g.
Related Literature
Stochastic setting. The most related work ours is [17], but differ in several important ways. First, [17] studies only (WO) while we also consider (RO). Second, [17] studies i..d. data while we also consider non-i.i.d. by exploiting a different notion of transport inequality. Third, even in the i.i.d. setting, [17] studies only smooth losses and Wasserstein order p = 2. We consider non-smooth losses and p E [1, 2). which includes important cases like |A x - yl". Moreover, for p 1, we tighten the order of the remainder; for p = 2, we obtain a cleaner expression using a different set of assumptions. All these extensions require in-depth analysis on worst-case scenarios.
For (WO) with i.i.d. data, [15] originally proposed to choose the radius On such that Prree is contained in the uncertainty set with high probability, but the resulting performance bound is overly conservative and suffers from the curse of dimensionality. This issue has been mitigated asymptotically for smooth loss functions [6, 8. 33], and aan-asymptotically for linear models [32, 12] and for smooth loss functions [17]. As mentioned above, our results apply to non-i.i.d. data and non-smooth losses.
For (RO) in the stochastic setting, its generalization properties were first studied in the pioneer work [39], which established algorithmic generalization generalization bounds for various learning tasks with i.i.d and Markovian data. Nonetheless, many bounds developed therein suffer from the curse of dimensionality. This framework is then extended to metric learning [3] and ensemble models [41]. Our results circumvent the curse of dimensionality of the bounds developed in [39].
Adversarial setting. For p E [1, oo). generalization properties of (WO) with fixed radius was considered first in [27]. The main difference is that we consider different magnitudes of data perturbation. We mainly focus on adversarial robustness where the radius is often a tiny number, and our results in Section 5 suggest that the generalization gap is small when the radius is small. While their motivation was from domain adaptation, and their bound is mostly useful when the Wasserstein radius is not extremely small, which suggests that the generalization gap becomes smaller as the radius grows to infinity (see their Remark 4). The bounds developed in [34, 30] does not depend on the Wasserstein radius, while our result indicates that when the radius is small, the remainder actually demonstrates its linear scaling and therefore tighter.
For oo, [24, 40, 1] focus on deriving generalization bounds for specific loss function classes such as linear hypotheses and neural networks. Our results apply to generic function classes, and most importantly, the bound suggests the the generalization gap controlled by not only the complexity of the loss function class, but also the complexity of the gradient norm functions of the loss functions. The intuition is that the gradient norm controls the robustness of the model subject to adversarial perturbations. As far as we know, the bound in such form is new in the literature. There are also some earlier works focusing on investigating the fundamental limit of adversarial learning and its difference from empirical risk minimization, such as [31, 35, 10, 11]. They consider somewhat different settings than ours, which usually involves a stylized data generating model that facilitates theoretical findings.
Regularization. Part of our analysis based on the connection between robustness and regular- ization. The connection between (RO)(WO) and norm regularization was established for various

---

machine learning tasks [38, 37, 6, 12], and the connection between (WO) and appschizzgrradien
regularization has been established for smooth loss functions [32, 34, 16. 13, 8. 2] and non- smoth loss functions [18]. Our results improve the sandwich bounds in [18] for p 1, and generalizes
the results therein to piecewise Hölder smooth loss functions for p E (1, co]. Finally, there are also works connecting regularization and distributional robustness under other choices of distance
[26, 21, 14, 23].
Preliminaries
In this section, we prepare several technical tools that are useful in deriving our main results.
Notations For [1, oc]. we denote by its Hölder conjugate number, i.c. + = 1. Let
((2)) be the set of Borel probability distributions on 2 = (R3 II-II), and let P, p (2) - {P E ooj. For given probability measure Q, denote by (2g(2) ), 1.1l.)))) the set of 1 functions on 2 with respect to Q. Unless stated otherwise, we will not assume the samples are i.i.d. Instead, we use Sn {i*) Ji=1 to represent a sample of size n, and denote by Jss, the sampling distribution and use Es,, to indicate the expectation with respect to the uss,, and (f = Es, Ex f())). For a fixed set of points, we denote Pa, as the empirical uniform distribution on these points. For two real numbers, and b, we denote A b = min(a, b), and b (a, b).
((T): Ep [|||/=/|P]
Transport inequalities In the stochastic setting, we will work with distributions that satisfy the following condition. Let p E [1, 5o) and > O. A distribution Q E Px(x)) satisfies a transport inequality, denoted (T), if for all P E (2)) it holds that
W2 (IP, Q) ST/
log(dP/dQQdll
where dP/dQ denotes the Cadon-Nikodyn derivative. The integral the right- side of the inequality above represents the relative entropy between P and Q. The transportation-infee -nnirmamtionnnooomationn inequality (T) covers variety of useful classes of distributions. For example, if 2 is bounded by B, then any distribution 2 satisfies Ti (8BB). Gaussian distributions with covariance Σ satisfies T2(2Amax (Σ)). Interested readers are referred to [22] for recent survey.
Variation Regularization Following [18], we define the local and global slope of continuous function f X -> at E 2, denoted by (x) and (zf) respectively, as
(S(3) - [(x))
(ʃ( - fx)))
(8)(x)) = lim | | æ|1
G()()) = sup SE
1 1=-
When f is differentiable at æ, we have [af(()) = |/ f (x)]l=. When f is L-Lipschitz, we have G())(z) s L for all 2 and [IG(f) loo. | For a function f. denote by Il its
Lipschitz norm whenever it exists, and by [|0 the (IPttree)) of its slope function. We define variation regularization as
min E (f: (f: == ( E f(#') ell@@f Il..
9< 00,
(VR)
E f(**) + ellf
g == cc.
We introduce the following class of functions consisting of slope functions of loss functions.
0. = (1afl: F). Nr =
15l fe fEg).
(1)
Throughout we utilize the following assumptions, which covers most loss functions that amenable to optimize efficiently using first-order methods.
Assumption 1. Every f E F is L-Lipschitz.
Assumption 2. Every J E is piecewise differentiable. There exists a such that for every F and every ā, x in the same piece of f. holds that [[Vf(ā) vf(z)]]- hllē z|1a.
3

---

Robustness and Variation Regularization
In this section, establishes connection between robust optimization (RO) (WO) and variation regularization (VR), which serve as building blocks for results in Section 5.
We make the following assumption, which states that the loss function family has sufficient variation. Assumption 3. = inf fe fe ||@f O.
We also define r) == inf R+, defined as
f j @f To simplify notations, we introduce a function On RR+ -
Ex-r, d(x, -(x)( 9))+}
ex sup feB
which describes the data concentration within a margin non-differentiable points.
Remark 1. i can be ensured to be positive with high probability using Assumptions 1, (see Lemma 5 in the supplementary). en(g) vanishes for differentiable families, and is often (p(1/n) when 2n = (LL/VT) (c.f., [18]).
Our first result in this section bounds the difference between (WO) and (VR) for p 1. Proposition! 1. Let p E oo]. Assume Assumptions 1, 2 and hold. Then it holds that (Cmppff Ø) - - (f: ( e)1 s (og(a41)AP 2en, (pp/n))=x Ø), Yf e F,
where Co equals pf oo, max(1, (Lp/r)) ifp 11, and L(h otherwise.
Proposition shows that (WO) and (VR) are close with gap controlled by two high-order terms: one term g(a+1)Ap depends on the Hölder smoothness parameter at while the other term en depends on the data distribution around the non-differentiable region. The smoother the loss function, the smaller the gap is. Intuitively, the worst-case distribution in (WO) perturbs the data approximately aligned with gradient ascent direction, thus the gradient norm in (VR) provides tighter first-order approximation on the difference between the worst-case and the empirical losses for smoother losses. able to
Compared [18, Theorem 1], here focus on Lipschitz loss functions, thereby obtain a cleaner result, but we have to modify the proof therein by bounding the worst-case loss differently.
Our second result this section establishes a relationship between (WO) and (RO) for E (1, recalling that they coincide for
Proposition Let p E (1,).) Assume Assumptions 1, and 3 hold. Then holds that 5 p (f: 2) C (f)
2L n ( ) VfEf,
where An the dual minimizer of (WO) satisfying
(2"-1)e A. 2 0 h- 2Le. 2Le,
- o' L'
Proposition shows that (WO) and (RO) have a uniformly upper bounded gap. Intuitively, both these two robust paradigms perturbs data points aligned with gradient ascent direction. The difference that (WO) allows to perturb a tiny fraction of probability arbitrarily far away, but (RO) prohibits probability splitting. The proof is based careful analysis the probabilistic nature of the worst- case distribution. The first result of this kind was established in [19] for a single loss function, but the bound therein is not controlled uniformly for a family of losses. Under the conditions in Remark the gap vanishes in the order Óp(e/n).
Thus far, we have shown that when p E (o) C (J: en), (e,,((e)) and (ew) only differ by higher order gap that depends on the smoothness of the loss function class.
Next, we consider the case p In light of the example in [18], it not always possible to have CVe (g) - C being of a higher order than g. Below we identify conditions to achieve this. For F. we define cumulative distribution functions Hy. H as
(a) == Ptree | G(f)() < sa). Hy = Firee [I 0f((X) S a}. 2 0, where the random variable X has distribution Ptrue. They describe how the global and local slope functions distribute around their maximum, i.c., the Lipschitz norm.

---

Assumption 4. Assume there exists B, a. c > 0 such that for all a E [0, a) and all f f &, it holds that H ) 2 ca for (WO), and (a(a 2 ca for (RO).
This assumption ensures sufficient concentration on the maximal slope I[ and large & indicates that (X) or (x) concentrates more on the maximal slope. Ideally, would like to have a large 3, and in particular, H has a density at O when 3 = 1. For example, if H has a density near zero, then Assumption 4 imposes positive lower bound on the density with / = 1. As another
example, if is linear function, then the set of global slopes is singleton and (a) H (a) 1 for all a 2 0, hence Assumption 4 is trivially satisfied with a = B = co. More generally, under the assumption that lim 20) (f())-((8))
||5 Ihpp which is imposed by [17], the global slope (z)) |I for all æ E L, thereby H for all 2 0.
2-
Proposition 3. Let p = 1. Assume Assumptions 1, 2, hold. Let E [0, 2- Then for every f E F, it holds that
(f: S (f: S (f:
and that
F (f:
Lxr 0,00 (f: Cnt C 2 f (f: En.
where
6n = eAn + 4h gatz + 2Le (
En = eÂn + Ahmn gatl + 2Len(en")
where An (resp. Án) equals the (1n-- + 1)-th order statistics of the sample {lffluip G(f)(+)) )i= (resp. {llflliip- 1a ))ū-))
Remark Consider data are generated i.i.d., o en O() and has piecewise Lipschitz gradient (i.e., 0 = 1). As shown in the supplementary, the remainder would be O n (1+ + n (1-26)) = O(n 342). When (X) has a positive mass on the maximal global slope, by setting d = 0, with high probability, we have An = O, and en = Oge² + en(e)), which is (1/n) under the condition in Remark 1.
Proposition 3 shows that for p (RO), (WO) and (VR) are equivalent up higher order error term, which depends on the smoothness of the loss function as indicated by a and en. and the concentration of slopes as indicated by An. The smoother the function and the more concentrated on the maximal global slope, the smaller the gap between (WO). (RO) and (VR) is. This improves the sandwich result of [18] in which e, = (n) Our finer analysis is based on construction of feasible solutions for (WO) and (RO) obtained from perturbation of empirical data points as well as careful control on the distances of perturbation.
Generalization Bounds for Variation Regularization
In this section, we derive generalization bounds for variation regularization in the stochastic setting, which are building blocks to develop the generalization bounds for (WO) and (RO).
We make the following assumptions on the sampling distribution.
Assumption 5. The sampling distribution ps.., satisfies (T)).
When S,, contains i.i.d. samples from some underlying distribution Piree that satisfies (T). then by tensorization of transport inequalities [22], pss, satisfies (T() with Tn 7 In Example 2, we will consider Markovian data that satisfies Ti (Tx) with Tn O(n).
Suppose we work with a parametric family- 3 (f { where the parameter space θ is endowed with norm |1-lle. We impose the following assumption of Lipschitz parametric family.
Assumption 6. There exists K > 0 such that If (x) - (x)) S xl|0' 0ll for all x E X.
Proposition 4. Let p = 1. Assume Assumptions 1, 5 and 6 are in force Let t > O. Set
(t log M θ (1-1le)
On
n²
5

---

Then with probability at least 1 - e- all f E F, it holds that
2x
(f S (f: en) +
n
Proposition 4 shows that by choosing the radius properly, Lipschitz regularization upper bounds the true risk [true( (f) uniformly with high probability up to some terms. The radius en depends on the transport inequality parameter of sampling distribution in Assumption 5 and the complexity of the loss function class. When Tn = (n) and log. ; 6, ll-le) = Ó(1), we have On = (1/vn))
corresponding to the canonical choice.
For > 1, let us assume true continuous and define the population counterpart of en (x(2) in (2) as
Bxx-rmm [60 d(x, (11,
c(p) = sup fE
Proposition 5. Let E (1, Assume Assumptions 1, 3, and are in force. Let t >> 0. Ser
t :
Tt + log(1 (.
On (1 (L/n)²
2n
n2/p
Then with probability at least e for all f F, holds that
2k
C (f) S Cn (f: (fi 2n) (+)++
n + Coola+11n0 +2Le((pL/ em).
where Co equals h p = oo, h max(1, (Ip/n) ifp E (a + 100), and L(h/L) otherwise.
Recalling N, is the set of normalized slope defined in (1), and the inflation of the radius compared with the case of p = 1 is to compensate the discrepancy between || ||af|ll and ||0. The inflation factor well-defined so long as the Rademacher complexity of A, diminishes with respect sample size. The additional remainder term is similar to the one in Proposition 1, which measures the difference between (WO) and (VR) when the nominal distribution is Ftrue. The proof of Propositions 4 and 5 follows a similar flow as that of [17, Corollary 2], but our result extends it to non-i.i.d. and non-smooth settings.
Example (Linear Prediction with Polynomial Loss), Consider a supervised learning problem with feature vector x E 2 C IRd and a response variable y E y C R. Suppose | < B₁ for all
E L. and ly| < for all E V. Let θ be bounded set in TR. such that ||0|| - B3 for all O E θ. Consider a linear predictor with polynomial loss F = {(xxx y) + fe y) = 10 y/p 0 EET ②). We now discuss how to ensure the assumptions in Propositions supplementary. It is easy to verify that every fo(x, u) is Lipschitz in both variables and parameters, with α = pBB + B Bg- in Assumption 6. Suppose the samples are i.i.d. from Ptree satisfying TT(T), which implies Assumption with Tn = Tnp Hence we can apply Proposition 4, and by [36, Example 5.8], we have (o O, (l:le) S log(1 BBn).
with details in the
Example 2 (Markovian Data), In this example, we show that our Assumption 5 about ps.. can be satisfied for Markovian data. Consider homogeneous Markov chain on T with transition kernel P(dyla). Assume there exist ag 0,3 < an and C < 00, such that
I pollyl? P(dyla) S Mal,, Vx E X.
Let (xt) Mi be n consecutive outputs of this Markov chain. Then by Theorem 4.1 in [9], (As., satisfies (T(T)) with Fn 2n(1+logC) Thus Assumption 5 is satisfied.
Generalization Bounds for (Wasserstein) Robust Optimization
In this section, we develop the generalization bounds for (WO) and (RO), based on the results in previous sections.

---

5.1 Stochastic Setting
Combining the results in Sections and 4, we immediately obtain the following theorems.
Theorem 1. Let E (1,2) and t. >> O. Under the setup of Propositions I and 5, with probability at least 1 e- for for all f E ,, holds that
( (f) S f. (n) + Cn.
where
6n - Co)e (a+t)Ar 2Len ((pL/n)01 en) =2Le((pLn)))1 en) 2x
n
With the additional setup in Proposition 2, it holds that
2L b
f (f) L (F: Qm) + 6n
n
An
Theorem 2. Let = andd t > 0. Under the setup of Propositions and 4, with probability at least 1 e-t, for all f F, holds that
2x
Cevee()) (f) c
1 (f: 0n) + tn +
2k
C S ( Ch. (f: 2n) + tān
12
Both Theorems 1 and 2 show that by choosing reasonably small radius without suffering from the curse of dimensionality, the robust solution resulting from solving (VR), (RO), or (WO) has nice generalization bound, expressed as the robust loss plus high-order term. The high-order term depends mainly on the smoothness of the loss function indicated by a, the nonn)connemmtatton of probability distributions on non-differentiable points indicated by en, and the concentration of the maximal slope as indicated by An (resp. A,) in the expression of ca (resp. ε,,) (when the Wasserstein order p 1).
Example 3 (Unsupervised Learning). Consider the principal component analysis
{IIWTXI) XII:: : W
max WeR
that seeks for d principal directions, along which the data has maximized variance. Here X is a d x n sample matrix consisting of n samples {X;};= from P on a set L C {i E Rd ||æ||| < B); I|-II denotes the Frobenius norm; 1ş denotes the k-dimensional identity matrix; and W [[w..... w&] is the set of k orthonormal principal directions in Re.. Assume that P Penue satisfies T2(T), Em,PP ou [x]] 0, and the smallest eigenvalue of the covariance matrix Ez- [xx is positive. Letp= =2 and & = {z + fw (z) = -IIW x11 W W = 1x}- Below we verify Assumptions 1, 2, 3, 5, 6 as required by Theorem and compute the constants, and refer the supplementary for detailed calculation.
It is easy to verify that Assumption I since fw is 2Bk--ipschitz; Assumption 2 holds with 1; the zero-mean and non-singulat covariance of IP PPrue true imply Assumption 3; Assumption holds with Tn = т; and Assumption 6 holds with k = 2 2>2..2 Finally, to compute the covering number of the sei W (W W WWW W Tx observe that euch W consists of k orthogonal vectors, each of which belongs to the unit ball in Rd. Hence log ( W, ||-112) < kol(1 2n)). Thus, we improve the ( bound [39, Example 8) which has an exponential dependence d.
Before closing this subsection, we would like to emphasize that this stochastic setting is drastically different from the adversarial setting in the next subsection, for which many recent studies on the generalization properties of robust optimization. In fact, choosing good radius scaling scheme with nice finite-sample guarantees is at the core of Wasserstein DRO and remains open for quite some time until the recent work [17]. We generalize this result non-i.i.d. and non-smooth settings as well as for (RO).
7

---

5.2 Adversarial Setting
In the adversarial setting (Adv), we are trying to minimize the expected loss under the worst-case scenario when the learning algorithm is being purposely attacked by an adversary. By replacing Prree with n, in (Adv), we obtain the empirical adversarial robustness problem, which is the same as the Wasserstein robust optimization problem (WO). One of the most fundamental questions in adversarial robustness problem is to estimate the generalization gap between (Adv) and its empirical counterpart (WO). We aim to derive generalization bounds for E [1, co] by virtue of Theorems 1 and 3. Following the literature, this subsection, we assume IP, consists of i..dd samples from a continuous distribution true-
We start with p = 1.
Theorem 3. Let p 1. Under the setup of Proposition 3, assume that Ilfl M for all f E F. Let ō E [0, 2 and t > 0. Then with probability at least 1 c-t, holds that for every f E I,
1 (f: -7 (f: S 29 M 22 + 26, + Co 20
On the right-hand side of the inequality in Theorem 3, the first two terms are identical to the generalization bound of empirical risk minimization. The third term en from Theorem 3 is linear in the adversarial perturbation level which represents the inflation of generalization bound in the adversarial setting as opposed to the stochastic setting, whose dominating factor the concentration of the maximal slope. The rest terms are of higher-orde for small adversarial perturbation level that mainly depends on the smoothness of the loss function.
Next, we consider E (1, oo].
Theorem 4. Let p E (o). Under the setup of Proposition 1, assume that || S M for all
f f F. Let s et (4) and t > 0. Then with probability at least 1 - 2e- 1, it holds that for every FE
20, (0.gg) +
1
IC (f: - cat (f:ee) s 29 ($)
+ M
t
+
2n
2n
9 9. P-T
Cog + Len ((LL/T) + CCe²
Similar the case of p 1, the first two terms in the above bound is identical to the bound of empirical risk minimization, and the high-order term in the second row depends on the smoothness of the loss functions. The major difference from p is that, the inflation term in the adversarial setting depends on (0.3 )) the Rademacher complexity of the class of gradient norm functions. This term appears to be new in the literature. Intuitively, the complexity of the variation is small, the model is more robust to the adversarial perturbations and thus generalizes better.
Theorems 3 and are proved based on different strategy than that in the stochastic setting. Set (e) == minfes [T= [f] + ell@@fllly.... Using the triangle inequality we decompose the dif- ference S (fi e) L.dv (f: e)l into three terms (.w, (fi (J: e): 1 (fig) L (f;2)), | (f: Ø) Ladv (f: e) and then bound each term individually.
Concluding Remarks
In this paper, we thoroughly analyzed the finite-sample performance bounds for robust optimization, drawing connection with transport inequality and local Rademacher complexity. Our results generalize existing results from various perspectives, and particularly, to non-smooth loss functions and to non- i..d. data, both of which requires non-trivial analysis. Our results help to better understand the regularization effect of robust learning and explain their superior empirical performances. We hope our results can inspire regularization schemes for other applications as well. Our bounds involve the Rademacher complexities of (normalized) gradient norm function 0.F q. Ny, and margin to discontinuity Sy, which are non standard, we have provided various examples and will investigate in more depth for future work.
8

---

References
[1] Pranjal Awasthi, Natalie Frank, and Mchryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. arXiv preprint arXiv:2004.13617 2020.
[2] Daniel Bartl, Samuel Drapeau, Jan Obloj, and Johannes Wiesel. Robust uncertainty sensitivity analysis. arXiv preprint arXiv:2006. / /2022, 2020.
[3] Aurélien Bellet and Amaury Habrard. Robustness and generalization for metric learning. Neurocomputing, 151:259-200 2679 2015.
[4] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization. Princeton university press, 2009.
[5] Dimitris Bertsimas and Martin S Copenhaver. Characterization of the equivalence of robusti- fication and regularization in linear and matrix regression. European Journal of Operational Research, 270(3):931-985 2018.
[6] Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust wasserstein profile inference and applications to machine learning. Journal of Applied Probability, 56(3):830-857, 2019.
[7] Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565-600, 2019.
[8] Jose Blanchet, Karthyek Murthy, and Nian Si. Confidence regions in wasserstein distributionally robust estimation. arXiv preprini arXiv: 0ee.119966011.1 2019.
[9] François Bolley and Cédric Villani. Weighted plications to transportation inequalities. In Annales de la Faculté des sciences de Toulouse: Mathémattiuues, volume 14, pages 331-355 2005.
inequalities and ap-
[10] Sébastien Bubeck, Yin Tat Lee, Eric Price, and lly Razenshteyn. Adversarial examples from computational constraints. In International Conference on Machine Learning, pages 831-840 PMLR, 2019.
[11] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, and John Duchi. Unlabeled data improves adversarial robustness. Advances in neural information processing systems, 2019.
[12) Ruidi Chen and loannis C Paschalidis. A robust learning approach for regression models based on distributionally robust optimization. Journal of Machine Learning Reseurch, 19(1)), 2018.
[13] Zac Cranko, Simon Korbliihh, Zhan Shi, and Richard Nock. Lipschitz networks and distribu- tional robustness. arXiv preprint arXiv:/809.01129, 2018.
[14] John C Duchi and Hongseok Namkoong. Variance-based regularization with convex objectives.
J. Mach. Learn. Res., 20:68-1, 2019.
[15] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metrie: Performance guarantees and tractable reformulations. Mathemati- cal Programming. (11(1):15--166) 2018
[16] Chris Finlay, Jeff Calder, Bilal Abbasi, and Adam Oberman. Lipschitz regularized deep neural networks generalize and are adversarially robust. arXiv preprint arXiv:1808.09540. 2018
[17] Rui Gao. samile guarantees for wasserstein distributionally robust optimization: Break- ing the curse of dimensionality. arXiv preprint vrXiv:2009.04382 2020.
[18] Rui Gao, Xi Chen, and Anton Kleywegt. Wasserstein distributional robustness and regulariza- tion in statistical learning. arXiv, pages 171iv-1712, 2017.
[19] Rui Gao and Anton J Kleywegt, Distributionally robust stochastic optimization with wasserstein distance. arXiv preprint 160iv: 1604002/00400999 /99, 2016.
[20] Rui Gao and Anton J Kleywegt. Distributionally robust stochastic optimization with dependence structure. arXiv preprint 170.0:1001.04200, 2017.

---

[21] Jun-ya Gotoh, Michael Jong Kim, and Andrew EB Lim. Robust empirical optimization is almost the same as mean-variance optimization. Operations research letters. 46(4):448 4522. 2018.
[22] Nathael Gozlan and Christian Léonard. Transport inequalities. a survey. Markov Processes and Related Fields, 16:635-736, 2010.
[23] Hisham Husain. Distributional robustness with ipms and links to regularization and gans. arXiv preprint arXiv:2006. 04349, 2020.
[24] Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. arXiv preprint arXiv: 1810.095 19, 2018.
[25] Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, and Soroosh Shafieezadeh- Abadeh. Wasserstein distributionally robust optimization: Theory and applications in machine learning. In Operations Research & Management Science in the Age of Analytics, pages 130-166. INFORMS, 2019.
[26] Henry Lam. Recovering best statistical guarantees via the empirical divergence- based distribu- tionally robust optimization. Operations Research, 1990)1100- 2019.
[27] Jaeho Lee and Maxim Raginsky. Minimax statistical learning with wasserstein distances. Advances in Neural Information Processing Systems, 31:2687-2696 2018.
[28] Olivier Marchal, Julyan Arbel, et al. On the sub- gaussianity of the beta and dirichlet distributions. Electronic Communications in Probability, 22, 2017.
[29] Mehryar Mohri and Afshin Rostamizadeh. Rademacher complexity bounds for non-iid processes. In Proceedings of the st International Conference on Neural Information Processing Systems, pages 1097-1104, 2008
[30] Amir Najafi, Shin-ichi Maeda, Masanori Koyama, and Takeru Miyato. Robustness to adversarial perturbations in learning from incomplete data, Advances in Neural Information Processing Systems, 32:5541-5551, 2019.
[31] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adversarially robust generalization requires more data. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 5019-5031, 2018.
[32] Soroosh Shafieezadeh-Abadhh Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation. Journal of Machine Learning Research, 20(103): 2019.
[33] Nian Si, Jose Blanchet, Soumyadip Ghosh, and Mark Squillante. Quantifying the empirical wasserstein distance to a set of measures: Beating the curse of dimensionality. Advances in Neural Information Processing Systems, 33, 2020.
[34] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. International Conference on Learning Representations, 2018.
[35] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representations, 2018.
[36] Martin J Wainwright. High-dimensional stafistics: A non-asymplotic viewpoint, volume 48. Cambridge University Press, 2019.
[37] Huan Xu, Constantine Caramanis, and Shie Mannor. Robustness and regularization of support vector machines. Journal of machine learning research, 10(7), 2009.
[38] Huan Xu, Constantine Caramanis, and Shie Mannor. Robust regression and lasso. IEEE Transactions on Information Theory, 566))3361-33344 2010.
[39] Huan Xu and Shie Mannor, Robustness and generalization. Machine learning, 86(3):391 2012.
10

---

[40] Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. International Conference on Machine Learning, pages 7085-7094. PMLR, 2019.
[41] Tom Zahavy, Bingyi Kang, Alex Sivak, Jiashi Feng, Huan Xu, and Shie Mannor. Ensem- ble robustness and generalization of stochastic deep learning algorithms. arXiv preprint arXiv:1602.02389. 2016.


Reviews:
[{"review_id": "iAaaNNb0am_", "reviewer": "Reviewer_vWvJ", "summary": "This paper derives finite-sample generalization bounds for robust optimization and Wasserstein distributionally robust optimization. The authors consider a broad class of piecewise Hölder smooth loss functions, under both stochastic setting—i.i.d. or weakly dependent data—and adversarial environment, assuming that the underlying data-generating distribution satisfies transportation-information inequalities. The proofs are built on a general connection between robustness and variation regularization (including Lipschitz and gradient regularization, among others) and new local Rademacher complexity results for variation regularization. ", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Besides the  Wasserstein distributionally robust optimization (WO) problem，this paper considers the robust optimization (RO) problem and establishes new general bounds. Specifically, in the stochastic setting, under proper choice of the radius $\\varrho_n$, this paper derive finite-sample guarantees for (RO) and (WO) that apply to non-i.i.d. data and non-smooth losses. For non-i.i.d. data, this paper exploits different notions of transport inequality and Rademacher complexity than the i.i.d. case. In the adversarial setting, generalization bounds for (Adv) with fixed small radius $\\varrho_n$ are derived.\n\n2. The analysis of this paper is based on the connection between robustness and regularization. The proposed results improve the sandwich bounds in Gao et al. (2017) for $p = 1$, and generalizes the results therein to piecewise Hölder smooth loss functions for $p\\in (1,\\infty].\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "anhBUFRssR", "reviewer": "Reviewer_XTX2", "summary": "This paper aims to theoretically analyze (and compare) a number of different robust learning paradigms. In particular, it has been shown that three different notions of robustness, namely 1) robust optimization 2) Wasserstein distributionally robust optimization, and 3) variation regularization, would result in close loss functions (based on some non-asymptotic bounds) whenever the strength of attacks becomes infinitesimally small. While connections between such methods have been conjectured (or even analyzed) in some recent works, I still found the results in this paper interesting.\n\nAlso, author(s) have tried to achieve non-asymptotic generalization bounds for cases where data samples are weakly-dependent (instead of i.i.d. generated) and/or the space of loss functions are only piece-wise smooth. I have not checked the proofs for this part, and results have not been clearly discussed nor compared with existing ones.\n\nOverall, a well-motivated paper which tries to add a number of nice contributions to the area. However, paper suffers from lack of clarifications and intuitive discussions in order to shed light on the technical significance of its many theorems. Also, some notations in parts of the paper (including theorem 2) are not properly framed. Another problem with this work is that author(s) might have missed many existing works that have already tried to analyze the same (or at least slightly different) problem sets. As a result, paper is not well-positioned w.r.t. the literature and cannot be easily compared with other researches.\n\nI cannot recommend the paper for acceptance in its current shape, thus my vote at this stage is weak reject.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nPaper is well-motivated. The fact that data samples can be generated in a weakly-dependent manner instead of the common i.i.d. assumption is nice. Also, considering piece-wise smooth functions instead of globally smooth ones is interesting for many applications. Moreover, author(s) have put so much effort to write the paper in a mathematically comprehensive way. This has (unfortunately) reduced the readability of the paper, but has made it technically rigor (except for a few parts, described below). By the way, I have not checked all the proofs.\n\n----------------------------------------------------------------------------------------------------------------\n\nWeaknesses: There are several issues with the manuscript\n\n1) Paper is well-organized, but when someone goes into details it is not written in an informative way. In many cases, several layers of nested definitions have been made with few to no intuition for the reader. Understanding the statement of main theorems requires one to go through all these cryptic definitions with so many parameters and variables. This problem has reduced the clarity of results and has made the paper hard to read. A total of 8 assumptions have been made throughout the main manuscript (haven't completely checked the supplements), almost all mathematically encrypted. And authors have not provided enough discussion on why making such assumptions could be plausible in real-world. One reason for all the above-mentioned issues might be due to the fact that author(s) have tried to fit so much content in a page-limited manuscript. Therefore, I kindly suggest to the author(s) to consider sending the paper to a journal instead of a conference.\n\n\n2) Paper is not well-positioned w.r.t. many recent works which have also addressed the generalization aspects of adversarial robustness in a distributionally robust setting. For example, Sinha et al. (2017), Carmon et al. (2019), Najafi et al. (2019), and several other works have recently proposed generalization guarantees for DRL (a.k.a. DRO) where generalization gap is $O\\left(n^{-1/2}\\right)$, similar to Theorem 6 of the current work. What has been improved in this work compared to existing results? This question is either left unanswered in this work, or the significance of the current results is buried under tones of cryptic and non-intuitive definitions and statements. In the latter case, author(s) should point out to the potential improvements and/or fundamental differences.\n\n\n3) There are some technical ambiguities that need to be addressed: \n-Theorem 1 is interesting. However, author(s) have not compared it well enough w.r.t. to existing works in the literature. The fact that distributionally robust learning has connections to some types of smoothness regularization over the hypothesis space is already known to the community (For example, check the keyword \"distributional smoothing\"). What is the main advancement in this particular theorem? For example, how is it different from Gao et al. (2017), also cited by the author(s), since I noted a rather similar result in Lemma 1 of that work.\n\n\n-Paper seems to be rushed in some parts. For example, Theorem 2 is supposed to be one of the main contributions, still its statement is not correctly framed: What is parameter $t$? Does having $\\varrho_n\\rightarrow 0$ when $n\\rightarrow\\infty$ suffice? does the rate of convergence toward zero matter? I assume they all affect the integer $N$, however, such issues need to be clarified. Otherwise, author(s) cannot claim the bound in this theorem is \"non-asymptotic\" since $N$ can become uncontrollably large.\n\n---------------------------------------------------------------------------\nMinor comments: \n\n-(Line 67): the word \"generalization\" is repeated.\n-(Line 118): This line doesn't make sense, unless one assumes $\\inf_{y\\in\\mathcal{D}_f}\\left\\Vert x-y\\right\\Vert$ instead of what has been written. Also, a full stop is missing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No problem here.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "TLPPqULaX0K", "reviewer": "Reviewer_A21Q", "summary": "The paper studies the generalization performance of minimizing Distributionally robust optimization (DRO) losses. In particular, it uses existing results that connect DRO to penalty (or regularization) based objectives and employs learning theoretic results to achieve concentration inequalities which ultimately manifest as a DRO generalization bound.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This submisison studies the generalization properties of DRO with quite interesting results by essentially merging different paradigms of proof techniques which appear nice conceptually. I believe the problem laid out is important however it is not clear to me how the offered bounds precisely resolves and adds anything actionable to the area of using DRO. Furthermore, this bleeds into my main concern which is that the results are highly inaccessible in their current form and difficult to understand their ramifications. I would prefer if the authors can clearly specify some benefits of their methods or existing work their methods provide validation for (specific methods as opposed to simply stating stochastic settings). \n\nThe correctness of the paper is of high standard as I have not found any mistake in the proofs after checking them and I find that all notation is self-contained which the authors should be applauded for given the dense machinery they have employed.\n\nWith regards to related work, they have focused on discussing work that relates to their proof techniques while briefly touching upon the adversarial training set-up. It seems they are missing quite a key reference since they have an entire paragraph of their related work discussing previous work on the link between robustness (DRO) and regularization yet a quick search with the words \"distributional robustness and regularization\" yields a NeurIPS2020 paper [1] which they don't seem to discuss. Other papers along this line can also be found for other cases which may be relevant such as https://www.jmlr.org/papers/volume10/xu09b/xu09b.pdf. Can the authors comment as to how the results in these papers relate to this or why it is irrelevant? \n\nThe applications they have are quite underwhelming since their motivation for a theoretical study is to better understand adversarial training (which often occurs in deep learning) yet their applications do not include a specific study on this - I would be interested to know any comments on this.\n\nMy other main concern is that the bounds contain several Rademacher complexities, some of which are highly inaccessible or difficult to grasp - my understanding is that Rademacher complexities are typically large and only for specific settings can be explicitly computed. For the case of neural networks, even a 2-layer neural network, do you have any comments on how the generalization bounds would look like? I'm especially interested to see the shape of Theorem 7.\n\nOverall, while studying the generalization properties is important, I think the core theorems of the paper are quite simple combinations of existing DRO results and concentration inequalities which at the moment are unclear of their practical use for the motivated setting of adversarial robustness in deep learning. The specific analysis contains some more technical results however they are not motivated for the same problem and therefore fall short of a cohesive story. I will currently rate this as a reject however I am interested to see if the authors have any derivation for the deep learning setting or perhaps something more actionable for specific methods as opposed to explaining 'superior performance' of an entire paradigm they refer to as 'robust learning' - the ambiguity here is dangerous since there are many variants of robust learning which clearly have differing performances, not many of which the results at this stage comment on.\n\n[1] Husain, H. (2020). Distributional Robustness with IPMs and links to Regularization and GANs arXiv preprint arXiv:2006.04349", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes they have.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "0F8FY1grFFI", "reviewer": "Reviewer_HGjU", "summary": "This paper studies the finite-sample generalization bounds for robust optimization and Wasserstein distributionally robust optimization. The results are more general than existing literature as they extend to piecewise Holder smooth loss functions. Besides the major contribution, the authors also provide application of the theorems in several examples, e.g. expected shortfall in Section 6.4 and adversarial training in Section 6.5. These examples show the usefulness of the main theorems.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: this paper has a clear literature review and compares the main results with the existing literature. The results in this paper are solid and novel.\n\nSignificance: this paper provides a lot of examples in various scenarios. These examples illustrate the significance of this paper to some extent. In addition, based on my knowledge, there is no existing literature that clearly studies the connection between distributional robustness and adversarial training. Improving the bounds is a contribution to this area, and utilizing it to other areas also brings more potentials.\n\nClarity and quality: this paper is well organized with clear illustrations. There is no experimental results, but numerical results are not essential for this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, the paper contains interesting technical contributions on generalization bounds for DRO problems. However, the technical exposition makes it difficult to access the results in the paper and has left much to be desired. In particular, the motivations and technical development need to be substantially improved.
Decision: Accept (Poster)