Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization

Abstract

This paper studies a decentralized stochastic gradient tracking (DSGT) algorithm for non-convex empirical risk minimization problems over a peer-to-peer network of nodes, which is in sharp contrast to the existing DSGT only for convex problems. To ensure exact convergence and handle the variance among decentralized datasets, each node performs a stochastic gradient (SG) tracking step by using a mini-batch of samples, where the batch size is designed to be proportional to the size of the local dataset. We explicitly evaluate the convergence rate of DSGT with respect to the number of iterations in terms of algebraic connectivity of the network, mini-batch size, gradient variance, etc. Under certain conditions, we further show that DSGT has a network independence property in the sense that the network topology only affects the convergence rate up to a constant factor. Hence, the convergence rate of DSGT can be comparable to the centralized SGD method. Moreover, a linear speedup of DSGT with respect to the number of nodes is achievable for some scenarios. Numerical experiments for neural networks and logistic regression problems on CIFAR-10 finally illustrate the advantages of DSGT.

arXiv commentThis paper has been revised and theoretical results are improved

References in corpus (17)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• Communication Compression for Decentralized Training
• D${}^2$: Decentralized Training over Decentralized Data
• On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Stochastic Gradient Push for Distributed Deep Learning
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Moniqua: Modulo Quantized Communication in Decentralized SGD
• Decentralized Deep Learning with Arbitrary Communication Compression
• Asynchronous Accelerated Proximal Stochastic Gradient for Strongly Convex Distributed Finite Sums
• Distributed Learning over Unreliable Networks
• Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization
• Decentralized gradient methods: does topology matter?

Cited by in corpus (10)

• Variance-Reduced Decentralized Stochastic Optimization with Accelerated Convergence
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning
• Fully Asynchronous Distributed Optimization with Linear Convergence in Directed Networks
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• A Decentralized Primal-Dual Framework for Non-convex Smooth Consensus Optimization
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• RelaySum for Decentralized Deep Learning on Heterogeneous Data
• Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence
• Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning