Dynamic FISTA for Convex Composite Bi-Level Optimization
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_ | 1866911001044058112 |
|---|---|
| author | Merchav, Roey Sabach, Shoham Teboulle, Marc |
| author_facet | Merchav, Roey Sabach, Shoham Teboulle, Marc |
| contents | In this paper, we study convex bi-level optimization problems where both the inner and outer levels are given as a composite convex minimization. We propose the Fast Bi-level Proximal Gradient (FBi-PG) algorithm, which can be interpreted as applying FISTA to a dynamic regularized composite objective function. The dynamic nature of the regularization parameters allows to achieve an optimal fast convergence rate of $O(1/k^{2})$ in terms of the inner objective function. This is the fastest known convergence rate under no additional restrictive assumptions. We also show that FBi-PG achieves sub-linear simultaneous rates in terms of both the inner and outer objective functions. Moreover, we show that under an Hölderian type error bound assumption on the inner objective function, the FBi-PG algorithm achieves improved simultaneous rates and converges to an optimal solution of the bi-level optimization problem. Finally, we present numerical experiments demonstrating the performance of the proposed scheme. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_21221 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dynamic FISTA for Convex Composite Bi-Level Optimization Merchav, Roey Sabach, Shoham Teboulle, Marc Optimization and Control 90C25, 65K05 In this paper, we study convex bi-level optimization problems where both the inner and outer levels are given as a composite convex minimization. We propose the Fast Bi-level Proximal Gradient (FBi-PG) algorithm, which can be interpreted as applying FISTA to a dynamic regularized composite objective function. The dynamic nature of the regularization parameters allows to achieve an optimal fast convergence rate of $O(1/k^{2})$ in terms of the inner objective function. This is the fastest known convergence rate under no additional restrictive assumptions. We also show that FBi-PG achieves sub-linear simultaneous rates in terms of both the inner and outer objective functions. Moreover, we show that under an Hölderian type error bound assumption on the inner objective function, the FBi-PG algorithm achieves improved simultaneous rates and converges to an optimal solution of the bi-level optimization problem. Finally, we present numerical experiments demonstrating the performance of the proposed scheme. |
| title | Dynamic FISTA for Convex Composite Bi-Level Optimization |
| topic | Optimization and Control 90C25, 65K05 |
| url | https://arxiv.org/abs/2407.21221 |