Manifold Regularization for Locally Stable Deep Neural Networks
Authors: Charles Jin
Martin Rinard
Venue:  (2021)
Keywords: regularization
deep learning
adversarial robustness

Abstract: We apply concepts from manifold regularization to develop new regularization techniques for training locally stable deep neural networks. Our regularizers encourage functions which are smooth not only in their predictions but also their decision boundaries. Empirically, our networks exhibit stability in a diverse set of perturbation models, including $\ell_2$, $\ell_\infty$, and Wasserstein-based perturbations; in particular, against a state-of-the-art PGD adversary, a single model achieves both $\ell_\infty$ robustness of 40% at $\epsilon = 8/255$ and $\ell_2$ robustness of 48% at $\epsilon = 1.0$ on CIFAR-10. We also obtain state-of-the-art verified accuracy of 21% in the same $\ell_\infty$ setting. Furthermore, our techniques are efficient, incurring overhead on par with two additional parallel forward passes through the network; in the case of CIFAR-10, we achieve our results after training for only 3 hours, compared to more than 70 hours for standard adversarial training.

Under review as a conference paper at ICLR 2021
MANIFOLD REGULARIZATION FOR LOCALLY STABLE DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We apply concepts from manifold regularization to develop new regularization techniques for training locally stable deep neural networks. Our regularizers en- courage functions which are smooth not only in their predictions but also their decision boundaries. Empirically, our networks exhibit stability in diverse set of perturbation models, including l22 foc. and Wasserstein- based perturbations; particular, against state-of-the-art PGD adversary, a single model achieves both Lo robustness of 40% at e = 8/255 and & robustness of 48% at e 1.0 on CIFAR-10. We also obtain offte-of-hheattt verified accuracy of 21% in the same loe setting. Furthermore, our techniques are efficient, incurring overhead on par with two additional parallel forward passes through the network; in the case of CIFAR-10, we achieve our results after training for only 3 hours, compared to more than 70 hours for standard adversarial training.
INTRODUCTION
Recent results in deep learning highlight the remarkable performance deep neural networks can achieve on tasks using data from the natural world, such as images, video, and audio. Though such data inhabits an input space of high dimensionality, the physical processes which generate the data often manifest significant biases, causing realistic inputs to be sparse in the input space.
One way of capturing this intuition is the manifold assumption, which states that input data is not drawn uniformly from the input space, but rather supported on some smooth submanifold(s) of much lower dimension. Starting with the work of Belkin et al. (2006), this formulation has been studied extensively in the setting of semi-supervised kernel and regression methods, where algorithms ex- ploit the unlabelled data points to learn functions which are smooth the input manifold (Geng ct al. 20122 Goldberg et al. 20088) Niyogi 2013; Sindhwani et al. 2005 Tsang and Kwok 2007 Xu et al.) 2010). Such techniques have seen less use in the context of deep neural networks, owing in part to the ability of such models to generalize from relatively sparse data (Zhang et al. 2016).
Contributions We apply concepts from manifold regularization to train locally stable deep neural networks. In light of recent results showing that neural networks suffer widely from adversarial inputs (Szegedy et al.) 2013). our goal is learn function which does not vary much in the neigh- borhoods of natural inputs, independently of whether the network classifies correctly. We show that this definition of local stability has natural interpretation in the context of manifold regularization, and propose an efficient regularizer based on an approximation of the graph Laplacian when the data is sparse, i.e., the pairwise distances are large. Crucially, our regularizer exploits the contin- uous piecewise linear nature of ReLU networks to learn function which is smooth over the data manifold in not only its outputs but also its decision boundaries.
We evaluate our approach by training neural networks with our regularizers for the task of image classification on CIFAR-10 (Krizhevsky et al., 2009). Empirically, our networks exhibit robustness against variety of adversarial models implementing lz, loc. and Wasserstein-basel attacks. We also achieve sfate-of-the ti-thhe-rt art verified robust accuracy under for of size = 8/255. Furthermore, our regularizers cheap: training sample, so the total computational cost is on par with three parallel forward passes through the network. Our techniques thus present novel, regularization-onf approach learning robust
simply evaluate the network at two additional random points for each

---

