PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence of Adversarial Training in Overparametrized Neural Networks

Ruiqi Gao, Tianle Cai, Haochuan Li, Liwei Wang, Cho-Jui Hsieh, Jason D. Lee

arXiv:1906.07916v2cs.LGstat.ML

TL;DR

Neural networks remain vulnerable to small adversarial perturbations, while adversarial training’s convergence and ability to reach low robust loss were not previously clear. This paper analyzes over-parameterized networks using NTK-based techniques and heuristic-optimization ideas, showing convergence near optimal robust loss and sufficient expressivity for small robust loss. It also finds that robust interpolation requires more capacity.

  • Problem

    Adversarial training is effective in practice, but its convergence properties and the existence of networks with small robust error remain unclear.

    Source: §1 · p. 2

  • Method

    The paper analyzes over-parameterized deep and two-layer networks using NTK-based convergence arguments, including arbitrary heuristic attack algorithms and robust expressivity.

    Source: §1 · p. 2

  • Results

    For sufficiently wide networks, adversarial training converges within ǫ of optimal robust loss, and the networks can achieve optimal robust loss ǫ.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The results indicate that adversarial training finds networks with low robust surrogate and training loss, while robust interpolation requires greater model capacity.

    Source: §1 · p. 3, §7 · p. 13

    Several theoretical questions remain unanswered, including limitations associated with the current treatment of projection steps and directions for improvement.

    Source: §7 · pp. 13–14

Abstract

from arXiv · show

Neural networks are vulnerable to adversarial examples, i.e. inputs that are imperceptibly perturbed from natural data and yet incorrectly classified by the network. Adversarial training, a heuristic form of robust optimization that alternates between minimization and maximization steps, has proven to be among the most successful methods to train networks to be robust against a pre-defined family of perturbations. This paper provides a partial answer to the success of adversarial training, by showing that it converges to a network where the surrogate loss with respect to the the attack algorithm is within $\epsilon$ of the optimal robust loss. Then we show that the optimal robust loss is also close to zero, hence adversarial training finds a robust classifier. The analysis technique leverages recent work on the analysis of neural networks via Neural Tangent Kernel (NTK), combined with motivation from online-learning when the maximization is solved by a heuristic, and the expressiveness of the NTK kernel in the $\ell_\infty$-norm. In addition, we also prove that robust interpolation requires more model capacity, supporting the evidence that adversarial training requires wider networks.

1 Introduction

The paper analyzes adversarial training in over-parameterized neural networks and shows convergence toward low robust loss under broad attack settings. It also establishes that robust interpolation requires greater capacity than ordinary interpolation.

Motivation

  • Adversarial examples motivate robust-loss optimization because small imperceptible perturbations can change predictions, while adversarial training has become a leading defense.The robust loss maximizes loss within each sample’s perturbation neighborhood.Source: §1 · p. 2

Convergence guarantees

  • Projected gradient descent converges within ǫ of the optimal robust loss for sufficiently wide deep ReLU networks under arbitrary attack algorithms.The required width is polynomial in the depth and input dimension.Source: §1 · p. 2
  • Two-layer networks with smooth activations admit a convergence proof without requiring the algorithm’s projection step.This is given as Theorem 5.1.Source: §1 · p. 2

Robust expressivity

  • Sufficiently wide neural networks can achieve optimal robust loss ǫ, establishing their expressivity for robust interpolation.The precise statement is given in Theorems 5.2 and C.1.Source: §1 · p. 2

Robust training outcome

  • Adversarial training finds networks with small robust training loss by combining convergence to near-optimal surrogate loss with neural-network expressivity.This result is stated for sufficiently wide networks.Source: §1 · pp. 2–3

Capacity requirement

  • Robust interpolation requires higher capacity: its model class has VC-Dimension at least Ω(nd), versus architectures interpolating n samples with O(n) parameters and VC-Dimension at most O(n log n).Here d denotes the input dimension.Source: §1 · p. 3

2 Related Work

Related work covers adversarial attacks and defenses, theoretical analyses of adversarial training, over-parameterized gradient descent, and certified robustness. The paper addresses convergence difficulties arising from heuristic inner maximization methods.

