Feature Purification: How Adversarial Training Performs Robust Deep Learning

1 Introduction

• Adversarial training with FGM can efficiently raise a two-layer ReLU network from near-zero to near-perfect robust accuracy against worst-case norm-bounded perturbations.This holds for certain binary classification data sets under gradient-descent training from random initialization, even though clean training remains non-robust despite weight decay, infinite data, and super-polynomially many iterations.Source: §1 · p. 3
• Feature purification changes only a small part of each learned feature: most clean- and adversarially-trained neurons remain strongly correlated, while different neurons remain weakly correlated.The theory gives C = 1 −o(1) for most corresponding neurons and c = o(1) for most distinct pairs.Source: §1 · pp. 4–5
• Clean training learns well-generalizing features that contain dense mixtures, which have low correlation with individual clean examples but are vulnerable to small perturbations along their directions.Under sparse coding, gradient descent accumulates these mixtures in each neuron; adversarial training removes them to purify the features.Source: §1 · pp. 3, 5
• The theory explains adversarial-example transfer by showing that dense mixtures arise from the sparse coding structure and gradient descent rather than random initialization, so attacks transfer across independently trained networks.The paper also empirically observes feature purification in deeper architectures such as AlexNet and ResNet on real-world data sets.Source: §1 · pp. 4–5
• Linear classifiers, low-degree polynomials, and the corresponding neural tangent kernel cannot achieve meaningful robust accuracy in the studied sparse coding model, although they can achieve high clean accuracy.The result establishes a complexity separation: a higher-complexity ReLU network can robustly learn the task because low-complexity models cannot zero out low-magnitude signals.Source: §1 · p. 5, §1.1 · pp. 6–7

1.1 Related Works

• Prior theories mainly attribute adversarial examples to finite-sample overfitting, high-dimensional effects, Fourier signals, or linear-model limitations, whereas this work studies learned hidden features in ReLU networks.Its contribution is a first theoretical treatment, for certain structured tasks, of how random-initialized neural-network training creates non-robust features and how adversarial training changes them.Source: §1 · pp. 2–4, §1.1 · p. 6

• Inputs follow a sparse-coding model x = Mz + ξ with D = d and unitary M, isolating dense mixtures as an intrinsic gradient-descent effect rather than feature correlation.The results extend to D < d or incoherent dictionaries, while lower bounds allow ξ = 0.Source: §2 · pp. 7–8
• The hidden vector z has independent, symmetric coordinates whose nonzero magnitudes are sparse and typically small, with w.h.p. ∥z∥0 = Θ(k).The sparsity regime assumes k ≤ d^0.499, and coordinates can attain a maximum value with nontrivial probability.Source: §2 · p. 7
• The binary classification task uses a labeling function linear in the hidden vector z, with extensions to other target vectors w⋆ at the cost of more notation.The sparse-coding model serves as a bridge for distinguishing neural-network clean and adversarial training, not as a claim that neural networks perform sparse coding.Source: §2 · pp. 7–8
• Upper bounds tolerate Gaussian-plus-spike noise, including Euclidean noise O(σx) larger than the signal and coordinate spikes up to 1/k^0.501.The model permits arbitrary constant σx, while lower bounds remain valid without noise.Source: §2 · p. 8
• Clean error measures disagreement between sign(f(x)) and y, whereas robust error is the probability that some δ with ∥δ∥p ≤ τ changes the prediction.The robust-error definition applies to ℓp adversarial perturbations of radius τ.Source: §2 · p. 8

Linear learners are not robust

• Linear classifiers fail under substantial feature noise because noise can overwhelm the O(1) signal, preventing meaningful clean accuracy even for constant-degree polynomials.When σ_x is at least Θ(1), the noise may be much larger than the signal.Source: §3 · p. 8
• Even with perfectly linearly classifiable data, no linear classifier remains robust to adversarial perturbations of the same small ℓ2-radius scale.An adversary can shift inputs along the classifier’s signal direction and change its prediction.Source: §3 · p. 9

High-complexity models are more robust

• Higher-complexity models use indicator-like features to preserve nonzero signals while zeroing low-magnitude signals, yielding substantially greater robustness than linear models.The construction achieves 1 − o(1) robust accuracy against perturbations of radius o(…), and is information-theoretically optimal.Source: §3 · p. 9

Learning robust classifier using neural network

