summaries: The authors study a principal component bias of deep linear neural networks when trained with gradient descent using a small learning rate. They show that when the network is sufficiently wide, deep linear networks behave like single layer linear networks during the first phase of training, where the rate of convergence is governed by the largest principled components of the data. It is further shown that at later stages of training, under some assumptions, the PC bias remains to some extent.

summaries: This work studies the training dynamics of over-parameterized deep linear networks. The authors propose the Principal Components bias (PC-bias) convergence pattern that characterizes the convergence behavior of deep linear networks training, which is supported by theoretical analysis and empirical results. This works also investigates the Learning Order Constancy effect (LOC-effect) and identified the connection between PC-bias and LOC-effect. Empirically, the authors also study several implications of PC-bias, including early stopping, convergence behavior under label noise, and provide interesting observations.

summaries: The paper studies the evolution of a deep over-parametrized linear network under gradient descent.  The main claim of the paper is that the convergence rate of the weights is faster along directions corresponding to the larger principal components of the data, at a rate governed by the singular values. The paper also supports its argument in an extensive experimental study.

summaries: The paper argues for the existence of the so-called “principal component bias” in the learning of deep wide nets, with the main focus on linear networks. This refers to the phenomenon that the learning that is associated with larger PCs of the data is typically faster. The paper does so via a theoretical analysis of the early stage of learning in linear nets and a series of experiments, involving both linear and nonlinear models.

abstractText: Recent work suggests that convolutional neural networks of different architectures 1 learn to classify images in the same order. To understand this phenomenon, we 2 revisit the over-parametrized deep linear network model. Our asymptotic analysis, 3 assuming that the hidden layers are wide enough, reveals that the convergence rate 4 of this model’s parameters is exponentially faster along directions corresponding 5 to the larger principal components of the data, at a rate governed by the singular 6 values. We term this convergence pattern the Principal Components bias (PC-bias). 7 We show how the PC-bias streamlines the order of learning of both linear and non8 linear networks, more prominently at earlier stages of learning. We then compare 9 our results to the spectral bias, showing that both biases can be seen independently, 10 and affect the order of learning in different ways. Finally, we discuss how the 11 PC-bias may explain some benefits of early stopping and its connection to PCA, 12 and why deep networks converge more slowly when given random labels. 13

title: Deep nets don’t learn via memorization

