A Phase Transition Induces Catastrophic Overfitting in Adversarial Training

Dear Reviewer bJoQ,

Thanks for your review and for helping us improve the quality of our work. We respond to your points as follows:

• P1: Although interesting, the toy example used in this paper is too simplified, which is far away from what we meet in deep learning.

That is true, the model that we employ to replicate CO is overly simplistic. But we believe that is the reason why it is a good model. The fact is that we can replicate the CO phenomena ocurring in large scales with a single parameter model. The simplicity of this model allows us to deeply analyze the problematic behaviours of AT leading to CO.

• P2: In section 2.1, the paper uses $c$ to represent the number of classes, while in section 3 $o$ is used.

Thanks for highlighting this inconsistency, we have updated the notation to use $o$ everywhere.

• P3: Typo: the dataset should be $\{x_i,y_i\}^{n} _{i=1}$ not $\{x_i,y_i\}^{i} _{i=1}$.

Thanks for pointing out this typo, it has been corrected.

• P4: $\alpha_S=1/S$ should be stated in the conditions of Proposition 3.1. In practice $\alpha_S > 1/S$ is employed.

Thanks for highlighting this issue, we have included it in the statement of Proposition 3.1

• P5: The authors should formally define CO.

Thanks for the suggestion, we have included a formal definition of CO in Definition 2.1. We believe this definition contributes to an easier understanding of our paper.

• P6: In lines 194-195, how do you quantify "high" curvature, please be more clear.

For curvature, we refer to $|\mathcal{R}_{2}|$ in Proposition 3.1, i.e., the absolute value of second order directional derivatives.

• P7: In lines 187-189, do you refer to FGSM solutions or AT solutions?

We refer in general when applying AT to any problem. The fact that we can show that such solutions exist in Theorem 4.1 means that for certain datasets and models, degenerate solutions with CO for any $S$ and $\epsilon$ do exist.

• P8: The proofs of the Corollaries are missing, please clearly state them.

We apologize for initially not including our proofs in the manuscript. Our corollaries are a very straightforward derivations from Proposition 3.2 and Theorem 4.1. We have included very detailed proofs in Appendix E.

• P9: What is the significance of Proposition 3.2?

We have rewritten the statement in Proposition 3.2 to be more direct and clear. The proposition simply states that training in a re-scaled dataset is equivalent to training in a standard dataset with re-scaled $\epsilon$. This has consequences as being able to produce CO for any $\epsilon$ by re-scaling the data.

Please let us know if any aspect of the paper remains unclear.

Dear Reviewer 4U7J,

Thanks for your careful reading of our manuscript. We address your questions and weaknesses in the following:

• P1: Authors assume that $\mathcal{L}$ is at least twice continuously differentiable. This assumption is missing.

Thank you for pointing this out. We have include this in the statement of Proposition 3.1.

• P2: [1,2] previously studied the implicit bias of AT, how does your analysis connect with theirs?

Thank you for bringing this work to our attention, they offer an interesting point of comparison with our results. In essence, these work studied the implicit bias of the solutions that a neural network trained adversarially arrive to, extending the SVM results of Soudry (2018) and others, from standard gradient descent training to the adversarial setup, finding the equivalent SVM solution in these cases. These works focus on a specific question: given a constraint (separable data, homogeneous networks), which set of equations must be satisfied by the network parameters at the infinite time limit under gradient flow dynamics, concluding that the adversarial margin must be maximized. We ask a much simpler question in a very general setting: what effective objective is being optimized by a neural network given a fixed adversarial perturbation budget. While these questions are certainly connected, our focus was geared towrd implicit regularization and a loss landscape approach, rather than the max margin formulation. We believe it is possible to rephrase our results in the SVM language. We have included this explanation as well as the references in the revised manuscript.

• P3: Your theoretical insights are extracted from the toy model, the connection with more practical scenarios is unclear.