• Adversarial training can make a symmetric two-layer ReLU network recover hidden features forming an input basis with sparse coefficients, while clean training does not learn this robust function.The paper also reports that adversarially trained AlexNet features reconstruct images using sparse linear combinations.Source: §3 · p. 9
• Adversarially trained AlexNet features reconstruct original images with average sparsity of 4.05% or less.This experiment supports the claim that learned first-layer features form a sparse basis.Source: §3 · p. 9, Figure 4 · p. 10

4 Learner Network and Adversarial Training

• The learner is a symmetric two-layer ReLU network with paired hidden weights, Gaussian pre-activation noise, fixed output weights, and weight-decay-style regularization.The pre-activation noise smooths ReLU gradients, while symmetry is assumed to simplify proofs.Source: §4 · p. 10

4.1 Clean Training

• Clean training applies gradient descent to hidden weights on the original data, with bias growth increasing activation sparsity during training.The procedure uses randomly initialized hidden weights and staged bias growth, including a later phase in which winning neurons grow significantly.Source: §4.1 · p. 11, §4.2 · p. 11

4.2 Adversarial Training

• Adversarial training starts from a clean-trained network, repeatedly perturbs training examples with an attacker, and then performs gradient descent on the perturbed data.The initialization supports isolating feature changes; the theory attributes the remaining o(1) feature change to dense-mixture directions and predicts direct avoidance from random initialization.Source: §4.2 · pp. 12–13
• Adversarial training achieves small empirical robust error for all perturbation algorithms in Definition 4.2, while FGM can yield small true robust error.The robust-error guarantee applies to perturbations satisfying the stated boundedness or Lipschitz condition; FGM satisfies these properties.Source: §4.2 · pp. 12–13

5.1 Clean Training, Adversarial Training and ℓ2 Robustness

• Clean training attains o(1) clean error but suffers 1−o(1) error under a small dense perturbation, even with super-polynomial iterations and infinitely many examples.The perturbation δ = −τ yMw⋆/∥Mw⋆∥2 does not depend on the trained network, and the failure is therefore not attributed to overfitting.Source: §5.1 · p. 14
• Clean training produces features containing a Θ(1) robust component plus a small dense mixture that barely affects clean accuracy but is highly vulnerable to dense adversarial perturbations.The mixture accumulates because local gradients correlate with the dense direction Mw⋆; adversarial training removes it, purifying the hidden weights and making perturbations more data-aligned.Source: §5.1 · pp. 14–15
• The model has o(1) error against some radius-τ perturbation of norm at most τ and o(1) error under the training perturbation algorithm A(ft, x, y, r).Source: §5.1 · p. 15

5.2 ℓ∞Robustness and Lower Bound for Low-Complexity Models

• For ℓ∞ perturbations, clean training remains non-robust while adversarial training is robust against any perturbation of radius τ = 1/k^(1.75+2c0), with the gap persisting as c0 and c1 approach zero.The result assumes ∥M∥∞ and ∥M∥1 are d^o(1), with k ∈ [d^c1, d^0.399].Source: §5.2 · p. 17
• When m ≤ d^C, the corresponding NTK has robust error 1−o(1) against ℓ∞ radius τ = 1/k^100, and constant-degree polynomials likewise have robust error at least 1−o(1).The lower bound holds even for M = I and σ_x = 0, where the original concept class is linearly separable; adversarially trained neural networks achieve radius τ = 1/k^1.76 instead.Source: §5.2 · p. 17

6.1 Wining Lottery Tickets Near Random Initialization

• Gradient descent first discovers feature-aligned neurons near random initialization, despite classification accuracy remaining around 50% while the loss is not yet sufficiently minimized.This lottery-ticket phase differs from neural tangent kernel analysis because ReLU activation patterns change dramatically, even as neuron weights remain controllable.Source: §6.1 · pp. 17–18
• With mild over-parameterization m ≥ d^1.01, every feature has at least one lottery-ticket neuron while each feature has at most d^0.01 potential tickets.Random Gaussian initialization produces potentially lucky neurons with slightly elevated feature correlation and surely lucky neurons with a unique elevated correlation; winning neurons later grow toward the corresponding feature.Source: §6.1 · p. 18

6.2 The Formation of “Dense Mixtures” During Training

• After lottery tickets are won, clean training preserves each neuron’s winning feature while accumulating a small dense mixture of the remaining features in its hidden weight.The mixture contributes negligibly on clean inputs because it is weakly correlated with any particular natural input, yet it can strongly alter network outputs under small dense perturbations.Source: §6.2 · p. 19
• These universal dense perturbations make the well-trained network non-robust, while adversarial examples expose their correlations and purify the mixtures through only small neuron changes.Clean-training gradients accumulate the dense direction Mw⋆ because they follow local label correlation without checking whether the direction supports the final classifier; this mechanism also explains transfer attacks.Source: §6.2 · p. 20

