Rethinking Moreau Envelope for Nonconvex Bi-Level Optimization: A Single-loop and Hessian-free Solution Strategy

We sincerely appreciate the time and effort you dedicated to reviewing our work. Your constructive comments are much appreciated, and we would like to address each of the questions you raised below.

(1) Although the assumptions are indeed weaker than previous works, the convergence measure is also different from many previous works, so the results may not be directly comparable.

Reply: We appreciate your comment. In the realm of nonconvex-nonconvex BLO, we recognize that various works adopt distinct stationary measures. This diversity is acknowledged in our Table 1, stating, "Different methods utilize distinct stationary measures, precluding direct complexity comparisons."

It is important to note that, traditionally, the hypergradient of the hyperobjective has been the preferred convergence measure in much of the existing literature. However, in our work, given the weaker assumptions we employ, the existence of the hypergradient is not always guaranteed.

While acknowledging that comparing methods based on different stationary measures may lack full rigor, we wish to highlight our achievement in developing a non-asymptotic convergence analysis for our proposed method under these more lenient assumptions.

While exploring the connection between various stationary measures for nonconvex-nonconvex BLOs is intriguing, it is not the primary focus of this work.

(2) I think the recent paper which has a strong theoretical guarantee should be cited. Kwon, Jeongyeol, et al. "On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation." arXiv preprint arXiv:2309.01753 (2023).

Reply: Thank you for bringing this latest paper to our attention. We also noticed Kwon et al.'s paper after submitting our own. This paper primarily explores bilevel optimization from the perspective of the hyper-objective, using a penalty value function-based approach. It is relevant to our research and contributes to our understanding of nonconvex-nonconvex BLOs. We will cite it in our revised manuscript.

(3) What does the "Rethinking" in the title mean? Why do we need to rethink? What is the finding after rethinking?

Reply: The Moreau envelope, a widely recognized and frequently employed technique in single-level optimization problems, has only recently been adapted for bilevel optimization. This novel application was first introduced in the work of Gao et al. (2023) for convex lower-level objectives. In our current study, we expand upon this approach by extending the application from the convex setting, as explored by Gao et al. (2023), to a nonconvex context. Unlike Gao et al. (2023), which focused exclusively on a double-loop scheme, our work leverages the benefits of the Moreau envelope reformulation to propose a single-loop, Hessian-free scheme for BLO.

We appreciate the time you dedicated to reviewing our work and your constructive comments. Below, we would like to provide further clarification.

(1) In the nonconvex case, (4) is only a relaxed version of the original BLO. Is not clear whether the global optimal solutions, local optimal solutions, and stationary points of (4) are related to the original BLO. Hence, I am not sure whether the stationarity measure in this paper is useful.

Reply: We would like to provide further clarification:

Firstly, the equivalence between the Moreau envelope reformulation (4) and the original BLO problem (1) is established in Section 2.1. Specifically, Theorem A.1 demonstrates that the reformulation (4) is equivalent to a specially relaxed version of the BLO problem (5), wherein the lower-level problem is replaced by its stationary points. The alignment of feasible sets in both (5) and (1) occurs when the lower-level problem's solution set aligns with its set of stationary points. Such conditions are met, for example, in scenarios where the lower-level objective is convex in $y$ or is smooth and adheres to the PL condition. Under these circumstances, the feasible regions defined by the reformulation (4) and the original BLO problem are identical, ensuring that their respective global and local optimal solutions concur.

Regarding the stationarity of BLO problems, it is important to note that BLOs do not conform to standard nonlinear programming frameworks, and thus lack a universally accepted stationary condition. To address this, various equivalent reformulations associated with BLOs are explored for defining a suitable stationary condition. In this paper, we consider a novel reformulation (4). While the exploration of different stationary measures for BLOs is indeed a topic of interest, it falls outside the primary scope of our current research.

(2) Assumption 3.2 (ii) appears too technical and artificial. The author does not convince me of its practicability, because the given examples are simple and no theoretical results is ensuring Assumption 3.2 (ii).

Reply: We would like to provide additional clarification regarding Assumption 3.2(ii):

Assumption 3.2(ii) is applicable to a broad spectrum of practical nonsmooth regularizers, many of which are yet to be explored in existing literature.

This assumption is composed of three parts: the weak convexity of $g(x,y)$, the existence and Lipschitz continuity of $\nabla_x g(x,y)$, and the Lipschitz continuity of the proximal operator of $g(x,\cdot)$ with respect to the upper-level variable $x$, as specified in inequality (11). Notably, the first two components – weak convexity and the gradient's Lipschitz property – are generally mild and easily satisfied.

