A Primal-Dual Approach to Bilevel Optimization with Multiple Inner Minima
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Bilevel OptimizationHyperparameter OptimizationMeta-LearningNeural Architecture SearchSimilar Papers 제목 키워드 기반
SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization
This paper studies decentralized bilevel optimization, in which multiple agents collaborate to solve problems involving nested optimization structures with neighborhood communications. Most existing literature primarily …
Bilevel OptimizationA Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints
Interest in bilevel optimization has grown in recent years, partially due to its applications to tackle challenging machine-learning problems. Several exciting recent works have been centered around developing efficient …
Bilevel OptimizationSample Complexity Analysis for Constrained Bilevel Reinforcement Learning
Several important problem settings within the literature of reinforcement learning (RL), such as meta-learning, hierarchical learning, and RL from human feedback (RL-HF), can be modelled as bilevel RL problems. A lot has…
Reinforcement LearningA Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse
In this paper, we propose a new Hessian inverse free Fully Single Loop Algorithm (FSLA) for bilevel optimization problems. Classic algorithms for bilevel optimization admit a double loop structure which is computationall…
Bilevel OptimizationBilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
Bilevel optimization has become a powerful framework in various machine learning applications including meta-learning, hyperparameter optimization, and network architecture search. There are generally two classes of bile…
BIG-bench Machine LearningBilevel OptimizationHyperparameter OptimizationMeta-Learning