7 Conclusion

• Clean training accumulates dense mixture directions across features, while adversarial training purifies these mixtures and improves robustness.The mixtures have low correlation with natural inputs but are highly vulnerable to dense adversarial perturbations.Source: §7 · p. 21
• Non-robustness arises from both stochastic gradient descent’s inductive bias and the sparse-coding structure of the data.Both factors are necessary in the paper’s analysis.Source: §7 · p. 21
• Even with regularization and infinite training examples, gradient descent can favor non-robust models, whereas some mixture-of-Gaussians tasks yield optimal robust accuracy under clean training.The conclusion contrasts these cases to motivate analyzing both the optimization algorithm and input structure.Source: §7 · p. 21
• Future work should address richer natural-image structure and extend feature purification to clean and robust training of multilayer networks.The authors suggest that hierarchical purification may occur in deep networks, as indicated by their Figure 10 experiments.Source: §7 · p. 21

8 Experiment Details

• Experiments use AlexNet, ResNet-16, and ResNet-34 with basic blocks on CIFAR-10, using standard data augmentation and SGD with 0.9 momentum.Random crops and random flips are used for augmentation; implementations come from the cited classification repository.Source: §8 · p. 22, §8.1 · p. 22
• Training evaluates ℓ2 attackers with parameters ℓ2(1, 0.25) and ℓ2(0.5, 0.12), plus 7-step PGD attacks at ℓ∞ radii 4/255 and 8/255.The study primarily focuses on ℓ2(1, 0.25), while comparing attackers in Section 8.4.Source: §8 · p. 22, §8.1 · p. 22
• Clean training followed by adversarial training from clean-trained initialization does not affect overall robust or clean accuracy.Table 1 reports robust and clean accuracies for vanilla clean and adversarial training against the evaluated attackers.Source: §8 · p. 22, Table 1 · p. 22

8.1 Feature Visualization of Deeper Layers

• Robustly trained models yield visually meaningful deep-layer feature visualizations, unlike cleanly trained models, because adversarial training removes harmful dense mixtures.This supports the paper’s feature-purification interpretation of deep representations.Source: §8.1 · p. 23, Figure 10 · p. 23

8.2 Feature Purification at Deeper Layers

• The deeper-layer purification experiment tests whether the single-layer feature-purification principle appears in practice through local purification at each layer.Deep features are visualized by taking 2000 gradient steps from a random image, with weight decay toward RGB (128,128,128), except Figure 6.Source: §8.1 · pp. 22–23, §8.2 · p. 23

adversarial training

• Adversarial training purifies features even in deep ResNet-34 layers, while clean training of later layers can reduce robust accuracy to 0% despite fixed robust earlier features.Figure 11 compares random, clean, and robust training after freezing earlier layers; the reported schedule stops when robust and clean accuracy match stage 1.Source: Figure 11 · p. 24, adversarial training · p. 25

8.3 Sparse Reconstruction of Input Data and of Adversarial Perturbation

• Robust features reconstruct input images with better sparsity than clean features, while clean-model adversarial perturbations are denser than robust-model perturbations and robust-model perturbations are closer to real input images.In experiments, clean delta almost lies in the span of robust features, with regression error < 0.00005 for AlexNet and < 10^-9 for ResNet.Source: §8.3 · pp. 25–26

8.4 Comparing Different Attackers

• Feature purification occurs against several different attackers, as demonstrated by visualizing the 27-th ResNet-34 convolutional layer.The paper explicitly reports this result in Figure 13.Source: §8.4 · p. 26, Figure 13 · p. 26

8.5 Feature Purification is a Low-Rank Update

• Low-rank adversarial updates can recover robustness from clean-trained models: rank-1 updates use less than 1% of parameters for over 80% of maximum robust accuracy, while rank 8* uses about 5% for over 90%.The experiment evaluates CIFAR-10 ResNet-28 and widened variants, comparing clean, traditional adversarial, and low-rank-updated training.Source: §8.5 · pp. 27–28, Figure 14 · p. 27

Appendix: Complete Proofs

• The appendix proves that lucky neurons amplify aligned directions faster than other directions, eventually yielding mostly pure-plus-dense-mixture neurons and explaining clean accuracy, non-robustness, and FGM-based mixture removal.Sections C–F cover neuron growth, clean accuracy, accumulated dense mixtures, and both ℓ2 and ℓ∞ adversarial training.Source: Appendix: Complete Proofs · p. 29

