Explanation for Adversarial Example and Robustness - 2

By LI Haoyang 2020.11.16

Content

Robustness

All-Layer Margin - ICLR 2020 ?

Paper: https://openreview.net/forum?id=HJe_yR4Fwr

Colin Wei, Tengyu Ma. Improved Sample Complexities for Deep Neural Networks and Robust Classification via an All-Layer Margin. ICLR 2020.

In this work, we propose to instead analyze a new notion of margin, which we call the “all-layer margin.”

Our analysis reveals that the all-layer margin has a clear and direct relationship with generalization for deep models.

Output Margin and Generalization

In linear classifiers, generalization error is controlled by the output margins normalized by the classifier norm.

Suppose there are $n$ training data points each with norm $1$, and let $\gamma_i$ be the output margin on the $i$-th example. With high probability, if the classifier perfectly fits the training data, there is

For deeper models, the relationship between output margin and generalization is unfortunately less clear and interpretable.

In this work, we remedy this issue by proposing a new notion of margin, called "all-layer margin", which we use to obtain simple guarantees like (1.1) for deep models.

Let $m_i$ be the all-layer margin for the $i$-th example. A bound can be obtained by simply normalizing it by the sum of the complexities of the weights, formed as following:

They present three applications:

• By relating all-layer margin to output margin and other quantities, we obtain improved generalization bounds for neural nets.
• We extend our tools to give generalization bounds for adversarially robust classification error which are analogous to our bounds in the standard setting.
• We design a training algorithm that encourages a larger all-layer margin and demonstrate that it improves empirical performance over strong baselines.

Notation

They use the following notations:

• $\{a_i\}_{i=1}^k$, a sequence of $k$ elements $a_i$ indexed by $i$.
• $\circ$, function composition, i.e. $f\circ g(x)=f(g(x))$
• $\mathcal{F}\circ\mathcal{G}\triangleq\{f\circ g:f\in\mathcal{F},g\in\mathcal{G}\}$.
• $D_h$, partial derivative operator with respect to variable $h$
• $D_{h_i} f(h_1,h_2)$, partial derivative of $f$ with respect to $h_i$ evaluated at $(h_1,h_2)$
• $||\cdot||$, some norm
• $||f||_{op}\triangleq \sup_{x\in\mathcal{D}_I}\frac{||f(x)||_O}{||x||_{I}}$, for a function $f$ mapping between normed spaces $\mathcal{D}_I,\mathcal{D}_O$ with norms $||\cdot||_I,||\cdot||_O$.
• $||M||_{fro}$, the Frobenius norms of $M$.
• $||M||_{1,1}$, the sum of the absolute values of the entries of $M$.
• $\mathcal{N}_{||\cdot||}(\epsilon,\mathcal{S})$, the covering number of some set $\mathcal{S}$ (often a class of functions) in the metric induced by norm $||\cdot||$ with resolution $\epsilon$.
• $\mathcal{N}_{\infty}(\epsilon,\mathcal{F})$, the covering number of $\mathcal{F}$ in the metric $d_{\infty}(f,\hat{f})=\sup_x||f(x)-\hat{f}(x)||$.
• $||f||_{L_q(P)}\triangleq (\Bbb{E}_{x\sim P}[|f(x)|^q])^{1/q}$, where $f$ is a function and $P$ is a distribution
• $P_n\triangleq\{(x_i,y_i)\}_{i=1}^n$, where $P$ is a test distribution, $x\in\mathcal{D}_0$ denotes inputs and $y\in[l]$ is an integer label.
• $P_n$ is also used to denote the uniform distribution on these training samples.
• $\max_{y^\prime\in[l]}F(x)_{y^\prime}$ , a predicted label on input $x$ by a classifier $F:\mathcal{D}_0\to\R^l$.
• $\ell_{0-1}(F(x),y)$, the 0-1 prediction loss, which outputs 1 when $F$ incorrectly classifies $x$ and 0 otherwise.

I think the course of functional analysis may be a prerequisite for the understanding of this paper.

Simplified all-layer margin and its guarantees

Popular loss functions for classification, such as logistic and hinge loss, attempt to increase the output margin of a classifier by penalizing predictions that are too close to the decision boundary.

Consider the $l$ class multi-class classification setting with a classifier $F:\mathcal{D}_0\to\R^l$, the output margin on example $(x,y)$ is defined as

The difference between the correct prediction and the nearest incorrect prediction.

Suppose that the classifier $F(x)=f_k\circ\cdots\circ f_1(x)$ is computed by composing $k$ functions $f_k,\dots,f_1$, and let $\delta_k,\dots,\delta_1$ denote perturbations intended to be applied at each hidden layer.

The perturbed network output $F(x,\delta_1,\dots,\delta_k)$ is recursively defined as

The all-layer margin is then defined as the minimum norm of $\delta$ required to make the classifier misclassify the input.

The corresponding perturbation to the input here is also referred as the adversarial robustness of the classifier, i.e. the smallest adversarial perturbation.

