You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'Deep neural networks (DNNs) are computationally/memory-intensive and vulnerable to adversarial attacks, making them prohibitive in some real-world applications. By converting dense models into sparse ones, pruning appears to be a promising solution to reducing the computation/memory cost. This paper studies classification models, especially DNN-based ones, to demonstrate that there exists intrinsic relationships between their sparsity and adversarial robustness. Our analyses reveal, both theoretically and empirically, that nonlinear DNN-based classifiers behave differently under $l_2$ attacks from some linear ones. We further demonstrate that an appropriately higher model sparsity implies better robustness of nonlinear DNNs, whereas over-sparsified models can be more difficult to resist adversarial examples.'
author:
- |
    Yiwen Guo^1,2^[^1]  Chao Zhang^3^ Changshui Zhang^2^ Yurong Chen^1^\
    ^1^ Intel Labs China\
    ^2^ Institute for Artificial Intelligence, Tsinghua University (THUAI),\
    State Key Lab of Intelligent Technologies and Systems,\
    Beijing National Research Center for Information Science and Technology (BNRis),\
    Department of Automation, Tsinghua University\
    ^3^ Academy for Advanced Interdisciplinary Studies, Peking University\
    \
bibliography:
- 'egbib.bib'
title: Sparse DNNs with Improved Adversarial Robustness
---

Introduction
============

Although deep neural networks (DNNs) have advanced the state-of-the-art of many artificial intelligence techniques, some undesired properties may hinder them from being deployed in real-world applications. With continued proliferation of deep learning powered applications, one major concern raised recently is the heavy computation and storage burden that DNN models shall lay upon mobile platforms. Such burden stems from substantially redundant feature representations and parameterizations [@Denil2013]. To address this issue and make DNNs less resource-intensive, a variety of solutions have been proposed. In particular, it has been reported that more than 90% of connections in a well-trained DNN can be removed using pruning strategies [@Han2015; @Guo2016; @Ullrich2017; @Molchanov2017; @Neklyudov2017], while no accuracy loss is observed. Such a remarkable network sparsity leads to considerable compressions and speedups on both GPUs and CPUs [@Park2017]. Aside from being efficient, sparse representations are theoretically attractive [@Candes2006; @Donoho2006] and have made their way into tremendous applications over the past decade. Orthogonal to the inefficiency issue, it has also been discovered that DNN models are vulnerable to adversarial examples—maliciously generated images which are perceptually similar to benign ones but can fool classifiers to make arbitrary predictions [@Szegedy2014; @Carlini2017]. Furthermore, generic regularizations (e.g., dropout and weight decay) do not really help on resisting adversarial attacks [@Goodfellow2015]. Such undesirable property may prohibit DNNs from being applied to security-sensitive applications. The cause of this phenomenon seems mysterious and remains to be an open question. One reasonable explanation is the local linearity of modern DNNs [@Goodfellow2015]. Quite a lot of attempts, including adversarial training [@Goodfellow2015; @Tramer2018; @Madry2018], knowledge distillation [@Papernot2016], detecting and rejecting [@Lu2017], and some gradient masking techniques like randomization [@Xie2018], have been made to ameliorate this issue and defend adversarial attacks.

It is crucial to study potential relationships between the inefficiency (i.e., redundancy) and adversarial robustness of classifiers, in consideration of the inclination to avoid “robbing Peter to pay Paul”, if possible. Towards shedding light on such relationships, especially for DNNs, we provide comprehensive analyses in this paper from both the theoretical and empirical perspectives. By introducing reasonable metrics, we reveal, somewhat surprising, that there is a discrepancy between the robustness of sparse linear classifiers and nonlinear DNNs, under $l_2$ attacks. Our results also demonstrate that an appropriately higher sparsity implies better robustness of nonlinear DNNs, whereas over-sparsified models can be more difficult to resist adversarial examples, under both the $l_\infty$ and $l_2$ circumstances.

Related Works
=============

In light of the “Occam’s razor” principle, we presume there exists intrinsic relationships between the sparsity and robustness of classifiers, and thus perform a comprehensive study in this paper. Our theoretical and empirical analyses shall cover both linear classifiers and nonlinear DNNs, in which the middle-layer activations and connection weights can all become sparse.

The (in)efficiency and robustness of DNNs have seldom been discussed together, especially from a theoretical point of view. Very recently, Gopalakrishnan et al. [@Gopalakrishnan2018; @Marzi2018] propose to sparsify the input representations as a defense and provide provable evidences on resisting $l_\infty$ attacks. Though intriguing, their theoretical analyses are limited to only linear and binary classification cases. Contemporaneous with our work, Wang et al. [@Wang2018] and Ye et al. [@Ye2018] experimentally discuss how pruning shall affect the robustness of some DNNs but surprisingly draw opposite conclusions. Galloway et al. [@Galloway2018] focus on binary DNNs instead of the sparse ones and show that the difficulty of performing adversarial attacks on binary networks DNNs remains as that of training.

To some extent, several very recent defense methods also utilize the sparsity of DNNs. For improved model robustness, Gao et al. [@Gao2017] attempt to detect the feature activations exclusive to the adversarial examples and prune them away. Dhillon et al. [@Dhillon2018] choose an alternative way that prunes activations stochastically to mask gradients. These methods focus only on the sparsity of middle-layer activations and pay little attention to the sparsity of connections.

