INTRODUCTION AND RELATED WORK

Many applications related to signal processing, machine learning, and robust optimization naturally take the form of min-max problems [1][2][3][4][5][6][7][8]. The objective is to simultaneously minimize and maximize the cost function with respect to specific variables such that we find the point of equilibrium (or the saddle-point). In this paper, we consider the cost function F : R px×py → R; and assume that F is convex in x and concave in y, where x ∈ R px and y ∈ R py . Thus, the objective is to find the saddle-point (x * , y * ) by minimizing F with respect to x and maximizing F with respect to y, i.e., min x∈R px max y∈R py F (x, y). A natural way to solve the above problem is by using a gradient-based method: gradient descent-ascent (GDA) [8][9][10]. GDA is well studied in literature due to its extensive applications in constrained optimization, robust regression, image reconstruction, and generative adversarial networks [4][5][6][7]. For each iteration, GDA requires the evaluation of partial gradients of F with respect to x and with respect to y, i.e., ∇ x F and ∇ y F respectively. However, for very largescale applications, data is often divided over a network of geographically distributed nodes. Therefore, the evaluation of ∇ x F and ∇ y F is practically not possible, and we can only evaluate the partial gradients with respect to the local data, i.e., for each node i, ∇ x f i and ∇ y f i (where f i is the local cost function). Moreover, heterogeneous data setting leads to local versus global cost gaps. Therefore, the local partial gradients are often very different from the global partial gradients, i.e., ∀i, ∥∇ x f i -∇ x F ∥ ̸ = 0 and ∥∇ y f i -∇ y F ∥ ̸ = 0, which leads to inexact convergence.

Existing work on distributed optimization has mainly focused on minimization problems [11][12][13][14]. Early work includes [11], which converges to an error ball around the optimal solution at a linear rate using a constant step size (and to the exact solution with a decaying step size at a sublinear rate). This error arises due to data dissimilarity across nodes. To eliminate this problem, the methods described in [12,13] use gradient tracking and converge to the optimal solution at a linear rate; see [14] for a detailed overview. [15][16][17] are also of interest where the authors propose distributed stochastic optimization methods for online problems.

Due to the distributed nature of data in several practical applications, some distributed variants of GDA are proposed recently [18][19][20][21]. In [18], the authors consider GDA in federated settings and use bounds on the dissimilarity of local cost functions possessed by the nodes using dissimilarity constants. [19] generalizes the distributed gradient descent-ascent method to any strongly connected undirected network topology but still uses similarity constants. [20,21] use gradient tracking to eliminate this problem but require strong assumptions on the cost functions (quadratic in x and y).

In this paper, we propose a distributed first-order gradient descent-ascent method (GT-GDA) that uses gradient tracking for both descent and ascent updates. The main contributions are: (i) GT-GDA addresses the data heterogeneity using gradient tracking; (ii) We use a unique analysis methodology that leverages the matrix perturbation theory of semi-simple eigenvalues to show that for (small enough) constant stepsizes, GT-GDA linearly converges to the unique saddle-point when the global cost function is strongly concave-convex.

We now describe the rest of the paper. Section 2 provides the problem formulation and the necessary assumptions. Section 3 discusses the algorithm development. Section 4 provides the main results along with the convergence analysis. Section 5 illustrates the performance of GT-GDA in different numerical experiments. Section 6 concludes the paper.

PROBLEM FORMULATION

In this paper, we consider a saddle-point problem distributed over a strongly connected network of n nodes, i.e., P : min

where the local cost function, at node i, is defined as:

for P i ∈ R py×px and, the global cost is F (x, y) := G(x) + ïy, P xð-H(y), for P := 1 n n i=1 P i . We next describe some assumptions necessary to ensure the convergence of GT-GDA.

Assumption 1 (Network connectivity). The nodes communicate over a strongly connected weight-balanced graph. The corresponding weight matrices W := {w i,j } associated with the network are primitive and doubly stochastic, i.e., W

, where 1 n is a vector of n ones.

Assumption 2 (Smoothness and convexity). Each local g i is ℓ 1 -smooth and each h i is ℓ 2 -smooth, where ℓ 1 , ℓ 2 are arbitrary positive constants. Furthermore, the global G is convex and the global H is µ-strongly convex.

Assumption 3 (Full ranked coupling matrix). The global coupling matrix P := 1 n i P i has full column rank. The above-mentioned assumptions are common in the literature on distributed optimization. Assumption 1 is used to ensure average consensus [14] when the nodes communicate over a network. Assumptions 2 and 3 are necessary for the existence of a unique saddle-point [9] in min-max problems.

