提出FlexATC框架，实现分布式优化中通信高效且收敛加速
Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration
- 采用概率化局部更新机制，统一多种ATC算法
- 强凸下线性收敛率与网络结构解耦，多数迭代可跳过通信
- 首次证明局部更新能真正带来通信加速，适合大规模分布式系统
本文研究网络中分布式复合优化问题，各节点需最小化本地光滑项之和与公共非光滑项的总和。基于概率性局部更新机制，提出通信高效的统一框架FlexATC，涵盖众多ATC类算法。在不依赖网络拓扑和局部更新次数的步长下，建立了凸与强凸情形下的次线性及线性收敛速率。特别地，在强凸情况下，线性收敛率与目标函数及网络结构解耦，且允许大多数迭代跳过通信而不影响收敛速度。所提统一理论首次证明，局部更新能为ATC类算法带来可证明的通信加速。数值实验验证了该框架的有效性，并支持理论结果。
原文摘要 · Abstract (English)
This paper is concerned with the distributed composite optimization problem over networks, where agents aim to minimize a sum of local smooth components and a common nonsmooth term. Leveraging the probabilistic local updates mechanism, we propose a communication-efficient Adapt-Then-Combine (ATC) framework, FlexATC, unifying numerous ATC-based distributed algorithms. Under stepsizes independent of the network topology and the number of local updates, we establish sublinear and linear convergence rates for FlexATC in convex and strongly convex settings, respectively. Remarkably, in the strong convex setting, the linear rate is decoupled from the objective functions and network topology, and FlexATC permits communication to be skipped in most iterations without any deterioration of the linear rate. In addition, the proposed unified theory demonstrates for the first time that local updates provably lead to communication acceleration for ATC-based distributed algorithms. Numerical experiments further validate the efficacy of the proposed framework and corroborate the theoretical results.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。