Bilevel Optimization for Adversarial Learning Problems: Sharpness, Generation, and Beyond

We thank the reviewers for their constructive feedback and careful evaluation of our work. In this paper, we introduce a bilevel optimization framework that achieves a principled balance between computational efficiency and performance across diverse problem domains. Our contributions include novel theoretical advancements over existing methods while retaining strong practical applicability. The proposed framework is rigorously validated through extensive large-scale experiments, including new GAN benchmarks comparing against nine classical and state-of-the-art approaches, and further demonstrates promising extensibility to broader tasks such as adversarial learning. We respectfully request the reviewers to reconsider their evaluation in light of these substantive contributions.

Compared with SOTA methods:

We present updated GAN experiments, including Stacked MNIST and CIFAR-10, Bi-level optimization results, and evidence of stable convergence, demonstrating our method’s superiority, and propose revisions to clarify these contributions.

(1) GAN Experiments – Stacked MNIST: On Stacked MNIST (1000 modes, 50,000 samples), our method achieves full mode coverage and superior KL divergence:

Our method reduces $D_{KL}$ by 41.7% compared to the baseline, showcasing robust generative performance.

(2) GAN Experiments – CIFAR-10: Using the R3GAN architecture (21M parameters), our method outperforms recent GANs:

Our method achieves a 7.5% FID improvement over R3GAN with stable convergence:

Our method stabilizes by 1800 steps with fewer oscillations, unlike R3GAN’s fluctuations.

(3) Bi-Level Optimization: We compared our framework to recent bilevel methods (HJBio, LwCL, PNGBiO) in the large-scale numerical case:

Our method achieves the lowest FID (0.136) and JS (0.096), converging in fewer steps (225 vs. 274 for PNGBiO) and less time (0.499s vs. 0.527s), a 5.3% FID and 5.4% runtime improvement over PNGBiO.

Our bilevel framework outperforms recent state-of-the-art methods in efficiency (fewer steps, lower runtime) and accuracy (lower FID/JS, full mode coverage), as shown in Stacked MNIST, CIFAR-10. Its stable convergence and theoretical guarantees enhance its applicability. We will revise the manuscript to incorporate these comparisons and clarify contributions.

Ablation studies of hyper-parameter selection:

We present an ablation study on hyperparameter sensitivity from our large-scale numerical experiments, varying key hyperparameters $\alpha$, $\beta$, $\eta$, $\mu_0$, demonstrating the robustness and efficiency of our framework, and propose revisions to clarify its contributions. We will revise the manuscript to add these experiments.

Our ablation study demonstrates the bilevel framework’s robustness and efficiency, with stable convergence across a wide range of hyperparameters, enabling robust adjustments of hyper-parameters in diverse tasks.

Generalization to other types of conditions: We present new experimental results demonstrating our method’s performance in domain shifts and noise inputs.. The domain shift is performed by data augmentation and the noise are performed under diverse levels.

These results demonstrate the proposed scheme which optimizes for sharpness-aware objectives, enhancing generalization under diverse adversarial conditions. We will revise the manuscript to incorporate these findings, clearly addressing the reviewer’s concerns.

Extension to other adversarial learning: Our bilevel framework is a general, theoretically guaranteed, and versatile computational approach for diverse min-max learning problem, where SAM and GANs are the two typical examples instead of specific design. The single-loop algorithm uses first-order gradients, ensuring computational efficiency comparable to or better than other single loop methods (improving 16.8% over BAMM).

Furthermore, our framework can integrates seamlessly with existing methods, as shown in GAN experiments with R3GAN, which are demonstrated in the new adversarial tasks (improving performance on Cifar10 and Stacked MNIST). This compatibility allows performance enhancements across diverse models.

Following with SAM-AT(ICML 24), we perform our algorithm for the adversarial training on the semantic segmentation task. We construct the DeeplabV3 with Resnet50 as backbone under Sandford background dataset. Our method outperforms SGD and AT across all settings.

Different with previous works: Our proposed bilevel framework is not limited to SAM or GANs but extends broadly to general min–max problems, provided that the inner maximization can be rendered tractable, even without requiring convexity. Unlike standard approaches that often sacrifice accuracy for computational efficiency, our framework maintains a principled balance between the two. Its key adaptable components include modular solver design, stochastic approximation strategies, and flexible smoothing mechanisms. This generality enables seamless application to diverse domains, including adversarial robustness and generation.

Theoretical foundations of our framework: The technique in this paper is mainly based on the prior BLPP techniques and a reformulation of the min-max problem. Specifically, we build a stochastic version of the single loop algorithm and its convergence result which shows better numerical efficiency. And for the BLPP reformulation, as we maintain the intrinsic information of classical min-max formulations (see the Example of SAM in Section 3), our method will conduct better effects then classical formulations without introducing too much numerical costs theoretically.

For the reviewer’s concerns:

1. In Section 4, we give more explicit limitations and future generalizations. We put assumptions on the original problem which can be transformed into a bilevel problem with an easily solved lower level particularly convex. Indeed, our methods may extends its applications to more problems with convexitor or reparametrization methods.

