Communication-Efficient Stochastic Gradient Descent Ascent with Momentum Algorithms

1 Introduction

Recently, the stochastic minimax optimization problem has been attracting increasing attention since numerous machine learning models can be formulated as a minimax optimization problem. For instance, the adversarial training paradigm [Goodfellow et al., 2014; Madry et al., 2017] solves the maximization and minimization subproblems alternately to obtain a robust machine learning model. The AUC maximization problem is formulated as a minimax optimization problem in [Ying et al., 2016] to facilitate stochastic training. Meanwhile, with the emergence of distributed data in real-world machine learning applications, efficiently solving large-scale stochastic minimax optimization problems becomes an open challenge. In this paper, we focus on developing efficient optimization algorithms to solve the following stochastic minimax optimization problem:

∗Corresponding author

where K is the number of workers, f (k) (x, y) = Eξ∼D(k) [f (k) (x, y; ξ)] is the loss function on the k-th worker and D(k) denotes the dataset on the k-th worker. In this paper, we assume f (k) (x, y) is nonconvex regarding x and stronglyconcave regarding y.

A typical application of Eq. (1) is the imbalanced data classification task. Specifically, the data in many machine learning applications is imbalanced, where the number of positive samples is extraordinarily different from that of negative samples. For instance, in the click-through rate (CTR) prediction task, there are much fewer positive samples than negative samples. It is challenging to learn a well-performing classifier with such kinds of imbalanced data. Recently, to address this issue, a line of research is to directly optimize the Area-Under-the-ROC-Curve (AUC) score, rather than the cross-entropy loss function. Specifically, [Ying et al., 2016] developed the following minimax loss function for the AUC maximization problem:

where w ∈ Rd denotes the model parameter of the classifier f, ˆw1 ∈ R, ˆw2 ∈ R, θ ∈ R are the additional parameters for computing AUC score, (a, b) represents the sample's feature and label, p denotes the prior probability of the positive class, and I is an indicator function. Here, when the classifier f is nonconvex, such as a deep neural network, Eq. (2) is a nonconvex-strongly-concave problem.

To solve stochastic minimax optimization problems, a lot of efforts have been made in the past few years. In particular, numerous stochastic gradient descent ascent (SGDA) algorithms [Lin et al., 2020; Zhang et al., 2020; Qiu et al., 2020; Yan et al., 2020; Yang et al., 2020; Chen et al., 2021] have been proposed. For instance, [Lin et al., 2020] developed mini-batch SGDA and established its convergence rate for nonconvex-strongly-concave problems. However, this method requires a large batch size. Thus, it is not practical for real-world machine learning applications. To address this issue, [Qiu et al., 2020] developed a momentum SGDA algorithm, which only needs a small constant batch size. Furthermore, a couple of accelerated algorithms [Huang et al., 2020; Luo et al., 2020; Qiu et al., 2020] have been proposed by incorporating the variance reduction techniques [Cutkosky and Orabona, 2019; Fang et al., 2018]. However, all of these algorithms ignore the distributed setting. They cannot be directly leveraged to solve Eq. (1) due to the unique challenges, such as the communication issue, in the distributed setting.

Different from the single-machine setting, the workers in a distributed training system should communicate frequently with the central server to communicate stochastic gradients. When the model is large, i.e., x and y are with high dimensionality, the incurred communication cost will lead to significant performance bottleneck [Gao et al., 2023; Qiu et al., 2019]. In recent years, to alleviate the large communication cost issue, a large number of methods have been proposed. For instance, [Alistarh et al., 2017; Wen et al., 2017] proposed to compress the stochastic gradient for reducing the communication cost. [Stich et al., 2018; Karimireddy et al., 2019] developed the error-feedback strategy to improve the convergence performance of compressed gradient algorithms, [Tang et al., 2019; Zheng et al., 2019] proposed the two-way compression strategy to compress the uplink and downlink gradient. Recently, [Richt´arik et al., 2021] developed a recursive compressor such that the compression error could be shrunken in the course of training.

However, all aforementioned communication-efficient algorithms only focus on theminimization problem. It's unclear whether those techniques still work for the minimax problem. 1) On the algorithmic design side, each worker in Eq. (1) has to communicate the stochastic gradient regarding x and that regarding y with the central server. How to compress those two stochastic gradients such that the communication cost is reduced and the convergence performance is not impaired has not been explored yet. 2) On the theoretical analysis side, how the compressed gradient algorithm for Eq. (1) affects the convergence has not been investigated. Especially, when the momentum technique and the compression technique are employed simultaneously, how they affect the convergence rate has not been studied. In fact, it is much more challenging to establish the convergence rate compared with the minimization problem due to the interaction between those techniques in both minimization and maximization subproblems. Thus, it is necessary to develop communication-efficient algorithms with theoretical guarantees to solve Eq. (1).

In this paper, to address aforementioned challenges, we developed two novel communication-efficient stochastic gradient descent ascent algorithms with momentum algorithms. Specifically, on the algorithmic design side, our first algorithm compresses the momentum, rather than stochastic gradients, in both worker-to-server and server-to-worker directions by employing the plain error-feedback compression scheme [Karimireddy et al., 2019]. Our second algorithm employs the recursive error-feedback compression mechanism [Richt´arik et al., 2021] for compressing the momentum communicated in both directions. As such, the communication cost can be reduced significantly. On the theoretical analysis side, we proposed novel theoretical analysis techniques to establish the convergence rate of our algorithms. Importantly, our theoretical results demonstrate how the compression operator and the number of devices affect the convergence rate. To the best of our knowledge, this is the first work to develop communication-efficient algorithm with theoretical guarantees for solving the distributed minimax optimization problem. At last, we apply our algorithm to solve the AUC maximization problem in Eq. (2) for the distributed imbalanced classification task. The extensive experimental results confirm the efficacy of our algorithms in saving communication cost and its effectiveness in preserving the convergence performance. In summary, we made the following contributions in this paper:

• We developed two novel communication-efficient algorithms for optimizing distributed minimax optimization problems. This is the first work studying how to reduce the communication cost for minimax problems.
• We established the convergence rate of our two algorithms, theoretically demonstrating how the compression operator and the number of workers affect convergence rates.
• We conducted extensive experiments on the imbalanced classification task, which confirms the effectiveness of our algorithms.

2 RelatedWorks

2.1 Stochastic Minimax Optimization Algorithms

In machine learning, a large number of models can be formulated as the stochastic minimax optimization problem. A typical example is the adversarial learning model [Goodfellow et al., 2014; Madry et al., 2017], which has been widely applied in a wide variety of data mining and machine learning applications. Due to the extensive application of stochastic minimax optimization problem in machine learning, developing efficient optimization algorithms for this problem has attracted a surge of attention in the past few years. As such, a large number of algorithms have been proposed. For instance, [Lin et al., 2020] leveraged stochastic gradients to solve the maximization and minimization subproblems, and established its convergence rate for nonconvex-stronglyconcave problems. This convergence rate is further improved in [Chen et al., 2021] by assuming that the second moment of stochastic gradients is bounded. Furthermore, to accelerate the convergence rate of SGDA, [Qiu et al., 2020] developed two momentum-based algorithms by exploiting the moving-average strategy and the STORM strategy [Cutkosky and Orabona, 2019], respectively. Meanwhile, [Luo et al., 2020] exploited the SPIDER variance-reduced gradient [Fang et al., 2018] to accelerate SGDA and achieve a better convergence rate than the standard SGDA for nonconvex-stronglyconcave problems.

As for the AUC maximization problem, traditional methods typically employ a surrogate function, which depends on a pair of training samples. As such, it is not friendly to the stochastic training. To address this problem, [Ying et al., 2016] reformulated it as a minimax loss function, which can be decomposed into a sum of loss functions regarding individual samples. As a result, it can be optimized by stochastic gradient algorithms. Based on this reformulated minimax loss function, a couple of algorithms have been proposed for AUC maximization. For instance, [Ying et al., 2016] developed a stochastic online algorithm and established its convergence rate for convex-concave problems. However, [Ying et al., 2016] assumes that the classifier is a linear function, which is too restrictive to be applied to practical machine learning applications. Later, [Liu et al., 2019] extended it to deep neural networks so that the loss function becomes nonconvexstrongly-concave. Then, they developed the stage-wise proximal primal-dual stochastic gradient algorithm and established its convergence rate based on the Polyak-Łojasiewicz (PL) condition. However, all these algorithms just focus on the single-machine setting so that they are not able to handle the communication challenges in the distributed setting.

2.2 Communication-Efficient Distributed Optimization Algorithms

