Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes

Authors: yan  huang
xiang  li
yipeng  shen
niao  he
jinming  xu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 15:46:07

Abstract: In this paper, we show that applying adaptive methods directly to distributed minimax problems can result in non-convergence due to inconsistency in locally computed adaptive stepsizes. To address this challenge, we propose D-AdaST, a Distributed Adaptive minimax method with Stepsize Tracking. The key strategy is to employ an adaptive stepsize tracking protocol involving the transmission of two extra (scalar) variables. This protocol ensures the consistency among stepsizes of nodes, eliminating the steady-state error due to the lack of coordination of stepsizes among nodes that commonly exists in vanilla distributed adaptive methods, and thus guarantees exact convergence. For nonconvex-strongly-concave distributed minimax problems, we characterize the specific transient times that ensure time-scale separation of stepsizes and quasi-independence of networks, leading to a near-optimal convergence rate of $\tilde{\mathcal{O}} \left( \epsilon ^{-\left( 4+\delta \right)} \right)$ for any small $\delta > 0$, matching that of the centralized counterpart. To our best knowledge, D-AdaST is the *first* distributed adaptive method achieving near-optimal convergence without knowing any problem-dependent parameters for nonconvex minimax problems. Extensive experiments are conducted to validate our theoretical results.

Main paper: 
 introduction: 
 Distributed optimization has seen significant research progress over the last decade, resulting in numerous algorithms (Nedic and Ozdaglar, 2009; Yuan et al., 2016; Lian et al., 2017; Pu and Nedić, 2021) . However, the traditional focus of distributed optimization has primarily been on minimization tasks. With the rapid growth of machine learning research, various applications have emerged that go beyond simple minimization, such as Generative Adversarial Networks (GANs) (Goodfellow et al., 2014; Gulrajani et al., 2017) , robust optimization (Mohri et al., 2019; Sinha et al., 2017) , adversary training of neural networks (Wang et al., 2021) , fair machine learning (Madras et al., 2018) , and just to name a few. These tasks typically involve a minimax structure as follows:min x∈X max y∈Y f (x, y) ,where X ⊆ R p , Y ⊆ R d , and x, y are the primal and dual variables to be learned, respectively. One of the simplest yet effective methods for solving the above minimax problem is Gradient Descent Ascent (GDA) (Dem'yanov and Pevnyi, 1972; Nemirovski et al., 2009) which alternately performs stochastic gradient descent for the primal variable and stochastic gradient ascent for the dual variable. This approach has demonstrated its effectiveness in solving minimax problems, especially for convexconcave objectives (Hsieh et al., 2021; Daskalakis et al., 2021; Antonakopoulos et al., 2021) , i.e., the function f (•, y) is convex for any y ∈ Y, and f (x, •) is concave for any x ∈ X .Adaptive gradient methods, such as AdaGrad (Duchi et al., 2011) , Adam (Kingma and Ba, 2014) , and AMSGrad (Reddi et al., 2018) , are often integrated with GDA to effectively solve minimax problems with theoretical guarantees in convex-concave settings (Diakonikolas, 2020; Antonakopoulos et al., 2021; Ene and Lê Nguyen, 2022) . These adaptive methods are capable of adjusting stepsizes based on historical gradient information, making it robust to hyper-parameters tuning and can converge without requiring to know problem-dependent parameters (a characteristic often referred to as being "parameter-agnostic"). However, in the nonconvex regime, it has been shown by Lin et al. (2020) ; Yang et al. (2022b) that it is necessary to have a time-scale separation in stepsizes between the minimization and maximization processes to ensure the convergence of GDA and GDA-based adaptive algorithms. In particular, the stepsize ratio between primal and dual variables needs to be smaller than a threshold depending on the properties of the problem such as the smoothness and strong-concavity parameters (Li et al., 2022; Guo et al., 2021; Huang et al., 2021) , which are often unknown or difficult to estimate in real-world tasks, such as training deep neural networks.Applying GDA-based adaptive methods into decentralized settings poses additional challenges due to the presence of inconsistency in locally computed adaptive stepsizes. In particular, it has been shown that the inconsistency of stepsizes can result in non-convergence in federated learning with heterogeneous computation speeds (Wang et al., 2020; Sharma et al., 2023) . This is mainly due to the lack of a central node coordinating the stepsizes of nodes in distributed settings, making it difficult to converge, as observed in minimization problems (Liggett, 2022; Chen et al., 2023b) . As a result, the following question arises naturally:"Can we design an adaptive minimax method that ensures the time-scale separation and consistency of stepsizes with provable convergence in fully distributed settings?"Contributions. In this paper, we aim to propose a distributed adaptive method for efficiently solving nonconvex-strongly-concave (NC-SC) minimax problems. The contributions are threefold:• We construct counterexamples showing that directly applying adaptive methods designed for centralized problems will lead to inconsistencies in locally computed adaptive stepsizes, resulting in non-convergence in distributed settings. To tackle this issue, we propose the first distributed adaptive minimax method, named D-AdaST, that incorporates an efficient stepsize tracking mechanism to maintain consistency across local stepsizes, which involves transmission of merely two extra (scalar) variables. The proposed algorithm exhibits timescale separation in stepsizes and parameter-agnostic capability in fully distributed settings.• Theoretically, we prove that D-AdaST is able to achieve a near-optimal convergence rate of Õ ϵ -(4+δ) with arbitrarily small δ > 0 to find an ϵ-stationary point for distributed NC-SC minimax problems. In contrast, we also prove the existence of a constant steady-state error in both the lower and upper bounds for GDA-based distributed minimax algorithms when being directly integrated with the adaptive stepsize rule without the stepsize tracking mechanism. Moreover, we explicitly characterize the transient times that ensure time-scale separation and quasi-independence of network, respectively.• We conduct extensive experiments on real-world datasets to verify our theoretical findings and the effectiveness of D-AdaST on a variety of tasks, including robust training of neural networks and optimizing Wasserstein GANs. In all tasks, we demonstrate the superiority of D-AdaST over several vanilla distributed adaptive methods across various graphs, initial stepsizes and data distributions (see also additional experiments in Appendix A).Distributed nonconvex minimax methods. In the realm of federated learning, Deng and Mahdavi (2021) introduce Local SGDA algorithm combining FedAvg/Local SGD with stochastic GDA and show an Õ ϵ -6 sample complexity for NC-SC objective functions. Sharma et al. (2022) provide improved complexity result of Õ ϵ -4 matching that of the lower bound of first-order algorithms for both NC-SC and nonconvex-Polyak-Lojasiewicz (NC-PL) settings (Li et al., 2021; Zhang et al., 2021a) . Yang et al. (2022a) integrate Local SGDA with stochastic gradient estimators to eliminate the data heterogeneity. More recently, Zhang et al. (2023) adopt compressed momentum methods with Local SGD to increase the communication efficiency of the algorithm. For decentralized nonconvex minimax problems, Liu et al. (2020) study the training of GANs using decentralized optimistic stochastic gradient and provide non-asymptotic convergence with fixed stepsizes. Tsaknakis et al. (2020) propose a double-loop decentralized SGDA algorithm with gradient tracking techniques (Pu and Nedić, 2021) and achieve Õ ϵ -4 sample complexity. With a stronger assumption of average smoothness, some studies employ variance reduction techniques to accelerate convergence (Zhang et al., 2021b; Chen et al., 2022; Xian et al., 2021; Tarzanagh et al., 2022; Wu et al., 2023; Chen et al., 2024; Zhang et al., 2024) , which require more memory and computational resources due to the need for larger batch-sizes or full gradient evaluations. However, all the above-mentioned methods use a fixed or uniformly decaying stepsize, requiring the prior knowledge of smoothness and concavity.(Distributed) adaptive minimax methods. For centralized nonconvex minimax problems, Yang et al. (2022b) show that, even in deterministic settings, GDA-based methods necessitate the timescale separation of the stepsizes for primal and dual updates. Many attempts have been made for ensuring the time-scale separation requirement (Lin et al., 2020; Yang et al., 2022c; Boţ and Böhm, 2023; Huang et al., 2023) . However, these methods typically come with the prerequisite of having knowledge about problem-dependent parameters, which can be a significant drawback in practical scenarios. To this end, Yang et al. (2022b) introduce a nested adaptive algorithm named NeAda that achieves parameter-agnosticism by incorporating an inner loop to effectively maximize the dual variable, which can obtain an optimal sample complexity of Õ ϵ -4 when the strong-concavity parameter is known. More recently, Li et al. (2023) introduce TiAda, a single-loop parameter-agnostic adaptive algorithm for nonconvex minimax optimization which employs separated exponential factors on the adaptive primal and dual stepsizes, improving upon NeAda on the noise-adaptivity. There has been few works dedicated to adaptive minimax optimization in federated learning settings. For instance, Huang et al. (2024) introduces a federated adaptive algorithm that integrates the stepsize rule of Adam with full-client participation, resembling the centralized counterpart. Ju et al. (2023) study a federated Adam algorithm for fair federated learning where the objective function is properly weighted to account for heterogeneous updates among nodes. To the best of our knowledge, it is still unknown how one can design an adaptive minimax method capable of fulfilling the time-scale separation requirement and being parameter-agnostic in fully distributed settings.Notations. Throughout this paper, we denote by E [•] the expectation of a random variable, ∥•∥ the Frobenius norm, ⟨•, •⟩ the inner product of two vectors, ⊙ the Hadamard product (entry wise), ⊗ the Kronecker product. We denote by 1 the all-ones vector, I the identity matrix and J = 11 T /n the averaging matrix with n dimension. For a vector or matrix A and constant α, we denote A α the entry-wise exponential operations. We denote Φ (x) := f (x, y * (x)) as the primal function where y * (x) = argmax y∈Y f (x, y), and P Y (•) as the projection operation onto set Y. 
distributed adaptive minimax methods: 
 We consider the distributed minimax problem collaboratively solved by a set of agents over a network. The overall objective of the agents is to solve the following finite-sum problem:EQUATIONwhere f i : R p+d → R is the local private loss function accessible only by the associated node representing the communication link from node j to node i. For node i, we define N i = {j | (i, j) ∈ E} as the set of its neighboring nodes. Before proceeding to the discussion of distributed algorithms, we first introduce the following notations for brevity:i ∈ N = {1, 2, • • • , n}, Y ⊂ R d isx k := [x 1,k , x 2,k , • • • , x n,k ] T ∈ R n×p , y k := [y 1,k , y 2,k , • • • , y n,k ] T ∈ R n×d ,where x i,k ∈ R p , y i,k ∈ Y denote the primal and dual variable of node i at each iteration k, and∇ x F (x k , y k ; ξ x k ) := • • • , ∇ x F i x i,k , y i,k ; ξ x i,k , • • • T , ∇ y F (x k , y k ; ξ y k ) := • • • , ∇ y F i x i,k , y i,k ; ξ y i,k , • • •T are the corresponding partial stochastic gradients with i.i.d. samples ξ x k , ξ y k in a compact form. Next, we will first explain the pitfalls of directly applying centralized adaptive stepsize rules to decentralized settings, and then introduce our newly proposed solution to address the challenge.For the distributed minimax optimization problem as depicted in (1) involving NC-SC objective functions, we will show shortly that the Distributed Stochastic Gradient Descent Ascent (D-SGDA) method may not converge due to the inability of time-scale separation with constant stepsizes (c.f., Figure 1 ), which is also observed in centralized settings (Lin et al., 2020; Yang et al., 2022b) . To address this issue, one can adopt the adaptive stepsize rule used in centralized TiAda (Li et al., 2023) for each individual node, which is renowned for its ability to adaptively fulfill the time-scale separation requirements. As a result, we arrive at the following Distributed TiAda (D-TiAda) algorithm.EQUATIONEQUATIONwhere γ x and γ y are the stepsizes, W is a doubly-stochastic weight matrix induced by graph G (Xiao et al., 2006) (c.f., Assumption 4), andEQUATIONwith v i,k+1 = max m x i,k+1 , m y i,k+1 , u i,k+1 = m y i,k+1 , andm x i,k+1 = m x i,k + ∇ x F i x i,k , y i,k ; ξ x i,k 2 , m y i,k+1 = m y i,k + ∇ y F i x i,k , y i,k ; ξ y i,k 2 (4)are the local accumulated gradient norm. Note that we impose a maximum operator in the preconditioner v i,k , and employ different stepsize decaying rates, i.e., 0 < β < α < 1, for the primal and dual variables, respectively. Such design allows to balance the updates of x and y, and achieves the desired time-scale separation without requiring any knowledge of parameters (Li et al., 2023) .However, in the distributed setting, such direct extension may fail to converge to a stationary point because v i,k and u i,k can be inconsistent due to the difference of local objective functions f i , In particular, we can rewrite the above vanilla distributed optimization algorithm (2) in the sense of average system of primal variables as below,EQUATIONwhere ṽ-αk T := • • • , v -α i,k -v-α k , • • • , xk := 1 T x k /n and vk := 1/n n i=1 v i,k .It is evident that, in comparison to centralized adaptive methods, an unexpected term (i.e., ṽk ) on the right-hand side (RHS) arises due to inconsistencies. This term introduces inaccuracies in the directions of gradient descent, degrading the optimization performance. The theorem presented below reveals a gap near the stationary points in a properly designed counterexample, indicating the non-convergence of D-TiAda. The proof is available in Appendix B.3. Theorem 1. There exists a distributed minimax problem in the form of Problem (1) and certain initialization such that after running D-TiAda with any 0 < β < 0.5 < α < 1 and γ x , γ y > 0, it holds that for any t = 0, 1, 2, . . . , we have,∥ ∇ x f (x t , y t ) ∥=∥ ∇ x f (x 0 , y 0 ) ∥, ∥ ∇ y f (x t , y t ) ∥=∥ ∇ y f (x 0 , y 0 ) ∥,where ∥∇ x f (x 0 , y 0 )∥ and ∥∇ y f (x 0 , y 0 )∥ can be arbitrarily large depending on the initialization.Remark 1. The counterexample we constructed consists of three nodes, forming a complete graph. Without the stepsize tracking, D-TiAda will remain stationary, and the iterates will not progress if initiated along a specific line. In this counterexample, the only stationary point is at (0, 0), but initial points along the line (c.f., Eq. ( 72)) can be positioned arbitrarily far away from this stationary point, implying the non-convergence of D-TiAda with certain initialization.Apart from the counterexample discussed in Theorem 1, we also experimentally observe the divergence of of D-SGDA and D-TiAda even in a simple scenario involving only two connected agents. This phenomenon is illustrated in Figure 1 and the functions are depicted as follows:EQUATION)It is not difficult to verify that the points on the line 3y = 5x + 2 are stationary points of f (x, y) = 1/2 (f 1 (x, y) + f 2 (x, y)). It follows from Figure 1 (a) and 1(b) that D-SGDA does not converge to a stationary point because of the lack of time-scale separation, and D-TiAda also fails to converge due to stepsize inconsistency, as shown in Figure 1 (c). In contrast, the utilization of the stepsize tracking protocol in D-AdaST ensures convergence to a stationary point, with the inconsistency in stepsizes gradually diminishing (c.f., Lemma 9). These two motivating examples effectively highlight the challenges associated with applying adaptive minimax algorithms to distributed settings.To address the issue of stepsize inconsistency across different nodes, we propose the following Distributed Adaptive minimax optimization algorithm with Stepsize Tracking protocol, termed D-AdaST, which allows us to asymptotically eliminate the stepsize inconsistency in a decentralized manner over networks. The pseudo-code for the algorithm is summarized in Algorithm 1, and can be rewritten in a compact form as follows:EQUATIONEQUATIONEQUATIONAlgorithm 1 Distributed Adaptive Minimax Method with Stepsize Tracking (D-AdaST) Initialization: x i,0 ∈ R p , y i,0 ∈ Y, buffers m x i,0 = m y i,0 = c > 0, stepsizes γ x , γ y > 0, exponential factors 0 < β < α < 1 and weight matrix W .1: for iteration k = 0, 1, • • • , each node i ∈ [n], do 2: Sample i.i.d. g x i,k = ∇ x F i x i,k , y i,k ; ξ x i,k and g y i,k = ∇ y F i x i,k , y i,k ; ξ y i,k . 3:Accumulate the gradient norm:m x i,k+1 = m x i,k + ∥g x i,k ∥ 2 , m y i,k+1 = m y i,k + ∥g y i,k ∥ 2 . 4:Compute the ratio:ψ i,k+1 = (m x i,k+1 ) α / max (m x i,k+1) α , (m y i,k+1 ) α ⩽ 1.Update primal and dual variables locally:x i,k+1 = x i,k -γ x ψ i,k+1 m x i,k+1 -α g x i,k , y i,k+1 = y i,k + γ y (m y i,k+1 ) -β g y i,k . 6:Communicate adaptive stepsizes and decision variables with neighbors:m x i,k+1 , m y i,k+1 , x i,k+1 , y i,k+1 ← j∈Ni W i,j m x j,k+1, m y j,k+1 , x j,k+1 , y j,k+1 .Projection of dual variable on the set Y: y i,k+1 ← P Y (y i,k+1 ). 8: end forwhere m x k = [• • • , m x i,k , • • • ] T , m y k = [• • • , m y i,k , • • • ]T denote the tracking variables for the accumulated global gradient norm, i.e., for z ∈ {x, y},1 T n m z k+1 = 1 n n i=1 k t=0 g z i,t 2 + m z i,0 while h z k = [• • • , ∥ g z i,k ∥ 2 , • • • ] T , and V k , U k are diagonal matrices with v i,k = max m x i,k , m y i,kand u i,k = m x i,k . Note that we also provide a variant of D-AdaST with coordinate-wise adaptive stepsizes in Algorithm 2, along with its convergence analysis in Appendix B.5. 
convergence analysis: 
 In this section, we present the main convergence results for the proposed D-AdaST algorithm and compare it with D-TiAda to show the effectiveness of the proposed stepsize tracking protocol.To this end, letting ūk := 1/n n i=1 u i,k , we define the following metrics to evaluate the level of inconsistency of stepsizes among nodes, which are ensured to be bounded by Assumption 3.ζ 2 v := sup i∈[n],k>0 v -α i,k -v-α k 2 / v-α k 2 , ζ 2 u := sup i∈[n],k>0 u -β i,k -ū-β k 2 / ū-β k 2 . (8)We consider the NC-SC setting of Problem (1) with the following assumptions that are commonly used in the existing works (c.f., Remark 2 and Remark 3). Notably, for the function and algorithm class determined by the assumptions of this work, Li et al. (2021) derived a lower complexity bound of Ω ϵ -4 and proved that such a dependency on ϵ is optimal (c.f., Remark 2).Assumption 1 (µ-strong concavity in y). Each objective function f i (x, y) is µ-strongly concave in y, i.e., ∀x ∈ R p , ∀y, y ′ ∈ Y and µ > 0,EQUATION)Assumption 2 (Joint smoothness). Each objective function f i (x, y) is L-smooth in x and y, i.e., ∀x, x ′ ∈ R p and ∀y, y ′ ∈ Y, there exists a constant L such that for z ∈ {x, y},∥∇ z f i (x, y) -∇ z f i (x ′ , y ′ )∥ 2 ⩽ L 2 ∥x -x ′ ∥ 2 + ∥y -y ′ ∥ 2 . (10)Furthermore, f i is second-order Lipschitz continuous for y, i.e., for z ∈ {x, y},EQUATION)Remark 2. Assumption 1 does not require the convexity in x and the objective function thus can be nonconvex. Assumption 1 and 2 ensure that y * (•) is smooth (c.f., Lemma 2), which is essential for achieving (near) optimal convergence rate (Chen et al., 2021; Li et al., 2023) C > 0 such that ∥∇ z F i (x, y; ξ i )∥ ⩽ C.Remark 3. Assumption 3 on unbiased stochastic gradient is widely used for establishing convergence rates of both minimization and minimax optimization methods with AdaGrad (Kavis et al., 2022; Li et al., 2023) or Adam (Zou et al., 2019; Chen et al., 2023a; Huang et al., 2024) adaptive stepsize. We note that under Assumption 2, this assumption can be easily satisfied in many real-world tasks by imposing constraints on the compact domain of f , e.g., neural networks with rectified activation (Dinh et al., 2017) and GANs with projections on the critic (Gulrajani et al., 2017) .Next, we make the following assumption on the underlying graph to ensure its connectivity. Assumption 4 (Graph connectivity). The weight matrix W induced by graph G is doubly stochastic, i.e., W1 = 1, 1 T W = 1 T and ρ W := ∥W -J∥ 2 2 < 1.Note that one can always find a proper weight matrix W compliant to the graph that satisfies Assumption 4 once the underlying graph is undirected and connected. For instance, the weight matrix can be easily determined based on the Metropolis-Hastings protocol (Xiao et al., 2006) . Moreover, this assumption is more general than that in Lian et al. (2017) ; Borodich et al. (2021) in the sense that W is not required to be symmetric, implying that certain directed graphs can be included in this assumption, e.g., directed ring and exponential graphs (Ying et al., 2021) .We are now ready to present the key convergence results in terms of the primal function Φ (x) := f (x, y * (x)) with y * (x) = argmax y∈Y f (x, y), whose proofs can be found in Appendix B.4.Theorem 2. Suppose Assumption 1-4 hold. Let 0 < β < α < 1 and the total iteration K satisfyEQUATION)with κ := L/µ to ensure time-scale separation and quasi-independence of the network. For D-AdaST, we have1 1 K K-1 k=0 E ∥∇Φ (x k )∥ 2 = Õ 1 K 1-α + 1 (1 -ρ W ) α K α + Õ 1 K 1-β + 1 (1 -ρ W ) K β .(13) Remark 4 (Near-optimal convergence). Theorem 2 implies that if the total number of iterations satisfies the conditions (12), the proposed D-AdaST algorithm converges to a stationary point exactly for Problem (1) with an Õ ϵ -(4+δ) sample complexity for arbitrarily small δ > 0, e.g., letting α = 0.5 + δ/ (8 + 2δ) and β = 0.5 -δ/ (8 + 2δ). It is worth noting that this rate is near-optimal compared to the existing lower bound of Ω ϵ -4 (Li et al., 2021) for a class of smooth NC-SC functions. Moreover, this result recovers the centralized TiAda algorithm (Li et al., 2023 ) as a special case, i.e., setting ρ W = 0, without assuming the existence of interior optimal point (c.f., Assumption 3.3 Li et al. (2023) ). To the best of our knowledge, there is no existing fully parameter-agnostic method that achieves a convergence rate of Õ ϵ -4 , even in a centralized setting. Remark 5 (Parameter-agnostic property and transient times). The above results show that D-AdaST converges without requiring to know any problem-dependent parameters, i.e., L, µ and ρ W , or tuning the initial stepsize γ x and γ y , and is thus parameter-agnostic. Moreover, we explicitly characterize the transient times (c.f., Eq. ( 12)) that ensure time-scale separation and quasi-independence of the network, respectively. Indeed, we can see that if α and β are close to each other, the time required for time-scale separation to occur increases significantly, which has been observed in (Li et al., 2023) . On the other hand, if α and β are relatively large, then Õ 1/K 1-α + 1/K 1-β dominates the other terms, indicating independence on the network. These observations highlight the trade-offs between the convergence rate and the required duration of the transition phase.For proper comparison, we also derive an upper bound for D-TiAda as follows. Together with the lower bound in Theorem 1, we demonstrate that without the stepsize tracking mechanism, the inconsistency among local stepsizes prevents D-TiAda from converging in the distributed setting. Corollary 1. Under the same conditions of Theorem 2. For the proposed D-TiAda, we haveEQUATION)4 ExperimentsIn this section, we conduct experiments to validate the theoretical findings and demonstrate the effectiveness of the proposed algorithm on real-world machine learning tasks. We compare the proposed D-AdaST with the distributed variants of AdaGrad (Duchi et al., 2011) , TiAda (Li et al., 2023) and NeAda (Yang et al., 2022b) , namely D-AdaGrad, D-TiAda and D-NeAda, respectively. These experiments run across multiple nodes with different networks, and we consider heterogeneous distributions of local objective functions/datasets. For example, each node can only access samples with a subset of labels on MNIST and CIFAR-10 datasets, which is a common scenario in decentralized and federated learning tasks (Sharma et al., 2023; Huang et al., 2022) . The experiments cover three main tasks: synthetic function, robust training of the neural network, and training of Wasserstein GANs (Heusel et al., 2017) . For the exponential factors of stepsize, we set α = 0.6 and β = 0.4 for both D-TiAda and D-AdaST. More detailed settings and additional experiments with different initial stepsizes, data distributions and choices of α and β can be found in Appendix A.Synthetic example. We consider a distributed minimax problem with the following NC-SC local objective functions over exponential networks with n = 50 (ρ W = 0.71) and n = 100 (ρ W = 0.75).EQUATIONwhere L i ∼ U (1.5, 2.5). The local gradient of each node is computed with an additive N (0, 0.1) Gaussian noise. It follows from Figure 2 (a) and 2 (b) that the proposed D-AdaST algorithm outperforms other distributed adaptive methods for both initial stepsize settings, especially in cases with a favorable initial stepsize ratio, as illustrated in plots (b) and (d) where γ x /γ y = 0.2. Similar observation can be found in Figure 2 (c) and 2 (d), demonstrating the effectiveness of D-AdaST.Robust training of neural networks. Next, we consider the task of robust training of neural networks, in the presence of adversarial perturbations on data samples (Sharma et al., 2022; Deng and Mahdavi, 2021) . The problem can be formulated as minx max y 1/n n i=1 f i (x; ξ i + y) -η ∥y∥ 2 ,where x denotes the parameters of the model, y denotes the perturbation and ξ i denotes the data sample of node i. Note that if η is large enough, the problem is NC-SC. We conduct experiments on MNIST dataset over different networks, e.g., ring graph, exponential (exp.) graph (Ying et al., 2021) and dense graph with n/2 edges for each node. We consider a heterogeneous scenario in which each node possesses only two distinct classes of labeled samples, resulting in heterogeneity among the local datasets across nodes, while the data is i.i.d within each node.In Figure 3 , we compare D-AdaST with D-AdaGrad, D-TiAda and D-NeAda, using adaptive stepsizes in AdaGrad (first row) and Adam (second row, name suffixed with Adam) respectively, it can be observed from the first three columns that the proposed D-AdaST outperforms the others on three different graphs and it is not very sensitive to the graph connectivity (i.e., ρ W ), demonstrating the quasi-independence of network as indicated in Theorem 2. It should be noted that Adam-like algorithms exhibit more fluctuations in the later stages of optimization as the gradient norm vanishes, leading to an inevitable increase in the Adam stepsize as the optimization process converges (Kingma and Ba, 2014) . In plots (d) and (h), we further demonstrate that D-AdaST can scale efficiently with respect to the number of nodes, while keeping a constant batch-size of 64 for each node. This showcases the algorithm's ability to handle large-scale distributed scenarios effectively.Generative Adversarial Networks. We further illustrate the effectiveness of D-AdaST on another popular task of training GANs, which has a generator and a discriminator used to generate and distinguish samples respectively (Goodfellow et al., 2014) . In this experiment, we train Wasserstein GANs (Gulrajani et al., 2017) on CIFAR-10 dataset in a decentralized setting where each discriminator is 1-Lipschitz and has access to only two classes of samples. We compare the inception score of D-AdaST with D-Adam and D-TiAda adopting Adam-like stepsizes in Figure 4 . It can be observed from the figure that D-AdaST achieves higher inception scores in three cases with different initial stepsizes, and has a small score loss as the initial step size changes. We believe that this example shows the great potential of D-AdaST in solving real-world problems.  
