Provable Robust Overfitting Mitigation in Wasserstein Distributionally Robust Optimization

We appreciate the thoughtful questions and comments of the reviewer. Below are our responses to your queries:

---

1. Limited Improvements in Numerical Experiments

We would like to emphasize that our method is currently one of the most effective in mitigating robust overfitting. Furthermore, while addressing robust overfitting, our method still achieves the highest robust accuracy, demonstrating its effectiveness in balancing both aspects. We believe that with further research, particularly in improving the solution methods for SR-WDRO, even greater advancements can be achieved. We are committed to refining our approach and further enhancing its performance in future work.

---

2. Highlighting Technical Challenges

We appreciate feedback on the need to better emphasize the technical challenges addressed in our work. We would like to highlight several key technical challenges of our work:

(1). Generalization Theorems:
Firstly, in proving our generalization theorems in Section 4.2, we faced the challenge of not being able to rely on the dual form of WDRO as in previous works [1,2]. Instead, we employed the Large Deviation Principle to demonstrate that the test distribution falls within our defined ambiguity set with high probability. This was a significant shift from conventional methodologies and is fundamentally different from the standard WDRO.

More specifically, the conditions required for the generalization bound in [2] differ significantly from ours. In particular, the results in [2] rely on several assumptions about the loss function, including its Lipschitz continuity and boundedness, which are not required in our framework. Furthermore, the form of the generalization bounds in [2] is entirely different from ours. Our bound provides a generalization guarantee where the probability of failure (i.e., the complement of the confidence level) decays exponentially with the sample size $n$. Moreover, the rate of decay is directly influenced by $\gamma$.

• Our Bound (Theorem 3):

$P(E_{D}[L(\theta, z)] \leq \mathcal{L}_{\varepsilon, \gamma}(\theta, D_n) )\geq 1 - e^{-\gamma n} \left(\frac{4}{\delta}\right)^{m(\mathcal{Z}, \delta)}, \quad \text{where} \quad \delta = (\frac{\varepsilon}{diam(Z)+1})^p.$

• WDRO’s Bound (Theorem 3.1 in [2]):

$$P(E_{D}[L(\theta, z)] \leq L_{\varepsilon, 0}(\theta, D_n) ) \geq 1 - \delta,$$

where $\varepsilon$ must satisfy:

$$\mathcal{O}\left(\sqrt{\frac{1 + \log(1/\delta)}{n}}\right) \leq \varepsilon \leq \frac{\varepsilon_c}{2} - \mathcal{O}\left(\sqrt{\frac{1 + \log(1/\delta)}{n}}\right),$$

and $\varepsilon_c$ is a constant that depends only on the loss function and the data distribution $D$. The computation of this bound requires the dual form of WDRO.

(2). Game Equilibrium:
Secondly, establishing the existence of the game equilibrium in Section 4.3 was another technical hurdle. We had to prove the compactness of our newly defined ambiguity set and verify certain continuity conditions of the loss function. These proofs were nontrivial. Furthermore, the Stackelberg equilibrium is first established by us in the WDRO regime, which requires essentially a weaker condition than that of Nash.

---

3. Analyzing WDRO in Neural Networks

Our framework is designed to be versatile, with $\theta$ capable of representing any model type, including neural networks. In our exploration of adversarial distribution shifts, $\theta$ specifically denotes neural networks, such as ResNet. This enables us to directly apply and analyze our SR-WDRO approach within the context of neural networks, effectively addressing the phenomenon of robust overfitting.

---

References

[1] An, Y., Gao, R. (2021). Generalization bounds for (Wasserstein) robust optimization. Advances in Neural Information Processing Systems, 34, 10382-10392.

[2] Azizian, W., Iutzeler, F., Malick, J. (2023). Exact generalization guarantees for (regularized) wasserstein distributionally robust models. Advances in Neural Information Processing Systems, 36, 14584-14596.

For Questions

1. Step 10 in Algorithm 1

