Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency

Abstract

Local SGD is a promising approach to overcome the communication overhead in distributed learning by reducing the synchronization frequency among worker nodes. Despite the recent theoretical advances of local SGD in empirical risk minimization, the efficiency of its counterpart in minimax optimization remains unexplored. Motivated by large scale minimax learning problems, such as adversarial robust learning and training generative adversarial networks (GANs), we propose local Stochastic Gradient Descent Ascent (local SGDA), where the primal and dual variables can be trained locally and averaged periodically to significantly reduce the number of communications. We show that local SGDA can provably optimize distributed minimax problems in both homogeneous and heterogeneous data with reduced number of communications and establish convergence rates under strongly-convex-strongly-concave and nonconvex-strongly-concave settings. In addition, we propose a novel variant local SGDA+, to solve nonconvex-nonconcave problems. We give corroborating empirical evidence on different distributed minimax problems.

This paper has been accepted to AISTATS 2021

References in corpus (21)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
• On the Convergence of FedAvg on Non-IID Data
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• Federated Optimization in Heterogeneous Networks
• Don't Use Large Mini-Batches, Use Local SGD
• Local SGD Converges Fast and Communicates Little
• On the Convergence of Local Descent Methods in Federated Learning
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• A Variational Inequality Perspective on Generative Adversarial Networks
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Is Local SGD Better than Minibatch SGD?
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• FedGAN: Federated Generative Adversarial Networks for Distributed Data
• Federated Accelerated Stochastic Gradient Descent
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach

Cited by in corpus (5)

• An Optimal Transport Approach to Personalized Federated Learning
• A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• FedMM: Saddle Point Optimization for Federated Adversarial Domain Adaptation
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization