Valentina Zantedeschi
email: vzantedeschi@gmail.com

Aurélien Bellet
email: aurelien.bellet@inria.fr

Marc Tommasi
email: marc.tommasi@inria.fr

Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs

We consider the fully decentralized machine learning scenario where many users with personal datasets collaborate to learn models through local peer-to-peer exchanges, without a central coordinator. We propose to train personalized models that leverage a collaboration graph describing the relationships between the users' personal tasks, which we learn jointly with the models. Our fully decentralized optimization procedure alternates between training nonlinear models given the graph in a greedy boosting manner, and updating the collaboration graph (with controlled sparsity) given the models. Throughout the process, users exchange messages only with a small number of peers (their direct neighbors in the graph and a few random users), ensuring that the procedure naturally scales to large numbers of users. We analyze the convergence rate, memory and communication complexity of our approach, and demonstrate its benefits compared to competing techniques on synthetic and real datasets.

Introduction

In the era of big data, the classical paradigm is to build huge data centers to collect and process users' data. This centralized access to resources and datasets is convenient to build predictive models with machine learning, but also comes with important drawbacks. The service provider needs to gather, store and analyze the data on a large central server, which induces high infrastructure costs. As the server represents a single point of entry, it must also be secure enough to prevent attacks that could put the entire user database in jeopardy. On the user end, disadvantages include limited control over one's personal data as well as possible privacy risks, which may come from the aforementioned attacks but also from potentially loose data governance policies on the part of service providers. A more subtle risk is to be trapped in a "single thought" model which fades individual users' specificities or leads to unfair predictions for some of the users.

For these reasons and thanks to the advent of powerful personal devices, we are currently witnessing a shift to a different paradigm where data is kept on the users' devices, whose computational resources are leveraged to train models in a collaborative manner. In this work, we focus on fully decentralized learning, which has recently attracted a lot of interest [START_REF] Duchi | Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling[END_REF][START_REF] Wei | Distributed Alternating Direction Method of Multipliers[END_REF][START_REF] Colin | Gossip dual averaging for decentralized optimization of pairwise functions[END_REF][START_REF] Lian | Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent[END_REF][START_REF] Jiang | Collaborative Deep Learning in Fixed Topology Networks[END_REF][START_REF] Tang | D 2 : Decentralized Training over Decentralized Data[END_REF]. In this setting, users exchange information through local peer-to-peer exchanges in a sparse communication graph without relying on a central server that aggregates updates or coordinates the protocol. Unlike federated learning where the central server plays a key role [START_REF] Mcmahan | Communication-efficient learning of deep networks from decentralized data[END_REF][START_REF] Konečnỳ | Federated learning: Strategies for improving communication efficiency[END_REF], fully decentralized learning thus naturally scales to large numbers of users without single point of failure or communication bottlenecks [START_REF] Lian | Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent[END_REF].

The present work stands out from existing approaches in fully decentralized learning, which train a single global model that may not be adapted to all users. Instead, our idea is to leverage the fact that in many large-scale applications (e.g., predictive modeling in smartphones apps), each user exhibits distinct behaviors/preferences but is sufficiently similar to some other peers to benefit from sharing information with them. We thus propose to jointly discover the relationships between the personal tasks of users in the form of a sparse collaboration graph and learn personalized models that leverage this graph to achieve better generalization performance. For scalability reasons, the collaboration graph serves as an overlay to restrict the communication to pairs of users whose tasks appear to be similar. In such a framework, it is crucial that the graph is well-aligned with the underlying similarity between the personal tasks to ensure that the collaboration is fruitful and avoid convergence to poorly-adapted models. We formulate the problem as the optimization of a joint objective over the models and the collaboration graph, in which collaboration is achieved by introducing a trade-off between (i) having the personal model of each user accurate on its local dataset, and (ii) making the models and the collaboration graph smooth with respect to each other.

More precisely, we design and analyze a fully decentralized algorithm to solve our collaborative problem in an alternating procedure, in which we iterate between updating personalized models given the current graph and updating the graph (with controlled sparsity) given the current models. We first propose an approach to learn personalized nonlinear classifiers as combinations of a set of base predictors inspired from l 1 -Adaboost [START_REF] Shen | On the dual formulation of boosting algorithms[END_REF]. In the proposed decentralized algorithm, users greedily update their personal models by incorporating a single base predictor at a time and send the update only to their direct neighbors in the graph. We prove a theoretical convergence rate for the procedure and show that it requires very low communication costs (linear in the number of edges in the graph and logarithmic in the number of base classifiers to combine). We then propose an approach to learn a sparse collaboration graph. From the decentralized system perspective, users update their neighborhood of similar peers by communicating only with small random subsets of peers obtained through a peer sampling service [START_REF] Jelasity | Gossip-based peer sampling[END_REF]. Our approach is flexible enough to accommodate various graph regularizers allowing to easily control the sparsity of the learned graph, which is key to the scalability of the model update step. For strongly convex regularizers, we prove a fast convergence for our algorithm and show how the number of random users requested from the peer sampling service rules a trade-off between communication and convergence speed.

To summarize, our main contributions are as follows. [START_REF] Almeida | DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models[END_REF] We formalize the problem of learning with whom to collaborate together with personalized models for collaborative decentralized learning. [START_REF] Anguita | A public domain dataset for human activity recognition using smartphones[END_REF] We propose and analyze a fully decentralized algorithm to learn nonlinear personalized models with low communication costs. (3) We derive a generic and scalable approach to learn sparse collaboration graphs in the decentralized setting. (4) We show that our alternating optimization scheme leads to better personalized models and lower communication costs than existing methods on several datasets.

Problem Setting and Notations

In this section, we formally describe the problem of interest. We consider a set of users (or agents)

[K] = {1, . . . , K}, each with a personal data distribution over some common feature space X and label space Y defining a personal supervised learning task. For example, the personal task of each user could be to predict whether he/she likes a given item based on features describing the item. Each user k holds a local dataset S k of m k labeled examples drawn from its personal data distribution over X × Y, and aims to learn a model parameterized by α k ∈ R n which generalizes well to new data points drawn from its distribution. We assume that all users learn models from the same hypothesis class, and since they have datasets of different sizes we introduce a notion of "confidence" c k ∈ R + for each user k which should be thought of as proportional to m k (in practice we simply set c k = m k / max l m l ). In a non-collaborative setting, each user k would typically select the model parameters that minimize some (potentially regularized) loss function L k (α k ; S k ) over its local dataset S k . This leads to poor generalization performance when local data is scarce. Instead, we propose to study a collaborative learning setting in which users discover relationships between their personal tasks which are leveraged to learn better personalized models. We aim to solve this problem in a fully decentralized way without relying on a central coordinator node.

Decentralized collaborative learning. Following the standard practice in the fully decentralized literature [START_REF] Boyd | Randomized gossip algorithms[END_REF], each user regularly becomes active at the ticks of an independent local clock which follows a Poisson distribution. Equivalently, we consider a global clock (with counter t) which ticks each time one of the local clock ticks, which is convenient for stating and analyzing the algorithms. We assume that each user can send messages to any other user (like on the Internet) in a peer-to-peer manner. However, in order to scale to a large number of users and to achieve fruitful collaboration, we consider a semantic overlay on the communication layer whose goal is to restrict the message exchanges to pairs of users whose tasks are most similar. We call this overlay a collaboration graph, which is modeled as an undirected weighted graph G w = ([K], w) in which nodes correspond to users and edge weights w k,l ≥ 0 should reflect the similarity between the learning tasks of users k and l, with w k,l = 0 indicating the absence of edge. A user k only sends messages to its direct neighbors N k = {l : w k,l > 0} in G w , and potentially to a small random set of peers obtained through a peer sampling service (see [START_REF] Jelasity | Gossip-based peer sampling[END_REF] for a decentralized version). Importantly, we do not enforce the graph to be connected: different connected components can be seen as modeling clusters of unrelated users. In our approach, the collaboration graph is not known beforehand and iteratively evolves (controlling its sparsity) in a learning scheme that alternates between learning the graph and learning the models. This scheme is designed to solve a global, joint optimization problem that we introduce below.

Objective function. We propose to learn the personal classifiers α = (α 1 , . . . , α K ) ∈ (R n ) K and the collaboration graph w ∈ R K(K-1)/2 to minimize the following joint optimization problem:

min α∈M w∈W J(α, w) = K k=1 d k (w)c k L k (α k ; S k ) + µ 1 2 k<l w k,l α k -α l 2 + µ 2 g(w), (1)
where

