Overcoming Lower-Level Constraints in Bilevel Optimization: A Novel Approach with Regularized Gap Functions

When and why would constraints in the LL be necessary?

​ a. GAN would not require constraints.

​ b. SVM has unconstrained versions.

​ c. Hyperparameter tuning / data selection can be solved with more naive approach without bilevel problems.

Response:

Thank you for your questions. We appreciate the opportunity to elaborate on the necessity of constraints in the lower-level (LL) of bilevel optimization problems and address the potential computational challenges.

When and Why LL Constraints are Necessary

Practical Scenarios: LL constraints are often required to model real-world restrictions and requirements in various applications. For example, in resource allocation, supply chain optimization, and decision analysis, constraints are used to ensure feasible solutions that meet specific conditions such as budget limits, capacity constraints, or physical boundaries.

Mathematical Model Integrity: In some problems, LL constraints contribute to a more accurate representation of real-world scenarios. Including constraints helps limit the solution space to realistic and valid outcomes, preventing impractical or suboptimal solutions.

Stability and Robustness: LL constraints can provide additional structure to complex optimization problems, including non-convex ones, which enhances solution stability and algorithm robustness. This is particularly beneficial in applications that demand reliable performance under varied conditions.

Addressing the Specific Examples:

a. GANs: While it is true that traditional GANs do not explicitly require LL constraints, there are notable examples where incorporating constraints has shown significant benefits. For instance, WGAN-GP [1] and ConGAN [2] introduce constraints in the form of gradient penalties and capacity constraints, respectively, to improve stability and training performance. These constraints are often integrated through penalty functions, which can complicate the optimization process by requiring careful tuning of penalty factors and potentially reducing model interpretability. Our research aims to provide a more systematic approach to handling these constraints effectively.

[1] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. In NIPS, 2017

[2] Xiaopeng Chao, Jiangzhong Cao, Yuqin Lu, Qingyun Dai, and Shangsong Liang. Constrained generative adversarial networks. Ieee Access, 9:19208–19218, 2021.

b. SVMs: Although there are unconstrained versions of SVMs, constrained SVMs are used in scenarios where additional conditions need to be satisfied for improved robustness and interpretability. For example, constraints may encode prior knowledge about the problem or ensure that the model operates within specific bounds. These constraints can be beneficial in applications where fairness, regulatory compliance, or domain-specific requirements are critical.

c. Hyperparameter Tuning / Data Selection: While more naive approaches may suffice for simple hyperparameter tuning or data selection tasks, bilevel optimization algorithms provide a more efficient and effective framework, especially for complex and high-dimensional problems. Bilevel optimization can handle hierarchical structures where the performance of the upper-level task depends on the optimal solution of the LL problem, resulting in more refined and optimized solutions.

We would like to thank the reviewer for acknowledging the contributions of our work. Below we would like to give some explanations to clarify the concerns.

Some theoretical assumptions are insufficiently justified (i.e. very weak statement), particularly in Remark 2.5, where it’s stated that the existence of a multiplier in Theorem 2.3 “can be guaranteed” under certain constraints qualification conditions like MFCQ. Is the assumption in fact guaranteed when the constraints qualification conditions are satisfied? Or does those conditions directly imply that the assumption is satisfied? Please clarify.

Response:

Yes, the assumption that "a corresponding multiplier of the lower-level problem (2) exists at $(x,y)$" holds when the constraints qualification conditions, including Guignard’s CQ, Linear Independence Constraint Qualification (LICQ), or Mangasarian-Fromovitz Constraint Qualification (MFCQ), are satisfied for the lower-level problem constraints. This is guaranteed by the established theory for the Karush-Kuhn-Tucker (KKT) conditions. Specifically, when the constraints qualification condition is met, the existence of a KKT point for the constrained optimization problem is ensured, and consequently, the existence of a corresponding multiplier is guaranteed.

