Yu-Guan Hsieh

Franck Iutzeler

Jérôme Malick

Panayotis Mertikopoulos

Optimization in Open Networks via Dual Averaging

In networks of autonomous agents (e.g., fleets of vehicles, scattered sensors), the problem of minimizing the sum of the agents' local functions has received a lot of interest. We tackle here this distributed optimization problem in the case of open networks when agents can join and leave the network at any time. Leveraging recent online optimization techniques, we propose and analyze the convergence of a decentralized asynchronous optimization method for open networks.

I. INTRODUCTION

Multi-agent systems are a powerful modeling framework for the analysis of signal processing or machine learning over sensor networks, fleets of autonomous vehicles, opinion dynamics, etc. This framework calls for decentralized optimization methods where the agents seek to minimize the sum of the individual functions by exchanging information through a communication graph, without the help of a central authority. Indeed, such methods are key to perform distributed computing, signal processing, or learning from scattered sources in communication-constrained or largescale environments; see e.g [START_REF] Tsitsiklis | Problems in decentralized decision making and computation[END_REF]- [START_REF] Lian | Asynchronous decentralized parallel stochastic gradient descent[END_REF] and references therein.

In this regard, decentralized optimization methods have been extensively studied in the literature. Depending on the agents' computing abilities and tasks at hand, several types of algorithms were considered. On the one hand, gradientbased methods such as decentralized gradient descent [START_REF] Nedic | Distributed subgradient methods for multiagent optimization[END_REF]- [START_REF] Jakovetić | Fast distributed gradient methods[END_REF], and decentralized dual averaging [START_REF] Duchi | Dual averaging for distributed optimization: Convergence analysis and network scaling[END_REF]- [START_REF] Colin | Gossip dual averaging for decentralized optimization of pairwise functions[END_REF] update the local variables using gradients of the agents' objective functions (see also [START_REF] Nedić | Network topology and communication-computation tradeoffs in decentralized optimization[END_REF] for a recent review). On the other hand, splitting methods such as the alternating direction method of multipliers (ADMM) [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF]- [START_REF] Wei | On the o (1= k) convergence of asynchronous distributed alternating direction method of multipliers[END_REF] imply that each agents has to minimize (a regularized version of) its local function, which can be too demanding depending on the application.

Despite the abundance of literature on this topic, most of them assume a network of fixed composition, that is, the agents that participate in the process always remain the same. On the contrary, this work focuses on the case of an open network where the agents can join and leave the system at any moment. This can happen in numerous situations, e.g.,

• When a cluster of servers is used to train a machine learning task, a node may leave the network due to a system failure or simply because the resource is acquired by another job. New nodes can also be deployed to accelerate the training process or process additional data.

Due to the dynamic nature of these open multi-agent systems, several works have studied the stability of consensus algorithm over the mean, maximum, or median of the agents values [START_REF] Franceschelli | Proportional dynamic consensus in open multi-agent systems[END_REF]- [START_REF] De Galland | Open multiagent systems with variable size: the case of gossiping[END_REF]. Among the very few works that tackle the problem of decentralized optimization over open networks, [START_REF] Hendrickx | Stability of decentralized gradient descent in open multi-agent systems[END_REF] showed that decentralized gradient descent is stable when agents/functions change over time if their objectives are sufficiently smooth.

Distributed algorithms also need to cope with asynchronous communications (i.e., the agents do not synchronize to communicate between optimization steps) with delays (i.e., there may be some gap between sending and receiving times). Such capacity is an important feature for scalability and flexibility. The study of this aspect was thus concomitant to the development of different decentralized optimization methods; see e.g., [START_REF] Tsianos | Consensus-based distributed optimization: Practical issues and applications in largescale machine learning[END_REF]- [START_REF] Zhou | Distributed asynchronous optimization with unbounded delays: How slow can you go?[END_REF].

