Multi-Consensus Decentralized Accelerated Gradient Descent

his paper considers the decentralized convex optimization problem, which has a wide range of applications in large-scale machine learning, sensor networks, and control theory. We propose novel algorithms that achieve optimal computation complexity and near optimal communication complexity. Our theoretical results give affirmative answers to the open problem on whether there exists an algorithm that can achieve a communication complexity (nearly) matching the lower bound depending on the global condition number instead of the local one. Furthermore, the linear convergence of our algorithms only depends on the strong convexity of global objective and it does not require the local functions to be convex. The design of our methods relies on a novel integration of well-known techniques including Nesterov's acceleration, multi-consensus and gradient-tracking. Empirical studies show the outperformance of our methods for machine learning applications. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

Authors

• Haishan Ye
• Luo Luo Fudan University Shanghai Key Laboratory for Contemporary Applied Mathematics
• Ziang Zhou
• Tong Zhang Nanjing University of Science and Technology

Keywords

No keywords are indexed for this paper.