A projection-free method for solving convex bilevel optimization problems

• 成果类型: Article
• 署名作者: Giang-Tran, Khanh-Hung; Ho-Nguyen, Nam; Lee, Dabeen
• 署名单位: University of Sydney; Cornell University; Korea Advanced Institute of Science & Technology (KAIST)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02157-1
• 发表日期: 2025
• 页码: 907-940
• 关键词: 1st-order method

摘要

When faced with multiple minima of an inner-level convex optimization problem, the convex bilevel optimization problem selects an optimal solution which also minimizes an auxiliary outer-level convex objective of interest. Bilevel optimization requires a different approach compared to single-level optimization problems since the set of minimizers for the inner-level objective is not given explicitly. In this paper, we propose a new projection-free conditional gradient method for convex bilevel optimization which requires only a linear optimization oracle over the base domain. We establish O(t-1/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(t<^>{-1/2})$$\end{document} convergence rate guarantees for our method in terms of both inner- and outer-level objectives, and demonstrate how additional assumptions such as quadratic growth and strong convexity result in accelerated rates of up to O(t-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(t<^>{-1})$$\end{document} and O(t-2/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(t<^>{-2/3})$$\end{document} for inner- and outer-levels respectively. Lastly, we conduct a numerical study to demonstrate the performance of our method.