text:
Recent work suggests that convolutional neural networks of different architectures1 learn to classify images in the same order. To understand this phenomenon, we2 revisit the over-parametrized deep linear network model. Our asymptotic analysis,3 assuming that the hidden layers are wide enough, reveals that the convergence rate4 of this model’s parameters is exponentially faster along directions corresponding5 to the larger principal components of the data, at a rate governed by the singular6 values. We term this convergence pattern the Principal Components bias (PC-bias).7 We show how the PC-bias streamlines the order of learning of both linear and non-8 linear networks, more prominently at earlier stages of learning. We then compare9 our results to the spectral bias, showing that both biases can be seen independently,10 and affect the order of learning in different ways. Finally, we discuss how the11 PC-bias may explain some benefits of early stopping and its connection to PCA,12 and why deep networks converge more slowly when given random labels.13
1 Introduction14
The dynamics of learning in deep neural networks is an intriguing subject, not yet sufficiently15 understood. Diverse empirical data seems to support the hypothesis that neural networks start by16 learning a simple model, which then gains complexity as learning proceeds (Gunasekar et al., 2018;17 Soudry et al., 2018; Hu et al., 2020; Nakkiran et al., 2019; Gissin et al., 2019; Heckel & Soltanolkotabi,18 2019; Ulyanov et al., 2018; Valle-Perez et al., 2018). This phenomenon is sometimes called simplicity19 bias (Dingle et al., 2018; Shah et al., 2020).20
Recent work additionally shows that neural networks learn the training examples of natural datasets21 in a consistent order, and further impose a consistent order on the test set (Hacohen et al., 2020;22 Pliushch et al., 2021). Below we call this effect Learning Order Constancy (LOC). Currently, the23 characteristics of visual data, which may explain this consistently imposed order, remain unclear.24 Surprisingly, this universal order persists despite the variability introduced into the training of different25 models and architectures.26
To understand this phenomenon, we start by analyzing the deep linear network model (Saxe et al.,27 2013, 2019), defined by the concatenation of linear operators. While not a universal approximator, it28 is nevertheless trained by minimizing a non-convex objective function with a multitude of minima.29 The investigation of such networks is often employed to shed light on the learning dynamics when30 complex geometric landscapes are explored by GD (Fukumizu, 1998; Arora et al., 2018).31
In Section 2, we prove that the convergence of the weights of deep linear networks is governed32 by the eigendecomposition of the raw data in a phenomenon we term PC-bias. These asymptotic33 results, valid when the hidden layers are wide enough, can be seen as an extension of the known34 behavior of the single-layer convex linear model (Le Cun et al., 1991). Our work is closely related to35 (Saxe et al., 2013, 2019), where the deep linear model’s dynamics is analyzed as a function of the36 input and input-output statistics. Importantly, the analysis in (Saxe et al., 2013, 2019; Arora et al.,37
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
2018) incorporates the simplifying assumption that the data’s singular values are identical (whitened38 data), an assumption which unfortunately obscures the main result of our analysis – the direct39 dependence of convergence rate on the singular values of the data.40
In Section 3, we empirically show that this pattern of convergence is indeed observed in deep linear41 networks, validating the plausibility of our assumptions. We continue by showing that the LOC-effect42 in deep linear network is determined solely by their PC-bias. We prove a similar (weaker) result for43 the non-linear two-layer ReLU model introduced by Allen-Zhu et al. (2018), where this model is44 presented as a certain extension of NTK (Jacot et al., 2020). In this framework, convergence is fastest45 along the largest kernel’s principal components, a result related to the Spectral bias discussed below.46
In Section 4, we extend the study empirically to non-linear networks, and investigate the relation47 between the PC-bias and the LOC-effect in general deep networks. We first show that the order48 by which examples are learned by linear networks is highly correlated with the order induced by49 prevalent deep CNN models. We then show directly that the learning order of non-linear CNN models50 is affected by the principal decomposition of the data. Moreover, the LOC-effect diminishes when51 data is whitened, indicating a tight connection between the PC-bias and the LOC-effect.52
Our results are reminiscent of another phenomenon, termed Spectral bias (Rahaman et al., 2019;53 Cao et al., 2019), which associates the learning dynamics of neural networks with the Fourier54 decomposition of functions in the hypothesis space. Rahaman et al. (2019) empirically demonstrated55 that the complexity of classifiers learned by ReLU networks increases with time. Basri et al. (2019,56 2020) showed theoretically, by way of analyzing elementary neural network models, that these models57 first fit the data with low-frequency functions, and gradually add higher frequencies to improve the fit.58
Nevertheless, the spectral bias and PC-bias are inherently different. Indeed, the eigendecomposition59 of raw images is closely related to the Fourier analysis of images as long as the statistical properties60 of images are (approximately) translation-invariant (Simoncelli & Olshausen, 2001; Torralba & Oliva,61 2003). Still, the PC-bias is guided by spectral properties of the raw data and is additionally blind to62 class labels. On the other hand, the spectral bias, as well as the related frequency bias that has been63 shown to characterize NTK models (Basri et al., 2020), are all guided by spectral properties of the64 learned hypothesis, which strongly depends on label assignment.65
In Section 4.3 we investigate the relation between the PC-bias, spectral bias, and the LOC-effect.66 We find that the LOC-effect is very robust: (i) when we neutralize the spectral bias by using low67 complexity models such as deep linear networks, the effect is still observed; (ii) when we neutralize68 the PC-bias by using whitened data, the LOC-effect persists. We hypothesize that at the beginning of69 learning, the learning dynamics of neural models is controlled by the eigendecomposition of the raw70 data. As learning proceeds, control of the dynamics slowly shifts to other factors.71
The PC-bias has implications beyond the LOC-effect, as expanded in Section 5 and Suppl. §A:72
1. Early stopping. It is often observed that when training deep networks with real data, the highest73 generalization accuracy is obtained before convergence. Consequently, early stopping is often74 prescribed to improve generalization. Following the commonly used assumption that in natural75 images the lowest principal components correspond to noise (Torralba & Oliva, 2003), our results76 predict the benefits of early stopping, and relate it to PCA. In Section 5 we investigate the relevance77 of this conclusion to real non-linear networks (see, e.g., Basri et al. (2019); Li et al. (2020) for78 complementary accounts).79
2. Slower convergence with random labels. Zhang et al. (2016) showed that neural networks80 can learn any label assignment. However, training with random label assignments is known to81 converge slower as compared to training with the original labels (Krueger et al., 2017). We report a82 similar phenomenon when training deep linear networks. Our analysis shows that when the principal83 eigenvectors are correlated with class identity, as is often the case in natural images, the loss decreases84 faster when given true label assignments as against random label assignments. In Section 5 we85 investigate this hypothesis empirically in linear and non-linear networks.86
3. Weight initialization. Different weight initialization schemes have been proposed to stabilize the87 learning and minimize the hazard of "exploding gradients" (e.g., Glorot & Bengio, 2010; He et al.,88 2015). Our analysis (see Suppl. §A) identifies a related variant, which eliminates the hazard when89 all the hidden layers are roughly of equal width. In the deep linear model, it can be proven that the90 proposed normalization variant in a sense minimizes repeated gradient amplification.91
2 Theoretical analysis92
Notations. Let X = {(xi,yi)}ni=1 denote the training data, where x ∈ Rq denotes the i-th data93 point and y ∈ {0, 1}K its corresponding label. Let 1nimi denote the centroid (mean) of class i with94 ni points, and M = [m1 . . .mK ]>. Finally, let X and Y denote the matrices whose ith column95 is xi and yi respectively. ΣXX = XX> and ΣY X = Y X> denote the covariance matrix of X96 and cross-covariance of X and Y respectively. We note that ΣXX captures the structure of the data97 irrespective of class identity.98
Definition 1 (Principal coordinate system). The coordinate system obtained by rotating the data in Rq99 by an orthonormal matrixU>, where SV D(ΣXX)=UDU>. Now ΣXX =D, a diagnoal matrix whose100 elements are the singular values of XX>, arranged in decreasing order d1 ≥ d2 ≥ . . . ≥ dq ≥ 0.101 Definition 2 (Compact representation). Let f(x) denote a deep linear network. Then f(x) =102 (∏1
l=LWl
) x = Wx, where W ∈ RK×q is called the compact representation of the network.103
Definition 3 (Error matrix). For a deep linear network whose compact representation is W , the104 error matrix is Er = WΣXX − ΣY X . In the principal coordinate system, Er = WD −M .105
Assumptions. Our analysis assumes that the learning rate µ is infinitesimal, and therefore terms106 of size O(µ2) can be neglected. We further assume that the width of the hidden layers lies in107 [m,m+Mb], wherem→∞ denotes a very large number and Mb is fixed. Thus terms of size O( 1m )108 can also be neglected. In Fig. 1 we show the plausibility of these assumptions, where the predicted109 dynamics is seen throughout the training of deep linear networks, even for small values ofm.110
2.1 The dynamics of deep over-parametrized linear networks111
Consider a deep linear network with L layers, and let112
L(X) = 1
2 ‖WX − Y ‖2F W := 1∏ l=L Wl, Wl ∈ Rml×ml−1 (1)
Above ml denotes the number of neurons in layer l, where m0 = q and mL = K.113 Theorem 1. In each time point s, the compact matrix representation W obeys the following dynamics,114 when using the notation Ers defined in Def. 3:115
W s+1 = W s − µ L∑ l=1 Asl · Ers ·Bsl +O(µ2) (2)
Above µ denotes the learning rate. Asl and B s l are called gradient scale matrices, and are defined as116
Asl := ( l+1∏ j=L W sj )( l+1∏ j=L W sj )> ∈ RK×K Bsl := ( 1∏ j=l−1 W sj )>( 1∏ j=l−1 W sj ) ∈ Rq×q (3)
The proof can be found in Suppl. §B.117
Gradient scale matrices. Some statistical properties of such matrices are established in Suppl. §A.118 Note that when the number of hidden layers is 0 (L = 1), both gradient scale matrices reduce to the119 identity matrix and the dynamics in (2) is reduced to the following known result (e.g., Le Cun et al.,120 1991): W s+1 = W s−µErs. Recall, however, that the focus of this paper is the over-parameterized121 linear model with L > 1, in which the loss is not convex. Since the difference between the convex122 linear model and the over-parametrized deep model boils down to these matrices, our convergence123 analysis henceforth focuses on the dynamics of the gradient scale matrices.124
In accordance, we analyze the evolution of the gradient scale matrices as learning proceeds. Let125 m = min (m1, ...,mL−1) denote the size of the smallest hidden layer. Initially for s = 0, all weight126 matrices W 0l are assumed to be initialized by sampling from a distribution with mean 0 and variance127 σ2l = O( 1 m ). The specific normalization factor, alluded to in O( 1 m
), is a variant of the Glorot128 initialization. Details and justification can be found in Suppl. §A.1.129
At time s, letAsl (m) andB s l (m) denote a sequence of random gradient scale matrices, corresponding130 to networks whose smallest hidden layer hasm neurons. From Suppl. §A we deduce that:131
Theorem 2. Using p−→ to denote convergence in probability asm→∞, and ∀s, l:132
Bsl (m) p−→ I, var[Bl(m)] = O
( 1
m
) Asl (m) p−→ I, var[Al(m)] = O ( 1
m ) Proof. Proof by induction on s. Initially when s = 0, the claim follows from Thm 4 and Corr 5.1.133 The induction step validity follows from Thm 6 and Thm 7 (see Suppl. §A.2).134
The detailed proof shows that the relevant constants are amplified with s. While they remain moderate135 andm is sufficiently large, Bsl (m) ≈ I and Asl (m) ≈ I ∀l. In this case, the dynamics of the over-136 parameterized model is identical to the dynamics of the convex linear model, W s+1 = W s − µErs.137 Convergence rate. In §A.2 we show that the convergence of Bsl (m) to I is governed to some extent138 by O ( K m ) , while the convergence of Asl (m) is governed by O ( q m ) . Recall that while m → ∞,139 q is the dimension of the data space which is fixed in advance and can be fairly large, while K is140 the number of classes which is fixed and quite small. Typically, K q. Thus we expect the right141 gradient scale matrices Bsl (m) to remain approximately I much longer than the left matrices A s l (m).142
Empirical validation. Since the results above are asymptotic, and to envision the difference between143 convergence governed by O ( K m ) vs. O ( q m ) , we resort to simulations whose results are shown in144 Fig. 1. These empirical results, recounting linear networks with 4 hidden layers of width 1024, clearly145 show that during a significant part of the training both gradient scale matrices remain approximately146 I . The difference between the convergence rate of Bsl and A s l is seen later on, when ∆A s l starts to147 increase shortly before convergence, while ∆Bsl remains essentially 0 throughout.148
2.2 Weight evolution149
K q entails that Bsl (m) remains approximately equal to I much longer than Asl (m). This is150 substantiated by the simulation results in Fig. 1. Consequently, while earlier on it is safe to assume151 that both Asl ≈ I and Bsl ≈ I , as learning proceeds only Bsl ≈ I is safe to assume.152 With this in mind, we obtain expressions for the evolution of W s separately for earlier and later in153 learning. We first shift to the principal coordinate system defined in Def 1. In this system we can154 analyze each column of W s separately, where wsj and mj denote the respective columns of W
s and155 M . At the beginning of learning when both Asl ≈ I and Bsl ≈ I (see §B.3 for a detailed derivation):156
ws+1j = (λj) sw0j + [1− (λj)s] mj dj
λj = 1− µdjL (4) 157 Eq. 4 is reminiscent of the well understood dynamics of training the convex one layer linear model. It158 is composed of two additive terms, revealing two parallel and independent processes:159
1. The dependence on random initialization tends to 0 exponentially with decline rate λj .160 2. The final value is the sum of a geometrical series with a common ratio λj .161
In either case, convergence is fastest for the largest singular eigenvalue, or the first column of W ,162 and slowest for the smallest singular value. This behavior is visualized in Fig. 2a. Importantly, the163 rate of convergence depends on the singular value dj , the number of layers L, and the learning rate µ.164
In later stages of learning, when we can only assume that Bsl ≈ I , the dynamic becomes:165
ws+1j = s∏ ν=1 (I − µdjAν)w0j + µ
[ s∑
ν=1 s∏ ρ=ν+1
(I − µdjAρ)Aν ] mj (5)
where As = ∑L l=1A s l . The proof is provided in §B.3. Although the dynamics now depends on166 matrices As as well, it is still the case that the convergence of each column is governed by its singular167 value dj . This suggests that while the PC-bias is more pronounced in earlier stages of learning, its168 effect persists throughout.169
The analysis above is extended to a simple non-linear ReLU model (cf. Arora et al., 2019) as detailed170 in §B.2, with qualitatively similar results (albeit under unrealistic assumptions). Empirical results,171 shown in Fig. 2b, indicate that the results are indicative beyond the assumed circumstances.172
3 PC-bias: empirical study173
In this section, we first analyze deep linear networks, showing that the convergence rate is indeed174 governed by the principal singular values of the data, which demonstrates the plausibility of the175 assumptions made in Section 2. We continue by extending the scope of the investigation to non-linear176 neural networks, finding there evidence for the PC-bias mostly in the earlier stages of learning.177
3.1 Methodology178
We say that a linear network is L-layered when it has L − 1 hidden fully connected (FC) layers179 (without convolutional layers). In our empirical study we relaxed some assumptions of the theoretical180 study, in order to increase the resemblance of the trained networks to networks in common use.181 Specifically, we changed the initialization to the commonly used Glorot initialization, replaced the182 L2 loss with the cross-entropy loss, and employed SGD instead of the deterministic GD. Notably,183 the original assumptions yielded similar results. The results presented summarize experiments with184 networks of equal width across all hidden layers, specifically the moderate value of m = 1024,185 keeping in mind that we test the relevance of asymptotic results form→∞. Using a different width186 for each layer yielded similar qualitative results. Details regarding the hyper-parameters, architectures,187 and datasets can be found in §D.1, §D.3 and §D.4 respectively.188
3.2 PC-bias in deep linear networks189
In this section, we train L-layered linear networks, then compute their compact representations190 W rotated to align with the canonical coordinate system (Def. 1). Note that each row wr in W191 essentially defines the one-vs-all separating hyper-plane corresponding to class r.192
To examine both the variability between models and their convergence rate, we inspect wr at different193 time points during learning. The rate of convergence can be measured directly, by observing the194 changes in the weights of each element in wr. These weight values1 should be compared with195 the optimal values in each row wr of Wopt = Y XT (XXT ). The variability between models is196 measured by calculating the standard deviation (std) of each wr across N models.197
We begin with linear networks. We trained 10 5-layered FC linear networks, and 10 linear st-VGG198 convolutional networks. When analyzing the compact representation of such networks we observe199 similar behavior – weights corresponding to larger principal components converge faster to the200 optimal value, and their variability across models converges faster to 0 (Figs. 3a,3b). Thus, while the201 theoretical results are asymptotic, PC-bias is empirically seen throughout the entire learning process202 of deep linear networks.203
Whitened data. The PC-bias is neutralized when the data is whitened, at which point ΣXX is the204 scaled identity matrix. In Fig. 3c, we plot the results of the same experimental protocol while using a205 ZCA-whitened dataset. As predicted, the networks no longer show any bias towards any principal206 direction. Weights in all directions are scaled similarly, and the std over all models is the same in207 each epoch, irrespective of the principal direction. (Additional experiments show that this is not an208 artifact of the lack of uniqueness when deriving the principal components of a white signal).209
1We note that the weights tend to start larger for smaller principal components, as can be seen in Fig. 3a left.
3.3 PC-bias in general CNNs210
In this section, we investigate the manifestation of the PC-bias in non-linear deep convolutional211 networks. As we cannot directly track the learning dynamics separately in each principal direction of212 non-linear networks, we adopt two different evaluation mechanisms:213
Linear approximation. We considered several linear approximations, but since all of them showed214 the same qualitative behavior, we report results with the simplest one. Specifically, to obtain a linear215 approximation of a non-linear network, without max-pooling or batch-normalization layers, we216 follow the definition of the compact representation from Section 2 while ignoring any non-linear217 activation. We then align this matrix with the canonical coordinate system (Def. 1), and observe the218 evolution of the weights and their std across models along the principal directions during learning.219 Note that now the networks do not converge to the same compact representation, which is not unique.220 Nevertheless, we see that the PC-bias governs the weight dynamics to a noticeable extent.221
More specifically, in these networks a large fraction of the lowest principal components hardly changes222 during learning, as good as being ignored. Nevertheless, the PC-bias affects the higher principal223 components, most notably at the beginning of training (see Fig. 3d). Thus weights corresponding to224 higher principal components converge faster, and the std across models of such weights decreases225 faster for higher principal components.226
Projection to higher PC’s. We created a modified test-set, by project-227 ing each test example on the span of the first P principal components.228 This is equivalent to reducing the dimensionality of the test set to P us-229 ing PCA. We trained an ensemble of N=100 st-VGG networks on the230 original small mammals training set, then evaluated these networks dur-231 ing training on 4 versions of the test-set, reduced to P=1,10,100,1000232 dimensions respectively. Mean accuracy is plotted in Fig. 4. Similar233 results are obtained when training VGG-19 networks on CIFAR-10,234 see §C.3.235
Taking a closer look at Fig. 4, we see that when evaluated on lower236 dimensionality test-data (P=1,10), the networks’ accuracy peaks after237
a few epochs, at which point performance starts to decrease. This result suggests that the networks238 rely more heavily on these dimensions in the earlier phases of learning, and then continue to learn239 other things. In contrast, when evaluated on higher dimensionality test-data (P=100,1000), accuracy240 continues to rise, longer so for larger P . This suggests that significant learning of the additional241 dimensions continues in later stages of the learning.242
4 PC-bias: Learning Order Constancy243
In this section, we show that the PC-bias is significantly correlated with the learning order of deep244 neural networks, and can therefore partially account for the LOC-effect described in Section 1.245 Following Hacohen et al. (2020), we measure the "speed of learning" of each example by computing246 its accessibility score. This score is given per example, and characterizes how fast an ensemble of247 N networks learns it. Formally, accessibility(x) = E [1(fei (x) = y(x))], where fei (x) denotes248 the outcome of the i-th network trained over e epochs, and the mean is taken over networks and249 epochs. For the set of datapoints {(xj ,yj)}nj=1, Learning Order Constancy is manifested by the high250 correlation between 2 instances of accessibility(x), each computed from a different ensemble.251
PC-bias is shown to pertain to LOC in two ways: First, in Section 4.1 we show high correlation252 between the learning order in deep linear and non-linear networks. Since the PC-bias fully accounts253 for LOC in deep linear networks, this suggests it also accounts (at least partially) for the observed254 LOC in non-linear networks. Comparison with the critical principal component verifies this assertion.255 Second, we show in Section 4.2 that when the PC-bias is neutralized, LOC diminishes as well. In256 Section 4.3 we discuss the relationship between the spectral bias, PC-bias and the LOC-effect.257
4.1 PC-Bias is correlated with LOC258
We first compare the order of learning of non-linear models and deep linear networks by computing259 the correlation between the accessibility scores of both models. This comparison reveals high260 correlation (r = 0.85, p < 10−45), as seen in Fig. 5a. To investigate directly the connection between261 the PC-bias and LOC, we define the critical principal component of an example to be the first262 principal component P , such that a linear classifier trained on the original data can classify the263 example correctly when projected to P principal components. We trained N=100 st-VGG networks264 on the cats and dogs dataset, and computed for each example its accessibility score and critical265 principal component. In Fig. 5b we see strong negative correlation between the two scores (p=−0.93,266 r<10−4), suggesting that the PC-bias affects the order of learning as measured by accessibility.267
4.2 Neutralizing the PC-bias leads to diminishing LOC268
Whitening the data eliminates the PC-bias as shown in Fig. 3c, since all the singular values are now269 identical. Here we use this observation to further probe into the dependency of the Learning Order270 Constancy on the PC-bias. Starting with the linear case, we train 4 ensembles of N=10 2-layered271 linear networks on the cats and dogs dataset, 2 with and 2 without ZCA-whitening. We compute the272 accessibility score for each ensemble separately, and correlate the scores of the 2 ensembles in each273 test case. Each correlation captures the consistency of the LOC-effect for the respective condition.274 This correlation is expected to be very high for natural images. Low correlation implies that the275 LOC-effect is weak, as training the same network multiple times yields a different learning order.276
2As non-linear models achieve the accuracy of linear models within an epoch or 2, low learning rate is used.
Fig. 6a shows the results for deep linear networks. As expected, the correlation when using natural277 images is very high. However, when using whitened images, correlation plummets, indicating that278 the LOC-effect is highly dependent on the PC-bias. We note that the drop in the correlation is much279 higher when considering only the 20% "fastest learned" examples, suggesting that the PC-bias affects280 learning order more evidently at earlier stages of learning.281
Fig. 6b shows the results when repeating this experiment with non-linear networks, training 2282 collections of N=10 VGG-19 networks on CIFAR-10. We find that the elimination of the PC-bias283 in this case affects LOC much less, suggesting that the PC-bias can only partially account for the284 LOC-effect in the non-linear case. However, we note that at the beginning of learning, when the285 PC-bias is most pronounced, once again the drop is much larger and very significant (half).286
4.3 Spectral bias, PC-bias and LOC287
The spectral bias (Rahaman et al., 2019) characterizes the dynamics of learning in neural networks288 differently, asserting that initially neural models can be described by low frequencies only. This may289 provide an alternative explanation to LOC. Recall that LOC is manifested in the consistency of the290 accessibility score across networks. To compare between the spectral bias and accessibility score,291 we first need to estimate for each example whether it can be correctly classified by a low frequency292 model. Accordingly, we define for each example a discriminability measure – the percentage out293 of its k neighbors that share with it class identity. Intuitively, an example has a low discriminability294 score when it is surrounded by examples from other classes, which forces the learned boundary to295 incorporate high frequencies. In §C.2 we show that in the 2D case analyzed by Rahaman et al. (2019),296 this measure strongly correlates (r=−0.8, p < 10−2) with the spectral bias.297 We trained several networks (VGG-19 and st-VGG) on several real datasets, including small-298 mammals, STL-10, CIFAR-10/100 and a subset of ImageNet-20. For each network and dataset,299 we computed the accessibility score as well as the discriminability of each example. The vector300 space, in which discriminability is evaluated, is either the raw data or the network’s perceptual space301 (penultimate layer activation). The correlation between these scores is shown in Table 1.302
Using raw data, low correlation is still seen between the accessibility and discriminability scores303 when inspecting the smaller datasets (small mammals, CIFAR-100 and STL10). This correlation304 vanishes when considering the larger ImageNet-20 dataset. It would appear that on its own, the305 spectral bias cannot adequately explain the LOC-effect. On the other hand, in the perceptual space,306 the correlation between discriminability and accessibility is quite significant for all datasets. Contrary307 to our supposition, it seems that networks learn a representation where the spectral bias is evident,308 but this bias does not necessarily govern its learning before the representation has been learned.309
5 PC-bias: further implications310
Early Stopping and the Generalization Gap. Considering natural images, it is often assumed that311 the least significant principal components of the data represent noise (Torralba & Oliva, 2003). In312 such cases, our analysis predicts that as noise dominates the components learned later in learning,313 early stopping is likely to be beneficial. To test this hypothesis directly, we manipulated CIFAR-10314 to amplify the signal in either the 1.5% most significant (higher) or 1.5% least significant (lower)315 principal components (see examples in Fig. 16, Suppl. §D). Accuracy over the original test set,316 after training 10 st-VGG and linear st-VGG networks on these manipulated images, can be seen317 in Fig. 7. Both in linear and non-linear networks, early stopping is more beneficial when lower318
principal components are amplified, and significantly less so when higher components are amplified,319 as predicted by the PC-bias.320
Slower Convergence with Random Labels. Deep neural models can learn any random label321 assignment to a given training set (Zhang et al., 2016). However, when trained on randomly labeled322 data, convergence appears to be much slower (Krueger et al., 2017). Assume, as before, that in natural323 images the lower principal components are dominated by noise. We argue that the PC-bias now324 predicts this empirical result, since learning randomly labeled examples requires signal present in325 lower principal components. To test this hypothesis directly, we trained 10 2-layered linear networks326 on datasets of natural images. Indeed, these networks converge slower with random labels (see327 Fig. 8a). In Fig. 8b we repeat this experiment after having whitened the images, to neutralize the328 PC-bias. Now convergence rate is identical, whether the labels are original or shuffled. Clearly, in329 deep linear networks the PC-bias gives a full account of this phenomenon.330
To further check the relevance of this account to non-linear networks, we artificially generate datasets331 where only the first P principal components are discriminative, while the remaining components332 become noise by design. We constructed two such datasets: in one the labels are correlated with the333 original labels, in the other they are not. Specifically, PCA is used to reduce the dimensionality of a334 two-class dataset to P , and the optimal linear separator in the reduced representation is computed.335 Next, all the labels of points that are incorrectly classified by the optimal linear separator are switched,336 so that the train and test sets are linearly separable by this separator. Note that the modified labels337 are still highly correlated with the original labels (for P = 500: p = 0.82, r < 10−10). The338 second dataset is generated by repeating the process while starting from randomly shuffled labels.339 This dataset is likewise fully separable when projected to the first P components, but its labels are340 uncorrelated with the original labels (for P = 500: p = 0.06, r < 10−10).341
The mean training accuracy of 10 non-linear networks with P=10,50,500 is plotted in Fig. 9a (first342 dataset) and Fig. 9b (second dataset). In both cases, the lower P is (namely, only the first few principal343 components are discriminative), the faster the data is learned by the non-linear network. Whether the344 labels are real or shuffled makes little qualitative difference, as predicted by the PC-bias.345
6 Summary and discussion346
When trained with gradient descent, the convergence rate of the over-parameterized deep linear347 network model is provably governed by the eigendecomposition of the data, and specifically, pa-348 rameters corresponding to the most significant principal components converge faster than the least349 significant components. Empirical evidence is provided for the relevance of these results to more350 realistic non-linear networks. We term this effect PC-bias. This result provides a complementary351 account for some prevalent empirical observations, including the benefit of early stopping and the352 slower convergence rate with shuffled labels.353
We use the PC-bias to explicate the Learning Order Constancy (LOC), showing that examples354 learned at earlier stages are more distinguishable by the higher principal components, demonstrating355 that networks’ training relies more heavily on higher principal components early on. A causal link356 between the PC-bias and the LOC-effect is demonstrated, as the LOC-effect diminishes when the357 PC-bias is eliminated by whitening the images. We analyze these findings in view of a related358 phenomenon termed spectral bias. While the PC-bias may be more prominent early on, the spectral359 bias may be more important in later stages of learning.360
References361 Allen-Zhu, Z., Li, Y., and Liang, Y. Learning and generalization in overparameterized neural362 networks, going beyond two layers. arXiv preprint arXiv:1811.04918, 2018.363
Arora, S., Cohen, N., and Hazan, E. On the optimization of deep networks: Implicit acceleration by364 overparameterization. In International Conference on Machine Learning, pp. 244–253, 2018.365
Arora, S., Du, S., Hu, W., Li, Z., and Wang, R. Fine-grained analysis of optimization and generaliza-366 tion for overparameterized two-layer neural networks. In International Conference on Machine367 Learning, pp. 322–332, 2019.368
Basri, R., Jacobs, D. W., Kasten, Y., and Kritchman, S. The convergence rate of neural networks for369 learned functions of different frequencies. In Advances in Neural Information Processing Systems,370 pp. 4761–4771, 2019.371
Basri, R., Galun, M., Geifman, A., Jacobs, D., Kasten, Y., and Kritchman, S. Frequency bias in neural372 networks for input of non-uniform density. In International Conference on Machine Learning, pp.373 685–694. PMLR, 2020.374
Cao, Y., Fang, Z., Wu, Y., Zhou, D.-X., and Gu, Q. Towards understanding the spectral bias of deep375 learning. arXiv preprint arXiv:1912.01198, 2019.376
Dingle, K., Camargo, C. Q., and Louis, A. A. Input–output maps are strongly biased towards simple377 outputs. Nature communications, 9(1):1–7, 2018.378
Fukumizu, K. Effect of batch learning in multilayer neural networks. Gen, 1(04):1E–03, 1998.379
Gissin, D., Shalev-Shwartz, S., and Daniely, A. The implicit bias of depth: How incremental learning380 drives generalization. arXiv preprint arXiv:1909.12051, 2019.381
Glorot, X. and Bengio, Y. Understanding the difficulty of training deep feedforward neural networks.382 In Proceedings of the thirteenth international conference on artificial intelligence and statistics,383 pp. 249–256, 2010.384
Gunasekar, S., Lee, J., Soudry, D., and Srebro, N. Implicit bias of gradient descent on linear385 convolutional networks. arXiv preprint arXiv:1806.00468, 2018.386
Hacohen, G., Choshen, L., and Weinshall, D. Let’s agree to agree: Neural networks share classification387 order on real datasets. In International Conference on Machine Learning, pp. 3950–3960. PMLR,388 2020.389
He, K., Zhang, X., Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing human-level390 performance on imagenet classification. In Proceedings of the IEEE International Conference on391 Computer Vision (ICCV), December 2015.392
Heckel, R. and Soltanolkotabi, M. Denoising and regularization via exploiting the structural bias of393 convolutional generators. arXiv preprint arXiv:1910.14634, 2019.394
Hu, W., Xiao, L., Adlam, B., and Pennington, J. The surprising simplicity of the early-time learning395 dynamics of neural networks. arXiv preprint arXiv:2006.14599, 2020.396
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in397 neural networks, 2020.398
Krueger, D., Ballas, N., Jastrzebski, S., Arpit, D., Kanwal, M. S., Maharaj, T., Bengio, E., Fischer, A.,399 and Courville, A. Deep nets don’t learn via memorization. 2017.400
Le Cun, Y., Kanter, I., and Solla, A. S. Second order properties of error surfaces learning time and401 generalization. Advances in neural information processing systems, 3:918–924, 1991.402
Li, M., Soltanolkotabi, M., and Oymak, S. Gradient descent with early stopping is provably robust403 to label noise for overparameterized neural networks. In International Conference on Artificial404 Intelligence and Statistics, pp. 4313–4324. PMLR, 2020.405
Nakkiran, P., Kaplun, G., Kalimeris, D., Yang, T., Edelman, B. L., Zhang, F., and Barak, B. Sgd406 on neural networks learns functions of increasing complexity. arXiv preprint arXiv:1905.11604,407 2019.408
Pliushch, I., Mundt, M., Lupp, N., and Ramesh, V. When deep classifiers agree: Analyzing409 correlations between learning order and image statistics. arXiv preprint arXiv:2105.08997, 2021.410
Rahaman, N., Baratin, A., Arpit, D., Draxler, F., Lin, M., Hamprecht, F., Bengio, Y., and Courville,411 A. On the spectral bias of neural networks. In International Conference on Machine Learning, pp.412 5301–5310. PMLR, 2019.413
Saxe, A. M., McClelland, J. L., and Ganguli, S. Exact solutions to the nonlinear dynamics of learning414 in deep linear neural networks. arXiv preprint arXiv:1312.6120, 2013.415
Saxe, A. M., McClelland, J. L., and Ganguli, S. A mathematical theory of semantic development in416 deep neural networks. Proceedings of the National Academy of Sciences, 116(23):11537–11546,417 2019.418
Shah, H., Tamuly, K., Raghunathan, A., Jain, P., and Netrapalli, P. The pitfalls of simplicity bias in419 neural networks. arXiv preprint arXiv:2006.07710, 2020.420
Simoncelli, E. P. and Olshausen, B. A. Natural image statistics and neural representation. Annual421 review of neuroscience, 24(1):1193–1216, 2001.422
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient423 descent on separable data. The Journal of Machine Learning Research, 19(1):2822–2878, 2018.424
Torralba, A. and Oliva, A. Statistics of natural image categories. Network: computation in neural425 systems, 14(3):391–412, 2003.426
Ulyanov, D., Vedaldi, A., and Lempitsky, V. Deep image prior. In Proceedings of the IEEE conference427 on computer vision and pattern recognition, pp. 9446–9454, 2018.428
Valle-Perez, G., Camargo, C. Q., and Louis, A. A. Deep learning generalizes because the parameter-429 function map is biased towards simple functions. arXiv preprint arXiv:1805.08522, 2018.430
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires431 rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.432
Checklist433
1. For all authors...434 (a) Do the main claims made in the abstract and introduction accurately reflect the paper’s435 contributions and scope? [Yes]436 (b) Did you describe the limitations of your work? [Yes]437 (c) Did you discuss any potential negative societal impacts of your work? [N/A]438 (d) Have you read the ethics review guidelines and ensured that your paper conforms to439 them? [Yes]440 2. If you are including theoretical results...441
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the442 "Assumptions" paragraph as Section 2443
(b) Did you include complete proofs of all theoretical results? [Yes] Each theorem reference444 to its proof. Proofs can be found in Suppl. §A,B445
3. If you ran experiments...446 (a) Did you include the code, data, and instructions needed to reproduce the main ex-447 perimental results (either in the supplemental material or as a URL)? [No] All data,448 instructions and hyper-parameters are explictly written in the main paper and/or in the449 Suppl. (see §D.4,D.4). The code itself will be provided once the anonymity will be450 lifted.451
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they452 were chosen)? [Yes]453
(c) Did you report error bars (e.g., with respect to the random seed after running experi-454 ments multiple times)? [Yes]455
(d) Did you include the total amount of compute and the type of resources used (e.g., type456 of GPUs, internal cluster, or cloud provider)? [N/A]457
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...458 (a) If your work uses existing assets, did you cite the creators? [Yes]459 (b) Did you mention the license of the assets? [N/A]460 (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]461
462
(d) Did you discuss whether and how consent was obtained from people whose data you’re463 using/curating? [N/A]464
(e) Did you discuss whether the data you are using/curating contains personally identifiable465 information or offensive content? [N/A]466
5. If you used crowdsourcing or conducted research with human subjects...467 (a) Did you include the full text of instructions given to participants and screenshots, if468 applicable? [N/A]469 (b) Did you describe any potential participant risks, with links to Institutional Review470 Board (IRB) approvals, if applicable? [N/A]471 (c) Did you include the estimated hourly wage paid to participants and the total amount472 spent on participant compensation? [N/A]473

