Efficiently Escaping Saddle Points in Bilevel Optimization

Understand

Bilevel optimization is one of the fundamental problems in machine learning and optimization.

• Recent theoretical developments in bilevel optimization focus on finding the first-order stationary points for nonconvex-strongly-convex cases.
• In this paper, we analyze algorithms that can escape saddle points in nonconvex-strongly-convex bilevel optimization.
• Specifically, we show that the perturbed approximate implicit differentiation (AID) with a warm start strategy finds $\epsilon$-approximate local minimum of bilevel optimization in $\tilde{O}(\epsilon^{-2})$ iterations with high probability.