Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization

arXiv:2405.00914v1 Announce Type: cross
Abstract: This paper presents a new algorithm member for accelerating first-order methods for bilevel optimization, namely the \emph{(Perturbed) Restarted Accelerated Fully First-order methods for Bilevel Approximation}, abbreviated as \texttt{(P)RAF${}^2$BA}. The algorithm leverages \emph{fully} first-order oracles and seeks approximate stationary points in nonconvex-strongly-convex bilevel optimization, enhancing oracle complexity for efficient optimization. Theoretical guarantees for finding approximate first-order stationary points and second-order stationary points at the state-of-the-art query complexities are established, showcasing their effectiveness in solving complex optimization …

abstract algorithm approximation arxiv complexity cs.lg math.oc minimax optimization oracle paper stat.ml the algorithm type