Distributed Consensus, Optimization, and Learning under Communication Constraints

1

Distributed Consensus, Optimization, and Learning under Communication Constraints

arXiv:2611.06524v1 [cs.IT] 4 Nov 2026

Zheng Chen, Nicolò Michelusi, Themistoklis Charalambous, and Kaibin Huang

Abstract—Many modern engineering applications require distributed problem-solving in which multiple nodes in a network cooperate to achieve a common optimization objective. Numerous distributed optimization and learning algorithms rely on consensus-based distributed coordination to ensure network-wide agreement via iterative local interactions. In these algorithms, the accuracy, frequency, and reliability of information exchange among network nodes directly influence system performance, including convergence behavior, training delay, and model accuracy. This tutorial article adopts a bottom-up approach to present the fundamentals of consensus averaging and distributed optimization methods, and highlights the impact of network connectivity, information flow, and communication uncertainty on network cooperation and optimization performance. Building on these theoretical insights, we discuss key design principles for communication-constrained distributed learning across diverse network topologies and review common approaches to communication-efficient learning, particularly in wireless networks. Despite substantial progress, further efforts are needed to bridge the gap between theory and practice and fully realize the potential of cooperative and networked intelligence. Index Terms—Distributed consensus, distributed optimization, federated and decentralized learning, communication constraints.

I. I NTRODUCTION Modern data-driven systems operate at increasingly large scales, with data generated by numerous edge devices distributed across wide geographical areas. Collecting all data at a central location for processing is often impractical due to communication constraints and privacy concerns. This motivates distributed algorithms that leverage local computational resources and information exchange to enable collaborative decision-making across the network [1]. Distributed optimization provides a principled framework for collaboratively solving large-scale inference and decision-making problems using Z. Chen is with the Dept. of Electrical Engineering, Linköping University, Linköping, Sweden (email: zheng.chen@liu.se). Her research is supported in part by ELLIIT, Swedish Research Council (VR), and Knut and Alice Wallenberg Foundation. N. Michelusi is with the School of Electrical, Computer and Energy Engineering, Arizona State University, AZ, USA (email: nicolo.michelusi@asu.edu). His research is funded by NSF CNS-2129015. T. Charalambous is with the Dept. of Electrical and Computer Engineering, University of Cyprus, Cyprus (email: charalambous.themistoklis@ucy.ac.cy). His research is supported in part by the MINERVA project funded by the European Research Council (ERC) (Grant No. 101044629), and by the University of Cyprus with project acronym LOVELACE. K. Huang is with the Dept. of Electrical and Computer Engineering, The University of Hong Kong (HKU), Hong Kong (email: huangkb@hku.hk). His research is supported in part by the Research Grants Council of the Hong Kong Special Administrative Region, China under the NSFC/RGC CRS scheme (CRS_HKU702/24), the Areas of Excellence scheme grant (AoE/E-601/22-R) and the GRF Grants 17304925 and 17212526, and in part by the Croucher Senior Fellowship.

Fig. 1: Illustration of a distributed learning network. Each agent performs local computation using its local dataset while exchanging model information with neighboring agents. The local model update combines locally computed information with models received from neighboring agents.

locally available information [2]. It has applications in a wide range of domains, including wireless sensor fusion, distributed estimation and inference [3], multi-agent coordination [4], and collaborative machine learning (ML) [5]. A. Historical Overview A prominent class of distributed optimization and learning methods is based on consensus mechanisms. The study of distributed consensus has its roots in the classical problems of coordination and agreement in distributed systems and control engineering [6], [7]. The quantity of interest in consensus problems can be continuous- or discrete-valued. For continuous-valued consensus, the seminal work of DeGroot [8] studies how a group reaches agreement on a common opinion (represented as a subjective probability distribution) through a linear update rule that iteratively computes weighted averages of the group members’ opinions. By interpreting the weight matrix as the transition matrix of a Markov chain, the work establishes a fundamental connection between the convergence of the opinion dynamics and the properties of the underlying Markov chain. This line of research gained significant momentum with the rise of networked control, multi-agent systems, and sensor networks. A central concept in this area is average consensus, where a group of nodes/agents seeks to agree on the average of their initial states using only local information exchange.1 The seminal work [9] formalizes 1 Due to differences in terminology in control and ML communities, we use the terms node, agent, and client interchangeably throughout the article.

2

average consensus as a linear iterative process and provides the necessary and sufficient conditions for convergence to the initial average. Several studies have revealed deep connections between consensus dynamics, spectral graph theory, and Markov chains [10], [11]. Later on, average consensus has been extensively studied under more realistic conditions, including time-varying random graphs [12]–[15], directed links [16]–[19], gossip communication [20]–[24], time delays [25]–[27], quantized updates [28]–[31], and link failures [32]– [35]. Beyond asymptotic convergence, a complementary line of work studies finite-time consensus that achieves exact agreement in a finite number of steps [36]–[41]. The simplicity and theoretical explainability of average consensus made it a fundamental building block for distributed optimization and learning. Integrating first-order optimization methods using gradient or subgradient with consensus averaging has led to the emergence of decentralized gradient descent (DGD) [42]. The basic principle is that each agent updates a local copy of the optimization variable by combining a gradient step on its local objective with a consensus step that incorporates information from neighbors. A key insight was that consensus drives agreement among agents, while gradient steps drive optimality. Subsequent research extended DGD to more realistic settings, including stochastic gradients [43], time-varying topologies and directed links [44], asynchronous communication [45], [46], and quantized updates [47], [48]. Distributed optimization provides the algorithmic foundation for collaborative ML over decentralized data, where multiple agents jointly optimize a global objective expressed as the sum of empirical risk functions defined over their local datasets. Depending on the network topology and system architecture, collaborative ML can be implemented in server-based, decentralized, or hierarchical (also called semidecentralized) settings (see Fig. 2). In a server-based architecture, such as Federated Learning (FL), a central parameter server (PS) aggregates local updates from distributed agents and updates the global model accordingly [49]. In decentralized systems, agents communicate only with local neighbors and often employ consensus mechanisms to enforce network-wide agreement on model parameters [50]. Hierarchical architectures [51], [52] combine intra-cluster aggregation among locally connected devices with inter-cluster aggregation assisted by higher-level servers/aggregators. Different network topologies and algorithmic designs introduce distinct communication flows within the network, through which information exchange contributes to the common goal of optimizing the global objective. B. Communication Constraints in Distributed Learning The ability of distributed agents to exchange information, update their states, and coordinate their actions through local interactions or server-assisted synchronization is fundamental to achieving system-level cooperation. The design of information mixing and the accuracy and frequency of communication directly influence the convergence, scalability, and robustness of distributed learning algorithms, particularly under data heterogeneity and resource constraints. As illustrated in Fig. 1, the communication interface is an integral part of the information

fusion process in distributed learning. In practical deployments, this interface operates over wireless networks subject to time-varying channel conditions, limited bandwidth and energy resources. These communication constraints necessitate the joint design of communication protocols and resource allocation schemes to ensure efficient and reliable operation. Consequently, communication should be treated as an essential component of the algorithm design rather than a secondary implementation detail. C. Purpose and Organization This tutorial provides a general introduction to the fundamentals of distributed consensus and optimization algorithms and underlines the connections between their convergence behavior and the design of information mixing mechanisms. The material complements existing tutorials on multi-agent consensus and cooperation [10], [53], first-order distributed optimization [54], and communication-efficient distributed learning [55]. Our focus in this article is on characterizing the joint impact of network topology, information flow, and communication uncertainties (including client scheduling, link failures, and compression) on distributed learning performance in practical settings. The remainder of the paper is organized as follows. Sec. II reviews the fundamentals of distributed linear consensus, including convergence conditions, weight design and optimization, the effects of imperfect communication, and ratio consensus over directed graphs. Sec. III presents classical distributed optimization algorithms, discusses steady-state errors and correction methods, and extends the discussion to collaborative ML with data sampling. Sec. IV examines sources of communication uncertainty and their impact on distributed learning performance, while Sec. V provides numerical illustrations of the theoretical results. Sec. VI reviews and categorizes communication-efficient methods. Finally, Sec. VII discusses open research questions and challenges, and Sec. VIII concludes the paper. D. Notation All vectors are column vectors. 1 is the vector of all ones (with dimension 𝑁). J = 𝑁1 11⊤ is the orthogonal projection onto span{1}. I𝑑 denotes the 𝑑 × 𝑑 identity matrix (or simply I when its dimension is clear from the context). |S| denotes the cardinality of a set S. For a vector a, a⊤ denotes its transpose and ∥a∥ its Euclidean norm. ∥ 𝐴∥ 2 denotes the 2-norm (or spectral norm) of the matrix 𝐴, and 𝜌( 𝐴) its spectral radius, which are defined below. Definition 1. Consider a matrix 𝐴 ∈ R 𝑁 × 𝑁 with eigenvalues 𝜆1 , . . . , 𝜆 𝑁 . The spectral radius of 𝐴 is defined as 𝜌( 𝐴) = max {|𝜆𝑖 |}.

(1)

𝑖=1,..., 𝑁

The spectral norm of the matrix is ∥ 𝐴∥ 2 = max ∥ 𝐴𝑥∥, ∥ 𝑥 ∥=1

(2)

which measures the maximum amplification of a vector by the matrix. It is also equal to the largest singular value of 𝐴. These two quantities have the following relations:

3

√︁ ∥ 𝐴∥ 2 = 𝜌( 𝐴⊤ 𝐴); • In general, 𝜌( 𝐴) ≤ ∥ 𝐴∥ 2 . When 𝐴 = 𝐴⊤ , 𝜌( 𝐴) = ∥ 𝐴∥ 2 .

•

It is easy to see that L1 = 0, i.e., 0 is an eigenvalue of L with corresponding eigenvector 1. Let Δ = max {𝑑𝑖 } 𝑖=1,..., 𝑁

II. F OUNDATIONS OF D ISTRIBUTED C ONSENSUS In this section, we present: (1) fundamental concepts in graph theory and spectral graph analysis (Sec. II-A); (2) key principles of distributed consensus, with a focus on average consensus implemented via linear iterative updates (Sec. II-B and II-C); (3) weight designs and convergence rate optimization (Sec. II-D); and (4) ratio consensus over directed graphs (Sec. II-F). Furthermore, we discuss how network connectivity and communication uncertainty influence the overall performance of consensus algorithms (Sec. II-E). A. Basics on Graphs and Spectral Graph Theory A graph G = (V, E) consists of a set of nodes (or vertices) V = {1, 2, . . . , 𝑁 } and a set of edges (or links) E ⊆ V × V. An edge (𝑖, 𝑗) ∈ E represents a direct communication link from node 𝑖 to node 𝑗. For undirected graphs, edges have no direction, then (𝑖, 𝑗) ∈ E implies ( 𝑗, 𝑖) ∈ E, ∀𝑖, 𝑗 ∈ V, meaning that direct communication is possible in both directions. For directed graphs (or digraphs), edges have directions, and (𝑖, 𝑗) ∈ E indicates that node 𝑖 can directly transmit information to node 𝑗, but not necessarily vice versa. If (𝑖, 𝑗) ∈ E, then: • node 𝑗 is an out-neighbor of node 𝑖; • node 𝑖 is an in-neighbor of node 𝑗. The in-neighbor and out-neighbor sets of each node 𝑖 ∈ V are defined by N𝑖in = { 𝑗 ∈ V |( 𝑗, 𝑖) ∈ E} and N𝑖out = { 𝑗 ∈ V |(𝑖, 𝑗) ∈ E}, respectively. The in-degree and out-degree of node 𝑖 are defined by 𝑑𝑖in = |N𝑖in | and 𝑑𝑖out = |N𝑖out |, respectively. For undirected graphs, the neighbor set is N𝑖 = N𝑖in = N𝑖out , and the degree of node 𝑖 is 𝑑𝑖 = |N𝑖 |. Definition 2. An undirected graph is connected if there exists a path between any pair of nodes 𝑖, 𝑗 ∈ V. A directed graph is strongly connected if there exists a path from every node 𝑖 ∈ V to every other node 𝑗 ∈ V. Next, we introduce two important matrix representations of a graph: the adjacency matrix and the graph Laplacian. Definition 3. The adjacency matrix of a graph G is the 𝑁 × 𝑁 square matrix A = [𝑎 𝑖 𝑗 ] given by  1 if ( 𝑗, 𝑖) ∈ E, 𝑎𝑖 𝑗 = (3) 0 otherwise. For undirected graphs, A is symmetric, i.e., A⊤ = A. In the remainder of this paper, we focus on undirected and connected graphs unless otherwise specified. Definition 4. The Laplacian matrix of an undirected graph is defined as L = D − A, where D = diag(𝑑1 , . . . , 𝑑 𝑁 ). Its elements are:  if 𝑖 = 𝑗,   𝑑𝑖  if ( 𝑗, 𝑖) ∈ E, L𝑖, 𝑗 = −1   0 otherwise. 

be the maximum node degree. According to the Gershgorin circle theorem, the eigenvalues of L are located within [0, 2Δ]. Furthermore, if the graph is connected, then 0 is a simple eigenvalue of L, and all other eigenvalues are strictly positive. B. Average Consensus over Time-Invariant Graphs Reaching a consensus refers to the process of reaching an agreement on a certain quantity of interest among a group of nodes. Let 𝑥𝑖 (0) represent the initial state value of node 𝑖 and let x(0) = [𝑥 1 (0), 𝑥2 (0), . . . , 𝑥 𝑁 (0)] ⊤ be the initial state value vector. Consensus is reached when the state vector converges to a point in the consensus subspace, i.e., the one-dimensional subspace C = span{1} = { 𝑐 1 : 𝑐 ∈ R }. In particular, the case where Í all state values converge to the initial network average 𝑁 𝑥𝑖 (0) is referred to as the average consensus. 𝑥¯ = 𝑁1 𝑖=1 The most fundamental algorithm for achieving average consensus is the following iterative update rule ∑︁ 𝑤 𝑖 𝑗 𝑥 𝑗 (𝑡), (4) 𝑥𝑖 (𝑡 + 1) = 𝑤 𝑖𝑖 𝑥𝑖 (𝑡) + 𝑗 ∈ N𝑖

where 𝑤 𝑖 𝑗 is the weight that node 𝑖 assigns to the information (state value) received from node 𝑗 and 𝑤 𝑖𝑖 is the self weight. This means that a node updates its state for the next iteration by averaging its own state value and the neighbors’ state values in the current iteration. Note that 𝑤 𝑖 𝑗 = 0 if ( 𝑗, 𝑖) ∉ E and 𝑖 ≠ 𝑗. Putting all node states in a vector, this linear iteration can be written in matrix form as x(𝑡 + 1) = Wx(𝑡),

(5)

where W = [𝑤 𝑖 𝑗 ] 𝑖, 𝑗 ∈ V . This matrix is often referred to as the mixing matrix, or weight matrix, or combination matrix. To reach average consensus asymptotically, all nodes’ state values need to converge to the average of initial values 𝑥¯ = 𝑁1 1⊤ x(0). This means 1 lim W𝑡 = 11⊤ ≜ J. (6) 𝑡→∞ 𝑁 According to the analysis in [9], (6) is achieved if the following spectral conditions on W are satisfied. Assumption 1 (Spectral Conditions on Mixing Matrix). The mixing matrix 𝑊 is assumed to satisfy the following conditions: W1 = 1, 1⊤ W = 1⊤ , 𝜌 (W − J) < 1, (7) where 𝜌(·) is the spectral radius. The first condition implies that every vector in the consensus subspace is a fixed point of the mapping described in (5). The second condition ensures that every consensus step preserves the average value (or the total mass) across the network, i.e., 1⊤ x(𝑡 + 1) = 1⊤ x(𝑡). Let 𝜆𝑖 (W), 𝑖 = 1 . . . 𝑁, denote the eigenvalues of W. Obviously, we have 𝜆1 (𝑊) = 1. The last condition imposes the requirement that all other eigenvalues lie strictly within the unit circle. This implicitly requires that the graph is connected. Under Assumption 1, we have 𝜌 (W − J) = max{|𝜆 𝑖 (W)|}, which is the second largest 𝑖≥2

eigenvalue modulus of W, sometimes denoted as 𝜆+2 .

4

Remark 1. An undirected graph (with a symmetric adjacency matrix) does not necessarily imply a symmetric mixing matrix. The spectral conditions in Assumption 1 do not require W to be non-negative or symmetric to ensure convergence to average consensus. However, assuming non-negativity and symmetry simplifies the convergence analysis of distributed consensus and optimization algorithms, which will be discussed later. The ideal consensus state is given by x̄ = 𝑥1 ¯ = Jx(0), which is the orthogonal projection of the initial state onto the consensus subspace C = span{1}. To characterize convergence, we define the disagreement vector as δ(𝑡) = (I − J)x(𝑡), which satisfies 1⊤ δ(𝑡) = 0. Since the network average is preserved, δ(𝑡) = x(𝑡) − x̄. For a fixed mixing matrix W satisfying Assumption 1, the disagreement evolves according to δ(𝑡 + 1) = (W − J)δ(𝑡).

(8)

Consequently, asymptotic average consensus is achieved for any initial state if and only if 𝜌(W − J) < 1. The convergence speed of the distributed linear iteration in (5) can be characterized by the following two metrics [9]: • asymptotic convergence factor  1/𝑡  ∥x(𝑡) − x̄∥ = 𝜌 (W − J) ; 𝑅asym (W) = sup lim x (0)≠x̄ 𝑡→∞ ∥x(0) − x̄∥ (9) • per-step convergence factor ∥x(𝑡 + 1) − x̄∥ = W − J 2. ∥x(𝑡) − x̄∥ x (𝑡 )≠x̄

𝑅step (W) = sup

(10)

•

doubly stochastic if 𝐴1 = 1 and 1⊤ 𝐴 = 1⊤ .

Furthermore, if the mixing matrix W is doubly stochastic and primitive, then 𝜌(W) = 1 is its Perron eigenvalue, and u = v = √1 1 are the corresponding (normalized) left and right 𝑁 Perron eigenvectors. It follows directly that lim W𝑡 = 𝑁1 11⊤ . 𝑡→∞ Then, average consensus is achieved asymptotically. Remark 2. Not all doubly stochastic matrices with a strongly connected communication graph are primitive. An example is W = [0 1; 1 0], which swaps the state values of two connected nodes. W has two eigenvalues (1 and −1) with maximum modulus. Obviously, lim W𝑡 does not exist. 𝑡→∞

Remark 3. A doubly stochastic mixing matrix satisfying the conditions in Assumption 1 can still be asymmetric even when the underlying communication graph is undirected. However, numerous studies still rely on the symmetric mixing assumption, in which case all eigenvalues are real-valued, and the matrix is orthogonally diagonalizable. For this reason, in Sec. III, we primarily focus on doubly stochastic and symmetric mixing matrices. D. Mixing Matrix Design In this subsection, we review some commonly adopted mixing matrix designs and show how the mixing weights can be optimized to achieve faster convergence. Two commonly considered mixing matrix designs are: 1) Constant edge weights: 𝑤 𝑖 𝑗 = 𝛽, ∀( 𝑗, 𝑖) ∈ E,

C. Doubly Stochastic Matrix and Perron-Frobenius Theorem In a special case where W is primitive (hence, non-negative, see Definition 5 and discussions thereafter), the dominant eigenvalue is real, positive, and simple. Then the limit of W𝑡 can be analyzed using the Perron-Frobenius theorem. Definition 5. A square matrix 𝐴 ∈ R 𝑁 × 𝑁 is non-negative if all entries 𝐴𝑖, 𝑗 ≥ 0, ∀𝑖, 𝑗. An important property of non-negative matrices is that the spectral radius 𝜌( 𝐴) is an eigenvalue. A non-negative matrix is irreducible if its associated directed graph is strongly connected. Then, by Perron–Frobenius theorem [56, Th. 8.4.4], 𝜌( 𝐴) is a simple eigenvalue (with algebraic multiplicity 1). An irreducible non-negative matrix is primitive if it has only one eigenvalue with maximum modulus (i.e., 𝜆1 = 𝜌( 𝐴)), and all other eigenvalues satisfy |𝜆𝑖 | < 𝜌( 𝐴), 𝑖 = 2, . . . , 𝑁. Theorem 1. [56, Th. 8.5.1] If a non-negative matrix 𝐴 ∈ R 𝑁 × 𝑁 is primitive, with left and right eigenvectors u and v associated to the Perron eigenvalue 𝜆1 = 𝜌( 𝐴), respectively, satisfying 𝐴v = 𝜆1 v, u⊤ 𝐴 = 𝜆1 u⊤ , normalized such that v⊤ u = 1, then lim 𝐴𝑡 /𝜆𝑡1 = vu⊤ . 𝑡→∞

Definition 6. A non-negative matrix 𝐴 ∈ R 𝑁 × 𝑁 is called row-stochastic if 𝐴1 = 1; • column-stochastic if 1⊤ 𝐴 = 1⊤ ; •

where 𝛽 is chosen such that 0 < 𝛽 < 1/Δ, with Δ = max {𝑑𝑖 }. 𝑖=1,..., 𝑁

2) Local-degree weights (Metropolis): 𝑤𝑖 𝑗 =

1 , ( 𝑗, 𝑖) ∈ E. 1 + max{𝑑𝑖 , 𝑑 𝑗 }

In both cases, the self-weights are chosen as 𝑤 𝑖𝑖 = 1 − Í 𝑗 ∈ N𝑖 𝑤 𝑖 𝑗 , thus the mixing matrix W is doubly stochastic. In particular, for the case with constant edge weights, we have W = I − 𝛽L.

(11)

As a result, the 𝑖-th eigenvalue (ranked in decreasing order) of W is 𝜆𝑖 (W) = 1 − 𝛽𝜆𝑖 (L), where 𝜆𝑖 (L) is the 𝑖-th eigenvalue of graph Laplacian L, ranked in increasing order. It is easy to see that this design of W satisfies all the conditions in Assumption 1 when the graph is connected. In the general case, the mixing matrix can be optimized by solving the following optimization problem, aiming to minimize the asymptotic convergence factor (9): minimize

𝜌 (W − J)

(12a)

subject to

W1 = 1, 1⊤ W = 1⊤ ,

(12b)

W ∈ S.

(12c)

S imposes a sparsity pattern that is consistent with the underlying communication graph, i.e., S = {W ∈ R 𝑁 × 𝑁 [W] 𝑖, 𝑗 = 0 if ( 𝑗, 𝑖) ∉ E, and 𝑖 ≠ 𝑗 }. However, the spectral radius

5

is a non-convex objective in general. Since 𝜌(A) ≤ ∥A∥ 2 , an alternative consideration is to minimize the spectral norm (equivalent to minimizing the per-step convergence factor (10)): minimize ∥W − J∥ 2 , subject to (12b) − (12c). This can be transformed into a semi-definite programming (SDP) problem [9], solvable using standard convex optimization tools: minimize

𝑠 

𝑠I subject to W⊤ − 11⊤ /𝑁 (12b) − (12c).

(13a)  W − 11⊤ /𝑁 ⪰ 0 (13b) 𝑠I (13c)

When W is symmetric, (13b) becomes −𝑠I ⪯ W−11⊤ /𝑁 ⪯ 𝑠I. E. Consensus with Communication Uncertainty So far, we have focused on deterministic settings, where every node communicates with its neighbors at every iteration and all transmitted messages are received without error. We now briefly discuss extensions to time-varying mixing matrices and noisy communications. 1) Time-Varying Mixing: The mixing matrix W(𝑡) may vary over time for several reasons: • network topology changes over time (due to, for instance, node mobility and time-varying channel conditions); • communication decisions change over time, as in asynchronous communication frameworks, such as randomized gossip or other forms of communication scheduling; • transmission outcomes change over time, due to packet losses or link failures. In the first two cases, the stochasticity conditions on the mixing matrix can be enforced, and the convergence behavior can be analyzed by studying the infinite product of random stochastic matrices and its connections to the ergodicity of non-homogeneous Markov chains [12], [14], [57]. However, in the last case, additional mechanisms need to be applied to compensate for the information loss and ensure convergence [32], [35], [58]. 2) Consensus with Noisy Communication: When nodes exchange their state values, the communication can be noisy, for instance, due to either additive noise in the channel or quantization noise in the compression process. In the presence of additive communication noise, the consensus iteration can be expressed as ∑︁ 𝑥𝑖 (𝑡 + 1) = 𝑤 𝑖𝑖 𝑥 𝑖 (𝑡) + 𝑤 𝑖 𝑗 𝑥 𝑗 (𝑡) + 𝑒 𝑖 (𝑡), (14) 𝑗 ∈ N𝑖

where 𝑒 𝑖 (𝑡) denotes the effective noise at node 𝑖, which may represent either node-specific receiver noise or the aggregate contribution of noise from its incoming communication links. Under the assumption that the additive noise is independent and identically distributed (i.i.d.) across nodes and iterations, with zero mean and finite variance, it was shown in [59] that the mean-square deviation from the instantaneous network average converges to a finite steady-state value, even though the network average itself evolves as an unbounded random walk.

For link-level additive noise, subsequent studies have established that stochastic approximation algorithms with diminishing stepsizes can achieve almost sure consensus, with all node states converging to a common random limit [34], [60]. This limiting value is unbiased only in expectation, and it generally differs from the exact average in any single realization due to the accumulated noise over time. Furthermore, a leakage-based algorithm was introduced in [61] to mitigate this random bias by incorporating the initial value into the consensus updating rule, and a similar mechanism was adopted in [62] for directed graphs. Recently, [63] reformulated average consensus as a distributed optimization problem and derived a noise-resilient linear recursion from a noisy DGD perspective, providing a unified interpretation of several existing approaches. Another source of communication error is quantization. Let Q denote a quantization operator, with the quantization error at node 𝑖 defined as 𝑒 𝑖 (𝑡) = Q (𝑥 𝑖 (𝑡)) − 𝑥 𝑖 (𝑡). For deterministic quantizers, the error generally depends on the local state and may introduce systematic bias. In contrast, randomized or dithered quantizers can be designed to produce conditionally zero-mean errors. Stochastic approximation algorithms with diminishing stepsizes can mitigate the effects of unbiased quantization errors, whereas persistent quantization bias may require additional compensation mechanisms. F. Ratio Consensus over Directed Graphs Common consensus algorithms developed for undirected graphs rely on the symmetry of information flows between nodes. If an undirected graph is connected, we can construct a doubly stochastic and primitive mixing matrix that is compatible with the graph topology. This ensures that the total mass (or average) of the node states is preserved and that all nodes asymptotically converge to the exact average of their initial values. However, in directed graphs, communication is generally asymmetric, and computing a doubly stochastic mixing matrix using only local information is challenging and may require additional weight-balancing mechanisms; see, for example, [30], [64]–[66] and references therein. As a result, standard average consensus algorithms no longer preserve the total mass, and the algorithm may converge to a biased value or fail to converge. One approach to overcome this limitation is ratio consensus (or push sum) by augmenting the state at each node with an additional variable and applying the same column-stochastic mixing weights to both states, so that the ratio of the two variables converges to the desired average [20], [27], [67], [68]. A more thorough discussion of distributed averaging (including ratio consensus) and balancing in directed graphs can be found in [19]. III. F OUNDATIONS OF D ISTRIBUTED O PTIMIZATION Distributed optimization aims to cooperatively minimize a global objective expressed as an aggregate of local functions across distributed nodes/agents. It is a key enabler of modern large-scale ML, particularly in federated and decentralized settings where data are distributed across heterogeneous agents. Consider a network of 𝑁 agents connected through a communication graph G = (V, E), where each agent 𝑖 ∈ V holds a

6

private local objective function 𝑓𝑖 : R𝑑 → R. The problem of interest is 𝑥★ ∈ arg min 𝐹 (𝑥), 𝑥 ∈R𝑑

𝐹 (𝑥) ≜

1 ∑︁ 𝑁 𝑁

𝑓𝑖 (𝑥).

(15)

𝑖=1

Since the local objective functions are not shared, each agent performs local computations based on its own objective and exchanges local estimates of the optimization variables with its neighbors (Fig. 1). Consensus mechanisms coordinate these local estimates, enabling the agents to iteratively approach the global optimizer in a fully distributed manner. In this section, we introduce the algorithmic foundations of distributed optimization, starting with DGD and its stochastic counterpart (DSGD). We then discuss steady-state bias and representative techniques for achieving exact convergence, followed by several extensions beyond the classical DGD/DSGD framework. Finally, we connect distributed optimization to distributed learning using a unified cooperative SGD framework for different communication architectures. First, we impose a set of standard assumptions. Assumption 2 (Network Connectivity). The communication graph G = (V, E) is connected. Assumption 3 (Mixing Matrix). The mixing matrix W is symmetric (W⊤ = W), doubly stochastic, with 𝜌 (W − J) < 1. A symmetric matrix has real-valued eigenvalues. Under this assumption, the eigenvalues of W can be sorted as 1 = 𝜆1 > 𝜆2 ≥ · · · ≥ 𝜆 𝑁 > −1. Assumption 4 (Strong Convexity). Each local objective function 𝑓𝑖 : R𝑑 → R is 𝜇-strongly convex, i.e., 𝜇 𝑓𝑖 (𝑦) ≥ 𝑓𝑖 (𝑥) + ∇ 𝑓𝑖 (𝑥) ⊤ (𝑦 − 𝑥) + ∥𝑥 − 𝑦∥ 2 , ∀𝑥, 𝑦 ∈ R𝑑 , (16) 2 for some constant 𝜇 > 0. Strong convexity ensures that the global objective 𝐹 (𝑥) admits a unique minimizer 𝑥★. This property is crucial for establishing linear convergence rates for distributed algorithms with constant stepsizes. In the absence of strong convexity, convergence guarantees typically weaken to sublinear rates or stationarity conditions. Assumption 5 (Smoothness). Each local objective function 𝑓𝑖 is 𝐿-smooth, i.e., its gradient is Lipschitz continuous with parameter 𝐿: ∥∇ 𝑓𝑖 (𝑥) − ∇ 𝑓𝑖 (𝑦) ∥ ≤ 𝐿 ∥𝑥 − 𝑦∥,

∀𝑥, 𝑦 ∈ R𝑑 .

(17)

Smoothness limits how rapidly the gradient can change with respect to the optimization variables, making it a key assumption in the convergence analysis of distributed firstorder methods. These assumptions represent the classical setting of distributed optimization over undirected graphs with simple consensus-based algorithms such as DGD and DSGD. Extensions to directed communication graphs require modified consensus mechanisms, as discussed in Sec. III-D.

A. Distributed Gradient Descent (DGD) The classical DGD algorithm generalizes gradient descent to multi-agent networks via a consensus–optimization iteration. Each agent 𝑖 maintains a local variable 𝑥𝑖 (𝑡) updated by ∑︁ 𝑁 𝑤 𝑖 𝑗 𝑥 𝑗 (𝑡) − 𝛼𝑡 ∇ 𝑓𝑖 (𝑥 𝑖 (𝑡)) , (18) 𝑥 𝑖 (𝑡 + 1) = 𝑗=1