For classifier $F$, input $x$ and label $y$, it's formulated as

The constraint that $F(x,\delta)$ misclassifies $x$ is equivalent to enforcing $\gamma(F(x),y)\le 0$. (by definition)

This all-layer margin considers simultaneous perturbations to all layers, which is crucial for achieving its statistical guarantees as they claimed.

Let $\mathcal{F}\triangleq\{f_k\circ\cdots\circ f_1:f_i\in\mathcal{F}_i\}$ be the class of compositions of functions from function classes $\mathcal{F_1,\dots,F_k}$.

An element of $\mathcal{F}$, i.e. $F\in\mathcal{F}$ will be a general classifier.

They assume that the covering number of each layer scales as

for some complexity $\mathcal{C}_i$.

Theorem 2.1 (Simplified version of Theorem A.1) In the above setting, with probability $1-\delta$ over the draw of the training data, all classifiers $F\in\mathcal{F}$ which achieve training error 0 satisfy

where $\zeta\triangleq O(\frac{\log(1/\delta)+\log n}{n})$ is a low-order term.

In other words, generalization is controlled by the sum of the complexities of the layers and the quadratic mean of $1/m_F$ on the training set.

In favor of generalization, more data (larger $n$) is better, a larger all-layer margin is better, i.e. more robustness against adversarial perturbation in all layers is better, less complexity is better.

For neural nets, $\mathcal{C}_i$ scales with weight matrix norms and $1/m_F$ can be upper bounded by a polynomial in the Jacobian and hidden layer norms and output margin, allowing us to avoid an exponential dependency on depth when these quantities are well-behaved on the training data.

Lemma 2.1 (Complexity Decomposition Lemma). Let $m\circ\mathcal{F}=\{m_F:F\in\mathcal{F}\}$ denote the family of all-layer margins of function compositions in $\mathcal{F}$. Then

The covering number of an individual layer commonly scales as $\log\mathcal{N}_{||\cdot||_{op}}(\epsilon,\mathcal{F_i})\le[\mathcal{C}_i^2/\epsilon^2]$. In this case, for all $\epsilon>0$, we obtain $\log\mathcal{N}_{\infty}(\epsilon,m\circ \mathcal{F})\le\left[\frac{(\sum_i c_i)^2}{\epsilon^2}\right]$.

???

Lemma 2.1 shows that the complexity of $m_F$ scales linearly in depth for any choice of layers $\mathcal{F}_i$.

Claim 2.1. For any two compositions $F=f_k\circ\cdots\circ f_1$ and $\hat{F}=\hat{f}_k\circ\cdots\circ\hat{f}_1$ and any $(x,y)$, we have $|m_F(x,y)-m_{\hat{F}}(x,y)|\le\sqrt{\sum_{i=1}^k||f_i-\hat{f}_i||_{op}^2}$

A result by Srebro et al. (2010) shows that generic smooth losses $\ell$ enjoy faster $O(n^{-1})$ convergence rates if the empirical loss is low.

Lemma 2.2. Suppose that $\ell$ is a $\beta$-smooth loss function taking values in $[0,1]$. Then in the setting of Theorem 2.1, we have with probability $1-\delta$ for all $F\in\mathcal{F}$:

for some universal constant $c>0$.

???

Generalization guarantees for neural networks

The math is too obscure....

Generalization guarantees for robust classification

Let $\mathcal{B}^{adv}(x)$ denote the set of possible perturbation of the adversarial classification loss $\ell_{0-1}^{adv}$ defined by

Theorem 4.1. Assume that the activation $\phi$ has a $\kappa_{\phi}^\prime$-Lipschitz derivative. Fix reference matrices $\{A_{(i)},B_{(i)}\}_{i=1}^k$ and any integer $q>0$. With probability $1-\delta$ over the draw of the training sample $P_n$, all neural nets $F$ which achieve robust training error 0 satisfy

where $\kappa_{(i)}^{adv}$ is defined by $\kappa_{(i)}^{adv}\triangleq\max_{x^\prime\in\mathcal{B}^{adv}(x)}\kappa_{(i)}^{NN}(x^\prime,y)$ for $\kappa_{(i)}^{NN}$ in (3.2), and $a_{(i)},\zeta$ are defined the same as in Theorem 3.1.

Designing regularizers for robust classification based on the bound in Theorem 4.1 is a promising direction for future work.

Empirical application of the all-layer margin

Inspired by the good statistical properties of the all-layer margin, we design an algorithm which encourages a larger all-layer margin during training.

Let $\ell$ denote the standard cross entropy loss used in training and $\Theta$ the parameters of the network, consider the following objective:

This objective can be interpreted as applying the Lagrange multiplier method to a softmax relaxation of the constraint $\max_{y^\prime}F(x,\delta_1,\dots,\delta_k)_{y^\prime}\neq y$ in the objective for all-layer margin.