Attack and defense

  • Adversarial attacks include PGD, L-BFGS, FGSM, iterative FGSM, and C&W, which differ in distance measures, loss functions, or optimization algorithms.Related work also considers black-box attacks with limited model information.Source: §2 · p. 3
  • Many defense methods rely on obfuscated gradients and fail under stronger attacks, whereas adversarial training was reported to remain effective under carefully designed attacks [3].The related work identifies adversarial training [31] as a notable exception.Source: §2 · p. 3

Adversarial training

  • Adversarial training approximates min-max robust-loss optimization by repeatedly generating adversarial samples and minimizing loss on them, achieving state-of-the-art robustness under strong attacks.PGD-based procedures implement this formulation, although the approach can be slow because each update includes several attack steps.Source: §2 · pp. 3–4

Global convergence

  • Standard over-parameterized gradient-descent analyses use full-rank Jacobians near random initialization, but robust and heuristic surrogate losses may violate those assumptions.The robust maximization may be unavailable, and the attack algorithm may be discontinuous.Source: §2 · p. 4

Certified defense

  • Verification methods upper-bound robust loss to provide certified robustness, and the paper’s convergence analysis can be extended to certified adversarial training.These methods differ from attack algorithms by computing upper bounds rather than searching for adversarial examples.Source: §2 · p. 4

3 Preliminaries

The paper formalizes the network, loss, perturbation sets, and surrogate objectives used to analyze adversarial training. These definitions connect ordinary training loss with attack-specific and robust losses.

3.1 Notations

  • 3.1 Notations specifies the index sets, Gaussian distribution, Euclidean and matrix norms, inner product, and asymptotic notation used throughout.Source: §3.1 · pp. 4–5

3.2 Deep Neural Networks

  • 3.2 defines width-m deep fully connected ReLU networks, fixes the first and output-layer weights after initialization, and assumes a Lipschitz, smooth, convex loss.The analysis uses scalar outputs and square intermediate layers for simplicity.Source: §3.2 · p. 5

3.3 Perturbation and the Surrogate Loss Function

  • A perturbation set assigns allowable input neighborhoods, while a perturbation function maps each parameter-input pair into its assigned set.The sets are assumed compatible with the dataset, and the analysis restricts inputs and perturbations to the unit sphere.Source: §3.3 · p. 6
  • The surrogate loss evaluates training loss after applying an attack, with ordinary loss as the identity-attack case and robust loss as the strongest-attack case.Adversarial training minimizes the robust loss through this surrogate-loss formulation; randomized perturbation functions are also noted as an extension.Source: §3.3 · pp. 6–7

4 Convergence Results of Adversarial Training

For sufficiently wide networks, projected gradient descent on the attack-dependent surrogate loss approaches the best robust loss within the chosen parameter region. The proof combines near-initialization linearization with an online-learning view of the attack.

4 Convergence Results of Adversarial Training

  • For sufficiently large width, projected gradient descent converges with high probability to surrogate loss within ǫ of the best minimax robust loss in B(R).The guarantee applies to arbitrary attack algorithms under the theorem’s width, stepsize, iteration, and loss assumptions.Source: §4 · pp. 7–8
  • The attack algorithm determines the guaranteed surrogate loss: stronger training attacks yield stronger guarantees against the corresponding attack loss.For example, training with projected gradient ascent guarantees that this attack cannot successfully attack the learned network under the theorem’s conditions.Source: §4 · p. 8
  • The approximation radius R controls the network’s expressive capacity, and larger R can reduce the optimal robust loss; sufficiently large width yields a network with small adversarial training error.Source: §4 · p. 8

4.1 Proof Sketch

  • The proof handles nonsmooth, potentially discontinuous surrogate losses by combining near-initialization network linearization with an online-learning treatment of the perturbation function.It separates nonconvexity from the network argument and worst-case behavior from the perturbation function.Source: §4.1 · pp. 8–9
  • The analysis does not require the stated zero-loss condition for the proof, allowing common cross-entropy losses, while the network is smooth only in its first argument rather than jointly in parameters and inputs.Source: §4.1 · p. 8

5 Adversarial Training Finds Robust Classifier

The paper combines adversarial-training convergence with NTK-based expressivity to show that sufficiently wide networks can achieve small robust training loss under a given attack algorithm.

Robust classifier via NTK expressivity

  • The analysis views networks near initialization as random features approximating an induced RKHS, whose robust classifier supplies the expressivity component.The NTK is introduced as the kernel underlying the RKHS, and the approximation argument can have exponential dependence on input dimension.Source: §5 · pp. 9–11

