An Inexact Conditional Gradient Method for Constrained Bilevel Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916159198068736 |
|---|---|
| author | Abolfazli, Nazanin Jiang, Ruichen Mokhtari, Aryan Hamedani, Erfan Yazdandoost |
| author_facet | Abolfazli, Nazanin Jiang, Ruichen Mokhtari, Aryan Hamedani, Erfan Yazdandoost |
| contents | Bilevel optimization is an important class of optimization problems where one optimization problem is nested within another. While various methods have emerged to address unconstrained general bilevel optimization problems, there has been a noticeable gap in research when it comes to methods tailored for the constrained scenario. The few methods that do accommodate constrained problems, often exhibit slow convergence rates or demand a high computational cost per iteration. To tackle this issue, our paper introduces a novel single-loop projection-free method employing a nested approximation technique. This innovative approach not only boasts an improved per-iteration complexity compared to existing methods but also achieves optimal convergence rate guarantees that match the best-known complexity of projection-free algorithms for solving convex constrained single-level optimization problems. In particular, when the hyper-objective function corresponding to the bilevel problem is convex, our method requires $\tilde{\mathcal{O}}(ε^{-1})$ iterations to find an $ε$-optimal solution. Moreover, when the hyper-objective function is non-convex, our method's complexity for finding an $ε$-stationary point is $\mathcal{O}(ε^{-2})$. To showcase the effectiveness of our approach, we present a series of numerical experiments that highlight its superior performance relative to state-of-the-art methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_02429 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An Inexact Conditional Gradient Method for Constrained Bilevel Optimization Abolfazli, Nazanin Jiang, Ruichen Mokhtari, Aryan Hamedani, Erfan Yazdandoost Optimization and Control Bilevel optimization is an important class of optimization problems where one optimization problem is nested within another. While various methods have emerged to address unconstrained general bilevel optimization problems, there has been a noticeable gap in research when it comes to methods tailored for the constrained scenario. The few methods that do accommodate constrained problems, often exhibit slow convergence rates or demand a high computational cost per iteration. To tackle this issue, our paper introduces a novel single-loop projection-free method employing a nested approximation technique. This innovative approach not only boasts an improved per-iteration complexity compared to existing methods but also achieves optimal convergence rate guarantees that match the best-known complexity of projection-free algorithms for solving convex constrained single-level optimization problems. In particular, when the hyper-objective function corresponding to the bilevel problem is convex, our method requires $\tilde{\mathcal{O}}(ε^{-1})$ iterations to find an $ε$-optimal solution. Moreover, when the hyper-objective function is non-convex, our method's complexity for finding an $ε$-stationary point is $\mathcal{O}(ε^{-2})$. To showcase the effectiveness of our approach, we present a series of numerical experiments that highlight its superior performance relative to state-of-the-art methods. |
| title | An Inexact Conditional Gradient Method for Constrained Bilevel Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2306.02429 |