{'fraction_non_alphanumeric': 0.03438387438053344, 'fraction_numerical': 0.006431315774820424, 'mean_word_length': 4.878723404255319, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Universal Adversarial Directions

Despite their great success in image recognition tasks, deep neural networks (DNNs) have been observed to be susceptible to universal adversarial perturbations (UAPs) which perturb all input samples with a single perturbation vector. However, UAPs often struggle in transferring across DNN architectures and lead to challenging optimization problems. In this work, we study the transferability of UAPs by analyzing equilibrium in the universal adversarial example game between the classifier and UAP adversary players. We show that under mild assumptions the universal adversarial example game lacks a pure Nash equilibrium, indicating UAPs' suboptimal transferability across DNN classifiers. To address this issue, we propose Universal Adversarial Directions (UADs) which only fix a universal direction for adversarial perturbations and allow the perturbations' magnitude to be chosen freely across samples. We prove that the UAD adversarial example game can possess a Nash equilibrium with a pure UAD strategy, implying the potential transferability of UADs. We also connect the UAD optimization problem to the well-known principal component analysis (PCA) and develop an efficient PCA-based algorithm for optimizing UADs. We evaluate UADs over multiple benchmark image datasets. Our numerical results show the superior transferability of UADs over standard gradient-based UAPs.


Introduction
Deep neural networks (DNNs) have achieved great success in many supervised learning problems from computer vision [1], speech recognition [2], natural language processing [3], and computational biology [4]. Their performance, however, has been observed to be highly susceptible to small perturbations to the neural network's input data widely recognized as adversarial attacks [5,6,7]. A typical adversarial attack scheme assigns a norm-bounded perturbation to an input feature vector, where the designed perturbation is intended to fool either a known DNN (white-box adversarial attacks) or an unknown DNN (black-box adversarial attacks) to predict a wrong label. Over the recent years, adversarial attack and robust training schemes have received enormous attention in the machine learning community.
An adversarial attack scheme typically designs different perturbation vectors for different input data. This property allows the attack algorithm to tailor the designed perturbation to every specific input sample and further empowers the adversary to attain higher success rates in misleading a DNN machine. On the other hand, the influential study by [8] has empirically shown the existence of a universal adversarial perturbation (UAP) that can change the target classifier's predictions over a significant fraction of input samples. As demonstrated in this work and several other papers on universal perturbations [9,10,11,12], while UAPs are highly constrained across different input data, they still manage to achieve a fair success rate on unseen test data.
While UAPs can successfully attack a target DNN machine, the recent papers [13,14] have reported that UAPs generated by standard gradient-based methods could weakly transfer to unobserved DNN classifiers different from the source DNN used for their construction. Specifically, the reported results suggest that gradient-based UAPs perform noticeably weaker than standard PGD adversarial perturbations in transferring to an unseen DNN architecture. Such observations motivate the following question: Why do gradient-based UAPs perform suboptimally in transferring to different DNN classifiers?
The answer to the above question will play a key role in understanding and improving the generalization and transferability properties of universal perturbations. In this work, we focus on the above question and apply a max-min approach to examine the transferability features of UAPs. The applied max-min framework extends the adversarial example game introduced by [15] for generating transferable adversarial examples to the setting of universal adversarial perturbations. According to the adversarial example game, the adversary attempts to find an attack strategy for generating adversarial examples that achieves the maximum success rate against the most robust classifier from a given function space. We show that under some mild assumptions on a DNN architecture, every universal attack scheme can be completely thwarted by the classifier player. From a game-theoretic perspective, the universal adversarial example game possesses no pure Nash equilibria where the players' deterministic strategies are simultaneously optimal. Consequently, while a gradient-based UAP can significantly drop the performance of a fixed target DNN, the same UAP may have limited impact on a modified DNN function.
To study and address the transferability suboptimality of gradient-based UAPs, we introduce a variant of universal adversarial perturbations which we call Universal Adversarial Directions (UADs). According to the UAD approach, the adversary is only constrained to generate the perturbations along a unique direction in the sample space. Therefore, the UAD perturbations are no longer required to share the same magnitude and could be chosen differently for different input samples. In particular, unlike gradient-based UAPs, the UAD adversary has the freedom of choosing not to perturb an input sample, which sounds a sensible option in the evaluation of a universal adversarial attack scheme.
In order to find an effective UAD, we introduce a bilevel max-max optimization problem and propose a projected gradient-based algorithm to find a stationary solution in its optimization landscape. Moreover, we develop an efficient principal component analysis (PCA)-based approach to approximate the solution to the UAD optimization problem. The PCA-based method indeed finds the top principle component of the matrix of unnormalized fast gradient method (FGM) perturbations to training data. We provide a stochastic optimization algorithm for computing the solution to the PCA-based optimization problem that is suitable for large-scale machine learning problems.
We perform theoretical analysis of the equilibrium properties of the UAD adversarial example game. We show that under the assumption that the Fast Gradient Method (FGM)-perturbation matrix has a unique top principal component, the PCA-based approximate UAD game will possess a Nash equilibrium with a pure strategy for the universal adversary. This result indicates the existence of a single UAD with the maximum impact on the most robust classifier. In the general case, our analysis suggests an extension of the UAD framework to rank-constrained adversarial attacks where the designed perturbations are restricted to a low-rank linear subspace. We show that the rank-constrained adversarial example game will generally possess a Nash equilibrium with a pure adversarial attack strategy.
Finally, we discuss the results of several numerical experiments comparing the performance of UAPs and UADs over standard image datasets and DNN architectures. Our experimental results support the better transferability and generalizability of UADs over gradient-base UAPs. In addition, the numerical results suggest that the designed UAD can be applied as a universal perturbation with a similar or even better performance than gradient-based UAP attack schemes. We can summarize the main contributions of our work as follows: • Analyzing the transferability of universal adversarial perturbations through the max-min framework of adversarial example games • Proposing universal adversarial directions (UADs) as an extension of universal adversarial perturbations • Proving the existence of Nash equilibiria with a pure UAD attack strategy in universal adversarial direction games • Developing an efficient PCA-based algorithm for optimizing UADs • Conducting an empirical study of the performance of UADs compared to gradient-based UAPs.

Related Work
Since their introduction by [8], universal adversarial attacks have been extensively studied in the machine learning literature . The related literature includes a large body of papers on generating universal perturbations  [16, 17, 18, 19, 13, 20], black-box universal perturbations [21,22], and on defense methods against universal adversarial attacks [23, 24, 25]. In our work, we focus on the gradient-based universal adversarial perturbations maximizing the perturbed loss function, which as discussed by [24] nicely connects to the bilevel optimization problem of universal adversarial example games. We note that the iterative deepfool-based approach in [8], the singular vector-based approach in [16], and generative model-based method in [13] are indeed different from our analyzed gradient-based UAPs which better match our formulation of UAD optimization problems. In addition, the equilibrium and convergence properties of adversarial example games have been analyzed in several recent papers. The related works [15,26,27] focus on the max-min framework of designing transferable adversarial perturbations. Specifically, [26] prove that the standard adversarial example game generally lacks pure Nash equilibria and proposes finding the mixed Nash equilibria of the adversarial example game. Also, the analysis by [28] focuses on the adversarial training game with standard adversarial attacks. We note that the mentioned papers focus on the standard adversarial attack setting which does not directly apply to universal perturbations. On the other hand, the related papers [24,29] focus on the sequential game of universal adversarial training where the classifier moves first followed by the universal adversary. While this sequence leads to robust classifiers against universal perturbations, it does not address the max-min game of transferable universal perturbations which we discuss in our work.
In another related work, [16] use the singular vectors of the DNN's Jacobian matrices at different layers as universal perturbations. On the other hand, our approximate UAD framework chooses the top right-singular vector of the DNN loss's gradient with respect to training data as a universal adversarial direction which allows optimizing the perturbations' magnitudes unlike [16]'s proposed approach. Similarly, the SVD-based approach by [30] uses the singular vectors of normalized FGSM and PGD perturbations as UAPs and does not focus on the single-direction UAD attacks and its game-theoretic aspects. In addition, we theoretically analyze equilibrium in the UAD adversarial example game. Finally, we note that the SVD-based analyses in [8,31] target the data matrix's singular vectors which is different from our work's PCA-based analysis of the loss's gradient matrix.

Preliminaries
In this section, we review some standard definitions and tools regarding standard and universal adversarial attacks. Throughout the paper, we consider a supervised learning setting where the goal is to predict a label variable Y ∈ Y from the observation of a d-dimensional feature vector X ∈ X ⊆ R d . Given a loss function (y, y ) for labels y and y , the standard empirical risk minimization (ERM) learner aims to find a classifier function f ∈ F minimizing the expected prediction loss over a given function space F. However, the ERM learner has been observed to lack robustness against norm-bounded adversarial perturbations. To generate a standard norm-bounded adversarial perturbation for classifier f , input (x, y), attack norm · , and attack power ≥ 0, the adversary finds an -norm-bounded perturbation δ ∈ R d maximizing the prediction loss for input x, y: In our theoretical analysis, we choose the attack norm function as the standard L 2 (Euclidean) norm. Note that the perturbation designed by solving (1) is a function of input data (x, y), which can result in different perturbations for different input samples. On the other hand, a universal adversarial perturbation (UAP) adds the same perturbation to all input data points. Given n training samples (x i , y i ) n i=1 , a standard approach to design a UAP is through the following optimization problem maximizing the averaged prediction loss for the universally-perturbed training 3 data: Given an adversarial attack scheme, an adversarial training method trains the classifier using the generated adversarial examples. As a result, the standard adversarial training method [32] solves the following min-max optimization problem where the perturbations are generated separately for different input data: To perform universal adversarial training through UAPs, [24] introduce the following min-max optimization problem: Note that the standard and universal adversarial training problems have different maximization variables, where the maximization variable in the standard adversarial training problem (3) has a size dependent on the training set size n, while the the maximization variable in the universal adversarial training (4) is independent of the number of training examples.

Universal Adversarial Example Games
In this section, we aim to analyze the transferability features of UAPs. To do this, we extend the adversarial example game framework introduced by [15] to the setting of universal perturbations. This extension, which we call the universal adversarial example game, is based on the following max-min optimization problem searching for the most transferable norm-bounded UAP δ ∈ R d against the most robust classifier over function space F: Note that the above bilevel optimization problem represents a zero-sum game where the UAP player designing an -norm-bounded universal perturbation δ ∈ R d moves first followed by the classifier player f ∈ F predicting the label from the universally-perturbed feature vector. The solution to this max-min problem provides the most transferable universal perturbation with the highest worst-case impact on the classifiers in F. Also, we highlight the difference between the above max-min optimization problem and the min-max problem of universal adversarial training [24,29]. Although these two problems only differ in the order of minimization and maximization, they do not necessarily share the same solution as the game could lack a pure Nash equilibrium where the deterministic minimization and maximization strategies are simultaneously optimal. In the following theorem, we indeed show that under a mild assumption on classifier space F which applies to multi-layer DNN architectures, every universal perturbation achieves the same transferability score against the robust classifier, revealing that the min-max and max-min problems have different solutions.

Theorem 1.
Suppose that for every f ∈ F and bias vector b ∈ R d the function • The minimized objective function in (5) over function space F takes the same value for every choice of δ ∈ R d .
• The universal adversarial example game has no Nash equilibria with a non-zero pure strategy δ * = 0 for the UAP adversary.
Proof. We defer the proof to the Appendix.
Theorem 1 observes that if the classifier set F is closed under the addition of an input bias vector, then the effect of a UAP can be reversed by subtracting the UAP using the bias vector. Hence, one can expect that a UAP could struggle in transferring to other DNN classifiers, since its effect is reversible. In next section, we discuss how to improve the performance of universal perturbations by addressing the reversibility of UAPs in the adversarial example game.

Universal Adversarial Directions
To address the lack of pure Nash equilibria in the universal adversarial example game, we propose a modified notion of universal perturbations. One of the main factors preventing the UAP game from reaching an equilibrium is the UAP adversary's restriction to apply the same perturbation to all input data. As a result, a classifier that knows the UAP in advance can easily reverse the effect of the fixed perturbation. Based on this discussion, we propose considering a universal adversary capable of choosing between adding the universal perturbation or not adding the perturbation for every individual sample. Such a universal adversarial attack is therefore only constrained to generate all the perturbations along the same direction. The discussion motivates the definition of a universal adversarial direction. Definition 1. We call a unit-norm δ a universal adversarial direction (UAD) if the adversarial perturbation δ(x, y) designed for every input (x, y) is aligned with δ, i.e. δ(x, y) = τ x,y δ holds for a scalar τ x,y ∈ R.
To generate a powerful UAD with the maximum impact on a given classifier f , we propose solving the following optimization problem: In the above formulation, every scalar variable τ i represents the magnitude of the additive perturbation τ i δ for the ith data point (x i , y i ). Note that all the perturbations are constrained to be along the optimization variable δ. Taking a standard gradient-based approach to optimize the UAD-based objective function in (6), one can apply the projected gradient method (PGM). Here, the optimization variables δ, τ 1 , . . . , τ n are optimized using the projected gradient ascent algorithm. To derive a stochastic version of the optimization algorithm using a mini-batch of training data at every iteration, we propose Algorithm 1 applying stochastic projected gradient ascent to solve the UAD problem.

A PCA-based Approach to Universal Adversarial Directions
In the previous section, we defined UADs and introduced a gradient-based algorithm for solving the UAD optimization problem. However, since the underlying UAD optimization task maximizes a non-concave objective function, the algorithm is only guaranteed to find a first-order stationary solution under regularity assumptions. In this section, we use a Taylor series-based approximation of the UAD optimization objective to relate the optimal UAD to the top principal component of the fast gradient method (FGM) perturbation matrix. This connection results in an analytically tractable optimization problem for approximating the optimal UAD, which facilitates the analysis of UADs.
To build the connection, we focus on the following Lagrangian version of the UAD optimization problem for a coefficient λ > 0 replacing the role of attack power in the UAD problem: Algorithm 1 UAD-Projected Gradient Ascent Initialize perturbation δ 0 , stepsizes η 1 , η 2 , batch-size B, number of inner updates K for t = 0, · · · , T − 1 do Draw a mini-batch of samples ( Initialize magnitudes τ 0 1 , . . . , τ 0 Assuming that δ 2 ≤ B holds with probability 1 and λ > Bρ, the following inequalities hold for every sample (x i , y i ): Proof. We defer the proof to the Appendix.
The above proposition suggests optimizing the above upper-bound on the UAD optimization objective function approximating the objective function within an error factor of λ+ρ λ−ρ : We observe that the solution to the above optimization problem is indeed the top principal component, i.e. the top right-singular vector, of the following matrix G S (f ) including the loss's gradient for classifier f with respect to training samples in dataset .
The above matrix contains the unnormalized fast gradient method (FGM) perturbations as its rows. Note that if we perform a similar first-order approximation analysis for the UAP optimization, the approximate solution will be the mean of the rows of the above matrix. Therefore, according to the above first-order analysis, the UAD framework approximately substitutes the average row of the loss's gradients used by the UAP approach with the gradient matrix's top principal component, which could better capture the existing structures in the FGM-perturbation matrix G S (f ). We note that the tractability of the PCA-based approach is due to the choice of 2 -norm for the universal direction. For other p -norm functions, the computation of the optimal universal direction could be intractable.
Inspired by several recent works applying stochastic optimization methods for computing the top singular vector [33,34], we propose Algorithm 2 to compute the PCA-based approximation of the optimal UAD. In particular, the stochastic nature of Algorithm 2 suits large-scale machine learning problems where a direct application of the singular value decomposition (SVD) algorithm could be computationally difficult.

Nash Equilibria in UAD Games
We previously discussed that UAPs suffer from the lack of equilibria in the universal adversarial example game. In this section, our aim is to show that a similar zero-sum game adapted for our proposed UADs will indeed possess a non-trivial Nash equilibrium, where a fixed non-zero direction is the most effective UAD against any classifier in function space F the most. To prove such a guarantee, we first define the universal adversarial direction game played between an adversary player searching for the most effective direction δ ∈ R d , along which the designed perturbations can mislead the classifier player f ∈ F. Mathematically, we use the following max-min optimization problem for universal adversarial direction games: Following the PCA-based approximation of the UAD optimization problem and defining f (x i ), y i as the averaged prediction loss over unperturbed training data, we can apply Proposition 1 to formulate the approximate universal adversarial direction game with the following optimization problem with parameter η > 0: Therefore, the min-max problem corresponding to the above approximate UAD optimization task reduces to the following one-level optimization problem where · 2 denotes the L 2 operator norm: (13) The following theorem proves that if for every minimizer f * ∈ F of the above objective function, the matrix G S (f * ) has a unique top singular value, then the approximate universal adversarial example game will possess a Nash equilibrium with a pure strategy for the UAD adversary.
where I d denotes the identity matrix, is convex and compact. Then, • If for every minimizer f * ∈ F of V(f ) the matrix G S (f * ) has a unique top right-singular vector, there exists a Nash equilibrium to the approximate universal adversarial example game with a pure strategy δ * ∈ R d for the UAD adversary.
• If for every minimizer f * ∈ F of V(f ) the matrix G S (f * ) has the top singular value with multiplicity at most r, the approximate universal adversarial example game has a mixed Nash equilibrium where the UAD player always chooses the adversarial direction from a universal r-dimensional space ∆ r ∈ R r×d spanned by a group of r universal vectors {δ * 1 , . . . , δ * r }.
Proof. We defer the proof to the Appendix.
The above theorem shows that unlike the UAP adversarial example game, the UAD-based game can indeed possess Nash equilibria with a pure or in general rank-constrained strategy for the universal adversary player. Hence, Theorem 2 indicates that the UAD adversary can apply a non-trivial pure strategy with the maximum impact on the classifier.
Universal Perturbations' Effectiveness. We performed attacks on the aforementioned DNN models with perturbations generated via UAD-PCA (PCA-based Algorithm 2), UAD-grad (gradient-based Algorithm 1), gradient-based UAP-grad adversaries and generative model-based GAP. We further report results for UAD-01, where we only optimize τ i from [0, 1] with comparable performance. In our experiments, we used the attack power = 0.1 · EP [ X 2 ]. Tables 1, 3 include the results of these experiments along with the reference clean accuracies. As shown in Table 1, UAD perturbations managed to significantly lower the original accuracy, demonstrating significantly higher effectiveness than gradient-based UAPs with the same    maximum allowed norm. The numerical results also suggest the UAD-based attacks have better generalization performance from training sample to test data. We further report the success rates for UAD-PCA, UAD-grad, UAP-grad and GAP perturbations with = .1, .05, .02, .01 · EP [ X 2 ] in the Appendix Tables 4, 5, 6, 7. In addition to the quantitative scores, we also visualized perturbations generated by the UAD-PCA, UAD-grad and UAP-grad adversaries in Figure 1, with = 0.1 · E[ X 2 ] adversarial noise on backbone models; Figure 4, where horizontal rows correspond to perturbations with decreasing powers (0.1, 0.05, 0.02, 0.01). We saw that the UAD adversary creates more regular noise patterns with enhanced semantic locality than UAP-grad. Generalizability and Transferability. We further benchmarked the generalization (from training to test samples) and transferability (from the source DNN to other target DNNs) capabilities of UAD-PCA and gradient-based UAP adversaries on TinyImageNet, CIFAR-100 and CIFAR-10. Comparing UAD-PCA and UAP-grad in Table 2, we verified that the PCA-based UAD perturbations achieve considerably better generalization and transferability performance. Specifically, the UAD adversary consistently outperformed the UAP-grad perturbations in achieving smaller generalization gaps between training and test accuracies. As for the transferability, Table 2 shows the cosine similarity scores between the designed UAD-PCA and UAP-grad vectors for the DNN architectures. As seen in this table, while gradient-based UAPs designed for different DNNs were almost orthogonal to one another, the UADs achieve higher cosine similarity scores across the DNN architectures. In Figures 5, 6, 7, 8 in the Appendix, we visualize the bar plot of the sorted singular values (descending order) for the attempted datasets and architectures. We observed that the loss's gradient matrix G S (f ) for the UAD-PCA perturbation has always a unique top singular value.

Conclusion
In this work, we introduced universal adversarial directions (UADs) as a new variant of universal attacks. We provided theoretical evidence that while the universal adversarial example game lacks pure Nash equilibria, the universal adversarial direction game can possess an equilibrium with a pure strategy for the universal adversary. In addition, our numerical results indicate the improved transferability of the UAD adversary in comparison to gradient-based universal perturbations. Our analysis further introduces a potential extension of the UAD framework to rank-constrained adversarial attack and training schemes. Another interesting future direction to our work is to apply the proposed game-theoretic framework to analyze existing generative model-based adversarial perturbations. Furthermore, analyzing the challenging min-max optimization problem of UADs and their computational complexity is another potential extension of our proposed theoretical framework. [

A.1 Proof of Theorem 1
According to Theorem 1's assumption, for every perturbation δ ∈ R d , the following optimization problems are equivalent: In the above, (a) is a consequence of the theorem's assumption that for every function f ∈ F and bias vector b ∈ R d , f b ∈ F is still a function in F. Also, (b) follows from the change of variable b = b + δ in the optimization problem. Since, the equivalent optimization problem has no dependence on perturbation δ, the optimal value of the optimization problem is independent from the choice of δ. Therefore, the proof of the theorem's first part is complete. We give a proof by contradiction for the theorem's second part. To do this, we suppose that for a pure strategy δ * : δ * ≤ and a general mixed strategy over F characterized by probability distribution P * , a Nash equilibrium in the universal adversarial example game is attained. The Nash equilibrium with pure strategy for the universal adversary implies that: However, as shown earlier, due to the theorem's assumption on function class F, for every vector δ ∈ R d we have Therefore, every δ ∈ R d satisfies: The above inequalities imply that the function g * (δ) := E f ∼P * 1 n n i=1 f (x i + δ), y i takes the same minimum value for every -norm-bounded δ. As a result, the existence of a Nash equilibrium with a pure adversary strategy implies that at the optimal classifier strategy every norm-bounded universal perturbation including the zero perturbation leads to a Nash equilibrium, and the minimum averaged loss does not change by adding any non-zero perturbations. This contradiction of attaining a Nash equilibrium with a trivial zero-universal-perturbation completes the theorem's proof.

A.2 Proof of Proposition 1
To show this proposition, note that under the smoothness assumption in the paper, we have: As a result, since δ 2 ≤ B, we obtain the followings: Note that both the upper-bound and lower-bound in the above inequalities represent quadratic optimization problems, where under the assumption that λ > Bρ, the optimal solutions to the lower-bound and upper-bound optimization problems will be the followings implied by the first-order necessary condition: Plugging the optimal solutions into the bounds will lead to the following inequalities: Therefore, the proof is complete.

A.3 Proof of Theorem 2
Consider the target max-min optimization problem: In the above max-min optimization problem, we can use the trace operator to rewrite the objective function as Here Tr(·) denotes the trace operator, and the above equality holds since the trace operator is linear and satisfies Tr(AB) = Tr(BA) as long as the matrix multiplications AB, BA are well-defined. Based on the 15 above discussion, we apply a change of variables and define the matrix variable ∆ = δδ which leads to the following equivalent max-min optimization problem: Here, S d + denotes the d × d-positive-semidefinite (PSD) cone, · * stands for the nuclear norm, i.e. the sum of a matrix's singular values, and rank(·) is the rank of a matrix. Note that the constraints on matrix variable ∆ requires ∆ = δδ for some vector δ ≤ 1. Also, since G S (f )G S (f ) and ∆ are both PSD matrices, every solution to the above bilevel optimization problem will take the maximum allowable norm value, i.e. ∆ * * = 1 or equivalently for a PSD matrix we have Tr(∆ * ) = 1. Therefore, assuming the loss function only takes non-negative values, the above max-min problem has the same solution as the following max-min problem We can define the equivalent problem using the matrix set According to the theorem's assumption M F is a convex and compact subset of PSD matrices. Also, note that the objective function Tr M ∆ is bi-linear in PSD matrix variables ∆ and M . We also note that the following superset of the maximization problem's feasible set {∆ ∈ S d + : ∆ * ≤ 1} is by definition convex and compact. As a result, Sion's minimax theorem [42] implies that the following min-max and max-min problems share a common saddle-point solution (∆ * , M * ): However, note that since the L 2 -operator norm ( · 2 ) and nuclear norms are dual to each other: Therefore, based on the theorem's first assumption that for every minimizer f * ∈ F for the min-max problem, the matrix G S (f * ) has a unique top singular value or equivalently the PSD matrix has a unique top eigenvalue, then the corresponding maximization solution ∆ * f * will be rank-1, as the matrix's nuclear norm needs to be concentrated on the top right-singular vector of G S (f * ). As a result, there exists a shared solution (f * , ∆ * ) for the min-max and max-min problems in (21) where ∆ * is a rank-1 matrix. Since this solution satisfies the maximization constraints of the original max-min problem in (20) with the maximization feasible set being a subset of the feasible set in (20), (f * , ∆ * ) will also be a solution to (20). Similarly, (f * , ∆ * ) is also a solution to the min-max version of (20), since the max-min inequality implies that Tr M ∆ and in the above min-max problem, matrix M f * achieves the lower-bound given by the max-min formulation.
Thus, (f * , ∆ * ) is a saddle-point for the original max-min optimization problem, and therefore results in a pure Nash equilibrium to the approximate universal adversarial direction game. Hence, the proof of the theorem's first part is finished.
Next, under the theorem's second assumption that for every minimizer f * ∈ F of the min-max problem, the corresponding matrix G S (f * ) has a top singular value with multiplicity at most r or equivalently the PSD matrix M f * = L S (f * )I d + ηG S (f * )G S (f * ) has a maximum eigenvalue with multiplicity at most r, then we have a saddle point solution (∆ * , M f * ) for (21) where ∆ * is of rank r. Therefore, we assume that the orthonormal unit-norm vectors in {δ * 1 , . . . , δ * r } are the top eigenvectors of ∆ * . Note that the solution (∆ * , M f * ) will solve the following problem since the maximization problem's feasible set in the following problem is a subset of the the one in (21).
In addition, (∆ * , M f * ) will solve the min-max problem corresponding to the above task, because it achieves the lower-bound coming from the following max-min inequality As a result, the rank-r ∆ * combined with a mixed strategy for the classifier player choosing f ∈ F results in a mixed Nash equilibrium for the following max-min game: This Nash equilibrium implies the existence of mixed strategies for the universal adversarial direction and classifier players where the universal adversary always generates the perturbation from the rank-r subspace of ∆ * 's range spanned by orthonormal vectors in {δ * 1 , . . . , δ * r }. Therefore, the theorem's proof is complete.

B.2 Additional Numerical Results on Generalizability and Transferability of UADs vs. UAPs
To measure the transferability and strength of the perturbations, we quantified the explained transferred fooling rate of UADs and UAPs across different DNN architectures. τ i δ a is the transferred (designed for a different model) universal attack's perturbation for sample x i , while τ i δ m is the original (designed for the same model) attack's perturbation. Consider the following evaluation measures: We defined and evaluated the following Transferred Fooling Rate (TFR) score in our experiments: TFR = T P + T N T P + F N + T N + F P Intuitively, TP (true positive / explained and transferred ability to fool) means both the transferred and original adversarial perturbations fool the source model (i.e., the model prediction on the transfer-perturbed sample is not equal to that on unperturbed sample but is equal to that on the original-perturbed sample); TN (true negative / unexplained and untransferred ability to fool) means the unexplained ability to fool the source model; FP (false positive / explained and transferred inability to fool) means neither the original nor transferred adversarial perturbations are able to fool the network; FN (false negative / unexplained and untransferred inability to fool) means the transferred attack neither fools the model nor does it have a prediction that corresponds to the original perturbed result. Since the measurement already accounts for the transferability between models, a higher TFR indicates both better transferability and fooling ability. Tables 11, 12, and 13 include the measured TFR scores across different DNN architectures and datasets, which suggest a generally higher transferability rate for the proposed UAD attacks in comparison to gradient-based UAPs.
Finally, singular value decomposition (SVD) was performed on the matrix of the loss function's gradients with respect to the input image samples on the TinyImageNet dataset, in order to compare the universality of perturbation. These results are visualized in Figures 5, 6, 7, 8. We observed that the loss's gradient matrix G S (f ) used for generating the UAD perturbations has always a unique top singular value across train and test sets.          Table 9: UAD-grad cross-network transferability via cosine similarities of the universal perturbations designed for the target DNNs (columns), using = 0.05 · E[ X 2 ].