CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems

Abstract

Minimax problems arise in a wide range of important applications including robust adversarial learning and Generative Adversarial Network (GAN) training. Recently, algorithms for minimax problems in the Federated Learning (FL) paradigm have received considerable interest. Existing federated algorithms for general minimax problems require the full aggregation (i.e., aggregation of local model information from all clients) in each training round. Thus, they are inapplicable to an important setting of FL known as the cross-device setting, which involves numerous unreliable mobile/IoT devices. In this paper, we develop the first practical algorithm named CDMA for general minimax problems in the cross-device FL setting. CDMA is based on a Start-Immediately-With-Enough-Responses mechanism, in which the server first signals a subset of clients to perform local computation and then starts to aggregate the local results reported by clients once it receives responses from enough clients in each round. With this mechanism, CDMA is resilient to the low client availability. In addition, CDMA is incorporated with a lightweight global correction in the local update steps of clients, which mitigates the impact of slow network connections. We establish theoretical guarantees of CDMA under different choices of hyperparameters and conduct experiments on AUC maximization, robust adversarial network training, and GAN training tasks. Theoretical and experimental results demonstrate the efficiency of CDMA.

arXiv commentExtended version of paper https://doi.org/10.1609/aaai.v37i9.26246 which appeared in AAAI 2023

References in corpus (30)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Towards Deep Learning Models Resistant to Adversarial Attacks
• On the Convergence of FedAvg on Non-IID Data
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Agnostic Federated Learning
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• AIDE: Fast and Communication Efficient Distributed Optimization
• Robust Federated Learning: The Case of Affine Distribution Shifts
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Stochastic AUC Maximization with Deep Neural Networks
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Momentum-Based Variance Reduction in Non-Convex SGD
• Stochastic Variance Reduction Methods for Saddle-Point Problems
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning
• Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Łojasiewicz Condition
• Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency
• One Sample Stochastic Frank-Wolfe
• Efficient Algorithms for Federated Saddle Point Optimization
• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation
• Federated Minimax Optimization: Improved Convergence Analyses and Algorithms
• A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning
• Efficient Projection-Free Online Methods with Stochastic Recursive Gradient