arXiv CSopen access

Duality for the Adversarial Total Variation

Duality for the Adversarial Total Variation

arXiv:2604.18540v1 [math.AP] 20 Apr 2026

Leon Bungert and Lucas Schmitt Institute of Mathematics, Center for Artificial Intelligence and Data Science (CAIDAS), University of Würzburg, Emil-Fischer-Str. 40, 97074 Würzburg, Germany, Email: {leon.bungert, lucas.schmitt}@uni-wuerzburg.de April 21, 2026 Abstract Adversarial training of binary classifiers can be reformulated as regularized risk minimization involving a nonlocal total variation. Building on this perspective, we establish a characterization of the subdifferential of this total variation using duality techniques. To achieve this, we derive a dual representation of the nonlocal total variation and a related integration of parts formula, involving a nonlocal gradient and divergence. We provide such duality statements both in the space of continuous functions vanishing at infinity on proper metric spaces and for the space of essentially bounded functions on Euclidean domains. Furthermore, under some additional conditions we provide characterizations of the subdifferential in these settings. Keywords: adversarial training, regularization, total variation, duality, subdifferential AMS subject classifications: 28A75, 49J45, 49N15, 49Q20, 68T05

Contents 1 Introduction 1.1 Preliminaries from Convex Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Main Results and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 4 5 6

2 Dualization for C0 (X ) 2.1 Dual Reformulation for Continuous Functions . . . . . . . . . . . . . . . . . . . . . 2.2 Nonlocal Gradient and Divergence . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Integral Characterization of the Subdifferential . . . . . . . . . . . . . . . . . . . .

6 7 12 15

3 Dualization for L∞ (Ω) 3.1 Dualisation of Essential Supremum and Infimum . . . . . . . . . . . . . . . . . . . 3.2 Dual Reformulation for Essentially Bounded Functions . . . . . . . . . . . . . . . . 3.3 Nonlocal Gradient and Divergence . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Limit Characterization of the Subdifferential . . . . . . . . . . . . . . . . . . . . .

20 21 21 29 33

4 Conclusions

34

A Adapted Measurable Maximum Theorem

37

1

1

Introduction

In recent years, machine learning algorithms and, in particular, deep neural networks have enjoyed unprecedented success; however, since more than a decade ago it is known that they are also susceptible to adversarial attacks [21], which are small carefully chosen perturbations of the input that lead to severe misclassifications. While this was initially a major concern for image classification applications in safety-critical domains, more recently, in [11] it was shown that adversarial attacks can also be crafted for LLMs. One prominent approach to improve robustness is adversarial training, proposed in [18] building on earlier ideas from [20]. The key idea is to replace the standard training risk by the risk evaluated on adversarial attacks, thereby simulating the presence of an adversary already during training. Mathematically speaking, the resulting method is a robust optimization problem of the form " # inf E(x,y)∼µ

u∈H

sup ℓ(u(x̃), y) ,

(1.1)

x̃∈Bε (x)

where µ ∈ P(X × Y) is a probability measure defined on the cartesian product of the feature space X and the label space Y, modeling the distribution of training data. The hypothesis class H may be any family of measurable functions from X to Y appropriate for the specific task. The value of ε ≥ 0 is called the adversarial budget and indicates how “strong” the adversarial attacks are allowed to be. Depending on the specific machine learning task that is considered, one chooses an appropriate loss function ℓ : Y × Y → R. With these ingredients at hand, the rationale behind (1.1) is to enforce that for any training example (x, y) ∼ µ, an optimal hypothesis satisfies u(x̃) ≈ y for all x̃ ∈ Bε (x) and is thereby robust for perturbations of size at most ε. In contrast, the mathematical understanding of (1.1) is highly non-trivial, as we will explain in the following: Proving existence is difficult due to the presence of the supremum in the objective function. For non-parametric binary classification, where Y = {0, 1}, H is a class of measurable functions and ℓ(y1 , y2 ) = |y1 − y2 | is the 0-1-loss, the existence of solutions is shown in [13] and [8]. The generalization to multiclass classification is treated in [6] and the case of general loss functions was treated in [3]. Uniqueness of solutions can not be expected in general but regular solutions can be constructed for positive ε, see [8]. The asympotics of (1.1) for the adversarial budget ε tending to zero were studied using Gamma-convergence in [5], relations to mean curvature flow were established in [4, 12], optimal transport perspectives on adversarial training can be found in [7, 10], and an overview of recent developments on this topic is given in [9]. With respect to adversarial attacks, i.e., maximizers of supx̃∈Bε (x) ℓ(u(x̃), y) we would like to point to [2] where the authors connect the project gradient ascent methods typically used for approximating adversarial attacks numerically to metric gradient flows. Note that also the algorithmic minimization of (1.1) is challenging since the presence of the supremum destroys differentiability of the objective. This fact is largely ignored by the machine learning community since the advent of automatic differentiation allows one to apply gradient-based optimizers to basically any function. By the classical Danskin theorem, however, this only makes sense if the supremum in (1.1) is attained at a unique point in the closure of Bε (x); an assumption that is too strong for most real life situations. In this paper we make a first step towards a rigorous treatment of this optimization problem by using duality and techniques from non-smooth convex analysis. We build on the key insight from [8] which, in the binary classification setting, connects adversarial training to a regularization problem of the form   inf E(x,y)∼µ ℓ(u(x), y) + λR(u), u∈H

where R is the regularization functional and λ > 0 a parameter that controls the strength of regularization. In classical linear parametric learning settings the connection between adversarial 2

training and regularization has been explored, for example, in [14, 17]. The regularization interpretation identified in [8] features a nonlocal notion of length of the decision boundary. Their precise result states that in the non-parametric binary setting minimizers of (1.1) exist and can be constructed from those of the convex optimization problem   E(x,y)∼µ |u(x) − y| + ε ν- TVε (u) (1.2) inf ∞ u∈L (X ;ν) 0≤u≤1, ν-a.e.

where ν is a reference measure that dominates the class-conditional data distributions and is supported on an ε-neighborhood around their support. The nonlocal adversarial total variation is given by Z Z ν- ess supBε (x) u − u(x) u(x) − ν- ess inf Bε (x) u dϱ0 (x) + dϱ1 (x), (1.3) ν- TVε (u) := ε ε X X where ϱi := µ( · × {i}) for i ∈ {0, 1} are the (un-normalized) class-conditional distributions of the points with label i. Until now, several properties of this functional has been examined in [4, 5, 8], see also [3, 6] for the multi-class case. In particular, in [5] it was shown that if X = Ω ⊂ RN is an open subset of RN the nonlocal total variation Gamma-converges to an anisotropic local total variation of the form   Z Du u 7→ β x, (x) d |Du| (x), u ∈ BV (Ω), |Du| Ω where the weight function β : Ω × SN −1 → R reduces to β(x, ν) = ϱ0 (x) + ϱ1 (x) if the classconditional distributions ϱ0 , ϱ1 possess a continuous density with respect to the Lebesgue measure. Here BV (Ω) is the space of functions of bounded variation on Ω, referring to all functions u ∈ L1 (Ω) such that the distributional gradient of u is a finite vector-valued Radon measure Du, see the monograph [31] for precise definitions and properties. Among other properties, like the coarea formula and positive homogeneity of ν- TVε , this Gamma-convergence justifies the nomenclature R “total variation”. Note that a local total variation of the form Ω ϱ(x) d |Du| (x) for sufficiently regular ϱ can be dualized as follows [31]:  Z  Z ∞ N ϱ(x) d |Du| (x) = sup − u(x) div (ϱ(x)φ(x)) dx : φ ∈ Cc (Ω; R ), |φ(x)| ≤ 1 ∀x ∈ Ω . Ω

Ω

In this and other similar dualization formulas we refer to the set of functions over which the supremum is taken as the set of test functions, which in this case is the set of compactly supported smooth vector fields on RN . Using standard statements from convex analysis (cf. [15, 19]) one can use this dualization to show that the subdifferential of the functional at some u ∈ Lp (Ω) ∩ BV (Ω) is given by all functions u∗ in the closure of the set  div (ϱφ) : φ ∈ Cc∞ (Ω; RN ), |φ(x)| ≤ 1 ∀x ∈ Ω in Lq (Ω) with p1 + 1q = 1 which satisfy Z

u∗ (x)u(x) dx =

Z

Ω

ϱ(x) d |Du| (x). Ω

Using the theory of Anzellotti pairings [36], it can further be shown that any subgradient can be written as u∗ = − div (ϱφ) where φ is an essentially bounded vector field that, in a suitable generalized sense, possesses a divergence and is parallel to the distributional gradient Du of u, see 3

[19] for all details. This subdifferential characterization has many applications, most notably, it is at the heart of the solution concept of the total variation flow, see [29, 30]. Another important application of the dualization formula for the total variation lies in numerical optimization. For instance, the seminal Rudin–Osher–Fatemi (ROF) model consists of the minimization of Z Z 1 2 |u − f | dx + λ d |Du| , L2 (Ω) ∋ u 7→ 2 Ω Ω where f ∈ L2 (Ω) is a given R noisy image that needs to be denoised and λ > 0 is a regularization parameter. Here, we set Ω d |Du| = ∞ for u ∈ L2 (Ω) \ BV (Ω). The optimality conditions for this optimization problem are given by u − f + λu∗ = 0 where u∗ ∈ L2 (Ω) is a subgradient of the total variation at u, i.e., p = − div φ for a suitable vector field φ. This optimality condition together with the subdifferential characterization was used in [28] to derive a seminal algorithm for approximating minimizers of the image denoising problem above and similar related problems in a provably convergent way. Later the famous primal-dual algorithm was devised in [22] which applies the dualization more directly to derive a non-smooth optimization algorithm. For example, we can reformulate the ROF model as the saddle-point problem Z Z 1 2 |u − f | dx − λ u div φ dx. inf sup u∈L2 (Ω) φ∈C ∞ (Ω;RN ) 2 Ω Ω c

|φ(x)|≤1 ∀x∈Ω

Note that—once discretized to a finite dimensional problem—the minimization problem in u is smooth and convex whereas the maximization problem in φ is smooth and concave with a convex and closed constraint set of test functions. Hence, one can apply projected gradient methods to both variables and obtain the primal-dual algorithm from [22]. It should be noted that the very same ideas can be applied to adversarial training problem in (1.2) (where the non-smoothness of the loss function does not pose a problem and can be ignored for the time being) once the adversarial total variation ν- TV is dualized.

1.1

Preliminaries from Convex Analysis

We briefly review some basics from convex analysis, which shall appear frequently in this paper. If X is a Banach space with continuous dual X ∗ , and f : X → (−∞, ∞] is convex, we define its subdifferential at x ∈ X as ∂f (x) = {x∗ ∈ X ∗ : f (x) + ⟨x∗ , y − x⟩X ∗ ×X ≤ f (y)

∀y ∈ X},

where ⟨·, ·⟩X ∗ ×X denotes the dual pairing of X ∗ and X. The elements of ∂f (x) are called subgradients of f . Furthermore, we define the convex conjugate f ∗ : X ∗ → R of f via f ∗ (x∗ ) := sup ⟨x∗ , x⟩X ∗ ×X − f (x),

x∗ ∈ X ∗ ,

x∈X

which is a convex and lower semicontinuous function. The two notions are connected through the Fenchel–Young inequality, see [32, Proposition 5.1]: ⟨x∗ , x⟩X ∗ ×X ≤ f (x) + f ∗ (x∗ ) with equality if and only if x∗ ∈ ∂f (x). The subdifferential ∂f (x) is convex and weakly-* closed. Furthermore, using the canonical embedding X ,→ X ∗∗ := (X ∗ )∗ the biconjugate f ∗∗ := (f ∗ )∗ satisfies f ∗∗ |X ≤ f with equality if and only if f is convex and lower semicontinuous. 4

1.2

Main Results and Discussion

The purpose of this paper is to derive dualization formulas, similar to the one for the classical total variation, for the adversarial total variation in two different scenarios: 1. First, we let the base space be C0 (X ), the space of continuous functions on a proper metric space X vanishing at infinity. In this case, the subdifferential will lie in the dual space of that space which is the space of finite signed Radon measures on X . In this setting the reference measure ν has no bearing and it holds for all u ∈ C0 (X ) that maxBε (x) u − u(x)

Z ν- TV(u) = TV(u) := X

ε

Z dϱ0 (x) +

u(x) − minBε (x) u

X

ε

dϱ1 (x),

where Bε (x) is the closed ball around x ∈ X . Furthermore, the total variation can be dualized as follows  Z  ϱ u d divε [m] . TVε (u) = max − m∈M×M

X

Here, ϱ := (ϱ0 , ϱ1 ) is the collection of the two class-conditional distributions, divϱε [m] is a finite signed measure, and divϱε is a suitable notion of nonlocal weighted divergence that is dual to the nonlocal gradient gradε [u](x, y) := u(y)−u(x) . The set of test “functions” is a set ε of random walks M, i.e., a family of probability measures m = {mx : x ∈ Ω} satisfying supp mx ⊂ Bε (x) as well as certain measurability conditions. Subgradients are the nonlocal divergences of random walks which attain the maximum above. These results are phrased in the language of metric random walk spaces and should be compared to the seemingly similar but fundamentally different setting in [16]. See Theorem 2 and Proposition 2.18 for the rigorous statements. 2. Second, we consider L∞ (Ω) as base space where Ω ⊂ RN is an open subset of RN and the class-conditional distributions have densities with respect to the Lebesgue measure. The reason for considering this setting, as well, is that minimizers of (1.2) naturally lie in L∞ (Ω), as proved in [8]. Choosing the reference measure ν as the N -dimensional Lebesgue measure on Ω we have Z Z ess supBε (x)∩Ω u − u(x) u(x) − ess inf Bε (x)∩Ω u ν- TVε (u) = ϱ0 (x) dx + ϱ1 (x) dx ε ε Ω Ω  Z  = sup − u divε [Ψ; ϱ] dx . Ψ∈P×P

Ω

While being structurally very similar to the previous dualization result, it is important to notice that here the test functions lie in P × P where P is a suitable subset of L1 (Ω × Ω) and also divε [Ψ; ϱ] is a L1 -function. For notational convenience we define the antisymmetric pairing [Ψ; ϱ] := Ψ0 ϱ0 − Ψ1 ϱ1 . Hence, the set of test functions is significantly smaller. However, unlike in the first case, where the maximizing random walk is always attained thanks to the compactness implied by Prokohov’s theorem, here, due to a lack of compactness of this set of nonlocal divergences, the supremum is usually not attained. The supremum is attained in the weak-* closure of this set in the dual space of L∞ (Ω) which is the space of bounded and finitely additive measures that are absolutely continuous with respect to the Lebesgue measure [35]. See Theorem 4 for the rigorous statement.

5

We would like to remark that the two settings we consider in this paper are complementary to each other. For the base space C0 (X ), which is separable for proper X , the subdifferential lies in the nice space of signed measures and subgradients can be explicitly characterized as nonlocal divergences of random walks that attain the maximum in the dualization formula. In contrast, for the larger space L∞ (Ω) which is not separable subgradients cannot be characterized explicitly. However, in this case the dualization is taken over the nice set of L1 -functions on Ω × Ω instead of just random walks. Proving this requires us to use the Euclidean structure to establish certain joint measurability statements. It should also be noted that for the first setting we can resort to the standard form of the measurable maximum theorem to perform the dualization while in the second setting, due to the lack of compactness, we have to generalize this theorem, see Section A in the appendix.

1.3

Outline

The rest of the paper is organized as follows. In Section 2 we derive a duality formulation of the adversarial total variation defined on the set of continuous functions vanishing at infinity, which subsequently leads to a characterization of its subdifferential. In Section 2.1 we first obtain dual representations of the maximum and minimum of a continuous function on ε-balls around each data point and unify them into random walks on the whole domain via the measurable maximum theorem. Based on this reformulation, Section 2.2 introduces a dualization involving a nonlocal gradient and divergence. Finally, in Section 2.3 we characterize the subdifferential of TVε in terms of nonlocal divergence measures arising from this construction. Section 3 is devoted to the duality formulation of the adversarial total variation defined on essentially bounded functions. In Section 3.1 we establish a dual representation of the essential supremum and infimum in a general measure space setting. We then restrict ourselves to essentially bounded functions on RN in Section 3.2 and derive an analogous duality formulation to that of Section 2.1, again involving nonlocal gradient and divergence operators. We also show the consistency of these nonlocal operators with their classical local counterparts in Section 3.3. Lastly, in Section 3.4 we provide a limit characterization of subgradients of the adversarial total variation in this setting. Finally, we conclude the paper in Section 4 with a brief discussion of possible directions for future research. Section A in the appendix provides a complete proof of the adapted measurable maximum theorem for closed-valued correspondences, which is used in Section 3.2.

2

Dualization for C0 (X )

In this section we rewrite the nonlocal total variation functional in a duality formulation, using C0 (X ) for a proper metric space as base space. In Section 2.1 we show that the set of test functions is given by random walks on metric spaces with additional support conditions, and in Section 2.2 we define a nonlocal gradient and divergence such that an integration-by-parts identity holds for the dual formulation of TVε . Finally, in Section 2.3 we characterize the subgradients in ∂ TVε (u) using the structure induced by the dual reformulation of the functional. Throughout this section we consider a continuous function u ∈ C(X ) on a metric space (X , d), which is assumed to be proper unless stated otherwise. A metric space X is called proper if every closed and bounded subset K ⊂ X is compact, for instance X = Ω ⊂ RN . In particular, every proper metric space is Polish and locally compact. Furthermore, C0 (X ) refers to the subspace of functions in C(X ) which vanish at infinity. For compact X it holds C(X ) = C0 (X ). In the following we assume that the reference measure ν satisfies the assumptions imposed in [8]. In particular, ν is a σ-finite measure on X that is locally doubling such that ϱ0 , ϱ1 ≪ ν and 6

the following support condition holds {x ∈ X : dist(x, supp ϱ0 ) ≤ ε} ∪ {x ∈ X : dist(x, supp ϱ1 ) ≤ ε} ⊆ supp ν. Under these assumptions, ν- TVε is independent of the particular choice of the reference measure, and we therefore omit its explicit dependence in the notation. To see this, note that we have ν- ess supBε (x) u = maxBε (x) u for ϱ0 -a.e. x ∈ X and ν- ess inf Bε (x) u = minBε (x) u for ϱ1 -a.e. x ∈ X since Bε (x) ⊂ X is compact and ν is supported on the whole ball Bε (x). Hence, in the whole of Section 2 we denote TVε := ν- TVε where ν- TVε was defined in (1.3).

2.1

Dual Reformulation for Continuous Functions

To obtain a duality formulation, we first derive a dual representation of the maximum and minimum for each data point, which is achieved by testing with probability measures. We then extract a measurable selector that defines a random walk on X , i.e., a BX -measurable map from X to the set of probability measures on X , where BX denotes the Borel σ-algebra on X . We show that maximizing (respectively minimizing) over such random walks yields the desired result. In this framework we obtain a dual representation of both parts of the nonlocal total variation. Let us briefly introduce the most important notions for the following statement. First, a random walk m = {mx ∈ P(X ) : x ∈ X } ∈ RW (X ) can be understood as a family of probability measures on X which depend measurably on x; the complete definition is given in Definition 2.8. Next, the set of test functions is now defined as  M := m ∈ RW (X ) : supp mx ⊂ Bε (x) for ϱ-almost every x ∈ X . To be able to apply the measurable maximum theorem later on, we need the following mild technical assumption. Assumption 2.1. For any x ∈ X and 0 < r < ε there exists a mapping Tx,r : Bε (x) → Bε−r (x) measurable such that d(Tx,r (y), y) ≤ r for all y ∈ Bε (x). Showing that Assumption 2.1 holds in a general metric space is rather difficult. However, in several important settings the mapping can be constructed explicitly through a map that suitably shrinks a ball with radius ε to one with radius ε − r. Example 2.2. The following two settings satisfy the Assumption 2.1.

(i) Let X = Ω ⊂ RN bounded domain equipped with the ℓp -distance d(x, y) := |x − y|p for p ∈ [1, ∞]. If Ω is convex, then the mapping is given by ε−r (y − x) + x. ε The measurability is given due to its continuity and a short calculation shows that we have |Tx,r (y) − y| ≤ r for y ∈ Bε (x) ∩ Ω. Tx,r : Bε (x) ∩ Ω → Bε−r (x) ∩ Ω,

Tx,r (y) =

(ii) Let X be a uniquely geodesic space where for any y ∈ Bε (x) there is a unique geodesic γx,y : [0, ε] → X such that γx,y (0) = x and γx,y (1) = y. Then, the mapping given by Tx,r : Bε (x) → Bε−r (x),

Tx,r (y) = γx,y (ε − r)

satisfies Assumption 2.1 if it is measurable. This is, for example, true for smooth manifolds— thanks to the theory of Jacobi fields which shows that Tx,r is even continuous—but needs to be checked in general. 7

The following is the main theorem of this section and a key ingredient for dualizing the total variation. Theorem 1 (Dual reformulation). Let X be a proper metric space satisfying Assumption 2.1, let µ ∈ P(X × {0, 1}) be a probability measure and ϱi := µ( · × {i}) for i ∈ {0, 1} the respective conditional distributions. Then, for u ∈ C(X ) we have Z Z Z u(y) dmx (y) dϱ0 (x) max u dϱ0 (x) = max m∈M

X Bε (x)

X

X

and Z

Z Z min u dϱ1 (x) = min

m∈M

X Bε (x)

u(y) dmx (y) dϱ1 (x). X

X

Proof of Theorem 1. The application of Proposition 2.3 and Lemma 2.10 below leads to the first equality. The second equality is obtained in an analogous way. As a first step, to obtain a dual formulation of the maximum over Bε (x), we use probability measures as test functions and note that the maximum is attained by Dirac measures concentrated at maximizers. Proposition 2.3. Let X be a proper metric space. Then, for every u ∈ C(X ) and x ∈ X we have Z max u = max u dm. Bε (x)

m∈P(Bε (x))

Bε (x)

Proof. Since u is continuous on X it is in particular a continuous function on Bε (x) ⊂ X which is a compact subset due to the properness of X . Hence, for all x ∈ X there exist Mx ∈ R such that maxBε (x) u = Mx and yx ∈ Bε (x) such that u(yx ) = Mx . Fix x ∈ X and let m ∈ P(Bε (x)) to obtain Z u(y) dm(y) ≤ Mx · m(Bε (x)) = max u. Bε (x)

Bε (x)

Since m ∈ P(Bε (x)) is arbitrarily chosen, we have Z max u ≥ max Bε (x)

m∈P(Bε (x))

u(y) dm(y).

Bε (x)

For the other inequality define m̂ := δyx which is a probability measure on Bε (x). Consequently, Z Z u(y) dm(y) ≥ u(y) dm̂(y) = u(yx ) = max u. max m∈P(Bε (x))

Bε (x)

Bε (x)

Bε (x)

This completes the proof. Since the dual space of continuous functions consists of measures, we need to work with a suitable topology. There are several ways to define convergence of measures. The following definition extends to one from [1, Chapter 13] to finite signed measures which we denote by M± f (X ). Definition 2.4 (Weak convergence of measures). Let X be a metric space and m ∈ M± f (X ). We ± say that (mn )n∈N ⊂ Mf (X ) converges weakly to m if Z Z n→∞ f dmn −−−−→ f dm for all f ∈ Cb (X ), X

X

where Cb (X ) denotes the space of continuous and bounded functions on X . The topology induced by weak convergence is called weak topology τw . 8

To distinguish limits of measures from limits of functions, we write m = w-limn→∞ mn if ± (mn )n∈N ⊂ M± f (X ) converges weakly to a limit measure m ∈ Mf (X ). Remark 2.5 (Measure convergence from a functional analytic perspective). Note that the term weak convergence may be slightly misleading, since τw corresponds to the weak-* topology in the functional analytic sense. However, to remain consistent with the literature, we keep this terminology. Next, we define a set of test functions that is independent of x by taking the maximum over families of measures instead of selecting each one individually. For this purpose, the family must be measurable in x to allow integration over X . To construct such a family, we rely on measurable selector functions of correspondences. We briefly introduce the most relevant definitions. A correspondence φ : S ↠ X from a set S to a set X is a set-valued function that assigns to each s in S a subset φ(s) of X. For a correspondence φ and a subset A ⊂ X the lower inverse φℓ is given by φℓ (A) := {s ∈ S : φ(s) ∩ A ̸= ∅}. A selector from a correspondence φ is a function f : S → X that satisfies f (s) ∈ φ(s) for each s ∈ S. If (S, Σ) is a measurable space and X a topological space, we say that a correspondence φ : S ↠ X is weakly measurable if φℓ (G) ∈ Σ for each open subset G ⊂ X and that φ is measurable if φℓ (F ) ∈ Σ for each closed subset F ⊂ X. A complete introduction to this topic can be found in [26, 27, 34]. Lemma 2.6. Let X be a Polish metric space and define the correspondence ψ : X ↠ P(X ),

ψ(x) := P(Bε (x)).

(2.1)

Under Assumption 2.1, the correspondence ψ is weakly measurable with respect to BX . Proof. Let G ⊂ P(X ) be an open set with respect to τw . We show that  ψ ℓ (G) = {x ∈ X : G ∩ ψ(x) ̸= ∅} = x ∈ X : ∃m ∈ G s.t. m ∈ P(Bε (x)) is open. For x ∈ ψ ℓ (G) there exists m ∈ G ∩ P(Bε (x)) and by Assumption 2.1 for 0 < r < ε there is a measurable mapping Tx,r : Bε (x) → Bε−r (x) such that d(Tx,r (y), y) ≤ r for y ∈ Bε (x). We define the pushforward measure µ := (Tx,r )♯ m ∈ P(Bε−r (x)) and note that µ ∈ P(Bε (y)) for all y ∈ Br (x). Furthermore, the Wasserstein-1 distance between m and µ can be upper-bounded as follows Z Z W1 (m, µ) ≤ d(Tr (y), y) dm(y) ≤ r dm(y) = r. Bε (x)

Bε (x)

Using that the Wasserstein-1 distance metrizes (P(Bε (x)), τw ), see [25], we obtain the existence of r0 > 0 such that µ ∈ G if W1 (m, µ) ≤ r0 . So by choosing r0 ≥ r > 0 small enough it follows that µ ∈ P(Bε (x)) ∩ G and therefore y ∈ ψ ℓ (G) for y ∈ Br (x) which implies that also the lower inverse of ψ is open and thus a Borel set. Hence, the correspondence ψ is by definition weakly measurable. We now establish the existence of a measurable selector for the correspondence ψ from Lemma 2.6. Moreover, the maximum over the x-dependent test sets is measurable in x, and the set of maximizers is nonempty and compact. Proposition 2.7. Let X be a proper metric space satisfying Assumption 2.1 and u ∈ C(X ). Define m : X → R by Z m(x) = max u(y) dm(y). (2.2) m∈P(Bε (x))

9

Bε (x)

and the argmax set ( x

A :=

)

Z m ∈ P(Bε (x)) :

u(y) dm(y) = m(x) . Bε (x)

Then, (i) m is measurable, (ii) Ax is nonempty and compact in the τw -topology for any x ∈ X , and (iii) there exists a measurable selector function Ψ : X → P(X ), meaning that Ψ(x) ∈ Ax for any x ∈ X and Ψ is measurable, i.e., for any τw -open subset G ⊂ P(X ) the preimage Ψ−1 (G) lies in the Borel σ-algebra on X . Proof. As mentioned before, Bε (x) ⊂ X is compact and thus due to Prokhohov’s theorem, P(Bε (x)) is weakly sequentially compact. Hence, the correspondence ψ as defined in (2.1) has nonempty and compact values and we aim to apply the classical measurable maximum theorem, see [27, R Theorem 18.19]. To this end we define f : Gr ψ → R, f (x, m) = Bε (x) u(y) dm(y) and by the fact that 1Bε (x) (y) is jointly measurable we obtain that f is a Carathéodory function. Lastly, since X is Polish and locally compact, the space (P(X ), τw ) is Polish. So, the measurable maximum theorem is indeed applicable and completes the proof. Using the regularity of a measurable selector, we interpret the family of measures provided by the selector function as a random walk, also known as Markov kernels in the literature. More precisely, for every x ∈ X we obtain a probability measure supported in the ε-ball around x, describing the probability distribution of a single step of the walk. We introduce random walks following [16]. Definition 2.8 (Random walk). Let (X , d) be a Polish metric space equipped with its Borel σ-algebra BX . A random walk m on X is a family of probability measures mx on X for x ∈ X satisfying (i) the measures mx depend measurably on the point x ∈ X , i.e., for any Borel set A of X and any Borel set B of R, the set {x ∈ X : mx (A) ∈ B} is Borel; (ii) each measure mx has finite first moment, i.e., for some x0 ∈ X and for any x ∈ X one has R d(x 0 , y) dmx (y) < +∞. X We define the set of random walks on X as RW (X ). Next, we show that random walks induce measurable parameter integrals. This is particularly useful since it allows integration without explicitly invoking the Fubini–Tonelli theorem. Lemma 2.9. Let X be a Polish metric space and u : X → R a measurable function. Then, for m ∈ RW (X ) the mapping Z I : X → R, x 7→ u dmx X