Under review as a conference paper at ICLR 2021
neural networks, which achieves performance comparable to existing defenses while also being an order of magnitude more efficient.
2 BACKGROUND
Manifold regularization The manifold assumption states that input data not drawn uniformly from the input domain X, also know as the ambienl space, but rather is supported on a submanifold M C X, called the intrinsic space. There thus distinction between regularizing on the ambient space, where the learned function is smooth with respect to the entire input domain (e.g., Tikhonov regularization (Phillips
1962 Tiihooovv et al., 2013), ), and regularizing over the intrinsic space, which uses the geometry of the input submanifold to determine the regularization norm.
A common form of manifold regularization assumes the gradient of the learned function VM)((x) should be small where the probability of drawing sample is large; we call such functions "smooth". Let be a probability measure with support M. This leads to the following intrinsic regularizer:
II S.a (I
In general, cannot compute this integral because M is not known, so Belkin et al. (0066) propose the following discrete approximation that converges to the integral as the number of samples grows:
N
|lfll
Σ (f(,)))((z,)))) 1-5-
N
Here, the I1, ..., NN are samples drawn, by assumption, from the input manifold M according p. and L is a matrix of weights measuring the similarity between samples. The idea is to approximate the continuous input manifold using a discrete graph, where the vertices are samples, the edge weights are distances between points, and the Laplacian matrix L encodes the structure of this graph. A common choice of weights is heat kernel: Lijj L(z,, 22) := exp(-Ila;; ==,ll/ /s). To improve computational costs, weights are often truncated to the k-nearest neighbors within some e-ball. Note that the Laplacian can also be interpreted as discrete matrix operator, which converges under certain conditions to the continuous Laplace operator (Belkin and Niyogi 2008).
ReLU networks Our development focuses on a standard architecture for deep neural networks: fully-comnected feedforward networks with ReLU activations. In general, represented by such network with n layers and parameters 0 = {Ai, bi as
write the function
20
(3)
&, = A, 14-1 + bj
for i = 1,.... 71 for i 1,..., n 2
(4)
o (ã:)
(5)
f(x; 0) = -n-1
(6)
where the A, are the weight matrices and the b; are the bias vectors. We call the "hidden activa- tions", or more simply, activations, and the 2; "pre-activations".
In this work, we consider networks in which of-) in (5) is the Rectified Linear Unit (ReLU)
2j o (0,
is clear from this description that ReLU networks are a family of continuous piecewise lincar functions. We denote the linear function induced by input v as fz(;; 0), i.e., the analytic extension of the local linear component about x over the input domain.
Adversarial robustness One common measure of robustness for neural networks is against norm-bounded adversary. In this model, the adversary is given an input budget over norm || 11 and asked produce an output perturbation over norm example for an input pair (I, y) if
lout- A point x' is an e-ô adversarial
|| - x Illin
(8)
( y out 5
(9)
2

---

Under review as a conference paper at ICLR 2021
When the specific norn is either unimportant or clear from context, we also write the first condition as x' E (x), where (z) refers to the e-ball or neighborhood about z. If such an adversarial example does not exist, say that the network is e-ô robust z. Standard examples of || Ilin include the &2 and Eoo "norm", defined for vectors as |||]| == max; |za|-- For classification tasks, the adversary is successful if it produces an example in the e-neighborhood of which causes the network to misclassify. In this case, we drop ó and say that the network is e-robust at z. Note that if fx; 0) is already incorrect, then I suffices as an adversarial example.
3 RELATED WORK
Manifold regularization was first introduced by BBelkin al. (2006) in the context of semi-supervised learning, where the goal was to leverage unlabeled samples to learn a function which behaves well (e.g., is smooth, or has low complexity) over the data manifold. The use of manifold regulariza- tion for deep neural networks has been explored in several contexts (Tomar and Rose 2014 2016
Hu et al., 2018: Zhu et al., 2018). In particular, [ee et al.] (2015) combine manifold regulariza- tion with adversarial training and show improvements in standard test accuracy. Our approach is to use manifold regularization to induce stability separately from accuracy. We note that a similar decomposition between accuracy and stability forms the basis for the TRADES algorithm (Zhang) ctt al. 2019), though the training procedure ultimately relies on adversarial training. Hein and An- driushchenko (2017) propose conceptually similar regularizer to minimize the difference between logits and show improved & certified robustness. Finally, several prior works explore regulariz- ing for robustness based other differential forms (Ross and Doshi-Velez 2017 Jakubovitz and (tryes/(0188 though they only report results using the weaker single-step PGD adversary. In par- ticular, a recent work by Zhai al. (2020) uses randomized smoothing for & certified robustness, and claim similar computational advatte due to avoiding adversarial training, but still take 61 hours train, compared to only hours in our approach.
Adversarial examples were introduced by SZzeedyy et al. (2013). who found that naively trained neural networks suffer almost complete degradation of performance on natural images under slight perturbations which are imperceptible to humans. A standard class of defenses is adversarial train- ing, which is characterized by training on adversarially generated input points (Goodfellow et al.) 2014). In particular, the Projected Gradient Descent (PGD) attack (Kurakin et al.) 2016 Madry] iet al. 2017) is widely considered to be an empirically sound algorithm for both training and evalu- ation of robust models. However, such training methods rely solving an inner optimization via an iterative method, effectively increasing the number of epochs by a multiplicative factor (c.g., an overhead of 5-10x for standard PGD). Achieving robustness against multiple adversarial models has also been explored previously (Schott et al. 2018) Tramer and Boneh 2019 Maini et al.) [2019] Croce and Hein 2019b), though in most cases these works use weaker variants of the subset of standard adversaries we consider (e.g., a smaller or the single-step version of PGD).
Another approach is train models which are provably robust. One method is to use an exact veri- fication method, such as an MILP solver, to prove that the network is robust on given inputs (Tieng al. 2017). In particular, Xiao et al. (2019) use a similar loss based on ReLU pre-activations to learn stable ReLUs for efficient verification, but rely on a PGD adversary to train a robust model. Certification methods modify models to work directly with neighborhoods instead of points (Dvi-
jotham et al. 2018. Gowal et al. 2018 Mirman et al.] 2018 Wong et al.) (018). In practice, the inference algorithms must overapproximate the neighborhoods to preserve soundness while keeping the representation compact as it passes through the network. This strategy can be interpreted as solv- ing a convex relaxation of the exact verification problem. Though certification thus far has produced technique is fully general and can be applied to any model
better lower bounds, verification (given sufficient time); recent work also suggests that methods using layerwise convex relaxations may face inherent barrier to tight verification (Salman et al. 2019).
4 SETTING
We reframe the goal of learning functions that are robust using a perspective which decouples sta- bility from accuracy. The key observation is that we would like to train networks that are locally stable around natural inputs, even if the network output is incorrect. This approach contrasts with
3

---

Under review as a conference paper at ICLR 2021
adversarial training, which attempts to train the network to classify correctly on worst-case adver- sarial inputs. In particular, recall that a network is c-robust at z if no point in the e-meighborhood of causes the network to misclassify. We consider the related property of e-stability (cf. Zheng et al. (016)):
Definition 4.1. A function f is e-Ō stable at an input x for all x' E N.(x), If(x) - f'(x) 6. classifier f is e-stable an input x if all x! E Nc(x), f(x) = f(x).
As e-stability is independent of the correct label for function with respect to the input manifold and can thus be captured using manifold regularization. For completeness,
argue that e-stability is property of the
state the following connection between robustness and stability:
Proposition 4.1. A function f is c-Ō robust an input iff f is c-ô stable and f(x) = y. A classifier f is c-robust at an input x iff f is c-stable at x and f correctly classifies x.
5 MANIFOLD REGULARIZATION FOR DEEP NEURAL NETWORKS
Applying the regularization term in yields, in the limit, function which is smooth the data manifold. Unfortunately. a straightforward approach does not suffice for our goal of learning c-stable deep neural networks. The first problem is that smoothness e-stability (Stutz et al. (2019);; indeed, we are concerned with the behavior of our function in an e- neighborhood of the manifold, not just on the manifold. The second observation is that convergence of the discrete approximation requires that the samples be dense over the input manifold; however, this assumption is almost certainly violated in most practical applications, particularly in the deep learning regime. The next two sections are dedicated to these challenges.
the data manifold does not yield
5.1 RESAMPLING FOR LOCAL SMOOTHNESS
We write the e-neighborhood of manifold .M as M, = fz By -,, yl1 S c}. Since e-stability is defined over the e-neighborhood of every input point, we might want a function which smooth over M. instead of just M, e.g., by slightly perturbing every input point. This strategy does produce samples from the c-neighborhood of the data manifold, however note that the induced distribution is not uniform but rather the convolution of the choice of noise distribution with the uniform distribution over M. Nevertheless, this procedure exhibits several properties we can exploit. The first is that for sufficiently small e, we get nearly the same operator over M, and M, so that smoothness over M, does not sacrifice smoothness on the original data manifold M. A more subtle property is that we can actually draw as many distinct points we would like from M,. We leverage these extra points to build regularizer which yields good estimations of the local smoothness. Moreover, taking a discrete approximation of the form in Equation [ with the resampled points from M. still converges to the original operator. Formally, we can state the following:
Proposition 5.1. Let 6, > 0 be given. Let 21..... In be n samples drawn uniformly at random from a submanifold M C X. For each 24, pick e new points Ti,1 ..., Di.e by sampling iid perturbations ,.,,..., di.c and setting æij exp(-liz - /l)?/s),, let L and Le be the Laplacian matrices defined by the n original samples and n-ce new samples, respectively. Then if < 8, we have that L. and Le converge to the same operator in the limit as DC.
I; + dug. where Vi,j. |18,,i1| < Given kernel ka v)
For our purposes, this result states that the resampled Laplacian enjoys the same behavior in the limit as the original Laplacian.
We prove this result in Appendix A
5.2 SPARSE APPROXIMATION OF RESAMPLED LAPLACIAN
The Laplacian matrix is dense, and requires both O(N2) time and space to compute and store. is thus standard to employ heuristics for sparsifying Laplacians to derive efficient algorithms; in this work, we consider the c-neighborhood sparsifier, denoted L,, which is defined as the Laplacian of the graph created by retaining only those edges whose weights are at most (Von Luxburg 2007).
To motivate this approach, our main observation is that, under certain sparsity assumptions in the data, the resampled Laplacian will consist of two types of edges: very short edges between points
4

---

