On Gossip Algorithms for Machine Learning with Pairwise Objectives
Authors: Igor Colin
Aurélien Bellet
Stephan Clémençon
Joseph Salmon
Venue: Accepted by TMLR ()

Abstract: In the IoT era, information is more and more frequently picked up by connected smart sensors with increasing, though limited, storage, communication and computation abilities. Whether due to privacy constraints or to the structure of the distributed system, the development of statistical learning methods dedicated to data that are shared over a network is now a major issue. Gossip-based algorithms have been developed for the purpose of solving a wide variety of statistical learning tasks, ranging from data aggregation over sensor networks to decentralized multi-agent optimization. Whereas the vast majority of contributions consider situations where the function to be estimated or optimized is a basic average of individual observations, it is the goal of this article to investigate the case where the latter is of pairwise nature, taking the form of a $U$-statistic of degree two. Motivated by various problems such as similarity learning, ranking or clustering for instance, we revisit gossip algorithms specifically designed for pairwise objective functions and provide a comprehensive theoretical framework for their convergence. This analysis fills a gap in the literature by establishing conditions under which these methods succeed, and by identifying the graph properties that critically affect their efficiency. In particular, a refined analysis of the convergence upper and lower bounds is performed.

Published in Transactions on Machine Learning Research (MM/YYYY)
On Gossip Algorithms for Machine Learning with Pairwise Objectives
Igor Colin
igr.coliin@teeccompprrr..
LTCI, Télécom Paris, Institut Polytechnique de Paris
Aurélien Bellet
aurelien.bellett@mrrio
PreMeDiCalL team, Inria, Idesp, Inserm, Université de Montpellier
Stephan Clémengon
LTCI, Télécom Paris, Institut Polytechnique de Poris
Joseph Salmon
joseph.sadmonn@inii..f
IMAG, IROKO, Univ Montpellier, Inria, CNRS
Reviewed on OpenReview: /ttps:///ppnrevveeet net/ forum? id- VezpURovJF
Abstract
In the ToT era, information is more and more frequently picked up by connected smart sensors with increasing, though limited, storage, communication and computation abili- lies. Whether due to privacy constraints or to the structure of the distributed system, the development of statistical learning methods dedicated to data that are shared over a net- work now major issuc. Gossip-based algorithms have been developed for the purpose of solving a wide variety of statistical learning tasks, ranging from data aggregation over sensor networks to decentralized multi-agent optimization. Whereas the vast majority of contributions consider situations where the function to be estimated optimized is basic average of individual observations, it is the goal of this article to investigate the case where the latter is of pairwise nature, laking the form of a U-stalistic of degree two. Motivated by various problems such as similarity learning, ranking or clustering for instance, we re- visit gossip algorithms specifically designed for pairwisc objective functions and provide a comprehensive theoretical framework for their convergence. This analysis fills a gap in the literature by establishing conditions under which these methods succeed, and by identifying the graph properties that critically affect their efficiency. In particular, refined analysis of the convergence upper and lower bounds is performed.
1 Introduction
The era of Big Data and widespread artificial intelligence has begun. It uses technological building blocks to automatically collect, store and process massive data of different types and formats in a short space of time. The machine learning craze is spreading to almost every field, as the Internet of Things (IoT) and the widespread use of technology for analysis make ever more data available, at ever finer granularity. Expectations are immense. However, whether for predictive interpretative purposes, the statistical analysis of data collected using modern technologies still raises wide variety of methodological questions in order to design smarter devices. The abundance of new applications, such as monitoring the state of health of complex infrastructures, the availability of massive data samples and the technological constraints inherent in acquiring and accessing information (e.g. sensor networks) and computing, have pushed the scientific community to develop new algorithms, beyond the example of successful applications such as computer vision, machinn-listening or automatic language translation. In the IoT era, information can be collected by connected smart sensors, shared across the network they form, and sometimes needs to be analyzed

---

