arXiv：cs.LG（机器学习，全量分类）· Linxuan Pan, Junchi Yang·· 15 小时前AI 评分37
MRT-FD：随机一阶预言机下最优双层优化方法
Optimal Stochastic Bilevel Optimization with First-Order Oracles
AI 导读
研究提出 MRT-FD，一种单循环一阶方法，在随机一阶预言机下求解非凸-强凸双层优化问题，同时跟踪上层变量、下层解及隐式微分产生的辅助响应。对任意固定有限光滑阶 p≥1，MRT-FD 以 O(ε^(-4-2/p)) 次随机梯度查询找到 ε-稳定点，并证明匹配的 Ω(ε^(-4-2/p)) 预言机下界，从而在该设定下对每个固定 p 达到最优复杂度。
正文
Abstract:We study nonconvex--strongly-convex bilevel optimization under a stochastic first-order oracle. We introduce MRT-FD, a single-loop first-order method that simultaneously tracks the upper-level variable, the lower-level solution, and the auxiliary response arising from implicit differentiation of the hyperobjective. MRT-FD performs one update of each variable per iteration and approximates the second-order derivative actions using order-$p$ finite differences. For any fixed finite smoothness order $p\ge1$ in the lower-level variable, MRT-FD finds an $\varepsilon$-stationary point using $\mathcal{O}(\varepsilon^{-4-2/p})$ stochastic gradient queries. We also prove a matching $\Omega(\varepsilon^{-4-2/p})$ oracle lower bound. The lower-bound construction starts from a hard nonconvex minimization chain with a stronger stochastic oracle, and lifts it to a bilevel problem through a sinusoidal coupling with a scalar lower-level variable. Consequently, the dependence on $\varepsilon$ is optimal for every fixed finite $p$, closing the upper--lower complexity gap in this stochastic first-order oracle setting.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.01843 [math.OC] |
| (or arXiv:2610.01843v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.01843 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Linxuan Pan [view email]
[v1]
Thu, 1 Oct 2026 15:11:24 UTC (52 KB)
来源：arXiv：cs.LG（机器学习，全量分类） · arxiv.org