In this paper, we focus on the particular case of asynchronous open networks where i) the agents can communicate with each other asynchronously following a timevarying communication graph; ii) the exchanges and local processing incur delays; and iii) the agents may join and leave the system for arbitrary periods of time. While the first two points are relatively well studied in the literature as mentioned above, the last point tremendously complicates the analysis since the system may completely change from one step to another, see e.g., [START_REF] De Galland | Fundamental performance limitations for average consensus in open multi-agent systems[END_REF] and references therein.

To address this challenge, we develop the idea that (offline) optimization problems over open networks can be efficiently handled by tools from online optimization. Using this viewpoint and building on recent results on dual averaging for online learning with delays [START_REF] Hsieh | Multiagent online optimization with delays: Asynchronicity, adaptivity, and optimism[END_REF], we introduce DAERON (Dual AvERaging for Open Network), a method for optimization over open networks that allows for asynchronous communications. On the theoretical side, we study the algorithm's performance with respect to the average (over both time and agents) of the agents' functions. We then provide numerical simulations on a decentralized regression problem to illustrate the potential of our method.

The rest of the paper is organized as follows. In Section II, we formulate the open multi-agent optimization problem mathematically and define the corresponding performance measures. The main algorithm is described in Section III and analyzed in Section IV. Section V is dedicated to numerical experiments. Finally, Section VI concludes the paper and provides several clues for future research.

II. AN OPEN NETWORK OF COMPUTING AGENTS A. Model

We consider a (possibly infinite) set of agents V; each of them associated with an individual convex cost function f i : R d → R. At each time t = 1, 2, . . . , only a (finite) subset of agents V t is active and may communicate using undirected communications links E t := {{i, j} ∈ V 2 t : i and j can exchange at t}. Let m t := card(V t ) denote the number of active agents at time t and we will also write M t := t s=1 m s . In open multi-agent systems, it is in general impossible to define a temporally invariant global objective to minimize over time. Since those who are present in the network are usually the entities that we really care about, an alternative is to focus exclusively on the active agents and define the instantaneous loss at time t as

f inst t (x) = 1 m t i∈Vt f i (x).
The problem of interest is then the minimization of f inst t . However, providing a proper analysis for this time-varying problem is still challenging because the set of active agents V t may change drastically between two consecutive time instants, which also leads to an abrupt change in the objective. In addition, agreeing on a consensus value in an open network is already a difficult problem [START_REF] Franceschelli | Stability of open multi-agent systems and applications to dynamic consensus[END_REF], [START_REF] De Galland | Open multiagent systems with variable size: the case of gossiping[END_REF].

B. Quantity of Interest

Instead of tackling the minimization of f inst t directly, we draw inspiration from online learning and analyze the running loss defined for a time-horizon T as

Loss(T ) = 1 M T T t=1 i∈Vt f i (x ref t ) -min u∈X T t=1 i∈Vt f i (u) (1)
where X ⊂ R d is the shared constrained set and x ref t is a reference point for time t. In the sequel, we will consider algorithms in which each agent i ∈ V t produces a local variable x i,t at time t. It is thus reasonable to set x ref t = x it,t for a reference agent i t ∈ V t that is chosen arbitrarily at each time, and Loss would then represent the average network suboptimality over time for these reference agents. Note that the suboptimality is compared with the best fixed a posteriori action which is the solution u ⋆ ∈ X of

min u∈X f run T (u) := 1 M T T t=1 i∈Vt f i (u) .
This quantity mimics the collective regret in [START_REF] Hsieh | Multiagent online optimization with delays: Asynchronicity, adaptivity, and optimism[END_REF] with an additional 1/M T which takes into account the total number of agents that have participated until time T . The notable difference here with the distributed online optimization literature [START_REF] Hosseini | Online distributed optimization via dual averaging[END_REF]- [START_REF] Yan | Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties[END_REF] is that we consider an open network of agents so that the composition of the system can change over time.

Algorithm 1 DAERON at node i for active period t join -t leave 1: Parameters: t join time when the agent joins the network;

t leave time when the agent leaves the network 2: Initialize: S i,t join ← S j,t join for j ∈ V t join -1 ∩ V t join 3: for t = t join , . . . , t leave do 4:

Generate the prediction x i,t using (2)

