# adversarial_classification_necessary_conditions_and_geometric_flows__1c18b83a.pdf

Journal of Machine Learning Research 23 (2022) 1-38 Submitted 3/21; Published 7/22

Adversarial Classification: Necessary Conditions and Geometric Flows

Nicol as Garc ıa Trillos garciatrillo@wisc.edu Department of Statistics University of Wisconsin Madison, Wisconsin, USA

Ryan Murray rwmurray@ncsu.edu Department of Mathematics North Carolina State University Raleigh, NC, USA

Editor: Amos Storkey

We study a version of adversarial classification where an adversary is empowered to corrupt data inputs up to some distance ε, using tools from variational analysis. In particular, we describe necessary conditions associated with the optimal classifier subject to such an adversary. Using the necessary conditions, we derive a geometric evolution equation which can be used to track the change in classification boundaries as ε varies. This evolution equation may be described as an uncoupled system of differential equations in one dimension, or as a mean curvature type equation in higher dimension. In one dimension, and under mild assumptions on the data distribution, we rigorously prove that one can use the initial value problem starting from ε = 0, which is simply the Bayes classifier, in order to solve for the global minimizer of the adversarial problem for small values of ε. In higher dimensions we provide a similar result, albeit conditional to the existence of regular solutions of the initial value problem. In the process of proving our main results we obtain a result of independent interest connecting the original adversarial problem with an optimal transport problem under no assumptions on whether classes are balanced or not. Numerical examples illustrating these ideas are also presented. Keywords: adversarial learning, classification, optimal transportation, geometric flow, differential equations, perimeter regularization

1. Introduction

In many learning settings, and in particular in the setting of deep learning, classifiers are known to behave poorly when exposed to adversarial examples. This has led to a significant body of work studying both the construction of specific adversaries and possible algorithms defending against them. Furthermore, the notion of pitting learners versus adversaries has stimulated significant new algorithms such as generative adversarial networks. One may view such adversarial frameworks as one possible notion of robustness of a learning algorithm, a critical concern in many applications. In this work we consider the problem of optimal adversarial learning and aim at connecting it with a family of geometric evolution equations. The evolution equations that we

c 2022 Nicol as Garc ıa Trillos & Ryan Murray.

License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v23/21-0222.html.

Garc ıa Trillos and Murray

derive answer the question: how would the decision boundary of a robust classifier change infinitesimally, if the adversary was to infinitesimally increase its power to perturb the data? Besides establishing new theoretical understanding for adversarial classification linking it with a set of geometric equations of surface diffusion type (similar to the ones describing the dynamics of interfaces of droplets of viscous fluids), our aim is also to explore computational alternatives to solve adversarial classification problems. At the theoretical level, a standard un-robust classification problem admits an explicit solution (i.e. the Bayes classifier), while adversarial problems typically do not have explicit solutions and in general are quite challenging from a numerical point of view. While the general perspective that we have described above can be studied in a variety of settings, here we will study a concrete model for adversarial binary classification. In particular, we assume that a binary classifier is subject to a data perturbing adversary: namely, that for any future input x Rd and associated output y {0, 1}, the adversary may select a new associated input x = x+η in order to disrupt a classifier. The adversary is assumed to possess limited power, namely that η 2 < ε, but is assumed to have knowledge of the classifier that has been chosen. A basic question is how such an adversary affects optimal classifiers. Various works have posited that adversaries do have an effect on classifiers, and that they can induce regular decision boundaries. Heuristically, from a geometric perspective this is natural, as boundaries with more surface area offer more opportunity for adversaries to disrupt classifiers. However, rigorous justification of this assertion is, to this point, unavailable. Several recent works have derived sufficient conditions for the adversarial learning problem with such an adversary. In particular, (Bhagoji et al., 2019; Pydi and Jog, 2019) both derive a duality principle related to the optimal adversarial classifier. They use this to derive bounds on the effect on the loss of such an adversary. Such a duality principle provides an embedding of the optimal adversarial classification problem as an optimal transportation problem. As mentioned earlier, despite the potential difficulty of solving the optimal adversarial classification problem for a fixed ε > 0 via optimization, we notice that the solution of the problem for ε = 0 is well-known and does not require optimization: the optimizer is the classical Bayes classifier. Namely, if we define

w0ρ0(x) = P(X dx, Y = 0), w1ρ1(x) = P(X dx, Y = 1),

then the Bayes classifier given by

