Prix ​​de dissertation en sciences informatiques canadiennes | 2018

Julie Nutini

Département d'informatique
Université de la Colombie-Britannique

Julie Nutini

Dissertation

Greed is Good: Greedy Optimization Methods for Large-Scale Structured Problems

Résumé

Ce travail porte sur l’apprentissage automatique à grande échelle, en mettant l’accent sur les méthodes gloutonnes. Une tendance récente causée par les grands ensembles de données consiste à utiliser des méthodes d’optimisation ayant un coût d’itération peu coûteux. Dans cette catégorie se trouvent les méthodes de descente par coordonnées (par blocs) et de Kaczmarz, car les mises à jour de ces méthodes ne reposent que sur un sous-espace réduit du problème à chaque itération. Avant nos travaux, la littérature avait qualifié ces variations gloutonnes de ces méthodes de calcul coûteuses avec des vitesses de convergence comparables à celles des versions aléatoires. Dans cette thèse, nous montrons que la cupidité est bonne. Plus précisément, nous montrons que la descente par coordonnée gloutonne et les méthodes de Kaczmarz ont des implémentations efficaces et peuvent être plus rapides que leurs équivalents aléatoires pour certaines structures de problèmes courants en apprentissage automatique. Nous montrons la convergence linéaire pour les méthodes de descente par coordonnées gloutonnes (bloc) sous une relaxation retrouvée de forte convexité à partir de 1963, que nous appelons l’inégalité de Polyak-Lojasiewicz (PL). Parmi les relaxations proposés de forte convexité dans la littérature récente, nous montrons que l’inégalité de la PL est la condition la plus faible qui assure encore un minimum global. De plus, nous soulignons la flexibilité exploitable dans les méthodes de descente par coordonnées de blocs, non seulement dans les différents types de règles de sélection possibles, mais également dans les types de mises à jour que nous pouvons utiliser. Nous montrons que l’utilisation de mises à jour exactes de second ordre ou exactes avec des méthodes de descente par coordonnées de blocs gloutons peut conduire à une convergence superlinéaire ou finie (respectivement) pour des problèmes d’apprentissage automatique courants. Enfin, nous introduisons la notion de “complexité d’ensemble actif”, que nous définissons comme le nombre d’itérations nécessaires pour qu’un algorithme atteigne la variété active optimale, et montrons des bornes explicites pour deux instances de problème courantes lors de l’utilisation du gradient proximal ou la méthode de descente par coordonnées proximales.

Dissertation

Biography

Dr. Nutini est née et a grandi dans la petite ville de ski de Rossland, en Colombie-Britannique, située dans les West Kootenays. Elle a obtenu un baccalauréat en mathématiques (avec distinction) de l’Université de la Colombie-Britannique (campus d’Okanagan) en 2010 et, en 2012, une maîtrise en optimisation mathématique (médaillée d’or du gouverneur général). Dans sa thèse de maîtrise, supervisée par Warren Hare, elle a étudié les méthodes d’optimisation sans dérivées pour les problèmes de minimax finis. Son doctorat était supervisé par Mark Schmidt de l’Université de la Colombie-Britannique à Vancouver. Son domaine de recherche est l’optimisation et l’apprentissage automatique en mettant l’accent sur les méthodes de descente coordonnée.

© 2019 CS-Can / Info-Can. All Rights Reserved.