We use Algorithm 1 to train a WideResNet architecture (Zagoruyko and Komodakis, 2016) on CIFAR10 and CIFAR100 in a variety of settings.

Inspired by our robust generalization bound, we also apply AMO to robust classification by extending the robust training algorithm of (Madry et al., 2017). Madry et al. (2017) adversarially perturb the training input via several steps of projected gradient descent (PGD) and train using the loss computed on this perturbed input.

Inspirations

I do not really get the sense of this paper.....

Understanding and Mitigating the Tradeoff Between Robustness and Accuracy - ICML 2020

Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, Percy Liang. Understanding and Mitigating the Tradeoff Between Robustness and Accuracy. ICML 2020. arXiv:2002.10716

Previous works attempt to explain the tradeoff between standard error and robust error in two settings:

• when no accurate classifier is consistent with the perturbed data
• when the hypothesis class is not expressive enough to contain the true classifier

Empirically on CIFAR-10, we find that the gap between the standard error of adversarial training and standard training decreases as we increase the labeled data size, thereby also suggesting the tradeoff could disappear with infinite data (See Figure 1).

In this work, we provide a different explanation for the tradeoff between standard and robust error that takes generalization from finite data into account.

We show that this tradeoff stems from overparameterization. If the restricted hypothesis class (by enforcing invariances) is still overparameterized, the inductive bias of the estimation procedure (e.g., the norm being minimized) plays a key role in determining the generalization of a model.

As shown in Figure 2

Training on augmented data with locally consistent perturbations of the training data (crosses) restricts the hypothesis class by encouraging the predictor to fit the local structure of the high density points.

They basically state that adversarial training overfits the augmented data.

Setup

They consider the problem of learning a mapping from input $x\in\mathcal{X}\sube \R^d$ to a target $y\in\mathcal{Y}$. Theoretically they consider $\mathcal{Y}=\R$, while empirically they consider general $\mathcal{Y}$.

The underlying distribution is denoted as $P_{xy}$, and $P_{x}$ is the marginal on the inputs, $P_{y}(\cdot|x)$ is the conditional distribution of the targets given inputs.

Given $n$ training pairs $(x_i,y_i)\sim P_{xy}$, they use $X_{std}$ to denote the measurement matrix $[x_1,x_2,\dots,x_n]^\top\in\R^{n\times d}$ and $y_{std}$ to denote the target vector $[y_1,y_2,\dots,y_n]^\top\in\R^n$.

The goal is to learn a predictor $f_{\theta}:\mathcal{X}\to\mathcal{Y}$ that has

1. low standard error on inputs $x$
2. low robust error with respect to a set of perturbations $T(x)$

For a predictor $f_{\theta}$ and a loss function $\ell$, the standard error is

and the robust error is

for consistent perturbations $T(x)$ that satisfy

These perturbations should not change the "label" of the target from human perspective.

Noiseless linear regression

For linear regression, i.e. $y=x^\top\theta ^*$ with true parameter $\theta^*\in\R^k$, the objective for the standard loss is (squared loss)

where $\Sigma=\Bbb{E}_{P_x}[x x^\top]$ is the population covariance.

Minimum norm estimators

They consider the robust training approaches that augment the standard training data $X_{std},y_{std}\in\R^{n\times d}\times\R$ with some extra training data $X_{ext},y_{ext}\in\R^{m\times d}\times \R,x_{ext}\in T(x)$, and call a combination of these two as augmented data.

They compare following mininorm estimators:

1. The standard estimator $\hat{\theta}_{std}$ interpolating $[X_{std},y_{std}]$.

   $$\hat{\theta}_{std}=\arg\min_{\theta}\{||\theta||_2:X_{std}\theta=y_{std}\}$$

2. The augmented estimator $\hat{\theta}_{aug}$ interpolating $X=[X_{std};X_{ext}],Y=[y_{std};y_{ext}]$.

   $$\hat{\theta}_{aug}=\arg\min_{\theta}\{||\theta||_2:X_{std}\theta=y_{std},X_{ext}\theta=y_{ext}\}$$

The minimum norm estimators estimate a linear interpolation of the provided data with a minimization of the norm of parameters.

Analysis in the linear regression setting

Case analysis

In the 3D space spanned by $e_1=[1,0,0]$, $e_2=[0,1,0]$ and $e_3=[0,0,1]$ in $\R^3$, suppose there is one data point for standard training $X_{std}=[0,0,1]$.

By definition, there exists $X_{std}\hat{\theta}_{std}=y_{std}$, hence $(\hat{\theta}_{std})_3=\theta^*_3$, while there is no constraint on the subspace spanned by $e_1,e_2$, i.e. the nullspace $Null(X_{std})$, by mininorm objective, the solution is chosen with $\hat{\theta}_{std}=[0,0,\theta_3^*]$, as shown in Figure 3, the projection of $\hat{\theta}_{std}$ onto $Null(X_{std})$ is the blue point at origin.

For this data point, the parameter only fits with the best estimator on the direction of $e_3$.

Suppose we augment with an extra data point $X_{ext}=[1,1,0]=e_1+e_2$ that lies in $Null(X_{std})$, as shown in Figure 3, the dotted black line. The augmented estimator $\hat{\theta}_{aug}$ still fits the standard data point $X_{std}$, i.e. $(\hat{\theta}_{aug})_3=\theta^*_3=(\hat{\theta_{std}})_3$, but with the extra data point $X_{ext}$, $\hat{\theta}_{aug}$ must also satisfy an additional constraint $X_{ext}\hat{\theta}_{aug}=X_{ext}\theta^*$.

The projection of the best estimator onto the extra data point should be the same with that of the augmented estimator.

The crucial observation is that additional constraints along one direction ($e_1+e_2$ in this case) could actually increase parameter error along other directions.

The contribution of different components of the parameter error to the standard error is scaled by the population covariance $\Sigma$.

Hence there exists a safe zone that when the augmenting data point falls into this zone, the standard error is not affected.

General characterizations

Define the parameter errors as

• $\Delta_{std}\stackrel{def}{=}\hat{\theta}_{std}-\theta^*$
• $\Delta_{aug}\stackrel{def}{=}\hat{\theta}_{aug}-\theta^*$

The corresponding standard errors are respectively

• $L_{std}(\hat{\theta}_{std})=\Delta_{std}^\top\Sigma\Delta_{std}$
• $L_{atd}(\hat{\theta}_{sug})=\Delta_{aug}^\top\Sigma\Delta_{aug}$

Define two projection operators respectively

• $\prod_{std}^{\bot}$, the projection matrix onto $Null(X_{std})$
• $\prod_{aug}^{\bot}$, the projection matrix onto $Null([X_{ext};X_{std}])$

Since $\hat{\theta}_{aug}$ and $\hat{\theta}_{std}$ are minimum norm interpolants, there exist

• $\prod_{std}^{\bot}\hat{\theta}_{std}=0$
• $\prod_{aug}^{\bot}\hat{\theta}_{aug}=0$

They should not have any extra value on the nullspace of the given data.

In noiseless linear regression, $\hat{\theta}_{std}$ and $\hat{\theta}_{aug}$ have no error in the span of $X_{std}$ and $[X_{std};X_{ext}]$ respectively, i.e.

• $\Delta_{std}=\prod_{std}^{\bot}\theta^*$
• $\Delta_{sug}=\prod_{aug}^{\bot}\theta^*$

The parameter error is controlled by the unseen data (the data in the nullspace of given data).

Theorem 1 The difference in the standard errors of the standard estimator $\hat{\theta}_{std}$ and augmented estimator $\hat{\theta}_{aug}$ can be written as follows:

where $v=\prod_{std}^{\bot}\prod_{aug}\theta^*$ and $w=\prod_{aug}^{\bot}\theta^*$.

The first term is always positive (as covariance matrix is semidefnite positive), corresponding to the benefit with extra data, while the second term can be negative and intuitively measures the cost of a positive increase in the parameter error along other directions.

The introduced extra data reduces the parameter error in its direction, but may bring other errors in other directions.

Corollary 1 The following conditions are sufficient for $L_{std}(\hat{\theta}_{aug})\le L_{std}(\hat{\theta}_{std})$, i.e. the standard error does not increase when fitting augmented data.

1. The population covariance $\Sigma$ is identity.
2. The augmented data $[X_{std};X_{ext}]$ spans the entire space, i.e. $\prod_{aug}^\bot=0$.
3. The extra data $x_{ext}\in\R^d$ is a single point such that $x_{ext}$ is an eigenvector of $\Sigma$.

We would like to draw special attention to the first condition. When $\Sigma=I$, notice that the norm that governs the standard error (Equation 6) matches the norm that is minimized by the interpolants (Equation 5).

As the eigenvalues of $\Sigma$ become less skewed, the space of safe points expands, eventually covering the entire space when $\Sigma=I$ (see Corollary 1).

Propostion 1 For a given $X_{std},X_{ext},\Sigma$,

for some scalar $\gamma>0$ that depends on $X_{std},X_{ext},\Sigma$.

In other words, for a large increase in standard error upon augmentation, the true parameter $\theta^*$ needs to be sufficiently more complex (in the $\ell_2$ norm) than the standard estimator $\hat{\theta}_{std}$.

Robust self-training

The so-called RST (robust self-training) refers to the adversarial training that incorporates additional unlabeled data via pseudo-labels from a standard estimator.

The general two-step robust self-training procedure is as follows:

1. Perform standard training on labeled data $\{(x_i,y_i)\}_{i=1}^n$ to obtain $\hat{\theta}_{std}=\arg\min_{\theta}\sum_{i=1}^n\ell(f_{\theta}(x_i),y_i)$.
2. Perform robust training on both the labeled data and unlabeled inputs $\{\tilde{x}_i\}_{i=1}^m$ with pseudo-labels $\tilde{y}_i=f_{\hat{\theta}_{std}}(\tilde{x}_i)$ generated from the standard estimator $\hat{\theta}_{std}$.

The second stage (adversarial training) typically involves a combination of the standard loss $\ell$ and a robust loss $\ell_{rob}$, i.e.

On the labeled dataset $\{(x_i,y_i)\}_{i=1}^n$, the standard and robust loss are

Respectively, on the unlabeled samples $\{\tilde{x}_i\}_{i=1}^m$, the losses are

Put them together, there comes

for fixed scalars $\alpha,\beta,\gamma,\lambda\ge 0$.

Robust self-training in linear regression

Using the squared loss as the loss function $\ell$, for consistent perturbations $T(\cdot)$, they analyze the following RST estimator for linear regression

The rest of this section is obscure without any illustration for the $\theta_{int-std}$.

Empirical evaluation of RST

In this work, we focus on both the standard and robust error and expand upon results from previous work.

Both RST+AT and RST+TRADES have lower robust and standard error than their supervised counterparts AT and TRADES across all perturbation types.

What is this so-called RST? It's unexpected that there isn't even one table illustrating this algorithm.

By the definition above, it seems that RST here denotes adversarial training with unlabeled data, but it was proposed in Unlabeled data improves adversarial robustness by Carmon et al. in 2019.

What's the difference exactly?

Inspirations

It was great to see someone trying to analyze the tradeoff from different perspectives and the introduction made in this paper showing that it's possible to use RST (robust self-training) without losing much accuracy is also promising.

But the paper itself is too statistical, too many mathematical equations while failed to propose the algorithm or the method clearly....

It's also doubtful whether an analysis on the very simple linear regression can be generalized to the deep models.

Adversarial Example

Adversarial Examples from Computational Constraints - ICML 2019

Sébastien Bubeck, Eric Price, Ilya Razenshteyn. Adversarial examples from computational constraints. ICML 2019. arXiv:1805.10204

Why are classifiers in high dimension vulnerable to “adversarial” perturbations? We show that it is likely not due to information theoretic limitations, but rather it could be due to computational constraints.

Then we give a particular classification task where learning a robust classifier is computationally intractable.

It suggests that adversarial examples may be an unavoidable byproduct of computational limitations of learning algorithms.

Excessive Invariance Causes Adversarial Vulnerability - ICLR 2019

Jörn-Henrik Jacobsen, Jens Behrmann, Richard Zemel, Matthias Bethge. Excessive Invariance Causes Adversarial Vulnerability. ICLR 2019. arXiv:1811.00401

We show deep networks are not only too sensitive to task-irrelevant changes of their input, as is well-known from -adversarial examples, but are also too invariant to a wide range of task-relevant changes, thus making vast regions in input space vulnerable to adversarial attacks.

To this end, we introduce the concept of invariance-based adversarial examples and show that class-specific content of almost any input can be changed arbitrarily without changing activations of the network, as illustrated in figure 1 for ImageNet.

The same activation corresponds to many different inputs, therefore, the activations are not even discriminative......

The invariance perspective suggests that adversarial vulnerability is a consequence of narrow learning, yielding classifiers that rely only on few highly predictive features in their decisions.

They point out a complement form of commonly defined adversarial example, i.e. it can also be crafted by keeping the activation unchanged while the content changed drastically.

Two complementary approaches to adversarial examples

Definition 1 (Pre-images / Invariance). Let $F:\R^d\to\R^C$ be a neural network, $F=f_L\circ\cdots f_1$ with layers $f_i$ and let $F_i$ denote the network up to layer $i$. Further, let $D:\R^d\to\{1,\dots,C\}$ be a classifier with $D=\arg\max_{k=1,\dots,C} softmax(F(x))_k$. Then for input $x\in\R^d$, we define the following pre-images

• (i) $i$-th Layer pre-image: $\{x^{*}\in\R^d|F_i(x^{*})=F_i(x)\}$
• (ii) Logit pre-image: $\{x^{*}\in\R^d|F(x^*)=F(x)\}$
• (iii) Argmax pre-image: $\{x^{*}\in\R^d|D(x^*)=D(x)\}$

where $(i)\sub (ii)\sub(iii)$ by the compositional nature $D$.

Moreover, the (sub-)network is invariant to perturbation $\Delta x$ which satisfy $x^*=x+\Delta x$.

Invariance corresponds to the perturbation that may change the semantic meaning, yet not change the prediction of neural network. The fooling image should stem from the invariance of neural network.

The oracle is a human decision-maker or the unknown input-output function considered in learning theory.

Definition 2 (Perturbation-based Adversarial Examples). A Perturbation-based adversarial example $x^*\in\R^d$ of $x\in\R^d$ fulfills:

• Perturbation of decision: $D(x^*)\neq o(x^*)$ and $D(x)\neq D(x^*)$, where $D:\R^d\to\{1,\dots,C\}$ is the classifier and $o:\R^d\to\{1,\dots,C\}$ is the oracle.
• Created by adversary: $x^*\in\R^d$ is created by an algorithm $\mathcal{A}:\R^d\to\R^d$ with $x\mapsto x^*$.

