改进双层优化单循环方法的收敛性分析，提升理论精度与实际效率。
Sharper Analysis of Single-Loop Methods for Bilevel Optimization
- 提出解耦范数分析框架，更精准刻画算法误差来源。
- AID方法收敛率从O(κ⁶/K)提升至O(κ⁵/K)，ITD渐近误差降至O(κ²)。
- 适用于超参数优化、元学习等需高效双层优化的场景。
双层优化支撑超参数优化、元学习、神经网络架构搜索和强化学习等多种机器学习应用。尽管基于超梯度的方法已取得显著进展，但理论保证与实际所需的高效单循环实现之间仍存在差距。本文通过提出的解耦范数分析（DNA）框架，为单循环近似隐式微分（AID）和迭代微分（ITD）方法建立了更紧的收敛性结果。对于AID，收敛率从O(κ⁶/K)提升至O(κ⁵/K)，其中κ为内层问题的条件数；对于ITD，证明其渐近误差为O(κ²)，与已知下界一致，优于此前的O(κ³)保证。在合成与真实任务上的数值实验验证了理论结论。
原文摘要 · Abstract (English)
Bilevel optimization underpins many machine learning applications, including hyperparameter optimization, meta-learning, neural architecture search, and reinforcement learning. While hypergradient-based methods have advanced significantly, a gap persists between theoretical guarantees and practical single-loop implementations required for efficiency. We bridge this gap by establishing sharper convergence results for single-loop approximate implicit differentiation (AID) and iterative differentiation (ITD) methods, leveraging our proposed analytical framework, decoupled norm analysis (DNA). For AID, we improve the convergence rate from $\mathcal{O}(κ^6/K)$ to $\mathcal{O}(κ^5/K)$, where $κ$ is the condition number of the inner-level problem. For ITD, we prove that the asymptotic error is $\mathcal{O}(κ^2)$, exactly matching the known lower bound and improving upon the previous $\mathcal{O}(κ^3)$ guarantee. Numerical experiments on synthetic and real tasks corroborate our theoretical findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。