Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes
Authors: Yan Huang
Xiang Li
Yipeng Shen
Niao He
Jinming Xu
Venue: NeurIPS 2024 poster (2024)
Keywords: Minimax Optimization
Distributed Learning
Nonconvex Optimization
Convergence Analysis
Stepsize Inconsistency
Primary area: optimization
TL;DR: This paper proposes a distributed adaptive method for solving nonconvex minimax problems and establishes a near-optimal convergence rate by employing adaptive stepsize tracking to eliminate the inconsistency in locally computed adaptive stepsizes.

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.

Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes
Yan Huang
Xiang Li
College of Control Science and Engineering Zhejiang University, China
Department of Computer Science ETH Zurich, Switzerland xiang li@iin ethz. ch
(aangyya56160ju...om edw..ueeedu.cooo
Yipeng Shen
Niao He
College of Control Science and Engineering Zhejiang University, China (23320748zju.euu edu. cn
Department of Computer Science ETH Zurich, Switzerland niao he@inff.f...... ettz. ch
Jinming Xu
College of Control Science and Engineering Zhejiang University, China j iimyyuuzjju edu cn
Abstract
In this paper, show that applying adaptive methods directly 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 employ an adaptive stepsize tracking protocol involving the transmission of extra (scalar) variables. This protocol ensures the consistency among stepsizes of nodes, eliminating the steady-state error due the lack of coordination stepsizes among nodes that commonly exists in vanilla distributed adaptive methods, and thus guarantees exact convergence. For nonconvex -troongly-sngy----oo -ttrongyy-ooncav conccvv 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 Ó (c (4++)) for any small > O, 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 moblem-dependent parameters for nonconvex minimax problems. Extensive experiments are conducted validate our theoretical results.
Introduction
Distributed optimization has seen significant research progress over the last decade, resulting in numerous algorithms (Nedic and Ozdaglar, 2009; Yuan al., 2016; Lian et al., 2017; and Nedić, 2021). However, the traditional focus of distributed optimization has primarily been on minimization tasks. With the rapid growth machine learning research, various applications have emerged that go beyond simple minimization, such as Generative Adversarial Networks (GANs) (Goodfellow et al., 2014; Guirajani 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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to name a few. These tasks typically involve a minimax structure as follows:
min max f (a, #Ex yey
where X C R", and z, 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 convex- concave objectives (Hsich al., 2021; Daskalakis et al., 2021; Antonakopoulos al., 2021), i.e. the function f(,, 3) is convex for any E y, and (x,-- is concave for any E X.
Adaptive gradient methods, such as AdaGrad (Duchi et al., 201 I), Adam (Kingma and Ba, 2014), and AMSGrad (Reddi et al., 2018), 8), are often integrated with GDA to effectively solve minimax problems with theoretical guarantees in 2021: Ene and Lê Nguyen, 2022). These adaptive methods are capable of adjusting stepsizes based on historical gradient information, making it robust hyper-parameters tuning and 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 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.
settings (Diakonikolas, 2020; Antonakopoulos et al.,
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 al., 2020; Sharma al., 2023). This mainly due 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 result, the following question arises naturally:
"Can we design 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 distributed adaptive method for efficiently solving soooovee-sttonglyyconnee (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 time- scale separation in stepsizes and paraseter-agnostic capability in fully distributed settings.
Theoretically, we prove that D-AdaST is able to achieve a near-optimal convergence rate of Ô (c-(4+)) with arbitrarily small 5 > 0 to find an e-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-indeeendence 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).

---

1.1 Related Works
Distributed nonconvex minimax methods. In the realm of federated learning, Deng and Mahdavi (2021) introduce Local SGDA algorithm combining FedAvg/LLoal SGD with stochastic GDA and show an Ó (e (E=)) sample complexity for NC-SC objective functions. Sharma et al. (2022) provide improved complexity result of Ô (E- matching that of the lower bound of first-order algorithms for both NC-SC and Manconvex-Polyale Soolyakk-oojsiewicz (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 double-loop decentralized SGDA algorithm with gradient tracking techniques (Pu and Nedié, 2021) and achieve Ö (E (c= sample complexity. With a stronger assumption of average smoothness, some studies employ variance reduction techniques to accelerate convergence (Zhang et al., b021b; 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 fixed or uniformly decaying stepsize, requiring the prior knowledge of smoothness and concavity.
(Distributed) adaptive minimax methods. For centralized nonconvex minimax problems, Yang al. (2022b) show that, even deterministic settings, GDA-based methods necessitate the time- scale 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; Bot 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 significant drawback in practical scenarios. To this end, Yang et al. (2022b) introduce nested adaptive algorithm named Ne that achieves parameter-agnoottiism by incorporating an inner loop to effectively maximize the dual variable, which can obtain an optimal sample complexity of Ô (c- 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 adaatiiiat i 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 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 paroseter-agnostic in fully distributed settings.
Throughout this paper, we denote by E [-] the expectation of a random variable, ||-|| the Frobenius norm, (.-)) the inner product of two vectors, 3 the Hadamard product (entry wise), & the Kronecker product. We denote by 1 the all-ones vector, I the identity matrix and J 11 /n the averaging matrix with n dimension. For a vector or matrix A and constant a, we denote A the entry-wise exponential operations. We denote & (x)) == (x.y² (æ)) as the primal function where y" (x) = argmaxf (I. y), and Py (-) as the projection operation onto set y
Notations.
2 Distributed Adaptive Minimax Methods
We consider the distributed minimax problem collaboratively solved by a set of agents over network. The overall objective of the agents is to solve the following finite-sum problem:
min max/ / (sx ZER BEY
Σ BENDD [Te (Z,
: f((.)))
where fi : RP+d - I the local private loss function accessible only by the associated node i E A = 21, nn.. D'e C Rd is closed and convex, and & ~ D; denotes the data sample locally stored at node i V with distribution DD We consider graph G (V, here, V = {1, ..... n) represents the set of agents, and È VV x V denotes the set of edges consisting of ordered pairs (i, j)
3

---

Matirary part
10"
D-Tidd D-NASTT
237
D-llaza D-AcEST
D-GG D-RREST
10:1
2014
301
Ilaratona
(a) trajectory
(b) convergence of .V (ac, x)1l
(c) convergence
Figure Comparison among D-SGDA, D-TiAda and D-AdaST for NC-SC quadratic objective function (6) with πt 2 nodes and Tar = Ty- In (a), it shows the trajectories of primal and dual variables of the algorithms, the points the black dash line stationary points of In (b), shows the convergence of -|V (#%,, y/2] over the iterations. (c), it shows the convergence of the inconsistency of stepsizes, C. defined in (8), over the iterations. Notably, S fails to converge for D-TiAda and 2 for non-adaptive D-SGDA
representing the communication link from node j to node i. For node i, we define N₁ = 1 e E} as the set of its neighboring nodes. Before proceeding to the discussion of distributed algorithms, we first introduce the following notations for brevity:
X
[2 22,
In,
RRXp, Ye [V kn U2,6,
un
R
where Fi.k E RR, Mi.k y denote the primal and dual variable of node each iteration k, and
F (xk. yk: .... VaP (I
Vs. (T,,)
v yx:
V I.
are the corresponding partial stochastic gradients with i.i.d. samples gg SK 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 address the challenge.
2.1 Non-Convergence Direct Extensions
For the distributed minimax optimization problem 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 al., 2020; Yang 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 renowned for its ability to adaptively fulfill the time-scale separation requirements. As result, we arrive at the following Distributed TiAda (D-TiAda) algorithm.
X W (xt
7o VoVV V (xt. yui
(2a)
Yk+1 Py (w (yx 1y 7 k+1 (Xt, Vxi
(2b)
where and Ty are the stepsizes, W is doubly-stochastic weight matrix induced by graph G (Xiao et al., 2006) (c.f., Assumption 4), and
k+1 = diag aa-a 1" (ii++1 ) UiL diag -B " [1,h+1 S==1'
(3)
with 0i max {
) m m my m/ Mitt1 = m. and
m = + P.P. (SAN m = m + V/ (II
are the local accumulated gradient norm. Note that we impose maximum operator in the precon- ditioner Ugk. and employ different stepsize decaying rates, i.c., 0 < 3 < 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 parameters (Li et al., 2023).
However, in the distributed setting, such direct extension may fail to converge to a stationary point because Ui and Ui,A be inconsistent due the difference of local objective functions fi, In particular, we can rewrite the above vanilla distributed optimization algorithm (2) in the sense of average system of primal variables as below,
1s Y
0
k+1 V Yki
Tk+1 TR - V
V
(Ki.
7/2
(5)
nh
adaptive descent
incousistancy
where (8x (zx=)²
By := 1 xx/n and 0g := 1/n Ei= Vi
is evident that, in comparison centralized adaptive methods, an unexpected term (i.e., ox) 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 gap near the stationary points in 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 < B 0.5 < 1 and Ye Tg 0, holds for any t = 0, 1, 2, ...., we have,
V Me) ||=|| V=f(zo, yo) ll, V n:) ||=1| v, 30) ll,
where 2 yo)l and || v (zo, yo'l 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 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 diver- gence of of D-SGDA and D-TiAda even in a simple scenario involving only two connected agents. This phenomenon is illustrated in Figure and the functions are depicted as follows:
fi (Ir,) v)
20 22
5
+ xy
2
(6)
3
fa (x, =
20 2² 5
2ry 2x
is not difficult to verify that the points on the line 3y 5x + 2 are stationary points of f (x. y) 1/2 (fi (I,z) + fz ()). It follows from Figure 1(a) and ((b) that D-SGDA does not converge to a stationary point because the lack of time-scale separation, and D-TiAda also fails to converge due to stepsize inconsistency,
shown in Figure 1(c). In contrast, the utilization of the stepsize tracking protocol in D-AdaST ensures convergence to 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.
2.2 The Proposed D-AdaST Algorithm
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 I, and can be rewritten in a compact form as follows:
mf+1 1 = W (m + h
(7a)
m W (m + h
(7b)
X = W (xx 7a V V. F
(7c)
Yk+1 Py (w (yx 7
(7d)
5

---

Algorithm Distributed Adaptive Minimax Method with Stepsize Tracking (D-AdaST)
Initialization: 2i,0 IR,, 14.0 E Y/, buffers mao m c O, stepsizes Ye: 7o > and weight matrix W. 1: for iteration & = 0, 1, each node i E [n]. do
exponential factors 0 < 3
Ett 2: Sample i.idd F.,x F. (r.,s. Yi.ii Si,k)
and 9h, = y.Fi SE.K
3: Accumulate the gradient norm:
mi,++1 =m + 11 m mi,+1 = m + 1l?
4: Compute the ratio:
0i,++ = (m 1 max {m ( 1m) < 1.
5: Update primal and dual variables locally:
Y= (m²,,+11) -a gi,ki ViAk-1 Yot (y P
21, 2i,k
6: Communicate adaptive stepsizes and decision variables with neighbors:
mf m 1 Mr.++ M.++1
Σ
Wis { (m m. To Mih+1
JEN.
7: Projection of dual variable on the set ): Vi,++1 +- Py (vi,++1).
8: end for
where m [ [... m ....... 17. m = [.... ..... ... 17 denote the tracking variables for the accu- mulated global gradient norm, i.c., for = E {x, y).
.m
1T m
1 " n2 Σ
E |1g. 1|2 =m
i
i=
n
while h [.... ,I, g II2,....''' IT, and VR: Un are diagonal matrices with Ug max (me m and u4k m Note that we also provide a variant of D-AdaST with coordinate-wist adaptive stepsizes in Algorithm 2, along with its convergence analysis in Appendix B.5.
3 Convergence Analysis
In this section, 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 ये 1/n En Wikk, define the following metrics to evaluate the level of inconsistency of stepsizes among nodes, which are ensured to be bounded by Assumption 3.
< =
sup kEjm),s>0 (1xx- -000)
( {
c := sup (E(n).E00
{ {15.6 ==²)²
/
(15
(8)
3.1 Assumptions
We consider the NC-SC setting of Problem (1) with the following assumptions that are commonly used 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 lower complexity bound of Ω (e=)) and proved that such a dependency on e optimal (c.f., Remark 2).
Assumption (u-strong concavity in y). Each objective function Sa (x. y) is j--strongly concave in y. iee. Vo E RRP, Vy. y E y and > 0,
fs (z, 3) - fo (x.1) > (2.v) H
11--
(9)

---

Assumption 2 (Joint smoothness). Each objective function fi (x, V) is L-smooth in x and y, i.e. Vx, R' and Vy. y' E Y, there exists a constant such that for 2 E {z,y).
( - Vafi - v'iIl < L2 (1 z'1l + lly - v/12²)
(10)
Furthermore, fi is second-order Lipschitz continuous for y, i.e., for 20r2= E {x. y).
Vy.. V (2, - (i', ,'''l'''"
< L.2
ly v/ 112)
(11)
Remark 2. Assumption I does not require the convexity in x and the objective function thus can be nonconvex. Assumption I 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). Besides, it can be verified that the constructed 'hard' examples for obtaining the lower complexity bound in Li al. (2021) satisfy the above second-on order Lipschitz continuity (11) on y, implying that the achievable optimal complexity for the function and algorithm class considered in this work is O (E
Assumption 3 (Stochastic gradient). For ii.dd sample Ç,, the stochastic gradient of each i is unbiased, Le., Vx E IR,,y J E V. Eg, FV (2c y: Ei)l = V.fi (I. v). for 2 E {r,y), y), and there is a constant C> O such that Fi (x. E.)1 C.
Remark 3. Assumption 3 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) 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 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 the underlying graph to ensure its connectivity. Assumption 4 (Graph connectivity). The weight matrix W induced by graph G is doubly stochastic, Le., W1 1, 1s and pw == || JJ <1
Note that one can always find a proper weight matrix W compliant to the graph that satisfies Assumption 4 once the underlying graph undirected and connected. For instance, the weight matrix can be easily determined based on the Metropolis-HHe Hastinss protocol (Xiao et al., 2006). Moreover, this assumption is more general than that in Lian al. (2017); Borodich 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).
3.2 Main Results
We are now ready to present the key convergence results in terms of the primal function & (x) = (x, 3² (z)) with y" (x) argmax (x, y). whose proof' can be found in Appendix B.4.
yEy
Theorem 2. Suppose Assumption 1-4 hold. Let 0 < < < 1 and the total iteration K satisfy
max
22
a-3
Ω
max
(12)
(1 )?- p
with = L/p p ensure time-scale separation and quasi--ndependence of the network. For D-AdaST, we have
K E
10
(T)))
(x(t Kl-a (1- (_ Ka
+
1
1
K1-B (1- pw) 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 (e (4+0)) sample complexity for arbitrarily small 8 0, e.g., letting
'The complete convergence result be found in (75) in Appendix.
7

---

a a (8 26) and 8 28). It is worth noting that this rate is near-optimal compared to the existing lower bound of f2 (c-) (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 pw= = O, 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-agnostc method that achieves a convergence rate of Ö (E-), even in a centralized setting.
Remark 5 (Paraseter-agnostic property and transient times). The above results show that D-AdaST converges without requiring to know any the initial stepsize "ix and "yy. and is thus parameter-agnostic. Moreover, we explicitly characterize the transient times (c.f.. Eq. (12)) that ensure time-scale separation and mhasi--nneeenddece of the network, respectively. Indeed, we see that if and (3 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 3 are relatively large, then Ô (1/K) K + 1/K1--) 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.
deeledeedp parameters, i.e, L, I and pw. or tuning
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 have
K-
E
V
[P]
=
1
Ki-a
(1 (--w)) Ka
k=
(14)
+
+
1
+Ō + 09)
K1-3 (1- pw) KB
4 Experiments
In 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), 1), 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 heteroge- neous 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 al., 2017). For the exponential factors of stepsize,
set 0.6 and 3 = 0.4 for both D-TiAda and D-AdaST. More detailed settings and additional experiments with different initial stepsizes, data distributions and choices of a 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 50 (pw 0.71) and 100 (pw 0.75).
12 x² - 2L, + L,y,
As (z, v) = - + L,zy
(15)
where L; 21 (1.5, The local gradient of each node is computed with an additive A (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 7 = 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 min max 1/n E Sa (æ; & + y) 7) |l
y
where x denotes the parameters of the model, y denotes the perturbation and & denotes the data sample of node i. Note that if 77 is large enough, the problem is NC-SC. We conduct experiments on
8

---

1.2
044
12
(a) 7/- 0.1, n 50
(b) 7x 0.02, n
(c) 7v-
0.1, n
100
(d) 7/- 0.02, 100
Figure 2: Performance comparison of algorithms quadratic functions over exponential graphs with node counts n = (50, 100} and different initial stepsizes (%v = 0.1).
Grad and cata
Grad and cala
dinddeetcco cal
Gradertcals
(a) ring, PW 0.97
(b) exp., PW 0.67
(c) dense, Pw 0.55
(d) scalability
piicle Saar
Toke
Jul Wap
2030 500 2000 wid
1000
2030
2010
1000
200
1000 1000
(e) ring, PW 0.97
(f) exp-, PW = 0.67
(g) dense, PW 0.55
(h) scalability
Figure 3: Comparison of the algorithms on training robust CNN on MNIST dataset. The first row shows the results of AdaGrad like stepsize, and the second row is for Adam-like stepsize. For the first three columns, we compare the algorithms on different graphs with n = 20. For the last column, show the scalability of D-AdaST in terms of number of nodes. Initial stepsizes Yrr = 0.01, 7/ = 0.1 for AdaGraad stepsize, and 7/ = 0.1, Tv 0.1 for Adam-like stepsize.
as
MNIST dataset over different networks, e.g., ring graph, exponential (exp.) graph (Ying et al., 2021) and dense graph with n1/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 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., PW), demonstrating the inddiiindeeeedecce 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 plots (d) and (h), we further demonstrate that D-AdaST can scale efficiently with respect to the number of nodes, while keeping constant batch-size of 64 for each node. This showcases the algorithm's 's ability to handle large-scale distributed scenarios effectively.
and Ba, 2014).
Generative Adversarial Networks. We further illustrate the effectiveness of D-AdaST on another popular task of training GANs, which has generator and 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 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 observed from the figure that D-AdaST achieves higher inception scores in three cases with different initial stepsizes, and has small score loss as the initial step size changes. We believe that this example shows the great potential of D-AdSST in solving real-world problems.

---

1.5
Ircoptin Score
25
D7 ATTAce-Mda
25-
15
G-Iida--zan
D-4c55/4cam
CuASaSTASam
Granlene cals
".Gnddlent cale
722 7/ 0.001
1/2
0.01
7/2 Vv 0.05
Figure 4: Training GANs on CIFAR-10 dataset over exponential graphs with n 10 nodes.
Conclusion
We introduced new distributed adaptive minimax method, D-AdaST, designed tackle the issue of non-convergence in smmconvee-ttrongly-coneee
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 convergeene. 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 opttmml convergence rate Ô (c-(4+)) with any arbitrarily small 5 0. Extensive experiments on both real-world and synthetic datasets have been conducted to validate our theoretical findings across various scenarios.
Acknowledgments
The work of Huang, Shen and Xu has been supported by the National Key R&D Program of China under Grant No. 1022YFB3102100 and in parts by National Natural Science Foundation China under Grants 62373323, 62088101. The work of Li and He has been supported by the ETH research grant and Swiss National Science Foundation (SNSF) Starting Grant.
References
Antonakopoulos, K., Belmega, E., and Mertikopoulos, (2021). Adaptive extra sutta-gradient methods for min-max optimization and games. In ICLR 2021-9th International Conference on Learning Representations, pages 1-28.
Borodich, E., Beznosikov, A., Sadiev, A., Sushko, V., Savelyev, N., Takáč, M., and Gasnikov. A. (2021). Decentralized personalized federated min-mar max problems. arXiv preprint arXiv:2106.07289
Bot, R. I. and Böhm, A. (2023). Alternating proxiaa-ggradint steps for (stochastic) nonconvex- concave minimax problems. SIAM Journal on Optimization, 33(3):1884-1913
Chen, C., Shen, L., Liu, W., and Luo, Z.-Q. (2023a). Efficient-adam Communication-efinn distributed adam. IEEE Transactions on Signal Processing.
Chen, L.. Ye, H., and Luo, L. (2022). A simple and efficient stochastic algorithm for decentralized nonconvex manconvex-stronglyyee strongly-concuve minimax optimization. arXiv preprint arXiv:2212.02887.
Chen, L., Ye, H., and Luo, (2024). An efficient stochastic algorithm for decentralized nonconvex- strongly-concave minimax optimization. In International Conference on Artificial Intelligence and Statistics, pages 1990-1998. PMLR.
Chen, T., Sun, Y., and Yin, (2021). Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 24:25794-25307.
Chen, X., Karimi, B., Zhao, W., and Li, (2023b). On the convergence of decentralized adaptive gradient methods. In Asian Conference Machine Learning, pages 217-232. PMLR.
10

---

Daskalakis, C., Skoulakis, S., and Zampetakis, M. (2021). The complexity of constrained min- max optimization. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1466-1478.
Dem' yanov, V. F. and Pevnyi, A. B. (1972). Numerical methods for finding saddle points. USSR Computational Mathematics and Mathematical Physics, 12(5):11-52.
Dem'yanov,
Deng, and Mahdavi, M. (2021). Local stochastic gradient descent ascent: Convergence analysis and communication efficiency. In International Conference on Artificial Intelligence and Statistics, pages 1387-1395. PMLR.
Diakonikolas, J. (2020). Halpern iteration for near-optimal and parameter- free monotone inclusion and strong solutions to variational inequalities. In Conference on Learning Theory, pages 1428- 1451. PMLR.
Dinh, L.,, Pascanu, R., Bengio. S., and Bengio, Y. (2017). Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028. PMLR.
Duchi, J., Hazan, E., and Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7).
Ene, A. and Lê Nguyen, H. (2022). Adaptive and universal algorithms for variational inequalities with optimal convergence. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6559-6567.
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. (2014). Generative adversarial nets. Advances in neural information processing
systems, 27.
Gulrajani, I., Ahmed, F., Arjovskyy, M.., Dumoulin, V., and Courville, A. C. (2017). Improved training of wasserstein gans. Advances in neural information processing systems, 30.
Guo, Z.,, Xu, Y., Yin, W., Jin, R., and Yang, T. (2021). A novel convergence analysis for algorithms of the adam family, arXiv preprint arXiv:2112.03459,
Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., and Hochreiter, S. (2017). Gans trained by two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30.
Hsieh, Y.P.., Mertikopoulos, P., and Cevher, V. (2021). The limits of min-max optimization algorithms: Convergence to spurious non-critical sets. International Conference on Machine Learning. pages 4337-4348. PMLR.
Huang, F., Wang, X., Li, J., and Chen, S. (2024). Adaptive federated minimax optimization with lower complexities. In International Conference on Artificial Intelligence and Statistics, pages 4663-4671. PMLR.
Huang, F., Wu, X., and Hu, Z. (2023). Adagda: Faster adaptive gradient descent ascent methods for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pages 2365-2389, PMLR.
Huang, F., Wu, X., and Huang, H. (2021). Efficient mirror descent ascent methods for nonsmooth minimax problems. Advances in Neural Information Processing Systems, 34: 144311111,
Huang, Y., Sun, Y., Zhu, Z., Yan, C., and Xu, J. (2022). Tackling data heterogeneity: A new unified framework for decentralized SGD with sample-induced topology. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 9310-9345. PMLR.
Ju. L., Zhang, T., Toor, S., and Hellander, A. (2023). Accelerating fair federated learning: Adaptive federated adam. arXiv preprint arXiv:2301.0933.
Kavis, A., Levy, Y., and Cevher, V. (2022). High probability bounds for a class of nonconvex algorithms with adagrad stepsize. In International Conference Learning Representations.

---

Kingma, D. P. and Ba, J. (2014), Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980.
Li, H., Farnia, F., Das, S., and Jadbabaie, A. (2022). On convergence of gradient descent ascent:
A tight local analysis. In International Conference on Machine Learning, pages 12717-12740. PMLR.
Li, H., Tian, Y. Zhang, J., and Jadbabaic, A. (2021). Complexity lower bounds for nonconvex- strongly-concave min-max optimization. Advances in Neural Information Processing Systems, 34:1792-1804.
Li, x., YANG, J., and Hc, N. (2023). Tiada: A time-scale adaptive algorithm for nonconvex minimax optimization. In The Eleventh International Conference on Learning Representations.
Lian, X., Zhang, C., Zhang, H., Hsich, C.-J., Zhang, W., and Liu, J. (2017). Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30.
Liggett, B. (2022). Distributed learning with automated stepsizes.
Lin, T., Jin, C., and Jordan, M. (2020). On gradient descent ascent for nonconvex-coneave minimax problems, In International Conference on Machine Learming, pages 6083-6093, PMLR.
Liu, M.. Zhang, W. Mroueh, Y., Cui, X., Ross, J., Yang, T., and Das, P. (2020). A decentralized parallel algorithm for training generative adversarial nets. Advances in Neural Information Processing Systems, 33: 13:11056-1107.
Madras, D., Creager, E., Pitassi, T., and Zemel, R. (2018). Learning adversarially fair and transferable representations. International Conference on Machine Learning, pages 3384-3393. PMLR.
Mohri, M., Sivek, G., and Suresh, A. T. (2019). Agnostic federated learning. International Conference on Machine Learning, pages 4615 4625. PMLR.
Nedic, A. and Ozdaglar, A. (2009). Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48-61.
Nedie, A., Ozdaglar, A., and Parrilo, A. (2010). Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 55(4):922-938.
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. (2009). Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574-166)
Pu. S. and Nedić, A. (2021). Distributed stochastic gradient tracking methods. Mathematical Programmiing, 187(1):409-444 457.
Reddi, J., Kale, S., and Kumar, S. (2018). On the convergence of adam and beyond. In International Conference on Learning Representations.
Sharma, P., Panda, R., and Joshi, G. (2023). Federated minimax optimization with client heterogeneity. arXiv preprini arXiv:2302.044: 04249..
Sharma, P., Panda, R., Joshi, G., and Varshney, P. (2022). Federated minimax optimization: Improved
convergence analyses and algorithms. In International Conference on Machine Learning, pages 19683-19730. PMLR.
Sinha, A., Namkoong, H., Volpi, R., and Duchi, J. (2017). Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv:1710. 10571.
Tarzanagh, D. A., Li, M., Thrampoulidis, C., and Oymak, S. (2022). Fednest; Federated bilevel, minimax, and compositional optimization. In International Conference on Machine Learning, pages 21 2114-11112 179.. PMLR.
Tsaknakis, I., Hong, M., and Liu, S. (2020). Decentralized min-max optimization: Formulations, algorithms and applications in network poisoning attack. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pages 5755-5759. IEEE.
12

---

Wang, J., Liu, Q., Liang, H., Joshi, G., and Poor. H. V. (2020). Tackling the objective inconsisteney problem in heterogeneous federated optimization. Advances in neural information processing systems, 33:761 1-7623.
Wang. J. Zhang. T., Liu, S., Chen, P.Y., Xu, J., Fardad, M., and Li, B. (2021). Adversarial attack generation empowered by min-max optimization. Advances in Neural Information Processing Systems, 111160020-6033.
Wu, X., Sun, J., Hu, Z.,, Zhang, A., and Huang, H. (2023). Solving class of non-convex minimax optimization in federated learning. In Thirty-seventh Conference on Neural Information Processing Systems.
Xian, W., Huang, F., Zhang, Y., and Huang, H. (2021). faster decentralized algorithm for nonconvex minimax problems. Advances in Neural Information Processing Systems, 34:25865-
Xiao, L., Boyd, S., and Lall, S. (2006). Distributed average consensus with time-varying metropolis weights. Automatica, 1:1-4.
Yang. H., Liu, Z., Zhang, X., and Liu. J. (2022a). Sagda: Achieving (
communication complexity in federated min-max learning, In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D.. Cho, K., and Oh, A., editors, Advances in Neural Information Processing Systems, volume 35, pages 7142-7154. Curran Associates, Inc.
Yang, J., Li, X., and He, N. (2022b). Nest your adaptive algorithm for parameter-agnostic nonconvex minimax optimization, In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K., editors, Advances in Neural Information Processing Systems.
Yang. J. Orvieto, A., Lucchi, A., and He, N. (2022c). Faster single-loop algorithms for minimax optimization without strong concavity. In International Conference on Artificial Intelligence and Statistics, pages 5485-5517. PMLR.
Ying, B., Yuan, K., Chen, Y., Hu, H., Pan, P., and Yin, W. (2021). Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Processing Systems, 34:13975 1111977797777...
Yuan, K., Ling, Q., and Yin, W. (2016). On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-1855
Zhang, S., Choudhury, S., Stich, S. U., and Loizou, N. (2023). Communication--fficceen gradient descent-accent methods for distributed variational inequalities: Unified analysis and local updates. arXiv preprint arXiv:2306.05// 1000
Zhang, S., Yang, J., Guzmán, C.,, Kiyavash, N., and He, N. (2021a). The complexity of nonconvex- strongly-concave minimax optimization. In Uncertainty in Artificial Intelligence, pages 482-492 PMLR.
Zhang, X., Liu, Z., Liu, J., Zhu, Z., and Lu, S. (2021b). Taming communication and sample complexities in decentralized policy evaluation for cooperative multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 34: 1811888211888.
Zhang, X., -all,, G., Aybat, N. S., and Xu, Y. (2024). Jointly improving the sample and communication complexities in decentralized stochastic minimax optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20865-20873.
Zhou, D., Chen, J., Cao, Y., Tang, Y., Yang, Z., and Gu, Q. (2018). On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv: 1808. 05671.
Zou, F., Shen, L., Jie, Z., Zhang, W., and Liu, W. (2019). sufficient condition for convergences of adam and rmsprop. In Proceedings of the IEEE/CVF Conference computer vision and pattern recognition, pages 1 111 111-51
13

---

A Additional Experiments
In this section, we provide detailed experimental settings and perform additional experiments on the task of training robust neural networks with different choices of typer-parameters All experiments are deployed a server with Intel Xeon E5-2680 v4 CPU @ 2.40GHZ and Nvidia RTX 3090 GPUs, and implemented using distributed communication package torch. drrrchdistrbbuted 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-wiss adaptive stepsize rule commonly used in existing centralized adaptive methods (Yang et al., 2022b; Li et al., 2023). Morcover, since we attempt to develop a parameter-agnon in tuning nyper-parameters,
algorithm that does not need much effort 0.6 and / 0.4 for all tasks in the main text, and evaluate the effect of the choices of a and 3 on the performance of D-AdaST individually in an additional experiment the synthetic objective function as shown in Appendix A.4.
A.1 Experimental details
Communication topology. For the experiments in the main text, we utilize three commonly used communication topologies: indirect ring, exponential graph and dense graph. An indirect ring is sparse graph in which each node is sequentially connected to form a ring, with only two neighbors per node. Exponential graph (Ying et al., 2021) is a directed graph where each node is connected to nodes at distances of 2 ,2 .... 2 Exponential graphs achieve a good balance between the degree and connectivity of the graph. A dense graph is an indirect graph where each node is connected to nodes at distances of 1, 2, ...., n. We also consider directed ring and fully connected graphs, which are more sparsely and densely connected, respectively, in the additional experiments.
Robust training of neural network. In this task, we train CNNs with three convolutional layers and one fully connected layer 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 31 = 0.9, 32 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 10 dataset, where the model used for discriminator is a four layer CNNs, and for generator is 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 31 0.5, 0.9. To obtain the inception score, we use 8000 artificially generated samples to feed the previously trained inception network.
A.2 Additional experiments on robust training of neural network.
In this part, we conduct additional experiments on robust training of CNNs on MNIST dataset considering variety of settings. We compare the convergence performance of D-AdaST with D-AdaGrad, D-TiAda and D-NeAda using adaptive stepsizes of AdaGirad and Adam. Unless otherwise specified, the total batch-size as Ya- 0.01, 7y = 0.1 for AdaGrad-like algorithms, and 7x Tv = 0.1 for Adam-like algorithms. Specificallyy, we consider two extra graphs that are more sparse and more dense, respectively in Figure 5, e.g., directed ring and fulle-comnected (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 Figure 8. Under all settings, the proposed D-AdaST outperforms the others, demonstrating the superiority of D-AdaST.
1280; the initial stepsizes for and y are assigned
A.3 Additional experiments on training GANs
We provide additional experiments of training GANs on a more complicated dataset CIFAR- 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 in
14

---

D. No
(a) directed-ring
(b)
(c) directed-ring
(d)
Figure 5: Performance comparison of training CNN MNIST with 20 nodes over directed
ring and fully connected graphs
304
(Ttute mi
(a) 0.01, 0.01
(b) 0.001, 0.01
(c) 0.01, 0.01
(d) 0.01, 0.1
Figure 6: Performance comparison of training CNN MNIST with 20 nodes with different
initial stepsizes Yo and 7v.
50
(a) exp.
(b) dense
(c) exp.
(d) dense
Figure 7: Performance comparison of training CNN on MNIST with nodes over exponential
and dense graphs where each node has 4 sample classes.
Auam Inquodten
Ooodeet
Guakent calss
(a) exp.
(b) dense
(c) exp.
(d) dense
Figure 8: Performance comparison of training CNN on MNIST with a = nodes over exponential
and dense graphs.
Figure 4 (a), it can be observed that D-AdaST outperforms the others in terms of the inception score. Together with other experimental results 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.
15

---

5.0
4.5
4.0
Inception
3.5
3.0
D-Adam
D-TiAda-Adam
D-AdaST-Adam
7500
15000
22500
30000
Gradient calls
Figure 9: Performance comparison of D-AdaST with D-Adam and D-TiAda adopting Adam-like stepsizes for training GANs on CIFAR- 100 with coarse labels over the exponential graph consisting of 10 nodes under initial stepsizes " Ty 0.001.
100
80
|[V, ylll2
60
D-AdiTT: 0.6. 0
D-AdaTT: 0- 9-
AddST: 040.4,
40
AdaST: 2- 0.34
20
2000
4000
6000
Gradient calls
Figure 10: Performance comparison of D-AdaST on quadratic functions over an exponential graph of 50 nodes with different choices of and B.
A.4 Additional experiments with different choices of a and 3
In this part, we evaluate the effect of the choices of a and / on the performance of D-AdaST. In particular, we provide an additional experimental result on the synthetic quadratic objective functions (15) with larger ratio of initial stepsizes, i.c., Ye/?, slower maximization processes the beginning). As shown in Figure 10, can be observed that the transient time (iteration before the inflection point) becomes longer as a - 3 decreases, while the convergence rate relatively faster, which is consistent with Theorem and the result in the centralized TiAda algorithm (c.f., Figure 5, Li et al., 2023).
20 (indicating faster minimization and
B Proof of the main results
We recall here some definitions used in the main text. The averaged variables and the inconsistency defined as follows:
T
(ū, =
Zg.
=
Xk.
Up ==
Ug
=
1
1- T
0k
Yk:
ūs :=
Ui.ks
ūg
Ug
T
n
16

---

The inconsistency of stepsizes of the primal and dual variables is defined as follows:
( - 2/ ) (of ( C.
{ / sc(n),E50
(1 ux 9) /
2 sup (E(n),A>0
sup
"k
Proof Sketch. The convergence analysis of the main results in Theorem 2 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 telescoped descent lemma from 0 to K - 1 iterations in Lemma 3, which is upper bounded by the following key error terms:
S .k k= E #
F (Xi, Yu: Ex) The asymptotically decaying terms by
adopting adaptive stepsize;
S2 nK
E
E
||x
17x lyy: 10
The consensus error of and y be-
tween the distributed system and the average system;
S3 == K
Σ
K-1 k=
E
[f
y² (3x)) - f (Øx, ]: The optimality gap in dual variable y; (Tx.
S1 = K
Σ
Σ k=
E
V YAk DO
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 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.
B.1 Supporting lemmas
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 { be a sequence of non-negative real numbers, Zo > 0 and a E (0, 1). Then we have,
T-1 Σ
1-a
T-1
T
1-a
Σ Dt
Ft
(16)
1 1 a
k=
When 0, we have
Σ1= Dt
Tt
< 1 + log
(17)
Ei
xx)
To
Lemma 2. Suppose Assumption 1 and 2 hold. Define $ (x) == I (2r, 3² (x:) as the envelope function and 1² (x) argmax I (I. Then, we have, vEY
T (-) is smoshh with La = L K),, and V (x) = Vaf (x.v" (x)) (cff. Lemma 4.3 in Lin et al. (2020));
"²* (-) is k-Lipschitz and L-smooth with K (1 + x) (c,f, Lemma 2 in Chen et al. (2021)).
B.2 Key Lemmas
In this subsection, we give the key lemmas to help the analysis of the main results. For simplicity. we define A : ||x; - 1,2 122 + Ilyx Then, have the following lemmas.
1/ the consensus error for primal and dual variables.
17

---

Lemma (Descent lemma), Suppose Assumption 1-4 hold. Then, we have
K-1
V&
[T
k=0
802a
(Tmaxx
4
E
V
(Tx.
Tall-a
K
k==0
K
81? 1 K-1
+ 8% 1.0 (1
(2)
E
X yki =2
Σ
TR. [Ax)
nk
nk
S
S2
K-1
T
(ktl
+ 8k
[s (Tk, V (Tx)) - f (Tx. mc)) +
F (XL.
yai
K
k=0
k+1
S3
S4
(18)
where K. p/ is the condition number of the function in y, gmax max 1 (x),
min (z).
Proof. By the smoothness of & given in Lemma 2, i.e.,
(ãx+1) + (Ix) < ( (5x) Jz41 Ix) + Li |8++1 =x11?
and noticing that the scalar Ük, (A are random variables, we have
① (Ix+1) $ (Tx)
E
U00
1
)| -E (1D ( (offg)
< E
V (Tx),
F Fxi.
V
no
Y/ La
1 +
(off1)
+
E
V F (XI.
2
U
(19)
where we have used the definition of ēet1 presented in (5). Then, we bound the inner-product terms on the RHS. Firstly,
1 F.
④ (Tx)
(x Ysi (x)
7
TT
1 V.F
17
V
(Ix)
F (xk yk)
(1kk, 17k)
V,F (1#k, FfF(1 18h)
TT
1
E
V
)1
+E
V.F F yk)
V (1āk. 18x)
(20)
E
(Ix)
Vaf (Zx. Tk. 313
-E
V (1+) - E || V (8x. 32 1²)
1
B
(x))
[9]
1
E|4
I
E
[1 - V" (=+))²
|iv (#x, (fx. 03)1
n
wherein the last inequality we have used the smoothness of the objective functions. Then, for the second inner-product (19), using Young's 's incquality we get
(X Yki (X) } V
k++
E
V
no
(21)
(I+)
+ 2E
V.F (x YKIEE)
n0
18

---

Then, for the last term on the RHS of (18), recalling the definition of stepsize inconsisteney in (8), we have
7/ Iap
E
pk+1
17
A+1
V (xk. VAI
uk+1
a
n
(22)
Ya Lo (1 + (
E
V
F (X): ya: E2)1"]
'k+1
Plugging the obtained inequalities into (18) and telescoping the terms, get
| [=)
K-
②b (3x) (Tx+1)
K
E
4
E
V (Tx.
Bwll
Vn
k=0
k=
K-1
8L
41,2
Σ
E
11
57 113
E
[A
(23)
n
k=0
k=0
8 L
(1
(2)
K
I
(X
yoi
n
K-1
(
+ 16
V
F
(x.,
(xk.
x+1
Now it remains to bound the first term on the RHS of the above inequality. With the help of Assumption 3, we have
K
S (Tk) T (TR+1)
E
7/ N+t1
K
(ix)
1 (Tx+1)
1
+ $ (Tk)
Yo
Ya 0
No0
k=0
4 max
K-1
(24)
E
max
U0
Vn-
Ux
k= 0
① max
Φ*) )
1F.
[Tg]]
7'2
④ max
(6) (KC2)
Noticing that IE |1 3" (Ex)1p]
< 2E (f y (2x))
f (Ix, Tx)], we thus complete the proof.
Next, we need bound the last four terms S₁-S, in (18) respectively. For S₁, we have the asymptotic convergence for both primal and dual variables in the following lemma.
Lemma 4. Suppose Assumption 1-4 hold. Then, we have
K-1
C2-2a
E
V F (XL, yu:
< a) Ko:
(25)
nk
k=0
and
2
E
B
(x:.
<
(26)
n
1+1
(1 - 3) KB
k=0
19

---

Proof. With the help of Lemma and Assumption 3, taking the primal variable x as an example. and noticing that vi,0
> 0, i [n], we have
F X Yai 12
K
K
n
V Fs
Mi Si,k
K
71
hht
)r
V Fi
Ti,k Ti S7,KK
K
n
Σi=
Σド= V2F, (2 Vy.1 (3o1
0=
2
V (F..
(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₂ in the following lemma.
Lemma 5. Suppose Assumption I hold. Then, we have
K
21 Ao]
E [Ax]
& (1 pw) K
K
k=
8npw?? (1+
22-4a
1+ log UK log U1
(1-Pw)²
(1 20x) K2a Ja<1/2
KoZa-1
a22/2
(27)
S (1 (.)
C2-48
1 1 log log 21
1<112 +
1211/2
(1- >?
23) K25
Kuj 28-1
where I(] E {0, 1) is the indicator for specific condition, and the initial consensus error Au can be set to O with proper initialization.
Proof. By the updating rule of the primal variable, we have
E2
||x+1 1x++ 1 112]
E W (xx - Ti Vii
Xba YxiEE)) - (xx - 7o V V (x Yki (1))
+ pw E [|xx - 18 [1]
2 + pw) pW
(28)
+
|V
(x yoj (
- pw
2 (1 pw) pw E
||| (V
v yo
(x)
PW
where we have used Young's 's inequality. Then, by the definition Co (8), we have
E [[I(VE - 3545)) V (XL. vA: < 2E
2a V
Fx
vx:
(29)
k+1
and thus
E
x
18x+11?
0==0
(30)
2 E
|xx6
16
8r2pw (1 + (2)
K-1
I yx:
0 k+l
PW
(1 (1- )
k=0
20

---

Then, we bound the last term on the RHS of the above inequality by Lemma 4. For the case a < 1/2. by Assumption we have
K-1
E
20
V
(x).
E1)
(31)
K-1 n
V Pr
Ki Mi,Ri Si.k
(KC2) 1-20 (1 - -2xx
E
2a
k+1
For the case a > 1/2, with the help of Lemma 1, we have
K 1
E
U k++
V
[k Vk: EE)1
0=
(32)
K
Vork Fi
Di yo.ks ST.R
11 (1 + log eT
log 0
E
pp--1
Uk+1 Uk+1
0=
1=1
For the dual variable, have
yk+1 = Py (W (yx + toU V.F Fo
= -wyx + 7o V.G
where
V
1
Py W yk + To (x.c
(Xk. Yu: yx: Wys)
7
Then, using Young's s inequality with parameter A, we have
E ||ya+1 18 11
= E Wyr 7o V.G (Wy((WW ty V
(1 + A) pw-F [18x= Jy
1
||>>> (w (yx + 7 T (xL. yx: Wyx 19)
1 +
E
+
PW
E
Ily Jy
2
1 + PW
||/33 (w (yx + 70 (x,, yai v2: - Wyrl|"
E.
1 PW
Noticing that Wyx = Py (Wy+) holds for convex set V, we get
E
[|y+4
18x+ 113]
+ Pw
E
[ly 1y
1 + PW
(1|/3) (W (yA + +7 V (xx, Yo: (2)
Py (Wix))) 27
E
-Py
1 PW
+ PW
E
[1yx 1y
+
1 PW E
|
U k+1
V
(XL. vni 11]
1 pw
+ 4 (1 + (22
+ PW
[ly: Jy [1]
U
(x
Nki 52)1
(1 PPW)
21

---

where we have used the non von-expansiveness of projection operator. Then, we have
K
15k 12]
E
k=0
2
|lyo Jyoll
87 + 2.)
Σ
E
Uu++
29 I F (Xa, Yas (1) 42
pw
(1 pw)
Similar to the primal variable, we can bound the last term above, which completes the proof.
Next, we need bound the term 53 i.e., the optimality gap dual variable. The intuition of the proof relies on the adaptive two time-scale protocol, that is, for given and 3, we try to find the threshold of the iterations ko, 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 constant G such that ūy < G hold for = 0, 1, ... Ko 1, then the analysis divided into two phases.
Lemma 6 (First phase). Suppose Assumption 1-4 hold. uf & G, k ... ko 1, then we have
No
E lf (Ik. y" (3x)) - f (3k, [kh]
kp
E [1, + 22.2 (1 + (.2) G ko- -1
20
V (Xx, yk: E2 11
k=0
k=
(33)
7v
(1 +
E
uk+
3
VV
(Xx.
Ex:
4xL
E
||xxe
1xx1
n
k=0
yui + |]]
kn
+
E
U 1
V
F
(xx.
E
186 11 1ly
11
k+
B
k=0
where
1- u 9
Ily--1 1y" (Tx+ 1) )1?
E1, =
Il ly" (Tx)ll
(34)
2ny U2 41
2 po u V/ u0
Proof. Using Young's inequality with parameter Ae. we get
yy441 17" (#x+ 1]1?
(35)
(1 11+N8 Ax) lyK+1 1y" (2x))1++ + (1 1
1 11 (Ix) - v² 11
N
n
Recalling that Yk+1 = Py: (
Yy Yo Uou V Jk: (2)) we further define
8 = W (ys + V Fxx. yx:
Then, for the first term the RHS of (35), by the non-expansiveness property of projection operator Py(-) (c.f., Lemma in (Nedic et al., 2010)), we have
[yk+1 1y" (+x))l
1 ||8241 1y" (#x)
1 yyk41 11+1l
1
7/
Uut V (x+. yk: 2
Ilyx - 1y" (2x) +
n
n (70 T 1o Vi.k - '/' (σt) Σ (70 (1i - uTf1)) De D6, -0" (Fx)),
(36)
22

---

wherein the last incquality we have used the fact [W 1. Then, multiplying by 1/ (10 ) both sides of (35) we get
on
1
Iy4+1 ly" (#x)ll²
k+1
1 1 +
11 (Ix) - JJ' (ix+1)ll
A u++1
9
+11+ Xx)
llys 1y" (Ix)ll Tv
| V vuP (xt (xe (2)
3w:
myyu++1
n
88 Wi,b+1
xx++
-(1+ Xx)
Σ
2
Oi Yi.k y2 (fx)
gh Yo.k
y (3x))
Uk+1
i=1
(37)
For the inner-product terms on the RHS, taking expectation on both sides, we have
E 2 g Vi.k -² (
n
B 1--2 2 V ff (Tk, Uik), (+x))
E (V o (I., Vyfe (Tx Mi,k) Mi 38 (2x))l
E (ff (Ex) (3x, 1llba 1² (ix)
(38)
VyJi (ZiR, - v.Ji (Tx, BiA 1 Iluna 50' (EW))I
E
1=1
2 (ʃ (Tx. 1/" (mx)) (Tx, 0k))
Σ
E 2 (Tx. (x) - Sa (Txx v6,k))
f=1
8xL
|00. 2x|l3]
7p
E
[lvi 3² (3x))²
11
8n
where we have used Young's inequality and strong-concavity of fi, and
9
R Vi.k - -y" (3Te) )
1
U
Uj,k+1 U
E
2
Y1
ik+1
B
(39)
9
8
Ug
Ux+t
11 8 Ilva, y² (mwe)l
0x++1
For the consensus error of dual variable on the objective function, using strong-concavity of and Jensen's 's inequality, we have
2f (Zx, fs (3x. v..))
:=1
(V yf (Tx, F2). V1. - Øk)
Ily
17x 21
(40)
i=1
n
1
20
Tell < 20
Ily: 19x 11
71
n
23

---

Letting A = # we get
E [ (Tx, 1J' (Tx)) (Ex+ (#x.
1 3p7y ukt1/
yy ly" (Tx+1) 11
E
lly: -yy" (fxe)l
21y"x= 11
2 + uy
Yo ux 9
(1 + 2
G
E
2a UR+1
V V (xx. yui =23112]
(41)
(1 + (
E
(xk. yai Ex))
+ n
4x= E3
||xs
15k
|
4
U b++1
1 V n
E
(xk,
(xk,
CIE
lly: 18
B
nu
k+1
By the x-smoothness of y², we have
1y" (#x+1) y² (ix)
x²
| Tx ?
1
Ü (im+i)) T
2
x²
Uktt k+1 Val Yki -
V
(xt. yki
(42)
2-2 x²
2 (1
(
2a
Telescoping the obtained terms from 0 to kg - 1 and noticing that ūn < G for & ko - we complete the proof.
For the second phase, i.e., ko. we have the following lemma.
Lemma (Second phase). Suppose Assumption 1-4 hold. If ūg & G. 0,1, ko then we have
K
E (Ze,y (fx) - S (fx:
k=
E [E + 822x2 (1 + (
| (Te, 02)l
222 22a-5 28
k=kn
k=ko
822 1 (1 (
4kiL
K-1
+
+
E
muur 22a2 2B
kimoo
(43)
79 (1 + (
K-1
8
V Yni
E
lly: - 186
n
n
At Ao Ro
2 (1 22)
272 (1 + (2) 02
17 #++1
22
E
|
F (xxr Yas 11
17001
2a-8
n
47 (1 + C.) 0
8
K
u
y
(x
NEi +2)
nox
k==
24

---

Proof. Firstly, by the non non-exxansiveness of projection operator, we have
11 y" (#x+1)ll
11r y" (#x+1) )1² 11 - - gi 1
1irA+11 y" (xx) 12 + 1lv" (#x+1) y² (I+) (1i,k+1 y² (#x), wy" (#x+1) - 44 (fx))
(44)
1 y" (Tx) 12 + l1v" (#x+1) y² (Ix) 1
( y" (#x))² Vy" (5x) (TR+1 5x)²
2 ( y" (+x))) (v" (aR+1)- -y" "y" (#x) Vy (#x) (FR+1 (FA+1- -r0)))
Then, for the first inner-product term on the RHS, letting V. = V (X:, VxF (x),
get
2 (ÚC,++ '² (3x)) Vy" (3x) (fx+1 x6)²
2 (Dik41 y-' (mx)) T Vy (ok) (V.F yk))
1 k+1
a
Fkt1
n2
n
2 (0i,+1 - 3² (3x)) T Vy (mx) (vofit) T
10 k+11
1 a
k+1
+
71
11
(45)
10
a
2T 110,,+ - '² (fx)ll
P (xx, yz))²
k++1
n
T
10
a x++1
2% (0i,4t1 n" (mx))² T Vy (Tx)
Fr
n
wherein the last inequality we have used the fact that y is k- Kipisschitz. Then, using Young's inequality with parameter dε. we get
2 (0i,411 - 3² (ix))² Vy" (3x) (Tx+1 - xx)²
< Au 11 3² (Ix)ll
2 b+1
U 20x2 x2?
||
1"d V F (x8)
(b T' no a
F (x))
(46)
d
+ 2% (01.441 V² (Tx)) T Vy" (7x) (v. T
10gtt
1/+t1
72
For the second inner-product term on the RHS, noticing that 1y is i. i== 1. (1 + xx)² smooth given in Lemma 2, we have
(fi,+1 y" (Tx))²² y" (Tx) - 3² (Tx+1) + Vy" (Tx) (Tk+1 - =za)
< <21l0i.et1 - -² (*+) 1Iv" (ox) - 3² (ōR+1) + Vy" (3x) (Ze+1 x12
< 2 1100,041 - 3- (#x) i
|| xxll
2
(o
< 22 - - (*+)l
+
(xI(
n
20
2a (1 + (2 C
< 3.2 3² (ix))l
|
(XL, Yks 1I
n
To (1+ (2) i
< < 2a (3) C 11 01,++ y² (ix)ll2
|
(xx, 22) (47)
T7
25

---

wherein the last inequality we have used Young's inequality with parameter т. Plugging the obtained inequalities into (44), we get
Vitk+1 - V/ (T++1)l?
(1 + d + m -2 (1+ (.) ( |0 22 (fx))?
<
1/ u (1+ +z)
2x + i
|V
(x
n
(48)
2
27 1/ k+1
20 x
17
F (x8: 120 )|
(+
F (xX:
ni
Vy" (7xx (voF)²
T 18/41
0641
+ 2% (0r,441 V² (ix))
+
n
Setting the parameters for Young's inequalities we used as follows,
20
AR=
Jry %0
(49)
4 (1 ( C2
then we get
11 82 (
1Ty u
1 1
|10,0111 -y" (ix)]l
2
1ar (1 + (2)
4 (1+ + (2) C²
2k
2a
V F
(x yu: Ex1l
17y00 20 8
(50)
8 8 20 x2
1T V F FI,FFx yk)
(Dff1)
V F (xk- Mkc)
K+11
n
Vy" (5x) (v=Fz)) T
18 +
+ 27 (0i,411 V² (ix))²
n
Recalling that
1
E
|
50' (#x))11
U++1
34r u 2x.1/44
SKL E
E
lIvE 17" (fx))12
[xx 15x1
1=1
My Ux+1
2%
(1
(2)
F (x: Ex]
- [2 (f (āx, J" (2x)) - f (#x, Tk))
9
+
8
k+
+ 2CE
lly: - 17
nū, nug+1
26

---

and multiplying by (2+ no
2
on both sides of (50), we obtain that
E (T 10' (5x)) (o&z [kh]
7v (1 Sa)
+ 4nih
<
E [Ei,a] +
uk+t [V F (xa.
YniEe)) (xi
|
15 12)
9
[
+ 4
V
(xk+ ykii 5
+ CE
Il - 18xl
1
4 1
k+ 2k
1s
2
21
+ -E
- Vall (xk (x)
+
V F (xL) yk)
/17 " k+1
2/
ni
(51)
22 (1 + (2)
272 (1 + ( 2
20x kk+1
n +
E
| F (xk. Ex)1
1
2a -
I'y uk+1
B|Eg,al
1
Y
(0i,k+1 - (2x)) Vy" (Ix) (v=Fis)
10
a
uk+1
E
B
71
1=1
B[E
Telescoping the terms from to to K - 1, we get
K
Elʃ (Tk. 1" (Tx)) - S (Tx, Øk)]
k=
K-1
K-1
K-1
K
E [1
Σ
E E2,1
E
[ +
E [E4,a]
k=
k=
k=
k=
(52)
Y/ (1 + Su
4xL
K
E
Ux+11
9
V
(xx.
E
||xx
18
n
k=
uk+1
+
E
V
+
llyx
17x
3
n#
k=Ao
Next we need to further bound the running sums of E [F2,s). E [Fg and E [Fa. respectively. For [22,s], with the help of Assumption 2 and noticing that üy & G, 0, 1, ko 1, we get
[E2,,]
k=
K
4 2m k++1 K²
1 V (E)
R
+
V F
(xx,
y1:)
(53)
117 u
no
k= ko
2n2
(1 + (
I,2
E
V
(T U1
Ak
p2g G2
23
k=
27

---

Then, for the term E () noticing that ux+1 < Uk+1 and Uk+1 2 U1. we have
1
[
k=
(1+ (
k²2 + 2 (1+ (1+ C
2a k
E
V F
vx:
(54)
k=
mly
2a-3 11y01
#k+1
2 (1 (2)
N + 27 (1 C²
K
E
k++
V F
(x
Yu: (
p1
2a-8
k==k
For the term Ea,k, we denote
T (
ck
(0iR++ 32 (#x))))
Vy" (Ix)
Yy 2
n0
1=1
then we have
lexl
$
2 9 91
7/ 1 n
Σ
1ir 3² (B+))
(vafi)" T
(
n
i=1
Aa (1 + (o)
1
Vuf (3k (1,411) Vut (Ix: w')ll|
||
(55)
To ntu
27 (1 (o) C
where we have used the Lipschitz continuity of y" given in Lemma and Assumption 3. Then,
noticing that V Fr
we obtain
Σ E
[aaR
Σ E [e
K
K-1
1 -1
Ux a
E
Ek
(6p
k+1
a
R ko
Ao +1
>0
(56)
K
< M0 hotil
+
Σ E M (J)
-
k=ko+1
4ya (1 Co) C
2E
M
+1
E m
Pyy0
Therefore, combining the obtained inequalities, we complete the proof.
Now, it remains to bound the term E1,k-
Lemma 8. Suppose Assumption 1-4 hold. Then, we have
2 244C2) 2+ 127
1 I 1y" (2o)11
E
[1
&
+
(57)
21 n
3 r'1
2+ -- n 28
2-28
28

---

Proof. Recalling the definition of 1 as given in (34), we have
K
3
k+1
3
/4
lyr 1y" (E+)11 lyk+1 1y (#x+1)ll 11?
E
Yy Uk k+1
3 10 u+y 1
1
9
9/4
11y0 1y" (3o)ll
Yyy 21 -n
K-
3 3p
E
1lye 10" 12" (Ex))1
2n ux B (2 u #))
27y 1
(58)
33) 9/4 Ilyo 1y" (3o))l
1 3p "
21
3 n
K-
1
E
+
y
1y" (a+))?
20
k+1
8 4k
8
2
wyy
uk
9
2
Next, we show that the term If the term is positive at iteration k. then we have
is positive for only a constant number of iterations.
21y0241
2ny 62
11 k++
ug
4
27
2y
8
Ya: EHI /naz)" 8
1 V F (xx.
Uk
p
27y
8
(59)
1 + 3 V (xx, yks (x) ???
/nuu
0k
27y
27
8
B V F (xx. Nki 1|
2
8
wherein the last inequality we used Bernoulli's 's inequality. Then we have the following two conditions,
7 19
No u -
1
F
(x VnikL)1
>
13
(60)
1.G²
43
V V
(x).
1-8
14%
which implies that we have most
4
43
(61)
pMy
Mry 01
1-8
constant number of iterations when the term positive. Furthermore, when the term positive, by the inequality (59), we have
1
1
y 1y (T2)
B
27
8
3
V., (Xx
YRi 1
llye 1y" (fx))l²
2
1 B
n
(62)
BC2
Vyde (TR, Vi.)) - Vyli (Tx, v/" I|(
2 u
3
1=1
2,C
1227 11 1-
29

---

where we have used the concavity of fi in y and Assumption 3. Then, we have
I
1
1
Iy:
1y" (x))
27/
2% kk
3
8
n
2
(43C2
4,
(63)
12271/ u 1-8
1-8
Poy 01
2+ 1-B
2 (4302)
2+
1- ui
2228
which 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 we have
6 (
4pw
(1+ G++))
F (Xb.
YKi (E)
K
nū
n 1-a
(1- (1-Pw)
(1 a) Ka
k=0
(64)
and
T
K
1
4pw
(1 + Gu) C,C2-8
E
VyF F
(xx, yei (
K
nū
n-
(1 pw)
(1 (3) KB
k=0
(65)
Proof. By the definition of v; in (3), we have
E
(x+,
Yki (
nū
27
9
E
La
Ug
a
20
(66)
im
Pr,
E
0f )
2a
J
i=1
1,t+1
30

---

Noticing that
< So. we have
Ü k+1
E
VxF (Xio Yki
k+1+
12
'k+1
k
11
ko+1
2
k+1
F5,4
11
1,k+1
2a
1b++1
22
Uk++1
(67)
Fe.A
+ E
PK41
2
1,
1
9i.h
<
0kt1
n
By Lemma 4, we get
K-
(Tnti)
E
V
(X
K
k01
k=
K-1 5
7 -i=1
Fi.k
& Go) G.E
Uk
a
K
k=0
0k+1
(68)
2- 20
< (1+ S.E
(1 a)) K
< <1+
1 7
||okt] 10++1
22
22-2a
(1 - a.) K
Next, for the term of inconsistency of the stepsize || - 10x we consider two cases due to the
max operator we used. At iteration k; for the case m > m with || 1māl2 = 0, we have
|1u+1 10 11
IE
[
1m 113
E [I(W
(mf
1mm) + Ti (W J) Ao 12
1 PW
||m] 1m6l?
(1 + pw) pw JE |1
2
pw
(69)
1 + PW
[|mm 1m6l"
n² (1
pw) pw
1 Pw
k-t
-P
2
2nC (1 +1++ pw) pw
(1 (1-pw)²
For the case m < m with |m - 1m = O.
2nC (1+ (1+pw) pW) Pw
E | 10 11?
E |m 1m [2]
(70)
(1 -1- -Pw)²
31

---

Combining these two cases, and using Lemma 4 and the fact aa - - < ||1 - ll 20 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.
1|
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 have
E
k+1 k+1
F Yk:
< C2
a
k=0
T
(71)
3
E
(Xk,
Vni
< C.
B
k=
Proof. By the definition of inconsistency stepsizes in (8) and Assumption 3 on bounded gradient, we immediately get the result.
B.3 Proof of Theorem 1
Proof of Theorem I. Consider a complete graph with nodes where the functions corresponding to the nodes are as follows:
fx
2)¹ 2 .y
2
1
1
1
fa - fz(x,1) = -2²²² - (1 +
+
jzy
x²
b
2
where a = 2 and b --
Notice that the only stationary point of f(x 3) = (f1(x, v) + fe(r.)) v) + fa(z, is (0. We
denote -h V f. (Fx, 3x) and gh Vyfiizz (2g, yk).
Now consider points initialized in line
+ a
2/
(72)
+
where we have
2ah + a +
gī,0 = yo
ab +
2ab + b a²(b + 1) 20
$2.0 = $5,0
+
yo Zo
a
2ab + + b
gi,0 Ho
yo
Fo
ab a
2ab + + b
2h.0 22 ab(b 1) TT-
Note that by our assumptions of the range a and 3, we have a < b. Thus, we have
| = loYool and 1g > loh
32

---

which means 32.0 would be chosen in the maximum operator in the denominator of TiAda stepsize for x. Therefore, after one step, we have
9ī.0
22.0
93,0
I1 30
(T)
(3)
92.0
$3.0
y1 = y/ - r/"
(1)%,013)
(10%,01 3)
(193,01))
Next, we will use induction to show that ar and will stay in zo and yo for any iteration. Assuming for all iterations in I,...,6 t, Ikk = zo and yk = yoo then we have in next step
$2.0 (t.
93.0
21+1 21 17" (t oo)
+
(t 15.00
Note that 5i,0
92.0 Then, we get
92.0
2
2++1 = It 17
ta
a 2cx
19200 2a
to
195.0 2
92.0
Ft
(2
1a
1955
22
-0 (by definition of a))
Zt-
Similarly, we can show that Mt+1 yt- Therefore all iterates will stay at (Io. wo) if initialized at line ab4a 2, which implies that the initial gradient norm can be arbitrarily large by picking zo to be large.
B.4
Proof of Theorem 2 and Corollary 1
Proof of Theorem 2. Combining the results obtained in Lemma 6, 7 and 8, we get
K 1
E [f (āx, v² (āx)) - ff (Ix, Tw)]
K-1 Σ
Σ
E [s (Tr, y² (5x)) I (Tx, Th))
Bss (Tx. y² (fx)) S (Tx,
k=
(4,322) 2+ -ー
1
|180 1y (mo))l?
2% 11
8 n
3+
2+ 2+ 2-23 23
7v
01
2x
(1 + (2)
G23
kp
E
F (xx, yki 52 12
mprr
(73)
1v (1 + (2)
K
K-1
+
E
U
1++1
(x
Yki Ex)l +
1 17k
n
k=0
K-1
3
822x2 (1
(2)
K-1
+
d++l
V
yki
V
(Txx 21
un G2 220-88 -28
nū
k=0
k=ko
8x2x2 L2 (1+ +2)
4xLL
K
47 (1 + (o) C
+
Σ
E [[Ax] +
E
mung 22aa-22
2
(1 + 22)
2 (1 + 22)
Tptt n
E
|
(xx.
H7y 57 20
k=
33

---

Letting the separation point between the two phases discussed in Lemma 6 and 7 satisfy
( [61
16 (1+ (:) 12
G
(74)
7/
then, plugging above inequality into (18), with the help of Lemma 4-8 and Lemma 9, we get
1 K- Σ
TR )
K
k=0
< Eo + EG + Ew + 80 (Tmax - $6)
PaKi-a
3 (1 ,2 So) C2+28
8K.T. (1 (1+52) (2) C2-20
+
7y KI-8
3) K3
1 In
27/ (1 + ( C²
8 (1++g) (.) C2-2a (1 (1-0) a) K
+
+
+
30 -28 1/
(75)
4pw
16 (1 + So) G,
+
n
)
a1))) K
1
4pw
32k² (1+ (u) CuCB-B
+
(1 pw)2
(1 B) K3
8pw (1 (1+
(2) (2)
22-48
+ log log 21
+ 8KLC
(1- 23) K28 Tx<1/2 +
I 1/2
(1 11-ww -Pw)²
Kul ku29-1
where
L = xs) Lo L (( (1+ + x), and
16k² 2 (4802) 2+ 2+,
Fo
4kL
E.
[1180 1y" (=
U1 13 n
Ku 2+ 1-
24
r'r 2 2-22
ūj
16 (1 + (2) G28
22-4a
+ log UK
log v1
Eg
(1 20x) K2a Ja<1/2
Kiza- 2a
aa212
Ew = 32 (8kT. + 3T.2) 12
2 (1 + (+)
22-1a
+ log uK - log 11
(1-Pw)² )
(1 (1-2a) 2a) K2n
Ta<i/2
K 20
II 1/21/22
32 (8kL + 3 pW (1 1 (
23-43
1 1+ log uK log U1
(1 pw)
(1 - 23) K28 B<1122
K 28-1
131/2
Letting the total iteration K satisfy the conditions given in (12) such that the terms Eg. Eg and Ew 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).
B.5 Extend the proof to coordinate-wise stepsize
In this subsection, we show how to extend our convergence analysis of D-AdaST to the coordinate- wise 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 G.
34

---

Algorithm 2 D-AdaST with coordinate-wise adaptive stepsize
Initialization:
2i,0 E R", Vi,0 E V, buffers mi.o m O, stepsizes Yo. Bv and 0 < <
a < 1.
for iteration & ==0,, 1,..., each node E [nd]. do
2: Sample i.i.d Gū and Ei, compute:
g Vafi (Ta,k, Mi.ki S L, Vusi (RiA.BLA
3: Accumulate the gradient with Hadamard product:
= n + Fi, @ Fh,s m² m Ri K'
4: Compute the ratio:
||m 20 maxx | 11
2a |
11,++
5: Update primal and dual variables locally:
21,++1 = Li,k 2s (mi,+11 -a
Lū
V = Vi + Yr (m²
2 gh
6: Communicate parameters with neighbors:
{ [ m 1 Ti, Mh++1 +
Σ
Wis m mjj m m², 23,411 BjA+11
JEN.
7: Projection of dual variable set V: Ni,++1
Py (Jr,A+1).
8: end for
m = W (mg + hg)
(76a)
my = W (m" + h
(76b)
Xt+1 W (xx Ta V41 V (xx,
(76c)
Yk+1 Py (W (Ve + My U V (XL. (x:
(76d)
where
= [... F - 1 Raxp, h²= Shh. g ... . Ruxd
and the matrices Ug and v are redefined as follows:
Vi [.... 2 -I" [ua,el, max [
[miial)] [p].
(77)
8 UpP 8 ... Ui
1" [me,ely [m²'a] ) [d],
1
where F,ly denotes the j-th element of vector. Recalling the definitions of inconsistency of stepsize in (8), we give the following notations:
V Vv 11 U
1
Vig.
Σ
P
Vija
Vij
np
p
n1
,
(78)
d
1
1
Ur Uv 11
Usi
Σ
Uijr ūg
Usi
nd
à
1=1
1=1
35

---

and
V 2
1l
Vx
(VxJp)
24 sup
22 sup kzu
kz0
np (x
U R
117 u
(U%JJa)~
c = sup
C2 = sup k20
k20
nd
3 1
nd U #
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 have
17
E
O F (Kk. (k)
K
nū
k+1
k=0
(79)
p0
C2-2a
2 + Gog
+ C2
n 1-a (1 pw)
(1 a. Ka
and
1
E
Ü -8
k+1
2 vuF (Xx, yki yki
nix++1
(80)
1
4C2pw
22
< 2
Su) Su Sug
(1 3) K + Ond
11
(1 - (1-
pw))
In contrast, for D-TiAda, we have
K
T
E
V
< SSZ
K
k+1
k=0
(81)
K
1T
Σ
E
U
[Kk V.
yki
< C2
ni
Proof. For the coordinate-wise adaptive stepsize, with the definitions of Frobenius norm and Hadamard product, we have
1 T
E
$
k+1
no
T
E
(V++1J) a + (Vo+1J) -a 11 @ V (xt Vei
k+1
n0
(82)
1T
< 2E
- 3 (x
IT
+ 2E
k+] - (V++1J)-a @ V.F (xi
36

---

For the first term on the RHS, according to the definitions given in (78), we have
1sr
E
Uh+ 11
C V (xi,
n+1+1
(83)
<
E
1 - +1+1 Vafi (R:A.
n
2
2a k+1
Then, for the second part, we have
2
Vi- (Vi+1J) -9) ④ Xks Yui Ski
n2
k+1
1
k+1
(Vo+1J)
|| (xx. yxi
(84)
11
U141
p
E
| (xa 22:
where the term 2 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,
1
E
(X yni
E
k+1
V F (Xs, yx:
<
nu
n
ū k++
(85) L
and using Lemma 9, complete the proof.
Theorem 3. Suppose Assumption 1-4 hold. Let < < < 1 and the total iteration satisfy
max 11
12
K = Ω max
7
(1
pw)
to ensure time-scale separation and quasi-indeepndennce of network. For D-AdaST with coordinate- wise alaptive stepsize, we have
K-1
V [T+))P]
K
0=0
(1 pw) Ka + K1-B + (1 pw) K3 +0 (p82 x==dd C²).
1
KI-a
(86)
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-wer wise adaptive stepsize.
show that the coordinate-wil variant of D-AdaST exhibits a steady- state 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 Algorithum 2).
Remark 6. In Theorem
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The contributions and scope of this work have been accurately discussed.
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.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes],
Justification: We have carefully discussed the limitations of this work in terms of assumptions and main results.
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 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 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
38

---

Justification: We have provided full set of assumptions and complete proof for the theoretical results. See Section and Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided detailed experimental settings and reproducibility informa- tion for the experiments of this work. See Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
39

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code of this work included the supplementary.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nipp cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//niss cttppsccccpbccccccceeeeccccccccc httee/guuudeeeeeeuubiiaeeeeeee
/Cooeeeooiissseeeeee wwssssnoolicyo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We have provided detailed experimental settings in Appendix A.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Multiple runs with averaging are used to produce the experimental curves in this work.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
40

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 96% CI, if the hypothesis of Normality 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 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided sufficient information on the computer resources Ap- pendix A.
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 compute required for each of the individual experimental rums well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https / http//nnrrpp..ee
wttprips....pppueee wwtppblcc//aaeecccccccccceeeeeet Ceteeiic//iieeee csQuideliunnnnnnn ines?
Answer: [Yes]
Justification:
This work conforms with the NeurlPS Code of Ethics.
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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper presents work whose goal is to advance the field Machine Learning. There are many potential societal consequences of our work, of which feel are negative.
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 why the paper does not address societal impact.
41

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 best faith effort.
12. Licenses for existing assets
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?
Question:
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 use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include 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 use in package should be provided. For popular datasets, paperswi wwwode.hho....c. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
42

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code of this paper is included in the supplementary.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
43


Reviews:
[{"review_id": "paEryh9fUR", "reviewer": "Reviewer_rQb7", "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. \n\nIn 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.\n\nThe 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.", "questions": "Some of the figures are rather difficult to read when printed on paper as they are rather small, but were readable digitally.\n\n* Is there a reason the constant $C$ does not appear in e.g. (13)?\n\n* 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": "Within the scope of the article, I think limitations are appropriately addressed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The article is well written: the authors explain the problem clearly and the algorithm is clearly outlined. \n* The result and formulation of Theorem 1 are insightful, and the synthetic example of (6) is simple yet very instructive. Together they outline the problem to be overcome in Section 2.2 nicely.\n* The authors provide an (almost) rate optimal theoretical guarantee for their proposed method.\n* The chosen real-world settings are both interesting and illustrative.\n* The proposed method is attractive in terms of communication complexity, with only a couple of scalars being required on top of the gradients.", "weaknesses": "* 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.\n\n* 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? \n\n* Similarly, the uniform bound on the gradient seems rather strong. Is this really required by the analysis?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the insightful and valuable comments. Please see below for a detailed point-by-point response.\n\n>__W1:__ 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.\n\n__Response:__ First of all, we would like to further clarify the scope and contributions of this work. In this paper, we focus on a nonconvex-strongly-concave distributed minimax problem over networks, which subsumes many applications in machine learning and optimization. To mitigate the challenge of hyper-parameter tuning, we propose the first parameter-agnostic distributed adaptive minimax algorithm, D-AdaST, that efficiently resolves the issue of inconsistent adaptive step sizes with relatively low communication costs, achieving a near-optimal rate. Moreover, the obtained convergence results indeed highlight the dependence on network topology as well as the trade-offs between convergence speed and the length of the transition phase (cf. Remark 5), as demonstrated in the experiments. We concur with the reviewer on the importance of considering communication efficiency and the influence of different noise sources in future work.\n\nRegarding the assumptions used in this work, we will provide a more detailed discussion of the rationale and limitations of the assumptions in the revision. Please also refer to the subsequent responses to specific assumptions.\n\n>__W2:__ 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?\n\n__Response:__ We agree with the reviewer that obtaining the unbiased stochastic gradient is not always feasible in practice. Nevertheless, this remains one of the most widely used assumptions in optimization and machine learning when uniform sampling is performed in an independent and identically distributed (IID) manner. Without this assumption, the biased term in the gradient may introduce an extra constant steady-state error in the current convergence result, which cannot be mitigated by employing decreasing stepsizes [1]. Nevertheless, the algorithm still functions and if the bias is small relative to other terms or exhibits a certain structure, e.g., memory-biased (c.f., Definition 11 in [2]), more explicit convergence results can be obtained [2]. We believe that investigating these biased stochastic gradient models represents an interesting direction for future work.\n\n>__W3:__ Similarly, the uniform bound on the gradient seems rather strong. Is this really required by the analysis?.\n\n__Response:__ We remark that the assumption of bounded gradient is essential for the adaptive methods to achieve the property of being parameter-agnostic, thus reducing the burden of hyper-parameter tuning. In our proof, without the assumption, the term $S_1$ in Eq. (18) cannot be proved to be vanishing. As a result, one would need to employ the negative term $-\\frac{4}{K}\\sum_{k=0}^{K-1}{\\mathbb{E} \\left[ \\|| \\nabla_xf\\left( \\bar{x}_k,\\bar{y}_k \\right) \\|| ^2 \\right]}$ to absorb $S_1$ to ensure a sufficient descent. However, this typically imposes specific requirements on step size selection that may depend on the problem-dependent parameters, as also observed in [3], which contradicts the basic principle of a parameter-agnostic method. Indeed, to the best of our knowledge, in the field of distributed nonconvex-strongly-concave minimax optimization, there is no existing parameter-agnostic method that achieves the (near) optimal convergence rate while also eliminating the bounded gradient assumption. On the other hand, as detailed in Remark 3, this assumption is widely used and can be met by imposing constraints on the bounded domain of decision variables in many real-world tasks [4, 5]. \n\n>__Q1:__ Some of the figures are rather difficult to read when printed on paper as they are rather small, but were readable digitally.\n\n__Response:__ To express the experimental results more clearly, we will adjust the text size and the thickness of the curves in the figure appropriately.\n\n>__Q2:__ Is there a reason the constant $C$ does not appear in e.g. (13)?\n\n__Response:__ For better readability of the convergence results, we show in the main text only the dependence of the convergence on some key parameters, while hiding other constant parameters such as $C$. The explicit convergence result with dependence on $C$ can be found in (75) in the Appendix. We will present a more detailed convergence result concerning other parameters in the revision.\n\n>__Q3:__ 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?\n\n__Response:__ Theorem 1 shows that the D-TiAda algorithm does not converge in certain scenarios, while Corollary 1 esentially shows that the underlying reason is due to the inconsistency of the adaptive stepsizes, i.e., $\\zeta _{v}^{2}$ and $\\zeta _{u}^{2}$ in (14), compared to the result for D-AdaST in Theorem 2. Together with these conclusions, we have demonstrated the impact of the stepsize inconsistency in the distributed adaptive minimax methods, as well as an efficient stepsize tracking mechanism to solve this problem. We will revise this part of the statements accordingly to avoid any possible confusion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aoUc9ZcaLC", "reviewer": "Reviewer_vU1y", "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.", "questions": "Please see weakness.", "limitations": "The paper employs general assumptions for distributed minimax optimization problems; therefore, it is unnecessary to discuss the limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality and Significance:\nThe paper introduces a novel Distributed Adaptive Minimax Optimization Algorithm with a Stepsize Tracking Protocol. This approach is significant in addressing the non-convergence issues that arise when transitioning adaptive single-machine algorithms to a distributed environment. The authors provide a thorough theoretical analysis, which could facilitate the development of similar methods or modifications to existing single-machine algorithms.\n\nQuality  and Clarity:\nThe paper is well-structured and clear, with thoroughly explained assumptions and convergence rates, making it easy to understand.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">__W1:__ 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.\n\n__Response:__ Thank you for your comments. 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 the __attached PDF file in General Response__. We use the entire training set of CIFAR-100 with coarse labels (20 classes) to train GANs over networks, where each node is assigned four distinct classes of labeled samples. Due to time constraints, we ran one experiment with the same settings as in Figure 4(a). The revision may include other complementary experiments on additional datasets. It can be observed that D-AdaST outperforms the others in terms of the inception score. Together with other experimental results in the paper, we believe that we have demonstrated the effectiveness of the proposed D-AdaST method and its potential for further real-world applications.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HvTbEjs6zl", "reviewer": "Reviewer_Nhkx", "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$.", "questions": "The proposed method does not require the knowledge of the parameters $L$, $\\mu$ and total iterations number, which is nice in  empirical. \n\nI have some questions as follows:\n\n1.\tThis 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. \n2.\tAssumption 3 introduce the upper bound $C$ for stochastic gradient, which should be included in the final convergence rate.\n3.\tCan you provide some explanation why the small $\\delta$ cannot be avoided in result? What happens if we try to take $\\delta\\to0$?\n4.\tThe 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$.\n5.\tIs 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": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "see questions", "weaknesses": "see questions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and suggestions. Please see below for a detailed point-by-point response.\n\n>__Q1:__  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 problems 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.\n\n__Response:__ We will further clarify the definition of optimality of the convergence in the revision to avoid possible confusion. Specifically, we followed the definitions in [6], where they derived a complexity lower bound $\\varOmega \\left( \\epsilon ^{-4} \\right)$ for a class of smooth nonconvex-strongly-concave (NC-SC) functions (c.f., Definition 1) and the first-order algorithms that satisfy the zero-respecting condition using only (historical) gradient information (c.f., Definition 4). Under this problem setting and algorithm class, they proved that the dependency on $\\epsilon$ is not improvable. Therefore, we claimed that our obtained convergence rate $\\tilde{\\mathcal{O}} \\left( \\epsilon ^{-\\left( 4+\\delta \\right)} \\right)$ is near-optimal in terms of $\\epsilon$ in the sense that the parameter $\\delta$ can be arbitrarily small so as to achieve the lower bound. It should be noted that the parameter $\\delta$ can not be 0 due to its key role in ensuring time-scale separation (refer to the response to Q3 and Remark 4 for a more detailed discussion). We note that, to our knowledge, there is no existing parameter-agnostic method that achieves the optimal convergence rate for NC-SC problems as considered in this work, even in a centralized setting. \n\nRegarding the assumption on second-order Lipschitz continuous for $y$, we note that it is essential for achieving the (near) optimal convergence rate $\\tilde{\\mathcal{O}} \\left( \\epsilon ^{- 4} \\right)$ for NC-SC problems [7, 8]. Specifically, together with Assumptions 1 and 2, we can show that $y^*\\left( \\cdot \\right)$ is smooth (c.f., Lemma 2). Nevertheless, without this assumption, [9] only shows a worse complexity of $\\tilde{\\mathcal{O}} \\left( \\epsilon ^{- 5} \\right)$ without large batch size (c.f., Remark 4.6).\n\n>__Q2:__ Assumption 3 introduce the upper bound $C$ for stochastic gradient, which should be included in the final convergence rate.\n\n__Response:__ We will provide a more detailed convergence result including dependence on $C$ in the revision. The explicit convergence result can be found in (75) in the Appendix, which shows the dependence on $C$ and other constant parameters. \n\n>__Q3:__ Can you provide some explanation why the small $\\delta$ cannot be avoided in result? What happens if we try to take $\\delta \\rightarrow 0$.\n\n__Response:__ We note that, for the NC-SC minimax problem, it is necessary to have a time-scale separation in stepsizes between the minimization and maximization processes to ensure the convergence of gradient-descent-ascent-based algorithms [10]. As shown in Theorem 2, the transient time required to reach this state is related to $\\left( \\cdot \\right) ^{\\frac{1}{\\alpha -\\beta}}$, while we need $\\alpha -\\beta =0$ to reach the convergence rate of $\\tilde{\\mathcal{O}} \\left( \\epsilon ^{-4} \\right)$ (c.f., Eq. (13)). Therefore, by setting $\\alpha -\\beta =\\mathcal{O} \\left( \\delta \\right), \\delta >0$, we found that the smaller $\\delta$, the faster the convergence and the longer the transition time (c.f., Figure 9 in Appendix A.3). Particularly, the transition time becomes infinite when $\\delta$ approaches 0, indicating that the algorithm does not converge. Therefore, the parameter $\\delta$ plays a key role in achieving adaptive time-scale separation as well as balancing the convergence speed with the transient process. Please refer to Remark 4 for a more detailed discussion.\n\n>__Q4:__ 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$.\n\n__Response:__ In the introduction, we initially introduced a general minimax problem with $x\\in \\mathcal{X} \\subseteq \\mathbb{R} ^p$ and $y\\in \\mathcal{Y} \\subseteq \\mathbb{R} ^d$, which subsumes both scenarios of the constrained and unconstrained problem, as $\\mathcal{X}$ and $\\mathcal{Y}$ can represent the full Euclidean space with appropriate dimensions. For the specific problem (1) considered in this work, we set $\\mathcal{X} =\\mathbb{R} ^p$ and  $\\mathcal{Y} \\subset \\mathbb{R} ^d$ is a closed and convex set, which is widely considered in centralized/distributed NC-SC minimax problems [10, 11].\n\n>__Q5:__ 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.\n\n__Response:__ We agree with the reviewer that the complexity of communication can be further reduced by incorporating certain techniques that amount to increasing the batch size of the stochastic gradient, such as variance reduction [12] and multiple local updates used in federated learning [13]. As mentioned by the reviewer, Chen et al. [12] used larger batch-size or full gradient evaluations (c.f., step 15 in Algorithm 2), together with the FastMix protocol, to reduce the computation and communication complexity. However, it should be noted that the resulting complexity is obtained under a stronger assumption of the average smoothness (c.f., Assumption 2.2 in [12]). Instead, we obtained a near-optimal rate under a weaker assumption of smoothness (c.f, Assumption 2), which is commonly used in machine learning tasks [6].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AOdSM0AsD5", "reviewer": "Reviewer_KXvx", "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.", "questions": "1- How does D-AdaST compare to other existing adaptive minimax methods in terms of computational time efficiency?\n\n2-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?\n\n3-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": "They discussed the limitations of their work in terms of assumptions and main results.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses a significant challenge in distributed minimax optimization by introducing a method that achieves near-optimal convergence rates. The theoretical contributions are well-founded, and the experimental validation is comprehensive.", "weaknesses": "Please consider my questions for this part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments and suggestions. Please see below for a detailed point-by-point response.\n\n>__Q1:__ How does D-AdaST compare to other existing adaptive minimax methods in terms of computational time efficiency?\n\n__Response:__ We note that, as discussed in the Introduction section, there is limited literature on the distributed adaptive minimax method; instead, the proposed D-AdaST is the first distributed adaptive method that achieves near-optimal convergence without knowledge of problem-dependent parameters for nonconvex minimax problems. The resulting *sample complexity* $\\tilde{\\mathcal{O}} \\left( \\epsilon ^{-(4+\\delta)} \\right)$ with arbitrarily small $\\delta>0$ represents the number of stochastic gradient computation needed to find an $\\epsilon$-stationary point, which indicates the theoretical computational complexity and is near-optimal compared to the existing lower bound $\\varOmega \\left( \\epsilon ^{- 4} \\right)$ for the centralized nonconvex minimax optimization [6]. Experimentally, we compared the convergence performance of D-AdaST with the distributed variants of AdaGrad, TiAda, and NeAda in terms of the number of *gradient calls* (see Figure 3 and 4), which properly represents the computational efficiency of the algorithms when all experiments are run on the same server with the same batch size. We believe that these results demonstrate the superiority of the proposed D-AdaST algorithm regarding computational efficiency.\n\n>__Q2:__ 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?\n\n__Response:__ Given the limited existing work on distributed adaptive minimax methods, we believe that it is an interesting and important direction for future work to study other problem settings, such as nonconvex-nonconcave or convex-concave objective functions. For the convex-concave setting, we expect that the convergence analysis techniques from centralized methods [14] can be used to obtain results in our decentralized setting. Going beyond the convex-concave assumption poses a major challenge in the sense that there is no well-formulated suboptimality measure for general nonconvex-nonconcave problems. Specifically, for a general nonconvex-nonconcave minimax problem, a saddle point may not exist even in a centralized setting [15], and determining its existence is known to be NP-hard. Therefore, making additional assumptions to ensure better properties of the inner problem is necessary,  such as employing the Polyak-Lojasiewicz condition on $y$  to obtain global convergence for the nonconvex-nonconcave  problem [16].\n\n>__Q3:__ 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?\n\n__Response:__ We believe that it is an independently interesting and important problem to consider the communication delays and asynchronous communication protocols in distribution minimax optimization, which requires major adjustments to the communication model. Particularly, we notice that in [17], by constructing an augmented topology graph (c.f., Fig. 2), the delayed and asynchronous system is reduced to a synchronous augmented one with no delays by adding virtual nodes to the graph. They obtained linear and sublinear convergence for strongly convex and non-convex minimization, respectively, under the assumptions of bounded delay and asynchronous model (see Assumption 6 in [17]). This motivates us to potentially extend this technique for modeling communication to our setting in future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
__General Response to All Reviewers__

We would like to express our gratitude to  all the reviewers for evaluating our work positively and providing their insightful and valuable comments that have helped us greatly improve the quality of our paper.

We have carefully considered each of the reviewers' concerns and provided a detailed point-by-point response under each rebuttal section. Minor comments aside, our response includes the following major aspects: i) we have further clarified the scope of this work and discussed the rationale behind our assumptions; ii) we have conducted an additional experiment on a more complicated dataset CIFAR-100 (c.f., the attached PDF file in this general response block) and will add more experimental results with additional datasets in the final version; iii) we have provided detailed explanations to clarify certain concepts and statements; iv) we have discussed possible extensions to other general settings of the problem as well as the communication model. Unless otherwise noted, the citations in our response correspond to those in the submitted manuscript.

Below are the references used throughout the rebuttal, which have been properly cited and compared in the main text.

* [1] Hu, B., Seiler, P. and Lessard, L. Analysis of biased stochastic gradient descent using sequential semidefinite programs. Mathematical Programming, 2021.

* [2] Driggs, D., Liang, J. and Schonlieb C. On Biased Stochastic Gradient Estimation. JMLR, 2022.

* [3] Huang, F., Wu, X., and Hu, Z.. Adagda: Faster adaptive gradient descent ascent methods for minimax optimization. AISTATS, 2023.

* [4] Dinh, L., Pascanu, R., Bengio S. and Bengio Y. Sharp minima can generalize for deep nets. ICML 2017.

* [5] Arjovsky, M., Chintala S. and Bottou L. Wasserstein generative adversarial networks. ICML 2017.

* [6] Li, H., Tian, Y., Zhang, J., and Jadbabaie, A. Complexity lower bounds for nonconvex-strongly-concave min-max optimization. NeurIPS, 2021.

* [7] Chen, T., Sun, Y. and Yin W. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. NeurIPS, 2021.

* [8] Li, X., Yang, J., and He, N. Tiada: A time-scale adaptive algorithm for nonconvex minimax optimization. ICLR, 2023.

* [9] Lin, T., Jin, C. and Jordan M. On gradient descent ascent for nonconvex-concave minimax problems. ICML, 2020.

* [10] Yang, J., Li, X., and He, N. Nest your adaptive algorithm for parameter-agnostic nonconvex minimax optimization. NeurIPS, 2022.

* [11] Tsaknakis, I., Hong, M., and Liu, S. Decentralized min-max optimization: Formulations, algorithms and applications in network poisoning attack. ICASSP, 2020.

* [12] Chen, L., Ye, H. and Luo, L. An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization. AISTATS, 2024.

* [13] Khaled, A. and Jin, C. Faster federated optimization under second-order similarity. ICLR, 2023.

* [14] Ene, A. and Le Nguyen, H. Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence. AAAI, 2022.

* [15] Jin, C., Netrapalli, P. and Jordan, M. What is local optimality in nonconvex-nonconcave minimax optimization? ICML, 2020.

* [16] Yang, J., Kiyavash, N. and He, N. Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems. NeurIPS, 2020.

* [17] Tian, Y., Sun, Y. and Scutari, G. Achieving linear convergence in distributed asynchronous multi-agent optimization. IEEE Transactions on Automatic Control, 2020.

Meta-review: 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.
Decision: Accept (poster)