A Theoretically Grounded Extension of Universal Attacks from the Attacker's Viewpoint

• The theoretical contribution is incremental and offers limited guidance for algorithm design. The primary theoretical input is the application of Rademacher complexity to the generalization of adversarial perturbations, which is somewhat limited. Furthermore, this theoretical insight does not significantly influence the algorithm's design.

• The experiments on adversarial transferability are not comprehensive enough. (1) Tests were conducted only on CIFAR-10, whereas most experiments concerning adversarial transferability are performed on ImageNet. (2) The choice of the target model is not reasonable; since the source model is already a ResNet, the target model should incorporate structures other than ResNet.

• The motivation for Equation (9) is unclear. Regarding Equation (9), it is not explained why a set of perturbations is used. Also, the definition of problem 1 suggests there should be constraints on L; otherwise, when L equals n, Equation (9) essentially degenerates into Equation (1). Moreover, there is a lack of discussion in the experimental section regarding the appropriate size of the parameter L.

• Comparative experiments are not entirely fair. The authors' method optimizes several perturbations simultaneously, but the baseline methods compared are all optimizing a single perturbation. This comparison's fairness needs further discussion.

1. The effectiveness of the L-UAP algorithm is not adequately explained. It basically designs a new step update procedure (inner loop of algorithm 1). How is that important? Is there any analytical or theoretical grounding?

2. The proof of Theorem 4 is missing. Although one paper is cited, and the theorem may be built from it, I do not think the paper considers Algorithm 1 proposed by you, so it was important to show the proof of it.

3. From the results in Table 1, why are multiple perturbations beneficial for source model attack but not that good for transfer attack?

4. Problem 1 and Algorithm 1 only do optimization with respect to one model, which is similar to a single model attack. What is the special component here for universal attack?

5. In proposition 1, the paper defines Radamecher complexity of a set of perturbations $\mathcal{B}_p(\delta)$, which is weird to me since the complexity measure is defined for a function class.

6. In Theorem 2, consider the formula inside the probability operator, parameter $L$ does not appear in LHS. What the paper bounds here is exactly the same as that in Theorem 1.

7. Is it possible to consider the complexity measure (Rademacher complexity) as a regularization term to improve the transferability of universal attacks? If it is feasible, the idea looks more interesting.

8. Presentation: I do not even find the definitions of $\rho$ and $h$ in algorithm 1 in the main text, which is very confusing to readers.

It is unclear how good the generalization bounds are. As a result it is difficult to evaluate the theoretical results. (More details in the Questions section)

The primary limitation of this research is the weak linkage between the theoretical framework and experimental results, even though it is a challenge commonly observed in uniform convergence analyses.

1. In both Theorem 1 and Theorem 2, the bounds are set for all perturbations within $B_p(\delta)$, rather than specifically for learned UAP attacks.

2. When contrasting Theorem 1 with Theorem 2, it becomes evident that the generalization abilities of UAP and L-UAP are evaluated by $R(B_p(\delta))$ and $R(B_p(\delta)^L)$ respectively. Considering that $B_p(\delta)^L$ represents a more extensive class, its Rademacher complexity would naturally be larger. As a result, the theorem might suggest that L-UAP's generalization is inferior to UAP, which contradicts the paper's primary objective. This is similar to a general criticism for previous rademacher complexity analysis: Rademacher complexity of large model is very large, yet large model generalize better.

Therefore, without a deeper analysis of $R(B_p(\delta))$ and $R(B_p(\delta)^L)$, the analysis is not informative. Given this, the assertion in Section 2 — "motivated by Theorem 2, we propose to maximize problem 1” — doesn't come across as compelling.

3. Theorem 4's convergence results under the Lipschitz and KL conditions appear somewhat lacking in depth and specificity.

Given the weak theoretical analysis, increasing the number of perturbation candidates is not very novel.