On the Convergence of Inexact Gradient Descent With Controlled Synchronization Steps

1 On the Convergence of Inexact Gradient Descent with Controlled Synchronization Steps Sandushan Ranaweera, Chathuranga Weeraddana, Prathapasinghe Dharmawansa, and Carlo Fischione Abstract—We develop a gradient-like algorithm to minimize a sum of peer objective functions based on coordination through a peer interconnection network. The coordination admits two stages: the first is to constitute a gradient, possibly with errors, for updating locally replicated decision variables at each peer and the second is used for error-free averaging for synchronizing local replicas. Unlike many related algorithms, the errors permitted in our algorithm can cover a wide range of inexactnesses, as long as they are bounded. Moreover, we do not impose any gradient boundedness conditions for the objective functions. Furthermore, the second stage is not conducted in a periodic manner, like many related algorithms. Instead, a locally verifiable criterion is devised to dynamically trigger the peer-to-peer coordination at the second stage, so that expensive communication overhead for error-free averaging can significantly be reduced. Finally, the convergence of the algorithm is established under mild conditions. Index Terms—Distributed optimization, inexact algorithms I. INTRODUCTION GRadient descent and its variants often lend themselves fully amenable to parallel and distributed algorithms, which are highly desirable in large-scale optimization problems [1]. As a result, solution methods for many problems of recent interest are predominantly based on such gradient-like algorithms [2]–[14]. Broadly speaking, those algorithms developments are twofold [15]: a) a federated setting where a central controller (CC) intervenes for decision variable update [2]–[8]; b) a peer-to-peer (PP) setting where subsystems (SSs), each with its replicated decision variable, perform locally the update through some peer interconnection network, often modeled by a connected graph [9]–[14]. In this setting, the algorithm relies on neighbors specified by the graph and does not rely on a CC like in the federated setting. As such, it appears that PP setting is more appealing than the CC setting due to many reasons, such as higher scalability and inherently decentralized collection of big data sets, among others [1], [15]. In the context of a PP setting, a more fundamental concern is that the distributed algorithms usually undergo inevitable inexact conditions, e.g., unreliable and often limited communication capabilities [1], [15], [16]. Thus, unlike the inexactnesses under CC settings [17]–[22], those under PP settings influence the optimality, convergence, and effective implementation of algorithms. Consequently, there is an appeal to design effective algorithms under PP setting [23]–[33]. S. Ranaweera (e-mail: [email protected]g) and P. Dharmawansa (email: [email protected]) are with the Dept. of Electronic and Telecom. Eng., University of Moratuwa, Sri Lanka. C. Weeraddana (e-mail: Chathuranga.W[email protected]) is with the Faculty of Information Technology and Electrical Eng., University of Oulu, Finland. C. Fischione (e-mail: [email protected]) is with the School of Electrical Eng. and Computer Science, KTH Royal Institute of Technology, Sweden. Algorithms in [23]–[28] are based on distributed subgradient methods due to [13]. Some of these methods consider quantization models [23]–[25] and others consider eventtriggered models [26]–[28], so as to reduce the communication burden between SSs. The gradient boundedness of underlying objective functions, although a restriction, has been considered in [23]–[28], a technical assumption that enables convergences. The errors introduced in [23]–[28] can be viewed as controllable, in the sense that they are at the disposal of the algorithm. For example, quantization models in [23], [25] are chosen to be unbiased, a favorable condition for convergence. However, a peer interconnection network can often admit errors that are not at the disposal of the algorithm, e.g., wireless links [34, § 9], limiting the applicability of developments in [23]–[28] Works in [29]–[33] rely on PP coordination to constitute a gradient, in contrast to common federated settings where primal variables are coordinated instead. Then the resulting gradients are for updating their locally replicated decision variables. They are persuaded again under quantization settings (e.g., [29], [30]) and event-triggered settings (e.g., [31], [32]). Hybrid variants have also been considered by some authors, e.g., [33]. Similar to the developments noted in the preceding discussion, errors introduced in [29]–[33] are also controlled by the algorithms. For example, the quantization models in [29] and [30] are chosen so that the errors are diminishing and unbiased, respectively. Moreover, the authors in [31], [33] have specific impositions on the gradient boundedness. It is worth noting that many algorithms in either of the setting federated or PP (e.g., [6]–[8], [31]–[33]) have considered an averaging step performed at periodic or predefined epochs to enable the consistency of the locally replicates decision variables. Depending on the context, this entails periodic communication through the CC or through the PP interconnection network. From a communication overhead point of view, however, such an overhead for periodic communication seems like a restriction. This may be avoided by dynamically choosing the averaging epochs for synchronization. In this paper, we develop an algorithm that relies on PP coordination to constitute a gradient for updating locally replicated decision variables associated with a problem of minimizing the sum of peer objective functions. The algorithm iterates two stages. The first is used to exchange gradients possibly with errors. We have no restrictions on the errors of local gradient estimates, except that they are bounded. As a result, our modeling can handle errors beyond those of classic quantization models with restrictions, such as diminishing and unbiasedness. For instance, a cheap low-bit quantization can be used throughout the algorithm iterates under the first arXiv:2208.07797v4 [math.OC] 31 May 2023 2 stage. The second stage is used to error-free averaging for synchronizing local replicas. In this respect, unlike other related algorithms, we do not rely on periodic communication over the PP network. Instead, a locally verifiable criterion is devised to dynamically trigger the averaging step, only when necessary. This has the advantage of minimizing expensive communication overhead. Throughout this paper, we consider the PP network to be fully connected. 1Subsequently, the convergence of the algorithm is established and is shown to be linear. II. PROBLEM FORMULATION Consider Npeers or subsystems which solve the problem minimize f(x) = PN i=1 fi(x)(1) where x∈Rnand fi:Rn→R,i∈ N ≜{1, . . . , N}, be a function satisfying the following standard assumption: AS 1. The objective function fi,i∈ N, is strongly convex with constant ℓi>0and is Li-smooth, i.e., ∇fiis Lipschitz continuous with the constant Li>0. A commonly used iterative algorithms for solving problem (1) is the gradient descent (GD) algorithm x(k+1) = x(k)−γPN j=1 ∇fjx(k), where k∈Z+≜{0,1,2, . . .}is the iteration index and γis the step size. In contrast, here we assume a setting where each subsystem (SS) iperforms locally the variable GD update of its own copy x(k+1) iof x(k+1). This setting facilitates a distributed implementation of GD and thus each SS irelies on a communication with SS jto get a rough measurement of ∇fjx(k) jas specified below: AS 2. ∀i, j ∈ N, s.t. i=j, gradient measurement h(k) ij ∈Rn received by i-th SS from j-th SS at k-th iteration is given by h(k) ij =∇fjx(k) j+ϵ(k) ij (2) where ϵ(k) ij ∈Rnis a error such that ||ϵ(k) ij || ≤ ϵwith || · || denoting the Euclidean norm. The parameters ϵ(k) ij model measurement errors, noises, quantization errors2due to compression, among others. However, note the upper bound condition on ϵ(k) ij in AS 2, where ϵcan be thought of as the worst-case characteristic of errors throughout the algorithm. Under AS 2, the gradient ∇fx(k) i is distorted, which in turn admits the following iterate: x(k+1) i=x(k) i−γPN j=1 h(k) ij , i ∈ N.(3) Strictly speaking, the local variables updates should be consistent in the sense that ∀k∈Z+,∀i, j ∈ N,x(k) j=x(k) i. However, (3) with distinct SSs do not admit at least a weaker form of the consistency, called synchrony given by ∀i, j ∈ N, i =j, x(m) j=x(m) i(4) where mis an iteration index of practical interest, e.g., the iteration index at the termination. Thus, the main challenge in 1An extension to an arbitrary graph is possible with an additional assumption on the gradient boundedness. The details are provided in the Appendix. 2cf. [19, Definition 2] for such a quantization that yield an error as in AS 2. this research is to establish the convergence properties of (3), while maintaining the synchrony. 3This challenge is taken up next, where the iterate (3) is integrated with potential SS coordination to yield an algorithm with guaranteed convergence. III. ALGORITHM DEVELOPMENT Let us first focus on establishing the evolutionary characteristics of (3) to set the stage for our subsequent developments. A. Evolutionary Characteristics of (3) From (3), (2), together with some standard algebraic manipulations as shown in the Appendix, it can be shown that, under AS 1, AS 2 and for γ∈(0,1/PN j=iLj], ∥∇fx(k) i−h(k) i∥ ≤ 2ϵN (k+ 1/2) , i ∈ N (5) where h(k) i≜PN j=1 h(k) ij . The inequality (5) indicates that, in the worst case, the norm of the difference between ∇fx(k) i and its local representation h(k) idiverges as k→ ∞. Thus, it is of paramount importance to control such growth for establishing convergence of iterates of the form (3). To this end, it is customary to rely on SS coordination possibly through an error-free communication medium. However, error-free communications are usually more expensive. Therefore, unlike the commonly considered periodic SS coordination [33], we seek to reduce the communication overhead by dynamically choosing the coordination epochs, so as to make it still possible to ensure convergences of the underlying sequences. As such, we consider a relative deviation of the gradient of the objective function fand its measurement from the standpoint of ith SS, i.e., e(k) i≜∥∇fx(k) i−h(k) i∥/∥∇fx(k) i∥, i ∈ N. Intuitively, when e(k) iis sufficiently small, the influence of errors ϵ(k) ij on (3) becomes relatively insignificant. On the other hand, when e(k) iis sufficiently large, the consequences become more detrimental, and (3) may evolve anomalously. Thus, to circumvent such anomalies, the objective is to start with synchrony [cf. (4)] at k= 0 and to perform iterate (3) as long as e(k) iis sufficiently small, for otherwise to trigger SS coordination. As a result, the iterates (3) at each SSs might tend to evolve in a meaningful direction. Let us next discuss how the preceding concept can be integrated into devise our algorithm. In this respect, the most crucial step is to identify an epoch at which the SS coordination is to be triggered. In other words, each SS needs a locally verifiable characterization of the iterates kfor which e(k) iis sufficiently small, despite the dependence of e(k) ion global information ∇f·. As such, we rely on the condition k≤r∥h(k) i∥/(2ϵN)−1/2 =⇒e(k) i≤r/(1 −r)(6) where r∈(0,1) is a design parameter, suitably chosen based on the strong convexity constants and the Lipschitz constants of the objective functions. The condition (6) follows from (5), together with that ∥h(k) i∥−∥∇fx(k) i∥ ≤ ∥∇fx(k) i−h(k) i∥. 3Under imperfect conditions, iterates of the form (3) are commonplace in many distributed algorithms such as primal or dual-decomposition methods, among others, see e.g., [12] and references therein. 3 Thus, the SSs perform the iterate (3) independent of each other, as long as, for all i∈ N,k≤r∥h(k) i∥/(2ϵN)−1/2, and is referred to as IndComp. If k > r∥h(k) i∥/(2ϵN)−1/2 for at least one SS, SSs communicate with others to average their local copies x(k) i, which is referred to as the intermittent synchronization (IntSync). IntSync is performed through an error-free communication system. Having presented the evolutionary characteristics of (3), we are now ready to propose our new algorithm. B. Algorithm and Its Convergence Analysis The two stages IndComp and IntSync are implemented in an iterative manner to yield the following algorithm. Algorithm 1 Inexact GD with IndComp−IntSync Input: x(0) j=x(0) i∀i, j ∈ N,ϵ≥0,r∈(0,√ℓ/(√L+ √ℓ)),s= 0, k = 0 1: repeat 2: repeat 3: ∀i∈ N, compute x(s+k+1) ifrom (3), k←k+ 1 4: until ∃i∈ N, k −1> r∥h(s+k−1) i∥/(2ϵN)−1/2 5: if k= 1 then 6: ∀i∈ N,x(s+k−1) i←1 NPN j=1 x(s+k−1) j 7: s←s+k−1,k←0 8: else 9: ∀i∈ N,x(s+k) i←1 NPN j=1 x(s+k) j 10: s←s+k,k←0 11: end if 12: until a stopping criterion true It is worth emphasizing that the indices sand kof the algorithm have an important interpretation. The index salways represents an iteration at which the synchrony [see (4)] of the local copies of the decision variables is imposed, cf. step 7, step 10. The inner loop [cf. steps 2-4] always starts with synchrony. Thus, krepresents the local iteration index within the inner loop, which is reset every time the synchrony is imposed, cf. step 7, step 10. Consequently, s+kis simply the global iteration index of Algorithm 1. The following Proposition establishes the convergence of Algorithm 1. Proposition 1. Suppose AS 1, AS 2 hold. Let {x(k) i}k∈Z+, i∈ N, be the sequence of local copies of the decision variable generated by Algorithm 1. Then for γ∈(0,1/L] 1) lim sup k→∞ fx(k) i−f(x⋆)≤ϵ2N2/(2(ℓ−L¯r2)) 2) lim sup k→∞ ∥∇fx(k) i∥ ≤ pLϵ2N2/(ℓ−L¯r2) 3) lim sup k→∞ ∥x(k) i−x⋆∥ ≤ pLϵ2N2/(ℓ2−L¯r2ℓ) where L=PN j=1 Lj,ℓ= minj∈N ℓj,¯r=r/(1 −r), and x⋆= arg minxf(x). It is not difficult to see that the Proposition holds even if x(k) iis set as x(k)=1 NPN j=1 x(k) jfor all k∈Z+. Note that until the termination of the algorithm [cf. step 12], the inner loop is in either of the following states: 1) it repeats more than once 2) it repeats only once. Thus, the proof of the Proposition is simply based on the characterization of the evolution of the sequence {fx(s+k+1) i−fx⋆}when the algorithm is in either of the states. To this end, we shall require the following results, the proofs of which are given in the Appendix. Lemma 1. Let AS 1, AS 2 hold, s∈Z+be any iteration index at which synchrony is imposed, i∈ N, and r∈(0,1). Moreover, suppose the inner loop of Algorithm 1 repeats for iteration indices ¯ k∈ {s, s + 1, . . . , s +κ}, for some κ≥2. Then for k∈ {0,1, . . . , κ −1} fx(s+k+1) i−fx⋆≤qfx(s+k) i−fx⋆(7) where q= (1+γL¯r2−γℓ)is a positive constant. Lemma 1 characterizes the evolution of the sequence {fx(s+k+1) i−fx⋆}when the algorithm is in states 1. Consequently, the recursive application of (7), together with the Jensen’s inequality yields fx(s+κ) i−fx⋆≤qκfx(s) i−fx⋆.(8) The evolution of the sequence {fx(s+k+1) i−fx⋆}when the algorithm is in state 2is established by the following result. Lemma 2. Let AS 1, AS 2 hold, s∈Z+be any iteration index at which synchrony is imposed, r∈(0,1), and i∈ N. Moreover, suppose the inner loop of Algorithm 1 repeats only once, where the iteration index is s. Then fx(s+1) i−fx⋆≤1−γℓfx(s) i−fx⋆+γϵ2N2 2. (9) The inequality (9) holds even if x(s+1) ifrom the inner loop of Algorithm 1 is set as x(s+1) i=1 NPN j=1 x(s+1) j. Finally, the following Lemma asserts that the algorithm necessarily switches to state 2from state 1. Lemma 3. Let AS 1, AS 2 hold. Moreover, suppose ∀i∈ N,r∥h(0) i∥ ≥ ϵN, and thus, the algorithm starts at state 1, where r∈(0,√ℓ/(√L+√ℓ). Then ∃¯s, ¯ k∈Z+such that Algorithm 1 switches to state 2from state 1, where ¯sis an iteration index at which the synchrony is imposed and ¯ kis a local iteration index within the inner loop. Having armed with the above results, we are now ready to give the proof of Proposition 1. Proof of Proposition 1. From Lemma 1 and (8), for any consecutive sequence of state 1, starting at some global iteration index n∈Z+and ending at n+k∈Z+, we have fx(n+k) i−fx⋆≤qkfx(n) i−fx⋆(10) ≤qkfx(n) i−fx⋆+γϵ2N2 2Pk−1 j=0 qj.(11) Similarly, recursively applying (9) in Lemma 2 for any consecutive sequence of state 2, starting at some global iteration index n∈Z+and ending at n+k∈Z+, together with that 1−γℓ ≤q, we again have an equivalent form of (11). 4 (a) Error Vs IntSync +IndComp (b) Error Vs IntSync Fig. 1: Comparison of error for different distortion levels (i.e, ϵ). Results are shown for ϵ= 0.01,0.1,1, and 10. Moreover, the algorithm necessarily switches to state 2from state 1,cf. Lemma 3. Thus, from (11), ∀k∈Z+, we have fx(k) i−fx⋆≤qkfx(0) i−fx⋆+γϵ2N2 2Pk−1 j=0 qj. Noting that q < 1, we take the limit as k→ ∞ to yield Part 1. Part 2 follows from Part 1 and [35, eq. 10, § 1.4]. Finally, Part 3 follows from Part 1 and [35, eq. 35, § 1.1]. IV. NUMERICAL RESULTS Let us first verify the convergence results of Proposition 1. To this end, we consider problem (1) with quadratic fis, i.e., fi(x) = xTBT iBix+cT ix, where BT iBi∈Sn ++,ci∈Rn, and Sn ++ is the positive definite cone. The entries of Bi and ciare generated from a normal distribution. Note that ℓiand Liare determined by Bi,cf. AS 1. We let N= 4, n= 10,γ= 1/(2L), and r= 0.03. Only the results related to Proposition 1-(1) is presented, since those related to Proposition 1-(2) and (3) behave similarly. For comparison, we consider two algorithms. The first one is the classic GD, i.e., Algorithm 1 with ϵ= 0 and r= 0. We also consider another algorithm which we refer to as inexactGD with distributed synchrony (IGDDS), i.e., Algorithm 1 with r= 0 and ∀i∈ N,ϵ(k) ij =ϵ(k) j[cf. (2)]. In this respect, the synchrony (4) holds for all k∈Z+and we have lim supk→∞ fx(k) i−f(x⋆)≤ϵ2N2/(2ℓ)[35], [36, § 4]. Figure 1(a) shows the error fx(s+k)−f(x⋆)vs global iteration index s+kfor different ϵ,cf. solid lines. Results are averaged over 1000 initializations x(0), whose entries are normally distributed. Plots agree with Proposition 1-(1), i.e., the smaller the ϵ, the smaller the error of the optimality. Results with IGDDS are given in non-solid lines. Convergence rates and the suboptimality obtained by Algorithm 1 and IGDDS seem almost identical. This is expected because the convergence rate of Algorithm 1, i.e., (1 −γL¯r2−γℓ)and that of IGDDS, i.e., (1 −γℓ)are almost identical when γL¯r2≪1−γℓ. This condition is always realizable in practice, e.g., we have γL¯r2= 0.0005 and 1−γℓ = 0.9986 in our simulation. A similar comparison holds for the suboptimality as well. Thus, results suggest that Algorithm 1 yields almost identical results to that of more constrained IGDDS. Since IGDDS is technically equivalent to Algorithm 1 with r= 0, error-free communication is needed in every iteration to yield synchrony (4). However, Algorithm 1 does not require synchrony in every iteration. Therefore, for a fair comparison of Algorithm 1 and IGDDS in terms of communication overhead, it is instructive to plot the error versus the number of IntSync steps m, where sm,m∈Z+is the iteration index of swithin Algorithm 1 at which the mth-synchrony is imposed. Figure 1(b) shows the error fx(sm)−f(x⋆)vs mwith Algorithm 1, see thick solid lines. Results related to IGDDS are also plotted, see the non-solid lines. Clearly, there is a shift of the plots with IGDDS towards the right relative to the plots with Algorithm 1. Therefore, for all considered ϵvalues, the number of IntSync steps mrequired to obtain a specified error with Algorithm 1 is smaller than with IGDDS. Moreover, if the number of IntSync steps mis fixed, the error with Algorithm 1 can be on the order of magnitude smaller than with IGDDS. This is useful in practice, because the cost of the error-free communication required for IntSync can be reduced with Algorithm 1 than with IGDDS. The benefits become greater as ϵdecreases. Finally, we plot results due to GD, see the thin solid line in Fig. 1(b). Results show that still the Algorithm 1 can benefit from less expensive IndComp steps. For example, in 150 IntSync steps, Algorithm 1 manages to yield an error significantly less than that from GD despite the value of ϵ. Clearly, GD outperforms Algorithm 1 if mis sufficiently large, since there are no inexactnesses. Thus, the results suggest if there is a choice for less expensive communication for IndComp, or a choice for allowing some inexactnesses, one can operate Algorithm 1 in a way there is a trade-off between the error and IntSync steps (m). V. CONCLUSION A gradient-like algorithm with guaranteed convergence has been developed to minimize a sum of peer objective functions through an interconnection network with multi-peer broadcast and multi-peer accumulation capabilities. Peer coordination can usually admit communications with bounded errors, however with some infrequent error-free synchronization epochs, which are dynamically triggered. Our algorithm can be attractive in many distributed applications, under inexact communication settings, such as decomposition with dualsubgradient methods and distributed learning systems with innetwork computing capabilities, among others. 5 APPENDIX A. Derivation of (5) Suppose AS 1 and AS 2 hold. Moreover, let γ∈ (0,1/PN j=iLj]. Then by recursively applying (3) followed by the use of the triangular inequality gives ∥x(k) i−x(k) j∥ ≤ 2ϵNγk, ∀i, j ∈ N.(12) From (2) and the gradient Lipshitz continuity of fis, it follows that ∥∇fjx(k) i−h(k) ij ∥ ≤ Lj∥x(k) i−x(k) j∥+ϵ. (13) Finally, (5) follows from (13) by noting that ∇fx(k) i= PN j=1 ∇fjx(k) j, the definition of h(k) i, (12), and γ≤ 1/PN j=iLj. B. Proof of Lemma 1 Without loss of generality we may assume s= 0. Now, one can bound f(x(k+1) i)as follows: fx(k+1) i≤fx(k) i+∇fx(k) iTx(k+1) i−x(k) i (L/2)∥x(k+1) i−x(k) i∥2(14) ≤fx(k) i−γ∇fx(k) iTh(k) i+(γ/2)∥h(k) i∥2(15) =fx(k) i−(γ/2)∥∇fx(k) i∥2 (γ/2)∥∇fx(k) i−h(k) i∥2(16) ≤fx(k) i+γ¯r2 2−γ 2∥∇fx(k) i∥2(17) ≤fx(k) i+ (γL¯r2−γℓ)fx(k) i−fx⋆(18) where ¯r=r/(1 −r). Here (14) follows from the descent lemma [37, Lemma 5.7], (15) follows from (3) and noting that γL ≤1, (16) follows from simple algebraic identities, (17) follows from (6), (18) follows from [35, Lemma 3, § 1.4] and [35, eq. 10, § 1.4] for bounding −∥∇fx(k) i∥2and ∥∇fx(k) i∥2, respectively. Now, subtracting fx⋆from the both sides of (18) yields the final result. C. Proof of Lemma 2 To begin with, let us bound f(x(s+1) i)as follows: fx(s+1) i≤fx(s) i−(γ/2)∥∇fx(s) i∥2 + (γ/2)∥∇fx(s) i−h(s) i∥2(19) ≤fx(s) i−γℓ fx(s) i−fx⋆+γϵ2N2/2 (20) where (19) is similar to (16) of the preceding lemma. (20) follows from [35, Lemma 3, § 1.4] for bounding −∥∇fx(s) i∥2 and from that ∥∇fx(s) i−h(s) i∥2≤ϵN, since the inner loop always starts from synchrony, cf. (5). Subtracting fx⋆from both sides yields (9). The latter part of the lemma is immediate from the Jensen’s inequality. D. Proof of Lemma 3 Suppose the algorithm remains in state 14without switching to state 2. For clarity, let s∈Z+and k∈Z+denote arbitrary iteration indices at which the synchrony is imposed and corresponding local iteration index within the inner loop, respectively. Thus, from Lemma 1 and (8), we have fx(s+k) i−fx⋆≤qs+kfx(0) i−fx⋆.(21) Consequently, bounding fx(s+k) i−fx⋆and fx(0) i− fx⋆using [35, Lemma 3, § 1.4] and [35, eq. 10 § 1.4] respectively, we have ∥∇fx(s+k) i∥2≤(L/ℓ)qs+k∥∇fx(0) i∥2.(22) Moreover, for r∈(0,√ℓ/(√L+√ℓ)), we have q∈(0,1). Thus, ∃s+k∈Z+such that guarantees 5 ∥∇fx(s+k) i∥< ϵN/¯r. (23) It holds that ∥h(s+k) i∥ ≤ ∥∇fx(s+k) i∥+∥∇fx(s+k) i−h(s+k) i∥(24) < ϵN/¯r+ 2ϵNk+ 1/2(25) <2ϵN(k+ 1/2)1/¯r+ 1= 2ϵN(k+1/2)/r (26) where (24) follows from triangular inequality, (25) follows from (23) and (5). The inequality (26) is the inner loop exit criterion [cf. step 4] which transfers the control of the algorithm to IntSync at steps 6-7 of the algorithm. From (8) it follows that the inequality (21) holds even after the synchrony at IntSync. Thus, by following arguments identical to that of (22) - (26), we conclude that the control of the algorithm is next transferred to IntSync at steps 9-10. That is, the previous inner loop has been repeated only once, which is a contradiction. Therefore, the algorithm must switch to state 2. E. Analysis with a General Peer-to-Peer Setting In § II and § III, we focused on a network that can be modeled using a fully connected graph. However, the mathematical derivations can be extended to a more generalized peer-to-peer network that is modeled using a connected graph. Therefore, communication need not be coordinated by a central controller like in a federated setting. In the sequel, the main points of the derivations and related results are discussed. Let us consider an arbitrary graph G(N,L), where N= {1,2, . . . , N}represents the set of subsystems (SSs) of problem (1). Moreover, Lrepresents a set of edges between SSs, where an edge is given by a pair (i, j),i, j ∈ N. The graph is considered to be undirected. In other words, (i, j)∈ L ⇐⇒ (j, i)∈ L. Communication from SS jto iis allowed if and only if there is a link (i, j)between the two nodes. We denote by Ni={j|(i, j)∈ L}, the set of 4More generally, the algorithm can be in a consecutive sequence of inner loops that are of state 1. 5To be precise s+k≥ln(ϵ2N2L∥∇fx(0) i∥2)−ln(¯r2ℓ) ln q, where ⌈.⌉is the ceiling function. 6 neighbours of the SS i. Furthermore, we denote by T(N,¯ L), a spanning tree of the graph Gwhere ¯ Ldenotes the set of edges in T. We also define Ti=j|(i, j)∈¯ L, the neighbors of the SS iin the spanning tree. Now, we note that the gradient measurement model in (2) is going to be modified as follows in the general setting: h(k) ij =∇fjx(k) j+ϵ(k) ij if (i, j)∈ L 0otherwise.(27) Consequently, it is immediate that   h(k) ij −∇fjx(k) j  =     ϵ(k) ij   if (i, j)∈ L   ∇fjx(k) j  otherwise. (28) It is worth highlighting that the generalized setting requires an additional assumption unlike the fully connected setting considered in § II and § III, which we will outline next. AS 3. The gradients ∇fis of the objective functions fi,i∈ N are bounded, i.e., ∥∇fi(x)∥ ≤ ζfor some ζ > 0for all x, i. Hence, from AS 2 and AS 3, together with (28), it is easily verified that   h(k) ij −∇fjx(k) j  ≤τ(29) where τ= max ϵ, ζ. Thus, the gradient measurement h(k) ij obeys the following remark: Remark 1. ∀i, j ∈ N, s.t. i=j, gradient measurement h(k) ij ∈Rnreceived by i-th SS from j-th SS at k-th iteration is given by h(k) ij =∇fjx(k) j+τ(k) ij (30) where τ(k) ij ∈Rnis a error such that ||τ(k) ij || ≤ τwith ||·|| denoting the Euclidean norm. Note that Remark 1 play the role of AS 2. Let us next outline the modified version of Algorithm 1. Algorithm 2 Inexact GD with IndComp−IntSync over a General Graph Input: x(0) j=x(0) i∀i, j ∈ N,τ≥0,r∈(0,√ℓ/(√L+ √ℓ)),s= 0, k = 0 1: repeat 2: repeat 3: ∀i∈ N, compute x(s+k+1) ifrom (3), k←k+ 1 4: until ∃i∈ N, k −1> r∥h(s+k−1) i∥/(2τN)−1/2 5: if k= 1 then 6: ∀i∈ N,x(s+k−1) i←1 NPN j=1 x(s+k−1) j▷ performed through T(G,¯ L). 7: s←s+k−1,k←0 8: else 9: ∀i∈ N,x(s+k) i←1 NPN j=1 x(s+k) j▷performed through T(G,¯ L). 10: s←s+k,k←0 11: end if 12: until a stopping criterion true Now, one can easily see that an identical result to Proposition 1 holds even in the general setting if AS 2 is replaced by Remark 1 above. More specifically, we have the following result: Proposition 2. Suppose AS 1, Remark 1 hold. Let {x(k) i}k∈Z+,i∈ N, be the sequence of local copies of the decision variable generated by Algorithm 2. Then for γ∈(0,1/L] 1) lim sup k→∞ fx(k) i−f(x⋆)≤τ2N2/(2(ℓ−L¯r2)) 2) lim sup k→∞ ∥∇fx(k) i∥ ≤ pLτ2N2/(ℓ−L¯r2) 3) lim sup k→∞ ∥x(k) i−x⋆∥ ≤ pLτ2N2/(ℓ2−L¯r2ℓ) where L=PN j=1 Lj,ℓ= minj∈N ℓj,¯r=r/(1 −r), and x⋆= arg minxf(x). REFERENCES [1] D. Bertsekas and J. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. MA: Athena Scientific, 1997. [2] J. Dean, G. Corrado, R. Monga, et al., “Large scale distributed deep networks,” Adv. Neural Inf. Process. Syst., vol. 25, F. Pereira, C. Burges, L. Bottou, and K. Weinberger, Eds., 2012. [3] T. Chilimbi, Y. Suzue, J. Apacible, and K. Kalyanaraman, “Project ADAM: Building an efficient and scalable deep learning training system,” Proceedings of the USENIX Symposium on Operating Systems Design and Implementation, pp. 571–582, Oct. 2014. [4] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas, “Communication-efficient learning of deep networks from decentralized data,” Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, A. Singh and J. Zhu, Eds., ser. Proceedings of Machine Learning Research, vol. 54, PMLR, 20–22 Apr 2017, pp. 1273–1282. [5] J. Koneˇ cn´ y, H. B. McMahan, D. Ramage, and P. Richt´ arik, “Federated optimization: Distributed machine learning for ondevice intelligence,” 2016. arXiv: 1610.02527. [6] A. Khaled, K. Mishchenko, and P. Richt´ arik, “First analysis of local GD on heterogeneous data,” 2019. arXiv: 1909.04715. [7] S. U. Stich, “Local SGD converges fast and communicates little,” 7th International Conference on Learning Representations, May 2019. [8] J. Wang and G. Joshi, “Adaptive communication strategies to achieve the best error-runtime trade-off in local-update SGD,” Proceedings of Machine Learning and Systems 1, 2019. [9] D. P. Palomar and Y. C. Eldar, Convex Optimization in Signal Processing and Communications. NY: Cambridge Univ. Press, 2010. [10] A. Nedi´ c, “Distributed gradient methods for convex machine learning problems in networks: Distributed optimization,” IEEE Signal Process. Mag., vol. 37, no. 3, pp. 92–101, May 2020. [11] L. Xiao, M. Johansson, and S. P. Boyd, “Simultaneous routing and resource allocation via dual decomposition,” IEEE. Trans. Commun., vol. 52, no. 7, pp. 1136–1144, Jul. 2004. [12] M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle, “Layering as optimization decomposition: A mathematical theory of network architectures,” Proc. IEEE, vol. 95, no. 1, pp. 255–312, Jan. 2007. [13] A. Nedi´ c and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Trans. Automat. Contr., vol. 54, no. 1, pp. 48–61, Jan. 2009. [14] A. S. Berahas, R. Bollapragada, and E. Wei, “On the convergence of nested decentralized gradient methods with multiple consensus and gradient steps,” IEEE Trans. Signal Process., vol. 69, pp. 4192–4203, Jul. 2021. 7 [15] J. Verbraeken, M. Wolting, J. Katzy, J. Kloppenburg, T. Verbelen, and J. S. Rellermeyer, “A Survey on distributed machine learning,” ACM Computing Surveys, vol. 53, no. 2, Mar. 2020. [16] P. Kairouz, H. B. McMahan, B. Avent, et al., “Advances and open problems in federated learning,” Foundations and Trends in Machine Learning, vol. 14, no. 1-2, Jun. 2021. [17] Y. Chen, R. S. Blum, M. Takac, and B. M. Sadler, “Distributed learning with sparsified gradient differences,” IEEE J. Sel. Top. Signal Process., vol. 16, no. 3, pp. 585–600, Apr. 2022. [18] S. Magn´ usson, C. Enyioha, N. Li, C. Fischione, and V. Tarokh, “Convergence of limited communication gradient methods,” IEEE Trans. Automat. Contr., vol. 63, no. 5, pp. 1356–1371, May 2018. [19] S. Magn´ usson, H. Shokri-Ghadikolaei, and N. Li, “On maintaining linear convergence of distributed learning and optimization under limited communication,” IEEE Trans. Signal Process., vol. 68, pp. 6101–6116, Nov. 2020. [20] A. Nedi´ c, A. Olshevsky, and M. G. Rabbat, “Network topology and communication-computation tradeoffs in decentralized optimization,” Proc. IEEE, vol. 106, no. 5, pp. 953–976, May 2018. [21] S. Magnusson, C. Enyioha, N. Li, C. Fischione, and V. Tarokh, “Communication complexity of dual decomposition methods for distributed resource allocation optimization,” IEEE J. Sel. Topics Signal Process., vol. 12, no. 4, pp. 717–732, Aug. 2018. [22] S. Khirirat, S. Magn´ usson, and M. Johansson, “Compressed gradient methods with Hessian-aided error compensation,” IEEE Trans. Signal Process., vol. 69, pp. 998–1011, 2021. [23] C. S. Lee, N. Michelusi, and G. Scutari, “Finite rate quantized distributed optimization with geometric convergence,” 52nd Asilomar Conf. Signals, Syst., Comput., Oct. 2018. [24] A. Nedi´ c, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis, “Distributed subgradient methods and quantization effects,” Proc. IEEE Conf. Decis. Control, pp. 4177–4184, Dec. 2008. [25] A. Koloskova, S. U. Stich, and M. Jaggi, “Decentralized stochastic optimization and gossip algorithms with compressed communication,” Proceedings of the 36th International Conference on Machine Learning, vol. 97, pp. 3478– 3487, Jun. 2019. [26] J. George and P. Gurram, “Distributed stochastic gradient descent with event-triggered communication,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 05, pp. 7169–7178, Apr. 2020. [27] X. Cao and T. Bas¸ar, “Decentralized online convex optimization with event-triggered communications,” IEEE Trans. Signal Process., vol. 69, pp. 284–299, 2021. [28] D. Jakoveti´ c, D. Bajovi´ c, N. Kreji´ c, and N. K. Jerinki´ c, “Distributed gradient methods with variable number of working nodes,” IEEE Trans. Signal Process., vol. 64, no. 15, pp. 4080–4095, Aug. 2016. [29] D. Alistarh, T. Hoefler, M. Johansson, S. Khirirat, N. Konstantinov, and C. Renggli, “The convergence of sparsified gradient methods,” Adv. Neural Inf. Process. Syst., vol. 31, pp. 5973–5983, 2018. [30] D. Alistarh, D. Grubic, J. Z. Li, R. Tomioka, and M. Vojnovic, “QSGD: Communication-efficient SGD via gradient quantization and encoding,” Adv. Neural Inf. Process. Syst., vol. 30, no. 1, pp. 1710–1721, Dec. 2017. [31] H. Yu, S. Yang, and S. Zhu, “Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 01, pp. 5693–5700, Jul. 2019. [32] F. Zhou and G. Cong, “On the convergence properties of a Kstep averaging stochastic gradient descent algorithm for nonconvex optimization,” IJCAI International Joint Conference on Artificial Intelligence, pp. 3219–3227, Jul. 2018. [33] C. Xie, S. Zheng, O. Koyejo, I. Gupta, M. Li, and H. Lin, “CSER: Communication-efficient SGD with error reset,” Adv. Neural Inf. Process. Syst., vol. 33, pp. 12 593–12 603, 2020. [34] A. Goldsmith, Wireless Communications. UK: Cambridge University Press, 2005. [35] B. T. Polyak, Introduction to Optimization (Translations Series in Mathematics and Engineering). NY: Optimization Software, Publications Division, 1987. [36] A. Ajalloeian and S. U. Stich, “On the convergence of SGD with biased gradients,” 2020. arXiv: 2008.00051. [37] A. Beck, First-Order Methods in Optimization (MOS-SIAM Series on Optimization). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017.