Title: LEARNING ADVERSARIAL EXAMPLES WITH RIEMAN-NIAN GEOMETRY

Abstract: Adversarial examples, referred to as augmented data points generated by imperceptible perturbation of input samples, have recently drawn much attention. Wellcrafted adversarial examples may even mislead state-of-the-art deep models to make wrong predictions easily. To alleviate this problem, many studies focus on investigating how adversarial examples can be generated and/or resisted. All the existing work handles this problem in the Euclidean space, which may however be unable to describe data geometry. In this paper, we propose a generalized framework that addresses the learning problem of adversarial examples with Riemannian geometry. Specifically, we define the local coordinate systems on Riemannian manifold, develop a novel model called Adversarial Training with Riemannian Manifold, and design a series of theory that manages to learn the adversarial examples in the Riemannian space feasibly and efficiently. The proposed work is important in that (1) it is a generalized learning methodology since Riemmanian manifold space would be degraded to the Euclidean space in a special case; (2) it is the first work to tackle the adversarial example problem tractably through the perspective of geometry; (3) from the perspective of geometry, our method leads to the steepest direction of the loss function. We also provide a series of theory showing that our proposed method can truly find the decent direction for the loss function with a comparable computational time against traditional adversarial methods. Finally, the proposed framework demonstrates superior performance to the traditional counterpart methods on benchmark data including MNIST, CIFAR-10 and SVHN.

1. INTRODUCTION:

Recently Deep Neural Networks (DNN) achieve a big success on a wide range of challengeable tasks, such as image classification, speech recognition, and object detection (LeCun et al., 2015) (He et al., 2017) . However, recent studies have found that DNNs can be easily fooled by some special input called adversarial examples which are referred to as augmented data points generated by imperceptible perturbation of input samples (Szegedy et al., 2013) (Biggio et al., 2013) (Nguyen et al., 2015) . Although such perturbation is visually imperceptible, it can lead DNNs to make incorrect predictions with high confidence.

There have been a lot of proposals studying how to generate more powerful adversarial examples, and how to build up robust networks to defend them (Goodfellow et al., 2014) (Szegedy et al., 2013) . This interesting problem was first studied in (Liu & Nocedal, 1989) where the authors proposed a simple way to produce adversarial examples with L-BFGS optimization. A more powerful approach Fast Gradient Sign Method (FGSM) is later proposed in (Goodfellow et al., 2014) and further extended to a more general case with l p constraint for perturbation (Lyu et al., 2015) (Shaham et al., 2015) . The multi-step variant FGSM k was proposed in (Kurakin et al., 2016) which is essentially projected gradient decent (PGD) on the negative loss. Aside from studying how to generate adversarial examples, some researchers developed methods to defend them. The adversarial training was proposed by (Goodfellow et al., 2014) (Lyu et al., 2015) which augmented the training set with adversarial examples. This method not only increases the model robustness for adversarial examples but also improves the generalization for benign samples. Some feature squeezing (Xu et al., 2017) and defensive distillation (Papernot et al., 2016) were also exploited to resist adversarial attacking. Semisupervised version of adversarial training was developed in (Miyato et al., 2015) (Miyato et al., 2018) (Miyato et al., 2016) called Virtual Adversarial Training (VAT) , where the output distribution was smoothed by penalizing the KL-divergence between outputs of original and adversarial examples. Moreover, some researchers provided the theory and principles for adversarial examples (Fawzi et al., 2016) . Furthermore, (Ma et al., 2018) have demonstrated that the adversarial examples are a dense region of pixel space instead of isolated points.

All these existing adversarial training methods simply consider the adversarial example problem in the Euclidean space with the orthogonal coordinate system. Specifically, this traditional adversarial training methods aim to solve a robust optimization problem (Lyu et al., 2015) :

min θ E (x,y) D [max ϵ L(x + ϵ, y, θ)] s.t. ∥ϵ∥ p ≤ σ (1)

where L denotes a loss function and the pair of input and label (x, y) is assumed to be drawn from the data distribution D. The robust optimization problem is defined as a min-max problem with respect to the worst perturbation ϵ and the best model parameters θ. The adversarial perturbation ϵ is restricted within l p -ball around benign example x. The FGSM can be seen as a special case with p = ∞. Such restriction is defined in Euclidean space and the similarity between two points is measured by Minkowski distance. However, data points may be in practice attached on a geometric manifold which cannot be appropriately described with Euclidean coordinate system. In this case, the Euclidean metric would be not rational. Moreover, existing adversarial training methods usually search the worst perturbation through the gradient of loss function with respect to x, since the gradient is considered as the steepest direction. However, in a geometric manifold, particularly in Riemannian space, the gradient of a loss function unnecessarily presents the steepest direction. Figure 1 illustrates the difference between a Riemannian space and the Euclidean space, where the detailed mathematic notation can be seen in Section 2. Clearly, In this figure, assuming that the data are attached in the manifold as defined in Figure 1 (a), the Euclidean distance may not appropriately reflect the true distance between two points (e.g., ξ(0) and ξ(a)).

