Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimization

We express our sincere gratitude to reviewer FxiL for recognizing our contributions and insightful comments. Below, we address the concerns raised.

On the practical efficiency of the zero-order method

In the algorithmic part of our work, the primary goal is establishing the theoretical computability of Clarke hyper-stationarity for the concerned BLO. To this end, it suffices to adopt a standard algorithm, i.e., a zero-order method, and utilize the developed structural properties. We view this computability result as a foundational step toward designing more efficient algorithms for computing Clarke hyper-stationary points. We did not provide empirical results in the current version because, to the best of our knowledge, no benchmark algorithms yet exist for computing Clarke hyper-stationary points. Given more space in the main body, we may include emprical experiments in a future version of our manuscript.

|Do you think the zero-th order algorithm have implications for first order algorithms, which is more practical? What is the major gap between them?

Certainly. We believe that the convergence guarantees established for the zero-order algorithm offer meaningful implications for first-order methods. In particular, one may expect stronger results—such as better dependence on the parameters and dimension—when using first-order algorithms.

Despite the potential efficiency of first-order methods, the evaluation of the hyper-subgradient might be a challenge to implement them, as this involves computing the subgradient of parametric function $\min_{y\in S(x)} F(x,y)$ or $\max_{y\in S(x)} F(x,y)$. This is highly nontrivial especially when $S(x)$ has multiple elements. In comparison,zero-order methods only require evaluations of the hyper-objective value, which are readily approximated using simple bilevel algorithms, as we discussed in lines 297-298 and Footnote 3.

That said, exploring first-order methods for computing Clarke hyper-stationarity in BLO with multiple lower-level solutions is a promising direction. In particular, once an efficient oracle for computing the hyper-subgradient was developed, it may lead to stronger convergence guarantees and practically effective algorithms for computing Clarke hyper-stationarity.

We thank the reviewer for pointing out the format issue. We used the provided neurips_2025.sty file in our tex file without modifying the margins or font size. We will address any remaining minor discrepancies in a future version of our manuscript.

We sincerely thank reviewer PTCZ for appreciating our contributions to bilevel optimization and providing valuable feedback. We also hope that Proposition 1 and Proposition 2 will find their applications in other optimization fields. Below, we address the concern raised.

On the dimension dependency in the upper bound

Thank you for the insightful observation and valuable comments. In Sec. 4, our primary goal is to establish the computability of Clarke stationarity, rather than to optimize the dimension dependence in the upper bound. That said, we agree that improving the dimension dependence is a compelling direction for future work. As you suggested, it may be possible to obtain a dimension-free upper bound under additional structural assumptions, which we believe is worth exploring further.

We sincerely thank reviewer orA8 for recognizing our contributions and providing insightful comments. Below, we address the concerns raised.

On the convexity assumption on $S(x)$

Thanks for pointing out this. We believe that this assumption is natural in BLO setting because defining the hyper-objective function involves minimizing the upper-level function over $S(x)$. If $S(x)$ were nonconvex, even evaluating the hyper-objective value generally become NP-hard. Furthermore, this assumption is weaker than the convexity of the lower-level function adopted in the literature (see e.g., [7, Assumption E.1], [42, Assumption 3.4], and [16, Chapter 9.1]).

Nevertheless, one can still weaken this convexity assumption. In our analysis, this convexity condition is primarily used to ensure the non-expansive property of the projection operator $\Pi_{S(x)}$ in lines 580 and 620. Thus, it be replaced by a weaker condition, such as a non-expansive-type property of the projection, without affecting our main results in Sec. 3.

On the minor issues and typo

We appreciate the reviewer's careful reading and pointing out the two typos. We will correct them accordingly. Also, given more space for the main body, we will include a brief recall of the definition of Goldstein stationarity for clarity in a future version of the manuscript.

We sincerely thank reviewer fL5D for the valuable feedback and appreciation of our contributions! We address the concerns raised as follows.

The relation of set smoothness to other regularity conditions

