Tikhonov Regularization is Optimal Transport Robust under Martingale Constraints
Authors: Jiajin Li
Sirui Lin
Jose Blanchet
Viet Anh Nguyen
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distributionally Robust Optimization
Optimal Transport
Tikhonov Regularization

Abstract: Distributionally robust optimization (DRO) has been shown to offer a principled way to regularize learning models. In this paper, we find that Tikhonov regularization is distributionally robust in an optimal transport sense (i.e. if an adversary chooses distributions in a suitable optimal transport neighborhood of the empirical measure), provided that suitable martingale constraints are also imposed. Further, we introduce a relaxation of the martingale constraints which not only provide a unified viewpoint to a class of existing robust methods but also lead to new regularization tools. To realize these novel tools,  provably efficient computational algorithms are proposed. As a byproduct, the strong duality theorem proved in this paper can be potentially applied to other problems of independent interest. 

Tikhonov Regularization is Optimal Transport Robust under Martingale Constraints
Jiajin Li
Sirui Lin Stanford University
José Blanchet
(jiajinli, siruilin, jose. (anchet)@stanfoool edu
Viet Anh Nguyen Chinese University of Hong Kong nguyen@se. cuhk, edu.
cuhk
Abstract
Distributionally robust optimization has been shown to offer principled way to regularize learning models. In this paper, find that Tikhonov regularization is distributionally robust in an optimal transport sense (i.e., an adversary chooses distributions in suitable optimal transport neighborhood of the empirical measure), provided that suitable martingale constraints are also imposed. Further, we intro- duce relaxation of the martingale constraints which not only provides unified viewpoint to a class of existing robust methods but also leads to new regularization tools. To realize these novel tools, tractable computational algorithms are proposed. As a byproduct, the strong duality theorem proved in this paper can be potentially applied other problems of independent interest.
Introduction
Regularization is important tool in machine learning which is used in, for instance, reducing overfitting [23]. Recently, ideas from distributionally robust optimization (DRO) have led to fresh viewpoint on regularization precisely in connection overfitting: see, e.g., [7, 20, 10, 29, 24, 25,5) and the references therein.
In these references it is shown that many standard regularization-bann estimators arise the solution of a min-max game which one wishes to minimize a loss over a class of parameters against an adversary that maximizes the out-of-distribution impact of any given parameter choice, that certain way. The choice of adversarial
is, the adversary perturbs the empirical distribution distributions or perturbations in DRO is often non non-paraeetric thus providing reassurance that the decision reasonably robust to a wide range of out-of-distribution perturbations. For example, such non-parametric choice is given by employing optimal transport costs [31] to construct so-called distributional uncertainty set (e.g. a Wasserstein ball around the empirical distribution) for the adversary to choose. [27] shows that optimal transport- based DRO (OT-DRO) is closely related to adversarial robustness in the sense steepest gradient loss contamination. This can be further explained by OT-DRO's hidden connection with generalized Lipschitz regularization [7]. Thus, understanding if a well-known regularization technique is actually distributionally robust and in what sense, allows
understand its diit---disttibttionn benefits and potentially introduce improvements.
In this paper, we introduce novel set of regularization techniques which incorporate martingale constraints into the OT-DRO framework. Our starting point is the conventional OT-DRO formulation. The conventional OT-DRO formulation can generally be interpreted as perturbing each data point in such way that the average size perturbation is less than given budget. In addition to this
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

conventional formulation. we will impose a martingale constraint in the joint distribution of the empirical data and the resulting adversarially perturbed data.
Why do we believe that the martingale constraint makes sense as a regularization technique? It turns that two random variables X and X form martingale in the sense that [[X = X if and only if the distribution of X dominates X in convex order [30]. In this sense, the adversary X will have higher dispersion in non-parametric sense than the observed data X but in suitably constrained way so that the average locations are preserved. This novel OT-DRO constrained regularization, we believe, helpful to potentially combat conservative solutions, see [16]. Moreover, by allowing a small amount of violation in the martingale property, we can control the regularization properties of this constraint, thus obtaining a natural interpolation towards the conventional OT-DRO formulation and potentially improved regularization performance. We point out that related optimal transport problems with martingale constraints have been studied in robust mathematical finance [1. 8).
Consider, for example, the linear regression setting with the exact martingale constraints, which means that for any given observed data point, the conditional expectation of the additive perturbation under the worst-case joint distribution equals zero. Surprisingly, we show that the resulting martingale DRO model is exactly equivalent the ridge regression [18] with the Tikhonov regularization. To the best of our knowledge, this paper is the first work to interpret the Tikhonov regularization from DRO perspective showing that it is distributionally robust in a precise non-parametric sense. In stark contrast, it is well-known that the conventional OT-based DRO model (without the martingale constraint) is identical to the regularized square-root regression problem [2]. Therefore, introducing an additional power in norm regularization (i.e., converting square-root regression to Tikhonov regularization) can be translated into adding martingale constraints in the adversarial perturbations thus reducing the adversarial power. A natural question that arises here is whether we can interpolate between the conventional DRO model and the Tikhonov regularization, and further improve them.
We will provide a comprehensive and positive answer to the above question in this paper. The key idea here is to relax the equality constraint on the conditional expectation of the adversarial violation and thus allow a small perturbation of the martingale property to gain more flexibility of the uncertainty set. This idea leads to another novel model, termed the perturbed martingale DRO the sequel. Intuitively, if the relaxation is sufficiently loose, the perturbed martingale DRO model will reduce to the conventional DRO, which is formally equivalent to setting an infinite amount of possible violations for the martingale constraint. By contrast, if no violation is allowed, the perturbed martingale DRO will automatically reduce to the exact counterpart - Tikhonov regularization. As a result, we are able to introduce new class of regularizers via the interpolation between the conventional DRO model and the Tikhonov regularization.
Furthermore, such insightful interpolation also works for a broad class of nonlinear learning models. Inspired by our extensive exploration of linear regression, the developed martingale DRO model can also provide a new principled adversarial training procedure for deep neural networks. Extensive experiments are conducted to demonstrate the effectiveness of the proposed perturbed martingale DRO model for both linear regression and deep neural network training under the adversarial setting.
We summarize main contributions below:
We reveal a new hidden connection in this paper, that is, Tikhonov regularization is optimal transport robust when exact martingale constraints (i.e., convex order between the adversary and empirical data) are imposed.
Upon this finding, we develop a new perturbed martingale DRO model, which not only provides a unified viewpoint of existing regularization techniques, but also leads to a new class of robust regularizers.
We introduce an easy-to-implement computational approach to capitalize the theoretical benefits in practice, in both linear regression and neural network training under the adversarial setting.
As a byproduct, the strong duality theorem, which is proved this paper and used as the main technical tool, can be applied to wider spectrum of problems of independent interest.
2 Preliminaries
Let us introduce some basic definitions and concepts preparing for the subsequent analysis.
2

---

Definition 2.1 (Optimal transport costs and the Wasserstein distance [21, 31]). Suppose that -(-:-)= RR x TR& + [0, oo] is lower semi-contiuous cost function such that c(X,x X) = 0 for every X E TR:
The optimal transport cost between two distributions Q and IP supported on R is defined as
D PQ.
A
min TEP(XXX)
[En [c(X, PIT=0, P2T=
Here, P(X 2) is the set of joint probability distribution of (X) supported on X x X while PiT and P2 respectively refer to the marginals of X and under the joint distribution n.
If of x)= |X X|| is any given norm RR4, then D recovers the Wasserstein distance [31]. In this paper, we are interested in a flexible family of functions for the computational tractability, so called the Mahalanobis cost functions in the form of c(X, (X x) M (X X), where M is a d-by-d positive definite matrix.
Next, consider the conventional OT-DRO problem:
sup [+((((((X))]
min (P p), where p) A
t. T REP(X x x)
(2.1)
Ry [c( S p. P2 =
where P A 1 Ei= 6x, is the empirical distribution. Using Definition 2.1, we have p) = max P( Eq (g]e(fa(X))), which is the worst-case expected loss under all possible distributions around the empirical measure IP at most with respect to the OT distance. It is well-known that under appropriate assumptions, the DRO problem (2.1) is equivalent the regularized square-root regression problem.
N
Proposition 2.2 ([2, Proposition 2.D). Suppose that (i) the loss function E(-) a convex quadratic
function, i.e., (-E(.) = Y > O, where y is a constant, (ii) the feature mapping fe(X) = BT X is
linear, and (iti) the ground cost e the squared Euclidean norm on X Rd. Then
Lo(P, Lo(e,))((VE,(00GG +V
We also present the strong duality result for a general class of optimal transport based DRO models with martingale constraints. This result serves as our main technical tool for reformulating the DRO models, and it can also be applied to other semi-infinity structured DRO models, which could be of independent interests. We consider the primal problem
sup f dr s.t. π TE P(X x X) Sxxx cx,, X) dr S P, P2t P
(Primal)
E, X = P-as.
and its associated dual form
N
N
inf XER CRER"
Ap
X1
+
Σ sup - x Xc X.)
(Dual)
N
==1
Here, f: X' + IR is upper cami-continuous and L' -integrrable. The next theorem states the strong duality result linking these two problems.
Theorem 2.3 (Strong duality). Let P
N EIEIN 8x, be the reference measure. Suppose that (i) every sample point is in the interior of the cone generated by X, i.e.. X; int(cone(xx)) Vi [N], and (ii) the ambiguity radius p > O. Then the strong duality holds, i.e., Val(Primal) = Val(Dual).
Remark 2.4. At the heart of our analysis tools is the abstract semi-infinite duality theory for conic linear program 126, Proposition 3.4]. Notably, it will be tricky and subtle to reformulate our problem into the standard form and further carefully check the general Slater condition. Moreover, we indeed fill the technical gap in [19, Theorem 4.2).
3

---

Notation, We use 84 to denote the set of d-by-d positive definite matrices and || - vX MX for any X E Rd,
, M E $4.: if M is the identity matrix, then omit M and write ||| - VXT X. We use ōx to denote the Dirac measure at X and let P a N Ei= ox, be the empirical measure constructed from sample (.
We use Ep to denote the integration over P: Ep]f(X)] = Ix ((X)dP Specifically, for (X, following joint distribution т, [x Jxxx c(X, )dT, [x[f((]]= = fxxx (d)d.. We use E(.) to denote the loss function applied to the parametrized feature mapping fa. Let VI(-), V-(()) be the first and second order derivative of e(-) respectively. Notably, we use (P, p) to denote the objective function of the conventional DRO model (2.1); use (I, p) to refer to the exact martingale DRO model (3.1); use CP p.e) to refer to the perturbed martingale DRO model (3.2).
3 Tractable Reformulations
In this section, we introduce an optimal transport-based DRO model with the exact martingale constraint at first. That is, on top of the vanilla DRO model [3], we add an additional martingale equality constraint on its coupling. It is surprisingly interesting to find out that the resulting DRO approach is equivalent to empirical risk minimization with Tikhonov regularization. Naturally, can relax the equality constraint and thus allow a small violation the martingale property to enrich the uncertainty set. Formally, by sending violation size to infinity in the martingale constraint, our relaxation allows to interpolate between the conventional DRO formulation (i.e. with no martingale constraints) and Tikhonov regularization (which involves exact martingale constraints). Therefore, this relaxation further leads to a new class of regularizers in principled way, which improves upon Tikhonov regularization
show in our experiments.
Assumption 3.1. The following assumptions hold throughout.
(i) The ground cost -) is the Mahalanobis cost with the weighting matrix M E S4+, (i) The domain X is unconstrained, i.e., X' = =d.
3.1 Optimal Transport-based DRO with Martingale Constraints
To start with, we investigate the exact martingale DRO problem:
sup [((((((X))]
s.t.
TE P(X x x)
min
(P. p), where La(P. p) e 3
(3.1)
Ex [c(( x)] I p, P2T =
E X = X P-as..
and p 2 0 is the radius of uncertainty centered P. Note that because PP is the empirical measure, the martingale constraint implies that the conditional expected value of the perturbation obtained by modifying each observed data point equals the observed data point itself. The quantity L p) referred to as the worst-case expected loss of the model parameter 3 under the martingale DRO
model. It is easy to see that (F p) < (2 p). where Lg is defined as in 12. This is because the adversary in (3.1) has smaller feasible set, and thus is less powerful than the adversary in (2.1).
Hence, the martingale DRO solution for problem (3.1) is considered to be less conservative than the conventional DRO solution for problem 12.
The next result asserts that the martingale DRO problem coincides with the Tikhonov regularization problem under similar conditions of Proposition 2.2.
Proposition 3.2 (Tikhonov equivalence). Suppose that (i) the loss function E(-) is convex quadratic function, i.e., V=((-) = 7 > O, and (ii) the feature mapping fa(X) = 8 X is linear. Then we have
La(P, - E X)]
TP 11 -
If the Mahalanobis matrix M is the identity matrix, the martingale DRO model (3.1) recovers the Tikhonov regularization problem.

---

Proof of Proposition 3.2. By change of the variable, let A = X - X and we have
sup
E |e(BT (X+4)))
sup B B-ARR Sp 0
E
[(3 X) + Ve(B" X)8
A 20107 A|2
I S
Ep LEB X)
sup
E
? 2
113
F. [x|
Epp (((B")) 7P |1
The last equality follows from the general Hölder's 's inequality. To achieve the equality, we can, for example, take normally distributed random variable C with mean 0 and variance p and which is independent of X, and then let A = CCM133.
Example 3.3 (Linear regression). Let X & (Y,Z") Ra and BT & (1.-bT) E R2, we have x = Y bo Z. For any Q E 84-1, we take M = diag( t00, , Q). which implies that we do not allow transport of the response Y, then the problem (3.1) with ? becomes
min
Eg [Y
bt z)
e plbbl8--
In Appendix C.I, we give another instructive proof based on the strong duality result in Section 2. For general convex loss functions, we have the following certificate of robustness that provides upper and lower bound for the worst-case DRO loss in (3.1).
Corollary 3.4 (General convex loss functions). Suppose that (i) the loss function E(-) is p--ttrongy
convex and C-soooth, that is, E(O) 2 2(0') VE(6") 0) + 1 (6' 0)² and {(0) S ((0'
((((0)(0' 6) + G - 8)² hold for all 0, 0' R, and (ii) the feature mapping fx(X) x is linear. Then we have for any p 2 O,
[p(((f((X)]] + 1P 11 S La (P s Exl((f(())) + CP 1111311 2
Example 3.5 (Logistic regression). Let X YZ E Rd, where Z Rd Y {+1} and ((t) log(1 + exp(-t)), where e(.) satisfies Assumption (i) in Corollary 3.4 with C = 2. Then we have
La (P. .) s Rp[log(1 + exp( 2)) -
3.2 Optimal Transport-based DRO with Perturbed Martingale Constraints
Now we turn to the relaxation of the martingale constraint to improve upon Tikhonov regularization and gain more flexibility. We consider the perturbed martingale coupling based DRO model (perturbed martingale DRO):
sup [+(((((())]]
s.t. TE P(X' x xx)
min CPP p,e), where (s(P,
(3.2)
E cc(8 X)] S., P2t P
E X X] X| Se P-a.s
The parameter e controls the allowed violations of the martingale constraint for the adversary. is trivial that if we set c 0, then we obtain (P = (F() and we recover the exact martingale DRO model (3.1). we set + 3o then the martingale constraint becomes ineffective, thus we have L. (IP, +oo) = Lo (P., p) and model (3.2) collapses to the DRO formulation (2. I). We thus can think of
interpolating parameter connecting two extremes: the conventional DRO model (2.1) (at e = +00) and the exact martingale DRO model (3.1) (at c c= 0).
However, the resulting optimization problem (3.2) constitutes an infinite-dine dimensional optimization problem over probability distributions and thus appears to computationally intractable. To overcome this issue, we leverage Theorem 2.3 and prove that the problem (3.2) is actually equivalent finite-dinen mnite-dimensional problem. begin with, we present one crucial proposition that can be applied to more general settings.
5

---

Theorem 3.6 (General loss functions and feature mappings), Suppose that the loss function E(.) and the feature mapping fa(-) upper temi-continuous. Then, for any p >> 0 and e > 0. the perturbed martingale DRO model (3.2) admits
N
Ls (,,
inf Ap 220
Σ
Ilasllas-1+
sup A
(((s(X aJ D. A|
(3.3)
Sketch of proof. The key step is to decouple (3.2) as a two-layer optimization problem: (s(
sup Il Iallasse a
Sxx (aa(a (X))dr sup
s.t
E P(X X)
(3.4)
Sxxx c(x, x)dm S. P=== = Sxxx (X) Xd = (
W
Then we invoke Theorem 2.3 for the inner maximization problem over and apply the Sion's minimax theorem [28] for the outer maximization over 1). The desired result is obtained.
Due to the specific structure of the quadratic cost and the linear feature mapping, the dual variable À admits a closed-form representation and E R in (3.3) can be reduced to N parallel one- dimensional optimization problems. Upon this observation, we thus conduct an instructive and intuitive reformulation in Theorem 3.7 for linear regression with proof detailed in Appendix C.2.
Theorem 3.7 (Linear regression). Suppose that (i) the loss function f(.)) is convex quadratic function, iee. (-((.)) =y > and (ii) the feature mapping fa(X) B X is linear. Then, the perturbed martingale DRO model (3.2) admits:
pp - Ex(((s(())]] + p|/31/ M-1 + +R(3))
(3.5)
where the additional regularizer is defined as R(B) || min ( + / s112)
SERN
and G3 (1)....))..... Ve(BTXN))
E IN.
Obviously, compared with the exact martingale constraint investigated in Proposition 3.2, the per- turbed constraint we consider here involves an additional term R(3). Fortunately, armed with Lemma D.3, we are able to shed light on its intuitive interpretation based on the quantitative relationship between modeling parameters e and p. First, we discuss two extreme cases - there are interesting hidden connections between (3.2) and other existing regularization techniques.
Remark 3.8. Intuitively, if relatively small, the optimal s* is zero which means that all perturbed martingale constraints will be active. Precisely, if S the additional regularization term satisfies R(3) I x ([fa(X))l 11). which so-called Jacobian or input gradient regularizer in the literature when M is an identity matrix. Recently, it has received much intention owing to its ability to improve adversarial robustness [32, 9]. Conversely, p relatively small, the optimal s* is equal to Gg. implying that none of perturbed martingale constraints is active. In fact, if 2 " Np, we have R(B)- / x
easily figure out that C p. E) can be reduced to the conventional OT-based DRO model in Proposition 2.2.
Then,
Then for the middle case, it is natural to infer that only part of constraints will be active. In Lemma D.3, justify this conjecture rigorously. We refer the reader Appendix D for the details. As such, the proposed martingale DRO model takes the first step bridging the input gradient regularization and regularized square-root regression problem in unified framework. On the other hand, it also opens up an exciting brand new avenue of robustified regularizers. In the next section, we validate its effectiveness for the adversarial training task.
4 Optimization Algorithms
To take advantage of the proposed perturbed martingale DRO model, a natural question here is whether we can address problem (3.2) in tractable manner. In this section, we answer the above question in the affirmative by developing two different computational paradigms for linear regression and deep neural network respectively.

---

Dataset
Mg Datoret
Hpg Dalaset
Adhaa-aii WASE
32.3
23.0
Vaniegale 31D
Tystesev Reguartzstan
Adversoriall R0N-5
1.0
Vart D50
Linar Rograsion
Reguiaiiation
Adveersntt RUISE
10 tinggl USSO
Tychoncx fleguleriation
20.5-
1.8
10.3"
1.4
15.6
1.2
1.0
30.5
0.2
0.
0.
0.6
PGD Artart Sire
PGD Attack Step Size
PGD Attack Step Size
(a) Housing
(h) Mg
(c) Mpg
Figure 1: Compare the proposed martingale DRO with standard benchmarks (linear regression and ridge regression) on three real world datasets - Housing, Mg and Mpg. The martingale DRO performs better than competing methods under large PGD step size. 4.1 Subgradient Method for Linear Regression
Unfortunately, the resulting formulation we conducted in Theorem 3.7 (i.c., (3.5)) for linear regression potentially intractable for optimizing (3, s) jointly. One obvious computational challenge here is that the overall problem is not necessarily convex in (3, s). even if the original problem is convex over 3. This is because the minima of convex functions not convex. However, under mild assumption, it is possible to give a reliable computational routine for solving the resulting problem over / directly.
To start with, a key observation is Ca p, is convex over 3. This is essentially from the fact that the pointwise supremum of class of convex functions is still convex. To check the details,
C (P, p)e) originally defined in (3.2) and E, (((f((X)) is convex over 3 for all æ. Thus, a natural yet simple algorithm is subgradient method. The main difficulty is to obtain the correct subgradient oracle. Since the first two terms are smooth and strongly convex, we know that R(3) is weakly convex and thus subdifferentially regular. All the subdifferential concepts are coincide. As such, we may simply use the Clarke subdifferential [6] in the sequel. Moreover, the sum rule is hold for computing the subgradient of C (P,, p, e) due to the weakly convexity. We have
(1 (TP p, B ((EE((((s((()) V p| + 0gR(3).
The remaining question is how to compute the Clarke subdifferential of R(3). When e² e² p and 22 2 N,, R(3) will enjoy the convex composite structure. Thus, by invoking the chain rule developed in [22, Theorem 10.6) directly. The more subtle and tricky case is the middle one - p < e < N Without of loss generality, assume that M T for simplicity. Based on [6, Theorem 2.3.9], we have
get the correct subgradient
N
0g R(3) S Conv 0g
c
Σ i=1
15
-
s* E S(B)
N
N
where S(3) is the optimal solution set and Conv(.} denotes the convex hull. If we assume the inclusion here is tight, then the vanilla subgradient method will converge to the optimal solution with the rate (11/VK) [4]. Empirically, we find out that the resulting subgradient method works well and the violated case will never happen.
4.2 A New Principled Adversarial Training Procedure for Deep Learning
In this subsection, we develop inexact stochastic gradient-type methods for (3.3) and thus able to realized the benefits the proposed DRO model adversarial learning tasks. As the nonconvexity of fa(-), the inner maximization problem over A; will be longer tractable. Therefore, leverage the methodology proposed in [27] to gain the computational efficiency, that is, regarding the dual variable modeling parameter. To proceed, Assumption B] (i.c., see Assumption E. in appendix for details).
make the same smoothness assumption in [27,
Lemma 4.1 (Convex-concave minimax theorem without compactness). Suppose that RR R is
convex and level bounded and Ih + IR. is strongly convex. Then we have
min max Z DERm
f(x) + Ay - g(v)
max min f(x) x Ay g(y).
yER* ZERA

---

Leveraging Lemma 4.1 and the smoothness assumption, (3.3) leads to simple and instructive form:
N
min 9 N
max Se
[Kffo(X + +A)) A|A
(4.1)
In contrast to the vanilla DRO model studied in [27]. (4.1) further constrains the perturbation into Euclidean ball with the correlation information M. Moreover, we can observe that the magnitude of decides how many martingale constraints will be active, which also perfectly matches our theoretical results and interpretations established for linear regression, see Theorem 3.7 and Remark 3.8.
From a computational viewpoint, if À is large enough (see Lemma E.2 for details), the inner max- imization problem is strongly concave and thus the outer minimization problem over | will be smooth. This motivates Algorithm 1, an inexact stochastic gradient method for Problem (4.1). The convergence guarantee is provided in [27, Theorem 2]. It is worthwhile mentioning that the resulting new principled adversarial training is extremely easy to implement by only adding three lines of Pytorch code based on [27]. We refer the interested readers Appendix F for details.
Algorithm 1: Martingale Distributionally Robust Optimization with Adversarial Training Input: Sampling distribution P, stepsize sequence (tx [t=) for k 0, 2, K do
Sample x and find n-approximate maximizer A satisfying
A A S 7
where A
arg max (((fa((X* + +1)) - A/IA [ || ISc
Set gett t 8 to V + +1)).
Numerical Results
In this section, we validate the effectiveness our methods (referred to as martingale DRO) on both linear regression and deep neural networks under the adversarial setting. All simulations implemented using Python 3.8 on: (1) a computer running Windows 10 with a 2. 2.80GHz, Intel(R) Core(TM) i7-1 165G7 processor and 16 GB of RAM, and (2) Google Colab with NVIDIA Tesla P100 GPU and 16 GB of RAM. As for the adversarial setting, we consider three types of attack, the detailed definitions of which are collected in Appendix F.
5.1 Linear Regression
To start with, we demonstrate the effectiveness of the proposed martingale DRO model (3.5) with the quadratic loss function and linear feature mapping, i.e., {(fa(X)) = -Y - Z)² with X & (Y, z and T A (1, [,), where Z is the feature vector and Y is the target variable. In this experiment, we test our method on three LIBSVM regression real world datasets 1 More specifically, we randomly select 60% of the data train the models and the rest as our test data. To showcase the effectiveness of martingale DRO model under adversarial setting, we apply one-step projected- gradient method (PGM) attack [17] on test data and report the performance in terms of the the
root mott-mea-sson -quare error (RMSE) on adversarial test data, where RMSE & V & (3T 2012 v
and 3 is the estimator of 3. All numerical results with different step sizes for PGM attack are collected in Figure 1. As mentioned in Proposition 3.2, since the exact martinagle DRO model (i.e., e = 0) is equivalent to Tikhonov regularization, we choose the same hyperparameter = 0.08 for ridge regression and martingale DRO mode for fair comparison. We can observe that the martingale DRO can outperform other two benchmarks over three real world datasets consistently when the step size for the PGD attack is relatively large. This result also corroborates our theoretical intuition the additional regularization R(3) can further improve the adversarial robustness.
/https://www. csie. ntu, edu. http:///w/w//ttoooooossssssseeee

---

5.2 Deep Neural Network for Adversarial Training
We generate the synthetic training data {Y,, Ze) with a wide margin as follows: generate i..d. Zj ~ [(0, I2), where Z E IR,, 1z is the identity matrix in IR? set I (j 1| ll &
(v (v2/n, 2))) where 77 1.6; let Y, sign 12 22), vi I. We train neural network with 3 hidden layers of size 4, and and ELU activations between layers. We compare our approach (cf. martingale DRO) with ERM and the conventional DRO approach developed in [27]. More details
about the experiment setup are collected in Appendix F.
PRM
DRO Martingale
DEO
Markinaki unO. me
(a) Classification boundaries
(b) Data perturbation
Figure 2: Illustration of the performance comparison between competing methods. ERM tends to overfit to the inner class while DRO becomes too conservative due to unconstrained perturbation. The martingale DRO leaves bigger margins from the sample points than the other methods.
Figure 2 show the experimental results on the synthetic dataset. Test data are shown in darkgray and gray with different shapes, which are generated by the above-mentioned procedure with smaller margin (1) = 1.2). Classification boundaries are shown in blue, green, and orange for ERM, DRO, and martingale DRO respectively, as well as with the true class boundaries of the test data. Intuitively, the boundary generated by ERM is too close to the true inner boundary since the majority of points are of darkgray class, while the DRO approach pushes the classification boundary outwards. However, as illustrated in Figure 2(a), the DRO approach suffers from over-conservativenns and martingale DRO becomes entangled with the boundary of the outer gray class. In contrast, boundary lands in between the two extremes and it leaves bigger margin. Figure 2(b) explicitly shows the qualitative difference between these methods in terms of the perturbation to the data: the Martingale perturbation is constrained below e while the DRO perturbation is unconstrained. Moreover, previously shown, decreasing non-zero pushes the perturbed martingale constraints towards the exact martingale constraints and forces the classification boundary increasingly inward. More results are in Appendix F.
Then, we validate our method on the MNIST dataset [15]. For the classifier, we train a neural network equipped with 8 x 8, 6 6, 5 x 5 convolutional filter layers and ELU activations followed by a fully connected layer and softmax output. To show the robustness our method, we test the performance of four methods (ERM, DRO, Jacobian regularization [13] and martingale DRO) under the PGD and FGSM attacks (Definition F.1) with test error defined to be: classification accuracy.
In Figures 3a and 3b, our martingale DRO model outperforms the other methods and still provides robustness under the oc-norm FGSM attacks. Figure 3c, we show the performance of our model with different As expected, when is relatively small, the model is not flexible enough and shows large test error. Alternatively, as becomes large, our model will behave similarly to the original DRO model since the e-constraint is almost inactive in this case.
Figure visualizes the different levels of robustness for the four methods. For each test data point, we perturb the image using the DRO attacks (Definition F.2) with decaying level of perturbation and respectively record the first perturbed images that each model correctly classifies. Figure 4, the original label is 6 and all methods output the correct prediction, whereas in the adversarial example that the DRO model predicts 6, the correct classification seems unreasonable to human eyes (see Appendix F for more examples). This observation shows insight that the original DRO model is too conservative in predicting and our model puts more constraints on the perturbation when training thus providing model that is more consistent to human eyes.

---

PGD Attack
ERM
DRO
Jacobian Regularization
Martingale DRO
14.16%
84.02%
81.73%
85.48%
0.04
77.50%
82.87%
78.78%
83.25%
6 0.08
70.20%
80.68%
73.85%
80.86%
Table
Top-1 accuracy results with different levels of perturbation on CIFAR-IO.
Regulariaates Na tintinale DRD
DRO
DRC Martir gale DRD
Test Eveor
Text Prom
Test
1.3
10:
1.
0.0
0.2
6/4 30
28
1.5
0.
022
0.4
0.0
6.1
65
8.
Step
FCSM Attack Step Size
PGD Attack Step Size
(a) PGD Attack
(b) FGSM Attack
(c) Sensitivity to
Figure 3: Compare the proposed martingale DRO with ERM and DRO on the MNIST datasets under
PGD and FGSM attack; compare the proposed martingale DRO with different values of
Experimental setup for CIFAR-10 [14]: For the classifier, we train a ResNet with the architecture in [12]. We optimize using Adam with batch size of 128 for all methods. The learning rate starts oech from 0.01 and shrinks by 0.1 नमा and each model is trained for 100 epochs. The simulations are implemented using Python 3.8 on Google Colab with TPU v2 and 16GB RAM. Similarly, we test the performance of four methods (ERM, DRO, Jacobian regularization and martingale DRO) under the PGD attack with different levels of perturbation, the results shown in Table are consistent with those from the MNIST dataset.
6
6
(a) Original
(b) ERM
(c) Jacobian Regularization
(d) DRO
(e) Martingale DRO
Figure The largest DRO perturbation such that each model makes correct prediction.
Closing Remarks
In this paper, we find that the OT-based DRO model is equivalent to Tikhonov regularization when exact martingale constraints are imposed. Upon this interesting hidden connection, we introduce a new model called the perturbed martingale DRO model, which not only provides unified viewpoint to several common robust methods but also leads to new regularization tools. Empirically, we validate the effectiveness of our model in addressing the conservativeness issue for the conventional DRO model. From the statistical perspective, how to optimally select the size of uncertainty regions and the perturbation size of the martingale constraint, is natural problem be further explored.
Acknowledgements Material in this paper is based upon work supported by the Air Force Office of Scientific Research under award number FA9550-20-1-0397 Additional support is gratefully acknowledged from NSF grants 1915967 and 21 18199. Viet Anh Nguyen acknowledges the support from the CUHK's Improvement Competitiveness in Hiring New Faculties Funding Scheme.
10

---

References
[1] Mathias Beiglböck, Pierre Henny-Labordere, and Friedrich Penkner. Modellindeeendent bounds for option prices mass transport approach. Finance and Stochastics, 17(3):777-01, 2013,
[2] 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.
[3] Jose Blanchet, Karthyek Murthy, and Fan Zhang. Optimal transport- based distributionally robust optimization: Structural properties and iterative schemes. Mathematics of Operations Research, 2021.
[4] Stephen Boyd, Lin Xiao, and Almir Mutapcic. Subgradient methods. lecture notes of EE392o. Stanford University, Autumn Quarter, 2004:2004-2005, 2003.
[5] Ruidi Chen and Ioannis C Paschalidis. A robust learning approach for regression models based on distributionally robust optimization. Journal of Machine Learning Research, 19(13), 2018.
[6] Frank H Clarke Optimization and nonsmooth analysis. SIAM, 1990.
[7] Zac Cranko, Zhan Shi, Xinhua Zhang, Richard Nock, and Simon Kornblith. Generalised Lips- chitz regularisation equals distributional robustness. In International Conference on Machine Learning, pages
PMLR. 2021.
[8] Yan Dolinsky and H Mete Soner. Martingale optimal transport and robust hedging continuous time. Probubility Theory and Related Fields, 160(1):391-427, 2014.
[9] Chris Finlay and Adam M Oberman. Scaleable input gradient regularization for adversarial robustness. arXiv preprint arXiv: 11468, 2019.
[10] Rui Gao, Xi Chen, and Anton Kleywegt. Wasserstein distributionally robust optimization and variation regularization. arXiv preprint arXiv: 2017.
[11] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint arXiv:1412.6572, 2014.
[12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[13] Judy Hoffman, Daniel A Roberts, and Sho Yaida. Robust learning with jacobian regularization. arXiv preprint 1e0:.0278222 2019.
[14] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[15] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdbhniist/, 1998.
[16] Jiashuo Liu, Zheyan Shen, Peng Cui, Linjun Zhou, Kun Kuang, and Bo Li. Distributionally robust learning with stable adversarial training. arXiv preprint arXiv:2 15791, 2021.
[17] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 2017.
[18) Gary C McDonald. Ridge regression. Wiley Interdisciplinary Reviews: Computational Statistics, 1(1:993-100, 2009.
[19] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Mathemati- cal Programming. 171(1):115 1566 2018
[20] Hongseok Namkoong and John Duchi. Vareance-based regularization with convex objectives. Advances in Neural Information Processing Systems, 30, 2017.
11

---

[21] Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning. 11(5-6):3556677, 2019.
[22] Tyrrell Rockafellar and Roger J-B Wets. Variational Analysis, volume 317. Springer Science & Business Media, 2009.
[23] Stephan R Sain. The Nature of Statistical Learning Theory. Taylor & Francis, 1996.
[24] Soroosh Shafierzadeh-Abader Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation. Journal of Machine Learning Research, 201103)1168, 2019.
[25] Soroosh Shafieezadeh Abadeh, Peyman M Mohajerin Esfahani, and Daniel Kuhn. Distribu- tionally robust logistic regression. Advances Neural Information Processing Systems, 28, 2015.
[26] Alexander Shapiro. On duality theory of conic linear problems. In Semi-infinite programming, pages 135-165. Springer, 2001.
[27] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In International Conference Learning Representations, 2018.
[28] Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):171-176 1958.
[29] Matthew Staib and Stefanie Jegelka. Distributionally robust optimization and generalization in kernel methods. Advances in Neural Information Processing Systems, 32, 2019.
[30] Volker Strassen. The existence of probability measures with given marginals. The Annals of Mathematical Statistics, 36(2):423-43) 1965.
[31] Cédric Villani. Optimal Transport: Old and New, volume 338. Springer, 2009.
[32] Wei Emma Zhang, Quan Sheng, Ahoud Alhazmi, and Chenliang Li. Adversarial attacks on deep-learning models in natural language processing: A survey, ACM Transactions on Intelligent Systems and Technology (TIST), 11(3):1-1,, 2020.
12

---

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


Reviews:
[{"review_id": "ZU-ioDR86v5", "reviewer": "Reviewer_Wc7X", "summary": "This paper proposes  a connection between Tikhonov regularization and optimal transport map with exact martingale constraints. This finding provides an explanation and guidance to the existing regularization in DRO problem. The authors also introduced a meaningful implementation to solve the problem at hand.", "questions": "a)\tTheorem 3.7 requires a convex quadratic function and linear mapping. I think these two constraints are quite strict in the adversarial learning problem, how can you guarantee these?  Can one relax these two conditions if so how? \nb)\tIn the first experiment of section 5.2, the  intuitive explanation of the results is not very enlightening if not meaningless to reader. Is there a  statistical measure to estimate the ensuing  results?\n\n", "limitations": "The model should also be tested on a more complex dataset thereby provide  a deeper understanding on the effectiveness and improvement of the model.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The paper  appears to be theoretically sound, firstly establishing a connection between regularization and martingale constraints, thereby building a potential basis for adversarial learning.\nWeaknesses: The notation in the paper is rather  hard to track, e.g., L_\\beta, l(f_\\beta), and f_\\beta are three different things. The experiments are rather thin. It  would be more useful  to show some comparisons with existing regularization approaches. Please also see questions below\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "G6rjjqEpOA3", "reviewer": "Reviewer_rU1F", "summary": "The paper show the equivalence of Optimal Transport Distributional Robust Optimization and Tikhonov regularization under martingale constraints. Inspired by this observation, the paper further introduce some new regularization techniques, both for linear regressions and black-box models such as neural networks.  ", "questions": "1. How do you get the last equality of the proof of Proposition 3.2 in the main text? Can you explain this step clearly? The Holder's inequality provides that \n$$ (\\beta^{T} \\Delta)^2 \\leq |\\Delta|_{M}^{2}  |\\beta|_{M^{-1}}^{2}, $$ \nwith the equality occurs if $\\Delta = M^{-1} \\beta$ (up to a constants). After that, we need to construct a $\\pi$ (or a sequence of $\\pi$) to attain this equality and satisfy all the imposed constraints. Although the other longer proof in the Appendix is correct, I am still confused about this short proof in the main text. \n\n2. The fact that we can choose the cost function in OT to be adjusted by a positive definite matrix $M$ is nice. But in practice, how do we choose $M$ rather than identity matrix $I$? It would be helpful to have some sentences to explain it around line 90-93. ", "limitations": "The paper is well written and has no major limitations. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**: \n\n1. The presentation in this paper is good, all the proofs in Appendix are carefully written. \n\n2. The proposed regularization method works better than the old OT-DRO method, and the theoretical support is solid.\n\n**Weakness**: I think this is a strong paper with no major weakness. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "0OE_OLvTHwa", "reviewer": "Reviewer_qbWC", "summary": "The authors focus on the problem of distributional robust optimization, which consists in training a model, assuming the learned distribution lies in a ball around the empirical dataset (w.r.t. to some metric). They consider the Wasserstein distance as such metric, and propose to add another martingale constraint on the true distribution. It is motivated by imposing a provably higher dispersion on the learned distribution. Inspired by a previous work proving the equivalence between distributionaly robust problem in some setting and a regularized MSE minimization problem, they prove an analog result on their formulation.  The martingale constraint is penalized using a Mahalanobis norm. They propose an subgradient algorithm to estimate the model. They provide experiments on synthetic and MNIST data.", "questions": "Could you please provide an answer to the above remarks (1), (3), (4), (5) and (6) ?", "limitations": "The authors did not adress societal impact, but I think it is limited for this work.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The contributions of this work are interesting. The equivalence with a regularized MSE problem is interesting. However, I am not an expert of distributionally robust optimization, so I cannot precisely assess the novelty of the authors contributions. I provide below some remarks.\n\n1) The derivation of the duality is a bit fast in the paper. In particular I am not sure how the martingale constraint is handled. It seems that in the proof you assume the adversary distribution is discrete (similar to the empirical distribution), so that the martingale constraint can be handled, and to obtain a duality result as for Theorem 2.3. Is it indeed the case ? If so, isn't it a restriction to assume it is discrete ? The adversary distribution could have a continuous density for instance.\n\n2) There seems to be a typo at line 147.\n\n3) Concerning Proposition 3.6, I wonder how behaves this result when taking asymptotics. For instance if \\epsilon goes to infinity, we should retrieve Proposition 2.2, but it does not seem obvious to retrieve the square root of the MSE. Could you discuss why we should retrieve such result ?\n\n4) Could you provide the definition of adversarial RMSE in the main body, so that we are sure what is plotted in figure 1 ?\n\n5) At line 242 you say that \"without loss of generality\" we can assume that M=I. However I see no argument to justify it. Is it a simplification assumption, or can one prove the loss and gradients is the same for any covariance  M ?\n\n6) It would be interesting to track time in the numerical experiments. The penalty seems much more complicated, thus do the benefits of the performance outweigh the extra computation complexity of the model ?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept