提出可证明收敛的随机双层优化框架，统一处理各类估计器。
A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimization
- 将无偏与有偏随机估计器整合到单循环框架中，支持独立插拔。
- 理论证明其样本复杂度达最优，与单层优化相当。
- 适合研究双层优化复杂度或需要高效实现的算法开发者。
双层优化因其广泛的应用和先进的分层优化能力，在机器学习领域受到广泛关注。本文提出一种名为PnPBO的即插即用框架，用于开发和分析随机双层优化方法。该框架将现代无偏与有偏随机估计器整合进[9]提出的单循环双层优化框架，并进行了若干改进。在实现中，不同变量的随机估计器可独立插入，使用无偏估计器时对上层变量引入移动平均技术。理论分析方面，我们为PnPBO提供了统一的收敛性与复杂度分析，证明在该框架内采用多种随机估计器（包括PAGE、ZeroSARAH及混合策略）可达到最优样本复杂度，与单层优化相当。这解决了双层优化是否具有与单层优化相同最优复杂度这一开放问题。最后，我们在多个基准问题上实证验证了该框架的有效性，确认了理论结果。
原文摘要 · Abstract (English)
Bilevel optimization has recently attracted significant attention in machine learning due to its wide range of applications and advanced hierarchical optimization capabilities. In this paper, we propose a plug-and-play framework, named PnPBO, for developing and analyzing stochastic bilevel optimization methods. This framework integrates both modern unbiased and biased stochastic estimators into the single-loop bilevel optimization framework introduced in [9], with several improvements. In the implementation of PnPBO, all stochastic estimators for different variables can be independently incorporated, and an additional moving average technique is applied when using an unbiased estimator for the upper-level variable. In the theoretical analysis, we provide a unified convergence and complexity analysis for PnPBO, demonstrating that the adaptation of various stochastic estimators (including PAGE, ZeroSARAH, and mixed strategies) within the PnPBO framework achieves optimal sample complexity, comparable to that of single-level optimization. This resolves the open question of whether the optimal complexity bounds for solving bilevel optimization are identical to those for single-level optimization. Finally, we empirically validate our framework, demonstrating its effectiveness on several benchmark problems and confirming our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。