Enhancing Adversarial Defense by k-Winners-Take-All
Authors: Chang Xiao
Peilin Zhong
Changxi Zheng
Venue:  (2020)
Keywords: adversarial defense
activation function
winner takes all

Abstract: We propose a simple change to existing neural network structures for better defending against gradient-based adversarial attacks. Instead of using popular activation functions (such as ReLU), we advocate the use of k-Winners-Take-All (k-WTA) activation, a C0 discontinuous function that purposely invalidates the neural network model’s gradient at densely distributed input data points. The proposed k-WTA activation can be readily used in nearly all existing networks and training methods with no significant overhead. Our proposal is theoretically rationalized. We analyze why the discontinuities in k-WTA networks can largely prevent gradient-based search of adversarial examples and why they at the same time remain innocuous to the network training. This understanding is also empirically backed. We test k-WTA activation on various network structures optimized by a training method, be it adversarial training or not. In all cases, the robustness of k-WTA networks outperforms that of traditional networks under white-box attacks.

Published as a conference paper at ICLR 2020
ENHANCING ADVERSARIAL DEFENSE BY k: WINNERS- TAKE-ALL
Chang Xiao
Peilin Zhong
Changxi Zheng
Columbia University
(chang, peilin, cxz ) 0 css.. columbia. ia. edu
ABSTRACT
We propose simple change to existing neural network structures for better defend- ing against gradient-based adversarial attacks. Instead of using popular activation functions (such as ReL.U), we advocate the use of k- Winners-Taae-An (k- (T-) ac- tivation, O discontinuous function that purposely invalidates the neural network model's gradient at densely distributed input data points. The proposed Æ- 6-WTA activation can be readily used in nearly all existing networks and training methods with no significant overhead. Our proposal is theoretically rationalized. We analyze largely prevent gradient-basse
why the discontinuities in k- WTA networks search of adversarial examples and why they at the same time remain innocuous the network training. This understanding is also empirically backed. We test k- CTWT activation on various network structures optimized by a training method, be it adversarial training or not. In all cases, the robustness of k-W networks outperforms that of traditional networks under white-box attacks.
INTRODUCTION
In the tremendous success of deep learning techniques, there is a grain of salt. It has become well- known that deep neural networks can be easily fooled by adversarial examples (Szegedy et al., 2014). Those deliberately crafted input samples can mislead the networks to produce an output drastically different from what we expect. In many important applications, from face recognition authorization to autonomous cars, this vulnerability gives rise to serious security concerns (Barreno et al., 2010; 2006; Sharif al., 2016; Thys et al., 2019).
Attacking the network is straightforward. Provided labeled data item (æ,,), y). the attacker finds perturbation x' perceptually similar to æ but misleading enough to cause the network to output a label different from y. By far, the most effective way of finding such a perturbation (or adversarial example) is by exploiting the gradient information of the network with respect to its input: the gradient indicates how perturb to trigger the maximal change of y.
The defense, however, is challenging. Recent studies showed that adversarial examples always exist if one tends to pursue a high classification accuracy adversarial robustness seems at odds with the accuracy (Tsipras et al., 2018; Shafahi et al., 2019a; Su et al., 2018a; Weng et al., 2018; Zhang et al., 2019). This intrinsic difficulty of eliminating adversarial examples suggests an alternative path: can we design a network whose adversarial examples are evasive rather than eliminated? Indeed, along with this thought is a series of works using obfuscated gradients as a defense mechanism (Athalye et al., 2018). Those methods hide the network's 's gradient information by artificially discretizing the input (Buckman et al., 2018; Lin et al., 2019) or introducing certain randomness to the input (Xie et al., 2018 8a; Guo et al., 2018) or the network structure (Dhillon et al., 2018 8; Cohen al., 2019) (see more discussion in Sec. 1.1). Yet, the hidden gradient in those methods can still be approximated, and as recently pointed out by Athalye et al. (2018), those methods remain vulnerable.
Technical contribution I) Rather than obfuscating the network's gradient, we make the gradient undefined. This is achieved by a simple change to the standard neural network structure: we advocate the use of C* discontinuous activation function, namely the k- d-Winners-Takee Take-All (K-WTA) activation, to replace the popular activation functions such as rectified linear units (ReLU). This is the only deep neural network. All other components (such as BatchNorm, convolution, and pooling) as well as the training methods remain unaltered. With no significant overhead, A- WTA activation can be readily used in nearly all existing networks and training methods.
change we propose

---

Published as a conference paper at ICLR 2020
k- B-WTA activation takes input the entire output of a layer, retains its k largest values and deactivates all others to zero. As we will show in this paper, even an infinitesimal perturbation to the imput may cause a complete change to the network neurons' activation pattem, thereby resulting in large jump in the network's ss output. This means that, mathematically, if we use f(æ; w)) to denote a k-WTA network taking an input a: and parameterized by weights w, then the gradient V (a;; w) at certain x' is undefined-ffet" w) is C*) discontinuous.
Technical contribution II) More intriguing than the mere replacement of the activation function is why k-WTA helps improve the adversarial robustness. We offer our theoretical reasoning of its behavior from two perspec- tives. On the one hand, we show that the discontinuities of fæ; w) is densely distributed in the space of æ. Dense enough such that a tiny perturbation from any æ almost always comes across some discontinuities, where the gra- dients are undefined and thus the attacker's search of adversarial examples becomes blinded (see Figure 1).
Figure 1: 1D illustration. Fit a 1D func- tion (green dotted curve) using k-WTA model provided with a set of points (red). The resulting model is piecewise contin- uous (blue curve), and the discontinuities can be dense.
On the other hand, paradox seemingly exists. The dis- continuities in the activation function also renders ff (a:; w) discontinuous with respect to the network weights w (at certain w values). But training the network relies on the presumption that the gradient with respect to the weights is almost always available. Interestingly, we show that, under k-WTA activation, the discontinuities of f(x; w) is rather sparse in the space of w. intuitively because the dimension of w (in parameter space) is much larger than the dimension of æ (in data space). Thus, the network can be trained successfully.
Summary of results. We conducted extensive experiments on multiple datasets under different network architectures, including ResNet (He et al., 2016). DenseNet (Huang et al., 2017), and Wide ResNet (Zagoruyko & Komodakis, 2016), that are optimized by regular training as well as various adversarial training methods (Madry et al., 2017: Zhang et al., 2019; Shafahi et al., 2019b).
In all these setups, we compare the robustness performance of using the proposed k-WTA activation with commonly used ReI.U activation under several white-box attacks, including PGD (Kurakin et al., 2016), Deepfool (Moosavi-Dezzooli et al., 2016), C&W (Carlini Wagner, 2017), MIM (Dong et al., 2018), and others. In all tests, &-WTA networks outperform ReLU networks.
The use of k-AA activation is motivated for defending against gradient- based adversarial attacks. Our experiments suggest that the robustness improvement gained by simply switching to k-WTA activation is universal, not tied to specific network architectures or training methods. To promote reproducible research, we will release our implementation of k-WTA networks, along with our experiment code, configuration files and pre-trained models!.
1.1 RELATED WORK: OBFUSCATED GRADIENTS AS DEFENSE MECHANNSMM
Before delving into k- &TA details, we review prior adversarial defense methods that share the same philosophy with our method and highlight our advantages. For a review of other attack and defense methods, we refer to Appendix A.
Methods aiming for concealing the gradient information from the attacker has been termed as obfuscated gradients (Athalye et al., 2018) or gradient masking (Papernot et al., 2017; Tramèr al., 2017) techniques. One type of such methods is by exploiting randomness, either randomly transforming the input before feeding it to the network (Xie et al., 2018a; Guo et al., 2018) or introducing stochastic layers in the network (Dhillon et al., 2018). However, the gradient information in these methods can be estimated by taking the average over multiple trials (Athalye et al., 2018; 2017). As a result, these methods are vulnerable.
Another type of obfuscated gradient methods relies on the so-called shattered gradient (Athalye et al., 2018), which aims to make the network gradients nonexistent or incorrect to the attacker, by purposely discretizing the input (Buckman et al., 2018; Ma et al., 2018) or artificially raising numerical instability for gradient evaluation (Song et al., 2018; Samangouei et al., 2018). Unfortunately, these methods are also vulnerable. As shown by Athalye et al. (2018), they can be compromised by backward pass
2

---