Concerning the third component (condition (11)), when the nonsmooth component of the lower-level objective is independent of the UL variable, exemplified by $g(x,y)=\hat{g}(y)$, the condition is trivially met. As a result, Assumption 3.2(ii) is satisfied by standard convex regularizers such as $g(x,y)=\lambda \|y\|_1$ and $g(x,y)=\lambda \|y\|_2$, where $\lambda>0$. Furthermore, the assumption's requirement for only weak convexity in $g$ means it is also valid for common nonconvex regularizers like the Smoothly Clipped Absolute Deviation (SCAD) and the Minimax Concave Penalty (MCP).

In scenarios where the nonsmooth component of the LL objective is dependent on the upper-level variable, condition (11) remains verifiable and practical. For instance, we studied the $l_1$ regularizer, $g(x,y)= x\| y\|_1$, with treating the regularization parameter as the upper-level variable, in Section A.9 of the Appendix, and demonstrated that $g(x,y)= x\| y\|_1$ meets Assumption 3.2(ii).

In summary, Assumption 3.2(ii) is not only practical but also encompasses a wide range of nonsmooth regularizers not yet fully explored in previous research. The practical examples satisfying Assumption 3.2(ii) are discussed following Assumption 3.2 in our paper.

(3) Do the models in the experiments satisfy the Assumptions previously assumed?

Reply: In the smooth BLO scenario, our Assumptions simplify to both UL and LL objective functions being $L$-smooth. Consequently, it is straightforward to verify that the models in (17), (18), (20)-(23) satisfy the previously assumed Assumptions when both upper-level and lower-level variables are confined within a bounded set because both the UL and LL objectives are smooth.

Turning to the non-smooth BLO scenario, specifically the LL Non-Smooth Case model (19) discussed in Section 4.1. In Appendix A.9, we establish that Assumption 3.2 holds for $g(x,y) = x \| y\|_1$. This verification can imply that the model in (19) satisfies the assumed Assumptions.

Therefore, we can state that all models employed in our experimental studies meet the Assumptions assumed.

We respectfully disagree with Reviewer Qikw'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.

We sincerely appreciate the time and effort you dedicated to reviewing our work and are thankful for your constructive comments. In the following section, we will address each question.

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

Reply: Thank you for your valuable suggestions. Non-smooth and weakly convex functions, like regularization (e.g., $\ell_1$), find extensive use in various machine learning applications. These applications include sparse representation, sparse coding, feature selection, and hyper-parameter optimization. For instance, in the context of hyper-parameter optimization for low-level vision tasks, $\ell_1$ regularization is applied to enforce sparsity in image restoration. Additionally, in data hyper-cleaning, this same regularization technique can help mitigate overfitting in the learning model.

In Appendix A.1, we provide a brief review of recent works on nonsmooth BLO. We appreciate your feedback and plan to incorporate more bilevel optimization examples in the introduction section of the revised manuscript.

(2) In the proposed algorithm 1, there exist five tuning parameters $\alpha_k$, $\beta_k$, $\eta_k$, $\gamma$, $c_k$. Although the authors gave the range of these parameters in the convergence analysis, I still think the choice of these tuning parameters is not easy in practice.

Reply: To explore the sensitivity of these parameters, we conducted extra numerical experiments in the LL Non-Smooth Case, with a dimension of 1000. The table below displays convergence time and steps while altering one parameter, keeping the others constant. It's important to note that the algorithm achieves convergence with various parameter combinations.

(3) From the convergence analysis, I saw that the authors used the condition that $f(x,y)$ is a weakly convex. I suggest that the authors should add this condition in Assumption 3.2 of the paper.

Reply: We appreciate your suggestion. As discussed in the paragraph prior to Section 3.2, the application of the descent lemma allows us to deduce that a function possessing a Lipschitz-continuous gradient is weakly convex. Consequently, Assumption 3.2(i) is sufficient for the weak convexity of the function $f(x, y)$.

(4) The inequality (11) in Assumption 3.2 (ii) is a strict condition ? If not , please give an example.

Reply: We would like to clarify that Assumption 3.2(ii) concerning the nonsmooth component $g(x,y)$ is not restrictive and is applicable to a wide range of practical nonsmooth regularizers, many of which have not been explored in prior research.