where W = [𝑤 𝑖 𝑗 ] 𝑖, 𝑗 ∈ [ 𝑁 ] is the mixing matrix, ∇ 𝑓𝑖 (𝑥 𝑖 (𝑡)) is the gradient of the local objective function evaluated at the current iterate, and 𝛼𝑡 is the stepsize (or learning rate). Since each agent maintains its local copy 𝑥 𝑖 (𝑡) of the decision variable and computes gradients using its own local objective, the local parameters generally differ across the network. By stacking the local parameters over the network, we can rewrite it as x(𝑡 + 1) = (W ⊗ I𝑑 )x(𝑡) − 𝛼𝑡 ∇f (x(𝑡)),

(19)

where x(𝑡) = [𝑥 1 (𝑡) ⊤ , . . . , 𝑥 𝑁 (𝑡) ⊤ ] ⊤ ∈ R 𝑁 𝑑 collects all local parameters in one vector, and ∇f (x(𝑡)) = [∇ 𝑓1 (𝑥1 (𝑡)) ⊤ , . . . , ∇ 𝑓 𝑁 (𝑥 𝑁 (𝑡)) ⊤ ] ⊤ collects all local gradient vectors in the same order. Under Assumptions 2, 3, 4, and 5, with constant stepsize 𝛼𝑡 = 𝛼 ≤ (1 + 𝜆 𝑁 )/(𝜇 + 𝐿), the squared error (SE) of DGD is bounded as [69] 𝑁 𝑁 2 ∑︁ 𝛼2 𝜅 2 Δ𝑏 1 ∑︁ ∥𝑥𝑖 (𝑡)−𝑥★ ∥ 2 ≤(1−𝛼𝜇) 2𝑡 ∥𝑥𝑖 (0)−𝑥★ ∥ 2 +8 , 𝑁 𝑖=1 𝑁 𝑖=1 (1−𝜆2 ) 2 (20) where 𝜅 = 𝐿/𝜇 is the condition number and Δ𝑏 ≜ 1 Í𝑁 ★) ∥ 2 measures gradient heterogeneity at the ∥∇ 𝑓 (𝑥 𝑖 𝑖=1 𝑁 global optimum, i.e., local and global optima do not coincide. Therefore, DGD converges linearly to a neighborhood of the global optimum 𝑥★, with contraction factor (1 − 𝛼𝜇) 2 . This limiting neighborhood is the steady-state bias caused by persistent disagreement across the network, and its size depends on the stepsize 𝛼, the spectral properties of W (second largest eigenvalue 𝜆2 ), and gradient heterogeneity Δ𝑏.2 On the other hand, with a properly chosen diminishing stepsize sequence 𝛼𝑡 = O (1/𝑡), the iterates converge to the exact optimizer, with the SE satisfying 1 ∑︁ 𝑁 ∥𝑥𝑖 (𝑡) − 𝑥★ ∥ 2 = O (1/𝑡 2 ). (21) 𝑖=1 𝑁

Note that there are variants of decentralized gradient-based methods other than (19), such as 1) Adapt-then-Combine (ATC) diffusion:  x(𝑡 + 1) = (W ⊗ I𝑑 ) x(𝑡) − 𝛼𝑡 ∇f (x(𝑡)) ; 2) Combine-then-Adapt (CTA) diffusion: x(𝑡 + 12 ) = (W ⊗ I𝑑 )x(𝑡), x(𝑡 + 1) = x(𝑡 + 21 ) − 𝛼𝑡 ∇f (x(𝑡 + 12 )). The main differences lie in whether the consensus operation is applied before or after the gradient step, and at which model the gradient is evaluated. As a result, these methods require different stability and convergence conditions. Nevertheless, all of them suffer from a steady-state bias under constant stepsizes, caused by gradient dissimilarity. 2 Here, the factor 1/(1 − 𝜆 ) = ∥ (I − W) † ∥ characterizes the network 2 2 dependence of the DGD steady-state error bound. One should not confuse 𝜆2 with the consensus contraction factor 𝜌(W − J) = max{ |𝜆2 |, |𝜆 𝑁 | }.

7

B. Distributed Stochastic Gradient Descent (DSGD) In DSGD, at each iteration 𝑡, agent 𝑖 does not have access to the exact gradient ∇ 𝑓𝑖 (𝑥𝑖 (𝑡)) at its current local iterate 𝑥 𝑖 (𝑡), but instead observes a noisy first-order oracle 𝑔𝑖 (𝑡) = ∇ 𝑓𝑖 (𝑥 𝑖 (𝑡)) + 𝜁𝑖 (𝑡), where 𝜁𝑖 (𝑡) is a random perturbation process capturing uncertainty in the gradient information. Such uncertainty arises from, for example, mini-batch sampling or streaming data in online learning settings (see more detailed discussions in Sec. III-E). The DSGD update rule is then 𝑥𝑖 (𝑡 + 1) =

𝑁 ∑︁

𝑤 𝑖 𝑗 𝑥 𝑗 (𝑡) − 𝛼𝑡 𝑔𝑖 (𝑡),

(22)

𝑗=1

which replaces the exact gradient in (18) with its stochastic approximation. In compact vector form, x(𝑡 + 1) = (W ⊗ I𝑑 )x(𝑡) − 𝛼𝑡 g(𝑡),

(23)

where g(𝑡) denotes the stacked local gradient estimators. In addition to the steady-state bias inherent to DGD, stochastic gradient noise introduces a second source of asymptotic error. Hence, rather than converging deterministically to the limiting neighborhood, the iterates exhibit persistent random fluctuations around it. As a result, the steady-state mean-square error (MSE) increases, yielding a larger asymptotic error than in the deterministic setting (see (25)). To study the convergence of DSGD, we introduce some additional assumptions. Assumption 6. The stochastic gradient 𝑔𝑖 (𝑡) is a conditionally unbiased estimator of the exact gradient ∇ 𝑓𝑖 (𝑥𝑖 (𝑡)), with finite 2 . That is, variance 𝜎sg E [𝑔𝑖 (𝑡) | x(𝑡)] = ∇ 𝑓𝑖 (𝑥𝑖 (𝑡)),   2 E ∥𝑔𝑖 (𝑡) − ∇ 𝑓𝑖 (𝑥𝑖 (𝑡)) ∥ 2 | x(𝑡) ≤ 𝜎sg .

(24a) (24b)

Under Assumptions 2-6, and a sufficiently small constant stepsize 𝛼𝑡 = 𝛼, DSGD converges linearly to a neighborhood of the global minimizer 𝑥★, with steady-state error bounded as [69, Sec. V.A]: # " 𝑁 2 𝛼𝜎sg 1 ∑︁ 𝛼2 𝜅 2 Δ𝑏 ★ 2 ∥𝑥 𝑖 (𝑡) − 𝑥 ∥ ≤ 2 +2 . (25) lim sup E 𝑁 𝑖=1 𝜇 (1 − 𝜆 2 ) 2 𝑡→∞ The first term in (25) reflects the impact of stochastic gradient noise and matches the steady-state behavior of centralized SGD, while the second term is a heterogeneity-induced bias, observed also in noiseless DGD. This asymptotic error floor can be mitigated by using diminishing stepsizes, 𝛼𝑡 = O (1/𝑡). In this case, DSGD achieves MSE convergence to 𝑥★ at a sublinear rate of O (1/𝑡), requiring O (1/𝜖) iterations to reach 𝜖-accuracy [70], [71]. This rate is slower than DGD with exact gradient computation, due to the impact of gradient noise. These observations highlight several fundamental challenges of DGD/DSGD: • Objective Heterogeneity: When the local objective functions differ, gradient heterogeneity may introduce a persistent optimization bias, resulting in a nonzero error floor

under a constant stepsize and preventing exact convergence to the global optimum. • Gradient Noise: Stochastic gradients introduce persistent random fluctuations around the limiting neighborhood, increasing the steady-state error (under a constant stepsize), or slowing convergence (O (1/𝑡) vs O (1/𝑡 2 ) with diminishing stepsizes). • Network Dependence: The asymptotic error bound scales as (1 − 𝜆2 ) −2 , indicating greater sensitivity to gradient heterogeneity in poorly connected networks (e.g., sparse or high-diameter graphs). C. Gradient Tracking and Variance Reduction To overcome the limitations of DGD/DSGD, modern distributed learning methods augment the basic framework with two key techniques, each targeting the two main sources of steady-state error of DSGD: gradient heterogeneity (Δ𝑏) and 2 ). stochastic gradient variance (𝜎sg 1) Gradient Tracking (GT): Each agent 𝑖 holds Í a local estimate 𝑦 𝑖 (𝑡) of the global average gradient 𝑁1 𝑁𝑗=1 ∇ 𝑓 𝑗 (𝑥 𝑗 (𝑡)), evaluated at the agents’ current local iterates [72]–[75]. Using this estimate, agent 𝑖 updates its local model according to 𝑥𝑖 (𝑡 + 1) =

𝑁 ∑︁

𝑤 𝑖 𝑗 𝑥 𝑗 (𝑡) − 𝛼𝑡 𝑦 𝑖 (𝑡),

(26)

𝑗=1

where the term −𝛼𝑡 𝑦 𝑖 (𝑡) plays the role of a gradient descent step with respect to the global objective function. After the model update is performed, each agent updates its gradient-tracking variable as 𝑦 𝑖 (𝑡 + 1) =

𝑁 ∑︁

𝑤 𝑖 𝑗 𝑦 𝑗 (𝑡) + ∇ 𝑓𝑖 𝑥𝑖 (𝑡 + 1) − ∇ 𝑓𝑖 𝑥𝑖 (𝑡) . (27)

𝑗=1

This recursion combines consensus on local gradient estimates with a correction term that compensates for the variation in local gradients caused by the model updates.3Í Initializing 𝑁 1 𝑦 𝑖 (0) = ∇ 𝑓𝑖 𝑥 𝑖 (0),
the recursion preserves 𝑁 𝑖=1 𝑦 𝑖 (𝑡) = 1 Í𝑁 𝑖=1 ∇ 𝑓𝑖 𝑥 𝑖 (𝑡) . 𝑁 With GT, the local gradient ∇ 𝑓𝑖 (𝑥 𝑖 (𝑡)) in DGD is replaced by a tracked global gradient estimate 𝑦 𝑖 (𝑡). By employing dynamic average consensus to track time-varying local gradients, GT estimates the global gradient at each agent without centralized coordination. This decouples consensus from optimization and eliminates the bias term Δ𝑏, enabling exact convergence to 𝑥★ under noiseless updates despite gradient heterogeneity. However, this improvement requires additional communication overhead, as agents must exchange both local model variables and global gradient estimates. 2) Variance Reduction (VR): Persistent gradient noise of SGD can be reduced by constructing unbiased estimators whose variance diminishes as the iterates approach the global optimum. To conceptually illustrate the idea, we focus on SAGA [76] in a server-based architecture, with stochasticity arising from random client/agent selection while assuming 3 For simplicity, we focus on the case where local gradient computations are noiseless, although the framework can be extended to noisy gradients in a manner similar to DSGD.

8

exact local gradient computations. More specifically, the PS maintains a table of past local gradients, with one entry per agent, which is updated incrementally over time. At iteration 𝑡, a single agent index 𝑖 𝑡 ∈ {1, . . . , 𝑁 } is selected uniformly at random, and the SAGA gradient estimator is formed as Í 𝑔(𝑡) ˜ = ∇ 𝑓𝑖𝑡 (𝑥(𝑡)) − ∇ 𝑓𝑖𝑡 ( 𝑥˜𝑖𝑡 ) + 𝑁1 𝑁𝑗=1 ∇ 𝑓 𝑗 ( 𝑥˜ 𝑗 ), (28) where ∇ 𝑓 𝑗 ( 𝑥˜ 𝑗 ) denotes the gradient stored in memory for agent 𝑗, evaluated at its most recent reference point 𝑥˜ 𝑗 . After the gradient estimator is formed, the memory table is updated by refreshing only the entry corresponding to the selected agent 𝑖 𝑡 . Specifically, the reference point and stored gradient are updated as 𝑥˜𝑖𝑡 ← 𝑥(𝑡), and ∇ 𝑓𝑖𝑡 ( 𝑥˜𝑖𝑡 ) ← ∇ 𝑓𝑖𝑡 (𝑥(𝑡)), respectively, while all other memory entries remain unchanged. It is easy to see that 𝑔(𝑡) ˜ is an unbiased estimate of the global gradient, i.e., with respect to the h taking the expectation i 𝑁 client selection, E 𝑔(𝑡)|𝑥(𝑡), ˜ {𝑥˜ 𝑗 } 𝑗=1 = ∇𝐹 (𝑥(𝑡)). Moreover, as 𝑥(𝑡), 𝑥˜ 𝑗 → 𝑥★, ∀ 𝑗, the variance of 𝑔(𝑡) ˜ vanishes, and hence 𝑔(𝑡) ˜ → ∇𝐹 (𝑥★) = 0. Another related method is Stochastic Variance Reduced Gradient (SVRG) [77], which uses a periodically updated snapshot point and its full gradient as a control variate. Unlike SAGA, SVRG avoids storing one gradient per agent but requires periodic full-gradient aggregation. Extensions of both methods can also incorporate stochastic or mini-batch local gradients, thereby effectively reducing variance due to both client and data sampling. Remark 4. For both SVRG and SAGA, the variance of the gradient estimator vanishes as the algorithm converges to the optimum. Consequently, for smooth and strongly convex objectives, these variance reduction methods achieve linear convergence with constant stepsizes, comparable to deterministic gradient descent, while maintaining a low per-iteration computational cost through stochastic gradient evaluations. 3) Variance Reduction for Graph-Structured Networks: Variance reduction methods do not directly extend to graphstructured networks. For example, with SVRG, exact computation of the global gradient at the snapshot point would require running a consensus procedure to convergence, which incurs significant communication overhead and undermines the communication efficiency of SVRG. This limitation has motivated the development of decentralized variance-reduction methods that replace exact global gradient computation with gradient tracking (or dynamic consensus mechanisms), enabling variance reduction while preserving localized communication and fully distributed operation. Combining gradient tracking with variance reduction yields algorithms such as GT-SAGA and GT-SVRG [78], which operate on undirected and weight-balanced directed graphs. Under the assumption of a primitive and doubly stochastic mixing matrix W (not necessarily symmetric), they achieve: • Exact Linear Convergence: For strongly-convex and smooth objectives, these methods converge linearly to the exact optimum 𝑥★ with constant stepsizes. • Sample Complexity: The total number of local gradient computations per agent to achieve a target level 𝜖 of

