Constrained Bi-Level Optimization: Proximal Lagrangian Value Function Approach and Hessian-free Algorithm

We sincerely appreciate the time you dedicated to reviewing our paper. Your feedback is valuable to us, and we would like to address some specific points for clarification.

(1) Assumption 3.1(i) seems too strong for me. Usually, the involved functions in BLO are assumed convex only w.r.t. $y$.

$**Reply:**$ We appreciate your comment and would like to clarify. First, Assumption 3.1 is about the $L$-smoothness and the lower boundedness of $F(x,y)$, without imposing any convexity condition on $F$.

If you are referring to the convexity in Assumption 3.3(i), it is a common and standard assumption in constrained bilevel optimization. Recent research, such as Gao et al. (2023), also employs this assumption.

It is important to note that in all experiments conducted by Khanduri et al. (2023), Xiao et al. (2023b), and Gao et al. (2023), as well as in the application models used in our numerical experiments, the lower-level constraints are either linear or linearly coupled and thus consistently satisfy Assumption 3.3(i).

(2) The stationarity measure needs further clarification. The proposed measure is based on (16). However, it is not clear how the stationary points of (16) are related to the original BLO.

$**Reply:**$ To provide some clarifications: Firstly, the equivalence between the constrained problem (6) and the original BLO problem (1) is rigorously discussed in Theorems A.1 and A.2. Additionally, in our study, we utilize the residual function $R_k$, as defined in (15), as the measure of stationarity for the constrained problem (6). This approach is justified as $R_k$ acts as a stationarity measure for the approximate KKT condition of problem (6), as discussed in Andreani et al. (2010). Moreover, $R_k$ is also applicable as a stationarity measure for the penalized problem (16) of problem (6).

(3) The techniques in the theoretical proofs lack novelty, which directly takes advantage of analysis for penalty methods.

$**Reply:**$ Our work introduces significant technical innovations for several reasons:

(i) We diverge from traditional methods by proposing a novel single-level equivalent reformulation for constrained BLO problems. This reformulation is based on a newly introduced proximal Lagrangian value function associated with the constrained LL problem.

(ii) The newly introduced proximal Lagrangian value function is defined as the value function of a strongly-convex-strongly-concave proximal min-max problem. Our study of its continuous differentiability, along with the derivation of its derivative as presented in Lemma A.1, constitutes a novel theoretical contribution.

(iii) Additionally, our findings regarding the Lipschitz continuity of the saddle point solution to the strongly-convex-strongly-concave proximal min-max problem defining the proximal Lagrangian value function, as detailed in Lemma A.3, represent a significant theoretical advancement.

(iv) Furthermore, the formulation of the descent lemma for the proximal Lagrangian value function, as elaborated in Lemmas A.2 and A.4, also signifies a theoretical progression.

(v) The newly established properties of the proximal Lagrangian value function, as mentioned above, play a crucial role in underpinning the non-asymptotic convergence of our proposed single-loop algorithm.

(4) What is the central benefit of using the Moreau envelope instead of the optimal value function, especially in the technical parts?

$**Reply:**$ Firstly, we would like to clarify that our approach is not the Moreau envelope of the lower-level problem as described in Gao et al. (2023). Our new proposed algorithm is based on the concept of the proximal Lagrangian value function.

In constrained BLO, methods based on value functions face challenges due to the non-differentiability of constraints arising from such value function-based reformulations. This issue arises even when the lower-level problem's data is smooth, as the value function typically lacks differentiability if the solutions or the Lagrangian multipliers of the lower-level problem are not unique.

To address this challenge, we introduce a new proximal Lagrangian value function tailored for handling constrained LL problem. Utilizing this function, we propose a new single-level reformulation for constrained BLOs, transforming them into equivalent single-level optimization problems with smooth constraints. The proximal Lagrangian value function, defined as the value function of a strongly-convex-strongly-concave min-max problem, exhibits the advantageous property of continuous differentiability.

Building on this reformulation, our work develops a Hessian-free gradient-based algorithm for constrained BLOs and provides a non-asymptotic convergence analysis.

We respectfully disagree with Reviewer 4Vih's comments regarding the Ethics Concerns, which did not appear in the original version of this reviewer’s Official Review. It should be noted that, as indicated by the system time record, these newly added Ethics Concerns were included in the reviewer’s Official Review only after we had submitted our rebuttal to their initial review. Moreover, the reviewer did not respond to our rebuttal. Consequently, we did not receive any notifications from the system and only became aware of these newly added Ethics Concerns a few hours ago.

Below, we provide detailed clarifications to address this biased comments.

