An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization
<|reference_start|>An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization: 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$.<|reference_end|>
@article{cao2024an,
    title={An Accelerated Gradient Method for Convex Smooth Simple Bilevel
  Optimization},
    author={Jincheng Cao, Ruichen Jiang, Erfan Yazdandoost Hamedani, Aryan
  Mokhtari},
    journal={arXiv preprint arXiv:2402.08097},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08097},
    primaryClass={math.OC cs.LG stat.ML}
}