TY - JOUR
T1 - A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem
AU - Jiang, Ruichen
AU - Abolfazli, Nazanin
AU - Mokhtari, Aryan
AU - Hamedani, Erfan Yazdandoost
N1 - Funding Information: The research of R. Jiang and A. Mokhtari is supported in part by NSF Grants 2127697, 2019844, and 2112471, ARO Grant W911NF2110226, the Machine Learning Lab (MLL) at UT Austin, and the Wireless Networking and Communications Group (WNCG) Industrial Affiliates Program. The research of N. Abolfazli and E. Yazdandoost Hamedani is supported by NSF Grant 2127696. Publisher Copyright: Copyright © 2023 by the author(s)
PY - 2023
Y1 - 2023
N2 - In this paper, we study a class of bilevel optimization problems, also known as simple bilevel optimization, where we minimize a smooth objective function over the optimal solution set of another convex constrained optimization problem. Several iterative methods have been developed for tackling this class of problems. Alas, their convergence guarantees are either asymptotic for the upper-level objective, or the convergence rates are slow and sub-optimal. To address this issue, in this paper, we introduce a novel bilevel optimization method that locally approximates the solution set of the lower-level problem via a cutting plane and then runs a conditional gradient update to decrease the upper-level objective. When the upper-level objective is convex, we show that our method requires O(max{1/ϵf, 1/ϵg}) iterations to find a solution that is ϵf-optimal for the upper-level objective and ϵg-optimal for the lower-level objective. Moreover, when the upper-level objective is non-convex, our method requires O(max{1/ϵ2f, 1/(ϵfϵg)}) iterations to find an (ϵf, ϵg)-optimal solution. We also prove stronger convergence guarantees under the Hölderian error bound assumption on the lower-level problem. To the best of our knowledge, our method achieves the best-known iteration complexity for the considered class of bilevel problems.
AB - In this paper, we study a class of bilevel optimization problems, also known as simple bilevel optimization, where we minimize a smooth objective function over the optimal solution set of another convex constrained optimization problem. Several iterative methods have been developed for tackling this class of problems. Alas, their convergence guarantees are either asymptotic for the upper-level objective, or the convergence rates are slow and sub-optimal. To address this issue, in this paper, we introduce a novel bilevel optimization method that locally approximates the solution set of the lower-level problem via a cutting plane and then runs a conditional gradient update to decrease the upper-level objective. When the upper-level objective is convex, we show that our method requires O(max{1/ϵf, 1/ϵg}) iterations to find a solution that is ϵf-optimal for the upper-level objective and ϵg-optimal for the lower-level objective. Moreover, when the upper-level objective is non-convex, our method requires O(max{1/ϵ2f, 1/(ϵfϵg)}) iterations to find an (ϵf, ϵg)-optimal solution. We also prove stronger convergence guarantees under the Hölderian error bound assumption on the lower-level problem. To the best of our knowledge, our method achieves the best-known iteration complexity for the considered class of bilevel problems.
UR - http://www.scopus.com/inward/record.url?scp=85161050650&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85161050650&partnerID=8YFLogxK
M3 - Conference article
SN - 2640-3498
VL - 206
SP - 10305
EP - 10323
JO - Proceedings of Machine Learning Research
JF - Proceedings of Machine Learning Research
T2 - 26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023
Y2 - 25 April 2023 through 27 April 2023
ER -