Under the distributed setting, a major concern is the large communication cost caused by the communication between workers and the central server. In the past few years, much progress has gone towards designing communicationefficient algorithms. The basic idea is to compress the gradient such that fewer bits are demanded in the communication step. Based on this strategy, a large number of communication-efficient stochastic gradient descent (SGD) algorithms [Jiang and Agrawal, 2018; Alistarh et al., 2017; Wen et al., 2017; Gao et al., 2021; Ivkin et al., 2019; Wangni et al., 2018; Gorbunov et al., 2020; Gupta et al., 2021] have been proposed. For instance, [Wen et al., 2017] developed the TernGrad algorithm, which quantizes gradients to ternary levels so that the communication cost can be reduced significantly. [Bernstein et al., 2018] proposed a more aggressive algorithm, which just communicates the sign of gradient entries. However, these compression strategies introduce a large gradient variance, which can impair the convergence performance. To address this problem, the plain error-feedback compression strategy was introduced in [Seide et al., 2014; Stich et al., 2018; Karimireddy et al., 2019]. It is able to reduce the gradient bias by compensating the compression error so that the convergence performance of compressed gradient algorithms can match that of full-precision counterparts. Recently, [Richt´arik et al., 2021] developed a new recursive error-feedback compression scheme, which enjoys the contractive compression error property and demonstrates superior performance in practice. However, all these methods only investigate the minimization problem.

Regarding the distributed minimax optimization problem, a few of works have been proposed in recent years. For instance, [Xian et al., 2021; Zhang et al., 2021; Gao, 2022; Zhang et al., 2023b] developed decentralized stochastic variance reduced gradient descent ascent algorithms where workers perform peer-to-peer communication. On the other hand, [Deng and Mahdavi, 2021; Tarzanagh et al., 2022; Sharma et al., 2022] developed a federated stochastic gradient descent ascent algorithm for Federated Learning. Moreover, [Guo et al., 2020; Yuan et al., 2021; Zhang et al., 2023a] studied the AUC maximization problem under the federated learning setting. These works are orthogonal to our setting because they reduce the communication cost by skipping the communication round, rather than compressing gradients. In summary, designing communication-efficient algorithms for optimizing Eq. (1) is still an open challenging problem.

3 Methodology

3.1 Problem Setup

The gradient compression technique has been widely studied in recent years. Typically, the compression operator satisfies the following property.

Definition 1. A compression operator C : Rd → Rd is αcontraction if there exists α ∈ (0, 1] such that

The commonly used compression operators that enjoy the α-contraction property include Top-k operator [Stich et al., 2018] and the scaled sign operator [Karimireddy et al., 2019].

To investigate the convergence rate of our algorithm, we assume the loss function satisfies the following assumptions, which are also commonly used in existing minimax optimization works [Lin et al., 2020; Luo et al., 2020; Huang et al., 2020; Qiu et al., 2020].

Assumption 1. The loss function f (k) on the k-th worker is L-smooth, i.e., there exists a constant value L > 0 such that

Assumption 2. The stochastic gradient ∇xf (k) (x, y; ξ) and ∇yf (k) (x, y; ξ) have bounded variances, i.e., there exist constant values σx > 0 and σy > 0 such that

Assumption 3. The loss function f (k) is µ-strongly-concave with respect to y, i.e., there exists a constant value µ > 0 such that

Algorithm 1 SGDAM-PEF

Input: η > 0, γ > 0, λ > 0, ρ1 > 0, ρ2 > 0,

r0 = 0, s0 = 0.

• 1: for t = 0, · · · , T -1 do
• 2: Worker-k:
• 3: if t == 0 then

• 5: else

• 7: end if

8: p(k)

t =m(k)

t +ϕ(k)

t , ϕ(k)

t -C(p(k)

t+1 = p(k)

Upload C(p(k) t ) to the central server.

• 9: if t == 0 then

• 11: else

• 13: end if

Upload C(q(k) t ) to the central server.

• 15: Server:

t ) + st , st+1 = vt -C(vt) ,

Broadcast C(ut) and C(vt) to all workers.

• 16: Worker-k:

• 17: end for

3.2 Communication-Efficient Stochastic Gradient Descent Ascent with Momentum Algorithms

In this paper, we focus on the stochastic gradient descent ascent with momentum algorithm, where the momentum stochastic gradient is employed to update the minimization and maximization subproblems. To reduce the communication cost, we proposed two communication-efficient stochastic gradient descent ascent with momentum algorithms. In particular, in Algorithm 1, we developed the communicationefficient stochastic gradient descent ascent with momentum algorithm, i.e., SGDAM-PEF, which employs the plain errorfeedback technique to compress the momentum in two directions. In Algorithm 2, we proposed the SGDAM-REF algorithm, which leverages the recursive error-feedback technique to compress the momentum in two directions.

