SAIF: Sparse Adversarial and Imperceptible Attack Framework

• It is not clear how the $\ell_0$-norm constrain is enforced: in Line 7 of Alg. 1, the sparsity of $s_t$ seems to decrease compared to $s_{t-1}$ (unless $\eta_t=1$ or $s_{t-1}$ and $z_t$ have the non-zero components and the same position). Moreover, the presentation in general could be more clear, e.g. some notation is used before being introduced.

• The case with $\epsilon=255$ is equivalent to a standard $\ell_0$-attack: then, I think a comparison to existing attacks (e.g. [A, B, C]) in this threat model should be included. Moreover, some of these attacks, e.g. [C], could be adapted to include $\ell_\infty$ bounds in a quite straightforward way, providing further baselines for the $\epsilon < 255$ setups.

• Some of the attacks used in the comparison, e.g. PGD $\ell_0 + \ell_\infty$, use sparsity constraints in the pixel space, while, if I understand it correctly, SAIF counts color channels individually. It's not clear how this difference, which would make the results of different attacks hardly comparable, is handled. Moreover, PGD $\ell_0 + \ell_\infty$ is flagged as a black-box attack, while it is a white-box method. Finally, the parameters, e.g. number of iterations, used for the existing methods are not detailed.

• The attacks are compared only on ResNet-50 and Inception-v3. Including more recent (and effective) architectures, and maybe adversarially trained models, would make the experimental evaluation more complete.

• The ablation study about removing the sparsity constrain (Sec. 7) doesn't seem to add any valuable insight into the proposed method, since it is known that $\ell_\infty$-bounded attacks perturb (almost) all pixels (which is also suggested by the update step in Eq. (5)).

[A] https://arxiv.org/abs/2006.12834
[B] https://arxiv.org/abs/2102.12827
[C] https://arxiv.org/abs/2106.01538

• The $O(1/\sqrt{T})$ convergence analysis is very interesting. But I was wondering how this number reflects the real running time in practice. For example, what are the convergence rates for existing methods in Table 4?
• The models tested are un-defended. The authors may need to test some robust models. Even the 'regular' robust models adversarially trained with small $\epsilon$ values and without sparsity constraints are helpful. Another way is to train the model with SAIF on the fly, to see if it performs better under SAIF.

• I did not find a practical motivation behind the proposed threat model. Sparse and low-magnitude attacks can indeed be hard to detect. However, to create the SAIF attacks, the attacker needs unrealistic powers: (i) it has white-box access to the model parameters, (ii) it knows the exact inputs processed by the model in advance, and (iii) it can also make the target model perceive the examples perfectly. The runtime of the SAIF algorithm is also slow so that makes real-time attack generation difficult. If the goal is to study the theoretical robustness of the model as with other unrealistic attacks, then stealthiness and low magnitude together are not really necessary and constraining the adversary by $L_{\infty}$ or $L_{0}$ already gives a stronger measure of robustness than the threat model considered here.

• Vision transformers have been shown to be more robust in literature (https://arxiv.org/abs/2105.07581) than the Inception and ResNet models considered here. It is not clear if the attack is effective on these more robust models.

• I found the technical details related to FW hard to digest as the authors assume familiarity with the details of FW. For example, computing $g(x_t)$ in section 3 involves maximizing over the set $\mathcal{A}$, but this is never defined. Similarly, the text in Section 4 suddenly starts talking about the undefined vectors $z_t, v_t$ and conditional gradients.