conclusion: 
 We introduced a new distributed adaptive minimax method, D-AdaST, designed to tackle the issue of non-convergence in nonconvex-strongly-concave minimax problems caused by the inconsistencies among locally computed adaptive stepsizes. Vanilla distributed adaptive methods could suffer from such inconsistencies, as highlighted by the carefully designed counterexamples for demonstrating their potential non-convergence. In contrast, our proposed method employs an efficient adaptive stepsize tracking protocol that not only ensures the time-scale separation, but also guarantees stepsize consistency among nodes and thus effectively eliminates steady-state errors. Theoretically, we showed that D-AdaST can achieve a near-optimal convergence rate of Õ ϵ -(4+δ) with any arbitrarily small δ > 0. Extensive experiments on both real-world and synthetic datasets have been conducted to validate our theoretical findings across various scenarios. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: NA Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Justification: The license/copyright information of the code and dataset in this paper is clear. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: In this section, we provide detailed experimental settings and perform additional experiments on the task of training robust neural networks with different choices of hyper-parameters. All experiments are deployed in a server with Intel Xeon E5-2680 v4 CPU @ 2.40GHz and 8 Nvidia RTX 3090 GPUs, and implemented using distributed communication package torch.distributed in PyTorch 2.0, where each process serves as a node, and we use inter-process communication to mimic communication between nodes. For the AdaGrad-like algorithms considered in the experiments of training neural networks, similar to the Adam-like stepsize, we adopt a coordinate-wise adaptive stepsize rule as commonly used in existing centralized adaptive methods (Yang et al., 2022b; Li et al., 2023) .Moreover, since we attempt to develop a parameter-agnostic algorithm that does not need much effort in tuning hyper-parameters, we set α = 0.6 and β = 0.4 for all tasks in the main text, and evaluate the effect of the choices of α and β on the performance of D-AdaST individually in an additional experiment on the synthetic objective function as shown in Appendix A.4.A Robust training of neural network. In this task, we train CNNs with three convolutional layers and one fully connected layer on MNIST dataset containing images of 10 classes. Each layer adopts batch normalization and ELU activation. The total batch-size is 1280, and the batch-size of each node during training is 1280/n. For Adam-like algorithms, we set the first and second moment parameters as β 1 = 0.9, β 2 = 0.999 respectively. Since NeAda is a double-loop algorithm, for fair comparison, we imply D-AdaGrad and D-Adam using 15 iterations of inner loop in this task.Generative Adversarial Networks. In this task, we train Wasserstein GANs on CIFAR-10 dataset, where the model used for discriminator is a four layer CNNs, and for generator is a four layer CNNs with transpose convolution layers. The total batch-size is 1280, and the batch-size of each node during training is 128 with 10 nodes. For Adam-like algorithms, we use β 1 = 0.5, β 2 = 0.9. To obtain the inception score, we use 8000 artificially generated samples to feed the previously trained inception network.In this part, we conduct additional experiments on robust training of CNNs on MNIST dataset considering a variety of settings. We compare the convergence performance of D-AdaST with D-AdaGrad, D-TiAda and D-NeAda using adaptive stepsizes of AdaGrad and Adam. Unless otherwise specified, the total batch-size is set to 1280; the initial stepsizes for x and y are assigned as γ x = 0.01, γ y = 0.1 for AdaGrad-like algorithms, and γ x = γ y = 0.1 for Adam-like algorithms.Specifically, we consider two extra graphs that are more sparse and more dense, respectively in Figure 5 , e.g., directed ring and fully-connected (fc) graphs. We consider more initial stepsizes settings for x and y respectively in Figure 6 . Further, we also consider different data distributions where each node has samples from 4 of the 10 classes in Figure 7 . Finally, we perform a comparison experiment with 40 nodes in Figure 8 . Under all settings, the proposed D-AdaST outperforms the others, demonstrating the superiority of D-AdaST.We provide additional experiments of training GANs on a more complicated dataset CIFAR-100 to further illustrate the effectiveness of the proposed D-AdaST, as shown in Figure 9 . We use the entire training set of CIFAR-100 with coarse labels (20 classes) to train GANs over networks, where each node is assigned with four distinct classes of labeled samples. Under the same settings as in Figure 4 (a), it can be observed that D-AdaST outperforms the others in terms of the inception score. Together with other experimental results in the main text, we believe that we have demonstrated the effectiveness of the proposed D-AdaST method and its potential for further real-world applications. In this part, we evaluate the effect of the choices of α and β on the performance of D-AdaST. In particular, we provide an additional experimental result on the synthetic quadratic objective functions (15) with a larger ratio of initial stepsizes, i.e., γ x /γ y = 20 (indicating faster minimization and slower maximization processes at the beginning). As shown in Figure 10 , it can be observed that the transient time (iteration before the inflection point) becomes longer as α -β decreases, while the convergence rate is relatively faster, which is consistent with Theorem 2 and the result in the centralized TiAda algorithm (c.f., Figure 5 , Li et al., 2023) .We recall here some definitions used in the main text. The averaged variables and the inconsistency are defined as follows:xk := 1 T n x k , vk := 1 n n i=1 v i,k , ṽ-α k T := • • • , v -α i,k -v-α k , • • • , ȳk := 1 T n y k , ūk := 1 n n i=1 u i,k , ũ-β k T := • • • , u -β i,k -ū-β k , • • • .The inconsistency of stepsizes of the primal and dual variables is defined as follows:ζ 2 v := sup i∈[n],k>0 v -α i,k -v-α k 2 / v-α k 2 , ζ 2 u := sup i∈[n],k>0 u -β i,k -ū-β k 2 / ū-β k 2 .Proof Sketch. The convergence analysis of the main results in Theorem 2 is mainly based on carefully analyzing the average system as shown in ( 5), and the difference between the distributed system and the averaged system. In general, under Assumption 1-4, we first give a telescoped descent lemma from 0 to K -1 iterations in Lemma 3, which is upper bounded by the following key error terms:• S 1 := 1 nK K-1 k=0 E v-α k+1 ∥∇ x F (x k , y k ; ξ x k )∥ 2 :The asymptotically decaying terms by adopting adaptive stepsize;• S 2 := 1 nK K-1 k=0 E ∥x k -1x k ∥ 2 + ∥y k -1ȳ k ∥ 2 :The consensus error of x and y between the distributed system and the average system;• S 3 := 1 K K-1 k=0 E [f (x k , y * (x k )) -f (x k , ȳk )]:The optimality gap in dual variable y;• S 4 := 1 K K-1 k=0 E (ṽ -α k+1 ) T nv -α k+1 ∇ x F (x k , y k ; ξ x k ) 2 :The inconsistency of stepsize of x.Next, we prove the contraction properties of these terms in Lemma 4-8 and Lemma 9 respectively. Finally, these results are integrated into the descent lemma to complete the proof. We note that the proof is not trivial in the sense that these terms are coupled and therefore are needed to be carefully analyzed. This proof can also be adapted to analyze the coordinate-wise adaptive stepsize variant of D-AdaST as explained in Appendix B.5, which is of independent interest.In this part, we provide several supporting lemmas that have been shown in the existing literature, which are essential to the subsequent convergence analysis.Lemma 1 (Lemma A.2 in Yang et al. (2022b) ). Let {x t }T -1 t=0 be a sequence of non-negative real numbers, x 0 > 0 and α ∈ (0, 1). Then we have,EQUATION)When α = 0, we haveEQUATION)Lemma 2. Suppose Assumption 1 and 2 hold. Define Φ (x) := f (x, y * (x)) as the envelope function and y * (x) = argmax y∈Y f (x, y). Then, we have, • Φ (•) is L Φ -smooth with L Φ = L (1 + κ),In this subsection, we give the key lemmas to help the analysis of the main results. For simplicity, we define∆ k := ∥x k -1x k ∥ 2 + ∥y k -1ȳ k ∥2 as the consensus error for primal and dual variables. Then, we have the following lemmas.Lemma 3 (Descent lemma). Suppose Assumption 1-4 hold. Then, we have Proof. By the smoothness of Φ given in Lemma 2, i.e.,EQUATIONΦ (x k+1 ) -Φ (x k ) ⩽ ⟨∇Φ (x k ) , xk+1 -xk ⟩ + L Φ 2 ∥x k+1 -xk ∥ 2 ,and noticing that the scalar vk , ūk are random variables, we haveEQUATIONwhere we have used the definition of xk+1 as presented in (5). Then, we bound the inner-product terms on the RHS. Firstly,EQUATION)wherein the last inequality we have used the smoothness of the objective functions. Then, for the second inner-product in (19), using Young's inequality we getEQUATIONThen, for the last term on the RHS of ( 18), recalling the definition of stepsize inconsistency in (8), we haveEQUATION)Plugging the obtained inequalities into (18) and telescoping the terms, we getEQUATIONNow it remains to bound the first term on the RHS of the above inequality. With the help of Assumption 3, we haveEQUATIONNoticing thatE ∥ȳ k -y * (x k )∥ 2 ⩽ 2 µ E [f (x k , y * (x k )) -f (x k , ȳk )],we thus complete the proof.Next, we need to bound the last four terms S 1 -S 4 in (18) respectively. For S 1 , we have the asymptotic convergence for both primal and dual variables in the following lemma. Lemma 4. Suppose Assumption 1-4 hold. Then, we haveEQUATIONandEQUATION)Proof. With the help of Lemma 1 and Assumption 3, taking the primal variable x as an example, and noticing that v i,0 > 0, i ∈ [n], we have1 K K-1 k=0 E v-α k+1 ∥∇ x F (x k , y k ; ξ x k )∥ 2 = 1 K K-1 k=0 1 n n i=1 ∇ x F i x i,k , y i,k ; ξ x i,k 2 vα k+1 ⩽ 1 K K-1 k=0 1 n n i=1 ∇ x F i x i,k , y i,k ; ξ x i,k 2 k t=0 1 n n j=1 ∇ x F j x j,t , y j,t ; ξ x j,t 2 α ⩽ 1 1 -α 1 K K-1 k=0 1 n n i=1 ∇ x F i x i,k , y i,k ; ξ x i,k 2 1-α ⩽ C 2-2α (1 -α) K α .The similar result can be obtained for dual variable y and we thus complete the proof.Next, we bound the the consensus error term S 2 in the following lemma.Lemma 5. Suppose Assumption 1-4 hold. Then, we haveEQUATIONwhere I [•] ∈ {0, 1} is the indicator for specific condition, and the initial consensus error ∆ 0 can be set to 0 with proper initialization.Proof. By the updating rule of the primal variable, we haveEQUATION)where we have used Young's inequality. Then, by the definition of ζ v in (8), we haveEQUATION)and thusEQUATION)Then, we bound the last term on the RHS of the above inequality by Lemma 4. For the case α < 1/2, by Assumption 3 we haveK-1 k=0 E v-2α k+1 ∥∇ x F (x k , y k ; ξ x k )∥ 2 = K-1 k=0 n i=1 E    ∇ x F i x i,k , y i,k ; ξ x i,k 2 v2α k+1    ⩽ n KC 2 1-2α(1 -2α) .(31)For the case α ⩾ 1/2, with the help of Lemma 1, we haveEQUATION)For the dual variable, we havey k+1 = P Y W y k + γ y U -β k+1 ∇ y F (x k , y k ; ξ y k ) = W y k + γ y ∇ y Ĝwhere∇ y Ĝ = 1 γ y P Y W y k + γ y U -β k+1 ∇ y F (x k , y k ; ξ y k ) -W y k .Then, using Young's inequality with parameter λ, we haveE ∥y k+1 -1ȳ k+1 ∥ 2 = E W y k + γ y ∇ y Ĝ -J W y k + γ y ∇ y Ĝ 2 ⩽ (1 + λ) ρ W E ∥y k -Jy k ∥ 2 + 1 + 1 λ E P Y W y k + γ y U -β k+1 ∇ y F (x k , y k ; ξ y k ) -W y k 2 ⩽ 1 + ρ W 2 E ∥y k -Jy k ∥ 2 + 1 + ρ W 1 -ρ W E P Y W y k + γ y U -β k+1 ∇ y F (x k , y k ; ξ y k ) -W y k 2 .Noticing that W y k = P Y (W y k ) holds for convex set Y, we getE ∥y k+1 -1ȳ k+1 ∥ 2 ⩽ 1 + ρ W 2 E ∥y k -Jy k ∥ 2 + 1 + ρ W 1 -ρ W E P Y W y k + γ y U -β k+1 ∇ y F (x k , y k ; ξ y k ) -P Y (W y k ) 2 ⩽ 1 + ρ W 2 E ∥y k -Jy k ∥ 2 + 1 + ρ W 1 -ρ W E γ y U -β k+1 ∇ y F (x k , y k ; ξ y k ) 2 ⩽ 1 + ρ W 2 E ∥y k -Jy k ∥ 2 + 4γ 2 y 1 + ζ 2 u (1 -ρ W ) E ū-2β k+1 ∥∇ y F (x k , y k ; ξ y k )∥ 2 ,where we have used the non-expansiveness of projection operator. Then, we haveK-1 k=0 E ∥y k -1ȳ k ∥ 2 ⩽ 2 1 -ρ W E ∥y 0 -Jy 0 ∥ 2 + 8γ 2 y 1 + ζ 2 u (1 -ρ W ) 2 K-1 k=0 E ū-2β k+1 ∥∇ y F (x k , y k ; ξ y k )∥ 2 .Similar to the primal variable, we can bound the last term above, which completes the proof.Next, we need to bound the term S 3 i.e., the optimality gap in dual variable. The intuition of the proof relies on the adaptive two time-scale protocol, that is, for given α and β, we try to find the threshold of the iterations k 0 , after which the inner sub-problem can be well solved (faster) to ensure that the computation of outer sub-problem can be solved accurately (slower). In specific, we suppose that there is a constantEQUATIONwhereEQUATION)Proof. Using Young's inequality with parameter λ k , we getEQUATION)Recalling thaty k+1 = P Y W y k + γ y U -β k+1 ∇ y F (x k , y k ; ξ y k ) , we further define ŷk+1 = W y k + γ y U -β k+1 ∇ y F (x k , y k ; ξ y k ) .Then, for the first term on the RHS of ( 35), by the non-expansiveness property of projection operator P Y (•) (c.f., Lemma 1 in (Nedic et al., 2010 )), we haveEQUATIONwherein the last inequality we have used the fact ∥W ∥ 2 2 ⩽ 1. Then, multiplying by 1/ γ y ū-β k+1 on both sides of (35) we get1 nγ y ū-β k+1 ∥y k+1 -1y * (x k )∥ 2 ⩽ 1 + λ k λ k γ y ū-β k+1 ∥ȳ * (x k ) -ȳ * (x k+1 )∥ 2 + (1 + λ k ) 1 nγ y ū-β k+1 ∥y k -1y * (x k )∥ 2 + γ y nū -β k+1 U -β k+1 ∇ y F (x k , y k ; ξ y k ) 2 -(1 + λ k ) 1 n n i=1 2 g y i,k , y i,k -y * (x k ) - 1 n n i=1 2 u -β i,k+1 -ū-β k+1 ū-β k+1 g y i,k , y i,k -y * (x k ) .(37) For the inner-product terms on the RHS, taking expectation on both sides, we haveEQUATIONwhere we have used Young's inequality and strong-concavity of f i , andEQUATION)For the consensus error of dual variable on the objective function, using strong-concavity of f i and Jensen's inequality, we haveEQUATION)Letting λ k = µγ y ū-β k+1 /2, we getEQUATION)By the κ-smoothness of y * , we haveEQUATIONTelescoping the obtained terms from 0 to k 0 -1 and noticing that ūk ⩽ G for k ⩽ k 0 -1 we complete the proof.For the second phase, i.e., k ⩾ k 0 , we have the following lemma.Lemma 7 (Second phase). Suppose Assumption 1-4 hold.EQUATIONProof. Firstly, by the non-expansiveness of projection operator, we haveEQUATIONThen, for the first inner-product term on the RHS, lettingEQUATIONwherein the last inequality we have used the fact that y * is κ-Lipschitz. Then, using Young's inequality with parameter λ k , we getEQUATIONFor the second inner-product term on the RHS, noticing that y * is L = κ (1 + κ) 2 smooth given in Lemma 2, we haveEQUATIONwherein the last inequality we have used Young's inequality with parameter τ . Plugging the obtained inequalities into (44), we getEQUATIONSetting the parameters for Young's inequalities we used as follows,EQUATIONthen we getEQUATIONRecalling that1 n n i=1 E 1 γ y ū-β k+1 ∥ŷ i,k+1 -ȳ * (x k )∥ 2 ⩽ 1 n n i=1 E 1 -3µγ y ū-β k+1 /4 γ y ū-β k+1 ∥y i,k -ȳ * (x k )∥ 2 + 8κL n E ∥x k -1ȳ k ∥ 2 + 2γ y 1 + ζ 2 u n E ū-β k+1 ∥∇ y F (x k , y k ; ξ k )∥ 2 -E [2 (f (x k , ȳ * (x k )) -f (x k , ȳk ))] + 8 µ E   ũ-β k+1 nū -β k+1 ∇ y F (x k , y k ; ξ y k ) 2   + 2CE 1 n ∥y k -1ȳ k ∥ 2 ,and multiplying by 2 (2+µγy ū-β k+1 )γy ū-β k+1 on both sides of (50), we obtain thatEQUATIONTelescoping the terms from t 0 to K -1, we getEQUATIONNext we need to further bound the running sums ofE [E 2,k ], E [E 3,k ] and E [E 4,k ] respectively. For E [E 2,k ],with the help of Assumption 2 and noticing that ūkEQUATIONThen, for the term E [E 3,k ], noticing that ūk+1 ⩽ vk+1 and vk+1 ⩾ v1 , we haveEQUATION)For the term E 4,k , we denotee k := γ x γ y ū-β k+1 1 n n i=1 (ŷ i,k+1 -y * (x k )) T ∇y * (x k ) ∇ x Fk T 1 n + ṽ-α k+1 nv -α k+1 ,then we haveEQUATIONwhere we have used the Lipschitz continuity of y * given in Lemma 2 and Assumption 3. Then, noticing that E ∇ x Fk = 0, we obtainEQUATIONTherefore, combining the obtained inequalities, we complete the proof. Now, it remains to bound the term E 1,k .Lemma 8. Suppose Assumption 1-4 hold. Then, we haveEQUATION)Proof. Recalling the definition of E 1,k as given in (34), we haveEQUATION)Next, we show that the term1 2γy ū-β k+1 -1 2γy ū-β k -µ8 is positive for only a constant number of iterations. If the term is positive at iteration k, then we haveEQUATIONwherein the last inequality we used Bernoulli's inequality. Then we have the following two conditions,EQUATIONwhich implies that we have at most4βC 2 µγ y 1 1-β 4β µγ y ū1-β 1 (61)constant number of iterations when the term is positive. Furthermore, when the term is positive, by the inequality (59), we haveEQUATIONwhere we have used the concavity of f i in y and Assumption 3. Then, we haveEQUATIONwhich completes the proof.Next, we show in the following lemma that the inconsistency terms, as described in (5), exhibit asymptotic convergence for the proposed D-AdaST algorithm.Lemma 9 (Convergence of inconsistency terms). Suppose Assumption 1-4 hold. For the proposed D-AdaST in Algorithm 1, we have1 K K-1 k=0 E   ṽ-α k+1 T nv -α k+1 ∇ x F (x k , y k ; ξ x k ) 2   ⩽ 1 n 1-α 4ρ W (1 -ρ W ) 2 α (1 + ζ v ) ζ v C 2-α (1 -α) K α ,(64) andEQUATIONProof. By the definition of v i,k in (3), we haveEQUATIONNoticing thatEQUATION)By Lemma 4, we get1 K K-1 k=0 E   ṽ-α k+1 T nv -α k+1 ∇ x F (x k , y k ; ξ x k ) 2   ⩽ (1 + ζ v ) ζ v E    1 n n i=1 vα k+1 -v α i,k+1 1 K K-1 k=0 1 n n i=1 g x i,k 2 vα k+1    ⩽ (1 + ζ v ) ζ v E 1 n n i=1 vα k+1 -v α i,k+1 C 2-2α (1 -α) K α ⩽ (1 + ζ v ) ζ v 1 n E ∥v k+1 -1v k+1 ∥ 2α C 2-2α (1 -α) K α . (68)Next, for the term of inconsistency of the stepsize ∥v k -1v k ∥ 2 , we consider two cases due to the max operator we used. At iteration k, for the case m x k ⩾ m y k with ∥m x 0 -1 mx 0 ∥ 2 = 0, we haveEQUATION)For the case m x k < m y k , with ∥m y 0 -1 my 0 ∥ 2 = 0,EQUATIONCombining these two cases, and using Lemma 4 and the fact ∥v α k -1v α k ∥ 2 ⩽ ∥v k -1v k ∥ 2α for α ∈ (0, 1), we obtain the result for primal decision variable. Following the same proof, we can also derive the result for dual decision variable. We thus complete the proof.We further give the following lemma to show that the inconsistency of stepsize remains uniformly bounded for the vanilla D-TiAda algorithm as given in (2).Lemma 10 (Inconsistency for D-TiAda). Suppose Assumption 1-4 hold. Then, for D-TiAda, we haveEQUATION)Proof. By the definition of inconsistency of stepsizes in (8) and Assumption 3 on bounded gradient, we immediately get the result.Proof of Theorem 1. Consider a complete graph with 3 nodes where the functions corresponding to the nodes are as follows:f 1 (x, y) = - 1 2 y 2 + xy - 1 2 x 2 , f 2 (x, y) = f 3 (x, y) = - 1 2 y 2 -(1 + 1 a + 1 b )xy - 1 2 x 2 ,where a = 2-1 2α-1 and b = 2 -1 2β-1 .Notice that the only stationary point of f (x, y) = (f 1 (x, y) + f 2 (x, y) + f 3 (x, y))/3 is (0, 0). We denote gEQUATIONwhere we haveg x 1,0 = y 0 -x 0 = - 2ab + a + b ab + a x 0 g x 2,0 = g x 3,0 = -1 + 1 b + 1 a y 0 -x 0 = 2ab + a + b a 2 (b + 1) x 0 g y 1,0 = x 0 -y 0 = 2ab + a + b ab + a x 0 g y 2,0 = g y 2,0 = - 2ab + a + b ab(b + 1) x 0 .Note that by our assumptions of the range of α and β, we have a < b. Thus, we have|g x 1,0 | = |g y 1,0 | and |g x 2,0 | > |g y 2,0 |,which means g x 2,0 would be chosen in the maximum operator in the denominator of TiAda stepsize for x. Therefore, after one step, we havex 1 = x 0 -η x g x 1,0 |g x 1,0 | 2 α + g x 2,0 |g x 2,0 | 2 α + g x 3,0 |g x 3,0 | 2 α =0 y 1 = y 0 -η y g y 1,0 |g y 1,0 | 2 β + g y 2,0 |g y 2,0 | 2 β + g y 3,0 |g y 3,0 | 2 β =0 .Next, we will use induction to show that x and y will stay in x 0 and y 0 for any iteration. Assuming for all iterations k in 1, . . . , t, x k = x 0 and y k = y 0 , then we have in next stepx t+1 = x t -η x g x 1,0 t • |g x 1,0 | 2 α + g x 2,0 t • |g x 2,0 | 2 α + g x 3,0 t • |g x 3,0 | 2 α . Note that g x 1,0 = -a • g x 2,0. Then, we getx t+1 = x t -η x -p • g x 2,0 t α • a 2α • |g x 2,0 | 2α + 2g x 2,0 t α • |g x 2,0 | 2α = x t - g x 2,0 t α • |g x 2,0 | 2α 2 -a 1-2α=0 (by definition of a) = x t . Similarly, we can show that y t+1 = y t . Therefore all iterates will stay at (x 0 , y 0 ) if initialized at line y = -ab+b ab+a x, which implies that the initial gradient norm can be arbitrarily large by picking x 0 to be large.Proof of Theorem 2. Combining the results obtained in Lemma 6, 7 and 8, we getEQUATION)Letting the separation point between the two phases discussed in Lemma 6 and 7 satisfyEQUATIONthen, plugging above inequality into (18), with the help of Lemma 4-8 and Lemma 9, we getEQUATIONwhereEQUATIONE 0 := 4κL Kγ y ū-β 1 n E ∥y 0 -1y * (x 0 )∥ 2 + 16κ 2 4βC 2 2+ 1 1-β Kµ 2+ 1 1-β γ 2+ 1 1-β y ū2-2β 1 , E G := 16γ 2 x κ 4 1 + ζ 2 v G 2β γ 2 y C 2-4α (1 -2α) K 2α I α<1/2 + 1 + log v K -log v 1 K v2α-1 1 I α⩾1/2 , E W := 32 8κL + 3L 2 ρ W γ 2 x 1 + ζ 2 v (1 -ρ W ) 2 C 2-4α (1 -2α) K 2α I α<1/2 + 1 + log v K -log v 1 K v2α-1 1 I α⩾1/2 + 32 8κL + 3L 2 ρ W γ 2 y 1 + ζ 2 u (1 -ρ W ) 2 C 2-4β (1 -2β) K 2β I β<1/2 + 1 + log u K -log v 1 K ū2β-1 1 I β⩾1/2 .Letting the total iteration K satisfy the conditions given in ( 12) such that the terms E 0 , E G and E W are dominated by the others, we thus complete the proof.Proof of Corollary 1. With the help of Lemma 10, we can directly adapt the proof of Theorem 2 to get the result in (14).In this subsection, we show how to extend our convergence analysis of D-AdaST to the coordinatewise adaptive stepsize (Zhou et al., 2018) variant. We first present this variant in Algorithm 2, which can be rewritten in a compact form with the Hadamard product denoted by ⊙.Algorithm 2 D-AdaST with coordinate-wise adaptive stepsize Initialization: x i,0 ∈ R p , y i,0 ∈ Y, buffers m x i,0 , m y i,0 > 0, stepsizes γ x , γ y > 0 and 0 < β < α < 1.1: for iteration k = 0, 1, • • • , each node i ∈ [n], do 2: Sample i.i.d ξ xi,k and ξ y i,k , compute:EQUATION3:Accumulate the gradient with Hadamard product:m x i,k+1 = m x i,k + g x i,k ⊙ g x i,k , m y i,k+1 = m y i,k + g y i,k ⊙ g y i,k 4:Compute the ratio:EQUATION⩽ 1.Update primal and dual variables locally:x i,k+1 = x i,k -γ x ψ i,k+1 m x i,k+1 -α ⊙ g x i,k , y i,k+1 = y i,k + γ y m y i,k+1 -β ⊙ g y i,k . 6:Communicate parameters with neighbors:m x i,k+1 , m y i,k+1 , x i,k+1 , y i,k+1 ← j∈Ni W i,j m x j,k+1, m y j,k+1 , x j,k+1 , y j,k+1 .Projection of dual variable on to set Y: y i,k+1 ← P Y (y i,k+1 ). 8: end forEQUATIONEQUATIONEQUATIONwhereh x k = • • • , g x i,k ⊙ g x i,k , • • • T ∈ R n×p , h y k = • • • , g y i,k ⊙ g y i,k , • • • T ∈ R n×d ,and the matrices U α k and V β k are redefined as follows:EQUATIONwhere [•] j denotes the j-th element of a vector.Recalling the definitions of inconsistency of stepsize in (8), we give the following notations:EQUATIONandζ 2 V = sup k⩾0 V -α k -v-α k 11 T p 2 np v-α k 2 , ζ2 v = sup k⩾0      V -α k -(V k J p ) -α 2 np v-α k 2      , ζ 2 U = sup k⩾0      U -β k -ū-β k 11 T d 2 nd ū-β k 2      , ζ2 u = sup k⩾0      U -β k -(U k J d ) -β 2 nd ū-β k 2     .Building upon the established definitions of coordinate-wise stepsize inconsistency, the subsequent lemma is presented to show the non-convergence of the inconsistency term compared to Lemma 9.Lemma 11 (Inconsistency, coordinate-wise). Suppose Assumption 1-4 hold. For the proposed D-AdaST algorithm, we have1 K K-1 k=0 E   1 T nv -α k+1 Ṽ -α k+1 ⊙ ∇ x F (x k , y k ; ξ x k ) 2   ⩽ 2 (1 + ζ v ) ζ v 1 n 1-α 4C 2 ρ W (1 -ρ W ) 2 α C 2-2α (1 -α) K α + 2np ζ2 v C 2 (79)andEQUATION)In contrast, for D-TiAda, we have1 K K-1 k=0 E   1 T nv -α k+1 Ṽ -α k+1 ⊙ ∇ x F (x k , y k ; ξ x k ) 2   ⩽ pζ 2 V C 2 , 1 K K-1 k=0 E   1 T nū -β k+1 Ũ -β k+1 ⊙ ∇ y F (x k , y k ; ξ y k ) 2   ⩽ dζ 2 U C 2 .(81)Proof. For the coordinate-wise adaptive stepsize, with the definitions of Frobenius norm and Hadamard product, we haveEQUATIONFor the first term on the RHS, according to the definitions given in (78), we haveE   1 T nv -α k+1 (V k+1 J) -α -v-α k+1 11 T p ⊙ ∇ x F (x k , y k ; ξ x k ) 2   ⩽ E 1 n 2 v-2α k+1 n i=1 vα i,k+1 -vα k+1 2 ∇ x f i x i,k , y i,k ; ξ x i,k 2 .(83)Then, for the second part, we haveEQUATION)where the term ζ2 v is not guaranteed to be convergent because the stepsizes between the different dimensions of each node are not consistent. Then, similar to the proof of Lemma 9, we can obtain the result presented in (79).Next, noticing that for D-TiAda,E   1 T nv -α k+1 Ṽ -α k+1 ⊙ ∇ x F (x k , y k ; ξ x k ) 2   ⩽ 1 n E   Ṽ -α k+1 v-α k+1 2 ∥∇ x F (x k , y k ; ξ x k )∥ 2   ⩽ pζ 2 V C 2 ,(85) and using Lemma 9, we complete the proof.Theorem 3. Suppose Assumption 1-4 hold. Let 0 < β < α < 1 and the total iteration satisfyK = Ω   max    γ 2 x κ 4 γ 2 y 1 α-β , 1 (1 -ρ W ) 2 max{ 1 α , 1 β }      .to ensure time-scale separation and quasi-independence of network. For D-AdaST with coordinatewise adaptive stepsize, we haveEQUATION)Proof. With the help of Lemma 11 and the obtained result (75) in the proof of Theorem 2, we can derive the convergence results for D-AdaST with coordinate-wise adaptive stepsize.Remark 6. In Theorem 3, we show that the coordinate-wise variant of D-AdaST exhibits a steadystate error in its upper bound. This error depends on the number of nodes and the dimension of the problem, which stems from the stepsize inconsistency in each dimension of the local decision variables for each node (c.f., Line 3 of Algorithm 2).• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).The complete convergence result can be found in (75) in Appendix. 


Decision: This paper introduces an adaptive-stepsize method for distributed minimax optimization. The authors construct counterexamples, showing that directly applying adaptive methods designed for centralized problems results in non-convergence in the distributed setting. Then, they propose an adaptive stepsize tracking protocol that involves transmitting two extra scalar variables to ensure consistency among stepsizes of different nodes. Theoretical guarantees are established, matching (nearly) the convergence rate in the non-distributed setting. This paper is well-written and the contributions are solid. Although the reviewers point several issues that need to be addressed in the future work, the strengths outweigh the weaknesses.

Reviews: review: paper_summary: paper_summary: The paper introduces a method for distributed minimax optimization, for the scenario that various "agents" each hold part of a data set locally, and aim to coordinate to find the minimax solution of some criterion. Here, the criterion consists of the average of local cost functions, which are assumed to be smooth but non-convex-strongly-concave. Each agent is assumed to able to compute a stochastic gradient at each iteration, which can be communicated across the neighboring agents, who collectively communicate according to a given, known graph structure. 

In the nondistributed setting, known gradient-based methods depend on hyper-parameter tuning, in particular in choosing the stepsizes. When such a method is properly adaptive, it finds the right stepsize without apriori knowledge based on continuous adjustment per iteration.

The authors construct counterexamples showing that directly applying adaptive methods designed for centralized problems results in non-convergence in distributed setting. The authors then propose an adaptive stepsize tracking protocol that involves transmitting two extra scalar variables to ensure consistency among stepsizes of different nodes. The authors give theoretical guarantees, matching (nearly) the convergence rate in the non-distributed setting. Furthermore, the authors exhibit their method on various real-world datasets to further underline their theoretical findings.
strength_weakness: strength_weakness: * Whilst I think the problem that the authors address is interesting, and within their scope they provide satisfying answers, I also think that this scope is rather limited. There are many things to investigate here in terms of e.g. network topology, communication efficiency, the influence of various noise sources. The authors stay within a set of rather stringent assumptions and do not capture the effect of these problem characteristics fully.