In our paper, under Assumption 3.2, we discuss practical instances that fulfill Assumption 3.2(ii). Notably, when the nonsmooth component of the lower-level objective is independent of the upper-level variable, exemplified as $g(x,y)=\hat{g}(y)$, Assumption 3.2(ii) is satisfied for convex regularizers like $g(x,y)=\lambda|y|_1$ and $g(x,y)=\lambda|y|_2$ where $\lambda>0$. Additionally, even for typical nonconvex regularizers such as the Smoothly Clipped Absolute Deviation (SCAD) and the Minimax Concave Penalty (MCP), Assumption 3.2(ii) remains valid.

Furthermore, in cases where the nonsmooth component of the lower-level objective is dependent on the upper-level variable, we investigate a specific example: $g(x,y)= x\|y\|_1$. Here, $g(x,y)$ represents the $l_1$ regularizer, considering the regularization parameter as the upper-level variable. As demonstrated in Section A.9 of the Appendix, $g(x,y)= x\|y\|_1$ also adheres to Assumption 3.2(ii).

Thus, we assert that Assumption 3.2(ii) is a practical and non-restrictive condition, encompassing a broad spectrum of practical scenarios.

(5) 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 suggestion. Please refer to our previous response for addressing your concern.

Thank you for taking the time to read and review our work. We appreciate your feedback and would like to provide further clarification.

(1) The only weakness the reviewer sees is the lack of technical novelty, as the analysis is largely based on previous work utilizing the Moreau envelope for convex low-level objectives (Gao et al., 2023), and other Hessian-free works. As a result, the proposed method seems like an extension / combination of previous methods.

Reply: Our research indeed builds upon existing works, such as the use of the Moreau envelope for convex lower-level objectives (Gao et al., 2023) and other Hessian-free works. However, our contribution goes beyond merely synthesizing these existing approaches, as we introduce several novel elements.

Firstly, while the Moreau envelope reformulation was initially proposed in Gao et al. (2023) with proposing a corresponding double-loop scheme, our work extends this to a non-convex setting and propose a new single-loop algorithm. Our single-loop algorithm's convergence analysis necessitated proving the Lipschitz continuity of the Moreau envelope solution $\theta_{\gamma}^*(x,y) := \mathrm{argmin}_{\theta \in Y} \{ \varphi(x, \theta) + \frac{1}{2\gamma}\|\theta-y\|^2 \}$, particularly challenging in the presence of a nonsmooth component, $g(x,y)$, in the lower-level objective (2). This analysis, detailed in Lemma A.5, represents a significant technical advancement.

Furthermore, while previous Hessian-free approaches for BLO with non-convex lower-level problems, such as those by Ye et al. (2022) and Shen & Chen (2023), depended on the Polyak-Łojasiewicz (PL) condition, our method does not. The Moreau envelope technique does not inherently satisfy the PL condition, prompting us to develop new techniques distinct from previous Hessian-free methods.

Moreover, to the best of our knowledge, no existing Hessian-free algorithms have addressed scenarios where the lower-level problem objective includes a nonsmooth component, as investigated in our work. Our iteration scheme and convergence analysis for managing this nonsmooth component are thus unique contributions to the field of Hessian-free algorithm research.

In summary, our research extends the Moreau envelope-based algorithm from Gao et al. (2023) from a double-loop to a single-loop approach. Additionally, we are the first to explore a Hessian-free algorithm for bilevel optimization problems where the lower-level objective incorporates a nonsmooth component, all without relying on the PL condition.

We are grateful for your dedicated time in reviewing our work and your constructive comments. Below, we address each question.

(1) While the proposed algorithm is clearly defined, authors could do a better job at providing the intuitions: the directions $d_x^k$ and $d_y^k$ are given with little context. The same comment applies to the merit function and Lemma 3.1.

Reply: Thank you for the suggestions. In the initial manuscript, we elucidated that the update scheme for variables $(x, y)$ can be interpreted as an inexact alternating proximal gradient approach, applied to a nonsmooth optimization problem:

$

\min_{(x,y)\in X \times Y} \frac{1}{ c_k}F(x,y) + f(x, y) + g(x,y) - v_\gamma (x,y).

$

Specifically, $d_{x}^k$ approximates the gradient of $\frac{1}{ c_k}F(x,y) + f(x, y) + g(x,y) - v_\gamma (x,y)$ with respect to $x$ at point $(x^k, y^k)$, with $\theta^{k+1}$ as an approximation for $\theta^*_{\gamma}(x^k,y^k)$. Similarly, $d_{y}^k$ approximates the gradient of $\frac{1}{ c_k}F(x,y) + f(x, y) - v_\gamma (x,y)$ with respect to $y$ at $(x^{k+1}, y^k)$, using $\theta^{k+1}$ to approximate $\theta^*_{\gamma}(x^{k+1},y^k)$.

