{"ID":2849279,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.24710","arxiv_id":"2510.24710","title":"A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization","abstract":"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.","short_abstract":"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 refor...","url_abs":"https://arxiv.org/abs/2510.24710","url_pdf":"https://arxiv.org/pdf/2510.24710v3","authors":"[\"Wei Shen\",\"Jiawei Zhang\",\"Minhui Huang\",\"Cong Shen\"]","published":"2025-10-28T17:58:17Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.IT\",\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false,"code_links":[{"ID":607689,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_id":2849279,"paper_url":"https://arxiv.org/abs/2510.24710","paper_title":"A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization","repo_url":"https://github.com/ShenGroup/SFLCB","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}