5: Compute the local subgradient g i,t ∈ ∂f i (x i,t ) 6:
Send subgradients to other active agents 7:

Receive subgradients identified by the index set G i,t

8:

Update S i,t+1 ← S i,t ∪ G i,t ∪{g i,t } 9: end for

III. DAERON: DUAL AVERAGING FOR OPEN NETWORK

A. Algorithm DAERON, as described in Algorithm 1, is a (sub)gradientbased method that applies dual averaging [START_REF] Nesterov | Primal-dual subgradient methods for convex problems[END_REF] at the level of the whole network. For this, we assume that given any point x i,t ∈ X , the agent i is able to compute a subgradient g i,t ∈ ∂f i (x i,t ). This information is transmitted to the whole network and used by all the agents for computing their own variable. Formally, let us define S i,t as the index set of the subgradients that the agent i ∈ V t has received/computed by time t. Then, the agent i generates the variable x i,t as

x i,t = Π X   x 1 -η i,t (j,s)∈Si,t g j,s   . (2)
where Π X : y → arg min x∈X ∥x -y∥ denotes the projection onto X , x 1 is a common starting point, and η i,t > 0 is a learning rate that can be both time and agent dependent. Note also that the communication of the subgradients (lines 6-7) can be done asynchronously in parallel with the other steps (lines 4-5) of the algorithm. Remark 1 (Arriving agents): In Algorithm 1, we initialize an agent arriving at time t with the subgradient set of an arbitrary agent in V t-1 ∩ V t , which implicitly assumes that V t-1 ∩ V t ̸ = ∅. This is not crucial, as what really counts is that the agent is initialized with sufficient knowledge about what the network has computed, but we will stick to this model in the remainder of the paper for simplicity.

B. Practical Implementation

Storing all the available subgradients at a node can be prohibitively expensive, or even infeasible since this would require infinite storage capacity when t goes to infinity. It is thus important to note that DAERON is just a conceptual algorithm that can be implemented in different ways to circumvent this issue. We provide below two possible workarounds to demonstrate the flexibility of our method: stored until the time that it has been sent to or received from these potential neighbors.

• If the number of involved agents m is small, we may define the sum of the subgradients computed by agent i as yi,t = t-1 s=1 g i,s with the convention g i,s = 0 when i / ∈ V s . Each node i ∈ V t then stores a table of size m×d containing the vectors y1,t-τ1,i(t) , . . . , ym,t-τm,i(t) corresponding to delayed versions of the computed subgradient sums over the network, with τ j,i (t) measuring this delay. These vectors are updated through communication. This strategy can also be adopted in a semi-centralized network with m central nodes and an arbitrary number of edge computing devices that retrieve information from these central nodes.

C. Quantities at play and assumptions

For our analysis, we make the following technical assumptions on the local cost functions and the constraint set.

Assumption 1: Each f i is convex and G-Lipschitz. The common constraint set X is closed and convex.

In order for the problem to make sense, we will assume that the communication delays are upper bounded.

Assumption 2: The delays of the algorithm are upper bounded by τ , i.e., for any t, s ∈ N such that t > s + τ and any i ∈ V t , j ∈ V s , we have (j, s) ∈ S i,t .

In particular, Assumption 2 supposes that every piece of information is spread to the whole network in a finite amount of time. While this is quite evident in a static network, in the case of an open network this requires that the evolution of the network is slow enough with respect to the communication between the agents.

For concreteness, let us consider a model where every node communicates all its available gradients to its neighbors at each iteration. Then for a static network with a fixed topology G = (V, E), we have clearly τ = diam(G) where diam(G) stands for the diameter of the graph. The case of an open network with changing topology is considerably more complicated. For instance, in the case of a line graph where at each time a new agent joins at the end of the graph, the diameter grows linearly with t and it becomes impossible to propagate information to the whole network. This is one kind of situation we want to avoid here. Formally, we define V j,s t = {i ∈ V t : (j, s) ∈ S i,t } as the set of active agents that possess g j,s at time t. The following example provides a sufficient stability assumption which allows information to spread across the network.

