Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions

Colin, Igor; Bellet, Aurelien; Salmon, Joseph; Clémençon, Stéphan

Document type :

Communication dans un congrès avec actes

Title :

Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions

Author(s) :

Colin, Igor [Auteur]
Laboratoire Traitement et Communication de l'Information [LTCI]
Bellet, Aurelien [Auteur]

Machine Learning in Information Networks [MAGNET]
Salmon, Joseph [Auteur]
Laboratoire Traitement et Communication de l'Information [LTCI]
Clémençon, Stéphan [Auteur]
Laboratoire Traitement et Communication de l'Information [LTCI]

Conference title :

International Conference on Machine Learning (ICML 2016)

City :

New York

Country :

Etats-Unis d'Amérique

Start date of the conference :

2016-06-19

English keyword(s) :

Decentralized Algorithms
Convex Optimization
Machine Learning
Gossip Protocols

HAL domain(s) :

Informatique [cs]/Apprentissage [cs.LG]
Statistiques [stat]/Machine Learning [stat.ML]

English abstract : [en]

In decentralized networks (of sensors, connected objects, etc.), there is an important need for efficient algorithms to optimize a global cost function , for instance to learn a global model from the local data collected ...
Show more >In decentralized networks (of sensors, connected objects, etc.), there is an important need for efficient algorithms to optimize a global cost function , for instance to learn a global model from the local data collected by each computing unit. In this paper, we address the problem of decentralized minimization of pairwise functions of the data points, where these points are distributed over the nodes of a graph defining the communication topology of the network. This general problem finds applications in ranking, distance metric learning and graph inference, among others. We propose new gossip algorithms based on dual averaging which aims at solving such problems both in synchronous and asynchronous settings. The proposed framework is flexible enough to deal with constrained and regularized variants of the optimization problem. Our theoretical analysis reveals that the proposed algorithms preserve the convergence rate of centralized dual averaging up to an additive bias term. We present numerical simulations on Area Under the ROC Curve (AUC) maximization and metric learning problems which illustrate the practical interest of our approach.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

https://hal.inria.fr/hal-01329315/document
Open access
Access the document

https://hal.inria.fr/hal-01329315/file/icml16_supp.pdf
Open access
Access the document

https://hal.inria.fr/hal-01329315/document
Open access
Access the document

https://hal.inria.fr/hal-01329315/document
Open access
Access the document

Gossip Dual Averaging for Decentralized ... BibTeX CSV Excel RIS

Files

Gossip Dual Averaging for Decentralized ...

BibTeX

CSV

Excel

RIS