M = M 1 × • • • × M K and W = {w ∈ R K(K-1
)/2 : w ≥ 0} are the feasible domains for the models and the graph respectively, d(w) = (d 1 (w), . . . , d K (w)) ∈ R K is the degree vector with d k (w) = K l=1 w k,l , and µ 1 , µ 2 ≥ 0 are trade-off hyperparameters. The joint objective function J(α, w) in ( 1) is composed of three terms. The first one is a (weighted) sum of loss functions, each involving only the personal model and local dataset of a single user. The second term involves both the models and the graph: it enables collaboration by encouraging two users k and l to have a similar model for large edge weight w k,l . This principle, known as graph regularization, is well-established in the multi-task learning literature [START_REF] Evgeniou | Regularized multi-task learning[END_REF][START_REF] Maurer | The Rademacher Complexity of Linear Transformation Classes[END_REF][START_REF] Paramveer | Semisupervised multi-task learning of structured prediction models for web information extraction[END_REF]. Importantly, the factor d k (w)c k in front of the local loss L k of each user k implements a useful inductive bias: users with larger datasets (large confidence) will tend to connect to other nodes as long as their local loss remains small so that they can positively influence their neighbors, while users with small datasets (low confidence) will tend to disregard their local loss and rely more on information from other users. Finally, the last term g(w) introduces some regularization on the graph weights w used to avoid degenerate solutions (e.g., edgeless graphs) and control structural properties such as sparsity (see Section 4 for concrete examples). We stress the fact that the formulation (1) allows for very flexible notions of relationships between the users' tasks. For instance, as µ 1 → +∞ the problem becomes equivalent to learning a shared model for all users in the same connected component of the graph, by minimizing the sum of the losses of users independently in each component. On the other hand, setting µ 1 = 0 corresponds to having each user k learn its classifier α k based on its local dataset only (no collaboration). Intermediate values of µ 1 let each user learn its own personal model but with the models of other (strongly connected) users acting as a regularizer.

While Problem (1) is not jointly convex in α and w in general, it is typically bi-convex. Our approach thus solves it by alternating decentralized optimization on the models α and the graph weights w. 1 Outline. In Section 3, we propose a decentralized algorithm to learn nonlinear models given the graph in a greedy boosting manner with communication-efficient updates. In Section 4, we design a decentralized algorithm to learn a (sparse) collaboration graph given the models with flexible regularizers g(w). We discuss related work in Section 5, and present some experiments in Section 6.

Decentralized Collaborative Boosting of Personalized Models

In this section, given some fixed graph weights w ∈ W, we propose a decentralized algorithm for learning personalized nonlinear classifiers α = (α 1 , . . . , α K ) ∈ M in a boosting manner with only logarithmic communication complexity in the number of model parameters. For simplicity, we focus on binary classification with Y = {-1, 1}. We propose that each user k learns a personal classifier as a weighted combination of a set of n real-valued base predictors H = {h j : X → R} n j=1 , i.e. a mapping x → sign( n j=1 [α k ] j h j (x)) parameterized by α k ∈ R n . The base predictors can be for instance weak classifiers (e.g., decision stumps) as in standard boosting, or stronger predictors pre-trained on separate data (e.g., public, crowdsourced, or collected from users who opted in to share personal data). We denote by A k ∈ R m k ×n the matrix whose (i, j)-th entry gives the margin achieved by the j-th base classifier on the i-th training sample of user k, so that for i ∈

[m k ], [A k α k ] i = y i n j=1 [α k ] j h j (x i )
gives the margin achieved by the classifier α k on the i-th data point (x i , y i ) in S k . Only user k has access to A k .

Adapting the formulation of l 1 -Adaboost [START_REF] Shen | On the dual formulation of boosting algorithms[END_REF][START_REF] Wang | Functional Frank-Wolfe Boosting for General Loss Functions[END_REF] to our personalized setting, we instantiate the local loss L k (α k ; S k ) and the feasible domain M k for each user k as follows:

L k (α k ; S k ) = log( m k i=1 e -[A k α k ]i ), M k = {α k ∈ R n : α k 1 ≤ β}, (2)
where β ≥ 0 is a hyperparameter to favor sparse models by controlling their l 1 -norm. Since the graph weights are fixed in this section, with a slight abuse of notation we denote by f (α) := J(α, w) the objective function in (1) instantiated with the loss function [START_REF] Anguita | A public domain dataset for human activity recognition using smartphones[END_REF]. Note that f is convex and continuously differentiable, and the domain

M = M 1 × • • • × M K is a compact and convex subset of (R n ) K .

Decentralized Algorithm

We propose a decentralized algorithm based on Frank-Wolfe (FW) [START_REF] Frank | An algorithm for quadratic programming[END_REF][START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF] (also known as conditional gradient descent), which has recently been proposed to solve l 1 -Adaboost in the centralized and non-personalized setting [START_REF] Wang | Functional Frank-Wolfe Boosting for General Loss Functions[END_REF]. For clarity of presentation, we set aside the decentralized setting for a moment and derive the Frank-Wolfe update with respect to the model of a single user.

Classical FW update. Let t ≥ 1 and denote by ∇[f (α (t-1) )] k the partial derivative of f with respect to the k-th block of coordinates corresponding to the model α (t-1) k of user k. For step size γ ∈ [0, 1], a FW update for user k takes the form of a convex combination α

(t) k = (1 -γ)α (t-1) k + γs (t) k with s (t) k = arg min s 1≤β s ∇[f (α (t-1) )] k = β sign(-(∇[f (α (t-1) )] k ) j (t) k )e j (t) k , (3) where j (t)
k = arg max j [|∇[f (α (t-1) )] k |] j and e j (t)
k is the unit vector with 1 in the j

(t)
k -th entry [START_REF] Kenneth | Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm[END_REF][START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF]. In other words, FW updates a single coordinate of the current model α (t-1) k which corresponds to the maximum absolute value entry of the partial gradient ∇[f (α (t-1) )] k . In our case, we have:

∇[f (α (t-1) )] k = -d k (w)c k η k A k + µ 1 (d k (w)α (t-1) k -l w k,l α (t-1) l ), with η k = exp(-A k α (t-1) k ) m k i=1 exp(-A k α (t-1) k )i
. The first term in ∇[f (α (t-1) )] k plays the same role as in standard Adaboost: the j-th entry (corresponding to the base predictor h j ) is larger when h j achieves a large margin on the training sample S k reweighted by η k (i.e., points that are currently poorly classified get more importance). On the other hand, the more h j is used by the neighbors of k, the larger the j-th entry of the second term. The FW update (3) thus preserves the flavor of boosting (incorporating a single base classifier at a time which performs well on the reweighted sample) with an additional bias towards selecting base predictors that are popular amongst neighbors in the collaboration graph. The relative importance of the two terms depends on the user confidence c k .

Decentralized FW. We are now ready to state our decentralized FW algorithm to optimize f . Each user corresponds keeps its personal dataset locally. The fixed collaboration graph G w plays the role of an overlay: user k only needs to communicate with its direct neighborhood N k in G w . The size of N k , |N k |, is typically small so that updates can occur in parallel in different parts of the network, ensuring that the procedure scales well with the number of users.

Our algorithm proceeds as follows. Let us denote by α (t) ∈ M the current models at time step t. Each personal classifier is initialized to some feasible point α (0) k ∈ M k (such as the zero vector). Then, at each step t ≥ 1, a random user k wakes up and performs the following actions:

1. Update step: user k performs a FW update on its local model based on the most recent information α (t-1) l received from its neighbors l ∈ N k :

α (t) k = (1 -γ (t) )α (t-1) k + γ (t) s (t) k , with s (t)
k as in (3) and γ (t) = 2K/(t + 2K).

Communication step: user k sends its updated model α (t)

k to its neighborhood N k . Importantly, the above update only requires the knowledge of the models of neighboring users, which were received at earlier iterations.

Convergence Analysis, Communication and Memory Costs

The convergence analysis of our algorithm essentially follows the proof technique proposed in [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF] and refined in [START_REF] Lacoste-Julien | Block-Coordinate Frank-Wolfe Optimization for Structural SVMs[END_REF] for the case of block coordinate Frank-Wolfe. It is based on defining a surrogate for the optimality gap f (α) -f (α * ), where α * ∈ arg min α∈M f (α). Under an appropriate notion of smoothness for f over the feasible domain, the convergence is established by showing that the gap decreases in expectation with the number of iterations, because at a given iteration t the block-wise surrogate gap at the current solution is minimized by the greedy update s (t) k . We obtain that our algorithm achieves an O(1/t) convergence rate (see supplementary for the proof). Theorem 1. Our decentralized Frank-Wolfe algorithm takes at most 6K(C ⊗ f + p 0 )/ε iterations to find an approximate solution α that satisfies, in expectation,

