{'fraction_non_alphanumeric': 0.05025891690461211, 'fraction_numerical': 0.011445579054348351, 'mean_word_length': 4.306497175141243, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tikhonov Regularization is Optimal Transport Robust under Martingale Constraints

Distributionally robust optimization 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 provides a 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 to other problems of independent interest.


Introduction
Regularization is an important tool in machine learning which is used in, for instance, reducing overfitting [23]. Recently, ideas from distributionally robust optimization (DRO) have led to a fresh viewpoint on regularization precisely in connection to overfitting; see, e.g., [7,2,20,10,29,24,25,5] and the references therein.
In these references it is shown that many standard regularization-based estimators arise as the solution of a min-max game in 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 is, the adversary perturbs the empirical distribution in a certain way. The choice of adversarial distributions or perturbations in DRO is often non-parametric thus providing reassurance that the decision is reasonably robust to a wide range of out-of-distribution perturbations. For example, one such non-parametric choice is given by employing optimal transport costs [31] to construct a 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 of 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 us to understand its out-of-distribution benefits and potentially introduce improvements.
In this paper, we introduce a 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 a way that the average size perturbation is less than a given budget. In addition to this 36th Conference on Neural Information Processing Systems (NeurIPS 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 out that two random variables X andX form a martingale in the sense that E[X|X] = X if and only if the distribution ofX dominates X in convex order [30]. In this sense, the adversaryX will have higher dispersion in non-parametric sense than the observed data X but in a suitably constrained way so that the average locations are preserved. This novel OT-DRO constrained regularization, we believe, is 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 to 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 a 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 in 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 a 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 our main contributions as 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 in this paper and is used as the main technical tool, can be applied to a wider spectrum of problems of independent interest.

Preliminaries
Let us introduce some basic definitions and concepts preparing for the subsequent analysis.
Definition 2.1 (Optimal transport costs and the Wasserstein distance [21,31]). Suppose that c(·, ·) : is a lower semi-continuous cost function such that c(X, X) = 0 for every X ∈ R d . The optimal transport cost between two distributions Q and P supported on R d is defined as E π c(X, X) : P 1 π = Q, P 2 π = P .
Here, P(X × X ) is the set of joint probability distribution π of (X, X) supported on X × X while P 1 π and P 2 π respectively refer to the marginals ofX and X under the joint distribution π.
If c(X,X) = X − X is any given norm on R d , 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, Next, we consider the conventional OT-DRO problem: , which is the worst-case expected loss under all possible distributions around the empirical measure P at most ρ with respect to the OT distance. It is well-known that under appropriate assumptions, the DRO problem (2.1) is equivalent to the regularized square-root regression problem. Proposition 2.2 ([2, Proposition 2.]). Suppose that (i) the loss function (·) is a convex quadratic function, i.e., ∇ 2 (·) = γ > 0, where γ is a constant, (ii) the feature mapping f β (X) = β X is linear, and (iii) the ground cost c is the squared Euclidean norm on X = R d . Then 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 π X ×X f (X) dπ s. t. π ∈ P(X × X ) X ×X c(X, X) dπ ≤ ρ, P 2 π = P E π [X|X] = X P-a.s.

(Primal)
and its associated dual form Here, f : X → R is upper semi-continuous and L 1 -integrable. The next theorem states the strong duality result linking these two problems.
δ Xi be the reference measure. Suppose that (i) every sample point is in the interior of the cone generated by X , i.e., X i ∈ int(cone(X )) ∀i ∈ [N ], and (ii) the ambiguity radius ρ > 0. 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 [26,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].
Notation. We use S d ++ to denote the set of d-by-d positive definite matrices and X M √ X M X for any X ∈ R d , M ∈ S d ++ ; if M is the identity matrix, then we omit M and write X √ X X. We use δ X to denote the Dirac measure at X and let P 1 N N i=1 δ Xi be the empirical measure constructed from sample {X 1 , . . . , X N }. We use E P to denote the integration over P : E P [f (X)] = X f (X)dP . Specifically, for (X, X) following joint distribution π, E π [c(X, X)] = X ×X c(X, X)dπ, E π [f (X)] = X ×X f (X)dπ. We use (·) to denote the loss function applied to the parametrized feature mapping f β . Let ∇ (·), ∇ 2 (·) be the first and second order derivative of (·) respectively. Notably, we use L β ( P, ρ) to denote the objective function of the conventional DRO model (2.1); we use L β ( P, ρ) to refer to the exact martingale DRO model (3.1); we use L β ( P, ρ, ) to refer to the perturbed martingale DRO model (3.2).

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, we can relax the equality constraint and thus allow a small violation of 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 a principled way, which improves upon Tikhonov regularization as we show in our experiments.
Assumption 3.1. The following assumptions hold throughout.
(i) The ground cost c(·, ·) is the Mahalanobis cost with the weighting matrix M ∈ S d ++ , (ii) The domain X is unconstrained, i.e., X = R d .

Optimal Transport-based DRO with Martingale Constraints
To start with, we investigate the exact martingale DRO problem: E π c(X, X) ≤ ρ, P 2 π = P E π [X|X] = X P-a.s., (3.1) and ρ ≥ 0 is the radius of uncertainty set centered at P. Note that because P 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, ρ) is referred to as the worst-case expected loss of the model parameter β under the martingale DRO model. It is easy to see that L β ( P, ρ) ≤ L β ( P, ρ), where L β is defined as in (2.1). This is because the adversary in (3.1) has a 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 (2.1).
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 (·) is a convex quadratic function, i.e., ∇ 2 (·) = γ > 0, and (ii) the feature mapping f β (X) = β X is linear. Then we have If the Mahalanobis matrix M is the identity matrix, the martingale DRO model (3.1) recovers the Tikhonov regularization problem. E π (β (X + ∆)) = sup The last equality follows from the general Hölder's inequality. To achieve the equality, we can, for example, take a normally distributed random variable C with mean 0 and variance ρ and which is independent of X, and then let ∆ = CM −1 β.
, which implies that we do not allow transport of the response Y , then the problem (3.1) with γ = 2 becomes In Appendix C.1, 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 (·) is µ-strongly convex and C-smooth, that is, 2 hold for all θ, θ ∈ R, and (ii) the feature mapping f β (X) = β X is linear. Then we have for any ρ ≥ 0,

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): The parameter controls the allowed violations of the martingale constraint for the adversary. It is trivial that if we set = 0, then we obtain L β ( P, ρ, 0) = L β ( P, ρ) and we recover the exact martingale DRO model (3.1). If we set = +∞ then the martingale constraint becomes ineffective, thus we have L β ( P, ρ, +∞) = L β ( P, ρ) and model (3.2) collapses to the DRO formulation (2.1).
We thus can think of as an interpolating parameter connecting two extremes: the conventional DRO model (2.1) (at = +∞) and the exact martingale DRO model (3.1) (at = 0).
However, the resulting optimization problem (3.2) constitutes an infinite-dimensional optimization problem over probability distributions and thus appears to be computationally intractable. To overcome this issue, we leverage Theorem 2.3 and prove that the problem (3.2) is actually equivalent to a finite-dimensional problem. To begin with, we present one crucial proposition that can be applied to more general settings.
Theorem 3.6 (General loss functions and feature mappings). Suppose that the loss function (·) and the feature mapping f β (·) are upper semi-continuous. Then, for any ρ > 0 and > 0, the perturbed martingale DRO model (3.2) admits Sketch of proof. The key step is to decouple (3.2) as a two-layer optimization problem: 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 η. 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 α ∈ R N ×d in (3.3) can be reduced to N parallel onedimensional 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 (·) is a convex quadratic function, i.e., ∇ 2 (·) = γ > 0 and (ii) the feature mapping f β (X) = β X is linear. Then, the perturbed martingale DRO model (3.2) admits: where the additional regularizer is defined as Obviously, compared with the exact martingale constraint investigated in Proposition 3.2, the perturbed constraint we consider here involves an additional term R(β). Fortunately, armed with Lemma D.3, we are able to shed light on its intuitive interpretation based on the quantitative relationship between modeling parameters and ρ. First, we discuss two extreme cases -there are interesting hidden connections between (3.2) and other existing regularization techniques. Remark 3.8. Intuitively, if is relatively small, the optimal s is zero which means that all perturbed martingale constraints will be active. Precisely, if 2 ≤ ρ, the additional regularization term satisfies , which is 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, if ρ is relatively small, the optimal s is equal to G β , implying that none of perturbed martingale constraints is active. In fact, if 2 ≥ N ρ, we . Then, we can easily figure out that L β ( P, ρ, ) can be reduced to the conventional OT-based DRO model in Proposition 2.2.
Then for the middle case, it is natural to infer that only part of constraints will be active. In Lemma D.3, we justify this conjecture rigorously. We refer the reader to 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 a 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.

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 a 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.

