Skip to yearly menu bar Skip to main content


Poster

Fully First-Order Methods for Linearly Constrained Bilevel Optimization

Guy Kornowski · Swati Padmanabhan · Kai Wang · Zhe Zhang · Suvrit Sra

West Ballroom A-D #5802
[ ] [ Project Page ]
Fri 13 Dec 4:30 p.m. PST — 7:30 p.m. PST

Abstract: 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 \textit{constrained} setting remains relatively underexplored. We present fully first-order linearly constrained optimization methods with finite-time hypergradient stationarity guarantees. For linear \textit{equality} constraints, we attain $\epsilon$-stationarity in $\widetilde{O}(\epsilon^{-2})$ gradient oracle calls, which is nearly-optimal. For linear \textit{inequality} constraints, we attain $(\delta,\epsilon)$-Goldstein stationarity in $\widetilde{O}({\delta^{-1} \epsilon^{-4}})$ or $\widetilde{O}(d{\delta^{-1} \epsilon^{-3}})$ gradient oracle calls, where $d$ is the upper-level dimension. Along the way, we develop new nonsmooth nonconvex optimization methods with inexact oracles. Our numerical experiments verify these guarantees.

Live content is unavailable. Log in and register to view live content