Towards Understanding the Dynamics of the First-Order Adversaries

Zhun Deng, Hangfeng He, Jiaoyang Huang, Weijie J. Su

The Optimization Gap in Adversarial Training

An acknowledged weakness of neural networks is their vulnerability to adversarial perturbations. To improve robustness, adversarial training has emerged as one of the most successful defense mechanisms. It is formulated as a min-max optimization problem: the outer loop updates the network weights to minimize the loss, while the inner loop crafts perturbations (adversaries) to maximize the loss.

In practice, this inner maximization is typically solved using Projected Gradient Descent (PGD). However, a theoretical gap exists. For neural networks, this inner problem is highly non-concave. Standard optimization theory suggests that first-order methods like PGD should easily get stuck in saddle points or take an exponentially long time to converge in such complex landscapes. Yet, empirically, PGD finds strong adversaries rapidly. This paper bridges the gap between theory and practice by mathematically explaining why PGD succeeds and investigating how the numerical scale of input data impacts the optimization process.

Theoretical Foundations: Why PGD Works

The authors conduct a rigorous theoretical analysis of the PGD dynamics using a two-layer neural network with softplus activations and a quadratic loss function. To make the mathematics tractable, they focus on the initial phase of training, where network weights are drawn from standard initialization distributions (like Xavier) and remain independent of the inputs.

They break the PGD trajectory into two distinct phases to explain its success:

  1. Escaping the Interior: Inside the allowed perturbation ball, the authors prove that the gradient is non-vanishing. This means PGD rarely terminates inside the ball; instead, it rapidly pushes the perturbation outward until it hits the boundary constraint (the sphere).
  2. Navigating the Boundary: Once on the sphere, the optimization becomes a constrained problem. Using Lagrangian multipliers, the authors prove that under certain regularity conditions, there are no saddle points on the sphere. Because the critical points are strictly local minima or local maxima, PGD does not stall and can efficiently converge to a local maximum.

The Crucial Role of Input Scaling

Perhaps the most actionable insight from the paper is how the scale of the input data dictates the complexity of the non-concave landscape.

In computer vision, practitioners routinely rescale image pixels from [0, 255] to [0, 1]. This paper provides a theoretical justification for why this rescaling is crucial for adversarial training. The authors prove that if the input scale (and consequently the perturbation radius) is below a certain threshold, the landscape on the sphere becomes highly regular and contains only one local maximum—which is inherently the global maximum.

Optimization landscapes under varying input scales and perturbation ratios. Smaller input scales yield smoother landscapes with a single global maximum, while larger scales create complex, multi-peak terrains.

Conversely, if the input scale is artificially large, the landscape becomes highly complex and multi-peaked. In these jagged terrains, PGD is much more likely to get bogged down, drastically slowing down the discovery of strong adversaries.

Key Results and Empirical Validation

The theoretical findings are backed by both mathematical proofs and empirical validation:

  • Polynomial Convergence: The authors mathematically prove that PGD will output a point on the sphere that is $O(\eta^{1/2})$ close to a local maximum in $O(\eta^{-2})$ iterations (where $\eta$ is the learning rate).
  • Threshold for Regularity: They establish the existence of a threshold $\tau_\epsilon > 0$. For any perturbation bound $\epsilon < \tau_\epsilon$, there is only one local maximum on the sphere with high probability.
  • Empirical Validation on MNIST: Using a multi-layer CNN on the MNIST dataset, the authors verified their claims. An input scale of 0.1 allowed PGD to easily escape sub-optimal points and rapidly maximize the loss. When the input scale was increased to 1000, the PGD trajectory became stuck in complex local geometries, confirming the theoretical predictions.

Limitations and Future Directions

While this paper provides a strong foundational understanding of PGD in adversarial settings, it has limitations. The rigorous proofs are restricted to shallow, two-layer neural networks. Furthermore, the analysis relies heavily on the assumption that the network weights are randomly initialized. As adversarial training progresses and weights adapt to the data, the loss approaches zero, potentially leading to vanishing gradients and complex cyclic dynamics not covered by this initial analysis.

Future work will need to extend this theoretical framework to deeper networks and capture the full dynamics of adversarial training, specifically how the optimization landscape shifts as the outer minimization loop updates the network weights over time.

Summary updated

Abstract

An acknowledged weakness of neural networks is their vulnerability to adversarial perturbations to the inputs. To improve the robustness of these models, one of the most popular defense mechanisms ...
BibTeX
@inproceedings{deng2020towards,
  author = {Zhun Deng and Hangfeng He and Jiaoyang Huang and Weijie J. Su},
  title = {{Towards Understanding the Dynamics of the First-Order Adversaries}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=3SgbvpkrXF},
}
Figure