Functionally Constrained Algorithm Solves Convex Simple Bilevel Problem

Abstract

This paper studies simple bilevel problems, where a convex upper-level function is minimized over the optimal solutions of a convex lower-level problem. We first show the fundamental difficulty of simple bilevel problems, that the approximate optimal value of such problems is not obtainable by first-order zero-respecting algorithms. Then we follow recent works to pursue the weak approximate solutions. For this goal, we propose a novel method by reformulating them into functionally constrained problems. Our method achieves near-optimal rates for both smooth and nonsmooth problems. To the best of our knowledge, this is the first near-optimal algorithm that works under standard assumptions of smoothness or Lipschitz continuity for the objective functions.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Zhang et al. "Functionally Constrained Algorithm Solves Convex Simple Bilevel Problem." Neural Information Processing Systems, 2024. doi:10.52202/079017-1836

Markdown

[Zhang et al. "Functionally Constrained Algorithm Solves Convex Simple Bilevel Problem." Neural Information Processing Systems, 2024.](https://mlanthology.org/neurips/2024/zhang2024neurips-functionally/) doi:10.52202/079017-1836

BibTeX

@inproceedings{zhang2024neurips-functionally,
  title     = {{Functionally Constrained Algorithm Solves Convex Simple Bilevel Problem}},
  author    = {Zhang, Huaqing and Chen, Lesi and Xu, Jing and Zhang, Jingzhao},
  booktitle = {Neural Information Processing Systems},
  year      = {2024},
  doi       = {10.52202/079017-1836},
  url       = {https://mlanthology.org/neurips/2024/zhang2024neurips-functionally/}
}