- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper addresses optimistic bilevel optimization problems where the lower-level problem may be nonsmooth and have multiple solutions. The authors propose to recast this problem using the value gap , where is the inner function and the inner function penalized by the outer function. They show that converges to the optimistic objective at rate under a Hölderian error bound. They propose Ghost, an algorithm which performs projected approximate gradient descent on . They provide a convergence result to stationary points of assuming that is smooth. Numerical illustrations are provided on a toy problem and on data hyper-cleaning with SNLI.
Critical strengths
- S1: This paper analyzes the value-gap approach with nonsmooth lower-level problems, where differencing two valid adjoints can give a wrong direction, and addresses it with compatible readouts at a shared random point. This analysis is new to my knowledge.
Critical weaknesses
-
W1 (Novelty and missing related work): The value-gap formulation is the basis of "value-function-based" or "fully first-order" bilevel methods [1,2,3,4,5], which recast the bilevel problem as s.t. [1,2], or penalize this gap with weight [3,4,5]. With , , , and , minimizing the penalized problem in gives exactly , and its gradient is exactly the ghost direction (3), already used in [3,4]. Moreover, [5] analyzes for the optimistic objective with multiple nonconvex lower-level solutions for smooth problems. None of these works is cited, and the novelty reduces to the treatment of nonsmooth lower-level problems.
-
W2 (Presentation): I personally find the writing extremely compressed and hard to follow. Many paragraphs (e.g., Sections 4.4 and 6.2) are sequences of standalone caveats with no connecting argument. Moreover, some notations are used before or without definition (, ).
Questions for authors
- Q1: How does the proposed formulation compare to the existing literature on value-function-based methods (see W1)? What are the differences and similarities?
3 comments
I thank the authors for their response. Would it be possible to highlight the modifications in the manuscript, by using another color for instance? Otherwise, it hard to evaluate the revision.
Thank you for the suggestion. We have added Ghost_Annotated_Revision.pdf to the supplementary material to make the revisions easier to locate. The marked copy includes a legend on the first page: light blue indicates automatically identified additions or wording changes, orange highlights selected substantive changes, and margin notes point reviewers to passages relevant to their comments. It is intended as a navigation aid rather than an exhaustive, line-by-line diff; the clean revised manuscript remains the authoritative version.
In particular, the revised related-work discussion and Appendix D.1, Table 9 clarify the relationship to the five cited papers and the scope of our contribution. Appendix D.2, Example 2 illustrates the nonsmooth readout issue. We have also revised Section 4.4 and Sections 6.2–6.3 for clarity and clarified the definitions of and .
We hope the marked copy makes these changes easier to review, and thank you again for the helpful suggestion.
Response to Reviewer ZziA
Thank you for your patience. We spent the past few days completing additional experiments to address your comments, and are now posting our response together with the revised manuscript.
Novelty and prior work
You're right: we share the value-gap formulation, and Kwon et al. (2024) already cover smooth, nonconvex inner problems with multiple solutions. We now cite all five papers and compare them in Appendix D, Table 9. Our contribution is nonsmooth readout compatibility.
Here's an example (Appendix D.2, Example 2). Let λ∈[−1,1] be the outer variable and τ>0 the validation-loss weight. Write G for the optimal training value and Vτ for the optimal value after adding τ times the validation loss:
V_\tau(\lambda)=|\lambda|+\frac{\tau\lambda^2}{2(2+\tau)}.$$ The surrogate is $$\Delta_\tau(\lambda):=\frac{V_\tau(\lambda)-G(\lambda)}{\tau} =\frac{\lambda^2}{2(2+\tau)},\qquad \Delta_\tau'(0)=0.$$ Implement $|\lambda|$ as $2r(\lambda)-\lambda$ in the base graph and $2r(-\lambda)+\lambda$ in the tilted graph, where $r(z)=\max(z,0)$ is ReLU for real $z$. At zero, the usual autodiff convention $r'(0)=0$ gives readouts $-1$ and $+1$. The computed direction $d$ is $$d=\frac{1-(-1)}{\tau}=\frac{2}{\tau},$$ Yet the surrogate derivative is zero, even with exact global inner solves. A shared continuously perturbed evaluation point removes the mismatch almost surely; our bound accounts for the displacement. A consistent unperturbed implementation also works in this example, which lies outside Kwon's smooth-input framework. Clarity and notation We've rewritten Section 4.4 and Sections 6.2-6.3 to connect the problem, construction, evidence and scope. Section 4.4 defines $L_\tau$ as a Lipschitz constant of the surrogate gradient on the evaluation neighborhood. Section 5, Eq. (13), defines $S_\tau(\lambda)$ as the global minimizer set of the tilted inner objective before use. We also separate the finite-SGD experiments from the theory's global-certificate assumptions.