A Notations and Warmups

• The warmup analysis establishes polynomial-sample training conditions and a high-probability gradient concentration result under bounded weights, Gaussian perturbations, and sufficiently large sample size.The stated probability guarantee is at least 1 − e^(-Ω(log^2 d)).Source: A Notations and Warmups · p. 30

B Neuron Structure and Initialization Properties

• The neuron-structure analysis defines potentially and surely lucky neurons through directional alignment, sign consistency, and sparse-versus-dense correlations across feature directions.At initialization, the required properties for surely lucky neurons need not hold, but the paper states that they emerge progressively during training.Source: B Neuron Structure and Initialization… · pp. 30–31

B.1 Proof of Lemma B.2

• Gaussian tail probabilities are bounded above and below for every t > 0 using standard normal tail estimates.The displayed bounds compare Pr[g > t] with expressions involving t, 2π, and exp(−t^2/2).Source: §B.1 · p. 32
• Concentration over all m samples lower bounds |S(0)_{j,sure}| with probability at least 1 − o(1/d^3).The proof first obtains a per-sample probability involving p1/2 · (1 − p2)^(d−1), then applies concentration.Source: §B.1 · p. 32
• Concentration similarly upper bounds |S(0)_{j,pot}|, with the per-sample probability controlled by p2 < O(1/√log d)·d.The resulting statement holds simultaneously over all m choices of i with probability at least 1 − o(1).Source: §B.1 · p. 32
• A chi-square tail bound and a union bound show that, with probability at least 1 − 1/d^4, all but O(1) coordinates satisfy the required bound for S(0)_{ept}.The proof bounds the relevant squared inner products for each i and then unions over i ∈ [m].Source: §B.1 · p. 32
• For nearly all coordinates, squared initialization correlations satisfy ⟨w_i^(0), M_j⟩^2 ≤ 2σ_0^2√log d with probability 1 − o(1/d^3).At least d(1 − 2^(−√log d)) indices j satisfy this condition.Source: §B.1 · p. 32
• A separate small-correlation event holds for a fraction 1/(100000√log d) of coordinates, based on the threshold σ_0/(10000√log d).The per-pair event has probability at least 1/(40000√log d), and concentration yields the stated coordinate count with probability 1 − o(1/d^3).Source: §B.1 · p. 32

C Neuron Structure Change During Training

• Phase I keeps binary-classification accuracy at 50% while some neurons begin forming singleton structures; Phase II produces more meaningful outputs and makes these neurons even more singleton.Theorem C.1 and Theorem C.2 hold with probability at least 1 − e−Ω(log2 d) under the stated initialization, parameter, and width conditions.Source: C Neuron Structure Change During… · p. 33
• Theorem C.2 directly implies the first claims of Theorems 5.1 and 5.2 after substituting the definitions of the neuron-structure sets.The derivation also uses the stated bounded-cardinality observations for the relevant neuron sets.Source: C Neuron Structure Change During… · pp. 33–34

C.1 Auxiliary Lemma 1: Geometry of Crossing Boundary

• Lemma C.4 bounds the size of each neuron’s pre-activation signal by controlling rare large-coordinate and boundary-crossing events with concentration arguments.The proof uses event decompositions, union bounds, and Bernstein concentration.Source: §C.1 · p. 34

C.2 Auxiliary Lemma 2: A Critical Lemma for Gradient Bound

• Lemma C.5 provides a critical gradient bound for center-symmetric functions under symmetric distributions, with an additional bound when the function is monotone non-decreasing.Its proof controls threshold-crossing probabilities and separates cases based on the magnitude of S2.Source: §C.2 · pp. 35, 37

C.3.1 Activation Probability

• During Phase I, activation probabilities are bounded by Γt, with Γt = e−Ω(log1/4 d) in Phase I.1 and Γt = O(k d) in Phase I.2.In both cases, Γt,y = 1 d10; the analysis also establishes a large auxiliary coordinate subset under the relevant activation-set assumption.Source: §C.3.1 · pp. 37–38

C.3.2 Growth Lemmas

