Nonsmooth Optimization for Statistical Learning with Structured Matrix Regularization
Optimisation non-lisse pour l'apprentissage statistique avec avec régularisation matricielle structurée
Résumé
Training machine learning methods boils down to solving optimization problems whose objective functions often decomposes into two parts: a) the empirical risk, built upon the loss function, whose shape is determined by the performance metric and the noise assumptions; b) the regularization penalty, built upon a norm, or a gauge function, whose structure is determined by the prior information available for the problem at hand.
Common loss functions, such as the hinge loss for binary classification, or more advanced loss func- tions, such as the one arising in classification with reject option, are non-smooth. Sparse regularization penalties such as the (vector) l1-penalty, or the (matrix) nuclear-norm penalty, are also non-smooth. The goal of this thesis is to study doubly non-smooth learning problems (with non-smooth loss functions and non-smooth regularization penalties) and first-order optimization algorithms that leverage the composite structure of non-smooth objectives.
In the first chapter, we introduce new regularization penalties, called the group Schatten norms, to generalize the standard Schatten norms to block-structured matrices. We establish the main properties of the group Schatten norms using tools from convex analysis and linear algebra; we retrieve in particular some convex envelope properties. We discuss several potential applications of the group nuclear-norm, in collaborative filtering, database compression, multi-label image tagging.
In the second chapter, we present a survey of smoothing techniques that allow us to use first-order optimization algorithms originally designed for learning problems with nonsmooth loss. We also show how smoothing can be used on the loss function corresponding to the top-k accuracy, used for ranking and multi-class classification problems. We outline some first-order algorithms that can be used in combination with the smoothing technique: i) conditional gradient algorithms; ii) proximal gradient algorithms; iii) incremental gradient algorithms.
In the third chapter, we study further conditional gradient algorithms for solving doubly non-smooth optimization problems. We show that an adaptive smoothing combined with the standard conditional gradient algorithm gives birth to new conditional gradient algorithms having the expected theoretical convergence guarantees. We present promising experimental results in collaborative filtering for movie recommendation and image categorization.
La phase d’apprentissage des méthodes d’apprentissage statistique automatique correspond à la résolution d’un problème d’optimisation mathématique dont la fonction objectif se décompose en deux parties: a) le risque empirique, construit à partir d’une fonction de perte, dont la forme est déterminée par la métrique de performance et les hypothèses sur le bruit sur les données; b) la pénalité de régularisation, construite à partir d’une norme ou fonction jauge, dont la structure est déterminée par l’information à priori disponible sur le problème à résoudre.
Les fonctions de perte usuelles, comme la fonction de perte charnière pour la classification supervisée binaire, ainsi que les fonctions de perte plus avancées comme celle pour la classification supervisée avec possibilité d’abstention, sont non-différentiables. Les pénalités de régularisation comme la norme L1 (vectorielle), ainsi que la norme nucléaire (matricielle), sont également non-différentiables. Le but de cette thèse est d’étudier les problèmes d’apprentissage doublement non-différentiables (perte non- différentiable et régularisation non-différentiable), ainsi que les algorithmes d’optimisation numérique qui sont en mesure de bénéficier de cette structure composite.
Dans le premier chapitre, nous présentons une nouvelle famille de pénalités de régularisation, les normes de Schatten par blocs, qui généralisent les normes de Schatten classiques. Nous démontrons les principales propriétés des normes de Schatten par blocs en faisant appel à des outils d’analyse convexe et d’algèbre linéaire; nous retrouvons en particulier des propriétés caractérisant les normes proposées en termes d’enveloppes convexes. Nous discutons plusieurs applications potentielles de la norme nucléaire par blocs, pour le filtrage collaboratif, la compression de bases de données, et l’annotation multi-étiquettes d’images.
Dans le deuxième chapitre, nous présentons une synthèse de différentes techniques de lissage qui permettent d’utiliser pour le problème doublement non-lisse des algorithmes de premier ordre initialement adaptés aux objectifs composites avec fonction de perte différentiable. Nous montrons comment le lissage peut être utilisé pour lisser la fonction de perte correspondant à la précision au rang k, populaire pour
le classement et la classification supervises d’images. Nous décrivons dans les grandes lignes plusieurs familles d’algorithmes de premier ordre qui peuvent bénéficier du lissage: i) les algorithmes de gradient conditionnel; ii) les algorithmes de gradient proximal; iii) les algorithmes de gradient incrémental.
Dans le troisième chapitre, nous étudions plus en profondeur les algorithmes de gradient conditionnel pour les problèmes d’optimisation non-différentiables d’apprentissage statistique automatique. Nous montrons qu’une stratégie de lissage adaptatif associée à un algorithme de gradient conditionnel donne lieu à de nouveaux algorithmes de gradient conditionnel qui satisfont des garanties de convergence théoriques. Nous présentons des résultats expérimentaux prometteurs des problèmes de filtrage collaboratif pour la recommandation de films et de catégorisation d’images.
Loading...