While it is true that our insights are extracted from the toy model, the implicit bias/regularization analysis is valid in general, with the toy model serving as a fully tractable example in which the phenomenology can of CO as a phase transition can be seen. The empirical results given in Fig.3 and Fig.4 show that our results qualitatively extend to real world cases, while the quantitative predictions must depend on the task/architecture and data, we further discuss this point in Section 5.3.

• P4: How does Proposition 3.1 characterize the properties of the converged solution?

Proposition 3.1 charecterizes the effective loss being optimized, meaning that the solution must satisfy the constraints imposed by the new terms, proportional to powers of $\epsilon$. We show that both in the toy model and in real world cases, the CO solutions are the ones which satisfy these constraints by setting the Hessian to large negative values, which results from a transition from the previous minimum of the network (on the original loss) to a new, overfitting minimum on the effective loss.

• P5: When and how will the term promotional to $\epsilon^{2}$ become more significant than the the term promotional to $\epsilon$ as discussed in line 192-193?

We can approximate this point by assuming the first and second term are bounded as $R_1,R_2$ respectively, and so we can simply equate their absolute values (or traces) as $\frac{\epsilon}{S} R_1 = \frac{\epsilon^2}{2S^2} R_2$ to obtain a threshold value at $\tilde{\epsilon} = 2 R_1 S/R_2$, at this point the second term is equivalent in contribution to the first, and should be accounted for in the effective loss.

Dear Reviewer UJp8,

Thanks for your thorough review and carefully checking the theoretical details. We respond to your concerns as follows:

• P1: "A more valuable direction would be identifying the conditions under which catastrophic overfitting does not occur"

There are many works on this direction, such as GradAlign, LLR, CURE or ELLE, that we cover in the introduction. In most works, local linearity is assumed. In this case it is impossible for CO to happen as the single-step solution is the global solution of the inner maximization problem, therefore, the network cannot overfit to only classify well the single-step adversarial examples.

In this work, we address the question of understanding why CO appears. Concretely, we discover that a phase transition induces CO in single-step AT, we show that CO can ocur with arbitrarily small $\epsilon$ and provide a mechanisms to induce CO for smaller $\epsilon$ in any dataset or model by simply re-scaling the data.

• P2: "the toy model settings differ significantly from those in deep learning models, suggesting that the theoretical insights derived from the toy model may have limited applicability to real-world deep learning scenarios"

While it is true that some of our insights are extracted from the toy model, all of our insights match the experimental observations in large scale models in the literature, e.g., the sudden appearance of CO for $\epsilon$ avobe a critical value $\epsilon_c$, or the appearance of CO for multi-step AT.

• P3: Proposition 3.1 omits the projection operator in line 7 of Algorithm 1.

Note that since $\alpha = 1/S$, and $\sigma=0$, it is guaranteed that all the perturbations along the PGD attack will be inside the ball, i.e., $||\mathbf{\delta}_{s}^{i}|| _{\infty} \leq \epsilon ~~ \forall s \in [S]$, and the projection results in the identity mapping. We have clarified this in the proof of Proposition 3.1.

• P4: When updating $\mathbf{\delta}_{s}^{i}$ in PDG-AT, the gradient should be taken w.r.t. $\mathbf{\delta}$ rather than w.r.t. $\mathbf{x}$.

Please note that $\nabla_{\mathbf{x}}h(\mathbf{x} + \mathbf{\delta}) = \nabla_{\mathbf{\delta}}h(\mathbf{x} + \mathbf{\delta})$ for any differentiable function $h : \mathbb{R}^{d} \to \mathbb{R}$. We have added a remark in lines 103-105.

• P5: How is Corollary 3.3 derived from Proposition 3.2?

Intuitively, Proposition 3.2 states that performing AT in re-scaled dataset with adversarial budget $\alpha\cdot \epsilon$ is effectively the same as performing AT in the standard dataset with adversarial budget $\epsilon$. This means that every phenomenon observed with adversarial budget $\epsilon$ in the standard dataset, will be observed with adversarial budget $\alpha\cdot \epsilon$ for the re-scaled dataset. That includes CO. We have included a detailed proof in Appendix E.