• The Phase I growth lemma lower-bounds growth of ⟨w_i(t), M_j⟩ for neurons in Sj,sure by combining activation estimates with the critical gradient bound.The argument applies Lemma C.5 using variance, signal, tail-probability, and large-subset bounds from Lemma C.7.Source: §C.3.2 · pp. 38–39
• The Phase I growth lemmas separately bound maximum, non-signal, and noise growth across phases, including exponentially unlikely large-noise events.Lemma C.9 covers maximum growth, Lemma C.10 non-signal growth, and Lemma C.11 noise growth.Source: §C.3.2 · pp. 38, 40

C.3.3 Proof of Theorem C.1

• Theorem C.1 is proved inductively by substituting the growth lemmas into the gradient update and verifying signal, non-signal, initialization, and iteration-time properties.The proof applies in both Phase I.1 and Phase I.2 and uses bounds on the evolving weight scale and active-neuron sets.Source: §C.3.3 · pp. 41–43

C.4 Phase II: Signal Growth After Winning Lottery

• The Phase II parameterization grows b(t) until it reaches βΞ2 and defines coordinate Lipschitz constants with probability at least 1 − e^−Ω(log2 d).Coordinate Lipschitzness compares inputs differing in one coordinate while holding the remaining latent variables and noise fixed.Source: §C.4 · p. 43

C.4.1 Growth Lemmas

• Phase II introduces new growth lemmas for signal, maximum, non-signal, and noise terms, replacing the corresponding Phase I lemmas.The analysis relies on high-probability coordinate Lipschitzness and decomposes noise contributions to obtain finer bounds.Source: §C.4.1 · pp. 43, 45
• Growth lemmas establish bounds on neuron and coordinate evolution used throughout the subsequent proof.The argument completes Lemma C.17a and Lemma C.17b before applying these growth estimates later.Source: §C.4.1 · pp. 47–48

C.4.2 Growth Coupling

• Growth coupling shows neurons sharing a relevant coordinate grow in roughly the same direction, independently of the neuron index.The proof distinguishes positive and negative coordinate cases and uses corresponding activation-probability bounds.Source: §C.4.2 · p. 48

C.4.3 Activation Probabilities

• Activation-probability bounds quantify when neurons activate after the ept+ condition, with high-probability concentration over neurons.Bernstein’s inequality is used to obtain simultaneous bounds for every neuron.Source: §C.4.3 · pp. 48–49

C.4.4 Coordinate Lipscthizness Bound

• Coordinate Lipschitzness bounds the contribution of active neurons outside S(t), controlling their aggregate effect on each coordinate.The bound follows from the activation lemma and the randomness of the neuron offsets ρ_i.Source: §C.4.4 · p. 49

C.4.5 Regularization

• Regularization proves high-probability regularity and a loss lower bound by combining growth, concentration, and coordinate-Lipschitz arguments.The analysis shows that independently constructed examples can receive different labels with probability at least Ω(√α), forcing either substantial loss or bounded outputs.Source: §C.4.5 · pp. 50–52

C.4.6 Proof of Theorem C.2

• Theorem C.2 is proved inductively through Phase II: losses remain o(1) over an initial interval, while relevant inner products grow to a target scale and thereafter stay above a lower threshold.The proof uses the preceding lemmas and regularity bounds to control potential-coordinate sets and establish the Phase II.1 invariant.Source: §C.4.6 · pp. 52–54
• The induction argument assumes (C.25) at t and proves its preservation at t + 1.The first half is derived by combining Lemmas C.18 and C.17a with the bound on β, while taking differences using (C.26).Source: §C.4.6 · pp. 54–55
• A two-case analysis verifies the second half of (C.25) at t + 1.The argument invokes the first half of (C.25), Lemma C.20, Lemma C.14, and Lemma C.17a to control the relevant quantity.Source: §C.4.6 · p. 55
• The controlled norm is bounded by O(k(b(t))^2) = o(1), completing the second-half verification.This small-norm estimate is used together with Lemmas C.14 and C.17a in the final step.Source: §C.4.6 · p. 55

D Clean Accuracy Convergence Analysis

• At least 99% of iterations after Te achieve population risk o(1) and clean population accuracy ≥1−o(1), under Theorem D.1’s stated conditions.The theorem holds with probability at least 1−e^−Ω(log^2 d) for the specified training horizon and parameter assumptions.Source: D Clean Accuracy Convergence Analysis · p. 56
• With additional work, Theorem D.1 can hold simultaneously with high probability for every T∈[Tc,Tf], although this extension is not proved.The paper notes that the omitted argument would complete the notation but lies outside its scope.Source: D Clean Accuracy Convergence Analysis · p. 56

D.1 Proof of Theorem D.1: Convergence Theorem