( 1 if w1ρ1(x) > w0ρ0(x) 0 otherwise

is known to be a minimizer of the un-robust risk. In the one-dimensional case we expect to be able to write u0(x) = 1E for a set of the form E = K i=1[ai(0), bi(0)], where the 0 indicates that ε = 0. The central idea of this work is to derive evolution equations for the decision boundary of an optimal classifier as ε increases from zero, in the regime where we may construct optimal classifiers as a perturbation of the explicit Bayes classifier. This is achieved by deriving local necessary conditions (i.e. Euler-Lagrange type equations) for optimal adversarial classifiers for any fixed ε (4.1). In particular, in the one-dimensional case, these necessary conditions take the form of the algebraic equation

w1ρ1(bi(ε) ε) = w0ρ0(bi(ε) + ε).

Geometric flows for adversarial classification

Analogous necessary conditions are derived for the ai. These necessary conditions are then used to derive evolution equations (4.2),(4.3). In particular, in one dimension this necessary condition takes the form of a decoupled, ordinary differential equation (ODE)

dε = w0ρ 0(bi(ε) + ε) + w1ρ 1(bi(ε) ε) w0ρ 0(bi(ε) + ε) w1ρ 1(bi(ε) ε),

with an analogous equation for the ai. We remark that the resulting equation involves a sort of weak non-local algebraic condition, which in turn means the evolution equation includes a weak non-local forcing term. The evolution equation is ultimately a relatively simple decoupled ODE, which may then be solved directly using numerical solvers, with very modest computational effort and no optimization. This gives an easily computed candidate solution to the optimal adversarial classification problem for ε sufficiently close to zero. As the equations that we derive are based upon necessary conditions, a natural question is whether solutions to the ODE indeed correspond to global minimizers of the optimal adversarial classification problems. Following the duality principle derived in (Bhagoji et al., 2019; Pydi and Jog, 2019) (which we extend here to include unbalanced classes, and which holds under arbitrary metrics constraining adversarial perturbations and in arbitrary dimension), we derive the following theorem (stated informally):

Theorem 1 In one dimension, under mild technical assumptions on w0ρ0, w1ρ1 and the associated Bayes classifier, there exists an interval [0, ε0] such that the solution of the optimal adversarial classification problem is given by the solution to the decoupled differential equations (4.2),(4.3) with initial values given by the decision boundary of the Bayes classifier (when ε = 0).

Subsequently, we turn our attention to studying the problem in higher dimensions, where decision boundaries are now expressed as hyper-surfaces. For simplicity, we focus our attention on the setting where the adversarial constraints are given in terms of the standard Euclidean norm, which we denote by | |. After deriving necessary conditions, which again take the form of weakly non-local algebraic equations (6.1), we derive an evolution equation for the decision boundary as ε varies (6.4). The well-posedness of this geometric evolution equation is not immediately clear, but under the assumption that regular solutions do exist we can also prove that the solution of the evolution equation characterizes global minimizers on some interval [0, ε0], see Theorem 12. Using a Taylor expansion around ε = 0, we can also identify approximate geometric evolution dynamics which are more interpretable. In particular, we derive the evolution equation (6.5), which may be written as follows:

v(x) = ρ ν + ρ P i κi ( w1ρ1 w0ρ0) ν , (1.1)

where here v represents the normal velocity (with respect to ε) of a point on the decision boundary of the Bayes classifier, ν is the normal vector to the boundary, κi denote the principal curvatures (see the Appendix for a definition) of the boundary, and ρ = w0ρ0 + w1ρ1 = P(X dx). Conceptually, the vector field vν describes the infinitesimal change of the Bayes classifier (i.e. the minimizer of the problem when ε = 0) as the adversary increases its power. Evolution equation (1.1) takes the form of a weighted mean curvature flow plus

Garc ıa Trillos and Murray

a biasing term (the biasing term is driven by the gradient of the distribution ρ). Mean curvature flow is an important geometric flow with many convenient properties, including a comparison principle, and is known in many instances to induce significant regularity to surfaces. In particular, mean curvature flow may be seen, within an appropriate function space, as a gradient flow of the perimeter functional (in particular a flow that aims at minimizing surface area). Equation (1.1) thus suggests that as ε increases, the corresponding optimal decision boundaries become shorter and smoother, supporting previous work on the topic. In addition, at least for the unweighted case, there are powerful and efficient numerical algorithms to compute mean curvature flows (i.e. the MBO scheme given in Merriman et al. 1992).

To be more concrete about the connection between equation (1.1) and perimeter minimization problems, let us consider the family of variational problems:

min E Rd{R(1E) + εPerρ(E)} (1.2)

indexed by ε 0, where R denotes the standard average misclassification error and Perρ represents the weighted (by ρ) perimeter of the set E, which, for sets E with smooth boundary E, can be written as:

Perρ(E) := ˆ

E ρ(x)d Hd 1(x);

in the above, Hd 1 is the d 1 dimensional Hausdorffmeasure. Problem (1.2) can be interpreted as a regularized risk minimization problem over binary classifiers, where Perρ plays the role of an explicit regularizer, in this case penalizing binary classifiers when they have large decision boundaries. Problem (1.2) is relevant in the context of adversarial learning because, as we illustrate formally in Section 6.1.1, Equation (1.1) also describes the infinitesimal change of solutions to the family of problems (1.2) (indexed by ε) when starting at ε = 0 (i.e. when starting with the Bayes classifier, which is the minimizer of the risk R.) From this observation we can deduce that the instantaneous regularization effect that the adversary has on the Bayes classifier is the same as the infinitesimal regularization effect enforced by explicit perimeter regularization. This observation provides a novel geometric interpretation for the role of adversaries in binary classification: they are approximately equivalent to an explicit perimeter penalization. This line of research has been further explored by the authors in their work with Bungert, namely (Bungert et al., 2021), where they prove an equivalence between adversarial learning for binary classification and regularized risk minimization for all ε > 0 (and not just infinitesimally around ε = 0) at the expense of having to modify the notion of perimeter used to measure the size of the boundary of a set.

In summary, in this paper we take a novel approach and view an adversarial problem as an ensemble of problems indexed by a parameter controlling the ability of an adversary to perturb the data. The main motivation for doing this is to provide new theoretical insights into the role played by adversaries in the training of binary classifiers. In concrete terms, we discuss properties of the evolution equations that track solutions to an ensemble of adversarial problems, starting from an un-robust optimal classifier. These evolution equations take the form of geometric equations. For the specific adversarial model that

Geometric flows for adversarial classification

we study here the adversarial problem and its corresponding geometric evolution equations can be connected to a dual optimal transport problem, which is of interest on its own right and that extends earlier work in (Pydi and Jog, 2019) where the case of balanced labels (w0 = w1) was considered. In this paper, the connection to optimal transport is used to certify global optimality of the decision boundaries generated by the geometric flows.

The remainder of this work is organized as follows. In Section 2 we review some relevant literature. In Section 3 we describe concretely the model that we consider. In Section 3.1 we review and extend the duality principle related to the model. In Sections 4 and 5 we derive the main results in one dimension. Subsequently, Section 6 formally studies the higherdimensional case. Finally, Section 7 concludes by summarizing our work and describing a number of promising future directions.

2. Related literature

2.1 Adversarial learning

A significant body of recent work considers the problem of adversarial learning; we only aim to provide a review of the most relevant references. Early works focused on the existence of adversarial examples in deep learning (Szegedy et al., 2013; Goodfellow et al., 2014b). These examples typically involved adding carefully structured noise to images in ways that was imperceptible to humans, but which led to gross classification errors for fitted neural networks. A number of different algorithms were then developed for both constructing adversarial attacks and defending against them; these models are distinct from but related to the one we consider in this work: one influential example from this literature is (Madry et al., 2017), which established important benchmarks for both adversarial attack and defense. Several works advocate for attempting to differentiate between natural and adversarial inputs (Gong et al., 2017; Grosse et al., 2017; Metzen et al., 2017), while other works describe the ability of adversaries to circumvent such a defense (Carlini and Wagner, 2017; Athalye et al., 2018). A parallel line of work posed a construction of improved classifiers by posing a game in which adversaries and classifiers iteratively try to best one another: this is the underlying framework for generative adversarial networks (Goodfellow et al., 2014a). One work along this vein which relates closely with our work is (Moosavi-Dezfooli et al., 2019). That work observes that many boundaries obtained via robust classification are empirically observed to have smaller curvature. They then propose including a regularization term in classification that penalizes boundaries with higher curvature. Our work complements theirs in that we directly obtain a mean curvature in our d-dimensional evolution equation, indicating that the curvature indeed plays an explicit role in how decision boundaries change upon introducing stronger adversaries. While we do not explicitly prove that lower curvature is induced in our adversarial setting, the evolution equation implicitly suggests that such is the case, and a rigorous connection between these notions is a topic of current work. The fact that simple defenses were often insufficient against adversaries led to a number of theoretical works regarding the inherent difficulty of finding classifiers that are robust to adversaries. For example, (Bubeck et al., 2019) suggests that in some settings computation is the primary bottleneck in constructing adversarially robust classifiers. (Gilmer et al., 2018; Mahloujifar et al., 2019; Shafahi et al., 2018) all highlight how high dimensional

Garc ıa Trillos and Murray

geometry induces inherent limitations in the ability to avoid adversarial examples. (Ilyas et al., 2019) argues that adversarial examples are often based upon human derived notions of similarity that are incompatible with the geometry and training that occurs in deep learning. Finally, the interplay between the geometry of the types of perturbations used in measuring adversarial attacks was explored in (Khoury and Hadfield-Menell, 2018). That work demonstrated that adversarial robustness with respect to ℓ norm perturbations is not equivalent to ℓ2 norm perturbations, and that under a manifold hypothesis adversarial examples may be a consequence of the the complicated nature of high-dimensional geometry.

While the above works highlight the difficulty of completely avoiding adversarial examples, they do not study the ability of classifiers to mitigate the effects of adversarial examples. One such framework for mitigating, on average, these effects is the optimal adversarial classification problem that we study here. Several variants of this problem have been previously studied. One variant permits the adversary to perturb the distribution of (x, y) s that are inputted (Blanchet et al., 2019; Gao et al., 2017); in (Blanchet et al., 2019) a family of robust regression and classification problems are seen to be equivalent to a series of regularized risk minimization problems. A second variant, considered in both (Bhagoji et al., 2019; Pydi and Jog, 2019), studies the data perturbing adversary. In particular, those works derive a duality principle relating the optimal classification problem for balanced classes to a optimal coupling or transportation problem. (Pydi and Jog, 2019) uses Strassen s theorem from the theory of optimal transportation (Villani, 2003) to derive a duality principle, and demonstrates that minimizers of the adversarial problem may be taken to be closed sets. This may be seen as an initial step towards proving that optimal adversarial classifiers are indeed smoother than ones without adversaries. These works have focused on the sufficient conditions associated with duality principles, but to our knowledge there is no work deriving the necessary conditions associated with optimal decision boundaries of adversarially robust classifiers. Tracking the effect of a regularization parameter on optimal solutions of a statistical problem has been studied in various contexts. For example, the evolution of optimal solutions of ℓ1 regularized regression problems (i.e. Lasso) were studied in (Belloni et al., 2011). More recently, in the context of parametric adversarial learning, (Javanmard et al., 2020) studied the tradeoffbetween accuracy and adversarial robustness as a function of ε . In that work the optimal solutions admit direct representation formulas, and hence one can directly describe the evolution of the optimal classifier. In contrast, our work focuses on non-parametric classifiers, and to our knowledge no other works attempt to describe the evolution, in terms of a differential equation, of classification boundaries as a function of the adversarial power.

Finally, it is worth mentioning that other notions of classification robustness have been introduced in the literature (Wang et al., 2018). Similar questions to the ones explored in this paper can also be studied under the setting proposed in that work.

2.2 Geometric flows and PDE methods in learning

Our work also draws upon ideas from geometric evolutions, and more generally variational problems. Mean curvature flow is well-studied from a theoretical standpoint, in particular

Geometric flows for adversarial classification

as a gradient flow of the perimeter. Desirable properties of this flow, such as comparison principles, and local regularity theorems, are available in (Ecker, 2012). High fidelity numerical approximations are also available (Merriman et al., 1992). Our evolution equation is also not unrelated to non-local versions of curvature flow, which also are a topic of significant current interest (Chambolle et al., 2015).

In recent years, there has also been a growing interest in using the ideas and techniques from the analysis of interfacial flows, to construct new algorithms in data analysis. These algorithms arise as iterative schemes to solve optimization problems closely related to graphbased supervised, unsupervised, and semi-supervised learning; see (Calatroni et al., 2017; Cucuringu et al., 2019; Hu et al., 2013; Jacobs et al., 2018; Merkurjev et al., 2013, 2018; van Gennip et al., 2014) and references within.

3. Problem setup

Let ν be a Borel probability measure on Rd {0, 1} representing a data distribution for pairs (x, y) where x is a feature vector and y an associated label. Let (X, Y ) ν. We assume that the conditional distribution of X given Y = 0 takes the form ρ0dx, while the conditional distribution of X given Y = 1 equals ρ1dx, for two density functions ρ0, ρ1 that are assumed to satisfy certain regularity and non-degeneracy properties that we will make precise later on (for example see Assumptions 5 for the one-dimensional setting). We use ρdx to denote the marginal distribution of X. Notice that ρ can be expressed as

ρ = w0ρ0 + w1ρ1,

where w0 = P(Y = 0) and w1 = P(Y = 1). We let

µ(x) := P(Y = 1|X = x)

represent the conditional probability (or mean) of the label variable Y given X. Our conventional notation throughout the paper is that ρi(z + w) is always meant to denote ρi evaluated at z+w, while any multiplication of ρi by (z+w) will be denoted using ρi (z+w). We notice that as a consequence of Bayes theorem µ may be written using

µ(x) = P(Y = 1) ρ1(x)

ρ(x) = w1ρ1(x)

The classical classification problem seeks to minimize the functional

R(f) = E(ℓ(f(x), y)) = ˆ ℓ(f(x), y) dν(x, y)

over some class of functions f F. Usually, one is required to select f = 1A for some Borel set A. Of particular importance is the case when ℓ(f(x), y) = 1f(x) =y (known as the 0-1 loss), where one may actually minimize over the class of L1 functions, and where minimizers of the form 1A always exist. In particular, the function

( 1 if µ(x) 1/2 0 otherwise

Garc ıa Trillos and Murray

known as the Bayes classifier, is a minimizer to the 0-1 loss problem. In short, at least from a theoretical perspective, the optimization of the risk functional R relative to 0-1 loss admits a closed form solution. In the adversarial classification problem, one supposes an adversary that is able to modify incoming data points. In particular, in this paper we imagine that the adversary is allowed to shift any data point x with label y to a nearby point g(x, y) so that |x g(x, y)| ε. Here ε is a parameter that describes the power of the adversary: the larger the value of ε, the more the adversary can perturb the data. In this setting, one seeks to build a classifier that minimizes the robust risk

Rε(f) := sup g:supx d(g(x,y),x) ε

ˆ ℓ(f(g(x, y)), y) dν(x, y),

which factors in the action of the adversary. Notice that in the above model, the adversary can use information of a feature vector x as well as of its corresponding label y in order to decide on the new features for that data point. This model has been studied previously in (Bhagoji et al., 2019; Pydi and Jog, 2019) where interesting connections with optimal transport problems have been established. In this paper we revisit these connections and extend them. In order to analyze the minimization of the above robust risk, we first must characterize the g which achieves the maximum risk for a given f = 1A. We begin by defining the distance between a point and a set A M(Rd) via

d(x, A) := inf y A d(x, y),

where M(Rd) denotes the Borel sets of Rd. For convenience, we also define a signed distance via

( d(x, A) if x / A d(x, Ac) if x A.

The maximization problem for the adversary admits a direct representation in terms of this signed distance. In particular, we notice that for f = 1A, if | d A(x)| ε, then the adversary is free to select an arbitrary response at the point (x, y) regardless of the value of y. On the other hand, if | d A(x)| > ε the adversary is unable to modify the label f(x) by moving the inputted point by distance ε. This information may be encoded by rewriting our objective functional Rε in the form:

d A(x)< ε ℓ(1, y) dν(x, y)+ ˆ

d A(x)>ε ℓ(0, y) dν(x, y)+ ˆ

| d A(x)|<ε max z {0,1} ℓ(z, y) dν(x, y).

We notice that when ε = 0 this functional reduces to the standard, non-adversarial, loss. In order to simplify notation, we define, for any s R, the set

As := {x Rd : d A(x) s}.

Geometric flows for adversarial classification

Furthermore, in what follows we will always consider the 0-1 loss function. In that case, we may rewrite our objective function as follows:

A ε w0ρ0dx + ˆ

(Aε)c w1ρ1dx + ˆ

| d A(x)| ε ρ(x)dx

A ε w0ρ0dx + ˆ

(Aε)c w1ρ1dx + ˆ

Aε\A ε w0ρ0 + w1ρ1dx

Aε w0ρ0dx + ˆ

(A ε)c w1ρ1dx

Aε w0ρ0dx + w1 ˆ

A ε w1ρ1dx,

where we have used the fact that ρ1 is a probability distribution. We are interested in the robust classification problem: inf A M(Rd) Rε(1A). (3.1)

3.1 Duality principle and connection to an optimal transport problem

Problem (3.1) admits a strong duality theorem. To illustrate, we recall previous results in (Bhagoji et al., 2019; Pydi and Jog, 2019). In those works, they consider w0 = w1 = 1/2, in which case the robust risk minimization problem becomes

inf A M(Rd) Rε(1A) = 1

1 sup A M(Rd)

It is then shown that

sup A M(Rd)

Aε ρ0dx = inf π Γ(ρ1,ρ0)

ˆ 1d(x1,x2)>2εdπ(x1, x2) =: dε(ρ1, ρ0),

where here Γ(ρ1, ρ0) denotes the set of probability measures on Rd Rd with marginals ρ1 and ρ0 (i.e. the set of couplings or transportation plans between ρ1 and ρ0); the above result is closely connected to Strassen s theorem (see Corollary 1.28 in (Villani, 2003)). This result may be restated in the following way

inf A M(Rd) Rε(1A) = sup π Γ(ρ1,ρ0)

1 ˆ 1d(x1,x2)>2εdπ(x1, x2) .

This duality principle provides a means of certifying the optimality of solutions to the functional Rε, as is common in the context of convex optimization. Our later proofs establishing the global optimality of solutions that we construct using evolution equations will directly utilize this duality principle. Previous results in this vein focused only on the case with balanced classes: here we extend their results to the case of unbalanced classes. Indeed, the remainder of this section provides a direct generalization of the duality results given in (Bhagoji et al., 2019; Pydi and Jog, 2019).

In order to state a duality principle for more general wi, it will be convenient to define the probability measure on Rd {0, 1} given by

νS(E {1}) = ν(E {0}), νS(F {0}) = ν(F {1}).

Garc ıa Trillos and Murray

In words, νS is simply the data distribution after swapping the y labels. Using the measures ν and νS, we now state a more general duality principle that applies for arbitrary w0, w1 and not just for w0 = w1 = 1/2.

Proposition 2 Let cε : (Rd {0, 1})2 R be the cost defined by

cε(z1, z2) := 1{d(x1,x2)>2ε} {y1 =y2},

where we write zi = (xi, yi). Then,

2 sup B M(Rd)

B ε w1ρ1dx ˆ

Bε w0ρ0dx w1 + w0 = inf π Γ(ν,νS)

ˆ cε(z1, z2)dπ(z1, z2),

which is also equal to

2 sup A M(Rd)

A ε w0ρ0dx ˆ

Aε w1ρ1dx w0 + w1.

Proof We follow Theorem 1.27 in (Villani, 2003). First, by the Kantorovich duality theorem (see Theorem 1.3 in (Villani, 2003)) we have

sup φ(z1)+ψ(z2) cε(z1,z2)

ˆ φ(z1)dν(z1)+ ˆ ψ(z2)dνS(z2) = inf π Γ(ν,νS)

ˆ cε(z1, z2)dπ(z1, z2). (3.2)

where the sup is over all φ L1(ν) and ψ L1(µ) (known as Kantorovich potentials), and the inequality constraint must be interpreted for ν almost every z1 and for νS almost every z2. Let φ and ψ be two arbitrary Kantorovich potentials. Notice that if φ(z) + ψ( z) cε(z, z) then necessarily φ is (essentially) bounded above. By subtracting a constant from φ and adding this same constant to ψ, we can assume without the loss of generality that supz φ(z) = 1. Now, for a given such φ the best corresponding ψ, i.e. its dual conjugate potential, is given by φcε( z) := inf z {cε(z, z) φ(z)} .

Notice that φcε can be written as:

φcε( x, 0) = min

inf{cε(z, z) φ(z) : z = (x, 0), d(x, x > 2ε} inf{cε(z, z) φ(z) : z = (x, 0), d(x, x) 2ε} inf{cε(z, z) φ(z) : z = (x, 1)}

1 sup x:d( x,x)>2ε

φ(x, 0), sup x:d( x,x) 2ε

φ(x, 0), 1 sup x φ(x, 1)

Similarly we find that

φcε( x, 1) = min

1 sup x:d( x,x)>2ε

φ(x, 1), sup x:d( x,x) 2ε

φ(x, 1), 1 sup x φ(x, 0)

Geometric flows for adversarial classification

Since we have assumed that supz φ(z) = 1 we can deduce from the above that φcε( z) [ 1, 0]. In particular, the supremum in (3.2) can be restricted to pairs φ, ψ satisfying the cost constraint and ψ [ 1, 0]. Let us now consider an arbitrary ψ taking values in [ 1, 0] with its best associated φ:

ψcε(x, 0) := min

1 sup x:d( x,x)>2ε

ψ( x, 0), sup x:d( x,x) 2ε

ψ( x, 0), 1 sup x ψ( x, 1)

ψcε(x, 1) := min

1 sup x:d( x,x)>2ε

ψ( x, 1), sup x:d( x,x) 2ε

ψ( x, 1), 1 sup x ψ( x, 0)

Since we are only considering ψ which take non-positive values, it follows that

ψcε(x, 0) = sup x:d( x,x) 2ε

ψ( x, 0), ψcε(x, 1) = sup x:d( x,x) 2ε

which in particular implies that ψcε [0, 1]. Finally, computing the conjugate of φ := ψcε

we get φcε( x, 0) = sup x:d( x,x) 2ε

φ(x, 0), φcε( x, 1) = sup x:d( x,x) 2ε

which is then seen to take values on [ 1, 0]. Since φcε is the best ψ for a given φ [0, 1], it follows that the supremum in (3.2) is equal to

sup φ [0,1]

ˆ φ(z)dν(z) + ˆ φcε( z)dνS(z).

From the fact that for arbitrary φ [0, 1] we have φcε [ 1, 0], we deduce, using the layer cake representation (which we recall in Lemma 16 in the Appendix),

ˆ φ(z)dν(z) + ˆ φcε( z)dνS( z) = ˆ 1

ˆ 1φ(z)>sdν(z)ds ˆ 1

ˆ 1 φcε( z)>sdνS( z)ds,

ˆ 1φ(z)>sdν(z)ds ˆ 1 φcε( z)>sdνS( z) ds. (3.3)

We now rewrite the indicator function 1 φcε( z) s in terms of a 2ε-expansion of a set. Indeed, for z = ( x, 0) we have:

1{ φcε( )>s}( z) = 1 φcε( x, 0) > s

x s.t. d(x, x) 2ε and φ(x, 0) > s

x {x : φ(x, 0) > s}2ε.

Thus, 1{ φcε( )>s}( x, 0) = 1{φ( ,0)>s}2ε( x). In the exact same way we see that 1{ φcε( )>s}( x, 1) = 1{φ( ,1)>s}2ε( x). Since we are integrating over s [0, 1], we may infer that there exists s [0, 1] such that ˆ 1

ˆ 1φ(z)>sdν(z)ds ˆ 1 φcε( z)>sdνS( z) ds ˆ 1φ(z)>sdν(z)ds ˆ 1 φcε( z)>sdνS( z)

Garc ıa Trillos and Murray

= ˆ 1{φ(x,0)>s}w0ρ0(x)dx + ˆ 1{φ(x,1)>s}w1ρ1(x)dx

ˆ 1{φ(x,0)>s}2εw1ρ1(x)dx ˆ 1{φ(x,1)>s}2εw0ρ0(x)dx,

where we have used the definitions of ν and νS. The above computations, along with (3.3), allow us to conclude that:

inf π Γ(ν,νS)

ˆ cε(z1, z2)dπ(z1, z2)

= sup A M(Rd)

A2ε w1ρ1dx + sup B M(Rd)

= sup A M(Rd)

A ε w0ρ0dx ˆ

Aε w1ρ1dx + sup B M(Rd)

B ε w1ρ1dx ˆ

= sup A M(Rd)

(Ac) ε w1ρ1dx ˆ

(Ac)ε w0ρ0dx

+ sup B M(Rd)

B ε w1ρ1dx ˆ

Bε w0ρ0dx w1 + w0

= 2 sup B M(Rd)

B ε w1ρ1dx ˆ

Bε w0ρ0dx w1 + w0.

In the previous computation the step from line two to line three is the only one which does not follow directly from definitions: its justification relies upon technical measuretheoretical arguments which can be found in the appendix of (Pydi and Jog, 2019), and which we omit here for the sake of brevity. Notice that we also obtain:

= 2 sup A M(Rd)

A ε w0ρ0dx ˆ

Aε w1ρ1dx w0 + w1.

This shows our desired result.

We now translate the previous proposition, which mirrors the terminology used in describing duality in optimal transportation and linear programming, into a form which directly links the adversarial classification problem with the transportation problem from the previous proposition.

Corollary 3 1A for some A M(Rd) minimizes Rε if and only if A maximizes

sup A M(Rd)

A ε ρ1dx w0

inf A M(Rd) Rε(1A) = 1

2 inf π Γ(ν,νS) cε(z1, z2)dπ(z1, z2).

Geometric flows for adversarial classification

Proof Recall that Rε(1A) = ˆ

Aε w0ρ0dx + w1 ˆ

inf A M(Rd) Rε(1A) = w1 sup A

A ε w1ρ1dx ˆ

2 inf π Γ(ν,νS) cε(z1, z2)dπ(z1, z2)

Remark 4 Let us consider the balanced case w0 = w1 = 1/2. Since

inf A M(Rd) Rε(A) = 1

1 inf π Γ(ν,νS) cε(z1, z2)dπ(z1, z2) ,

it follows that

inf π Γ(ν,νS)

ˆ cε(z1, z2)dπ(z1, z2) = inf γ Γ(ρ0,ρ1)

ˆ 1d(x1,x2)>2εdγ(x1, x2).

4. Necessary conditions and corresponding evolution equation in one dimension

We now describe, in detail, the necessary conditions for minimizing Rε, and the evolution equation that they induce. For clarity, we begin by describing this evolution equation in the simple case where x R, under the standard metric. In this case we will be able to prove that the resulting evolution equation completely characterizes the global minimizer of Rε for small ε under mild assumptions; the formal statement and proof of this result is given in Section 5. Subsequently, in Section 6 we will turn our attention to the case where x Rd. To begin, let us assume that we may represent the boundary of the optimal set A ε in terms of two parametrized collections of points ai(ε) and bi(ε), so that A ε = K i=1[ai(ε), bi(ε)]. Here we allow a1 = and b K = + if necessary, and we notice that, as w0ρ0, w1ρ1 are both absolutely continuous (see Assumptions 5), it makes no difference whether the subintervals are open or closed. We note that this assumption will hold for ε = 0 as long as the set where w0ρ0 = w1ρ1 is a discrete set, a mild assumption. Finally, in the remainder we may suppress the dependence of ai, bi on ε, in order to decrease the notational burden. Furthermore, and following our notational convention for the ρi, any time ai, bi are followed by parentheses we always mean that the parentheses denote function evaluation: cases where multiplication is implied will be denoted by ai z. We use the convention a1 < b1 < a2 < b2 < < a K < b K. As A ε is a minimizer of Rε, we may freely perturb the boundary points (i.e. ai, bi) without increasing the energy. In particular, for |δ| small enough, if we consider the set A(δ) = (a1, b1 + δ) K i=2(ai, bi) , then since A ε is a minimizer we have that Rε(A(δ))

Garc ıa Trillos and Murray

Rε(A ε) 0. Taking δ 0 and using the fundamental theorem of Calculus then allows us to write

0 = lim δ 0 Rε(A(δ)) Rε(A ε) δ = w0ρ0(b1 + ε) w1ρ1(b1 ε).

An analogous argument for the ai and for the rest of the bi then allows us to write the necessary conditions:

w1ρ1(bi ε) = w0ρ0(bi + ε), w1ρ1(ai + ε) = w0ρ0(ai ε), (4.1)

which hold for all ai and bi that are not or + . In the remainder, if a1(0) = we set a1(ε) = for ε > 0 and likewise if b K(0) = + , then b K(ε) = + . This relates to the fact that our differential equation approach does not track potential topological changes in the decision boundaries, and is mostly focused on the case where ε is small. We remark that when ε = 0, the above necessary condition gives precisely w0ρ0 = w1ρ1, which characterizes the boundary points of the Bayes classifier. In a sense, we may view the necessary condition above as a non-local algebraic condition: namely, that the condition that w0ρ0(bi) = w1ρ1(bi) (for ε = 0) has been replaced by the non-local algebraic condition w0ρ0(bi + ε) = w1ρ1(bi ε) (for ε > 0). Using the necessary conditions (4.1), we can exactly describe the local evolution of the boundary of the set A ε for small changes in ε. In particular, let us suppose that each boundary point varies smoothly in ε, namely that we express ai(ε) and bi(ε) as smooth functions in ε. Differentiating the necessary condition and using the chain rule, we find that

w0ρ 0(bi + ε) dbi

dε + 1 w1ρ 1(bi ε) dbi

We may then solve this equation for dbi

dε = w0ρ 0(bi + ε) + w1ρ 1(bi ε) w0ρ 0(bi + ε) w1ρ 1(bi ε). (4.2)

The necessary condition for the ai is analogous:

dε = w1ρ 1(ai + ε) + w0ρ 0(ai ε) w1ρ 1(ai + ε) w0ρ 0(ai ε). (4.3)

We continue to use the convention that a1(ε) = when a1(0) = and similarly b K(ε) = + if b K(0) = + . The previous equations allow us to precisely describe (locally) the evolution of the decision boundaries using ordinary differential equations. In particular, beginning at ε = 0 with the decision boundary of the Bayes classifier, we may directly solve for the optimizer of Rε by solving a system of at most 2K decoupled differential equations. High fidelity approximations of these equations may be obtained using standard software packages. We remark that the differential equations at ε = 0 are much simpler, for example:

dε [ε = 0] = ρ (bi) w0ρ 0(bi) w1ρ 1(bi).

Geometric flows for adversarial classification

This indicates that the bi initially moves downhill in ρ, with speed dictated by the inverse of the derivative of the difference between the probability of the different classes. To determine the sign of the denominator, we notice that since w1ρ1 is assumed to be larger than w0ρ0 inside (ai(0), bi(0)), it is natural to assume that w1ρ 1(bi(0)) < w0ρ 0(bi(0)). This assumption is made explicit in Assumption 5). A similar conclusion holds for the left endpoints ai. Although the above non-local formulas are not too complicated here, the analogous approximation near ε = 0 will be more important in understanding the geometric flow induced in dimension higher than one as we will see in Section 6.

4.1 Simple example

Suppose that P(X dx|Y = 1) = φ(x)dx, where φ is the standard normal density φ(x) = 1

2π exp( x2/2), and let P(X dx|Y = 0) = φ((x 2)/2)dx

2 . Assume also that P(Y = 1) = P(Y = 0) = 1/2. Since the variances of the two Gaussians P(X dx|Y = 0) and P(X = x|Y = 1) are different, their densities must intersect at exactly two points, in this case at

2(2 + 3 log(2)) 2.57, b1(0) = 2

2(2 + 3 log(2)) 1 1.23.

The corresponding Bayes classifier for this problem is the indicator function of the set (a1(0), b1(0)). Since the solutions a1 and b1 of the ODEs (4.2) and (4.3) satisfy the necessary conditions (4.1), it follows from Theorem 2 in (Pydi and Jog, 2019) (which characterizes optimality in the Gaussian setting) that the set A ε := (a1(ε), b1(ε)) is a global solution to the adversarial robust problem (3.1) for all ε small enough. In order to provide concrete numerical values for the decision boundary as a function of ε we use a standard ODE solver in Python. The decision boundary, as well as the associated densities, are given in Figure 1. We notice that aε moves to the left, which is consistent with the fact that ρ has positive slope at a(0). Similarly, the bε moves to the right, which is consistent with the fact that ρ has negative slope at b(0). These decision boundaries required no optimization, and are provably global minimizers for small ε.

5. Global minimizers in one dimension

The evolution equations of the previous section are based upon necessary conditions for the adversarial classification problem. Since they are based upon necessary conditions, it is not immediately obvious whether or not these solutions are global minimizers of the adversarial variational problem (3.1). The goal of this section is to prove that solutions of the evolution equation are indeed global minimizers for all small enough ε, or in other words that the evolution equation locally characterizes the minimizers of the adversarial problem. In order to do so, we will require the following mild assumptions on the densities w0ρ0, w1ρ1:

Assumption 5 We make the following assumptions on the densities ρ0 and ρ1.

i) Regularity condition: ρ0, ρ1 C1(R).

Garc ıa Trillos and Murray

Figure 1: Plot of decision boundaries as ε varies for example in Section 4.1 , as well as the underlying probabilities.

ii) Non-degeneracy condition I: there are only finitely many t R for which w0ρ0(t) = w1ρ1(t) > 0.

iii) Non-degeneracy condition II: for every t R for which w0ρ0(t) = w1ρ1(t) > 0 we have w0ρ 0(t) = w1ρ 1(t).