title: Principal Components Bias in Deep Neural Networks


summaries: This paper observes that deep neural networks learn backdoored data faster than benign samples. Based on this finding, the paper proposes Anti-Backdoor Learning (ABL), which can learn a benign model on poisoned datasets. Specifically, at the beginning of model training, ABL maximizes the training loss gap between clean samples and backdoored examples and detects backdoored data based on the differences in their loss values. Then, ABL unlearns backdoored model with the detected data.

summaries: The proposed work identifies that backdoor attack examples converge fairly quickly compared to clean examples during training, due to the nature of their objective. Using this, the authors identify backdoor examples and use a gradient ascent method to unlearn the backdoor, while gradient descent is used for clean examples. The proposed method is shown to be effective in reducing Attack Success Rate (ASR) while increasing Clean Accuracy (CA) on multiple datasets and attacks.

summaries: Authors have introduced the concept of anti-backdoor learning to learn clean models using backdoor-poisoned data. They have proposed Anti-Backdoor Learning (ABL) to automatically break backdoor attack during training with poisoned data. They have identified two weaknesses from backdoor attack. First weakness is that models learn from poisoned data at a much faster rate than these learn from clean data. The stronger the attack, the faster the models converge to a backdoor. The second weakness is that the backdoor task is tied to a specific class (the backdoor target class). Based on the two weaknesses, the authors designed a two-step method to learn a clean model with poisoned data.  The first step is to isolate poisoned samples from the training dataset, and the second step is to use the isolated samples to unlearn backdoor. The first step happened in the early training stage and the second stage takes over the training after the first stage. As compared to other state of the arts, the isolation step is very precise, and in many case, the precision is easily to reach 100%. The second step is very effective to unlearn backdoors. Even if only 1% of the poisoned samples are isolated, it can counter up to 70% poisoned samples to learn a clean model. Overall, this is a good paper and the proposed method outperformed the competing methods under the authors’ experimental setting.

summaries: This paper observes that models converge much faster on backdoored data than clean data. Within a few epochs, the training loss for backdoored data will decrease to zero, but not for clean data. Based on such an observation, this paper aims to train clean models on poisoned data without knowing the backdoored portion in the training set. Specifically, it proposes a new training procedure called anti-backdoor learning (ABL), which splits the traditional training procedure into two stages. In the first stage, ABL uses a threshold to prevent loss values for individual samples being too small by flipping the sign of the loss. It then selects a small portion (1%) of the training set with small losses as the backdoored set and the remaining as the clean set. In the second stage, ABL applies gradient ascent on the backdoored set and gradient descent on the clean set. The evaluation is conducted on three standard benchmarks and ABL is compared with three existing backdoor removal baselines. The experimental results show ABL has the best performance on both reducing attack success rate and retaining normal accuracy in most cases. A list of studies on different components of ABL and comparisons with other alternative methods are interesting and informative.

abstractText: Backdoor attack has emerged as a major security threat to deep neural networks (DNNs). While existing defense methods have demonstrated promising results on detecting or erasing backdoors, it is still not clear whether robust training methods can be devised to prevent the backdoor triggers being injected into the trained model in the first place. In this paper, we introduce the concept of anti-backdoor learning, aiming to train clean models given backdoor-poisoned data. We frame the overall learning process as a dual-task of learning the clean and the backdoor portions of data. From this view, we identify two inherent characteristics of backdoor attacks as their weaknesses: 1) the models learn backdoored data much faster than learning with clean data, and the stronger the attack the faster the model converges on backdoored data; 2) the backdoor task is tied to a specific class (the backdoor target class). Based on these two weaknesses, we propose a general learning scheme, Anti-Backdoor Learning (ABL), to automatically prevent backdoor attacks during training. ABL introduces a two-stage gradient ascent mechanism for standard training to 1) help isolate backdoor examples at an early training stage, and 2) break the correlation between backdoor examples and the target class at a later training stage. Through extensive experiments on multiple benchmark datasets against 10 state-of-the-art attacks, we empirically show that ABL-trained models on backdoor-poisoned data achieve the same performance as they were trained on purely clean data. Code is available at https://github.com/bboylyg/ABL.

