Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means
Authors: Anna van Elst
Igor Colin
Stephan Clémençon
Venue: NeurIPS 2025 poster ()
Keywords: Decentralized Learning
Gossip Algorithms
Ranking
Rate Bound Analysis
Robust Estimation
Primary area: theory
TL;DR: We introduced and analyzed two novel gossip algorithms for rank and trimmed means estimation, proving convergence rates of $\mathcal{O}(1/t)$.

Abstract: This paper addresses the problem of robust estimation in gossip algorithms over arbitrary communication graphs. Gossip algorithms are fully decentralized, relying only on local neighbor-to-neighbor communication, making them well-suited for situations where communication is constrained. A fundamental challenge in existing mean-based gossip algorithms is their vulnerability to malicious or corrupted nodes. In this paper, we show that an outlier-robust mean can be computed by globally estimating a robust statistic. More specifically, we propose a novel gossip algorithm for rank estimation, referred to as \textsc{GoRank}, and leverage it to design a gossip procedure dedicated to trimmed mean estimation, coined \textsc{GoTrim}. In addition to a detailed description of the proposed methods, a key contribution of our work is a precise convergence analysis: we establish an $\mathcal{O}(1/t)$ rate for rank estimation and an $\mathcal{O}(1 / {t})$ rate for trimmed mean estimation, where by $t$ is meant the number of iterations. Moreover, we provide a breakdown point analysis of \textsc{GoTrim}. We empirically validate our theoretical results through experiments on diverse network topologies, data distributions and contamination schemes.

Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means
Anna van Elst Igor Colin Stephan Clémençon
LTCI, Télécom Paris, Institut Polytechnique de Paris (anna. vanelst, igor .orrooo colin, stephan. clemencon) @telecom-pariss
Abstract
This paper addresses the problem of robust estimation in gossip algorithms over arbitrary communication graphs. Gossip algorithms are fully decentralized, relying only on local neighbor-to toabbo-tt--neghborr communication, making them well-suited for situations where communication is constrained. A fundamental challenge in exist- ing mean-based gossip algorithms is their vulnerability to malicious or corrupted nodes. In this paper, show that outlier-robust globally estimating a robust statistic. More specifically, we propose novel gossip algorithm for rank estimation, referred as GORANK, and leverage it design a gossip procedure dedicated to trimmed mean estimation, coined GOTRIM. addition to detailed description of the proposed methods, key contribution of our work is precise convergence analysis: we establish an (1/t)) rate for rank estimation and an (1//t) rate for trimmed mean estimation, where by is meant the number of iterations. Moreover, we provide breakdown point analysis of GOTRIM. We empirically validate our theoretical results through experiments on diverse network topologies, data distributions and contamination schemes.
be computed by
Introduction
Distributed learning has gained significant attention in machine learning applications where data naturally distributed across network, either due to resource or communication constraints [7]. The rapid development of the Internet of Things has further amplified this trend, as the number of connected devices continues grow, producing large volumes of data at the edge of the network. As a result, edge computing, where computation is performed closer to the data source, has emerged as viable alternative conventional cloud computing 6 36) By reducing reliance on centralized servers, edge computing offers several advantages. including lower energy consumption, improved data security, and reduced latency 6 36. In this context, several distributed learning frameworks, including Gossip Learning and Federated Learning, have been developed. Federated Learning depends on a central server for model aggregation [26). which introduces challenges such as communication bottlenecks and a single point of failure. In contrast, Gossip Learning provides fully decentralized alternative where nodes communicate only with their nearby neighbors [8]. addition. Gossip learning is particularly well-suited for situations where communication is constrained, such in ser-tt-pper or sensor networks.
One of the central challenges in distributed learning is robustness to corrupted nodes scenarios where some nodes may contain contaminated data due to hardware faults, or even adversarial attacks 8 (3). Consider network of sensors deployed to monitor the temperature in small region, as described [ In idealized scenarios, sensor noise is typically modeled by a zero- mean Gaussian. However, a recent survey (see [I]) mentions that sensor networks especially prone to outliers due to their reliance on imperfect sensing devices. Indeed, in practice, sensors can malfunction (e.g., become miscalibrated, get stuck at constant values, report extreme values
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Z
Swap
i
j
i
k
g
g
1. Vik E V: update rank Rg and trimmed mean Zµ estimates
2. Select (i E randomly
3. Swap observations
and average Z; and 2,
X, and X,
Figure 1: Illustration of a GOTRIM'S 's iteration paired with GORANK on a communication graph
(V, Initially, each node stores the observation Xx.
due to environmental interference). These issues introduce outliers the dataset which can corrupt the estimated temperature. Specifically, consider a setting in which fraction of the nodes hold outlying data [14). In Federated Learning, significant progress has been made in designing robust aggregation methods based on statisties, such as the median and trimmed mean
39 These statistics are known to be more robust to outliers than the standard mean [19]. However, ensuring robustness Gossip Learning remains challenging. Unlike Federated Learning. where a central server can enforce robust aggregation rules, gossip algorithms inherently rely on local communication. To the best of our knowledge, approaches relying on globally estimating robust statistics remain largely unexplored in the gossip literature.
In this paper, address the problem of robust estimation in gossip algorithms over arbitrary communication graphs. Specifically, we show that an outlier-robust mean can be computed by globally estimating robust statistic. Ranks play a crucial role in the framework we develop here, as they allow us to identify outliers and compute robust statistics on the one hand [30], and because they can be obtained by means of pairwise comparisons on the other. This allows us exploit the gossip approach proposed in [10] to compute pairwise averages (U (U-statistics) in decentralized way. Note that both ranks and trimmed means are inherently global statistics, which makes them more challenging to estimate in decentralized manner compared to statistics like averages. minima, or maxima that rely on local conservation principles.
Our main contributions are summarized as follows:
We propose GORANK, new gossip algorithm for rank estimation, and establish the first theoretical convergence rates for gossip-based ranking on arbitrary communication graphs, proving an (1/1t) convergence rate, where &. denotes the number of iterations.
We introduce GOTRIM, the first gossip algorithm for trimmed mean estimation which can be paired with any ranking algorithm. GOTRIM does not rely on strong graph topology assumptions- common restriction in robust gossip algorithms. We prove a competitive convergence rate of order (1/t) and provide breakdown point analysis, demonstrating the robustness of its estimate. Finally, we conduct extensive experiments on various contaminated data distributions and network topologies. Numerical results empirically show that (1) GORANK consistently outperforms previous work in large and poorly connected communication graphs, and (2) GOTRIM effectively handles outliers-ing its estimate quickly improves the naive mean and converges the true trimmed mean.
This paper is organized as follows. Section 2 introduces the problem setup and reviews the related works. In Section 3, present our gossip algorithm for ranking, along with its convergence analysis and supporting numerical experiments. Section introduces our novel gossip algorithm for trimmed mean estimation, together with a corresponding convergence analysis and experimental results. Finally, Section 5 explores potential extensions of our work. Due to space constraints, technical details, further discussions, and results deferred to the Supplementary Material.
2 Background and Preliminaries
This section briefly introduces the concepts of decentralized learning, describes the problem studied and the framework for its analysis.

---

2.1 Problem Formulation and Framework
Here, we formulate the problem using a rigorous framework and introduce the necessary notations.
Notation. Let n 2 L. We denote scalars by normal lowercase letters x E RR vectors (identified as column vectors) by boldface lowercase letters x E RD, and matrices by boldface uppercase letters X E R 'he set {1...., n) is denoted by [n|. R 's canonical basis by (ex h E [n]]] the indicator function of any event A by lA. the transpose of any matrix M by M and the cardinality of any finite set F by |F). By I, is meant the identity matrix in R=xn, by 1,, (1, ..... 1) the vector in R" whose coordinates are all equal to one, by || the usual lz norm, by [-] the floor function, and by A @ B the Hadamard product of matrices A and B. We model network of size n >> 0 as an undirected graph G = (V, E), where V = [n] denotes the set of vertices and E' C V x V the set of edges. We denote by A its adjacency matrix, meaning that for all (i. E V2, [A] in (i,j) E E, and by D the diagonal matrix of vertex degrees. The graph Laplacian of g is defined as L= A. A.
iff
Setup. We consider a decentralized setting where ni 2 real-valued observations Xi,..., X, are distributed over communication network represented by a connected and non-bipartite graph G = E). see [12] the observation X2 is assigned to node k E [n]] For simplicity, we assume no ties: for all & * Xx * X₁- Communication between nodes occurs in stochastic and pairwise manner: at each iteration, an edge of the communication graph G is chosen uniformly at random, allowing the corresponding neighboring nodes to exchange information. This popular setup is robust to network changes and helps reduce communication overhead and network congestion 10 [3]. We focus the synchronous gossip setting, where nodes have access to a global clock and synchronize their updates (5] 10 13.. We assume that a fraction 0 < E < 1/2 of the data is corrupted and may contain outliers, as stipulated in Huber's contamination model, refer to [9
The Decentralized Estimation Problem. The goal pursued here to develop a robust gossip algorithm that accurately estimates the mean over the network despite the presence of outliers, specifically the a-trimmed mean with a E (0, 1/2), i.e., the average of the middle (1 - -a))th fraction of the observations. This statistic, discarding the observations of greater smaller rank, is a widely used location estimator when data contamination is suspected; see [31 (34. Formally, Xn(n) be the order statistics (i.e., the observations sorted in ascending order), and define = [am] for E (0, 1/2). The a-trimmed mean is given by:
let Xn(1) Xn(2)=
1
Rx
Xn(k).
n
2m
A
Based on the rank of each node's observation Xx. namely rh = 1 + Ei= [[x,>x) in the absence of ties, for & E [n)]. it can also be formulated as a weighted average of the observations, just like many other robust statistics:
1 Σ (Fx)(r
Pa
km
where an, is a weight function defined as Wn.a (rk) = (n/(n-2m))Tim 22m) with the inclusion interval given by In,a = [u, v] where u = m + and n m..
The framework can be extended to the case of f 2 2 tied observations with the mid-rank method: the rank assigned to the tied values the average of the ranks they would have obtained in absence of ties, that is, the average of p + 1.p + 2, 2.....P + f, which equals p + (E + 1)/2, see (24]. To account for the possibility of non-integer rank estimates, one may use the adjusted inclusion interval to define the weights in (2) In.a - 1/2, v + 1/2]. Note that when ranks are integers, this adjustment has no effect.
Remark 1.
Our setup assumes honest nodes, meaning they perform updates correctly and consistently based on their local observations. However, under Huber's 's contamination model, these observations may include outliers. Note that this setup is fundamentally different from the Byzantine model where nodes may behave urbitrarily or maliciously, potentially sending incorrect updates with the intent to disrupt consensus degrade performance. This model is still realistic in many practical settings: sensor could be miscalibrated, stuck at a fixed value, or may consistently report incorrect readings due to enviroumental factors, without necessarily being attacked.
Remark 2.
3

---

2.2 Related Works State of the Art
The overview of related literature below highlights the novelty of the gossip problem analyzed here.
Distributed Ranking, Distributed ranking (or ordering) is considered in [9] where gossip al- gorithm for estimating ranks on any communication graph is proposed. The algorithm is proved to converge, in the sense of yielding the correct rank estimate, in finite time with probability one. However, their work does not provide any convergence rate bound, and empirical results suggest that the algorithm is suboptimal in scenarios with long return times, i.e., when the expected time for a random walk on the graph to return to its starting node is long (see the Supplementary Mate- rial). Alternatively, here we take advantage of the fact that ranks can be calculated using pairwise comparisons [(x,>xXi )1). so as to build on the GoSta approach in [10], originally introduced for the distributed estimation of U-statistics, with a proved convergence rate bound of order (1/t).
Robust Mean Estimation. To the best of our knowledge, the estimation of a-trimmed means has not yet been explored in the gossip literature. Several related works examine the estimation of medians and quantiles in sensor networks [15 23 33]. A key limitation of these works is their reliance on a special node, such as a base station or leader, which initiates queries, broadcasts information, and collects data from other sensors-an an assumption that does not apply our setting [15 23 33
Another work has proposed an algorithm for estimating quantiles [6]; however, there seems to be no guarantees of convergence to the true quantiles. Moreover, their algorithm assumes fully connected communication graph and the ability to sample from four nodes at each step and to sample K random nodes the end of the protocol, whereas we consider the more challenging setting of arbitrary communication graphs and pairwise communication. Recently, He et al. [77 proposed a novel local aggregator, ClippedGossip. for Byzantine- gossip learning. In our pairwise setup with fixed clipping radius, their approach- though reasonable for robust optimization does not work for robust estimation. Specifically, ClippedGossip ultimately converges to the corrupted mean and, therefore, fails to reduce the impact of outliers. A detailed analysis is provided in the Supplementary Material.
The following table assesses whether each method is fully decentralized, whether the estimator is unbiased, and whether theoretical convergence rates exist (for both complete and arbitrary graphs).
Method
Decentralized?
Unbiased?
Rates on: Any Graph? Complete Graph?
Chiuso al. (Baseline) Baseline++ (ours) GoRank (ours)
Complete Graph: ((exp(-t/1P)
x
Complete Graph: (cexp(-t/|E))
Any Graph: (11/t)
Haeupler et al. He et al.
X
Complete Graph: (log(()) rounds
Shrivastava et al. GoTrim (ours)
X
X
Any Graph: (11())
3 A Gossip Algorithm for Distributed Ranking - GORANK
In this section, we introduce and analyze the GORANK algorithm. We establish that the expected estimates converge to the true ranks at ( /cl)) rate, where the constant e >>> 0 (given in Theorem hhelow) quantifies the degree of connectivity of G: the more connected the graph, the greater this quantity and the smaller the rate bound. We also prove that the expected absolute error decreases at rate of O(1/vct) In addition, we empirically validate these results with experiments involving graphs of different types, showing that the observed convergence aligns with the theoretical bounds.
3.1 Algorithm - Convergence Analysis
We introduce GORANK. gossip algorithm for estimating the ranks of the observations distributed on the network, see Algorithm T
It builds on GOSTA, an algorithm originally designed for estimating
pairwise averages (U -tastiiiss of degree 2) proposed and analyzed in [10). The GORANK algorithm
exploits the fact that ranks can be computed by means of pairwise comparisons:
n
Fk = 1 + n
+ nrk. for .... n.
(3)
n

---

Algorithm 1 GoRank: a synchronous gossip algorithm for ranking.
1: Init: For each & E [n]. initialize YE < Xx and Rig s O. // init(k)
2: for = 1.2.....do do
3: for k=
do Update estimate: Ri + (1-1/s)RR + (x
4:
5: Update rank estimate: R2 + n +1. // update s)
6: end for
7: Draw (i.j) E E uniformly at random.
8: Swap auxiliary observation: Y; ++ Yj. // swap(i, j)
9:
end for
10: Output: Estimate of ranks Rx-
Let R3 (t) and R2 (t) denote the local estimates of r. and r' respectively at node k E [n]] and iteration t 2 1. Each node maintains an auxiliary observation, denoted (t), which enables the propagation of observations across the network, despite communication constraints. For each node k. the variables are initialized as (0) Xx and R2 (0) = O. At each iteration 2 1, node & updates its estimate (t) by computing the running average of R (t - 1) and (xx->)((-1))- The rank estimate is then computed as R& (t) = n. (t) + 1. Next, an edge (i E E is selected uniformly at random, and the corresponding nodes exchange their auxiliary observations: (t) = (t 1 1) and (t Yt(t 1). This random swapping procedure allows each observation to perform random walk on the graph, which described by the permutation matrix W (t) I, (e: (e e,) TT which plays a key role in the convergence analysis [O]. By taking the expectation with respect to the edge sampling process, we obtain W1 == W (t) I, - (1 (1/EE) L. This stochastic matrix W, shares similarities with the transition matrix used in gossip averaging 5 25 32 :: it is symmetric and doubly stochastic. Consequently, W, has eigenvector 1, with eigenvalue 1, resulting in a random walk with uniform stationary distribution. In other words, after sufficient iterations (i.e.. in nearly stationary regime), each observation has (approximately) an equal probability of being located at any given node-a property that would naturally hold (exactly) without swapping if the communication graph were complete. In addition, it can be shown that, if the graph is connected and non- non-bipartite, the spectral gap of W1 satisfies 0- < c < 1 and is given by /2/ E where Ae is the second smallest eigenvalue (or spectral gap) of the Laplacian [1O]. This spectral gap plays a crucial role in the mixing time of the random walk, reflecting how quickly (geometrically) converges to its stationary distribution [32]. In fact, the spectral gap of the Laplacian is also known as the graph's hs algebraic connectivity, larger spectral gap meaning a higher graph connectivity (27
Remark 3. We assume that the network size n Z 2 is known to the nodes. not, can be easily estimated by injecting value +1 into the network, where all initial estimates applying the standard gossip algorithm for averaging [3], see the Supplementary Material. The quantities computed for each node will then converge 1/n.
0, and
Remark 4. The asynchronous extension of GORANK is straightforward: it replaces the global iteration counter with local counter C2 maintained at each node k. The update rule then becomes (1-1/Ck)R; + (1/Cx)lx,,>t= Empirically, we find that Asynchronous GORANK converges slightly faster and is more efficient than its synchronous counterpart. Due to space constraints, the detailed algorithm and experimental results are deferred to Appendix H.
We now establish convergence results for GORANK, by adapting the analysis in [10. origi- nally proposed to derive convergence rate bounds for GOSTA follows. For l [n]. set and observe that the true rank of observation X₁ is given by Fa- = h 1,, + 1. At iteration é 1, the auxiliary observation has not yet been swapped, so the expected estimate is updated as E (1)
h& = (I -(x.,xx,...IIxxxxx.,))
hī eg- At the end of the iteration, the auxiliary observa- tion is randomly swapped, yielding the update: E[R (2)] (1 [1/2)E[M) RR, (1)] h1/2)h W 1,,, where E|.] denotes the expectation taken over the edge sampling process. Using recursion, the evolution of the estimates, for any 2 1 and & E [m], is given by
B[R[(() = (1/0) Σ hg Wie and ([)+ = nE(R + 1.
5

---

Note that E [R (t) can be viewed as the average of terms of the form (x,) where X₁ is picked at random. Observe also that R(t) = [R1 (t).... (t)) is not permutation of [n] in general: in particular, we initially have (1) 1 for all [n]. We now state convergence result for GORANK, which claims that the expected estimates converge to the true ranks at a rate of (1/ct).
Theorem (Convergence of Expected GORANK Estimates). We have: Vk E [n], Vt 2 1,
ok d'
[t]
- m4
where the constant c >2/ [E] represents the connectivity of the graph, with X2 being the spectral is determined by the
gap of the graph Laplacian, and the rank functional σ% 3/2
score generating function Φ u E (0,1) Vu(1 u).
More details, as well as the technical proof, are deferred to section C of the Supplementary Material. Theorem establishhes that, for each node, the estimates converge in expectation to the true ranks at O rate, where e is a constant depending on the graph's algebraic connectivity: higher network connectivity leads to faster convergence. In addition, the shape of the function ø involved in the bound ( resp. of u E (0, + vu(1 u), suggests that extreme (i.e., the lowest and largest) values intrinsically easier to rank than middle values, also Fig. 2 Regarding its shape, observe that GORANK can be seen as an algorithm that estimates Bernoulli parameters (L/n) Ei= xxx, (Tk- 1)/n and, from this perspective, the oy 's can be viewed as the related standard deviations, up to the factor 3/2.
We state an additional result below that builds upon the previous analysis, and establishes a bound of order (1///ol for the expected absolute deviation.
Theorem 2 (Expected Gap). Let k E [n], and let and on be as defined in Theorem ! For all 1 2 1,
have: B (t) Tkl 1 S O (1/ct) of Consequently,
E (t) rxll 0 ( o
Refer to section in the Supplementary Material for the technical proof. Theorem 2 shows that the expected error in absolute deviation decreases at rate of (l1/vel), similar to the convergence rate for the expectation E R()] but with a square root dependence. In addition, Theorem 2 can be combined with Markov's 's inequality to derive high-probabie be shown in the next section, this is a key component in the convergence analysis of GOTRIM.
bounds on the ranking error. As will
Building upon the previous analysis, we derive another gossip algorithm called Baseline+ +, an improved variant of the one proposed by [Chuuo for decentralized rank estimation (9. is described at length in section A of the Supplementary Material. The algorithm's 's steps and propagation closely resemble those of GORANK. However, instead of estimating the means (3) based on pairwise comparisons directly, +aseline++ aims to minimize, for each node l E [nt]. specific ranking loss function, namely the Kendall 7 distance dh (X, R) = Ei= ((xxx-X)) RO), counting the number of discordant pairs among ((Rs, Xx), (Ri, Xi)) with 1, .... n. While GORANK provides quick approximation of the ranks, especially in poorly connected graphs, Baseline++. despite being slower at first, may ultimately achieve lower overall error as it minimizes a discrete loss function. However, GORANK has practical advantage: it does not require an initial ranking, which may not always be available in real-world settings. Moreover, it comes with convergence rate guarantees that apply to any graph topology. In contrast, analyzing the convergence of Baseline++ on arbitrary communication graphs is challenging and is left for future work.
3.2 Numerical Experiments
Setup. We conduct experiments on a dataset S (1.....n) with = 500, distributed across nodes of communication graph. Our evaluation metric is the normalized absolute error between estimated and true ranks, i.e., for node k at iteration t, the error is defined as (x()) = R& (t) rsl/n. While more sophisticated ranking metries such as Kendall 7 exist, they are not relevant in our context, as we focus on individual rank estimation accuracy. We first examine the impact of the constants appearing in our theoretical bounds (see Theorem 1), the one related to graph connectivity and the one reflecting rank centrality. To this end, consider three graph topologies: the complete

---

graph (c = 4.01 X 10-3), in which every node is directly connected to all others, yielding maximal connectivity; the two-dimensional grid (c 1.65 x 10 "), where each node connects its four immediate neighbors; and the Watts- network (c = 3.31 x 10-1), randomized graph with average degree
and rewiring probability p = 0.2, offering intermediate connectivity between the complete and grid graphs. Then, we compare GORANK with the two other ranking algorithms Baseline and Baseline++. Figure (a) was generated on a Watts-Strogate graph, averaged over 1e3 trials. Figure (b) and (c) show the convergence of ranking algorithms with mean and standard deviation computed from 100 trials: figure (b) shows the convergence of GORANK on different graph topologies; figure (c) compares the convergence of the ranking algorithms a 2D Grid graph. All experiments were run on a single CPU with 32 GB of memory for 8e4 iterations, with a total exccution time of approximately two hours. The code for our experiments is publicly available
Absolute Error vs. Rank
Absolute Error vs. Timesteps
Absolute Error vs. Timesteps
0.20
0.5
0.07
0.50
Grid Watts Strogatz
GoRank (ours)
0.4
Baseline (ours)
Complete
Baseline (Chiuso et al.
0.05
0.04
0.25
0.2
0.02
GoRank Bound
0.1
-..00
0.00
0.0
125
250
375
500
204
4e4
6e4
8o4
264
4e4
6e4
(a) Role of
(b) Role of
(c) GoRANK Baseline
Figure 2: Illustration of the behavior of GORANK: (a) shows how the absolute error of the rank
estimates of GORANK aligns with the shape of the function Φ. and highlights the role of the constant ax for k E [n] in the error bound; (b) compares the convergence rate of GoR ANK across different graph topologies (i.e. levels of connectivity), illustrating the influence of the constant in the bound; (c) compares GORANK with existing method (Baseline) and an alternative ranking algorithm developed in this work (Baseline++).
Results. Together, the figures illustrate key properties of GORANK. Figure (a) empirically confirms that extreme ranks are easier estimate than those in the ceadlle-consistem. with the shape of the theoretical bound. Figure (b) highlights the impact of graph topology: as connectivity decreases, convergence slows, in line with the theoretical bounds. Finally, Figure (c) compares the different methods. GoR ANK and Baseline++ provide fast rank approximations even for large, poorly con- nected graphs (e.g., 2D grid graph). Baseline++ appears converge faster in the end, as it directly optimizes a discrete loss. Baseline, on the other hand, converges more slowly throughout, which aligns with its dependence on the return time (i.e., the expected time for a random walk revisit its starting node), a quantity known to be large for poorly connected graphs. More extensive experiments and discussion, confirming the results above, can be found in the Supplementary Material.
4 GOTRIM - A Gossip Algorithm for Trimmed Means Estimation
In this section, we present GOTRIM, gossip algorithm for trimmed means estimation. We establish a convergence in (1/t)) with constants depending on the network and data distribution.
4.1 Algorithm Convergence Analysis
We introduce GOTRIM, a gossip algorithm to estimate trimmed mean statistics (see Algorithm 2
which dynamically computes weighted average using current estimated ranks. Notably, GOTRIM
can be paired with any ranking algorithm, including GORANK consequently. Let (t) and (t)
denote the local estimates of the statistic and weight at node k and iteration t. First, by Equation 2 the a-trimmed mean can be computed via standard gossip averaging: for all k E [n]. (t) (1/n) Σ Wi( X1, where (i( Wn,a (t)) with (,,a(() (-) defined in Section 2. Secondly,
'The code is available at weg.tuu..om/mnnnaaaaesesiieeeeee
7

---

Algorithm 2 GoTrri: a synchronous gossip algorithm for estimating a-trimmed means.
1: Input: Trimming level E (0, 1/2), function Wn,a defined in and choice of ranking algorithm
rank (e.g. GoRank).
2: Init: For all node k, set Z <- 0, W <- and Rg +- rank.init(k).
3: for = 1. do
4: for k = 1,... ..... do
5:
Update rank: Ry f- rank. update(k;s))
6:
Set W Wn.a (.
7: Set Zk f Zk + (Wg Wk) Xx-
8:
Set W f W.
9:
end for
10:
Draw (i,j) E uniformly at random.
11:
Set Z4, 23 < (Z 22)/2.
12:
Swap auxiliary variables: swap j)
13:
end for Output: Estimate of trimmed mean Za.
since ranks Rg(t) (t) vary over iterations, the algorithm dynamically adjusts to correct past errors: at each step, it compensates by injecting (Wx(t) - (t ()) Xx into the averaging process. On the one hand, we have an averaging operation which captured by the averaging matrix: (2( = I, (e: e,)(e, /2) Similarly to the permutation matrix (see the previous section), the expectation of the averaging matrix is symmetric, doubly stochastic and has spectral gap that satisfies 0 c2 < and is given by c2 = cc/2 [5] 32). On the other hand, we have a non-linear operation that depends on the estimated ranks: at each iteration >> 0, each node k is updated Zz Zt(t 1) (t) Xx., where (t) Wx(t) W& 1). Hence,
the evolution of the estimates can be expressed as Z(t) = W2(() (Z(t - + 8(t) C X), where Z(t) (t), (t) and d(t) (t) ...f),...d.............. (,, (t)). Taking the expectation
the sampling process, the expected estimates are given by: ((Z(()) = W₂ (Rl - 1)] + (w)()) @ X) with
W₂ I, [1/2 and Aw(t) [[]( For & 1, since Zu (0) 0, we have E B[Z(1) W (1) @ X. Recursively, for any > 0,
E B[Z
Aw oX.
We first state lemma that claims that Wtt(t) converges in expectation to (r).
Lemma (Convergence in Expectation of (t).. Let R(t) and (()) be defined as in Algorithm 7 and Algorithm respectively. For all E [n]] and t O, we have:
[[)] (Wnna))-Wna(ra)) (r.a((k)
0
o
where "Tk = min()r -a,, Irx - b1) 2 1/2 with a = [avn] + 1/2 and b = n - [an]] + 1/2 being
the endpoints of interval Tn.cr The constants and 0% are those defined Theorem 2.
Further details and the complete proof are provided in Section D of the Supplementary Material, Lemma 1 establishes that, for each node k. the estimates of the weight Wi converge in expectation to the true weight an,a (Tx) at a rate of O (1/rect). In addition, this lemma suggests that points closer to the interval endpoints are subject larger errors, as reflected in the constant 7x which is consistent with the intuition that these points require greater precision in estimating ranks.
Having established the convergence of the weights Wt((),, now focus the convergence of the estimates Zμ (t). The following theorem demonstrates the convergence in expectation of GOTRIM when paired with the GORANK ranking algorithm.
Theorem (Convergence in Expectation of GOTRIM). Let Z(t) be defined as in Algorithm 2 and assume the ranking algorithm is Algorithm
Then, for any > T min {t 1| ot 2 2og ()),
E ZZ)) - F. 1
K OII
where k= = (ot/2i, .... /2/12) and c, oke ih are the constants defined in Lemmal 1
8

---

See Section D of the Supplementary Material for the detailed proof. Theorem 3 shows that, for each node k, the estimate of the trimmed mean Z₁ converges in expectation to the true trimmed mean To at rate of O (1/c²t). While the presence of the c² term may appear pessimistic, empirical evidence suggests that the actual convergence may faster in practice. The vector K acts as rank-dependent mask over X, modulating the contribution of each data point X to the error bound. Specifically: (1)
extreme values are more heavily penalized by the mask, as they come with better rank estimation; (2) values with ranks near the trimming interval endpoints are amplified, as small inaccuracies in rank estimation can lead to disproportionately larger errors.
4.2 Robustness Analysis Breakdown Points
Consider dataset S of size n > and Tn, (S) real-valued statistic based on it. The breakdown point for the statistic (S) is detined as E" = Poe/nn, where Poe = min E N sups, (Sp
o the supremum being taken over all corrupted datasets Sy obtained by replacing p samples in S by arbitrary samples. The breakdown point a popular notion of robustness [20] corresponding here to the fraction of samples that need to be corrupted to make the statistic T, arbitrarily large (i.e., "break down"). For example, the breakdown point of the a-trimmed mean given by |om]/n, which is approximately a. We consider here a generalization of this notion, namely the T-breakdown point by replacing Pse with p. min N supsy [T) - Tn (S,)) 2 T)
where r > 0 is a threshold parameter. Since our algorithm does not compute the exact a-trimmed mean, we focus instead on determining the 7-breakdown point e (f) of the partial a-trimmed mean at iteration for each node k, i.e., the estimate (t). Given that this quantity was previously shown to converge to the a-trimmed mean, we expect that ef (t) S a. The following theorem provides framing bounds for the breakdown point of the estimates of GOTRIM when paired with GORANK.
Theorem 4. Let r > and 6, a E (0, 1). With probability at least 1 - 8, the T-breakdown point (t) of the partial a-trimmed mean iteration t T for any node h satisfies
1
(Lon))
1 K(ő)
| .00 S Et(()s [an] Vl T
max n
+
2
n
where K(0) = (L166) is a constant and T (log(L//TT) represents the time allowed for the
mean propagate.
See Section E of the Supplementary Material for the technical proof, which relies on the idea that, when estimating a partial a-trimmed mean, there are two sources of error: (1) the uncertainty in rank estimation, which can lead to incorrect data points being included in the mean, and (2) the delay from the gossip averaging, which requires certain propagation time T to update the network estimates. Note that, as t + 0o, Theorem 4 recovers the breakdown point of the exact a- erirrimed mean.
4.3 Numerical Experiments
Setup. The experimental setup is identical to that of the previous section, with the key difference being the introduction of corrupted data. Specifically, the dataset 5 is contaminated by replacing fraction = 0.1 of the values with outliers. We consider two types of corruption, each affecting [en] randomly selected data points: (a) scaling, where a value x is changed to sæ, and (b) shifting, where r becomes r + s. While this a relatively simple form of corruption, is sufficient to break down the classical mean. We measure performance using the absolute error between the estimated and true trimmed mean. For node i at iteration I, the error is given by E(1) = (1/n) Σ (1) Tal- Experiments (a) and (b) are run on dataset S, corrupted with scaling 10, using a Watts- SStoogStt and a 2D grid graph, respectively. Experiment (c) uses the Basel Luftklima dataset, corrupted with shift 100. This dataset includes temperature measurements from 105 sensors across Basel. graph with connectivity e = 4.7 x 10-4 is constructed by connecting sensors within km of each other. The code and dataset for our experiments is publicly available
Figure (a) empirically confirms that the uncertainty in the weight estimates is highest near the boundaries of the interval, consistent with our theoretical bound. Figures (b) and (c) show that GOTRIM, when combined with GORANK or even alternative ranking methods, quickly approximates
Results.
"The code and Basel Luktklima dataset available at githhbb..om/mnnaauuusssttottttto

---

Absolute Error of Weight vs. Rank
Absolute Error vs. Timesteps
Absolute Error vs. Timesteps
0.9
GoRank Bound
350
caftrim Beselines-
Colfim Coffark tours)
17.5
Gellim Bocel mew
Ge Colaank (ours)
300
Goodlo etail
comupted
15.0
Clipeed Gozzlp ald
250
12.5
10.0
0.3
150
7.5
5.0
100
50
2.5
125
250
375
500
2e4
4e1
6-4
8e4
1c4
2e4
2ed
3ed
(a) Role of of/ri
(b) Simulated Dataset
(c) Basel Luftklima Dataset
Figure Convergence behavior of GOTRIM in combination with different ranking algorithms. Figure (a) illustrates how the constant in the bound reflects the error of the weight estimate of GOTRIM. Figures (b) and (c) demonstrate that, for a 0.2 and 1, GOTRIM quickly improves on the naive corrupted mean and converges to the trimmed mean.
the trimmed mean and significantly improves over the corrupted mean (indicated by the black dashed line). Overall, GOTRIM quickly outperforms the naive mean under corruption and ClippedGossip which will ultimately converge to the corrupted mean. Additional experiments and implementation details are provided in the Supplementary Material.
5 Conclusion and Discussion
We introduced and analyzed two novel gossip algorithms: GORANK for rank estimation and GOTRIM for trimmed mean estimation. We proved convergence rates of (1/ft) and established robustness guarantees for GOTRIM through breakdown point analysis. Empirical results show both methods perform well large, poorly connected networks: GORANK quickly estimates ranks, and GOTRIM is robust to outliers and improves on the naive mean.
Byzantine Robustness. In this work, we focused on robustness to data contamination in the sense of Huber's ' framework. Extending these results to the more adversarial setting of Byzantine robustness remains an interesting direction. Developing a rigorous theoretical foundation for this setting still an open problem, and we plan to address it in future work.
Asynchronous Extension. Although our analysis focuses on the synchronous setting, real- world systems are often asynchronous. We present the asynchronous version of GORANK in Appendix H. The theoretical analysis in the asynchronous setting is carried out in an extension to this work [35].
Scalability. To demonstrate the scalability of our method on large networks, we repeated the experiments from Fig. (c) in Sections 3.2 and 4.3, originally conducted with n = 500, on larger networks with 1000 and 5000. The detailed results are provided in Appendix
Robustness to Network Disruptions. While robustness to data contamination is important, the robustness our proposed algorithms to network disruptions (e.g., edge or node failures, network partitioning) is equally crucial in real-world applications. In Appendix J, we provide detailed analysis of how our current framework can be extended.
Performance Sparse Graphs. An interesting question is whether algorithms perform well on sparse graphs. In practice, however, performance depends more on the graph's is connectivity than on its sparsity. To illustrate this, we present experiments in Appendix K sparse graphs with varying levels of connectivity.
Rank-based Statisties. GOTRIM naturally extends the decentralized estimation of rank-based statistics. This includes rank statistics (2I, which are key tools in data analysis-partionn for robust hypothesis testing as well as L-statistics (such as the Winsorized mean).
Further Discussion. In appendix I., we provide extended discussion several topics, including the optimality of the bounds, faster gossip algorithms, extension to multivariate data, and potential applications like robust decentralized optimization.
10

---

Acknowledgments
This research was supported by the PEPR IA Foundry and HilParis ANR Cluster IA France 2030 grants. The authors thank the program for its funding and support.
References
[1] Aya Ayadi, Oussama Ghorbel, Abdulfattah M Obeid, and Mohamed Abid. Outlier detection approaches for wireless sensor networks: survey. Computer Networks, 129:319-333, 2017.
[2] Gilad Baruch, Moran Baruch, and Yoav Goldberg. little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, 32, 2019.
[3] Peva Blanchard, El Mahdi EI Mhamdi, Rachid Guerraoui. and Julien Stainer. Machine learn- ing with adversaries: Byzantine tolerant gradient descent. Advances in neural information processing systems, 30, 2017.
[4] Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing markov chain on a graph. SIAM review, (6(4))667-689, 2004.
[5] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, 52(6):2588-2530 2006.
[6] Keyan Cao, Yefan Liu, Gongjie Meng. and Qimeng Sun. An overview on edge computing research. IEEE access, 8:85714-85728, 2020.
[7] Mingzhe Chen, Deniz Gündüz, Kaibin Huang. Walid Saad. Mchdi Bennis, Aneta Vulgarakis Feljan, and H Vincent Poor. Distributed learning in wireless networks: Recent progress and future challenges. IEEE Journal on Selected Areas in Communications, 39(12):35993365, 2021.
[8] Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1255, 2017.
[9] Alessandro Chiuso, Fabio Fagnani, Luca Schenato, and Sandro Zampieri. Gossip algorithms for distributed ranking. In Proceedings of the 201 American Control Conference, pages 1468-5473. IEEE, 2011.
[10] Igor Colin, Aurélien Bellet, Joseph Salmon, and Stéphan Clémençon. Extending gossip algorithms to distributed estimation of u-statistics. Advances in Neural Information Processing Systems, 28, 2015.
[11] Igor Colin, Aurélien Bellet, Joseph Salmon, and Stéphan Clémençon. Gossip dual averaging for decentralized optimization of pairwise functions. In International conference on machine learning, pages 1388-1396. PMLR, 2016.
[12] Reinhard Diestel. Graph Theory, volume 173. Graduate Texts in Mathematics, Springer, 2025.
[13] John C Duchi, Alekh Agarwal, and Martin J Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic control, 57(3):592-666. 2011.
[14] Jiashi Feng, Huan Xu, and Shie Mannor. Distributed robust learning. arXiv preprint 100v55440. 2014.
[15] Michael B Greenwald and Sanjeev Khanna. Power-conserving computation of order-statistics over sensor networks. In Proceedings of the twenty-third ACM symposium on Principles of database systems, pages 275-285, 2004.
[16] Bernhard Haeupler, Jeet Mohapatra, and Hsin-Hao Su. Optimal gossip algorithms for exact and approximate quantile computations. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 179-188, 2018

---

[17] Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Byzantine-robut decentralized learning via clippedgossip. arXiv preprint arXiv:2202.01545, 2022.
[18] István Hegedūs, Gábor Danner, and Márk Jelasity, Decentralized learning works: An empirical comparison of gossip learning and federated learning. Journal of Parallel and Distributed Computing, 148:1094 48:1109-124, 2021.
[19] Peter J Huber. Robust estimation a location parameter. In Breakthroughs in statistics: Methodology and distribution, pages 492-518. Springer, 1992.
[20] Peter Huber and Elvezio M Ronchetti. Robust statistics. John Wiley & Sons, 2011.
[21] Jaroslay Häjek and Zbyněk Šidák. Theory of Rank Tests. Probability and Mathematical Statistics. Academic Press, San Diego, second edition edition, 1999.
[22] Hamid Jalalzai, Stephan Clémençon, and Anne Sabourin. On binary classification in extreme regions. Advances in Neural Information Processing Systems, 31, 2018.
[23] David Kempe, Alin Dobra, and Johannes Gehrke Gossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. pages 482-491. IEEE, 2003.
[24] Maurice G Kendall. The treatment of ties in ranking problems. Biometrika, 33(3):239-251, 1945.
[25] Anastasia Koloskova, Sehastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International conference machine learning, pages 3478-3487. PMLR, 2019.
[26] Priyanka Mary Mammen. Federated learning: Opportunities and challenges. arXiv preprint arXiv:2101.05428, 2021.
[27] Bojan Mohar, Y Alavi, G Chartrand, and Ortrud Oellermann. The laplacian spectrum of graphs. Graph theory, combinatorics, and applications, 2(871-898):1,, 1991.
[28] Karl Mosler. Depth statistics. Robustness and complex data structures: Festschrift in Honour of Ursula Gather, pages 17-34, 2013.
[29] Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IEEE Transactions on Signal Processing, 70:1142-1154, 2022.
[30] Helmut Rieder. Qualitative robustmess of rank tests. Ann. Statist., 10(1):205 211, 1982.
[31] Robert J Serfling. Approximation theorems of mathematical statistics. John Wiley & Sons, 2009.
[32] Devavrat Shah et al. Gossip algorithms. Foundations and Trends@ in Networking, 3(1):1-125, 2009.
[33] Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri. Medians and beyond: new aggregation techniques for sensor networks. In Proceedings of the 2nd international conference Embedded networked sensor systems, pages 239-249, 2004.
[34] Aad W. Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[35] Anna Van Elst, Igor Colin, and Stephan Clémençon. Asynchronous gossip algorithms for rank-based statistical methods. To appear in International Conference on Federated Learning Technologies and Applications (FLTA), 2025.
[36] Esther Vodrir-Ro María Arostegi Pérez, Ana Torre-Bastida, Cristina Regueiro Senderos, and Juan López-de Armentia. Edge intelligence secure frameworks: Current state and future challenges. Computers & Security, 130: 103:703 2023.
[37] Sissi Xiaoxiao Wu, Hoi-To Wai, Lin Li, and Anna Seaglione. review of distributed algorithms for principal component analysis. Proceedings of the IEEE, 106(8):1321-1333 -3400 2018.
12

---

[38] Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-77, 2004.
[39] Dong Yin, Yudong Chen, Ramchandran Kanman, and Peter Bartlett. Byzantine-robus' distributed learning: Towards optimal statistical rates. In International conference machine learning, pages 6650-5659. Pmlr, 2018.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly state the contributions in the abstract and introduction: two new gossip algorithms with corresponding convergence rate bounds, as well as numerical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We address the limitations in the Conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code and data available in anonymous Github.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.co. ccippi.cc/pulli///gr. guwdes/ddeeeee CooeeSumeeeeeeeeeeeeee ssi onyolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: We provide most details of the experiments in the subsections Numerical Experiments and the rest of the details is available the Supplementary Material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We compute the mean error and standard deviation over all the runs. The variability comes from the edge sampling process and the distribution of the data over the graph.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

single CPU for few of The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: As mentioned the paper and detailed in the Supplementary Material, the experiments are not computationally intensive and hours.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The paper's contribution methodological nature and regarding the experi- ments, we use either synthetic data or publicly available data with no sensitive information.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our paper mostly theoretical but our introduction mentions the positive impact of decentralized and robust learning, regarding trustworthiness and frugality.
17

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
18

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurips hett::///earrrpsscc//oooerreeeee cc///oofeeeeeecs//22/////.. for what should or should not be described.
20

---

Outline of the Supplementary Material
The Supplementary Material is organized as follows. Section A introduces two alternative gossip algorithms for distributed ranking: Baseline and Baseline++. In Section B, we present auxiliary results related to gossip matrices and the convergence analysis of the standard gossip algorithm for averaging. The detailed convergence analysis of GORANK, including the proofs of Theorems and 2, provided in Section C. Section presents the convergence proofs for GOTRIM, specifically Lemma 1 and Theorem 3. In Section E, provide the robustness analysis of GOTRIM (i.e., the proof of Theorem 4). The convergence analysis of ClippedGossip is covered in Section F. Section G includes additional experiments and implementation details. Section H introduces Asynchronous GORANK, along with corresponding experimental results. Section details experiments on larger networks. Section J describes how the current framework can be extended include network disruptions. Section K provides experiments on sparse networks. Finally, Section I. offers further discussion and outlines future work.
A Gossip Algorithms for Ranking
Here, we detail two gossip algorithms for ranking, which can be considered natural competitors to GORANK. The algorithm presented first was proposed in [ and, to our knowledge, the only decentralized ranking algorithm documented in the literature. The algorithm presented next can be seen as a variant of the latter, incorporating the more efficient communication scheme of GORANK.
A.1 Baseline: Algorithm from Chiuso al.
Chiuso et al. propose a gossip algorithm for distributed ranking in a general (connected) network [9]. They demonstrate that this algorithm solves the ranking problem almost surely in finite time. However, they do not provide any convergence rate or non-asymplotic convergence results, The algorithm is outlined in Algorithm 3 and proceeds as follows, At each time step t, edge (i,j) is selected, and the algorithm operates in three phases:
1. Ranking:
The nodes check if both their local and auxiliary ranks are consistent with the corresponding local and auxiliary observations. If the ranks are inconsistent, the nodes exchange their local and auxiliary rank.
2. Propagation: The nodes swap all their auxiliary variables.
3. Local update: Each of the two nodes verifies if the auxiliary node has the same ID. If so, it updates its local rank estimate based on the auxiliary rank estimate.
Algorithm 3 Algorithm from Chiuso et al. (Baseline)
1: Require: Each node with id 4 & holds observation X
2: Init: Each node initializes its ranking estimate R2 <- and its auxiliary variables RY +
Re. Xg X2 and I < It.
3: for t = 1,2,.... do
4: Draw (i, uniformly at random from E.
5: if (X; - X,) -R, R2) < then
6: Swap rankings of nodes and j: R. Rg.
7:
end if
8:
if (X,
(R) R2) then Swap rankings of nodes and j: R + Ry.
9:
end if
11:
Swap auxiliary variables of nodes i and j: 1 ++ 17, R2 + R2 and X + Xy.
12:
for p { do
-- = then Update local ranking estimate: Rp + Ry end if
14:
16:
end for
end for
18:
Output: Each node contains the estimate of the ranking.
21

---

A.2 Baseline++ Our Improved Variant Proposal
The algorithm selects an edge (i at each step, and the corresponding nodes check the auxiliary ranks are consistent with their auxiliary observations. If the ordering is inconsistent, the nodes swap their auxiliary ranks. Then, each node updates local rank the ordering of local observation inconsistent with the auxiliary observation. In contrast, the algorithm proposed by Chhuuo et al. only updates the local estimates when the wandering estimate returns to its originating node. This design can significantly slow down convergence in graphs with low connectivity and long return times.
Algorithm 4 Baselinc++
1: Init: For all k, Rs k, Ry l and X3 Xs.
2: for t = 2, do uniformly random.
3: Draw (i,
4: if (X; - X3) (14 R2) < 0 then
5:
Swap rankings: R + Ryz.
6: end if
7:
for p E {i,j} do
8:
(X, xp) RR₂ Rp) 0 or X
X₂ then
9: Update local rank: Rp - R.
10: end if
end for
12: Swap: R2 ++ R2 and X + Xz..
end for
14:
Output: Estimate of ranks Rg.
B Auxiliary Results
In this section, we present key properties of the transition matrices that will be essential for the proof's of our main theorems. We also present the standard gossip algorithm for mean estimation, along with its convergence results.
B.1 Properties of Gossip Matrices
Lemma (B.1). Assume the graph EV, connected and non-bipartite. Let > O. If at iteration i, edge (i, is selected with probability [ET then the transition matrices are given by
Wi(t) In (c: -c) (c; c2)
(swapping matrix)
1
W2(1) = In (e: e,) (e: ej) (averaging matrix)
(5)
For [1,2), denote W (. = In (e: e,) (e: - ee,)
The following properties hold:
(a) The matrices are symmetric and doubly stochastic, meaning that
W.(1),, In, ([))() =
(b) The matrices satisfy the following equalities:
22(1)² W2(1), W1(1)² In-
(c) For (1,2), have
W. = E E. = I,
L
(6)
E
(d) The matrix W a also doubly stochastic and follows that 1, is an eigenvector with eigenvalue I.
22

---

(e) The matrix W. A Wa 1,12 that aaal I >2(a), where >²(0) is the second largest eigenvalue of W and llop denotes the operator norm of a matrix.
satisfies, by construction, W1, and it can be shown
n
(f) The eigenvalue >2(a) satisfies 0 I >2(a) < 1 and X2(a) = 11 a/ where X2 the spectral gap (or second smallest eigenvalue) of the Laplacian.
Proof. The proofs of (a), (b), (d), and (e) are omitted for brevity, For more details, we refer the reader to TO]. The proof of (c) follows from the fact that
E W (t) = E
Σ (i,))E
I
(c, -0) (c)))
and from the definition of the Laplacian matrix L Σ (B,eE (e: -e) -e;) The proof of (f) can be found in 1T0 (see Lemmas and 3).
B.2 Convergence Analysis of Gossip for Averaging
In the following section, we present classical results on the gossip algorithm for averaging.
Algorithm 5 Gossip algorithm for estimating the standard average [5]
1: Each node & initializes its estimate as Z Xg.
2: for t = 1, 2....... do
3: Randomly select an edge (i,j) from the network.
4: Update estimates: Z4 Zz & 2,+2,
5:
end for
Lemma (B.2), Let us assume that = (V, E) is connected and non bipartite. Then, for Z(t) defined in Algorithm 5 we have that for all k E [m]:
lim E [Za(()) = =x, t++00
Moreover, for any t >> 0,
EZ((t] X,1,,| 50-02 1000 | X,11111
where = 1 - 12) > O, with (2) =
Aa 2
Proof.
The proof is kept brief, this is standard result. For more details, we refer the reader to To prove this lemma, we will primarily use points (e) and (f) from Appendix B.I
10
Let t > 0. Recursively, we have E[Z(t)] W where W2 I, 2 L.
Denote W₂ A W2
I, n
Noticing that 1, X 1,1,, and that W W 1,
have
[|Z(()] X, 1, [
Since 1, W2 0, it follows that
[[]Z(t)] X, 1, s (A2(2)) || -,,1,,1||
Setting 0o = (2) finishes the proof, (2 1.
Lemma (B.3). Let assume that (V.E) is connected and non bipartite. Then, for Z(t) defined in Algorithm 5 we have that for any > 0:
cut
(([
X,, 1, 2 8,1,,1)
22
where =1 -22(2) > O, with 22 = 1 Aa
2
23

---

Proof. The original proof can be found in [
Let O and >> O. At iteration
have Z(() (2(1)Z((-1)) Denoting Y(I) Z(1) X,, In.
follows that (t) = (2 - 1). Taking the conditional expectation, we get
(( T (() ( 1)] Y( - E(Wa((( (2( (W (1 1)l1? B|W (t) (t) = (2)) 2
By repeatedly conditioning, we obtain the bound
(Y Y(t) & A2(2)
Finally,
(( X, ( x, = (())(())
2
X,I,1 22
(7)
$ 2
(
Y()))
(8)
Y())2
(2)
(9)
6²
Remark. Using the Cauchy-Schwarz inequality YII| S v E Y 1
we can also derive
(va(22
((] - -,,1, 2 E Z X,1nIl) 2
Setting C2 1- A2(2) finishes the proof, as 0 (2 <1.
C Convergence Analysis of GORANK
In this section, we will prove Theorem and 2.
C.1 Proof of Theorem 1
Theorem 1. Let R(t) be defined in GoRank. have that for all E [n]
lim +000
[R) rk-
(10)
Moreover. for any O,
E [[) rk S ok.
(11)
where e = A2 with X2 being the second smallest eigenvalue of the graph Laplacian (spectral gap), [
and o = nă (m==1), with 7n (x(x) / /nx(1 x).
Proof. prove Theorem 1, we will primarily use points (e) and (f) from Appendix B.
Let E [m]. L > 0, and h = Ih 1,, From the previous derivation, one has:
E E (1)
Σ h Wiex.
(12)
Denote W, A W, I.II Noticing that h 1.11 e = h and that W = W
1.1. for
0 5 have
E E - hal <
h Wie.l
(13)
==0
Since 1, W, = 0, it follows that
h Wiew 1 (Ae(1)))
||b haln
24

---

Thus,
E (+) - hug S Σ (22(1))* [he h S 1 >2(1) V /nhg(11 hs). (14)
1
since (1 < 1 and hy - h,1,
v ( - h₂)2. Using - X2(1) = da
where Ag is
[8]
the second smallest eigenvalue of the graph Laplacian, it follows that
Fl 3n (he),
EE R (t) hgl - 8 X2
(15)
where (x) = / 1/12(1 - z). Plugging E[Rx(t) = nLE R (t) + 1 and n4 = nhy + 1 finishes the proof:
E
rk
[E] r - i A2
nōn
(16)
71
C.2 Proof of Theorem
We now present convergence result for the expected gap, which is key to proving the convergence of GOTRIM.
Theorem 2 (Expected Gap). Let all ls E [n], and let c and og be as defined in Theorem 1 Then, for all t 2 L, we have: (t) rxl? z (3/ct) of Consequently.
RR (t) - rkll
ok
Proof. The proof relies on the Cauchy-Schwarz inequality:
(t) rxll S (t)(R((t)-ra)
Thus, to prove Theorem
convergence result for the variance term E [R&a()) (0)((tt)r)) -ra)² equiva-
lently EE (R& Tu))
is required. This result is formalized in the following lemma.
Lemma (C.1). We have
E (Ra(t)- r
3
o
where the constants are defined in Theorem 1.
Proof. Lett > and let & E [n]. Using the update rule in GoRank, the estimated rank R2(t) of agent k at iteration can be expressed as follows:
(1)
Σ
Σ he (i:s) ek.
(17)
where for any S 11 W 8: W(s) ... W(1) and W(O:)
For any 2 1, let us define Wt(t) as Wi( W1( 1axn Note that Wi(t) are real symmetric matrices and that 1, is always an eigenvector of such matrices. Therefore, for any 0 I s < 1, one has: (s(s) (s(s)) 1axe Using this decomposition in 17 yields
(1((1)
Σ ha heln) W.T.TT (s :)ex
since h4 hī Iaxe n
ex and 1, (T), 0. The squared gap can thus be expressed as follows:
1-1
(R)(1) Tva)
hbs Tu 1n) W (s:) Tex - 1.1 TW (ex)
==0
25

---

or equivalently,
(R2()) - Txx)²
Σ
(hx kg (i(()))) (s:))<
e - 1m11)) T (u:) ex
82
s<u
1
hh hgln) T (u:):) ex - hgln) W (u:) ex
+
1
ex. Denoting hg his hgln define vss) = hig (s) Tex. We first consider the second term:
17 + ou)) P. Note that
r(u)2 = h Wi (w:) exe, W1 Ww:
Let J = 1 Since h J = 0, we can simplify:
uuu)² = h2 W, (u:) e (i(w:)he s h2 Wi())) (w:),
Since the product of two identical permutation matrices is equal to the identity matrix, we obtain W (u:) W (w:) = In and conclude that B[o(u)²] < || Now let's consider the first term: 3 Exen (6))((u). Note that for < u,
c(s)u(u) = h (i(s: exee e Wi + (
Taking expectation conditional on W (s:), we have
B(u(s)v(u) W (s:)] = h W (s:) e B W (w:s + +1] (s:ss)
Since E, Wi(sus + 1)] = WT we obtain the following bound:
((u(s)u(u) W < A2(1) h Wi (s:) W hs
Using the previous derivation, we get:
Elu(s)v(u) S (2(1)== | 12
Combining the two terms, we obtain:
(R((t)) - hu) 1
+ tz
Σ d2()am
||ا 12
s<u
Note that:
Σ (a(11)= <
5 1 22
t
SCu
1=00== d=1
Recalling = -1)
1 +
2
3 |
E
(R) hw)) 1
h 11
Plugging [ a. (hx)² and using (t) hx)
}
(R (t) =] finish the proof. h
D Convergence Proofs for GOTRIM
In this section, we will prove Lemma 1 and Theorem
D.I Proof of Lemma
Lemma 1. Let R(I) and ( be defined as in Algorithm 7 and Algorithm 2 respectively. For all k E [n] and 1 0, we have:
3
o
E WW Wn.o (rw)) S ct 7/
(18)
2a)
where 7ik = min((ra - al |rk bl) 2 1 with = [am] + and b n aon + 2 being the endpoints of interval In.a. The constants and x.)-) as defined in Theorem
26

---

7kk Tk: Proof of Lemma 1. Let & E [n] and t >> 0. Denoting PA (t) (() = (()x(t) E In,a).
we have E & (t) = pa(t) where Cn,ax = 2mn with m = |an].
Hence, we need to show, for " > 0:
(())((t) E In.a) - [(rvEnn.)) | {P(()) - TM 78) 1
(19)
ct
The right-hand side of the inequality follows directly from Lemma C.1 via an application of Markov's inequality:
E8 (t rxl1
P R& (t) TA 2 Tuc = (() TM rel S
For the left-hand side, we introduce the interval In,a = (a, b] and define
min(b Tke Tk a)), if a S Th S b,
r3 a, rk >
7' b,
Observe that Yt 2 1/ since ra is always discrete. We now analyze the three different cases.
Case 1: a S r4 I b. Then, (t) [(reer..u) = -1- pa (t) = P( (t))(()) & I,,a). Since we have (t) - rkl S mh) < PP (t) E In,a), follows that the probability can be upper-bounde bounded as (()x(t) $ In,a) S RR
rkl > 7k) I (t) rxl 2 7k).
Case 2: 7 < a. Here, (t) [ pt(() P(Ra(tt) I,,a). Since it holds that (t) rkl 7k) & (t) & In,a), obtain (())(t)) E In,a) I (((()((t)) ral 2 mk).
Case 3: T3 > b This case follows symmetrically from the previous one.
In all cases, we have (P(Re(t) E Jn,a)= (rreIn..)) S (1) rkl 2 7kk)
Finally, the result follows from F[)+((1) Ca.a
p&(() and Cn.a 2mm -1 20.
D.2 Proof of Theorem 3
Now, we will prove the convergence in expectation of the estimates of GOTRIM.
Theorem 3 (Convergence in Expectation of GoTrim), Let Ztt) be defined GoTrim, and assuming the ranking algorithm is GoRank, we have that for all la E [m]
lim 00
(1)]
Ta.
(20)
Moreover, for any t > T min {t ct > llgg(t)), we have
[E[ - 1a <
cl. + el 2lo((!)
K O X||,
c(1 2a.)
where K
and c, an and yn constants defined in Lemma 1.
Proof of Theorem 3. Recall that for t > 1, the expected estimates are characterized recursively as:
E Z
w wi+1-s Aw((s
(w))) o X.
(21)
Denote W₂ A W2 have have
I.1I and notice that W 2
W!
I.1. Denoting S(s) = Amr(s) ④ X, we
BIZ(1)
Σ
1,
1,
(())
S(s))
(22)
n
==1
27

---

Since Vi, (0) = 0, the first term can be rewritten as:
t Σ
1, S(s) = Σ - Σ S((s) 1n =
(1) Σ wx(() In
1
(23)
==1 n
where Aw;(s) (s) wi(s 1) with wi(s) E[Wi(s)]. This leads to the bound:
[t) 2a1n11 S ( (t)xx))) 1n - Ialn + ||((t)]]
(24)
The first term simplifies as:
1
1
E (WW(()) (n)a(ri)) X;
.vn -
[[], - Wn. (ra)) |X,
(25)
n
vn
1
C
<
|X,
(26)
S 7
|c
(27)
2
where C; =
(1- comes from Lemma and we denote C = [C,,..., C..] To bound R(t),
20)
we decompose using an intermediate time step
log(t) 02 0, where 0o A2(2) 0.
Let T min {t c2t > log(t)}. We obtain for all t > T"
T
R(1)
W S(s)
W
w
2
8=1
Using Lemma we derive for s > 1, Aw)(s)] S
2C,
We obtain |S(L)] - ||C & X|| and for
8 >>> 1,
x 4C 2
[S(s] S
S 8 5-1 | X||
(s - 1)2
Applying this bound and using 02 1 (2) yields:
R(t)] S (2)
Σ 12(2)==01((s)) + Σ SS(s)
8=T+1
2
2
|ooX| + T x2
|
1 (2)
2
2
+
|CoX|
c2t
c²t log(t)
Finally, we establish the following error bound:
[E|Z(0) - F. 1. S 1 I
4
2
|oo
C
+
|Co |
d
where c -222- This bound simplifies to
5
(t)) - Z. 1n1
5
+
ccoll
2lg((!)
o2 n
Moreover, we have ||C 3 x0| proof.
K
X
where K
which completes the
ca1
%
k=1
28

---

E Robustness Analysis: Breakdown Point of the Partial Trimmed Mean
Here, we prove provide a breakdown point analysis of GOTRIM and prove Theorem
Theorem 4 (Breakdown Point). Let > O and a E (0, 1). Denote m [om]. With probability at least 1 - 6, the r-breakdown point El (t) of the partial a-trimmmed mean at iteration & > T for any node satisfies
max (L (m=+ 1
((6) Vt 2
n
where T 1 log (+)) denote a propagation time with being the connectivity constant and ě := T/ max; [X,] denote a tolerance parameter. Moreover, we define K(ő)
Cm where Cy. =
v3n2/22 6((m- - 1)/n) with o u E (0,1)-+ vu(l-u).
Proof. Applying Lemma 1, we estimate the breakdown point while accounting for the uncertainty
in rank estimation, and combine it with Lemma 2 via union bound. Lemma 2 introduces I the number of iterations required for the mean to propagate and the maximum delay T corresponds to the smallest possible given by e B where B max; [x Setting ó complete the proof.
1 8 and 82
Lemma E.1 (Instant Breakdown Point). iteration I as the statistic defined as
Let 81 0. Denote (t) the breakdown point at
Wn.o (n.o(Pi())) (Ri(
12
Then, with probability at least 81.
max m +
61 Vi .0)
Oo
(t)
where we define m = [naa] and Cm 33 3/2 3033/220((mmmmm (0(mmm((mmm)))))m 1)/n). As - oc, note that = =1 + m m, which allows us recover the breakdown point of the a-trimmed mean.
We are interested in the observations X3 with rank S г S m (the outliers that should be excluded from the mean), where = |na]. Note that do not consider the data points with rank n m + $ Tx S n, as this case is symmetrical for determining the breakdown point.
Proof.
Let 1 < rx < and consider the probability pı.(l) of including X5 in the mean. This probability satisfies:
(t) - (3on(rk) (a (a- va-rx)vet (a-rx)
Cy
where = + is the left endpoint of the inclusion interval. The breakdown point can be interpreted as 2 where p the maximum rank required to "break" the mean and n is the sample size. To determine the maximum rk in [1, m| such that the probability of inclusion is lower than certain confidence parameter 6, we solve for rs:
Cm
(x(1) S (a -a- rat
S 8,
and obtain
- 8vell .0)
p max
Thus, with probability at least 6, the breakdown point is given by 8xx (1)
Lemma E.2 (Propagation Time). Let 82 > O be a confidence parameter and E > 0 tolerance parameter. We define Z(-) as the evolution of the standard mean estimate, initialized as Z(0) X. Additionally, we introduce a perturbed estimate, Z(-), which starts at 7(() =
Bej- At
iteration t, detect mistake of magnitude B, we correct it by injecting - BB leading to the update
29

---

(t) -- Z(t) Bej. Then, follows that, with probability at least 1 - for all 2 + for any node 2,
[z((3] < ((s) [()) S eB,
where T represents number of iterations required to correct a mistake with tolerance E > 0 and is with is the connectivity of the graph.
given by T log 502
Proof. iteration I, the perturbed estimate is (()) (z((:)Z(()) 2(1) + W2(1:) since
(()) W2(1: :) (0). Then, at iteration > I, we inject - B at node j which gives the following:
Z W2(s:)) [t) W2(t:)Be; Bey]- Thus, for any > t,
A (s) Z(s) ((s) W2 (2:(:) I..] Be, = W2(8) 1).
Following the proof in [5]. by repeatedly conditioning, obtain
((A (x) ( = (
Since
[ - and taking the expectation on both sides, we have
E (
($)
[s) S B2²
Finally, we derive
Z() ((s) 2 cB) = (() 2(s)lI2 B²)²
(28)
1
- B2
(s) A
(29)
22
(30)
e²
Let 02 > 0. We need to solve - < 6, which gives T = 4 log (1)) It follows that with
probability at least 1 82, for 2 t + T, for all nodes i,
[Z,(t) = ((s)) Z(s)]l S eB
Convergence Analysis of ClippedGossip
In this section, we show that ClippedGossip, in our pairwise setup with fixed clipping radius, ultimately converges to the corrupted mean. The following lemma describes the update rule of ClippedGossip through its transition matrix.
Lemma (Transition Matrix). Assume at iteration t, edge (t. E E is selected. Then, the update using ClippedGossip rule with constant clipping radius is given by xt+! Wt) where (() E Raxn denotes the transition malrix at iteration I which is given by
W I, -a Ligs
where Lij- := (e, - ee)(e, - -e₁)T is the elementary Laplacian associated with edge (i.j) and aty = min (1,T/ | 2²11 a constant that depends on the previous estimates. Moreover, we have (t) = I, 20l a11- L In the special case aij 1/2, the matrix reduces to the standard averaging and is projection matrix: W(t (t) (t)).
Proof. At iteration I, edge (i.j) E E is selected, the update rule is
1 [+ = of CLIP(2) 2I,T), atti= 24 + CLIP(2 - - r),
where the clipping operator is defined as CLIP 7) = min (1, /||==|] z. This update can be expressed in matrix form as r+1 Wt) It equals the identity matrix except for 2 block corresponding to nodes i and j. given by
1 at a
a 1 --
where
aty 2 min
1.
|
23)
30

---

Observe that L.j 2 and conclude.
The next lemma allows us to bound the coefficients ol of the transition matrix. Lemma (Lower Bound on Coefficient of the Transition Matrix). Let m = max (M.)EE || -xi1l- We have m I m and thus we derive
a S min
1, 10 x311
S1,
where a == muin(1,T/m)) with m = (..)E |00 x911-
Proof. Let m² (..)e | 2/ |l- We can show that m S m. After update, we have a! = - 0ky ) + axjar and x = - ang)ary + asyar Observe that the new estimates remain
within the convex hull of the original points. Since only xy and ag have changed, the next maximum distance is:
m
max
max ReLi.j Eyi,)
|0 - x lI. max KFi.)
||=] ablls max keii. |aa
2bll ||
27
Note: || z21l S m by definition. So we just need to show that the other terms smaller than m. For l: * j, recall s! = (1 Ozj ) asyz]. then we have
| - xIll = [[1 - any = + alaf =2)1 s (1 ams)m + asym = m,
by the triangle inequality. Similarly, we derive for h: + i.j. | =22l S m. Finally, since 1 - 20,3 < 1, we have
| 2/}l = 11 - 20,gg1 || 2991 < m.
Recursively, we have for all 1, m I m, which finishes the proof.
The next lemma shows that each iteration, the expected gap between the estimates and the corrupted mean will decrease.
Lemma (Contraction Bound). Let t. >> O. Define y x² Fln where I (1/n) Ei= xa is the initial average. We have the following bound:
3A2 ||
E|ll
3r 1
E
where B = =2a11 - a) with a = min(1, (1, T 1/m) 2 m = (a) 1 xfll and Xg denotes the spectral gap of the Laplacian.
Proof. Taking the conditional expectation over the sampling process, we have
( y y'1
(g') TE(((t) (() v'ly'.
Since y' 1 1, and is the eigenvector corresponding to the largest eigenvalue I of E [(t) y²).
TE))))(((L) ((I) v'ly' < A2
y'l) ||
Now from the first lemma, we have W (t) (()) = J, By Lij where By = 2nly (1 off)). We see
that B S B/ 1/2 where 8 21 a). Observing that E(W W(I) 1vo I, (1/| where we define the weighted Laplacian as
i'
Σ (ME)
Lyy.ig
Using the quadratic form of the weighted Laplacian:
x. T
L(w)x=
Σ
miglx(1) - x(1)²,
(K.))
31

---

derive 3L L' 3 (1/2)L, as 3 S 1/2 Using the Courant-Fischer Theorem, obtain:
3A - p' ///2, where o' denotes the second smallest eigenvalue of L' and X2 is the second smallest eigenvalue of the (unweighted) Laplacian L. We therefore obtain bound on the second largest eigenvalue of TE (t) (W)) y"]:
(t)
A2
AA
2 E
E
E
which finishes the proof.
Finally, the convergence of ClippedGossip estimates is established in the following proposition. Proposition (Convergence of ClippedGossip Estimates). For each node k,
lim (t((t) 7+000
Moreover, we huve
Biiaa* =1,,1?1 - 1
312
1| =1,
E
where I = (1/n) - 2 is the initial average, B = 2a(1 - a) with == min(I,7/m)) and
m maX(k. |0 - sf and x2 denotes the spectral gap of the Laplacian.
Proof. Using the previous lemma, recursively, we obtain
Elll> S (1
11
Recalling y = x² 31, finishes the proof.
G Additional Experiments and Implementation Details
This section provides additional experiments and more details the Basel Luftklima dataset well as compute resources.
G.1 Experiments Compute Resources
The experiments are run on single CPU with 32 GB of memory.
The execution time for each experiment less than 30 minutes (except for the large-scale experiments).
The details of few experiments are given in Table
Experiments
Execution Time
Figure
expl+exp2+exp3
30 min
Ranking (a)
exp4+expStexp6
5 min
Ranking (b)
exp7+exp&+exp9
15 min
Ranking (c)
exp10+exp10aaeexp100
50 min
Trimmed Mean (a)
expl1+exp12+exp13
15 min
Trimmed Mean (b)
expl4
5 min
Trimmed Mean (c)
expl54exp16+exp17
~ 5 min
Ranking (d)
Table 1: Execution times for all experiments
G.2 Basel Luftklima Dataset
The dataset contains temperature measurements from 99 Meteoblue sensors across the Basel region, recorded between April 14 and April 15, 2025. For each sensor, only the first observation used. graph is built by connecting sensors that are within 1 km of each other, based their geographic coordinates. Only the connected component of the graph kept. To avoid ties during ranking, we add small, imperceptible amount of noise to the data.
32

---

G.3
Additional Experiments
Figures
S
and extend the experiments presented in sections 3 and 4.
Absolute Error vs. Rank
Absolute Errer Rank
Absolute Error Rank
0.03
0.50
0.07
0.50
0.07
0.0
0.02
0.04
0.01
0.02
GoRank
GoRank
GoRark
0.00
0.00
0.00
0.00
0.00
0.00
125
250
375
500
125
250
375
500
125
250
375
500
(a) Complete Graph
(b) Sttts-Stroggtzz Graph
(c) 2D Grid Graph
Figure 4: Role of ø for three different communication graphs
Absolute Error Timesteps
Absolute Error vs. Timesteps
Absolute Error Timesteps
0.5
0.5
GoRank (ours)
GoRank (ours)
GoRank (ours)
0.4
Baseline (Chiuse
Raseline++ + tours]
0.4
Baseline+ tours)
Beseline (Chiuso et al.)
0.4
Baseline++ + (ours)
Basellie (Chiuso
0.3
0.3
0.0
0.0
0.0
2c4
404
604
806
2e4
4ed
6e1
0e4
204
406
624
804
(a) Complete Graph
(b) Watts-Strogatz Graph
(c) 2D Grid Graph
Figure 5: Comparison of ranking algorithms on three different communication graphs
Absolute Error Timesteps
Absolute Error vs. Timesteps
Absolute Error vs. Timesteps
400
Ge + Golla tours)
Gohhim + Golaank (pun)
330
G17im + Baselnce+ (oun))
350
G377mm Baselnee+ louns)
Clipped Gooile the el
Clipped Gooip die al
300
300
Error of the comupted mean
Enoro the comupted mean
250
200
150
150
100
100
4ec4
8ec
(a) Complete Graph
(b) Watts-Strogant Graph
(c) 2D Grid Graph
Figure 6: Comparison of gossip algorithms for robust mean estimation on three different graphs
H Asynchronous Variant of GORANK
In this section, we propose an asynchronous variant of GORANK that operates without access to a global clock or a shared iteration counter. Instead, each node & maintains local counter Ck which tracks the number of times has participated in an update. Asynchronous GORANK, outlined in Algorithm 6 proceeds as follows. When node lo is selected, it increments Cg and updates its local rank estimate using a running average, where the global iteration replaced by Ct. As in the synchronous version of GoRank, selected nodes also exchange their auxiliary observations. Note that this asynchronous version is more efficient, as it significantly reduces the number of podaaees-performing only two updates per iteration instead of n.
33

---

Algorithm 6 Asynchronous GoRank
1: Init: For each & E [n]] Ya + Xk, B2g - 0, C+ + 0.
2:
for 1,2, 1,2....0
3: Draw (i.j) E E uniformly at random.
4: for p E {i do
5: Set C. f Cp+11.
6: Set R 5 (1-1 + (1x
7: Update rank estimate: Rp t RR +1.
8: end for
9: Swap auxiliary observation: Y ++ Yj.
10:
end for
11: Output: Estimate of ranks Rg-
Figure 7 shows a comparison of Asynchronous GoRank with our two other ranking algorithms: Synchronous GoRank and Baseline++. The results suggest that Asynchronous GoRank converges slightly faster than Synchronous GoRank, thereby outperforming it in both speed and efficiency.
Absolute Error vs. Timesteps
Absolute Error Timesteps
Absolute Error vs. Timesteps
0.5
Baseline++ + lours)
Baseline+ (ours)
Baseline++ (ours)
GoRank Async (ours)
GoRank (ours)
0.4
GoRank (ours)
GoRank Asyne (ours)
GoRank (ours)
GoRank Async lours)
0.3
0.2
0.2
0.2
6.1
0.1
0.1
264
464
664
Bo4
(a) Complete Graph
(b) Watts-Strogatz Graph
(c) 2D Grid Graph
Figure 7: Comparison of Asynchronous GoRank with other ranking algorithms. Results show that Asynchronous GoRank slightly converges faster than the synchronous version.
Note that the convergence analysis in the asynchronous case is more complex because it requires analyzing the ratio of two statistics. Nonetheless, though technically more demanding, it is possible to derive convergence rate bounds using Taylor expansions techniques. We will carry out such an analysis in an extension to this work.
I Large-scale Experiments
To demonstrate the scalability of our method on large networks, repeated the experiments from Fig. (c) in Sections 3.2 and 4.3, originally conducted with n = 500, on larger networks with n = 1000 and 5000.
For the experiments related to Section 3.2, the results lead to the same conclusions: Figure shows that GoRank continues to achieve low error (< 0.1), and the overall performance trends of the other ranking algorithms remain similar on the Watts-Strogatz graph but are significantly worse on the 2D grid graph. These additional results further reinforce GoRank's scalability and robustness, particularly in comparison to the other methods.
For the experiments related to Section 5.4, Figure 9 shows that GoTrim + GoRank continues to converge efficiently to the trimmed mean, even on larger 2D grid graphs, clearly outperforming the corrupted mean. In contrast, GoTrim + Baseline++ converges significantly more slowly on the grid (and does not even outperform the corrupted mean), although remains efficient on Watts Patts-Strrogat graphs.
34

---

Absolute Error Timesteps
Absolute Error vs. Timesteps
Absolute Error vs. Timesteps
0.5
0.3
GoRank lours)
GoRaak (ours)
GoRank (ours)
0.4
Baseline++ [ours]
Basaline+ (ourg)
Baseline++ (ours)
Baseline (Chuss at al]
Baseline (Chiuso et al)
Baseline (Chiuso all
0.3
03-
0.2
0.2
0.1
0.0
0.0
2d4
5e4
Bo4
10c4
264
Delt
10s4
0
Bed
15e4
22e4
30e4
(a) Watts-Strogatz with
1000
(b) 2D grid with 1000
(c) 2D grid with n 5000
Figure 8: Comparison of the performance of gossip algorithms for ranking across large networks
Absolute Error vs. Timesteps
Absolute Error vs. Timesteps
Absolute Error vs. Timesteps
12000
10020
25000
10000
8000
Cullin in Cerlam DurO
0020
20000
Gofhin Gozani touns)
scselince CI Couup at
6000
Errr the compited mean
15000
corruptdd
0000
4000
2020
5000
8ad
204
5.6
10c4
Sed
10e4
15ed
20e4
(a) Watts-Strogatz with n = 1000
(b) 2D grid with n = 1000
(c) 2D grid with v = 5000
Figure Comparison of the performance for trimmed means estimation across large networks.
J Robustness to Network Disruptions
While robustness to data contamination is important, the robustness of our proposed algorithms to network disruptions (e.g., edge/node failures, network partitioning) is equally crucial in real-world applications.
One natural extension to introduce a fixed probability of failure for each node or edge (see [2]). This would modify the edge sampling: instead of uniform distribution, the algorithm would sample edge e with probability Pe- In our analysis, this change corresponds to replacing the normalized Laplacian L/ with weighted sum Ee PeLe. where Ee Pe < 1 due to edge failures and Le correspond to the elementary Laplacians. The spectral gap, which governs the convergence rate, would now correspond to the connectivity constant ē of this weighted Laplacian instead of c / For instance, if each edge fails independently with probability 0.5, then Pe = E/2 for all e, and the effective spectral gap becomes emphasize that as long as Pa > for all e, the weighted graph remains connected and non-bipartite the original graph was.
(2)(2 c, indicating slower convergence rate. We
Another interesting scenario is network partitioning. One way to model this is by designing graphs composed of tightly connected clusters with only a few inter-cluster edges that are prone to failure. In such a setup, the connectivity constant would degrade significantly, and we expect the convergence rate to reflect this bottleneck. We generated graph consisting of 500 nodes organized into three well-connected clusters, with only five inter-cluster edges. As expected, we observed a very low connectivity constant 1.86 x 10-6 and the convergence behavior of this graph is similar that of a 2D grid graph, which is consistent with the low overall connectivity.
K Experiments on Sparse Graphs
An interesting question is whether our algorithms performance well on sparse graphs. First, we note that the StrosaStrogatzz and 2D grid graphs used in our main experiments are already quite sparse, with both containing fewer than 1000 edges. However, we would like to emphasize that
35

---

what primarily governs convergence behavior is not sparsity per se, but graph connectivity. For example, a dense graph composed of loosely connected clusters may have poor connectivity, while a sparse graph like 3-regular graph can exhibit strong connectivity properties. A cycle graph, in addition to being sparse, has very low connectivity and serves as useful pathological case. To better illustrate the relationship between topology and performance, we conducted additional experiments
using three different sparse graphs: 1) Watts-Strogatz graph (connectivity = 3.31 x 10-4, 1000 edges), 2) Cycle graph (c 3.16 10-7, 499 edges), 3) 3-regular graph (c 2.24 x 10 750 edges). All experiments were run for 15 x 10* iterations. For GoRank, both the Watts- Strtos-ttrogtt and 3-regular graphs achieved fast convergence (absolute error below 0.05), consistent with their strong connectivity properties typical of expander graphs. The cycle graph, as expected, performed worse due to its very low connectivity, but still achieved an error below 0.1. For GoTrim, using the same corruption model as in Fig. 5b, the Watts-Strogatz and 3-regular graphs again performed very well, with errors close to O. However, the cycle graph exhibited much slower convergence: after 8 x 104 iterations, the absolute error remained above 40. Doubling the number of iterations reduced the error to below 40, While this is indeed slow, is important to note that performance remains better than the corrupted mean, and such a topology is highly atypical in real-world sensor networks. In practice, such scenarios would likely require gossip algorithms specifically designed for cycle graphs. These experiments support the conclusion that Gririm still performs well sparse graph with good connectivity properties.
Absolute vs. Timesteps
Absolute Error vs. Timestaps
Absolute Error vs. Timesteps
0.20
Expander
400
400
Goltmm fisellte- (our))
Goliin Banel
Watts
350
Clipaed Gands atail
350
Cipped Sceup abal
0.15
Cycle
300
Ertor the comupted mean
300
Emar the compreed mean
250
250
0.10
200
200
150
150
100
100
0.00
404
Boo
11.4
15.4
4e4
Sel
11e4
15e4
4e4
Sel
11e4
15e4
(a) GoRank on sparse graphs
(b) GoTrim on expander graph
(c) GoTrim on cycle graph
Figure 10: Comparison of the performance of GoRank and GoTrrm on different sparse graphs.
L Further Discussion and Future Work
Our main focus was to develop foundational results for robust decentralized estimation. This section highlights directions for deepening our understanding of the algorithms' properties, extending them to more complex settings, and applying them to related problems.
Optimality of the Bounds. To the best of our knowledge, there are currently no established lower bounds on the convergence rate for the class of gossip-based algorithms applied to either decentralized ranking or trimmed mean estimation. Thus, the optimality of our algorithms remains an open question. In the special case of a complete graph, we observe that significantly faster convergence than the typical (1/tt) rate is possible. For example, in the Baseline++ algorithm, which performs direct ranking swaps, we can show exponential convergence of the form exp(-1/\El). However, this fast convergence critically relies on the high connectivity of the complete graph and does not generalize well to less connected graphs. In contrast, GORANK demonstrates more robust performance across general graphs, including those with limited connectivity, where achieving (11/t) convergence is already non-trivial Deriving a formal lower bound for arbitrary graphs remains an open and challenging problem. Nevertheless, it can be noted that with the current approach, the GORANK convergence rate of O(1/t) is tight in the sense that rank estimation involves averaging t random indicator functions. Finally, since GOTRIM relies the rank estimates from GORANK, it inherits the (1/tt) convergence rate, which is already near-optimal.
Faster Gossip Algorithms. Designing faster gossip algorithms is an interesting direction, and we have also been exploring this aspect. One promising approach involves optimizing the edge sampling strategy based on the graph connectivity constant (see 4 38). While this strategy improves gossip
36

---

performance in standard averaging tasks, our empirical experiments suggest that its impact on the GORANK algorithm is more limited. This is likely due to the relatively small variation in c, which is insufficient to significantly affect rate in 1/cl-thoughe it has more noticeable effect under geometric rate.
Extension to Multivariate Data. Extending the proposed approach to multivariate data is an important direction. natural extension involves ranking multivariate observations based on their norms. Specifically, one could define suitable norm depending on the task (e.g.. Euclidean), compute the norm for each observation, and then apply our univariate ranking method (GoRank) to these one-dimensional values. Observations with the largest norms can then be treated potential outliers. Following this, a multivariate version of GoTrim can be defined by discarding the top k = [on observations with the largest norms, and computing the mean of the remaining points using the standard gossip algorithm. Alternatively, one could explore data depths as a generalization of ranking in multivariate settings (see (28). Data depth provides measure of centrality for multivariate data. While this approach is promising, it would require more in-depth investigation beyond the scope of the current work, since depth computations usually require solve computationally demanding optimization problems, just like alternative methods recently designed to define multivariate ranks (e-g- based optimal transport). Finally, we could simply compute the coordinate- trimmed mean by applying GoTrrm to each coordinate individually 22 39.
Applications. The proposed methods offer promising foundation for robust decentralized opti- mization. In particular, GOTRIM could be integrated into existing mean-based optimization algorithms enhance robustness against outliers [11 25 377. Realizing this integration, however, will require further algorithmic and theoretical development. Additionally, our ranking algorithms may prove valuable in extreme value theory, where identifying rare or extreme observations is critical especially in high- sigh-stakes domains such as finance, insurance, and environmental science [22].
critical-especially
37


Reviews:
[{"review_id": "eCcbAnv6lO", "reviewer": "Reviewer_VJLP", "summary": "The paper introduces two novel gossip algorithms designed for robust distributed estimation over arbitrary communication graphs: GORANK for rank estimation and GOTRIM for trimmed mean estimation. The authors demonstrate that GORANK provides efficient rank estimation with an $\\mathcal{O}(1/t)$ convergence rate, while GOTRIM achieves robust trimmed mean estimation with an $\\mathcal{O}(\\log(t)/t)$ convergence rate. Both algorithms are analyzed in terms of their theoretical convergence rates and breakdown point analysis, with empirical validation also provided. The proposed algorithms aim to improve the robustness of distributed learning in decentralized networks, particularly in the presence of corrupted or adversarial nodes.", "questions": "- Is there any comparison of GOTRIM with other trimmed mean estimation techniques (like those based on median or quantile estimations) in terms of both theoretical bounds and practical performance?\n- Though GORANK is quite intuitive, $t$ in Algorithm 1 Step 4 seems to be abused. I wonder if the weights of $R_k^{\\prime}$ and $\\mathbb{I}_{X_k > Y_k}$ is varying across different iterations?", "limitations": "See 'Weakness' part.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The proposed GORANK and GOTRIM algorithms extend gossip-based methods in a meaningful way by incorporating robust ranking and trimmed mean estimation. This is a significant contribution to decentralized, robust statistical estimation.\n- GOTRIM’s breakdown point analysis further demonstrates the robustness of the trimmed mean estimate even in the presence of corrupted data.\n- The experiments are extensive, covering different graph topologies and contamination schemes, and show that both algorithms outperform existing methods in terms of robustness to outliers and performance in poorly connected graphs.\n\nWeaknesses\n- The experiments conducted involve relatively small network sizes (e.g., 500 nodes), which may not fully represent the scalability of the proposed methods. The performance of the algorithms in larger networks or at scale has not been sufficiently tested.\n- The experiments assume that the network graph is connected and non-bipartite. However, in real-world applications, graphs might experience node failures, network partitioning, or other disruptions. It would be useful to see robustness tests under these conditions.\n- While the authors provide upper bounds for the convergence rates of GORANK and GOTRIM, there is no discussion on whether these rates are tight. The paper does not explore the possibility of faster gossip-based algorithms or variance reduction strategies that might improve the convergence rates.\n- Some parts of the paper are notation-heavy, and symbols like $\\sigma_{n}(r_{k}),  c_{n}(r_{k})$, and $\\gamma_{k}$ are introduced quickly without much surrounding context or intuition. Readers not deeply familiar with decentralized estimation literature may find it difficult to parse the implications of these quantities.\n- The paper provides upper bounds on the convergence rates of GORANK and GOTRIM but does not discuss whether these bounds are optimal or how they compare to known lower bounds in decentralized or robust estimation (if any). This leaves open the question of whether the proposed methods are theoretically optimal.", "was_revised": true, "final_justification": "I will keep my positive score for potential acceptance.", "rebuttal": "We thank the reviewer for their valuable feedback. Below, we address the weaknesses point by point: \n\n1. It is indeed important to demonstrate the scalability of our method on larger networks. The experiments from Fig (c) in Section 3.2 and 4.3 conducted with n=500 were also carried out with larger networks of sizes of $n = 1000$ (using $t = 10^5$ iterations) and $n = 5000$ (using $t = 3\\cdot 10^5$ iterations). Regarding the experiments related to Section 3.2, the results lead to the same conclusions: GoRank continues to achieve a low error (< 0.1), and the overall performance trends of the other ranking algorithms remain similar, although they are generally slower as the network size increases. These additional results further reinforce GoRank's scalability and robustness, particularly in comparison to the other methods. Regarding the experiments related to Section 5.4, we observed that GoTrim + GoRank continues to converge efficiently to the trimmed mean, even on larger 2D grid graphs. In contrast, GoTrim + Baseline++ converges significantly more slowly on the 2D grid, although it remains efficient on Watts-Strogatz graphs. These additional experiments will be included in the Supplementary Material of the revised version for the sake of completeness. Scalability issues on very large networks (e.g. $n>100 000$) are beyond the scope of this paper.\n\n2. The robustness of our proposed algorithms to network disruptions is indeed an important consideration in real-world applications. First, note that randomized gossip algorithms (our setup) are inherently more robust to node/edge failures than deterministic algorithms, since they operate by sampling a single edge at each iteration and do not require full connectivity at every step (see [1]). Moreover, since our synchronous setup requires all nodes to update at each iteration, node failures could be a problem. However this is easily solved with the asynchronous setup we proposed in the appendix, since in this setting, each node keeps a local counter and is not affected by a missing update. That said, we agree that explicitly incorporating failures into our framework would enhance its practical relevance. One natural extension is to introduce a fixed probability of failure for each node or edge (see [2]). This would modify the edge sampling: instead of a uniform distribution, the algorithm would sample edge $e$ with probability $p_e$. In our analysis, this change corresponds to replacing the normalized Laplacian $L/|E|$ with a weighted sum $\\sum_e p_e L_e$, where $\\sum_e p_e < 1$ due to edge failures and $L_e$ correspond to the elementary Laplacians. The spectral gap, which governs the convergence rate, would now correspond to the connectivity constant $\\tilde{c}$ of this weighted Laplacian instead of $c=\\lambda_2/|E|$. For instance, if each edge fails independently with probability 0.5, then $p_e = 1/2|E|$ for all $e$, and the effective spectral gap becomes $\\tilde{c} = \\lambda_2 / (2|E|) < c$, indicating a slower convergence rate. We emphasize that as long as $p_e > 0$ for all $e$, the weighted graph remains connected and non-bipartite if the original graph was.  Regarding network partitioning, this is indeed an interesting direction to explore. One way to model this is by designing graphs composed of tightly connected clusters with only a few inter-cluster edges that are prone to failure. In such a setup, the connectivity constant would degrade significantly, and we expect the convergence rate to reflect this bottleneck. We generated a graph consisting of 500 nodes organized into three well-connected clusters, with only five inter-cluster edges. As expected, we observed a very low connectivity constant $c = 1.86 \\times 10^{-6}$. Empirically, the convergence behavior of this graph is similar to that of a 2D grid graph, which is consistent with the low overall connectivity of the graph structure. The experiments mentioned will be included in the Supplementary Material in an additional section dedicated to robustness to topology changes.\n\n3. Regarding the tightness of the bounds, please see point 5 below. Designing faster gossip algorithms is indeed an interesting direction, and we have also been exploring this aspect. One promising approach involves optimizing the edge sampling strategy based on the graph connectivity constant $c$ (see [3]). While this strategy improves gossip performance in standard averaging tasks, our empirical experiments suggest that its impact on the GoRank algorithm is more limited. This is likely due to the relatively small variation in $c$, which is insufficient to significantly affect a rate in $1/ct$—though it has a more noticeable effect under a geometric rate. Regarding variance reduction strategies, we agree that they could potentially enhance convergence. However, the application of these techniques would require stronger assumptions and a more extensive theoretical framework. While these questions will be discussed in the final version of the article, providing answers to them is beyond the scope of the current paper.\n\n\n4. We agree that the notation in some parts of the paper could be simplified. The symbols $\\sigma_{n}(r_{k})$, $c_{n}(r_{k})$, and $\\gamma_{k}$ are constants that arise naturally in the derivation of our convergence bounds. Their expressions are somewhat complex, so we used simplified notation to keep the results readable. The dependence on $n$ and $r_k$ was included for completeness, but we understand it may add unnecessary complexity without providing much intuition. These constants are specific to our analysis and do not come from the standard decentralized estimation literature. In the revision, we will simplify the notation—for example, replacing $\\sigma_{n}(r_k)$ with $\\sigma_k$—to improve clarity. \n\n5. We agree that a discussion on the tightness of the convergence bounds would strengthen the theoretical presentation. To the best of our knowledge, there are currently no established lower bounds for the specific problems addressed in our work, the optimality of our algorithms remains an open question. For GoRank, the convergence rate of $O(1/t)$ is indeed tight in the sense that rank estimation involves averaging $t$ random indicator functions. As a result, the convergence is necessarily in $O(1/t)$. However, the constant $1/c$ is not tight in the bound due to the use of an upper bound of a finite geometric sum. This simplification was useful for obtaining interpretable expressions. For GoTrim, we noticed that the original bound was actually not optimal and included an unnecessary $\\log t$ term. Upon closer analysis, we realized that in the proof of Theorem 3, we used a crude bound of $\\sum_{s=T+1}^{t} \\lambda^{t-s} \\leq t - T$, leading to the $\\log t$ dependence. However, this term can be more tightly bounded by $1/c$, and we have updated the proof of Theorem 3 accordingly in the camera-ready version. Finally, since GoTrim relies on the rank estimates from GoRank, it inherits the $O(1/t)$ convergence rate, which is already near-optimal. While Boyd et al. have shown that gossip algorithms for averaging have optimal convergence rates (see [1]), this approach does not directly apply to our setting due to the different nature of the problem. We agree that deriving formal general lower bounds is an important question and this will be the subject of further research.\n\n\nWe now respond to the two questions raised:\n\n1. To the best of our knowledge, there are no existing quantile or median estimation methods that are directly applicable to our setting---specifically, a randomized pairwise gossip framework operating over arbitrary graph topologies. That said, our GoRank algorithm can be adapted for median estimation by propagating the observation whose current rank estimate is close enough to the rank of the median and most recent. \nWe have also explored gossip-based algorithms that use a median update rule. One variant we tested involves using three neighboring nodes and updating their estimate to the median of the three values. Another variant maintains a \"wandering observation\" $Y_k$ for each node $k$, and upon communication between nodes $i$ and $j$, updates $Z_i$ and $Z_j$ using the median of $(Z_i, Y_i, Y_j)$ and $(Z_j, Y_j, Y_i)$ respectively, while swapping $Y_i$ and $Y_j$. Despite converging to a consensus, these algorithms had a strong bias and did not converge to the true median on average in our empirical evaluations. \n\n2. You are correct that the weights do vary across iterations, and we realize this may not have been sufficiently clear in the original version. In Algorithm 1, the variable $t$ denotes the current iteration counter. For example, at $t = 1$, the weight on $R_k^{\\prime}$ is $w_1 = 0$ and the weight on $\\mathbb{I}_{X_k > Y_k}$ is $w_2 = 1$; at $t = 2$, we have $w_1 = \\frac{1}{2}$ and $w_2 = \\frac{1}{2}$; and so on. This effectively performs a running average. We emphasize that this implementation assumes a \\emph{synchronous} setting, where all nodes share the same iteration counter $t$. For the \\emph{asynchronous} case (as discussed in the Appendix), $t$ can be replaced by a local counter $c_k(t)$ for each node $k$. To avoid confusion between $t$ as an iteration counter and $t$ as a time horizon, we now use $s$ in Algorithms 1 and 2 to denote the iteration counter.\n\nWe hope this response has fully addressed your questions and concerns. Please let us know if there is anything else you would like clarified, or any additional information you would need.\n\n[1] Boyd, Stephen, et al. \"Randomized gossip algorithms.\" IEEE transactions on information theory 52.6 (2006).\n\n[2] Haeupler, Bernhard, Jeet Mohapatra, and Hsin-Hao Su. \"Optimal gossip algorithms for exact and approximate quantile computations.\" Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (2018).\n\n[3] Boyd, Stephen, Persi Diaconis, and Lin Xiao. \"Fastest mixing Markov chain on a graph.\" SIAM review 46.4 (2004)."}, {"review_id": "LPRCObZTM5", "reviewer": "Reviewer_eSuy", "summary": "The paper introduces two decentralized gossip algorithms designed to robustly estimate ranks and trimmed means in networks with corrupted or malicious nodes. The authors provide a theoretical convergence analysis for both methods, which is insightful, and experiments validating the theoretical results on diverse network topologies and data contamination scenarios.", "questions": "- Can you give a more clear motivation on why rank estimation, and trimmed mean estimation in the gossip setting is practically relevant. Including why it's important over the whole graph as opposed to taken locally for each neighborhood of a node?\n- Does the method extend to random-edge gossip (sampling one edge at a time)? This would be a pragmatic way to go towards asynchronous?\n- Currently some clarity is missing on Byzantine vs weaker notions of robustness. In the discussion of He et all ClippedGossip, is it fair to me to use fixed clipping radius? Could you clarify the high-level results comparison of types of robustness (Byzantine vs just robust) achieved/not achieved.", "limitations": "See above", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- Novelty of extension, and solid mathematical formulation of the problems. \n- Breakdown point analysis is insightful\n\nWeaknesses:\n- The comparison to Byzantine robustness is left unclear. What exactly is the threat model? (Discussing practical relevance also)", "was_revised": true, "final_justification": "I'm fine with either outcome on this paper. The rebuttal clarified minor aspects so I'm not having major concerns remaining. The real-world example they provided is only half convincing though: the method does not give privacy guarantees, and if that's the case then centralized methods are applicable as well and scale rather well as we're exchanging scalars only, not LLM-sized model parameters", "rebuttal": "We thank the reviewer for their valuable feedback. Below, we respond to the four questions raised:\n\n1. In this work, we adopt the model of honest nodes with corrupted data, following Huber's contamination model, in which a fraction of the data consists of outliers. The nodes perform updates correctly and consistently based on their local observations but their local observation could be an outlier. This distinguishes our setting from the Byzantine model, where nodes may behave arbitrarily or maliciously, potentially sending incorrect updates with the intent to disrupt consensus or degrade performance. To clarify this distinction, we propose to add the following remark in Section 2.1 explicitly comparing Huber robustness with Byzantine robustness: \n\n\"Remark 2. Our setup assumes honest nodes, meaning they perform updates correctly and consistently based on their local observations. However, under Huber’s contamination model, these observations may include outliers. Note that this setup is fundamentally different from the Byzantine model where nodes may behave arbitrarily or maliciously, potentially sending incorrect updates with the intent to disrupt consensus or degrade performance.\"\n\nWe underline that our model is still realistic in many practical settings: a sensor could be miscalibrated, stuck at a fixed value, or may consistently report incorrect readings due to environmental factors, without necessarily being attacked. Although less challenging, Huber robustness is still an important problem that needed to be addressed.  \n\n2. We clarify the motivation as follows:\n\na) Rank estimation over the whole graph is crucial because it provides a measure of how extreme a particular value is in a global context. A node that is a global outlier may appear normal when compared only to its immediate neighbors, particularly if those neighbors are also outliers. In gossip-based algorithms, where values propagate across the network, even a single undetected extreme value can significantly skew global statistics such as the mean. Therefore, identifying and quantifying outliers requires comparisons across the entire graph, not just local neighborhoods.\n\nb) Trimmed mean estimation likewise requires a global perspective. A locally computed trimmed mean (e.g., using values from a node’s neighborhood) may still be biased or corrupted if a majority of neighboring nodes are outliers. For such an algorithm to be reliable, we would need strong assumptions about each node’s neighborhood, which is often unrealistic, particularly in poorly connected graphs. We have explored deterministic gossip algorithms that use the median rule as the aggregator, meaning that at each iteration, each node computes the median of its neighbors. While this approach does converge to a consensus, our experiments showed that it is biased (especially when the graph is sparse/poorly connected) and does not converge to the true median. \n\nOverall, both rank and trimmed mean are inherently global statistics—unlike local aggregates such as averages, minima, or maxima, which can rely on local conservation principles to ensure convergence to the correct global values. No such local conservation principle exists for ranks or trimmed means, which justifies the need for our proposed approach.\n\n3. Yes, our method does indeed extend naturally to a fully asynchronous setting, where only two nodes (one edge) update at each iteration. We addressed this extension (see Appendix H), where we introduce an asynchronous version of GoRank. In this variant, each node maintains a local counter $C_k$ that tracks the number of updates it has participated in, replacing the use of a global iteration counter $t$. The update rule becomes $(1 - \\frac{1}{C_k}) R_k' + \\frac{1}{C_k} \\mathbb{I}_{X_k > Y_k}$. Empirically, we observed that Asynchronous GoRank converges slightly faster than its synchronous counterpart, and is more efficient. Furthermore, note that GoTrim inherits the asynchronous nature of GoRank when used in this setting. Since this is an interesting extension, we have added the following remark in section 3.1 discussing it in detail:\n\n\"Remark 3. The asynchronous extension of GoRank is straightforward: it replaces the global iteration counter $t$ with a local counter $C_k$ maintained at each node $k$. The update rule then becomes $(1 - \\frac{1}{C_k}) R_k' + \\frac{1}{C_k} \\mathbb{I}_{X_k > Y_k}.$ Empirically, we find that Asynchronous GoRank converges slightly faster and is more efficient than its synchronous counterpart (see Appendix H).\"\n\nHowever, in this paper, we focus primarily on the synchronous setting to simplify the theoretical analysis. The asynchronous case is more complex because it requires analyzing the ratio of two statistics. Nonetheless, though technically more demanding, it is possible to derive convergence rate bounds using Taylor expansions techniques. We have carried out such an analysis in an extension to this work. For completeness, we may refer to it.\n\n4. Please see our response to Question 1 for a more detailed discussion of the distinction between Byzantine robustness and weaker notions of robustness.\nRegarding the use of a fixed clipping radius in our analysis of ClippedGossip: yes, it is fair to use a fixed clipping radius, as this is consistent with the experimental setup in He et al.’s original work. Although He et al. mention an adaptive clipping mechanism, its applicability to a randomized pairwise gossip setting is unclear. Specifically, adaptive clipping typically relies on statistics computed over neighbors' data, which may not be readily available in a pairwise setting. Moreover, such a scheme appears to require a well-connected network topology and introduces an additional hyperparameter, which limits its practicality in our setup. As noted in our response to Question 1, this work specifically focuses on robustness to data corruption under the assumption that all nodes are honest. In contrast, Byzantine robustness is a fundamentally different setting. While Byzantine robustness is indeed an important direction, it falls outside the scope of this paper. In the final version we will write that the development of a rigorous theoretical framework for Byzantine robustness remains an open problem in this field, which we will address in the future. \n\nWe hope this response has fully addressed your questions and concerns. Please let us know if there is anything else you would like clarified, or any additional information you would need."}, {"review_id": "kFMjvxVmsj", "reviewer": "Reviewer_AiVM", "summary": "This paper proposes two gossip algorithms for robust distributed estimation: GORANK for rank estimation, and GOTRIM for trimmed mean estimation, which builds upon GORANK. The key insight is computing robust statistics by first estimating ranks through pairwise comparisons, then using these ranks to compute weighted averages that exclude outliers. The authors provide theoretical convergence guarantees as well as empirical validation of each approach.", "questions": "1. It is noted that the $c^2$ term in the convergence rate of GOTRIM may be overly pessimistic. Can you provide additional ablations on simulated sparse graphs to better illustrate the true performance? \n2. Could you comment on the potential applicability of the proposed method to multivariate data?", "limitations": "1. The provided bounds may be loose, particularly for sparse graphs. The current work also focuses on simple settings with synchronous communication and Huber faults, rather than more general networks with Byzantine faults.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The writing is clear and easy to follow.\n2. The method is accompanied by a strong theoretical analysis with convergence rates and breakdown point guarantees.\n\nWeaknesses:\n1. Additional comparisons to prior work would be beneficial, both empirically and to provide context at a higher level. A table comparing the convergence rates, requirements on the graph structure, and estimation bias could help clarify the contributions of this work over prior methods.\n2. The results are based on a simple data corruption model, rather than considering more general Byzantine faults.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their valuable feedback. Below, we address the weaknesses point by point: \n\n1. While there has been significant work on decentralized estimation of simple aggregates (e.g., average, min, max), to the best of our knowledge, relatively little attention has been given to rank-based statistics in randomized pairwise gossip settings. This is likely due to the inherently global nature of rank-based statistics, which makes them more challenging to estimate in a decentralized setting. As discussed in the related work section (see section 2.2), we identified Chiuso et al. and He et al., which share a similar setting and that can be directly compared to our methods. However, conducting an empirical comparison with other prior works proved to be more difficult. As suggested, we will add a comparative table in the final version that summarizes key aspects of prior methods and our own. This includes whether each method is fully decentralized, whether the estimator is unbiased, and whether theoretical convergence guarantees exist on arbitrary graphs. Such a table could be as follows:\n| **Method**             | **Fully Decentralized?** | **Unbiased?** | **Rates on Any Graphs?** | \n| --------------- | ----------------- | ------------- | ------------------------ |\n| Chiuso et al. (Baseline) [1] | ✗                        | ✓             | ✗                        |\n| Baseline++ (ours)        | ✗                        | ✓             | ✗                        |\n| **GoRank (ours)**        | ✓                        | ✓             | O(1/t)                   | \n| Haeupler et al.  [2]        | ✗                        | ~            | ✗                        |\n| He et al.  [3]              | ✓                        | ✗             | ✗                        |\n| Shrivastava et al.  [4]    | ✗                        | ✓             | ✗                        |\n| **GoTrim (ours)**        | ✓                        | ✓             | O(1/t)                   | \n\nWe consider Chiuso et al.’s method not fully decentralized, as it requires an initial global ranking, which may not be available in real-world decentralized settings. Additionally, their convergence analysis is restricted to the complete graph.  Haeupler et al.'s method is also not fully decentralized since it requires sampling $K$ random nodes at the end of the protocol. Furthermore, their algorithm estimates only an approximate median, making the bias unclear. Their theoretical guarantees are again limited to complete graphs. Shrivastava et al.'s method relies on a base station for coordination, and thus does not meet the criteria for full decentralization. \n\n2. Considering more general Byzantine faults is indeed important. However, we believe that addressing Huber robustness is still relevant and realistic in many practical settings: a sensor could be miscalibrated, stuck at a fixed value, or may consistently report incorrect readings due to environmental factors, without necessarily being attacked. \n\n\nWe now respond to the two questions raised:\n1. First, we note that the Watts-Strogatz and 2D grid graphs used in our main experiments are already quite sparse, with both containing fewer than 1000 edges. However, we would like to emphasize that what primarily governs convergence behavior is not sparsity per se, but graph connectivity. For example, a dense graph composed of loosely connected clusters may have poor connectivity, while a sparse graph like a 3-regular graph can exhibit strong connectivity properties. A cycle graph, in addition to being sparse, has very low connectivity and serves as a useful pathological case. To better illustrate the relationship between topology and performance, we conducted additional ablation studies using three different sparse graphs: 1) Watts-Strogatz graph (connectivity $c = 3.31 \\times 10^{-4}$, \\~1000 edges), 2) Cycle graph ($c = 3.16 \\times 10^{-7}$, 499 edges), 3) 3-regular graph ($c = 2.24 \\times 10^{-4}$, 750 edges). All experiments were run for $8 \\times 10^4$ iterations. For GoRank, both the Watts-Strogatz and 3-regular graphs achieved fast convergence (absolute error below 0.05), consistent with their strong connectivity properties typical of expander graphs. The cycle graph, as expected, performed worse due to its very low connectivity, but still achieved an error below 0.1. For GoTrim, using the same corruption model as in Fig. 5b, the Watts-Strogatz and 3-regular graphs again performed very well, with errors close to 0. However, the cycle graph exhibited much slower convergence: after $8 \\times 10^4$ iterations, the absolute error remained above 40. Doubling the number of iterations reduced the error to below 40. While this is indeed slow, it is important to note that performance remains better than the corrupted mean, and such a topology is highly atypical in real-world sensor networks. In practice, such scenarios would likely require gossip algorithms specifically designed for cycle graphs. These ablations support the conclusion that GoTrim still performs well on sparse graph with good connectivity properties. \n\n2. We agree that extending the proposed approach to multivariate data is an important direction. A natural extension involves ranking multivariate observations based on their norms. Specifically, one could define a suitable norm depending on the task (e.g., Euclidean), compute the norm for each observation, and then apply our univariate ranking method (GoRank) to these one-dimensional values. Observations with the largest norms can then be treated as potential outliers. Following this, a multivariate version of GoTrim can be defined by discarding the top $k = \\lfloor \\alpha n \\rfloor$ observations with the largest norms, and computing the mean of the remaining points using the standard gossip algorithm. Alternatively, one could explore data depths as a generalization of ranking in multivariate settings (see [5]). Data depth provides a measure of centrality for multivariate data. While this approach is promising, it would require a more in-depth investigation beyond the scope of the current work, since depth computations usually require to solve computationally demanding optimization problems, just like alternative methods recently designed to define multivariate ranks (e.g. based on optimal transport). Finally, we could simply compute the coordinate-wise trimmed mean by applying GoTrim to each coordinate individually. A discussion about such possible extensions will be added in a dedicated section of the Supplementary Material. \n\nFinally, regarding limitations, we note that an asynchronous extension of GoRank has been presented, which also enables an asynchronous version of GoTrim.\n\nWe hope this response has fully addressed your questions and concerns. Please let us know if there is anything else you would like clarified, or any additional information you would need.\n\n[1] Chiuso, Alessandro, et al. \"Gossip algorithms for distributed ranking.\" Proceedings of the 2011 American Control Conference. IEEE (2011).\n\n[2] Haeupler, Bernhard, Jeet Mohapatra, and Hsin-Hao Su. \"Optimal gossip algorithms for exact and approximate quantile computations.\" Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (2018).\n\n[3] He, Lie, Sai Praneeth Karimireddy, and Martin Jaggi. \"Byzantine-robust decentralized learning via clippedgossip.\" arXiv preprint arXiv:2202.01545 (2022).\n\n[4] Shrivastava, Nisheeth, et al. \"Medians and beyond: new aggregation techniques for sensor networks.\" Proceedings of the 2nd international conference on Embedded networked sensor systems (2004).\n\n[5] Mosler, Karl. \"Depth statistics.\" Robustness and complex data structures: Festschrift in Honour of Ursula Gather (2013)."}, {"review_id": "3YfxXXbOHG", "reviewer": "Reviewer_XdBk", "summary": "The paper studies gossip algorithms for robust mean and rank estimation. In this setting, there exists a graph $G$ over $n$ nodes, as well as a value $X_i$ for each node. For each time step, a uniformly random edge in the graph is chosen, allowing communication of the endpoints of this edge. One should then design an algorithm that, after as few time steps as possible, can find the $\\alpha$-trimmed mean of $X$'s for some $0 < \\alpha < \\frac{1}{2}$, or find the rank of $X_i$ for each node $i$.\n\nThe paper establishes the first theoretical results for the convergence rate of such tasks, including an algorithm that achieves $O(1/t)$ convergence rate on rank estimation, and an algorithm that achieves $O(\\frac{\\log t}{t})$ convergence rate on robust mean estimation, based on the previous rank estimation algorithm. It is worth noting that the hidden factors in the $O$ notations contain the degree of connectivity of $G$.\n\nAt a high level, the algorithm for rank estimation works by letting each node $i$ to \"see\" the labels of all other nodes, done by randomly swapping the labels of the chosen edge at every time step. One should expect that at some time in the future, every label would have walked through every node in the graph, which means every node can now obtain a good estimation of their own rank. For robust mean estimation, one can think of trimming the $\\alpha$ outliers as identifying these outliers via finding their ranks, explaining the dependency of robust mean estimation on rank estimation.\n\nFinally, the paper gives numerical experiments showing that their algorithms' performance match the theoretical bound, and are also better than the state-of-the-art.", "questions": "**Questions**:\n1) Is there any lower bound on the convergence rate achievable via the class of gossip algorithms for the two tasks? It would be nice to understand the gap between the proposed algorithms and the optimal algorithms for the two respective tasks.\n\n**Comments**:\n1) In Theorem 3, what is \"for all $k \\in [n]$\" doing in the statement? I don't think the expression below has anything to do with $k$.\n2) I think the authors should not output an entire vector for GoTrim, since we're talking about mean estimation here. I believe simply outputting the mean of $Z$ is already good enough due to the L2-norm bound in Theorem 3, and this makes the algorithm a bit less confusing.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**:\n1) The model is very well motivated while not having a lot of prior work on theoretical bounds, so I think this is a very worthwhile question to study.\n2) The algorithms proposed are simple and intuitive, but seem to be better than the current state-of-the-art. In fact, GoRank is the first thing that comes to my mind when reading the model, so I am quite surprised that it performs better than the current SOTA while also satisfying some theoretical bounds.\n3) The paper is well-written and seem theoretically sound.\n\n**Weaknesses**:\n1) As the authors have mentioned, all of the expected convergence results can be transformed into the high-probability kind using Markov's inequality. However, I believe that a more careful analysis with some standard concentration bounds would benefit this paper a lot, as it enhances the \"robustness\" aspect of these gossip algorithms.", "was_revised": true, "final_justification": "I have read the rebuttals and decided to keep my score.", "rebuttal": "We thank the reviewer for their valuable feedback. We first address the limitation pointed out:\n\nFirst, let us recall that expected convergence results and high-probability bounds are the standard forms of convergence results in the gossip literature (see [1]). But you are right, this would certainly be interesting to derive concentration bounds in such dependent settings—where each data permutation depends on the previous one—along with the high dimensionality (the state space of permutations is $n!$) and complex data structure (graphs). However this is far from immediate and requires careful analysis. Results such as those in [2] could possibly be applied to establish such bounds. This point will be addressed in the final version of the article, but dealing with it in depth would require an analysis beyond the scope of this work, and we leave it for future research.\n\nWe now respond to the two questions raised:\n\n1. To the best of our knowledge, there are currently no established lower bounds on the convergence rate for the class of gossip-based algorithms applied to either decentralized ranking or trimmed mean estimation.  In the special case of a complete graph, we observe that significantly faster convergence than the typical $\\mathcal{O}(1/t)$ rate is possible. For example, in the Baseline++ algorithm, which performs direct ranking swaps, we can show exponential convergence of the form $\\exp(-t/|E|)$. However, this fast convergence critically relies on the high connectivity of the complete graph and does not generalize well to less connected graph. In contrast, GoRank demonstrates more robust performance across general graphs, including those with limited connectivity, where achieving $\\mathcal{O}(1/t)$ convergence is already non-trivial. Deriving a formal lower bound for arbitrary graphs remains an open and challenging problem. A similar challenge arises in the case of trimmed mean estimation, which depends on accurate rank estimation. We agree that developing tighter theoretical bounds for these problems is an important direction for future work.\n\n2. The phrase “for all” in Theorem 3 was indeed a typo and should be removed. Regarding your second point, we are not entirely sure we understand your concern, but it seems you are suggesting that the GoTrim algorithm should output only the mean of the vector rather than the full vector itself. First, note that the estimation error we are interested in is whether every node has a good estimator of the trimmed mean of the network. The vector $\\boldsymbol{Z}(t)$ is used to capture the error of all the estimators $Z_k(t)$ across the nodes simultaneously, which is a standard formulation in the gossip literature. Importantly, GoTrim outputs an estimate $Z_k(t)$ for each node individually. Would a version of Theorem 3 using the following left-hand term be clearer?\n\n$\\frac{1}{n} \\sum_{k=1}^n \\left|| \\mathbb{E}[Z_k(t)] - \\bar{x} \\right| \\leq \\frac{1}{\\sqrt{n}} \\left\\| \\mathbb{E}[\\boldsymbol{Z}(t)] - \\bar{x}_\\alpha \\mathbf{1}_n \\right\\||_2.$\n\nOr do you suggest the following alternative?\n\n$\\left| \\mathbb{E}[Z_k(t)] - \\bar{x} \\right| \\leq \\|| \\mathbb{E}[\\boldsymbol{Z}(t)] - \\bar{x}_\\alpha \\mathbf{1}_n \\||_2.$\n\nWe would appreciate your clarification.\n\nWe hope this response has fully addressed your questions and concerns. Please let us know if there is anything else you would like clarified, or any additional information you would need.\n\n[1] Boyd, Stephen, et al. \"Randomized gossip algorithms.\" IEEE transactions on information theory 52.6 (2006).\n\n[2] Bertail, Patrice, and Stéphan Clémençon. \"Sharp bounds for the tails of functionals of Markov chains.\" Theory of Probability \\& Its Applications (2010)."}]

Author rebuttal:

Meta-review: This paper proposes two gossip-based algorithms, GoRank and GoTrim, for robust distributed estimation under Huber’s contamination model. The theoretical analysis is solid, with convergence and breakdown guarantees, and the experiments show improvements over existing methods. Reviewers appreciated the novelty, clarity of the mathematics, and the practical validation. Concerns remain about scalability, the relation to Byzantine robustness, and the tightness of the bounds, though the rebuttal addressed some of these points. Overall, the contribution is significant and the consensus leans positive, so I recommend acceptance.
Decision: Accept (poster)