Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917826144501760 |
|---|---|
| author | Chen, Pengyu Shi, Xu Jiang, Rujun Wang, Jiulin |
| author_facet | Chen, Pengyu Shi, Xu Jiang, Rujun Wang, Jiulin |
| contents | This paper investigates simple bilevel optimization problems where we minimize an upper-level objective over the optimal solution set of a convex lower-level objective. Existing methods for such problems either only guarantee asymptotic convergence, have slow sublinear rates, or require strong assumptions. To address these challenges, we propose a penalization framework that delineates the relationship between approximate solutions of the original problem and its reformulated counterparts. This framework accommodates varying assumptions regarding smoothness and convexity, enabling the application of specific methods with different complexity results. Specifically, when both upper- and lower-level objectives are composite convex functions, under an $α$-H{ö}lderian error bound condition and certain mild assumptions, our algorithm attains an $(ε,ε^β)$-optimal solution of the original problem for any $β> 0$ within $\mathcal{O}\left(\sqrt{{1}/{ε^{\max\{α,β\}}}}\right)$ iterations. The result can be improved further if the smooth part of the upper-level objective is strongly convex. We also establish complexity results when the upper- and lower-level objectives are general nonsmooth functions. Numerical experiments demonstrate the effectiveness of our algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02155 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds Chen, Pengyu Shi, Xu Jiang, Rujun Wang, Jiulin Optimization and Control This paper investigates simple bilevel optimization problems where we minimize an upper-level objective over the optimal solution set of a convex lower-level objective. Existing methods for such problems either only guarantee asymptotic convergence, have slow sublinear rates, or require strong assumptions. To address these challenges, we propose a penalization framework that delineates the relationship between approximate solutions of the original problem and its reformulated counterparts. This framework accommodates varying assumptions regarding smoothness and convexity, enabling the application of specific methods with different complexity results. Specifically, when both upper- and lower-level objectives are composite convex functions, under an $α$-H{ö}lderian error bound condition and certain mild assumptions, our algorithm attains an $(ε,ε^β)$-optimal solution of the original problem for any $β> 0$ within $\mathcal{O}\left(\sqrt{{1}/{ε^{\max\{α,β\}}}}\right)$ iterations. The result can be improved further if the smooth part of the upper-level objective is strongly convex. We also establish complexity results when the upper- and lower-level objectives are general nonsmooth functions. Numerical experiments demonstrate the effectiveness of our algorithms. |
| title | Penalty-based Methods for Simple Bilevel Optimization under Hölderian Error Bounds |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2402.02155 |