  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.