Published as a conference paper at ICLR 2020
0.8
0.8
0.8
Q2
1.7
1.7
1.7
1.7
17
1.2
1.7
8.9
0.9
ReLU
Maxpool
LWTA
k-WTA
Figure 2: Different activation functions. ReLU: all neurons with negative activation values will be set to zero. Max-pooling: only the largest activation in each group is transmitted to the next layer, and this effectively downsample the output. LWTA: the largest activation each group retains its value when entering the next layer, others are set to zero. k- WTA the & largest activations in the entire layer retain their values when entering the next layer, others are set to zero (k in this example). Note that the output is not downsampled through ReLU, LWTA and k-WTA
differentiable approximation (BPDA). Suppose fx) is non-differentiable component of network expressed by fi fz o... fn- The gradient V can estimated long as one can find smooth delegate y that approximates well Sú (i.e., g(x) R f((z)).
In stark contrast to all those methods, a slight change of the k-WTA activation pattern in an earlier layer of network can cause radical reorganization of activation patterns in later layers (as shown in Sec. 3). Thereby, k-WTA activation not just obfuscates the network's gradients but destroys them certain input samples, introducing discontinuities densely distributed in the input data space. We are not aware of any possible smooth approximation of a TTA network to launch BPDA attacks.
2 k- WINNERS WVINNERS-TAKE-LLL ACTIVATION
The debut of the Winner-Takes-Al (WTA) activation on the stage of neural networks dates back to 1980s, when Grossberg (1982) introduced shunting short-term memory equations in on-center off-surround networks and showed the ability identify the largest of N real numbers. Later, Majani et al. (1989) generalized the WTT network to identify the K largest of N real numbers, and they termed the network the K- functions output only boolean values, mainly motivated by the properties of biological neural circuits. In particular, Maass (2000a:b) has proved that any boolean function can be computed by a single KWTA unit. Yet, the boolean nature of these activation functions differs starkly from the modern activation functions, including the one use.
(KWTA) network. These early WTA-type activation
2.1 DEEP NEURAL NETWORKS ACTIVATED BY A- WINNERS TAKE-ALL
We propose to use A- Winners-Tatee Take-All (k- WTA) activation, natural generalization of the boolean KWTA² (Majani et al., 1989). k-ATAA retains the largest values of an N input vector and sets all others to be zero before feeding the vector to the next network layer, namely,
ex = Yi. Yj {k largest elements of y) Otherwise.
(1)
Here du N N is the W-AA function (parameterized the activation, and di (y), denote the j-the element of the output de (y) (see the rightmost subfigure of Figure 2). Note that if y has multiple elements that are equally k-th largest, break the tie by retaining the element with smaller indices until the slots are taken.
integer k), y R is the input to
When using k- WTA activation, we need to choose Yet it makes no sense to fix & throughout all layers of the neural network, because these layers often have different output dimensions; small to one layer's dimension can be relatively large to the other. Instead of specifying k, we introduce
In this paper, use k-WTA to refer activation function, while using KWTA to refer the original boolean version by Majani al. (1989).

---

Published as a conference paper at ICLR 2020
parameter 7 (0.1) called sparsity ratio. If a layer has output dimension N, then its k-WTA activation has lt = 1y -N. Even though the sparsity ratio can be set differently for different layers, in practice we found no clear gain from introducing such variation. Therefore, use fixed 7 the only additional hyperparameter needed for the neural network.
In convolutional neural networks (CNN), the output of a layer is a C' x H x W tensor. C denotes the number of output channels; H and W indicate the feature resolution. While there are multiple choices of applying k- WTA on the tensor-for example, one can apply k-WTA individually to each caannel--mpiricallll we found that the most effective (and conceptually the simplest) way is to treat the tensor as a long C- H- - W X vector input to the k-WTA activation. Using k- 4-WTA in this way is also backed by our theoretical understanding (see Sec. 3).
The runtime cost of computing a k- 6-W activation is asymptotically O(N), because finding & largest values in a list is asymptotically equivalent to finding the k-thh largest value, which has an O(N) complexity (Cormen et al., 2009). This cost is comparable to ReLU's O(N) cost on a N N-length vector. Thus, replacing ReLU with k-WTA introduces no significant overhead.
Remark: other WTA-type activations. Relevant to k-WTA is the local Winner-Take-All (LWTA) activation (Srivastava et al., 2013; 2014), which divides each layer's output values into local groups and applies WTA to each group individually. LWTA is similar to max- max-loooing (Riesenhuber & Poggio, 1999) for dividing the layer output and choosing group maximums. But unlike ReLU and max-pooling being C continuous, LWTA and our k: 5-T are both discontinuous with respect to the input. The differences among ReLU,, max max-pooling pooling. LWTA, and k-WTA are illusrated in Figure
LWTA is motivated toward preventing catastrophic forgetting (McCloskey & Cohen, 1989), whereas our use of k- WTA is for defending against adversarial threat. Both are discontinuous. But it remains unclear what the LWTA'S discontinuity properties are and how its discontinuities affect the network training. Our theoretical analysis (Sec. 3), in contrast, sheds some light on these fundamental questions about W-WAA, rationalizing its ability for improving adversarial robustness. Indeed, our experiments confirm that T-A outperforms LWTA in terms of robustness (see Appendix D.3).
WTA--yppe activation, albeit originated decades ago and widely studied in computational neuro- science (Douglas et al., 1989; Douglas & Martin, 2004), remains elusive in modern neural networks. Perhaps this is because it has not demonstrated a considerable improvement to the network's 'ss standard test accuracy, though it can offer accuracy comparable to ReLU (Srivastava et al., 2013). Our analysis and proposed use of k- W-A and its enabled improvement on adversarial defense may suggest renaissance of studying WTA.
2.2 TRAINING k- WTA NETWORKS
k WTA networks require no special treatment in training. Any optimization algorithm (such as stochastic gradient descent) for training ReLU networks can be directly used to train k-WTA networks.
Our experiments have found that when the sparsity ratio 7 is relatively small (< 0.2), the network training converges slowly. This is not a surprise. A smaller y activates fewer neurons, effectively reducing more of the layer width and in turn the network size, and the stripped "subnetwork" is much less expressive (Srivastava et al., 2013). Since different training examples activate different subnetworks, collectively they make the training harder.
Nevertheless, we prefer a smaller 7. As we will discuss in the next section, a smaller 7 usually leads to better robustness against finding adversarial examples. Therefore, to ease the training (when y is small), we propose to use an iterative fine-tuning approach. Suppose the target sparsity ratio is YI- We first train the network with larger sparsity ratio "o using the standard training process. Then, we iteratively fine tune the network. In each iteration, we reduce its sparsity ratio by small 8 and train the network for two epochs. The iteration repeats until % is reduced ?1-
This incremental process introduces little training overhead, because the cost of each fine tuning is negligible in comparison to training from scratch toward Nu- We also note that this process is optional. In practice we use it only when 7 0.2. We show more experiments on the efficacy of the incremental training in Appendix D.2.
3 UNDERSTANDING k- WTA DISCONTINUITY
We now present our theoretical understanding of k 6-WT discontinuity behavior in the context of deep neural networks, revealing some implication toward the network's adversarial robustness.
4

---

Published as a conference paper at ICLR 2020
Logit value
Logit value
Loss
25
20
100 Step 0
(b)
100 Step
(c)
100 Step
Figure 3: (a, b) We plot the change of 10 logits values when conducting untargeted PGD attack with 100 iterations. X-axis indicates the perturbation size and Y-axis indicates the 10 color-coded logits values. (a) When we apply PGD attack on k-WTA ResNet18, the strong discontinuities w.r.t. to input invalidate gradient estimation, effectively defending well against the attack. (b) In contrast, for ReLU ResNet18, PGD attack can easily find adversarial examples due to the model's smooth change w.r.t. input. (c) In the process of training k-WTA ResNet18, the loss change w.r.t. model weights is largely smooth. Thus, the training is not harmed by k- k-Wasss discontinuities.
Activation pattern. To understand k- 6-WTA's discontinuity, consider layer outputting values æ, passed through a k- k-WTA activation, and followed by the next layer whose linear weight matrix is W (see adjacent figure). Then, the value fed into the next activation can be expressed as Wø)(z), where (-) the k-WTA function defined (I). Suppose the vector has length We define the k-WTA's 's activation pattern under the input
L
W
I-WIA
A(x) = ii E [4] I; is one of the k largest values in æ} S [4]-
(2)
Here (and throughout this paper), we use [I] to denote the integer set 21.
Discontinuity. The activation pattern A(x) is a key notion for analyzing k-WTA's discontinuity behavior. Even an infinitesimal perturbation of may change A(x): some element is removed from A(x) while another element j is added in. Corresponding to this change, in the evaluation of (x)), the contribution of W's column vector W, vanishes while another column W, suddenly takes effect. It is this abrupt change that renders the result of Web((2) C discontinuous.
Such a discontinuity jump can be arbitrarily large, because the column vectors We and W, can be of any difference. Once W determined, the discontinuity jump then depends on the value of x; and zz. As explained in Appendix B, when the discontinuity occurs, T; and tú have about the same value, depending on the choice of the sparsity ratio y (recall Sec. 2.1) the smaller the 7 is, the larger the jump will be. This relationship suggests that a smaller will make the search of adversarial examples harder. Indeed, this is confirmed through our experiments (see Appendix D.6).
Piecewise linearity. Now, consider an n-layer k-WA network, which can be expressed as f(x) W(1) Φx (W(2) di (l (W()) b("))) b(2)) + b(1), where W(O and ((4) are the i-th layer's weight matrix and bias vector, respectively. If the activation patterns of all layers are fixed, then f(x) a linear function. When the activation pattern changes, f(x) switches from one linear function to another linear function. Over the entire space of f(x) is piecewise linear. The specific activation patterns of all layers define a specific linear piece of the function, or a linear region (following the notion introduced by Montufar et al. (2014)). Conventional ReLU (or hard tanh) networks also represent piecewise linear functions and their linear regions are joined together at their boundaries, whereas in F-WTA networks the linear regions disconnected (see Figure 1).
Linear region density. Next, we gain some insight the distribution of those linear regions. This is of our interest because if the linear regions are densely distributed, a small Aæ perturbation from any data point will likely cross the boundary of the linear region where locates. Whenever boundary crossing occurs, the gradient becomes undefined (see Figure 3-a).
For the purpose of analysis, consider an input & passing through a layer followed by k- &-WTA activation (see adjacent figure). The output from the C
W
activation is Φv (Wæ + b). We would like to understand, when x is changed into x', how likely the activation pattern of OR will change. First, notice that x' and æ satisfy x' = c x with some e > O, the activation pattern remains unchanged. Therefore, introduce notation d(æ x²) that measures the "perpendicular" distance between and æ', one
&-WAA
5

---

Published as a conference paper at ICLR 2020
that satisfies x' = cx + d( x' x1)) for some scalar c, where I is a unit vector perpendieular to a and on the plane spanned by æ and x'. With this notion, and if the elements in W is initialized by sampling from (0, 4) and b is initialized zero, we find the following property:
Theorem (Dense discontinuities). Given any input xn E Rm and some B, and Vac T such that
d' (m,,"")) 1
2 3, if the following condition
m (m=
log m 1 Y 3 1
12 Ω
3
is satisfied, then with a probability at least 1 - -h, "h we have A(Wx + b) 4 A(Wa' + b).
Here I is the width of the layer, and is again the sparsity ratio in F-WAA This theorem informs us that the larger the layer width is, the smaller B and thus the smaller perpendicular perturbation distance d(x - needed to trigger change of the activation pattern, that is, as the layer width increases, the piecewise linear regions become finer (see Appendix C for proof and more discussion). This property also echos similar trend in ReLU networks, as pointed out by Raghu et al. (2017).
Why is the WTA network trainable? While k-WTA networks are highly discontinuous as revealed by Theorem 1 and our experiments (Figure 3-a), in practice we experience no difficulty on training these networks. Our next theorem sheds some light on the reason behind the training success.
Theorem 2. Consider N data points I1. D2. EN E R". Suppose Vi + j. Tmllla + sufficiently large, then with a high probability, we have Vi + A.W(; + b) A(Wx, + b) 2.
| a If
This theorem is more formally stated in Theorem 10 in Appendix C together with a proof there.
Intuitively speaking, it states that if the network is sufficiently wide, then for any + j. activation pattern of input data Φ; is almost separated from that of x,, Thus, the weights for predicting x; 's and zj 's labels can be optimized almost independently, without changing their individual activation patterns. In practice, the activation patterns of x; and æ; are not fully separated but weakly correlated. During the optimization, the activation pattern of data point 2; may change, but the chance is relatively low-a similar behavior has also been found in ReLU networks (Li & Liang, 2018; Du al., 2018; Allen-Zhu et al., 2019a;b; Song & Yang, 2019).
Further, notice that the training loss takes summation over all training data points. This means weight update would change only a small set of activation patterns (since the chance of having the pattern changed is low); the discontinuous change the loss value, after taking the summation, will be negligible (see Figure 3-c). Thus, the discontinuities in k WTA is not harmful to network training.
4 EXPERIMENTAL RESULTS
We evaluate the robustness of WTA networks under adversarial attacks. Our evaluation considers multiple training methods on different network architectures (see details below). When reporting statistics, we Arob indicate the worst-case robustness accuracy test data under all adversarial attacks we evaluated, and use Asd to indicate the accuracy on the clean test data, We use k-WTA-- to represent 6TA activation with sparsity ratio 7.
4.1 ROBUSTNESS UNDER BHITE-BOX ATTACKS
The rationale behind &- WTA activation is to destroy network gradients-informen inffrratiin needed in white-box attacks. We therefore evaluate k-WTA networks under multiple recently proposed white- box attack methods, including Projected Gradient Descent (PGD) (Madry et al., 2017). Deep- fool (Moosavi-Dezfooli et al., 2016), C&W attack (Carlini & Wagner, 2017), and Momentum Iterative Method (MIM) (Dong et al., 2018). Since k-WTA activation can be used in almost any training method, be it adversarial training or not, we also consider multiple training methods, including natural training, adversarial training (AT) (Madry et al., 2017), TRADES (Zhang et al., 2019) and free adversarial training (FAT) (Shafahi et al., 2019b).
In addition, we evaluate the robustness under transfer-based Black-box (BB) attacks (Papernot et al., 2017). The black-box threat model requires no knowledge about network architecture and parameters. Thus,
a pre-traace pre-trained VGG19 network (Simonyan & Zisserman, 2014) as the source model to generate adversarial examples using PGD. As demonstrated by Su et al. (2018b), VGG networks have the strongest transferability among different architectures.

---

Published as a conference paper at ICLR 2020
Table Adversarial robustness on CIFAR-10 and SVHN datasets. Arob in the last column denotes the empirical worst-case robustness among different attacks (columns) for each network optimized by different training methods (row). The bold numbers indicate the best Aras robustness achieved on ReLU and k-WTA networks by each training method.
CIFAR-10
Training
Activation
Aged
PGD
C&W
Deepfool
MIM
BB
Arob
ReLU
92.9%
0.0%
0.0%
1.5%
0.0%
18.9%
0.0%
Natural
k-WTA-0.1
89.3%
13.3%
27.9%
55.6%
13.1%
62.6%
13.1 %
k-WTA-0.2
91.7%
4.2%
6.2%
47.8%
3.9%
66.8%
4.2%
ReLUU
83.5%
46.3%
43.6%
46.8%
45.9%
71.0%
43.6%
AT
k-WTA-0.1
78.9%
51.4%
64.4%
70.4%
50.7%
73.4%
50.7% %
k-WTA-0.2
81.4%
48.4%
52.7%
66.1%
47.4%
73.5%
47.4%
ReLU
79.7%
49.8%
52.3%
57.6%
49.9%
70.6%
49.8%
TRADES
k-WTA-0.1
76.6%
55.0%
62.2%
66.0%
57.5%
72.3%
55.0%
k-
80.4%
51.5%
57.7%
63.9%
53.4%
74.7%
51.5%
ReLUU
82.6%
42.7%
44.4%
49.7%
41.6%
73.4%
41.6%
FAT
k-WTA-0.1
78.4%
51.7%
66.3%
72.4%
49.1%
72.3%
49.1 %
k-WTA-0.2
82.8%
48.4%
60.5%
67.2%
46.7%
76.8%
46.7%
SVHN
Training
Activation
Asid
PGD
C&W
Deepfool
MIM
BB
Arob
ReLU
95.1%
0.0%
0.0%
2.5%
0.0%
14.7%
0.0%
Natural
k-WTA-0.1
92.6%
10.2%
19.5%
88.7%
11.6%
51.4%
10.2%
k-WTA-0.2
93.8%
4.3%
8.0%
86.8%
8.3%
56.7%
4.3%
ReLU
84.2%
44.5%
42.7%
70.3%
48.4%
77.7%
42.7%
AT
k-WTA-0.1
79.9%
62.2%
65.7%
71.5%
56.9%
76.1%
56.9%
k-WTA-0.2
82.4%
53.2%
63.6%
77.4%
52.3%
74.2%
52.3%
ReLU
84.7%
47.4%
51.6%
76.9%
49.6%
76.5%
47.4%
TRADES
k-WTA-0.1
81.6%
61.3%
77.4%
79.4%
58.3%
78.1%
58.3%
k-WTA-0.2
85.4%
56.7%
59.2%
71.6%
54.5%
79.3%
54.5%
ReLU
85.9%
40.8%
46.2%
76.1%
39.9%
76.9%
40.8%
FAT
k-WTA-0.1
85.5%
57.7%
70.0%
77.0%
62.8%
75.6%
57.7%
W-T--002
86.8%
54.3%
64.3%
74.7%
55.2%
74.4%
54.3%
In each setup, compare the robust accuracy of k-WTA networks with standard ReLUU networks on three datasets, CIFAR-10, SVHN, and MNIST. Results on the former two are reported in Table while the latter is reported in Appendix D.4. We use ResNet-18 for CIFAR-10 and SVHN. The perturbation range 0.031 (CIFAR-1O) and 0.047 (SVHN) for pixels ranging [0, 1]. More detailed training and attacking settings reported in Appendix D.1.
The main takeaway from these experiments (in Table 1) is that k-WTA is able to universally improve the white-box robustness, regardless of the training methods. The k-WTA robustness under black-box attacks is not always significantly better than ReLU networks. But black-box attacks, due to the lack of network information, are generally much harder than white-box attacks. In this sense, white-box attacks make the networks more vulnerable, and W-AA is able to improve network's worst-case robustness. This improvement not tied to any specific training method, achieved with no significant overhead, just by a simple replacement of ReLU with k- WTA.
Athalye et al. (2018) showed that gradient- based defenses may render the network more vulnerable under black-box attacks than under gradient-based white-box attacks. However, have not observed this behavior in k- 6-WTA networks. Even under the strongest black-box attack, i.c., by generating adversarial examples from an independently trained copy of the target network, gradient-based attacks are still stronger (with higher successful rate) than black-box attacks (see Appendix D.3).
Additional experiments include: 1) tests under transfer attacks across two independently trained 6-WTA networks and across k- G-WTA and ReLU networks, 2) evaluation of k-WTA performance different network architectures, and 3) comparison of k-WTA performance with LWTA (recall Sec. 2.1) performance. See Appendix D.3 for details.
7

---

Published as a conference paper at ICLR 2020
Ast
Aya
0.9
0.20
0.8
0.15
0.7
Wide ResNet
0.10
0.6
DenseNet121
0.05
0.5
ResNet18
0.20
0.16
0.12
0.08
0.04
?
0.20
0.16
0.12
0.08
0.04 7
Figure 4: Robustness changing w.r.t. y CIFAR. When 7y decreases, the standard test accuracy (left)
starts to drop after certain point. The robust accuracy (right) first increases then decreases.
(a) ResNet18-0.1
(b)ResNet18-0.) +adv
(c) ResNet18 (Vanilla)
(d) ResNett 8+adv
20
6
25
10
10
15
6
0.04
0.04
0.04
0.04
0.04
0.00
0.04
0.00
0.04
0.00
0.04
0.00
<1
0.00
-0.04
-0.04
52
0.00
-0.04
-0.04
22
0.00
-0.04
-0.04
22
0.00
-0.04
-0.04
Figure 5: Gradient- attack's 's loss landscapes in A- TTA (a, b) and conventional ReLU models (c, d). (a.b) k-WTA Models have much more non-convex and non-smooth landscapes. Also, the model optimized by adversarial training (b) has lower absolute value of loss.
4.2 VARYING SPARSITY RATIO 7 AND MODEL ARCHITECTURE.
We further evaluate our method on various network architectures with different sparsity ratios Figure 4 shows the standard test accuracies and robust accuracies against PGD attacks while ? decreases. To test on different network architectures, we apply K-WAA to ResNet18, 88, DenseNet122 and Wide ResNet (WRN-22-12) In each case, starting from y = 0.2, we decrease y using incremental fine-tuning. We then evaluate the robust accuracy CIFAR dataset, taking 20-iteration PGD attacks with perturbation range = 0.31 for pixels ranging [o. 1].
We find that when 7 is larger than 0.1, reducing Y has little effect the standard accuracy, but increases the robust accuracy. When 7 is smaller than ~ 0.1, reducing drastically lowers both the standard and robust accuracies. The peaks in the Arob curves (Figure 4-right) consistent with theoretical understanding: Theorem suggests that when is fixed, a smaller y tends to sparsify the linear region boundaries, exposing more gradients to the attacker. Meanwhile, as also discussed in Sec. 3, smaller leads to larger discontinuity jump and thus tends to improve the robustness.
4.3 Loss LANDSCAPE GRADIENT-BAN BASED ATTACKS
We now empirically unveil why A-WTA is able improve the network's robustness (in addition to our theoretical analysis in Sec. 3). Here we visualize the attacker's loss landscape in gradient-based attacks in order reveal the landscape change caused by k-WTA Similar to the analysis in Tramèr et al. (2017), we plot the attack loss of a model with respect to its input points x'' = x 61 + where æ a test sample from CIFAR test set, 91 is the direction of the loss gradient with respect to the input, g2 is another random direction, E1 and E2 sweep in the range of [-0.04, 0.04], with 50 samples each. This results in a 3D landscape plot with 2500 data points (Figure 5).
As shown in Figure 5, k- T- models (with 7 = 0.1) have highly non-convex and non-smooth loss landscape. Thus, the estimated gradient is hardly useful for adversarial searches. This explains why k-WTA models can effectively resist gradient-based attacks. In contrast, ReLU models have much smoother loss surface, from which adversarial examples can be easily found using gradient descent.
Inspecting the range of loss values in Figure 5, we find that adversarial training tends to compress the loss landscape's dynamic range in both the gradient direction and the other random direction, making the dynamic range smaller than that the models without adversarial training. This phenomenon has been observed in ReLU networks (Madry et al., 2017: Tramèr et al., 2017). Interestingly. k-WTA models manifest a similar behavior (Figure 5-a.b). Moreover, we find that in f:- (-WTA models larger y leads smoother loss surface than smaller (see Appendix D.6 for more details).
8