Example 1 (Bounded delays): Come back to the same situation as above where every node communicates all its available gradients to its neighbors during each iteration. Suppose further that the set of the active agents remain unchanged for periods of B iterations (i.e., for t = lB, . . . , (l + 1)B -1), and that the graph G l = (V t , l(B+1)-1 t=lB E s ) is k-vertexconnected (i.e., removing at least k nodes is necessary to disconnect it). If the number of arriving plus leaving agents at the end of iteration (l + 1)B -1 is q < k, then for any s ≤ lB -1 and j ∈ V s , the number of nodes that do not possess g j,s is reduced by at least k -q > 0 after the B iterations, i.e., card(V j,s (l+1)B ) ≤ max(0, card(V j,s lB ) -(k -q)). In that case, the maximal delay is thus bounded by max t m t B/(k -q) + B.

The above example means that provided that the number of exiting/incoming agents is not too large compared to the connectivity of the communication graph, the delays are naturally bounded.

Remark 2 (Loss of information due to agent departure): When an agent leaves the network, some of its computed subgradients may be lost for the network. This can happen either because it never communicated them or because the agents to which it communicated them also left the network. In Example 1, the change of composition at the end of iteration (l + 1)B -1 could notably cause the loss of the subgradients computed at time t = lB, . . . , (l + 1)B -1. This does not affect the proposed algorithm. The only difference is in the analysis: we will consider that the agent j is not in V s if V j,s t = ∅ starting from some t. 1

IV. ANALYSIS

A. Performance in the general case

We provide the convergence result for DAERON in terms of the running loss defined in (1). To do so, we define the quadratic mean and the average number of active agents over time:

m QM = 1 T T t=1 m 2 t and m = 1 T T t=1 m t .
Note that we always have m QM ≥ m.

Theorem 1: Let Assumptions 1 and 2 hold. Running DAERON with constant learning rate

η i,t ≡ η = r 0 m QM G (3τ + 1)T
for some r 0 > 0 guarantees that

Loss(T ) ≤ m QM m 2αrG √ 3τ + 1 √ T , (3)
where r = ∥u ⋆ -x 1 ∥ 2 and α = max(r/(2r 0 ), r 0 /r).

Proof: An important feature of DAERON is that the subgradients are not always applied to the points where they are evaluated. To accommodate this in our analysis, we consider the virtual iterates ( x t ) t∈N defined by

x t = Π X x 1 -η t-1 t=1 i∈Vt g i,t .
1 Note that in Example 1, we have either V j,s t = ∅ or V j,s t = Vt for t sufficiently large (assuming that s is fixed).

From the regret analysis of dual averaging (see, e.g., [START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF]Prop. 2]), the following holds for all u ∈ X ,

t=1 i∈Vt ⟨g i,t , x t -u⟩ ≤ ∥u -x 1 ∥ 2 2η + η 2 T t=1 i∈Vt g i,t 2 ≤ ∥u -x 1 ∥ 2 2η + η 2 T t=1 m 2 t G 2 .
In the second line we have used the Lipschitz continuity of the functions which implies that ∥g i,t ∥ ≤ G. Next, by using the convexity and the Lipschitz continuity of the functions, each term of (1) can be bounded for any u ∈ X by

f i (x ref t ) -f i (u) = f i (x it,t ) -f i (x i,t ) + f i (x i,t ) -f i (u) ≤ G∥x it,t -x i,t ∥ + ⟨g i,t , x i,t -u⟩.
We proceed to bound the second term in the above inequality

⟨g i,t , x i,t -u⟩ = ⟨g i,t , x i,t -x t ⟩ + ⟨g i,t , x t -u⟩ ≤ G∥x i,t -x t ∥ + ⟨g i,t , x t -u⟩.
Using the triangle inequality, we get ∥x it,t -x i,t ∥ ≤ ∥x it,tx t ∥ + ∥x i,t -x t ∥. Now, let Γ t = max i∈Vt ∥x i,t -x t ∥ and set u ← u ⋆ . We have from the above