authors:
Tianyu Gu
Brendan Dolan-Gavitt
Siddharth Garg

title: Badnets: Identifying vulnerabilities in the machine learning model supply chain

venue: arXiv preprint arXiv:1708.06733,

authors:
Cheng-Hsin Weng
Yan-Ting Lee
Shan-Hung Brandon Wu

title: On the trade-off between adversarial and backdoor robustness

venue: In NeurIPS,

authors:
Yiming Li
Baoyuan Wu
Yong Jiang
Zhifeng Li
Shu-Tao Xia

title: Backdoor learning: A survey

venue: arXiv preprint arXiv:2007.08745,

authors:
Bolun Wang
Yuanshun Yao
Shawn Shan
Huiying Li
Bimal Viswanath
Haitao Zheng
Ben Y Zhao

title: Neural cleanse: Identifying and mitigating backdoor attacks in neural networks

venue: In S&P

authors:
Huili Chen
Cheng Fu
Jishen Zhao
Farinaz Koushanfar

title: Deepinspect: A black-box trojan detection and mitigation framework for deep neural networks

authors:
Brandon Tran
Jerry Li
Aleksander Madry

title: Spectral signatures in backdoor attacks

authors:
Bryant Chen
Wilka Carvalho
Nathalie Baracaldo
Heiko Ludwig
Benjamin Edwards
Taesung Lee
Ian Molloy
Biplav Srivastava

title: Detecting backdoor attacks on deep neural networks by activation clustering

venue: In AAAI Workshop,

authors:
Kang Liu
Brendan Dolan-Gavitt
Siddharth Garg

title: Fine-pruning: Defending against backdooring attacks on deep neural networks

venue: In RAID,

authors:
Pu Zhao
Pin-Yu Chen
Payel Das
Karthikeyan Natesan Ramamurthy
Xue Lin

title: Bridging mode connectivity in loss landscapes and adversarial robustness

venue: In ICLR,

authors:
Yige Li
Xixiang Lyu
Nodens Koren
Lingjuan Lyu
Bo Li
Xingjun Ma

title: Neural attention distillation: Erasing backdoor triggers from deep neural networks

authors:
Xinyun Chen
Chang Liu
Bo Li
Kimberly Lu
Dawn Song

title: Targeted backdoor attacks on deep learning systems using data poisoning

venue: arXiv preprint arXiv:1712.05526,

authors:
Yunfei Liu
Xingjun Ma
James Bailey
Feng Lu

title: Reflection backdoor: A natural backdoor attack on deep neural networks

venue: In ECCV,

authors:
Cong Liao
Haoti Zhong
Anna Squicciarini
Sencun Zhu
David Miller

title: Backdoor embedding in convolutional neural network models via invisible perturbation

venue: CODASPY,

authors:
Shaofeng Li
Minhui Xue
Benjamin Zi Hao Zhao
Haojin Zhu
Xinpeng Zhang

title: Invisible backdoor attacks on deep neural networks via steganography and regularization

authors:
Jinyin Chen
Haibin Zheng
Mengmeng Su
Tianyu Du
Changting Lin
Shouling Ji

title: Invisible poisoning: Highly stealthy targeted poisoning

venue: ICISC,

authors:
Aniruddha Saha
Akshayvarun Subramanya
Hamed Pirsiavash

title: Hidden trigger backdoor attacks

venue: In AAAI,

authors:
Shihao Zhao
Xingjun Ma
Xiang Zheng
James Bailey
Jingjing Chen
Yu-Gang Jiang

title: Clean-label backdoor attacks on video recognition models

venue: In CVPR,

authors:
Anh Nguyen
Anh Tran

title: Input-aware dynamic backdoor attack

venue: NeurIPS,

authors:
Yuezun Li
Yiming Li
Baoyuan Wu
Longkang Li
Ran He
Siwei Lyu

title: Invisible backdoor attack with sample-specific triggers

venue: In ICCV,

authors:
Ali Shafahi
W Ronny Huang
Mahyar Najibi
Octavian Suciu
Christoph Studer
Tudor Dumitras
Tom Goldstein

title: Poison frogs! targeted clean-label poisoning attacks on neural networks

authors:
Alexander Turner
Dimitris Tsipras
Aleksander Madry

title: Clean-label backdoor attacks

authors:
Chen Zhu
W Ronny Huang
Hengduo Li
Gavin Taylor
Christoph Studer
Tom Goldstein

title: Transferable clean-label poisoning attacks on deep neural nets

venue: In ICML,

authors:
Yingqi Liu
Shiqing Ma
Yousra Aafer
Wen-Chuan Lee
Juan Zhai
Weihang Wang
Xiangyu Zhang

title: Trojaning attack on neural networks

authors:
Shihao Zhao
Xingjun Ma
Yisen Wang
James Bailey
Bo Li
Yu-Gang Jiang

title: What do deep nets learn? class-wise patterns revealed in the input space

venue: arXiv preprint arXiv:2101.06898,

authors:
Yansong Gao
Change Xu
Derui Wang
Shiping Chen
Damith C Ranasinghe
Surya Nepal

title: Strip: A defence against trojan attacks on deep neural networks

venue: In ACSAC,

authors:
Xiaojun Xu
Qi Wang
Huichen Li
Nikita Borisov
Carl A Gunter
Bo Li

title: Detecting ai trojans using meta neural analysis

venue: In S&P,

authors:
Jonathan Hayase
Weihao Kong
Raghav Somani
Sewoong Oh

title: Spectre: Defending against backdoor attacks using robust statistics

authors:
Di Tang
XiaoFeng Wang
Haixu Tang
Kehuan Zhang

title: Demon in the variant: Statistical analysis of dnns for robust backdoor contamination detection

venue: In USENIX Security,

authors:
Soheil Kolouri
Aniruddha Saha
Hamed Pirsiavash
Heiko Hoffmann

title: Universal litmus patterns: Revealing backdoor attacks in cnns

authors:
Guangyu Shen
Yingqi Liu
Guanhong Tao
Shengwei An
Qiuling Xu
Siyuan Cheng
Shiqing Ma
Xiangyu Zhang

title: Backdoor scanning for deep neural networks through k-arm optimization

authors:
Dongxian Wu
Yisen Wang

title: Adversarial neuron pruning purifies backdoored deep models

authors:
Yuanshun Yao
Huiying Li
Haitao Zheng
Ben Y Zhao

title: Latent backdoor attacks on deep neural networks

venue: In CCS,

authors:
Yiming Li
Tongqing Zhai
Baoyuan Wu
Yong Jiang
Zhifeng Li
Shutao Xia

title: Rethinking the trigger of backdoor attack

venue: arXiv preprint arXiv:2004.04692,

authors:
Yanyao Shen
Sujay Sanghavi

title: Learning with bad training data via iterative trimmed loss minimization

authors:
Mauro Barni
Kassem Kallas
Benedetta Tondi

title: A new backdoor attack in cnns by training set corruption without label poisoning

authors:
Siyuan Cheng
Yingqi Liu
Shiqing Ma
Xiangyu Zhang

title: Deep feature space trojan attack of neural networks by controlled detoxification

authors:
Sergey Zagoruyko
Nikos Komodakis

