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 14 references indexed in Scilit:
- Inexact bilevel stochastic gradient methods for constrained and unconstrained lower-level problemsJournal of Global Optimization, 2025
- 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
- A General Descent Aggregation Framework for Gradient-Based Bi-Level OptimizationIEEE Transactions on Pattern Analysis and Machine Intelligence, 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
- Efficiency of minimizing compositions of convex functions and smooth mapsMathematical Programming, 2018
- 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