提出单循环随机双层优化的收敛性分析，明确条件数影响。
On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation
- 改进近似隐式微分算法的理论证明
- 达到每轮误差约κ¹⁴ε⁻²的查询复杂度
- 适合研究元学习与超参优化的理论工作者
随机双层优化已成为元学习和超参数优化的基本框架。尽管单循环算法在实践中广泛应用，其在随机情形下的理论理解仍不如多循环方法成熟。本文对单循环随机近似隐式微分（SSAID）算法进行了精细化收敛分析。在平方梯度平稳性准则‖∇Φ(x)‖²≤ε下，修正后的证明表明，查询复杂度为𝒪(κ¹⁴ε⁻²)，等价于平均平稳性速率𝒪(κ⁷K⁻¹⁄²)。该结果保持了对目标精度ε的典型𝒪(ε⁻²)依赖关系，同时首次显式刻画了基于随机隐式微分的单循环方法中条件数κ的影响。
原文摘要 · Abstract (English)
Stochastic Bilevel Optimization has emerged as a fundamental framework for meta-learning and hyperparameter optimization. Despite the practical prevalence of single-loop algorithms, their theoretical understanding in the stochastic regime remains less developed than that of multi-loop methods. In this paper, we provide a refined convergence analysis of the Single-loop Stochastic Approximate Implicit Differentiation (SSAID) algorithm. Under the squared-gradient stationarity criterion $\|\nablaΦ(x)\|^2\leε$, the corrected proof establishes an oracle complexity of $\mathcal{O}(κ^{14}ε^{-2})$, equivalently an averaged stationarity rate of $\mathcal{O}(κ^7K^{-1/2})$. The result preserves the canonical $\mathcal{O}(ε^{-2})$ dependence on the target accuracy while giving an explicit characterization of the condition-number dependence for stochastic AID-based single-loop methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。