acceptodds
Under review as a conference paper at ICLR 2027

Sharpness-Aware Bilevel and Minimax Optimization

Abstract

Bilevel and minimax optimization are foundational frameworks of nested optimization widely used in hyperparameter tuning, adversarial training, meta-learning, and reinforcement learning. Despite their versatility, these methods frequently suffer from poor generalization due to sharp minima and training instability, especially in overparameterized regimes. We introduce a unified first–order sharpness-aware optimization framework comprising Sharpness-Aware Bilevel Optimization (SABO) and Sharpness-Aware Minimax Optimization (SAMO). SABO improves generalization by jointly minimizing inner and outer objectives and their sharpness via a penalty-based reformulation that avoids costly implicit gradient computations. SAMO also yields a simplified algorithm tailored for sharpness-aware minimax settings. We establish theoretical convergence guarantees under the Polyak–ojasiewicz condition and derive generalization bounds. Experiments on synthetic and real tasks show that SABO and SAMO consistently enhance generalization over standard baselines.

Primary area:
optimization
Keywords:
Bilevel and minimax optimization, Sharpness-Aware Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_kxcUOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
1
Read review
Paper summary

This paper considers the sharpness-aware bilevel optimization (SABO) and minimax optimization (SAMO) problems by combining the notions in sharpness-aware minimization (SAM) with bilevel and minimax contexts. It first formulates the SABO problem, reformulates it using the penalty function method, and then designs an algorithm with some first-order approximation techniques to solve it. Under some assumptions, the paper provides some theoretical analysis. The same story is stated for SAMO as well. Finally, some numerical experiments verify the proposed algorithms.

Critical strengths

This paper is well-motivated. The SABO and SAMO are interesting topics.

Critical weaknesses

My main concern is that the established theoretical results seem not to be aligned with the original SABO problem. Specifically, Equation 8 is an equivalent reformulation of the original SABO problem, but Equation 12, which fixes γ\gamma, is not necessarily equivalent to the previous problem and is not even its dual formulation. Moreover, Theorem 3.3 cannot close this gap: (1) in Theorems C.8–C.9, the gap does not automatically vanish; and (2) the limit point may not be either a local or a global solution, but only a stationary point, which then implies nothing about the original SABO problem.

The PL condition is of course weaker than strong convexity. However, in the bilevel optimization literature, it plays a similar role in the analysis and is still quite restrictive.

The experiments are limited to small datasets and impractical settings. It would be better to show some LLM-based numerical results to verify the scalability of the proposed method. Also, there are almost no baseline methods.

Questions for authors

In Line 74, the authors claim that “Standard BO frameworks, such as (1), are highly susceptible to converging toward sharp local minima”. Is there any evidence?

Can authors provide any insights on the selection of TkT_k?

Minor mistake in Line 229: Assumption 2 is missing.

4 comments
AuthorsOpenReview ↗

Response to Reviewer kxcU - Part I

We thank the reviewer for the clear assessment. Blue text in the revised PDF marks the changes. Under each answer we quote the text that we added; equation, table, line and appendix numbers refer to the revised PDF.

Weakness 1 (penalized problem vs. original SABO problem): My main concern is that the established theoretical results seem not to be aligned with the original SABO problem. … the limit point may not be either a local or a global solution, but only a stationary point, which then implies nothing about the original SABO problem.

Response: We agree that Eq. (8) is an equivalent reformulation of the original SABO problem, whereas Eq. (12), obtained by introducing a fixed penalty parameter γ\gamma, is a penalized formulation rather than an equivalent reformulation or a dual formulation of Eq. (8).

This distinction is also recognized in the penalty-based bilevel optimization literature. For instance, Shen and Chen (ICML 2023) explicitly study the relationship between an original bilevel problem and its penalized reformulation. Their results (Theorems 1 and 2) establish that, under suitable assumptions on the penalty function and the problem structure, solutions of the penalized problem can recover approximate solutions of the original bilevel problem. Importantly, these results require additional conditions and do not establish unconditional equivalence between the two formulations.

Following this distinction, we clarify that Eq. (12) is the penalized problem considered by our algorithm, and our convergence analysis establishes stationarity guarantees for its penalized objective. We will revise the manuscript to explicitly distinguish the original SABO problem, its equivalent reformulation in Eq. (8), and the penalized formulation in Eq. (12), and to clarify the scope of our theoretical guarantees.

We agree that convergence to a stationary point of the penalized problem (12) does not, in general, imply that the limit point is a local or global minimax point (MMP). Consequently, Theorem 3.3 alone does not guarantee that the limit point of Algorithm 1 solves the original SABO problem.

We would like to clarify, however, that the connection between the penalized problem and the original SABO problem is established independently in Theorems C.8 and C.9. Specifically, Theorem C.8 establishes that every global MMP of the original SABO problem is an approximate global MMP of the penalized problem and, conversely, that an approximate global MMP of the penalized problem solves the relaxed problem (30), under appropriate conditions on the penalty parameter and the uniqueness condition of Lemma E.1. Furthermore, Theorem C.9 establishes that a local MMP of the penalized problem is also a local MMP of problem (30), provided that the penalty parameter is sufficiently large (under the same condition).

(this answer continues in the next part)


AuthorsOpenReview ↗

Response to Reviewer kxcU - Part II

(continuation of the previous answer)

We acknowledge that these results do not automatically apply to every stationary point generated by Algorithm 1, since the convergence analysis does not establish local or global minimax optimality of its limit point. We have therefore clarified the distinction between the stationarity guarantee of Theorem 3.3 and the conditional solution-transfer guarantees of Theorems C.8 and C.9. In particular, we do not claim that convergence to an arbitrary stationary point of problem (12) necessarily yields a solution to the original SABO problem.

Revisions made to the paper.

Section 3, Theorem 3.3 (lines 293–297), revised text:

