Double Momentum Method for Lower-Level Constrained Bilevel Optimization

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

Q1: It is not clear why is differentiable (e.g., in Lemma 5) and how Assumption 3 works.

A1: We acknowledge that the assumptions made in our study might have been overly stringent, potentially affecting the applicability of our research. The reason for employing these assumptions was to simplify the problem and facilitate theoretical analysis. However, we recognize that these strong assumptions may pose limitations in specific contexts. We have modified Assumption 3 in our new version as follows,

Assumption 3. a) If projection operator has a closed-form solution and $z^\*=y^\*(x)-\eta \nabla_y g(x,y^\*(x))$ is not on the boundary of the constraint, then $P_Y(z^*)$ is continuously differentiable in a neighborhood of $z^*$. In addition, in the neighborhood of $z^*$, $P_Y(z^*)$ has Lipschitz continuous gradient with constant $L$. b) $y^\*(x)$ is continuously differentiable on a neighborhood of $x$.

In many complicated machine learning problems, the probability that $z^*$ falls exactly on the constraint boundary is very low. $z^*$ primarily reside either within or outside the boundary, i.e., a) the constraint is not active and $\nabla_y g(x,y^*)=0$; b) $y^*$ is on the boundary and $||\nabla_y g(x,y^*)||>0$. In these two cases, the projection operator could be differentiable in the neighborhood of $z^*$, since we have the closed form of the projection operator and $z^*$ is not on the nonsmooth point.

This assumption is used in [1,2] and [1,2] use this assumption derive the hypergradient (6). Even [1,2] assume $y^*(x)$ and $\mathcal{P}_ {\mathcal{Y}}(z^*)$ are differentiable in a small neighborhood, [1,2] cannot give a convergence analysis. Because they need $||\nabla \mathcal{P}_ {\mathcal{Y}}(z_1^*)-\nabla \mathcal{P}_ {\mathcal{Y}}(z_2^*)||\leq L_ P||z_1^*-z_2^*||$, which is not satisfied. Using the new Assumption 3, we can obtain the gradient of $F$ and ignore the non-differentiable point.

Most importantly, the main purpose and contribution of our paper is to propose a single-loop method with convergence analysis based on [1,2], instead of proposing a new method to calculate the hypergradient. Therefore, even if the hypothesis is relatively strong, we believe that the proposal of this method is still meaningful.

Q2: Assumption 4 is also strange to me. More discussions are needed for this kind of boundedness assumption.

A2: For the hypergradient estimation $\nabla f_{\delta}(x,y)$, we have

|| \nabla f_ {\delta}(x,y)|| \ \leq || \nabla_x f(x,y)||+ \eta ||\nabla_ {xy}^ 2 g(x,y) || \cdot||\nabla\mathcal{P}_ {\mathcal{Y}\delta}(z)^ {\top}||\cdot ||\sum_ {i=0}^ {Q-1}\left((I_ {d_2}-\eta\nabla_ {yy}^2 g(x,y))\nabla\mathcal{P}_ {\mathcal{Y}\delta}(z)^{\top}\right)^i||\cdot||\nabla_yf(x,y)||\ =C_{fx}+\eta C_{gxy}C_{fy}\sum_ {i=0}^ {Q-1}||I_ {d_2}-\eta\nabla_ {yy}^ 2g(x,y)||^i\ \leq C_ {fx}+\dfrac{C_ {gxy}C_ {fy}}{\mu_ g}

Q3: Why is the convergence rate only related to $d_2$ but not $d_1$?

A3: Since we use the zeroth order method to approximate the Jacobian matrix of the projection operator, the Lipschitz constant and variance of the approximation of the hypergradient is related to $d_2$. In addition, from our analysis, we can find that the convergence rate highly depends on these constants which make the convergence rate related to $d_2$. However, these constant does not affect these constants in the approximation of the hypergradient and therefore the convergence rate is not related to $d_1$.

Q4: Are the lower-level constraints active at the solution returned by the proposed algorithm?