is measurable. Proof. First, we show the statement for u being a simple function. By definition there is a family Pn of Borel sets (Ai ) ⊂ X and αi ∈ R \ {0} (i ∈ {1, . . . , n}) such that u = i=1 αi 1Ai . Define Z Ii : X → R, x 7→ αi 1Ai dmx = αi mx (Ai ) X

10

which is a measurable mapping since the righthand side is measurable due to the definition of a random walk. Linear combinations of measurable functions still being measurable yields that Z I(x) =

u dmx = X

Z X n

αi 1Ai dmx =

n X

X i=1

Ii (x)

i=1

is measurable. Now assume that u : X → R is a general measurable function. We can split u = u+ − u− into the difference of two non-negative measurable functions. For each of them there is a sequence of − + + − − simple functions (u+ n )n∈N and (un )n∈N such that un (y) ↑ u (y) and un (y) ↑ u (y) for all y ∈ X , see [27, Theorem 4.36]. This implies that Z Z Z + I(x) = u(y) dmx (y) = u (y) dmx (y) − u− (y) dmx (y) X X X Z Z lim u− lim u+ (y) dm (y) − = x n (y) dmx (y) n X n→∞ X n→∞ Z Z = lim u+ u− n (y) dmx (y) − lim n (y) dmx (y) n→∞

n→∞

X

X

where we used the monotone convergence theorem for the last equation. Due to the first part of the proof and the fact that the pointwise limit of measurable functions is itself measurable we obtain that I is the difference of two measurable functions and thus a measurable function itself. Next, we prove that instead of integrating over each maximum separately, one may choose a maximizing random walk, thereby obtaining a set of test functions independent of x. Lemma 2.10. Let X be a proper metric space satisfying Assumption 2.1 and define  M := m ∈ RW (X ) : supp mx ⊂ Bε (x) for ϱ-almost every x ∈ X . Then for every u ∈ C(X ) and i ∈ {0, 1} we have Z Z Z Z max u(y) dm(y) dϱi (x) = max u(y) dmx (y) dϱi (x). X m∈P(Bε (x))

m∈M

Bε (x)

X

X

Proof. For the first inequality let m ∈ M. Then, by definition for ϱ-a.e. x ∈ X the measure mx Bε (x) ∈ P(Bε (x)) and thus Z Z Z max u(y) dm(y) ≥ u(y) d(mx Bε (x))(y) = u(y) dmx (y). m∈P(Bε (x))

Bε (x)

X

Bε (x)

By Proposition 2.7 (i) the lefthand side is measurable on X and by Lemma 2.9 the same is true for the righthand side. Hence, integration over X yields Z Z Z Z max u(y) dm(y) dϱi (x) ≥ u(y) dmx (y) dϱi (x). X m∈P(Bε (x))

X

Bε (x)

X

Lastly, since m ∈ M was arbitrarily chosen we obtain Z Z Z Z max u(y) dm(y) dϱi (x) ≥ max u(y) dmx (y) dϱi (x). X m∈P(Bε (x))

m∈M

Bε (x)

X

X

For the converse inequality we define a random walk by using the selector Ψ : X → P(X ) which we obtain from Proposition 2.7. Define m̂ = (m̂x ) where m̂x is the extension of Ψ(x) on X by 11

zero for every x ∈ X . Then, this family of probability measures on X is measurably dependent on x ∈ X due to the measurability of Ψ. Furthermore, it has also finite first moments which means that m̂ ∈ RW (X ). Due to the construction, the support condition is also satisfied meaning that m̂ ∈ M. Apart from that, the properties of the selector Ψ imply that Z Z u dm. u(y) dm̂x (y) = max m∈P(Bε (x))

X

Bε (x)

By Lemma 2.9 the lefthand side is measurable, whereas the measurability of the righthand side is given by Proposition 2.7. So, we can once again integrate over X to obtain Z Z max u(y) dmx (y) dϱi (x) m∈M X X Z Z Z Z ≥ u(y) dm̂x (y) dϱi (x) = max u(y) dm(y) dϱi (x) X

X m∈P(Bε (x))

X

Bε (x)

which finishes the proof. By symmetry of the nonlocal total variation functional, the same arguments apply to the second part of the sum, which completes the proof of the dual reformulation.

2.2

Nonlocal Gradient and Divergence

Based on the dual reformulation of each part of the nonlocal total variation, we rearrange the terms to obtain suitable notions of nonlocal gradient and nonlocal divergence operators connected by an integration-by-parts identity. Before stating our main result, we define its essential ingredients; the nonlocal gradient and divergence. Definition 2.11 (Nonlocal gradient). For a function u : X → R and ε > 0 we define its nonlocal gradient gradε [u] : X × X → R via gradε [u](x, y) :=

u(y) − u(x) , ε

x, y ∈ X .

Note that, in particular, this definition induces a linear operator gradε : C(X ) → C(X × X ). Next, we define a nonlocal divergence which acts like some sort of adjoint operator of the nonlocal gradient. Note that the adjoint would map signed measures on X × X to a signed measure on X . Here, however, taking the structure of our problem into account, we define the nonlocal divergence on random walks, mapping to the space of finite signed Radon measures on X , denotes by M± f (X ). A signed measure µ is called a finite signed (Radon) measure if both its positive and negative variations µ+ and µ− , given by the Jordan decomposition, are finite (Radon) measures. Definition 2.12 (Nonlocal weighted divergence). For i ∈ {0, 1} the i-the nonlocal weighted divergence is defined as the operator divϱε i : RW (X ) → M± f (X ), given by R divϱε i [m](A) :=

A

R mx (X ) dϱi (x) − X mx (A) dϱi (x) , ε

A ∈ BX .

Furthermore, for ϱ := (ϱ0 , ϱ1 ) we define divϱε : RW (X ) × RW (X ) → M± f (X ) via divϱε [m](A) := divϱε 0 [m0 ](A) − divϱε 1 [m1 ](A),

12

m ∈ RW (X ), A ∈ BX .

Finally, we introduce suitable dominating measure which allows us to simplify certain integral expressions by applying the Radon–Nikodym theorem. Definition 2.13 (Dominating measures). Given m ∈ RW (X ) × RW (X ) and ϱ = (ϱ0 , ϱ1 ) we define the random walk n ∈ RW (X ) and the probability measure ϱ ∈ P(X ) via m0x + m1x , 2 ϱ := ϱ0 + ϱ1 ,

nx :=

x ∈ X,

which satisfy m0x , m1x ≪ nx for all x ∈ X and ϱ0 , ϱ1 ≪ ϱ. Furthermore, we define the measurable function [m; ϱ] : X × X → R via [m; ϱ](x, y) :=

dϱ0 dm0x dϱ1 dm1x (x) (y) − (x) (y), dϱ dnx dϱ dnx

x, y ∈ X .

Theorem 2. Let X be a proper metric space satisfying Assumption 2.1. Furthermore, let µ ∈ P(X × {0, 1}) be a probability measure and ϱi := µ( · × {i}) for i ∈ {0, 1} the respective conditional distributions. For u ∈ C(X ) it holds Z Z Z Z gradε [u](x, y) dm0x (y) dϱ0 (x) + − gradε [u](x, y) dm1x (y) dϱ1 (x), TVε (u) = max m∈M×M X X X X Z Z = max gradε [u](x, y)[m; ϱ](x, y) dnx (y) dϱ(x). m∈M×M

X

X

For u ∈ Cb (X ) it even holds Z TVε (u) =

max

m∈M×M

−

u(x) d divϱε [m](x).

X

A straightforward rearrangement and the Radon–Nikodym theorem lead to the first two equalities in Theorem 2. Proposition 2.14 (Nonlocal gradient). Under the conditions of Theorem 2 for all u ∈ C(X ) we have Z Z Z Z 0 gradε [u](x, y) dmx (y) dϱ0 (x) + − gradε [u](x, y) dm1x (y) dϱ1 (x) TVε (u) = max m∈M×M X X X X Z Z = max gradε [u](x, y)[m; ϱ](x, y) dnx (y) dϱ(x) m∈M×M

X

X