Sparsity and Robustness of Classifiers {#sec:sob}
======================================

This paper aims at analyzing and exploring potential relationships between the sparsity and robustness of classifiers to untargeted white-box adversarial attacks, from both theoretical and practical perspectives. To be more specific, we consider models which learn parameterized mappings $\mathbf x_i\mapsto y_i$, when given a set of labelled training samples $\{(\mathbf x_i, y_i)\}$ for supervision. Similar to a bunch of other theoretical efforts, our analyses start from linear classifiers and will be generalized to nonlinear DNNs later in Section \[subsec:dnn\].

Generally, the sparsity of a DNN model can be considered in two aspects: the sparsity of connections among neurons and the sparsity of neuron activations. In particular, the sparsity of activations also include that of middle-layer activations and inputs, which can be treated as a special case. Knowing that the input sparsity has been previously discussed [@Gopalakrishnan2018], we shall focus primarily on the weight and activation sparsity for nonlinear DNNs and just study the weight sparsity for linear models.

Linear Models {#subsec:lin}
-------------

For simplicity of notation, we first give theoretical results for binary classifiers with $\hat{y}_i=\mathrm{sgn}(\mathbf w^T \mathbf x_i)$, in which $\mathbf{w, x}_i \in \mathbb R^n$. We also ignore the bias term $b$ for clarity. Notice that $\mathbf w^T \mathbf x+b$ can be simply rewritten as $\acute{\mathbf w}^T[\mathbf x;1]$ in which $\acute{\mathbf w}=[\mathbf w; b]$, so all our theoretical results in the sequel apply directly to linear cases with bias. Given ground-truth labels $y_i\in \{+1, -1\}$, a classifier can be effectively trained by minimizing some empirical loss $\sum_i \tau(-y_i\cdot \mathbf w^T\mathbf x_i)$ using a logistic sigmoid function like softplus: $\tau(\cdot)=\log (1 + \exp(\cdot))$ [@Goodfellow2015].

Adversarial attacks typically minimize an $l_p$ norm (e.g., $l_2$, $l_\infty$, $l_1$ and $l_0$) of the required perturbation under certain (box) constraints. Though not completely equivalent with the distinctions in our visual domain, such norms play a crucial role in evaluating adversarial robustness. We study both the $l_\infty$ and $l_2$ attacks in this paper. With an ambition to totalize them, we propose to evaluate the robustness of linear models using the following metrics that describe the ability of resisting them respectively: $$\begin{split}
\textbf{Binary}:\ r_\infty &:=\mathrm{E}_{\mathbf x,y} \left(1_{y = \mathrm{sgn}(\mathbf w^T \check{\mathbf x})}\right),  \\
r_2\ &:= \mathrm{E}_{\mathbf x,y} \left(1_{y = \hat{y}}\cdot d(\mathbf x, \tilde{\mathbf x}) \right).
\end{split}$$ Here we let $\check{\mathbf x}=\mathbf x - \epsilon y \cdot \mathrm{sgn}(\mathbf w)$ and $\tilde{\mathbf x}=\mathbf x - \mathbf w (\mathbf w^T \mathbf x)/\|\mathbf w\|^2_2$ be the adversarial examples generated by applying the fast gradient sign (FGS) [@Goodfellow2015] and DeepFool [@Moosavi2016] methods as representatives. Without box constraints on the image domain, they can be regarded as the optimal $l_\infty$ and $l_2$ attacks targeting on the linear classifiers [@Marzi2018; @Moosavi2016]. Function $d$ calculates the Euclidean distance between two $n$-dimensional vectors and we know that $d(\mathbf x, \tilde{\mathbf x})=|\mathbf w^T \mathbf x|/\|\mathbf w\|_2$.

The introduced two metrics evaluate robustness of classifiers from two different perspectives: $r_\infty$ calculates the expected accuracy on (FGS) adversarial examples and $r_2$ measures a decision margin between benign examples from the two classes. For both of them, higher value indicates stronger adversarial robustness. Note that unlike some metrics calculating (maybe normalized) Euclidean distances between all pairs of benign and adversarial examples, our $r_2$ omits the originally misclassfied examples, which makes more sense if the classifiers are imperfect in the sense of prediction accuracy. We will refer to $\bm{\mu}_k:=\mathrm{E}(\mathbf x|y=k,\hat{y}=k)$, which is the conditional expectation for class $k$.

Be aware that although there exists attack-agnostic guarantees on the model robustness [@Hein2017; @Weng2018], they are all instance-specific. Instead of generalizing them to the entire input space for analysis, we focus on the proposed statistical metrics and present their connections to the guarantees later in Section \[subsec:dnn\]. Some other experimentally feasible metrics shall be involved in Section \[sec:exp\]. The following theorem sheds light on intrinsic relationships between the described robustness metrics and $l_p$ norms of $\mathbf w$.

 \[theo:0\](The sparsity and robustness of binary linear classifiers). Suppose that $\mathrm{P}_y(k)=1/2$ for $k=\pm1$, and an obtained linear classifier achieves the same expected accuracy $t$ on different classes, then we have $$\label{eq:0}
r_2=\frac{t}{2}\cdot\frac{\mathbf w^T (\bm{\mu}_{+1}-\bm{\mu}_{-1})}{\|\mathbf w\|_2} \quad \text{and} \quad r_\infty\leq \frac{t}{2}\cdot\frac{\mathbf w^T (\bm{\mu}_{+1}-\bm{\mu}_{-1})}{\epsilon \|\mathbf w\|_1}.$$

For $r_\infty$, we first rewrite it in the form of $\mathrm{Pr}(y\cdot \mathbf w^T\check{\mathbf x} > 0)$. We know from assumptions that $\mathrm{Pr}(\hat{y}=k|y=k)=t$ and $\mathrm{Pr}(y=k)=1/2$, so we further get $$\label{eq:1}
r_\infty = \sum_{k=\pm1} \frac{t}{2}\,\mathrm{Pr}\,(k\cdot\mathbf w^T\mathbf x>\epsilon\|\mathbf w\|_1 |\, y=k, \hat{y}=k),$$ by using the law of total probability and substituting $\check{\mathbf x}$ with $\mathbf x - \epsilon y \cdot \mathrm{sgn}(\mathbf w)$. Lastly the result follows after using the Markov’s inequality.

As for $r_2$, the proof is straightforward by similarly casting its definition into the sum of conditional expectations. That is, $$\label{eq:2}
r_2 = \sum_{k=\pm1} \frac{t}{2}\,\mathrm{E}_{\mathbf x|y, \hat{y}}\left(\left.\frac{|\mathbf w^T \mathbf x|}{\|\mathbf w\|_2} \right| y=k, \hat{y}=k\right).$$-0.25in

Theorem \[theo:0\] indicates clear relationships between the sparsity and robustness of linear models. In terms of $r_\infty$, optimizing the problem gives rise to a sparse solution of $\mathbf w$. By duality, maximizing the squared upper bound of $r_\infty$ also resembles solving a sparse PCA problem [@d2008]. Reciprocally, we might also concur that a highly sparse $\mathbf w$ implies relatively robust classification results. Nevertheless, it seems that the defined $r_2$ has nothing to do with the sparsity of $\mathbf w$. It gets maximized iff $\mathbf w$ approaches $\bm{\mu}_{+1}-\bm{\mu}_{-1}$ or $\bm{\mu}_{-1}-\bm{\mu}_{+1}$, however, sparsifying $\mathbf w$ probably does not help on reaching this goal. In fact, under some assumptions about data distributions, the dense reference model can be nearly optimal in the sense of $r_2$. We will see this phenomenon remains in multi-class linear classifications in Theorem \[theo:1\] but does not remain in nonlinear DNNs in Section \[subsec:dnn\]. One can check Section \[subsec:explin\] and \[subsec:expdnn\] for some experimental discussions in more details.

Having realized that the $l_\infty$ robustness of binary linear classifiers is closely related to $\|\mathbf w\|_1$, we now turn to multi-class cases with the ground truth $y_i\in \{1,\ldots,c\}$ and prediction $\hat{y}_i=\operatorname*{arg\,max}_k (\mathbf w^T_k \mathbf x_i)$, in which $\mathbf w_k=W[:,k]$ indicates the $k$-th column of a matrix $W\in \mathbb R^{n\times c}$. Here the training objective $f$ calculates the cross-entropy loss between ground truth labels and outputs of a softmax function. The introduced two metrics shall be slightly modified to: $$\begin{split}
\textbf{Multi-class}:\ r_\infty &:=\mathrm{E}_{\mathbf x,y} \left(1_{y = \operatorname*{arg\,max}_k(\mathbf w_k^T \check{\mathbf x})}\right),\\
r_2\ &:= \mathrm{E}_{\mathbf x,y} \left(1_{y = \hat{y}}\cdot d(\mathbf x, \tilde{\mathbf x}) \right).
\end{split}$$ Likewise, $\check{\mathbf x}=\mathbf x + \epsilon \cdot \mathrm{sgn}(\nabla f(\mathbf x))$ and $\tilde{\mathbf x}=\mathbf x-\mathbf w_\delta(\mathbf w_\delta^T\mathbf x)/\|\mathbf w_\delta\|^2_2$ are the FGS and DeepFool adversarial examples under multi-class circumstances, in which $\mathbf w_\delta=\mathbf w_{\hat{y}}-\mathbf w_{e}$ and $e\in \{1,\ldots, c\}-\{\hat{y}\}$ is carefully chosen such that $ |(\mathbf w_{\hat{y}}-\mathbf w_e)^T\mathbf x|/\|\mathbf w_{\hat{y}}-\mathbf w_e\|_2$ is minimized. Denote an averaged classifier by $\bar {\mathbf w}:=\sum_k \mathbf w_k/c$, we provide upper bounds for both $r_\infty$ and $r_2$ in the following theorem.

 \[theo:1\](The sparsity and robustness of multi-class linear classifiers). Suppose that $\mathrm{P}_y(k)=1/c$ for $k\in \{1,...,c\}$, and an obtained linear classifier achieves the same expected accuracy $t$ on different classes, then we have $$r_2 \leq \frac{t}{c} \sum_{k=1}^c \frac{(\mathbf w_k-\bar{\mathbf w})^T \bm{\mu}_k}{\|\mathbf w_k-\bar{\mathbf w}\|_2}\quad \text{and} \quad r_\infty \leq \frac{t}{c}\sum_{k=1}^c \frac{(\mathbf w_k-\bar{\mathbf w})^T \bm{\mu}_k}{\epsilon \|\mathbf w_k-\bar{\mathbf w}\|_1}$$ under two additional assumptions: () FGS achieves higher per-class success rates than a weaker perturbation like $-\epsilon \cdot \mathrm{sgn}(\mathbf w_y - \bar{\mathbf w})$, () the FGS perturbation does not correct misclassifications.

We present in Theorem \[theo:1\] similar bounds for multi-class classifiers to that provided in Theorem \[theo:0\], under some mild assumptions. Our proof is deferred to the supplementary material. We emphasize that the two additional assumptions are intuitively acceptable. First, increasing the classification loss in a more principled way, say using FGS, ought to diminish the expected accuracy more effectively. Second, with high probability, an original misclassification cannot be fixed using the FGS method, as one intends to do precisely the opposite.

Similarly, the presented bound for $r_\infty$ also implies sparsity, though it is the sparsity of $\mathbf w_k - \bar{\mathbf w}$. In fact, this is directly related with the sparsity of $\mathbf w_k$, considering that the classifiers can be post-processed to subtract their average simultaneously whilst the classification decision won’t change for any possible input. Particularly, Theorem \[theo:1\] also partially suits linear DNN-based classifications. Let the classifier $g_k$ be factorized in a form of $\mathbf w^T_k=(\mathbf w_k')^TW^T_{d-1}\ldots W^T_1$, it is evident to see that higher sparsity of the multipliers encourages higher probability of a sparse $\mathbf w_k$.

Deep Neural Networks {#subsec:dnn}
--------------------

A nonlinear feedforward DNN is usually specified by a directed acyclic graph $G=(\mathcal V,\mathcal E)$ [@Cisse2017] with a single root node for final outputs. According to the forward propagation rule, the activation value of each internal (and also output) node is calculated based on its incoming nodes and learnable weights corresponding to the edges. Nonlinear activation functions are incorporated to ensure the capacity. With biases, some nodes output a special value of one. We omit them for simplicity reasons as before.

Classifications are performed by comparing the prediction scores corresponding to different classes, which means $\hat{y} = \operatorname*{arg\,max}_{k\in\{1,\ldots,c\}} g_k(\mathbf x)$. Benefit from some very recent theoretic efforts [@Hein2017; @Weng2018], we can directly utilize well-established robustness guarantees for nonlinear DNNs. Let us first denote by $B_p(\mathbf x, R)$ a close ball centred at $\mathbf x$ with radius $R$ and then denote by $L_{q,\mathbf x}^k$ the (best) local Lipschitz constant of function $g_{\hat y}(\mathbf x)-g_k(\mathbf x)$ over a fixed $B_p(\mathbf x, R)$, if there exists one. It has been proven that the following lemma offers a reasonable lower bound for the required $l_p$ norm of instance-specific perturbations when all classifiers are Lipschitz continuous [@Weng2018].

\[lemm:1\] Let $\hat{y} = \operatorname*{arg\,max}_{k\in\{1,\ldots,c\}} g_k(\mathbf x)$ and $\frac{1}{p} + \frac{1}{q} = 1$, then for any $\Delta_{\mathbf x} \in B_p(\mathbf 0, R)$, $p \in \mathbb R^+$ and a set of Lipschitz continuous functions $\{g_k: \mathbb R^n\mapsto \mathbb R\}$, with $$\|\Delta_{\mathbf x}\|_p \leq \min\left\{\min \limits_{k \neq \hat{y}} \frac{g_{\hat{y}}(\mathbf x)-g_k(\mathbf x)}{L_{q,\mathbf x}^k}, R\right\} := \gamma,$$ it holds that $\hat{y} = \operatorname*{arg\,max}_{k\in\{1,\ldots,c\}} g_k(\mathbf x+\Delta_{\mathbf x})$, which means the classification decision does not change on $B_p(\mathbf x, \gamma)$.

Here the introduced $\gamma$ is basically an instance-specific lower bound that guarantees the robustness of multi-class classifiers. We shall later discuss its connections with our $r_p$s, for $p\in\{\infty, 2\}$, and now we try providing a local Lipschitz constant (which may not be the smallest) of function $g_{\hat y}(\mathbf x)-g_k(\mathbf x)$, to help us delve deeper into the robustness of nonlinear DNNs. Without loss of generality, we will let the following discussion be made under a fixed radius $R>0$ and a given instance $\mathbf x\in \mathbb R^n$.

Some modern DNNs can be structurally very complex. Let us simply consider a multi-layer perceptron (MLP) parameterized by a series of weight matrices $W_1\in \mathbb R^{n_0\times n_1},\ldots, W_d\in \mathbb R^{n_{d-1}\times n_{d}}$, in which $n_0=n$ and $n_d=c$. Discussions about networks with more advanced architectures like convolutions, pooling and skip connections can be directly generalized [@Bartlett2017]. Specifically, we have $$g_k(\mathbf x_i) = \ \mathbf w^T_k\sigma(W^T_{d-1}\sigma(\ldots\sigma(W^T_1\mathbf x_i))),$$ in which $\mathbf w_k=W_d[:, k]$ and $\sigma$ is the nonlinear activation function. Here we mostly focus on “ReLU networks” with rectified-linear-flavoured nonlinearity, so the neuron activations in middle-layers are naturally sparse. Due to clarity reasons, we discuss the weight and activation sparsities separately. Mathematically, we let $\mathbf a_0=\mathbf x$ and $\mathbf a_j=\sigma (W^T_j \mathbf a_{j-1})$ for $0< j< d$ be the layer-wise activations. We will refer to -0.2in $$D_j(\mathbf x) := \mathrm{diag}\left(1_{W_j[:,1]^T \mathbf a_{j-1} > 0},\ldots,1_{W_j[:,n_{j}]^T \mathbf a_{j-1} > 0}\right),$$ -0.01in which is a diagonal matrix whose entries taking value one correspond to nonzero activations within the $j$-th layer, and $M_j\in\{0,1\}^{n_{j-1}\times n_j}$, which is a binary mask corresponding to each (possibly sparse) $W_j$. Along with some analyses, the following lemma and theorem present intrinsic relationships between the adversarial robustness and (both weight and activation) sparsity of nonlinear DNNs. 0.06in

\[lemm:2\](A local Lipschitz constant for ReLU networks). Let $\frac{1}{p} + \frac{1}{q} = 1$, then for any $\mathbf x \in \mathbb R^n$, $k\in\{1,\ldots,c\}$ and $q \in \{1, 2\}$, the local Lipschitz constant of function $g_{\hat{y}}(\mathbf x)-g_k(\mathbf x)$ satisfies -0.15in $$L_{q,\mathbf x}^k \leq \|\mathbf w_{\hat{y}} - \mathbf w_k\|_q  \sup \limits_{\mathbf x' \in B_p(\mathbf x, R)} \prod_{j=1}^{d-1} \left(\|D_j(\mathbf x')\|_p\|W_j\|_p\right).$$

-0.08in

\[theo:3\] (The sparsity and robustness of nonlinear DNNs). Let the weight matrix be represented as $W_j=W'_j\circ M_j$, in which $\{M_j[u,v]\}$ are independent Bernoulli $B(1, 1-\alpha_j)$ random variables and $0\notin\{W'_j[u,v]\}$, for $j\in\{1,\ldots,d-1\}$. Then for any $\mathbf x \in \mathbb R^n$ and $k\in\{1,\ldots,c\}$, it holds that $$\mathrm{E}_{M_1,\ldots,M_{d-1}} (L_{2,\mathbf x}^k) \leq c_2\cdot(1-\eta(\alpha_1, \ldots, \alpha_{d-1}; \mathbf x))$$ and $$\mathrm{E}_{M_1,\ldots,M_{d-1}} (L_{1, \mathbf x}^k) \leq c_1\cdot(1-\eta(\alpha_1, \ldots ,\alpha_{d-1}; \mathbf x)),$$ -0.05in in which function $\eta$ is monotonically increasing w.r.t. each $\alpha_j$, $c_2=\| \mathbf w_{\hat{y}} - \mathbf w_k\|_2 \prod_j \| W_j' \|_F $ and $c_1=\| \mathbf w_{\hat{y}} - \mathbf w_k\|_1 \prod_j \| W_j' \|_{1,\infty}$ are two constants.

Function $\prod\|D_j(\cdot)\|_p\|W_j\|_p$ defined on $\mathbb R^n$ is bounded from above and below, thus we know there exists an $\hat{\mathbf x}\in B_p(\mathbf x, R)$ satisfying $$L_{q,\mathbf x}^k \leq \|\mathbf w_{\hat y} - \mathbf w_k\|_q \prod_{j} \|D_j(\hat{\mathbf x})\|_p\|W_j\|_p.$$ Particularly, $\prod\|D_j(\hat{\mathbf x})\|_p\neq 0$ is fulfilled iff $\|D_{d-1}(\hat{\mathbf x})\|_p\neq 0$ (i.e., it equals 1 for $q\in\{1,2\}$). Under the assumptions on $M_j$, we know that the entries of $W_j$ are independent of each other, thus $$\begin{aligned}
\mathrm{Pr}_{M_1,\ldots,M_{d-1}}(D_{d-1}(\hat{\mathbf x})[u,u]=0) &= \mathrm{Pr}_{M_1,\ldots,M_{d-1}}(W_{d-1}[:,u]^T \mathbf a_{d-2} \leq 0) \\
&\geq \prod_{u'} (\alpha_{d-1}+ \xi_{d-2, u'}-\alpha_{d-1}\xi_{d-2, u'}),
\end{aligned}$$ in which $\xi_{d-2, u'}$ is a newly introduced scalar that equals or less equals to the probability of the $u'$-th neuron being deactivated. In this manner, we can recursively define the function $\eta$ and it is easy to validate its monotonicity. Additionally, we prove that $c_q\geq \| \mathbf w_{\hat{y}} - \mathbf w_k\|_q\mathrm{E}\,(\prod\|W_j\|_p|\|D_{d-1}(\hat{\mathbf x})\|_p=1)$ holds for $q\in\{1,2\}$ and the result follows. See the supplementary material for a detailed proof.

In Lemma \[lemm:2\] we introduce probably smaller local Lipschitz constants than the commonly known ones (i.e., $c_2$ and $c_1$), and subsequently in Theorem \[theo:3\] we build theoretical relationships between $L_{q,\mathbf x}^k$ and the network sparsity, for $q\in\{1, 2\}$ (i.e., $p\in\{\infty, 2\}$). Apparently, $L_{q,\mathbf x}^k$ is prone to get smaller if any weight matrix gets more sparse. It is worthy noting that the local Lipschitz constant is of great importance in evaluating the robustness of DNNs, and it is effective to regularize DNNs by just minimizing $L_{q,\mathbf x}^k$, or equivalently $\|\nabla g_{\hat{y}}(\mathbf x) - \nabla g_k(\mathbf x)\|_q$ for differentiable continuous functions [@Hein2017]. Thus we reckon, when the network is over-parameterized, an appropriately higher weight sparsity implies a larger $\gamma$ and stronger robustness. There are similar conclusions if $\mathbf a_j$ gets more sparse. Recall that in the linear binary case, we apply the DeepFool adversarial example $\tilde{\mathbf x}$ when evaluating the robustness using $r_2$. It is not difficult to validate that the equality $d(\mathbf x, \tilde{\mathbf x})=|( \mathbf w_{\hat{y}}-\mathbf w_{k\neq\hat{y}})^T \mathbf x|/L^k_{2,\mathbf x}$ holds for such $\tilde{\mathbf x}$ and $\mathbf w_{\pm1} := \pm \mathbf w$, which means the DeepFool perturbation ideally minimizes the Euclidean norm and helps us measure a lower bound in this regard. This can be directly generalized to multi-class classifiers. Unlike $r_2$ which represents a margin, our $r_\infty$ is basically an expected accuracy. Nevertheless, we also know that a perturbation of $-\epsilon y \cdot\mathrm{sgn}(\mathbf w)$ shall successfully fool the classifiers if $\epsilon\geq|( \mathbf w_{\hat{y}}-\mathbf w_{k\neq\hat{y}})^T \mathbf x|/L^k_{1,\mathbf x}$.

Experimental Results {#sec:exp}
====================

In this section, we conduct experiments to testify our theoretical results. To be consistent, we still start from linear models and turn to nonlinear DNNs afterwards. As previously discussed, we perform both $l_\infty$ and $l_2$ attacks on the classifiers to evaluate their adversarial robustness. In addition to the FGS [@Goodfellow2015] and DeepFool [@Moosavi2016] attacks which have been thoroughly discussed in Section \[sec:sob\], we introduce two more attacks in this section for extensive comparisons of the model robustness.

#### Adversarial attacks.

We use the FGS and randomized FGS (rFGS) [@Tramer2018] methods to perform $l_\infty$ attacks. As a famous $l_\infty$ attack, FGS has been widely exploited in the literature. In order to generate adversarial examples, it calculates the gradient of training loss w.r.t. benign inputs and uses its sign as perturbations, in an element-wise manner. The rFGS attack is a computationally efficient alternative to multi-step $l_\infty$ attacks with an ability of breaking adversarial training-based defences. We keep its hyper-parameters fixed for all experiments in this paper. For $l_2$ attacks, we choose DeepFool and the C&W’s attack [@Carlini2017]. DeepFool linearises nonlinear classifiers locally and approximates the optimal perturbations iteratively. C&W’s method casts the problem of constructing adversarial examples as optimizing an objective function without constraints, such that some recent gradient-descent-based solvers can be adopted. On the base of different attacks, four $r_2$ and $r_\infty$ values can be calculated for each classification model.

-0.07in

[0.23]{} ![The robustness of linear classifiers with varying weight sparsity. Upper: binary classification between “1”s and “7”s, lower: multi-class classification on the whole MNIST test set.](images/mnist-lin-a.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of linear classifiers with varying weight sparsity. Upper: binary classification between “1”s and “7”s, lower: multi-class classification on the whole MNIST test set.](images/mnist-lin-c.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of linear classifiers with varying weight sparsity. Upper: binary classification between “1”s and “7”s, lower: multi-class classification on the whole MNIST test set.](images/mnist-lin-b.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of linear classifiers with varying weight sparsity. Upper: binary classification between “1”s and “7”s, lower: multi-class classification on the whole MNIST test set.](images/mnist-lin-d.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of linear classifiers with varying weight sparsity. Upper: binary classification between “1”s and “7”s, lower: multi-class classification on the whole MNIST test set.](images/mnist-linm-a.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of linear classifiers with varying weight sparsity. Upper: binary classification between “1”s and “7”s, lower: multi-class classification on the whole MNIST test set.](images/mnist-linm-c.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of linear classifiers with varying weight sparsity. Upper: binary classification between “1”s and “7”s, lower: multi-class classification on the whole MNIST test set.](images/mnist-linm-b.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of linear classifiers with varying weight sparsity. Upper: binary classification between “1”s and “7”s, lower: multi-class classification on the whole MNIST test set.](images/mnist-linm-d.png "fig:"){width="\linewidth"}

-0.1in \[fig:lin\]

The Sparse Linear Classifier Behaves Differently under $l_\infty$ and $l_2$ Attacks {#subsec:explin}
-----------------------------------------------------------------------------------

In our experiments on linear classifiers, both the binary and multi-class scenarios shall be evaluated. We choose the well-established MNIST dataset as a benchmark, which consists of 70,000 $28\times28$ images of handwritten digits. According to the official test protocol, 10,000 of them should be used for performance evaluation and the remaining 60,000 for training. For experiments on the binary cases, we randomly choose a pair of digits (e.g., “0” and “8” or “1” and “7”) as positive and negative classes. Linear classifiers are trained following our previous discussions and utilizing the softplus function: $\min_{\mathbf w, b} \sum_i \log(1+\exp(-y_i(\mathbf w^T\mathbf x_i+b)))$. Parameters $\mathbf w$ and $b$ are randomly initialized and learnt by means of stochastic gradient descent with momentum. For the “1” and “7” classification case, we train 10 reference models from different initializations and achieve a prediction accuracy of $99.17\pm 0.00\%$ on the benign test set. For the classification of all 10 classes, we train 10 references similarly and achieve a test-set accuracy of $92.26\pm0.08\%$.

To produce models with different weight sparsities, we use a progressive pruning strategy [@Han2015]. That being said, we follow a pipeline of iteratively pruning and re-training. Within each iteration, a portion ($\rho$) of nonzero entries of $\mathbf w$, whose magnitudes are relatively small in comparison with the others, will be directly set to zero and shall never be activated again. After $m$ times of such “pruning”, we shall collect $10(m+1)$ models from all 10 dense references. Here we set $m=16, \rho=1/3$ so the achieved final percentage of zero weights should be $99.74\%\approx1-(1-\rho)^m$. We calculate the prediction accuracies on adversarial examples (i.e., $r_\infty$) under different $l_\infty$ attacks and the average Euclidean norm of required perturbations (i.e., $r_2$) under different $l_2$ attacks to evaluate the adversarial robustness of different models in practice. For $l_\infty$ attacks, we set $\epsilon=0.1$.

Figure \[fig:lin\] illustrates how our metrics of robustness vary with the weight sparsity. We only demonstrate the variability of the first 12 points (from left to right) on each curve, to make the bars more resolvable. The upper and lower subfigures correspond to binary and multi-class cases, respectively. Obviously, the experimental results are consistent with our previous theoretical ones. While sparse linear models are prone to be more robust in the sense of $r_\infty$, their $r_2$ robustness maintains similar or becomes even slightly weaker than the dense references, until there emerges inevitable accuracy degradations on benign examples (i.e., when $r_\infty$ may drop as well). We also observe from Figure \[fig:lin\] that, in both the binary and multi-class cases, $r_2$ starts decreasing much earlier than the benign-set accuracy. Though very slight in the binary case, the degradation of $r_2$ actually occurs after the first round of pruning (from $2.0103\pm0.0022$ to $2.0009\pm0.0016$ with DeepFool incorporated, and from $2.3151\pm0.0023$ to $2.3061\pm0.0023$ with the C&W’s attack).

-0.07in

[0.23]{} ![The robustness of nonlinear DNNs with varying weight sparsity. (a)-(b): LeNet-300-100, (c)-(d): LeNet-5, (e)-(f): the VGG-like network, (g)-(h): ResNet-32.](images/mnist-mlp-a.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of nonlinear DNNs with varying weight sparsity. (a)-(b): LeNet-300-100, (c)-(d): LeNet-5, (e)-(f): the VGG-like network, (g)-(h): ResNet-32.](images/mnist-mlp-c.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of nonlinear DNNs with varying weight sparsity. (a)-(b): LeNet-300-100, (c)-(d): LeNet-5, (e)-(f): the VGG-like network, (g)-(h): ResNet-32.](images/mnist-lenet-a.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of nonlinear DNNs with varying weight sparsity. (a)-(b): LeNet-300-100, (c)-(d): LeNet-5, (e)-(f): the VGG-like network, (g)-(h): ResNet-32.](images/mnist-lenet-c.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of nonlinear DNNs with varying weight sparsity. (a)-(b): LeNet-300-100, (c)-(d): LeNet-5, (e)-(f): the VGG-like network, (g)-(h): ResNet-32.](images/cifar-vgg-a.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of nonlinear DNNs with varying weight sparsity. (a)-(b): LeNet-300-100, (c)-(d): LeNet-5, (e)-(f): the VGG-like network, (g)-(h): ResNet-32.](images/cifar-vgg-c.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of nonlinear DNNs with varying weight sparsity. (a)-(b): LeNet-300-100, (c)-(d): LeNet-5, (e)-(f): the VGG-like network, (g)-(h): ResNet-32.](images/cifar-res-a.png "fig:"){width="\linewidth"}

[0.23]{} ![The robustness of nonlinear DNNs with varying weight sparsity. (a)-(b): LeNet-300-100, (c)-(d): LeNet-5, (e)-(f): the VGG-like network, (g)-(h): ResNet-32.](images/cifar-res-c.png "fig:"){width="\linewidth"}

-0.15in \[fig:dnn\]

Sparse Nonlinear DNNs Can be Consistently More Robust {#subsec:expdnn}
-----------------------------------------------------

Regarding nonlinear DNNs, we follow the same experimental pipeline as described in Section \[subsec:explin\]. We train MLPs with 2 hidden fully-connected layers and convolutional networks with 2 convolutional layers, 2 pooling layers and 2 fully-connected layers as references on MNIST, following the “LeNet-300-100” and “LeNet-5” architectures in network compression papers [@Han2015; @Guo2016; @Ullrich2017; @Molchanov2017]. We also follow the training policy suggested by Caffe [@Jia2014] and train network models for 50,000 iterations with a batch size of 64 such that the training cross-entropy loss does not decrease any longer. The well-trained reference models achieve much higher prediction accuracies (LeNet-300-100: $98.20\pm0.07\%$ and LeNet-5: $99.11\pm0.04\%$) than previous tested linear ones on the benign test set.

#### Weight sparsity.

Then we prune the dense references and illustrate some major results regarding the robustness and weight sparsity in Figure \[fig:dnn\] (a)-(d). (See Figure 3 in our supplementary material for results under rFGS and the C&W’s attack.) Weight matrices/tensors within each layer is uniformly pruned so the network sparsity should be approximately equal to the layer-wise sparsity. As expected, we observe similar results to previous linear cases in the context of our $r_\infty$ but significantly different results in $r_2$. Unlike previous linear models which behave differently under $l_\infty$ and $l_2$ attacks, nonlinear DNN models show a consistent trend of adversarial robustness with respect to the sparsity. In particular, we observe increased $r_\infty$ and $r_2$ values under different attacks when continually pruning the models, until the sparsity reaches some thresholds and leads to inevitable capacity degradations. For additional verifications, we calculate the CLEVER [@Weng2018] scores that approximate attack-agnostic lower bounds of the $l_p$ norms of required perturbations (in Table 3 in the supplementary material).

Experiments are also conducted on CIFAR-10, in which deeper nonlinear networks can be involved. We train 10 VGG-like network models [@Neklyudov2017] (each incorporates 12 convolutional layers and 2 fully-connected layers) and 10 ResNet models [@He2016] (each incorporates 31 convolutional layers and a single fully-connected layers) from scratch. Such deep architectures lead to average prediction accuracies of $93.01\%$ and $92.89\%$. Still, we prune dense network models in the progressive manner and illustrate quantitative relationships between the robustness and weight sparsity in Figure \[fig:dnn\] (e)-(h). The first and last layers in each network are kept dense to avoid early accuracy degradation on the benign set. The same observations can be made. Note that the ResNets are capable of resisting some DeepFool examples, for which the second and subsequent iterations make little sense and can be disregarded.

#### Activation sparsity.

Having testified relationship between the robustness and weight sparsity of nonlinear DNNs, we now examine the activation sparsity. As previously mentioned, the middle-layer activations of ReLU incorporated DNNs are naturally sparse. We simply add a $l_1$ norm regularization of weight matrices/tensors to the learning objective to encourage higher sparsities and calculate $r_\infty$ and $r_2$ accordingly. Experiments are conducted on MNIST. Table \[tab:act\] summarizes the results, in which “Sparsity ($\mathbf a$)” indicates the percentage of deactivated (i.e., zero) neurons feeding to the last fully-connected layer. Here the $r_\infty$ and $r_2$ values are calculated using the FGS and DeepFool attacks, respectively. Apparently, we still observe positive correlations between the robustness and (activation) sparsity in a certain range.

  Network         $r_\infty$                  $r_2$                       Accuracy                  Sparsity ($\mathbf a$)   
  --------------- --------------------------- --------------------------- ------------------------- ------------------------ --
                  0.2862$\pm$0.0113           1.3213$\pm$0.0207           98.20$\pm$0.07%           45.25$\pm$1.14%          
  LeNet-300-100   [**0.3993$\pm$0.0079**]{}   [**1.5903$\pm$0.0240**]{}   [**98.27$\pm$0.04%**]{}   75.92$\pm$0.54%          
                  0.2098$\pm$0.0133           1.1440$\pm$0.0402           97.96$\pm$0.07%           95.22$\pm$0.18%          
                  0.7388$\pm$0.0188           2.7831$\pm$0.1490           99.11$\pm$0.04%           51.26$\pm$1.88%          
  LeNet-5         [**0.7729$\pm$0.0081**]{}   [**3.1688$\pm$0.1203**]{}   [**99.19$\pm$0.05%**]{}   97.54$\pm$0.10%          
                  0.6741$\pm$0.0162           2.0799$\pm$0.0522           99.10$\pm$0.06%           99.64$\pm$0.02%          

  : The robustness of DNNs regularized using the $l_1$ norm of weight matrices/tensors.[]{data-label="tab:act"}

Avoid “Over-pruning” 
---------------------

We discover from Figure \[fig:dnn\] that the sharp decrease of the adversarial robustness, especially in the sense of $r_2$, may occur in advance of the benign-set accuracy degradation. Hence, it can be necessary to evaluate the adversarial robustness of DNNs during an aggressive surgery, even though the prediction accuracy of compressed models may remain competitive with their references on benign test-sets. To further explore this, we collect some off-the-shelf sparse models (including a $56\times$ compressed LeNet-300-100 and a $108\times$ compressed LeNet-5) [@Guo2016] and their corresponding dense references from the Internet and hereby evaluate their $r_\infty$ and $r_2$ robustness. Table \[tab:dns\] compares the robustness of different models. Obviously, these extremely sparse models are more vulnerable to the DeepFool attack, and what’s worse, the over $100\times$ pruned LeNet-5 seems also more vulnerable to FGS, which suggests researchers to take care and avoid “over-pruning” if possible. One might also discover the fact with other pruning methods.

  Model                  $r_\infty$       $r_2$            Sparsity ($W$)   
  ---------------------- ---------------- ---------------- ---------------- --
  LeNet-300-100 dense    0.2663           [**1.3899**]{}   0.00%            
  LeNet-300-100 sparse   [**0.3823**]{}   1.1058           98.21%           
  LeNet-5 dense          [**0.7887**]{}   [**2.7226**]{}   0.00%            
  LeNet-5 sparse         0.6791           1.7383           99.07%           

  : The robustness of pre-compressed nonlinear DNNs and their provided dense references.[]{data-label="tab:dns"}

Conclusions
===========

In this paper, we study some intrinsic relationships between the adversarial robustness and the sparsity of classifiers, both theoretically and empirically. By introducing plausible metrics, we demonstrate that unlike some linear models which behave differently under $l_\infty$ and $l_2$ attacks, sparse nonlinear DNNs can be consistently more robust to both of them than their corresponding dense references, until their sparsity reaches certain thresholds and inevitably causes harm to the network capacity. Our results also demonstrate that such sparsity, including sparse connections and middle-layer neuron activations, can be effectively imposed using network pruning and $l_1$ regularization of weight tensors.

Acknowledgement {#acknowledgement .unnumbered}
===============

We would like to thank anonymous reviewers for their constructive suggestions. Changshui Zhang is supported by NSFC (Grant No. 61876095, No. 61751308 and No. 61473167) and Beijing Natural Science Foundation (Grant No. L172037).

[^1]: The first two authors contributed equally to this work.