In this paper, we extend the traditional adversarial problem to Riemannian space and propose a novel adversarial method called Adversarial Training with Riemannian Manifold (ATRM). ATRM is regarded as a generalized framework in that Riemannian space contains the Euclidean space as a special case. In more details, we start with defining the local coordinate system and Riemannian metric tensor to evaluate the similarity between two points in Riemannian space. We then propose to restrict the adversarial perturbation within l p -ball around natural examples x on Riemannian manifold, and develop a framework to search the worst perturbation through the generalized trust region method. Our proposed method is to solve the adversarial problem from the perspective of geometry which is similar to Natural Gradient methods (Amari, 1998) , however, our method is implemented on input space instead of parameter space of DNNs.

We list the main contributions of this paper as follows: 1) To our best knowledge, this is the first work to tackle the adversarial example problem through the perspective of geometry. 2) We study the adversarial example in the more generalized Riemannian space of which Euclidean space is a special case. 3) Our method considers the curvature information of the loss function which can be viewed as the second order method, enabling a more accurate direction of adversarial perturbation. Importantly, from the perspective of geometry, our method leads to the steepest direction of loss function in Riemannian space. 4) We also provide a series of theory showing that our proposed method can truly find the decent direction for the loss function with a comparable computational time against traditional adversarial method (one more backward backward prorogation).

2. MAIN METHODOLOGY:

In this section, we first study how to generate adversarial examples within l 2 -ball in Riemannian Manifold. We then define the local metric tensor on the manifold and generate the adversarial examples using our proposed ATRM with l 2 -ball restriction. Next, we extend our proposed method to l p -ball restriction on Riemannian manifold. Finally, we propose the adversarial training method called ATRM and also provide theories showing that ATRM can find the decent direction of the loss.

2.1. RIEMANNIAN GEOMETRY:

In this subsection, we first introduce the mathematical notations and some background of geometry. 

l = ∫ a 0 √ g ij (t) ξi (t) ξj (t) dt (2)

where g ij (t) denotes the metric tensor at point ξ(t).

The geodesic can be calculated with Theorem 2.1, which measures the distance of two points on Riemannian manifold. It can be seen as an extension of the Euclidian distance in Euclidian space. Lemma 2.2. Let ξ(0) and ξ(a) be two close points on Riemannian manifold, where ξ(t) is a shortest curve connecting these two points. Then, the distance between these two points can be computed by:

ds 2 = g ij (t)dθ i dθ j (3)

where dθ i = ξ(t) i dt is the i th component of small vector dθ and g ij (t) is the metric tensor (proof can be seen in Appendix D).

We can also rewrite ds 2 in form of inner production:

ds 2 = ⟨dθ i e i , dθ j e j ⟩ = ⟨e i , e j ⟩dθ i dθ j (4)

where basis vectors {e i } is the set of tangent vectors along the coordinate curves. Combining these two equations, we have:

g ij = ⟨e i , e j ⟩ (5)

Therefore, the metric tensor G = (g ij ) is the inner product of basis vectors. In the case of Euclidean space (orthonormal coordinate system), the metric tensor is:

g ij = δ ij = { 1 i=j 0 otherwise (6)

where δ ij represents the Kronecker delta. The Euclidean space can be viewed as a special case of Riemannian space with the identity metric tensor. For traditional adversarial training, the data are assumed to be in Euclidean space with the identity metric tensor. In this paper, we consider a more general case that the data are attached on the Riemannian manifold with positive definite metric tensor varying smoothly on the manifold. Figure 1 illustrates the difference between the two spaces.

2.2. ADVERSARIAL PERTURBATION WITHIN l 2 -BALL ON MANIFOLD:

In this subsection, we introduce in details how we exploit a generalized trust region method to search the adversarial perturbation on the Riemannian manifold.

To search the adversarial examples on the Riemannian manifold feasibly, we propose to solve the inner optimization problem of (1) with the generalized trust region method:

ϵ = arg max ϵ T k {L, x, ϵ} s.t. d(x, x + ϵ) ≤ σ (7)

where ϵ is a small perturbation and σ is a small value. T k {L, x, ϵ} denotes the k th order Taylor expansion of function L(.) around x evaluated at x + ϵ. Here k can be set to 1 or 2. d(x, x + ϵ) represents the distance between two points x and x + ϵ. In this paper, we follow the setting of previous research (Lyu et al., 2015 ) (Shaham et al., 2015) and provide the 1 th Taylor expansion for the loss function L(.). We define the d(.) geodesic distance between two points on Riemannian manifold. Since the perturbation ϵ is very small, by applying Lemma 2.2, ( 7) can be reformulated as:

EQUATION

where G = (g ij (x)) denotes the metric tensor at the point x on data manifold. In ( 7), since geodesic d(x, x + ϵ) ≤ σ, the geodesic can be evaluated by (3). It can be proved that we can solve the problem (8) with Lagrangian multiplier method and the worst perturbation can be given as:

ϵ ∝ G -1 ∇ x L (9)

The detailed proof of ( 9) can be seen in Appendix A.

2.3. DEFINING METRIC TENSOR:

In the previous subsection, we have derived that the direction of the worst perturbation is relevant to metric tensor and the first derivative of L with respect to x. It is easy to evaluate ∇ x L in DNNs through back propagation. It is then very crucial to define the Riemannian manifold for input and the metric tensor G. Since, the adversarial examples are closely related to loss function and classification boundary, we can define the Riemannian manifold and metric tensor from loss function. Specifically, We first take the n th order Taylor expansion of L around x evaluated at x + ϵ (n is an extremely large value):

L(x + ϵ) ∼ = L(x) + L (1) x (x) 1! ϵ + L (2) x (x) 2! ϵ 2 + ... + L (n) x (x) n! ϵ n = L(x) + L (1) x (x) 1! ϵ + m(x) (10)

where L

(n)

x (x) denotes the n th order derivative of L with respect to x and

m(x) = L (2) x (x) 2! ϵ 2 + o(x) (11)

The loss function L(x + ϵ) can be written as summation of its 1 th order Taylor expansion and the other components of Taylor series m(x). The 1 th order Taylor expansion is more reliable when |m(x)| is small enough. Naturally, the restriction can be defined as:

|m(x)| ∼ = | L (2) x (x) 2! ϵ 2 | = 1 2 |ϵ T Hϵ| ≤ σ 2 (12)

However, it is difficult to deal with the constraint (12) in the optimization problem. We can simplify it with its upper bound by using Lemma 2.3.

Lemma 2.3. Assume H be a symmetric square matrix in R n×n and r ∈ R n be a vector. Then we have |r T Hr| ≤ r T |H|r and |H| represents the matrix with taking the absolute value of each eigenvalue of H (proof can be seen in Appendix E).

Based on Lemma 2.3, we can have

1 2 |ϵ T Hϵ| ≤ 1 2 ϵ T |H|ϵ ≤ σ 2 (13)

where H is the Hessian matrix of L with respect to x and σ is a small value. When the loss function is locally convex with respect to x, the Hessian matrix H is positive semidefinite matrix and the absolute Hessian matrix is the same as the Hessian matrix. When the loss function is not locally convex, the non-negative eigenvalues of absolute Hessian matrix keep the same with the Hessian matrix while the negative eigenvalues are changed to positive ones. The curvature information is partially kept. ( 13) can be viewed as the distance between two close points x and x + ϵ on the Riemannian manifold with metric tensor |H|.

Comparing ( 13) with constraint of (8), we can define the metric tensor as |H|. Substituting |H| in (8), we can easily get the worst perturbation:

ϵ ∝ |H| -1 ∇ x L (14)

In contrast to the traditional adversarial training methods, the metric tensor |H| of our method involves the curvature information of the loss function which can be seen as the second order method.

Through the perspective of geometry, the direction of gradient is not guaranteed to be steepest in Riemannian space, however, the metric tensor adjusts it to the steepest one as illustrated in Figure 2 . Note that, for DNNs, it is easy to evaluate the Hessian matrix of L with respect to input x by back propagation.

Figure 2 : The red circle denotes the region of ∥ϵ∥ 2 ≤ σ, while the red arrow illustrates the direction of gradient. The blue ellipse shows the region of ϵ T |H|ϵ ≤ σ 2 , the blue arrow represents the direction found by the proposed method, and green lines present the contour lines. The steepest direction is given by the gradient of the loss function, which is orthogonal to contour lines only when an orthonormal coordinate system is used in Euclidean space. In the Riemannian space, the steepest direction is not guaranteed to be orthogonal to contour lines. However, adjusted with the metric tensor |H| -1 , the direction of gradient can be approximate to the steepest direction. The graph is better viewed in color.

2.4. ADVERSARIAL PERTURBATION WITHIN l p -BALL ON MANIFOLD:

In the previous subsections, we have calculated the worst perturbation within l 2 -ball on Riemannian manifold. Similar to traditional adversarial training methods, we can also extend our method to l p -ball on manifold. First, we introduce Lemma 2.4 before we proceed to the case of l p -ball. Lemma 2.4. Let A a real symmetric positive definite matrix in R n × R n . Then we have a unique positive definite matrix S in R n × R n so that A = S 2 (proof can be seen in Appendix F).

Using Lemma 2.4, we reformulate the constraint of ( 13)

ϵ T |H|ϵ = ϵ T SS T ϵ = (ϵ T S) 2 ≤ σ 2 (15)

where S is a positive definite matrix which we call a transformation matrix. Then we can easily extend (15) to l p -ball on manifold:

∥ϵ T S∥ p = ( ∑ i |ϵ T S| p i ) 1/p ≤ σ (16)

Substituting ( 16) with the constraint of (8), we can easily evaluate the corresponding worst perturbation (details are provided in Appendix B):

ϵ = σsign(∇L T S -1 )( |∇L T S -1 | ∥∇L T S -1 ∥ p * ) 1 p-1 S -1 (17)

where p * is the dual of p, i.e., 1 p * + 1 p = 1. Clearly, when p = 2, the worst perturbation is reduced to ( 14) which is the case of the perturbation within l 2 -ball on manifold. When p = ∞, our method reduces to the generalized FGSM:

ϵ = σ lim p→∞ sign(∇L T S -1 )( |∇L T S -1 | ∥∇L T S -1 ∥ p * ) 1 p-1 S -1 = σsign(∇L T S -1 )S -1 (18)

Though we can evaluate the adversarial perturbation for any l p -ball on Riemannan manifold through (17). In this paper, we focus on the constraint of l 2 -ball and will develop the corresponding adversarial training method to improve the performance of DNNs in the next subsection.

2.5. ADVERSARIAL TRAINING METHOD WITH RIEMANNIAN MANIFOLD:

After studying the adversarial examples on manifold, we now consider to design an optimization method to improve the DNNs using the theory in the previous subsections. We first define the overall optimization as the robust optimization problem in a way similar to the traditional adversarial training:

min θ E (x,y) D [max ϵ L(x + ϵ, y, θ)] s.t. ∥ϵ T S∥ p ≤ σ (19)

In this paper, we focus on the l 2 -ball constraint, while it is easily extended to the l p -ball constraint. In the case of l 2 , we can reduce the constraint in (19) to ϵ T |H|ϵ ≤ σ. To optimize this problem, we can first solve the inner optimization problem then followed by the outer one. We then repeat this process until it converges. The whole process is shown as Algorithm 1. On the other hand, Algorithm 2 demonstrates the function of approximating |H| -1 ∇ x L(y i , x i , θ). Hessian matrix may require a large amount of computation. In Algorithm 1, we approximate |H| -1 ∇ x L(y i , x i , θ) with the first derivative of loss function with respect to input. Specifically, we simply modify the Limited-memory BroydenCFletcherCGoldfarbCShanno (L-BFGS) method. More details can be seen in Appendix C.

Algorithm 1 Framework of ensemble learning for our system. 1: for number of training iterations do 2:

Sample a batch of labeled data (x i , y i ) with size N .

3:

for i in 1...N do 4:

d i ← |H| -1 ∇ x L(y i , x i , θ) 5: ϵ i adv = ξd i 6:

end for 7:

Update the parameters of neural network with stochastic gradient: θ) . We now provide the theoretical analysis showing that our proposed method truly offers the decent direction for the optimization problem as (Madry et al., 2017) . In order to do this, we first present Theorem 2.5.

8: 9: -∇ θ 1 N ∑ N i=1 logL(y i , x i + ϵ i adv , θ) 10: end for In Algorithm 1, |H| -1 ∇ x L(y i , x i , θ) represents the normalization of |H| -1 ∇ x L(y i , x i ,

Algorithm 2 Approximation for |H|:

-1 ∇ x L(y i , x i , θ). 1: function APPROHD(y i , x i , θ, ζ) 2:

Give ζ very small value 3:

g 0 = ∇ x L(y i , x i , θ) 4: g 1 = ∇ x L(y i , x i + ζg 0 , θ) 5: y = g 1 -g 0 6: s = ζg 0 7: ρ = 1 y T s 8: α = ρs T g 1 9:

q = g 1 -αy 10:

r 0 = q 0 11: β = ρy T r 0 12: r 1 = r 0 + (α -β)s 13:

return r 1 14: end function Theorem 2.5. (Danskin). Let S be nonempty compact topological space and g : R × S → R such that g(., δ) is differentiable for every δ ∈ S and ∇ θ g(θ, δ) is continuous on R n × S. Also assume δ * (θ) = {δ ∈ arg max δ∈S g(θ, δ)}. Then the max-function ϕ(θ) = max δ∈S g(θ, δ) is locally Lipschitz continuous, directionally differentiable, and its directional derivatives satisfy:

ϕ ′ (θ) = sup δ∈δ * (θ) h T ∇g(θ, δ) In particular, if for some θ ∈ R n the set δ * (θ) = {δ * θ } is a singleton, the max-function is differentiable at θ and ∇ϕ(θ) = ∇ θ g(θ, δ * θ )

. This theorem states that the gradients of ϕ(θ) are local objects and the gradients are locally the same as that of g(θ, δ * θ ). With Theorem 2.5, we describe the theory showing that our proposed optimization method truly offers the decent direction: Lemma 2.6. Let δ ∈ S be a maximizer of max δ L (θ, x+θ, y) . Then, we have that -∇ theta L(θ, x+ δ, y) is a decent direction for ϕ(θ) = max δ∈S L(θ, x + δ, y).

Proof. We apply Theorem 2.5 that g(θ, δ) := L(θ, x + δ, y) and S = B p (σ), which is defined as the l p -ball with radius σ on Riemannian manifold. The directional derivative in the direction of h = ∇ θ L(θ, x + δ, y) satisfies:

ϕ ′ (θ, h) = sup δ∈ δ(θ) h T ∇ θ L(θ, x + δ.y) ≥ h T h = ∥∇ θ L(θ, x + δ, y)∥ 2 2 ≥ 0 (20)

2.6. COMPUTATIONAL ANALYSIS:

Compared with traditional adversarial training methods, our proposed ATRM need compute the Hessian matrix of the loss function with respect to input additionally. It may cost extra computation to calculate the Hessian matrix. Nonetheless, we exploit in this paper the first-order derivative of the loss function to approximate the product of Hessian matrix and the vector, which is shown in Algorithm 2. Therefore, our proposed method requires backward propagation three times and forward prorogation once. Specifically, the first backward prorogation is used to approximate the Hessian matrix, the second one is used to evaluate the adversarial perturbation, and the last time is to update the parameters of DNNs. In contrast to traditional adversarial training methods, our proposed method need merely one additional backward propagation which is acceptable in practice.

3. EXPERIMENT:

To validate the efficacy of our proposed method, we conduct a series of experiments on benchmark data including MNIST, CIFAR-10, and SVHN. In these experiments, we compare our proposed ATRM with other competitive methods. For MNIST datasets we use the same baseline as (Rasmus et al., 2015) . The same base structure called 'conv-large' is used on dataset CIFAR-10 and SVHN, which follows (Miyato et al., 2018) . Specifically, 'conv-large' means a large convolutional neural network with seven convolutional layers and three fully-connected layers with dropout where the size of all the convolutional kernels is 3 × 3.

We first implement our proposed ATRM on handwriting dataset MNIST. Since there is no previous adversarial research on this baseline model on this dataset, we conduct the experiment on two methods (adversarial training with l ∞ and l 2 constraint) for comparison. The model is trained with 60, 000 labeled samples without any data augmentation and is tested with 10, 000 samples. We train the model with a batch size of 32 and the maximum 500 epochs. There are two hyper parameters {ζ, ξ} in Algorithm 1 and Algorithm 2. We set ζ to a very small value, which is 10 -6 in this paper.

We tune the value of ξ in the range of {0.1, 0.2, 0.5, 1, 2, 5, 10}. We use the set of hyper parameters that achieved the best performance on the validation set of size 5, 000, selected randomly from the pool of training samples of size 60, 000.

Table 1 lists the performance of various methods including our proposed ATRM and other competitive methods. Except for ATRM, we also conduct the same experiment for the baseline model and traditional adversarial training methods with l 2 -ball and l ∞ -ball constraint. We conduct the experiment with this same setting for five times and calculate the mean and standard deviation. As observed, our proposed ATRM demonstrates the best performance. In particular, all the adversarial methods achieve remarkably good performance, while the ATRM shows a further improvement. This validates the advantages of our proposed method over the other methods, especially the other traditional adversarial methods. (Srivastava et al., 2014) 1.05 Ladder networks (Rasmus et al., 2015) 0.57 ± 0.02 VAT (Miyato et al., 2018) 0.72 RPT (Miyato et al., 2018) 0.82 Baseline (Rasmus et al., 2015) 0.32 Baseline+l ∞ adversarial training 0.30 ± 0.013 Baseline+l 2 adversarial training 0.26 ± 0.019 ATRM 0.22 ± 0.016

For CIFAR-10, we train our proposed model ATRM with 50, 000 labeled samples with data augmentation as conducted in (Miyato et al., 2018) (translation and horizontal flip). The test dataset of CIFAR-10 involves 10, 000 samples. Similar to the experiment on MNIST, we set ζ to a small vaule 10 -6 , and tune the value of ξ in the range of {1, 2, 5, 8, 10}. We run the experiments for five times and report the average performance and corresponding standard deviation. We train our model using the same setting as (Huang et al., 2017) . As can be clearly observed in Table 3 , our method demonstrates the best performance. It is even much better than the very deep networks (DenseNet and ResNet). More importantly, our method achieves an obvious improvement compared with the traditional adversarial training algorithms. (Lin et al., 2013) 8.81 All-CNN (Springenberg et al., 2014) 7.25 Deeply Supervised Net (Lee et al., 2015) 7.97 Highway Network (Srivastava et al., 2015) 7.72 RPT (Miyato et al., 2018) 6.25 ± 0.04 ResNet (1,001 layers) (He et al., 2016) 4.62 ± 0.2 DenseNet (190 layers) (Huang et al., 2017) 3.46 Baseline (Miyato et al., 2018) 6.76 ± 0.07 VAT (Miyato et al., 2018) 5 (Lin et al., 2013) 2.35 Deeply Supervised Net (Lee et al., 2015) 1.92 ResNet (110 layers) (He et al., 2016) 2.01 DenseNet (250 layers) (Huang et al., 2017) Finally, we have also done the experiments to prove the convergence for our proposed method. We have plotted the convergence curves for both training set and validation set of all three datasets as Figure 3 showing.

4. CONCLUSION:

We present the novel framework called Adversarial Training with Riemannian Manifold (ATRM) which generalizes the traditional adversarial training method to Riemannian space. For traditional adversarial training methods, the worst perturbation is often searched with the gradient ∇ x L. However, when the data lay on a geometric manifold defined as a Riemannian manifold, the gradient ∇ x L is not the steepest direction, leading the adversarial perturbation is not the worst one. We present a series of theory showing that our method leads to the steepest direction of the loss function in Riemannian space. In practice, we also develop a practical algorithm guaranteeing the decent direction for the loss function at each epoch. Experiments demonstrate encouraging results on benchmark data including MNIST, CIFAR-10 and SVHN.

arg max ϵ ∇ x L T ϵ s.t. g ij (x)ϵ i ϵ j = σ 2

Then we apply the Lagrangian multiplier method on this problem:

arg max ϵ ∇ x L T ϵ -λ(g ij (x)ϵ i ϵ j -σ 2 ) (21)

Making the first derivative of ( 21) with respect to ϵ zero, we have:

∇ x L = λg ij (x)ϵ i

Then we have:

ϵ = 1 λ G -1 ∇ x L Therefore: ϵ ∝ G -1 ∇ x L B FIND THE ADVERSARIAL PERTURBATION WITH l p -BALL ON MANIFOLD

The optimization problem is:

ϵ = arg max ϵ L(x) + ∇ x L T ϵ s.t. ∥ϵ T S∥ p ≤ σ

Similar to Appendix A, we reduce the problem to:

ϵ = arg max ϵ L(x) + ∇ x L T ϵ s.t. ∥ϵ T S∥ p = σ

We solve it with the Lagrangian multiplier method again and set r = ϵ T S and f (r) ≡ ∥r∥ p = σ.

We have

∇ x LrS -1 = λ(f (r) -σ)

Then we make the first derivative respect to r:

∇ x LS -1 = λ r p-1 p( ∑ i ϵ p i ) 1-1 p ∇ x LS -1 = λ p ( r σ ) p-1 (∇ x LS -1 ) p p-1 = ( λ p ) p p-1 ( r σ ) p (22)

If we sum over two sides, we have

∑ (∇ x LS -1 ) p p-1 = ∑ ( λ p ) p p-1 ( r σ ) p ∥∇ x LS -1 ∥ p * p * = ( λ p ) p * * 1 ( λ p ) = ∥∇ x LS -1 ∥ p * (23)

By combining ( 22) and ( 23), we have

r = σsign(∇L T S -1 )( |∇L T S -1 | ∥∇L T S -1 ∥ p * ) 1 p-1 Since r = ϵ T S, we have ϵ = σsign(∇L T S -1 )( |∇L T S -1 | ∥∇L T S -1 ∥ p * ) 1 p-1 S -1 C FIND THE APPROXIMATION FOR |H| -1 ∇ x L(y i , x i , θ).

We develop a modified BFGS method to approximate the |H| -1 . To solve the memory problem, we use the simplified Limited-memory BFGS (L-BFGS) to approximate |H| -1 ∇ x L(y i , x i , θ) directly (based on BFGS).

We first present Theorem C.1. Theorem C.1. (Sherman Morrison formula (Bartlett, 1951) ) Let A ∈ R n×n be an invertible square matrix and v, u ∈ R n be column vectors. Then A + uv T is invertible if and only if 1 + v T A -1 u ̸ = 0. And its inverse is given by

(A + uv T ) -1 = A -1 - A -1 uv T A -1 1 + v T A -1 u (24)

We then take the second order Taylor expansion for L(x + ϵ 1 ) (where ϵ 1 is a small value):

L(x + ϵ 1 ) ≈ L(x) + ∇L(x)ϵ 1 + ϵ T 1 ∇ 2 L(x)ϵ 1

If we make the first derivative on both sides with respect to ϵ 1 , we can have:

∇L(x + ϵ 1 ) -∇L(x) ≈ Hϵ 1

where H denotes the Hessian matrix of L(x) with respect to ϵ 1 .

We can define y = ∇L(x + ϵ 1 ) -∇L(x), then return r 1 14: end function Proof. We evaluate the geodesic distance between ξ(0) and ξ(a) through Theorem 2.1: F PROOF FOR LEMMA 2.4

d s = ∫ a 0 √ g ij (t)

Let A be a real symmetric positive definite matrix in R n × R n . Then we have a unique positive definite matrix S in R n × R n so that A = S 2 .

:



Figures and Tables:

Figure 1: 1(a) shows a Riemanian space M , where ξ(t) is the geodesic connecting two points ξ(0) and ξ(a). The distance between these two points is measured by the geodesic distance g. T p M is the tangent space of M at point ξ(0) and ξ(t) represents the derivative of curve function ξ(t). 1(b) demonstrates the Euclidean space where the distance between two points is described by Euclidean distance d. Detailed notations can be seen in Section 2.

Figure 3: The convergence curves on three datasets

≈ Hϵ 1 (25)Next, we use modified BFGS algorithm to approximate H and letB = I + ∆M (26) Algorithm 3 Approximation for |H| -1 ∇ x L(y i , x i , θ). 1: function APPROHD(y i , x i , θ, ζ) ∇ x L(y i , x i , θ) 4: g 1 = ∇ x L(y i , x i + ζg 0 , θ)

r T e i ) 2 | = ∑ i (r T e i )|λ|(r T e i ) = r T |H|r (40)

