A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization

Wei Shen, Jiawei Zhang, Minhui Huang, Cong Shen · 2025

Read A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization by Wei Shen, Jiawei Zhang, Minhui Huang, Cong Shen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24710.txt.

Introduction

Wei Shen, Jiawei Zhang, Minhui Huang, and Cong Shen tackle two level math tasks where the low level has straight line limits. Such tasks show up when a top choice must sit on top of a best low choice. The top goal can be rough, and its slope needs costly second order terms.

The team recasts the task as one level with a fine and a boost term, and shows the new form tracks the old one in worth and slope. Their one loop method then uses just first order slopes. Its step count beats past two loop ways, and tests match the claim.

Catalog record

CREATORWei Shen, Jiawei Zhang, Minhui Huang, Cong Shen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE133 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-24710

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization Wei Shen, Jiawei Zhang, Minhui Huang, Cong Shen 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 ) ) O(\epsilon^{-3}\log(\epsilon^{-1})) to O ⁡ ( ϵ − 3 ) O(\epsilon^{-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 . 1 Introduction In recent years, bilevel optimization (BLO) has gained significant popularity for addressing a wide range of modern machine learning problems, such as hyperparameter optimization ( pedregosa2016hyperparameter ; franceschi2018bilevel ; mackay2019self ) , data hypercleaning ( shaban2019truncated ) , meta learning ( rajeswaran2019meta ; ji2020convergence ) , reinforcement learning ( sutton2018reinforcement ; hong2023two ) and neural architecture search ( liu2018darts ; liang2019darts+ ) ; see survey papers ( zhang2024introduction ; liu2021investigating ; sinha2017review ) for additional discussions. While numerous works for unconstrained BLO problems have been proposed ( ghadimi2018approximation ; liu2020generic ; ji2021bilevel ; dagreou2022framework ; hong2023two ; kwon2023fully ) , studies focusing on constrained BLO problems are relatively limited. In this paper, we consider the following BLO problem where the lower-level (LL) problem has coupled constraints : \displaystyle\min_{x\in\mathcal{X}}\quad\Phi(x)\triangleq f(x,y^{*}(x)) (1) \displaystyle\text{s.t. }\quad y^{*}(x)\in\arg\min_{y\in\mathcal{Y}(x)}g(x,y). The upper-level (UL) objective function f:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\to\mathbb{R} and the lower-level objective function g:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\to\mathbb{R} are continuously differentiable. Moreover, we assume that g(x,y) is strongly convex with respect to y . The feasible sets are defined as \mathcal{X}=\mathbb{R}^{d_{x}},\mathcal{Y}(x)=\{\,y\in\mathbb{R}^{d_{y}}\mid h(x,y)\leq 0\,\} where h:\mathbb{R}^{d_{x}}\times\mathbb{R}^{d_{y}}\to\mathbb{R}^{d_{h}} . For this setting, we develop a single loop algorithm for the special case h(x,y)=Bx+Ay-b , where B\in\mathbb{R}^{d_{h}\times d_{x}} and A\in\mathbb{R}^{d_{h}\times d_{y}} . This special class of constrained BLO problems covers a wide class of applications, including distributed optimization ( yang2022decentralized ) , hyperparameter optimization of constrained learning problems ( xu2023efficient ) and adversarial training ( zhang2022revisiting ) and draw significant attentions ( tsaknakis2022implicit ; khanduri2023linearly ; kornowski2024first ) . A popular approach for solving unconstrained BLO is implicit gradient descent ( ghadimi2018approximation ; ji2021bilevel ; ji2022will ; chen2022single ; khanduri2021near ) . For constrained BLO, several studies have extended this approach to accommodate different constraint settings ( tsaknakis2022implicit ; khanduri2023linearly ; xu2023efficient ; xiao2023alternating ) . However, these implicit gradient-based methods in constrained BLO necessitate computing the Hessian matrix of the lower-level problem ( tsaknakis2022implicit ; khanduri2023linearly ; xu2023efficient ; xiao2023alternating ) . The potential computational challenges associated with the Hessian matrix limit their practical applicability for large-scale problems. Recently, some first-order methods ( kwon2023penalty ; yao2024constrained ; yao2024overcoming ; jiang2024primal ; kornowski2024first ) have been proposed for addressing constrained BLO problems. Most of those works considered transforming the original problem ( 1 ) into a single-level one and trying to find the stationary points of the reformulated problem. For example, yao2024constrained ; yao2024overcoming reformulated the original problem into some approximated functions and proposed single-loop algorithms for finding the stationary point of the approximated problem. However, neither yao2024constrained nor yao2024overcoming establishes clear relationships between the stationary points of their approximated problems and the original one. Works most closely related to ours are those by kwon2023penalty and jiang2024primal , both of which reformulated the problem ( 1 ) as \displaystyle\min_{x\in\mathcal{X},y\in\mathcal{Y}(x)}f(x,y)\quad\text{s.t. }g(x,y)-\min_{z\in\mathcal{Y}(x)}g(x,z)\leq 0, (2) and considered optimizing the following function with a penalty parameter \delta : \displaystyle\min_{x\in\mathcal{X}}[\Phi_{\delta}(x)\triangleq\min_{y\in\mathcal{Y}(x)}\max_{z\in\mathcal{Y}(x)}\Phi_{\delta}(x,y,z)] (3) where \Phi_{\delta}(x,y,z)=f(x,y)+\frac{1}{\delta}[g(x,y)-g(x,z)] . Based on this reformulation, kwon2023penalty proposed algorithms for solving BLO with LL constraints y\in\mathcal{Y} and jiang2024primal proposed algorithms for solving coupled LL constraints \mathcal{Y}(x)=\{y\in\mathbb{R}^{d_{y}}|h(x,y)\leq 0\} . However, kwon2023penalty only considered the LL constraints \mathcal{Y} that are independent of x and their methods require projection oracle to \mathcal{Y} at each iteration. Algorithms in jiang2024primal require complex double or triple loops, resulting in sub-optimal convergence rates and difficult implementation. Moreover, the connection between the stationary point of the reformulated function \Phi_{\delta} and the original hyper-objective \Phi is not discussed in ( kwon2023penalty ; jiang2024primal ) for coupled constraints \mathcal{Y}(x) . To address these limitations, in this paper, we establish a rigorous theoretical justification for this reformulation ( 3 ) and propose a single-loop Hessian-free algorithm for the linearly constrained cases. Our main contributions can be summarized as follows. • We establish a rigorous theoretical connection between the reformulated function \Phi_{\delta} and the original hyper-objective \Phi by proving the closeness of their values and derivatives under coupled constraints \mathcal{Y}(x)=\{y\in\mathbb{R}^{d_{y}}|h(x,y)\leq 0\} with certain assumptions, which provides strong justifications for the reformulation ( 3 ). • Based on this reformulation and equipped with augmented Lagrangian methods, we proposed SFLCB, a single-loop, first-order algorithm for linearly constrained bilevel optimization problem. and provide rigorous analyses of its non-asymptotic convergence rates, achieving an improvement in the convergence rate from O(\epsilon^{-3}\log(\epsilon^{-1})) to O(\epsilon^{-3}) compared to prior works (See Table 1 for a more comprehensive comparison of our work with previous studies). The simple single-loop structure also makes our algorithm easier to implement in practice compared to jiang2024primal . • Our experiments on hyperparameter optimization in the support vector machine (SVM) and transportation network design problems validate the practical effectiveness and efficiency of the proposed SFLCB algorithm. Table 1 : Comparison of our paper with ( kwon2023penalty ; jiang2024primal ; kornowski2024first ) . More detailed introductions and discussions of other related works can be found in Section 2 . Here, the “Complexity” for ( kwon2023penalty ; jiang2024primal ) and SFLCB means the complexity needed to achieve the \epsilon -stationary point of \Phi_{\delta} ; for ( kornowski2024first ) , it means the complexity needed to achieve the (\delta,\epsilon) -Goldstein stationarity defined in kornowski2024first . Methods LL Constraint Complexity Loops kwon2023penalty y\in\mathcal{Y} , \mathcal{Y} is a convex and compact set O(\epsilon^{-3}\log(\epsilon^{-1})) single/double jiang2024primal h(x,y)\leq 0 , LICQ holds O(\epsilon^{-5}\log(\epsilon^{-1})) triple jiang2024primal B(x)+A(x)y\leq 0 , A(x) is full row rank O(\epsilon^{-3}\log(\epsilon^{-1})) double kornowski2024first Bx+Ay-b\leq 0 , LICQ holds \tilde{O}(d\delta^{-1}\epsilon^{-3}) double kornowski2024first Bx+Ay-b\leq 0 , LICQ holds \tilde{O}(\delta^{-1}\epsilon^{-4}) double SFLCB (ours) Bx+Ay-b\leq 0 , A is full row rank O(\epsilon^{-3}) single SFLCB (ours) Ay\leq 0 , LICQ holds at the initial points O(\epsilon^{-3}) single SFLCB (ours) Ay\leq 0 O(\epsilon^{-4}) single 2 Related works BLO without constraints. One popular approach for solving unconstrained BLO is to use implicit gradient descent methods ( pedregosa2016hyperparameter ) . It is well established that when the LL problem is strongly convex and unconstrained, y^{*}(x)=\mathop{\rm argmin}_{y}g(x,y) exists and is differentiable, and the gradient of the hyper-objective can be calculated by \nabla\Phi(x)=\nabla_{x}f(x,y)+(\nabla y^{*}(x))^{\top}\nabla_{y}f(x,y^{*}(x)) ( ghadimi2018approximation ) . Later works improved the convergence rates and studied the gradient descent methods under various settings ( ji2021bilevel ; ji2022will ; chen2022single ; khanduri2021near ; yang2023accelerating ) . Another popular approach is based on iterative differentiation, which iteratively solves the LL problems and computes \nabla y^{*}(x)

Read the complete text