We pause to briefly discuss these assumptions. First, we notice that the points in the boundary of the Bayes classifier will necessarily satisfy w0ρ0(t) = w1ρ1(t). Condition ii) then can be restated as requiring that the Bayes classifier be composed of finitely many intervals on the support of ρ. Condition iii), which only makes sense if we assume enough regularity, i.e. Condition i), rules out degeneracies, implying that the Bayes classifier is essentially unique. Condition iii) also implies that the Bayes classifier is stable under C1

perturbations of the ρi: in a sense, this is what is leveraged in the proof of our main result, namely Theorem 8. These conditions should be seen as relatively mild, and indeed Condition iii) ought to be generic within the class of C1 functions. For example, if we require that the ρi be given by finite mixtures of Gaussians, then these assumptions will hold for almost every choice of parameters (i.e. means and variances). Before stating the main result, we begin with a few remarks which will be important in our proof strategy.

Geometric flows for adversarial classification

Remark 6 (Global optimality via duality) Suppose that A is a measurable subset of Rd that satisfies

ˆ cε(z1, z2)dπε(z1, z2) + 1

A ε w1ρ1dx ˆ

Aε w0ρ0dx, (5.1)

for some πε Γ(ν, νS). Then, it follows from Proposition 2 that A and πε are solutions to the optimization problems in that same proposition, and by Corollary 3, A is also a minimizer of (3.1).

