A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem

Ruichen Jiang, Nazanin Abolfazli, Aryan Mokhtari, Erfan Yazdandoost Hamedani

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)10305-10323
Number of pages19
JournalProceedings of Machine Learning Research
Volume206
StatePublished - 2023
Event26th International Conference on Artificial Intelligence and Statistics, AISTATS 2023 - Valencia, Spain
Duration: Apr 25 2023Apr 27 2023

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem'. Together they form a unique fingerprint.

Cite this