A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915774939004928 |
|---|---|
| author | Shen, Wei Zhang, Jiawei Huang, Minhui Shen, Cong |
| author_facet | Shen, Wei Zhang, Jiawei Huang, Minhui Shen, Cong |
| contents | We study bilevel optimization problems where the lower-level problems are strongly convex and have coupled linear constraints. To overcome the potential non-smoothness of the hyper-objective and the computational challenges associated with the Hessian matrix, we utilize penalty and augmented Lagrangian methods to reformulate the original problem as a single-level one. Especially, we establish a strong theoretical connection between the reformulated function and the original hyper-objective by characterizing the closeness of their values and derivatives. Based on this reformulation, we propose a single-loop, first-order algorithm for linearly constrained bilevel optimization (SFLCB). We provide rigorous analyses of its non-asymptotic convergence rates, showing an improvement over prior double-loop algorithms -- form $O(ε^{-3}\log(ε^{-1}))$ to $O(ε^{-3})$. The experiments corroborate our theoretical findings and demonstrate the practical efficiency of the proposed SFLCB algorithm. Simulation code is provided at https://github.com/ShenGroup/SFLCB. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_24710 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization Shen, Wei Zhang, Jiawei Huang, Minhui Shen, Cong Optimization and Control Information Theory Machine Learning We study bilevel optimization problems where the lower-level problems are strongly convex and have coupled linear constraints. To overcome the potential non-smoothness of the hyper-objective and the computational challenges associated with the Hessian matrix, we utilize penalty and augmented Lagrangian methods to reformulate the original problem as a single-level one. Especially, we establish a strong theoretical connection between the reformulated function and the original hyper-objective by characterizing the closeness of their values and derivatives. Based on this reformulation, we propose a single-loop, first-order algorithm for linearly constrained bilevel optimization (SFLCB). We provide rigorous analyses of its non-asymptotic convergence rates, showing an improvement over prior double-loop algorithms -- form $O(ε^{-3}\log(ε^{-1}))$ to $O(ε^{-3})$. The experiments corroborate our theoretical findings and demonstrate the practical efficiency of the proposed SFLCB algorithm. Simulation code is provided at https://github.com/ShenGroup/SFLCB. |
| title | A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization |
| topic | Optimization and Control Information Theory Machine Learning |
| url | https://arxiv.org/abs/2510.24710 |