Random Pairwise Gossip on CAT(k) Metric Spaces

28/10/2015
Publication GSI2015
OAI : oai:www.see.asso.fr:11784:14297

Résumé

In the context of sensor networks, gossip algorithms are a popular, well established technique, for achieving consensus when sensor data are encoded in linear spaces. Gossip algorithms also have several extensions to non linear data spaces. Most of these extensions deal with Riemannian manifolds and use Riemannian gradient descent. This paper, instead, studies gossip in a broader CAT(k) metric setting, encompassing, but not restricted to, several interesting cases of Riemannian manifolds. As it turns out, convergence can be guaranteed as soon as the data lie in a small enough ball of a mere CAT(k) metric space. We also study convergence speed in this setting and establish linear rates of convergence.

Random Pairwise Gossip on CAT(k) Metric Spaces

Collection

application/pdf Random Pairwise Gossip on CAT(k) Metric Spaces Anass Bellachehab, Jérémie Jakubowicz

Média

Voir la vidéo

Métriques

103
8
353 Ko
 application/pdf
bitcache://3e8da15a44f3d0c65e2a9a8ce393d09882c8b90e

Licence

Creative Commons Attribution-ShareAlike 4.0 International

Sponsors

Organisateurs

logo_see.gif
logocampusparissaclay.png

Sponsors

entropy1-01.png
springer-logo.png
lncs_logo.png
Séminaire Léon Brillouin Logo
logothales.jpg
smai.png
logo_cnrs_2.jpg
gdr-isis.png
logo_gdr-mia.png
logo_x.jpeg
logo-lix.png
logorioniledefrance.jpg
isc-pif_logo.png
logo_telecom_paristech.png
csdcunitwinlogo.jpg
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/11784/14297</identifier><creators><creator><creatorName>Jérémie Jakubowicz</creatorName></creator><creator><creatorName>Anass Bellachehab</creatorName></creator></creators><titles>
            <title>Random Pairwise Gossip on CAT(k) Metric Spaces</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2015</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sun 8 Nov 2015</date>
	    <date dateType="Updated">Wed 31 Aug 2016</date>
            <date dateType="Submitted">Tue 15 May 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">3e8da15a44f3d0c65e2a9a8ce393d09882c8b90e</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>24687</version>
        <descriptions>
            <description descriptionType="Abstract">
In the context of sensor networks, gossip algorithms are a popular, well established technique, for achieving consensus when sensor data are encoded in linear spaces. Gossip algorithms also have several extensions to non linear data spaces. Most of these extensions deal with Riemannian manifolds and use Riemannian gradient descent. This paper, instead, studies gossip in a broader CAT(k) metric setting, encompassing, but not restricted to, several interesting cases of Riemannian manifolds. As it turns out, convergence can be guaranteed as soon as the data lie in a small enough ball of a mere CAT(k) metric space. We also study convergence speed in this setting and establish linear rates of convergence.

</description>
        </descriptions>
    </resource>
.

Gossip in CAT(κ) metric spaces Anass Bellachehab J´er´emie Jakubowicz T´el´ecom SudParis, Institut Mines-T´el´ecom & CNRS UMR 5157 GSI 2015 Palaiseau October 28 1 / 21 Problem We consider a network of N agents such that: The network is represented by a connected, undirected graph G = (V , E), where V = {1, . . . , N} stands for the set of agents and E denotes the set of available communication links between agents. At any given time t an agent v stores stores data represented as an element xv (t) of a data space M. Xt = (x1(t), . . . , xN(t)) is the tuple of data values of the whole network at instant t. 2 / 21 Problem (cont’d) Each agent has its own Poisson clock that ticks with a common intensity λ (the clocks are identically made) independently of other clocks. When an agent clock ticks, the agent is able to perform some computations and wake up some neighboring agents. The goal is to take the system from an initial state X(0) to a consensus state; meaning a state of the form X∞ = (x∞, . . . , x∞) with: x∞ ∈ M. 3 / 21 Random Pairwise Gossip (Xiao & Boyd’04) x0 =     −1 −1 1 −1 −2 1 1 2     4 / 21 Random Pairwise Gossip (Xiao & Boyd’04) x0 =     −1 −1 1 −1 −2 1 1 2     4 / 21 Random Pairwise Gossip (Xiao & Boyd’04) x1 =     0 −1 0 −1 −2 1 1 2     4 / 21 Random Pairwise Gossip (Xiao & Boyd’04) x1 =     0 −1 0 −1 −2 1 1 2     4 / 21 Random Pairwise Gossip (Xiao & Boyd’04) x1 =     0.5 0.5 0 −1 −2 1 0.5 0.5     4 / 21 Random Pairwise Gossip (Xiao & Boyd’04) x1 =     0.5 0.5 0 −1 −2 1 0.5 0.5     4 / 21 Random Pairwise Gossip (Xiao & Boyd’04) x2 =     0.5 0.5 −1 0 −1 0 0.5 0.5     4 / 21 Random Pairwise Gossip (Xiao & Boyd’04) x∞ =     −0.25 0.25 −0.25 0.25 −0.25 0.25 −0.25 0.25     4 / 21 Random Pairwise Gossip (Xiao & Boyd’04) x∞ =     −0.25 0.25 −0.25 0.25 −0.25 0.25 −0.25 0.25     xn = I − 1 2 (δin − δjn )(δin − δjn )T xn−1 4 / 21 A natural extension in a metric setting 5 / 21 A natural extension in a metric setting 5 / 21 A natural extension in a metric setting 5 / 21 A natural extension in a metric setting 5 / 21 A natural extension in a metric setting 5 / 21 A natural extension in a metric setting 5 / 21 A natural extension in a metric setting 5 / 21 A natural extension in a metric setting 5 / 21 Outline 1. Motivation 2. State of the art 3. CAT(κ) spaces 4. Previous result for κ = 0 5. Why the κ > 0 case is more complex 6. Our result 6 / 21 Motivation In its Euclidean setting, Random Pairwise Midpoint cannot address several useful type of data: Sphere positions (Sphere) Line orientations (Projective space) Solid orientations (Rotations) Subspaces (Grassmanians) Phylogenetic Trees (Metric space) Cayley graphs (Metric space) Reconfigurable systems (Metric space) 7 / 21 State of the art Consensus optimization on manifolds : [Sarlette-Sepulchre’08],[Tron et al.’12],[Bonnabel’13] Synchronization on the circle : [Sarlette et al.’08] Synchronization on SO(3) : [Tron et al.’12] Our previous work: Distibuted pairwise gossip on CAT(0) spaces Caveat: In this work, we deal the problem of synchonization, i.e. attaining a consensus, whatever its value; contrarily to the Euclidean case where it is known that random pairwise midpoints converges to ¯x0. 8 / 21 CAT(κ) spaces Model spaces Consider a model surface Mκ with constant sectional curvature κ: κ < 0 corresponds to a hyperbolic space κ = 0 corresponds to a Euclidean space κ > 0 corresponds to a sphere Geodesics Assume M is a metric space equipped with metric d. A map γ : [0, l] → M such that: ∀0 ≤ t, t ≤ l, d γ(t), γ(t ) = |t − t | is called a geodesic in M; a = γ(0) and b = γ(l) are its endpoints. If there exists one and only one geodesic linking a to b, it is denoted [a, b]. 9 / 21 CAT(κ) spaces (cont’d) Triangles A triple of geodesics γ, γ and γ with respective endpoints a, b and c is called a triangle and is denoted (γ, γ , γ ) or (a, b, c) when there is no ambiguity. Comparison triangles When κ ≤ 0, given a triangle (γ, γ , γ ), there always exist a triangle (aκ, bκ, cκ) in Mκ such that d(a, b) = d(aκ, bκ), d(b, c) = d(bκ, cκ) and d(c, a) = d(cκ, aκ) with a = γ(0), b = γ (0) and c = γ (0). b a c l l l bκ aκ cκ l l l 10 / 21 CAT(κ) spaces (cont’d) CAT(κ) inequality A triangle (γ, γ , γ ) in a metric space M satisfies the CAT(κ) inequality if for any x ∈ [a, b] and y ∈ [a, c] one has: d(x, y) ≤ d(xκ, yκ) where xκ ∈ [aκ, bκ] is such that d(aκ, xκ) = d(a, x) and yκ ∈ [aκ, cκ] is such that d(aκ, yκ) = d(a, y). b a c x y d d ≤ dκ bκ aκ cκ xκ yκdκ A metric space is said CAT(κ) if every pair of points can be joined by a geodesic and every triangle with perimeter less than 2Dκ = 2π√ κ satisfy the CAT(κ) inequality. 11 / 21 Formal setting Assumptions 1. Time is discrete t = 0, 1, . . . 2. At each time each agent holds a “value” xt,v in a CAT(κ) metric space M 3. At each time t, an agent Vt randomly wakes up and wakes up a neighbor Wt, according to the probability distribution: P[{Vk, Wk} = {v, w}] = Pv,w > 0 if v ∼ w 0 otherwise Algorithm description xt,v = Midpoint(xt−1,Vt , xt−1,Wt ) if v ∈ {Vt, Wt} xt−1,v otherwise 12 / 21 Previous result The algorithm is sound Because geodesics exist and are unique in CAT(0) spaces. Convergence The algorithm converges to a consensus with probability 1, whatever the initial state x0. Rate of convergence Convergence occur at a linear rate: define σ2 (x) = v∼w d2 (xv , xw ) ; then, there exists a constant L < 0 such that Eσ2 (Xk) ≤ C0 exp(Lk) 13 / 21 What changes for the κ > 0 (the case of the sphere) 14 / 21 What changes for the κ > 0 (the case of the sphere) 14 / 21 What changes for the κ > 0 (the case of the sphere) 14 / 21 What changes for the κ > 0 (the case of the sphere) 14 / 21 What changes for the κ > 0 (the case of the sphere) 14 / 21 What changes for the κ > 0 (the case of the sphere) 14 / 21 What changes for the κ > 0 (the case of the sphere) 14 / 21 What changes for the κ > 0 (the case of the sphere) 14 / 21 What changes for the κ > 0 (the case of the sphere) 14 / 21 Our result Provided the diameter of the initial set of values is less than Dκ/2, The algorithm is sound Because geodesics exist and are unique using this restriction. Convergence The algorithm converges to a consensus with probability 1. Rate of convergence Convergence occur at a linear rate: define σ2 (x) = v∼w χκ (d(xv , xw )) ; with: χκ(x) = 1 − cos( √ κx) then, there exists a constant L ∈ (−1, 0) such that: Eσ2 (Xk) ≤ C0 exp(Lk) 15 / 21 Before iteration xt−1,u • xt−1,Vt • xt−1,Wt• 16 / 21 After iteration xt,u • xt,Vt xt,Wt • • • 16 / 21 Net balance xt−1,u • xt−1,Vt • xt−1,Wt•xt,Vt xt,Wt • 16 / 21 Sketch of proof (Net balance) Let us look at the increments: N(σ2 κ(Xt) − σ2 κ(Xt−1)) = −χκ(d(XVt (t − 1), XWt (t − 1))) + u∈V u=Vt ,u=Wt Tκ(Vt, Wt, u) with: Tκ(Vt, Wt, u) = 2χκ(d(Xu(t), Mt)) − χκ(d(Xu(t), XVt (t − 1))) −χκ(d(Xu(t), XWt (t − 1))) Using the inequality: χκ d p + q 2 , r ≤ χκ(d(p, r)) + χκ(d(q, r)) 2 17 / 21 Sketch of proof (Two propositions) We can prove the a first propostion: E[σ2 κ(Xk+1) − σ2 κ(Xk)] ≤ − 1 N E∆κ(Xk) with: ∆κ(x) = 1 2N v∼w {v,w}∈E Pv,w χκ(d(xv , xw )) Using graph connectedeness we prove a second proposition: Assume G = (V , E) is an undirected connected graph, there exists a constant CG ≥ 1 depending on the graph only such that: ∀x ∈ MN , 1 2 ∆κ(x) ≤ σ2 κ(x) ≤ CG ∆κ(x) 18 / 21 Sketch of proof (cont’d) The following lemma Assume an is a sequence of nonnegative numbers such that an+1 − an ≤ −βan with β ∈ (0, 1). Then, ∀n ≥ 0, an ≤ a0 exp(−βn) Combined with the two propositions, gives the desired result. Eσ2 (Xk) ≤ exp(Lk) 19 / 21 Simulation results Sphere 20 / 21 Simulation results Rotations 20 / 21 Summary We have proved that, when the data belong to complete CAT(κ) metric space, provided the initial values are close enough, the same algorithm makes sense and also converge linearly. We have checked that our results are consistent with simulations. 21 / 21