Distributed Event-Based Learning via ADMM
Authors: Guner Dilsad ER
Sebastian Trimpe
Michael Muehlebach
Venue: ICML 2025 poster (2025)
Keywords: distributed learning
event-based optimization
dynamical systems
communication efficiency
heterogeneous data-distribution
Primary area: optimization
TL;DR: Our distributed learning method reduces communication cost, handles non-i.i.d. data distributions, ensures fast convergence, and is robust to failures, outperforming standard baselines.

Abstract: We consider a distributed learning problem, where agents minimize a global objective function by exchanging information over a network. Our approach has two distinct features: (i) It substantially reduces communication by triggering communication only when necessary, and (ii) it is agnostic to the data-distribution among the different agents. We can therefore guarantee convergence even if the local data-distributions of the agents are arbitrarily distinct. We analyze the convergence rate of the algorithm both in convex and nonconvex settings and derive accelerated convergence rates in a convex setting. We also characterize the effect of communication failures and demonstrate that our algorithm is robust to communication failures. The article concludes by presenting numerical results from distributed learning tasks on the MNIST and CIFAR-10 datasets. The experiments underline communication savings of 35\% or more due to the event-based communication strategy, show resilience towards heterogeneous data-distributions, and highlight that our approach outperforms common baselines such as FedAvg, FedProx, SCAFFOLD and FedADMM.

Distributed Event-Based Learning via ADMM
Guener Dilsad ER'
Sebastian Trimpe? ? Michael Muehlebach
Abstract
the burden off central processors and improves data privacy by avoiding centralized training and storage of data.
We consider a distributed learning problem, where agents minimize a global objective function by exchanging information over a network. Our ap- proach has two distinct features: It substan- tially reduces communication by triggering com- munication only when necessary, and (ii) it is ag- nostic to the data-distribution among the different agents. We therefore guarantee convergence even if the local data-distributions of the agents are arbitrarily distinct. We analyze the convergence rate of the algorithm both in convex and noncon- vex settings and derive accelerated convergence rates for the convex case. We also characterize the effect of communication failures and demon- strate that our algorithm is robust to these. The article concludes by presenting numerical results from distributed learning tasks on the MNIST and CIFAR-10 10 datasets. The experiments underline communication savings of 35% or more due the event-based communication strategy, show re- silience towards heterogeneous data-distributionss and highlight that our approach outperforms com- mon baselines such as FedAvg, FedProx, SCAF- FOLD and FedADMM.
Distributed learning is particularly challenging when the data is not independent and identically distributed (non- ii.d.) across the different agents. This situation often hin- ders the convergence to a globally optimal model. The non-i.id. nature leads to disparities in local datasets, pre- venting the local models from generalizing across the entire dataset, leading to a fundamental dilemma between min- imizing local and global objective functions (Acar et al., 2021). In addition, a second key challenge arises from the communication between agents, which is required to en- sure convergence to the global solution and may lead to a substantial overhead. This communication overhead results in a waste of energy (Li al., 2020b), and is prone de- lays and communication channel failures. As a result, both, non-i.i.d datasets and communication overhead, constitute major bottlenecks for enabling large-scale learning systems.
We provide an effective solution to both challenges. In- spired by the sent-on-delta concept (Miskowicz, 2006), we reduce the communication load by introducing an event- based communication strategy, such that each agent (or computational node) communicates only if necessary. Our communication rule enforces local constraints that collec- tively guarantee bounded overall error, a paradigm related to safe zone design strategies in distributed computing (Garo- falakis & Samoladas, 2017). Our approach is also rooted in event-based estimation, where communication is trig- gered by significant state changes. We further base our approach the Alternating Direction Method of Multi- pliers (ADMM). Our method is therefore robust against ill- ill-condiiioning and agnostic towards a disparity of the local data data-distributions among the agents (these can be skewed in arbitrary ways). The approach further enables an explicit trade-off between communication load on the network and solution accuracy via a small set of hyperparameters that have clear interpretation. We explicitly quantify the influ- ence of these hyperparameters on the solution accuracy and analyze the effect of communication failures. The article concludes by highlighting the effectiveness of our algorithm in training neural networks, and solving LASSO problems in a distributed and communication-effici
1. Introduction
Distributed learning refers to the minimization of global objective function over a network of agents, where each agent has only access to a local cost function and can com- municate with some or all agents in the network. Distributed learning systems provide solution for handling the grow- ing amount of data being generated everywhere on earth, by utilizing the computational power of individual devices in a network rather than relying on a central entity. This takes
'Learning and Dynamical Systems Group, Max Planck Institute for Intelligent Systems. 72076 Tübingen, Germany "Institute for Data Science in Mechanical Engineering, RWTH Aachen Univer- sity, 52068 Aachen, Germany. Correspondence to: Guener Dilsad ER <gder @ mee..mpp.de>.
manner. Our theoretical analysis builds on recent trend in the opti-
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Distributed Event-Based Learning via ADMM
mization literature (Wibisono al., 2016; Su et al., 2016; Muehlehach & Jordan, 2019; Tong & Muehlebach, 2023) that views algorithms as dynamical systems and leverages ideas from differential or symplectic geometry, as well as passivity and dissipativity (Lessard et al., 2016; Muehlebach & Jordan, 2020). As we will show, this enables convergence proofs and a convergence rate analysis for our distributed algorithms, together with an analysis of robustness against communication failures. Our work provides important in- sights into the behavior of the event-based optimization under communication failures, an aspect, which has been overlooked in prior works, and thereby lays the groundwork for future research in this area.
tionally, Liu al. (2021) propose lazy evaluation of dual gradients, reducing communication by skipping redundant updates, while (Chen et al., 2018) adaptively reuse lagged gradients to meet target accuracy with fewer communica- tion rounds. There has also been a third line of work that focuses on reducing communication via event-based trig- gering and compression of network parameters (Liu et al., 2019; Ghadikolaei et al., 2021: Singh et al., 2023; Zhang et al., 2023). While (Zhang et al., 2024; 2023) employ an ADMM-based strategy that is similar to ours, their focus lies on investigating different compression schemes, and not on analyzing convergence rates and the effect of communi- cation failures. wrent-triggerig has also been explored in contexts like dynamies model learning (Solowjow & Trimpe, 2020; Umlauft & Hirche, 2019), and Bayesian optimization (Brunzema et al., 2025). While highlighting the benefit of triggering for reducing communication, these works do not consider distributed optimization problems as we do herein.
Related Work: In the 1980s, Bertsekas & Tsitsiklis (1989) and others laid the foundation for the analysis of distributed algorithms. As machine learning became popular, dis- tributed learning emerged, specifically focusing on paral- lelizing computation for empirical risk minimization. Shokri & Shmatikov (2015) explored collaborative deep learning with multiple agents using distributed stochastic gradient descent, which was later coined federated learning (MeMa- han et al., 2017) and advanced by subsequent contributions (Kairouz al., 2021; Asad et al., 2023). A unifying element in these works is the consensus problem, where agents agrec on a common value or decision. This problem is both central to distributed optimization and is also a special instance of distributed optimization (Wei & Ozdaglar, 2012).
In addition to the communication overhead, another major challenge for distributed learning arises from non-i.i.d. data distributions across agents (Zhao et al., 2018: Li et al., 2020c; Glasgow et al., 2022). SCAFFOLD (Karimireddy et al., 2020) addresses this challenge by introducing a client control variate to improve convergence at the cost of doubling communication. Similarly, (Gao et al., 2022) enhances training with auxiliary drift variables, while (Zheng et al., 2024) selects representative clients and adjusts server gradients. Recent contributions by Li et al. (2020a); Acar et al. (2021); Shi al. (2023) add a proximal regularization term to the local objective functions of the individual agents, whereas Zhang et al. (2021) (FedPD) and Zhou & Li (2023); Wang et al. (2022); Gong et al. (2022) (FedADMM) address the challenge with ADMM formulations. However, compared to our work, FedADMM (Zhou & Li, 2023; Wang et al., 2022; Gong et al., 2022) relies on utilizing a random selection of agents that communicate and FedPD (Zhang et al., 2021) considers full participation, whereas we use an event-triggered mechanism. Alternatively, other splitting schemes such as Bouglas-Rachfore method proposed by Tran Dinh et al. (2021), similarly align local and global objectives but remain constrained by random agent participation.
The trade-off between communication and computation is in- evitable in distributed optimization (Nedic et al., 2018). Re- cent work by Cao et al. (2023) categorizes communication- efficient distributed learning into four main strategies: (1) minimizing the number of communications, (2) compres- sion, (3) managing resources (e.g., bandwidth), and (4) using game theoretical approaches. We focus our review on the first category that aligns with our work, and reduces com- munication by transmitting information only if necessary. A first line of work (McMahan et al., 2017; Wei Liu et al., 2021; Reisizadeh et al., 2020, and many more) proposes algorithms with a periodical exchange of model parameters either among all agents or randomly selected subsets for decreasing communication load. While this approach is particularly straightforward and easy to implement, the ran- dom sampling risks missing critical updates or performing redundant communications. A second line of work involves accelerated gradient methods for distributed optimization, reducing the need for many communication rounds to con- verge. For instance, Kovalev et al. (2020) and Nabli & Oyallon (2023) optimize the number of gradient evaluations together with communication rounds. Shamir et al. (2014) replaces gradient descent with Newton-like methods and Hendrikx et al. (2020) proposes statistical preconditioning where both methods further improve convergence rates at the cost of higher computational load per iteration. Addi-
ADMM remains a widely-used tool for distributed learning. with recent advancements focusing on improving conver- gence rates and communication efficiency. For example, Wang et al. (2025) introduce inertia and adaptive iteration strategies to accelerate convergence, while Song et al. (2025) controls inexactness and dynamically tunes penalty parame- ters. In addition, He et al. (2023) explore dynamic tuning of ADMM hyperparameters, and hierarchical grouping ap- proaches (Qiu et al., 2023), inspired by Elgabli et al. (2020), aim to reduce communication overhead by restricting up- dates to neighboring workers. These methods share the goal
2

---

Distributed Event-Basce Learning via ADMM
of improving the efficiency of ADMM in distributed settings, but they still rely periodic full-agent participation, whereas our approach uses event-triggered mechanisms to further reduce communication costs.
and the topology of the communication network. The con- vergence analysis requires Lyapunov-like function that is different compared to earlier work (Nishihara et al., 2015), due to the presence of the event-based communication.
As we also highlight in numerical experiments, a random selection of agents might prevent important local changes from propagating quickly through the network, leading to a slower convergence. To the best of our knowledge, this is the first work to provide a convergence analysis of distributed learning with event-triggered communication that addresses key aspects, such as packet drop and the presence of non-i.idd data.
(v) We study the robustness of our algorithm against com- munication failures, both in theory as well as in numerical experiments, which, the best of our knowledge, is largely missing in the literature (a notable exception for the con- sensus problem is (Bastianello et al., 2021)). We address communication failures algorithmically by proposing a rare periodic reset strategy. We show that, without such a re- set strategy, inter-agent errors accumulate rapidly in the presence of packet drops and prevent convergence.
Contributions are summarized as follows:
(i) We propose an event-based communication scheme for distributed optimization, where a communication event is only triggered, when the current state has deviated by predefined threshold A, indicating significant change in the local decision variables. Therefore, our approach is ef- fective in reducing communication overhead and can adapt to the limited communication resources in heterogeneous networks. Our method is also compatible with and com- (Hegazy et al., 2024; Mao et al., 2022; Wang et al., 2018) and fair aggregation techniques (Zhu& & Ling, 2021).
Outline:
The article is structured as follows: Sec. 2 de- scribes the problem formulation and introduces our event- based learning algorithm in the consensus setting. The more general formulation is discussed in Sec. 3, where we also introduce a dynamical systems model for our algorithm. Sec. 4 discusses the convergence analysis of the proposed algorithm and presents convergence rates, while empirical results that underline the theoretical findings are included in Sec. 5 and in App. G. The appendix contains additional tech- nical details about the communication structure in App. A and the details of the convergence analysis in App. C and D.
plementary to gradient compression/quantiatiie
(ii) We characterize the effect of the communication thresh- old A on the solution accuracy and therefore quantify the trade-off between communication and solution accu- racy. Compared to other ADMM-based approaches, such as (Zhang et al., 2021; Zhou & Li, 2023), our method is versatile, both in the selection of variables that are being communicated (which is important for reducing commu- nication in practice). as well as the different problem for- mulations that we can address. In particular, our approach goes beyond the scope of consensus problems, and can solve generic constrained optimization problems, sparse re- gression and LASSO problems, perform robust principal component analysis (Candès et al., 201 1), and solve dis- tributed learning instances where the features but not the data points are distributed (Boyd et al., 2010).
2. Event-Based Distributed Learning
We consider a distributed learning problem of the type min ΣN (zz), where the overall cost function f(x) is the sum of N individual, potentially nonsmooth func- tions. The different f" typically arise from different training datasets stored on different computational nodes. In the most basic instance, our algorithm arises from the consen- sus formulation
N
+ {()))
min E.
ERR
(1)
1=1
subject to x² =2= 2, i i= N,
where we impose the constraints xf = by correspond- ing dual variables n'. Thus, by guaranteeing constraint satisfaction, we can ensure consensus between the agents despite different local problems and, in particular, arbitrary non-i.i.d. data distributions among the computational nodes. In addition, we assume the function f³ IR" + R to be smooth, while g: IR= - is allowed to be nonsmooth (g typically represents a regularizer) and maps to the extended real numbers.
(iii) Numerical experiments support the theoretical analy- sis and highlight that our approach even converges in the most extreme non-i.i.d. setting, where each agent has only access to training data from a single class (see the MNIST classifier example in Sec. 5). Comparisons to the baselines FedADMM (Zhou& & Li, 2023), SCAFFOLD (Karimireddy et al., 2020), FedProx (Li et al., 2020a) and FedAvg (McMa- han et al., 2017) demonstrate superiority both in terms of communication efficiency and classification accuracy.
Our event-based algorithm, stated in Alg. 1, works as fol- lows. Each agent (or computational node) i, i I,..., N. has access to the local objective function f its local so- lution x', its local multiplier w', and an estimate 2 of the consensus variable z. We further introduce the agent N
(iv) We demonstrate an accelerated convergence rate, and derive symbolic expressions that relate the convergence rate to instance-speciffe quantities such as the condition number
3

---