Test performance on MNIST

Table content: <table><tr><td>Method</td><td>MNIST Test error rate(%)</td></tr><tr><td>SVM</td><td>1.40</td></tr><tr><td>Dropout</td><td/></tr></table>

summarizes the results of different methods on CIFAR-10 dataset. In this experiment, we intentionally compare our proposed method ATRM with the other two very deep models, i.e., the densely connected network (DenseNet) with 190 layers and very deep residual network (ResNet) with 1, 001 layers. Overall, our proposed method demonstrates competitive performance. Though not as good as the very deep networks DenseNet and ResNet, the proposed ATRM shows superior performance to those adversarial learning methods and all the other remaining approaches. Once again, this shows that adversarial learning should be conducted on the geometric manifold rather than the traditional Euclidean space.The Street View House Numbers (SVHN) dataset contains 32 × 32 colored digit images. There are 73, 257 images in the training set, 26, 032 images in the test set, and 531, 131 images for additional training.

Table content: <table/>

Test performance on CIFAR-10

Table content: <table><tr><td>Method</td><td>CIFAR-10 Test error rate(%)</td></tr><tr><td>Network in Network</td><td/></tr></table>

Assume H be a symmetric square matrix in R n × R n and r ∈ R n be a vector. Then we have |r T Hr| ≤ r T |H|r and |H| represents the matrix with taking the absolute value of each eigenvalue of H.Proof. Assume {e 1 , e 2 , ..., e n } and {λ 1 , λ 2 , ..., λ n } are the eigenvectors and corresponding eigenvalues of matrix H. Then we reformulate |r T Hr| with eigenvectors and corresponding eigenvalues as:

