Robustness Verification against Patch Attacks via Group-Lasso Semidefinite Relaxation

Yukina Nakagawa, Takami Sato, Ken Kobayashi, Kazuhide NakataarXiv 2026 · arXiv

TL;DR

Verifying neural network robustness against localized "patch attacks" (like physical stickers) is traditionally a slow, combinatorial nightmare. This paper introduces a novel "one-shot" verification framework that models patch attacks using group-wise sparsity and relaxes the problem into a continuous Group-Lasso Semidefinite Program, achieving a 91% verification rate while running in less than 3% of the time required by exact methods.

What Problem Does This Paper Address?

Deep Neural Networks (DNNs) are notoriously fragile. Most research into "robustness verification"—mathematically proving a model won't change its prediction under pressure—focuses on $L_p$ norm-ball attacks. These attacks assume an adversary adds a tiny amount of noise to every pixel.

However, real-world physical attacks often look like "patches": a sticker on a stop sign or a patterned glasses frame. These are localized (only a few pixels change) but high-intensity (the pixels change a lot). Verifying against these is hard because you don't know where the patch will be. A naive approach would be to check every possible patch location one by one, but for a standard image, the number of possible locations makes this computationally impossible. The authors aim to bridge this gap by creating a verification method that handles all possible patch locations simultaneously without the exponential cost.

Methods

The authors propose a multi-step optimization approach to turn a discrete search problem into a continuous, solvable one:

  1. Group-Wise Sparsity Modeling: They divide the image into non-overlapping groups of pixels. A patch attack is then modeled as an adversary choosing at most $k$ groups to perturb.
  2. Mixed-Integer Semidefinite Programming (MISDP): They first formulate the verification as an exact problem using binary variables to represent patch locations and ReLU activations. While accurate, this is too slow for practical use.
  3. SDP Relaxation: To handle the non-linear ReLU activations, they apply a standard Semidefinite Programming (SDP) relaxation, which turns the neural network's behavior into a set of convex constraints.
  4. Group-Lasso Relaxation: This is the "secret sauce." To eliminate the binary variables representing patch locations, they propose three relaxations. The most effective is the Group-Lasso relaxation, which constrains the sum of the $L_2$ norms of the perturbations in each group. This preserves the "localized" nature of the attack (spatial sparsity) while allowing the use of efficient continuous optimization solvers.

Datasets

The researchers evaluated their method using the MNIST dataset of handwritten digits.

  • For scalability tests, they used downsampled 5x5 versions of the images.
  • For full verification performance, they used the standard 28x28 images.
  • They tested two architectures: FCNNa (2 hidden layers, 20 neurons each) and FCNNb (3 hidden layers, 100 neurons each), using both "Clean" models and models trained with Adversarial Training (Adv.).

Key Insights and Ideas

  • Structure is Everything: The authors found that simply treating a patch attack as a global $L_2$ perturbation (ignoring the group structure) leads to very "loose" proofs that fail to certify models. By explicitly preserving the group-sparse structure in the optimization objective, the Group-Lasso relaxation provides a much tighter bound.
  • The "One-Shot" Advantage: Instead of iterating through thousands of potential patch locations, the Group-Lasso formulation allows the solver to "find" the most dangerous location automatically as part of a single optimization problem.
  • Visualizing the Gap: As seen in Figure 1, traditional verification methods (like IBP or MILP) assume perturbations are spread across the whole image. The proposed Group-Lasso method correctly identifies that a patch attack would concentrate its energy on the foreground object (the digit).
Figure 1: Adversarial perturbations generated during verifi- cation. Red and blue mean positive- and negative-direction perturbations, respectively. Compared to existing baselines (MILP and IBP) that spread perturbations across the entire image, our proposed Group-Lasso relaxation restricts per- turbations to localized foreground regions, closely matching the localized patch attack threat model.

Key Results

  • Extreme Speedup: The proposed relaxations required less than 3% of the computation time of the exact MISDP formulation. In some cases, they achieved speedup factors of over 1400x.
  • High Fidelity: Despite being a relaxation, the Group-Lasso objective value was only 0.34% higher than the exact solution on average. This tightness is visualized in Figure 3, where Group-Lasso points sit almost perfectly on the diagonal compared to other relaxations.
  • Superior Verification: On adversarially trained models (FCNNa), Group-Lasso achieved a 91% verification rate, crushing existing baselines like bounded-MILP (70%) and CROWN (47%). For the deeper FCNNb model, where baselines failed almost completely (0-4%), Group-Lasso still managed to verify 69% of samples.
Figure 2: Comparison of the objective values obtained by the original MISDP and the proposed relaxations for ε = 0.1. Each point corresponds to one evaluation sample. Group- Lasso is almost on the diagonal, demonstrating its very tight relaxation of the MISDP.

Limitations and Future Work

While a significant step forward, the authors note several areas for improvement:

  • Scalability to Large Models: The experiments were limited to fully connected networks and small images (MNIST). Scaling this to high-resolution images and deep Convolutional Neural Networks (CNNs) will require more efficient first-order optimization solvers.
  • Fixed Geometries: The current model uses a fixed grid of non-overlapping squares. Real-world patches might be circular, rotated, or overlap multiple grid cells, which the current partition might not capture perfectly.
  • Solver Dependency: The method currently relies on commercial solvers like MOSEK; developing custom, open-source solvers tailored for this specific sparsity structure could further improve accessibility and speed.

Summary updated

Abstract

Robustness verification is essential for ensuring the safety and security of neural networks, but current methods focus heavily on norm-ball attacks, which do not adequately model typical real-world threats that present physical perturbations, known as patch attacks. A naive approach requires computationally prohibitive enumeration of all possible patch positions. To address the challenge, we propose a novel neural network verification method specialized to the patch-attack threat. Instead of enumerating patch locations, we first model the patch attack with group-wise sparsity and formulate its verification methods as a mixed-integer semidefinite program (MISDP) by applying SDP relaxation to the neural network. We then propose three relaxations, including Group-Lasso relaxation, that remove the integer variables while preserving the sparse, group-wise structure of the original attack, enabling substantially efficient verification. Our empirical analysis demonstrates that the proposed relaxations require less than 3% of the computation time of the original MISDP, while the Group-Lasso relaxation incurs only a 0.34\% average increase in the objective value over the original formulation. Furthermore, Group-Lasso achieves a verified rate of 91%, compared with under 70% for prior methods.
BibTeX
@misc{nakagawa2026robustness,
  author = {Yukina Nakagawa and Takami Sato and Ken Kobayashi and Kazuhide Nakata},
  title = {{Robustness Verification against Patch Attacks via Group-Lasso Semidefinite Relaxation}},
  year = {2026},
  eprint = {2611.04939},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.04939},
}
Figure