Published in Transactions on Machine Learning Research (MM/YYYY)
in distributed way, due to systemic or privacy constraints for example. Gossip algorithms have been designed to solve various statistical tasks in this context, such as data aggregation or decentralized multi-
agent optimization, see e.g., Loizou and Richtárikk (2016), (Zantedeschi et al. (2020), Xin et al.
(2020a) or
Hendrikx et al. (020)) While the situation where the functional of interest is a basic average of individual
observations has received much attention in the literature, see e.g. Agarwal et al. 2010 Boyd el al. (201]
Bianchi and Jakubowicz (2013). Xin et al. (2020a) or Scaman et al. (2018). the present article focuses on the case where the function to be estimated or be optimized in a distributive manner is of pairwise nature,
taking the form of U-statistic of degree two (i.c., an average over all pairs of individual observations), see Clémençon et al.] (2008) Clémengon et al. (2016) or Laforgue et al. (2019). Indeed, many criteria that are relevant for evaluating the performance of decision rules in complex problems such as clustering, ranking, metric and similarity learning or graph reconstruction involve statistical quantilies that are precisely of this form, see e.g., Clémençon (2014), Clémençon and Vayatis (2010), Vogel et al. (2018) and Papa et al. (2016). This structural difference prevents the direct application of standard decentralized averaging techniques, and calls for dedicated algorithuic and theoretical tools.
Unlike local learning tasks such as classification regression, these global problems require the computation of pairwise interactions. The main motivation of this paper is to propose and analyze gossip algorithms adapted to pairwise objectives.
Classically, it is assumed that agents can exchange a limited amount of information per unit of time, via a communication infrastructure modeled by a connected graph whose nodes they constitute. Merging all the data at a given node not always possible, due to memory capacity constraints for example, nor necessarily desirable, for security and confidentiality reasons. It is therefore necessary to implement distributed estimation or optimization strategy, based solely on the local caleulations performed by the agents and on the communication enabled by the network structure.
Beyond communication constraints, gossip-based strategics are particularly well suited to realistic distributed settings such as IoT or edge networks, where each device has limited memory and computational resources. In such scenarios, storing or transmitting the entire dataset to a rentral node often infeasible, and sometimes undesirable ble for privacy or security reasons. Gossip protocols also naturally tolerate temporary node failures, communication delays, and asynchronous operation, since information continues to propagate through al- ternative paths without requiring global synchronization. These properties make gossip-based algorithms a natural candidate for decentralized learning with pairwise objectives.
The assumption that all local data processing and communication can be synchronized by means of a global clock, to which all agents have access, can greatly simplify the analysis of distributed algorithms. However, the asynchronous framework, which cach node processes local data and manages its information transfer to its neighbors in the communication network according to its own clock (modeled as a homogeneous Poisson process) only, is also considered in the Appendix (the extension requires only minor adjustments).
In this article, we first investigate the issue of computing U-statistic in a decentralized setting, f.c., from a sample of observations that is partitioned and distributed over a network. Whereas much attention has been paid to the standard distributed averaging problem, in both synchronous and asynchronous cases, refer to Boyd et al. (2006) (see also Karp et al. (2000), Kempe et al. (2003), Silvestre et al. (2018) and Wang ct al.] (2017)), few methods have been proposed in the case of pairwise averages. A fundamental difficulty in the pairwise setting is that, unlike classical averaging, the observations required to form pairwise estimates are not initially available at all nodes. Instead, auxiliary data must be progressively disseminated across the communicttin graph by gossip interactions, inducing a transient and non-uniform sampling of pairs. Understanding how this non con-urifomm impacts the bias and variance of local estimates over time is a central challenge addressed in this paper.
A dedicated algorithm for both synchronous and asynchronous settings is introduced in Colin et al. (205 referred to as GOSTA, This estimation procedure can be viewed as a mixture of local estimation of partial estimates and standard averaging method, of [Boyd et al.] (2006), and attains convergence rate of order ((1/t) after t 21 1 iterations. Although theoretical analysis was provided in Colin et al. 2015 it focused solely on the bias of the estimator.
2

---

Published in Transactions on Machine Learning Research (MM/YYY)
In this article, we examine the expected error, thereby proposing the first theoretical guarantee of convergence for the procedure, as well as variance result that can be used for concentration analyses or robust estimation applications.
We also address the problem of decentralized optimization in the case where the objective function is of the form of a U-statistic of degree two. Following in the footsteps of Duchi et al. (2012a), Colin et al. (2016) introduced and analyzed distributed synchronous and asynchronous optimization algorithus relying on the dual averaging of subgradients for pairwise functions. Beyond the rate bounds established, highlighting in particular the impact of the network's communication structure, the experimental results provided empirical evidence of the performance of the approach. However, the upper bound presented depends on a bias term related to the propagation of observations on the graph. Although numerical experiments suggested that this bias disappears quickly, its dependence on the optimization process did not allow one to draw firm conclusions about the convergence of the procedure.
We propose to extend gossip algorithms from single-observation objectives to pairwise objectives, and analyze their statistical and optimization properties. Our main contributions threefold: (i) for estimation, we provide the first complete non-asymptotic analysis of the GoSta algorithm, including expectation and variance bounds; (ii) for optimization, we establish convergence guarantees and show that the bias present in previous works vanishes; (iii) we derive a novel lower bound tailored to the pairwise setting. In addition, we include numerical experiments illustrating the predicted convergence behavior, the decay of the bias induced by pairwise gossip sampling, and the role of the communication graph topology.
The article organized follows. In Section 2 the essential concepts of decentralized data processing are briefly reviewed, along with standard approaches to distributed estimation and optimization. The state of the art in the case of U-stalistics is also presented for comparison with the results obtained in the following sections. Decentralized estimation of a U-statistic is addressed in Section 3 In Section E distributed optimization of a pairwise objective is considered, rate bounds are stated for both the error upperbound and lowerbound. Section 5 reports numerical experiments conducted on a real-world dataset, illustrating the practical behavior of the proposed algorithms. Some concluding remarks are collected and lines of further research are sketched in Section 6 Technical details and extension to the asynchronous setting are deferred to the Appendix section.
2 Background and Preliminaries
First, we describe the main features of decentralized systems in this section and then summarize the es- sential ideas underlying the gossip approach to distributed estimation and optimization. For the sake of completeness, we also briefly recall the basic notions U-statistics theory and review the state of the art in distributed learning with pairwise objectives.
x column vector, is denoted by ||=|| = (Σx=1 -/2, By I, = (1, ...., 1) is meant the vector in I" whose coordinates are all equal to one, and by B(0, D) fz R" || < D} the ball centered at O,, = (0, .... ...... 0) E R" with radius
Here and throughout, the Euclidean norm of any vector E R with n 2 1, viewed
D > O. The cardinality of any finite set A is denoted by [A].
2.1 Decentralized Setup Motivation and Framework
A variety of modern applications, among which statistical estimation and signal processing in sensor networks (Zhao and Guibas 2004), coordination in multi-agent systems, distributed localization and federated learning [Kairouz et al.) 2021), require solving tasks across datasets that are naturally distributed across a large number of nodes. The design of elficient algorithmic solutions must take into account the many constraints that arise from this context. Depending on the use case, these constraints may include the following:
C1 There is no central server to centralize data or orchestrate calculations (or such centralization is deemed too coslly);
C2 Node-to-node communiiaaton over the network is costly;
3

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Cs The computing and storage capacities of each node are severely limited; Ca Network-wide synchronization of nodes significantly degrades performance.
In this paper, we will consider decentralized problems in which at least constraint C1 holds. Federated learning is therefore outside the scope of our analysis, although we do analyze synchronous contexts where a central controller orchestrates the learning process. Both decentralized and federated learning offer ways of mitigating the privacy risks and costs of centralized learning. Decentralized computing has tradition- ally been studied in the context of sensor networks (Zhao and Guibas 2004). However, recent large-scale deployments of connected smart devices have also made the decentralized framework relevant to variety of use cases in which nodes communicate with only small subset of other peers, due to physical and /or/or efficiency constraints. It is worth pointing out that the relevance of docentralized computing has recently been demonstrated even in tightly-coupled systems (e.g., data centers). A striking example is the distributed training of machine learning models across a large number of compute nodes (CPUs or GPUs) in computing
cluster, where using a 'master node' to aggregate intermediate computations quickly becomes a performance
bottleneck, as it has to collect results from all the other nodes (see for instance Lian et al., 2017 Daily et al. 2018
Formal setup. We now formally describe the framework considered here and introduce some key notations that will be used throughout the paper. We consider a set of n 2 1 nodes (e.g., agents, sensors, connected objects) indexed by i E {1,.... ..... n}. Each node holds a local data sample X; from the data set D,, = (Xi,..., ). The network topology is modeled as an undirected connected graph g = (V,E), where the vertex set V is the set of nodes [n] == m... The edge set E consists of unordered pairs of vertices from the set V and describes the communicatio constraints: for all i i j. (i. E E if and only if nodes and j communicati....
can communicate directly with each other. Denoting A as the adjacency matrix (i.e., [A]k = 1 if and only if (i, E &, and [A] otherwise). the degree of node i E V is given by d, = [ and represents the number of neighbors of i in G. In practice, keeping the maximum degree small, ideally independent of n, ensures that nodes do not have to communicate with a large number of pecrs, thereby taking into account constraints C2 and C3] The communication ion properties of the network, i.e., the connectivity of the graph G, plays a crucial role in the performance of decentralized algorithms. They are generally described by the eigenvalues of the graph Laplacian, see e.g., Chung (1997). This symmetric and positive semi-definite n x n matrix is defined by L D A, where D diag(d1.... di...., .......d. da) is the degree matrix. Remarkably, up to renormalization, the matrix L is the transition matrix of a random walk on the connected graph G. Its smallest non-zero eigenvalue, the spectral gap, characterizes the stochastic stability of the random walk on G: if the connected graph G is non-bipartite, this specific finite-stale Markov chain is aperiodic, irreducible and geometrically ergodic, with the uniform distribution on G as limit distribution. The convergence occurs at a geometric rate that depends on the spectral gap in an explicit. fashion, see Chung 1997).
Gossip algorithms. The general idea behind decentralized algorithms is that each node alternates weew two stages: a local update stage and communication stage with its neighbors. In this paper, we focus on a certain type of decentralized algorithms, namely gossip protocols (Shah 2009 Dimakis et al. 2008). Rather than requiring communication with all neighbors, we consider a randomized gossip protocol in which each node exchanges information with only one random neighbor at each stage. Such randomized peer-to-peer communication makes gossip naturally resilient to temporary node failures or intermittent connectivity: if some devices disconnect or pause, information can still propagate along alternative paths without requiring global synchronization. Decentralized algorithms can be synchronous or asynchronous. In the synchronous setting, nodes have access to global clock. At each time step (tick of the clock), all nodes perform a local update and a communication step, and the next step only begins when all nodes have finished. Although this assumption is not always realistic, and significant slowdowns can occur, first focus our analysis on the synchronous framework, as it allows for more explicable rates. The asynchronous framework, where communication occurs randomly on the network and without a global clock, is next considered. One may refer to Boyd et al. (2006) for more details about synchronous and asynchronous time models. Two classes of docentralized problems have been widely studiod: estimation and optimization. Let f(; .,,...,K8 xx)) be some function of the data set D, parameterized by 0 E Rd. Broadly speaking, estimation refers to the problem of computing (or approximating) the value of for known value of 0, while optimization aims at finding
4

---

Published in Transactions on Machine Learning Research (MM/YYYY)
the parameters 0 that minimize f. Clearly, optimization appears more challenging than estimation, and the difficulty of solving these problems efficiently under the decentralized constraints described in Section 2.1 strongly depends on the structure of the function f. In fact, the vast majority of existing work has focused on docentralized estimation and optimization problems where f is separable across nodes. Namely:
(O;:X....,x,)) 1 Σ (((:x.))
(1)
For estimation purposes, the case encompasses many interesting statistios, particularly those in the form of sums and averages of quantities calculated from each data point. The thesis of Tsitsikkis (1984) is one of the earliest references on decentralized averaging, followed by a large number of more recent works (see
e.g., Gupta et al.] 2001] Kempe and Kleinberg 2002: Kempe et al. 2003 Xiao and Boyd 2004] [oyd et al.
2006 Mosk-Aoyama and Shah [0088] and references therein). More specifically, gossip algorithms have boen studied for this problem in (Kempe et al. 2003; Boyd et al.) 2006). Here we briefly describe the main ideas behind Boyd et al. (2006)'s classic gossip averaging algorithm. The algorithm operates in asynchronous framework: nodes wake up asynchronously and average their local estimate with that of randomly chosen neighbor. As long as the network graph is connected and non-bipartite, the local estimates converge to ( at a rate ((e-c) where the constant e can be related to the spectral gap of the network graph, showing faster convergence for well-connected networks.
The optimization of separable functions has attracted a great deal of interest in recent decades, mainly, but not exclusively, in the context of federated learning (Kairouz et al. 2021). Several methods have been proposed to improve the convergence rate by extending Nesterov's acceleration (Even et al.) (021) or by using a more specific approach (Hendrikx et al.) 2019), by optimizing the balance between communication and local computation (Scaman et al., 2018). or by means of variance reduction techniques (Xin et al., 2020b a). Other approaches have tackled the non-i.i.d framework, either for personalization or for multitask learning (Zantedeschi et al.) 2020 Li et al. 2022b Vanhaesebrouck et al.) 2017 Dai et al. 2022). Another way of improving the convergence properties of decentralized and federated optimization is to tackle the communication bottleneck: quantization techniques developed for compressed sensing have been extended to the decentralized case improve communication efficiency during the optimization process (Haddadpour
et al. 2021 Albasyoni et al. 2020: Hamer el al. 2020 Li et al. 2022c).
Although privacy is one of the constraints motivating decentralized and federated learning, these designs remain vulnerable to various privacy attacks. However, local data storage allows communication to be modified through noise or encryption to provide satisfactory privacy guarantees, al the cost. of slower learning (Kasyap and Tripathy, 2021 Ji et al., 2024 Jeon et al., 2021). ) Similar approaches have been adopted for robustness, where adapting communication rules can lead to robust optimization processes (Li ct al. 2022a; Raynal et al. 2023 Zecchin et al.) 2022). Finally, fairness in distributed learning is also active research topic, as preserving fairness while limiting user information leakage in the case of inter-device learning
leads to significantly lower learning rates Biswas et al. 2024 Du et al. 2021 Jiang and Lu 2019).
We point out that all the above approaches are restricted to functions that are separable across agents, as in D seen in the next section, many interesting estimation and optimization problems are only separable across pairs of agents, thus motivating the design of the algorithms described and analyzed in Section 4, tailored to pairwise objectives. A key aspect of pairwise objectives in decentralized settings is that, unlike separable averaging, the information required to form pairwise interactions is not initially available at every node; nodes start with one local obscrvation and must progressively acquire additional (auxiliary) observations through gossip exchanges. As a consequence, pairwise estimates and gradients are formed from a transiently non-uniform sampling of pairs, which only approaches the uniform distribution after sufficient mixing of the auxiliary variables. Quantifying the effect of this progressive dissemination on bias and variance is one of the main technical challenges addressed in our analysis.
2.2 Pairwise Averages and U-statistics: Definition and Examples
In many situations, the quantity of interest is not a simple mean (e; taken w.r.t. the distribution of r.v. X but takes the form y(h) E[h(0; X, X')), where X and X' are two independent and identically
5

---

Published in Transactions on Machine Learning Research (MM/YYYY)
distributed random vectors, taking their values in some measurable space X' with probability distribution F(dx) and h: X x X + R is symmetric measurable mapping, square integrable w.r.t. the product measure F 8 F.
A natural estimator of ((hh) based on an i..d. sample Dn = (X1, Xn} drawn from F is the average over all pairs
2 (m(hh) a(n - 15isjsn
Σ
k(X,,
The quantity 2 is known as the U-statistic of degree two with kernel h based on the sample Dn. For U-statistics of degree higher than two, we refer the reader to Appendix B As may be shown by a classic Lehmann-Scheffé argument, it is the unbiased estimator of μuhh) with minimum variance. However, the reduced variance property has a price when it comes to analyzing the fluctuations of such functional (uniformly over a class of kernels possibly), the terms averaged in (2) exhibiting complex dependence structure. This technical difficulty can be overcome in order to prove limit theorems (e.g., SLLN, CLT, LIL) for such statistics by means of linearization techniques (i.e., Hoeffding decomposition, Hajek projection), see e.g., Leel (1990) for an account of the asymptotic theory of U-statistics. Similar approaches can also be used to establish concentration bounds for U-statistics; see Clémençon et al. (2008) and the references al. (2016) for scalability challenges tackled by means of sampling schemes and Laforgue et al. (2019) for robustness issues. Many commonly used statistics mcasuring dispersion, such as empirical variance and the Gini mean difference, take the form of U-statistic
therein for further details. See also Clémençon
(2) Similarly, in various statistical learning problems whether supervised or unsupervised the empirical risk criterion can also be expressed as a U-statistic.
Metric learning. Numerous machine learning methods involve a metric between data points. The perfor- mance of such techniques is crucially determined by the choice of an adequate metric. It is precisely the goal of metric learning to adapt the metric to the data analyzed. Motivated by many applications (e.g., computer vision, information retrieval), this problem has been recently the subject of much attention in the literature, see for instance Bellet al. (2013) and the references therein. Inspired by biometric identification problems, it is formulated in Vogel et al. (2018) in the framework of supervised multi-class classification: random label Y, laking values in finite set [K] with K 2 2, is assigned to random observation X valued in feature space X. Given independent copies
YY),........ (Xn, Yn) of the random couple (X, Y), the learning task consists in finding a metric D: x X' > R, such that pairs of points with the same label are close, whilc pairs with different labels are distant from each other. The risk of a metric candidate D can be formulated as follows:
R(D) = B E ((-D(XX) (2I(Y- =Y' 1 -Y)]
where (X,Y") is an independent copy of (X,Y) and d(u) is a convex loss function upper bounding the indicator function I[u 2 0} (e.g., the hinge loss Φ(u) max(0, 1 u)). Its empirical version is the U- statistic of degree two:
(D) n(n 1) 15KCJER
2
Σ
- X,), (2T(), Y2) - -1))
Ranking. Given objects described by a random vector of features X E X and the (temporarily hidden) ordinal and real valued labels Y assigned to them, the goal of supervised ranking is to rank them in the same order as that induced by the labels, on the basis of a training set of labeled examples. This statistical learning problem finds its motivation a wide variety of applications, e.g. medical diagnosis support, search of scoring function + R, transporting the natural order on the real line onto the feature space. Ideally, the larger s(X), the larger the label Y with overwhelming probability. Learning such scoring function from independent
engines, credit-risk scrcening, e-commerce. Rankings are generally defined by means
6

---

Published in Transactions on Machine Learning Research (MM/YYY)
labeled data (X,,)), .... (Xn, Yn) drawn as the generic random pair (X,Y) can be formulated as the problem of minimizing the U-statistic known as the empirical ranking risk; refer to Clémençon et al. (2005)
(x(s) n(n -1-1 1)
2
Σ
((-(s(x))- - s(x,)) - (x)-
Igi<isn
where L:R. - R4 is given loss function, e.g., f(u) = Iluu > 0). The quantity (3) is U-statistic of degree two with kernel ha ((x, v), (a'; (/)) = ((-(s(x) s(x')) (y- )') for (r, and (a', in X' x R. Observe incidentally that, in the case where the label Y is binary (é.e., bipartite ranking), the ranking risk is equal to the popular AUC critcrion, up to an affine transform.
Clustering. The unsupervised learning task one completes when segmenting a dataset Xi...., X, in a feature space X' into finite subgroups depending on their similarity is referred to as clustering: observations in the same segment should be more similar each other than to those lying in other segments. See e.g. Chapter 14 in Friedman et al. 22009) for review of popular clustering methods. More precisely, consider a symmetric function D X'x X R4 such that ()x, = O for any E X. D measures the dissimilarity between pairs of observations (x, x') E x2; the smaller the quantity D(x, the more similar x and x'. Fix also the number of desired clusters M 2 2. It is the objective of clustering methods to find a partition P of the feature space X in a class 1I of partition candidates that minimizes the following empirical clustering risk:
(P((P) n(n -1 1)
2
Σ Xx), Xx),
(4)
ISieiSn
where ( = ((x,))((xxx)) E J indicates whether two points x and x' belongs to the same cell of the partition or not. When the Xi's are i..d. realizations of a generic I.v. X with distribution F(zx), the quantity 4 usually referred to as the intra-cluste similarity or within cluster point seatter, is a U-statistic of degree two with kernel li(ax, x') = D(x, x') (p(x,2²) for all (x,z²) E X2, provided that Ma..ae)x (x,, x²) Ox(x, x') (a))F((()a F(dx) F(dz') < 400. The statistical analysis of the clustering performance of minimizers of (4 over a class II of appropriate complexity can be found in Clémençon (2014).
Remark. (U-STATISTICS Vs V-STATISTICS) When the symmetric kernel function h X x X R is such that h(z,x) = O for all x E X (which is the case for most kernels used in the problems mentioned above), we naturally have: Eiej h(X,, Xi) = Ein X,). However, when this is not the case, the quantity V-statistic-uite when divided by and is obviously obtained by
En, Xx) is classically referred to adding to the pairwise summation Eizy h(x,, Xz) the basic i.i.d. sum X.), For simplicity, with slight abuse of language, (1/n²) Eis h(X,, X3) will be called a U -tottistic throughout the article, the possible presence of diagonal terms in the functional of interest having no impact on the algorithms proposed and their analysis.
Although the field of decentralized learning has received a lot of attention, especially since the advent of federated learning, work on pairwise decentralized learning remains scarce. This problem was first investi- gated in Pelckmans and Suykens (2099), where a method for estimating partial sums of a U-statistic was proposed and then extended to full estimation by requiring two gossip protocols to run in parallel. This method was further refined in Colin et al. (2015), using only one gossip protocol in contrast, along with refined convergence rates for both synchronous and asynchronous settings. To the best of our knowledge, the pairwise optimization problem has only been tackled in Colin et al. (2016). using an algorithm that com- bines distributed dual averaging (Duchi et al. 2010b) with pairwise estimation (Colin et al., 2015). The rates derived in Colin et al. (2016) provide some intuition about the problem characteristics, but do not guarantee convergence of the method, as they only show convergence in the case where the gradient biased estimates actually converge to the true gradient. Our new analysis shows that this is true without any additional assumption, and provides a better understanding of the impact of bias on the optimization process. A key clement in our analysis is to show that the gradient bias induced by the auxillary-observation propagation decays at a rate controlled by the mixing properties of the communication graph (in particular, through its spectral gap), which leads to explicit non-asymptotie convergence guarantees.
7

---

Published in Transactions on Machine Learning Research (MM/YYY)
3 Decentralized Estimation of a Pairwise Functional
To begin with, we consider the docentralized estimation problem for pairwise functional. Formally, let (Xi,..., .n) E x be a sample of n 2 2 points in a feature space X' C Rd with d 2 1 and let h: X' x X - R a measurable function, symmetric in its two arguments. The goal pursued here is to estimate, in the anl and with asm-ssypio guarantees, the following quantity:
decentralized framework described in Section 2.1
(h)
Σ x(x, n² 4=
(5)
Let F be probability distribution X. As pointed out in Remark 2.2 the statistic
(5) slightly dif-
fers from the U-statistic (2), which forms unbiased estimator with minimum variance of the paramcter [[M(X, X')] f h(,, F (odz))(dzz))) soon as h is square integrable w.r.t. F @ F and the x;'s are inde- pendent realizations of the distribution F: their difference is of order Op(n~8/ and (2) differs from (5) by a factor of nn/nn - 1) when h(x,,) = 0 for all x E X. When clear from context, we will omit to index the functional 5 by h and will use the notation Ün. We define H E Raxn such that [H] == h(x,, xi) for all k, n and h Hl,/n / the vector of partial sums. Observe that Ü, = 1, h/n.
3.1 GoSTA Algorithm
In Boyd et al. (2006) and other related papers, the gossip averaging methods rely on activated neighbors averaging their local estimates in order converge to the network mean. Such algorithms cannot be extended to efficiently compute (5) it depends on pairs of observations. Indeed, in the separable averaging case, the values to be averaged are already locally available from the start, whereas in the pairwise case each node must progressively acquire auziliary observations from other nodes in order to form pairwise evaluations h(x,, xy). As a consequence, the pairs effectively used in local updates are non-uniform until the auxiliary observations have sufficiently mixed over the graph. This problem is investigated in Pelckmans and Suykens (2009) with U1-GOSSIP and U2-GOSSIP algorithms. In UI-GOSSIP, each node i [n] estimates its partial U-statistic:
Σ h(x;,,))
(6)
The spirit of the algorithm is a bit different from the standard gossip case. For each node k E [n]. estimator (t) is initialized to zero and an auxiliary observation yx(t) is initialized to At each iteration 2 1, if communiattin is initiated between nodes i and j, they swap their auxiliary observations:
(1) = (t - 1) and (1 y:(l -
Then, every node updates its estimator using its (local) pair of observations:
t t-
Vk E [m]. (t)
zx(t 1) + h(xx, vt(())
Both algorithms are detailed in Appendix C.3 and C.4 Introduced in Colin al. (015)) GOSTA algorithm
is based on the observation that U, = n == where (-(1) are the partial sums defined in 6 The goal is thus similar to the usual gossip averaging problem, with the key difference that each local value 7,00 is itself an average depending the entire data sample. Consequently, each iteration: a data propagation step to allow each node i to estimate (1(0), and an averaging step to ensure convergence to the desired value Ü,. Here, we only present the algorithm for the simpler synchronous setting in Algorithm the asynchronous version being detailed in the optimization case.
algorithm combines two steps
3.2 Mommasympto Estimation Bounds
We now carry out non-asymptotic analysis of the GOSTA-SYNG algorithm presented in Scction 3.1 The following result is originally stated in Colin et al. (2015) and provides bound in expectation taken w.r.t.
8

---

Published in Transactions on Machine Learning Research (MM/YYY)
Algorithm GOSTA-SYNC
Require: Each node k E [n] holds observation X
Each node E [n]] initializes its auxiliary observation y+ X2 and its estimate 2
2: for L = 1,2..... do
3:
for p = ,...., n do
4:
Ep +- - (x)
5: end for
6: Draw (i,j) uniformly at random in E'
7: 2 + (2: 22)
Swap auxiliary observations of nodes i and j: y: 6+ Yj
9:
end for
return Each node & [n] has the estimate 2 disposal
the random edge activations for the deviation between the estimate produced by Algorithm [ and the target Ün. More preciscly, the expectation in Proposition is taken with respect to the algorithmic randomness (random edge activations and auxillary-observation swaps), for a fixed dataset (x,)....x)).
Proposition (Convergence in expectation). Let g ([n),E) be a connected and non-bipartite graph, (XI...., .xx) a sample of 2 2 points in X C Idd and (z(t))(21 the sequence of estimates generated by Algorithm 7 For all l [ni] and any 2 1, we have:
B[2(() - Unlnn
D(h) D(h)
E
DA
where An-1 is the second smallest eigenvalue of the graph Laplacian L and
D(h) h 1 + 2|| h1
Proposition [ shows that all the local estimates generated by Algorithm | converge in expectation to U, at a rate of order O(1/t). In addition, the constants involves in the rate bound above reveal the impact of graph structure and the distribution the data points on it on convergence. Indeed, the quantity D(h) is dala-dependent and reflects the difficulty of the estimation problem itself through a measure of dispersion. In contrast, / is a detwork-dependent term since An-1 the second smallest eigenvalue of the graph Laplacian L. The value A,-1 is also known as the spectral gap of G and graphs with larger spectral gap typically have better connectivity, see Chung (1997) for detailed analysis of the graph Laplacian notion. It should be noticed that pairwise estimation rates are slower than those in mcan estimation, which are geometric (Boyd et al. 2006). This is due to the fact that mean estimation relies on values already computed by the nodes, whereas pairwise estimation requires the nodes to estimate these quantities while averaging them.
In the separable averaging setting, each node starts with a locally available value and the only source of error is the mixing of the averaging dynamics, which yields geometric convergence. In contrast, in the pairwise setting each node must first estimate its partial sum by exchanging auxiliary observations. At early times, the auxiliary observations have not mixed yet, so the pairs (xx, Yx(t) used in the updates are drawn from a non-uniform distribution over the dataset, which induces bias. Although Proposition D guarantees that the bias of the estimate decreases in O(1/t), it does not ensure that the (random) estimate converges to the target 55. In particular, controlling ||E[z(t)] i. alone does not prevent fluctuations of z(t) around its mean. In the following theorem, we state an upper bound on the expected gap, therefore providing such a guarantee. This result is also helpful when considering robustness constraints or guarantees high probability.
Theorem (Expected deviation). Let G ((n).) be connected and non-bipartite graph, (Xi,...,X,, sample of n 2 2 points in X' c Idd and (z(1))=21 the sequence of eslimates generaled by Algorithm For all k E [n] and any 2 1, we have:
2/ An-1
4/81 ( An-1
1 2t
E zt)) Ü, S Vi
1/(
1+
H 51
+
1+
H
9

---

Published in Transactions on Machine Learning Research (MM/YYY)
where An-1 is the second smallest eigenvalue of the graph Loplacion L.
We almost recover convergence rate of order 0(1/Vl,, up to factor of v 12+1// 1/1. As can be seen by
examining the technical proof given in Appendix C22] this term is consequence of the bias of the early estimates propagating through the network, but it quickly vanishes.
4 Decentralized Optimization of Pairwise Objective Function
Motivated by the statistical learning problems mentioned in Section 2.2 we now tackle the problem of minimizing objective function of the form of pairwiss average of the network agents' data, such (5) with respect to parameter 0 on which it depends:
F(0) =
1 n
E ISiJSn
f(0:x,,)))
where θ _ B(0,, D) S Rd the parameter space with D > 0 and, for 1 1 i,j S n, the function fiy == f( xx),,, : C Rd R is L-Lipschitz with L 0, convex and possibly non-smooth. Finally, for 1 i n, we denote Si := (1/n) Σ Jij the partial objectives. In general, we will use notation for network averages, and notation for temporal averages.
Again, the main difficulty in solving the optimization problem
min F(0)
(8)
BE
arises from the fact that each term of the sum depends on two agents i and j, making standard local update schemes impossible unless data is exchanged between nodes. In contrast to separable objectives, where each node can compute (unbiased) gradients of its local loss immediately, the pairwise setting requires each node to progressively acquire auxiliary observations from other nodes. As result, the pairs used in early iterations are non-uniform over the datasct, and the corresponding gradient estimates are biasod until sufficient mixing has occurred on the communication network. To the best of our knowledge, efficient search of solution 0* of (8) in decentralized setting has only been tackled in Colin et al. (2016).
The methods of Colin et al. (2016) rely on dual averaging NNstcrrvv 2009
Agarwal et al. 2010 This choice is guided by the fact that dual averaging is often easier to analyze than subgradient descent in const or regularized settings, because it maintains a linear accumulator of (sub)gradients while the (oon-linea)) smoothing/projectionn
smoothing/ projection operator is applied separately:
Rd
+
Te
arg max {o(t)0 z 1111/22
(9)
z
+
This work builds upon the analysis carried out in Duchi et. al. 2012ap, where a distributed dual av- eraging algorithm is proposed to optimize an average of separable functions f(;x). In that setting, each node can compute unbiased estimates of its local (sub)gradient vf(;x;) that are iteratively av- eraged over the network- see Appendix D.1.3 for details. Unfortunately, there major difference with the optimization problem considered here. In setting, node i cannot compute unbiased estimates of V.((-)) (11/n) - only holds x;. To circumvent this, the algorithm relies on gossip data propagation step similar to that introduced in Section 3 so that nodes can compute biased estimates of vf((-) while keeping communication and memory overheads low for each node.
because the latter depends all data points, while each node i E [n]
We first recall the pairwise optimization algorithm in the synchronous context Section 4.1 provide a refined analysis of the gradient bias via an ergodic argument in Section 4.2 lower-bound result for pairwise decentralized optimization procedures in Scction
We then
Finally, we prove a
For completeness, background on (distributed) dual averaging is provided in Appendix D.I.1
10

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Algorithm 2 Gossip dual averaging for pairwise function in the synchronous case
Require: Step size (n(t))e21 > 0
Each node i E [r] initializes y; Xi. 2; = 0; 0. 0
2: for L I.....T do
3: Draw (f.j) uniformly at random
4: 3, 1.
5: Swap auxiliary observations: y: ++ Yy
6:
for k = L...., do
7:
Zk: + 2t + Vof(Ox:Xx,
02 (2x)
02 (1 0x 0
10: end for
11:
end forreturn Each node E [m] has 0x
4.1 Decentralized Pairwise Function Optimization
In the synchronous framework, we assume that each node has access to a global clock, so that each node can be updated simultancously with each clock tick. We assume that the scaling sequence (+(t))221 is the same for every node. At any time 2 L, each node i E [n] stores: gradient accumulator Zū, its original observation X,, and auziliary observation y;: initialized at x; and evolving through data propagation. The algorithm is summarized in Algorithm 2 At each iteration,
edge (i,j) E E is drawn uniformly at random. Nodes i and average their accumulators and swap their auxiliary obscrvations. Finally, all nodes perform a dual averaging step, using their local pair (x) to form a (biased) partial gradient estimate.
Average iterate and gradient bias. For any t > 0, define the average accumulator 2(t) = Ex (t) and the corresponding average iterate
(() n, (ē(t))
Then, we denote by E(t) the average gradient bias across the network:
1 n n
7tt) 72
([(0((0);x
Σ (x(x)))))))))
Equipped with these notations, we can state the following result (initially stated in Colin et al. (2016) which adapts the convergence rate of centralized dual averaging under term capturing the contribution of the bias.
Proposition 1. Let (mn) be a connected and non-bipartite graph, and let 0* E aaggminees F(Ø). Let
(7()))22 be non-increasing and non-negative sequence. For any E [n] and any t 2 0, let 2,(() E Rd and (,(t) Rdd be generated according to Algorithm 2 Then, for any i [n] and T > 1, we have:
B[F(O,(T) - S (T(T) + C2(T) Cz(T)
where
T
1
Ci(T) (T
10
7()
2T
t=
3L
C2(T)
7(1)
T
/I 1n-1/18]
1 T-1 Σ
Cs(T) T 1=1
(.((((t)= 0-) TE(t)]
and An-1 is the second smallest eigenvalue of the graph Laplacian L.
11

---

Published in Transactions on Machine Learning Research (MM/YYYY)
We refer the reader to Appendix D.2 for detailed proof. As in the estimation case, the bound in Propo- sition [ decomposes into: a centralized term CT()), network disagreement term C2(T) depending on the spectral gap, and puirvise-specific term C2')) coming from the gradient bias induced by auxiliary-data propagation.
Importantly, Proposition by itself does not guarantee convergence unless one controls C3(T). While Colin et al. (2016) observed empirically that the bias term vanishes quickly, the upper bound does not provide explicit non-asymptotic guarantee that (T) vanishes. In the next section, refine the analysis by explicitly quantifying the bias decay in terms of the mixing properties of the auxillary-obseevation process
on the graph.
4.2 Pairwise Ergodic Dual Averaging Gradient Bias Convergence Analysis
We now focus on slightly different objective from that in
S For E [n], define py: O x A, as follows:
{ + x An R (0,E)
4 E ()fi(
where An = (E E RQ ||E|| = 1} the simplex in RR. Note that
F(O) = F
0
f((0)
72
72
Let S, = fe1. .... J be the canonical basis of R and let (E,(t))e20 be sequence of (not necessarily independent) random variables over Sn identified with [n]. For t 2 0, denote by Pt(t) the distribution of (t) and assume
lim [P((1) 1./n/ITV = +
where || I/ is the total variation norm and 1,/n is the uniform distribution on [m]]
This abstraction captures the auxillary-observation mechanism in gossip pairwise optimization: at time t, node i can only pair x; with a single auxiliary sample (encoded by {,()),, whose distribution becomes approximately uniform only after sufficient mixing the graph.
We make the additional assumption that one cannot access Vol. (,, In/n) directly. Instead, at ileration 2 one can compute V (., yielding the noisy update
{
z, +1) 11)
z,(t) + (eF((((t)
(10)
+1) (t)
For any >> define the mixing time Tz(e):
Tc(c) = sup inf {s 0: [ + s|t) - 1n/n//rv S c) 120
where Pi(l P s(t) the conditional distribution of E. 8) given the filtration F( = (E),
We ready to quantify explicitly the impact of the gradient bias and state the following refined rate bound.
Theorem (Pairwise ergodic dual averaging). Let G ((n),)) be a connected and non-biparlite graph, and let 0- E arg mingge F(O). Let (y(t))sz1 be non-increasing, non-negative sequence such that yxt) to for some a E (-1,0). For any i E [n] and any 2 0, let 2t) E Rd and (t) E Rdd be generated according to Algorithm 2 Then, for any > 0,
((F(O,(T)) F(O0) s CC() Cc(T,)))
12

---

Published in Transactions on Machine Learning Research (MM/YYYY)
where
C(T,E) D³
+ (1+1(()))
1.2
T
Σ (())
(t()
2Ty(T)
2T
31,²
T-1 Σ ((t)
(2(T) T -1-vo 11
An-1/18)
Xn
1=1
(+ T(E)
Ca(T,e) 2LD
T
and
log(v[T/E)
c(9) = An-1 (1- A 2
(()) = log(c(g))
with
[
Sketch of proof. In the centralized setting, the convergence analysis relies on the regret decomposition of Duchi et al. (2012b): for any 0 TTT
- f(((t)))((0'))) = Σ f(0(t)) - f(0)) - +10 g(t++(((
(11)
Σ
(F(O(t) ((0
(12)
- ((T0))(()))))))))))))())))))))))
(13)
Σ T
(f(0(t)- f(0)))
(14)
The key point is that each term isolates variations of either 0 or & but never both simultancously, which allows one to handle the dependence induced by the evolving sampling distribution. Including the network disagreement contribution in the noiseless term 13 yields the stated bound; see Appendix D.2 for details. ]
Theorem 2 makes the bias mechanism explicit through T(E) and the residual term CT(T, In gossip settings, the auxiliary process mixes geometrically, hence T(E) grows only logarithmically in 1/c.
Corollary 1 (Corrected and refined rate for 7(t) a/ VF). Let g ([nl,E) be connected and non-bipartite gruph, and let 0* E arg mitlage F(0). Let > 0 and (()) a/ Vl. For any i E [n), let (:(T) be generaled by Algorithm Then, for any T 1
100 - 0-11²
6aL
12aL² log(c(G)) log(T)
- -
<
+ aT?
+
VT
2a
/1 An-1/181
2., - A*ll
+
(1+ ([ol(og(((()) log(T")
T
which corresponds to the choice ET 1/T in Theorem
In particular, the term appearing in the second line of the bound above is precisely the explicit remainder term that was previously hidden in o(I/VT) when eт was not specified. Choosing a = 100-0-11/L4 minimizes the leading constant in the 1/VT term, yielding the equivalent (but more interpretable) form:
E [[F(O,(T)) - F(O*)) < LI100 - 00
(3
6
12 (T)
+
VT
2
1
V1-
An-1
Tog(c(()))
2T
A*ll
+
(1 + log(c(g)) log(T))
T
13

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Remark.
The asynchronous setting requires time estimators, inducing additional voriance and slower overall convergence rate. For completeness, the asynchronous implementation and associaled mlle are pro- vided in Appendia D.2.3
4.3 A Lower Bound Result for Pairwise Decentralized Optimization
We derive a lower bound related to the synchronous decentralized optimization problem considered in Sec- tion 4.1 by extending the argument of Scaaann et al. (2018) the pairwise case. The lower bound closely related the distance induced by graph G, which why we introduce it here. Given connected graph G [[n], the distance j) between nodes i and the minimurn length of a path between them.
Theorem (Lower bound). Let n > 2 and let g ([n), E) be a connected graph. Let (i,j) E [n]? be two modes of that are marimum distance, that is dg(i. E arg max do(ki 1) and let
do(i,k) k) + dk(k.
2 (((1.))
There crist n² functions Saj : Rdd - R such that F == En.j Jij L-Lipschila and for any E [n], any R > 0, any t (d 22) minff, (A, 1) and any synchronous black-bor procedure (0x(t)),
RL
1
((O
min F(O) 2 |
36 V (1+1/A)
I+1
Theorem 3 extends the construction of Scaman et al. 2018) from separable objectives to pairwise objectives. The proof is provided in Appendix D.3 The lower bound for decentralized pairwise optimization is similar to known lower bounds for separable objectives; the main difference lies in the appearance of Á. For separable objectives, the lower bound typically depends on the diameter (distance between two farthest nodes). In the pairwise case, information must effectively propagate from to through intermediate nodes k, which leads to the averaged two-hop distance quantily A.
5 Numerical Experiments
In this section, we report numerical experiments illustrating the behavior of the proposed decentralized algorithms for the maximization of the Area Under the ROC Curve (AUC). This criterion is standard performance measure in binary classification and ranking problems, see Section 2.2 Our experiments aim at assessing both the convergence propertics the docontralized pairwisc optimization scheme and the practical impact of the bias induced by local information exchanges. In particular, we observe that the algorithuss converge reliably and that the bias term rapidly becomes negligible as iterations progress.
Given collection of feature vectors X,,...,X, Xn Rdd with associated binary labels f 1-1,1), consider linear scoring functions of the form x + x TT,, parameterized by 0 E Rd. The AUC criterion measures the proportion of correctly ordered positive positive-negative pairs and can be written as
AUC Eiswysn ((a2))) (xTOxx
Eisiss 1(iie)))
This quantity corresponds to the probability that the scoring function assigns a higher value to positively labeled observation than to a negatively labeled one. Since the resulting optimization problem non-smooth and non-convex, is common to replace it with a convex surrogate. In our experiments, we rely on the logistic pairwise loss and consider the following empirical risk:
1
R, (0)
Σ 15t,55n
1(xe)))) log(1 (1 + exp((x) T0))
n
14

---

Published in Transactions on Machine Learning Research (M/YYYY)
Consensus loss
Bias error term
0.12
0.11
Async complete
Async Watts-Strogatz
0.04
Async complete
Async Watts- Strogatz
Lagistic AUC
0.10
Async grid
Async grid
Blas
0.02
0.08
0.01
0.07
0.06
0.00
0.05
1.25e4
2.5e4
3.75e4
5e4
1.25e4
2.5e4
3.75e4
5e4
Iterations
Rerations
(a) Loss evolution (asynchronous setting).
(b) Bias term (asynchronous setting).
Figure 1: Logistic AUC. Solid lines are averages and filled area are standard deviations.
No explicit regularization is added in these experiments. All experiments conducted the Breast Cancer Wisconsin dataset. [ which contains n = 699 samples in dimension d = 11. In the decentralized setting considered here, each node of the network stores exactly one observation.
Network topologies. To investigate the influence of commuication constraints, we consider three net- work structures with markedly different connectivity properties:
Complete graph. Every pair of nodes can communicate directly. This topology represents an idealized scenario, as information mixing is immediate and gradient estimates are expected to exhibit minimal bias. For a fixed number of nodes, the complete graph maximizes the spectral gap, see Chung 1997 Ch. 1). In our setting with 699, obtain An-1/181 2.86 10-3
2D grid. Each node has exactly four neighbors, leading to poor connectivity and large graph diameter. This topology represents a challenging regime for decentralized optimization. In this case, the normalized spectral gap is An 4.30 10-3
Watts Strogatz graph. Following ?, this random graph model interpolates between regular lattices and well-connected networks. is controlled by the average degree i and a rewiring probability p E (0, 1). We choose / = 1.82 10-4
and p 0.3, yielding intermediate connectivity properties with
Experimental setup. For each network topology, we initialize all local parameters 0: to and Algorithms and for 50 independent trials. The stepsize sequence is chosen as 7(t) = 10/3
Figure Ia reports the evolution of the objective value in the asynchronous regime, together with the standard deviation of the local objectives across nodes. As expected, better-connected networks exhibit faster conver- gence. In particular, the complete and Watts-Strogatz graphs outperform the grid topology. In addition, the dispersion of the local estimates decreases as network connectivily improves.
Finally, Figure 1b illustrates the behavior of the bias term ē(t) T ((). In all considered networks, this quantity rapidly converges to zero and remains several orders of magnitude smaller than the objective value throughout the optimization process. This empirical observation supports the the analysis and explains the good practical performance of the proposed decentralized algorithm.
6 Concluding Remarks and Future Work
In this final section, we summarize the main contributions of our study and outline promising directions for extending our results. Beyond the theoretical guarantees established for decentralized estimation and
hhttps///archvee.tt ics. uci htt.aa///..aateeeeeeerreeeeeeeta
15

---

Published in Transactions on Machine Learning Research (MM/YYYY)
optimization with pairwise objectives, we discuss potential adaptations of our methods to broader and more demanding learning scenarios.
6.1 Multiple Points per Node
For ease of presentation, we have assumed throughout the paper that each node holds single data point X₁. We now consider the case where each node holds the same number of points k 2 2. First, it is easy to see that our results still hold if nodes swap their entire set of k points (essentially viewing the set of & points as single one). However, depending on the network bandwidth, this solution may be undesirable. We thus propose another strategy where only two data points are exchanged at each iteration, as in the algorithms proposed in the main text. The idea is view each "physical" node E [n] as a set of l "virtual" nodes, each holding a single observation. These k nodes are all connected each other well as to the neighbors of i in the initial graph G and their virtual nodes. Formally, this new graph G [[n] E*) is given by G x KR. the tensor product between G and the k-node complete graph Kg. It is easy to see that [|]]
kn and We can then run our algorithms on G (cach physical node i E [n]] simulating the behavior of its corresponding & virtual nodes) and the convergence results hold, replacing - - by 1 - in the bounds. The following result gives the relationship between both gaps.
|E$ k-2 El.
Let G = (mi, E) be a connected, non-bipartite and non-complete graph. Let k 2 2 and let G be the lensor product graph of G and Kg. We have that.
Proposition 2.
0 -- = k
where An-1 and X are the second smallest eigenvalues of L and L respectively.
The proof is stated in the Appendix. Proposition 2 shows that the network-dependent term in our conver- gence bounds is only affected by a factor k. Furthermore, note that iterations involving two virtual nodes corresponding to the same physical node will not require actual network communication, which somewhat attenuates this effect in practice.
6.2 Differential Privacy
In many decentralized applications, privacy is major concern: raw data is sensitive and agents may not be willing to share it with other peers in the network. To accommodate such privacy constraints into our algorithms, which are based on exchanging data points across the network, one can rely the local model of differential privacy (Dwork and Roth 2014 Duchi et al., 2013 In this model, agents randomize their inputs locally before sharing them. The simplest example of locally differentially private protocol in the case of data in a discrete domain is randomized response, in which cach agent either shares its true value (with some probability p) or a randomly selected one (with probability 1 - 1-p). This gives rise lo a natural trade-off between privacy and utility. Bell et al. (2020) recently proposed protocols to compute pairwise U-statistics under local differential privacy. Their first protocol based on randomized response can be easily combined with our decentralized algorithms since it allows to compute unbiased estimates of the pairwise function of interest. They also provide error bounds with respect to the non-private setting. The protocol can be extended to continuous data through quantization, see (Bell et al. 2020) for details.
6.3 Conclusion
In this work, we provided comprehensive theoretical analysis of decentralized estimation and optimization of pairwisc objectives, filling key gaps left by existing methods. We established new non-asymptotic guarantees for both the estimation of U-statistics and the convergence of deceentralized pairwise optimization ion under gossip protocols, highlighting the role of network topology and gradient bias. These results lay the groundwork for extending our framework more challenging scenarios. In particular, future research could integrate robustness and fairness constraints, which are often naturally formulated as U-statistics, thereby enabling principled decentralized learning under realistic and socially responsible requirements.
16

---

Published in Transactions on Machine Learning Research (MM/YYX)
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. 2030' program, as part of the Hi! PARTS Cluster and the PEPR IA Foundry.
References
A. Agarwal, M. Wainwright, and J. C. Duchi. Distributed dual averaging in networks. In Advances in Newral Information Processing Systems, pages 550-558, 2010.
A. Albasyoni, M. Salaryan, L. Condat, and P. Richtárik. Optimal gradient compression for distributed and federated learning. arXie e-prints, pages arXiv arXiv-2010, 2020.
J. Bell, A. Bellet, A. Gascón, and T, Kulkarni. Private Protocols for U-Statistics in the Local Model and Beyond. In AISTATS, 2020.
A. Bellet, A. Habrard, and M. Sebban. A Survey on Metric Learning for Feature Vectors and Structured Data. ArXio e-prinls, June 2013.
P. Bianchi and J. Jakubowicz. Convergence of Multi-Agent Projected Stochastic Gradient Algorithm for Non-Convex Optimization. JEEE Trans. Aulom. Control, 58(2):391 400, 2013.
S. Biswas, A.- Kermarrec, Sharma, T. Trinca, and M. de Vos. Fair decentralized learning. arXiv e-prints, pages arxiv 2410, 2024.
S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Trans. Inf. Theory, 52(6))2508-2533 2006.
S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning, 3(1): 122, 2011.
P. Brémand. Markov chains: Gibbs fields, Monte Carlo simulation, and queues, volume 31. Springer Science & Business Media, 1999.
F. Chung. Spectral Graph Theory, volume 92. Amer. Math. Soc., 1997.
S. Clémençon. A statistical view of clustering performance through the theory of U-processos. Journal of Multivoriate Analysis, 124:42-56 2014.
S. Clémençon and N. Vayatis. Overlaying classifiers: a practical approach to optimal scoring. Construclive Approzimation, 32:619 648, 2010.
S. Clémençon, G. Lugosi, and N. Vayatis. Ranking and scoring using empirical risk minimization. In Proceedings of COLT, 2005.
S. Clémençon, G. Lugosi, and N. Vayatis. Ranking and empirical risk minimization of U-statistics. The Annals of Stalistics, 36(2):844 874, 2008.
S. Clémençon, I. Colin, and A. Bellet. Scaling-up empirical risk minimization: Optimization of incomplete u-statistics. Journal of Machine Learning Research, 17(76):1-33,, 2016. URL http://jmlr.org: http:pprrrrrpppppp////s v17/15-012.htm
1. Colin, A. Bellet, J. Salmon, and S. Clémençon. Extending Gossip Algorithms to Distributed Estimation U-Statistics. In NIPS, 2015.
Colin, A. Bellet, J. Salmon, and S. Clémençon. Gossip dual averaging for decentralized optimization of pairwise functions. In International Conference Machine Learning, 2016.
17

---

Published in Transactions on Machine Learning Research (MM/YYYY)
R. Dai, L. Shen, F. He, X. Tian, and D. Tao. Dispfi: Towards communccation-cffcientt personalized federated learning via decentralized sparse training. Xiv preprint arXiv:2206.00187 2022.
J. Daily, A. Vishnu, C. Siegel, T. Warfel, and V. Amatya. GossipGraD: Scalable Deep Learning using Gossip Communication based Asynchronous Gradient Descent. Technical report, arXiv:1803.05880, 2018.
A. Dimakis, A. Sarwate, and M. Wainwright. Geographic Gossip: Efficient Averaging for Sensor Networks. IEEE Transactions on Signal Processing, 56(3): (605):120--1216, March 2008.
W. Du, D. Xu, X. Wu, and H. Tong. Fairness-aware agnostic federated learning. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 181-189 SIAM, 2021.
J. Duchi, J. Agarwal, and M. Wainwright. Distributed Dual Averaging in Networks. In Aduances Neural Information Systems, 2010a.
J. Duchi, L. Mackey, and M. Jordan. On the consistency of ranking algorithms. In Proceedings of ICML, 2010b.
J. Duchi, A. Agarwal, and M. Wainwright. Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling. TEEE Trans. Autom. Control, 57(3):592 606, 2012a.
J. C. Duchi, A. Agarwal, M. Johansson, and M. T. Jordan. Ergodic mirror descent. STAM Journal Optimization, 22(4):1549 1578, 2012b.
J. C. Duchi, M. 1. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates, In FOCS, 2013.
R. M. Dudley. Distances of probability measures and random variables. Selected Works of RM Dudley, pages 28 28-37, 2010.
C. Dwork and A. Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2014.
M. Even, R. Berthier, F. Bach, N. Flammarion, Gaillard, H. Hendrikx, L. Massoulié, and A. Taylor.
A continuized view on nesterov acceleration for stochastic gradient descent and randomized gossip. Proceedings of the 35th International Conference on Neural Information Processing Systems, pages 28054- 28066, 2021.
M. Fiedler. Algebra connectivity of graphs. Czechoslouake Mathematical Journal, 23(98) (988))298-3055 305, 1973.
J. Friedman, T. Hastic, and R. Tibshirani. The Elements of Statistical Learning. Springer, 2009.
Gupta, R. Van Renesso, and K. Birman. Scalable fault-tolorant aggregation in large process groups. In Dependable Systems and Networks, 2001. DSN 2001. International Conference on, pages 433 442. IEEE, 2001.
F. Haddadpour, M. M. Kamani, A. Mokhtari, and M. Mahdavi. Federated learning with compression: Unified analysis and sharp guarantocs. In International Conference on Artificial Intelligence and Statistics, pages 2350 2358. PMLR, 2021.
J. Hamer, M. Mohri, and A. T. Suresh. Fedboost: A communication-effiieell algorithm for federated learning. Tn International Conference on Machine Learning, pages 3973-3953 PMLR, 2020.
H. Hendrikx, F. Bach, and L. Massoulié. Accelerated decentralized optimization with local updates for smooth and strongly convex objectives. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 897-906. PMLR, 2019.
H. Hendrikx, F. Bach, and L. Massoulié. Dual-free stochastic decentralized optimization with variance reduction. Advances in neural information processing systems, 33:19455-1999 19466, 2020.
18

---

Published in Transactions on Machine Learning Research (MM/YYYY)
B. Jeon, S. Ferdous, M. R. Rahman, and A. Walid. Privacy-preserving decentralized aggregation for fed- erated learning. In TEEE INFOCOM 2021-IEER Conference on Compuler Communications Workshops (INFOCOM WKSHPS), pages 1 6. IEEE, 2021.
C. Ji, Maag, R. Heusdens, and Q. Li. Re-ovaluating privacy centralized and decentralized learning: An information-thcoreiccal and empirical study. arXiv preprint arXiv::409.14220 2024.
J. Jiang and Z. Lu. Learning fairness in multi-agent systems. Advances in Neural Information Processing Systems, 32, 2019.
P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Charles, G. Cormode, R. Cummings, al. Advances and open problems in federated learning. Foundations and trendsl in machine learning, 14(1 2):1 210, 2021.
R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading. In Symposium on Foundations of Computer Science, pages 565-574. IEEE, 2000.
Kasyap and Tripathy. Privacy-preser ralized learning framework for healthcare system. ACM Transactions on Multimedia Computing, Communiication,, and Applications (TOMM), 17(2s):1 24, 2021.
D. Kempe and J. Kleinberg. Protocols and impossibility results for gossip-based communication mechanisms. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 471 480. IEEE, 2002.
D. Kempe, A. Dobra, and J. Gehrke. Gossip-Based Computation of Aggregate Information. In FOCS, pages 482 491, 2003.
P. Laforgue, S. Clémencon, and P. Bertail. On medians of (Randomized) pairwise means. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1272-1281. PMLR, 09-15 Jun 2019. URL https: h/pp:e///roceeinggs mlr. pll.s.rres/v9//// /aeess//v97/eemmmccoo1.... clemencon199.htmm
A. J. Lee. U-Slatisties: Theory and Practice. Marcel Dekker, New York, 1990.
Q. Li, B. Kailkhura, R. Goldhahn, P. Ray, and P. K. Varshney. Robust decentralized learning using admm with unreliable agents. IEEE Transactions on Signal Processing, 70:2743-277 2757,, 2022a.
S. Li, T. Zhou, X. Tian, and D. Tao. Learning to collaborate in decentralized learning of personalized models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9766 9775, 2022b.
Z. Li, H. Zhao, B. Li, and Y. Chi. Soteriaff: A unified framework for private federated learning with communication compression. Advances in Neural Information Processing Systems, 35:4285-4300, 2022c.
X. Lian, C. Zhang, Zhang, C.-J, Hsieh, W. Zhang, and J. Liu, Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent. In NIPS, 2017.
N. Loizou and P. Richtárik. A new perspective on randomized gossip algorithms. In 2016 IEEE Global Conference on Signal and Information Processing, GlobolSIP 2016, Washington, DC, USA, December 7-9, 2016, pages 440-444, 2016.
D. Mosk-Aoyama and D. Shah. Fast distributed algorithms for computing separable functions. IEEE Trans. Inf. Theory, 54(7):2997 3007, 2008.
A. Nedié. Asynchronous broadcast-basel convex optimization over a network. Automatic Control, IEEE Transactions on, 56(6):1337-14) 1351,, 2011.
Y. Nesterov. Primal-dual subgradient methods for convex problems. Math. Program., 120(1):2611225) 283, 2009.
19

---

Published in Transactions on Machine Learning Research (MM/YYYY)
G. Papa, A. Bellet, and S. Clémengon. On graph reconstruction via empirical risk minimiza- tion: Fast learning rates and scalability. In D. Tee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Cur- ran Associates, Inc., 2016. URL https::/ppooceddinggt neurips... coturpp..ccpapppeee Files//aaprr/2D6/fffee Blia0000:3661222222111144400-0-0
pdf
K. Pelckmans and J. Suykens. Gossip Algorithms for Computing U-Statistics. In NecSys, pages 48 53, 2009.
M. Raynal, D. Pasquini, and C. Troncoso. Can decentralized learning be more robust than federated learning? arXiv e-prints, pages arXiv 2303, 2023.
K. Scaman, F. Bach, S. Bubeck, Massoulié, and Y. T. Lee. Optimal algorithms for mon-h distributed optimization in networks. Advances in Neural Information Processing Systems, 31, 2018.
D. Shah. Gossip Algorithms. Foundations and Trends in Networking, 3(1):1-125, 2009.
D. Silvestre, J. P. Hespanha, and C. Silvestre. Broadcast and gossip stochastic average consensus algorithms in directed lopologies. IEEE Transaclions Control of Network Systems, 6(2):474 486, 2018.
J. Tsitsiklis. Problems in decentralized decision making and computation. PhD thesis, Massachusetts Institute of Technology, 1984.
A. Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
P. Vanhaesebrouck, A. Bellet, and M. Tommasi. Decentralized collaborative learning of personalized models over networks. In Artificial Intelligence and Statistics, pages 509-517. PMLR, 2017.
Vogel, A. Bellet, and S. Clémençon. probabilistic theory of supervised similarity learning for pointwise ROC curve optimization. In Dy and A. Krause, editors, Proceedings of the 35th International Con- ference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5065 5074, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
T. Vogels, H. Hendrikx, and M. Jaggi. Beyond spectral gap: The role of the topology in decentralized learning. Advances in Neural Information Processing Systems, 35:15039 15050, 2022.
G. Wang, 7. Wang, and J. Wu. A local average broadcast gossip algorithm for fast global consensus over graphs. Journal of Parallel and Distributed Computing, 109:301 109, 2017.
L. Xiao. Dual averaging method for regularized stochastic learning and online optimization. In NIPS, pages 2116-2131 2224, 2009.
L. Xiao. Dual averaging methods for regularized stochastic learning and online optimization. JMLR, 11: 2543 1196-299,,220 2010.
L. Xiao and S. Boyd. Fast linear iterations for distributed averaging. Systems Control Letters, 53(1): 65-78, 2004.
R. Xin, S. Kar, and U. A. Khan. Decentralized stochastic optimization and machine learning: A uni- fied variance-reduction framework for robust performance and fast convergence. IEEE Signal Processing Magazine, 37(3):102 113, 2020a.
R. Xin, C. A. Khan, and S. Kar. Variance-reducee decentralized stochastic optimization with accelerated convergence. IEEE Transactions on Signal Processing, 68:6255-622 6271, 2020b.
V. Zantedeschi, A. Bellet, and M. Tommasi. Fully decentralized joint learning of personalized models and collaboration graphs. In International Conference on Artificial Intelligence and Statistics, pages 864-874 PMLR, 2020.
M. Zecchin, M. Kountouris, and D. Gesbert. Commuiication-effiieell distributionally robust decentralized learning. arXio preprint arXiv:2205.16111 2022.
F. Zhao and L. Guibas. Wireless Sensor Networks: An Information Processing Approach. Morgan Kaufmann Publishers Inc., 2004.
20

---

Published in Transactions on Machine Learning Research (MM/YYY)
A
Additional notation
We here introduce notation that will be useful for the various proofs. Let G = ([n], E)) be connected graph. We denote as L E "= its Laplacian, that is, = A, and we denote as X 2 ... 2 An its cigenvalues, sorted in decreasing order. For a 1, let Wa be the symmetric matrix in R defined as:
Wa
Σ (IJ)EE
In -e-c))(e - -3)²)) I, a E a
L
E
In particular, W2 is the transition corresponding to gossip averaging and W is the transition of auxiliary observations. We also denote as (a) .... 2 X, (a) the corresponding cigenvalues, sorted in decreasing order. We denote as Jn == n 1,,1, E gux" and for any a 21, 1,
Wa = Wa - JJ,
For t > 2 0 and sequence of matrices M(0), M(t) E RTX", denote M(t s) the product M(t 8) = M 1) ((s +
Additionally, :(I:) M())... ... M()) and we use the convention M(I :)) In.
B U-statistic of degree
In this section, present the more general definition of a U-statistic (Van der Vaarl 2000
Definition (U-statistic). Denote r 2 1 as the degree of a U-statistic and let (xI,..., In) E X be sample of n 2 r points in a feature space X. Let h X" + symmetric in its r arguments. The Usttaiistic of degree r is defined as:
a measurable function that is permutation
(h)
Σ (E)
Ri,),
where Irn is the set of all unordered tuples of r different integers from f1.
For r = 2, we obtain the classical U-statistic:
(h( = n(n 1sKKSS
2
Σ
C Pairwise estimation
C.1 Preliminary Results
Here, we state preliminary results on the matrices W,, that will be useful for deriving convergence proofs and compare the algorithms. First, characterize the eigenvalues of W. in terms of those of the graph Laplacian.
Lemma 1. Let G = (nn) E) be an undirected graph and let (Ai)sssn be the eigenvalues of its Laplacian L, sorted in decreasing order. For any a 2 1, we denole as (Mra)))ssisn the eigenvalues of Wa, sorted in decreasing order. Then, for any ssigm n,
An-it1
A:(a)
a|El
Proof. Let a 2 1 and let d; E R be an eigenvector of L corresponding to the eigenvalue \;, then we have:
Wade = I, 1 L Φ1 = (1
a A
Thus, Φ; is also eigenvector of W. for the eigenvalue 1
E d and the result holds.
21

---

Published in Transactions on Machine Learning Research (MM/YYY)
The following lemmata provide essential properties Wa eigenvalues.
Lemma 2. Let n > 0 and let = (m), E) be an undirected graph, G is connected and non-bipartite, then for any a 2 1, Wa primitive, I.c., there crists k > 0 such that W > 0.
Proof. Let a 2 1. For every (1,5) E E, I, (e, - -j)(c; - oz) is nonnogative. Therefore Wa is also nonnegative. For any < <IS n, by definition of Was one has the following equivalence:
([) 0) ([aa)a 0)
By hypothesis, G is connected. Therefore, for any pair of nodes (k E [n]² there exists integer Sы >> 0 such that [(A)*] > 0 so W. is irreducible. Also, G is non-bipartite so similar reasoning can be used to show that Wa is aperiodic.
By the Lattice Theorem (see (Brémand 1999 Th. 4.3, p.75)), for any 1 S k, S there exists an integer ma such that, for any 2 mg:
W kk 0
Finally, we can define m = supky ma and observe that W > 0.
Lemma 3. Let G ([n], F)) be connected and bipartite graph. Then for any 2 1,
1 >1 > d2(a).
where X (a), )2(a) are respectively the largest and the second largest eigenvalue of W..
Proof. Let a 2 1. The matrix Wa is bistochastic, so (a) = 1. By Lemma 2 Wa is primitive. Therefore,
by the Perron-Frobenius Theorem (see BBémmad 1999 Th. 1.1, p.197)), we can conclude that A1 (a(a).
Now that we have a relation between the graph structure and the eigenvalues of War we are ready to prove our main results.
C.2 Decentralized pairwise estimation
C.2.1 Proof of Theorem
(Synchronous Setting)
Let h = vec (H) E R= For 12 1, one has
2(1) t-
We(I)a(t 1)+ B h
W2(t:s)B (I, @ Wi
Using spectral theorem, we decompose the mixing matrices as W. = W,, + Jn, The above expression can thus be expanded as follows:
x(1) ; Σ (We(::) JJ)) B (I, @ (Wi(s)++J.))
-,,,+ Wa(t:s)B @ Wi(s:) h+ & Wi(s:) h+ W2(t:))Bh
22

---

Published in Transactions on Machine Learning Research (MM/YYYY)
where h = h - In J,,h. Taking the squared norm and using the orthogonality of eigenspaces yields
|2(1)) - 1,
W2(t: @ Wi(s:) h J,, @ Wi(s:) h
W2(t:8) (I, @ Wi(s:)) h
(A)
J,B (I, @ Wi(s:) h
(B)
Let us start by analyzing the first term
one has
ΣΣ
h T (I, & Wi(r:)) B We(t:)) B[,, & Wi(s:)) h
f ==1==
t Σ h (I, & Wi(s:)) B Wa(:s)) Ba( @ Wi(s:)
(A.1)
+ 1
Σ Σ aL @ wi(r:)) T B
@ Wi(s:))
(A.2)
r=++1
For any t 2 and any x E R", one has
B[x
T [ = W2 - 1:s)
S 12)xx W2(t - 1:s) W2(t 1:8)x
(15)
Using
15 on
A.1
yields the following result
1 h
(2 [L,, @ Wi(s:)) h1]
F 1- 22
The second part
A.2
can be bounded in a similar fashion, using the above reasoning up to index r:
2
A.2
222 (I, @ wi(r:)) B Bl, @ (s:)))))))) h
12
r=s+1
1-1
<
Σ Σ
x2
12
1=11=
2 h|
< (1 (2))
This concludes the analysis of the first term:
(2)
Let us now focus on the second term. It can be split in similar way:
T (I, @ Wi(s:) B BJJ.BBBLL @ Wi(s:)
12
(I. Wi(s)) BJ @ Wi(s:) h
(B.1)
1
[-]
+
Σ
Σ
h
(I (I. ((.)) B B.B, 8 Wi(s:)
(B.2)
23

---

end for end for Published in Transactions on Machine Learning Research
Algorithm 3 U1-GOSSIP algorithm for computing 6
Require: Each node k holds observation
1: Ys +- X (Each node initializes its auxilaary observation)
2: ze +- 0 (Each node initializes its estimator)
3: for = .,,.... do
Draw (t.j) uniformly random from E
5: Nodes and j swap their auxiliary observations: y: ++ Yj
for I,..., n do
7: 2k + 1-1 2 V1)
9:
10:
return Each node has z
The first term B.1 can be simply bounded by
B.1
Regarding the second lerm, one has
2 1-1
B.2
2 h
( - A2(1))
Combining our bounds on and yiclds
E
(1l)
1, S
((1+
1
|
2 An-
2+ 2 [1ba1²)
An
The result holds by using the Cauchy-Schward inequality on the above result.
C.3 U1-GOSSIP algorithm
The goal of the U1-COSSIP algorithm for each node to compute an estimate of its respective partial U- statistic. This process sunmarized in Algorithm 3 Using reasoning similar to that for GoSTA, one can derive convergence rate for the expected estimates, stated in the following theorem.
Theorem 4. Let assume that G EV is connected and non bipartite. defined in Algorithm we have that for all [n] and any >> 0,
Then, for z(t)
E [[)x(t)) - O(()) S E Hcp
2An-1t
where An-1 is the second smallest eigenvalue of the graph Laplacian L.
C.4 U2-GOSSIP algorithm
U2-GOSSIP Pelckmans and Suykens 2009 is alternative to GOSIA for computing U-statistics. In this algorithm, each node stores two auxiliary observations that are propagated using independent random walks. These two auxiliary observations will be used for estimating the U-statistic see Algorithm for details.
We can now state a convergence result for Algorithm
Theorem 5. Let us assume that is connected and nin-biiaatite. Then, for z(t) defined in Algorithm are have that for all l E [n]:
lim [[(+(()) (b)
1++00
24

---

Published in Transactions on Machine Learning Research (M//YYYY
Algorithm 4 U2-gossip Pelckmans and Suykens (2009)
Require: Each node holds observation X
yk - Xa. %/ + Xk. Zu
+
2: for = 1,2..... do
3: for p .1... do
Lp 1-1 2 HX,, ,,,))
5:
end for
Draw (i.j) uniformly at random from E
Nodes and j swap their first auxiliary observations: y, y
8: Draw (ke 1) uniformly at random from E
9: Nodes k and swap their second auxiliary observations: ( 4+ 1,
end for
Moreover, for anyy 1 >> O,
[[z(t)] (h)
E
3 Xn
H h1 + [ 1-02(0)).11)
tx--1
2 1
where An-1 is the second smallest eigenvalue of L. Proof of Theorem
Let & > 0, one can adapt GoSTA analysis and write
zt)) 1
W (s:) (I, & Ws(s:)
where for any 1 8 S,, (s()) is an independent copy of Wi(s). Therefore, one has
[t) = (h) + J.B (I, W wih+ WiB, (I, @ Wi) h
Using the eigenvalues properties of WT, one can write
B|z(() -
- (1)1,
(1011|| + 110
Rearranging the terms yields
2+ (1)
1
< 1- A2(1)²
h
+
|b||
1 x2
and the result holds.
D Dual averaging
In this section, focus the dual averaging algorithm. First, Section D.1 introduces some centralized approaches for dual averaging and the key theorctical guarantees associated. Then, Scction D.2 develops the proofs for such guarantees, alongside the proofs of the convergence rales presented in Section
D.1 Centralized dual averaging
D.1.1 Deterministic Setting
In this section, we review the dual averaging optimization algorithm (Nesterov) Problem 7 in the centralized setting (where all data lie the same machine). To explain the main idea.
2009
Xiao 2010 solve
25

---

Published in Transactions on Machine Learning Research (MM/YYY)
behind dual averaging, let first consider the iterations of Stochastic Gradient Descent (SGD), assuming t = 0 for simplicity:
at = = -
where (()) = V)((())), and (r()))=20 is a non-negative and non-increasing step size sequence. This update rule can be rewritten equivalently as follows:
[t + 1) arg min [(((t)) + (0- g(t) + 0 - (t))))))
(7(1)
BER
meaning that 0(1 1) is the minimizer of some quadratic approximation of around O(1). Recursively and assumiig that 0(0) 0, one obtain:
|0| 2
+ 0(1 + 1) arg min 0 Σ ())g(()))))))))))))))))))))){{)
(16)
DER
For SGD to converge to an optimal solution, the step size sequence must satisly lime-++0 7()) = 0 and Er (t) = co. As noticed by Nesterov (2009), an undesirable consequence that new gradient estimates are given smaller weights than old ones in (16) Dual averaging aims at integrating all gradient estimates with the same weight.
Let (7(())220 be positive and non-increasing step size sequence. The dual averaging algorithm maintains sequence of primal iterates (0(1))cso, and sequence (z(t))(20 of dual variables which collects the sum of the unbiased gradient estimates seen to time t. We initialize to 8(1) = z(0) = 0. At each step t > O, we compute an unbiased estimate g(t) of ((((()) The most common choice is to take g(t) = ( X1, x.,) where 4 and Jr are drawn uniformly at random from [n]. We then set z(t + 1) z(t) + g(t) and generate the next iterate with the following rule:
0(t + 1) = n. (z(t + 1)),
|101
1 (z) == arg min BERd
z
+ to(o)
(y(
This particular formulation was introduced in Xiao 2009 2010), extending the method introduced by
Nestcrov (209)) in the specific case of indicator functions. In this work, we borrow the notation from Xiao
(2010h. When it is clear from the context, we will drop the dependence in s and simply write ni Tz(z) m (z).
Note that (-)-) is related to the proximal operator of function & Rd - R defined by
2 - x|2
prox = arg min ZERd
2 + ((x)
Indeed, one can write:
Te(z)= = prox (7())z)
For many functions vi of practical interest, (-).) has a closed form solution. For instance, when 16 = || 112 ()(-) corresponds to a simple scaling, and when sb = || !|I it a soft-thresholdig operator. If t is the indicator function of closed convex C, then (-(-) is the projection operator onto
The dual averaging method is summarized in Algorithm In order to perform theoretical analysis of this algorithm, we introduce the following function. Let us define, for t 2 0
||0|
Vi(z) == max D
z To 8
tu)
(7(t)
Remark that with the assumption that e0 = 0, then Vi(0) = o. Strong convexity in of the objective function, cnsures that the solution of the optimization problem is unique. The following lemma. links the function V, and the algorithm update and is simple application of the results from (Xiao) 2009 Lemma 10):
26

---

Published in Transactions on Machine Learning Research MM/YYYY)
Algorithm 5 Centralized dual averaging
Require: Step size (y(1))221 >
<-00 0. < 0. 2 <- 0
2: for I....,Tu. do
3:
x - V+
4:
f (T(
5: 0 0+ 7) 0 1
6: end forreturn 0
Lemma 4. For any E RR, one has:
(z = VVi(z)
and the following statements hold true: for any Z1, 22 E Rdd
[|t( - mx((2)) s ((t) z2ll
and for any g, Rdd
Vi(z + g) S Vi(z) +g VV.(2z) + 7(1)
2 [g]]
(17)
Moreover, adapting Xiao 2009
Lemma 11) can state:
Lemma 5. For any 2 1 and any mon-tnereasing sequence (n(()) have
V= + 1)) (0 + 1)) S Vi-1 (-2(1 +
We also need a last technical result that we will use several times in the following:
Lemma 6. Let O(() n. 2E g()), and let (c(()))21 be a non-increasing and non-negative sequence sequence (with the convention 7(0) = 0), then for any 0 E Rd:
T Σ g(t)
((())((())))))))))))))))
- 0) + T Σ (v((()) (0))
Σ
T
7 1)
(gg()))1 +
|1012
(18)
T
T
2
(Tx(T)
t=1
Proof. Using the definition of Vr, one can get the following upper bound:
Σ
= z - (T)(0) + |101
|10|
-
2T(T)
2y(T)
|012
<
Vr( (2( + 1))
(19)
(T(T)
Then, one can chock that with
17 and Lemma 5 that, for any $ $ T:
Vi(-z(t + 1)) + & (0 1)) < V.-1(-2(( 2(1 1)) = V/-1 g(())
$ VVo-1(-2(t) -(t) Te(t) + (t-
2 [g)
From the last display, the following holds:
T(() + (0(1 1)) S (-1((=(()) vi(-z(1 + 1)) + 7(t - 1)
lg(())2
2
27

---

Published in Transactions on Machine Learning Research (MM/YYY)
Summing the former for 1,.... T yields
T
T
7 1)
Σ 8(1) 0(L) + (0(( 1)) S vol-20) (-(-)
gt 11
Remark that Vo( 0 and v(((1) - (0(TT + +1) = -55(0TT + 1)) S 0, so the previous display can be reduced to:
T Σ (()) ((t) + Va
7 1)
Σ
[g{()]]
(20)
2
1=1
Combining with 19 the lemma holds true.
Bounding the error of the dual averaging provided in the next theorem, where we remind that R., ʃ th:
Theorem (Dual averaging). Let (x(t)) a non increasing sequence. Let (z(t))221, (f(t))s21, (0(t))o21
Assume that the function f is I-p-isschitz and let 0* E Rd be minimizer of Rn, i.e., 0* arg mingreRd Rr, (0').". Then for any T 2, one has:
and (g(1)) be generated according to Algorithm &
10012
L T-1
R. (O(T) Rn (0') S (T)
+
Σ 7(1)
(21)
27
Moreover, with > 0 such that ||0*1| < D, and choosing (t)) = LIVII yields:
RA, (O(T)) - R0*)0)) - v2DL,
VT
Proof. Let 2 Using the convexity of f and vb, we can get:
T
R, (O(T)) - Rn <
Σ
f(e(t)) f(0)) + (0) - (00))
T
t=1
T g(())(
Σ
(0(t) - 0*) + 1 Σ (v)()(t) (0()))
<
T
T
==1
>(1 - 1)
|1011
|g(())]
2
2T)
where the second inequality holds since g(t) (f(((t)), and the third one is from an application of Lemma with the choice 0 8". We can conclude the proof provided that [[g(t)) < Ly, which true whenever f is LypTiischitz.
D.1.2 Stochastic Dual Averaging
Similarly to sub- bub-graddent descent algorithms, one can adapt dual averaging algorithm to a stochastic setting; this was studied extensively by Xiao (2009). Instead of updating the dual variable z(t) with the (full) gradient of f at ((t), one now only requires the expected value of the update to be the gradient, that is:
z(t 1) = z(t) + gt))
with ((g(t)
(f(tt)) As in the gradient descent case, convergence results still hold in expectation,
stated in Theorem
28

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Theorem 7 (Stochastic dual averaging). Let (7(1))221 be increasing sequence. Let (z(t))(21, (0(t))(21 and (g()))21 be generated according to slochastic dual averaging rules. Assume that the function I is T.j- Lipschitz and that 0" E arg ein Rn (0'),, then for any T 2 2, one has:
10-11
L
T-1
Er (n((O()) - RR. Rn)
-
Σ
7(t)
(22)
(T>
2T
where Er is the expectation over all possible sequence (g(())
Moreover, if one knows that D > O such that |10'1| < D, then for (() L
12
one has:
V2DL1
Er [R R2 (0)) S
VT
holds in expectation. The rest of Proof- One only has to prove that the convexity inequality in Lemma 6 the proof can be directly adapted from Theorem G
Let T 2 2; using the convexity of f. one obtains:
B-( -(00)) T Er(s(0())) - s(00)
For any < <T ((((t))g(0), ............... g(] ((t). Therefore, we have:
(T( - s(0)) = -E-1(((((() [(0')]
The vector [g()))() is the gradient of f at 0(1); we can then use ʃ convexity to write:
Ea- [()) s E,- [(00)) 8*) T,,l(())(((t))
Using properties of conditional expectation, we obtain:
E B- - 0r) (0) (0) E.- [B,[(O(1) - O0) [(0)0(())) (0()) 0*) g()))
Finally, write:
T TT)
Br(((((1)-f(0))
g(t) = Er T Σ (")
1
Σ (())) TT)
T
Therefore, the convexity inequality holds in expectation and one can adapt the proof of Theorem b to conclude.
D.1.3 Distributed dual averaging
Let Xi,...,X,, X, Rd. We consider functions ff of the form f EI/ f(xx)) In addition, now focus a distributed setting, where each node E [n] holds one observation for simplicity. The distributed dual averaging algorithm for solving (7) was first introduced by Duchi et al. (2010a) and consists in the following: each node E [n] stores its own primal and dual sequences (0,(1), 2, (1) sign- We denote as Z(t) the matrix of dual variables Ztt) = (t), (t)) At iteration + 1, a node will perform the following update:
{
(t++1) g:(t) E (t)
(23)
0,(1+1) (,(2,(1 + (1)
where W is doubly stochastic matrix such that.
(F W =
29

---

Published in Transactions on Machine Learning Research MM/YYYY)
Algorithm 6 Distributed dual averaging
Require: Step size (r(1))221 > 0, weight matrix W
(0) <- 0, (,( <- 0 for each node
2: for / = I.....T do
3:
(tt + 1) + (t) + (tt)
4:
for i= 1, ....., do
5:
(1+++1)+ + no (t (t + 1))
6: end for
7: end forreturn (T))sssss
only differs in the dual update: gradients are now added to an average of neighbors dual variables. Let us point out that the dual update can be reformulated as follows:
Update 23
(t + 1) Gtt) + WZ(t),
where G(t) = (t)....... g (t))
This is detailed in Algorithm 6 The main convergence results of this method can be stated as follows: given a sequence of step sizes (7(1))e20, for any i E [n] and any T >> O, one has
101 2T
L T-1
T-1
3L
f(O, -
yt)
+
max ISJS
Σ (t)lz, -(()l
(24)
2T
T
where ā(() = (1/n (1) is the average dual variable over the network. The first. two terms are related to the dual averaging method and the last one depends on the graph topology. Establishing convergence of a distributed version dual averaging thus relics on finding a communicatio scheme such that the rightmost quantity in 24 is decreasing.
D.1.4 Ergodic dual averaging
The previous analysis is sufficient for providing convergence rate decentralized optimization when the objective is separable in the observations. For pairwise objectives however, an additional look the dual averaging needed. Indeed, one key insight to the method we describe later on is that biased estimates of gradients are computed in opposition to unbiased estimates of the stochastic dual averaging, However, estimate bias decreases exponentially fast, so it should not penalize heavily the convergence rate. We thus study the bias influence using an ergodic analysis.
Problem setting
We define F: x An as follows:
x An
+ R
F
(0,E) + EE. c.1
where An is the simplex in R", i.e.,
A = E R. |1E1 =
Our goal is to solve the following optimization problem:
1 0
min
f(0) = F 8e
f(())
(25)
Throughont this section, make the assumption that there cxists D > 0, such that i X then |0]| S D. Using the dual averaging approach, one aims al finding algorithm for solving problem 25 with "noisy" information, in a way to be defined later. In the dual averaging method with true gradient information, variables are updated as follows:
{
z(t+1) 1) 0 (t++1) = (e(z(t + 1))
z(t)+ + vf(((t))
(26)
30

---

Published in Transactions on Machine Learning Research (MM/YYYY)
As mentioned previously, focus here noisy setting, similar to ergodic mirror descent introduced in Duchi et al. 2012bb. Let. (E()))e2o be sequence on-non necessarily independent-randee variables over An. For { 2 0, we denote as P(t) the distribution of {(t) and we assume that there exists pe such that +om P(t) - 1-pplll 1|vv = 0 and
non
p [F(+))= f
We make the additional assumption that one may not access the true value of VoF (.. 1,/n). Instead, at iteration 1, one can only compute an estimate VoP (()). The ilerative process described in 26 can then be reformulated:
{ z(t+1 = z(t) + V,F(O(t). 0(++1) = (x(+++1))
(27)
Recall that, for any > O, the mixing time of the distribution Ptt) towards its limit pe is defined as follows:
T(t, : E inf {s 2 0, [|t + s|t) po S E)
where ||- ||rv is the total variation distance between two distributions and P(t + s|() is the distribution of E(t + s) conditioned on the natural filtration F, ==
Convergence analysis As mentioned in Section 4.2
the convergence analysis of such a setting relics on for any 0 S < T and any 0r E X, the regret can
one key observation, described Duchi et. al. (201 2b be decomposed follows
T- Σ f(0r))
E (F(0()) - f(0)) ((00)) F(0 E(t T)))
(28)
(F((0),)(++)) - (()
(29)
(F(O(), E(O))
(30)
(1(((1)) - s(0"))
(31)
Following the reasoning of Duchi et al. some bounds actually being expected bounds (see Section D.2 for detailed proofs).
(012b)), we will provide: bound on each term of the decomposition
Lemma 7 (Error after mixing). Let 0 be F-mmesurble variable. Then for any 0" E X and any > 0, has:
Elʃ(0) - f(0)) + F(0, +)) F(0"
< ((
poc |
Lemma 8 (Consecutive iterates bound). Let (8(t))(20 be generated according to (10 Then, for any 2 0:
||0(t + 1) - -(t)] S S3L (1+
2t 21 1))++))-((t))
where for 2 0, [()) (7(()) In addition, (1) x 1a for some (-1,0), then for any 2 0:
1 1
|10(t +) -(0+) s 3L,
1+ 21 +
(a (o++))() = (L))(t)
When a = 1/2, the bound is equivalent to (() when L goes to infinity. bound of other first order methods (gradient descent, mirror descent, etc.).
This is similar to the Lyy(1)
Lemma provides bound over the distance of two consecutive iterates. We now use this result to control term 29 in the regret decomposition.
31

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Lemma 9 (Gap with noisy objectives). Let r 2 0. If (0(t)) is generated according to 10 120 0:
then for ony
+(t++(++)))))) (((((++))))(((()))))))))) (() s 311
(1 21 2T
(I(++))-1(()
Moreover, if (t) & t" for some E (-1,0), one has:
1 +1) (1 +
F(0(t).((t+ - -))
E(t r)) s 3
1+
S =
(t)
2t
Finally, we bound the term 30), which corresponds to the optimization regret. This bound is quite straightforward adpatation from the regular dual averaging algorithm bound in Nesterov (0099).
Lemma 10 (Optimization error). For any 0 E X, one has:
10 L
F(B(t),E(t) F(0", F(0",E(()) S
Σ 7())
(T(T)
2
t=T+1
Proof. For any & E An, E) is convex. Therefore, one has for any 0* E X:
T
Σ E(((t),(()) - F(0,E((t)) & Σ VoE(((t) - 0*)
1=++1
One can then conclude using the definition of (0(t)) and the proof of dual averaging convergence in standard setting see (Nesterov 2009 Theorem 1) for instance.
From now on, we assume that there exists E (-1,0) such that (t) x a. This allows for easier convergence analysis but a more general analysis can still be performed using the bound provided Lemma g We can now apply previous results to the expected regret; for any T 2 0, one has:
T
B((f(((t)) - f(0))) S2LD
P(
+ rlt) P 1lrv
1
+ 3L
Σ
1
(1 + ())(t)
2t 2++1
1=1
10011
1
(f)
(T)
2
1=
+
B((((0()) ((0)))
I=T-++1
We made the assumption 0 D, so f(0(t)) - f(0') < 2LD, and one has the following bound:
B[(((0())- <2LD
IP(L poo ITV
T-r
110-11 (T)
L
6L
7(t)
Σ 7(t)
+LD
Let us assume that the mixing times are uniform, that is for any e > 0, there exists 7(c) such that:
14 72200 0, 7(1,e) & 7(6)
32

---

Published in Transactions on Machine Learning Research (MM/YYY)
Therefore, one has for any 0:
L?
r(t) + |100 1
Σ - 2
T(c)) + 22DDT= (1 127()))
Σ
2
2y(1)
and we can write the following theorem.
Theorem 8 (Ergodic dual averaging). Let (0(1)) be generated according to 10 and let 0" X be
minimizer of the problem 25 We make the following assumptions:
1. There erists (-1,0) such that 7(t) x tt
2. There erists D such that for any A E X, |101| 1 D.
Por any e > 0, there erists T(E) such that for any 2 0, S((,)) r(t).
Then, for any >
E[(((((T)) - f(0)) 2LD ( E-
F(E) T
L
T
110-11
+ 27
[1 + 12T(e))
Σ (t)) + 2T)(TT
(32)
where 0(T) +T= O(1) is the ilerales overage al lime T.
Note that one able to compute VF 1n/n) at every iteration, then 7(e) 0 for any 0 and one can recover the dual averaging convergence rate when <- 0 in (32). This upper-bound evidences the need to compare the mixing time to the optimization rate: if r(e) < vT then similar bounds preserved.
D.2 Proofs
This section is organized as follows. First, we establish proofs in Section D.2.1 for cach lemma involved in the ergodic dual averaging analysis. Then, we perform the analysis of the pairwise decentralized dual averaging in the synchronous case. Finally, we tackle the proof convergence in the fully asynchronous setting.
D.2.1 Ergodic dual averaging
Error after mixing (Lemma
Proof. Let be a Fe-mesurable variable, 0" E X' and 2 0. By definition of P(t + r(t) and pxo the LHS can rewritten as follows:
SELA. EEA.
(F(0,E) (10",)))P='(G EEA.
(F(0,E) F(e", ((("))=F(())))))) ())))(((++)))))))
(33)
Both expectations in be bounded by:
33 only differ from the probability measures involved; the above quantity can thus
JEEA
(F(0,E)
F(00") F(O", (P) -
Using the fact that for any E F(-E) is Lipsscih, one has, for any 0 E X::
[F(0,E) F(0",E) Ly 0 D,
the last inequality deriving from the definition of D. Then the result holds using the definition of the total variation norm.
33

---

Published in Transactions on Machine Learning Research (MM/YYY)
Consecutive iterates bound (Lemma
Proof. Let (z(t), (2)) be generated according to 11 for some positive, non-inereasing sequence (7(1))220-
For any 2 O, we aim at bounding | +1 - {(t) Let s(t) E (v)((t)) and s(t + +1) E (v - 1)). The
respective optimality conditions on (l) and ( + 1) lead the following inequalities:
1 0 0) ( [t
{ (s(1+ 1)z(t (2(1+1)2(t
()(t))(t) - ((t) - ((t)s(t)))
(()) 1)s(t + 1)) (0(t) - 0(t + 1))
(34)
0
Then, using convexity of v and the property of the subgradient leads to:
s(t + 1)T + 1 {
IV Iv
1 (0(t + 1)) ((((t) ()((t) - (0((+
(35)
((()) - O( 1))
Summing both inequalities in 34 and using
35
one obtains:
|0((t + 1) (()]
+ ()z(t))z(tt+++ + ((t)) (0(t ()(+ 0(t))
+ (I (() - ((((t)))
(36)
The optimality of 0(L+ 1) ensures the following relation:
((t 1) z(1 1)
|0(1 + 1)112
2(1 + (((+
[0(())2
( 1)) 2 0(t)
(((())
++1 (t 1)
++1
We can reformulate this last inequality to provide upper bound (0 + 1)) (0(1))
z(t + 1)
((t) - 0( + 1)
(0 + 1)) - (b(t)) (0(t+ - -(t)) T
+
++1
21 +
+(t+1)
+ (0(t + 1) - O(t))
1)
|Iz(t [ + 1)ll
11((t) 0(t + 1)ll
< 110(1 + 1) O(1)
1+1
21( 11)
|0(++1)II
+ 0 + - 0(+)
+(++1)
where the last inequality derived from Cauchy-Schwar, relation. Since m1+1 7t + 1)-Tipschitz and T+41 (0) 0, one has 0 + 1)ll S 7(t + [)]lz(t+ 1)]l- Moreover, by definition of z(t o(++1] 1) and since all fa are L-Lipschitz, one has |z(t - 1)ll (t + 1)L. These two last results lead the following bound:
|0((1) O(L + 1)11"
(0 + 1)) ab (0(I) (T. 0(1)
2r + 1)
Now, we can use this bound in incquality (36
(1- 2T((+1)
I(++ - |10(1 -()) < [1 =)(())))))=)))00000000000 +200000++000000+0000000000000+00 1) T(O)...
The first term in the RHS can be simply bounded as follows:
(I + 1)z(t + 1) - (t))((t)ll S (t + 1)]lz(t + 1) z(t) + -)()++))>())
-
Since [[t + 1) and r(t) are both positive, one has:
r(t + I(t) I(t + 1) + r(t))
2
21(++1)
21(( + 1)
34

---

Published in Transactions on Machine Learning Research (MM/YYYY)
which finally leads to:
(1
(1+2+1)
10 + - s 3L (t - r(t)
((L+1)+TT) 33 - r())
We make the additional assumption that (t) & da for some (-1,0). This is not a particularly restrictive assumption since the dual averaging algorithm imposes that:
1. lim;-0o 7(t) = 0, hence a < O.
2. lim;-xo (1) +00, hence + 1>>00 0.
With this assumption and Taylor-Lagrange formula yields:
r(t+ r(t) s (a+ 1))(t)
and the final result holds.
7
Gap with noisy objectives (Lemma 9)
Proof. Let T, 2 0. One has:
((00))((t+r))--(00++)))))) < L|((()) - 0(t + +T]l
< L
0(t+ +) O(t + 1)1l
8=0
Using Lemma g one has for any 55
[]0(++ s) O(t + s 1) <3L
1+
+
2(t + 8) +1
S3L
1+
1
II(++++))-T(--
21 +1+1
Summing over leads to:
Σ 10( + s) 0(t + 1)1l < 3L
(1+
1 T) -
2t 2t+1
and the first claim holds. We now make the assumption that 7(t) x 1o, with a E (-1, 0). As denoted in the proof of Lemma g one has:
so the second claim also holds.
D.2.2 Synchronous Pairwise Gossip Dual Averaging
In this section, we focus on the synchronous setting. First, we establish a result on the expected dispersion of the dual variables over the nerwork. We then use this result to detail the rale of the decent dual averaging, both for separable and pairwise objectives. Finally, we use the ergodic dual averaging to provide explicit rate of convergence.
In Duchi et al. 2012a4, the following convergence rate for distributed dual averaging is established:
1
L
E R, (0, (T)) (0")
|10-112
7(t 1)
(T)
2T
+ I.f
T.
r(t - 1) Σ
(|22(() 20 + +|((()) (2)))
nT
t=2
j=1
35

---

Published in Transactions on Machine Learning Research (MM/YYYY)
The first part is optimization term, which is exactly the same as in the centralized setting. Then, the second part is network-dependent term which depends on the global variation of the dual variables; the following lemma provides an explicit dependence between this term and the topology of the network.
Lemma 11. Let (G(1))r21 and (Z(t))(21 respectivcly be the gradients and the gradients cummulativv sums of the distributed dual averaging algorithm. If G is connected and non bipartite, then one has for t 2 1:
L
E (t) 2(t)| - 1
where Xn-1 is the second smallest eigenvalue of the graph Laplacian L.
Proof. For t 2 1, let (t)) be the random matrix such that if (i: E E is picked at t, then
W(I) = I, 2(( (e: e,)(e: - -e²)
As denoted in Duchi et al. (2012a), the update rule for can be expressed as follows:
Z(t 1) G(t) ((t)Z(t),
= 0, (() = 0. Therefore, one can obtain recursively for any 2 1, reminding that -
Z(t) Σ W(t:
where W(t: 8) W(I)... W(s + 1), with the convention W(t: = I,- For any 22 1, let W(1) be defined as follows:
W(t) = W(t) - Jn
One can notice that for any 0 05 W(t:s) W(t: s) Jn and write:
z(l) 1() Σ W(())
We now take the expected value of the Frobenius norm:
I(t) - 2, |1 s
E s)
E W( s)
(s) W(I: (s)]
where gl (s) is the i-th column of matrix G(s). Conditioning over Fz-1 leads to:
E
(s)
W(t: 8) T W(L: (s) (2) g 1 W( 1 s)
where >2) is defined in Section A Using the fact that for any 82 0, G < nL?
one has:
E (t) - 2,) s VnL E x2) - Vul.
(2)
Finally, using the bounds between E and fg-nrrs yields:
El (l)z,(t) - 2(t)] <
E
z(t) - 1, 2 1 1 (22
n2
36

---

Published in Transactions on Machine Learning Research (MM/YYYY)
With this bound on dual variables, the convergence rate can be reformulated as follows.
Corollary 2. Let 9 = ([n), E) be connected and non bipartite gruph. Let (+(())e2 be non-increasing and non-negative sequence. For i E [n], let (g.(t))e21, (z,(t))21 and (t)()) be generated according to the distributed dual averaging algorithm. For O" E arg minggenge eR R, (0'), E [n]] and T 2 2, one has:
L T
3L
T-1
([,,((,((T)] - (0') S (T
10112+
+
(1)) 2T 1=1
+
Σ
7(),
T A2222)
where A2 < 1 is the second largest eigenvalue of W2.
We now focus on gossip dual averaging for pairwise functions, as shown in Algorithm 2 The key observation is that, at each iteration, the descent direction is stochastic but also a biased estimate the gradient. That is, instead of updating dual variable (t) with g, (t) such that Elg, (t) = (t), we perform some update d (t), and we denote by (t) the quantity such that Etd, (t) (t) = (lg (t) (f)(
We now prove Proposition T which upper-bound the error with additional bias-dependent term.
Proof. We can apply the same arguments as in the proofs of centralized and distributed dual averaging, for T > 0 and i E [m]:
Er (0, (T)) R., S L
Σ
7(t 1)
>
E
ltz(t) (0()
1=2
1=1
T
L
Σ
7(t - 1)
Σ
||a(t) 2,(1)1|
+ + Σ B((((t) - )-) Tg(t))
n7
1=2
/=1
1=2
T
3L nT
7t - 1) Σ
|2(()) (+)) + Σ ([(((t) - -8)) Tg)))
j=1
The first term can be bound using Lemma
The second term however can no longer be bound using Lemma 0 since the updates are performed with (t) and not (t) = (t(t) - (t). With the definition of (t),, the former yields:
11
T
+
Σ Bl((t) TB))) +
Σ
(áa)) ((t))
t=2
Now Lemma G can be applied to the first term in the right hand side and the result holds.
We now focus on the proof of 2 This results is based both on Proposition and ergodic dual averaging presented in Section D.L.4
Proof. Throughout this proof, we assume &b 0 for simplicity; similar results can however be obtained in the case sb # O. Let i E [n]] and T 2 1. One has:
T
(0,(T)) RO,())) 5
In(1)22)11) 2,00))2,((0) 2|(1
(,(0,(0)-1,000
nT
nT
1=
2L T
T
(())2((() 2(0) + ==
())
nT
nT
The first. term in the right hand side can be bounded using Lemma 11 so we only need to handle the last term. To do so, we adapt the proof of convergence for the ergodic dual averaging to the partial objectives. For j E [n], let us define Fj Rd x A, + R such that for any (0. E IRd x A,:
F((0,E) = Σ (0;x,,,, x6).
37

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Moreover, for t we define (t) {0.1]" n An such that for & [n], E,) e₁ if and only if ()(1) = Xx. Deriving the decomposition of the ergodic dual averaging proof yields:
-(,0,(()--(0)))
(,(0,(0) - -1000000--000+0300000000000011)- F,(0" E, +)))
(37)
(38)
+ Σ -((0)(0)_,00)-((((11
(39)
Σ (t)( f)(0)))
(40)
Bounding the term 37 requires the knowledge of the total variation distance between the random walk
associated after algorithm steps and the uniform. (Chung 1997 Theorem 1.18) states that such norm for one random walk is upper-bounded as follows:
[ 12))
[P -|0) PSolITV 2 minnke()] dk
maXag]a] de However, in this case, the random walk associated to the j-th auxiliary observation will not necessarily be propagated times during 7 algorithm steps. Since we are interested in expected bound, we bound the expected total variation norm as follows:
where )2) is such that )2( <
An-1
E (2))
Bl + -|() Poo TV <
PP
(r(r) =
2 minnel[m] dz
sm0
0
r=t
|E|
(3)
p3(1 (3)
<
2 minke(n] d+
==0 8
EE|
((1 - p3) + + p))) sGG) (()),
2 minke(n] dk
where cGG) = 2 minnee de and c'(G) == maxxe(n) {(1 - pk:) + {2))).
The term 33
provides an upper-bound similar to the centralized ergodic case, as it only depends the
Lipschitz constant L and the step size sequence. When averaging over all j E [n], the term 33 can be upper-bounded as follows:
a
Σ
Σ
- -F)(())))())F((()))))))
J= 1=
(F)(0,()),E)())) F,(((t),E,(tt) FF(00,))))))) + (1())
n |=
- Σ
(0)l,, -2())))) + Σ (0)
t=1t
which can then be bounded similarly to Proposition in the centralized case.
Finally, the last term 40 is bounded by 2rLD,
38

---

is picked at iteration t Published in Transactions on Machine Learning Research (MM/YYYY)
Algorithm 7 Gossip dual averaging for pairwise function in asynchronous setting
Require: Step size (r(t))(2u> > 0, probabilities (pa)ke(n)
yi < Xi, 2: <- 0, 0: < 0, 0, <- 0, my for each node i [1c]
2: for L 1==1,... I...,, do
3: Draw (i.j) uniformly at random
4: Swap auxiliary observations: Y: ++ yj
5:
for k E {i.j} do
6:
Zk + 1:421
7:
=s Ph
VoS (Oxixa,
8:
my - my Pk
9:
02 + kmg (2t)
10:
Ū. <- MpPE)
0x
11: end for
12:
end for
13:
return Each node & [n]] has 0s
D.2.3 Asynchronous Pairwise Dual Averaging
For any variant of gradient descent over network with decreasing step size, there is need for common time scale to perform the suitable decrease. In the synchronous setting, this time scale information can be shared easily among nodes by assuming the availability a global clock. This is convenient for theoretical considerations, but is unrealistic many practical (asynchronous) scenarios. As in the decentralized esti- mation framework considerod in the appendix, we place ourselves here in fully asynchronous sctting where each node has a local clock, licking at Poisson rale of independently from the others and we use the time estimators (ma)isk<n defined as follows:
my (t) = =
me(t 1) + Pk (t -
otherwise
Using these estimators, we can now adapt Algorithm to the fully asynchronous case, as shown in Algo- rithm 7 The update step slightly differs from the synchronous case: the partial gradient has a weight 1/ps instead so that all partial functions asymptotically count in equal way in every gradient accumulator. In contrast., uniform weights would penalize partial gradients from low degree nodes since the probability of being drawn proportional to the degree. This weighting scheme essential to ensure the convergence to the global solution. The model averaging step also needs to be altered: in absence of any global clock, the weight 1/t cannot be used and is replaced by 1/(maPH)) where m&Ps corresponds to the average number of times that node k has been selected so far.
The following result is the analogue Proposition I in the asynchronous framework.
Proposition 3. Let G ([n), E) a connected and non biportite graph. Let (7(1))221 be defined as 7(1) = /2ta for some constant. c and a E (0, 1/2). For E [n], let (2((1))221 and (0,(1))s2 be generated as described in Algorithm 7 Then, there exists some constant < to0 such that, for 0" E arg eRe F(O'), E [n] and T > 0,
T Σ T B((((() - T2(1)
(T), - F(0") <C mT a/2 a/aa///a-1//)) +
The main difficulty in the asynchronous setting is that each node i has to use time estimate m, instead of the global clock reference (that is no longer available in such a context). Even if the time estimate is unbiased, its variance puts an additional error term in the convergence rate. However, for an iteration T large enough, one can bound these estimates as stated bellow.
Lemma 12. There ezists Ti > 0 such that for any 2 Tı, any le E [n] and any q > 0,
1= L- 11+o m²(1) t. 1 = 1t
39

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Proof. Let & E [n]. For 2 1, let us define (t) such that (t( if k is picked at iteration and 5tx(t) 0 otherwise. Then one has (1) (1/pk) Σ = (t). Since (d)())) is a Bernoulli process of parameter
1/ps, by the law of iterative logarithms Dudley (2010), (Nedić 2011 Lemma 3) one has with probability 1 and for any q O, lime-++o
my (0)+0) O, and the result. holds.
12
Theorem 9. Let G = ([n), F.) be a connected and non bipartite graph. Let (7(()) be defined as 7(t) c/t//2ta for some constant c > 0 and a E (0, 1/2). For E [n], let (zi(t))21 and (0,(t))(21 be generated stated previously. For 0 E arggming minorere (6'), i E [n] and T > 0, one has for some C:
-((1)))RRR,00 Rn)O((T))- R., (0') s C ma 1/2)
B(2(t)T@())
Proof. In the asynchronous case, for E [n] and L 2 1 one has
T 8,(1)
( m:
0.(1)
Pi
Then, using the convexity of Ra, one has:
T
(t(t)
Ey [T,R,,0,(TT)) (0') s E
R. (0,(t)) Rn))"))
(41)
(T)
Pi
By Lemma 12 one has for q g>0
E R. (O,( (0')
1 T
T
(t(())
RA (0(()()) Rn)("))
pi
Similarly to the synchronous case, one can write
(t)
(.(t)
E
((O.(1)
= Σ E
((0(()))
p:
Pf
8,(1) (,,(0,()) ((0((0))
8.(11)
(0,(0)))
E
E f
Pt
pt
In order to use the gradient inequality, we need to introduce (,,(),((0(()) instead of (0, For
j E [n], one has:
T T
(t (,),(()))
1 T
T ΣE E
(
6:((t)
8,(() f)((,(t))+ + 6,(t)
Pj ),
E
P
Ps
Let Nj- = ΣT 1
(1(1)
and 24 <... < <NN, S T be such that (1x)x = 1 for E [N3]. One can write
1
6,(t)
8,((()
1(00,(0))
13
(42)
T
Pi
Pj
E
N1
11-1-1
8,(t)
1
f((0,((w))
Σ
f1
8,(t) P:
((,,000)
Pt
Pj
t=
8,(())
E
[,(0,(NN,))
T
Pi
P5
|=N,
N
1141-1
8:(1))
1
50
13Ely(tN, - -1]
R
Σ
((0
Pi
pj
P:PST
PiPj
t=
40

---

Published in Transactions on Machine Learning Research (MM/YYYY)
We need to study the behavior of 6, and dj in the first term of the r.h.s.
N
1
E
5.(1)
1
((00(()))
P3
1=
r=
N, -
++++1
E
E
belt)
Lxs lx+1
[0(00(w)))
Pi
6t(t) will not have the same dependency in ty whether and j are connected not. Let us first assume that
(i,j) E. Then,
[())(()))(4] = (0) = 1] d.j
Also, for la < < 1++1, we gel:
(10(0)) ((6,())6, - 0] P; 2
Pj
Finally, if (i,)) E E, we obtain
T
(t)
= -(t
d + (1x+1 t - 1) - - 2/ E
E
Σ
1x+1
Pi
1 Pj
Pi
Before using this relation in the full expectation, let us denote that since tx+1 is independent from the one can write
( d
to -
1
= dg
1 (1-P) Pj
Pt -2/
E
+ (te+1
t
Pj
Pi
Pj
1 - Pj
Pi
Pj
We can now use this relation in the full expectation
(t(t)
(,(()
Er
11(05(t))
Pr
Pj
N3
1
6x(t)
E
tx+1
tb
((
=0.
(43)
pi
Pj
Similarly (1,5)= & F, one has
= = ((,,((+))44 (1)
and for to < < t++1,
[(O(()) =00,
Pi
I-P;
so the result Equation 43 holds in this case. We have just shown that for every j E [m]. we can use
(1))p) instead of (0)) Combining 41 and 42
yields:
1
5,(t)
(U,(0.()) [000000)
E,R R, (0') < nT
E
Pr
1=2
J=1
T
8,(()
(((00,(1)--((0)))
E
n
Pj
0:(1)
Σ
(v)()(()) ((0)
T-
Px
(0)
L3 - 1)]
P.P;T
PiPj
41

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Let us focus the second term of the right hand side. For t 2 2, one can write
8t(t) Pj
(1)(0((1) - 1((01)) -1)00))))0000))00)))))))))))))))
E
6,(t)
g,
(t)
(0,(t) (0-())00) 04)
Pj
(1(1)
Σ
R
(1) T (0,(1)
Pj
1=1
66 (t((t)
Σ
E
8y (t) (0(()) 8')
(44)
Pj
Here we control the term from
44
using (+t) == Tm, (1) (2(t))
T
(t)
1 Σ
1 8y(t)
gy (t) T (o)(t (2(()))0) 07) =E
(t(
(a(t) (0(t) -0)
71
Pj
TE j=1 Pj
E [B()) (G()) - 0¹)
and the reasoning of the synchronous case can be applied to obtain
8t(t)
E
g (t)T((() - 00)
Pj
t=2
j=1
L2
T
1012
T
T B ((1) + - Σ E(v0)) - (())(()
Σ
7t - 1)
T Σ
(45)
27
(T(
We have:
T
8,(1)
T
E
(0()(()) - *(07))
+ T Σ
(w(00) - E((((()))
Pi
T
(t)
((0((1)) - -(()))
E
Ps
(t)(t)
T
81(t)
EE
(t) v((()))
+ T
EE
1){(((())
Pr
Pi
2=
t=2
(5((t)
(1b ())()(()) (((1))
Ps
where we have used for the last term the same arguments as in 43 to state 0. Then, one can use the fact that ne is (ipssiiss to write:
T 21=2
1
E (((l))
1)((((t))
ΣE E (ilmmi(t11)][22( (+]l+ (m, - (1))((((()) 2;(1)112
P E
2(m,(t -1))
42

---

Published in Transactions on Machine Learning Research (MM/YYY)
Provided that yt) I C/V² for some constant C, then using Lemma 12 we can bound this term by C//VT.
Let us now control the following term:
o5(()
8y -()(0))))) 2(0)
E
-
Pj
L
E [|le, (+)l
(46)
np
L
E [100,(]) 0,00| +10,(0) -
npp
L,
Σ
E (t
2()) + (10 (()ll
npj
where (t) (t- (t-((()))(((t) We can apply Lemma 13 with the choice 01 = (t),), 02 = @()), t = =t,(t).
z(t)).
la = =l) and 2(1):
[[ā(1) - 0,,(
[[((t)ll((m(()))
+ |[((t)]
3 max
((m)(t)) (mm((t)
(())(()) )) (mm m.(t)
my(t) (m,(tt)
((m,(t)) (mm
3 + [t))
(mm((1) ( (4)) (m,(
(t, (m, (t))
ml((1)
max
((m,(t)) ((nn(t))
We use Lemma
12 with the choice g = a:/2, so we can bound for t large enough the former expression by a
term of order || (() - (mm,(t))
Note also that |(((t)|| Σ L. max;=1,.... me((), so for large enough
we obtain:
[+)(t) (t)l < Lt
Ltthhhhtt hn(t)))()))))))))tt))) ((t)|
With the additional constraint that the step size is of the form 71) C1-1/2-a the term |[((1) O,(() is bounded by C't-a/2 for t large enough, and so is (1/n) E E 8,(1)
Py 9, (())()())))))))))))))))))))))))) - -
To control the objectives, we use that ʃj is L-Lipschitz
())()(()) - [0(0 < (1) - 0,) < L(1 - ( + (0(1) - O,0I
and we use now the same control as for hence the result.
Lemma 13. Lel. y: : RR+ - R2,, be non-increasing posilève function and let E Rdd. For any 1, > 0, one.
has
(3 - + ||2l
(2 + max ((1)) 7(12)
1 +
()) [(n((1)-
||0₂ - 101-0 [12111((()) 7(1)
(2>(6)))))
(1z)) 7(1))
4
where, for E (1,2).
||0|2
0: = (z) == arg max
Z 0
(7,t,)
BER4
Proof. Using the optimality of the minimizer, for any E (01) (resp. 82 On (02)):
- (02 10--0.. 01) < 0
- T
(x(t2)z- - T() 02) < 0
43

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Re-arranging the terms, and using properties of sub-gradients yields:
|0 011l (()((2)) (((1))z 01) (117(11)s1 (t2)))))))) (02 01)
(47)
<(7((2) - (((1)) (02 -2)- 01) + (t17(tt) - (27((6)) (01))
Also, using the definition of 01 and 02, one has:
3 (0)(1;) (0 ) - | 01 02ll (
max ((1)) 2(22)
t -b5b) (1)+))
(48)
7(t2) ((1))
With relations 47 and 48 we bound the distance between 02 and 02 as follows:
{ + max ((11) 2(te)) ) (+ + 1t) ( - t27
|00 - 01ll < ((2) - (t1) ||z||
(122 7(41)
D.3 Proof of Theorem 3
In this section, we state the proof of Theorem 3
Proof. Let G = (m)),)) be connected graph. We consider decentralized first-order methods that, at each iteration, can query local (sub)gradients and exchange messages along E. For simplicity, we assume unit per-hop latency т = 1; heterogencous latencies only change the bound by a multiplicative factor.
Following Scaman et al. (2018), the idea to construct an objective function whose coordinates must be activated sequentially, forcing information to alternate between two distant nodes of the network. Fix nodes io. i V. Consider the local functions
| + n 7 Et= 102m41 02rl - 30.] -30
if i0.
(0(
1110 + Et= 102r - 02r-111 + 0024+1 if j = i1 otherwisc.
T 1101
Here > O controls strong convexity, while 7,8,8 0 control the nonsmooth pero-preserving terms. The overall objective F(0) : E, (0) is convex, nonsmooth, and designed so that cach gap |02r41 02r is controlled by io. and each gap (2r -2r-82p -2 by i,. Starting from (0) = 0, first-order algorithm can activate at most one new coordinate per communication round between in and i
In the centralized setting, the nonsmooth lower bound is obtained by considering the family of functions (?, see Lemma 3.1):
s(0) -- 1 max 0,
Isist
This function is convex and 1-Lipschitz on the fg ball of radius R= = Vt, and a-strongly convex. For any deterministic first-order algorithm, after s oracle calls the error satisfies
RL ((O(T)) - VT+
for some universal constant c > 0. This lower bound relies on the fact that cach oracle query can reveal information about at most one active coordinate in the max-term, hence the suboptimality decays only 1/VT.
In the decentralized setting, each activation requires communication round-trip between tn and in, of length at least 2dg (io, i1), where dg(-.-) is the graph distance. This dilates the effective time parameter by 2dg (io, it), and the careful analysis in Scaman et al. 2018) yields, for any i E [n]:
RL
1
((), - min F(0) 2
(1o. tz))) + +
|
36
(1 + (1+g)(22g(in
44

---

Published in Transactions on Machine Learning Research (MM/YYY)
where (g( 11) is the distance between nodes tn and i1- Selecting tn and to maximize this distance yield bound where dg( i1) can be replaced by the graph diameter A.
In our setting, each local function fi decomposes as sum of pairwise terms
f((0) Σ (0),
jEim]
where each Jú is stored jointly at the pair (i,j) and depends on both nodes. We can therefore split the nonsmooth chain terms of the previous construction across the network.
Specifically, let :o. E [n] and ji. E [n]] be two sets of distinct, intermediary nodes. We then define pairwise functions fwo as follows:
11 - n 01
if u = v == io:
0 + nă 0
if u t1
Jun (0)
|| + ny 10 02rl
if (u, v) Ju.))
||101 + ny 10/r 02 if (u, v) = (11,)1.));
1110122
otherwise.
The global objective F(0) remains unchanged, but now, computing the gradient of fiodo.r (resp, Jur..) requires routing information from jo.r to ip (resp. jir to i1). This effectively replaces cach occurrence of de (g(oo,81) i1) in the activation time by the length of the path from in to jo,r and from jur to well as from in to jı, and from jı,
Let do(to, i1) be the average effective communication length between in. i and intermediary nodes, that is
2k Σ
Jo.r) + dg in) + (i. + do
This quantity represents the average commanication length per coordinate activation, i.e., the effective dis- lance that must be covered by each new gradient piece, on average. Repeating the same zero-preserving argument as Scaman et al. (0018) and optimizing over (ig,2) then gives the lower bound:
RT.
F(O,(t)) min F(O) 2 |0|SR
36 V (1+1/A)²
+ i+1
E Multiple points per node
Proof. Denoting the Kronecker product by 8, can write:
G = 1
and D kI, & D
Recall that L D A and 0 D A Let (Ø. E R x R be an eigenpair of L i.e.,
(DG 6 x = XΦ and Φ + O. Lot us write & = [Φ] I where , Φx E R.. Exploiting the
structure of A G and D we have:
DD O.
A AG = N
for all i [k].
(49)
1=1
Summing up
44 over all E [M] gives
k
k
&
D
G
Φ
Σ
Φ
Φ
k
1=1
i=1
45

---

Published in Transactions on Machine Learning Research (MM/YYYY)
which shows that if (Ø, A) is eigenpair of L with E Φ, O, then (Ei=1 ((,/k) is cigenpair of
L In the case where Eis1 Ø; = O, then there exists an index j E [k] such that Φ = -ip Φ3 * 0. Hence gives
49
D R
which shows that ( A/K) is an eigenpair of L Observe that X = kd, for some i E [ne].
We have thus shown that any eigenvalue R of _ is either of the form A = kXC, where G is an cigenvalue L or the form A = kd, for some E [n]]
Since L is a Laplacian matrix, its smallest eigenvalue is O. Let A be the second smallest cigenvalue of L Note that G not a complete graph since G is not complete. Therefore, A is bounded above by the vertex connectivity of G (Feddle 1973), which is itself trivially bounded above by the minimum degree d [kn] [ G of G This implies that n k\g 1: and hence
A
G kn
KGG
1 G (2)
E
1:2 E
46


Reviews:
[{"review_id": "cAEIawH9yT", "reviewer": "Reviewer_q5Em", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of analyzing gossip algorithms for pairwise objectives in decentralized settings. Focusing on objectives formulated as U-statistics of degree two, the authors provide a non-asymptotic convergence analysis of the GOSTA algorithm. Additionally, the work establishes a theoretical framework by deriving fundamental lower bounds for learning with pairwise objectives in distributed environments.\n\n\nStrengths\n\n- The paper provides a clear and mathematical introduction to gossip algorithms and establishes a good notation framework for the problem setting.\n\n-  The paper attempts a rigorous non-asymptotic analysis, addressing a gap in the literature regarding the expected error (variance + bias) of the GOSTA algorithm, rather than just the bias.\n\nWeaknesses\n\n- The introduction fails to compellingly justify the problem setting. The connection between general IoT/sensor network discussions and the specific pairwise objective contributions is unclear.\n\n- Section 2.2 introduces the pairwise objective abruptly without sufficient motivation or simple examples. It is unclear to the reader why decentralized pairwise averaging is a critical problem worth solving compared to standard averaging.\n\n- The paper spends a significant amount of space (Sections 1-3.1) recapping background and existing algorithms (e.g., GOSTA from Colin et al., 2015). The novel contributions do not appear until Section 3.2, making the first half of the paper feel repetitive of prior work.\n\n- Proposition 1 is presented without discussing the technical challenges involved in the derivation. The authors do not clarify how their analysis overcomes the difficulties of U-statistics in a decentralized setting compared to existing work. Is the expectation inside the norm in Proposition 1? \n\n- The paper is purely theoretical and lacks empirical evidence. Experiments demonstrating the convergence behavior and the practical benefits of the proposed analysis on real-world datasets would help to validate the theoretical claims.", "claims_and_evidence_yn": "No", "claims_explanation": "Please refer to the weakness above.", "audience_yn": "Yes", "audience_explanation": "The paper focuses on non-asymptotic analysis of gossip algorithms for pairwise objective, which can be of interest for theoretical research in this area.", "requested_changes": "Please address the weakness mentioned above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JVsGvkXtz2", "reviewer": "Reviewer_sSar", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studied the decentralized optimization problem where the loss function is not separable across nodes. This problem setting encompasses several applications, including ranking and clustering. First, this paper analyzed the convergence behavior of the existing method, GOSTA-Sync, and provided a novel analysis of it. GOSTA-Sync is the method to estimate the function defined in Eq. (5). \nMore specifically, the existing analysis established the convergence of $\\| \\mathbb{E} [z] - \\hat{U}_n \\mathbf{1}_n \\|$, while this paper analyzed $\\mathbb{E} \\| z - \\hat{U}_n \\mathbf{1}_n \\|$. Then, this paper studied the optimization problem described in Eq. (7), and analyzed the existing optimization method, described in Algorithm 2. The convergence rate is analyzed in Theorem 2 and Corollary 1.", "claims_and_evidence_yn": "Yes", "claims_explanation": "## Strength\n* The problem that this paper addressed seems to have several interesting applications, including clustering and ranking.\n* This paper provided the refined analysis for the existing methods, GOSTA-Sync and Algorithm 2.\n\n## Weakness\n* The convergence rate presented in Corollary 1 is strange. The left-hand side represents function values, while the right-hand side is, roughly speaking, of order $O(L^2)$. These two sides have different units. More specifically, let the unit of the function be $[f]$ and the unit of the parameter be $[\\theta]$. The unit of the Lipschitz coefficient is $[f] / [\\theta]$. Thus, the left-hand side has unit $[f]$, whereas the right-hand side has unit $( [f] / [\\theta])^2$. It appears inappropriate to compare quantities with different units. I suspect that there might be an error in the proof or that the choice of hyperparameters, e.g., $\\gamma (t)$, is suboptimal, or $\\| \\theta_0 - \\theta^\\star\\|$ is missing. \n* Can the author show the explicit equation hidden in $o(1/ \\sqrt{T})$ in Corollary 1? The remaining terms are also $O(1 / \\sqrt{T})$, and it is unclear whether $o(1 / \\sqrt{T})$ diminishes faster than the rest.\n* The quantity of $D$ in Theorem 2 and Corollary 1 seems not to be defined.\n* The convergence rate shown in Theorem 3 looks a bit strange. The left-hand side and right-hand side depend on $R$, and it is a bit hard to understand this lower bound. This paper claims that \"The lower bound for decentralized pairwise optimization is similar to the known lower bounds for separable objective\" in page 13, but this paper did not cite the reference. Can the authors cite the appropriate reference here and provide additional discussion on $R$? Furthermore, is it guaranteed that the left-hand side is always positive?\n* Is a gossip-based method truly communication-efficient for the problem addressed in this paper? For example, when solving the problem in Eq. (6), each node $k$ can obtain all the observations $\\\\{ x_j \\\\}_{j=1}^n$​ in finite time by using some operation. The required communication cost in this case seems to be proportional to the diameter of the communication graph. Compared with such a simple approach, methods like GOSTA-Sync and Algorithm 2 appear to be less communication-efficient. In what kind of scenarios is it necessary to use gossip-based methods?\n* This paper did not check the performance of these methods numerically.", "audience_yn": "Yes", "audience_explanation": "The problem addressed in this paper appears to be important, and it is good that this paper analyzes the convergence behavior of basic methods, such as GOSTA-Sync and Algorithm 2.", "requested_changes": "See the weakness section.", "broader_impact_concerns": "There are no ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lrwUpQPZcr", "reviewer": "Reviewer_Qri3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses a gap in centralized machine learning, specifically in estimating and optimizing functions that involve pairwise dependencies on the data that is, U-statistics of degree two. The paper makes a strong and clear contribution to this problem by refining and extending the work of Colin et al. on decentralized estimation and by deriving new bounds for decentralized optimization (all focused on degree-2 U-statistics). The authors clearly articulate these contributions in the introduction.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Yes, all theoretical claims are supported by theorems and corollaries, each accompanied by proofs. Some empirical statements could be further validated through experiments, which would improve the quality of the paper.", "audience_yn": "Yes", "audience_explanation": "Yes, definitely! In terms of importance and relevance, the proposed results are highly informative for the community. They provide a theoretical analysis of a practical algorithm that explicitly depends on key quantities such as the data \"dispersion\" and network topology. Moreover, the analysis of the bias term $C_3(T)$ is technically valuable and, I believe, represents a great contribution of the paper.", "requested_changes": "Overall, I find the paper to be of high quality. My only suggestion would be to include some simple experimental evidence to support the theoretical claims. The paper mentions multiple times that empirical results confirm the theory and that the bias term vanishes quickly in experiments; however, including a few plots to illustrate this behavior would make those claims more convincing.", "broader_impact_concerns": "I don’t think the paper raises any ethical implications or concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)