Dauphine Numérique - Nos recherches
Optimisation et contrôle parental

Présentation

L’optimisation et le contrôle optimal sont au coeur des algorithmes avancées d’Intelligence Artificielle, que ce soit pour accélérer les outils de calibration ou d’estimation, ou plus en amont pour entraîner des algorithmes d’apprentissage, y compris les réseaux de neurones profonds.

L’optimisation est représentée selon ses différentes facettes à Dauphine : optimisation continue et contrôle optimale au CEREMADE, optimisation discrète, et optimisation sans dérivée au LAMSADE.

Optimisation continue

Il s’agit de construire des algorithmes efficace pour l’estimation de paramètre ou la calibration de réseau de neurones. Ceci recouvre notamment la résolution des problèmes inverses, des méthodes de discrétisation d’ordre supérieur pour les flots de gradients sur l’espace de Wasserstein, les systèmes de Langevin avec interaction à champs moyen, ou le contrôle .

L’une des spécialités du CEREMADE, à travers son équipe INRIA Mokaplan, est le transport optimal qui est fortement lié aux problèmes de minimisation sur l’espace de Wasserstein.

Mots clés : Calibration, Problèmes inverses, Flots de gradients, Transport optimal, Optimisation sur l’espace de Wasserstein.

Chercheurs : Irène Waldspruger (chaire PRAIRIE), Gabriel Turinici (anciennement membre de l’Institut Universitaire de France), Guillaume Legendre, Zhenjie Ren, Guillaume Carlier, Jean-David Benamou, Laurent Cohen (chaire PRAIRIE).

Exemples de publications récentes :

  • Hu K., Kazeykina A., Ren Z. (2019), Mean-field Langevin System, Optimal Control and Deep Neural Networks, Paris, Cahier de recherche CEREMADE, Université Paris-Dauphine, 25 p.
  • Waldspurger I., d’Aspremont A., Mallat S. (2015), Phase recovery, Maxcut and complex semidefinite programming, Mathematical Programming, vol. 149, n°1-2, p. 47-81.
  • Legendre G., Turinici G. (2017), Second-order in time schemes for gradient flows in Wasserstein and geodesic metric spaces, Comptes rendus. Mathématique, vol. 355, n°3, p. 345-353.
  • Carlier G., Duval V., Peyré G., Schmitzer B. (2017), Convergence of Entropic Schemes for Optimal Transport and Gradient Flows, SIAM Journal on Mathematical Analysis, vol. 49, n°2, p. 1385-1418.
  • Benamou J-D., Carlier G., Cuturi M., Nenna L., Peyré G. (2015), Iterative Bregman Projections for Regularized Transportation Problems, SIAM Journal on Scientific Computing, vol. 37, n°2, p. A1111–A1138.
  • Turinici G. (2017), Metric gradient flows with state dependent functionals: the Nash-MFG equilibrium flows and their numerical schemes, Nonlinear Analysis, vol. 165, p. 163-181

Contrôle optimal stochastique

Le contrôle optimal consiste à maximiser un critère lié à la trajectoire d’un système contrôlé, souvent dans un environnement aléatoire, parfois en présence d’un joueur adverse.

Il peut s’agir par exemple, de définir une stratégie d’utilisation de robots de trading en présence d’incertitude sur les paramètres de marché, de définir une stratégie d’enchère optimale face à un provider d’espace publicitaire et en présence de multiples enchérisseurs, etc.

Il peut également s’agir de contrôler un système de manière à le maintenir dans un espace défini, par exemple une voiture autonome sur une route. On parle alors de problème de cible stochastique. C’est l’un des domaine historiquement phare du CEREMADE, suivant en particulier les travaux de Pierre-Louis Lions (Chaire au Collège de France) qui est tout à la fois à l’origine de l’invention de la théorie des solutions de viscosité, particulièrement adaptée aux problèmes de contrôle, et de celle des jeux à champ moyen qui permettent de tenir compte des interactions entre joueurs lorsqu’ils sont très nombreux.

C’est également à Dauphine qu’est né la théorie des cibles stochastiques, sous l’impulsion de Nizar Touzi, alors maître de conférence au CEREMADE.

Mots clés : Contrôle optimal stochastique, Solution de viscosité, Optimisation en environnement incertain, Robustesse, Learning, Cibles stochastique, Invariance stochastique, Jeux à champs moyens.

Chercheurs : Pierre-Louis Lions (médaille Fields), Jean-Michel Lasry, Pierre Cardaliaguet, Bruno Bouchard, Daniela Tonon, Julien Claisse, Imen Ben Tahar.

Exemples de publications récentes :

  • Briani A., Cardaliaguet P. (2018), Stable solutions in potential mean field game systems, NoDEA. Nonlinear Differential Equations and Applications, vol. 25, n°1.
  • Abi Jaber E., Bouchard B., Illand C. (2019), Stochastic invariance of closed sets with non-Lipschitz coefficients, Stochastic Processes and their Applications, vol. 129, n°5, p. 1726-1748.
  • Graber P., Mészáros A., Silva F., Tonon D. (2019), The planning problem in mean field games as regularized mass transport, Calculus of Variations and Partial Differential Equations, vol. 58, n°3.
  • Baradel N., Bouchard B., Dang N. (2018), Optimal Control Under Uncertainty and Bayesian Parameters Adjustments, SIAM Journal on Control and Optimization, vol. 56, n°2, p. 1038-1057.
  • Claisse J. (2018), Optimal control of branching diffusion processes: A finite horizon problem, The Annals of Applied Probability, vol. 28, n°1, p. 1-34.
  • Bouchard B., Djehiche B., Kharroubi I. (2017), Quenched mass transport of particles towards a target, Paris, Cahier de recherche CEREMADE, Université Paris-Dauphine, 28 p.
  • Fernandez Tapia J., Guéant O., Lasry J-M. (2017), Optimal Real-Time Bidding Strategies, Applied Mathematics Research Express, vol. March 2017, n°1, 1, p. 142–183.