[…] Moreover, under the uniqueness condition of Lemma E.1 (or strong convexity of g(x,⋅)g(\mathbf{x},\cdot)), if (x∗,y∗)(\mathbf{x}^{\ast},\mathbf{y}^{\ast}) is a local (respectively, global) solution to problem (12), then it is also a local (respectively, global) solution to problem (30) for some ζγ≤ϱ\zeta_{\gamma}\leq \varrho, where ϱ\varrho is defined in Theorem 3.1.

Section 3, after Theorem 3.3 (lines 299–304), new text:

[…] For finite γ\gamma this link is approximate, not exact, and stationarity alone does not imply a local or global solution. The guarantees use only the size of the perturbations, so they show that SABO keeps the convergence of the penalty method; they do not by themselves show that SABO finds flatter solutions, which the generalization bounds and the experiments address.


Weakness 2 (PL condition): The PL condition is of course weaker than strong convexity. However, in the bilevel optimization literature, it plays a similar role in the analysis and is still quite restrictive.

Response: We agree that, although the PL condition is weaker than strong convexity, it remains a restrictive assumption in bilevel optimization. Nevertheless, it offers an important degree of flexibility, as it does not require the inner-level objective to be convex and can accommodate certain nonconvex functions.

In our analysis, the PL condition plays a key role in establishing the convergence of the inner optimization iterations and controlling the error arising from the inexact solution of the inner problem. In particular, it allows us to establish a geometric convergence rate for the inner gradient descent iterations without imposing strong convexity. We acknowledge that extending our theoretical results beyond the PL setting is an interesting direction for future research.


AuthorsOpenReview ↗

Response to Reviewer kxcU- Part III

Weakness 3 (scale and baselines): The experiments are limited to small datasets and impractical settings. It would be better to show some LLM-based numerical results to verify the scalability of the proposed method. Also, there are almost no baseline methods.

Response: We thank the reviewer for this suggestion.

Language model. We added data hypercleaning with a pretrained language model (newly added Appendix N, Table 17). The model is Qwen2.5-0.5B (494M parameters, frozen); the lower-level variable is a LoRA adapter of rank 88 with a linear head (1.471.47M parameters), and the upper level holds one weight per training text (20,00020{,}000 variables). The data set is AG News with 4040\\% label noise, and we report three seeds. SABO reaches 91.56±0.1691.56\pm0.16 test accuracy, against 90.31±0.2390.31\pm0.23 for BO and 89.99±0.4089.99\pm0.40 for ERM. It beats BO on every seed and raises the F1 of the cleaner from 84.284.2 to 88.388.3. It costs 1.9×1.9\times BO per iteration, but BO given the same time (66 epochs) reaches only 90.290.2. Memory is unchanged (2.032.03 against 2.022.02 GB), because the proxy and the perturbations live in the adapter. At 2020\\% noise the accuracy gain is small (+0.3+0.3 points), but the cleaner is much better (F1 71.971.9 against 59.759.7). This is one model and one data set, and Appendix N states this limitation.

Baselines. BO and MO are now tuned with the same procedure as SABO and SAMO, with comparable budgets, on a separate seed (Tables 2 and 6). For hypercleaning we compare with tuned BO, BO with the same compute, ERM, SAM without reweighting, and each perturbation alone (Table 3), and, on a controlled problem, with nested BO and nested SAM that use exact hypergradients (Appendix M.1). Against tuned BO, SABO wins all 3636 comparisons of Table 1. Appendix A.2 also discusses the closest sharpness-aware methods for nested problems (Sharp-MAML, SDARTS, SAPA, AWP, SDAT).

Revisions made to the paper. Appendix N (new); Section 5.2 (lines 471–479); Tables 2–4; Appendix M.1.


Question 1 (evidence for sharp local minima, line 74): In Line 74, the authors claim that "Standard BO frameworks, such as (1), are highly susceptible to converging toward sharp local minima". Is there any evidence?

Response: Our statement was intended to highlight a potential limitation of standard bilevel optimization (BO) frameworks, rather than to suggest that all standard BO methods necessarily converge to sharp local minima.

In standard BO formulations, the optimization objective is typically based on the original loss functions, without explicitly accounting for the local sensitivity of the objective to perturbations in the upper- and lower-level variables. Consequently, such methods do not explicitly discourage solutions that exhibit high local sensitivity or sharpness. This motivates incorporating sharpness-aware optimization into the bilevel framework.

We agree that the original wording was too strong and could be interpreted as claiming a guaranteed convergence behavior. We have therefore revised the statement to clarify this point and avoid overstating the claim.

Revisions made to the paper.

Section 2 (line 78), revised text:

Standard BO methods for (1) contain no mechanism that favors flat solutions. In differentiable architecture search, a bilevel problem, the curvature of the validation loss grows during search and correlates with test error (Zela et al., 2020), and on the controlled instances of Appendix K BO converges to the sharp minimum.


AuthorsOpenReview ↗

Response to Reviewer kxcU- Part IV

Question 2 (choice of TkT_k): Can authors provide any insights on the selection of TkT_k?

Response: The choice of TkT_k is motivated by the linear convergence rate of the inner gradient descent iterations. Under our assumptions, the inner iterations exhibit a geometric contraction with factor cβ=1−β/(2μ)∈(0,1)c_\beta=1-\beta/(2\mu)\in(0,1). Consequently, the inner optimization error decreases proportionally to cβTkc_\beta^{T_k}.

The lower bound on TkT_k is chosen to ensure that this error is sufficiently small to control the approximation error arising from the inexact solution of the inner problem in the convergence analysis. In particular, the condition in Theorem 3.1 guarantees that

cβTk≤min⁡{1288μ2ℓg,12,1(2αk)2}.c_\beta^{T_k}\leq\min\Big\lbrace \frac{1}{288\mu^2\ell_{g,1}^2},\frac{1}{(2\alpha k)^2}\Big\rbrace .