title: Wide residual networks

venue: In BMVC,

authors:
Takashi Ishida
Ikko Yamane
Tomoya Sakai
Gang Niu
Masashi Sugiyama

title: Do we need zero training loss after achieving zero training error

authors:
Junyu Lin
Lei Xu
Yingqi Liu
Xiangyu Zhang

title: Composite backdoor attack for deep neural network by mixing existing benign features

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

authors:
Johannes Stallkamp
Marc Schlipsing
Jan Salmen
Christian Igel

title: Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition

venue: Neural networks,

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A large-scale hierarchical image database

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Chulin Xie
Keli Huang
Pin-Yu Chen
Bo Li

title: Dba: Distributed backdoor attacks against federated learning

authors:
Lingjuan Lyu
Han Yu
Xingjun Ma
Lichao Sun
Jun Zhao
Qiang Yang
Philip S Yu

title: Privacy and robustness in federated learning: Attacks and defenses

venue: arXiv preprint arXiv:2012.06337,

heading: 1 Introduction

text:
A backdoor attack is a type of training-time data poisoning attack that implant backdoor triggers into machine learning models by injecting the trigger pattern(s) into a small proportion of the training data [1]. It aims to trick the model to learn a strong but task-irrelevant correlation between the trigger pattern and a target class, and optimizes three objectives: stealthiness of the trigger pattern, injection (poisoning) rate and attack success rate. A backdoored model performs normally on clean test data yet consistently predicts the target class whenever the trigger pattern is attached to a test example.
†Correspondence to: Xixiang Lyu, Xingjun Ma.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Studies have shown that deep neural networks (DNNs) are particularly vulnerable to backdoor attacks [2]. Backdoor triggers are generally easy to implant but hard to detect or erase, posing significant security threats to deep learning.
Existing defense methods against backdoor attacks can be categorized into two types: detection methods and erasing methods [3]. Detection methods exploit activation statistics or model properties to determine whether a model is backdoored [4, 5], or whether a training/test example is a backdoor example [6, 7]. While detection can help identify potential risks, the backdoored model still needs to be purified. Erasing methods [8–10] take one step further and remove triggers from the backdoored model. Despite their promising results, it is still unclear in the current literature whether the underlying model learns clean and backdoor examples in the same way. The exploration of this aspect leads to a fundamental yet so far overlooked question, “Is it possible to train a clean model on poisoned data?"
Intuitively, if backdoored data can be identified during training, measures can be taken to prevent the model from learning them. However, we find that this is not a trivial task. One reason is that we do not know the proportion nor the distribution of the backdoored data in advance. As shown in Figure 1, on CIFAR-10, even if the poisoning rate is less than 1%, various attacks can still achieve high attack success rates. This significantly increases the difficulty of backdoor data detection as the model’s learning behavior may remain the same with or without a few training examples. Even worse, we may accidentally remove a lot of valuable data when the dataset is completely clean. Another important reason is that the backdoor may have already been learned by the model even if the backdoor examples are identified at a later training stage.
In this paper, we frame the overall learning process on a backdoor-poisoned dataset as a dual-task learning problem, with the learning of the clean portion as the original (clean) task and the learning of the backdoored portion as the backdoor task. By investigating the distinctive learning behaviors of the model on the two tasks, we identify two inherent characteristics of backdoor attacks as their weaknesses. First, the backdoor task is a much easier task compared to the original task. Consequently, the training loss of the backdoored portion drops abruptly in early epochs of training, whereas the loss of clean examples decreases at a steady pace. We also find that the stronger the attack, the faster the loss on backdoored data drops. This finding indicates that the backdoor correlations imposed by stronger attacks are easier and faster to learn, and marks one distinctive learning behavior on backdoored data. Second, the backdoor task is tied to a specific class (i.e., the backdoor target class). This indicates that the correlation between the trigger pattern and the target class could be easily broken by simply randomizing the class target, for instance, shuffling the labels of a small proportion of examples with low loss.
Inspired by the above observations, we propose a principled Anti-Backdoor Learning (ABL) scheme that enables the training of clean models without any prior knowledge of the distribution of backdoored data in datasets. ABL introduces a gradient ascent based anti-backdoor mechanism into the standard training to help isolate low-loss backdoor examples in early training and unlearn the backdoor correlation once backdoor examples are isolated. In summary, our main contributions are:
• We present a novel view of the problem of robust learning with poisoned data and reveal two inherent weaknesses of backdoor attacks: faster learning on backdoored data and target-class dependency. The stronger the attack is, the more easily it can be detected or disrupted.
• We propose a novel Anti-Backdoor Learning (ABL) method that is capable of training clean models on poisoned data. To the best of our knowledge, ABL is the first method of its kind in the backdoor defense literature, complementing existing defense methods.
• We empirically show that our ABL is robust to 10 state-of-the-art backdoor attacks. The models trained using ABL are of almost the same clean accuracy as they were directly trained on clean data and the backdoor attack success rates on these models are close to random guess.

heading: 2 Related Work

text:
Backdoor Attack. Existing backdoor attacks aim to optimize three objectives: 1) making the trigger pattern stealthier; 2) reducing the poisoning (injection) rate; 3) increasing the attack success rate [3]. Creative design of trigger patterns can help with the stealthiness of the attack. These can be simple patterns such as a single pixel [6] and a black-white checkerboard [1], or more complex patterns such as blending backgrounds [11], natural reflections [12], invisible noise [13–16], adversarial patterns [17] and sample-wise patterns [18, 19]. Backdoor attacks can be further divided into two categories: dirty-label attacks [1, 11, 12] and clean-label attacks [20–22, 17, 16]. Clean-label attacks are arguably stealthier as they do not change the labels. Backdoor attackers can also inject backdoors via retraining the victim model on a reverse-engineered dataset without accessing the original training data [23]. Most of these attacks can achieve a high success rate (e.g., > 95%) by poisoning only 10% or even less of the training data. A recent study by Zhao et al.[24] showed that even models trained on clean data can have backdoors, highlighting the importance of anti-backdoor learning.
Backdoor Defense. Existing backdoor defenses fall under the categories of either detection or erasing methods. Detection methods aim to detect anomalies in input data [7, 6, 25–28] or whether a model is backdoored [4, 5, 29, 30]. These methods typically show promising accuracies; however, the potential impact of backdoor triggers remains uncleared in the backdoored models. On the other hand, erasing methods take a step further and aim to purify the adverse impacts on models caused by the backdoor triggers. The current state-of-the-art erasing methods are Mode Connectivity Repair (MCR) [9], Neural Attention Distillation (NAD) [10] and Adversarial Neuron Pruning (ANP) [31]. MCR mitigates the backdoors by selecting a robust model in the path of loss landscape, NAD leverages attention distillation to erase triggers, while ANP prunes adversarially sensitive neurons to purify the model. Other previous methods, including finetuning, denoising, and fine-pruning [8], have been shown to be insufficient against the latest attacks [32, 33, 12]. An early work [34] found that DNNs are more accurate on clean samples in an early training stage, while we find that the backdoor attacks studied in [34] are only limited to simple BadNets attacks. Thus, it would be interesting to further study the different properties of diverse types of backdoor attacks.
In this paper, we introduce the concept of anti-backdoor learning. Unlike existing methods, our goal is to train clean models directly on poisoned datasets without further altering the models or the input data. This requires a more in-depth understanding of the distinctive learning behaviors on backdoored data. However, such information is not available in the current literature. Anti-backdoor learning methods may replace the standard training to prevent potential backdoor attacks in real-world scenarios where data sources are not 100% reliable, and the distribution or even the presence of backdoor examples are unknown.

heading: 3 Anti-Backdoor Learning

