Adversarial robustness in discontinuous spaces via alternating sampling & descent

Rahul Venkatesh, Eric Wong, Zico KolterWACV 2023 · OpenReview

Abstract

Several works have shown that deep learning models are vulnerable to adversarial attacks where seemingly simple label-preserving changes to the input image lead to incorrect predictions. To combat this, gradient based adversarial training is generally employed as a standard defense mechanism. However, in cases where the loss landscape is discontinuous with respect to a given perturbation set, first order methods get stuck in local optima, and fail to defend against threat. This is often a problem for many physically realizable perturbation sets such as 2D affine transformations and 3D scene parameters. To work in such settings, we introduce a new optimization framework that alternates between global zeroth order sampling and local gradient updates to compute strong adversaries that can be used to harden the model against attack. Further, we design a powerful optimization algorithm using this framework, called Alternating Evolutionary Sampling and Descent (ASD), which combines an evolutionary search strategy (viz. covariance matrix adaptation) with gradient descent. We consider two settings with discontinuous/discrete and non-convex loss landscapes to evaluate ASD: a) 3D scene parameters and b) 2D patch attacks, and find that it achieves state-of-the-art results on adversarial robustness.

Introduction: The Challenge of Rugged Landscapes

Most research into adversarial robustness focuses on $l_p$ bounded pixel perturbations. In these cases, the loss landscape—how the model's error changes as the input is tweaked—is relatively smooth, allowing standard Gradient Descent (specifically PGD) to find the "worst-case" noise efficiently.

However, real-world threats are often "naturalistic," involving parameters like 3D object rotations, lighting changes, or physical patch placements. When optimizing these parameters, the loss landscape becomes "rugged," non-convex, and often discontinuous. Standard gradient-based methods get stuck in local optima almost immediately, and for discrete parameters like pixel locations, gradients may not even exist. Consequently, models trained with standard methods remain vulnerable to these physical-world attacks.

Methodology: Alternating Evolutionary Sampling and Descent (ASD)

To overcome these limitations, we propose a novel optimization framework that alternates between global exploration and local refinement. Our specific algorithm, Alternating Evolutionary Sampling and Descent (ASD), combines evolutionary search with gradient descent.

The ASD framework (bottom) addresses the discontinuous loss landscapes (top) inherent in naturalistic perturbations by alternating between global sampling and local gradient refinement.

The process operates in a loop consisting of three main steps:

  1. Global Sampling: The algorithm maintains a probability distribution (a multivariate normal) over the possible perturbations. It samples a batch of candidate solutions using CMA-ES (Covariance Matrix Adaptation Evolution Strategy), a derivative-free optimizer.
  2. Local Gradient Updates: For differentiable parameters (like patch textures or differentiable 3D rendering), the algorithm performs steps of Projected Gradient Descent (PGD) on each sampled candidate, pushing them toward nearby local maxima.
  3. Distribution Update: The algorithm evaluates the loss for these updated samples and updates the mean and covariance of its sampling distribution to move toward areas of the search space that produced the highest loss.

By combining these techniques, ASD uses evolution to jump over "cliffs" in the landscape and gradients to sprint up the "hills."

Experimental Results

We evaluated ASD on two primary settings characterized by discontinuous and non-convex loss landscapes:

3D Scene Parameters

We created a new benchmark using 56 different 3D traffic sign models rendered via PyTorch3D and Blender. We tested scenarios ranging from 7 parameters (pose and light position) to 17 parameters (adding light color and material shininess). Models trained with ASD achieved a Robust Test Accuracy (RTA) of 0.63, significantly outperforming models trained with simple random search (0.31).

2D Patch Attacks

Using the CIFAR-10 dataset, we tested robustness against adversarial patches. ASD achieved a state-of-the-art RTA of 0.60, doubling the performance of previous leading methods like Local Linearization (0.30).

Key Insights and Conclusion

A central insight of this work is that gradients remain locally meaningful even when globally useless; they provide a "sense of direction" that accelerates evolutionary search. Furthermore, we demonstrate that simple data augmentation (training on random renders) is insufficient for true robustness, as a determined adversary can still find specific conditions that cause model failure.

While ASD is more computationally expensive than standard PGD, it is significantly more efficient than pure evolutionary strategies. This "sampling + descent" framework offers a robust path forward for optimization in other rugged machine learning domains, such as Neural Architecture Search (NAS) and hyperparameter optimization.

Summary updated

Abstract

Several works have shown that deep learning models are vulnerable to adversarial attacks where seemingly simple label-preserving changes to the input image lead to incorrect predictions. To combat this, gradient based adversarial training is generally employed as a standard defense mechanism. However, in cases where the loss landscape is discontinuous with respect to a given perturbation set, first order methods get stuck in local optima, and fail to defend against threat. This is often a problem for many physically realizable perturbation sets such as 2D affine transformations and 3D scene parameters. To work in such settings, we introduce a new optimization framework that alternates between global zeroth order sampling and local gradient updates to compute strong adversaries that can be used to harden the model against attack. Further, we design a powerful optimization algorithm using this framework, called Alternating Evolutionary Sampling and Descent (ASD), which combines an evolutionary search strategy (viz. covariance matrix adaptation) with gradient descent. We consider two settings with discontinuous/discrete and non-convex loss landscapes to evaluate ASD: a) 3D scene parameters and b) 2D patch attacks, and find that it achieves state-of-the-art results on adversarial robustness.
BibTeX
@inproceedings{venkatesh2023adversarial,
  author = {Rahul Venkatesh and Eric Wong and Zico Kolter},
  title = {{Adversarial robustness in discontinuous spaces via alternating sampling \& descent}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2023},
  url = {https://openreview.net/forum?id=mLbE5cdO9L},
}
Figure