• The convergence proof approximates the neural network at each iteration with a linear coupling function that matches the real network at μ=w(t) to zero and first order.This coupling function is introduced as the proof’s first-order approximation of the neural network.Source: §D.1 · p. 56
• The proof constructs a special parameter μ⋆ from disjoint initialization-related sets and chooses an auxiliary parameter α=o(1).The construction uses the disjoint sets S(0) and a later choice of α, with properties checked using Lemma B.2.Source: §D.1 · p. 56
• With probability at least 1−e^−Ω(log^2 d), the constructed μ⋆ yields g_t(μ⋆;x,ρ)=α⟨w⋆,z⟩±O(1) under the stated random variables.This property is identified as a key fact about μ⋆ and is proved in Section D.2.Source: §D.1 · p. 56
• After Te, the analysis defines a pseudo-objective that is convex in μ because the coupling function g_t(μ;x,ρ) is linear in μ.The proof relates the actual objective to this convex pseudo-objective before deriving the iteration-wise bound.Source: §D.1 · pp. 56–57
• Telescoping the iteration-wise inequality from t=Te through Te+T−1, with η≤1/poly(d), completes the convergence bound.The proof combines the coupling definition, Lemma D.6b, Theorem C.2, and Claim D.5 before telescoping.Source: §D.1 · p. 57

Main coupling

• The proof splits g_t(μ⋆; x) = g_{t,1} + g_{t,4} and bounds the two terms separately.This decomposition supplies the two components used to prove Lemma D.6a.Source: §D.2 · p. 57
• With probability at least 1 − e^−Ω(log^2 d), g_{t,1}(μ⋆; x) = α⟨w⋆, z⟩ over x and ρ.The result holds for the specified j,sure and j ∈ [d] conditions in the supplied proof passage.Source: §D.2 · p. 58
• The fluctuation g_{t,4}(z, ξ, ρ) is treated as a function of independent variables z, ξ, and ρ, enabling separate sensitivity analysis.The proof explicitly represents g_{t,4} through independent variables ξ_1, …, ξ_d, z_1, …, z_d, and ρ_1, …, ρ_m, with component functions g_{t,4,i}(z, ξ, ρ_i).Source: §D.2 · p. 58
• Applying high-probability McDiarmid bounds to perturbations in z and ξ, and using E_z,ξ[g_{t,4}(z, ξ, ρ)] = 0, completes the proof of Lemma D.6a.The argument applies McDiarmid’s inequality twice, after establishing bounded sensitivities for z and ξ, and concludes with the zero expectation of g_{t,4}.Source: §D.2 · pp. 58, 60, 61
• Lemma D.6b is then proved using Lipschitz continuity of log(1 + e^−x), followed by expectation and the exponential tail bound.The supplied proof states that this final step completes Lemma D.6b.Source: §D.2 · p. 61

E Why Clean Training is Non-Robust

• Clean training is provably non-robust to ℓ2 perturbations of size τ = Ω under the theorem’s initialization, width, and iteration assumptions.The result holds with high probability over the initialization event and training randomness.Source: E Why Clean Training is Non-Robust · p. 61
• Near the end of clean training, neurons develop a small common direction in Mw⋆, which is the key structural ingredient behind the vulnerability.Lemma E.2 supplies the shared-direction property used in the proof of Theorem E.1.Source: E Why Clean Training is Non-Robust · pp. 61–62

E.2 Proof of Theorem E.1

• Perturbing each input in the direction −y·Mw⋆ can change the network output dramatically, reversing its sign on the perturbed input.The proof analyzes both x − δ and x + δ before selecting the label-dependent direction.Source: E Why Clean Training is Non-Robust · p. 62, §E.2 · p. 65

E.1 Proof of Lemma E.2: Common Direction Among Neurons

• Claim E.3 and auxiliary lemmas bound neuron contributions and establish the shared-direction behavior required by Lemma E.2.The proof combines recalled identities, norm bounds, and small-ball probability estimates.Source: §E.1 · pp. 62–63
• Lemma E.2 is obtained by combining Claim E.3 with high-probability estimates and auxiliary lemmas controlling the relevant neuron terms.The argument uses Lemmas C.19, C.21, C.22, and H.1a as stated in the proof passages.Source: §E.1 · pp. 62–63

E.2 Proof of Theorem E.1

• The resulting robust accuracy is below e−Ω(log2 d), and the final norm bound completes the proof of Theorem E.1.The argument combines bounds over neuron subsets with the condition k > d(1−c0)/3 and uses ∥Mw⋆∥2 ≤ O(∥M∥1).Source: §E.2 · pp. 64–65