---

Published as a conference paper at ICLR 2020
5 CONCLUSION
This paper proposes to replace widely used activation functions with the k-WTA activation for improving the neural network's robustness against adversarial attacks. This is the only change advocate. The underlying idea is embrace the discontinuities introduced by k-WTA functions to make the search for adversarial examples more challenging. Our method comes almost for free, harmless to network training, and readily useful in the current paradigm of neural networks.
Acknowledgments. This work was supported in part by the National Science Foundation MAAEEER-445300.
(CAREER- 1453101. 1816041, 1910839, 1703925, 1421161, 1714818, 1617955, 1740833), Si- mons Foundation (#491119 to Alexandr Andoni), Google Research Award, a Google PhD Fellowship, Snap Research Fellowship, a Columbia SEAS CKGSB Fellowship, and SoftBank Group.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate training recurrent neural networks. In NeurlPS. https:
111.....6......1..... 12065, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via parameterization. In ICML. http://pss//ax...oooo///.t.te/.e
03962, 2019b.
Anish Athalye, Logan Engstrom, Andrew llyas, and Kevin Kwok. Synthesizing robust adversarial examples. arXiv preprint arXiv:/707.07333 2017.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Cireumventing defenses to adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICMI. 2018, July 2018. URL https::/// /ttp///axvvvv/..///e//eee///.a org/ abs/ 1802. 00420.
Marco Barreno, Blaine Nelson, Russell Sears, Anthony D Joseph, and Doug Tygar. Can machine learning be secure? In Proceedings of the 2006 ACM Symposium on Information, computer and communications security, pp. 16-25. ACM, 2006.
Marco Barreno, Blaine Nelson, Anthony D Joseph, and J Doug Tygar. The security of machine learning. Machine Learning, 81()):211-148, 2010.
Wieland Brendel, Jonas Rauber, and Matthias Bethge. Decision-based adversarial attacks: Reliable attacks against black-box machine learning models. urXiv preprint urXiv: 2017.
Jacob Buckman, Aurko Roy, Colin Raffel, and Ian Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. 2018. URL https: http://ennreeee.eeeteeeeeeeeeeee S18Su--Cr CW.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium Security and Privacy (SP), pp. 39-57. IEEE, 2017.
Jianbo Chen and Michael I Jordan. Boundary attack++: Query-efficient decision-based adversarial attack. arXiv preprint arXiv: 1944004404 2019.
Jeremy M Cohen, Elan Rosenfeld, and J Zico Kolter. Certified adversarial robustness via randomized smoothing. arXiv preprint arXiv: /902. 029/8, 2019.
Thomas Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithums MIT press, 2009.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scall scale hierarchical image database, In 2009 IEEE conference on computer vision and pattern recognition, pp. 245-255. Icee, 2009.
Guneet S. Dhillon, Kamyar Azizzadenesheli, Jeremy D. Bernstein, Jean Kossaifi, Aran Khanna, Zachary C. Lipton, and Animashree Anandkumar. Stochastic activation pruning for robust adversarial defense. In International Conference on Learning Representations, 2018. URL https:// pettps:/cpperreviee net http:/orrmmmi//mm (o

---

Published as a conference paper at ICLR 2020
Yinpeng Dong, Fangzhou Liao, Tianyu Pang, Hang Su, Jun Zhu, Xiaolin Hu, and Jianguo Li. Boosting adversarial attacks with momentum. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 9185-9193, 2018.
Rodney Douglas and Kevan AC Martin. Neuronal circuits of the neocortex. Annu. Rev. Neurosci. 27:419-451, 2004.
Rodney Douglas, Kevan AC Martin, and David Whitteridge. canonical microcircuit for neocortex. Neural computation, 1(4):480-488) 1989.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-paramettrized neural networks. arXiv preprint arXiv:1810.02054, 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples, arXiv preprint arXiv:1412.6572, 2014.
Stephen Grossberg. Contour enhancement, short term memory, and constancies in reverberating neural networks. In Studies of mind and brain, pp. 332-378. Springer, 1982.
Chuan Guo, Mayank Rana, Moustapha Cisse, and Laurens van der Maaten. Countering adversarial images using input transformations. In International Conference Learning Representations, 2018. URL https::////........ http::::////eereeee.eeeee.ee net/ wwwp:orumtoouueeoooo d-s.uummnd.ySSCC..
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. In International Conference on Learning Representations, 2019. URL https:: wpwpreveeeeeeeeeeeeeeeeeeeeeeeee net/ forum? id=:idd iitrummmdddttu2tccgyym
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Ruitong Huang, Bing Xu, Dale Schuurmans, and Csaba Szepesvári. Learning with a strong adversary. http://aazii.orggaa////11..13
11 2015.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning at scale. arXiv preprint a61 1.01236, 2016.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in Neural Information Processing Systems, pp. 8157-8166. 2018.
Ji Lin, Chuang Gan, and Song Han. Defensive quantization: When efficiency meets robustness. In International Conference on Learning Representations, 2019. URL fett/forum? d=yytt220ctx
Xingjun Ma, Bo Li, Yisen Wang, Sarah M. Erfani, Sudanthi Wijewickrema, Grant Schoenebeck, Michael E. Houle, Dawn Song, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality. In International Conference on Learning Represenaaions, 2018. URL
https: http::///peeeeeeeeeeee / wtt.://wwwwweeeeeeuueu.u.. dtrrummdddBgg112255
Wolfgang Maass. On the computational power of winner-take-all. Neural computation, 12(11):
2519-2535, 2000a.
Wolfgang Maass. Neural computation with winner-take-all the only nonlinear operation. In Advances in neural information processing systems, pp. 293-299, 2000b.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: 1706:0606600, 2017.
10

---

Published as a conference paper at ICLR 2020
E Majani, Ruth Erlanson, and Yaser S Abu-Mostafa. On the k- winners-takee network. In Advances in neural information processing systems, pp. 634 634-642, 1989.
Michael McCloskey and Neal J Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pp. 109-165. Elsevier, 1989.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. the number of linear regions of deep neural networks. In Advances in neural information processing systems, pp. 2924-2932 2014.
Seyed-Mohsen
Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2574-2582. 2016.
Nina Narodytska and Shiva Prasad Kasiviswanathan. Simple black-box adversarial perturbations for deep networks. arXiv preprint arXiv:1612.06299, 2016.
Nicolas Papernot, Patrick McDaniel, Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communicationns security, pp. 506-519, ACM, 2017.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein. On the expressive power deep neural networks. In Proceedings of the 34th International Conference on Volume 70, pp. 2847-2854. JMLR. org. 2017.
Machine
Jonas Rauber, Wieland Brendel, and Matthias Bethge. Foolbox: python toolbox to benchmark the robustness of machine learning models. arXiv preprint arXiv:1707.04133 2017. URL
http: //axivv/rrivv../// org/
wtg/abs/////ooooo..re/....ae.aar abs 1077 04133..
Maximilian Riesenhuber and Tomaso Poggio. Hicrarchical models of object recognition in cortex.
Nature neuroscience, 2(1 10119 1999.
Andrew Slavin Ross and Finale Doshi Velez. Improving the adversarial robustness and interpretability of deep neural networks by regularizing their input gradients. CoRR, abs/1711.09404, 2017. URL
http: //tp///axvvvvv///a///////ee///ia org/ abs / 1711.09404.
Pouya Samangouci, Maya Kabkab, and Rama Chellappa. Defense-GAN: Protecting classifiers against adversarial attacks using generative models. In International Conference Learning Representations, 2018. URL https: http::/://////eeieeeeeee wtw.:/wreeeeeeeeeeeee.
forum httr://ooumiiddBBJ3333 Bkd-kk33bbbb----
Ali Shafahi, W. Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? In International Conference on Learning Representations, 2019a. URL
.ne/ o
forum?1d=r11Wook.
Ali Shafahi, Mahyar Najibi, Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! arXiv preprint 1904 12843, 2019b.
Mahmood Sharif, Sruti Bhagavatula, Lujo Bauer, and Michael K. Reiter. Accessorize to crime: Real and stealthy attacks on state-of-the-art face recognition. Proceedings of the 2016 ACM Computer and Communicattions Security, CCS 16. pp. 1528-1540 1540, New York, NY, USA, 2016. ACM. ISBN 978- 4499994-----44994 doi: 10.1145/2976749 2978399. URL http:// / /oi. acm, www//0..////.o..o.. / 297.7449..9999999 2978392.
SIGSAC Conference
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition, arXiv preprint arXiv:1409.153: 2014.
Yang Song. Taesup Kim, Sebastian Nowozin, Stefano Ermon, and Nate Kushman. Pixeldefend: Leveraging generative models understand and defend against adversarial examples. In Inter- national Conference on Learning Representations, 2018. URL https: http//ppweii.eeeeeeeeee Morru?id=rJuyGa...

---

Published as a conference paper at ICLR 2020
Zhao Song and Xin Yang. Quadratic suffices for weer-parametrization via matrix chernoff bound. arXiv preprint Neti:.1906.03355. 2019.
Rupesh K Srivastava, Jonathan Masci, Sohrob Kazerounian, Faustino Gomez, and Jürgenn Schmidhu- ber. Compete compute. In Advances in Neural Information Processing Systems 26, pp. 23 2318. 2013. URL /ttp://papers nips. hwps.cc/peeteee.. wwtpccccpppppp/aeeee 5059 compete ceappte--o-comeee to-cooopteeee.. pdf.
Rupesh Kumar Srivastava, Jonathan Masci, Faustino Gomez, and Jürgen Schmidhuber. Understanding locally competitive networks. arXiv preprint arXiv: 1410. 165, 2014.
Dong Su, Huan Zhang. Hongge Chen, Jinfeng Yi, Pin-Ya Chen, and Yupeng Gao. Is robustness the cost of accuracy? a comprehensive study on the robustness 18 deep image classification models. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss (eds.), Computer Vision ECCV 2018, pp. 644-661, Cham, 2018a. Springer International Publishing.
Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Pin-Yu Chen, and Yupeng Gao. Is robustness the cost of accuracy?- comprehensive study on the robustness of 18 deep image classification models. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 631-648 2018b.
Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Transactions on Evolutionary Computation, 2019.
Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In International Conference Learning Representations, 2014. URL http: / arxiv. org/ haap/ab///ae
abs/1312 3112. 6199.
Simen Thys, Wiebe Van Ranst, and Toon Goedemé. Fooling automated surveillance cameras: adversarial patches to attack person detection. arXiv preprint 1904. 2019.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint arXi::1705.0722 2017.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be odds with accuracy. stat, 1050:11, 2018.
Tsui- Weii-WWii Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsieh, Duane Boning, Inderjit Dhillon, and Luca Daniel. Towards fast computation of certified robustness for relu networks. 2018.
Przemyslaw Wojtaszezyk. Banach spaces for analysts, volume 25, Cambridge University Press, 1996.
Cihang Xie, Jianyu Wang, Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. In International Conference on Learning Representations, 2018a. URL https: http::///peeeeeeeeeeememeee net fowummidd-kkyyueeee
Cihang Xie, Yuxin Wu, Laurens van der Maaten, Alan Yuille, and Kaiming He. Feature denoising for improving adversarial robustness. arXiv preprint arXiv:1812.034 18/2.03411, 2018b.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 175 2016.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P Xing, Laurent El Ghaoui, and Michael I Jordan. Theoretically principled trade-off between robustness and accuracy. arXiv preprint 1rXiv:1901.08573, 2019.
Stephan Zheng, Yang Song, Thomas Leung, and Ian Goodfellow. Improving the robustness of deep neural networks via stability training. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
12

---

Published as a conference paper at ICLR 2020
Supplementary Document
Enhancing Adversarial Defense by --Winners-Take-l
A OTHER RELATED WORK
In this section, we briefly review the key ideas of attacking neural network models and existing defense methods based on adversarial training.
Attack methods. Recent years have seen adversarial attack studied extensively. The proposed attack methods fall under two general categories, white-box and black-box attacks.
The white-box threat model assumes that the attacker knows the model's structure and parameters fully. This means that the attacker can exploit the model's gradient (with respect to the input) to find adversarial examples. A baseline of such attacks is the Fast Gradient Sign Method (FGSM) (Goodfel- low et al., 2014), which constructs the adversarial example x' of a given labeled data (æ, y) using gradient-based rule:
x' + esign V (f
(3)
where f (x) denotes the neural network model's output, L(-) is the loss function provided f(x) and input label y, and is the perturbation range for the allowed adversarial example.
Extending FGSM, Projected Gradient Descent (PGD) (Kurakin et al., 2016) utilizes local first- order gradient of the network in a multi-step fashion, and is considered the "strongest" first-order adversary (Madry et al., 2017). In each step PGD, the adversarial example is updated by a FGSM rule, namely,
2 = IIwes x¹, + esign( V (f((' v)),
(4)
where x' is the adversarial examples after n steps and a A, (z/,) projects x', back into an allowed perturbation range A. (such as an ball of x under certain distance measure). Other attacks include Deepfool
et al., 2016), C&W (Carlini & Wagner, 2017) and momentum based attack (Dong et al., 2018). Those methods are all using first-order gradient information to construct adversarial samples.
The black-box threat model is a strict subset of the white-boo box threat model. It assumes that the attacker has information about the model's architecture parameters. Some black-box attack model allows the attacker to query the victim neural network to gather (or reverse-engineer) information. By far the most successful black-box attack is transfer attack (Papernot al., 2017: Tramèr et al., 2017). The idea is to first construct adversarial examples on an adversarially trained network and then attack the black-box network model use these samples. There also exist some gradient-free black-bo attack methods, such as boundary attack (Brendel et al., 2017; Chen & Jordan, 2019), one-pixel attack (Su et al., 2019) and local search attack (Narodytska & Kasiviswanathan, 2016). Those methods rely on repeatedly evaluating the model and are not as effective as gradient-based white-box attacks.
Adversarial training. Adversarial training (Goodfellow et al., 2014; Madry et al., 2017; Kurakin al., 2016; Huang et al., 2015) is by far the most successful method against adversarial attacks. It trains the network model with adversarial images generated during the training time. Madry al. (2017) showed that adversarial training in essence solves the following min-max optimization problem:
min
EE max L(f(x'),)), xt E'EA.
(5)
where A, the set of allowed perturbations of training samples, and y denotes the true label of each training sample. Recent works that achieve sfte--of-the-rtt adversarial robustness rely on adversarial training (Zhang et al., 2019; Xie et al., 2018b). However, adversarial training is notoriously slow because it requires finding adversarial samples on-the-fly at each training epoch. Its prohibitive cost makes adversarial training difficult to scale to large datasets such as ImageNet (Deng et al., 2009) unless enormous computation resources are available. Recently, Shafahi et al. (2019b) revise the adversarial training algorithm to make it has similar training time as regular training, while keep the standard and robust accuracy comparable standard adversarial training.
13

---

Published as a conference paper at ICLR 2020
Regularization. Another type of defense is based regularizing the neural network, and many works of this type are combined with adversarial training. For example, feature denoising (Xie et al., 2018b) adds several denoise blocks to the network structure and trains the network with adversarial training. Zhang et al. (Zhang et al., 2019) explicitly added a regularization term to balance the trade-off between standard accuracy and robustness, obtaining state-of-the-art robust accuracy CIFAR.
Some other regularization- methods require no adversarial training. For example, Ross Doshi- Velez. (2017) proposed to regularize the gradient of the model with respect to its input; Zheng et al. (2016) generated adversarial samples by adding random Gaussian noise to input data. However, these methods are shown to be brittle under stronger iterative gradient-based attacks such PGD (Zhang et al., 2019). In contrast, as demonstrated in our experiments, our method without using adversarial training is able to greatly improve robustness under PGD and other attacks.
B DISCONTINUITY JUMP OF Wox(2)
Consider a gradual and smooth change of the vector æ. For the ease of illustration, us assume all the values in æ are distinct. Because every element in æ changes smoothly, when the activation pattern A(x) changes, the k-th largest and + 1-th largest value æ must swap: the previously k-th largest value is removed from the activation pattern, while the previously k + 1-th largest value added in the activation pattern. Let and j denote the indices of the two values, that is, x; is previously the k-th largest and 2; is previously the h + 1-th largest. When this swap happens, 2; and ty must be infinitesimally close to each other, and we use x to indicate their common value.
This swap affects the computation of Wox(2) Before the swap happens, 2; is in the activation pattern but 2; is not, therefore W; takes effect but W, does not. After the swap, W, takes effect while W, suppressed. Therefore, the discontinuity jump due to this swap is (W, W,)x*.
When W is determined, the magnitude of the jump depends x². Recall that x is the k-th largest value in æ when the swap happens. Thus, it depends on and in turn the sparsity ratio yy: the smaller the y is, the smaller & is effectively used (for fixed vector length). As result, the k-th largest value becomes larger-when l = 1, the largest value of æ is used as x².
C THEORETICAL PROOFS
In this section, we will prove Theorem I and Theorem 2. The formal version of the two theorems are Theorem and Theorem 10 respectively.
Notation. We use [n]] to denote the set (1,2....,,n) We use 1( indicate an indicator variable. If the event & happens, the value of 1(E) is 1. Otherwise the value of (E)) is O. For a weight matrix W. we use W, to denote the i-th row of W. For bias vector b, we use d, to denote the i-th entry of b. In this section, show neural network fxx with k-WTA activation function can be seen as the following:
n).
behaviors of the k-WTA activation function. Recall that n-layer
((x) = W() &u (2 db - du (w (w(1) x + b()))) + (()) + (()
where (ii) is the weight matrix, (60) is the bias vector of the i-th layer, and o(-) is the k-WTA activation function, i.c., for an arbitrary vector y. dx(v) is defined as the following:
2 (v), = U/ y is one of the top-k largest values, O, otherwise.
For simplicity of the notation, if i is clear in the context, will just use o(y) for short. Notice that if there is a tie in the above definition, we assume the entry with smaller index has larger value. For vector y E IR! we define the activation pattern A(y) C [4] as
A(v) = (i E [1] is one of the top-k largest values).
Notice that if the activation pattern A(y) is different from A(3/), then Wyy) and W ógy') will be in different linear region. Actually, W o(v) may represent discontinuous function. In the next section, we will show that when the network is much wider, the function may be more discontinuous with respect to the input.
14

---

Published as a conference paper at ICLR 2020
C.I DISCONTINUITY WITH RESPECT TO THE INPUT
We only consider the activation pattern of the output of one layer. We consider the behavior of the network after the initialization of the weight matrix and the bias vector. By initialization, the entries of the weight matrix W are i.i.d random Gaussian variables, and the bias vector is zero. We can show that if the weight matrix sufficiently wide, then for any vector x. with high probability, for all vector x' satisfying that the "perpendicular" distance between x and x' is larger than small threshold, the activation patterns of Wz x and Wx' are different.
Notice that the scaling of W does not change the activation pattern of Wæ for any x, we can thus assume that each entry of W is a random variable with standard Gaussian distribution (0, 1).
Before we prove Theorem 9, let us prove several useful lemmas. The following several lemmas does not depend on the randomness of the weight matrix.
Lemma (Inputs with the same activation pattern form a convex set), Given an arbitrary weight matrix W E R..xm and an arbitrary bias vector b E R for any E R"" the set of all the vectors r' E R satisfying A(Wx' x' + b) = A(Wx + b) convex, i.e. the set {x' E Rmm A(Wx + b) = A(Wx' + b)}
convex.
Proof. If A(Wx' + b) = + b), then x' should satisfy:
Vi E A(Wx b), E |1] \. A(Wx x + b), Wir' + b; 2 (or >) Wjr' + bj.
Notice that the inequality Wix' + b, (or >) Waa' + b, denotes half hyperplane (W; Wz)a'' + (b. - b,, 2 (or >) O. Thus, the set {a' E R A(Wx + b) = A(WI' + b)} is convex since it is an intersection of half hyperplanes.
Lemma 2 (Different patterns of input points with small angle imply different patterns of input points
with large angle). Let a E (0, 1). Given an arbitrary weight matrix W e RRixm, bias vector 0,
and vector x R. with || 22 = 1, if every vector x' E I with ||x'|22 1 and (z. xx)
satisfies A(W x + 6) + A(W x' + b). then for any x" E 1 with || Il2 = and (z, x") < a, it
satisfies A(Wa b) # A(W x" b).
Proof. We draw line between x and x". There must be point x" E R on the line and (x,x") = where x' =====x/ll "xx/||>>'| 1|2=" Since b = O, we have A(Wx" x'' +b) = +'x+++b) + A(Wx+b). Since x" is
on the line between and we have A(W x" +b) + A(Wx +b) b) by convexity (see Lemma 1). 0
Lemma 3 (A sufficient condition for different patterns). Consider two vectors E RC and y E IR.. 1f E A(y), E (4) \ A(y) such that v V/y then Aly) # A(y').
Proof. Suppose A(v) = A(y"). We have i E A(v'). It means that vf is one of the top-k largest values among all entries of y'. Thus v/y is also one of the top-k largest values, and should be in A(y') which leads to contradiction.
In the remaining parts, we will assume that each entry of the weight matrix W e p is a standard random Gaussian variable.
Lemma 4 (Upper bound of the entires of W). Consider a matrix W E x where each entry is a random variable with standard Gaussian distribution NO, 1). With probability at least 0.99, Vi [.]
||Wall2 S ml
Proof. Consider a fixed é E [7]. We have B[[[ = m. By Markov's inequality, we have Pr[][W > 100ml] I 0.01/l. By taking union bound over all E [1], with probability at least 0.99, we have Vi I|Wila < 10
Lemma (Two vectors may have different activation patterns with good probability). Consider matrix W E BRixm where each entry is random variable with standard Gaussian distribution N 1). Let 7 E (0, 0.48) be the sparsity ratio of the activation, i.e., 7 = k/l. For any two vectors I, Rm with || || l|2 1 and (z. x²) a for some arbitrary
(0.5, 1), with probability
at least 1 1--0((1//))) - 1))) A(Wx) + A(Wx') and 3i E A(Wx).. E [1] \ A(Wx)) x)) such that
VI V2
WiX' < Ws
2
24a
15

---

Published as a conference paper at ICLR 2020
Proof. Consider arbitrary two vectors x' R with ||>|| ||~||| 1 and (x.z') a. We can find an orthogonal matrix Q E Rmxm such that ï' = Q2 = 01,0,0 00) E F" and H' == Qr' = (a, v1 a², 0, 0, ...... 0) E E.T WI' = Wx'. Thus, we only need to analyze the activation patterns of W and WF' Since Q' an orthogonal matrix and each entry of W is an i.i.d. random variable with standard Gaussian distribution (V 1), W WQ is also a random matrix where each entry is an i..d. random variable with standard Gaussian distribution [(, 1). Let the entries in the first column of W be X1, '", X, and let the entries in the second column of W be Y1, Y2, ... Yi. Then we have
Let W = = Then we have Wi = Wa and
XI
aXi + vI - a
X₂
aX₂ + v1 a2=a2Y2
Wx Wi-
We' = WX
(6)
X,
ax, + VI VI- Y
We set /1 aa2/(9a) and define R
< R1 < R < R22 as follows:
Pr
X 2 R2 = (1 22y7,
10,(1..1
Pr
X > R2] = (1 - s)7;
(8)
X=N(0.1)
Pr
X R1] = (1 + =)7;
(9)
X0
Pr
X> Rj = (1+ + 2z)y.
(10)
X0N(0,1)
Since 7 0.48 and E S 0.02, we have (1 2c)7 < 0.5. It implies 0 < R R1 R2 R22-
Claim 3.
R² - R S 8
Proof. By Equation (7) and Equation (10).
Pr XoN(0.1)
[R] S S R21 = 45y
Due to the density function of standard Gaussian distribution, we have
1
RG
P P/2dt
Pr X~N(0.1)
RR S X S R2]= 45y.
R
Since R2 2 R2 2 0, we have 14 E Ry):
e 8 12 > e
-R RR212, /2, Thus,
12)) 1 e n2. -
1
nt 12
R2
ldl <
1
12
22/2 487.
2m
2n
v
2m
m
By the tail bound of Gaussian distribution, we have
Pr XwN(
[X 2 R'g $ c R 12
By combining with Equation (7), we have
1
(1-22)y
(R² R())
22
=
Pr
[X 2 Rgg
R2g - R2))
X-N10011)
2m
< e RR3/2.
1
(R/g Ry)
V2T
< 42y,
which implies
4g
R < 1 28
2T S 8T,
where the last inequality follows from 1 - > 0.5.
16

---

Published as a conference paper at ICLR 2020
Claim 4.
Pr
Σ
1(x; 2 21-
S e 5 11/244
(11)
Na, X
Pr
Σ 2 2/2
Se 1//18
(12)
Xa, X
i=1
Pr
Σ 1 2 X, s
8///8
(13)
X1.Xa.-. X1
Pr X1, Xi
Σ
1 2 x; R) - 07//2
(14)
Proof. For E [1 we have (X 2 R₂) = Pr(x, 2 R₂] = (1 - e)7 by Equation (8). By
Chernoff bound, have
Pr
Σ 1(x,
2 R2) 21+ (1 (1- se (11(9/991--2))111
Since e < 0.02,
Pr
1(x; 2 R2) 2 (1 - E/-1/
S <1-6211/24
We have E[1(X, 2 R1) = Pr[X; 2 R1 = (1 + 5)y by Equation (9). By Chernoff bound, we have
1(x, 2 R1) 5 (L-E/3) (1 (1+tml < ((166/))444)))11
Pr
Thus,
I
Pr
Σ
1(x 2 Rb) (1++//21)
S 5
i=1
We have [R, > X, 2 R2)] = Pr 2 x Aa] = Ey by Equation (7) and Equation (8). By
Chernoff bound, we have
Pr
Σ
I(R' 2 X; > R2) < 1/2 198 -071//
Similarly, have (R x RD] Pr(R > X, R2] 87 by Equation (9) and Equation (10). By chernoff bound, we have
Pr X1. XI
Σ I(R1
2 X,
2
R1 < 1/2 End
Equation (11) says that, with high probability, Vi E [[] with X, 2 R2, has i A(Wx). Equa- tion (12) says that, with high probability, Vi [1] with X; S R1, it has i ((W.). Equation (14) (Equation (13)) says that, with high probability, there are many E [1] such that Wa E [R Ri (W,xr [Rg, [.).
Let a = & A & A E3 A Ea, where
E: E 1(x; > R₂) < (1 - e1-//2)
& Ele 1(X; > R1) (1+1/2)/l
17

---

Published as a conference paper at ICLR 2020
Es: Σ 1 R2) 2 e21/2,
E.: E 1 X; R2) 2 s21/2.
According to Equation (11), Equation (12), Equation (13) and Equation (14), the probability that & happens at least
1 4e 52/
(15)
by union bound over & 2. E3: E4.
Claim 5. Condition on E, the probability that 3i E
[1] with X, E [R2, Ri] such that Y; <
-a/v v1 - a² 16e is at least
(168
a
1 2
2x1/2
166
+
vI
a²
Proof. For a fixed E [1]
0
Pr Y, -a/v V a² 16 2
- 12 +
-a/Vi caa/ii-a* 16cv 27 VTT
1
1
a/
a²
166 +
V2T
a
1
16e
v1
a² 2
Thus, according to event E we have
ex//2
Pr Vi with X, [R2, Ki -a/V1-a
- 2 El s
16E
+
1
v1 - a
2
Claim 6. Condition on E, the probability that 3i E [1] with X, E [R Ri] such that Y; 2 0 is at
least 1 (1/2)en1/2
Proof. For a fixed i [4. Pr|Y, 0] 1/2. Thus, according to event Eg, we have Pr PV with X; E [R, R.), 2 S (1/2)e11/2
Condition that & happens. Because of E1, if X; > R2, X; must be of the top-k largest values. Due to Equation (6), we have X; = W.r. Thus, if X, 2 R2, E A(Wx). By Claim 5, with probability least
1 2x//2
1-(16e
1-
168
+
(16)
V1 - a
2
there is i E A(Wx)) such that
Wa = aX; + / a2%
<ax; + v1 - a² (-
v1 (-V1-- a²
a
168
2m
= a(X; 165 2
S (R'2 16: / 2TT
(17)
where the first step follows from Equation (6), the second step follows from Y, 5 168 12n, and the last step follows from X; [R2, Ry)
-a/vi---a= az
18

---

Published as a conference paper at ICLR 2020
Because of Eg if X, I R1. X, should not be one of the top-k largest values. Due to Equation (6), we have X, = aa. Thus, if X5 I R1, j & A(wx). By Claim C.I, with probability at least
1 (1/2)011/2,
(18)
there j j & A(Wx) such that
Wjz' = ax, + - a2y, 2 aXj 2 2Rl',
(19)
where the first step follows from Equation (6), the second step follows from Y 2 0, and the last step follows from X, E [ Ri].
By Equation (19) and Equation (17), 3i E A(Wz). [4] \ A(Wx).
W S aR222 - 165v 2x) S a ( - 85V S W 8TE
s W - 2 W W V1- a² V
24a
where the second step follows from Claim 3, the forth step follows from 2 0.5, and the last step follows from v1 - a²² (96a). By Lemma 3, we can conclude A(Wa) x))= o A(Ww'') By Equation (15), Equation (16), Equation (18), and union bound, the overall probability is at least
1 1
4e -//22
+
16E
+ 1 2)
67//2
+
(
5x1/2
vI
--aa
az
2
4e 22/22
2
e///2
1
5x//2
2 1
+
2
6771/24
2 11-6 6
2 1 1 2 (( -1).t)
where the first and the last step follows from E == =-1 a22//29))))
Next, we will use tool called c-net.
Definition 7 (e-Net). For a given set S. if there is a set N C S such that Væ E S there exists vector y E N such that || yll2 S e. then N is an e-net of S.
There is a standard upper bound of the size of an e-net of a unit norm ball.
Lemma 6 (Wojtaszezyk (1996) II.,, 10). Given matrix U E Rx let S = (Uy ||ub|2 1). For & E (0, 1), there is an g-net N of with [W| S (1 + 1/e)a.
Now can extend above lemma to the following.
Lemma (s-Net for the set of points with a certain angle). Given a vector x E IR' with | = 1
and parameter E (-1, 1). let S fx'e E R" ||'l|| 1, (x, a). For 1), there is an E-net N of S with W s (1 + 1/e)m-1.
Proof. Let U E Rmxx (m-1) have orthonormal columns and Ur = 0. Then S can be represented as S= (a x + v a² Uy y E m-1 y1uyll2 = 1).
Let
s' = (Uy y 1 |U = =1}.
According to Lemma 6, there is an e-net N' of S' with size 1 < (1 + 1/2)m We construct. ' following:
N = fa. /1 a² N2)
It is obvious that W = [' < (1 + 1/2)m-1. Next, we will show that N is indeed an E-net of S.
Let x' be an arbitrary vector from S, Let a- vI - a² for some E S', There is vector (a v1 - az z²) E N such that z' N and ||= ='112 < Thus, we have
|| - (a . + V1 a² z')l22 = /1 - a² | - z' 1|2 S.
19

---

Published as a conference paper at ICLR 2020
Theorem 8 (Rotating vector little bit may change the activation pattern). Consider weight matrix
W E R'xm where each entry is an i.i.d. sample drawn from the Gaussian distribution N 1/t). Let Y (0, 0.48 be the sparsity ratio of the activation function, i.e., k/l. With probability at least 0.99, it has Vi E [], [|Wll & 10 Condition on that Vi E [ 1|Wlll2 I 10y/m happens, then, for any In and (0.5, 1), if
m + log(1/0)
m + 1og(0101/)))
12C.
log
7
a²
for sufficiently large constant C, with probability at least 1 1-22- Va E R. with (x,2') A(Wa) x) * A'(Wx').
<< S a
Proof. Notice that the scale of W does not affect the activation pattem of W z for any E R Thus, we assume that each entry of W a standard Gaussian random variable in the remaining proof, and we will instead condition on Vi E !1, ||W;ll2 1l The scale of x or x' will not affect (a,² will not affect the activation pattern either. Thus, we assume ||0:||2 = ||>| 2|2 =
By Lemma 4, with probability at least 0.99, we have Vi E [1] W - 10
Let
S = {y E R
llvll2
1, (z, a}.
Set
V 2 az)
=
720a
By Lemma 7, there is an N of S such that
m
720 ml
M s (1
2 a())
By Lemma 5, for any E NN, with probability at least
1 (11/a2
Bi e A(Wx).j e 14]
A(Wx) such that
V1-a²
wy < WGy
2m.
24a
By taking union bound over all y E N, with probability at least
W 2 0((1/a2-1/3)
720a ml
2 0( (0-2--110)
+
2T a²)
ml
2 ( -1)d)
1000
V1
ml
m
2 C² (1t--11)7
m+lor(1/6) - log( mm)))
N
1000
11 O' is sufficiently large constant
VI
ml
m
(mm+log(1/8)))-ogg ml
1000
2
VI
8
the following event 8' happens: Vy E A(Wx), E [4] A(Wx) such that
V1-a²
Way < WTy
V2T.
24x
20

---

Published as a conference paper at ICLR 2020
In the remaining of the proof, will condition on the event Ex. Consider y E S. Since N is an E-net of S, we can always find a E N such that
lll u--yl v'll2 = (2T aa)
720uv
Since event E" happens, we can find i E A()x) and j E [4] A((xx) such that
V1 11-a² x² 22.
Way < Wsy
24a
Then, we have
Wsy Way + Wily'' y)
1-a²
22 + WWllllly v112
24a
V1 o²
2 a²)
S W
22 1l
24a
720 ml
V1 a
Wyy 360
2
a²
Wiy' W 1/)
2T
36a
v1 - a²
S Wsy' + IW, 12lly
~/112
2/2x
36a
127
a²))
vI a²
S W3y' + 100ml
V22T 2T
720av
36a
v1
wW
V2T,,
72a
where the second step follows from Wy < WGy - VI a² /24a) V2n and Wi(y'
v) < [Wall2lly ylla. the third step follows from |Will2 I 10v ml and Il vlla I
(1 - /00-a=))(2000 (720ayml), the sixth step follows from Wy - 1/) < |[, lelly v'll2, and the seventh step follows from |[Willa I 10 and - -llla- 2 a²) (720a/ ml).
By Lemma 3, we know that A(Wx) F A(Wy') Thus, Vy E Rn with llv' = 1 and (x, y²) = we have A(Wx) x) + A(Wa)) conditioned on E'. By Lemma 2, we can conclude that Va' E Rd with | = 1 and (x,xx) S. a, we have A(Wx) + A(Wx') conditioned on E'.
O
Theorem (A formal version of Theorem 1). Consider a weight matrix W E R..m where each entry is an i.idd sample drawn from the Gaussian distribution ((0, 1/1). Let Let (0, 0.48) be
the sparsity ratio of the activation function, i.e., = k/L. With probability at least 0.99, it has
vi E [1] ||Wall2 I 10 Condition on that Vi E [4], [Wal22 S 10ym happens, then, for any
E Rm
1 120 C. (m- ( log(1/8) (
1 log m m log(1/8) 1
7
3
for some 3 E (0,1) 1) and a sufficiently large constant C, with probability at least 2m Vrr' E Rmm with || ||= 2 8, A(Wx) + A(Wx'), where x' = = (x + Ar) for some scaler and Ar is perpendicular to x.
Proof. If (I, x') < O, then the statement follows from Theorem 8 directly. In the following, we consider the case (ar, x²) > O. If || | 2 3,
(x,, x²)²
> 12 1
2
|
Am 13
2
+
Az
1
1
1x 12 +
3
|<<1
1+1 8
21

---

Published as a conference paper at ICLR 2020
Thus, we have the bounds:
1 3
0
(
(.. | | =1
By Theorem 8, we conclude the proof.
Example 1. Suppose that the training data contains N points 21,22,"' .N E R (m 2 Olog N)), where each entry of x4 for E [N] is an i.i.d. Bernoulii random variable, i.e., each entry is with some probability p E (100 lo/ 0.5) and otherwise. Consider a weight matrix W E R where each entry an ii.dd sample drawn from the Gaussian distribution ((0 1/1). Let E (0, 0.48) be the sparsity ratio of the activation function,, i..., y = k/L. Ifl 2 Qmm/7 log(m//g))))))) m//1)). then with probubility at least 0.9, Vi,j E [N], the activation pattern of W xs and W x are different,
Le., A(Wx;) # x.))
Proof. Firstly, let bound |041122- inequality, we have
We have [[[[=;11]]
E
F2,1
pm. By Bernstein
Pr
Σ
m pm
Tiet
>
10 Pm
1
S
2e
post 3 pm
(pmm/10) /10)
0.01/N.
Thus, by taking union bound over all E [.V] with probability at least 0.99, vi E [M] v0.9pm < ||>|||a S vI.lpm. Next we consider (z), Notice that [[ +,yر = E E Fiaaz = p²m. There are two cases.
Case 1 (p2m > 20 N). By Bernstein inequality, we have
122m/33//2
Pr [x), - pmm| 50mm S 2e pmmthhrm
-2 =ppm < 0.01/N2.
By taking union bound over all pairs i, j. with prohability at least 0.99, vi j (1) S 3ppm.. Since ||=:||2, ||= 2 /0.9pm, we have
Ty) |
3p²m/2 5
5
0.9pm 3 6*
Case 2 (p2m= < 20 20g N). By Bernstein inequality, we have
(10 N)
Pr x)),, - p² pam > 10 N] < 2e
pm 1 1030x
< 0.01/N2
By taking union bound over all pairs of i, with probability at least 0.99, vi + (z,,0z) 10 log N, Since ||,;||2, ||رح||2 /0.9pm 2 900 log N, we have
(z),
10 N
| la
90 N 9 |zy 112
Thus, with probability at least 0.98, we have Vi + j. (ry) (|cra///llll
5/6. By Theorem 8. with probability at least 0.99, Vi E [2]. [[a S 10.m. Condition on this event, and since vi + j we have (2,,, 2,,, | (12) < 5/6, by Theorem 8 again and union bound over all i [N], with probability at least 0.99, vi & j, A(W xx) + A(Wz;).
C.2 DISJOINTNESS OF ACTIVATION PATTERNS OF DIFFERENT INPUT POINTS
Let X2,X, X2....,.4 Xm be i.i.d. random variables drawn from the standard Gaussian distribution (O, 1). Let = th X?? We use the notation 2 to denote the distribution of Z. If m is clear in the context, we just use x" for short.
Lemma 8 (A property of x² distribution). Let Z be random variable with x2 (m 2 2) distribution. Given arbitrary E, 17 E (0, 1). if R is sufficiently large then
Pr[Z (1 R)/ Pr((1 + 8) 22
22

---

Published as a conference paper at ICLR 2020
Proof. Let R be a sufficiently large number such that:
e 4 R// Rm/2211 R/4 16 с
Let e/4. By the density function of x² distribution, we have
(1+c)R
5 (1+ 2m/2T(mm/2 R
gm/2-1c -t/2
1/2
and
Pr|z 2 (1 + (1+ 2mm2T((m22)
/2/2-1 E -1/2
(1+c)
where r'-) is the Gamma function, and for integer ((m/2) (m/2 11)mm/22 2) ......1 (m/2- 1)! By our choice of R. we have
(1++)R
Pr(R 2 +1+))R 2m/2[(m/2)
e 1/2
1
2 (R-122
R12 - -e -1(
2m/22((m/2)
2 2m/2[(m/22 -2(1 - -) .e -R/2
where the first step follows from vt 2 R, 12221 2 1, and the third step follows from
R/2
e R/2 = 11/2 SE
We also have:
Pr|z 2 (1++)
c (1--)//2
pm/2T(m/2))
(1+))
2
(1))(1)))
2m/2[(m/2)
1 1-
2
1- e (1+2/22)/22
2m/2[(m/2)
where the first step follos from Vt > R, 1m/2-1 - et//2, and the third step follows from (1 E) 2 (1 + e/2). Thus, we have
Pr 2 (1 + R
1
ER/4
<
16 -RR/1 <n.
e 2 R
(1 E)2
g
Lemma 9. Consider I, y, E R". If T
(x-y)
< T E
(2.2)
> B for some a. 2 0, then
||l||||=l|a I a -1- fZ. Furthermore, if 3 2+a
a then
(1 Ea) where |
(w.e)
Ea E (0, 1) only depends on a.
Proof. Without loss of generality, we suppose ||>||2 = ||a/22 = ||=112 = 1. We can decompose y as + yy where y' is perpendicular to x. We can decompose as b1 bay / /lly 12 + z' where z' is perpendicular to both x and y'. Then we have:
(u. 2) ad, bz b2l1 a V1- 32
23

---

Published as a conference paper at ICLR 2020
where the last inequality follows from 0 I bj 1, I a, and by v1- 8f 1 v11 B
0 S 11 ll I 1. By solving B a V1- Be, can get B at 22 a²
Thus, if we set
B a+v2-0 V2-a"
2
should be strictly larger than a + /1- 3e, and the gap only depends on a.
Lemma 10. Give x E R let y E mh be random vector, where each entry of is i.id sample drawn from the standard Gaussian distribution N( 1). Given B E (0.5, 1),
Pr( />/(l==lllllll 2 3) 2 1/11+1//2/11 -)
Proof. Without loss of generality, we can assume ||||| = 1. Let y'= y ///ly/122 Since each entry of is an i..dd Gaussian variable, y/ is random vector drawn uniformly from unit sphere. Notice that if (sr, u²) 2 then |ar 1/1122 /2(1 B). Let C'= (= E IR" ||=||2 1, 1| ||===1|12 $ /2(1 3))
be a cap, and let S = {= E I || = }} be the unit sphere. Then we have
Pr[ 3/) 2 3 arca(C)/arca(())
According to Lemma 6, there is an /2 -net N with [ < (1 (1+1/v2(11)) B)) If we put a cap centered each point N, then the whole unit sphere will covered. Thus, we can conclude
Pr((e, v/) 2 ø 2 1/(1 + + 1/12(11 3)
Theorem 10 (A formal version of Theorem 2). Consider N data points 21, 02, .N E T and a weight matrix W E IR!xm where each entry of W is an i.i.d. sample drawn the Gaussian distribution (0, 1/t). Suppose Vi + jE E [N], 25)) ss)//(leae /[|==]la|| [23]12)) S a for some a (0.5, 1). Fix k 2 1 and å E (0, 1), if is sufficiently large, then with probability at least - 6,
Vi,j E AN x:)) 0 A(W x.)) 0.
Proof. Notice that the scale of W and æ 22, ... NN do not affect either (z,, xz)/ ([<=|12||= or the activation pattern. Thus, we can assume || ||| ||l2||2 = || 1 and each entry of W is an i..dd standard Gaussian random variable.
Let 3 2-at and Ea be the same mentioned in Lemma 9, Set and 8 as
7-1 2 8¹ = (1=11)))8
E =
Now, set
6/100
100% log( N/8)) (1+ 21+2/v -3)))
and let R satisfies
Pr |2 (1+ 8/100 ~~x
According to Lemma 8, if is sufficiently large, then R is sufficiently large such that
Pr [Z 2 (1+ Z
Pr [1+ 2 Z 2 R
2 2
Notice that for t E [1, Well is a random variable with x² distribution. Thus, Pr[I[Wel22 2 (1 + R]
7 By taking union bound over all [4] with probability at least 1 8 6/100, Vt E [], |Wall2 < (1 + +).. In the remaining of the proof, we will condition on that Vi E
5/100
[,IlWlll2 S (1+ E... Consider i.j E [N],t E [1], if W.,; > g R. then we have
W
B'R.
2 B (1 + B. (1+e)R
[ell
24

---

Published as a conference paper at ICLR 2020
Due to Lemma 9, we have
W
- <1
|Wil22
Thus,
Way < (w) (.)+ 5o)
(20)
Notice that for i E [N], t E [4], we have
W
Pr[Wa,, > 8' 2 Pr|l|W,l22 2 Pr
[llooll2 2 3
8/100 1
1
" (1+1/v2(1
-
100k log(N/6)-
By Chernoff bound, with probability at least 1 - 6/(10ON),
Σ 1(W,, > 2 k.
By taking union bound over E [N], with probability at least 8/100, E [N],
Σ 1( > 8') 2 k.
This implies that Vi E [f] E A(Wx,)) then Wi R.R. Due Equation (20). vj [N]. we
have Wary < 8 R which implies that & A(Wr,)) Thus, with probability at least 1 6/50 2 - probability, Vi * j. A(Wx,) x.) n A(Wx,)
Remark 1. Consider any 12, JN E I with ||al |122|22 = =.. |IN 1l2 = 1. If
Vi # E [M], (I., a for some (0.5, 1), then N < (1 + 2/ a))
Proof. Since (I,, a, I.; 2 12 + 1 - 2(x,, 2 2 2a. Let S be the unit
sphere, i.e., S = (x E R. ||0||| = 1]. Due to Lemma 6, there (v2(11 - a2) N of S with size at most [ < (1+ 2/ ( Consider Tj, and E N. By triangle inequality, if || v/12 < 2 /2(1-a)/2, then ||= yll /2(1- - a2/2 due to ||:; z, || 2 /2(1 a).
Since N is a net S, for each 24, we can find a y E A such that || vll2 /2 a2/2. Thus, we can conclude N s a)))m
Theorem 11. Consider N data points Ii, T2, JN E RM with their corresponding labels Z1, 22, ... NN E IR and weight matrix W E fixm where each entry W is an i.i.d. sample drawn from the Gaussian distribution NO, 1/t). Suppose Vi jjE [N], (I,,
l12) S for some a E (0.5, 1). Fix k 2 1 and 8 E (0,1), if is sufficiently large, then with probability at least 1 8, there exists a vector E IR. such that
Vie [N], (v. (Wax)) = 2;.
Proof. Due to Theorem 10, with probability at least 8, Vi # j. A(Wx,, AWW,), = 0. Let 11, .... IN E [1] such that 1; E A(Wx;). Then 4, E A(Wxx;) xx,) for j + i.
For each entry Ve. if to for some i [N], then set 82 (W/,. Then for E [N], we have
(v. (wzz))
Σ
0e Wa2, 2/(W,zz;)) W1, = 24.
BEA(Wo.)
25

---

Published as a conference paper at ICLR 2020
D ADDITIONAL EXPERIMENTAL RESULTS
This section presents details of our experiment settings and additional results for evaluating and empirically understanding the robustness of k- t-WTA networks.
D.1 EXPERIMENT SETTINGS
First, we describe the details of setting up the experiments described in Sec. 4. To compare k- 6-WTA networks with their ReLU counterparts, we replace all ReLU activations in a network with k-WTA activation, while retaining all other modules (such as BatchNorm, Convolution, and pooling). To test on different network architectures, including ResNet18, DenseNet121, and Wide ResNet, we use the standard implementations that are publicly available'. All experiments are conducted using PyTorch framework.
Training setups. We follow the same training procedure on CIFAR-IO and SVHN datasets. All the ReLU networks are trained with stochastic gradient descent (SGD) method with momentum=0.9. We use a learning rate 0.1 from the first to 50-th epoch and 0.01 from 50-th to 80-th epoch. To compare with ReLU networks, the k-W networks are trained in the same way as ReLU networks. All networks are trained with a batch size of 256.
For k-WTA networks with a sparsity ratio 7 = 0.1, when adversarial training is not used, we train them incrementally (recall in Sec. 2.2). starting with 7 0.2 for 50 epochs with SGD (using learning rate=0.1, momentum=0.9) and then decreasing 7 by 0.005 every 2 epochs until y reaches 0.1.
When adversarial training is enabled, we use untargeted PGD attack with 8 iterations construct ad- versarial examples. To train networks with TRADES (Zhang et al.. 2019), we use the implementation of its original paper* with the parameter 1/A 6, value that reportedly leads the best robustness according to the paper. To train networks with the free adversarial training method (Shafahi et al., 2019b), we implement the training algorithm by following the original paper. We set the parameter 8 as suggested in the paper.
Attack setups. All attacks evaluated under the foo metric, with perturbation size 0.031 (CIFAR-10) and 0.047 (SVHN) for pixels ranging in [0, 1]. We use Foolbox (Rauber et al., 2017). third-party toolbox for evaluating adversarial robustness.
We use the following setups for generating adversarial examples in various attack methods: For PGD attack, we use 40 iterations with random start, the step size is 0.003. For C&W attack, we set the binary search step to 5, maximum number of iterations to 20, learning rate to 0.01, and initial constant to 0.01, For Deepfool, we use 20 steps and 10 sub-samples in its configuration. For momentum attack, we set the step size to 0.003 and number of iterations to 20. All other parameters are set by Foolbox to be its default values.
D.2 EFFICACY OF INCREMENTAL TRAINING
We now report additional experiments to demonstrate the efficacy of the incremental fine-tuning method (described in Sec. 2.2). As shown in Figure 6 and described its caption, models trained with incremental fine-tuning (denoted as w/ FT in the plots' legend) performs better in terms of both standard accuracy (denoted as std the plots' legend) and robust accuracy (denoted as Rob in the plots) when the WTAA sparsity < 0.2, suggesting that fine-tuning is worthwhile when is small.
D.3 ADDITIONAL RESULTS ON CIFAR-10
Tests on different network architectures. We evaluate the robustness of k- 4TA on different network architectures, including 18, DenseNet-121 and WideResNet-22-100 10. The results are reported in Table 2, where similar to the notation used Table I of the main text, Arab calculated as the worst-case robustness, i.e., under the most effective attack among PGD, C&W, Deepfool and MIM. The training and attacking settings are same as other experiments described Sec. D.I.
As shown in Table 2, while the standard and robustness accuracies, Asta and Arab, vary on different network architectures, k- (TA networks consistently improves the worst-case robustness Arab over ReLU networks, no matter what the network architecture and training method are used.
26

---

Published as a conference paper at ICLR 2020
ResNet18
Wide ResNet
0.8
Accuracy
Accuracy
0.6
0.6
Std
0.4
0.4
Rob
Rob FT
0.21
0.0
0.0
0.20
0.15
0.10 Sparsity ?
0.05
0.10 Sparsity y
0.05
Efficacy of incremental training. We sweep through a range of sparsity ratios, and evaluate the standard and robust accuracies of two network structures (left: ResNet18 and right: Wide ResNet). We compare the performance differences between the regular training (i.e., training without incremental fine-tuning) and the training with incremental fine-tuning.
Figure 6:
Table 2: Additional CIFAR-10 10 results.
Training
Model
Activation
Autd
Ayob
ReLU
92.9%
0.0%
LWTA-0.1
82.8%
3.7%
Natural
ResNet-18
LWTA-0.2
84.6%
0.9%
k-WTA-0.1
89.3%
13.1% %
k-WTA-0.2
91.7%
4.2%
ReLU
83.5%
43.6%
LWTA-0.1
71.4%
46.6%
AT
ResNet-18
LWTA-0.2
78.7%
43.1%
k-WTA-0.1
78.9%
50.7% %
k-WTA-0.2
81.4%
47.4%
ReLU
93.6%
0.0%
LWTA-0.1
86.1%
4.6%
Natural
DenseNet- 121
LWTA-0.2
88.5%
1.4%
3-WTA-0.1
90.5%
12.3%
k-WTA-0.2
93.3%
6.2%
ReLU
84.2%
46.3%
LWTA-0.1
74.0%
49.1%
AT
DenseNet-122 121
LWTA-0.2
80.2%
44.9%
k-WTA-0.1
81.6%
52.4%
k- A-WTA-022
83.4%
49.6%
ReLU
93.4%
0.0%
LWTA-0.1
83.7%
4.2%
Natural
WideResNet-22-10
LWTA-0.2
86.1%
2.8%
k-WTA-0.1
88.6%
18.3%
k- WTA-0.2
92.7%
7.4%
ReLU
83.3%
43.1%
L
74.2%
47.5%
AT
21deRessNet22-110
L.TA-0.2
79.8%
44.7%
k- -TA-0.11
78.9%
50.4% %
k- WTA-0.2
82.4%
47.1%
Comparison with LWTA. We addition compare k: WTA to LWTA activation (Srivastava et al., 2013; 2014). For fair comparisons, we use the same sparsity ratio in both k-WTA and I.TAA. As shown Table on all network architectures and training methods we tested, k-WTA networks con- sistently have better robustness performance than LWTA networks (in terms of both Astd and Arob). These results suggest that WTA more suitable then LWTA for defending against adversarial attacks.
Transfer attack. Since a l- WTA network is architecturally similar to its ReLU counterpart counterpart-wwit with the only difference being the activation- evaluate their robustness under (black-box) transfer
27

---

Published as a conference paper at ICLR 2020
Table 3: Transferability test CIFAR-IO.
Source Model
Target Model
ReLU
k-WTA-0.1
ReLU (AT)
E-WTA-0.1 (AT)
ReLU
4.8%
75.5%
59,4%
84.7%
k-WTA-0.1
61.2%
71.2%
67.8%
86.4%
ReLU (AT)
62.7%
80.9%
61.6%
78.6%
k-WTA-0.1 (AT)
79.2%
78.6%
69.2%
67.2%
Table 4:
White-box attack results on MNIST dataset.
Activation
Training
Astd
Arob
Activation
Training
Astd
Arob
Natural
99.4%
0.0%
Natural
99.3%
62.2 %
AT
99.2%
95.0%
AT
99.2%
96.4 %
ReLU
k-WTA-0.1
TRADES
99.2%
96.0%
TRADES
99.0%
96.9%
FAT 98.2%
94.7%
FAT 98.1%
96.0% %
attacks across k-WTA and ReLU networks. To this end, we build a ReLU and a k-WTA-0.1 network on ResNet- 18, and train both networks with natural (non-adversarial) training as well as adversarial training. This gives us four different models denoted (in Table 3) as ReLU, k- 1T--0.1. ReLU (AT), and k-WTA-0.1 I (AT). then launch transfer attacks across each pair of models. We also consider by-far the strongest black-box attack (according to Papernot al. (2017)): for the same model, for example, a k- WTA-0.1 network optimized by adversarial training, we train two independent versions, each with different random initialization, and apply the transfer attacks across the two versions.
The results are reported in Table 3, where each row corresponds to a target (attacked) model, and source model from which the adversarial examples generated. On
each column corresponds the diagonal line of Table 3, each entry corresponds to the robustness under aforementioned transfer attacks across the two versions of the same models.
The results suggest that 1) it is more difficult to transfer attack F-WAA networks than ReLU networks using adversarial examples from other models, and 2) is also more difficult to use adversarial examples of &-WTA network to attack other models. In a sense, the adversarial examples of k-WTA network tend to be "disjoint" from the adversarial examples of a ReLU network, despite their architectural similarity. Inspecting the diagonal entries of Table 3, also find that k- networks are more robust than their ReLU counterparts under the strongest black-box attack (Papernot et al., 2017) (i.e., transfer attacks across two different versions of the same model).
D.4 MNIST RESULTS
On MNIST dataset, we conduct experiments with an adversarial perturbation size = for pixels ranging [0, 1]. We use Stochastic Gradient Descent (SGD) with learning rate=0.01 and momen- tum=0.9 to train a 3-layer CNN. The training takes 20 epochs for all the methods we evaluate. The robust accuracy are evaluated under PGD attacks that take 20 iterations with random initialization and step size of 0.03.
The results are summarized in Table Again, k &-W activation consistently improves robustness under all different training methods. Even with natural (non-adversarial) training, the resulting k-WTA network still has 62.2% robust accuracy, significantly outperforming ReLU network.
D.5 ROBUSTNESS WITH RESPECT TO NATURAL PERTURBATIONS
We also evaluate the robustness of k-WTA networks under (nos-adversarial) natural perturbations. We evaluated various types of perturbations, including adding Gaussian noise to the input image (std=0.05/0.1), random translation (maximum 5 pixel), random rotation (maximum 10 degrees) and color jittering (i.e., randomly changing the brightness, contrast and saturation of an image, with maximum perturbation 0.4), following Hendrycks Dietterich (2019). The results are summerized in Table 5, in which all models are ResNet18.
We found that under all the tested perturbations, the accuracy drops in k- WTA networks are no worse than those in ReL.U networks. Note that in these tests, all our models are trained with standard data
28

---

Published as a conference paper at ICLR 2020
Table 5: Robustness under natural perturbations.
Model
Clean
GN(0005)
GN (0.1)
Translation
Rotation
ColorJitter
ReLU
92.9%
69.7%
27.0%
92.3%
88.9%
90.7%
1-WTA-0.1
89.3%
80.2%
50.9%
89.1
86.8%
87.4%
k-WTA-0.2
91.7%
77.9%
39.6%
91.2%
88.9%
89.4%
ReLU (AT)
83.5%
80.3%
73.9%
80.5%
79.8%
74.9%
k-WTA-0.1 (AT)
78.9%
77.8%
69.8%
75.9%
74.7%
68.7%
k-W-A-0.2 (AT)
81.4%
80.6%
70.9%
79.8%
78.6%
74.7%
augmentations (e.g., random crop and random flip); they are not specifically trained to avert the tested perturbations.
We also highlight interesting finding here. Adding Gaussian noise leads to large accuracy drop (e.g., from 92.9% to 69.7%/97..2.. as shown in the table) on naturally trained ReLU network, but in k-WTA networks (especially k- k-WTA-0.1), the corresponding accuracy drop is much smaller (e.g., from 89.3% to 80.2% We conjecture that the dense discontinuities in k- A-WT networks (recall Figure 5) effectively add noise the input distribution, thus making the model more robust against input noise.
D.6 LOsS LANDSCAPE VISUALIZATION
In addition to the experiments shown in Figure and Sec. 4.3 of the main text, we further we visualize the loss landscapes &-WTA networks when different sparsity ratios y are used. The plots are shown in Figure 7, produced in the same way as Figure 5 described in Sec. 4.3.
As analyzed in Sec. 3, a larger tends to smooth the loss surface of the k-WTA network with respect to the input, while smaller y renders the loss surface more discontinuous and "spiky". : In addition, adversarial training tends to reduce the range of the loss values-aa similar phenomenon in ReLU networks has already been reported Madry et al. (2017); Tramèr et al. (2017) that does not mean that the loss surface becomes smoother; the loss surface remains spiky.
29

---

Published as a conference paper at ICLR 2020
Res0et18-0.3
ResNetl 8-0.2
30
25
20
15
0.04
-0.050.02 0.00
0.02
0.02
0.04
0000%
0.00
0.02
0.04
-0.4
0.00
0.02
0.02
ResNetl 8-0.1
DenseNet 12-0.22
25
25
20
15
15
0.04
0.02
-0.04 -0.01..0%
0.00
0.04
0.00
0.00
-0.22
0.07
0.00
0.02
0.02
0.02
0.04
0.00
1
Dense 21-0.
30
10
10
0.04
0.04
0.07
%.00
0.02
0.04 0..07
0.0%%
0.00
0.02
0.02
0.04
-0.04
0.00
0.02
-0.02
Figure 7: Visualization of ResNet18 and DenseNet121 with different values. The last one (DenseNet121-0.1 -+ayv is the result using adversarial training. The others are optimized using natural (non-adversarial) training.
30


Reviews:
[{"review_id": "ryg2N7D7cr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper suggests using the activation function k-Winners-Take-All (k-WTA) in deep neural networks to enhance the performance of adversarial defense. Their experiments show that the robustness is improved when they simply change the activation function to k-WTA. They also give reasonable theoretical analysis for their approach. \n\nI find that the idea is simple and elegant. Since they only change the activation function, their approach can be easily applied to almost all network structures and training processes. Their experiments show that the robust accuracies are significantly improved on all evaluated methods when they use the k-WTA activation function. I also appreciate their theoretical analysis. They show that k-WTA makes the network very discontinuous with respect to the input x, and thus the adversary could not get useful gradient information. In contrast, if the network is wide enough, then the discontinuities with respect to the weights w is sparse. This is why the network is still trainable though itself is not continuous.\n\nThe paper is also well-written and easy to follow. I recommend the acceptance of the paper.\n\nOne limitation of this paper is that their approach mainly focuses on defending gradient based attack. But I agree that the gradient based attack is currently almost the best attack method.\n\nA minor question:\n- How do we choose k in general? What is the behaviour for different k?\n", "extra_scores": {"experience_assessment": "I have published one or two 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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Skgu1ZFjtr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose using k-winner take all (k-WTA) activation functions to prevent white box adversarial attacks. A k-WTA activation functions outputs the k highest activations in a layer while setting all other activations to zero. The reasoning given by the authors is that k-WTA activation functions have many discontinuities with respect to the input space. This makes it more difficult for attacks to use gradient information. The authors note that networks with k-WTA activation functions are still easy to train because, for a given input, the sub-network that is activated becomes more stable as training progresses. Therefore, it is not as discontinuous in the parameter space.\n\nThe authors test their method with 5 different adversarial attacks and train with 4 different training methods. They use the CIFAR10 and SVNH datasets.\n\nThe experiments showed that using k-WTA activation functions resulted in consistent improvements over ReLU activation functions in model robustness to white-box adversarial attacks when training with and without adversarial training methods. While, in the worst case, ReLU networks were around 50%-58% accurate in the face of adversarial attacks, k-WTA has accuracy that is usually 5%-17% higher.\n\nWhile the novelty of this paper is low, the switch from ReLU to k-WTA appear relatively simple and yields better results than that of ReLU.\n\nOther comments:\nI don't think that this claim can be made without experimental evidence and should be removed:\n\"We are not aware of any possible smooth approximation of a k-WTA network to launch BPDA attacks.\nEven if hypothetically there exists a smooth approximation of k-WTA activation, that approximation\nhas to be applied to every layer. Then the network would accumulate the approximation error at each\nlayer rapidly so that any gradient-estimation-based attack (such as BPDA) will be defeated.\"\n\nQuestion:\nI see the \\gamma parameter of k-WTA is updated with a certain schedule that includes some finetuning. Including this finetuning, is the final k-WTA network trained with the same number of iterations as the ReLU network? Are all the other hyperparameters the same?\n\n** After Author Response **\nChanging from weak accept to accept\n\nThe authors have addressed my concerns and I believe the paper can provide significant value to those interested in adversarial robustness.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gbs2K9FH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses the important question of improving the robustness of deep neural networks against adversarial attacks. The authors propose a surprisingly simple measure to improve adversarial robustness, namely replacing typical activation functions such as ReLU with a k-winners-take-all (k-WTA) functions, whereby the k largest values of the input vector are copied, and all other elements of the output vector are set to zero. Since the size of input and output maps varies drastically within networks, the authors instead use a sparsity ratio \\gamma that calculates k as a function of input size. k-WTA networks can be trained without special treatment, but for low \\gamma values the authors propose a training schedule, whereby \\gamma is slowly reduced, then re-training takes place, until the desired value of \\gamma is reached. The presented effect is backed up by extensive theoretical investigations that relate the increased robustness to the dense introduction of discontinuities, which makes gradient-based adversarial attacks harder. A small change in an input signal can change the identity of the \"winning\" inputs, and thus in a sub-sequent matrix multiplication make use of other rows or columns, thus allowing arbitrarily large effects due to small input variations. Empirical evaluations in CIFAR and SVHN for a variety of attacks and defense mechanisms demonstrate the desired effects, and illustrate the loss landscapes due to using k-WTA.\n\nI think the paper is a valuable and novel contribution to an important topic, and is definitely suitable for publication at ICLR. In principle there is just one novel idea, namely using k-WTA activations to improve adversarial robustness, but this claim is investigated thoroughly, in theory, and demonstrated convincingly in experiments. The paper is well written and tries to address all potential questions one might have surrounding the basic idea. There is code available, and the idea should be simple to implement in practice, so I would expect this paper to have large impact on the study of adversarial robustness.\n\nI appreciate the thorough proofs of the claims in section C of the appendix, but I did not review all proofs in  detail. \n\nPotential weaknesses that should be addressed:\n1. Section 4: I would propose to fully define A_rob here or at least provide a reference.\n2. From Table 1 it seems that using k-WTA leads to a quite noticeable drop in standard accuracy, especially for sparse \\gamma, which leads to the best adversarial robustness. Can you please comment on whether the full ReLU accuracy in the natural case can always be recovered by k-WTA networks, e.g. with larger \\gamma?\n3. Since small changes have a big effect in k-WTA, it should be investigated how robust the k-WTA networks are with respect to more natural perturbations, e.g. noisy input, blurring, translations, rotations, occlusions, etc. as introduced in (Hendrycks and Dietterich, 2019). It would be critical if such perturbations have a stronger effect on k-WTA.\n4. Is there any intuition about whether k-WTA should be used everywhere in a deep network, or whether it makes sense to mix k-WTA and ReLU functions? \n\nMinor comments:\n5. WTA networks are very popular in computational neuroscience and are even hypothesized to represent canonical microcircuit functions (see e.g. Douglas, Martin, Whitteridge, 1989, Neural Computation, and many follow-up articles). You cite the work of Maass, 2000a,b already, it could be interesting to link your work to other papers in that field who motivate WTA from a biological perspective.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents new non-linearity function which specially affects regions of the model which are densely valued. The non-linearity is simple: it retains only top-k highest units from the input, while truncating the rest to zero. This also makes the models more robust to adversarial defense which depend on the gradients. The non-linearity function is shown to have better adversarial robustness on CIFAR-10 and SVHN datasets. The paper also presents theoretical analysis for why the non-linearity is a good function.

The authors have already incorporated major suggestions by the reviewers and the paper can make significant impact on the community. Thus, I recommend its acceptance.
Decision: Accept (Spotlight)