* In high-dimensional settings, which the authors aim to address, achieving zero bias for stochastic gradients is not always feasible. Additionally, confirming the absence of bias in the gradient estimator is challenging to verify in practice. Does the method still work without this assumption? What if the bias is very small? 

* Similarly, the uniform bound on the gradient seems rather strong. Is this really required by the analysis?
questions: questions: Some of the figures are rather difficult to read when printed on paper as they are rather small, but were readable digitally.

* Is there a reason the constant $C$ does not appear in e.g. (13)?

* I do not see the point of Corollary 1. As I understand it, this is an upper bound for D-TiAda. The authors say that this result is provided for "proper comparison". How does Corollary 1 provide any comparison if it is only an upper bound? Isn't Theorem 1 to provide the comparison that the authors are after?
limitations: limitations: Within the scope of the article, I think limitations are appropriately addressed.
paper_summary: paper_summary: The authors introduced a new distributed adaptive minimax method, D-AdaST, to address the issue of non-convergence in nonconvex-strongly-concave minimax problems caused by inconsistencies in locally computed adaptive stepsizes. D-AdaST employs an efficient adaptive stepsize tracking protocol that ensures time-scale separation and consistency of stepsizes among nodes, thereby eliminating steady-state errors. Extensive experiments on both real-world and synthetic datasets validate their theoretical findings across various scenarios.
strength_weakness: strength_weakness: The experimental section has some deficiencies, as it only includes a GAN experiment on the CIFAR-10 dataset. I believe it would be beneficial to supplement the paper with results from additional datasets or other minimax optimization problems to provide a more comprehensive evaluation.
questions: questions: Please see weakness.
limitations: limitations: The paper employs general assumptions for distributed minimax optimization problems; therefore, it is unnecessary to discuss the limitations.
paper_summary: paper_summary: This paper proposed a decentralized stochastic first-order method for nonconvex minimax optimization. For nonconvex-strongly-concave setting, the proposed D-AdaST has the convergence rate of $O(\epsilon^{-4+\delta})$ for any small $\delta>0$.
strength_weakness: strength_weakness: see questions
questions: questions: The proposed method does not require the knowledge of the parameters $L$, $\mu$ and total iterations number, which is nice in  empirical. 