Remark 7 (Knott-Smith optimality criterion) According to Remark (6), to show that a given measurable set A is an optimizer for (3.1), we would need to construct a coupling πε for which (5.1) holds. Now, let A be a measurable subset of Rd, and suppose that πε Γ(ν, νS) is concentrated on the set:

{(z1, z2) (Rd {0, 1})2 : 1A ε {0}(z1) 1Aε {0}(z2)+1(Ac) ε {1}(z1) 1(Ac)ε {1}(z2) = cε(z1, z2)}.

Then, it is straightforward to check that A and πε satisfy (5.1) (with equality). The above condition for πε suggests then how mass must be exchanged between the measures ν and νS

in order to get an optimal coupling. This insight is used to build the coupling from Theorem 8 below.

We are now ready to state the main result of this section, which states that the evolution equations (4.2) and (4.3) locally characterize minimizers of the adversarial classification problem.

Theorem 8 Under Assumptions 5 on ρ0, ρ1, w0, w1, there exists ε0 > 0 such that for every ε [0, ε0] there exists a coupling πε Γ(ν, νS) satisfying:

(A ) ε ρ1dx w0

(A )ε ρ0dx = 1

ˆ cε(z1, z2)dπε(z1, z2) + 1

where A = A ε := SK i=1(ai(ε), bi(ε)) and the functions ai, bi solve the Equations (4.2) and (4.3), which we recall to be

dε = w0ρ 0(bi + ε) + w1ρ 1(bi ε) w0ρ 0(bi + ε) w1ρ 1(bi ε),

dε = w1ρ 1(ai + ε) + w0ρ 0(ai ε) w1ρ 1(ai + ε) w0ρ 0(ai ε),

with initial conditions ai(0), bi(0); here, the points ai(0), bi(0) form the decision boundary for the Bayes classifier. In particular, according to Remark 6 the set A ε induces an optimal robust classifier for ε, i.e., it is a solution to the Problem (3.1).

The proof of this result is somewhat technical, because one needs to explicitly construct the transportation plans in question. We construct these plans in several steps, which can be related to the different cases in the 0-1 cost function. The most crucial step of this construction, and the one which requires Assumption iii), involves how to construct the

Garc ıa Trillos and Murray

part of the transportation plan close to the classification boundary. This is carried out in Steps 1-3 below, and is illustrated in Figure 2. Step 4 constructs the (relatively simple) remainder of the transportation plan and wraps up the proof. Proof Let us recall that by convention we have ordered the endpoints as a1(0) < b1(0) < a2(0) < b2(0) < < a K(0) < b K(0). We can pick δ > 0 small enough so that for all i > 1 we have bi 1(0) + δ < ai(0) δ < ai(0) + δ < bi(0) δ.

For i = 1, if a1(0) is finite the same inequality applies, interpreting b0(0) := . Similarly,

ai(0) + δ < bi(0) δ < bi(0) + δ < ai+1(0) δ

for i < K, and if b K(0) < + the same inequality applies, interpreting a K+1(0) := + . We notice that the solutions of the evolution equations (4.2) and (4.3), which will possess local solutions under Assumption 5, are guaranteed to satisfy the necessary conditions (4.1). This fact will be used repeatedly below.

r+ i r+ i bi + ε bi ε

Figure 2: Illustration of mass exchange defined by γbi (middle) and by γ 1 bi (bottom).

Step 1: [Construct matching from the left of bi] Figure 2 provides a visual illustration of the particular construction that we use in our transportation plan near the

Geometric flows for adversarial classification

