Feature Purification: How Adversarial Training Performs Robust Deep Learning

Zeyuan Allen-Zhu; Yuanzhi Li

Source-linked AI summary

Feature Purification: How Adversarial Training Performs Robust Deep Learning

Zeyuan Allen-Zhu, Yuanzhi Li

arXiv:2005.10190v4May 20, 2020cs.LGcs.NEmath.OCstat.ML

TL;DR

The paper addresses why clean-trained neural networks can generalize while remaining vulnerable to adversarial perturbations, and what adversarial training changes internally. It develops the feature-purification principle, combining theory and experiments, and shows that adversarial training can robustify networks by purifying dense mixtures that clean training accumulates, whereas several low-complexity models cannot achieve comparable robustness.

Problem
The paper studies why clean training learns features that generalize on ordinary data yet remain non-robust, and how adversarial training robustifies those features.
Method
The paper develops a feature-purification theory for learned hidden weights in two-layer ReLU networks, supported by experiments and analysis of dense mixtures produced by gradient descent.
Results
Adversarial training can purify dense mixtures and achieve near-perfect robust accuracy, while linear classifiers, low-degree polynomials, and the corresponding NTK cannot achieve meaningful robust accuracy in the same setting.
Takeaways & Limitations
The results support feature purification as an explanation for how adversarial training changes learned features and improves robustness beyond the capability of the studied low-complexity models.
Takeaways & Limitations
The theory is proved only for two-layer ReLU networks and certain learning tasks, while extending it to richer natural-image structure and multilayer networks remains open.

Abstract

from arXiv · show

Despite the empirical success of using Adversarial Training to defend deep learning models against adversarial perturbations, so far, it still remains rather unclear what the principles are behind the existence of adversarial perturbations, and what adversarial training does to the neural network to remove them. In this paper, we present a principle that we call Feature Purification, where we show one of the causes of the existence of adversarial examples is the accumulation of certain small dense mixtures in the hidden weights during the training process of a neural network; and more importantly, one of the goals of adversarial training is to remove such mixtures to purify hidden weights. We present both experiments on the CIFAR-10 dataset to illustrate this principle, and a theoretical result proving that for certain natural classification tasks, training a two-layer neural network with ReLU activation using randomly initialized gradient descent indeed satisfies this principle. Technically, we give, to the best of our knowledge, the first result proving that the following two can hold simultaneously for training a neural network with ReLU activation. (1) Training over the original data is indeed non-robust to small adversarial perturbations of some radius. (2) Adversarial training, even with an empirical perturbation algorithm such as FGM, can in fact be provably robust against ANY perturbations of the same radius. Finally, we also prove a complexity lower bound, showing that low complexity models such as linear classifiers, low-degree polynomials, or even the neural tangent kernel for this network, CANNOT defend against perturbations of this same radius, no matter what algorithms are used to train them.

1 Introduction

The paper explains adversarial vulnerability through dense mixtures accumulated in hidden weights during clean training and studies how adversarial training purifies them. Its theory and experiments show that clean training can generalize yet remain non-robust, while adversarial training can recover robust accuracy and exceed low-complexity model limits.

Small adversarial perturbations can cause errors even when they are invisible to humans, motivating a theory of adversarial examples and robust training.
A new analytical routine studies learned features, identified with hidden weights, for neural networks on naturally structured inputs.
With polynomially many examples and iterations, randomly initialized gradient descent learns well-generalizing features and achieves close-to-perfect clean test accuracy, yet the resulting network has near-zero robust accuracy against small perturbations.
Adversarial training with methods such as FGM can efficiently achieve near-perfect robustness against worst-case norm-bounded perturbations through feature purification.
Feature purification formalizes adversarial training as removing dense mixtures from features rather than learning new robust features or removing entire existing features.
The paper proves purification for two-layer ReLU networks, observes it empirically in deeper networks, and shows that linear classifiers, low-degree polynomials, and the corresponding NTK cannot achieve meaningful robust accuracy in the same setting.
Gradient descent accumulates dense mixture directions because they correlate with average training data while remaining weakly correlated with individual natural examples under sparse coding.