Further, $\epsilon$-bounded adversarial example $x^*$ of $x$ fulfill $||x-x^*||\le \epsilon$, $||\cdot||$ a norm on $\R^d$ and $\epsilon>0$.

This is the generally used definition of an adversarial example.

Definition 3 (Invariance-based Adversarial Examples). Let $G$ denote the $i$-th layer, logits or the classifier (Definition 1) and let $x^*\neq x$ be in the $G$ pre-image of $x$ and $o$, an oracle (Definition 2). Then, an invariance-based adversarial example fulfills $o(x)\neq o(x^*)$, while $G(x)=G(x^*)$ and $D(x)=D(x^*)$.

Intuitively, adversarial perturbations cause the output of the classifier to change while the oracle would still consider the new input $x^*$ as being from the original class.

The perturbation-based adversarial examples indicate that the classifier is too sensitive to task-irrelevant changes, while the invariance-based adversarial examples indicate that the classifier is too insensitive to task-relevant changes.

In an unconstrained attack space, these two adversarial examples yield the same input $x^*$ via

with different reference points $x_1$ and $x_2$, as shown in Figure 2.

Definition 4 (Semantic/Nuisance perturbation of an input). Let $o$ be an oracle (Definition 2) and $x\in \R^d$. Then, a perturbation $\Delta x$ of an input $x\in\R^d$ is called semantic, if $o(x)\neq o(x+\Delta x)$ and nuisance if $o(x)=o(x+\Delta x)$.

For example, such a nuisance perturbation could be a translation or occlusion in image classification.

The nuisance adversarial example is the generally defined adversarial example, while semantic adversarial example changes the meaning of example, can be viewed as a generative result.

Using bijective networks to analyze excessive invariance

We need a generic approach that gives us access to the discarded nuisance variability.

They remove the final linear mapping onto the class probes in invertible RevNet-classifiers and call these networks fully invertible RevNets to gain access to their decision space.

The fully invertible RevNet classifier can be written as

where $F_{\theta}$ represents the bijective neural network.

They denote $z=F_{\theta}(x),z_s=z_{1,\dots,C}$ as the logits (semantic variables) and $z_n=z_{C+1,\dots, d}$ as the nuisance variables ($z_n$ is not used for classification).

In practice they choose the first $C$ indices of the final $z$ tensor or apply a more sophisticated DCT scheme.

Due to its simple readout structure, the resulting invertible network allows to qualitatively and quantitatively investigate the task-specific content in nuisance and logit variables.

Analytic attack

The heuristic metameric sampling is obtained by computing $x_{met}=F^{-1}(z_s,\tilde{z}_n)$, where $z_s$ and $\tilde{z}_n$ are taken from two different inputs.

The samples would be from the true data distribution if the subspaces would be factorized as $P(z_s,z_n)=P(z_s)P(z_n)$.

Metameric sampling gives us an analytic tool to inspect dependencies between semantic and nuisance variables without the need for expensive and approximate optimization procedures.

Attack on adversarial spheres

First, we evaluate our analytic attack on the synthetic spheres dataset, where the task is to classify samples as belonging to one out of two spheres with different radii.

We densely sample points in a 2D subspace, following Gilmer et al. (2018b), to visualize two cases:

• 1) the decision-boundary on a 2D plane spanned by two randomly chosen data points,
• 2) the decision-boundary spanned by metameric sample $x_{met}$ and reference point $x$.

Most notably, the visualized failure is not due to a lack of data seen during training, but rather due to excessive invariance of the original classifier $D$ on $z_s$.

Thus, the nuisance classifier on $z_n$ does not exhibit the same adversarial vulnerability in its subspace.

The nuisance variables are not used for classification, seems naturally immune to adversarial attacks?

Attack on MNIST and ImageNet

The result is striking, as the nuisance variables $z_n$ are dominating the visual appearance of the logit metamers, making it possible to attach any semantic content to any logit activation pattern.

The attack shows the same failures for non-bijective models. This result highlights the general relevance of our finding and poses the question of the origin of this excessive invariance, which we will analyze in the following section.

Independence Cross-entropy Loss

Let $(x,y)\sim\mathcal{D}$ with labels $y\in\{0,1\}^C$. Then the goal of a classifier can be stated as maximizing the mutual information between semantic features $z_s$(logits) extracted by network $F_{\theta}$ and labels $y$, denoted by $I(y;z_s)$.

They introduce the concept of an adversarial distribution shift $\mathcal{D}_{Adv}\neq\mathcal{D}$ to formalize these modifications brought by these perturbations.

Their first assumption is

i.e. the nuisance variables $z_n$ do not become more informative about $y$.

Thus, the distribution shift may reduce the predictiveness of features encoded in $z_s$, but does not introduce or increase the predictive value of variations captured in $z_n$.