Table content: <table><tr><td/><td/><td/><td/><td>(37)</td></tr><tr><td>Therefore, we have</td><td/><td/><td/></tr><tr><td/><td colspan="3">ds 2 = g ij (t)dθ i dθ j</td><td>(38)</td></tr><tr><td colspan="2">E PROOF FOR LEMMA 2.3</td><td/><td/></tr><tr><td>|r T Hr| = |</td><td colspan="3">∑ (r T e i )λ i (e T i r)| = | ∑</td><td>λ i (r T e i ) 2 |</td><td>(39)</td></tr><tr><td/><td>i</td><td/><td>i</td></tr><tr><td colspan="2">We can now use the triangle inequality |</td><td>∑ i r i | ≤</td><td>∑</td></tr></table>

Peer review (iclr2019):
 The authors argue that they propose a method to find adversarial examples, when the data lie on a Riemannian manifold. In particular, they derive a perturbation, which is argued to be the worst perturbation for generating an adversarial example, compared to the classical Euclidean derivation. I strongly disagree with the proposed (Riemannian) geometric analysis, because there are several technical mistakes, a lot of arbitrary considerations, and flawed assumptions. In particular, my understanding is that the proposed method is not related at all with Riemannian geometry. For justification I will comment some parts: #1) In Section 1 paragraph 4, and in Section 2.3 after Eq. 14, the sentences about the gradient of a function that is defined on a manifold are strange and unclear. In general, the gradient of a function defined on a manifold, points to the ascent direction. Thus, if I understood correctly the sentences in the paper support that the gradient of such a function is meaningless, so I think that they are wrong. #2) How the -ball on a manifold is defined? Usually, we consider a ball on the tangent space, since this is the only Euclidean space related to the manifold. Here, my understanding is that the authors consider the ball directly on the manifold. This is clearly wrong and undefined. #3) To find the geodesic you have to solve a system of 2nd order non-linear ODEs, and there are additional details which I will not include here, but can be easily found in the Riemannian geometry literature. Also, I think that the Lemma 2.2. is wrong, since the correct quantity of Eq. 3 is , where based on the included proof. This is clearly not a sensible geodesic, it is just the infinitesimal length of a line segment when , which means that the two points are infinitesimally close. #4) If is on a Riemannian manifold then the operator does not make sense, so Eq. 7 is wrong. In particular, for operations on Riemannian manifolds you need to use the exponential and the logarithmic map. #5) Continuing from #4). Even if we consider the perturbation to be sufficiently small, still the is not defined. In addition, the constraint in Eq. 8 is wrong, because the inner product related to the Riemannian metric has to be between tangent vectors. Here the is an arbitrary quantity, since it is not defined where it actually lies. In general, the derivation here is particularly confusing and not clear at all. In my understanding the constraint of Eq. 8 is a purely linear term, and is not the geodesic distance on a manifold. It just represents the Mahanalobis distance between the points and , for a matrix defined for each , so it is a linear quantity. So Eq. 9 just utilizes a precondiner matrix for the classical linear gradient. #6) The Eq. 12 is very flawed, since it equalizes a distance with the Taylor approximation error. I think that this is an unrealistic assumption, since these terms measure totally different quantities. Especially, if is the geodesic distance. #7) The upper bound in inequality Eq. 13 comes from Eq. 12, and it is basically an assumption for the largest absolute value of the Hessian*s eigenvalues. However, this is not discussed in the text, which are the implications? #8) I find the paper poorly written, and in general, it lacks of clarity. In addition, the technical inconsistencies makes the paper really hard to follow and to be understood. I mentioned above only some of them. Also, there are several places where the sentences do not make sense (see #1), and the assumptions made are really arbitrary (see #6). The algorithms are not easy to follow. Minor comments, you can reduce the white spaces by putting inline Eq. 3, 4, 5, 6, 9, 10, 14, and Figure 2. The notation is very inconsistent, since it is very unclear in which domain/space each quantity/variable lies. Also, in Section 2.5. the authors even change their notation. In my opinion, the geometrical analysis and the interpretation as a Riemannian manifold is obviously misleading. Apart from the previously mentioned mistakes/comments, I think that the proposed approach is purely linear. Since actually the Eq. 14 implies that the linear gradient of the loss function, is just preconditioned with the Hessian matrix of the loss function with respect to the input . Of course, if this function is convex around , then this quantity is the steepest ascent direction of the loss function, simply on the Euclidean space where lies. However, when this function is not convex, I am not sure what is the behavior when all the eigenvalues of the Hessian are set to their absolute value. Also, the (arbitrary) constraint in Eq. 13 implicitly sets a bound to the eigenvalues of the Hessian, which in some sense regularizes the curvature of the loss function. To put it simple, I think that the proposed method, is just a way to find a preconditioner matrix for the linear gradient of the loss function, which points to the steepest direction. This preconditioner is based on the Hessian of the loss function, where the absolute values of the eigenvalues are used, and also, are constrained to be bounded from above based on a given value. Generally, in my opinion the authors should definitely avoid the Riemannian manifold consideration. I believe that they should change their perspective, and consider the method simply as a local preconditioner, which is based on the Hessian and a bound to its (absolute) eigenvalues. They should also discuss what is the implication by setting the eigenvalues to their absolute values. However, since I am not an expert in the field of adversarial examples, I am not sure how novel is this approach.