Accelerating Inexact HyperGradient Descent for Bilevel Optimization

Abstract We present a method for solving general nonconvex-strongly-convex bilevel optimization problems. Our method---the Restarted Accelerated HyperGradient Descent (RAHGD) method---finds an ε-first-order stationary point of the objective with O(κ3.25ε-1.75) oracle complexity, where κ is the condition number of the lower-level objective and ε is the desired accuracy. We also propose a perturbed variant of RAHGD for finding an (ε,O(κ2.5√ε\,))-second-order stationary point within the same order of oracle complexity. Our results achieve the best-known theoretical guarantees for finding stationary points in bilevel optimization and also improve upon the existing upper complexity bound for finding second-order stationary points in nonconvex-strongly-concave minimax optimization problems, setting a new state-of-the-art benchmark. Empirical studies are conducted to validate the theoretical results in this paper.