The update steps in BiC-GAFFA are quite similar to existing constrained optimization reformulation methods, such as primal-dual [1] and dynamic barrier [2] methods. While these approaches have been applied successfully in other constrained settings, the paper does not explain why they are inadequate for the additional lower-level constraint here, suggesting a need for BiC-GAFFA. A discussion on this distinction would help clarify the necessity of more complex methods such as the proposed BiC-GAFFA.

Response:

Thank you for raising this question. We would like to clarify that both [1] and [2], as well as some other methods in the literature, propose approaches based on the value function reformulation of bilevel optimization problems. Specifically, they consider reformulations of the form:

where $v(x) := \inf_{y} \\{f(x, y) \mid g(x, y) \leq 0\\}$. The convergence analysis and theoretical soundness of these single-loop gradient-based methods heavily depend on the smoothness of the value function $v(x)$ of the lower-level problem.

However, when the lower-level problem includes constraints, the smoothness of $v(x)$ is generally not guaranteed. For instance, consider the following example:

In this case, the value function is $v(x) = |x|$, which is not differentiable at $x = 0$. As a result, the value function reformulation of the bilevel optimization problem is not smooth, and the convergence analyses in [1] and [2] do not apply.

To address this challenge, we introduce a new doubly regularized gap function for the constrained lower-level problem. This doubly regularized gap function is smooth, enabling us to propose a smooth, single-level reformulation of the bilevel optimization problem with a constrained lower-level problem. Building on this smooth reformulation, we develop the BiC-GAFFA method, a single-loop gradient-based algorithm, and establish its convergence properties.

Thank you for pointing this out. We will include this discussion in the revised version.

In line 1007, can you provide the specific mathematical format of the functions $\mathcal{L}_{gen/det}$.

Thank you for your feedback. We appreciate your attention to detail. In our experiments, we used the following specific mathematical formats for the loss functions $\mathcal{L}{gen}$ and $\mathcal{L}{det}$:

1. GAN:

2. WGAN:

with a box constraint that $\\|D\\|_ {\infty} \le c_ \mathrm{clip}$.

3. WGAN-GP:

where $\lambda_ {\text{gp}}$ is the parameter of gradient penalty, and $\mathbb{P}_ {\hat{\mathbf{x}}}$ is defined by sampling uniformly along straight lines between pairs of points sampled from the data distribution $\mathbb{P}_ r$ and the generator distribution $\mathbb{P}_ g := \\{G(\mathbb{z}) | \mathbb{z}\in \mathbb{N}\\}$.

4. Con-GAN:

where

5. UGAN:

6. Bi-GAN:

7. Bi-WGAN:

with constraint

where $\mathbb{P}_ {\hat{\mathbf{x}}}$ is defined by sampling uniformly along straight lines between pairs of points sampled from the data distribution $\mathbb{P}_ r$ and the generator distribution $\mathbb{P}_ g := \\{G(\mathbb{z}) | \mathbb{z}\in \mathbb{N}\\}$.

8. Bi-ConGAN:

with constraint

We will incorporate these detailed expressions in the revised manuscript for clarity and completeness.

In the experimental settings, we observe that the step sizes $\alpha_k$ and $\eta_k$ are fixed or vary in a specific form. Are the step sizes related to the specific formulations of different problems?

Response:

Thank you for your question. We appreciate the opportunity to clarify the step size selection in our experimental settings. On one hand, our theoretical convergence analysis indicates that sufficiently small step sizes are adequate to ensure the convergence of our algorithm. To simplify the practical application of our method and reduce the tuning burden, we chose $\alpha_k = \eta_k/10$ as the default step size relationship. This choice was based on its strong empirical performance across various tests, and we recommend it as an initial step size configuration for users. However, it is important to note that this step size relationship is not a strict requirement. Users can adjust $\alpha_k$ and $\eta_k$ according to the specific characteristics and needs of different problems.

Can the conclusion of Lemma 2.1 be stated as "$\mathcal{G}_\gamma (x,y,z)=0$ if and only if $y\in S(x)$ and $z\in M(x,y)$"?

Response:

Yes, the conclusion of Lemma 2.1 can be stated as $\mathcal{G}_ \gamma(x,y,z) = 0$ if and only if $y \in S(x)$ and $z \in \mathcal{M}(x, y)$. This is because $\mathcal{G}_ \gamma(x, y, z) \geq 0$ for any $(x, y, z) \in X \times Y \times \mathbb{R}_ +^p$ (as shown in Lemma 2.1), and thus the constraint $\mathcal{G}_ \gamma(x, y, z) \leq 0$ defines the same feasible set as the constraint $\mathcal{G}_ \gamma(x, y, z) = 0$ on $(x, y, z) \in X \times Y \times \mathbb{R}_ +^p$.

In line 845, the loss function in lower-level problem should be $\mathcal{L}_{tr}$.

Thank you for pointing out this oversight. We have corrected the expression to the following:

We appreciate your attention to this detail.

We would like to thank the reviewer for acknowledging the contributions of our work. Below we would like to give some explanations to clarify the concerns.

From Section 6.2 and A.2.2., we observe that when dealing with nonsmooth problems, such as sparse group lasso and SVM, it is necessary to reformulate them into a smooth form for effective resolution. It may impact the applicability of the algorithms.

Response:

We acknowledge the challenges posed by nonsmooth functions in optimization problems. Addressing these challenges is a valuable direction for future research, and we plan to explore strategies for effectively handling nonsmooth functions in subsequent studies.

While our theoretical convergence guarantees rely on the assumption of smoothness for the functions involved, this does not preclude the application of our method in scenarios where smoothness conditions are not fully satisfied. In practice, for a wide range of real-world applications, automatic differentiation often provides an effective approximation or substitution for subgradients, enabling the computation of update directions to proceed effectively. Developing a rigorous theoretical framework to support these practical extensions is an important area for future work.

By introducing the gap function, the authors have designed a single-loop algorithm. However, the dimensionality of the introduced variables remains the same as that of the original problem, resulting in an increased iteration scale. Compared to LV-HBA proposed in [1], there is no significant improvement in mathematical representation or convergence results.

Response:

We would like to clarify that, compared to the LV-HBA method in [1], the proposed algorithm in this work offers significant advantages. Specifically, it eliminates two key restrictions present in LV-HBA. First, it relaxes the requirement for joint convexity of the lower-level constraint $g(x, y) \leq 0$ with respect to $(x,y)$. Second, it removes the need to compute the projection onto the set $\\{(x, y) \mid g(x, y) \leq 0 \\}$. Instead, the proposed method requires only the convexity of the lower-level constraint $g(x, y) \leq 0$ with respect to the lower-level variable $y$, and does not require the costly projection operation onto the set $\\{(x, y) \mid g(x, y) \leq 0 \\}$. These two improvements significantly broaden the applicability of the proposed method to real-world problems, compared to LV-HBA.

The necessity to control multiple iteration step sizes within the algorithm significantly affects the convergence theory and empirical performance, making them highly dependent on the adjustment of these step size parameters.

Response:

We would like to clarify that our proposed algorithm involves only two step sizes, $\eta_k$ and $\alpha_k$. Regarding the convergence theory, the requirements for these step sizes are relatively mild. Specifically, the convergence results hold as long as the step sizes $\eta_k$ and $\alpha_k$ are chosen to be small constants.

In practical implementations, while step sizes indeed play a critical role in the empirical performance of the algorithm, we have found that initial values of $\alpha_k = 0.0001$ and $\eta_k = 0.001$ typically provide a good starting point. These values can be adjusted based on the specific problem setting to optimize performance. For example, in scenarios with faster or slower convergence behavior, the step sizes can be fine-tuned accordingly to balance convergence speed and algorithmic stability.

Moreover, adaptive step size strategies, such as using techniques inspired by learning rate schedulers or gradient normalization methods, could further enhance practical performance and reduce sensitivity to initial choices.

The convergence results for extending the proposed algorithm to bilevel optimization problems with minimax lower-level problems are lacking, which leads to that Section 5 feels somewhat abrupt overall.

Response:

We would like to clarify that Section 5 is included to highlight the potential of the doubly regularized gap function idea, demonstrating its applicability not only to bilevel optimization problems with constrained lower-level problems, but also to more complex problems such as bilevel optimization with minimax lower-level optimization. The aim was to show that the proposed technique has broader applicability and can lead to a smooth single-level reformulation for minimax bilevel optimization. However, since the primary focus of this paper is on bilevel optimization with constrained lower-level problems, we chose to provide only a brief discussion on the minimax case. A more detailed analysis of bilevel optimization problems with minimax lower-level problems will be explored in future work.

Thanks for your patient response. We have increased the rating to 8. We also looks forward to your more detailed analysis of bilevel optimization problems with minimax lower-level problems to be explored in future work.

“This paper addresses a relaxation ...... independent of the target error $\epsilon$."

Response: We would like to clarify that the choice of $r$ as a constant in the convergence theorem is based on the reasoning presented in Proposition 3.1. Specifically, once $r$ is appropriately selected to be sufficiently large—such that it encompasses at least one Lagrange multiplier $z^*$ of the lower-level problem at the optimal solution point $(x^*, y^*)$, satisfying $\|z^*\|_{\infty} \leq r$ —the optimal solution of the truncated variant (7) also becomes optimal for the original reformulation (6). Therefore, in the convergence theorem, we focus on the truncated variant (7) with this appropriately chosen $r$.

“In Proposition 3.1, it is assumed that the optimal solution $(x^*, y^*, z^*)$ to (6) exists with finite $z^*$. How can this be guaranteed? Additionally, how should r be chosen in practice? Setting $r$ too large may hinder algorithm convergence, while choosing $r$ too small could exclude the optimal point $z^*$, which is unknown."

Response:

To clarify, for any optimal solution $(x^*, y^*, z^*)$ of (6), $z^*$ corresponds to a Lagrange multiplier associated with the lower-level problem at the optimal solution point $(x^*, y^*)$. By definition, such Lagrange multiplier is finite if it exists. Furthermore, the existence of multiplier is guaranteed under standard constraint qualification conditions for the lower-level problem constraints, as discussed in Remark 2.5. We will include additional explanations around Proposition 3.1 in the revised manuscript to make this clearer.

Regarding the selection of the truncation parameter $r$, theoretically, $r$ should be chosen large to ensure it includes at least one feasible Lagrange multiplier $z^*$. In practice, $r$ can be tuned based on problem-specific characteristics or adjusted adaptively during the algorithm’s execution. Specifically, the parameter $r$ can be selected as follows: Initially, a relatively large $r$ can be chosen, and the behavior of $F$, $f$, and $\max(z)$ can be monitored during computations. If the results exhibit stable convergence characteristics, the chosen $r$ can be retained. Conversely, if significant oscillations or instability are observed, $r$ can be adjusted iteratively based on prior observations of $\max(z)$. Furthermore, grid search provides a systematic approach for exploring different $r$ values to identify the optimal balance between convergence stability and computational performance.

Additionally, several concurrent related works are missing: [1]--[2].

[1] A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints. L Jiang, et. al. arXiv:2406.10148.

[2] First-Order Methods for Linearly Constrained Bilevel Optimization. G Kornowski, et.al. arXiv:2406.12771.

Response: We thank the reviewer for pointing out these recent and relevant references. We will include a discussion of these works in the revised manuscript.

In Table 3, the term "Required accuracy" could be replaced with a word like "Time" to clarify the values reported. As it stands, it is unclear whether the numbers in this table represent accuracy or computation time.

Response:

Thank you for your observation regarding Table 3. We appreciate the opportunity to clarify this. The numbers in the table represent the computation time required to achieve the target accuracy, as indicated by the metric EM < 0.5 and EM < 0.1. To avoid any confusion, we agree that changing the column heading from "Required accuracy" to "Time to reach target accuracy" would better reflect the content of the table. We will make this change in the revised manuscript to improve clarity.