First-Order Methods for Linearly Constrained Bilevel Optimization
This work addresses a bottleneck in optimization for machine learning and AI by providing efficient algorithms for constrained bilevel problems, though it is incremental as it builds on prior first-order methods for unconstrained cases.
The paper tackles the problem of bilevel optimization with linear constraints, which is computationally challenging due to Hessian computations, by developing first-order methods that avoid these costs. It achieves nearly-optimal convergence rates, such as $\widetilde{O}(\epsilon^{-2})$ for equality constraints and $\widetilde{O}(d\delta^{-1} \epsilon^{-3})$ for inequality constraints, with numerical experiments verifying the results.
Algorithms for bilevel optimization often encounter Hessian computations, which are prohibitive in high dimensions. While recent works offer first-order methods for unconstrained bilevel problems, the constrained setting remains relatively underexplored. We present first-order linearly constrained optimization methods with finite-time hypergradient stationarity guarantees. For linear equality constraints, we attain $ε$-stationarity in $\widetilde{O}(ε^{-2})$ gradient oracle calls, which is nearly-optimal. For linear inequality constraints, we attain $(δ,ε)$-Goldstein stationarity in $\widetilde{O}(d{δ^{-1} ε^{-3}})$ gradient oracle calls, where $d$ is the upper-level dimension. Finally, we obtain for the linear inequality setting dimension-free rates of $\widetilde{O}({δ^{-1} ε^{-4}})$ oracle complexity under the additional assumption of oracle access to the optimal dual variable. Along the way, we develop new nonsmooth nonconvex optimization methods with inexact oracles. We verify these guarantees with preliminary numerical experiments.