  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.