2 Preliminaries

The paper studies binary classification under a sparse-coding data model, where inputs combine sparse hidden vectors with noise. It defines clean and robust errors to analyze performance on original data and under bounded adversarial perturbations.

Data model: Inputs follow a sparse-coding model, combining a dictionary representation Mz with noise ξ.The main setting uses a unitary dictionary for simplicity, while noting extensions to other dimensions or incoherent dictionaries.
Data model: The hidden vector z is sparse, with independent symmetric coordinates whose magnitudes follow the stated distributional assumptions.The assumptions permit both small nonzero coordinates and occasional maximum-magnitude coordinates.
Data model: With high probability, z has Θ(k) nonzero coordinates, establishing the model’s sparsity.This fact is used later to reason about robustness of higher-complexity classifiers.
Motivation: The sparse-coding assumptions are intended to model structured inputs such as images, text, and speech rather than unstructured Gaussian data.The paper emphasizes distinguishing neural-network training behavior from separate dictionary-learning algorithms.
Noise model: The noise model includes Gaussian and spike-noise components, and the lower bounds continue to hold even when ξ=0.The upper bounds also cover substantially noisy settings, including noise whose norm can exceed the signal norm.
Error measures: Clean error measures misclassification on the original data, while robust error measures whether any perturbation within radius τ can change the prediction.The robust-error definition is given for perturbations constrained by an ℓp norm.

3 Warmup Intuitions

The warmup contrasts linear classifiers with higher-complexity models on sparse-coded data. Linear rules can have poor clean or robust accuracy, whereas nonlinear feature selection can suppress weak signals and achieve strong robustness.

Linear versus nonlinear models: When σx is Θ(1), linear classifiers may fail to achieve good clean accuracy because noise can be as large as the signal.The paper states that no linear classifier, and even no constant-degree polynomial, can then achieve meaningful clean accuracy.
Linear versus nonlinear models: Even with perfectly linearly classifiable data, linear classifiers remain vulnerable to small adversarial perturbations.An adversary can perturb along the classifier’s feature direction and change the prediction.
Linear versus nonlinear models: Higher-complexity models can use indicator-like features to retain significant coordinates while suppressing low-magnitude signals.This produces a classifier that matches the labeling function on the original data and is more robust to noise than a linear model.
Robustness: The high-complexity classifier achieves 1−o(1) robust accuracy against ℓ2 perturbations of the stated radius, which is information-theoretically optimal in this setting.Its robustness follows from the sparsity of the active signal coordinates.
Neural-network motivation: The paper’s neural-network goal is to show that adversarial training can recover a sparse-basis representation using two-layer ReLU features.Experiments report that adversarially trained AlexNet features sparsely reconstruct images, with average sparsity of 4.05% or less.

4 Learner Network and Adversarial Training

The learner is a symmetric two-layer ReLU network trained first on clean data and then, in the adversarial-training analysis, on perturbed examples. Robust error is evaluated against arbitrary bounded perturbations, while FGM connects the empirical training objective to true robust error.

Learner network: The model is a symmetric two-layer ReLU network whose hidden weights are treated as learned features.Symmetry pairs weights with their negatives to simplify the proofs, and pre-activation noise smooths the ReLU gradient.
Training objective: The training objective uses logistic loss together with a regularizer corresponding to weight decay.The paper distinguishes population, empirical, and sample-level losses in defining the objective.
Clean training: Clean training applies gradient descent to hidden weights on the original data, starting from random initialization.The setup includes bias schedules and fixed output weights for analytical simplicity.
Adversarial training: Adversarial training initializes from a clean-trained network and repeatedly applies gradient descent using examples perturbed by an attacker A.The paper notes that this initialization is chosen for theoretical comparison, although clean-trained initialization performs no worse than random initialization in practice.
Adversarial training: The attacker maps the current network and example to a bounded perturbation, and FGM satisfies the paper’s admissibility conditions.FGM uses the input gradient and a dual-norm constraint to construct the perturbation.
Feature purification: The analysis attributes clean-training failure to dense mixtures and interprets adversarial training as removing those directions from neuron features.The paper also notes that direct adversarial training from random initialization should avoid learning such mixtures rather than first learning and later removing them.
Robustness evaluation: The theory controls empirical robust error for all admissible attackers and obtains true robust error by using FGM as an example.Robust error quantifies failure under any perturbation within the specified ℓp radius.

