Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization

This paper presents a new algorithm member for accelerating first-order methods for bilevel optimization, namely the (Perturbed) Restarted Accelerated Fully First-order methods for Bilevel Approximation, abbreviated as (P)RAF²BA. The algorithm leverages 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 tasks. Empirical studies for real-world problems are provided to further validate the outperformance of our proposed algorithms. The significance of (P)RAF²BA in optimizing nonconvex-strongly-convex bilevel optimization problems is underscored by its state-of-the-art convergence rates and computational efficiency.