boundary point bi(ε). In Step 1, we are focusing on constructing the mapping involving the green mass in the plot. This mapping is constructed in such a way that the total green mass on the left and the right are equal, and so that no mass needs to travel a distance greater than 2ε. We notice that the heights at bi(ε) ε and bi(ε) + ε are equal, and so that mass travels distance exactly 2ε. The slope conditions assumed in Assumption 5, which we can show continues to hold locally near bi(0), is what allows us to infer that the rest of the green mass indeed is transported less than distance 2ε.

To begin the construction, let us fix a particular i corresponding to a finite right endpoint bi(ε) and notice that for small enough ε > 0 we have

bi(0) δ/2 bi ε < bi + ε < bi(0) + δ/2 < ai+1(0) δ,

where we recall that bi = bi(ε) (we have dropped the dependence on ε to ease the notation). Now, by Assumption 5 we know that w0ρ 0(bi(0)) = w1ρ 1(bi(0)). Given that when ε = 0 we have that A ε is the Bayes classifier, we may deduce that w0ρ0 < w1ρ1 inside (ai(0), bi(0)). Hence w0ρ 0(bi(0)) > w1ρ 1(bi(0)). Moreover, the fact that ρ0, ρ1 are C1(R) allows us to deduce that w0ρ 0(t0) > w1ρ 1(t1) (5.4)

for every t0, t1 in [bi(0) δ, bi(0) + δ] (by making δ smaller if needed). In particular, for all ε > 0 small enough we have

d ds (w0ρ0(bi + ε s)) < d

ds (w1ρ1(bi ε s)) , s (0, δ/2). (5.5)

The above condition can be combined with the necessary condition for bi in (4.1) and the fundamental theorem of Calculus to obtain

w0ρ0(bi + ε s) w1ρ1(bi ε s), s (0, δ/2), (5.6)

for all small enough ε > 0. Let r+ i (which depends on ε) be the largest number smaller than bi ε satisfying:

r+ i w1ρ1(x)dx = ˆ bi+ε

r+ i w0ρ0(x)dx. (5.7)

The existence of r+ i (at least for small enough ε) follows from (5.5) and condition (4.1), which combined also imply that r+ i satisfies bi δ/2 r+ i . On the other hand, we can see that r+ i also satisfies r+ i bi(0). Indeed, if bi ε bi(0) this is immediate. If on the other hand, bi ε > bi(0) we see that for all t [bi(0), bi ε]

t w1ρ1(x)dx < ˆ bi+ε

t w0ρ0(x)dx,

because in the interval (bi(0), bi + ε) we have w0ρ0 > w1ρ1. Therefore, r+ i bi(0) in this case too. In summary, r+ i [bi δ/2, bi(0)].

Garc ıa Trillos and Murray

Now we define the function φbi : [r+ i , bi ε] [r+ i , bi + ε] as t 7 φbi(t) where φbi(t) is the largest number in [r+ i , bi ε] which satisfies: ˆ bi ε

t w1ρ1(x)dx = ˆ bi+ε

φbi(t) w0ρ0(x)dx.

Due to inequality (5.6), φbi satisfies:

|t φbi(t)| 2ε, t [r+ i , bi ε].

The map φbi induces a measure γbi on R R given by

γbi := (Id φbi) w1ρ1

[r+ i , bi ε] ,

whose first and second marginals are the measures w1ρ1

[r+ i , bi ε] and w0ρ0

[r+ i , bi + ε] respectively; in the above denotes the push-forward operation and

the restriction of a measure to a given set. Here we recall that the push-forward of a measure µ (defined over a space Ω1) by a map F : Ω1 Ω2 is a measure on Ω2 defined by F µ(B) = µ(F 1(B)), where by F 1 is the inverse image. We also consider the inverse coupling γ 1 bi defined according to the identity γ 1 bi (D D ) := γbi(D D),

for all D, D measurable subsets of R. Step 2: [Construct matching from the right of bi] In Step 2 we are repeating the same type of construction that we did in Step 1, but to the other side of the boundary point. In terms of the illustration in Figure 2, we are now describing the transportation of the blue mass at the bottom of the figure. As in Step 1, we have to guarantee that such a mapping exists and transports mass at most distance 2ε.

To achieve this goal, we consider a symmetric construction to the one from Step 1. Using again (5.4) and combining with the necessary condition for bi in (4.1) we obtain:

w1ρ1(bi ε + s) w0ρ0(bi + ε + s), s (0, δ/2). (5.8)

We let r+ i be the smallest number larger than bi + ε that satisfies:

bi ε w1ρ1(x)dx = ˆ r+ i

bi+ε w0ρ0(x)dx.

This quantity can be shown to exist and to satisfy

r+ i [bi(0), bi + δ/2]

using similar arguments to the ones employed in Step 1 (including utilizing Assumption 5).

We let φbi : [bi ε, r+ i ] [bi + ε, r+ i ] be the function defined as t 7 φbi(t) where φbi(t) is the smallest number in [bi + ε, r+ i ] which satisfies:

bi ε w1ρ1(x)dx = ˆ φbi(t)

bi+ε w0ρ0(x)dx.

Geometric flows for adversarial classification

Inequality (5.8) implies

|t φbi(t)| 2ε, t [bi ε, r+ i ].

The map φbi induces a measure γbi on R R given by

γbi := (Id φbi) w1ρ1

[bi ε, r+ i ] ,

whose first and second marginals are the measures w1ρ1

[bi ε, r+ i ] and w0ρ0

[bi + ε, r+ i ] respectively. We also consider the inverse coupling γ 1 bi . Step 3: [Construct matchings for ai] So far we have constructed measures γbi, γ 1 bi , γbi, γ 1 bi relative to a finite right endpoint bi, but following a completely analogous scheme, and again utilizing Assumption 5, we can introduce measures γai, γ 1 ai , γai, γ 1 ai satisfying completely equivalent properties to their ai counterparts. In particular, for a finite left endpoint ai we introduce two quantities r i and r i that satisfy

r i [ai(0), ai + δ/2], r i [ai δ/2, ai(0)],

r i w1ρ1(x)dx = ˆ ai ε

r i w0ρ0(x)dx, ˆ r i

ai+ε w1ρ1(x)dx = ˆ r i

ai ε w0ρ0(x)dx.

Two maps φai : [ai + ε, r i ] [ai ε, r i ] and φai : [ r i , ai + ε] [ r i , ai ε] satisfying

|t φai(t)| 2ε, t [ai + ε, r i ], |t φai(t)| 2ε, t [ r i , ai + ε].

can be constructed. These maps induce the couplings

γai = (Id φai) w1ρ1

[ai + ε, r i ] and γai = (Id φai) w1ρ1

[ r i , ai + ε] .

Step 4:[Construct remainder of plan and compute cost] In addition to the constructions in Steps 1-3 we introduce r+ 0 = and r K+1 = + . Also, we set r 1 = r 1 = in case a1(0) = and r+ K = r+ K = + in case b K(0) = + . We now define the desired transport plan πε. Let νR 0 , νR 1 be the measures on R given by:

i=1 (w1ρ1 w0ρ0)

[r i , r+ i ]

i=1 (w0ρ0 w1ρ1)

[ r+ i 1, r i ]

+ (w0ρ0 w1ρ1)

[ r+ K, r K+1],

we notice that since [r i , r+ i ] [ai(0), bi(0)], ν0 is indeed a positive measure. Similarly, we can see that νR 1 is a positive measure too . From our construction it follows that

r+ i w0ρ0 dx = ˆ r+ i

r+ i w1ρ1 dx, ˆ r i

r i w0ρ0 dx = ˆ r i

r i w1ρ1 dx, (5.9)

Garc ıa Trillos and Murray

for all i, and hence νR 0 (R) = νR 1 (R) + w1 w0.

Let πR be any coupling between the measures

(νR 0 δ0 + νR 1 δ1), and (νR 1 δ0 + νR 0 δ1);

notice that πR is a measure on (R {0, 1})2. This is always possible using a product coupling. In the above is used to denote the product of two measures. Let π0 be the measure on (R {0, 1})2 given by:

π0(dz1, dz2) :=

i=1 (γbi(dx1, dx2) δ{0} {0}(dy1, dy2) + γ 1 bi (dx1, dx2) δ{1} {1}(dy1, dy2)

+ γbi(dx1, dx2) δ{0} {0}(dy1, dy2) + γ 1 bi (dx1, dx2) δ{1} {1}(dy1, dy2)

+ γai(dx1, dx2) δ{0} {0}(dy1, dy2) + γ 1 ai (dx1, dx2) δ{1} {1}(dy1, dy2)

+ γai(dx1, dx2) δ{0} {0}(dy1, dy2) + γ 1 ai (dx1, dx2) δ{1} {1}(dy1, dy2)).

The first and fourth terms in this expression with eight terms are the mass exchanges illustrated in Figure 2. The other terms have similar interpretations. Finally, we let πF be the measure on (R {0, 1})2 given by πF := (Id Id) (ν (π0 + πR)1), where (π0 + πR)1 is the first marginal of π0 + πR. With all the above definitions in hand, we can now introduce:

πε := π0 + πR + πF .

Here, π0 satisfies the property that for all the points in its support cε = 0. πF corresponds to the mass that is fixed and thus does not contribute to the cost of πε. Finally, πR corresponds to the remaining mass. Our construction then guarantees that ˆ cε(z1, z2)dπε(z1, z2) = ˆ cε(z1, z2)dπR(z1, z2) πR((R {0, 1})2)

= νR 0 (R) + νR 1 (R) = 2νR 0 (R) + w0 w1 = 2

r i (w1ρ1 w0ρ0)dx + w0 w1.

r i (w1ρ1 w0ρ0)dx =

ai+ε w1ρ1dx ˆ bi+ε

ai ε w0ρ0dx

(A ) ε w1ρ1dx ˆ

(A )ε w0ρ0dx,

thanks to equation (5.7) and the analogues for the ai. Thus,

ˆ cε(z1, z2)dπε(z1, z2) + 1

(A ) ε w1ρ1dx ˆ

(A )ε w0ρ0dx,

Geometric flows for adversarial classification

which thanks to Remark 6 implies that A solves the optimization problem and that the above inequality is actually an equality.

Remark 9 The construction of transportation plans in the previous proof is possible due to the necessary conditions (4.1) that are maintained by the evolution equations (4.3) and (4.2). Indeed, the necessary conditions are crucially used to prove the equalities in (5.9), which factored prominently in the construction of the certifying transportation plan πε.

Remark 10 The construction in the previous proof is local, in the sense that we can only show that solutions to our evolution equations are global minimizers for ε sufficiently small. However, the proof of the previous proposition indicates some situations where one can detect that these solutions cease to be global minimizers. For example, if at some point r+ i = r i+1 then one expects that the construction may not be continued for larger ε. This should correspond to a change in topology of the global optimizer. On the other hand, the fact that global minimizers are characterized by the differential equation implies that the topology of the minimizers does not change for small values of ε, and if one chose to track the range of values for which the constructions in the previous proof were valid (which would depend upon the difference between w0ρ 0 and w1ρ 1 and upon the C1 norms of the densities) one could quantify the range of ε for which the topology does not change.Understanding the type of degeneracies that may arise when solving the geometric evolution equations, and the associated changes in topology of the optimizers,as well as their implications to the adversarial risk minimization problem are topics of current investigation.

