Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions

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

Type de document :

Communication dans un congrès avec actes

Titre :

Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions

Auteur(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]

Titre de la manifestation scientifique :

International Conference on Machine Learning (ICML 2016)

Ville :

New York

Pays :

Etats-Unis d'Amérique

Date de début de la manifestation scientifique :

2016-06-19

Mot(s)-clé(s) en anglais :

Decentralized Algorithms
Convex Optimization
Machine Learning
Gossip Protocols

Discipline(s) HAL :

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

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

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

Source :

Harvested from HAL

Fichiers

https://hal.inria.fr/hal-01329315/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-01329315/file/icml16_supp.pdf
Accès libre
Accéder au document

https://hal.inria.fr/hal-01329315/document
Accès libre
Accéder au document

https://hal.inria.fr/hal-01329315/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

icml16.pdf
Accès libre
Accéder au document

icml16_supp.pdf
Accès libre
Accéder au document

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

Fichiers

Gossip Dual Averaging for Decentralized ...

BibTeX

CSV

Excel

RIS