MSE accuracy is O (max{𝑀, 𝜅 2 (1− ∥W−J∥ 2 ) −2 } log(1/𝜖)), where 𝑀 is the number of data samples per agent [78, Theorem 1]. D. Beyond the Classic DGD/DSGD Framework Practical distributed learning departs from the classical DGD/DSGD framework through several important relaxations, including time-varying topologies, directed information flows, and asynchronous operation. In what follows, we briefly review representative extensions along these directions. • Time-varying topologies: In practice, the communication graph often evolves over time due to agent mobility, intermittent participation, link failures, or dynamic scheduling policies. Although the resulting communication patterns vary across iterations, convergence can still be established under suitable connectivity assumptions [44], [82]. • Directed communication links: Communication networks may exhibit asymmetric information flows, due to heterogeneous transmit powers or unidirectional communication links. In such settings, the mixing matrix may no longer be symmetric or doubly stochastic. Directed-network algorithms rely on additional mechanisms, such as pushsum normalization (see Sec. II-F) [23], weight-balancing techniques [30], or separate row- and column-stochastic mixing matrices. Under suitable connectivity assumptions, these methods still achieve exact convergence [81], [83]. • Asynchronous operation: Heterogeneous computation capabilities and communication delays often prevent synchronous operation. Asynchronous algorithms allow agents to compute and update independently without waiting for all others to complete each iteration. However, stale information and delayed updates complicate the convergence analysis and may slow convergence. Representative approaches include [84], [85]. Table I summarizes classical DGD/DSGD algorithms and the representative extensions, highlighting their mixing strategies, noise models, stepsize design, convergence rates, and optimality guarantees. E. From Optimization to Learning The most prominent application of distributed optimization is collaborative training of ML models over decentralized data. In such settings, the global objective is often expressed as the empirical risk evaluated over the ensemble of all local datasets. Consider a supervised ML model 𝑝 𝑥 : F → Y parameterized by a vector 𝑥 ∈ R𝑑 that maps an input feature vector 𝜙 ∈ F to an output label 𝑦 ∈ Y. Given a dataset of 𝑀tot datapoints (input-output pairs) D = {(𝜙 𝑚 , 𝑦 𝑚 )} 𝑚=1,...,𝑀tot , and the loss function ℓ : Y × Y → R, the empirical risk over the dataset D is defined as 1 ∑︁ 𝑀tot ℓ(𝑦 𝑚 , 𝑝 𝑥 (𝜙 𝑚 )). (29) R (𝑥; D) = 𝑚=1 𝑀tot The goal of model training is to find the parameter vector 𝑥★ that minimizes the empirical risk: 𝑥★ = arg min R (𝑥; D). 𝑥 ∈R𝑑

(30)

9

TABLE I: Representative distributed first-order optimization algorithms and their convergence properties, under the assumptions of strongly convex and smooth local objectives. Algorithm

Mixing

Noise Source

Stepsize

DGD Doubly stoch. — Constant DGD Doubly stoch. — Diminishing DSGD Doubly stoch. Gradient Diminishing DSGD Doubly stoch. Random links/gradient Diminishing DSGD Doubly stoch. Comm. noise/gradient Diminishing DIGing (DGD-GT) Doubly stoch. Time-varying network Constant GT-SVRG/SAGA Doubly stoch. Gradient Constant EXTRA Doubly stoch. — Constant Push-DIGing Column stoch. Time-varying network Constant AB/Push-Pull Row-/Column-stoch. — Constant

In a distributed setting with 𝑁 agents, each agent holds a local dataset D𝑖 = {(𝜙𝑖𝑚 , 𝑦 𝑖𝑚 )} 𝑚=1,..., 𝑀𝑖 with 𝑀𝑖 data samples. Thus, 𝑁 the global dataset in the entire network is D = ∪𝑖=1 D𝑖 . The local objective can be written as 𝑓𝑖 (𝑥) = R (𝑥; D𝑖 ), and the global objective takes the form ∑︁ 𝑁 𝑀𝑖 𝑓𝑖 (𝑥), (31) 𝐹 (𝑥) = 𝑖=1 𝑀tot Í𝑁 where 𝑀tot = 𝑖=1 𝑀𝑖 is the total number of training samples in the system. Note that 𝐹 (𝑥) is equivalent to the empirical risk R (𝑥; D) over the global dataset, defined in (29). A key distinction with respect to the formulation in (15) is that the contribution of agent 𝑖 is weighted proportionally to its local dataset size, 𝑀𝑖 /𝑀tot , rather than uniformly by 1/𝑁. This mismatch can be readily addressed by rescaling the local objective functions 𝑓𝑖 (·) by a factor of 𝑁 𝑀𝑖 /𝑀tot . For simplicity of exposition, we henceforth assume that all agents hold datasets of equal size, i.e., 𝑀𝑖 = 𝑀 for all 𝑖. The empirical risk minimization problem in (30) can then be addressed using the algorithmic frameworks presented in Sec. III, across all distributed learning architectures depicted in Fig. 2. In large-scale ML with a massive amount of training data (𝑁 · 𝑀 ≫ 1), mini-batch sampling is often applied to reduce the cost of gradient computation. At each iteration, each agent computes its local gradient using only a single datapoint or a small mini-batch, rather than the full local dataset. This data sampling process introduces noise in the gradient computation. Specifically, in the local training step, each agent 𝑖 obtains a stochastic gradient under the current local model 𝑥𝑖 as 𝑔𝑖 = ∇R (𝑥𝑖 ; 𝜉𝑖 ),

(32)

where 𝜉𝑖 ⊆ D𝑖 is the randomly sampled mini-batch with 𝐵𝑖 samples. When these 𝐵𝑖 samples are selected uniformly at random from the local dataset D𝑖 (without replacement), it is straightforward to see that E[𝑔𝑖 |𝑥𝑖 ] = ∇ 𝑓𝑖 (𝑥𝑖 ), i.e., the stochastic gradient 𝑔𝑖 is an unbiased estimate of the local gradient. Furthermore, its variance var(𝑔𝑖 |𝑥𝑖 ) ≜ E[∥𝑔𝑖 − ∇ 𝑓𝑖 (𝑥 𝑖 ) ∥ 2 |𝑥 𝑖 ] can be expressed as [86, Prop. 1] var(𝑔𝑖 |𝑥 𝑖 ) =

𝑀𝑖 − 𝐵𝑖 var ( 𝜙,𝑦)∼U ( D𝑖 ) (∇ℓ(𝑦, 𝑝 𝑥𝑖 (𝜙))), 𝐵𝑖 (𝑀𝑖 − 1)

SE/MSE Conv. Rate

Optimality

Reference

Linear (O (𝑐 𝑡 ))

Neighborhood Exact Exact Exact Exact Exact Exact Exact Exact Exact

[69] [69] [70] [71] [79] [73] [78] [80] [73] [81]

O (1/𝑡 2 ) O (1/𝑡 ) O (1/𝑡 ) √ O (1/ 𝑡 ) Linear Linear Linear Linear Linear

where ∇ℓ(𝑦, 𝑝 𝑥𝑖 (𝜙)) is the gradient of the loss function (with respect to the local parameter vector 𝑥 𝑖 ) and var ( 𝜙,𝑦)∼U ( D𝑖 ) (∇ℓ(𝑦, 𝑝 𝑥𝑖 (𝜙))) is its variance, with respect to a datapoint (𝜙, 𝑦) selected uniformly at random from the local dataset D𝑖 . When the loss function ℓ(·) is 𝐿-smooth with respect to the parameter vector 𝑥, we can further bound [79, Appendix A] i2 𝑀𝑖 − 𝐵𝑖 h 𝜎sg★ + 𝐿 ∥𝑥 𝑖 − 𝑥★ ∥ , (33) var(𝑔𝑖 |𝑥𝑖 ) ≤ 𝐵𝑖 (𝑀𝑖 − 1) 2 where 𝜎sg★ ≜ max𝑖 ∈ V {var ( 𝜙,𝑦)∼U ( D𝑖 ) (∇ℓ(𝑦, 𝑝 𝑥★ (𝜙)))} denotes the maximum variance of the sample-wise gradients evaluated at the optimal solution 𝑥★ in (30), across all agents. Notably, in the regime of small mini-batch sizes (𝐵𝑖 ≪ 𝑀𝑖 ), the variance of the mini-batch gradient estimator is inversely proportional to the mini-batch size as O (1/𝐵𝑖 ). Unlike the uniform bounded-variance assumption in Assumption 6, the upper bound in (33) depends on the distance to the global optimum and may grow as the iterates move away from it. This additional error term may lead to instability if not properly controlled, but can be mitigated by choosing a sufficiently small stepsize [69].

F. Unified Framework on Cooperative SGD Collaborative ML algorithms under different network structures (e.g., fully decentralized, semi-decentralized, and serverbased) can be unified within a common theoretical framework. Fundamentally, they are all special cases of distributed optimization where the mixing matrices can be either fixed or time-varying to capture the effects of communication dynamics and model aggregation/mixing. 1) Distributed Synchronous SGD: This setting consists of a central PS and multiple clients that synchronize their models through server-assisted aggregation. In each communication round, all clients participate by performing one local SGD step on their local data before the server aggregates the updated models. The mathematical representation of this algorithm is equivalent to ATC diffusion with W = 𝑁1 11⊤ . 2) Federated Averaging (FedAvg): The main distinctive features of FedAvg compared with distributed synchronous SGD are partial client participation and multiple local SGD updates between communication rounds. Suppose that one communication round takes place every 𝜏 local SGD steps

10

and that, in each communication round, 𝐾 out of 𝑁 clients are selected randomly. Then the local models from selected clients are averaged at the server, and the resulting new model is broadcast to all clients. An equivalent matrix representation is obtained by defining the time-varying mixing matrix 1   1s(𝑡) ⊤ , 𝑡 ≡ 0 (mod 𝜏),  W(𝑡) = 𝐾   I, 𝑡 . 0 (mod 𝜏),  where s(𝑡) ∈ {0, 1} 𝑁 denotes the client-selection vector. Using this mixing matrix representation, it is readily verified that W(𝑡)1 = 1, whereas 1⊤ W(𝑡) ≠ 1⊤ in general. Thus, although consensus can be achieved, the consensus value is generally biased toward clients with higher participation probabilities [87]. If all clients have the same participation probability, then 1⊤ E[W(𝑡)] = 1⊤ , and convergence in expectation to the exact minimizer 𝑥★ can still be achieved under suitable assumptions. 3) Semi-Decentralized Learning: Suppose that inter-cluster aggregation occurs every 𝜏 iterations. The mixing matrix alternates between a sparse matrix W (1) , representing intra-cluster communication with peer-to-peer information exchange, and an aggregation matrix W (2) , representing periodic inter-cluster synchronization coordinated through the server. IV. C OMMUNICATION C ONSTRAINTS IN D ISTRIBUTED O PTIMIZATION AND L EARNING In distributed learning systems, each node typically computes local model updates based on its own local data, but convergence to the global optimum requires consistent communication and coordination with other nodes in an iterative process. In this section, we will review the following aspects: (1) the sources of communication uncertainty in distributed learning over modern wireless networks (Sec. IV-A); (2) information flows and communication costs under different system architectures (Sec. IV-B); (3) latency and reliability trade-offs in DSGD, and the impact of communication noise on convergence (Sec. IV-C). A. Communication Uncertainty in Distributed Learning a) Link Reliability: Modern data networks are designed using a layered architecture, in which each layer performs specific functions that enable reliable communication between a source and a destination. Packet transmission from one point to another may fail due to random channel variations, contention for the shared communication medium, and hardware impairments. When information transmission occurs over wireless channels, the probability of packet failure (or outage) depends on many factors, such as the transmit power, noise and interference levels, and time-varying channel conditions. Although higher-layer protocols implement mechanisms such as retransmission and error control to improve reliability, these mechanisms cannot fully eliminate physical-layer randomness under stringent latency, bandwidth, or energy constraints. Consequently, distributed learning and inference systems operate under communication uncertainty: communication links act as stochastic operators whose random realizations directly affect the information exchanged among agents and, consequently, the collective system performance.

b) Data Compression: Local model updates, such as gradients or model parameters, are inherently continuousvalued and must be represented using a finite number of bits before transmission over digital communication links. Since communication resources are limited, the available communication budget often does not permit transmitting high-precision updates. For example, in an Orthogonal Frequency Division Multiplexing (OFDM) system, each user is allocated only a limited number of resource blocks. Consequently, model updates are typically compressed prior to transmission. The maximum number of bits that can be reliably conveyed over a communication link depends on both the allocated communication resources and the channel conditions, which together determine the achievable compression ratio. The resulting compression process (including quantization and source coding) introduces distortion and information loss as structured noise in the received updates, affecting both consensus and optimization dynamics. c) Intermittent Node Participation: In addition to linklevel impairments, distributed learning systems often face uncertainty arising from intermittent node participation: nodes may temporarily disconnect from the network due to client scheduling, energy constraints, mobility, or a lack of incentives to participate continuously [88]. As a result, the set of active participating nodes may vary over time, leading to timevarying network topologies and information flows. This intermittent participation introduces additional randomness into the learning process, affecting consensus formation, information mixing, and convergence behavior. Overall, communication uncertainty arising from link failures, quantization, compression, and intermittent node participation fundamentally shapes the performance of distributed learning algorithms, by slowing down information mixing, biasing model updates, and introducing steady-state errors. This motivates the development of distributed optimization and learning frameworks that are both communication-aware and resilient to highly dynamic and uncertain environments. B. Communication Architectures Depending on how nodes cooperate and on the underlying system architecture, various challenges arise in optimizing resource allocation under communication constraints. Here, we briefly review three commonly considered architectures: server-based FL, fully decentralized, and semi-decentralized learning, depicted in Fig. 2. 1) Server-Based FL (Fig. 2(a)): The canonical FL algorithm is FedAvg [49], which can be viewed as a generalized version of distributed synchronous SGD with multiple local steps, partial client participation, under data and system heterogeneity. With FedAvg, each device communicates directly with the PS in every communication round after performing a certain number of local SGD steps. Communication costs can be measured, for instance, by the number of participating clients per communication round [89], or the number of quantization bits per communication link [90], [91]. When the number of participating clients is very large, client sampling/selection is necessary to reduce the communication costs.

11

Parameter Server (PS)

(a) Server-based

Local Device

(b) Decentralized

(c) Semi-decentralized

Fig. 2: Illustration of common distributed learning architectures.

Furthermore, for large-dimensional models, gradient quantization and compression become necessary to fit transmissions within the available frequency-time resources. Both model compression and client sampling contribute to an increased level of distortion in aggregated local updates, causing the global model to oscillate or converge to a biased solution [87]. This effect is further exacerbated under non-independent and identically distributed (non-IID) local data distributions and heterogeneous propagation environments [92], underscoring the challenge of resource allocation in FL under data and channel heterogeneity. To reduce communication overhead, FedAvg performs multiple local SGD steps between successive aggregation rounds. The number of local SGD steps per communication round is another important design parameter in FedAvg that affects the communication costs. Performing multiple local updates reduces communication frequency but gives rise to the client drift phenomenon, caused by data heterogeneity across clients [93], [94]. In particular, model updates may drift away from the global optimum during local training, degrading convergence performance and final accuracy. This requires a careful design on the number of local SGD steps to balance the available communication budget and the convergence performance. 2) Decentralized Learning (Fig. 2(b)): In fully decentralized learning systems, each client or agent communicates with its local neighbors via peer-to-peer information exchange. With standard DGD or DSGD, one communication phase (consensus mixing) occurs after every local GD or SGD iteration. More recent studies have considered extended settings with multiple gradient and consensus steps [95]. Depending on whether unicast or broadcast transmission is considered, the communication costs can be measured by either the number of activated nodes or links per iteration of the algorithm, or by the

