Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity

Authors: qihao  zhou
haishan  ye
luo  luo
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 15:09:19

Abstract: This paper considers the distributed convex-concave minimax optimization under the second-order similarity.
We propose stochastic variance-reduced optimistic gradient sliding (SVOGS) method, which takes the advantage of the finite-sum structure in the objective by involving the mini-batch client sampling and variance reduction.
We prove SVOGS can achieve the $\varepsilon$-duality gap within communication rounds of 
${\mathcal O}(\delta D^2/\varepsilon)$, 
communication complexity of ${\mathcal O}(n+\sqrt{n}\delta D^2/\varepsilon)$,
and local gradient calls of 
$\tilde{\mathcal O}(n+(\sqrt{n}\delta+L)D^2/\varepsilon\log(1/\varepsilon))$, 
where $n$ is the number of nodes, $\delta$ is the degree of the second-order similarity, $L$ is the smoothness parameter and $D$ is the diameter of the constraint set.
We can verify that all of above complexity (nearly) matches the corresponding lower bounds.
For the specific $\mu$-strongly-convex-$\mu$-strongly-convex case, 
our algorithm has the upper bounds on communication rounds,  communication complexity, and local gradient calls of $\mathcal O(\delta/\mu\log(1/\varepsilon))$, ${\mathcal O}((n+\sqrt{n}\delta/\mu)\log(1/\varepsilon))$, and $\tilde{\mathcal O}(n+(\sqrt{n}\delta+L)/\mu)\log(1/\varepsilon))$ respectively, which are also nearly tight.
Furthermore, we conduct the numerical experiments to show the empirical advantages of proposed method.

Main paper: 
 introduction: 
 We study the distributed minimax optimization problemEQUATIONwhere f i is the differentiable local function associated with the i-th node, and X ⊆ R dx and Y ⊆ R dy are the constraint sets. We are interested in the centralized setting, where there are one server node and n -1 client nodes that collaboratively solve the minimax problem. Without loss of generality, we assume the function f 1 is located on the server node and the functions f 2 , . . . , f n are located on the client nodes. This formulation is a cornerstone in the study of game theory, aiming to achieve the Nash equilibrium [12, 44] . It covers a lot of applications such as signal processing [23] , optimal control [41] , adversarial learning [44] , robust regression [15, 35] and portfolio management [52] .Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes]Justification: [Yes] See Section 1.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
preliminaries: 
 We focus on the distributed optimization in client-sever framework for solving minimax problem (1) . The notation f i presents the local function on the i-th node. We assume the function f 1 is located on the server and the other individuals are located on clients. We stack variables x ∈ R dx and y ∈ R dy as the vector z = [x; y] ∈ R d , where d = d x + d y . We let Z := X × Y ⊆ R d and define the projection operator P Z (v) := arg min z∈Z ∥z -v∥ for given v ∈ R d . We also denote the vector functions F i : R d → R d and F : R d → R d asF i (z) := ∇ x f i (x, y) -∇ y f i (x, y) and F (z) := 1 n n i=1 F i (z).We consider the following common assumptions for our minimax problem. Assumption 1. We suppose the constraint set Z ⊆ R d is a non-empty, closed, and convex. Assumption 2. We suppose the constraint set Z ⊆ R d is bounded by diameter D > 0, i.e., we have ∥z 1 -z 2 ∥ ≤ D for all z 1 , z 2 ∈ Z.Assumption 3. We suppose each local function f i : R dx ×R dy → R is smooth, i.e., there exists L > 0 such that ∥F i (z 1 ) -F i (z 2 )∥ ≤ L ∥z 1 -z 2 ∥ for all i ∈ [n] and z 1 , z 2 ∈ R d .Assumption 4. We suppose each differentiable local function f i : R dx × R dy → R is convex-concave, i.e., we have f i (x, y) ≥ f i (x ′ , y) + ⟨∇ x f i (x ′ , y), x -x ′ ⟩ and f i (y) ≤ f i (y ′ ) + ⟨∇ y f i (y ′ ), y -y ′ ⟩ for all i ∈ [n], x, x ′ ∈ R dx and y, y ′ ∈ R dy .Assumption 5. We suppose the global objective f : R dx × R dy → R is strongly-convex-stronglyconcave, i.e., there exists µ > 0 such that the function f (x, y) -µ 2 ∥x∥ 2 + µ 2 ∥y∥ 2 is convex-concave.Besides, we introduce the assumption of second-order similarity to measure the homogeneity in local functions [5, 8, 19, 20] . Assumption 6. The local functions f 1 , . . . , f n : R dx × R dy → R are twice differentiable and hold the δ-second-order similarity, i.e., there exists δ > 0 such that∇ 2 f i (x, y) -∇ 2 f (x, y) ≤ δ for all i ∈ [n],x ∈ R dx and y ∈ R dy .We measure the sub-optimality of the approximate solution z = (x, y) ∈ Z by duality gap, that is Gap(x, y) := maxy ′ ∈Y f (x, y ′ ) -min x ′ ∈X f (x ′ , y).We also consider the criterion of the gradient mapping for given z = (x, y) ∈ Z [31, 40, 54] , that is,F τ (z) = z -P Z (z -τ F (z)) τ ,where τ > 0. The gradient mapping F τ (z) is a natural extension of gradient operator F (z).Noticing that we have F τ (z) = F (z) if the problem is unconstrained (i.e., Z = R d ), and the condition F τ (z) = 0 is equivalent to the point z is a solution of the problem. Compared with the duality gap, the norm of gradient mapping is a more popular measure in empirical studied since it is easy to achieve in practice.For the specific strongly-convex-strongly-concave case, we can also measure the sub-optimality by the square of Euclidean distance to the unique solution z * = (x, y) ∈ Z, that is∥z -z * ∥ 2 = ∥x -x * ∥ 2 + ∥y -y * ∥ 2 .Moreover, we use notations O(•), Θ(•) and Ω(•) to hide constants which do not depend on parameters of the problem, and notations Õ(•), Θ(•), and Ω(•) to additionally hide the logarithmic factors of n, L, µ and δ.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: [Yes] See Section 8.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
related work: 
 For convex-concave minimax optimization, the full batch first-order methods [24, 33, 34, 38, 39, 43, 51] can achieve ε-duality gap within at most O(LD 2 /ε) iterations. Applying these idea to distributed setting naturally leads to the communication rounds of O(LD 2 /ε) and each round requires all of the n nodes to compute and communicate their local gradient.In a seminar work, Beznosikov et al. [5] proposed Star Min-Max Data Similarity (SMMDS) algorithm, which additionally consider the second-orders similarity (Assumption 6) by involving gradient sliding technique [27, 45] . The SMMDS requires communication rounds of O(δD 2 /ε), which benefits from the homogeneity in local functions. Each round of this method needs to communicate/compute the local gradient of all n nodes, and perform the local updates on the server within Õ(L/δ log(1/ε)) local iterations, which results in the overall communication complexity of O(nδD 2 /ε) and local gradient complexity of Õ((nδ + L)D 2 /ε log(1/ε)). Later, Kovalev et al. [25] introduced extragradient sliding (EGS), which further improves the local gradient complexity to O((nδ + L)D 2 /ε).It is worth pointing out that the communication rounds of O(δD 2 /ε) achieved by SMMDS and EGS matches the lower complexity bound under the second-order similarity assumption [5] . However, these methods enforce all nodes to participate into communication in every round, which does not sufficiently take the advantage of finite-sum structure in the objective.Recently, Beznosikov et al. [8] proposed Three Pillars Algorithm with Partial Participation (TPAPP), which uses the variance-reduced forward-backward-forward method [1, 10] to encourage only one of clients participate into the communication in most of the rounds. The TPAPP can achieve point z ∈ R d such that E[∥F (z)∥ 2 ] ≤ ε for unconstrained case within the communication rounds of O(nδ 2 D 2 /ε), O LD 2 ε O nLD 2 ε O nLD 2 ε SMMDS [5] O δD 2 ε O nδD 2 ε Õ (nδ+L)D 2 ε log 1 ε EGS [25] O δD 2 ε O nδD 2 ε O (nδ+L)D 2 ε SVOGS (Algorithm 1) O δD 2 ε O n + √ nδD 2 ε Õ n + ( √ nδ+L)D 2 ε log 1 εLower Bounds (Theorem 3,4,5)Ω δD 2 ε Ω n + √ nδD 2 ε Ω n + ( √ nδ+L)D 2 εTable 2 : The complexity of achieving E[∥x -x * ∥2 +∥y -y * ∥ 2 ] ≤ ε in the strongly-convex-stronglyconcave case. † These methods use permutation compressors [49] , which require the assumption of d > n. ♯ The complexity of TPAPP depends on local iterations number H, where "TPAPP (a)" and "TPAPP (b)" correspond to H=⌈L/( √ nδ)⌉ and H=⌈8 log(40nL/µ)⌉ respectively.Local Gradient ComplexityEG [24] O L µ log 1 ε O nL µ log 1 ε O nL µ log 1 ε SMMDS [5] O δ µ log 1 ε O nδ µ log 1 ε Õ nδ+L µ log 1 ε EGS [25] O δ µ log 1 ε O nδ µ log 1 ε O nδ+L µ log 1 ε OMASHA [4] † O L µ log 1 ε O n + √ nδ+L µ log 1 ε O nL µ log 1 ε TPA [8] † O n + √ nδ µ log 1 ε O n + √ nδ µ log 1 ε O n + √ nL δ + L µ log 1 ε TPAPP (a) [8] ♯ O n + √ nδ µ log 1 ε O n + √ nδ µ log 1 ε O n + √ nL δ + L µ log 1 ε TPAPP (b) [8] ♯ O n + √ nδ+L µ log 1 ε O n + √ nδ+L µ log 1 ε Õ n + √ nδ+L µ log 1 ε SVOGS (Algorithm 1) O δ µ log 1 ε O n + √ nδ µ log 1 ε Õ n + √ nδ+L µ log 1 ε Lower Bounds ([5, 8], Theorem 7) Ω δ µ log 1 ε Ω n + √ nδ µ log 1 ε Ω n + √ nδ+L µ log 1 ε communication complexity of O(nδ 2 D 2 /ε), and local gradient complexity of O(n 2 δ 4 L 2 D 6 ε -3 ). 2The theoretical analysis of TPAPP for the constrained problem requires the objective being stronglyconvex-strongly-concave. In addition, we can also reduce the communication complexity by using the permutation compressors [49] for high-dimensional problem [4, 8] , which achieves the similar complexity to existing partial participation methods [8] .We present the complexity of existing methods and compare them with our results in both general convex-concave case and strongly-convex-strongly-concave case in Table 1 -3.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
stochastic variance-reduced optimistic gradient sliding: 
 We propose stochastic variance-reduced optimistic gradient sliding (SVOGS) method in Algorithm 1.The design of our algorithm starts from reformulating problem (1) as followsEQUATIONThe idea of gradient sliding [27] on minimax optimization can be viewed as iteratively solving the surrogate of problem (3) within the quadratic approximation of g(x, y) [5, 8, 25] . Recall that the [8] § O nδ 2 D 2 ε O nδ 2 D 2 ε O n 2 δ 4 L 2 D 6 ε 3 SVOGS (Algorithm 1) Õ δD √ ε log 1 ε Õ n + √ nδD √ ε log 1 ε Õ n + ( √ nδ+L)D √ ε log 1 ε Algorithm 1 Stochastic Variance-Reduced Optimistic Gradient Sliding (SVOGS)1: Input: initial point z 0 = (x 0 , y 0 ) ∈ Z, step size η, accuracy {ε k } K k=1 , communication rounds K, mini-batch size b, probability p ∈ (0, 1], weights α, γ ∈ (0, 1); 2: Initialization: w -1 = z -1 = w 0 = z 0 = (x 0 , y 0 ) ∈ Z, z 0 i = z 0 for all i ∈ [n]; 3: for k = 0, 1, 2, . . ., K -1 do 4: zk = (1 -γ)z k + γw k ; 5: Sample S k = {j k 1 , . . . ,δ k = F (w k-1 ) -F 1 (w k-1 ) + 1 b j∈S k F j (z k ) -F 1 (z k ) -F j (w k-1 ) + F 1 (w k-1 ) + α b j∈S k F j (z k ) -F 1 (z k ) -F j (z k-1 ) + F 1 (z k-1 ) ; 7: v k = zk -ηδ k ; 8: Find u k ∈ R d such that ∥u k -ûk ∥ 2 ≤ ε k ,where ûk is the solution of the problemEQUATIONz k+1 = u k ; 10:w k+1 = z k+1 with probability p, w k with probability 1 -p.11: end for optimistic gradient descent ascent (OGDA) method [34, 43] iterates withEQUATIONwhere η > 0 is the step size. It is well-known that OGDA achieves optimal convergence rate under the first-order smoothness assumption [42, 55] , which motivated us construct the quadratic approximation of g(x, y) by using the optimistic gradient of g at (x k , y k ) in the linear terms, that isg(x, y) ≈ ĝ(x, y) =g(x k , y k ) + ⟨∇ x g(x k , y k ) + ∇ x g(x k , y k ) -∇ x g(x k-1 , y k-1 ) optimistic gradient with respect to x , x -x k ⟩ + 1 2η x -x k 2 + ⟨∇ y g(x k , y k ) + ∇ y g(x k , y k ) -∇ y g(x k-1 , y k-1 )optimistic gradient with respect to y , y -y k ⟩ - 1 2η y -y k 2 .(EQUATIONApplying approximation (5) to formulation (3), we obtain the optimistic gradient sliding (OGS), which iteratively solve the sub-problemEQUATIONWe can verify function g(x, y) is δ-smooth under Assumption 6, which indicates taking η = Θ(1/δ) and solving the sub-problem sufficiently accurate can find an ε-suboptimal solution within the iteration numbers of O(δD 2 /ε) and O(δ/µ log(1/ε)) for the convex-concave case and the stronglyconvex-strongly-concave case respectively (see Section 5) . The dependence on δ implies OGS benefits from the second-order similarity in local functions, while each of its iteration requires the communication and the computation of the exact gradient of f (x, y) within the complexity of O(n).The key idea to improve the cost in each iteration is involving the mini-batch client sampling and variance reduction with momentum [2, 26] . Specifically, we estimate the optimistic gradient in formulation (5) as followsEQUATIONwhereG(z) := F (z) -F 1 (z), S k ⊆ [n]is the random index set, w k is the snapshot point which is updated infrequently in iterations, and α ∈ (0, 1) is the momentum parameter. Applying the optimistic gradient estimation (7) to formulations ( 5)-( 6), we achieve our stochastic variance-reduced optimistic gradient sliding (SVOGS) method (Algorithm 1).The proposed SVOGS enjoys the mini-batch partial participation in the steps communication and computation in most of rounds, which is the main difference between SVOGS and existing methods [5, 8, 26] . Concretely, taking the mini-batch size|S k | = Θ( √ n )for SVOGS can simultaneously balance communication rounds, communication complexity and local gradient complexity. The SVOGS keeps both the benefit of parallel communication like full participation methods (i.e., SMMDS [5] and EGS [25] ) and the low communication cost like existing participation methods (i.e., TPAPP [8] ). Additionally, the communication advantage of SVOGS also makes the algorithm achieves better local gradient complexity than state-of-the-arts [5, 8, 26] . 
the complexity analysis: 
 In this section, we provide the complexity analysis of proposed SVOGS (Algorithm 1) to show its superiority. In particular, we let µ = 0 for the convex-concave case to the ease of presentation.We analyze the convergence of SVOGS (Algorithm 1) by establishing the Lyapunov functionEQUATIONwhere we take the step size such that η ≤ 1/(32δ) which always guarantees Φ k ≥ 0 by using Young's inequality and the similarity assumption (see detailed proof in Appendix B).We show that the decrease of Lyapunov function in expectation as follows. Lemma 1. Suppose Assumptions 1, 3, 4, and 6 hold with0 ≤ µ ≤ δ ≤ L, running SVOGS (Algorithm 1) with γ ≤ 1/8, α = max {1 -ηµ/6, 1 -pηµ/(2γ + ηµ)}, η ≤ min{1/µ, 1/(32δ)}, 256η 2 δ 2 α 2 (b + 1)/b ≤ α, 4ηδ 2 /b ≤ αγ/(4η), and ε k ≤ c -1 min ∥û k -z k ∥, ∥û k -z k ∥ 2for some c = poly(µ, δ), then we haveE[Φ k+1 ] ≤ max 1 - ηµ 6 , 1 - pηµ 2γ + ηµ E[Φ k ] - 1 16η E ∥z k -ûk ∥ 2 - γ 2η E ∥w k -ûk ∥ 2 .(9)For the convex-concave case, we use Jensen's inequality and the convexity (concavity) to bound the duality gap atEQUATION)Applying Lemma 1 by summing over inequality (9) , we can bound the right-hand side of (10) via the terms ofK-1 k=0 E ∥z k -ûk ∥ 2 and K-1 k=0 E ∥w k -ûk ∥ 2, and achieve the following theorem. Theorem 1. Suppose Assumptions 1, 2, 3, 4 and 6 hold with 0 < δ ≤ L and D > 0, we run Algorithm 1 with b = ⌈ √ n ⌉, γ = p = 1/( √ n + 8), η = min √ γb/(4δ), 1/(32δ) , α = 1, and ε k = min ζ, ĉ-1 min ∥û k -z k ∥, ∥û k -z k ∥ 2 for some ζ = poly(L, δ, n, D, ε) and ĉ = poly(δ). Then we haveE max z∈Z 1 K K-1 k=0 ⟨F (u k ), u k -z⟩ ≤ 10D 2 ηK + ε 2 , where u K avg = 1 K K-1 k=0 u k .Theorem √ nδ + L)D 2 /ε log(1/ε)), where u K avg = 1 K K-1 k=0 u k .By appropriate settings of SVOGS, Lemma 1 leads to the following linear convergence of our Lyapunov function in the strongly-convex-strongly-concave case. Theorem 2. Suppose Assumptions 1, 3, 4, 5 and 6 hold with 0 < µ ≤ δ ≤ L, we run Algorithm 1 with b = ⌈min { √ n, δ/µ}⌉, γ = p = 1/(min { √ n, δ/µ} + 8), η = min √ αγb/(4δ), 1/(32δ) , α = max {1 -ηµ/6, 1 -pηµ/(2γ + ηµ)}, and ε k = c -1 min ∥û k -z k ∥, ∥û k -z k ∥ 2 for some c = poly(µ, δ). Then we haveE[Φ K ] ≤ max 1 - ηµ 6 , 1 - pηµ 2γ + ηµ K Φ 0 .We then apply Theorem 2 with K = O(δ/µ log(1/ε)) and analyze the complexity like the discussion after Theorem 1, which results in the upper complexity bounds as follows. Corollary 2. Following the setting of Theorem 2, we can achieveE ∥z K -z * ∥ 2 ≤ ε within communication rounds of O(δ/µ log(1/ε)), communication complexity of O((n+ √ nδ/µ) log(1/ε)), and local gradient complexity of Õ((n + ( √ nδ + L)/µ) log(1/ε)).For the convex-concave case (under the assumptions of Theorem 1), we can achieve the points with small gradient mapping by solving the regularized problemEQUATIONfor some λ > 0. Noticing that the function f (x, y) is (L + λ)-smooth, λ-strongly-convex-λstrongly-concave and δ-similarity. Then Corollary 2 implies running SVOGS (Algorithm 1) by iterations number K = O(δD/ √ ε log(L/ε)) to solve problem (11) with λ = O( √ ε/D) can achieve E[∥F τ (z K )∥ 2 ]≤ ε, which results in the complexity shown in Table 3 . For the stronglyconvex-strongly-concave case, the complexity of achieving E[∥F τ (z K )∥ 2 ≤ ε nearly matches the complexity of achieving E ∥z K -z * ∥ 2 ] ≤ ε. We defer the detailed derivation for these results of making the gradient mapping small to Appendix G. 
the optimality of svogs: 
 In this section, we provide the lower complexity bounds for solving our minimax problems by using distributed first-order oracle (DFO) methods. The class of algorithms considered in our analysis follows the definition of Beznosikov et al. [8] , which is formally described in Appendix D. Compared with existing lower bound analysis for second-order similarity only focusing on communication [5, 8] , we additionally study the computation complexity by considering the local gradient calls. The results in this section imply the complexity of proposed SVOGS (nearly) matches the lower bounds on the communication rounds, the communication complexity and the local gradient calls simultaneously.We first provide the following lower bounds for convex-concave case.Theorem 3. For any 0 < δ ≤ L, n ≥ 3, D > 0 and ε ≤ δD 2 /(12 √ 2 ), there exist L-smooth and convex-concave functions f 1 , . . . , f n : R dx × R dy with δ-second-order similarity, and closed convex set Z = X × Y with diameter D. In order to find an approximate solution z = (x, y) of problem (1) such that E[Gap(z)] ≤ ε, any DFO algorithm needs at least Ω(δD 2 /ε) communication rounds. Theorem 4. For any 0 < δ ≤ L, n ≥ 2, D > 0 and ε ≤ δD 2 /(16 √ 2n ), there exist L-smooth and convex-concave functions f 1 , . . . , f n : R dx × R dy with δ-second-order similarity, and closed convex set Z = X × Y with diameter D. In order to find an approximate solution z = (x, y) of problem (1) such that E[Gap(z)] ≤ ε, any DFO algorithm needs at least Ω(n + √ nδD 2 /ε) communication complexity and Ω(n + √ nδD 2 /ε) local gradient calls.The lower bounds on communication round and communication complexity shown in Theorem 3 and 4 match the corresponding upper bounds of SVOGS shown in Corollary 1. However, the lower bound on local gradient complexity shown in Theorem 4 only nearly matches the result of Corollary 1 in the case of √ nδ ≥ Ω(L). Therefore, we also provide the following lower bound on local gradient complexity to show the tightness of dependence on the smoothness parameter L. Lemma 2. For any L > 0, n ∈ N, D > 0 and ε ≤ δD 2 /(4 √ 2), there exist L-smooth and convex-concave functions f 1 , . . . , f n : R dx × R dy with δ-second-order similarity, and closed convex set Z = X × Y with diameter D. In order to find an approximate solution z = (x, y) of problem (1) such that E[Gap(z)] ≤ ε, any DFO algorithm needs at least Ω(n + LD 2 /ε) local gradient calls.Combining the results of Theorem 4 and Lemma 2, we achieve the following lower bound on local gradient complexity, which nearly matches the corresponding upper bound shown in Corollary 1.EQUATION), there exist L-smooth and convex-concave functions f 1 , . . . , f n : R dx × R dy with δ-second-order similarity, and closed convex set Z = X × Y with diameter D. In order to find an approximate solution z = (x, y) of problem (1) such that E[Gap(z)] ≤ ε, any DFO algorithm needs at least Ω(n + (√ nδ + L)D 2 /ε) local gradient calls.The constructions in our lower bound analysis is based on the modifications on the blinear functions provided by Han et al. [14] , which are originally used to analyze the minimax optimization in nondistributed setting. We provide detailed proofs in Appendix E. In related work, Beznosikov et al. [5] also provide the lower bound of Ω(δD 2 /ε) (matching the result of Theorem 3) for communication rounds by using the regularized function, which is different from our construction in the proof of Theorem 3. In addition, our lower bounds on the communication complexity and the local gradient complexity shown in Theorem 4 and 5 are new. 13) on a9a.The tight lower bound on communication rounds in strongly-convex-strongly-concave case has been provided by Beznosikov et al. [5, Theorem 1] . We present the result as follows. Theorem 6 ( [5] ). For any µ, δ, L > 0 with L ≥ max{µ, δ} and n ≥ 3, there exist L-smooth and convex-concave functions f 1 , . . . , f n : R dx ×R dy with δ-second-order similarity such that the functionf (x, y) = 1 n n i=1 f i (x, y) is µ-strongly-convex-µ-strongly-concave.In order to find a solution of problem (1) such that E[∥z -z * ∥ 2 ] ≤ ε, any DFO algorithm needs at least Ω(δ/µ log(1/ε)) communication rounds.The tight lower bound on communication complexity has been provided by Beznosikov et al. [8] . We follow their construction to establish the lower bound on local gradient complexity, nearly matching the corresponding upper bound of our SVOGS. We formally present these lower bounds as follows. Theorem 7. For any µ, δ, L > 0 with L ≥ max{µ, δ} and n ≥ 2, there exist L-smooth and convexconcave functions f 1 , . . . , f n : R dx × R dy with δ-second-order similarity such that the functionf (x, y) = 1 n n i=1 f i (x, y) is µ-strongly-convex-µ-strongly-concave. In order to find a solution of problem (1) such that E[∥z -z * ∥ 2 ] ≤ ε, any DFO algorithm needs at least Ω((n+ √ nδ/µ) log(1/ε)) communication complexity and Ω((n + ( √ nδ + L)/µ) log(1/ε)) local gradient calls. 
experiments: 
 We conduct the experiment on robust linear regression [5, 15, 35] . Concretely, we consider the constrained convex-concave minimax problemEQUATION)and the unconstrained strongly-convex-strongly-concave minimax problemEQUATIONwhere x contains the weights of the model, y describes the noise, and We compare the proposed SVOGS (Algorithm 1) with baselines Extra-Gradient method (EG) [24] , Star Min-Max Data Similarity algorithm (SMMDS) [5] , Extra-Gradient Sliding (EGS) [25] ), and Three Pillars Algorithm with Partial Participation (TPAPP) [8] . We test the algorithms on realworld datasets "a9a" (N = 32, 561, d ′ = 123), "w8a" (N = 49, 749, d ′ = 300) and "covtype" (N = 581, 012, d ′ = 54) from LIBSVM repository [9] and set the nodes number be n = 500. For problem (12) , we set R x = 2 and R y = 0.05, respectively.{(a i , b i )} N i=1 is the training set.We implement all of the methods by Python 3.9 with NumPy and run on a machine with AMD Ryzen(TM) 7 4800H 8 core with Radeon Graphics 2.90 GHz CPU with 16GB RAM. We solve the sub-problem in SVOGS (Algorithm 1), SMMDS [5] , EGS [25] , and TPAPP [8] by Extra-Gradient method of Korpelevich [24] . We tune the step-size η of SVOGS from {0.01, 0.1, 1}. The probability p is tuned from {p 0 , 5p 0 , 10p 0 }, where p 0 = 1/ min{ √ n+δ/µ}. The batch size b is determined from {⌊b 0 /10⌋, ⌊b 0 /5⌋, ⌊b 0 ⌋}, with b 0 = 1/p 0 . We set the other parameters by following our theoretical analysis. We set the average weight as γ = 1 -p. For the momentum parameter, we set α = 1 for convex-concave case and α = max{1 -ηµ/6, 1 -pηµ/(2γ + ηµ)} for strongly-convex-stronglyconcave case, where we estimate µ by max{λ, β} for problem (13) . For the sub-problem solver, we set its step-size according to the smoothness parameter of sub-problem, i.e., 1/(L + 1/η). In addition, we estimate the smooth parameter L and the similarity parameter δ by following the strategy in Appendix C of Beznosikov et al. [5] .We present the experimental results in Figure 1 to 4 for datasets "a9a" and "w8a". The results for dataset "covtype" is displayed in Appendix H due to the space limitation. We can observe that our SVOGS outperforms all baselines in terms of the local gradient complexity. Additionally, the SVOGS requires less communication rounds than classical EG and existing partial participation method TPAPP, and it requires significantly less communication complexity than full participation methods EG, SMMDS and EGS. All of these empirical results support our theoretical analysis. 
conclusion: 
 This paper presents a novel distributed optimization method named SVOGS, which use the secondorder similarity in local functions and the finite-sum structure in objective to solve the convex-concave minimax problem within the near-optimal complexity. Our theoretical results are also validated by the numerical experiments. In future work, it is interesting to use our ideas to improve the efficiency of distributed nonconvex minimax optimization under the second-order similarity.for all z 1 , z 2 ∈ R d and i ∈ [n].Lemma 4 (Alacaoglu and Malitsky [1, Section 8] ). Let F = {F k } k≥0 be a filtration and {r k } be a stochastic process adapted to F with E[r k+1 |F k ] = 0. Then for any K ∈ N, x 0 ∈ Z, and any compact set C ⊂ Z, we haveE max x∈C K-1 k=0 ⟨r k+1 , x⟩ ≤ max x∈C 1 2 ∥x 0 -x∥ 2 + 1 2 K-1 k=0 E∥r k+1 ∥ 2 .In related work, Beznosikov et al. [8, Assumption 4.3 ] considers the following second-order similarity assumption that is slightly different from our Assumption 6. Assumption 7. The local functions f 1 , . . . , f n : R dx × R dy → R are twice differentiable and hold the δ-average-second-order similarity, i.e., there exists δ > 0 such that1 n n i=1 ∇ 2 f i (x, y) -∇ 2 f j (x, y) 2 ≤ δ 2for all x ∈ R dx , y ∈ R dy , and j ∈ [n], .We present the relationship between δ-average-second-order similarity (Assumption 7) and δ-secondorder-similarity (Assumption 6). Proposition 1. For twice differentiable local functions f 1 , . . . , f n : R dx × R dy → R, we have• If functions {f i } n i=1hold the δ-average-second-order similarity, then they also hold the δ-secondorder similarity.• If functions {f i } n i=1 hold the δ-second-order similarity, then they hold the 2δ-average-secondorder similarity.Proof. If functions {f i } n i=1 hold the δ-average-second-order similarity, then for all j ∈ [n], we have∥∇ 2 f j (x, y) -∇ 2 f (x, y)∥ 2 2 = 1 n n i=1 ∇ 2 f j (x, y) -∇ 2 f i (x, y) 2 2 ≤ 1 n n i=1 ∥∇ 2 f j (x, y) -∇ 2 f i (x, y)∥ 2 2 ≤ δ 2 ,where we use the convexity of ∥ • ∥ 2 2 . This implies functions {f i } n i=1 also hold the δ-second-order similarity.If functions {f i } n i=1 hold the δ second-order similarity, then for all j ∈ [n], we have1 n n i=1 ∥∇ 2 f j (x, y) -∇ 2 f i (x, y)∥ 2 2 ≤ 1 n n i=1 2∥∇ 2 f j (x, y) -∇ 2 f (x, y)∥ 2 2 + 2∥∇ 2 f (x, y) -∇ 2 f i (x, y)∥ 2 2 ≤ (2δ) 2 ,where we use the Young's inequality for the matrix 2-norm. This implies functions {f i } n i=1 hold the 2δ-average-second-order similarity.Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: [Yes] See Section 7 and Appendix H.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA]Justification: [NA] The paper focuses on optimizing algorithmic enhancements unrelated to potential social impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • 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). 
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: [Yes] The original paper for used LIBSVM dataset is cited.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. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Our convergence analysis is based on the following Lyapunov functionΦ k = 1 η + µ ∥z k -z * ∥ 2 + 2⟨F (z k-1 ) -F 1 (z k-1 ) -F (z k ) + F 1 (z k ), z k -z * ⟩ + 1 64η ∥z k -z k-1 ∥ 2 + γ 2η ∥w k-1 -z k ∥ 2 + (2γ + ηµ) 2pη ∥w k -z * ∥ 2 .Noticing that we can always guarantees Φ k ≥ 0 by taking η ≤ 1/(32δ), because the Young's inequality and Lemma 3 indicatesΦ k ≥ 1 η ∥z k -z * ∥ 2 + 2⟨F (z k-1 ) -F 1 (z k-1 ) -F (z k ) + F 1 (z k ), z k -z * ⟩ + 1 64η ∥z k -z k-1 ∥ 2 ≥ 1 η ∥z k -z * ∥ 2 - 1 64ηδ 2 ∥F (z k-1 ) -F 1 (z k-1 ) -F (z k ) + F 1 (z k )∥ 2 -64ηδ 2 ∥z k -z * ∥ 2 + 1 64η ∥z k -z k-1 ∥ 2 ≥ 1 η ∥z k -z * ∥ 2 - 1 64ηδ 2 δ 2 ∥z k -z k-1 ∥ 2 -64ηδ 2 ∥z k -z * ∥ 2 + 1 64η ∥z k -z k-1 ∥ 2 = 1 2η (2 -128η 2 δ 2 )∥z k -z * ∥ 2 ≥ 0.We provide the proofs for results in Section 5.In later analysis, we denote E k [•] as the expectation with respect to the random sampled set S k in round k and denote E k+1/2 [•] as the expectation with respect to the random update of the snapshot point w k in round k. Specifically, we take the constantEQUATIONfor the statement of Lemma 1.We first provide several lemmas that will be used in the proof of Lemma 1. Lemma 5. Under the setting of Lemma 1, we have-2E ⟨δ k -E k [δ k ], ûk -z k ⟩ ≤ 1 2η E ∥û k -z k ∥ 2 + 4ηδ 2 b E ∥z k -w k-1 ∥ 2 + 4ηδ 2 α 2 b E ∥z k -z k-1 ∥ 2 ,and-2E ⟨E k [δ k ] + F 1 (û k ) -F (z * ), ûk -z * ⟩ ≤ 2δ 2 µ E ∥û k -u k ∥ 2 + µ 2 E ∥û k -z * ∥ 2 -2µE ∥û k -z * ∥ 2 + 1 64η E ∥z k -z k+1 ∥ 2 + 64ηδ 2 E ∥û k -u k ∥ 2 -2E ⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z * ⟩ + 1 4η E ∥z k -ûk ∥ 2 + 4ηδ 2 α 2 E ∥z k -z k-1 ∥ 2 -2αE ⟨F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1 ), z k -z * ⟩ .Proof. Firstly note thatE k [δ k ] = F (z k ) -F 1 (z k ) + α F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1) . According to the uniform and independent sampling and Lemma 3 we haveE ∥δ k -E k [δ k ]∥ 2 ≤ 2E 1 b j∈S k F j (z k ) -F j (w k-1 ) -F (z k ) -F (w k-1 ) 2 + 2E α b j∈S k F j (z k ) -F j (z k-1 ) -F (z k ) -F (z k-1 ) 2 = 2 b 2 E   j∈S k F j (z k ) -F j (w k-1 ) -F (z k ) -F (w k-1 ) 2   + 2α 2 b 2 E   j∈S k F j (z k ) -F j (z k-1 ) -F (z k ) -F (z k-1 ) 2   ≤ 2 nb E   n j=1 F j (z k ) -F j (w k-1 ) -F (z k ) -F (w k-1 ) 2   + 2α 2 nb E   n j=1 F j (z k ) -F j (z k-1 ) -F (z k ) -F (z k-1 ) 2   ≤ 2δ 2 b E ∥z k -w k-1 ∥ 2 + 2δ 2 α 2 b E ∥z k -z k-1 ∥ 2 .According to the above bound onE ∥δ k -E k [δ k ]∥ 2, we achieve the first result as follows-2E ⟨δ k -E k [δ k ], ûk -z k ⟩ ≤ 1 2η E ∥û k -z k ∥ 2 + 2ηE ∥δ k -E k [δ k ]∥ 2 ≤ 1 2η E ∥û k -z k ∥ 2 + 4ηδ 2 b E ∥z k -w k-1 ∥ 2 + 4ηδ 2 α 2 b E ∥z k -z k-1 ∥ 2 .Again using Lemma 3, we achieve the second result as follows-2E ⟨E k [δ k ] + F 1 (û k ) -F (z * ), ûk -z * ⟩ = -2E ⟨F (z k ) -F 1 (z k ) + α F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1 ) , ûk -z * ⟩ -2E ⟨F 1 (û k ) -F (z * ), ûk -z * ⟩ = -2E ⟨F (u k ) -F 1 (u k ) -F (û k ) + F 1 (û k ), ûk -z * ⟩ -2E ⟨F (û k ) -F (z * ), ûk -z * ⟩ -2E ⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), ûk -z k+1 ⟩ -2E ⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z * ⟩ -2αE ⟨F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1 ), ûk -z k ⟩ -2αE ⟨F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1 ), z k -z * ⟩ ≤ 2δ 2 µ E ∥û k -u k ∥ 2 + µ 2 E ∥û k -z * ∥ 2 -2µE ∥û k -z * ∥ 2 + 1 64η E ∥z k -z k+1 ∥ 2 + 64ηδ 2 E ∥û k -u k ∥ 2 -2E ⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z * ⟩ + 1 4η E ∥z k -ûk ∥ 2 + 4ηδ 2 α 2 E ∥z k -z k-1 ∥ 2 -2αE ⟨F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1 ), z k -z * ⟩ .Lemma 6. Under setting of Lemma 1, we have- 1 8η E ∥û k -z k ∥ 2 - γ η E ∥w k -ûk ∥ 2 - 3µ 2 E ∥û k -z * ∥ 2 ≤ - 1 16η E ∥û k -z k ∥ 2 - 1 32η E ∥z k+1 -z k ∥ 2 + 1 8η + 3µ E ∥û k -u k ∥ 2 - γ 2η E ∥w k -ûk ∥ 2 - γ 4η E ∥w k -z k+1 ∥ 2 -µE ∥z k+1 -z * ∥ 2 .Proof. From the facts ∥a + b∥ 2 ≥ 1 2 ∥a∥ 2 -∥b∥ 2 and 3 2 ∥a + b∥ 2 ≥ ∥a∥ 2 -3∥b∥ 2 , we have- 1 8η E ∥û k -z k ∥ 2 ≤ - 1 16η E ∥û k -z k ∥ 2 - 1 32η E ∥z k+1 -z k ∥ 2 + 1 16η E ∥û k -u k ∥ 2 , - γ η E ∥w k -ûk ∥ 2 ≤ - γ 2η E ∥w k -ûk ∥ 2 - γ 4η E ∥w k -z k+1 ∥ 2 + γ 2η E ∥û k -u k ∥ 2 ≤ - γ 2η E ∥w k -ûk ∥ 2 - γ 4η E ∥w k -z k+1 ∥ 2 + 1 16η E ∥û k -u k ∥ 2 ,and- 3µ 2 E ∥û k -z * ∥ 2 ≤ -µE ∥z k+1 -z * ∥ 2 + 3µE ∥û k -u k ∥ 2 ,where we use the setting γ ≤ 1/8 in the second inequality.Lemma 7. Under setting of Lemma 1, we have1 η + µ E ∥z k+1 -z * ∥ 2 + 2E ⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z * ⟩ + 1 64η E ∥z k+1 -z k ∥ 2 + γ 4η E ∥w k -z k+1 ∥ 2 + γ + 1 2 ηµ pη E ∥w k+1 -z * ∥ 2 ≤ 1 η + µ 2 E ∥z k -z * ∥ 2 + 2αE ⟨F (z k-1 ) -F 1 (z k-1 ) -F (z k ) + F 1 (z k ), z k -z * ⟩ + α 1 64η E ∥z k -z k-1 ∥ 2 + 4ηδ 2 b E ∥w k-1 -z k ∥ 2 - 1 16η E ∥z k -ûk ∥ 2 + - 7 8η + 2δ 2 µ + 64ηδ 2 + 3µ E ∥û k -u k ∥ 2 + 2 η E ∥û k -u k ∥∥z k+1 -z * ∥ + 1 - pηµ 2γ + ηµ (γ + 1 2 ηµ) pη E ∥w k -z * ∥ 2 - γ 2η E ∥w k -ûk ∥ 2 .Proof. The optimality of ûk impliesEQUATIONCombine equation (15) with the update rule in Line 7 of Algorithm 1 and ⟨-γF (z * ), z * -ûk ⟩ ≥ 0, we achieveEQUATION)Using the result of equation ( 16), we have1 η ∥û k -z * ∥ 2 = 1 η ∥z k -z * ∥ 2 + 2 η ⟨û k -z k , ûk -z * ⟩ - 1 η ∥û k -z k ∥ 2 = 1 η ∥z k -z * ∥ 2 + 2γ η ⟨w k -z k , ûk -z * ⟩ -2⟨δ k , ûk -z * ⟩ - 1 η ∥û k -z k ∥ 2 - 2 η ⟨z k -ûk -ηδ k , ûk -z * ⟩ ≤ 1 η ∥z k -z * ∥ 2 + 2γ η ⟨w k -z k , ûk -z * ⟩ -2⟨δ k , ûk -z * ⟩ - 1 η ∥û k -z k ∥ 2 -2⟨F 1 (û k ) -F (z * ), ûk -z * ⟩ = 1 η ∥z k -z * ∥ 2 + γ η ∥w k -z * ∥ 2 - γ η ∥w k -ûk ∥ 2 - γ η ∥z k -z * ∥ 2 - 1 -γ η ∥û k -z k ∥ 2 -2⟨δ k -E k [δ k ], ûk -z k + z k -z * ⟩ -2⟨E k [δ k ] + F 1 (û k ) -F (z * ), ûk -z * ⟩.Taking the expectation on above result and using the factE ⟨δ k -E k [δ k ], z k -z * ⟩ = E E k ⟨δ k -E k [δ k ], z k -z * ⟩ = 0,we obtainEQUATIONApplying Lemma 5 to bound the term (17) , we obtain-2E ⟨δ k -E k [δ k ], ûk -z k ⟩ in equationEQUATION-2E ⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z * ⟩ - 3µ 2 E ∥û k -z * ∥ 2 -2αE ⟨F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1 ), z k -z * ⟩ ,where we use the setting γ ≤ 1/8 in the second inequality.Then we consider the terms related to û. Firstly, we haveEQUATIONApplying Lemma 6 and plugging equation (19) into equation ( 18), we haveEQUATION)where we use the fact that 256η2 δ 2 α 2 /b + 256η 2 δ 2 α 2 ≤ α to bound the coefficient before the term of E ∥z k -z k-1 ∥ 2 .Then we add the termEQUATIONto both sides of equation (20) and use the update rule in Line 10 of Algorithm 1 to obtainγ + 1 2 ηµ pη E ∥w k+1 -z * ∥ 2 = γ + 1 2 ηµ pη E E w k+1 ∥w k+1 -z * ∥ 2 = γ + 1 2 ηµ η E ∥z k -z * ∥ 2 + (γ + 1 2 ηµ)(1 -p) pη E ∥w k -z * ∥ 2 ,andγ η + (γ + 1 2 ηµ)(1 -p) pη = 1 -p + pγ (γ + 1 2 ηµ) (γ + 1 2 ηµ) pη = 1 - pηµ 2γ + ηµ (γ + 1 2 ηµ) pη .Combining all above results, we achieve1 η + µ E ∥z k+1 -z * ∥ 2 + 2E ⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z * ⟩ + 1 64η E ∥z k+1 -z k ∥ 2 + γ 4η E ∥w k -z k+1 ∥ 2 + γ + 1 2 ηµ pη E ∥w k+1 -z * ∥ 2 ≤ 1 η + µ 2 E ∥z k -z * ∥ 2 + 2αE ⟨F (z k-1 ) -F 1 (z k-1 ) -F (z k ) + F 1 (z k ), z k -z * ⟩ + α 64η E ∥z k -z k-1 ∥ 2 + 4ηδ 2 b E ∥w k-1 -z k ∥ 2 - 1 16η E ∥z k -ûk ∥ 2 + - 7 8η + 2δ 2 µ + 64ηδ 2 + 3µ E ∥û k -u k ∥ 2 + 2 η E ∥û k -u k ∥∥z k+1 -z * ∥ + 1 - pηµ 2γ + ηµ (γ + 1 2 ηµ) pη E ∥w k -z * ∥ 2 - γ 2η E ∥w k -ûk ∥ 2 .Lemma 8. Under setting of Lemma 1, we additionally assume E[Φ k ] ≤ Φ 0 holds, then we haveE[Φ k+1 ] ≤ max 1 - ηµ 6 , 1 - pηµ 2γ + ηµ E[Φ k ] - 1 16η E ∥z k -ûk ∥ 2 - γ 2η E ∥w k -ûk ∥ 2 .Proof. Recall that the definition of our Lyapunov function isEQUATION)Recall that we take constant c by equation ( 14), then the conditionEQUATIONThe inequality ( 23) is based on the assumptionE[Φ k ] ≤ Φ 0 . Note that we have ∥z k+1 -z * ∥ ≤ ∥u k -ûk ∥ + ∥û k -z k ∥ + ∥z k -z * ∥, then - 7 8η + 2δ 2 µ + 64ηδ 2 + 3µ E ∥û k -u k ∥ 2 + 2 η E ∥û k -u k ∥∥z k+1 -z * ∥ ≤ 9 8η + 2δ 2 µ + 64ηδ 2 + 3µ E ∥û k -u k ∥ 2 + 2 η E ∥û k -u k ∥∥û k -z k ∥ + 2 η E ∥û k -u k ∥∥z k -z * ∥ ≤ 9 8η + 2δ 2 µ + 64ηδ 2 + 3µ E ∥û k -u k ∥ 2 + 2 η E ∥û k -u k ∥∥û k -z k ∥ + 2 2E[Φ k ] η E ∥û k -u k ∥ ≤ 1 32η E ∥û k -z k ∥ 2 .According to Lemma 7, we have1 η + µ E ∥z k+1 -z * ∥ 2 + 2E ⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z * ⟩ + 1 64η E ∥z k+1 -z k ∥ 2 + γ 4η E ∥w k -z k+1 ∥ 2 + γ + 1 2 ηµ pη E ∥w k+1 -z * ∥ 2 ≤ 1 η + µ 2 E ∥z k -z * ∥ 2 + 2αE ⟨F (z k-1 ) -F 1 (z k-1 ) -F (z k ) + F 1 (z k ), z k -z * ⟩ + α 1 64η E ∥z k -z k-1 ∥ 2 + 4ηδ 2 b E ∥w k-1 -z k ∥ 2 + 1 32η E ∥z k -ûk ∥ 2 - 1 16η E ∥z k -ûk ∥ 2 - γ 2η E ∥w k -ûk ∥ 2 + 1 - pηµ 2γ + ηµ (γ + 1 2 ηµ) pη E ∥w k -z * ∥ 2 .From the facts 4ηδ 2 /b ≤ αγ/(4η) and ηµ ≤ 1, we obtain (1/η + µ/2) ≤ (1/η + µ)(1 -ηµ/6). Thus, it holds1 η + µ E ∥z k+1 -z * ∥ 2 + 2E ⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z * ⟩ + 1 64η E ∥z k+1 -z k ∥ 2 + γ 4η E ∥w k -z k+1 ∥ 2 + γ + 1 2 ηµ pη E ∥w k+1 -z * ∥ 2 ≤ 1 - ηµ 6 1 η + µ E ∥z k -z * ∥ 2 + 1 - pηµ 2γ + ηµ (γ + 1 2 ηµ) pη E ∥w k -z * ∥ 2 + 2αE ⟨F (z k-1 ) -F 1 (z k-1 ) -F (z k ) + F 1 (z k ), z k -z * ⟩ + α 1 64η E ∥z k -z k-1 ∥ 2 + α γ 2η E ∥w k-1 -z k ∥ 2 - 1 16η E ∥z k -ûk ∥ 2 - γ 2η E ∥w k -ûk ∥ 2 .The definition (22) and the setting α = max {1 -ηµ/6, 1 -pηµ/(2γ + ηµ)} impliesEQUATION)Then we provide the proof of Lemma 1.Proof. We firstly use the induction to proveE[Φ k ] ≤ Φ 0holds for all k ∈ N.Note that it holds for k = 0. Assume we have E[Φ k ] ≤ Φ 0 holds, then Lemma 8 means it holdsE[Φ k+1 ] ≤ max 1 - ηµ 6 , 1 - pηµ 2γ + ηµ E[Φ k ] ≤ E[Φ k ] ≤ Φ 0 ,which finish the induction.The result of above induction implies the condition of Lemma 8 always holds. Therefore, we can apply Lemma 8 to achieve equation (24) , which finishes the proof of Lemma 1.We firstly introduce the following quantities for our analysisEQUATIONSpecifically, we take the constantEQUATIONandEQUATIONfor the statement Theorem 1. We then provide several lemmas that will be used in the proof of Theorem 1. Lemma 9. Under the setting of Theorem 1, we have-2⟨E k [δ k ] + F 1 (û k ), ûk -z⟩ ≤ 4LD∥u k -ûk ∥ + 2⟨F (u k ), z -u k ⟩ + (8LD + 6D F )∥û k -u k ∥ + 1 16η ∥z k -z k+1 ∥ 2 + 16ηδ 2 ∥û k -u k ∥ 2 -2⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z⟩ + 1 2η ∥z k -ûk ∥ 2 + 2ηδ 2 α 2 ∥z k -z k-1 ∥ 2 -2α⟨F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1 ), z k -z⟩,whereD F := max i∈[n] sup z∈Z ∥F i (z)∥.Proof. Note that the sequence {∥F i (z)∥} n i=1 is bounded on z ∈ Z, since we haveEQUATION)The Lipschitz continuity of F (•) impiesEQUATIONLemma 10. Under the setting of Theorem 1, the quantities defined in equation ( 25) holdmax z∈Z Ψ 0 (z) + E max z∈Z K-1 k=0 e 11 (z, k) + e 12 (z, k) + γ p e 2 (z, k) ≤ max z∈Z 4∥z 0 -z∥ 2 + 4η 2 δ 2 b K-1 k=0 E ∥z k -ûk ∥ 2 + 2p + 4η 2 δ 2 b K-1 k=0 E ∥w k -ûk ∥ 2 + 2p + 8η 2 δ 2 b K-1 k=0 E ∥û k -u k ∥ 2 .Proof. Applying Lemma 4 with x 0 = z 0 , F 0 = σ(S 0 ), F k = σ(S 0 , . . . , S k-1 , w k ) for k ≥ 1, andr k+1 = 2η b j∈S k F j (z k ) -F (z k ) -F j (w k-1 ) + F (w k-1) and using E k [r k+1 ] = 0, we haveE max z∈Z K-1 k=0 e 11 (z, k) = E max z∈Z K-1 k=0 ⟨r k+1 , z⟩ ≤ max z∈Z 1 2 ∥z 0 -z∥ 2 + 1 2 K-1 k=0 E ∥r k+1 ∥ 2 ≤ max z∈Z 1 2 ∥z 0 -z∥ 2 + 2η 2 δ 2 b K-1 k=0 E ∥z k -w k-1 ∥ 2 .Similarly we can obtainE max z∈Z K-1 k=0 e 12 (z, k) ≤ max z∈Z 1 2 ∥z 0 -z∥ 2 + 2η 2 α 2 δ 2 b K-1 k=0 E ∥z k -z k-1 ∥ 2 .Applying Lemma 4 with x 0 = z 0 , F 0 = σ(S 0 ), F k = σ(S 0 , . . . , S k-1 , w k ) for k ≥ 1, and r k+1 = pz k+1 +(1-p)w k -w k+1 and using the fact thatE[∥w k+1 ∥ 2 -p∥z k+1 ∥ 2 -(1-p)∥w k ∥ 2 ] = 0 and E k [r k+1 ] = 0, we have E max z∈Z K-1 k=0 e 2 (z, k) = 2E max z∈Z K-1 k=0 ⟨r k+1 , z⟩ ≤ max z∈Z ∥z 0 -z∥ 2 + K-1 k=0 E ∥r k+1 ∥ 2 ≤ max z∈Z ∥z 0 -z∥ 2 + p(1 -p) K-1 k=0 E ∥z k+1 -w k ∥ 2 ,where we useE ∥r k+1 ∥ 2 = E E k+1/2 ∥E k+1/2 [w k+1 ] -w k+1 ∥ 2 = E E k+1/2 [∥w k+1 ∥ 2 ] -∥E k+1/2 [w k+1 ]∥ 2 = E p∥z k+1 ∥ 2 + (1 -p)∥w k ∥ 2 -∥pz k+1 + (1 -p)w k ∥ 2 = p(1 -p)E ∥z k+1 -w k ∥ 2 .Note that z k = u k-1 , then we havemax z∈Z Ψ 0 (z) + E max z∈Z K-1 k=0 e 11 (z, k) + e 12 (z, k) + γ p e 2 (z, k) ≤ 4 max z∈Z ∥z 0 -z∥ 2 + 2η 2 δ 2 b K-1 k=0 E ∥z k -w k-1 ∥ 2 + 2η 2 α 2 δ 2 b K-1 k=0 E ∥z k -z k-1 ∥ 2 + p(1 -p) K-1 k=0 E ∥z k+1 -w k ∥ 2 ≤ 4 max z∈Z ∥z 0 -z∥ 2 + 4η 2 δ 2 b K-1 k=0 E ∥û k-1 -w k-1 ∥ 2 + 4η 2 α 2 δ 2 b K-1 k=0 E ∥û k-1 -z k-1 ∥ 2 + 2p K-1 k=0 E ∥û k -w k ∥ 2 + 4η 2 δ 2 b + 4η 2 α 2 δ 2 b + 2p K-1 k=0 E ∥û k -u k ∥ 2 ≤ 4 max z∈Z ∥z 0 -z∥ 2 + 4η 2 δ 2 b K-1 k=0 E ∥z k -ûk ∥ 2 + 2p + 4η 2 δ 2 b K-1 k=0 E ∥w k -ûk ∥ 2 + 2p + 8η 2 δ 2 b K-1 k=0 E ∥û k -u k ∥ 2 ,where we use Young's inequality and α ≤ 1.Proof. The optimality of ûk implies for all z ∈ Z, we haveEQUATION)Combine equation (30) with the update rule in Line 7 of Algorithm 1 , we achieveEQUATION)Then we haveEQUATIONCombining the results of equation (32) with Lemma 9, we haveEQUATIONwhere we use the fact γ ≤ 1/4.From the fact that ∥a + b∥ 2 ≥ 1 2 ∥a∥ 2 -∥b∥ 2 and 3 2 ∥a + b∥ 2 ≥ ∥a∥ 2 -3∥b∥ 2 , we haveEQUATION)Plugging equation (34) into equation ( 33), we achieve1 η ∥û k -z∥ 2 ≤ 1 η ∥z k -z∥ 2 + γ η ∥w k -z∥ 2 - γ η ∥z k -z∥ 2 - 1 8η ∥z k+1 -z k ∥ 2 + 1 4η ∥û k -u k ∥ 2 + 2⟨F (u k ), z -u k ⟩ + (12LD + 6D F )∥û k -u k ∥ + 1 16η ∥z k -z k+1 ∥ 2 -2⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z⟩ + 16ηδ 2 ∥û k -u k ∥ 2 -2α⟨F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1 ), z k -z⟩ + 2ηδ 2 α 2 ∥z k -z k-1 ∥ 2 - γ 2η ∥w k -z k+1 ∥ 2 + γ η ∥û k -u k ∥ 2 + 1 η e 11 (z, k) + 1 η e 12 (z, k) ≤ 1 η ∥z k -z∥ 2 + γ η ∥w k -z∥ 2 - γ η ∥z k -z∥ 2 - 1 16η ∥z k+1 -z k ∥ 2 - γ 2η ∥w k -z k+1 ∥ 2 + 2⟨F (u k ), z -u k ⟩ + (12LD + 6D F )∥û k -u k ∥ -2⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z⟩ + 2ηδ 2 α 2 ∥z k -z k-1 ∥ 2 -2α⟨F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1 ), z k -z⟩ + 16ηδ 2 + 1 2η ∥û k -u k ∥ 2 + 1 η e 11 (z, k) + 1 η e 12 (z, k).Note that the fact1 η ∥û k -z∥ 2 = 1 η ∥z k+1 -z∥ 2 + 1 η ∥û k -u k ∥ 2 - 2 η ∥û k -u k ∥∥z k+1 -z∥,then we have2⟨F (u k ), u k -z⟩ ≤ - 1 η ∥z k+1 -z∥ 2 - 1 η ∥û k -u k ∥ 2 + 2 η ∥û k -u k ∥∥z k+1 -z∥ + 1 η ∥z k -z∥ 2 + γ η ∥w k -z∥ 2 - γ η ∥z k -z∥ 2 - 1 16η ∥z k+1 -z k ∥ 2 - γ 2η ∥w k -z k+1 ∥ 2 + (12LD + 6D F )∥û k -u k ∥ + 2ηδ 2 α 2 ∥z k -z k-1 ∥ 2 -2⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z⟩ -2α⟨F (z k ) -F 1 (z k ) -F (z k-1 ) + F 1 (z k-1 ), z k -z⟩ + 16ηδ 2 + 1 2η ∥û k -u k ∥ 2 + 1 η e 11 (z, k) + 1 η e 12 (z, k) ≤ - 1 η ∥z k+1 -z∥ 2 - 1 16η ∥z k+1 -z k ∥ 2 - γ 2η ∥z k+1 -w k ∥ 2 -2⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z⟩ + 1 η ∥z k -z∥ 2 + γ η ∥w k -z∥ 2 - γ η ∥z k -z∥ 2 + 2ηδ 2 α 2 ∥z k -z k-1 ∥ 2 + 2α⟨F (z k-1 ) -F 1 (z k-1 ) -F (z k ) + F 1 (z k ), z k -z⟩ + 12LD + 6D F + 2D η ∥û k -u k ∥ + 16ηδ 2 ∥û k -u k ∥ 2 + 1 η e 11 (z, k) + 1 η e 12 (z, k) ≤ - 1 -γ η ∥z k+1 -z∥ 2 - γ ηp ∥w k+1 -z∥ 2 - 1 16η ∥z k+1 -z k ∥ 2 -2⟨F (z k ) -F 1 (z k ) -F (z k+1 ) + F 1 (z k+1 ), z k+1 -z⟩ + 1 -γ η ∥z k -z∥ 2 + γ ηp ∥w k -z∥ 2 + 2ηδ 2 α 2 ∥z k -z k-1 ∥ 2 + 2α⟨F (z k-1 ) -F 1 (z k-1 ) -F (z k ) + F 1 (z k ), z k -z⟩ + 12LΩ + 6D F + 2D η ∥û k -u k ∥ + 16ηδ 2 ∥û k -u k ∥ 2 + 1 η e 11 (z, k) + e 12 (z, k) + γ p e 2 (z, k) - γ 2η ∥z k+1 -w k ∥ 2 .The parameters settings implies 2ηδ 2 α 2 ≤ 1/(16η), then we haveEQUATION)Recall that we take ĉ by equation ( 27), then the settingε k = min ζ, ĉ-1 min ∥û k -z k ∥, ∥û k -z k ∥ 2satisfies the condition on ε k in Lemma 1. Then we apply Lemma 1 with µ = 0 and α = 1 and sum over equation ( 9) with k = 0, . . . , K -1 to obtainEQUATION)Note that parameter settings γ = p = 1/( √ n + 8), b = ⌈ √ n⌉, and η = min √ γb/(4δ), 1/(32δ) satisfyEQUATION)Substituting equations ( 36) and (37) into equation (35) and applying Lemma 10, we obtainE max z∈Z 1 K K-1 k=0 ⟨F (u k ), u k -z⟩ ≤ 1 2ηK (4 + 8 • 2) max z∈Z ∥z 0 -z∥ 2 + 1 2ηK K-1 k=0 (12ηLD + 6ηD F + 2D) ∥û k -u k ∥ + 16η 2 δ 2 + 8η 2 δ 2 b + 2p ∥u k -ûk ∥ 2 ≤ 10D 2 ηK + 6ηLD + 3ηD F + D η ζ + 12η 2 δ 2 + 1 η ζ ≤ 10D 2 ηK + 9ηLD + 3η max i∈[n] ∥F i (z 0 )∥ + D η ζ + 12η 2 δ 2 + 1 η ζ,where we use the equation (28) to bound D F .Recall that we take constant ζ by equation ( 26), then we get the boundE max z∈Z 1 K K-1 k=0 ⟨F (u k ), u k -z⟩ ≤ 10D 2 ηK + ε 2 .Proof. Theorem 1 means we can achieve E[Gap(u K avg )] ≤ ε by taking the communication rounds ofK = 20D 2 εη = O D 2 εη = O δD 2 ε .Consider that the expected communication complexity in each round is O(b(1 -p) + np) = O( √ n) and the server need to communicate with all client in initialization within the communication complexity of O(n), the overall communication complexity isO(n) + K • O( √ n) = O n + √ nδD 2 ε .Note that the objective of the sub-problem in Line 8 of Algorithm 1 is (L + 1/η)-smooth-(1/η)strongly-convex-(1/η)-strongly-concave, the local gradient complexity for solving the sub-problem is O((1 + ηL) log(max{ζ -1 , ĉ}). Therefore, the overall local gradient complexity isO(n) + K • O( √ n) + O (1 + ηL) log(ζ -1 + ĉ) = O(n) + O δD 2 ε • O( √ n) + O 1 + L δ log LD + D F ε + Φ 0 δ = Õ n + ( √ nδ + L)D 2 ε log 1 ε .Proof. We can verify that the parameter setting of Theorem 2 satisfies the condition of Lemma 1.Then we can apply Lemma 1 to obtainEQUATIONProof. Recall that we set the parameters asγ = p = 1 min √ n, δ µ + 8 , b = min √ n, δ µ , η = min √ γb 4δ , 1 32δ , α = max 1 - ηµ 6 , 1 - pηµ 2γ + ηµ .We can lower bound α asEQUATIONThen the number of communication rounds isK = O 1 + 1 ηµ + γ + ηµ pηµ log 1 ε = O 1 p + 1 ηµ log 1 ε = O 1 p + 1 µ 32δ + 32δ √ αγb log 1 ε = O 1 p + δ µ + 1 √ pb δ µ log 1 ε .memories with the clients with numbers from S, i.e. can add points x ′ i , y ′ i to the corresponding local memories of client i asx ′ i ∈ span {x 1 , x i } and y ′ i ∈ span {y 1 , y i } ,where x i ∈ M x i and y i ∈ M y i , and we say that it costs b communication complexity. • Local computations: During local computations each client i can make any computations using f i , i.e. can add points x ′ i , y ′ i to the corresponding local memory of client i asx ′ i ∈ span {x ′ , ∇ x f i (x ′′ , y ′′ )} and y ′ i ∈ span {y ′ , ∇ y f i (x ′′ , y ′′ )} ,for given x ′ , x ′′ ∈ M x i and y ′ , y ′′ ∈ M y i . And we use local gradient calls to count the times when ∇ x and ∇ y are applied to any one of {f i }.The final global output is calculated asx ∈ M x 1 , ŷ ∈ M y 1 .Our Definition 1 follows the algorithm class of Beznosikov et al. [8, Definition C.7 ], but additionally take the communication from the server to the clients into considerations.In this section, we provide the proofs of the lower bounds for solving the problemEQUATIONby DFO algorithms, where the diameters of closed convex sets X and Y are R x and R y respectively. We define the subspaces {F k } d k=0 asF k = span{e 1 , . . . , e k }, for 1 ≤ k ≤ d, {0 d }, for k = 0,which is used in the following proofs of lower bounds.We first define the function set with one server (i = 1) and n -1 clients (i = 2, . . . , n -1) as followsEQUATIONThen corresponding global objective isEQUATIONwhereEQUATION)Proposition 2. For any d ≥ 3, the functions f i (x, y) and f (x, y) defined by equations ( 41) and ( 42) satisfy 1. The function f i is L-smooth with L ≥ δ and convex-concave for all i ∈ [n], and the function set {f i } n i=1 holds δ-second-order similarity. Thus, the function f is also convex-concave.EQUATIONProof. The smoothness and the convexity (concavity) are easy to verify. The similarity holds because∇ 2 xx f 1 (x, y) -∇ 2 xx f (x, y) = ∇ 2 xx f 2 (x, y) -∇ 2 xx f (x, y) = ∇ 2 xx f 3 (x, y) -∇ 2 xx f (x, y) = 0; ∇ 2 yy f 1 (x, y) -∇ 2 yy f (x, y) = ∇ 2 yy f 2 (x, y) -∇ 2 yy f (x, y) = ∇ 2 yy f 3 (x, y) -∇ 2 yy f (x, y) = 0; ∥∇ 2 xy f 1 (x, y) -∇ 2 xy f (x, y)∥ ≤ ∥∇ 2 xy f 1 (x, y)∥ + ∥∇ 2 xy f (x, y)∥ ≤ δ 3 ≤ δ; ∥∇ 2 xy f 2 (x, y) -∇ 2 xy f (x, y)∥ ≤ ∥∇ 2 xy f 2 (x, y)∥ + ∥∇ 2 xy f (x, y)∥ ≤ δ 5 8 + 1 3 ≤ δ; ∥∇ 2 xy f 3 (x, y) -∇ 2 xy f (x, y)∥ ≤ ∥∇ 2 xy f 3 (x, y)∥ + ∥∇ 2 xy f (x, y)∥ ≤ δ 5 8 + 1 3 ≤ δ.The function f (x, y) defined by our equation ( 42) is identical to the function f CC (x, y) defined by Han et al. [14, Proposition 3.31]3 by replacing their notation L with our δ and taking n = 3. Then Proposition 3.31 of Han et al. [14] directly prove the result of equation ( 44).The structure of A 1 and A 2 results the following lemma. Lemma 11. For the function set (41) , all (x, y) ∈ F k × F k and k = 0, . . . , d -1, we have∇f i (x, y) ∈ F k+1 × F k+1 , (i, k) ∈ I 1 ∪ I 2 , F k × F k , otherwise,where the index sets are defined as I 1 := {(i, k) : i -1 ≡ 1 (mod 3), k ≡ 0 (mod 2)} andI 2 := {(i, k) : i -1 ≡ 2 (mod 3), k ≡ 1 (mod 2)}.Now we provide the proof of Theorem 3.Proof. Consider the minimax problem (40) with functions ( 41) and (42) ,EQUATION2) implies d ≥ 3. Lemma 11 means that we need at least one communication round to increase the number of non-zero coordinate, i.e. (x, y) ∈ Z ∩ F 2 K . Running any DFO algorithm with communication rounds of K = ⌊(d -1)/2⌋ ≥ 1, we have d/2 ≤ (K + 1) ≤ (d + 1)/2 and Proposition 2 impliesE[Gap(x, y)] ≥ min (x,y)∈Z∩F 2 K Gap(x, y) ≥ δD 2 6 d(K + 1) ≥ δD 2 6 √ 2(K + 1) ≥ δD 2 3 √ 2(d + 1) ≥ ε.Hence, we achieve the lower bound on the communication rounds ofK = δD 2 6 √ 2ε -1 = Ω δD 2 ε .We first define the function set with one server (i = 1) and n -1 clients (i = 2, . . . , n -1) as followsf i (x, y) =            - √ nδR y 8 √ d e ⊤ 1 x, i = 1, √ nδ 8 x ⊤ j≡(i-1)mod(n-1)e j a ⊤ j y, i ≥ 2.(EQUATIONThen corresponding global objective isEQUATIONwhere e j is the j-th basis column vector, a ⊤ j is the j-th row of A, A i = j≡(i-1) mod (n-1) e j a ⊤ j , A 1 = 0 and A is defined in equation (43) .We provide the following proposition and lemmas for the proof of Theorem 4. Proposition 3. For any d ≥ 3, f i (x, y) and f (x, y) defined as equations ( 45) and ( 46 [14] directly prove the result of equation (47) .Lemma 12. Consider the minimax problem (40) with functions ( 45) and (46) , R x = R y = D, d = ⌊δD 2 /(4 √ 2nε)⌋ -1 and ε ≤ δD 2 /(16 √ 2n). We let M = ⌊(d -1)/2⌋ ≥ Ω(δD 2 /( √ nε)), then any point (x, y) ∈ Z ∩ F 2 M satisfies Gap(x, y) ≥ ε.Proof. Proof. At initialization, M x i = M y i = F 0 . Let's analyze how M x i and M y i change through local computations. For the i-th client, we add the following points to M x i and M y i asx ∈ span {x ′ , A i y ′ } , and y ∈ spane 1 • I{i = 1}, y ′ , A ⊤ i x ′ ,where x ′ ∈ M x i and y ′ ∈ M y i . It is easy to see that the server can make the first coordinate of y non-zero using e 1 , and broadcast this progress to other clients. Only updates of the type A i y ′ or A ⊤ i x ′ will help in this regard. Since A i only contains rows from the matrix A such as the (i -1)-th row, (n + i -1)-th row, etc., to make the first coordinate of x in the global output non-zero, we need and can only use the A 2 matrix. It can be noted that by using A 2 , we can also make the second coordinate of y non-zero after making the first coordinate of x non-zero. Furthermore, to make more progress, we need to use A 3 and so on. We conclude that we must constantly transfer progress from the node currently needed (to make the next coordinate of x non-zero; then of y) to the server, and then to other nodes. By definition, one communication round involves communication with all clients or only with batches of some uniform and independent clients. When we sample without replacement, the success probability of a communication round on clients with batch size b (i.e., making one coordinate non-zero) is b n-1 (or 1 when b = n), which is also the expected number of non-zero coordinates that can be obtained with b communication complexity and at least b local gradient calls (as each use of the matrix A necessarily comes from a gradient call). When we sample with replacement by a batch size b, it is equivalent to that we sample without replacement by batch size 1 for b times. Assuming that we have communication rounds with batch sizes (sampling without replacement) of 1, 2, . . . , n for s 1 , s 2 , . . . , s n times, then the communication complexity we spent is V = n j=1 js j and the minimum gradient calls we spent is C = n j=1 js j . This implies the expected number of non-zero coordinates is M = n-1 j=1 j n-1 s j +s n . Therefore, the expected total number of non-zero coordinates in the global output is at most M for y and M -1 for x (or we can say M ). By comparing expressions of V , C and M , we can have M ≤ 2V /n and M ≤ 2C/n, completing the proof.Then we can prove Theorem 4 by combining Lemma 12 and 13.We choose the function set asEQUATIONwhere A is defined as equation (43) . The structure of A results the following lemma. Lemma 14. For the function set (48) , all (x, y) ∈ F k × F k and k = 0, . . . , d -1, we have∇f i (x, y) ∈ F k+1 × F k+1 .One can follow the similar method as the proof of Theorem 4 to prove the following proposition and lemma for the proof of Lemma 2. Proposition 4. For any d ≥ 3, f i (x, y) and f (x, y) defined as equation ( 48) satisfy 1. f i is L-smooth and convex-concave, function set {f i } n i=1 has δ second-order similarity for any δ > 0. Thus, f is convex-concave. Lemma 15. Consider the minimax problem (40) with the function set (48) ,R x = R y = D, d = ⌊δD 2 /( √ 2ε)⌋ -1 and ε ≤ δD 2 /(4 √ 2). We let M = ⌊(d -1)/2⌋ ≥ Ω(LD 2 /ε), then any point (x, y) ∈ Z ∩ F 2 M satisfies Gap(x, y) ≥ ε.Then we can prove Lemma 2 by combining Lemma 14 and 15.Proof. In the case of √ nδ ≥ Ω(L), the problem with with functions ( 45) and (46) in Theorem 4 implies the lower bound on the local gradient complexity ofΩ n + √ nδD 2 ε = Ω n + ( √ nδ + L)D 2 ε .In the case of L ≥ Ω( √ nδ), the problem with function (48) in Lemma 2 implies the lower bound on the local gradient complexity of Ω(LD 2 /ε) = Ω(n + ( √ nδ + L)D 2 /ε). Combining these two cases, we achieve the lower bound on the local gradient complexity of Ω(n + ( √ nδ + L)D 2 /ε).We follow similar steps as in Appendix E to prove Theorem 7. Firstly we divide it into several detailed theorems and lemmas as below and prove them one by one.We introduce the function set asEQUATIONwhereÃ =     1 1 -1 . . . . . . 1 -1     .Note that since all the nodes have the same function, this function set (51) satisfies Assumptions 1, 3, 4, 5, and 6 for L, µ and any δ > 0. The structure of Ã results the following lemma.Lemma 19. For the function set (51), all (x, y) ∈ F k × F k and k = 0, . . . , d -1, we have∇f i (x, y) ∈ F k+1 × F k+1 . Lemma 20. Let µ, δ, L > 0, n ∈ N, C ∈ N.There exists a centralized distributed saddle-point problem with functions (51), in which z * ̸ = 0 and d ≥ max{2 log q (α/ √ 2), 4C} where α = µ 2 /L 2 and q = 1 + 2α -2 √ α 2 + α ∈ (0, 1). Then for any DFO algorithm, the output (x C , y C ) after C local gradient calls will satisfiesEQUATIONProof. Follow the proof of Theorem 3.5 by Zhang et al. [55] , in which we take L x = L y = L xy = L and µ x = µ y = µ.Then we can prove Lemma 16 by combining Lemma 19 and 20 and noting that to reach a solution with ε-accuracy needs at least Ω(L/µ log(1/ε)) local gradient calls from equation (52) .Proof. In the case of nµ + √ nδ ≥ Ω(L), the problem with with functions ( 49) and ( 50) in Theorem 8 implies the lower bound on the local gradient complexity ofΩ n + √ nδ µ log 1 ε = Ω n + √ nδ + L µ log 1 ε .In the case of L ≥ Ω(nµ + √ nδ), the problem with function (51) in Lemma 16 implies the lower bound on the local gradient complexity of Ω(L/µ log(1/ε)) = Ω((n + ( √ nδ + L)/µ) log(1/ε)). Combining these two cases, we can achieve the lower bound on the local gradient complexity of Ω((n + (√ nδ + L)/µ) log(1/ε)).In constrained case, we can also use gradient mapping to measure the sub-optimality of a solution z, that isF τ (z) = z -P Z (z -τ F (z)) τ .For the L-smooth convex-concave function f , we consider the constrained problem where f is λ-strongly-convex-λ-strongly-concave and Z is bounded by diameter D. From the the result of Theorem 2, we have E z K -ẑ * 2 ≤ (1 -χλ/δ) K z 0 -ẑ * 2 for some constant χ (0, 1), then we haveEQUATIONE ∥F τ (z K )∥ = E z K -P Z z K -τ ( F (z K ) -λ(z K -z 0 )) τ = E P Z (z K ) -P Z z K -τ ( F (z K ) -λ(z K -z 0 )) τ ≤ E F (z K ) -λ(z K -z 0 ) ≤ E F (z K ) + λE z K -z 0 = E F (z K ) -F (ẑ * ) + λE z K -z 0 ≤ LE z K -ẑ * + λE z K -z 0 ,where we use the property of the projection that ∥P Z (z 1 ) -P Z (z 2 )∥ ≤ ∥z 1 -z 2 ∥ and the gradient mapping holds that F τ (ẑ * ) = 0. Then we haveE F (z K ) 2 ≤ 2L 2 E z K -ẑ * 2 + 2λ 2 E z K -z 0 2 ≤ 2L 2 (1 -χλ/δ) K z 0 -ẑ * 2 + 2λ 2 E z K -z 0 2 ≤ (2L 2 (1 -χλ/δ) K + 2λ 2 )D 2 . Let λ = ε/(4D 2 ) and K = O(δ/λ log(L/ε)), then we have E F (z K ) 2 ≤ ε.Hence, the complexity of communication rounds is K = O (δD/ √ ε log(L/ε)We present the experimental results on dataset "covtype" in Figure 5 and 6 .NeurIPS Paper ChecklistAlthough the complexity of TPAPP for achieving E[∥F (z)∥] 2 ≤ ε is established for the unconstrained case, its analysis additionally assume that the sequences generated by the algorithm are bounded by D > 0 [8, Theorem 5.12].We follow the notation of Han et al.[14]'s arXiv version: https://arxiv.org/pdf/2103.08280v1 


Decision: This paper studies convex-concave minimax problems in distributed settings, focusing specifically in settings where the instance satisfies a second order similarity bound. This latter condition refers to an upper bound on the Hessian of the difference between all pairs of objectives within the finite sum. Under such assumption, it is shown that algorithms converge with improved rates, compared to those which simply quantify convergence with smoothness (it should be mentioned that the rates under second-order similarity are never worse than those based on smoothness, from the fact that $L$-smoothness implies $2L$-similarity). The paper also provides matching lower bounds.

Reviewers were mostly positive about this submission. However, it appears that the technical contributions of this work are somewhat marginal:

1. The idea of using gradient sliding appears in [5], and the idea of subsampling nodes is quite standard in distributed optimization.
2. The lower bound is also an adaptation of [42] which is by now quite standard.

Furthermore, the property of Hessian similarity is quite strong. Despite these concerns, and due to the mostly positive assessment of the work, I recommend acceptance.

Reviews: review: paper_summary: paper_summary: This manuscript considers solving (strongly) convex (strongly) concave distributed minimax optimization problem. The authors proposed a stochastic variance-reduced optimistic
gradient sliding method with node sampling, named SVOGS, which achieves complexity nearly matches the obtained lower bound.
strength_weakness: strength_weakness: - The algorithm design is straightforward. The novelty of the algorithm is limited to the node sampling aspect, which is a simple and obvious adaptation from the existing methods, e.g. Ref. [5]. The authors should further clarify the unique characterisics of the algorithm.
- It seems to the reviewer that incorporating uniform and independent node sampling (c.f., Line 5 in Algorithm 1) does not present any new challenge to the convergence analysis as compared to existing methods. The authors should further clarify the technical contribution of their approach.
- The experiments utilize toy datasets, e.g., a9a, which may limit the generalizability of the results.
- The rationality of Assumption 2 should be discussed in more detail to ensure its validity and relevance to the study.
- Theorems 1 and 2 requires many hyperparameters to be set to exact values that depend on the parameters of the problem. In practice, these parameters are often very difficult to obtain, which may weaken the theoretical results in this work.
questions: questions: - The authors bring the results for minimization in Ref. [25] directly to compare with the results for the minimax problem in this paper. Does this mean that the minimax problem in this paper does not have additional difficulties compared with the minimization problem?
- The distinction between the optimistic gradient and extra-gradient methods for minimax problem should be clarified. The reviewer is curious about the possibility that the EG method in Ref. [25], combined with node sampling, could also achieve similar results.
- Refer to Weaknesses for more concerns to be addressed properly.
limitations: limitations: The (strongly) convex (strongly) concave distributed minimax optimization problem considered in this work is not applicable to most machine learning tasks and is thus of limited significance in this area.
paper_summary: paper_summary: The paper studies distributed min-max optimization under the assumption of second-order data similarity, i.e. the hessians of the objectives at different nodes are close enough. For the classes of (strongly)-convex-(strongly)-concave functions with Lipschitz gradient, lower complexity bounds are proposed. Moreover, an algorithm SVOGS is proposed that strictly reaches the lower bounds in communications and up to a logarithmic factor in local gradient calls. Therefore, the paper almost closes the gap in distributed centralized min-max optimization with data similarity.
strength_weakness: strength_weakness: There still remains a gap in the local gradient calls complexity. Maybe it can be overcome with the usage of gradient sliding technique.
questions: questions: I did not find the difference between the number of communication rounds and communication complexity. It seems that Algorithm 1 sends the same amount of information at each communication round. So why is communication complexity different from the number of communication rounds?
limitations: limitations: The work is theoretical and does not have negative societal impact.
paper_summary: paper_summary: The paper proposes SVOGS, and improved algorithm for distributed minimax optimization by client mini-batch sampling and gradient variane reduction. Theoretical rates on communication complexity and gradient computations are provided, along with their lower bounds. The analysis shows that SVOGS achieves the corresponding lower bounds. A numerical example is provided to justify the efficacy.
strength_weakness: strength_weakness: The main drawback is the experiment section. The proposed method is only tested on one small dataset, and the paper lacks the basic information on how SVOGS is implemented and tuned (e.g., parameter $b, p, \alpha, \gamma$ in Algorithm 1). It seems to me that the proposed method requires much heavier fint-tuning than prior methods thus less practically convenient. The implementation details should be provided to justify the true practical value of this method. 

Also, it should be tested on more datasets.
questions: questions: See above
limitations: limitations: NA

Comments: title: Answer to Rebuttal
comment: Thank you for the detailed response. Since most of my concerns have been well addressed, I raise my overall rating to weak accept.
Dear Authors,

Thank you for the response.