Regarding the merit function $V_k$, employed in convergence analysis and Lemma 3.1, it is defined as the scalar sum of the penalized problem’s objective (12):

$

\phi_{c_k}(x,y) := \frac{1}{ c_k}(F(x,y) - \underline{F}) + f(x, y) + g(x,y) - v_\gamma (x,y),

$

and the proximity of iterate $\theta^k$ to the actual solution defining the Moreau envelope of lower-level problem at iterate $(x^k, y^k)$, i.e., $\mathrm{argmin}_{\theta\in Y} \{\varphi(x^k,\theta)+\frac{1}{2\gamma}\|\theta-y^k\|^2 \}$.

(2) Could you comment on the novelty, is this the first analysis with such a weak set of assumptions? Or I am missing something?

Reply: In this study, we present a novel algorithm for BLO by leveraging the Moreau envelope-based reformulation initially introduced by Gao et al. (2023). To our knowledge, this is the first application of such a reformulation in the design of a single-loop, Hessian-free gradient-based algorithm for BLO with such weak assumptions. Significantly, our algorithm has a non-asymptotic convergence analysis, and can handle lower-level problems with potentially nonconvex and nonsmooth objectives. Notably, this result is achieved without the necessity of the PL condition on the lower-level problem.

(3) Could you give intuitions on the proof? (which is currently 10 pages long in the appendix) and intuitions on the merit function. Maybe the authors could provide a proof sketch

Reply: Intuitions on the merit function $V_k$:

The update scheme for variables $(x, y)$ can be interpreted as an inexact alternating proximal gradient method applied to the penalized problem (12) :

$

\phi_{c_k}(x, y) := \frac{1}{c_k}\big(F(x, y) - \underline{F} \big) + f(x, y) + g(x, y) - v_\gamma(x, y).

$

Consequently, we anticipate a decreasing value of $\phi_{c_k}(x^k, y^k)$ for the iterates $(x^k, y^k)$.

Furthermore, the update of variable $\theta$ aligns precisely with a single proximal gradient step to the problem defining the Moreau envelope $v_{\gamma}(x,y) :=\inf_{\theta \in Y} \{ \varphi(x, \theta) + \frac{1}{2\gamma}\|\theta-y\|^2 \}$. This alignment leads us to expect that the iterate $\theta^k$ will converge towards the solution of the Moreau envelope at $(x^k, y^k)$, specifically $\mathrm{argmin}_{\theta \in Y} \{ \varphi(x^k, \theta) + \frac{1}{2\gamma}|\theta - y^k|^2 \}$.

Building on these insights into the update schemes for $(x, y)$ and $\theta$, we examine the merit function $V_k$ defined as the sum of the objective value of the penalized problem (12), $\phi_{c_k}(x, y)$, and the distance between the iterate $\theta^k$ and the optimal solution $\theta_{\gamma}^*(x^k, y^k)$ for the Moreau envelope of lower-level problem at $(x^k, y^k)$.

Proof Sketch of non-asymptotic convergence result:

The proof of Theorem 3.1, which establishes the non-asymptotic convergence, fundamentally relies on the monotonically decreasing property of the merit function $V_k$, as delineated in Lemma 3.1. We succinctly outline the pivotal steps leading to this lemma.

Step 1: We first consider the Moreau envelope $v_{\gamma}(x,y)$, focusing on two of its critical properties: its weak convexity (referenced in Lemma A.1) and the associated gradient formulas (outlined in Lemma A.2). These properties enable us to derive an upper bound for the descent of the objective value of the penalized problem (12), $\phi_{c_k}(x, y)$ with incorporating the error term $\left(\frac{\alpha_k}{2} (L_f + L_g)^2 + \frac{\beta_k}{\gamma^2} \right) \left\| \theta^{k+1} - \theta_{\gamma}^*(x^k,y^{k}) \right\|^2$, as formulated in Equation (35) in Lemma A.7.

Step 2: The subsequent step involves leveraging the Lipschitz continuity of the Moreau envelope solution $\theta_{\gamma}^*(x,y)$ (as per Lemma A.5) along with the contraction properties of $\theta^k$ towards this solution (discussed in Lemma A.6). This approach is instrumental in controlling the aforementioned error term $\left\| \theta^{k+1} - \theta_{\gamma}^*(x^k,y^{k}) \right\|^2$ as presented in Equation (35).

Ultimately, these steps culminate in confirming the monotonically decreasing nature of the merit function $V_k$ as in Lemma 3.1.