text:
In this section, we first formulate the Anti-Backdoor Learning (ABL) problem, then reveal the distinctive learning behaviors on clean versus backdoor examples and introduce our proposed ABL method. Here, we focus on classification tasks with deep neural networks.
Defense Setting. We assume the backdoor adversary has pre-generated a set of backdoor examples and has successfully injected these examples into the training dataset. We also assume the defender has full control over the training process but has no prior knowledge of the proportion nor distribution of the backdoor examples in a given dataset. The defender’s goal is to train a model on the given dataset (potentially poisoned) that is as good as models trained on purely clean data. Moreover, if an isolation method is used, the defender may identify only a subset of the backdoor examples. For instance, in the case of 10% poisoning, the isolation rate might only be 1%. Robust learning methods developed under our defense setting could benefit companies, research institutes, government agencies or MLaaS (Machine Learning as a Service) providers to train backdoor-free models on potentially poisoned data. More explanations about our threat model and how our proposed ABL method can help other defense settings can be found in Appendix B.10.
Problem Formulation. Consider a standard classification task with a dataset D = Dc [Db where Dc denotes the subset of clean data and Db denotes the subset of backdoor data. The standard training
trains a DNN model f✓ by minimizing the following empirical error:
L = E(x,y)⇠D[`(f✓(x), y)] = E(x,y)⇠Dc [`(f✓(x), y)]| {z } clean task +E(x,y)⇠Db [`(f✓(x), y)]| {z } backdoor task , (1)
where `(·) denotes the loss function such as the commonly used cross-entropy loss. The overall learning task is decomposed into two tasks where the first clean task is defined on the clean data Dc while the second backdoor task is defined on the backdoor data Db. Since backdoor examples are often associated with a particular target class, all data from Db may share the same class label. The above decomposition indicates that the standard learning approach tends to learn both tasks, resulting in a backdoored model.
To prevent backdoor examples from being learned, we propose anti-backdoor learning to minimize the following empirical error instead:
L = E(x,y)⇠Dc [`(f✓(x), y)] E(x,y)⇠Db [`(f✓(x), y)]. (2)
Note the maximization of the backdoor task is defined on Db. Unfortunately, the above objective is undefined during training since we do not know the Db subset. Intuitively, Db can be detected and isolated during training if the model exhibits an atypical learning behavior on the backdoor examples. In the following subsection, we will introduce one such behavior, which we recognize as the first weakness of backdoor attacks.

heading: 3.1 Distinctive Learning Behaviors on Backdoor Examples

text:
We apply 6 classic backdoor attacks including BadNets [1], Trojan [23], Blend [11], Dynamic [18], SIG [35], and CL [21], and 3 feature-space attacks including FC [20], DFST [36], and LBA [32] to poison 10% of CIFAR-10 training data. We train a WideResNet-16-1 model [37] on the corresponding poisoned dataset using the standard training method by solving equation (1) for each attack. Each model is trained following the standard settings (see Section 4 and Appendix A.2). We plot the average training loss (i.e., cross-entropy) on clean versus backdoored training examples in Figure 2. Clearly, for all 9 attacks, the training loss on backdoor examples drops much faster than that on clean examples in the first few epochs. Both pixel- and feature-space attacks exhibit this faster-learning pattern consistently, although some feature-space attacks (FC and LBA) can slow down the process to some extent. For all attacks except SIG, FC and LBA, the training loss reaches almost zero after only two epochs of training. Moreover, according to the attack success rate, the stronger the attack is, the faster the training loss on backdoor examples drops. More results on GTSRB and an ImageNet subset can be found in Appendix B.2.
The above observation indicates that the backdoor task is much easier than the clean task. This is not too surprising. In a typical clean dataset, not all examples are easy examples. Thus, it requires a certain number of training epochs to minimize the loss on those examples, even for small datasets like CIFAR-10. On the contrary, a backdoor attack adds an explicit correlation between the trigger pattern and the target class to simplify and accelerate the injection of the backdoor trigger. We argue that this is a fundamental requirement and also a major weakness of backdoor attacks. For a backdoor attack to work successfully, the trigger(s) should be easily learnable by the model, or else the attack would lose its effectiveness or require a much higher injection rate, which goes against its key objectives. Therefore, the stronger the attack is, the faster the training loss on backdoor examples drops to zero; e.g., compare FC with other attacks in Figure 2. We also show in Figure 6 in Appendix B.1 that the training loss of the backdoor task drops more rapidly as we increase the poisoning rate.
Based on the above observation, one may wonder if backdoor examples can be easily removed by filtering out the low-loss examples at an early stage (e.g., the 5th epoch). However, we find that this strategy is ineffective for two reasons. First, the training loss in Figure 2 is the average training loss which means some backdoor examples can still have high training loss. Additionally, several powerful attacks such as Trojan and Dynamic can still succeed even with very few (50 or 100) backdoor examples. Second, if the training progresses long enough (e.g., beyond epoch 20), many clean examples will also have a low training loss, which makes the filtering significantly inaccurate. Therefore, we need a strategy to amplify the difference in training loss between clean and backdoor examples. Moreover, we need to unlearn the backdoor since the backdoor examples can only be identified when they are learned into the model (i.e., low training loss).

heading: 3.2 Proposed Anti-Backdoor Learning Method

text:
Suppose the total number of training epochs is T , we decompose the entire training process into two stages, i.e., early training and later training. We denote the turning epoch from early training to later training by Tte. Our anti-backdoor learning method consists of two key techniques: 1) backdoor isolation during early training, and 2) backdoor unlearning during later training. The turning epoch is chosen to be the epoch where the average training loss stabilizes at a certain level.
Backdoor Isolation. During early training, we propose a local gradient ascent (LGA) technique to trap the loss value of each example around a certain threshold . We use the loss function LLGA in equation (3) to achieve this. The gradient ascent is said to be “local” because the maximization is performed around a fixed loss value . In other words, if the loss of a training example goes below , gradient ascent will be activated to boost its loss to ; otherwise, the loss stays the same. Doing so will force backdoor examples to escape the constraint since their loss values drop significantly faster. The choice of an appropriate lies in the core of this strategy, as an overly large will hurt the learning of the clean task, while an overly small may not be strong enough to segregate the clean task from the backdoor task. Note that can be determined by the strength of potential attacks: stronger attacks only need a smaller to isolate. Since most backdoor attacks are strong, the poisoned data can easily reach a small loss value below 0.5. So, we set = 0.5 in our experiments and show its consistent performance across different datasets and models in Section 4.2 and Appendix B.5. At the end of early training, we segregate examples into disjoint subsets: p percent of data with the lowest loss values will be isolated into the backdoor set bDb (p = | bDb|/|D|), and the rest into the clean set bDc (D = bDb [ bDc). An important note here is that the isolation rate (e.g., p = 1%) is assumed to be much smaller than the poisoning rate (e.g., 10%).
Backdoor Unlearning. With the clean and backdoor sets, we can then proceed with the later training. Note that at this stage, the backdoor has already been learned by the model. Given the above low isolation rate, an effective backdoor unlearning method is required to make the model unlearn the backdoor with a small subset bDb of backdoor examples while simultaneously learning the remaining
(unisolated) backdoor examples in the clean set bDc. We make this possible by exploiting the second weakness of backdoor attacks: the backdoor trigger is usually associated with a particular backdoor target class. We propose to use the loss LGGA defined in equation (2) for this purpose. In LGGA, a global gradient ascent (GGA) is defined on the isolated subset bDb. Unlike the local gradient ascent, it is not constrained to be around a fixed loss value. We will show in Section 4.2 that a low isolation rate of 1% is able to effectively unlearn the backdoor against 50% poisoning.
The loss functions used by our ABL for its two training stages are summarized as follows,
LtABL = ( LLGA = E(x,y)⇠D ⇥ sign(`(f✓(x), y) ) · `(f✓(x), y) ⇤ if 0  t < Tte
LGGA = E(x,y)⇠ bDc ⇥ `(f✓(x), y) ⇤ E(x,y)⇠ bDb ⇥ `(f✓(x), y) ⇤ if Tte  t < T ,
(3)
where t 2 [0, T 1] is the current training epoch, sign(·) is the sign function, is the loss threshold for LGA and bDb is the isolated backdoor set with the isolation rate p = | bDb|/|D|. During early training (0  t < Tte), the loss will be automatically switched to `(f✓(x), y) if `(·) is smaller than by the sign function; otherwise the loss stays the same, i.e., `(f✓(x), y). Note that LLGA loss may also be achieved by the flooding loss proposed in [38] to prevent overfitting: |`(f✓(x), y) b|+ b where b is a flooding parameter. We would like to point out that LGA serves only one part of our ABL and can potentially be replaced by other backdoor detection methods. Additionally, we will show that a set of other techniques may also achieve backdoor isolation and unlearning, but they are far less effective than our ABL (see Section 4.3 and Appendix B.3).

heading: 4 Experiments

text:
Attack Configurations. We consider 10 backdoor attacks in our experiments, including four dirtylabel attacks: BadNets [1], Trojan attack [23], Blend attack [11], Dynamic attack [18], two clean-label attacks: Sinusoidal signal attack(SIG) [35] and Clean-label attack(CL) [21], and four feature-space attacks: Feature collision (FC) [20], Deep Feature Space Trojan Attack (DFST) [24], Latent Backdoor Attack (LBA) [32], and Composite Backdoor Attack (CBA) [39]. We follow the settings suggested by [10] and the open-sourced code corresponding to their original papers to configure these attack algorithms. All attacks are evaluated on three benchmark datasets, CIFAR-10 [40], GTSRB [41] and an ImageNet subset [42], with two classical model structures including WideResNet (WRN-16-1) [37] and ResNet-34 [43]. No data augmentations are used for these attacks since they hinder the backdoor effect [12]. To keep their original configurations of dataset and parameter settings, here we only run the four feature-space attacks on CIFAR-10 dataset. We also omit some attacks on GTSRB and ImageNet datasets due to a failure of reproduction following their original papers. The detailed settings of the 10 backdoor attacks are summarized in Table 5 (see Appendix A.2).
Defense and Training Details. We compare our ABL with three state-of-the-art defense methods: Fine-pruning (FP) [8], Mode Connectivity Repair (MCR) [9], and Neural Attention Distillation (NAD) [10]. For FP, MCR and NAD, we follow the configurations specified in their original papers, including the available clean data for finetuning/repair/distillation and training settings. The comparison with other data isolation methods are shown in Section 4.3. For our ABL, we set T = 100, Tte = 20, = 0.5 and an isolation rate p = 0.01 (1%) in all experiments. The exploration of different Tte, , and isolation rates p are also provided in Section 4.1. Three data augmentation techniques suggested in [10] including random crop (padding = 4), horizontal flipping, and cutout, are applied for all defense methods. More details on defense settings can be found in Appendix A.3.
Evaluation Metrics. We adopt two commonly used performance metrics: Attack Success Rate (ASR), which is the classification accuracy on the backdoor test set, and Clean Accuracy (CA), the classification accuracy on clean test set.

heading: 4.1 Effectiveness of Our ABL Defense

text:
Comparison to Existing Defenses. Table 1 demonstrates our proposed ABL method on CIFAR-10, GTSRB, and an ImageNet Subset. We consider 10 state-of-the-art backdoor attacks and compare the performance of ABL with three other backdoor defense techniques. It is clear that our ABL achieves the best results on reducing ASR against most of backdoor attacks, while maintaining an extremely high CA across all three datasets. In comparison to the best baseline method NAD, our ABL achieves 12.71% (7.69% vs. 20.40%), 11.90% (7.27% vs. 19.17%), and 7.35% (6.00% vs. 13.35%) lower
average ASR against the 10 attacks on CIFAR-10, GTSRB, and the ImageNet subset, respectively. This superiority becomes more significant when compared to other baseline methods.
We notice that our ABL is not always the best when looking at the 10 attacks individually. For instance, NAD is the best defense against the Blend attack on CIFAR-10 and against the SIG attack on GTSRB, while MCR is the best against Blend on GTSRB and the ImageNet subset. We suspect this is because both Blend and SIG mingle the trigger pattern (i.e., another image or superimposed sinusoidal signal) with the background of the poisoned images, producing an effect of natural artifacts. This makes them harder to be isolated and unlearned, since even clean data can have such patterns [24]. This is one limitation of our ABL that needs to be improved in future works. Our ABL achieves a much better performance than the baselines on defending against the 4 feature-space attacks. For example, NAD only manages to decrease the attack success rates of the FC and the DFST attacks to 58.68% and 35.21%, respectively. In contrast, our ABL can bring their ASRs down to below 10%. The Dynamic and the CBA attacks are found to be the toughest attacks to defend against in general. For example, baseline methods NAD, MCR and FP can only decrease CBA’s ASR to 33.11%, 38.76%, and 77.33% on CIFAR-10, and Dynamic’s ASR to 68.71%, 64.82%, and 99.84% on GTSRB, respectively, a result that is much worse than the 29.81% and 6.24% ASRs of our ABL.
Maintaining the clean accuracy is as important as reducing the ASR, as the model would lose utility if its clean accuracy is much compromised by the defense. By inspecting the average CA results in Table 1, one can find that our ABL achieves nearly the same clean accuracy as models trained on 100% clean (shown in row None and column ‘No Defense’) datasets. Specifically, our ABL surpasses the average clean accuracy of NAD by 4.39% (84.76% vs. 80.37%), 8.21% (95.25% vs. 87.04%) and 5.07% (86.87% vs. 81.80%) on CIFAR-10, GTSRB, and the ImageNet subset, respectively. FP defense decreases the model’s performance even when training data are clean (the None row). This makes our ABL defense more practical for industrial applications where performance is equally
important as security. Results of our ABL with 1% isolation against 1% poisoning can be found in
Table 10 (Appendix B.9).
Effectiveness with Different Isolation Rates. Here, we study the correlation between the isolation rate p = | bDb|/|D| and the performance of our ABL, on the CIFAR-10 dataset. We run ABL with different p 2 [0.01, 0.2] and show attack success rates and clean accuracies in Figure 3. There is a trade-off between ASR reduction and clean accuracy. Specifically, a high isolation rate can isolate more backdoor examples for the later stage of unlearning, producing a much lower ASR. However, it also puts more examples into the unlearning mode, which harms the clean accuracy. In general, ABL with an isolation rate < 5% works reasonably well against all 6 attacks, even though the backdoor poisoning rate is much higher, i.e., 70% (see Figure 2 in Section 4.2). Along with the results in Table 1, this confirms that it is indeed possible to break and unlearn the backdoor correlation with only a tiny subset of correctly-identified backdoor examples, highlighting one unique advantage of backdoor isolation and unlearning approaches.
Effectiveness with Different Turning Epochs. Here, we study the impact of the timing to switch from the learning stage (LLGA) to the unlearning stage (LGGA) on CIFAR-10. We compare four different turning epochs: the 10th, 20th, 30th, and 40th epoch, and record the results of our ABL in
Table 6 (see Appendix B.4). We find that delayed turning epochs tend to slightly hinder the defense performance. Despite the slight variations, all choices of the turning epoch help mitigate backdoor attacks, but epoch 20 (i.e., at 20% - 30% of the entire training progress) achieves the best overall results. This trend is consistent on other datasets as well. We attribute these results to the success of LGA in preserving the difference between clean and backdoor samples over time, which enables us to select the turning epoch flexibly. A more comprehensive discussion on LGA is given in Section 4.2.

heading: 4.2 Comprehensive Understanding of ABL

text:
Importance of Local Gradient Ascent. To help understand how LGA works in isolating backdoor data, we visualize and compare in Figure 4 the training loss and the model’s performances (ASR and CA) under three different settings where is set to 0.5, 1.0, and 1.5, respectively. It is evident that LGA can segregate backdoor examples from clean examples to a certain extent under all three settings of by preventing the loss of clean examples from converging. Moreover, a larger leads to
a wider difference in training loss as well as ASR and CA. However, we note that this may cause training instability, as evidenced by the relatively larger fluctuations with = 1.5.
We also examine the precision of the 1% isolated backdoor set under different of 0, 0.5, 1.0, and 1.5 on CIFAR-10, GTSRB, and the ImageNet subset. We use BadNets attack with a poisoning rate 10% and set the turning (isolation) epoch of ABL to 20. We report the isolation precision results in Table 7 (see Appendix B.5). As can be seen, when = 0, the detection precision is poor; this indicates that it is tough for the model to tell apart backdoor examples from the clean ones without the LGA, which is foreseeable because the clean training loss is uncontrolled and overlaps with the backdoor training loss. Note that as soon as we set > 0, the precision immediately improves on both CIFAR-10 and the ImageNet subset. Additionally, the precision of the isolation task is not sensitive to the change in , which again allows the hyperparameter value to be flexibly chosen. In our experiments, = 0.5 works reasonably well across different datasets and models.
In summary, LGD creates and sustains a gap between the training loss of clean and backdoor examples, which plays a vital role in extracting an isolated backdoor set.
Stress Testing: Fixing 1% Isolation Rate While Increasing Poisoning Rate. Now that we know we can confidently extract a tiny subset of backdoor examples with high purity, the challenge remains whether the extracted set is sufficient for the model to unlearn the backdoor. We demonstrate that our ABL is a stronger method, even under this strenuous setting. Here, we experiment on CIFAR-10 against 4 attacks including BadNets, Trojan, Blend, and Dynamic with poisoning rates up to 50%/70% and show the results in Table 2. We can find that even with a high poisoning rate of 50%, our ABL method can still reduce the ASR from 100% to 4.98%, 16.11%, 27.28%, and 25.74% for BadNets, Trojan, Blend, and Dynamic, respectively. Note that ABL will break when the poisoning rate reaches 70%. In this case however, the dataset should not be used to train any models in the first place. Overall, ABL remains effective against up to 1) 70% BadNets; and 2) 50% Trojan, Blend, and Dynamic. This finding is very compelling, considering ABL needs to isolate only 1% of training data. As we mentioned before, this is because the correlation between the backdoor pattern and the target label exposes a weakness of backdoor attacks. Our ABL utilizes the GGA to break this link and achieve defense goals effortlessly.

heading: 4.3 Exploring Alternative Isolation and Unlearning Methods

text:
Alternative Isolation Methods. In this section, we compare the isolation precision of our ABL with two backdoor detection methods, namely Activation Clustering (AC) [7] and Spectral Signature Analysis (SSA) [6]. The goal is to isolate 1% of training examples into the backdoor set ( bDb), and we provide in Figure 7 (see Appendix B.3) the precision of these methods alongside our ABL in detecting the 6 backdoor attacks on CIFAR-10 dataset. We find that both AC and SS achieve high detection rates on BadNets and Trojan attacks while perform poorly on 4 other attacks. A reasonable explanation is that attacks covering the whole image with complex triggers (e.g., Blend, Dynamic, SIG, and CL) give confusing and unidentifiable output representations of either feature activation or spectral signature, making these detection methods ineffective. It is worth mentioning that our ABL is effective against all backdoor attacks with the highest average detection rate. In addition, we find that the flooding loss [38] proposed for mitigating overfitting is also very effective for backdoor isolation. We also explore a confidence-based isolation with label smoothing (LS), which unfortunately fails on most attacks. More details of these explorations can be found in Figure 8 and 9 in Appendix B.6.
Alternative Unlearning Methods. Here we explore several other empirical strategies, including image-based, label-based, model-based approaches, to rebuild a clean model on the poisoned data.
These approaches are motivated by the second weakness of backdoor attacks, and are all designed to break the connection between the trigger pattern and the target class. We experiment on CIFAR-10 with BadNets (10% poisoning rate), and fix the backdoor isolation method to our ABL with a high isolation rate 20% (as most of them will fail with 1% isolation). Table 3 summarizes our explorations. Our core findings can be summarized as: a) adding perturbations to pixels or gradients is not effective; b) changing the labels of isolated examples is mildly effective; c) finetuning some (not all) layers of the model cannot effectively mitigate backdoor attacks; d) “self-learning” and “retraining the model from scratch” on the isolated clean set are good choices against backdoor attacks; and e) our ABL presents the best unlearning performance. Details of these methods are given in Appendix A.4. The performance of these methods under the 1% isolation rate is also reported in Table 8 in Appendix B.7. We also considered another widely used attack settings that the user only allowed to access a backdoored model and hold limited benign data. In this case, we proposed to combine our ABL unlearning with Neural Cleanse [4] to erase the backdoroed model (see Appendix B.10).