A4: Since the dimension of the lower-level variable is relatively large and the constraint parameter $r=1$ is relatively small, using gradient update in $y$ will easily make $y$ get out of the constraint and lead to the projection on the boundary of the constraints. This makes the lower-level constraints active at the solution return by our method. We can easily check the constraint at the end of our algorithm.

[1] Blondel M, Berthet Q, Cuturi M, et al. Efficient and modular implicit differentiation[J]. Advances in neural information processing systems, 2022, 35: 5230-5242. [2] Bertrand Q, Klopfenstein Q, Massias M, et al. Implicit differentiation for fast hyperparameter selection in non-smooth convex learning[J]. The Journal of Machine Learning Research, 2022, 23(1): 6680-6722. [3] Guo Z, Xu Y, Yin W, et al. On stochastic moving-average estimators for non-convex optimization. ArXiv e-prints[J]. arXiv preprint arXiv:2104.14840, 2021. [4] Shi W, Gao H, Gu B. Gradient-Free Method for Heavily Constrained Nonconvex Optimization[C]//International Conference on Machine Learning. PMLR, 2022: 19935-19955. [5] Guo Z, Xu Y, Yin W, et al. A novel convergence analysis for algorithms of the adam family and beyond[J]. arXiv preprint arXiv:2104.14840, 2021.

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

Q1: The authors are encouraged to discuss the reason why DMLCBO does not achieve $\tilde{O}(\epsilon^{-3})$ and the theoretical technique difference between DMLCBO and SUSTAIN[1] and MRBO[2].

A1: Your comments are greatly appreciated. SUSTAIN[1] and MRBO[2] using the Variance Reduction methods, i.e., STORM and SPIDER, both on the gradient estimation of $x$ and $y$. These methods need stochastic gradient to be Lipschitz continuous. However, this condition is not satisfied in our method. Therefore, we can only use the traditional moving average method which leads to a different convergence rate. Similar results can be found (i.e., $\tilde{\mathcal{O}}(\epsilon^{-4})$) in [3,4] if the stochastic gradient is Lipschitz continuous.

Q2: The author only shows the results of DMLCBO in early time, it will be more informative to provide results in the later steps.

A2: We highly value your feedback and comments. Please be aware that we've already included results in subsequent sections within our appendix. We extended the iteration count of our method to 100,000 to illustrate its convergence performance. Thank you for your consideration!

Q3: DMLCBO exhibits higher variance compared with other baselines in MNIST datasets. A3: Your comments are greatly appreciated. In our method, we use the zeroth order method which may have a large variance. This makes the poison data points found by our methods have high variance in different turns. And MNIST is a simple dataset and easily to be attacked which will increase the variance in the poison data points. Finally, these variances will highly affect the retrained model and lead to a large variance in the test accuracy.

[1] A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum

[2] Provably Faster Algorithms for Bilevel Optimization

[3] Dagréou M, Ablin P, Vaiter S, et al. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms[J].

[4] Chen X, Xiao T, Balasubramanian K. Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions[J].

We sincerely appreciate the time and effort you dedicated to reviewing our paper, and we are thankful for your constructive comments. In the sections below, we address each of the questions you raised.

Q1: Assumption 3 is restrictive to satisfy.

A1: We acknowledge that the assumptions made in our study might have been overly stringent, potentially affecting the applicability of our research. The reason for employing these assumptions was to simplify the problem and facilitate theoretical analysis. However, we recognize that these strong assumptions may pose limitations in specific contexts. We have modified Assumption 3 in our new version as follows,

Assumption 3. a) If projection operator has a closed-form solution and $z^\*=y^\*(x)-\eta \nabla_y g(x,y^\*(x))$ is not on the boundary of the constraint, then $P_Y(z^*)$ is continuously differentiable in a neighborhood of $z^*$. In addition, in the neighborhood of $z^*$, $P_Y(z^*)$ has Lipschitz continuous gradient with constant $L$. b) $y^\*(x)$ is continuously differentiable on a neighborhood of $x$.

