acceptodds
Under review as a conference paper at ICLR 2027

Improved KKT Complexity for First-Order Bilevel Optimization under Weak Lower-Level Convexity

Abstract

We study deterministic first-order bilevel optimization under weak lower-level convexity, allowing nonconvex lower-level objectives and without assuming strong convexity, the Polyak–Łojasiewicz condition, or an error-bound property. We consider a -relaxed Moreau-gap constraint, with , for the lower-level stationarity condition and propose an inexact variable-smoothing penalty method (IVSP) for computing its approximate Karush–Kuhn–Tucker (KKT) points. For any fixed relaxation level , under a standard extended no-nonzero-abnormal-multiplier constraint qualification (ENNAMCQ), we prove finite stabilization of the adaptive penalty parameter and an overall first-order complexity for computing an -KKT point. Notably, we give verifiable sufficient conditions for ENNAMCQ covering convex lower-level objectives without nonconstant affine segments (including the strictly convex case), and a class of nonconvex sample-reweighting models. The positive relaxation avoids the intrinsic constraint-qualification degeneracy of the exact Moreau-gap constraint while achieving an lower-level near-stationarity guarantee. Numerical experiments on synthetic and real-world bilevel learning problems illustrate the practical performance of IVSP.

Primary area:
optimization
Keywords:
Bilevel optimization, weakly convex optimization, Moreau envelope, penalty methods, first-order methods, complexity analysis

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_BcxgOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes IVSP, a first-order method for bilevel optimization with weakly convex lower-level objectives. By introducing a positive Moreau-gap relaxation and using an inexact smoothing penalty method, the authors establish an O~(ε−3)\widetilde O(\varepsilon^{-3}) complexity bound for finding an approximate KKT point of the relaxed problem under ENNAMCQ.

Critical strengths
  1. The paper addresses an interesting setting without assuming strong convexity or the PL condition at the lower level.

  2. The treatment of inexact Moreau evaluations is useful. In particular, the error estimates and their incorporation into the convergence analysis are carefully developed.

  3. The sufficient conditions for ENNAMCQ extend beyond strictly convex lower-level problems.

  4. The experiments show promising performance against several existing first-order bilevel methods.

Critical weaknesses
  1. In Appendix F, the sample weights are defined by ω(xi)=1/(1+e−xi)\omega(x_i)=1/(1+e^{-x_i}), with xi∈[−100,100]x_i\in[-100,100] and δ=10−3\delta=10^{-3}. Consider the admissible choice xi=−100x_i=-100 for every training sample. By the bound used in Corollary 18, $ H_\rho(x,y)\le \omega(-100)D_\ell <2.5\times10^{-40}<\delta $ for every y in the classifier domain.

But this does not mean the algorithm necessarily converges to such a solution. Nevertheless, it raises a concern about whether the hyper-cleaning experiment adequately evaluates the intended bilevel structure. It would be helpful to report the learned sample weights and compare with direct validation-loss minimization.

  1. The O~(ε−3)\widetilde O(\varepsilon^{-3}) result concerns KKT conditions for a fixed positive relaxation parameter δ\delta. In contrast, the O~(ε−4)\widetilde O(\varepsilon^{-4}) results quoted for MEHA and PNGBiO include control of the unrelaxed Moreau-gap feasibility error.

The authors acknowledge this difference in Appendix E. Still, the comparison does not establish a complexity improvement for an identical solution criterion. A more explicit discussion of this limitation would make the theoretical contribution easier to assess.

Questions for authors
  1. In the hyper-cleaning experiments, how do the learned sample weights behave? Can the authors rule out the possibility that the relaxed formulation mainly permits direct validation-loss minimization?

  2. Can the authors clarify which experiments satisfy the full theoretical assumptions, particularly ENNAMCQ and the global smoothness bounds? How were the curvature constants used for the Moreau subproblems obtained?

  3. Can the authors provide a comparison under a common feasibility criterion, or clarify more prominently that the improved rate applies to a different relaxed KKT target?

5 comments

(W1 and Q1) Sample Weights and Bilevel Structure

We thank the reviewer for this insightful observation and for suggesting concrete experiments to assess whether the identified degeneracy arises in practice. We agree that the relaxed formulation admits the proposed degenerate feasible points. However, as the reviewer also notes, this does not imply that IVSP necessarily converges to such points.