Their second assumption is

It corresponds to positive or zero interaction information.

Knowing $z_n$ does not provide more information about $y$.

Bijective networks $F_{\theta}$ capture all variations by design, i.e. preserves information

Consider the reformulation

by the chain rule of mutual information.

It offers two ways forward:

• Direct increase of $I(y;z_s)$
• Indirect increase of $I(y;z_s|z_n)$ via decreasing $I(y;z_n)$

In a general classification task, only $I(y;z_s)$ is actively increased, which is sufficient in most cases, but may fail under $\mathcal{D}_{Adv}$.

Definition 5 (Independence cross-entropy loss). Let $F_{\theta}:\R^d\to\R^d$ a bijective network with parameters $\theta\in\R^{p_1}$ and $\tilde{F}_{\theta}(x)=softmax(F_{\theta}(x)_{1,\dots,C})$. Furthermore, let $D_{\theta_{nc}}:\R^{d-C}\to[0,1]^C$ be the nuisance classifier with $\theta_{nc}\in\R^{p_2}$. Then, the independence cross-entropy loss is defined as

The minimization of the nuisance classification loss $\mathcal{L}_{nCE}$ aims to tighten a lower bound on $I_{\mathcal{D}}(y;z_n)$.

The second term is designed to decrease the mutual information between the target label and nuisance predictions.

Theorem 6 (Information $I_{\mathcal{D}_{Adv}}(y;z_s)$ maximal after distribution shift). Let $\mathcal{D}_{Adv}$ denote the adversarial distribution and $\mathcal{D}$ the training distribution. Assume $I_{\mathcal{D}}(y;z_n)=0$ by minimizing $\mathcal{L}_{iCE}$ and the distribution shift satisfies $I_{\mathcal{D}_{Adv}}(z_n;y)\le I_{\mathcal{D}}(z_n;y)$ and $I_{\mathcal{D}_{Adv}}(y;z_s|z_n)\le I_{\mathcal{D}_{Adv}}(y;z_s)$. Then

Thus, incorporating the nuisance classifier allows for the discussed indirect increase of $I_{\mathcal{D}_{Adv}}(y;z_s)$.

To aid stability, they add a maximum likelihood term to their independence cross-entropy objective, the final term becomes

where $\det (J_{\theta}^x)$ denotes the determinant of the Jacobian of $F_{\theta}(x)$ and $p_k\sim\mathcal{N}(\beta_k,\gamma_k)$ with learned parameters $\beta_k,\gamma_k$.

Just as in GANs the quality of the result relies on a tight bound provided by the nuisance classifier and convergence of the MLE term.

Experiments

In this section, we show that our proposed independence cross-entropy loss is effective in reducing invariance-based vulnerability in practice by comparing it to vanilla cross-entropy training in four aspects:

• (1) error on train and test set,
• (2) effect under distribution shift, perturbing nuisances via metameric sampling,
• (3) evaluate accuracy of a classifier on the nuisance variables to quantify the class-specific information in them and
• (4) on our newly introduced shiftMNIST, an augmented version of MNIST to benchmark adversarial distribution shifts according to Theorem 6.

The CE-trained network allows us to transform any image into any class without changing the logits. However, when training with our proposed iCE, the picture changes fundamentally and interpolations in the pre-image only change the style of a digit, but not its semantic content.

To further test the efficacy of our proposed independence cross-entropy, we introduce a simple, but challenging new dataset termed shiftMNIST to test classifiers under adversarial distribution shifts.

The dataset is based on vanilla MNIST, augmented by introducing additional, highly predictive features at train time that are randomized or removed at test time.

It turns out that this task is indeed very hard for standard classifiers and their tendency to become excessively invariant to semantically meaningful features, as predicted by our theoretical analysis.

When trained with cross-entropy, ResNets and fi-RevNets make zero errors on the train set, while having error rates of up to 87% on the shifted test set.

When applying our independence cross-entropy, the picture changes again. The errors made by the network improve by up to almost 38% on binary shiftMNIST and around 28% on textured shiftMNIST.

Inspirations

This paper presents an important complementary type of adversarial examples, pointing out that invariance to semantically meaningful features also leads to weak adversarial robustness to the model.

The basic idea is the same as that in fooling image, but they rephrase it into an easy term and make more theoretically sound analysis. They further propose a new loss and experiments show its effectiveness, although I see it as a little fuzzy.

It's a promising direction to combine bijective network and adversarial robustness.

Hold me tight! Influence of discriminative features on deep network boundaries - NIPS 2020

Code: https://github.com/LTS4/hold-me-tight

Guillermo Ortiz-Jimenez, Apostolos Modas, Seyed-Mohsen Moosavi-Dezfooli, Pascal Frossard. Hold me tight! Influence of discriminative features on deep network boundaries. NIPS 2020. arXiv:2002.06349

In this work, we borrow tools from the field of adversarial robustness, and propose a new perspective that relates dataset features to the distance of samples to the decision boundary.

