Analyse fine de l'apprentissage avec des pertes discrètes.

Résumé Le problème de la conception de stratégies d'apprentissage pour les pertes discrètes (par exemple, le multi-étiquetage, le classement) est actuellement abordé avec des méthodes et des analyses théoriques ad-hoc pour chaque perte. Dans cet article, nous étudions un cadre des moindres carrés pour concevoir systématiquement des algorithmes d'apprentissage pour les pertes discrètes, avec des caractérisations quantitatives en termes de complexité statistique et informatique. En particulier, nous améliorons les résultats existants en fournissant une dépendance explicite du nombre de labels pour une large classe de pertes et des taux d'apprentissage plus rapides dans des conditions de faible bruit. Les résultats théoriques sont complétés par des expériences sur des ensembles de données réels, montrant l'efficacité de l'approche générale proposée.