Approximation stochastique et régression des moindres carrés, avec applications à l'apprentissage automatique.

Résumé De nombreux problèmes d'apprentissage automatique sont naturellement présentés comme la minimisation d'une fonction lisse définie dans un espace euclidien. Pour l'apprentissage supervisé, cela inclut la régression des moindres carrés et la régression logistique. Alors que les petits problèmes sont résolus efficacement par les algorithmes d'optimisation classiques, les problèmes à grande échelle sont généralement résolus avec des techniques de premier ordre basées sur la descente de gradient. Dans ce manuscrit, nous considérons le cas particulier de la perte quadratique. Dans la première partie, nous nous intéressons à sa minimisation lorsque ses gradients ne sont accessibles que par un oracle stochastique. Dans la seconde partie, nous considérons deux applications de la perte quadratique en apprentissage automatique : le clustering et l'estimation avec des contraintes de forme. Dans la première contribution principale, nous avons fourni un cadre unifié pour l'optimisation des fonctions quadratiques non fortement convexes, qui englobe la descente de gradient accélérée et la descente de gradient moyennée. Ce nouveau cadre suggère un algorithme alternatif qui présente le comportement positif de la moyenne et de l'accélération. La deuxième contribution principale vise à obtenir les taux d'erreur de prédiction optimaux pour la régression des moindres carrés, tant en termes de dépendance au bruit du problème que d'oubli des conditions initiales. Notre nouvel algorithme repose sur la descente de gradient accélérée et moyennée. La troisième contribution principale traite de la minimisation de fonctions objectives composites composées de l'espérance de fonctions quadratiques et d'une fonction convexe. Nous étendons les résultats précédents sur la régression des moindres carrés à tout régularisateur et à toute géométrie représentée par une divergence de Bregman. Comme quatrième contribution, nous considérons le cadre du clustering discriminatif. Nous proposons sa première analyse théorique, une nouvelle extension sparse, une extension naturelle pour le scénario multi-label et un algorithme itératif efficace avec une meilleure complexité en temps de fonctionnement que les méthodes existantes. La cinquième contribution principale traite du problème de la sériation. Nous proposons une approche statistique de ce problème où la matrice est observée avec du bruit et étudions le taux d'estimation minimax correspondant. Nous suggérons également un estimateur efficace en termes de calcul dont les performances sont étudiées à la fois théoriquement et expérimentalement.