I have some questions as follows:

1.	This paper states D-AdaST achieves the near-optimal convergence rate, while the definition of optimality is unclear, e.g., problem setting and algorithm class. I’m not sure whether this statement is correct. Specifically, Assumption 2 requires the second-order Lipschitz continuous, while the existing lower for solving nonconvex-strongly-concave minimax problem by first-order methods only considers the first-order Lipschitz continuous. The author should clarify how to fill this gap and explain how to achieve the lower bound in the setting of D-AdaST more clearly. 
2.	Assumption 3 introduce the upper bound $C$ for stochastic gradient, which should be included in the final convergence rate.
3.	Can you provide some explanation why the small $\delta$ cannot be avoided in result? What happens if we try to take $\delta\to0$?
4.	The section of introduction describes the problem setting with constraints on both $x$ and $y$, while the algorithm design and convergence analysis looks only consider the constraint on $y$.
5.	Is it possible to increase the batch-size of stochastic gradient to reduce the total communication rounds? Typically, the communication rounds in decentralized optimization can be smaller than the computation rounds, e.g., Chen et al., 2024.
limitations: limitations: N/A
paper_summary: paper_summary: The paper presents D-AdaST, a distributed adaptive minimax method designed to address non-convergence issues in nonconvex-strongly-concave (NC-SC) minimax problems caused by inconsistent locally computed adaptive stepsizes in distributed settings. The method incorporates a stepsize tracking mechanism, which ensures consistency across local stepsizes and maintains time-scale separation, achieving near-optimal convergence rates comparable to centralized counterparts.
strength_weakness: strength_weakness: Please consider my questions for this part.
questions: questions: 1- How does D-AdaST compare to other existing adaptive minimax methods in terms of computational time efficiency?

