CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 45 of its 77 references that are in the map. First posted on arXiv 29 May 2021.
Builds on
45 of 77 references.
References · 45
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
- 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
- 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
- 2014Deep Learning Face Attributes in the Wildcited by 3,693
- 2019Advances and Open Problems in Federated Learningcited by 3,046
- 2018Federated Optimization in Heterogeneous Networkscited by 2,987
- 2015Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networkscited by 2,054
- 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,538
- 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
- 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
- 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 539
33 more
- 2019Agnostic Federated Learningcited by 456
- 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
- 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
- 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
- 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
- 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
- 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 132
- 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
- 2021Distributionally Robust Federated Averagingcited by 104
- 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
- 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
- 2020FedGAN: Federated Generative Adversarial Networks for Distributed Datacited by 90
- 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 77
- 2019Reducing Noise in GAN Training with Variance Reduced Extragradientcited by 62
- 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
- 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 60
- 2016Stochastic Variance Reduction Methods for Saddle-Point Problemscited by 60
- 2016AIDE: Fast and Communication Efficient Distributed Optimizationcited by 43
- 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
- 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
- 2020Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problemscited by 38
- 2019One Sample Stochastic Frank-Wolfecited by 32
- 2019A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimizationcited by 27
- 2020Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networkscited by 27
- 2020Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learningcited by 24
- 2021Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexitycited by 21
- 2021Efficient Algorithms for Federated Saddle Point Optimizationcited by 20
- 2019Efficient Projection-Free Online Methods with Stochastic Recursive Gradientcited by 19
- 2019Fast and Furious Convergence: Stochastic Second Order Methods under Interpolationcited by 18
- 2020Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithmscited by 14
- 2020Gradient Free Minimax Optimization: Variance Reduction and Faster Convergencecited by 11
- 2021Decentralized Distributed Optimization for Saddle Point Problemscited by 10
- 2018Solving Non-Convex Non-Concave Min-Max Games Under Polyak-Lojasiewicz Conditioncited by 7
Built on by
Citing papers per year: 2022: 1; 2023: 0; 2024: 1.
2 papers.