6. Necessary conditions and geometric evolution equations in higher dimension

In one dimension, the necessary condition allowed us to derive an ordinary differential equation that described the motion of decision boundaries as we increased the adversarial power ε. This evolution equation was driven, for small ε, by the gradient of ρ. In higher dimension the optimality conditions and their associated geometric evolution equations are necessarily more complex. In particular, the presence of curvature in higher dimensions introduces a greater degree of complexity. For clarity, throughout our study of dimension d > 1 we will restrict our attention to the standard Euclidean metric, namely we let d(x1, x2) = |x1 x2|.

To begin, we will develop some intuition about the problem by studying an explicit, radial example.

Example 1 Let us consider the case where ρ is a uniform distribution on a ball of radius 1 in Rd, and w0ρ0(x) = |x|

ωd , with ωd the Ld measure of the unit ball. Here the Bayes classifier is given by u B(x) = 1|x| 1/2. We then consider a classifier, parameterized in ε, which (by way of ansatz) is given by 1|x| r(ε), which minimizes the adversarial cost. Necessary

Garc ıa Trillos and Murray

conditions for optimality then take the form

0 = lim δ 0 Rε(r(ε) + δ) Rε(r(ε))

δ = ωdw0ρ0(r(ε) + ε) (r(ε) + ε)d 1 ωdw1ρ1(r(ε) ε) (r(ε) ε)d 1

= (r(ε) + ε) (r(ε) + ε)d 1 (1 (r(ε) ε)) (r(ε) ε)d 1,

where here we are abusing notation slightly and writing ρ1(t) and ρ0(t) to represent ρ1(x) and ρ0(x) for all x such that |x| = t, and writing Rε(s) = Rε(1|x| s).Taking a derivative in ε we obtain

d(r(ε) + ε)d 1 d

dεr + 1 = (d 1)(r(ε) ε)d 2 d(r(ε) ε)d 1 d

which may be written

dr dε = d(r(ε) + ε)d 1 + (d 1)(r(ε) ε)d 2 d(r(ε) ε)d 1

d(r(ε) + ε)d 1 ((d 1)(r(ε) ε)d 2 d(r(ε) ε)d 1) .

At ε = 0 this becomes

dr dε(ε = 0) = (d 1)rd 2

2drd 1 (d 1)rd 2 = (d 1)r 1

2d (d 1)r 1

Recalling that r 1 = κ is the mean curvature of a sphere of radius r in Rd, we immediately see the effect of curvature, namely that this evolution corresponds, at ε = 0 to a mean curvature flow that has been reweighted in the denominator by a density-dependent factor. We notice that here, ρ 0, which in the one-dimensional case dominated the evolution for small ε regimes. This example was specifically chosen in order to highlight the effect of curvature, but we will subsequently see that both curvature and ρ play a role in the surface evolution.

We remark that, in order to make the formulas explicit, we choose to work with the uniform density on the ball, which has non-smooth density. We notice that the classification boundary occurs in the region where the density is smooth, and so mollifying the density near the boundary of the ball would not materially affect the behavior of the example besides complicating the formulas for the total density.

With the previous example in mind, we derive the necessary condition, assuming that the decision boundary is sufficiently smooth.

Proposition 11 Suppose that Aε is a critical point of the problem Rε (with respect to normal variations (Maggi, 2012), further description given in the proof below) and that the signed distance function d Aε is C3 on the set | d Aε| < 2ε. For x Aε, let ν denote the outward unit normal and κi denote the principal curvatures (see the Appendix for a definition). Then the following necessary condition holds for almost every x Aε:

w1ρ1(x εν(x))

i=1 |1 κiε| w0ρ0(x + εν(x))

i=1 |1 + κiε| = 0. (6.1)

Geometric flows for adversarial classification

Proof We again recall

d A(x)< ε w0(x)ρ0(x) dx + ˆ

d A(x)>ε w1ρ1(x) dx

| d A(x)|<ε ρ(x) dx.

We consider the class of normal variations (Maggi, 2012) of the set A = Aε: that is, we consider a one parameter family of sets At of the form At = φ(t, A) for some diffeomorphism φ(t, x) which satisfies φ(0, A) = A and dφ

dt (t = 0) = F(x), where F satisfies F(x) = ν(x)ψ(x) for x A and for some smooth scalar valued function ψ that we assume, without loss of generality, satisfies ψ(x) ν(x) = 0 for all x A . Taking the derivative of Rε(1At) and evaluating it at t = 0, we obtain that

d A(y)=ε w0ρ0(y)ψ(P A(y)) d Hd 1(y) ˆ

d A(y)= ε w1ρ1(y)ψ(P A(y)) d Hd 1(y),

where here P A(x) is the projection of x onto the boundary of A, meaning the point in the boundary of A which is closest to x, whose uniqueness is guaranteed by the assumption upon the regularity of the signed distance function.

Noting that y = x εν(x) in the previous two integrals, we then use a change of variables as in Corollary 15 to convert to

w0ρ0(x + εν(x))

i=1 |1 + κi(x)ε| w1ρ1(x εν(x))

i=1 |1 κi(x)ε|

ψ(x) d Hd 1(x).

Since this holds for all smooth ψ, we then have that, for Hd 1 almost every x A

w0ρ0(x + εν(x))

i=1 |1 + κi(x)ε| w1ρ1(x εν(x))

i=1 |1 κi(x)ε|

We notice that assuming that the conditional densities ρ0, ρ1 are smooth is not sufficient to guarantee that the set of x s for which w0ρ0 w1ρ1 = 0 is smooth, as evidenced by the following basic example:

Example 2 Suppose in R2 that one places normals associated with y = +1 at (1, 1) and ( 1, 1), and then places normals associated with y = 1 at (1, 1) and ( 1, 1), with w0 = w1 = 1/2. In this case the set where w0ρ0 = w1ρ1 is given by the set {x = 0} {y = 0}, which is not smooth at (0, 0).

In Proposition 11 we notice that the necessary condition directly utilizes the normal vectors to the surface and the curvatures (which may be viewed as derivatives of the normal vectors). These notions are intimately tied with the classical Euclidean geometry: indeed if we did not have d(x1, x2) = |x1 = x2| then the previous theorem would need to be modified in order to accommodate for normal vectors and their derivatives in the appropriate geometry. Such definitions have been pursued in the context of mean curvature flow, for example in (Bellettini, 2004). However, extending those definitions to apply to the present context is beyond the scope of this work.

Garc ıa Trillos and Murray

6.1 Geometric flow

In this section we seek to formally derive a geometric flow which characterizes the evolution of the boundary of the Aε. As in the one-dimensional case, we can Taylor expand for ε small to derive an approximating geometric flow which is more transparent and easier to interpret. To begin, let us suppose that φ(ε, x) be a diffeomorphism so that φ(ε, A) = Aε. We shall utilize the necessary condition (6.1) to characterize this diffeomorphism for points x A0. We now use a chain rule on the necessary condition as follows (suppressing the dependence on x, ε, and always assuming that x A0):

w0ρ0(φ + εν(φ))

