Sharper Analysis of Single-Loop Methods for Bilevel Optimization

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 O(κ^6/K) to O(κ^5/K), where κ is the condition number of the inner-level problem. For ITD, we prove that the asymptotic error is O(κ^2), exactly matching the known lower bound and improving upon the previous O(κ^3) guarantee. Numerical experiments on synthetic and real tasks corroborate our theoretical findings.