To investigate the actual behavior, we have added sample-weight evolution and AUC plots in Appendix F.3, Figure 5. On MNIST, IVSP substantially reduces the weights of corrupted samples while maintaining those of clean samples, with the weight AUC approaching 0.980.98. On FashionMNIST, the separation is more modest, but the AUC approaches 0.890.89. In particular, neither experiment exhibits uniform weight collapse.

Importantly, the observed weight evolution provides evidence that IVSP meaningfully exploits the bilevel structure of the problem. Since the upper-level objective is independent of xx, the sample-weight updates are driven entirely by the smoothed Moreau-gap penalty, which incorporates lower-level training information through the inner proximal subproblems. The resulting separation between clean and corrupted samples therefore indicates that the lower-level training problem actively influences the iterates, rather than the method simply reducing to direct validation-loss minimization.

We also conducted the suggested comparison with direct validation-loss minimization using PGD. Although IVSP attained lower validation loss, this comparison does not directly address the concern about weight collapse. We therefore focus the additional results in the revised manuscript on the learned-weight trajectories and AUC, which provide more direct evidence of whether the lower-level training problem meaningfully influences the iterates.

(W2) and (Q3) Complexity Comparison under Different Feasibility Criteria

We agree that our O~(ε−3)\widetilde O(\varepsilon^{-3}) bound does not establish a complexity improvement over MEHA and PNGBiO under an identical solution criterion. The distinction concerns both the feasibility requirement and the stationarity guarantee.

Specifically, IVSP computes an approximate KKT point of the fixed-δ\delta Moreau-gap formulation, simultaneously controlling stationarity, feasibility, and complementarity. Its feasibility guarantee is Hρ(x,y)≤δ+εfH_\rho(x,y)\leq\delta+\varepsilon_f, where δ>0\delta>0 is fixed. In contrast, the O(ε−4)O(\varepsilon^{-4}) guarantees for MEHA and PNGBiO include penalized stationarity together with Hρ(x,y)=O(ε)H_\rho(x,y)=O(\varepsilon), corresponding to vanishing unrelaxed Moreau-gap feasibility error. Thus, the reported complexity exponents cannot be directly compared as guarantees for the same problem and optimality criterion.

Regarding a common feasibility criterion, choosing δ=O(ε)\delta=O(\varepsilon) and εf=O(ε)\varepsilon_f=O(\varepsilon) would formally give Hρ(x,y)=O(ε)H_\rho(x,y)=O(\varepsilon). However, our complexity theorem is established for fixed δ\delta, and its implicit constants may depend on δ\delta, particularly through the ENNAMCQ margin ηδ\eta_\delta. Consequently, our analysis does not establish a uniform O~(ε−3)\widetilde O(\varepsilon^{-3}) complexity bound as δ↓0\delta\downarrow0. We therefore do not claim an improved complexity exponent under the unrelaxed feasibility criterion.

In the revision, we have made this limitation explicit in Section 1.2, including the different feasibility guarantees of IVSP, MEHA, and PNGBiO. We have also clarified the caption of Table 1 and its interpretation in the related-work discussion. Appendix E provides the detailed comparison of the solution criteria. Our contribution is the O~(ε−3)\widetilde O(\varepsilon^{-3}) first-order complexity guarantee for the complete approximate KKT system of a fixed positive Moreau-gap relaxation under weak lower-level convexity and ENNAMCQ.

(Q2) Theoretical assumptions and curvature constants

We have clarified the assumptions and curvature bounds in the revised Appendices B.2 and F.2-F.4. Data hyper-cleaning satisfies the standing smoothness assumptions and ENNAMCQ, as verified by Corollary 20. The synthetic problem is smooth but does not satisfy global ENNAMCQ.

For Omniglot, we follow the standard Conv-4 architecture used in MEHA to maintain comparability. Although ReLU and max-pooling fall outside our smoothness assumptions, the lower-level problem remains smooth and convex in the classifier parameters. We therefore include Omniglot as an additional empirical benchmark beyond the theoretical setting.

Appendix F provides the derivations and values of the curvature constants. These justify strong convexity of the hyper-cleaning Moreau subproblems and the lower-level curvature bounds for Omniglot, where LxyL_{xy} and BRB_R are empirically chosen.

Dear Reviewer Bcxg,

Thank you again for your helpful comments. We would particularly like to draw your attention to the new sample-weight evolution and AUC plots in Appendix F.3 (Figure 5), added in response to W1/Q1. The weight AUC approaches 0.98 on MNIST and 0.89 on FashionMNIST, and neither experiment exhibits uniform weight collapse. These results provide empirical evidence that IVSP meaningfully uses lower-level training information, as discussed in our earlier response.