Algorithm 1. SGDAM-PEF

Both algorithms exploits the momentum stochastic gradient to update model parameters. For instance, for the minimization subproblem with respect to x, at the t-th iteration, each worker k computes the momentum m(k) t based on the

t ) ,

Algorithm 2 SGDAM-REF

• 1: for t = 0, · · · , T -1 do
• 2: Worker-k:
• 3: Receive xt and yt from the server
• 4: if t == 0 then

• 6: else

• 8: end if

9: p(k)

t = C(m(k)

t -u(k)

t ) , u(k)

t +p(k)

t+1 = u(k)

t

Upload p(k) t to the central server.

• 14: end if

Upload q(k) t to the central server.

• 16: Server:

Broadcast rt+1 and st+1 to all workers.

• 17: Worker-k:

• 18: end for

,

stochastic gradient as follows:

where ρ1 and η are two positive hyperparameters such that ρ1η < 1, ξ (k) t denotes the randomly selected samples from the local dataset on the k-th worker. Note that the model parameter x(k) t on the k-th worker is the same with other workers due to the synchronization across all workers. Thus, we omit the superscript of x(k) t and y(k) t throughout this paper.

Algorithm 1 employs the following error-feedback scheme to compress the momentum m(k) t :

where ϕ(k) t+1 denotes the residual error between the fullprecision momentum p(k) t , which is the original momentum m(k) t corrected by the residual error ϕ(k) t in the prior iteration, and the compressed momentum C(p(k) t ). Then, C(p(k) t ) is uploaded to the central server and thus the communication cost is reduced. With such an error-feedback mechanism, we can control the bias caused by the compression operation to improve the convergence.

To reduce the communication cost when broadcasting the global momentum to all workers, we also compress the global

,

momentum with the same error-feedback compression mechanism to get the compressed global momentum C(ut), which is shown in Line 15 of Algorithm 1. Then, each worker exploits this global momentum to update it model parameters. As for the model parameter y, our algorithm leverages the same compression technique to reduce communication cost.

It can be observed that our algorithm compresses the momentum of the minimization and maximization subproblems, rather than the stochastic gradient, in both worker-to-server and server-to-worker directions to reduce the communication overhead. To the best of our knowledge, our work is the first one applying this technique to the minimax optimization algorithm, especially the compression of the momentum, which is much more challenging. Specifically, the minimax structure and momentum cause significant challenges to investigate the convergence rate. We addressed these challenges and established the convergence rate in Section 4.

Algorithm 2. SGDAM-REF

However, the plain error-feedback mechanism in Algorithm 1 cannot guarantee the residual error converges to zero [Richt´arik et al., 2021]. Therefore, in Algorithm 2, we resort to the recursive error-feedback compression strategy, which is first proposed for the minimization problem in [Richt´arik et al., 2021], to compress momentumm(k) t as follows:

where u(k) t+1 can be viewed as an approximation to momentum m(k) t . It can be observed that this compression mechanism compress the difference between the original momentum m(k) t and the approximated one u(k) t in the prior iteration. With this compression strategy, u(k) t+1 will converge to m(k) t , which will be shown in our theoretical analysis. Here, p(k) t is uploaded to the central server and the communication cost is reduced. Similarly, the maximization subproblem with respect to y also follows the same strategy to compute the local momentum h(k) t and compress it with the recursive compression strategy to obtain v(k) t+1 .

As for the central server, when it receives p(k) t from all workers, it computes the average ¯ut+1 = ¯ut + 1K ∑Kk=1 p(k) t and compresses it with the same recursive compression strategy, which is shown in Line 16 of Algorithm 2. Then, the server broadcasts rt+1 to all workers. Similarly, the server applies the same procedure to the maximization subproblem. As such, the communication cost in both worker-to-server and server-to-worker directions are reduced significantly.

After receiving the global rt+1 from the central server, each worker k updates its local ˆut+1 and exploits it to update the local model parameter as follows:

where γ > 0 is a hyperparameter. It is worth noting that all workers and the central server maintain an identical sequence {ˆut}, since ˆu0 = 0 and rt is shared by all workers and the central server. In addition, due to the employed recursive compression strategy, ˆut+1 will converge to ¯ut+1, while

