- 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 , 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 ?
Minor mistake in Line 229: Assumption 2 is missing.
4 comments
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 ), if is a local (respectively, global) solution to problem (12), then it is also a local (respectively, global) solution to problem (30) for some , where is defined in Theorem 3.1.
Section 3, after Theorem 3.3 (lines 299–304), new text:
[…] For finite 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.
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 with a linear head (M parameters), and the upper level holds one weight per training text ( variables). The data set is AG News with label noise, and we report three seeds. SABO reaches test accuracy, against for BO and for ERM. It beats BO on every seed and raises the F1 of the cleaner from to . It costs BO per iteration, but BO given the same time ( epochs) reaches only . Memory is unchanged ( against GB), because the proxy and the perturbations live in the adapter. At noise the accuracy gain is small ( points), but the cleaner is much better (F1 against ). 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 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.
Response to Reviewer kxcU- Part IV
Question 2 (choice of ): Can authors provide any insights on the selection of ?
Response: The choice of 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 . Consequently, the inner optimization error decreases proportionally to .
The lower bound on 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
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 , 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 .
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).
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.
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 γ, 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)