DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization
DIAMOND: Taming Sample and Communication Complexities in Decentralized Bilevel Optimization
复制标题
DOI：
10.1109/infocom53939.2023.10228853
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Pei-Yuan Qiu;Yining Li;Zhuqing Liu;Prashant Khanduri;Jia Liu;N. Shroff;E. Bentley;K. Turck
中科院分区：
文献类型：
--
作者：
Pei-Yuan Qiu;Yining Li;Zhuqing Liu;Prashant Khanduri;Jia Liu;N. Shroff;E. Bentley;K. Turck
分散式双层优化最近受到越来越多的关注，这是由于其在许多新兴的多智能体学习范例中的基础作用（例如，多代理元学习和多代理强化学习）。然而，为了利用边缘网络有限的计算和通信能力，开发分散式双层优化技术的主要挑战是降低样本和通信复杂性。这促使我们开发一种新的分散式双层优化，称为DIAMOND（分散式单时间尺度随机近似与动量和梯度跟踪）。本文的贡献在于：1）我们的DIAMOND算法采用单循环结构，而不是遵循自然的双层优化的双循环结构，这提供了较低的计算和实现复杂度; 2）与现有的方法相比，DIAMOND算法不需要任何完整的梯度评估，这进一步降低了样本和计算复杂度; iii）通过动量信息和梯度跟踪技术的仔细整合，我们表明DIAMOND算法享有$\mathcal{O}\left（{{ \in ^{ - 3/2} \right）$的采样和通信复杂性，这两种方法都与数据集大小无关，并且显著优于现有的工作。大量的实验也验证了我们的理论研究结果。
Decentralized bilevel optimization has received increasing attention recently due to its foundational role in many emerging multi-agent learning paradigms (e.g., multi-agent meta-learning and multi-agent reinforcement learning) over peer-to-peer edge networks. However, to work with the limited computation and communication capabilities of edge networks, a major challenge in developing decentralized bilevel optimization techniques is to lower sample and communication complexities. This motivates us to develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale stochastic approximation with momentum and gradient-tracking). The contributions of this paper are as follows: i) our DIAMOND algorithm adopts a single-loop structure rather than following the natural double-loop structure of bilevel optimization, which offers low computation and implementation complexity; ii) compared to existing approaches, the DIAMOND algorithm does not require any full gradient evaluations, which further reduces both sample and computational complexities; iii) through a careful integration of momentum information and gradient tracking techniques, we show that the DIAMOND algorithm enjoys $\mathcal{O}\left( {{ \in ^{ - 3/2}}} \right)$ in sample and communication complexities for achieving an ϵ-stationary solution, both of which are independent of the dataset sizes and significantly outperform existing works. Extensive experiments also verify our theoretical findings.