Subgradient Method for Linear Regression
Unfortunately, the resulting formulation we conducted in Theorem 3.7 (i.e., (3.5)) for linear regression is potentially intractable for optimizing (β, s) jointly. One obvious computational challenge here is that the overall problem is not necessarily convex in (β, s), even if the original problem is convex over β. This is because the minima of convex functions is not convex. However, under a 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 L β ( P, ρ, ) is convex over β. This is essentially from the fact that the pointwise supremum of a class of convex functions is still convex. To check the details, 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(β) 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 L β ( P, ρ, ) due to the weakly convexity. We have The remaining question is how to compute the Clarke subdifferential of R(β). When 2 ≤ ρ and 2 ≥ N ρ, R(β) will enjoy the convex composite structure. Thus, we can get the correct subgradient by invoking the chain rule developed in [22,Theorem 10.6] directly. The more subtle and tricky case is the middle one -ρ < 2 < N ρ. Without of loss generality, we assume that M = I for simplicity. Based on [6, Theorem 2.3.9], we have where S(β) 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 O(1/ √ K) [4]. Empirically, we find out that the resulting subgradient method works well and the violated case will never happen.

A New Principled Adversarial Training Procedure for Deep Learning
In this subsection, we develop inexact stochastic gradient-type methods for (3.3) and thus are able to realized the benefits of the proposed DRO model in adversarial learning tasks. As the nonconvexity of f β (·), the inner maximization problem over ∆ i will be no longer tractable. Therefore, we leverage the methodology proposed in [27] to gain the computational efficiency, that is, regarding the dual variable as a modeling parameter. To proceed, we make the same smoothness assumption in [27, Assumption B] (i.e., see Assumption E.1 in appendix for details). Lemma 4.1 (Convex-concave minimax theorem without compactness). Suppose that f : R n → R is convex and level bounded and g : R m → R is strongly convex. Then we have Leveraging Lemma 4.1 and the smoothness assumption, (3.3) leads to a simple and instructive form: In contrast to the vanilla DRO model studied in [27], (4.1) further constrains the perturbation into a 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 maximization 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 to Appendix F for details.

Numerical Results
In this section, we validate the effectiveness of our methods (referred to as martingale DRO) on both linear regression and deep neural networks under the adversarial setting. All simulations are implemented using Python 3.8 on: (1) a computer running Windows 10 with a 2.80GHz, Intel(R) Core(TM) i7-1165G7 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.

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., (f β (X)) = 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 to 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 projectedgradient method (PGM) attack [17] on test data and report the performance in terms of the the root-mean-square error (RMSE) on adversarial test data, where RMSE andβ is the estimator of β. All numerical results with different step sizes for PGM attack are collected in Figure 1. As we mentioned in Proposition 3.2, since the exact martinagle DRO model (i.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(β) can further improve the adversarial robustness.

Deep Neural Network for Adversarial Training
We generate the synthetic training data {(Y i , Z i )} i∈I with a wide margin as follows: generate , ∀i ∈ I. We train a neural network with 3 hidden layers of size 4, 3 and 2 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.  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 a smaller margin (η = 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-conservativeness and becomes entangled with the boundary of the outer gray class. In contrast, our martingale DRO boundary lands in between the two extremes and it leaves bigger margin. Figure 2(b) explicitly shows the qualitative difference between these two methods in terms of the perturbation to the data: the Martingale perturbation is constrained below 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 × 8, 6 × 6, 5 × 5 convolutional filter layers and ELU activations followed by a fully connected layer and softmax output. To show the robustness of 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: 1 − classification accuracy.
In Figures 3a and 3b, our martingale DRO model outperforms the other methods and still provides robustness under the ∞-norm FGSM attacks. In 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 -constraint is almost inactive in this case. Figure 4 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. In 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 an insight that the original DRO model is too conservative in predicting and our model puts more constraints on the perturbation when training thus providing a model that is more consistent to human eyes.

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 a 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 a natural problem to be further explored.

Broader impact
This work does not present any foreseeable societal consequence. While our contribution has a theoretical orientation, we believe that the structure of our method holds significant promise in the adversarial learning and robust optimization as we mentioned in the body context.

A Organization of the Appendix
We organize the appendix as follows: • The proof details of Theorem 2.3 (cf. Strong Duality Result) is given in Section B.
• We collect all proof details of tractable reformulation results in Section C, including Proposition 3.2, Theorem 3.6 and Theorem 3.7.
• All useful technical lemmas are summarized in D.
• Convergence analysis of optimization algorithms are provided in Section E.
• Supplementary materials of numerical results are included in Section F.

B Strong Duality Result
To obtain the tractable reformulation result, we start to prove the strong duality theorem for a general class of martingale constraints-based Wasserstein DRO optimization problems (i.e., in the main context, we just provide the simplified version for simplicity): Here, • f : X → R is assumed to be upper semi-continuous and µ-integrable i.e., f ∈ L 1 (µ).
• P(X ) denotes the set of all Borel probability measures supported on X .
• The cost function c : X × X → [0, ∞] is a lower semicontinuous function satisfying c(X, X) = 0 for every X ∈ X .
• For simplicity, let the reference measure be the empirical distribution P = 1 •X is the perturbed discrete distribution based on the empirical distribution P supported on The Lagrangian dual problem is derived as Theorem B.1 (Restate Theorem 2.3 in a more general fashion). Suppose that (i) the reference measure P is the empirical distribution, i.e., P = 1 N i∈[N ] δ Xi , (ii)X follows from the perturbed empirical distribution, i.e.,P = 1 N i∈[N ] δ Xi+ηi satisfying X i + η i ∈ int(cone(X )) ∀i ∈ [N ], and (iii) the ambiguity radius satisfies ρ > 0. Then strong duality holds, i.e., Val(P rimal) = Val(Dual).
Proof of Theorem B.1. Since Q = P 1 π a change of variables allows us to rewrite the objective function as Then, as the reference measure P = 1 N N i=1 δ Xi , we can recast the marginal constraint P 2 π = P as X ×X where I S is the indicator function of the set S. Similarly, we can also reformulate the martingale constraint via further exploiting the discrete structure of the reference measure P: Thus, we have where X i + η i ∈ X . If we make the normalization of π explicit, we obtain the following equivalent reformulation of Problem (Primal): sup Here, M + (X × X) is the set of all non-negative Borel measures supported on X × X and the first integral constraint ensures that π is a probability measure. As M + (X × X) is a convex cone and all of constraints regarding π are linear, problem (B.1) can be fitted into the standard primal problem in [26, (3.2)]. That is, min and A is the linear mapping defined through the left hand side of the constraints in (B.1): Next, we aim at invoking Proposition 3.4 in [26] to prove the strong duality. A sufficient condition is the generalized Slater condition, see (3.12) in [26]. That is, we have to check b ∈ int[A(M + (X × X)) − K], (B.3) where int(·) is the interior of a set. As such, where F : M + (X × X) → R d satisfying F (π) = X ×X I Xi (X) ·Xdπ. Then, To check the Slater condition, we validate each constraint separately.
, for all i ∈ [N ]; • As X i + η i ∈ int(cone(X )), ∀i ∈ [N ] and Lemma D.1 holds (i.e., cone(X ) ⊆ Range(F ), Then, we obtained the desirable result. At last, we derive the dual problem by the standard Lagrangian method following [26], Due to the strong duality result, we have L(π; λ, s, α).

(B.4)
We complete the proof.

(C.1)
Because P is the empirical measure and because any feasible measure π satisfy the constraint P 2 π = P, the integral in the last two constraints of (C.1) is restricted to X × X (instead of X × X ) without any loss of optimality.
The trivial case ρ = 0 is easy to verify. To begin with, we focus on the case where ρ > 0. Here, we want to invoke the strong result, i.e., Theorem 2.3. Before getting into details, we check the conditions at first. (·) is quadratic and thus upper semi-continuous; X = R d can help us to get rid of the mild regularity condition, that is, X i ∈ int(R d ) automatically holds. Then, we get By a change of the variables, i.e., Thus, the crux is the inner maximization problem. To proceed, we exhaust all possible cases. When λ < β 2 M −1 γ/2, it is easy to check that the inner maximization problem will go to +∞ due to the general Cauchy-Schwarz inequality for the normed space M −1 γ/2 and α i = ∇ (β X i )β, the inner maximization problem will also go to +∞. As such, we have At last, we focus on the left case and further prove the above inequality is the equality. If λ > β 2 M −1 γ/2, we have The desirable result is obtained, that is, This completes the proof.
C.2 Proof of Theorem 3.6 and Theorem 3.7 Proof of Theorem 3.6. To start with, we recast problem (3.2) into a two-layer optimization problem: sup π X (f β (X))dQ s.t Q ∈ P(X ), π ∈ P(X × X ), where X = {X 1 , X 2 , · · · , X N }. Then, we apply Theorem 2.3 (i.e., strong duality) to the inner maximization problem, i.e., The second equality follows by settingX i = X i + ∆ i . As 0 < < +∞ and M is a positive definite matrix, the set {(η 1 , . . . , η N ) : η i M ≤ ∀i ∈ [N ]} is a compact set. Consider the following mapping It is easy to see that this mapping is linear, and thus concave, in η. Moreover, it is convex in (λ, α) as the pointwise supremum of a class of convex functions (i.e., the inner function over (λ, α) is linear) is always convex. From Sion's minimax theorem [28], we can interchange the outer supremum and infimum operators to obtain For any feasible value of (λ, α), the optimal solution in η i is either We thus have We complete the proof.
Proof of Theorem 3.7. Taking (f β (X)) = (β X) with the second derivative of ∇ 2 (·) = γ in (3.3), we have Similar with the argument to proof Proposition 3.2 in the appendix, see section ?? for details, we can conclude that 0 ≤ λ ≤ γ 2 β 2 M −1 . As such, we analyze two cases separately. Case 1: suppose that the optimal value of λ = γ 2 β 2 M −1 . As we discussed the exact martingale DRO mode in the last subsection , we have α i = ∇ (β X i )β and Case 2: suppose that the optimal value of λ > γ 2 β 2 M −1 . For any fixed i = 1, . . . , N . Define As λ > γ 2 β 2 M −1 , the inner maximization with respect to ∆ i is strongly convex. Consequently, it is necessary and sufficient to study its first-order optimality condition: Then, we obtain the optimal solution and the optimal value, where the matrix inversion is valid as λ > γ 2 β 2 M −1 and For simplicity, let us ignore the empirical loss at first, which is the constant w.r.t. the dual variables λ and α.
The resulting structure of (λ, α) is still quite complicated. To further characterize the structure of the optimal solution, we utilize the parallel structure of α and focus on the corresponding subproblem as follow: By the Sherman-Morrison Formula (i.e., see Fact D.2), we have .
Here, the optimal solution θ is Consequently, we have By applying Lemma D.3, we have when ≤ √ ρ. Then, combining these two cases, we can obtain, We complete the proof.

D Useful Technical Lemmas
For any x ∈ cone(A), then there exists where δ xi are Dirac's delta measure at x i . Then µ ∈ M + (A), and which leads to the postulated claim.
Fact D.2 (Sherman-Morrison Formula). Suppose A ∈ R n×n is an invertible square matrix and u, v ∈ R n are column vectors. Then A + uv is invertible if and only if 1 + v A −1 u = 0. In this case, Here, uv is the outer product of two vectors u and v. Lemma D.3. Suppose that y ∈ R d satisfying |y 1 | ≤ |y 2 | ≤ · · · ≤ |y d | and ϑ > 0. Then, there exist 1 < j < d and α > 0 such that the problem admits the following optimal solution

(D.2)
Proof of Lemma D.3. The basic strategy here is to check the first-order optimality condition.
• The most complicated case is the middle one, i.e., y 2 y ∞ < ϑ < √ d. Here, we are trying to characterize the structure of the optimal solution. Without of loss generality, we assume that y = sort(y, abs ), i.e., sorted by its absolute value. Still, we focus on its first-order optimality condition: as x cannot equal to y derived from the condition y 2 y ∞ < ϑ < √ d. Furthermore, the optimal solution x shares the same sign of y and |x i | ≤ |y i |, ∀i ∈ [d], otherwise you can always decrease the objective value by changing the sign. Next, we will argue that the optimal solution admits x * i = 0 for some index i. We prove it by contradiction. If we assume x * = 0, there exists a constant α > 0 such that Then, the first-order optimality condition will not hold, i.e., sign(y) + ϑ α sign(y) α sign(y) 2 = 0, as ϑ < √ d. As such, there exist 1 < j < d and a constant α > 0 such that x * = [0 1:j , y j+1:d − α sign(y j+1:d )].

E Convergence Analysis of Optimization Algorithms
Denote (f β (X)) = h(β, X) and we make the following blanket assumption: Assumption E.1. The loss function h : Ω × X → R satisfies the Lipschitzian smoothness conditions where Ω ⊂ R d is a closed convex set.
Derivation of (4.1) where equality (a) follows from the following minimax theorem as the inner maximization over ∆ i is strongly concave and α i M −1 is level bounded.
Proof of Lemma 4.1. By invoking the general best-case primal-dual relations given in [22,Corollary 11.40 (d)], the key ingredient is to check the boundedness of and y ∈ R m : y = arg max .
For the purpose of this proof, we use f * to denote the convex conjugate of f , formally defined as . Similarly, g * is the conjugate of g. We have: • As f (x) is level-bounded, max y f (x) + x Ay − g(y) = f (x) + g * (A x) is also level bounded.
Compared with Lemma 1 in [27], our proof here is simpler as we utilize the compactness condition. .

F Supplementary Experiments
First we introduce the attack methods we use in the experiments of adversarial training. Definition F.1 (PGD/FGSM attack). For any model parameter β, let ∆z i (β) arg max where ξ is the attack step size, α is a pre-specified hyperparameter and Π denotes the projection onto B ξ,p (z i ) {z : z − z i p ≤ ξ}. When p = ∞, the attack is reduced to the Fast Gradient Sign Method (FGSM) [11]. As in [27], we also consider the Euclidean case p = 2, which is a general version of Projected Gradient Descent (PGD) [17] with one step.
Definition F.2 (DRO attack). For any parameter β, let where γ is is a pre-specified hyperparameter.
As for the setup of the experiments on the synthetic data (i.e., Figure 2), we use λ = 2 for both the DRO approach and our approach. Further in our approach, we use a sequence of ∈ {0.2, 0.22, . . . , 1.5} to demonstrate the effectiveness of our approach for being less conservative then the conventional DRO approach. Full results are shown in Figure 5.
As for the setup of the experiments on the MNIST dataset (Figures 3, 4), E P X 2 = 9.21 and we choose λ = 0.04E P X 2 for training the original DRO and Martingale DRO model. Additionally, we choose = 1.2 in our model, which is smaller than the average L 2 norm of the perturbations suggested by the original DRO model when training on the MNIST dataset. As for the DRO attack, we choose an increasing sequence of γ (corresponding to a decaying sequence of perturbation) and collect the images after the largest perturbation so that these methods can classify correctly. Full results are shown in Figures 6, 7.
All the hyperparameters conducted in this section have been fine-tuned via grid search for optimal performance.
In the following, we want to highlight that our method can be applied within three lines of PyTorch code modification based on the original DRO approach, which is due to the formulation (4.1). The interested reader is referred to our code to see the details.