2-The current analysis focuses on nonconvex-strongly-concave minimax problems. How would the theoretical framework extend to other problem classes, such as nonconvex-nonconcave or convex-concave problems? What modifications or additional assumptions would be necessary?

3-In a distributed setting, communication delays and asynchrony can pose significant challenges. How does the theoretical analysis account for these factors? Are there any bounds or guarantees provided for performance in asynchronous or delayed communication settings?
limitations: limitations: They discussed the limitations of their work in terms of assumptions and main results.

Comments: title: Thanks to Reviewer vU1y
Thanks to Reviewer KXvx
Thanks to Reviewer Nhkx
Thanks to Reviewer rQb7
Response to Reviewer Nhkx
comment: Thanks for the thoughtful acknowledgement and consideration of our responses. We sincerely appreciate the reviewer's valuable time in reviewing our paper.
Thank you for the additional information regarding the experiment. I will accordingly adjust my score.
We appreciate the reviewer's acknowledgement. Thank you for taking the time to carefully review our paper and respond to our clarifications.
Appreciate authors for their response and clarification. I am satisfied with their response and maintain my score.
We are grateful for the reviewer's engagement and recognition.  Thanks for spending your time carefully reviewing our paper and responding to our clarifications. 

We will incorporate the necessary revisions, taking into account all the points we have discussed. We believe that these changes will enhance the quality of our paper.
Thanks for your very detailed response. The response to Q7 and Q8 should be involved into the revision.