F Robust Training Through Local Feature Purification

• The robust-training theorems apply to every norm-bounded adversarial perturbation algorithm A, including the Fast Gradient Method.The algorithm receives the current network, input, label, and internal random string, then outputs a norm-bounded perturbation.Source: F Robust Training Through Local… · p. 65
• Theorem F.4 establishes ℓ∞ robust convergence after clean pretraining followed by T = Tg robust-training iterations under stated σx, k, and perturbation-radius conditions.The guarantee holds with probability at least 1 − e^−Ω(log^2 d) against an ℓ∞ perturbation algorithm A.Source: F Robust Training Through Local… · p. 66
• For ℓ∞ perturbations, robust training gives 99.9% accuracy for k ∈ [d^0.0001, d^0.3999] at radius ≥ 1/(k^1.75·d^0.0001·∥M∥∞), while clean training gives 0.01% for k ≥ d^0.3334 at radius ≤ d^0.0001∥M∥1/k^2.For k ∈ [d^0.3334, d^0.3999] and ∥M∥∞, ∥M∥1 ≤ d^0.1248, robust training provably beats clean training in ℓ∞ robust accuracy.Source: F Robust Training Through Local… · p. 66

F.1 Some Notations

• The analysis records neuron structure at the clean-training endpoint, decomposing each hidden weight into signal-aligned and remaining components with bounded support and correlations.These structural properties are introduced as corollaries of Theorem C.2 and support the subsequent robust-training analysis.Source: §F.1 · p. 67

F.2 Robust Coupling

• Robust coupling approximates the real network by a linearized function matching its value and first-order behavior, with closeness analyzed separately for ℓ2 and ℓ∞ perturbations.The coupling depends on controlling perturbation norms and individual-neuron quantities, motivating the separate norm-specific analyses and growth lemmas.Source: §F.2 · p. 67

F.2.1 Robust Coupling for ℓ2 Perturbation

• In both settings, perturbation vectors δ may depend on x but not on ρ: the ℓ2 case assumes ∥δ∥2 ≤τ, while the ℓ∞ case assumes ∥δ∥∞≤τ.Source: §F.2.1 · p. 68, §F.2.2 · p. 71

F.3 Individual Neuron Growth Lemma

• The individual-neuron growth analysis bounds post-training neuron movement, with the ℓ2 movement lemma controlling updates under bounded perturbations and bounded prior neuron norms.The section’s stated purpose is to upper-bound max_i∈[m] ∥v_i^(Tf+T)∥1 for ℓ∞ perturbations and the analogous ℓ2 quantity.Source: §F.3 · p. 72, §F.3.1 · p. 73

F.3.2 Growth Lemma for ℓ∞Perturbation

• Under a bounded ℓ1-norm condition on hidden weights, robust training admits an ℓ∞ movement-growth corollary subject to a step-size and iteration constraint.The bound is derived from the movement lemma and the assumption that ∥v_i∥1 remains at most r′ throughout the robust-training interval.Source: §F.3.2 · p. 75

F.4 Robust Convergence

• The robust-convergence analysis is introduced as the argument establishing the paper’s main convergence theorems for robust learning.The surrounding proof framework first calculates a simple bound before proceeding to the theorem-specific convergence arguments.Source: §F.4 · p. 76

F.4.2 Robust Convergence for ℓ∞Perturbation

• The main robust-convergence proof is organized around an induction over iterations from Tf through Tf + T, followed by calculations specialized to the ℓ∞ perturbation setting.The proof explicitly states that it is nearly identical to the ℓ2 convergence proof, but that certain calculations must be redone using Lemma F.14 and Claim F.17.Source: §F.4.2 · p. 78

F.5 Fast Gradient Method (FGM) Robust Training

• The ℓ∞ analogue is stated to follow completely analogously from the ℓ2 proof of Corollary F.2.The appendix explicitly proves the ℓ2 case while identifying Corollary F.5 as the analogous ℓ∞ case.Source: §F.5 · p. 78
• The robustness proof considers every iteration t ∈ [T_f,T_f+T_g] and perturbations δ that may depend on x but satisfy ∥δ∥2≤τ.The perturbation vector may depend on the input but not on ρ.Source: §F.5 · p. 78
• The proof uses δ⋆=A(f_t,x,y), the fast-gradient perturbation with ℓ2 radius τ, and the linearity of g_t in δ.The argument first applies the relevant inequality to δ⋆ and then extends the conclusion to all perturbations of radius τ.Source: §F.5 · p. 79
• FGM-trained network outputs are robust at almost all inputs against any perturbation δ with radius τ.The proof combines bounds holding on probability masses at least 1−O(1/log d) and 1−o(1), then applies the FGM perturbation δ⋆.Source: §F.5 · p. 79