The first term provides a uniform accuracy requirement, while the second ensures a progressively tighter inner solution accuracy as the outer iterations proceed. Importantly, this choice does not require solving the inner problem to exact optimality. Moreover, since the contraction factor is strictly smaller than one, the required number of inner iterations grows only logarithmically with kk, making the resulting inner-loop complexity relatively mild. We will add this explanation to the revised manuscript to clarify the rationale behind the choice of TkT_k.


Minor (line 229): Minor mistake in Line 229: Assumption 2 is missing.

Response: Fixed: Theorem 3.1 now lists Assumptions 2.1, 2.2, 2.3 and 2.4 (line 240).

Reviewer_F3G6OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Sharpness-Aware Bilevel Optimization (SABO) and Sharpness-Aware Minimax Optimization (SAMO) to improve generalization in bilevel and minimax optimization. The main idea is to introduce sharpness-aware perturbations into both inner and outer optimization. SABO uses a penalty-based reformulation and first-order approximations to avoid expensive implicit differentiation and second-order computations. SAMO extends the sharpness-aware approach to minimax optimization. The paper provides convergence and generalization analyses and evaluates the proposed methods on synthetic problems, data hypercleaning, and GAN training.

Critical strengths

The paper studies sharpness-aware optimization in bilevel and minimax settings, which are relevant to several machine learning applications.

The proposed methods use first-order approximations to reduce the computational cost of nested sharpness-aware optimization.

The paper provides theoretical analyses of convergence and generalization under specific assumptions.

The experiments show improvements over standard BO and MO baselines, particularly in data hypercleaning with high label noise. The synthetic experiments also investigate the effects of inner and outer perturbation radii.

Critical weaknesses
  1. Introducing sharpness-aware perturbations into both inner and outer objectives is a straightforward extension. Related ideas have been explored in prior work. Sharp-MAML (ICML 2022) applies SAM to bilevel meta-learning and provides efficient algorithms with convergence and generalization analyses. BiSAM (ICML 2024) [a] reformulates SAM as bilevel optimization to improve perturbation quality. XSAM (ICLR 2026) [b] examines the limitations of first-order SAM approximations and proposes a more faithful implementation. Although their settings differ from SABO, these studies are closely related. Moreover, combining adversarial training with SAM follows a similar multi-level perturbation strategy: first generating adversarial examples by maximizing the input loss, then applying SAM perturbations to model parameters. Study [c] discusses the relationship between these two types of optimization. The authors should clarify the novelty of SABO relative to these studies and include relevant baselines.

  2. An important baseline is missing for evaluating the effectiveness of SABO. A direct approach to Eq. (2) is to fix the outer variable xx, sufficiently optimize the inner SAM objective to obtain yη∗(x)y_\eta^{*}(x), and then optimize the outer sharpness-aware objective using accurate hypergradients. SABO approximates this procedure but is only compared with standard BO. The authors should compare SABO with such a nested-SAM solver in terms of objective value, inner optimality gap, test performance, gradient computation cost, and runtime to demonstrate its efficiency–accuracy trade-off.

  3. The accuracy and accumulated errors of the multiple approximations are insufficiently evaluated. Eq. (9) approximates the inner worst-case perturbation, Eq. (10) approximates the inner optimum using finite SAM steps, and Eq. (14) approximates the outer perturbation. Eq. (15) then combines these approximations to construct the update direction. The paper should quantify the adversarial approximation error, inner optimization error, and outer gradient estimation error, and examine their dependence on TkT_k, ρ\rho, η\eta, and γ\gamma. More inner steps do not necessarily improve all these approximations.

  4. The treatment of the inner value function in Eqs. (6)–(8) needs clarification. Eq. (4) defines ν∗(x,y)∈arg⁡max⁡∥ν∥≤ηg(x,y+ν)\nu^{\ast}(x,y)\in\arg\max_{\|\nu\|\leq\eta}g(x,y+\nu), where the optimal perturbation depends on yy. Eq. (6) is equivalent to g∗(x)=min⁡ymax⁡∥ν∥≤ηg(x,y+ν)g^{\ast}(x)=\min_{y}\max_{\|\nu\|\leq\eta}g(x,y+\nu) only when this dependence is preserved. However, Appendix E.1 appears to treat ν∗\nu^{\ast} as fixed when minimizing over yy, and then equates the result with the robust inner minimum. These two operations are generally not equivalent. The authors should clarify whether ν∗\nu^{\ast} is recomputed for each candidate inner variable and justify the equivalence used in the proof of Lemma C.5.

  5. The gradient approximation in Eq. (15a) uses the same ν~k\tilde{\nu}_k for both ∇xg(xk,yk+ν~k)\nabla_x g(x_k,y_k+\tilde{\nu}_k) and ∇xg(xk,y~k+ν~k)\nabla_x g(x_k,\tilde{y}_k+\tilde{\nu}_k), although the optimal adversarial perturbations at yky_k and y~k\tilde{y}_k are generally different. Moreover, Eq. (10c) obtains ν~k\tilde{\nu}_k before the final inner update rather than recomputing it at y~k\tilde{y}_k. The authors should justify this approximation, provide a gradient estimation error bound, and compare shared versus recomputed perturbations.

  6. The real-world experiments lack sufficient ablations. Although the synthetic experiments examine different combinations of ρ\rho and η\eta, Data Hypercleaning mainly compares SABO with standard BO. Inner-SAM-only, Outer-SAM-only, Inner+Outer SAM, and penalty-only baselines are missing. The improvements may result from sharpness regularization, penalty strength, or altered optimization dynamics. The authors should evaluate the individual contributions of ρ\rho, η\eta, and γ\gamma under matched computational budgets.

  7. The paper relies heavily on mathematical derivations and provides limited methodological motivation and intuition. The authors should better explain the proposed approximations and their underlying mechanisms in the main text, particularly their advantages over more direct optimization approaches.

[a] Improving SAM Requires Rethinking its Optimization Formulation

[b] Revisiting Sharpness-Aware Minimization: A More Faithful and Effective Implementation

[c] On the Duality Between Sharpness-Aware Minimization and Adversarial Training

Questions for authors

Please check the weakness.

7 comments
AuthorsOpenReview ↗

Response to Reviewer F3G6- Part I

We thank the reviewer for the detailed comments and the pointers to related work. Blue text in the revised PDF marks the changes. Under each answer we quote the text that we added; equation, table, line and appendix numbers refer to the revised PDF.

Weakness 1 (novelty relative to Sharp-MAML, BiSAM, XSAM and SAM with adversarial training): Introducing sharpness-aware perturbations into both inner and outer objectives is a straightforward extension. … The authors should clarify the novelty of SABO relative to these studies and include relevant baselines.

Response: We thank the reviewer for these references; Appendix A.2 now discusses them in a new paragraph. Sharp-MAML is the closest prior work, and we do not claim to be the first to perturb both levels of a bilevel problem. SABO differs from it in scope, algorithm and analysis.

  • Sharp-MAML replaces the lower level by one gradient step and differentiates through it with Hessian-vector products. SABO treats a general bilevel problem whose inner objective satisfies the PL condition, runs several inner SAM steps, and replaces the hypergradient by a value-function penalty, so it uses gradients only.
  • Sharp-MAML perturbs the upper level only through the meta-parameter. In SABO the outer objective is also perturbed in the follower, through ν\boldsymbol{\nu} in f(x+ϵ,y+ν)f(\mathbf{x}+\boldsymbol{\epsilon},\mathbf{y}+\boldsymbol{\nu}).
  • Sharp-MAML proves a rate for the unperturbed MAML objective. Our analysis covers the penalized sharpness-aware problem under the PL condition, and our PAC-Bayes bounds cover both levels and the minimax case, which Sharp-MAML does not treat.

BiSAM and XSAM are single-level methods that change how the perturbation of one loss is computed. This is orthogonal to our contribution: either could replace the normalized-gradient perturbations of SABO and SAMO at any level (BiSAM only where that level is a classification loss). The study of the duality between SAM and adversarial training does not solve a nested problem. AWP, which combines weight and input perturbations, is an instance of (17) with ν=0\boldsymbol{\nu}=\mathbf{0} whose maximizing variable is a set of per-sample input perturbations. SAMO targets games in which the maximizing variable is a second learned model that satisfies a PL condition, and it comes with a convergence analysis.

Baselines. Since SAM is known to be robust to label noise, we added SAM without any reweighting as a hypercleaning baseline: it reaches 87.7±1.187.7\pm1.1 test accuracy against 91.1±0.991.1\pm0.9 for SABO (newly added Table 3). We also added nested BO and nested SAM with exact hypergradients (our answer to Weakness 2).

Revisions made to the paper. Appendix A.2: new paragraphs "Sharpness in Nested Problems" and "Relation to Sharp-MAML, BiSAM, XSAM, and SAM–Adversarial Training Duality"; Table 3 (SAM-ERM row).


AuthorsOpenReview ↗

Response to Reviewer F3G6- Part II

Weakness 2 (nested-SAM baseline): An important baseline is missing for evaluating the effectiveness of SABO. … to demonstrate its efficiency–accuracy trade-off.

Response: We thank the reviewer for this suggestion and added the baseline (newly added Appendix M.1, Tables 10–11). We ran it on the controlled hypercleaning problem of Appendix L (logistic regression with 2020 parameters, one weight per training point, 3030 clean validation points), where the robust inner solution can be computed exactly; results are over 5050 seeds. Nested SAM uses the exact robust inner solution yη∗(x)\mathbf{y}^*_\eta(\mathbf{x}), the exact outer objective and SAM steps on x\mathbf{x}. Nested BO uses the exact inner solution and the exact hypergradient. Both were tuned on separate seeds, including early stopping and, for nested SAM, the radii.

  • Objective value. The nested methods solve their problems accurately. Without early stopping, nested BO reaches the lowest bilevel objective of all methods (0.1520.152–0.1750.175 over the four noise levels, against 0.2270.227–0.2470.247 for tuned BO and 0.2540.254–0.2660.266 for tuned SABO).
  • Inner optimality gap. Zero for nested BO, and a robust gap below 0.6⋅10−30.6\cdot10^{-3} for nested SAM. The penalty methods keep an inner gap of 4.9⋅10−34.9\cdot10^{-3} (tuned BO) to 11.7⋅10−311.7\cdot10^{-3} (SABO) at 40%40\% corruption, because y\mathbf{y} also descends the validation loss.
  • Test performance. The nested methods are the least accurate on test data: against tuned BO, tuned nested SAM loses 0.130.13, 0.920.92, 1.251.25 and 1.391.39 points at 2020–50%50\% corruption, and tuning chose ρ=0\rho=0 for nested SAM at every level. With 3030 validation points, minimizing the validation loss exactly overfits it. SABO with radii selected on tuning seeds is the most accurate method at 3030–50%50\% (+0.75+0.75 to +1.20+1.20 points over tuned BO) and ties tuned BO at 20%20\%.
  • Gradient computation cost. Nested SAM needs up to 152,288152{,}288 gradient and 28,12428{,}124 Hessian passes per run, against 6,7206{,}720 gradient passes and no Hessians for SABO.
  • Runtime (at 40%40\% corruption). 238238–243243 ms per run for SABO against 1,0711{,}071–1,5961{,}596 ms for nested SAM. Early-stopped nested BO is the fastest (7474 ms), because the problem is small and Hessians are cheap; this problem cannot show the advantage of the first-order design when Hessians cannot be formed.

AuthorsOpenReview ↗

Response to Reviewer F3G6- Part III

Weakness 3 (accuracy of the approximations): The accuracy and accumulated errors of the multiple approximations are insufficiently evaluated. … More inner steps do not necessarily improve all these approximations.

Response:

  • Adversarial approximation error. We have added two new lemmas (Lemmas B.3 and B.4 in Appendix B.1) to quantify the adversarial approximation errors in Eqs. (9) and (14), respectively. Specifically, under the corresponding smoothness assumptions, we establish that

g(xk,yk+νk∗)−g(xk,yk+ν~k)≤ℓg,1η2andf(xk+ϵk∗,yk+νk∗)−f(xk+ϵ^k,yk+ν^k)≤ℓf,1(ρ2+η2).g(\mathbf{x}_k,\mathbf{y}_k+\boldsymbol{\nu}_k^{\ast})-g(\mathbf{x}_k,\mathbf{y}_k+\tilde{\boldsymbol{\nu}}_k)\leq \ell_{g,1}\eta^2 \quad\text{and}\quad f(\mathbf{x}_k+\boldsymbol{\epsilon}_k^{\ast},\mathbf{y}_k+\boldsymbol{\nu}_k^{\ast})-f(\mathbf{x}_k+\hat{\boldsymbol{\epsilon}}_k,\mathbf{y}_k+\hat{\boldsymbol{\nu}}_k)\leq \ell_{f,1}(\rho^2+\eta^2).

These results show that the adversarial approximation errors are of orders O(η2)\mathcal{O}(\eta^2) and O(ρ2+η2)\mathcal{O}(\rho^2+\eta^2), respectively, and are independent of the number of inner iterations TkT_k and the penalty parameter γ\gamma.

  • Inner optimization error. We have clarified the effect of finite inner optimization in Eq. (10) through Lemma G.2. This bound reveals two distinct contributions to the inner optimization error: a transient component that decreases geometrically with TkT_k, and a residual component caused by the adversarial perturbation, which does not vanish merely by increasing the number of inner iterations.
  • Outer gradient estimation error. To quantify the accumulated effect of these approximations on the update direction in Eq. (16), we have provided an explicit bound on the gradient estimation error in Eq. (80):

∥∇Lγ(wk)−∇^Lγ,k∥2≤3ℓf,12(ρ2+η2)+9γ2ℓg,12η2+6γ2ℓg,12∥y~k∗−y~k∥2.\Vert \nabla \mathcal{L}_{\gamma}(\mathbf{w}_k)-\widehat{\nabla} \mathcal{L}_{\gamma,k} \Vert ^2\leq 3\ell_{f,1}^2(\rho^2+\eta^2)+9\gamma^2\ell_{g,1}^2\eta^2+6\gamma^2\ell_{g,1}^2\Vert \tilde{\mathbf{y}}_k^{\ast}-\tilde{\mathbf{y}}_k\Vert ^2 .

Combining this inequality with Lemma G.2 explicitly characterizes the dependence of the gradient estimation error on Tk,ρ,η,γT_k,\rho,\eta,\gamma. Moreover, by incorporating these error bounds into the descent analysis, we derive the cumulative stationarity bound in Eq. (83). This result quantifies the accumulated effect of the approximation errors over the entire optimization process.

Importantly, our analysis clarifies that increasing TkT_k only reduces the geometrically decaying component of the inner optimization error. It does not improve the adversarial approximation errors in Eqs. (9) and (14), nor does it eliminate the residual error induced by the perturbation radius η\eta. Thus, increasing the number of inner iterations does not necessarily improve all sources of approximation error, as correctly pointed out by the reviewer.

(this answer continues in the next part)


Reviewer_57jkOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
1
Read review
Paper summary

This paper extends sharpness-aware optimization to bilevel and minimax problems. For bilevel optimization, SABO adds perturbations to the outer objective and the inner problem, and uses a value-function penalty to avoid implicit differentiation and Hessian computations. For minimax optimization, SAMO combines normalized gradient perturbations with alternating descent and ascent. The paper provides convergence bounds under PL conditions and PAC-Bayesian generalization bounds. Experiments cover synthetic landscapes, data hypercleaning, and GAN training. The reported results suggest that perturbations can improve data cleaning under substantial label noise and stabilize some GAN configurations.

Critical strengths

S1. Extending sharpness-aware training to coupled optimization problems is a worthwhile direction. The penalty approach gives a concrete way to combine inner and outer perturbations using first-order computations, and the paper explains how the two radii enter the updates.

S2. The synthetic experiments go beyond showing a single favorable trajectory. Appendices K and L examine settings in which one radius, both radii, or either radius is useful, as well as sensitivity to initialization and perturbation size. These experiments help explain when the two perturbations can complement one another.

S3. The real-task results include meaningful improvements at high label-noise rates and examples of avoiding GAN collapse. The controlled hypercleaning experiments also report results over 15 seeds.

Critical weaknesses

W1. The minimax formulation does not clearly support the claimed role of both perturbations or the claimed smoothness. In Equation (16), the maximization variable yy ranges over all of Rd2\mathbb{R}^{d_2}. Therefore, adding a bounded perturbation ν\nu does not change the set of points available to the maximizer:

=\max_{z\in\mathbb{R}^{d_2}} f(x+\epsilon,z).$$ Thus, $\eta$ can affect the finite-step algorithm, but it does not change the exact objective as written. Also, the PL condition in $y$ does not by itself make the additional maximum over $\epsilon$ smooth. For example, $f(x,y)=x^2-y^2$ satisfies the smoothness, inner PL, and lower-bounded primal-objective assumptions, but Equation (17) gives $h(x)=(|x|+\rho)^2$, which is not differentiable at zero for $\rho>0$. Lemma C.2 establishes smoothness of $F(x)=\max_y f(x,y)$, not necessarily of $h$. The authors should clarify the distinct roles of $F$ and $h$, revise the gradient claim for $h$, and explain whether $\eta$ is intended as an algorithmic device rather than a separate robustness term in the exact minimax problem. **W2.** Theorem 3.3 claims an exact connection to the bilevel problem, but the appendix establishes an approximate connection. The theorem states that a local or global solution of the finite-penalty problem (12) is also a solution of the original constrained problem (5). However, Theorems C.8 and C.9 connect the penalized problem to the relaxed problem (29), which allows a nonzero inner optimality gap $p(x,y)\leq\zeta_\gamma$. Making this gap small is different from making it exactly zero. The proof in Appendix G.2 invokes these approximate results without showing why the gap vanishes for the chosen finite $\gamma$. The authors should either provide an additional condition that ensures exact feasibility or revise Theorem 3.3 to state an approximate result with an explicit feasibility error. The discussion should also distinguish convergence to a stationary point from obtaining a local or global solution. **W3.** Some real-task experiments appear to use problems or updates different from those analyzed. In standard data hypercleaning, $x$ contains training-sample weights, while the outer validation loss depends directly only on the classifier parameters $y$. In that case, the partial gradient $\nabla_x f(x,y)$ in Equation (14) is zero, making its normalized perturbation undefined. Since the penalty in Equation (11) is evaluated at unperturbed $x$, it is also unclear how the outer radius $\rho$ affects this implementation. The authors should write out the actual validation loss and perturbation update used in the experiments, including any dependence on $x$ that is missing from the description. In addition, $\ell_2$ regularization does not by itself make the lower-level training of a full ResNet or WideResNet strongly convex; please clarify which parameters are trained and qualify the strong-convexity claim in Section 5.2. For GANs, Equation (24) applies separate worst-case perturbations to two different losses, using a non-saturating generator objective. This differs from the shared zero-sum objective and updates in Section 4. The paper acknowledges the special case $L_G=-L_D$, but the reported experiment does not use that case. Please provide the experimental update equations or pseudocode and state which theoretical conclusions apply to this game. A small experiment following Algorithm 2 directly would help connect the minimax theory to the empirical results. **W4.** The generalization discussion claims more than the bounds establish. Appendix D.1 states that increasing the radii tightens the bound and that SABO has provably superior generalization to standard bilevel methods. However, increasing the radii decreases the displayed complexity term while potentially increasing the worst-case empirical loss in the same bound. A smaller complexity term alone does not show that the full bound decreases, and a bound becoming vacuous at zero radius does not establish that a baseline generalizes worse. The authors should describe this trade-off and remove or justify the claim of proven superiority. **W5.** The current experiments on real-world tasks primarily demonstrate that the complete method outperforms the selected baselines. However, it remains unclear whether both perturbations contribute to the results, and whether the observed performance gains are stable. Please clarify the specific implementations of BO and MO, and compare the results—for the data cleaning and GAN tasks—across three scenarios: no perturbations, a single perturbation, and both perturbations applied. Additionally, please report the results from multiple runs along with the associated computational costs, so that the stability of the improvements and the costs incurred to achieve them can be assessed.
Questions for authors
  1. Can the authors clarify the minimax objective after absorbing ν\nu into the unconstrained variable yy? Please explain what the inner perturbation changes beyond the finite-step optimization procedure and correct the smoothness claim for hh in light of the example in W1.

  2. Does Theorem 3.3 guarantee exact inner feasibility at finite γ\gamma, or only the approximate feasibility established in Appendix C.3? Please state the resulting bound on p(x,y)p(x,y) and distinguish this from stationarity of the penalized objective.

  3. What is the explicit outer loss in the data hypercleaning implementation, and how is the perturbation in xx computed when the validation loss has no direct dependence on the sample weights? Are the neural networks fully trained, or is only a convex classifier trained on fixed features?

  4. Please provide pseudocode for the GAN experiment and explain how it differs from Algorithm 2. Generator-only, discriminator-only, and joint perturbation results would help determine whether the gains require both players to use sharpness-aware updates.

  5. Please qualify the generalization claims by considering both the worst-case empirical-loss term and the complexity term.

  6. What algorithms do BO and MO denote in each experiment? Please report how the radii, penalty schedule, and learning rates were selected, and whether the baselines received comparable tuning. For data hypercleaning, please distinguish the clean data used in the outer objective from any data used to select hyperparameters and checkpoints.

  7. Please report the number of independent runs and per-run or mean-and-standard-deviation results for Table 1 and Figure 3. For the GAN collapse cases, how often does each method collapse across runs? The FID/IS evaluation should also specify the number of generated samples and the preprocessing used for FashionMNIST.

  8. Corollary 3.2 reports O(ε−2)O(\varepsilon^{-2}) gradient complexity, but the number of inner steps grows logarithmically with the outer iteration. Please distinguish outer-iteration complexity from the total number of gradient evaluations and state any suppressed logarithmic factors. Also, the exact rate uses radii that shrink with KK, whereas the experiments use fixed radii; please make the corresponding nonzero error floor explicit when summarizing convergence.

  9. Appendix L explains that the synthetic study uses a more accurate outer-ball search and that the single normalized-gradient step can behave differently. Please identify which solver is used in Figure 1 and show its comparison with Algorithm 1 in the same setting. This would make clear which conclusions demonstrate the implemented first-order algorithm and which concern a more accurately solved perturbation problem.

  10. A few implementation and presentation details need correction: specify how zero gradient norms are handled in Equations (9), (14), and (18); reconcile the statement that Equation (14) incorporates the penalty with its dependence only on ff; include Assumption 2.2 in Theorem 3.1 if it is required; and reconcile the zero minimum learning rate in Appendix J.1 with the 10−310^{-3} value in the Table 1 caption.