(1) $**Differences in Problem Settings and Challenges:**$

It's important to note that submissions 3145 and 3552 are tackling two distinct challenges that arise in the development of single-loop Hessian-free algorithms for bi-level optimization (BLO) problems. Specifically, the configurations of the BLO problems, and more specifically, the settings of the lower-level problems examined in submissions 3145 and 3552, are significantly different.

To be more specific, submission 3145 focuses on BLO with an $**unconstrained**$ lower-level problem with potentially $**nonconvex**$ objective and a potentially additional $**nonsmooth**$ component depending on both upper- and lower-level variables and it is for addressing the nonconvexity and nonsmothness challenges appeared in the lower-level problem of BLO.

In contrast, submission3552 addressed BLO problems with $**constrained**$ convex lower-level problems.To provide more detail, the lower-level problem is with coupled lower-level constraints, and both the objective and constraint functions of lower-level problem is smooth and convex with respect to the lower-level variable. And submission3552 primarily addressed challenges arising from coupled lower-level constraints, i.e., lower-level $x$-dependent constraints.

To summarize, the differences in problem settings and challenges can be outlined as follows.

Dear Reviewer 4Vih

Thank you so much for pointing out the potential research integrity issue (dual submission). I realize Reviewer W8M5 also share his/her opinion on this, so I response there with my thought. Please take a look at that discussion and leave your thoughts.

Thanks,

AC

(2) In the experiments, how to choose these hyper parameters including the parameter $r$ in set $Z$?

$**Reply:**$
Thank you for your question. The table below outlines the parameter settings for the experiments involving the parameter $r$:

(3) From the Theorem 3.1, the best convergence rata is $O(1/K^{1/4})$ when $p=1/4$?

$**Reply:**$ Yes, you are correct.

(4) It is better to list some bilevel optimization examples in machine learning that have nonsmooth and weakly convex lower level functions, which will strength the motivation of this work.

$**Reply:**$ Thank you for your suggestions. Since the $L$-smoothness of $f$ over $X \times Y$ ensures its weak convexity of $f$ on the same domain, the setting of a weakly convex lower-level objective encompasses all sufficiently smooth applications within bounded $X \times Y$ in the realm of machine learning.

We sincerely appreciate the time you dedicated to reviewing our paper and are grateful for the valuable insights you provided. In the following, we will address each of your questions with thorough consideration.

(1) In the proposed LV-HBA algorithm, there exist many hyper parameters such as $\alpha_k$, $\beta_k$, $\eta_k$, $\gamma$, $c_k$. Although the authors provided the range of these parameters in the convergence analysis, I still think that the choice of these hyper parameters is not easy in practice.

$**Reply:**$ In addition to the step size parameters, our method involves three hyperparameters: $\gamma$, $r$, and $c_k$. The parameters $\gamma$ and $r$ define the truncated proximal Lagrangian value function. Theoretically, the requirements for $\gamma$ and $r$ are modest; $\gamma$ is positive, and $r$ should be large. The penalty parameter, $c_k$, follows a specific selection strategy outlined in Theorem 3.1, namely $c_k = \underline{c}(k+1)^p$ where $p \in (0,1/2)$ and $\underline{c}>0$. Consequently, in practice, typically only the step size parameters require careful tuning.

In our numerical experiments, we analyzed the sensitivity of the parameter $c_k$, with its convergence curve displayed in Figure 2.

Additionally, to assess the sensitivity of the remaining parameters, further numerical experiments were conducted on the LL merely convex synthetic model. We record the time when $\|x^k - x^*\| / \|x^*\| \leq 10^{-2}$ is met by the iterates generated by LV-HBA. The results are as follows:

We sincerely appreciate the time and effort you dedicated to reviewing our paper and are grateful for your constructive comments. Below, we will respond to each of the questions you raised.

(1) In Table 1, to the best of my knowledge, BVFSM does not require LL objective to be convex.

$**Reply:**$ Thank you for your observation. You are correct that BVFSM does not require the LL objective to be convex. We appreciate your comment and will clarify this point in a future revision of the paper.

(2) The authors have not included some recent works that investigate algorithms for addressing constrained Bi-Level Optimization (BLO) problems through the value function approach, such as:

Fliege, J., Tin, A., & Zemkoho, A. (2021). Gauss–Newton-type methods for bilevel optimization. Computational Optimization and Applications, 78(3), 793-824.

Fischer, A., Zemkoho, A. B., & Zhou, S. (2022). Semismooth Newton-type method for bilevel optimization: global convergence and extensive numerical experiments. Optimization Methods and Software, 37(5), 1770-1804.