heading: 5 Conclusion

text:
In this work, we identified two inherent characteristics of backdoor attacks as their weaknesses: 1) backdoor examples are easier and faster to learn than clean examples, and 2) backdoor learning establishes a strong correlation between backdoor examples and the target label. Based on these two findings, we proposed a novel framework - Anti-Backdoor Learning (ABL) - which consists of two stages of learning utilizing local gradient ascent (LGA) and global gradient ascent (GGA), respectively. At the early learning stage, we use LGA to intentionally maximize the training loss gap between clean and backdoor examples to isolate out the backdoored data via the low loss value. We use GGA to unlearn the backdoored model with the isolated backdoor data at the last learning stage. Empirical results demonstrate that our ABL is resilient to various experimental settings and can effectively defend against 10 state-of-the-art backdoor attacks. Our work introduces a simple but very effective ABL method for industries to train backdoor-free models on real-world datasets, and opens up an interesting research direction for robust and secure machine learning.
Broader Impact
Large-scale data have been key to the success of deep learning. However, it is hard to guarantee the quality and purity of the training data in many cases, and even high-quality datasets may contain backdoors, especially those collected from the internet. By introducing the concept of anti-backdoor learning (ABL), our work opens up a new direction for secure and robust learning with not-fullytrusted data. Even in the clean setting, ABL can prevent deep learning models from overfitting to those overly easy samples. Beyond backdoor defense, ABL could be explored as a generic data-quality-ware learning mechanism in place of the traditional data-quality-agnostic learning. Such a mechanism may help reduce many potential data-quality-related risks such as memorization, overfitting, backdoors and biases. Although not our initial intention, our work may adversely be exploited to develop advanced backdoor attacks. This essentially requires new defenses to combat.

heading: Acknowledgement

text: This work is supported by China National Science Foundation under grant number 62072356 and in part by the Key Research and Development Program of Shaanxi under Grant 2019ZDLGY12-08.

title: Anti-Backdoor Learning: Training Clean Models on Poisoned Data