G NTK Lower Bound For ℓ∞Perturbation

• For the NTK lower bound, the analysis uses the simplest input distribution with M=I and σ_x=0, so ξ≡0, and writes the NTK function from the feature mapping and weights.The NTK function p(x) is defined given the weights {v_i}_{i∈[m]}.Source: G NTK Lower Bound For ℓ∞Perturbation · p. 79
• With probability at least 1−e^−Ω(log^2 d), the NTK theorem applies at τ=1/d^c6 for sufficiently large d under its stated Gaussian-weight, width, bias, and variance conditions.The theorem assumes i.i.d. w_i∼N(0,I), m≤d^C, |σ_ρi|≤d^o(1), and |b_i|≤d^o(1).Source: G NTK Lower Bound For ℓ∞Perturbation · p. 80

G.1 Proof of Theorem G.1

• Gaussian perturbation converts ℓ∞ robustness into a smoothed analysis of the NTK function, enabling Taylor expansion of its indicator components.The proof sacrifices the radius from τ to τ/2 while using ζ ∼ N(0, τ^2) to smooth the function.Source: §G.1 · p. 80
• At least 50% · (1 −o(1)) of the data-distribution probability mass is misclassified under ℓ2 perturbations of radius τ.The argument first obtains the same fraction among paired disjoint-support points, then transfers it to the data distribution.Source: §G.1 · p. 82

G.2 Tensor Lower Bound

• For Gaussian-initialized hidden weights with r ≥ 3C, Lemma G.4 lower-bounds the Frobenius norm of each relevant symmetric tensor with probability at least 1 −e−Ω(log2 d).The lemma applies when m ≤d^C and uniformly accommodates arbitrary vectors that may depend on the sampled weights.Source: §G.2 · pp. 82–83

G.3 Tensor Perturbation

• Lemma G.5 shows that bounded, disjoint-support perturbations can expose a symmetric tensor’s magnitude, using Gaussian anti-concentration and tensor multilinearity.For the Gaussian choice, |T(δ⊗r)| is at least Ω(∥T∥F) with constant probability under the stated perturbation constraints.Source: §G.3 · pp. 83–84

G.4 Smoothed ReLU Taylor Series: Proof of Claim G.3

• The smoothed-ReLU expansion decomposes the NTK terms into polynomial components whose coefficients satisfy the bounds required by Claim G.3.The calculation applies the smoothed-ReLU formula to Gaussian variables formed from the hidden weights and perturbation noise, under the condition bi ≪d−0.2 ≪σ.Source: §G.4 · pp. 84–86

G.5 Simple Lemmas

• The simple lemmas relate constant-degree polynomial values to coefficients and compare symmetric-tensor norms through polynomial representations.These results support the tensor and polynomial estimates used in the preceding proof steps.Source: §G.5 · p. 86

H.1 Small ball probability: The basic property

• The small-ball lemma provides one-dimensional anti-concentration bounds for sums with sufficiently many active coordinates.Its proof combines Chernoff concentration, the Littlewood–Offord theorem [30], and a Wasserstein-distance central-limit estimate.Source: §H.1 · p. 87

H.2 McDiarmid’s Inequality and An Extension

• The appendix states McDiarmid’s inequality for independent variables under coordinate-wise bounded differences and introduces a more general extension.The standard setup bounds the change in f by ci when one coordinate is replaced.Source: §H.2 · p. 88
• The McDiarmid extension is proved by conditioning on progressively larger subsets of independent variables and controlling the resulting deviations with high-probability events.The proof constructs events K≤t, truncated variables X_t, and bounds their increments before applying martingale concentration.Source: §H.2 · pp. 88–89
• The construction yields a truncated terminal variable that agrees with f(w1, . . . , wN) except on a controlled failure event, completing the desired theorem.The proof states agreement with probability at least 1 −2N√p and concludes that the required result follows.Source: §H.2 · p. 89
• Lemma H.4 supplies a one-sided Bernstein form of martingale concentration for submartingale sequences, with its proof based on exponential-moment bounds.The derivation invokes ey ≤1+y +y2 for y ≤0.5 and conditional expectation.Source: §H.2 · p. 90