Distributed Event-Basce Learning via ADMM
Agent 1
Agent 2
Agent 3
Agent 4
Algorithm 1 Event-Based Distributed Learning with Over-
Relaxed ADMM
fk 11
11
4
11
42
AA 1
Require: Local objective functions f", parameters p.
9[0]
11
9[4]
9(0)
dd A reset period T
Require: Initialize atj = zo, 20 = Co = =z0, i²_1 = ub
Agent
for k = 0 to tmax do
for 1 to N do
Figure 1: The figure illustrates the distributed learning setup. The Agents 1 44 store x², u² and perform updates based on the information received by Agent 5, according to Alg. Agent 5, stores and performs updates based on the infor- mation received by Agent 1-4. This architecture is common in distributed learning, where single server aggregates up- dates from multiple distributed clients to collaboratively train a model.
2j - receive 24 - 21/-1]
{Agent i}
" 1 + ax 2k + (1 =]
Tk+1 arg min.. f((x' x² 2k + ufg 1
event-based send of d d2et1
[M]
{See (2)}
end for
ÇA f receive +े Eveey (d - djs)) {Agent N N+1}
aR+1 = arg min; g() + 1 - CA- -(1 a))xx 1
event-based send of 2x+1 1 2[k]
(acting as server) that has access to g. the variable 2, and maintains an estimate Ç of the average
mod(k + 1, = 0 then
perform reset + ČA = Ck. 2x = 2k
N Σ
end if end for
Sk == N
(aak+11 + ui)).
based and randomized event-based.
Following the communication structure in Fig. 1, the algo- rithm proceeds in two steps:
Vanilla event-based: This communication rule is inspired from the sent-on-delta concept (Miskowicz, 2006), which aims to reduce the number of communications by only send- ing updates when significant changes occur. A communica- tion is triggered, if the value d' has deviated by more than the predefined threshold ~ 0 compared to the value that was last communicated. We introduce the variable diw to de- note the value di that was last communicated and add the in- dex to the set C/++1 The set C+++1 denotes the set of agents that trigger communication of di++1 time-step k, that is,
Each agent i = I,...,,N N first updates its estimate a based on whether it receives event-based communication from the agent N+ The agent then updates its multiplier vi and solves local minimization over f², which also includes a quadratic regularization term. The regularization term ensures that the minimization is well-conditioned (a key advantage to dual ascent, for example) and the local solution xf is biased towards af. In practice, the minimization is replaced by fixed number of (stochastic) gradient descent steps. If the resulting value 1 == a +uj of the agent is signifi- cantly different from the value that it last communicated to the agent N 1,, an event-based communication is triggered and the difference of di++1 to the last communicated value is sent to the agent N +1.
Parallel update of agents i i= 1,..., N:
Id - -aandijnl >> A = iE
and d - din is sent out. Similarly, agent N + 1 triggers communication if | 2n1] > A We also model communication failures as drops, which we represent by the variables X The variable X6+11 takes the value X (di++ dny) if di+ dd'y is not received by the di agent +1; otherwise X = O. The agent N+1 updates its estimate of the average Çe according to the primal and dual variables that it has received at time k; that is,
di
iii Update of agent N+1: The agent N+1 updates its esti- mate Ç of Ç by accumulating the d' variables that it receives from all agents. It then updates the consensus variable 2 by solving local minimization over g with a quadratic regularization term. Note that if the nonsmooth component g is missing, 2 is simply set to Č - (1 (1-a) 2.) Finally, the agent 1+1 triggers an based communication if the value zk+1 is significantly different from the value that it last communicated to the agents 1....,N. N.
= +
Σ (ditt - dig + 11
KECK
Randomized event-based: The protocol makes a case distinction. If -d'+1-dpn] S Ad, a communication is ran- > Ad,
Next, we explain the details of the event-based communi- cation protocol on the example of the communication of d', which is related to the primal x² and dual u' variables of agent i. The other event- based communications proceed similarly. The protocol comes in two variants, vanilla event-
domly triggered with probability Puig. If [[ a communication is triggered with certainty. Randomized communication from agent N + 1 to the other agents works in a similar way. If | =my S A then a
4

---

Distributed Event-Basce Learning via ADMM
communication is randomly triggered with probability Puig between agent N and agent i.
imposing the same condition on the individual components I' In addition, we present convergence result for general nonconvex cases in Thm. 2.3 leading to sublinear conver- gence rates. The proof is provided in App. B.
We observed in our numerical experiments that randomized event-based often improves vanilla wvent-based in terms of the achieved communication versus solution accuracy trade-off.
Theorem 2.3. Let each f IR" + R be smooth (potentially nonconvex) and let g IR - be a proper, closed convex function. Let the relaxation parameter be a = 1, and the communication threshold Dn decay as Ds Ao/ + 1)². Then, the gradients and residuals converge with a rate of ( (1),k,, and the following bound holds:
The error caused by the event-based communication remains bounded all times thanks to the communication protocol and the periodic resets. This is summarized with the next proposition, whose proof is included in App. E:
Proposition 2.1. The error Sx iteration k is bounded by I5e- Ck| A TXx. where T denotes the reset period (see Alg. 1) and x is bound on the disturbance de.
1
K
2
)
Th+1
GK+1
K
3N
6N
where Thtn gradient terms are given by
2k+1 are the residuals, and the
We now state the main convergence result for Alg. 1. The result arises as corollary from the convergence analysis in the more general distributed optimization setting (see Thm. 4. We also provide sublinear convergence rates a nonconvex setting (see Thm 2.3).
G++IE 1. PN
(
Corollary 2.2. Let f = E f be m-strongly convex and L-smooth with K. = L/m, and g be corvex. Let the step-size be = (mL) K" with e E (0), and a = 1. For large enough K. we have
3. Event-Based ADMM as a Dynamical System
We introduce a more general problem formulation that en- compasses the previous section as a special case in order to broaden the scope of our analysis. This leads to the following constrained minimization problem
1
2k
5 2+2 AZ +
I 2.12 2.
Dot
4 1
N
min FER" =ER
f(x + g()), subject to Ar B= (3)
where 2. is the optimal value for the consensus variable and Dn represents the initial error, Do = 1 2.12 -2.2 + N |ub 10-u. 2 with ut, denoting the optimal values of the dual variables associated with each agent. Here, captures the error arising from the event-based communication.
where x E RpP and E IR9 are decision variables, A E RT B E Rrxq, and E R' are corresponding matrices, and the objective function is decomposed into a smooth part [ IR. + and a nonsmooth part g: RR. We will pro- vide an analysis under the following standard assumptions in distributed optimization.
1 DE -i=ilub
N
A= NA"+A=
-T(Nx++ ==
Assumption 3.1. The matrix A is invertible and B is full column rank.
The convergence result bounds the distance between the consensus variable zy and the optimal solution z. = x. that minimizes (I). The analysis models our event-based learning algorithm as a dynamical system, accounting for disturbances introduced by the event-based communication strategy. By design, these disturbances remain bounded under the communication protocol. The next section elab- orates on the formulation of our algorithm as a dynamical system.
Assumption 3.2. The function f is m-strongly convex and L-smooth. The function is convex.
It is important emphasize that the assumption of strong convexity for f is introduced derive linear rates within dynamical systems framework. This assumption does not limit the practical applicability of the algorithm and a corresponding nonconvex result is included in Thm. 2.3. We also note that Assumption 3.2 allows for nonconvex f (see (1)) that Σ is strongly convex.
The strong convexity assumption enables faster conver- gence rates compared to more general nonconvex scenarios. Specifically, under this assumption, the rate of convergence is linear, shown in Cor. 2.2 and accelerated. In contrast, without such assumptions, convergence rates are generally much slower, typically sublinear or achieving only asymp- lotic convergence.
The formulation in (3) accommodates a variety of dis- tributed optimization problems, including consensus, re- source sharing, and distributed model fitting, see for exam- ple (Boyd et al., 2010). App. A further highlights how the general formulation can be tailored and simplified to accom- modate specific applications, such as the sharing problem or finding a consensus on a graph.
We note that the strong convexity assumption in Cor. 2.2 only requires f : Ei f' be strongly convex, without
5

---

Distributed Event-Based Learning via ADMM
Our event-based distributed learning method is summarized in Alg. 2. The algorithm is based an over-relaxed version of ADMM, where an event-based communication structure between different agents is introduced. The over-relaxation brings the additional parameter a, which, as we will show, can be used to achieve faster convergence rates. The com- munication structure of the algorithm is shown in Fig. 2 and includes three agents that keep track of the individual quantities T4K Ark, 8k B2g, and the dual multiplier ug- In the special case of the consensus problem, the updates of the primal variable zy and dual variable ug decompose further into local updates based on oi and u.. which results in the communication structure shown in Fig. 1.
whereby the first two involve optimization problems that can be replaced by their corresponding stationarity conditions. This yields the following implicit update equations:
V[((2+1) PA T (AIR+1 + 8 c (
0g(2+++)++++ (af --1- 1111-111111111 (1-a) B2x B2x+1 ac+ū.)
"*+1 = ui + af (1 - (x) + 8k+1 - oX.,
which can be expressed by the dynamical system shown in Fig. 2. We note that the variable 21++1 is uniquely de- termined by 6% and ii. and does not depend on 2g, which means that only &A == (#k; u*x) comprises the state of the dynamical system. We further note that the dynamical sys- tem includes a nonlinear component, which arises from the (sub)gradient evaluations f and 0g, and the system is subjected to external disturbances eg that arise from the event-based communication. The detailed derivation and the corresponding matrices for the dynamies in Fig. 2 are included in App. C. Our convergence analysis will build on the dynamical systems model of Alg. 2. While our analysis is inspired by earlier works, such as (Nishihara et al., 2015) and (I (Lessard et al., 2016), the I. Lyapunov function that is used to prove convergence rates are different due to the external disturbances caused by the event-based communication.
Alg. begins by initializing its variables, and over a series of iterations, agents alternate between sharing information and optimizing their local variables. Key steps include up- dating variables based on local objectives and residuals, and triggering communication events when individual resid- ual changes exceed predefined thresholds. The algorithm leverages event- based communication to reduce the commu- nication load, while still achieving convergence towards an optimal solution of (3), we will show in the following sec- tion. The event-based communication proceeds in Sec. 2, that is, the r-agent, for example, triggers communication with the other agents if |rx+1 -Mps] >> A", at which point it sends the difference r*+1-TI to the other agents. We again model communication failures by introducing the variables Xk+1 if the communication is not received by the u-agent at time k++1, 1. The notation is analogous for the remaining agents and communication lines (see also Fig. 2).
U
Th++1
8k+1
8(H]
Uk+11
91-41
874)
Tk+1
Algorithm 2 Event-Based Distributed Optimization with Over-Relaxed ADMM
Delay
8k+1
56
Require: Functions/ f and g, matrices A and B, vector c, parameters and a. Initial condition 20, 20
Mk+1
14k
Å
6
C
F.y
11
Yn =-= = 8- = A = 8 = =8 = B20, uo = in - úg 0
Mk41 SE41
for = to max do
sr 0% + receive $k+1 k uk+1 - 22(1]
T = argmin, (xx + [ Ax + 3/ c + 0r 12
Figure 2: The figure visualizes the event-based commu- nication structure of Alg. 2 at the top and discrete-time dynamical system which represents the sequence generated by the event-hased ADMM algorithm on the bottom. The function & is nonlinear and represents the evaluation of (sub)gradients.
event-based send rk+1 - T[k) where rk+1 A
1 0 receive F | UA+ 1 - U[A] 24+1 argmming( (2) H2 a - B BBx+BBBBBBB B uc
event-based send 1 - [|)) where s B B
" + receive rk+1 M Sk+1 [
1k+1 = uk + ar x+ - (1 - a 888 + + - ac
4. Convergence Analysis
event-based send u [[k]]
if (o
then
This section provides convergence guarantees for the event- based learning algorithm (Alg. 2). The detailed proof for Thm. 4.1 is provided in App. D.
reset + Fk41 1 guar 8k41, # uk+1
end if
end for
Theorem 4.1. Let Assumption 3.1 and 3.2 be satisfied and let the step-size for Alg. be p <<V for some e 2 and a E (0.675, + V1-1/Vm), K =
Alg. has three update steps that occur sequentially,
6

---

Distributed Event-Based Learning via ADMM
(A)) where a and a denote the minimum and maximum singular value of matrix, respectively. Then, for large enough K, the following bound holds:
5. Numerical Experiments
This section discusses the performance of Alg. I in nu- merical experiments, highlighting that Alg. achieves fast convergence while reducing communication. Numerical experiments with the more general version (Alg. 2) are in- cluded in App. G, where distributed training over network of agents is explored. We also investigate the tradc-off be- tween communication load and solution accuracy achieved by selecting different communication thresholds. The com- munication load calculated by counting the number of triggered communications for Tmxx number of steps and normalizing according to the full communication case of one data package per round.
Ex-Ex1 =x - E.P(1
60x
4x -
al1-la- 1)
with Ea = (Sk; ux), and where 8k: = BEE, un is the dual variable, and &. the optimizer corresponding to (3). Fur- thermore, A
X") represents the error arising from the event-based communication and kp= -
We conclude the section by highlighting a few important points.
(i) For e 00,0=11 the bound considerably simplified to
90
Validation Accuracy %
80
I. Alp. Rand, FddADMM
1 [6 - $ - -c-2 (1 AVR
2 + +60x2A²
70
FodAvg, FedPrxx SCAFFOLD
60
50
which shows that the convergence rate scales with 1/EE and is therefore accelerated. This also highlights that the same convergence rate (up to constants) can be achieved with the event-based learning algorithm stated in Alg. compared to a standard ADMM algorithm. As we will show in the numerical experiments, our event-based algorithm reduces communication without any significant reduction in accuracy.
Alg. (A 1.73)
40
Alg. I-Rand (A 3.75,, 0.7)
FedAvg pert_rate- - 0.7
30
FedProx -pprrrtrreee pate 0.7
20
FedADMM part, 0.9
SCAFFOLD part
10
0
50
100
150
Round
Communication Load %
100
(ii) The bound from Thm. 4.1 also highlights how the com- munication thresholds A affect the solution accuracy. In the simplified scenario with e = 0, a = 1 (the more general scenario follows the same rationale), the solution accuracy bounded by [&x - I 8x.A, for large enough This
80
Anm
60
40
Alg. 1 (2 1.75)
Alg. I-Rand (A 3.75, = 0.7)
20
FeddvgEeeProoSSAATOLD part.rote note 0.7
means that the solution accuracy of Alg. 2 is proportional to the condition number and A.
FodADMM pori.rate = 0.9
0
50
100
150
Round
(iii) We can therefore easily ensure convergence, by choos- ing a time-varying A = As such that A + 0. The formal statement is included and derived in App. F. We also obtain precise nonasymptotic bounds. For example, if A Ao/(k + 1) for any t > 0, we conclude that the error converges with O(1/k9) (see again App. F).
Figure 3: Validation accuracy (top) and communication load percentage (bottom) over 150 communication rounds for training a CIFAR-10 classifier. The results indicate that Alg. achieves top accuracy at a lower communication rate. The plots compare the performance of various algo- rithms, including Alg. 1 with different parameter settings (Vanilla and randomized), FedAvg, FedProx, FcMADMM. and SCAFFOLD. Notably, ADMM-based methods (Alg. 1, Alg. 1-Rand and FedADMM) demonstrate better conver- gence by reaching up to 78% test accuracy. compared to other algorithms FedAvg, FedProx and SCAFFOLD, which reach only 70% accuracy. Among ADMM based methods, Alg. and Alg. 1-Rand achieve the same accuracy with over 20% less communication load. Communication load curves smoothed using window length of three for visualization purposes.
(iv) If f fails to be strongly convex, we can include small regularizer, for example of the type m) 2//2/ Choosing diminishing regularizer with m = (1/22) and a diminish- ing threshold A = O(1kaA) can be shown to result in an accelerated convergence rate of (1/k²))
(v) The topology of the communication network, rep- resented by the matrix A, directly influences the con- vergence rate, through the condition number к (A)) This formulation allows us to gen- eralize our convergence results beyond simple clivnt-server architectures. See App. A.2 for a detailed discussion on how agent network topology is encoded the matrix A.
7

---

Distributed Event-Basce Learning via ADMM
MNIST Target Accuracy
CIFAR-10 Target Accuracy
Algorithm
80 %
85%
90%
70%
75%
77%
78%
Alg. 1 Randomized
629
693
1723
12531
13422
15008
18376
Alg. 1- Vanilla
816
1285
1710
12214
14780
14780
20690
Fc (Zhou & Li, 2023)
800
1200
>2000
12000
15000
21000
27000
FedAvg (McMahan et al., 2017)
800
2000
N/A
3000
N/A
N/A
N/A
FedProx (Li et al., 2020a)
1000
2000
N/A
6000
N/A
N/A
N/A
SCAFFOLD (Karimireddy et al., 2020)
1600
2000
3200
12000
N/A
N/A
N/A
The total number of communication events required by each algorithm to achieve the target accuracies for the MNIST and CIFAR-IO 10 classifiers within 100 and 150 rounds, respectively. "N/A" indicates cases where the target accuracy was not reached within the specified rounds. Parameter choices for the algorithms are detailed in Appendix G. Reported values are averages over multiple experiments with different random seeds, with standard deviations below 2%, making them negligible. The corresponding communication load and accuracy trends for the rightmost column of CIFAR-10 shown in Fig. 3. The results emphasize the trade-off between achieving higher validation accuracy and maintaining communication efficiency across various algorithm configurations.
Table 1:
Due to space limitations, we present two examples in this section. Further experiments (including linear regression, LASSO, and distributed training over network of agents) are presented in App. G. App. G also includes hyperparam- eters for the experiments, model details and discusses the effect of communication failures.
adopting an event-based agent selection approach and out- performs all baselines by yielding uniformly better trade-off curves.
6. Conclusion
We introduce an event-based distributed learning approach that effectively reduces communication overhead by trig- gering events only when local models undergo significant changes. The method, based on over-relaxed ADMM, ex- hibits accelerated convergence rates convex settings, demonstrates robustness to communication failures, and outperforms common baselines such as FedAvg, FedProx, SCAFFOLD and FedADMM in our experiments, which include an MNIST and CIFAR-10 10 learning task. The exper- iments highlight that savings of more than 35% are possible without significantly degrading the solution accuracy (less than ). Our method allows for explicit trade-offs be- tween communication load and solution accuracy, making it promising for large-scale learning systems with heteroge- neous data and communication constraints.
We start by evaluating the performance of Alg. I on MNIST (Deng, 2012) and CIFAR-10 (Krizhevsky, 2009). Tab. reports the total number of communication events required by each algorithm to achieve the target accuracies for the MNIST and CIFAR-10 classifiers. Our event-based algo- rithm consistently requires fewer communication events to achieve high accuracies compared to baseline methods. This reduction is attributed to the selective triggering mechanism, which prevents unnecessary communication while ensur- ing convergence. For instance, on the CIFAR-10 dataset, our approach achieved 78% accuracy with a cost of 18,376 communication events, compared to 27,000 for FedADMM.
The comparison with other federated learning methods em- phasizes the challenges associated with non-i.i.d. data dis- tribution and communication overhead. FedAvg, as high- lighted in (Li et al., 2020c; Glasgow et al., 2022), experi- ences slowdowns in the presence of non-i.i.d. data, and increasing participation does not necessarily alleviate this issue. FedProx has the same issue and unable to converge to classifier that generalizes across all digits. FedADMM and SCAFFOLD can indeed cope with non-i.i.d. data, in general, both achieving high classification accuracies. How- ever, FedADMM has disadvantages arising from the random sampling mechanism and SCAFFOLD suffers from an addi- tional communication load to communicate two variables (client drift and local model). Notably, all baselines employ random selection of agents, which, in non-i.i.d. scenarios, misses crucial changes and results in a waste of communi- cation resources. Our method addresses these challenges by
While our approach offers significant improve- ments in communication efficiency, has not yet accounted for adversarial attacks, such as gradient poisoning, or un- reliable nodes in the network. These factors could poten- tially degrade the robustness of the method. Nevertheless, our event-based methodology can be integrated with robust aggregation or anomaly detection methods (Pillutla et al., 2022; Yin et al., 2018) to improve security without compro- mising communication efficiency. Additionally, this method has not been specifically analyzed with respect to differen- tial privacy and does not address privacy concerns in the current formulation.
Limitations:
Discussion: In this article, focused communication efficiency and convergence relationship under some con-
8

---

Distributed Event-Basce Learning via ADMM
straints. However, practical implementations often face additional challenges, such limited bandwidth, high la- tency, and network failures. Although we have not explic- itl named these factors, they can be effectively modeled through our packet drop framework, which provides a foun- dation for handling such constraints.
alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1-122, 2010.
Brunzema, P., von Rohr, A., Solowjow, F., and Trimpe, S. Event-triggered time-varying Bayesian optimization. Transactions on Machine Learning Research, 2025.
Furthermore, while we initially framed our algorithm as synchronous method, event-based communication can also be adapted function in asynchronous systems. This flexibility allows the method to accommodate real-world scenarios with varying degrees of network reliability and synchronization.
Candès, E. J., Li, X., Ma, Y., and Wright, Robust principal component analysis. Journal of the ACM, 58(3):1-37, 2011.
Cao, X., Başar, T., Diggavi, S., Eldar, Y. C., Letaief, K. B., Poor, H. V., and Zhang, J. Communication- tributed learning: An overview. Journal on Selected Areas in Communications, 41(4):851-87) 2023.
dis-
Finally, our method is compatible with compression and quantization techniques, which can further reduce the size of the models exchanged during communication events and improve communication efficiency. This can also help mini- mize the amount of data stored in the agents, contributing to more efficient memory usage and reducing the overall communication load.
Chen, T., Giannakis, G. B., Sun, T., and Yin, W. LAG: Lazily aggregated gradient for communication-effiiienn distributed learning. Proceedings of the International Conference on Advances in Neural Information Process- ing Systems, pp. 5055-5065 2018.
Deng, L. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-142, 2012.
Impact Statement
This article advances machine learning by introducing communication-efficee efffficc,,,,,nffiiiiiettt, event-based distributed learning method, enabling scalability for resource conssrriind sys- tems. While the work does not explicitly address adversarial robustness or differential privacy, future extensions could explore these aspects to further improve security in applica- tions. We see no immediate negative societal impacts.
Elgabli, A., Park, J., Bedi, A. S., Bennis, M., and Aggar- wal, V. GADMM: Fast and communication efficient framework for distributed machine learning. Journal of Machine Learning Research, 21:1-39, 2020.
Gao, L., Fu, H., Li, L., Chen, Y., Xu, M., and Xu, C.-Z. FedDC: Federated learning with non-iid data via local drift decoupling and correction. Proceedings of the Con- ference Computer Vision and Pattern Recognition, 2022.
References
Acar, D. A. E., Zhao, Y., Navarro, R. M., Mattina, M., Whatmough, P. N., and Saligrama, V. Federated learning based on dynamic regularization. Proceedings of the International Conference on Learning Representations, pp. 1-36, 2021.
Garofalakis, M. and Samoladas, V. Distributed query mon- itoring through convex analysis: Towards composable safe zones. Proceedings of the International Conference on Database Theory, 68(14):1-18, 2017.
Asad, M. Shaukat, S., Hu, D., Wang, Z., Javanmardi, E., Nakazato, J., and Tsukada, M. Limitations and future aspects of communication costs in federated learning: A survey. Sensors, 23(17):3358, 2023.
Ghadikolaei, H. S., Stich, S. U., and Jaggi, M. LENA: Communication-effce effficciiiinneiiiinnnnt distributed learning with self- triggered gradient uploads. Proceedings of the Interna- tional Conference on Artificial Intelligence and Statistics. pp. 3943-3951, 2021.
Bastianello, N., Carli, R., Schenato, L., and Todescato, M. Asynchronous distributed optimization over lossy net- works via relaxed ADMM: Stability and linear conver- gence. IEEE Transactions on Automatic Control, 66(6): 2620-2635, 2021.
Glasgow, M., Yuan, H., and Ma, Sharp bounds for fed- erated averaging (local sgd) and continuous perspective. Proceedings of the International Conference on Artificial Intelligence and Statistics, 151, 2022.
Bertsekas, D. P. and Tsitsiklis, N. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, 1989.
Gong, Y., Li, Y., and Freris, N. M. FedADMM: A robust federated deep learning framework with adaptivity to sys- tem heterogeneity. Proceedings of the IEEE International Conference on Data Engineering, pp. 2575 77887, 2022.
Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, Distributed optimization and statistical learning via the

---

Distributed Event-Basse Learning via ADMM
He, S., Zheng, J., Feng, M., and Chen, Y. Communication- efficient federated learning with adaptive consensus ADMM. Applied Sciences, 13(9):5270, 2023.
Liu, Y., Sun, Y., and Yin, W. Decentralized learning with lazy and approximate dual gradients. IEEE Transactions Signal Processing, 69; 69:1362-1377 2021.
Hegazy, M., Leluc, R., Ting Li, C., and Dieuleveut, A. Compression with exact error distribution for federated learning. Proceedings of the International Conference on
Mao, Y., Zhao, Z., Yan, G., Liu, Y., Lan, T., Song, L., and
Ding, W. Communication-effin effficient federated learning with adaptive quantization. ACM Transactions on Intelli- gent Systems and Technology. 13(4), 2022.
Artificial Intelligence and Statistics, 238:613 621, 2024.
Hendrikx, H., Xiao, L., Bubeck, S., Bach, F., and Mas- soulié, L. Statistically preconditioned accelerated gradi- ent method for distributed optimization. Proceedings of the International Conference on Machine Learning, 119: 4203 4227, 2020.
McMahan, H. B., Moore, E.,, Ramage, D., and Hampson, S. Coomuuncation-effiicci learning of deep networks from decentralized data. Proceedings of the International Conference on Artificial Intelligence and Statistics, 54: 1273-1282, 2017.
Kairouz et al., Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2):1-210, 2021.
Miskowicz, M. Send-On-Deiln Concept: An event-based data reporting strategy. Sensors, 6(1):49 63, 2006.
Muehlebach, M. and Jordan, M. I. A dynamical systems
Karimireddy, S. P., Kale, Mohri, M., Reddi, S. J., Stich, S. U., and Suresh, A. T. SCAFFOLD: Stochastic con- trolled averaging for federated learning. Proceedings of International Conference on Machine Learning, 119: $132-5143, 2020.
perspective on Nesterov acceleration. Proceedings of the International Conference on Machine Learning, 97: 4656-4662, 2019.
Muchlebach, M. and Jordan, M. Continuous-time lower bounds for gradient-based algorithms. Proceedings of the International Conference on Machine Learning, 1 119: 2020.
Kovalev, D., Salim, A., and Richtárik, Optimal and practical algorithms for smooth and strongly convex de- centralized optimization. Proceedings of the Conference on Advances in Neural Information Processing Systems, pp. 18342-18352, 2020.
Nabli, A. and Oyallon, E. DADAO: Decoupled accelerated decentralized asynchronous optimization. Proceedings of the International Conference Machine Learning, 202: 25604-25626 2023.
Krizhevsky, Learning multiple layers of features from tiny images. Technical Report, University of Toronto, 2009.
Nedic, A., Olshevsky, A., and Rabbat, M. G. Network topology and cummunication-computatii tradeoffs in decentralized optimization. Proceedings of the IEEE, 106 (5):953-976, 2018.
Lessard, L., Recht, B., and Packard, A. Analysis and de- sign of optimization algorithms via integral quadratic constraints. SIAM Journal on Optimization, 26(1):57-95, 2016.
Nishihara, R., Lessard, I.,, Recht, B., Packard, A., and Jordan, M. I. A general analysis of the convergence of ADMM. Proceedings of the International Conference on Machine Learning, 37:343-3522 2015.
Li, M., Sanjabi, M., and Jaggi, M. Federated optimization in heterogeneous networks. Proceedings of the Conference Machine Learning and Systems, 2:429 450, 2020a.
Pillutla, K., Kakade. S. M., and Harchaoui, Z. Robust aggregation for federated learning. IEEE Transactions on Signal Processing, 70: 142-1154, 2022.
Li, T., Sahu, A. K., Talwalkar, A., and Smith, V. Feder- ated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 30-3),00-60, 2020b.
Polyak, B. T. Introduction to optimization. Optimization Software Inc., Publications Division, New York, 1987.
Li, X., Yang, W., Huang, K., Wang, S., and Zhang, On the convergence of FedAvg on non-i.i.d. Proceedings of the International Conference Learning Representations, pp. 1-26, 2020c.
Qiu, Y., Lei, Y., and Wang, G. PSRA-HGADMM: com- munication efficient distributed ADMM algorithm. Pro- ceedings of the 52nd International Conference on Parallel Processing, pp. 82-91, 91, 2023.
Liu. Y.. Xu, W., Wu, G., Tian, Z., and Ling, Q. Communiction-eenssoedd ADMM for decentralized con- sensus optimization. IEEE Transactions on Signal Pro- cessing, 67(10))5565-2577 2019.
Reisizadeh, A., Jadbabaie, A., Mokhtari, A., Hassani, H., and Pedarsani, R. FedPAQ: A communication--fficin federated learning method with periodic averaging and
10

---

Distributed Event-Based Learning via ADMM
quantization. Proceedings of the International Confer- ence on Artificial Intelligence and Statistics, 108:2021- 2031, 2020.
learning via atomic sparsification. Proceedings of the International Conference on Advances in Neural Infor- mation Processing Systems, pp. 9850-9861, 2018.
Shamir, O., Srebro, N., and Zhang, T. Communication- efficient distributed optimization using an approximate Newton-type method. Proceedings of the International Conference Machine Learning, 52(2):1000-10000 2014.
Wang. H., Marella, S., and Anderson, J. FedADMM: A federated primal-dual algorithm allowing partial partici- pation. Proceedings of the IEEE Conference on Decision and Control, pp. 287-294, 2022.
Wei, E. and Ozdaglar, A. Distributed alternating direction method of multipliers. Proceedings of the IEEE Confer- ence on Decision and Control, pp. 5445-5450, 2012.
Shi, Y., Zhang, Y., Zhang, P., Xiao, Y., and Niu, L. Feder- ated learning with & regularization. Puttern Recognition Letters, 172:15-21, 2023.
Wei Liu, Li Chen, and Wenyi Zhang. Decentralized feder- ated learning: Balancing communication and computing costs. IEEE Transactions on Signal and Information Processing over Networks, 8:131-143, 2021.
Shokri, R. and Shmatikov, V. ing. Proceedings of the SIGSAC Conference on Computer and Communications Security, pp. 1310-1321, 2015.
deep learn-
Singh, N., Data, D., George, J., and Diggavi, S. SPARQ- SGD: Event-triggered and compressed communication in decentralized optmiiaatinn IEEE Transactions on Automatic Control, 68(2):721-736, 2023.
Wibisono, A., Wilson, A. C., and Jordan, M. I. A variational perspective on accelerated methods in optimization. Pro- ceedings of the National Academy of Sciences, 113(47);
E7351-E7358 2016.
Solowjow, F. and Trimpe, S. Event-triggered learning, Au- tomatica, 117:109009, 2020.
Yin, D., Chen, Y., Kannan, R., and Bartlett, P. Byzantine- robust distributed learning: Towards optimal statistical rates. Proceedings of the International Conference on Machine Learning, 80:5650-5659, 2018.
Song, Y., Wang, Z., and Zuazua, E. FedADMM-InSa: An inexact and self-adaptive admm for federated learning. Neural Networks, 181:106772, 2025.
Yu, Z. and Freris, N. M. Communication tributed optimization with adaptability to system hetero- geneity. Proceedings of the IEEE Conference on Decision and Control, pp. 3321-3326, 2023.
dis-
Su, W., Boyd, S., and Candes, E. J. A differential equation for modeling Nesterov's s accelerated gradient method: Theory and insights. Jourmal of Machine Learning Re- search, 17(153):1145 2016.
Zhang. X., Hong, M., Dhople, S., Yin, W., and Liu, Y. FedPD: A federated learning framework with adaptivity to non-iid data. IEEE Transactions on Signal Processing. 69:6055 6070, 2021.
Tong, G. and Muchlebach, M. A dynamical systems perspec- tive on discrete optimization. Proceedings of Machine Learning Research, 211:1-14, 2023.
Tran Dinh, Q., Pham, N. H., Phan, D., and Nguyen, L. FrndDneandomized Douglas- Rachfos- splitting algo- rithms for nonconvex federated composite optimization. Proceedings of the International Conference Advances in Neural Information Processing Systems, 34:30326- 30338, 2021.
Zhang, Z., Yang. S., and Xu, W. Decentralized ADMM with compressed and triggedd communication. Neural Networks, 165:472 482, 2023.
Zhang, Z., Yang, S., Xu, W., and Di, K. Privacy-preserving distributed ADMM with event-triggered communication. IEEE Transactions Neural Networks and Learning Systems, 35(2):2835-284) 2024.
Umlauft, and Hirche, Feedback lincarization based on gaussian processes with event-triggered online learning. IEEE Transactions on Automatic Control, 65(10) 65(10):4154- 4169, 2019.
Zhao, Y., Li, M., Lai, L., Suda, N., Civin, D., and Chandra, V. Federated learning with non-iid data. 11xiv:1806.000 005800 2018.
Wang, G., Wang, D., Li, C., and Lei, Y. The fast inertial ADMM optimization framework for distributed machine learning. Future Generation Computer Systems, 164: 107575,
Zheng, S., Ye, T., Li, X., and Gao, M. Federated learning via consensus mechanism on heterogeneous data: A new perspective on convergence. IEEE International Con- ference on Acoustics, Speech and Signal Processing, pp. 7595-7599, 2024.
Wang, H., Sievert, S., Liu, S., Charles, Z., Papailiopoulos, D., and Wright, S. ATOMO: Communication

---

Distributed Event- Learning via ADMM
Zhou, S. and Li, G. Y. Federated learning via inexact
ADMM. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(8):999-97708 2023.
Zhu, H. and Ling, Q Broadeast: Reducing both stochas- tic and compression noise to robustify communication- efficient federated learning. arXiv:2104.06685 2021.
12

---

Distributed Event-Basee Learning via ADMM
A. Communication Structure
This section discusses the sharing problem and consensus reaching over graphs as two special cases of the more general constrained minimization problem
min x ERRP 2ER
f() + g(2),
subject to Ar + Bz C,
(4)
with variables R2 and E IR and constant matrices A E R B R and c R". The objective function is decomposed into smooth part f IRP and nonsmooth part g I R. The communication structure of the problem formulation (4) is shown in Fig. 4, where primal, dual and auxiliary variables treated different communication nodes.
uk++1
U(k]
U
S6+1
8(6]
Uk++
"[a]
8k+1
S(N]
Tk+1
Mk+1 [[A]
Figure 4: The communication structure that arises from Alg. 2. where 8 = B2, r = Ax, and u denotes the dual variable.
A.1. Sharing Problem
We will show that the event- bast- communication structure introduced in Fig, 4 simplifies considerably for the sharing problem. The sharing problem takes the following form,
N
min
Σ
(xx)) +
Σ x
and arises as a special case from (4) when choosing f(x)
Σn1
fx()), (at, ,..,..,,"N) E RN A = IND
B = -(p, Ip. Ip........ Ip). c= 0. The problem can solved via the following updates, by agents :....::::
sk+1 argmin (x')
P xx x + h4
(5)
2
x' E'E3"
and by agent N 1:
1 N
Tk+1 N
#b+1
Np
2
2# .+1 argmin g(N22)
z 0k+1
u
(6)
sERP
2
P
uk+1 = uu + p (#++1 - 2x+1)
h&+1 Tt+1 2k+1 +
uk+11
For the sharing problem, the general communication scheme in Fig. reduces to the diagram in Fig. 5, where each node communicates their local variable in an event-based manner.
Agent
Agent
Agent
Agent
21
27
2Tx
hutt
Agent 5
Figure 5: The diagram visualizes the communication structure for the sharing problem for N 4 agents.
13

---

Distributed Event-Basse Learning via ADMM
Agent
Agent
[fA]
*
4[4]
Agent
Agent
Figure 6: The diagram visualizes the communication structure for a distributed learning problem over a graph that connects four agents with four edges.
A.2. Consensus over a Graph
As another example, we will show that (4) also generalizes to distributed learning scenarios over graphs. We consider network topology, captured by an undirected connected graph G = (V. E). where V {l...., , .N) is the set of vertices and V x V is the set of edges. Each agent (vertex) has local data distribution, and the aim is to train model without central server to aggregate the collected information. The problem can be formulated as follows:
min 20 ERP
p (at),
=0= subject =²==20 x0=2, =2 v(i.5) E
Similar to the formulation in (Yu & Freris, 2023), we define transmitter and receiver matrices A,, A, E BlEIxN for all edges, i.e.,
-(0
A - |1 [A,]
(1.5)&& Ve E.
otherwise
By stacking x², ,²,2 E TR into column vectors x E TR, E RI respectively, we conclude that distributed learning over graphs is indeed a special case of (4),
Ag X 1p A, & 1p
Lelp T/p
min MERMP SERIEIP
f(x),
subject to
r
where denotes the Kronecker product and I, the identity matrix. Thus, the matrices A and B encode the topology of the communication graph, which will affect the convergence rates as highlighted with our main result Thm. 4.1 where the convergence rate is dictated by the value x = (a) (A))))
The resulting instance of Alg. takes the following form:
Wele
1
1 2 #/) +
11 argmin (x:) +
x²
(2
p
ZERRY
2
z
*+1
WI
E+1
(7)
JEN,
p p + P
- x
where Ns represents the set containing the neighbors of the agent and [M] is the number of vertices. In the event cossuucommunicitoon setting, an agent transmits its local model (xf+z) to the neighbors only if there has been significant change the local model. Fig. 6 shows an example with four agents, each communicating local variables only.
14

---

Distributed Event-Based Learning via ADMM
B. Proof of Thm. 2.3
Proof. We will establish the convergence rate by analyzing the behavior a carefully chosen Lyapunov function. Let us begin by formulating the augmented Lagrangian for (1):
Lp(x, 2, Σ ((x)) + g())
Ev' =)
Σ
(8)
where x xx',...,,")) and y = (y' ./. represent the primal and dual variables respectively, and p > the )
penalty parameter.
We express the ADMM updates in Alg. 1 for 1 as follows by introducing the scaled dual variable u' y
+ = arg min (((x') + P Jrr - 2x + =uk/3)
Vi (1)..,,,),
(9)
No
2++1 arg min g(z)+
#k+1 2 + 0//1
(10)
2
u = u + x|+1 2k+1,
Vi E [1....,N).
(11)
Here, the notation Ex+1 2++1 + + emerging from event-based communication. From (9) and (10), we derive the following first-order optimality conditions for x and 2641
2k+1 2/41 +
n. 6441 and 6641 u + E411 to account for errors
un
0 = ( + p(1)+1
2x + uzk)
(12)
N
0 (gg(z 2 1) >
(#k+1 =b/-1 ut..)
(13)
We then define the Lyapunov function:
N
V22 = 12k 2x
+
1u
(14)
N
where (ut, 2.) denotes the optimal dual and consensus variables. Our goal is to demonstrate that this Lyapunov function is monotonically decreasing.
The optimality condition in (12) implies that #1+1 minimizes,
(x) + p (uf + z6+1 - 2x) x ple - =G)
From this minimization, we can derive the following inequality.
ff S (w + 24+1 24) (x), (x4-2141) + p(= T -
(2)
(15)
Similarly, the optimality condition (13) indicates that 24+1 minimizes.
N
g (x)
det (ut+1 + Ekt1 =k41)
(16)
where x+1 Ebt1 + c ui
d. 2.
This minimization leads to,
g (#++1) - g (zx) < Σ (4(+)) [2x+1 - =zx) - Σ
di
(EM+1 zz).
(17)
k+i
15

---

Distributed Event-Based Learning via ADMM
By adding (17) and the sum of (15), and applying the conditions st == along with the relation 2f x
-rkt1 (2k+1 2.). obtain,
N
N
((#++1)-g(24)
--P))
(ukt2)
Tktt P 2 2h-41 - zx) (ri+1 + (2++1 2+))
(18)
N
N
+p
[1 - =tt (xt 2 2 + + kt1 + Ex+1) (2x+1
where the residual is defined as r == 2 - 2k-
Since (af, R, v is a saddle point of Co in (8), i..., Co( S Co(xx+1, Zk41, Un), we have,
(((++1 + 9(2.)
E -
Σ
u (5 =k+11 Σ u, Th+l
(19)
By adding (18) and (19) and multiplying by 2. we arrive at
N
N
0 2
(u - utt) T
réti + 2 Σ
(zx+1 - 2x) T (ré+1 + (Ex+1 - 2x))
(1)
(20)
N
Nv
2
(= - Txt - - Σ
k+l
di
T 2x)-
2=1
i=1
Here (uk+1 - v²) rhtz can be written as (uk+1 - ui) T
(uk41 - w/ + + which splits into
(uk+1 - wt)) T rkt1 (uk-1 uk)) Eb41 + 2 |1/ ut 12 2 (uk+1 - -ube (uk+1 up Ek422
1
+ (uk ut) T (ub+r m() + (uk. - ut) cbt1 lut - 22
Next, we substitute # u/. 1 +i+ and use the following squared norm identity,
Jutt1 - u/f 12 + (ut - wi)) (Mi+1 - wi)) = 2 j - 21, + 2 ju - u2,
Consequently, can expand terms (I) and (II) as follows:
N Σ
(1) (1u441 - 2 l14 - ui12 + 2(1 - T + +15h=112 1 -2(ett)))
111
(II) Σ (Irke + (#x+1 2x) 2 |26+1 2 122 2u 12 1r)++1?).
Substituting these expansions back into (20) and using the definition of our Lyapunov function from (14), we can express the decrease in the Lyapunov function as.
0 NVV++ V42 +
Σ (2(1k41 1=1
TT) + 1 - (T(k1)
2((2_1)
N
N
(1241 (zx+1 xx) 12) + >
(o =t) (xxk+1 xtt) 2 Σ
di k+1 +
(844))(2k))) 2x).
i=1
16

---

Distributed Event-Basce Learning via ADMM
Modifying the error terms using #*+1 2t -rkt1 + (#x+1 z.) and rk+1 u2t1 ur + + get,
N
N
N(V++1- 12) vA) S
Irlt1 + (#A+1 - 2x) 12 12 Σ (- 2(E - -E ((/x+1 =.,) - -1 Σ
(21)
1=1
+2(E041 + Ett
(#k+1 2.) -((Et) (ut u!) -2(=)) T E
Furthermore, we expand the squared norm term:
N
N >
Σ Irln + (2N+1 2x) 12) Σ M -2 > (r)++)) (2k+1 2kk)
2k++ 2x12.
(22)
N (r k+11)² Next will establish bound for the cross term -2 -i
(2k+1 - =x))
We recall that (13) implies (16). This minimization property leads to the following pair of inequalities:
g - - S
di ( + ek+1 + ox41) (20+1 zx))
1=1
g ( - 9 (*K+1) S p Σ
[uu (ut + dit + sk) (Zu+1 -zn).
By adding these inequalities and rearranging terms, we obtain,
(1i+1 u +
d. Ex+1
Ck d.s + + - =t) (#k+1 2k) Σ (rh+1
Ek+1 6x
di dit -xx)
T 2k)-
This yields the desired bound on the cross term -2 -2 (r2+1) (zk+1 21,) which takes the form
N
N
Σ
(riz1) (2k+1 - zτ) 52
di (et1 - Ex - -x).-
(23)
i=1
As the next step, we rewrite | zul in terms of the gradients of Ie and g. This will be important for deriving the desired convergence result. From the first-order optimality condition of the z-update (13), and rearranging for 2g+11 we get,
N N
1k++
E
s + us + +xx+1) ON 0g(zz+1).
(24)
The optimality condition for 2i+1 (see (12)) results in,
N
- x u (
- 2k
(25)
We combine (24) and (25) express the update for 24+11 24 as follows,
N
1 PN
Σ ( + 0g(2x+1) + o
di
2 - 24 E
Thus, 2k+1 21 depends on the averaged gradients f and 0g. scaled by the penalty parameter p. We now take the square and apply Young's inequality on the cross term with ? = 2, which yields,
ll (m141) +M++1/ )
2
-|=++1
=x1
1
+
di
(26)
pN
N
k+1
17

---

Distributed Event-Based Learning via ADMM
for any pk+1 E 0g((==1)).
By substituting (22), (23), and (26) in (21), and applying Young's inequality to cross terms, we derive the following inequality:
N(V++1
Vo)
Σ
N
M441
12
1
N
v (# + va+t1)
)
2
+
Ex
d, 1++1
2
p.
N
1=1
f=1
Tale
ExI
1
rktt k+1 2 + n1 2
1
11te
u²1 2
|ež+1
+ 72
102 d.i
k+1
Ex
74
71
+
12k+1
2%
2
+
k+1
di
+
+
+
12x 201² + +( -2E (
7/2
733
for any v&+1 E 0g(2x-1).
We can further simplify the expression by choosing the values as 71 = 7h and 7/2 = 7 = 3,
N
N
v ( + Mx++1 )
|2 + E
N
NV+++ Vkx)=
7k
V/=
2
3 1=1
r 1+11
6
PN
N
k+1
di
1=1
N
Σ
(31 = + * 12
| + 3/22
=x
7x d.
+ 2
4|
2e
for any Pk+1 E 0g(=x-1)
The error values arising from event-hased communication are bounded by the communication thresholds, 1, s A. | < Aj. This leads to the following inequality.
N
N
v V (2(+2) + (At1) + )
2
Vi+1 S [
7k
Vx
3NV
2
k+1
6.V
PN
+ (3
+ 51 +
> + (2%% + 30
8
d²
3N
3N
for any Mk+1 E +g(2z++)) where rh41 we obtain:
x/41
Øb41 represents the residuals at step A + 1. Simplifying the expression,
N
)
2
Va+1 S (+
1 mk
Vv
2
2k41
1
1
vf + +8+1 Σ
+ 0 AQ),
(27)
3N
6.V
PN
for any Mk+1 E 0g(Zk+1), where A represents the time-varying communication threshold, i.e., chosen bound for the perturbation term. This inequality suggests relationship between V and V4+1 at consecutive steps.
To analyze the convergence of the sequence Vs, we apply Polyak's Lemma (Lemma 2 in (Polyak, 1987, Chapter 2.2)). which establishes convergence under certain additional assumptions. Polyak's Lemma states that if a sequence Ve satisfies an inequality of the form.
(1+
1 Vs 7k
Vk+1
ci + c
where of and of are sequences of non-negative terms, then the sequence V₁ is bounded above provided that D 1 Te < 0o,
and Σt= of cc.
18

---

Distributed Event-Based Learning via ADMM
We choose 7 (k: 1)2 for some p obtain:
ensure convergence. Substituting this choice into the recurrence relation,
V + (a-1)) ))² +0 -
2
Vi+1 S 1+ + 1)p
Vi
3N
p+t1 2x+1
PN
for any Pa+1 E 0g(=x-1).
By assumption the communication threshold As decays as As (1/k)). Under this assumption, the perturbation term O(k? A scales as O(p--21 A which satisfies Σk in Ag oo if 1 and <> 1+2 These conditions ensure that the perturbation term decays sufficiently fast, ensuring boundedness of Vi.
Finally, by summing over = to K and dividing by K + 1, we obtain the following bound for the average of the residuals and gradient terms:
N
[ + + )r) S 0
2
6NV P.V Σ
2k-1
(28)
K ++11
3N
for any PA+1 E 0g(2++1), where communication threshold decays As < convergence rate for both the residuals and the gradient terms. The rate of decay of the communication threshold ensures that these error terms decrease at a rate proportional to O (x)) which yields the desired result.
[++1) This result establishes sublinear
19

---

Distributed Event-Based Learning via ADMM
C. Derivation of Alg. 2 as Dynamical System
In this section, we represent Alg. as a dynamical system that consists linear dynamics with nonlinear feedback interconnection. The communication structure is summarized with Fig. 2.
For the convenience of the reader, we start by restating Alg. 2, which is based over-relaxed ADMM algorithm.
Algorithm 3 Event- Based Distributed Optimization with Over- Relaxed ADMM
Require: Functions f and g. matrices A and B, vector c, parameters p and
Require: Initial condition Jo: 20 To P6 f Aro. $o 5/ =
B2g
Ug 0
uij
for k to <max do
S.. 0% + event- event-based receive of sk+1 s()) uk+1 [[k]
1 = arg min, f() + [ Az + % - c + 0g 1
(r-agent)
event-based send of rk+1 [[k] where rk+1 = Ar&+1
1 0g event-based receive of rk+1 - []k]: Ux+1 U[k]
2k+1 arg min; g(2) 2 offf11 - B Bz 0g]
{s-agent)
event-based send of 8 8/l where 8 B
k 8 k+1 - event-based receive of M T[H) Sk+1 - 8(M] #k+1 = ú2 + af (1 a3 + k++ ac
[u-agent]
event-based send of uk+1 M[A]
if mod (k 1, then
reset .u18
P:S
k+1 Tk+1; k+1 = 8k+1, #k+1
= ug+1
end if end for
The following definitions will be useful for simplifying the updates of the iterates: Definition C.1. Let Assumption 3.1 and 3.2 hold. We define the function f R -> TR as follows,
f (p A-1
(29)
where p is the step-size of Alg. 2. The function is m = m/ (mn -st)ongyy convex and & = L/(oo and has therefore the condition number
I. (AA)
m gA
Definition C.2. Let Assumption 3.1 and 3.2 hold. The function 9 ; m + R is defined as
g (p g) B vim(B):
(30)
where B is the Moore-Penrose inverse of B, (B) B) is the indicator function of the image of B, and p is the step-size of Alg. 2.
We proceed by summarizing the notation that will be used subsequently. The sequences r and 8 are defined as F == =Ar and #; = Bzg. We introduced the variable fg. for example, which models agent s's estimate of the variable rk. The variables fg, S7. sy. etc., are defined analogously and follow the notational convention
noceiving_aeent
variable,
:= receiving agent's estimate of variable at time k.
As result of the event-based communication, the local estimates Pg, f &6. etc., differ from rı, 8ks etc. These differences will be captured by the variable for which we introduce the following notational convention:
wuriable, agent
variable,
receiving agent
variables
saciiving_agentt estimation error of variable time k.
20

---

Distributed Event-Basee Learning via ADMM
We further introduce the error
C/: = (6b411 su Sr &h .kk 5 :8k
(31)
that collects the estimation errors the different agents. By virtue of the event-based communication mechanism and the reset mechanism, the error Eg bounded by the communication threshold A. We finally introduce the notation for the corresponding communication thresholds, A A etc. (see Fig. 2), according the same rationale:
A yariable,.oclvingggggn.t threshold for triggering a communication of variable receiving agent.
To sum up, the vector eμ contains errors on the communication lines shown on Fig. 2. For example, 6 stands for the difference between the actual value of state rk+1 and agent s's estimate f that is, Ek41 f Tk+1 at time step
k +
If the value r has deviated more than A amount since the time-step [k:], where the last value ['4]] has been communicated to the agent a communication is triggered. This means rs E Ck+1-
|
mi
rs Ck+1
=++
The set Da+1, which is subset of C collects indices of failed transmission lines time step k: + 1. We further introduce that the superscript to denote the complement of set. If the communication does not fail, that is, rs E D then agent s's estimate of rk+1 is updated as follows.
Ck+1 ATS E Di+1 + Pit1 (rx+1 T(k)).
To incorporate the effect of communication drops, introduce the variable X6+1 which represents the disturbance that results from dropped communications,
rs D Xk+1 - -rr++1 m(A)). Therefore, the dynamics of +4 are expressed follows
(32)
k+1
Ak = [[++1]
xI"
(33)
[=1
When deriving the previous equation, we have exploited the fact that
r8 Ca+1 = [k 1] = k
rS E Ck+1 = [k 1] [k].
To summarize, in the case of communication drop, the agent updates the image of with disturbed value.
We now express the different minimization steps in Alg. by their corresponding stationarity conditions, and simplify the corresponding expressions. The minimization step for the primal variable æ can be rewritten as follows
Tk++ = arg min ZERP
(xx) + 2
Ar + 5% - c at
= A arg min f(A + 2 |r 8% c 0,1
2
FER
due to the fact that A is invertible, which yields
Tk+1 = arg min re
f(r) + |r + 3t. - c utp
The variable r441 satisfies therefore the following stationarity condition
v((rk=1)) +
8% c c 0/
21

---

Distributed Event-Basce Learning via ADMM
which can be rearranged to
Mk+1 - c= -V 8/ -x uk Ek
(34)
where &6 is replaced by 8& + of and on by uk + =
Similarly, the update step of the auxiliary variable can be reformulated as
2k+1 arg min ((2) I glar ++1 a)ssk + BB ac üig
=E
Bt arg min SER
g 8) + Vim(B) (s) + & affk+11 - - (1 - assk + s - ac + 2g/
2
since the matrix B has full column rank and therefore possesses the left inverse Bt, This yields
8k+1 = arg min ((s) +
2 J - (1 0.)sk + ac + agl
.ER
and implies the following stationarity condition for 8
0 E 0g(5++1) + aff (1 - asss + 8k+1 ac + üß.
(35)
This stationarity condition can be reformulated as
8 = 8% + (a - 1)ux + aV f(rk+))) - 7k+1 =% + aas + aee ae
(36)
for some MM++1 E (g(+++1), ). and where we have expressed 1 as rk+1 + + and úg as uy + =g. We have further replaced rk+1 e by the expression given in (34).
The update of the dual variables uy evolve according the following dynamics:
Uk+1 Uk + aff a1-a) )a $ ac
uk + a = - (sk =f") + (sk41 + ac
The dynamics can be further simplitied by replacing sk+1 with the help of (35), which yields:
Uk+1 -*++1 aci + ae + + (a- 1)= - 2
(37)
As a result of these simplifications, we note that r is uniquely determined by sg. ug and the corresponding errors eg and eur. We further note that according to (36) and (37) the iterates of Alg. 3 can be represented as an intervonnection between a linear dynamical system, with a nonlinear feedback interconnection that models the evaluation of the gradient V f and Øg. The state of the dynamical system therefore chosen as &N := (#R, ux), the output as y/ == (rk+1 - C, 86+11 ), and the input as U2= == (V (r((r))), (1++), where 7 E () We also define output variables w| := (rk-1 c, frr++1)) - = (sk+1. 7k+1), which will be employed for the convergence analysis.
According to these definitions, we can express the iterates of Alg. 3 as trajectories of the following nonlinear dynamical system,
1
0 0
Ex+1
0
0
Ek
+
0
0k
a
0
a
0
-1
Uk
o(yx),
(38)
-1
1
0
- 0
Uk
EN
Uk +
Cx:
1
1
0
-1
Fx
0
0
fA
1
0
Uk
0
0
6k>
D
E
(39)
1
a
a
0
0
1
Uk
Ek
:=D>
B2
22

---

Distributed Event-Basce Learning via ADMM
Delay
8k+1
Sk
u0+1
A
E
B
C
Ey
D
Tk+1 8k+1
f((441)
Y9+1
Figure 7: The dynamical system following (38) is visualized.
where é denotes the nonlinear feedback interconnection that captures the evaluation of the gradients V and dg. Fig. 7 provides a graphical representation of the time-invariant dynamics determined by the matrices A, B, C, D.
We close the section with the following proposition that shows that |ex| is bounded.
Proposition C.3. The error ej at iteration k is bounded by
lex
A,
E
A + TX'
where the variable x is an upper bound on the communication drops.
Proof. The proof is analogous to Prop. 2.1. The error resulting from the event-based communication structure is given by
k+1
c+1
k++1 Th++1 [[++1]
Tk+11
(40)
We further note that the first term is bounded by r by virtue of the communication rule
Fk+1 - T[++1] S ~
Through the assumption Ix[ I X" the second part bounded by TX"*, where T is the reset period. Therefore, we conclude that lettn is bounded by A + +Tx"s, Similarly, the other elements of the vector ex bounded by A Txx"
A sM Tx etc. Hence, lex| is bounded by A where
A
Σ
TX!
The analysis indicates that periodic reset with a period is required to achieve a bounded error. If no reset is included, Alg. 2 may not converge, which could result in large error that accumulates over time. The dependence of A on the period T' highlights how the reset period T' affects the error (where smaller leads smaller error bound). If there no communication failures, there is also need for reset (x 0), and A reduces to the collection of communication thresholds.
23

---

Distributed Event-Basce Learning via ADMM
D. Convergence Analysis
We first start by proving the following intermediate lemmas.
Lemma D.1. Let Assumption 3.2 be satisfied. Then, the following holds,
((1-12) -
(I I.) -2 8xn)) ( - vf(12) 2 0,
(I
-2in (m + L)]
) ((((m)))((()))))
11 11-12 72
(41)
for all r1.72 R..
Proof. We define the auxiliary function f(r) f(r) -/2 rr| which is L m-smoooh and convex by the properties of f.
Then the following inequality holds,
Vf(r)) (mi - r2) 2 L - m
-
for any r1, 12 E Substituting f(r) = f(r) - ii |r| and vf(r)= = vf(r) -nr, we get
(m ()(1- ( (Vf(r)) vf(r2)) 2 mb/r r21 [v((r)) 2
which yields the desired result.
Lemma D.2. Let Assumption 3.2 be satisfied. Then, the following holds,
[(0] [ 82) (7) - 7] (L
81
82 72
20
m
2 0.
(42)
0
7/1
where n E (g( and 12 0g(s2) and for any $1, $2 R".
Proof. The subdifferential of convex function is monotone operator, and therefore
(81 82) Tm - -2)) 2 0.
Lemma D.3. Let I., 2. denote the minimizer of (3) and define r. == Aw. 80 = Bz., B. = v((r.), and 7. E 0g(s.).
Then, the iterates of Alg. 3 with step-size (o((i)) satisfy
(ut w M - w 2 20, ViE (1,2), vk 20
with
-2p5
Pū (
0
M
Las
M
x Ams
Po -1 (N m²t)
2
0
where
wh =
Tk+1 - C Bx+1
wo =
8k+1 7k+1
w! =
r. c
w =
8.
3,
%
Proof. The proof follows directly from Lemma D.I and Lemma D.2.
Lemma D.4. Let the sequence Vv 2 satisfy
Ve+1 5 Vx(1 ā) + Aā
(43)
for all l 2 0, where the parameters o, 3 satisfy
< à < and 0 < B. Then, the following holds for all k 2 0:
V S Vo a²* + 3.
(44)
24

---

Distributed Event-Based Learning via ADMM
Proof. We prove the lemma by induction.
The claim holds for k = O. We therefore assume that the claim holds for & and show that, result, the claim holds for k + 1. More precisely,
Vi+1 S Vi(1 a) + Aā
S Vo(1 -6)+t1 + (1 ق)B + Ba
(45)
< Vo(1 a)k+2 + 3,
which completes the induction argument.
In App. C, expressed the iterates of Alg. as the trajectories of a dynamical system. The dynamical system was given as a linear time-invariant system that was interconnected in feedback with a nonlinear function Φ. We now arrive at the main result that will be used to show convergence Alg. 3.
Theorem D.5. Let Assumption 3.2 be satisfied, let the step-size for Alg. 3 be p po(mnL)),, and let (Bz,, u.), where (I., 2.) is the minimizer of (3) and u. the corresponding dual variable.
Suppose there exists positive definite matrix P > O, < < 1, and nonnegative constants X X3, 7², 72, 7 and yp such that the following linear matrix inequality
(L+ ATP BTPÅ
(c D'1 C Da
T
A 0 0 A
Ō D
02
(1+7)) PB]
+
C D2
(46)
satisfied, where Al = 21 + 7 )) A2 = 22 ) Then, for all 2 0, we have
aQ)A2²
1s Ex12 S krlEo -
(47)
(P)
where Kp (PP) denotes the condition number of the matrix P. A a bound on the ervor ex (see Prop. C.3), and
Q 1 + 7 ET PT
(1+
+
2
E M
(48)
73
Proof. We consider the following quadratic storage function,
V₁ (Ex - (.) P(EE - E.),
and claim that the following inequality holds for the iterates of Alg, 3:
Vi+1 72V2
Σ Xt Xto T 'M(""" -wt)
1=1
((1
E PE
Σ X'
E +
1
+
1
ETME)
25

---

Distributed Event-Based Learning via ADMM
Proof of the claim: We insert the system dynamics stated in App. C into the expression on the left-hand side, which yields
2
VK+1- - V +
X (wfj w M - ww²)
1=1
2
-(6+11 - P(xx+1 - {.) - -Ex - _.)² P(Ex- - Ex, +
x Xww - -wa) T - -w()
-G. PA Ex + 0% BJ PBūx + C/ F. PEEK
-
(49)
+ B. + o T PÂE. + +ūg B SPEE))
2
MCC. + 8y DiT M D' + e E M'
+
(IT +e E MCC + +o DiT M
2
X²
==1
where & = Ex - E., and Uk Uk- u.. for simplicity. We now apply Young's inequality on the cross terms in (49), which yields
---1-2V- + Σ Al(n w()) Mw - w!))
556 (A PA P2P) E. + B B PBO + E PEex + 20g B PÂG
+ + BT PBūB) + マ ETTETT E PEES) + +
+ + E PEEN)
(50)
THT M D' + +ej E M M' + 2 (o (.E:)) x OH MOT + D
2
ΣΣ X (ATDDTD'' + 7 E. E' + T M + 1 o
E. M (OTTE)
+
If we rearrange the right-hand side of the inequality in matrix form, we obtain,
2
Vx+1 - - Σ
x (un - w()
-N w() S
([
(AT 72P
ATP
5T
T
PTP
(1+73) PD
(51)
Ca D4T C² D2
(1 +73)
[ Er C² D2
D1
)
E ūkk Ck-
+
0
X + 70)
1 (1+
1
1
+ ee
E
PE
PE
+ Σ x 1=1
(1+ 73
+ 73
E E M'F
The fact that the linear matrix inequality (46) is satisfied proves the claim. Furthermore, we conclude that Ei w M ('(w). w > 0 from Lemma D.I and D.2. This simplifies the previous expression to
Va+1 S V + Qek:
where we have also inserted the definition of the matrix Q. The right-hand side can further be bounded by virtue of the reset mechanism and the event-based communication, which results in
VK+1 S 72V2 + (Q)A
(52)
26

---

Distributed Event-Based Learning via ADMM
We now in position where apply Lemma D.4, which concludes
=(Q)
V S 2k Vo
1 1-
By definition of the quadratic storage function we conclude
L5x - 5.12 2 72 (P)
aQ))4²
150
2
((P)
(1
which implies the result of Thm. D.5.
We are now ready prove our main result in Thm. 4.1.
Proof of Thm. 4. The proof is based on Thm. D.5 which shows that if the matrix inequality
0 (A+A')APPAPP P2P
PB
C
D
A'M'
0 A
][
D D
BT PÀ
(L+ PB
+
D2
(53)
satisfied for a symmetric positive definite matrix P and for positive constants A A ,1, 7, the following bound holds
aQ))A² c(P) - 72)
E E.12 S kplEo - 2.12,26
where Kp denotes the condition number P and Q is defined in App. D. fact, the following set of parameters satisfies the linear matrix inequality (53),
P
==1
4xttg² A - A =²=a, a, 7²= xet n
7²=1
a 1
VK
This be checked as follows: The matrix the right-hand side of (53) can be expressed - - IL, where L is symmetric x 4 matrix (compared to earlier analyses (Nishihara et al., 2015), the last row and last column is not zero). We now prove that L is positive semidefinite for all sufficiently large x by checking the leading principle minors, which can be expressed as polynomials in k. If the leading terms of the principle minors have positive coefficients, it means that for large enough K, the principle minor will indeed be positive.
The leading term for the first principle minor is given by 6x and is therefore positive. Likewise, the second principle minor dominated by the positive term 24(2 - 2)x²- For the third leading principle minor, there are two different cases. If 0, the leading term of the third leading principle minor is 16x 4 - 4a² + 22a 12)/a, which is positive for E (0.675, 2). If e >> 0, the leading term of the third principle minor becomes 192x5 S a),, which is positive for E (0, 2). Finally, for the fourth principle minor, there are also two different cases. If 0, the leading term is 64x 2 (a+ 4 4a² 22a 12)/a², which is positive for (0.675, 2). If 0, the leading term of the fourth principal minor becomes 768k (2 aa/a, which is positive for (0,2). 2). In conclusion, for all sufficiently large K, all four leading principle minors are positive, which implies that L is positive definite.
It remains to bound the second term / (Q) - -2)). We again investigate the symbolic expression, and conclude 60x2+2e that the term is always bounded by 60x 2+2c 2+<22 - la 11)) for large enough k. This concludes the proof.
27

---

Distributed Event-Based Learning via ADMM
E. Bound on Event-Based Error Variables
We restate Prop. 2.1 and present its proof.
Proposition. The error Eo- - Sk at iteration is bounded by Alg. 1) and X is bound on the disturbance Xk
where T denotes the reset period (see
Proof. We note that the error Č Ca can be expressed as
&A Sk
(K+
d +
di X1+1
N
1=TM
where Ti denotes the last time instant where reset has been performed. The terms I and II have each clear interpretation: In the absence of communication failures, is an average over the primal and dual variables, 2 of++1] and ufa) that were last communicated, which leads to the term T. The term IT captures the dropped information through failures. The communication protocol ensures that | [1j|| Ad, 4 for all 1: 2 which means that the term is bounded by A The bound for the term II arises from the triangle inequality, which yields, x" and concludes the proof.
The previous proposition required the variable Xk+1 be bounded. Prop. E.1 establishes such bound under standard conditions on f and g-
Proposition E.1. Let be L-smooth and convex and let {z E R" 19(2) < oo} be contained in ball of radius R. Then, the disturbances Xk
di and Xk are bounded by
Ixt'l < 2R, 1x41 S (a 1) 2(p + L)
| + 2R,
P
for all i=1,..., N and all k2 O, where ai == arg min f((x) + pl///// and where xi denotes the communication drops when communicating 2n. between agent + and agent
Proof. Due to the assumption that the domain is contained in ball of radius R, we conclude |ax| < R for all Z 0. This also implies that | S R and concludes the bound on X². For obtaining the remaining two bounds, we analyze the x', ue dynamics of agent i, where we introduce the convex conjugate
(w, 2) sup u' x ('(x) - G/u
- ---- =1
xER"
We note that the supremum is attained for o if u -utt and = in the previous equation. In addition, due the properties of the convex conjugate, we conclude that f', 2) is 1/p-smooth and 1/(p + L)-strongly convex. The conjugate subgradient theorem implies,
V v. 2t) = zf
which means that the updates for uj can now be expressed as:
wht1 use + (- 2 2t.
By applying Taylor's theorem, we obtain
" = uf (v (v) (-px)) - 2 + V.F
for some U/ E R.. By leveraging the fact that, as a result of strong convexity and smoothness of (1,,)), the Hessian (2,)() is upper and lower bounded by 1/p and 1p(p + I),, respectively, we conclude
|uttzl s (I-0f) - 1
|u | + V. V. 2
(54)
28

---

Distributed Event-Based Learning via ADMM
By similar argument based Taylor's s theorem, can bound the last term in the previous equation by
L
E - V. (0, 20 |x +
[k
p L
Unrolling the recursion in (54) and exploiting the fact that un 0 yields
ku - P +
|x + sup
A20
where the last term bounded by R. Finally, due to the 1/p-smoothness of ('),),, we conclude | S yields the desired result as follows,
/ufl,
which
(P+L)
xx |ark+1 + uil S al + juil S (a + 1))uuk (a+1)
x + sup
[
P
k20
(pt |oo|| R
s (a+
p
29

---

Distributed Event-Based Learning via ADMM
F. Diminishing Communication Threshold
In the main text, we focused our presentation on fixed communication thresholds. However, it is important to note that our approach and our analysis can be easily extended to the case where communication thresholds A are varied as a function of the number of iterations. For example, it is straightforward show that for any vanishing sequence As. our iterates indeed converge to the minimizer of (3).
Corollary F.1. Let the assumptions of Thm. D.5 be satisfied and let As 0 be such that Ae - Ofror k 00. Then limg Exx Ex + O.
Proof. According to Thm. D.5, the following holds,
Va+1 S Vo + 7
see (52). We now apply Lemma 3 in Sec. 2.2 in (Polyak, 1987), which yields the desired result.
We can also derive explicit convergence rate. In fact, the following corollary proves that if A is the form q/(k: + 1)", where q 0 and >> 0 are constants and k is the iteration number, 1&x E. converges a rate of O(1kk)).
Corollary E2. Let the assumptions of Thm. D.5 be satisfied and let A I1+ Ak 2 t 0. Then, the following holds for all k 200
ko + Ko
16x - E.l2 S g(P)
Co.
2 { 1-7² (P))60 - S.12].
where Ko-
and = max
2
Proof. According (52), the following holds,
Vk+1 S +v())
(k 1)
We make the following claim:
ko
VA S
co
Wk 2 0.
k + Kn
We prove the claim by induction. The claim holds for k = 0 due to the fact that co 2 (P)) - 1 We therefore assume that the claim holds for k and show that this implies that the claim holds for & + This yields
V S V222 + +Q(
(kc + 1)a
ko
72c0
+ō(
k k Ku
(k: + 1)²
kn
h: + ko + 1
x(Q)4
k + ko +
))
72
co
b: Ko +1
+ kio
cokó
k k+1
kp
Ko + 1
a(Q)q
ko +o+11"
Co
72
+
k ko
ko
Co
ko
lin
$ 6p
1: + Ko +
7
and completes the induction argument.
30

---

Distributed Event-Basce Learning via ADMM
G. Additional Experiments and Hyperparameters
We ran various experiments order to assess the performance of the event-based distributed learning algorithm (Alg. 1). In the comparative studies, we choose FedAvg (MeMahan et al., 2017), FedProx (Li et al., 2020a), SCAFFOLD (Karimireddy et al., 2020) and FedADMM (Zhou & Li, 2023) as baselines, since these methods have been developed to address challenges such data heterogeneity and communication efficiency. For fair comparison in terms of computation resources in all setups, each of the agents are run for the same number of local gradient steps.
We include the first example in Sec. 5, which showcases how two image classifiers (for MNIST and CIFAR-10 datasets) can be trained in a distributed and communication efficient way. Our setup included N = 10 agents for MNIST, each storing data for a single digit, resulting in the most extreme non-i.i.d. distribution of data among agents. For a CIFAR-10 classifier, the data are distributed among N = 100 agents according to a Dirichlet distribution, i.e., we sample Pa ~ Dir.N where N is the number of agents and [ =3 0.5. We then assign Pa.j proportion of the training data of class a to agent j.
We applied our implementation to train fully connected neural network on the MNIST dataset and convolutional network on the CIFAR- 10 dataset. The classifier model has 4 convolutional layers, each with 3 x 3 kernels and 32, 64, 128, and 256 filters, respectively, followed by three fully connected layers with ReLU activation functions. After each set of convolutions, a 2 2 max pooling layer is applied, followed by a ReLU activation. We train the MNIST classifier model using Alg. 1, where we replace the full minimization step of each local objective with five steps of stochastic gradient descent with a learning rate of 4 = 10-1, 1 and the CIFAR-10 10 model with epochs of stochastic gradient descent (batch size 20, learning rate 4 = 10 10. Further hyperparameters are listed in Tabs. and 4.
Tab. 1 in Sec. 5 summarizes the main result of this paper, by comparing the performance of different methods. From this table, it is clear that Alg. 1 achieves the same test accuracy with less communication cost. The communication configurations for Tab. 1 are summarized in Tab. 2.
Fig. illustrates the trade-off between accuracy and communication load. The results demonstrate that our event-based approach consistently achieves higher accuracy with fewer communication events compared to baselines. Each point in Fig. 8 represents a different value of A, where A monotonically increases along the curve, demonstrating that with our algorithm and well-chosen A threshold, communication among agents can be reduced while still achieving a high classification accuracy. Our experimental results indicate that the approach can reduce communication costs by over 30% without significant accuracy degradation. Notably, SCAFFOLD doubles the communication cost due to its dual oual-package communication protocol. These findings directly translate to the results in Tab. 1 showing total communication events for target accuracies. The extensive experimentation across both small-scale (MNIST) and large-scale (CIFAR-10) scenarios demonstrates the scalability and effectiveness of our event-based communication strategy, particularly for large-scale distributed learning problems.
The next sections provide additional numerical experiments. We first show an example based on LASSO where the local objectives are strongly convex (Sec. G.1 and G.2). In this setup, our theoretical results apply. Sec. G.3 shows how our algorithm can train an MNIST classifier, when only local communications are allowed, as specified by a given communication graph. In such a setup, the baselines FedAvg, FedProx, SCAFFOLD and FedADMM are not applicable.
MNIST Target Accuracy
CIFAR-10 Target Accuracy
Algorithm
80%
85%
90 %
70%
75%
77%
78%
Alg. 1-randomized (Perig, Ad)
(0.1.5)
(0.1, 4)
(0.1, 1)
(0.2, 4.5)
(0.1,
(0.2,
(0.7,3.75)
Alg. 1-Vanilla (Ad)
(3)
(2)
(1)
(4.25)
(3.25)
(3.25)
(1.75)
FedADMM (part_rate)
0.4
0.6
1.0
0.4
0.5
0.7
0.9
FedAvg (part.rate)
0.4
1.0
0.1
FedProx (part.rate)
0.5
1.0
0.2
SCAFFOLD (part_rate x 2)
0.4 x 2 0.5 x 2
0.8 x
0.2 x 2
Table 2: Communication configurations across algorithms. Values represent the probability of communication for baseline methods. SCAFFOLD values are doubled due to double package transmission per round.
31

---

Distributed Event-Basce Learning via ADMM
MNIST
CIFAR-I0
Total Comm. Load (%)
Total Comm. Load (%)
Alg. 1- I-Vanilla
80
80
Alg. 1-Rand
FedADMM
60
60
FedProx
40
40
FedAvg
SCAFFOLD
20
20
70
80
90
65
70
75
80
Classification Accuracy (%)
Classification Accuracy (%)
Figure 8: The figure compares different federated learning methods the MNIST and CIFAR-10 datasets with respect to the resulting trade-off between total communication load and classification accuracy on the test set. In the MNIST case (left), randomization includes agent-to-serve communication with 0.1 probability. For CIFAR-10 (right), randomization incorporates server-to-agent communication with 0.2 probability. Points along each curve represent different thresholds, demonstrating the relationship between communication reduction and model accuracy.
Table 3: The table summarizes the hyperparameters used for distributed training of MNIST classifier (Fig. 8, Tab.
Hyperparameter
Value
number of agents (N)
10
size of neural network layers
[400,
200, 10]
learning rate (gradient descent step-size)
0.1
number of iterations
100
A A, A = 0.1 x A
range between [0, 10)
x (FedProx) augmented lagrangian parameter (p) (FedADMM, Alg. I)
0.1
1
n (SCAFFOLD)
Table 4: The table summarizes the hyperparameters used for the distributed training of CIFAR-10 classifier (Fig. 8, Tab. 1)
Hyperparameter
Value
number of agents (N)
100
augmented lagrangian parameter (p) (FedADMM, Alg. 1)
0.01
learning rate
0.01
momentum number of iterations number of local epochs batch size
0.9
150
3
20
Ad A, A 0.01 A μ (FedProx)
range between [0,4]
0.1
ng (SCAFFOLD)
1
G.1. Linear Regression and LASSO with Non-i.i.d. Data
We conduct numerical experiments based on the following distributed learning problem:
N
min ZER
A'' - 1¹12 + A|2/11 2E 2
Σ
(55)
subject to x² = 0, i= 1..,,,,, N,
where A E Rmxn, E R". In the data generation process, we generate samples from three different distributions: a standard normal distribution, a Student's t distribution with one degree freedom, and a uniform distribution the range [-5,5] 5). These samples are concatenated form single dataset, which is then partitioned into subsets for each agent to
32

---

Distributed Event-Based Learning via ADMM
obtain (A*, b). Finally, we normalize the feature vectors and target values for each agent to prepare the data for the learning problem. In this non-i.i.d. setting, local optimal points of individual agents st are far away from each other, and their average Σ ///N is also far away from the global optima z.,. The experiments were run for max = 50 steps, which are required for Alg. to converge to the global optimal point with high accuracy. Fig. illustrates the communication load against the absolute difference between the objective function value f and the optimal value f", where the communication load is defined the number of communications accumulated over time.
100
100
Comm. load (5)
Comm. load (%)
60
60
Alg. a = 1,5
40
FedADMM
40
FedProx
20
FedAvg
20
OSCAFFOLD
G
10
10-8 8 10-6
10
10-2
10
10
10-6
10-6
10
10
10-2
100
|/
s-|
Figure 9: The figure shows the communication load versus accuracy trade-off for the different methods applied to two distinct problems derived from (55): linear regression (A 0, left panel), and on the right, LASSO (A 0.1, right panel).
In the first scenario, we set À 0 to obtain a linear regression problem, where the proposed algorithm with relaxation parameter 1.5 clearly outperforms baseline methods by a large margin. We note that the gap between the global and local optimal points prevents FedAvg and FedProx from converging to the optimal point f*
For the second case, we set À = 0.1 to solve the LASSO problem. By assumption, FedAvg, SCAFFOLD and FedADMM require the local objective functions to be smooth. However, we allow handling nonsmooth local objective functions, which relevant to the distributed learning problems with é regularization. To avoid noncontinuous gradient for the local minimization for SCAFFOLD, FedADMM, FedAvg and FedProx, the local update step is carried out by the following local gradient,
A N
sgn(x*)
| > 5
V f A (A's"
b¹) +
(56)
1
where d can be chosen small as 1e- 16 (double precision machine epsilon). However, we found that the results are largely unaffected by the choice of 8.
Table 5: The table summarizes the hyperparameters used for the distributed linear regression and LASSO experiments (Fig. 9).
Hyperparameter
Value
number of agents (N) augmented lagrangian parameter (p)
50
gradient descent step-size
number of iterations
50
A
range between [0, 10 10-2]
G.2. Effect of Communication Drops
To observe the effect of communication drops, repeated the same LASSO experiment in (55) with hyperparameters in Tab. 6, but this time, we allow the transmission of information from the agents the server to fail with probability of 0.3. As seen in the second panel of Fig. 10, if we have no reset, i.c., T = co, the algorithm cannot converge and a significant emror remains. On the left panel, the trade-off between communication load and suboptimality is presented. More frequent reset operations lead to a faster convergence and less error, in exchange for additional communication cost that comes with the reset.
33

---

Distributed Event-Basee Learning via ADMM
6 10a
6 10
Objective Value
T =
Comm. Load
25
Comm Load
1.1
10
7 5
7 10
2 10
24.8
10
T
24.6
10 10 10
25
50
0
25
50
I/
iteration
iteration
Figure 10: The left panel presents the trajectory of communication load versus suboptimality of the objective function value. The panel in the center shows the evolution of the objective function for different values of the reset period for drop rate of 0.3 and for A = 10 whereas the right panel shows the cumulative communication load over time in addition to the reset communication at each 7 step.
Table 6: The table summarizes the hyperparameters used for the distributed LASSO experiment against communication drops (Fig. 10).
Hyperparameter
Value
number of agents (N)
50
regularization parameter (A)
0.1
augmented lagrangian parameter (p)
relaxation parameter (a)
1
gradient descent step-size
number of iterations d
50
A
10
G.3. Distributed Training on a Graph
Our distributed learning algorithm, Alg. 2, is general enough to train a machine learning classifier over network of agents; the network structure can be encoded by a proper selection of the linear constraint matrices and (see App. for further details). Our framework therefore generalizes well beyond server-client structures, and our theoretical analysis also captures the influence of the network structure on the resulting convergence rate.
In order highlight the versatility, train an MNIST Classifier over a network of agents. We use multi-layer perceptron that has the same structure as in Sec. 5 and consider situation where each agent has only access the training data of single digit. Fig. 11 shows the resulting communication load and classification accuracy trade-off on the entire dataset (left), whereas the diagram on the right shows the network structure (only communication along the edges of the graph is allowed), The error bars indicate the range (minimum and maximum) of the classification accuracy among the different agents.
The results shown Fig. and highlight that a purely random selection of agents (suggested (Yu Freris, 2023) results in worse trade-off curve, which further motivates our event-based strategy. We also apply our algorithm much larger distributed learning problem with 50 agents and where the corresponding accuracy versus communication trade-off is shown in Fig. 12, together with the agent network that has been used.
Table 8: The table summarizes the hyperparameters used for the distributed linear regression experiment over a graph (Fig. 12).
Hyperparameter
Value
number of agents (N)
50
augmented lagrangian parameter (p)
10
number of iterations =
17 x 103
range between [0, 1]
34

---

Distributed Event-Basee Learning via ADMM
100
Vanilla
Comm. Load (%)
80
Randomized Porig = 0.1
Random selection
60
40
4
8
9
20
65
70
75
Classification Accuracy (%)
Figure 11: The figure shows comparison of the vanilla event-based and the randomized event event-based communication strategy (see Sec. 2) with purely random selection of agents. The outcome of purely random strategy is consistently worse with respect to the resulting trade-off between communication load and classification accuracy. The right panel visualizes the agent network with ten agents connected with 70 edges.
Table 7: The table summarizes the hyperparameters used for the distributed training of MNIST classifier over graph (Fig, 11).
Hyperparameter
Value
number of agents (N)
10
size of neural network layers
[400, 200, 10]
learning rate (gradient descent step-size)
10-3
augmented lagrangian parameter (p)
5 x 10-3
number of iterations
103
number gradient steps per iteration
5
A
range between [0.0,
100
Vanilla
Comm. load (%)
Random selection
10
10-3
10
1f- 1*1
Figure 12: The first panel shows the comparison of the communication load versus solution accuracy for different communication methods applied the linear regression problem derived from (55) = 0). The right panel visualizes the agent network with 50 agents connected with 1762 edges.
35


Reviews:
[{"review_id": "fi3hsMvT8C", "reviewer": "Reviewer_QcWU", "summary": "This paper proposed an ADMM style algorithm with event-triggered communication for minimizing the sum of a smooth possibly nonconvex function and a closed proper convex convex regularizer subject to linear equality constraints. This general problem formulation subsumes the typical consensus optimization framework, which enables one to apply the proposed algorithm to the typical federated learning problem setup (parameter server) and decentralized communication topologies.\n\nTheoretical guarantees are provided using a Lyapunov analysis. In the strongly convex setting, this work can achieve an accelerated linear convergence with a dependence on the square-root of the condition number, up to a neighbourhood of the minimizer that depends on the threshold of communication triggering, as well as the the periodic \"resets\" required for handling dropped messages. In the non-convex case, a fast O(1/k) rate is proven. The proposed method involves exactly solving for nested optimization problems \"argmin,\" however, in practice this is replaced with a few stochastic gradient steps.\n\nEmpirical results provided training an MLP on MNIST, a ConvNet on CIFAR10, and linear regression with L1 regularization in the appendix, comparing to established federated learning baselines.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback and recognition of our work’s strengths. We reviewed (Hadjicostis et al. 2016), and their approach using running sums offers an interesting alternative to periodic synchronization. While our method ensures strong theoretical guarantees, exploring tools from the gossip literature could be a valuable direction for future work to further mitigate communication drops.\nWe appreciate the reviewer’s insights and are happy to provide further clarifications if needed.", "claims_and_evidence": "All claims are well supported, theoretical results are the primary contribution and are relatively impressive. Empirical results are convincing, with sufficient details provided in the appendix.", "methods_and_evaluation_criteria": "Main claim is to reduce the number of required communication rounds. Thus focusing on validation accuracy of downstream tasks as a function of communication rounds is appropriate.", "theoretical_claims": "Coarsely went through the proofs in the appendix, which look ok.", "experimental_designs_or_analyses": "Yes checked all experiments, including those in the appendix. All appear sound.", "relation_to_broader_scientific_literature": "Paper is well situated within the broader literature on federated learning.", "essential_references_not_discussed": "Nothing major, but the approach to handling dropped packages is a bit brutish. Essentially, need exact synchronization to mitigate the effect of dropped packages, and the frequency of this synchronization is reflected in the residual error of the convergence bounds. There are already tools in the gossip literature for dealing with dropped packages by tracking running sums (Hajdicostos et al., IEEE TAC 2016). I am curious whether such approaches can be combined with the proposed method to better handle dropped packages. As can be seen in Figure 10 in page 33 of the Appendix, dropped packages require significant synchronization to establish fine-grained convergence.\n\nHadjicostis et al., “Robust distributed average consensus via exchange of running sums,” IEEE TAC, 2016.", "other_strengths_and_weaknesses": "Well-written paper with solid results, convincing empirical experiments, well document experimental setup in the appendix, and several additional ablations in the appendix.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "N.A.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i1Bjyr1OLG", "reviewer": "Reviewer_YpUD", "summary": "The authors present an event-based distributed agent framework that leverages a relaxation of Alternating Direction Methods of Multipliers (ADMM) to provide a framework with a reduced communication cost.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time and effort invested in evaluating our work. Below, we address each of the points raised.\n\n- **Robustness to Biased/Shifting Distributions:**\n\nOur experiments already use heterogeneous datasets with inherent bias and distribution shifts among agents (e.g., each agent having one digit in MNIST, shown in Fig. 8 and other cases in Fig. 3,9,11 and 12).\n\n- **Relevance to Safe Zone Design:**\n\nWe acknowledge the relevance of reducing communication overhead through local conditions in distributed systems. We will incorporate the corresponding reference and the following discussion in the revised version of our manuscript: \n\nOur approach similarly monitors local models through local constraints (our communication event definition, see (2) in the paper), which collectively guarantee the global condition of overall error remaining bounded. While thresholding can be seen as a subset of such local constraints, our methodology is directly inspired by the send-on-delta (SoD) concept (Miskowicz, 2006) and event-based control literature, where communication is triggered by significant state changes. \n\n- **Bad Actors and Gradient Poisoning Attacks:**\n\nOur method is compatible with existing techniques that mitigate issues related to bad actors and gradient poisoning. Addressing all possible challenges in federated learning is beyond the scope of a single approach. However, our event-based methodology can be integrated with robust aggregation or anomaly detection methods [1,2] to improve security without compromising communication efficiency. We will add these methods into our discussion as possible compatible solutions.\n\n[1] Yin, D., Chen, Y., Kannan, R. &amp; Bartlett, P. (2018). Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates. Proceedings of the 35th International Conference on Machine Learning, 80:5650-5659 \n\n[2] Pillutla K., Kakade S. M. and Harchaoui Z. (2022) \"Robust Aggregation for Federated Learning,\" IEEE Transactions on Signal Processing, 70:1142-1154\n\nWe thank the reviewer for bringing this up.\n\n- **Code in the Submission:**\n\nAll details related to our implementation can be found in App G. We will release our code if the manuscript gets accepted. However, we are happy to share the current version of the code upon request.\n\n---\n\nWe believe we have addressed all points and agree to add further discussions to the final version. We kindly request raising our paper’s score based on our responses. If further clarifications are needed, we are happy to provide them and refine our work.", "claims_and_evidence": "The authors make sufficient claims to support their idea and also list its limitations which is notable. Overall, I feel that the evidence provided is enough to verify the author's claims.", "methods_and_evaluation_criteria": "The method is compared against a suite of recent methods and seem to be sufficient given the application at hand.", "theoretical_claims": "The theoretical claims are sound but in order to be followed fully one has to delve into the appendix. I feel that _critical_ claims and ideas should be present in the main text.", "experimental_designs_or_analyses": "Overall the experimental design is acceptable however I would appreciate to have an ablation study as well as use data drawn from biased/shifting distributions to see how robust the framework is in such conditions.", "relation_to_broader_scientific_literature": "The paper reduces the communication overhead in a distributed system when local models undergo substantial transformation. It is heavity related to convex safe zones [1] and it would be great for the authors to compare against similar literature which is missing in the text.\n\n[1] Distributed query monitoring through convex analysis: Towards composable safe zones, Garofalakis et al.", "essential_references_not_discussed": "I feel that the paper lacks discussion on the broader topic mentioned above, but other than that the authors have included sufficient ammount of references.", "other_strengths_and_weaknesses": "While the paper proposes a significant reduction in the communication cost, it is still missing imporant guarantees required in such a system. The authors also listed most of them but I feel not catering for bad actors and to gradient poisoning attacks limits the system applicability.\n\nIt would be great if the authors discussed potential methods to mitigate these concerns.", "other_comments_or_suggestions": "Nothing of note.", "questions_for_authors": "Most of my theoretical concerns were answered in the previous segments. However, I could not find the code to replicate the experiments in the supplied submission. Is there any reason why the authors did not include the associated artefacts?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CYF8xJUXE3", "reviewer": "Reviewer_4Bk5", "summary": "This paper introduces an event-triggered distributed learning method using ADMM to reduce communication in federated learning (FL) while handling non-i.i.d. data distributions. \n\nThe key contributions claimed include:\n- A communication-efficient approach that reduces the number of message exchanges using an event-based trigger.\n- A convergence analysis for convex and nonconvex settings, with accelerated rates in the convex case.\n- Robustness to communication failures, both theoretically and experimentally.\n- Empirical validation using MNIST and CIFAR-10, showing up to **35% communication savings** over baselines like FedAvg, FedProx, SCAFFOLD, and FedADMM.\n\nThe approach is interesting and contributes to reducing communication in distributed learning, but the empirical evaluation is limited to small-scale image classification datasets.\n\n===== After rebuttal. =======\n\nThanks for the authors' responses. My questions and concerns have been addressed. I tend to accept this submission. So I increase my point.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for their thorough review and constructive feedback. \nBelow, we address the specific points raised.\n\n- **Justification of Experiment Design and Generalization:**\n\nThe point of our manuscript is to present a distributed optimization/learning algorithm that is both communication-efficient and robust, even under heterogeneous data distributions (e.g., each agent having one digit in MNIST, shown in Fig. 8). The experiments were designed to demonstrate the feasibility of our method in these scenarios. Additionally, we show that our approach scales to larger networks, with examples using 100 clients to train a CNN on CIFAR-10 (Fig. 3) and 50 agents that communicate over a graph (Fig. 12). Our theoretical result (Corollary 2.2) guarantees that the method can indeed scale to large networks. Numerical experiments align with these theoretical predictions, highlighting that our approach is effective even in the presence of 100 agents or more.\n\n- **Missing References:**\n\nThank you for bringing these papers to our attention. We will incorporate them into the related work section of the revised manuscript. \n\nThe paper by Swaroop et al. (2025) is very recent, so it was not included in our initial submission. Regarding Chen et al. (2022), which discusses the ordered ADMM variant, we cite other relevant works related to our ADMM variant. We will include Chen et al. (2022) in the revised manuscript.\n\nWe will also add references to alternative convergence techniques, such as Liang et al., 2022 and Deng et al., 2024. Additionally, (Glasgow, 2022) proves FedAvg is suboptimal under heterogeneity, which aligns with the findings of (Li, 2020c) that we already cite, but we will include this reference as well.\n\n- **Communication vs Performance Trade-off:**\n\nOur framework allows explicit trade-offs between communication load and solution accuracy, which we demonstrate through experiments in Fig. 8, 9, 11, 12 (App. G). These curves clearly show the relationship between the communication threshold and the resulting model accuracy. \n\n- **Benefits of Event-triggered Communication:**\n\nOur framework, based on ADMM with event-triggered communication, not only saves communication but also ensures convergence under heterogeneous data distributions. This is not guaranteed by many other federated learning methods. We also provide a bounded error guarantee, which can be controlled by a single threshold value ($\\Delta$). Our numerical examples (see, e.g., Fig. 3, as well as 8, 9, 11, 12) highlight that the event-triggered communication strategy requires much less communication for a given target accuracy than a vanilla communication strategy that randomly communicates among neighbors (in the context of our ADMM-based approach).\n\n**Clarifications**\n\n- **Interpretation of $d_{k+1}^i$:**\n\nThe term $d_{k+1}^i$, defined in line 189, encapsulates the combined effect of the local primal and dual updates. Its change essentially quantifies the deviation of the local state from the last communicated state and serves as the key signal for triggering communication (see (2)).\n\n- **Practical Tuning Strategy for $\\Delta_k$:**\n\nThank you for raising this point. We discuss a tuning strategy in line 347, where we suggest a time-varying schedule, such as $\\Delta_k = \\Delta_0 / (k+1)^t$ with $t > 0$. Convergence is further analyzed in App.F. Alternatively, the communication threshold can be actively tuned based on feedback from the system, as in [1].\n\n[1] Cummins, M., Er, G. D., Muehlebach, M. “Controlling Participation in Federated Learning with Feedback” (arXiv:2411.19242).\n\n- **Generalization to Decentralized Settings:**\n\nWe demonstrate in App. G (see Fig. 11 and Fig. 12) that our algorithm operates over a network of agents, supporting decentralized FL systems. \n\n- **Covering Asynchrony, Network Delays and Heterogeneous Computing Capabilities:**\n\nWe already discuss the adaptability of our approach to asynchronous systems at the end of the manuscript (line 412). While initially framed as a synchronous method, event-based communication naturally extends to asynchronous settings, enabling robust operation in real-world scenarios with varying network reliability and synchronization.\n\nWe also propose to model the effect of stragglers, network delays and heterogeneous computing capabilities as communication drops, which are effectively managed via our reset strategy. Proposition 2.1, Corollary 2.2 and Theorem 4.1 provide theoretical guarantees for convergence under these conditions.\n\n---\n\nWe believe we have addressed all the questions and provided the necessary clarifications. We kindly request raising our paper’s score based on the responses provided. If there are further questions or additional clarifications needed, please let us know.", "claims_and_evidence": "- Claim: \"Our method reduces communication while remaining agnostic to data distribution.\"\n  - **Partially valid:** These are general advantages of FL methods, and it's unclear whether the event-triggered mechanism offers a **significant advantage** beyond existing FL techniques.\n\n- Claim: \"We ensure convergence by setting a time-varying $\\Delta_k \\to 0$.\"\n  - **Unclear in practice:** The authors do not provide a **practical tuning strategy** for $\\Delta_k$, which is critical for real-world implementations.\n\n- Claim: \"Our work is the first to analyze communication failures in event-triggered ADMM.\"\n  - **Partially valid:** While the paper contributes to understanding failures in event-based ADMM, prior work in **randomized communication reduction** and **partial client participation** should be acknowledged.", "methods_and_evaluation_criteria": "- The event-triggered ADMM approach is reasonable, but the paper misses discussions on prior ADMM-based FL methods and SDE-based convergence analyses.\n- Missing Related Work:\n  - **FL methods using SDE/OPE tools**:\n    - Liang, J., Han, Y., Li, X., Liu, Y., Zhang, Y., & Lin, Z. (2022). Asymptotic behaviors of projected stochastic approximation: A jump diffusion perspective. NeurIPS 2022. (Jump diffusion perspective)\n    - Deng, W., Zhang, Q., Ma, Y. A., Song, Z., & Lin, G. (2024). On Convergence of Federated Averaging Langevin Dynamics. UAI 2024. (Federated Averaging Langevin Dynamics)\n    - Glasgow, M. R., Yuan, H., & Ma, T. (2022). Sharp bounds for federated averaging (local SGD) and continuous perspective. AISTATS 2022. (Sharp bounds for FedAvg)\n  - **Federated ADMM studies**:\n    - Swaroop, S., Khan, M. E., & Doshi-Velez, F. (2025). Connecting Federated ADMM to Bayes. ICLR 2025 (to appear).\n    - Chen, Y., Blum, R. S., & Sadler, B. M. (2022). Communication efficient federated learning via ordered ADMM in a fully decentralized setting. CISS 2022.\n  \n- Experimental limitations:\n  - Only small-scale datasets (MNIST, CIFAR-10) are tested.\n  - The paper ignores asynchrony and stragglers, which are critical in real-world FL.", "theoretical_claims": "- Theoretical results rely on strong convexity:\n  - The claimed accelerated rates are only valid under strong convexity, limiting applicability to deep learning models.\n  - The nonconvex case analysis (Theorem 2.3) provides only a slow $O(1/k)$ rate, which does not demonstrate a significant advantage over existing FL methods.\n  - The analysis is for deterministic optimization while practices favor stochastic optimization.\n\n- Interpretability issue in Algorithm 1:\n  - The term $d_{k+1}^i$ is not well explained.\n  - **Question:** Could the authors clarify how this term fits into the computation and **why it is needed?**", "experimental_designs_or_analyses": "- Communication savings are demonstrated, but scalability is unclear:\n  - The method is tested on small networks. What happens when scaling to hundreds or thousands of clients?\n  - There is no study on network delays or heterogeneous computing capabilities.\n\n- No clear study on the benefits of event-triggered communication:\n  - The results show communication savings, but is there a trade-off in terms of final model performance?\n  - **Question:** Could the authors summarize the **practical benefits** of event-triggered communication?", "relation_to_broader_scientific_literature": "- The paper didn't discuss some prior work in ADMM variants for FL, particularly:\n  - ICLR 2025 (Swaroop et al.): Connections between Federated ADMM and Bayesian inference.\n  - CISS 2022 (Chen et al.): Ordered ADMM for fully decentralized FL.\n\n- Misses FL literature using SDE-based analysis:\n  - UAI 2024 (Deng et al.): Federated Averaging Langevin Dynamics.\n  - NeurIPS 2022 (Liang et al.): OPE/SDE tools in FL.\n\n- The novelty claim on communication failures seems to be overstated since prior work already discusses robust FL under partial participation. The author should highlight the difference between them.", "essential_references_not_discussed": "See previous report for missing references.", "other_strengths_and_weaknesses": "**Strengths:**\n- The idea of event-triggered ADMM is interesting and could be useful for communication-limited FL settings.\n- The paper provides some convergence guarantees, though they rely on strong convexity assumptions.\n- The communication savings are demonstrated empirically.\n\n**Weaknesses:**\n- Experiments are too simple (MNIST, CIFAR-10) and may not generalize.\n- Some references are missing (SDE, ADMM in FL).\n- Unclear benefits of event-triggered communication beyond saving messages.", "other_comments_or_suggestions": "- Clarify the interpretation of $d_{k+1}^I$ in Algorithm 1.\n- Provide a practical tuning strategy for $\\Delta_k \\to 0$.\n- Discuss how this approach generalizes to asynchronous/decentralized FL settings.", "questions_for_authors": "See the other comments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces event-based communication triggering in ADMM to reduce communication cost. Compared to other optimization algorithms in federated learning, the communication cost is reduced by 35%+. Three reviewers found the paper technically sound, and all agreed to accept with scores of 3,4,4. All reviewers acknowledged reading rebuttal response. In particular, reviewer 4Bk5 gave detailed review with constructive feedback, and raised score from 3 to 4 after discussion. I would encourage the authors to incorporate the feedback to their next version. 

Reviewers also mentioned that they are more familiar with federated learning than ADMM and distributed optimization in general. In my opinion, the proposed method is a rather agnostic improvement on ADMM, not necessarily tied to FL. In fact, as some of the reviewers also allude to, I would strongly encourage the authors discuss the application of the proposed algorithm in practical federated learning. For example, the applicability to cross-device, or cross-silo FL; whether the algorithm can handle stragglers, and partial participation. These are important practical considerations, and the authors can probably find discussions in [Advances and Open Problems in Federated Learning](https://arxiv.org/abs/1912.04977) and [A Field Guide to Federated Optimization](https://arxiv.org/abs/2107.06917).
Decision: Accept (poster)