AdaProx: A Novel Method for Bilevel Optimization under Pessimistic Framework

Ziwei Guan, Daouda Sow, Sen Lin, Yingbin Liang
Conference on Parsimony and Learning, PMLR 280:134-164, 2025.

Abstract

As a powerful framework for various machine learning problems, bilevel optimization has attracted significant attention recently. While many modern gradient-based algorithms have been devised for optimistic bilevel optimization (OBO), pessimistic bilevel optimization (PBO) is much less explored and there is almost no formally designed algorithms for nonlinear PBO with provable convergence guarantee. To fill this gap, we investigate PBO with nonlinear inner- and outer-level objective functions in this work. By leveraging an existing reformulation of PBO into a single-level constrained optimization problem, we propose an Adaptive Proximal (AdaProx) method which features novel designs of adaptive constraint relaxation and accuracy level in order to guarantee an efficient and provable convergence. We further show that AdaProx converges sublinearly to an $\epsilon$-KKT point, and characterize the corresponding computational complexity. Our experiments on an illustrative example and the robust hyper-representation learning problem validate our algorithmic design and theoretical analysis. To the best of our knowledge, this is the first work that develops principled gradient-based algorithms and characterizes the convergence rate for PBO under nonlinear settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v280-guan25a, title = {AdaProx: A Novel Method for Bilevel Optimization under Pessimistic Framework}, author = {Guan, Ziwei and Sow, Daouda and Lin, Sen and Liang, Yingbin}, booktitle = {Conference on Parsimony and Learning}, pages = {134--164}, year = {2025}, editor = {Chen, Beidi and Liu, Shijia and Pilanci, Mert and Su, Weijie and Sulam, Jeremias and Wang, Yuxiang and Zhu, Zhihui}, volume = {280}, series = {Proceedings of Machine Learning Research}, month = {24--27 Mar}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v280/main/assets/guan25a/guan25a.pdf}, url = {https://proceedings.mlr.press/v280/guan25a.html}, abstract = {As a powerful framework for various machine learning problems, bilevel optimization has attracted significant attention recently. While many modern gradient-based algorithms have been devised for optimistic bilevel optimization (OBO), pessimistic bilevel optimization (PBO) is much less explored and there is almost no formally designed algorithms for nonlinear PBO with provable convergence guarantee. To fill this gap, we investigate PBO with nonlinear inner- and outer-level objective functions in this work. By leveraging an existing reformulation of PBO into a single-level constrained optimization problem, we propose an Adaptive Proximal (AdaProx) method which features novel designs of adaptive constraint relaxation and accuracy level in order to guarantee an efficient and provable convergence. We further show that AdaProx converges sublinearly to an $\epsilon$-KKT point, and characterize the corresponding computational complexity. Our experiments on an illustrative example and the robust hyper-representation learning problem validate our algorithmic design and theoretical analysis. To the best of our knowledge, this is the first work that develops principled gradient-based algorithms and characterizes the convergence rate for PBO under nonlinear settings.} }
Endnote
%0 Conference Paper %T AdaProx: A Novel Method for Bilevel Optimization under Pessimistic Framework %A Ziwei Guan %A Daouda Sow %A Sen Lin %A Yingbin Liang %B Conference on Parsimony and Learning %C Proceedings of Machine Learning Research %D 2025 %E Beidi Chen %E Shijia Liu %E Mert Pilanci %E Weijie Su %E Jeremias Sulam %E Yuxiang Wang %E Zhihui Zhu %F pmlr-v280-guan25a %I PMLR %P 134--164 %U https://proceedings.mlr.press/v280/guan25a.html %V 280 %X As a powerful framework for various machine learning problems, bilevel optimization has attracted significant attention recently. While many modern gradient-based algorithms have been devised for optimistic bilevel optimization (OBO), pessimistic bilevel optimization (PBO) is much less explored and there is almost no formally designed algorithms for nonlinear PBO with provable convergence guarantee. To fill this gap, we investigate PBO with nonlinear inner- and outer-level objective functions in this work. By leveraging an existing reformulation of PBO into a single-level constrained optimization problem, we propose an Adaptive Proximal (AdaProx) method which features novel designs of adaptive constraint relaxation and accuracy level in order to guarantee an efficient and provable convergence. We further show that AdaProx converges sublinearly to an $\epsilon$-KKT point, and characterize the corresponding computational complexity. Our experiments on an illustrative example and the robust hyper-representation learning problem validate our algorithmic design and theoretical analysis. To the best of our knowledge, this is the first work that develops principled gradient-based algorithms and characterizes the convergence rate for PBO under nonlinear settings.
APA
Guan, Z., Sow, D., Lin, S. & Liang, Y.. (2025). AdaProx: A Novel Method for Bilevel Optimization under Pessimistic Framework. Conference on Parsimony and Learning, in Proceedings of Machine Learning Research 280:134-164 Available from https://proceedings.mlr.press/v280/guan25a.html.

Related Material