(a) While one of our main contributions is to introduce the concept of set smoothness, we highlight that relating it to the lower-level PL condition is a second key contribution; see Proposition 2. Proposition 2 shows that set smoothness holds for a group of nonconvex-PL BLO problems that are widely studied in the literature. It provides valuable insight into the generality and practical relevance of the set-smoothness condition.

(b) Great suggestion regarding natural examples where set smoothness holds while other assumptions fail. Here is a simple illustrative case: Consider the lower-level function $g(x,y)=h(\sin(x)+y)$ for a function $h:R\to R$ with a nonempty set of minimizers $V=\arg\min_z h(z)$. Then, the solution set function $S(x)=\arg\min_{y}h(x,y)$ satisfies $S(x)=V-\sin(x)$. In this example, $S$ satisfies set smoothness yet no additional regularity assumptions are required on $h$ or $g$. This illustrates that when $g$ has a separate structure in $x$ and $y$, set smoothness may arise naturally. We will incorporate this discussion in the future version of our manuscript in response to your suggestion.

Preference on Clarke stationarity

As noted in lines 150-153 of Sec. 2, Goldstein stationarity is a relatively weak condition, whereas Clarke stationarity is significantly stronger. For example, there exists a differentiable function $f$ such that a point $x$ with $\|\|\nabla f(x)\|\|\geq1$ still satisfying Goldstein stationarity [31, Proposition 1]. In contrast, Clarke stationarity excludes such points, offering a more meaningful notion of stationarity. Consequently, employing Clarke stationarity would lead to much stronger theoretical convergence guarantees for algorithms. Following your suggestion, and given more space in the main body, we will provide a more detailed justification for our preference for Clarke stationarity in a future version of our manuscript.

Position of set smoothness in broader context

We agree that discussing the implications of results in Sec. 3 would be highly insightful. As we mentioned in Sec. 5, our results may have potential implication in coupled minmax optimization. Indeed, our Proposition 1 may directly apply to the inner problem of coupled minmax problem (see reference [46]) under set smoothness condition, offering structural insights into such problems. For algorithmic implication, the established weak convexity/concavity suggests that the problems fall within the broad class of weakly convex/concave optimization. This connection opens the door to utilizing established methods from that literature, such as subgradient methods, proximal point methods, and zero-order methods. We will incorporate these discussion on the implication of our results in the future version of our manuscript.

Clarification on Algorithm 1 in Sec. 4

We note that the main contribution of Sec. 4 is establishing the computability of Clarke hyper-stationarity for the concerned BLO, as we stated in lines 293-294 of Sec. 4. To achieve this goal, we do not necessarily need to design a new special algorithm. Instead, we utilize the established structural property in Sec 3 and extend a standard algorithm, i.e., the zero-order method, also used in [7], to both optimistic and pessmistic BLO. While previous works only show that it computes Goldstein stationarity, our analysis provides a stronger convergence guarantee to approximate Clarke stationary points. This is enabled by the weak convexity/concavity we established, as noted in lines 313-315. These results enhance the understanding of the computability of BLO and we leave designation of new efficient algorithms for computing Clarke stationarity for future work, as stated in lines 329-331.

|Has Definition 2 (set-smoothness) appeared in prior literature, perhaps in the context of set-valued analysis or variational analysis?

Indeed, we carefully reviewed related concepts for set-valued mappings in the literature on set-valued analysis and variational analysis, including but not limited to the classical reference [28] and a recent book [38]. To the best of our knowledge, the specific concept of set smoothness as defined in Definition 2 has not appeared in prior work. In Footnote 2, we provide a comparison between our proposed notion and existing concepts for set-valued functions. Given more space in the main body, we plan to present this comparison more explicitly in a future version of the paper.

|Could the proposed method or analysis be extended to stochastic bilevel settings?

Certainly. We believe it is quite natural to extend our methodology to stochastic/decentralized settings, which are practical for real applications. As the lower-level PL condition has also been adopted in such settings, we expect that similar properties and strong convergence results can be obtained.

If you have any additional concerns regarding our manuscript, we would be happy to provide further clarifications. Finally, we thank the reviewer for pointing out the format issue. We used the provided neurips_2025.sty file in our tex file without modifying the margins or font size. We will address any remaining minor discrepancies in a future version of our manuscript.