Functionally Constrained Algorithm Solves Convex Simple Bilevel Problems
This addresses a fundamental challenge in optimization for researchers and practitioners, providing the first near-optimal algorithm under standard smoothness or Lipschitz continuity assumptions, though it is incremental in building on recent works for weak approximate solutions.
The paper tackles the difficulty of solving convex simple bilevel problems, where approximate optimal values are not obtainable by first-order zero-respecting algorithms, and proposes a novel method that reformulates them into functionally constrained problems, achieving near-optimal rates for both smooth and nonsmooth cases.
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.