Accelerated Fully First-Order Methods for Bilevel and Minimax Optimization

Abstract

We present in this paper novel accelerated fully first-order methods in Bilevel Optimization (BLO). Firstly, for BLO under the assumption that the lower-level functions admit the typical strong convexity assumption, the (Perturbed) Restarted Accelerated Fully First-order methods for Bilevel Approximation (PRAF^2BA) algorithm leveraging fully first-order oracles is proposed, whereas the algorithm for finding approximate first-order and second-order stationary points with state-of-the-art oracle query complexities in solving complex optimization tasks. Secondly, applying as a special case of BLO the nonconvex-strongly-convex (NCSC) minimax optimization, PRAF^2BA rediscovers perturbed restarted accelerated gradient descent ascent (PRAGDA) that achieves the state-of-the-art complexity for finding approximate second-order stationary points. Additionally, we investigate the challenge of finding stationary points of the hyper-objective function in BLO when lower-level functions lack the typical strong convexity assumption, where we identify several regularity conditions of the lower-level problems that ensure tractability and present hardness results indicating the intractability of BLO for general convex lower-level functions. Under these regularity conditions we propose the Inexact Gradient-Free Method (IGFM), utilizing the Switching Gradient Method (SGM) as an efficient sub-routine to find an approximate stationary point of the hyper-objective in polynomial time. Empirical studies for real-world problems are provided to further validate the outperformance of our proposed algorithms.

Tasks

Reproductions