Valentina Zantedeschi

Aurélien Bellet

Marc Tommasi

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 user 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 when updating the models, and a few random users when updating the graph), ensuring that the procedure naturally scales with the number of users. Overall, our approach is communication-efficient and avoids exchanging personal data. We provide an extensive analysis of 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 user data. This centralized access to resources and datasets is convenient to train machine learning models, 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. The resulting data is not typically balanced nor independent and identically distributed across machines, and additional constraints arise when many parties are involved. In particular, the specificities of each user result in an increase in model complexity and size, and information needs to be exchanged across users to compensate for the lack of local data. In this context, communication is usually a major bottleneck, so that solutions aiming at reaching an agreement between user models or requiring a central coordinator should be avoided.

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][START_REF] Lian | Asynchronous Decentralized Parallel Stochastic Gradient Descent[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 which requires such central coordination [START_REF] Mcmahan | Communicationefficient learning of deep networks from decentralized data[END_REF][START_REF] Konečnỳ | Federated learning: Strategies for improving communication efficiency[END_REF][START_REF] Kairouz | Advances and Open Problems in Federated Learning[END_REF], fully decentralized learning 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 sufficiently 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. We then 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 establish the convergence rate of 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 spar-sity 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, we propose the first approach to train in a fully decentralized way, i.e. without any central server, personalized and nonlinear models in a collaborative way while also learning the collaboration graph. Our main contributions are as follows. (1) We formalize the problem of learning with whom to collaborate, together with personalized models for collaborative decentralized learning. (2) 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 at lower communication costs than existing methods on several datasets.

RELATED WORK

Federated multi-task learning. Our work can be seen as multi-task learning (MTL) where each user is considered as a task. In MTL, multiple tasks are learned simultaneously with the assumption that a structure captures task relationships. A popular approach in MTL is to jointly optimize models for all tasks while enforcing similar models for similar tasks [START_REF] Evgeniou | Regularized multitask learning[END_REF][START_REF] Maurer | The Rademacher Complexity of Linear Transformation Classes[END_REF][START_REF] Dhillon | Semi-supervised multi-task learning of structured prediction models for web information extraction[END_REF]. Task relationships are often considered as known a priori but recent work also tries to learn this structure (see Zhang and Yang, 2017, and references therein). However, in classical MTL approaches data is collected on a central server where the learning algorithm is performed (or it is iid over the machines of a computing cluster). Recently, distributed and federated learning approaches (Wang et al., 2016b,a;[START_REF] Baytas | Asynchronous Multi-task Learning[END_REF][START_REF] Smith | Federated Multi-Task Learning[END_REF] have been proposed to overcome these limitations. Each node holds data for one task (non iid data) but these approaches still 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 task models, creating a significant communication and computation bottleneck when the number of tasks is large. Furthermore, the task similarities do not form a valid weighted graph and are typically not sparse. This makes their problem formulation 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 objectives [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 | D-FW: 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][START_REF] Lian | Asynchronous Decentralized Parallel Stochastic Gradient Descent[END_REF]. In this case, there is no personalization: the graph merely encodes the communication topology 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. In fact, as we demonstrate in our experiments, our decentralized graph learning procedure of Section 5 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 our alternating optimization procedure, thereby broadening their scope. 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 (Section 4) learns nonlinear models with logarithmic communication cost, providing an interesting alternative for problems of high dimension and/or with complex decision boundaries, as illustrated in our experiments.

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, 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 multitask learning[END_REF][START_REF] Maurer | The Rademacher Complexity of Linear Transformation Classes[END_REF][START_REF] Dhillon | Semi-supervised 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 5 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. 2

Outline. In Section 4, we propose a decentralized algorithm to learn nonlinear models given the graph in a greedy boosting manner with communication-efficient updates. In Section 5, 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 2, 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 which is essential to ensure only logarithmic communication complexity in the number of model parameters while optimizing expressive models. 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)) parameter- ized 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 = {α k ∈ R n : α k 1 ≤ β} for each user k as follows:

L k (α k ; S k ) = log m k i=1 e -[A k α k ]i , (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 (2). 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. Our approach is inspired from a recent FW algorithm 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 FW 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] Clarkson | 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
), ( 4)

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). 2. 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] 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 + µ 1 ) and p 0 = f (α (0) ) - f (α * ) is the initial sub-optimality gap.
Theorem 1 shows that large degrees for users with low confidence and small margins penalize the convergence rate much less than for users with large confidence and large margins. This is rather intuitive as users in the latter case have greater influence on the overall solution in Eq. ( 1).

Remarkably, using a few tricks in the representation of the sparse updates, the communication and memory cost needed by our algorithm to converge to an -approximate solution can be shown to be linear in the number of edges of the graph and logarithmic in the number of base predictors. We refer to the supplementary material for details. 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 leading to significantly better complexities than the state-of-the-art (see the experiments of Section 6).

Remark 1 (Other loss functions). We focus on the Adaboost log loss (2) to emphasize that we can learn nonlinear models while keeping the formulation convex. We point out that our algorithm and analysis readily extend to other convex loss functions, as long as we keep an L1-constraint on the parameters.

DECENTRALIZED LEARNING OF 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][START_REF] Kermarrec | Converging quickly to independent uniform random topologies[END_REF]. Let κ ∈ [1..K -1] be a parameter of the algorithm, which in practice is much smaller than K. At each step, a random user k wakes up and samples uniformly and without replacement a set K of κ users from the set {1, . . . , K} \ {k} using the peer sampling service. 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 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). (5)
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, loss value 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. Indeed, no global information is needed to update the weights: the information requested from users in K at step 1 of the algorithm is sufficient to compute (5). 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] Wright | 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. 3Theorem 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 4, 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 analysis 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 2 (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 λ).

EXPERIMENTS

In this section, we study the practical behavior of our approach. Denoting our decentralized Adaboost method introduced in Section 4 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 5 (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 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(3, 15). 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. 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 data (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].

  Proceedings of the 23 rd International Conference on Artificial Intelligence and Statistics (AISTATS) 2020, Palermo, Italy. PMLR: Volume 108. Copyright 2020 by the author(s).

  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 distributions. Despite the noise introduced by the finite sample setting, Dada-Learned effectively makes up for not having access to any knowledge on the relations between the users' tasks. Figure1(right) shows that the graph learned by Dada-Learned remains sparse across time (in fact, always sparser than the oracle graph), ensuring a small communication cost for the model update steps. Figure2(left) confirms that the graph learned by Dada-Learned is able to approximately recover the ground-truth cluster structure. Figure2(right) provides a more detailed visualization of the learned graph. We can clearly see the effect of the inductive bias brought by the confidence-weighted loss term in Problem (1) discussed in Section 3. 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] Duarte | Vehicle classification in distributed sensor networks[END_REF] (K = 23, D = 100), Computer Buyers (K = 190, D = 14) and School (Goldstein, 1991) (K = 140, D = 17). As shown in Table

Figure 2 :

 2 Figure 2: Graph learned on Moons. Top: Graph weights for the oracle and learned graph (with users grouped by cluster). 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.

Table 1 :

 1 Test accuracy (%) on real data, averaged over 3 runs. Best results in boldface, second best in italic. Additional details and results can be found in the supplementary. The source code is available at https://github.com/vzantedeschi/Dada.

	DATASET	HARWS VEH. COMP. SCH.
	Global-linear	93.64	87.11	62.18	57.06
	Local-linear	92.69	90.38	60.68	70.43
	Perso-linear-Learned	96.87	91.45	69.10	71.78
	Global-Adaboost	94.34	88.02	69.16	69.96
	Local-Adaboost	93.16	90.59	66.61	70.69
	Dada-Learned	95.57	91.04	73.55	72.47
	users.

Figure 1: Results on the Moons dataset. Top: 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. Bottom: Average number of neighbors w.r.t. iterations for 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

This work was carried out while the author was affiliated with Univ Lyon, UJM-Saint-Etienne, CNRS, Institut d Optique Graduate School, Laboratoire Hubert Curien UMR 5516, France

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] 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.

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, by the European Union's Horizon 2020 Research and Innovation Program under Grant Agreement No. 825081 COMPRISE and by a grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020.


William De Vazelhes
email: wdevazelhes@gmail.com

C J Carey

Yuan Tang

Nathalie Vauquier
email: nathalie.vauquier@inria.fr

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

Balazs Kegl

metric-learn: Metric Learning Algorithms in Python

Keywords: machine learning, python, metric learning, scikit-learn

metric-learn is an open source Python package implementing supervised and weaklysupervised distance metric learning algorithms. As part of scikit-learn-contrib, it provides a unified interface compatible with scikit-learn which allows to easily perform cross-validation, model selection, and pipelining with other machine learning estimators. metric-learn is thoroughly tested and available on PyPi under the MIT license.

Introduction

Many approaches in machine learning require a measure of distance between data points. Traditionally, practitioners would choose a standard distance metric (Euclidean, City-Block, Cosine, etc.) using a priori knowledge of the domain. However, it is often difficult to design metrics that are well-suited to the particular data and task of interest. Distance metric learning, or simply metric learning [START_REF] Bellet | Metric Learning[END_REF], aims at automatically constructing task-specific distance metrics from data. A key advantage of metric learning is that it can be applied beyond the standard supervised learning setting (data points associated with labels), in situations where only weaker forms of supervision are available (e.g., pairs of points that should be similar/dissimilar). The learned distance metric can be used to perform retrieval tasks such as finding elements (images, documents) of a database that are semantically closest to a query element. It can also be plugged into other machine learning algorithms, for instance to improve the accuracy of nearest neighbors models (for classification, regression, anomaly detection...) or to bias the clusters found by clustering [START_REF] Huang | Learning to Align from Scratch[END_REF].

algorithms towards the intended semantics. Finally, metric learning can be used to perform dimensionality reduction. These use-cases highlight the importance of integrating metric learning with the rest of the machine learning pipeline and tools. metric-learn is an open source package for metric learning in Python, which implements many popular metric-learning algorithms with different levels of supervision through a unified interface. Its API is compatible with scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF], a prominent machine learning library in Python. This allows for streamlined model selection, evaluation, and pipelining with other estimators.

Positioning with respect to other packages. Many metric learning algorithms were originally implemented by their authors in Matlab without a common API convention. 1 In R, the package dml [START_REF] Tang | dml: Distance metric learning in R[END_REF] implements several metric learning algorithms with a unified interface but is not tightly integrated with any general-purpose machine learning library. In Python, pyDML [START_REF] Suárez | pyDML: A Python Library for Distance Metric Learning[END_REF] contains mainly fully supervised and unsupervised algorithms, while pytorch-metric-learning 2 focuses on deep metric learning using the pytorch framework [START_REF] Paszke | PyTorch: An Imperative Style, High-Performance Deep Learning Library[END_REF].

Background on Metric Learning

Metric learning is generally formulated as an optimization problem where one seeks to find the parameters of a distance function that minimize some objective function over the input data. All algorithms currently implemented in metric-learn learn so-called Mahalanobis distances. Given a real-valued parameter matrix L of shape (n components, n features) where n features is the number of features describing the data, the associated Mahalanobis distance between two points x and x is defined as

D L (x, x ) = (Lx -Lx ) (Lx -Lx ).
This is equivalent to Euclidean distance after linear transformation of the feature space defined by L. Thus, if L is the identity matrix, standard Euclidean distance is recovered. Mahalanobis distance metric learning can thus be seen as learning a new embedding space, with potentially reduced dimension n components. Note that D L can also be written as

D L (x, x ) = (x -x ) M (x -x )
, where we refer to M = L L as the Mahalanobis matrix.

Metric learning algorithms can be categorized according to the form of data supervision they require to learn a metric. metric-learn currently implements algorithms that fall into the following categories. Supervised learners learn from a data set with one label per training example, aiming to bring together points from the same class while spreading points from different classes. For instance, data points could be face images and the class could be the identity of the person (see Figure 1a). Pair learners require a set of pairs of points, with each pair labeled to indicate whether the two points are similar or not. These methods aim to learn a metric that brings pairs of similar points closer together and pushes pairs of dissimilar points further away from each other. Such supervision is often simpler to collect than class labels in applications when there are many labels. For instance, a human annotator can often quickly decide whether two face images correspond to the same person (Figure 1b) while matching a face to its identity among many possible people may be difficult. Triplet learners consider 3-tuples of points and learn a metric that brings the first (anchor ) point of each triplet closer to the second point than to the third one. Finally, quadruplet learners consider 4-tuples of points and aim to learn a metric that brings the two first points of each quadruplet closer than the two last points. Both triplet and quadruplets learners can be used to learn a metric space where closer points are more similar with respect to an attribute of interest, in particular when this attribute is continuous and/or difficult to annotate accurately (e.g., the hair color of a person on an image, see Figure 1c, or the age of a person, see Figure 1d). Triplet and quadruplet supervision can also be used in problems with a class hierarchy.

Overview of the Package

The current release of metric-learn (v0.6.2) can be installed from the Python Package Index (PyPI) and conda-forge, for Python 3.6 or later. 3 The source code is available on GitHub at http://github.com/scikit-learn-contrib/metric-learn and is free to use, provided under the MIT license. metric-learn depends on core libraries from the SciPy ecosystem: numpy, scipy, and scikit-learn. Detailed documentation (including installation guidelines, the description of the algorithms and the API, as well as examples) is available at http://contrib.scikit-learn.org/metric-learn. The development is collaborative and open to all contributors through the usual GitHub workflow of issues and pull requests. Community interest for the package has been demonstrated by its recent inclusion in the scikit-learn-contrib organization which hosts high-quality scikit-learncompatible projects, 4 and by its more than 1000 stars and 200 forks on GitHub at the time of writing. The quality of the code is ensured by a thorough test coverage (97% as of June 2020). Every new contribution is automatically checked by a continuous integration platform to enforce sufficient test coverage as well as syntax formatting with flake8.

Currently, metric-learn implements 10 popular metric learning algorithms. Supervised learners include Neighborhood Components Analysis (NCA, [START_REF] Goldberger | Neighbourhood Components Analysis[END_REF], Large Margin Nearest Neighbors (LMNN, [START_REF] Weinberger | Distance Metric Learning for Large Margin Nearest Neighbor Classification[END_REF], Relative Components Analysis (RCA, [START_REF] Shental | Adjustment Learning and Relevant Component Analysis[END_REF], 5 Local Fisher Discriminant Analysis (LFDA, [START_REF] Sugiyama | Dimensionality Reduction of Multimodal Labeled Data by Local Fisher Discriminant Analysis[END_REF] and Metric Learning for Kernel Regression (MLKR, [START_REF] Weinberger | Metric Learning for Kernel Regression[END_REF]. The latter is designed for regression problems with continuous labels. Pair learners include Mahalanobis Metric for Clustering (MMC, [START_REF] Xing | Distance Metric Learning with Application to Clustering with Side-Information[END_REF], Information Theoretic Metric Learning (ITML, [START_REF] Davis | Information-Theoretic Metric Learning[END_REF] and Sparse High-Dimensional Metric 3. Support for Python 2.7 and 3.5 was dropped in v0.6.0. 4. https://github.com/scikit-learn-contrib/scikit-learn-contrib 5. RCA takes as input slightly weaker supervision in the form of chunklets (groups of points of same class).

Learning (SDML, Qi et al., 2009). Finally, the package implements one triplet learner and one quadruplet learner: Sparse Compositional Metric Learning (SCML, [START_REF] Shi | Sparse Compositional Metric Learning[END_REF] and Metric Learning from Relative Comparisons by Minimizing Squared Residual (LSML, [START_REF] Liu | Metric Learning from Relative Comparisons by Minimizing Squared Residual[END_REF]. Detailed descriptions of these algorithms can be found in the package documentation.

Software Architecture and API

metric-learn provides a unified interface to all metric learning algorithms. It is designed to be fully compatible with the functionality of scikit-learn. All metric learners inherit from an abstract BaseMetricLearner class, which itself inherits from scikit-learn's BaseEstimator. All classes inheriting from BaseMetricLearner should implement two methods: get metric (returning a function that computes the distance, which can be plugged into scikit-learn estimators like KMeansClustering) and score pairs (returning the distances between a set of pairs of points passed as a 3D array). Mahalanobis distance learning algorithms also inherit from a MahalanobisMixin interface, which has an attribute components corresponding to the transformation matrix L of the Mahalanobis distance. MahalanobisMixin implements get metric and score pairs accordingly as well as a few additional methods. In particular, transform allows to transform data using components , and get mahalanobis matrix returns the Mahalanobis matrix M = L T L.

Supervised metric learners inherit from scikit-learn's base class TransformerMixin, the same base class used by sklearn.LinearDiscriminantAnalysis and others. As such, they are compatible for pipelining with other estimators via sklearn.pipeline.Pipeline. To illustrate, the following code snippet trains a Pipeline composed of LMNN followed by a k-nearest neighbors classifier on the UCI Wine data set, with the hyperparameters selected with a grid-search. Any other supervised metric learner can be used in place of LMNN.

from sklearn.datasets import load_wine from sklearn.neighbors import KNeighborsClassifier from sklearn.model_selection import train_test_split, GridSearchCV from sklearn.pipeline import Pipeline from metric_learn import LMNN X_train, X_test, y_train, y_test = train_test_split(*load_wine(return_X_y=True)) lmnn_knn = Pipeline(steps=[('lmnn', LMNN()), ('knn', KNeighborsClassifier())]) parameters = {'lmnn__k':[1, 2], 'knn__n_neighbors':[1, 2]} grid_lmnn_knn = GridSearchCV(lmnn_knn, parameters, cv=3, n_jobs=-1, verbose=True) grid_lmnn_knn.fit(X_train, y_train) grid_lmnn_knn.score (X_test, y_test) Weakly supervised algorithms (pair, triplet and quadruplet learners) fit and predict on a set of tuples passed as a 3-dimensional array. Tuples can be pairs, triplets, or quadruplets depending on the algorithm. Pair learners take as input an array-like pairs of shape (n pairs, 2, n features), as well as an array-like y pairs of shape (n pairs,) giving labels (similar or dissimilar) for each pair. In order to predict the labels of new pairs, one needs to set a threshold on the distance value. This threshold can be set manually or automatically calibrated (at fit time or afterwards on a validation set) to optimize a given score such as accuracy or F1-score using the method calibrate threshold. Triplet learners work on array-like of shape (n triplets, 3, n features), where for each triplet we want the first element to be closer to the second than to the third one. Quadruplet learners work on array-like of shape (n quadruplets, 4, n features), where for each quadruplet we want the two first elements to be closer together than the two last ones. Both triplet and quadruplet learners can naturally predict whether a new triplet/quadruplet is in the right order by comparing the two pairwise distances. To illustrate the weakly-supervised learning API, the following code snippet computes cross validation scores for MMC on pairs from Labeled Faces in the Wild [START_REF] Huang | Learning to Align from Scratch[END_REF]. Thanks to our unified interface, MMC can be switched for another pair learner without changing the rest of the code below.

from sklearn.datasets import fetch_lfw_pairs from sklearn.model_selection import cross_validate, train_test_split from metric_learn import MMC ds = fetch_lfw_pairs() pairs = ds.pairs.reshape(*ds.pairs.shape[:2], -1) # we transform 2D images into 1D vectors y_pairs = 2 * ds.target -1 # we need the labels to be in {+1, -1} pairs, _, y_pairs, _ = train_test_split(pairs, y_pairs) cross_validate(MMC(diagonal=True), pairs, y_pairs, scoring='roc_auc ',return_train_score=True,cv=3,verbose=True) 5. Future Work metric-learn is under active development. We list here some promising directions to further improve the package. To scale to large data sets, we would like to implement stochastic solvers (SGD and its variants), forming batches of tuples on the fly to avoid loading all data in memory at once. We also plan to incorporate recent algorithms that provide added value to the package, such as those that can deal with multi-label [START_REF] Liu | Large Margin Metric Learning for Multi-Label Prediction[END_REF] and high-dimensional problems [START_REF] Liu | Escaping the Curse of Dimensionality in Similarity Learning: Efficient Frank-Wolfe Algorithm and Generalization Bounds[END_REF], or learn other forms of metrics like bilinear similarities, nonlinear and local metrics (see [START_REF] Bellet | Metric Learning[END_REF], for a survey).

Figure 1 :

 1 Figure 1: Different types of supervision for metric learning illustrated on face image data taken from the Labeled Faces in the Wild data set (Huang et al., 2012).

Acknowledgments

We are thankful to Inria for funding 2 years of development. We also thank scikit-learn developers from the Inria Parietal team (in particular Gaël Varoquaux, Alexandre Gramfort and Olivier Grisel) for fruitful discussions on the design of the API and funding to attend SciPy 2019, as well as scikit-learn-contrib reviewers for their valuable feedback.