1
Decentralized Gradient Descent: Bottleneck Regimes and Budget Complexity
arXiv:2607.12172v1 [cs.DC] 13 Jul 2026
Nicolò Michelusi, Senior Member, IEEE
Abstract—Decentralized gradient descent (DGD) is widely used for solving distributed optimization problems over networks of agents. While its convergence properties are well understood, less is known about the communication and computation resources required to attain a prescribed accuracy. In this paper, we study DGD from a resource-aware perspective and characterize the communication-computation budget required to attain a target error level. We develop a bottleneck-centric framework in which different factors dominate the optimization dynamics at different error scales. Specifically, we identify operating regimes governed by initialization, objective heterogeneity and network connectivity, gradient noise, and communication noise. To capture these effects, we introduce two fundamental quantities: the gradient-Diversity-to-Network-connectivity Ratio (DNR) and the Gradient-to-Communication-noise Ratio (GCR). We show that these quantities determine the sequence of bottlenecks encountered during optimization and the corresponding budgetoptimal operating strategy. Using a multi-stage analysis, we derive optimal stepsize selections and explicit budget-complexity bounds that quantify the budget resources required to attain a prescribed accuracy. The resulting expressions reveal how the overall budget decomposes into contributions associated with successive bottlenecks and provide insight into the fundamental tradeoffs among objective heterogeneity, network connectivity, gradient noise, and communication noise.
I
I NTRODUCTION
Many emerging systems consist of large collections of interconnected devices that must collaboratively solve optimization problems using locally available data. Examples arise in machine learning, distributed inference, estimation, remote sensing, and multi-agent control, where the objective is to learn a common model or estimate a global parameter from information dispersed across the network [1]–[3]. In such settings, N devices seek to cooperatively solve N
1 X fi (x), x∈Rd N i=1
x⋆ = arg min
{P}
where fi : Rd 7→ R is a local objective function known only to node i. In machine-learning applications, fi typically represents the empirical loss associated with a local dataset, whereas in distributed estimation problems it quantifies the mismatch between local measurements and the underlying parameter of interest [4]. The challenge is to solve {P} efficiently despite distributed information and limited communication resources. In many applications, including swarms of uncrewed aerial vehicles operating in remote areas [5], solving {P} without N. Michelusi is with the School of Electrical, Computer and Energy Engineering, Arizona State University. This research has been funded in part by NSF under grant CNS-2129015.
centralized data aggregation is paramount [6]. Decentralized optimization algorithms, such as decentralized gradient descent (DGD) [7], [8], solve {P} by alternating between local computation and information exchange with neighboring nodes. Over the past decade, a large body of work has established convergence guarantees for DGD and its variants under a variety of assumptions on the objective functions and network topology [8], [9]. Subsequent works have investigated stochastic gradients [10], communication impairments [11]– [18], as well as communication-efficient schemes based on quantization and compression [19]–[21]. Collectively, these works have revealed the key role of objective heterogeneity, network connectivity, gradient and communication noises. While convergence rates are now relatively well understood, less is known about the communication and computation resources required to attain a prescribed accuracy. This question is becoming increasingly important in large-scale and resource-constrained systems, where communication latency, transmission energy, and computational costs may dominate the overall optimization process. A key observation is that reducing the optimization error is not equally difficult across all stages of the algorithm: when the error is large, local computation may suffice, whereas at higher accuracy levels other factors, such as objective heterogeneity, gradient noise, or communication noise, may become dominant. This suggests that the optimization process should be viewed as a sequence of stages, each governed by a different dominant factor and therefore requiring a different operating strategy. This observation motivates the bottleneck-centric perspective adopted in this paper. Rather than treating all error sources as simultaneously active throughout the optimization process, we identify the bottleneck governing convergence at each error scale and characterize the most cost-effective strategy for overcoming it. This viewpoint leads to a multistage formulation in which different bottlenecks become active at different stages of the optimization trajectory, giving rise to distinct operating regimes and fundamentally different budget scalings. Since the resulting budget-allocation problem is generally intractable, we instead seek a tractable characterization of the dominant cost components that determine the budget required to attain a prescribed accuracy. To this end, our analysis identifies two fundamental quantities governing the optimization dynamics: the gradient-Diversity-to-Network-connectivity Ratio (DNR) and the Gradient-to-Communication-noise Ratio (GCR). The former captures the tension between objective heterogeneity and network connectivity, whereas the latter captures the relative importance of gradient and communication noises. Together, these quantities determine which bottleneck
2
is active at a given error scale and therefore dictate the budgetoptimal operating mode and parameter selection. Building on this characterization, we derive explicit budget-complexity bounds that quantify the dependence of the required budget on the DNR, GCR, target accuracy, and noise levels, and reveal the contributions of successive bottlenecks. Figure 1 schematically summarizes the main budget-complexity characterization developed in this paper. More broadly, the proposed bottleneck-centric perspective opens a new direction for adaptive decentralized optimization frameworks. I-A
Related Work
Early works established convergence bounds for DGD under strongly convex and smooth objectives over connected networks, revealing the impact of objective heterogeneity and network topology on performance [7], [8]. Unlike centralized gradient descent, which converges linearly to the global optimum under strong convexity, DGD with a constant learning stepsize converges linearly only to a neighborhood of the optimum [8], [12]. This bias stems from the combination of objective heterogeneity and decentralized information exchange. To eliminate this bias, several works have considered decreasing learning stepsizes, under which the distance to the global optimum converges at a sublinear rate of O(1/t) [12]. These results reveal that, even in the absence of stochastic perturbations, objective heterogeneity and limited network connectivity fundamentally limit the convergence behavior of DGD. Several exact decentralized optimization methods, including EXTRA, exact diffusion, and gradient tracking [22]–[25], have been proposed to eliminate the heterogeneity-induced bias of DGD. These methods may improve convergence performance but require additional communication, memory, and computational resources. Several works have extended DGD to stochastic settings in which the exact local gradients are replaced by estimates obtained from minibatch sampling or noisy observations [10], [12], [26]. In terms of the root mean squared error (RMSE) between the iterates and the global optimum, gradient noise √ slows the convergence rate of DGD from O(1/t) to O(1/ t) in the strongly convex setting [27]. These results suggest that gradient noise may become the dominant limitation once the error is sufficiently small, thereby inducing a bottleneck distinct from that associated with objective heterogeneity and network connectivity. Another line of work has investigated decentralized optimization under imperfect or constrained communications, including link failures, channel noise, fading, interference, unreliable links, rate-constrained networks, and quantized communications [11], [13]–[15], [17], [19]. Unlike gradient noise, communication noise directly affects the consensus process itself, creating a tradeoff between information exchange and noise accumulation, typically controlled via a consensus stepsize [12], [13], [19], [28]. As a result, communication noise leads to a more severe degradation of the √ convergence behavior, yielding an RMSE decay of O(1/ 4 t) [12], [19].
This suggests that communication noise may eventually become the dominant bottleneck limiting further error reduction. Communication-efficient decentralized optimization has also been studied through quantization, compression, and related techniques [21], [29]–[31]. While these methods reduce communication overhead and can preserve favorable convergence guarantees, they primarily focus on algorithm design rather than on characterizing the budget implications of different bottlenecks. The communication-computation tradeoff in decentralized optimization has also been recently investigated through multiconsensus and nested DGD methods [32]–[34]. These approaches perform multiple consensus and/or gradient updates within each iteration to improve convergence. Their analyses demonstrate that the balance between communication and computation can significantly affect the efficiency of decentralized optimization and that increasing the amount of communication may substantially accelerate convergence. However, these works focus on the design and analysis of specific algorithmic architectures and do not explicitly characterize how the communication-computation budget should evolve as different impairments become active throughout the optimization process. Taken together, the above works suggest that different impairments may dominate the optimization dynamics at different error scales. However, existing analyses largely focus on a specific impairment or algorithmic enhancement. In contrast, we develop a bottleneck-centric framework that characterizes how different bottlenecks become active throughout the optimization process and how they jointly determine the budget required to attain a prescribed accuracy. I-B
Contributions
The main contributions of this paper are summarized as follows: • We develop a resource-aware, bottleneck-centric framework for decentralized optimization and introduce a multi-stage formulation that partitions the optimization trajectory into successive error scales. • We introduce two fundamental quantities, the gradientDiversity-to-Network-connectivity Ratio (DNR) and the Gradient-to-Communication-noise Ratio (GCR), and show that they govern the sequence of bottlenecks encountered during optimization. • We identify the resulting bottleneck-dominated operating regimes and derive the corresponding budget-optimal operating mode and parameter selection across different error scales. • We derive explicit budget-complexity bounds that characterize the communication-computation resources required to attain a prescribed accuracy and quantify the contribution of successive bottlenecks to the overall budget. The remainder of this paper is organized as follows. Sec. II introduces the system model and the multi-stage formulation. Sec. III develops the single-stage optimization framework and identifies the operating regimes associated with different bottlenecks. Sec. IV derives budget-complexity bounds. Sec. V
3
Fig. 1: Representative optimization trajectory under the proposed bottleneck-centric framework (high-GCR, intermediate-DNR setting studied in Sec. IV-B.d). As the error decreases, the dominant bottleneck changes, leading to distinct operating regimes and budget contributions. Thresholds and budget contributions are shown up to multiplicative constants. See Table I for symbols.
presents numerical results, followed by concluding remarks in Sec. VI. Proofs of the main theoretical results are deferred to the Appendix.
I-C
Notation
xN,t
Bold lowercase and uppercase letters denote vectors and matrices, respectively. 0 and 1 are the all-zeros and allones vectors, respectively. Id is the d × d identity matrix. Vector/matrix transpose is denoted by (·)⊤ , ∥·∥ denotes the Euclidean norm, and ⊗ denotes the Kronecker product. The gradient of a function f is denoted by ∇f , and E[·] denotes expectation. The main symbols are summarized in Table I. II
controlling the incorporation of local gradient updates. Defining the stacked vectors x1,t ∇f1 (x1,t ) ϵc,1,t ϵg,1,t . . .. xt ≜ ... , ∇f (xt )≜ , ϵc,t ≜ .. , ϵg,t ≜ .. , .
S YSTEM M ODEL AND M ULTI -S TAGE F ORMULATION
We consider N spatially distributed devices cooperatively solving the optimization problem x⋆ = arg min F (x),
(1)
x∈Rd
PN where F (x) ≜ N1 i=1 fi (x) is the global objective, fi : Rd 7→ R denotes the local loss function of node i, known only to node i. The nodes solve (1) via decentralized gradient descent (DGD) over a communication graph. Let Ni denote the set of neighbors of node i (including i itself), and wij be the corresponding mixing weights, with wij = 0 whenever j ∈ / Ni . At iteration t, node i updates its local parameter vector xi,t by forming a weighted combination of the received neighbor models using the corresponding mixing weights, corrupted by communication noise, while simultaneously computing a noisy local gradient. This process yields the update xi,t+1 =(1 − γt )xi,t + γt
N X
wij xj,t + ϵc,i,t
∇fN (xN,t )
ϵc,N,t
ϵg,N,t
the recursion (2) can be compactly expressed as xt+1 =(1 − γt )xt + γt [(W ⊗ Id )xt + ϵc,t ] − ηt (∇f (xt ) + ϵg,t ),
(3)
N ×N
where W = [wij ] ∈ R is the mixing matrix (see Assumption 2). In other words, DGD combines a consensus step (a weighted average of the models of the neighbors), via interagent model exchanges, controlled by a consensus stepsize γt , with a local gradient descent step, controlled by a learning stepsize ηt . Both communications and gradient computations are affected by noise, characterized in Assumption 3. Remark 1. We adopt an abstract model of the communication channel, captured by the weight matrix W and the communication noise ϵc,t . For instance, in quantized DGD [19], W is typically constructed using Metropolis-Hastings weights [35], with neighbors defined by physical proximity. In this setting, ϵc,t corresponds to the error induced by dithered quantization. In DGD with link failures [12], [16], W admits a similar interpretation, while ϵc,t captures the mismatch between the instantaneous link realizations (successful or failed transmissions) and their average success probabilities. In non-coherent over-the-air DGD [13], [14], mixing occurs directly over the wireless channel by exploiting its average energy superposition property. In this case, W is dictated by average path loss conditions, whereas ϵc,t arises from channel fading, non-coherent signal superposition, receiver noise, and interference.
j=1
− ηt (∇fi (xi,t ) + ϵg,i,t ), ∀i,
(2)
where: ϵc,i,t denotes the communication noise affecting the aggregation step; ϵg,i,t denotes the noise injected during gradient computation, e.g., due to minibatch sampling; γt ∈ [0, 1] is the consensus stepsize, controlling the rate of information diffusion across the network; ηt ≥ 0 is the learning stepsize,
We assume that both communication and gradient computation consume resources, such as latency, energy, or a combination thereof, and therefore associate a cost with each operation. At each iteration, the network selects an operating mode specifying whether communication, computation, or both are performed. All modes are described by the unified recursion (3), obtained by appropriately activating or suppressing its
4
TABLE I: Summary of symbols
Symbol Definition µ strong-convexity parameter (Assumption 1) L smoothness parameter (Assumption 1) κ condition number L/µ N number of agents σc2 communication noise variance bound (Eq. 3 & Assumption 3) σg2 gradient noise variance bound (Eq. 3 & Assumption 3) DNR gradient-Diversity-to-Network-connectivity Ratio (Eq. 18) GCR Gradient-to-Communication noise Ratio (Eq. 19) Φ stage-wise error decay factor (Eqs. 23 & 34) bdgd budget cost of Full DGD iteration bg budget cost of Local SGD iteration
Symbol Definition x⋆ global optimum (Eqs. 1 & 15) xloc local minima (Eqs. 13 & 14) xt iterate at time t (Eq. 3) W mixing matrix (Eq. 3 & Assumption 2) Et root mean squared error at time t (Eq. 6) ε target error for the optimization problem (Eq. 5) Eloc distance between local & global optimal (Eq. 16) E(s) error bound at the start of stage s (Eq. 8) ηt , η(s) learning stepsize at time t or stage s (Eqs. 3 & 10) γt , γ(s) consensus stepsize at time t or stage s (Eqs. 3 & 10) δ(s) number of iterations of stage s (Eq. 7)
communication and computation components:
Directly solving (5) is generally intractable because the exact RMSE Et cannot be characterized in closed form as a function of the decision variables ηt , γt and the horizon T . Rather, it depends on the optimization dynamics determined by the objective functions, network topology, noise statistics, and stepsize schedule. We therefore analyze a computable upper bound Et ≤ Ēt . Unlike the exact RMSE, Ēt admits an explicit characterization in terms of the problem parameters, including the strong convexity and smoothness constants (Assumption 1), network connectivity (Assumption 2), initialization error, objective heterogeneity, noise statistics (Assumption 3), and the stepsize schedule. Moreover, Ēt provides a rigorous performance guarantee, ensuring that the actual RMSE Et remains below the prescribed bound. Nevertheless, even after replacing Et by Ēt , the resulting budget-allocation problem remains analytically intractable. The bound Ēt depends on the entire optimization trajectory, so decisions made at a given iteration influence all future rounds, resulting in a highly coupled dynamic optimization problem. A key observation is that the error typically evolves gradually, implying that the quantities governing convergence vary only slowly over time. Consequently, the budget-optimal communication-computation tradeoff is expected to remain nearly constant over a range of iterations. This observation suggests a multi-stage formulation. Rather than adapting the algorithm at every iteration, we partition the optimization trajectory into stages associated with different error scales. Within each stage, the error is allowed to vary only by a prescribed factor, while the communication and learning stepsizes remain fixed. The algorithm parameters are updated only when the error has decreased sufficiently to alter the dominant factors governing the convergence behavior. This approximation makes the design problem tractable while preserving the dominant mechanisms that determine the budgetoptimal strategy. Specifically, we partition the optimization horizon into S stages. The sth stage starts at iteration ks , with k0 = 0 for the initial stage s = 0, and has duration δs , so that the next stage starts at iteration
•
Local SGD (γt = 0): In this case, the update reduces to xt+1 = xt − ηt ∇f (xt ) − ηt ϵg,t ,
(4)
i.e., nodes perform a local gradient descent step without communication. The cost of this operation is denoted by bg . • Consensus (ηt = 0): In this case, the update becomes xt+1 = (1 − γt )xt + γt (W ⊗ Id )xt + γt ϵc,t , corresponding to one consensus round without a local gradient step, with cost bc . • Full DGD (ηt > 0 and γt > 0): In this case, the update includes both gradient computation and communication. The associated cost is denoted by bdgd . For example, if the cost represents latency, then bdgd = max{bc , bg } since communication and computation can be executed in parallel with DGD. On the other hand, if the cost represents energy consumption, then bdgd = bc + bg , due to the overall additive contribution of computation and communication energy costs. More generally, we assume that bdgd ≥ max{bc , bg }. The network is given a target accuracy level ε. During the optimization process, the network scheduler1 selects at each iteration one of the operating modes described above, together with the corresponding communication and learning stepsizes. The objective is to attain the prescribed accuracy using the minimum cumulative budget, leading to the optimization problem min
−1 {γt ≥0, ηt ≥0}T t=0 , T ≥0
T −1 X
bt
s.t.
ET ≤ ε,
(5)
t=0
where bt is the cost incurred at iteration t, determined by the selected operating mode, T is the total number of iterations, and p Et ≜ E[∥xt − x⋆ ∥2 ] (6) denotes the root mean squared error (RMSE) between the iterates at time t and the global optimum x⋆ ≜ 1N ⊗ x⋆ . In other words, we seek the most budget-efficient path to a target accuracy level ε. 1 The scheduler is introduced as a coordination abstraction. In practice, its decisions could be communicated over a low-rate, long-range control channel (e.g., an LPWAN [36]). Since the proposed framework updates the operating mode only at stage transitions, such coordination is required only infrequently.
ks+1 = ks + δs .
(7)
Let Φ > 1 denote the target error-reduction factor per stage. We define the error bound at the beginning of stage s as Eks ≤
E(0) ≜ E(s) . Φs
(8)
5
Accordingly, the objective of stage s is to reduce the error bound to E(s) ≜ E(s+1) . Φ Within stage s, the stepsizes are held constant, Eks+1 ≤
ηt = η(s) ,
γt = γ(s) ,
t = ks , . . . , ks+1 − 1,
(9)
(10)
and the operating mode, stepsizes (η(s) , γ(s) ), and stage length δs , are chosen to attain (9) with minimum budget cost. Since the error bound decreases only from E(s) to E(s) /Φ during a stage, the optimization process remains within the same error scale. Consequently, the relative importance of initialization, objective heterogeneity, limited network connectivity, and noise is expected to remain nearly unchanged, making parameter adaptation within the stage of limited benefit. The operating mode and stepsizes are therefore updated only at stage boundaries, where the error has decreased sufficiently for the optimal communication-computation tradeoff to change. In the remainder of the paper, we restrict attention to Local SGD (computation only) and Full DGD (simultaneous communication and computation), leaving the treatment of consensus-only rounds to future work. Since consensus-only updates primarily reduce disagreement rather than optimality error, their analysis requires explicitly tracking the coupled evolution of consensus and optimality errors. While of independent interest, this would substantially complicate the analysis and is therefore beyond the scope of the present work. To develop our multi-stage budget-limited framework, we begin by introducing several assumptions and definitions used in the analysis. II-A
Assumptions
We make the following assumption on each local function fi and the mixing matrix W. Assumption 1. Each local objective function fi : Rd → R is µ-strongly convex and has Lipschitz continuous gradients with parameter L (i.e., it is L-smooth), where 0 < µ ≤ L. It follows that F (x) is also µ-strongly convex and L-smooth, and the global minimizer x⋆ is unique. Assumption 2. The mixing matrix W ∈ RN ×N is entry-wise non-negative (W ≥ 0), symmetric (W⊤ = W), and doubly stochastic (W 1 = 1 and 1⊤ =1⊤ W). Furthermore, the communication graph induced by the positive entries of W is connected. By the Perron-Frobenius Theorem [37, Th. 8.4.4], the eigenvalues of W are real and satisfy 1 = λ1 > λ2 ≥ λ3 ≥ . . . ≥ λN ≥ −1. Let {Ft }t≥0 denote the natural filtration generated by the iterates and all randomness up to time t, i.e., Ft = σ(x0 , ϵc,0 , ϵg,0 , . . . , ϵc,t−1 , ϵg,t−1 ) . Note that xt is Ft -measurable, i.e., it is fully determined by the history up to time t, through the dynamics in (3). We impose the following assumptions on the noise processes.
Assumption 3. The communication and gradient noises satisfy: E [ϵc,t | Ft ] = 0, E ∥ϵc,t ∥22 | Ft ≤ σc2 ; (11) 2 2 E [ϵg,t | Ft ] = 0, E ∥ϵg,t ∥2 | Ft ≤ σg . (12) Here, σc2 and σg2 characterize the variance of the communication and computation noises, respectively. We do not require the communication and gradient noises to be conditionally uncorrelated, i.e., E ϵ⊤ g,t · ϵc,t | Ft may be nonzero. Unbiasedness of the gradient noise is guaranteed by a suitable minibatch sampling strategy. On the other hand, unbiasedness of the communication noise can be achieved by suitable design of the encoding scheme, e.g. via dithered quantization [19], and of the communication protocol (see for instance [13], [14]). Assumption 3 adopts a uniformly bounded noise variance model. Extensions to signal-dependent noise variance models (e.g., [12]) are left for future work. II-B Definitions We define the condition number of the optimization problem as κ ≜ L µ (≥ 1 since L ≥ µ). It measures the intrinsic difficulty of the optimization problem, with larger values corresponding to more ill-conditioned objectives, hence slower convergence of gradient-based methods. We define the local minimizer at each agent as xloc i = arg min fi (x).
(13)
x∈Rd
Under Assumption 1, each xloc exists and is unique. We stack i the local minimizers across the network into the vector ⊤ xloc = xloc⊤ , xloc⊤ , . . . , xloc⊤ . (14) 1 2 N We define the global optimum stacked over the network as x⋆ ≜ 1N ⊗ x⋆ .
(15)
We define the distance between local minima and the global optimum as Eloc ≜ ∥xloc − x⋆ ∥.
(16)
We define the gradient heterogeneity at the global optimum as ∥∇f (x⋆ )∥=
N X
∥∇fi (x⋆ )∥2
1/2
.
i=1
Notably, if all local minima coincide with the global optimum (i.e., xloc = x⋆ ), then Eloc = 0 and ∇fi (x⋆ ) = 0, ∀i, which implies ∥∇f (x⋆ )∥= 0. Hence, both Eloc and ∥∇f (x⋆ )∥ quantify the degree of objective heterogeneity across the network. They are closely related as2 µ Eloc ≤ ∥∇f (x⋆ )∥≤ L Eloc .
(17)
We define the gradient-Diversity-to-Network-connectivity Ratio (DNR) as 2κ ∥∇f (x⋆ )∥ 2 , (18) DNR ≜ L + µ 1 − λ2 2 Seen by using ∇f (xloc ) = 0, ∥∇f (x⋆ )∥= ∥∇f (x⋆ ) − ∇f (xloc )∥, followed by strong convexity and smoothness.
6
where λ2 is the second-largest eigenvalue of the mixing matrix W (Assumption 2). The DNR captures the relative difficulty of mitigating objective heterogeneity (captured by ∥∇f (x⋆ )∥) through DGD updates across the network (captured by 1−λ2 ). Large values of DNR arise when objective heterogeneity is high, or the network is poorly connected (λ2 close to 1), making disagreement mitigation across agents more challenging. Furthermore, a higher condition number κ makes the problem harder to solve over a network, yielding larger DNR. Finally, we define the Gradient-to-Communication noise Ratio (GCR) GCR ≜
4σg2 . (L + µ)2 σc2
(19)
It compares the relative impact of stochastic gradient noise and communication noise on the evolution of the iterates. Large values of GCR indicate that gradient noise is relatively stronger than communication noise, whereas small values indicate a comparatively larger influence of the latter. The scaling factor 4/(L+µ)2 accounts for the effect of the learning and consensus stepsizes on the propagated noise. In particular, the ratio var(η ϵg,t )/var(γ ϵc,t ) coincides with the definition above when the stepsizes take their largest admissible values γ=1 and η=2/(L + µ), required for convergence of gradient descent with strongly convex objectives [12]. III
S INGLE -S TAGE B OTTLENECK A NALYSIS
With these definitions, we now analyze the convergence properties of a generic stage, in which the learning and consensus stepsizes are held fixed. These results are then combined in the multi-stage formulation developed in Sec. IV. To initialize the stage-wise recursion, we require a computable upper bound on the initial error, E0 ≤ E(0) , whose derivation is deferred to the Appendix. We therefore consider a generic stage s ≥ 0, beginning at iteration ks . The stage starts with error bound Eks ≤ E(s) and aims to reduce it to Eks+1 ≤ E(s) /Φ, with minimum budget cost. We analyze the Local-SGD and Full-DGD operating modes separately. III-A
Local SGD
When communication is disabled (γt = 0), the one-step update with fixed η reduces to xt+1 = xt − η∇f (xt ) − ηϵg,t . Since no information is exchanged among agents, each node optimizes its local objective independently. Consequently, if this mode is maintained, the algorithm converges toward the local minima xloc , yielding a residual error xloc − x⋆ due to objective heterogeneity. The following lemma bounds the RMSE after δ iterations of a Local-SGD stage with fixed learning stepsize. Lemma 1. Consider a Local-SGD stage with learning stepsize 0 ≤ η ≤ 2/(L + µ). After δ iterations, the RMSE satisfies p n η(κ + 1) δ √ σg , Eks +δ ≤ 3 max (1 − ηµ) E(s) , 2L
o (1 + (1 − ηµ)δ )Eloc . Proof. See Appendix B. This bound reveals that the error after δ rounds of Local SGD is the worst among three terms: 1) the term (1 − ηµ)δ E(s) , accounting for the impact of the initialization error of stage s; 2) the propagated gradient-noise term, ∝ σg , 3) the mismatch between local and global optima, Eloc , due to objective heterogeneity. The worst among these error terms acts as a bottleneck in the error dynamics. Reducing the error by a factor Φ: We wish to choose the stepsize η and the length δ of stage s, so that Eks +δ ≤ E(s) /Φ (the error is reduced by a factor Φ by the end of the stage) with minimum budget cost. Using the bound found above, it is sufficient to impose E(s) , (initialization constraint); (20a) (1 − ηµ)δ E(s) ≤ 3Φ p E(s) η(κ + 1) √ σg ≤ , (gradient noise constraint); (20b) 3Φ 2L E 1+ 1 Eloc ≤ (s) , (heterogeneity constraint); (20c) 3Φ 3Φ where we used (1 − ηµ)δ ≤ 1/(3Φ) from (20a) to simplify (20c). These constraints can be interpreted as follows: • The initialization constraint term determines how many local steps δ are required to diminish the effect of stage initialization below the required threshold (given η); • The gradient noise constraint, controlled by η, ensures that the accumulated gradient noise does not exceed the desired target; • The heterogeneity constraint captures the bias due to objective heterogeneity (mismatch between the local and global minimizers). It is feasible only if E(s) ≥ (3Φ + 1)Eloc . ln(3Φ) The constraint (20a) requires δ ≥ − ln(1−ηµ) . From (20b), coupled with the stepsize condition of Lemma 1, we obtain ( ) E 2 2 (s) . (21) η≤ min 1 , µL L+µ 3Φσg
Finally, if (20c) is violated (E(s) < (3Φ + 1)Eloc ), then Local SGD is unfeasible. In this case, we need communication (studied in the next section) to mitigate the effect of objective heterogeneity and further drive the error down. The next stage starts at time ks+1 = ks + δ, with the corresponding error bounded by E(s+1) = E(s) /Φ. Under this stepsize design, we can also bound the error for the iterates t = ks . . . , ks+1 , by combining the Local-SGD bound (70) with (1 − ηµ)t−ks ≤ 1 as p η(κ + 1) √ Et ≤ E(s) + σg + 2Eloc 2L (3Φ)2 + 12Φ + 1 ≤ E(s) , (22) 3Φ(3Φ + 1) where we used (20b)-(20c) in the last inequality.
7
Minimum stage-wise budget cost: Under the condition E(s) ≥ (3Φ + 1)Eloc , reducing the RMSE by a factor Φ using Local SGD is feasible. The budget cost of performing δ local gradient steps is δ · bg . Hence, the budget in the sth stage is minimized by choosing δ as small as possible, yielding ln(3Φ) . (23) δ(s) ≜ − ln(1 − ηµ) Since this expression is decreasing in η, minimizing the budget cost amounts to maximizing η. Coupled with (21), this yields the optimal stepsize in stage s, ) ( E 2 2 (s) η(s) ≜ . (24) min 1 , µL L+µ 3Φσg Plugging this expression into (23), we obtain the minimum budget cost required to reduce the error by a factor Φ as ln(3Φ) ln(3Φ) bg · δ(s) = bg · ≤ bg · , (25) − ln(1 − η(s) µ) η(s) µ where we used − ln(1 − η(s) µ) ≥ η(s) µ in the last inequality. This analysis further reveals two regimes of interest. III-A.a Initialization-dominated regime of Local SGD: If 3Φσg E(s) ≥ max √ , (3Φ + 1)Eloc , (26) µL then both the gradient-noise and heterogeneity constraints (20b)-(20c) are inactive, and the optimal stepsize specializes 2 to η(s) = L+µ . Replacing this expression into (25), we bound the stage-wise budget cost as m l √ (27) bg · δ(s) ≤ bg · ln( 3Φ)(κ + 1) . This corresponds to the initialization-dominated regime, where the initial stage error E(s) is sufficiently large. In this regime, the contraction term (1 − ηµ)δ E(s) acts as the dominant factor governing error reduction, while gradient-noise and objective heterogeneity remain negligible relative to E(s) . Consequently, the behavior resembles that of noiseless centralized gradient descent: the error decreases geometrically, and the cost required to reduce the error by a constant factor Φ is independent of the gradient noise and heterogeneity metric. Instead, this cost grows proportionally to the condition number κ, capturing the difficulty of the optimization problem. III-A.b Gradient-noise-dominated regime of Local SGD: If the error bound satisfies 3Φσg √ > E(s) ≥ (3Φ + 1)Eloc , (28) µL then the gradient-noise constraint (20b) becomes active, and the optimal stepsize is 2µL E(s) 2 η(s) = . L + µ 3Φσg This regime is feasible as long as the interval in (28) is non-empty, i.e., 1 p σg > 1 + µLEloc , 3Φ corresponding to a setting where gradient noise is significant.
Plugging the expression of η(s) into (25), we bound the stage-wise budget cost as l σ 2 m g . (29) bg · δ(s) ≤ bg · 9Φ2 ln(3Φ) µE(s) This corresponds to the gradient-noise-dominated regime, where the noise term ∝ σg acts as the primary bottleneck in the error bound, while the heterogeneity term remains small relative to E(s) . Hence, the budget cost grows proportionally to the gradient noise variance σg2 . III-B
Full DGD
With both local computations and communications enabled and fixed stepsizes γ, η > 0, the update becomes xt+1 =(1 − γ)xt + γ(W ⊗ Id )xt − η∇f (xt ) + γϵc,t − ηϵg,t .
(30)
The following lemma bounds the RMSE after δ iterations of a Full-DGD stage. Lemma 2. Consider a Full-DGD stage with learning stepsize N) and consensus stepsize γ ∈ (0, 1]. After 0 < η ≤ 2−γ(1−λ L+µ δ iterations, the RMSE satisfies p n η(κ + 1) δ √ Eks +δ ≤ 4 max (1 − ηµ) E(s) , σg , 2L √ o γ κ+1 η L + µ√ σc , (1 + (1 − ηµ)δ ) DNR . (31) √ √ η γ 2 2L Proof. See Appendix C. Similar to the analysis of Local SGD, the above bound shows that the error after δ rounds of Full DGD is determined by the largest among four terms: 1) the term (1 − ηµ)δ E(s) , capturing the effect of the initial error at the beginning of stage s; 2) the propagated gradient-noise term, ∝ σg ; 3) the propagated communication-noise term, ∝ σc ; 4) the bias due to the mismatch between the fixed point x̂ which Full DGD aims to converge to and the desired global optimum x⋆ , scaling with the DNR. The largest of these contributions acts as a bottleneck in the error dynamics. Reducing the error by a factor Φ: We seek to choose the learning stepsize η, the consensus stepsize γ, and the length E δ of stage s, such that Eks +δ ≤ Φ(s) with minimum budget cost. Using (31), it suffices to impose E(s) (1 − ηµ)δ E(s) ≤ , (initialization constraint); (32a) 4Φ p E(s) η(κ + 1) √2L σg ≤ 4Φ , (gradient noise constrain); (32b) √ E(s) γ κ+1 √ σc ≤ , (comm. noise constraint); (32c) √ η 4Φ 2L E(s) 1 η L+µ √ DNR ≤ , (FP constraint). (32d) 1+ 4Φ γ 2 4Φ
8
Above, we used the bound (1 − ηµ)δ ≤ 1/(4Φ) implied by (32a) to simplify (32d). These constraints admit the following interpretation:
The initialization constraint determines the number of iterations δ required to sufficiently attenuate the effect of the initial stage error (for a given stepsize η). • The gradient-noise and communication-noise constraints √ limit the learning stepsize η and the stepsize ratio γ/ η, respectively, so that the propagated noise remains below the target error. • The fixed point (FP) constraint captures the intrinsic bias of DGD due to objective heterogeneity and limited connectivity, controlled by the stepsize ratio η/γ. •
cost, subject to constraints (36), are ( 3 E(s) κ √ , γ(s) ≜ min (κ + 1)2 4Φ2 (4Φ + 1)σc2 DNR ) √ 2 E(s) L 2κ E(s) 1 . , , κ + 1 8Φ2 σg σc κ + 1 4Φσc 2 1 η(s) = min L+µ
(
√κ
2
√
E(s)
√
(37)
2
, 2Φ(4Φ + 1)σc DNR | {z } (a) ) E 2 E(s) (s) √ 2µL , , 1 . (38) 4Φσg (4Φ + 1) DNR | {z } | {z } |{z} κ+1
(c)
(e)
(f)
Proof. See Appendix D. The next stage starts at time ks+1 = ks + δ, with the corresponding error bounded by E(s+1) = E(s) /Φ. Under this stepsize design, we can also bound the error for the iterates t = ks . . . , ks+1 using the Full-DGD bound (76) with (1 − ηµ)t−ks ≤ 1 as p √ √ η(L + µ) γ L+µ η σg + √ σc + (L + µ) DNR Et ≤ E(s) + √ γ 2µL 2ηµL 8Φ2 + 10Φ + 1 ≤ E(s) , (33) 2Φ(4Φ + 1) where in the last inequality we used (32b)-(32d). Minimum stage-wise budget cost: The budget cost of performing δ Full-DGD steps is δ·bdgd . Hence, minimizing δ·bdgd is equivalent to minimizing δ, yielding from (32a) ln(4Φ) δ(s) ≜ . (34) − ln(1 − ηµ) Since this expression is decreasing in η, minimizing the budget cost amounts to maximizing η with respect to (η, γ), subject to the constraints (32b)-(32d) and the stepsize conditions 0 < γ ≤ 1, 0 < η ≤
2 − γ(1 − λN ) , L+µ
(35)
required in Lemma 2. In the following, we impose slightly stronger conditions 0<γ≤
1 , 2
0<η≤
1 . L+µ
(36)
While the original constraints could be retained, they considerably complicate the analysis. The proposed conditions imply the original ones and are at most a factor 2 more conservative. Since smaller values of η and γ are often desirable in the presence of gradient and communication noise, this simplification incurs only a minor loss of generality while yielding a much cleaner analysis. The following lemma characterizes the budget-optimal learning and consensus stepsizes. Lemma 3. The budget-optimal learning and consensus stepsizes that guarantee Eks+1 ≤ E(s) /Φ with minimum budget
Plugging this expression into (34), we bound the minimum stage-wise budget cost as ln(4Φ) ln(4Φ) bdgd · δ(s) =bdgd ≤bdgd , (39) − ln(1 − η(s) µ) η(s) µ where we used − ln(1 − η(s) µ) ≥ η(s) µ in the last inequality. The learning stepsize expression in Lemma 3 reveals four operating regimes, depending on which term in the minimum is active, namely (a), (c), (e), or (f). Each regime is associated with a different bottleneck governing the convergence behavior, studied next. III-B.a Initialization-dominated regime of Full DGD: When E(s) is sufficiently large, term (f) becomes the smallest among the arguments of the minimum defining η(s) , yielding η(s) =
1 . L+µ
(40)
The activation of this regime requires that the remaining terms satisfy (a), (c), (e) ≥ (f) in (38). Solving these inequalities yields the following conditions on E(s) : √ √ κ + 1p 4 √ E ≥ Φ(4Φ + 1)σ 2 DNR, (41a) c (s) 4 κ √ 2 2Φσg E(s) ≥ √ , (41b) µL √ E ≥ (4Φ + 1) DNR. (41c) (s) Replacing (40) into (39), the stage-wise budget cost becomes bdgd · δ(s) ≤ bdgd · ⌈ln(4Φ)(κ + 1)⌉ . This corresponds to the initialization-dominated regime, in which the stage initialization error acts as the main bottleneck governing the error evolution. In this regime, the effects of communication noise, gradient noise, objective heterogeneity and network connectivity remain negligible relative to E(s) , and the convergence behavior is primarily dictated by the contraction induced by the gradient descent dynamics, captured by the condition number κ. In fact, the budget cost is independent of the noise parameters (σg and σc ) as well as the DNR.
9
III-B.b DNR-dominated regime of Full DGD: When E(s) is moderately large, term (e) becomes the smallest in (38), yielding the optimal learning stepsize as η(s) =
E(s) 1 √ . L + µ (4Φ + 1) DNR
(42)
By enforcing (a), (c), (f) ≥ (e) in (38), operating in this regime requires r 2 √ 3 (κ + 1) E(s) ≥ 2Φ2 (4Φ + 1)σc2 DNR, (43a) κ 2 8Φ2 σg 1 √ E(s) ≥ , (43b) 4Φ + 1 µL DNR √ E ≤ (4Φ + 1) DNR. (43c) (s) This regime is feasible provided that the interval defined by (43a)-(43c) is non-empty, yielding ϕ
µL DNR 1 ≥ , 2 σg min{GCR, 1}
(44)
where we defined the scaling factor ϕ≜
(4Φ + 1)2 ∈ [2, 3.125). 8Φ2
(45)
Replacing η(s) into (39), the stage-wise budget cost becomes ' & √ DNR . (46) bdgd · δ(s) ≤ bdgd · ln(4Φ)(4Φ + 1)(κ + 1) E(s) In this regime, the effects of both gradient and communication noises are small relative to E(s) . The convergence behavior is therefore governed by objective heterogeneity and network connectivity, whose combined effect is captured by the DNR. We thus refer to this regime as the DNR-dominated regime of Full DGD. Notably, the budget cost is not affected by the noise parameters σg and σc .
III-B.c Gradient-noise-dominated regime of Full DGD: When E(s) is moderately small, term (c) becomes the smallest in (38), yielding the optimal learning stepsize as 2L E(s) 2 η(s) = . (47) κ + 1 4Φσg By enforcing (a), (e), (f) ≥ (c) in (38), operating in this regime requires p E(s) ≥ (4Φ + 1) DNR/GCR, (48a) 2 σ2 8Φ 1 g √ E(s) ≤ , (48b) 4Φ + 1 µL DNR √ 2 2Φσg , (48c) E(s) ≤ √ µL which is feasible provided that √ µL DNR √ ϕ ≤ GCR min{ GCR, 1}, 2 σg
(49)
with ϕ defined in (45). Replacing η(s) into (39), the stage-wise budget cost becomes & ' κ + 1 σg 2 2 bdgd · δ(s) ≤ bdgd · 8Φ ln(4Φ) . (50) µL E(s) In this regime, gradient noise is the dominant bottleneck, whereas the effects of objective heterogeneity, communication noise, and network connectivity are comparatively small. We therefore refer to this regime as gradient-noise-dominated. As a result, the budget cost depends primarily on σg2 and is independent of σc and the DNR. III-B.d Communication-noise-dominated regime of Full DGD: When E(s) is small, term (a) becomes the smallest in (38), yielding the optimal learning stepsize as !2 2 √ E(s) κ 1 √ √ . (51) η(s) = L + µ κ + 1 2Φ(4Φ + 1)σc DNR By enforcing (c), (e), (f) ≥ (a), the conditions required to operate in this regime are p + 1) DNR/GCR, (52a) E(s) ≤ (4Φ r 2 √ 3 (κ + 1) 2Φ2 (4Φ + 1)σc2 DNR, E(s) ≤ (52b) κ √ √ κ + 1p 4 Φ(4Φ + 1)σc 2DNR. (52c) E(s) ≤ √ 4 κ Replacing η(s) into (39), we obtain the stage-wise budget cost as & ' (κ+1)3 σc2 DNR 2 2 bdgd ·δ(s) ≤bdgd 2Φ (4Φ+1) ln(4Φ) .(53) 4 κ E (s)
In this regime, the gradient-noise constraint becomes inactive, and the performance is instead limited by the interaction between communication noise and the DNR, which captures the combined effects of objective heterogeneity and network connectivity. Indeed, communication is the mechanism by which agents reconcile heterogeneous local objectives, so communication noise directly impairs this process. We therefore refer to it as the communication-noise-dominated regime of Full DGD. Accordingly, the budget cost is governed by σc2 and the DNR, while being independent of the gradient-noise level σg . IV
M ULTI -S TAGE B UDGET C OMPLEXITY
The previous section characterized the budget cost and stepsize design of a generic stage under both Local-SGD and FullDGD operations. We now leverage these stage-wise results to characterize the minimum communication-computation budget required to attain a prescribed accuracy by accumulating the contributions of the bottleneck-dominated regimes traversed during optimization. For illustrative purposes, we focus on the case where the initial error bound satisfies (26) and the target accuracy ε satisfies (52a)-(52c). More generally, the analysis extends directly to any initial error and target accuracy by simply omitting operating regimes that are never encountered.
10
Consider stage s, starting at iteration ks with error bound E(s) = E(0) Φ−s , where each preceding stage has reduced the error by a factor Φ. The first question is: given E(s) and the target error reduction by a factor Φ, which operating mode is most budget-efficient, and which regime can actually be encountered? The answer is given by the following lemma. Lemma 4. If E(s) > (3Φ+1)Eloc , then Local SGD is budgetoptimal. Otherwise, Full DGD is budget-optimal. Moreover, the initialization-dominated regime of Full DGD is never encountered. Proof. See Appendix E.
The intuition is that objective heterogeneity becomes relevant only when the error level is comparable to Eloc . When E(s) ≫ Eloc , the current error dominates the effect of heterogeneity, so communication provides little benefit and the lower-cost Local-SGD iterations are sufficient. As the error decreases toward Eloc , heterogeneity becomes the limiting factor, and communication is required to reconcile the local objectives and enable further progress toward the global optimum. At that point, Full DGD becomes the budget-optimal operating mode. Moreover, this transition implies that the initializationdominated regime of Full DGD is never encountered. By the time the algorithm enters the Full-DGD phase, the initialization error has already ceased to be the dominant limitation. Consequently, the Full-DGD phase can only traverse the DNR-, gradient-noise-, and communication-noise-dominated regimes. Lemma 4 therefore partitions the optimization process into two consecutive operating phases. Starting from E(0) satisfying (26), the algorithm first operates in the Local-SGD phase E ≤ (3Φ+1)Eloc . It then permanently for Sgd stages, until ΦS(0) gd switches to the Full-DGD phase, which continues for the remaining Sdgd stages, until the target accuracy ε is attained. The single-stage analysis of Sec. III further revealed that each operating phase may consist of multiple bottleneckdominated regimes. Within a given regime, the stage-wise budget follows a common scaling law, which remains valid until the error reaches the corresponding regime-transition threshold. The remaining task is therefore to accumulate the budget incurred across successive stages belonging to each regime. This is accomplished by Theorem 1 (Appendix F), which converts the stage-wise budget scaling into the total budget required to traverse a regime. The following corollary summarizes the qualitative implications of Theorem 1. Corollary 1. Consider a bottleneck-dominated regime spanning stages r = s, s + 1, . . ., in which the stage lengths satisfy −n δr = O(E(r) ), for some exponent n ≥ 0. Then, the cumulative budget incurred while traversing this regime, until the RMSE falls below a target level εth , satisfies ( O(ε−n n > 0, th ), B(εth ) = O(ln(E(s) /εth )), n = 0,
while the corresponding RMSE satisfies ( O(t−1/n ), n > 0, Et = O(e−ct ), n = 0, for some c > 0. Corollary 1 highlights the qualitative relationship between the stage-wise and global optimization problems. In particular, it shows how the stage-length scaling exponent n determines the budget complexity and convergence rate of each bottleneck-dominated regime. The exact quantitative analysis presented next is based on Theorem 1, which retains the explicit dependence on the DNR, GCR, target accuracy, and other problem parameters. We now characterize the total budget of the Local-SGD and Full-DGD phases. Each phase is analyzed by partitioning it into its constituent bottleneck-dominated regimes, applying Theorem 1 to each regime, and summing the resulting budget contributions. For each regime, the target accuracy εth corresponds to the error threshold at which the subsequent regime becomes active, while the stage-length scaling law, and hence the exponent n, is determined by the corresponding bottleneck. For the final regime, εth coincides with the overall target accuracy ε. In particular, applying this methodology to the FullDGD phase identifies the four DNR–GCR settings shown in Fig. 2, and characterizes the corresponding budget-complexity. For concreteness, we also provide explicit expressions for the √ representative choice Φ = 2. IV-A
Budget complexity of the Local-SGD phase
Recall that Local SGD remains budget-optimal as long as the error exceeds the threshold (3Φ + 1)Eloc (Lemma 4). By (80), the number of Local SGD stages is l m E(0) Sgd ≜ logΦ . (54) (3Φ + 1)Eloc Since E(0) satisfies (26), the algorithm initially operates in the initialization-dominated regime of Local SGD (Sec. III-A.a). Depending on the relative magnitude of the gradient-noise level and the heterogeneity threshold (3Φ + 1)Eloc , the optimization trajectory may subsequently enter the gradient-noisedominated regime (Sec. III-A.b) before transitioning to the Full-DGD phase. We then obtain two settings. IV-A.a Small-gradient-noise: This setting is characterized by 1 p σg ≤ 1 + µLEloc , 3Φ in which the gradient-noise level is small relative to the objective heterogeneity. The gradient-noise-dominated regime of Local SGD thus becomes infeasible. Consequently, throughout the entire Local-SGD phase the algorithm operates in the initialization-dominated regime (Sec. III-A.a) with a constant learning stepsize. The total budget incurred over the resulting Sgd stages can be obtained by applying Theorem 1 to the stage complexity −n bound (27). Specifically, comparing (27) with δr ≤ ⌈ν E(r) ⌉ √ in (81), we set n = 0, ν = ln( 3Φ)(κ + 1), and the target
11
error as εth = (3Φ + 1)Eloc , thus bounding the budget cost of the Local SGD phase via (82) as E(0) Bg ≲ 7.1 bg κ ln 0.27 loc E √ for the case Φ = 2, after using ⌈x⌉ ≤ 1 + x to bound Sgd in (54). Furthermore, Et can be bound via (84) with α ≈ 1.6 (cf. (22)), yielding t + 1 , (55) Et ≲ 1.6E(0) exp − 0.12 κ for t = 0, . . . , kSgd − 1. Thus, throughout the Local-SGD phase, the error decays geometrically, analogous to noiseless gradient descent on a strongly convex objective. As a result, the associated budget cost grows only logarithmically with the ratio E(0) /Eloc . The phase ends when the error reaches the heterogeneity threshold (3Φ + 1)Eloc . At this point, objective heterogeneity becomes an active bottleneck and communication becomes necessary for further error reduction. IV-A.b
Large-gradient-noise: This setting is characterized
by 1 p µLEloc . σg > 1 + 3Φ Thus, the algorithm first operates in the initializationdominated regime for Sinit stages, until the error falls below 3Φσ the threshold εth = √µLg given by (26). Similar to the previous setting, but with the target error εth in place of (3Φ + 1)Eloc , we bound the total budget cost incurred during the initialization-dominated regime as √µLE (0) bg · Sinit + logΦ (3Φ)κ ln , 3σg during which the RMSE exhibits the geometric decay in (55). The algorithm then enters the gradient-noise-dominated regime of Local SGD for the subsequent Sgnd stages, until the error falls below the threshold εth = (3Φ + 1)Eloc . Applying Theorem 1 to the stage complexity bound (29) in Sec. III-A.b, σ2 with n = 2 and ν = 9Φ2 ln(3Φ) µg2 , we bound the budget cost accumulated during the gradient-noise-dominated regime as σ 2 9Φ4 ln(3Φ) g bg Sgnd + 2 , (Φ − 1)(3Φ + 1)2 µEloc √ during which the RMSE decays as (Φ = 2 and α ≈ 1.6 from (22)) σg 1 Et ≲ 16.3 p , t = kSinit , . . . , kSgd − 1. µ t − kSinit + 1 Thus, after an initial geometric phase, √ the convergence behavior exhibits the characteristic O(1/ t) decay of stochastic gradient descent on strongly convex objectives [27]. In this regime, gradient noise constitutes the dominant bottleneck, and both the error and the budget cost scale with the gradient-noise variance. Combining the contributions of the two regimes yields the
Fig. 2: Classification of the four settings governing the Full-DGD phase as a function of the DNR-to-gradient-noise ratio and GCR. Each region corresponds to a distinct sequence of bottlenecks encountered during optimization, indicated below the setting label. The boundaries are determined by the setting conditions derived in Sec. IV-B.
total budget cost of Local SGD as √µLE h E(0) (0) Bg ≲ bg · 2.9 ln 0.27 loc + 4.2κ ln E 3σg σ 2 i g + 1.9 µEloc √ for Φ = 2, where we used Sgd = Sinit + Sgnd together with ⌈x⌉ ≤ 1 + x in (54). The Local-SGD phase terminates once the error falls below (3Φ + 1)Eloc . Beyond this point, objective heterogeneity becomes an active bottleneck, and local computation alone can no longer achieve the desired stage-wise error reduction. Communication is therefore required to reconcile objective heterogeneity, motivating the transition to the Full-DGD phase analyzed next. IV-B
Budget complexity of the Full-DGD phase
After the Sgd stages of Local SGD, the error satisfies EkSgd ≤ E(Sgd ) ≤ (3Φ + 1)Eloc . The algorithm then switches to Full DGD and continues until the target accuracy ε is reached, while traversing the DNR-, gradient-noise-, and communication-noise-dominated regimes (the initializationdominated regime is unfeasible, as shown in Lemma 4). The resulting behavior depends on the relative magnitudes of these bottlenecks, giving rise to four settings that partition the DNR–GCR parameter space into the four regions shown in Fig. 2, each associated with a distinct bottleneck sequence and budget-complexity characterization, analyzed next. We let Sdnr , Sgnd , and Scnd denote the numbers of stages spent in each regime, in order, equal to zero if the corresponding regime is infeasible or never reached. Since each stage reduces the error bound by a factor Φ, the total number of stages of the Full-DGD phase, Sdgd = Sdnr + Sgnd + Scnd , satisfies (see (80)) Φ(3Φ+1)Eloc Sdgd ≜ logΦ E(Sgd ) /ε ≤ logΦ , (56) ε where we used E(Sgd ) ≤ (3Φ + 1)Eloc and ⌈x⌉ ≤ 1 + x. The setting conditions presented below characterize the bottleneck structure of the Full-DGD phase in isolation. Since Full DGD is entered only after the Local-SGD phase has already reduced the error below (3Φ + 1)Eloc , some regimes
12
may become infeasible. For clarity, we discuss these additional feasibility conditions separately as a remark for each setting. IV-B.a Low GCR, intermediate DNR-to-gradient-noise ratio: This setting is characterized by GCR ≤ ϕ
1 µLDNR ≤ , 2 σg GCR
GCR < 1,
with ϕ defined in (45). In other words, the communication noise is large relative to the gradient noise (low GCR), while the DNR is of intermediate magnitude relative to the gradientnoise level. Under these conditions, it follows from (44) and (49) that both the DNR-dominated and gradient-noisedominated regimes are infeasible, i.e., Sdnr = Sgnd = 0. Consequently, the Full-DGD phase operates entirely in the communication-noise-dominated regime. Applying Theorem 1 to the stage complexity bound (53) in Sec. III-B.d, with (κ + 1)3 2 σc DNR, (57) κ and target error εth = ε, bounds the total budget Bdgd of the Full-DGD phase as σ 2 DNR Bdgd ≤ bdgd Scnd + ϕcnd κ2 c 4 , (58) ε √ 6 2 ln(4Φ) . Specializing to Φ = 2 and where ϕcnd ≜ 16Φ (4Φ+1) Φ4 −1 using (56), we obtain loc E σ 2 DNR Bdgd ≲ bdgd 5.8 + 2.9 ln + 3276κ2 c 4 . ε ε n = 4,
ν = 2Φ2 (4Φ + 1)2 ln(4Φ)
Applying (84) with n and ν as in (57) and α ≈ 1.65 (cf. (33)) yields s √ 4 σc2 DNR , (59) Et ≲ 15 κ t − ks + 1 √ for all t ≥ ks and s = Sgd . Thus, the error decays as O(1/ 4 t), matching the characteristic behavior of DGD with communication noise on strongly convex objectives [13]. In this case, σ 2 DNR the dominant contribution to the budget scales as κ2 c ε4 , dependent on both the communication-noise level, the DNR and the target accuracy, while remaining independent of the gradient-noise level σg . Notably, the quartic dependence on 1/ε implies that attaining high accuracy becomes increasingly expensive once communication noise becomes the dominant bottleneck. IV-B.b High DNR-to-gradient-noise ratio: This setting is characterized by √ µLDNR GCR ϕ ≥ , 2 σg min{GCR3/2 , 1} with ϕ defined in (45). In other words, the DNR is large relative to the gradient-noise level. Under this condition, the gradient-noise-dominated regime is unfeasible.3 Consequently, the Full-DGD phase consists of a DNR-dominated regime, 3 This can be seen by direct inspection of (44) and (49), for the cases
GCR ≥ 1 and GCR < 1 separately
followed by a communication-noise-dominated regime until the target accuracy ε is attained. Intuitively, objective heterogeneity and limited network connectivity initially constitute the dominant bottleneck, making the DNR the primary factor governing the convergence behavior. As the error decreases, the effect of communication noise eventually becomes dominant, causing the algorithm to transition to the communicationnoise-dominated regime. Specifically, the network remains in the DNR-dominated regime until the error reaches r 2 √ 3 (κ + 1) 2Φ2 (4Φ + 1)σc2 DNR, εth = κ as given by (43a).4 Comparing (46) in Sec. III-B.b with δr ≤ −n ⌈ν E(r) ⌉ in (81), we set √ n = 1, ν = ln(4Φ)(4Φ + 1)(κ + 1) DNR. (60) Substituting these quantities into (82), we bound the total budget accumulated until the error falls below εth as s ! DNR 3 2 bdgd Sdnr + ϕdnr κ , σc2 p 3 where ϕdnr ≜ ln(4Φ) Φ(4Φ + 1)2 . Furthermore, specializing Φ−1 (84) to n and ν as in (60) and α ≈ 1.65 √ (cf. (33)), yields, for ks ≤ t ≤ ks+Sdnr , s = Sgd , and Φ = 2, √ κ DNR Et ≲ 260 . (61) t − ks + 1 Thus, the O(1/t) error decay matches the characteristic behavior of noiseless DGD on strongly convex objectives [13]. In this regime, objective heterogeneity and limited network connectivity constitute the dominant bottleneck. Consequently, both the error and the dominant contribution to the budget cost scale with DNR, while remaining independent of the gradientnoise level σg . Notably, larger communication noise leads to an earlier transition to the communication-noise-dominated regime (higher εth ), hence the budget cost decreases with the communication-noise level σc . At this point, the network enters the communication-noisedominated regime of Full DGD, whose budget cost and error decay are given by (58) and (59) (with s = Sgd +Sdnr ), respectively. Combining the contributions of the DNR-dominated and communication-noise-dominated regimes√yields the following bound on the total budget cost for Φ = 2: s loc E DNR Bdgd ≲ bdgd 5.8 + 2.9 ln + 16.6 3 κ2 2 ε σc σ 2 DNR +3276κ2 c 4 . ε Notably, the budget cost increases with the DNR, reflecting the fact that larger objective heterogeneity and weaker network connectivity make it more difficult for the agents to reconcile
√
4 By direct inspection, (43a) is stricter than (43b) if and only if ϕ µLDNR ≥ 2 σg
GCR, which is implied by the defining condition of this setting.
13
their local objectives and reach consensus on the global solution. Remark 2 (Interaction with the Local-SGD phase). Since the initialization of Full DGD satisfies E(s) ≤ (3Φ + 1)Eloc , the DNR-dominated regime is skipped whenever (3Φ + 1)Eloc violates the lower threshold condition (43a) required to operate in the DNR-dominated regime. In this case, the corresponding budget term is omitted from the overall budget expression. IV-B.c Low DNR-to-gradient-noise ratio: This setting is characterized by ϕ
µLDNR ≤ min{GCR, 1}, σg2
where ϕ is defined in (45). In other words, the DNR is small relative to the gradient-noise level. Under this condition, the DNR-dominated regime is unfeasible (seen by direct inspection of (44) and (49)). Consequently, the Full-DGD phase consists of a gradient-noise-dominated regime, followed by a communication-noise-dominated regime that persists until the target accuracy ε is attained. Intuitively, gradient noise is initially the dominant bottleneck. As the error decreases, the gradient-noise bottleneck is eventually overcome and communication noise becomes the dominant bottleneck, triggering the transition to the communication-noise-dominated regime. Thus, the network operates in the gradient-noise-dominated regime until reaching the error p εth = (4Φ + 1) DNR/GCR given by (48a). Comparing (50) in Sec. III-B.c with δr ≤ −n ⌈ν E(r) ⌉ in (81), we set n = 2,
ν = 8Φ2 ln(4Φ)
κ+1 2 σ , µL g
(62)
yielding the total budget accumulated until the error falls below εth as ! σg2 GCR bdgd Sgnd + ϕgnd 2 , (63) µ DNR 4
ln(4Φ) where we defined the scaling factor ϕgnd = (Φ16Φ 2 −1)(4Φ+1)2 . Furthermore, specializing (84) to n nd ν as in (62), α ≈ 1.65 √ (cf. (33)), and Φ = 2, yields
Et ≲ 24.6
σg 1 √ , µ t − ks + 1
(64)
for all iterations belonging to the gradient-noise-dominated √ regime and s = Sgd . Thus, the error decays as O(1/ t), matching the characteristic behavior of stochastic DGD on strongly convex objectives [27]. Notably, both the error and the dominant contribution to the budget cost scale with the gradient-noise variance. Once the error falls below εth , the network transitions to the communication-noise-dominated regime of Full DGD, whose budget cost and error decay are given by (58) and (59) (with s = Sgd + Sgnd ), respectively. Combining the contributions of the gradient-noise- and communication-noise-
dominated regimes, we bound the total budget cost of the FullDGD phase as loc σg2 GCR E Bdgd ≲ bdgd 5.8 + 2.9 ln + 2.5 2 ε µ DNR σ 2 DNR , +3276κ2 c 4 ε √ for Φ = 2. The total budget increases with both the gradientnoise and communication-noise levels, consistent with the fact that mitigating stronger noise sources requires more communication and computation resources. Remark 3 (Interaction with the Local-SGD phase). Since the initialization of Full DGD satisfies E(s) ≤ (3Φ + 1)Eloc , the gradient-noise-dominated regime is skipped whenever (3Φ + 1)Eloc violates the lower threshold condition (48a) required to operate in this regime. In this case, the corresponding budget term should be omitted from the overall budget expression. IV-B.d High-GCR, intermediate DNR-to-gradient-noise ratio: This setting is characterized by 1≤ϕ
µLDNR √ ≤ GCR, σg2
GCR > 1,
with ϕ defined in (45). In other words, communication noise is small relative to gradient noise (high GCR), while the DNR is of intermediate magnitude relative to the gradientnoise level. Under these conditions, both the DNR-dominated and gradient-noise-dominated regimes are feasible (seen by direct inspection of (44) and (49)). Consequently, the FullDGD phase traverses all three bottleneck regimes: it first operates in the DNR-dominated regime, then transitions to the gradient-noise-dominated regime, and finally enters the communication-noise-dominated regime until the target accuracy ε is attained. Specifically, the network operates in the DNR-dominated regime until reaching the error threshold εth =
8Φ2 σg2 1 √ , 4Φ + 1 µL DNR
given by (43b).5 Comparing (46) in Sec. III-B.b with δr ≤ −n ⌈ν E(r) ⌉ in (81), we set n and ν as in (60). Using (82) in Theorem 1 gives the total budget accumulated until the error falls below εth as DNR bdgd Sdnr + ϕdnr L2 2 , σg 2
(4Φ+1) where we defined the scaling factor ϕdnr = ln(4Φ) 4Φ(Φ−1) , and the error decays as in (61). In this regime, the accumulated budget cost scales linearly with DNR and inversely with σg2 , since the error threshold εth is reached earlier as σg2 increases. At this point, gradient noise becomes the dominant bottleneck, and the network transitions to the gradient-noisedominated regime of Full DGD. The corresponding budget 5 Indeed, (43b) is stricter than (43a) if and only if ϕ µLDNR 2 σg
implied by the defining condition of this setting.
≤
√
GCR,
14
cost and error decay are given by (63) and (64), respectively. Finally, once the error threshold (48a) is reached, the network transitions to the communication-noise-dominated regime of Full DGD, with budget cost and error decay given by (58) and (59), respectively. The total budget is obtained by √ combining the costs of the three regimes traversed. For Φ= 2: loc E L2 Bdgd ≲ bdgd 5.8 + 2.9 ln + 32.8 2 DNR ε σg ! σg2 GCR σ 2 DNR +2.5 2 + 3276κ2 c 4 . µ DNR ε
resulting covariance becomes Σc = σq2 W2 . The correspond ing communication-noise level is σc2 = E ∥ϵc,t ∥22 | Ft = trace(Σc ) = σq2 trace(W2 ). Similarly, gradient noise is mod-
The third and fifth terms increase with the DNR, highlighting the fact that larger objective heterogeneity or weaker network connectivity makes it more difficult for the agents to reconcile their local objectives and to overcome communication noise. By contrast, the gradient-noise contribution decreases with the DNR, since a larger DNR shortens the duration of the gradientnoise-dominated regime.
These are initialized as D0 = x0 − x⋆ and Σ0 = 0. For t > 0, Dt and Σt can be computed recursively from the updates (3). Using ∇f (xt ) = µ(xt − xloc ), where µ is diagonal with ith diagonal element µi , we rewrite (3) as
Remark 4 (Interaction with the Local-SGD phase). Since the initialization of Full DGD satisfies E(s) ≤ (3Φ + 1)Eloc , the DNR-dominated regime is skipped whenever (3Φ + 1)Eloc violates the lower threshold condition (43b) required to operate in this regime. Furthermore, the gradient-noise-dominated regime is skipped whenever (3Φ + 1)Eloc violates the lower threshold condition (48a) required to operate in it. In these cases, the corresponding budget terms should be omitted from the overall budget expression.
Dt+1 = At Dt + ηt µ(xloc − x⋆ ).
V N UMERICAL R ESULTS To illustrate the proposed bottleneck-centric framework, we consider a network of N = 50 agents arranged in a Knearest-neighbor ring graph with K = 10. Thus, each agent communicates with its K nearest neighbors on either side of the ring. The mixing matrix W is symmetric and doubly stochastic, with weight 1/(2K) assigned to each active link. Each agent holds a one-dimensional quadratic objective µi 2 fi (x) = (x − xloc x ∈ R, i ) , 2 where the curvature parameters µi are drawn independently and uniformly from [µ, L], with µ = 1 and L = 4, while the local minimizers xloc are drawn independently from N (0, 100). i All agents are initialized from a common point xinit . This quadratic setting is particularly insightful because the resulting optimization dynamics admit a closed-form meansquare error, allowing us to isolate and visualize the effects of objective heterogeneity, network connectivity, gradient noise, and communication noise. The global optimum is PN loc ⋆ i=1 µi xi . x = P N i=1 µi Communication noise is modeled as additive Gaussian, ϵc,t ∼ N (0, Σc ), where Σc = σq2 W2 . This model can be interpreted as an abstraction of a quantization process, where each agent introduces independent quantization noise of variance σq2 . After aggregation through the mixing matrix, the
σ2
eled as ϵg,t ∼ N (0, Σg ), with covariance Σg = Ng IN , corresponding to independent Gaussian perturbations injected by each agent during gradient computation, each having variance σg2 /N . The gradient and communication noises are assumed independent. To find the closed-form RMSE, define the bias Dt and error covariance matrix Σt as Dt ≜ E[xt − x⋆ ], Σt ≜ E (xt −x⋆ −Dt )(xt −x⋆ −Dt )⊤ .
xt+1 −x⋆ =At (xt −x⋆ )+ηt µ(xloc −x⋆ )+N (0, γt2 Σc +ηt2 Σg ), where At ≜(1−γt )IN +γt W−ηt µ. Taking expectation yields (65)
Similarly, xt+1 −x⋆ −Dt+1 =At (xt −x⋆ −Dt )+N (0, γt2 Σc +ηt2 Σg ). Calculating its covariance yields 2 2 Σt+1 = At Σt A⊤ t + γ t Σc + η t Σ g .
(66)
With Dt and Σt thus given, we can compute the RMSE as p p (67) Et = E[∥xt − x⋆ ∥2 ] = ∥Dt ∥2 +trace(Σt ). In addition, it is useful to quantify the contribution of the different bottlenecks to the overall error. To this end, we further decompose the error covariance into the contributions (comm) due to communication noise, Σt , and that due to gradient (grad) noise, Σt . These quantities evolve according to (comm)
= At Σt
(grad)
= At Σt
Σt+1
Σt+1 (comm)
(comm)
(grad)
2 A⊤ t + γ t Σc ,
2 A⊤ t + η t Σg ,
(grad)
(comm)
= 0. By linearity, Σt = Σt + with Σ0 = Σ0 (grad) Σt . Similarly, we decompose the bias into two components: the contribution due to objective heterogeneity and limited network connectivity, and that due to initialization. To isolate the former, consider the noiseless dynamics x̃t+1 = [(1 − γt )IN + γt W]x̃t − ηt ∇f (x̃t ),
(68)
initialized at the global optimum, x̃0 = x⋆ . The resulting trajectory captures the bias induced solely by objective heterogeneity and limited connectivity. The remaining bias is due to the fact that the algorithm is initialized at xinit ̸= x⋆ , and thus captures the effect of initialization. Accordingly, we (DNR) (init) decompose Dt = Dt + Dt , where (DNR)
Dt
(init)
≜ x̃t − x⋆ ,
Dt (DNR)
These quantities satisfy D0
(DNR)
≜ Dt − Dt (init)
= 0, D0
.
= D0 , and for
15
t ≥ 0, (DNR)
Dt+1
(DNR)
= At Dt
(init)
(init)
Dt+1 = At Dt
+ ηt µ(xloc − x⋆ ),
.
With these definitions, the overall MSE can be written as (init)
Et2 = ∥Dt
(DNR) 2
(comm)
∥ +trace(Σt
+Dt
(grad)
)+trace(Σt
).
We then measure the relative contributions of communication and gradient noises to the MSE as (comm)
(comm)
ρt
≜
trace(Σt Et2
)
(grad)
(grad)
, ρt
≜
trace(Σt Et2
)
.
For the effects of initialization and DNR, the MSE is not additive with respect to their contributions, since the cross (init)⊤ (DNR) product Dt Dt is generally non-zero. We therefore define their relative contributions as (init) (DNR) 2 (init) 2 ∥Dt + Dt ∥ ∥Dt ∥ (init) ≜ · , ρt 2 (init) 2 (DNR) 2 Et ∥Dt ∥ +∥Dt ∥ (DNR) 2 (init) (DNR) 2 ∥Dt ∥ ∥Dt + Dt ∥ (DNR) ≜ ρt · . 2 (init) 2 (DNR) 2 Et ∥Dt ∥ +∥Dt ∥
With these definitions, the four relative contributions satisfy (init) (DNR) (grad) (comm) ρt + ρt + ρt + ρt = 1. In the subsequent numerical evaluation, we compare the proposed multi-stage schedule against several benchmarks. The selected stepsize schedule determines the evolution of the bias and covariance according to (65) and (66), and therefore characterizes the RMSE in (67). Constant stepsizes: This schedule employs constant learning 1 and consensus stepsizes, η = L+µ , γ = 12 , satisfying the convergence conditions in (35). In the noiseless setting, the resulting iterates converge linearly to a neighborhood of the global optimum, with asymptotic error (75). • Gradient-noise-aware: This schedule is designed to mitigate the effect of gradient noise in DGD. Communication noise is neglected in its design. It therefore uses a fixed consensus stepsize, γ = 21 , together with a decreasing learning stepsize 1 1 ηt = min , . µt L + µ
•
The 1/(µt) decay is motivated by classical stochastic approximation and stochastic gradient methods for strongly convex objectives, see, e.g., [38]. • Communication-noise-aware: This schedule is designed to mitigate the combined effects of communication noise, gradient noise, objective heterogeneity, and limited network connectivity. Following [13], the learning and consensus stepsizes are chosen as ηt =
1 1 , 4µ µ + L 1 + 5(µ+L) t
γt =
0.5 4µ 1 + 5(µ+L) t
3/4 ;
the specific exponents and scaling factors are motivated and theoretically justified in [13]. The proposed √ multi-stage schedule is illustrated in Fig. 3 for the case Φ= 2. During the Local-SGD phase, the consensus
Fig. 3: Learning and consensus stepsizes, η(s) and γ(s) , as a function of the RMSE bound E(s) , for the High-GCR, intermediate DNR-to-gradient-noise ratio setting. The plot shows also the phase and regime transitions under the multi-stage schedule.
stepsize is identically zero, since no communication takes place. As the error decreases, the learning stepsize is progressively reduced from its maximum admissible value 2/(µ + L). Upon entering the Full-DGD phase, both the learning and consensus stepsizes become functions of the current error level. In particular, the learning stepsize scales linearly with the error in the DNR-dominated regime (η(s) ∝ E(s) ), quadratically 2 in the gradient-noise-dominated regime (η(s) ∝ E(s) ), and with the power of four in the communication-noise-dominated 4 regime (η(s) ∝ E(s) ), in agreement with the theoretical characterizations derived in Sec. III-B. The consensus stepsize exhibits a different behavior. It remains at its maximum value γ(s) = 1/2 throughout the DNRdominated and most of the gradient-noise-dominated regimes, indicating that communication is not yet the limiting factor and that aggressive information mixing is therefore desirable. However, once communication noise becomes significant, the consensus stepsize is progressively reduced. This reflects the fact that communication becomes increasingly error prone, and a smaller consensus stepsize is required to limit the accumulation of communication noise across iterations. The proposed method transitions from a Local-SGD phase to a Full-DGD phase as dictated by the active bottleneck, whereas all benchmark methods rely exclusively on Full DGD. To facilitate a fair comparison of the resulting optimization dynamics, we adopt the optimistic setting bg = bdgd = 1, so that the budget coincides with the total number of iterations. This choice isolates the impact of the different bottlenecks and operating strategies without introducing additional asymmetries between Local-SGD and Full-DGD operations. Consequently, any performance gain observed for the proposed method stems from its bottleneck-aware scheduling strategy rather than from assigning a lower cost to local computation. Figure 4 shows the RMSE (top row), normalized by the initial error ∥x0 − x⋆ ∥, together with the relative contributions of the four error components (bottom row) under the proposed multi-stage schedule. The left and right columns correspond to the High-GCR, intermediate DNR-to-gradient-noise ratio setting (Sec. IV-B.d) and the High DNR-to-gradient-noise ratio setting (Sec. IV-B.b), respectively. From the RMSE curves, we observe that the proposed multi-stage schedule achieves a sus-
16
(a) High-GCR, intermediate DNR-to-gradient-noise ratio setting: DNR≈1.2·106 , GCR=3.7·106 , σc ≈3·10−4 ∥∇f (x⋆ )∥, σg ≈1.4∥∇f (x⋆ )∥.
(b) High DNR-to-gradient-noise ratio setting: DNR≈1.2 · 106 , GCR=1, σc ≈9.1·10−5 ∥∇f (x⋆ )∥, σg ≈2.3·10−4 ∥∇f (x⋆ )∥.
Fig. 4: Top row: normalized RMSE under different stepsize schedules. Bottom row: relative contributions of initialization, DNR, gradient noise, and communication noise to the overall MSE. The plots show also the phase and regime transitions under the proposed multi-stage schedule.
tained error reduction throughout the entire optimization horizon. In contrast, the constant-stepsize schedule saturates due to the heterogeneity-induced bias of DGD. The communicationnoise-aware schedule also exhibits a decreasing error, but its convergence is significantly slower because it assumes communication noise to be the dominant bottleneck at all times, resulting in overly conservative stepsizes during the early stages of optimization. The gradient-noise-aware schedule performs well initially, when communication noise contributes little to the overall error. However, once communication noise becomes significant, its fixed consensus stepsize is unable to sufficiently suppress the propagation of communication errors, leading to a deterioration in performance. The bottom row provides insight into the evolution of the active bottleneck. In the High-GCR, intermediate DNR-togradient-noise ratio setting (left column), the optimization trajectory traverses all bottleneck regimes predicted by the theory. The initialization error dominates during the early iterations and rapidly decays. Gradient noise subsequently becomes the dominant source of error during the Local-SGD phase, followed by a DNR-dominated phase after the switch to Full DGD. As the error decreases further, the relative impact of DNR diminishes and that of gradient-noise remains sustained, until communication noise progressively emerges as the dominant bottleneck, eventually accounting for the majority of the MSE. A similar behavior is observed in the High DNR-to-
gradient-noise ratio setting (right column). However, since gradient noise is comparatively weak, the gradient-noisedominated regimes are skipped. The optimization process therefore transitions directly from the initialization-dominated regime of Local SGD to the DNR-dominated regime of Full DGD, and subsequently to the communication-noisedominated regime. The corresponding error decomposition reflects this sequence of bottlenecks. Overall, these results validate the proposed bottleneckcentric framework. The observed transitions closely match the theoretically predicted operating regimes, and the resulting multi-stage schedule adapts the learning and consensus stepsizes to the active bottleneck, improving budget-efficiency compared with the benchmark schemes. VI
C ONCLUDING R EMARKS
This paper developed a resource-aware, bottleneck-centric framework for DGD. We showed that objective heterogeneity, network connectivity, gradient noise, and communication noise become dominant at different error scales, giving rise to distinct operating regimes and budget scalings. The resulting analysis reveals how the overall budget decomposes into the costs of overcoming successive bottlenecks and provides insight into the tradeoffs among objective heterogeneity, network connectivity, gradient noise, and communication noise. More broadly, the proposed framework opens new avenues for
17
resource-aware decentralized optimization, where algorithms adapt to the active bottleneck as the optimization progresses. A PPENDIX A U PPER BOUND ON THE INITIAL RMSE Suppose all devices initialize the algorithm from the same point xi,0 = xinit , ∀i. Then, using strong convexity of the global objective F (x), we have ∥∇F (xinit )∥= ∥∇F (xinit ) − ∇F (x⋆ )∥≥ µ∥xinit − x⋆ ∥. √ Recalling√ that E0 = N ∥xinit − x⋆ ∥, this implies N E0 ≤ µ ∥∇F (xinit )∥. We continue by using F (x) = PN 1 i=1 fi (x) and the triangle inequality: N √ √ N N N 1 X E0 ≤ ∥∇F (xinit )∥= ∇fi (xinit ) µ µ N i=1 √ N 1 X N ≤ √ ∥∇fi (xinit )∥≤ max∥∇fi (xinit )∥≜ E(0) . i µ µ N i=1 The bound E(0) can be computed with low communication overhead via a scalar distributed max-consensus procedure [39]. Tighter, albeit more communication-intensive, bounds can be obtained by using one of the intermediate bounds in the above sequence of inequalities. Since E(0) only serves to initialize the stage-wise recursion, any computable upper bound may be used. A PPENDIX B P ROOF OF L EMMA 1 Proof. When 0≤η≤2/(L + µ), the mean-square error relative to xloc satisfies [12] E[∥xt+1 − xloc ∥2 ] ≤ (1 − ηµ)2 E[∥xt − xloc ∥2 ] + η 2 σg2 , where σg2 bounds the conditional second moment of the gradient noise (Assumption 3). Applying this inequality recursively for δ local steps gives E[∥xks +δ − xloc ∥2 ]
which relates the RMSE at time ks + δ to that at time ks . The final result of the lemma is obtained by using a + b + c ≤ 3 max{a, b, c}.
A PPENDIX C P ROOF OF L EMMA 2 N) Proof. In [12], it was proved that, for 0<η≤ 2−γ(1−λ and L+µ γ ∈ (0, 1], the one-step error dynamic is bounded as
E[∥xt+1 −x̂∥2 | Ft ]≤(1−ηµ)2 ∥xt −x̂∥2 +E[∥γϵc,t − ηϵg,t ∥2 | Ft ], where x̂ is the fixed point (FP) of the noiseless iterate,6 that is, the unique solution of x̂ = (1 − γ)x̂ + γ(W ⊗ Id )x̂ − η∇f (x̂),
(71)
which Full DGD converges to. Furthermore, using Minkowski’s inequality [40, Lemma 14.10], q q E[∥γϵc,t − ηϵg,t ∥2 | Ft ] ≤ γ E[∥ϵc,t ∥2 | Ft ] q +η E[∥ϵg,t ∥2 | Ft ] ≤ γσc + ησg , where σg2 and σc2 bound the conditional second moments of the gradient and communication noises (Assumption 3). Taking total expectation, we then obtain E[∥xt+1 −x̂∥2 ]≤(1−ηµ)2 E[∥xt −x̂∥2 ]+(γσc +ησg )2 . (72) Applying this inequality recursively for δ steps gives
≤ (1 − ηµ)2δ E[∥xks − xloc ∥2 ]+η 2 σg2 ≤ (1 − ηµ)2δ E[∥xks − xloc ∥2 ]+
where we used (69) in the last inequality. Next, using p Minkowski’s inequality again to bound E∥x − xloc ∥2 ≤ k s p loc loc ⋆ 2 E∥xks − x ∥ + E =Eks +E and Eks ≤E(s) , we obtain p η(κ + 1) δ √ Eks +δ ≤(1 − ηµ) E(s) + σg 2L + (1 + (1 − ηµ)δ )Eloc , (70)
δ−1 X
(1 − ηµ)2r
r=0 η 2 σg2
1−(1−ηµ)2 η(κ+1)σg2 ≤ (1 − ηµ)2δ E[∥xks − xloc ∥2 ]+ , (69) 2L where in the last step we used 1 − (1 − ηµ)2 = ηµ(2 − ηµ) ≥ 2ηµL/(L + µ) for η ≤ 2/(L + µ). We are interested in the distance to the global optimum x⋆ . By Minkowski’s inequality [40, Lemma 14.10] and the RMSE definition in (6), q p Eks +δ = E[∥xks +δ − x⋆ ∥2 ] ≤ E[∥xks +δ − xloc ∥2 ] + Eloc p q η(κ + 1) δ loc 2 √ ≤ (1 − ηµ) E[∥xks − x ∥ ] + σg + Eloc , 2L
E[∥xks +δ − x̂∥2 ] ≤ (1 − ηµ)2δ E[∥xks − x̂∥2 ] + (γσc + ησg )2
δ−1 X (1 − ηµ)2r r=0
(γσc + ησg )2 ≤ (1 − ηµ) E[∥xks − x̂∥ ] + 1 − (1 − ηµ)2 (γσc + ησg )2 ≤ (1 − ηµ)2δ E[∥xks − x̂∥2 ] + (κ + 1) , (73) 2ηL 2δ
2
where in the last step we used 1 − (1 − ηµ)2 = ηµ(2 − ηµ) ≥ 2ηµL/(L + µ) since η ≤ 2/(L + µ). The distance to the global optimum follows from
6 Its existence and uniqueness is guaranteed by the fact that, under the stepsize condition, (30) is a contraction mapping, combined with Banach’s fixed point Theorem [41, Th. 9.23]. See [12] for further details.
18
Minkowski’s inequality [40, Lemma 14.10], p Eks +δ = E[∥xks +δ − x⋆ ∥2 ] p ≤ E[∥xks +δ − x̂∥2 ] + ∥x̂ − x⋆ ∥ p p η(κ + 1) δ 2 √ ≤ (1 − ηµ) E[∥xks − x̂∥ ] + σg 2L √ κ+1 γ σc + ∥x̂ − x⋆ ∥, +√ √ η 2L where in the last step we used (73) and the triangle inequality. Next, using p Minkowski’s inequality again to bound p E∥xks − x̂∥2 ≤ E∥xks − x⋆ ∥2 + ∥x̂ − x⋆ ∥, we obtain p η(κ + 1) √ σg Eks +δ ≤ (1 − ηµ)δ Eks + 2L √ κ+1 γ σc + (1 + (1 − ηµ)δ )∥x̂ − x⋆ ∥. +√ √ (74) η 2L In [12], it was shown that the FP error satisfies η L + µ√ η ∥∇f (x⋆ )∥ DNR. = ∥x̂ − x⋆ ∥≤ κ γ (1 − λ2 ) γ 2
(75)
(see the definition of DNR in (18)). Substituting (75) into (74) and using Eks ≤ E(s) , we obtain p η(κ + 1) δ √ Eks +δ ≤ (1 − ηµ) E(s) + σg 2L √ η L + µ√ γ κ+1 σc + (1 + (1 − ηµ)δ ) +√ √ DNR, (76) η γ 2 2L which relates the error after δ iterations to the error at the start of stage s. The bound in the lemma statement directly follows after using a + b + c + d ≤ 4 max{a, b, c, d}.
Proof. We can reformulate (32b)-(32d) as E(s) 2 2L η ≤ κ+1 ≜ A; 4Φσ g 2 4γΦσc η ≥ κ+1 ≜ B; 2L E(s) γE(s) 2 1 √ η ≤ L+µ 4Φ+1 DNR ≜ C.
(77)
provided that the following feasibility conditions hold: B≤
s.t.
(79b) 3
E(s) κ √ γ≤ , (79c) 2 2 (κ + 1) 4Φ (4Φ+1)σc2 DNR √ 2κ E(s) γ≤ , (79d) κ + 1 4Φσc 1 γ≤ , (79e) 2 where the constraints (79b)-(79d) correspond to (78), and the last one corresponds to (36). Since the objective (79a) is nondecreasing in γ, the optimal γ matches the tightest constraint among (79b)–(79e), yielding (37). Substituting γ(s) into (79a) gives the optimal learning stepsize ( √ 2 κ 2 E(s) 1 √ √ min , η(s) ≜ L+µ κ + 1 2Φ(4Φ + 1)σc DNR | {z } (a)
3 E 2 E(s) L (s) √ , 2µL , κ + 1 4Φ2 (4Φ + 1)σg σc DNR 4Φσg {z } | {z } | (c)
(b)
√
2 E(s)
) E(s) κ √ √ √ , , 1 . κ + 1 2Φ(4Φ + 1)σc DNR (4Φ + 1) DNR | {z } | {z } |{z} (d)
√
(e)
(f)
√
A PPENDIX E P ROOF OF L EMMA 4
These conditions must hold together with (36). For a given consensus stepsize 0 < γ ≤ 21 , the learning stepsize η should be chosen as large as possible. From (77) and (36), this yields 1 η = min A, C, , L+µ
B ≤ C,
2
E(s) L , γ≤ κ + 1 8Φ2 σg σc
Note that (b) = (a)·(c) and (d) = (a)·(f), hence (b) ≥ min{(a), (c)} and (d) ≥ min{(a), (f)}. Therefore, the terms (b) and (d) in the expression of η(s) can never be the smallest among the arguments of the minimum, and can thus be discarded. This yields (38) and proves the lemma.
A PPENDIX D P ROOF OF L EMMA 3
B ≤ A,
This leads to the problem ( ) 2γE(s) 1 µL E(s) 2 √ min , , 1 (79a) max γ≥0 L+µ 8Φ2 σg (4Φ+1) DNR
1 . L+µ
(78)
If any of the conditions in (78) are violated, then the feasible region for η in (77) is empty, resulting in an infeasible stepsize configuration. Optimizing γ therefore amounts to selecting the value of γ that maximizes the admissible learning stepsize η.
Proof. If E(s) ≤ (3Φ+1)Eloc , Local SGD is unfeasible, hence Full DGD is the only feasible option. Otherwise (E(s) >(3Φ + 1)Eloc ), the stage-wise budget costs under Local SGD or Full DGD are given by (25) and (39): ln(3Φ) ln(4Φ) Bg =bg , Bdgd =bdgd , − ln(1 − µηg ) − ln(1 − µηdgd ) where ηg and ηdgd are the optimal stepsizes, given in (24) and (38), respectively. Since ln(3Φ) < ln(4Φ) and bg ≤ bdgd , it follows ln(4Φ) Bg < bdgd . − ln(1 − µηg ) Therefore, to prove that Bg ≤ Bdgd , it suffices to show that ηdgd ≤ ηg . Using the expression of ηg in (24), this condition is equivalent to !2 E(s) 2 2µL ηdgd ≤ , ηdgd ≤ . L+µ L + µ 3Φσg
19
1 The first condition holds trivially since ηdgd ≤ L+µ (term (f) in (38)). The second one holds trivially since ηdgd ≤ E(s) 2 2µL (term (c) in (38)), thus proving the first part L+µ 4Φσg of the lemma. Upon entering Full DGD, the error satisfies E(s) ≤ (3Φ + 1)Eloc . At the same time, from (41c), operating in the initialization-dominated regime of Full DGD requires E(s) ≥ √ (4Φ + 1)√ DNR. A necessary condition is (3Φ + 1)Eloc ≥ (4Φ + 1) DNR. Equivalently, using (18),
the conditions of the theorem, the error is reduced by a factor Φ at every stage. Hence S is the smallest integer such that E(s+S) = E(s) · Φ−S ≤ εth , which yields (80). We now bound the corresponding number of iterations. In stage r = s, . . . , s + S − 1, the stage length is bounded as in (81). Using ⌈x⌉ ≤ 1 + x and E(r) = Φ−(r−s) E(s) yields −n
δr ≤ 1 + νΦ(r−s)n E(s) . If n > 0, we then bound the total number of iterations as
⋆
3Φ + 1 2κ ∥∇f (x )∥ . ≥ 4Φ + 1 L + µ (1 − λ2 )Eloc
K=
s+S−1 X
δr ≤ S + ν
r=s
5
>
4Φ + 1
≤S+
⋆
and
2κ ∥∇f (x )∥ L + µ (1 − λ2 )Eloc
−n
Φqn E(s) = S +
q=0
However, 4 (a) 3Φ + 1
S−1 X
ν ΦnS − 1 n E(s) Φn − 1
ν ΦS n . Φn − 1 E(s)
Finally, note that by definition of S
(c) (d) 2 4κ ≥ ≥ 1, ≥ (κ + 1)(1 − λ2 ) 1 − λ2
(b)
where (a) uses Φ > 1, (b) uses (17), (c) uses κ ≥ √ 1, and (d) uses λ2 ≥ −1. Therefore, (3Φ+1)Eloc < (4Φ+1) DNR, and the initialization-dominated regime of Full DGD is infeasible.
E(s) > εth ΦS−1
Φ ΦS < . ε E(s) th
i.e.,
Using this bound, we then obtain (82) for the case n > 0. By repeating the same steps for the special case n = 0, we S find δr ≤ 1 + ν, hence K ≤ S + Sν. Using EΦ < Φ/εth ⇒ (s)
A PPENDIX F M ULTI -S TAGE B UDGET B OUNDS Theorem 1. Let Eks ≤ E(s) be the RMSE error bound at the start of stage s, and let εth < E(s) be a target error level. Then, E(s+S) ≤ εth after S ≜ logΦ E(s) /εth (80)
S ≤ logΦ (ΦE(s) /εth ), yields (82) for the case n = 0. Finally, consider t = ks , . . . , ks + K − 1 and let r be the unique integer such that r−1 X
r = s, . . . , s + S − 1,
(81)
for some constants ν > 0 and n ≥ 0. Then, if each iteration incurs a cost of b, the total budget required to reach Eks+S ≤εth satisfies ( n −n s+S−1 X S + ΦνΦ n > 0, n −1 εth , b· δr ≤ b · (82) ΦE(s) ν S + ln(Φ) ln εth , n = 0. r=s n
Furthermore, suppose that E(s) ≤ 2ν and that there exists α ≥ 0 such that, ∀r = s, . . . , s + S − 1, Et ≤ α E(r) ,
∀t = kr , . . . , kr+1 − 1.
Then, for all t = ks , . . . , ks+S − 1, Φα( Φn2ν−1 )1/n , (t−ks +1)1/n Et ≤ αE · e− ln(Φ) 2ν (t−ks +1) , (s)
(83)
r X
q=s
δq − 1.
(85)
q=s
Then the t-th iteration falls in stage r, and therefore Et ≤ α E(r) = αE(s) Φ−(r−s)
stages. Furthermore, assume that the stage lengths satisfy −n δr ≤ ⌈ν E(r) ⌉,
δq ≤ t − ks ≤
(86)
by the condition (83) of the theorem. To further bound Φ−(r−s) , note that & ' & ' ν νΦ(q−s)n 2νΦ(q−s)n δq ≤ = ≤ , (87) n n n E(q) E(s) E(s) (r−s)n
where we used the fact that νΦE n
(s)
n
≥ Eνn ≥ 0.5 under the (s)
condition E(s) ≤ 2ν of the theorem, combined with ⌈x⌉ ≤ 2x for x ≥ 0.5. Continuing from (85) for the case n > 0, we obtain r r X X Φ(q−s)n 2ν Φn(r−s+1) t − ks + 1 ≤ δq ≤ 2ν ≤ n . n E(s) E(s) Φn − 1 q=s q=s Equivalently,
n>0
(84)
n = 0.
Remark 5. The regimes investigated in Sec. III-A and Sec. III-B satisfy the conditions of Theorem 1 for specific choices of α, εth , ν, and n. Proof. Consider a generic stage s starting at iteration ks , with error bound E(s) . We aim to bound the total number of stages S required to ensure E(s+S) ≤ εth , the corresponding number of iterations K = ks+S − ks and budget cost b · K. Under
(Φn − 1)En −1/n (s) Φ ≤Φ (t − ks + 1) , 2ν so that (84) follows for the case n > 0, after replacing this bound into (86). Repeating the same steps for n = 0 gives −(r−s)
t − ks + 1 ≤
r X
δq ≤ 2ν(r − s + 1).
q=s
Equivalently, Φ−(r−s) ≤ Φ−
t−ks +1 2ν
, so that (84) follows after
20
replacing this bound into (86). The theorem is thus proved. R EFERENCES [1] S. Kar and J. M. Moura, “Consensus + innovations distributed inference over networks: cooperation and sensing in networked systems,” IEEE Signal Processing Magazine, vol. 30, no. 3, pp. 99–109, 2013. [2] A. Nedić, J.-S. Pang, G. Scutari, and Y. Sun, Multi-agent Optimization, 1st ed. Springer, Cham, 2018. [3] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson, “A survey of distributed optimization,” Annual Reviews in Control, vol. 47, pp. 278–305, 2019. [4] Y. Ji, G. Scutari, Y. Sun, and H. Honnappa, “Distributed (ATC) Gradient Descent for High Dimension Sparse Regression,” IEEE Transactions on Information Theory, vol. 69, no. 8, pp. 5253–5276, 2023. [5] Y. Xiao, Y. Ye, S. Huang, L. Hao, Z. Ma, M. Xiao, S. Mumtaz, and O. A. Dobre, “Fully Decentralized Federated Learning-Based OnBoard Mission for UAV Swarm System,” IEEE Communications Letters, vol. 25, no. 10, pp. 3296–3300, 2021. [6] S. Savazzi, M. Nicoli, and V. Rampa, “Federated Learning With Cooperating Devices: A Consensus Approach for Massive IoT Networks,” IEEE Internet of Things Journal, vol. 7, no. 5, pp. 4641–4654, 2020. [7] A. Nedić and A. Ozdaglar, “Distributed subgradient methods for multiagent optimization,” IEEE Trans. Autom. Control, vol. 54, no. 1, pp. 48–61, Jan. 2009. [8] K. Yuan, Q. Ling, and W. Yin, “On the Convergence of Decentralized Gradient Descent,” SIAM Journal on Optimization, vol. 26, no. 3, pp. 1835–1854, 2016. [9] A. Nedić, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis, “On distributed averaging algorithms and quantization effects,” IEEE Trans. Autom. Control, vol. 54, no. 11, pp. 2506–2517, Nov. 2009. [10] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu., “Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent,” in Proc. 31st NeurIPS, Dec. 2017. [11] S. Kar and J. M. F. Moura, “Distributed consensus algorithms in sensor networks with imperfect communication: Link failures and channel noise,” IEEE Trans. Inf. Theory, vol. 57, no. 1, pp. 355–369, Jan. 2009. [12] E. G. Larsson and N. Michelusi, “Unified analysis of decentralized gradient descent: A contraction mapping framework,” IEEE Open Journal of Signal Processing, vol. 6, pp. 507–529, 2025. [13] N. Michelusi, “Non-coherent over-the-air decentralized gradient descent,” IEEE Transactions on Signal Processing, vol. 72, pp. 4618–4634, 2024. [14] ——, “Interference-robust non-coherent over-the-air computation for decentralized optimization,” 2026, IEEE ICC, to appear. [Online]. Available: https://arxiv.org/abs/2602.12426 [15] R. Saha, S. Rini, M. Rao, and A. J. Goldsmith, “Decentralized optimization over noisy, rate-constrained networks: Achieving consensus by communicating differences,” IEEE Journal on Selected Areas in Communications, vol. 40, no. 2, pp. 449–467, 2022. [16] Z. Jiang, G. Yu, Y. Cai, and Y. Jiang, “Decentralized Edge Learning via Unreliable Device-to-Device Communications,” IEEE Transactions on Wireless Communications, vol. 21, no. 11, pp. 9041–9055, 2022. [17] H. Ye, L. Liang, and G. Y. Li, “Decentralized Federated Learning With Unreliable Communications,” IEEE Journal of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 487–500, 2022. [18] E. Jeong, M. Zecchin, and M. Kountouris, “Asynchronous Decentralized Learning over Unreliable Wireless Networks,” in IEEE International Conference on Communications, 2022, pp. 607–612. [19] A. Reisizadeh, A. Mokhtari, H. Hassani, and R. Pedarsani, “An exact quantized decentralized gradient descent algorithm,” IEEE Transactions on Signal Processing, vol. 67, no. 19, pp. 4934–4947, 2019. [20] A. Koloskova, S. U. Stich, and M. Jaggi, “Decentralized stochastic optimization and gossip algorithms with compressed communication,” in Proc. 36th ICML, Jun. 2019.
[21] N. Michelusi, G. Scutari, and C.-S. Lee, “Finite-Bit Quantization for Distributed Algorithms With Linear Convergence,” IEEE Transactions on Information Theory, vol. 68, no. 11, pp. 7254–7280, 2022. [22] W. Shi, Q. Ling, G. Wu, and W. Yin, “EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization,” SIAM J. Optim., vol. 25, pp. 944–966, May 2015. [23] K. Yuan, B. Ying, X. Zhao, and A. H. Sayed, “Exact Diffusion for Distributed Optimization and Learning–Part I: Algorithm Development,” IEEE Transactions on Signal Processing, vol. 67, no. 3, pp. 708–723, 2019. [24] G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” in 2016 IEEE 55th Conference on Decision and Control (CDC), 2016, pp. 159–166. [25] P. D. Lorenzo and G. Scutari, “Next: In-network nonconvex optimization,” IEEE Transactions on Signal and Information Processing over Networks, vol. 2, no. 2, pp. 120–136, 2016. [26] H. Tang, S. Gan, C. Zhang, T. Zhang, and J. Liu, “Communication compression for decentralized training,” in Proc. 32nd NeurIPS, Dec. 2018. [27] A. Nedić and A. Olshevsky, “Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs,” IEEE Transactions on Automatic Control, vol. 61, no. 12, pp. 3936–3947, 2016. [28] H. Xing, O. Simeone, and S. Bi, “Federated Learning Over Wireless Device-to-Device Networks: Algorithms and Convergence Analysis,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 12, pp. 3723–3741, 2021. [29] D. Kovalev, A. Koloskova, M. Jaggi, P. Richtárik, and S. U. Stich, “A linearly convergent algorithm for decentralized optimization: Sending less bits for free!” in Proc. 24th AISTATS, Apr. 2021. [30] Y. Liao, Z. Li, K. Huang, and S. Pu, “A compressed gradient tracking method for decentralized optimization with linear convergence,” IEEE Trans. on Automatic Control, vol. 67, no. 10, pp. 5622–5629, 2022. [31] S. Magnússon, 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, 2020. [32] A. S. Berahas, R. Bollapragada, N. S. Keskar, and E. Wei, “Balancing Communication and Computation in Distributed Optimization,” IEEE Transactions on Automatic Control, vol. 64, no. 8, pp. 3141–3155, 2019. [33] A. S. Berahas, R. Bollapragada, and E. Wei, “On the Convergence of Nested Decentralized Gradient Methods With Multiple Consensus and Gradient Steps,” IEEE Transactions on Signal Processing, vol. 69, pp. 4192–4203, 2021. [34] W. Choi, D. Kim, and S.-B. Yun, “Convergence results of a nested decentralized gradient method for non-strongly convex problems,” Journal of Optimization Theory and Applications, vol. 195, no. 1, pp. 172–204, Aug. 2022. [35] V. Schwarz, G. Hannak, and G. Matz, “On the convergence of average consensus with generalized metropolis-hasting weights,” in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2014, pp. 5442–5446. [36] M. Centenaro, L. Vangelista, A. Zanella, and M. Zorzi, “Long-range communications in unlicensed bands: the rising stars in the iot and smart city scenarios,” IEEE Wireless Communications, vol. 23, no. 5, pp. 60– 67, 2016. [37] R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge University Press, 1999. [38] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro, “Robust Stochastic Approximation Approach to Stochastic Programming,” SIAM Journal on Optimization, vol. 19, no. 4, pp. 1574–1609, 2009. [39] F. Iutzeler, P. Ciblat, and J. Jakubowicz, “Analysis of max-consensus algorithms in wireless channels,” IEEE Transactions on Signal Processing, vol. 60, no. 11, pp. 6103–6107, 2012. [40] I. Florescu and C. A. Tudor, Handbook of Probability. Wiley, 2013. [41] W. Rudin, Principles of Mathematical Analysis. McGraw-Hill, 1953.