Loss(T ) ≤ 1 M t ∥u ⋆ -x 1 ∥ 2 2η + T t=1 ( η 2 m 2 t G 2 + 3m t GΓ t ) .
To conclude, we may bound Γ t thanks to the bounded delay assumption. In fact, since the projection operator is non-expansive, it holds for all i ∈ V t that

∥x i,t -x t ∥ ≤ η t-1 t=1 j∈Vt g i,t -η (j,s)∈Si,t g j,s ≤ η t-1 s=t-τ j∈Vs g j,s ≤ η t-1 s=t-τ m s G. 2
Then, with m t m s ≤ (m 2 t + m 2 s )/2, we obtain the following

Loss(T ) ≤ 1 M t ∥u ⋆ -x 1 ∥ 2 2η + ηG 2 T t=1 (3τ + 1)m 2 t .
Inequality (3) follows immediately by the definition of m QM , m, and α.

Theorem 1 shows that when the ratio m QM /m is upper bounded, the running loss of the algorithm has a convergence rate in O(1/ √ T ). The factor m QM /m also indicates that the algorithm converges slower when the number of active agents varies greatly across iterations, which is expected because the algorithm would need more time to accommodate the change in this situation.

Remark 3 (Extensions): One drawback of the theorem is that the expression of the learning rate involves both the sqaure mean number of the agents m QM and the time horizon T . In a continuously evolving network, neither of these two quantities are known in advance. We provide below several alternatives which allow us to establish the same O(1/ √ T )

2 If s ≤ 0, then Vs = ∅ and mt = 0.

rate without these quantities. Proofs are variations of the above proof; we omit details due to space limitations.

• If the number m t is known to every agent. We may use

η i,t = η t = Θ(1/ τ ( t s=1 m 2 s )). • If m max =
max 1≤t≤T m t can be estimated and the agents have access to a global clock that indicates t, we can take η i,t = η t = Θ(1/(m max √ τ t)).

• Note that

t s=1 m 2 s ≤ √ m max √ M t .
Therefore, provided that m max is known, another alternative is to use η i,t = Θ(1/ √ τ m max M t ). This does not require to know m t explicitly since M t can be estimated by card(S i,t ). In particular, under Assumption 2, it holds M t ≤ card(S i,t ) + (τ + 1)m max .

B. The case of fixed agents V t = V

For comparison with existing literature (e.g., [START_REF] Duchi | Dual averaging for distributed optimization: Convergence analysis and network scaling[END_REF]), we now turn back to the case of a "closed network" where all the agents are active at each iteration. In this situation, we can define the (fixed) global loss as

f (x) = 1 m i∈V f i (x),
where m = card(V) is the number of agents. We have m QM = m = m and thus m QM /m = 1. As an immediate corollary of Theorem 1, if we apply DAERON with the constant stepsize η i,t ≡ η = r mG (3τ + 1)T , then for any agent i ∈ V,

f 1 T T t=1 x i,t -min u∈X f (u) ≤ 1 T T t=1 f (x i,t ) -min u∈X f (u) ≤ 2rG √ 3τ + 1 √ T .
This means that the running average of each agent's iterates decreases in global suboptimality at rate O(1/ √ T ), which matches the rate of [8, Th. 2] for the slightly different decentralized dual averaging algorithm. 3 Going one step further, the same result would still hold under asynchronous activation as long as the activation patterns can be described by a stationary probability distribution. On the other hand, Theorem 1 also allows us to prove the convergence of the algorithm in an open network whose composition stops changing after finite time.

V. NUMERICAL EXPERIMENTS

In this section, we demonstrate the effectiveness of DAERON with experiments on a static and an open network.

A. Problem Description

Let us consider a decentralized least absolute deviation (LAD) regression model. Given a data set evenly distributed on m nodes

(a ik , b ik ) i,k∈[m]×[n] with a ik in R d and b ik ∈ R, it consists in solving min x∈R d f (x) := 1 m m i=1 1 n n k=1 |a ⊤ ik x -b ik | . (4)
Compared to least square regression, LAD is known to be more resistant to the presence of outliers. Although the use of absolute value makes the problem non-differentiable, DAERON can be run with subgradients as suggested by our analysis. For the experiments, we generate synthetic data as follows:

