提出统一框架SPARKLE，提升去中心化双层优化的收敛效率
SPARKLE: A Unified Single-Loop Primal-Dual Framework for Decentralized Bilevel Optimization
- 设计单循环原偶框架，支持多种异构性修正策略组合
- 理论证明收敛速度优于现有去中心化双层算法
- 实证表明EXTRA和Exact Diffusion比梯度追踪更适配双层结构
本文研究去中心化双层优化问题，多个代理通过邻域通信协作求解具有嵌套优化结构的问题。现有方法多依赖梯度追踪缓解数据异构性影响，未探索EXTRA或Exact Diffusion等其他成熟异构性修正技术，且通常对上下层问题采用相同去中心化策略，忽视不同层级的差异化机制。为此，本文提出SPARKLE——一种统一的单循环原偶算法框架，可灵活集成多种异构性修正策略，并支持上下层使用不同策略。本文给出统一收敛分析，适用于所有变体，达到现有去中心化双层算法最优收敛速率。结果进一步表明，EXTRA和Exact Diffusion更适合此类场景，混合策略优于仅使用梯度追踪。
原文摘要 · Abstract (English)
This paper studies decentralized bilevel optimization, in which multiple agents collaborate to solve problems involving nested optimization structures with neighborhood communications. Most existing literature primarily utilizes gradient tracking to mitigate the influence of data heterogeneity, without exploring other well-known heterogeneity-correction techniques such as EXTRA or Exact Diffusion. Additionally, these studies often employ identical decentralized strategies for both upper- and lower-level problems, neglecting to leverage distinct mechanisms across different levels. To address these limitations, this paper proposes SPARKLE, a unified Single-loop Primal-dual AlgoRithm frameworK for decentraLized bilEvel optimization. SPARKLE offers the flexibility to incorporate various heterogeneitycorrection strategies into the algorithm. Moreover, SPARKLE allows for different strategies to solve upper- and lower-level problems. We present a unified convergence analysis for SPARKLE, applicable to all its variants, with state-of-the-art convergence rates compared to existing decentralized bilevel algorithms. Our results further reveal that EXTRA and Exact Diffusion are more suitable for decentralized bilevel optimization, and using mixed strategies in bilevel algorithms brings more benefits than relying solely on gradient tracking.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。