total number of bits required to achieve a target accuracy [47]. Meanwhile, implementing decentralized learning algorithms over wireless networks requires medium access control to avoid packet collisions caused by co-channel interference. This introduces additional constraints that determine which set of nodes or links can be active simultaneously. Activating a smaller number of nodes or links in each iteration is equivalent to creating time-varying sparser communication graphs under a given base topology. Reducing communication costs by activating fewer nodes or links typically results in a slower convergence rate, but this effect is non-uniform, as some nodes or links are more critical to network connectivity than others. This observation highlights the importance of node/link scheduling design in balancing convergence speed and communication costs. 3) Semi-Decentralized Learning (Fig. 2(c)): Recently, semi-decentralized learning has attracted increasing attention. It follows a hierarchical network architecture that combines local consensus and server-assisted model aggregation [51], [52], [96], [97]. In this setting, there are two types of communication links: device-to-device (D2D) information exchange within local clusters and periodic device-to-server (D2S) updates. The strong heterogeneity of communication links across the network hierarchy leads to diverse latency, bandwidth, congestion, and energy characteristics. Moreover, the effective communication cost depends on the communication pattern, update size, transmission strategy, and time-varying channel conditions. Consequently, resource allocation should move beyond minimizing the number of transmissions and instead jointly account for the dynamics of D2D and D2S links and their impact on learning convergence. In particular, D2D aggregation generally incurs lower latency than global aggregation at higher levels of the hierarchy, but provides a more localized view of the network state. This creates a fundamental trade-off between synchronizing D2D cluster models through slower global aggregation, which may rely on outdated models, and relying on faster, more localized D2D updates that better reflect the current state of the system [98]. C. Latency–Reliability Trade-offs in DSGD Although modern communication systems can provide highly reliable links through channel coding and retransmission mechanisms, they generally incur a significant latency cost, particularly when delivering high-dimensional model updates. Conversely, reducing communication latency generally comes at the expense of sacrificing communication reliability, leading to increased distortion in the exchanged model updates. This latency–reliability trade-off lies at the heart of communication-efficient distributed learning and motivates the design of algorithms that jointly optimize communication and learning performance. We consider the implementation of DSGD over a wireless network with 𝑁 agents as an example. Assuming that each agent broadcasts its local 𝑑-dimensional model update over orthogonally allocated communication resources, the communication latency per iteration scales as 𝑇ite = O (𝑁 𝑑). Combined with the O (1/𝑡) MSE convergence rate of DSGD

12

(see Sec. III-B), achieving a target accuracy 𝜖 requires an overall communication latency of 𝑇tot = O (𝑁 𝑑/𝜖) . This scaling becomes prohibitive in densely deployed networks (large 𝑁), such as swarms of UAVs, or when optimizing high-dimensional models (large 𝑑), as in deep neural networks. To alleviate this communication bottleneck, two complementary approaches have emerged: model compression targets the high-dimensional regime (large 𝑑) [99], whereas physical-layer transmission/aggregation techniques improve scalability in the large-network regime (large 𝑁) [79]. These communication-efficient techniques introduce additional distortion into the exchanged model updates. In these cases, DSGD can be modeled as x(𝑡 + 1) = (W ⊗ I𝑑 )x(𝑡) − 𝛼𝑡 g(𝑡) + n(𝑡),

(34)

where n(𝑡) denotes the additive error induced during the information mixing stage of DSGD, arising from protocoldependent communication impairments, such as fading channels, interference, link failures, and model compression.4 This model specializes to (23) when n(𝑡) = 0. The error 𝑛𝑖 (𝑡) experienced at node 𝑖 is commonly modeled as E[𝑛𝑖 (𝑡) | x(𝑡)] = 0,

2 E[∥𝑛𝑖 (𝑡) ∥ 2 | x(𝑡)] ≤ 𝜎com ,

(35)

2 where, similar to Assumption 6, 𝜎com bounds the variance of communication errors. Unlike stochastic gradient noise, which is multiplied by the learning stepsize 𝛼𝑡 , communication noise enters the consensus update independently of 𝛼𝑡 . Consequently, as the learning stepsize decreases, communication noise eventually becomes the dominant source of error. A common mitigation strategy is to introduce an autoregressive consensus filter (see, e.g., [69], [79], [100]), leading to

x(𝑡+1) = (1−𝛾𝑡 )x(𝑡)+𝛾𝑡 (W⊗I𝑑 )x(𝑡)−𝛼𝑡 g(𝑡)+𝛾𝑡 n(𝑡), (36) controlled by the consensus stepsize 𝛾𝑡 ∈ (0, 1). With constant stepsizes, under Assumptions 2-6, the convergence of DSGD under noisy communications has been characterized in [69, Sec. V], yielding lim sup 𝑡→∞

𝑁 2 2 𝛼𝜎sg  𝛾 2 𝜎com 1 ∑︁  +2 E ∥𝑥𝑖 (𝑡) − 𝑥★ ∥ 2 ≤2 𝑁 𝑖=1 𝛼𝜇 𝜇

𝛼2 𝜅 2 Δ𝑏 +2 2 , 𝛾 (1 − 𝜆 2 ) 2

(37)

provided that the stepsize 𝛼 is chosen sufficiently small. In contrast to stochastic gradient noise, whose contribution vanishes as 𝛼 → 0, the communication-induced term scales as 1/𝛼 when 𝛾 is fixed. Consequently, reducing the learning stepsize alone does not improve the asymptotic error and may even worsen it. Controlling the asymptotic error bound in (37) therefore requires careful tuning of consensus and learning stepsizes to ensure stability and convergence. In particular, by 4 Link failures are often modeled through a time-varying mixing matrix;

alternatively, they can be represented as additive noise, with the noise term capturing the information lost due to failed links.

choosing a decreasing learning stepsize as 𝛼𝑡 = O (1/𝑡) and a decreasing consensus stepsize as 𝛾𝑡 = O (𝑡 −3/4 ), the error to the global optimum decays as [79] √  1 ∑︁ 𝑁  E ∥𝑥𝑖 (𝑡) − 𝑥★ ∥ 2 = O (1/ 𝑡). (38) 𝑖=1 𝑁 after 𝑡 iterations. Although the convergence rate deteriorates √ from O (1/𝑡) to O (1/ 𝑡), communication-efficient implementations substantially reduce the per-iteration latency 𝑇ite . This highlights a fundamental trade-off between communication resources and optimization performance, which is intrinsic to collaborative ML and sets it apart from classical reliabilitycentric communication paradigms. V. N UMERICAL E XAMPLE As discussed earlier, the convergence behavior of distributed learning algorithms is governed by the interplay between deterministic optimization error, stochastic gradient noise, and communication uncertainty. In this section, we numerically compare these different regimes under representative stepsize sequences, illustrating the theoretical results presented in the previous sections. We consider a network of 𝑁 = 50 agents arranged on a ring, where each agent communicates with its 10 nearest neighbors on each side (i.e., 20 neighbors in total). The mixing matrix W is symmetric and doubly stochastic, with equal weights assigned to all active links. Each agent holds a onedimensional quadratic objective
2 𝜇𝑖 𝑥 − 𝑥𝑖loc , (39) 𝑓𝑖 (𝑥) = 2 where the curvature parameters 𝜇𝑖 are independently drawn from the interval [𝜇, 𝐿] with 𝜇 = 1 and 𝐿 = 4, while the local minimizers 𝑥𝑖loc are independently generated according to N (0, 100). Gradient noise is modeled as independent additive 2 I). Communication noise is Gaussian at each agent, N (0, 𝜎sg modeled as additive Gaussian, N (0, Σcom ) with covariance Σcom = 𝜎𝑞2 W2 . It can be interpreted as the effect of independent quantization errors propagated over the network.5 We compare three representative stepsize strategies. • Constant stepsizes: Both the learning and consensus step1 sizes remain fixed, 𝛼 = 𝐿+𝜇 , 𝛾 = 12 , corresponding to a constant-stepsize DGD/DSGD scheme with a scaled mixing matrix, known to converge linearly to a neighborhood of the optimum. • Gradient-noise-aware: The consensus stepsize remains fixed, 𝛾 = 21 , while the learning stepsize decreases as 𝛼𝑡 = O (1/𝑡) following classical stochastic approximation rules [101]. This strategy mitigates the effect of stochastic gradient noise but does not explicitly account for communication noise. • Communication-noise-aware: Both the learning and consensus stepsizes decrease over time as 𝛼𝑡 = O (1/𝑡) and 𝛾𝑡 = O (1/𝑡 3/4 ) respectively, following the theoretically 5 Quantization errors are generally neither Gaussian nor independent of the state, unless dithering or a high-resolution approximation is employed. Here, we use a Gaussian surrogate to model independent perturbations introduced before network mixing.

13

(a) Noiseless

(b) Gradient noise

(c) Gradient and communication noise

Fig. 3: Comparison of the optimization error under three representative stepsize schedules. Legend shown in the left figure.

motivated design discussed in Sec. IV-C and in [79]. The decreasing consensus stepsize progressively attenuates the accumulation of communication noise while preserving convergence. Fig. 3 compares the MSE (normalized to the initialization error) in three different settings: noiseless optimization (Fig. 3(3a)), optimization with stochastic gradient noise only (Fig. 3(3b)), and optimization with both gradient and communication noise (Fig. 3(3c)). In the noiseless case, the constant-stepsize method converges only to a neighborhood of the optimum due to the steady-state bias of DGD, while the gradient-noise-aware stepsize sequence converges to the exact optimum with the theoretical rate O (1/𝑡 2 ) (Sec. III-A). When gradient noise is introduced (Fig. 3(3b)), the gradientnoise-aware stepsize sequence achieves the asymptotic O (1/𝑡) decay predicted by the theory (Sec. III-B), reflecting the effect of stochastic gradient noise. Since communication remains ideal, decreasing the consensus stepsize provides no additional benefit, and the communication-noise-aware stepsize sequence therefore converges more slowly. Finally, Fig. 3(3c) considers the practical setting where both stochastic gradient and communication noises are present. In this case, the gradient-noise-aware stepsize sequence initially decreases the error rapidly, but communication noise ultimately dominates, leading to performance degradation. In contrast, the communication-noise-aware stepsize sequence progressively decreases both the learning and consensus stepsizes, mitigating the accumulation of communication √ noise and achieving the asymptotic theoretical rate O (1/ 𝑡), discussed in Sec. IV-C. These results demonstrate that communication impairments fundamentally alter the convergence behavior of distributed optimization algorithms, making communicationaware algorithm design essential for achieving both reliable convergence and communication efficiency. VI. C OMMUNICATION -E FFICIENT M ETHODS When implementing distributed consensus, optimization, and learning algorithms in large-scale wireless networks where bandwidth, energy, and spatial resources are limited, communication efficiency becomes a central design objective. Various communication-efficient methods have been developed and analyzed, including link or node scheduling, data compression (such as quantization, sparsification, low-rank approximation,

compressed sensing), and event-triggered communication. In this section, we review commonly considered approaches for improving communication efficiency and emerging techniques that leverage the unique properties of wireless channels. A. Communication-Efficient Distributed Consensus Earlier research on distributed consensus often models the information exchange as a deterministic process. However, many of the most promising applications of consensus mechanisms, such as multi-robot control and sensor fusion, rely on wireless connectivity in practice. When implementing consensus protocols in wireless networks, the inherent unreliability of the wireless medium (e.g., packet losses, variable latency, and intermittent connectivity) has prompted a shift from deterministic to probabilistic performance guarantees. In particular, the broadcast nature of the wireless medium introduces collisions and co-channel interference, making node/link scheduling and power control two important design elements for achieving fast and reliable information fusion. Moreover, limited bandwidth and energy constraints motivate communication-efficient methods based on compressed updates. 1) Node and Link Scheduling: Earlier studies assume that all nodes communicate with their neighbors in every iteration. Later on, motivated by the communication and computation constraints in sensor networks, gossip algorithms with randomized pairwise interactions have been extensively studied [21], [22], [24]. This can be viewed as an example of communication scheduling where one link is randomly sampled in each iteration. Subsequent studies have considered various forms of communication scheduling and partial activation to improve communication efficiency, such as event-triggered communication [102]–[104] and probabilistic link scheduling [105], [106]. Considering the broadcast nature of wireless channels, [107] proposes a broadcast-based scheduling policy with various ways of designing the node transmission probabilities. These works demonstrate that appropriate scheduling mechanisms can significantly reduce communication costs while maintaining convergence to average consensus. 2) Power Control: In wireless networks with potential link failures, power control directly influences communication reliability and, consequently, the effective network connectivity. Motivated by this observation, several studies have investigated power allocation strategies in distributed consensus. In

14

[108], a joint topology control and transmit power optimization problem is formulated with the aim of minimizing the total energy consumption required to achieve consensus. Considering the presence of interference in wireless networks, [109] analyzes how transmission power and interference impact both convergence speed and energy costs. 3) Compressed Updates: As discussed in Sec. II-E2, directly implementing consensus averaging algorithms with quantized state values may lead to persistent steady-state errors. Recent work considers error compensation using additional state variables, leading to the CHOCO-Gossip algorithm introduced in [99], which achieves convergence to the exact solution even with biased quantization operators. For directed network topologies, [30] develops a fully decentralized quantized algorithm for designing the mixing weights, coupled with a quantized consensus update rule, and establishes almost sure convergence to the exact average consensus. In summary, existing studies have shown that power allocation, topology design, transmission scheduling, and compression jointly affect both convergence performance and energy efficiency in wireless consensus systems. B. Communication-Efficient FL Communication efficiency is essential for scaling FL to large networks [110]. Existing approaches can be broadly categorized into several complementary directions, including reducing message sizes through compression, limiting communication links through scheduling, learning-aware resource allocation, and exploiting over-the-air computation (AirComp). 1) Model Update Compression: A first major line of work develops gradient or model update compression techniques that reduce the payload size in each communication round. Communication overhead can be reduced by either decreasing the number of transmitted elements or compressing their digital representation. The former is typically achieved through dimensionality reduction techniques, including sparsification [111], [112], low-rank approximation [113], [114], and subspace projection [115]. The latter is commonly accomplished via quantization techniques, including scalar and vector quantization [90], [116]. 2) Client Selection: Earlier works on FL have considered various client selection policies under the static channel setting. [89] uses a norm-based importance criterion and derives the optimal participation probabilities for client scheduling. [117] reviews common client selection strategies, including optimization-based, importance-based, and adaptive sampling approaches. Event-triggered communication is another popular mechanism that reduces communication frequency by avoiding insignificant update transmissions [118]. In time-varying wireless environments, [119] shows that different device selection and scheduling policies can substantially affect convergence speed. Extending from synchronous training and aggregation, [120] considers asynchronous FL and proposes a joint scheduling and aggregation design that accounts for data similarity, channel conditions, and model staleness. 3) Joint Learning-Communication Design: In addition to algorithmic approaches, another line of research considers

