An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization

In this paper, we focus on simple bilevel optimization problems, where we minimize a convex smooth objective function over the optimal solution set of another convex smooth constrained optimization problem. We present a novel bilevel optimization method that locally approximates the solution set of the lower-level problem using a cutting plane approach and employs an accelerated gradient-based update to reduce the upper-level objective function over the approximated solution set. We measure the performance of our method in terms of suboptimality and infeasibility errors and provide non-asymptotic convergence guarantees for both error criteria. Specifically, when the feasible set is compact, we show that our method requires at most $\mathcal{O}(\max\{1/\sqrt{\epsilon_{f}}, 1/\epsilon_g\})$ iterations to find a solution that is $\epsilon_f$-suboptimal and $\epsilon_g$-infeasible. Moreover, under the additional assumption that the lower-level objective satisfies the $r$-th H\"olderian error bound, we show that our method achieves an iteration complexity of $\mathcal{O}(\max\{\epsilon_{f}^{-\frac{2r-1}{2r}},\epsilon_{g}^{-\frac{2r-1}{2r}}\})$, which matches the optimal complexity of single-level convex constrained optimization when $r=1$.

Paper

Similar papers

Peer review

Reviewer fv8w6/10 · confidence 3/52024-06-24

Summary

This work proposes a novel optimization algorithm with improved iteration complexity for convex smooth simple bilevel optimization, and demonstrates its faster convergence using experiments.

Strengths

The presentation is very clear. The literature review looks comprehensive. The algorithm and complexity results look reasonable.

Weaknesses

This work focuses on simple bilevel optimization with both levels being convex and under deterministic setting (with access to full gradients instead of stochastic gradients), so the scope is not wide. Also, as shown in Table 1, the complexity results outperform existing ones only a little since the complexity order is the same as [8] for $r=1$, and the complexity dependence on $\epsilon_g^{-\frac{2r-1}{2r}}$ is worse than $\epsilon_g^{-0.5}$ in [16].

Questions

(1) In line 27, you may write down the math formulation for ``more general settings with parameterized lower-level problems'', or refer this formulation to appendix. (2) How did you obtain Eq. (5), the condition about $g_k$? How to guarantee Eq. (5) in implementation with unknown $g^*$, $x^*$, $L_g$? (3) Does Lemma 4.3 require Assumption 4.1? If yes, add Assumption 4.1 to Lemma 4.3.

Rating

6

Confidence

3

Soundness

3

Presentation

4

Contribution

2

Limitations

In the checklist, the authors mention their limitation of compact domain assumption. There is no societal impact of this theoretical work.

Reviewer fv8w2024-08-08

Reviewer fv8w's further query on Q2

Hello, authors. For Q2, does $g_k$ denote the function value from the k-th iteration of the Nesterov's gradient method on $g$? {$g_k$} is input of Algorithms 1 and 2. Could you remove that input and give the procedure of obtaining $g_k$ in the algorithm body part? Reviewer fv8w

Authorsrebuttal2024-08-09

Thank you for the follow-up questions! **Q. For Q2, does $g_k$ denote the function value from the k-th iteration of the Nesterov's gradient method on $g$? $\\{g_k\\}$ is input of Algorithms 1 and 2. Could you remove that input and give the procedure of obtaining $g_k$ in the algorithm body part?** **A.** The reviewer is correct: the function value of the $k$-th iteration of the Nesterov accelerated gradient method on $g$ is denoted by $g_k$. However, this is not the only possible choice. In fact, any $\\{g_k\\}$ satisfying Eq. (5) can also be used as an input of our algorithms. As you mentioned, this input can be removed. Instead, we could obtain the $g_k$ at the beginning of the $k$-th iteration in our algorithm body part and use it to construct our approximated feasible set $\mathcal{X}_{k}$. We will add an instantiation of our algorithm with Nesterov accelerated gradient iterates to the paper, which will be included in the appendix. To clarify, there are multiple choices for the sequence $g_k$. For instance, one could consider a constant sequence where $g_k$ is set to the function value of the last iterate of AGD for all $k$. This choice has the benefit of shaving a logarithmic factor from the convergence rate, as discussed in Remark 4.2.

Reviewer fv8w2024-08-09

The answer to Q2 is clear now.

Thanks authors. The answer to Q2 is clear now. Reviewer fv8w

Reviewer 1z4b6/10 · confidence 3/52024-06-30

Summary

The paper works on the problem of simple convex smooth bilevel optimisation, where ''simple'' means single-variable. The paper achieves the optimal rate for this problem by a combination of Nesterov's acceleration and Jiang-Abolfazli-Mokhtari-Hamedani's cutting-plane method.

Strengths

