A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima
This addresses a critical bottleneck in machine learning for tasks requiring bilevel optimization with non-unique inner solutions, offering a more general and efficient solution.
The paper tackles the challenge of bilevel optimization with multiple inner minima, which is common in applications like hyperparameter optimization and meta-learning, by proposing a primal-dual algorithm (PDBO) that achieves a non-asymptotic convergence guarantee, the first such result for this problem.
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.