Finally, we show that the construction of the decision boundary is extremely sensitive to small perturbations of the training samples, and that changes in certain directions can lead to sudden invariances in the orthogonal ones.

Clearly, reaching the boundary using high frequency perturbations requires much more energy than using low frequency ones [7].

But surprisingly, when the network is adversarially trained [5], the largest increase in margin happens in the high frequency subspace.

Adversarial training dramatically increase the robustness of model against high frequency perturbations.

They intend to answer two questions in this paper:

• How is the margin in different directions related to the features in the training data?
• How can very small perturbations significantly change the geometry of deep networks?

Proposed framework

For a neural network

where $f_k(x)$ is the $k$-th component of the logits of the network $f:\R^D\to\R^L$.

The decision boundary between classes $k$ and $l$ of a neural network is the set

In this work, they study the role of training set $\mathcal{T}=\{(x^{(i)},y^{(i)})\}_{i=0}^{N-1}$ on the boundary $\mathcal{B}(f)$.

Definition 1 (Minimal adversarial perturbations). Given a classifier $F$, a sample $x\in\R^D$, and a sub-region of the input $\mathcal{S}\sube\R^D$, we define the ($\ell_2$) minimal adversarial perturbation of $x$ in $\mathcal{S}$ as $\delta_{\mathcal{S}}(x)=\arg\min_{\delta\in\mathcal{S}}||\delta||_2,s.t.\ F(x+\delta)\neq F(x)$.

In general, $\delta(x)$ denotes $\delta_{\R^D}(x)$.

The minimal norm of adversarial perturbations reachable in the given region.

Definition 2 (Margin) The magnitude $||\delta_{\mathcal{S}}(x)||_2$ is the margin of $x$ in $\mathcal{S}$.

The main objective is to obtain a local summary of $\mathcal{B}(f)$ around a set of observation samples $\mathcal{O}=\{x^{(i)}\}_{i=0}^{M-1}$ by measuring their margin in a sequence of distinct subspaces $\{\mathcal{S}_j\}_{j=0}^{R-1}$.

Given a set of samples, the purpose is to obtain their distances to the boundary by constructing adversarial perturbations.

They use DeepFool attack for further research.

Margin and discriminative features

We want to show that neural networks only construct boundaries along discriminative features, and that they are invariant in every other direction.

Evidence on synthetic data

They generate a balanced training set $\mathcal{T}_1(\epsilon,\sigma)$ by independently sampling $N$ points $x^{(i)}=U(x_1^{(i)}\oplus x_2^{(i)})$, such that $x_1^{(i)}=\epsilon y^{(i)}$ and $x_2^{(i)}\sim\mathcal{N}(0,\sigma^2I_{D-1})$, where $\oplus$ denotes the concatenation operator, $\epsilon>0$ the feature size and $D=100$.

The labels $y^{(i)}$ are uniformly sampled from $\{-1,+1\}$. $U\in SO(D)$ is a random orthonormal matrix, multiplied to avoid an y possible bias of the classifier towards the canonical basis.

Note that this is a linearly separable dataset with a single discriminative feature parallel to $u_1$ (i.e., first row of $U$), and all other dimensions filled with non-discriminative noise.

They synthesize a dataset that only one discriminative feature is included.

To evaluate our hypothesis, we train a heavily overparameterized multilayer perceptron (MLP) with 10 hidden layers of 500 neurons using SGD (test: 100%)

They then calculate the margin statistics on

• the linearly separable direction $u_1$
• its orthogonal complement $\text{span }\{u_1\}^\bot$
• a fixed random subspace of dimension $S$, i.e. $\mathcal{S}_{rand}\sube\R^D$
• a fixed random subspace of the same dimensionality, but orthogonal to $u_1$, i.e. $\mathcal{S}_{orth}\sube\text{span }\{u_1\}^\bot$

As shown in Table 1

From these values we can see that along the direction where the discriminative feature lies, the margin is much smaller than in any other direction.

Evidence on real data

In our study, we train multiple networks on MNIST [25] and CIFAR-10 [26], and for ImageNet [27] we use several of the pretrained networks provided by PyTorch [28].

Let $W,H,C$ denote the width, height and number of channels of the images in those datasets respectively. They use the 2-dimensional discrete cosine transform (2D-DCT) basis of size $H\times W$ to generate the observation subspaces .

Let $\mathcal{D}\in\R^{H\times W\times H\times W}$ denote the 2D-DCT generating tensor, such that $\text{vec}(\mathcal{D}(i,j,:,:)\oplus I_{C})$ represents one basis element of the image space. The subspaces are generated by sampling $K\times K$ blocks from the diagonal of the DCT tensor using a sliding window with step-size $T:\mathcal{S}_j=\text{span }\{\text{vec} (\mathcal{D}(i\cdot T+k,j\cdot T+k,:,:)\oplus I_C),k=0,\dots,K-1\}$.