joint learning–communication design that integrates FL with wireless resource management. Representative studies formulate optimization problems that integrate device scheduling, transmit power control, and bandwidth allocation to minimize training loss, latency, or total energy consumption under wireless constraints [92], [121]–[124]. The analysis in [125] derives explicit expressions linking convergence to wireless resource conditions, providing a theoretical foundation for communication-aware resource allocation. Overall, the literature suggests that practical FL in communication-constrained wireless networks benefits from a combined design of learning algorithms, update compression, and resource management. 4) AirComp: Traditionally, multi-user wireless communication systems rely on orthogonal resource allocation, ensuring interference-free transmissions by dividing time and frequency resources among devices. Such orthogonal resource allocation becomes inefficient in FL settings with an extremely large number of participating devices, yielding a communication overhead that grows linearly with network size. To overcome this limitation, AirComp has emerged as a promising physicallayer technique for low-latency wireless data aggregation. By exploiting the superposition property of wireless channels, AirComp enables the direct computation of aggregate functions, including arithmetic means, weighted sums, and geometric means, in one shared channel use per scalar component, independently of the number of devices [126]–[128]. More generally, any nomographic function can be implemented via AirComp through appropriate pre-processing at the transmitter and post-processing at the receiver [129]. This approach transforms the communication process from mere data transfer to in-network computation, making AirComp particularly well suited for model update aggregation in FL [130], [131]. Prior work has developed techniques to enhance AirCompassisted FL, including adaptive learning rate control [132], [133], hybrid beamforming [134], retransmissions [135], and interference management [136]. Recently, AirComp has been extended to other emerging areas such as distributed sensing and inference [137], [138]. Despite its advantages in low latency and high resource efficiency, analog AirComp is sensitive to noise, channel estimation errors, and synchronization mismatches, which may limit its robustness in practical systems. Motivated by these limitations, recent works have proposed digital AirComp methods that integrate quantization, coding, and digital modulation to improve robustness while preserving efficient in-network computation [139]–[142]. Although research in this direction has grown substantially, a comprehensive theoretical framework that explicitly relates channel estimation accuracy and calibration mismatch to perround aggregation MSE and, ultimately, to end-to-end convergence remains lacking. Moreover, a systematic comparison between digital communication and analog AirComp remains an open research problem that deserves further investigation. C. Communication-Efficient Decentralized Learning Decentralized learning relies on spatially distributed peer-topeer information exchange among neighboring nodes. Recent research on communication-efficient decentralized learning

15

focuses on communication scheduling, quantized information exchange, and AirComp-based aggregation. More recently, non-coherent AirComp has emerged as a scalable alternative that eliminates the need for channel state information, explicit scheduling, and topology-aware coordination. 1) Communication Scheduling: As discussed in Sec. IV-B2, not all nodes or links are equally important in terms of their impact on the network connectivity. In [143], a matching-based link scheduling design is proposed, which allows connectivitycritical links to be activated with higher probabilities under a given communication budget. Similar ideas have been explored in [144], [145], where various node or link scheduling policies and mixing matrix optimization designs are developed under different communication models and cost measures. Eventtriggered communication is another example of communication scheduling, where information exchange is initiated only when a predefined triggering condition is satisfied, thereby reducing communication overhead while maintaining the desired algorithmic performance [146]. 2) Quantized Updates: Recent studies have considered quantized updates and ways to mitigate the steady-state error caused by quantization noise [47], [99], [147], [148]. Adaptive quantization has also been explored, where the quantization resolution increases over time to progressively reduce quantization error. For example, [47] proposes a finitebit quantization framework applicable to a broad class of linearly convergent distributed algorithms, preserving linear convergence while characterizing the communication budget required to achieve a target accuracy. 3) AirComp for Decentralized Aggregation: Most existing AirComp-based learning frameworks assume star topologies, where multiple clients communicate with a central server (e.g., a base station). Recently, AirComp has been explored for fully decentralized multi-agent consensus and optimization, enabling one-step aggregation without centralized coordination [79], [149]–[151]. Decentralized AirComp-based consensus and optimization algorithms have been analyzed under both single-antenna [150] and multi-antenna [151] configurations. Several recent works have combined AirComp with decentralized learning by decomposing the network into non-interfering subgraphs using graph coloring [150], [152], [153]. Within each subgraph, a designated node performs AirComp-based aggregation, followed by a consensus step akin to DSGD. Although effective, these approaches require topology information and channel state information (CSI) feedback, leading to substantial signaling overhead in large networks. To address these signaling and scalability challenges, recent work [79] proposes non-coherent over-the-air aggregation to achieve fully scalable decentralized learning without scheduling, topology information, or CSI. This approach leverages noisy energy superposition to obtain unbiased consensus estimates using average channel gains as implicit consensus mixing weights, eliminating explicit weight design and CSI acquisition. This framework accommodates general fading and frequency-selective channels, and has been extended to achieve robustness against interference [154] and to incorporate power control for convergence acceleration [155].

VII. O PEN P ROBLEMS AND E MERGING D IRECTIONS This section outlines key open problems and topics of interest for future research, including more realistic assumptions and convergence criteria, fundamental trade-offs, secure and resilient operation, and modern learning scenarios. A. Mismatch Between Theoretical Assumptions and Reality Theoretical analyses of distributed optimization necessarily rely on idealized assumptions regarding the optimization problem, the algorithm, and the underlying system. Although these assumptions enable rigorous convergence guarantees, they often differ significantly from those encountered in practical distributed learning applications. In this section, we discuss several important mismatches between theory and practice, focusing on assumptions on local objective functions, learningrate design, system-level heterogeneity, and system dynamics. 1) Assumptions on Local Objectives: Much of the literature assumes well-behaved objective functions, including strong convexity, Lipschitz-continuous gradients, bounded gradients, or bounded SGD variance. These conditions often fail in practice, since typical neural networks are nonconvex and may violate Lipschitz continuity and bounded gradient assumptions. This motivates the development of analytical tools that accommodate broader function classes. However, enlarging the function class typically leads to weaker convergence guarantees, which makes the resulting bounds overly conservative when used for resource allocation or parameter tuning. 2) Adaptive Learning Rates: Most convergence analyses assume carefully designed constant or diminishing stepsize schedules. In practice, however, such schedules are rarely known a priori and often require extensive hyperparameter tuning. Adaptive learning-rate methods alleviate this burden by automatically adjusting the learning rate according to the optimization history [156], [157]. Extending adaptive optimization to federated and decentralized settings remains challenging because learning-rate adaptation must rely on local information while preserving network-wide convergence guarantees. Representative approaches include [158], [159]. 3) System-Level Heterogeneity: Practical distributed learning systems are highly heterogeneous. Agents may differ substantially in processing power, energy availability, communication bandwidth, and local data characteristics. In addition, communication delays, intermittent participation and packet losses can lead to asynchronous operation with unpredictable system dynamics. These sources of system-level heterogeneity introduce challenges that are often not captured by classical assumptions and convergence analyses. Developing distributed optimization algorithms and analytical frameworks that explicitly account for realistic system heterogeneity remains an active area of research [160]. 4) Correlated System Dynamics: Most convergence analyses assume that stochastic gradients, communication noise, or network variations are independent across iterations. These assumptions greatly simplify the analysis by enabling the use of classical stochastic approximation techniques. Practical distributed learning systems, however, exhibit significant temporal and spatial correlations [161]. Examples include timecorrelated wireless fading channels [162], bursty packet losses,

16

temporally correlated data [163], and dynamically evolving environments [164]. Such correlations may substantially alter the optimization dynamics and invalidate convergence analyses based on independence assumptions. Developing analytical frameworks that explicitly account for correlated stochastic processes therefore remains an active research direction. B. Convergence Criteria The overwhelming majority of the literature on decentralized optimization uses the MSE (i.e., the expected squared Euclidean distance between the algorithm’s iterates and the optimizer in convex optimization, or the expected squared Euclidean norm of the gradient in non-convex optimization) as the primary convergence criterion, providing the number of iterations required to reach a target 𝜖-accuracy. While meansquare convergence characterizes the algorithm’s average behavior, it does not guarantee convergence along individual sample paths. This motivates the study of stronger notions such as almost-sure convergence, which guarantees convergence with probability one [43]. Establishing such guarantees typically relies on martingale-based techniques, most notably the Robbins-Siegmund supermartingale convergence theorem [165], together with suitable assumptions on the underlying stochasticity and the stepsize sequence. C. Interplay between Communication and Computation Distributed learning relies on repeated local computation and communication among resource-constrained devices, making the joint optimization of communication and computation essential [166]. A central challenge is to allocate communication and computing resources, including local updates, mini-batch sizes, communication rounds, and communication reliability, to achieve a target learning accuracy under latency and energy constraints. Despite the extensive literature on communication-efficient techniques, most existing approaches optimize only a subset of the available design parameters while treating the remaining ones as fixed. As a result, they provide only a partial characterization of the underlying communication-computation trade-off. Recent work has investigated unified resource allocation frameworks. For example, [167] proposes heuristic rules for balancing communication and computation steps in decentralized optimization, while [168] formulates decentralized learning under an explicit communication-computation budget and derives adaptive bottleneck-aware scheduling policies. Nevertheless, a general theory for jointly optimizing communication, computation, and wireless resources remains largely unexplored. D. Privacy, Security, and Resilience While distributed learning keeps data local and thus provides inherent privacy advantages, it remains vulnerable to various privacy and security threats, including gradient inversion, membership inference, and model poisoning attacks [169]. To protect data confidentiality, two widely adopted approaches are secure aggregation, which leverages secure multi-party computation to prevent disclosure of individual model updates [170], and differential privacy, which injects carefully

calibrated random noise into local updates [171]. To enhance robustness against unreliable or malicious participants, Byzantine-resilient aggregation methods [172]–[174] identify and suppress adversarial updates using robust statistical techniques. Consequently, distributed learning algorithms must operate accurately and reliably under multiple sources of uncertainty, including artificial perturbations introduced for privacy preservation and malicious manipulations. E. Modern Topics Our analysis and case studies in this article have focused on single-task distributed learning with static datasets and firstorder optimization methods. Extensions to multi-task learning [175], continual learning [176], zeroth- [177] and secondorder methods [178] bring many new questions into the communication optimization problem. In multi-task decentralized learning, agents are connected at the topology and task levels, which complicates the effects of communication scheduling on the system performance. With continual learning and streaming datasets, the local objectives become time-varying, which creates another source of dynamics in the importance of model updates from different nodes. Another promising direction is integrating finite-time consensus with communication-aware distributed optimization [179] to accelerate convergence and improve learning efficiency in resource-constrained networks. VIII. C ONCLUSION In this tutorial, we provided a comprehensive review of the fundamentals of distributed consensus and optimization over networked agents, highlighting the critical role of information mixing and network topology in system performance. We then examined how communication resource constraints affect distributed learning algorithms in practical settings with diverse communication architectures, including federated, decentralized, and semi-decentralized systems. Building on these foundations, we reviewed communication-efficient approaches for distributed learning, including compression, client/link scheduling, learning-aware resource allocation, and joint communication and computation designs such as AirComp. Beyond summarizing existing works, this tutorial provides a unified framework for understanding multi-agent cooperation and learning under various sources of information uncertainty. We emphasize that communication is not merely an implementation detail, but a fundamental design component of scalable and efficient decentralized AI systems. Despite significant progress in related research areas, numerous challenges and open problems remain. These include a deeper understanding of the mismatch between theoretical assumptions and reality, balancing computation, communication, and privacy trade-offs, and developing theoretical guarantees for increasingly complex and stochastic learning environments. R EFERENCES [1] S. Vlaski, S. Kar, A. H. Sayed, and J. M. Moura, “Networked signal and information processing: Learning by multiagent systems,” IEEE Signal Processing Magazine, vol. 40, no. 5, pp. 92–105, 2023.

17

[2] 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. [3] 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. [4] A. Nedić, J.-S. Pang, G. Scutari, and Y. Sun, Multi-agent Optimization, 1st ed. Springer, Cham, 2018. [5] J. Verbraeken, M. Wolting, J. Katzy, J. Kloppenburg, T. Verbelen, and J. S. Rellermeyer, “A survey on distributed machine learning,” ACM Computing Surveys, vol. 53, no. 2, pp. 1–33, 2020. [6] J. N. Tsitsiklis, “Problems in decentralized decision making and computation,” Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, MA, USA, 1984. [7] D. Bertsekas and J. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Englewood Cliffs, 1989. [8] M. H. DeGroot, “Reaching a consensus,” Journal of the American Statistical Association, vol. 69, no. 345, pp. 118–121, 1974. [9] L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” Systems & Control Letters, vol. 53, no. 1, pp. 65–78, 2004. [10] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE, vol. 95, no. 1, pp. 215–233, 2007. [11] A. Olshevsky and J. N. Tsitsiklis, “Convergence speed in distributed consensus and averaging,” SIAM Journal on Control and Optimization, vol. 48, no. 1, pp. 33–55, 2009. [12] Y. Hatano and M. Mesbahi, “Agreement over random networks,” IEEE Transactions on Automatic Control, vol. 50, no. 11, pp. 1867–1872, 2005. [13] W. Ren and R. Beard, “Consensus seeking in multiagent systems under dynamically changing interaction topologies,” IEEE Transactions on Automatic Control, vol. 50, no. 5, pp. 655–661, 2005. [14] A. Tahbaz-Salehi and A. Jadbabaie, “A necessary and sufficient condition for consensus over random networks,” IEEE Transactions on Automatic Control, vol. 53, no. 3, pp. 791–795, 2008. [15] G. Shi, B. D. O. Anderson, and K. H. Johansson, “Consensus over random graph processes: Network Borel–Cantelli lemmas for almost sure convergence,” IEEE Transactions on Information Theory, vol. 61, no. 10, pp. 5690–5707, 2015. [16] A. D. Domínguez-García and C. N. Hadjicostis, “Distributed strategies for average consensus in directed graphs,” in IEEE Conference on Decision and Control, 2011, pp. 2124–2129. [17] K. Cai and H. Ishii, “Average consensus on general strongly connected digraphs,” Automatica, vol. 48, no. 11, pp. 2750–2761, 2012. [18] A. Priolo, A. Gasparri, E. Montijano, and C. Sagues, “A distributed algorithm for average consensus on strongly connected weighted digraphs,” Automatica, vol. 50, no. 3, pp. 946–951, 2014. [19] C. N. Hadjicostis, A. D. Domínguez-García, and T. Charalambous, “Distributed averaging and balancing in network systems: with applications to coordination and control,” Foundations and Trends® in Systems and Control, vol. 5, no. 2-3, pp. 99–292, 2018. [20] D. Kempe, A. Dobra, and J. Gehrke, “Gossip-based computation of aggregate information,” in IEEE Symposium on Foundations of Computer Science, 2003, pp. 482–491. [21] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2508–2530, 2006. [22] F. Fagnani and S. Zampieri, “Randomized consensus algorithms over large scale networks,” IEEE Journal on Selected Areas in Communications, vol. 26, no. 4, pp. 634–649, 2008. [23] F. Bénézit, V. Blondel, P. Thiran, J. Tsitsiklis, and M. Vetterli, “Weighted gossip: Distributed averaging using non-doubly stochastic matrices,” in IEEE International Symposium on Information Theory, 2010, pp. 1753–1757. [24] A. G. Dimakis, S. Kar, J. M. Moura, M. G. Rabbat, and A. Scaglione, “Gossip algorithms for distributed signal processing,” Proceedings of the IEEE, vol. 98, no. 11, pp. 1847–1864, 2010. [25] R. Olfati-Saber and R. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1520–1533, 2004. [26] P.-A. Bliman and G. Ferrari-Trecate, “Average consensus problems in networks of agents with delayed communications,” Automatica, vol. 44, no. 8, pp. 1985–1995, 2008. [27] C. N. Hadjicostis and T. Charalambous, “Average consensus in the presence of delays in directed graph topologies,” IEEE Transactions on Automatic Control, vol. 59, no. 3, pp. 763–768, 2014.