In many complicated machine learning problems, the probability that $z^*$ falls exactly on the constraint boundary is very low. $z^*$ primarily reside either within or outside the boundary, i.e., a) the constraint is not active and $\nabla_y g(x,y^*)=0$; b) $y^*$ is on the boundary and $||\nabla_y g(x,y^*)||>0$. In these two cases, the projection operator could be differentiable in the neighborhood of $z^*$, since we have the closed form of the projection operator and $z^*$ is not on the nonsmooth point.

This assumption is used in [1,2] and [1,2] use this assumption derive the hypergradient (6). However, these methods do not have the convergence analysis. The main purpose and contribution of our paper is to design a single-loop method with convergence analysis based on [1,2], instead of proposing a new method to calculate the hypergradient. Therefore, even if the hypothesis is relatively strong, we believe that the proposal of our method is still meaningful.

Q2:the algorithm would require a minimum of approximately $\mathcal{O}(d_2^8\epsilon^{-8})$ iterations.

A2: Thank you very much for pointing out our mistake. We have modified the proof in the new version, hope you can check it again.

In our new proof of Theorem 1, we use the following new function,

\Phi_{k+1}\ =\mathbb{E}[F_{\delta}(x_{k+1})+\dfrac{10L_0^a c_l}{\tau\mu_g c_u}||y_{k+1}-y^*(x_{k+1})||^2 + c_l(|w_{k+1}-\bar{\nabla} f_{\delta}(x_{k+1},y_{k+1})-R_{k+1}|^2\ +|\nabla_y g(x_{k+1},y_{k+1})-v_{k+1}|^2)]

where $G=\dfrac{\Phi_1-\Phi^*}{\gamma c_l}+\dfrac{17t}{4K^2}(m+K)^{1/2}+\dfrac{4}{3tK^2}(m+K)^{3/2}+(m\sigma_{f}^2(d_2))t^2\ln (m+K)$. Then, setting $a=0$, we have $\sqrt{G}=\tilde{\mathcal{O}}(\sqrt{d_ 2})$. Let $\delta=\mathcal{O}(\epsilon d_2^ {-3/2})$, $r$ randomly sampled from $\{0,1,\cdots,K\}$, we have $\mathbb{E}[\dfrac{1}{2}\mathcal{M}_ r]=\dfrac{1}{K}\sum_ {k=1}^ K\mathbb{E}[\dfrac{1}{2}\mathcal{M}_k]=\tilde{\mathcal{O}}(\dfrac{\sqrt{d_2}}{ K^{1/4}})\leq \epsilon$. Therefore, we have $K=\tilde{\mathcal{O}}(\dfrac{d_2^2}{ \epsilon^{4}})$. This is the first method with convergence analysis for LCBO with general constraints, which directly solves the BO problem. Comparatively, in [6], for the single-level nonsmooth problem, the authors derived an iteration number of $\mathcal{O}(d^{3/2}\delta^{-1}\epsilon^{-4})$. This outcome demonstrates that, even within the LCBO context, our method achieves results akin to those in the single-level problem setting."

Q3: What measures can be taken to verify that Assumption 4 is satisfied, or are there specific checkable sufficient conditions to ensure its validity?

A3: For the hypergradient estimation $\nabla f_{\delta}(x,y)$, we have

|| \nabla f_ {\delta}(x,y)|| \ \leq || \nabla_x f(x,y)||+ \eta ||\nabla_ {xy}^ 2 g(x,y) || \cdot||\nabla\mathcal{P}_ {\mathcal{Y}\delta}(z)^ {\top}||\cdot ||\sum_ {i=0}^ {Q-1}\left((I_ {d_2}-\eta\nabla_ {yy}^2 g(x,y))\nabla\mathcal{P}_ {\mathcal{Y}\delta}(z)^{\top}\right)^i||\cdot||\nabla_yf(x,y)||\ =C_{fx}+\eta C_{gxy}C_{fy}\sum_ {i=0}^ {Q-1}||I_ {d_2}-\eta\nabla_ {yy}^ 2g(x,y)||^i\ \leq C_ {fx}+\dfrac{C_ {gxy}C_ {fy}}{\mu_ g}

We are grateful for your time dedicated to reviewing our paper, as well as your constructive comments. Below we address each question.