i=1 (1 + εκi(φ)) w1ρ1(φ εν(φ)

i=1 (1 εκi(φ))

i=1 (1 + εκi(φ))

w0ρ0(φ + εν(φ) d

dεφ + ν(φ) + ε d

dε(ν(φ)) + w0ρ0(φ + εν(φ)) X

κi(φ) + ε d

dεκ(φ) 1 + εκi(φ)

i=1 (1 εκi(φ))

w1ρ1(φ εν(φ) d

dεφ ν(φ) ε d

dε(ν(φ)) + w1ρ1(φ εν(φ)) X

dεκ(φ) 1 εκi(φ)

One major challenge here is that d dεν(φ) and d dεκ will involve mixed derivatives, i.e., derivatives in both ε and x. Indeed, we recall (see for example Section 17.1 in (Maggi, 2012)) that, in terms of φ and for x A0, one may express the geometric quantity ν (the outward surface normal) as

ν(φ(ε, x)) = (

xφ(ε, x)) T ν0(x)

xφ(ε, x)) T ν0(x)|

Similarly, the curvatures κi may be expressed in terms of appropriate spatial derivatives of ν, more precisely, as the non-trivial eigenvalues of the matrix ν

x; see Proposition 14 in the Appendix. Thus for ε > 0 this evolution equation is a non-local, mixed-type partial differential equation, which appears difficult to solve. However, each of the terms involving mixed derivatives is pre-multiplied by ε, and hence may plausibly be ignored for ε sufficiently small. To this end, we rearrange the previous equation d 1 Y

i=1 (1 + εκi(φ)) w1ρ1(φ + εν(φ))

i=1 (1 εκi(φ)) w0ρ0(φ εν(φ))

i=1 (1 + εκi(φ))

w1ρ1(φ + εν(φ)(ν(φ) + ε d

dεν(φ)) + w1ρ1(φ + εν(φ)) X

κi(φ) + ε d

dεκ(φ) 1 + εκi(φ)

i=1 (1 εκi(φ))

w0ρ0(φ εν(φ)(ν(φ) + ε d

dεν(φ)) + w0ρ0(φ εν(φ)) X

κi(φ) + ε d

dεκ(φ) 1 εκi(φ)

Geometric flows for adversarial classification

Evaluating at ε = 0, we find that

(w1 ρ1 w0 ρ0)dφ

If we express dφ

dε = vν, namely we consider the normal speed v, then we may write

v(x, ε = 0) = ρ ν + ρ P i κi (w1 ρ1 w0 ρ0) ν (6.5)

Here we observe two terms: one which induces motion downhill in ρ and a second which is a positively weighted mean curvature term. As we have used ν as an outwardly pointing normal vector, the P κ will correspond to the standard mean curvature flow. This indicates that heuristically, near ε = 0, the optimal adversarial classifier seeks to i) go downhill in ρ, and ii) decrease the perimeter of the decision boundary (since mean curvature flow is a type of gradient flow of perimeter; see Section 6.1.1 below.) While the reweighing in the denominator is not homogeneous, and indeed makes this heuristic description imprecise, we believe this heuristic picture is helpful for understanding the local effects induced by adversarial robustness.

Mean curvature flow, namely the case where v(x) = P i κi without any density weighting, is a fundamental geometric flow. One reference text, among many, on the topic is (Mantegazza, 2011). This geometric flow is known to be the gradient flow of the perimeter or area functional with respect to a certain function space. It is also known to induce increased smoothness in surfaces, when measured in the correct function spaces. Finally, mean curvature flow obeys a comparison principle and admits efficient numerical methods. While the flow that we have derived for the adversarial problem does not match mean curvature flow exactly, one of the terms in the approximate surface evolution at ε = 0 amounts to a scalar function times mean curvature flow, suggesting that the flow induced by the adversarial problems also may enjoy similar useful characteristics. In the next section we take this analogy one step further by deriving a variant of perimeter regularization, which matches the adversarial evolution equation to higher order.

6.1.1 Connection with explicit perimeter regularization

As mentioned at the end of the Introduction, there is a close relationship between the evolution equation derived earlier and the one that one would obtain by tracking solutions to the family of problems (1.2) indexed with ε. In what follows we elaborate on this statement. It will be convenient to write R explicitly as:

A w0ρ0(x)dx + w1 ˆ

A w1ρ1(x)dx.

First, let us derive necessary conditions for an optimal solution A to problem (1.2). We assume that A has at least C2 boundary for simplicity. Let φ be a normal variation of A as considered in Section 6.1 with the same notation used there. Then the following two

Garc ıa Trillos and Murray

relations hold:

t=0R(1At) = d

At(w0ρ0(x) w1ρ1(x))dx

A ψ(x)(w0ρ0(x) w1ρ1(x))d Hd 1(x),

t=0Perρ(At) = d

At ρ(z)d Hd 1(z)

A ρ (x + tψ(x)ν(x)) det I + tψ(x) ν(x)

A ψ(x)( ρ(x) ν(x) + ρ(x) X

i κi)d Hd 1(x).

We conclude that

R(1At) + εPerρ(At)

A ψ(x)(w0ρ0(x) w1ρ1(x) + ε( ρ(x) ν(x) + ρ(x) X

i κi))d Hd 1(x).

Since the normal variation was arbitrary, and thus the scalar function ψ was too, we deduce the necessary condition:

0 = w0ρ0(x) w1ρ1(x) + ε( ρ(x) ν(x) + ρ(x) X

i κi), x A. (6.6)

Let Aε be a solution to problem (1.2) for a given value of ε and let us assume that the family {Aε}ε>0 can be represented via a one-parameter family of diffeomorphisms {φ(ε, )}ε>0 so that φ(ε, A) = Aε, where A is the set induced by the Bayes classifier. As in Section 6.1, we now use the necessary conditions (6.6) at each point x to characterize the family of diffeomorphisms at ε = 0 and x A. Indeed, differentiating the equation

0 = w0ρ0(φ(ε, x)) w1ρ1(φ(ε, x))

+ ε( ρ(φ(ε, x)) ν(φ(ε, x)) + ρ(φ(ε, x)) X

i κi(φ(ε, x))), x A, ε 0

with respect to ε, and setting ε = 0, we deduce:

0 = (w0 ρ0(x) w1 ρ1(x)) dφ

dε (0, x) + ( ρ(x) ν(x) + ρ(x) X

i κi(x)), x A.

Expressing dφ

dε = vν(x), we obtain (6.5), i.e., the same infinitesimal change as the one coming from the original adversarial problem.

Geometric flows for adversarial classification

6.2 Global minimizers in higher dimension

Theorem 12 Suppose that the evolution equation (6.3) admits a classical solution for ε [0, ε0], in the sense that there exists a C2 diffeomorphism φ which satisfies the equation at every point x A0. Suppose, furthermore, that ρ0, ρ1 are C2 (i.e. bounded first and second derivatives) and that along the entire interface of the Bayes classifier we have

(w0 ρ0 w1 ρ1) ν c0 > 0, (6.7)

for some constant c0, where ν = ν(x) is the outer unit normal at x A0. Then for ε sufficiently small the solution to the evolution equation is also a global minimizer of the adversarial problem, where the metric determining the actions of the adversary is the Euclidean metric.

Proof To begin, we notice that, by (6.7) along with the implicit function theorem, the boundary of A0 is locally the graph of a C2 function. Classical geometric results imply that for any point x in a δ neighborhood of A0 there exists a unique closest point P A0( x) in the boundary of A0, and that the signed distance function is C3 in that same δ neighborhood of A0.

Under the assumption that φ is C2, the chain rule computation shown in Section 6.1, along with the fact that A0 is the Bayes classifier, implies that the necessary condition (6.2) is satisfied at every point in the boundary of Aε, namely for every x Aε

w0ρ0(x + εν(x))

i=1 |1 + κi(x)ε| w1ρ1(x εν(x))

i=1 |1 κi(x)ε|

Next we notice that we may express points within the δ neighborhood of A0, using what is called a normal coordinate system. In particular, for any x in that neighborhood, we may (uniquely) represent x = P A0( x) + d A0( x)ν(P( x)). This essentially allows us to locally transform from points in a neighborhood of the boundary into flattened geometry. We note that, since φ is C2 and starts as the identity mapping, the set Aε also has boundary which is the graph of a C2 function and admits local normal boundary coordinates, for ε sufficiently small, and for a δ neighborhood of the boundary of Aε which is independent of ε. From this point on we will always assume that ε is small enough that this representation is possible. Our goal now will be to construct a transportation plan which certifies the optimality of the set Aε. In doing so, as in the one-dimensional proof, it suffices to construct mappings locally near the boundary which transfer mass from ρ0 to ρ1 (and vice versa), and which move mass at most 2ε distance. As we will see, our construction reduces the problem almost entirely to the one-dimensional setting.

In particular, fix x0 A0 let z0 = φ(ε, x0), and consider points of the form z0+tν(z0) = z(t, z0), for t ( δ, δ). After changing variables (to be precise, in the boundary normal coordinates associated with Aε), the density associated with a particular t for fixed z0 is given by

ρi(t|z0) := ρi(z(t, z0))

i=1 |1 + tκi(z0)|.

Garc ıa Trillos and Murray

More precisely, using the coarea formula (Evans and Gariepy, 2015) and Corollary 15 in the Appendix, we can write

| d Aε(z)| δ g(z)ρi(z)dz = ˆ δ

d Aε(z)=s g(z)ρi(z)d Hd 1(z)

Aε g(z(t, z0))ρi(z(t, z0))

i=1 |1 + tκi(z0)|d Hd 1(z)

δ g(z(t, z0)) ρi(t|z0)dtd Hd 1(z),

for arbitrary smooth and bounded test function g. This provides a representation of the distribution ρidx restricted to the set {| d Aε(z)| δ} in normal coordinates, and in particular, up to rescaling, we can now interpret the function ρi( |z0) as the conditional distribution of t [ δ, δ] given z0. Now for any fixed ε and x0 (i.e. fixed z0 = φ(ε, x0)) we will construct a transportation plan using ρ( |z0): in the original high-dimensional problem this means that in the set {| d Aε(z)| δ}, our transportation plan only transports along rays normal to the boundary of Aε. Notice that outside of {| d Aε(z)| δ}, on the other hand, we may transport in any way we want so as to match the marginal constraints (just as in the 1d setting): this is why we focus on the set {| d Aε(z)| δ} exclusively. By the necessary condition (6.2) we have the necessary matching condition, namely that w0 ρ0( ε|z0) = w1 ρ1(ε|z0). All that remains is to verify that we can transport w0 ρ0( |z0) on the interval [ ε, ε] on to w1 ρ1( |z0) without moving more than distance 2ε in t. To this end, we notice that, by the assumption (6.7), |(w1 ρ1( x) w0 ρ0( x )) ν(x0)| > c0/2 > 0 for all x, x in a neighborhood of x0 A0. Using the fact that φ is C2 and that is the identity for ε = 0, then implies that the same inequality, with constant c0/4 holds in a neighborhood of φ(x0, ε), for small enough ε, and for the size of the neighborhood independent of ε. We may then compute

w1 ρ 1(t1|z0) w0 ρ 0(t0|z0) = (w1 ρ1(z(t1, z0)) w0 ρ0(z(t0, z0))) ν(z0)

+ w1ρ1(z(t1, z0)) X

j =i |1 + t1κj(z0)|

w0ρ0(z(t0, z0)) X

j =i |1 + t0κj(z0)|.

The first of these terms is bounded from below by c0/4. Recalling that w0ρ0(x0) = w1ρ1(x0) (as A0 is a Bayes classifier), we may bound the magnitude of the remaining terms by |ti|(1 + δ): in particular, if ti is of order ε ( notice that κi is uniformly bounded since φ was assumed C2) then we may conclude that w1 ρ 1(t1|z0) w0 ρ 0(t0|z0) > c0/8 for small enough ε. This then allows us to directly use the one-dimensional construction from the proof of Theorem 8 in order to construct appropriate transportation plans for the ρ( |z0). By constructing such a plan along normal rays corresponding to every z0 Aε, we then have a candidate transportation plan, which transports points near the boundary at most distance 2ε. Using the same argument via the fundamental theorem of calculus and the

Geometric flows for adversarial classification

Figure 3: The contours of the function w1ρ1 w0ρ0 for the example in Section 6.3. The contour corresponding to w1ρ1 w0ρ0 = 0 is the s-shaped curve, and represents the decision boundary for the Bayes classifier.

duality principle as in the proof of Theorem 8, we obtain the desired result.

Remark 13 In the previous proof we assumed that the solutions to the partial differential equation existed. We suspect that the local existence and uniqueness of solutions can be proved by an appropriate non-linear PDE argument under the assumption (6.7), but the technical details of such a proof lie outside of the scope of this paper. We also notice that the same conclusions about topology which we indicated in one dimension would also hold in the setting of Theorem 12. Indeed, minimizers will not change their topology for sufficiently small ε, the size of which should depend upon the size of c0 in (6.7) and upon the smoothness of the underlying densities. Of course the topologies are potentially much more complicated in higher dimension, and the evolution of the topology of the minimizing classifiers is an intriguing potential future direction.

6.3 Illustration in two dimensions

Here we show a basic numerical example of the geometric evolution (6.5) in two dimensions. This example is intended to be an illustration, rather than a detailed computational study. Such a study would require careful numerical analysis, which lies outside of the scope of this work. We consider two different classes ρ1 N(( .5, 2), Σ) + N(( .5, .5), Σ) and ρ2 N((.5, .5), Σ) + N((.5, 2), Σ, where Σ = .2I, and w0 = w1 = .5. The Bayes classifier boundary, along with contours of the misclassification error w1ρ1 w0ρ0 are shown in Figure 3.

Garc ıa Trillos and Murray

We then use a modified version of the scheme from (Merriman et al., 1992) to track the evolution of the decision boundary under the evolution equation (6.5) for different values of ε. These curves are displayed in Figure 4, next to the curves evolved via standard mean curvature flow as a point of reference.

7. Conclusion

This work provides a first analysis of the evolution equations associated with an ensemble of adversarial classification problems. In particular, we have shown that for the model considered here, the evolution equations in one dimension are completely able to characterize the global minimizer for small enough ε (the power level of the adversary) without needing to conduct any optimization. In higher dimension the same evolution equations are linked with mean curvature flow and allude to implicit regularization. This work suggests many promising future directions, both in terms of analysis and implementation. We list a few here, some of which are the topic of current investigation.

i) In this work, the connection between the evolution equations and global minimizers only holds for small ε, and we made no attempt to quantify the size of ε0 in our theorem. This is partly unavoidable given the generality of the input distributions and the learned classifiers. We expect that the results in our paper should hold locally in ε, in the sense that if the adversarial problem admits a unique solution at ε then the solution of the adversarial problem should be characterized by the evolution equation in a neighborhood of ε. We do not expect the theorem to generally hold for large ranges of ε, as topological changes can cause non-uniqueness of optimal solutions for certain (likely discrete) values of ε. It may be possible to use primal-dual methods to numerically detect when topological changes occur, or, in other words, in what ranges of ε the evolution equations describe optimal solution families. Investigating such methods could provide a lot more information about how large ε may be in our theorems.

ii) In higher dimensions, we made the additional assumption that the evolution equations admitted smooth solutions. Justifying this assumption would likely require careful analysis of the partial differential equation. Similarly, it would be interesting to develop more efficient numerical methods for the actual evolution equation in higher-dimensional settings.

iii) The smoothness of minimizers, and whether curvature is implicitly bounded, is a natural question. This is not obvious, as the objective functional of the adversarial problem does not impose a priori regularity. Similarly, the evolution of singularities (and whether they may disappear or appear) is completely unclear.

