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 is to alternatively maximize the loss over the constrained perturbations (or called adversaries) on the inputs using projected gradient ascent and minimize over weights. In this paper, we analyze the dynamics of the maximization step towards understanding the experimentally observed effectiveness of this defense mechanism. Specifically, we investigate the non-concave landscape of the adversaries for a two-layer neural network with a quadratic loss. Our main result proves that projected gradient ascent finds a local maximum of this non-concave problem in a polynomial number of iterations with high probability. To our knowledge, this is the first work that provides a convergence analysis of the first-order adversaries. Moreover, our analysis demonstrates that, in the initial phase of adversarial training, the scale of the inputs matters in the sense that a smaller input scale leads to faster convergence of adversarial training and a "more regular" landscape. Finally, we show that these theoretical findings are in excellent agreement with a series of experiments.
Introduction
Deep neural networks are notoriously fragile; tiny, human-imperceptible perturbations—known as adversarial examples—can easily trick them into making incorrect predictions. To counter this, adversarial training has emerged as the gold-standard defense. This method is formulated as a "min-max" game: the network attempts to minimize loss over its weights while an "adversary" simultaneously tries to maximize that loss by perturbing the inputs.
While the optimization of weights (the "min" part) is relatively well-studied, the "max" part—finding the optimal adversarial perturbation—presents a challenging non-concave optimization problem. In practice, researchers rely on Projected Gradient Ascent (PGD) to find these perturbations. However, until now, there has been little theoretical guarantee that PGD actually finds a "good" adversary or how long it takes to converge. This paper fills that gap by analyzing the dynamics and landscape of this inner maximization step.
Theoretical Framework and Convergence
The study focuses on a two-layer neural network with a quadratic loss function during the initial phase of training, where weights are still close to their random Xavier initialization. By transforming the constrained perturbation problem into an unconstrained one using Lagrangian multipliers, the authors were able to study the "approximate gradient" and "approximate Hessian" on the surface of the perturbation constraint (the $l_2$ ball).
Their analysis yields a significant theoretical breakthrough: within the perturbation ball, the gradient is non-vanishing, and on the sphere boundary, there are no saddle points—only local maxima and minima. Specifically, Theorem 3.1 proves that for a sufficiently wide network, PGD outputs a point on the sphere that is $O(\eta^{1/2})$ close to a local maximum in $O(\eta^{-2})$ iterations with high probability. This confirms that PGD is a trustworthy tool that avoids saddle points and converges rapidly to local maxima, explaining its practical effectiveness.
The Impact of Input Scale
A major insight of this work is that the scale of the input data fundamentally changes the optimization landscape. The authors prove the existence of a uniqueness threshold: if the input scale is below a certain value, the multi-modal landscape collapses into a simpler one with only one local maximum on the sphere.
As illustrated in the figure above, the input scale acts as a complexity dial. At a small scale (0.01), the landscape is nearly flat and easy to navigate, leading to faster convergence. As the scale increases to 100, the landscape transforms into a jagged "mountain range" of local optima, making it significantly harder for PGD to find a global maximum. This suggests that simply rescaling inputs (e.g., to a [0, 1] range) can fundamentally simplify the adversarial training process.
Experimental Validation
The theoretical findings were validated using both simulated 2D data (visualized in the 3D landscapes above) and the MNIST dataset. For MNIST, the authors simplified the task to binary classification of odd vs. even digits. These experiments confirmed that the behavior observed in low-dimensional simulations—specifically the relationship between input scale and landscape regularity—holds true for high-dimensional, real-world data.
Conclusion and Future Work
While this paper provides the first rigorous convergence analysis for first-order adversaries, it primarily focuses on the initial phase of training where weights are near-random. As training progresses, the weights evolve away from their Gaussian initialization, and the interaction between weight updates and perturbation updates can lead to more complex "cyclic dynamics." Extending this analysis to deeper architectures and later stages of training remains an important challenge for future research.
Summary updated