[28] R. Carli, F. Fagnani, P. Frasca, T. Taylor, and S. Zampieri, “Average consensus on networks with transmission noise or quantization,” in IEEE European Control Conference (ECC), 2007, pp. 1852–1857. [29] T. C. Aysal, M. J. Coates, and M. G. Rabbat, “Distributed average consensus with dithered quantization,” IEEE Transactions on Signal Processing, vol. 56, no. 10, pp. 4905–4918, 2008. [30] C.-S. Lee, N. Michelusi, and G. Scutari, “Finite rate distributed weightbalancing and average consensus over digraphs,” IEEE Transactions on Automatic Control, vol. 66, no. 10, pp. 4530–4545, 2021. [31] G. Oliva, C. Fioravanti, E. Makridis, and T. Charalambous, “Quantized average consensus with a plateau escaping strategy in undirected graphs,” IEEE Control Systems Letters, vol. 9, pp. 709–714, 2025. [32] F. Fagnani and S. Zampieri, “Average consensus with packet drop communication,” SIAM Journal on Control and Optimization, vol. 48, no. 1, pp. 102–133, 2009. [33] S. Patterson, B. Bamieh, and A. El Abbadi, “Convergence rates of distributed average consensus with stochastic link failures,” IEEE Transactions on Automatic Control, vol. 55, no. 4, pp. 880–892, 2010. [34] S. Kar and J. M. F. Moura, “Distributed consensus algorithms in sensor networks with imperfect communication: Link failures and channel noise,” IEEE Transactions on Signal Processing, vol. 57, no. 1, pp. 355–369, 2009. [35] E. Makridis, T. Charalambous, and C. N. Hadjicostis, “Harnessing HARQ retransmissions for fast average consensus over unreliable communication channels,” in IEEE Conference on Decision and Control (CDC), 2023, pp. 5437–5443. [36] S. Sundaram and C. N. Hadjicostis, “Finite-time distributed consensus in graphs with time-invariant topologies,” in IEEE American Control Conference (ACC), 2007, pp. 711–716. [37] T. Charalambous, Y. Yuan, T. Yang, W. Pan, C. N. Hadjicostis, and M. Johansson, “Decentralised minimum-time average consensus in digraphs,” in IEEE Conference on Decision and Control, 2013, pp. 2617–2622. [38] ——, “Distributed finite-time average consensus in digraphs in the presence of time delays,” IEEE Transactions on Control of Network Systems, vol. 2, no. 4, pp. 370–381, 2015. [39] T. Charalambous and C. N. Hadjicostis, “When to stop iterating in digraphs of unknown size? an application to finite-time average consensus,” in European Control Conference (ECC), 2018, pp. 1–7. [40] A. Y. Kibangou, “Graph laplacian based matrix design for finite-time distributed average consensus,” in IEEE American Control Conference (ACC), 2012, pp. 1901–1906. [41] T. Charalambous and C. N. Hadjicostis, “Laplacian-based matrix design for finite-time average consensus in digraphs,” in IEEE Conference on Decision and Control (CDC), 2018, pp. 3654–3659. [42] A. Nedić and A. Ozdaglar, “Distributed subgradient methods for multiagent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009. [43] S. Sundhar Ram, A. Nedić, and V. V. Veeravalli, “Distributed stochastic subgradient projection algorithms for convex optimization,” Journal of Optimization Theory and Applications, vol. 147, no. 3, pp. 516–545, 2010. [44] A. Nedić and A. Olshevsky, “Distributed optimization over timevarying directed graphs,” IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 601–615, 2015. [45] J. Tsitsiklis, D. Bertsekas, and M. Athans, “Distributed asynchronous deterministic and stochastic gradient optimization algorithms,” IEEE Transactions on Automatic Control, vol. 31, no. 9, pp. 803–812, 1986. [46] M. Assran, A. Aytekin, H. R. Feyzmahdavian, M. Johansson, and M. G. Rabbat, “Advances in asynchronous parallel and distributed optimization,” Proceedings of the IEEE, vol. 108, no. 11, pp. 2013– 2031, 2020. [47] 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. [48] X. Cao and T. Başar, “Decentralized multi-agent stochastic optimization with pairwise constraints and quantized communications,” IEEE Transactions on Signal Processing, vol. 68, pp. 3296–3311, 2020. [49] H. B. McMahan, E. Moore, D. Ramage, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. PMLR, 2017, pp. 1273–1282. [50] 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,” Advances in Neural Information Processing Systems, vol. 30, 2017.

18

[51] S. Hosseinalipour, S. S. Azam, C. G. Brinton, N. Michelusi, V. Aggarwal, D. J. Love, and H. Dai, “Multi-stage hybrid federated learning over large-scale D2D-enabled fog networks,” IEEE/ACM Transactions on Networking, vol. 30, no. 4, pp. 1569–1584, 2022. [52] F. P.-C. Lin, S. Hosseinalipour, S. S. Azam, C. G. Brinton, and N. Michelusi, “Semi-decentralized federated learning with cooperative D2D local model aggregations,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 12, pp. 3851–3869, 2021. [53] S. S. Kia, B. Van Scoy, J. Cortes, R. A. Freeman, K. M. Lynch, and S. Martinez, “Tutorial on dynamic average consensus: The problem, its applications, and the algorithms,” IEEE Control Systems Magazine, vol. 39, no. 3, pp. 40–72, 2019. [54] R. Xin, S. Pu, A. Nedić, and U. A. Khan, “A general framework for decentralized optimization with first-order methods,” Proceedings of the IEEE, vol. 108, no. 11, pp. 1869–1889, 2020. [55] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” IEEE Signal Processing Magazine, vol. 37, no. 3, pp. 50–60, 2020. [56] R. A. Horn and C. R. Johnson, Matrix Analysis, 2nd ed. Cambridge University Press, 2013. [57] B. Touri and A. Nedić, “Product of random stochastic matrices,” IEEE Transactions on Automatic Control, vol. 59, no. 2, pp. 437–448, 2014. [58] C. N. Hadjicostis, N. H. Vaidya, and A. D. Domínguez-García, “Robust distributed average consensus via exchange of running sums,” IEEE Transactions on Automatic Control, vol. 61, no. 6, pp. 1492–1507, 2016. [59] L. Xiao, S. Boyd, and S.-J. Kim, “Distributed average consensus with least-mean-square deviation,” Journal of Parallel and Distributed Computing, vol. 67, no. 1, pp. 33–46, 2007. [60] M. Huang and J. H. Manton, “Coordination and consensus of networked agents with noisy measurements: Stochastic algorithms and asymptotic behavior,” SIAM Journal on Control and Optimization, vol. 48, no. 1, pp. 134–161, 2009. [61] L. Pescosolido, S. Barbarossa, and G. Scutari, “Average consensus algorithms robust against channel noise,” in IEEE 9th Workshop on Signal Processing Advances in Wireless Communications, 2008, pp. 261–265. [62] V. Khatana and M. V. Salapaka, “Noise resilient distributed average consensus over directed graphs,” IEEE Transactions on Signal and Information Processing over Networks, vol. 9, pp. 770–785, 2023. [63] Y. Deng, Z. Chen, and E. G. Larsson, “Exact average consensus under noisy communication links: A decentralized gradient perspective,” in IEEE Conference on Decision and Control, 2026. [64] B. Gharesifard and J. Cortés, “Distributed strategies for generating weight-balanced and doubly stochastic digraphs,” European Journal of Control, vol. 18, no. 6, pp. 539–557, 2012. [65] A. I. Rikos, T. Charalambous, and C. N. Hadjicostis, “Distributed weight balancing over digraphs,” IEEE Transactions on Control of Network Systems, vol. 1, no. 2, pp. 190–201, June 2014. [66] T. Charalambous, C. N. Hadjicostis, and M. Johansson, “Distributed minimum-time weight balancing over digraphs,” in International Symposium on Communications, Control and Signal Processing (ISCCSP), 2014, pp. 190–193. [67] A. D. Dominguez-Garcia and C. N. Hadjicostis, “Coordination and control of distributed energy resources for provision of ancillary services,” in IEEE International Conference on Smart Grid Communications, 2010, pp. 537–542. [68] P. Rezaeinia, B. Gharesifard, T. Linder, and B. Touri, “Push-sum on random graphs: Almost sure convergence and convergence rate,” IEEE Transactions on Automatic Control, vol. 65, no. 3, pp. 1295–1302, 2020. [69] 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. [70] S. Pu, A. Olshevsky, and I. C. Paschalidis, “A sharp estimate on the transient time of distributed stochastic gradient descent,” IEEE Transactions on Automatic Control, vol. 67, no. 11, pp. 5900–5915, 2022. [71] D. Jakovetic, D. Bajovic, A. K. Sahu, and S. Kar, “Convergence rates for distributed stochastic optimization over random networks,” in IEEE Conference on Decision and Control (CDC), 2018, pp. 4238–4245. [72] 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. [73] A. Nedić, A. Olshevsky, and W. Shi, “Achieving geometric convergence for distributed optimization over time-varying graphs,” SIAM Journal on Optimization, vol. 27, no. 4, pp. 2597–2633, 2017.

[74] R. Xin, A. K. Sahu, U. A. Khan, and S. Kar, “Distributed stochastic optimization with gradient tracking over strongly-connected networks,” in IEEE Conference on Decision and Control (CDC), 2019, pp. 8353– 8358. [75] S. Pu and A. Nedić, “Distributed stochastic gradient tracking methods,” Mathematical Programming, vol. 187, no. 1–2, pp. 409–457, 2021. [76] A. Defazio, F. Bach, and S. Lacoste-Julien, “SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives,” Advances in Neural Information Processing Systems, vol. 27, 2014. [77] R. Johnson and T. Zhang, “Accelerating stochastic gradient descent using predictive variance reduction,” in Advances in Neural Information Processing Systems, vol. 26, 2013. [78] R. Xin, U. A. Khan, and S. Kar, “Variance-reduced decentralized stochastic optimization with accelerated convergence,” IEEE Transactions on Signal Processing, vol. 68, pp. 6255–6271, 2020. [79] N. Michelusi, “Non-coherent over-the-air decentralized gradient descent,” IEEE Transactions on Signal Processing, vol. 72, pp. 4618– 4634, 2024. [80] W. Shi, Q. Ling, G. Wu, and W. Yin, “Extra: An exact first-order algorithm for decentralized consensus optimization,” SIAM Journal on Optimization, vol. 25, no. 2, pp. 944–966, 2015. [81] S. Pu, W. Shi, J. Xu, and A. Nedić, “Push–Pull Gradient Methods for Distributed Optimization in Networks,” IEEE Transactions on Automatic Control, vol. 66, no. 1, pp. 1–16, 2021. [82] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, “A unified theory of decentralized SGD with changing topology and local updates,” in Proceedings of the International Conference on Machine Learning. PMLR, 2020, pp. 5381–5393. [83] R. Xin and U. A. Khan, “A linear algorithm for optimization over directed graphs with geometric convergence,” IEEE Control Systems Letters, vol. 2, no. 3, pp. 315–320, 2018. [84] B. Recht, C. Re, S. Wright, and F. Niu, “Hogwild!: A lock-free approach to parallelizing stochastic gradient descent,” Advances in Neural Information Processing Systems, vol. 24, 2011. [85] D. Cederberg, X. Wu, S. P. Boyd, and M. Johansson, “An asynchronous bundle method for distributed learning problems,” in The Thirteenth International Conference on Learning Representations, 2025. [86] J. Wu, W. Hu, H. Xiong, J. Huan, V. Braverman, and Z. Zhu, “On the noisy gradient descent that generalizes as SGD,” in Proceedings of the International Conference on Machine Learning. PMLR, 2020, pp. 10 367–10 376. [87] Y. J. Cho, J. Wang, and G. Joshi, “Towards understanding biased client selection in federated learning,” in Proceedings of The 25th International Conference on Artificial Intelligence and Statistics. PMLR, 2022, pp. 10 351–10 375. [88] S. Wang and M. Ji, “A unified analysis of federated learning with arbitrary client participation,” Advances in Neural Information Processing Systems, vol. 35, pp. 19 124–19 137, 2022. [89] W. Chen, S. Horváth, and P. Richtárik, “Optimal client sampling for federated learning,” Transactions on Machine Learning Research, 2022. [90] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, “QSGD: Communication-efficient SGD via gradient quantization and encoding,” Advances in Neural Information Processing Systems, vol. 30, 2017. [91] J. Sun, T. Chen, G. Giannakis, and Z. Yang, “Communication-efficient distributed learning via lazily aggregated quantized gradients,” Advances in Neural Information Processing Systems, vol. 32, 2019. [92] M. F. Ul Abrar and N. Michelusi, “Biased federated learning under wireless heterogeneity,” IEEE Transactions on Wireless Communications, vol. 25, pp. 16 449–16 462, 2026. [93] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh, “SCAFFOLD: Stochastic controlled averaging for federated learning,” in Proceedings of the International Conference on Machine Learning. PMLR, 2020, pp. 5132–5143. [94] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, “On the convergence of fedavg on non-iid data,” in International Conference on Learning Representations, 2020. [95] 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. [96] T. Chen, J. Yan, Y. Sun, S. Zhou, D. Gündüz, and Z. Niu, “Mobility accelerates learning: Convergence analysis on hierarchical federated learning in vehicular networks,” IEEE Transactions on Vehicular Technology, vol. 74, no. 1, pp. 1657–1673, 2025.

19

[97] A. Rodio, G. Neglia, Z. Chen, and E. G. Larsson, “A unified convergence analysis for semi-decentralized learning: Sampled-to-sampled vs. sampled-to-all communication,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 40, no. 30, 2026, pp. 25 151–25 159. [98] F. P.-C. Lin, S. Hosseinalipour, N. Michelusi, and C. G. Brinton, “Delay-aware hierarchical federated learning,” IEEE Transactions on Cognitive Communications and Networking, vol. 10, no. 2, pp. 674– 688, 2024. [99] A. Koloskova, S. Stich, and M. Jaggi, “Decentralized stochastic optimization and gossip algorithms with compressed communication,” in Proceedings of the International Conference on Machine Learning, vol. 97. PMLR, 2019, pp. 3478–3487. [100] 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. [101] 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. [102] D. V. Dimarogonas, E. Frazzoli, and K. H. Johansson, “Distributed event-triggered control for multi-agent systems,” IEEE Transactions on Automatic Control, vol. 57, no. 5, pp. 1291–1297, 2012. [103] G. S. Seyboth, D. V. Dimarogonas, and K. H. Johansson, “Event-based broadcasting for multi-agent average consensus,” Automatica, vol. 49, no. 1, pp. 245–252, 2013. [104] C. Nowzari and J. Cortés, “Distributed event-triggered coordination for average consensus on weight-balanced digraphs,” Automatica, vol. 68, pp. 237–244, 2016. [105] D. Antunes, D. Silvestre, and C. Silvestre, “Average consensus and gossip algorithms in networks with stochastic asymmetric communications,” in 50th IEEE Conference on Decision and Control and European Control Conference, 2011, pp. 2088–2093. [106] S. Kar and J. M. F. Moura, “Sensor networks with random links: Topology design for distributed consensus,” IEEE Transactions on Signal Processing, vol. 56, no. 7, pp. 3315–3326, 2008. [107] D. P. Herrera, Z. Chen, and E. G. Larsson, “Distributed consensus in wireless networks with probabilistic broadcast scheduling,” IEEE Signal Processing Letters, vol. 30, pp. 41–45, 2023. [108] S. Sardellitti, S. Barbarossa, and A. Swami, “Optimal Topology Control and Power Allocation for Minimum Energy Consumption in Consensus Networks,” IEEE Transactions on Signal Processing, vol. 60, no. 1, pp. 383–399, Jan. 2012. [109] S. Vanka, V. Gupta, and M. Haenggi, “Power-delay analysis of consensus algorithms on wireless networks with interference,” International Journal of Systems, Control and Communications, vol. 2, no. 1-3, pp. 256–274, 2010. [110] M. Chen, N. Shlezinger, H. V. Poor, Y. C. Eldar, and S. Cui, “Communication-efficient federated learning,” Proceedings of the National Academy of Sciences, vol. 118, no. 17, 2021. [111] D. Alistarh, T. Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli, “The convergence of sparsified gradient methods,” Advances in Neural Information Processing Systems, vol. 31, 2018. [112] B. Wang, J. Fang, H. Li, and B. Zeng, “Communication-efficient federated learning: A variance-reduced stochastic approach with adaptive sparsification,” IEEE Transactions on Signal Processing, vol. 71, pp. 3562–3576, 2023. [113] H. Wang, S. Sievert, S. Liu, Z. Charles, D. Papailiopoulos, and S. Wright, “ATOMO: Communication-efficient learning via atomic sparsification,” Advances in Neural Information Processing Systems, vol. 31, 2018. [114] T. Vogels, S. P. Karimireddy, and M. Jaggi, “PowerSGD: Practical lowrank gradient compression for distributed optimization,” Advances in Neural Information Processing Systems, vol. 32, 2019. [115] S. Park and W. Choi, “Regulated subspace projection based local model update compression for communication-efficient federated learning,” IEEE Journal on Selected Areas in Communications, vol. 41, no. 4, pp. 964–976, 2023. [116] N. Shlezinger, M. Chen, Y. C. Eldar, H. V. Poor, and S. Cui, “UVeQFed: Universal vector quantization for federated learning,” IEEE Transactions on Signal Processing, vol. 69, pp. 500–514, 2021. [117] L. Fu, H. Zhang, G. Gao, M. Zhang, and X. Liu, “Client selection in federated learning: Principles, challenges, and opportunities,” IEEE Internet of Things Journal, vol. 10, no. 24, pp. 21 811–21 819, 2023. [118] T. Chen, G. Giannakis, T. Sun, and W. Yin, “LAG: Lazily aggregated gradient for communication-efficient distributed learning,” Advances in Neural Information Processing Systems, vol. 31, 2018.

