cs.CVNov 3, 2026

Robustness Verification against Patch Attacks via Group-Lasso Semidefinite Relaxation

Authors: Yukina Nakagawa, Takami Sato, Ken Kobayashi, Kazuhide Nakata

Organizations: Institute of Science Tokyo, 2-12-1 Ookayama, Meguro-ku, Tokyo 152-8550, Japan · Keio University, 2-15-45 Mita, Minato-ku, Tokyo 108-8345, Japan

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.

Figures & tables

Explore similar work

CardsList
  1. Certified Robustness via Sparse Second-Order Cone Relaxations

    Oct 12, 2026Mohammadreza Maleki, Daniel Sadig, Rushendra Sidibomma +3Convex RelaxationSecond-Order Cone Programming

  2. Privacy-Preserving Robustness Verification for Neural Networks

    Jul 6, 2026Nianyun Song, Xiaokun Luan, Yu Guo +3Secure Multi-Party ComputationNeural Network Verification