2. (9) shows the theoretical influence of the discarding process to the learning accuracy, and the experiments of SAM [1] shows different loss of this discarding. [1] Foret et al., 2021. Sharpness-Aware Minimization for Efficiently Improving Generalization.

3. (15) is the iterations of the algorithm(we move it to the appendix), is indeed a gradient desent iteration of $L^{b_k}$. This is based on the reformulation by the Moreau envelope and the penalty method in (14) for BLPPs. This algorithm updates the upper level variable together with de lower level--single loop—meaning that it do not need to solve the inner problem first and thus ensures the numerical efficiency. Besides, it take the intrinsic Hessian informations of L into considerations and thus balances the learning efficiency and numerical costs to solve the traditional SAM difficulties.

4. We have add more explinations and backgrounds of some parts of this paper. Thanks for the reviewer’s valuable suggestions.

5. Yes, we have mentioned potential techniques to extends our methods in Section 4. Thanks again for the valueable suggestions. Following with SAM-AT(ICML 24), we perform our algorithm for the adversarial training on the semantic segmentation task. We construct the DeeplabV3 with Resnet50 as backbone under Standford background dataset. Our method outperforms SGD and AT across all settings.

We thank the reviewers for their thoughtful feedback and careful evaluation. This work introduces a bilevel optimization framework that not only provides new theoretical insights beyond existing methods but also achieves strong practical performance and scalability across diverse domains. To address potential concerns regarding the theory–practice gap, we rigorously validate our framework through extensive large-scale experiments, including new GAN benchmarks against nine classical and state-of-the-art approaches, and demonstrate its extensibility to broader tasks such as adversarial learning. We believe these contributions establish both the novelty and practical relevance of our approach, and we respectfully request the reviewers to reconsider their evaluation in light of these results.

New experiments of GAN: To validate our method’s effectiveness in high-dimensional and complex settings, we conducted two high-dimensional experiments of GAN, comparing with nine typical GAN methods and will replace the section of GAN with these new results in the revised paper.

Specially, we first conducted comparison with Stacked MNIST, a challenging dataset with 1000 modes. Obviously, Our method achieves full mode coverage (1000 modes) and the lowest $D_{KL}$ (0.09)，outperforming typical schemes (DCGAN, WGAN) and the latest baseline (R3GAN, NeurIPS 24), where our method is only trained with 1k steps.

We tested our method on CIFAR-10 using the same architecture as R3GAN (NeurIPS 2024, 21M parameters) with 50,000 training samples. FID results illustrate the performance of our schemes compared to state-of-the-art GANs.

Convergence analysis over training steps also shows our method’s stability. In summary, our method achieves a 5% FID improvement over R3GAN at 2.4K steps and converges more stably, demonstrating superior performance and robustness in high-dimensional settings.

Furthermore, please also note that the experimental details of 2D mixture about GAN follows with BVFSM (TPAMI 23), where WGAN also cannot displays the desired performance.

Computation efficiency of GAN: We argue that standard GANs rely on simple alternating optimization, lacking robust convergence theory and often requiring engineering tricks (e.g., gradient penalties) to avoid mode collapse. Unlike GANs, our single-loop algorithm is supported by rigorous convergence analysis with first-order computation, achieving faster and more stable convergence. This is validated by a 16.8% efficiency improvement over BAMM (single-loop BLO scheme) and more stable FID reduction on CIFAR-10, compared with the latest GAN scheme R3GAN .

Theoretical Foundations of Our Framework: The technique in this paper is mainly based on the prior BLPP techniques and a reformulation of the min-max problem. Specifically, we build a stocstic version of the single loop algorithm and its convergence result which shows better numerical efficiency. And for the BLPP reformulation, as we maintain the intrinsic informations of classical min-max formulations (see the Example of SAM in Section 3), our method will conduct better effects then classical formulations without introducing too much numerical costs theoretically.

Revisions to Section 4 (Theoretical Part): We have revised and reorganized several paragraphs to improve the clarity and quality of the writing.

Typos: Thanks for pointing out these typos. We will check the paper carefully to revise all typos and mistakes.

Comparison under high-dimensional applications: Firstly, to address the reviewer’s concern about high-dimensional applicability, we conducted new experiments on CIFAR-10 with our method using the same network as R3GAN. Our method achieves a 5% FID improvement over R3GAN, only training with 2.4k steps, demonstrating competitive performance in image generation tasks.

Furthermore, our experiments on SAM (training with diverse typical bakcbones) and large-scale numerical cases also demonstrate the scalability. Comparing existing heuristic and bi-level optimization method, our method realize the consistent improvement. We are committed to revising the manuscript to incorporate these clarifications and results.

Theoretical Benefit of Bilevel Reformulation: The reviewer rightly questions whether robustness stems from the reformulation itself or algorithmic improvements. We emphasize that the advantages:

• Intrinsic Stability: By decoupling the min-max dynamics via Moreau smoothing, our reformulation inherently avoids cyclic gradients (e.g., Figure 4 in Vlatakis et al.), even with vanilla solvers (Appendix C.3 validates this with fixed-step GDA).

• Accuracy Preservation: Unlike heuristic simplifications (e.g., SAM’s "discarding step"), our bilevel framework preserves essential problem structure, enabling theoretical guarantees (Theorem 4.1).

General Guidelines for Reformulation: General Guidelines for Reformulation To clarify applicability, we will add a step-by-step flowchart outlining:

1. Problem Screening: Check if the classical method sacrifies learning accuracy for the numerical cost.
2. Reformulation: Apply the bilevel reformulation, by reparametrization or convexitor if necessary.
3. Algorithm: Apply the single-loop algorithm for the reformulation. This framework already covers SAM and GANs, and we explicitly discuss limitations:

Comparison to Vlatakis et al. (2023): While both works address min-max instability, our approach differs fundamentally:

Our method bypasses cyclic attractors (Vlatakis’ Fig. 4) by bilevel methods.

Future Generalization. For various types of min-max problems, modern methods have been proposed (e.g., [andriushchenko2020understanding, andriushchenko2022towards, li2020towards, zhang2022revisiting, vlatakis2021solving]). For instance, vlatakis2021solving investigates min-max problems of the form$\min_{\theta}\max_{\phi}L(F(\theta),G(\phi))$ in the convex-concave setting. Our method can be applied to some of these problems, particularly when the inner concave subproblem $\max_{\phi}L(F(\theta),G(\phi))$ is tractable, but solving the overall min-max problem requires sacrificing learning accuracy for computational efficiency. Some of these problems suffer from cyclic behavior of level sets (see Figure 4 in vlatakis2021solving). Unlike the approach in vlatakis2021solving, we address this issue through a bilevel reformulation, whose convergence is established in Theorem~3.

In such cases, our bilevel framework provides a compelling alternative, offering a more favorable balance between learning accuracy and computational cost, as illustrated in the SAM and GAN applications.

Furthermore, while not all min-max problems naturally satisfy the two features outlined earlier, many can be transformed into a suitable bilevel form through reparametrization techniques or the use of convexificators. This enables broader applicability of our approach, which can be extended via the following three-step process:

• Problem Screening: Identify whether existing methods trade off learning accuracy for reduced numerical cost.
• Reformulation: Apply a bilevel reformulation, using reparametrization or convexification techniques if needed, to ensure the lower-level problem is tractable.
• Algorithm Deployment: Solve the reformulated problem using the proposed single-loop bilevel algorithm. This process broadens the applicability of our framework beyond SAM-type problems. Investigating such extensions remains an important direction for future research.

Limitations. Beyond the SAM and GAN problems discussed in this paper, our method is applicable to a broader class of min-max problems that possess the following characteristics:

1). Classical methods for min-max problems often trade learning accuracy for numerical efficiency, as the inner-level optimization is typically difficult to solve. In such cases, introducing a bilevel reformulation allows us to better balance learning accuracy and computational cost.

2). The original min-max problem can be reformulated as a bilevel problem in which the lower-level problem is easily solvable, without requiring any convexity assumptions on the objective function $L$. In such settings, the bilevel reformulation does not introduce significant additional complexity.

Given these two features, the bilevel approach offers distinct advantages. On the one hand, it preserves more intrinsic and essential information from the original problem than standard simplifications (e.g., the “discarding step” used in SAM), thereby enhancing learning accuracy. On the other hand, when the lower-level problem is easily solvable, efficient bilevel optimization algorithms can be employed, resulting in a computational cost that remains manageable.

Nevertheless, in high-dimensional learning tasks, our method may encounter challenges in maintaining an acceptable computational cost while ensuring learning accuracy. This difficulty, however, is inherent to high-dimensional settings: higher-dimensional data typically carry more information, which inevitably leads to increased computational demands. In such cases, the trade-off between accuracy and efficiency becomes more pronounced, further emphasizing the value of a principled framework for balancing the two.

Table 1 Analysis: Table 1 presents three key metrics for analyzing loss landscape geometry. The ascent-direction loss, corresponding to the minimum eigenvalue (λₘᵢₙ) of the Hessian matrix H_L(ω), captures the local curvature along the most favorable ascent direction. The average-direction loss, quantified by the trace of the Hessian (Tr(H_L(ω))), characterizes the overall sharpness of the loss surface. The table clearly demonstrates that SAM's effectiveness in sharpness minimization stems from its utilization of second-order information through the Hessian matrix. Notably, the largest eigenvalue (λ₁(H_L(ω))) serves as a direct measure of loss function sharpness, thereby elucidating SAM's mechanism for improving generalization via sharpness reduction. For detailed mathematical derivations of these relationships, we refer readers to Theorems E.1-E.3 in [Wen et al., 2023].

Moreau Envelope: To address the nonsmooth nature of the value function, we employ the Moreau envelope technique to construct a smooth approximation. This approach not only enhances mathematical tractability but also facilitates algorithmic development. Geometrically, the Moreau envelope generates a family of smooth surfaces that progressively approximate the original value function's graph. We will revise this part for the clear description.