提出更高效算法，解决高光滑性双层优化问题
Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimization
- 用高阶差分近似超梯度，提升收敛速度
- 理论证明复杂度达近最优的 $\tilde{\mathcal{O}}(p ε^{-4-p/2})$
- 适用于低误差需求的高光滑性优化场景
本文研究上层非凸、下层强凸的随机双层优化问题中寻找 $ε$-平稳点的复杂度。已有方法 F²SA 在一阶光滑情况下达到 $\tilde{\mathcal{O}}(ε^{-6})$ 的上界，慢于单层问题的最优下界 $Ω(ε^{-4})$。本文通过将 F²SA 重述为前向差分近似超梯度，提出一类新方法 F²SA-$p$，利用 $p$ 阶有限差分近似超梯度，使 $p$ 阶光滑问题的上界降至 $\tilde{\mathcal{O}}(p ε^{-4-p/2})$。进一步证明，当下层变量满足高阶光滑性时，$Ω(ε^{-4})$ 下界依然成立，表明当 $p = Ω( \log ε^{-1} / \log \log ε^{-1})$ 时，F²SA-$p$ 的上界近乎最优。
原文摘要 · Abstract (English)
This paper studies the complexity of finding an $ε$-stationary point for stochastic bilevel optimization when the upper-level problem is nonconvex and the lower-level problem is strongly convex. Recent work proposed the first-order method, F${}^2$SA, achieving the $\tilde{\mathcal{O}}(ε^{-6})$ upper complexity bound for first-order smooth problems. This is slower than the optimal $Ω(ε^{-4})$ complexity lower bound in its single-level counterpart. In this work, we show that faster rates are achievable for higher-order smooth problems. We first reformulate F$^2$SA as approximating the hyper-gradient with a forward difference. Based on this observation, we propose a class of methods F${}^2$SA-$p$ that uses $p$th-order finite difference for hyper-gradient approximation and improves the upper bound to $\tilde{\mathcal{O}}(p ε^{-4-p/2})$ for $p$th-order smooth problems. Finally, we demonstrate that the $Ω(ε^{-4})$ lower bound also holds for stochastic bilevel problems when the high-order smoothness holds for the lower-level variable, indicating that the upper bound of F${}^2$SA-$p$ is nearly optimal in the highly smooth region $p = Ω( \log ε^{-1} / \log \log ε^{-1})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。