iv) Various notions of distance have been used in studying adversarial examples. Notable examples include the ℓ distance. The effect of such a distance on the evolution equations that we describe in this work is an interesting question to study.

v) The problem of a data perturbing adversary for multiple labels, and the resulting evolution equations, is also a compelling, open problem.

Geometric flows for adversarial classification

Figure 4: The first set of curves represent the evolution of the decision boundary according to the geometric evolution (6.5), which includes a weighted curvature flow and a drift term. The second set of curves is the geometric evolution following standard mean curvature flow. In this case the curves are largely the same, with only a very small damping of the curvature flow in the first case (which makes sense since ρ is of modest size in this example).

Garc ıa Trillos and Murray

vi) Finally, here we have considered one specific example of adversarial classification model, but many others are possible. Likewise, we have restricted our attention to the classification problem with 0-1 loss, while one may also study other settings like regression under different loss functions. Exploring other settings and studying their connection to other geometric flows is a promising direction of research that we hope to explore. Our hope is to provide deeper insights into the properties of different robust learning methodologies.

Acknowledgments

NGT was supported by NSF grant DMS 2005797

Appendix A. Properties of the signed distance function

We recall the definition of the signed distance function

( d(x, E) if x E d(x, Ec) for x E

The following properties are classical and may be found in, for example, (Ambrosio and Mantegazza, 1998):

Proposition 14 Let E be an open set with C2 boundary. Then on some neighborhood U of E we have the following:

Each y in U has a unique closest point P(y) in E, and P is a continuous function in y.

We have, for y / E, that d = P(y) y

d(Y ) . For y E the outward unit normal is

given by ν(y) = d(y).

For y E, the matrix D2 d = ν

x has 1 eigenvalue that is equal to zero (with eigenvector in the normal direction ν), and d 1 eigenvalues with eigenvectors spanning the tangent directions. These eigenvalues are called the principal curvatures of the surface, and are denoted κi.

The principal curvatures of a surface may be viewed as inverses of the principal radii. The principal radii grow (or shrink depending on their sign) linearly in their distance from E. By using these facts and applying a classical change of variables to the transformation T(x) = x + εν(x), we obtain the following formula:

Corollary 15 If E is a C2 surface then for ε sufficiently small ˆ

d A(y)=ε g(y) d Hd 1(y) = ˆ

d A(x)=0 g(x + εν(x))

i=1 |1 + εκi(x)| d Hd 1(x).

Geometric flows for adversarial classification

The following lemma, sometimes called the layer cake representation , is a classical lemma from measure theory (see for example Chapter 1 in (Lieb and Loss, 2001)), and may be directly proved by using the Fubini-Tonelli theorem.

Lemma 16 Given a non-negative function f on a measure space (X, µ) the following identity holds: ˆ

X f(x) dµ(x) = ˆ

0 µ({x : f(x) > t}) dt.

Luigi Ambrosio and Carlo Mantegazza. Curvature and distance function from a manifold. The Journal of Geometric Analysis, 8(5):723 748, 1998.

Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. ar Xiv preprint ar Xiv:1802.00420, 2018.

Giovanni Bellettini. Anisotropic and crystalline mean curvature flow. A sampler of Riemann-Finsler geometry, 50:49 82, 2004.

A. Belloni, V. Chernozhukov, and L. Wang. Square-root lasso: pivotal recovery of sparse signals via conic programming. Biometrika, 98(4):791 806, 2011. ISSN 00063444, 14643510. URL http://www.jstor.org/stable/23076172.

Arjun Nitin Bhagoji, Daniel Cullina, and Prateek Mittal. Lower bounds on adversarial robustness from optimal transport. In Advances in Neural Information Processing Systems, pages 7498 7510, 2019.

Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust Wasserstein profile inference and applications to machine learning. Journal of Applied Probability, 56(3):830 857, 2019.

S ebastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. Adversarial examples from computational constraints. In International Conference on Machine Learning, pages 831 840, 2019.

Leon Bungert, Nicol as Garc ıa Trillos, and Ryan Murray. The geometry of adversarial training in binary classification. ar Xiv preprint ar Xiv:2111.13613, 2021.

Luca Calatroni, Yves van Gennip, Carola-Bibiane Sch onlieb, Hannah M. Rowland, and Arjuna Flenner. Graph clustering, variational image segmentation methods and hough transform scale detection for object measurement in images. Journal of Mathematical Imaging and Vision, 57(2):269 291, 2017. doi: 10.1007/s10851-016-0678-0. URL https: //doi.org/10.1007/s10851-016-0678-0.

Nicholas Carlini and David Wagner. Adversarial examples are not easily detected: Bypassing ten detection methods. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 3 14, 2017.

Garc ıa Trillos and Murray

Antonin Chambolle, Massimiliano Morini, and Marcello Ponsiglione. Nonlocal curvature flows. Archive for Rational Mechanics and Analysis, 218(3):1263 1329, 2015.

Mihai Cucuringu, Andrea Pizzoferrato, and Yves van Gennip. An MBO scheme for clustering and semi-supervised clustering of signed networks, 2019.

Klaus Ecker. Regularity theory for mean curvature flow, volume 57. Springer Science & Business Media, 2012.

Lawrence Craig Evans and Ronald F Gariepy. Measure theory and fine properties of functions. Chapman and Hall/CRC, 2015.

Rui Gao, Xi Chen, and Anton J Kleywegt. Wasserstein distributional robustness and regularization in statistical learning. ar Xiv preprint ar Xiv:1712.06050, 2017.

Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian Goodfellow. Adversarial spheres. ar Xiv preprint ar Xiv:1801.02774, 2018.

Zhitao Gong, Wenlu Wang, and Wei-Shinn Ku. Adversarial and clean data are not twins. ar Xiv preprint ar Xiv:1704.04960, 2017.

Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672 2680, 2014a.

Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. ar Xiv preprint ar Xiv:1412.6572, 2014b.

Kathrin Grosse, Praveen Manoharan, Nicolas Papernot, Michael Backes, and Patrick Mc Daniel. On the (statistical) detection of adversarial examples. ar Xiv preprint ar Xiv:1702.06280, 2017.

Huiyi Hu, Thomas Laurent, Mason A. Porter, and Andrea L. Bertozzi. A method based on total variation for network modularity optimization using the MBO scheme. SIAM Journal on Applied Mathematics, 73(6):2224 2246, 2013. doi: 10.1137/130917387. URL https://doi.org/10.1137/130917387.

Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. In Advances in Neural Information Processing Systems, pages 125 136, 2019.

Matt Jacobs, Ekaterina Merkurjev, and Selim Esedo glu. Auction dynamics: A volume constrained MBO scheme. Journal of Computational Physics, 354:288 310, 2018. ISSN 0021-9991. doi: https://doi.org/10.1016/j.jcp.2017.10.036. URL http: //www.sciencedirect.com/science/article/pii/S0021999117308033.

Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoffs in adversarial training for linear regression. In Conference on Learning Theory, pages 2034 2078. PMLR, 2020.

Geometric flows for adversarial classification

Marc Khoury and Dylan Hadfield-Menell. On the geometry of adversarial examples. ar Xiv preprint ar Xiv:1811.00525, 2018.

Elliott H Lieb and Michael Loss. Analysis, volume 14. American Mathematical Soc., 2001.

Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. ar Xiv preprint ar Xiv:1706.06083, 2017.

Francesco Maggi. Sets of finite perimeter and geometric variational problems, volume 135 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2012. ISBN 978-1-107-02103-7. doi: 10.1017/CBO9781139108133. URL https://doi. org/10.1017/CBO9781139108133. An introduction to geometric measure theory.

Saeed Mahloujifar, Dimitrios I Diochnos, and Mohammad Mahmoody. The curse of concentration in robust learning: Evasion and poisoning attacks from concentration of measure. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4536 4543, 2019.

Carlo Mantegazza. Lecture notes on mean curvature flow, volume 290. Springer Science & Business Media, 2011.

Ekaterina Merkurjev, Tijana Kosti c, and Andrea L. Bertozzi. An MBO scheme on graphs for classification and image processing. SIAM Journal on Imaging Sciences, 6(4):1903 1930, 2013. doi: 10.1137/120886935. URL https://doi.org/10.1137/120886935.

Ekatherina Merkurjev, A. Bertozzi, and F. Chung. A semi-supervised heat kernel pagerank MBO algorithm for data classification. Communications in Mathematical Sciences, 16: 1241 1265, 2018.

Barry Merriman, James Kenyard Bence, and Stanley Osher. Diffusion generated motion by mean curvature. Department of Mathematics, University of California, Los Angeles, 1992.

Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff. On detecting adversarial perturbations. ar Xiv preprint ar Xiv:1702.04267, 2017.

Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9078 9086, 2019.

Muni Sreenivas Pydi and Varun Jog. Adversarial risk via optimal transport and optimal couplings. ar Xiv preprint ar Xiv:1912.02794, 2019.

Ali Shafahi, W Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? ar Xiv preprint ar Xiv:1809.02104, 2018.

Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. ar Xiv preprint ar Xiv:1312.6199, 2013.

Garc ıa Trillos and Murray

Yves van Gennip, Nestor Guillen, Braxton Osting, and Andrea L. Bertozzi. Mean curvature, threshold dynamics, and phase field theory on finite graphs. Milan Journal of Mathematics, 82(1):3 65, 2014. doi: 10.1007/s00032-014-0216-8. URL https: //doi.org/10.1007/s00032-014-0216-8.

Cedric Villani. Topics in Optimal Transportation. Graduate Studies in Mathematics. American Mathematical Society, 2003. ISBN 9780821833124. URL http://books.google. com/books?id=q6ky E2Zkxrc C.

Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighbors to adversarial examples. volume 80 of Proceedings of Machine Learning Research, pages 5133 5142, Stockholmsm assan, Stockholm Sweden, 10 15 Jul 2018. PMLR. URL http://proceedings.mlr.press/v80/wang18c.html.