Since my questions have been well addressed, I will raise my overall rating.
We appreciate the acknowledgment of the reviewer. Thanks for spending your time carefully reviewing our paper and responding to our clarifications.
Thank you for your prompt response and valuable comments. We have carefully considered your remaining concerns and have responded in detail as follows:

>__Q6:__ My main consideration is the applicability of the lower bound provided by Li et al. [6]. Noticing that their Definition 1 does not include second-order Lipschitz continuity. The lower bound of $\varOmega \left( \epsilon ^{-4} \right)$ in their Theorem 2 is based on the function $f^{\text{sc-nc-sg}}$. The proof of this theorem only verifies its gradient is Lipschitz continuous. However, the Lipschitz continuity of its Hessian is unclear. Therefore, we should check if the construction of Li et al. [6] holds the second-order Lipschitz continuity shown in Assumption 2. If the author can address this issue, I will increase my overall rating. Otherwise, the statement on the optimality should be avoided in revision (I will still keep borderline accept).

__Response__ We have carefully checked the construction of the hard examples for obtaining the complexity lower bound in [6] and verified that they satisfy second-order Lipschitz continuity on $y$ as assumed in Assumption 2. Specifically, we recall the hard instance in the stochastic setting in [6] (c.f., Eqs. (10) and (11)) as follows:
$$
\bar{f}^{\text{nc-sc-sg}}\left( \boldsymbol{x},\boldsymbol{z};\bar{\boldsymbol{y}} \right) =-\Psi \left( 1 \right) \Phi \left( x_1 \right) +\sum_{i=2}^T{\left[ \Psi \left( -z_i \right) \Phi \left( -x_i \right) -\Psi \left( z_i \right) \varPhi \left( x_i \right) \right]}+\sum_{i=1}^{T-1}{\left[ c_1x_{i}^{2}+c_2z_{i+1}^{2} \right]}+\sum_{i=1}^{T-1}{h^{\text{sg}}\left( x_i,z_{i+1};\bar{\boldsymbol{y}}^{\left( i \right)} \right)},
$$

with

$$
h^{\text{sg}}\left( x,z;\boldsymbol{y} \right) =\frac{C}{n}\left[ -\frac{1}{2}\boldsymbol{y}^{\text{T}}\left( \frac{1}{n^2}I_n+A \right) \boldsymbol{y}+\boldsymbol{b}_{x,z}^{\text{T}}\boldsymbol{y} \right]
$$

and $\boldsymbol{b}_{x,z}=x\boldsymbol{e}_1-\frac{1}{2}z\boldsymbol{e}_n$, where $\boldsymbol{x}$ and $\boldsymbol{z}$ are variables to minimize, $\boldsymbol{y}$ is the variable to maximize, $\Psi \left( \cdot \right)$ and $\Phi \left( \cdot \right)$ are component functions, $c_1$, $c_2$ and $C$ are constants, $A$ is a positive semi-definite matrix (refer to Section 4 in [6] for detailed definitions).

It should be noted that the assumption of second-order Lipschitz continuity of this work is only required to hold for $y$ (c.f., Eq. (11) in Assumption 2), and the terms related to $y$ in the objective function $\bar{f}^{\text{nc-sc-sg}}$ are only in $h^{\text{sg}}$, which is twice differentiable. It is not difficult to verify that $\nabla _{x,z;\boldsymbol{y}}^{2}h^{\mathrm{sg}}=-\left( \frac{1}{n^2}I_n+A \right)$ and $\nabla _{\boldsymbol{yy}}^{2}h^{\mathrm{sg}}=\mathrm{diag}\left\\{ 1,0,\cdots,0,-1/2 \right\\}$ are constant matrices and thus both are Lipschitz continuous. This indicates that $\bar{f}^{\text{nc-sc-sg}}$ is second-order Lipschitz continuous for $y$, satisfying Eq. (11) in Assumption 2. Therefore, we believe that the lower bound given by Li et al. [6] is applicable to the function class considered in our work. Combined with the previous discussion, we will carefully revise our statement about "near-optimal" to avoid any possible confusion.

>__Q7:__ For Q4, I recommend to unify the presentation of constrained/unconstrained setting on the variable.

__Response__ Thank you for your suggestion. We will do a proper revision of the presentation of the decision variable domains.

>__Q8:__ For Q5, I think reduce the communication complexity is possible even if there is no average smoothness assumption. At least, this can be address in nonconvex minimization, e.g.,
> * [18] Yucheng Lu and Christopher De Sa. Optimal Complexity in Decentralized Training. ICML 2021.

__Response__ We agree with the reviewer that reducing the communication complexity is possible even without relying on the average smoothness assumption. As mentioned by the reviewer, without this assumption, Lu et al. [18] combined local updates with the Factorized Consensus method (c.f., Lemma 1 in [18]) and Accelerated Gossip protocol (c.f., Algorithm 3), yielding reduced communication complexity. However, in order to obtain a computational complexity of $\varOmega \left( \epsilon ^{-3} \right)$ as in [12], this assumption is required in most of the literature based on the variance reduction methods. Otherwise, without this assumption, the sampling complexity obtained by Lu et al. [18] matches another lower bound $\varOmega \left( \epsilon ^{-4} \right)$. Having noted the characteristics and limitations of these methods, we believe they are all worthy of further investigation to improve the communication efficiency of distributed algorithms, with or without this average smoothness assumption.
I appreciate the detailed response by the authors. I wish to maintain my score.
Thanks for your detailed rebuttal. I am satisfied with most of your response, while there are still some questions should be addressed.

My main consideration is the applicability of the lower bound provided by Li et al. [6]. Noticing that their Definition 1 does not include second-order Lipschitz continuity. The lower bound of $\Omega(\epsilon^{-4})$ in their Theorem 2 is based on the function $f^{{\rm nc}-{\rm sc}-{\rm sg}}$. The proof of this theorem only verifies its gradient is Lipschitz continuous. However, the Lipschitz continuity of its Hessian is unclear. Therefore, we should check if the construction of Li et al. [6] holds the second-order Lipschitz continuity shown in Assumption 2. If the author can address this issue, I will increase my overall rating. Otherwise, the statement on the optimality should be avoided in revision (I will still keep borderline accept).

**Some minor comments:**

For Q4, I recommend to unify the presentation of constrained/unconstrained setting on the variable.

For Q5, I think reduce the communication complexity is possible even if there is no average smoothness assumption. At least, this can be address in nonconvex minimization, e.g.,

[18] Yucheng Lu and Christopher De Sa. Optimal Complexity in Decentralized Training. ICML 2021.