According to Eq.(9), initially, we generate adversarial examples for a given batch. Once adversarial examples $\{(x_i', y_i)\} _ {i=1}^n$ are identified, the task of computing $$p_i$_{i=1}^n$ becomes a convex optimization problem. Specifically:

• The objective is to maximize the weighted loss:

  $$\max \sum_{i=1}^n p_i L\left(\theta, {(x_i', y_i)}\right),$$

  subject to the following constraints:

  • (\sum_{i=1}^n p_i = 1\),
  • (KL(q \| p) = \sum_{i=1}^n q_i \log \left(\frac{q_i}{p_i}\right) \leq \gamma\), where $(q = \left(\frac{1}{n}, \cdots, \frac{1}{n}\right))$.

Then, this optimization can be efficiently executed using standard solvers.

2. Updating Adversarial Examples

Updating Adversarial Examples: We use the sign function for updating adversarial examples due to its effectiveness in generating perturbations. The sign function, as employed in famous methods like FGSM[1] and PGD[2], ensures that perturbations are uniformly small, yet sufficient to cause misclassification, adhering to the constraint $||\eta||_\infty$.

---

3. Comparison with Phan et al. (GLOT)

We thank the reviewer for highlighting the related work by Phan et al. [3], which enhances distributional robustness through local and global regularization. This approach is different from ours: we use KL divergence to enlarge the ambiguity set, thereby explicitly addressing statistical error, while Phan et al. [3] use KL divergence as a regularization term, akin to the TRADES method [4]. We will discuss their method in our revised manuscript and include experimental comparisons (have mentioned before) to highlight the distinct strengths and contributions of each approach.

---

4. Performance Under Natural Distributional Shifts

Performance under Natural Distributional Shifts: Our framework is indeed designed to accommodate various types of distributional shifts, including but not limited to the adversarial examples that we primarily discuss. We can theoretically extend our robustness guarantees, similar to those in Theorem 4, to other distributional shifts, provided that they remain within a certain bounded distance.

To address this point, we have included additional theoretical analysis and discussions in the appendix A.3 of our revised manuscript to clarify these robustness guarantees under broader conditions.

---

References

[1] Goodfellow, I. J., Shlens, J., & Szegedy, C. (2014). Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572.

[2] Madry, A., Makelov, A., Schmidt, L., Tsipras, D., & Vladu, A. (2018). Towards deep learning models resistant to adversarial attacks. ICLR.

[3] Phan, H., et al. (2023). Global-local regularization via distributional robustness. International Conference on Artificial Intelligence and Statistics (AISTATS).

[4] Zhang, H., Yu, Y., Jiao, J., Xing, E., El Ghaoui, L., & Jordan, M. (2019). Theoretically principled trade-off between robustness and accuracy. International Conference on Machine Learning (ICML).

We sincerely appreciate the reviewer's thoughtful questions and constructive feedback. Below, we provide our responses, carefully addressing both weaknesses and specific questions.

---

Addressing Weaknesses

1. Scope of Experiments
   We appreciate the reviewer's observations regarding the scope of our experiments. In response, we have expanded our experimental section to include comparisons with the work GLOT by Phan et al. [1], as suggested. As shown in the following table, our experiments on CIFAR10 with ResNet18 demonstrate that while GLOT reduces adversarial overfitting through global and local regularization, our method, SR-WDRO, achieves substantially better robustness on the test set, with an improvement of about 3% on CIFAR-10.

Additionally, we have conducted experiments using larger network architectures WideResNet28-10 on CIFAR10 to further validate the scalability and robustness of our method. These results show that our approach consistently outperforms the baselines and maintains strong performance across various architectures, as shown in the following table.

2. Trade-off Between Adversarial Robustness and Natural Accuracy
   Regarding the observed trade-off between adversarial robustness and natural accuracy, we acknowledge this issue, as highlighted in Table 1. While this trade-off exists, our approach is notably effective in mitigating robust overfitting during training, which we consider a critical achievement. Robust overfitting is a significant challenge in adversarial training, and our method explicitly addresses this challenge. We acknowledge the importance of balancing robustness and accuracy and are committed to exploring further methods to address this trade-off more effectively in future work.

[1] Phan, H., et al. (2023). Global-local regularization via distributional robustness. International Conference on Artificial Intelligence and Statistics (AISTATS).

2. Theoretical Concerns

We appreciate the reviewer's insightful comments and the opportunity to clarify the theoretical distinctions between SR-WDRO and WDRO.

1. Comparison to WDRO:
   Our framework fundamentally distinguishes itself from standard WDRO by requiring $\gamma > 0$ to explicitly account for statistical error. In contrast, standard WDRO corresponds to the case where $\gamma = 0$, as the reviewer mentioned, the bound becomes $P(\cdot)$ is greater than a large negative, which is meaningless. However, as indicated in our experimental results, standard WDRO often suffers from robust overfitting due to its inability to effectively address statistical error. By setting $\gamma > 0$, our method mitigates this issue and enhances robustness, representing a significant shift from conventional WDRO approaches.
   From a theoretical perspective, our framework differs from standard WDRO in both the assumptions required and the form of the generalization bounds:

• Assumptions:
  The generalization bounds in [2] rely on additional assumptions about the loss function, such as Lipschitz continuity and boundedness, which are not required in our framework.

• Form of the Bounds:
  The bounds in our framework are fundamentally different from those of WDRO. Our bound provides a generalization guarantee where the probability of failure (i.e., the complement of the confidence level) decays exponentially with the sample size $n$. Moreover, the rate of decay is directly influenced by $\gamma$.

  For clarity, we summarize the key differences below:

  Our Bound (Theorem 3):

  $P(E_{D}[L(\theta, z)] \leq \mathcal{L}_{\varepsilon, \gamma}(\theta, D_n) )\geq 1 - e^{-\gamma n} \left(\frac{4}{\delta}\right)^{m(\mathcal{Z}, \delta)}, \quad \text{where} \quad \delta = (\frac{\varepsilon}{diam(Z)+1})^p.$

  WDRO’s Bound (Theorem 3.1 in [2]):

  $$P(E_{D}[L(\theta, z)] \leq L_{\varepsilon, 0}(\theta, D_n) ) \geq 1 - \delta,$$

  where $\varepsilon$ must satisfy:

  $$\mathcal{O}\left(\sqrt{\frac{1 + \log(1/\delta)}{n}}\right) \leq \varepsilon \leq \frac{\varepsilon_c}{2} - \mathcal{O}\left(\sqrt{\frac{1 + \log(1/\delta)}{n}}\right),$$

  and $\varepsilon_c$ is a constant that depends only on the loss function and the data distribution $D$. The computation of this bound requires the dual form of WDRO.

2. Existence of Game Equilibria:
   In response to the reviewer's question regarding Section 4, we acknowledge that under similar assumptions, WDRO can indeed admit Nash equilibria when viewed as a game-theoretical problem [3]. However, proving the existence of equilibria in SR-WDRO is more complex due to the introduction of a new uncertainty set. Furthermore, the existence of Stackelberg equilibrium (needs a weaker condition than that of Nash equilibrium) is first considered in this paper.

References:
[1] An, Y., Gao, R. (2021). Generalization bounds for (Wasserstein) robust optimization. Advances in Neural Information Processing Systems, 34, 10382-10392.

[2] Azizian, W., Iutzeler, F., Malick, J. (2023). Exact generalization guarantees for (regularized) wasserstein distributionally robust models. Advances in Neural Information Processing Systems, 36, 14584-14596.

[3] Shafieezadeh-Abadeh, S., Aolaritei, L., Dörfler, F., Kuhn, D. (2023). New perspectives on regularization and computation in optimal transport-based distributionally robust optimization.

3. Experiments Concerns

We appreciate the reviewer's detailed feedback and recognize the need to address these experimental concerns.

1. Effectiveness of Our Method:
   It is worth emphasizing that our method is currently among the most effective in mitigating robust overfitting, as demonstrated by our experimental results. We would like to further highlight that WDRO-type methods are indeed necessary in adversarial training settings. Prior works [1, 2] have extensively validated the advantages of WDRO-type approaches, both empirically and theoretically, demonstrating their strong generalization guarantees. Similar to adversarial training, WDRO-type methods serve as a foundational framework for robust training. Additionally, as you have suggested, techniques such as SWA or EMA can be incorporated into WDRO-based approaches to further enhance performance. We appreciate this suggestion and believe it highlights the potential for complementary improvements in future work.

2. SR-WDRO as a Fundamental Framework:
   We would like to emphasize that our method, similar to adversarial training, serves as a fundamental framework for robust learning. Just as other types of methods have built upon adversarial training to achieve further improvements, these approaches can also be applied on top of SR-WDRO to enhance its performance. We agree that incorporating these advancements is a valuable direction, and we plan to explore such extensions in future work to further improve the effectiveness of SR-WDRO.

3. Additional Experiments:
   We have conducted additional experiments using WideResNet28-10, a larger model commonly used in the adversarial training community. As shown in the following table, it can be observed that our method achieves the best performance in mitigating adversarial overfitting, and it achieves the highest robust accuracy, demonstrating the effectiveness of our approach on large models. | Robust Methods | Nat Accuracy (%) | Final Robust Test Acc (%) | Best Robust Test Acc (%) | Diff (%) | |------------------|-------------------------|---------------------------|---------------------------|---------------------| | PGD-AT | 86.51 ± 0.16 | 48.81 ± 0.49 | 55.64 ± 0.07 | 6.83 ± 0.55 | | UDR-AT | 85.99 ± 0.15 | 49.01 ± 0.13 | 55.82 ± 0.19 | 6.81 ± 0.31 | | HR | 84.89 ± 0.16 | 48.45 ± 0.31 | 52.45 ± 0.27 | 4.00 ± 0.34 | | GLOT | 86.57 ± 0.22 | 49.45 ± 0.32 | 52.26 ± 0.46 | 2.81 ± 0.15 | | Ours | 84.52 ± 0.27 | 51.26 ± 0.42 | 53.87 ± 0.06 | 2.61 ± 0.47 |

References:
[1] Bui, T. A., Le, T., Tran, Q., Zhao, H., Phung, D. (2022). A unified wasserstein distributional robustness framework for adversarial training.

[2] Phan, Hoang, et al. Global-local regularization via distributional robustness. International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

We sincerely appreciate the reviewer's feedback. We will address your concerns in three sections: Clarity Issue, Theoretical Concern, and Experiments Concern. Additionally, we have corrected the minor issues you pointed out in the revised version of our paper. Thank you for your valuable insights.

---

1. Clarity Issues

To address the reviewer's concerns regarding clarity and the definition of statistical error, we offer the following explanations.

1. Definition of Statistical Error:
   In our paper, the statistical error refers to the discrepancy between the finite sample data used during training and the true underlying data distribution, which was also used in this way in [1, 2]. This error arises because the limited dataset can only approximate the full distribution.

2. Statistical Error from Finite Samples:
   Training on finite samples inherently introduces statistical error due to the sampling randomness and limited size of the training dataset. As a result, the empirical loss only serves as an approximation of the true out-of-sample loss and is subject to fluctuations caused by the randomness of the finite sample. This discrepancy can lead to scenarios where solutions appear effective in-sample but fail to generalize well out-of-sample, resulting in the phenomenon of overfitting.

3. Mitigating Statistical Error with KL Divergence in WDRO:
   Building on the exploration of KL divergence's advantages in addressing statistical error, as demonstrated in Van Parys et al. [3], the KL-DRO predictor efficiently guards against overfitting by considering the worst-case expectation across a set of distributions, we have incorporated KL-DRO into WDRO framework. This integration helps to guard against robust overfitting and improves generalization by considering a range of distributions that include the true out-of-sample distributions with high probability.

References:
[1] Bennouna, A., Van Parys, B. (2022). Holistic robust data-driven decisions.

[2] Bennouna, A., Lucas, R., Van Parys, B. (2023, July). Certified robust neural networks: Generalization and corruption resistance. In International Conference on Machine Learning (pp. 2092-2112). PMLR.

[3] Van Parys, B. P., Esfahani, P. M., Kuhn, D. (2021). From data to decisions: Distributionally robust optimization is optimal. Management Science, 67(6), 3387-3402.

We appreciate the reviewer’s thoughtful questions and insightful comments. Below, we address your concerns point by point:

---

1. Regarding the condition $\gamma > m(\mathcal{Z}, \delta) \cdot \log(4/\delta)/n$

We understand that this condition might appear strong due to the exponential dependency on the dimensionality of the sample space $\mathcal{Z}$. However, it is important to note that the cover number is inherently not excessively large in practice because the intrinsic dimensionality of the sample space is often much lower than its ambient dimension. For instance, the intrinsic dimensionality of MNIST is around 13, CIFAR-10 approximately 26, and ImageNet between 26 and 43 ([1], [2]). This intrinsic dimension can be directly used in our theory, instead of the ambient dimension, which significantly reduces the burden of this condition in practical scenarios. We will clarify this distinction in the revised version of the paper, as discussed in Remark 5 of Section 4.2.

Additionally, as the number of samples $n$ becomes sufficiently large, we can consistently find appropriate values of $\gamma$ that satisfy the condition. Empirically, we observe that properly chosen $\gamma$ values enhance generalization performance on the test set, further validating this condition in practice.

---

2. Comparison with standard WDRO

Our framework fundamentally distinguishes itself from standard WDRO by requiring $\gamma > 0$ to explicitly account for statistical error. In contrast, standard WDRO corresponds to the case where $\gamma = 0$. However, as indicated in our experimental results, standard WDRO often suffers from robust overfitting due to its inability to effectively address statistical error. By setting $\gamma > 0$, our method mitigates this issue and enhances robustness, representing a significant shift from conventional WDRO approaches.

From a theoretical perspective, our framework differs from standard WDRO in both the assumptions required and the form of the generalization bounds:

• Assumptions:
  The generalization bounds in [2] rely on additional assumptions about the loss function, such as Lipschitz continuity and boundedness, which are not required in our framework.

• Form of the Bounds:
  The bounds in our framework are fundamentally different from those of WDRO. Our bound provides a generalization guarantee where the probability of failure (i.e., the complement of the confidence level) decays exponentially with the sample size $n$. Moreover, the rate of decay is directly influenced by $\gamma$.

For clarity, we summarize the key differences below:

Our Bound (Theorem 3):

$P(E_{D}[L(\theta, z)] \leq \mathcal{L}_{\varepsilon, \gamma}(\theta, D_n) )\geq 1 - e^{-\gamma n} \left(\frac{4}{\delta}\right)^{m(\mathcal{Z}, \delta)}, \quad \text{where} \quad \delta = (\frac{\varepsilon}{diam(Z)+1})^p.$

WDRO’s Bound (Theorem 3.1 in [2]):

$$P(E_{D}[L(\theta, z)] \leq L_{\varepsilon, 0}(\theta, D_n) ) \geq 1 - \delta,$$

where $\varepsilon$ must satisfy:

$$\mathcal{O}\left(\sqrt{\frac{1 + \log(1/\delta)}{n}}\right) \leq \varepsilon \leq \frac{\varepsilon_c}{2} - \mathcal{O}\left(\sqrt{\frac{1 + \log(1/\delta)}{n}}\right),$$

and $\varepsilon_c$ is a constant that depends only on the loss function and the data distribution $D$. The computation of this bound requires the dual form of WDRO.

---

3. Formal theory for Algorithm 1

Our method is grounded in the robust optimization framework, which seeks the most adversarial distribution within a specified ambiguity set defined by Wasserstein distance and KL divergence constraints. While we acknowledge the absence of a formal derivation using a strict dual formulation, we believe this represents an exciting direction for future work. Formalizing the duality theory for our approach would further solidify its theoretical foundation, and we plan to explore this in subsequent research.

---

References

[1] Facco, E., d’Errico, M., Rodriguez, A., & Laio, A. (2017). Estimating the intrinsic dimension of datasets by a minimal neighborhood information. Scientific Reports, 7(1), 12140.

[2] Pope, P., Zhu, C., Abdelkader, A., Goldblum, M., & Goldstein, T. (2021). The Intrinsic Dimension of Images and Its Impact on Learning. International Conference on Learning Representations (ICLR).