¯ut+1 will approach to the global momentum 1K ∑Kk=1 m(k) t . Thus, ˆut+1 is an approximation to the global momentum. As such, each worker leverages the compressed global momentum to update its model parameters. Regarding the maximization subproblem with respect to y, our algorithm exploits the same strategy to update it.

Note that the recursive compression strategy is first proposed in [Richt´arik et al., 2021]. However, our algorithm is extraordinarily different from it. First, [Richt´arik et al., 2021] studies the full gradient descent algorithm. Our algorithm focuses on stochastic gradients. Additionally, [Richt´arik et al., 2021] compresses gradients, while our algorithm compresses the momentum, which is much more challenging. Second, [Richt´arik et al., 2021] just compresses the gradient sent from workers to the central server. On the contrary, our algorithm performs compression on both directions. Thus, our algorithm is able to save much more communication cost. Meanwhile, the two-way compression makes it much more challenging to establish the convergence rate of our algorithm. At last, [Richt´arik et al., 2021] established the convergence rate for minimization problem. As such, their convergence analysis does not hold for our minimax optimzation problem. All in all, our algorithm is significantly different from [Richt´arik et al., 2021] and it is much more challenging to establish the convergence rate of our algorithm due to the employed twoway compression and momentum techniques.

4 Theoretical Analysis

To investigate the convergence rate of our algorithm, we first introduce two auxiliary functions: Φ(x) = maxy f(x, y) and y∗ (x) = argmaxy f(x, y). Then, based on Assumption 1, it is easy to get that Φ(x) is LΦ-smooth where LΦ = 2L2 /µ [Lin et al., 2020]. Moreover, we introduce an additional assumption about the compression operator in the following, which has been commonly used in existing works [Alistarh et al., 2018; Li and Li, 2022; Haddadpour et al., 2021], e.g., Assumption 1 of [Alistarh et al., 2018] and Assumption 3 of [Li and Li, 2022].

Assumption 4. The compression operator C : Rd → Rd satisfies the following condition:

where α ∈ (0, 1] and a ∈ Rd .

Then, based on the aforementioned assumptions and auxiliary functions, we establish the convergence rate of our algorithm for nonconvex-strongly-concave problems.

Theorem 1. Given Assumptions 1-4, by setting ρ1 > 0, ρ2 > 0, η <min{ 1 2γLΦ , 1 ρ1 , 1 ρ2 , 1}, and

Algorithm 1 has the following convergence rate

where x∗ represents the optimal solution.

Remark 1. From Theorem 1, it can be observed that γ = O(α4 ), λ = O(α4 ), ρ1 = O(1), and ρ2 = O(1).

Remark 2. In terms of Theorem 1, by setting η = O(Kϵ2 ), T = O( α-4 Kϵ4 ), Algorithm 1 can achieve the ϵ-accuracy solution, i.e., 1 T ∑T -1 t=0 E[∥∇Φ(xt)∥2 ] ≤ ϵ2 . The dependence on α indicates that the compression operation increases the number of iterations. To the best of our knowledge, this is the first algorithm disclosing how the compression operation affects the convergence rate of minimax optimization algorithms. When there is no compression operation, i.e., α = 1, we can get the iteration complexity O( 1 Kϵ4 ), which indicates that our algorithm can achieve linear speedup with respect to the number of devices compared with that O( 1 ϵ4 ) of the single-machine counterpart [Qiu et al., 2020].

Theorem 2. Given Assumptions 1-4, by setting ρ1 > 0, ρ2 > 0, η <min{ 1 2γLΦ , 1 ρ1 , 1 ρ2 , 1}, and

Algorithm 2 has the following convergence rate

where x∗ represents the optimal solution.

Similarly, we can find that γ = O(α4 ), λ = O(α4 ), ρ1 = O(1), and ρ2 = O(1) in Theorem 2. We can also get the iteration complexity as follows.

Remark 3. In terms of Theorem 2, by setting η = O(Kα4 ϵ2 ), T = O( α-8 Kϵ4 ), Algorithm 2 can achieve the ϵaccuracy solution, i.e., 1 T ∑T -1 t=0 E[∥∇Φ(xt)∥2 ] ≤ ϵ2 . This iteration complexity also indicates the linear speedup with respect to the number of devices. Additionally, compared with Theorem 1, the learning rate has an additional dependence on α, resulting a larger iteration complexity O( α-8 Kϵ4 ) than O( α-4 Kϵ4 ) of Theorem 1.

