Compressive Recovery Defense: A Defense Framework for $\ell_0, \ell_2$ and $\ell_\infty$ norm attacks.
Authors: Jasjeet Dhaliwal
Kyle Hambrook
Venue:  (2020)
Keywords: adversarial input
adversarial machine learning
neural networks
compressive sensing.

Abstract: We provide recovery guarantees for compressible signals that have been corrupted with noise and extend the framework introduced in \cite{bafna2018thwarting} to defend neural networks against $\ell_0$, $\ell_2$, and $\ell_{\infty}$-norm attacks. In the case of $\ell_0$-norm noise, we provide recovery guarantees for Iterative Hard Thresholding (IHT) and Basis Pursuit (BP). For $\ell_2$-norm bounded noise, we provide recovery guarantees for BP, and for the case of $\ell_\infty$-norm bounded noise, we provide recovery guarantees for Dantzig Selector (DS). These guarantees theoretically bolster the defense framework introduced in \cite{bafna2018thwarting} for defending neural networks against adversarial inputs. Finally, we experimentally demonstrate the effectiveness of this defense framework against an array of $\ell_0$, $\ell_2$ and $\ell_\infty$-norm attacks.   

Under review as a conference paper at ICLR 2020
COMPRESSIVE RECOVERY DEFENSE: A DEFENSE FRAMEWORK FOR lo, l2, AND loo NORM ATTACKS.
Anonymous authors Paper under double-blind review
ABSTRACT
We provide recovery guarantees for compressible signals that have been corrupted with noise and extend the framework introduced in Baffn al. (2018) to defend neural networks against to. Eg, and -norm attacks. In the case of to éo-norm noise, we provide recovery guarantees for Iterative Hard Thresholding (IHT) and Basis Pursuit (BP). For f2-norm bounded noise, we provide recovery guarantees for BP, and for the case of L -nom bounded noise, we provide recovery guarantees for a modified version of Dantzig Selector (DS). These guarantees theoretically bolster the defense framework introduced in Bafna al. (2018) for defending neural networks against adversarial in- puts. Finally, we experimentally demonstrate the effectiveness of this defense framework against an array of Ea. &g and Lo norm attacks.
INTRODUCTION
Signal measurements often corrupted by noise. The theory of compressive sensing (Candes et al. 2006)) allows us to retrieve the original signal from a corrupted measurement, under some structural assumptions the measurement mechanism and the signal. Let consider the class of machine learning problems where the inputs are compressible (i.e., approximately sparse) in some domain. For instance, images and audio signals are known be compressible in their frequency domain and machine learning algorithms have been shown to perform exceedingly well on clas- sification tasks that take such signals input (Krizhevsky al.) (2012); [Sutskever al.] (2014)). However, it was found in Szegedy et al. (2013) that neural networks can be easily forced into mak- ing incorrect predictions by adding adversarial perturbations to their inputs; see also [Szegedy et al. 2014); Goodfellow et al. (2015): Papernot et al. (2016); [Crllii & Wagner (2017). Further, the adversarial perturbations that led to incorrect predictions were shown to be very small (in either fo. l2, or foe -norm) and often imperceptible to human beings. For this class of machine learning tasks, we show how to approximately recover original inputs from adversarial inputs and thus defend the neural network norm, f--norm and & noom attacks.
In the case of lo norm attacks on neural networks, the adversary can perturb a bounded number of coordinates in the input vector but has restriction on how much each coordinate is perturbed in absolute value. In the case of f--m attacks, the adversary can perturb as many coordinates of the input vector as they choose long the f--norm of the perturbation vector bounded. Finally, in loo -norm attacks, the adversary is only constrained by the amount of noise added to each coordinate of the input vector.
The contribution and structure of this paper is as follows. In Section 3.1 we describe the Compres- sive Recovery Defense (CRD) framework, a compressiv--sensing neural networks against adversarial inputs. This is essentially the same framework introduced in Bafna et al. 2018), though Bafna et al. (2018) considered only lo attacks. Section 3.2 we present the recovery algorithms which are used in the CRD framework to approximately recover original inputs from adversarial inputs. These algorithms include standard Basis Pursuit (BP), (A: -s-saae Iterative Hard Thresholding (IHT) and Dantzig Selector (DS) with additional constraint. In Sec- tion 3.3, we state recovery guarantees for the recovery algorithms in the presence noise bounded in either Lu, fz, or loo norm. The guarantees apply to arbitrary La, Ez, and -orm attacks; they do not require prior knowledge of the adversary's attack strategy. The recovery guarantees are proved rigorously in Appendix A In Section 4 experimentally demonstrate the performance of
framework for defending

---

Under review as a conference paper at ICLR 2020
the CRD framework in defending neural network classifiers CIFAR- 10, MNIST, and Fashion- MNIST datasets against state-of-ther the-art& Lo, Eg and & -nomm attacks.
Notation. Let be vector in CN. Let S E [I,...,,N) and =
S. The cardinality of S is |S]. If A E CmxN is matrix, then As E [ is the column submatrix of A consisting of the columns indexed by S. We denote by zş either the sub-vector in C consisting of the entries indexed by S or the vector in CV that is formed by starting with x and setting the entries indexed by S to zero. For example, if x = [4,5, -9, 1)" and 5 = {1,3), then rs is either -9]² or [4, 0, -9, 0j² It will always be clear from context which meaning is intended. Note that, under the second meaning, z5 =
2g. The support of x, denoted by supp(r), is the set of indices of the non-zero entries of x, i.c., supp(x)
{i E (I....,,V } I, + 0}. The lo-quasinorm of x, denoted | is defined to be the number of non-zero entries of x, i... | card We say that is k-sparse if |æl|o- I We use Tb(R) denote a k-sparse vector in CNN consisting of the l largest (in absolute value) entries of x with all other entries zero. For example, if x [4, 5, -9, 1)² then TM(2) = [0, 5, -9,0 Note that Tb(c) may not be uniquely defined. contexts where a unique meaning for T)(k) is needed, we can choose TN(k) out of all possible candidates according to a predefined rule (such as the lexicographic order). We also define T((k) = x [h())-
If x = x2]" E Can with 11, Z2 E C and if xj is k-sparse and 22 is t-sparse, then x is called (k, -sparse. We define Th(k,)) [xx))(() (22))(e))* which is (ki, -)-sass vector in Can
3 THEORY
3.1
COMPRESSIVE RECOVERY DEFENSE (CRD)
Bafna et al. (0188) introduced a framework for defending machine learning classifiers against tu- attacks. We extend the framework to lz and fo attacks. The defense framework is based on the theory of compressive sensing, so we call Compressive Recovery Defense (CRD).
We explain the idea behind the CRD framework in the context of an image classifier. Suppose a E C a (flattened) image vector we wish to classify. But suppose an adversary perturbs x with noise vector E C". We observe y = I + e, while and be the Discrete Fourier Transform (DFT) matrix. The Fourier coefficients of æ are á = Fz. It is well-known that natural images approximately sparse in the frequency domain. So we expect that à is approximately sparse, meaning that dz(N) is small for some small k. We can write
unknown to us. Let F Cax"
F
(1)
If |ell2 S 17 or |/ells= S n, with r) small (as in a l2 or aatakkk, then we can use an appropriate sparse recovery algorithm with and F-1 as input to compute a good approximation I# to a. Precise error bounds are given in Section 3.3 Then, since F unitary. F- F-1++ will be a good approximation (i.e., reconstruction) of x expect to get the same classification as we would have for x. For an lo-attack where is I-sparse, the approach is only slightly different, We set A = [F_1, 1I and write
't. So we can feed F x into the classifier and
y = F= = )=)))())) + F (2(0) Alina)) e) + F-
so that ef] is (k:, ()-sparee. This structure lets us use sparse recovery algorithm to compute a good approximation to à, as before. Note that the same idea can be applied with audio signals or other types of data instead of images. Moreover, the DFT can be replaced by any unitary transfor- mation for which 1 = Fx is approximately sparse. For example, F may be the Cosine Transform, Sine Transform, Hadamard Transform, another wavelet transform.
We now describe the training and testing procedure for CRD. For each training image x, we compute (ACA)) (Fa) ((t). and then compute the compressed the image x' F-- We then add both and x' to the training set and train the network in the usual way. Given a (potentially adversarial) test image y, we first use a sparse recovery algorithm to compute an approximation ## to 4 then compute the reconstructed image y' F- f and feed it into the network for classification.
3.2 RECOVERY ALGORITHMS
We provide the recovery algorithms used in this section. For attatacks, we set A = [F-1, as in Against fa or aatacks,,, take A F-1 as in (T.
2

---

Under review as a conference paper at ICLR 2020
Algorithm 1: (k,,)) t---parse Iterative Hard Thresholding (IHT)
Procedure: IHT(Y,A, T.)
Input: y C", C=x2n, and positive integers k. T.
0
for = 0 to T' do
x: x
(I10 (y Ar!!)) n(k.e)
return x = [T
The IHT algorithm above is used to defend against Ey fo-norm attacks. For such attacks, according to ( the vector need to recover is (k, t)-sparse. Thus this IHT is adapted to the structure of our problem as uses the thresholding operation hig. 2) that produces (k, 1)-saare vectors. This structured IHT was first considered in Baraniuk al.] (2010). It gives better theoretical guarantees and practical performance in our CRD application than the standard IHT, which would instead use the thresholding operation h((++)) that produces (k + f)-sparse vectors. For lz or loo attacks, the recovery error for IHT would (in general) be larger due to the need to include term for the & norm of the tail of the noise vector e. This, in turn, produces worse expected performance of the recovery defense. Therefore we only use Algorithm for 4--orm attacks. We note that the results of Theorem I Tallow for values of and greater than or equal to Theorem 2.2. of Bafna al. (0188)
Algorithm 2: Basis Pursuit (BP).
Procedure: By,, A,
Input: y E C A CmmN and 0. x# = arg mingeco ||=||ı subject to Az yl1 S
return x
We utilize BP for to and le norm attacks. In the to norm case, BP allows to provide recovery guarantees for larger values of & and t than IHT. For instance, the case MNIST and Fashion- MNIST, IHT (equation 4 of Theorem T) allows to set h and 3, whereas BP (equation 7 of Theorem 2 allows us to set k = and =
In the case of &2 norm attacks, BP applied with A = F-1, unitary matrix. As unitary matrices isometries in & norm, BP provides good recovery guarantees for such matrices, and hence against l2 norm attacks.
Algorithm 3: Modified Dantzig Selector (DS).
Procedure: DS A, Input: y E C"", A E Cm*N, and 2 0. # arg min.gcv ||ı|| subject to ||A" - o0 S Von, ||Az 1llo S 5n
return #
We utilize DS for foo norm attacks. The standard Dantzig Selector algorithm does not have the additional constraint ||Az ylloo S n) Our modified Dantzig Selector includes this constraint for the following reason. In our application, A = F-1 and we want the reconstruction Az# = F-1x" r be close to the original image x, so that they are classified identically. Thus, we want the search space for # to be restricted to those E C. such that ||Az - 2r =z] is small. Note, for any E C.N, ||Az - -||>0 < ||A= yl + Iæ yo In an -atack, ||00 y/|lx = ||e]]so is already small. Thus it suffices to require || - yll is small. We experimentally illustrate the improvement in reconstruction due to the additional constraint Scction 4.3 (Figure 4 Table 4
Remarks on Eegines-- Attacks. As observed in Bafna al. 2018 .,!o in Algorithm 1 can be initialized randomly to defend against reverse-engin -verse--ngineeeee attack. In the case of Algorithm 2 and Algorithm 3, the minimization problems can be posed as semi-definite programming prob- lems. If solved with interior point methods, one can use random initialization of the central path paramcter and add randomness to the stopping criterion. This makes recovery non-deterministic and consequently non-trivial to create reverse-engineered attack.
3.3 RECOVERY GUARANTEES
Let F' e C be unitary matrix and Cax" be the identity matrix. Define A [F,4] C"x2n and let y = A(t, c = Ft + where á e E C Let 1 S k. t S be integers.
3

---

Under review as a conference paper at ICLR 2020
Theorem
(lo-nomm IHT), Assume |Fyl I á and is t-sparse. Let x![+1] IIT(H T,,,
where p[[++]] ( el CD with a(T+1),, el C
Define = 27
cet n
T(1- - p): v3 1 + 2 ckt
1ʃ0 < < then:
| fn(a)ll2 S pl2+1), / |10 + |1e11 + T T1122
(3)
Moreover for any < and any T loR(1/e)+loR( [1anne 11 (ell)) log(1/p)
we get:
||10++111 Bn(x))le -14-111mmpp S =1| +
(4)
Now define p = 2 ckt T(1- p):= == 2. 1f0 < p 1, then:
|| (L(R) 112 p (T++D)1((AA)) + (1122(()ll2 + l|ell2)
(5)
Moreover for any 0 <<<< < and any T T2 -og(1/e) we get:
log(1/p)
||||++]| Bn(a)ll2 S +(] + [|ell2) +e
(6)
Let us explain how to interpret the recovery guarantees provided by Theorem [ The inequalities (3)
5). (6) provide an upper bound on the size of || &n 2l2. Since is a unitary matrix,
|| [+ Zn(k)) 2 equals || - F ( which is the difference between the reconstructed
image F*[T-1] and the compressed image (R) (which is compressed version of the original image z). So the inequalities the compressed image, and thus indicates how confident should be that the classification of the reconstructed image will agree with the classification of the compressed image. In other words, the inequalities tell us how likely is that the CRD scheme using IHT will be able recover the correct class of the original image, and thus defend the classifier from the adversarial attack. The presence of the norm of the tail .r(K) in the upper bounds indicates that the CRD scheme should be more effective when the original image is closer to being perfectly k-sparse in the transformed basis. The ratio kt/ bt/n in the upper bounds (via p and 7) suggests that smaller values of and relative to n (i.e., sparser transformed images & and error vectors e) will lead to the CRD being more effective. The experiments in Section 4 will demonstrate these phenomena.
Theorem tell us how close the reconstructed image must be to
Let us compare Theorem ! to the similar Theorem 2.2 of Bafna et al. (018)) We observe that (3) and (4) allow larger values of and than Theorem 2.2 of Bafna et al (2018). This is because the
authors of Bafna et al. (2018) prove their results using Theorem 4 of Baraniuk et al. (2010). which more restrictive for the values of and t. We do not use Theorem 4 of Baraniuk et al. 2010). Instead
(a modified form of) Theorem 6.18 18 of Foucart & Rauhut (2017) to get and (4) Both Theorem 4 of BaBaniuk et al. (2010) (used by [Bafna et al. (20188)))) and Theorem 6. 1818 of Foucart & RRuhut (201)) (used by here) take input the Restricted Isometry Property (RIP) stated in Theorem 7 We and [Bafna et al. (2018) both essentially prove the same RIP, although the proof methods are different. We use a standard Gershgorin disc theorem argument bound eigenvalues, while Baina et al. (2018) perform direct estimation using the triangle inequality and AM-GM inequality.
We turn now to (5) and 6), which provide recovery guarantees for larger values of l and t than
33) and (4). the expense of the extra error term ||e|| Our proof of (5) and (6) is novel. relies on explicitly expanding one iteration of IHT in matrix form and using the structure of the resulting
matrix form to bound the approximation error iteration T terms of the error at iteration T 2.
We then use an inductive argument in Theorem 6.18 of Foucart & Rauhut (2017) to get ( and 6).
Next, we consider the recovery error for fo-norm bounded noise with BP instead of IHT. We note that since Algorithm 2 is not adapted to the (k, t)-sparse structure of vector to be recovered, we do not expect the guarantees to be particularly strong. However, providing bounds for BP is useful as there are cases when BP provides recovery guarantees for when recovering a larger number of coefficients (k)) and larger fn noise budget (1) than IHT.
4

---

Under review as a conference paper at ICLR 2020
Theorem (lo-norm BP). Assume
|Fy] e. Define
ckt δ Voht
B max
vk 1
V + Ōr
n
0
(1 - )x.t)
B,
T
òū,e
1f0 < 6 < and O < 0 < 1, then for x# -BP(y, A, [1 we have the ervor bound
2T
8
||* - Sn(K)ll2 -
1 1 1 5x,t
+ 2r
||02(19122
where we write xh = [ e E C with "",
,",e"
elt E C
Note that the recovery error in 7 is ((((k++t (2(())))))) which means that we should not expect recovery to be close when the attacker has a large lo noise budget or when is not sparse. Also observe that the recovered vector 3# is not necessarily k-sparse. The recovery error still captures the difference in the original image Få and the reconstructed image F&# where smaller recovery error should once again indicate that our classifier would make the correct prediction. Our third result covers the case when the noise is bounded in fn-norm.
Theorem (f2-norm BP). If |eel2 S then for x# = (y, F, F,r),, we have the error bound
| - =1|1 s
|8((,)]11 22/k))
(8)
2
1 $112 s
|| 667
Vk
Finally, we provide recovery guarantees when the noise is bounded in -
Theorem 4 -norm DS). If ||ello I 11, then for x# DS(y,, F,r)), we have the error bound
| =111 - ( 11 2k/)))
(10)
2
|| =112 S
| + 6v/kn
(11)
Vh
The proofs of Theorem 3 and Theorem 4 are based on standard arguments in compressive sensing that rely establishing the so-called robust null space property of the matrix. Note that the results of Theorem 3 and Theorem 4 also bound the norm difference of the original image Få and the reconstructed image F where 2 has no sparsity guarantees. Next, observe that the results of Theorem incur factor of /n in the error bounds due to the constraint [AA y)ll & vin in Algorithm 3 which is required to prove the robust null space property. Finally, we note that the additional constraint added to Algorithm 3 does not affect the proof of Theorem
3.4 RELATED WORK
The authors Bafna et al. (218)) introduced the CRD framework which inspired this work. In fact, Theorem 2.2 of Bafna et al. (2018) also provides an approximation error bound for recovery via 1HT. Note that a hypothesis & O(n/A kk) has accidentally been dropped from their Theorem 2.2, though it appears in their Lemma 3.6. By making the implied constants explicit in the argument of
Bafna et al. (2018), one sees that their Theorem 2.2 is essentially the same as (3) and 4 in Theorem Jabove. For more details, see the proof of Theorem in Appendix A Note that our recovery error bounds for IHT in (5) and (6) of Theorem T do not have analogs in Bafnn et al. (2018). They hold
for larger values
and at the expense of the additional error term ||e||
Other works that provide guarantees include (Hein & Andriushchenko (201)) and (Cisse et al. (017)) where the authors frame the problem as one of regularizing the Lipschitz constant network and give lower bound the norm of the perturbation required change the classifier decision. The authors of [Sinha et al. (2017) use robust optimization to perturb the training data and provide training procedure that updates parameters based on case perturbations. A similar approach to (Sinha et al. (2017)) is (Wong & Kolter (2017)) in which the authors use robust optimization to provide lower bounds the norm of adversarial perturbations the training data.
5

---

Under review as a conference paper at ICLR 2020
In Lecuyer et al. (2018), the authors use techniques from Differential Privacy (Dwork et al. (2014))im order to augment the training procedure of the classifier to improve robustness to adversarial inputs. Another approach using randomization is Li et al. (2018) in which the authors add i..d. Gaussian noise to the input and provide guarantees of maintaining classifier predictions as long as the f2-norm of the attack vector is bounded by function that depends on the output of the classifier.
Most defenses against adversarial inputs do not come with theoretical guarantees. Instead, a large body of research has focused on finding practical ways to improve robustness adversarial inputs by either augmenting the training data (Goodfellow et al. ). using adversarial inputs from various networks (Tramèr et al.] (2017)) or by reducing the dimensionality of the input (Xu et al. (2177) For instance, Madry et al. (017)) use robust optimization to make the network robust to worst case adversarial perturbations on the training data. However, the effectiveness of their approach is determined by the amount and quality of training data available and its similarity to the distribution of the test data. An approach similar to ours but without any theoretical guarantees is Samangouci et al. 2)) In this work, the authors use Generative Adversarial Networks (GANs) to estimate the distribution of the training data and during inference, use a GAN to reconstruct a non-adversarial input that is most similar to given test input. We now provide a brief overview the field of compressive sensing.
Though some component ideas originated earlier in other fields, the field of compressive sensing was initiated with the work of Candès et al.] (2006) and Donoho et al.) (2006) in which the authors studied the problem of reconstructing sparse signals using only small number of measurements with the choice of a random matrix. The reconstruction was performed using f--minimization (i.e., Basis Pursuit) which was shown to produce sparse solutions even in presence of noise; see also Donoho & Elad (2003) 2006); Donoho & Huo (200T). Some of the earlier work in extending com- pressive sensing to perform stable recovery with deterministic matrices was done by Candes Tao (205) and Candes et al. (2006), where the authors showed that recovery of sparse vectors could be performed as long as the measurement matrix satisfied restricted isometry hypothesis. BBlumensath & Davies (2009) introduced IHT as an algorithm to recover sparse signals which was later modified in Baraniuk et al. (2010) to reduce the search space as long as the sparsity was structured. The standard DS algorithm was introduced in Candes et al. (2007) in order to perform stable recovery in the presence of 2o noise.
4 EXPERIMENTS
All of our experiments are conducted on CIFAR-10 (Krizhevsky (2009)), MNIST LeCun), and Fashion-MNIST (Xiao et al. (2017)) datasets with pixel values of each image normalized to lic in [o, 1]. Each experiment is conducted on a set of 1000 points sampled uniformly at random from the test set of the respective dataset. For every experiment,
the Discrete Cosine Transform (DCT) and the Inverse Discrete Cosine Transform (IDCT) denoted by the matrices F E R=x* and FT E Ru respectively. That is, for an adversarial image E RVRXVR such that, y = x+e, we let f FI, and x F á. where I, R" and En the noise vector. For an adversarial image y RRVxvVxxe that contains channels, we perform recovery on each channel independently by considering ym Zm + Cm. where &m. Frm I' = F &m for m 1,...,c. c. The value k denotes the number of largest (in absolute value) DCT coefficients used for reconstruction of each channel, and the value / denotes the tn noise budget for each channel. We implement Algorithm and Algorithm 3 using the open source library CVXPY (Diamond Boyd (2016))
We now outline the neural network architectures used for experiments in Section and For CIFAR-10, we use the network architecture of [e et al. (2016) while the network architecture for MNIST and MasHion-MNIST datasets is provided in Table of the Appendix. We train our networks using the Adam optimizer for CIFAR-10 and the AdaDelta optimizer for MNIST and Fashion- MNIST. In both cases, we cross-entropy loss function. We train the each neural network according to the CRD framework stated in Section 3.1 The code to reproduce our experiments is available here: htttps://qitiie www.hhww.ooooeeeeooooeee.eeeeoee www.://///oonouusseceoo www.ooowwoooussccoorrrreeeeeeeee cettompressiveiciiiie. r2200

---

Under review as a conference paper at ICLR 2020
Orig. Acc. 77.4%
OPA. Acc 0.0%
IHT. Acc. 71.8%
Table 1: Effectiveness of CRD against OPA. The first column lists the accuracy the network on original images and the OPA Acc. column shows the network's accuracy adversarial images. The IHT. Acc. column shows the accuracy of the network on images reconstructed using IHT.
4.1 DEFENSE AGAINST Ey- NO-NORM ATTACKS
This section is organized follows: first examine CRD against the One Pixel Attack (OPA) (Su et al. (2019) for CIFAR-10. We only test the attack on CIFAR-10 as is most effective against natural images and does not work well on MNIST or FASHION-MIIST We note that this attack satisfies the theoretical constraints for provided in Theorem | hence allowing us to test how well CRD works within existing guarantees. Once we establish the effectiveness CRD against OPA, we then test it against two other ly-no fy-norm bounded attacks: Carlini and Wagner (CW) 4y-norm attack (Carlini & Wagner (2017) and Jacobian based Saliency Map Attack (JSMA) (Papernot et al. (016)).
4.1.1 ONE PIXEL ATTACK
We first resize all CIFAR-10 images to 125 x 125 while maintaining aspect ratios to ensure that the data falls under the hypotheses of Theorem even for large values of k. The OPA attack perturbs exactly one pixel the image, leading to an to noise budget of 3 per image. The to noise budget of t 3 per image allows us use & = 275 per channel. Table [ shows that OPA is very effective against natural images and forces the network to mis-classify all previously correctly classified inputs.
Original
OPA
IHT-Rec
Figure The original image is shown in the first column, the adversarial image in the second column, and image reconstructed using IHT is shown in the third column.
We test the performance of CRD in two ways: a) reconstruction quality b) network performance on reconstructed images. In order to analyse the reconstruction quality of Algorithm [ we do the following: for each test image, approximate its largest (in absolute value) & = 275 DCT co-efficients. We then perform the IDCT on these recovered co-efficients to generate reconstructed images. We illustrate reconstruction on randomly selected image from the test set in Figure
use OPA to perturb the image and then use Algorithm [ to
Noting that Al Algorithm Sraithhmllade leads to high quality reconstruction, we now test whether network accuracy improves on these reconstructed images. To do so, we feed these reconstructed images as input to the network and report its accuracy Table T We note that network performance does indeed improve network accuracy goes from 0.0% to 71.8% using Algorithm [ Therefore, we conclude that CRD provides a substantial improvement in accuracy in against OPA.
4.1.2 CW-&, ATTACK AND JSMA
Having established the effectiveness of CRD against OPA, we onto the CW fn-norm attack and JSMA. We note that even when much larger than the hypotheses of Theorem D and Theorem 2, we find that Algorithms I and 2 are still able to defend the network. We hypothesize that this maybe related to the behavior the RIP a matrix for "most" vectors as opposed to the RIP for all vectors, and leave more rigorous analysis for follow up work.
7

---

Under review as a conference paper at ICLR 2020
Original
CW-&o
Iee-Rec
Re-Rec
JSMA
IeT-Rec
BP-Rec
8
8
Figure 2: Reconstruction quality of images using IHT and BP. The first column shows randomly selected original images from the test set, while the second and fifth column show the adversarial images. Reconstructions using IHT are labeled IHT-Ree and using BP are labeled RP-Rec. We show reconstructions in columns three, four, six, and seven.
Dataset
Orig-
C&W to IHT Acc.
JSMA
Acc.
tavg
Acc.
BP Acc.
tave
Acc.
IHT Acc.
BP Acc.
CIFAR-
84.9%
18
8.7%
83.0%
67. 07.0%
34
2.7%
63.2%
67.3%
MNIST
98.8%
15
0.9%
84.2%
55.9%
17
56.5 %
90.1%
67.4%
F-MNIST
91.8%
16
5.27%
84.1%
71.4%
17
62.6 %
83.3%
72.0%
Table The tavg column lists the average adversarial budget for each attack. The Orig. Ace column lists the accuracy of the network on original test inputs, the Acc. columns under C&W tn and ISMA list network accuracy on adversarial inputs. The IHT Acc. and the BP Acc. columns list the accuracy of the network inputs that have been corrected using IHT and BP respectively.
We follow the procedure described in Section 4.1.1 to analyze the quality of reconstructions for Algorithm Sarrithhmannddd and Algorithm in Fig In each case can be seen that both algorithms provide high quality reconstructions for values of that are well outside the hypotheses required by Theorem and Theorem 2
We report these values and the improvement in network performance on reconstructed
adversarial images using CRD in Table 2
4.2 DEFENSE AGAINST NORM ATTACKS
In the case of mn-mrrm bounded attacks, we use the CW fo-morm attack (Carlini & Wagner (2017) and the Deepfool attack (Moosavi-Dzzleeen Deztooli et al. (016)) as they have been shown to be the most powerful. We note that Theorem does not impose any restrictions on or and therefore the guarantees of equations
( and are applicable for recovery in all experiments of this section.
Original
CW-
BP-Rec
DF
BP-Rec
2
Z
7
Z
7
Figure 3: Reconstruction quality of images using BP. The first columns shows the original images, while the adversarial images are shown in the second and fourth column. The reconstructions are shown in columns three and five.
8

---

Under review as a conference paper at ICLR 2020
Dataset
Orig.
C&W
L2
Deepfool
Acc.
22
Acc.
BP Acc.
Acc.
BP Acc.
CIFAR-10
84.9%
0.12
8.7%
72.3%
0.11
7.7%
71.6%
MNIST
99.17%
1.35
0.9%
92.4%
1.72
1.1 %
90.7%
Wushion-MNISS
90.3%
0.61
5.4%
78.3%
0.63
5.5 %
76.4%
Table 3: The f2 column lists the average f2-norm of the attack vector. The Orig. Ace column lists the accuracy of the network original test inputs, while the Acc. columns under C&W and DF columns report network accuracy on adversarial inputs. BP Acc, columns lists the accuracy of the network inputs reconstructed using BP.
The reconstruction quality is shown in Figure 3 It can be noted that reconstruction using Algorithm is of high quality for all three datasets. In order to check whether this high quality reconstruction also leads to improved performance in network accuracy, we test each network on reconstructed images using Algorithm 2 We report the results in Table R] and note that Algorithm [ provides substantial improvement in network accuracy for each dataset and each attack method used.
4.3 DEFENSE AGAINST &o -NORM ATTACKS
For -norm bounded attacks, we use the BIM attack (Kurakin al. (2016) as it has been shown to be very effective and also allows us to control the lo -norm of the attack vector explicitly. We note that while the CW - -nom attack (Carlini Wagner (2017) has the ability to create attack vectors with & -nom less than equal BIM, it computationally expensive and also does not allow one to pre-specify a value for the - -nom of an attack vector. Therefore, we limit our experimental analysis to the BIM attack. Note that for any attack vector ||e||2 S /n|lel|oo hence allowing fx-- norm attacks to create attack vectors with large m--nrm. Therefore, we could expect reconstruction quality and network accuracy be lower when compared to f--norm attacks.
Original
With Constraint
No Constraint
8
Figure 4: Comparison of images reconstructed using Algorithm (With Constraint) with images reconstructed using DS without the additional constraint (No Constraint).
In figure we compare the reconstruction quality of images reconstructed with Algorithm to those reconstructed using DS without the additional constraint. As can be noted from the figure, images reconstructed using DS without the additional constraint may not produce meaningful images. This also reflected in Table which shows that the accuracy of the network is roughly random on images reconstructed without the additional constraint.
We show examples of original images, adversarial images, and their reconstructions using Algorithm 3 in Figure
5 Finally, report the network performance reconstructed inputs using Algorithm 3 in Table 4 and also compare this to the performance on inputs reconstructed using DS without the additional constraint. We note that
increase in network performance against reconstructed adversarial inputs. However, the improvement performance is not as substantial as it against la or fg-nrrm attacks.

---

Under review as a conference paper at ICLR 2020
Dataset
Orig.
BIM
Acc.
Loops
Acc.
Modified DS Acc.
DS Acc.
CIFAR-I0
84.9%
0.015
7.4%
49.4%
17.6%
MNIST
99.17%
0.15
4.9%
74.7%
10%
90.3%
0.15
5.3%
57.5%
11.1%
Table 4: The fo,, column lists the -orm of each attack vector, Orig. Acc. and BIM Acc. columns list the accuracy of the network on the original and adversarial inputs respectively, and the Modified DS Acc. column lists the accuracy of the network on inputs reconstructed using Algorithm We also show accuracy of the network images reconstructed with DS (without the additional constraint) in the DS Acc. column.
Original
BIM
DS-Rec
4
4
Figure 5:
Reconstruction quality of images using DS. The first column shows the original images, while the second columns shows adversarial images and the third columns shows reconstructions using Algorithm respectively.
CONCLUSION
We provided recovery guarantees for corrupted signals the case of fo-norm, f2-norm, and too- norm bounded noise. We were able utilize these results in CRD and improve the performance of neural networks substantially in the case of fo-nom, & fo-norm and &oe -oom bounded noise. While fo-norm attacks don't always satisfy the constraints required by Theorem [ and Theorem 2 showed that CRD is still able to provide a good defense for values of t much larger than allowed in the guarantees. The guarantees of (ieorremaann Theorem 4 were applicable in all experiments and CRD was shown to improve network performance for all attacks.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Mitali Bafna, Jack Murtagh, and Nikhil Vass Thwarting adversarial examples: An/ O-robust sparse fourier transform. In Advances in Neural Information Processing Systems, pp. 10075-10085, 2018.
Richard G. Baraniuk, Volkan Cevher, Marco F. Duarte, and Chinmay Hedge. Model-based com-
pressive sensing. IEEE Transactions Information Theory, (6(())1982-200)) 2010.
Thomas Blumensath and Mike E Davies. Iterative hard thresholding for compressed sensing. Ap- plied and computational harmonic analysis, 27(3):26--274, 2009.
Emmanuel Candes and Terence Tao.
Decoding by linear programming. arXiv preprint
math/0502327, 2005.
Emmanuel Candes, Terence Tao, et al. The dantzig selector: Statistical estimation when is much larger than The annaly of Statistics, 35(6):2313-233 2007.
Emmanuel J Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on information theory, 52(2):489-555 50948995599000 2006.
Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: Journal Issued by the Courant Institute Mathematical Sciences, 59(8): 2006.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP). pp. 39 57. IEEE, 2017.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In Proceedings of the 34th International Conference on Machine Learning-Voile Volume 70, pp. 854-863. JMLR. org, 2017.
Steven Diamond and Stephen Boyd. CVXPY: A Python-emhedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
David Donoho and Michael Elad. Optimally sparse representation general (nonorthogonal) dictionaries via 1 minimization. Proceedings of the National Academy of Sciences, 100(5):2197- 2202, 2003.
David I. Donoho and Michael Elad, On the stability of the basis pursuit in the presence of noise. Signal Processing, 86(3):511-332 2006.
David L Donoho and Xiaoming Huo. Uncertainty principles and ideal atomic decomposition. 1EEE transactions on information theory, 4777):2445-2862, 2001.
David L Donoho al. Compressed sensing. IEEE Transactions information theory, 52(4): 1289-1306, 2006.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4)211-4077, 2014.
Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. 2017.
IJ Goodfellow, J. Shlens, and C. Szegedy, Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015. URL http://arxiv.
abs/ abs/1412. 0tts/1412.6572 6572
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp- 770-778, 2016.
M. Hein and M. Andriushchenko. Formal guarantees on the robustness of a classifier against ad- versarial manipulation. In Advances in Neural Information Processing Systems 30: Annual Con- ference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 2263-2273, 2017.
11

---

Under review as a conference paper at ICLR 2020
A. Krizhevsky, I. Sutskever, and G. E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Alexey Kurakin, lan Goodfellow, and Samy Bengio. Adversarial examples in the physical world. arXiv preprint arXiv: arXiv:/60..025333 2016.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/nmist//
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. arXiv preprint DXXi::802.03371,, 2018.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Second adversarial attack and certifiable robustness. arXiv preprint arXiv::809.03/1 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.066 2017.
Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on com- puter vision and pattern recognition, pp. 2574-2582, 2016.
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami. The limitations of deep learning in adversarial settings. In 2016 IEEE European Sympo- sium on Security and Privacy (EuroS&P), pp. 372-387. IEEE, 2016.
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan Protecting classifiers against adversarial attacks using generative models. arXiv preprint arXiv: 18805.06600 2018.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv: 10571, 2017.
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Transactions on Evolutionary Computation, 2019.
I. Sutskever, O. Vinyals, and Q. V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pp. 3104 3112, 2014.
C. Szegedy, W. Zaremba, and I. Sutskever. Intriguing properties of neural networks. International Conference on Learning Representations, 2014.
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.
Tramèr, A. Kurakin, N. Papernot, D. Boneh, and McDaniel. Ensemble Adversarial Training: Attacks and Defenses. ArXiv e-prints, May 2017.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. arXiv preprint arXiv:1711.0085: 2017.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint 778.77770. 2017.
W. Xu, D. Evans, and Y. Qi. Feature Squeezing Mitigates and Detects Carlini/Wagner Adversarial Examples. ArXiv e-prints, May 2017.
12

---

Under review as a conference paper at ICLR 2020
A
APPENDIX
A.1
RESTRICTED ISOMETRY PROPERTY
We first establish the restricted isometry property for certain structured matrices. First, we give some definitions.
Definition 5. Let A be a matrix in CM*M,, let M S CN and let ò 2 O. We say that A satisfies the M-restricted isometry property (or M-RIP) with constant ö
(1 || =
|| | S (1 + 1>
for all x E M.
Definition 6. We define Mj be the set of all k-sparse vectors in CN and similarly define Mg. x to be the set of (kt, t) -ssaase vectors in C In other words, Mr is the following subset of C
MA.t = {ar [>] x2 E C²n x1 E C" i2 E C", || llo S k. || S $1)
We define Sa.r to be the following collection of subsets of f 2m}:
Sk. (Si U S2 : S1 S (1, (1.....n) ..) S2 S {n + ,,...,2n) card(Si) S k card(S2) S S
Note that Sk. is the collection of supports of vectors in Mk.t-
Theorem 7. Let A= [F I) C"x2n, where F E Caxn is unitary matrix with |Fay S and
I E C is the identity matrix. Then
ckt
ckt 1
1
1 S ||Ar|2 1
||>|
(12)
n
ckt
for all x E MA In other words, A satisfies the MIP
RIP property with constant
Proof. In this proof, if B denotes an matrix in Caxn then X1 (B), ........ (B) denote the eigenvalues of B ordered so that [B1 - ... S (B). It suffices to fix an S = S S2 E Sk. and prove
12 for all non-zero x E CS
Since AşAs normal, there is orthonormal basis of eigenvectors u1y...y Uktr for AšAAs, where u; corresponds to the eigenvalue (s) For any non-zero x E CS we have x = k+t C2U, for some G E C,
|
(A5A5I,
k+t AsAAAss
(13)
|0012
(1,
Sktt of
Thus it will suffice prove that (A.(AAAs) -1|5 v okt for all i. Moreover,
IA, - m)|= / Xx: ((A3As (A5 1))
(14)
where the last equality holds because A5A - is normal. By combining [13 and 14), we see that (12) will hold upon showing that the eigenvalues of (AtAs 1)" AA 1) are bounded by ckt/ n.
So far we have not used the structure of A. but we must. Observe that (s) is a block diagonal matrix with two diagonal blocks of the form X*X and X Therefore the three I).X X XxX, and X X have the same non-zero eigenvalues. Moreover, X is simply the matrix Fs, with those rows not indexed by S, deleted. The hypotheses on F imply that the entries of X X satisfy [(X* X)xpl < n So the Gershgorin disc theorem implies that each eigenvalue À of X X and (hence) of As 5 () 1) satisfies |X| < ckt
matrices (A3As-I)** (A -)).
13

---

Under review as a conference paper at ICLR 2020
A.2 ITERATIVE HARD THRESHOLDING
First we present Theorem 8 and then use it to prove Theorem
Theorem 8. Let A C be a matrix. Let 1 S k,t S n be positive integers and suppose dg is Mak,3x-RIT RIP constant for A and that 82 is a M2x.2t-RI1 constant for A. Let C r E C", y Ax + v, and S Sk,t- Letting x!T+1]] IHT (.. A, k. t, T), is < 1/v3, then we have the approximation error bound
|| - (T+ | xs|l2 + 7 =lIArg r/12
where p :== v30g < 1 and (1 ()- v /3v1 1/ t S 2.18. Thus, the first term on the right goes to as goes to oc.
Theorem 8 modification of Theorem 6.18 of Foucart & Rauhut (2017). More specifically,
Theorem 6.18 of Foucart & Raubut (2017) considers M3t. M2s. and Sy in place of Mak.3 and M2 and Sk. and any dimension N in place of 2n. The proofs are very similar, so we omit the proof of Theorem 8 We will now prove lemma that will be required for the proof of Theorem For the proof of Lemma 9 and Theorem [ we use the following convention:
E CmxN be matrix, then, denote by (A)s. the N matrix that is obtained by starting with A and zeroing out the columns indexed by S. Note that (A)s = A (A)s-
Lemma 9. Let F Cax" be unitary matrix with |Fig|² S and let S [m]] be a index with |S| = t. Then for any k-sparse vector E C", we have:
ktc 1
II(F") )2223
Proof of Lemma First note that (F*)s E Cuxa contains only non-zero columns since |S| = Therefore, we have (((F)ss)),)
since |Fiy Further, since the non-zero columns of (F*)s orthogonal to each other, get ((F*)s) (F*)s (I)s, where I C" is the identity matrix. Using this, we have for any w E C",
[I(F)) FFFF = ((F*)s Fw, )sF) =
w) = ((F')s Fu w) = I((FF)s Fw, w)
Now let V C [n] be any index set with cardinality k. that is V i and let & E C any vector supported on V. We then get,
1 ((FF))sF)s
((FF)s=21) = ((1F)))F222)))
Σ a
|z
Σ
(((FF))
((FFls)))sll
KEV
JEV
WEV
jEV
Le Σ lasl
|
AEV
jEV
ktc
|| S
1|
n
n
where we use the fact that is k-sparse for the last inequality.
Now we provide the proof for Theorem
Proof of Theorem 7 Theorem 7 implies that the statement of Theorem & hholds with
53 3t and 82
2k n
Noting that y Alpnan e)" FFi(()), where (Rn(k) e|"
MR.t, i. set [T+1] IHT k, T)) and apply Theorem 8 with x [()(()) ejt r Fū and
= supp(z)) (.). Letting zo! [ [] = [+[T+I] clT+ use the facts that || [|a[T++] Bn( ll2 - - ||
log(1/c)++oog ( (1
ssll2 and || | ll2 = | That will give
Letting T
log(1/p)
14

---

Under review as a conference paper at ICLR 2020
gives p" VIl + leel S e, which can be substituted (3) to get (4) Noting that ||e [
-e12
2l(020))122 + 6, we can use the same reasoning as used
Bafna et 2018 to get:
2ct (Tl10 +
||| - #2(c)llos S
(15)
n
4ckt (1l6210))ll2++ +c)
| En(K)]l2 S
(16)
n
which are the essentially the same as the results of Theorem 2.2 Bafna et al. (2018).
Now we prove
5
Write yI8 (214.) A(kK0) where 2(4] x!f-11 A (1 Ax (all"-11 -1). Further, [21]
write
217] [ T
22 I E C²n, where 2|= 22 E C Note that alt) (zf ((a)) Therefore,
have 21 [ F el?- where clT-1] (y F+lT 2) ) Now let S be the set of
indices selected by the hard thresholding operation h((t) to get el e Then observe that =!
F' (y - (y - F 1 ss) Next, note that || |
1T &n(k) 1 as a a best k-sparse || - ||
approximation = We can thus write,
[| 44 (x())) (+(T) =l( | 2 (Re P1 =n(k), x(T) Tr(a)) + [| 1
Therefore, have,
| an( 2Re(=1 [T] 5n(c),, 8131 )n()))
2 (z1 fn(ck) 107 =n(()))
< 2|| [2] - - (lnck)l221180 21 *n(c)) l2
|| lncw)ll2 > O, then - + 2|2 S 2/| 2//2|/7 @n((a)l22 Now note that
|T'
= + F Fr (F FF
-/ -2)) + e)s = F* (F(()(F(( - -lT-21) + e) = i + (F* ))* (F*)s F $ 1/1
Using the fact that (F*)g F (F*) )s can simplify the above to get:
|| 2n(K)l12 [1(F)) (2 +
- --T--11)1
Therefore,
|| T1
BR(K)/12 $ (I((F)) ( + [1 1122-22le||1 + [I(F)) F - =1T-21)
22 [1(0)) |a + ||ella] + (1((( + (( - =fr-2))ll2
where use [I
x 12 2-
F 2- 1. Now since &r(c)) -!(--2 is 2h 2k-sparse, we can
the result Lemma
to get:
|| (v
(2hte) n
|| fn(x)l2e 2 211 [lell2) +2
Rx(K)ll2
Now let p 2/2./ lite
lite, 7(1 - p) = 2 and note that if p <
induction on T to get (5) loog 1/g) (1 ). we have p² ([I S which
Then for any 0 < and any T >
log(1
gives us 6
15

---

Under review as a conference paper at ICLR 2020
A.3 BASIS PURSUIT
Definition 10. The matrix A E C satisfies the robust null space property with constants 0 <
p 1, > 0 and norm || If if for every set S S [N] with card(S) S and for every E C.V have
|eslll S pllugl1a + All
Definition 11. The matrix E Cm satisfies the Eg robust null space property of order s with constants O < p < 1 > 0 and norm || Il if for every set S _ [M] with card(S) I and for every
E C we have
1
|el|| 81 pllvglla =1|
Note that if g then this is simply the robust null space property.
The proof Theorem requires the following theorem (whose full proof is given in the Foucart & Rauhut (2017))
Theorem 12 (Theorem 4.33 in Foucart & Rauhut (2017)). Let 01,.... ON be the columns of A E CmxN let x CN with largest absolute entries supported S, and let y Ar + e with ||e||2 S n. For 8, 8,8, T 2 0 with 8 < 1, assume that:
|AgAs 11 max [|gaull2 B,
LE3
and that there exists a vector A*h CN with h E C such that
luu - sgn(rs)]le 2 ||ugll & 0, and [1lll2 S T T/S.
By < 1, then minimizer ## of ||=||| subject to 1|Az - 4112 S 11 satisfies: If p=:=0= 0 (1-8)
2
8
(2 + TV/) (1+ 1-8 8
3
11 x112 S (1-p) p)
11
||اا||1
2
(1 8)
1-p
00
I3 =
VI+6 where ;== 1-8 and sgn(x); =
1,
>> O.
-1 <
Lemma 13. Let A Cux2a if |x for any S E Sk.
(1+0)|==13fo all x e Ma.. then, ||AzAs 1 1112-+2 S
Proof. Let S E Sk., be given. Then for any E C we have
| 1 || - 611=1|
that A5 I is Hermitian, have: | = (Asæ, Asx) - (0,x)) = ((A3As - T)x,)). Noting
We can re-write this as ||
((AgAg - I)x,, x))
|AgAs 1112-2 = max
||0 < 8
20C*\10)
Proof of Theorem 2 We will derive 7 by showing that the matrix A satisfies all the hypotheses in
Theorem 12 for every vector in MR
First note that by Theorem A satisfies the Mr,- property with constant 6x,1 : V ckt There-
fore, by Lemma 13 for any S Sk,r. we have ||AğAA - l|l2-2 ōu,t. Since A5 is positive semi-definite matrix, it has only non-negative eigenvalues that lie in the range [1 - 8k. 1 + 8x.). Since òx, < 1 by assumption, As is injective. Thus, we can set: h As(A)As) - sg)(xs)
and get:
|| ||As(AAAs) 'sgn(xs) -sgn(=s)))ss(((s))))>>
- (22-- TV
16

---

Under review as a conference paper at ICLR 2020
where 7 V1+8,.1 and have used the following facts: since || T12--1 S ŌR,t < 1-62,t
get that (AA3As)) 112-2 22-2 I 1- and that the largest singular value of Ag is less than / + + ŌR, Now let = A h, then |lug sgn(as)ll2 = 0. Now we need to bound the value ||ugllx- Denoting row, j of AsAs by the vector vy. see that it has most max (k, (k non-zero entries and that [(1))=l² - for = l....,, t). Therefore, for any element (ug)s. we have:
S V
max t
((5g)al = (((A3ss) (sg((ns)) (1,)"> [I())ss) (aaeissss-ll--00 2|ll-2/|sgg(
5x,
Defining 8 == max (k.t)e and 0 == I- B, we get ||ugll S 0 and also observe that
" max ||Azar|l2 S B. Therefore, all the hypotheses of Theorem 12 have been satisfied. Note that Fi+e= A(āa(k) c)T + F(z(K), Therefore, setting x# = BP A. | 112,, we use the fact [ 112 = [| ll2 combined with the bound in Theorem
12 to get (
22 (2TV++] +1 (1+
3
||** tncill2 S
2r [1)20))122
1-
Sx,e
where we write # 1 e with 8t e# E Ca.
We now focus on proving Theorem 3 In order to do we will need some lemmas that will be used in the main proof.
Lemma 14. If a matrix A E Cm satisfies the l2 robust null space property for S C [N], with
card S) = s, then it satisfies the & robust null space property for S with constants p 1, := TV3 >a>>0 0.
Proof. For any E CN, ||us|la I + Then, using the fact that ||us||a S / we get:: ges:l S ellulll I + Av|]
Lemma 15 (Theorem 4.20 in Foucart & Rauhut 2017 ). If a matrix E C N satisfies the & robust null space property (with respect [|-1)) and for 0 p and 0 S c [N]. then:
0 ([|= 11 - | + 21|=s111 + 1
2r ||A( - x)
||2 - x111
S 1
for all 2, x. E C
Lemma (Proposition 2.3 in Foucart Rauhut (2017)) For any p > q > 0 and x E C",
1
inf sEMe
||x =|Ip <
|
(k)
Proof of Theorem 3 E Ch we have
Let < p be arbitrary. Since F is unitary matrix, for any C [n] and
||us||2 <
||gll1 + T||0||2
P Vk
||uz|| + +
(17)
Vk
where 7 1. Now let S C [n]] such that card(S) < k. Then, F satisfies the & robust null space property for S. Next, using Lemma 14 we get ||u [ <pl|v_] + [Vk]] for all C". Now let # = BP F. n), then we know I || S | Fixing S S [m]] to be the support of (x()) and
using Lemma 15 get:
17

---

Under review as a conference paper at ICLR 2020
Layer
Type
Properties
Convolution
32 channels, 3 3 Kernll, No padding 64 channels, 3 x 3 Kernel, No padding, Dropout with 0.5
2
Convolution
Max-p Max-pooling
2, Dropout with p = 0.5
4
Fully Connected
128 neurons, Dropout with p 0.5 10 neurons
5
Fully Connected
Table 5:
Network architecture used for MNIST and Fashion-MNIST datasets in Section and
Section 0
4.2
The first four layers use ReLU activations while the last layer uses softmax activation.
1+
2TV ||F(x* =2]12
11*
1/|1
(1I** 11: | + 2| 211
1 p
1 1 (211
2TV/ F1
$
-2)ll2
p
1 + P (211
47 4T
< -
1 lell2
$ 1 + (211 111)
4 1-
-
Letting - 0 and recalling that 1 gives
Now let S be the support of (x## - i))(k)- Note
|1 = in 11(** 8) = =112- Then, using Lemma 16 and
17 that
|| 0112 I 11x* 8)3112 + 11 - s)s|(2
11x -2)l11 P |1(* +) +T| x2]12
Vk
Vk
+ p
11x - -R)ll1 + 2TT
VT
(1 p)2
(21122())111) + 4T(1 + p)
(1-p) + 2T
Vk(1 pp)
(1 +p2
[TT(1 + p) 2r (1 - p)
(21(m
Vk(1 p)
Recalling and letting > 0 gives the desired result.
A.4 DANTZIG SELECTOR
Next introduce the Dantzig Selector algorithm with an additional constraint. We first prove its recovery guarantees for fo -oom and then explain the reasoning behind the additional constraint.
Proof of Theorem 4 The proof follows the same structure as the proof of Theorem Therefore provide sketch and leave out the complete derivation. Let 0 unitary matrix, for any 5 [ [n] and E Ch,, we have
be arbitrary. Since F is
||sl||2 I
|cyll1 + ||el||2 S P |llllla + VAllulso V
|1 + F[][FFFFlll Vi
P
VR
=
The rest of the argument is the same as in the proof of Theorem
18


Reviews:
[{"review_id": "SylPwe8AKB", "reviewer": "AnonReviewer1", "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": "This paper extends the compressive sensing framework introduced in Bafna et al. to handle l1 and l2 attacks. The authors provide theoretical analysis for several recovery algorithms (IHT, BP, DS) and provide experimental result on CIFAR-10, MNIST and Fashion-MNIST. \n\nMy major concern is how significant the provided results are. It is indeed interesting to extend the compressive sensing framework to handle l1 and l2 attacks. However, the proposed recovery algorithms are all classical ones, and it is unclear how novel the analysis is, since the authors do no discuss the technical challenges they overcome or the difference between their proof techniques and the previous ones. Also, it would be nice if the authors could discuss the theoretical results in more detail, e.g., how to interpret them and new insights it brings to us. \n\nMoreover, some experimental details are missing. In last paragraph in Section 3.1, the authors say ``We then use both x and x′ to train the network''. How do you do so? Just add both x and x' to the training set? ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJgxdIHqFB", "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 studies the problem of the robustness of the neural network-based classification models under adversarial attacks. The paper improves upon the known framework on defending against l_0, l_2 norm attackers. \n\nThe main idea of the algorithm is to use the \"compress sensing\" framework to preprocess the image: Using F, the discrete Fourier transformation matrix, and the algorithm tries to reproduce on every given input x, a vector y with the smallest number of non-zero coordinate such that Fy approximates x. The main algorithms proposed in this paper are sparse iterative hard thresholding (IHT) or base pursuit (BP) which are all quite simple and standardized. \n\nThe intuition of the approach is that l_0, l_2 attackers on the original input x can not allude the sparse vector y by too much, thus the recovered vector Fy could have better robustness property comparing to the original input x. \n\n\nThe main concern for me is the experiment in this paper. The author does not provide enough details about how the attacker is trained in their task. It seems that the authors only use the attacker trained on a standard neural network. However, since the authors have a preprocessing algorithm (IHT, BP) on top of the given input, the attacker should in principle tries to attack this pre-processing process as well. Since the pre-processing process is not differentiable, it is, therefore, unclear to me how to define the true robustness of the approach of the authors. \n\nAn analog of my argument is if we create an artificial network that has a pre-processing layer that zeros out most of the input pixel, however, if we train an attacker without this knowledge (so it tries to attack a network without this pre-processing), the l_2, l_0 attacker might not be very good for the true network. \n\n\nAfter Rebuttal: I have read the authors' responses and acknowledge the sensibility of the statement. However, I still think the algorithm in this paper is merely a \"clever\" version of gradient masking, which does not give the neural networks real robustness, it is just harder to design attacks on all these discrete operations.\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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": "H1xdXAoCYB", "reviewer": "AnonReviewer2", "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": "This paper extends the compressive recovery defense framework introduced by Bafna et al. (2018), which is mainly against l_0 attacks, to l_2 and l_∞ attacks. They provide guarantees for some recovery algorithms in the case of different kinds of norm bounded noises. The difference between their work and the previous work is clearly clarified. \n\nOverall, this paper is a follow-up work towards Bafna et al. (2018) but with better theoretical guarantees and ample experiment results to support their robustness against various popular attacks. Given their contribution and inspiration for future work, I think this paper could be accepted to the 2020 ICLR conference. \n\nIn Section 3.2 Recovery Algorithms, the author clearly states three algorithms including IHT, BP, DS, and their modification from the standard ones, but fails to compare the differences between these algorithms. It is not clear about the author’s motivations to proposes these different recovery algorithms and whether their performance varies from each other also remains unknown. Maybe some analysis about their disadvantages and advantages in varied conditions of attacks could be necessary. \n\nIn the Section 3.4 Comparison to Related Work, the author mentions many works aiming at defending against adversarial inputs. However, Bafna et al. (2018) is the only work here that has something to do with compressive sensing. I think maybe the paper should involve some related work here regarding theory of compressive coding besides Bafna et al. (2018). And how they are combined to the defense against adversarial inputs. It would help the readers to have better understanding towards the novelty and breakthroughs in this aspect. \n\nFor the experiments, it would be better to have the comparisons between the proposed algorithm and related methods. Also, the proposed IHT and DS are modified versions. What are the differences in experiments? \n\nMinor comments:\n- Page 2: the line above the equation 1 ‘meaning that x_t (k)…..’, it could be (x_t ) ̂(k)\n- Page 6: in the explanation of figure 2, the adversarial inputs are second column and fifth column not fourth column. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: After reading the author's response, all the reviwers still think that this paper is a simple extension of gradient masking, and can not provide the robustness in neural networks.
Decision: Reject