ADAPTIVE PROXIMAL GRADIENT METHODS FOR CONVEX BILEVEL OPTIMIZATION

Bilevel optimization is a comprehensive framework that bridges single- and multi-objective optimization. It encompassess many general formulations, such as, but not limited to, standard nonlinear programs. This work demonstrates how elementary proximal gradient iterations can be used to solve a wide class of convex bilevel optimization problems without involving subroutines. Compared to and improving upon existing methods, ours (1) can handle a much wider class of problems, including both constraints and nonsmooth terms, (2) does not require strong convexity or Lipschitz smoothness assumptions, and (3) provides a systematic adaptive stepsize selection strategy with no need of function evaluations. A linesearch-free variant is also proposed that eliminates wasteful backtracking trials at the sole expense of cost evaluations.