1) The ground truth model x ⋆ ∈ [-5, 5] d is drawn from a uniform distribution.

2) The local model x ⋆ i of the node i is obtained by perturbing x ⋆ with a Gaussian noise, i.e., x ⋆ i = x ⋆ + ε i where ϵ i ∼ N (0, I d ).

3) We sample a ik ∼ N (0, I d ) and compute b ik = a ⊤ ik x ⋆ i + ε ik with ε ik ∼ N (0, 1). 4) On each node, a random portion of samples are corrupted. For these samples, we replace b ik by a random value generated from a Gaussian distribution.

In the above, we introduce the second and the fourth steps mainly for two reasons. First, it makes the problem more heterogeneous, and thus more difficult. Second, it makes the communication between agents more important for finding a good approximation of x ⋆ . In the following, we will take m = 64 nodes, n = 200 samples per node, and dimension d = 20. On each node, the number of corrupted samples is random in {0, . . . , 120}. We also verify that the solution x of (4) is not too far from x ⋆ .

B. Static network

We first investigate the performance of the algorithm on a static network. The nodes are arranged in a 2d grid of size 8 × 8. Adjacent nodes exchange gradients at each iteration. Communication-computation overlap is allowed for better efficiency-in Algorithm 1, this means that lines 4-5 and 6-7 are run in parallel. Then, with a constant stepsize η, the update writes

x i,t+1 = x i,t -η m i=1 g j,t-τj,i ,
where τ j,i is the distance between the nodes j and i. For illustration purposes, we also compare with a decentralized (sub)gradient descent (DGD) method [START_REF] Nedic | Distributed subgradient methods for multiagent optimization[END_REF] with constant stepsize γ and a mixing matrix W = (w i,j ). Its update is

x i,t+1 = m j=1 w i,j x j,t -γg i,t
Algorithm 2 DAERON at each node i as implemented in Section V-C

ζ i ← ζ i + z i mod 2 13: if z i = 1 and ζ i = 1 then 14: Pick randomly j ∈ V t ∩ V t+1 15:
Update S i,t+1 ← S j,t+1 end if 18: end for and we take W as the Metropolis matrix of the graph in our experiments:

w i,j =    1/(max(deg(i), deg(j)) + 1) if {i, j} ∈ E, 1 - m k=1 w i,k if i = j, 0 otherwise,
with deg(i) denoting the degree of the node i.

For a proper comparison of the two algorithms, it is important to notice that a subgradient is sent to all the m nodes in DAERON while it is averaged out in DGD. Therefore, we will take γ = mη and refer to it as the effective learning rate of both methods. With this in mind, in Fig. 1a we plot the convergence of the averaged optimality gap (1/m) m i=1 f (x i,t ) -min f for DAERON and DGD with different choices of γ.

Interestingly, we observe that when using the same effective learning rate, the two algorithms establish similar convergence behavior until reaching their respective fixed points. However, DAERON is able to converge to a point with higher accuracy. We believe that this is because the variables (x i,t ) i∈V tend to be closer to each other in DAERON. 4

C. Open network

Now that we have shown that DAERON performs comparably to standard decentralized optimization methods in a static network, we proceed to study its behavior in an open multi-agent system (Algorithm 2). Following [START_REF] Varma | Open multi-agent systems with discrete states and stochastic interactions[END_REF], we model the arrivals and departures of the agents by a Bernoulli process. Initially, only half of the 64 nodes are active. Then, every K = 20 iterations, each agent may change its activation status (i.e., from active to inactive or vice-versa) with probability p = 0.05. At each iteration, the active nodes are randomly paired with each other, then each pair synchronizes their gradients. 5 Formally, if nodes i and j are paired at time t, then S i,t+1 \ {g i,t } = S j,t+1 \ {g j,t } = S i,t ∪ S j,t . In the spirit of DGD, we also implement an algorithm which directly updates the primal variables as

