- 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 complexity bound for finding an approximate KKT point of the relaxed problem under ENNAMCQ.
Critical strengths
-
The paper addresses an interesting setting without assuming strong convexity or the PL condition at the lower level.
-
The treatment of inexact Moreau evaluations is useful. In particular, the error estimates and their incorporation into the convergence analysis are carefully developed.
-
The sufficient conditions for ENNAMCQ extend beyond strictly convex lower-level problems.
-
The experiments show promising performance against several existing first-order bilevel methods.
Critical weaknesses
- In Appendix F, the sample weights are defined by , with and . Consider the admissible choice 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.
- The result concerns KKT conditions for a fixed positive relaxation parameter . In contrast, the 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
-
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?
-
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?
-
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
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 under additional lower-level regularity assumptions. In particular, choosing yields with overall first-order/projection complexity . 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 to be independent of (x). For , 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.
(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.98. On FashionMNIST, the separation is more modest, but the AUC approaches 0.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 x, 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) 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-δ Moreau-gap formulation, simultaneously controlling stationarity, feasibility, and complementarity. Its feasibility guarantee is Hρ(x,y)≤δ+εf, where δ>0 is fixed. In contrast, the O(ε−4) guarantees for MEHA and PNGBiO include penalized stationarity together with Hρ(x,y)=O(ε), 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(ε) and εf=O(ε) would formally give Hρ(x,y)=O(ε). However, our complexity theorem is established for fixed δ, and its implicit constants may depend on δ, particularly through the ENNAMCQ margin ηδ. Consequently, our analysis does not establish a uniform O(ε−3) complexity bound as δ↓0. 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) 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 Lxy and BR are empirically chosen.