A Single-Loop Algorithm for Decentralized Bilevel Optimization

Bilevel optimization has gained significant attention in recent years because of its broad applications in machine learning. This paper focuses on bilevel optimization in decentralized networks and proposes a novel single-loop algorithm for solving decentralized bilevel optimization with a strongly convex lower-level problem. Our approach is built on the basis of the SOBA framework, and it is a fully single-loop method that approximates the hypergradient by using merely two matrix-vector multiplications per iteration. Importantly, by incorporating the gradient tracking and projection techniques, our algorithm does not require any gradient heterogeneity assumption, which distinguishes it from existing methods for decentralized bilevel optimization and federated bilevel optimization. We establish the convergence rate of the proposed algorithm. Moreover, we present experimental results on hyperparameter optimization and data hyper-cleaning problems, which demonstrate the efficiency of our proposed algorithm. Funding: This work was supported by the National Science Foundation Division of Mathematical Sciences [Grant 2243650]; the Division of Computing and Communication Foundations [Grants 2308597 and 2311275]; the Division of Electrical, Communications and Cyber Systems [Grant 2326591]; the National Natural Science Foundation of China [Grants 12431011, 12371301 and 12501425]; the Key Laboratory of NSLSCS, Ministry of Education of China; and the Natural Science Foundation of Jiangsu Province [Grant SBK20250404650].