An Accelerated Gradient Method for Simple Bilevel Optimization with
  Convex Lower-level Problem
Jincheng Cao Ruichen Jiang Erfan Yazdandoost Hamedani Aryan Mokhtari
In this paper, we focus on simple bilevel optimization problems, where we
minimize a convex smooth objective function over the optimal solution set of
another convex smooth constrained optimization problem. We present a novel
bilevel optimization method that locally approximates the solution set of the
lower-level problem using a cutting plane approach and employs an accelerated
gradient-based update to reduce the upper-level objective function over the
approximated solution set. We measure the performance of our method in terms of
suboptimality and infeasibility errors and provide non-asymptotic convergence
guarantees for both error criteria. Specifically, when the feasible set is
compact, we show that our method requires at most
$\mathcal{O}(\max\{1/\sqrt{\epsilon_{f}}, 1/\epsilon_g\})$ iterations to find a
solution that is $\epsilon_f$-suboptimal and $\epsilon_g$-infeasible. Moreover,
under the additional assumption that the lower-level objective satisfies the
$r$-th H\"olderian error bound, we show that our method achieves an iteration
complexity of
$\mathcal{O}(\max\{\epsilon_{f}^{-\frac{2r-1}{2r}},\epsilon_{g}^{-\frac{2r-1}{2r}}\})$,
which matches the optimal complexity of single-level convex constrained
optimization when $r=1$.