• P6: The writting could be improved. Theorem 4.1 and Corollaries 4.2 and 4.3 are not clearly explained. The connection between the theory and practical implications is not clear.

We apologize for not conveying our message clearly, we have improved our writting by:

1. Formally defining CO in Definition 2.1.
2. Rewritting the statement of Proposition 3.2 and Theorem 4.1.
3. Including the proofs of all the Corollaries.

With respect to the relationship between the insights in the small model, we believe it is clear that similarly to the toy model:

1. Agreeing with Corollary 4.2: There is a clear phase transition with a critical value $\epsilon_c$ for every studied dataset and various $S$ values. Leading to nearly zero PGD-20 accuracy for $\epsilon > \epsilon_c$. This is observed in practically in Figure 3.
2. Agreeing with Corollary 4.3: When the norm is constrained (Practically with weight decay), larger number of steps $S$ produce larger $\epsilon_c$. Observed for SVHN in Figure 3.

• P7: In the top panel of Figure 1, why is catastrophic overfitting attributed to the increased curvature of the local minima?

Please note that CO is related to a high curvature of the loss with respect to the input. In the top panel we simply select the solutions for both the FGSM and AT objectives. Curvature is displayed in the bottom panel, where for larger $\epsilon$, the sinusoidal classifiers obtained with FGSM present a very high frequency, i.e., curvature.

• P8: In Theorem 4.1, what does $\theta_{k}^{\star}$ represent? Why do we choose $\theta_k$ as $b_k$?

$\theta^{\star}$ is a solution that attains the minimum loss $\mathcal{L}^{⋆} = \log(1 + e) − 1 ≈ 0.3133$. As explained in the proof of Theorem 4.1, $\mathcal{L}^{⋆}$ is attained when $\sin(\theta_{k}^{\star}\cdot(x_i + \delta_{S}^{i})) = y_i$. We believe that introducing $\theta_{k}^{\star}$ in the analysis is not necessary. We have rewritten Theorem 4.1 to compare against the optimal loss value $\mathcal{L}^{⋆}$ to simplify the presentation.

Dear reviewer UJp8,

Thanks for your response and the thorough feedback on the revised version of the manuscript. We answer to your remaining concerns as follows:

Regarding the writing of Section 3

We appreciate your detailed feedback about the writing of this section. We apologize if the main ideas are not easy to extract at the moment. We believe that given your feedback, it is a good idea to integrate Sections 3 and 4 together. We can first pose the three questions an then combine Sections 3 and 4, pointing at how each insight from our theory connects to the questions. Moreover, this way, the connection between the toy model and large scale results can be made more clear. However, given that there are less than 13h remaining to update the manuscript, we believe the time is not enough to provide the desired quality. We can work on making sections 3 and 4 more reader friendly for the camera ready version.

Overall, leaving the readability aside, we believe the three questions we point out are covered in the paper, let us explain:

• Question (i) Can we have PGD AT solutions where curvature is high?

Proposition 3.1 and the results in Section 5.4 answer this question affirmatively both theoretically and practically. Moreover, the theoretical results in Theorem 4.1, show that this is also the case in the toy model, where curvature along the PGD trajectory is proportional to $\theta_k^{2}$. Given that $\theta_k$ is proportional to $1/\epsilon_k$, this results in higher curvature solutions the smaller $\epsilon_k$ is.

• Question (ii) Can we have solutions where CO appears for any $S$ and $\epsilon$?

As you pointed out, via re-scaling the data, Corollary 3.3 gives us a mechanism to induce CO for arbitrarily small $\epsilon$. Nevertheless, this is not our strongest result. Check that Theorem 4.1 provides analytical solutions to the AT problem in the toy model for arbitrarily small $\epsilon_k$ and arbitrarily large $S$.

• Question (iii) Can we understand why these solutions do not appear in practice?

In lines 238–246, we argue that adding noise prior the PGD attack ($\sigma > 0$) and weight decay can help avoid CO. The noise argument is an intuition arising from our theory and since it is not fully understood, it has been included in the limitations of our work. Regarding weight decay, our result in Corollary 4.3 in the toy model and the experimental results in Figure 3 confirm that: Constraining the parameter norm and increasing the number of PGD steps $S$ can avoid CO.

We will make sure these aspects are covered more clearly in the revised version of the manuscript. Thanks for helping us improve the readability of the paper.

About dataset re-scaling

As mentioned in our response to Reviewer bJoQ, our target with this theoretical result and experiment, was to show that the scale of $\epsilon_c$ is not only dependent on the hyperparameters of Algorithm 1. Our result in Corollary 3.3 shows that $\epsilon_c$ can be re-scaled independently of Algorithm 1 just by re-scaling the data. This result is somewhat expected, as re-scaling the data and perturbations is perceptually invariant to the human eye. Nevertheless, we believe that the independence of Algorithm 1 and data re-scaling, is a valuable and interesting result.

Further questions

• P1: On the construction of $\theta_k$ through Theorem 4.1

In Theorem 4.1 we characterize the possible solutions of the AT problem when solved with Algorithm 1. Nevertheless, the convergence of Algorithm 1 to one of these solutions is not guaranteed. As other local minima exist (See Figure 1 top row), convergence will depend on the initialization of the weights, the learning rate and the order of data samples seen during training. This is not covered in Theorem 4.1.

• P2: Connection between Theorem 4.1. and CO

For a connection between Theorem 4.1 and CO please check Corollary 4.2. In Theorem 4.1, the Upper bound in the optimality gap vanishes to $0$ when increasing $a$. This shows that the optimal loss is achieved. In Corollary 4.2 we show that this results in a correct classification of the PGD points and misclassification of the points $x_i \pm \frac{\epsilon_k}{2\cdot S}$. Given our characterization of CO in Definition 2.1, this is exactly $(0,0)$-CO.

• P3: What is the relationship between Theorem 4.1, Corollary 4.3 and the observations in Figure 3?

In Figure 3, the critical value $\epsilon_c$ is larger when increasing $S$, this is exactly the theoretical insight from Corollary 4.3 in the toy model and the answer to Question (iii).

• P4: "Our analysis in the toy model covers the existence of a CO solution with lower loss than the robust solution for larger $\epsilon$"

The robust solution is given by $\theta=1$ in the toy model. In Figure 1, we can see that the FGSM loss at $\theta=1$ is higher than the optimal loss $\mathcal{L}^{\star}$ attained at $\theta_{\text{FGSM}}$ for $\epsilon > \epsilon_c$.

Dear Reviewer vMYY,

Thanks for your review. At the moment your review seems incomplete, we would like to ask if the reviewer has any other concerns. Regarding the concerns raised in your review, our answer is as follows:

• P1: "Adversarial Training (AT) (Madry et al., 2018) and its variants ..." It is better to replace this descirbtion with "one of the most".

We have incorporated your suggestion in the manuscript and referenced RobustBench.

• P2: "According to this sentence, the motivation of studying underlying phenomenon resulting in CO is insuficient. Moreover, there is little logical connection before and after."

We do not understand the point of the reviewer, Could you please be more specific?

• P3: ".It is redundant to introduce the known PGD algorithm 1, if you don’t bring in additional important ideas. Besides, the initialization of perturbation is random, not just $0$."

We believe it is necessary for our analysis to present the PGD AT algorithm. It is true that the initialization in practice is uniform as we discuss in lines 221-222 of the original submission. We have updated line 4 of Algorithm 1 to contemplate this possibility and clarified that our analysis follows with $\sigma=0$.