An Alternating Optimization Method for Bilevel Problems under the Polyak-Łojasiewicz Condition

Bilevel optimization has recently regained interest owing to its applications in emerging machine learning fields such as hyperparameter optimization, metalearning, and reinforcement learning. Recent results have shown that simple alternating (implicit) gradient-based algorithms can match the convergence rate of single-level gradient descent (GD) when addressing bilevel problems with a strongly convex lower-level objective. However, it remains unclear whether this result can be generalized to bilevel problems beyond this basic setting. In this paper, we first introduce a stationary metric for the considered bilevel problems, which generalizes the existing metric, for a nonconvex lower-level objective that satisfies the Polyak-Łojasiewicz (PL) condition. We then propose a Generalized ALternating mEthod for bilevel opTimization (GALET) tailored to BLO with convex PL LL problem and establish that GALET achieves an ϵ-stationary point for the considered problem within Õ(ϵ -1 ) iterations, which matches the iteration complexity of GD for single-level smooth nonconvex problems.