On Penalty-based Bilevel Gradient Descent Method
Preprint
Abstract
Bilevel optimization enjoys a wide range of applications in hyper-parameter optimization, meta-learning and reinforcement learning. However, bilevel optimization problems are difficult to solve. Recent progress on scalable bilevel algorithms mainly focuses on bilevel optimization problems where the lower-level objective is either strongly convex or unconstrained. In this work, we tackle the bilevel problem through the lens of the penalty method. We show that under certain conditions, the penalty reformulation recovers the solutions of the original bilevel problem. Further, we propose the penalty-based bilevel gradient descent (PBGD) algorithm and establish its finite-time convergence for the constrained bilevel problem without lower-level strong convexity. Experiments showcase the efficiency of the proposed PBGD algorithm.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problemsJournal of Global Optimization, 2025
- First-Order Penalty Methods for Bilevel OptimizationSIAM Journal on Optimization, 2024
- A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-CriticSIAM Journal on Optimization, 2023
- Loss landscapes and optimization in over-parameterized non-linear systems and neural networksApplied and Computational Harmonic Analysis, 2022
- Investigating Bi-Level Optimization for Learning and Vision From a Unified Perspective: A Survey and BeyondIEEE Transactions on Pattern Analysis and Machine Intelligence, 2021
- A First Order Method for Solving Convex Bilevel Optimization ProblemsSIAM Journal on Optimization, 2017
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimizationMathematical Programming, 2014
- Gradient methods for minimizing composite functionsMathematical Programming, 2012
- Cubic regularization of Newton method and its global performanceMathematical Programming, 2006
- Exact Penalization and Necessary Optimality Conditions for Generalized Bilevel Programming ProblemsSIAM Journal on Optimization, 1997