7 comments
AuthorsOpenReview ↗

Response to Reviewer 57jk - Part I

We thank the reviewer for the careful reading and the precise questions. Blue text in the revised PDF marks the changes. Under each answer we quote the text that we added; equation, table, line and appendix numbers refer to the revised PDF.

Weakness 1 (role of the two perturbations; smoothness of hh): The minimax formulation does not clearly support the claimed role of both perturbations or the claimed smoothness. … explain whether η\eta is intended as an algorithmic device rather than a separate robustness term in the exact minimax problem.

Question 1 (minimax objective after absorbing ν\nu): Can the authors clarify the minimax objective after absorbing ν\nu into the unconstrained variable yy? … correct the smoothness claim for hh in light of the example in W1.

Response:

  • Role of η\eta. We acknowledge that η\eta does not alter the exact minimax objective in Eq. (17). Its role in our algorithm is related to the perturbation of the current inner iterate during finite-step optimization, rather than introducing an additional robustness term in the exact objective. Therefore, ν\boldsymbol{\nu} affects the gradient evaluations and the optimization trajectory, even though it does not introduce an independent robustness term into the exact objective. We have clarified in Section 4 that its role is algorithmic rather than an additional perturbation of the exact minimax problem, and revised the corresponding discussion.
  • Roles of FF and hh. We clarify that FF and hh serve different purposes in our presentation. Specifically, F(x)=max⁡yf(x,y)F(\mathbf{x})=\max_{\mathbf{y}} f(\mathbf{x},\mathbf{y}) denotes the original minimax objective, with respect to which the stationarity criterion and convergence guarantees in Theorem 4.3 are established. In contrast, hh is introduced as a compact representation of the sharpness-aware minimax objective in (18), primarily to facilitate the presentation of the problem formulation and the algorithmic motivation.
  • Smoothness of hh (Question 1). We have removed the smoothness claim regarding hh (line 317 of the submission) in the revised manuscript.

Revisions made to the paper.

Section 4 (line 320), revised text:

We assume a PL condition on the ascent variable y\mathbf{y} to ensure that the inner maximization is tractable.

Section 4 (lines 328–336), new text:

Since y\mathbf{y} ranges over all of Rd2\mathbb{R}^{d_2}, the maximization over ν\boldsymbol{\nu} in (18) is absorbed by y\mathbf{y}, so h(x)=max⁡∥ϵ∥≤ρF(x+ϵ)h(\mathbf{x})=\max_{\|\boldsymbol{\epsilon}\|\le\rho}F(\mathbf{x}+\boldsymbol{\epsilon}) with F(x):=max⁡yf(x,y)F(\mathbf{x}):=\max_{\mathbf{y}}f(\mathbf{x},\mathbf{y}). Thus η\eta does not change the exact objective; it acts only through the algorithm, where ν\boldsymbol{\nu} moves the point at which the gradients of ff are evaluated. Moreover, hh need not be differentiable under Assumption 4.1: for f(x,y)=x2−y2f(x,y)=x^2-y^2, h(x)=(∣x∣+ρ)2h(x)=(|x|+\rho)^2 has a kink at x=0x=0. […] In general, we therefore measure convergence through the smooth primal function FF.


AuthorsOpenReview ↗

Response to Reviewer 57jk - Part II

Weakness 2 (exact vs. approximate connection in Theorem 3.3): Theorem 3.3 claims an exact connection to the bilevel problem, but the appendix establishes an approximate connection. … The discussion should also distinguish convergence to a stationary point from obtaining a local or global solution.

Question 2 (inner feasibility at finite γ\gamma): Does Theorem 3.3 guarantee exact inner feasibility at finite γ\gamma, or only the approximate feasibility established in Appendix C.3? … distinguish this from stationarity of the penalized objective.

Response: In the statement of Theorem 3.3, we mistakenly referred to Equation (5) instead of Equation (30) in the Appendix. We have corrected this in the revised version.

Question 2. Theorem 3.3 does not guarantee exact inner feasibility for a finite value of γ\gamma. Instead, it establishes approximate inner feasibility under the additional condition that the limit point is a local or global solution of the penalized problem. Specifically, under the assumptions of Theorem 3.1 and the uniqueness condition of Lemma E.1 (or strong convexity of g(x,⋅)g(\mathbf{x},\cdot)), choosing γ≥ℓf,0μ/ϱ\gamma \geq \ell_{f,0}\sqrt{\mu/\varrho} ensures that 0≤p(x∗,y∗)≤ζγ≤ϱ0\leq p(\mathbf{x}^{\ast},\mathbf{y}^{\ast})\leq \zeta_{\gamma}\leq \varrho, where (x∗,y∗)(\mathbf{x}^{\ast},\mathbf{y}^{\ast}) is a local or global solution to the penalized problem. Equivalently, the resulting feasibility violation is bounded by μℓf,02/γ2\mu\ell_{f,0}^2/\gamma^2.

We emphasize that this approximate feasibility guarantee follows from the local/global optimality condition in Theorem 3.3, and not merely from stationarity of the penalized objective. The stationarity conclusion and the approximate feasibility guarantee are therefore distinct results.

Revisions made to the paper.

Section 3, Theorem 3.3 (lines 293–297), revised text:

[…] Moreover, under the uniqueness condition of Lemma E.1 (or strong convexity of g(x,⋅)g(\mathbf{x},\cdot)), if (x∗,y∗)(\mathbf{x}^{\ast},\mathbf{y}^{\ast}) is a local (respectively, global) solution to problem (12), then it is also a local (respectively, global) solution to problem (30) for some ζγ≤ϱ\zeta_{\gamma}\leq \varrho, where ϱ\varrho is defined in Theorem 3.1.

Section 3, after Theorem 3.3 (lines 299–304), new text:

