  Sparse adversarial attacks fool deep neural networks (DNNs) through minimal
pixel perturbations, typically regularized by the $\ell_0$ norm. Recent efforts
have replaced this norm with a structural sparsity regularizer, such as the
nuclear group norm, to craft group-wise sparse adversarial attacks. The
resulting perturbations are thus explainable and hold significant practical
relevance, shedding light on an even greater vulnerability of DNNs than
previously anticipated. However, crafting such attacks poses an optimization
challenge, as it involves computing norms for groups of pixels within a
non-convex objective. In this paper, we tackle this challenge by presenting an
algorithm that simultaneously generates group-wise sparse attacks within
semantically meaningful areas of an image. In each iteration, the core
operation of our algorithm involves the optimization of a quasinorm adversarial
loss. This optimization is achieved by employing the $1/2$-quasinorm proximal
operator for some iterations, a method tailored for nonconvex programming.
Subsequently, the algorithm transitions to a projected Nesterov's accelerated
gradient descent with $2$-norm regularization applied to perturbation
magnitudes. We rigorously evaluate the efficacy of our novel attack in both
targeted and non-targeted attack scenarios, on CIFAR-10 and ImageNet datasets.
When compared to state-of-the-art methods, our attack consistently results in a
remarkable increase in group-wise sparsity, e.g., an increase of $48.12\%$ on
CIFAR-10 and $40.78\%$ on ImageNet (average case, targeted attack), all while
maintaining lower perturbation magnitudes. Notably, this performance is
complemented by a significantly faster computation time and a $100\%$ attack
success rate.