Under review as a conference paper at ICLR 2021
resampled from the same e-meighborhood, and very long edges between points sampled from dif- ferent e-neighborhoods. For an appropriate choice of the scale factor s, the exponential form of the heat kernel causes the weights on the long edges to fall off very quickly compared to the short edges. The following results gives bounds for this approximation of the regularizer in Equation 2 Jnder a certain separation assumption in the data:
Proposition 5.2. Consider function f and a set of points {xi such that the pairwise differences
bounded from above and below by < 01 S -(x; S 30 for all + j. Let be the parameter of the heat kernel kş- exp(-Ilaa - Fyy [//]///s Assume farther that the points {r,} are separated in the sense that there exist at least (n)) pairs of points (Ia (x2), E S whose distances are bounded from above by /s. and the remainder of the points have distances bounded from below by m 6 for some constant TO > 1. Writing R(L)- = Ex.=
- {(x;))² Li.j. we have that
R(L)- c2 exp(-m²) S R(L)) S R(L) s (1+b-))
(10)
where b (((ca/c2)(ex((m2))))
We give proof in Appendix A In this work, we only consider bounded functions S. which allows us to apply this proposition. This result gives two bounds on the dense regularization R(L) in terms of R(L.). The first inequality says that the absolute approximation eπror is bounded by a term which vanishes unless the squared sample count N2 grows as the exponential of the squared separation m The third inequality gives tighter bound on the relative error in a term that vanishes unless the linear sample count N grows as the exponential of the squared separation m², but requires that have good control over the ratio c1/02. Note that the dependence on Ci c//c2 is unavoidable in the sense that a function which is very smooth in local neighborhoods of size will necessarily have large relative contribution from the longer edges; however, in this case we still have a bound on the absolute contribution (though we trade the ratio /1/02 for factor of N). Crucially, in both cases the error bound depends on an exponential factor of the squared separation m
To provide some empirical evidence that the separation m can be made non-trivial in some set- tings, we offer the following statistics from CIFAR-10 10. We select a random subset of 10,000 (20%) training samples. For each of these points, we find the closest point within the remaining 49,999 training samples, and compute the distance. Using the & metric, we found a mean distance of 9.597, a median distance of 9.405, and the distance the 10th percentile to be 5.867. Conversely, we resample points in an foo ball of radius = 8 8/255, which is contained in an & ball of radius v3. 32-32-12 32-8/22/2222 8/255 = 1.739. In fact, only 21 training samples, or 0.21% % of the random subset, have partner closer than twice the perturbation bounds. Thus, after the resampling procedure, setting the scale parameter to = z² and taking the e-neighborhood Laplacian should yield a good approxima- tion the full Laplacian. Finally, to generalize this to larger datasets, for fixed s one would expect that the separation / between points grows with the dimension of the ambient space, which gives an exponential decay in the approximation error. Indeed, this is one of the manifestations of the oft-cited curse of dimensionality (Hastic et al.) 2009).
Due to our resampling procedure, we have at least o² points whose squared pairwise distances are less than 2², which motivates setting s = 2:: notice that this choice of satisfies the assumptions of Proposition [. needed for convergence. However, rather than find the c-neighborhood Laplacian, we propose to compute the regularizer only using points resampled from the same e-neighorhood, yielding the following sparse approximation of the intrinsic regularizer:
11/1B3
(f(a)s) -(a,,))((rr))))))))))))))))))))) ((n,,
(11)
N
1-1=1
We emphasize that this is heuristic, motivated by computational efficiency, whose quality ulti- mately depends on the sparsity of the dataset and the particular choice of e. In particular, this approximation should not be used when the data is dense and there many points that are within distance of each other. However, the diagonal form of this approximation permits extremely efficient computations, particularly on vectorized hardware.
5

---

Under review as a conference paper at ICLR 2021
Figure 1: Surface and contour plots for Ha (a 1).
5.3 HAMMING REGULARIZERS
We additionally leverage the structure of ReLU networks to induce stronger regularization effect on the data manifold. The central observation is that not just do we want the function computed by the neural network to be constant (i.e., smooth with respect to its outputs) on the manifold, also want the network to produce its outputs in roughly the same way.
First, identify every local linear component f=(:;) 0) with its "activation pattemn,, i.e., the quence of branches taken at each ReLU. We will write [' 0) for the map that takes inputs x their activation patterns, which live on the unit hypercube {0, 13 (where N is the number of ReLUs in the network). If we endow the hypercube with the standard Hamming distance dh this induces pullback (psuedo- )etricc in the input space: d' (2, y) = du (fH (z; 0). fH (y: 0)). Notice that the metric identification is exactly the set of local linear components f=(:;;)
Recall that the goal of regularization is reduce the complexity of the learned function f in the e-neighborhood of inputs z. We argue that d' provides concise measure of this complexity. Specifically, if we consider the number of distinct local linear components is psuedo-metric, we have that Vx E N₂ (2r), dir (z, x²; 0) = 0 if and only if N. (x) is a single linear component. Thus, minimizing d'j between æ and all x' E Ne(x) reduces the number of linear components in the neighborhood of æ. In fact, by the triangle inequality, the same holds in the interior of any convex polytope defined by set points (xi)er where Vi, i' E I, d'a (Zi, Tee 0) = O. This makes minimizing di very sample efficient.
(2), then since d
Treating (u as an output of the network, we have the following (sparse) manifold regularizer:
||n((50)1
(12)
M
N
(13)
1,k=1
which is just Equations and with the outputs f(x) replaced by the activation pattern map. However, this loss term is not continuous in the inputs, and furthermore, the gradients vanish almost everywhere, does not generate good training signals. We thus continuous relaxation:
H (2, ÿ: 0) == abs(tanh(a * 2) tanh(a Ú))
(14)
This form is differentiable everywhere except when E ÿ. and recovers the Hamming distance when take to infinity (after scaling). Qualitatively, sensitive activations (i.e., small |å] and (ğ) are permitted so long as they are precise. Figure presents the surface and contour plots of Ha. Note that this idea can be extended more generally to other activation functions by penalizing differing pre-activations more when the second derivative of the activation function is large (and so the first-order Taylor approximation has larger errors).

---

Under review as a conference paper at ICLR 2021
5.4 TRAINING WITH SPARSE MANIFOLD REGULARIZATION
For every sample 2, we generate new random maximal perturbation E {=ted and produce the pair of perturbed inputs xt regularization term as (f)l) & Σ; [I](=))) [(, ell- For the Hamming regularizer, we use the lg norm to combine the Hamming distances between pre-active seeaativaaions within a layer and normalize by twice the number of elements in each layer. We sum over the layers, then normalize by the total number of layers. Note that in both cases, the weights [(x: x, can be dropped since the distance between xx and iy is constant. The final optimization objective thus
+ p and x == I p. We compute the standard manifold
1
0- = arg min
Σ V(((a;)) + +x + mlll((; N
(n (15)
where V is the loss function, (I 0) is the ambient regularizer (e.g.. & regularization), and the 7K, Yr, 7H are hyperparameters which control the relative contributions of the different regularizers.
5.5 DISCUSSION
Our development has focused on learning deep neural networks which are smooth when samples are sparse the input manifold M. While this property is related to e-stability, in general the two are not equivalent. Roughly, c-stability is inherently a property about worst case behavior, whereas manifold regularization is aimed at learning function which is smooth on average. Nonetheless, we note that function achieving zero loss with the manifold regularizer yields perfect stability (i.e.. a constant function on the data manifold).
Next, we discuss our choice to focus on the sparse setting. The basic idea is two-fold: first, the requirement that the learned function be e-stable significantly alters the geometry of the input mani- fold; second, when data is sparse, the amount of information one can glean about the overall geom- etry of the input manifold is limited, as evidenced by the vanishing weights in the Laplacian. Our main hypothesis is that the combination of these two observations allows one to formulate version of the regularizer built from resampled data, which maintains the same properties in the limit but yields more local information when data is sparse.
Conversely, consider the alternative approach, namely, directly learning a smooth function when is possible to produce samples, not necessarily labelled, that are dense over the input manifold M. Then given the central thesis behind this work, one would expect stability to improve. In fact, the top four results for robust accuracy reported in Croce and Hein (2020) all exploit an additional dataset of unlabeled images which is orders of magnitude larger than the original training set (Carmon et al.)
2019 Hendrycks al. 2019
Uesato al. 2019 Wang al. 2020
6 EXPERIMENTAL RESULTS
We report results for two models trained on CIFAR-10 image classification using regularization techniques: a smaller CNN for exact verification, following Xiao et al. (2019); and a PreActRes- Net18 model (He al. 2016) for benchmarking against a variety of adversarial models. We also include three ablation studies for the larger model, including one which does not use the sparsifica- tion scheme developed in Section (dense regularizer), and using the individual regularizers to isolate their individual effects on stability (intrinsic / Hamming regularizer only). Appendix B reports training details and hyperparameters; full experimental results (including MNIST, which is not discussed here) are in Appendix
6.1 STABILITY
The main characteristic that differentiates our approach conceptually from existing methods for adversarial robustness is that we train our models using pure regularization, i.e., without reference to a particular adversary. In comparison, most methods train and test using inputs produced by the same adversary. While this procedure yields good performance against the adversary used during training, performance degrades significantly when evaluated under different perturbation models. In general, the bounds for various adversarial models set that maximal perturbations remain

---

Under review as a conference paper at ICLR 2021
Table CIFAR-10 robust accuracy against various adversaries and perturbation models.
Test Accuracy (%)
Defense
Wasserstein
Clean
e = 0.5
- 8/255
.1
Wong et al.
2019)
76
80.69
baseline (Lo certified)
61
66.33
Maini et al. 2019
66.0
49.8
81.7
baseline (cx PGD, Madry et al. (017
<5.0
45.8
87.3
Manifold Regularization
57,538
36,908
66.02
69.95
$Computed using the full AutoAttack+ attack (Croce and Hein
2020), which includes APGD APGD-DLR (+targeted), FAB (Harggetdd) (Croce and Hein [019a) and Square Attack (Andriushchenko)
al. 2019 *Wit slightly smaller 0.03 7.65/255. Reported in Maini al. (019)
somewhat reasonable by human standards; thus, we expect a model that stable in the general sense to be robust against a variety of adversaries, particularly those not seen during training.
In line with this observation, we test a single model trained to be stable using manifold regularization against three norm-bounded perturbation models. The first two constitute the most common settings for adversarial robustness, namely. CIFAR- 10 robustness using &o and & PGD adversaries bounded at 8/255 and 0.5, respectively. We also which is a metric for images more closely aligned with human perceptions. Our results indicates that model trained using our manifold regularizer does in fact learn to be more stable test images across a variety of different perturbation models (T. We obtained our results after training for 3 hours on one GPU, compared to several days for standard PGD training (Shafahi et al. 2019).
Wasserstein-basee
PGD adversary at 0.1,
For comparison, we note that standard adversarial training using PGD from Madry et al. 2017 which forms the basis of every state-of-the-art approach for Eo robustness (Croce and Hein 2020)
achieves negligible performance when evaluated in the &g setting. We also report results from Maini al. (2019), which was the only other approach in the literature to evaluate their models for both loo and le robustness at the full levels of using a PGD adversary; their models are trained for 50 epochs with 50 steps of PGD against multiple adversaries parallel ( 5000 effective epochs). Finally, we also report results from Wong et al. (2119) for comparison against the Wasserstein adversary. Their results are obtained against a PGD adversary using a 50-step inner optimization (number of training epochs is not reported); their baseline model is trained to be certifiably robust against foc attacks of size e = 2/255, and achieves lower robustness than ours.
6.2 ABLATION STUDIES
We several ablation studies to better understand the behavior of our methods. The first column of Table 2 reports the verifiable robustness of our smaller model, which outperforms the previous state of the art as reported Xiao al. (2019). We emphasize that we provide this metric as a base- line for establishing a provable lower bound on the robustness achieved by our defense, compared empirical robustness which is often brittle measure of true robustness, particularly for newly
proposed defenses (Athalye et al. 2018 Carlini et al. 2019 Tramer et al. 2020).
The second column of Table presents robust accuracy against the standard PGD adversary used in the literature. The dense regularizer has both lower robust and clean accuracy, which suggests an over-regularization effect stemming from longer edges that do not yield reliable information about the intrinsic geometry of the manifold. Furthermore, training with the dense regularizer takes around 21.5 hours, or nearly 8 times longer than the sparse method (due to both the overhead computing additional gradients during backpropogation, as well the smaller batch sizes for offsetting the increased memory requirements for storing the dense Laplacian). We also report the results from using intrinsic or Hamming regularizers alone, which indicate that both terms contribute jointly and individually to our performance. For comparison, we report results for other approaches which not variants of PGD (i.e., do not rely solving minimax problem at each training loop).
8

---

Under review as a conference paper at ICLR 2021
Table 2: CIFAR-10 provable and robust accuracies against an loo adversary at 8/255.
Test Accuracy (%)
Mechanism
Defense
Verified
Robust
Clean
PGD (Madry al.
2017
45.8
87.3
Adversarial Training
FGSM (Madry et al. 2017)
0.0
90.3
Xiao et al.
(019)
20.27
26.78
40.45
Verification
Manifold Regularization (small)
21.04
25.56
36.66
Pang et al.
2019
24.8
92.7
Manifold Regularization (large)
40.54
69.95
Regularization
dense regularizer
35.04
64.08
intrinsic regularizer only
20.11
34.74
Hamming regularizer only
24.87
90.24
With slightly smaller 0.03 = 7.65/255. *Computed from 500 10000 images in test set. *Results for regularization only; reported robust accuracy is 55.0% when trained with PGD.
To the best of our knowledge, Pang et al. 2019) is the only other result in the literature which achieves non-trivial loo robust accuracy on the standard benchmark of CIFAR-I0 at e = 8/255 using regularization-only approach; their results are better than either of our regularizers used independently, but significantly worse than when the regularizers are used together, either the sparse the dense setting. For context, the best result in this setting is reported Waang et al. 2020) using a PGD variant at 65.04% robust accuracy.
7 CONCLUSION
We design regularizers based on manifold regularization that encourage piecewise linear neural networks learn locally stable functions. We demonstrate this stability by showing that single model trained using our regularizers is resilient against l2, loo. and Wasserstein-basee attacks. We also achieve ofate-of-the-art verified robustness of 21% against -buudded perturbations of size 8/255 on CIFAR- 10. Critically, computing our regularizers relies only on random sampling, and thus does not require running an inner optimization loop to find strong perturbations training time. As such, our techniques exhibit strong scaling, since they increase batch sizes rather than epochs during training, allowing us to train an order of magnitude faster than standard adversarial training. This work thus presents the first regularization-only approach to achieve comparable results to standard adversarial training against a variety perturbation models.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: query- efficient black-box adversarial attack via random search, 2019.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses adversarial examples, 2018.
Mikhail Belkin and Partha Niyogi. Towards theoretical foundation for laplacian-based based manifold methods.
Journal of Computer and System Sciences, 74(8):1289 1308, 2008, ISSN 0022-0000. doi: https://do..rr/ 10. 1016/ 2007 006. URL lttp::// wwtp:/ssceneeireee.o.o con/ con/ http://ee...coeeseeeee/e///rr//e 50022000007001220 Learning Theory 2005.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of machine learning research, 23N4444339,-2444, 2006.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks, 2017.
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wicland Brendel, Jonas Rauber, Dimitris Tsipras, lan Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv preprint arXiv:1902.06705, 2019.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Perey Liang, and John Duchi. Unlabeled data improves adversarial robustness, 2019.
Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21 (1):5 30, 2006. ISSN 1063-5203. doi: ssciencedirect.c com/ http:///wccc.......t....eeeeee..
2006.00000 URL [RR/htt:: /wwww
Special Issue;
Issue: Diffusion
Maps and Wavelets.
Francesco Croce and Matthias Hein. Minimally distorted adversarial examples with fast adaptive boundary attack, 2019a.
Francesco Croce and Matthias Hein. Provable robustness against all adversarial ty-perturbations for 2 1, 2019b.
Francesco Croce Matthias Hein. Reliable evaluation of adversarial robustmess with an ensemble of diverse parameter-F -ereterr-reeeeeeo attacks, 2020.
Krishnamurthy Dvijotham, Sven Gowal, Robert Stanforth, Relja Arandjelovic, Brendan O' Donoghue, Jonathan Uesato, and Pushmeet Kohli. Training verified learners with learned verifiers, 2018.
Logan Engstrom, Andrew Ilyas, Shibani Santurkar, and Dimitris Tsipras. Robustness (python library), 2019. /tRLhhtts://gtthmme thub. com/ htw.aaaaa.bbbboutteeeeeeeeeeeeee
Bo Geng, Dacheng Tao, Chao Xu, Linjun Yang. and Xian-Sheng Hua. Ensemble manifold regularization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1227-1333, 2012.
Andrew B Goldberg, Ming Li, and Xiaojin Zhu. Online manifold regularization: A new learning setting and empirical study. In Joint European Conference Machine Learning and Knowledge Discovery Databases, pages 393-407. Springer, 2008
Goodfellow, Jonathon Shlens, Christian Szegedy. Explaining and harnessing adversarial examples, 2014.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin. Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models, 2018
Trevor Hastic, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining. inference, and prediction. Springer Science & Business Media, 2009.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks, 2016.
Matthias Hein and Maksym Andriushchenko. Formal guarantees on the robustness of a classifier against ad- versarial manipulation. In Advances Neural Information Processing Systems, pages 2266-2276, 2017.
10

---

Under review as a conference paper at ICLR 2021
Matthias Hein, Jean-Yves Audibert, and Ulrike Von Luxburg. From graphs manifolds-weak and strong pointwise consistency of graph laplacians. International Conference on Computational Learning Theory, pages 470-485. Springer, 2005.
Matthias Hein, Yves Audihert, and Ulike von Luxburg. Graph laplacians and their convergence on random neighborhood graphs. Journal of Machine Learning Research, 80Jm)):325-1336, 2007.
Dan Hendrycks, Kimin Lee, and Mantas Mazeika. Using pre-training can improve model robustness and uncertainty, 2019.
Hongwei Hu, Bo Ma, Jianbing Shen, Hanqiu Sun, Ling Shao, and Fatih Porikli. Robust object tracking using manifold regularized convolutional neural networks. IEEE Transactions Multimedia, 21(2):510-3 521, 2018.
Daniel Jakubovitz and Raja Giryes. Improving dun robustness adversarial attacks using jacobian regulariza- tion. In Proceedings of the European Conference on Computer Vision (ECCV), pages 514-529, 2018.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint 0607. 2016.
Tachnon Lee, Minsuk Choi, and Sungroh Yoon, Manifold regularized deep neural networks using adversarial examples, 2015.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks, 2017.
Pratyush Maini, Eric Wong, and Zico Kolter. Adversarial robustness against the union of multiple perturbation models. arXiv preprint arXiv:1909,04000 04068, 2019.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for provably robust neural networks. In International Conference on Machine Learning, pages 3578-3586, 2018.
Partha Niyogi. Manifold regularization and supe-supe learning: Some theoretical analyses. The Journal of Machine Learning Research, 14(1):1229-12500 2013.
Tianyu Pang, Kun Xu, Yinpeng Dong, Chao Du, Ning Chen, and Jun Zhu. Rethinking softmax cross-cntropy loss for adversarial robustness, 2019.
David I. Phillips. A technique for the numerical solution of certain integral equations of the first kind. Journal of the ACM (JACM), 9(1)88497 1962.
Andrew Slavin Ross and Finale Doshi-Velas Improving the adversarial robustness and interpretability of deep neural networks by regularizing their input gradients. arXiv preprint 17Xiv:1711.09400 2017.
Hadi Salman, Greg Yang. Huan Zhang, Cho-Jui Hsich, Pengchuan Zhang. convex relaxation barrier to
tight robustness verification of neural networks. In Advances in Neural Information Processing Systems 32, pages 9835-9846. Curran Associates, Inc., 2019.
Lukas Schott, Jonas Rauber, Matthias Bethge, and Wieland Brendel. Towards the first adversarially robust neural network model on mnist. arXiv preprint arXiv: 1805.09190, 2018.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S. Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free!, 2019.
Vikas Sindhwani. Partha Niyogi, Mikhail Belkin, and Sathiya Keerthi. Linear manifold regularization for large scale semi-supervised learning. Proc. of the 22nd ICML Workshop on Learning with Partially Classified Training Data, volume 28, 2005.
David Stutz, Matthias Hein, and Bernt Schiele. Disentangling adversarial robustness and generalization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages
2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks, 2013.
Andrei Nikolaevich Tikhonov, AV Goncharsky, VV Stepanov, and Anatoly G Yagola. Numerical methods for the solution of ill-posed problems, volume 328. Springer Science & Business Media, 2013.
11

---

Under review as a conference paper at ICLR 2021
Vincent Tjeng. Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint 171.::711. 2017.
Vikrant Singh Tomar and Richard C Rose. Manifold regularized deep neural networks. In Fifieenth Annual Conference of the International Speech Communication Association, 2014.
Vikrant Singh Tomar and Richard C. Rose. Graph based manifold regularized deep neural networks for auto- matic speech recognition, 2016.
Florian Tramer and Dan Boneh. Adversarial training and robustness for multiple pertur- bations. In Н. Wallach, Larochelle. A. Beygelzimer. dAlché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 5866- 5876. Curran Associates, Inc., 2019.
URL http::/ nips. ccpppprrr
B821 8821-adveree -a--aaessrrra--rraniiinn and- hottrrrotttttatooooooooooooooorr pdf
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses, 2020.
Ivor W Tsang and James T Kwok. Large-scale sparsified manifold regularization. In Advances in Neural Information Processing Systems, pages 1401-1408, 2007.
Jonathan Uesato, Jcan-Baptiste Alayrac, Po-Sen Huang, Robert Stanforth, Alhusscin Fawzi, and Pushmeet Kohli. Are labels required for improving adversarial robustness?, 2019.
Ulrike Von Luxburg. tutorial on spectral clustering. Statistics and computing, 17(4):395 416, 2007.
Ulrike Von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. The Annals of Statistics, pages 555-586, 2008.
Xu Wang. Spectral convergence rate of graph laplacian, 2015.
Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu. Improving adversarial robustness requires revisiting misclassified examples. In International Conference on Learning Representa- tions, 2020.
Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses, 2018.
Eric Wong, Frank R. Schmidt, and J. Zico Kolter. Wasserstein adversarial examples via projected sinkhom iterations, 2019.
Kai Xiao, Vincent Tjeng, Nur Muhammad Shafiullah, and Aleksander Madry. Training for faster adversarial robustness verification via inducing relu stability. ICLR, 2019.
Zenglin Xu, Irwin King, Michael Kung-Tsong Lyu, and Rong Jin. Discriminative semi-supervised feature selection via manifold regularization. IEEE Transactions on Neural networks, 21(7))1033-1043 2010.
Runtian Zhai, Chen Dan, Di He, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsieh, and Liwei Wang. Macer: Attack-free and scalable robust training via maximizing certified radius. arXiv preprint arXiv:2001.02378, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization, 2016.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoret- ically principled trade-off between robustness and accuracy. 2019.
Stephan Zheng, Yang Song, Thomas Leung, and Ian Goodfellow. Improving the robustness of deep neural networks via stability training. In Proceedings of the ieee conference on computer vision and pattern recog- nition, pages 4480 4488, 2016.
Wei Zhu, Qiang Qiu, Jijji Huang. Robert Calderbank, Guillermo Sapiro, and Ingrid Daubechies. Ldmnet: Low dimensional manifold regularized neural networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2743-2751, 2018
12

---

Under review as a conference paper at ICLR 2021
A PROOFS
Proof of Proposition 5.1 Given a heat kernel (,, y) = exp(-1|> -
y11//) and samples
T1 my NN we define the discrete operator for out-of-sample point x as
Lf(x) = N E (.(2,,))(())
Σ (x,x,,)))(x.)) N
1
(16)
Our claim is that the original Laplacian L and the resampled Laplacian L/ converge pointwise to the same continuous operator.
The proof proceeds two parts. First, we show that resampling once still yields convergence the model the resampling procedure as form of noise; desired result
Laplacian. Notice that follows immediately from the following result of Coifman and Lafon (2006):
Proposition A.1 (Criterion 5 in Coifman and Lafon (0066). Suppose that X' is a perturbed version of M, that is, there exists a perturbation function y : . - X with a small norm (the size of the perturbation) such that every point in X can be written the approximation is valid as long as the scale parameter 8 remains larger than the size of the perturbation.
+ n(x) for some E M. Then
Since we have that the size of our perturbations is bounded by 2² < 8, this gives us the desired result.
Next we show pointwise convergence holds for arbitrary resampling c. This is a simple conse- quence of the linearity of the operator L. We order the samples as Fi.j. where indexes the original data points 1,... N, and indexes the resample j 1,..., Furthermore, let LŽ denote the Laplacian operator defined only on the jth resampled points Fi for í = I,..., N. Then
1 cN
1 CN
Lol(a)=
he (1,
he (x,
(17)
ka(a,
k.
ke (
(18)
N
c
1
(x)
(19)
Lf(x)
(20)
where the last line follows from the first half of the proof.
Remarks. We have shown that L' converges pointwise to the discrete operator L. However, for to converge to its continuous counterpart in Equation [ (i.c., the Laplace-Beltrand operator), we actually need to take the scale of the kernel to zero (see, e.g. the proofs of convergence in Belkin and Niyogi (2008) Hein et al. 2005 2007)). Then Proposition|..I]ii
that we also need to take c zero, that in the limit are just sampling from the unperturbed manifold. In fact, it is possible to prove convergence without taking 8 to zero, however the continuous operator that is recovered longer refers the gradient but rather the value of the kernel over the manifold (Von Luxburg et al. (2008) analyze this case). The spectra of these operators are often used in various clustering algorithms; in the context of deep neural networks, these operators yield similar regularizers for "smoothness"" though for different definition than the one used in this work. Finally, it should also be noted that the convergence these operators depends on the intrinsic dimension of the manifold; as we consider here e-neighborhood of the manifold which has the same dimension the ambient space, our operators will converge more slowly (Wang (2015)).
Hein
13

---

Under review as a conference paper at ICLR 2021
Proof of Proposition 5.2 We introduce L. L Le, which is just the Laplacian the com- plement the e neighborhood subgraph, i.c., the subgraph whose edges are at least c. Clearly R(L) R(L.) R(L.). Then have the following bounds:
R(T.)) (((a)) [( S N22 2 exp(-m²²
(21)
1988
R(L.) (0(a.)) ((;))) 2 ac, N exp(-1)
(22)
i,ES
where the a is a constant introduced for the O(N) edges in the graph of Le.
Take b (cc1/c2((exp(m))
1)/N), A simple rearrangement gives 02 (b-
1)/N), thus we have that
R(L) = R(L.) R(L.)
(23)
I R(L.) + c2N2 exp(-m²²
(24)
S R(L.) ((0="ac)(exp(mm 1)/N) N2 exp(-m?)
(25)
(RL.)) abaac exp(-1)
(26)
S R(L.) + R(Le)
(27)
(1(L)))
(28)
Then the first inequality follows from (24). the second inequality is trivial and the third inequality follows from
14

---

Under review as a conference paper at ICLR 2021
B EXPERIMENTAL METHODS AND HYPERPARAMETERS
We use a PreActResNer18 model (He et al. 2016 for the CIFAR-10 robustness experiments. We train using SGD with batch size of 128 and weight decay *K of Se-4. We follow Maini et al. (2019) for our learning rate schedule, which is piecewise linear and starts at O and goes to 0.1 over first 40 epochs; 0.005 over the next 40 epochs; and 0 over the final 20 epochs. We increase epsilon from 2 to 8 over epochs 10 to 35. We start the weight 7/2 of the manifold regularization at 0.8 and the weight Yn of the Hamming regularization at 2.400; these increase linearly up factor of 10 from epochs 20 to 80. We set the hyperparameter the CIFAR-10 ablation studies (except when setting "/r or "H to for the ablation studies involving the individual regularizers).
8. We use this set of hyperparamaters for all
For the dense regularizer, we used heat kernel with scale 8 = e² as weights for the Laplacian. We use smaller batch size of 40 to offset the increased memory requirements of storing and computing the dense regularizer.
We use two-layer convolutional neural network for the CIFAR-10 10 verification experiments, con- sisting of 2x2 strided convolutions with 16 and 32 filters, then a 128 hidden unit fully connected layer. This is the same model used in Wong et al. (0188) and Xiao al. (2019), except those works use a 100 hidden unit fully connected layer. We use the same schedule for the learning rate and as in the Pre1ctResNet18 model. The weight nt starts at 0.4 and the weight "Y starts at 9000; these increase linearly up to a factor of 10 from epochs 20 to 80. We use the same hyperparameter for the Net model.
We use the CNN with four convolutional layers plus three fully-connected layers from Carlini and Wagner (2017) for the MNIST robustness experiments. We use the same schedule for the learning rate. 6, Yr. and as in the PreActResNet18 8 model (except that e scales to 0.3). We use the same hyperparameter as for the PreActResNet18 model.
To set the hyperparameters 7/r and " on the PreActResNet11 8 model, we ran a grid search for .......... 500 and selected the settings which yielded the best robust accuracy against a 20-step f.x. PGD adversary with 10 restarts for 8/255 on the full training set; the range 7/X /77 was set such that the corresponding losses were roughly equal for randomly initialized, untrained network. For reporting results, we train five models using the selected hyperparameters and report results using the one with the median performance on the test set against 20-step for PGD adversary at 8/255 CIFAR-10 or 0.3 MNIST. For the PreActResNet18 8 model, robust accuracy over the 5 runs ranged from 40. % to 41.5% with median 40.5%; clean accuracy ranged from 66.9% to 72.4% with median 70.0%.
01 0.2, ..., 1.0 and / 100,200,...... ...,
For our stability results, we use the full version of AutoAttack+. an ensemble of attacks proposed by |Croce and Hein] (2020), for the le and fox perturbations. We choose the attack because it is parameter-free, which reduces the possibility of misconfiguration; empirically is at least as strong as standard PGD, and has been successful in breaking many proposed defenses. For the Wasserstein adversary, we use an implementation by Wong et al. (2019). For comparing with standard PGD, we use 20-step PGD adversary with 10 random restarts and a step size of 2.5 c/20 as implemented by |Engstrom et al. (2019). For verification, we adopt the setup of Xiao et al. (2019), using the MIP verifier of Tjeng al. (2017), with solves parallelized over CPU cores and the timeout set to 120 seconds.
15

---

Under review as a conference paper at ICLR 2021
C ADDITIONAL EXPERIMENTS
We plot robustness curves for both CIFAR and MNIST against standard 20-step PGD adversary with 10 restarts using both &g and &oo bounds in Figure 2 These results show that, compared with models trained using standard PGD against &oc perturbations, our methods perform on par (or substantially better, in the case of the lg adversary on CIFAR-I0) in a variety of settings, despite the disadvantage of not using the adversary during training. We also used stronger AutoAttack+ adversary for the CIFAR 10 results in T which we plot for reference "ours (AA+)".
For the CIFAR-10 results, we use PreActResNer18 model trained with manifold regularization on CIFAR-10 10 c 8/255. The curves for PGD are taken from Madry al. (2017). Our findings mirror those in |Schott et al.] (2018), namely, that model trained using PGD on CIFAR-10 10 for &oo performs poorly against & attacks. We also ran a 500-step foo PGD adversary with 20 restarts at 8/255 against our model, yielding 40.4% robust accuracy, which is plotted as "ours (PGD+)".
For the MNIST results, we use the CNN architecture from Carlini and Wagner (2017). trained with manifold regularization MNIST
0.3. The curves for PGD are taken from Madry et al. (0117). The difference in performance is much less dramatic in this case, which we attribute to the lower complexity of the task. We note in particular that both methods experience sharp drop in performance in the for case for c larger than the one used during training.
100
ours pgd ours (A.+)
100
ours pgd ours AA+
Robust accuracy (%)
75
nurs (PGD+)
75
50
50
25
25
0
0
10
20
30
0
2
3
Eo bound (c/255)
l bound (e)
(a) Robust accuracy on CIFAR-10 against 20-
(b) Robust accuracy on CIFAR- 10 against a 20- step & PGD adversary with 10 restarts.
step Eo PGD adversary with 10 restarts.
100
ours pgd
100
ours
Pgd
Robust accuracy (%)
75
75
50
50
25
25
0
0
0.1
0.2
0.3
0.4
0
2
4
6
Lo0 bound (c)
Eg bound (e)
(c) Robust accuracy on MNIST against a 20-step Loo PGD adversary with 10 restarts.
Robust accuracy on MNIST against 20-step PGD adversary with 10 restarts.
Figure 2: Robust accuracy as increases for a 20-step PGD adversary with 10 restarts.
16


Reviews:
[{"review_id": "hQDGMDUpCls", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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 proposes new regularizers for obtaining adversarially-robust models, inspired by the \"manifold assumption\" that data lies on a low-dimensional manifold. The first regularizer is based a sparsified Laplacian regularizer on the dataset along with random perturbations around each point, while the second is an approximation of the hamming distance between activation maps of a point and its local perturbations.\n\nWhile the obtained results seem promising, the motivation is questionable, in the sense that the obtained regularizers simply encourage local robustness around each point with random perturbations in all directions, and thus do not really exploit anything about a possible manifold structure in the data. The authors simply point to the \"sparsity\" of the data in high-dimensions (from what I understand, this is in the sense of points being much further away from each other compared to the local generated perturbations) in order to reduce the laplacian regularizer to only edges between perturbations of the same point, which leads to a natural regularizer that looks like a simple surrogate for penalizing the lipschitz constant. The Hamming regularizer seems more interesting but also seems unrelated to the motivation of manifold assumption.\n\nThis makes lean towards rejection, and I encourage the authors to better motivate the proposed regularizers and further compare to previous works in theory and in practice.\n\nmore comments:\n- introduction: the meaning of \"sparse data\" should be clarified\n- proposition 5.1: I am not convinced that L and Lc converge to the same operator, as the underlying distributions are different, perhaps the authors mean that the limiting operators are close to each other in operator norm? a rigorous proof is desirable\n- p.5 \"By the curse of dimensionality ...\": this should be clarified\n- definition of H_alpha: please elaborate on what inputs are fed into this function.\n- section 5.5 \"the two properties converge\": this is not clear\n- Table 1: are all models in a given column evaluated using the same attack? why were these particular baselines chosen? I am not sure I understand what makes the comparison to Wong et al. a strength of the current approach.\n- section 6.2 / Table 2: please clarify what \"verified robustness\" means. \n- table 2: are all numbers in a given row obtained for a single model with a fixed choice of hyperparameters? which metric are these optimized on?\n\n** update after rebuttal **\n\nThank you for the detailed clarifications. I still find that the recommended method used in practice, which only encourages robustness to local random perturbations, is too disconnected from the motivation of manifold regularization, and will thus keep my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ViEkk7ifT-O", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "Strength:\n1. The author introduced a regularization-based robust training method that can perform well on CIFAR-10.\n2. The comparison in the experiment section contains many different aspects of robust training.\n\nWeakness:\n1. The perturbation of the $\\epsilon$-neighborhood on page 4 is not described. Is it Gaussian? Or Uniform? For the Gaussian perturbation, there's another track of verifiable robustness by Cohen \"Certified Adversarial Robustness via Randomized Smoothing\" and a following-up method to train the robustness called \"MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius\". \n2. The biggest concern comes from the perturbation part as well. The author includes a local small perturbation and only considers this local information to compute the $L$ matrix, which used to be computed between all the samples. Since the model only considers the arbitrary fake neighbors, the model will have an un-accurate view of the overall manifold (of equation (2)). Otherwise, this sounds like a free-lunch theory. Can the author make a more clear statement that which is given up and which is beneficial? Also, when considering the data manifold, after perturbation, the manifold is almost surely corrupted. For example, if you consider $S^1\\subset R^2$, when you perturb by any arbitrary noise, it will turn out to be a ring with dimension $2$ instead of $1$. So I doubt the local perturbation-based estimation will not recover the actual tangent vector, etc., of the manifold.\n3. The benefit of this method is not well addressed. For example, compared with the attack-based robust training, does this method performs a faster training speed? How fast? Will this reduce the number of data that is required? Some more discussion on the benefit as well as the compromising will be appreciated.\n4. One of the important matrices in this method is $L$. Is this matrix pre-computed or is this matrix computed in each iteration? Will this cause extra storage space?\n\nSome minor comments:\n1. The tables should be self-explainable. For example, highlight the SoTA or give a detailed description of evaluating which number is better. \n2. The numbering of equations is confusing. The (3)-(6) can be combined and the most important equation (section 5.4) contains no numbering. I would recommend the author to number those important equations. \n3. The equation in section 5.4, if expanded, it would be a norm on $||\\cdot||_2$ as well as $||\\cdot||_H$, which is also the robustness argument this paper is made. Can the author explained why this is different from just constrain those norm?", "extra_scores": {}, "extra_text": {}}, {"review_id": "QaqxXG8a8tn", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Summary of the paper:\nThis work aims at proposing a new type of regularization based on the affinity of the samples in the training set which is used, that allows to design more robust neural networks. 3 ideas are combined to obtain a tractable training procedure. First, the authors assume that the data lay on a manifold and propose to be stable to an $\\epsilon$-sausage of the manifold rather than the manifold itself. Then, the authors propose to neglect the correlation terms between different samples and to assume that the affinity matrix is diagonal - they however employ some \"ghost\" samples for computing the affinity. Finally, simple metrics (like hamming distances) are used to obtain a simple to compute regularization term. The authors demonstrate good performances against standard attack, on CIFAR-10.\n\nPros:\n- Interestingly, some of the assumptions on the manifold look reasonable, and it is interesting to rather study a neural network with the distance induced by a manifold rather than with the Euclidean distance of the ambient space. Indeed, the natural setting of the stability is along the manifold, where any points outside the manifold is an outlier: this leads to a different notion of manifold.\n- The performances seem good and to use standard approach, and seems fast (though no benchmark is done in the paper)\n\nCons:\n- Unfortunately, in the current writing, I noticed sometimes a certain lack of rigor, which makes the paper difficult to read and the drawn conclusions difficult to understand.\n- In my current understanding of the paper, the data manifold isn't really used and the method remains local, and employs solely the Euclidean metric, which sounds paradoxical given the promises of the paper: if two data points are in the same neighborhood, this information can *not* be used by the current algorithm.\n\nSpecific remark:\n- I don't understand the path from \"adversarial robustness\" to the definition and proposition 4.1. Indeed, I thought the definition 4.1 was the standard notion of robustness (as used e.g., in https://storage.googleapis.com/pub-tools-public-publication-data/pdf/45227.pdf ) \"We reframe the goal of learning with decouples from accuracy\" thus sounds slightly wrong, because I believe this was done in previous works.\n- Sec 5.2 needs a substantial rewriting: \"by the curse of dim... grows\" sounds really bad. I don't understand the equation right above eq. (7), what is L'? This is not introduced. \"the curse of dimensionality implies data becomes more sparse\" sounds really wrong. On the contrary, sparsity is an assumption to fight the curse of dimensionality. I think the idea can be understood as neglecting the cross term of the covariance matrix, under a local approximation. I find the final justification very informal, and I think there is a confusion between sparsity and high dimension.\n- Sec 5.3 and 5.4 describe experimental protocols that include a lot of new hyper parameter. I'd be curious and happy to see the cross validation protocol and its results. For instance, it's unclear to me what is the conceptual difference between the 3 regularizition-distances proposed and why/how, in a joined manner, they affect the performances.\n- As described in 5.5, the validity of the model indeed requires on a certain notion of invariance (or smoothness), which is linked  strongly to a manifold assumption, and the idea that, the l2 metric is important, is not new. In fact, it is somehow limited as translation is also a major variability and one could used the quotient distance related to this Lie group over the manifold of images. Furthermore, going beyond this type of explicit & analytic distance(eg l2 metric) is one of the purpose of graph-based regularisation, but according to this paper, this would require to understand the regularity of the data because there is no clear model of the manifold $\\mathcal{M}$ of the data.\n- The notion of regularity which is used here doesn't introduce more complex smoothness that what is used traditionally in the litterature of adversarial examples for neural network: it's almost purely an additive perturbation that relies on an euclidean distance.\n\nSuggestion for improving this paper:\n- I would try to find a manner to employ a non-diagonal approximation of the Laplacian or at least to verify this case is the appropriate one in practice. Indeed, if the data were sampled from the same low-dimensional manifold, then this assumption would be too strong.\n- I believe it is important to clarify the experimental protocol and to clean the informal statements.\n- I would also try to go beyond the Euclidean setting.", "extra_scores": {}, "extra_text": {}}, {"review_id": "2NJyNihpyVH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 work introduces manifold regularization as an approach for learning stable deep nets, towards the goal of adversarial robustness. Several regularizers are proposed: intrinsic, sparse Laplacian and Hamming regularizers. As the proposed method relies only on adding these regularization terms to the loss, it is more computationally efficient than methods that require computation of adversarial examples during training. The proposed method is evaluated on CIFAR-10 under $\\ell_2$ and $\\ell_{\\infty}$ ball attacks and shown to be state-of-the-art in terms of verifiable robustness to $\\ell_{\\infty}$ attacks at $\\epsilon = 8/255$.\n\nStrengths:\n- Clear, well-motivated approach\n- Hamming regularizer seems to be novel\n- State-of-the-art verifiable robustness\n\nWeaknesses:\n- Limited experimental evaluation:\n  * Lack of comparison with more recent approaches; this could be done by using AutoAttack (\"Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks\", ICML 2020)\n  * Results from a single epsilon budget and on a single dataset\n  * Experiment results seem to be from only a single run\n- No direct experimental comparison/validation of stability, which is the stated goal of the work\n\nOverall, this work introduces some interesting and novel ideas, but is lacking in its experimental evaluation, most significantly, in evaluating the stated goal of stability, as opposed to robustness which was done in the experiments. In particular, as noted in the paper, stability can also be achieved by regularizing the Jacobian-norm of the network, which seems like a more direct approach to the goal and should therefore be compared with; indeed, the implementation of the standard manifold regularization term looks almost like a finite difference approximation to the Jacobian-norm.\n\nOther comments:\n- The recent work \"MACER: Attack-free and Scalable Robust Training via Maximizing Certified Radius\", ICLR 2020 also presents an attack-free approach based on randomized smoothing, albeit for achieving certified $\\ell_2$ robustness.\n- \"Disentangling Adversarial Robustness and Generalization\", CVPR 2019 suggests that generalization (i.e. on-manifold robustness) is somewhat independent of off-manifold adversarial robustness; the proposed method seems to be aimed at targeting the on-manifold case (\"we only need $\\epsilon$ stability around valid input points\") - what about the off-manifold case? \n- Related to the previous point, the sampling procedure in Section 5.4 of picking perturbed points (using \"random maximal perturbations\") does not seem to restrict samples to be on the data manifold.\n\n*** Post response comments ***\n\nThanks for the detailed responses and clarifications, especially regarding the manifold used. I suggest that the notion of $\\epsilon$-manifold regularization is made clear upfront in the manuscript (e.g. in the introduction) to avoid misunderstanding.\n\nThe new results with the dense $\\epsilon$-manifold regularizer obtaining 5% less accuracy suggests to me that the specific approximation scheme used is indeed responsible for at least part of the benefit, and it would be useful to understand precisely why this is so since this is the core-contribution of the paper. I also agree with the other reviewers that the overall method as implemented seems a bit disconnected from the core idea of manifold regularization, and rather appears to be a variant of stability training (Zheng et al. 2016). As such, I will be keeping my original rating; nonetheless, I want to again thank the authors for the interesting and vigorous discussion.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper received borderline and negative reviews but has raised many questions and discussions, showing that the paper has some merit. Many concerns were however raised on various aspects of the paper such as mathematical rigor, clarity, and motivation of manifold regularization that is too disconnected from the robustness to local random perturbation which is encouraged by the method. The rebuttal addresses some of these comments and the reviewers have appreciated the detailed answer. Yet, it was not sufficient to change the reviewer's opinions.

In its current form, the paper is not ready for publication and the area chair agrees with most of the reviewer's comments. He recommends a reject, but encourage the authors to take into account the feedback from the reviewer before resubmitting to a future venue.
Decision: Reject