In summary, we established the convergence rate for our two algorithms, disclosing how the compression operation and the number of devices affect the convergence rate. To the best of our knowledge, this is the first work achieving these theoretical results. In fact, it is challenging to establish these convergence rates. Specifically, our algorithms compress the momentum on both directions so that the interaction among the momentum technique, compression scheme, and two subproblems make it difficult to study how the function value and the compression error evolves across iterations. We developed novel theoretical analysis strategies, e.g., a novel potential function for Algorithm 2, to establish the convergence rate. All in all, establishing the convergence rate of our two algorithms is challenging. Our new theoretical analysis strategies are novel and can benefit other distributed minimax optimization, such as federated minimax optimization.

5 Experiments

5.1 Experimental Setup

In our experiments, we apply our two algorithms to the distributed AUC maximization problem for imbalanced data classification.

Datasets. In our experiments, five benchmark datasets are employed to evaluate the performance of our algorithm. They are CATvsDOG 1 , CIFAR10, CIFAR100 2 , STL10 [Coates et al., 2011], Melanoma [Rotemberg et al., 2021]. For the first four datasets, we partition each dataset into two groups according to its classes. Specifically, the first half of classes are viewed as the positive class, while the second half of classes are viewed as the negative class. Then, we randomly drop some samples from the positive class in the training set such that the ratio between positive samples and all samples is 0.1. As such, the first four datasets are imbalanced binary classification datasets. The statistics of all datasets are shown in Appendix. Then, the training set is randomly distributed to all workers, while the testing set are the same for all workers.

Experimental settings. To evaluate the performance of our algorithm, we compare it with the full-precision stochastic gradient descent with momentum algorithm (SGDM), which is to optimize the cross-entropy loss function, the fullprecision stochastic gradient descent ascent with momentum algorithm (SGDAM) [Qiu et al., 2020], which is to optimize the AUC loss function, and the compressed SGDAM without the error-feedback technique (SGDAM-NEF). To make a fair comparison, we use the equivalent learning rate for all algorithms, i.e., 0.1. The compression operator in our experiment include Top-k and Rand-k where k = 20%. Note that θ in Eq. (2) is a scalar, which cannot be compressed by Top-k or Rank-k operators. Thus, we employ the quantization operator [Alistarh et al., 2017] where the quantization level is set to 4. More experimental settings can be found in Appendix.

1 https://www.kaggle.com/c/dogs-vs-cats

2 https://www.cs.toronto.edu/∼kriz/cifar.html

5.2 Results and Analysis

In Figure 1, we report the testing AUC score versus the number of epochs on testing sets. Here we use four workers where each worker is a V100-GPU. From Figure 1, we have the following observations. 1) Our two algorithms with the error-feedback technique significantly outperform those without error-feedback. 2) Our SGDAM-PEF and SGDAM-REF can achieve almost the same AUC score, which means the empirical performance of two error-feedback strategies does not have significant difference. 3) Our algorithms with Topk compressor perform better than the variants with Rand-k compressor. The possible reason for this phenomenon is that the Rand-k compressor discards too much informative gradient components. When using Top-k compressor, our two algorithms can achieve almost the same AUC score as the fullprecision SGDAM. In Figure 2, we plot the testing AUC score versus the number of communicated megabytes. The same experimental settings are used as Figure 1. It can be observed that our two algorithms with Top-k compressor achieve almost the same final testing performance as full-precision SGDAM under the condition of greatly reducing the communication cost, which confirms the efficacy of our algorithms in saving the communication cost and preserving the convergence performance.

To further demonstrate the communication efficiency of our algorithm, we use different compression ratios for our algorithms. The testing AUC score versus the consumed megabytes is shown in Figure 3. Here, due to the limitation of space, we only show the result of CIFAR10 and three different compression ratio: Top-20%, Top-10%, Top5%, and Top-2%. From Figure 3, we can observe our algorithms can achieve almost the same final performance with full-precision SGDAM consistently, which means that they are robust to high compression ratios. For example, our algorithm SGDAM-REF-Top5 with 95% compression ratios still achieve almost the same AUC score compared with fullprecision SGDAM on CIFAR10 dataset.

6 Conclusion

In this paper, we developed two novel communicationefficient stochastic gradient descent ascent algorithms for distributed minimax optimization problems. This is the first work to demonstrate how to reduce the communication cost of minimax optimization algorithms. Moreover, we established the convergence rate, disclosing how the compression operator and the number of devices affect the convergence rate. Extensive experimental results confirm the effectiveness of our algorithms.