f (α) -f (α * ) ≤ ε, where C ⊗ f ≤ 4β 2 K k=1 d k (w)(c k A k 2 + µ) and p 0 = f (α (0) ) -f (α * ) is the initial sub-optimality gap.
Remarkably, we further prove in the supplementary material that the communication and memory cost needed by our algorithm to converge to an -approximate solution is linear in the number of edges of the graph and logarithmic in the number of base predictors. For the classic case where base predictors consist of a constant number of decisions stumps per feature, this translates into a logarithmic cost in the dimensionality of the data (see the experiments of Section 6).

Decentralized Learning of the Collaboration Graph

In the previous section, we have proposed and analyzed an algorithm to learn the model parameters α given a fixed collaboration graph w. To make our fully decentralized alternating optimization scheme complete, we now turn to the converse problem of optimizing the graph weights w given fixed models α. We will work with flexible graph regularizers g(w) that are weight and degree-separable:

g(w) = k<l g k,l (w k,l ) + K k=1 g k (d k (w))
, where g k,l : R → R and g k : R → R are convex and smooth. This generic form allows to regularize weights and degrees in a flexible way (which encompasses some recent work from the graph signal processing community [START_REF] Dong | Learning Laplacian matrix in smooth graph signal representations[END_REF][START_REF] Kalofolias | How to learn a graph from smooth signals[END_REF][START_REF] Berger | Graph Learning Based on Total Variation Minimization[END_REF]), while the separable structure is key to the design of an efficient decentralized algorithm that relies only on local communication. We denote the graph learning objective function by h(w) := J(α, w) for fixed models α. Note that h(w) is convex in w.

Decentralized algorithm. Our goal is to design a fully decentralized algorithm to update the collaboration graph G w . We thus need users to communicate beyond their current direct neighbors in G w to discover new relevant neighbors. In order to preserve scalability to large numbers of users, a user can only communicate with small random batches of other users. In a decentralized system, this can be implemented by a classic primitive known as a peer sampling service [START_REF] Jelasity | Gossip-based peer sampling[END_REF].

At each step, a random user k wakes up and samples uniformly and without replacement a set K of κ ≥ 1 users from the set {1, . . . , K} \ {k} using the peer sampling service (κ is a parameter of the algorithm). We denote by w k,K the κ-dimensional subvector of a vector w ∈ R K(K-1)/2 corresponding to the entries

{(k, l)} l∈K . Let ∆ k,K = ( α k -α l 2 ) l∈K , p k,K = (c k L k (α k ; S k ) + c l L l (α l ; S l )) l∈K and v k,K (w) = (g k (d k (w)) + g l (d l (w)) + g k,l (w k,l )) l∈K .
The partial derivative of the objective function h(w) with respect to the variables w k,K can be written as follows:

[∇h(w)] k,K = p k,K + (µ 1 /2)∆ k,K + µ 2 v k,K (w). (4)
We denote by L k,K is the Lipschitz constant of ∇h with respect to block w k,K . We now state our algorithm. We start from some arbitrary weight vector w (0) ∈ W, each user having a local copy of its K -1 weights. At each time step t, a random user k wakes up and performs the following actions:

1. Draw a set K of κ users and request their current models and degree.

2. Update the associated weights: w

(t+1) k,K ← max 0, w (t) k,K -(1/L k,K )[∇h(w (t) )] k,K . 3. Send each updated weight w (t+1) k,l
to the associated user in l ∈ K.

The algorithm is fully decentralized: no global information is needed to update the weights (local information from users in K is sufficient). Updates can thus happen asynchronously and in parallel.

Convergence, communication and memory. Our analysis proceeds as follows. We first show that our algorithm can be seen as an instance of proximal coordinate descent (PCD) [START_REF] Tseng | Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization[END_REF][START_REF] Richtárik | Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[END_REF] on a slightly modified objective function. Unlike the standard PCD setting which focuses on disjoint blocks, our coordinate blocks exhibit a specific overlapping structure that arises as soon as κ > 1 (as each weight is shared by two users). We build upon the PCD analysis due to [START_REF] Stephen | Coordinate descent algorithms[END_REF], which we adapt to account for our overlapping block structure. The details of our analysis can be found in the supplementary material. For the case where g is strongly convex, we obtain the following convergence rate. 2Theorem 2. Assume that g(w) is σ-strongly convex. Let T > 0 and h * be the optimal objective value. Our algorithm cuts the expected suboptimality gap by a constant factor ρ at each iteration: we have

E[h(w (T ) ) -h * ] ≤ ρ T (h(w (0) ) -h * ) with ρ = 1 - 2κσ K(K-1)Lmax with L max = max (k,K) L k,K .
The rate of Theorem 2 is typically faster than the sublinear rate of the boosting subproblem (Theorem 1), suggesting that a small number of updates per user is sufficient to reach reasonable optimization error before re-updating the models given the new graph. In the supplementary, we further analyze the trade-off between communication and memory costs and the convergence rate ruled by κ.

Proposed regularizer. In our experiments, we use a graph regularizer defined as g(w) = λ w 2 -1 log(d(w) + δ), which is inspired from [START_REF] Kalofolias | How to learn a graph from smooth signals[END_REF]. The log term ensures that all nodes have nonzero degrees (the small positive constant δ is a simple trick to make the logarithm smooth on the feasible domain, see e.g., [START_REF] Koriche | Compiling Combinatorial Prediction Games[END_REF]) without ruling out non-connected graphs with several connected components. Crucially, λ > 0 provides a direct way to tune the sparsity of the graph: the smaller λ, the more concentrated the weights of a given user on the peers with the closest models. This allows us to control the trade-off between accuracy and communication in the model update step of Section 3, whose communication cost is linear in the number of edges. The resulting objective is strongly convex and block-Lipschitz continuous (see supplementary for the derivation of the parameters and analyze of the trade-offs). Finally, as discussed in [START_REF] Kalofolias | How to learn a graph from smooth signals[END_REF], tuning the importance of the log-degree term with respect to the other graph terms has simply a scaling effect, thus we can simply set µ 2 = µ 1 in (1). Remark 1 (Reducing the number of variables). To reduce the number of variables to optimize, each user can keep to 0 the weights corresponding to users whose current model is most different to theirs. This heuristic has a negligible impact on the solution quality in sparse regimes (small λ).

Related Work

Federated multi-task learning. Our work can be seen as multi-task learning (MTL): as mentioned before, the graph regularization term is popular in the MTL literature [START_REF] Evgeniou | Regularized multi-task learning[END_REF][START_REF] Maurer | The Rademacher Complexity of Linear Transformation Classes[END_REF][START_REF] Paramveer | Semisupervised multi-task learning of structured prediction models for web information extraction[END_REF]. There has been recent work on distributed and federated multi-task learning [START_REF] Wang | Distributed Multitask Learning[END_REF][START_REF] Wang | Distributed Multi-Task Learning with Shared Representation[END_REF][START_REF] Baytas | Asynchronous Multi-task Learning[END_REF][START_REF] Smith | Federated Multi-Task Learning[END_REF], in which each node holds data for one task. These approaches rely on a central server to aggregate updates. The federated learning approach of [START_REF] Smith | Federated Multi-Task Learning[END_REF] is closest to our work for it jointly learns personalized (linear) models and pairwise similarities across tasks. However, the similarities are updated in a centralized way by the server which must regularly access all up-to-date models, creating a significant communication and computation bottleneck when the number of users is large. Furthermore, the task similarities do not form a valid weighted graph and are typically not sparse. This makes their formulation of the problem poorly suited to the fully decentralized setting, where sparsity is key to ensure scalability. Decentralized learning. There has been a recent surge of interest in fully decentralized machine learning. In most existing work, the goal is to learn the same global model for all users by minimizing the average of the local losses (see [START_REF] Duchi | Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling[END_REF][START_REF] Wei | Distributed Alternating Direction Method of Multipliers[END_REF][START_REF] Colin | Gossip dual averaging for decentralized optimization of pairwise functions[END_REF][START_REF] Lafond | Communication efficient distributed algorithms for high-dimensional sparse optimization[END_REF][START_REF] Lian | Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent[END_REF][START_REF] Jiang | Collaborative Deep Learning in Fixed Topology Networks[END_REF][START_REF] Tang | D 2 : Decentralized Training over Decentralized Data[END_REF] and references therein). In this case, there is no personalization: the graph merely encodes some communication constraints without any semantic meaning and only affects the convergence speed. Our work is more closely inspired by recent decentralized approaches that have shown the benefits of collaboratively learning personalized models for each user by leveraging a similarity graph given as input to the algorithm [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF][START_REF] Li | Distributed Multi-task Learning for Sensor Network[END_REF][START_REF] Bellet | Personalized and Private Peer-to-Peer Machine Learning[END_REF][START_REF] Almeida | DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models[END_REF]. As in our approach, this is achieved through a graph regularization term in the objective. A severe limitation to the applicability of these methods is that a relevant graph must be known beforehand, which is an unrealistic assumption in many practical scenarios. Crucially, our approach lifts this limitation by allowing to learn the graph along with the models. As a matter of fact, our decentralized graph learning procedure of Section 4 can be readily combined with the algorithms of [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF][START_REF] Li | Distributed Multi-task Learning for Sensor Network[END_REF][START_REF] Bellet | Personalized and Private Peer-to-Peer Machine Learning[END_REF][START_REF] Almeida | DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models[END_REF] in an alternating optimization procedure, as we demonstrate in our experiments. It is also worth mentioning that [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF][START_REF] Li | Distributed Multi-task Learning for Sensor Network[END_REF][START_REF] Bellet | Personalized and Private Peer-to-Peer Machine Learning[END_REF][START_REF] Almeida | DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models[END_REF] are restricted to linear models and have per-iteration communication complexity linear in the data dimension. Our boosting-based approach of Section 3, which learns nonlinear models with logarithmic communication cost, provides an interesting alternative for problems of high dimension and/or with complex decision boundaries, as illustrated in our experiments.

Experiments

In this section, we study the practical behavior of our approach. Denoting our decentralized Adaboost method introduced in Section 3 as Dada, we study two variants: Dada-Oracle (which uses a fixed oracle graph given as input) and Dada-Learned (where the graph is learned along with the models).

We compare against various competitors, which learn either global or personalized models in a centralized or decentralized manner. Global-boost and Global-lin learn a single global l 1 -Adaboost model (resp. linear model) over the centralized dataset S = ∪ k S k . Local-boost and Local-lin learn (Adaboost or linear) personalized models independently for each user without collaboration. Finally, Perso-lin is a decentralized method for collaboratively learning personalized linear models [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF]. This approach requires an oracle graph as input (Perso-lin-Oracle) but it can also directly benefit from our graph learning approach of Section 4 (we denote this new variant by Perso-lin-Learned). We use the same set of base predictors for all boosting-based methods, namely n simple decision stumps uniformly split between all D dimensions and value ranges. For all methods we tune the hyper-parameters with 3-fold cross validation. Models are initialized to zero vectors and the initial graphs of Dada-Learned and Perso-lin-Learned are learned using the purely local classifiers, and then updated after every 100 iterations of optimizing the classifiers, with κ = 5. All reported accuracies are averaged over users. Additional details, results and code can be found in the supplementary. The source code is available at https://github.com/vzantedeschi/Dada.

Synthetic data. To study the behavior of our approach in a controlled setting, our first set of experiments is carried out on a synthetic problem (MOONS) constructed from the classic two interleaving Moons dataset which has nonlinear class boundaries. We consider K = 100 users, clustered in 4 groups of 10, 20, 30 and 40 users. Users in the same cluster are associated with a similar rotation of the feature space and hence have similar tasks. We construct an oracle collaboration graph based on the difference in rotation angles between users, which is given as input to Dada-Oracle and Perso-lin-Oracle. Each user k obtains a training sample random size m k ∼ U [START_REF] Baytas | Asynchronous Multi-task Learning[END_REF][START_REF] Frank | An algorithm for quadratic programming[END_REF]. The data dimension is D = 20 and the number of base predictors is n = 200. We refer to the supplementary material for more details on the dataset generation. Figure 1 (left) shows the accuracy of all methods.

As expected, all linear models (including Perso-lin) perform poorly since the tasks have highly nonlinear decision boundaries. The results show the clear gain in accuracy provided by our method: both Dada-Oracle and Dada-Learned are successful in reducing the overfitting of Local-boost, and also achieve higher test accuracy than Global-boost. Dada-Oracle outperforms Dada-Learned as it makes use of the oracle graph computed from the true data distribution of users. Despite the noise introduced by the finite sample setting, Dada-Learned effectively makes up for not having access to any background knowledge on the relations between the users' tasks. Figure 1 (right) shows that the graph learned by Dada-Learned remains sparse across time (in fact, always sparser than the oracle graph), which ensures a small communication cost for the model update steps. Figure 2 (left) confirms that the graph learned by Dada-Learned is able to approximately recover the ground-truth cluster structure. Figure 2 (right) provides a more detailed visualization of the learned graph. We can clearly Nodes are labeled with their rotation angle, and a darker edge color indicates a higher weight. see the effect of the inductive bias brought by the confidence-weighted loss term in Problem (1) discussed in Section 2. In particular, nodes with high confidence and high loss values tend to have small degrees while nodes with low confidence or low loss values are more densely connected.

Real data. We present results on real datasets that are naturally collected at the user level: Human Activity Recognition With Smartphones (HARWS, K = 30, D = 561) [START_REF] Anguita | A public domain dataset for human activity recognition using smartphones[END_REF], VEHICLE SENSOR [START_REF] Marco | Vehicle classification in distributed sensor networks[END_REF] (K = 23, D = 100), COMPUTER BUYERS (K = 190, D = 14) and SCHOOL [START_REF] Goldstein | Multilevel modelling of survey data[END_REF] (K = 140, D = 17). As shown in Table 1, Dada-Learned and Perso-lin-Learned, which both make use of our alternating procedure, achieve the best performance. This demonstrates the wide applicability of our graph learning approach, for it enables the use of Perso-lin [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF] on datasets where no prior information is available to build a predefined collaboration graph. Thanks to its logarithmic communication, our approach Dada-Learned achieves higher accuracy under limited communication budgets, especially on higher-dimensional datasets (Table 2). More details and results are given in the supplementary.

Future Work

We plan to extend our approach to (functional) gradient boosting [START_REF] Friedman | Greedy function approximation: A gradient boosting machine[END_REF][START_REF] Wang | Functional Frank-Wolfe Boosting for General Loss Functions[END_REF] where the graph regularization term would need to be applied to an infinite set of base predictors. Another promising direction is to make our approach differentially-private [START_REF] Dwork | Differential Privacy[END_REF] to formally guarantee that personal datasets cannot be inferred from the information sent by users. As our algorithm communicates very scarcely, we think that the privacy/accuracy trade-off may be better than the one known for linear models [START_REF] Bellet | Personalized and Private Peer-to-Peer Machine Learning[END_REF].

SUPPLEMENTARY MATERIAL

This supplementary material is organized as follows. Section A provides the convergence analysis for our decentralized Frank-Wolfe boosting algorithm. Section B describes the convergence analysis of our decentralized graph learning algorithm. In Section C, we derive the strong convexity and smoothness parameters of g(w) = λ w 2 -1 log(d(w) + δ) needed to apply Theorem 2. Section D discusses the communication and memory costs of our method, with an emphasis on the scalability. Finally, Section E gives more details on our experimental setting and present additional results.

A Proof of Theorem 1

We first recall our optimization problem over the classifiers α

= [α 1 , . . . , α K ] ∈ (R n ) K : min α1 1 ,..., α K 1≤β f (α) = K k=1 d k (w)c k log 1 m k m k i=1 exp -(A k α k ) i + µ 1 2 K k=1 k-1 l=1 w k,l α k -α l 2 . ( 5
)
We recall some notations. For any k ∈ [START_REF] Berger | Graph Learning Based on Total Variation Minimization[END_REF]. We also denote by v [k] ∈ M the zero-padding of any vector v k ∈ M k . Finally, for conciseness of notations, for a given γ ∈ [0, 1] we write

[K], we let M k = {α k ∈ R n : α k 1 ≤ β} and denote by M = M 1 × • • • × M K our feasible domain in
α = α + γ(s [k] -α [k]
) and αk = (1 -γ)α k + γs k .

A.1 Curvature Bound

We first show that our objective function satisfies a form of smoothness over the feasible domain, which is expressed by a notion of curvature. Precisely, the global product curvature constant C ⊗ f of f over M is the sum over each block of the maximum relative deviation of f from its linear approximations over the block [START_REF] Lacoste-Julien | Block-Coordinate Frank-Wolfe Optimization for Structural SVMs[END_REF]:

C ⊗ f = K k=1 C k f = K k=1 sup α∈M,s k ∈M k γ∈[0,1] 2 γ 2 f (α) -f (α) -(α k -α k ) ∇ k f (α) . ( 6
)
We will use the fact that each partial curvature constant C k f is upper bounded by the (block) Lipschitz constant of the partial gradient ∇ k f (α) times the squared diameter of the blockwise feasible domain M k [START_REF] Lacoste-Julien | Block-Coordinate Frank-Wolfe Optimization for Structural SVMs[END_REF]. The next lemma gives a bound on the product space curvature C ⊗ f . Lemma 1. For Problem (5), we have

C ⊗ f ≤ 4β 2 K k=1 d k (w)(c k A k 2 1 + µ 1 ).
Proof. For the following proof, we rely on two key concepts: the Lipschitz continuity and the diameter of a compact space. A function f :

X → R is L-lipschitz w.r.t. the norm . 1 if ∀(x, x ) ∈ X 2 : |f (x) -f (x )| ≤ L x -x 1 . ( 7
)
The diameter of a compact normed vector space (M, . ) is defined as:

diam . (M) = sup x,x ∈M x -x .
We can easily bound the diameter of the subspace M k = {α k ∈ R n : α k 1 ≤ β} as follows:

diam . 1 (M k ) = max α k ,α k ∈M k α k -α k 1 = 2β. ( 8
)
We recall the expression for the partial gradient:

∇ k f (α) = -d k (w)c k η k (α) A k + µ 1 d k (w)α [k] - l w k,l α [l] , (9)
where we denote

η k (α) = exp(-A k α [k] ) m k i=1 exp(-A k α [k] )i .
We bound the Lipschitz constant of η k (α) by bounding its first derivative:

∇ k (η k (α)) 1 = (-η k (α) + η k (α) 2 ) A k 1 ≤ A k 1 . (10)
Eq. ( 10) is due to the fact that η k (α) 1 ≤ 1 and η k (α) ≥ 0. It is then easy to see that considering any two vectors α, α ∈ M differing only in their k-th block (α

[l] = α [l] ∀l = k), the Lipschitz constant L k of the partial gradient ∇ k f in (9) is bounded by d k (w)(c k A k 2 1 + µ 1 )
. Finally, we obtain Lemma 1 by combining the above results ( 8) and ( 10):

C ⊗ f = K k=1 C k f ≤ K k=1 L k diam 2 . 1 (M k ) ≤ 4β 2 K k=1 d k (w)(c k A k 2 1 + µ 1 ). (11)

A.2 Convergence Analysis

We can now prove the convergence rate of our algorithm by following the proof technique proposed by Jaggi in [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF] and refined by [START_REF] Lacoste-Julien | Block-Coordinate Frank-Wolfe Optimization for Structural SVMs[END_REF] for the case of block coordinate Frank-Wolfe.

We start by introducing some useful notation related to our problem (5):

gap(α) = max s∈M {(α -s) ∇(f (α))} = K k=1 gap k (α k ) = K k=1 max s k ∈M k {(α k -s k ) ∇ k f (α)} (12)
The quantity gap(α) can serve as a certificate for the quality of a current approximation of the optimum of the objective function [START_REF] Jaggi | Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization[END_REF]. In particular, one can show that

f (α) -f (α * ) ≤ gap(α)
where α * is a solution of ( 5). Under a bounded global product curvature constant C ⊗ f , we will obtain the convergence of Frank-Wolfe by showing that the surrogate gap decreases in expectation over the iterations, because at a given iteration t the block-wise surrogate gap at the current solution gap k (α

(t)
k ) is minimized by the greedy update s

(t) k ∈ M k .
Using the definition of the curvature (6) and rewriting αk -

α k = -γ k (α k -s k ), we obtain f (α) ≤ f (α) -γ(α k -s k ) ∇ k f (α) + γ 2 C k f 2 .
In particular, at any iteration t, the previous inequality holds for γ = γ

(t) = 2K t+2K , α (t+1) = α (t) +γ (t) (s (t+1) k -α (t+1) k ) with s (t+1) k = arg min s∈M k {s ∇ k f (α (t) )} as defined in (3). Therefore, (α k -s k ) ∇ k f (α) is by definition gap k (α k ) and f (α (t+1) ) ≤ f (α (t) ) -γ (t) gap k (α (t) k ) + (γ (t) ) 2 C k f 2 .
By taking the expectation over the random choice of k ∼ U(1, K) on both sides, we obtain

E k [f (α (t+1) )] ≤ E k [f (α (t) )] -γ (t) E k [gap k (α (t) k )] + (γ (t) ) 2 E k [C k f ] 2 ≤ E k [f (α (t) )] - γ (t) gap(α (t) ) K + (γ (t) ) 2 C ⊗ f 2K . (13)
Let us define the sub-optimality gap p(α) = f (α)-f * with f * the optimal value of f . By subtracting f * from both sides in (13), we obtain

E k [p(α (t+1) )] ≤ E k [p(α (t) )] - γ (t) K E k [p(α (t) )] + (γ (t) ) 2 C ⊗ f 2K (14)
≤ 1 - γ (t) K E k [p(α (t) )] + (γ (t) ) 2 C ⊗ f 2K . (15)
Inequality ( 14) comes from the definition of the surrogate gap [START_REF] Duchi | Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling[END_REF] which ensures that E k [p(α)] ≤ gap(α).

Therefore, we can show by induction that the expected sub-optimality gap satisfies

E k [p(α (t+1) )] ≤ 2K(C ⊗ f +p0) t+2K
, with p 0 = p(α (0) ) the initial gap. This shows that the expected sub-optimality gap E k [p(α)] decreases with the number of iterations with a rate O( 1 t ), which implies the convergence of our algorithm to the optimal solution. The final convergence rate can then be obtained by the same proof as [START_REF] Lacoste-Julien | Block-Coordinate Frank-Wolfe Optimization for Structural SVMs[END_REF] (Appendix C.3 therein) combined with Lemma 1.

B Proof of Theorem 2

We first show that our algorithm can be explicitly formulated as an instance of proximal block coordinate descent (Section B.1). Building upon this formulation, we prove the convergence rate in Section B.2.

B.1 Interpretation as Proximal Coordinate Descent

First, we reformulate our graph learning subproblem as an equivalent unconstrained optimization problem by incorporating the nonnegativity constraints into the objective:

min w∈R K(K-1)/2 F (w) = h(w) + r(w), (16)
where

h(w) = K k=1 d k (w)c k L k (α k ; S k ) + µ 1 2 k<l w k,l α k -α l 2 + µ 2 g(w) (17) r(w)
= k<l I ≥0 (w k,l ). (18)
In the expression above, I ≥0 denotes the characteristic function of the nonnegative orthant of R: I ≥0 (x) = 0 if x ≥ 0 and +∞ otherwise. Recall that g is the sum of smooth, weight-separable and degree-separable functions

g(w) = k<l g k,l (w k,l ) + K k=1 g k (d k (w)) .
We assume that h(w) is strongly convex and smooth, while it is clear that r(w) is not smooth but convex and separable across the coordinates of w. We will denote by w * the solution to [START_REF] Friedman | Greedy function approximation: A gradient boosting machine[END_REF], which is also the solution to our original (constrained) graph learning subproblem.

We will now show that the algorithm presented in the main text can be explicitly reformulated as an instance of proximal block coordinate descent [START_REF] Richtárik | Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[END_REF] applied to the function F (w). In the process, we will introduce some notations that we will reuse in the convergence analysis provided in Section B.2. At each iteration t, a random block of coordinates indexed by (k, K) is selected. Consider the following update:

     z (t) k,K ← arg min z∈R κ (z -w (t) k,K ) [∇h(w (t) )] k,K + L k,K 2 z -w (t) k,K 2 + l∈K I ≥0 (z k,l ) w (t+1) ← w (t) + U k,K (z (t) k,K -w (t) k,K ) (19)
For notational convenience, U k,K denotes the column submatrix of the

K(K -1)/2 × K(K -1)/2 identity matrix such that w U k,K = w k,K ∈ R κ for any w ∈ R K(K-1)/2 .
Notice that the minimization problem in ( 19) is separable and can be solved independently for each coordinate. Denoting by

z(t) = arg min z∈R K(K-1)/2 (z -w (t) ) ∇h(w (t) ) + L k,K 2 z -w (t) 2 + r(z) , (20)
we can thus rewrite [START_REF] Jelasity | Gossip-based peer sampling[END_REF] as:

w (t+1) j,l = z(t) j,l if j = k and l ∈ K w (t) j,l otherwise (21)
Finally, recalling the definition of the proximal operator of a function f :

prox f (w) = arg min z f (z) + 1 2 w -z 2 ,
we can rewrite [START_REF] Jiang | Collaborative Deep Learning in Fixed Topology Networks[END_REF] as:

z(t) = prox 1 L k,K r (w (t) -(1/L k,K )∇h(w (t) )). (22)
We have indeed obtained that ( 21) corresponds to a proximal block coordinate descent update [START_REF] Richtárik | Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[END_REF],

i.e. a proximal gradient descent step restricted to a block of coordinates.

When f is the characteristic function of a set, the proximal operator corresponds to the Euclidean projection onto the set. Hence, in our case we have prox r (w) = max(0, w) (the thresholding operator), and we recover the simple update introduced in the main text.

B.2 Convergence Analysis

We start by introducing a convenient lemma.

Lemma 2. For any block of size κ indexed by (k, K), any w ∈ R K(K-1)/2 and any z ∈ R κ , we have:

h(w + U k,K z) ≤ h(w) + z [∇h(w)] k,K + L k,K 2 z 2 .
Proof. This is obtained by applying Taylor's inequality to the function

q w : R κ → R z → h(w + U k,K z)
combined with the convexity and L k,K -block smoothness of h.

We are now ready the prove the convergence rate of our algorithm. We focus below on the more interesting cases where the block size κ > 1, since the case κ = 1 (blocks of size 1) reduces to standard proximal coordinate descent and can be addressed directly by previous work [START_REF] Richtárik | Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function[END_REF][START_REF] Stephen | Coordinate descent algorithms[END_REF].

Recall that in our algorithm, at each iteration an user k is drawn uniformly at random from [K], and then this user samples a set K of κ other users uniformly and without replacement from the set {1, . . . , K} \ {k}. This gives rise to a block of coordinates indexed by (k, K). Let B be the set of such possible block indices. Note that B has cardinality K K-1 κ since for κ > 1 all K-1 κ blocks that can be sampled by an user are unique (i.e., they cannot be sampled by other users). However, it is important to note that unlike commonly assumed in the block coordinate descent literature, our blocks exhibit an overlapping structure: each coordinate block b ∈ B shares some of its coordinates with several other blocks in B. In particular, each coordinate (graph weight) w i,j is shared by user i and user j can thus be part of blocks drawn by both users. Our analysis builds upon the proof technique of [START_REF] Stephen | Coordinate descent algorithms[END_REF], adapting the arguments to handle our update structure based on overlapping blocks rather than single coordinates. Let b t = (k, K) ∈ B be the block of coordinates selected at iteration t. For notational convenience, we write (j, l) ∈ b t to denote the set of coordinates indexed by block b t (i.e., index pairs (j, l) such that j = k and l ∈ K). Consider the expectation of the objective function F (w (t+1) ) in ( 16) over the choice of b t , plugging in the update [START_REF] Jelasity | Gossip-based peer sampling[END_REF]:

E bt [F (w (t+1) )] = E bt h w (t) + U bt (z (t) bt -w (t) bt ) + (j,l)∈bt I ≥0 (z (t) j,l ) + (j,l) / ∈bt I ≥0 (w (t) j,l ) = 1 K K-1 κ b∈B h w (t) + U b (z (t) b -w (t) b ) + (j,l)∈b I ≥0 (z (t) j,l ) + (j,l) / ∈b I ≥0 (w (t) j,l ) ≤ 1 K K-1 κ b∈B h(w (t) ) + (z (t) b -w (t) b ) [∇h(w (t) )] b + L b 2 z (t) b -w (t) b 2 + (j,l)∈b I ≥0 (z (t) j,l ) + (j,l) / ∈b I ≥0 (w (t) j,l ) , (23)
where we have used Lemma 2 to obtain [START_REF] Koriche | Compiling Combinatorial Prediction Games[END_REF], and z

(t)
b is defined as in [START_REF] Jelasity | Gossip-based peer sampling[END_REF] for any block b = (k, K). We now need to aggregate the blocks over the sum in [START_REF] Koriche | Compiling Combinatorial Prediction Games[END_REF], taking into account the overlapping structure of our blocks. We rely on the observation that each coordinate w k,l appears in exactly 2 K-2 κ-1 blocks. Grouping coordinates accordingly in [START_REF] Koriche | Compiling Combinatorial Prediction Games[END_REF] gives:

E bt [F (w (t+1) )] ≤ K K-1 κ -κ K-2 κ-1 K K-1 κ F (w (t) ) + κ K-2 κ-1 K K-1 κ h(w (t) ) + (z (t) -w (t) )∇h(w (t) ) + L max 2 z(t) -w (t) 2 + r(z (t) ) , (24)
where z(t) is defined as in [START_REF] Jiang | Collaborative Deep Learning in Fixed Topology Networks[END_REF]. This is because the block b of z(t) is equal to z We now deal with the second term in [START_REF] Lacoste-Julien | Block-Coordinate Frank-Wolfe Optimization for Structural SVMs[END_REF]. Let us consider the following function H: H(w (t) , z) = h(w (t) ) + (z -w (t) ) ∇h(w (t) ) + L max 2 z -w (t) 2 + r(z).

By σ-strong convexity of h, we have:

H(w (t) , z) ≤ h(z) - σ 2 z -w (t) 2 + L max 2 z -w (t) 2 + r(z) = F (z) + 1 2 (L max -σ) z -w (t) 2 . ( 25
)
Note that H achieves its minimum at z(t) defined in [START_REF] Jiang | Collaborative Deep Learning in Fixed Topology Networks[END_REF]. If we minimize over z both sides of [START_REF] Lafond | Communication efficient distributed algorithms for high-dimensional sparse optimization[END_REF] we get H(w (t) , z(t) ) = min z H(w (t) , z)

≤ min z F (z) + 1 2 (L max -σ) z -w (t) 2 .
By σ-strong convexity of F , 3 we have for any w, w and α ∈ [0, 1]:

F (αw + (1 -α)w ) ≤ αF (w) + (1 -α)F (w ) - σα(1 -α) 2 w -w 2 . ( 26
)
Using the change of variable z = αw * + (1 -α)w (t) for α ∈ [0, 1] and ( 26) we obtain:

H(w (t) , z(t) ) ≤ min α∈[0,1] F αw * + (1 -α)w (t) + 1 2 (L max -σ)α 2 w * -w (t) 2 ≤ min α∈[0,1] αF (w * ) + (1 -α)F (w (t) ) + 1 2 (L max -σ)α 2 -σα(1 -α) w * -w (t) 2 (27)
≤ σ L max F (w * ) + 1 - σ L max F (w (t) ), (28)

D.2.1 Refined communication complexity analysis

The communication complexity of our decentralized graph learning algorithm can be reduced if the users store the models and local losses of all the peers they communicate with. The communication complexity for a given iteration t then depends on the expected number of nodes κ(t) , among the selected K, that the picked user has not yet selected:

κ2Z + κ(t) Z + min t α K , n (Z + log n)) .
The next lemma shows that κ(t) decreases exponentially fast with the number of iterations. Proposition 1. For any T ≥ 1, the expected number of new nodes after T iterations is given by

κ(T ) = κ 1 - κ K(K -1) T -1 .
Proof. At a given iteration t, let k (t) denote the random user that performs the update and K (t) the set of κ users selected by k (t) . We denote by X (t) l,m the random variable indicating if node l selected node m at that iteration:

X (t)
l,m = 0 if node m was not selected by node l at iteration t, 1 otherwise.

Similarly, X l,m indicates if node l has ever selected node m after T iterations.

Let us denote by R (t) = {X k (t) ,j } j∈K (t) the set of random variables that have to be updated at iteration t. The probability that node m is not selected by node l at a given round t is given by

P[X (t) l,m = 0] = P[k (t) = l]P[X k (t) ,m / ∈ R (t) |k (t) = l] + P[k (t) = l]P[X k (t) ,m / ∈ R (t) |k (t) = l] = 1 K 1 - κ K -1 + K -1 K 1 = K 2 -K -κ K(K -1) = 1 - κ K(K -1)
.

As k and K are drawn independently from the previous draws, the probability that node m has never been selected by node l after T iterations is given by:

P[X l,m = 0] = T -1 t=0 P[X (t) l,m = 0] = 1 - κ K(K -1) T .
Finally, the expected number of new nodes seen at iteration T is given by

κ(T ) = E k,K [ |{X k,l ∈ R (T ) |X k,l = 0}| ] = 1 K K k=1 1 K-1 κ K m∈K P[X l,m = 0] = κ 1 - κ K(K -1) T -1 .

E Additional Experiments E.1 Details on Experimental Setting

Hyperparameter tuning. We tune the following hyper-parameters with 3-fold cross validation on the training user datasets: β ∈ {1, . . . , 10 3 } (l 1 constraint for all Adaboost-based methods), µ ∈ {10 -3 , . . . , 10 3 } (trade-off parameter for Dada and Perso-lin), and λ ∈ {10 -3 , . . . , 10 3 } (graph sparsity in Dada-Learned and Perso-lin-Learned).

Description of Moons dataset. We describe here in more details the generation of the synthetic problem MOONS used in the main text, which is constructed from the classic two interleaving Moons dataset which has nonlinear class boundaries. We consider K = 100 users, clustered in 4 groups of respectively K c1 = 10, K c2 = 20, K c3 = 30 and K c4 = 40 users. Each cluster is associated with a rotation angle Θ c of 45, 135, 225 and 315 degrees respectively. We generate a local dataset for each user k by drawing m k ∼ U [START_REF] Baytas | Asynchronous Multi-task Learning[END_REF][START_REF] Frank | An algorithm for quadratic programming[END_REF] training examples and 100 test examples from the two Moons distribution. We then apply a rotation (coplanar to the Moons' distribution) to all the points according to an angle θ k ∼ N (Θ c , 5) where c is the cluster the user belongs to. This construction allows us to control the similarity between users (users from the same cluster are more similar to each other than to those from different clusters). We build an oracle collaboration graph by setting w k,l = exp( cos(θ k -θ l )-1 σ ) with σ = 0.1 and dropping all edges with negligible weights, which we will give as input to Dada-Oracle and Perso-lin-Oracle. In order to make the classification problems more challenging, we add random label noise to the generated local samples by flipping the labels of 5% of the training data, and embed all points in R D space by adding random values for the D -2 empty axes, similar to [START_REF] Vanhaesebrouck | Decentralized Collaborative Learning of Personalized Models over Networks[END_REF]. In the experiments, we set D = 20.

Description of the real datasets. We give details on datasets used in the main text:

• HARWS (Human Activity Recognition With Smartphones) [START_REF] Anguita | A public domain dataset for human activity recognition using smartphones[END_REF], which is composed of records of various types of physical activities, described by D = 561 features and collected from K = 30 users. We focus on the task of distinguishing when a user is sitting or not, use 20% of the records for training and set the number of stumps for the boosting-based methods to n = 1122.

• VEHICLE SENSOR [START_REF] Marco | Vehicle classification in distributed sensor networks[END_REF] contains data from K = 23 sensors describing vehicles driving on a road, where each record is described by D = 100 features. We predict between AAV and DW vehicles, using 20% of the records for training, and fix the number of stumps to n = 1000.

• COMPUTER BUYERS4 consists of K = 190 buyers, who have each evaluated m k = 20 computers described by D = 14 attributes, with an overall score within the range [0, 10].

We use a total of 1407 (between 5 and 10 per user) instances for training and 2393 (between 10 and 15 per user) for testing. We tackle the problem as binary classification, by affecting all instances with a score above 5 to the positive class and the remaining ones to the negative class, and we set the number of stumps to n = 28.

• SCHOOL [START_REF] Goldstein | Multilevel modelling of survey data[END_REF] 5 consists of m = 15362 total student examination records described by D = 17 features, with an overall score in the range [0, 70] from K = 140 secondary schools. In total, there are 11471 instances (between 16 and 188 per user) for training and 3889 (between 5 and 63 per user) for testing. We predict between records with scores smaller or greater than 20 and set the number of stumps to n = 34.

E.2 Effect of the Block Size κ

As discussed in Section D.2, the parameter κ allows to trade-off the communication cost (in bits as well as the number of pairwise connections at each iteration) and the convergence rate for the graph learning steps of Dada-Learned. We study the effect of varying κ on our synthetic dataset MOONS. Figure 3 shows the evolution of the objective function with the number of iterations and with the communication cost depending on κ when learning a graph using the local classifiers learned with Local-boost. Notice that the numerical behavior is consistent with the theory: while increasing κ reduces the number of communication rounds, setting κ = 1 minimizes the total amount of communication (about 5 × 10 5 bits). By way of comparison, the communication cost required to send all weights to all users just once is ZK 2 (K -1)/2 = 1.6 × 10 7 bits. In practice, moderate values of κ can be used to obtain a good trade-off between the number of rounds and the total communication cost, and to reduce the higher variance associated with small values of κ.

E.3 Test Accuracy with respect to Local Dataset Size

In the main text, the reported accuracies are averaged over users. Here, we study the relation between the local test accuracy of users depending on the size of their training set. Figure 5 shows a comparison between Dada-Oracle, Dada-Learned and Local-boost, in order to assess the improvements introduced by our collaborative scheme. On MOONS, Local-boost shows good performance on users with larger training sets but generalizes poorly on users with limited local information. Both Dada-Oracle and Dada-Learned outperform Local-boost, especially on users with small datasets. Remarkably, in the ideal setting where we have access to the ground-truth graph (Dada-Oracle), we are able to fully close the accuracy gaps caused by uneven training set sizes. Dada-Learned is able to match this performance except on users with smaller datasets, which is expected since there is very limited information available to learn reliable similarity weights for these users. On HARWS, Dada-Learned generally improves upon Local-boost, although there is more variability due to difference in difficulty across user tasks and uneven numbers of users in each size group.

E.4 Test Accuracy with respect to Communication Cost

We report the full study of the test accuracies under limited communication budget, summarized in Table 2 of the main text. Figure 5 confirms that Dada-Learned generally allows for reaching higher test accuracies with less communications than Perso-lin-Learned, especially on higher-dimensional datasets, such as HARWS (Figure 5(a)).

E.5 Additional Synthetic Dataset: Moons100

We report the experiments carried out on a synthetic dataset referred to as MOONS100, which is also based on the two interleaving Moons dataset but with a different ground-truth task similarity structure. We consider a set of K = 100 users, each associated with a personal rotation axis drawn from a normal distribution. We generate the local datasets by drawing a random number of points from the two Moons distribution: uniformly between 3 and 20 for training and 100 for testing. We 22

Figure 1 :

 1 Figure 1: Results on the Moons dataset. Left: Training and test accuracy w.r.t. iterations (we display the performance of non-collaborative baselines at convergence with a straight line). Global-lin is off limits at ∼50% accuracy). Right: Average number of neighbors w.r.t. iterations for Dada-Learned.

Figure 2 :

 2 Figure 2: Graph learned on MOONS. Left: Graph weights for the oracle and learned graph (with users ordered by their cluster membership). Right: Visualization of the graph. The node size is proportional to the confidence c k and the color reflects the relative value of the local loss (greener = smaller loss). Nodes are labeled with their rotation angle, and a darker edge color indicates a higher weight.

Figure 3 :

 3 Figure 3: Impact of κ on the convergence rate and the communication cost for learning the graph on MOONS.

Figure 4 :

 4 Figure 4: Average test accuracies with respect to the number of training points of the local sets.

Table 1 :

 1

	HARWS	93.64	92.69	96.31	94.34	93.16	95.70
	VEHICLE	87.11	90.38	91.37	88.02	90.59	90.81
	COMPUTER	62.18	60.68	69.08	69.16	66.61	72.09
	SCHOOL	57.06	70.43	71.92	69.16	66.61	72.22

Test accuracy (%) on real datasets. Best results in boldface and second best in italic bold. Dataset Global-lin Local-lin Perso-lin-Learned Global-boost Local-boost Dada-Learned