5 Statements and Explanations of Our Main Results

The paper characterizes clean training as learning robust features mixed with small dense components that preserve clean accuracy but enable adversarial vulnerability. It proves that adversarial training removes these mixtures, yielding robustness against worst-case perturbations, while low-complexity models cannot achieve comparable robustness.

Clean training: Clean training can achieve good clean accuracy while retaining near-zero robust accuracy, even with infinitely many data and super-polynomially many training iterations.The paper attributes this failure to learned features that generalize on clean data but remain vulnerable to small adversarial perturbations.
Clean training features: After clean training, each hidden neuron contains a robust feature component plus a small dense mixture across many feature directions.The mixture is associated with fixed feature subsets determined by random initialization, while many neurons predominantly select a single feature.
Feature purification: Dense mixtures have low correlation with ordinary inputs, preserving clean accuracy, but small dense perturbations aligned with them can make the model non-robust.These dense perturbation directions do not occur in the original data distribution, so clean training does not remove them.
Adversarial training: Adversarial training locally purifies hidden weights by removing dense mixtures, and the paper reports that low-rank updates can suffice to regain robust accuracy.The dense-mixture direction is common across neurons, motivating a low-rank update rather than retraining every parameter.
Adversarial training: When FGM is used, adversarial training provably generalizes from the training perturbation procedure to robustness against any worst-case perturbation of the same radius.The result distinguishes robustness against the attack algorithm from robustness against all norm-bounded perturbations.
ℓ∞ robustness: The theory gives an ℓ∞ robustness gap: clean training is non-robust at radius 1/k^(2−c1), whereas adversarial training is robust at radius 1/k^(1.75+2c0).The constants c0 and c1 can be made arbitrarily small, and the comparison applies to the stated sparse-coding setting.
Complexity lower bound: Linear classifiers, low-degree polynomials, and the corresponding NTK cannot achieve meaningful robust accuracy for the same concept class, despite achieving high clean accuracy.The lower bound contrasts these low-complexity models with the robustly trainable ReLU network.

6 Overview of the Training Process

The analysis describes how randomly initialized gradient descent first selects feature-aligned neurons, then accumulates small dense mixtures that cause non-robustness, while adversarial training purifies those mixtures.

Training overview: The training-process proof starts from random initialization and analyzes gradient descent in successive phases.The complete proof is deferred to the Appendix.
Lottery ticket winning: “Lottery ticket winning” describes how neurons deviate from random initialization and grow toward individual features.The process is distinct from the neural tangent kernel regime because ReLU activation patterns change substantially.
Lottery ticket winning: With mild over-parameterization m ≥ d^1.001, each feature dimension has at most d^0.01 potential lottery tickets, while at least one neuron wins a ticket.Random Gaussian initialization yields both potentially lucky and surely lucky neurons.
Dense mixtures: After lottery-ticket selection, gradient descent accumulates a small dense mixture in each neuron, leaving clean accuracy high but creating vulnerability to small dense perturbations.The mixture has negligible contribution on clean inputs because it is weakly correlated with any particular natural input.
Dense mixtures: The dense perturbation direction is universal across independently trained models, explaining why an adversarial perturbation found on one model can transfer to others.Its effect on the network can be large even when the perturbation norm is much smaller than the input norm.
Feature purification: Adversarial training purifies dense mixtures through adversarial examples whose correlations with the vulnerable directions are unusually high.The resulting changes to individual neurons are small but substantially improve robustness.

7 Conclusion

