On the Need for Topology-Aware Generative Models for Manifold-Based Defenses
Authors: Uyeong Jang
Susmit Jha
Somesh Jha
Venue:  (2020)
Keywords: Manifold-based Defense
Robust Learning
Adversarial Attacks

Abstract: ML algorithms or models, especially deep neural networks (DNNs), have shown significant promise in several areas. However, recently researchers have demonstrated that ML algorithms, especially DNNs, are vulnerable to adversarial examples (slightly perturbed samples that cause mis-classification). Existence of adversarial examples has hindered deployment of ML algorithms in safety-critical sectors, such as security. Several defenses for adversarial examples exist in the literature. One of the important classes of defenses are manifold-based defenses, where a sample is "pulled back" into the data manifold before classifying. These defenses rely on the manifold assumption (data lie in a manifold of lower dimension than the input space). These defenses use a generative model to approximate the input distribution. This paper asks the following question: do the generative models used in manifold-based defenses need to be topology-aware? Our paper suggests the answer is yes. We provide theoretical and empirical evidence to support our claim.

Published as a conference paper at ICLR 2020
ON THE NEED FOR TOPOLOGY-AWARE GENERATIVE MODELS FOR MANIFOLD-BASED DEFENSES
Uyeong Jang
Susmit Jha Computer Science Laboratory SRI International
Department of Computer Sciences
University of Misconsin-Madison Madison, WI, USA wj wjangêcs. sc. edu
Menlo Park, CA, USA susmit jaa@shaa@sr com
Somesh Jha
Department of Computer Sciences
University of Misdonnin-Maddion
Madison, WI, USA XaiPient
Princcton, NJ, USA jhaßcs. wisc.edu
ABSTRACT
Machine-learingg (ML) algorithms models, especially deep neural networks (DNNs), have shown significant promise in several areas. However, researchers have recently demonstrated that ML algorithms, especially DNNs, are vulnerable adversarial examples (slightly perturbed samples that cause misclassification) The existence of adversarial examples has hindered the deployment of ML algorithms in safety-critical sectors, such as security. Several defenses for adversarial examples exist in the literature. One of the important classes of defenses are manifold- based defenses, where sample is "pulled back" into the data manifold before classifying. These defenses rely on the assumption that data lie in a manifold lower dimension than the input space. These defenses to approximate the input distribution. In this paper, we investigate the following question: do the generative models used in manifold-basee defenses need be topology-aware? We suggest the answer is yes, and we provide theoretical and empirical evidence support our claim.
generative model
INTRODUCTION
Machine-learning (ML) algorithms, especially deep-neural networks (DNNs), have had resounding success in several domains. However, adversarial examples have hindered their deployment in safety-critical domains, such autonomous driving and malware detection. Adversarial examples are constructed by an adversary adding a small perturbation to a data-point so that it is misclase misclassified.
Several algorithms for constructing adversarial examples exist in the literature (Biggio al. 2013
Szegedy et al. 2013 Goodfellow et al.) 2011b;; Kurakin et al. 201 Carlini & Wagner 2017 Madry
al.] 2017| Papernot et al. [217)). Numerous defenses for adversarial examples
have been
explored (Kurakin et al. (016b] Guo et al.
9in7, et al.
2017
Song et al. 2017
Tramer et al.
2017 Xie et 2017 Dhillon et al. 2018 Raghunathan et al.
2018
Cohen
2019
Dubey et
2019
In this paper, we focus on "manifold- based"""" defenses (Ilyas al. 2017 Samangouei et al. 2018). The general idea in these defenses is to "pull back" the data point into the data manifold before classifica- tion. These defenses leverage the fact that, several domains, natural data lies in low-dimensional manifold (henceforth referred to as the manifold assumptions) (Zhu & Goldberg, 2009). The data distribution and hence actual manifold that the natural data lies in is usually unknown, so these defenses generative model to "approximate" the data distribution. Generative models attempt to learn to generate data according to the underlying data distribution. (The input to a generative model is usually random noise from known distribution, such Gaussian uniform.) There

---

Published as a conference paper at ICLR 2020
various types of generative models in the literature, such as variational autoencoder (VAE) (Kingma
& Welling 2013), generative adversarial network (GAN) (Goodfellow et al. (0114) and reversible generative models, e.g., real-valued non-volume preserving transform (Real NVP) (Dinh et al. 2016).
This paper addresses the following question:
Do manifold- based defenses need to be aware of the topology of the underlying data manifold?
In this paper, we suggest the answer to this question is yes. We demonstrate that if the generative model does not capture the topology of the underlying manifold, it can adversely affect these defenses. In these cases, the underlying generative model is being used as approximation of the underlying manifold. We believe this opens a rich avenue for future work on using topology-awar generative models for defense to adversarial examples.
Contributions and Roadmap. We begin with brief description of related work in Section 2 Section provides the requisite mathematical background. Our main theoretical results are provided in Section Informally, our result says that if the generative model is not topology-aware, it can lead to a "topological mismatch" between the distribution induced by the generative model and the actual distribution. Section 5 describes our experimental verification of our theoretical results and investigates their ramifications on a manifold-based defenses called Invert-and- -lasssify (INC) (Ilyas)
et al. 2017 Samangouei al. 2018
2
RELATED WORK
2.1
GENERATIVE MODELS
As a method for sampling high-dimenn sith-immeniioal data, generative models find applications in various fields in applied math and engineering, c.g., image processing, reinforcement learning, etc. Methods for learning data data-generating distribution with neural networks include well-known examples of Variational Autoencoders (VAEs) (Kingma & Welling (201)) and variations of Generative Adversarial
Networks (GANs) (Goodfellow et al. 2014a| Radford et al. 2015 Zhao al., 2016).
These generative models learn how to map latent variables into generated samples. The VAE is variational Bayesian approach, so it approximates a posterior distribution over latent vectors (given training samples) by simpler variational distribution. Similar to other variational Bayesian methods, VAE tries to minimize the Kullback-Leibler divergence between the posterior distribution and the variational distribution by minimizing the reconstruction error of the autoencoder. GANs represent another approach to learning how to transform latent vectors into samples. Unlike other approaches, the GAN learns the target distribution by training two networks generator and discriminator simultaneously.
In addition to generating plausible samples, some generative models construct bijective relations between latent vector and generated samples, so that the probability density of the generated sample can be estimated. Due to their bijective nature, such generative models are called be reversible. Some examples are normalizing flow (Rezende & Mohamed (2055), Masked Autoregressive Flow (MAF) (Papamakarios al., 2017), Real NVP (Dinh et al.) 2016). and Glow (Kingma & Dhariwal 2018).
2.2
APPLICATIONS OF GENERATIVE MODELS IN ADVERSARIAL MACHINE LEARNING
The DNN-based classifier has been shown be vulnerable to adversarial attacks (Szegedy al.
2013
Goodfellow et al., 2014b Moosavi-Dezion
et al. 2016 Papernot et al.. 2016 Madry et al. Several hypothesis try explaining such vulnerability (Szegedy et al.) 2013 Goodfellow et al.
2017).
2014b
Tanay & Griffin 2016 Feinman et al. 2017), and one explanation is that the adversarial examples lie far away from the data manifold. This idea leads to defenses making use of the geometry learned from the dataset by projecting the input to the nearest point in the data manifold.
To learn a manifold from a given dataset, generative models can be exploited. The main idea is to approximate the data-generating distribution with generative model, to facilitate searching over data manifold by searching over the space of latent vectors. The term Invert-and Iivert-and-Classe MandClassfy (INC) was coined to describe this type of defense (Ilyas et al. (017). and different types of generative models were tried to detect adversarial examples (lyas et al. 2017; Song et al. [017]: (Samangouei et al. 2018). Usually, the projection is done by searching the latent vector that minimizes the geometric
2

---

Published as a conference paper at ICLR 2020
distance (Iyyss et al., 2017: Samangouei et al. 2018). However, despite the promising theoretical background, all of those methods are still vulnerable (Athalye et al. 2018 Ilyas et al. 2017).
BACKGROUND
We formally describe data generation, based on the well-known manifold assumption; data lies close to manifold whose intrinsic dimension is much lower than that of the ambient space. In model of data generation, we provide a formal definition of data- aatta-gnerattng manifold M on which the data-generating distribution lies such that M conforms to the manifold assumption.
3.1 REOUIREMENTS
Real-world data tends to be noisy, so the data does not easily correspond to an underlying manifold. We first focus on an ideal case where data is generated solely from the manifold M without noise.
In the setting of classification with labels, we consider manifolds Mi...., Mr c R" that correspond respectively. We assume those manifolds
to the generation of data in each class ε {l,..... pair- wise disjoint, i.e., Mr n M, Ø for any i & j. We set the data-generan generating manifold . as the disjoint union of those manifolds, M = U Mj- We assume M to be a compact Riemannian manifold with volume measure d.M induced by its Riemannian metric. When a density function pM defined on M satisfies some requirements, it is possible compute probabilities over M via S M PM (x) dM (x). We call such M equipped with PM an d.M as data-genn manifold. We refer Appendix A and Appendix Appendix(D.Ifoor details about definitions and requirements on PMr
In practice, data generation is affected by noise, so not all data lic on the eata-generating manifold. Therefore, we incorporate the noise as an artifact of data-generation and extend the density Pas on M to the density on the entire R" by assigning local noise densities on M. We consider a procedure that (I) samples point x, from M first, and (2) adds a noise vector n to get an observed point Here, the noise is random vector sampled from a probability distribution, centered at X whose noise density function is Vx., satisfying Ux (x(n)= "xxx x) = PM (&) x, x).
&
3.2 EXTENDING DENSITY
When M is equipped with a density function PM and a measure dM that we can integrate over M, we can compute the density after random noise is added as follows.
p(x) = f v=(* x)x(x)dM(xx
Since (x x) is function on when X is fixed, computing this integration can be viewed as the computing expectation of a real-valued function defined on M. Computing such expectation has been explored in Peennee [1999). A demonstrative example is provided in Appendix B and this extension further discussed in Appendix D.2
3.3
GENERATIVE MODELS
generative model tries to find a statistical model for joint density p( ((x v) (Ng & Jordan 2002). We mainly discuss a specific type that learns a transform from one distribution Dz 2 to another target distribution D x. Commonly, a latent vector z ~ Dz is sampled from a simpler distribution, e.g.. Gaussian, then a pre-trained deterministic function G maps to sample x G(z).
Specifically, we focus on reversible generative models to facilitate the comparison between the density of generated samples and the target density. In this approach, the dimensions of latent vectors are set to be the same as those of the samples to generated. Also, for a given x, the density of x is estimated by the change of variable formula (equation (2) in Section 5.1)
3.4 INVERT AND CLASSIFY (INC) APPROACH FOR ROBUST CLASSIFICATION
As the data-generating manifold M contains class wise disjoint manifolds, there is classifier on IR" separating these manifolds. If separates the manifolds of M, any misclassified point should lie out of M. Therefore, to change correct classification near manifold, any adversary would pull sample further out of the manifold. By projecting misclassified points to the nearest manifold, we may expect the classification to be corrected by the projection. The INC method (Ilyas al. 2017 Samangouei et al. 2018) implements this using a generative model.
The main idea of INC is invert the perturbed sample by projecting to the nearest point the data-gent settttegneraatinggg manifold. Ideally, the data-gent gentaageneraiig manifold M accessible. For any point (x. y) with [x) f y, out-of-manifold perturbation is reduced by projecting & to x" on M. The manifold M
by
3

---

Published as a conference paper at ICLR 2020
unknown in practice. However, M is the data-generating manifold of Dxx x. generative model G for D is trained to approximate M. Then, searching over M is replaced by searching over latent vectors of G. More details about INC implementations described in Section 5.1
4 TOPOLOGICAL PROPERTIES OF DATA FROM GENERATIVE MODELS
In this paper, we study the significance of differences in the topological properties of the latent vector distribution and the target distribution in learning generative models. Initial information about the topology of target distribution is crucial to the generative model performance. Specifically, if there difference in the number of connected components in the superlevel between the target distribution and the distribution of the latent vector, then any continuous generative model G cannot approximate the target distribution properly (irrespective of the training method). Due to the space limit, all proofs are presented in Appendix C
4.1 TOPOLOGY OF DISTRIBUTIONS BASED ON SUPERLEVEL SETS
The data-generating manifold geometric shape that corresponds to the distribution. However, this manifold is not accessible in most cases and we only have indirect access via the distribution extended from it. Therefore, we consider finding shape from the extended density so that this "shape" successfully approximates the data-generating manifold.
X-density superlevel set. We use the concept of X-density superlevel set to capture geometric features of the density function. Simply put, for a density function p and a threshold À O, the X-density superlevel set Lp, is the inverse image p L oo]. Our theoretical contribution is the conditional existence of a A-density superlevel set reflecting the topology of the data- mata-generating manifold under proper conditions on the noise density.
Assumptions on noise density. For a family of densities (Ux)xeM, we require the noise Vx to satisfy number of as- sumptions. These assumptions facilitate theoretical discussion about the superlevel set reflecting the data-generating manifold. the following definition, we denote a Euclidean ball of radius 5 centered at by (x).).
be
Definition 1. Let ux be family of noise densities.
À is mmall-enough if Lyn.> is nonempty for all x E M,
X-bounding radius 6x,x == min(ō) 66 Le E (0) is the smallest radius that (0) contains LegiA When maXxeM xx,x exists for some X, we denote the maxi- mum value 8x.
L
>-guaranteeing radius Ex,A max(E (0) Lug.A}
Figure 1: Example superlevel set Lx, with A-bounding radius òx and X- guaranteeing radius Ex.>-
is the largest radius that Lug,A contains (0). When minge as xx exists for some X, denote the mini- mum value as ex-
Sufficient conditions for the existence of these radii are dis- cussed in Appendix D.3 The properties of these radii summarized in Lemma follows from Definition
I
(The proof
Lemma 1. Let Vx be family of noise densities and let A be small-enough. Then,
* - x 82
xx (x-xx
| x Sex 1x
whenever 8x and ex exist.
Figure 1 shows an example of superlevel set Lxx, of noise at point and its X-bounding radius 6x,1 and g-guaranteeing radius xx
'The topology of distributions, refers the topology of shapes that correspond the distributions.
4

---

Published as a conference paper at ICLR 2020
Finally, we define the continuous variation of noise densities 1/x over changes of x M. For the continuous variation, we require the continuity of both radii 6x.A and 6x,A as real-valued functions of X .M for any fixed value of X.
Definition 2 (Continuously varying radii). Noise densities 8xx have continuously varying radii if, for a fixed small-enough X, both X-bounding radius 6x,A and X-guaranteeing radius 6x,A are continuous functions of x M.
When noise densities have continuously varying radii, with the compactness of M, we can apply the extreme value theorem to guarantee the existence of both 8x maXxe 0x,A and Ex millye Ex,A-
4.2 MAIN THEOREM
Our main theorem establishes, under the assumptions on noise densities from Section 4.1 the existence of À such that,
(Inclusion) The X-density superlevel set Lp. includes the data-generating manifold M. (Separation) The X-density superlevel set Lp.A consists of connected components such that each component contains most one manifold Mj.
Definition 3. Consider a data-generating manifold M with density function pM- For radius we define w, to be the minimum (over x E .)) probability of sampling x' e M in an e-ball B, (x).
We := min Pr [x's (x)x)
x x'-pM
Definition 4 (Class-wisg wise distance). Let (X, d) be a metric space and let M = U/ M, a data- generating manifold in X. The class-wise distance dew of M is defined as,
dew min min x(x,x') A xeM;
ff x'EM,
With the definitions above, we proved the following main theorem.
Theorem 1. Pick any small-enough threshold A. Fix value X s wed and let 8" = 6x* be the X bounding radius. If dew of M is larger than 28", then the superlevel set Lp.>* satisfies the following properties.
Lp, contains the data-genenn generatennnnn manifold M.
Each connected component of Lp, contains at most one manifold M4 of class i.
4.3 APPLICATION TO THE GENERATIVE MODEL.
We show an application of Theorem 1
We denote the target distribution by Dx, the latent distribution
by Dz, and the distribution of G(z) where ~ Dz by De Similarly, we denote the corresponding
X-density superlevel sets of densities by LN L2 and L G(() We assume the generative model G to be continuous. Then, we get the following theorem regarding the difference between T.A and T. G(2) in the number of connected components.
Theorem 2.
Let Dz be a mixture of nz multivariate Gaussian distributions, and let the data- generating manifold of Dx contain nx components. Let G be continuous generative model for Dx using latent vectors from Dz. Let X" be the threshold value from the Theorem If nz < nx, XXX and I X
G(Z) do not agree on the number of connected components.
We can use this theorem to deduce the need for adequate information about the target distribution when training generative model, especially if it used for security application, e.g., INC.
Corollary 1. If Theorem satistied, there is point x _ such that & L but x G(2)
As result, with density least > G generates point x that is unlikely be generated by the target distribution. Since INC is based on generations of G, the INC method can output an out-of-manifold point as a solution of optimization (12).
In Appendix D.4 Theorem generalized for more topalogical properties.
5

---

Published as a conference paper at ICLR 2020
two-moons
spirals
circles
: (2)
m2 s
in cos0
Mo
(2)
21
22
3e cos(t)
ge' oce(1)
Mo (
ig - sinff
M1 (21)022)
22 = 1- sin
21 = 1- cas
Mr
(2)
21 s oos(t+ + m)
ge sin(t
cos 22 sim
8 [0,w]
Ma 8
(2)
222 5e siu(t 3m) }
211 = se' coe(1 + fm)
8 [0,2n]
6art [0,T] where T In
Table 1: Parameterizations of dataset used in the experiments.
EXPERIMENTAL RESULTS
In this section, we empirically demonstrate the consequence of the two theorems and explore their implication for the INC defense. Our main goals the applicability of Theorem and Corollary [ via toy datasets, and (2) the improvement in INC
provide (1) empirical support for
performance using a class-aware generative model. The main questions and the corresponding answers are shown below.
(Q1) Can we experimentally verify the results of section 4.3
Specifically, can we find cases that the superlevel sets of D and Da(z) have different numbers of connected components?
(Q2) How does INC fail when the generative model is ignorant of topology information?
(Q3) Does the class-aware generative model improve the INC performance?
(A1) Theorem and Corollary cann be verified by plotting the X-density superlevel set. Especially, we visualize the X-density superlevel set of Do(z) reflecting Theorem and Corollary [
(A2) When generative model is not trained with topology information, naive INC may fail. We found out two possible reasons regarding INC failure: (1) choice of a bad initial point and (2) out-of- manifold search due to non-separation of density superlevel set.
(A3) The performance of INC is improved by training generative models with topology informa- tion on the target distribution. We improved the average INC performance by decreasing the error induced by projection 30% compared to the class-ignorant counterpart.
In the rest of this section, we provide more detailed description of our experiments. First, we briefly describe the experimental setup in Section 5.T datasets, latent vector distributions, training method, and INC implementation. Then, Sections 5.2 5.4 describe the experimental results regarding the findings summarized above. (5.ciionS.5]comeeeet an additional experiment illustrating the changes of decision boundaries by INC application.
5.1 EXPERIMENTAL SETUP
Datasets. For all experiments, we use three toy datasets in I two-moons, spirals, and circles. Table summarizes the parameterizationg of each data-generating manifold and Figure shows the plots of the corresponding uatt-generattnn manifolds. To construct the training set, we first sample 1000 points uniformly from each manifold M,, then each point is perturbed by isotropic Gaussian noise (f,,o"1))) 0²12) with 0.05. Before the training, each training set is standardized by preprocessing of Scikit-learn package.
Latent vector distributions. For latent vector distributions Dz, prepared three different mix- tures of ng Gaussian distributions with n2 ε (1,2,3). When ng = 1, we simply use N/0 12). When n 2.3, we arranged nz Gaussian distributions along circle of radius R = 2.5, so that i-th Gaussian has mean at f4, (- [-Rsin 2 Reos 2 with 0.5 for 2 and = 0.3 for n 3. Then, the uniform mixtures of the arranged Gaussian are used as Dz. In Figure (top row), we visualize the connected components corresponding to the latent vector distributions.
Training generative models. Our experiments mostly the Tensorflow Probability (Dillon et al. 2017) library that contains the implementation of reversible generative models. Specifically, the Tensorflow Probability library contains implementation of the Real NVP coupling layer that we used as building block of our models. The default template provided by Tensorflow Probability
'The value T is from the reparamcterization t In (s/V2+1) for [0, 15] for uniform sampling.

---

Published as a conference paper at ICLR 2020
85-
10
60
-05
-10
P
-15
-15
(a) two-moons
(h) spirals
(c) circles
Figure 2: Data-generating manifolds used in the experiments
library was used to construct each Real NVP coupling layer with two hidden layers of 128 units. Each model uses eight coupling layers that are followed by permutations exchanging two dimensions of R except for the last coupling layer.
We describe the details of the training procedure of the generative models used in the experiments. We prepared two different types of generative models: class-ignorant and class-aware.
The class-ignorant type the usual Real NVP model. This model uses the empirical estimation of negative -ggliikl over a training batch
Xm) as its training loss.
m Σ
Egt = m
log(px(x:))
The density Px of x estimated by applying the change of variables formula,
px (x) = pz(z) det [dG(z)
(2)
0zT
where pz is the density of Dz and aG(2) Oz"
is the Jacobian of G as function from R" to itself.
The class-aware type is the Real NVP model trained with information about the number connected components, i.c. the number of class labels 1. Using the number of labels, the densities px and can be decomposed as follows.
(x(x)=
Σ (e(2.....!)
Pr[y (x)(xx)
pz(2) Σ Pr[y (2)
ve(1.....!)
where Px. px.a(x) px (x and each pz, the i-th Gaussian component described above. Since Pr[y i] is not generally known, the uniform distribution Pr(y & is used, where is the number of classification labels.
The main idea is class-wise training, i.e., training each px, from each pz.:- Applying the change of variables formula for each class i,
aG(2)
(x) pz,(2) det
(4)
dz
Combining equations and we get the change of variables formula loss function & for class-wise training as follows.
We define the class-wise
4
mi Σ 1[v = lxx()x;((x))) 1-1
where m. is the number of training samples in class i. Then, we train generative model using the weighted sum & as the training loss function.
fea
Σ (e(1.....
Pr(y +44
Each model was trained for 30,000 iterations. For each iteration, batch of 200 random samples was chosen from two-moons and circles dataset, and a batch of 300 random samples was chosen from the spirals dataset. For the choices of latent vector distribution, we chose the mixture of - Gaussians for the class-ignorant type, whereas we chose the mixture of Gaussians for the class-aware type.
7

---

Published as a conference paper at ICLR 2020
sotropic Gaussians Crt =1
Micture Gauestans (it =
Mature Gaussians Sty
-3
(a) Isotrpic Gaussian
(b) Mixture 2 Gaussians
(c) Mixture of 3 Gaussians
Two-monnk: Clacs-ignorant
Spirale Classignorart
Circlen: Classignorant
1
-2
-2
(d) two-moons, class-ignt ignorant
(c) spirals, class ignorant
(f) circles, class-ignores ignorant
Two moons. Closs sware
Spirals: Clsss aware
Cirdes. Class aware
4
2
2
(g) twD-moons, class-aware
(h) spirals, class-aware
(i) circles, classaware
Figure 3:
X-density superlevel sets of Dz and Da(2) with À = 0.01. Top row: Dz for n2 1,2,3. Middle row: Da(z). class-ignorant model. Bottom Da(z). class-aware model.
5.2 VISUAL VERIFICATION OF THEOREMS
The goal of this section is to verify Theorem and the Corollary [ by visualizing the superlevel set reflecting the statements. Figure 3 shows the X-density superlevel sets of densities of DG(2) using the same threshold class-ignorant version and those from the class-aware version, respectively. Each column corresponds to each dataset. All distributions are scaled for the standardization preprocessing before the training. In general, superlevel set components are separated when the generative model class-aware. On the contrary, the class-ignorant generative models introduce connections between the components, as anticipated by Corollary Due to this connection, the class-ignorant generative models contain fewer connected components in their superlevel sets; this verifies Theorem 2 for our choice of X* = 0.01.
0.01. The first row and the second row show the results from the
5.3 INC FAILURE DUE TO THE LACK OF INFORMATION ON THE DISTRIBUTION TOPOLOGY
We present how the non-separation of superlevel set components influences the performance of the INC. We provide two possible explanations why the INC fails. First, the bad initialization causes suboptimal solution manifold not-the-nearest to the input. Second, artifact induced by the topological difference produces an out-of-manifold solution.
Figure presents three visualized examples of INC with class-ignorant generative model for two- moons. In each plot, the black dot is the given point x, and cyan dot is the initial point from choosing randomly from the latent vector distribution - (O, I2), and magenta dot is the final point output by INC. All intermediate points of the optimization are plotted with dots, changing colors gradually from cyan magenta. The training set for two-moon used in the training procedure is plotted in gray.
8

---

Published as a conference paper at ICLR 2020
43
(a) INC with ideal initialization
(b) INC with bad initialization
(c) INC searching out of manifold
gennnraatggeeeeattvvee Figure 4: Successful and failed cases of INC using class-ignorant generative model of two-moon.
Two-moons
Spirals
Circks
class-ignorant
class-aware
class-ignorant
class-aware
class-ignorant
class-aware
0.647 (0.666)
0.148 (0.208)
1,523 (1.338)
0.443 (0.440)
0.699 (0.491)
0,180 (0.259)
Table 2: Comparison of the projection errors of INC based on the class- awasenesssssss of the model.
Figure 4aj is the INC optimization with ideal start. The initial point lies in the same manifold as the manifold closest to & Then, the INC optimization searches along the manifold, converging to point close &. Figure 4b shows case in which INC fails because of bad initialization. The initial point was chosen on a manifold not containing the desired solution, so the INC converged to a local optimum on the wrong manifold. Our class-aware INC performs manifold-wis initialization to circumvent this issue. Figure[4cJshows that the INC failed due to an out-of of-mmmifoldd search. The INC converged in a wrong manifold, and a nontrivial amount of intermediate points were out of manifold, resulting in an out-of out-of-manifold solution (see Figure 3d
5.4 INC IMPROVEMENT VIA CLASS- GENERATIVE MODEL
We demonstrate that INC performance is improved by using class-aware generative models. To measure the performance the INC, 100 points are chosen uniformly from each manifold M, Then, each point is perturbed by ny normal to the manifold at generating 200 adversarial points = X Dg. For all datasets, r 0.2 used for perturbation size. We expect two types of INC to map back to the original point x, is the optimal solution to 11 We define the projection error of INC as |INC(*) x 2|, and collect the statistics of projection errors over all &
Table 2 shows the projection eπror statisties for two types of INC. Each pair of columns show the results on the indicated dataset. For each pair, one column shows the error of the class-ignorant INC and the other column shows that of the class-aware counterpart. Numbers in each cell are averages and standard deviations (in parenthesis) of the projection error. For any dataset, the class-aware INC achieves lower projection errors. Histograms of the projection errors are provided in Appendix E
5.5 ADDITIONAL EXPERIMENTS FOR THE INC PERFORMANCE.
Finally, we present experiments to demonstrate the effect of the superlevel set discrepancy on the INC performance. First, we begin with training support vector machines (SVMs) performing classification tasks for our target distributions. For training data, we randomly sampled 1000 training points from each data-generating manifold. The baseline SVMs were intentionally ill-trained by using the high kernel coefficient 7 100. D
After training SVMs, we formed other classifiers by applying INC to ill-trained SVMs To explain, for each dataset, we have four types of classifiers as follows.
(1) Ill-trained SVM: Baseline classifier
(2) Ideal INC: Classifier with INC using a direct access to the data- eetta-enerating manifolds
(3) Class-ignoran INC: Classifier with INC using copology-ignoran generative model
(4) Class-aware INC: Classifier with INC with using a topology-ane awaee generative model
We want to emphasize that direct access to the data-generating manifold is not possible general. However, applying INC using direct access gives us an INC purely based on the geometry, it is an ideal form of INC that should be approximated. Also, since the class-ignorant INC is affected by a bad choice of initial point, we reduced the effect of bad initialization by sampling more initial points and taking the best solution among the projection results. For this number of initial choices, we
'In general, choosing unnecessarily high kernel coefficient causes overfitting (Chaudhuri et al. 2017 inducing decision boundary close to the training data.

---

Published as a conference paper at ICLR 2020
(a) IlI-triined SVM
(b) Ideal INC
(c) Class-ignrrant INC
(d) Class-aware INC
Figure 5: Changes in the decision boundaries of ill-trained SVM after the INC applications.
chose many initial points the number of manifolds, which was exactly the same the number of initial points for the topology-aware INC model.
To demonstrate the improvement in the robustness of the model, we visualize the effect by depicting the decision boundary of each classifier. Specifically, we form a 300 300 grid on the domain of [-3.3] x [3,3 3] and compute the classification result. The depicted decision boundaries in Figure Each row corresponds to each dataset: two moons, spirals, and circles, respectively. Each column corresponds to classifiers 1-4 described above, from the first column the fourth column, respectively. From Figure 5) it is visually evident that the class-aware INC models provide more proper approximations the ideal INC model compared the class-ignorant INC models.
presented
CONCLUSION
We theoretically and experimentally discussed the necessity of topology awareness in the training of generative models, especially in security-critical applications. A continuous generative model sensitive to the topological mismatch between the latent vector distribution and the target distribution. Such mismatch leads to potential problems with manifold-based adversarial defenses utilizing generative models such as INC. We described two cases in which the INC failed: the bad initialization and the artifacts from the topological difference. We experimentally verified that topology-awe training effectively prevented these problems, thereby improving the effectiveness of generative models in manifold-base defense. After topology-awer training of generative models, the INC projection errors represented 30% of the errors of the topology-ignorant INC.
7 ACKNOWLEDGEMENT
Dr. Susmit Jha and Uyeong Jang's internship SRI International were supported in part by U.S. National Science Foundation (NSF) grants #1740079, #1 #5000,,9, U.S. Army Research Laboratory Cooperative Research Agreement W91INF- 17-2-0197 and DARPA Assured Autonomy under contract 148750-19-C-0089 The views, opinions and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Govermment. This work is partially supported by Air Force Grant FA9550-18-1- 0166, the National Science Foundation (NSF) Grants CCF-FMitF- and
BaTC-Frontien Centterr--100666 1804648
and ARO grant number W91 1911N1-17-1-00
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. arXiv preprint /r0.v:/802..00 004000 2018.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Šındić, Pavel Laskov. Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 387-402 Springer, 2013.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEFE Symposium on Security and Privacy (SP), pp. 39-57. IEFF, 2017.
Arin Chaudhuri, Deovrat Kakde, Carol Sadek, Laura Gonzalez, and Seunghyun Kong. The mean and median criteria for kernel bandwidth selection for support vector data description. In 2017 IEEE International Conference on Data Mining Workshops (ICDMW), pp. 842-849. IEEE, 2017.
Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary dif- ferential equations. In Advances in Neural Information Processing Systems, pp. 6571-6583, 2018.
Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: 1902.02000.0999 02918, 2019.
Guneet S Dhillon, Kamyar Azizzadenesheli, Zachary C Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Anima Anandkumar. Stochastic activation pruning for robust adversarial defense. arXiv preprint arXiv: 0003.8003.0333 2018.
Joshua V Dillon, Ian Langmore, Dustin Tran, Eugene Brevdo, Srinivas Vasudevan, Dave Moore, Brian Patton, Alex Alemi, Matt Hoffman, and Rif A Saurous. Tensorflow distributions. arXiv preprint 17XXiv:1711.106/0 2017.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. arXiv 2016.
preprint
Abhimanyu Dubey, Laurens van der Maaten, Zeki Yalniz, Yixuan Li, and Dhruv Mahajan. De- fense against adversarial images using web-scale nearest-neighhor search. arXiv preprint 1oX3v:1903.01612, 2019.
Reuben Feinman, Ryan R Curtin, Saurabh Shintre, and Andrew B Gardner. Detecting adversarial samples from artifacts. arXiv preprint arXiv: 1703.000 10, 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, pp. 2672-2680, 2014a.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 142.6274 2014b..
Will Grathwohl, Ricky TQ Chen, Jesse Betterncourt, Ilya Sutskever, and David Duvenaud. Ffjord: Free-form continuous dynamics for scalable reversible generative models. arXiv preprint /80.03//1 2018.
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens Van Der Maaten. Countering adversarial images using input transformations. arXiv preprint arXiv:1711.001 17, 2017.
Andrew Ilyas, Ajil Jalal, Eirini Asteri, Constantinos Daskalakis, and Alexandros G Dimakis. The robust manifold defense: Adversarial training using generative models. arXiv preprint 17Xi::712..099900 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:14/2.6988) 2014.
Diederik P Kingma and Max Welling. 1rXiv:1312.6114 2013.
Auto-encoding variational bayes. arXiv preprint
11

---

Published as a conference paper at ICLR 2020
Durk P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolutions, In Advances in Neural Information Processing Systems. pp. 10215-10224, 2018.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint 1607. 02233,, 2016a.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint urXiv:161..01236. 2016b.
John M Lee. Introduction to smooth manifolds. Graduate Texts in Mathematics, 218, 2003.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 3kkv:1706.000833 2017.
Seyed-Mohse Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: a simple and accurate method to fool deep neural networks. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pp. 2574-2582, 2016.
James R Munkres. Topology prentice hall. Inc., Upper Saddle River, 2000.
Andrew Y Ng and Michael Jordan. On discriminative vs. generative classifiers: comparison of logistic regression and naive bayes. In Advances in Neural Information Processing Systems, pp. 841-848, 2002.
George Papamakarios, Theo Pavlakou, and lain Murray. Masked autoregressive flow for density estimation. In Advances in Neural Information Processing Systems, pp. 2338-2347, 2017.
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. 2016 IEEE European Symposium on Security and Privacy ( (EuroS&P) P). pp. 372-387. IEEE, 2016.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pp. 506-519. ACM, 2017.
Xavier Pennec. Probabilities and statistics on riemannian manifolds: Basic tools for geometric measurements. In Nonlinear Signal and Image Processing, pp. 194-198. Citeseer, 1999.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:1511.06444 2015.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. arXiv preprint 0r01v:/801.09. 2018.
Danilo Jimenez Rezende and Shakir Mohamed, Variational inference with normalizing flows. arXiv preprint arXiv:1505.05770 2015.
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan: Protecting classifiers against adversarial attacks using generative models. arXiv preprint arXiv: 1805.066550 2018.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. arXiv preprint arXiv: 10571, 2, 2017.
Yang Song, Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models to understand and defend against adversarial examples. arXiv preprint wwX.vv1110..0110 2017.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks, arXiv preprint arXiv:1312.6199, 2013.
Thomas Tanay and Lewis Griffin. boundary tilting persepective on the phenomenon adversarial examples. arXiv preprint arXiv: (608:::600000000 2016.
12

---

Published as a conference paper at ICLR 2020
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, lan Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint arXiv:1755.07204, 2017.
Weinan. A proposal on machine learning via dynamical systems. Communications in Mathematics and Statistics, 5(1):1-11, 2017.
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. arXiv preprint 1711:997,, 2017.
Linfeng Zhang, Lei Wang. et al. Monge-amplere flow for generative modeling. arXiv preprint arXiv: 10188, 2018.
Junbo Zhao, Michael Mathieu, and Yann LeCun. Energy-based generative adversarial network. arXiv preprint arXiv:1609.00m 1 2016.
Xiaojin Zhu and Andrew B Goldberg. Introduction to semi-superrviee learning, Synthesis Lectures on Artificial Intelligence and Machine Learning, 3(1):1-130, 2009.
13

---

Published as a conference paper at ICLR 2020
A
MATHEMATICAL BACKGROUND
A. GENERAL TOPOLOGY
We introduce definitions and theorems related to general topology appeared in the paper. For more details, all the definitions and theorems can found Munkres (2000).
Definitions in general topology. We first provide the precise definitions of the terms we brought from the general topology.
Definition (Topological space), A topology on a set X is a collection T of subsets of X having the following properties.
1. 2 and X are in T.
2. The union of the elements of any subcollection of is T.
3. The intersection of the elements of any finite subcollection of T is in T.
set X for which topology T has been specified is called a topological space.
For example, a collection of all open sets in R" is a topology, thus 1e is a topological space. If topology be constructed by taking arbitrary union and finite number of intersections of smaller collection B of subsets of X, we call B a basis the topology.
Pick metric d in R" and consider B set of all open balls in I" using the metric d. The topology of R" can be constructed by taking B as basis. When this construction is possible, metric d is said to induce the topology.
Definition (Metrizable space). If a topological space, is said to be metrizable there exists metric d the set X that induces the topology of X. A metric space is metrizable space X together with a specific metric d that gives the topology of X.
Since R" is equipped with Euclidean metric that induces its topology, RR" is metrizable.
Continuity and the extreme value theorem. Let X and Y be topological spaces. In the field of general topology, a function f X + Y is said to be continuous, if for any subset V open in Y, its inverse image f-V(V)
open in X. Moreover, if a continuous bijection whose inverse is also continuous, f is called a homeomorphism. The notion of homeomorphism is important as it always preserves topological property, e.g., connectedness, compactness, etc., and this will be used in the further generalization of Theorem
Here, we only introduce the generalized statement of extreme value theorem.
Theorem (Extreme value theorem). Let f X + Y be continuous, where Y is an ordered set. If X is compact, then there exist points x and x in X such that f(x) fx) f(x) for every x X.
Specifically, if manifold M is compact subset in IR.,, we may use X M and Y R.
Normal space and Urysohn's 's lemma. The Urysohn's 's lemma was used to prove the Corollary We first introduce the notion of normal space.
Definition (Normal space). Let be a topological space that one me-pointt sets in X are closed. Then, X is normal if for each pair A, B of disjoint closed sets of X, there exist disjoint open sets containing A and B, respectively.
Urysohn's 's lemma is another equivalent condition for space be normal. Theorem (Urysohn's 's lemma). Let X be a normal topological space: let A and be disjoint closed subsets in X. Let [a, 6] be a closed interval in the real line. Then there exists a continuous map
f : X
[a,b]
such that fxx = for every x in A, and f(x) 5 for every x in B.
To apply this lemma to IR"", we only need the following theorem.
Theorem 5. Every metrizable space normal.
Since R" is metrizable, is a normal space by Theorem Therefore, we can apply Urysohn's lemma to any pair of disjoint subsets in I to show the existence of continuous map f: X [0, 1].
14

---

Published as a conference paper at ICLR 2020
A.2 DIFFERENTIAL GEOMETRY
We provide the definitions from differential geometry (Lee 2003 used in the paper.
Manifold and tangent space. Formally, topological manifold is defined as follows.
Definition (Manifold). Suppose M a topological space. We say M is a topological manifold of dimension if it has the following properties.
1. For any pair of distinct points X1,X2 M, there are disjoint open subsets U1, U2 M such that X₃ U and X2 V.
2. There exists a countable basis for the topology of M.
3. Every point has neighborhood U that is homeomorphic an open subset Ü of IR
There are different ways to define tangent space of k-dimensional manifold M. Informally, can be understood as geometric tangent space M IR" point M, which collection of pairs (x, v) where v is a vector tangentially passing through x. Here we put a more formal definition of tangent space. Consider a vector space C (M). a set of smooth functions on M.
Definition (Tangent space). Let be point of a smooth manifold M. A linear map X C (M)
R is called a derivation al x if it satisfies
= (xx)
for all f,ge CO
The set of all derivations of C (M) at x forms vector space called the tangent space to M at x, and is denoted by (MM).
Riemannian metric. As tangent space (MM is vector space for each e M, we can consider a inner product 9bfr defined on (M).
Definition 10 (Riemannian metric). Riemannian metric g on smooth manifold M smooth collection of inner products 9x defined for each Tx (MM. The condition for smoothness of is that, for any smooth vector fields X, y on M, the mapping x ++ 9x xx1x))/xx))
manifold M equipped with a Riemannian metric g called Riemannian manifold.
B EXAMPLES
Computing density PM over Riemannian manifold M. This section presents example compu- tations of the probability computations from Section and and Section 3.2 As concrete example of computing density over a manifold, we use the following simple manitolds, so called two-moons in R
[2)
cas
[0,=]]
22 sin
(z)
21 = cos 22 sin
for f [0.
We take M Mo u Mj our example manifold. Figure 6a shows the manifold of two-moons dataset plotted in different colors: My in red and M2 blue. First recall the following equation (equation from the Section D.I
S pM (x)
S.ep PM (M (eelxxx)]]
where [αx(w)] is the x matrix representation of the inner product 9x(u) at X(u) e M.
Especially, when a manifold in Rn of dimension ie.. parameterized curve 7 [a. b] + R², the integration (8) can be written in simpler way.
Se pM (x) S.". (M((())))
(5)
where 71()) is the nd-dimensional velocity vector at e [].
15

---

Published as a conference paper at ICLR 2020
42
(a) Plot of the two-moons mani- fold in R
(b) Extended density function over R2 from the two-moons dataset
Figure 6: Density extension example from two-moons manifold.
Let PM be a probability density function defined on M. As M is composed of disjoint manifolds Mo and M1. we consider conditional densities po: P1 as follows.
PM PM (x)
pn(x) PM X Mo)
Pr[x e Mg]
(6)
pi(x) = ( Mi) Parlas, (x)
Pr|x Mi]
Here, PMMM, and PMlM, represent the density function pM with its domain restricted to Mo and M, respectively. By our definition of data-generating manifolds, Pr[x e M.] corresponds to the probability of data generation for class i.e. Pr[y i]. For concrete example of such density, uniform density for each manifold M; be defined as (x() for all x M..
Note that each manifold has parameterized curves in R²2
?o 6 - (cos 0, sin 0)
?1 : - cos 0, sin 0 0.5)
with constant speed [+) (0)] at all [0. T.. Therefore, from equation (5)
f parl ( (x))Mo(xx {" pM (no(()))
A-D
f PM (0)
parlar, (x)dMi
For any measurable subset s M, the probability for an event that x is in can be computed as follows.
[
Pr|x e A]
xCAMM (x(
S parlas (x)dM1(x)
XaAndo Pul (x)dMo(xx)
Seqann PM (70()))
/dqool Parla, ( (: 31(deed
Pr[x Mo]]
lojo..] po(To(0))d0 70l0)ed
Pr[x Mi]
01 (1))) 2(0)cd
( 6
Pr|x Mo]
1d0 Pr[x Mi] (0)e
0l 1d0 2s (0)ed
We can briefly check all the requirements
R1
(R2) and R3
The computation of Pr[x A is
based on (R1) so (R1)
is satisfied trivially. Also, Pas is a function defined only on M, thus ( [R2) is
clear, i.c. supp(pm)
{x R" p(x) 0} = M. To check R33) when A M,, computing this
integration will result in the exact probability Pr[x e M,] Prly i]. so when A M, computing the integration will result in Pr[y = 0] + Pr[y 1] 1, as desired in the requirements.
16

---

Published as a conference paper at ICLR 2020
Extending density to R". We extend the domain R" for the example of two-moon. In Section we defined the noise density function to satisfy the following requirement.
3
(R0)
The translated noise density function, Px(x- - chosen for given X. Given x,, = X, since adding noise n is the only way generate by perturbing Xo. p( X x, x) is equal to (2xnn)
(xxx-xx x). is the density of noise = x x being
Under a proper noise density function, We show an example construction of the density extended from M satisfying the requirement (RO) For simplicity, we choose isotropic Gaussian distribution, N(0, o² with the standard deviation a for each dimension as the noise density function Vxx for all M. Such noise density Vx defined in Ix can be written follows.
1xx 1
(nx) V2T0²
exp
2x²
By putting = 8- x to density equation above,
p(x)=
Seess
exp
(-18-x18 2a²
(x)dM))
22T022
Specifically, We assume an isotropic Gaussian distribution with a 0.05 as the noise density Vxc for all e M.
By the equation
I we have the following computation of density on x.
Shen vx(* (x)Mx()
(x))
Seemo ux(8 (x6-x)pMlMM (x))MM))) Sr JX Ux(# x)pM(M)) (x)dM
Son ux ()
S. ux (
= -Pfxx Mo] Jor 1x(2 x))o(70(0))
+ +P((x Mi] f ux(8 x)pi (71()d)) (::
Pr[xe Mol
Mol
S Jan
exp
| x
12
d0
2
20²
S" exp
X x 1
+ Pr(xx Mi]
8-00
2r²
We can also check that the requirement (RO) satisfied by the construction; our construction (equation ① is based on (RO) The computed density is shown in Figure 6b
C
PROOFS
In this section, we provide the proofs for statements that appeared in Section
C.1 PROOF OF THEOREM 1
To begin with, pick a value X such that the X-density superlevel set Lug. is nonempty for all x e M. As noise densities vx described in Section 4.1, it is safe to assume that both X-bounding radius òx maXxeM &x,A and X-guaranteeing radius e minlxMM Ex,A exist.
Then, we can prove that, with proper choice of threshold X, the X-density superlevel set includes the data-generating manifold.
Lemma 2. Assume that noise densities have radií in Definition for all x M and small enough >> 0. Then, for any x M, the density p(x) is least W, i.e. pxx) w. where ex.
Proof. By Lemma 1
x' E B.(x) - xx(xxx>== (xy (:6=6))
= -x(xxx)2 2
17

---

Published as a conference paper at ICLR 2020
Then, can lower bound the density PM (x) follows.
Sreat vx (x (xXxx))M (N
p(x)=
SrEEmBEd vx x (' (dd)(((2)))
SVCMAR, pa pxr(x)dM(x
[X'E Bc(x)] X'EM 2 w.
This lemma shows that the thresholding the extended density p with threshold X s w.d guarantees the superlevel set to include the entire manifold M.
Corollary 2. For any threshold X w the corresponding X -density superlevel set Lp.x of the extended density includes the data-generating manifold M.
Similarly, we show that, with a proper choice of threshold A, each connected component X-density superlevel set contains most one manifold.
Lemma 3. Assume family noise densities satisfies the assumptions Section 4.1 Let À > 0 be value such that the X-density superlevel set L is nonempty for any M. Also, let 5 8x be the maximum X-bounding radius over M. Then, for any & & (MM the extended density value is smaller than X, i.e. p(&)= X.
Proof. By Lemma] M
& No(M)
= x Ba(x)= = Bs, (x) for any x M (x6=
1x xxxx > for any x M
Then, upper bound the density pl (x) follows.
p(x) S ux (x)
ʃ pa (x)dx((( No,
xeM
This lemma says that the X-density superlevel set is included by the 5-neighborhood N&(M) of the data-generating manifold M.
Now, we can deduce the following main result.
Theorem 1. Pick any X A threshold value satisfying the Corollary 2 If the class-wise distance of data- setitaageeeatinnggg manifold is larger than 28* where 8* 5x (the X --bbunning radius), then the superlevel set Lp. satisfies the followings.
I.p. contains the mata-generating manifold M.
* Each connected component of Lp.x* contains at most one manifold M; of class i.
Proof. The first property is a direct application of Corollary for X* w.
For the second property, since the class- wise distance M is larger than 28*, the -e-neighborrood of manifolds are pairwise disjoint, i.c. N& (M,) Ng (M2) Ø for each i Therefore, No (M) has exactly connected components N;- Ng- (M,)'s.
By Lemma 3 8 -r-neigbborhood Ns- (M) contains the superlevel set Lp.x,, thus each connected ss Since M contained in Lp each M, is contained
component of Lp.x- is exactly one N,'s. in some connected component C' of Lp.>- which is in N;. Then, for any j # i, M, & C N,, since M, is in N, which is disjoint to N,. Therefore, a connected component C contains a manifold M.. then it cannot contain any other manifold.
18

---

Published as a conference paper at ICLR 2020
C.2 PROOFS FOR SECTION 4.3
Theorem 2. Let Z be a mixture of nz multivariate Gaussian distributions, and let Dx be the target distribution from a generating manifold with nx manifolds. Let G be continuous generative model for Dx x using latent vectors from Dz. Assume the Theorem I is satisfied, and let X be the threshold value from the Theorem connected components.
G( do not agree on the number of If rzz nx, LX and L
Proof. Since L is the results of Theorem nx-
| the number of connected components of L is at least
However, since D is a mixture of Gaussians, for any value of À (including the special case À = A*), T can never have more than ni connected components. Since G is continuous, preserves the number of connected components, thus L _xx) [) G(L has at most nz connected components. As nz < nxx L and LXx ((2) can never agree on the number of connected components.
G(Z). Corollary 1. If Theorem is satisfied, there is point & é I"" such that & / L but & L
Proof. Since ng < nx, there exists a connected components E of (( containing least two connected components of S,,,, Without loss of generality, assume contains exactly two connected components C' and C". By definition, X-superlevel set closed set, so C and C' are disjoint closed sets. In Euclidean space IR",, the Urysohn's 's lemma tells us that for any disjoint pair of closed sets A, A' R"" there is continuous function f such that fxx(x) and [] = for any x IR". Especially, when A = C and A' C", there exists continuous function f such that,
*f(x) 0 for all x in C
* f((x) 1 for all x in C"
Consider S f-1 which is a separating plane separating C and C². Ié Ø, then Čns- - [0, 2) and Cn - (2 1] will be two open set in subspace Č whose union is Ć. This implies that O is disconnected, which is contradiction. Therefore, Ö should be nonempty, and any point x in Ô S not LX.
D FURTHER DISCUSSIONS
D.1 COMPUTING DENSITY OVER A DATA- GATA-GENERATING MANIFOLD
When M is Riemannian manifold equipped with Riemannian metric g, we can compute probabili- ties over M. There are two essential components of probability computation: (a) a density function PM and (b) measure dM over M. We assume PM and dM satisfy the followings.
(R1) For any measurable subset A c M, i.c., Pr[x A] = fxe A PM (x) (x).
(R2) is zero everywhere out of M, i.e., supp(pm) = {x E IR" PM (x) > 0) _ M
(R3) For any (x, 3), x is sampled from M, if and only if y i.c Pr[x M.] Pr(y= i]
When equipped with such PM and dM, we call M as data-generating manifold.
Probability over a Riemannian manifold. We show how to compute a probability of x being generated from Riemannian manifold M. We assume a k-dimensional manifold M equipped with Riemannian metric 9. family of inner products Ix on tangent spaces M. In this case, 9 induces the volume measure d.M for integration over M. If M is parameterized by X(u) for g R the integration of a density function PM on M is as follows.
S pr pM (x)
S.
pa (X (
(8)
where [gx(w)] is the x matrix representation of the inner product 9x(u) at X X(u) e M. In Appendix concrete example of this computation will be provided.
19

---

Published as a conference paper at ICLR 2020
D.2 DENSITY EXTENSION OF THE SECTION 3.2
This section introduces some remaining discussions regarding our data-generating process from -ata-gener manifold.
Relation to kernel density estimation. While this extension is computing the density of compound distribution, it can be interpreted as computing expectation over a family of locally defined densities. Such an expected value can be observed in previous approaches of density estimation. For example, if Ux is isotropic Gaussian for each x, the above integration is equivalent to the kernel density estimation, with Gaussian kernel, over infinitely many points on M.
Observed property of the extended density. In Figure 6b in Appendix B we can observe that the extended density achieved higher values near the sata-generating manifold. We formalize this observation to discuss its implication to the INC approach.
Let d(x; (x, M) to the minimum distance from & to the manifold M.
(C1) For any given &, letyy y be the class label whose conditional density p(xly = y+) dominates p i) for i y".
y argmax HI(
and let My be the manifold corresponding y" (C2) For y² satisfying (CL)
choose y" such that the distance of & from the manifold
M,-) is the smallest.
If there multiple y" satisfying both of (1)) and (C2) expect the following property be true for all of those y²
(P1) Consider the shortest line from & to the manifold My.. As X goes closer to My along this line, & should be more likely to be generated the influence of noise decreases when moving away from the manifold. Therefore, we expect our density PM to have the following property.
x' c arg min d(x,x) xeM,
(10)
p(x) s p(((1 X)* >x") for all X [0,1]
Actually, this provides another justification of INC. In reality, the density conditioned by the label is not available even after running a generative model, so finding y with (CT is relatively hard. If we only consider (C2) without filtering y" via (CI) we are finding point x . achieving the minimum distance to X, which is the optimization (TT) above. Then projecting & to the x", i.c. the solution of the optimization 11 can be explained by 10 when À 1, p the highest along the shortest line between & and x"
D.3 SUFFICIENT CONDITIONS FOR THE EXISTENCE OF RADII
We discuss the sufficient conditions guaranteeing the existence of radii introduced in Definition Those sufficient conditions are derived from natural intuition about the properties of distributions in most machine- learning contexts.
The first intuition is that the influence of noise should diminish as observed sample x moves away from source point x,, Therefore, we formalize the noise whose density decreases as the noise = & x, gets bigger. We formalize boundedness of noise densities via the boundedness of their X-density superlevel sets and continuity of noise density via the continuity of individual Px.
Definition 11 peenter-peaked noise density). Noise density functions V are center-peaked, if for any source point x M and any noise vector n E IR" with i > 0, Px (n) < (x(An) for all X E [0, 1). Definition 12 (Bounded noise density). Noise density functions vx are bounded, if X-density superlevel set is nonempty, there is a radius 8 by which the X-density superlevel set is bounded, i.c.,
LyN.1 (0) where (0) is the closed ball of radius 8 centered at 0.
Definition 13 (Continuous noise density). Noise density functions Vxx are continuous, 1/x is continuous in R",, for any M.
20

---

Published as a conference paper at ICLR 2020
Under the conditions above, the radii in Definition 1 Jawwys exist.
Proposition 1. If noise densities are center-peaked, bounded, and continuous, any nonempty X-density superlevel set L has both A-bounding radius 6x.x and X-guaranteeing radius <x,
Proof. Let Xx be center peaked, superlevel set bounded family of continuous noise densities. Since Vxx is continuous, superlevel set L vx" [A, oo) is closed as an inverse image of Vxx Therefore, its boundary v is contained in Lv
Because Vx is superlevel set bounded, superlevel set I is bounded by a closed ball () with radius 6 2 0. Since 1x is center peaked, nonempty superlevel set L always contains 0 as the maximum is achieved O. Moreover, there exists closed neighborhood ball (0) with radius O contained in the superlevel set Tyg. Now it is enough to show that the minimum of and the maximum of exist.
Since Lu is bounded, its boundary ÖL,,.> is also bounded. a is closed and bounded, thus it is a compact set. Therefore, the Euclidean norm, as a continuous function, should achieve the maximum F and the minimum y on θL by the extreme value theorem. From the choice of 8 and e, we can get,
Therefore, can find the minimum 8x,1 7 and the maximum 6x,A L.
D.4 GENERALIZATION OF THE THEOREM 1
We try generalizing the Theorem 2 to handle more concepts in topology. Theorem 2 fact that the number of connected components of X-density superlevel is preserved by continuous generative model G.
mainly uses a
In algebraic topology, each connected component corresponds to a generator of O-th homology group Ho. and continuity of a function is enough to preserve each component. In general, generators of i-th homology group H; for i > are not preserved by continuous map, so we need to restrict further. By requiring G to be a homeomorphism, we can safely guarantee that all topological properties are preserved by G; therefore, we can generalize the Theorem 2 with a homeomorphic generative model G.
To generalize the proof the Theorem
2 we first provide the sketch of the proof.
X -density superlevel set T. mixture of nz Gaussian distributions has at most nz connected components.
(2) Since G is continuous, the number of connected components of (Z. G(LZ.) is same to the number of connected components of T. so it is also at most nzzz
(3) We choose X* so that L is included in 8* -neighborhooo of M.
(4) By assumption on the class-wise distance of M, 8" -nighhbbooooodd of M has exactly same number of connected components to M, i.e. nx. Therefore L has at least n connected components.
(5) By (2) and (4) conclude that T.C. (7) and X.X do not agree the number of connected components as long as r2 nx
In this proof, nz corresponds to the maximal 0-th Betti number of L i.c. the number of generators of Ho(L..). If we keep using mixture of Gaussians as latent vector distribution, all components of L are contractible, so we may use 0 as the maximal i-th Betti number.
Also, n. corresponds the 0-th Betti number of M and worked the minimal 0-th Betti number of LX The condition on the class-wise distance of M is used to ensure to be a lower bound. Combining these observations, we can get the following generalized statement.
Theorem 3.
Let Dz be mixture of multivariate Gaussian distributions, and let D.x be the target distribution from Mata-generating manifold M. Let n, be the i-th Betti number of M.
Consider generative model G is used approximate Dx using the latent vectors sampled from Dz. Assume that G is a homeomorphism from IR" to itself. Assume that data tatta-generating manifold satisfies the conditions of the Theorem and let X* be the threshold value that X corresponds
21

---

Published as a conference paper at ICLR 2020
to that superlevel set. Assume that for some j the homomorphism 1* induced by the inclusion
:: + N8. (M) is injective.
If 0 ng. LX and Lxx"
G(2) do not agree on the number of connected component.
Proof. Since LX. is the results of Theorem | it includes M and included by -eighooorooo
No- (M) of M. Define inclusions 11,44 as,
* M + X
* -x + No- (M)
Clearly, L 12 11.
Let if and l be induced homomorphisms of (1 and l2, resp.
By the assumption, any generator [a] in (MM is injectively mapped to a nonzero generator 1" ([a]) in (N (M)). Therefore, the j-th Betti number of Na- (M) is equal that of M, i.e. ny. Note that j-th Betti number is the rank of j-th homology group rank (N& (M))) Because 12 is a homomorphism from H, (L ) to Hj (Nx+ (M)), rank(L 2 rank(H, (No (M))). Therefore the j-th Betti number of T at least Vi-
However, since Dz is mixture of Gaussians, for any value of X (including the special case À X²), 4X does not have any generator of j-th homology group, so it has j-th Betti number 0 for all j> Since G is homeomorphic, it preserves all the Betti numbers, thus _((²) G(L has the
same j-th Betti number. As 0 ny, LX and G(2) can never agree on the number of connected components.
In Section 5.2 we see the Figure from the circles dataset, which is a remarkable example that (2) has the same number of connected components, but does not have any loop (non-contractible eircle). This is empirical evidence of Theorem 3 so it is explained by mismatches in the topology of distributions. Each concentric circle has Z as its first homology group as circle contains exactly one generator. However, latent vector distribution always has trivial first homology group, as any superlevel set of a mixture of Gaussians is set of contractible connected components.
D.5 DETAILS OF INC IMPLEMENTATIONS IN THE SECTION 5
INC implementation. We start from introducing the optimization for the ideal INC projection when the generatinn manifold M available.
x" arg min d(x, x)
(11)
xtii
where d is a metric defined on the domain X. If perfect classification on M is assumed (model is well- trained on M) and X is close enough to the manifold of correct label, classification f(x") (xx) is likely to be correct, since x" is likely lie on the correct manifold. Since the data-generating manifold M is unknown, the INC approach runs the following optimization with before the classification.
G(z') where arg min dl (2))))
(12)
z-Dz
where d a metric defined the domain X.
When INC is implemented with reversible generative model G, for any given & R" there exists
trivial solution z' = G (x) to the optimization (12). achieving d(G(z" (z" ). x) = 0. This is even true
for x out of the manifold, resulting in the situation that the output x* G(z" X is still out of the data-generating manifold.
To manage this problem, we add another term penalizing a low density of latent vector to the objective function. Thus, in INC implementation, solve the following optimization problem.
x" G(z') where arg min [d(C(z), 2-D2
a(M pz [z))]
(13)
Any generator of the j-th homology group (M(M) of M is mapped to nonzero generators of the j-th homology group Hy(Ng (M)) of 8 neighborhood of M.
22

---

Published as a conference paper at ICLR 2020
where is the regularization factor and M is the maximum possible value of the density pz of the latent vector distribution. For the choice of regularization factor, we used the same value a = during the entire experiment.
To solve each optimization problem, we used the built-in adam optimizer (Kingma & Ba 2014) in Tensorflow package. For optimization parameters, ran 100 iterations of adam optimizer using learning rate 0.01 with random sampling of z.
When implementing INC using class-aware generative model, used the following strategy to improve its robustness.
As the class-aware generative model generates each manifold from each Gaussian compo- nent, we first sample initial points from each manifold by randomly choosing latent vectors 21....: Ze from each Gaussian component.
We run INC for i-th manifold by solving the following optimization.
G(z,) where z arg min [d(G(z), z-Dz
where M; is the maximum value of i-th Gaussian component. The regularization term is designed to penalize z which unlikely to be generated by i-th Gaussian component, so we only search in the range of i-th Gaussian component, i.e., i-th manifold.
We choose the final solution x; achieving the minimum , x), breaking ties randomly.
Since each search is performed only on each submanifold, the artifact observed in Section 5.3 never appears during the optimization process. Also, choosing initial points from each manifold prevents the initialization problem mentioned Section 5.3
D.6 DISCUSSION ABOUT THE LIMITATION OF TOPOLOGICAL INFORMATION
Given sufficient number of connected components in the latent vector distribution, does the class- aware training suggested in this paper result in a generative model that achieves manifold separation? For this question, the answer is no, and the manifold separation depends other factors, e.g., alignment of latent vector distribution, choice of training parameter, etc.
Mixture 2 Gaussians =
Two-moons: Class-aware
3
2
1
0
-1
-1
-2
2
-3
3
33
(a) Superlevel of Dz
(b) Superlevel set of Dc(z)
Figure 7: Failure cases of class-aware training.
Figure 7b shows the superlevel set Da(z) from a class-aware training to learn the two-moonss dataset when latent vector distribution mixture of two Gaussian distributions aligned horizontally (Figure 7ap. is clear that in this case, the generative model induced a connection artifact even when the class aware training was used.
We explain this by interpreting reversible generative models as dynamical systems (Weinan 2017 Chen al. 2018 Grathwohl et al. 2018 Zhang al. 2018). To elaborate, reversible generative
23

---

Published as a conference paper at ICLR 2020
model can be viewed dynamical system moving the latent vector distribution to the target distribution continuously in time. When two Gaussian mixtures are aligned vertically, a reversible generative model is likely to learn how to move the upper (and lower) Gaussian distribution toward the upper moon (and the lower moon, respectively), without being affected by the entanglement of two moons. However, moving the left (and right) Gaussian distribution toward the left moon (and the right moon, respectively) continuously in time is required to avoid the entanglement of two moons during the transition. This case alludes that information about the topological properties may not be enough to learn a generative model separating manifolds, because it does not provide an understanding of information about how data- sata-generating manifolds are aligned.
MORE EXPERIMENTAL RESULTS E
We present more experimental results about the INC performance comparing topology-aware genera- tive model to its topology-ignorant counterpart.
Histogram for projection error distributions in 5.4 Figure presents the histogram of the projection errors distributed from 0 to the diameter of the distribution. Each row corresponds to each dataset, whereas the first column and the second column represent the results from the topology- ignorant model and the topology-aware model, respectively. All histograms are normalized so that the sum of values adds up to 1. To explain, the y-axis of each histogram the estimated probability that INC achieves the projection error the z-axis. Not only can we observe the improved mean of projection errors the histograms, but we can also check the reduced standard deviation, i.c. we get more consistent projection errors the mean.
Two-moons: Class-ignorant
Two-moons: Class-aware
100
1.0
0.8
0.8
Estimated
probabiiiy
Estimated probability
0.6
0.6
0.4
Projection error
Projection error
(a) Two-moons, topology-ignorant
(b) Two-moons, topology-aware
Spirals: Class-ignorant
Spirals: Class-aware
1.0
1.0
0.8
Estimated probabiity
Estimated probability
0.6
Projection error
Projection error
(c) Spirals, topology-ignorat
(d) Spirals, topology-awar aware
Circles: Class-ignorant
Circles: Class-aware
1.0
0.8
Estimated grobabiity
Estimated probabiltt
0.6
0.0
0.0
0.5
1.0
2.5
3.0
0.0
1.5
2.0
2.5
Projection error
Projection error
Cireles, topology-ignorant
(f) Circles, topology-aware
Figure 8: Histograms of the projection errors of INC. Each y-axis represents the estimated probability that INC incurs the projection error on the corresponding r-axis.
24


Reviews:
[{"review_id": "Skg5fxnRYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper argues that defenses against adversarial attacks need to be stronger than they currently are. Defenses that use generative models assume that there exists a manifold of data that is modeled by a trained generative model that can be used to project any out-of-manifold data unto the manifold. However, this work argues that if the generative model does not model the topology of the manifold, it can still be fooled by an adversarial example. They argue that a generative model needs to be at least aware of the number of connected components of the data-generating manifold. If the number of connected components does not match, based on theorem 2, Corollary 1 argues that a generative model can generate an adversarial example that does not exist in the data-generating manifold.\n\nPros:\n- To the extent I checked, proofs are correct.\n- The experimental results support this result on 2D toy manifolds. They show how a prior defense based on generative-models (INC) fails on the toy problems and show how a modification to INC can improve it.\n\nCons:\n- In their experiments, they use the number of classes as an approximation to the number of connected components (Appendix E) and train class-conditional generative models. Some of these details are better to be put in the main text.\n- There are no experiments beyond toy examples on high-dimensional problems and datasets. It should not be too difficult to have some preliminary results using the proposed extension of INC on MNIST or CIFAR10.\n\nAfter rebuttal:\nI have raised my score after authors improved to quality of the text. Even though this work does not have empirical results on high-dimensional datasets such as MNIST or CIFAR10, it has a nice theoretical contribution useful for finding stronger defenses against adversarial examples.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJe4ZU5t9r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper tries to answer the following question:\nIn adversarial defense training do manifold based defenses need to know the structure of the underlying data manifold?\nThe question is quite rhetoric (the answer is most probably yes), nevertheless, the paper provides a theoretical and empirical answer.\n\nThe paper reads well and it is interesting to read. Nevertheless, I have a very basic question regarding the usefulness of the methods that the paper studies and the topic of adversarial defenses. I have worked on the topic for some years and in the beginning, I found it quite interesting, until I realized that, at least for images, audio, 3d meshes, all adversarial attacks can be very easily addressed with simple denoising mechanisms (for images even a non-local means filter or even a Gaussian filter eliminated all the adversarial attacks I have tried). There are some recent papers that demonstrate this [A] or recently feature denoising [B]. Why denoising is not enough to pull the data back to the data manifold (e.g., general low-rank data denoising or general denoising suitable for the data under investigation)?  \n\nI really want a discussion about that before I make a final decision.\n\n[A] Defensive denoising methods against adversarial attack\n[B] Feature Denoising for Improving Adversarial Robustness", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BkxjO615FH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I. Summary of the Paper\n\nThis paper studies robustness to adversarial examples from the\nperspective of having 'topology-aware' generative models. Next\nto some experiments on data sets with a manifold structure, the\nmain contribution of the paper is a tandem of theorems that state\nthe conditions under which models can recover the topology---or\nthe number of connected components---of a data set correctly,\nthereby making them more robust to adversarial examples.\n\nII. Summary of the Review\n\nThis paper provides a novel perspective on adversarial examples through\nthe lens of Riemannian Geometry and topology. I appreciate novel\nresearch that employs topology-based methods, but at present, I cannot\nfully endorse accepting the paper. Specifically, I see the following\nissues:\n\n- Missing clarity: while the appendix is very comprehensive, which\n  I appreciate, the main text could be improved; some statements appear\n  redundant, while others need to be re-formulated to build intuition\n\n- This paper appears to span both theory and applications. I appreciate\n  this attempt, knowing full well that this is no easy feat to\n  accomplish. However, the main theoretical result on the number of\n  connected components only applies to mixtures of Gaussian\n  distributions, but the purported scope of the paper is the analysis of\n  manifold-based defences in general. I would expect a more in-depth\n  discussion of the limitations of the theorem. Can we expect this to\n  generalise? Moreover, 'topology' is reduced to 'connected components'\n  in this paper. While this is perfectly adequate in the sense of\n  connected components being a particular concept from topology, I would\n  expect this to be clarified much earlier in the paper. In addition,\n  connected components are a very basic and coarse concept, so I am\n  wondering to what extent it is sufficient to describe models purely\n  based on that information.\n\n- As a sort of corollary to the previous point, the experiments could be\n  improved. I like the idea of employing known data sets with a simple\n  manifold structure, but the setup is somewhat preliminary; I would\n  prefer to see an analysis of border cases or limit cases in which the\n  theorem _almost_ applies (or not); plus, a more in-depth analysis of\n  stochastic effects during training: do _all_ models end up being\n  robust if their number of connected components is sufficiently large?\n  Is there a dependency between the number of connected components and\n  vulnerabilities---are models with a very small number of connected\n  components more vulnerable than models with a very larger number of\n  connected components? The present experimental section is lacking this\n  depth.\n\n- The same statements apply to the INC example. I found this super\n  instructive, but it is only _one_ case on _one_ manifold---I would\n  like to see more details here; maybe some of the experiments in the\n  appendix could be moved to the front? I have some suggestions for\n  shortening the paper (see below).\n\nDespite these issues, I think this paper can be a strong contribution if\nproperly revised; since I am positive that at least some of these\nsuggestions could be performed within a revision cycle, I want to be\nupfront and state that I will definitely consider raising my score,\nprovided that my concerns are addressed appropriately!\n\nI have to state that I am _not_ an expert in adversarial examples, but\nan expert in topology-based methods; I consider this paper to belong to\nthe latter field given its theoretical contributions about 'recovering'\nthe correct density distribution.\n\nIII. Clarity\n\nThe paper provides an extensive background to Riemannian geometry, which\nI appreciated as a reference. Nevertheless, there are improvements to\nthe main text that I would suggest:\n\n- Please consider changing the title to 'On the need...'\n\n- The manifold assumption is that data lie _on_ a manifold or _close to_\n  a manifold whose intrinsic dimension is much lower than that of the\n  ambient space. This is not stated in sufficient precision in the\n  paper; please correct the usage on p. 1 and p. 2\n\n- In terms of notation, why use $p_M$ to denote the density on the whole\n  of $\\mathds{R}^n$? I would expect $p_M$ to refer to the density on $M$\n  rather than the density of the whole space.\n\n- If $M$ is a disjoint union of manifolds, please consider using\n  a '\\cupdot' operator to make this more clear.\n\n- If the pairwise manifolds are disjoint, how can the resulting data\n  distribution still contain any ambiguities? I find this hard to\n  harmonise with the statement in Section 3.4 about the existence of\n  a classifier that separates the manifolds. Please clarify the meaning\n  behind the term 'ambiguities' here.\n\n- The '(R0)' requirement definition and the discussion in Section 3.2\n  strike me as needlessly complex. Would it be possible to shorten this\n  or move some content to the appendix? I think it would be sufficient\n  to have Eq. 1 and mention how it could be solved.\n\n- Section 3.3 could be shortened as well, if I am not mistaken; while it\n  is good to know how such models look, the 'change of variable formula'\n  is not used directly any more in the paper; I think it might be easier\n  to write down a generic form of the density for each model.\n\n- The salient points of Section 3.4 seem to be the projection point;\n  maybe this could also be shortened somewhat in the interest of having\n  more space for experiments. The relevant information of this section\n  was to learn how projections work for different models, but it would\n  be sufficient to keep Eq. 3 and discuss Eq. 4 in the appendix\n\n- The 'topological differences' mentioned in Section 4 could be\n  clarified: the paper talks about differences in connected components.\n\n- The $\\lambda$-density set appears to be a superlevel set, if I am not\n  mistaken: the level set would be defined for a single threshold only,\n  while this paper introduces the pre-image of an interval.\n\n- I would expect the pre-image to be defined as $p^{-1}$, not $p_{-1}$;\n  the latter strikes me as somewhat non-standard usage\n\n- The statements preceding Definition 1 require some more intuition;\n  what is the purpose of these assumptions?\n\n- The notation for the Euclidean balls should be briefly introduced\n  before Definition 1. I recognise this as a standard notation, but\n  since this is the first appearance of the symbol, it should be\n  mentioned at least briefly.\n\n- Definition 1 could also be phrased more intuitively; additional\n  sentence behind each definition would be useful, such as:\n  $\\delta_\\lambda$ is the largest $\\delta$ such that the full\n  superlevel set is contained in a ball of radius $\\delta_\\lambda$.\n\n  Figure 1 is already helpful in that regard; it should ideally precede\n  the definition and/or be made larger to be more illustrative\n\n- Maybe the results of Theorem 2 could already be stated earlier; it\n  could probably be explained reasonably well when describing the number\n  of connected components as a sort of 'baseline' topological complexity\n  that a model has to satisfy.\n\n  On a more abstract level, could it also be summarised as 'the\n  inclusion of prior knowledge is a necessary condition for robustness'?\n\n- I would not state that the main goals of the experiments are to\n  'check the correctness of Theorem 2'---the proofs should be\n  responsible for this! I would rather say that the main goals are to\n  provide empirical evidence for the *relevance* or *applicability* of\n  the Theorem.\n\n- The paragraph on 'Latent vector distributions' contains the most\n  relevant information, viz. the knowledge of what the paper considers\n  to be a 'topology-aware' and 'topology-ignorant' model; this should be\n  highlighted more; maybe the figures could be extended to contain\n  information about $n_X$?\n\nOverall, I like the idea of having one overarching question in a paper\nthat is subsequently answered or discussed under different aspects. I\nvery much commend the authors of the paper for choosing this sort of\nwriting style!\n\nIV. Experimental setup\n\nAs mentioned above, the experiments require more depth. I would propose\nadding more repetitions of the training process for different data sets\nand analysing the impact of the 'parameters' used in the theorems.\n\nIn particular, the 'INC' experiments show great promise for multiple\nrepetitions. Why not choose more data sets and more staring positions\nand visualise the trajectories of _multiple_ draws, as shown for\na single draw in Figure 4 a,b,c?\n\nAlso, please consider moving the additional experiments from the\nappendix to the main paper.\n\nMore compelling examples would also be helpful. Why not generate data\nsets consisting of more than two manifolds? At present, the largest\nissue I see in this section is that the conceptual 'leap of faith'\nbetween the theory and the applications is simply too large. Would it\nnot be possible to perform the same experiments on a simple digits data\nset, say MNIST?\n\nV. Minor issues\n\nThe paper is well-written overall. There are only a few typos and minor\nstyle issues that I would recommend fixing:\n\n- please check the usage of quotes; it should be ``pulled back'', not ''pulled back'' in LaTeX\n\n- please check the usage of citations; if '\\citet' is used, citations\n  can be used as nouns directly (for example: 'in Pennec (1999)' instead\n  of 'in (Pennec, 1999)'.\n\n- etc.. --> etc.\n- it approximates posterior distribution --> it approximates a posterior distribution\n- for compound distribution --> for a compound distribution\n- a relatively simpler distribution --> a simpler distribution\n- near manifold --> near a/the manifold\n- we simply the minimum --> we denote (?) the minimum\n- satisfies the followings --> satisfies the following properties\n- number of connected component --> number of connected components\n- Experimental result --> Experimental results\n\nVI. Update after the rebuttal\n\nThe authors managed to address the majority of my comments. Overall, I still would like to see a more detailed/in-depth experimental setup, but I realise that this not directly possible within the timeframe allotted during the rebuttal period. I am thus raising my score.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the role of topology in designing adversarial defenses. Specifically , the authors study defense strategies that rely on the assumption that data lies on a low-dimensional manifold, and show theoretical and empirical evidence that such defenses need to build a topological understanding of the data.

Reviewers were initially positive, but had some concerns pertaining to clarity and limited experimental setup. After a productive rebuttal phase, now reviewers are mostly in favor of acceptance, thanks to the improved readibility and clarity. Despite the small-scale experimental validation, ultimately both reviewers and AC conclude this paper is worthy of publication.  
Decision: Accept (Poster)