提出单循环一阶算法SGHA，高效求解非凸-强凸双层优化问题。
SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization
- 将下层最优性作为约束，构建带正则的对偶形式，用光滑梯度下降上升求解。
- 确定性场景下复杂度为 $O(\barκ_y^5ε^{-2})$，随机场景下为 $O(\barκ_y^{17}ε^{-6})$。
- 首次实现与理论下界匹配的 $ε$-依赖复杂度，适合高精度双层优化任务。
本文研究在仅使用一阶信息的情况下，求解非凸-强凸双层优化中 $ε$-平稳点的查询复杂度。现有方法通常依赖双循环、基于惩罚的策略，复杂度较高。本文提出一种新型单循环算法SGHA，基于下层最优性作为约束的重构形式，通过引入二次正则项并限制对偶变量在有界域内，构造正则化拉格朗日函数，并应用光滑梯度下降上升法（Zhang et al., 2020），其中黑塞-向量积通过梯度差分近似。该算法在确定性情形下达到 $O(\barκ_y^5ε^{-2})$ 的查询复杂度，在随机情形下，以至少 $1-ρ$ 的概率达到 $O(\barκ_y^{17}ε^{-6}ρ^{-3})$，在额外有界迭代假设下，期望复杂度为 $O(\barκ_y^{17}ε^{-6})$。若仅对下层目标施加随机光滑性假设，复杂度可提升至 $O(\barκ_y^{11}ε^{-4}ρ^{-2})$（高概率）和 $O(\barκ_y^{11}ε^{-4})$（期望），匹配已知下界对 $ε$ 的依赖。
原文摘要 · Abstract (English)
In this work, we study the oracle complexity of finding an $ε$-stationary point for nonconvex-strongly-convex (NC-SC) bilevel optimization using only first-order oracles. Existing methods achieving the best-known complexity guarantees typically rely on double-loop, penalty-based procedures. We propose a novel single-loop algorithm based on a constrained reformulation in which lower-level stationarity is imposed as a constraint. Specifically, we construct a regularized Lagrangian by introducing a quadratic regularizer and restricting the dual variable to a bounded domain, and then apply Smoothed Gradient Descent Ascent [Zhang et al., 2020], with Hessian-vector products approximated via finite differences of gradients. We refer to the resulting deterministic and stochastic algorithms as SGHA and Stoc-SGHA, respectively. In the deterministic setting, SGHA achieves an oracle complexity of $O(\barκ_y^{5}ε^{-2})$, where $\barκ_y$ denotes the relevant condition number. In the stochastic setting, Stoc-SGHA achieves an oracle complexity of $O\left(\barκ_y^{17}ε^{-6}ρ^{-3}\right)$ with probability at least $1-ρ$ for any $ρ\in(0,1)$, and an oracle complexity of $O\left(\barκ_y^{17}ε^{-6}\right)$ in expectation under an additional bounded-iterate assumption. Moreover, under an additional stochastic smoothness assumption imposed only on the lower-level objective, the stochastic oracle complexity of Stoc-SGHA improves to $O\left(\barκ_y^{11}ε^{-4}ρ^{-2}\right)$ with high probability and $O\left(\barκ_y^{11}ε^{-4}\right)$ in expectation, matching the $ε$-dependence of the lower bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。