Nos partenaires

CNRS

Rechercher





Accueil du site > Français > Evénements > Séminaires

Séminaires

 

L’IRIT étant localisé sur plusieurs sites, ses séminaires sont organisés et ont lieu soit à l’Université Toulouse 3 Paul Sabatier (UT3), l’Université Toulouse 1 Capitole (UT1), l’INP-ENSEEIHT ou l’Université Toulouse 2 Jean Jaurès (UT2J).

 

Optimisation non convexe avec garanties de complexité via Newton+gradient conjugué
Nonconvex optimization with complexity guarantees: a Newton-CG approach

Clément ROYER - Equipe APO - ENSEEIHT

Mardi 8 Janvier 2019, 14h00 - 15h30
INP-ENSEEIHT, Salle des thèses
Version PDF :

Résumé

On observe actuellement un regain d'intérêt pour la recherche de minima locaux de fonctions non convexes, dû en grande partie à la recrudescence de tels problèmes en sciences des données. Dans ce contexte, on cherche souvent à développer des algorithmes possédant de bonnes garanties de complexité au pire cas. Celles-ci peuvent varier en mesure de coût (nombre d'itérations, d'évaluations, d'opérations algébriques) ainsi qu'en nature (déterministe, en forte probabilité), ce qui ne facilite pas la comparaison entre diverses stratégies. Par ailleurs, les méthodes avec de bonnes propriétés de complexité sont parfois construites de manière théorique, et s'avèrent alors délicates à utiliser en pratique.

Dans cet exposé, nous partons d'une approche classique en optimisation de grande dimension, consistant à incorporer l'algorithme du gradient conjugué linéaire au sein de l'itération de Newton. Nous présentons tout d'abord une instance de base de cet algorithme, pour laquelle des bornes de complexité peuvent être obtenues : celles-ci sont optimales au sein d'une large classe de méthodes dites d'ordre deux. Nous nous intéressons ensuite à établir des garanties plus précises pour ces algorithmes, tout en conservant l'essence même de ces méthodes. A cet effet, nous revisitons la théorie de convergence du gradient conjugué linéaire appliqué à une fonction quadratique. Nous exploitons également des techniques d'algèbre linéaire aléatoire afin d'obtenir des résultats de complexité à l'ordre deux. En incorporant ces deux ingrédients dans notre méthode de type Newton, nous obtenons des résultats de complexité similaires à ceux récemment établis pour des variantes de l'algorithme du gradient accéléré. Enfin, nous terminons cette étude en présentant les clés d'une implémentation efficace de nos stratégies, dont nous illustrons le comportement sur un ensemble de problèmes non convexes.

Abstract

There has been a recent surge of interest for finding local minima of nonconvex functions, mostly due to the outbreak of such instances in data science. In this setting, one aims at developing algorithms with suitable worst-case complexity properties. However, those guarantees may differ in terms of cost measure (number of iterations, evaluations or arithmetic calculations) as well as in strength (deterministic or high-probability results), thereby making it difficult to compare various strategies. In addition, endowing an algorithm with a complexity analysis is sometimes done in a theoretical fashion, and this can be detrimental to the practical use of such a method.

In this talk, we consider a classical approach in large-scale optimization, where the (linear) conjugate gradient algorithm is incorporated in a Newton-type method. We first present a simple instance of this scheme, for which complexity bounds can be derived: those are optimal within a large class of second-order methods. We then propose new variants that compare favorably to recently proposed algorithms based on accelerated gradient in terms of computational cost. To this end, we revisit the convergence theory of the conjugate gradient algorithm when applied to a nonconvex quadratic function. We also leverage randomized linear algebra techniques to allow for second-order complexity results at a suitable cost. By incorporating these tools within our Newton-type framework, we are able to match the guarantees of recently proposed algorithms based on accelerated gradient. Finally, we describe some features of a good implementation of our strategies, and illustrate their performance on several types of nonconvex problems.

 

Retour