We would also like to highlight a new theoretical result relevant to W2/Q3. In Appendix D.4 (Proposition 31 and Corollary 33), we establish a complexity bound with constants independent of the relaxation parameter δ\delta under additional lower-level regularity assumptions. In particular, choosing δ=ε\delta=\varepsilon yields Hρ(x,y)≤2εH_\rho(x,y)\leq 2\varepsilon with overall first-order/projection complexity O~(ε−3)\widetilde O(\varepsilon^{-3}). This addresses the vanishing Moreau-gap feasibility concern for this restricted problem class, although the assumptions and stationarity guarantees remain different from those of MEHA and PNGBiO. We have also clarified these distinctions in Section 1.2 and Remark 8.

Regarding Q2, we have clarified the applicability of the theoretical assumptions and the curvature bounds in Appendices B.2 and F.2–F.4.

We would appreciate it if you could review these revisions and let us know if you have any remaining questions or concerns.

Best regards,

The Authors

Thank you for the revisions. The corrected curvature bounds, weight plots, and new uniform-complexity result address parts of my concerns. However, I maintain 2 for two reasons:

The empirical concern is only partly resolved. Figure 5 shows no uniform weight collapse in the reported runs, but does not establish the benefit of the bilevel formulation.

The new uniform result also has a substantial restriction. Under the paper’s smoothness assumptions and fixed Y, uniform weak sharpness in Proposition 31 actually forces S(x)S(x) to be independent of (x). For y∈S(x′)y\in S(x'), these assumptions give $ \kappa d\le L_{yx}|x-x'|d,\quad d=\operatorname{dist}(y,S(x)). $ Hence nearby solution sets coincide; connectedness of X extends this globally. The result therefore excludes problems where lower-level solutions vary with the upper-level variable. This limits how much Appendix D.4 resolves the original concern about the general weakly convex setting.

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

This paper develops IVSP, a first-order variable-smoothing penalty method for computing approximate KKT points of a fixed-(\delta) relaxed Moreau-gap formulation under weak lower-level convexity.

Critical strengths

The paper is very well written and technically complete. For instance, the discussion of ENNAMCQ is helpful, and the sufficient conditions should be highlighted more clearly in the main text with an explicit reference to Appendix B.

Critical weaknesses
  1. The O~(ϵ−3)\widetilde O(\epsilon^{-3}) complexity seems somewhat expected: F2SA already attains this rate under strong convexity, while Prox-F2SA and related methods use Moreau-envelope ideas to handle weaker lower-level structures. The paper should more clearly explain the technical obstacle that prevents a direct extension of existing methods and why obtaining the same rate under weak convexity is nontrivial.

  2. Moreover, it is unclear whether O~(ϵ−3)\widetilde O(\epsilon^{-3}) is optimal. No lower bound is provided, and the paper does not offer evidence that an ϵ−2\epsilon^{-2} rate is impossible.

My current score may slightly underrate the paper’s overall quality, since the four-level ICLR rating scale offers no natural middle option. I would be willing to raise my rating if the above concerns are convincingly addressed.

Questions for authors
  1. What is the key technical barrier in extending existing Moreau-envelope or Prox-F2SA-type methods to weakly convex lower-level problems while retaining a KKT guarantee?

  2. Is there any lower-bound evidence suggesting that ϵ−3\epsilon^{-3}, rather than ϵ−2\epsilon^{-2}, is necessary for this problem class? If not, please clearly position the result as the best-known upper bound rather than implying near-optimality.

4 comments

(W1 and Q1) Technical Barriers to KKT Guarantees under Weak Convexity

We agree that the exponent O~(ε−3)\widetilde O(\varepsilon^{-3}) is not new by itself. Our main contribution is establishing a complete approximate KKT guarantee-jointly controlling stationarity, feasibility, and complementarity—for the fixed-δ\delta Moreau-gap relaxation under weak lower-level convexity and ENNAMCQ, with an overall first-order complexity of O~(ε−3)\widetilde O(\varepsilon^{-3}). This guarantee does not follow directly from existing methods for three reasons.

1. Different lower-level regularity and stationarity guarantees. F$^2$SA (Kwon et al., 2023) establishes the same complexity exponent for hyperobjective stationarity under strong lower-level convexity, which ensures uniqueness and stability of the lower-level solution. Prox-F$^2$BA (Kwon et al., 2024) accommodates nonconvex lower-level objectives but relies on a uniform proximal error-bound condition for perturbed lower-level problems. Weak convexity alone does not imply either assumption, and the reduced hyperobjective need not be differentiable. These are genuine differences: our ENNAMCQ-based analysis accommodates lower-level objectives that fall outside the assumptions of these existing complexity guarantees. For example, the fixed-δ\delta Moreau-gap relaxation associated with g(y)=y4g(y)=y^4 satisfies ENNAMCQ for every δ>0\delta>0, although gg is not strongly convex and fails the local linear proximal error bound required by Prox-F$^2$BA, as discussed in the revised Section 1.2.

2. Constraint qualification and finite penalty stabilization. The Moreau envelope provides a smooth reformulation under weak lower-level convexity, but this alone does not yield a KKT complexity guarantee. In particular, the exact Moreau-gap constraint is intrinsically degenerate: standard constraint qualifications fail at every feasible point (Proposition 15). Introducing δ>0\delta>0 permits strict feasibility but does not automatically guarantee ENNAMCQ.

The key difficulty is therefore to exclude constrained stationary points of the relaxed constraint wherever R≥0R\geq0. Under ENNAMCQ, we establish finite stabilization of the adaptive penalty parameter (Lemma 5), which also yields bounded KKT multiplier estimates. Importantly, we provide verifiable sufficient conditions for ENNAMCQ beyond strong convexity, including convex lower-level objectives without nonconstant affine segments and a class of nonconvex sample-reweighting models (Propositions 17--19 and Corollary 20, Appendix B). Thus, the required regularity is established for the relaxed constraint rather than imposed through a lower-level solution-map error bound.

3. Inexact Moreau evaluations and KKT complexity. The Moreau-gap constraint and its gradient depend on proximal points that are computed only approximately. Lemma 12 establishes one-sided constraint-evaluation errors and smoothed-gradient errors of order O(ζk+ζk/μk)O(\sqrt{\zeta_k}+\zeta_k/\mu_k). The latter are amplified as the smoothing parameter decreases and must be controlled throughout the analysis. We establish descent and finite penalty stabilization despite these errors (Lemmas 4--5), and derive simultaneous stationarity, feasibility, and complementarity bounds at a suitable non-update iteration (Lemmas 26--28). Together with the logarithmic complexity of the inner solves, this yields the overall O~(ε−3)\widetilde O(\varepsilon^{-3}) first-order complexity (Corollary 7).

We also distinguish our result from other Moreau-envelope approaches: MEHA and PNGBiO establish penalized-stationarity and unrelaxed-feasibility guarantees, while TSP considers KKT guarantees through a stochastic primal-dual framework. These results are not directly interchangeable with our deterministic fixed-relaxation KKT guarantee.

In the revision, we have expanded Sections 1.1--1.2 to clarify these technical barriers, distinguish F$^2$SA and Prox-F$^2$BA, and highlight the sufficient ENNAMCQ conditions with explicit references to Appendix B.

(W2 and Q2) Tightness of the Complexity Bound

We agree that the optimality of the O~(ε−3)\widetilde O(\varepsilon^{-3}) complexity has not been established. Our result is an upper complexity bound for computing an approximate KKT point of the fixed-δ\delta Moreau-gap formulation under ENNAMCQ. We do not provide a matching lower bound, and our analysis does not rule out the possibility of achieving O~(ε−2)\widetilde O(\varepsilon^{-2}) complexity under the same assumptions and KKT criterion.

The exponent arises from balancing the stationarity rate O(K−(1−r)/2)O(K^{-(1-r)/2}) with the feasibility and complementarity rates O(K−r)O(K^{-r}) in Theorem 6. Choosing r=1/3r=1/3 yields the reported complexity. This reflects the trade-off in our variable-smoothing analysis, rather than a fundamental lower bound for the problem class. Whether O~(ε−2)\widetilde O(\varepsilon^{-2}) complexity is achievable under the same assumptions and KKT criterion remains open.

We have clarified this in Remark 8 and revised the motivating question and contribution statement in Section 1 to avoid suggesting an optimality claim.

Dear Reviewer bQt2,

Thank you again for your constructive comments. We would particularly like to draw your attention to the revised Sections 1.1–1.2, where we have clarified the technical challenges in establishing KKT guarantees under weak lower-level convexity. In particular, we explain the role of ENNAMCQ in ensuring finite penalty stabilization, the difficulties introduced by inexact Moreau evaluations, and how our assumptions differ from those of F$^2$SA and Prox-F$^2$BA.

We would also like to highlight a new theoretical result established since our initial response. In Appendix D.4 (Proposition 31 and Corollary 33), we prove that, under additional lower-level regularity assumptions, IVSP achieves an ε\varepsilon-KKT point with overall first-order/projection complexity O~(ε−3)\widetilde O(\varepsilon^{-3}), with constants independent of the relaxation parameter δ\delta. Choosing δ=ε\delta=\varepsilon also yields O(ε)O(\varepsilon) distance to the lower-level solution set.

Regarding the optimality of the complexity exponent, we have clarified in Remark 8 that our result is an upper bound and that achieving O~(ε−2)\widetilde O(\varepsilon^{-2}) under the same assumptions remains an open question.

We would appreciate it if you could review these revisions and let us know if you have any remaining questions or concerns.

Best regards, The Authors

Update to Appendix D.4: Relaxation-dependent complexity

Thank you again for your comments. We have further revised Appendix D.4, replacing the earlier uniform weak-sharpness assumption, which was found to be restrictive under our standing assumptions.

The revised Proposition 31 uses a curvature condition along proximal displacements, which includes uniformly strongly convex lower-level objectives and permits nonunique lower-level solution sets that vary with xx (Example 32). Under this condition, Proposition 33 establishes overall first-order/projection complexity O~(δ−3(α−1)/2ε−3)\widetilde O(\delta^{-3(\alpha-1)/2}\varepsilon^{-3}) for α≥2\alpha\geq2, with constants independent of δ\delta and ε\varepsilon. In particular, under uniform strong lower-level convexity, choosing δ=ε\delta=\varepsilon yields O~(ε−9/2)\widetilde O(\varepsilon^{-9/2}) complexity.

Nevertheless, the original fixed-δ\delta complexity guarantee and our explanations of its technical contributions remain unchanged.

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

This paper addresses bilevel optimization with fixed convex constraints, where both objectives are smooth and the lower-level objective is weakly convex. The authors propose an inexact variable-smoothing penalty (IVSP) method and establish a first-order complexity of Õ(ε⁻³) for finding an ε-KKT point of a fixed-δ relaxed Moreau-gap reformulation, under the extended no-nonzero-abnormal-multiplier constraint qualification (ENNAMCQ). The method employs a Moreau-envelope reformulation to build a smooth relaxation of the lower-level stationarity condition, combined with a smoothed exact-penalty approach featuring adaptive penalty updates and inexact proximal computations. The theoretical analysis shows finite stabilization of the penalty parameter and provides sufficient conditions for ENNAMCQ in selected convex and nonconvex lower-level problems. Experiments on a synthetic nonconvex problem, data hyper-cleaning with MNIST and FashionMNIST, and few-shot learning on Omniglot compare IVSP against representative first-order bilevel methods, showing competitive performance in convergence speed, validation loss, and test accuracy.

Critical strengths
  1. The paper establishes an Õ(ε⁻³) first-order complexity guarantee for computing approximate KKT points of a fixed-δ relaxed Moreau-gap reformulation, without requiring lower-level strong convexity, PL conditions, or error bounds. The analysis controls stationarity, feasibility, and complementarity, yielding a theoretically meaningful guarantee for the relaxed constrained formulation.

  2. The paper integrates inexact Moreau-envelope evaluations into a smoothed exact-penalty framework and establishes finite stabilization of the adaptive penalty parameter under ENNAMCQ. It further derives sufficient conditions for ENNAMCQ in certain convex and structured nonconvex lower-level problems, improving the applicability and interpretability of the theoretical guarantees.

Critical weaknesses
  1. The Õ(ε⁻³) complexity holds only for a fixed δ > 0 and the convergence analysis does not remain uniform as δ → 0. Proposition 17 also imposes a positive sufficient lower bound on δ for nonconvex sample-reweighting problems. Even under lower-level strong convexity, achieving g(x, y) − v(x) = O(ε²) requires δ = O(ε²) and a corresponding feasibility tolerance, for which the displayed rates formally suggest Õ(ε⁻⁴), but the paper does not establish this joint complexity.

  2. The paper does not provide quantitative function-value or gradient approximation guarantees linking its penalty formulation to the original bilevel hyperobjective, nor does it establish equivalence between their stationary solutions. The limiting Moreau-gap constraint characterizes lower-level stationarity only for nonconvex problems, making the comparison in Table 1 with methods targeting original bilevel stationarity or vanishing lower-level optimality errors potentially misleading.

  3. Table 1 contains questionable complexity comparisons. V-PBGD is reported as Õ(ε⁻²) with a fixed penalty coefficient, yet accounting for the accuracy-dependent penalty yields Õ(ε⁻³), while the improved F²SA analysis achieves Õ(ε⁻²) in the constrained setting. The authors should revisit these comparisons in light of [1] and [2], while carefully distinguishing their assumptions and convergence criteria.

  4. The experimental comparison raises concerns about baseline tuning, particularly for F²SA, which uses a large initial stepsize α₀ = 5, γ = 0.5, and a small initial penalty coefficient λ₀ = 1, with an update rule that prevents the penalty coefficient from increasing during the first 8,000 iterations. These choices may explain its poor reported performance, and the absence of F²BA and adequate hyperparameter sensitivity experiments further weakens the empirical comparison.

[1] Jiang et al., Efficient Penalty-Based Bilevel Methods: Improved Analysis, Novel Updates, and Flatness Condition, arXiv:2511.16796. [2] Chen et al., On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis, COLT 2024.

Questions for authors
  1. The convergence analysis assumes continuously differentiable objectives with Lipschitz-continuous gradients. Do all experimental problems satisfy these assumptions, particularly the Omniglot experiment involving ReLU and max-pooling operations?

  2. Can the authors provide empirical convergence results for the three KKT residuals (stationarity, feasibility, and complementarity), along with the evolution of the adaptive penalty parameter and the accuracy of the inner Moreau subproblems? These results would help assess whether the theoretical mechanisms are reflected in practical performance.

  3. Since the outer algorithm is adapted from sESQM (Xu et al., 2026), which parts of the convergence and complexity analysis require fundamentally new arguments beyond extending the existing framework to inexact Moreau-envelope evaluations?

5 comments

(W1) Fixed-Relaxation Scope and Nonuniform Complexity

The positive relaxation δ>0\delta>0 is essential to our KKT approach: the exact Moreau-gap constraint is intrinsically degenerate and fails standard constraint qualifications at every feasible point (Proposition 15). The relaxation removes this structural obstruction and enables KKT analysis under ENNAMCQ. In the original version, the nonuniformity as δ↓0\delta\downarrow0 is already acknowledged in Appendix A.4 and illustrated by Example 25. We have further emphasized the fixed-δ\delta scope in Remark 8.

Regarding Proposition 19 (previously Prop 17), the condition δ>ω(−M)Dℓ\delta>\omega(-M)D_\ell is sufficient, not necessary, for ENNAMCQ in the particular class of sample-reweighting models considered there. It is not required by our general complexity theorem. We have clarified this distinction following Proposition 19.

Finally, the suggested O~(ε−4)\widetilde O(\varepsilon^{-4}) calculation is valid for fixed δ\delta: choosing r=1/2r=1/2 gives an (ε,ε2,ε)(\varepsilon,\varepsilon^2,\varepsilon)-KKT point at that first-order complexity. Under strong lower-level convexity, Proposition 16 yields g(x,y)−v(x)≤1+ρμgρμg(δ+εf)g(x,y)-v(x)\leq \frac{1+\rho\mu_g}{\rho\mu_g}(\delta+\varepsilon_f). Thus, choosing δ=O(ε2)\delta=O(\varepsilon^2) and εf=ε2\varepsilon_f=\varepsilon^2 gives g(x,y)−v(x)=O(ε2)g(x,y)-v(x)=O(\varepsilon^2). However, since the said O~(ε−4)\widetilde O(\varepsilon^{-4}) rate involves implicit constants which depends on δ\delta (through the ENNAMCQ margin ηδ\eta_\delta), this does not establish joint O~(ε−4)\widetilde O(\varepsilon^{-4}) complexity. This is also emphasized in Remark 8.

(W2) Connection to the Original Bilevel Problem and Comparability of Guarantees

We have strengthened the connection to the original bilevel problem by establishing a quantitative hyperobjective approximation guarantee under uniform strong lower-level convexity (new Proposition 16, Appendix A.4). Writing Φ(x)=f(x,y⋆(x))\Phi(x)=f(x,y^\star(x)) and Φδ(x)\Phi_\delta(x) for the relaxed hyperobjective, we prove 0≤Φ(x)−Φδ(x)≤Aδ,0\leq \Phi(x)-\Phi_\delta(x)\leq A\sqrt{\delta}, uniformly in xx. Moreover, any εf\varepsilon_f-feasible point satisfies ∣f(x,y)−Φ(x)∣≤Aδ+εf|f(x,y)-\Phi(x)|\leq A\sqrt{\delta+\varepsilon_f}.

The correspondence under weaker assumptions is already established in Appendix A.4: the exact Moreau-gap constraint characterizes lower-level stationarity under weak convexity and recovers lower-level optimality (and hence the original bilevel feasible set) under convexity. The relaxed feasible sets also converge to the exact Moreau-gap feasible set as δ↓0\delta\downarrow0.

Table 1 is intended to summarize different optimality guarantees rather than provide a direct complexity ranking. The Guarantee column distinguishes hyperobjective stationarity, penalty stationarity, weak KKT, and relaxed KKT. This interpretation was explicitly stated in Appendix E of the original submission. We have further clarified the table caption and related-work discussion (see last paragraph of Section 1.2) to make these distinctions more immediately apparent.

(W3) Corrections and Clarifications to Complexity Comparisons

We have updated Table 1 to address the concerns raised:

  • V-PBGD: We corrected the reported complexity from O~(ε−2)\widetilde O(\varepsilon^{-2}) (fixed penalty) to O~(ε−3)\widetilde O(\varepsilon^{-3}) (accuracy-dependent penalty), with the relevant qualifications explained in Appendix E.

  • Jiang et al. [1]: We added ALT-PBGD, which achieves O~(ε−2)\widetilde O(\varepsilon^{-2}) complexity for reduced-penalty stationarity under strong lower-level convexity, distinguishing it from the original F2SA result.

  • Chen et al. [2]: We added the O~(ε−2)\widetilde O(\varepsilon^{-2}) hyperobjective-stationarity result for F2BA under PL and additional regularity assumptions.

We have also expanded the discussion in Section 1.2 and Appendix E to clarify the assumptions, convergence criteria, and complexity rates of these methods.

(W4) Baseline Tuning and Experimental Fairness

We retuned F$^2$SA for Omniglot, enabling earlier penalty updates and improving the final validation loss from 1.70 to 0.46. The updated results and hyperparameter settings are provided in Figure 3 and Appendix F.4 (Table 4).

We also included F$^2$BA as an additional tuned baseline across all experiments (Figures 1-3 and Appendix F, Tables 2-4). Finally, we added hyperparameter sensitivity experiments for IVSP on MNIST hyper-cleaning, varying μ0\mu_0, γ0\gamma_0, and δ\delta (Appendix F, Figure 6). The results indicate robustness across the tested settings.

(Q1) Smoothness assumptions in the experiment

The synthetic and hyper-cleaning experiments satisfy the smoothness assumptions of our analysis. For Omniglot, we adopted the standard Conv-4 architecture used in MEHA (Liu et al., ICML 2024) to maintain comparability. Its ReLU and max-pooling operations make both the UL and LL objectives nonsmooth in the feature-extractor parameters, although the LL objective remains smooth and convex in the classifier parameters for fixed xx. None of the compared algorithms, including IVSP, provides theoretical guarantees for this nonsmooth setting.

Thus, the Omniglot experiment lies outside the smooth convergence guarantees of IVSP and the compared methods. We include it as an additional empirical benchmark to evaluate their practical performance in this setting. This distinction is now clarified in Appendix F.4.

(Q2) Empirical KKT Residuals, Penalty Updates, and Inner Accuracy

We have added the convergence trajectories of the three KKT residuals for the synthetic experiment (Figure 1) and MNIST/FashionMNIST hyper-cleaning (Appendix F.3, Figure 4). Appendix F.2-F.4 ("Penalty update" paragraphs) also reports the behavior of the adaptive inverse-penalty parameter γk\gamma_k, which undergoes only three updates in the synthetic experiment and remains constant in the real-world experiments, making separate plots unnecessary.

For the inner Moreau subproblems, we prescribe the accuracy ζk=ζˉμkq\zeta_k=\bar{\zeta}\mu_k^q and provide a computable residual-based stopping criterion that certifies the required objective-gap bound (Section 2.3 and Appendix C, Lemma 21). The normalized Moreau-gap curves, (g−gρ)/δ(g-g_\rho)/\delta, in Figure 2 additionally illustrate the behavior of the relaxed constraint.

(Q3) Technical Contributions Beyond sESQM

We acknowledge that IVSP adopts the variable-smoothing and adaptive-penalty framework of sESQM (Xu et al., 2026). However, applying this framework to the Moreau-gap formulation is not immediate when the constraint function and its gradient are accessible only through inexact proximal computations. The original sESQM analysis assumes exact evaluations, whereas IVSP must control the effects of inexactness on descent, penalty updates, and KKT residuals.

The main additional arguments are:

  • Inexact evaluations (Lemma 12, Appendix A.3): We establish one-sided Moreau-gap errors and explicit gradient-error bounds, which are essential for the subsequent analysis.
  • Descent and penalty stabilization (Lemmas 4--5): We develop an inexact Armijo condition and establish finite penalty stabilization under ENNAMCQ despite the errors in the constraint evaluations and gradients.
  • KKT complexity (Lemmas 26--28, Appendix D.3): In particular, Lemma 28 uses a different selection argument from sESQM. Rather than selecting a window of consecutive iterations with small steps, we exclude the finitely many penalty-update iterations from the weighted descent estimate and directly identify a non-update iteration satisfying simultaneous stationarity, feasibility, and complementarity bounds, including the inexactness errors.
  • Overall first-order complexity (Corollary 7): Using the computable inner stopping rule and logarithmic proximal-solver complexity (Lemmas 21--22), we establish an overall O~(ε−3)\widetilde O(\varepsilon^{-3}) first-order complexity, including the inexact Moreau computations.

Thus, while the outer complexity mechanism is inherited from sESQM, our analysis establishes that its convergence guarantees can be preserved with implementable inexact Moreau evaluations, using additional error estimates and a different KKT-iterate selection argument.

Thank the reviewer for their detailed response. The answers are clear and easy to follow. I would revised the score later after the discussion period.

I have some remaining problem regarding my original W1-2, which is my greatest concern on the problem of δ\delta:

  • I am aware of the explanation in the Appendix A.4 when I raised the concern. The clarification of the problem did not eliminate its importance, as having non-uniform delta would greatly dampen the strength of this work.
  • I do understand and am aware the skill of using such δ\delta as a relaxation, which is interesting despite the limitation above. My understanding is that as the authors are tackling with the very general weak LL convexity problem, the relaxation such as delta is unavoidable. I do appreciate the authors' effort towards trying to solve these line of difficult problem. From my understanding, it would be valuable to present in the way both acknowledge the nonuniformity of δ\delta, at the same time give concrete (and preferrably) comprehensive classes of "additional assumptions", under which you can have uniform delta. That would make the paper of more strength.

Thank you.

Comments on the paper

1 comment

Contributions, scope, and main revisions

We thank the reviewers for their careful assessment and constructive feedback. We briefly summarize the paper’s scope and the main revisions for ease of reference.

Our central contribution is KKT complexity under weak lower-level convexity. We develop IVSP, a deterministic method using first-order information and projections. For any fixed δ>0\delta>0, under the stated assumptions including ENNAMCQ (for which we provide sufficient conditions), IVSP computes an ε\varepsilon-KKT point of the δ\delta-relaxed Moreau-gap formulation with overall O~(ε−3)\widetilde O(\varepsilon^{-3}) first-order/projection complexity, including the cost of inexact Moreau evaluations. The guarantee simultaneously controls stationarity, feasibility, and complementarity at the same iterate, without requiring strong convexity, a PL condition, or a lower-level error bound.

The discussion has led to the following substantive improvements:

  • Quantitative relaxation dependence: The revised Appendix D.4, Propositions 31 and 33, quantifies the ENNAMCQ margin and complexity as δ\delta decreases under an additional proximal-curvature condition. This condition includes uniform strong lower-level convexity and permits nonunique lower-level solution sets that vary with the upper-level variable (Example 32). It replaces the earlier, overly restrictive uniform weak-sharpness assumption.
  • Strengthened experimental evaluation and technical clarification: We corrected the curvature bounds, retuned F²SA and added F²BA comparisons, and included learned-weight/AUC diagnostics, KKT residual trajectories, penalty behavior, and hyperparameter-sensitivity experiments (Section 4 and Appendix F).

We have provided detailed responses and revision pointers in the individual reviewer threads, and clarified the scope and limitations of the guarantees throughout the manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.