Near-Optimal Algorithms for Convex Simple Bilevel Optimization under Weak Assumptions
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_ | 1866913935445196800 |
|---|---|
| author | Jiang, Rujun Shi, Xu Song, Weizheng Wang, Jiulin |
| author_facet | Jiang, Rujun Shi, Xu Song, Weizheng Wang, Jiulin |
| contents | This paper considers the simple bilevel optimization (SBO) problem, which minimizes a composite convex function over the optimal solution set of another composite convex minimization problem. We first show that this bilevel problem is equivalent to finding the left-most root of a nonlinear equation. Based on this and a novel dual approach for solving the subproblem in each iteration, we efficiently obtain an $(ε, ε)$-optimal solution through the bisection and Newton methods. The proposed methods achieve near-optimal operation complexity of ${\tilde{\mathcal{O}}(\sqrt{1/ε})}$ under mild assumptions, aligning with the lower complexity bounds of the first-order methods in SBO with both level objectives being smooth convex and unconstrained composite convex optimization when ignoring logarithmic terms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08948 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Algorithms for Convex Simple Bilevel Optimization under Weak Assumptions Jiang, Rujun Shi, Xu Song, Weizheng Wang, Jiulin Optimization and Control This paper considers the simple bilevel optimization (SBO) problem, which minimizes a composite convex function over the optimal solution set of another composite convex minimization problem. We first show that this bilevel problem is equivalent to finding the left-most root of a nonlinear equation. Based on this and a novel dual approach for solving the subproblem in each iteration, we efficiently obtain an $(ε, ε)$-optimal solution through the bisection and Newton methods. The proposed methods achieve near-optimal operation complexity of ${\tilde{\mathcal{O}}(\sqrt{1/ε})}$ under mild assumptions, aligning with the lower complexity bounds of the first-order methods in SBO with both level objectives being smooth convex and unconstrained composite convex optimization when ignoring logarithmic terms. |
| title | Near-Optimal Algorithms for Convex Simple Bilevel Optimization under Weak Assumptions |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2409.08948 |