Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction

Abstract

There is growing interest in large-scale machine learning and optimization over decentralized networks, e.g. in the context of multi-agent learning and federated learning. Due to the imminent need to alleviate the communication burden, the investigation of communication-efficient distributed optimization algorithms - particularly for empirical risk minimization - has flourished in recent years. A large fraction of these algorithms have been developed for the master/slave setting, relying on a central parameter server that can communicate with all agents. This paper focuses on distributed optimization over networks, or decentralized optimization, where each agent is only allowed to aggregate information from its neighbors. By properly adjusting the global gradient estimate via local averaging in conjunction with proper correction, we develop a communication-efficient approximate Newton-type method Network-DANE, which generalizes DANE to the decentralized scenarios. Our key ideas can be applied in a systematic manner to obtain decentralized versions of other master/slave distributed algorithms. A notable development is Network-SVRG/SARAH, which employs variance reduction to further accelerate local computation. We establish linear convergence of Network-DANE and Network-SVRG for strongly convex losses, and Network-SARAH for quadratic losses, which shed light on the impacts of data homogeneity, network connectivity, and local averaging upon the rate of convergence. We further extend Network-DANE to composite optimization by allowing a nonsmooth penalty term. Numerical evidence is provided to demonstrate the appealing performance of our algorithms over competitive baselines, in terms of both communication and computation efficiency. Our work suggests that performing a certain amount of local communications and computations per iteration can substantially improve the overall efficiency.

References in corpus (14)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Constrained Consensus
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• AIDE: Fast and Communication Efficient Distributed Optimization
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Optimal Algorithms for Distributed Optimization
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach

Cited by in corpus (5)

• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Variance-Reduced Decentralized Stochastic Optimization with Gradient Tracking--Part I: GT-SAGA
• Gradient tracking and variance reduction for decentralized optimization and machine learning
• COKE: Communication-Censored Decentralized Kernel Learning
• Model Linkage Selection for Cooperative Learning