$**Reply:**$ Thank you for sharing these recent works with us. We'll take them into account when revising our manuscript.

(3) On page 8, $|y^k - y^*(x)|$ should be revised to $|y^k - y^*(x^k)|$?

$**Reply:**$ Thank you for pointing out the typo. We'll correct it in the revised version.

(4) When the constraints of the LL problem are absent, i.e., when $g=0$, does the introduced proximal Lagrangian value function revert to the classical Moreau envelope function of the LL objective? Furthermore, is there any relationship between the proximal Lagrangian value function and the augmented Lagrangian function of the LL problem?

$**Reply:**$ Thank you for your interesting questions.

Firstly, your observation is accurate: the proximal Lagrangian value function introduced in our study simplifies to the classical Moreau envelope function of the lower-level objective in the absence of LL problem constraints. Regarding the connection between this proximal Lagrangian value function and the augmented Lagrangian function of the LL problem, this indeed presents an intriguing avenue for exploration. We intend to investigate this relationship in our future research endeavors.

(2) While other bilevel optimization algorithms employ techniques such as Nesterov's momentum or utilize high-order information of the objective function, the plain and simple gradient descent/ascent algorithm may be slow in practical applications.

$**Reply:**$ In the numerical experiments section, we compare our method against two competitors: AiPOD and E-AiPOD (Xiao et al., 2023b), as well as GAM (Xu & Zhu, 2023). Both of these are bilevel optimization algorithms that leverage the Hessian information from the lower-level objective. Our results demonstrate a significant advantage of our method: it relies solely on gradient information of the lower-level problem. This approach not only simplifies the computational process but also notably enhances the speed, rendering our method considerably faster than the competing algorithms.

(3) Assumption 3.3 (ii) can be quite stringent since the global Lipschitz constant for both $L_{g_1}$ and $L_{g_2}$ have not been determined in advance for many applications.

$**Reply:**$ We appreciate your feedback and understand your concern about Assumption 3.3 (ii). Here are some clarifications:

(i) The Lipschitz continuity of the gradient of the lower-level constraints in Assumption 3.3 (ii) is a common and standard assumption in the context of constrained bi-level optimization. This assumption is similarly employed in recent studies, such as those by Khanduri et al. (2023) and Xiao et al. (2023b).

(ii) Importantly, in practical applications considered in the experiments conducted in Khanduri et al. (2023) and Xiao et al. (2023b), including scenarios like Adversarially Robust Learning and Federated Bilevel Learning, the lower-level constraints are either linear or linearly coupled. This observation holds true for all models assessed in our numerical experiments. In such cases, the global Lipschitz constants for both $L_{g_1}$ and $L_{g_2}$ are equal to zero.

(4) The choice for the parameter $r$ for the truncated proximal Lagrangian value function is not mentioned.

$**Reply:**$
As demonstrated in Theorem A.2, that given a solution $(x^*, y^*, z^*)$ to the reformulation (4), selecting the parameter $r$ to be sufficiently large, specifically $r \ge \|z^*\|_{\infty}$, ensures that $(x^*, y^*, z^*)$ also solves variant (6), Therefore, it is standard to choose a large value for the parameter $r$ in practice.

We sincerely appreciate the time and effort you devoted to reviewing our paper. Your valuable feedback is greatly appreciated, and we would like to clarify some specific points in response.

(1) There are an excessive number of stepsize parameters in use, and it remains uncertain whether the algorithm's performance is significantly affected by the choice of these parameters.

$**Reply:**$ In addition to the step size parameters, our method involves three hyperparameters: $\gamma$, $r$, and $c_k$. The parameters $\gamma$ and $r$ define the truncated proximal Lagrangian value function. Theoretically, the requirements for $\gamma$ and $r$ are modest; $\gamma$ is positive, and $r$ should be large. The penalty parameter, $c_k$, follows a specific selection strategy outlined in Theorem 3.1, namely $c_k = \underline{c}(k+1)^p$ where $p \in (0,1/2)$ and $\underline{c}>0$. Consequently, in practice, typically only the step size parameters require careful tuning.

In our numerical experiments, we analyzed the sensitivity of the parameter $c_k$, with its convergence curve displayed in Figure 2.

Additionally, to assess the sensitivity of the remaining parameters, further numerical experiments were conducted on the LL merely convex synthetic model. We record the time when $\|x^k - x^*\| / \|x^*\| \leq 10^{-2}$ is met by the iterates generated by LV-HBA. The results are as follows:

(5) The proposed methods includes many hyperparameters, making difficult to implement in practice.

$**Reply:**$ We appreciate your feedback and would like to clarify a few points:

In addition to the step size parameters, our method involves three hyperparameters: $\gamma$, $r$, and $c_k$. The parameters $\gamma$ and $r$ define the truncated proximal Lagrangian value function. Theoretically, the requirements for $\gamma$ and $r$ are modest; $\gamma$ is positive, and $r$ should be large. The penalty parameter, $c_k$, follows a specific selection strategy outlined in Theorem 3.1, namely $c_k = \underline{c}(k+1)^p$ where $p \in (0,1/2)$ and $\underline{c}>0$. Consequently, in practice, typically only the step size parameters require careful tuning.

In our numerical experiments, we analyzed the sensitivity of the parameter $c_k$, with its convergence curve displayed in Figure 2.

Additionally, to assess the sensitivity of the remaining parameters, further numerical experiments were conducted on the LL merely convex synthetic model. We record the time when $\|x^k - x^*\| / \|x^*\| \leq 10^{-2}$ is met by the iterates generated by LV-HBA. The results are as follows:

We appreciate your time and effort in reviewing our work and providing constructive feedback. Below, we will address each of your questions with careful consideration.

(1) Can the authors elaborate why there is no need to assume the Lipschitz continuity of the upper level function $F(x,y)$, which is typically necessary in bilevel optimization even the lower function is strongly convex, e.g. Xiao et al. (2023b).

$**Reply:**$ Our approach diverges fundamentally from previous algorithms, such as the one proposed by Xiao et al. (2023b). Specifically, Xiao et al. assume the strong convexity of the lower-level objective with respect to $y$, leading to a unique solution for the lower-level problem, denoted as $y^*(x)$. Their algorithm is designed based on the hyper-gradient of the hyper-objective $F(x, y^*(x))$. The Lipschitz continuity of the upper-level objective $F(x, y)$ is utilized to establish the $L$-smoothness of the hyper-objective.

In contrast, our work does not presume strong convexity of the lower-level objective with respect to $y$. This allows for the possibility of multiple lower-level solutions, and consequently, the hyper-objective framework used by Xiao et al. is inapplicable. Instead of relying on the hyper-objective, our paper introduces an innovative single-level reformulation for constrained bilevel optimization. This reformulation translates the problem into an equivalent single-level optimization problem with a smooth constraint. We then develop a gradient-type method to address this reformulation. Consequently, our theoretical analysis requires only that $F(x,y)$ be $L_F$-smooth, as detailed in Assumption 3.1, without necessitating the Lipschitz continuity of $F(x, y)$.

(2) On page 6, the sentences after Assumption 3.2 say $f$ is $\rho_f$-weakly convex on $X\times Y$ with $\rho_f\geq0$, which is potentially being smaller than $L_f$. Can you provide the exact form of or show the case of $\rho_f$ being smaller for some specific application? Does that mean we can only suppose $\rho_f=L_f$ in general?

$**Reply:**$ A typical instance occurs when $f$ is convex over the domain $X \times Y$. In such scenarios, $\rho_f$ equals $0$, which is less than $L_f$. This property appears in bilevel optimization problems related to hyperparameter selection, where $f$ often exhibits convexity. For detailed examples, refer to the following works:

Lucy L Gao, Jane J. Ye, Haian Yin, Shangzhi Zeng, and Jin Zhang. Value function based difference-of-convex algorithm for bilevel hyperparameter selection problems. In ICML, 2022.

Jane J. Ye, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. Difference of convex algorithms for bilevel programs with applications in hyperparameter selection. Mathematical Programming, 198(2):1583–1616, 2023.

(3) Theorem A.1 says reformulation (4) is equivalent to constrained BLO problem (1). In the proof of Theorem A.1, it only illustrates that the feasible points of (4) and (1) are equivalent. It is unclear why this means the formulations (4) and (1) and are also equivalent. Can we conclude the optimal solution of (4) and (1) are equivalent?

$**Reply:**$ In addition to the equivalence of feasible points between formulation (4) and (1), they share identical objectives, denoted as $F(x,y)$. Consequently, both (4) and (1) have identical optimal solutions, applicable in both global and local contexts.

(4) In reformulation (5), how to choose the parameter $r$?

$**Reply:**$ As demonstrated in Theorem A.2, that given a solution $(x^*, y^*, z^*)$ to the reformulation (4), selecting the parameter $r$ to be sufficiently large, specifically $r \ge \|z^*\|_{\infty}$, ensures that $(x^*, y^*, z^*)$ also solves variant (6). Therefore, it is standard to choose a large value for the parameter $r$ in practice.