Q1: By Remark 2 on page 7, the iteration number $K=\mathcal{O}(\dfrac{d_2^8}{\epsilon^8})$.

A1: Thank you very much for pointing out our mistake. We have modified the proof in the new version, hope you can check it again.

In our new proof of Theorem 1, we use the following new function,

\Phi_{k+1}\ =\mathbb{E}[F_{\delta}(x_{k+1})+\dfrac{10L_0^a c_l}{\tau\mu_g c_u}||y_{k+1}-y^*(x_{k+1})||^2 + c_l(|w_{k+1}-\bar{\nabla} f_{\delta}(x_{k+1},y_{k+1})-R_{k+1}|^2\ +|\nabla_y g(x_{k+1},y_{k+1})-v_{k+1}|^2)]

where $G=\dfrac{\Phi_1-\Phi^*}{\gamma c_l}+\dfrac{17t}{4K^2}(m+K)^{1/2}+\dfrac{4}{3tK^2}(m+K)^{3/2}+(m\sigma_{f}^2(d_2))t^2\ln (m+K)$. Then, setting $a=0$, we have $\sqrt{G}=\tilde{\mathcal{O}}(\sqrt{d_ 2})$. Let $\delta=\mathcal{O}(\epsilon d_2^ {-3/2})$, $r$ randomly sampled from $\{0,1,\cdots,K\}$, we have $\mathbb{E}[\dfrac{1}{2}\mathcal{M}_ r]=\dfrac{1}{K}\sum_ {k=1}^ K\mathbb{E}[\dfrac{1}{2}\mathcal{M}_k]=\tilde{\mathcal{O}}(\dfrac{\sqrt{d_2}}{ K^{1/4}})\leq \epsilon$. Therefore, we have $K=\tilde{\mathcal{O}}(\dfrac{d_2^2}{ \epsilon^{4}})$. This is the first method with convergence analysis for LCBO with general constraints, which directly solves the BO problem. Comparatively, in [13], for the single-level nonsmooth problem, the authors derived an iteration number of $\mathcal{O}(d^{3/2}\delta^{-1}\epsilon^{-4})$. This outcome demonstrates that, even within the LCBO context, our method achieves results akin to those in the single-level problem setting."

Q2: Could you provide some representative class of problems that satisfy Assumption 3? Is Assumption 3 satisfied for all small values of $\eta$?

A2: We acknowledge that the assumptions made in our study might have been overly stringent, potentially affecting the applicability of our research. The reason for employing these assumptions was to simplify the problem and facilitate theoretical analysis. However, we recognize that these strong assumptions may pose limitations in specific contexts. We have modified Assumption 3 in our new version as follows,

Assumption 3. a) If projection operator has a closed-form solution and $z^\*=y^\*(x)-\eta \nabla_y g(x,y^\*(x))$ is not on the boundary of the constraint, then $P_Y(z^*)$ is continuously differentiable in a neighborhood of $z^*$. In addition, in the neighborhood of $z^*$, $P_Y(z^*)$ has Lipschitz continuous gradient with constant $L$. b) $y^\*(x)$ is continuously differentiable on a neighborhood of $x$.

In many complicated machine learning problems, the probability that $z^*$ falls exactly on the constraint boundary is very low. $z^*$ primarily reside either within or outside the boundary, i.e., a) the constraint is not active and $\nabla_y g(x,y^*)=0$; b) $y^*$ is on the boundary and $||\nabla_y g(x,y^*)||>0$. In these two cases, the projection operator could be differentiable in the neighborhood of $z^*$, since we have the closed form of the projection operator and $z^*$ is not on the nonsmooth point.

In addition, this assumption has been used in [4,5] to derive the hypergradient (6). The main contribution of this paper is not to use Assumption 3 to derive the hypergradient. The main purpose and contribution of our paper is to design a single-loop method with convergence analysis based on [4,5]. Therefore, even if the hypothesis is relatively strong, we believe that the proposal of our method is still meaningful. Specifically, we propose a single loop method for the LCBO and our method achieves convergence results akin to that in the single-level problem setting.