• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

SGD Algorithms based on Incomplete U ...
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Partie d'ouvrage
Title :
SGD Algorithms based on Incomplete U -statistics: Large-Scale Minimization of Empirical Risk
Author(s) :
Papa, Guillaume [Auteur]
Laboratoire Traitement et Communication de l'Information [LTCI]
Clémençon, Stéphan [Auteur]
Laboratoire Traitement et Communication de l'Information [LTCI]
Bellet, Aurelien [Auteur] refId
Machine Learning in Information Networks [MAGNET]
Book title :
SGD Algorithms based on Incomplete U -statistics: Large-Scale Minimization of Empirical Risk
Publication date :
2015
HAL domain(s) :
Mathématiques [math]
Statistiques [stat]/Machine Learning [stat.ML]
Mathématiques [math]/Statistiques [math.ST]
Mathématiques [math]/Probabilités [math.PR]
English abstract : [en]
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 ...
Show more >
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.Show less >
Language :
Anglais
Audience :
Internationale
Popular science :
Non
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • https://hal.telecom-paris.fr/hal-02107492/document
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017