Table 2 :

 2 Test accuracy (%) with different fixed communication budgets (# bits) on real datasets.

	Budget	Model	HARWS VEHICLE COMPUTER SCHOOL
	DZ × 160	Perso-lin-Learned Dada-Learned	-95.70	-75.11	-52.03	-56.83
	DZ × 500	Perso-lin-Learned Dada-Learned	81.06 95.70	89.82 89.57	-62.22	-71.90
	DZ × 1000	Perso-lin-Learned Dada-Learned	87.55 95.70	90.52 90.81	68.95 68.83	71.90 72.22

Preprint. Under review.

Alternating optimization converges to a local optimum under mild technical conditions, see[START_REF] Tseng | Convergence of a block coordinate descent method for nondifferentiable minimization[END_REF][START_REF] Tseng | Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization[END_REF][START_REF] Meisam Razaviyayn | A unified convergence analysis of block successive minimization methods for nonsmooth optimization[END_REF].

For the general convex case, we can obtain a slower O(1/T ) convergence rate.

F = h + r is σ-strongly convex since h is σ-strongly convex and r is convex.

https://github.com/probml/pmtkdata/tree/master/conjointAnalysisComputerBuyers

https://github.com/tjanez/PyMTL/tree/master/data/school

Acknowledgments The authors would like to thank Rémi Gilleron for his useful feedback. This research was partially supported by grants ANR-16-CE23-0016-01 and ANR-15-CE23-0026-03, and by a grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020.

where the last inequality is obtained by plugging the value α = σ/L max , which cancels the last term in [START_REF] Lian | Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent[END_REF].

We can now plug [START_REF] Maurer | The Rademacher Complexity of Linear Transformation Classes[END_REF] into [START_REF] Lacoste-Julien | Block-Coordinate Frank-Wolfe Optimization for Structural SVMs[END_REF] and subtract F (w * ) on both sides to get:

where we used the fact that

. We conclude by taking the expectation of both sides with respect to the choice of previous blocks b 0 , . . . , b t-1 followed by a recursive application of the resulting formula.

C Smoothness and Strong Convexity of Graph Learning Formulation

We derive the (block) smoothness and strong convexity parameters of the objective function h(w) when we use

Smoothness. A function f : X → R is L-smooth w.r.t. the Euclidean norm if its gradient is L-Lipschitz, i.e. ∀(x, x ) ∈ X 2 : ∇f (x) -∇f (x ) ≤ L x -x .

In our case, we need to analyze the smoothness of our objective function h for each block of coordinates indexed by (k, K). Therefore for any (w, w ) ∈ R K(K-1)/2 + which differ only in the (k, K)-block, we want to find L k,K such that:

Proof. Recall from the main text that the partial gradient can be written as follows:

where

In our case, g(w) is defined as in (30) so we have

Note also that we set µ 2 = µ 1 , as discussed in the main text.

The first two terms do not depend on w k,K and can thus be ignored. We focus on the Lipschitz constant corresponding to the third term. Let (w, w ) ∈ R K(K-1)/2 + such that they only differ in the block indexed by (k, K). We denote the degree of an user k with respect to w and w by d k (w) = j w k,j and d k (w) = j w k,j respectively. Denoting z k,K = ( 1 d k (w)+δ + 1 d l (w)+δ ) l∈K , we have:

, where to obtain [START_REF] Shen | On the dual formulation of boosting algorithms[END_REF] we used the nonnegativity of the weights and the fact that w and w only differ in the coordinates indexed by (k, K), and ( 33)-( 34)-( 35) by classic properties of norms.

We conclude by combining this result with the quantity 2λ that comes from the last term in v k,K and multiplying by µ 1 .

Observe that L k,K only depends on the block size κ (not the block itself). Hence we also have

It is important to note that the linear dependency of L k,K in the block size κ, which is the worst possible dependency for block Lipschitz constants [START_REF] Stephen | Coordinate descent algorithms[END_REF], is tight for our objective function. This is due to the log-degree term which makes each entry of [∇h(w)] k,K dependent on the sum of all coordinates in w k,K . This linear dependency explains the mild effect of the block size κ on the convergence rate of our algorithm (see the discussion of Section D.2 and the numerical results of Appendix E.2).

Strong convexity. It is easy to see that the objective function h is σ-strongly convex with σ = 2µ 1 λ.

D Communication and Memory

In this section we provide additional details on the communication and memory costs of the proposed method. The section is organized in two parts corresponding to the decentralized boosting algorithm of Section 3 and the graph learning algorithm of Section 4.

D.1 Learning Models: A Logarithmic Communication and Memory Cost

We prove that our Frank-Wolfe algorithm of Section 3 enjoys logarithmic communication and memory costs with respect to the number of base predictors n. Combined with the approach for building sparse collaboration graphs we introduce in Section 4, we obtain a scalable-by-design algorithm. The following analysis stands for systems without failure (all sent messages are correctly received). We express all costs in number of bits, and Z denotes the bit length used to represent floats. Assume we are given a collaboration graph G = ([K], E, w) with K nodes and M edges.

Recall that the algorithm proceeds as follows. At each time step t, a random user k wakes up and performs the following actions:

1. Update step: user k performs a Frank-Wolfe update on its local model based on the most recent information α (t-1) l received from its neighbors l ∈ N k :

k , with γ (t) = 2K/(t + 2K).

Communication step: user k sends its updated model α (t)

k to its neighborhood N k . Memory. Each user needs to store its current model, a copy of its neighbors' models, and the similarity weights associated with its neighbors. Denoting by |N k | the number of neighbors of user k, its memory cost is given by Z(n + |N k |(n + 1)), which leads to a total cost for the network of

The total memory is thus linear in M , K and n. Thanks to the sparsity of the updates, the dependency on n can be reduced from linear to logarithmic by representing models as sparse vectors. Specifically, when initializing the models to zero vectors, the model of an user k who has performed t k updates so far contains at most t k nonzero elements and can be represented using t k (Z + log n) bits: t k Z for the nonzero values and t k log n for their indices.

Communication. At each iteration, an user k updates a single coordinate of its model α k . Hence, it is enough to send to the neighbors the index of the modified coordinate and its new value (or the index and the step size γ (t) k ). Therefore, the communication cost of a single iteration is equal to (Z + log n)|N k |. After T iterations, the expected total communication cost for our approach is

Combining this with Theorem 1, the total communication cost needed to obtain an optimization error smaller than ε amounts to

For the classic case where the set of base predictors consists of a constant number of simple decisions stumps per feature, this translates into a logarithmic cost in the dimensionality of the data (see the experiments of Section 6). This can be much smaller than the cost needed to send all the data to a central server.

D.2 Learning the Collaboration Graph: Communication vs. Convergence

Recall that the algorithm of Section 4 learns in a fully decentralized way a collaboration graph given fixed models α. It is defined by: 1. Draw a set K of κ users and request their current models and degree.

Update the associated weights: w

to the associated user in l ∈ K.

At each iteration, the active user needs to request from each user l ∈ K its current degree d l (w), its personal model α (tα) l and the value of its local loss, where t α is the total number of FW model updates done so far in the network. It then sends the updated weight to each user in K. As the expected number of nonzero entries in the model of an user is at most min(t α /K, n), the expected communication cost for a single iteration is equal to κ(3Z + min( tα K , n)(Z + log n)), where Z is the representation length of a float. This can be further optimized if users have enough local memory to store the models and local losses of all the users they communicate with (see Section D.2.1 below).

In general, Theorem 2 shows that the parameter κ can be used to trade-off the convergence speed and the amount of communication needed at each iteration, especially when the number of users K is large. For the particular case of g(w) = λ w 2 -1 log(d(w) + δ) that we propose, we have σ = 2µλ and L max ≤ µ( κ+1 δ 2 + 2λ) (see Section C). This gives the following shrinking factor in the convergence rate of Theorem 2:

Hence, while increasing κ results in a linear increase in the per-iteration communication cost (as well as in the number of users to communicate with), the impact on ρ in Theorem 2 is mild and fades rather quickly due to the (tight) linear dependence of L k,K in κ. This suggests that choosing κ = 1 will minimize the total communication cost needed to reach solutions of moderate precision (which is usually sufficient for machine learning). Slightly larger values (but still much smaller than K) will provide a better balance between the communication cost and the number of rounds. On the other hand, if high precision solutions are needed or if the number of communication rounds is the primary concern, large values of κ could be used. As shown in Section E.2, the numerical behavior of our algorithm is in line with this theoretical analysis. then apply the random rotation of the user to all its points. We further add random label noise by flipping the labels of 5% of the training data and embed all the points in R D space by adding random values for the D -2 empty axes. In the experiments, the number of dimensions D is fixed to 20 and the number of base functions n to 200. For Dada-Learned, the graph is updated after every 200 iterations of optimizing α. We build an oracle collaboration graph where the weights between users are computed from the angle θ ij between the users' rotation axes, using w i,j = exp( cos(θij )-1 σ

) with σ = 0.1. We drop all edges with negligible weights.

Figure 6 shows the evolution of the training and test accuracy over the iterations for the various approaches defined in the main text. The results are consistent with those presented for MOONS100 in the main text. They clearly show the gain in accuracy provided by our method:Dada-Oracle and Dada-Learned are successful in reducing the overfitting of Local-boost, and allow higher test accuracy than both Global-boost and Perso-lin. Again, we see that our strategy to learn the collaboration graph can effectively make up for the absence of knowledge about the ground-truth similarities between users. At convergence, the learned graph has an average number of neighbors per node E k [|N k |] = 42.64, resulting in a communication complexity for updating the classifiers smaller than the one of the ground-truth graph, which has E k [|N k |] = 60.86 (see Figure 7). We can make the graph even more sparse (hence reducing the communication complexity of Dada) by setting the hyper-parameter λ to smaller values. Of course, learning a sparser graph can also a negative impact on the accuracy of the learned models. In Figure 7(b), we show this trade-off between the sparsity of the graph and the test accuracy of the models for the MOONS100 problem. As expected, as λ → 0 the graph becomes sparser and the test accuracy tends to the performance of Local-boost. Conversely, larger values of λ induce denser graphs, sometimes resulting in better accuracies but at the cost of higher communication complexity.