Convergence analysis

  • Gradient descent for smooth two-layer networks converges without a projection step, whereas the deep-network analysis uses projected gradient descent.The two-layer result assumes smooth activations; the authors suggest smoothness may also remove projection technically in deeper networks.Source: §5 · p. 10

Robust classifier via NTK expressivity

  • Sufficiently wide two-layer networks admit a robust classifier near initialization, enabling adversarial training to achieve small robust training loss under the stated assumptions.The construction uses NTK/RKHS approximation and random-feature analysis, then combines expressivity with convergence.Source: §5 · p. 11

Assumptions and scope

  • The robust-classifier guarantee requires compatible perturbation sets and functions, smooth and Lipschitz activations, NTK robust-classifier existence, and sufficiently large width.The corollary is stated for data on the unit sphere and uses gradient descent with a width and stepsize depending on the prescribed accuracy.Source: §5 · pp. 10–11
  • The resulting guarantee is specific to the attack algorithm and perturbation function used during training, rather than automatically extending to larger attack families.The paper explicitly identifies generalization to different attacks as an open direction.Source: §5 · p. 11

6 Capacity Requirement of Robustness

Robust interpolation requires more capacity than ordinary interpolation: its VC-Dimension scales with both sample count and input dimension, supporting wider networks for robust learning.

Implication

  • The result supports increasing neural-network width because reliably resisting strong attacks has been associated with greater capacity than classifying benign examples.The paper presents wider networks as necessary in this sense, while noting empirical motivation from adversarial training.Source: §6 · pp. 12–13

Robust interpolation

  • The paper defines robust interpolation over separated datasets and perturbation balls, requiring correct labels throughout each sample’s allowed perturbation neighborhood.The perturbation sets are Bδ(x), with datasets restricted to Sδ.Source: §6 · p. 12

Capacity comparison

  • For a general hypothesis class, n-point interpolation already implies VC-Dimension at least n, but robust interpolation imposes the stronger lower bound.The comparison isolates the additional capacity associated with robustness rather than ordinary fitting alone.Source: §6 · p. 13
  • Robust interpolation by neural networks requires VC-Dimension at least Ω(nd), whereas ordinary interpolation can be realized with VC-Dimension O(n log n).Here d is the input dimension, so the robust requirement is larger than the ordinary interpolation bound in the stated comparison.Source: §6 · pp. 12–13

7 Discussion on Limitations and Future Directions

The discussion identifies boundaries of the theory, including attack-family mismatch, limited structural dependence, approximation bounds affected by dimensionality, and unresolved robust-generalization questions.

Generalizing to different attacks

  • The current guarantee controls surrogate loss for the same perturbation function used in training, leaving broader attack families outside the stated result.Generalizing the guarantee to larger perturbation families is identified as an open question.Source: §7 · p. 13

Exploiting structures of network and data

  • The theory does not exploit useful network or data structure beyond sufficient width, so increasing depth can worsen the bound.The authors suggest finer analysis based on alignment between network structure and data distribution.Source: §7 · pp. 13–14

Improving the approximation bound

  • The NTK-based robust-expressivity argument can suffer from curse-of-dimensionality dependence, and its required approximation radius may be larger than necessary in practice.The authors propose adapting robust expressivity to low-dimensional data mechanisms as a possible improvement.Source: §7 · p. 14

Capacity requirement of robustness and robust generalization

  • Robust generalization remains less settled than robust training: increased capacity can reduce training loss while having much less effect on robust generalization.The discussion also points to training-data quantity and other factors as relevant to robust generalization.Source: §7 · p. 14

Future directions

  • Several proposed improvements remain unanswered even for non-robust neural networks and are left to future work.The authors frame these directions as limitations of the current theory rather than completed results.Source: §7 · pp. 13–14

8 Acknowlegements

The paper acknowledges discussions with several researchers and lists institutional, program, fellowship, and agency support.

Acknowledgements

  • The authors acknowledge useful discussions with Siyu Chen, Di He, Runtian Zhai, and Xiyu Zhai.Source: §8 · p. 14

Funding

  • The listed support includes Peking University’s elite undergraduate training program, China and Beijing programs, the ARO, the Sloan Research Fellowship, and NSF CCF #1900145.Source: §8 · p. 14

A Proof of the Convergence Result for Deep Nets in Section 4

