提出无需强凸假设的去中心化双层优化算法,解决多智能体协作难题。
DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity
- 通过递减二次正则化消除下层强凸性依赖
- 理论证明收敛速度达 $O(1/T^{1-5p-rac{11}{4}τ})$
- 适用于数据异构场景,适合多智能体系统研究者
去中心化双层优化(DBO)为多智能体系统在无中央服务器情况下解决局部双层任务提供了强大框架。然而,现有大多数DBO方法依赖下层强凸性(LLSC)以保证解的唯一性和可定义的超梯度,限制了其在不满足该条件的实际场景中的应用。为此,我们提出一种新型单循环DBO算法——递减二次正则化去中心化双层优化(DUET),通过在下层目标中引入递减二次正则项,消除了对LLSC的依赖。我们证明,在较宽松假设下,DUET实现近似KKT平稳点收敛的迭代复杂度为 $O(1/T^{1-5p-rac{11}{4}τ})$,其中 $p$ 和 $τ$ 分别为控制下层学习率和平均化的参数。此外,算法结合梯度追踪机制以应对数据异构性这一关键挑战。据我们所知,这是首个在去中心化设置下处理无LLSC且具备数据异构性的DBO工作。数值实验验证了理论结果,并展示了所提算法的实用性。
原文摘要 · Abstract (English)
Decentralized bilevel optimization (DBO) provides a powerful framework for multi-agent systems to solve local bilevel tasks in a decentralized fashion without the need for a central server. However, most existing DBO methods rely on lower-level strong convexity (LLSC) to guarantee unique solutions and a well-defined hypergradient for stationarity measure, hindering their applicability in many practical scenarios not satisfying LLSC. To overcome this limitation, we introduce a new single-loop DBO algorithm called diminishing quadratically-regularized bilevel decentralized optimization (DUET), which eliminates the need for LLSC by introducing a diminishing quadratic regularization to the lower-level (LL) objective. We show that DUET achieves an iteration complexity of $O(1/T^{1-5p-\frac{11}{4}τ})$ for approximate KKT-stationary point convergence under relaxed assumptions, where $p$ and $τ$ are control parameters for LL learning rate and averaging, respectively. In addition, our DUET algorithm incorporates gradient tracking to address data heterogeneity, a key challenge in DBO settings. To the best of our knowledge, this is the first work to tackle DBO without LLSC under decentralized settings with data heterogeneity. Numerical experiments validate the theoretical findings and demonstrate the practical effectiveness of our proposed algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。