On Penalty-based Bilevel Gradient Descent Method

Han Shen, Tianyi Chen
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:30992-31015, 2023.

Abstract

Bilevel optimization enjoys a wide range of applications in hyper-parameter optimization, meta-learning and reinforcement learning. However, bilevel problems are difficult to solve and 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 algorithm and establish its finite-time convergence for the constrained bilevel problem without lower-level strong convexity. The experimental results showcase the efficiency of the proposed algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-shen23c, title = {On Penalty-based Bilevel Gradient Descent Method}, author = {Shen, Han and Chen, Tianyi}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {30992--31015}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/shen23c/shen23c.pdf}, url = {https://proceedings.mlr.press/v202/shen23c.html}, abstract = {Bilevel optimization enjoys a wide range of applications in hyper-parameter optimization, meta-learning and reinforcement learning. However, bilevel problems are difficult to solve and 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 algorithm and establish its finite-time convergence for the constrained bilevel problem without lower-level strong convexity. The experimental results showcase the efficiency of the proposed algorithm.} }
Endnote
%0 Conference Paper %T On Penalty-based Bilevel Gradient Descent Method %A Han Shen %A Tianyi Chen %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-shen23c %I PMLR %P 30992--31015 %U https://proceedings.mlr.press/v202/shen23c.html %V 202 %X Bilevel optimization enjoys a wide range of applications in hyper-parameter optimization, meta-learning and reinforcement learning. However, bilevel problems are difficult to solve and 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 algorithm and establish its finite-time convergence for the constrained bilevel problem without lower-level strong convexity. The experimental results showcase the efficiency of the proposed algorithm.
APA
Shen, H. & Chen, T.. (2023). On Penalty-based Bilevel Gradient Descent Method. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:30992-31015 Available from https://proceedings.mlr.press/v202/shen23c.html.

Related Material