ALGORITHM DEVELOPMENT

To motivate the significance of gradient tracking, we first describe a well-known distributed optimization method: distributed gradient descent (DGD) [11]. For a strongly convex cost function G(x) := 1/n n i=1 g i (x), distributed over a network of n nodes, DGD aims to find the unique minimum x * (of G) iteratively by implementing:

However, due to data heterogeneity, there exists a local versus global cost gap, i.e., ∀i, ∥∇g i (x) -∇G(x)∥ ̸ = 0. Therefore, DGD converges to an error ball around x * . To eliminate this error, GT-DGD uses a gradient tracking technique [12,13] which replaces ∇g k r with a gradient tracking term q k i evaluated as follows:

It can be verified that for all i, q k i → ∇G(x). Thus, GT-DGD converges to the unique minimum x * . In this paper, we use a similar gradient tracking technique for both descent and ascent updates. Algorithm 1 formally describes GT-GDA.

Algorithm 1 GT-GDA at each node i Require:

4:

5:

6:

At each node i, the two state vectors x k i and y k i are initialized randomly. For some positive constant step-sizes ³ and ´, GT-GDA iteratively evaluates: (i) P k i , the estimate of global coupling matrix P ; (ii) gradient descent step for x k i updates and the corresponding gradient tracking term q k i ; (iii) gradient ascent step for y k i updates and the corresponding gradient tracking term t k i . It can be verified that for all i, P k i → P , q k i → ∇ x F , and t k i → ∇ y F . Therefore, the state vectors x k i and y k i are updated using the estimates of global partial gradients q k i and t k i respectively, and not the local partial gradients ∇ x f i and ∇ y f i .

MAIN RESULTS AND CONVERGENCE ANALYSIS

Now we describe the main theorem that establishes the convergence properties of GT-GDA.

Theorem 1. Consider P under Assumptions 1, 2, and 3.

For small enough positive step-sizes ³, ´> 0, GT-GDA converges linearly to the unique saddle-point (x * , y * ) of F .

Theorem 1 states that GT-GDA converges to the exact solution (x * , y * ) at a linear rate. To establish this result, we first formulate an LTI system that governs the error dynamics of GT-GDA. Then we show that the errors decay to zero at a linear rate. For evaluating the error quantities, we first define the state vectors x k , q k ∈ R npx and y k , t k ∈ R npy that concatenate the local vectors x k i , q k i and y k i , t k i for all i. Moreover, we define the average vectors and t k := 1 n n i=1 t k i . We now describe the error quantities.

(i) Agreement errors, ∥x k -

This error quantifies the gap between the network's estimate and the agreement (where ¹ denotes the Kronecker product);

(ii) Optimality gaps, ∥x kx * ∥ and ∥y k -∇H * (P x k )∥: This error quantifies the discrepancy between the network average and the optimal solution (x * , y * );

(iii) Gradient tracking error terms, ∥q k -1 n ¹ q k ∥ and ∥t k -1 n ¹ t k ∥: This error quantifies the gap between the gradient tracking estimates and the global gradients.

We now describe Lemma 1 to establish the system dynamics of GT-GDA using these error quantities.

Lemma 1. Consider GT-GDA described in Algorithm 1 under Assumptions 1, 2, and 3. Let s k , e k ∈ R 6 be defined as

and N ³,´∈ R 6×6 be such that it has ³ and ´at the (2, 1) and (1, 5) locations, respectively, and zeros everywhere else. Furthermore, for some positive à M g à m > 0, we define à m f ||| P i ||| f à M for all i. Then ∀k > 0 and some positive step-sizes

, (where Ω > 1) and ´> 0 , the LTI system governing the error dynamics of GT-GDA can be described by the following relation:

where ¿ := 1 n n i=1

is defined as:

, and M ∈ R 6×6 takes the form:

, where '×' are the "don't care" terms (will be clarified later),

We note that Lemma 1 establishes the system dynamics of GT-GDA. The proof is omitted due to space limitations, see [22] for details. Next, we describe a useful lemma that is essential for proving the convergence properties of GT-GDA using matrix perturbation theory for semi-simple eigenvalues.

Lemma 2. [23] Consider a matrix M ´∈ R n×n , of the form M ´:= M 0 + ´M , depends smoothly on a real parameter ´g 0. Assume M 0 has l < n equal eigenvalues,

such that I l ∈ R l×l is an identity matrix. Let ¼ i (´) denote the i-th eigenvalue of M ´, as a function of ´, corresponding to ¼ i , where i ∈ {1, . . . , l}, and the matrix M := dM ´/d´| ´=0 . Then d¼ i /d´| ´=0 is the i-th eigenvalue of the following l × l matrix:

Proof of Theorem 1. Now we analyze the error dynamics of GT-GDA described in Lemma 1 and evaluate the convergence rate. Equation (1) shows the evolution of error with time. If ∥s k ∥ → 0 at a linear rate, it essentially proves that GT-GDA converges to (x * , y * ) linearly. We observe that the second term on the right-hand side of ( 1) converges to 0 6 (a vector of six zeros) exponentially because ¼ ∈ [0, 1) and ¼ k → 0 exponentially. Therefore, it is sufficient to show that the spectral radius Ä(M 0 + ´M ) < 1. By observing the structure of M 0 , it can be verified that the eigenvalues of the matrix are the elements at the main diagonal. Therefore, when ´= 0, the spectral radius Ä(M 0 + ´M ) = 1 (and is governed by the two semi-simple eigenvalues of M 0 ). To understand the perturbation effect of the step-size ´on these repeated eigenvalues, we use the result from Lemma 2. It can be verified that the left eigenvectors corresponding to the two semi-simple eigenvalues of M 0 are u ¦ 1 = [0 1 0 0 0 0] and u ¦ 2 = [0 0 0 0 1 0], and the right eigenvectors are v 1 = u 1 and v 2 = u 2 . Thus, the d¼ 1 /d´| ´=0 and d¼ 2 /d´| ´=0 are the eigenvalues of the following 2×2 matrix:

If both eigenvalues of S matrix are negative, it is sufficient proof to show that both semi-simple eigenvalues become less than 1 with a small change in ´. It can be verified that both diagonal terms of S are negative. Thus, the sum of eigenvalues of S is negative (trace is equal to the sum of eigenvalues). This implies that at least one eigenvalue of S is negative. Next, we observe the determinant of S. If the determinant is positive, then both eigenvalues must possess the same (nega-tive in our case) sign. To establish that, we find a bound on Ω:

When Ω satisfies the above bound, both eigenvalues of S are negative. Thus, the spectral radius Ä(M 0 + ´M ) < 1 and the theorem follows.

NUMERICAL EXPERIMENTS

In this section, we describe some numerical experiments to compare the performance of GT-GDA with D-GDA (a distributed variant of GDA that does not use gradient tracking).

For the generality of results, we consider two types of networks based on the structure and connectivity of nodes: (i) directed exponential graph with n = 16 nodes (see Figure 1, left) and (ii) undirected geometric graph with n = 200 nodes (see Figure 1, right). We consider the saddle-point equivalent of the regression problem such that each node i has access to its private cost:

, where b i ∈ R py is the local vector, P i ∈ R py×px is the local data matrix, R i (x) is the local regularizer, and ¼ R is the regularization constant. The global objective is to evaluate the saddle-point by computing:

In this section, we consider two different regularizers and evaluate the performance by computing the optimality gap, i.e., ∥x kx * ∥ + ∥y ky * ∥ for all k > 0. Smooth and strongly convex regularizer: We first use a smooth and strongly convex regularizer for every node i, i.e., R i (x) = ∥x∥ 2 . It can be verified that the global cost F is strongly convex and strongly concave. Figure 2 shows the performance results of GT-GDA and D-GDA. The left figure shows the evolution of optimality gap when the problem is distributed over a strongly connected directed exponential network of n = 16 nodes. The figure on the right shows the performance when the underlying graph is geometric with n = 200 nodes. For both cases, it can be seen that the optimality gap of D-GDA initially decreases and then stays constant. This steady-state error is caused by the global versus local cost gaps due to heterogeneous data distribution. However, GT-GDA converges to the unique saddle-point using gradient tracking.

CONCLUSION

In this paper, we propose a first-order optimization method that solves distributed saddle-point problem when the global cost can be described as F (x, y) := G(x) + ïy, P xð -H(y). The proposed method GT-GDA uses gradient tracking to deal with the error caused by data heterogeneity and converges to the unique saddle-point (x * , y * ) at a linear rate when F is strongly concave-convex. We develop an LTI system governing the error dynamics of GT-GDA and use matrix perturbation theory for semi-simple eigenvalues to prove the convergence results. Numerical experiments illustrate the performance of GT-GDA and compare it with related work that does not use gradient tracking.