The proof establishes convergence for deep overparameterized networks by controlling gradient perturbations uniformly over input neighborhoods and showing near-convexity within a parameter region. Projected gradient descent then approaches the optimal surrogate loss under the stated width and initialization conditions.

Initialization control

  • The analysis relies on high-probability initialization bounds for Gaussian weight matrices and hidden-layer quantities under sufficiently large width.These initialization estimates support the gradient and uniformity lemmas used later.Source: A Proof of the Convergence Result for… · p. 20

Gradient stability

  • Gradient perturbations remain controlled for every perturbed input in the neighborhood by converting input perturbations into equivalent first-layer parameter perturbations.This lets results developed for fixed data points extend to adversarially perturbed inputs.Source: A Proof of the Convergence Result for… · pp. 20–21

Uniform near-convexity

  • An epsilon-net extends fixed-input bounds to all inputs, yielding a loss function that is approximately convex throughout the parameter neighborhood B(R).The argument combines covering-number bounds with uniform gradient control.Source: A Proof of the Convergence Result for… · pp. 23–24

Optimization argument

  • Projected gradient descent remains inside B(R) and uses the resulting bounds to compare each iterate with an optimal parameter W* over T steps.The proof tracks the update from random initialization with step size alpha.Source: A Proof of the Convergence Result for… · pp. 24–25

B Proof of Theorem 5.1: Convergence Result for Two-Layer Networks

For two-layer networks with smooth activations, the proof analyzes unprojected gradient descent through parameter-distance recurrences. It shows that the iterates achieve epsilon-close surrogate loss without requiring a projection step.

B Proof of Theorem 5.1: Convergence Result for Two-Layer Networks

C.1 Proof of Theorem 5.2

The proof constructs low-robust-loss solutions near initialization by combining NTK/RKHS expressiveness with finite random-feature approximation. A quadratic-ReLU example makes the approximation and width dependence more explicit.

C.1 Proof of Theorem 5.2

  • The random-feature class FRF is dense in the NTK RKHS H(Kσ) under the uniform norm on the unit sphere.This supplies functions that can approximate the target robust interpolant over the entire input domain.Source: §C.1 · p. 28
  • Finite random features approximate FRF functions with high probability, enabling a finite-width network construction near the initialization.The approximation is controlled through importance sampling and concentration inequalities.Source: §C.1 · pp. 29–30, §C.2 · p. 33
  • The neural Taylor expansion separates a linear random-feature term from a residual, allowing the approximation result to construct a classifier with low robust loss near initialization.The construction combines uniform approximation over perturbation sets with the NTK expansion.Source: §C.1 · pp. 30–32

C.2 Example of Using Quadratic ReLU Activation

  • Combining RKHS capacity, finite-sum approximation, and optimization yields a quadratic-ReLU network with small robust training loss under explicit width and optimization requirements.The resulting corollary uses width m = Omega(...) and gradient-descent stepsize alpha = O(epsilon), with the full dependencies stated in the theorem.Source: §C.2 · pp. 33, 35
  • For quadratic ReLU, the induced RKHS contains sufficiently smooth even functions, while the dataset assumption excludes oppositely labeled overlapping perturbation regions.A lifting trick can address the even-function restriction when needed.Source: §C.2 · pp. 33, 35

D Proof of Theorem 6.1

The proof establishes a lower bound on the capacity required for robust interpolation by explicitly constructing separated positive and negative perturbation regions. This demonstrates that robust interpolation demands additional model capacity as perturbation neighborhoods expand.

D Proof of Theorem 6.1

  • For each cluster, positive and negative labeled points are separated by a hyperplane and enclosed in disjoint balls of a suitable radius.The radius is chosen above a cluster-dependent threshold proportional to a small constant.Source: D Proof of Theorem 6.1 · pp. 35–36
  • The construction sets r = δ and chooses cluster centers ci with ||ci-ci'||2 ≥ 6δ for i ≠ i', while placing the corresponding balls disjointly.Source: D Proof of Theorem 6.1 · p. 36
  • A robust interpolation class can shatter the constructed labeled points by assigning separate perturbation balls to positive and negative examples.The construction uses two disjoint radius-δ balls for each cluster and a separating hyperplane when both labels occur.Source: D Proof of Theorem 6.1 · p. 36

Related papers

Loading 1906.07916v2…