Optimisation combinatoire

Plusieurs problèmes d’intelligence artificielle, que ce soit en apprentissage automatique, en choix social, ou en décision collective, se posent comme un problème d’optimisation combinatoire sous contraintes.

Le LAMSADE a depuis sa création structuré les communautés nationales et européennes de l’optimisation combinatoire/Recherche Opérationnelle et de l’aide à la décision (seul laboratoire européen dont deux membres ont dirigé la société savante EURO).

Les recherches dans ces thématiques sont structurées au sein des projets MATHIS (Programmation Mathématique et Structures Discrètes) du pôle « Optimisation combinatoire et algorithmique » et « Optimisation Combinatoire Multicritère » à l’interface des pôles Aide à la Décision et Optimisation combinatoire et algorithmique du LAMSADE.

Mots clés : Approche polyédrale, Conception de réseaux, Théorie des Graphes, Méthode probabiliste, Robustesse, Programmation semi-définie positive, système (box-)TDI, Problèmes de grandes tailles, génération de colonnes, algorithmes de plans coupants, Ensemble efficace, Pareto, approximation, énumération, compromis.

Chercheurs : Denis Cornaz, Fabio Furini, Virginie Gabrel, Ararat Harutyunyan, A. Ridha Mahjoub, Cécile Murat, Lucie Galand, Daniek Vanderpooten, Aissi Hassene.

Optimisation non convexe

De nombreuses situations en apprentissage sont naturellement formulées comme des problèmes d’optimisation non convexe : c’est le cas par exemple des réseaux de neurones profonds, ou de problèmes en variables matricielles (complétion, factorisation, apprentissage de dictionnaire).

Sur de telles instances, il peut être particulièrement délicat de garantir la réslution globale du problème, et il devient crucial de garantir que les méthodes ne restent pas bloquées au voisinage de points selles.

On cherche donc à développer des algorithmes avec de fortes garanties théoriques au second ordre, exprimées en termes de complexité au pire cas, qui soient aussi capables de fonctionner en très grande dimension (par rapport au nombre de variables ou à la taille du jeu de données utilisé).  

Mots clés : optimisation non convexe, méthodes d’ordre deux, complexité au pire cas.

Exemples de publications récentes :

  • C. W. Royer, M. O’Neill et S. J. Wright, A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization. Mathematical Programming, 2019.  
  • C. W. Royer et S. J. Wright, Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM Journal on Optimization 28(2):1448-1477, 2018.
  • E. Bergou, Y. Diouane, V. Kungurstev et C. W. Royer, A subsampling line-search method with second-order results. Rapport technique, 2018.  
  • S. Gratton, C. W. Royer et L. N. Vicente, A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds. Mathematical Programming, 2018. 

Optimisation sans dérivées

Lorsque l’on cherche à calibrer les hyperparamètres d’un modèle d’apprentissage complexe, ou à déterminer la meilleure perturbation d’un jeu de données pour fausser l’apprentissage, on se trouve face à des problèmes d’optimisation pour lesquels la fonction objectif est extrêmement coûteuse à évaluer, souvent bruitée, et représente la seule information disponible pour l’optimisation.

Les techniques associées, dites d’optimisation sans dérivées, reposent soit sur de l’exploration par échantillonnage, soit sur la construction de modèles simulant le comportement de la fonction. Nos travaux considèrent principalement l’utilisation de versions probabilistes de ces approches, dont le coût est plus faible que celui des méthodes déterministes, mais pour lequel on peut toujours obtenir des garanties théoriques (convergence presque sûre, complexité en forte probabilité).

L’intérêt à la fois théorique et pratique de l’aléatoire permet ainsi d’envisager l’application de ces stratégies en grande dimension.   

Mots-clés : optimisation sans dérivées, propriétés probabilistes, évaluations coûteuses.

Exemples de publications récentes : 

  • E. Bergou, Y. Diouane, V. Kungurstev et C. W. Royer, A stochastic Levenberg-Marquardt method using random models with application to data assimilation. Rapport technique, 2018.  
  • S. Gratton, C. W. Royer, L. N. Vicente et Z. Zhang, Direct search based on probabilistic feasible descent for bound and linearly constrained problems. Computational Optimization and Applications, 72(3):525-559, 2019.S.
  • Gratton, C. W. Royer, L. N. Vicente et Z. Zhang, Complexity and global rates of trust-region methods based on probablistic models. IMA Journal of Numerical Analysis, 38(3):1579-1597, 2018.  
  • S. Gratton, C. W. Royer et L. N. Vicente, A second-order globally convergent direct-search method and its worst-case complexity. Optimization: A Journal of Mathematical Programming and Operations Research, 65(6):1105-1128, 2016.  
  • S. Gratton, C. W. Royer, L. N. Vicente et Z. Zhang, Direct search based on probabilistic descent. SIAM Journal on Optimization, 25(3):1515-1541, 2015.