x i,t+1 = x i,t + x j,t 2 -γg i,t , x j,t+1 = x i,t + x j,t 2 -γg j,t .
In both cases, an agent that becomes active at the end of round t -1 is assigned the state variable (i.e., S i,t or x i,t ) of a random node in V t-1 ∩ V t . We take γ = mη/2 in our experiment since on average m/2 nodes are active.

As for the performance measure, we consider the averaged instantaneous optimality gap linst (t) and the averaged running loss lrun (t) defined by linst (t) = 1 m t i∈Vt f inst t (x i,t ) -min f inst t (5)

lrun (t) = 1 M t t s=1 1 m s i∈Vs f inst s (x i,s ) -min f run t . (6)
The evolution of these two measures for γ = 0.005 are plotted in Fig. 1b. We see that both algorithms are able to converge to an area where potential solutions are located whereas DAERON can get much closer to the optimum of f inst t . Moreover, we observe that the instantaneous loss for DAERON increases abruptly when the set of active agents changes and gets decreased again afterwards. This indicates that the algorithm actually has the ability to track the instantaneous solution.

VI. CONCLUSION

In this paper, we introduced a decentralized optimization method for open multi-agent systems, in which agents can freely join or leave the network during the process. This 5 If there is an odd number of nodes, one node is ignored in this process.

setting is particularly challenging since there is not a clear objective to minimize and even exact convergence to a consensus is generally out of reach. These difficulties led us to adopting techniques and performance measures from online optimization. We proved that our algorithm benefits from a O(1/ √ T ) convergence rate with respect to the running average of the functions of the agents present in the network. In our simulations, we showed that our method outperformed decentralized subgradient descent on a least absolute deviation problem.

The positive results in our numerical experiments also raises several important questions: How can we analyze the tracking behavior of the algorithm from a theoretical perspective? Is it possible to combine DAERON with other consensus-based methods to achieve superior performance? How do we determine the best algorithm to use given a specific open network? Each of these question leads to new research direction that is worth exploring in future works.

Fig. 1 :

 1 Fig. 1: Comparison of DAERON and DGD. For a static network we plot in (a) the averaged suboptimality. For an open network we plot in (b) the averaged instantaneous suboptimality (5) and the averaged running loss (6).

1 :

 1 Initialize: S i,1 ← ∅, activation status ζ i ∈ {0, 1}, network parameters K ∈ N, p ∈ [0, 1] 2: for t = 1, 2, . . . doCompute x i,t by (2) and g i,t ∈ ∂f i (x i,t )

	3:	Agent update
	4:	if ζ i = 1 then
	5:	Get randomly paired with another active agent j
	6:
	7:	Update S i,t+1 ← S i,t ∪ S j,t ∪{g i,t }
	8:	end if
	9:	Network evolution
	10:	if (t + 1) ≡ 0 mod K then
	11:	Draw a Bernoulli random variable z i ∼ B(p)
	12:

• We can maintain y i,t = (j,s)∈Si,t g j,s while keeping track of the most recent subgradients in order to communicate them with other agents. Formally, suppose that each node has a number of potential neighbors they may be connected to; then a subgradient g j,s only needs to be

In[START_REF] Duchi | Dual averaging for distributed optimization: Convergence analysis and network scaling[END_REF], the subgradient are averaged by gossiping while in DAERON, they are directly exchanged.

Indeed, let ∆ and 1-λ be respectively the diameter of the graph and the spectral gap of the mixing matrix. Then, as shown in the proof of Theorem 1, for DAERON we can roughly bound ∥x i,t -x j,t ∥ by mητ G = ∆γG. As for DGD, it is known that we have asymptotically ∥x i,t -x j,t ∥ ≲ γG/(1 -λ)[START_REF] Nedić | Network topology and communication-computation tradeoffs in decentralized optimization[END_REF] Lem. 11]. Since it generally holds ∆ ≤ 1/(1 -λ) and this is notably the case for the graph that we consider, this provides a possible explanation for the superiority of DAERON over DGD.

ACKNOWLEDGMENTS

This work has been partially supported by MIAI Grenoble Alpes (ANR-19-P3IA-0003).

This work has been partially supported by MIAI@Grenoble Alpes (ANR-19-P3IA-0003)