SGD Algorithms based on Incomplete U -statistics: Large-Scale Minimization of Empirical Risk - Télécom Paris Accéder directement au contenu
Chapitre D'ouvrage Année : 2015

SGD Algorithms based on Incomplete U -statistics: Large-Scale Minimization of Empirical Risk

Résumé

In many learning problems, ranging from clustering to ranking through metric learning, empirical estimates of the risk functional consist of an average over tu-ples (e.g., pairs or triplets) of observations, rather than over individual observations. In this paper, we focus on how to best implement a stochastic approximation approach to solve such risk minimization problems. We argue that in the large-scale setting, gradient estimates should be obtained by sampling tuples of data points with replacement (incomplete U-statistics) instead of sampling data points without replacement (complete U-statistics based on subsamples). We develop a theoretical framework accounting for the substantial impact of this strategy on the generalization ability of the prediction model returned by the Stochastic Gradient Descent (SGD) algorithm. It reveals that the method we promote achieves a much better trade-off between statistical accuracy and computational cost. Beyond the rate bound analysis, experiments on AUC maximization and metric learning provide strong empirical evidence of the superiority of the proposed approach.
Fichier principal
Vignette du fichier
5819-sgd-algorithms-based-on-incomplete-u-statistics-large-scale-minimization-of-empirical-risk.pdf (506.18 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02107492 , version 1 (23-04-2019)

Identifiants

  • HAL Id : hal-02107492 , version 1

Citer

Guillaume Papa, Stéphan Clémençon, Aurélien Bellet. SGD Algorithms based on Incomplete U -statistics: Large-Scale Minimization of Empirical Risk. SGD Algorithms based on Incomplete U -statistics: Large-Scale Minimization of Empirical Risk, 2015, Advances in Neural Information Processing Systems 28 (NIPS 2015). ⟨hal-02107492⟩
74 Consultations
59 Téléchargements

Partager

Gmail Facebook X LinkedIn More