提出新方法解决凸双层优化难题，首次实现近最优解率。
Functionally Constrained Algorithm Solves Convex Simple Bilevel Problems
- 将双层问题重构成函数约束问题，突破传统算法局限
- 在光滑与非光滑情况下均达到近最优收敛速率
- 适用于标准平滑或Lipschitz连续假设下的优化场景
本文研究简单双层优化问题，即在下层凸问题最优解集上最小化上层凸目标函数。首先揭示了此类问题的根本难点：一阶零尊重算法无法获得近似最优值。随后借鉴近期工作，转向弱近似解的求解。为此，提出一种新方法，将问题重构为函数约束形式。该方法在光滑与非光滑情形下均实现了近最优收敛速率。据我们所知，这是首个在标准光滑性或Lipschitz连续性假设下实现近最优率的算法。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。