where the nonlocal gradient gradε is defined in Definition 2.11, and the dominating measures nx and ϱ are defined in Definition 2.13. Proof. Due to Theorem 1 we have   Z Z Z Z 1 1 0 max u − u(x) dϱ0 (x) = max u(y) dmx (y) dϱ0 (x) − u(x) dϱ0 (x) ε X Bε (x) ε m0 ∈M X X X     Z Z Z    1   u(y) dm0x (y) − = max dm0x (y) u(x) dϱ0 (x)     0 m ∈M ε X X } | X {z =1 Z Z u(y) − u(x) = max dm0x (y) dϱ0 (x) ε m0 ∈M X X Z Z = max gradε [u](x, y) dm0x (y) dϱ0 (x) 0 m ∈M

X

X

13

and similarly 1 ε

Z X

Z Z u(x) − min u dϱ1 (x) = max 1 Bε (x)

m ∈M

X

− gradε [u](x, y) dm1x (y) dϱ1 (x).

X

Summing these two expressions proves the first equality. For the second one, we use Radon– Nikodym derivatives to compute Z Z Z Z dm0x dϱ0 gradε [u](x, y) dm0x (y) dϱ0 (x) = gradε [u](x, y) (y) dnx (y) (x) dϱ(x) dn dϱ x X X X X Z Z dϱ0 dm0x = (y) (x) dnx (y) dϱ(x) gradε [u](x, y) dnx dϱ X X and similarly Z Z Z Z dϱ1 dm1x − gradε [u](x, y) dm1x (y) dϱ1 (x) = − (y) (x) dnx (y) dϱ(x). gradε [u](x, y) dn dϱ x X X X X Summing both expressions, taking the maximum over m0 , m1 ∈ M, and using the definition of [m; ϱ] from Definition 2.13 shows to the second equality. Proposition 2.15 (Nonlocal divergence). Under the conditions of Theorem 2 for all u ∈ Cb (X ) and m ∈ M the following identity holds true for i ∈ {0, 1}: Z Z Z gradε [u](x, y) dmx dϱi (x) = − u(y) d divϱε i [m]. (2.3) X

X

X

Moreover, we have Z TVε (u) =

max

m∈M×M

−

u(x) d divϱε [m](x).

X

Proof. Taking into account Proposition 2.14 and Definition 2.12 it suffices to show (2.3). To see this, consider first the case where u = 1A for A ∈ BX . Then, Z Z  Z Z Z Z 1 gradε [u](x, y) dmx (y) dϱi (x) = dmix (y) dϱi (x) − dmix (y) dϱi (x) ε X X A X R Xi A R i m (A) dϱ (x) − m (X ) dϱi (x) i x x A = X ε = − divϱε i (A) Z =− u(x) d(divϱε i [m])(x). X

By linearity the same is true for a simple function u. Approximating u ∈ Cb (X ) by simple functions which converge pointwise and are uniformly bounded, we can apply the dominated convergence theorem to get the desired statement (2.3). Finally, we will prove that the divergence divϱε from Definition 2.12 is actually the unique probability measure which allows for an integration-by-parts formula like (2.3). Since we use duality techniques to show this, we restrict ourselves to u ∈ C0 (X ), i.e., the space of continuous functions vanishing at infinity, the dual space of which coincides with the space of finite signed Radon measures. Recall that a real function u on a locally compact Hausdorff space X is said to vanish at infinity if for every δ > 0 there exists a compact set K ⊂ X such that |f (x)| < δ for all x ∈ X \ K. Note that it holds C0 (X ) ⊂ Cb (X ). 14

Definition 2.16. Under the conditions of Theorem 2, we call a finite signed Radon measure µ a nonlocal divergence of a random walk m ∈ RW (X ) with weight ϱi for i ∈ {0, 1} if Z Z Z − u(x) dµ(x) = gradε [u](x, y) dmx (y) dϱi (y) for all u ∈ C0 (X ). (2.4) X

X

X

By applying the Riesz–Markov–Kakutani theorem, we show that (2.4) admits a unique solution, given by our nonlocal weighted divergence divϱε i [m]. Proposition 2.17. For each m ∈ RW (X ) there is a unique solution to (2.4) which is given by the finite signed Radon measure divϱε i [m] defined in Definition 2.12. Proof. First, for m ∈ RW (X ) define the map Gm : C0 (X ) → R by Z Z Gm [u] := − gradε [u](x, y) dmx (y) dϱi (y). X

X

Since the nonlocal gradient and integrals are linear maps, the same is true for Gm . Next, we show that Gm is a bounded which will imply that Gm ∈ C0 (X )∗ . For any u ∈ C0 (X ) we have Z Z 2ϱi (X ) u(y) − u(x) dmx (y) dϱi (y) ≤ ∥u∥∞ |Gm [u]| ≤ ε ε X X which shows that Gm is indeed bounded. The application of the Riesz–Markov–Kakutani theorem (see, e.g., [31, Theorem 1.54]) yields Rthe existence of a uniquely determined finite signed Radon measure µ on X such that Gm [u] = X u dµ. The fact that µ = − divϱε i [m] follows directly from identity (2.3).

2.3

Integral Characterization of the Subdifferential

Finally, we provide an integral characterization of the subdifferential of the adversarial total variation. Following [19], we use the dual formulation of the functional from Theorem 2 to identify the subgradients. In our setting, we have to show that the set of nonlocal divergences corresponding to admissible random walks is convex and closed with respect to weak convergence of measures. Proposition 2.18. Under the conditions of Theorem 2 and assuming that X is compact, let u ∈ C0 (X ). Then, µ∗ ∈ ∂ TVε (u) if and only if  there exists a pair of random walks m ∈ RW (X ) × RW (X )     such that supp mix ⊂ Bε (x) for ϱ-a.e. x ∈ X and i ∈ {0, 1}, Z     µ∗ = − divϱε [m] and TVε (u) = u dµ∗ . X

Before we prove this result we need two lemmas that are concerned with a suitable notion of compactness for random walks. Lemma 2.19. Let X be a metric space, F ⊂ X be open, and p ∈ Mf (X) a finite measure such R that X f dp = 0 for all f ∈ Cb (X) with f ≡ 0 in X \ F . Then, supp p ⊂ X \ F . Proof. Aiming for a contradiction, assume that supp p ̸⊂ X \ F which implies that there exists z ∈ F such that every open neighborhood of z has positive measure. Let O ⊂ F be an open neighborhood of z. By applying Urysohn’s Lemma we obtain a continuous function f : X → [0, 1] such that f (z) = 1 and f ≡ 0 on X \ O, in particular, f ≡ 0 in X \ F . Using f (z) = 1 and the 15

continuity of f , we can find a neighborhood Õ ⊂ O of z such that f > 0 on Õ. As p(Õ) > 0, we get Z Z 0< f dp ≤ f dp = 0 Õ

X

which is a contradiction. Hence, supp p ⊂ X \ F . Lemma 2.20. Let X be compact, ϱ ∈ Mf (X ) be a finite measure, and (mn )n∈N ⊂ RW (X ). Then, there exists m ∈ RW (X ) and a subsequence (mnk )k∈N ⊂ (mn )n∈N such that Z Z Z Z lim g(x, y) dmnk ,x (y) dϱ(x) = g(x, y) dmx (y) dϱ(x) for all g ∈ C(X × X ). k→∞

X

X

X

X

If, moreover, supp mn,x ⊂ Bε (x) for ϱ-almost every x ∈ X and all n ∈ N, then supp mx ⊂ Bε (x) for ϱ-almost every x ∈ X . Proof. If ϱ(X ) = 0, then ϱ = 0 and the statement holds trivially. Hence, without loss of generality, 1 assume that ϱ is a probability measure, otherwise we replace ϱ by ϱ(X ) ϱ. For each n ∈ N there exists the so called semidirect product, see [23, Theorem 6.11], that is a unique probability measure pn on the product space X × X equipped with the product Borel σ-algebra BX ⊗ BX satisfying Z pn (A × B) = mn,x (B) dϱ(x) for A, B ∈ BX , (2.5) A

and ZZ

Z Z f (x, y) dpn (x, y) = X ×X

f (x, y) dmn,x (y) dϱ(x) X

X

for any BX ⊗ BX -measurable function f : X × X → R. The latter is a direct consequence of [23, Theorem 6.11] by splitting f in positive and negative part. Since X is compact, so is X × X and we can apply Prokhorov’s theorem to obtain a subsequence (pnk )k∈N ⊂ (pn )n∈N and p ∈ P(X × X ) such that p = w-limk→∞ pnk . Next, define q := π♯ p where π is the projection on the first factor. The application of the disintegration theorem, see [31, Theorem 2.28], yields the existence of a q-almost everywhere uniquely determined family of probability measures {mx }x∈X satisfying the properties of a random walk on X and Z p(A × B) = mx (B) dq(x) for A, B ∈ BX . A

Furthermore, for any measurable f : X × X → R we have ZZ Z Z f (x, y) dp(x, y) = f (x, y) dmx (y) dq(x) X ×X

X

X

Next, for n ∈ N define qn := π♯ pn and note that for any A ∈ BX we have Z qn (A) = π♯ pn (A) = pn (A × X ) = mn,x (X ) dϱ(x) = ϱ(A) A

and hence trivially ϱ = w-limk→∞ qnk . Furthermore, since for any f ∈ C(X ), the function f ◦ π lies in C(X × X ), it holds that Z ZZ ZZ f (x) dq(x) = f (π(x, y)) dp(x, y) = lim f (π(x, y)) dpnk (x, y) k→∞ X X ×X X ×X Z = lim f (x) dqnk (x) k→∞

X

16

which implies q = w-limk→∞ qnk . So, by the uniqueness of the weak limit we have q = ϱ and, in particular, Z p(A × B) = mx (B) dϱ(x) for A, B ∈ BX . A

Lastly, for any g ∈ C(X × X ) we obtain Z Z ZZ lim g(x, y) dmnk ,x (y) dϱ(x) = lim g(x, y) dpnk (x, y) k→∞ X X k→∞ X ×X ZZ Z Z = g(x, y) dp(x, y) = g(x, y) dmx (y) dϱ(x). X ×X

X

X

For the second statement assume that supp mn,x ⊂ Bε (x) for ϱ-almost every x ∈ X and for all n ∈ N. Furthermore, define p̃n : BX ⊗ BX → R by Z := p̃n (E) mn,x (Ex ) dϱ(x) for E ∈ BX ⊗ BX X

where Ex := {y ∈ X : (x, y) ∈ E}. Note that for two disjoint sets E 1 , E 2 ⊂ X × X we have that (E 1 ∪ E 2 )x = Ex1 ∪ Ex2 and thus p̃n defines a finite measure on (X × X , BX ⊗ BX ). Additionally, for E = A × B, where A, B ∈ BX , we have that Ex = B for x ∈ A and Ex = ∅ otherwise and hence Z p̃n (A × B) = mn,x (B) dϱ(X) = pn (A × B). A

Since pn is the unique measure satisfying (2.5), we obtain that pn = p˜n . Next, define  B := (x, y) ∈ X × X : y ∈ Bε (x) and observe that for the complement it holds that (B c )x = (Bε (x))c which implies that Z c pn (B ) = mn,x ((Bε (x))c ) dϱ(x) = 0 X

and thus for all f ∈ Cb (X × X ) that are only supported outside of B we have Z Z Z Z f (x, y) dp(x, y) = lim f (x, y) dpnk (x, y) = 0 X

k→∞

X

X

X

and by Lemma 2.19 we obtain supp p ⊂ B. Similarly as before we show that Z p(E) = mx (Ex ) dϱ(X) for E ∈ BX ⊗ BX . X

Hence, Z

mx ((Bε (x))c ) dϱ(x) = p(B c ) = 0

X

implying that supp mx ⊂ Bε (x) for ϱ-a.e. x ∈ X . Now that we secured the compactness of M we can finally prove Proposition 2.18.

17

Proof of Proposition 2.18. By Theorem 2 we have for u ∈ C0 (X ) that Z TVε (u) = max − u(x) d divϱε [m](x) m∈M×M X Z = max u(y) dµ(y) − χP (µ) = χ∗P (u) ± µ∈Mf (X )

X

where P := {− divϱε [m] : m ∈ M × M} ⊂ Mf± (X ). As shown in [32, Example 4.3], for µ ∈ Mf (X ) it holds that TV∗ε (µ) = χ∗∗ P (µ) = χconv(P ) (µ), where the closure is taken with respect to weak measure convergence. Applying the Fenchel–Young inequality, we have that µ∗ ∈ ∂ TVε (u) if and only if Z ∗ ∗ u dµ∗ . TVε (u) + TVε (µ ) = X

Hence, the proof is finished if we show that P is convex and closed. First, to prove convexity note that for m0 , m1 ∈ M their convex combination mθ ∈ RW (X ) which is defined through mθx := (1 − θ)m0x + θm1x for θ ∈ [0, 1] satisfies supp mθx = supp((1 − θ)m0x ) ∪ supp(θm1x ) = supp m0x ∪ supp m1x ⊂ Bε (x) for ϱ-a.e. x ∈ X which implies that M is convex. Due to the linearity of divϱε i in the definition of divϱε , set P is a convex set. Next, let (pn )n∈N ⊂ P and p be a finite signed measure such that p = w-limn→∞ pn is the limit with respect to weak measure convergence. Then, by definition for each pn there exists mn ∈ M × M such that pn = divϱε [mn ]. We apply Lemma 2.20 to both components min for i ∈ {0, 1} to obtain that for a subsequence (which we do not relabel) we have Z Z Z Z lim g(x, y) dmin,x (y) dϱi (x) = g(x, y) dmix (y) dϱi (x), ∀g ∈ C(X × X ). (2.6) n→∞

X

X

X

X

Applying (2.6) to g := gradε [f ] ∈ C(X × X ) for f ∈ C(X ), using (2.3) as well as Proposition 2.15 we have Z Z f dp = lim f dpn n→∞ X X Z Z ϱ0 0 = lim f d divε [mn ] − lim f d divϱε 1 [m1n ] n→∞ X n→∞ X Z Z = lim − gradε [f ](x, y) dm0n,x (y) dϱ0 (x) n→∞ X X Z Z − lim − gradε [f ](x, y) dm1n,x (y) dϱ1 (x) n→∞ X X Z Z =− gradε [f ](x, y) dm0x (y) dϱ0 (x) X X Z Z Z + gradε [f ](x, y) dm1x (y) dϱ1 (x) = − f (x) d divϱε [m](x). X

X

X

Since X is compact, we have C(X ) = C0 (X ) and Proposition 2.17 shows that p = − divϱε [m] ∈ P as equality of finite signed Radon measures.

18

To conclude this section, we now show that our result matches with the subgradient formula derived in [4] in the setting where X = Ω ⊂ RN is a bounded domain and u ∈ C 2 (Ω) is such that |∇u| ≥ c in Ω for a constant c > 0. In this case, an explicit subgradient of u was constructed in [4], but it was not investigated whether this is the only  subgradient. For Ω define the inner parallel set as Ωε := x ∈ Ω : dist(x, RN \ Ω) > ε . Then, under the assumptions above for any x ∈ Ωε the sets arg maxBε (x) u and arg minBε (x) u are singletons and induce C 1 diffeomorphism. We show that in this case the subdifferential is a singleton. Example 2.21. Under the conditions of Proposition 2.18 and for any u ∈ C(X ) such that the maps and

Γε (x) := arg maxBε (x) u

γε (x) := arg minBε (x) u

are singletons for every x ∈ X , the subdifferential is given by ∂ TVε (u) = {p} where p is the finite signed Radon measure defined by p(A) :=

(Γε )♯ ϱ0 (A) − ϱ0 (A) ϱ1 (A) − (γε )♯ ϱ1 (A) + , ε ε

A ∈ BX .

First, due to the assumption on u the mappings Γε and γε reduce to measurable functions on X , see Remark 2.22, and we can rewrite Z  Z

1 TVε (u) = u(Γε (x)) − u(x) dϱ0 (x) + u(x) − u(γε (x)) dϱ1 (x) . ε X X On the other hand, due to Proposition 2.18 for any µ∗ ∈ ∂ TVε (u) there exists m ∈ M × M such that Z TVε (u) = u dµ∗ X   Z Z Z  Z 1 1 0 1 u(y) dmx (y) − u(x) dϱ0 (x) + u(x) − u(y) dmx (y) dϱ1 (x). = ε X ε X X X Subtracting both and using that u(Γε (x)) ≥ u(y) (and similarly u(γε (x)) ≤ u(y)) for all y ∈ Bε (x) yields Z Z 0 u(y) dmx (y) = u(Γε (x)) and u(y) dm1x (y) = u(γε (x)) X

X

for ϱ0 -a.e. and ϱ1 -a.e. x ∈ X . In fact, we even get u(y) = u(Γε (x)) for m0x -a.e. y ∈ Bε (x) (and similarly for γε ). Finally, Γε (x) being the unique maximizer of u over Bε (x) we obtain  m0x ( y ∈ Bε (x) : u(y) < u(Γε (x)) ) = m0x (Bε (x) \ Γε (x)) = 0 and hence m0x = δΓε (x) for ϱ0 -a.e. x ∈ X . Similarly, m1x = δγε (x) for ϱ1 -a.e. x ∈ X . Note, that by definition of the pushforward measure one can rewrite Z Z
(Γε )♯ ϱ0 (A) = ϱ0 Γ−1 (A) = 1 (Γ (x)) dϱ (x) = δΓε (x) (A) dϱ0 (x) A ε 0 ε X

X

for any A ∈ BX . So, there is only one subgradient µ∗ of TVε (u) which is given by R R δΓ (x) (A) dϱ0 (x) − ϱ0 (A) ϱ1 (A) − X δγε (x) (A) dϱ1 (x) + µ∗ (A) = X ε ε ε (Γε )♯ ϱ0 (A) − ϱ0 (A) ϱ1 (A) − (γε )♯ ϱ1 (A) = + = p(A), A ∈ BX . ε ε 19

For the sake of completeness we prove that in the setting of Example 2.21 the mappings Γε and γε indeed reduce to measurable functions on X . Remark 2.22 (Measurability of Γε and γε ). We only show that Γε is a measurable function since γε follows analogously. Knowing that Γε (x) is a singleton for every x ∈ X , it is clear that the correspondence Γε reduces to a function. To prove its measurability, define for any x ∈ X the argmax set, in the spirit of Proposition 2.7, by ) ( Z Ax :=

m ∈ P(Bε (x)) :

u dm = m(x) Bε (x)

where m is the duality formulation of the maximum as defined in (2.2). By Proposition 2.3 we have that m(x) = maxBε (x) u and thus ( x

A =

Z m ∈ P(Bε (x)) :

) u dm = u(Γε (x)) .

Bε (x)

Using the same arguments as in Example 2.21 we obtain that Ax = {δΓε (x) } is a singleton and by Proposition 2.7 there exists a measurable function D : X → P(X ) given by D(x) = δΓε (x) . Finally, this implies that also Γε is measurable. To see this, note that for any continuous function u ∈ C(X ) we have Z u(Γε (x)) = u(y) dδΓε (x) (y). X

Since X is compact, the right hand side is the composition of the measurable function D with a continuous function, namely the integral against u. Hence, we get that for any u ∈ C(X ) the map x 7→ u(Γε (x)) is measurable. It remains to show that this implies measurability of Γε . Let A ∈ BX be an open set and choose continuous function un such that un (x) → 1A (x) for all x ∈ X . Applying this shows un (Γε (x)) → 1A (Γε (x)) and, since the pointwise limit of measurable functions is measurable, the function x 7→ 1A (Γε (x)) is measurable. This is equivalent to Γ−1 ε (A) being measurable and hence Γε is measurable.

3

Dualization for L∞ (Ω)

In the previous section we showed that the adversarial total variation functional admits a duality formulation for continuous functions vanishing at infinity and we characterized the subdifferential on compact spaces. In this section, we pursue the same goal while dropping the assumption that u is continuous. This naturally leads to a smaller set of admissible test functions and hence to a different characterization of the subdifferential. Furthermore, it reintroduces the reference measure ν in (1.3) which was irrelevant in the previous section. In Section 3.1 we show that the essential supremum and infimum admit a dual representation in a very general setting. In Section 3.2 we focus on the dual reformulation of the adversarial total variation for essentially bounded functions on Euclidean domains equipped with the Lebesgue measure as reference measure. This setting, which was also adopted in [4, 5], simplifies certain technicalities while still covering the relevant scenario of data distributions at the population level. Next, in Section 3.3 we obtain an integration-by-parts identity involving the previously defined nonlocal gradient and corresponding nonlocal divergence. Finally, we conclude with a limit characterization of the subdifferential of the adversarial total variation.

20

3.1

Dualisation of Essential Supremum and Infimum

In the following, we show that the essential supremum (respectively infimum) can be dualized in a general measure space setting for essentially bounded functions. Let (S, Σ, ν) be a measure space. If for every E ∈ Σ with ν(E) = ∞ there exists F ∈ Σ such that F ⊂ E and 0 < ν(F ) < ∞, then ν is called semifinite. Every σ-finite measure is semifinite. Further details can be found in [33]. Unless stated otherwise, we assume throughout that (S, Σ, ν) is a measure space with a semifinite measure ν. With Lp (S) for p ∈ [1, ∞] we denote the standard Lebesgue spaces with respect to the measure ν. First, similarly to the continuous case, we show that the essential supremum admits a dual representation. For f ∈ L∞ (S) the essential supremum and infimum are finite, and the test functions can be chosen to stem from the predual space L1 (S). Lemma 3.1. Let f ∈ L∞ (S) and define n o G := g ∈ L1 (S) : g ≥ 0 ν-a.e. on S and ∥g∥L1 (S) = 1 . Then, Z

Z

ν- ess sup f = sup S

g∈G

f g dν

ν- ess inf f = inf

and

S

S

g∈G

f g dν. S

Proof. We only prove the first equality since the second can be shown analogously. First, choose g ∈ G arbitrarily to obtain Z Z f g dν ≤ ν- ess sup f g dν = ν- ess sup f. S

S

S

S

So, supg∈G S f g dν ≤ ν- ess supS f . For the converse inequality let δ > 0 and define the set A := {f ≥ ν- ess supS f − δ}. Then, by definition ν(A) > 0 and due to the semifiniteness of ν there is a subset B ⊂ A such that 0 < ν(B) < ∞. Next, define g ∗ := ν(B)−1 1B ∈ G which yields Z Z Z sup f g dν ≥ f g ∗ dν = − f dν ≥ ν- ess sup f − δ. R

g∈G

S

Sending δ to zero implies supg∈G

S

R S

B

S

f g dν ≥ ν- ess supS f .

Remark 3.2. The duality formulation derived in Lemma 3.1 can be also shown for general measurable functions by replacing the potentially unbounded function f with a suitable function f ∈ L∞ in any nontrivial case, i.e., the left-hand side is finite. Remark 3.3 (Adversarial total variation for unbounded functions). For generic non-zero data distribution measures ϱ0 and ϱ1 one can easily find u ∈ L1 (S) \ L∞ (S) such that ν- TVε (u) = ∞. Under certain technical assumptions on the supports of the measures (e.g., if they are not both fully supported), one can identify cases where ν- TVε (u) < ∞ despite u ∈ / L∞ (S). To keep the exposition simple, we therefore restrict ourselves in the following to essentially bounded functions, which covers most relevant situations from a practical point of view.

3.2

Dual Reformulation for Essentially Bounded Functions

Based on the general duality formulation for the essential supremum and infimum, we now complete the reformulation of TVε for essentially bounded functions defined on finite-dimensional spaces. The goal is to extract a measurable selector that allows us to define a single test function over which we can maximize (or minimize), instead of dealing with infinitely many individual test functions 21

for each data point. To achieve this, we first restrict the class of test functions to continuous L1 functions, which later enables us to construct jointly measurable test functions. In the following, we set X = Ω ⊂ RN as a bounded domain equipped with the Euclidean distance. For technical reasons we have to assume that Ω is convex. Moreover, as reference measure ν we choose the N -dimensional Lebesgue measure on Ω. Note that parts of the construction also apply to general N reference measures, see R Remark R3.11. We assume ϱ0 , ϱ1 ≪ λ , identify these measures with their densities, and write f dϱ0 = f ϱ0 dx for notational convenience. In addition to that, to be consistent with commonly used notation but slightly inconsistent with Section 2, we refer to the  standard norm ball around x ∈ Ω by Bε (x) = y ∈ RN : |x − y| < ε , and as before its closure is denoted by Bε (x). Correspondingly, all occurrences of Bε (x) will be replaced by Bε (x) ∩ Ω in this section which equals the ε-ball on the metric space Ω equipped with the Euclidean distance restricted to Ω. We obtain the following dual representation as the main result of this part where the set of test functions is given by Z     Ψ ≥ 0 a.e. on Ω × Ω, Ψ(x, y) dy = 1, . P := Ψ ∈ L1 (Ω × Ω) Ω   ess supp Ψ(x, ·) ⊂ Bε (x) ∩ Ω for x ∈ Ω For technical reasons we have to pose a convexity assumption on Ω for the proofs in this section to work. Assumption 3.4. The feature space Ω ⊂ RN is a bounded and convex domain.

Theorem 3 (Dual representation). Let Ω ⊂ RN satisfy Assumption 3.4, let µ ∈ P(Ω × {0, 1}) be a probability measure, and assume that the respective conditional distributions ϱi := µ( · × {i}) for i ∈ {0, 1} are absolutely continuous with respect to the N -dimensional Lebesgue measure. Then, for u ∈ L∞ (Ω) we have Z Z Z ess sup u ϱ0 (x) dx = sup Ψ(x, y)ϱ0 (x)u(y) dy dx Ψ∈P

Ω Bε (x)∩Ω

Ω

Ω

and Z

Z Z ess inf u ϱ1 (x) dx = inf

Ψ∈P

Ω Bε (x)∩Ω

Ψ(x, y)ϱ1 (x)u(y) dy dx. Ω

Ω

Proof. This follows by combining Proposition 3.5 and Lemmas 3.6, 3.10 and 3.12 below. As a first step, we derive the dual formulation of the essential supremum and infimum by applying Lemma 3.1. Proposition 3.5. Let Ω ⊂ RN be a bounded domain and u ∈ L∞ (Ω). Then, for all x ∈ Ω we have Z Z ess sup u = sup uφ dy and ess inf u = inf x uφ dy Bε (x)∩Ω

φ∈Px

Bε (x)∩Ω

Ω

where the set of test functions is given as  x P := φ ∈ L1 (Ω) : φ ≥ 0 a.e. on Ω,

φ∈P

Ω

Z ess supp φ ⊂ Bε (x) ∩ Ω,

 φ dy = 1 .

(3.1)

Ω

Proof. Applying Lemma 3.1 to S = Ω ∩ Bε (x) and ν = λN and afterwards extending the test functions by zero onto Ω leads to the result. 22

Next, we restrict the set of test functions to continuous ones, which later allows us to utilize that Carathéodory functions are jointly measurable test functions. This is achieved by approximating almost maximizing functions via mollification, which is possible due to the specific choice of the reference measure. Lemma 3.6. For Ω satisfying Assumption 3.4 and x ∈ Ω we have Z Z Z Z sup uφ dy = sup uφ dy and inf x uφ dy = inf x uφ dy φ∈Px

φ∈Px c

Ω

φ∈P

Ω

where Px is defined as in (3.1) and  Pxc := φ ∈ C(Ω) : φ ≥ 0,

φ∈Pc

Ω

Z supp φ ⊂ Bε (x) ∩ Ω,

Ω

 φ dy = 1 .

(3.2)

Ω

Proof. We only show the first equality, since the second one follows analogously. First, for δ > 0 choose φ̂ ∈ Px such that Z Z φ̂(y)u(y) dy ≥ sup φ(y)u(y) dy − δ. φ∈Px

Ω

Ω

The overall idea is to first squeeze the support of the test function such that we can afterwards mollify it, see Figure 1 for a visualization. By assuming convexity of Ω the “squeezing-operation” is well-defined. For n ∈ N we define the squeezed function by  φ̂n (y) :=

n+1 n

N

 φ̂

n+1 n

 y−

x n



n for y ∈ n+1 (Ω + nx ) ⊂ Ω and zero otherwise. Since Ω is convex by Assumption 3.4, φ̂n is welldefined. Furthermore, for all n ∈ N its support satisfies n 1 ess supp (φ̂n ) ⊂ B n+1 ε (x) ∩ Ω = Bε− n+1 ε (x) ∩ Ω.

Furthermore, by definition we have φ̂n ∈ L1 (Ω) and ∥φ̂n ∥L1 (Ω) = 1. Apart from that, the squeezed function also converges to the original function φ̂ in L1 (Ω) as n goes to infinity. To see this, let µ > 0 and choose f ∈ Cc∞ (Ω) such that ∥φ̂ − f ∥L1 (Ω) ≤ µ2 , which is possible since Cc∞ (Ω) is densely contained in L1 (Ω). For y ∈ Ω we then have N      n+1 n+1 x n+1 x |φ̂n (y) − φ̂(y)| ≤ φ̂ y− −f y− n n n n n !  N     n+1 x x n+1 n+1 −1 f y− y− − f (y) + |f (y) − φ̂(y)| . + + f n n n n n 

Next, we perform the change of variables w := an y − nx where an := n+1 n , which is once again possible due to the convexity of Ω, to obtain Z |φ̂n (y) − φ̂(y)| dy Ω Z Z  aN x n −1 f (w) dw + f a y − − f (y) dy + ∥φ̂ − f ∥L1 (Ω) . ≤ ∥φ̂ − f ∥L1 (Ω) + n n RN aNn Ω 23

Taking the limit n → ∞, and using the continuity of f as well as the fact that an → 1 as n → ∞, we obtain Z lim |φ̂n (y) − φ̂(y)| dy ≤ µ. n→∞

Ω

Since µ > 0 was arbitrary, we have proved the L1 -convergence of φ̂n to φ̂. The second part of the construction is the mollification of the squeezed function. For that we fix n ∈ N and apply a standard mollifier ! −N  x ε η ηm (x) := ε m+2 m+2 R where η ∈ Cc∞ (RN ) is such that RN η dx = 1, η ≥ 0, and supp η ⊂ B1 (0). We extend φ̂n ∈ L1 (Ω) by zero to define the measurable function Z
∗ := φn,m (y) φ̂n ∗ ηm (y) = φ̂n (z)ηm (y − z) dz

R

N

for all y ∈ Ω. By standard results for mollifiers we obtain that φ∗n,m ∈ L1 (Ω), φ∗n,m is continuous on Ω, and φ∗n,m → φ̂n in L1 (Ω) for m → ∞. Moreover, by construction φ∗n,m is nonnegative on Ω and φ̂∗n,m L1 (Ω) = 1. Lastly, its support is contained in the following Minkowski sum supp(φ∗n,m ) = ess supp (φ̂n ∗ ηm ) ⊂ ess supp (φ̂n ) + ess supp (ηm ) 1 1 ⊂ Bε(1− n+1 + m+2 ) (x) ⊂ Bε (x)

if m ≥ n. In particular, for m ≥ n we have that φ∗n,m ∈ Pxc . For the last part we apply the L1 -convergences of φ∗n,m → φ̂n for m → ∞ and φ̂n → φ̂ for n → ∞ to obtain Z Z Z φ̂n (y)u(y) dy sup φ(y)u(y) dy ≥ lim lim φ∗n,m (y)u(y) dy = lim φ∈Px c

n→∞ n≤m→∞

Ω

n→∞

Ω

Z

Ω

Z φ̂(y)u(y) dy ≥ sup

=

φ∈Px

Ω

φ(x, y)u(y) dy − δ. Ω

So, by sending δ to zero we obtain the first inequality Z Z sup φ(y)u(y) dy ≤ sup φ(y)u(y) dy φ∈Px

φ∈Px c

Ω

Ω

and since the other inequality is trivial the proof is completed. We now show that the underlying correspondence is weakly measurable. Compared to Example 2.2, a more delicate construction is required to shift the support of the test function while preserving continuity. In particular, simply moving the mass to the center would introduce discontinuities if φ were nonzero on ∂Ω. Therefore, we introduce a continuous function that cuts off φ only near ∂Bε (x) ∩ Ω, where it is already small. Lemma 3.7. Let Ω satisfy Assumption 3.4 and define the correspondence ψ : Ω ↠ C(Ω), Then, ψ is a weakly measurable correspondence. 24

ψ(x) = Pxc .

R φ∗n,m

φ̂n φ̂

x

x−ε

x+ε

RN

Figure 1: Schematic visualization of the construction by squeezing and mollifying. Proof. Let G ⊂ C(Ω) be open. We show that ψ ℓ (G) = {x ∈ Ω : G ∩ ψ(x) ̸= ∅} = {x ∈ Ω : ∃φ ∈ G s.t. φ ∈ Pxc } is open and thus a Borel set. Let x ∈ ψ ℓ (G) be fixed and denote the corresponding function by φx ∈ G ∩ ψ(x). For fixed δ > 0, there exists a 0 < rδ < ε depending on x such that φx (y) ≤ δ for all y ∈ (Bε (x) ∩ Ω) \ Bε−rδ (x) as φx is zero on ∂Bε (x) ∩ Ω. Note that rδ → 0 for δ → 0 as φx is uniformly continuous which allows us to choose a δ > 0 such that Brδ (x) ⊂ Ω since Ω is open. Applying Urysohn’s Lemma, we define a continuous cutoff function ζ ∈ C(Ω; [0, 1]) such that ζ = 0 on Ω \ Bε− rδ (x) and ζ = 1 on Bε−rδ (x) ∩ Ω. Furthermore, we define 2 Z −1 := := φC Z · ζ · φx where Z ζφx dy. Ω

By construction, φC is a nonnegative continuous function and ∥φC ∥L1 (Ω) = 1. Furthermore, supp φC ⊂ Bε− rδ (x) ∩ Ω, which, thanks to the convexity of Ω from Assumption 3.4, implies that 2 supp φC ⊂ Bε (y) ∩ Ω for all y ∈ B rδ (x). Hence, φC ∈ Pyc for all y ∈ B rδ (x). 2 2 Next, we show that φC ∈ G for δ > 0 small enough. Since G is an open set, there exists ϱ > 0 such that any φ ∈ C(Ω) satisfying ∥φx − φ∥∞ ≤ ϱ is also an element of G. By inserting the corresponding estimates we find that for y ∈ Ω we have |φx (y) − φC (y)| ≤ |φx (y)| |1 − Zζ(y)|  for y ∈ Ω \ Bε− rδ (x),  δ 2 ≤ δ · max{1, |1 − Z|} for y ∈ Bε− rδ (x) ∩ Ω \ Bε−rδ (x), 2   ∥φx ∥∞ · |1 − Z| for y ∈ Bε−rδ (x) ∩ Ω. Note that the first and the third estimate follow directly from the properties of ζ. For the second one we note that Z ≥ 1 and by making a simple case distinction on Z ≤ 2 and Z > 2 and using ζ ∈ [0, 1] we arrive at the second estimate. In addition to that Z Z 1≥ ζφx dy ≥ φx dy ≥ 1 − δ |Bε (x) \ Bε−rδ (x)| Ω

Bε−rδ (x)

implying that Z → 1 for δ → 0. So, |φx (y) − φC (y)| is controlled by δ independent of y ∈ Ω which implies that ∥φx − φC ∥∞ ≤ ϱ for sufficiently small δ. Lastly, if necessary we choose δ small enough such that B rδ (x) ⊂ Ω to finally obtain φC ∈ G ∩ ψ(y) for all y ∈ B rδ (x) which proves that ψ ℓ (G) 2 2 is open and thus Borel. So ψ is indeed a weakly measurable correspondence. 25

Having established weak measurability of the correspondence ψ, we aim to extract a measurable selector as in the previous section. However, since ψ is not compact-valued, the classical measurable maximum theorem is not applicable. Instead, we employ an adaptation for closed-valued correspondences, namely Theorem 5 in the appendix, which still yields a measurable selector. Proposition 3.8. Let Ω satisfy Assumption 3.4 and let u ∈ L∞ (Ω). Define s : Ω → R by Z s(x) := sup u(y)φ(y) dy φ∈Px c

Ω

where Pxc is defined as in (3.2). Furthermore, for δ > 0 and x ∈ Ω define the set   Z x x := Sδ φ ∈ Pc : u(y)φ(y) dy ≥ s(x) − δ . Ω

Then, (i) s is measurable, (ii) Sδx is nonempty and closed with respect to the supremum norm topology for any x ∈ Ω, and (iii) there exists a measurable selector function Ψ : Ω → C(Ω), meaning that Ψ(x) ∈ Sδx for any x ∈ Ω and Ψ is measurable, i.e., for any open subset G ⊂ C(Ω) the preimage Ψ−1 (G) lies in the Borel σ-algebra on Ω. Proof. Firstly, by Proposition 3.5 s(x) = ess supBε (x) u < ∞ for all x ∈ Ω as u ∈ L∞ (Ω). By Lemma 3.7 the correspondence ψ : Ω ↠ C(Ω) is weakly measurable. Next, for fixed x ∈ Ω the respect to uniform convergence. Similarly, the maximized set Pxc is nonempty and closed with R function f : Gr ψ → R, f (x, φ) = Ω uφ dy is a Carathéodory function since continuity in the second argument is equivalent to weak convergence and f is trivially measurable in the first argument. Lastly, C(Ω) is Polish, so we can apply Theorem 5 to obtain the result. The symmetry between supremum and infimum directly gives the analogous result. Corollary 3.9. Let Ω satisfy Assumption 3.4 and let u ∈ L∞ (Ω). Define i : Ω → R by Z i(x) := inf x u(y)φ(y) dy φ∈Pc

Ω

where Pxc is defined as in (3.2) Furthermore, for δ > 0 and x ∈ Ω define the set Iδx :=



φ ∈ Pxc :

Z

 u(y)φ(y) dy ≤ i(x) + δ .

Ω

Then, (i) i is measurable, (ii) Iδx is nonempty and closed with respect to the supremum norm topology for any x ∈ Ω, and (iii) there exists a measurable selector function Ψ : Ω → C(Ω), meaning that Ψ(x) ∈ Iδx for any x ∈ Ω and Ψ is BΩ -measurable.

26

R Proof. Let v := −u ∈ L∞ (Ω) and s : Ω → R, s(x) = supφ∈Px Ω vφ dy. Then, by Proposition 3.8 we obtain that s is measurable implying that i = −s is measurable. Furthermore, for δ > 0 and x ∈ Ω the set   Z x x Sδ := φ ∈ Pc : v(y)φ(y) dy ≥ s(x) − δ Ω

is nonempty, closed and there exists a measurable selector Ψ : Ω → C(Ω) such that Ψ(x) ∈ Sδx . Since Z Z − u(y)φ(y) dy = v(y)φ(y) dy ≥ s(x) − δ = −(i(x) + δ) Ω

Ω

we obtain that Iδx = Sδx for δ > 0 and any x ∈ Ω and therefore (ii) and (iii) follow directly. We now use the selector functions provided by Proposition 3.8 and Corollary 3.9 to redefine the set of test functions independently of x. Recall that in the continuous setting we relied on the fact that random walks define measurable parameter integrals. In the present setting it is essential that the test functions are jointly measurable. Lemma 3.10. Define Z   ′ ′   Ψ(x , y) dy = 1, Ψ ≥ 0 on Ω × Ω, Ψ(x , ·) ∈ C(Ω), Pc := Ψ ∈ L1 (Ω × Ω) . Ω   and, supp Ψ(x′ , ·) ⊂ Bε (x′ ) ∩ Ω for x′ ∈ Ω Then, under the conditions of Theorem 3 for all u ∈ L∞ (Ω) we have Z Z Z Z sup u(y)φ(y) dy ϱ0 (x) dx = sup Ψ(x, y)u(y) dy ϱ0 (x) dx Ω φ∈Px c

Ψ∈Pc

Ω

Ω

Ω

and Z

Z Z

Z inf x

Ω φ∈Pc

Ψ(x, y)u(y) dy ϱ1 (x) dx.

u(y)φ(y) dy ϱ1 (x) dx = inf

Ψ∈Pc

Ω

Ω

Ω

Proof. Fix an arbitrary Ψ ∈ Pc and note that for each x ∈ Ω by construction Ψ(x, ·) ∈ Pxc which implies that Z Z sup u(y)φ(y) dy ≥ u(y)Ψ(x, y) dy φ∈Px c

Ω

Ω

for every x ∈ Ω. Due to Proposition 3.8 (i), the left hand side is measurable, whereas the measurability of the right hand side is provided by the Fubini–Tonelli theorem. Hence, we integrate over x ∈ Ω yielding Z Z Z Z sup u(y)φ(y) dy ϱ0 (x) dx ≥ u(y)Ψ(x, y) dy ϱ0 (x) dx. Ω φ∈Px c

Ω

Ω

Ω

Since Ψ ∈ Pc is arbitrarily chosen, we obtain Z Z Z Z sup u(y)φ(y) dy ϱ0 (x) dx ≥ sup Ψ(x, y)u(y) dy ϱ0 (x) dx. Ω φ∈Px c

Ω

Ψ∈Pc

27

Ω

Ω

δ For the converse inequality fix δ > 0 and define δ0 := ϱ0 (Ω) > 0. Evoking Proposition 3.8 (iii)

implies the existence of a measurable selector function Φ : Ω → C(Ω) such that Z Z u(y)[Φ(x)](y) dy ≥ sup u(y)φ(y) dy − δ0 Ω

φ∈Px c

(3.3)

Ω

and Φ(x) ∈ Pxc for any x ∈ Ω. We define Ψ∗ : Ω × Ω → R by Ψ∗ (x, y) = evy ◦ Φ(x) where evy : C(Ω) → R, φ 7→ φ(y). So for fixed y ∈ Ω we obtain that Ψ∗ ( · , y) is the composition of a continuous function and a Borel-measurable function, hence a measurable function itself. Since Ψ∗ is continuous in its second argument, it is a Carathéodory function and thus jointly measurable. Furthermore, ∥Ψ∗ ∥L1 (Ω×Ω) = |Ω| < ∞ and we conclude that Ψ∗ ∈ Pc is an admissible test function. Hence, integrating (3.3) over Ω gives Z Z Z Z Ψ∗ (x, y)u(y) dy ϱ0 (x) dx ≥ sup u(y)φ(y) dy ϱ0 (x) dx − δ. Ω

Ω φ∈Px c

Ω

Since Ψ∗ ∈ Pc we have Z Z Z sup Ψ(x, y)u(y) dy ϱ0 (x) dx ≥ Ψ∈Pc

Ω

Ω

Z u(y)φ(y) dy ϱ0 (x) dx − δ

sup

Ω φ∈Px c

Ω

Ω

and sending δ to zero completes the proof. The proof for the second equality is completely analogue by applying Corollary 3.9. Remark 3.11 (Measurability of the test function). R R The main difficulty in this construction is to ensure that the test function Ψ is such that Ω Ω Ψ(x, y) dy dx is well defined. This is the primary reason for restricting the test functions to continuous ones as in this case we may use that Carathéodory functions are jointly measurable. Without this additional regularity, the adapted measurable selector theorem would only yield separately measurable functions, which causes difficulties for double integration; see [37]. Notably, in the general Polish metric space setting with a σ-finite reference measure ν we are able to apply the adapted measurable selector theorem but since the resulting test function is only separately measurable, we cannot perform the double integration. We now relax the assumptions on the test functions to simplify the subsequent analysis. The continuity assumption was mainly needed to construct jointly measurable functions from an infinite family. We proceed analogously to Lemma 3.6 and therefore omit intermediate steps that are entirely analogous. Lemma 3.12. Define the set Z   ′   Ψ ≥ 0 a.e. on Ω × Ω, Ψ(x , y) dy = 1, P := Ψ ∈ L1 (Ω × Ω) . Ω   ′ ′ ′ ess supp Ψ(x , ·) ⊂ Bε (x ) ∩ Ω for x ∈ Ω Then, under the conditions of Theorem 3 for all u ∈ L∞ (Ω) we have Z Z Z Z sup Ψ(x, y)u(y) dy ϱ0 (x) dx = sup Ψ(x, y)u(y) dy ϱ0 (x) dx Ψ∈Pc

Ω

Ψ∈P

Ω

Ω

Ω

and Z Z inf

Ψ∈Pc

Z Z Ψ(x, y)u(y) dy ϱ1 (x) dx = inf

Ω

Ψ∈P

Ω

28

Ψ(x, y)u(y) dy ϱ1 (x) dx. Ω

Ω

Proof. For δ > 0 choose Ψ̂ ∈ P such that Z Z Z Z Ψ̂(x, y)u(y) dy ϱ0 (x) dx ≥ sup Ψ(x, y)u(y) dy ϱ0 (x) dx − δ Ω

Ψ∈P

Ω

Ω

(3.4)

Ω

and define for n ∈ N the squeezed function N      x n+1 n+1 := y− Ψ̂ x, Ψ̂n (x, y) n n n n for (x, y) ∈ Ω× n+1 (Ω+ nx ) and zero otherwise. Next, for fixed n ∈ N we define a standard mollifier for any x ∈ Ω by !  −N ε x η ηm (x) := ε m+2 m+2

R where η ∈ Cc∞ (RN ) such that RN η dx = 1, η ≥ 0, and supp η ⊂ B1 (0). After extending Ψ̂n (x, ·) to RN by zero we define the convolution
Ψ∗n,m (x, y) := Ψ̂n (x, ·) ∗ ηm (y) for all y ∈ RN . As shown in Lemma 3.6, we have Ψ̂n −−−−→ Ψ̂ and Ψ∗n,m −−−−→ Ψ̂n in L1 (Ω). We can then apply the Lebesgue convergence theorem since Ψ∗n,m (x, · ) ∈ Px by construction and thus by Proposition 3.5 and Lemma 3.6 we have Z Z φ(y)u(y) dy ≥ Ψ∗n,m (x, y)u(y) dy. ess sup u = sup n→∞

Bε (x)∩Ω

φ∈Px

Ω

m→∞

Ω

As Ω ess supBε (x)∩Ω u ϱ0 (x) dx ≤ ∥u∥L∞ (Ω) |Ω| < ∞ the convergence is dominated by an integrable function and we end up with Z Z Z Z Ψ(x, y)u(y) dy ϱ0 (x) dx ≥ lim lim Ψ∗n,m (x, y)u(y) dy ϱ0 (x) dx sup n→∞ n≤m→∞ Ω Ω Ψ∈Pc Ω Ω Z Z Z Z Ψ̂n (x, y)u(y) dy ϱ0 (x) dx = lim lim Ψ∗n,m (x, y)u(y) dy ϱ0 (x) dx = lim n→∞ Ω n≤m→∞ Ω n→∞ Ω Ω Z Z Z Z Ψ̂n (x, y)u(y) dy ϱ0 (x) dx = Ψ̂(x, y)u(y) dy ϱ0 (x) dx. = lim R

Ω n→∞

Ω

Ω

Ω

Hence, by (3.4) and sending δ to zero we finish the proof.

3.3

Nonlocal Gradient and Divergence

With the dual representation at hand, we rearrange the terms to obtain reformulations involving the same nonlocal gradient as in the continuous case and a corresponding nonlocal divergence. A similar derivation of nonlocal operators can be found in [24]. Remark 3.13. Using the definition of the nonlocal gradient introduced in Definition 2.11 a linear operator gradε : L∞ (Ω) → L∞ (Ω × Ω) is induced by gradε [u](x, y) :=

u(y) − u(x) ε

for u ∈ L∞ (Ω).

Similar to Definition 2.12 we define a nonlocal divergence that acts like the adjoint operator. However, due to the absolute continuity of ϱ0 and ϱ1 as assumed in Theorem 3, the nonlocal divergence can be formulated independently of the conditional distributions and therefore becomes unweighted. 29

Definition 3.14 (Nonlocal divergence). The nonlocal divergence divε : L1 (Ω × Ω) → L1 (Ω) is defined by Z f (y, x) − f (x, y) divε [f ](y) := dx for all y ∈ Ω. ε Bε (y)∩Ω Remark 3.15. Note that when inserting Ψ ∈ P we implicitly only integrate over Bε (y) ∩ Ω for each y ∈ Ω due to the support condition. For general functions f ∈ L1 (Ω × Ω), however, we need to include the integration domain Bε (x) ∩ Ω into the definition of the nonlocal divergence for consistency, see Proposition 3.17. Those definitions lead to a similar duality reformulation of the total variation as the one we obtained for the continuous case. In the rest of this section we abbreviate Z Z ess supBε (x)∩Ω u − u(x) u(x) − ess inf Bε (x)∩Ω u ϱ0 (x) dx + ϱ1 (x) dx, TVε (u) := ε ε Ω Ω where the essential supremum and infimum is taken with respect to the Lebesgue measure. For notational convenience, we denote the vector of densities by ϱ = (ϱ0 , ϱ1 ) and the vector of test functions by Ψ = (Ψ0 , Ψ1 ) ∈ P×P and define the antisymmetric pairing [Ψ; ϱ] := (Ψ0 ϱ0 )−(Ψ1 ϱ1 ) as a function from Ω × Ω to R, where (Ψi ϱi )(x, y) := Ψi (x, y)ϱi (x) for x, y ∈ Ω. Note that in the following, we shall write divε [Ψ; ϱ] in place of divε [[Ψ; ϱ]]. Theorem 4 (Dual representation of TVε ). Let Ω ⊂ RN satisfy Assumption 3.4, µ ∈ P(Ω × {0, 1}) be a probability measure and ϱi := µ( · × {i}) for i = 0, 1 the respective conditional distributions such that ϱ0 , ϱ1 ≪ λN . Then, for u ∈ L∞ (Ω) the adversarial total variation TVε admits the following representations Z Z Z TVε (u) = sup gradε [u][Ψ; ϱ] dy dx = sup − u divε [Ψ; ϱ] dy. Ψ∈P×P

Ω

Ψ∈P×P

Ω

Ω

Proof. The first equality is shown in Proposition 3.18 and the second one in Proposition 3.19. Remark 3.16 R (Connection to the C(X ) case). Let Ψ ∈ P and define a family of measures by Ψx (A) := A Ψ(x, y) dy for any x ∈ Ω. Evoking Fubini–Tonelli and the properties of Ψ we obtain that this family defines a random walk on Ω in the sense of Definition 2.8. In particular, due to the support condition of Ψ we have that Ψ = {Ψx : x ∈ Ω} ∈ M and, furthermore, using joint measurability of Ψ and the Fubini–Tonelli theorem we can express the divergence from Definition 2.12 as R R Ψ (Ω)ϱi (x) dx − Ω Ψx (A)ϱi (x) dx ϱi A x divε [Ψ](A) = ε R R R R Ψ(x, y) dyϱ (x) dx − Ω A Ψ(x, y) dyϱi (x) dx i A Ω = εR R R R Ψ(x, y) dyϱ (x) dx − Ψ(x, y)ϱi (x) dx dy i A Ω = A Ω Rε Z R Ψ(y, x) dxϱ (y) − Ψ(x, y)ϱi (x) dx i Ω Ω = dy. ε A Hence, the measure divϱε i [Ψ] has a Lebesgue density given by R R Ψ(y, x)ϱi (y) dx − Bε (y)∩Ω Ψ(x, y)ϱi (x) dx Bε (y)∩Ω = divε [Ψϱi ] y 7→ ε 30

where on the right hand side we have the divergence defined in Definition 3.14. In total, for Ψ = (Ψ0 , Ψ1 ) ∈ P × P we find a random walk Ψ ∈ M × M such that divϱε [Ψ] = divϱε 0 [Ψ0 ] − divϱε 1 [Ψ1 ] = divε [Ψ; ϱ] dλN . The definition of the nonlocal divergence is not only consistent within the two settings examined in this paper but also with its local counter part. In the next statement we show that the nonlocal definitions of gradient and divergence are consistent with their classical local counterparts under appropriate regularity assumptions on u. A Taylor expansion of the nonlocal terms recovers the classical gradient and divergence after suitable scaling.

Proposition 3.17. Let Ω ⊂ RN be a bounded domain. For u ∈ C 2 (Ω) and ϱ ∈ C 1 (Ω) we have  
1 divε ϱ · gradε [u] = div ϱ∇u + o(1) on Ωε , C N εN where CN is a constant only depending on the dimension N . Proof. For y ∈ Ωε we have Bε (y) ⊂ Ω and thus Z   1 divε ϱ · gradε [u] (y) = 2 (u(x) − u(y)) (ϱ(x) + ϱ(y)) dx. ε Bε (y) The application of Taylor’s expansion to both factors each yields   divε ϱ · gradε [u] (y) Z Z 1 2 ϱ(y) ⟨∇u(y), x − y⟩ dx + 2 ϱ(y) x − y, ∇2 u(y)(x − y) dx = 2 ε Bε (y) ε Bε (y) Z 1 + 2 ⟨∇u(y), x − y⟩ ⟨∇ϱ(y), x − y⟩ dx ε Bε (y) Z 1 1 + 2 x − y, ∇2 u(y)(x − y) ⟨∇ϱ(y), x − y⟩ dx + o(εN ) ε Bε (y) 2 =:I1 + I2 + I3 + I4 + o(εN ). A direct calulation shows that Z Z N N X X ε2 ∂ij u(y)εN +2 zi zj dx ∂ij u(y) (xi − yi )(xj − yj ) dx = I2 = ϱ(y) B1 (0) Bε (y) i,j=1 i,j=1 N X

= εN +2

2 ∂ij u(y)δij CN = εN +2 CN ∆u(y)

i,j=1

and ε2 I3 =

N X

Z Bε (y)

i,j=1 N +2

=ε

(xi − yi )(xj − yj ) dx =

∂i u(y)∂j ϱ(y)

CN

N X

N X

∂i u(y)∂j ϱ(y)εN +2

Z

i,j=1

δij ∂i u(y)∂j ϱ(y) = εN +2 CN ⟨∇u(y), ∇ϱ(y)⟩

i,j=1 N

where CN := N1+2 Γ(2πN 2)N . Furthermore, I1 = I4 = 0 and therefore 2   divε ϱ · gradε [u] (y) = εN CN (∆u(y)ϱ(y) + ∇u(y)∇ϱ(y)) + o(εN ) = εN CN div(ϱ∇u)(y) + o(εN ). Dividing by CN εN then yields the result. 31

zi zj dz B1 (0)

We now prove the two identities in Theorem 4, involving the nonlocal gradient and divergence, respectively. Applying Theorem 3 and a straightforward rearrangement similar to Proposition 2.14 leads to the first equality in Theorem 4. Proposition 3.18 (Nonlocal gradient). Under the conditions of Theorem 4 for all u ∈ L∞ (Ω) we have Z Z TVε (u) = sup gradε [u](x, y)[Ψ; ϱ](x, y) dy dx. Ψ∈P×P

Ω

Ω

Proof. Due to Theorem 3 we have   Z Z Z Z 1 1 [ess sup u − u(x)]ϱ0 (x) dx = sup Ψ(x, y)ϱ0 (x)u(y) dy dx − u(x)ϱ0 (x) dx ε Ω Bε (x)∩Ω ε Ψ∈P Ω Ω Ω Z Z  Z 1 = sup Ψ(x, y)ϱ0 (x)u(y) dy − Ψ(x, y) dy u(x)ϱ0 (x) dx Ψ∈P ε Ω Ω Ω Z Z u(y) − u(x) dy dx = sup Ψ(x, y)ϱ0 (x) ε Ψ∈P Ω Ω Z Z = sup Ψ(x, y)ϱ0 (x) gradε [u](x, y) dy dx Ψ∈P

Ω

Ω

and similarly Z  Z Z Z 1 1 [u(x) − ess inf u]ϱ1 (x) dx = u(x)ϱ1 (x) dx − inf Ψ(x, y)ϱ1 (x)u(y) dy dx Ψ∈P Ω Ω ε Ω ε Ω Bε (x)∩Ω Z  Z Z 1 = u(x)ϱ1 (x) d x + sup Ψ(x, y)ϱ1 (x)(−u(y)) dy dx ε Ω Ψ∈P Ω Ω Z Z Z 1 = sup Ψ(x, y)ϱ1 (x) dy u(x) + Ψ(x, y)ϱ1 (x)(−u(y)) dy dx Ψ∈P ε Ω Ω Ω Z Z u(x) − u(y) = sup Ψ(x, y)ϱ1 (x) dy dx ε Ψ∈P Ω Ω Z Z = sup (−Ψ(x, y))ϱ1 (x) gradε [u](x, y) dy dx. Ψ∈P

Ω

Ω

Summing both expressions and taking the supremum over (Ψ0 , Ψ1 ) ∈ P × P proves the statement. We next rewrite the gradient formulation in an integration-by-parts form to derive the nonlocal divergence. Owing to joint measurability of the test functions, we may apply the Fubini—Tonelli theorem and directly compute the solution, which exhibits the same divergence-type structure as in the continuous setting. Proposition 3.19 (Nonlocal divergence). Under the conditions of Theorem 4 for all u ∈ L∞ (Ω) and Ψ ∈ P the following identity holds true for i ∈ {0, 1}: Z Z Z (Ψϱi )(x, y) gradε [u](x, y) dy dx = − u(y) divε [Ψϱi ](y) dy. Ω

Ω

Ω

Moreover, we have Z TVε (u) =

sup Ψ∈P×P

−

u(y) divε [Ψ; ϱ] (y) dy. Ω

32

Proof. For Ψ ∈ P and i = 0, 1, due to Fubini–Tonelli and the integral constraint, we have Z Z Z Z Z Ψ(x, y) gradε [u](x, y) dyϱi (x) dx = Ψ(x, y)u(y) dyϱi (x) dx − u(x)ϱi (x) dx Ω Ω Ω ZΩ h ΩZ Z i = Ψ(x, y)ϱi (x) dx − Ψ(y, x)ϱi (y) dx u(y) dy Ω Ω Z ZΩ =− [Ψ(y, x)ϱi (y) − Ψ(x, y)ϱi (x)] dx u(y) dy. Ω

Ω

Dividing by ε and the support condition of Ψ ∈ P leads to the first equality. Applying Theorem 3 completes the proof.

3.4

Limit Characterization of the Subdifferential

Using the same arguments as in the proof of Proposition 2.18, we have that µ∗ ∈ ∂ TVε (u) for u ∈ L∞ (Ω) if and only if Z ∗ µ ∈ cl {− divε [Ψ; ϱ] : Ψ ∈ P × P} and TVε (u) = u dµ∗ Ω

where the closure is taken with respect to L∞ (Ω)∗ . However, since L∞ (Ω) is not separable, the unit ball in its dual space is not sequentially but only topologically weak-* closed. This dual space is known to be the space of all finitely additive finite signed measures on BΩ that are absolutely continuous with respect to the N -dimensional Lebesgue measure, denoted by ba(Ω, BΩ , λN ); see [35, Theorem IV.8.16]. To obtain a “sequential” characterization of the closure we need to work with nets rather than sequences, since a point belongs to the closure of a set in a topological space if and only if it is the limit of a net in the set, see [27, Theorem 2.14]. We shortly recall the definition and some properties of a net, following [27, Chapter 2.4] where a complete introduction is given. For a topological space (X, τ ) a net is a function x : D → X, where D is a directed set. This refers to a set with a reflexive transitive binary relation ⪯, called direction, which enjoys the property that each pair has an upper bound, i.e., for all x, y ∈ X there exists z ∈ X with x ⪯ z and y ⪯ z. In particular, sequences are nets where D = N. A net (xα )α∈D ⊂ X converges to some point x ∈ X if for every open neighborhood U of x there is an index α0 , dependent on U , such that xα ∈ U for all α ≥ α0 . Note that a net in the dual space X ∗ converges in the weak-* topology if and only if its dual pairing with any element in X is converging as a net in R; see the text below [27, Definition 5.90]. Proposition 3.20. Let Ω ⊂ RN satisfy Assumption 3.4, let µ ∈ P(Ω × {0, 1}) be a probability measure and ϱi := µ( · × {i}) for i = 0, 1 the respective conditional distributions such that ϱ0 , ϱ1 ≪ λN . Furthermore, let u ∈ L∞ (Ω). Then, µ∗ ∈ ∂ TVε (u) if and only if  Z  ∗ N  µ ∈ ba(Ω, BΩ , λ ), TVε (u) = u dµ∗ , and    Ω  there exists a net (Ψα )α∈D in P × P such that  Z Z     v divε [Ψα ; ϱ] dx → v dµ∗ for all v ∈ L∞ (Ω).  − Ω

Ω

Remark 3.21 (Difficulties and Conjecture). Calculating the precise form of subgradients µ∗ is delicate. In Proposition 2.18 we showed that the set under consideration was already closed, which is not true in this case, as L1 (Ω) is known not to be closed in the weak-* L∞ (Ω) topology. Furthermore, as explained above, in L∞ (Ω)∗ sequential weak-* closedness does not coincide with weak-* closedness which is why we needed to switch to the more general notion of nets instead 33

of sequences which provide the equivalence of closedness and sequential closedness even in general topological spaces as mentioned above. We conjecture that subgradients are given by nonlocal divergences of random walks that are ba measures and whose nonlocal divergence is still a ba measure, comparable to the result in Section 2. Proving this, however, is beyond the scope of this work.

4

Conclusions

In this paper, we derived dualization formulas for the nonlocal adversarial total variation functional in two different settings and characterized their respective subdifferentials. Using measure-theoretic tools, we provided a new perspective on adversarial total variation that opens new doors for the analytical and algorithmic treatment of the adversarial training problem. In particular, we obtained an integral characterization of its subgradients for the separable base space C0 (X ) as nonlocal divergences of random walks. On the larger space L∞ (Ω), we were still able to characterize the subdifferential in a limit sense. Furthermore, we showed that the nonlocal divergences appearing in both settings are consistent with each other and (as ε → 0) with local differential operators. We highlight several directions for future research based on this work: First, if one is able to properly define the dualization formula and the nonlocal divergence for separately measurable rather than jointly measurable test functions in the second setting, it should be possible to obtain a subdifferential characterization for the case of a general reference measure, thereby generalizing our present results. Second, it would be interesting to investigate to what extent our subdifferential characterizations can be further refined. This could be pursued by explicitly analyzing the weak-* closure and computing the limit points of the nets of test functions in order to obtain an integral characterization in both cases. Third, one could investigate nonlocal versions of the Anzellotti pairing [36] to derive a pointwise characterization of the subgradients similar to the one in [19]. As mentioned in the introduction, for the classical total variation Anzellotti pairings are used to define both a normal trace operator and a full trace operator, allowing the integral condition to be replaced by a pointwise trace condition, see [19]. In the spirit of transferring successful ideas originally developed for classical total variation to the nonlocal setting, this appears to be a promising direction. Lastly, an important part of the motivation for this work was to open the doors for new algorithmic approaches to solve the adversarial training problem more efficiently. As explained in the introduction, primal–dual algorithms have been successfully applied to problems with similar structure to adversarial training, however, involving the local total variation. Therefore, a natural next step is to exploit the results of this paper to develop a primal–dual algorithm for adversarial training.

Acknowledgments LB and LS acknowledge funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number 544579844 (GeoMAR) within DFG-SPP 2298 “Theoretical Foundations of Deep Learning”. Furthermore, they are grateful to the Casa Matemática Oaxaca (CMO) for hosting them during the workshop Mathematical Analysis of Adversarial Machine Learning (25w5469) in August 2025.

34

References [1]

Achim Klenke. Probability theory—a comprehensive course. Third. Universitext. Springer, Cham, [2020] ©2020, pp. xiv+716. isbn: 978-3-030-56402-5; 978-3-030-56401-8 (cit. on p. 8).

[2]

Lukas Weigand, Tim Roith, and Martin Burger. “Adversarial flows: A gradient flow characterization of adversarial attacks”. In: European Journal of Applied Mathematics (2026), pp. 1–57 (cit. on p. 2).

[3]

Lennart Siethoff. “Adversarial Training: Existence for general loss functions and asymptotics”. Provided upon request to [email protected]. MA thesis. University of Würzburg, 2025 (cit. on pp. 2, 3).

[4]

Leon Bungert, Tim Laux, and Kerrek Stinson. “A mean curvature flow arising in adversarial training”. In: J. Math. Pures Appl. (9) 192 (2024), p. 103625. issn: 0021-7824,1776-3371 (cit. on pp. 2, 3, 19, 20).

[5]

Leon Bungert and Kerrek Stinson. “Gamma-convergence of a nonlocal perimeter arising in adversarial machine learning”. In: Calculus of Variations and Partial Differential Equations 63.5 (2024), p. 114 (cit. on pp. 2, 3, 20).

[6]

Nicolás García Trillos, Matt Jacobs, and Jakwang Kim. “On the existence of solutions to adversarial training in multiclass classification”. In: European Journal of Applied Mathematics (2024), pp. 1–21 (cit. on pp. 2, 3).

[7]

Nicolás García Trillos, Matt Jacobs, Jakwang Kim, and Matthew Werenski. “An optimal transport approach for computing adversarial training lower bounds in multiclass classification”. In: Journal of machine learning research 25.393 (2024), pp. 1–45 (cit. on p. 2).

[8]

Leon Bungert, Nicolás García Trillos, and Ryan Murray. “The geometry of adversarial training in binary classification”. In: Inf. Inference 12.2 (2023), pp. 921–968. issn: 2049-8764,20498772 (cit. on pp. 2, 3, 5, 6).

[9]

Nicolás García Trillos and Matt Jacobs. “An analytical and geometric perspective on adversarial robustness”. In: Notices of the American Mathematical Society 70.08 (2023), p. 2 (cit. on p. 2).

[10]

Nicolás García Trillos, Matt Jacobs, and Jakwang Kim. “The multimarginal optimal transport formulation of adversarial multiclass classification”. In: Journal of machine learning research 24.45 (2023), pp. 1–56 (cit. on p. 2).

[11]

Andy Zou, Zifan Wang, Nicholas Carlini, Milad Nasr, J. Zico Kolter, and Matt Fredrikson. Universal and Transferable Adversarial Attacks on Aligned Language Models. 2023. arXiv: 2307.15043 [cs.CL] (cit. on p. 2).

[12]

Nicolás García Trillos and Ryan Murray. “Adversarial classification: Necessary conditions and geometric flows”. In: Journal of Machine Learning Research 23.187 (2022), pp. 1–38 (cit. on p. 2).

[13]

Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. “On the existence of the adversarial bayes classifier”. In: Advances in Neural Information Processing Systems. Vol. 34. 2021, pp. 2978–2990 (cit. on p. 2).

[14]

Jose Blanchet, Karthyek Murthy, and Viet Anh Nguyen. “Statistical analysis of Wasserstein distributionally robust estimators”. In: Tutorials in Operations Research: Emerging optimization methods and modeling techniques with applications. INFORMS, 2021, pp. 227–254 (cit. on p. 3).

[15]

Leon Bungert, Martin Burger, Antonin Chambolle, and Matteo Novaga. “Nonlinear spectral decompositions by gradient flows of one-homogeneous functionals”. In: Analysis & PDE 14.3 (2021), pp. 823–860 (cit. on p. 3). 35

[16]

José M. Mazón, Marcos Solera, and Julián Toledo. “The total variation flow in metric random walk spaces”. In: Calc. Var. Partial Differential Equations 59.1 (2020), Paper No. 29, 64. issn: 0944-2669,1432-0835 (cit. on pp. 5, 10).

[17]

Jose Blanchet, Yang Kang, and Karthyek Murthy. “Robust Wasserstein profile inference and applications to machine learning”. In: Journal of Applied Probability 56.3 (2019), pp. 830–857 (cit. on p. 3).

[18]

Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. “Towards Deep Learning Models Resistant to Adversarial Attacks”. In: Proceedings of the 6th International Conference on Learning Representations (ICLR). Conference Track Proceedings. 2018 (cit. on p. 2).

[19]

K. Bredies and M. Holler. A pointwise characterization of the subdifferential of the total variation functional. 2016. arXiv: 1609.08918 [math.FA] (cit. on pp. 3, 4, 15, 34).

[20]

Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and Harnessing Adversarial Examples. 2015. arXiv: 1412.6572 [stat.ML] (cit. on p. 2).

[21]

Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. “Intriguing Properties of Neural Networks”. In: Proceedings of the 2nd International Conference on Learning Representations (ICLR). Ed. by Yoshua Bengio and Yann LeCun. Conference Track Proceedings. 2014 (cit. on p. 2).

[22]

Antonin Chambolle and Thomas Pock. “A first-order primal-dual algorithm for convex problems with applications to imaging”. In: J. Math. Imaging Vision 40.1 (2011), pp. 120–145. issn: 0924-9907,1573-7683 (cit. on p. 4).

[23]

Erhan Çinlar. Probability and stochastics. Springer, 2011 (cit. on p. 16).

[24]

Guy Gilboa and Stanley Osher. “Nonlocal operators with applications to image processing”. In: Multiscale Modeling & Simulation 7.3 (2009), pp. 1005–1028 (cit. on p. 29).

[25]

Cédric Villani. Optimal transport. Vol. 338. Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Old and new. Springer-Verlag, Berlin, 2009, pp. xxii+973. isbn: 978-3-540-71049-3 (cit. on p. 9).

[26]

Irene Fonseca and Giovanni Leoni. Modern methods in the calculus of variations: Lp spaces. Springer Monographs in Mathematics. Springer, New York, 2007, pp. xiv+599. isbn: 978-0387-35784-3 (cit. on pp. 9, 37).

[27]

Charalambos D. Aliprantis and Kim C. Border. Infinite dimensional analysis. Third. A hitchhiker’s guide. Springer, Berlin, 2006, pp. xxii+703. isbn: 978-3-540-32696-0; 3-540-32696-0 (cit. on pp. 9–11, 33, 37, 38).

[28]

Antonin Chambolle. “An algorithm for total variation minimization and applications”. In: Journal of Mathematical imaging and vision 20.1 (2004), pp. 89–97 (cit. on p. 4).

[29]

Fuensanta Andreu, Vicent Caselles, Jesus Ildefonso Díaz, and José M Mazón. “Some qualitative properties for the total variation flow”. In: Journal of functional analysis 188.2 (2002), pp. 516–547 (cit. on p. 4).

[30]

F. Andreu, C. Ballester, V. Caselles, and J. M. Mazón. “Minimizing total variation flow”. In: Differential and Integral Equations 14.3 (2001), pp. 321–360 (cit. on p. 4).

[31]

Luigi Ambrosio, Nicola Fusco, and Diego Pallara. Functions of bounded variation and free discontinuity problems. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, 2000, pp. xviii+434. isbn: 0-19-850245-1 (cit. on pp. 3, 15, 16).

36

[32]

Ivar Ekeland and Roger Témam. Convex analysis and variational problems. English. Vol. 28. Classics in Applied Mathematics. Translated from the French. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999, pp. xiv+402. isbn: 0-89871-450-8 (cit. on pp. 4, 18).

[33]

Gerald B. Folland. Real analysis. Second. Pure and Applied Mathematics (New York). Modern techniques and their applications, A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1999, pp. xvi+386. isbn: 0-471-31716-0 (cit. on p. 21).

[34]

R. Tyrrell Rockafellar and Roger J.-B. Wets. Variational analysis. Vol. 317. Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1998, pp. xiv+733. isbn: 3-540-62772-3 (cit. on pp. 9, 37).

[35]

Nelson Dunford and Jacob T. Schwartz. Linear operators. Part I. Wiley Classics Library. General theory, With the assistance of William G. Bade and Robert G. Bartle, Reprint of the 1958 original, A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1988, pp. xiv+858. isbn: 0-471-60848-3 (cit. on pp. 5, 33).

[36]

Gabriele Anzellotti. “Pairings between measures and bounded functions and compensated compactness”. In: Annali di Matematica pura ed applicata 135.1 (1983), pp. 293–318 (cit. on pp. 3, 34). R1 R1 Wacław Sierpiński. “Sur les rapports entre l’existence des intègrales 0 f (x, y)dx, 0 f (x, y)dy R1 R1 et 0 dx 0 f (x, y)dy”. In: Fundamenta Mathematicae 1 (1920), pp. 142–147 (cit. on p. 28).

[37]

Appendix A

Adapted Measurable Maximum Theorem

The techniques used in this paper rely heavily on the theory of measurable selectors for measurable correspondences. A comprehensive introduction can be found in [26, 27, 34]. In this section, we present an adaptation of the measurable maximum theorem (see [27, Theorem 18.19]), which guarantees measurability of maximizers in certain optimization problems. The following proofs are based on the Kuratowski–Ryll-Nardzewski theorem and adapt the classical proof of the measurable maximum theorem; see again [27]. The main difficulty is to relax the assumption that correspondences are compact-valued and replace it with closed-valuedness. Compared to the classical Filippov theorem, we introduce an additional parameter δ > 0 and define a correspondence γ that maps s to all x ∈ φ(s) such that f (s, ·) is within δ of the supremum value π(s). This relaxation makes it sufficient to assume that φ is closed-valued. Lemma A.1 (Adapted Filippov’s implicit function theorem). Let (S, Σ) be a measurable space and let X be a Polish metric space. Suppose that f : S × X → R is a Carathéodory function and that φ : S ↠ X is weakly measurable with nonempty closed values. Furthermore, let δ > 0 and assume that π : S → R is measurable and that for each s ∈ S there exists an x ∈ φ(s) such that f (s, x) ≥ π(s)−δ. Additionally, assume that for each s ∈ S we have f (s, x) ≤ π(s) for all x ∈ φ(s). Then, the correspondence γ : S ↠ X, defined by γ(s) = {x ∈ φ(s) : f (s, x) ≥ π(s) − δ} is weakly measurable with nonempty and closed values. In addition to that, γ admits a measurable selector, i.e., a measurable function ξ : S → X with ξ(s) ∈ φ(s) and f (s, ξ(s)) ≥ π(s) − δ for any s ∈ S.

37

Proof. We define g : R × R → R,

g(y1 , y2 ) = |y1 − y2 |

and h : S × X → R,

h(s, x) = g(f (s, x), π(s)) = |f (s, x) − π(s)| .

Note that π and f are both Carathéodory functions and due to the continuity of g, h is jointly measurable; even a Carathéodory function. Next, for n ∈ N and n > 1δ define  Ψn : S ↠ X, Ψn (s) = x ∈ X : |f (s, x) − π(s)| < δ − n−1 . So for any s ∈ S we have   Ψn (s) = x ∈ X : h(s, x) < δ − n−1 = x ∈ X : h(s, x) ∈ (−∞, δ − n−1 ) . As h is a Carathéodory function and (−∞, δ − n−1 ) is an open subset in R, we can use that such a correspondence defined over an open set is known to be measurable, see [27, Lemma 18.7]. Note that for fixed s ∈ S we have h(s, x) < δ − n1 for any x ∈ Ψn (s) which implies that all x ∈ Ψn (s) are elements of X that fulfill π(s) − δ + n1 < f (s, x) < π(s) + δ − n1 . However, if x ∈ φ(s) then by assumption the second inequality becomes redundant as this is trivially fulfilled for all x ∈ φ(s). This implies that ! ∞ ∞ [ [ (Ψn (s) ∩ φ(s)) = φ(s) ∩ Ψn (s) . {x ∈ φ(s) : f (s, x) > π(s) − δ} = n=1

n=1

S∞

Define Ψ := n=1 Ψn as the countable union of measurable correspondences. Hence, Ψ is a measurable correspondence and thus also weakly measurable. Since by assumption φ is also weakly measurable, we have for any open set G ⊂ X that (φ ∩ Ψ)ℓ (G) = {s ∈ S : (φ(s) ∩ Ψ(s)) ∩ G ̸= ∅} = {s ∈ S : φ(s) ∩ G ̸= ∅ and Ψ(s) ∩ G ̸= ∅} = φℓ (G) ∩ Ψℓ (G) ∈ Σ which shows that φ ∩ Ψ is a weakly measurable correspondence. Note that γ = φ ∩ Ψ and the closure of a weakly measurable correspondence is weakly measurable itself. By assumption, for each s ∈ S there exists an x ∈ φ(s) such that f (s, x) ≥ π(s) − δ which implies that γ has nonempty values. Furthermore, γ(s) is closed for any s ∈ S by construction. Lastly, γ being a weakly measurable, nonempty and closed-valued correspondence from a measurable space into a Polish space, the Kuratowski–Ryll-Nardzewski selection theorem guarantees the existence of a measurable selector. Next, we show that in this setting the supremum is measurable and that approximate maximizers are measurable as well. To this end, we reformulate the problem so that the adapted Filippov theorem can be applied. Theorem 5 (Adapted measurable maximum theorem). Let X be a Polish metric space and (S, Σ) a measurable space. Let φ : S ↠ X be a weakly measurable correspondence with nonempty closed values, and suppose f : S × X → R is a Carathéodory function. Define m : S → R,

m(s) = sup f (s, x) x∈φ(s)

and for δ > 0 define µδ : S ↠ X,

µδ (s) = {x ∈ φ(s) : f (s, x) ≥ m(s) − δ} .

Then, 38

(i) m is measurable, (ii) µδ has nonempty closed values, and (iii) µδ is weakly measurable and admits a measurable selector. Proof. By assumption, φ is a weakly measurable correspondence with nonempty and closed values, so a direct implication of the Kuratowski–Ryll-Nardzewski selection theorem, sometimes known as Castaing Corollary, implies the existence of a sequence (gn )n∈N of measurable selectors from φ satisfying φ(s) = {g1 (s), g2 (s), . . .} for each s ∈ S. Define hn : S → S × X by hn (s) = (s, gn (s)). For A × B ⊂ S × X the inverse is given as −1 h−1 n (A × B) = {s ∈ S : (s, gn (s)) ∈ A × B} = A ∩ gn (B).

Hence, for any measurable rectangle A × B ∈ Σ ⊗ BX we have h−1 n (A × B) ∈ Σ which shows that hn is (Σ, Σ ⊗ BX )-measurable for each n. Since f is assumed to be a Carathéodory function, it is jointly measurable and thus f ◦ hn is Σ-measurable for each n. Since φ(s) = {g1 (s), g2 (s), . . .} and f is continuous in the second argument we have m(s) = sup f (s, x) = sup f (s, gn (s)) = sup [f ◦ hn ](s) x∈φ(s)

N

n∈

N

n∈

for any s ∈ S. The pointwise supremum of measurable functions being measurable, m is a measurable function, too, which proves (i). An application of Lemma A.1 to this setting directly yields (ii) and (iii).

39