[119] H. H. Yang, Z. Liu, T. Q. S. Quek, and H. V. Poor, “Scheduling policies for federated learning in wireless networks,” IEEE Transactions on Communications, vol. 68, no. 1, pp. 317–333, 2020. [120] C.-H. Hu, Z. Chen, and E. G. Larsson, “Scheduling and aggregation design for asynchronous federated learning over wireless networks,” IEEE Journal on Selected Areas in Communications, vol. 41, no. 4, pp. 874–886, 2023. [121] S. Wang, T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan, “Adaptive federated learning in resource constrained edge computing systems,” IEEE Journal on Selected Areas in Communications, vol. 37, no. 6, pp. 1205–1221, 2019. [122] Z. Yang, M. Chen, W. Saad, C. S. Hong, and M. Shikh-Bahaei, “Energy efficient federated learning over wireless communication networks,” IEEE Transactions on Wireless Communications, vol. 20, no. 5, pp. 1935–1949, 2021. [123] W. Shi, S. Zhou, Z. Niu, M. Jiang, and L. Geng, “Joint device scheduling and resource allocation for latency constrained wireless federated learning,” IEEE Transactions on Wireless Communications, vol. 20, no. 1, pp. 453–467, 2021. [124] C.-H. Hu, Z. Chen, and E. G. Larsson, “Energy-efficient federated edge learning with streaming data: A lyapunov optimization approach,” IEEE Transactions on Communications, vol. 73, no. 2, pp. 1142–1156, 2025. [125] M. Chen, Z. Yang, W. Saad, C. Yin, H. V. Poor, and S. Cui, “A joint learning and communications framework for federated learning over wireless networks,” IEEE Transactions on Wireless Communications, vol. 20, no. 1, pp. 269–283, 2021. [126] G. Zhu, J. Xu, K. Huang, and S. Cui, “Over-the-air computing for wireless data aggregation in massive IoT,” IEEE Wireless Communications, vol. 28, no. 4, pp. 57–65, 2021. [127] Z. Chen, E. G. Larsson, C. Fischione, M. Johansson, and Y. Malitsky, “Over-the-air computation for distributed systems: Something old and something new,” IEEE Network, vol. 37, no. 5, pp. 240–246, 2023. [128] A. Şahin and R. Yang, “A survey on over-the-air computation,” IEEE Communications Surveys & Tutorials, vol. 25, no. 3, pp. 1877–1908, 2023. [129] M. Goldenbaum, H. Boche, and S. Stańczak, “Harnessing interference for analog function computation in wireless sensor networks,” IEEE Transactions on Signal Processing, vol. 61, no. 20, pp. 4893–4906, 2013. [130] G. Zhu, Y. Wang, and K. Huang, “Broadband analog aggregation for low-latency federated edge learning,” IEEE Transactions on Wireless Communications, vol. 19, no. 1, pp. 491–506, 2020. [131] H. H. Yang, Z. Chen, T. Q. S. Quek, and H. V. Poor, “Revisiting analog over-the-air machine learning: The blessing and curse of interference,” IEEE Journal of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 406–419, 2022. [132] C. Xu, S. Liu, Z. Yang, Y. Huang, and K.-K. Wong, “Learning rate optimization for federated learning exploiting over-the-air computation,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 12, pp. 3742–3756, 2021. [133] C. Wang, Z. Chen, N. Pappas, H. H. Yang, T. Q. S. Quek, and H. V. Poor, “Adaptive federated learning over the air,” IEEE Transactions on Signal Processing, vol. 73, pp. 3187–3202, 2025. [134] J. Yao, W. Xu, G. Zhu, Z. Yang, K. Huang, and D. Niyato, “Over-theair multitask federated learning via cost-effective hybrid beamforming,” IEEE Transactions on Signal Processing, vol. 73, pp. 3977–3993, July 2025. [135] H. Hellström, V. Fodor, and C. Fischione, “Federated learning overthe-air by retransmissions,” IEEE Transactions on Wireless Communications, vol. 22, no. 12, pp. 9143–9156, 2023. [136] X. Cao, G. Zhu, J. Xu, and K. Huang, “Cooperative interference management for over-the-air computation networks,” IEEE Transactions on Wireless Communications, vol. 20, no. 4, pp. 2634–2651, Apr. 2021. [137] Z. Liu, Q. Lan, and K. Huang, “Over-the-air fusion of sparse spatial features for integrated sensing and edge AI over broadband channels,” IEEE Transactions on Wireless Communications, vol. 24, no. 4, pp. 2999–3013, 2025. [138] D. Wen, X. Jiao, P. Liu, G. Zhu, Y. Shi, and K. Huang, “Task-oriented over-the-air computation for multi-device edge AI,” IEEE Transactions on Wireless Communications, vol. 23, no. 3, pp. 2039–2053, 2024. [139] J. Liu, Y. Gong, and K. Huang, “Digital over-the-air computation: Achieving high reliability via bit-slicing,” IEEE Transactions on Wireless Communications, vol. 24, no. 5, pp. 4101–4114, May 2025. [140] L. Qiao, Z. Gao, M. Boloursaz Mashhadi, and D. Gündüz, “Massive digital over-the-air computation for communication-efficient federated

20

edge learning,” IEEE Journal on Selected Areas in Communications, vol. 42, no. 11, pp. 3078–3094, Nov. 2024. [141] S. Razavikia, J. M. Barros da Silva, and C. Fischione, “Channelcomp: A general method for computation by communications,” IEEE Transactions on Communications, vol. 72, no. 2, pp. 692–706, 2024. [142] S. Razavikia, J. M. B. da Silva, and C. Fischione, “Sumcomp: Coding for digital over-the-air computation via the ring of integers,” IEEE Transactions on Communications, vol. 73, no. 2, pp. 752–767, 2025. [143] J. Wang, A. K. Sahu, G. Joshi, and S. Kar, “Matcha: A matching-based link scheduling strategy to speed up distributed optimization,” IEEE Transactions on Signal Processing, vol. 70, pp. 5208–5221, 2022. [144] C.-C. Chiu, X. Zhang, T. He, S. Wang, and A. Swami, “Laplacian matrix sampling for communication- efficient decentralized learning,” IEEE Journal on Selected Areas in Communications, vol. 41, no. 4, pp. 887–901, 2023. [145] D. Pérez Herrera, Z. Chen, and E. G. Larsson, “Faster convergence with less communication: Broadcast-based subgraph sampling for decentralized learning over wireless networks,” IEEE Open Journal of the Communications Society, vol. 6, pp. 1497–1511, 2025. [146] X. Cao and T. Başar, “Decentralized online convex optimization with event-triggered communications,” IEEE Transactions on Signal Processing, vol. 69, pp. 284–299, 2021. [147] R. Nassif, S. Vlaski, M. Carpentiero, V. Matta, M. Antonini, and A. H. Sayed, “Quantization for decentralized learning under subspace constraints,” IEEE Transactions on Signal Processing, vol. 71, pp. 2320–2335, 2023. [148] R. Nassif, S. Vlaski, M. Carpentiero, V. Matta, and A. H. Sayed, “Differential error feedback for communication-efficient decentralized learning,” IEEE Transactions on Signal Processing, vol. 73, pp. 1905– 1921, 2025. [149] Z. Lin, Y. Gong, and K. Huang, “Distributed over-the-air computing for fast distributed optimization: Beamforming design and convergence analysis,” IEEE Journal on Selected Areas in Communications, vol. 41, no. 1, pp. 274–287, 2023. [150] 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. [151] Z. Zhai, X. Yuan, and X. Wang, “Decentralized federated learning via MIMO over-the-air computation: Consensus analysis and performance optimization,” IEEE Transactions on Wireless Communications, vol. 23, no. 9, pp. 11 847–11 862, 2024. [152] E. Ozfatura, S. Rini, and D. Gündüz, “Decentralized SGD with overthe-air computation,” in IEEE Global Communications Conference (GLOBECOM), 2020, pp. 1–6. [153] Y. Shi, Y. Zhou, and Y. Shi, “Over-the-air decentralized federated learning,” in IEEE International Symposium on Information Theory (ISIT), 2021, pp. 455–460. [154] N. Michelusi, “Interference-Robust Non-Coherent Over-the-Air Computation for Decentralized Optimization,” in ICC 2026 - IEEE International Conference on Communications, 2026, pp. 1–6. [155] Y. Deng, Z. Chen, and E. G. Larsson, “Robust and efficient average consensus with non-coherent over-the-air aggregation,” in IEEE International Conference on Communications, 2025, pp. 3455–3460. [156] J. Duchi, E. Hazan, and Y. Singer, “Adaptive subgradient methods for online learning and stochastic optimization,” Journal of Machine Learning Research, vol. 12, no. 61, pp. 2121–2159, 2011. [157] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in Proceedings of the International Conference on Learning Representations, 2015. [158] Y. Wang and A. Nedić, “Decentralized gradient methods with timevarying uncoordinated stepsizes: Convergence analysis and privacy design,” IEEE Transactions on Automatic Control, vol. 69, no. 8, pp. 5352–5367, 2024. [159] A. I. Rikos, N. Bastianello, T. Charalambous, and K. H. Johansson, “Distributed optimization and learning for automated stepsize selection with finite time coordination,” in 2025 IEEE 64th Conference on Decision and Control (CDC), 2025, pp. 4389–4395. [160] M. Even, H. Hendrikx, and L. Massoulié, “Asynchronous speedup in decentralized optimization,” IEEE Transactions on Automatic Control, vol. 70, no. 3, pp. 1467–1482, 2025. [161] A. Edin, M. Kieffer, M. Johansson, and Z. Chen, “Exploiting correlations in federated learning: Opportunities and practical limitations,” arXiv preprint arXiv:2604.14751, 2026. [162] H. S. Wang and N. Moayeri, “Finite-state Markov channel–a useful model for radio communication channels,” IEEE Transactions on Vehicular Technology, vol. 44, no. 1, pp. 163–171, 1995.

[163] N. H. Chau, E. Moulines, M. Rásonyi, S. Sabanis, and Y. Zhang, “On stochastic gradient langevin dynamics with dependent data streams: The fully nonconvex case,” SIAM Journal on Mathematics of Data Science, vol. 3, no. 3, pp. 959–986, 2021. [164] J. Cutler, D. Drusvyatskiy, and Z. Harchaoui, “Stochastic optimization under distributional drift,” Journal of Machine Learning Research, vol. 24, no. 147, pp. 1–56, 2023. [165] H. Robbins and D. Siegmund, “A convergence theorem for non negative almost supermartingales and some applications,” in Optimizing Methods in Statistics, J. S. Rustagi, Ed. Academic Press, 1971, pp. 233–257. [166] A. Nedić, A. Olshevsky, and M. G. Rabbat, “Network topology and communication-computation tradeoffs in decentralized optimization,” Proceedings of the IEEE, vol. 106, no. 5, pp. 953–976, 2018. [167] 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. [168] N. Michelusi, “Decentralized gradient descent: Bottleneck regimes and budget complexity,” arXiv preprint arXiv:2607.12172, 2026, submitted to the IEEE Transactions on Information Theory. [169] C. Ma, J. Li, K. Wei, B. Liu, M. Ding, L. Yuan, Z. Han, and H. Vincent Poor, “Trusted AI in multiagent systems: An overview of privacy and security for distributed learning,” Proceedings of the IEEE, vol. 111, no. 9, pp. 1097–1132, 2023. [170] K. Bonawitz et al., “Practical secure aggregation for privacy-preserving machine learning,” in Proc. 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1175–1191. [171] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in Proc. of the ACM SIGSAC Conf. on computer and communications security, 2016, pp. 308–318. [172] P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer, “Machine learning with adversaries: Byzantine tolerant gradient descent,” Advances in Neural Information Processing Systems, vol. 30, 2017. [173] E.-M. El-Mhamdi, R. Guerraoui, and S. Rouault, “The hidden vulnerability of distributed learning in byzantium,” in Proceedings of the International Conference on Machine Learning. PMLR, 2018, pp. 3521–3530. [174] Y. Chen, L. Su, and J. Xu, “Distributed statistical machine learning in adversarial settings: Byzantine gradient descent,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 1, no. 2, pp. 1–25, 2017. [175] R. Nassif, S. Vlaski, C. Richard, J. Chen, and A. H. Sayed, “Multitask learning over graphs: An approach for distributed, streaming machine learning,” IEEE Signal Processing Magazine, vol. 37, no. 3, pp. 14–25, 2020. [176] M. Hellkvist, A. Özçelikkale, and A. Ahlén, “Distributed continual learning with CoCoA in high-dimensional linear regression,” IEEE Transactions on Signal Processing, vol. 72, pp. 1015–1031, 2024. [177] D. Yuan, L. Wang, A. Proutiere, and G. Shi, “Distributed zeroth-order optimization: Convergence rates that match centralized counterpart,” Automatica, vol. 159, p. 111328, 2024. [178] N. Dal Fabbro, S. Dey, M. Rossi, and L. Schenato, “Shed: A newtontype algorithm for federated learning based on incremental hessian eigenvector sharing,” Automatica, vol. 160, p. 111460, 2024. [179] A. Fainman and S. Vlaski, “On the convergence of decentralized stochastic gradient-tracking with finite-time consensus,” IEEE Transactions on Signal Processing, vol. 74, pp. 1079–1093, 2026.

Related documents

• Budget-Constrained Multi-Consensus Decentralized Gradient Descent#1218243
• Structured Distributed Computation under Communication and Computation Constraints#796406
• DistributedDesignOptimizer: A modular Python framework for Setup, Execution and Processing of Distributed Design Optimization#1106145
• Learning and identification in complex systems through multi-objective optimization#8245
• Strong Global Convergence of the Consensus-Based Optimization Algorithm#1386218