A Single-Loop Algorithm for Decentralized Bilevel Optimization

• 成果类型: Article; Early Access
• 署名作者: Dong, Youran; Ma, Shiqian; Yang, Tunfeng; Yin, Chao
• 署名单位: Nanjing University; Rice University; Hohai University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0488
• 发表日期: 2025
• 关键词: convergence

摘要

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.