A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning

Abstract

We study the consensus decentralized optimization problem where the objective function is the average of $n$ agents private non-convex cost functions; moreover, the agents can only communicate to their neighbors on a given network topology. The stochastic learning setting is considered in this paper where each agent can only access a noisy estimate of its gradient. Many decentralized methods can solve such problem including EXTRA, Exact-Diffusion/D${}^2$, and gradient-tracking. Unlike the famed DSGD algorithm, these methods have been shown to be robust to the heterogeneity across the local cost functions. However, the established convergence rates for these methods indicate that their sensitivity to the network topology is worse than DSGD. Such theoretical results imply that these methods can perform much worse than DSGD over sparse networks, which, however, contradicts empirical experiments where DSGD is observed to be more sensitive to the network topology. In this work, we study a general stochastic unified decentralized algorithm (SUDA) that includes the above methods as special cases. We establish the convergence of SUDA under both non-convex and the Polyak-Lojasiewicz condition settings. Our results provide improved network topology dependent bounds for these methods (such as Exact-Diffusion/D${}^2$ and gradient-tracking) compared with existing literature. Moreover, our results show that these methods are often less sensitive to the network topology compared to DSGD, which agrees with numerical experiments.

References in corpus (20)

• Harnessing Smoothness to Accelerate Distributed Optimization
• Large Batch Training of Convolutional Networks
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Distributed Pareto Optimization via Diffusion Strategies
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• D${}^2$: Decentralized Training over Decentralized Data
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Stochastic Gradient Push for Distributed Deep Learning
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Distributed Algorithms for Composite Optimization: Unified Framework and Convergence Analysis
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
• A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• A Stochastic Proximal Gradient Framework for Decentralized Non-Convex Composite Optimization: Topology-Independent Sample Complexity and Communication Efficiency
• Improving the Transient Times for Distributed Stochastic Gradient Methods

Cited by in corpus (5)

• A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
• Distributed Adaptive Gradient Algorithm with Gradient Tracking for Stochastic Non-Convex Optimization
• BlueFog: Make Decentralized Algorithms Practical for Optimization and Deep Learning
• Online Distributed Learning with Quantized Finite-Time Coordination
• Asynchronous Distributed Learning with Quantized Finite-Time Coordination