  Bilevel optimization has found extensive applications in modern machine
learning problems such as hyperparameter optimization, neural architecture
search, meta-learning, etc. While bilevel problems with a unique inner minimal
point (e.g., where the inner function is strongly convex) are well understood,
such a problem with multiple inner minimal points remains to be challenging and
open. Existing algorithms designed for such a problem were applicable to
restricted situations and do not come with a full guarantee of convergence. In
this paper, we adopt a reformulation of bilevel optimization to constrained
optimization, and solve the problem via a primal-dual bilevel optimization
(PDBO) algorithm. PDBO not only addresses the multiple inner minima challenge,
but also features fully first-order efficiency without involving second-order
Hessian and Jacobian computations, as opposed to most existing gradient-based
bilevel algorithms. We further characterize the convergence rate of PDBO, which
serves as the first known non-asymptotic convergence guarantee for bilevel
optimization with multiple inner minima. Our experiments demonstrate desired
performance of the proposed approach.