[…] and that its local or global minima solve the relaxed problem (30), i.e., the bilevel problem (5) up to an inner optimality gap p(x,y)≤ζγ≤ϱp(\mathbf{x},\mathbf{y})\le\zeta_{\gamma}\le\varrho. For finite γ\gamma this link is approximate, not exact, and stationarity alone does not imply a local or global solution.


Weakness 4 (generalization claims): The generalization discussion claims more than the bounds establish. … The authors should describe this trade-off and remove or justify the claim of proven superiority.

Question 5 (generalization): Please qualify the generalization claims by considering both the worst-case empirical-loss term and the complexity term.

Response: We agree, and we revised Appendix D.1 and the contribution list. Larger radii shrink the complexity term, but they also raise the worst-case empirical loss over the perturbation ball, which enters the same bound. The radii therefore trade one term against the other, and the bound does not decrease monotonically in (ρ,η)(\rho,\eta). We removed the statements that larger radii tighten the bound and that SABO has provably superior generalization. That the bound becomes vacuous as (ρ,η)→0(\rho,\eta)\to0 is a limitation of the proof technique; it does not show that standard bilevel methods generalize worse.

Revisions made to the paper.

Appendix D.1 (lines 1525–1528 and 1538–1539), revised text:

Finite perturbations (ρ,η)>0(\rho,\eta)\gt 0 keep log⁡C(⋅)\log C(\cdot) finite, but larger radii also raise the worst-case empirical loss over the perturbation ball, which enters the same bound. The bound is therefore small only for solutions whose loss stays low on the whole ball: the radii trade one term against the other, and the bound does not decrease monotonically in (ρ,η)(\rho,\eta). […] That the bound becomes vacuous as (ρ,η)→0(\rho,\eta)\to0 is a limitation of the proof technique; it does not show that standard bilevel methods generalize worse.

Also changed: the second contribution in Section 1 ("in which larger radii shrink the complexity term but raise the worst-case training loss over the perturbation ball").


AuthorsOpenReview ↗

Response to Reviewer 57jk - Part III

Weakness 3 (experiments vs. analyzed problems): Some real-task experiments appear to use problems or updates different from those analyzed. … A small experiment following Algorithm 2 directly would help connect the minimax theory to the empirical results.

Question 3 (data hypercleaning loss and model): What is the explicit outer loss in the data hypercleaning implementation, and how is the perturbation in xx computed when the validation loss has no direct dependence on the sample weights? … only a convex classifier trained on fixed features?

Question 4 (GAN pseudocode and ablation): Please provide pseudocode for the GAN experiment and explain how it differs from Algorithm 2. … whether the gains require both players to use sharpness-aware updates.

Response: We thank the reviewer. The revised paper writes out the problems and updates that the experiments use, and states where the theory does not apply.

Data hypercleaning (Question 3). The outer loss is the cross-entropy of the classifier on the clean validation set, f(x,y)=1∣Dval∣∑(a,b)∈Dvalℓ(y;a,b)f(\mathbf{x},\mathbf{y})=\frac{1}{|\mathcal{D}_{val}|}\sum_{(a,b)\in\mathcal{D}_{val}}\ell(\mathbf{y};a,b). The inner loss is the training cross-entropy weighted by σ(x)\sigma(\mathbf{x}) plus λ2∥y∥2\frac{\lambda}{2}\|\mathbf{y}\|^2 (Eq. (129), Appendix J.1). As the reviewer notes, ff does not depend on x\mathbf{x}, so ∇xf=0\nabla_{\mathbf{x}}f=\mathbf{0} and x\mathbf{x} is learned only through the penalty. Eq. (14) then allows any ϵ^k\hat{\boldsymbol{\epsilon}}_k in the ball. We take ϵ^k=ρ dk/∥dk∥\hat{\boldsymbol{\epsilon}}_k=\rho\,d_k/\|d_k\| along the x\mathbf{x}-gradient dkd_k of the penalty term and evaluate the penalty terms at xk+ϵ^k\mathbf{x}_k+\hat{\boldsymbol{\epsilon}}_k. So ρ\rho acts through the penalty, and it is active whenever the classifier and the proxy disagree on a sample. Appendix J.1 now lists one iteration step by step. Both levels train all weights of the network (no frozen features), so the lower level is not strongly convex and not known to be PL. We removed the strong-convexity claim from Section 5.2, which now says that these runs test SABO outside the assumptions of our theory.

GAN (Question 4). Appendix J.3 now gives the exact update (Algorithm 3). Each player takes one SAM step on its own loss, perturbing only its own parameters, against the unperturbed opponent; MO is the same code with ρG=ρD=0\rho_G=\rho_D=0. With the non-saturating generator loss the game is not zero-sum, so Theorem 4.3 does not apply. Even with LG=−LD\mathcal{L}_G=-\mathcal{L}_D, the update differs from Algorithm 2: the opponent is not perturbed, the discriminator's SAM step perturbs y\mathbf{y} with the opposite sign of ν\boldsymbol{\nu} in (19), and the experiment uses one inner step, minibatches and Adam. Section 5.3 therefore states that the GAN experiment tests the idea of Section 4, not Algorithm 2 itself, and Appendix J.3 states that for this experiment the theory motivates the update but does not guarantee it.

Which player to perturb. On CIFAR-10, with the tuned optimizer and three evaluation seeds (newly added Table 8), FID is as follows. DCGAN-64: MO 32.132.1, generator only 31.631.6, discriminator only 34.634.6, both 34.434.4. DCGAN-128: MO 30.330.3, generator only 28.928.9, discriminator only 30.030.0, both 28.028.0. Most of the gain comes from the generator perturbation; perturbing the discriminator as well helps only with the wider network. Tuning on a separate seed also selected a generator-only perturbation (Table 6).

(this answer continues in the next part)


From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.