STRENGTHS. 1. The paper achieves an optimal rate for an important problem class. 2. The paper is very well-written.

Weaknesses

-

Questions

QUESTIONS. What limitations do the authors anticipate in extending this technique (acceleration + cutting-plane) to the non-simple case (i.e., when you have an additional variable $y$ in the upper level objective, defined as the optimizer of a parametrized lower-level problem).

Rating

6

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

N/A since it's a theory paper

Reviewer B2N78/10 · confidence 4/52024-07-09

Summary

The paper introduces a new algorithm called AGM-BiO (Accelerated Gradient Method for Bilevel Optimization) for solving simple bilevel optimization problems where both the upper and lower level objectives are convex and smooth.

Strengths

1. The paper is well-written and easy to follow. The assumptions are clearly stated. The dependence of the convergence rates on everything seems to be explicitly written out. 2. The proposed algorithm seems to be easy to implement, and it achieves the best-known complexity bounds for both suboptimality and infeasibility in the considered settings. 3. Experiments are conducted to validate the strength of the proposed algorithm.

Weaknesses

You provide a modified algorithm (Algorithm 2) that could potentially handle this composite structure. In line 629-line 631 you mention that you can derive identical complexity results for Algorithm 2 in either the compact domain setting or with the Hölderian error bounds on g. I guess formally stating the convergence result in a theorem would strengthen the paper and provide a clear reference point for readers interested in the composite case.

Questions

-

Rating

8

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

Reviewer R6Rr6/10 · confidence 4/52024-07-12

Summary

This work proposes an accelerated method to solve convex simple bilevel problems, with the author providing both theoretical and numerical guarantees of the algorithm's convergence.

Strengths

- This work makes a theoretical contribution to the convergence analysis, and the algorithm demonstrates an advanced convergence rate under the Hölderian error bound. - The analysis are detailed and concrete. The whole work is easy to follow.

Weaknesses

Since the main techniques in this work, such as the accelerated gradient method and the cutting plane approach, have already been studied, the contribution of the proposed methods is incremental, and the convergence rate may not be difficult to prove based on existing studies.

Questions

- What is the convergence rate without using the accelerated gradient method, relying only on the projection onto the cutting plane? - Since the accelerated gradient method has been well studied recently, what is the unique challenge of applying it to simple bilevel problems? - Will this algorithm demonstrate any advantage in convergence without the assumption of the Hölderian error bound? - How do you find a feasible $X_k$​ in practice? Is an additional loop required to achieve this?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

No Limitation

Authorsrebuttal2024-08-09

Thank you for your response and advocating for the acceptance of our paper!

Reviewer R6Rr2024-08-12

Thanks for the authors' response. My concerns and questions are solved so I will raise my score to 6. I am still curious about why the non-accelerated algorithm fails to provide any convergence guarantee for the lower-level objective.

Authorsrebuttal2024-08-12

Thank you for the response. We're glad your questions and concerns have been addressed! Regarding your further query, specifically, the non-accelerated version of our algorithm follows the update rule $x_{k+1} = \Pi_{X_k}(x_k - \eta_k \nabla f(x_k))$, where the set $X_k$ is similarly constructed from a cutting plane as $X_k = \\\{z \in Z: g(x_k) + \langle \nabla g(x_k), z-x_k \rangle \leq g_k \\\}$. To upper bound the lower-level objective, we can apply a similar analysis as in our Lemma A.1, leading to:$$g(x_{k+1}) \leq g(x_k) + \langle \nabla g(x_k), x_{k+1} - x_k\rangle+ \frac{L_g}{2}\\|x_{k+1} - x_k\\|^2 \leq g_k + \frac{L_g}{2}\\|x_{k+1} - x_k\\|^2,$$where the first inequality used the $L_g$-smoothness of $g$, and the second inequality follows from the fact that $x_{k+1} \in X_k$. However, the main challenge is controlling $\\|x_{k+1} - x_k\\|^2$ (see also Remark 4.1 for a related issue in our accelerated methods). If we follow the same strategy as in Theorem 4.1 and upper bound $\\|x_{k+1} - x_k\\|^2 \leq D^2$ by the compactness of $Z$, this results in $g(x_{k+1}) \leq g_k + \frac{L_g}{2}D^2$, which fails to provide a convergence rate for the lower-level objective. Therefore, it appears that acceleration is crucial to achieve the $O(1/k)$ rate for the lower-level objective reported in Theorem 4.1. That said, we should clarify that this does not rule out the possibility of proving a convergence rate for the lower-level objective under the standard assumptions, though this appears non-trivial and would require a different analysis from the one presented in our paper. Thank you for your question, and we will further explore this topic in future research.

Program Chairsdecision2024-09-25

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC