Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
We consider the decentralized stochastic optimization problems, where a network of $n$ nodes, each owning a local cost function, cooperate to find a minimizer of the globally-averaged cost. A widely studied decentralized algorithm for this problem is decentralized SGD (D-SGD), in which each node averages only with its neighbors. D-SGD is efficient in single-iteration communication, but it is very sensitive to the network topology. For smooth objective functions, the transient stage (which measures the number of iterations the algorithm has to experience before achieving the linear speedup stage) of D-SGD is on the order of ${\Omega}(n/(1-\beta)^2)$ and $\Omega(n^3/(1-\beta)^4)$ for strongly and generally convex cost functions, respectively, where $1-\beta \in (0,1)$ is a topology-dependent quantity that approaches $0$ for a large and sparse network. Hence, D-SGD suffers from slow convergence for large and sparse networks. In this work, we study the non-asymptotic convergence property of the D$^2$/Exact-diffusion algorithm. By eliminating the influence of data heterogeneity between nodes, D$^2$/Exact-diffusion is shown to have an enhanced transient stage that is on the order of $\tilde{\Omega}(n/(1-\beta))$ and $\Omega(n^3/(1-\beta)^2)$ for strongly and generally convex cost functions, respectively. Moreover, when D$^2$/Exact-diffusion is implemented with gradient accumulation and multi-round gossip communications, its transient stage can be further improved to $\tilde{\Omega}(1/(1-\beta)^{\frac{1}{2}})$ and $\tilde{\Omega}(n/(1-\beta))$ for strongly and generally convex cost functions, respectively. These established results for D$^2$/Exact-Diffusion have the best (i.e., weakest) dependence on network topology to our knowledge compared to existing decentralized algorithms. We also conduct numerical simulations to validate our theories.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Addressing Data Heterogeneity in Decentralized Learning via Topological Pre-processing
Recently, local peer topology has been shown to influence the overall convergence of decentralized learning (DL) graphs in the presence of data heterogeneity. In this paper, we demonstrate the advantages of constructing …
HERMES: Heterogeneous Application-Enabled Routing Middleware for Edge-IoT Systems
The growth of the Internet of Things has enabled a new generation of applications, pushing computation and intelligence toward the network edge. This trend, however, exposes challenges, as the heterogeneity of devices an…
Towards Heterogeneity-Aware and Energy-Efficient Topology Optimization for Decentralized Federated Learning in Edge Environment
Federated learning (FL) has emerged as a promising paradigm within edge computing (EC) systems, enabling numerous edge devices to collaboratively train artificial intelligence (AI) models while maintaining data privacy. …
Federated LearningDecentralized Bilevel Optimization: A Perspective from Transient Iteration Complexity
Stochastic bilevel optimization (SBO) is becoming increasingly essential in machine learning due to its versatility in handling nested structures. To address large-scale SBO, decentralized approaches have emerged as effe…
Bilevel OptimizationRefined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data
One of the key challenges in decentralized and federated learning is to design algorithms that efficiently deal with highly heterogeneous data distributions across agents. In this paper, we revisit the analysis of the po…
Federated Learning