The conclusion attributes clean-training non-robustness to the interaction between gradient-descent inductive bias and sparse data structure, while identifying feature purification as the paper’s central mechanism. The authors frame the analysis as provisional and call for extensions to richer data and multilayer networks.

Main conclusion: The paper’s main conclusion is that clean training accumulates dense mixture directions with low natural-input correlation but high vulnerability to dense adversarial perturbations.Adversarial training purifies these mixtures and improves robustness.
Main conclusion: The proposed explanation identifies two necessary ingredients: the inductive bias of stochastic gradient descent and the sparse-coding structure of the data.The conclusion states that both reasons are necessary in the paper’s setting.
Implications: Understanding non-robustness therefore requires considering both the training algorithm and the structure of the inputs.The paper notes that some datasets allow clean gradient-descent training to achieve the best robust accuracy.
Limitations and extensions: The authors describe the work as provisional because natural images may contain richer structure than sparsity and multilayer networks may require hierarchical feature purification.They cite Figure 10 experiments as evidence of such a hierarchical phenomenon.

8 Experiment Details

The experiments evaluate AlexNet and two ResNet architectures on CIFAR-10 using clean and adversarial training, multiple attack settings, and feature visualizations. They also examine whether robust training produces more meaningful deep-feature visualizations.

Architectures and data: Experiments use AlexNet, ResNet-16, and ResNet-34 with basic blocks on CIFAR-10.The implementations use standard data augmentation and SGD with momentum.
Attack settings: The study implements empirical ℓ2 and ℓ∞ attackers, including ℓ∞ radii 4/255 and 8/255 with seven PGD steps.The main focus is the ℓ2(1, 0.25) attacker, with comparisons in Section 8.4.
Training protocol: Adversarial training can start from clean-trained weights without affecting overall robust or clean accuracy performance.Table 1 reports robust and clean accuracies against the specified attackers.
Feature visualization: The visualization procedure starts from a random image and repeatedly updates it using gradients to excite a selected neuron.The implementation takes 2000 gradient steps and applies weight decay toward a specified RGB value.
Feature visualization: Robustly trained models allow the naive deep-feature visualization procedure to produce visually meaningful images.The paper attributes the improvement to removal of dense mixtures that are visually meaningless.

adversarial training

The experiments show that adversarial training purifies features and perturbations, including in deep layers, while low-rank updates can recover much of full adversarial-training robustness.

Feature purification in deep layers: Feature purification occurs even when only deep ResNet-34 layers are trained, with earlier layers frozen at pre-trained robust weights.The comparison includes random initialization, clean training, and adversarial training for layers beginning at multiple depths.
Sparse reconstruction: Robust features reconstruct input images more sparsely than random or clean features, supporting their greater purity.The reconstruction comparison uses Lasso across random, clean, and robust features.
Sparse reconstruction: Clean-model adversarial perturbations contain denser mixtures, whereas robust-model perturbations are purer and closer to real input images.The paper compares sparse reconstruction of clean delta and robust delta using robust features.
Attacker robustness: Feature purification occurs against several different attackers.
Low-rank updates: A clean-trained ResNet-28-10 has zero robust accuracy, but a rank-1 update using less than 1% of parameters recovers more than 80% of maximum robust accuracy.The experiment applies adversarial training only to low-rank updates of convolutional parameters.
Low-rank updates: A rank-8* update trains about 5% of parameters and recovers more than 90% of maximum robust accuracy.

B.1 Proof of Lemma B.2

The initialization analysis establishes high-probability bounds on Gaussian inner products and related neuron quantities used in the subsequent training analysis.

Initialization bounds: Gaussian tail bounds control inner products between randomly initialized weights and feature directions.
Proof strategy: The proof uses concentration and union bounds over neurons and coordinates to obtain simultaneous initialization guarantees.
Initialization bounds: With high probability, most feature directions have small initial correlations with randomly initialized neuron weights.

C Neuron Structure Change During Training

The neuron-structure analysis divides training into phases and tracks how signal, non-signal, and activation properties evolve with high probability.

Training phases: Phase I begins with neurons moving little and accuracy remaining at 50%, while some neurons form singleton structures through a lottery-ticket effect.
Training phases: In Phase II, neurons move more substantially, network outputs become meaningful, and singleton neurons become even more selective.
Consequences: The resulting high-probability estimates support the paper’s claims about neuron structure and learned feature organization.
Signal evolution: The analysis bounds pre-activation signals and separates signal growth from non-signal growth across training.
Activation analysis: Activation probabilities are controlled through phase-specific bounds on Γ_t and Γ_t,y.

D Clean Accuracy Convergence Analysis

The clean-training convergence analysis shows that gradient descent can achieve low population risk and high clean accuracy while tracking a tractable coupling function.

Convergence guarantee: After sufficient training, at least 99% of iterations have population risk o(1) and clean population accuracy at least 1−o(1).
Scope of the proof: The analysis notes that extending the guarantee uniformly over the full iteration range would require additional effort and is not proved.
Proof strategy: The proof analyzes a coupling function that first-order approximates the neural network and matches its output at the current parameters.
Proof strategy: A specially constructed parameter choice μ⋆ is used to characterize the target behavior of the coupled dynamics.
Proof strategy: The convergence argument combines a pseudo-objective, convexity in μ, and telescoping over training iterations.

D.2 Proof of Claim D.6: Main Coupling

The proof bounds the coupling term by decomposing it into components and controlling sensitivity to the independent random variables z and ξ. High-probability concentration, followed by McDiarmid’s inequality and a zero-expectation argument, completes the proof.

Decomposition: The proof splits gt(µ⋆; x) into gt,1 and gt,4, then bounds the two terms separately.The gt,1 component is identified explicitly, while gt,4 is treated as a function of independent variables z, ξ, and ρ.
Sensitivity bounds: The analysis controls gt,4 by checking its sensitivity when individual z_j or ξ_j variables are perturbed.Separate perturbation cases are considered for z_j ∈ [−1,1] and ξ_j ∈ [−B,B].
High-probability control: With probability at least 1 − e^−Ω(log^2 d), the relevant exceptional-coordinate counts are bounded by O(kΞ^2).These bounds support the subsequent concentration estimates for the perturbed expressions.
Concentration: Applying high-probability McDiarmid inequalities twice yields concentration bounds, first over z and then over ξ.The proof combines the two perturbation analyses before invoking the inequality in each variable block.
Conclusion: Because E_z,ξ gt,4(z, ξ, ρ) = 0 for every ρ, the concentration bounds finish the proof of Lemma D.6a.The proof then uses a Lipschitz argument and expectation bounds to establish Lemma D.6b.

E Why Clean Training is Non-Robust

Clean training develops a shared hidden-weight direction that adversarial perturbations can exploit. Perturbing inputs along this direction can sharply change the network output, driving robust accuracy below e^−Ω(log^2 d).

Main theorem: Clean training is proved non-robust to ℓ2 perturbations of radius τ = Ω(·) under the theorem’s parameter conditions.The result applies after sufficiently many clean-training iterations and with high probability over initialization and training randomness.
Shared direction: Near the end of clean training, hidden neurons acquire a small common direction in Mw⋆.This shared component is the structural mechanism used in the proof of non-robustness.
Adversarial direction: Perturbing each input in the direction −y·Mw⋆ can change the network’s output label dramatically.The proof establishes opposite output signs after perturbations in the corresponding directions.
Robustness consequence: The resulting robust accuracy is below e^−Ω(log^2 d).A norm bound on Mw⋆ supplies the required perturbation-radius control.

F Robust Training Through Local Feature Purification

Robust training is analyzed after an initial clean-training phase using arbitrary norm-bounded perturbation algorithms. Under the stated conditions, it controls hidden-weight movement and yields provable robustness, including cases where it outperforms clean training.

Robust-training guarantees: After clean pretraining, ℓ2 and ℓ∞ robust training are each shown to achieve high-probability robustness under separate parameter conditions.Theorems F.1 and F.4 analyze the two perturbation norms after additional robust-training iterations.
Training setup: The robust-training theorems apply to arbitrary norm-bounded perturbation algorithms, including FGM.The perturbation may depend on the current network, input, label, and internal randomness, subject to the specified norm bound.
ℓ2 comparison: For k ∈ [d^0.3334, d^0.3999], robust training provably beats clean training in ℓ2 robust accuracy.The comparison is stated directly for the specified range of k.
ℓ∞ comparison: For k ∈ [d^0.3334, d^0.3999] and ∥M∥∞, ∥M∥1 ≤ d^0.1248, robust training provably beats clean training in ℓ∞ robust accuracy.This comparison requires both norm bounds on M.
Feature purification mechanism: The analysis introduces robust coupling to compare the perturbed network with a linearized representation while bounding hidden-weight movement.Separate lemmas handle ℓ2 and ℓ∞ perturbations and control the relevant neuron-wise norms during robust training.

F.5 Fast Gradient Method (FGM) Robust Training

The FGM analysis derives robustness from bounds that hold for most inputs and then extends the guarantee from the FGM perturbation to every perturbation within the same radius. The section also gives a complexity lower-bound setting for the neural tangent kernel.

FGM setup: For the ℓ2 case, the FGM perturbation is defined as δ⋆ = A(ft, x, y) with radius τ.The proof treats this perturbation as one admissible vector in the robust-training analysis.
High-probability inputs: The movement and coupling bounds hold for at least 1 − o(1) probability mass of inputs.Markov’s and Jensen’s inequalities are used to obtain the high-probability-over-inputs statement.
Any-perturbation guarantee: The network output is robust at those inputs against any perturbation δ with radius τ, not only the FGM perturbation.The proof uses linearity in δ after applying the bounds to δ⋆.
Complexity lower bound: The section defines the neural tangent kernel feature mapping and specializes the lower-bound analysis to M = I and σx = 0.The simplified setting has ξ ≡ 0 and is used to strengthen the lower bound.
NTK limitation: With high probability, choosing τ = 1/d^c6 yields the stated lower-bound regime for sufficiently large d and k in the specified interval.The theorem assumes Gaussian hidden weights, polynomially bounded width, and small biases and smoothing parameters.

G.1 Proof of Theorem G.1

The proof establishes that the neural tangent kernel cannot robustly classify the constructed data under perturbations of radius τ. It combines Gaussian smoothing, polynomial and tensor bounds, and a distributional construction to obtain a 50% · (1 − o(1)) error mass.

Robustness reduction: Claim G.2 converts robustness to every ℓ∞ perturbation of radius τ into a constraint involving Gaussian perturbations ζ ∼ N(0, τ^2).With high probability, ζ + δ remains within the allowed ℓ∞ radius, so the robust classifier must preserve the correct label after both perturbations.
Robustness reduction: The proof smooths the NTK with Gaussian noise so its indicator functions can be analyzed using Taylor expansion.The smoothing step sacrifices the ℓ∞ radius from τ to τ/2 and leads to a polynomial expansion whose homogeneous components are represented as tensors.
Polynomial and tensor bounds: Claim G.3 decomposes the smoothed NTK into polynomial components with controlled coefficients under the stated parameter and perturbation conditions.The claim applies to τ ∈ [1/d^1/5, 1], perturbations with ℓ∞ norm at most τ/2, and bounded MW(δ).
Lower-bound conclusion: At least 50% · (1 − o(1)) of the 2q constructed points are classified incorrectly under ℓ2 perturbations of radius τ.Claim G.2 implies that the NTK outputs the wrong label for either zj or −zj, producing the stated fraction of errors.
Lower-bound conclusion: The disjoint-support construction transfers this error fraction from the finite point set to at least 50% · (1 − o(1)) of the data distribution’s probability mass.The construction uses O(k)-sparse inputs grouped so their supports are disjoint while matching the overall distribution.